[優(yōu)秀畢業(yè)設(shè)計(jì)精品] 基于隱馬爾科夫模型的移動(dòng)節(jié)點(diǎn)路徑預(yù)測(cè)算法設(shè)計(jì)

1、<p><b>　　第1章 緒論</b></p><p>　　1.1 論文的背景</p><p>　　無線移動(dòng)自組織網(wǎng)絡(luò)（Ad hoc Network）技術(shù)研究始于二十世紀(jì)七十年代，美國國防部高級(jí)研究計(jì)劃署（DARPA）出于軍事需要，開始研究分組無線網(wǎng)PRNET（Packet Radio Network）在戰(zhàn)場(chǎng)環(huán)境下數(shù)據(jù)通信中的應(yīng)用，與傳統(tǒng)無線網(wǎng)絡(luò)不同的

2、是Ad hoc網(wǎng)絡(luò)既不需要固定的網(wǎng)絡(luò)結(jié)構(gòu)，也沒有專用固定的基站或路由器作為網(wǎng)絡(luò)的管理中心。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)均具有路由器的功能，能夠發(fā)現(xiàn)和維護(hù)到其他節(jié)點(diǎn)的路由，并且可以任意移動(dòng)、拓?fù)浣Y(jié)構(gòu)高度變化。由于具備組網(wǎng)簡單靈活、成本低、生存能力強(qiáng)等特點(diǎn)，其應(yīng)用范圍不斷擴(kuò)大，由原來的軍用領(lǐng)域擴(kuò)大到地震、火災(zāi)等應(yīng)急通信領(lǐng)域。近年來，國外很多著名實(shí)驗(yàn)室紛紛設(shè)立蜂窩網(wǎng)與自組織網(wǎng)絡(luò)結(jié)合方面的研究項(xiàng)目，我國對(duì)未來移動(dòng)通信的研究也正式列入“863”項(xiàng)目，移動(dòng)自組

3、網(wǎng)極有可能成為未來移動(dòng)通信系統(tǒng)的網(wǎng)絡(luò)構(gòu)架。</p><p>　　1.2 移動(dòng)自組網(wǎng)的研究現(xiàn)狀與應(yīng)用</p><p>　　九十年代以來，無線移動(dòng)自組織網(wǎng)絡(luò)的研究在世界范圍內(nèi)方興未艾，已經(jīng)從無線通信領(lǐng)域中的一個(gè)小分支逐漸擴(kuò)大到相對(duì)較獨(dú)立的領(lǐng)域。目前，無論在國際上還是在區(qū)域上，周期性的Ad hoc網(wǎng)絡(luò)學(xué)術(shù)會(huì)議日益增多，Ad hoc網(wǎng)絡(luò)成果主要在以下幾個(gè)方面：</p><p&

4、gt;　?。?） 提出新的路由協(xié)議。Ad hoc路由面臨的主要挑戰(zhàn)是：傳統(tǒng)的保存在結(jié)點(diǎn)中的分布式路由數(shù)據(jù)庫如何適應(yīng)網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化。新協(xié)議一般以廣播或組播方式建立網(wǎng)絡(luò)路由，核心是減少廣播風(fēng)暴。目前，一般普遍得到認(rèn)可的代表性成果有DSDV、WRP、AODV、DSR、TORA和ZRP等。源頭性的創(chuàng)新性研究主要集中在2001年以前，后續(xù)的成果多為這些協(xié)議的改進(jìn)，目前，路由協(xié)議的研究仍然是Ad hoc網(wǎng)絡(luò)成果最集中的部分。不過，從實(shí)現(xiàn)的難度來

5、看，這些協(xié)議離適用性還有一定的距離。</p><p>　　（2） 提出基于Ad hoc網(wǎng)絡(luò)的媒體接入控制（MAC）協(xié)議。主要是解決隱藏終端和暴露終端問題，影響比較大的有MACA協(xié)議，即RTS/CTS/ACK方案，控制信道和數(shù)據(jù)信道分裂的雙信道方案和基于定向天線的MAC協(xié)議，以及一些改進(jìn)類的MAC協(xié)議。有一些研究則是側(cè)重于將IEEE 802.11的MAC協(xié)議移植到Ad hoc網(wǎng)絡(luò)中?；诙ㄏ蛱炀€的MAC協(xié)議在理論上

6、性能較為優(yōu)越，但在技術(shù)上實(shí)現(xiàn)的難度較大。</p><p>　?。?） Ad hoc網(wǎng)絡(luò)與蜂窩網(wǎng)的互連互通。研究并提出了一種ICAR（internet Cellular and Ad hoc Realy）系統(tǒng)，提供蜂窩小區(qū)內(nèi)信號(hào)的補(bǔ)盲。該方案給出了在加入補(bǔ)盲點(diǎn)之后系統(tǒng)性能改善的性能評(píng)價(jià)。從結(jié)果看，該系統(tǒng)只是針對(duì)目前的2G系統(tǒng)，尚無法聯(lián)系到基于IP方式的分組網(wǎng)絡(luò)。最近，提出了一種在蜂窩網(wǎng)上覆蓋一個(gè)無線多跳網(wǎng)絡(luò)的方案，

7、其中用一些無線路由器來代替蜂窩網(wǎng)絡(luò)中的一些結(jié)點(diǎn)。通過優(yōu)化路由、信道規(guī)劃和功率控制等使系統(tǒng)在發(fā)射功率受限的情況下達(dá)到系統(tǒng)吞吐量最大化，其他方面沒有太多的貢獻(xiàn)。</p><p>　　（4） 基于Ad hoc網(wǎng)絡(luò)的多播/組播協(xié)議、TCP協(xié)議、地址分配、功率（節(jié)能）控制、安全性問題、分布式算法、QoS等方面有一些研究成果，但各部分的數(shù)量相對(duì)較少。其中，比較有意思的有，試圖把移動(dòng)IP擴(kuò)展到Ad Hoc網(wǎng)絡(luò)，基本方案是要用特

8、定的RIP協(xié)議（Routing Information Protocol）作為路由協(xié)議，但這種方案與Ad hoc網(wǎng)絡(luò)的其他路由協(xié)議不相容。</p><p>　?。?） 在實(shí)驗(yàn)和應(yīng)用網(wǎng)絡(luò)的構(gòu)建上，最近比較值得注意的是，一些學(xué)者正在研究用藍(lán)牙節(jié)點(diǎn)組建Ad hoc網(wǎng)絡(luò)。就藍(lán)牙本身的技術(shù)來說，藍(lán)牙可以組成微微網(wǎng)（piconet），微微網(wǎng)通過橋節(jié)點(diǎn)（bridge）互連，可以形成多跳的Ad hoc網(wǎng)絡(luò)，也稱為藍(lán)牙散射網(wǎng)（sc

9、atternet）。藍(lán)牙規(guī)范尚未對(duì)藍(lán)牙微微網(wǎng)之間的通信和基于藍(lán)牙的Ad hoc網(wǎng)絡(luò)的形成等內(nèi)容做出具體描述，這是一個(gè)開放的問題，目前已有一些文獻(xiàn)針對(duì)基于藍(lán)牙的Ad hoc網(wǎng)絡(luò)的形成提出了各種不同的協(xié)議或方案。</p><p>　?。?） 國內(nèi)學(xué)者所發(fā)表的Ad hoc網(wǎng)絡(luò)的研究成果較少。從2001年起，開始有少量 成果發(fā)表，研究類的論文大約有數(shù)十篇，主要成果基本上集中在路由協(xié)議的一些改進(jìn)，少量成果涉及MAC協(xié)議的研

10、究。可以說國內(nèi)在該研究領(lǐng)域基本上是剛剛起步。</p><p>　　移動(dòng)自組網(wǎng)潛在的應(yīng)用很多，主要可以分為以下幾類：</p><p>　?。?）在軍事通信領(lǐng)域中，由于移動(dòng)自組網(wǎng)具有快速展開與組織，抗毀性強(qiáng)，通信距離遠(yuǎn)等特點(diǎn)，在現(xiàn)代化戰(zhàn)場(chǎng)上，可以方便快捷的完成車輛、機(jī)群、艦隊(duì)和士兵間的統(tǒng)一指揮，協(xié)調(diào)作戰(zhàn)。</p><p>　?。?）應(yīng)用于緊急搜救，在地震、洪水等自然災(zāi)害

11、發(fā)生時(shí)，固定的網(wǎng)絡(luò)基礎(chǔ)設(shè)施遭到破壞，要重新建立這些固定設(shè)施不僅耗時(shí)，有時(shí)甚至是不可能的。移動(dòng)自組網(wǎng)絡(luò)不需固定通信設(shè)施的支持，且組網(wǎng)靈活、快捷，因此，可作為救援小分隊(duì)的通信網(wǎng)絡(luò)。支持實(shí)時(shí)的災(zāi)情報(bào)告、救援的組織協(xié)調(diào)等。 </p><p>　　（3）應(yīng)用于移動(dòng)會(huì)議，在室外臨時(shí)環(huán)境中，工作團(tuán)體所有成員可以通過Ad hoc網(wǎng)絡(luò)方式組成一個(gè)臨時(shí)網(wǎng)絡(luò)來協(xié)同完成一項(xiàng)任務(wù)，在室內(nèi)更可通過無線方式上傳下載文件。</p>

12、<p>　　其次移動(dòng)自組網(wǎng)在家庭關(guān)網(wǎng)、傳感器網(wǎng)絡(luò)，、個(gè)人通信方面都有很好的應(yīng)用前景。</p><p><b>　　1.3 問題提出</b></p><p>　　由于移動(dòng)自組網(wǎng)絡(luò)內(nèi)的每個(gè)節(jié)點(diǎn)都可以隨機(jī)移動(dòng)，所以有了網(wǎng)絡(luò)組建靈活的特性，同時(shí)也給網(wǎng)絡(luò)的開發(fā)帶來了很大的難度，當(dāng)移動(dòng)節(jié)點(diǎn)在子網(wǎng)間切換時(shí)，通信中斷就很難避免，并會(huì)產(chǎn)生較大的切換時(shí)延，如果能預(yù)測(cè)移動(dòng)節(jié)

13、點(diǎn)的移動(dòng)方向和將要連接的接入路由器，就可以使移動(dòng)節(jié)點(diǎn)為可能發(fā)生的切換提前做好準(zhǔn)備，為避免或減小通信中斷和時(shí)延贏得時(shí)間。</p><p>　　目前所提出的預(yù)測(cè)模型大致可分為基于概率統(tǒng)計(jì)模型的和基于人工神經(jīng)網(wǎng)絡(luò)的兩類。雖然后者能夠構(gòu)建出更為精確的分類界面，但需要大量的訓(xùn)練數(shù)據(jù)才能進(jìn)行參數(shù)估計(jì)，計(jì)算復(fù)雜度高，模型收斂慢，因此在路徑預(yù)測(cè)問題中大量使用的是基于概率統(tǒng)計(jì)模型的方法。本文基于隱馬爾科夫模型（HMM：Hidden

