基于启发式环索算法的anycasing路由

基于启发式环索算法的anycasing路由

1总结1.1任播路由技术移动社交网络（移动adhoc网络）是一种新型的无线网络。这些动态节点由带wlan条件的无线传感器暂时形成一个罕见的自治系统。网络上的每个节点都有两个主机和路由器。与传统的固定无线网络（如基站或访问点）相比，没有必要在网络上建立固定的通信装置。因此，移动网络具有很高的可靠性和灵活性，可以广泛应用于海上勘探、紧急调查、临时会议和其他办公室。AdHoc网络的路由协议可以分为表驱动路由和按需路由两大类.在表驱动路由协议(先应路由协议)中,每个节点维护到所有已知目的节点的路由表.节点之间周期性连接且在网络拓扑发生变化时交换路由信息,减少了获得路由的延迟,使源节点能够立即判断目的节点的可达性,但是消费了较多的网络资源,此外它浪费了一些资源来建立和重建那些根本没有被使用的路由.在按需路由协议(反应路由协议)中,节点不需要花费资源来维护无用的路由,但路由发现过程费用比较昂贵而且不可预测,路由延迟与先应路由协议中恒定的查表时间相比,更加多变.目前研究的最为深入的表驱动路由协议为DSDV,OLSR,按需路由协议为DSR,AVOD和TORA.任播路由(AnycastingRouting)是一种全新的路由方式.这个词的最初定义出现在1993年的rfc1546中.它的最初语义为,用一个anycast地址标识一组提供某种服务的主机,发送到该anycast地址的数据报将被投递给这组主机中的某一台,也就是任意一台.这是一种无状态的、尽力而为的网络层投递服务.从功能上说,任播路由可以描述如下:在给定的路由域当中,一个任播地址对应为多个接收节点,任播路由协议为转发带有任播地址的数据分组到某个接收节点而建立、维护必要的路由信息.概念上,任播路由为每个接收节点维护的路由信息定义为“服务域”,为适应接收节点设置的变化、网络拓扑和环境的改变,任播路由需动态地调整服务域的内容.在移动无线网络中,用户和网络拓扑结构都是完全动态的,带宽资源和终端的能源十分有限.任播可以为动态的管理终端节点提供一种鲁棒性的模式.下面是任播技术在AdHoc网络中的具体应用:(1)分布式服务定位.在未来的AdHoc网络中,需要在高度动态的环境内提供连续的分散控制,从而保证全网都得到鲁棒性的可升级的服务.然而在没有优先级配置的前提下管理和定位分布式服务是个棘手的问题.在军事上,要求网络能够在动态的环境内根据用户的需求而平稳切换和运行,任播路由技术可以通过支持分布式服务和用户设计来达到此目的.(2)信息定位、检索和收集.任播路由技术能从以下几个方面实现此功能.首先,任播路由为信息的定位提供一种简单的方法,可能分布在网络层的更高层,通过某种服务或应用层来实现;其次,服务节点的定位有利于信息的检索,这样可以满足数据序列号码的检索需求以及建立稳定的连接.一个简单的应用举例为移动网络中节点对分布式目录和有关安全的服务要求.最后,任播路由为动态、分布式网络数据的收集提供直接的功能支持.2基于主动广播的anyctoring路由算法文献中提出了一种基于虚拟节点的Anycasting扩展方法,方法的基本思想是用一个虚拟节点(vistualnode)通过虚拟链路(vistuallink)连接所有的Anycasting主机,任何一个发往虚拟节点的数据报被确保到达一个Anycasting主机(如图1所示).文献中给出了简单扩展DSR、AODV和TORA路由协议的方法,但是完整的协议细节并没有被阐述,而且文章中并没有详细讨论如何减少在路由请求过程中带来的过多的无用的网络代价.在文献中,作者通过模拟的方法证明了在AdHoc网络中采用任播路由方法比采用传统的单播路由方法具有更高的效率.文章同时指出了如何消除Anycasting路由在路由发现阶段带来的网络代价过高的问题是一个需要深入研究的课题.为解决路由发现阶段网络代价过高的问题,文献提出了中心节点路由算法(Node-CentricRouting),方法的基本思想是将Anycasting主机视为AdHoc网络中的中心节点,由中心节点主动广播自己的存在,网络中的其他节点收到中心节点广播后在路由表中建立到中心节点的路由.这样,当节点访问中心节点时不需要再发起路由发现过程,从而减少了网络代价.但是,进一步的实验表明,当网络节点数较多,网络拓扑变化较快的时候,中心节点为了维持网络中其他节点到自己的路由,必须较频繁地发出更新信息,这样对AdHoc网络仍然会产生较高的代价,而且如果网络中的节点在一次更新周期内并没有访问中心节点,那么因此产生的网络代价实际上是“无用”的.因此,基于主动广播的Anycasting路由算法的广播周期T和消息广播范围D等参数仍需要进一步地优化.3启发式环索算法环索技术(ringsearchingtechnique)是一种简单实用的节点搜索技术,源节点从距离自己最近的区域开始搜索,逐步扩大自己的搜索范围,若搜索成功,则立即停止搜索.在Anycasting的路由请求阶段,可利用环索技术控制RREQ的生存跳数,从而控制RREQ的传播范围,达到减少网络代价的目的.在AODV协议中,已经建议在路由请求阶段采用环索技术,但是搜索的参数需手动配置,不适合AdHoc网络分布式自组管理的特点.为使环索具有更大的灵活性和自适应性,从而提高环索算法的效率,进一步减少搜索时间和产生的网络代价,本文提出的启发式环索算法在以下两个方面做了适合Anycasting路由的优化.(1)采用主、被动路由相结合的混合方式.Anycasting主机定期广播自己的存在,不必随着网络拓扑变化而发送更新消息.节点可从Anycasting主机广播的消息中获得搜索所需的先验知识,动态地调整搜索的参数.(2)中间节点不是简单地将RREQ中的生存跳数减1,而是根据以往积累的“经验”以一定的概率和步长递减,使搜索总是向着“最可能”的方向进行.3.1启发式环搜索算法一个AdHoc网络可被模型化为一个平面无向图G=(V,E),其中E为图中所有节点的集合,V为图中边的集合.图G与实际网络的对应为:网络中的一个移动节点对应E中的一个节点,若网络中的两个节点可直接通信(即为邻居),则两节点在图中的对应节点之间存在一条边.假设AdHoc网络中的每个节点具有相同的传输半径,则G中的所有边都为单位长度,任意两节点间的距离由两点间的跳数决定.为描述环搜索技术,先定义网络直径的概念.AdHoc网络的网络直径为网络中任意两点间的最大跳数.即此外,定义与环搜索技术相关的参数如下:HOP_START为节点开始搜索时设置的跳数值;HOP_INCREMENT为搜索失败时的跳数增量;NODE_TRAVERSAL_TIME为测量得到的节点间传输报文所用的时间;WAIT_RREP_TIME为等待RREP返回的最大超时时间;FAIL_THRESHOLD为搜索步长跳变的失败阈值.其中满足关系式WAIT_RREP_TIME=2×NODE_TRAVERSAL_TIME×HOP_START.启发式环搜索算法的搜索过程描述如下:1.当一台主机加入Anycasting组,它会定期广播自己的存在,广播消息中的生存跳数TTL=MaxD/2+1.2.中间节点收到这个广播消息后,比较消息中的距离跳数值与路由表中已经存在的距离跳数值.若小,则更新路由表项,同时更新该路由信息的有效期.将广播消息中的TTL=TTL-1;若TTL>0,则继续广播该消息.3.当一个节点请求Anycasting服务的时候,先检查本地路由表中是否有有效的主机路由,若有,则不必发起路由请求过程;否则,按算法1动态调整搜索参数.算法1.启发式环搜索的算法路由请求发起过程.1.IF(路由表中有到该地址过期的主机路由,跳数为H)THEN2.HOP_START=H/2+13.ELSEHOP_START=14.发出RREQ消息,进行路由请求5.IF(在WAIT_RREP_TIME时间内收到RREP消息)THEN6.更新路由表项H,FAIL_THRESHOLD=[MaxD/H],进行路由保持过程7.ELSE8.失败计数器Counter=Counter+19.IF(Counter>=2×FAIL_THRESHOLD)THEN10.HOP_START=MaxD/2+111.ELSEIF(FAIL_THRESHOLD≤Counter<2×FAIL_THRESHOLD)THEN12.HOP_INCREMENT=Counter13. ELSEHOP_INCREMENT=114.HOP_START=HOP_START+HOP_INCREMENT15.GOTO4.分析算法1,可以得到搜索半径R与失败次数n的如下分段关系式:分段函数曲线如图2所示.启发式环索算法根据当前的网络状况和从上一次搜索中获得的“先验”知识,优化当前搜索的关键参数Base_Start和FAIL_THRESHOLD.Base_Start与上一次成功时的跳数相关,而不必从1开始搜索.同时,FAIL_THRESHOLD与“记忆”中的目的节点的跳数成反比关系,即节点可能的存在距离越远,搜索就越能快速的以较大的步长进行,从而提高环索算法的效率,进一步减少搜索时间和产生的网络代价.3.2基于启发式算法的rreq动态搜索算法中间节点在转发Ayncasting路由请求过程中,如果能根据以往积累的“经验”以一定的概率和步长减少消息中的生存跳数TTL,使搜索总是向着“最可能”的方向进行,会进一步提高搜索的效率.当Anycasting路由请求RREQ到达中间节点的时候,中间节点以如下规则减少RREQ中的生存跳数TTL.TTL=TTL-1-α(3)其中α>0称为递减因子.α按照如下算法2动态调整(其中变量M为节点根据已有“经验”预测本地到目的地距离,称为本地预测距离).算法2.启发式环搜索算法的路由请求传播过程.1.IF(路由表中有到该地址有效的主机路由)THEN2.先源地址发送RREP,α=TTL+13.ELSEIF(路由表中有到该地址无效的主机路由,跳数为H)THEN4.M=H/*预测距离M的值等于缓存的跳数H*/5. ELSEM=MaxD/*否则,M的值等于缓存的跳数H*/6.IF(M<TTL)THENα=07.ELSE8.RETURNα为验证上述启发式算法能使中间节点根据从前的搜索经验动态地减少RREQ的生存跳数,我们在MaxD=50,TTL分别等于5,6,7的3种情况下,按上述算法计算1000次α的值后求其平均,得到α与M的关系曲线(如图3所示).从图3中可以看出,对于TTL选取任何值,α与M之间都遵循如下规律:若中间节点通过以前的转发经验知道自己距离目标节点较远(M值较大),中间节点会有较大的可能以较大的α值减少RREQ的生存跳数;如果节点附近从来没有过目标主机,那么节点的路由表中不会有到目标主机的过期路由表项,M取值为网络直径MaxD,从而使RREQ在本方向的无用传播尽快结束,以降低网络代价,使搜索总是向着“最可能”的方向进行.同时,α的取值又是概率相关的,这样就避免了算法对某些特殊网络情况的搜索失败.4模拟与评估4.1模型拟合与性能评价我们用模拟软件ns2设计了模拟实验.实验的AdHoc网络场景包括50个移动节点,节点均匀分布在10000×10000m的正方形平面.每个节点采用IEEE802.11无线网络接口,最大传输范围为200m.节点的移动方式遵照RandomWayPoint移动模型.移动速率均匀分布在0～10m/s之间,停留时间均匀分布在0～500ms之间.AdHoc网络中有一个Anycasting组,组中有5个Anycasting主机成员,网络中有20个服务请求源节点.模拟实验反复运行30次,每次运行1200s.模拟着重分析了三个协议:标准的DSR协议、简单扩展支持Anycasing的DSR协议(SA-DSR)、采用启发式环索算法的DSR协议(HA-DSR).采用如下三个指标评价协议的性能:(1)报文转发率(packetdeliveryratio).数据报文成功地由源节点转发到目的节点的比率.(2)消息平均跳数(meanmessagehopcount).数据报文由源节点成功地转发到目的节点经过的跳数平均值.(3)路由代价(routingoverhead).网络中RREQ和消息总数的比值.4.2基于anyctoring的网络代价图4、图5、图6分别给出了三种协议的三项指标的性能比较.从图4中可以看出在一般情况下,三种协议的包转发率都要高于80%.随着节点停留时间的增加(即节点运动速度的降低),三种协议的包转发率均增加.DSR的包转发率要低于另外两种改进的协议,SA-DSR和HA-DSR在包转发率上只有细微的差别.从图5中可以看出,DSR的消息平均跳数要远远大于SA-DSR和HA-DSR.这说明在AdHoc网络中采用Anycasting路由会极大地提高网络的整体效率,这个结论与文献中提到的相符.此外,由于HA-DSR采用的是分布式局部搜索,有时不会比较网络中的所有Anycasting主机,选择的Anycasting主机可能不是最近的.