高速移动自组网OLSR路由协议研究与改进

图4－3表示在18个节点场景下，节点移动速度为16米/秒的性能对比情况。左边的图表示数据的传输成功率，右边的图表示数据的端到端时延；黑色曲线代表MPOLSR路由协议的性能指标，白色曲线代表经典OLSR路由协议的性能指标。从图中可以看出，OLSR单路径机制体现出来的端到端分组投递成功率在25秒之后一直保持比MPOLSR算法下的高；而端到端平均时延也是OLSR单路径的较低。考虑到信道之间的干扰，多路径路由协议并不是到处都可以行得通，尤其在节点移动速度相对较快的情况下，因此，笔者提出基于重定义MPR集的OLSR后备路由协议（SR_OLSRStandbyRouting-OLSR）：节点内部运用多重Dijkstra算法。即：第一次用Dijkstra算法，找到一条最短路径；复制一张完整的拓扑图，在该拓扑图上删除第一条路径中的所有中间节点，重新运用Dijkstra算法，找第二条最短路径……依此类推。如图4－4所示：PAGE图4－4独立节点多路径算法传统的多路径源路由协议，采用负荷均衡的方式，采取两条路径同时传输数据。基于后备路径的路由算法，根本原理上还是采用Dijkstra算法，首先，由源节点S获得S-E-K-D，S-F-K-D两条最短路径，从中任选一条S-E-K-D为第一条路径；除出中间节点E、K，再重新进行Dijkstra算法，可得到S-A-G-I-D，S-A-G-J-D，S-B-G-I-D，S-B-G-J-D，S-B-H-J-D，S-B-H-K-D，S-C-H-J-D，S-C-H-K-D八条最短路径，从中任选一条S-A-G-I-D为第二条路径；再除去中间节点A、G、I，重新进行Dijkstra算法，可得到，S-B-H-J-D，S-B-H-K-D，S-C-H-J-D，S-C-H-K-D四条最短路径，从中任选一条S-B-H-J-D为第三条路径；再除去中间节点B、H、J，重新进行Dijkstra算法，则没有剩余的路径可供选择了，这样可以轻易选择三条传输路由。由于本地链路信息库存储到达相邻节点的有关链路信息[49]，一个节点记录一个“链路数组”集合，链路数组为：（D_add,N_addr,SYM_time,ASYM_time,N_time）,其中，D_add为源节点地址；N_addr为邻居几点地址；SYM_time表示认为本条链路为对称链路的有效时间长度；ASYM_time表示能够收到本条链路上相邻节点的相邻接口上的信息的有效时间长度；N_time表示本数组有效期满时间，期满时间结束后必须删除本数组，到下一个更新周期时再重新记录该集合。参数SYM_time用来决定所声明的相邻节点接口的链路类型：如果该参数有效时间没有结束，则必须声明本条链路是对称链路；如果其有效时间已经结束，则必须声明本条链路是非对称链；如果SYM_time和ASYM_time的有效时间均已结束时，则必须声明本条链路已经丢失，这时传统的OLSR路由协议在Hello消息发送更新周期没到也得重新计算MPR和路由表，这样做势必会增大网络开销和数据传输延时。改进方案为：在发生网络断链的上游节点直接以从该节点计算出的第二条路由来传输数据。4.3仿真试验：重定义MPR集的OLSR与SR-OLSR性能对比4.3.1仿真试验场景的设置本实验测试重定义MPR集的OLSR路由算法和SR-OLSR路由算法之间的性能对比。实验场景为500×1000平方米，发包频率为10个/秒，网络通信半径设置为200米，节点平均移动速率为30米/秒。实验重点考察在网络速度增加时，重定义MPR集的OLSR路由协议和SR-OLSRPAGE协议所表现出的数据传输成功率和端到端传输时延。4.3.2试验数据图4－5表示在18个节点，移动速度为30米/秒场景下的性能比较情况。对比图3－6和表3－3，scenario_18nodetest_fastest曲线为重定义MPR集后的端到端数据传输成功率（82.5％），scenario_18nodetest_fastest_SROLSR曲线为后备路径协议仿真的端到端数据传输成功率（83.4％）。由于后备路由算法往往需要采用第二条数据通路，而第二条路径一般都是相对较复杂和多跳的路由，那么数据传输必定会受到一定的影响，其结果表现为并没提高多大的端到端数据传输成功率。注：图4－5中，曲线scenario_18nodetest_fastest，scenario_18nodetest_fastest_SROLSR分别代表节点移动速度为30米/秒情况下，重定义MPR集和基于重定义MPR集的后备路径协议在改进前后端到端数据传输成功率的实验仿真结果。图4－5SR-OLSR与重定义MPR集的OLSR数据成功率试验结果图同时，由于后备路径可以避免数据包过多的积压在节点缓冲区中，可以更及时的通过第二条路径传输出去，相比经典的OLSR路由协议重新选择路由，然后再发送缓冲区中的数据，那么后备路径算法在数据传输延时方面会有很大的降低。其结果如图4－6：注：图4－6中，曲线scenario_18nodetest_PAGEfastest1，scenario_18nodetest_fastest_SROLSR分别代表节点移动速度为30米/秒情况下，重定义MPR集和基于重定义MPR集的后备路径协议在改进前后端到端数据传输时延的实验仿真结果。图4－6SR-OLSR与重定义MPR集的OLSR数据延时试验结果图对比图3－5和表3－4，可以明显看出：网络节点移动速度在30米/秒时，重定义MPR集的OLSR数据延时基本都在0.01以上，而改进后的SR-OLSR路由协议的数据传输延时一直在0.01以下，趋向于0.005，这样的提高是明显的。所以，后备路径在利用现有链路状态路由信息的条件下，以适当的节点消耗来换取数据传输的端到端成功率提高和数据传输延时降低，这种开销是值得的。4.4结论分析路由协议是自组网络中的核心问题之一，如何使用和改进网络路由协议将直接影响到网络性能的发挥。现有多路径路由协议多是按需路由协议，针对先应式路由协议的研究则相对不足。笔者对SR-OLSR算法的仿真试验初步表明：它可在一定程度上提高网络数据的投递成功率。同时，端到端传输的平均时延性能也可以得到相应的改善。还应该注意的是：SR-OLSRPAGE对OLSR路由算法的改进是在传统的多路径方案之上讨论问题。虽然改进后的SR-OLSR路由协议在数据传输成率和传输时延都有相对的提高，但这些都是需要源节点更多的保存相邻节点和其他链路状态信息，势必会造成链路开销增加，当然，基于源路由的多路径路由协议本身就在链路开销上增加相应的控制信息，所以笔者的SR-OLSR路由协议对于MPOLSR路由协议还是得到了相应的改进和提高。同时，也的更清晰的认识到，现有的各种路由协议都是在一定的适应范围内比较有利，也就是说没有任何一种路由协议可以适用于所有的网络场景，它们所表现出来的高性能，比如，高数据传输成功率，低时延等等都是在一个相对的区间内取得的。因此，在研究无线自组网的路由协议时，有必要先认清网络状况和进行需求分析，这样选择的协议或者改进时会更加有针对性。最后还应该着重指出的是：不论是无线网络还是有线网络，不论是几层协议的网络体系结构，要使上层的协议、机制、应用发挥更好的作用，就需要注意对较低的层次进行较好的管理，采用各种机制协调好下层中各个方面的矛盾冲突，这样才能充分的利用有限的物理资源，更好地为上层提供服务。4.5改进建议4.5.1链路层对多径路由的影响移动AdHoc网络中的节点在无线媒介上进行通信，如果使用共享信道，那么相邻节点必须竞争信道[50]。当发送节点正在使用信道发送的时候，相邻节点接收到该发送而无法接收其他源节点的发送，而且，根据链路层协议，相邻节点肯能推迟发送，直到信道空闲为止。即使采用多信道，相邻节点的发送质量也可能由于干扰而下降。相互处在对方传输覆盖范围内的节点处在相同的碰撞区域内。现在考虑采用多径路由和同时采用多条路径发送数据分组，即使多条路径节点不相交，如果多条路径上的某些节点处在相同的碰撞区域内，那么多条路径上的发送仍然可能相互干扰。节点不相交性能够确保路由中断的独立性，当是却不能保证发送的独立性。因此，在选择多条路由的时候，选择的路径尽可能独立，确保相互间的干扰最低。因此，两条节点不相交路径的相关因素λ可以定义为连接这两条路径的链路的条数。如果两条节点不相交路径直接没有任何链连接着，那么相关因素λ＝0，就是说着两条节点不相交路径不相关；否则的话，如果两条节点不相交路径之间有n条链路连接着，那么相关因素λ＝n，就是说这两条节点不相交路径λ相关。PAGE还有，路径长度也是多径路由的一个重要因素。路径越长，其端到端时延越大，消耗的带宽越多。当在一个源节点－目的节点之间同时使用多条路由的时候，这些路由之间的端到端时延之差要求目的节点具有更大的缓存空间来处理顺序错乱的数据分组，那势必会加快节点能量的消耗，降低网络使用寿命。基于上述观测，移动AdHoc网络多径路由协议路径选择准则包括以下特性：=1\*GB3①节点不相交；=2\*GB3②主路由（最短路由）与备用路由之间的长度差小；=3\*GB3③任何两条路由之间的相关因素小。然而，当节点移动的时候，尤其是移动速度比较快的时候（比如本文讨论的重点，节点移动速度很快），路由相关因素也随着在不停的变化，所以，维护小相关因素特性的代价将是随着节点移动速度的加快而越来越高。4.5.2选择后备路径路由协议带来的影响本文所采用的后备路径路由算法是在多径路由协议的基础上提出的，和前面讨论的一样，每种路由协议都有它适合的网络范围和工作数据区间。由于无人驾驶飞机往往飞行速度都比较快，网络拓扑更新比较频繁，要想维护小相关因素特性的代价将是非常大的，那么采用多径路由协议传输数据必定会频繁的出现节点之间的干扰，甚至造成网络的阻塞。同时由于与高速有线网络相比，无线网络的传输速率相对较低，所以节点的存储容量应该不是一个很严重的问题，因此可以把当前的多路径信息保存在节点中，当出现链路断裂或者网络阻塞时，及时采用后备路径来传输数据，那么数据传输时延会得到很大的降低。同时，我们也不得不看到，后备路径往往相比最短路径会长一些，那么数据传输时延将会变大（但对于重新进行路径选择带来的时延会小的多，平均下来还时值得的），消耗的带宽也会越多，因此，适当的调整网络更新周期，以当前网络的阻塞情况或者基于MAC层丢包数据来适当改变HELLO消息发送频率，来自适应网络拓扑变化[53]，以求得到更加优越的网络性能。PAGE第五章工作总结与展望5.1关于使用OPNET进行OLSR协议仿真实验的体会笔者在用OPNET实现OSLR协议的实践中，借用了结构化、模块化的思想，其结果使协议实现的扩展性较好，通过合理的规划与定义函数，协调函数间的关系可以增强OLSR模拟程序的可伸缩性和可扩展性。此外，笔者在此项工作中还体会到：①OPNET仅仅是网络模拟器，在OPNET环境下的协议实现是，也仅是协议实现的模拟对象，并不能取代真实的协议实现。但是，它的确为网络协议的制订、改进提供了方便灵活的模拟协议实体行为和进行性能分析的手段。②OPNET环境下进行模拟可以回避与实际系统有关的部分细节，从而将研究重心集中在协议的主要功能上，这有助于把握住问题的主要方面。但是在实际的产品研发中，为了让系统得到稳定性，可能会在一些非常规的问题上投入大量的研究精力。这是仿真与产品开发的一个重大区别。例如，仿真协议实现时，不需要考虑涉及操作系统和系统调用的细节问题。但在真正涉及到关于实现路由协议的产品时，这些问题则往往是不可回避的。③OPNET提供了许多方便的工具，利用这些工具可以提高工作效率。例如：可以通过包格式编辑器设计数据报头的格式；可以通过进程模型编辑器实现协议的状态变迁图；可以通过相关的工具收集、查看仿真结果。所有这一切都大大减轻了仿真实验编程人员的负担，提高了工作效率。5.2OLSR协议研究工作的总结笔者主要在2个方面对OLSR路由进行了比较深入的研究，一个是基于重定义MPR集的OLSR改进方案和另一个是基于多径的后备路由算法的OLSR改进方案。这2个方案研究研究成果：=1\*GB3①PAGE基于重定义MPR集的OLSR路由协议的改进，原则上违背了选择MPR的准则：所有严格二跳节点必须至少通过一个MPR节点可达，一个节点应该将其MPR集选择得尽可能小，以便降低协议开销。同时，MPR集的冗余度影响所广播的链路数量、进行链路广播的节点的数量、以及MPR泛洪机制的效率。但是，我们必须清晰的认识到，每个路由协议都有它适合的网络体系结构，或者说都有它最大限度发挥性能的取值区间。随着网络节点密度的增加，节点移动速度的加快，传统的OLSR路由协议已经不能够满足这样的需要。由于网络拓扑更新加剧，出现链路断裂或者网络阻塞的情况就更加频繁，而网络在链路发现的时候，也会占用很大的网络资源，当数据传输不可达的时候势必会造成这些资源的很大浪费，因此，增加必要的MPR冗余度，就可以实现在网络节点高速移动时，最大限度的利用现有网络资源，使OLSR路由协议发挥更大的优越性，网络健壮性更强，更有利于高速移动自组网网络的作战体系结构。实验也表明，当节点移动速度达到30米/秒时，数据传输成功率可以提高10个百分点，而传输时延也可以得到极大的降低。因此，适当的“牺牲”网络协议开销来换取传输成功率的提高和时延的降低是值得的。=2\*GB3②基于多径路由的后备路径协议算法的提出是基于源路由的多径算法，该协议算法根本出发点是想以多条路由链路来同时进行数据传输，以达到提高数据传输吞吐率的目的。然而，由于多径路由往往会产生链路的缠绕或者信道竞争，其结果反而得不偿失。而后备路径算法是基于多路径考虑的，首先，节点通过路由协议算法保存第二条路径，也就是后备路径的地址信息，状态信息等等。当链路出现断裂或者网络阻塞时，快速切换到后备路径上来[51]，继续进行数据包的传输，这样可以避免频繁进行路径选择以此来降低数据传输时延。实验结果表明，后备路径算法在降低数据传输时延方面有极大的效率。5.3未来工作的展望网络体系结构是一个层层相互连接和作用的系统。本文的重点是放在网络层的路由算法。然而，网络层要想充分发挥其作用，往往需要上、下层之间的配合。现有的路由协议都很少考虑到底层，尤其是MAC层信息的采集和分析。比如对MAC层缓冲区数据包的丢失或者排队序列的情况分析，我们可以得到现在网络的阻塞情况，这个时候是否考虑要对网络层进行负荷均衡分担，来实现网络的健壮性的提高；由于今后的无人驾驶机PAGE群作战网络体系结构中，往往是将数据分组发送给由一个目的地址指定的一组主机，这将会是今后可能大量出现的多目标传输（Multicasting）。多目标用于面向节点组的计算。越来越多的应用必须是点对多点传输。多目标服务对于团队密切协作的应用非常重要，这点对无人机来说尤其重要，要求共享文本或图片、召开音频和视频会议。这样的好处对于需要将同一个分组发送给多个接收节点的应用，采用多目标传输技术代替采用单目标传输针对每个接收节点单独发送，链路带宽消耗最小；发送节点、转发节点的处理最少；分组交付时延最短；因而能够降低通信开销。目前笔者已经在后备路径和高速路由算法方面进行了相应的研究，对于上面提到的跨层信息和多目标路由协议是将来的研究和兴趣方向。我会在今后的学习和工作中，继续钻研，勇攀高峰。PAGE参考文献UASRoadmap2005-2030,OfficeoftheSecretaryofDefense,U.S.A.,August2005JointRoboticsProgramMasterPlanFY2005,publishedbyOUTS(AT&L)DefenseSystems/LandWarfareandMunitions,http://www.jointr-obotics.comTheNavyUnmannedUnderseaVehicle(UUV)MasterPlan,USA,April20,2000EuropeanCivilUnmannedAirVehicleRoadmapTransformationGuideLines,DepartmentofDefense,USA,April2003//曾华燊等，无人驾驶机群作战网络体系结构（结题报告），四川省网络通信技术重点实验室，2006.3T.Clausen,P.Jacquet.OptimizedLinkStateRoutingProtocol(OLSR)RFC3626-OLSR,October2003.ZhiRen,WeiGuo.

