论文研究-基于延时约束的AODV改进协议 .pdf

所需积分/C币:10 2019-08-17 08:35:27 471KB .PDF
收藏 收藏
举报

基于延时约束的AODV改进协议,徐鹏,李腊元, 随着移动Ad hoc网络的发展和用户需求的不断提高,服务质量(QoS)问题已成为当前的研究热点。本论文提出了一种保证实时传输的路由协议
山国武技文在线 http://www.paper.edu.cn Srea/B( n+TH)+T,(]+toros,D) MEDOWNreq 其中DOWN={S,A,B,C}; ∈UPLt (7)+T2()]+Tbmo2(D,S 2ieUP[Srep/Ba(D)+Tw(+Ta(l+tprop(D, S) 其中UP={D,C,B,A}; 根据假设,Tp(S,D)=Tp(D,S),且所有节点的实际处理延时T4相等。另 外,由于无线节点只有一条信号发送通道,因此对于中间节点米说,其队列中的上行数据包 和下行数据包经历的平均等待时间也是相等的。所以,上下行延时的差为 diff down (T1(S)-T(D)+C I∈DO Srea /B(n))-Lleup(Srep /ba(r) ≈(Tn(S)-Tn(D)+∑[(Sm-Sm)/B( TM(S)-TMD) 第二个近似成立的原因是一般情况下,S/与Scq相差不过几十,甚至几个比特而 理论上,要使选择的路由满足数据流的端到端延时要求,应有: 也就是说 T+tdiff <27 如果要用双向延时的一半来估计下行延时的话,选择路由的标准就变为: Tr≤2T 这样,可能造成的路由选择大误(即实际延时不满足标准,估计延时满足标准)的概 率约为: P= p ITd>T|Tr≤2T =PIT>2T-Tdiff T. <2T I Tifr/2T 相对于T,7m的值是很小的。而且,T减m的值只与源结点、目的节点的队列等待 时间有关,与所选择的路由基本没有关系。因此,用T2,来估计Tom是合理的。 还需要说明的是,在带宽条件满足的情況下,网络能够为数据流的传输提供稳定的延 时,因此我们推断如果路由建立过程中估算的传输延时能够满足数据流的延时要求,那么数 据流实际传输的延时也能满足要求。 这样就能得到:当源节点收到来自目的节点的路由冋复(能够收到的路由冋复都是满 足延时要求的,下面还会具体说明)时,根据当前时间与其发送路由要求的时间算出T,, 并与数捱流允许的最人延时作比较,最终决定是否可以利用这条路山来传输数据流 山国武技文在线 http://www.paper.edu.cn T≤2T,能够传输数据流 Tr>2T,不能传输数据流 端到端延时估计的优化如下: 在传输过程中,当源节点发送的 REQUEST包达到目的节点时,如果此时的Tn已经 超过了T时,即Tdm>T时,我们认为此时此刻该路出已经不满足延时了,所以我们可 以直接丢弃该 REQUEST报文,没有必要再去统计T了,这样减少了一定的路由开销。优 化后的1.5式 Ton≤T且T≤2T,能够传输数据流 (16) Ton>T或T>27,不能传输数据流 2. RT QRP协议描述 RT QRP协议是传统AODV协议改进而米,主要改变有:在路由条目中增加延时信息, 在路由请求分组( Route request)、回复分组( Route Reply)中增加了新域:延时,并在路由发 现和路由维护中加入QoS机制,最后加入备份路由机制 21 RT QRP协议模型 RT QRP定义了一个移动 Ad Hoc网络的拓扑结构为一个加权图G(V,E),V代表网络的节 点集合,EsV,V代表网终中连接节点对的通信链路集合。如果两个移动节点问的距离小 于或等于节点通信的有效距离r时,则称这两个节点互为邻居节点。和分别表示网络中 的节点数和链路数,M2|表小节点i的度。定义节点ⅹ的邻居节点集点 N={n1|d(x,n;,Xn1,n;∈VN,N集合随着时间而变化。在GE)中,考虑源 节点到日的节点的QoS约束的路由问题,即给定一个非空集合M={su},其中,MsV,s 为源节点,Ⅱ为目的节点。寻找的QS路由P=(Vn,En),其中VnV,E2F 【定义1.1】在G(V,B中,假定路由请求的最大延时约束为D,对于v(i)∈E,L(ij) 为从节点i到节点j的路径,若L(ij)满足:Dij)≤D,则称此路径L(ij)为可行路径。 【定义1.2】在G(VF)中,对于源节点s,目的节点u,假设G(R)为满足上述延时约 束的可行路径集合,则我们要寻找的QS路出P应满足:S(P)max(S(GGn∈G(R。P 是节点s与节点u间最小代价的可行路径,称为最佳路径,P即为 RT QRP所选择的QoS 路由。 2 RT QRP协议包结构 表1给出 RT QRP路由请求包( Route request结构 表2给出 RT QRP路由回复包( Route reply)结构。 23路由发现 RT QRP是一种按需的路由协议,因为延时约束机制的引入,所以中间结点收到 Route Rcqμuest包时,即使存在到达目的地的QoS路由,也不能回复,必需继续转发该请求包。同 山国利技记文在线 http://www.paper.edu.cn 样,中间结点收到 Route Reply包时,也不能通过已建立的路由发送数据。如图1所示源节 点S到目的节点D的路由建立过程。 表1 RT QRP路由请求包( Route request RT QRP包类型 保留字段(16bi) 跳数(8bi 路由请求广播ID(32bit) 目的节点地址(32bi 目的节点序列号(32b 源节点地址(32bi 源节点序列号(32bi 时间戳(32bit 请求最大延时(32bit) 表2 RT QRP路出回复包( Route Reply RT ORP包类型 保留字段(l6bi 跳数(&bit) 路由请求广播ID(32bit) 目的节点地址(32bit) 日的节点序列号(32bit) 源节点地址(32bit) 路由维持时间(32bi) 吋间戳(32bit) 请求最大延时(32bit) REQ 日 ackward point RREP 佟1路由建立过程 下面是具体流程: (1)当源节点S要发送数据吋,先检它的路由缓仔,如果有满足QoS约宋的到达目的 节点的可行路径,则源节点在可行路径中选择最佳路径发送数据分组。如果在路由缓存区中 山国利技记文在线 http://www.paper.edu.cn 没有叫行峰径,则节点将启动路由发现过程,发送路由请求分组( Route request) (2)源节点S广播对目的节点D的路由请求 Route request,请求分组里包含请求延时 信息、路由发现发起时刻。 (3)当中间节点接收到 Route request分组时,如果收到过该分组,则丢弃,如果没有 收到过,则将该分组中的上一节点的地址加入到的反向路由链表中,并更新路由表,转发该 Route request分组 (4)当目的节点D收到该 Route request分组时,将比较延时,如果满足就向源节点发 送 Route reply分组,该分组中将记永对应的 Route request分组中的路由发现发起时刻及延 时信息,否则,丟弃该 Route request分组 (5)当中间节点收到 Route reply分组时,建立正向路由链表,向源节点转发该 Route Repy分组。 (6)当源节点S收到 Route reply分组时,通过1.6式判断延时是否满足,若满足则更新 路由表,在可行路由中选择延时最小的作为最佳路由,并发送数据包,否则,丢弃分组 图2是接收到RREQ后的处理过稈流程图,图3是接收到RREP后的处理过稈流程图 接收到RREP 更新路由 本节点是否是源节点 根据时间戳参数和当时时刻估计时延 将下游节点加入到本节点的正向路由链中 估计时延小于 到本节点的有效的 时延约束 反向路由是否存在 是 是 更新路由表 更新RRFP包的跳数 及源地址 发送缓冲区中的数据丢弃REP包立即向上游节点转发丢弃REP包 RREP包 更新反向路山链 结束 图2RRFP的过程流程图 24路由维护 移动 Ad hoc网终中节点的移动特性决定了网络的拓扑随时可能变化,建立的路由可能 断裂,也可能不再能提供所要求的QoS保证。因此,在 Ad hoc网终中,实时有效的QoS 路由维护也是非常必要的。 由于节点的移动可能造成己有链路的断裂,AODV提供了两种方法用以检测无线链路 的断裂。一是通过链峰层的反馈信息;二是通过路由层定期发送的 HELLO包。对于路由层 山国武技文在线 http://www.paper.edu.cn 的探测机制,具体的说,就是每个节点都定期( HELLO INTERVAL)广播 HELLO包,并且通 过收到的其他节点的Hel包米获得其邻节点的信息。如果在预定时间段( ELETE PERIOD) 内,节点没有收到某一邻节点的 Hello信息,便认为节点到这个邻节点的链路断裂了。如果 链路的断裂影响了正在传输数据的路由,那么源节点也将重新发起路由建立的过程。 本文的 RT QRP协议将利用路由层的反馈信息来测链路状态,原因是文献[4]中已经比 较上述两种检测方式的性能,并证明利用链路层的反馈信息在控制负载、路由建立时间、路 由恢复时间等方面的性能均优于利用路由层的定期广播机制 接收到RRFQ包 本节点是否是接收过此 Request包 否 史新广播链 更新反向路由链 史新路由表 本节点地址是否是 Request包 的目标节点地址 丢弃 是 否 RREQ包 估计的时延是否 满足时延要求 是 否 发送 Reply的 Request包 报文回复丢齐 Request包 并广播 销毁原 Request 报文 结束 图3RREQ过程流程图 3.增加备份路由机制 31备份路由的作用 根据本文延时估计模型所描述的,每次估计延时时都需要控制报文从源节点到日的节点 一个来回的时间,QoS路由的发现代价是很高的,当QoS路由发生断裂或是原QoS路由条 目失效时,源节点将不得不重新执行路由发现过程,这在大规模网络应用下,网络开销是相 当大的。此外,AODV采用的机制是将新找到的路由与路由表中的路由比较,如果新路由 较优,则用新路由条目覆盖旧的路由条目,否则丢弃新路由,然后发送数据,等待下一条新 的路由到来,显然这样做存在很大的局限性,在这和机制下,一些较优的可行的QoS路由 也被夭弃了。因此增加了各份路由机制能够有效的减少路重建的开销。 32备份路山的设计 关于备份路由的算法主要包括三个方面: 1)当源节点收到 Route reply包时,首先比较是否有新路由,如果有,则删除旧的路由条 山国利技记文在线 http://www.paper.edu.cn 目链,增加将新的QoS路由条目链,否则将新的QoS路由与同序刎号的路由条目上比较, 如果延时小于原来路由条目中最大的延时时,则覆盖掉旧的,并保持整个链表是有序的。否 则,丢弃新的QoS路由。 2)当路由发生断裂,源节点收到错误分组后,就必须查找备份路由,以取代现在的失效路 由。如果没有备份路由,则删除整个备份路由链,重启路由发现过程。 3)在所有路由条日中增加该链表上路由条日的计数和备份路由的链表。因为备份路由本身 要消耗资源,如果增加的备份路由链表过大,那么在存储上将占用大量的内存,在查找时也 会占去大量的查找时间,增大了延时,所以本文将新增加的链表上的计数设为3,即在有一 个最佳路由的情况下,最多只能有2个各份路由。并且这3个路由条目是按延时从小到大排 厅的,链头为最佳路由 4.协议正确性证明和复杂性分析 定理1 RT QRP协议的路山选择是无环的。 讦眀假设p是一个以D为目的探测帧,而S(P,D)是路山算法选择的路径。若S(PD) 中存在一个环路,则说明在路径S(P,D)上存在一个节点i两次收到了探测帧p并转发p。又 因为 RT QRP延用了原AODⅤ的广播机制,所以这与 RT QRP协议中根据<源地址,广播 ID>判断是否收到过该请求消息,如果收到过则丢弃请求消息矛盾,因此,S(P,D必定无环。 证毕。 定理2 RT QRP协议的路由算法中,时间复杂性为O(2h)。式中:h为 Ad hoc网络中 各条路径中链路数量的最大值。 证在 RT QRP协议的路由算法中,需要发送探测帧来建立跻由,成功建立一条路 径需要花费的时间开销是一个来回的时间。假设消息每绎过一条链路花费的时间开销是一个 单位,而假设h是被选择的多路径中链路数量的最大佰,则RT_QRP协议算法路径建立的 时问复杂性为O(2h),证毕。 5.仿真实现 51协议的修改 本次使用的仿真程序仅以延时作为参数,程序的实现是在ns-2.29版本下完成,主要对 ns2,29下的adv协议进行了修改,涉及到文件有 aodv packet. h, aodv packet co, aodv tcl, aodv table h, andy table. co, andy h, aodv. cc,上要修改內容如下: (1)修改路由条目,增加延时变量,备份路由链表及计数,并在构造函数中初始化。 (2)修改路由请求、回复包头,增加延时变量,并修改包头大小变量sz (3)修改 sendRequest、 recvRequest、 sendreply、 recvReply等函数 52性能评价参数 使用的性能评价参数主要包括: (1)平均分组投递率=目的端收到的数据包数/源端发送的数据包数 (2)路由控制开销=发送的路由控制分组总数/发送的数据分组总数。 3)平均端到端的延时-∑(数据分组i接收时刻一数据分组i发送时刻)接收数据分组总 数。 山国武技文在线 http://www.paper.edu.cn 5.3仿真环境和参数设定 (1)网络拓扑:随札分布节点数为100,场景在1200m*1200m的空问内。 (2)节点移动模式:节点随机移动,最大速凇40ms。 (3)节点通信模式:数据流类型:CBR,发包率为1.0,包大小为512 bytes (4)MAC协议:采用IFFF8Q2 (5)无线电传播模型:模型采用Two- Ray ground reflection modcl,载频是914MH,带 宽为2M。 (6)天线类型:天线用Omni△ ntenna 每个仿真取5个随机场景平均佰的结果,用脚本语言awk统计Ns2产生的裸数据,并 用 grupo工具作图。 5.4仿真结果分析 图4反映了在100个节点的网络中,不同网络连接数下, RT QRP协议的均包投递率 比AODⅴ协议要高,虽然当连接数增大时,总体上两协议都逞递减趋势,但连接数较大时, 两协议差距较人,特别是网络中连接数超过50个后。这是因为在协议中支持了延时约束和 各份路,体现了 RT QRP的优越性。 从图5可以看出, RT QRP办议的平均端到端的延迟比AODV要少很多,且随着网络 连接数的増大,虽然总体上逞递増趋势,但两协议延时比较有较差距,特别当连接数超过 50后,这是因为在协议中支持了延付约束的要求,整体上降低了网络中传输的延时 图4平均包投递率与连接数的关系 图5平均端到端的延时与连接数的关系 从图6可以看岀,不同连接数下的,路由控翎开销的变化情况,总体上,随着网络连接 数的增加,两协议都逞递増趋势,虽然 RT QRP协议的路由控制负载略高于AODV的,但 是并没有很大差距,特别当连接数超过50后, RT QRP的增加相比AODV更趋」平稳,这 是因为由于协议对延时的约束,导致在路径的选择中增加了许多控制报文,使得路由控訇负 载的增大,备份路由的机制也减少了些路由控制的负载,总体上达到了预期的效果。 图7反映了在100个节点的网络中,不同最大节点移动速度下,两协议的平均分组投递 率的变化情况, RT QRP协议的平均分组投递率比AODV协议要高,虽然当最大移动速度 增人时,总体上两协议都逞递减趋势,但最人移动速度较人时,两协议差距较人,特别是网 终中最人移动速度超过30后。这是因为在协议中支持了延时约束和备份路由,体现了 RT QRP的优越性。 -9 山国利技记文在线 http://www.paper.edu.cn 只0.5!c 一日一 和D 十da D 山 la< move sp 图6路由控制开销与连接数的关系 图7分组投递率与节点最大移动速度的关系 图8给出了在100个节点、连通度为30的网络中,不同的最大节点移动速度下,平均 端到端的延吋的变化情况,可以看出, RT QRP协议的平均端到端的延迟比AODV要少 随着最大移动速度的增大,两协议总体上逞递嶒趋势,但 RT QRP协议延吋增长较快,特 别当连接数超过30后,这是因为虽然在协议中支持了延时约束的要求,整体上降低了网络 中传输的延时,但是由于延时佔计模型的限制以及在高速网终环境下,网终变化太快给备份 路由机制带来了影响。 从图9可以看岀,不同最人移动速度下的,跻由控制开销的变化情况,总体上,随着最 大移动速度的增加,两协议都逞递増趋势,虽然 RT QRP协议的路由控制负载略高于AODVⅤ 的,但是并没有很大差距,特别当连接数超过30后, RT QRP的增加相比AODV更趋」 稳,这是因为由」协议对延时的约束,导致在略径的选择中增加了许多控制报文,使得嵱由 控制开销的增大,但备份路由的机翎减少了·些路由控制的开销,故劣势不明显。 RT_RP一 18Dw日一 9.5F AODV-A 0。14 器0.1 图8平均端到端的延时 图9路由控制开销节点 6.总结语 针对实时业务的需求,木文提出了基于延时约束的AODV改进协议 RT QRP。在 RT QRP中,当网络中存在延时约束的业务时,它基于最小延时来选择路由以满足业务对延 吋的需要,使用路由备份机制来减少不必要的重启路由发现带来的开销,实现在满足业务对 延时要求的同时还能让资源分配更优化。仿真结果表明,与经典的AODV协议相比, RT QRP 协议减少了路由开销,提高了包投递率,降低了延时,改善了网终的服务质量 目前 ad hoc网络中的QoS路由目标是选择满足QoS连接请水的一条或多条路由,同时 提供足够的路资源信息(如带宽、时延等),为管理控制机制(如接受呼叫等)提供支持,最

...展开详情
试读 11P 论文研究-基于延时约束的AODV改进协议 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_39840588 如果觉得有用,不妨留言支持一下
2019-08-17
上传资源赚积分or赚钱
最新推荐
论文研究-基于延时约束的AODV改进协议 .pdf 10积分/C币 立即下载
1/11
论文研究-基于延时约束的AODV改进协议 .pdf第1页
论文研究-基于延时约束的AODV改进协议 .pdf第2页
论文研究-基于延时约束的AODV改进协议 .pdf第3页

试读结束, 可继续读1页

10积分/C币 立即下载 >