AODV协议及其改进对Ad Hoc网络的影响与性能比较研究

© 2013作者。出版社：Elsevier B.V.由美国应用科学研究所负责选择和/或同行评审可在www.sciencedirect.com在线获取ScienceDirectAASRI Procedia 5（2013）21 - 312013年AASRI并行和分布式计算与系统Ad Hoc网络AODV路由协议研究1刘胜，杨洋，王长安大学信息工程学院，摘要本文首先介绍了Ad Hoc网络的基本特点、关键技术，并与其他移动通信系统进行了比较。通过对DSR、TORA、ABR、AODV等路由协议的分析和比较，研究了Ad Hoc网络的按需路由协议。详细介绍了AODV路由协议。针对AODV协议在路由发现和路由修复方面的不足，提出了一种改进的AODV协议：B-AODV。在B-AODV协议中，首先通过反向请求发送BRREQ代替RREP，减少了路由发现的时间。第二，在控制消息和路由表中记录两跳IP，可以提高路由修复率，减少路由发现次数。同时也提高了Ad Hoc网络的性能。在NS 2环境下进行了AODV和B-AODV的仿真实验，并对AODV和B-AODV的性能进行了比较。比较了AODV和B-AODV在控制包、包比、端到端时延等方面的差异。结果表明，B-AODV算法优于AODV算法。© 2013作者。由Elsevier B. V.在CC BY-NC-ND许可下开放获取。由美国应用科学研究所负责选择和/或同行评审关键词：Ad Hoc网络，在端路由，AODV近年来，Ad Hoc网络路由协议的研究[1]引起了人们的广泛关注。基于Ad Hoc网络的多跳特性[2]，经典的路由协议已经不能满足网络拓扑不可预测和频繁Ad Hoc路由协议必须保持及时、* 通讯作者。联系电话：电话：+0-139-91256322传真：+0-139-91256322电子邮件地址：thgpc@163.com。2212-6716 © 2013作者由Elsevier B. V.在CC BY-NC-ND许可下开放获取。美国应用科学研究所负责的选择和/或同行评审doi：10.1016/j.aasri.2013.10.05422Sheng Liu等/ AASRI Procedia 5（2013）21重新构造路由，必须考虑带宽和高错误率。由于其他网络路由协议的不足，需要设计新的适用于AdHoc网络的路由协议。1. AODV协议1.1. AODV协议AODV（Ad hoc on-demand distance vector routing）是一种源驱动类型的路由协议。当源节点向目标节点发送消息时，如果没有路由，它首先发送Rename。当相邻节点接收到带有源节点和目标节点地址的Rename时，判断Rename是否与目标节点的地址相同。如果是，则向源节点发送RREP，否则，检查路由表中可以到达目标节点的路由，然后向源节点发送RREP，或者继续洪泛发送RREP。AODV协议通过定期广播hello消息来维护路由节点。如果其中一条链路中断，则向节点发送ERROR消息，同时删除中断记录或修复路由。1.2. AODV的不足[4]AODV协议是在路由发现和路由维护的基础上，在网络中的两个节点之间建立路由。在路由请求过程中，以洪泛的形式向目标节点广播RREP消息;在路由响应过程中，目标节点优先选择最先到达的RREP并发送RREP消息。由于节点在寻找路由过程中的剧烈运动，路由很容易被破坏，从而导致RREP数据包的丢失。在路由维护过程中，失效节点在广播RERR报文时，会丢弃错误报文并通知源节点重发请求报文，导致后续报文的时延;为了消除新路由引起的拥塞，局部修复可能导致下游节点发送的RREP报文被丢弃，降低了路由恢复的概率。另外，尽管有路由维护机制，但节点是移动的，路由可能无法及时修复或修复失败，这降低了网络控制信息的利用率，并可能增加路由延迟，从而影响网络的性能。2. B-AODV协议针对AOFV协议的不足，需要一种更好的协议来避免路由中断，降低消息丢失率，减少网络延迟。在AODV协议的基础上，设计了一种改进的B-AODV协议，假设网络链路是双向的，即源节点和目的节点可以通过一条路由到达对方。2.1. 路由构造对于AODV，如果节点移动速度快，在反向路由中RREP通过单播发送应答消息，并将RREP单播回源节点，可能会导致数据包丢失，因此在B-AODV中，在建立反向路由时，设计了类似于RREP的控制消息B-RREP。源节点也作为目标节点承担路由发现的任务，在接收到路由请求后，向源节点发送泛洪B-Rack消息，查找源节点。当源节点获得第一个B-RREQ时，它开始传输数据，并在RREQ和B-RREQ中记录前两跳节点和下两跳节点的信息，以便快速重建路由。Sheng Liu等/ AASRI Procedia 5（2013）2123路由发现过程详细描述如下。当源节点没有到目的节点的路由而必须向目的节点发送数据时，它向邻居节点广播Rounds消息。Rounds消息这种格式增加了前两跳节点和下两跳节点的地址，表明Rename不仅记录了当前节点的邻居地址，而且还记录了两跳节点的地址。当一个节点广播Rounds控制消息时，Rounds计数器自动加1。源节点IP地址和RMBID可以唯一地标识RMBID控制消息。一个节点在接收到相同的控制消息时检查ID，如果相同，则丢弃其中一个。这个过程与AODV完全相同。中间节点在得到路由信息后，与自身的路由信息进行比较，并更新路由表中的相关信息，从而增加相关字节：前两跳节点地址和后两跳节点地址。路由表的格式如表2所示。如果中间节点没有到目标节点的路由，则继续发送RREQ，并构造反向路由。当Rack分组到达目标节点时，目标节点创建类似于Rack的分组B-Rack。表3显示了B-Risk消息格式。表1 RREP报文格式表2新建路由表表3 B-RREP报文格式类型保留Hip HopRIDID类型保留HipHopRIDID目标节点IP地址下一跳节点地址前一 跳 节 点 地址下一个两跳前两跳节点地址下一跳节 点地 址 前 一 跳节点地址前 两 跳 节 点地址目标节点序列号目标节点序列号标签下一个单跳节点地址下一个两跳节点地址源节点IP地址源节点序号目标节点IP地址目标节点序号源节点的IP地址源节点的序列号路由请求时间源节点IP地址源节点序号目标节点IP地址目标节点序号源节点的IP地址源节点的序列号路由应答时间前一跳节点地址前两跳节点地址跳数寿命前两跳节点地址目标节点创建B-Rounds后，立即将其广播给邻居节点，与源节点广播Rounds的过程相同，即建立反向路由。当中间节点接收到数据包时，它会检查是否有相同的数据包，如果是，则丢弃相同的数据包。否则，它将被发送到邻居节点。邻居节点接收到数据包后，记录下一跳和前两跳节点的地址，并设置路由生命周期，直到到达目标节点。源节点在接收到第一B-RREQ时立即发送数据。路由应答过程如图1所示。图1发送B-Risk24Sheng Liu等/ AASRI Procedia 5（2013）21如果找到YNN如果存在从其下一跳节点到目标节点的路由Y中间节点RREP回答，并建立路由上游节点向目标节点如果找到YN如果存在从其下一跳节点到目标节点NY中间节点RREP回答，并建立路由上游节点向目标节点发送数据发送数据在B-AODV中，由于 R4、R3 、R2、R3 、R4、R4、R5、R6 、R7 、R8 、 R9 、 R14 、 R13 、R12 、 R11 、 R10 、 R11 、 R12 、R13、R14、R13、R12、R13、R14、R16、R17、R18、R19、R18、R19、R19、R S节点可以在具有最大能量的路由中遍历数据。解决了AODV中RREP随中间节点移动而丢失的问题。路由发现流程如图2（a）、（b）所示。(a)（b）第（1）款图2 B-AODV2.2. 控制路由消息计算在B-AODV中，似乎增加了发送B-REQ的路由开销，然而，通过证明，它确实减少了。这里设置了一个网络环境网络中有N个节点在AODV协议中，路由发现过程中发送控制消息的数量为AONV（N）;在B-AODV协议中，路由发现过程中发送控制消息的个数为B-AONV（N）;在路由发现过程中，假设有m个节点发送消息，N如果路由被破坏了Y来自上游节点的路由可以到达下两跳节点继续发送数据如果路由被破坏了NY来自上游节点的路由可以到达下两跳节点继续发送数据Sheng Liu等/ AASRI Procedia 5（2013）21251234SFR1234SHR所述，如果第一路由发现正确，则发送控制消息的路由节点号为：AODV（m）=m-1+t（1）其中，t是发送路由应答消息的节点的数量。如果在AODV中路由发现超过1次，则应该是：AODV（m）=c（m-1+t）（2）其中c表示路由发现进程的数量。如果数据按照B-AODV传输，则在路由发现过程中至少有1条稳定的路由可以用来传输数据，因此只需要2 m-2个节点来传输数据：B-AODV（m）= 0（2m-2）（3）由此可以得出结论：当c>1时，AODV协议在路由建立过程中产生了更多的路由开销。2.3. 路由维护如图3所示，在AODV算法中，如果节点2和节点3之间的链路已经断开，节点2需要修复本地路由，发送RREQ，并找到到目标节点R的路由。RREP通过节点F转发到节点4，直到到达节点R，然后R沿着反向路由将RREP回复回节点2。从而建立了一条新的有效路由。如果在一定的修复时间内路由修复失败，则向源节点发送RRER消息，源节点重新发送RRER以查找路由。在新算法中，每个路由表维护相邻两跳节点的地址，当路由表中下一个节点3失效时，它将到达目标节点，这意味着路由无效，需要进行局部修复。与AODV协议不同的是，节点2不等待目标节点R的RREQ消息，因为路由表中已经记录了下两跳节点的地址，节点2寻找下两跳节点4，然后向节点4发送RREQ消息。当RREP通过节点F到达节点4时，同时节点4拥有到目标节点的主动路径，因此节点4可以将RREP直接发送到节点F，然后节点2. 这样就建立了从节点2到节点R的有效路由，如图3所示图3路由修复：找到2和4，建立新的路由图4路由修复：找到2和3，建立新的路由如果节点2和3之间没有共同的邻居节点，如图4所示，则节点3无法逃脱节点2的下一跳范围。因此，节点3很可能是节点2的下一个两跳节点之一。在这种情况下，节点H在接收到来自节点2的RREP后，发现其邻居中没有节点4而只有节点3，则节点H向节点2发送RREP，旨在通知其是与节点3共同的邻居节点，从而节点2将重建通过节点H和3到目标节点的新路由。26Sheng Liu等/ AASRI Procedia 5（2013）21M1234SMR如果节点3和节点4失效，如图5所示，节点2向目标节点R发送RREQ，寻找新的断路路由;如果路由发现失败，节点2向邻居节点发送RRER，直到返回源节点S，S重新发送RREQ，开始新一轮的路由发现，与AODV协议相同。由于节点的移动速度有限，实际上会更少。这降低了路由维护成本以及路由延迟。如果情况特殊，则节点4为目标节点，与原AODV算法完全相同，发送Random查找下一个两跳节点，即目标节点。当节点3为目标节点时，发送Rename直接查找目标节点。此外，由于断裂的下游邻居节点比目标节点更靠近断裂的上游节点，因此发现速度更快，即发现时间比AODV路由算法更短，因此新协议更优化。图5路由修复失败：下两跳节点无效2.4. 路由恢复设向目标节点4发送RREQ并回复RREP的时间为S1，向目标节点R发送RREQ并回复RREP的时间为S2，由上述叙述[5]可知：S1和S2 （当节点4与节点R相同时，方程成立）（4）设一个节点失效的概率为p（p1），则两个节点同时失效的概率为p，一个节点失效而另一个节点有效的概率为p（1-p）对于AODV路由算法，当节点3无效时，节点2重新找到路由的时间为：S（AODV）= p（5）对于改进的B-AODV路由算法，当节点3失效时，节点2重新找到路由的时间为：S（B-AODV）=（1-p）+p2（6）从（6）-（5），S（B-AODV）-S（AODV）=p（1-p）（S1由上可知，（7）0，即与AODV相比，改进算法的查找时间要短得多，而且节点3比节点R更靠近节点2，因此所需时间会更短。Sheng Liu等/ AASRI Procedia 5（2013）21273. 实验分析路由协议的性能取决于[6]：路由开销，发送数据包的能力，从节点到节点的延迟和数据包发送成功率等。而且不同的场景对路由协议有很大的影响。相同的路由协议在不同的模拟场景下，其路由性能也有很大的差异。adhoc网络场景的主要影响因素：网络节点的数量、网络的变化速度和运动速度。因此，在比较和分析不同的路由协议时，必须考虑到网络场景。这里的simulink环境是：windows xp+fedora core4+NS2。第二十九章。3.1. 设置网络参数，配置路由协议设置网络参数如下：节点数量：10，20，30，40，50; simulink环境：1000 m * 1000 m;节点最大速度分别为：2、5、10、25、50、75 m/s;无线模型：Two-Rav;网络业务：CVR业务流; MAC层模型：8.2.11;报文发送速率：8 packets/s。3.2. 路由协议路由协议的性能指标如下[7][8][9]：(1)成功数据包投递率成功数据包投递率=（发送数据包的数量(2)从节点到节点的从节点到节点的平均延迟=1NNi1RTI stI（九）其中N表示成功传输的数据包的数量，rt是数据包到达目标节点的时间，st是数据包被发送的时间。(3)路由开销路由开销可以比较不同路由协议的自适应能力和效率。公式为：路由开销=路由控制数据包总数（10）3.3. 结果分析通过对AODV和B-AODV的仿真，比较了它们在节点数和最大节点移动速度方面的性能。(1)分组投递率28Sheng Liu等/ AASRI Procedia 5（2013）21a. 不同节点图6不同节点b. 不同速度图7不同速度从图6中可以看出，改进后的协议在节点数较少的情况下与原协议的分组投递率基本相同，路由中断后路由修复的概率较低。当节点数较多时，路由的投递率明显降低，节点数越多，节点移动越频繁，路由中断的概率越大。9080706050节点数量›807060504030²010040AODV比例9590858075706560558070605040节点质量×速度30²010050AODV比例Sheng Liu等/ AASRI Procedia 5（2013）2129从图7中可以看出，速度越快，数据包投递率越低。显然，当节点高速移动时，丢包率会增加。然而，B-AODV的分组投递率远远高于AODV。(2)从节点到节点的a不同节点之间的平均延迟 b不同速度图8不同节点图9不同速度0.40.350.30.²50.²0.150.10.05节点数量›807060504030²01000B–AODV0.60.50.40.30.²0.1节点数量›807060504030²01000B–AODVDalayDalay30Sheng Liu等/ AASRI Procedia 5（2013）21B-AODV的延迟较低。另一方面，由于原协议在路由发现时必须限制RREP应答，当路由中断时，AODV必须先向目标节点发送RREP，然后通过返回RREP重建路由，而B-AODV只向前两跳节点发送RREP，然后再建立前向路由，因此时延较低。(3)路由开销比较图10路由开销从图10中可以看出，当节点数较少时，两个控制包的数量相近，但当节点数增加时，B-AODV协议明显比AODV协议优化。.4. 结论Ad Hoc网络的自组织性、多跳性以及网络结构的多变性等特点增加了路由技术的难度，因此设计Ad Hoc路由协议的关键是解决节点快速移动造成网络结构复杂变化的问题。在对AODV路由协议进行比较分析的基础上，提出了一种改进的B-AODV路由协议，该协议对路由发现和局部修复进行了改进，以便于重新构建新的路由。新协议提高了路由修复能力和数据包成功投递率，减少了节点间的时延，降低了路由过载。尽管如此，网络中的节点并不只有双向链路，单链路协议的优化是未来研究的目标。确认国家自然科学基金（61170147）。800070006000500040003000²00010000010²0304050607080节点数量›B–AODV控制包›Sheng Liu等/ AASRI Procedia 5（2013）2131引用[1] 李文，一种基于带域的自组织网络控制方法，北京：计算机科学出版社，2006。[2] Ankit Sggarwal，Bhumika Garg. Ad Hoc网络安全AODV路由机制研究综述。J International Journalof Advanced Research in Computer Science and Software Engineering，2012;2（3）：203- 206.[3] L. Abusalah，A. Khokhar和M.张文，安全移动自组网路由协议的研究，2001。Commun.调查图茨，2008;10（4）：78-93.[4] 宁格林拉元帅移动自组网中基于信任的轻量级路由协议。J IET信息安全，2012;6（2）：77-83.[5] 金东元无线网状网路中具方向性泛洪的有效按需路由方法。J Journal of Communications andNetworks，2010;12（1）：67-73.[6] Nakayama Hidehisa，Kurosawa，Satoshi等提出了一种基于AODV的移动自组网动态异常检测方案。J IEEE Transactions on Vehicular Technology，2009; 58（5）：2471-2481.[7] Lee Breslau，Deborah Estrin等，Advances in Network Simulation。IEEE计算机，2000;5：78-85.[8] 洪永忠，罗启良，贾礼贤。一种适用于Ad Hoc局域网的动态多信道MAC协议。在第21届两年一度的通信研讨会上。金斯顿加拿大2002;7：132-138.[9] R. Choudhary，S. Bhandhopadhyay和K. Paul.一种使用移动代理的Ad Hoc无线网络拓扑发现的分布式机制. 2000;（5）：96-101.