战场环境下的DTN 路由算法研究

谢凌杰，韩学东

（中国航天科工集团第二研究院706所，北京100854）

0 引 言

容迟容断网络 （delay and disruption tolerant networks，DTN）是一种适应较高延时、频繁中断、异构互联、端到端连接不能保证的新型网络体系［1］，作为MANET 和WSN的发展，在未来战场中应用将十分广泛。

选路协议的设计是当前DTN 研究的一个重难点问题，传统有线网络和Ad Hoc网络选路协议不能有效地应用于DTN，因此有必要结合不同应用场景提出相应的选路协议。DTN 最初于2003年在SIGCOMM 国际会议上提出，用于深空通信，后来很快推广到游牧计算、车载网络、战场通信、野生动物保护和紧急救灾等领域。不同的领域和场景都有各自的特点和需求，目前针对战场通信，尤其是战场上VANET 通信的DTN路由算法较少，战场上通信节点分布相对稀疏，信息量大且优先级不同，本文将据此展开研究。

1 相关工作

由于DTN 中连接是间断的，因此一般采用存储－携带－转发的方式传递消息。传统的DTN 路由算法，如基于洪泛的Epidemic算法和Spray－and－Wait算法，基于转发的First Contact、Earlist Delivery 算 法，基 于 概 率 的MaxProp 和PRoPHET 算法，主要考虑依靠节点自身随机或有目的的移动，但由于DTN 中节点的存储空间、处理能力和能量都受限，很难保证网络质量，尤其是当网络规模较大或分布较稀疏时。于是，出现了面向主动移动模型的路由算法，包括W.Zhao和M.Ammar提出的消息摆渡 （message ferry，MF）策略和R.Shah等人提出的数据骡子 （data mule）策略。由于Data Mule的移动是随机的，难以保证效率，且考虑到战场中不同作战组内部相对集中，相互之间较为分散的情况，本文采用无人机作为Message Ferry。采用Fer－ry节点可以从以下几方面提高网络性能：首先，使用Ferry节点可以满足端到端的传输，提高网络QoS。其次，Ferry节点可以致力于消息转发任务，普通节点就不用考虑路由转发问题，从而节约能量。最后，使用Ferry节点可以大大增加网络的灵活性的鲁棒性［2］。

1.1 消息摆渡算法

自从消息摆渡算法被提出后，学术界已经产生了多种基于此的路由模型。文献 ［3］提出了NIMF／FIMF两种单Ferry路由算法，但是它们都不能很好地满足网络吞吐量和网络规模的扩展，于是出现了多Ferry路由算法。消息摆渡路由算法研究主要集中于Ferry节点的选取和Ferry的移动策略两个重点。本文针对战场设计，而战场上的各节点一般按照各作战小分队部署并有组织的移动，故不考虑节点的区域划分及其Ferry节点的选取，假设每个作战小分队为一自治区域，配备有满足需要的无人机作为Ferry节点，重点考虑Ferry的移动策略。文献 ［4］提出了Ferry节点移动空间自定位路由算法 （MSSL），能较好的兼顾信息传输率、公平性和路径节点效率，但其基于概率的决策不能充分发挥卫星定位系统的优势；文献 ［5］仅考虑了固定路径的情况；文献 ［6］提出了多约束目标的选择算法MCTSA，但单路由模式大大地增加了整体的传输延时。文献 ［7］提出了椭圆区域转发 （EZF）算法，结合了区分服务策略和摆渡节点，对本文工作有一定的指导意义。

1.2 区分服务的路由算法

