An Optimal Relaying Scheme for Delay-Tolerant Networks With Heterogeneous Mobile Nodes

Abstract—To provide communication services in delay-tolerant networks (DTNs) where there may exist no end-to-end paths between mobile node pairs, a variety of relaying and routing algorithms have been proposed under the assumption that the mobile nodes are homogeneously distributed in the network with the same contact rate and delivery cost. However, experimental data have revealed the heterogeneous contact rates between node pairs, and various applications of DTNs have shown that the mobile nodes often belong to different types in terms of energy consumption, communication ability, and other properties. Fol-lowing the philosophy of exploiting the heterogeneous features of nodes to enhance the routing performance, we design an optimal relaying scheme for DTNs, which takes into account the nodes’ heterogeneous contact rates and delivery costs when selecting relays to minimize the delivery cost while satisfying the required message delivery probability. We use the trace-driven simulations to demonstrate the effectiveness of our optimal relaying scheme in various distributions of nodes ’ delivery costs and mobility environments. Simulation results show that our proposed optimal relaying scheme requires the least delivery cost and achieves the largest maximum delivery probability, compared with the schemes that neglect or do not fully take into account nodes ’ heterogeneity. Index Terms—Delay-tolerant networks (DTNs), heterogeneous networks, message delivery cost, message delivery probability, optimal relaying scheme. I