基于稳定链路的移动AdHoc网络路由算法

黄波 张小华

摘 要： 移动自组织网络（MANETs）是无基础设施、由移动节点构成的动态网络。MANETs的移动特性给路由协议的设计提出挑战。为此，以典型的按需路由（AODV）为基础，提出基于链路稳定的MANETs路由协议，记为LSR。首先，分析了AODV的路由过程和不足，再计算节点能量寿命和链路寿命，然后通过比较能量寿命和链路寿命，构建候选转发节点集，最后，从链路稳定性角度，选择下一跳转发节点。实验结果表明，提出的LSR协议降低了路由开销，提升了吞吐量。与AODV相比，LSR协议的路由开销降低了近50%，吞吐量提高了23%。

关键词： 移动自组织网络； 路由； 按需路由； 链路寿命； 稳定链路； LSR协议

中图分类号： TN915.05?34； TPT393 文献标识码： A 文章编号： 1004?373X（2018）17?0090?05

Abstract： The mobile Ad Hoc networks （MANETs） composed of mobile nodes act as the dynamic network without infrastructure， and its mobile characteristic challenges the design of routing protocol. On the basis of the typical Ad Hoc on?demand distance vector （AODV） routing， the stable link based MANETs routing protocol （LSR） is proposed. The routing process and deficiency of AODV are analyzed， and then the energy lifetime and link lifetime of the node are calculated. The candidate forwarding node set is constructed by comparing the energy lifetime with link lifetime. The next?hop forwarding node is selected in term of link stability. The experimental results show that the proposed LSR protocol can reduce the routing overhead and improve the throughput. In comparison with AODV， the routing overhead of LSR protocol is reduced by 50%， and the throughput is improved by 23%.

Keywords： MANETs； routing； on?demand routing； link lifetime； stable link； LSR protocol

0 引 言

节点的移动性是移动自组织网络（Mobile Ad Hoc Networks，MANETs）[1?2]典型特性。由于节点自由移动，MANETs拓扑呈动态性变化。动态变化的拓扑对数据传输路径提出挑战。因此，路由技术成为MANETs的研究热点。由于节点通信半径有限，节点需要通过多跳传输方式才能将数据传输至目的节点。换而言之，数据包携带节点需要从邻居节点中选择某个节点作为下一跳节点，从而逐步建立完整的数据传输路径。将寻找最优的下一跳转发节点的过程称为路由发现。

现有的路由协议[4?5]主要有：表格驱动型、按需以及混合型三类。OLSR[3]，DSDV[4]就是典型的表格驱动型路由。按需路由协议典型的有AODV（Ad Hoc On?demand Distance Vector）[5]，ABR[6]。按需路由协议是指只有当节点需要传输数据时，才启动路由发现工作。混合型路由是指结合表格驱动型和按需型特点的路由，典型的有ZRP[7]，CEDAR[8]。

这些协议的主要差异在于路由发现机制的不同。表格驱动型路由是预先建立路由表，然后依据查表传输数据包。按需路由是当节点需要传输数据包时，通过传输路由请求（Route REQuest，RREQ）控制包和路由回复（Route REPly，RREP）包建立路由。

文献[9]提出了基于链路生存时间的改进路由协议（Enhanced Routing Protocol on Ad Hoc On?demand Distance Vector with Speed Variance， SV_AODV）。SV_ AODV路由协议计算每条链路的速度方差，再选择速度方差最小的路径传输数据，提高了链路的稳定性。文献[10]提出了AODV路由的改进协议AODV_D。AODV_D协议考虑了MAC层的节点竞争信息和接口队列时延，降低了传输时延。文献[11]提出AODV的优化协议，基于单播和广播结合策略，实现路由探测，通过降低广播帧数量，增强路由稳定性。文献[12]提出了基于链路质量的改进AODV协议，通过设定链路质量阈值，丢弃链路质量差链路，提高了路径稳定性。

