Potential-Based Entropy Adaptive Routing
for Disruption Tolerant Networks

Hideya Ochiai

Hiroshi Esaki

The University of Tokyo / NICTDTNRG, IETF 76 Hiroshima, 2009-11-13

Outline• Introduction• Potential-based entropy adaptive routing• Prototype implementation• Campus-wide experiment• Conclusion

Introduction• DTN for opportunistic networking– Isolated sensor networking / vehicular ad-hoc networks– Intermittent connectivity / isolated networks
Isolated Networks

12
7

4IntermittentConnectivity• API

38Mobile Node5– void sendMessage(ID dst, String msg);– void recvMessage(ID src, String msg);• All the nodes are always virtually connected.

6

Contributions of this work
Implementation and deployment ofpotential-based entropy adaptive routing (PEAR)– PEAR autonomously enables message delivery inad-hoc manner.
– PEAR dynamically adapts to wide-range of mobility
patterns without being aware of mobility pattern itself.
• In general, the performance of routing algorithms arestrongly dependent on mobility patterns.

Outline

Message Delivery

SourceIntermediate

Source NodeDirect PathPotential

Potential• Introduction• Potential-based entropy adaptive routing• Prototype implementation• Campus-wide experiment• Conclusion

Destination

Destination Nodeknbr( n )Intermediate Nodes
Destination
Nodex

Small entropy case

Distribution

Distribution

Potential-field

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 )IntermediateNodes

SourceNodePossible
Intermediate Nodes

DestinationNodex
Large entropy caseCharacterize Mobility Pattern by Entropy

Small Entropy Case

Large Entropy Case

Locally Distributed

Widely Distributed

Entropy and Delivery Patterns1s23

12

dA bolder link indicateslarger contact time.

d3

Small Entropy Case

Large Entropy Case

Biased contact

Uniform contact

It should choose the best path

It should improve delivery rateby increasing redundancy.

How does PEAR achieve that ??
• For choosing the next hop node:– Potential-based routing– Potential-field construction (inspired by diffusiontheory)• For message delivery– Copy-based message delivery
 Transfer-based message delivery

Potential-Based Routing
PotentialInternetGateway

Data Flow

ve E!

Truck
Data FlowSensor

To deliver sensor readings to the Internet GW: Wireless DevicePotential-Field Construction in PEAR
Potential-Field ConstructionV n, t  1  V n, t   D min V k , t   V n, t   knbr( n )n  N , V d n,0  0D( 0),  ( 0) const.
t , V d d , t   0ddddDiffusion Equationdddd
V n, t  1  V n, t  D  V k , t  V n, t knbr( n )Potential-Field Construction
V d n, t  1  V d n, t   D min V d k , t   V d n, t  knbr( n )dV Vk , tk,Vt  nV, t n, t   VV nn, t, t11 V nn,,ttDD minddddnbr
kknbr( n )( n )ddd

t , V d , t   0dConstructed
Potential-FielddV Vk , tk,Vt  nV, t n, t   VV nn, t, t11 V nn,,ttDD minddddnbrkknbr( n )( n )ddd

t , V d d , t   0dTransfer-Based v.s. Copy-Based
Message Delivery
PEAR

Transfer-Based
Message Delivery

Copy-Based
Message Delivery

Copy-Based Message Transfer in PEAR
Do you have any
information about
msg_id= XXXX ??

H BODYH BODYs

H BODYn-1

sourcen

H BODYn+1Algorithm
For each k in nexthop
stat := check_message_status(k,m)
if stat = NEIGHBOR_NOT_FOUND thencontinue
if stat = MESSAGE_DELIVERED thendelete_content(m)m.IsDelivered:=truecontinue
if m.DisseminationTTL>0 Thenif stat = NOT_HAVE Thencopy(k,m)
if m.DisseminationTTL > DISSEMINATION_MODE_TIME thenm.DisseminationTTL :=DISSEMINATION_MODE_TIMEd• NOT_HAVE• ALREADY_HAVE• DELIVERED

destination

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

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 )SourceNodePossible
Intermediate Nodes

Destination
Nodex

Rough Simulation-Based Evaluation

Rough Simulation-Based Evaluation (Summary)
Delivery Rate

PEAR100%

Spray and Wait

Link State Based

Village-to-village

Mobility Pattern

Human-to-humanOutline• Introduction• Potential-based entropy adaptive routing• Prototype implementation• Campus-wide experiment• Conclusion