战场中的信息种类繁多，如作战指令、作战情报、战场环境收集等，它们的重要性和对实时性的要求不尽相同。因此，必须对他们实行有区别的服务。现有的DTN 路由算法中，基于优先级区分服务的有以下几种。文献 ［8］把消息最大拷贝数表示为消息初始优先级函数，高优先级消息复制更多的副本，而基于复制的策略仅适用于小型网络。文献 ［9］提出为高优先级消息预留缓存空间，适用于节点缓存空间较小的场景，且会严重影响低优先级数据的传输。文献 ［10］提出在网络出现拥塞时，优先丢弃低优先级数据包以保证高优先级数据包的顺利转发，并没有考虑网络未发生拥塞时服务的区分问题。文献 ［11］结合传染路由的优缺点，提出了MQAE算法，根据信息的优先级，分队列存储管理并利用效用函数在队列内排序，整体上提高了网络的利用率并降低了时延，但数据并没有根据优先级的不同而进行服务区分。文献 ［12］提出的SDRP 算法重点考虑的是提高投递率，而本文重点考虑根据优先级不同决定传输路线，将最重要的信息尽快送达，尽可能满足战场中准实时的要求。

由DTNRG （DTN research group）提出的DTN 体系结构中，bundle层的进程控制标识比特层通过第7 和第8两个字节定义了数据的优先级，每个bundle的优先级共分为3个等级：00 （低优先级），01 （中优先级），10 （高优先级）。本文的工作也是基于此定义实现区别优先级的投递策略，关于如何确定每个bundle的优先级不在本文的讨论范围之内。

2 B－DTN 设计

2.1 概述

现有的研究普遍没有专门针对战场情况而设计，具体表现在：①没有实际考虑对战场情报信息的分级，进而保证高优先级消息的投递；②没有充分利用其它可以利用的条件，包括卫星定位系统、无人机等；③在建模及仿真中没有考虑真实战场上部队的分布，只是笼统地将所有部队视为全部随机移动的节点，即使考虑了分簇也是根据节点数量强行划分，这些算法并非针对战场环境，从而忽略了真实情况下不同作战小分队的存在。

在所有的MF路由算法中，节点分为普通节点和Ferry节点。所有节点的移动可根据其目的分为两类：

（1）面向任务的移动：普通节点或者Ferry节点的移动是由各自的任务决定的。例如，一辆公交车作为Ferry节点传递消息，其移动轨迹是由既定线路确定的。

（2）面向消息的移动：普通节点或者Ferry节点的移动是为了更好的传输消息而决定的。

本文结合战场实际情况，假定在每个作战小分队中的作战车辆，移动传感器和手持终端的移动是面向任务的，而各作战小分队中的信息发射车和作为Ferry节点的无人机的移动为面向消息的。每个自治区域中的消息传递采用Epidemic算法，作为Ferry接入点的信息发射车在区域内不断移动以收集和传送信息。在本章后续讨论中， “节点”表示Ferry接入点，而非普通节点。

综上所述，本文的设计基于以下场景：在一个较大的战场中，稀疏分布着若干作战小分队，各分队为一自治区域，其内部通信延时较小，不同自治区域间相距较远，通信质量难以保证。各区域内的作战节点进行面向任务的移动，仅通过其接入点与外界进行信息交换。各区域中有一辆信息发射车作为接入点，各接入点和Ferry利用卫星定位系统可以确定相互间的地理位置信息。接入点具有长距离波通信功能，但仅用于对远处的Ferry 提出服务请求，在进行普通数据传输时仍使用短距离波。另外，多Ferry节点路由算法需要考虑每个Ferry 节点的运动问题以及Ferry节点间的交互问题。由于本文考虑的是稀疏环境，暂时不考虑交互，方便集中解决Ferry节点的选路问题。

2.2 EZF算法

每个Ferry维持着两个队列，一个是待投递节点队列D，一个是待收集节点队列C，给予D 队列更高的优先级（因为当某一bundle被Ferry收集后，它的发送者便信任此Ferry并假设bundle能被及时送达；而当某一bundle未被Ferry收集时，发送者会不断发送待收集请求。因此有理由给予已被收集的bundle更高的优先级）。

假设某时刻D 队列中依次有3个目的节点待访问，分别设为Y1，Y2，Y3，Ferry此时在X 点，取X 和Y1为椭圆的两个焦点，以Ferry速度与Y1的剩余延时之积为长轴长度构建一个椭圆，如图1所示。

