高效路由（共7篇）
高效路由 篇1
机会网络 (opportunistic networks) [1,2,3]是一种特殊的自组织网络, 能够在源节点与目的节点之间路径不存在的情况下, 通过节点对数据的“存储-携带-转发”操作来完成数据传送。由于机会网络在网络拓扑发生分割时仍能保持有效的数据传输, 目前已成为移动ad hoc网络 (Mobile Adhoc NETworks) 技术的一个重要发展方向。
节点的地理位置信息是一种可帮助网络路由的有用信息, 如果对其加以合理有效的使用, 能够提升路由性能。目前, 已存在一些可用于移动ad hoc网络的基于地理位置信息的路由算法[4,5,6,7,8], 其中具有代表性的算法有LAR (Location-Aided Routing) [4], GLS (Grid Location Service) [5], LOTAR (Location Trace Aided routing) [6], GPSR (Greedy Perimeter Stateless Routing) [7], DREAM[8]等。这类算法要求每个节点都携带有定位装置 (如GPS) , 节点通过利用目的节点和邻居节点的地理位置信息, 提高找路的效率, 有利于路由发现和维护。但是目前这些算法难以直接应用于机会网络, 其原因在于当源节点到目的节点的路径出现断裂时, 这些算法的性能就会下降;而且它们的周期性地理位置信息发布机制开销偏大。在本文中, 针对现有的基于位置的移动ad hoc网络路由算法不适应机会网络中路径断裂的情况和发布地理位置信息开销偏大的问题, 提出了一种基于地理位置信息的机会网络路由新算法, 通过优化数据分组发送策略, 使其在源节点和目的节点之间出现断路时仍能保持有效的数据传输能力;并通过加入位置预测机制减少地理位置信息分组的发送, 提高地理位置信息的准确性。
本文后面部分安排如下:第1节介绍相关工作;第2节详述提出的新算法, 第3节对所提算法进行仿真验证;第4节总结全文。
1 相关工作
基于地理位置信息的ad hoc路由算法能够利用节点的地理位置信息辅助进行路由的发现和维护, 提高寻路的方向性和效率, 因此近年来受到人们的关注。基于地理位置信息的ad hoc路由算法根据路由发现策略不同大致可分为两大类:反应式路由算法和先应式路由算法。其中代表性的反应式路由算法有LAR[4]算法和GLS[5]算法。LAR[4]算法在路由发现过程中, 源节点通过利用目的节点地理位置信息确定目的节点期望区域, 然后根据自己的当前位置确定请求区域, 发起路由请求, 其他节点收到请求分组后, 根据分组中携带的请求区域判定是否转发该请求, 以此控制路由查询范围, 提高路由查询效率。GLS[5]是一种分层路由算法。该算法将整个网络按等级划分为栅格, 节点在一级栅格内采用周期的两跳地理位置信息分组与邻居节点保持联系, 一级栅格外通过在各级栅格选取的节点作为位置服务器, 以便进行地理位置信息更新及查询。当节点要发送数据时, 根据邻居的地理位置信息采用贪婪机制转发数据。基于地理位置信息的先应式路由算法主要有LOTAR[6]算法, GPSR[7]算法和DREAM[8]算法等。LOTAR[6]是一种位置踪迹辅助路由算法;该算法路由发现机制与LAR相类似, 但当某条路径断裂时, 该算法并不是由源节点发起路由发现过程, 而是找一个有目的节点最新地理位置信息的节点, 由该节点发起路由发现过程;如果再次失败, 则由源节点发起路由发现过程。同时, 在LOTAR中, 节点可以通过监控链路情况来预测链路的生存期, 以便提前进行路由发现过程, 从而降低丢包的可能。但该算法周期性地发布地理位置信息使得开销偏大。GPSR[7]是一种贪婪型的路由算法, 该算法不需要维护路由表。当节点需要发送数据时, 利用地理位置信息把数据分组发给离目的节点最近的邻居, 如果出现局部优化问题, 则采用边界转发机制。但在该算法中遇到的空洞问题目前还没有很好的解决方案。DREAM[8]是一种定向泛洪路由算法, 该算法周期性地广播地理位置信息, 使得网络中每个节点都能获得其他节点的地理位置信息, 其中地理位置信息的发送周期和转发距离根据源节点的移动速度而设定;在数据转发过程中, 源节点利用地理位置信息, 计算到目的节点的期望区域的角度, 得出一个扇形区域, 然后把数据转发给处在该扇形区域的所有一跳邻居节点, 邻居节点收到数据后也采用相同的机制转发数据, 直到数据到达目的地。BFDREAM[9]是对DREAM算法的改进方案;当节点需要发送数据时, 节点在一跳范围内广播数据分组, 其他节点收到后, 根据自己当前位置和数据分组携带的关于上一个转发节点和目的节点的地理位置信息, 判断是否处于转发区域, 并决定是否转发该数据分组, 以此使得不在转发区域内的节点不参与数据的转发。
由上述内容可知, 对于现有基于位置的ad hoc路由算法 (尤其是先应式算法) , 当源节点到目的节点的路径不存在时, 算法的性能会因为无法确定下一跳节点而下降, 因此不能适应拓扑间断/部分连接的机会网络环境, 需要加以改进。
2 LBRON路由算法
针对现有的基于位置的移动ad hoc网络先应式路由算法不适应机会网络中路径断裂的情况和发布地理位置信息开销偏大的问题, 提出一种基于地理位置信息的机会网络路由算法LBRON (Location-Based Routing for Opportunistic Networks) ;它由逻辑上相互独立的地理位置信息发布机制和数据传输机制两部分组成。以下做具体介绍。
2.1 算法操作
LBRON算法由节点地理位置信息发布和数据传输两个交替出现的阶段内的操作组成。
(1) 地理位置信息发布阶段
此阶段包括2个步骤, 具体如下:
(1) 初始化时, 每个节点都在全网范围内广播自己的地理位置信息, 并且保存发送的内容, 以便此后采用预测机制按需地发送地理位置信息。
(2) 当节点收到其他节点的地理位置信息后, 更新自己的地理位置信息表和邻居表, 然后根据自己所处的位置判断是否转发该地理位置信息分组。
(2) 数据传输阶段
当节点收到来自应用层或其它节点转发来的数据的时候, 选取比当前节点更靠近目的节点的邻居作为转发节点, 向它们转发数据分组, 然后结束;如果出现路径断裂, 则保存数据分组到缓存队列, 并且当邻居表发生变化, 查找缓存队列, 发送目的地是自己邻居的数据分组。
2.2 地理位置信息按需发布机制
LBRON算法使用了一种新的按需启动的地理位置信息发布机制。节点发送的地理位置信息分组中包括的主要内容如表1:
当需要利用Source节点的地理位置信息时, 可以通过式 (1a) (1b) 计算出Source节点的当前位置:
其中Tc为当前时刻, Xp, Yp为通过预测计算出来的Source节点在Tc时刻所处的位置。
初始化时, 节点全网范围内广播自己的地理位置信息分组, 并保存该地理位置信息, 此后节点利用保存的地理位置信息周期性的对自己的位置进行预测, 预测方法如式 (1a) (1b) , 当预测值和自己真实位置的误差值大于门限值AER (Acceptable Error Range) [10]时, 节点就重新广播自己的地理位置信息, 并重新保存地理位置信息。误差值的计算公式如下:
其中Xc, Yc为Tc时刻节点真实的位置。
当节点收到新的地理位置信息分组后, 具体处理方法如下:
(1) 利用地理位置信息分组更新地理位置信息表和邻居表, 并通过地理位置信息表查找转发节点的地理位置信息, 如果没有转发节点的地理位置信息, 则直接转发该分组。如果有, 则执行步骤2。
(2) 当前节点通过转发节点地理位置信息计算出转发节点的当前位置, 并把以转发节点的当前位置为中心的通信范围划分为6个等大的扇形区域, 从而确保处在同一扇形区域的节点都在彼此的通信范围内。然后当前节点确定自己所处的扇形区域, 并通过邻居表计算是否有邻居的当前位置和自己处在同一扇形区域, 如果没有, 则当前节点转发该分组, 否则从这些邻居中找出当前位置最靠近本扇形区域弧形边界中心的节点, 如果该节点比当前节点更靠近弧形边界的中心, 则当前节点丢弃该分组, 否则转发该分组。具体过程如图1:
当前节点B收到节点S发的地理位置信息分组后, 通过地理位置信息表计算出和自己处在同一扇形区域的节点N更靠近弧形边界的中心M点, 节点B就丢弃该分组, 不再转发。
2.3 数据分组携带机制
在LBRON算法中, 当节点发现路径断裂时, 节点就携带数据分组, 缓存该数据分组到缓存队列, 此后当节点发现邻居表发现变化时, 节点就查找缓存队列, 发送目的地是自己邻居的数据分组。
2.4 算法关键参数设置
(1) AER门限值
AER门限值表征位置的预测值和真实值之间允许的最大误差, 它影响地理位置信息的准确性和位置信息分组的发送次数。LBRON算法将AER门限值设置为:
其中R表示节点的通信半径。
(2) 自身位置预测周期TL
节点需要周期性的检测自己的预测位置和真实位置的误差值是否大于AER。AER和节点相对运动速度决定了从节点改变运动速度到触发AER所需的时间。因此设置TL如下:
3 仿真分析
3.1 仿真参数设置
本文使用的仿真平台是OPNET, 仿真过程中共有25个可自由移动的节点, 每个节点都产生数据分组, 数据分组大小为1024bytes, 并随机选取另外24个节点作为数据分组的目地。每个节点从仿真第5s时开始产生数据分组, 数据分组产生间隔为1s, 共产生24个。节点运动模型采用Community model[11], 节点移动速度为1-20m/s, 节点运动间歇时间为0s。网络场景为1 000m×1 000m, 节点通信范围为100m-200m。MAC和物理层采用IEEE802.11b标准, 数据传输速率为5.5Mbit/s。仿真时间为800s。仿真中为了尽可能在相同的仿环境下验证算法的性能, 统一设置AER, TL的值如下:
其中V为节点之间平均相对运动速率, 大小为V= (0+20×2) /2=20m/s。
3.2 仿真结果分析
通过仿真分析比较L B R O N算法和D R E A M, BFDREAM算法在数据分组传输成功率, 端到端时延, 地理位置信息分组开销等方面的性能。
3.2.1 数据分组传送成功率
从图2中可以看出LBRON算法的成功率要高于其他两种算法, 这是由于并且当源节点到目的节点路径不存在时, LBRON算法采取了数据携带的机制, 降低了丢包的可能。在DREAM和BFDREAM算法中都没有设计应对源到目的地的路径不存在的机制, 所以当源节点到目的节点路径不存在时, 就会出现丢包, 导致数据分组传送成功率下降。
3.2.2 平均端到端时延
从图3中可看出, 当源节点到目的节点路径存在时, LBRON算法的分组端到端时延要远小于DREAM算法和BFDREAM算法。在LBRON算法中, 通过确定目的节点和邻居节点的准确位置, 采用类似贪婪机制传输数据分组, 缩短了传输路径, 降低了时延。而在DREAM和BFDREAM算法中, 由于地理位置信息不准确, 只能通过定向泛洪的方式传输数据分组, 并且在数据分组传输失败后, 还要采用恢复机制重传数据。上述原因使得LBRON算法的时延要明显小于其他两个算法。
3.2.3 地理位置信息发布开销
LBRON算法中地理位置信息分组的结构不同于其他两个算法, LBRON算法和其他两个算法地理位置信息分组的大小分别为为81bit, 56bit, 56bit。从图4中可以看出, LBRON算法的地理位置信息总比特数要远少于其他两个算法。在LBRON算法中, 采用了预测机制按需的发送地理位置信息分组, 并且在转发时, LBRON算法只是选择部分邻居节点参与地理位置信息分组的转发;而在其他两个算法中, 节点只是简单的通过移动速率确定地理位置信息分组的发送周期和最大传输距离, 并且在转发地理位置信息分组时, 所有邻居都参与转发。以上原因使得LBRON算法的地理位置信息总比特数少于其他两个算法。
4 结束语
在本文中所提算法中, 通过预测机制按需的发布地理位置信息, 并且在发送数据时选取更靠近目的节点的邻居作为下一跳, 若满足条件的邻居不存在时则携带数据直到遇到合适的目的地节点, 以达到减少控制开销, 提高数据传送成功率的目的;并通过仿真验证了所提算法的有效性。
参考文献
[1] Liu C and Wu J.On multicopy opportunistic forwardingprotocols in nondeterministic delay tolerant networks, IEEE transactions on parallel and distributed systems, 2012, 23 (3) :1121~1128
[2] Stavroulaki V, Tsagkaris K, Logothetis M, et al.Opportunisticnetworks[J].IEEE vehicular technology magazine, 2011, 6 (3) :52-59
[3] Erdogan M, Gunel K, Koc T, Sokun H, Dag T, Routingperformance analysis of opportunistic networks withflooding and partial flooding methods, in signal processingand communications applications conference (SIU) , 2012, 20, 1-4, Mugla, Turkey, Apr.18-20
[4] Ko Y B, Vaidya N H.Location-aided routing (LAR) in mobilead hoc networks[J].Wireless networks journal, 2000, 6 (4) :307-321
[5] Li J Y, Jannotti J, Douglas S J.A scalable location servicefor geographic ad hoc routing[C]//MOBICOM 2000.Boston:ACM Press, 2000:202-213
[6] Wu K, Harms J.Location trace aided routing in mobile adhoc networks[C]//ICCCN 2000.Las Vegas:IEEE Press, 2000:354-359
[7] Zayene M A, Tabbane N, Elidoudi R.Performanceevaluation of greedy perimeter stateless routing protocolin Ad Hoc networks, Computer sciences and convergenceinformation technology, ICCIT‘09.Fourth internationalconference on, Seoul, Korea, 2009:907~912
[8] Basagni S, Chlamtac I, Syrotiuk V R, et al.A distancerouting effect algorithm for mobility (DREAM) [C]//MOBICOM 2000.Dallas:ACM Press, 1998:76-84
[9] Hu H N, Liu Z, Yang B.BFDREAM:A new routing protocolfor deep sea acoustic network[C]//ICSP 2010.Beijing:IEEE Press, 2010:2377-2381
[10] Chen Q J, Kanhere S S, Hassan M.Adaptive positionupdate in geographic routing[C]//ICC 2006.Istanhul:IEEEPress, 2006:4046-4051
[11] Lindgren A, Doria A, Schelen O.Probabilistic routing inintermittently connected networks[J].Lecture notes incomputer science, 2004, 3126:239-245
高效路由 篇2
发布/订阅系统[1]在信息生成和接受两者间具有弱耦合、非同步及多点通信的特点,成为很多网络应用的一种重要组件[2],尤其适用于具有动态拓扑特性的移动Ad hoc(自组织)网络。
针对移动Ad hoc网络中基于位置的发布/订阅路由算法,目前已有一些研究。文献[3]提出了一种STEAM(基于附近和分布式过滤的区域事件转发群组算法),在该算法中,订阅节点只订阅附近发布方的内容。这导致只能在发布内容时分发内容给目标区域内的节点,限制了内容的发布与匹配。文献[4]提出了INGEO(基于内部地理位置的路由协议)算法,该算法以速度位移矢量来重新定位移动的订阅节点。文献[5]提出了基于位置的自适应路由算法,在合理的区域内实现内容的分发和匹配。但该算法较少考虑节点的移动性,以节点的请求频次计算的结果因节点频繁移动而不准确,并且所有节点的区域频繁更新所带来的开销很大。文献[6]提出的Courier算法(基于位置感知的有效群组通信算法),类似源路由算法LGS(以位置为导向的小区多播生成树算法)[7],订阅节点将速度位置信息嵌在Hello包内,再转发至内容发布方,依靠订阅节点及时更新信息,发布方计算发布内容所需转发的路径转发树和受限泛洪区域的大小,实现目标区域节点的内容匹配。基于上述分析,以Courier算法为代表的基于位置感知的路由算法对于位置速度信息的更新要求频繁,且Hello包存在冗余广播问题。本文在文献[6]的基础上提出一种EPRLM(基于位置感知的移动Ad hoc网络高效发布/订阅路由算法)。本文的主要贡献有:(1)在内容消息接收过程中,节点通过计算自身是否移出区域来判断是否更新位置速度信息,从而减少了不必要的控制数据包转发;(2)订阅节点的回应包可以捎带之后的Hello包信息,减少了冗余Hello包的广播。
1 网络模型与问题描述
1.1 网络模型
定义1(节点转发区域)如图1所示。在t1时刻,源节点srcA收到订阅节点memB的位置更新信息;在t2时刻(t2>t1),srcA发送数据给memB;memB在t1~t2这个时间段内能够移动的范围是以srcA存储的memB位置为中心、半径为VB(t2-t1)的圆形区域,即NFZ(节点转发区域)。
定义2(群组转发区域)如图2所示。srcA发布内容给多个订阅节点时,需要优化转发区域。首先srcA降序排列订阅节点的NFZ大小,然后判断NFZC和NFZB的关系。如果二者相交,并且半角α1小于阈值[6],则合并两区域;如果两区域中的一个区域包含另一区域,则将其合并为一个区域;如果两区域并不包含或者相交,但是半角α1小于阈值[6],则合并两区域。至此,形成GFZ(群组转发区域)。
定义3(欧几里德Steiner树)如图3所示。A、B和C为网络中的3个节点,S为欧几里德Steiner节点(即网络中的虚拟中继节点)。节点A发送给B和C的总的开销,可以经过S(实际中也可以是S的附近节点)再分别分发至B和C。而对于多个订阅节点的GFZ,此时可以通过迭代计算出适合的欧几里德Steiner树。
1.2 问题描述
以Courier算法为代表的基于位置感知的路由算法存在以下问题:
(1)位置速度信息需要通过Hello消息频繁更新。而在节点没有离开NFZ时,上次更新的信息依然可以将内容转发至此区域,并实现区域泛洪,使得节点收到此发布内容。此时,更新导致冗余开销。
(2)在订阅节点回应源节点的请求包(Join Request)时,回应包(Join Reply)和之后一次的Hello包所起作用重复,产生冗余。
2 EPRLM
EPRLM采用基于NFZ的信息更新以及Join Reply包的捎带等新机制,从而达到内容消息与订阅节点的高效匹配,降低控制开销的效果。
2.1 EPRLM新机制
2.1.1 基于NFZ的信息更新机制
Courier算法只考虑了订阅节点位置速度信息改变后,通过Hello消息通知发布节点。但是,如果订阅节点在接收内容消息时并没有移出NFZ,此时内容消息已经在转发的路径上,那么此次位置速度信息的更新就不会起作用,发布节点基于上次的位置速度信息依然可以将消息泛洪至订阅节点。因此,订阅节点在接收内容消息时,位置速度信息如果发生变更,首先判断订阅节点自身是否移出上次位置速度信息更新到目前为止的NFZ。如果已经移出,则通过Hello包更新位置速度信息,否则,在位置速度信息失效前不再更新。
通过基于NFZ的信息更新,可以减少频繁转发至发布节点的信息更新Hello包,从而减少网络的控制开销,减缓网络的通信负荷。
2.1.2 Join Reply包的捎带机制
在Courier原算法中,订阅节点收到发布节点的请求包Join Request时,需要回应Join Reply包;并且在回应包到达发布节点的过程中,对应路径上的节点须转发此消息。此后,产生或转发回应包的节点需要广播Hello包告知邻居节点自己的状态信息,而该Hello包的信息与先前回应包的信息重合,产生冗余。本算法提出了Join Reply包的捎带机制,改变Join Reply包的消息类型并在转发时广播此消息,此时除转发至发布节点路径上的节点需要继续广播此包外,其余节点收到Join Reply包后将其当作Hello包提取信息。
Join Reply包的捎带机制将订阅节点至发布节点路径上所有节点的一次Hello包广播的信息由Join Reply包捎带完成,降低了冗余控制开销,减少了信道资源的竞争。
2.2 算法操作
EPRLM的主要操作步骤如下:
(1)发布节点周期性全网泛洪Join Request包(包含发布节点ID、位置及内容摘要等信息)。
(2)节点收到Join Request包后,如需要发布节点所拥有的内容,则回复Join Reply包(包含该节点ID、位置和速度等信息)并在转发时广播此消息,此时除转发至发布节点路径上的节点需要继续广播此包外,其余节点收到Join Reply包后将其当作Hello包提取信息。
(3)节点收到Join Request包后,如不需要发布节点所拥有的内容,则继续广播此消息。
(4)发布节点在发布内容时,首先根据订阅节点的位置速度信息计算各个订阅节点的NFZ,再生成GFZ,然后依次迭代计算出抽象的欧几里德Steiner树,并依此树的虚拟路径分发内容消息至订阅节点。
(5)订阅节点的位置速度发生变化需要更新时,首先判断订阅节点自身是否移出上次位置速度信息更新到目前为止的NFZ。如果已经移出,则通过Hello包更新位置速度信息;否则,在位置速度信息失效前不再更新。
3 仿真
本文使用OPNET[8]作为仿真软件平台,选取LGS算法和Courier算法作为与EPRLM进行比较的对象,在相同仿真条件下(仿真参数设置如表1所示)分析比较3种算法的消息传送成功率、消息端到端时延、内容消息转发次数和控制包开销等性能。其中,实际的消息端到端时延等于平均跳数乘以每一跳的平均转发时间,而每一跳的平均转发时间依赖于具体的硬件条件;内容消息转发次数为内容消息成功到达所有订阅节点所需转发的总次数。
(1)消息传送成功率
3种算法的消息传送成功率仿真结果如表2所示。从表中可以看出,EPRLM的消息传送成功率高于Courier和LGS算法,这是因为基于NFZ的信息更新机制减少了Hello包的产生和转发,而且此时减少的Hello包原本是沿着与内容消息传播的反方向路径转发的,由此减少了冲突和资源竞争。同样,Join Reply包的捎带机制也降低了信道中资源的竞争。
(2)消息端到端时延
3种算法的消息端到端时延仿真结果如图4所示。由图可见,EPRLM的消息端到端时延低于Courier和LGS算法,这是因为EPRLM中基于NFZ的位置信息更新机制减少了Hello包的数量,降低了与反方向路径内容消息的转发而产生的信道和资源竞争,减少了同一路径上转发消息的负担;另外,Join Reply包的捎带机制同样降低了信道中资源的竞争。平均跳数随网络中节点数目增加而减少的原因是:在密集网络中发现源节点到目的节点之间最短路径的概率会更高一些。
(3)内容消息转发次数
在不同节点数时3种算法的内容消息转发次数比较如图5所示。从图中可以看出,随着节点数的增多,3种算法的内容消息转发次数都是递增的。EPRLM的内容消息转发次数比其他两种算法低,主要是因为EPRLM的两种新机制减少了Hello包的产生和转发,减少了信道资源的竞争和冲突,因而减少了内容消息转发次数。
(4)控制包开销
图6给出了不同节点数下3种算法的控制包开销的比较。由图可见,相对于Courier和LGS算法,EPRLM在不同节点数下的控制包开销都是最少的,这是因为基于NFZ的位置信息更新机制和Join Reply包的捎带机制都减少了Hello包的产生和转发,且减少的冲突和资源竞争带来的控制包开销的降低也很可观。
4 结束语
针对结合地理位置信息的发布/订阅内容路由算法中节点频繁更新位置信息和控制包存在冗余的问题,本文提出了EPRLM。仿真验证表明,与Courier和LGS算法相比,EPRLM能够很好地提高网络中节点的消息传送成功率,并降低网络吞吐量,减少消息时延和发送次数,降低控制开销。
参考文献
[1]Carzaniga A,Rosenblum D S,Wolf A L.Design and evaluation of a widearea event notification service[J].ACM Transactions on Computer Systems,2001,19(3):332-383.
[2]Rezende G C,Rocha B,Loureiro A.Publish/subscribe architecture for mobile ad hoc networks[C]//Proc of the ACM Symposium on Applied Computing2008.Fortaleza,Brazil:ACM,2008:1913-1917.
[3]Rene M,Vinny C.On event-based middleware for location-aware mobile applications[C]//IEEE Transactions on Software Engineering 2010.Los Alamitos:IEEE,2010,36(3):409-430.
[4]Hai L,Houda L.INGEO:indoor geographic routing protocol for MANETs[C]//In Proceedings of the 3rd International Conference on Mobile Computing and Ubiquitous Networking 2006.San Jose:ACM,2006:224-229.
[5]Holzer A,Eugster P,Garbinato B.ALPS-Adaptive Location-based Publish/Subscribe[J].Computer Networks,2012,56(12):2949-2962.
[6]Mitra P,Poellabauer C.Efficient group communications in location aware mobile ad-hoc networks[J].Pervasive and Mobile Computing,2012,(8):229-248.
[7]Chen K,Nahrstedt K.Effective location-guided tree construction algorithms for small group multicast in MANET[C]//In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies 2002.New York:IEEE,2002:1180-1189.
高效路由 篇3
如图1(a)所示,是4X4 mesh型拓扑结构的NOC,主要由通信节点和资源节点组成。每个IP核为一个资源节点,通过网络接口与一个通信节点(switch)互联,资源节点之间通过发送和接收数据包的方式进行通信。数据包由一个个数据微片构成。每个数据包从源节点到目的节点的通信链路有很多条,数据包通过每条链路所需要的时间各不相同。特定的路由技术不仅为数据包的传送选好路径,还决定了switch的工作状态。图1(b)所示为switch的结构图,它是由n+1条输入沟道(input channel,IC)和n+1条输出沟道(output channel,OC)通过交叉开关(crossbar)连接而成。Switch中需要植入一定的路由算法,才能使数据包在网络中传输。而这个路由算法由两大部分组成:输出选择和输入选择。一个数据包从某个IC流入,可以从多个OC中流出。例如,从IC_0中流入的数据包p0可以从输出沟道OC_0,OC_1等等中流出。这时,输出选择就决定了数据包具体选择哪一条OC输出。同样的,可能有多个输入沟道IC请求通过某一条输出沟道OC进行数据包输出。例如,IC_0中数据包p0和IC_1中数据包p1同时请求从OC_0中输出。这时,输入选择就需要选出具体是哪一条输入沟道IC获得选通权。
先前的很多工作[4,5]都是研究输出选择对路由效率的影响。该文提出一种新的基于阻塞程度的输入选择机制(block-level input selection,BLIS)。该机制可以使链路通信变的流畅,提高通信效率。实验研究表明,与传统的先到先得(first come first served,FCFS)输入选择机制相比,该机制不论是与自适应性输出选择还是与确定性输出选择结合使用,都大大降低了传输延迟。
1 基于阻塞程度的输入选择机制
先前已有先到先得(FCFS)[4]输入选择机制应用于NOC中,FCFS的输出沟道给了请求最早的输入沟道,因此所有输入沟道的优先级都是等同的,然而这种输入选择并没有考虑实际网络通信情况。本节提出一种不同阻塞程度下灵活选择输入沟道的输入选择机制。
1.1 输入选择机制
为了说明输入选择和输出选择对路由效率的影响,现在考虑如图2所示的一组通信节点网络,为了简单起见,IP核没有画出。
通信节点Switch颜色的灰暗程度表示其中等待的数据包数量。随着颜色的加深,switch中等待的数据包数量逐渐增多。白色的switch中等待的数据包数量最少,灰色有比白色要多,黑色的switch如节点(2,2),表示其中等待的数据包数量最多。为了证明输出选择对路由效率的影响,现在考虑数据包p0从节点(3,0)起始,传送到节点(0,2),现有多条路径可以选择,例如path1,path2。传输延迟较少的路径需要避开阻塞区域(如图中灰色和黑色的switch区域),所以path1与path2相比,延时较少,路径较优。这就证明了输出选择对路由效率的影响,一条合适的路径可以减少链路时延。现在考虑输入选择的影响,节点(3,2)处的数据包p1和节点(4,3)处的数据包p2同时想通过节点(3,3)。在这种情况下,较好的选择是让p1通过节点(3,3),因为节点(3,2)处比节点(4,3)处等待的数据包要多,网络阻塞程度要高。这样的选择将会降低阻塞更严重区域中等待的数据包数量,降低网络阻塞,进而提高NOC的性能。由此,该文提出一种基于阻塞程度输入选择机制(block-level input selection,BLIS)。
BLIS的基本思想是赋予输入沟道不同的优先权来选通输出沟道,而输入沟道的优先级是在通信过程中基于上流switch阻塞程度动态授予的。精确的来说就是通信节点中每个输出沟道根据当前switch中输入沟道的输出请求次数,得到一个BL(block level)值,然后把得到的BL值(即为输出请求次数)传送给下路相邻switch对应的IC,再根据所得BL的值来断定下路相邻switch中对应IC的优先级别。当某个通信节点中,同时有多个IC请求同一个OC输出时,BL最大的IC优先级最高,优先被选通。
图3作出了含有BLIS的switch结构图,可以看出该switch除了含有用来传输数据的连接线,还额外包括用来传送相邻switch BL的连接线。该switch共有n+1条IC和n+1条OC,每个IC中还有一个缓存(buffer),那些即将到来的数据包微片在还没送到某个OC之前,就暂时存放在buffer中。输出选择(OS)模块根据数据包的头微片,决定整条报文从哪个OC中输出。OS模块将输出请求发送到对应的OC。一旦某个OC空闲,OC中的BLIS模块就会检查所有的输出请求并发送一条选择信号给MUX模块,MUX模块再将获得许可的输入数据输出。如果只有一条输出请求,那么那条数据可以直接传送。如果有多条请求,则需考虑此刻具体哪个请求可以被选通。这个选择机制接下来做详细介绍。
2.2 BLIS算法伪代码
BLIS根据输入沟道BL的大小作出选择,输入沟道BL的取自上流相邻switch输出沟道的BL。上流switch输出沟道的BL是特定时刻收到输入沟道传送请求的次数。
图4为该输入机制算法的VHDL伪代码,它包括了两个并行的进程。当req_0...n变化时,进程observe_BL被激发,它根据当前第i个输出沟道收到的请求次数,将BL值赋予out_BL_i。接着BL值被传送到下流相邻switch中对应的第i个输入沟道并用于输入选择。例如,考虑图3所示的switch,IC_0和IC_1同时请求OC_0,则out_BL_0的值就是2,下流相邻的switch的in_BL_0的值也是2。为了避免高复杂性和硬件消耗,BL值传送到下一个相邻的switch中就截止,不会继续向更远的switch传送。例如先前的例子,IC_0的in_BL_0的值为3,IC_1的in_BL_1值为4,IC_0和IC_1同时请求OC_0,OC_0中out_BL_0值不是3+4而是2。当有输出请求且输出沟道空闲时,select_input进程被激发。它比较所有的输出请求及对应的输入沟道BL的值,选择BL值最大的作为输出。
对于那些与IP核相连的输入沟道,它们没有上流switch传送BL给它们。这些输入沟道的BL值默认设置为0,因此,网络中所有正在传送的数据包优先级都高于IP核中正在等待注入网络的数据包。
2 实验结果
该文设计了一系列实验来评估BLIS的性能,并与传统的FCFS输入选择做了对比。两种输入选择分别与确定性路由输出(XY路由[6])和自适应性路由输出(OE路由[7])结合使用,并用VHDL实现了四种路由模型:XY+FCFS,XY+BLIS,OE+FCFS,OE+BLIS,四种模型都在6X6 mesh NOC上做了仿真。由先前的工作[4,9]可知,路由算法的性能的主要是通过传输延迟来评估的。在给定的注入率(在一个周期内注入网络的数据包数)下,我们测量每个数据包的平均传输延迟。一个数据包的传输延迟时间是指从源节点数据包的第一个微片产生开始到最后个微片送进目的节点后所持续的时间。所有的仿真都是基于50,000个数据包求平均的。考虑到网络的稳定性,在头5000个周期内传输延迟不作计算。假定,数据包的固定长度是5个微片,输入沟道的buffer深度也是5个微片。将该文的路由算法应用到三种不同的通信模式上:普通(uniform)模式,对调(transpose)模式,热点(hot spot)模式[7]。在普通模式下,每个IP核随机的发送数据包去另一个IP核。在对调模式下,节点(i,j)IP核发送数据包去节点(5-i,5-j)IP核。在热点模式下,节点(3,3)IP核被设为热点,它比在普通模式下收到的数据包数量要高出10%。
图5显示了在普通模式下四种路由算法的性能。X轴代表的是每个节点的注入率,Y轴是数据包平均延迟。由图可得,在低注入率下(<0.038包/周期),四种路由算法的性能几乎相同。随着注入率的增大,由于网络变的阻塞,包传输延迟急剧上升。比较OE+FCFS和OE+BLIS特性曲线可得,在OE输出选择下,BLIS性能优于FCFS。同样的比较XY+FCFS和XY+BLIS特性曲线可知,在XY输出选择下,BLIS性能更优。在[4,7]中曾经说明XY路由算法比OE路由算法性能要优,这是因为在普通模式下,XY算法综合了全局和长远的负载信息,从而使网络的负载分配变的平稳。而OE算法基于的是局部短期的负载情况,只是对当前的数据包特性敏感,对于长久的通信缺乏平稳性。
图6显示了在对调模式下四种算法的性能。由图可知,在结合使用XY算法下,FCFS算法和BLIS算法性能几乎相同。在结合OE算法,FCFS算法的性能稍稍优于BLIS算法的性能。这是因为在对调通信模式下,很少出现多个输入同时请求一个输出的情况,从而输入选择对整个路由算法的性能影响很小。图7是在热点模式下四种算法的性能体现。不论是结合XY输出选择还是OE输出选择,同样可以得出BLIS算法的性能要优于FCFS算法的性能。此外,尽管在FCFS输入选择下,OE算法比XY算法性能要差。但在BLIS输入选择下,OE算法的性能却比较接近XY算法的性能。
以上实验均证明了输入选择的重要性。该文设计的BLIS输入选择很大程度上提高了NOC的路由效率。
3 结论
该文证明了输入选择对于路由效率的影响,并设计了一种基于阻塞程度的输入选择算法(BLIS)。BLIS是根据上流switch的阻塞情况,赋予那些比较繁忙的输入沟道更高的优先权来输出。在高负载情况下,促使阻塞区域得以继续通信,减少了网络的阻塞。与输出选择机制结合使用,该文设计了四种路由方案。实验证明除了在对调模式下,BLIS输入选择与传统的FCFS输入选择性能相近外,其余模式下,BLIS性能均优于FCFS。在一些模式下,BLIS还能使复杂度低硬件需求少的XY路由算法在性能上接近甚至超过高复杂度硬件需求高的算法。
参考文献
[1]Benini L,De Micheli G.Networks on chips:A new SoC paradigm[J].Computer,2002,(35):70-78.
[2]Henkel J,Wolf W,Chakradhar S.On-chip networks:A scalable,communication-centric embedded system design paradigm[J].VLSI De sign,2004(1):845-85.
[3]Dally W J,Towles B.Route packets,not wires:On-chip interconnection networks[J].DAC,2001:684-689.
[4]Hu J,Marculescu R.DyAD Smart routing for networks-on-chip[J].DAC,2004:260-263.
[5]Nilsson E,Millberg M,Oberg J,et al.Load distribution with the proximity congestion awareness in a network on chip[C].DATE,2003(1):126-7.
[6]Ni L M,McKinley P K.A survey of wormhole routing techniques in direct networks[J].Computer,1993(26):62-76.
高效路由 篇4
传感网或移动自组网(Mobile Ad Hoc Network,MANET)[1]是在一定范围内,由一些无线移动设备(也称为节点)组成的集合,它无需任何固定的基础设施支持和管理,就可以互相通信。其因有限的电池能量引起了一系列关于物理层、MAC层和网络层的节能问题。因此,最大化网络生存期受到越来越多的关注。网络生存期定义为直到出现第一个节点能量耗尽的时间。
许多文献尝试降低能耗和最大化自组织和无线传感器网络的生存期。文献[2]提出一种降低无线网络能耗的策略,利用能量控制来降低传输功率,这样能最小化物理层的能量消耗[3]。在移动自组织网络中,通过假设单源节点引起的传输降低了复杂度[4,5,6]。关于最小化广播通信中总能耗的相关问题已得到广泛研究,它为网络的生存期提供了一个自然上界。文献[7 - 8]表明最小化总传输能量是NP难问题。文献[9]提出容错拓扑控制问题的一般近似框架,但该问题并没有解决节点的剩余能量。
同样有文献研究多跳路由选择来最大化网络生存期。文献[10]提出最大化系统生存期的新路由算法,在限制给定的能量时,最大化源节点和目标节点间的信息传输量。文献[11]将该方法进一步拓展,考虑了每条链路的Shannon容量。当节点用完电池或者连接到电源,为解决这种异构化情况,研究一种新的能量感知路由算法,该方法解决了多跳网络中的单播通信问题,然而本文解决的是单跳情况下的广播通信问题。当部分节点位置为变量时,寻找中继节点(能量最优)的位置,给出网络中传感器位置,该问题在文献[12 -13]中作为示例进行研究。
本文将节点分割为若干小组,称之为聚类。成员节点发送数据到最近的簇头(主节点),这些节点将数据聚合,并将消息发送到下一目标节点。如文献[14 -15]中的低能量自适应聚簇分层(Low Energy Adaptive Clustering Hierarchy,LEACH) 是无线传感网中第一个基于聚类的路由协议,它利用一种随机模型进行簇头选择,该协议采用分布式随机算法形成聚类,但并没有考虑残余能量。文中主节点(簇头) 将数据广播给所有节点,且所提算法考虑了剩余能量。本文用一种形式化分析补充了算法上的仿真结果,且所提分析方法可用于分析不同的聚类算法。
1 问题描述
本文中,对于集合V (表示潜在主节点),功率分配是一种函数p:V → R。对收发器的每个有序组(u,v) 分配一个传输功率阈值c(u,v),其有以下含义:仅当传输能量至少为c(u,v),v可以接收到由u发射的信号。本文假设c(u,v) 确定且对称。当以最大功率传播时,仅当节点可以到达其他所有节点时才选择它。对于节点m ∈ V,定义pm表示功率分配p:V → R,表示为:
式中,pm(v) 为当m为主节点时分配到v的功率。
一个包的传输功耗由发送和接收的一个距离独立部分和发送的一个距离相关部分组成。假设电池模型为线性,本文聚焦于和功耗相关的距离支配通信的有效性。每条边具有电池能量bv,通过具有传输功率为pm(v) 的节点v ,每条消息传输降低的功率为 λpm(v) 。
假设所有节点v ∈ V以恒定速率av传输,其中av表示单位时间的消息数量,称一系列传输为每个v ∈ V节点每轮传播av次。基于这些假设经过一轮可以获得电池下降(主节点m ):
文献[16]分析主节点m在网络整个生存周期中保持不变的情况。本文研究该问题的动态场景:给定一个图G = (V,E,c,b,a) ,其中c:E → R表示初始电池电压bv,v ∈ V和相对频率a1,…,an。本文寻找每个节点v作为主节点的轮数xv。其中,xv≥ 0 须以这种方式选择:当每个节点的剩余电池容量在网络生存期内为正数,∑v∈Vxv最大,其中,x表示向量(x1,…,xn) 。根据以最大功率传播时每个节点都能到达所有其他节点,本文假设E对应一张完全图。
当所有m ∈ {1,…,n} 满足以下条件时称x = { x1,…,xn} ∈ N+n是合理的:
其中项λ∑v≠mamxvpv(m)和分别表示节点m在节点v ≠ m和m时,主节点周期性的电池容量下降。
依比例缩放,假设 λ = 1 。当x = (x1,…,xn)时,式(2)可改述为: Ax ≤ b ,其中b:V → R+,A是一个n × n矩阵,(v,m) 对应项定义为:
丢弃轮数的完整性约束,生存期的最大值( 对于一个动态选择的单中继节点)对应着一个简单线性程序的解,称之为最优主节点选择(Optimal Master Selection,OPT) 算法。最优主节点选择中,本文选择x ≥0 ,当Ax ≤ b时,是最大的,矩阵A如式(3)所示。
下一节将比较最优主节点选择算法和直接传输算法(Direct Transmission,DIR)。在直接传输算法中,没有主节点:从源到目的节点,所有节点都能通过单跳传输到达其他所有节点。
2 均匀分布情况分析
本文所有节点以相同的传输功率p进行传输。式(3) 中定义的矩阵A表示为A = (n - 1)p In+p En,其中In表示单位矩阵,En表示全1 矩阵。
定理1 给定G = (V,E,c,b,a) ,其中E是完全图,对于所有v ∈ V满足av= 1,n ≥ 2。然后直接传输算法的网络生存期表示为:
对于最优主节点选择算法可得网络生存期为:
式(5)解释如下:当电池容量在网络中均匀分布,最优生存期由经过一轮网络的总电池容量降为(2n - 1)p的事实决定。一轮后,所有n - 1 个受控节点已经传输,降低了总能耗的(n - 1)p ,所有这些传输已经经过主节点转播,该主节点已经执行了n - 1 次转播行为,并将功率降低了(n - 1)p 。此外,主节点将单广播初始化为源节点,这样每一轮网络的总功率降低p(2n - 1)。所以轮数不能超过∑v∈Vbv/ p(2n - 1),当有一个或多个电池容量小的节点时,不可能达到上界,因为当其他节点是主节点时,它们不能作为从节点。
本文首先考虑均匀模型,它分配一个传输功率阈值c(u,v) 到组(u,v) 的每一个节点,其中c( u,v) 在[0,1]上均匀分布,c( v,u) = c( u,v) 。同样将Bv作为随机电池容量,假设,其中α≥0,U表示均匀分布。对于传输频率,假设对于所有v∈V满足av=1,其中单边决定了两个顶点的传输功率阈值,本文分析一个“独立模型”,对于每个节点v,传输功率阈值为U1,…,Un-1,它们的n-1个相邻节点随机产生。
定理2在独立假设下,所有的全一电池容量为B=1,网络的预期生存期采用直接传输算法为:
注意到当n→∞时,E[L]无限趋近于1。对于很多节点最大权重趋近于1(自下),就回到恒功率情况下(如式(4)所示)。下一个定理解决了电池水平从区间[α,1]中均匀选择的情况,其中0≤α<1。
定理3当0≤α<1,基于独立假设,其中,网络采用直接传输算法的预期生存期L为:
其中,
注意当 α = 0 时,式(7)减少为:
它无限趋近于0,对应网络中的情况是,节点刚开始电池几乎是空的,且决定了网络的生存期。
定理4 定义0 ≤ α < 1 ,基于独立性假设,B [α,1],网络生存期L的上界L' 采用最优主节点选择算法可描述为:
其中Z,W,B是随机变量,Z = max{U1,…,Un-1}(n≥3),,此外,
其中,表示平均收敛。
上界E|L'|,L'=B/(n Z+W)由网络中总功率决定网络生存期这一事实决定。L'的准确值可通过调整B=b和W=w来计算,然后计算w≥b/x、w ≤ b / x - n和其它条件下的P( L ≤ x | B = b,W =w) ,依次消除W和B 。从定理4 可看出E[L']≈n( α + 1) /3( n - 1) 。
3 几何情况分析
本文对动态中继节点选择方案中,研究了几何设置对于网络生存期问题的影响。假设图G = (V,E,c,b,a) ,其中对于所有v ∈ V有av= 1,E是一个嵌入了R2的完全图,满足c(u,v) = ‖u - v‖2。除最优主节点选择算法和直接传输算法之外,本文也考虑了中央主节点选择( Central Master Selection,CEN) 和最大化电池主节点选择( Battery Master Selection,BAT),它们都提供了可行解x = ( x1,…,xn) ∈ R+n,且计算上更简单。
最大化电池主节点选择最简单。该方法以如下方式选择主节点m : 拥有最大的电池容量bm=maxv∈V{bv},接下来 Δt轮都选择m作为主节点。然后重新评估该主节点选择,选择一个新的主节点bm'= maxv∈V{bv'},其中带标号的项表示重新评估时的电池容量,每 Δt轮周期性执行该过程。仿真实验中,本文选择 Δt = 0. 1 (当处理非整数轮数时,与1 轮相比,通过按比例降低每个节点的电池容量) 。
中央主节点选择遵循相同模式,参考式(2)。根据该公式,对于每个节点m ∈ V ,在整个网络生存期内选择m ∈ V为一个固定主节点时,可得到网络生存期Lm。
当主节点固定,最优主节点选择最大化Lm的m*,网络生存期变为:
和最大化电池主节点选择相似,本文在中央主节点选择中,在每 Δt轮周期性依据式(13),重复执行该过程来选择主节点m* ,其中 Δt = 0. 1,n在4到20 之间。
为避免角效应,节点在单位直径的二维磁盘上均匀分布。分配到每个节点的传输功率是1,足够覆盖整个圆,但根据p(u,v) = c(u,v) =‖u - v‖2,实际分配到每个节点的传输功率仅够到达期待的相邻节点(如主节点)。对于每种算法,平均网络生存期经过100 次仿真实验得到,计算置信区间作为标准偏差。
为研究用动态主节点选择代替静态主节点选择方案所取得的改进,本文比较了该算法的生存期和最优静态算法的生存期的比值,如图1 - 2 所示,显示了两种情况:全1 电池容量: bv= 1 ,v ∈ V和,v ∈ V,在所有v ∈ V情况中,av= 1。根据仿真实验可推出:①动态主节点选择相对于静态主节点明显延长了生存期;②生存期依次降低的顺序是:最优主节点选择算法、中央主节点选择、最大化电池主节点选择和直接传输算法。最优主节点选择算法和中央主节点选择很相近,预期当 Δt无限小时,两方法相同;③最优主节点选择算法的性能与直接传输算法对比强烈依赖于初始电池容量。对于均匀的[0,1]电池容量,最优主节点选择算法大约是直接传输算法的3 倍。对于全1 电池容量,其中网络的总能量平均是两倍,该因子至少相当于6。这和第2 节结果不同,仅当电池容量均匀[0,1]分布时,最优主节点选择算法优于直接传输算法,这是由于所有节点在一个单位直径的磁盘上。随着n的增长,长时间作为主节点的节点离圆心更近。这样,主节点相对于任意节点需要更低的传输功率。
4 实验结果与分析
本文在数值上评估了实际的网络生存期,通过使用最优主节点选择算法和直接传输算法,及在α ∈ {0,1 /2,1} 中的独立模型中,通过定理3 和4的近似值获得。
图3 中,通过比较均匀模型的仿真结果和理论结果,本文在数值上评估了该近似值的质量,同样评估了独立模型的精度。这些图表示直接传输算法的独立模型为网络生存期提供了一个非常好的近似值。如定理4,最优主节点选择算法收敛到(α + 1) /2。图3(a)显示当b ∈[α,1],α = 0 时,最优主节点选择算法的线性近似产生了一个过高的估值。这符合定理1。当 α = 0 时最优主节点选择算法相比于直接传输算法产生了一个更好的生存周期,在最优主节点选择算法下,剩余电池容量小的节点可以传输到一个“附近”的主节点,取代了必须传输到其他所有节点。图3(b)显示当 α =1 / 2 时,仿真模型和最优主节点选择算法的独立近似值相协调。n值的区别可由计算的独立假设解释,现实中依赖关系作为一个单边决定了两个节点的权重。对于 α ,最优主节点选择算法相对于直接传输算法仍会产生一个好的生存期。图3(c)直接传输算法的生存期明显趋近于1,表明对于相等的电池容量,直接路由相对于动态主节点选择方法产生更长的生存期。
5 结束语
高效路由 篇5
在有限的初始能量配置下最大限度地节省节点及网络的能量开销,以延长节点及网络的寿命,是WSN(无线传感器网络)应用研究中的一个热点课题[1]。多路径路由协议在WSN中明显优于传统的DSR(动态源路由)协议、AODV(按需距离 矢量路由)协议等,其对节点能量有效性、可扩展性和传输可靠性进行了综合考虑,采用了减少路由建立和维护的开销、提高路由可靠性等办法来降低数据分组传输的能量消耗。
网络编码融合了路由和编码的信息交换技术,核心思想在于允许网络中的节点对收到的信息进行编码操作,再转发出去,目的节点只需接收部分数据就能够解码出原始数据。网络编码在提高网络吞吐量、减少数据分组传输次数、均衡网络负载、减小传输延迟、节省网络带宽资源、降低节点能耗以及增强网络链路鲁棒性等方面均显示出优势,线性编码、随机网络编码均是较为成熟的方法。在实际应用中,如何高效地编码与解码是关键的技术手段[2,3,4,5]。
本文构建了一种新的网络编码方法,结合多路径路由技术,提出了一种WSN中新的能量有效算法,即MRAEE算法。目的是应用网络编码技术,在中继节点对数据分组进行编码,以增加数据传输的可靠性,减少分组不必要的发送频率,提高节点能量的有效使用。
1编码方案
1.1网络模型
非循环通信网络可以表示为有向图G (V,E),其中V为节点集,E为链路集;节点V的输入链路记为In(V),输出链路记为Out(V);对于任意一个节点对(d,e),xde表示(d,e)的数据流;如果节点对不相邻,则编码系 数kd,e = 0;S为源节点;KC为|E|×|E|矩阵;P表示主要理想域;ω为G维数;Jω,|E|表示ω×|E|矩阵。本文提出一种对于网络编码的可行模式,在R2(R代表矩阵G的秩)内使用泊松点过程模拟WSN,WSN内的节点随机散布在区域BR2。Φ0为区域B内的节点个数,λ0为密度,即单位面积的节点平均数。Φ1,Φ2,…,ΦN-1是N 1个二维独 立的基于 密度λ1,λ2,…,λN-1,泊松过程中 的节点描 述 ,它们独立 于Φ0,N为节点数 。假定每个节点可全向发送信号,且其自身的能量可动态调节,以控制它的发送范围。
1.2基本模型
在本文所提出的方法中,构建一个基于网络编码的多散联路由。网络编码示例如图1所示。
首先,源节点S发送数据分组a、b和c,编码这些分组形成数据1、数据2和数据3,然后将它们发送到目的节点D。这些分组将按多播特性几乎同时到达中间节点,即节点1、节点2和节点3。节点1成功收到数据1和数据2,对它们进行编码,形成数据4和数据5,然后将它们发送到下一个节点。节点2成功收到数据1和数据3,对它们进行编码,形成数据6和数据7,然后将它们发送到下一个节点。节点3成功收到数据1、数据2和数据3,对它们进行编码,形成数据8、数据9和数据10,然后将它们发送到下一个节点。目的节点D将收到三个编码过的数据分组,即数据4、数据6和数据10。当采用适当的网络编码方案后,目的节点D能够高效地还原三个原始的分组,即数据1、数据2和数据3。因此,传输的分组数无须增加,但可靠性会有很大提高,因为编码过的分组被发送到目的节点后,通过解码能快速实现分组信息的还原[6]。
2网络编码策略
在网络中,路由器或中间节点仅转发其收到的数据分组,而网络编码可让路由器或中间节点对数据分组进行编码,本文采用一种线性网络编码方案。
编码:将来自源节点的数据分组分成若干批,每一批包含N个分组,线性网络编码方案是给出编码矢量gi= (gi1,gi2,…,giN ),输入分组M =(M1,M2,…,MN)按式(1)转化成输出分组Pi:
目的节点能够解码出输入分组信息,因为编码矢量G=(g1,g2,…,gN),gij是从伽罗华域随机选择的系数,例如GF(28),输出分组数据P = (P1,P2,…,PN)可从接收到的分组信息中得到,并且存在逆矩阵于G。
解码:任何一个接收者(路由器或中间节点)都可对通过采集得到的一批分组进行解码。目的节点可用如下算法解码接收到编码分组。这些分组构造产生一个线性方程组系统,求解它们可找回原始发送的分组。解码矩阵表示这个线 性系统的系数矩阵。目的节点利用高斯-约当消去法将解码矩阵转化成一个简要的行梯次形式进行求解。假定一个节点收到属于某一批次的v个编码过的分组X1,X2,…,Xv,此处v≤ N,且代表对应某个编码过的分组的编码矢量,解码矩阵G的一般元素满足Gij=gij,此处i=1,…,v且j=1,…,N。当矩阵满秩时,R=v= N,对于传递过来给定的一批编码分组,节点能够求解线性方程组得出对应的原始分组信息。这种情形下,接收者能够复原得到由源节点发出的对应于给定的一批编码分组的原始分组内容。最终可观察到:当节点接收到一个分组时,必须检测它是否较新,即它是否增加解码矩阵G的秩,如果没有,则丢弃这个分组[7,8]。
当目的节点D收到N个以线性独立编码矢量表示的分组时,通过矩阵求逆可得到原来的分组。
3能量消耗
我们利用MRAEE算法推导出能量有效增益公式。假定源节点S需要传输信号到目标节点D,不考虑一般意义上的损耗,且假定信号发送周期为1s。
相对于非网络编码传输,基于网络编码传输的能量有效增益为GA,其定义如下:
式中,εptp为源节点S在非网络编码传输中对目标节点传输N个分组消耗的能量;εncptp为采用MRAEE算法在网络编码传输中源节点S对目标节点传输N个分组消耗的能量。接着,我们导出εptp和εncptp。εptp可表示为
式中,Pptp表示在非网络编码传输中点对点的平均传输能量。
为了用有限的平均能量传输,我们作一个限制,仅当信道的能量增益大于一个阈值时,节点才进行传输,否则,节点不传输或者处于断电状态。用ρuv表示信道在源节点与目的节点之间断电阈值,δ表示断电概率,即
式中,信道能量增益的指数分布|huv|2的概率密度函数由下式得到:
因而,式(4)可表示为
假定δ是一个固定的系统参数,我们能够从式(5)、式(6)中得到:
当未断电时,在非网络编码传输中,从节点1到节点2传输信号的平均传输能量能够计算得到,信道能量增益的指数分布|h12|2可表示为
式中,利用式(8)和式(3),可以得到:
对于MRAEE算法,节点1发送第一个编码过的分组到节点2,节点3和节点2之间的信道能量增益大于对应的断电阈值ρ32,因而,余下的分组利用MRAEE方法协同传送。
所有的能量消耗计算如下:
式中,Pnc表示未利用MRAEE算法时,在Pn1和Pn2发送期间,节点1的平均传 输能量。当它 们利用MRAEE算法进行网络编码时,分别代表节点1和节点3的平均传输能量。
4仿真实验
为有效评价MRAEE算法的性能,我们将之与著名的多路径路由协议算法EECA(基于能量高效冲突发现的多路径路由)算法[9]及NC-RMR(基于可信节点分簇网络编码多路径路由)算法[10]在能量消耗、分组传输率和网络寿命等方面做了相应的实验比较。仿真参数如下:节点总数为100,分布范围为1000s×1000s,发射距离为250m,节点平均度为3~5,仿真时间为600s,最大传输能量Ttmax为0.282 W,初始节点能量为30J,连接接收阈 值为3.652×10-10W,归避冲突 阈值为1.559×10-11W,信道带宽为1~3Mbit/s,连接延迟为20~200ms,流量类型为CBR,节点暂停时间为10s,除特别说明以外,均使用缺省值。
我们将在相同的能量模式和通信模式下对比三种路由协议的有关性能参数,主要从能量消耗、分组传输率和网络寿命三个方面进行相应的仿真比较。
(1)能量消耗:基于IEEE802.1低能量休眠模式的1-WLAN.规范,在发射层测量能量消耗。能量消耗的变化从0.013 W到0.83、1.0、1.4 W ,分别对应空闲侦听、接收和传输状态。
(2)分组传输率:分组传输率 = 接收的分组数/发送的分组数,代表某种协议的网络传输效率,是一个重要的网络量度指标。接收的分组数指任一目标节点接收的分组总数之和,发送的分组数是指任一源节点发送的分组总数之和。
(3)网络寿命:定义为网络节点的活动期,在这个时间范围内,节点能够处理、传输数据直到节点电池耗尽失效为止。
利用网络仿真软件NS2来评价计算NC-RMR协议。以BER(误码率)为参照基准来对比评述各项指标,在WSN中,BER通常在10-4~ 10-3。对于网络编码,一个代包含三个包 (即M =3)。图2比较了三种算法的能量消耗,由图可以看出,MRAEE算法的性能优于其他两种算法,它在较宽的误码率范围内表现出较低的能量消耗,说明网络编码技术对改善网络的能量效率有较好的作用。
图3比较了三种协议算法的分组传输率。从图中可以看出,对任一种流量负载类型,所有方案的性能都会受到BER增加的影响,但MRAEE比另外两种算法拥有更好的分组传输率。因为后两种算法采用的是传统的多路径结构,在分组的提取处理方面因为能量消耗过大而造成效率过低。
图4所示为网络寿命与BER的关系。当BER较小时,三种算法 差别不大;但当BER较高时,MRAEE的网络寿命远远长于另外两种算法,约有10%~ 30%的提高。
5结束语
本文通过构建一个基于网络编码的多路径路由,采用伽罗华域的编码矢量方法,利用高斯-约当行梯次矩阵求解技术,提出了一种新的基于网络编码多路径路由技术的节点能量有效算法MRAEE,并以BER为参照基准,与EECA和NC-RMR算法做了相应的比较,仿真结果表明,MRAEE算法在能量高效、网络生命延长及数据分组传递方面有较大的改进,具有较高的参考价值。
未来的工作中,我们将借助仿真技术重点考虑最优化和网络编码中解码算法的效率提高及其他参数的度量评测,以提高网络效 能,增进网络使用实效。
参考文献
[1]于宏毅,李鸥,张效义,等.无线传感器网络理论、技术与实现[M].北京:国防工业出版社,2008.
[2]王雪,王晟,马俊杰,等.无线传感网络任务分配的能效性控制策略[J].控制理论与应用,2007,24(3):127-134.
[3]Sun Baolin,Gui Chao,Song Ying.Energy Entropybased Clusterhead Selection Algorithm for Ad Hoc Networks[J].International Journal of Advancements in Computing Technology,2012,4(1):207-214.
[4]Sun Baolin,Pi Shangchao,Gui Chao,et al.Multiple Constraints QoS Multicast Routing Optimization Algorithm in MANET based on GA[J].Progress in Natural Science,2008,18(3):331-336.
[5]Sun Baolin,Gui Chao,Song Ying.Energy Entropy On-Demand Multipath Routing Protocol for Mobile Ad Hoc Networks[J].China Communications,2011,8(7):75-83.
[6]Sun Baolin,Lu Xiaocheng,Gui Chao,et al.Network Coding-Based On-Demand Multipath Routing in MANET[C]//Proceedings of 26th IEEE International Parallel&Distributed Processing Symposium(IPDPS).Shanghai:IEEE,2012:1514-1518.
[7]Anantapalli M K,Li Wei.Multipath multihop routing analysis in mobile ad hoc networks[J].Wireless Network,2010,16(1):79-94.
[8]Leinonen M,Karjalainen J,Juntti M.Distributed power and routing optimization in single-sink data gathering wireless sensor networks[C]//9th European Signal Processing Conference(EUSIPCO 2011).Barcelona,Spain:IEEE,2011:407-411.
[9]Wang Z J,Bulut E,Szymanski B K.Energy Efficient Collision Aware Multipath Routing for Wireless Sensor Networks[C]//Proceedings of IEEE ICC 2009.Xi’an:IEEE,2009:1-5.
高效路由 篇6
1 路由优化安全威胁
移动节点MN (Mobile Node) 进行路由优化的过程如图1所示。首先MN将新的转交地址NCo A (New Care-of address) 与家乡地址Ho A (home address) 的绑定关系发送给通信对端CN (Correspondent Node) 。然后CN向MN发送确认。但MN与CN之间不经认证的或错误的绑定更新BU (Binding Update) 往往会引发多种攻击。
第一类攻击:错误绑定更新攻击。由于绑定更新不经认证, 攻击者可以将合法MN的Ho A与攻击者的转交地址Co A (Care-of address) 或另一节点的IP地址绑定, 从而使CN发给MN的数据流向攻击者或另一节点。
第二类攻击:中间人攻击。在MN和CN都移动的情况下, 攻击者将自己的IP地址作为新的Co A分别发给移动节点和通信对端, 使移动节点和通信对端都以为这个Co A就是对方的新转交地址。攻击者成功介入通信双方的会话之中。
第三类攻击:拒绝服务攻击。攻击者可以先与一个或多个提供大量数据流 (如视频) 的服务器建立连接, 然后将绑定更新中的新转交地址设置为受害者地址。由于不经验证, 提供大量数据流的服务器会以为受害者是刚才发起连接的用户, 并将数据发给受害者, 从而导致受害者的机器拒绝服务。类似的攻击手段还有反射式拒绝服务攻击, 放大式拒绝服务攻击等。
2 现有的安全路由优化方法
返回路由可达协议RRP[1] (Return Routability Protocol) 由两项测试组成:家乡地址测试和转交地址测试。通过令牌的交换进行密钥协商, 确定Ho A和Co A地址是否可达, 以保证在MN的移动过程中, CN依然能够与真实的MN交换数据。但RR的安全性仅依赖于两个令牌环, 攻击者完全可以截获令牌环并完成返回路由可达。因此, 返回路由可达只能限制攻击者的位置, 从一定程度上减少受攻击的可能, 但并不能完全抵御绑定更新引起的各种安全威胁[2]。
为此人们又提出了一些安全路由解决方法, 大体可分为基于公共密钥基础设施的解决方法和不依赖公共密钥基础设施的解决方法。由于基于公共密钥基础设施的解决方法在部署上的困难, 因此这类路由优化方案实现起来仍存问题。
基于加密生成地址协议CGA (Cryptographically Generated Addresses) 的安全路由优化方法[3]是一种典型的不依赖公共密钥基础设施的解决方法。它将128bit的IP地址划分为2部分:64bit的子网前缀和64bit的接口标识。利用Hash算法对公钥和子网前缀等信息生成一个合法的IPv6地址, 从而在公钥和IP地址之间形成绑定关系。但由于基于CGA的安全路由优化方法不验证Co A的有效性, 任何攻击者都可以实施洪水攻击。
基于身份的安全路由优化[4]在返回路由可达协议的基础上结合了基于身份的加密机制IBC (ID-based Cryptography) 。它利用IBC的特点, 使用MN的Ho A和Co A作为其身份信息分别产生公私钥, 并利用这两对公私钥实现家乡地址测试和转交地址测试。虽然不依赖于全球密钥分发系统, 但这种方法速度较低。首先, 返回路由可达采用家乡地址和转交地址两项测试的目的在于通过不同路径上的测试判定Ho A和Co A的真实性。而在结合了IBC后, IBC能够确定MN的身份, 因此两组测试实现身份认证的方式应该简化。其次, 虽然进行了预绑定更新, 但从安全考虑, MN和CN之间需要利用非对称加密机制进行MN的身份验证。由于非对称加密算法速度相对较慢, 因此也延长了绑定更新时间。针对以上两点, 本文提出了一种高效的安全路由优化机制。
3 高效的移动IPv6安全路由优化
3.1 协议介绍
快速的移动IPv6安全路由优化是对基于身份的安全路由优化的改进。在传统的公钥体系中, 公钥、私钥成对产生, 并公开公钥。而在基于身份的公钥体系中, 公钥就是用户的ID, 或者可由用户的ID直接导出。私钥由密钥生成中心KGC (Key Generator Center) 生成。
快速的移动IPv6安全路由优化过程如:当MN移动到一个新的外地链路并得到新转交地址NCo A后, 如果发现与CN之间的数据交换依然需要通过HA进行转交, 应该立刻执行路由优化, 具体过程如图2所示。
(1) MN向HA发送私钥生成请求消息REQ
MN通过隧道向HA发送私钥生成请求消息REQ, 请求家乡代理HA为其生成新转交地址NCo A对应的私钥和用于加、解密的系统参数param。
REQ={Ho A, NCo A, CN, N0}, 其中, N0是MN生成的随机数。
(2) HA向MN发送私钥生成应答消息REP-MN
HA收到私钥生成请求消息REQ后, 利用IBE产生MN的新转交地址NCo A对应的私钥SMN。并向MN发送私钥应答消息REP。
REP-MN={SMN, N0, Co A, param}, 其中, SMN是MN的新转交地址NCo A对应的私钥, N0与私钥生成请求消息REQ中的N0匹配, param是用于加解密的系统参数。
(3) HA向CN发送用于加解密的系统参数param
在HA向MN发送REP的同时, HA向CN发送用于加解密的系统参数param。
REP-CN={Co A, CN, param}, 其中, param与REP-MN中的系统参数一致。
(4) CN向MN发送对称密钥k0
k0是CN为它与MN之间通信生成的会话密钥, 用于实现对MN的身份验证和绑定更新消息的完整性保护。为保证k0的私密性, CN利用MN的公钥PMN对k0加密发送, 记为EPMN (k0) 。由于采用了IBE, 因此, MN的公钥PMN是可以由CN通过MN的新转交地址直接获得的。
(5) MN向CN发送绑定更新消息BU和BU的消息认证码
当MN收到EPMN (k0) 后, 利用REP-MN消息中得到的自己的私钥SMN对EPMN (k0) 进行解密, 得到k0。显然, 这个k0只有MN和CN知道。因此, MN能够利用k0对绑定更新消息BU生成消息认证码MAC-BU, 并将它与BU一起发送给CN。
(6) CN向MN发送绑定更新确认消息BA
当CN收到MN的绑定更新消息BU和消息认证码MAC-BU后, 利用k0对BU进行和MN一样的认证码生成算法。然后和接收到的MAC-BU进行比较。若一致, 说明绑定更新消息BU的来源和完整性, 于是CN向MN发送绑定更新确认消息BA。
到此, 路由优化完成, MN可以不经过HA直接与CN进行通信。
3.2 协议分析
3.2.1 安全性分析
由于基于身份的加密机制中密钥分配中心能够在核实用户身份后对用户生成私钥, 而在本方案中HA作为密钥分配中心, 与MN之间有隧道保证安全, 因此, HA能够确认MN身份并为其生成私钥SMN。这就保证了由MN的公私密钥对保护的k0的私密性。因此, 利用k0生成的绑定更新消息认证码能够保证BU的真实性和完整性。这就抵御了上文所述的错误绑定更新攻击。同样, 在MN移动, CN也移动的情况下, MN也可利用本方法对CN的绑定更新消息进行认证, 从而避免攻击者欺骗通信双方的情况发生。这就抵御了中间人攻击。最后, 由于利用k0生成了BU的认证码, 因此攻击者也不可能在向多个服务其发起访问服务后, 再将受害者MN的Co A与自己的家乡地址绑定, 使大量的数据流向受害者的机器。这就抵御了拒绝服务攻击的发生。
3.2.2 效率分析
在快速移动IPv6安全路由优化中, 密钥生成中心 (家乡代理HA) 能够为MN生成安全的私钥。由于私钥只有MN和其家乡代理HA知道, 因此家乡地址测试和转交地址测试一次完成, 可以简化路由优化步骤, 提高切换效率。其次, 由于对称加密机制比非对称加密机制运算速度快, 因此利用对称加密机制实现MN与CN之间的身份认证能够进一步提高绑定速度。
结束语
移动IPv6主要的安全威胁是路由优化过程中CN对MN绑定更新消息的认证问题。利用可达返回路由这类安全协议无法完全解决绑定更新存在的安全问题。公共密钥基础设施PKI虽然能够保证绑定更新消息的安全, 但由于实际部署上的困难, 也不可行。本文对基于身份的安全路由优化进行了改进, 将家乡地址测试和转交地址测试一次完成, 并用对称加密机制提高运算速度, 在保证绑定更新安全性的同时降低了移动IPv6的切换时延, 提高了路由优化效率。
参考文献
[1]IETF RFC 3775.Mobility Support in IPv6[S].2004
[2]Kui Ren, Wenjing Lou, Kai Zeng, etal.Routing Optimization Security in Mobile IPv6[OL].http://ece.wpi.edu/~wjlou/publication/COMNET06-Ren.pdf.2009, 9
[3]M.Roe, T.Aura, G.O’Shea, etal.Authentication of mobile IPv6 Binding Updates andAcknowledgments[OL].http://tools.ietf.org/search/draft-roe-mobileip-updateauth-02.2009, 9
高效路由 篇7
Ad Hoc网络终端具有路由功能, 是由一组带有无线收发装置的可移动节点组成的一个多跳的临时性自治系统。因其具有独立自组网能力以及无中心、动态性、易于铺设等特点被广泛应用于紧急救援、道路交通、军事战场、偏远野外和探险等临时信息系统建设, 成为当今的一个研究热点[1,2]。
基于Ad Hoc的组播路由协议有多种分类方法, 一般把它们按组播传输结构可分为树状组播路由协议、栅格状组播路由协议、混合性组播路由协议和无状态组播路由协议。在小规模的Ad Hoc网络中, 无状态组播路由协议因其独特的性能和特点得到众多研究人员的关注和认可。
无状态组播路由协议是基于这样一种考虑:基于树和基于网格的组播路由协议都需要进行路由树或网格的创建和维护, Ad Hoc网络频繁的拓扑变化导致这种过程的开销非常大。为了减少这种开销, 无状态的组播路由采用组播发送者集中管理组播成员关系的方法, 在分组的报头中显式的列出组播的接收者, 中间节点不需要维护动态的组播路由信息。无状态的组播路由主要用于小规模的组播, 并由单播路由协议根据分组的报头转发到各个接收者。
1DDM协议
DDM[3] (Differentail Destination Multicast) 是一种典型的无状态组播路由协议, 它由组播发送者负责对成员的管理。当节点加入组播组时, 利用单播路由, 发送JOIN消息到组播发送者, JOIN消息包括组播的ID号, 加入节点的ID号, 发送者的ID号。组播发送者接收到JOIN后, 将加入节点的ID号加入成员列表中, 加入节点就成了一个组播发送者的接收成员。
成员列表的更新是发送节点主动完成的。发送成员在数据分组中周期地捎带一个查询标志, 接收成员通过单播一个JOIN信息来响应发送成员的“查询”。当一个成员需要退出组播分组时, 显式地发送一个LEAVE消息。
DDM议的关键技术是基于组播接收成员的转发报头计算与编码, DDM采用差分编码。它的控制包有四种类型, 即JOIN, ACK, LEAVE和RSYNC。前三种控制分组用于成员控制算法, RSYNC用于节点与其上游节点的组播成员列表同步。DDM的包格式如图1所示。其包格式分数据包和控制包, 数据包主要包括DDM报头和有效负荷。
每一个DDM块对应一个下游邻居。DDM块包括有期望的接收者、DDM块类型、DDM块序列号。有三种类型的DDM块:空 (Empty) 块、刷新 (Refresh) 块、差分 (Difference) 块, 简便记为E, R, D。在无线广播网络中, 到不同邻居节点的DDM块可能汇聚到一个分组中, 以减少传输次数。
DDM的包头中需要转发的信宿节点的集合称作FS。在组播的源节点, FS和成员列表是一致的。在其他节点, FS是所有上游邻居节点FS的并集。节点到达FS中的信宿节点的路径是不同的, 根据转发的下一跳, 可将FS中的信宿节点划分为不同的子集, 成为方向子集DS。每个DS对应一个下游邻居节点。每个DS还包括一个强制刷新标志, 用于转发组的同步。节点在接到数据包以后, 首先比较序列号, 如果已经处理过, 则丢弃该包, 并根据DDM快的期望接收节点, 定位自己的DDM块。如果是R块, 则创建新的FS, 如果是D块, 则更新FS, FS=∪FS。
当采用差分编码时, 在DDM块中仅包含节点的差分列表, 因此保持上游节点的FS表与下游节点的DS表的一致性是十分重要的, DDM用序列号来维护表的同步。每个DDM块都有一个序列号, 来标记上游节点FS表的序列号为, 每发一个分组序列号加1, 发E块时不变。当节点检测到序列号不连续时, 就发送一个RSYNC消息到相应的上游节点, 接收到RSYNC的节点根据发RSYNC消息的节点的ID定位将发送DDM相应的分组DSS, 并更新列表, 从而使列表同步。
2对DDM的分析和扩展
评价一个协议好坏的标准有很多, 其中数据传输效率是很重要的一条。在Ad Hoc环境中, 能量和带宽是有限的, 怎么样在一定的时间里用尽可能少的能量传输尽可能多的数据, 一直是人们努力实现的技术。DDM是一个适用于规模小、移动速度快的Ad Hoc环境, 但从DDM的包格式来看, 其控制部分在整个包中占了很大比例, 这将严重影响协议的传输效率。一般情况下, 按需路由协议的包头都带有大量控制信息;表驱动的路由协议则需要大量的控制信息。
表驱动路由协议又称为主动式的路由协议, 该路由协议试图维护网格中各个节点到其余所有节点的最新路由信息, 所有路由信息保持一致。每个节点都维护一张或几张到网络中其他节点的信息表, 当网络拓扑结构发生变化时, 节点通过交互信息来实时地维护网络路由表。在表驱动协议中, 由于每个节点需要实时地维护路由信息, 这样在网络规模较大、拓扑变化较快的环境中, 大量拓扑信息更新消息会占用过多的信道资源, 使得系统效率下降。按需路由协议是只有在节点有数据要发送时, 才激活路由发现机制寻找到达目的地的路由, 很多控制信息加在数据包上, 减轻了网络负担, 灵活性、健壮性较好, 但其包格式的控制部分占比例太大, 影响传输效率[4]。
为了保持协议的传输效率和健壮性, 可以取长补短, 使用表驱动和按需驱动两种方式相结合的协议。即组播路由的发现和维护使用按需驱动的方式, 而传输组播数据包则用表驱动的方式。这里提出一种同样适用于规模小, 移动速度快的Ad Hoc环境的新的组播路由协议EDDM。
3EDDM组播路由协议
EDDM (Efficient Differentail Destination Multicast) 是一种靠单播链路来进行分发的组播协议, 它是使用按表驱动和按需驱动混合的一种高传输效率的组播协议。它内嵌的单播协议也是DSR协议。
3.1 EDDM的包格式
EDDM主要有JOIN, REQ, ACK, DATA, LEAVE和RSYNC六种包格式, 其中, JOIN, REQ, ACK, LEAVE和RSYNC是控制包, 它们的包格式是DSR格式, 如JOIN的包格式, 如图2所示。JOIN, REQ, LEAVE是用来维护和发现路由的, RSYNC是用来同步数据包的。这些包中含有部分控制信息, 包头相对较长。
DATA包是数据包, 它的格式相对就简单多了。为了提高传输效率, EDDM的数据包不包含控制信息, 控制信息都写在节点内部的表中, 其格式如图3所示。
3.2 组播路由的发现和维护
EDDM的路由维护和管理是由组播的发送者来实施的。其过程如下:
(1) 想加入组播的节点通过向源节点单播一个JOIN消息来加入组播组, 源节点收到JOIN消息后, 把发送JOIN的节点加入组播组然后单播REQ消息给请求的节点。
(2) 中间节点在收到JOIN消息后, 就认为自己是组播的转发节点, 并记下JOIN消息的上一个节点、下一个节点以及JOIN消息的发送节点, 从而建立了一只组播链路。
(3) 组播源节点周期性的组播确认信息REQ, 当成员节点收到REQ后, 将回复JOIN消息。
(4) 如果组播成员节点在规定的时间内没有收到REQ消息, 那么它将继续周期性的发送JOIN消息, 直到得到源节点的回应。
(5) 如果某条链路在数据转发的过程中发生断链, 那么发现断链的节点将使用单播的形式发送RSYNC消息给与本链路相关的各个目的节点。目的节点收到RSYNC消息后将重启单播寻路机制, 然后向源节点发送JOIN消息, 从而达到维护路由的目的。
(6) 如果某个目的节点想退出组播组, 则发送LEAVE消息给源节点, 那么沿途所有收到LEAVE消息的中间节点都会取消针对退出的目的节点的数据转发。源节点如果在规定的时间内没有收到某个成员的JOIN消息, 也没收到LEAVE消息, 会将该节点从组播成员中删除。而中间节点如果在一定的时间内 (这个时间设定为刷新时间的2倍) 没有收到经过它的JOIN消息, 则认为自己不再是中间节点, 不再转发数据。
3.3 EDDM数据包的转发
当源节点广播数据包时, 源节点和目的节点之间已经通过发送JOIN消息和REQ消息建立起了组播路由。组播路由表是独立于单播路由表的, 它只是从靠JOIN消息中解读出有用的信息保存在JION所经过的节点的表中。
(1) 当一个中间节点收到一个组播数据包, 先检查是不是收到过同样的包, 如果以前收到过则销毁。
(2) 如果第一次收到这个包, 则检查这个包经过的上一个节点号和它的组播号并将他们跟自己的组播路由表对比, 看其是否与自己相关如果不相关则销毁。
(3) 如果这个数据包与自己相关, 则立即给上游邻节点发送ACK消息并广播数据包, 然后等待下游邻节点的ACK消息。
(4) 如果在规定的时间内没有收到下游邻节点的ACK消息, 则认为该处断链。
4仿真与分析
为了评测EDDM协议的性能, 使用NS2仿真工具对其性能进行模拟研究, 并与经典组播协议ODMRP进行比较。网络中节点通信半径最大为250 m, 信道能力为2 Mb/s, 节点的无线传输模型选Two-Ray Ground传输模型, 仿真过程中每个组播组中仅有一个信号源发送数据;仿真时间为400 s, 节点移动速度为2～20 m/s。节点在1 000 m×1 000 m的矩形平面空间中进行随机运动移动。
本实验针对ODMRP和EDDM的数据包传输效率进行了仿真比较, 比较结果如图4所示。从图中可以看到, 组播成员节点相对较少的情况下, EDDM的数据包传输效率明显优于ODMRP。但随着成员节点个数的增多, 其性能逐渐下降, 说明EDDM的扩展性不强。在这里没有从仿真中严格比较DDM和EDDM在数据传输效率方面的优劣, 但给出了EDDM和ODMRP的比较。在成员节点数目较少的情况下, 他的数据传输效率都优于ODMRP, 但这种优势也都随着组播成员个数的增多而变小。
从传输单个数据包的角度来看, EDDM的效率与DDM的效率相比差别很大。现在设DDM的源节点周围有m个下游节点 (也就是说第一次转发的数据包中需要带m个DS块) , 设每个DS块中有n个目的节点, m和n的最小值为1, 每个段按最小8位, x为数据大小, 则DDM的数据部分占总大小比例为 x/[8 (4+m (5+n) ) +x];而EDDM的数据部分占的比例为x/ (3×8+x) 。
通过Matlab的计算比较可以得到如图5所示的结果。
图5分别对式x/[8 (4+m (5+n) ) +x]中的n=m=1和n=2, m=3及式x/ (3×8+x) 进行了计算比较, 数据部分x的大小范围为32～256 b。从图5中很容易发现, 在DDM协议的包格式中, 目的节点越多, 单个包的数据传输效率越低, 只有在带宽很大时, 其单包传输效率才很高, 而这在实际应用中是很难达到的。在EDDM中, 单个数据包的数据传输效率高于DDM很多, 在数据部分x比较小的时候, 这种优点尤为明显。
5结语
EDDM是一种使用于小规模的高效组播路由协议。它从无状态组播路由协议延伸而来, 是一种树状结构的协议, 但其状态结构的组织非常松散, 类似于无状态的组播结构。该协议充分考虑了表驱动与按需路由驱动的优缺点, 是从实际应用出发, 使用二者相结合的方式形成的一种高效数据传输协议。从各个方面的比较来看, EDDM确实有效地保证了在小规模、高速度Ad Hoc网络中的高效数据传输。
摘要：Ad Hoc网络中, 组播路由协议具有广泛的应用前景。但由于网络拓扑的变化和节点能量的限制, 设计具有高效传输能力的组播路由协议比较困难。通过综合比较表驱动路由协议与按需路由协议的优缺点, 并且考虑Ad Hoc网络中节点的移动性以及路由发现与路由维护的方法对传输效率的影响, 在无状态组播路由的基础上, 使用表驱动与按需路由驱动相结合的路由方法, 提出一种新的组播路由协议, 使传输效率有较高的提升。
关键词：自组网,组播路由协议,传输效率,按需驱动
参考文献
[1]郭永洪, 李光胜, 毛启容, 等.Ad Hoc网络组播路由协议研究现状、问题和方向[J].计算机应用及软件, 2006, 23 (4) :8-10, 65.
[2]孙宝林, 李腊元, 李相棚.移动Ad Hoc网络多播路由协议的研究进展[J].计算机工程与应用, 2004, 40 (32) :139-143.
[3]JI Lu-sheng, CORSON M Soctt.Explicit multicasting formobile Ad Hoc network[J].Mobile Networks and Appli-cations, 2003, 8 (1) :535-549.
[4]郑少仁, 王海涛.Ad Hoc网络技术[M].北京:人民邮电出版社, 2004.
[5]LEE S, SU W, GERLA M.On-demand multicast routingprotocol (ODMRP) [C]//Proceedings of IEEE WCNC′99.New Orleans, LA:IEEE, 1999:1298-1302.
[6]LUO Jun-hai, YE Dan-xia.A survey of multicast routingprotocol for mobile Ad Hoc networks[C]//IEEE Commu-nications Surveys&Tutorials.[S.l.]:IEEE, 2009, 11 (1) :78-91.
[7]KALIAPERUMAL B, EBENEZER A, Jeyakumar.Adap-tive core-based scalable multicasting networks[J].Proc.IEEE INDICON, 2005, 29 (3) :198-202.
[8]SOON Y O, PARK J S, GERLA M.E-ODMRP:enhancedODMRP with motion adaptive refresh[J].Proc.ISWCS, 2005, 49 (17) :211-217.
[9]YU Yao, ZHOU Yu.Impact of Interference on multicastthroughput over Ad Hoc Networks[R].Fifth InternationalJoint Conference on INC, IMS and IDC, 2009.