MANETs中基于节点移动度的虚连接的路由

丁颖　黄继海

摘 要： 由于移动自组织网络MANETs中节点的快速移动，使得维持源节点与目的节点间的通信路径成为一项挑战性工作。节点的高速移动导致通信链路频繁断裂。为此，提出基于节点移动度的虚连接的路由（MDVRP）。虚路由为一条动态的逻辑路由，其由一系列的特定地理区域构成。每个区域内的节点依据自己的移动度设置转发数据包的定时器，移动度越小，具有优先转发数据包权。MDVRP通过虚路由策略，在源节点与目的节点间建立了多条传输路通，每个节点能独立选取下一跳转发节点，并利用节点移动度，择优选取转发数据包下一跳节点，从而提高链路的稳定性。仿真结果表明，提出的路由协议在端到端传输时延、路由开销以及数据包传输率性能均得到提高。

关键词： 移动自组织网络； 路由协议； 移动节点； 虚路由； 虚连接

中图分类号： TN915?34 文献标识码： A 文章编号： 1004?373X（2017）20?0067?05

Abstract： Since the node in mobile Ad Hoc networks （MANETs） moves fast， which makes the maintaining of communication routing between source node and destination node become a significant challenge， and results in frequently break of communication links， a routing of virtual connection based on node mobility degree， which is marked as MDVRP （mobility degree of node?virtual router protocol）. The virtual routing is a dynamically?created logical routing that is constructed with a series of particular geographical areas. The timers of forwarding data packet of nodes in each region are set according to their mobility degree. The smaller the mobility degree of node is， the earlier the priority of forward data packet obtains. The MDVRP is used to establish more transmission paths between source node and destination node. Each node is able to independently determine its next forwarding node according to the stability degree of the node， so as to improve the stability of the link. The simulation results show that the proposed MDVRP has good performance in term of end?to?end transmission delay， routing overhead and transmission ratio of delivered packet.

Keywords： mobile Ad Hoc network； routing protocol； mobile node； virtual routing； virtual connection

0 引 言

移动自组织网MANETs （Mobile Ad Hoc Networks）是由移动节点MNs（Mobile Nodes）自行移动构成的网络[1]。在MANETs中，无需任何硬件设备，移动节点MNs能够相互通信，每个移动节点MN扮演路由（Router）角色。由于移动节点MNs自由移动，使得拓扑结构动态变化，这也是移动自组织网MANETs最显著的特性[2]。这一特性给MANETs的路由技术提出挑战。

依据是否面向连接，MANETs中现有的路由协议可分为面向连接（Connection?oriented）路由协议和非连接（Connection?less）路由协议[3]。在面向连接（Connection?oriented）路由协议中，在数据包传输前先建立逻辑连接（Logical connection），并且在数据传输的整个过程，保持连接的连通性。一旦某链路断裂，连接就发生中断，数据传输失败，就需要重新建立连接，增加了路由开销。AODV协议[4]是典型的面向连接路由协议。

相反，非连接路由协议在数据传输前无需预先建立连接[5?9]。每个数据包内存在通往目的节点的路由信息，独立选路。若某链路断开，节点依据目的地址，再重新选择路由。

为此，为了能更好应对高速移动的环境，提出基于节点移动度的虚路由（Virtual router）的连接路由协议，记为MDVRP（Mobility Degree of Node?Virtual Router Protocol）。尽管MDVRP协议是面向连接的，但是在数据传输前建立的是虚连接，而不是物理连接。虚路由是关于特定地理区域的逻辑路由（logical router）。一个虚路由是由地理区域内的一个或多个移动节点构成。虚路由所在地理区域性内的物理节点依据节点的移动度设置转发数据包的定时器，移动度越小，定时器时长越短，即具有优先转发数据包权。仿真结果表明，相比于AODV，提出的MDVRP在提出的路由协议端到端传输时延、路由开销以及数据包传输率性能均得到显著提高。endprint

1 MDVRP协议

现存的路由协议方案，在面对高速移动的环境时，均遭受严重的链路断裂。在此，提出的MDVRP方案，其重点是预防通信链路的断裂而不是重建已断裂的通信路径。

1.1 关键概念

1.1.1 虚路由

