战场环境下基于节点移动性的DTN路由算法*

和 何，李琳琳，路云飞

（火箭军工程大学，西安 710025）

0 引言

容迟容断网络（DTN）是一种典型的在任意时刻任意两个网络节点间缺乏可靠路径的特殊网络。不同于传统通信网络，DTN使用存储-携带-转发机制[1]，能够有效地解决网络拓扑结构动态变化、通信链路经常中断、间歇性连接、传送延迟长、资源有限等问题[2]。因此，近年来针对DTN的路由算法已经成为研究网络通信的一大热点。

在DTN中有3种经典的路由算法：Epidemic[3]、Spray and Wait[4]、PROPHET[5]。在此基础上，近年来出现了很多新的路由算法，如：文献[6]通过将节点接触信息和消息特性相结合，提出了基于路由协议的期望相遇算法，利用同一个社区内节点间高接触频率提出了社区意识路由算法，仿真结果表明，两种路由算法相比于3种经典路由算法，其消息投递率、平均时延和有效吞吐量得到了较大提升。文献[7]中提出了基于用户中心性和兴趣度的路由算法，同时多跳中心性概念的提出使得中继节点有更多的机会传送消息，因此，有效地提高了路由算法的消息投递率。文献[8]提出了交际度的概念，即为节点经常相遇的其他节点的总量。节点交际度越大，说明该节点有更高的可能性传送消息到其他节点，因此，路由策略即为选择交际度最大的节点作为中继节点。近年来对于DTN的其他研究进展还包括调度车载式 DTN[9]，多播路由方案[10]，ad-hoc网络的绿色技术假设[11]等。

1 基于节点移动性的路由算法

一个作战单元在遂行作战任务时，所面临的情况是稍纵即逝、难以预知的，加之通信资源稀缺，作战节点之间很难做到实时通信，即不存在稳定可靠的端到端通信链路，即认为在某些战场环境下通信网络属于DTN网络[12]。

战场环境下节点类型主要包括：武器平台、各级指挥所、作战单兵、通信节点、便携式移动终端等。基于节点的运动水平指数和历史接触信息，把消息传送给在每个作战单元内具有最大运动水平指数的节点，其次通过这些节点进行作战单元间以及作战单元与上级指挥所间的通信。

MRA算法的主要创新点体现在如下2个方面：1）综合了Binary Spray and Wait和PROPHET算法，分类讨论了单副本传送和多副本传送问题，对单副本传送综合考虑运动水平指数和历史接触信息，对多副本传送仅考虑运动水平指数，解决了Binary Spray and Wait算法在喷洒阶段由于泛洪导致网络负载增大和在等待阶段使用被动的直接投递算法导致消息投递率下降的问题；2）解决了战场环境下，由于高网络负载和低消息投递率所带来的信道拥塞、单点失效和贻误战机等问题。

1.1 节点运动水平指数的量化

在本文中，节点运动水平指数MWM（Mean Weighted Moving）如式（1）所示：

其中的v0、vt、…、vn-1为某个样本节点在10 min内按时间由近及远随机抽取n个时刻的瞬时速度。

采样步长取10 min的主要原因为：仿真过程表明，当采样步长大于10 min时，采样精度不够；而取采样步长小于10 min时，又会出现采样节点运动状态没有发生变化，而增加了网络负载率的问题。从实际战场环境分析，如果一个作战节点超过10 min对呼叫方没有应答，则认为该节点丧失通信能力，不可以作为中继节点进行选择。

按照时间局部性原则，距离当前时刻越近的移动节点的速度应越契合当前时刻的移动节点的速度，所以v0被赋予的权值最大，为n；vn-1被赋予的权值最小，为1。n既是某个样本节点被随机抽取的总个数，同时也是瞬时速度的权值。在本文中，设定n=10。

本文中设置为每隔2 h采样一次，即采样周期为2 h。主要原因为：战场环境的总体局势不会因为某个节点运动状态的变化而发生重大转变，只有当可观数目的战场节点同时发生变化，战场总体态势才会发生变化，仿真实验表明，2 h以内节点的总体运动态势比较平稳，因此，把采样周期设定为2 h，这便于保证上级指挥所实时掌握战场全局态势的同时，也不会因为频繁采样的原因而增大战场网络资源的开销。

MWM值每2 h更新一次，通过式（1）分别计算出不同时段的节点运动水平指数。每个节点的运动水平指数分为如下3种：1）MWM≤3时，第1种：移动水平最弱的节点；2）3＜MWM≤10时，第2种：移动水平适中的节点；3）MWM＞10时，第3种：移动水平最强的节点。MWM的单位为m/s。

1.2 路由算法

MRA算法综合考虑节点移动性的运动水平指数（MWM）和历史接触信息完成消息传送。当两个节点相遇时，要进行消息传送的节点检查自身携带的消息副本数是否大于1。MRA算法步骤如下。

步骤1消息副本数大于1。1）要进行消息传送的节点A的MWM属于第1种类别且它所相遇节点B的MWM高于第1种类别；2）节点A的MWM不属于第1种类别且它所相遇节点B的MWM高于或等于节点A的MWM。则A传送1/2（如果不能被2整除，则向下取整）的消息副本数至B，否则不予传送。中继节点B大于1个时，选取MWM最大的节点。

步骤2消息副本数等于1。检验到此消息副本在之前的步骤中被传送过，则无需任何操作。

