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.%高效的消息传输机制是机会网络的核心问题.在对CRAWDAD公开发布的Trace数据进行深入分析的基础上刻画了机会网络中的消息传输路径特性.节点的相遇时间分析指出节点间存在明显的聚集性,少量的节点相遇对网络的连通性和消息传输成功率起决定性作用.为分析该特性对消息传输路径的影响,构造了机会网络的时间演化图TEG(time evolving graph)模型以计算任意节点对间的消息单拷贝最小延迟路径(single copy minimal delay path,SC-MDP).结果表明网络具有典型的"小世界"特性,即大多数消息平均通过较短路径可达目的节点.结论指出,探测并利用发生次数较少但对网络连通性具有重要影响的节点相遇进行消息转发,能够有效降低网络的传榆代价和提高传输成功率.
展开▼