Unicastroutinginmobileadhocnetworks:presentandfuturedirections.ParallelandDistributedComputing,ApplicationsandTechnologies,2003.PDCAT'2003.ProceedingsoftheFourthInternationalConference.Royer,E.M.Chai-KeongToh.Areviewofcurrentroutingprotocolsforadhocmobilewirelessnetworks.PersonalCommunications,IEEE[seealsoIEEEWirelessCommunications].PublicationDate:April1999Helmy,A.Architecturalframeworkforlarge-scalemulticastinmobileadhocnetworks.Communications,2002.ICC2002.IEEEInternationalConference.Tchakountio,F.

Ramanathan,R.AnticipatoryroutingforhighlymobilePAGEendpoints.MobileComputingSystemsandApplications,2004.WMCSA2004.SixthIEEEWorkshop.HongJiang,Garcia-Luna-Aceves,J.J.Performancecomparisonofthreeroutingprotocolsforadhocnetworks.ComputerCommunicationsandNetworks,2001.Proceedings.TenthInternationalConference.Borgia,E.ExperimentalEvaluationofAdHocRoutingProtocols.PervasiveComputingandCommunicationsWorkshops,2005.PerCom2005Workshops.ThirdIEEEInternationalConference.deMoraisCordeiro,C.

Gossain,H.