14、 Markov Model）提出一種新的移動(dòng)節(jié)點(diǎn)的移動(dòng)路徑預(yù)測(cè)模型。</p><p>　　第2章 無線移動(dòng)自組織網(wǎng)相關(guān)理論</p><p>　　2.1 無線通信簡介</p><p>　　無線通信，顧名思義，是不借助有線傳輸媒介，而通過電磁波在空間傳播來傳遞信息的通信方式。無線通信的特點(diǎn)就在于它的傳播媒介—無線通信具有以下特征。</p><p&

15、gt;　　廣播性：一個(gè)發(fā)射機(jī)發(fā)送，多個(gè)接收機(jī)都可以接受；</p><p>　　信道隨空間而變化：隨著空間環(huán)境的不同，信道特性往往不同；</p><p>　　信道隨時(shí)間而變化：有快速變化和較慢的變化區(qū)別；</p><p>　　傳播距離有限：發(fā)送信號(hào)隨距離增大在逐漸衰減，信號(hào)衰減到一</p><p>　　定程度，接收機(jī)將不能正確接受；</p

16、><p>　　多徑效應(yīng)：信號(hào)可沿不同路徑到達(dá)接收機(jī)，造成衰減和時(shí)延擴(kuò)展；</p><p>　　相互之間形成干擾：多個(gè)發(fā)射機(jī)發(fā)送的信號(hào)可能會(huì)在接受端疊加，</p><p>　　形成相互干擾，從而對(duì)信號(hào)的爭取接受造成影響。</p><p>　　所謂無線通信系統(tǒng)，就是采用無線通信技術(shù)的通信系統(tǒng)，它是通信系統(tǒng)的一個(gè)組成部分，從整個(gè)通信網(wǎng)整體而言，無線通信

17、系統(tǒng)處于通信網(wǎng)的末端，它往往被用來解決接入問題。</p><p>　　無線通信系統(tǒng)有兩種網(wǎng)絡(luò)結(jié)構(gòu)：有基礎(chǔ)設(shè)施網(wǎng)和無基礎(chǔ)設(shè)施網(wǎng)。下面分別介紹這兩種結(jié)構(gòu)。</p><p>　　有基礎(chǔ)設(shè)施網(wǎng)絡(luò)結(jié)構(gòu)：通常是對(duì)有線通信網(wǎng)的一種擴(kuò)展。有線網(wǎng)被用作骨干網(wǎng)，連接到特殊的有線/無線轉(zhuǎn)接節(jié)點(diǎn)，即基站或接入點(diǎn)，基站負(fù)責(zé)協(xié)調(diào)覆蓋區(qū)內(nèi)的移動(dòng)節(jié)點(diǎn)通過一個(gè)或多個(gè)傳輸信道接入網(wǎng)絡(luò)?；竞陀芯€骨干網(wǎng)相連并且覆蓋一個(gè)區(qū)域，它

18、必須被預(yù)先規(guī)劃、設(shè)計(jì)和布設(shè)，因此這種網(wǎng)絡(luò)結(jié)構(gòu)被稱為有基礎(chǔ)設(shè)施網(wǎng)絡(luò)結(jié)構(gòu)。有基礎(chǔ)設(shè)施網(wǎng)包含很多種類，比較典型的有：蜂窩移動(dòng)通信系統(tǒng)、集群移動(dòng)通信系統(tǒng)、無線局域網(wǎng)等。</p><p>　　無基礎(chǔ)設(shè)施網(wǎng)絡(luò)結(jié)構(gòu)：一般也稱為自組織網(wǎng)絡(luò)（簡稱自組網(wǎng)），自組網(wǎng)是由多個(gè)移動(dòng)節(jié)點(diǎn)組成的多跳無線網(wǎng)絡(luò)。這些移動(dòng)節(jié)點(diǎn)處在一個(gè)局域區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)都具備路由器的功能，可以通過存儲(chǔ)轉(zhuǎn)發(fā)技術(shù)幫助其他節(jié)點(diǎn)構(gòu)成通信鏈路。網(wǎng)絡(luò)的組織是臨時(shí)的、按需的、自

19、動(dòng)的。由于自組網(wǎng)無基礎(chǔ)設(shè)施，導(dǎo)致無控制中心，因此必須采用分布式的控制方式。自組網(wǎng)特別適用于要求臨時(shí)、快速組網(wǎng)的情況，所以經(jīng)常用于軍事領(lǐng)域、災(zāi)難救援、會(huì)議等場(chǎng)合。</p><p>　　2.2 無線移動(dòng)自組織網(wǎng)概述</p><p>　　無線移動(dòng)自組織網(wǎng)英文名最常用的是Ad hoc Network。它是一種不依賴于固定通信設(shè)施的由若干無線通信設(shè)備構(gòu)成的分布式無線分組網(wǎng)絡(luò)。網(wǎng)絡(luò)中的節(jié)點(diǎn)既是終端，

20、又是路由器，不在彼此覆蓋范圍內(nèi)的無線節(jié)點(diǎn)之間的通信可經(jīng)中間節(jié)點(diǎn)的轉(zhuǎn)發(fā)來完成。</p><p>　　無線移動(dòng)自組織網(wǎng)絡(luò)具有如以下特點(diǎn)：</p><p><b>　?。?） 多跳網(wǎng)</b></p><p>　　由于無線通信距離受限，自組網(wǎng)內(nèi)節(jié)點(diǎn)間的通信往往需要借助其他節(jié)點(diǎn)中繼轉(zhuǎn)發(fā)才能實(shí)現(xiàn)，這樣就形成了多跳通信路徑。</p><p

21、>　　（2） 網(wǎng)絡(luò)的動(dòng)態(tài)拓?fù)?lt;/p><p>　　自組網(wǎng)中節(jié)點(diǎn)間的互相連通性構(gòu)成了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。自組網(wǎng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)往往采用拓?fù)鋱D的方式表達(dá)。在拓?fù)鋱D中，頂點(diǎn)代表一個(gè)移動(dòng)節(jié)點(diǎn)；邊代表兩個(gè)移動(dòng)節(jié)點(diǎn)間的無線鏈路，表明這兩個(gè)節(jié)點(diǎn)在對(duì)方的無線傳輸范圍內(nèi)。如圖2-1所示。由于自組網(wǎng)中節(jié)點(diǎn)可以以較隨意的速度和方式移動(dòng)，加上發(fā)射功率的變化，以及無線信道的干擾大小頻繁變化的因素，節(jié)點(diǎn)間通過無線通信形成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可能隨

22、時(shí)發(fā)生變化，而且變化的方式和速度都是難以預(yù)測(cè)的。圖2.2給出了由于B節(jié)點(diǎn)的移動(dòng)而造成的圖2.1網(wǎng)絡(luò)拓?fù)涞淖兓?lt;/p><p>　　圖2.1 自組網(wǎng)拓?fù)鋱D 圖2.2 拓?fù)渥兓?lt;/p><p><b>　　（3）分布式控制</b></p><p>　　在自組網(wǎng)中，為了實(shí)現(xiàn)網(wǎng)內(nèi)成員之間的通信，一定要解決無線資源使用、路由發(fā)現(xiàn)等控制問題

23、。由于自組網(wǎng)沒有預(yù)設(shè)的基礎(chǔ)設(shè)施，也就是沒有預(yù)設(shè)的中心控制節(jié)點(diǎn)，所以只能采用分布式控制的方式來完成。分布式控制與集中式控制是一對(duì)相對(duì)的概念。通俗來講，集中式控制就是把“成員”之間需要協(xié)調(diào)的所有事情上交中心（領(lǐng)導(dǎo)）仲裁分配，例如蜂窩網(wǎng)；分布式控制則是由每個(gè)“成員”按照預(yù)先確定的一套規(guī)則，各自依據(jù)自己掌握的局部信息獨(dú)自計(jì)算和管理，例如自組網(wǎng)。如果把自組網(wǎng)和蜂窩網(wǎng)同人類社會(huì)相類比，自組網(wǎng)就如同一個(gè)沒有預(yù)先確定“領(lǐng)導(dǎo)”的“組織”；蜂窩網(wǎng)則正好相反

24、，是一個(gè)預(yù)先選定了領(lǐng)導(dǎo)的“組織”。</p><p><b>　　（4）對(duì)等性</b></p><p>　　與蜂窩網(wǎng)不同，自組網(wǎng)中節(jié)點(diǎn)與節(jié)點(diǎn)之間可以直接互通。在蜂窩網(wǎng)中，移動(dòng)終端與移動(dòng)終端之間不能直接互通，只能通過基站才能實(shí)現(xiàn)連通。這是因?yàn)榛九c移動(dòng)終端是完全不同的設(shè)備，基站與移動(dòng)終端之間的雙向鏈路被分成了上/下行鏈路，移動(dòng)終端能夠接下行鏈路的信號(hào)，但往往不能接收上行鏈

25、路的信號(hào)。蜂窩網(wǎng)中這樣做是因?yàn)榛九c終端之間有主從之分，而在自組網(wǎng)中，一般每個(gè)節(jié)點(diǎn)都相同，無主從之分，所以，每個(gè)節(jié)點(diǎn)應(yīng)當(dāng)能支持邏輯上的自發(fā)自收，也就是節(jié)點(diǎn)之間的來去雙向鏈路都相同。因此，自組網(wǎng)節(jié)點(diǎn)的無線通信裝置一般采用時(shí)分雙工方式（TDD）。</p><p><b>　?。?）臨時(shí)性</b></p><p>　　當(dāng)幾個(gè)自組網(wǎng)的節(jié)點(diǎn)聚集在一起時(shí)，他們就會(huì)臨時(shí)性地組成一個(gè)

26、無線通信網(wǎng)絡(luò)，無需預(yù)先的規(guī)劃，無需預(yù)先建設(shè)的基礎(chǔ)實(shí)施。這種臨時(shí)性包括：網(wǎng)絡(luò)成員的臨時(shí)性，網(wǎng)絡(luò)組織的臨時(shí)性，網(wǎng)絡(luò)拓?fù)涞呐R時(shí)性，網(wǎng)絡(luò)路由的臨時(shí)性，網(wǎng)絡(luò)無線資源分配采用按需臨時(shí)分配等。</p><p><b>　?。?）自組織性</b></p><p>　　自組網(wǎng)不依賴于基站等基礎(chǔ)設(shè)施的支持，可以在任何時(shí)刻、任何地點(diǎn)構(gòu)成網(wǎng)絡(luò)以實(shí)現(xiàn)移動(dòng)節(jié)點(diǎn)的信息交互。具體而言，在自組網(wǎng)中，網(wǎng)

