Message Delivery Properties in Opportunistic Networks

Finding an effective message delivery path in opportunistic networks is a challenging task as there is no complete end-to-end path existing in such a network and mobile nodes rely on encounter opportunities to exchange data with each other. Based on the trace datasets publicly released by CRAWDAD, we comprehensively analyze the nodal encounter occurrence and node contact frequency, and find that both of them exhibit unique power-law distributions. Most of the contacts occurring in short period of time show that mobile nodes cluster into communities during moving, which indicates the spatial dependency among them. The fact that most node pairs only encounter few times implies that the network connectivity greatly depends on those rare contacts. Using the time evolving graph (TEG) theory, we analyze the single copy minimal delay path (SC-MDP) for each node pair on TEG and find that the average hops of SC-MDP is relative small even with a large number of nodes in the network, which indicates that communities are inherently organized into a hierarchy structure as our human society is, and some rare encounters have significant influence on the average length of MDP as well as the transport delay. Our results demonstrate that decentralized community detection algorithms based on nodal historical contact information for inter-community based message delivery can achieve optimal performance.