（通信与信息系统专业论文）ad+hoc网络中的qos多播路由协议研究.pdf

i l ll li ll 1 ll lll li llll n 溅i nt e l e c o 吼u n i c a 6 0 璐粕di l l f o n n a 舶ns y s t e 麟 y 18 4 2 9 6 4 r e s e a r c ho nm u l t i c a s t r o u t i n gp r o t o c o l sw i t h q o sg u a r a n t e e di na dh o cn e t w o r k s b yw a n g y u c h e n s u p e r v i s o r ：a s s o c ia t ep r o f e s s o ry u a np i n g n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 j 1 一 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 = 也 思。 学位论文作者签名：气叱端 日期：沙留1 8 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 立 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半口两年酉 k c ， 学位论文作者签名：孤埸 签字日期：枷可f 五万 导师签名：溥磊 签字日期：洲羽 一会上 一、 _ t 、， i 一， r 一一一 ) r 2 东北大学硕士学位论文 a b s t r a c t a dh o c 网络中的o o s 多播路由协议研究 摘要 随着无线通信技术的发展和便携设备的不断普及，人们对新的移动通信服务的需求 与f 1 俱增。顺应这一趋势，作为一种多跳、无中心、自组织的a dh o c 越来越收到关注， 成为研究的热点网络之一。近年来的研究成果表明，多播成为a dh o c 网络路由首选的 方式，而q o s ( q u a l i t yo f s e r v i c e ) 多播路由又充分考虑到了a dh o c 网络这种带宽资源紧 张、系统资源有限的网络环境。 多播是一种面向群组计算的通信传播方式，它是将数据发送给由一个目的地址指定 的一组节点。论文研究的a dh o c 网络多播路由是考虑了带有q o s 约束的那样一组节点。 从而就服务质量主要包含的延迟、延迟抖动、带宽、代价等q o s 约束，给出了一种适应 于a dh o c 网络q o s 多播路由的网络模型，提出了a dh o c 网络中一种具有多q o s 约束 的多播路由协议q m r p a ( q o sb a s e dm u l t i c a s tr o u t i n gp r o t o c o l i nm o b i l ea dh o c n e t w o r k s ) 。q m r p a 协议基于可行链路的定义，分两个步骤完成多播树的建立，首先建 立从多播源节点到某多播目的节点满足多q o s 约束的单一链路构成初始多播树，其次， 多播目的节点再申请加入多播树中。在路由过程中每个节点只需要了解相邻节点的信息 而不必掌握全局信息，提高了路由的成功率，降低了算法实现的复杂度。同时给出了 q m r p a 中多播树的修剪和维护的过程，并设计了路由备份机制，进行了正确性证明和 复杂性分析。根据分簇结构，对q m r p a 进行了改进，提出了具有多q o s 约束的分簇 多播路由协议q m r p a c l 。协议中每个簇内节点只需要维护本簇的簇内信息，每个桥 节点需要维护簇内的主要信息和在这个高级簇内的其他同等级簇的相关信息，每个节 点能够在满足q o s 约束下快速动态加入多播树。仿真实验结果表明，q m r p a 是有效的， 且为a dh o c 网络解决带有多q o s 约束多播路由问题提供了一种新的思路。 关键词：a d h o c 网络：多播路由；q o s 路由 一i i 一 劳上 。 ， t 二一 飞 一 3 4 土 k x f 7 s i n g l ed e s t i n a t i o na d d r e s s t h i st h e s i sm a i n l yr e s e a r c hm u l t i c a s tr o u t i n gp r o t o c o lf o ra dh o c n e t w o r k , w h i c hc o n s i d e r sq o sc o n s t r a i n t so ft h eg r o u po fn o d e s f o rt h es e r v i c eq u a l i t i e s ，i t m a i n l yd e a l sw i t ht h ed e l a y ，d e l a yj i t t e r ，b a n d w i d t ha n dc o s tm e t r i c s ，a n dd e s c r i b e san e t w o r k m o d e lf o rr e s e a r c h i n gt h em o b i l ea dh o cn e t w o r k sq o sm u l t i c a s tr o u t i n gp r o b l e m ，t h e n p r e s e n t saq o sb a s e dm u l t i c a s tr o u t i n gp r o t o c o li nm o b i l ea dh o cn e t w o r k s ( q m r p a ) q m r p ai sb a s e do nt h ed e f i n i t i o no ff e a s i b l el i n k s ，a n du s e st w os t e p st o c o m p l e t et h e e s t a b l i s h m e n to fm u l t i c a s tt r e e f i r s to fa l l ，e s t a b l i s ha s i n g l el i n kf r o mt h em u l t i c a s ts o a r c et o ad e s t i n a t i o nn o d e ，w h i c hs a t i s f i e s t h em u l t i p l eq o sc o n s t r a i n t s ，t oc o n s t i t u t et h ei n i t i a l m u l t i c a s tt r e e s e c o n d l y ，o t h e rd e s t i n a t i o nn o d e sj o i nt h em u l t i c a s tt r e e i nt h ec o w s e o fe a c h r o u t i n gp r o c e s s ，e a c hn o d eo n l yn e e d st ok n o wt h ei n f o r m a t i o no fa a j a c e n tn o d e s ，w i t h o u t h a v i n gt og r a s pt h eo v e r a l li n f o r m a t i o n t h i si m p r o v e st h es u c c e s sr a t eo ft h er o u t i n ga n d r e d u c e st h ec o m p l e x i t yo ft h ea l g o r i t h m a tt h es a m et i m e ，t h et h e s i sg i v e st h ep r o c e s so f p r u n i n ga n dm a i n t e n a n c e ，a n dd e s i g n st h er o u t i n gb a c k u pm e c h a n i s m t h e p r o o fo f c o r r e c t n e s sa n dt h ec o m p l e x i t ya n a l y s i so ft h eq m r p a a r ea l s og i v e n i ta l s od e s c r i b e sa m u l t i c a s tr o u t i n gp r o t o c o lw i t h m u l t i p l eq o sc o n s t r a i n t si nc l u s t e r i n gm o b i l ea dh o c n e t w o r k s ( q m r p a - c l ) ，w h i c hi m p r o v e do nq m r p a i nt h i sp r o t o c o l ，e a c hi n t r a c i u s t e rn o d e o n l yn e e d st om a i n t a i ni t sc l u s t e r sr o u t i n gi n f o r m a t i o n ，a n dt h ee a c hb r i d g en o d en e e dt o m a i n t a i nt h ec l u s t e ri na n dt h es u m m a r yi n f o r m a t i o no fo t h e rs 锄e l e v e lc l u s t e r so ft h i s h i g h e l l e v e lc l u s t e r t h eq m r p a - c la l s oa l l o w sa n ya dh o cg r o u pm e m b e rc a nj o i l e a v e t h em u l t i c a s tg r o u pd y n a m i c a l l y ，a n ds u p p o r t sm u l t i p l eq o sc o n s t r a i n t s t h ep e r f o r m a n c eo f q m r p ai se v a l u a t e du s i n gs i m u l a t i o n t h es t u d i e ss h o wt h a tq m r p a i se f f e c t i v e a n d p r o d e san e ws o l u t i o nt om u l t i c a s tm u t i n gd e c i s i o nw i t h m u l t i p l eq o sc o n s t r a i n t sf o r t t l 一 p；矿 m o b i l ea dh o cn e t w o r k s k e yw o r d s ：a dh o cn e t w o r k s ；m u l t i c a s tr o u t i n g ；q o sm u t i n g ， f - _ 吩 一 - v 簟 二 f 工 l i 、 ， 、1 广 o 东北大学硕士学位论文目录 目录 声明i 中文摘要i i a b s t r a c t i i i 第1 章绪论二1 1 1 课题背景1 1 2a dh o c 网络特点与应用l 1 3a dh o c 网络多播路由协议研究现状3 1 4 研究的目的与意义4 1 5 论文的组织结构5 第2 章a dh o c 网络的多播路由协议7 2 1 多播的概念7 2 2a dh o e 网络多播路由协议参考模型8 2 3a dh o e 网络多播路由协议1 0 2 3 1 基于树的多播路由协议j1 2 2 3 2 基于格网的多播路由协议1 6 2 3 3 混合多播路由协议：2 0 2 3 4 无状态的多播路由协议j 2 1 2 4 移动a dh o c 网络多播路由协议比较2 3 2 5 小结2 4 第3 章a d h o c 网络中q o s 多播路由协议一q m r p a 2 5 3 1 设计思路一2 5 3 2q m r p a 网络模型及问题描述2 7 3 2 1 网络模型2 7 3 2 2 多约束q o s 多播路由问题2 7 3 2 3 端到端的时延估计3 0 3 3q m r p a 协议描述3 3 3 3 1 控制报文格式3 3 3 3 2 初始多播树的建立3 7 3 3 3 目的节点的动态加入3 9 3 3 4 节点的维护过程4 1 一v 一 东北大学硕士学位论丈目 录 3 3 5 节点的剪除4 1 3 4 增加备份路由机制4 2 3 4 1 备份路由的有效性和可行性4 2 3 4 2 备份路由的设计4 2 3 4 3 多播路由维护4 3 3 5 协议j 下确性证明及复杂性分析4 51 3 6 、结4 6 第4 章q m r p a 仿真及性能分析：4 7 4 1 仿真背景及场景4 7 4 1 1 仿真工具4 7 4 1 2 仿真设置4 8 4 2q m r p a 在n s 上的实现5 0 4 2 1q m r p a 组播路由实现5 0 4 2 2 节点中需要维护的数据结构5 3 4 3 性能指标的选择5 4 4 4 仿真结果及分析5 5 。 4 4 1 多播组大小对网络性能的影响5 5 4 4 2 节点运动速度对网络性能的影响5 7 ， 4 4 3 延时约束对网络性能的影响5 9 4 5 月、结6 0 第5 章分簇基础上的改进一q m i 心a c l 6 1 5 1 设计思路6 1 5 2 分簇m a n e t 及网络模型6 1 孓3 q m 氅曼。婪：= y 巧3i ， 5 3 1 初始多播树的建立6 3 。 ， 5 3 2 目的节点的动态加入6 4 5 4 协议正确性证明及复杂性分析6 6 5 5 小结6 6 第6 章结论6 7 6 1 论文工作6 7 6 2 未来研究方向6 8 参考文献6 9 o ，产1 ，2 ，尸， 存在一组实数亭，产1 ，2 ，p ，使得x 宰是： j p m a x 彬乃( x ) ； ，l l s t 艄童 j ，j _ 、，2 ，p 五酬 i 的一个最优解。通过变动( 卣，受，己) 的取值，求解一系列上述问题，就可以得到近似 的非劣解集。 。 在多度量参数的q o s 路由选择问题中，通过对乘性q o s 参数进行对数变换，对凹 性q o s 参数进行加权或倒数变换，这样多参数q o s 问题最终将被转换成为多项式加法 求极值的多目标决策问题。假如在多度量q o s 问题中，决策空间x = 伍，翰) 1 分别 对应( 剩余带宽、延迟、节点剩余能量、费用、跳数等) ，则目标函数力 ) ，石 ) 分 别表示路径p 上的可用带宽函数、延迟函数、剩余能量函数、延迟抖动函数、丢包率函 数等。通过对相关乘性和凹性函数进行对数和加权或倒数变换，采用混合法，可以得到 如下q o s 路由的一般数学模型： 一2 r 一 东北大学硕士学位论文第3 章a d h o c 网络中q o s 多播路由协议一q m 砌狐 p m i n 矽乃( 工) ； 宅l s f - f , f x ) 耋孝，户l ，2 ，p 工甜 其中，x 为包括x 在内的节点和链路属性，孝，为链路的一组临界指标，w , 0 为一组 p 权值。通常取嵋o ) = l ，彬 o ，1 。 j 年l 设p = 4 ，f = ( b ，d ，j ，c ) ( 分别表示路径的带宽、延迟、延迟抖动和链路费用) ，取 w = ( 钟，川，嵋，川) = ( o ，0 ，0 ，1 ) ，则问题转化成为在满足带宽和延迟的条件下， 求链路费用最大的问题。 因此，在多目标q o s 路由问题中，根据不同业务对特定指标的不同要求，可以根据 每次赋予的不同的权值，求得一组路径，然后在这些路径集合中按照具体规则进行选优。 在a dh o c 网络g = 形习中，若s z - 2 为一棵组播树的源节点，m 为该组播树的目的 节点或叶节点集。设r 为正实数集，r 为非负实数集。对于任意链路e e ，可定义某些 q o s 特征值：带宽函数b a n d w i d t h ( 矽：e 瑚，延迟函数d e l a y ( e ) ：e 嘲，延迟抖动函数 d e l a y _ j i t t e r ( e ) ：e 哪+ ，传输费用函数c 吖砂：e 瑚。类似地， 对于任一节点，z n 也可定义某些q o s 特征值：延迟函数d ( n ) - y 瑚， 传输费用函数c 例：瑚，延迟抖 动函数孝f ，砂? y 瑚+ 。令吖s ，岣表示组播树，其相互关系如下： ( 1 ) b a n d w i d t h ( p ( s ，圳= r a i n b a n d w i d t h ( e ) ，e p ( s ，彬 ( 2 ) & t a y ( p ( s ，圳= 嘶，) d e l a y ( e ) + 榔_ f ) d ( ，z ) ( 3 ) d e a l y - j i t t e r 匆侮，圳= 二r ) d e l a y j i t t e ，_ ( p ) + 榔f ) 够( 玎) ( 4 ) c o s t ( t ( s , m ) ) = 村，) c os t ( e ) + 脚幢，) c 例 其中，p ( s ，砂为多播树耶，蚴上源点s 到目的节点f 的路由路径。则多约束q o s 多播 路由问题可以描述为寻找一棵多播树砸朐满足如下q o s 约束： ( 1 ) 带宽约束：b a n d w d t h ( p ( s ，纠既加； ( 2 ) 延迟约束：d e l a y 6 d ( s , 纠d m a x ； ( 3 ) 延迟抖动约束：d e a l y - j i t t e r ( p ( s ，圳； ( 4 ) 费用约束：在所有满足( 1 ) ( 3 ) 条件的组播树中，c o s t ( t ( s ，删尽可能最 小。 其中，b f i l i 。是带宽约束，d 撇；和j n 砒分别是延迟和延迟抖动约束。 一2 9 东北大学硕士学位论文第3 章a dh o c 网络中q o s 多播路由协议一q m 砒，a 3 2 3 端到端的时延估计 破 q m r p a 协议中q o s 约束包括端到端时延，那么有必要通过有效的方法对端到端时 “ 延进行估计，从而获得较为准确的q o s 指标。对于同步网络，端到端的时延是很容易计 算的。只要用目的节点收到数据包的时刻减去源节点发送数据包的时刻就可以了。 。 在异步网络中，这个问题就变得复杂起来。根据q m r p a 协议中初始多播树的建立 过程( 即多播源节点广播路由请求报文r e q u ，目的节点收到路由请求报文即按照翻转路 径向源节点返回路由回答报文r p l y ) ，可以考虑利用这个建立过程的双向时延( 源节点一 目的节点一源节点) 来估算下行时延( 源节点一目的节点) 。下面将证明这个估算是合理 的： 首先给出端到端时延t 的定义： 定义1 端到端时延d ：报文从源端发出，到被目的端正确接收所经历的时间延迟。 单位为秒。 d = ，( d f ( ，) ) + d j d ( j ) + d 如( s ，丁) ， ( 3 1 ) 其中，i 为选定路由包括的各节点，s 为源节点，t 为目的节点，d ，为数据包的传输 时延，岛为处理时延。9 脚为信号在无线信道中的传播时延，它们进一步可以表示为： d = s 啦| b a ( 1 )0 砩= d w + 乃( 3 3 ) 其中虢为数据包的大d , ( l g 特) ，玩为节点i 实际能够利用的有效带宽( 比特秒) ， 砩为数据包在节点i 的处理时间( 秒) ，它又包括了在节点i 的队列中的等待时间d w 和 真正的数据包被处理的时间d d 。 对于多媒体文件来说，其传输所要求的平均时延必须满足 d 2 d 卅口, - d a _ f f f ld ，s 2 d 用o x 、 d d 孵f2 d 懈 相对于d m 烈，d d i f f f l c j 值是很小的。而且，d d 批值只与源节点、目的节点的队列等待 时间有关，与所选择的路由基本没有关系。因此，用d ，2 ，来估计d 加是合理的。 还需要说明的是，在带宽条件满足的情况下，网络能够为数据流的传输提供稳定的 时延，因此推断如果路由建立过程中估算的传输时延能够满足数据流的时延要求，那么 数据流实际传输的时延也能满足要求。 这样就能得到：当源节点收到来自目的节点的路由回复( 能够收到的路由回复都是 满足时延要求的) 时，根据当前时间与其发送路由要求的时间算出d ，并与数据流允许 的最大时延作比较，最终决定是否可以利用这条路由来传输数据流。即当d r s 2 d 小甜时， 能够传输数据流；当d r 2 d 朋甜时，不能传输数据流。 在q m r p a 协议初始多播树建立过程中，当多播源节点发送的路由请求报文r e q u - 到达目的节点时，如果此时的d d o m 已经超过了d 小时，即d d 0 跏 d 朋甜时，此时此刻该 路由已经不满足时延了，所以可以直接丢弃该报文。 同理，q m r p a 协议中，在目的节点请求加入多播树时，即目的节点广播请求加入 报文j o i n ，多播树节点接收到请求加入报文时，即按照翻转路径向目的节点返回请求回 复报文r a c k ) ，可以考虑利用这个建立过程的双向时延( 目的节点x 一多播树节点z 一目 的节点x ) 来估算下行时延( 目的节点一多播树节点) 。 因为多播树节点均存储链路信息表l t ，所以多播树节点的存储链路信息表中存储着 从多播树源节点到树节点z 的时延以z ) ，这样就能得到：当目的节点x 收到来自多播树节 点z 的路由回复( 能够收到的路由回复都是满足时延要求的) 时，根据当前时间与其发送路 由要求的时间算出d ，并与数据流允许的最大时延d 历甜减去多播树源节点到多播树节点 的时延以z ) 作比较，最终决定是否可以利用这条路由来传输数据流。即当d ，s2 ( 9 一一吠z ) ) 时，能够传输数据流；当d r 2 ( d 一吠z ) ) 时，不能传输数据流。 在q m r p a 协议的多播节点加入过程中，当多播源节点发送的路由请求报文r e q u 。 到达目的节点时，如果此时的d 如硼已经超过t d 聊a x - d ( z ) 时，即砒m d m a x - - 战z ) 时，此 一3 2 一 ， j 东北大学硕士学位论文第3 章a dh o c 网络中q o s 多播路由协议一q m r p a 时此刻该路由已经不满足时延了，所以可以直接丢弃该报文，没有必要再去统计研了， 这样减少了一定的路由开销。 3 3q m r p a 协议描述 在本节将描述一种基于延迟、延迟抖动、带宽、费用约束的q o s 多播路由协议( q o s b a s e dm u l t i c a s tr o u t i n gp r o t o c o li nm o b i l ea dh o c n e t w o r k s ，q m r p a ) ，在q m r p a 协议中， 定义了相邻节点之间的可行链路；在路由过程中，首先建立从多播源节点到某多播目的 节点满足多q o s 约束的单一链路构成初始多播树，其余多播目的节点再申请加入多播树 中，达到了快速高效建立满足多q o s 约束多播树的目的。 定义2 若节蔚为节点i 的相邻节点，链路e ( f ，力钮，并且d ( s ，0 和孝p ，0 分别表示 从多播源节点s 到节点f 的延时值之和和延时抖动之和，如果链路e 满足：( b a n d w i d t h ( e ) 三b 小i 。s u t ( s ，f ) + d e l a y ( e ) ) s 玩甜( d j ( s ，d + d e 伽一j i t t e r ( e ) ) s 厶似则称链路e 为满足q o s 约束的可行链路。 定义3 树节点集口中的节点均存储链路信息表l t ( n o d e ，u p n o d e ，d ( n o a e ) ，d j c n o d e ) ， e ( n o d e ) ) ，l t 主要记载某节点( n o d e ) 到源节点s 的延时值( d ( n o d e ) ) 、延时抖动值 ( c i f 向d 圳) 以及费用( c ( n o d e ) ) 等q o s 约束信息，同时记载该节点在树中的父节点( u p n o d e ) 。 3 3 1 控制报文格式 q m r p a 协议的路由控制报文主要有以下几种类型：路由请求报文r e q u 、路由回 答报文r p l y 、请求加入报文j o i n 和加入确认报文r a c k 。 ( 1 ) 路由请求报文r e q u 格式： r e q u 报文格式如图3 1 ： 一3 3 东北大学硕士学位论文第3 章a d h o e 网络中q o s 多播路由协议一q m r p a 报文类型( 8 b i t ) 保留字段( 1 6 b i t ) 跳数( 8 b i t ) r e q ui d ( 3 2 b i t ) 目的i p 地匀l ( 3 2 b i t ) 目的i p 序列号( 3 2 b i t ) 源i p 地j ( 3 2 b i t ) 源i p 序列号( 3 2 b i t ) 延时d ( 3 2 b i t ) 延时抖动j ( 3 2 b i t ) 最小带宽b ，加( 3 2 b i 0 费用c d ( 3 2 b i t ) 路径p a t h 图3 1 路由请求报文( r e q u ) f i g 3 1r o u t i n gr e q u e s tm e s s a g e ( r e q u ) 其中： r e q ui d ：r e q ui d 和源i p 地址联合起来标志一个独一无二的r e q u 报文。 目的序列号：目的节点收到的来自源节点的所有序列号中的最新( 最大) 值。 源序列号：源节点路由表项中的当前序列号。 延时d ：在多播源节点时的初始值为0 ，延时约束d 棚甜，报文每经过个节点，延 时d 就会累加，所以报文到达某个节点时的d 值就是从源节点到这个节点之间的延迟 累加值，到达的每个节点都会把这个值存储到链路信息表l t 中的d ( n o d e ) 中。 延时抖动 在多播源节点时的初始值为0 ，延时抖动约束厶甜，报文每经过一个节 点，延时抖动，就会累加，所以报文到达某个节点时的，值就是从源节点到这个节点之 间的延迟抖动累加值，到达的每个节点都会把这个值存储到链路信息表l t 中的a j ( n o d e ) 中。 最小带宽b 胁：q o s 约束中的最小带宽值。 费用c d ：在多播源节点时的初始值为o ，报文每经过一个节点，费用c d 就会累加， 所以报文到达某个节点时的c d 值就是从源节点到这个节点之间的费用累加值，到达的 每个节点都会把这个值存储到链路信息表l t 中的c ( n o d e ) 中。 路径p a t h ：从多播源节点到处理该请求的节点的路径。 ( 2 ) 路由回答报文p p l y 格式： r p l y 报文格式如图3 2 ： 3 4 东北大学硕士学位论文第3 章a dh o c 网络中q o s 多播路由协议一q 愀 报文类型( 8 b i t )保留字段( 1 6 b i t l 跳数( 8 b i t ) 目的i p 地址( 3 2 b i t ) 目的i p 序列号( 3 2 b i t ) 源i p 地址( 3 2 b i t ) 生存时间( 3 2 b i t ) 路径p a t h 图3 2 路由回答报文( i 啦l y ) f i g 3 2r o u t i n gr e p l ym e s s a g e ( r p l y ) 其中： 生存时间：节点收到r p l y 后考虑的路由有效时间。这个值是在目的节点中继节 点应答r p l y 时确定的，当源节点收到该r p l y 时利用该值设置对应路由表项的超时时 间，以和目的节点中继节点的路由表项生存期一致。 ( 3 ) 请求加入报文j o i n 格式： j o i n 报文格式如图3 3 ： 报文类型( 8 b i t )保留字段( 1 6 b i t )跳数( 8 b i t ) j o i ni d ( 3 2 b i t ) 目的口地j q k ( 3 2 b i t ) 目的i p 序列号( 3 2 b i t ) 多播源i pj 勘k ( 3 2 b i t ) 多播源腰序列号( 3 2 b i t ) 请求延时d ( 3 2 b i t ) 请求延时抖动，( 3 2 b i t ) 请求最小带宽b 。跏( 3 2 b i t ) 请求费用c d ( 3 2 b i t ) 路径p a t h 图3 3 请求加入报文( j o i n ) f i g 3 3j o i nr e q u e s tm e s s a g e ( j o i n ) 其中： 请求延时d ：在目的节点时的初始值为延时约束口一，减去报文经过的链路延时， 到达处理该请求的节点时所剩的值为d 。 请求延时抖动，：在目的节点时的初始值为延时抖动约束厶烈，减去报文经过的链 路延时抖动，到达处理该请求的节点时所剩的值为，。 一3 5 查! ! 查兰翌主兰堡笙圭箜3 章a d h o c 网络中q o s 多播路由协议一q m 褂) a 二二= 2 二二二= ：= i 二! 竺 型竺 请求最小带宽如伽：q o s 约束中的最小带宽值。 请求费用c d ：从目的节点到处理该请求的节点的链路费用，c d = 0 表示初始的链路 费用。 路径p a t h ：从目的节点( 请求节点) 到处理该请求的节点的路径。 ( 4 ) 加入确认报文r a c k 格式： r a c k 报文格式如图3 4 ： o 东北大学硕士学位论文第3 章a d h o c 网络中q o s 多播路由协议一q m 砌) a w ：链路错误标志，当发现了不可达( 移动或损坏) 的节点或链路，由发现不可达 节点或链路的节点向源节点和目的节点回送错误分组。 3 3 2 初始多播树的建立 在多播路由建立前，由源节点s 以某多播目的节点t i ( 厶曰) 为目的节点构造一个有 唯一标识的路由请求报文r e q u ，r e q u 包含源节点、目的节点、q o s 约束要求以及跳 数等信息。开始路由建立时，首先由源节点5 向其具有可行链路的相邻节点广播报文 r e q u 。 节点发送完报文r e q u 后，如果在r e q u w a i t t i m e 时间内没收到路由回答报文 r p l y ，节点重新广播报文r e q u ，如果节点在重试次后，仍然没收到i 冲l y ，则认为在 该网络内没有那个多播组的成员。 当某节蔚接收到由节点f 转发来的r e q u 报文时，节蔚作如下处理： ( 1 ) 如果节蔚非目的节点t i 且已经接收过报文r e q u ，则丢弃该报文，结束处理。 否则转2 。 ( 2 ) 节蔚将节点f 作为其父节点，节蔚作已接收r e q u 报文的标志，并更新自 身的链路信息表l t ：节蔚的标识号一聆d 比；节点f 的标识号- - - ，u p n o d e ；d ( i ) + d e l a y ( i ， 一划；砂+ d e l a y _ j i t t e r ( i ，_ 谚；c 何+ c o s t ( i , j ) _ c ；然后将节向加入树节点集口 中，将链路( f ，) 加入到r e q u 报文的链路信息中，转3 。 ( 3 ) 如果节蔚非目的节点t ，则节蔚在其相邻节点中寻找没有接收r e q u 报文 标志且具有可行链路的节点广播该报文r e q u ，结束处理。否则转4 。 当节点，不能找到满足条件的相邻节点转发报文，则丢弃报文，并删除集合口中的 节蔚，撤消报文链路信息中( f ，力的内容，撤消节点，的接收r e q u 报文的标志，并相对 节点i 将节点，作上标志，同时让节点i 重新选择可行链路广播报文r e q u 。 ( 4 ) 节点，为目的节点t i ，则节点t i 在规定的时间间隔内将收到的所有请求报文中 c 0 9 值最小者作为本次路由请求的结果，沿报文r e q u 蛰j 达的链路信息向源节点发送路由 回答报文r p l y ，进行资源预留；而其它报文记载的链路信息作为备用路由信息被保存。 当确认报文到达源节点时，即建立了由源节点s 到目的节点满足q o s 约束的单一链路， 形成初始多播树。 初始多播树建立过程中的中间节点流程如图3 6 所示： 一3 7 查! ! 查兰塑主兰堡垒丈 第3 章a d h o c 网络中q o s 多播路由协议一o m 砌) a 一一 一二- = - 二 ： ：= ：- 二：= ： 一 0 东北大学硕士学位论文第3 章a dh o e 网络中q o s 多播路由协议一q m 砒) a 当路由回答报文r p l y 到达源节点时，即建立了由源节点s 到目的节点满足q o s 约 束的单一链路，形成初始多播树。 3 3 3 目的节点的动态加入 当生成单链路的初始多播树琊后，多播目的节点集m 中除t i 夕 、的其余节点再动 态申请加入中。如果某多播目的节点t j ( t je m 一 f i ) ) ) 申请加入砸加中，首先 判断岛q 是否成立，成立则说明节点务已经是多播树中的成员节点，则申请工作完成； 否则节点构造一个具有唯一标识的请求加入报文j o i n 。当节点厶发起请求加入报文 j o i n 时，把本节点地址加入阳砌中，然后由节点务向其具有满足q o s 约束可行链路的相 邻节点广播该报文j o i n 。 当某节点p 接收到由节点g 发送来的j o i n 报文，做如下处理： ( 1 ) 如果节点p 已经接收过报文j o i n ，则丢弃该报文，结束处理。否则转2 。 ( 2 ) 节却置已接收报文j o i n 标志，并对报文做如下处理：将链路( g ，p ) 加入至呐口砌 中，且使c d = c d + c o s t ( q ，力，d = d 一如缸) ，( g ，p ) ，= ，一d e l a y _ j i t t e r ( q ，p ) ，转3 。 ( 3 ) 判断条件p 刃是否成立，若不成立说明节点p 不是多播树中的节点，转 s t e p 4 。否则再判断条件烈p ) s d & d j ( p ) 茎是否成立，若不成立，则撤消节点p 接收 报文j o i n 的标志，在p a t h 中撤消( g ，p ) ，丢弃该报文，结束处理；否则，节却向目的 节点务发送加入确认报文r a c k ，结束处理。 ( 4 ) 节点p 在其相邻节点中寻找没有接收j o i n 报文标志且具有可行链路的节点广 播该报文j o i n ，结束处理。 目的节点的动态加入过程