图1 EZF椭圆

如果椭圆区域内存在待收集节点，记d （I，J）为I和J 之间的距离，验证d （X，Zi）＋d （Zi，Y1）＜d （A，B）是否成立。若成立，则访问Zi；若同时存在多个Zi，选取d （X，Zi）＋d （Zi，Y1）最小的访问；若不存在，则继续访问Y1。

2.3 B－DTN算法

EZF的设计思想是在降低整体延迟的基础上尽力满足高优先级，但它不能完全保证高优先级消息的送达，而且它认为如果节点产生消息的周期是一定的，就不用考虑在每个节点消耗的传输时间。但实际上，不同节点待投递的消息数是不同的，这就导致投递时间不同；而由于等待Ferry的到来，每个节点累积的消息数也是不同的，这也就意味着在每个节点的收集时间也不同。因此在选点计算时，应加以考虑。再对算法的具体步骤进行分析发现，在原文献陈述的EZF算法中，若同时存在多个Zi，当Ferry选取d （X，Zi）＋d （Zi，Y1）最小的Zi访问后，没有说明是直接访问Y1，还是再访问其它Zi。

（1）如果是直接访问Y1，那算法的效果将大打折扣，因为在椭圆内可能分布着很多Zi节点；

（2）如果是再依次访问其它Zi节点，可能会出现 “饥饿”现象，使原本应按时投递给Y1的消息超时，如图2所示。

图2 “饥饿”现象

综上所述，本文提出了B－DTN 路由算法，由基于优先级的多级队列和改进的EZF算法构成。

每个Ferry同EZF 一样维持两个队列，但每个队列中再根据消息优先级划分为多级队列，队列中每个节点还包括其待送达 （待收集）的bundle数Ndi（Nci）。缓存空间在DTN 节点中是宝贵的资源，本文把缓存空间优先分配给高优先级消息，当空间不足时，依次从低、中、高队列的队尾删除消息，如表1所示。

表1 基于优先级的多级队列

在此椭圆内的其它节点，如图3中Z1，Z2，若其优先级与Y1相同，则改变运动路径访问它；若其优先级低于Y1，则仅在经过时与其进行消息传输，而仍沿着Y1继续前进。

图3 改进的EZF椭圆

改进的EZF寻径算法如下：

记d （I，J）为I 和J 之间的距离，Vf表示Ferry的速度，w 为数据传输率，M 为每个bundle的大小，易得对Zi的访问时间为Ti＝M·N／w 。

初始化时将所有要访问的接入点按照优先级排出3个队列，各队列中按照距离由近及远排序。然后执行以下步骤：

步骤1 从当前D 队列最高优先级子队列中选择第一个接入点进行访问，若所有队列为空则返回Ferry 所属区域；

步骤2 构造EZF 椭圆，如果椭圆区域内存在待收集节点，验证d （X，Zi）＋d （Zi，Y1）＋T·Vf＜d （A，B）是否成立。若成立，分以下3种情况：

（1）Zi的优先级高于Y1（只可能是待收集节点），则访问Zi。

（2）Zi的优先级与Y1相同 （只可能是待收集节点），不访问Zi但对Zi进行收集，具体策略为：以Zi为圆心，Zi的传输半径为半径作圆，若存在交点S1和S2，如图2所示，从行进至S1开始进行传输，若到S2尚未完成，则等待至传输完毕再继续行进至Y1；若不存在交点，则不对Zi进行收集。

（3）Zi的优先级低于Y1（可能是待收集节点也可能是待投递节点），策略同 （2），但在S2处若未传输完毕，则终止传输，继续行进至Y1。

步骤3 回到步骤1。

需要说明的是，由于Ferry支持多播，可以同时与多个Ferry节点进行消息传输，对于所有满足步骤2 中 （2）和 （3）的Zi节点，Ferry沿着XY1行进，依次对进入其传输半径的进行消息传输。

3 仿真与评估

3.1 仿真实验概述

