Exploiting Heterogeneity for Improving Forwarding Performance in Mobile Opportunistic Networks: An Analytic Approach

Heterogeneity arises in a wide range of scenarios in mobile opportunistic networks and is one of the key factors that govern the performance of forwarding algorithms. While the heterogeneity has been empirically investigated and exploited in the design of new forwarding algorithms, it has been typically ignored or marginalized when it comes to rigorous performance analysis of such algorithms. In this paper, we develop an analytical framework to quantify the performance gain achievable by exploiting the heterogeneity in mobile nodes' contact dynamics. In particular, we derive a delay upper bound of a heterogeneity-aware static forwarding policy per each given number of message copies and obtain its closed-form expression, which enables our quantitative study on the benefit of leveraging underlying heterogeneity structure in the design of forwarding algorithms. In addition, we develop a dynamic forwarding policy that performs as an extension of the static forwarding policy while proven to improve the delay performance. We then demonstrate that only a small fraction of total (unlimited) message copies, via both static and dynamic forwarding policies, are enough under various heterogeneous network settings to achieve the same delay as that obtained using the unlimited message copies when the networks become homogeneous. We also show that, given the same number of message copies, our dynamic forwarding policy significantly outperforms the `homogeneous-optimal' forwarding policy (up to about 50 percent improvement in the delay performance), especially when the number of message copies allowed in the networks is small.

1 Introduction

Mobile opportunistic networks, a.k.a. delay or disruption tolerant networks, have received much attention from the networking research community as a promising evolution of mobile ad-hoc networks toward several applications such as Pocket Switched Networks [2] or UMass Dieselnet [3]. In mobile opportunistic networks, network connectivity is changing over time and frequently disrupted due to node mobility, power limitation, limited storage, among others. To overcome this intermittent connectivity nature, mobile opportunistic networks employ a ‘store-carry-and-forward’ principle in which mobile nodes can carry messages and copy and/or relay them to other nodes upon encounter, thereby rendering messages eventually delivered to their destinations.