基于边独立演化的机会网络时间演化图模型  

Time Evolving Graph Model for Opportunistic Networks Based on Edge-independent Evolution

作　　者：蔡青松[1,2] 牛建伟[2] 

机构地区：[1]北京工商大学计算机与信息工程学院,北京100037 [2]北京航空航天大学计算机学院,北京100191

出　　处：《计算机工程》2011年第15期17-22,共6页Computer Engineering

基　　金：国家自然科学基金资助重点项目(60933011);国家自然科学基金资助项目(60873241);国家"863"计划基金资助项目(2008AA01Z217)

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]