一种间歇性连接移动网络自适应路由协议*

蒋庆丰，门朝光，田泽宇,马英瑞

(1.哈尔滨工程大学计算机科学与技术学院,黑龙江 哈尔滨 150001；2.常熟理工学院计算机科学与工程学院，江苏 常熟 225500;3.大庆师范学院计算机科学与信息技术学院,黑龙江 大庆 163712)

1 引言

移动自组网MANET(Mobile Ad hoc NETwork)是一种由移动节点构成的非中心化、多跳无线网络。按需距离矢量路由AODV(Ad hoc On-demand Distance Vector Routing)[1]、目的节点序列距离矢量路由DSDV(Destination-Sequenced Distance-Vector Routing)[2]和最优链路状态路由OLSR(Optimized Link State Routing)[3]等MANET路由协议能够在网络连通时有效传递数据，但当无线网络由于节点移动、环境恶劣或者遭受攻击造成中断、间歇性连接时，上述常规路由协议将无法成功发送数据。延迟容忍网络DTN(Delay Tolerant Network)是一种具有长时延、链路经常中断特点的网络，在环境监测、军事战略、深空探测等方面具有广泛的应用前景和实用价值[4]。因为DTN中节点间不存在完全路径，所以节点需通过“存储-携带-转发”方式来传递数据，即一个节点临时存储消息直到遇到一个和目的节点相遇概率更大的节点，然后将消息发送给此中继节点，由中继节点将消息发送给目的节点。

针对MANET和DTN的特点，相关文献设计了一些MANET和DTN混合路由协议，以在网络连通和中断情况下有效传递数据。文献[5]针对MANET和DTN混合网，实现了一种简单的混合路由协议延迟容忍动态自组按需路由DT-DYMO(Delay-Tolerant DYnamic MANET On-demand routing)。该协议首先基于AODV的RREQ消息查找连通区域内的目的节点，若找到直接使用AODV发送消息；否则将消息发送给RREQ查找过程中发现的DTN节点，由该节点“存储-携带-转发”消息。文献[6]针对车载自组网VANET (Vehicular Ad hoc NETworks),同样设计了一种结合AODV协议和DTN的“存储-携带-转发”机制的按需路由协议DT-AODV,来提高数据传递率。文献[7]提出了一种基于分组的混合容迟自组网路由协议HYMAD(HYbrid DTN-MANET routing)，该路由协议将移动节点分成多个组，在组内使用MANET中的距离矢量路由发送消息，在组间则采用DTN的Spray-and-Wait路由。针对间歇性连接的移动网络环境，文献[8]提出一种新的增强基础设施DTN路由协议IEDR(Infrastructure Enhanced DTN Routing)。IEDR在网络中断时利用节点间相遇的机会交换数据，并将无线接入点AP (Access Point)作为辅助数据传播的有效途径，扩大网络连通范围。文献[5-8]中每个节点只能获得其所在连通网络中部分节点的传递信息，当和目的节点之间的网络中断时，将无法选择传递效率最大的下一跳中继节点来传递消息，从而影响消息的传递效率。文献[9]为在间歇性连接的移动网络中有效传递数据，提出一种上下文感知的自适应单播路由协议CAR(Context-aware Adaptive Routing)。CAR协议在网络连通时通过DSDV协议转发消息，在网络中断时通过卡尔曼滤波技术和多属性决策理论来选择下一跳中继节点。DSDV适应于规模较小、速度变化慢的网络环境，当网络规模增大和节点移动速度增大时，CAR的性能会下降。文献[10]提出结合OLSR协议和DTN的DTS-OLSR协议，该协议利用部分具有OLSR和DTN功能的节点形成重叠网络，重叠网络中的节点在网络中断时会临时存储消息，以防止消息丢失。该协议中只有部分节点具有DTN功能，会影响路由效率，而本文中所有节点都进行DTN转发。文献[11]提出一种结合OLSR和DTN的有效混合路由协议OLSR-OPP(OLSR-OPPortunistic)，OLSR-OPP针对的是多副本路由，不同于本文研究的单副本路由。

本文针对间歇性连接移动网络提出一种基于OLSR协议的自适应路由协议ARPBO(Adaptive Routing Protocol Based on OLSR)。OLSR是一种先验式路由协议，每个节点可以获得连通网络的全网拓扑结构，并计算各自的路由表。该协议采用多点中继MPR(MultiPoint Relay)的思想，减少了网络中广播分组的数量，适用于节点分布密集、网络规模大的网络。ARPBO协议为一种单副本路由协议，能够在网络连通时利用OLSR协议快速转发消息，在网络中断时通过扩展OLSR协议，获得消息发送节点的局部连通网络中传递效率最大的下一跳中继节点，能够在高移动的密集网络中有效传递数据。

2 路由协议概述

