On the cost/delay tradeoff of wireless delay tolerant geographic routing

Abstract

In Delay Tolerant Networks (DTNs), there is a fundamental tradeoff between the aggregate transport cost of a packet and the delay in its delivery. We study this tradeoff in the context of geographical routing in wireless DTNs.We first specify the optimal cost/delay tradeoff, i.e., the tradeoff under optimal network operation, using a dynamic network construction termed the Cost/Delay Evolving Graph (C/DEG) and the Optimal Cost/Delay Curve (OC/DC), a function that gives the minimum possible aggregate transportation cost versus the maximum permitted delivery delay.We proceed to evaluate the performance of two known delay tolerant geographic routing rules, i.e., MOVE and AeroRP, a delay tolerant version of the geographic routing rule that selects as next relay the node for which the cost-per-progress ratio is minimized, and finally two novel rules, the Balanced Ratio Rule (BRR) and the Composite Rule (CR). The evaluation is in terms of the aggregate packet transmission cost as a function of the maximum permitted packet delivery delay. Simulations show that CR achieves a cost/delay tradeoff that is overall the closest to the optimal one specified by the OC/DC, while BRR achieves the smallest aggregate transmission costs for large packet delays and a fixed transmission cost model.