移动机会网络路由算法应用研究

李志勇

(大众报业集团 信息技术部, 山东 济南 250014)

0 引言

作为一种新型的自组织网络，移动机会网络的通信过程在端到端间实现，对于网络传输中的延迟具有一定的容忍度，不同于传统的自组织网络(基于TCP/IP协议)，机会网络的网络通信基于“存储-携带-转发”机制实现，移动机会网络消息的传输主要通过规律或随机移动的节点所产生的相遇机会实现，无需搭建和维护从源节点到目的节点的完整路径。受到自身特殊性的影响，机会网络的节点经常处于资源严重受限的状态，导致其存在拓扑割裂频繁、传输时延较高等不足。但在包括海洋探测、野生动物追踪、军事等在内的部分极端应用环境中，通过合理部署移动机会网络可得到较佳的效果，由于其网络节点的带宽和存储能力较低，如何实现消息的合理路由转发以及避免消息泛滥成为机会网络的一项研究重点。

1 设计原理

移动机会网络具有资源有限、拓扑变化、节点移动频繁、链路间歇性连接、时延高、安全性不足等特点，不同于传统网络，移动机会网络中的节点传递消息时不建立完整的传输路径，产生消息后的节点继续移动，遇到其他子区域的节点后，在各自的通信范围内完成数据的交换，或向移动时遇到的节点传递消息，再经过多跳传输后完成到目的节点的消息转发过程，即移动机会网络采用存储-携带-转发方式通过节点的移动与接触完成数据传输。相继被提出的多备份路由协议以实现提高移动机会网络的数据扩散效率为目标，例如，一种改进的移动机会网络数据转发算法；一种突发灾害应急路由算法，主要结合社会活动和物理接触设计；一种移动社交网络的数据转发方案；一种基于历史信息的路由协议；类似传染病扩散的EpidemicRouting算法，在降低传输时延的同时有效提高了数据传输投递率，但存在明显的网络负载大、资源开销大的不足；PeopleRank路由算法，包含少量的能量算法，将物流节点按照其社交性的高低进行排序，再以节点的中心度为依据完成路由决策，Geo-Social进行转发决策，在以位置历史作为社会特征的基础上确定新的地理社会指标，使用效用值高的节点传递消息；针对资源受限的移动机会网络，关于移动网络的能量优化路由算法、低功耗传输策略、最优数据传播问题、能量使用效率问题等方面的研究。移动社会网络在实际通信过程中离不开能量的支持，而各移动设备能量有限，忽略能量因素易导致频繁传输数据的关键节点过早死亡。部分紧急服务场景中的网络节点难以及时补充能量，能量耗尽无法继续工作，进而中断了其他通过该节点的路径，阻碍通信过程的正常进行。在延迟容忍网络中，为保证网络节点的存活率，避免因过度活跃而导致的低能量节点死亡问题，可根据节点的剩余能量，选用能量较高的节点传输数据[1-2]。本文在现有研究成果的基础上，兼顾数据传输性能和较低的能量消耗，设计了一种节点不相交的路由算法，实现对网络节点存活时间的延长，使网络中节点能量消耗更加均衡。

2 路由算法设计分析

2.1 功能分析与设计

在网络中通过洪泛路由算法可实现消息的快速扩散，此时网络中存在较多相同的消息副本，在不限制网络资源和节点能量等时具有最优的数据投递性能。但移动机会网络在间歇性连接的情况下进行数据传输时，通常不存在完整路径，且机会网络中的移动设备能量有限，目前移动网络在军事、野外等较恶劣的现实环景下应用较多，一旦链路中某个设备能量不足且无法进行能量补充时，将阻碍数据传输过程的正常进行。为此本文设计了一种节点不相交路由算法，规定全部中间节点(除源节点外)的数据包转发机会均只有一次，完成一次数据传输后的中间节点不能向其他非目的节点转发数据包，进而使任意两条路径上不会同时出现已转发过数据包的某一中间节点，进而使关键节点因能力不足而过早死亡问题得以有效避免，实现了网络存活时间的有效延长。对应的多径路由的示意图，如图1所示。

图1 节点不相交多径路由

A表示一般节点，S和D分别表示源节点和目的节点，箭头表示数据传输方向，除相交的路径与节点外共有3条源到目的节点的路径。本文路由算法的设计目标为：相比于洪泛路由算法中副本的数量，移动机会网络中单个消息的副本数明显减少并尽可能提高传递率，消息的传递延迟则尽可能相近，最大程度降低节点的能量消耗[3]。

2.2 路由策略

