Adaptive Backbone-Based Routing in Delay Tolerant Networks

In this paper, we develop a localized algorithm for the routing problem in delay tolerant networks (DTNs). We first design a modeling approach to derive a weighted graph from the DTN, taking into consideration the obtained history contact information of the nodes. This modeling provides adaptive ness by accommodating diverse network predication characteristics. Based on the derived weighted graph, we then put forward the concept of a delay tolerant network backbone for the DTN. When only the nodes in the backbone forward data, the routing in the DTN is achieved with the optimal performance in terms of the expected end-to-end delivery latency. This work is inspired by the widely used virtual backbone-based routing for mobile ad hoc and sensor networks. In DTNs with intermittent connectivity, we explore the meeting frequency between nodes for the construction of the backbone. Accordingly, we develop the delay tolerant connected dominating set (DTCDS) as an approximation to the delay tolerant network backbone, and further formalize the problem of minimum equally effective DTCDS. A localized heuristic algorithm for constructing an efficient DTCDS is proposed. Performance studies include a theoretical analysis and a comprehensive simulation on the proposed algorithm.