Software Design of PEAR
Application(Message Send / Receive)
Nexthop Table

V (n, t )V (n, t )nexthop (n)MessagePool

V (k , t )k  nbr (n)V (k , t )k  nbr (n)Advertisement

Message Manager

Advertisement Manager

Potential Table

Investigation Message Copy

About 3000 lines in C.
Footprint is 34k byte in object code.

Armadillo220

Power Circuit

Storage(2GByte)

Wifi 802.11g

Battery(6.0V 2100mAh)

Armadillo-220Outline• Introduction• Potential-based entropy adaptive routing• Prototype implementation• Campus-wide experiment• Conclusion
Group2Group1Gateway

電気系会議室3

Sensor2
Group3

Sensor150m

Delivery patternContact graphExperiment settings

Members for the experiment• The University of Tokyo– Ochiai, Shimotada, Fujita, Kawakami, Himura,Sugita, Lert, Wan, Minshin, Motodate, Kure,
Kawaguchi, Ishizuka• Nara Institute of Science and Technology– Dr. Matsuura• Keio University– Dr. Miyakawa, Yamanouchi• Cisco Systems, Inc.
– MomoseScenario Overview
Armadillo-220
Wifi Interface (USB)
Storage (USB)

リチウムイオン蓄電池

InternetGW (#99)

1. Deploy sensors in remote sites.
2. Sensors periodically transmit data to the GW
3. Mobility of nodes enables delivery of data fromsensors to the GW.

Armadillo-220
Wifi Interface (USB)
Storage (USB)

リチウムイオン蓄電池

Armadillo-220
Wifi Interface (USB)
Storage (USB)

リチウムイオン蓄電池

Mobile Node (#4)
Armadillo-220
Wifi Interface (USB)
Storage (USB)

Armadillo-220

リチウムイオン蓄電池
Wifi Interface (USB)
Storage (USB)

リチウムイオン蓄電池

Mobile Node (#3)
Armadillo-220
Wifi Interface (USB)
Storage (USB)

Mobile Node (#5)
Armadillo-220
Wifi Interface (USB)
Storage (USB)

リチウムイオン蓄電池

SensorStatic (#2)

Armadillo-220
Wifi Interface (USB)
Storage (USB)

リチウムイオン蓄電池

リチウムイオン蓄電池

SensorStatic (#1)

Group2

Group1

Gateway

電気系会議室3

Sensor2
Group3

Sensor150m

Contact Graph

Mobility Entropy≒2.1

The number of received neighbor advertisement packets.
e.g., node 8 received 45 advertisements from sensor 1.

Potential for the Gateway

Message Flow (1/2)

GW: #99

Red arrow: messages from sensor 1 (#1)
Blue arrow: messages from sensor 2 (#2)

Message Flow (2/2)

The number along with an arrow indicates the time of the transfer

Distribution of Delivery Latency

E.g., 50 = [0,100]

Collected Temperature Data from Sensor 1

Delivery Rate = 100 %Collected Temperature Data from Sensor 2

Delivery Rate = 100 %Outline• Introduction• Potential-based entropy adaptive routing• Prototype implementation• Campus-wide experiment• Conclusion

Conclusion• We proposed PEAR for opportunistic networking– It directly forwards a message at small entropy cases– It replicates a message to improve delivery latency atlarge entropy cases• Implementation and deployment of PEAR
– Prototype system with embedded computers– 10-node scale campus wide experiment• PEAR has achieved 100% delivery rate withreasonable delay on the experiment settings.

Thank you...

Intermediate

Destination

Source NodeDirect Path

Message Delivery

SourcePotential

Potential

Google by "Mobility Entropy and Message Routing"Intermediate
Nodes

Destination NodeV d n, t  1  V d n, t   D min V d k , t   V d n, t   knbr( n )Intermediate NodesDestination
NodeDistribution

Distributionknbr( n )SourceNodeSource
NodeDestination
NodePossible
Intermediate Nodes

Large entropy case

Small entropy caseArmadillo220

V d n, t  1  V d n, t   D min V d k , t   V d n, t   

Storage(2GByte) Wifi 802.11g

Delivery Rate

PEAR

100%

Spray and Wait

Link State BasedPower Circuit

Mobility Pattern

Battery(6.0V 2100mAh)

Prototype implementation

PEAR maintains high delivery rate overwide-range of mobility patterns