本文路由算法的前提假设为：数据传输不存在信道争用，网络节点位置随时间的推移呈现动态变化，各节点的能量均有限制，通信范围内的任意两节点均具有传输数据的可能。为实现节点不相交，避免同一个节点转发两次数据，将一个初值为False的标志位Forwarded设置于各网络节点中，Forwarded在节点接收并转发数据后置为True，据此完成对节点转发过数据与否的判断。假设，由非源节点i携带消息，i从未复制转发过携带消息时的Forwarded为False，当i在网络中移动遇到j时，若j为目的节点则直接传递消息；在j不是目的节点的情况下，若其含有i携带的消息副本则不转发数据，若不含有i携带的消息副本则i会向j复制转发消息，完成一次数据传输，之后i和j继续移动并按照同样策略进行转发，此时由于i已转发过一次消息其Forwarded变为True，i在接下来的移动中除非遇到目的节点否则不再转发数据，以避免出现路径相交问题。在遇到目的节点时，无论节点的Forwarded是False还是True均需传输数据，以完成通信任务。从而有效避免多条路径出现同一节点的问题，使消息副本数量和能量消耗均得到明显降低。同一种消息各节点仅能转发一次则有效避免了关键节点出现过早死亡问题[4]。

3 模型设计

3.1 马尔可夫链模型的建立

本文设计使用一个“病毒传染”模型表示数据传输过程，源节点、未含消息副本的节点和目的节点分别对应模型中的病毒感染点、易感节点和治疗院，称首次被感染的节点为传染节点，其中，易感节点仅感染一次同一种病毒，每一个接触病毒感染点的易感节点均能被其感染，非目的节点仅能被各传染节点感染一次，感染某一易感节点后的传染节点变为等待治疗院救治的节点(此时不再具备传染的功能)，易感节点可转变为传染和等待救治两种状态，这两种状态下的节点均称为感染节点，节点不相交的目的通过设置仅具备一次传染病毒机会的其他节点(除病毒感染点以外)实现。采用马尔可夫链完成对受感染节点数目变化情况的建模，该节点不相交模型具体基于洪泛建立，易感节点由源病毒点和传染节点感染后转变形成传染节点，由S→A表示，由A→W表示经传染节点转变的等待救治节点，采用3层结构的模型示意图，如图2所示。

图2 洪泛传染病马尔可夫链模型示意图

A对应传染状态，S对应易感状态，W对应等待救治状态，这3种状态中涵盖了所有节点。此外，被感染后的易感节点是转变为传染状态的唯一路径，变为传染状态后的节点才能转变为等待救治状态[5]。

3.2 模型分析

易感节点由病毒感染点与传染节点感染后完成到传染节点的转变，被病毒感染后的传染节点变为等待救治状态，因传染节点的一次数据转发而导致等待救治节点数量增加，传染节点状态对传染节点数量变化不构成影响，网络节点状态数量变化情况如图3所示，圆圈对应具体的时刻，箭头表示数量变化情况，(i，j)对应当前时刻的某一状态，其中i和j分别表示传染节点的数目和等待救治节点的数目，这两个数目的变化情况分别由IA和IW表示，状态(i，j)向(i+1，j)的转变表示保持j不变的同时增加1个传染节点数目，说明此时有一个易感节点被病毒感染点感染了，因此IA++；状态(i，j)向(i，j+1)的转变表示某一被病毒感染后的传染节点变为等待救治的节点，因此IW++，在原感染点不感染其他节点时被感染的节点变为传染节点不会改变i的总数。假设，系统模型中初始时共包含节点N个，其中的病毒感染点(同时作为感染节点)和易感节点分别为1个、S个，无等待救治的节点。N表示节点的总数目，β表示节点的接触率，I表示感染节点数目总和，在t时刻，系统中易受感染的节点数目由S(t)表示、感染节点数目由I(t)表示、传染节点数目由IA(t)表示、等待救治节点数目由IW(t)表示，β(N-1)表示单位时间内各节点接触的节点数，S/(N-1)表示模型中未感染节点的占比。各类感染节点的数量变化，如图3所示。

图3 感染节点数目变化图

采用马尔可夫链(CTMC)模型完成追踪，状态S到IA的转变率为：新增的传染节点数目=βS(即源节点、单位时间接触节点数和未感染节点的比例三者乘积)状态IA到IW的转变率为：新增的等待救治的节点数目=βS(IA- 1)(即传染节点、单位时间接触节点数和未感染节点比例三者乘积)。据此得出节点数量转变的马尔可夫模型[6]，如图4所示。

图4 节点数量变化的马尔可夫链模型

状态S和I中涵盖了整个模型中节点状态，假设各类病毒的传染具有独立性，在初始即t=0时，S=N-1，IA(0)=1，IW(0)=0，节点数目变化的瞬态解如下。

I=IA+IW，两个时间函数IA(t)和IW(t)的表达式[7]如下。

3.3 模型验证