27、絡(luò)路由的計(jì)算、網(wǎng)絡(luò)臨時(shí)結(jié)構(gòu)的形成不需要外部參與，都可以依據(jù)當(dāng)時(shí)的情況自我組織，并隨環(huán)境變化自適應(yīng)的自我調(diào)整。</p><p><b>　?。?）鏈路帶寬受限</b></p><p>　　自組網(wǎng)采用無線傳輸技術(shù)作為基本通信手段，與有線傳輸技術(shù)相比，具有較低的傳輸帶寬。并且由于多個(gè)節(jié)點(diǎn)分布式競(jìng)爭使用信道，使得每個(gè)移動(dòng)節(jié)點(diǎn)實(shí)際使用的帶寬遠(yuǎn)小于物理層提供的最大傳輸速率。<

28、;/p><p><b>　?。?）信道的單向性</b></p><p>　　自組網(wǎng)的一對(duì)節(jié)點(diǎn)之間可能存在單向通信。也就是說節(jié)點(diǎn)A發(fā)送分組是B能收到，但是B發(fā)送分組是A收不到。那么A與B之間就只存在A到B的單方向鏈路。對(duì)于TDD雙工方式而言，這種情況往往在使用功率控制時(shí)發(fā)生。</p><p><b>　　（9）能量受限</b>&

29、lt;/p><p>　　自組網(wǎng)內(nèi)的移動(dòng)節(jié)點(diǎn)一把米需要依靠電池提供能量，在電池容量沒有大幅提高前，節(jié)省功率將是自組網(wǎng)技術(shù)只一個(gè)需要高度重視的問題。</p><p>　?。?0）有限的安全性</p><p>　　自組網(wǎng)由于采用分布式控制、無中心、臨時(shí)組織等原因，它比一般的無線網(wǎng)絡(luò)更容易受到安全方面的威脅。</p><p>　　2.3 協(xié)議棧　　

30、 </p><p><b>　　2.3.1 引言</b></p><p>　　自組網(wǎng)中的通信大都采用分組傳輸方式：首先要將傳輸?shù)臄?shù)據(jù)打成一個(gè)個(gè)分組，然后一次傳輸。圖2.3給出了一個(gè)分組的結(jié)構(gòu)示意圖。它由兩部分組成：控制部頭（報(bào)頭）和數(shù)據(jù)塊。數(shù)據(jù)部分就是要傳輸?shù)臄?shù)據(jù)，經(jīng)過多跳一直傳輸?shù)侥康墓?jié)點(diǎn)。報(bào)頭部分一般由源地址和目的地址以

31、及其他的控制信息組成，中間節(jié)點(diǎn)和目的節(jié)點(diǎn)間將根據(jù)這些控制信息來處理這個(gè)分組。</p><p><b>　　圖2.3 數(shù)據(jù)分組</b></p><p>　　例如，在圖2.1中，有一系列數(shù)據(jù)分組要從源節(jié)點(diǎn)A傳輸?shù)侥康墓?jié)點(diǎn)E，其中的某一分組如圖2.3所示。A節(jié)點(diǎn)首先利用無線傳輸技術(shù)將這個(gè)分組發(fā)往B節(jié)點(diǎn)，B節(jié)點(diǎn)完整地接收這個(gè)分組并存儲(chǔ)后，按照?qǐng)?bào)頭中的源地址和目的地址信息查找路

32、由表，查找到下一跳為C節(jié)點(diǎn)，然后再將這個(gè)分組利用無線傳輸技術(shù)發(fā)往C節(jié)點(diǎn)。C、D節(jié)點(diǎn)一次對(duì)該分組進(jìn)行存儲(chǔ)轉(zhuǎn)發(fā)，直到E節(jié)點(diǎn)。E節(jié)點(diǎn)依據(jù)報(bào)頭目的地址發(fā)現(xiàn)這個(gè)分組是由A節(jié)點(diǎn)發(fā)給自己的，它就取出其中的數(shù)據(jù)部分，從而完成了一個(gè)分組從A到E的通信過程。</p><p>　　上面節(jié)點(diǎn)中繼轉(zhuǎn)發(fā)過程的描述中，遺留了許多問題。例如：如何時(shí)將數(shù)據(jù)分組包含的比特轉(zhuǎn)化為信號(hào)發(fā)送和接收?如何能夠保證傳輸?shù)男畔⒈忍乜煽?多個(gè)節(jié)點(diǎn)共享信道時(shí)，這些

33、節(jié)點(diǎn)如何分配使用信道?路由表如何生成?如圖2.2中拓?fù)浒l(fā)生變化時(shí)，如何修改路由表（路由表維護(hù)）?這些問題只是完成一次通信所要解決部分問題。事實(shí)上，完成一次通信，涉及的問題很多，問題互相之間又有關(guān)聯(lián)，要全面解決這些問題十分復(fù)雜。目前，在通信網(wǎng)絡(luò)研究與開發(fā)過程中，人們一般采用將協(xié)議分層的方法將通信過程中的所有問題分解到各個(gè)層去分別加以研究與設(shè)計(jì)。對(duì)于自組網(wǎng)，也可以采用圖2.4中所示的OSI七層協(xié)議模型加以分析與設(shè)計(jì)。移動(dòng)自組網(wǎng)關(guān)注的是其中最

34、具特色的兩個(gè)子層：MAC子層和網(wǎng)絡(luò)層。</p><p><b>　　7</b></p><p><b>　　6</b></p><p><b>　　5</b></p><p><b>　　4</b></p><p><b>

35、;　　3</b></p><p><b>　　2</b></p><p><b>　　1</b></p><p>　　圖2.4 OSI七層協(xié)議模型</p><p>　　2.3.2 多個(gè)節(jié)點(diǎn)共享無線資源的控制與仲裁</p><p>　　由于電磁波的傳播特性，無線通

36、信的傳輸媒介（信道）屬于廣播信道類型。當(dāng)一個(gè)節(jié)點(diǎn)發(fā)送無線電信號(hào)時(shí)，鄰近的節(jié)點(diǎn)都將接收到這個(gè)信號(hào)。如果在一個(gè)小的空間范圍內(nèi)，有兩個(gè)或多個(gè)節(jié)點(diǎn)發(fā)送無線電信號(hào)，將會(huì)在它們的接收節(jié)點(diǎn)處產(chǎn)生信號(hào)的相互疊加，造成相互干擾，嚴(yán)重時(shí)將使接收節(jié)點(diǎn)無法正確接收所需要的信息，一般將這種情況稱為發(fā)生了信道使用上的沖突，簡稱沖突。例如圖2.5中，</p><p>　　圖2.5 信道資源共享</p><p>　　節(jié)點(diǎn)

37、A、B、C、D相距很近，并且共享信道資源，當(dāng)A和B同時(shí)發(fā)送，A發(fā)往C，B發(fā)往D，A與B的發(fā)送信號(hào)在節(jié)點(diǎn)C和D處都產(chǎn)生沖突，導(dǎo)致兩者都不能正確接收。</p><p>　　在通信協(xié)議棧中，如何在多個(gè)節(jié)點(diǎn)間分配無線信道資源屬于數(shù)據(jù)鏈路層的媒介接入控制子層（MAC，Media Access Control）要解決的問題。</p><p>　　同一個(gè)信道資源可以被多個(gè)節(jié)點(diǎn)共同使用，需要找到一種資源分

38、配的方法，即MAC協(xié)議，如何使分配后不發(fā)生沖突（沖突造成信道資源浪費(fèi)）?如何分配信道使得信道利用率高（信道被充分利用）?如何分配使得節(jié)點(diǎn)有數(shù)據(jù)時(shí)等待帶的時(shí)間較短（快速使用信道）?這些都是MAC協(xié)議所面臨的問題。</p><p>　　基于移動(dòng)自組網(wǎng)的特點(diǎn)，在蜂窩移動(dòng)通信系統(tǒng)中使用的有中心的信道接入技術(shù)，以及傳統(tǒng)的基于廣播信道接入技術(shù)（例如IEEE 802.3）都無法直接應(yīng)用到移動(dòng)自組網(wǎng)中去，因而需要專門設(shè)計(jì)適用于移

39、動(dòng)自組網(wǎng)的信道接入?yún)f(xié)議。</p><p>　　自組網(wǎng)中MAC協(xié)議設(shè)計(jì)的主要目標(biāo)是：能夠保證信道資源高效率的使用；能夠保證業(yè)務(wù)快速接入信道，特別是高優(yōu)先級(jí)業(yè)務(wù)的快速接入信道。</p><p>　　目前，已經(jīng)有很多自組網(wǎng)MAC協(xié)議被提出，它們大致可以分為兩大類：競(jìng)爭型、非競(jìng)爭型。其中，非競(jìng)爭型一般采用固定分配的方式分配各個(gè)節(jié)點(diǎn)的子信道，由于它是一種低效率的信道分配方式，故在此不做多介紹。本文

40、就一種競(jìng)爭型的信道接入方式作以下介紹。競(jìng)爭方式是自組網(wǎng)MAC協(xié)議的主流。顧名思義，競(jìng)爭方式就是多個(gè)節(jié)點(diǎn)“搶占”使用權(quán)的方式。但是，如何使搶占發(fā)生的沖突少（要避免沖突），發(fā)生沖突后如何避免進(jìn)一步的沖突（要避免不斷的沖突），這都需要認(rèn)真考慮。經(jīng)典的ALOHA協(xié)議主要解決了如何避免不斷沖突的問題，它的基本思想是：如果某個(gè)節(jié)點(diǎn)有數(shù)據(jù)，它就立刻發(fā)送（搶占信道）；如果發(fā)生了沖突（有兩個(gè)以上節(jié)點(diǎn)同時(shí)搶占信道），則發(fā)送失敗，需要重新發(fā)送；重新發(fā)送時(shí)，每

41、個(gè)發(fā)送失敗的節(jié)點(diǎn)應(yīng)當(dāng)各自等待一段隨機(jī)的時(shí)間再發(fā)送。各自等待一段隨機(jī)時(shí)間是ALOHA協(xié)議的關(guān)鍵，這樣就以極大的可能造成不同節(jié)點(diǎn)等待的時(shí)間不同，從而使得等待時(shí)間短的節(jié)點(diǎn)可以先使用信道發(fā)送數(shù)據(jù)，等待時(shí)間長的節(jié)點(diǎn)晚點(diǎn)使用信道發(fā)送數(shù)據(jù)。反之，如果沖突節(jié)點(diǎn)發(fā)現(xiàn)沖突后不等待或者等待固定的時(shí)間，則將會(huì)造成不斷的沖突。針對(duì)ALOHA協(xié)議的效率問題，引進(jìn)了CSMA（Carrier </p><p>　　但是，由于自組網(wǎng)一般是多跳網(wǎng)，

