摘要：

根据机会网络中拓扑的高度动态性和随时间演化的特性，提出一种基于边独立演化的时间演化图(E-TEG)模型。该模型采用马尔可夫链和生灭过程刻画演化过程的时间相关性，利用Laplace后继法则估计边的出生和死亡概率，E-TEG最终收敛于非均匀随机图。采用CRAWDAD数据集对模型进行实验，结果表明，E-TEG能够准确反映机会网络中消息传输路径的演化特性。

关键词: 机会网络, 边独立时间演化图, 生灭过程, Laplace后继法则, 随机图

Abstract:

This paper introduces an Edge-independent Time Evolving Graph(E-TEG) model to capture the evolution of the connectivity properties of Opportunistic Networks(OppNet). E-TEG model is presented through using discrete time Markovian model to deal with the time dependencies of consecutive time-step indexed network snapshots, and the dynamic of each possible edge is assumed to be an independent birth-death process. In addition, given the sequence data, the birth and the death probability of each edge are estimated through using Laplace’s rule of succession. It shows that an E-TEG eventually converges to an un-uniform random graph. E-TEG model is validated through CRAWDAD trace datasets by computing the fastest path of each pair of nodes in an instance of E-TEG.

Key words: Opportunistic Networks(OppNet), Edge-independent Time Evolving Graph(E-TEG), birth-death process, Laplace’s rule of success- sion, random graph

中图分类号: 

• TP393