ARPBO路由协议运行过程如下：

(1) 节点间通过消息交换生成路由表。

(2) 节点发送一个消息时，如果路由表中有到达目的节点的直接路由，则发送消息。

(3) 如果没有，表明网络中断，则根据路由表选择连通网络中传递效率(概率)最大的中继节点。

(4) 如果选择的中继节点传递效率大于自身，则节点通过连通网络将消息发送给中继节点，由中继节点“存储-携带-转发”消息。当中继节点和目的节点连通时，将消息发送给目的节点。

(5) 如果中继节点传递效率小于自身，则将消息临时存储在自身缓存中，直到遇到传递效率大的节点或者目的节点。

具体流程如图1所示。

Figure 1 Flow chart of ARPBO routing protocol图1 ARPBO路由协议流程图

假设节点A向H发送消息，如图2所示，图中UIJ表示节点I和J间的传递效率，由于没有到达目的节点H的直接路由，则节点A将消息发送给连通网络中传递效率最大的中继节点E，当节点E和F相遇时，则直接将消息发送给处于同一连通网络的目的节点H。如果F的传递效率小于自身，节点A自身将先存储消息。

Figure 2 Instance of ARPBO routing protocol图2 ARPBO路由协议实例

3 路由协议详细设计

3.1 传递效率计算

同文献[12]一样，假设网络中断时两个节点间相遇时间服从均值为1/λ的指数分布，λ代表两节点的接触率。两节点Ni和Nj的接触率λij的值可通过式(1)进行计算。

(1)

由于节点间相遇时间服从均值为1/λ的指数分布，所以节点Ni和Nj在timeij时间间隔内相遇的概率密度函数如式(2)所示：

f(timeij)=λije-λijtimeij

(2)

假设节点Ni中消息m的目的节点为Nj，剩余生存时间为timeremain，则节点Ni对消息m的传递效率，即和目的节点Nj相遇的概率Pij如式(3)所示：

Pij=P(timeij≤timeremain)=

1-e-λij×timeremain

(3)

消息剩余时间timeremain的值如式(4)所示：

timeremain=TTL+tgen-trec

(4)

其中，TTL(Time to Live)为消息的生存期；tgen和trec分别为消息生成时刻和节点Ni接收消息m的时刻。

ARPBO路由协议中，当节点传输时间有限时会优先发送传递效率大的消息，而当缓存溢出时会首先删除传递效率小的消息。

3.2 路由表生成

ARPBO路由表的生成实现包括Hello消息发送、拓扑生成、路由表计算三个过程。节点首先发送Hello消息，进行邻居感知、MPR节点的选择以及中断时节点间平均相遇时间的统计；然后通过消息广播获得网络中节点的连接信息和相遇信息，从而生成全网络的拓扑模型；最后根据网络拓扑信息生成路由表，在网络连通和中断情况下有效选择下一跳节点传递消息。

3.2.1 Hello消息发送

OLSR协议对标准链路状态路由协议进行了优化，其核心是多点中继技术。多点中继的思想是通过减少同一个区域中相同控制消息的转发次数来达到减少网络中广播分组数量的目的。网络中每个节点选择其邻居节点集合的一个子集(MPR集)来转发该节点的控制消息，这个子集中的节点就是该节点的MPR节点，而该节点就是MPR节点的多点中继选择节点(MPR Selector)。只有被选为MPR的节点才产生并周期性洪泛拓扑控制信息，这样可以显著地减少网络中广播的控制分组数量。

移动节点周期性地发送Hello消息，可以进行邻居感知和MPR节点的选择。每个节点从其一跳邻居中选择自己的MPR集，通过该集合转发的分组能够覆盖该节点所有的二跳邻居节点。节点选择MPR节点后可以在连通网络中有效传递信息。

3.2.2 拓扑生成

节点计算和非连通节点间最近相遇(即两节点连通)时间的平均值，从而根据式(1)计算两节点的接触率，然后生成如表1所示的TC消息并广播给网络中其他节点。

Table 1 TC message

序列号用来判断消息的新旧；MPR Selector为多点中继选择节点地址；最近相遇节点地址存放当前非连接、最近相遇过的节点地址；接触率存放的是当前节点和最近相遇节点的接触率信息。

节点收到TC消息后，根据TC消息来感知全网的拓扑，生成如表2所示的连通拓扑表项和表3所示的中断拓扑表项。

Table 2 Connected topology table item

表2中，序列号用于记录本节点收到的最后一个TC消息的序号，当收到一个新的TC消息时，将新的TC消息的序列号与表项序列号相比较来决定接收还是丢弃该消息；目的节点地址为TC消息中的MPR Selector节点地址；连通的上一跳地址为发送TC消息的源节点地址。

Table 3 Interrupted topology table item