42、當(dāng)將CSMA協(xié)議直接應(yīng)用到自組網(wǎng)時(shí)，將會(huì)遇到隱藏和暴露節(jié)點(diǎn)問題。</p><p>　　圖2.6 隱藏和暴露節(jié)點(diǎn)問題</p><p>　　如圖2.6中，節(jié)點(diǎn)B正向節(jié)點(diǎn)C發(fā)送數(shù)據(jù)，由于節(jié)點(diǎn)A相距B較遠(yuǎn)，所以節(jié)點(diǎn)A沒有“聽到”節(jié)點(diǎn)B發(fā)送的信號(hào)，節(jié)點(diǎn)A就會(huì)認(rèn)為信道空閑。如果這時(shí)節(jié)點(diǎn)A也有數(shù)據(jù)要發(fā)送，它就會(huì)直接發(fā)送，從而造成A和B相互隱藏（聽不到對(duì)方）而造成了這個(gè)問題，這就是所謂的隱藏節(jié)點(diǎn)問題。在節(jié)

43、點(diǎn)B發(fā)送數(shù)據(jù)時(shí)，如果節(jié)點(diǎn)D有數(shù)據(jù)也想要發(fā)送節(jié)點(diǎn)E，由于節(jié)點(diǎn)D聽到了節(jié)點(diǎn)B正在通信，所以節(jié)點(diǎn)D會(huì)認(rèn)為信道被占用，節(jié)點(diǎn)D就被禁止發(fā)送。然而，由于節(jié)點(diǎn)E距節(jié)點(diǎn)B較遠(yuǎn)，節(jié)點(diǎn)D距節(jié)點(diǎn)C也較遠(yuǎn)，所以節(jié)點(diǎn)D發(fā)送數(shù)據(jù)實(shí)際上不會(huì)影響節(jié)點(diǎn)C接收，而正在進(jìn)行的節(jié)點(diǎn)B向C的通信也不會(huì)影響節(jié)點(diǎn)E的接收，因此節(jié)點(diǎn)D完全可以發(fā)送。直觀地講，節(jié)點(diǎn)B“暴露”給D聽到造成了這個(gè)問題，載波偵聽機(jī)制反倒造成了信道使用的浪費(fèi)，這就是所謂的暴露節(jié)點(diǎn)問題。隱藏和暴露節(jié)點(diǎn)問題會(huì)導(dǎo)致信

44、道利用率的降低，因此自組網(wǎng)的許多MAC協(xié)議都研究如何解決隱藏和暴露節(jié)點(diǎn)問題。</p><p>　　除了上述討論的問題，在自組網(wǎng)的MAC協(xié)議設(shè)計(jì)中還面臨許多其他的問題，例如節(jié)能、公平性、QoS保證等。在這里就不多介紹了。</p><p>　　2.4 其他關(guān)鍵技術(shù)</p><p>　　在無線自組網(wǎng)中，存在許多關(guān)鍵技術(shù)問題，主要包括：MAC協(xié)議、路由協(xié)議、自組網(wǎng)中網(wǎng)絡(luò)

45、與信息的安全性、QoS保證框架與技術(shù)、功率控制與管理等。下面對(duì)QoS保證、功率管理與控制、安全問題進(jìn)行簡要介紹。</p><p><b>　　1、QoS保證</b></p><p>　　所謂QoS，就是網(wǎng)絡(luò)為用戶傳送端到端數(shù)據(jù)時(shí)必須滿足的一套可測(cè)量的預(yù)先定義的基于端到端（E2E）性能的服務(wù)屬性，一般包括時(shí)延、時(shí)延抖動(dòng)、可用寬帶和分組丟包率等。</p>&

46、lt;p>　　自組網(wǎng)中支持QoS保證所面臨的問題主要有如下幾點(diǎn)：</p><p>　?。?）鏈路質(zhì)量預(yù)測(cè)的困難：自組網(wǎng)使用無線通信進(jìn)行傳輸，無線信號(hào)傳輸面臨著路徑損耗、多徑衰落和干擾問題，這些問題都與周圍環(huán)境相關(guān)。</p><p>　　（2）鏈路帶寬預(yù)測(cè)的困難：無線媒介屬于廣播媒介，信道帶寬被周圍的節(jié)點(diǎn)共享，周圍節(jié)點(diǎn)的移動(dòng)和這些節(jié)點(diǎn)業(yè)務(wù)量的變化使鏈路帶寬很難預(yù)測(cè)。</p>

47、<p>　?。?）分布式控制：分布式控制機(jī)制對(duì)QoS保證影響很大。由于信道使用權(quán)需要采用分布式方式獲得，這導(dǎo)致優(yōu)先級(jí)的保證和資源的預(yù)留都帶有一定的隨機(jī)性。</p><p>　?。?）網(wǎng)絡(luò)動(dòng)態(tài)性：有三個(gè)方面導(dǎo)致網(wǎng)絡(luò)的動(dòng)態(tài)特性，一是移動(dòng)設(shè)備通常使用電池作為資源，而電池的生命期是有限的，二是節(jié)點(diǎn)的移動(dòng)性，三是網(wǎng)絡(luò)業(yè)務(wù)流的動(dòng)態(tài)與不可預(yù)測(cè)。</p><p>　　網(wǎng)絡(luò)的動(dòng)態(tài)特性及通信介質(zhì)

48、的不可預(yù)測(cè)性使得對(duì)網(wǎng)絡(luò)狀態(tài)信息的獲得和維護(hù)非常困難，也使得自組網(wǎng)中的QoS保證機(jī)制通常工作在不準(zhǔn)確的狀態(tài)信息下。</p><p><b>　　2、功率控制與管理</b></p><p>　　對(duì)于一個(gè)自組網(wǎng)的節(jié)點(diǎn)而言，功率控制與管理包括兩個(gè)方面的內(nèi)容：控制發(fā)送功率的大小和管理節(jié)點(diǎn)的工作狀態(tài)。發(fā)送功率的大小影響節(jié)點(diǎn)的耗能和傳輸距離的遠(yuǎn)近。傳輸距離的遠(yuǎn)近還影響網(wǎng)絡(luò)節(jié)點(diǎn)的連接

49、性，即網(wǎng)絡(luò)拓?fù)??？梢院唵蔚恼J(rèn)為，一個(gè)自組網(wǎng)的節(jié)點(diǎn)具有兩種狀態(tài)：激活狀態(tài)，非激活狀態(tài)。激活狀態(tài)就是節(jié)點(diǎn)正在發(fā)送或接收數(shù)據(jù)；非激活狀態(tài)就是節(jié)點(diǎn)空閑但有可能在偵聽信道的使用狀況，偵聽時(shí)節(jié)點(diǎn)接收機(jī)的部分功能模塊還在工作。</p><p>　　在自組網(wǎng)中，功率控制和管理主要考慮兩個(gè)方面的問題：</p><p>　　（1）降低能耗，盡量延長節(jié)點(diǎn)和網(wǎng)絡(luò)的壽命。</p><p>　

50、?。?）在保證網(wǎng)絡(luò)連通性的條件下，力圖降低發(fā)送功率，使無線資源的空間復(fù)用性增大，最終達(dá)到網(wǎng)絡(luò)累積吞吐量最大的目的。</p><p>　　一個(gè)移動(dòng)節(jié)點(diǎn)消耗的能量可分為與通信相關(guān)的能量消耗和通信無關(guān)的能量消耗這兩類。由于移動(dòng)節(jié)點(diǎn)的電池能量有限，節(jié)能是自組網(wǎng)設(shè)計(jì)的最重要的目標(biāo)之一。一個(gè)節(jié)點(diǎn)的電能的不足不僅會(huì)影響它本身，而且還會(huì)影響它為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)分組，因此會(huì)影響整個(gè)網(wǎng)絡(luò)的壽命。與節(jié)能有關(guān)的研究主要集中在：狀態(tài)控制、MA

51、C層功率控制、功率意識(shí)路由協(xié)議和拓?fù)淇刂啤?lt;/p><p>　　關(guān)于利用功率控制使網(wǎng)絡(luò)吞吐增大技術(shù)的研究，目前尚處于起步階段。現(xiàn)在的研究都是基于一些直觀的觀察，事實(shí)上還存在一些基本理論問題尚待進(jìn)一步澄清。</p><p>　　3、自組網(wǎng)中網(wǎng)絡(luò)與信息的安全</p><p>　　目前，自組網(wǎng)的安全性已經(jīng)成為一大研究熱點(diǎn)。自組網(wǎng)面臨的安全威脅有著它自身的特殊性，與傳統(tǒng)網(wǎng)絡(luò)

52、相比，自組織網(wǎng)本身具有許多系統(tǒng)脆弱性：</p><p>　?。?）無線鏈路：節(jié)點(diǎn)之間的無線鏈路非常容易受到攻擊。</p><p>　　（2）無基礎(chǔ)設(shè)施的分布式網(wǎng)絡(luò)：由于沒有基礎(chǔ)設(shè)施的支持，無法事先對(duì)網(wǎng)絡(luò)做出預(yù)測(cè)，礙于了傳統(tǒng)密鑰管理和身份認(rèn)證等技術(shù)的應(yīng)用，需要采用新的方案來保證網(wǎng)絡(luò)的安全。</p><p>　　（3）動(dòng)態(tài)變化的網(wǎng)絡(luò)：自組網(wǎng)的動(dòng)態(tài)性和臨時(shí)性導(dǎo)致節(jié)點(diǎn)間的信

53、任關(guān)系不斷變化，這給密鑰管理帶來了麻煩。為靜態(tài)配置系統(tǒng)而設(shè)計(jì)的標(biāo)準(zhǔn)安全方案不在適用，需要研究新的安全方案，以適應(yīng)拓?fù)鋭?dòng)態(tài)變化和節(jié)點(diǎn)可移入、移出網(wǎng)絡(luò)等特點(diǎn)。節(jié)點(diǎn)的數(shù)量也是動(dòng)態(tài)變化的，這就要求任何網(wǎng)絡(luò)協(xié)議和安全方案都必須具有良好的可擴(kuò)展性，要能適應(yīng)不同的網(wǎng)絡(luò)規(guī)模。</p><p>　?。?）節(jié)點(diǎn)的特性：節(jié)點(diǎn)可以自由漫游并與鄰近的節(jié)點(diǎn)通信，在加入或離開一個(gè)子網(wǎng)時(shí)無需任何聲明，這樣在大規(guī)模網(wǎng)絡(luò)中，無法為大多數(shù)節(jié)點(diǎn)都建立信

54、任關(guān)系。在這種情況下無法保證兩個(gè)節(jié)點(diǎn)間路徑上經(jīng)過的中間節(jié)點(diǎn)都按協(xié)議操作，不能排除存在想要破壞網(wǎng)路的惡意節(jié)點(diǎn)。節(jié)點(diǎn)的計(jì)算能力也有限，存儲(chǔ)空間也不大，對(duì)復(fù)雜運(yùn)算不堪重負(fù)。</p><p>　　正由于自組織網(wǎng)具有許多系統(tǒng)脆弱性，容易遭受多種攻擊，因此所要求的安全性面臨嚴(yán)重威脅。統(tǒng)的安全機(jī)制不再使用與自組織網(wǎng)：由于缺乏足夠的物理保護(hù)、沒有中心節(jié)點(diǎn)、節(jié)點(diǎn)計(jì)算能力低，使得傳統(tǒng)的加密和認(rèn)證機(jī)制無法實(shí)現(xiàn)，由于拓?fù)浣Y(jié)構(gòu)、成員數(shù)量、