仿真的主要目的是考察算法是否适用于战场环境，从而为进一步研究以及真实场景的测试提供参考。针对战场的实际需要，选取投递率和总时延作为衡量指标。采用由赫尔辛基科技大学网络实验开发的基于代理的离散事件模拟器ONE （opportunity networking environment）进 行 仿真，它支持DTN 协议，集运动模型、路由仿真以及可视化和报告于一体。

3.2 仿真环境

300个普通节点中，高、中、低优先级各100 个，其TTL对应为10min，30min，60min。各区域内部使用Epidemic路由算法。仿真时间为6h，所有结果均是10次仿真的平均值，默认仿真参数见表2。

表2 默认仿真参数

3.3 仿真结果及分析

（1）不同优先级的投递情况

本算法的核心思想是保证高优先级的信息优先送达，故首先应该分析得出不同优先级的信息随时间的送达情况分布。实际中不同优先级的信息TTL 设置也不同，因此本文设定：TTL高＝10min，TTL中＝30min，TTL低＝60min。

由图4、图5可以看出，EZF算法虽然尽力满足高优先级，但是对于设定的默认TTL，高优先级消息的投递率仍远远低于较低优先级消息。相比之下，B－DTN 能保证高优先级的消息的投递率。在相同的场景下，使用EZF 算法，低优先级的消息投递率能达到接近0.9，而高优先级的消息投递率仅有0.5左右。而B－DTN 算法可使高优先级的消息投递率达到0.8左右。

虽然EZF算法考虑了不同优先级，但该算法是在减少全局延时的思想下兼顾优先级。实际应用中，不同优先级的消息TTL是不同的，由于高优先级的TTL 较短，若椭圆区域中存在较多低级别的消息，高优先级消息很容易因超时被丢弃，因此投递率低于较低级别消息，由此可见其不能保证高优先级消息的投递率。而B－DTN 算法重点照顾了高优先级消息，可以有效避免 “饥饿”现象。

图6显示了不同传输半径对投递率的影响，可以看出，不同的传输半径对高优先级消息的影响很小，对中、低优先级影响较大。随着半径不断扩大，中、低优先级的投递率明显改善，达到250米之后增势趋于稳定。

（2）网络时延的比较

图6 传输半径对投递率的影响

由图7可以看出Epidemic算法在稀疏环境下的时延很大，而且波动很大。加入了Message Ferry后的MFS算法在一定程度上减少了传输时延，而且性能相对稳定。EZF算法和B－DTN 算法的平均延时优于传统算法，而虽然有优先满足高优先级消息这一条件，B－DTN 的延时也只是略高于EZF，约为8%～15%。

之所以B－DTN 算法的延时会略高于EZF 算法，是因为我们为了保证较高优先级的消息的及时投递，必然要在一定程度上影响原EZF算法对全局延时的缩减。

图7 与现有算法的平均时延比较

图8表明Ferry数量是影响B－DTN 算法性能的一个重要因素，在Ferry数量不足时，平均时延最高可达到9000秒；当Ferry数目达到30之后，逐渐接近饱和，延时低于2000秒。此外可以看出，随着Ferry的增加，延时趋于稳定，说明主要延时是飞行寻路延时，由于报文较小，传输时延对整体时延的影响较低。

4 结束语

本文结合战场实际情况，提出了B－DTN 路由算法。利用卫星定位系统和无人机作为消息摆渡，提升了稀疏环境DTN 的性能和扩展性。同时，为了尽可能满足战场准实时的要求，提出了基于优先级的多级队列，并改进了EZF 选路算法。通过仿真验证了B－DTN 算法的有效性，算法保证了高优先级消息优先送达，整体传输时延和投递率相对于传统路由算法也有较大改善。下一步将研究Ferry节点间的通信问题，bundle包的优先级确定策略，拥塞控制和安全机制等。

图8 不同Ferry节点数的平均时延对比