对本文模型系统进行验证和评估，需先完成节点间的接触概率β值的计算，具体通过对每个S与IA、IA与IW感染的时间进行多次模拟和记录实现，例如，记录Δt时间间隔内的状态IA=i→IA=i+1、状态IW=j→IW=j+1，取多次模拟中β的平均值。节点数目在某一时刻Δt内由状态S到A的瞬态解为βS，推出β=1/SΔt；同理推出由状态A到W时的β=1/(S(IA-1)Δt)，取不同状态上β的平均值，据此得到模型的β。通过参数β模拟上述模型，移动机会网络中共包含90个节点，以KAIST中的真实数据集作为节点移动情况，模拟时间为15 000S，受感染节点数变化情况，如图5所示。

模型曲线同理论结果基本吻合，能够实现对受感染节点数变化的准确预测，说明该模型合理有效[7]。

图5 受感染节点数变化拟合曲线

4 仿真实验与结果分析

设计仿真实验对比本文路由算法和其他算法的性能，仿真时间设为15000S，仿真实验采用KAIST的真实数据集，各节点的通信距离最大为250m，设置各节点的初始能量为10000个能量单位，接收或转发数据各需消耗1个，通过使用VisualC++平台完成了5种路由算法的集成，即Epidemic(基于洪泛的路由算法)、PageRank、PageRankEpidemicDisjointPath(基于中心度节点不相交的算法)、EpidemicDisjointPath(基于洪泛路径不相交的路由算法)和Geosocial，已有文献详细介绍了该移动机会网络模拟器平台[8]。实验初始时，从KAIST中随机选出1 000对源-目的节点对，根据不同指标性能对比分析路由算法的性能，5种算法的投递率的仿真结果，如图6所示。

图6 投递率

EpidemicDisjointPath路由算法的投递率仅次于最高的Epidemic路由算法，并且在7 500 S后增长缓慢，最早稳定在0．9左右；0-7 000 S时，相比于PageRank和Geosocial，PageRankEpidemicDisjointPath算法的投递率更高，7 000 S后逐渐趋近于PageRank并小于Geosocial算法。总能量消耗仿真结果，如图7所示。

图7 总能量消耗

5种路由算法的能量消耗均随时间的延长而增加，PageRank能量消耗最低，洪泛所达到的最高投递率通过不计代价完成数据传输实现，因此会消耗掉大量的能量，其能量消耗快速达到巅峰，继续传输剩余少量未投递消息时能量消耗增长缓慢；EpidemicDisjointPath算法的能量消耗曲线变化趋势同Epidemic基本相同，但消耗明显小于Epidemic算法，能量消耗控制效果较佳；相比于Geosocial，PageRankEpidemicDisjointPath的能量消耗更少，并随时间推移逐渐趋近于PageRank。说明通过节点不相交的方式的使用实现了对能量消耗的有效控制。平均投递延时仿真结果，如图8所示。

图8 平均投递延时

投递延时随时间推移而增大，Epidemic的投递延时最小，PageRankEpidemicDisjointPath的投递延时略大于Epidemic，EpidemicDisjointPath的投递延时在7 500 S后开始放缓增长，最终低于Geosocial。平均网络开销(即消息在网络中平均的副本数)的仿真对比结果，如图9所示。

图9 平均网络开销

Epidemic的数据传输通过相遇的各节点进行，导致存在大量的消息副本，其网络开销在初始时急剧增长(所有网络开销几乎均在此时产生)且已经含有大量副本，此时其投递率已趋于1，仅剩余少量的未投递消息，随后只产生少量副本；EpidemicDisjointPath的各节点仅转发一次消息，明显较少了网络中的消息副本数量；其他3种算法的网络开销均明显小于Epidemic，PageRankEpidemicDisjointPath的网络开销在15000S时几乎与PageRank重合，预计随后会小于PageRank。仿真实验验证了基于路径不相交的路由算法的有效性，在较高投递率下可实现对能量消耗的有效控制，其节点能量消耗的均衡性较好，可避免链路中断的出现。

5 总结

目前多副本路由协议成为提升网络中数据传输速度的有效手段，但由于缺少对能量问题的考虑，而易导致消耗能量较多时出现设备停止工作的状况。考虑到移动机会网络中没有完整的传输路线且网络节点的能量有限，为有效解决其中的数据传递能量消耗问题，本文设计了一种多路径解决方案及路由算法，分析节点状态间的变换，详细介绍了节点不相交路由策略，利用二维连续时间马尔可夫链完成了系统模型的构建，并给出问题的求解方法，最后通过仿真实验对比分析了本文算法和其他路由算法的相关性能，结果表明本文方案具有一定的研究价值，为进一步优化和完善移动机会网络提供参考。