收稿日期:20140713;修回日 期:20140903 基金 项目: 陕西省科 技计 划自 然 基金 重点 项 目 (2012JZ8005);军 事学 研 究生 课题
(2011XXXXX523)
作者简介:钟
!
(1990),男,江苏金坛人,硕士,主要研究方向为延迟 /中断容忍网络(18629615032@163.com);夏靖波(1963),男,河北秦皇
岛人,教授,博导,博士(后),主要研究方向为通信网络规划与评估;付凯(1987),男,山东济宁人,博士,主要研究方向为延迟 /中断容忍网络;
柏骏(1985),男,四川南充人,博士研究生,主要研究方向为网络流量测量与分类;张毅卜(1989),男,陕西西安人,硕士,主要研究方向为网络流
量测量.
基于动态分簇的 DTN路由算法
钟
"
,夏靖波,付 凯,柏 骏,张毅卜
(空军工程大学 信息与导航学院,西安 710077)
摘 要:针对延迟 /中断容忍网络特定场景下节点具有的集群运动模式问题,并结合近年来 DTN研究领域分簇
路由算法的研究进展,提出了基于动态分簇的 DTN路由算法。该算法采用基于节点重要度的分簇算法,并选择
层次分析法作为节点各参数权重的计算准则;定义节点关联度和稳定度作为普通节点归属特定簇的依据。簇内
采取直接递交方式进行消息转发,簇间消息转发时根据节点历史相遇频率选取更可能与目的节点相遇的中继节
点。仿真结果表明,与其他经典算法相比,无论是消息生存时间还是仿真时间的影响,该算法在消息递交率和平
均延迟等方面都表现出了较好的网络性能。
关键词:延迟 /中断容忍网络;集群运动模式;层次分析法;历史相遇频率
中图分类号:TP39304 文献标志码:A 文章编号:10013695(2015)11339504
doi:10.3969/j.issn.10013695.2015.11.046
DynamicclusterbasedroutingalgorithminDTN
ZhongYun,XiaJingbo,FuKai,BaiJun,ZhangYibo
(CollegeofInformation&Navigation,AirForceEngineeringUniversity,Xi’an710077,China)
Abstract:Inviewoftheissuethatnodesindelay/disruptiontolerantnetworkhaveclusteringmovementpatterninparticular
scenarios,andcombiningtheprogressofclusterbasedroutingalgorithminDTNresearchfieldfortherecentyears,thispaper
proposedadynamicclusterbasedroutingalgorithminDTN.Itadoptedclusteringalgorithmbasedonnodeimportancedegree,
choseanalytichierarchyprocess(AHP)asthenodeweightcalculationprinciple,definednoderelevancedegreeandstability
degreeasthebasisofordinarynodesbelongingtoaparticularcluster.Sourcenodeforwardedmessagesdirectlytothedestina
tionnodeinintracluster,whileforwardingmessagesinintercluster,thealgorithmselectedthenodewhichwasmorelikelyto
encounterwithdestinationnodeasrelaynodeaccordingtothehistoricalencounterfrequency.Thesimulationresultshowsthat,
comparedtoothertypicalDTNroutingalgorithms,thealgorithmcanimprovethemessagedeliveryratioandreducetheaverage
delayinscenarioswithdifferenttimetoliveofmessagesandsimulationtime.
Keywords:delay/disruptiontolerantnetwork(DTN);clusteringmovementpattern;AHP;historicalencounterfrequency
!
引言
延迟 /中断容忍网络(DTN)中,由于节点的高速运动和通
信环境的影响从而造成链路断开频繁和端到端时延增大。因
此,在 DTN中主要采用“存储—携带—转发”机制用于解决这
类网络中消息递交率不高的问题,其应用场景主要包括未来卫
星通信网络
[1]
、车载网络
[2]
、农地数据收集网络
[3]
等。
最初的 DTN路由算法都是平面结构的,即节点是同构的,
并不存在性能和功能上的差异。目前,已有的平面结构路由协
议主要分为基于转发策略和基于洪泛策略。其中基于转发策
略的路由算法主要包括以 PRoPHETv2
[4]
为代表的概率转发路
由、以 seekandfocus
[5]
为代表的效用转发路由以及以 firstcon
tact
[6]
为代表的首遇转发路由等;基于洪泛策略的路由算法主要
包括以 epidemic
[7]
为代表的副本不限洪泛路由以及以 sprayand
wait
[8]
和 directdelivery
[9]
为代表的副本受限洪泛路由。
随着 DTN相关研究的深入,研究人员发现,在节点具有集
群运动模式的网络场景中,节点的移动往往具有一致的规律
性;且各节点所拥有的网络资源并不均等,节点具有异构性。
具有特定指挥关系和编组移动特性的战术互联网络就是此类
网络,简单的平面结构路由算法已经难以适用于这种情况。为
了便于网络管理和降低网络开销,具有相同运动特性的节点一
般按照簇或者组的形式进行聚集,充分发挥簇头节点在网络资
源方面的优势,实现网络性能指标的提升。
目前,分簇 /分组 DTN路由技术主要包括基于网络稳定性
的分簇算法
[10]
、基于相遇概率的分簇算法
[11,12]
、基于节点运
动特性的分簇算法
[13]
、基于摆渡的分簇算法
[14]
。另外,在文
献[15]中还提出了在缺乏基础设施的紧急通信环境中将数据
层和控制层独立设计的混合分簇网络结构 EDTN。
本文通过研究现有 Adhoc和 DTN分簇算法,提出了一种基
于动态分簇的 DTN路由算法(dynamicclusterbasedroutingalgo
rithm,DCBRA),综合考虑节点能量剩余率、中心度、通信范围等
节点性能选举簇头节点,按照节点关联度和稳定度作为普通节
第 32卷第 11期
2015年 11月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol32No11
Nov.2015