［1］DING Baoping，CHEN Ming，LIU Xinyu，et al.Design and realization of an experiment platform of delay／disruption tolerant network ［J］.Journal of Military Communications Technology，2011，32 （2）：83－86 （in Chinese）.［丁宝平，陈鸣，刘新宇，等.一种容迟／容断网络试验平台的设计与实现 ［J］.军事通信技术，2011，32 （2）：83－86.］

［2］WANG Lei.Research on multiple ferries routing in DTN ［D］.Nanjing：Nanjing University of Post and Telecommunication，2010 （in Chinese）.［王磊.延迟容忍网络多Ferry路由算法研究 ［D］.南京：南京邮电大学，2010.］

［3］Christopher A Rapin.Message prioritization for routing in a DTN environment［D］.Naval Postgraduate School，2011.

［4］ZHANG Yun，WEI Peng，WANG Ruchuan，et al.Research on Ferry node MSSL routing algorithms in DTN ［J］.Computer Technology and Development，2009，19 （5）：107－110 （in Chinese）.［章韵，魏鹏，王汝传，等.DTN 网络中Ferry节点的MSSL路由算法研究 ［J］.计算机技术与发展，2009，19（5）：107－110.］

［5］ZHAO Guangsong，CHEN Ming.Forward tendency based fixed path Ferry routing algorithm ［J］.Journal of Beijing University of Posts and Telecom，2012，35 （2）：41－45 （in Chinese）.［赵广松，陈鸣.基于转发倾向度的固定路径摆渡路由算法 ［J］.北京邮电大学学报，2012，35 （2）：41－45.］

［6］HU Wei.MCTSA：Research on key issues of message Ferrybased routing in DTN ［J］.Computer Knowledge and Technology，2010，6 （34）：9741－9743 （in Chinese）. ［胡伟.MCTSA：一种DTN 网络中Ferry多约束目标选择算法 ［J］.电脑知识与技术，2010，6 （34）：9741－9743.］

［7］Mooi Choo Chuah，Peng Yang.A message ferrying scheme with differentiated services ［C］／／Military Communications Conference，2005：1521－1527.

［8］SU Huiwei，SUN Lin，Ou Yufeng.Service－aware adaptive message forwarding routing algorithm in DTN ［J］.Computer Engineering and Design，2010，31 （17）：3816－3819 （in Chinese）.［苏会卫，孙琳，欧瑜枫.DTN 中服务感知的自适应消息转发路由算法 ［J］.计算机工程与设计，2010，31 （17）：3816－3819.］

［9］XU Changbiao，WANG Yu，QI Yan.Congestion control mechanism of Push－Pull based on service level in DTN ［J］.Application Research of Computers，2010，27 （10）：3929－3931 （in Chinese）.［徐昌彪，王宇，祁彦.DTN 中基于服务等级的Push－Pull拥塞控制研究 ［J］.计算机应用研究，2010，27 （10）：3929－3931.］

［10］WANG Guizhu，XU Zhenghuan，LI Xiaofeng.Congestion control strategy based on quality of message in DTN ［J］.Computer Engineering and Applications，2012，48 （9）：74－77 （in Chinese）. ［王贵竹，徐正欢，李晓峰.DTN 中依据报文质量的拥塞控制策略 ［J］.计算机工程与应用，2012，48 （9）：74－77.］

［11］GUO Hang，WANG Xingwei，HUANG Min，et al.Adaptive epidemic routing algorithm based on multi queue in DTN［J］.Journal of Chinese Computer Systems，2012，33 （4）：829－832 （in Chinese）. ［郭航，王兴伟，黄敏，等.基于多队列自适应的DTN 传染路由算法 ［J］.小型微型计算机系统，2012，33 （4）：829－832.］

［12］SHEN Jian，XIA Jingbo，FU Kai，et al.A service distinguished DTN probabilistic routing algorithm ［J］.Application Research of Computers，2013，30 （6）：1772－1774 （in Chinese）.［申健，夏靖波，付凯，等.一种区分服务的DTN 概率路 由 算 法 ［J］.计 算 机 应 用 研 究，2013，30 （6）：1772－1774.］