本文研究了AODV协议的不足，然后针对移动自组织的特性，提出基于链路稳定的MANETs路由协议，记为LSR（Link Stable Routing）。LSR协议充分考虑了MANETs的移动特性，从链路的稳定性角度选择下一跳转发节点。实验数据表明，提出的LSR协议能够有效地提高数据包传输率，并降低了端到端传输时延。

1 AODV协议及问题描述

相对于其他反应式路由，AODV协议具有一定的优势，具体而言，AODV协议是利用局部广播发现路由。当节点需要传输数据包，它首先向邻居广播RREQ包。一旦是第一次收到RREQ包，邻居节点就将自己信息加入RREQ包，并转播，直到目的节点接收到RREQ包。

源节点与目的节点间可能存在多条路径，因此，目的节点可能会收到来自不同路径传输的RREQ包。目的节点就沿着传输RREQ包的路径回复包，进而告知源节点，数据路径通道已建立。

图1显示了AODV路由发现过程，其中图1a）表述了RREQ的传输过程，图1b）表示RREP的传输过程。具体而言，若源节点1需要传输数据包，就向邻居节点广播RREQ控制包，再由邻居节点转播，直到目的节点8接收到RREQ包。当目的节点8接收RREQ包后，就沿着传输RREQ包回复RREP包，即目的节点8沿着[8→5→2→1]向源节点1回复RREP控制包。源节点一旦接收了RREP，就意味着路由发现阶段完成。

相比于其他反应式路由，AODV路由具有一定的优势，如较低的控制开销和按需特性[13]。但是对于移动自组织网络而言，节点移动是一个重要特性。而传统的AODV协议并没有考虑到节点移动。基于AODV的改进RAODV协议考虑了节点的移动性。此外，节点能耗也是一个必须考虑的因素。其中MAODV?X考虑了节点能耗问题，将节点能耗融入链路的稳定性。然而，这些协议在路由发现过程中，只是单一考虑了节点移动或节点能耗。

为此，提出LSR协议。与传统的AODV协议不同，LSR协议考虑了节点移动和能耗问题。同时，LSR协议不再建立从源节点至目的节点整条路径，而是引用了基于位置路由的思想，从链路稳定性角度选择下一个转发节点。

2 LSR协议

LSR协议中节点通过交互HELLO消息，获取网络拓扑信息，并且每个节点传输半径为[R]，覆盖范围为圆形。通过交互节点的局部信息，可计算节点能量消耗率，再计算节点能量寿命，然后计算链路寿命，最后，计算链路的稳定性。最终选择最稳链路传输数据包。整个LSR协议框图如图2所示。

2.1 能量消耗率

首先，计算节点的剩余能量。假定节点[i]的初始能量为[Ei]。若节点[i]每传输一个数据包所需的能量为[Ti]，每接收一个数据包所消耗的能量为[Rk]。因此，在时刻[t]，节点[i]的剩余能量[REit]为：

2.2 链路的稳定性

2.3 下一跳转发节点

假定源节点[S]需要转发数据包，据此，节点[S]先向其邻居节点广播RREQ包，其包含了节点速度和位置。邻居节点接收RREQ后，分别依据式（3）和式（9）计算能量寿命和链路稳定性，并将这些信息载入RREP，向源节点[S]回复RREP。

通过多次接收RREP后，源节点[S]就从邻居选择中选择一个最合适的节点作为下一跳转发节点。为此，源节点[S]选择在节点能量寿命区间具有链路最稳定的节点作为下一跳节点。

具体而言，假定源节点[S]的一跳邻居节点集为[NS]。源节点[S]就分别比较一跳邻居节点（假定节点[i∈NS]）的能量寿命与链路寿命。只有能量寿命大于链路寿命的节点才能作为候选转发节点集[ψS]，如式（10）所示。反之，若能量寿命小于链路寿命，即数据在传输过程中，节点能量消耗殆尽，这将导致链路中断。

2.4 路由发现流程

