Properties of Message Delivery Path in Opportunistic Networks

One of the main challenges in opportunistic networks is how to deliver messages effectively. Mobile nodes have to rely on encounter opportunities to exchange data due to no complete end-to-end path existing in such networks. In this paper, based on in-depth analysis of encounter occurrence process and contact frequency, we find that both of them exhibit unique power-law distributions. The great majority of contacts occurred in short period of time shows that mobile nodes cluster into communities during moving, which indicates the spatial dependency existing among them. The fact that most node pairs only encountered a few times implies that the network connectivity greatly depends on those rare contacts. Using Time Evolving Graph (TEG) theory we analyze the Minimum Delay Path (MDP) for each node pair and find that although there are large number of nodes in networks, the average length of MDP is relative small, which indicates that communities are inherently organized into a hierarchy structure as human society is, and some rare encounters have a significant influence on the average length of MDP as well as the message delivery delay. Our results suggest that decentralized community detection algorithms will achieve optimal message delivery performance with the help of node encounter history information about inter-community.