55、信任關(guān)系、網(wǎng)絡(luò)中產(chǎn)生和傳輸?shù)臄?shù)據(jù)都是動(dòng)態(tài)的，傳統(tǒng)的基于數(shù)據(jù)庫、文件系統(tǒng)等靜態(tài)配置的網(wǎng)絡(luò)安全方案不再適用，由于網(wǎng)絡(luò)邊界模糊，傳統(tǒng)的防火墻無從部署。</p><p><b>　　2.5 本章小結(jié)</b></p><p>　　本章在詳細(xì)介紹無線通信和無線移動(dòng)自組織網(wǎng)的基礎(chǔ)知識(shí)的同時(shí)，簡要的對(duì)無線自組織網(wǎng)的特性作了一下介紹，對(duì)于加深無線移動(dòng)網(wǎng)絡(luò)的認(rèn)識(shí)，有很好的幫助，也對(duì)后面

56、的路由技術(shù)有所涉及，將是對(duì)本文的后繼工作的一個(gè)很好的鋪墊。</p><p>　　第3章　移動(dòng)自組網(wǎng)的路由技術(shù)</p><p>　　不管是移動(dòng)自組網(wǎng)，還是有線網(wǎng)絡(luò)，路由都是其關(guān)鍵技術(shù)，因?yàn)槿魏螖?shù)據(jù)的傳輸，信息的交換，都需要有路由（也即路徑）才能完成。在有線網(wǎng)絡(luò)中，路由動(dòng)作包括兩項(xiàng)基本內(nèi)容：尋徑和轉(zhuǎn)發(fā)。尋徑即判定到達(dá)目的地的最佳路徑，由路由選擇算法來實(shí)現(xiàn)。由于涉及到不同的路由選擇協(xié)議和路由選擇

57、算法，要相對(duì)復(fù)雜一些。為了判定最佳路徑，路由選擇算法必須啟動(dòng)并維護(hù)包含路由信息的路由表，其中路由信息依賴于所用的路由選擇算法而不盡相同。路由選擇算法將收集到的不同信息填入路由表中，根據(jù)路由表可將目的網(wǎng)絡(luò)與下一站（nexthop）的關(guān)系告訴路由器。路由器間互通信息進(jìn)行路由更新，更新維護(hù)路由表使之正確反映網(wǎng)絡(luò)的拓?fù)渥兓?，并由路由器根?jù)量度來決定最佳路徑，這就是路由選擇協(xié)議（routing protocol）。轉(zhuǎn)發(fā)即沿尋徑好的最佳路徑傳送信息

58、分組。路由器首先在路由表中查找，判明是否知道如何將分組發(fā)送到下一個(gè)站點(diǎn)（路由器或主機(jī)），如果路由器不知道如何發(fā)送分組，通常將該分組丟棄；否則就根據(jù)路由表的相應(yīng)表項(xiàng)將分組發(fā)送到下一個(gè)站點(diǎn)，如果目的網(wǎng)絡(luò)直接與路由器相連，路由器就把分組直接送到相應(yīng)的端口上，這就是路由轉(zhuǎn)發(fā)協(xié)議（routed protoc</p><p>　　3.1　移動(dòng)自組網(wǎng)路由技術(shù)概述</p><p>　　自組網(wǎng)是由一組具有路

59、由功能的節(jié)點(diǎn)組成的分布式無線多跳網(wǎng)絡(luò)，它不依靠任何預(yù)設(shè)的網(wǎng)絡(luò)基礎(chǔ)設(shè)施。因?yàn)樽越M網(wǎng)中節(jié)點(diǎn)的傳輸范圍有限，源節(jié)點(diǎn)在想目的節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，通常需要其他節(jié)點(diǎn)的輔助，所以路由協(xié)議是自組網(wǎng)中不可或缺的一部分。從功能上講，路由協(xié)議是通信網(wǎng)絡(luò)中的一套將業(yè)務(wù)數(shù)據(jù)從源節(jié)點(diǎn)指引到目的節(jié)點(diǎn)的機(jī)制。路由協(xié)議的主要設(shè)計(jì)目標(biāo)是：滿足應(yīng)用需求的同時(shí)盡量降低網(wǎng)絡(luò)開銷，取得資源利用的整體有效性，擴(kuò)大網(wǎng)絡(luò)吞吐量。其中，應(yīng)用需求一般包括時(shí)延、時(shí)延抖動(dòng)、網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)、節(jié)點(diǎn)密度

60、、端到端的通信頻率（比如呼叫率）和拓?fù)渥兓念l繁程度（節(jié)點(diǎn)移動(dòng)率）等因素有關(guān)。</p><p>　　自組網(wǎng)中的路由協(xié)議主要包括路徑產(chǎn)生（Path Generation）、路徑選擇（Path Selection）和路徑維護(hù)（Path Maintenance）三項(xiàng)核心功能。其中，路徑產(chǎn)生是指根據(jù)集中式或分布式的網(wǎng)絡(luò)狀態(tài)信息和用戶業(yè)務(wù)需求生產(chǎn)路徑，網(wǎng)絡(luò)狀態(tài)信息和用戶業(yè)務(wù)狀態(tài)信息的收集與分發(fā)是該過程的主要內(nèi)容；路徑選擇是

61、指根據(jù)網(wǎng)絡(luò)狀態(tài)信息和用戶業(yè)務(wù)狀態(tài)信息選擇最適當(dāng)?shù)穆窂?，在自組網(wǎng)路由協(xié)議中，路徑產(chǎn)生和路徑維護(hù)這兩項(xiàng)功能通常合在一起成為路由發(fā)現(xiàn)。路徑維護(hù)是指對(duì)所選路徑進(jìn)行維護(hù)。由于自組網(wǎng)是一種沒有預(yù)設(shè)基礎(chǔ)設(shè)施的網(wǎng)絡(luò)，它工作于無線環(huán)境，通信帶寬受限，而且節(jié)點(diǎn)具有移動(dòng)性，因此，路由協(xié)議還必須充分考慮這些因素造成的影響。</p><p>　　綜上所述，自組網(wǎng)的路由協(xié)議設(shè)計(jì)需要綜合考慮用戶業(yè)務(wù)需求、網(wǎng)絡(luò)能力、自組網(wǎng)的特點(diǎn)和運(yùn)行環(huán)境、路由

62、協(xié)議基本功能等諸多因素。</p><p>　　圖3.1 路由協(xié)議的定義和功能</p><p>　　圖3.1給出了路由協(xié)議的示意圖。有鑒于此，為Internet設(shè)計(jì)的許多路由協(xié)議（如RIP、OSPF等）并不能直接適用于自組網(wǎng)，主要原因如下：在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)快速變化的情況下，協(xié)議無法及時(shí)收斂，產(chǎn)生大量的不可靠路由和路由環(huán)路，而且路與開銷過大。為了適應(yīng)自組網(wǎng)的需要，必須設(shè)計(jì)新的路由協(xié)議。路由協(xié)議是

63、自組網(wǎng)研究的一個(gè)熱點(diǎn)。</p><p>　　理想的自組網(wǎng)路由協(xié)議應(yīng)該具有以下特點(diǎn)：</p><p>　　采用分布式路由算法。</p><p>　　具有自適應(yīng)能力，可適應(yīng)快速變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。</p><p><b>　　無環(huán)路。</b></p><p><b>　　控制開銷少。<

64、/b></p><p>　　具有可擴(kuò)展性，適應(yīng)于大規(guī)模網(wǎng)絡(luò)。</p><p>　　自組網(wǎng)是一種無中心的分布式控制網(wǎng)絡(luò)，所以分布式算法更適合于自組網(wǎng)。自組網(wǎng)中，節(jié)點(diǎn)可以以任意速度和任意方式在網(wǎng)中移動(dòng)，加上無線發(fā)送裝置發(fā)送功率的變化、無線信道間的相互干擾以及地形等綜合因素的影響，移動(dòng)終端間通過無線信道形成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)隨時(shí)可能發(fā)生變化，而且變化的方式和速度都是不可預(yù)測(cè)的，所以路由必須具有

65、自適應(yīng)能力，可適應(yīng)快速變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。無環(huán)路是保證路由協(xié)議正確性的一個(gè)基本要求。環(huán)路將導(dǎo)致路由出錯(cuò)，浪費(fèi)大量的寬帶資源，嚴(yán)重影響路由協(xié)議性能。自組網(wǎng)中的帶寬資源十分有限。由于自組網(wǎng)采用無線傳輸技術(shù)作為底層通信手段，考慮無線信道本身的特性，自組網(wǎng)所能提供的網(wǎng)絡(luò)帶寬相對(duì)有線信道要低得多。因此必須控制路由協(xié)議的開銷，提高網(wǎng)絡(luò)的整體性能。自組網(wǎng)的應(yīng)用范圍越來越廣，自組網(wǎng)中的節(jié)點(diǎn)個(gè)數(shù)也在不斷增加。而最初提出的自組網(wǎng)路由協(xié)議一般只支持幾十個(gè)節(jié)點(diǎn)

66、到幾百個(gè)節(jié)點(diǎn)的中小規(guī)模網(wǎng)絡(luò)，所以自組網(wǎng)路由協(xié)議的可擴(kuò)展性問題，成為了一個(gè)研究熱點(diǎn)。</p><p>　　洪泛（Flooding）技術(shù)在自組網(wǎng)路由協(xié)議中具有廣泛的應(yīng)用。在許多路由協(xié)議中，都顯式或隱式地采用了洪泛技術(shù)。甚至，在網(wǎng)絡(luò)動(dòng)態(tài)變化十分劇烈的情況下，路由只能通過洪泛實(shí)現(xiàn)。該技術(shù)不需要已知任何網(wǎng)絡(luò)拓?fù)湫畔?，其工作原理如下：遠(yuǎn)節(jié)點(diǎn)向所有的鄰居節(jié)點(diǎn)廣播分組。中間節(jié)點(diǎn)判斷自己是否是目的節(jié)點(diǎn)，如果不是而且是第一次收到該分