虚路由是关于特定地理区域的逻辑路由[10]。 一条虚路由是由一系列地理区域内的一个或多个移动节点构成，可形成多条数据传输通路。每个节点一跳通信范围为一个地理区域，且相邻地理区域之间允许重叠。如图1所示，源节点S与目的节点D存在一条虚路由[r1→r2→r3→r4→r5]。其中[r1，r2，…，r5]表示地理区域，如图1中的虚线圈所示。在每個地理区域内存在一个或多个传感节点。这些传感节点以多跳方式向目的节点传输数据包。此外一条虚路由存在多条路径，图1描述了两条路径[S→a→b→c→e→f→g→h→][m→D，S→A→B→C→E→F→G→H→L→M→D。]

1.1.2 节点的移动度

移动是MANETs最显著的特性。为了更好地描述这一特性，本文引入节点移动度MD（Mobility Degree）量化此特性，并利用移动度进行路由发现和路由更新，进而找到稳定的虚路由。

1.2 路由请求

当源节点需要向目的节点发送数据包时，源节点首先产生路由请求消息M_req（Route Request Message），其包含源节点ID号，再广播路由请求消息M_req，邻近的节点将收到M_req。尽管收到M_req的每个节点能够简单地转发该M_req，但是为了避免了网络风暴，采用随机延时（Probabilistic delay）技术[11]。致使接收到M_req每个移动节点随机延时一段时间[T]，且[T∈0 ， Tmax]。[Tmax]表示最长的延时时间。在这段时间内，节点监听是否有其他节点转发M_req。如果这段延时未结束前，已有其他节点转发了该M_req，那么该节点就不再转发M_req。若没有，节点就在延时结束后，将自己的ID号嵌入M_req再转发。通过多跳转发方式，目的节点最终收到M_req消息。此外，本文将转发M_req消息的节点，称为转发节点RN（Reply Node）。

1.3 路由回复

一旦目的节点收到M_req消息，目的节点就产生路由回复消息M_rep（route reply Messages ）消息，并建立通信路由。M_rep消息包括源节点、目的节点的ID号、路由ID，以及转发M_req消息的一系列的转发节点，如图3所示。 目的节点产生了M_req消息后，立即广播M_req消息。位于M_req消息中的转发节点RNs就识别该路由。

在传递M_req消息的过程，一些邻居节点可能监听M_req消息。这些监听节点可加入通信路由，成为传递数据包的潜在的一个成员。因此，与转发节点RNs一样，监听节点也能够沿着路由转发数据包。对于任何路由中的移动节点，包括转发节点RNs和监听节点，最终是否转发数据包是依据它的移动度MD决定的，具有最小移动度MD的节点具有最先转发数据包的权利。

1.4 数据包的转发

一旦建立了通信路由，源节点就可沿着该路由向目的节点转发数据包。源节点在转发数据包前，先在数据包前加载一个信息头，该信息头包涵源节点的ID、目的节点ID以及数据包ID、路由ID、移动度MD以及遍历节点TNs（Traversed Nodes）区域。数据包ID域用于存储源节点需要向目的节点发送的数据包标识。移动度MD域用于存储转发了数据包节点的移动度。遍历节点TNs是指已转发了数据包的一系列节点。

一旦节点[i]接收到来自节点[j]的数据包，节点[i]首先检查自己是否是该数据包的目的节点。若是，则不转发该数据包，否则进一步检验之前是否有接收过该数据包，若有，则不转发该数据包，若没有，节点[i]检测是否在该路由中，若不在，也不转发该数据包，如果在，节点[i]将依据自己的移动度，设置等待转发数据包的定时器。定时器的时间[Times]与移动度成正比，如下：

式中：[MDi，t]表示节点[i]在时刻[t]的移动度；[Timesmax]表示定时器的最长时间；[?]表示下限取整。

如果在定时器定时完毕之前，节点[i]监听到其他节点转发的数据包，那么节点[i]就不转发数据包，并将定时器置0。否则，等待定时器计时，当计时完毕，节点[i]就立即转发该数据包。节点[i]处理来自节点[j]的数据包具体流程如图4所示。

1.5 路由更新

如果一些节点脱离了虚路由，就可能导致链路断裂。为了降低链路断裂概率，目的节点周期地向源节点发送路由更新消息M_Rup（Route Update Message）。M_Rup消息包含目的节点ID、源节点ID、路由ID以及目的节点从源节点接收到的最新数据包所遍历的节点集。目的节点通过这些节点集将M_Rup消息转发给源节点。一旦源节点接收到M_Rup消息，将丢失旧的虚路由，采用新的路由。

