Social Frameworks

The Haggle Project at the University of Cambridge has published a number of papers regarding the use of social communities in delay tolerant networks or, as they call them, pocket-switched networks. The following classes implement some of their contributions in ONE.

The Entire routing.community Package

BubbleRap.jar

Last Updated: Oct 15th, 2010 12:27pm

Social Routing

Interfaces

routing.community.CommunityDetectionEngine

An interface that provides access to the local community of some object. The Decision Engine Classes below implement this interface, and it's main purpose right now is give Reports generic access to a node's local community.

Last Updated: Oct 15th, 2010 11:50am

Implementations

routing.community.LABELDecisionEngine

An implementation of the LABEL protocol described in How Small Labels Create Big Improvements by Pan Hui and Jon Crowcroft (2007). This class is a bit of an extension from that work in that they authors describe a scenario where the nodes (conference goers) self-describe their community (with a label). Here, we use the community detection techniques the authors present in later works. They refer to this protocol, but, to my knowledge, don't explicitly state that it employs a community detection algorithm.

This class is an extension of routing.RoutingDecisionEngine. It's therefore used in conjunction with routing.DecisionEngineRouter as described in the example settings below.

Last Updated: Oct 15th, 2010 11:49am

routing.community.DistributedBubbleRap

An implementation of the Bubble Rap protocol discussed in BUBBLE Rap: Social-based Forwarding in Delay Tolerant Networks by Pan Hui et al. (MobiHoc '08). The protocol can actually utilize any methods of community detection and centrality measures to perform routing, and several methods are presented throughout the various works of the authors. To accommodate this, this class refers to instances of CommunityDetection and Centrality interfaces so that different algorithms can be swapped into the protcol.

This class too is an extension of routing.RoutingDecisionEngine. It's therefore used in conjunction with routing.DecisionEngineRouter as described in the example settings below.

Last Updated: Oct 15th, 2010 11:45am

Community Detection

Interfaces

routing.community.CommunityDetection

An interface that defines the methods used by DistributedBubbleRap to acquire information about a node's local community. Implementers of this interface are the community detection algorithms discussed in the authors' works.

Last Updated: Oct 15th, 2010 11:51am

Implementations

routing.community.SimpleCommunityDetection

Implements the SIMPLE community detection algorithm described in Distributed Community Detection in Delay Tolerant Networks by Hui et al.

Last Updated: Oct 14th, 2010 1:38pm

routing.community.KCliqueCommunityDetection

Implements the K-Clique community detection algorithm described in Distributed Community Detection in Delay Tolerant Networks by Hui et al.

Last Updated: Oct 15th, 2010 11:53am

routing.community.ModularityCommunityDetection

It's coming

Centrality Algorithms

Interfaces

routing.community.Centrality

An interface that abstracts each of the centrality computation algorithms described in BUBBLE Rap: Social-based Forwarding in Delay Tolerant Networks by Pan Hui et al. (MobiHoc '08).

Last Updated: Oct 15th, 2010 11:54am

Implementations

routing.community.DegreeCentrality

Computes the global and local centrality values over the contact history of the entire simulation without partitioning and averaging. The global centrality in this case is essentially the number of unique encounters the node has had in the simulation, and the local centrality is the number of these contacts that were made with members of the local community.

BUBBLE Rap: Social-based Forwarding in Delay Tolerant Networks by Pan Hui et al. (MobiHoc '08) is a bit vague about this algorithm. The discussion describes a protocol for estimating the node's centrality by maintaining the node's degree (unique past encounters). They go on to say that this value, computed for all time, does not correlate well to the node's centrality, but the node degree over the past six hours does. They further claim that computing this value for all time is difficult and state that computing either a average for multiple six hour periods in the past, which they do in CWindowCentrality, or simply using the prior six hour window, which they do in SWindowCentrality would be better approaches. A third algorithm called DEGREE is also presented as a computation of the node degree for all time, but it's unclear whether this refers to an average over all prior six-hour time windows or simply the total number of prior unique encounters (without any averaging). As such, I've implemented both possible algorithms. DegreeCentrality is the simpler and less computationally demanding of the two. It estimates the node's global centrality as the total number of unique nodes encountered in the past and local centrality as the same but confined only to nodes within the local community. See the AvgDegreeCentrality class for the other algorithm.

Last Updated: Oct 14th, 2010 1:39pm

routing.community.AvgDegreeCentrality

Estimates the global and local centrality of a node as the average node degree observed over the entire life of the node. The timeline is broken into a series of time windows in each of which the node degree is computed, and an average over all time windows is taken.

See the discussion above in DegreeCentrality.

Last Updated: Oct 15th, 2010 11:18am

routing.community.SWindowCentrality

Computes the global and local centrality of a node using the SWindow centrality algorithm described in BUBBLE Rap: Social-based Forwarding in Delay Tolerant Networks by Pan Hui et al. (MobiHoc '08)

Last Updated: Oct 15th, 2010 12:04pm

routing.community.CWindowCentrality

Computes the global and local centrality of a node using the CWindow centrality algorithm described in BUBBLE Rap: Social-based Forwarding in Delay Tolerant Networks by Pan Hui et al. (MobiHoc '08)

Last Updated: Oct 15th, 2010 12:13pm

Reports

report.CommunityDetectionReport

At the end of the simulation (or interval), this report extracts the detected communities from each host whose RoutingDecisionEngine implements the CommunityDetectionEngine interface (and, consequently, whose router is an instance of DecisionEngineRouter). It prints each unique community to the report on its own line preceeded by the size of the community.

Last Updated: Oct 15th, 2010 12:30pm

report.DeliveryCentralityReport

Computes the Betweenness Centrality for all the nodes in the simulation following the work described in BUBBLE Rap: Social-based Forwarding in Delay Tolerant Networks by Pan Hui et al. (MobiHoc '08).

Last Updated: Oct 15th, 2010 12:32pm

report.SimpleCommunityDetectionReport

A stand alone report that will detect communities over time during the simulation using the SIMPLE community detection algorithm.

Last Updated: Oct 15th, 2010 2:24pm

Helper Classes

routing.community.Duration

Stores the start and end point of some duration. The class is currently used by the decision engines (LABEL and DiBuBB) to record the connection histories over the course of the simulation.

Last Updated: Oct 7th, 2010 2:17pm

Example Settings

The following is an snippet of the settings file needed to detect

   Group.router = DecisionEngineRouter
   DecisionEngineRouter.decisionEngine = community.DistributedBubbleRap
   DecisionEngineRouter.communityDetectAlg = routing.community.KCliqueCommunityDetection
   DecisionEngineRouter.K = 5
   DecisionEngineRouter.familiarThreshold = 700
   DecisionEngineRouter.centralityAlg = routing.community.CWindowCentrality
		

Decision Engine

routing.DecisionEngineRouter

This is just a routing framework that supports my usual M.O. when developing a routing protocol on ONE. I had noticed that much of the simulation time was spent calling MessageRouter.update() and that many of the decisions made in the function didn't really change until an event occurred, like a connection going up or down. This router is designed to remove as much code from the update() call as possible by keeping a list of premade routing decisions (message paired with connections to forward them across) that gets updated when events occur. To make this generic, when an event occurs, another object is consulted to make the actual decisions, which must implement the routing.RoutingDecisionEngine interface.

Note that you'll get a few compilation errors with this class at first that actually require changes to MessageRouter.java included with ONE. The errors really suggest the changes that need to be made: one is the addition of the DENIED_DELIVERED constant to the list given in MessageRouter.

Last Updated: Apr 18th, 2011 2:43pm

routing.RoutingDecisionEngine

An interface that abstracts routing logic from the decision engine router. Each method generally corresponds to an event that occurs in the router that requires a decision to be made.

Last Updated: Aug 4th, 2010 4:50pm

Spray and Focus Routing

routing.SprayAndFocusRouter

An implmentation of the Spray and Focus Routing Protocol as described in Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility by Thrasyvoulos Spyropoulos et al. The ONE simplifies most routing protocols that require an exchange of information with each new connection. Instead of simulating the exchange of this information in the communication path, the simulated instances of the mobile devices access each other's tables in memory. This version of Spray and Focus actually generates these exchange messages on each connection in order to be more realistic, but this can create issues with message delivery reports.

Last Updated: Oct 15th, 2010 2:37pm

routing.decisionengine.SnFDecisionEngine

A version of the Spray and Focus Routing Protocol for the DecisionEngineRouter. This version does not generate the extra exchange messages on each new connection, and it also is likely to run faster in the decision engine framework than the version above.

Last Updated: Oct 15th, 2010 2:50pm

Movement Models

movement.FixedMovement

A simple stationary movement model where the node positions are specified in a WKT file. The nodes can be assigned positions in the order they appear in the file or select their position randomly from the list. No two nodes take the same position as well.

Last Updated: Oct 15th, 2010 3:10pm

movement.EveningActivityControlSystem

A version augmented to avoid situations where a node would be waiting forever for other participants in its EveningTrip.

Last Updated: Aug 13th, 2010 11:31am

movement.EveningActivityMovement

A version augmented to avoid situations where a node would be waiting forever for other participants in its EveningTrip.

Last Updated: Aug 15th, 2010 1:23pm

movement.EveningTrip

A version augmented to avoid situations where a node would be waiting forever for other participants in its EveningTrip.

Last Updated: Aug 13th, 2010 11:08am

movement.BusTravellerMovement

A version that makes bus travellers exhibit a more realistic movement pattern in that they will only board a bus that is headed in the direction they want to go with a minimal amount of stops between boarding and exiting the bus.

Last Updated: Oct 15th, 2010 3:17pm

Network Interfaces

core.Activeness

An interface to abstract the method by which a node or some other entity determines whether or not it is currently active.

Last Updated: Oct 19th, 2010 11:51am

core.NetworkInterface

A version of NetworkInterface augmented to support interfaces.APInterface and interfaces.SmartphoneActiveness. It defines its own concept of activeness where a given network interface can be actively trying to create connections with other hosts, in which case isActive() returns true, can be accepting connections from other hosts, in which case a newly added method, acceptingConnections(), returns true, or both.

Last Updated: Sep 17th, 2010 4:06pm

interfaces.APInterface

A NetworkInterface subclass that acts like an access point. Collectively, all the APInterfaces in the simulation maintain knowledge of all the hosts within their ranges. When a new mobile host comes in range of an AP, rather than create a connection between the mobile host and itself, the AP creates multiple connections between the mobile host and every other mobile host in range of any AP. As such, the AP does not act as an endpoint but provides the means for a mobile device to access distant nodes out of its range.

This is done to avoid an issue with DTN Routing. Routing protocols only update when connections change state (go up or down). If a group of access points created interconnections amongst themselves, as mobile nodes connected and disconnected from them, they would update their routing tables but not send those updates across the simulated wired connections, meaning it would be hard to locate a destination beyond the wired network.

Last Updated: Oct 18th, 2010 3:19pm

interfaces.SmartphoneActiveness

A class that provides functionality akin to the waking and sleeping behavior of a mobile device being used by a human as described in Diversity in Smartphone Usage by Falaki et al. (2010). The authors found that the usage behavior of a smartphone, as it relates to the ONE simulator, can be modelled as a series of epochs oscillating between active and inactive states where the device is available to make and accept connections only in the active intervals. They model the duration of the active intervals by adding an exponential distribution with a Pareto distribution where the minimum value of the Pareto distribution is equivalent to the timeout of the smartphone screen. They model the duration between active intervals as a Weibul distribution.

The parameters for each of the (component) distributions ranges across the population of users. This class can either configure the population of simulated nodes to use the same distribution parameters or select the distribution parameters from the ranges found in the paper.

Last Updated: Oct 19th, 2010 12:05pm

interfaces.SimpleBroadcastInterface

A revised version of the standard ONE SimpleBroadcastInterface modified for the changes made to NetworkInterface in the class above and compatiable with APInterace.

Last Updated: Oct 18th, 2010 3:23pm

interfaces.InterferenceLimitedInterface

A revised version of the standard ONE InterferenceLimitedInterface modified for the changes made to NetworkInterface in the class above and compatiable with APInterace.

Last Updated: Oct 18th, 2010 3:30pm

Settings

core.Settings

A version of Settings.java that does the following:

• Allows the user to employ the value filling functionality for any setting.
• Adds an addSetting method to support setting declarations on the command line. See the DTNSim class below.
• Reappropriates secondary namespaces as alternative locations for a given setting. This, in conjunction with the SimScenario class below, facilitates a settings file such as the following:

    People.speed = 3, 5
    People.nrOfInterfaces = 2
    People.interface1 = btInterface
    People.interface2 = 3gInterface
    People.waitTime = 10, 30
    People.movementModel = WorkingDayMovement
       
    Bus.speed = 20, 30
    Bus.nrOfInterfaces = 1
    Bus.interface1 = btInterface
    Bus.waitTime = 30, 60
    Bus.movementModel = BusMovement
    
    Group1.secondaryNamespace = People
    Group2.secondaryNamespace = People
    Group3. ...
    
    Group10.secondaryNamespace = Bus
    Group11.secondaryNamespace = Bus
    Group12. ...
  					

Last Updated: Sep 5th, 2010 2:46pm

core.SimScenario

A version that checks for the declaration of a seconardary namespace for each host group. To be used with the core.Settings file above.

Last Updated: Sep 10th, 2010 5:41pm

core.DTNSim

Adds a command line switch, '-d', to support the definition of settings in the command line (in conjunction with the Settings class above). To simply this, the settings specified cannot contain any spaces and multiple settings can be specified by separating each with a '@@' token. For example:

java core.DTNSim -b 1:1 -d MovementModel.rngSeed=2@@Group.nrofHosts=3 my.settings
				

Last Updated: Oct 8th, 2010 3:14pm

Pittsburgh Model Package

Pittsburgh.tar.gz

All the files below in a neat little tar ball.

Last Updated: Oct 20th, 2010 1:42pm

Settings File

pittsburgh_settings.txt

This is a settings file for ONE that defines node groups for people and buses in the Working Day Movement Model using the files below where groups of "people" nodes are appropriately paired with their intended bus nodes through a BusControlSystem object and with other node groups for shopping trips through a EveningTripControlSystem object.

Node groups are also defined for fixed infrastructure at public and semi-public places like local coffee shops and the University of Pittsburgh campus.

This file is in no way intended to define a complete simulation scenario. Interfaces, speeds, wait times, and routing protocols are not defined here. This file just defines appropriate home, work, and shopping locations for nodes such that a bus route adequately services their movement between each and that evening trip groups are appropriately chosen.

Last Updated: Oct 20th, 2010 1:35pm

Pittsburgh WKT Map

Pittsburgh.wkt

Last Updated: Aug 15th, 2010 1:57pm

Fixed Locations

These are files containing lists of WKT POINTs where the location of a stationary node should reside. These files can be used in conjunction with the movement.FixedMovement class above to layout nodes in the ONE.

Starbucks.wkt

WiFi Access Points at Pittsburgh Area Starbucks.

Last Updated: Aug 24th, 2010 1:07pm

localCoffeeShops.wkt

WiFi Access Points at other local coffee shops around Pittsburgh.

Last Updated: Aug 24th, 2010 1:56pm

APs.wkt

Other miscellaneous access points, among them some Univ. of Pittsburgh campus WiFi locations.

Last Updated: Aug 24th, 2010 1:10pm

cellTower.wkt

Dedicated cell tower structures in Pittsburgh (those with dedicated land).

Last Updated: Aug 24th, 2010 3:56pm

cellAntennas.wkt

Cell antennas in Pittsburgh attached to buildings or other structures. This is not a definitive list, but provides enough towers such that they cover the physical space of the included Pittsburgh map.

Last Updated: Aug 24th, 2010 4:38pm

Homes

Being that the Working Day Model can only associate a node group with one bus route through the BusControlSystem class, the home locations for each node group center around the bus routes that service the area.

home-1F.wkt

Homes at the end of the 1F bus route (Northern most part of the Pittsburgh map).

Last Updated: Aug 13th, 2010 5:16pm

home-54C.wkt

Homes along the 54C bus route, which snakes through much of the map.

Last Updated: Aug 13th, 2010 4:16pm

home-64.wkt

Homes along the 64 bus route, running vertically along the eastern side of the map.

Last Updated: Aug 13th, 2010 5:59pm

home-eba.wkt

Homes at the end of the EBA bus route (eastern most portion of the map).

Last Updated: Aug 13th, 2010 5:26pm

home-highland.wkt

Homes in the Highland Park neighborhood in the northeastern part of the map, which is accessed by several bus routes: 71A, 74B, 77D.

Last Updated: Aug 13th, 2010 5:36pm

home-mtwash.wkt

Homes in the Mount Washington neighborhood just south of Downtown across the river. Serviced by the 43E bus route.

Last Updated: Aug 13th, 2010 6:06pm

home-shady-75.wkt

Homes in the Shadyside neighborhood in the eastern central part of the map serviced by the 75 bus route.

Last Updated: Aug 13th, 2010 6:15pm

home-sqhill.wkt

Homes in the Squirrel Hill neighborhood in the eastern central part of the map. Serviced by 61D and 64 bus routes.

Last Updated: Aug 12th, 2010 7:26pm

home-ss.wkt

Homes in the South Side neighborhood in the southern portion of the map serviced by the 54C, 51B, and 75 bus routes.

Last Updated: Aug 13th, 2010 4:38pm

home-wbw.wkt

Homes along the west busway route in the western part of the map and serviced by the G2 bus route.

Last Updated: Aug 13th, 2010 4:57pm

Meeting Locations

meet-54C.wkt

Meeting locations for nodes using the 54C bus route.

Last Updated: Aug 13th, 2010 4:21pm

meet-dt.wkt

Meeting locations Downtown (where the rivers meets).

Last Updated: Aug 13th, 2010 5:17pm

meet-oak-shady.wkt

Meeting locations in the Oakland and Shadyside neighborhoods for nodes that live in shadyside whose bus route travels through Oakland

Last Updated: Aug 13th, 2010 5:45pm

meet-oakland-dt.wkt

Meeting locations in the Oakland and Downtown neighborhoods for nodes that work downtown and whose bus route travels through Oakland.

Last Updated: Aug 13th, 2010 3:50pm

meet-shady-oak-ss.wkt

Meeting locations in the Shadyside, Oakland and South Side neighborhoods for nodes using either the 75 or 54C bus routes.

Last Updated: Aug 13th, 2010 4:02pm

meet-ss.wkt

Meeting locations in the South Side neighborhood for nodes using the 51B bus route.

Last Updated: Aug 13th, 2010 4:37pm

meet-waterfront-sqhill.wkt

Meeting locations in the Squirrel Hill neighborhood and at the Waterfront Mall for nodes using the 61D bus route.

Last Updated: Aug 13th, 2010 3:41pm

Offices

office-54C.wkt

Working locations for nodes using the 54C bus route.

Last Updated: Aug 13th, 2010 4:19pm

office-64.wkt

Working locations for nodes using the 64 bus route.

Last Updated: Aug 13th, 2010 6:01pm

office-dt.wkt

Working locations Downtown (where the rivers meets).

Last Updated: Aug 13th, 2010 4:35pm

office-oakland.wkt

Working locations in the Oakland neighborhood for nodes whose bus route travels through Oakland

Last Updated: Aug 13th, 2010 5:44pm

office-oakland-dt.wkt

Working locations in the Oakland and Downtown neighborhoods for nodes whose bus route travels through Oakland to Downtown.

Last Updated: Aug 13th, 2010 3:48pm

office-oaklandss.wkt

Working locations in the South Side and Oakland neighborhoods for nodes using the 75 or 54C bus routes.

Last Updated: Aug 13th, 2010 4:06pm

Bus Routes

The bus routes in Pittsburgh change on a regular basis due to constant funding crisis. These are some routes circa early to mid 2010.

1F.wkt

1F bus route travelling between downtown and northern area of the map.

Last Updated: Aug 13th, 2010 1:44pm

43E.wkt

43E bus route travelling between downtown and the Mount Washington neighborhood just across the river south of downtown.

Last Updated: Aug 13th, 2010 1:56pm

51B.wkt

51B bus route travelling between the Downtown and South Side Neighborhoods.

Last Updated: Aug 13th, 2010 1:36pm

54C.wkt

54C bus route travelling between the South Side, Oakland, Shadyside, Bloomfield, Strip District and North Side neighborhoods. This route snakes around eastern portion of the map mostly.

Last Updated: Aug 13th, 2010 9:53am

61D.wkt

61D bus route travelling through the Downtown, Oakland, and Squirrel Hill neighborhoods ending at the Waterfront Mall.

Last Updated: Aug 10th, 2010 10:08am

64.wkt

64 bus route travelling vertically along the eastern portion of the map through the Lawrenceville, Shadyside, and Squirrel Hill neighborhoods to and from the Waterfront Mall.

Last Updated: Aug 13th, 2010 2:26pm

71A.wkt

71A bus route travelling between the Highland Park and Downtown neighborhoods through Oakland and Shadyside.

Last Updated: Aug 13th, 2010 2:41pm

71C.wkt

71C bus route travelling between the eastern portion of the map and Downtown through Oakland and Shadyside. (This bus route was recently changed in Pittsburgh)

Last Updated: Aug 13th, 2010 3:29pm

74B.wkt

74B bus route travelling between the Highland Park and Downtown neighborhoods through Oakland and Shadyside.

Last Updated: Aug 13th, 2010 3:15pm

75.wkt

75 bus route travelling between the Shadyside and South Side neighborhoods through Oakland.

Last Updated: Aug 10th, 2010 10:55am

77D.wkt

77D bus route travelling between the Highland Park and Downtown neighborhoods through the Bloomfield and Strip District neighborhoods.

Last Updated: Aug 13th, 2010 1:22pm

EBA.wkt

EBA bus route travelling along the east busway (eastern portion of the map) to Downtown.

Last Updated: Aug 13th, 2010 2:17pm

G2.wkt

G2 bus route travelling along the west busway (western portion of the map) to the Downtown and Oakland neighborhoods.

Last Updated: Aug 10th, 2010 12:53pm