（通信與信息系統(tǒng)專業(yè)論文）ad+hoc網(wǎng)絡(luò)中的qos多播路由協(xié)議研究.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 一 獨(dú)創(chuàng)性聲明 本人聲明，所呈交的學(xué)位論文是在導(dǎo)師的指導(dǎo)下完成的。論文中取得 的研究成果除加以標(biāo)注和致謝的地方外，不包含其他人己經(jīng)發(fā)表或撰寫過 的研究成果，也不包括本人為獲得其他學(xué)位而使用過的材料。與我一同工 作的同志對(duì)本研究所做的任何貢獻(xiàn)均己在論文中作了明確的說明并表示謝 = 也 思。 學(xué)位論文作者簽名：氣叱端 日期：沙留1 8 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者和指導(dǎo)教師完全了解東北大學(xué)有關(guān)保留、使用學(xué)位論 文的規(guī)定：即學(xué)校有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和 磁盤，允許論文被查閱和借閱。本人同意東北大學(xué)可以將學(xué)位論文的全部 或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索、交流。 立 作者和導(dǎo)師同意網(wǎng)上交流的時(shí)間為作者獲得學(xué)位后： 半年口一年口一年半口兩年酉 k c ， 學(xué)位論文作者簽名：孤埸 簽字日期：枷可f 五萬(wàn) 導(dǎo)師簽名：溥磊 簽字日期：洲羽 一會(huì)上 一、 _ t 、， i 一， r 一一一 ) r 2 東北大學(xué)碩士學(xué)位論文 a b s t r a c t a dh o c 網(wǎng)絡(luò)中的o o s 多播路由協(xié)議研究 摘要 隨著無(wú)線通信技術(shù)的發(fā)展和便攜設(shè)備的不斷普及，人們對(duì)新的移動(dòng)通信服務(wù)的需求 與f 1 俱增。順應(yīng)這一趨勢(shì)，作為一種多跳、無(wú)中心、自組織的a dh o c 越來越收到關(guān)注， 成為研究的熱點(diǎn)網(wǎng)絡(luò)之一。近年來的研究成果表明，多播成為a dh o c 網(wǎng)絡(luò)路由首選的 方式，而q o s ( q u a l i t yo f s e r v i c e ) 多播路由又充分考慮到了a dh o c 網(wǎng)絡(luò)這種帶寬資源緊 張、系統(tǒng)資源有限的網(wǎng)絡(luò)環(huán)境。 多播是一種面向群組計(jì)算的通信傳播方式，它是將數(shù)據(jù)發(fā)送給由一個(gè)目的地址指定 的一組節(jié)點(diǎn)。論文研究的a dh o c 網(wǎng)絡(luò)多播路由是考慮了帶有q o s 約束的那樣一組節(jié)點(diǎn)。 從而就服務(wù)質(zhì)量主要包含的延遲、延遲抖動(dòng)、帶寬、代價(jià)等q o s 約束，給出了一種適應(yīng) 于a dh o c 網(wǎng)絡(luò)q o s 多播路由的網(wǎng)絡(luò)模型，提出了a dh o c 網(wǎng)絡(luò)中一種具有多q o s 約束 的多播路由協(xié)議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 協(xié)議基于可行鏈路的定義，分兩個(gè)步驟完成多播樹的建立，首先建 立從多播源節(jié)點(diǎn)到某多播目的節(jié)點(diǎn)滿足多q o s 約束的單一鏈路構(gòu)成初始多播樹，其次， 多播目的節(jié)點(diǎn)再申請(qǐng)加入多播樹中。在路由過程中每個(gè)節(jié)點(diǎn)只需要了解相鄰節(jié)點(diǎn)的信息 而不必掌握全局信息，提高了路由的成功率，降低了算法實(shí)現(xiàn)的復(fù)雜度。同時(shí)給出了 q m r p a 中多播樹的修剪和維護(hù)的過程，并設(shè)計(jì)了路由備份機(jī)制，進(jìn)行了正確性證明和 復(fù)雜性分析。根據(jù)分簇結(jié)構(gòu)，對(duì)q m r p a 進(jìn)行了改進(jìn)，提出了具有多q o s 約束的分簇 多播路由協(xié)議q m r p a c l 。協(xié)議中每個(gè)簇內(nèi)節(jié)點(diǎn)只需要維護(hù)本簇的簇內(nèi)信息，每個(gè)橋 節(jié)點(diǎn)需要維護(hù)簇內(nèi)的主要信息和在這個(gè)高級(jí)簇內(nèi)的其他同等級(jí)簇的相關(guān)信息，每個(gè)節(jié) 點(diǎn)能夠在滿足q o s 約束下快速動(dòng)態(tài)加入多播樹。仿真實(shí)驗(yàn)結(jié)果表明，q m r p a 是有效的， 且為a dh o c 網(wǎng)絡(luò)解決帶有多q o s 約束多播路由問題提供了一種新的思路。 關(guān)鍵詞：a d h o c 網(wǎng)絡(luò)：多播路由；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 東北大學(xué)碩士學(xué)位論文目錄 目錄 聲明i 中文摘要i i a b s t r a c t i i i 第1 章緒論二1 1 1 課題背景1 1 2a dh o c 網(wǎng)絡(luò)特點(diǎn)與應(yīng)用l 1 3a dh o c 網(wǎng)絡(luò)多播路由協(xié)議研究現(xiàn)狀3 1 4 研究的目的與意義4 1 5 論文的組織結(jié)構(gòu)5 第2 章a dh o c 網(wǎng)絡(luò)的多播路由協(xié)議7 2 1 多播的概念7 2 2a dh o e 網(wǎng)絡(luò)多播路由協(xié)議參考模型8 2 3a dh o e 網(wǎng)絡(luò)多播路由協(xié)議1 0 2 3 1 基于樹的多播路由協(xié)議j1 2 2 3 2 基于格網(wǎng)的多播路由協(xié)議1 6 2 3 3 混合多播路由協(xié)議：2 0 2 3 4 無(wú)狀態(tài)的多播路由協(xié)議j 2 1 2 4 移動(dòng)a dh o c 網(wǎng)絡(luò)多播路由協(xié)議比較2 3 2 5 小結(jié)2 4 第3 章a d h o c 網(wǎng)絡(luò)中q o s 多播路由協(xié)議一q m r p a 2 5 3 1 設(shè)計(jì)思路一2 5 3 2q m r p a 網(wǎng)絡(luò)模型及問題描述2 7 3 2 1 網(wǎng)絡(luò)模型2 7 3 2 2 多約束q o s 多播路由問題2 7 3 2 3 端到端的時(shí)延估計(jì)3 0 3 3q m r p a 協(xié)議描述3 3 3 3 1 控制報(bào)文格式3 3 3 3 2 初始多播樹的建立3 7 3 3 3 目的節(jié)點(diǎn)的動(dòng)態(tài)加入3 9 3 3 4 節(jié)點(diǎn)的維護(hù)過程4 1 一v 一 東北大學(xué)碩士學(xué)位論丈目 錄 3 3 5 節(jié)點(diǎn)的剪除4 1 3 4 增加備份路由機(jī)制4 2 3 4 1 備份路由的有效性和可行性4 2 3 4 2 備份路由的設(shè)計(jì)4 2 3 4 3 多播路由維護(hù)4 3 3 5 協(xié)議j 下確性證明及復(fù)雜性分析4 51 3 6 、結(jié)4 6 第4 章q m r p a 仿真及性能分析：4 7 4 1 仿真背景及場(chǎng)景4 7 4 1 1 仿真工具4 7 4 1 2 仿真設(shè)置4 8 4 2q m r p a 在n s 上的實(shí)現(xiàn)5 0 4 2 1q m r p a 組播路由實(shí)現(xiàn)5 0 4 2 2 節(jié)點(diǎn)中需要維護(hù)的數(shù)據(jù)結(jié)構(gòu)5 3 4 3 性能指標(biāo)的選擇5 4 4 4 仿真結(jié)果及分析5 5 。 4 4 1 多播組大小對(duì)網(wǎng)絡(luò)性能的影響5 5 4 4 2 節(jié)點(diǎn)運(yùn)動(dòng)速度對(duì)網(wǎng)絡(luò)性能的影響5 7 ， 4 4 3 延時(shí)約束對(duì)網(wǎng)絡(luò)性能的影響5 9 4 5 月、結(jié)6 0 第5 章分簇基礎(chǔ)上的改進(jìn)一q m i 心a c l 6 1 5 1 設(shè)計(jì)思路6 1 5 2 分簇m a n e t 及網(wǎng)絡(luò)模型6 1 孓3 q m 氅曼。婪：= y 巧3i ， 5 3 1 初始多播樹的建立6 3 。 ， 5 3 2 目的節(jié)點(diǎn)的動(dòng)態(tài)加入6 4 5 4 協(xié)議正確性證明及復(fù)雜性分析6 6 5 5 小結(jié)6 6 第6 章結(jié)論6 7 6 1 論文工作6 7 6 2 未來研究方向6 8 參考文獻(xiàn)6 9 o ，產(chǎn)1 ，2 ，尸， 存在一組實(shí)數(shù)亭，產(chǎn)1 ，2 ，p ，使得x 宰是： j p m a x 彬乃( x ) ； ，l l s t 艄童 j ，j _ 、，2 ，p 五酬 i 的一個(gè)最優(yōu)解。通過變動(dòng)( 卣，受，己) 的取值，求解一系列上述問題，就可以得到近似 的非劣解集。 。 在多度量參數(shù)的q o s 路由選擇問題中，通過對(duì)乘性q o s 參數(shù)進(jìn)行對(duì)數(shù)變換，對(duì)凹 性q o s 參數(shù)進(jìn)行加權(quán)或倒數(shù)變換，這樣多參數(shù)q o s 問題最終將被轉(zhuǎn)換成為多項(xiàng)式加法 求極值的多目標(biāo)決策問題。假如在多度量q o s 問題中，決策空間x = 伍，翰) 1 分別 對(duì)應(yīng)( 剩余帶寬、延遲、節(jié)點(diǎn)剩余能量、費(fèi)用、跳數(shù)等) ，則目標(biāo)函數(shù)力 ) ，石 ) 分 別表示路徑p 上的可用帶寬函數(shù)、延遲函數(shù)、剩余能量函數(shù)、延遲抖動(dòng)函數(shù)、丟包率函 數(shù)等。通過對(duì)相關(guān)乘性和凹性函數(shù)進(jìn)行對(duì)數(shù)和加權(quán)或倒數(shù)變換，采用混合法，可以得到 如下q o s 路由的一般數(shù)學(xué)模型： 一2 r 一 東北大學(xué)碩士學(xué)位論文第3 章a d h o c 網(wǎng)絡(luò)中q o s 多播路由協(xié)議一q m 砌狐 p m i n 矽乃( 工) ； 宅l s f - f , f x ) 耋孝，戶l ，2 ，p 工甜 其中，x 為包括x 在內(nèi)的節(jié)點(diǎn)和鏈路屬性，孝，為鏈路的一組臨界指標(biāo)，w , 0 為一組 p 權(quán)值。通常取嵋o ) = l ，彬 o ，1 。 j 年l 設(shè)p = 4 ，f = ( b ，d ，j ，c ) ( 分別表示路徑的帶寬、延遲、延遲抖動(dòng)和鏈路費(fèi)用) ，取 w = ( 鐘，川，嵋，川) = ( o ，0 ，0 ，1 ) ，則問題轉(zhuǎn)化成為在滿足帶寬和延遲的條件下， 求鏈路費(fèi)用最大的問題。 因此，在多目標(biāo)q o s 路由問題中，根據(jù)不同業(yè)務(wù)對(duì)特定指標(biāo)的不同要求，可以根據(jù) 每次賦予的不同的權(quán)值，求得一組路徑，然后在這些路徑集合中按照具體規(guī)則進(jìn)行選優(yōu)。 在a dh o c 網(wǎng)絡(luò)g = 形習(xí)中，若s z - 2 為一棵組播樹的源節(jié)點(diǎn)，m 為該組播樹的目的 節(jié)點(diǎn)或葉節(jié)點(diǎn)集。設(shè)r 為正實(shí)數(shù)集，r 為非負(fù)實(shí)數(shù)集。對(duì)于任意鏈路e e ，可定義某些 q o s 特征值：帶寬函數(shù)b a n d w i d t h ( 矽：e 瑚，延遲函數(shù)d e l a y ( e ) ：e 嘲，延遲抖動(dòng)函數(shù) d e l a y _ j i t t e r ( e ) ：e 哪+ ，傳輸費(fèi)用函數(shù)c 吖砂：e 瑚。類似地， 對(duì)于任一節(jié)點(diǎn)，z n 也可定義某些q o s 特征值：延遲函數(shù)d ( n ) - y 瑚， 傳輸費(fèi)用函數(shù)c 例：瑚，延遲抖 動(dòng)函數(shù)孝f ，砂? y 瑚+ 。令吖s ，岣表示組播樹，其相互關(guān)系如下： ( 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 ，砂為多播樹耶，蚴上源點(diǎn)s 到目的節(jié)點(diǎn)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òng)約束：d e a l y - j i t t e r ( p ( s ，圳； ( 4 ) 費(fèi)用約束：在所有滿足( 1 ) ( 3 ) 條件的組播樹中，c o s t ( t ( s ，刪盡可能最 小。 其中，b f i l i 。是帶寬約束，d 撇；和j n 砒分別是延遲和延遲抖動(dòng)約束。 一2 9 東北大學(xué)碩士學(xué)位論文第3 章a dh o c 網(wǎng)絡(luò)中q o s 多播路由協(xié)議一q m 砒，a 3 2 3 端到端的時(shí)延估計(jì) 破 q m r p a 協(xié)議中q o s 約束包括端到端時(shí)延，那么有必要通過有效的方法對(duì)端到端時(shí) “ 延進(jìn)行估計(jì)，從而獲得較為準(zhǔn)確的q o s 指標(biāo)。對(duì)于同步網(wǎng)絡(luò)，端到端的時(shí)延是很容易計(jì) 算的。只要用目的節(jié)點(diǎn)收到數(shù)據(jù)包的時(shí)刻減去源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的時(shí)刻就可以了。 。 在異步網(wǎng)絡(luò)中，這個(gè)問題就變得復(fù)雜起來。根據(jù)q m r p a 協(xié)議中初始多播樹的建立 過程( 即多播源節(jié)點(diǎn)廣播路由請(qǐng)求報(bào)文r e q u ，目的節(jié)點(diǎn)收到路由請(qǐng)求報(bào)文即按照翻轉(zhuǎn)路 徑向源節(jié)點(diǎn)返回路由回答報(bào)文r p l y ) ，可以考慮利用這個(gè)建立過程的雙向時(shí)延( 源節(jié)點(diǎn)一 目的節(jié)點(diǎn)一源節(jié)點(diǎn)) 來估算下行時(shí)延( 源節(jié)點(diǎn)一目的節(jié)點(diǎn)) 。下面將證明這個(gè)估算是合理 的： 首先給出端到端時(shí)延t 的定義： 定義1 端到端時(shí)延d ：報(bào)文從源端發(fā)出，到被目的端正確接收所經(jīng)歷的時(shí)間延遲。 單位為秒。 d = ，( d f ( ，) ) + d j d ( j ) + d 如( s ，丁) ， ( 3 1 ) 其中，i 為選定路由包括的各節(jié)點(diǎn)，s 為源節(jié)點(diǎn)，t 為目的節(jié)點(diǎn)，d ，為數(shù)據(jù)包的傳輸 時(shí)延，島為處理時(shí)延。9 腳為信號(hào)在無(wú)線信道中的傳播時(shí)延，它們進(jìn)一步可以表示為： d = s 啦| b a ( 1 )0 砩= d w + 乃( 3 3 ) 其中虢為數(shù)據(jù)包的大d , ( l g 特) ，玩為節(jié)點(diǎn)i 實(shí)際能夠利用的有效帶寬( 比特秒) ， 砩為數(shù)據(jù)包在節(jié)點(diǎn)i 的處理時(shí)間( 秒) ，它又包括了在節(jié)點(diǎn)i 的隊(duì)列中的等待時(shí)間d w 和 真正的數(shù)據(jù)包被處理的時(shí)間d d 。 對(duì)于多媒體文件來說，其傳輸所要求的平均時(shí)延必須滿足 d 2 d 卅口, - d a _ f f f ld ，s 2 d 用o x 、 d d 孵f2 d 懈 相對(duì)于d m 烈，d d i f f f l c j 值是很小的。而且，d d 批值只與源節(jié)點(diǎn)、目的節(jié)點(diǎn)的隊(duì)列等待 時(shí)間有關(guān)，與所選擇的路由基本沒有關(guān)系。因此，用d ，2 ，來估計(jì)d 加是合理的。 還需要說明的是，在帶寬條件滿足的情況下，網(wǎng)絡(luò)能夠?yàn)閿?shù)據(jù)流的傳輸提供穩(wěn)定的 時(shí)延，因此推斷如果路由建立過程中估算的傳輸時(shí)延能夠滿足數(shù)據(jù)流的時(shí)延要求，那么 數(shù)據(jù)流實(shí)際傳輸?shù)臅r(shí)延也能滿足要求。 這樣就能得到：當(dāng)源節(jié)點(diǎn)收到來自目的節(jié)點(diǎn)的路由回復(fù)( 能夠收到的路由回復(fù)都是 滿足時(shí)延要求的) 時(shí)，根據(jù)當(dāng)前時(shí)間與其發(fā)送路由要求的時(shí)間算出d ，并與數(shù)據(jù)流允許 的最大時(shí)延作比較，最終決定是否可以利用這條路由來傳輸數(shù)據(jù)流。即當(dāng)d r s 2 d 小甜時(shí)， 能夠傳輸數(shù)據(jù)流；當(dāng)d r 2 d 朋甜時(shí)，不能傳輸數(shù)據(jù)流。 在q m r p a 協(xié)議初始多播樹建立過程中，當(dāng)多播源節(jié)點(diǎn)發(fā)送的路由請(qǐng)求報(bào)文r e q u - 到達(dá)目的節(jié)點(diǎn)時(shí)，如果此時(shí)的d d o m 已經(jīng)超過了d 小時(shí)，即d d 0 跏 d 朋甜時(shí)，此時(shí)此刻該 路由已經(jīng)不滿足時(shí)延了，所以可以直接丟棄該報(bào)文。 同理，q m r p a 協(xié)議中，在目的節(jié)點(diǎn)請(qǐng)求加入多播樹時(shí)，即目的節(jié)點(diǎn)廣播請(qǐng)求加入 報(bào)文j o i n ，多播樹節(jié)點(diǎn)接收到請(qǐng)求加入報(bào)文時(shí)，即按照翻轉(zhuǎn)路徑向目的節(jié)點(diǎn)返回請(qǐng)求回 復(fù)報(bào)文r a c k ) ，可以考慮利用這個(gè)建立過程的雙向時(shí)延( 目的節(jié)點(diǎn)x 一多播樹節(jié)點(diǎn)z 一目 的節(jié)點(diǎn)x ) 來估算下行時(shí)延( 目的節(jié)點(diǎn)一多播樹節(jié)點(diǎn)) 。 因?yàn)槎嗖涔?jié)點(diǎn)均存儲(chǔ)鏈路信息表l t ，所以多播樹節(jié)點(diǎn)的存儲(chǔ)鏈路信息表中存儲(chǔ)著 從多播樹源節(jié)點(diǎn)到樹節(jié)點(diǎn)z 的時(shí)延以z ) ，這樣就能得到：當(dāng)目的節(jié)點(diǎn)x 收到來自多播樹節(jié) 點(diǎn)z 的路由回復(fù)( 能夠收到的路由回復(fù)都是滿足時(shí)延要求的) 時(shí)，根據(jù)當(dāng)前時(shí)間與其發(fā)送路 由要求的時(shí)間算出d ，并與數(shù)據(jù)流允許的最大時(shí)延d 歷甜減去多播樹源節(jié)點(diǎn)到多播樹節(jié)點(diǎn) 的時(shí)延以z ) 作比較，最終決定是否可以利用這條路由來傳輸數(shù)據(jù)流。即當(dāng)d ，s2 ( 9 一一吠z ) ) 時(shí)，能夠傳輸數(shù)據(jù)流；當(dāng)d r 2 ( d 一吠z ) ) 時(shí)，不能傳輸數(shù)據(jù)流。 在q m r p a 協(xié)議的多播節(jié)點(diǎn)加入過程中，當(dāng)多播源節(jié)點(diǎn)發(fā)送的路由請(qǐng)求報(bào)文r e q u 。 到達(dá)目的節(jié)點(diǎn)時(shí)，如果此時(shí)的d 如硼已經(jīng)超過t d 聊a x - d ( z ) 時(shí)，即砒m d m a x - - 戰(zhàn)z ) 時(shí)，此 一3 2 一 ， j 東北大學(xué)碩士學(xué)位論文第3 章a dh o c 網(wǎng)絡(luò)中q o s 多播路由協(xié)議一q m r p a 時(shí)此刻該路由已經(jīng)不滿足時(shí)延了，所以可以直接丟棄該報(bào)文，沒有必要再去統(tǒng)計(jì)研了， 這樣減少了一定的路由開銷。 3 3q m r p a 協(xié)議描述 在本節(jié)將描述一種基于延遲、延遲抖動(dòng)、帶寬、費(fèi)用約束的q o s 多播路由協(xié)議( 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 協(xié)議中， 定義了相鄰節(jié)點(diǎn)之間的可行鏈路；在路由過程中，首先建立從多播源節(jié)點(diǎn)到某多播目的 節(jié)點(diǎn)滿足多q o s 約束的單一鏈路構(gòu)成初始多播樹，其余多播目的節(jié)點(diǎn)再申請(qǐng)加入多播樹 中，達(dá)到了快速高效建立滿足多q o s 約束多播樹的目的。 定義2 若節(jié)蔚為節(jié)點(diǎn)i 的相鄰節(jié)點(diǎn)，鏈路e ( f ，力鈕，并且d ( s ，0 和孝p ，0 分別表示 從多播源節(jié)點(diǎn)s 到節(jié)點(diǎn)f 的延時(shí)值之和和延時(shí)抖動(dòng)之和，如果鏈路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 樹節(jié)點(diǎn)集口中的節(jié)點(diǎn)均存儲(chǔ)鏈路信息表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 主要記載某節(jié)點(diǎn)( n o d e ) 到源節(jié)點(diǎn)s 的延時(shí)值( d ( n o d e ) ) 、延時(shí)抖動(dòng)值 ( c i f 向d 圳) 以及費(fèi)用( c ( n o d e ) ) 等q o s 約束信息，同時(shí)記載該節(jié)點(diǎn)在樹中的父節(jié)點(diǎn)( u p n o d e ) 。 3 3 1 控制報(bào)文格式 q m r p a 協(xié)議的路由控制報(bào)文主要有以下幾種類型：路由請(qǐng)求報(bào)文r e q u 、路由回 答報(bào)文r p l y 、請(qǐng)求加入報(bào)文j o i n 和加入確認(rèn)報(bào)文r a c k 。 ( 1 ) 路由請(qǐng)求報(bào)文r e q u 格式： r e q u 報(bào)文格式如圖3 1 ： 一3 3 東北大學(xué)碩士學(xué)位論文第3 章a d h o e 網(wǎng)絡(luò)中q o s 多播路由協(xié)議一q m r p a 報(bào)文類型( 8 b i t ) 保留字段( 1 6 b i t ) 跳數(shù)( 8 b i t ) r e q ui d ( 3 2 b i t ) 目的i p 地勻l ( 3 2 b i t ) 目的i p 序列號(hào)( 3 2 b i t ) 源i p 地j ( 3 2 b i t ) 源i p 序列號(hào)( 3 2 b i t ) 延時(shí)d ( 3 2 b i t ) 延時(shí)抖動(dòng)j ( 3 2 b i t ) 最小帶寬b ，加( 3 2 b i 0 費(fèi)用c d ( 3 2 b i t ) 路徑p a t h 圖3 1 路由請(qǐng)求報(bào)文( 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 地址聯(lián)合起來標(biāo)志一個(gè)獨(dú)一無(wú)二的r e q u 報(bào)文。 目的序列號(hào)：目的節(jié)點(diǎn)收到的來自源節(jié)點(diǎn)的所有序列號(hào)中的最新( 最大) 值。 源序列號(hào)：源節(jié)點(diǎn)路由表項(xiàng)中的當(dāng)前序列號(hào)。 延時(shí)d ：在多播源節(jié)點(diǎn)時(shí)的初始值為0 ，延時(shí)約束d 棚甜，報(bào)文每經(jīng)過個(gè)節(jié)點(diǎn)，延 時(shí)d 就會(huì)累加，所以報(bào)文到達(dá)某個(gè)節(jié)點(diǎn)時(shí)的d 值就是從源節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)之間的延遲 累加值，到達(dá)的每個(gè)節(jié)點(diǎn)都會(huì)把這個(gè)值存儲(chǔ)到鏈路信息表l t 中的d ( n o d e ) 中。 延時(shí)抖動(dòng) 在多播源節(jié)點(diǎn)時(shí)的初始值為0 ，延時(shí)抖動(dòng)約束厶甜，報(bào)文每經(jīng)過一個(gè)節(jié) 點(diǎn)，延時(shí)抖動(dòng)，就會(huì)累加，所以報(bào)文到達(dá)某個(gè)節(jié)點(diǎn)時(shí)的，值就是從源節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)之 間的延遲抖動(dòng)累加值，到達(dá)的每個(gè)節(jié)點(diǎn)都會(huì)把這個(gè)值存儲(chǔ)到鏈路信息表l t 中的a j ( n o d e ) 中。 最小帶寬b 脅：q o s 約束中的最小帶寬值。 費(fèi)用c d ：在多播源節(jié)點(diǎn)時(shí)的初始值為o ，報(bào)文每經(jīng)過一個(gè)節(jié)點(diǎn)，費(fèi)用c d 就會(huì)累加， 所以報(bào)文到達(dá)某個(gè)節(jié)點(diǎn)時(shí)的c d 值就是從源節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)之間的費(fèi)用累加值，到達(dá)的 每個(gè)節(jié)點(diǎn)都會(huì)把這個(gè)值存儲(chǔ)到鏈路信息表l t 中的c ( n o d e ) 中。 路徑p a t h ：從多播源節(jié)點(diǎn)到處理該請(qǐng)求的節(jié)點(diǎn)的路徑。 ( 2 ) 路由回答報(bào)文p p l y 格式： r p l y 報(bào)文格式如圖3 2 ： 3 4 東北大學(xué)碩士學(xué)位論文第3 章a dh o c 網(wǎng)絡(luò)中q o s 多播路由協(xié)議一q 愀 報(bào)文類型( 8 b i t )保留字段( 1 6 b i t l 跳數(shù)( 8 b i t ) 目的i p 地址( 3 2 b i t ) 目的i p 序列號(hào)( 3 2 b i t ) 源i p 地址( 3 2 b i t ) 生存時(shí)間( 3 2 b i t ) 路徑p a t h 圖3 2 路由回答報(bào)文( 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 ) 其中： 生存時(shí)間：節(jié)點(diǎn)收到r p l y 后考慮的路由有效時(shí)間。這個(gè)值是在目的節(jié)點(diǎn)中繼節(jié) 點(diǎn)應(yīng)答r p l y 時(shí)確定的，當(dāng)源節(jié)點(diǎn)收到該r p l y 時(shí)利用該值設(shè)置對(duì)應(yīng)路由表項(xiàng)的超時(shí)時(shí) 間，以和目的節(jié)點(diǎn)中繼節(jié)點(diǎn)的路由表項(xiàng)生存期一致。 ( 3 ) 請(qǐng)求加入報(bào)文j o i n 格式： j o i n 報(bào)文格式如圖3 3 ： 報(bào)文類型( 8 b i t )保留字段( 1 6 b i t )跳數(shù)( 8 b i t ) j o i ni d ( 3 2 b i t ) 目的口地j q k ( 3 2 b i t ) 目的i p 序列號(hào)( 3 2 b i t ) 多播源i pj 勘k ( 3 2 b i t ) 多播源腰序列號(hào)( 3 2 b i t ) 請(qǐng)求延時(shí)d ( 3 2 b i t ) 請(qǐng)求延時(shí)抖動(dòng)，( 3 2 b i t ) 請(qǐng)求最小帶寬b 。跏( 3 2 b i t ) 請(qǐng)求費(fèi)用c d ( 3 2 b i t ) 路徑p a t h 圖3 3 請(qǐng)求加入報(bào)文( 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 ) 其中： 請(qǐng)求延時(shí)d ：在目的節(jié)點(diǎn)時(shí)的初始值為延時(shí)約束口一，減去報(bào)文經(jīng)過的鏈路延時(shí)， 到達(dá)處理該請(qǐng)求的節(jié)點(diǎn)時(shí)所剩的值為d 。 請(qǐng)求延時(shí)抖動(dòng)，：在目的節(jié)點(diǎn)時(shí)的初始值為延時(shí)抖動(dòng)約束厶烈，減去報(bào)文經(jīng)過的鏈 路延時(shí)抖動(dòng)，到達(dá)處理該請(qǐng)求的節(jié)點(diǎn)時(shí)所剩的值為，。 一3 5 查! ! 查蘭翌主蘭堡笙圭箜3 章a d h o c 網(wǎng)絡(luò)中q o s 多播路由協(xié)議一q m 褂) a 二二= 2 二二二= ：= i 二! 竺 型竺 請(qǐng)求最小帶寬如伽：q o s 約束中的最小帶寬值。 請(qǐng)求費(fèi)用c d ：從目的節(jié)點(diǎn)到處理該請(qǐng)求的節(jié)點(diǎn)的鏈路費(fèi)用，c d = 0 表示初始的鏈路 費(fèi)用。 路徑p a t h ：從目的節(jié)點(diǎn)( 請(qǐng)求節(jié)點(diǎn)) 到處理該請(qǐng)求的節(jié)點(diǎn)的路徑。 ( 4 ) 加入確認(rèn)報(bào)文r a c k 格式： r a c k 報(bào)文格式如圖3 4 ： o 東北大學(xué)碩士學(xué)位論文第3 章a d h o c 網(wǎng)絡(luò)中q o s 多播路由協(xié)議一q m 砌) a w ：鏈路錯(cuò)誤標(biāo)志，當(dāng)發(fā)現(xiàn)了不可達(dá)( 移動(dòng)或損壞) 的節(jié)點(diǎn)或鏈路，由發(fā)現(xiàn)不可達(dá) 節(jié)點(diǎn)或鏈路的節(jié)點(diǎn)向源節(jié)點(diǎn)和目的節(jié)點(diǎn)回送錯(cuò)誤分組。 3 3 2 初始多播樹的建立 在多播路由建立前，由源節(jié)點(diǎn)s 以某多播目的節(jié)點(diǎn)t i ( 厶曰) 為目的節(jié)點(diǎn)構(gòu)造一個(gè)有 唯一標(biāo)識(shí)的路由請(qǐng)求報(bào)文r e q u ，r e q u 包含源節(jié)點(diǎn)、目的節(jié)點(diǎn)、q o s 約束要求以及跳 數(shù)等信息。開始路由建立時(shí)，首先由源節(jié)點(diǎn)5 向其具有可行鏈路的相鄰節(jié)點(diǎn)廣播報(bào)文 r e q u 。 節(jié)點(diǎn)發(fā)送完報(bào)文r e q u 后，如果在r e q u w a i t t i m e 時(shí)間內(nèi)沒收到路由回答報(bào)文 r p l y ，節(jié)點(diǎn)重新廣播報(bào)文r e q u ，如果節(jié)點(diǎn)在重試次后，仍然沒收到i 沖l y ，則認(rèn)為在 該網(wǎng)絡(luò)內(nèi)沒有那個(gè)多播組的成員。 當(dāng)某節(jié)蔚接收到由節(jié)點(diǎn)f 轉(zhuǎn)發(fā)來的r e q u 報(bào)文時(shí)，節(jié)蔚作如下處理： ( 1 ) 如果節(jié)蔚非目的節(jié)點(diǎn)t i 且已經(jīng)接收過報(bào)文r e q u ，則丟棄該報(bào)文，結(jié)束處理。 否則轉(zhuǎn)2 。 ( 2 ) 節(jié)蔚將節(jié)點(diǎn)f 作為其父節(jié)點(diǎn)，節(jié)蔚作已接收r e q u 報(bào)文的標(biāo)志，并更新自 身的鏈路信息表l t ：節(jié)蔚的標(biāo)識(shí)號(hào)一聆d 比；節(jié)點(diǎn)f 的標(biāo)識(shí)號(hào)- - - ，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 ；然后將節(jié)向加入樹節(jié)點(diǎn)集口 中，將鏈路( f ，) 加入到r e q u 報(bào)文的鏈路信息中，轉(zhuǎn)3 。 ( 3 ) 如果節(jié)蔚非目的節(jié)點(diǎn)t ，則節(jié)蔚在其相鄰節(jié)點(diǎn)中尋找沒有接收r e q u 報(bào)文 標(biāo)志且具有可行鏈路的節(jié)點(diǎn)廣播該報(bào)文r e q u ，結(jié)束處理。否則轉(zhuǎn)4 。 當(dāng)節(jié)點(diǎn)，不能找到滿足條件的相鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)報(bào)文，則丟棄報(bào)文，并刪除集合口中的 節(jié)蔚，撤消報(bào)文鏈路信息中( f ，力的內(nèi)容，撤消節(jié)點(diǎn)，的接收r e q u 報(bào)文的標(biāo)志，并相對(duì) 節(jié)點(diǎn)i 將節(jié)點(diǎn)，作上標(biāo)志，同時(shí)讓節(jié)點(diǎn)i 重新選擇可行鏈路廣播報(bào)文r e q u 。 ( 4 ) 節(jié)點(diǎn)，為目的節(jié)點(diǎn)t i ，則節(jié)點(diǎn)t i 在規(guī)定的時(shí)間間隔內(nèi)將收到的所有請(qǐng)求報(bào)文中 c 0 9 值最小者作為本次路由請(qǐng)求的結(jié)果，沿報(bào)文r e q u 蟄j 達(dá)的鏈路信息向源節(jié)點(diǎn)發(fā)送路由 回答報(bào)文r p l y ，進(jìn)行資源預(yù)留；而其它報(bào)文記載的鏈路信息作為備用路由信息被保存。 當(dāng)確認(rèn)報(bào)文到達(dá)源節(jié)點(diǎn)時(shí)，即建立了由源節(jié)點(diǎn)s 到目的節(jié)點(diǎn)滿足q o s 約束的單一鏈路， 形成初始多播樹。 初始多播樹建立過程中的中間節(jié)點(diǎn)流程如圖3 6 所示： 一3 7 查! ! 查蘭塑主蘭堡壘丈 第3 章a d h o c 網(wǎng)絡(luò)中q o s 多播路由協(xié)議一o m 砌) a 一一 一二- = - 二 ： ：= ：- 二：= ： 一 0 東北大學(xué)碩士學(xué)位論文第3 章a dh o e 網(wǎng)絡(luò)中q o s 多播路由協(xié)議一q m 砒) a 當(dāng)路由回答報(bào)文r p l y 到達(dá)源節(jié)點(diǎn)時(shí)，即建立了由源節(jié)點(diǎn)s 到目的節(jié)點(diǎn)滿足q o s 約 束的單一鏈路，形成初始多播樹。 3 3 3 目的節(jié)點(diǎn)的動(dòng)態(tài)加入 當(dāng)生成單鏈路的初始多播樹琊后，多播目的節(jié)點(diǎn)集m 中除t i 夕 、的其余節(jié)點(diǎn)再動(dòng) 態(tài)申請(qǐng)加入中。如果某多播目的節(jié)點(diǎn)t j ( t je m 一 f i ) ) ) 申請(qǐng)加入砸加中，首先 判斷島q 是否成立，成立則說明節(jié)點(diǎn)務(wù)已經(jīng)是多播樹中的成員節(jié)點(diǎn)，則申請(qǐng)工作完成； 否則節(jié)點(diǎn)構(gòu)造一個(gè)具有唯一標(biāo)識(shí)的請(qǐng)求加入報(bào)文j o i n 。當(dāng)節(jié)點(diǎn)厶發(fā)起請(qǐng)求加入報(bào)文 j o i n 時(shí)，把本節(jié)點(diǎn)地址加入陽(yáng)砌中，然后由節(jié)點(diǎn)務(wù)向其具有滿足q o s 約束可行鏈路的相 鄰節(jié)點(diǎn)廣播該報(bào)文j o i n 。 當(dāng)某節(jié)點(diǎn)p 接收到由節(jié)點(diǎn)g 發(fā)送來的j o i n 報(bào)文，做如下處理： ( 1 ) 如果節(jié)點(diǎn)p 已經(jīng)接收過報(bào)文j o i n ，則丟棄該報(bào)文，結(jié)束處理。否則轉(zhuǎn)2 。 ( 2 ) 節(jié)卻置已接收?qǐng)?bào)文j o i n 標(biāo)志，并對(duì)報(bào)文做如下處理：將鏈路( 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 ) ，轉(zhuǎn)3 。 ( 3 ) 判斷條件p 刃是否成立，若不成立說明節(jié)點(diǎn)p 不是多播樹中的節(jié)點(diǎn)，轉(zhuǎn) s t e p 4 。否則再判斷條件烈p ) s d & d j ( p ) 莖是否成立，若不成立，則撤消節(jié)點(diǎn)p 接收 報(bào)文j o i n 的標(biāo)志，在p a t h 中撤消( g ，p ) ，丟棄該報(bào)文，結(jié)束處理；否則，節(jié)卻向目的 節(jié)點(diǎn)務(wù)發(fā)送加入確認(rèn)報(bào)文r a c k ，結(jié)束處理。 ( 4 ) 節(jié)點(diǎn)p 在其相鄰節(jié)點(diǎn)中尋找沒有接收j o i n 報(bào)文標(biāo)志且具有可行鏈路的節(jié)點(diǎn)廣 播該報(bào)文j o i n ，結(jié)束處理。 目的節(jié)點(diǎn)的動(dòng)態(tài)加入過程