67、組，則繼續(xù)廣播；否則，直接丟棄。不加限制的廣播會(huì)導(dǎo)致分組在全網(wǎng)范圍內(nèi)重傳，所以自組網(wǎng)中路由協(xié)議對(duì)洪泛的改進(jìn)之一是：在分組中加入TTL（Time To Live）域，將分組的傳播限制在一定范圍內(nèi)。洪泛使分組像輻射波一樣從源節(jié)點(diǎn)以波浪形式向外傳播，最終到達(dá)木點(diǎn)節(jié)點(diǎn)（如果目的節(jié)點(diǎn)是可達(dá)的）。采用洪泛方式傳遞分組，具有很大的盲目性，消耗大量的帶寬，但它是將分組擴(kuò)散到整個(gè)網(wǎng)絡(luò)的最健壯和最基本的方法。</p><p>　　3

68、.2　主要關(guān)鍵技術(shù)問題</p><p>　　與有線網(wǎng)絡(luò)相比，自組網(wǎng)具有很多獨(dú)特之處，如網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化、無線傳輸帶寬有限、移動(dòng)節(jié)點(diǎn)的能力有限、需要采用分布式控制方式、安全性差、網(wǎng)絡(luò)的可擴(kuò)展性不強(qiáng)、存在單向無線信道以及生存時(shí)間短等。因此，自組網(wǎng)的路由協(xié)議采用了許多獨(dú)特的技術(shù)方法，用以解決自組網(wǎng)中的關(guān)鍵技術(shù)問題。這些關(guān)鍵技術(shù)問題主要包括以下幾個(gè)方面：路由環(huán)路避免問題、路由協(xié)議的控制開銷問題、路由協(xié)議的可擴(kuò)展性問

69、題、路由協(xié)議對(duì)網(wǎng)絡(luò)動(dòng)態(tài)性的適應(yīng)問題以及路由協(xié)議與其他技術(shù)的結(jié)合問題等。</p><p>　　3.2.1 路由環(huán)路避免問題</p><p>　　按照路由協(xié)議所依據(jù)的基本路由算法不同，自組網(wǎng)路由協(xié)議可分為基于鏈路狀態(tài)的路由協(xié)議、基于距離矢量的路由協(xié)議、源路由協(xié)議和反向鏈路協(xié)議。</p><p>　　在遠(yuǎn)路由協(xié)議中，由于路由信息標(biāo)記在數(shù)據(jù)分組和路由控制分組的頭部，本身具

70、有環(huán)路避免的特性。反向鏈路協(xié)議又包括全鏈路翻轉(zhuǎn)和部分鏈路翻轉(zhuǎn)兩種做法。由于有向無環(huán)圖具有無環(huán)路特性，在網(wǎng)絡(luò)穩(wěn)定的情況下，不會(huì)出現(xiàn)路由問題；鏈路狀態(tài)協(xié)議是在得到全部網(wǎng)絡(luò)拓?fù)湫畔⒌臈l件下進(jìn)行路由計(jì)算的，所以也不會(huì)產(chǎn)生環(huán)路問題。而對(duì)于距離矢量路由協(xié)議，由于控制分組經(jīng)過不同的路徑，在網(wǎng)絡(luò)中的時(shí)延不同，如果采用過期的控制分組進(jìn)行路由計(jì)算，很可能產(chǎn)生環(huán)路。所以在距離矢量路由協(xié)議中，路由環(huán)路問題成為一個(gè)關(guān)鍵性問題。</p><p&

71、gt;　　信息標(biāo)識(shí)技術(shù)是一種解決路由環(huán)路的技術(shù)。在自組網(wǎng)的路由協(xié)議中，每一個(gè)分組可用二元組（源節(jié)點(diǎn)，序列號(hào)）來唯一標(biāo)識(shí)。其中的序列號(hào)是在源節(jié)點(diǎn)中與時(shí)間有關(guān)的唯一值，序列號(hào)越高，分組越新。分組在路由過程中，會(huì)受到網(wǎng)絡(luò)延遲、阻塞和鏈路通斷的影響，因此在到達(dá)目的節(jié)點(diǎn)時(shí)，會(huì)發(fā)生順序顛倒和重復(fù)，而分組標(biāo)識(shí)就是用來保證過濾重復(fù)分組和有序處理分組。信息標(biāo)識(shí)技術(shù)不僅可以應(yīng)用到標(biāo)識(shí)分組，也可標(biāo)識(shí)一個(gè)路由項(xiàng)等。在DSDV（Destination-Seque

72、nced Distance-Vector）和AODV（Ad hoc On demand Distance Vector Routing）協(xié)議中，每個(gè)距離向量都帶有一個(gè)直接序列信息標(biāo)識(shí)，以確定距離向量生成順序，解決路由環(huán)路問題。</p><p>　　3.2.2 控制開銷問題</p><p>　　路由開銷是衡量自組網(wǎng)路由協(xié)議性能的重要指標(biāo)。路由開銷可以用單位時(shí)間內(nèi)控制分組的傳輸量來表示，它是

73、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化率的函數(shù)。自組網(wǎng)路由協(xié)議的設(shè)計(jì)過程就是一個(gè)路由優(yōu)化過程，即在滿足分組傳輸要求的基礎(chǔ)上盡量減少路由開銷，從而提高網(wǎng)絡(luò)的吞吐量。路由協(xié)議設(shè)計(jì)和優(yōu)化的基本思想如下：</p><p>　　減少路由協(xié)議的開銷，從而提高網(wǎng)絡(luò)的有效吞吐量。</p><p>　　提高路由分組的利用效率，從有限的信息中，發(fā)掘更多有價(jià)值的網(wǎng)</p><p><b>　　絡(luò)狀態(tài)

74、信息。</b></p><p>　　采用自適應(yīng)設(shè)計(jì)方法，根據(jù)網(wǎng)絡(luò)狀態(tài)，動(dòng)態(tài)調(diào)整路由協(xié)議及其參數(shù)。</p><p>　　解決路由協(xié)議的控制開銷問題，有以下幾種典型方法。</p><p><b>　　多點(diǎn)中繼技術(shù)</b></p><p>　　多點(diǎn)中繼技術(shù)是一種降低路由協(xié)議控制開銷的技術(shù)。在許多路由協(xié)議中， <

75、;/p><p>　　都顯式或隱式地采用了洪泛技術(shù)。提高洪泛效率，減少洪泛開銷，是優(yōu)化路由協(xié)議的有效途徑。按照網(wǎng)絡(luò)最小生成樹，就必須預(yù)先知道整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，而這在許多情況下是不現(xiàn)實(shí)的。但是，通過局部鏈路狀態(tài)信息交換可獲得局部區(qū)域的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，進(jìn)而可以計(jì)算出局部生成樹。沿著局部生成樹進(jìn)行分組廣播，可以用最小的網(wǎng)絡(luò)開銷將分組傳送到局部區(qū)域的邊界節(jié)點(diǎn)。鏈路狀態(tài)分組不斷地按局部生成樹向外擴(kuò)散，最終擴(kuò)散到全網(wǎng)，其路由開銷要

76、比純洪泛方式小。當(dāng)局部區(qū)域被限制為兩跳時(shí)，該技術(shù)就被稱為“多點(diǎn)中繼（Multipoint Relay）”技術(shù)，OLSR（Optimized Link State Routing Protocol）路由協(xié)議使用了該方法對(duì)鏈路狀態(tài)信息的洪泛進(jìn)行優(yōu)化。</p><p><b>　　2．多范圍技術(shù)</b></p><p>　　多范圍技術(shù)

77、也是一種降低路由協(xié)議控制開銷的技術(shù)。在大規(guī)模自組網(wǎng)中，受傳播時(shí)延和節(jié)點(diǎn)移動(dòng)性的影響，距離節(jié)點(diǎn)越遠(yuǎn)的鏈路狀態(tài)信息準(zhǔn)確性越差，對(duì)路由計(jì)算的意義越小。因此，路由協(xié)議應(yīng)當(dāng)區(qū)別對(duì)待不同距離的鏈路狀態(tài)信息。多范圍的涵義在于：針對(duì)某個(gè)節(jié)點(diǎn)而言，距離自己越遠(yuǎn)的節(jié)點(diǎn)，了解到關(guān)于它的路由信息應(yīng)當(dāng)越模糊；相反，距離自己越近的節(jié)點(diǎn)，了解到的關(guān)于它的路由信息應(yīng)當(dāng)越精確。這樣可以達(dá)到降低路由協(xié)議控制開銷的目的。FSR（Fisheye State Routing，魚

78、眼狀態(tài)路由）協(xié)議通過模仿魚眼“對(duì)距離越近的物體看得越清楚”的生理特性，對(duì)不同距離范圍的鏈路狀態(tài)信息采用不同的更新頻率，在GSR（Global State Routing，全局狀態(tài)路由）協(xié)議的基礎(chǔ)上進(jìn)一步降低了路由協(xié)議的控制開銷。</p><p><b>　　3. 增量消息技術(shù)</b></p><p>　　增量消息技術(shù)是一種常用的降低路由協(xié)議控制開銷的技術(shù)。節(jié)點(diǎn)向鄰居&

79、lt;/p><p>　　節(jié)點(diǎn)報(bào)告拓?fù)湫畔ⅰ⒙酚杀硇畔?、鄰接關(guān)系等信息時(shí)，只報(bào)告對(duì)應(yīng)信息的變化部分，而不是每次都將全部信息報(bào)告給鄰居節(jié)點(diǎn)。這樣，可以減少控制分組的長度，從而降低開銷。這種技術(shù)在DSDV（Destination-Sequenced Distance-Vector）、TBRPF（Topology Broadcast Based On Reverse-Path Forwarding）等路由協(xié)議中得到廣泛應(yīng)用。

80、 </p><p>　　3.2.3 對(duì)網(wǎng)絡(luò)動(dòng)態(tài)性的適應(yīng)問題</p><p>　　網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)性是自組網(wǎng)與固定的Internet的一個(gè)重要區(qū)別。網(wǎng)絡(luò)的高度動(dòng)態(tài)性必將導(dǎo)致路由失效。甚至，在網(wǎng)絡(luò)動(dòng)態(tài)變化十分劇烈的情況下，路由只能通過洪泛來實(shí)現(xiàn)。但是，在網(wǎng)絡(luò)的動(dòng)態(tài)變化不大的情況下，通常有以下3種方法對(duì)失效路由進(jìn)行維護(hù)：備份路由、路由失效節(jié)點(diǎn)通知源節(jié)點(diǎn)重新計(jì)算路由、在路由失效節(jié)點(diǎn)進(jìn)行局部路由恢復(fù)

81、。下面重點(diǎn)介紹局部恢復(fù)技術(shù)。</p><p>　　在Internet路由協(xié)議中，當(dāng)節(jié)點(diǎn)間鏈路發(fā)生變化時(shí)，其設(shè)計(jì)思想是以最快的速度將該變化通知到網(wǎng)絡(luò)中其他節(jié)點(diǎn)，并重新調(diào)整和計(jì)算最短路由。鏈路狀態(tài)變化越快，由此引起的路由開銷就越大。在自組網(wǎng)中，更適合采用局部修復(fù)技術(shù)，將這種變化限制在一個(gè)局部區(qū)域內(nèi)。</p><p>　　不同的路由協(xié)議，所采用的具體技術(shù)也不同。在ABR中，當(dāng)源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路

