Mobility Entropy and Message Routing inCommunity-Structured Delay Tolerant Networks

Hideya Ochiai

Hiroshi Esaki

The University of Tokyo / NICT
Asia Future Internet (AsiaFI) 200912th-16th January 2009. Beijing, China.

Table of Contents• Introduction• Mobility Entropy and Routing• Potential-Based Approach• Evaluation• Conclusion

Introduction• Message delivery in DTNs
MessageAB
CCircle: Transmission Range• How can they manage routing, when 100 nodes?
• A large number of node mobility patterns• Contribution of this work:– Mobility Entropy, Community-Structured Environment (CSE)– Potential-based Entropy Adaptive Routing (PEAR)

Table of Contents• Introduction• Mobility Entropy and Routing• Potential-Based Approach• Evaluation• Conclusion

Mobility Entropy and Message Routing• Mobility Entropy represents uniformity of node distribution.

Small Entropy

Large Entropy• Widely Distributed• Locally Distributed• Contact with many nodes• Contact with only a small• Message Delivery by Mobility
set of nodes• Message Delivery by Routing

Distribution of Nodes

Small Entropy Case
• Short overlapping of node distributionDistribution

 Small Contact Areasx2x1

Distribution of Nodes

Large Entropy Case
• Long overlapping of node distribution

Distribution

 Large Contact Areasx2x1

Message Delivery

Small Entropy Case
Distribution

Intermediate Nodes
SourceDestinationx
Contact Areas

Message Delivery

Distribution

Large Entropy Case

SourceDestinationx
A Contact Area

Community-Structured Environment (CSE)
1. Nodes can communicate with each other when they are in the same community.
2. Nodes move among predefined community set repeatedly.
3. Mobility entropy is given by the number of communities a node belongs to.
Mobility Entropy  log 2 Contact
Contact Area
Area

The number of communities
each node belongs to.

Community A
Contact
Contact Area
Area
Contact
Contact Area
Area
Community B

Community CCSE and Mobility Entropy
If every node belongs

If every node belongs

to 2 communities.

to 3 communities.

c0c0

c0
c0
c2
c2

c2
c2
c1
c1
Mobility Entropy

 log 2 2

c1
c1
Mobility Entropy

 log 2 3

When nodes belong totwo communities.

Mobility Entropy = 1

When nodes belong tofour communities.

Mobility Entropy = 2

CSE and Mobility Entropy

Mobility Entropy = 0

Mobility Entropy = 1

Mobility Entropy = 2

Mobility Entropy = 3

Table of Contents• Introduction• Mobility Entropy and Routing• Potential-Based Approach• Evaluation• ConclusionPotential-Based Routing
PotentialInternetGateway

Data Flow

Live
Live E!
E!

Truck
Data Flow

SensorTo deliver sensor readings to the Internet GW: Wireless Device

Message Forwarding in Potential-Based Routing

V x d

Message for dx2xF x dd
A message goes down the curve until it reaches the destination.

x1

How to develop potential-field in PEARPotential-Field Construction
ddddV n, t  1  V n, t   D min V k , t   V n, t   BoundaryConditionn  N , V d n,0   0

t , V d d , t   0knbr ( n )D( 0),  ( 0) const.

Diffusion Equation
V d n, t  1  V d n, t   D  V d k , t   V d n, t knbr ( n )Potential and Message Routing

Potential

Small Entropy Case
Message Delivery

SourceIntermediateDestination

V d n, t  1  V d n, t   D min V d k , t   V d n, t   Distributionknbr ( n )SourceNodeIntermediate Nodes
Destination
Nodex

Message Delivery by PEAR

Potential

Small Entropy Case

SourceIntermediate

Destination

Potential and Message Routing

Source NodeDirect Path

Potential

Large Entropy Case
Intermediate
Nodes

Destination NodeV d n, t  1  V d n, t   D min V d k , t   V d n, t   Distributionknbr ( n )SourceNodeDestination
Nodex

Message Delivery by PEAR

Large Entropy Case
Potential

sourcedestination
SourceIntermediate

Destination

Table of Contents• Introduction• Mobility Entropy and Routing• Potential-Based Approach• Evaluation• Conclusion

Evaluation• Evaluation of Delivery Rate and Total Transmissions
on Mobility Entropy• PEAR in comparison with:– Epidemic Routing– Spray and Wait
– Link-State Routing• Minimum Expected Delay (MED)• Maximum Delivery Probability (MDP)• Java-based CSE simulator– Ignored: link-bandwidth, radio properties, messagepartitioning, storage size, etc...

Delivery RateTotal Message Transmissions

Table of Contents• Introduction• Mobility Entropy and Routing• Potential-Based Approach• Evaluation• Conclusion

Conclusion• Mobility Entropy– The new metrics that describes mobile environment.
• Small entropy: Nodes are locally distributed.
• Large entropy: Nodes are widely distributed.

– Community-Structured Environment• PEAR achieved high delivery probability– Small entropy: hop-by-hop routing– Large entropy: multiplying messages

Thank you..

Mobility Entropy

Large Entropy Case

Message DeliverySource

IntermediateSource NodeDirect Path

Potential

Potential

Small Entropy Case

Destination NodeDestinationknbr ( n )Intermediate Nodes
Destination
Nodex

Distribution

Distribution

SourceNode

V d n, t  1  V d n, t   D min V d k , t   V d n, t   V d n, t  1  V d n, t   D min V d k , t   V d n, t   knbr ( n )Intermediate
Nodes

Source
NodeDestination
Nodex