摘要 摘要 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)( w i r e l e s sm e s hn e 附o r k ，w m n ) 是一種多跳無(wú)線(xiàn)網(wǎng)絡(luò)，它 具有網(wǎng)狀的拓補(bǔ)結(jié)構(gòu)，終端之間通過(guò)多跳無(wú)線(xiàn)中繼進(jìn)行數(shù)據(jù)傳輸。w m n 的構(gòu)成可 以分為m e s h 路由器、m e s h 終端以及m e s h 網(wǎng)關(guān)，m e s h 網(wǎng)關(guān)為不同網(wǎng)絡(luò)間的連接 點(diǎn)：主干路由器位置較固定，有穩(wěn)定的電源供給；m e s h 終端除了可以通過(guò)m e s h 路由器接入其它網(wǎng)絡(luò)外，也可以作為子網(wǎng)內(nèi)的路由器，為本節(jié)點(diǎn)和同一子網(wǎng)的其 它節(jié)點(diǎn)提供路由。w m n 具有自組織和自愈的特點(diǎn)，能夠提供更大的網(wǎng)絡(luò)容量和更 高的傳輸速率。w m n 正在成為下一代因特網(wǎng)技術(shù)的重要組成部分。 w m n 路由協(xié)議是組建m e s h 網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，是本文主要的研究和工作 內(nèi)容。文中首先簡(jiǎn)要介紹了無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的結(jié)構(gòu)，特點(diǎn)以及應(yīng)用；其次討論了 a dh o c 網(wǎng)絡(luò)的路由協(xié)議和無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由設(shè)計(jì)的原則和思路。接著，詳細(xì)介 紹了m e s h 終端，特別是m e s h 路由協(xié)議的工作原理和具體實(shí)現(xiàn)。最后根據(jù)設(shè)計(jì)好 的系統(tǒng)，對(duì)m e s h 終端組成的單級(jí)網(wǎng)絡(luò)和m e s h 終端與w i m a x 基站組成的分級(jí)網(wǎng) 絡(luò)進(jìn)行了測(cè)試，并對(duì)測(cè)試結(jié)果進(jìn)行了合理分析，為路由協(xié)議的后續(xù)改進(jìn)提出了建 議。 關(guān)鍵詞：無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由協(xié)議分級(jí)網(wǎng)絡(luò)測(cè)試 a b s t r a c t a b s tr a c t aw i r e l e s sm e s hn e t w o r k ( w m n ) i sam u l t i h o pw i r e l e s sn e 似o r k i th a sam e s h t c 巾o l o 跖a n dt h et 黝i n 面sc a n t r 觚s m i td a t ab ya 謝r e l e s sm u l t i - h 叩r e l a y a 刪i s a l s oah i e r a r c l l i c a ln e t w o r k c o n s i s t i n go f m e s hc l i e n t s ，m e s hr o u t e r s ，觚dg a t e w a y s w i t h af i x e dl o c a t i o n 鋤das t a b l ep o w e rs u p p l y ，m e s hr o u t e 瑙c o n s t i n l t eaw 硫l e s sm e s h b a c k b o n e ，t 0w 1 1 i c hm e s hc l i e n t sa r ec o m l e c t e da sas t a rt o p o l o g 蠣a n dg a t e w a ) ，sa r e c h o s e l l 鋤o n gm e s hc l i e l l t sp r o v i d i n go t h e rn e 倆o r k sa c c e s s m e s hc l i e n t sc 鋤a c c e s s o t h e rn e 觚o r k s 伽o u 曲m e s hr o u t e r s ，a n dt h e yc 孤a l s oc o m m i c a t e 謝t he a c ho m e ri i l t h es 鋤el o c a l 扣e an e 附o f kw i t h o u tam e s hr - 0 u t e r aw dnh a saf i e a t i i i eo f s e l g o 珞鋤i z i n ga n ds e l f h e a l i n g ，a i l dc 鋤p r 0 v i d eg r e a t e rn e 腑o r kc a p a c i 毋弛dl l i 廬e r 仃a n s f hr a t e s ot h ew m ni sb e c o m i n g 觚i i l l p o r t a n tp a r ti nt l l en e x tg e n e r a t i o no f h l t e m e tt e c h n o l o g y m e s hr 0 血n gp r o t o c o l i so n eo ft l l ek e yt e c h n o l o 西e st ob u i l dn e 時(shí)o f k sa n d 曲s p a p e rf o c u s e so ni t sd e s i g n f i r s t ，t h e 咖t u r e ，c h a r a c t e r i s t i c sa n da p p l i c a t i o n so f w m na r e 曲吶d u c e db r i e n y ；s c c o n d ，l ep r i n c i p l e s 趾di d e 弱o fd e s i g i l i n gm e s h r o u t i n gp r o t o c o l s 盯ed i s c u s s e d ；m e n ，aw m nr o u t i n gi sp r o p o s e db yi m p r o v i n ga n d o p t i m i z i n ga m o b i l ea dh o c r o u t i r l gw i t l lt h ec o n c r e t er e a l i z a t i o no f 0 t h e rp a i t s ，a “船t t e s t sa r e 舢o nt h em e s hs y s t e m ，f o l l o w e db yr e s u l t s 鋤d 吼a l y s i s k e y w o r d ：y m nr o u t i n g p r o t o c o l sh i e r a r c h i c a ln e l w o r k s i l 垮t i n g 創(chuàng)新性聲明 本人聲明所呈交的論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研 究成果。盡我所知，除了文中特別加以標(biāo)注和致謝中所羅列的內(nèi)容以外，論文 中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果；也不包含為獲得西安電子科技 大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書(shū)而使用過(guò)的材料。與我一同工作的同志對(duì)本 研究所做的任何貢獻(xiàn)均已在論文中做了明確的說(shuō)明并表示了謝意。 申請(qǐng)學(xué)位論文與資料若有不實(shí)之處，本人承擔(dān)一切相關(guān)責(zé)任。 本人簽名：一4 漁 日期 坦2 ：主： 關(guān)于論文使用授權(quán)的說(shuō)明 本人完全了解西安電子科技大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，即：研 究生在校攻讀學(xué)位期間論文工作的知識(shí)產(chǎn)權(quán)單位屬西安電子科技大學(xué)。本人保 證畢業(yè)離校后，發(fā)表論文或使用論文工作成果時(shí)署名單位仍然為西安電子科技 大學(xué)。學(xué)校有權(quán)保留送交論文的復(fù)印件，允許查閱和借閱論文；學(xué)?？梢怨?論文的全部或部分內(nèi)容，可以允許采用影印、縮印或其它復(fù)制手段保存論文。 ( 保密的論文在解密后遵守此規(guī)定) 本學(xué)位論文屬于保密，在_ 年解密后適用本授權(quán)書(shū)。 日期坦2 ：i ：! 醐中 第一章結(jié)論 第一章緒論 隨著大量新的無(wú)線(xiàn)通信技術(shù)不斷涌現(xiàn)，無(wú)線(xiàn)廂鯧由于其接入靈活、成本低廉 咀及易于擴(kuò)展等特性近年來(lái)得到了飛速發(fā)展。無(wú)線(xiàn)局域網(wǎng)( w i r e l e s s 脅柏a r e a n e t w o r k ，w l a n ) 、移動(dòng)自組織網(wǎng)絡(luò)( m 0 b i l e a d h o c n e t w o r k ，m a n e t ) 以及無(wú)線(xiàn)傳感 器網(wǎng)絡(luò)f w i r e l e s ss 鋤s o rn e t w o r k ，w s n ) 等形式的無(wú)線(xiàn)網(wǎng)絡(luò)在近幾年已經(jīng)得到了廣 泛的研究，特別近年來(lái)w l a n 在接入領(lǐng)域中得到了迅速發(fā)展依其所具有的巨 大數(shù)據(jù)傳輸速率，w l a n 被認(rèn)為是3 g 或3 g 后移動(dòng)數(shù)據(jù)通信部分的一個(gè)主要競(jìng)爭(zhēng) 對(duì)手。但w l a n 有其不足之處，其中最主要的一個(gè)便是接入點(diǎn)的覆蓋范圍較 為有限，若要在一個(gè)相對(duì)較大的區(qū)域提供無(wú)線(xiàn)覆蓋，就需要在該地區(qū)內(nèi)配置多個(gè) 接入點(diǎn)，因而增加了建設(shè)基于w l a n 的公共寬帶網(wǎng)的成本。無(wú)線(xiàn)m e s h 網(wǎng)絡(luò) 州i r e l e 娼m 曲n e t 啪r k ，w m 娜作為一種能夠提供更大范圍無(wú)線(xiàn)接入的新技術(shù)己經(jīng) 成為了新的研究熱點(diǎn)。 i 1 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的背景和起源 。鑫嗡k 峰纛 尤線(xiàn)m e s h 網(wǎng)綹踣由技術(shù)的設(shè)計(jì)與實(shí)現(xiàn) 用需求。另方面，無(wú)線(xiàn)局域網(wǎng)的發(fā)展己經(jīng)進(jìn)入技術(shù)成熟期，它有效延伸了因特 網(wǎng)的覆蓋范圍，賦予了用戶(hù)一定的移動(dòng)性。一些沒(méi)有取得移動(dòng)通信網(wǎng)絡(luò)運(yùn)營(yíng)牌照 的運(yùn)營(yíng)商也期望通過(guò)布置熱點(diǎn)地區(qū)接八點(diǎn)( a c c e s sp o m t ，a p ) ，將原本并沒(méi)有用于 商業(yè)網(wǎng)絡(luò)的w l a n 技術(shù)推向了市場(chǎng)，但是w l a n 無(wú)法做到像蜂窩網(wǎng)絡(luò)一樣無(wú)處 1 i 在的信號(hào)覆蓋。為了能夠?qū)崿F(xiàn)無(wú)線(xiàn)通信中無(wú)處不在的通信目標(biāo)，我們需要基于 移動(dòng)a dh o c 網(wǎng)絡(luò)的技術(shù)基礎(chǔ)，開(kāi)發(fā)出一種完全適用于民用通信的無(wú)線(xiàn)多跳網(wǎng)絡(luò)技 術(shù)，于是w m n 技術(shù)就隨著這一需求而出現(xiàn)。 2 0 0 0 年初，業(yè)界的幾個(gè)重要事件引起了人們的特別關(guān)注，其中之一是美國(guó)r r t 公司將其為美國(guó)軍方研發(fā)的戰(zhàn)術(shù)移動(dòng)通信系統(tǒng)的一些專(zhuān)利技術(shù)轉(zhuǎn)讓給了 m e s h n e t w o r k s 公司，該公司借此開(kāi)發(fā)了一系列具有自主知識(shí)產(chǎn)權(quán)的無(wú)線(xiàn)多跳網(wǎng)絡(luò) 民用產(chǎn)品w m n 全套技術(shù)產(chǎn)品，井在市場(chǎng)上獲得了極大的成功。與此同時(shí)，諾 基亞、北電網(wǎng)絡(luò)、t r o p o s 、s k y p i l o t 、r a d i 抓t n e n v 幽和f i 嘣i d e 等多家公司開(kāi)發(fā) 的w m n 產(chǎn)品相繼問(wèn)世。從此w m n 進(jìn)入了飛速發(fā)展的時(shí)期，同時(shí)也給移動(dòng)a d h o c 網(wǎng)絡(luò)本身的發(fā)展注入了新的活力。其問(wèn)摩托羅拉公司極為看好m e 刪帆f k s 公 司的發(fā)展，于2 0 0 5 年成功地將其收于麾下。 w m n 本質(zhì)上屬于移動(dòng)a dh o c 網(wǎng)絡(luò)( 見(jiàn)圖1 2 ) ，它與后者的最大區(qū)別在于前 者的用戶(hù)終端相對(duì)來(lái)說(shuō)移動(dòng)性較低w m n 一般不是作為獨(dú)立的網(wǎng)絡(luò)形態(tài)存在r 而 是因特網(wǎng)核心網(wǎng)的延伸【u 】。通常，會(huì)有一個(gè)或多個(gè)網(wǎng)關(guān)節(jié)點(diǎn)( g d 忙w a y ，也稱(chēng)為 n a 幽d ”o da c c e s sp o 砷，鄰居接 點(diǎn)) 與因特網(wǎng)高速相連，家庭或辦公室等用 戶(hù)通過(guò)自身的無(wú)線(xiàn)接入點(diǎn)與網(wǎng)關(guān)節(jié)點(diǎn)相連。對(duì)于網(wǎng)關(guān)節(jié)點(diǎn)信號(hào)覆蓋之外的區(qū)域， 用戶(hù)節(jié)點(diǎn)負(fù)責(zé)來(lái)往業(yè)務(wù)的中繼或轉(zhuǎn)發(fā)，從而實(shí)現(xiàn)大范圍的廉價(jià)和快速信號(hào)覆蓋。 顯然，這種方式的組網(wǎng)省去網(wǎng)絡(luò)建設(shè)初期昂貴的基礎(chǔ)設(shè)施建設(shè)投資，比傳統(tǒng)的點(diǎn) 到多點(diǎn)方式的無(wú)線(xiàn)接入有很多無(wú)可比擬的優(yōu)點(diǎn)。 僻 叁奉l 圖l2w m n 結(jié)構(gòu)示意圖 與w m n 晶密切相關(guān)的網(wǎng)絡(luò)技術(shù)有w l a n 和無(wú)線(xiàn)寬帶接入網(wǎng)( w b a n 第一章結(jié)論 w i r e l e s sb r o a d b a n da c c e s sn e 鉚o r k ) 技術(shù)。圖1 3 為w m n 與這兩種網(wǎng)絡(luò)技術(shù)的關(guān) 系示意圖。 圖1 3刪與移動(dòng)a d h o c 網(wǎng)絡(luò)、。a n 和w b a n 的關(guān)系示意圖 1 2 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的結(jié)構(gòu) w m n 的結(jié)構(gòu)與傳統(tǒng)意義上的移動(dòng)a dh o c 網(wǎng)絡(luò)結(jié)構(gòu)有一定的差異。一般來(lái)講， 刪由客戶(hù)節(jié)點(diǎn)、m e s h 路由器節(jié)點(diǎn)和網(wǎng)關(guān)節(jié)點(diǎn)組成。但根據(jù)網(wǎng)絡(luò)具體配置的不 同，w m n 不一定包含以上所有類(lèi)型的節(jié)點(diǎn)。 若按節(jié)點(diǎn)的不同功能，網(wǎng)絡(luò)結(jié)構(gòu)可分為基礎(chǔ)設(shè)施的網(wǎng)絡(luò)結(jié)構(gòu)、終端設(shè)備的網(wǎng) 絡(luò)結(jié)構(gòu)和混合結(jié)構(gòu)。若按結(jié)構(gòu)層次，網(wǎng)絡(luò)又可分為平面結(jié)構(gòu)、多級(jí)結(jié)構(gòu)和混合結(jié) 構(gòu)。這兩種分層思路本質(zhì)上是相似的，基礎(chǔ)設(shè)施的網(wǎng)絡(luò)結(jié)構(gòu)就是一種多級(jí)結(jié)構(gòu)， 而終端設(shè)備的網(wǎng)絡(luò)結(jié)構(gòu)就是一種平面結(jié)構(gòu)。 1 2 1 平面網(wǎng)絡(luò)結(jié)構(gòu) 圖1 4 所示為帆烈中最簡(jiǎn)單的一種結(jié)構(gòu)平面結(jié)構(gòu)【】。圖中所有的節(jié)點(diǎn) 為對(duì)等結(jié)構(gòu)，具有完全一致的特性，即每個(gè)節(jié)點(diǎn)均包含相同的m a c 、路由、管理 和安全等協(xié)議，既具有客戶(hù)端節(jié)點(diǎn)的功能，也具有能夠轉(zhuǎn)發(fā)業(yè)務(wù)的路由器節(jié)點(diǎn)的 功能。 ， 這是一種任意網(wǎng)狀的拓補(bǔ)結(jié)構(gòu)，節(jié)點(diǎn)可以任意移動(dòng)，網(wǎng)絡(luò)拓補(bǔ)結(jié)構(gòu)會(huì)動(dòng)態(tài)變 化。在這種環(huán)境中，由于終端的無(wú)線(xiàn)通信覆蓋范圍有限，兩個(gè)無(wú)法直接通信的用 戶(hù)終端可以借助其他終端的分組轉(zhuǎn)發(fā)功能進(jìn)行數(shù)據(jù)通信。在任一時(shí)刻，終端設(shè)備 在不需要其他基礎(chǔ)設(shè)施的條件下可獨(dú)立運(yùn)行，可支持移動(dòng)終端較高速率的移動(dòng)， 快速形成寬帶網(wǎng)絡(luò)。終端用戶(hù)模式事實(shí)上就是一種a dh o c 網(wǎng)絡(luò)結(jié)構(gòu)模式，它可以 在沒(méi)有或不便利用現(xiàn)有網(wǎng)絡(luò)基礎(chǔ)設(shè)施的情況下提供一種通信支撐環(huán)境。 4 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由技術(shù)的設(shè)計(jì)與實(shí)現(xiàn) 1 2 2 多級(jí)網(wǎng)絡(luò)結(jié)構(gòu) 圖1 4w m n 平面結(jié)構(gòu) 圖1 5 所示為w m n 典型的多級(jí)結(jié)構(gòu)f l l 】，分為上層和下層兩個(gè)部分。在這種結(jié) 構(gòu)中，終端節(jié)點(diǎn)可以是普通的v 0 口手機(jī)、筆記本電腦和無(wú)線(xiàn)p d a 等。這些終端 節(jié)點(diǎn)設(shè)備通過(guò)m e s h 路由器接入到上層m e s h 結(jié)構(gòu)的網(wǎng)絡(luò)中，實(shí)現(xiàn)網(wǎng)絡(luò)節(jié)點(diǎn)的互邊 互通。 1 2 3 混合網(wǎng)絡(luò)結(jié)構(gòu) 圖1 5w m n 多級(jí)結(jié)構(gòu) 圖1 6 所示的混合結(jié)構(gòu)為以上兩種結(jié)構(gòu)的混合【l l 】。在這種結(jié)構(gòu)中，終端節(jié)點(diǎn) 是增加了具有轉(zhuǎn)發(fā)和路由功能的m e s h 設(shè)備，設(shè)備之間可以以a dh o c 方式互聯(lián)， 直接通信。一般來(lái)說(shuō)，終端節(jié)點(diǎn)設(shè)備需要同時(shí)能夠支持接入上層網(wǎng)絡(luò)m e s h 路由器 和本層網(wǎng)絡(luò)對(duì)等節(jié)點(diǎn)的功能。 籬一童端拾 圖1 6w m n 混臺(tái)結(jié)構(gòu) 由于上述結(jié)構(gòu)中的兩種接入模式具有優(yōu)勢(shì)互補(bǔ)性，因此同時(shí)支持這兩種模式 的設(shè)備可以在一個(gè)廣闊的區(qū)域內(nèi)實(shí)現(xiàn)多跳方式的無(wú)線(xiàn)通信：移動(dòng)終端既可以與其 它網(wǎng)絡(luò)相連，實(shí)現(xiàn)無(wú)線(xiàn)寬帶接入，又可以與其他用戶(hù)直接通信；并且可以作為中 間的路由器轉(zhuǎn)發(fā)其他節(jié)點(diǎn)的數(shù)據(jù)。所以w m n 不僅可以看作是w l j 與移動(dòng)a d h o c 網(wǎng)絡(luò)融合的一種網(wǎng)絡(luò)，也可看作是因特網(wǎng)的一種無(wú)線(xiàn)版本。 目前的熱點(diǎn)技術(shù)w i m a c 因其遠(yuǎn)距離下的高容量( 近5 嘶n 的覆蓋距離以及高 達(dá)7 0 m 斷以的寬帶接入) 等優(yōu)勢(shì)，吸引了眾多無(wú)線(xiàn)寬帶接入提供商的注意。從這 些網(wǎng)絡(luò)提供商一保護(hù)投資的角度出發(fā)，如果要迅速發(fā)展w i m a 【，必然要與目前已經(jīng) 蓬勃發(fā)展的w i f i 相融合。從組網(wǎng)結(jié)構(gòu)上講，可以采用兩種融合模式：( 1 ) 在w l a n 中，因?yàn)閍 p 的覆蓋范圍非常有限，用戶(hù)在熱點(diǎn)地區(qū)以外，可咀采用w i m 蹦接入 網(wǎng)絡(luò)享受服務(wù)。但是這種接入方案需要在終端設(shè)備中配置雙網(wǎng)卡。( 2 ) 采用w m n 的組網(wǎng)模式，即采用雙層結(jié)構(gòu)，骨干網(wǎng)采用砌a x 技術(shù)，接入網(wǎng)采用w i f i 。其 網(wǎng)絡(luò)結(jié)構(gòu)如圖l7 。 剛17w l m a x 與w i f i 結(jié)臺(tái)的m e s h 網(wǎng)絡(luò) 掣強(qiáng)= ；| = 9k 堅(jiān)蠆 ，、一蚵 6 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由技術(shù)的設(shè)計(jì)與實(shí)現(xiàn) 1 3 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的優(yōu)缺點(diǎn)與應(yīng)用 1 3 1 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的主要優(yōu)缺點(diǎn) m o i 與傳統(tǒng)無(wú)線(xiàn)網(wǎng)絡(luò)相比有以下優(yōu)點(diǎn)。 ( 1 ) 可靠性大大增強(qiáng)。w m n 采用的網(wǎng)絡(luò)拓補(bǔ)結(jié)構(gòu)避免了點(diǎn)對(duì)多點(diǎn)星型結(jié)構(gòu)。 ( 2 ) 網(wǎng)絡(luò)的覆蓋范圍增大，頻譜的利用率也大大提高，系統(tǒng)的容量得到了增 大。 ( 3 ) 組網(wǎng)靈活、維護(hù)方便。由于肌刪本身的組網(wǎng)特點(diǎn)，只要在需要的地方 加上、聃r e l e s sr o u t e ( w r ) 等少量的無(wú)線(xiàn)設(shè)備，即可與已有的設(shè)施組成無(wú)線(xiàn)的寬 帶接入網(wǎng)。刪的路由選擇特性使鏈路中斷或局部擴(kuò)容和升級(jí)不影響整個(gè)網(wǎng)絡(luò)運(yùn) 行。 ( 4 ) 投資成本低、風(fēng)險(xiǎn)小。w m n 的初建成本低，具有可伸縮性、易擴(kuò)容、 自動(dòng)配置和應(yīng)用范圍廣等優(yōu)勢(shì)。此外，w m n 一般采用非許可證頻段，所以為用戶(hù) 也節(jié)省了服務(wù)支出。 不過(guò)，目前來(lái)說(shuō)，、猻也存在以下一些問(wèn)題。 ( 1 ) 路由準(zhǔn)則和選擇算法：目前提出的特別適用于w m n 的路由協(xié)議寥寥無(wú) 幾。 ( 2 ) 分散管理問(wèn)題：由于w m n 的分散性，很難實(shí)現(xiàn)像有線(xiàn)網(wǎng)絡(luò)那樣那個(gè)的 集中管理，即使對(duì)于低移動(dòng)性的w m n ，網(wǎng)絡(luò)配置與管理仍然是一個(gè)不易解決的問(wèn) 題。 ( 3 ) 共存干擾問(wèn)題：對(duì)于非許可證頻段的刪必然存在與其他共存網(wǎng)絡(luò)的 無(wú)線(xiàn)干擾問(wèn)題。 ( 4 ) 安全問(wèn)題：由于、刪結(jié)構(gòu)本身的脆弱性，極易遭受其他惡意節(jié)點(diǎn)的攻 擊、干擾和竊聽(tīng)，所以安全問(wèn)題是w m n 需要解決的重要問(wèn)題之一。 1 3 2 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的應(yīng)用 m e s h 網(wǎng)絡(luò)將可以為政府與市政應(yīng)用，為城內(nèi)( 如公園等公共場(chǎng)所) 的市民提 供寬帶無(wú)線(xiàn)接入。可成為本地的商業(yè)企業(yè)和傳媒等潛在伙伴，為旅游觀光客等提 供旅游信息的寬帶接入。為無(wú)線(xiàn)服務(wù)提供商( w i s p ) 提供熱點(diǎn)地區(qū)的服務(wù)覆蓋的 延伸，向移動(dòng)用戶(hù)提供高性能的m t 鋤e t 接入服務(wù)。在教育上，將大學(xué)校園網(wǎng)覆蓋 延伸到校外，向身處校外的學(xué)生和教職員工提供無(wú)處不在的寬帶接入。另外在應(yīng) 急通信臨時(shí)網(wǎng)絡(luò)( 臨時(shí)集群通信系統(tǒng)) ，還能為警察、消防等提供應(yīng)急通信服務(wù)， 第一章結(jié)論 7 特別是在通信基礎(chǔ)設(shè)施遭受破壞的突發(fā)事件現(xiàn)場(chǎng)更加重要。它還能為城市地鐵、 輕軌等通勤車(chē)輛提供移動(dòng)w i f i 接入，通過(guò)站臺(tái)無(wú)線(xiàn)a p ，為車(chē)內(nèi)旅客建立移動(dòng) w i f i 環(huán)境，站間信號(hào)可以通過(guò)安裝多個(gè)無(wú)線(xiàn)a p 來(lái)延伸站內(nèi)信號(hào)。在無(wú)線(xiàn)數(shù)字化 家庭，m e s h 能輕松構(gòu)成多媒體家庭無(wú)線(xiàn)網(wǎng)絡(luò)，實(shí)現(xiàn)家庭安全系統(tǒng)聯(lián)網(wǎng)、家庭 h n e m e t 接入、家庭通信設(shè)備互聯(lián)等。 1 4 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)中的主要研究課題 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)在幾個(gè)關(guān)鍵技術(shù)問(wèn)題需要進(jìn)一步研究解決【1 4 l 。 1 ) 天線(xiàn)技術(shù) 無(wú)線(xiàn)m e s h 寬帶網(wǎng)絡(luò)中一個(gè)重要的問(wèn)題就是天線(xiàn)的使用，因?yàn)槊總€(gè)節(jié)點(diǎn)必須和 各個(gè)方向上的多個(gè)節(jié)點(diǎn)通信，很簡(jiǎn)單的一種方式就是采用全向天線(xiàn)，但是這樣覆 蓋范圍有限，并會(huì)帶來(lái)干擾，導(dǎo)致頻譜利用率下降，網(wǎng)絡(luò)容量減小，所以不建議 采用全向天線(xiàn)。智能天線(xiàn)允許頻譜重復(fù)使用，從而能大大提高了頻譜的利用率， 同時(shí)減小了干擾。在e e8 0 2 1 6 a 寬帶無(wú)線(xiàn)接入標(biāo)準(zhǔn)中也建議把智能天線(xiàn)技術(shù)應(yīng) 用到無(wú)線(xiàn)m e s h 寬帶接入網(wǎng)絡(luò)中。 2 ) 路由選擇技術(shù) 無(wú)線(xiàn)m e s h 寬帶接入網(wǎng)絡(luò)中另外一個(gè)很重要的問(wèn)題是路由選擇。當(dāng)節(jié)點(diǎn)增加或 是減少時(shí)，無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的拓補(bǔ)結(jié)構(gòu)會(huì)發(fā)生變化，路由選擇問(wèn)題變得更加復(fù)雜。 3 ) 動(dòng)態(tài)帶寬分配技術(shù) 寬帶無(wú)線(xiàn)接入系統(tǒng)的頻譜資源有限，因此必須使信道資源盡可能被充分利用。 在e e8 0 2 1 6 標(biāo)準(zhǔn)中規(guī)定的點(diǎn)到多點(diǎn)( p m ) 寬帶無(wú)線(xiàn)接入網(wǎng)絡(luò)中采用了動(dòng)態(tài)按 需時(shí)分多址分配d a m at d m a 方式，在這種網(wǎng)絡(luò)中資源的管理和分配由基站負(fù) 責(zé)。而在正e e8 0 2 1 6 a 標(biāo)準(zhǔn)中規(guī)定，對(duì)于基于無(wú)線(xiàn)m e s h 技術(shù)的寬帶接入網(wǎng)絡(luò)，帶 寬的分配可以采用集中調(diào)度方式，或者采用分布調(diào)度方式。如果采用集中調(diào)度方 式，由m e s hb s 節(jié)點(diǎn)收集所有m e s hs s 節(jié)點(diǎn)的資源請(qǐng)求信息，分別為它們分配一 定數(shù)量的帶寬資源。如果采用分布調(diào)度方式，包括m e s hb s 和m e s hs s 在內(nèi)的所 有節(jié)點(diǎn)應(yīng)該相互協(xié)調(diào)，充分利用資源。任何一個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，不能和兩跳以 內(nèi)的鄰近區(qū)域的其它節(jié)點(diǎn)發(fā)送的數(shù)據(jù)產(chǎn)生碰撞。 1 5 本文主要內(nèi)容 本文主要研究無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的路由問(wèn)題，主要包括以下幾個(gè)方面： ( 1 ) 對(duì)當(dāng)前常見(jiàn)幾種路由協(xié)議的研究。 ( 2 ) 重點(diǎn)研究魚(yú)眼分級(jí)路由協(xié)議( f i s h e y eh i e r a r c h i c a lr o u t i n g ，f 瓜) 的原理， 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由技術(shù)的設(shè)計(jì)與實(shí)現(xiàn) 實(shí)現(xiàn)過(guò)程，根據(jù)w m n 的特點(diǎn)提出相應(yīng)的改進(jìn)方案。 ( 3 ) 基于w l a n 的無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的實(shí)現(xiàn) “) w m n 的組網(wǎng)與測(cè)試 全文分為五章，具體安排如下： 第一章是緒論部分，介紹了什么是無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)，無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的典型結(jié) 構(gòu)和應(yīng)用，以及它的發(fā)展現(xiàn)狀以及相關(guān)技術(shù)。 第二章為無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由協(xié)議的設(shè)計(jì)基礎(chǔ)。本章首先總結(jié)了移動(dòng)a dh o c 網(wǎng)絡(luò)路由協(xié)議的分類(lèi)和設(shè)計(jì)思想，然后討論了無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的特點(diǎn)以及路由設(shè)計(jì) 原則和思路。 第三章是本文的重點(diǎn)無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由協(xié)議的詳細(xì)實(shí)現(xiàn)。主要包括路由算 法，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)以及程序?qū)崿F(xiàn)。 第四章首先對(duì)最終系統(tǒng)的設(shè)計(jì)框架進(jìn)行了簡(jiǎn)要說(shuō)明，介紹了除路由外其它模 塊的實(shí)現(xiàn)，然后給出了整個(gè)系統(tǒng)的組網(wǎng)測(cè)試結(jié)果，并對(duì)測(cè)試結(jié)果進(jìn)行了分析。 第二章無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由設(shè)計(jì)基礎(chǔ) 9 第二章無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由設(shè)計(jì)基礎(chǔ) 在第一章中我們提到無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)本質(zhì)是一種a dh o c 網(wǎng)絡(luò)，因此它的路由 協(xié)議可以借鑒a dh o c 網(wǎng)絡(luò)的路由協(xié)議。 現(xiàn)有的a dh o c 網(wǎng)絡(luò)路由協(xié)議可以分為三大類(lèi)：表驅(qū)動(dòng)( t a b l e 一“v c l l ) 路由協(xié)議、 按需( o n - d e l l l a n d ) 路由協(xié)議以及混合式路由協(xié)議。 2 1 移動(dòng)a dh o c 網(wǎng)絡(luò)路由協(xié)議簡(jiǎn)介與比較 2 1 1 表驅(qū)動(dòng)路由協(xié)議 表驅(qū)動(dòng)路由協(xié)議又稱(chēng)為先應(yīng)式路由協(xié)議。在表驅(qū)動(dòng)路由協(xié)議中，每個(gè)節(jié)點(diǎn)需 要維護(hù)一張或多張路由表以記錄該節(jié)點(diǎn)到其它節(jié)點(diǎn)的路由。為了維護(hù)網(wǎng)絡(luò)拓補(bǔ)和 路由信息的一致性，所有節(jié)點(diǎn)都要以定期或觸發(fā)的方式更新路由表。 圖2 1 是現(xiàn)有的部分先驗(yàn)式路由協(xié) 2 ；【1 2 1 。 圖2 1 表驅(qū)動(dòng)路由協(xié)議 這些協(xié)議的主要區(qū)別在于，每個(gè)節(jié)點(diǎn)維護(hù)了不同數(shù)量的表，并且當(dāng)網(wǎng)絡(luò)拓補(bǔ) 變化時(shí)更新信息在網(wǎng)絡(luò)中具有不同的傳輸方式。 表驅(qū)動(dòng)路由協(xié)議里最典型的是基于目的序號(hào)距離矢量( d e s t i n a t i o n s e q u e n c e d d i s t a n c ev e c t o r ，d s d v ) 協(xié)議，它對(duì)b e l h n a n - f o r d 路由算法即距離矢量( d i s 切n c e v e c t o r ，d v ) 算法進(jìn)行了改進(jìn)。以避免在路由表中形成路由環(huán)路。 在這種算法當(dāng)中，每一個(gè)節(jié)點(diǎn)維護(hù)一張包括網(wǎng)內(nèi)所有可能目的地和到它們的 路由跳數(shù)的路由表。每一條記錄帶有一定的序列號(hào)標(biāo)記，該序列號(hào)是由目標(biāo)節(jié)點(diǎn) 分配的。這一序列號(hào)使得移動(dòng)節(jié)點(diǎn)可以區(qū)分過(guò)時(shí)的路由和最近的路由，從而可以 避免路由環(huán)的形成。 路由表更新有兩種方式。一種是全部更新，即拓補(bǔ)更新消息中將包括整個(gè)路 由表，這種方式主要應(yīng)用于網(wǎng)絡(luò)拓補(bǔ)變化較快的情況：另一種方式是部分更新， l o 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由技術(shù)的設(shè)計(jì)與實(shí)現(xiàn) 即更新消息中僅包含變化的路由部分，通常適用于網(wǎng)絡(luò)變化較慢的情況。 在一個(gè)新的路由廣播數(shù)據(jù)包里面包括以下信息：到目標(biāo)節(jié)點(diǎn)的跳數(shù)，到目標(biāo) 節(jié)點(diǎn)的該記錄的序列號(hào)，以及用于廣播的最新的序列號(hào)。節(jié)點(diǎn)總是采用帶有最新 的序列號(hào)的路由信息。當(dāng)兩個(gè)更新信息有相同的序列號(hào)時(shí)，將選用選擇最優(yōu)( 如 跳數(shù)最少) 的那條路由。 2 1 2 按需路由協(xié)議 按需路由( o n d e m a i l d ) 協(xié)議又稱(chēng)反應(yīng)式路由選擇協(xié)議，是一種當(dāng)需要時(shí)才 查找路由的路由選擇方式。節(jié)點(diǎn)并不保存及時(shí)準(zhǔn)確的路由信息。當(dāng)源節(jié)點(diǎn)要向目 的節(jié)點(diǎn)發(fā)送報(bào)文時(shí)，源節(jié)點(diǎn)在網(wǎng)絡(luò)中發(fā)起路由查找過(guò)程，找到相應(yīng)的路由后，才 開(kāi)始發(fā)送報(bào)文。為了提高效率，節(jié)點(diǎn)可以將找到的路由保存在緩存中供后續(xù)發(fā)送 使用。 圖2 2 是現(xiàn)有的部分按需路由協(xié)謝埋】。 圖2 2 按需路由協(xié)議 a dh o c 按需距離矢量路由協(xié)議a o d v ( a dh o co n d e m 孤dd i s t a l l c ev e c t o r r o u t i n g ，a o d v ) 建立在d s d v 算法之上的，但是它并不維持一個(gè)路由表，而是在 需要的時(shí)候才啟動(dòng)路由選擇過(guò)程，因此大大地降低了路由維持的開(kāi)銷(xiāo)。事實(shí)上它 是d s r 和d s d v 的組合，它借用了d s r 的路由發(fā)現(xiàn)和路由維持機(jī)制，利用了d s d v 的按跳( h o pb y h o p ) 路由、順序編號(hào)( s e q ) 和周期更新( 只在路由維持階段) 的機(jī)制。 a o d v 支持單播、多播和廣播通信，在相鄰節(jié)點(diǎn)之間只使用對(duì)稱(chēng)鏈路。通過(guò) 使用特殊的路由錯(cuò)誤信息，可以快速刪除非法路由。a o d o 能及時(shí)對(duì)影響動(dòng)態(tài)路 由的拓補(bǔ)變化作出反應(yīng)。另外，在建立路由時(shí)，除了路由控制分組外，沒(méi)有其他 的網(wǎng)絡(luò)開(kāi)銷(xiāo)，路由開(kāi)銷(xiāo)也很小。 在實(shí)現(xiàn)上，a o d v 包括3 大部分：路由建立、路由維護(hù)和路由刪除。 a o d v 路由建立過(guò)程與d s r 基本一致，是基于一種泛洪路由( n 0 0 d i n gr o u t i n 曲 的方式。網(wǎng)絡(luò)中的節(jié)點(diǎn)在接收到路徑請(qǐng)求報(bào)文后，根據(jù)自己是否是目的節(jié)點(diǎn)，是 否具有能夠到達(dá)目的節(jié)點(diǎn)的有效緩存，或是應(yīng)答路徑請(qǐng)求報(bào)文，或是繼續(xù)轉(zhuǎn)發(fā)路 第二章無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由設(shè)計(jì)基礎(chǔ) 1 i 徑請(qǐng)求報(bào)文。a o d v 協(xié)議采用節(jié)點(diǎn)路由方式，其數(shù)據(jù)分組報(bào)文不需要夾帶路由的 信息，這是與d s r 協(xié)議最大不同處之一。當(dāng)應(yīng)答報(bào)文經(jīng)過(guò)節(jié)點(diǎn)時(shí)( 這表明存在一條 從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑經(jīng)過(guò)本節(jié)點(diǎn)) ，記錄下本節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑，以便 為將來(lái)數(shù)據(jù)分組報(bào)文的到來(lái)提供路由服務(wù)。 網(wǎng)絡(luò)中所有節(jié)點(diǎn)除了記錄路徑信息外，同時(shí)還要維護(hù)用來(lái)區(qū)分新舊不同的路 由信息的序列號(hào)s e q 。當(dāng)節(jié)點(diǎn)收到說(shuō)明到某一節(jié)點(diǎn)的路徑信息的控制報(bào)文( 路徑建立 報(bào)文、應(yīng)答報(bào)文) 時(shí)，對(duì)比檢查報(bào)文中的s e q 值與自己路由緩存中到該節(jié)點(diǎn)路由的 s e q 值，只有在大于等于的情況下才考慮變更路由。 2 1 - 3 混合式路由協(xié)議 混合式路由是將表驅(qū)動(dòng)路由和按需路由結(jié)合起來(lái)，在局部范圍內(nèi)使用表驅(qū)動(dòng) 路由協(xié)議，維護(hù)準(zhǔn)確的路由信息，并可以縮小路由控制消息傳播的范圍，當(dāng)目標(biāo) 節(jié)點(diǎn)較遠(yuǎn)時(shí)，使用按需路由協(xié)議查找發(fā)現(xiàn)路由。 區(qū)域路由協(xié)議( z o n er 0 u t i n gp r o t o c o l ，z i 啦) 是一種典型的混合式路由協(xié)議， 它巧妙的結(jié)合了這兩種路由協(xié)議的特點(diǎn)。z r p 將整個(gè)網(wǎng)絡(luò)分成若干個(gè)以節(jié)點(diǎn)為中 心、一定的跳數(shù)為半徑的虛擬區(qū)。與一般的分級(jí)路由協(xié)議不同，區(qū)內(nèi)的節(jié)點(diǎn)數(shù)與 設(shè)定的區(qū)半徑有關(guān)，因此z r p 的區(qū)重疊程度很高，許多節(jié)點(diǎn)可能同時(shí)屬于多個(gè)區(qū) 域，每個(gè)區(qū)域的半徑長(zhǎng)度由用戶(hù)設(shè)定。 z r p 中，分級(jí)被稱(chēng)“域 。域形成算法比較簡(jiǎn)單，它是通過(guò)一個(gè)重要的協(xié)議參 數(shù)區(qū)域半徑( 以跳數(shù)為單位) ，指定每個(gè)節(jié)點(diǎn)維護(hù)的區(qū)域大小，即所有距離不 超過(guò)區(qū)域半徑的節(jié)點(diǎn)都屬于該區(qū)域。一個(gè)節(jié)點(diǎn)可能同時(shí)從屬于多個(gè)區(qū)域，這是與 分群路由的主要區(qū)別。 為了綜合利用按需路由和主動(dòng)路由的各自?xún)?yōu)點(diǎn)，z r p 規(guī)定每個(gè)節(jié)點(diǎn)采用主動(dòng) 路由協(xié)議維護(hù)去往域內(nèi)節(jié)點(diǎn)的路由，采用按需路由機(jī)制尋找去往區(qū)域外節(jié)點(diǎn)的路 由。 z r p 協(xié)議操作主要包括路由發(fā)現(xiàn)和路由維護(hù)。 路由發(fā)現(xiàn)協(xié)議由三個(gè)部分組成：區(qū)內(nèi)路由協(xié)議、區(qū)間路由協(xié)議和邊界傳播分 解協(xié)議。乃沖的區(qū)內(nèi)路由協(xié)議采用傳統(tǒng)的主動(dòng)路由法，支持距離向量和鏈路狀態(tài) 兩種路由策略，節(jié)點(diǎn)和相鄰節(jié)點(diǎn)之間通過(guò)周期性的交互路由表獲得到區(qū)內(nèi)各節(jié)點(diǎn) 的最新路由。z r p 的區(qū)間路由協(xié)議是一種按需路由協(xié)議，負(fù)責(zé)尋找去往區(qū)外節(jié)點(diǎn) 的路由。邊界路由協(xié)議使得路由查詢(xún)分組只在邊界節(jié)點(diǎn)之間廣播。 z r p 的路由維護(hù)也是混合式的在區(qū)問(wèn)路由維護(hù)中，當(dāng)節(jié)點(diǎn)需要使用的鏈路斷 開(kāi)時(shí)，節(jié)點(diǎn)選擇通知源節(jié)點(diǎn)或進(jìn)行局部查找路由，其局部查找方法和區(qū)間路由協(xié) 議中的路由查找相同，只是查找的范圍較小。 1 2 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由技術(shù)的設(shè)計(jì)與實(shí)現(xiàn) 本文提出的無(wú)線(xiàn)m e s h 路由協(xié)議的基礎(chǔ)魚(yú)眼分級(jí)路由協(xié)議也是一種混合式路 由協(xié)議，下一章將具體予以說(shuō)明。 2 1 4 移動(dòng)a dh o c 網(wǎng)絡(luò)路由協(xié)議的比較 先驗(yàn)式路由選擇協(xié)議通過(guò)連續(xù)的檢測(cè)鏈路質(zhì)量，時(shí)刻維護(hù)準(zhǔn)確的網(wǎng)絡(luò)拓補(bǔ)和 路由信息。其優(yōu)點(diǎn)是發(fā)送報(bào)文時(shí)可立即得到正確的路由信息。但先驗(yàn)式路由需要 大量的控制報(bào)文，開(kāi)銷(xiāo)太大。反應(yīng)式路由協(xié)議中節(jié)點(diǎn)不需要維護(hù)網(wǎng)絡(luò)的拓補(bǔ)結(jié)構(gòu)， 僅當(dāng)需要時(shí)才查找相應(yīng)的路由，這就節(jié)省了路由維護(hù)的開(kāi)銷(xiāo)，特別是當(dāng)網(wǎng)絡(luò)負(fù)荷 不是很重時(shí)，節(jié)省的開(kāi)銷(xiāo)相當(dāng)可觀。但查找路由將引起較大的時(shí)延，不適應(yīng)對(duì)時(shí) 延敏感型應(yīng)用?；旌鲜铰酚蓞f(xié)議對(duì)簇的選擇和維護(hù)方面的算法比較復(fù)雜，并且不 易實(shí)現(xiàn)。另外，如何尋找一種有效地算法來(lái)確定區(qū)域半徑仍是一個(gè)難題。 美國(guó)卡耐基梅隆( c a r n e g i em e l l o n ) 大學(xué)的幾位研究人員對(duì)d s d v ，d s r ，t o r a 和a o d v 四種協(xié)議進(jìn)行了仿真實(shí)驗(yàn)【1 5 】，他們從三個(gè)不同方面對(duì)各個(gè)協(xié)議進(jìn)行了比較。 分組傳遞率：應(yīng)用層信源發(fā)送的分組數(shù)目與信宿接收分組數(shù)目之比。它描 述的是通過(guò)應(yīng)用層觀察到的丟失率，又反映了網(wǎng)絡(luò)所支持的最大吞吐量。 它是路由協(xié)議完成性和正確性的指標(biāo)。 路由開(kāi)銷(xiāo)：路由選擇過(guò)程使用的分組總數(shù)。路由開(kāi)銷(xiāo)是代表協(xié)議擴(kuò)展性的 指標(biāo)，在移動(dòng)無(wú)線(xiàn)m e s h 這樣一個(gè)帶寬和功率受限的環(huán)境中，該參數(shù)顯得 更為重要。 路徑優(yōu)化：協(xié)議選擇路由的路數(shù)與實(shí)際網(wǎng)絡(luò)最短路徑的路數(shù)之差。它表示 路由協(xié)議使用網(wǎng)絡(luò)資源的效率，差值越小，網(wǎng)絡(luò)的效率越高。 圖2 3 是四種協(xié)議的分組傳遞率。當(dāng)節(jié)點(diǎn)移動(dòng)較小時(shí)，四種協(xié)議的分組傳遞 率都很高，當(dāng)無(wú)移動(dòng)時(shí)，分組傳遞率都達(dá)到了1 0 0 。d s r 和a o d v 性能尤其好，節(jié) 點(diǎn)在任何移動(dòng)狀態(tài)都達(dá)到9 5 以上，而d s d v 在暫停時(shí)間小于3 0 0 s ( 節(jié)點(diǎn)移動(dòng)較快) 時(shí)則處于動(dòng)蕩狀態(tài)，分組傳輸率極低。 第二章無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由設(shè)計(jì)基礎(chǔ) 1 3 皿 籟 囊 求 皙停時(shí)同秒 圖2 3 不同協(xié)議的分組傳遞率 從圖2 4 可以看出，四種協(xié)議的開(kāi)銷(xiāo)差別很大，d s r 的開(kāi)銷(xiāo)最小，t o r a 的開(kāi) 銷(xiāo)最大。從曲線(xiàn)的走勢(shì)可以看出，按需路由( t o r a ，d s r 和a o d v ) 隨節(jié)點(diǎn)的移動(dòng)性 減小而降低，而表驅(qū)動(dòng)路由的開(kāi)銷(xiāo)與節(jié)點(diǎn)的移動(dòng)性關(guān)系不明顯。這里d s r 的開(kāi)銷(xiāo) 是按分組數(shù)來(lái)計(jì)算的，當(dāng)按字節(jié)數(shù)來(lái)計(jì)算時(shí)，d s r 的開(kāi)銷(xiāo)會(huì)增加很多，因?yàn)閐 s r 使 用源路由方式，它的完整路徑信息包含在每一個(gè)分組( i p 報(bào)文的頭部) 中，因此它 的所有分組都包含有路由選擇字節(jié)，i p 報(bào)文的有效負(fù)荷降低。應(yīng)當(dāng)指出的是，在 移動(dòng)通信系統(tǒng)中，由于無(wú)線(xiàn)電波存在多普勒遷移現(xiàn)象，使得移動(dòng)節(jié)點(diǎn)發(fā)送的無(wú)線(xiàn) 分組不能過(guò)長(zhǎng)，一般小于5 1 2 字節(jié)，這就更加劇了i p 報(bào)文的有效負(fù)荷問(wèn)題。 圖2 4 不同協(xié)議的路由開(kāi)銷(xiāo) 在圖2 5 ，橫坐標(biāo)表示路由協(xié)議選擇的路由的路數(shù)與實(shí)際網(wǎng)絡(luò)的最短路由路數(shù) 無(wú)線(xiàn)m e s l l 網(wǎng)絡(luò)路由技術(shù)的設(shè)計(jì)與實(shí)現(xiàn) 的差值，即路由優(yōu)化值，縱坐標(biāo)是各個(gè)狀態(tài)下的分組數(shù)目?？删卓闯?，d s d v 和d s r 接近屜優(yōu)，t o r a 和a o d v 則有較大的拖尾，有些路由與最短路由相差4 跳。 。j 二互翻d s d vj _ t o r a l d s r 1 珊a o d v1 - l l - 一 圖25 不同路由優(yōu)化比較 2 2 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由協(xié)議 2 2l 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的特點(diǎn) 州n 繼承了a dh o c 網(wǎng)絡(luò)的特點(diǎn)具有自配置、自組織與自管理等特性，所以 部分傳統(tǒng)的a dh o c 網(wǎng)絡(luò)路由協(xié)議在w 中仍然可用，但需要在州n 路由協(xié)議設(shè)計(jì) 中考慮其特殊性口】。 ( 1 )移動(dòng)性 不同類(lèi)型的網(wǎng)絡(luò)節(jié)點(diǎn)具有不同的移動(dòng)性。眥( m o b i l er o u t e r ) 一般具有很小 的移動(dòng)性，而m c ( m e s hc l i e n t ) 則可為固定節(jié)點(diǎn)或者移動(dòng)節(jié)點(diǎn)。因此在設(shè)計(jì)w 刪 路由協(xié)議時(shí)，最好能夠同時(shí)滿(mǎn)足不同節(jié)點(diǎn)的移動(dòng)性要求。 ( 2 )能量約束 不同類(lèi)型的節(jié)點(diǎn)具有不同的能量約束。m r 通常不以電池為動(dòng)力，所以不需要 考慮能量約束。而m c 則需要運(yùn)行一種能量使用效率較高的路由協(xié)議。 ( 3 )業(yè)務(wù)模式 刪n 作為i n t e r n e t 網(wǎng)絡(luò)的無(wú)線(xiàn)延伸，既要能提供可靠的數(shù)據(jù)傳輸服務(wù)，又要 能提供盡可能好的實(shí)時(shí)數(shù)據(jù)傳輸服務(wù)。因此，w m n 與移動(dòng)a dh o c 網(wǎng)絡(luò)相比，對(duì)q o s 的要求更高。 畦 l l 第二章無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由設(shè)計(jì)基礎(chǔ) 1 5 ( 4 )規(guī)模 w m n 的路由應(yīng)既能應(yīng)用于小規(guī)模臨時(shí)網(wǎng)絡(luò)，又能應(yīng)用于大規(guī)模永久網(wǎng)絡(luò)，同時(shí) 滿(mǎn)足不同網(wǎng)絡(luò)的需求。 由于w m n 具有其特殊性，在設(shè)計(jì)w m n 路由協(xié)議時(shí)，必須考慮以下因素： ( 1 ) 路由判據(jù)：許多已有的a dh o c 網(wǎng)絡(luò)路由協(xié)議均以最小跳數(shù)作為路由判據(jù)。 然而，在靜態(tài)網(wǎng)絡(luò)中該路由的性能并不是最優(yōu)的【1 9 ，2 0 1 。由于干擾沖突、通信距離 等因素的影響，使該路徑的鏈路質(zhì)量惡化，從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的端到端的吞吐 量、誤碼率等性能將變得非常差。 ( 2 ) 負(fù)載均衡：在w m n 中，所有節(jié)點(diǎn)通過(guò)路由協(xié)議共享網(wǎng)絡(luò)資源。因此，w m n 路由協(xié)議必須滿(mǎn)足負(fù)載均衡的這一要求。如當(dāng)網(wǎng)絡(luò)中某些節(jié)點(diǎn)發(fā)生擁塞，并成為 整個(gè)網(wǎng)絡(luò)的瓶頸節(jié)點(diǎn)時(shí)，新的業(yè)務(wù)流應(yīng)能“繞過(guò) 該節(jié)點(diǎn)。可以從兩個(gè)方面來(lái)解 決該問(wèn)題：通過(guò)路由發(fā)現(xiàn)機(jī)制在業(yè)務(wù)流建立階段“繞過(guò) 網(wǎng)絡(luò)中的擁塞區(qū)；利用 路由維護(hù)機(jī)制在鏈路發(fā)現(xiàn)擁塞時(shí)，自動(dòng)選擇其他路徑進(jìn)行數(shù)據(jù)傳輸。此外，以節(jié) 點(diǎn)往返時(shí)間r t t ( r o u n dt r i pt i m e ) 作為性能判據(jù)在一定程度上達(dá)到負(fù)載均衡的目 的。但由于r t t 受鏈路質(zhì)量影響，并不對(duì)所有情況都有效?？傊?，路由判據(jù)需要 在一定程度上滿(mǎn)足負(fù)載均衡的要求。 ( 3 ) 路由容錯(cuò)：在w 刪中，路由發(fā)生錯(cuò)誤時(shí)，需要盡快完成路由重建，以避免 服務(wù)中斷。一般有兩種重建方法：一種是利用緩存路由進(jìn)行數(shù)據(jù)發(fā)送；另一種是 通過(guò)重新執(zhí)行路由查找過(guò)程實(shí)現(xiàn)路由重建。在w 州中，由于m r 移動(dòng)性小，路由錯(cuò) 誤往往是由數(shù)據(jù)沖突造成的，并非實(shí)際鏈路斷裂造成。有兩種方法可以解決該矛 盾：利用跨層設(shè)計(jì)機(jī)制，在m a c 層，對(duì)因沖突而發(fā)送失敗的數(shù)據(jù)包進(jìn)行二次處理； 通過(guò)對(duì)節(jié)點(diǎn)增加路由緩存功能，對(duì)暫時(shí)不能發(fā)送的數(shù)據(jù)包進(jìn)行緩存，待無(wú)線(xiàn)信道 質(zhì)量變好時(shí)再次嘗試發(fā)送。 ( 4 ) 網(wǎng)絡(luò)容量：隨著網(wǎng)絡(luò)規(guī)模的增大，利用廣播機(jī)制進(jìn)行路由查找的方法會(huì)消 耗很多網(wǎng)絡(luò)資源。同時(shí)，由于大規(guī)模網(wǎng)絡(luò)建立路徑時(shí)將花費(fèi)很長(zhǎng)時(shí)間，使端到端 的延時(shí)變大，一旦路徑建立起來(lái)，由于路徑發(fā)生變化又需要消耗很大的網(wǎng)絡(luò)資源 進(jìn)行路由重建。 ( 5 ) 如何在w m n 中為用戶(hù)提供q o s 保證，是一個(gè)新的研究課題【5 1 。 2 2 2 無(wú)線(xiàn)m e s h 網(wǎng)路由設(shè)計(jì)原則與思路 ( 1 )多判據(jù)路由 典型的路由判別方法有以下三種：平均傳輸次數(shù)e t x ( e x p e c t e dt r a n s m i s s i o n c o u n t ) 、往返時(shí)間r t t ( r o u n dt r i pt i m e ) 和數(shù)據(jù)對(duì)延遲時(shí)間p k t p a i r ( p a c k e t p a i r l a t e n c y ) 。將這三個(gè)路由判據(jù)與最小跳數(shù)h o p ( h o pc o u n t ) 作為判據(jù)進(jìn)行對(duì)比發(fā)現(xiàn)， 1 6 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由技術(shù)的設(shè)計(jì)與實(shí)現(xiàn) 當(dāng)節(jié)點(diǎn)完全靜止時(shí)e t x 獲得最好的性能【1 9 ，2 0 】；r t t 與p k t p a i r 由于沖突的影響，性 能稍差；但在網(wǎng)絡(luò)節(jié)點(diǎn)移動(dòng)時(shí)，h o p 則優(yōu)于其他三種判據(jù)。這是因?yàn)楣?jié)點(diǎn)移動(dòng)時(shí)， e t x 不能及時(shí)反映出鏈路質(zhì)量的變化。研究表明，以e t x 為判據(jù)的路由協(xié)議在1 j | m n 中加入移動(dòng)節(jié)點(diǎn)時(shí)性能還不夠完善，需要提出更優(yōu)的性能判據(jù)。同時(shí)，由于單一 的路由判據(jù)很難反映出鏈路質(zhì)量對(duì)各個(gè)性能指標(biāo)帶來(lái)的影響，所以在制定路由判 據(jù)時(shí)，應(yīng)使用多路由準(zhǔn)則來(lái)解決。 ( 2 )多信道路由 在w m n 中，使用多信道的方式有多種，如單收發(fā)器多信道、多收發(fā)器多信道 等方式。使用多信道與多收發(fā)器能夠較大地提高w m n 的網(wǎng)絡(luò)吞吐量。使用多收發(fā) 器可以在不需要修改m a c 協(xié)議的基礎(chǔ)上提升網(wǎng)絡(luò)性能。通過(guò)對(duì)m r - l q s r 協(xié)議的仿 真結(jié)果表明【2 0 】，該方案能較好的提高網(wǎng)絡(luò)性能。同時(shí)，該協(xié)議提出了適應(yīng)多信道 條件下的路由判據(jù)w c e e t ，綜合考慮了不同信道上的延時(shí)、帶寬等信息。 ( 3 ) 多徑路由 多徑技術(shù)可以很好地避免單徑時(shí)的網(wǎng)絡(luò)震蕩影響，在充分利用帶寬等網(wǎng)絡(luò)資 源的同時(shí)實(shí)現(xiàn)負(fù)載均衡、路由迂回和容錯(cuò)等。在其中某條鏈路因?yàn)樾诺蕾|(zhì)量惡化 不能正常工作時(shí)，其他鏈路可以繼續(xù)使用，因此，也可以在路由故障時(shí)，避免路 由重建等操作。多徑路由比較復(fù)雜，尤其對(duì)于僅靠路由表驅(qū)動(dòng)的路由協(xié)議。采用 多徑技術(shù)后數(shù)據(jù)包到達(dá)的順序可能得不到保證。此時(shí)，上層協(xié)議是否需要作相應(yīng) 的改動(dòng)等問(wèn)題還有待研究。由于多徑路由可以很好地滿(mǎn)足負(fù)載均衡與路由容錯(cuò)這 一特點(diǎn)，所以它的研究是個(gè)熱點(diǎn)。 ( 4 )分級(jí)路由 分級(jí)路由主要解決a dh o e 網(wǎng)絡(luò)路由協(xié)議在網(wǎng)絡(luò)規(guī)模變大時(shí)網(wǎng)絡(luò)性能降低的問(wèn) 題。通過(guò)分級(jí)技術(shù)，在簇內(nèi)與簇問(wèn)使用不同的路由，分別發(fā)揮其優(yōu)點(diǎn)，從而實(shí)現(xiàn) 大規(guī)模w m n 路由協(xié)議。若所有的數(shù)據(jù)業(yè)務(wù)都需要通過(guò)簇頭轉(zhuǎn)發(fā)，則簇頭將成為整 個(gè)網(wǎng)絡(luò)的瓶頸。若數(shù)據(jù)業(yè)務(wù)不通過(guò)簇頭轉(zhuǎn)發(fā)，該路由的設(shè)計(jì)變得更加復(fù)雜。一種 方法是在簇內(nèi)和簇間使用不同的路由協(xié)議。簇內(nèi)路由協(xié)議為基于d s r 的反應(yīng)式路 由協(xié)議，該協(xié)議能夠很好地適應(yīng)簇內(nèi)用戶(hù)移動(dòng)快的特點(diǎn)；簇間使用先應(yīng)式路由協(xié) 議，反映了簇之間移動(dòng)性小的特點(diǎn)。 ( 5 )跨層路由 路由協(xié)議與m a c 協(xié)議之間的跨層設(shè)計(jì)是另一個(gè)研究課題，以往的研究都集中 在網(wǎng)絡(luò)第三層上，結(jié)果并不理想。可以從第二層提取一些參數(shù)信息作為路由判據(jù)， 僅僅在m a c 層與路由層之間進(jìn)行數(shù)據(jù)交換也許還不夠，還可以考慮合并m a c 與路 由層之間的一些功能。研究表明，跨層設(shè)計(jì)可以使路由協(xié)議收集到節(jié)點(diǎn)底層的實(shí) 際數(shù)據(jù)傳輸情況，做出正確的路徑選擇，對(duì)網(wǎng)絡(luò)性能的提高有很大的意義。 ( 6 )q o s 路由 第二章無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由設(shè)計(jì)基礎(chǔ) 1 7 如何為用戶(hù)提供q o s 保證是當(dāng)前路由研究的熱點(diǎn)問(wèn)題。特別是對(duì)于實(shí)時(shí)業(yè)務(wù)， 如何提供q o s 支持更是迫切需要解決的。q o s 路由的主要思想是：首先，需要選擇 滿(mǎn)足用戶(hù)各種q o s 要求的到達(dá)目的節(jié)點(diǎn)的路徑；其次，在路徑建立后，若當(dāng)前路 徑已經(jīng)不能滿(mǎn)足用戶(hù)q o s 需求，則節(jié)點(diǎn)需要尋找新的路由。通常的方法是對(duì)網(wǎng)絡(luò) 剩余帶寬進(jìn)行估計(jì)，選擇滿(mǎn)足用戶(hù)需求的路徑，為用戶(hù)提供特定帶寬要求的q o s 保證【5 1 。 第三章m e s h 系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 1 9 第三章m e s h 系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) 混合結(jié)構(gòu)的無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)( 見(jiàn)圖1 1 6 ) 是一個(gè)分級(jí)網(wǎng)絡(luò)，它的上層網(wǎng)絡(luò)由 m e s h 路由器構(gòu)成，下層網(wǎng)絡(luò)由m e s h 終端構(gòu)成。本文研究的主要內(nèi)容是中m e s h 終 端的實(shí)現(xiàn)。內(nèi)容包括系統(tǒng)設(shè)計(jì)原理，模塊組成，以及各模塊尤其是路由的實(shí) 現(xiàn)。 3 1 系統(tǒng)設(shè)計(jì)原理 i e e e8 0 2 1 1 標(biāo)準(zhǔn)定義了兩種組網(wǎng)結(jié)構(gòu)：獨(dú)立基本服務(wù)組( i n d i v i d u a lb a s i c s e r v i c es e t ，i b s s ) 和擴(kuò)展服務(wù)組( e x t e n d e ds e r v i c es e t ，e s s ) 。獨(dú)立基本服 務(wù)組是一種對(duì)等網(wǎng)絡(luò)形式，所有站點(diǎn)在網(wǎng)絡(luò)中通信的地位是平等的，也稱(chēng)為a dh o c 組網(wǎng)形式，這正是無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)的原型。 然而，8 0 2 1 1 標(biāo)準(zhǔn)定義的i b s s 組網(wǎng)方式，提供的只是a dh o c 組網(wǎng)的基礎(chǔ)通 信手段，只能組成單跳的a dh o c 網(wǎng)，多跳a dh o c 網(wǎng)絡(luò)、對(duì)站點(diǎn)的移動(dòng)性支持， 僅靠8 0 2 1 1 是無(wú)法實(shí)現(xiàn)的，因?yàn)? 0 2 1 1 標(biāo)準(zhǔn)沒(méi)有提供對(duì)中繼功能的支持。如果 需在m a c 子層進(jìn)行中繼，只能在一些非常特殊環(huán)境下可以實(shí)現(xiàn)，無(wú)法在一般環(huán)境 下實(shí)現(xiàn)中繼，更無(wú)法提供對(duì)移動(dòng)的支持。中繼功能只能在m a c 子層之上來(lái)實(shí)現(xiàn)。 m a c 子層無(wú)法實(shí)現(xiàn)中繼的原因是m a c 的幀格式適用于固定網(wǎng)絡(luò)而不適用于拓補(bǔ) 結(jié)構(gòu)動(dòng)態(tài)變化中的網(wǎng)絡(luò)，如a dh o c 多跳網(wǎng)絡(luò)情況。 。薯圣；一 ( b ) c - 卜 ( c ) 圖3 1 模糊中繼 圖3 1 ( a ) 所示，讓b 固定為a 和c 之間的數(shù)據(jù)提供中繼是可行的，但若存在 移動(dòng)時(shí)就無(wú)法工作了，例如b 和c 互換位置，就無(wú)法工作了。 如果站點(diǎn)有一點(diǎn)點(diǎn)移動(dòng)發(fā)生，形成圖3 1 ( b ) 的情況，那么，b 站再提供中繼 就是沒(méi)有必要的。除非a 和c 站仍堅(jiān)持采用b 的中繼來(lái)通信。 如果是圖3 1 ( c ) 情況，網(wǎng)絡(luò)就會(huì)癱瘓。b 在為a c 中繼的同時(shí)，也會(huì)收到d 為a c 中繼的幀，并繼續(xù)中繼，d 也樣。形成b d 間的中繼循環(huán)。 奄 圓一 。加， 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)路由技術(shù)的設(shè)計(jì)與實(shí)現(xiàn) 只要在網(wǎng)絡(luò)上有移動(dòng)存在，m a c 層就無(wú)法確定如何中繼( 這個(gè)現(xiàn)象有時(shí)也被稱(chēng) 為“模糊中繼 ) 。因此，要實(shí)現(xiàn)中繼，就需要b 能夠“知道 a 、c 之間是否可以 直接通信，對(duì)于這種非本地鏈路的認(rèn)知顯然應(yīng)該是網(wǎng)絡(luò)層的路由協(xié)議來(lái)維護(hù)。目 前大多數(shù)無(wú)線(xiàn)多跳網(wǎng)絡(luò)的實(shí)現(xiàn)中都采用阻斷鏈路層中繼，在網(wǎng)絡(luò)層由路由方法來(lái) 實(shí)現(xiàn)中繼。本文正是在此基礎(chǔ)上完善了網(wǎng)絡(luò)層的路由協(xié)議，使無(wú)線(xiàn)網(wǎng)絡(luò)中的普通 節(jié)點(diǎn)具備了簡(jiǎn)單的路由功能，實(shí)現(xiàn)了網(wǎng)絡(luò)中數(shù)據(jù)的多跳傳輸，為構(gòu)成混合結(jié)構(gòu)的 無(wú)線(xiàn)m e s h 網(wǎng)絡(luò)做好了客戶(hù)端準(zhǔn)備。 3 2 系統(tǒng)設(shè)計(jì)框架 在w i n d o w s 開(kāi)發(fā)平臺(tái)上，網(wǎng)絡(luò)層已經(jīng)被封裝，向上完全透明，因此我們無(wú)法 直接修改路由協(xié)議，只能在應(yīng)用層上補(bǔ)充實(shí)現(xiàn)，完成選路、中繼等路由功