表3中，序列号用于记录本节点收到的最后一个TC消息的序号；目的节点地址为消息源节点最近相遇的节点的地址；中断的上一跳地址为TC消息源节点地址；上一跳接触率为TC消息源节点和目的节点的接触率。

3.2.3 路由表计算

节点发送消息时，需要根据拓扑结构图生成如表4所示的路由表项，从而在网络连通和中断时有效选择下一跳节点。ARPBO路由协议在网络连通时，基于连通拓扑表，根据Dijkstra算法计算出跳数最少的路径及下一跳地址；在网络中断时，根据中断拓扑表选择接触率最大的中继节点，并将接触率填入路由表中。

Table 4 Routing table item

路由表项中存储了网络连通和中断时的下一跳节点地址及接触率信息。其中，第1项为目的节点地址；第2项为网络连通时根据连通拓扑结构图计算出的下一跳地址；第3项为网络连通时消息源节点和目的节点之间的跳数；第4项为网络中断时选择的接触率值最大的下一跳节点地址；第5项为节点间接触率值。

节点在发送消息时，会根据路由表和式(3)计算缓存中每个消息的下一跳节点的传递效率，并对消息进行排序，然后优先发送和存储传递效率大的消息。

4 性能评估

4.1 实验设置

为验证ARPBO路由协议的性能，通过NS3模拟器对其性能进行仿真。同文献[9]一样，默认情况下，仿真区域为1000 m×1000 m，包括50个移动节点。移动模型为根据社会网络理论设计的基于社区的节点移动模型CM(Community Model)[13]，该模型可以很好地代表人类的移动。CM模型中节点被分为5个社区即组，其中每个节点表示人类携带的具有无线通信功能的移动设备，每组节点代表关系较密切的社会团体。仿真时间为2 400 s，共发送1 000个消息，消息大小为1 KB，缓存大小为100 KB，节点无线传输范围为200 m，移动速度为1～6 m/s，TTL为2 000 s。

4.2 性能比较

为验证路由的性能，将ARPBO路由协议与OLSR[3]、DT-DYMO[5]、HYMAD[7]、CAR[9]进行性能对比。使用传递成功率、平均传递时延、负载率3个性能评价指标来对路由性能进行评价。传递成功率为成功传递的消息数与发送消息数比例。平均传递时延是指所有传递成功消息的传递时延的平均值。负载率为消息转发数和成功传递消息数的比值，表示成功传递一个消息需要多少次转发，负载率越大意味着网络能耗越高，资源消耗越大。下面通过改变节点移动速度、节点数目的大小来验证路由性能。

(1)节点移动速度对性能的影响。

节点移动速度对传递成功率的影响如图3所示。可以看出，所有路由协议的消息传递成功率都随着节点移动速度的增大而变小。随着节点移动速度的增大，节点在同一连通网络的概率变小，所以导致传递成功率减小。由于ARPBO路由协议能够利用连通网络拓扑信息，在网络连通和中断时自适应地高效转发消息，所以传递成功率高于其他协议。由于CAR协议在节点移动速度增大时，路由信息失效较快，所以传递成功率在速度较大时低于其他路由协议。由于OLSR协议在网络中断时无法有效选择下一跳节点，所以传递成功率最低。

Figure 3 Impact of varying speeds on delivery success ratio图3 速度对传递成功率的影响

节点移动速度对时延的影响如图4所示。可以看出，所有路由协议的消息传递时延都随着节点移动速度的增大而增大。因为节点移动速度增大时，消息在连通网络中被传递的概率减小，消息需要在网络中断情况下通过“存储-携带-转发”方式转发，导致传递时延增大。OLSR协议传递时延最小，是因为其传递成功率较低，许多长时延的消息没有被成功传递。ARPBO路由协议的传递时延小于DT-DYMO等协议的传递时延。

Figure 4 Impact of varying speeds on delivery delay图4 速度对传递时延的影响

节点移动速度对负载率的影响如图5所示。可以看出，消息负载率随着节点移动速度的增大而减小。因为节点移动速度增大，连通网络中包含的节点减少，成功传递消息的转发次数变少，并且消息在网络中断情况下转发次数也变少，所以负载率变小。由于ARPBO路由协议有效传递消息，所以负载率略高，但获得了较高的传递成功率和较低的传递时延。

Figure 5 Impact of varying speeds on overhead ratio图5 速度对负载率的影响

(2)节点数对性能的影响。