图5描述建立新路由的过程。假定现存在一新虚路由，其由[r1→r2→r3→r4→r5]一系列区域构成。一旦该虚路由有链路断裂，目的节点就发送路由更新M_Rup消息。目的节点D注意到，最新收到的数据包是[S→a→b→c→e→f→g→h→m→D]路径传递。因此，目的节点沿着[D→m→h→g→f→e→c→][b→a→S]向源节点传递M_Rup消息。在M_Rup消息经[D→m→h→g→f→e→c→b→a→S]传递至源节点过程中，这些节点的邻居节点偷听到M_Rup消息，从而形成新的虚路由[R′1→R′2→R′3→R′4→R′5]，如图5所示的粗线圈。一旦源节点接收到M_Rup消息，随后的数据包就沿着最新虚路由转发。注意到，路由更新过程，节点不需要周期地广播beaconing消息，降低了路由开销。endprint

2 系统仿真及性能分析

为了更好地评估提出MDVRP性能，采用GloMoSim进行仿真[12]，并与AODV和SVR[13]进行性能比较。选择AODV和SVR的原因是在于：AODV是移动自组织网络中最典型的路由协议，具有很好的参考价值；SVR（Static Virtual Router）是静态的虚路由，虚路由是预先设定的，并且每个移动节点有虚路由分布图。而提出的MDVRP是动态的虚路由，将MDVRP与SVR进行比较，能够更好地分析MDVRP性能。

仿真过程中，首先考虑[100×1 000]的仿真区域，传感节点均匀分布于仿真区域，传感节点通信半径为133 m。采用Random Way point 移动模型[14]。在该模型中，每个节点随机选择一个目的节点进行移动。仿真时间为15 min，具体的仿真参数如表1所示。

2.1 性能指标

分析MDVRP性能时，主要考虑数据包传输率RPD（Ratio of Packets Delivered）、端到端传输时延EED（End?to?End delay）以及归一化的路由开销NRO（Normalized Routing Overhead）三个指标：

（1） 数据包传输率RPD。指目的节点接收到的数据包与源节点发送的数据包之比，其反应了路由协议传输数据包的能力。

（2） 端到端传输时延EED。表示数据包从源节点传递至目的节点所需的时间，反应了路由协议传输数据包的速度；

（3） 归一化的路由开销NRO。表示目的节点每接收一个数据包所需的控制包数量，其反应路由协议的效率以及可扩展性。

2.2 仿真结果及分析

在仿真過程中，设置三类不同场景考查节点移动速度、节点密度以及仿真区域大小对路由协议的性能影响。

（1）移动速度。为了分析移动速度对路由协议的性能影响，在仿真过程中将节点移动速度从10～25 m/s变化。仿真结果如图6所示。

从图6可知，提出的MDVRP方案的数据包传输率RPD、端到端传输时延EED以及归一化的路由开销NRO均优于AODV。具体而言，在RPD方面，MDVRP优于AODV，与SVR类似。采用虚路由的MDVRP和SVR均能应对节点的高速移动，达到高的数据包传输率。而EED方面，类似地，MDVRP和SVR均优于AODV，并且MDVRP也优于SVR。这主要是因为：SVR中的通信路由是由预先设定的虚路由构成，而MDVRP采用动态虚路由，能够更好地应对节点的移动。在NRO方面，MDVRP和SVR均优于AODV，但MDVRP略优于SVR，原因在于MDVRP采用动态虚路由，降低链路断裂的概率，而SVR采用预设的虚路由，难以应对因节点移动而带来的链路，提高了路由开销。

（2） 节点密度。为了分析节点密度对路由协议的性能影响。在[100×1 000]的仿真区域内的节点数从600～3 000变化，换而言之，仿真区域内节点密度发生变化。仿真结果如图7所示。

从图7可知，节点密度的增加提高了路由开销，并且对数据包传输率有消极影响，导致了更高的传输时延。这主要是因为节点密度增加，使得每条路由请求中涉及的节点数增加，增加了网络拥塞概率。

具体而言，从图7（a）和图7（c）可知，随着节点密度的增加，AODV采用了更多的控制数据包修复路由，但数据包传递率未得到提升。相反，随着节点密度的增加MDVRP的路由开销只是略有增加，并且仍保持高的数据包传输率。从图7（b）和图7（c）可知，在高密度区域，AODV的传输时延比MDVRP高出了6倍，路由开销高出了20倍。此外，SVR和MDVRP的数据包传输率、路由开销的性能类似，但是MDVRP的端到端传输时延优于SVR。

