Optimal Routing Strategy in Throw-box based Delay Tolerant Network

Routing in intermittently connected networks, or delay tolerant networks, can utilize the assistants from statically deployed computing and communication devices (throw-boxes) at certain locations. In such as a network, a mobile destination node will receive messages from throw-boxes when it moves close to the location. The virtual links between throw-boxes are formed by mobile nodes that are able to carry messages from one box to another. Messages temporally stored at the boxes could be transported among these boxes for being quickly collected by the interested mobile receivers. In many scenarios of mobile networks, mobile nodes reveal the mobility pattern of frequent visits to a few locations. When such locations are deployed with throw-boxes, searching the shortest delay path among boxes becomes a critical issue for the senders. In this paper, we study routing strategies that take considerations of the time-varying delay of the virtual links occurred between arbitrary two throwboxes, instead of using the expected delay to measure the virtual link. A Markov Chain is introduced to model the realistic link evolution. After that, a policy iteration algorithm is given to derive the optimal policy for message delivery. In evaluating the routing scheme, we analyze UMassDieselNet contact trace to extract the states of the virtual links. The simulation results using the resulting network graph validate the advantages of the proposed routing strategy.