当源节点[i]需要向目的节点[d]传输数据包时，先向邻居广播RREQ控制包。接收了RREQ控制包后，首先检测是广播ID，若之前已接收过同样的ID，则丢弃。否则进一步判断自己是否是目的节点，如果是，就直接回复RREP控制包，否则就计算能量寿命和链路寿命，并将这些信息载入RREP，再向源节点[i]回复RREP控制包。源节点接收多个RREP包后，依据式（10）构建一跳候选转发节点集，然后再依据式（11）产生下一跳转发节点，整个流程如图3所示。

3 數值分析

3.1 仿真场景

为了更好地分析LSR协议性能，通过NS2建立实验平台。[N]个节点随机分布于1 000×1 000区域，且以Random Waypoint作为节点的移动模型，移动速度为[?]，且[R=250] m，节点初始能量为1 873 J。每次实验独立重复50次，取均值作为最终实验数据。仿真时间为800 s。

为了衡量LSR协议性能，选择AODV，SV?AODV和AODV_D作为参照。同时考查路由开销、吞吐量和端到端传输时延方面的性能。其中路由开销是指每接收一个数据包所需的控制开销；吞吐量是指单位时间内平均每个节点所接收的数据量；端到端传输时延是指平均传输一个数据包所需的时间。

3.2 实验数据

3.2.1 路由开销

首先分析路由开销随节点数的变化情况，其中，[N]从50～200变化，且节点移动速度[?=10 m/s]，实验数据如图4所示。

从图4可知，路由开销随节点数的增加而增加。这主要是因为：节点越多，网络密度越大，信道资源竞争越激烈，提升了控制包的冗余数。此外，节点数越多，传输路径的跳数可能也越多，这也增加了控制包数。与AODV，SV?AODV和AODV_D相比，LSR协议的路由开销得到有效控制。

图5分析了路由开销随节点移动速度的变化情况。其中节点数为150，节点移动速度为从0～20 m/s变化。从图5可知：移动速度的加快，加速了拓扑变化，增强了路径的不稳定性，导致需频繁地建立数据包传输路径，最终增加了路由开销；AODV协议的路由开销最多，这主要是因为AODV采用泛洪机制建立路由；LSR路由开销最少，原因在于LSR路由在建立路由时考虑了节点的移动问题，并且总是选择最稳定的路由传输数据包。

通过图4，图5实验数据可知，与AODV，SV?AODV和AODV_D协议相比，提出的LSR协议能有效地控制路由开销。原因在于SV?AODV协议采用固定概率转播数据包，并没有依据网络信息决策是否转发数据包。与SV?AODV协议相比，AODV_D协议的路由开销得到控制，但仍高于LSR。

3.2.2 吞吐量

图6，图7分别描述了吞吐量随节点数和节点移动速度变化情况。在图6的实验中，节点数[N]从50～200变化，且节点移动速度[?=10] m/s；而在图7实验中，[N]为150，且节点移动速度从0～20 m/s变化。

从图6可知，节点数的增加降低了吞吐量。原因在于：节点数越多，网络资源竞争越激烈，影响了数据传输的流畅性。与AODV，SV?AODV和AODV_D协议相比，LSR协议的吞吐量最高，比AODV_D协议提高了近30%。这主要归功于LSR协议是基于链路稳定性选择下一跳转发节点。

图7的数据与图6类似。节点移动速度的变化减少了网络吞吐量，原因在于：移动速度的增加，加剧网络拓扑变化，必然降低路径稳定性。尽管如此，LSR协议仍能保持较高的吞吐量。

3.2.3 端到端传输时延

圖8，图9分别描述了端到端传输时延随节点数和节点移动速度变化情况。在图8的实验中，节点数[N]从50～200变化，且节点移动速度[?=10] m/s；而在图9实验中，[N]为150，且节点移动速度从0～20 m/s变化。

由图8可知，节点数的增加加大了端到端传输时延，原因在于：节点数的增加，加剧了网络资源的竞争，破坏了数据传输的流畅性。从图9可知，LSR协议的端到端传输时延最低，这主要是因为LSR协议在选择下一跳转发节点时，充分考虑了节点的移动速度及链路的稳定性，增强了LSR协议对节点移动的强健性。

