基于动态半马尔可夫路径搜索模型的DTN分簇路由方法  

A Clustering Routing Method Based on Semi-Markov Process and Path-Finding Strategy in DTN

作　　者：王恩[1] 杨永健[1] 李莅[2] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]吉林大学软件学院,长春130012

出　　处：《计算机学报》2015年第3期483-499,共17页Chinese Journal of Computers

基　　金：国家自然科学基金(61272412);吉林省科技发展计划项目-重点项目(20120303)资助~~

摘　　要：在容迟网络环境下,文中提出一种基于动态半马尔可夫路径搜索模型的分簇路由方法 CRSMP(Clustering Routing method based on Semi-Markov process and Path-finding strategy),该方法既考虑了节点拥有的社会属性所导致的分簇问题,又考虑到节点间未来一段时间内的最大相遇概率以及对应的相遇时间,结合分簇结果和相遇情况生成动态路由表,完成一种单副本的路由方法.该方法首先依据节点间路径的相似程度进行分簇,然后运用半马尔可夫模型预测节点间未来某一时刻的相遇概率,依据源节点和目的节点所在的分簇确定可以应用到路由中的节点集合,最后根据路径搜索策略找到最优路径,生成与当前时刻有关的动态路由表.仿真结果表明CRSMP在缓存较小的情况下投递成功率远高于DirectDeliveryRouter、FirstContactRouter和SimBetRouter三种单副本路由方式以及Spray and Wait、Epidemic和Prophet三种多副本路由协议.在10M缓存下的CRSMP有着与500M缓存下的Epidemic相近的路由性能.进一步在真实数据集上进行测试,测试结果表明CRSMP算法依然有着较好的路由性能.In delay tolerant network,we have proposed a clustering routing method based on semi-Markov process and path-finding strategy（CRSMP）,which considers not only the nodes＇ social properties but also the time and maximum probability of node contacts.This method firstly clusters nodes according to path similarity,then predicts node contact probabilities at some point in the future by applying semi-Markov process and determines a collection of nodes used in the routing on the basis of cluster or clusters containing the source node and the destination node.Lastly,dynamic routing tables related to the current time are obtained by executing path-finding algorithm.Simulation results show that the delivery rate of CRSMP is much higher than DirectDeliveryRouter,FirstContactRouter and SimBetRouter which are also single-copy routing schemes under the condition that the size of caches is small,and the delivery rate of CRSMP is also higher than Spray and Wait,Epidemic and Prophet which are multi-copy routing schemes,andCRSMP with 10M caches is similar to Epidemic with 500M caches in routing performance.Furthermore,experiments with the real data set are done,and CRSMP still keeps better routing performance.

关 键 词：容迟网络 半马尔可夫 分簇 动态路由表 路径相似度 路径搜索 

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