Optimal Online Data Dissemination for Resource Constrained Mobile Opportunistic Networks

Delivery delay and communication costs are two conflicting design issues for mobile opportunistic networks with nonreplenishable energy resources. In this paper, we study the optimal data dissemination for resource constrained mobile opportunistic networks, i.e., the delay-constrained least-cost multicasting in mobile opportunistic networks. We formally formulate the problem and introduce a centralized heuristic algorithm which aims to discover a tree for multicasting, in order to meet the delay constraint and achieve low communication cost. While the above algorithm can be implemented by each individual node, it is intrinsically centralized (requiring global information) and, thus, impractical for real-world implementation. However, it offers useful insights for the development of a distributed scheme. The essence of the centralized approach is to first learn the probabilities to deliver the data along different paths to different nodes and then decide the optimal multicast tree by striking the balance between cost and delivery probability. In mobile opportunistic networks, even if the optimal routing tree can be computed by the centralized solution, it is the 'best' only on a statistic basis for a large number of data packets. It is not necessarily the best solution for every individual transmission. Based on the above observation, we develop a distributed online algorithm using optimal stopping theory, in which in each meeting event, nodes make adaptive online decisions on whether this communication opportunity should be exploited to deliver data packets. We carry out simulations to evaluate the scalability of the proposed schemes. Furthermore, we prototype the proposed distributed online multicast algorithm using Nexus tablets and conduct an experiment that involves 37 volunteers and lasts for 21 days to demonstrate its effectiveness.