步骤3消息副本数等于1。检验到此消息副本在之前的步骤中没有被传送过，此时除了节点的MWM，节点的历史接触信息也要考虑进消息副本的传送过程当中，即：每个节点都要保存在过去某段时间内该节点的相遇信息，超出算法规定时窗时，相遇节点从某节点的历史接触信息中自动丢弃。基于此，选出曾经与目的节点相遇的中继节点。根据局部性访问原理，过去的时窗范围内与目的节点有过相遇的中继节点，更有可能在未来与目的节点发生相遇。基于此作如下讨论：1）如果要进行消息传送的节点A的MWM属于第1种类别，且它所相遇节点B的MWM高于第1种类别，且B节点在所规定的时窗内曾与目的节点相遇；2）节点A的MWM不属于第1种类别，且它所相遇的B节点在所规定的时窗内曾与目的节点相遇。则A将该消息传送给B。中继节点B大于1个时，针对1）选取MWM最大的节点，如MWM相同，则选取最小时窗的节点；针对2）选取最小时窗的节点。

MRA的具体步骤如下所示。

2 仿真分析

本文运用离散时间模拟器ONE对MRA算法进行仿真，比较分析了MRA算法与Epidemic、Spray and Wait和PROPHET 3种DTN经典路由算法在消息投递率、网络负载率、平均时延等方面的仿真结果。

2.1 仿真环境的运动模型

假设作战单元在遂行作战任务时，各作战节点依据各自目标，可随时调整运动路线，具有自主机动性。为了更贴合战场环境的实际，选用随机路点移动模型（Random Waypoint Mobility Model，RWP）。

2.2 仿真参数

表1 仿真参数设置

表1为本实验的具体参数设置。仿真过程中各类作战节点数固定为50个，150个节点随机分布在10 000 m×8 000 m的场地中；第1类节点、第2类节点、第3类节点的移动速度分别设置为1 m/s、3 m/s、10 m/s；节点生存时间 TTL（Time To Live）为24 h；每类节点都配备有蓝牙广播界面，通信范围为：10 m、20 m、100 m。

2.3 仿真结果

如图1所示，所有算法的消息投递率都随着仿真时间的增加而得到提升，在经过4天的仿真后，所有算法的消息投递率都到达一个最大值。Epidemic算法消息投递率最低的主要原因是：Epidemic算法的核心是把消息复制并传送到本身遇到的每一个节点，导致节点缓冲区的容量严重不足，发生“溢出”的现象，于是新到来的消息不能及时得到传送；MRA算法和PROPHET算法则都因没有使用Epidemic的洪泛机制，因此，与Epidemic相比，两者具有较高的消息投递率；而Spray and Wait算法的Spray阶段与Epidemic算法的原理一样，是多副本拷贝路由，而Wait阶段则是单副本路由，所以Spray and Wait算法的消息投递率低于MRA算法和PROPHET算法，高于Epidemic算法。通过图1可以发现，MRA算法和PROPHET算法经过4 d的仿真后消息投递率均超过了80%。

图1 消息投递率

图2 网络负载率

如图2所示，PROPHET算法的消息副本数的上限只与DP（Delivery Predictability）值有关：节点只要遇到比自身DP值大的邻居节点，就进行传送。因此，与Epidemic算法一样，大量冗余的消息副本将产生拥塞问题，增大网络负载率，所以Epidemic算法和PROPHET算法的网络负载率都较大，约为MRA算法和Spray and Wait算法的100倍。而MRA算法取得了最优的结果，其主要原因是：MRA算法通过运动水平指数（MWM）和历史接触信息对图2网络负载率传送的消息副本数进行有效控制，在仿真过程中，Spray and Wait中每个消息的副本数控制为32个；而MRA算法中第1类节点的副本数为16个，第2类节点为8个，第3类为1个。因此，MRA算法的网络负载率比Spray and Wait还低。

图3 平均时延

如图3所示，Epidemic算法在平均时延中的仿真结果是最理想的，主要原因是：Epidemic算法对每一个消息都进行快速复制并传送，导致在路由环境中每一个消息都存在大量副本，便于迅速传送到目的节点。PROPHET算法的平均时延结果比Epidemic算法高，但均低于Spray and Wait和MRA算法。Spray and Wait和MRA算法平均时延较高的主要原因在于网络传送过程中对消息副本数的控制，其中MRA主要是通过运动水平指数（MWM）和历史接触信息控制消息副本数，使消息副本数远小于Epidemic中的副本数，因此，该消息被传送到目的节点的机会随之减少，延长了从源节点到目的节点所消耗的时间。

3 结论

本文通过节点运动水平指数和历史接触信息，对消息副本传送进行了有效控制。MRA算法的核心在于：依据节点运动水平指数（MWM）进行分类，使消息副本传送到具有更高MWM的节点。该算法需要考虑的另一大因素是节点的历史接触信息，当进行单副本传送时，中继节点的选取除了MWM之外还需考虑时窗内与目的节点的历史接触信息。

仿真结果表明，MRA算法与 Epidemic、Spray and Wait、PROPHET算法相比，首先具有最低的网络负载率，有效地控制了网络拥塞，使得消息在生存时间TTL内能得到及时传送，避免了消息失效，而在战场环境下，消息的实时投递是非常重要的；其次具有较高的消息投递率，战场环境下保证消息从上级指挥所到下级作战平台的成功投递率也是要重点考虑的因素之一。虽然MRA算法增大了一定的平均时延，但一般情况下，在战场环境下降低决策等级较高节点的网络负载率和提高消息投递率的意义高于降低平均时延。

下一步的研究工作主要是：1）针对多节点选择同一高运动水平指数节点作为中继节点时导致的网络拥塞问题，主要研究高运动水平指数节点的布设方法。2）针对MRA算法中存在的较高平均时延问题，开展优化编码调制方法研究。