节点数对消息传递成功率的影响如图6所示。可以看出，所有路由协议的消息传递成功率都随着节点数的增大而增长。这是因为节点数越大，网络越密集，节点在同一连通网络的概率增大，并且网络中断时节点相遇的概率也增大，所以传递成功率增大。由于DT-DYMO通过AODV路由协议不能获取连通网络全局拓扑信息，从而不能有效选择传递效率大的中继节点传递消息，导致传递成功率低。HYMAD中组内节点只能够获得组内拓扑信息，而无法获得连通时组外节点的传递效率信息，所以传递成功率不高。由于ARPBO路由协议能够有效利用OLSR协议感知全局网络拓扑来获得节点的传递效率，在网络中断时有效选择下一跳中继节点，并且在网络密集时能够利用MPR机制进行广播消息的优化，所以获得了比CAR高的传递成功率，成功率最高。OLSR协议在网络中断时无法有效传递消息，所以传递成功率最低。

Figure 6 Impact of varying node numbers on delivery success ratio图6 节点数对传递成功率的影响

节点数对时延的影响如图7所示。可以看出，消息传递时延随着节点数的增大而减小。因为节点越多，消息在网络连通和中断情况下被快速转发的机会增大，所以平均传递时延减小。由于ARPBO路由协议能够在网络连通和中断情况下有效转发消息，所以传递时延小于除OLSR以外的其他协议。

Figure 7 Impact of varying node numbers on delivery delay图7 节点数对传递时延的影响

节点数对负载率的影响如图8所示。可以看出，消息负载率随着节点数增大而增大。因为节点增多、网络密集，一些消息能够通过更多的节点转发，从而导致负载率增大。由于ARPBO路由协议能够有效利用局部连通网络中节点间的信息，在网络连通和中断情况下快速转发消息，所以负载率略大。

Figure 8 Impact of varying node numbers on overhead ratio图8 节点数对负载率的影响

5 结束语

为在间歇性连接移动网络中有效传递消息，本文提出一种基于OLSR协议的自适应路由协议ARPBO，并对其性能进行仿真。实验结果表明，ARPBO协议在网络连通时能够利用OLSR协议快速转发消息；在网络中断时能够有效选择传递效率大的下一跳中继节点传递数据。下一步工作将针对间歇性连接移动网络研究设计更加有效的中继选择策略及多对多的数据分发协议。

[1] Perkins C E,Belding-Royer E M,Das S R. Ad hoc on-demand distance vector (AODV) routing:RFC 3561[S].NY:The Internet Society:2003.

[2] Perkins C,Bhagwat P.Highly dynamic destination-sequences distance-vector routing (DSDV) for mobile computers[C]∥Proc of ACM SIGCOMM,1994:232-244.

[3] Clausen T,Jacquet P. Optimized link state routing protocol (OLSR):RFC 2326[S].NY:The Internet Society:2003.

[4] Zhang Long, Zhou Xian-wei,Wang Jian-ping,et al.Routing protocols for delay and disruption tolerant networks[J].Journal of Software,2010,21(10):2554-2572.(in Chinese)

[5] Kretschmer C, Ruhrup S,Schindelhauer C.DT-DYMO:Delay-tolerant dynamic MANET on-demand routing[C]∥Proc of the 29th IEEE International Conference on Distributed Computing Systems Workshops,2009:493-498.

[6] Zhu D J,Cui G F,Zhong C.DT-AODV:An on-demand routing protocol based DTN in VANET[J].Applied Mathematics & Information Sciences,2014,8(6):2955-2963.

[7] John W, Vania C.HYMAD:Hybrid DTN-MANET routing for dense and highly dynamic wireless networks[J].Computer Communications,2010,33(13):1483-1492.

[8] Yu Zhen, Xu Jing-dong,Zhang Jian-zhong,et al.IEDR:An infrastructure enhanced DTN routing protocol[J].Journal on Communications,2013,34(8):44-52.(in Chinese)

[9] Musolesi M,Mascolo C.CAR:Context-aware adaptive routing for delay-tolerant mobile networks[J].IEEE Transactions on Mobile Computing,2009,8(2):246-260.

[10] Pant R,Tunpan A,Mekbungwan P,et al.DTN overlay on OLSR network[C]∥Proc of AINTEC’10,2010:56-63.

[11] Azzuhri S R,Ahmad H,Portmann M,et al.An efficient hybrid MANET-DTN routing scheme for OLSR[J].Wireless Pers Commun,2016,89(4):1335-1354.

[12] Gao W,Li Q H,Zhao B,et al.Multicasting in delay tolerant networks:A social network perspective[C]∥Proc of ACM MobiHoc,2009:299-308.

[13] Musoles M，Mascolo C.Designing mobility models based on social network theory[J].ACM SIGMOBILE Mobile Computing and Comm,2007,1(2):1-12.

附中文参考文献：

[4] 张龙,周贤伟,王建萍,等.容迟与容断网络中的路由协议[J].软件学报,2010,21(10):2554-2572.

[8] 于振，徐敬东，张建忠，等.基础设施增强的DTN路由协议[J].通信学报,2013,34(8):44-52.