82、徑發(fā)生中斷時(shí)，整個(gè)路徑并不需要立即重新建立，而是試圖從中斷點(diǎn)開始，查找合適的路徑，修復(fù)斷開的鏈路。在TORA路由協(xié)議中，鏈路的通斷，會(huì)引起局部節(jié)點(diǎn)高度的調(diào)整，從而將變化約束在一個(gè)小的區(qū)域內(nèi)。局部鏈路恢復(fù)技術(shù)實(shí)際上是放棄了對(duì)最優(yōu)路徑的追求，而更關(guān)注在保持路由連通性的前提下，減少路由開銷，縮短路由恢復(fù)時(shí)間。</p><p>　　3.2.4 路由協(xié)議與定位技術(shù)的結(jié)合</p><p>　　目前，

83、存在著一些比較成熟的定位技術(shù)（例如GPS、北斗定位系統(tǒng)等），可以為自組網(wǎng)中的節(jié)點(diǎn)提供地理位置信息。利用地理位置信息可以使自組網(wǎng)的性能得到很大的改善，利用地理位置信息的路由協(xié)議是自組網(wǎng)的一大特色。在自組網(wǎng)中利用位置信息，可以使節(jié)點(diǎn)在尋找路喲時(shí)避免簡單的洪泛；利用相鄰節(jié)點(diǎn)或目的節(jié)點(diǎn)的位置信息，可以提高路由尋找的效率。根據(jù)節(jié)點(diǎn)在發(fā)送數(shù)據(jù)前是否先建立路由，自組網(wǎng)中利用位置信息的路由協(xié)議可分為兩類：位置輔助的路由協(xié)議和基于位置信息的路由協(xié)議。第一

84、類協(xié)議的特點(diǎn)是：節(jié)點(diǎn)在發(fā)送數(shù)據(jù)錢先尋找路由，并保存路由表，數(shù)據(jù)轉(zhuǎn)發(fā)依據(jù)路由表進(jìn)行。地理位置信息的支持可以縮小路由搜索的范圍，進(jìn)而降低路由控制開銷。該類協(xié)議的典型代表是LAP（location-aided-routing）。第二類協(xié)議的特點(diǎn)是：節(jié)點(diǎn)在發(fā)送數(shù)據(jù)前不尋找路由，不保存路由表，數(shù)據(jù)轉(zhuǎn)發(fā)決策直接根據(jù)位置信息（包括自己的、鄰居節(jié)點(diǎn)的、以及目的節(jié)點(diǎn)的位置信息）進(jìn)行。此類協(xié)議包括GPRS、GRA、和GEDIR等。</p>&

85、lt;p>　　3.3　自組網(wǎng)路由協(xié)議分類</p><p>　　依據(jù)不同的標(biāo)準(zhǔn)，自組網(wǎng)的路由協(xié)議有不同的分類方式。按照路由協(xié)議所依據(jù)的基本路由算法的不同，自組網(wǎng)路由協(xié)議可分為基于鏈路的路由協(xié)議、基于距離矢量的路由協(xié)議、源路由協(xié)議和反向鏈路協(xié)議；按照路由建立的方式不同，自組網(wǎng)路由協(xié)議可分為先應(yīng)式路由協(xié)議、按需路由協(xié)議和混合路由協(xié)議；按照路由協(xié)議所依據(jù)的網(wǎng)絡(luò)邏輯結(jié)構(gòu)不同，自組網(wǎng)路由協(xié)議可分為平面結(jié)構(gòu)的路由協(xié)議和分

86、層結(jié)構(gòu)的路由協(xié)議；按照路由協(xié)議所適應(yīng)的網(wǎng)絡(luò)規(guī)模不同，自組網(wǎng)路由協(xié)議可分為中、小規(guī)模路由協(xié)議和大規(guī)模（可擴(kuò)展）路由協(xié)議；按照接收業(yè)務(wù)的目的節(jié)點(diǎn)個(gè)數(shù)不同，自組網(wǎng)路由協(xié)議可分為單播路由協(xié)議和多播路由協(xié)議。另外，自組網(wǎng)中還有一些路由協(xié)議，通過利用地理位置信息來改善路由協(xié)議的性能或直接根據(jù)地理位置信息進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，我們稱它們?yōu)槔玫乩砦恢眯畔⒌穆酚蓞f(xié)議。某些路由協(xié)議具備提供一定程度的QoS保證的能力，我們稱它們?yōu)镼oS路由協(xié)議。還有一些路由協(xié)議，

87、專門設(shè)計(jì)用來節(jié)省網(wǎng)絡(luò)功率消耗，延長網(wǎng)絡(luò)壽命，這一類路由協(xié)議，我們稱之為工率感知路由協(xié)議。</p><p>　　3.3.1　基本路由算法及相應(yīng)路由協(xié)議</p><p>　　距離矢量算法主要是基于Bellman-Ford的簡單最短路徑的分布式路由算法。該算法的基本思想是：節(jié)點(diǎn)維護(hù)一張到網(wǎng)絡(luò)中已知節(jié)點(diǎn)的路由表，每個(gè)表項(xiàng)內(nèi)容包括到已知節(jié)點(diǎn)的最小“距離”和下一跳節(jié)點(diǎn)。節(jié)點(diǎn)周期性的向鄰居節(jié)點(diǎn)廣播它的距

88、離矢量表，同是根據(jù)接收到的鄰居節(jié)點(diǎn)距離矢量廣播，按照最小距離原則更新自己的路由表。距離矢量算法的典型特征是路由選擇的分布性，而且簡單實(shí)用，適用于小型網(wǎng)絡(luò)。距離矢量算法的主要缺點(diǎn)是路由協(xié)議收斂時(shí)間長，可能會(huì)產(chǎn)生暫時(shí)的環(huán)路。自組網(wǎng)中基于距離矢量算法的路由協(xié)議有DSDV等。</p><p>　　在鏈路狀態(tài)算法中，節(jié)點(diǎn)的鏈路狀態(tài)是指節(jié)點(diǎn)與鄰居節(jié)點(diǎn)之間的鏈路狀態(tài)（包括通/段狀態(tài)、帶寬信息和時(shí)延信息等），各節(jié)點(diǎn)的鏈路狀態(tài)總體

89、構(gòu)成了網(wǎng)絡(luò)鏈路狀態(tài)。鏈路狀態(tài)算法分為“鄰居節(jié)點(diǎn)探測(cè)”和“節(jié)點(diǎn)鏈路狀態(tài)全網(wǎng)廣播”兩部分。節(jié)點(diǎn)通過發(fā)送“HELLO”分組來探測(cè)鄰居節(jié)點(diǎn)，以感知節(jié)點(diǎn)鏈路狀態(tài)。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)會(huì)周期性地或在鏈路狀態(tài)發(fā)生改變時(shí)，通過洪泛方式將節(jié)點(diǎn)鏈路狀態(tài)向全網(wǎng)廣播。其他節(jié)點(diǎn)接收到廣播信息，據(jù)此構(gòu)造出網(wǎng)絡(luò)鏈路狀態(tài)表（或者是拓?fù)浔恚跃W(wǎng)絡(luò)管理非常方便。另外，每個(gè)節(jié)點(diǎn)的鏈路狀態(tài)以洪泛方式直接向外傳遞，算法收斂速度快，適合應(yīng)用于大型網(wǎng)絡(luò)。但與距離矢量算法相比，鏈路狀態(tài)

90、算法實(shí)現(xiàn)復(fù)雜，路由開銷大。自組網(wǎng)中基于鏈路狀態(tài)算法的路由協(xié)議有OLSR、WRP、STAR和TBRPF等?！?lt;/p><p>　　源路由算法的實(shí)現(xiàn)是建立在TCP/IP提供的源路由功能基礎(chǔ)之上。在源路由算法中，每個(gè)數(shù)據(jù)分組中添加了從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所經(jīng)過的所有節(jié)點(diǎn)的地址序列，中間節(jié)點(diǎn)并不負(fù)責(zé)路由計(jì)算，而是按照路由序列轉(zhuǎn)發(fā)分組。在源路由協(xié)議中，源路由的建立與維護(hù)由源節(jié)點(diǎn)負(fù)責(zé)。嚴(yán)格的源路由算法可以杜絕路由環(huán)路的存在，減少

91、分組對(duì)中間節(jié)點(diǎn)路由能力的依賴。DSR是自組網(wǎng)中典型的源路由協(xié)議。</p><p>　　反向鏈路算法充分利用了洪泛過程，建立從網(wǎng)絡(luò)各節(jié)點(diǎn)到源節(jié)點(diǎn)的反向路徑，也就是：在洪泛過程中，分組有效傳輸路徑的集合構(gòu)成了一個(gè)從源節(jié)點(diǎn)到網(wǎng)絡(luò)的所有其他節(jié)點(diǎn)的生成樹，生成樹的反向構(gòu)成了一個(gè)從網(wǎng)絡(luò)各節(jié)點(diǎn)到源節(jié)點(diǎn)的有向無環(huán)圖（DAG）。根據(jù)DAG可以構(gòu)造各節(jié)點(diǎn)到源節(jié)點(diǎn)的單向路由。TORA協(xié)議是一種基于反向鏈路算法的路由協(xié)議。</p&

92、gt;<p>　　3.3.2 先應(yīng)式路由協(xié)議和按需路由協(xié)議</p><p>　　先應(yīng)式路由協(xié)議又稱為表驅(qū)動(dòng)路由協(xié)議，在這種路由協(xié)議中，無論是否有通信需求，每個(gè)節(jié)點(diǎn)采用周期性的路由分組廣播，交換路由信息，維護(hù)一張包含到達(dá)其他節(jié)點(diǎn)的路由信息的路由表。當(dāng)檢測(cè)到網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，節(jié)點(diǎn)在網(wǎng)絡(luò)中發(fā)送更新消息。收到更新消息的節(jié)點(diǎn)將更新自己的路由表，以維護(hù)準(zhǔn)確的路由信息。源節(jié)點(diǎn)一旦要發(fā)送分組，可以立即獲得指

93、向目的節(jié)點(diǎn)的路由。</p><p>　　先應(yīng)式路由協(xié)議一般包含鄰居節(jié)點(diǎn)探測(cè)和路由廣播兩個(gè)過程。節(jié)點(diǎn)向各通信端口周期廣播“HELLO”分組，來實(shí)現(xiàn)鄰居節(jié)點(diǎn)探測(cè)。在距離矢量基本算法中，雖然沒有顯式的鄰居節(jié)點(diǎn)探測(cè)過程，但在與鄰居節(jié)點(diǎn)交換距離向量路由表時(shí)，隱含了鄰居節(jié)點(diǎn)探測(cè)。路由廣播通常采用洪泛方式想全網(wǎng)擴(kuò)散。</p><p>　　在帶寬資源有限、拓?fù)浣Y(jié)構(gòu)不斷變化的自組網(wǎng)網(wǎng)絡(luò)環(huán)境中，為節(jié)點(diǎn)維護(hù)到