4 结 论

针对MANETs的数据传输问题，提出基于链路稳定的MANETs路由协议LSR。LSR从节点能量和链路稳定性出发，旨在选择稳定路径传输数据包。依据节点移动以及能量消耗速度，计算能量寿命和链路寿命，再构建候选转发节点集，最后，择优选择下一跳转发节点。仿真数据表明，提出的LSR协议能够有效地降低时延，并提高吞吐量。

参考文献

[1] CHITRAXI R， URVIK U， TWINKLE P M. Simulation of VANET using ns?3 and SUMO [J]. International journal of advanced research in computer science and software engineering， 2014， 4（2）： 563?569.

[2] ANDREA G， GIANLUIGI F. Irresponsible AODV routing [J]. Vehicular communications， 2015， 3（2）： 47?57.

[3] EI W， BEN G， SAFA H. MOLSR： mobile?agent based optimized link state routing protocol [C]// 2015 International Wireless Communications and Mobile Computing Conference. Pisca?taway： IEEE， 2015： 355?360.

[4] PERKINS C E， BHAGWAT P. Highly dynamic （DSDV） for mobile computers routing [C]// Proceedings of 1994 the ACM SIGCOMM. New York： ACM， 2014： 234?244.

[5] LEE S J， BELDING E M， PERKINS C E. Ad Hoc on?demand distance?vector routing scalability [J]. ACM mobile computing and communications， 2012， 6（3）： 94?104.

[6] TOH C K. Associativity?based routing for Ad Hoc mobile networks [J]. Wireless personal communications， 2010， 4（2）：103?139.

[7] HAAS Z J， PEARLMAN M R. The performance of query control schemes for the zone routing protocol [J]. IEEE transactions on networking， 2001， 9（4）： 427?438.

[8] SINHA P， SIVAKUMAR R， BAHRGHAVAN V. CEDAR： a core extraction distributed Ad Hoc routing algorithm [J]. IEEE journal on selected areas in communications， 1999， 17（8）： 1454?1466.

[9] 曹文君，薛善良.一种适用于城市车载网的改进的AODV协议[J].计算机与现代化，2016，23（7）：98?103.

CAO Wenjun， XUE Shanliang. An improved AODV routing protocol for urban vehicular Ad Hoc networks [J]. Computer and modernization， 2016， 23（7）： 98?103.

[10] 刘大勇，赵春江.基于AODV的农田无线传感器网络路由和休眠算法[J].微电子学与计算机，2015（10）：115?120.

LIU Dayong， ZHAO Chunjiang. A wireless sensor network routing and sleeping algorithm in agriculture based on AODV [J]. Microelectronics & computer， 2015（10）： 115?120.

[11] 蔡菁，朱余兵.一种基于AODV改进的城市车载自组网络路由协议研究[J].计算机工程与科学，2013，35（1）：61?66.

CAI Jing， ZHU Yubing. An improved AODV routing protocol in urban vehicular ad hoc networks [J]. Computer engineering and science， 2013， 35（1）： 61?66.

[12] BUTT M R， AKBAR A H. LABILE： link quality?based lexical routing metric for reactive routing protocols in IEEE 802.15.4 networks [J]. Journal of supercomputing， 2012， 62（1）： 84?104.

[13] LEI Q， WANG Xiaoqing. Improved energy?aware AODV rou?ting protocol [C]// 2009 International Conference on Information Engineering. [S.l.： s.n.]， 2009： 18?21.

[14] HAFEEZ K， ZHAO L， LIAO Z， et al. Impact of mobility on VANETs′ safety applications [C]// 2010 IEEE Global Telecommunications Conference. Piscataway： IEEE， 2013： 1?5.

[15] ZHAO M， LI Y， WANG W. Modeling and analytical study of link properties in multi?hop wireless networks [J]. IEEE tran?sactions on communications， 2012， 60（2）： 445?455.