（3） 仿真区域大小。为了分析仿真区域大小对路由协议的性能影响，设置4个仿真区域尺寸，并保持节点密度相等。4个区域尺寸分别为：[500 m×500 m]区域，内有250节点；[1 000 m×1 000 m]区域，内有1 000节点；[1 500 m×1 500 m]区域，内有2 250节点；[2 000 m×2 000 m]区域，内有4 000节点。仿真结果如图8所示，图8的横坐标中的500，1 000，1 500，2 000分别表示[500 m×500 m]区域、[1 000 m×1 000 m]区域、[1 500 m×1 500 m]区域、[2 000 m×2 000 m]区域。

从图8可知，AODV难以维持长的路由。随着仿真区域的扩大，路由长度增加，路由断裂的概率也成比率增加。由于不采用固定的hop?by?hop路由，相比于AODV，MDVRP仅以小的路由开销的增加（见图8（c））得到高的数据包传输率（见图8（a））。随着仿真区域的扩大，MDVRP的时延略有增加，如图8（b）所示。这主要因为，仿真区域的扩大，增长了路由，相应地，增长了数据包达到目的节点的时延。

此外，注意到图8（b）和图8（c），在[2 000 m×2 000 m]区域，MDVRP的端到端传输时延性能比AODV提高了3倍，路由开销性能提高了近40倍。与AODV相比，SVR仍具有良好的性能，但是SVR的端到端传输时延仍劣于MDVRP。

3 结 语

本文针对移动自组织网络MANETs的路由协议，提出MDVRP协议。MDVRP采用虚路由，使得源节点至目的节点间存在多条通信路径，并依据节点移动度，择优选取数据包的转发节点，提高链路的稳定性，能够有效地应对节点的移动。

仿真结果表明，提出的MDVRP在端到端传输时延、数据包传输率以及归一化的路由开销明显优于AODV。

参考文献

[1] KUMAR M， MISHRA R. An overview of MANET： history， challenges and applications [J]. Indian journal of computer science and engineering， 2012， 3（1）： 121?125.endprint

[2] CHLAMTAC I， CONTI M， LIU N. Mobile ad hoc networking： imperatives and challenges [J]. Ad Hoc networks， 2003， 1（1）： 13?64.

[3] HO A H， HO Y H， HUA K A. Handling high mobility in next?generation wireless Ad Hoc networks [J]. International journal of communication systems， 2010， 23（9）： 1078?1092.

[4] GUI C， MOHAPATRA P. A framework for self?healing and optimizing routing techniques for mobile ad hoc networks [J]. Wireless networks， 2008， 14（1）： 29?46.

[5] 洪棒，俞立，张贵军.无线传感网络自适应分布式聚簇路由协议[J].自动化学报，2011，37（10）：1197?1206.

[6] 罗娟，肖仪，卢真，等.基于网络编码的多播车载网络路由算法研究[J].计算机研究与发展，2011，48（9）：1616?1622.

[7] PANICHPAPIBOON S， FERRARI G， TONGUZ O K. Connectivity of ad hoc wireless networks： An alternative to graph?theoretic approaches [J]. Wireless networks， 2010， 16（3）： 793?811.

[8] 夏梓峻，刘春凤，赵增华，等.基于链路预测的VANET路由算法[J].计算机工程，2012，38（4）：110?114.

[9] KESTING A， TREIBER M， HELBING D. Connectivity statistics of storeand?forward intervehicle communication [J]. IEEE transactions on intelligent transportation systems， 2010， 11（1）： 172?181.

[10] PASCOE?CHALKE M， GOMEZ J， RANGEL V， et al. Route duration modeling for mobile Ad?Hoc networks [J]. Wireless networks， 2010， 16（3）： 743?757.

[11] YAN Gongjun， OLARIU Stephan. A probabilistic analysis of link duration in vehicular Ad Hoc networks [J]. IEEE transactions on intelligent transportation system， 2011， 12（4）： 1227?1237.

[12] ZENG X， BAGRODIA R， GERLA M. GlomoSim a library for parallel simulation of large?scale wireless network [C]// Proceedings of the Twelfth Workshop on Parallel and distributed simulation. [S.l.：s.n.]，1998： 154?161.

[13] HO Y H， HO A H， HUA K A. Connectionless protocol： a localized scheme to ad hoc network [J]. International journal of Ad Hoc and ubiquitous computing （IJAHUC）. [S.l.：s.n.]， 2007， 2（1）： 21?35.

[14] LEE J H， ERNST T， CHILMAKURTI N. Performance analysis of pmipv6 based network mobility for intelligent transportation systems [J]. IEEE transaction on vehicular technology， 2012， 61（1）： 23?32.endprint