94、網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)的路由是沒有必要的。快速變化的拓?fù)浣Y(jié)構(gòu)會(huì)使獲得的路由有效時(shí)間縮短，路由信息利用率下降。在有效時(shí)間內(nèi)，只有個(gè)別路由表項(xiàng)被使用。所以節(jié)點(diǎn)沒有必要維護(hù)到網(wǎng)絡(luò)所有其他節(jié)點(diǎn)的路由信息。按需路由協(xié)議根據(jù)網(wǎng)絡(luò)分組的傳輸請(qǐng)求，被動(dòng)地搜索從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由。當(dāng)沒有分組傳遞請(qǐng)求時(shí)，節(jié)點(diǎn)處于靜默狀態(tài)，并不需要交換路由信息。</p><p>　　按需路由協(xié)議主要包括“路由發(fā)現(xiàn)”和“路由維護(hù)”兩個(gè)過程。當(dāng)源節(jié)點(diǎn)需要獲

95、得到目的節(jié)點(diǎn)的路由，而該路由又沒有在路由表中時(shí)，路由發(fā)現(xiàn)過程將被激活。節(jié)點(diǎn)采用洪泛的方式，向整個(gè)網(wǎng)絡(luò)廣播路由請(qǐng)求分組。當(dāng)有路由請(qǐng)求分組到達(dá)目的節(jié)點(diǎn)時(shí)，目的節(jié)點(diǎn)將向源節(jié)點(diǎn)發(fā)出路由請(qǐng)求應(yīng)答分組。這樣，在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立起雙向“激活路徑”。激活路徑建立所需時(shí)間定義為路由建立延遲。隨著拓?fù)浣Y(jié)構(gòu)的變化，當(dāng)激活路徑上的某段鏈路發(fā)生中斷時(shí)，路由維護(hù)過程被啟動(dòng)。路由維護(hù)可以采用兩種不同的策略：從斷點(diǎn)處開始修復(fù)路徑或通知源節(jié)點(diǎn)重新啟動(dòng)路由建立過程

96、。</p><p>　　按需路由協(xié)議是自組網(wǎng)特有的路由協(xié)議類型，它可以降低路由開銷，提高網(wǎng)絡(luò)的吞吐量。但是，按需路由協(xié)議具有潛在的不確定性，包括目的節(jié)點(diǎn)是否可達(dá)的不確定性和路由建立延遲的不確定性。在按需路由協(xié)議中，每條激活路由建立的平均開銷要遠(yuǎn)遠(yuǎn)高于先應(yīng)式路由協(xié)議的平均開銷。在只有少數(shù)節(jié)點(diǎn)之間需要通信的情況下，按需路由協(xié)議的路由開銷才比先應(yīng)式路由協(xié)議的小。</p><p>　　混合型路由協(xié)

97、議是對(duì)先應(yīng)式路由協(xié)議和按需路由協(xié)議的綜合。它在小范圍局部區(qū)域內(nèi)使用先應(yīng)式路由協(xié)議，對(duì)局部區(qū)域外節(jié)點(diǎn)的路由查找采用按需路由協(xié)議。這樣可將鏈路變化限定在局部區(qū)域內(nèi)，從而減少全網(wǎng)廣播帶來的路由開銷?；旌下酚蓞f(xié)議實(shí)現(xiàn)了按需路由協(xié)議和先應(yīng)式路由協(xié)議優(yōu)勢(shì)互補(bǔ)，具有相對(duì)低的帶寬消耗和路由發(fā)現(xiàn)延遲</p><p>　　3.3.3 平面結(jié)構(gòu)路由協(xié)議和分層結(jié)構(gòu)路由協(xié)議</p><p>　　按照路由協(xié)議所依據(jù)

98、的網(wǎng)絡(luò)邏輯結(jié)構(gòu)的不同，自組網(wǎng)路由協(xié)議可分為平面結(jié)構(gòu)和分層結(jié)構(gòu)。平面結(jié)構(gòu)路由協(xié)議是指網(wǎng)絡(luò)中各節(jié)點(diǎn)在路由功能上地位相同，沒有引入分層管理機(jī)制。它的主要優(yōu)點(diǎn)是網(wǎng)絡(luò)中沒有特殊的節(jié)點(diǎn)，網(wǎng)絡(luò)流量均勻地發(fā)散在網(wǎng)絡(luò)中，路由算法易于實(shí)現(xiàn)；其主要缺點(diǎn)是可擴(kuò)展性差，在一定程度上限制了網(wǎng)絡(luò)的規(guī)模。</p><p>　　與平面結(jié)構(gòu)路由協(xié)議相對(duì)應(yīng)的是分層結(jié)構(gòu)路由協(xié)議。分層路由協(xié)議采用群的概念對(duì)移動(dòng)節(jié)點(diǎn)進(jìn)行層次劃分。若干個(gè)在地理空間上相鄰的節(jié)

99、點(diǎn)構(gòu)成一個(gè)群，每個(gè)群有一個(gè)群首。群與群之間通過網(wǎng)關(guān)節(jié)點(diǎn)進(jìn)行通信。網(wǎng)關(guān)節(jié)點(diǎn)可以是群首也可以是其他群成員。網(wǎng)關(guān)節(jié)點(diǎn)之間的鏈接構(gòu)成上層骨干網(wǎng)。所有群之間的通信都通過骨干網(wǎng)轉(zhuǎn)發(fā)。</p><p>　　分層結(jié)構(gòu)路由協(xié)議包括分群算法、群維護(hù)協(xié)議、群內(nèi)路由協(xié)議和群間路由協(xié)議4個(gè)部分。分群算法解決如何在動(dòng)態(tài)分布式網(wǎng)絡(luò)環(huán)境下使移動(dòng)節(jié)點(diǎn)高效地聚集成群，它是分層路由協(xié)議的關(guān)鍵。群維護(hù)協(xié)議主要解決節(jié)點(diǎn)移動(dòng)過程中的群結(jié)構(gòu)維護(hù)問題，包括移動(dòng)

100、節(jié)點(diǎn)退出和加入群、群的產(chǎn)生和消亡等功能。分層結(jié)構(gòu)路由協(xié)議適用于超大型網(wǎng)絡(luò)，但在自組網(wǎng)環(huán)境中，由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的快速變化，其算法實(shí)現(xiàn)非常復(fù)雜。</p><p>　　3.3.4 中、小規(guī)模路由協(xié)議和大規(guī)模（可擴(kuò)展）路由協(xié)議</p><p>　　中、小規(guī)模路由協(xié)議是指適用于中、小規(guī)模自組網(wǎng)（通常是幾十個(gè)節(jié)點(diǎn)）的路由協(xié)議，當(dāng)前在該方面的研究已取得了很大進(jìn)展，陸續(xù)提出了一系列IETF草案，如DSR

101、、AODV、TORA、TBPRF協(xié)議等。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大以及節(jié)點(diǎn)移動(dòng)性的增強(qiáng)，這些路由協(xié)議的開銷都成為一個(gè)非常棘手的問題。同時(shí)，網(wǎng)絡(luò)規(guī)模的擴(kuò)大意味著路由協(xié)議收斂時(shí)間的增長，再加上節(jié)點(diǎn)的可移動(dòng)性，整個(gè)網(wǎng)絡(luò)路由信息的一致性和準(zhǔn)確性很難保證，路由失效和環(huán)路等問題開始出現(xiàn)。因此，適用于大規(guī)模網(wǎng)絡(luò)的路由協(xié)議（可擴(kuò)展路由協(xié)議）成為自組網(wǎng)路由協(xié)議研究的重要內(nèi)容。</p><p>　　3.3.5 單播路由協(xié)議和多播路由協(xié)議&

102、lt;/p><p>　　DSDV、DSR、AODV、FSR協(xié)議等都是支持單播應(yīng)用的自組網(wǎng)路由協(xié)議。將多播技術(shù)的有效性與自組網(wǎng)的特殊優(yōu)勢(shì)相結(jié)合，在自組網(wǎng)環(huán)境下開發(fā)一些基于組的多播應(yīng)用業(yè)務(wù)，具有非常廣闊的前景。因此，支持多播應(yīng)用的自組網(wǎng)多播路由協(xié)議也是當(dāng)前的一個(gè)研究熱點(diǎn)。</p><p>　　3.3.6 其他路由協(xié)議</p><p>　　另外，還可以根據(jù)是否使用地理位置信

103、息、是否提供QoS保證或者是否考慮功率信息，將路由協(xié)議分為利用地理位置信息的路由協(xié)議、QoS路由協(xié)議和功率感知路由協(xié)議。其中，利用地理位置信息的路由協(xié)議又可以分為地理位置輔助路由協(xié)議和基于地理位置的路由協(xié)議。目前提出的自組網(wǎng)QoS路由算法可以分為兩類：對(duì)盡力而為型協(xié)議的改進(jìn)和針對(duì)QoS要求設(shè)計(jì)的路由算法。功率感知路由協(xié)議主要包括兩個(gè)方面的要求：</p><p>　　（1） 盡量保證每個(gè)節(jié)點(diǎn)剩余能量均衡，要求尋找路

104、由盡量選擇剩余能</p><p>　　量多的節(jié)點(diǎn)加入路由（參與中繼轉(zhuǎn)發(fā)），同時(shí)避免使用電量已不足的節(jié)點(diǎn)加入路由。</p><p>　?。?） 尋找一條節(jié)能的路由，要求尋找總體最節(jié)能的路由。</p><p>　　在空閑狀態(tài)下，功率感知路由協(xié)議的基本思想是讓每個(gè)空閑狀態(tài)下的節(jié)點(diǎn)盡量將自己的工作模式調(diào)整到休眠或者關(guān)機(jī)，以此來節(jié)省能耗。然而，這種思想需要很好的路由設(shè)計(jì)，使得

105、當(dāng)許多節(jié)點(diǎn)處于休眠/關(guān)機(jī)狀態(tài)（此時(shí)，無法為其他節(jié)點(diǎn)轉(zhuǎn)發(fā)分組）時(shí)也能保證通信的正常進(jìn)行。</p><p><b>　　3.4　本章小結(jié)</b></p><p>　　移動(dòng)自組網(wǎng)中的路由，是網(wǎng)絡(luò)得以正常運(yùn)行的重要組成部分，也可以說是核心部分，本章對(duì)移動(dòng)自組網(wǎng)的路由技術(shù)作了引論，對(duì)路由技術(shù)的分類，以及分類的標(biāo)準(zhǔn)也作了介紹，這樣可以對(duì)移動(dòng)自組網(wǎng)的路由技術(shù)有個(gè)比較全面的了解，為對(duì)