Agrawal,D.P.，Multicastoverwirelessmobileadhocnetworks:presentandfuturedirections.Network,IEEE,PublicationDate:Jan.-Feb.2003.K.Bharath-Kumar,J.M.Jaffe.Routingtomultipledestinationincomputernetworks.IEEETransactiononCommunications.1983S.E.DeeringandD.R.Cheriton.MulticastRoutinginDatagramInternetworksandExtendedLANS.ACMTransactiononComputerSystems.vol8.May1990V.ChikarmaneandC.L.Williamson.Performanceevaluationofthemommobilemulticastprotocol.MobileNetworksandApplications.1998于宏毅等.无线移动自组织网.人民邮电出版社.2005郑相全等.无线自组网技术实用教程.清华大学出版社.2004Sung-JuLeeSu,W.Hsu,J.Gerla,M.Bagrodia,R.，Aperformancecomparisonstudyofadhocwirelessmulticastprotocols.INFOCOM2000.NineteenthAnnualJointConferenceoftheIEEEComputerandCommunicationsSocieties.Proceedings.IEEEVaishampayan,R.Garcia-Luna-Aceves,J.J.，Efficientandrobustmulticastroutinginmobileadhocnetworks.MobileAd-hocandSensorSystems,2004IEEEInternationalConference姜河.Adhoc组播路由协议研究与仿真.Biswas,J.Barai,M.Nandy,S.K.，Efficienthybridmulticastroutingprotocolforad-hocwirelessnetworks.LocalComputerNetworks,2004.29thAnnualIEEEInternationalConferenceMauve.MWidmer.AHartenstein.H，Asurveyonposition-basedroutinginmobileadhocnetworks.Network,IEEEPublicationDate:Nov.-Dec.PAGE2001Stojmenovic,I.，Position-basedroutinginadhocnetworks.CommunicationsMagazine,IEEE,PublicationDate:July2002R.Jain,A.Puri,R.Sengupta.，GeographicalRoutingUsingPartialInformationforWirelessAdHocNetworks.IEEEPers.Commun.,Feb.2001,pp58-57J.Lietal.，AScalableLocationServiceforGeographicAdHocRouting.Proc.ACMMOBICOM2000,pp.120-30S.Capkun,M.Hamdi,J.Hubaux，Gps-freePositioninginMobileAdHocNetworks.Proc.HawiiInt’l.Conf.SystemScience,Jan.2001Lochert,C.Hartenstein,H.Tian,J.Fussler,H.Hermann,D.Mauve,M.，Aroutingstrategyforvehicularadhocnetworksincityenvironments.IntelligentVehiclesSymposium,2003.Proceedings.IEEEShigangChenNahrstedt,K.，Distributedquality-of-serviceroutinginadhocnetworks.SelectedAreasinCommunications,IEEEJournalonPublicationDate:Aug.1999刘元安,唐碧华,胡月梅.Adhoc网络中的路由算法.北京邮电大学学报2004年4月Rubin.ILiu.Y-C.，LinkstabilitymodelsforQoSadhocroutingalgorithms.VehicularTechnologyConference,2003.VTC2003-Fall.2003IEEE58thSu,W.Lee,S.-J.Gerla,M.，Mobilitypredictioninwirelessnetworks.MILCOM2000.21stCenturyMilitaryCommunicationsConfere