時間：2022-10-30 11:03:08
序論：寫作是一種深度的自我表達(dá)。它要求我們深入探索自己的思想和情感，挖掘那些隱藏在內(nèi)心深處的真相，好投稿為您帶來了七篇路由協(xié)議范文，愿它們成為您寫作過程中的靈感催化劑，助力您的創(chuàng)作。
關(guān)鍵詞： Ad Hoc網(wǎng)絡(luò)； AODV路由協(xié)議； 修復(fù)； 改進(jìn)
中圖分類號： TN915.04?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2014）05?0055?03
0 引 言
Ad Hoc網(wǎng)絡(luò)作為一種自組織網(wǎng)絡(luò)，其具備節(jié)點可在主機(jī)與路由之間相互切換以及可移動等性能，且其具備的高度動態(tài)拓?fù)浣Y(jié)構(gòu)也對應(yīng)用的路由協(xié)議提出了更多的要求。Ad Hoc網(wǎng)絡(luò)和目前最常用的蜂窩技術(shù)不同，其與傳統(tǒng)蜂窩技術(shù)最主要的區(qū)別在于它自身結(jié)構(gòu)中的移動節(jié)點之間的相互通信和連通是建立在沒有任何基礎(chǔ)網(wǎng)絡(luò)設(shè)施或者路由器的條件下開展或運行傳遞的，且該網(wǎng)絡(luò)系統(tǒng)支持動態(tài)數(shù)據(jù)流控制和動態(tài)配置，運行中使用的所有路由協(xié)議都具備分布式特性。這就是說Ad Hoc網(wǎng)絡(luò)的控制和自組性并不會過度依靠某些相對較為重要的節(jié)點，所有結(jié)構(gòu)中的節(jié)點在功能上和網(wǎng)絡(luò)組成中都是平等的，且任何一節(jié)點因故障或其他原因離開網(wǎng)絡(luò)或加入網(wǎng)絡(luò)都是被允許的。
Ad Hoc網(wǎng)絡(luò)技術(shù)作為最近幾年研究活動最為頻繁的領(lǐng)域之一，其最常使用的路由協(xié)議AODV協(xié)議也成為目前研究的方向之一。下面通過對AODV路由協(xié)議的工作原理和存在的問題進(jìn)行詳細(xì)的描述，重點介紹了關(guān)于該協(xié)議的修復(fù)和改進(jìn)，現(xiàn)闡述如下。
1 AODV路由協(xié)議及其原理
1.1 AODV路由協(xié)議
Ad Hoc網(wǎng)絡(luò)是一種擁有動態(tài)化特性高的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，也具備單向信道的特征，同時也有無線移動終端局限性和有限無線傳輸帶寬等特征，Ad Hoc網(wǎng)絡(luò)的上述特點對路由協(xié)議提出了很高的要求，一般路由協(xié)議難以在該網(wǎng)絡(luò)中工作。
自組按需請求型距離向量協(xié)議簡稱AODV協(xié)議，該協(xié)議是建立在DSDV協(xié)議的條件上，通過借鑒DSR中相關(guān)路由協(xié)議機(jī)制，對上述兩種協(xié)議進(jìn)行改進(jìn)后產(chǎn)生的一種協(xié)議，也就是說AODV協(xié)議糅合了DSDV和DSR兩者的優(yōu)點，如DSDV協(xié)議中設(shè)定的定期廣播、序列號以及逐跳路由，DSR中設(shè)計的路由維護(hù)機(jī)制以及按需路由發(fā)現(xiàn)。這在一定程度使得AODV路由協(xié)議擁有了按需路由協(xié)議所具備的特性及功能。與此同時，在Ad Hoc網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)運行的過程中發(fā)生變化或出現(xiàn)改變時，它會快速收斂，斷路后也可憑借自身功能進(jìn)行自我修復(fù)，保證鏈路暢通，使得節(jié)點能通過建立正向路由到達(dá)目的節(jié)點。在運行的過程中，還具備消耗的儲存資源少，計算量小，網(wǎng)絡(luò)帶寬占用資源少等優(yōu)點。
Ad Hoc網(wǎng)絡(luò)在構(gòu)建移動節(jié)點以及對移動節(jié)點進(jìn)行維護(hù)時，需要借助AODV路由協(xié)議的計算功能，對網(wǎng)絡(luò)結(jié)構(gòu)中各移動節(jié)點之間多跳路由、自啟動以及動態(tài)變化進(jìn)行記錄和計算。操作AODV路由協(xié)議過程中具有一定的開環(huán)性，而在Ad Hoc網(wǎng)絡(luò)結(jié)構(gòu)中拓?fù)涑霈F(xiàn)改變時，即結(jié)構(gòu)中節(jié)點開始在網(wǎng)絡(luò)內(nèi)移動，可以快速收斂，有效地避免了Bellman?Ford“無窮計算”產(chǎn)生問題的影響。若是鏈路出現(xiàn)中斷，該協(xié)議會對相關(guān)受到累及的節(jié)點給予鏈路中斷的信息通知，這就會使累及到的節(jié)點不會因路由中斷而受到影響。
1.2 基本原理
AODV協(xié)議中，若結(jié)構(gòu)中某個源節(jié)點在通向某個節(jié)點時會建立一個路徑，此時就會使得一個路徑發(fā)現(xiàn)程序被發(fā)起，這一時刻廣播路徑會自主向RREQ發(fā)出請求，并安排一個能與之處于對方無線電覆蓋范疇內(nèi)且相鄰的節(jié)點，而該范圍臨近節(jié)點會依據(jù)請求轉(zhuǎn)發(fā)RREQ，一直到源節(jié)點通過建立路由達(dá)到目的節(jié)點或者達(dá)到某個中間節(jié)點，同時這個中間節(jié)點必須具備能夠達(dá)到目的節(jié)點的新的路徑。而在RREQ被上述相鄰節(jié)點轉(zhuǎn)發(fā)的過程中，中間節(jié)點在與之相對性的路由表中會對第一個拷貝RREQ且轉(zhuǎn)發(fā)給其他節(jié)點的相鄰節(jié)點進(jìn)行記錄，這種記錄同時也搭建了一條反向路徑。當(dāng)RREQ達(dá)到中間節(jié)點或者目的節(jié)點后，那么中間節(jié)點就會與目的節(jié)點借助反向路徑單播一個RREP（路徑響應(yīng)分組），再轉(zhuǎn)發(fā)給路徑表上記錄的相鄰節(jié)點。在上述源節(jié)點移動并到目的節(jié)點的整個過程中，路徑上的節(jié)點會依據(jù)路徑表上的記錄搭建一條源節(jié)點正確通向目的節(jié)點的路徑。路由的建立如圖1所示。
路由表項構(gòu)建完成后，路由中任何一個節(jié)點都必須達(dá)到依據(jù)路由維持和管理路由表中各自設(shè)定的目標(biāo)，即任何一個路由表項都在路由表中保持或擁有一個與之對應(yīng)的目的地址，這是為了完成逐條轉(zhuǎn)發(fā)而設(shè)定的。同樣，在對路由表維護(hù)的時間段，與節(jié)點相對應(yīng)項會被從路徑表中被抹除掉，前提是路由沒有被使用。這時，節(jié)點會對下一跳節(jié)點進(jìn)行監(jiān)視，若是在活動路由的過程中發(fā)生了鏈路斷開，這時就會對其他節(jié)點發(fā)出相關(guān)的修復(fù)消息對路由鏈路斷開處進(jìn)行修復(fù)。
2 Ad Hoc路由修復(fù)與改進(jìn)
Ad Hoc網(wǎng)絡(luò)在運行的過程中，節(jié)點的拓?fù)浣Y(jié)構(gòu)在一定程度上具備很強(qiáng)的可移動性，也就是說路由節(jié)點會依據(jù)這種移動特性在網(wǎng)絡(luò)中有目的移動，同時無線自組網(wǎng)絡(luò)中構(gòu)建各個節(jié)點也應(yīng)節(jié)點的移動而成為中繼路由器的替補(bǔ)，而在這一階段鏈路就會因節(jié)點早網(wǎng)絡(luò)中的移動而斷路。因此，對AODV路由協(xié)議運行時因節(jié)點移動而導(dǎo)致路由斷路進(jìn)行修復(fù)對于保證通信的正常進(jìn)行就顯得非常重要。目前，對于斷鏈問題修復(fù)主要有三種處理方法：
（1） 斷路被發(fā)現(xiàn)后，廣播RERREP報文會從路由中斷鏈處的下游節(jié)點處主動發(fā)起，而節(jié)點在收到該報文后就會通過已經(jīng)搭建好的正確通向目的節(jié)點的路徑實現(xiàn)節(jié)點轉(zhuǎn)移，一旦斷鏈上游節(jié)點在收到該報文后，上游節(jié)點也會搭建正確通向目的節(jié)點路徑，這樣就完成了路由的修復(fù)。
（2） 斷鏈時充分發(fā)揮本地修復(fù)功能，并通過上游節(jié)點實現(xiàn)對RREQ報文的傳播控制，在控制范圍內(nèi)完成本地修復(fù)。
（3） 將源修復(fù)與本地修復(fù)相結(jié)合，依據(jù)設(shè)計者對斷鏈做出的實際判斷來選擇使用何種方式進(jìn)行修復(fù)。
2.1 由下游節(jié)點發(fā)廣播報文
當(dāng)在活動路由進(jìn)行的過程中，某條中間鏈路正在使用，因故障原因或者其他出現(xiàn)了斷鏈情況，這時出現(xiàn)斷鏈位置的下游節(jié)點會對路由表進(jìn)行檢查，會明確位于自己上游的節(jié)點屬于哪一條路由，并依據(jù)該節(jié)點到達(dá)的目的節(jié)點發(fā)起一個RERRER廣播消息。任何一個節(jié)點在收到該廣播消息后，都會對自身路由表進(jìn)行檢查，查看是否存在通往該目的節(jié)點的正確路徑及可用路由，若是并不存在與之相關(guān)的路由表項，則會創(chuàng)建并轉(zhuǎn)發(fā)；若是存在與之相關(guān)表項，而目的狀態(tài)無法到達(dá)，則會根據(jù)廣播消息對路由表進(jìn)行更新；若存在能到達(dá)相應(yīng)目標(biāo)的節(jié)點，同時路由信息處于可以占用狀態(tài)，那么該廣播消息會不被理會或丟棄。然而，在廣播消息通過鏈路到達(dá)斷鏈位置的上游節(jié)點處時，就能立即建立正向的路由，完成修復(fù)。
然而，該修復(fù)方法也存在一定的問題。在廣播報文被下游節(jié)點發(fā)起的過程中，路由表除了會對路由中某一下跳節(jié)點進(jìn)行保存或記錄時，還對上一跳點相關(guān)信息進(jìn)行保存，這與AODV協(xié)議中到達(dá)目的節(jié)點的思想存在一定的沖突性。同時，下游節(jié)點發(fā)起對斷鏈的修復(fù)過程中，它們都會對上一節(jié)點信息進(jìn)行緩存，下游節(jié)點是不可預(yù)見的；因此，下游節(jié)點發(fā)起對斷鏈處路由的修復(fù)是沒有區(qū)別性的，也就是即使不存在數(shù)據(jù)傳輸，不存在該條路由，修復(fù)還是會被發(fā)起，這使得廣播報文的傳播量大大增加，加大了無線信道的負(fù)荷。
2.2 本地修復(fù)與源修復(fù)
AODV在運行的過程中，若是發(fā)現(xiàn)斷路，傳統(tǒng)的修復(fù)方法為源節(jié)點修復(fù)法，這就是說RERR會被傳遞到源節(jié)點處，并通知其路由出現(xiàn)斷鏈時，而這時源節(jié)點會重新對路由進(jìn)行發(fā)現(xiàn)，進(jìn)而完成修復(fù)。這種修復(fù)方法比較可靠，但修復(fù)延時較長，因此對AODV提出了本地修復(fù)法：由于節(jié)點在網(wǎng)絡(luò)中的移動而導(dǎo)致斷鏈，而導(dǎo)致斷鏈的節(jié)點極有可能就在斷鏈處的附近或周邊，借助這種方式對斷鏈上游位置節(jié)點的TTL（生存時間）相對較小的RREQ廣播報文來對斷鏈的路由進(jìn)行修復(fù)。然而，本地修復(fù)法受到路由使用效率的限制，特別適用于網(wǎng)絡(luò)運行時，節(jié)點不會出現(xiàn)范圍移動的可能情形中。使用OPNET軟件對上述兩種修復(fù)方法的仿真結(jié)果圖如圖2，圖3所示。
本地小范圍修復(fù)同樣存在問題，若是位于斷鏈處上游位置的相關(guān)節(jié)點周邊臨近節(jié)點較少，那么尋找下兩跳節(jié)點而發(fā)起修復(fù)必將失敗，這時上游節(jié)點也不可能尋到合適的總計節(jié)點，那么在此發(fā)起本地小范圍修復(fù)，也必然會是失敗。也就是說，由同樣一個節(jié)點引發(fā)的兩次尋找修復(fù)，都會因為周邊臨近節(jié)點不足且沒有合適的中繼節(jié)點而出現(xiàn)修復(fù)失敗的問題，這樣會轉(zhuǎn)而尋求源節(jié)點修復(fù)，而在整個過程中會使得端到端延時、路由開銷以及丟包率增加。
2.3 路由斷鏈修復(fù)方法的改進(jìn)
對上面描述進(jìn)行分析，可以知道不同的修復(fù)方法其優(yōu)勢不相同，所面臨的缺陷也具有差異性，因此，在斷鏈發(fā)生時最好配合使用各種修復(fù)方法，這便于提升修復(fù)性能。目前，對上述修復(fù)方法的改進(jìn)主要如下：
（1） 當(dāng)某條路由出現(xiàn)斷鏈且被某中間節(jié)點發(fā)現(xiàn)時，在斷鏈上游節(jié)點發(fā)現(xiàn)后，可以發(fā)出具有限制跳數(shù)作用的Local RREQ，這樣可以將路由重建或者斷鏈修復(fù)的整個過程限制在因拓?fù)涓淖児?jié)點移動周邊范圍。若是在一段時間未能獲取RREP，可以通過上游節(jié)點向上發(fā)出Route Notfication，并對上一節(jié)點進(jìn)行要求，發(fā)起RREQ；若是整個向上過程直至源節(jié)點和目的節(jié)點的中點都未能獲取RREP或路由重建不成功時，應(yīng)該停止繼續(xù)在該節(jié)點繼續(xù)發(fā)送RREQ，而是通知源節(jié)點重新建立一條通向目的節(jié)點的路徑，實現(xiàn)路由的重建。
（2） 鏈路中斷后，首先對鏈路中斷位置的上一處節(jié)點位于的位置進(jìn)行判斷，在根據(jù)其特點采取相應(yīng)的修復(fù)方法。若是該節(jié)點位置距離源節(jié)點相對較近，則選擇源節(jié)點修復(fù)；若是距離目的節(jié)點相對較近，則選擇本地修復(fù)。判斷方法：當(dāng)某條活動路由出現(xiàn)斷鏈的情況后，假定路由表中中斷位置的上一個節(jié)點有效的反向路由與之相對應(yīng)的跳數(shù)為hopl，而在程序錄入中的代碼“DestinationIP address”有效的路由表項與之相對應(yīng)的跳數(shù)為hopl2，若是（hopl+hopl2）/2≥hopl，這表明斷鏈路由位置的上一節(jié)點到目的節(jié)點的距離遠(yuǎn)于到源節(jié)點的距離，這時就應(yīng)采取源節(jié)點修復(fù)，這便于源節(jié)點重建新的到達(dá)目的節(jié)點的路徑，有效地避免了因重建路由而產(chǎn)生的引入時延，且相對本地修復(fù)法節(jié)省了因需要重建路由而開銷的費用。若是hopl>（hopl+hopl2）/2，那么則相反，應(yīng)選取本地修復(fù)，這有助于減少時延。
3 結(jié) 語
Ad Hoc網(wǎng)絡(luò)是一種具備無線移動、自組織的網(wǎng)絡(luò)，該網(wǎng)絡(luò)結(jié)構(gòu)并不需要在某種特定的結(jié)構(gòu)環(huán)境下工作，其工作環(huán)境是可多變化的。因此，Ad Hoc網(wǎng)絡(luò)非常適用于一些特殊場合或軍事場合。在缺乏相關(guān)基礎(chǔ)網(wǎng)絡(luò)設(shè)施構(gòu)建網(wǎng)絡(luò)環(huán)境的條件下，Ad Hoc網(wǎng)絡(luò)通過憑借自身具備的特性及功能完成快速組網(wǎng)，而且構(gòu)建組網(wǎng)結(jié)構(gòu)中任何一個節(jié)點都具備可移動的特性，這就是說每個節(jié)點除了可以作為主機(jī)外，還具備路由器的功能，而這種優(yōu)秀特性也使該網(wǎng)絡(luò)具備非常廣的應(yīng)用前景。而AODV路由協(xié)議作為Ad Hoc網(wǎng)絡(luò)最常使用的路由協(xié)議，其重要性不言而喻，因此，開展相關(guān)AODV路由協(xié)議的修復(fù)研究和改進(jìn)是非常有意義的，這對于提升路由協(xié)議的高效工作有著極為明顯的促進(jìn)作用。
參考文獻(xiàn)
[1] 胡曦，李喆，劉軍.移動Ad Hoc網(wǎng)絡(luò)中基于鏈路穩(wěn)定性預(yù)測的按需路由協(xié)議[J].電子與信息學(xué)報，2010（2）：284?289.
[2] 葉亮，沙學(xué)軍，徐玉.Ad Hoc網(wǎng)絡(luò)路由抖動與路由維護(hù)[J].吉林大學(xué)學(xué)報：工學(xué)版，2010（5）：1397?1403.
[3] 王琦進(jìn)，侯.一種節(jié)點低能量避免的AODV改進(jìn)協(xié)議[J].合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2013（4）：431?434.
[4] 周杰.基于AODV的Ad Hoc網(wǎng)絡(luò)多路徑路由協(xié)議[J].長春工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2012（4）：451?455.
[5] 謝佳，徐山峰.AODV、AOMDV和AODV?UU路由協(xié)議性能仿真與分析[J].中國電子科學(xué)研究院學(xué)報，2011（6）：592?594.
[6] 王莎莎，朱國暉，王鑫.Ad Hoc網(wǎng)絡(luò)負(fù)載均衡路由協(xié)議研究[J].現(xiàn)代電子技術(shù)，2013，36（3）：40?42.
關(guān)鍵詞： 路由協(xié)議；RIP協(xié)議；路由環(huán)路；配置
中圖分類號：TP39 文獻(xiàn)標(biāo)識碼：A 文章編號：1671－7597（2012）0720016-02
1 RIP協(xié)議概述
動態(tài)路由協(xié)議有距離向量路由協(xié)議和鏈路狀態(tài)路由協(xié)議兩種，RIP（Routing Information Protocol，路由信息協(xié)議）就是最典型的距離向量路由協(xié)議，它被廣泛應(yīng)用于小型的同類網(wǎng)絡(luò)。
RIP是由Xerox在20世紀(jì)70年代開發(fā)的，最初定義在RFC1058中。RIP用兩種數(shù)據(jù)包進(jìn)行傳輸更新：更新和請求，每個有RIP功能的路由器在默認(rèn)的情況下，每間隔30秒利用UDP 520端口向與它直連的網(wǎng)絡(luò)鄰居廣播（RIPv1）或者組播（RIPv2）路由更新。
RIP協(xié)議分為版本1和版本2，但不論版本1還是版本2，它們都具備下面的特征：
1）都是距離向量路由協(xié)議；
2）使用跳數(shù)（Hop Count）作為度量值；
3）默認(rèn)路由更新周期為30秒時間；
4）管理距離（AD）為120；
5）支持觸發(fā)更新；
6）最大跳數(shù)為15跳；
7）支持等價路徑，默認(rèn)4條，最大16條；
8）使用UDP 520端口進(jìn)行路由更新。
RIPv1和RIPv2的主要差異如下：
表1 RIPv1和RIPv2的區(qū)別
2 RIP協(xié)議的工作原理
2.1 RIP路由表
RIP協(xié)議路由表中包含了一系列的信息：目的地的地址；到目的地路徑的下一跳及距離計算值，距離是指到達(dá)目的地的網(wǎng)絡(luò)所要經(jīng)過路由器的個數(shù)；除了這些最主要的信息外，路由表還包括了其他的一些信息：比如時鐘（計時器）、狀態(tài)信息（標(biāo)志位）。下面就是一個典型的RIP路由表：
表2 RIP路由表
2.2 RIP工作原理
RIP協(xié)議的整個運行都是與RIP路由表密切相關(guān)的，簡單來說其工作原理就是路由器之間進(jìn)行RIP路由表的交換的過程。
1）RIP路由表的更新維護(hù)
路由器每30秒通過UDP報文發(fā)送路由交換信息，以此確定鄰居是否存在。如果180秒內(nèi)未收到相鄰節(jié)點的路由信息反饋，則標(biāo)識該條路徑不可達(dá)；再經(jīng)過120秒還是未收到路由信息反饋，就刪除這條路由。一旦網(wǎng)絡(luò)發(fā)送變換，路由器就必須更新RIP路由表，這個過程可以稱之為收斂（Convergence），RIP協(xié)議要確定一條路徑是否可達(dá)需要3分鐘，所以整個收斂過程是比較慢的。
路由表是存放在路由器的內(nèi)存中，路由器啟動后會初始化路由表，對每個直連網(wǎng)絡(luò)生成一條路由信息，然后復(fù)制相鄰路由器上的路由表，每復(fù)制一次“跳數(shù)”就加1，并且把下一跳地址指向該路由器。例如達(dá)到某個網(wǎng)絡(luò)下一跳地址是指向R1，可是R1上沒有到達(dá)該網(wǎng)絡(luò)的路由信息，則刪除該條路由。“跳數(shù)”是直到達(dá)目的網(wǎng)絡(luò)所必須經(jīng)過路由器的個數(shù)，直連網(wǎng)絡(luò)的跳數(shù)為0，優(yōu)先級也是最高。
2）路由環(huán)路
由于RIP是距離向量路由協(xié)議，因而也就有了該類協(xié)議的弱點：可能會產(chǎn)生路由環(huán)路。一般來說，產(chǎn)生路由環(huán)路常見原因有二：一是有可能靜態(tài)路由的設(shè)置不合理，二是動態(tài)路由的定時廣播產(chǎn)生了誤會。
情況一，靜態(tài)路由設(shè)置不合理：假設(shè)有兩個路由器R1和R2，它們的路由表中都有一條到達(dá)同一目標(biāo)網(wǎng)絡(luò)的靜態(tài)路由信息，并且下一跳地址彼此指向?qū)Ψ剑@樣就產(chǎn)生了環(huán)路。
情況二，動態(tài)路由產(chǎn)生的：假設(shè)路由器R1有條通過路由器R2到達(dá)網(wǎng)絡(luò)A的路由信息，但是由于網(wǎng)絡(luò)變化，路由器R2到網(wǎng)絡(luò)A不可達(dá)，并且路由器R2的路由廣播先于路由器R1。由于路由器R1路由表中有到達(dá)網(wǎng)絡(luò)A的路由，且下一跳地址就是R2，所以路由器R2就會學(xué)習(xí)到路由器R1的這條路由信息，并且將下一跳的地址設(shè)置為R1，如此一來，路由器R1和R2都把下一跳地址彼此指向?qū)Ψ搅耍瑥亩纬森h(huán)路。
3）環(huán)路的解決
由于環(huán)路的產(chǎn)生，不利用網(wǎng)絡(luò)的正常高效運行，所以針對此種情況有如下解決方法：
① 設(shè)置最大跳數(shù)：RIP協(xié)議規(guī)定了最大跳數(shù)為16，跳數(shù)達(dá)到16就標(biāo)識該條路由不通，并且會阻止環(huán)跳繼續(xù)進(jìn)行，如上文中描述的環(huán)路產(chǎn)生情況二，就可以通過這種方法來解決環(huán)路的產(chǎn)生。
② 水平分割：水平分割就是把路由信息中發(fā)送給原發(fā)者的信息過濾掉，路由信息采用單向發(fā)送。
③ 毒性反轉(zhuǎn)：毒性反轉(zhuǎn)是水平分割的改進(jìn)版本，如果路由器收到的路由信息是自己原來發(fā)送的信息，就馬上將此路由信息的跳數(shù)設(shè)置為16，這個過程稱之為毒化。
④ 觸發(fā)方式：這種方法主要是避免網(wǎng)絡(luò)收斂速度慢而形成環(huán)路，只要網(wǎng)絡(luò)發(fā)生了變化，路由器馬上發(fā)送更新路由信息，迅速通知相鄰的路由器，避免信息誤傳。
⑤ 抑制時間：這是指路由器在收到路由變化信息時，馬上開啟抑制時間，在這段時間內(nèi)，有變化的項目被凍結(jié)，用以防止信息被錯誤覆蓋。
3 RIP協(xié)議的優(yōu)缺點
RIP協(xié)議最大的優(yōu)點就是實現(xiàn)起來簡單，開銷比較小，很適合小型網(wǎng)絡(luò)，但其也存在一些缺陷：
1）當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時，需要比較長的時間才能將此消息傳遞到所有的路由器上，通俗的說就是壞消息傳播的慢。
2）由于RIP協(xié)議規(guī)定最大的“跳數(shù)”是15，也就是路由器個數(shù)，因此限制了網(wǎng)絡(luò)規(guī)模。
3）路由器彼此之間交換的信息是路由器上的完整路由表，隨著網(wǎng)絡(luò)的不斷擴(kuò)大，所花費的開銷也隨之增加。
4 RIP配置簡述
實驗拓?fù)鋱D如下，以思科路由器為例。
圖1 RIP基本配置
4.1 實驗步驟
關(guān)鍵字： 路由算法； 協(xié)議仿真； MANET； NS?3
中圖分類號： TN711?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2013）08?0055?04
0 引 言
隨著網(wǎng)絡(luò)技術(shù)和通信技術(shù)的蓬勃發(fā)展，如何在硬件條件不具備的情況下研究大規(guī)模網(wǎng)絡(luò)，如何快速設(shè)計、實現(xiàn)、分析新的協(xié)議和算法，如何比較新老系統(tǒng)和算法而不必花費巨資建立實際系統(tǒng)等問題日益成為網(wǎng)絡(luò)研究者關(guān)注的焦點。近年來，盛行的方式是通過計算機(jī)軟件對網(wǎng)絡(luò)協(xié)議、網(wǎng)絡(luò)拓?fù)洹⒕W(wǎng)絡(luò)性能進(jìn)行模擬分析。采用這種網(wǎng)絡(luò)仿真的研究方法，降低了成本，研究方法靈活可靠，提高了研究效率。現(xiàn)在主流的網(wǎng)絡(luò)仿真工具[1]主要有：OPNET，QualNet，NS?2。OPNET是商業(yè)軟件，軟件所提供的模型庫比較有限，而且主要集中于路由仿真。QualNet也是一款商業(yè)軟件，弱化了網(wǎng)絡(luò)分層的概念。NS?2的內(nèi)容比較龐雜，各模塊間的協(xié)同及耦合不便于系統(tǒng)擴(kuò)展。為此，在廣泛汲取現(xiàn)有網(wǎng)絡(luò)模擬器的成功經(jīng)驗基礎(chǔ)上，美國華盛頓大學(xué)Thmos R. Henderson教授及其小組研發(fā)了一款極具特色的新型網(wǎng)絡(luò)仿真器――NS?3。相比其他網(wǎng)絡(luò)仿真工具，NS?3是一款開源軟件，在多網(wǎng)卡處理和IP尋址策略方面表現(xiàn)出更好特性，同時，NS?3的架構(gòu)也相對更明了清晰，代碼不需做很大修改就可直接移植到真實網(wǎng)絡(luò)節(jié)點上，此外，研究者可根據(jù)自身需求進(jìn)行任意拓展[2?3]。
1 MANET路由協(xié)議分析
移動無線自組織網(wǎng)絡(luò)（MANET）是一種無中心、自組織的分布式多跳網(wǎng)絡(luò)，MANET以其固有特點在某些特殊場景（如：救災(zāi)、戰(zhàn)爭等）中得到了廣泛運用。路由協(xié)議的好壞直接影響到整個網(wǎng)絡(luò)性能的優(yōu)劣。這里簡要介紹MANET中應(yīng)用比較廣泛的3種平面路由協(xié)議[4]。DSDV（Destination?Sequenced Distance Vector）是一種表驅(qū)動路由協(xié)議，它是在傳統(tǒng)的距離矢量DV算法基礎(chǔ)上改進(jìn)設(shè)計的，同時也被稱為消除環(huán)路的Bellman?Ford路由算法[5]。DSDV算法中每個節(jié)點都維護(hù)一張到達(dá)全網(wǎng)可達(dá)目的節(jié)點的路由表。相比DV算法，DSDV最大的區(qū)別是路由中增加了目的系列號（Sequence Number）字段，通過序列號來區(qū)別新舊路由信息。節(jié)點將收到新路由信息和當(dāng)前路由信息比較，選擇序列號較大的路由記錄來更新路由表。若兩者序列號相同，則選擇跳數(shù)較小者。此外，全網(wǎng)節(jié)點要求周期性廣播路由包來進(jìn)行路由維護(hù)。AODV（Ad Hoc On?Demand Distance Vector）是一種源驅(qū)動的路由協(xié)議[5]，是DSR[6]協(xié)議結(jié)合了DSDV中的按需路由機(jī)制設(shè)計出來的。節(jié)點在發(fā)送數(shù)據(jù)包時，首先查找自己路由表是否有到達(dá)目的節(jié)點的路由信息，若有，則直接按照路由信息發(fā)送；若沒有，則執(zhí)行路由發(fā)現(xiàn)過程。節(jié)點廣播路由請求包RREQ給自己鄰居，鄰居收到RREQ包后查詢自己路由表是否有到達(dá)目的節(jié)點路由信息，若有或本身就是目的節(jié)點，則將路由信息添加到路由應(yīng)答包RREP，并將其反饋給源節(jié)點；若沒有，再將RREQ轉(zhuǎn)發(fā)給自己所有的鄰居。依次類推，直到到達(dá)目的節(jié)點或中間節(jié)點存在到達(dá)目的節(jié)點的路由。AODV協(xié)議通過定期廣播Hello分組來進(jìn)行路由維護(hù)，一旦發(fā)現(xiàn)了某條通信鏈路斷開，節(jié)點就會在DELETE_PERIOD時間之后從路由表中刪除包含該斷開鏈路的路由，并發(fā)送ERROR（路由錯誤）報文來通知那些因為鏈路斷開而不可達(dá)的節(jié)點刪除相應(yīng)的路由記錄或者對已經(jīng)存儲的路由信息進(jìn)行修復(fù)更新。
OLSR（Optimized Link State Routing）是一種優(yōu)化的鏈路狀態(tài)路由協(xié)議，類似其他表驅(qū)動路由協(xié)議，節(jié)點需要周期互網(wǎng)絡(luò)路由信息[7]。被鄰居節(jié)點選作中繼節(jié)點（Multi Point Telay，MPR）的節(jié)點周期性向網(wǎng)絡(luò)廣播控制信息分組，分組中包括將它選作MPR的那些節(jié)點的信息，以告訴網(wǎng)絡(luò)中其他節(jié)點與這些節(jié)點之間相連。而且，只有MPR節(jié)點才能夠作為路由節(jié)點，其他非MPR節(jié)點不參與路由計算，也不需轉(zhuǎn)播控制信息。OLSR協(xié)議中主要通過HELLO和TC（Topological Control）兩種控制消息來感知廣播拓?fù)洹Ｍㄟ^HELLO消息實現(xiàn)鏈路偵測、鄰居偵聽，以此建立節(jié)點的本地鏈路信息表，同時用于向鄰居節(jié)點通告本節(jié)點的多點中繼MPR節(jié)點的選擇；TC消息負(fù)責(zé)執(zhí)行MPR Selector鏈路狀態(tài)聲明，使得每個節(jié)點都能夠感知全網(wǎng)拓?fù)浣Y(jié)構(gòu)。最終，節(jié)點根據(jù)本地鏈路信息庫和拓?fù)浼现械男畔ⅲ捎肈ijkstra算法根據(jù)路徑最短的原則計算路由表。
2 NS?3仿真平臺搭建
2.1 NS?3仿真架構(gòu)
NS?3是一款離散型模擬器，NS?3的網(wǎng)絡(luò)架構(gòu)主要由模擬器內(nèi)核和網(wǎng)絡(luò)構(gòu)件2部分組成，如圖1所示。其中模擬器內(nèi)核包括時間調(diào)度器和網(wǎng)絡(luò)模擬支持系統(tǒng)，是NS?3最核心的部分。相比NS?2，NS?3仿真時間不僅支持Default Scheduler，而且還支持Realtime Scheduler。NS?3的網(wǎng)絡(luò)模擬支持系統(tǒng)包括：Attribute系統(tǒng)、Logging系統(tǒng)和Tracing系統(tǒng)。由于廣泛汲取了其他網(wǎng)絡(luò)仿真工具的經(jīng)驗和技術(shù)，NS?3的內(nèi)核在可量測性、可擴(kuò)展性、模塊化、支持仿真與現(xiàn)實融合等方面具有極大優(yōu)勢[8]。NS?3的網(wǎng)絡(luò)構(gòu)件包括：節(jié)點（Node）、應(yīng)用（Application）、協(xié)議棧（Protocol Stack）、網(wǎng)絡(luò)設(shè)備（Net Device）、信道（Channel）、拓?fù)渖善鳎℉elper）等。網(wǎng)絡(luò)構(gòu)件是對真實網(wǎng)絡(luò)的各個部分的抽象，具有低耦合高內(nèi)聚特點，NS?3通過低層次的抽象，使得仿真效果盡可能反映真實網(wǎng)絡(luò)的性能。
2.2 NS?3仿真流程
以下簡單介紹NS?3代碼編寫的特點及如何在NS?3中搭建一個完整仿真場景的過程。NS?3運行在Linux環(huán)境下，對Linux系統(tǒng)版本有要求且依賴較多系統(tǒng)組件，安裝過程較復(fù)雜。NS?3仿真器代碼核心部分全部使用C++語言編寫，外部配置、編譯、執(zhí)行使用了基于Python的waf系統(tǒng)，方便使用者配置仿真場景。NS?3完全模擬了TCP/IP的協(xié)議棧，并且把每一層的功能模塊化，在NS?3安裝完成后，默認(rèn)只是生成各個功能模塊，自帶的仿真例子沒有生成，需要把這些例子復(fù)制到scrach文件夾下才能運行，并且NS?3中編寫好的代碼也都需要放到該文件夾下才能運行。在NS?3中搭建仿真場景遵循固定的流程，在編寫C++代碼時一般可以分為以下幾個步驟：
（1）設(shè)置仿真場景的全局參數(shù)。比如采用Seed?Manager：：SetSeed（7）設(shè)置隨機(jī)數(shù)種子，以保證產(chǎn)生相同的隨機(jī)序列，設(shè)置隨機(jī)平面移動模型（RandomWalk2dMobilityModel）的參數(shù)Config：：SetDefault（"NS?3：：RandomWalk?2dMobilityModel：：Mode"， StringValue （"Tim?e"））等，以上的全局設(shè)定使得仿真場景可以重現(xiàn)。
（2）定義仿真中使用的參數(shù)，比如數(shù)據(jù)包的大小，需要創(chuàng)建的節(jié)點個數(shù)，物理層使用的傳輸速率等，這些參數(shù)可以使用CommandLine類來實現(xiàn)并解析，方便在仿真過程中使用外部腳本動態(tài)改變這些參數(shù)。
（3）創(chuàng)建網(wǎng)絡(luò)節(jié)點，然后按照TCP/IP協(xié)議，從下而上給網(wǎng)絡(luò)節(jié)點安裝協(xié)議棧。NS?3在實現(xiàn)中考慮到為了方便使用者，協(xié)議棧的每一層都實現(xiàn)了幫助類（XXXHelper），使用者可以方便地使用這些幫助類設(shè)定每一層參數(shù)。比如使用YansWifiPhyHelper設(shè)定物理層協(xié)議，使用YansWifiChannelHelper來設(shè)置傳輸信道類型，使用NqosWifiMacHelper來設(shè)置數(shù)據(jù)鏈路層協(xié)議等。最后通過幫助類給節(jié)點安裝路由協(xié)議，分配IP地址，至此便搭建了TCP/IP的物理層、數(shù)據(jù)鏈路層和網(wǎng)絡(luò)層，實現(xiàn)網(wǎng)絡(luò)的通信功能。
（4）通信網(wǎng)絡(luò)搭建好后，需要編寫實驗程序，即在節(jié)點之間的收發(fā)數(shù)據(jù)包的代碼，以達(dá)到測試底層協(xié)議的目的。NS?3中為了減少使用者的編程工作量，同樣提供了豐富易用的函數(shù)，一般都是先創(chuàng)建使用UDP協(xié)議套（Socket），同時把接收節(jié)點號、發(fā)送節(jié)點號作為參數(shù)傳入，再給套接字指定IP地址，端口號，最后讓發(fā)送節(jié)點連接到接收節(jié)點、為接收節(jié)點指定回調(diào)函數(shù)。
（5）完成節(jié)點之間如何發(fā)送數(shù)據(jù)包的代碼后，需要編寫接收節(jié)點的回調(diào)函數(shù)，即在接收節(jié)點收到數(shù)據(jù)包后調(diào)用的函數(shù)。可以在回調(diào)函數(shù)中對數(shù)據(jù)包的時延，投遞率進(jìn)行統(tǒng)計。
（6）使用Simulator：：Schedule函數(shù)設(shè)定調(diào)度事件即設(shè)定源節(jié)點的發(fā)送數(shù)據(jù)的開始時間，發(fā)送間隔，發(fā)送數(shù)據(jù)包總數(shù)等。至此，整個場景部署完成。
3 路由協(xié)議的仿真及性能比較
在Ubuntu 10.04環(huán)境下使用NS?3.16對AODV、DSDV和OLSR這三種路由協(xié)議進(jìn)行仿真，并在相同的仿真場景下比較其性能指標(biāo)。分別在靜態(tài)場景和動態(tài)場景下，考察網(wǎng)絡(luò)規(guī)模、網(wǎng)絡(luò)拓?fù)渥兓瘜f(xié)議性能的影響。
3.1 靜態(tài)場景
仿真場景設(shè)置：模擬器的隨機(jī)數(shù)種子設(shè)定為常數(shù)7，節(jié)點按網(wǎng)格分布，網(wǎng)格邊長500 m，節(jié)點的規(guī)模從2×2，3×3逐漸增大到18×18；設(shè)定節(jié)點的通信半徑為656 m，選取網(wǎng)格中對角線的一個節(jié)點向另一個節(jié)點發(fā)送UDP數(shù)據(jù)包，共發(fā)送500個數(shù)據(jù)包，包的大小為1 000 B，發(fā)送時間間隔為1 s。這里節(jié)點的物理層傳輸延遲模型采用ConstantSpeedPropagationDelayModel，衰落模型選用FriisPropagationLossModel，數(shù)據(jù)傳輸速率設(shè)置為1 Mb/s。增加網(wǎng)絡(luò)節(jié)點數(shù)，考察3種協(xié)議的端到端平均時延和包投遞率情況，如圖2和圖3所示。
由圖2可以看出，3種路由協(xié)議的平均時延隨節(jié)點規(guī)模的增大而增大，其中AODV和OLSR協(xié)議受到的影響較小，而DSDV的平均時延隨著節(jié)點規(guī)模的增大而急劇增大。圖3中AODV，OLSR的數(shù)據(jù)包投遞率隨節(jié)點數(shù)增大而不變，能保證百分百交付；而DSDV協(xié)議的投遞率在節(jié)點數(shù)增大到一定的規(guī)模后開始下降。以上特性說明在節(jié)點規(guī)模增大時，AODV和OLSR協(xié)議的性能要優(yōu)于DSDV。
3.2 動態(tài)場景
仿真場景設(shè)置：在靜態(tài)場景的基礎(chǔ)上，為節(jié)點添加RandomWalk2dMobilityModel運動模型，該模型為每個節(jié)點隨機(jī)選擇一個方向，以設(shè)定的速度移動一段時間后再隨機(jī)選擇另一個方向繼續(xù)移動，直接到仿真結(jié)束。設(shè)定相同的隨機(jī)數(shù)種子以保證每次仿真中節(jié)點的運行軌跡一致。設(shè)定網(wǎng)格的邊長為300 m，節(jié)點的規(guī)模固定為7×7，即節(jié)點運動的區(qū)域限制在2 100 m×2 100 m的矩形內(nèi)。仍考察對角線的一個節(jié)點向另一個節(jié)點發(fā)送UDP數(shù)據(jù)包，每次仿真發(fā)送3 000個數(shù)據(jù)包。增加節(jié)點移動速度，考察三種協(xié)議的端到端平均時延和包投遞率情況，如圖4和圖5所示。
從圖4和圖5可以看出，3種路由協(xié)議的平均時延與節(jié)點的移動速度相關(guān)性不大，在速度較小時，3種路由協(xié)議的平均時延較穩(wěn)定，但在速度較大時，由于節(jié)點在矩形區(qū)域內(nèi)做無規(guī)則的快速運動，數(shù)據(jù)包從源節(jié)點傳輸?shù)侥繕?biāo)節(jié)點的跳數(shù)不確定，所以平均時延變化具有一定隨機(jī)性。
而由圖5可以看出，隨著節(jié)點移動速度的增大，數(shù)據(jù)包的投遞率逐漸下降，AODV協(xié)議因其屬于按需路由而不需要頻繁地維護(hù)路由信息，所以在速度較大時較其他2種協(xié)議表現(xiàn)更好。
4 結(jié) 語
論文通過NS?3搭建了MANET路由仿真平臺，從端到端平均時延和投遞率角度分析比較了MANET三種路由協(xié)議。靜態(tài)場景中，節(jié)點數(shù)增加時，3種協(xié)議端到端平均時延均隨之增加，但AODV和OLSR增加不明顯，并且兩者的投遞率也幾乎不受網(wǎng)絡(luò)規(guī)模影響，相比之下，DSDV端到端時延和投遞率受網(wǎng)絡(luò)規(guī)模影響較明顯。動態(tài)場景中，節(jié)點移動速度增加，3種協(xié)議的投遞率都降低，而且總體上平均時延較小者，表現(xiàn)出更好的投遞率。
參考文獻(xiàn)
[1] 雷擎，王行剛.計算機(jī)網(wǎng)絡(luò)模擬方法與工具[J].通信學(xué)報，2001，22（9）：84?90.
[2] HENDERSON T R， LACAGE M， RILEY G F. Network simulations with the NS?3 simulator [C]// Proceedings of the ACM SIGCOMM. Seattle， Washington： [s.n.]， 2008： 1111?1121.
[3] NS?3 developers. NS?3 Tutorial [EB/OL]. [2012?11?13. http：///docs/release/3.15/manual/ns?3manual.
[4] 王立平，崔智林，馬力.基于OPNET仿真平臺的MANET路由協(xié)議性能分析[J].現(xiàn)代電子技術(shù)，2011，34（14）：71?74.
[5] PERKINS C E， BHAGWAT P. Highly dynamic destination?sequenced distance vector routing（DSDV） for mobile computer [C]// Proc. of ACMSIGCOMM’94. [S.l.]： ACM， 1994， 8： 250?256.
[6] JOHNSOM D， MALTZ D A， BROCH J. The dynamic source routing protocol for mobile AD hoc networks （Internet?draft） [M]. [S.l.]： Mbole Ad?hoc Network（MANET） Working Group，IETF， 1998.
[7] CLAUSEN T， JACQUET P， ADJIH C， et al. Optimized link state routing protocol [J]. 2003.
關(guān)鍵詞 城市巡邏 移動自組網(wǎng) 路由協(xié)議
中圖分類號：TF393 文獻(xiàn)標(biāo)識碼：A
1 移動自組網(wǎng)
移動自組織網(wǎng)絡(luò)（MANET）是由一組依靠無線鏈路通信的獨立移動節(jié)點組成的一個臨時性自治系統(tǒng)。由于MANET具有無中心、自組織、部署迅速等優(yōu)點，非常適合多個移動點之間傳輸信息，是巡邏過程傳輸視頻首選的組網(wǎng)方式。
2路由協(xié)議
在MANET中，源節(jié)點在向目的節(jié)點發(fā)送數(shù)據(jù)時，通常需要其它中間節(jié)點的中繼轉(zhuǎn)發(fā)，因此路由協(xié)議是MANET中極其重要的部分。目前應(yīng)用較為廣泛的是OLSR、DSR、AODV三種路由協(xié)議。OLSR協(xié)議是一種先應(yīng)式的鏈路狀態(tài)路由協(xié)議，采用優(yōu)化的洪泛機(jī)制來廣播鏈路狀態(tài)信息。DSR協(xié)議是按需路由協(xié)議，每個數(shù)據(jù)分組攜帶有整條路由信息。AODV協(xié)議也是按需路由協(xié)議，采用逐跳轉(zhuǎn)發(fā)分組方式。
3場景建立
基于OPNET軟件模擬城市巡邏場景，設(shè)定哨兵的移動速度為5km/h，巡邏車輛的移動速度為20km/h。巡邏人員之間進(jìn)行視頻信息交互。
4路由性能分析
模型建立后，設(shè)置OLSR、DSR、AODV三種路由協(xié)議進(jìn)行仿真，選擇吞吐量、時延、路由開銷三個統(tǒng)計量作為評價路由性能的參數(shù)。仿真結(jié)果如圖1、圖2、圖3。
由仿真結(jié)果可以看出，OLSR 的吞吐量一直在2000kbits/s以上，網(wǎng)絡(luò)可靠性最高。時延方面，OLSR為100ms左右，滿足實時通信需求。OLSR在網(wǎng)絡(luò)初始化階段路由開銷較高，但隨后迅速降低，協(xié)議效率較好。
5結(jié)論
本文分析了移動自組網(wǎng)的特點，提出了在城市巡邏過程中通過建立移動自組網(wǎng)實現(xiàn)現(xiàn)場視頻的實時傳輸。同時，基于OPNET軟件比較分析了OLSR、DSR、AODV三種路由協(xié)議性能。由仿真結(jié)果可以看出，在城市巡邏場景中，OLSR協(xié)議的吞吐量、時延、路由開銷性能均為最優(yōu)。
參考文獻(xiàn)
[1] 孫寶林，桂超，李媛，等.移動Ad Hoc網(wǎng)絡(luò)路由技術(shù)研究[M].武漢：湖北人民出版社，2008：2-3.
[2] 鄭少仁，王海濤，趙志峰，等.Ad Hoc網(wǎng)絡(luò)技術(shù)[M].北京：人民郵電出版社，2005：1-4.
關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)（WSN）；LEACH協(xié)議；拓?fù)浣Y(jié)構(gòu)；帶狀網(wǎng)絡(luò)
中圖分類號：TN929.5 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-7712 (2012) 14-0052-02
一、概述
路由協(xié)議一直以來是無線傳感器網(wǎng)絡(luò)中的一個重要研究方向。無線傳感器網(wǎng)絡(luò)的路由協(xié)議將數(shù)據(jù)從源節(jié)點發(fā)送到基站或者匯聚節(jié)點，其主要目標(biāo)是在滿足應(yīng)用需求的情況下盡可能地降低網(wǎng)絡(luò)的能耗，通過有效地能量管理技術(shù)避免網(wǎng)絡(luò)連通性的惡化，提高網(wǎng)絡(luò)的整體性能。但是由于WSN中節(jié)點的處理能力和能量有限的局限性，傳統(tǒng)的路由協(xié)議無法滿足它的要求，很大程度的影響了路由協(xié)議的研究，因此本文的目標(biāo)是針對帶狀網(wǎng)絡(luò)研究一種改進(jìn)的路由協(xié)議L-P。該協(xié)議以LEACH為基礎(chǔ)進(jìn)行改進(jìn)，更適應(yīng)帶狀網(wǎng)絡(luò)應(yīng)用。
二、路由協(xié)議分析
LEACH協(xié)議通過隨機(jī)選舉簇頭避免了簇頭過分消耗能量；通過簇頭的數(shù)據(jù)融合有效減少了通信量，從而提高了網(wǎng)絡(luò)生存時間。但該協(xié)議采用單跳通信，擴(kuò)展性差，雖然傳輸時延較小，但要求節(jié)點具有較大通信功率，不適合大規(guī)模應(yīng)用；即使在小規(guī)模網(wǎng)絡(luò)中，離匯聚節(jié)點較遠(yuǎn)的節(jié)點由于采用大功率通信會消耗大量能量，導(dǎo)致生存時間較短；而且頻繁的動態(tài)拓?fù)浣Y(jié)構(gòu)變化和大量額外的廣播也會耗費很多能量。
（三）LEACH協(xié)議的不足
LEACH協(xié)議雖然是分簇類協(xié)議有著不可替代的優(yōu)勢，但仍有一些地方有待商榷，直接應(yīng)用于長帶狀狀網(wǎng)絡(luò)還是有很多不適應(yīng)的地方，仍需要根據(jù)具體的應(yīng)用環(huán)境進(jìn)行相應(yīng)的改進(jìn)。
（1）簇頭的選擇只遵循等概率，而沒有考慮節(jié)點的剩余能量，如果一個能量較低的節(jié)點被選作簇頭，就很容易因大工作量耗盡能量而失效，因而縮短了網(wǎng)絡(luò)的生命周期。
（2）簇頭是選取隨機(jī)的，無法保證簇頭節(jié)點的合理分布，如果某區(qū)域附近沒有簇頭節(jié)點時，該區(qū)域內(nèi)的節(jié)點就要選擇加入距離較遠(yuǎn)的簇，這樣就增加簇頭和簇內(nèi)節(jié)點的通信距離，使得能量消耗增大。
（3）所有的簇頭都是直接與匯聚節(jié)點通信，那么離匯聚節(jié)點越遠(yuǎn)的簇頭能量就消耗得越快，生存時間就越短，整個網(wǎng)絡(luò)也因此受到影響。工作面環(huán)境復(fù)雜，通信距離經(jīng)過實測也就30m左右，每個節(jié)點都直接與匯聚節(jié)點通信是不可能的。如果只是簡單的其之間采用多跳路由，那么離匯聚節(jié)點較近的節(jié)點因為多輪多次轉(zhuǎn)發(fā)其他簇頭的數(shù)據(jù)，能量消耗的更多。而且網(wǎng)絡(luò)規(guī)模越大，節(jié)點數(shù)目越多，死亡越快，從而影響網(wǎng)絡(luò)的生命周期。同時，由于數(shù)據(jù)向一個方向傳輸，會形成一頭大一頭小的“棒槌”式結(jié)構(gòu)，這必然造成能量的不均衡分布。
（4）傳感器節(jié)點在加入簇時僅考慮通信能耗最小，不考慮簇的負(fù)載程度，這會導(dǎo)致各個簇中的節(jié)點數(shù)嚴(yán)重不均衡，不利于簇首能量的均衡消耗和網(wǎng)絡(luò)生命周期的延長。
四、改進(jìn)的路由協(xié)議研究
（一）網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)
（二）算法設(shè)計
L-P協(xié)議也是基于分簇的路由協(xié)議，但不同于LEACH，由于網(wǎng)絡(luò)呈長帶狀分布，若采用單跳路由形式，距離匯聚節(jié)點遠(yuǎn)的節(jié)點能量很容易耗盡。故該協(xié)議采用簇間單跳的動態(tài)方式傳遞信息。簇頭一旦確定，簇便隨機(jī)建立，每簇的簇頭就成為中繼節(jié)點。這樣就由簇頭節(jié)點組成了多條能夠遍歷整個區(qū)域的簇頭鏈，但路徑質(zhì)量和通信代價良莠不齊，而不同的無線傳感器網(wǎng)絡(luò)對于傳輸路徑的能耗或可靠性的要求各有高低。因此通過對每條候選路徑的能耗或丟包率的比較，最終確定一條符合要求的簇頭鏈。如果數(shù)據(jù)融合量很小，數(shù)據(jù)流就會呈“棒槌”狀，越靠近匯聚節(jié)點數(shù)據(jù)量越大，造成的“熱區(qū)”問題。故本文利用非均勻分簇的思想，越靠近匯聚節(jié)點簇的規(guī)模越小，來解決“熱區(qū)”問題，平衡整個網(wǎng)絡(luò)的負(fù)載，提高網(wǎng)絡(luò)的生存時間達(dá)到增加網(wǎng)絡(luò)壽命的目的。
五、仿真與分析
本文通過對LEACH協(xié)議和改進(jìn)的L-P協(xié)議進(jìn)行了仿真和比較。主要從丟包率和生存節(jié)點個數(shù)這兩個方面分析，說明該進(jìn)的協(xié)議的優(yōu)勢。
六、結(jié)論
丟包率和存活節(jié)點數(shù)是衡量無線傳感器網(wǎng)絡(luò)可靠性和網(wǎng)絡(luò)生命周期的重要指標(biāo)。L-P協(xié)議在這兩方面都要優(yōu)越于LEACH協(xié)議，改進(jìn)后的簇首選擇機(jī)制，非均勻成簇方式和簇間通信機(jī)制的確提高了網(wǎng)絡(luò)和協(xié)議可靠性，延長了網(wǎng)絡(luò)生命周期。由此可見，改進(jìn)后的L-P協(xié)議更適應(yīng)帶狀網(wǎng)絡(luò)的無線通信應(yīng)用。
參考文獻(xiàn)：
[1]任豐源,黃海寧,林闖,無線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報,2003,14(7):1278-1291.
針對無線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸可靠性的問題，本文提出了一種可靠性路由協(xié)議RANC，在GAINZ實驗平臺上實現(xiàn)RANC拓?fù)浯罱ǎo出了節(jié)點組網(wǎng)具體過程，實現(xiàn)可靠路由的最佳通信路徑選擇。
【關(guān)鍵詞】無線傳感器網(wǎng)絡(luò)RANC GAINZ可靠性
1 引言
無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）是由多個微型傳感器節(jié)點面向任務(wù)以自組織方式構(gòu)成的網(wǎng)絡(luò)，WSNs由多個微型傳感器節(jié)點通過自組織方式構(gòu)成，其自組織性和容錯能力使它非常適合在特殊時刻和環(huán)境中應(yīng)用。WSNs一般部署在面積廣闊且復(fù)雜惡劣的環(huán)境中，傳感器節(jié)點資源受限，自然環(huán)境損毀和能量耗盡將導(dǎo)致節(jié)點失效，對實際應(yīng)用產(chǎn)生巨大隱患。這些隱患決定了路由協(xié)議在WSNs研究中的重要性。為了保證WSNs能夠正常通信，必須保證路由在全連通的基礎(chǔ)上進(jìn)行數(shù)據(jù)傳輸信息。本文首先介紹了一種可靠性路由協(xié)議RANC算法（Routing Algorithm Based on Node Credibility），在此算法基礎(chǔ)上，在GAINZ平臺實驗環(huán)境實現(xiàn)WSNs真實的網(wǎng)絡(luò)拓?fù)洹?/p>
2 RANC協(xié)議簡介
本節(jié)介紹的RANC路由協(xié)議綜合了鏈路質(zhì)量、傳感器節(jié)點能量、儲存空間等對路由可靠性的影響，通過可信度數(shù)學(xué)模型的構(gòu)建實現(xiàn)網(wǎng)絡(luò)路徑的調(diào)整，達(dá)到延長網(wǎng)絡(luò)生命期的目的。
WSNs中節(jié)點可信度（Node Credibility，NC）的數(shù)學(xué)模型表示為：
（1）
式（1）中，Ere（j）為j的剩余能量，d（j，sink）為節(jié)點j到基站的距離，LQ（i，j）為（i，j）的鏈路質(zhì)量，TC（j）為節(jié)點j的轉(zhuǎn)發(fā)能力。節(jié)點的轉(zhuǎn)發(fā)能力與節(jié)點緩存占用率BO和擁塞因子CF有關(guān)，轉(zhuǎn)發(fā)能力的數(shù)學(xué)表達(dá)式可表示為：
（2）
通過式（1）、（2）可以得出節(jié)點可靠性數(shù)學(xué)模型：
（3）
式（3）可以看出節(jié)點可靠性與傳感節(jié)點剩余能量Ere（j）、節(jié)點緩存占用率BO（j）、鏈路質(zhì)量LQ（i，j）、擁塞因子CF（j）正相關(guān)，與節(jié)點到基站的距離負(fù)相關(guān)。因此，在實驗過程中可以選擇節(jié)點剩余能量多的、節(jié)點緩存占用率高的、鏈路質(zhì)量優(yōu)并且與目的節(jié)點距離小的節(jié)點作為通信節(jié)點，使路由數(shù)據(jù)傳輸工作更為可靠。
3 RANC協(xié)議在GAINZ平臺實現(xiàn)方案
GAINZ平臺硬件由微處理器，射頻芯片以及設(shè)備組成，是一款WSNs硬件開發(fā)平臺，傳感器節(jié)點在AVR單片機(jī)基礎(chǔ)上進(jìn)行設(shè)計。基于GAINZ實驗平臺上，實現(xiàn)RANC路由協(xié)議搭建的網(wǎng)絡(luò)結(jié)構(gòu)。
3.1 拓?fù)浯罱ㄟ^程
協(xié)調(diào)器節(jié)點組網(wǎng)過程的具體偽碼如下所示：
協(xié)調(diào)器節(jié)點組網(wǎng)算法
確定網(wǎng)絡(luò)環(huán)境，設(shè)定自身網(wǎng)絡(luò)ID
令N=0；
whlie收到節(jié)點請求
if N
N+1，將該節(jié)點IP、能量信息等加入鄰居列表，并向請求節(jié)點發(fā)送加入回復(fù)信息
else if N>Nmax
將加入請求信息刪除
end if
end
3.2 RANC拓?fù)鋵崿F(xiàn)
在實驗環(huán)境，硬件環(huán)境由20個GAINZ節(jié)點，USB電子狗和PC機(jī)組成。軟件環(huán)境分為兩部分，一部分為由C語言編寫的測試程序；另一部分是在運行的Zigbee分析儀。
圖1為 GAINZ平臺上的原始拓?fù)鋱D，通過RANC算法，通過擇優(yōu)選擇路由，選擇最佳通信路徑，提升路由數(shù)據(jù)傳輸?shù)目煽啃裕鐖D2所示。
4 結(jié)語
本文針對WSNs網(wǎng)絡(luò)中路由選擇問題，介紹了RANC路由協(xié)議優(yōu)化網(wǎng)絡(luò)的通信路徑。給出了RANC協(xié)議的網(wǎng)絡(luò)拓?fù)浯罱ㄟ^程，并且在GAINZ平臺上的實現(xiàn)RANC拓?fù)洹Ｍㄟ^優(yōu)化網(wǎng)絡(luò)通信路徑，達(dá)到延長網(wǎng)絡(luò)生命期。
參考文獻(xiàn)
[1]李凌晶.能量有效的無線傳感器網(wǎng)絡(luò)路由協(xié)議研究[D].南京：南京郵電大學(xué)學(xué)位論文，2012：6-9.
[2]韓旭，劉迎新，文正江.無線傳感器網(wǎng)絡(luò)路由協(xié)議研究[J].中國儀器儀表，2012，9：27-31.
[3]孫佩剛，趙海，羅玎玎等.無線傳感器網(wǎng)絡(luò)鏈路通信質(zhì)量測量研究[J].通信學(xué)報，2007，28（10）：14-22.
[4]于海濱，曾鵬，王忠峰等.分布式無線傳感器網(wǎng)絡(luò)通信協(xié)議研究[J].通信學(xué)報，2004，25（10）：102-110.
關(guān)鍵詞：Ad Hoc網(wǎng)絡(luò)；多播路由；協(xié)議；網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)
中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2008)31-0841-05
Multicast Routing Protocols in Ad Hoc Networks
HU Jia-qing
(Anhui Architectural Design & Research Institute, Hefei 230001, China)
Abstract: Ad Hoc wireless network is a multi-hop, temporary and non-central network without infrastructure to support which consists of a group of wireless mobile nodes. Multicast is a group-oriented communication transmission mode, and it uses a single source address to send data to a group of hosts. How to realize effective multicast routing algorithms is an urgent problem which needs to be solvedin this research field. In this paper, current several typical multicast routing protocols are described and studied, their own working ways are analyzed and their characteristics are compared.
Key words: Ad Hoc networks; multicast routing; protocol; network topology
1 引言
在典型的Ad Hoc網(wǎng)絡(luò)中，主機(jī)按組工作以共同完成一個特定任務(wù)，例如軍事上對人員及裝備的指揮與控制、在線游戲、交通管理等。因此，多播在Ad Hoc網(wǎng)絡(luò)中扮演著重要角色。
多播是一種一點對多點的分組傳輸方式。當(dāng)有多臺主機(jī)同時成為一個分組的接收者時，出于對帶寬和CPU負(fù)擔(dān)的考慮，多播成了一種最佳選擇。在一個擁有多個主機(jī)的網(wǎng)絡(luò)中，為了能讓多個主機(jī)接收到相同的數(shù)據(jù)包，假如要采用單播傳送的方式，那么源主機(jī)就必須不斷地產(chǎn)生多個相同的數(shù)據(jù)包，然后發(fā)送給其他主機(jī)。但對于一些對于時延很敏感的數(shù)據(jù)，在源主機(jī)發(fā)送多個相同的數(shù)據(jù)包后再產(chǎn)生第二個數(shù)據(jù)包，顯然是不可取的。而且，對于一臺主機(jī)而言，不停的產(chǎn)生一個相同的數(shù)據(jù)包也是很大的負(fù)擔(dān)。在這種情況下，如果采用多播發(fā)送，源主機(jī)只需發(fā)送一個數(shù)據(jù)包就可以到達(dá)每個需要數(shù)據(jù)的組成員主機(jī)上，提高了網(wǎng)絡(luò)資源的利用率，同時降低了通信成本。
研究多播問題的關(guān)鍵是如何確定多播路徑。當(dāng)前，人們一般采用多播生成樹來描述多播數(shù)據(jù)包在網(wǎng)絡(luò)里經(jīng)過的路徑，多播路由算法主要就是建立一棵性能好的多播樹。多播樹的根為源主機(jī)，其節(jié)點為所有的多播組員，其優(yōu)點在于信息以并行方式沿著樹枝發(fā)送到不同多播成員，減低了信息傳遞的延遲，并且信息的復(fù)制只是在樹杈上進(jìn)行，網(wǎng)絡(luò)中需要傳送的復(fù)制信息最少，從而節(jié)省了網(wǎng)絡(luò)帶寬資源，減少了擁塞。一般而言，網(wǎng)絡(luò)中的多播路由算法應(yīng)提高自身的計算效率，降低多播服務(wù)本身的系統(tǒng)開銷，還要為新的網(wǎng)絡(luò)服務(wù)和網(wǎng)絡(luò)資源的優(yōu)化配置
提供有效的支持，這樣才能使網(wǎng)絡(luò)的運行效率得到進(jìn)一步的提高。
2 Ad Hoc網(wǎng)絡(luò)多播路由協(xié)議
多播路由協(xié)議是實現(xiàn)多播的基礎(chǔ)，而固定網(wǎng)絡(luò)中的多播路由協(xié)議，如距離適量多播路由協(xié)議DVMRP、開放的最短路徑多播MOSPE、基于核心的樹CBT、協(xié)議獨立的多播PIM等，使不適合在Ad Hoc網(wǎng)絡(luò)中運行的，原因是由于Ad Hoc網(wǎng)絡(luò)的特殊性，包括以下幾個方面：
1) 網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化：導(dǎo)致頻繁的組成員發(fā)現(xiàn)與維護(hù)過程、路由更新過程，大大增加了協(xié)議的附加開銷。
2) 無固定的基礎(chǔ)設(shè)施：需要所有的節(jié)點參與路由信息的存儲、更新。包括新成員的加入、成員的退出、成員的移動、多播路由參與節(jié)點的移動。
針對Ad Hoc網(wǎng)絡(luò)的特殊性，在設(shè)計移動Ad Hoc網(wǎng)絡(luò)的多播路由算法時，我們需要重點考慮以下幾個問題：
1) 算法應(yīng)該有對網(wǎng)絡(luò)拓?fù)渥兓拿舾行院土己玫淖赃m應(yīng)能力。算法須通過協(xié)議消息的交互獲得網(wǎng)絡(luò)的拓?fù)湫畔ⅲ瑥亩S護(hù)路由狀態(tài)的有效性；對網(wǎng)絡(luò)拓?fù)渥兓奶幚頇C(jī)制需要考慮算法消息的效率，如在廣播流量較輕時，由廣播數(shù)據(jù)驅(qū)動建立和維護(hù)廣播路由狀態(tài)，可以有效地降低網(wǎng)絡(luò)維護(hù)的開銷。
2) 數(shù)據(jù)轉(zhuǎn)發(fā)的效率和可靠性，避免路由環(huán)路，降低重傳率，避免路由狀態(tài)失效導(dǎo)致大量的分組丟失。
3) 建立和維護(hù)路由狀態(tài)的效率，既要在動態(tài)的網(wǎng)絡(luò)中保持路由狀態(tài)的健壯性和保持轉(zhuǎn)發(fā)結(jié)構(gòu)的連通性，又要降低路由開銷，這是一對矛盾。
迄今為止，Ad Hoc網(wǎng)絡(luò)的研究者已提出了一些多播路由協(xié)議，根據(jù)參與多播傳送的節(jié)點的拓?fù)浣Y(jié)構(gòu)，可分為基于樹的多播路由、基于格網(wǎng)的多播路由、混合的多播路由。另外，還提出可一些其它思想的多播路由，包括無狀態(tài)的多播路由、似然的多播路由、基于位置的多播路由等等。
在Ad Hoc網(wǎng)絡(luò)中，多播路由協(xié)議主要工作在媒體訪問層、路由層、應(yīng)用層三個層次，其參考模型如圖1所示：
1) MAC層：MAC層主要負(fù)責(zé)數(shù)據(jù)傳輸和分組接收，它提供刪除節(jié)點、觀察鏈路的特性和執(zhí)行數(shù)據(jù)的傳輸和接收三種功能。與它所對應(yīng)的三個服務(wù)模塊式鄰居表處理模塊、傳輸模塊和接收模塊。鄰居表處理模塊主要是維護(hù)節(jié)點的鄰居信息，可以通過信標(biāo)或信道的數(shù)據(jù)分組來獲取。傳輸模塊主要是對信道傳輸方案進(jìn)行仲裁，依賴于MAC層的傳輸協(xié)議，MAC協(xié)議通過信道的傳輸狀態(tài)來維護(hù)多播狀態(tài)信息。
2) 路由層：大多數(shù)的多播路由協(xié)議都是在路由層工作的，如建立路由表，構(gòu)成和維護(hù)單播或多播路由、路由生命周期和路由緩沖區(qū)等信息，維護(hù)多播成員的加入、刪除和多播數(shù)據(jù)分組的傳輸和接收等。路由層主要是由單播路由信息處理模塊、多播信息處理模塊、多播轉(zhuǎn)發(fā)模塊、樹/格網(wǎng)結(jié)構(gòu)模塊、路徑緩沖區(qū)維護(hù)模塊和多播表示維護(hù)模塊等六大模塊構(gòu)成。
3) 應(yīng)用層：主要對多播應(yīng)用需求提供服務(wù)，由數(shù)據(jù)分組傳輸/接收控制模塊和多播表示者/終端模塊組成。
3 基于樹的多播路由
在有線網(wǎng)絡(luò)中，基于樹的多播路由協(xié)議是性能非常好的協(xié)議，計算機(jī)網(wǎng)絡(luò)中實現(xiàn)多對多通信的主要方式就是多播樹算法，多播樹是連接多有多播成員的最小代價生成樹，研究人員結(jié)合Ad Hoc網(wǎng)絡(luò)自身的特性把基于樹的多播路由協(xié)議引入到網(wǎng)絡(luò)中，設(shè)計出了許多經(jīng)典的路由協(xié)議。
基于樹的多播路由主要有兩種：獨立樹的多播路由和共享樹的多播路由。獨立樹的多播路由是指為各個多播發(fā)送者分別建立多播路由，使用獨立樹尋徑，相關(guān)節(jié)點必須為每個不同的多播發(fā)送者維護(hù)一個多播表項，其可擴(kuò)展性不好且開銷很大，典型的代表協(xié)議有ABAM、ADMR等。共享樹多播路由是指所有多播發(fā)送節(jié)點建立一個共享的路由樹，使用共享樹尋徑，可擴(kuò)展性好，存儲開銷也小，但是分組的傳送路徑大于發(fā)送節(jié)點到接收節(jié)點間的最短路徑。典型的協(xié)議有MAODV、AMRIS、LAM等。
基于樹的多播路由有以下優(yōu)點：
1) 有效性高。在多播路由樹中，兩個節(jié)點之間提供一條路徑，多播發(fā)送者能以最少的拷貝把分組分發(fā)到各個組接收者。對于包括N個節(jié)點的網(wǎng)絡(luò)，只需要N-1條鏈路來傳送相同的分組到所有的節(jié)點。對于單信道的無線網(wǎng)絡(luò)，利用無線傳輸?shù)膹V播特性，以各成員節(jié)點只需發(fā)送一次。
2) 節(jié)點的路由決策簡單。只需將分組轉(zhuǎn)發(fā)到能到達(dá)的樹接口上。
基于樹的多播路由協(xié)議的路徑是非優(yōu)化的，所有的共享樹需要一個核心節(jié)點來維護(hù)組的信息和創(chuàng)建多播樹，增加了核心節(jié)點的通信量。另外，基于樹的多播路由協(xié)議的魯棒性也不好，路由樹的任何一段鏈路有故障或因移動不可用將導(dǎo)致路由樹的重構(gòu)，從而會帶來大量的控制開銷。
其中AMRIS協(xié)議和MAODV協(xié)議是典型的基于樹的Ad Hoc網(wǎng)絡(luò)多播路由協(xié)議：
A）AMRIS協(xié)議(Ad Hoc Multicast Routing Protocol Utilizing Increasing ID-Numbers Protocol)是新加坡國立大學(xué)C.W.WU等人提出的，98年11月成為IETF草案。它是按需路由協(xié)議，基于共享樹的協(xié)議。網(wǎng)絡(luò)中的每個節(jié)點分配一個多播成員ID號msm-id,并且指定一個稱為會話節(jié)點(SID)的特定節(jié)點，且該節(jié)點的ID最小。Msm-id表明每個節(jié)點在共享樹中的邏輯權(quán)重，以指導(dǎo)多播數(shù)據(jù)的流向。AMRIS以SID為根，基于表示號來創(chuàng)建多播傳送樹。
主要設(shè)計思想如下：
3.1 多播樹的初始化
SID節(jié)點的選擇：對于只有一個發(fā)送者的一次多播會話，SID分配給這個發(fā)送者；對于有多個發(fā)送者、多個接收者的一次多播會話，需要先選舉一個發(fā)送者，并把SIDF分配給它。
各節(jié)點ID的計算：SID節(jié)點(會話節(jié)點)根據(jù)多播會話需要，廣播一個NEW-SESSION分組，通過該分組，建立一個從會話節(jié)點向外輻射狀MSM-ID遞增的分級邏輯結(jié)構(gòu)。具體過程如下：NEW-SESSION分組包含SID的MSM-ID，鄰居節(jié)點收到該分組后，就計算它們自己的MSM-ID，取值要大于分組中指定的那個MSM-ID。然后，節(jié)點將分組中的MSM-ID用它們自己的MSM-ID替換后繼續(xù)轉(zhuǎn)發(fā)NEW-SESSION分組。
3.2 多播成員的加入
節(jié)點A可以通過發(fā)送JOIN-REQ來加入一個多播會話，并因此而形成一個新的或加入一個已經(jīng)存在的共享樹。
具體過程如下：
1) 節(jié)點A在具有比自己小的MSM-ID的潛在父親節(jié)點列表中選擇一個節(jié)點，比如節(jié)點B，并向B發(fā)送一個單目標(biāo)JOIN-REQ分組。B在接收到JOIN-REQ后，如果B已經(jīng)加入可該多播會話，就送回一個JOINACK分組；否則，B發(fā)送JOIN-REQ給B潛在的父親。該過程重復(fù)，直到尋找到一個成員父親節(jié)點，并由它沿JOIN-REQ的反向路徑向A發(fā)送JOIN-ACK消息；
2) 如果上述過程失敗，A將進(jìn)行一個本地廣播來尋找成員父親節(jié)點；
3) 如果A不能發(fā)現(xiàn)任何父親節(jié)點，它就執(zhí)行“支路重構(gòu)”過程，其作用就是在共享分發(fā)樹發(fā)生變化的時候局部動態(tài)修復(fù)分發(fā)樹。
3.3 多播樹的維護(hù)
多播樹的維護(hù)過程保證多播傳送過程節(jié)點的連續(xù)性，當(dāng)兩個節(jié)點間的連路不可用時，有ID號較大的節(jié)點執(zhí)行支路重構(gòu)BR，使節(jié)點能夠重新加入。BR包括BR1和BR2兩個過程。在節(jié)點具有潛在的鄰居父親節(jié)點時，執(zhí)行BR1過程；在節(jié)點沒有潛在的父親節(jié)點時，執(zhí)行BR2過程。
BR1工作過程與節(jié)點的加入過程是一樣的。
BR2的工作過程不同于加入過程，節(jié)電A廣播一個JOIN-REQ消息，該消息指向一個范圍字段R，使廣播是一個受限的廣播。接到JOIN-REQ消息的節(jié)點如果是父親節(jié)點，則沿反方向路徑JOIN-ACK消息到該節(jié)點，A可能收到多個JOIN-ACK，它選擇一個，JOIN-CONF消息到選擇的父親節(jié)點B，B接收到JOIN-CONF時，就建立一個到A的樹分支。
B) MAODV協(xié)議(Multicast Ad Hoc On-Demand Distance Vector Routing Protocol)是美國加州大學(xué)E.M.Royer等人于1999年提出的，2000年成為IETF草案，它是在單播路由協(xié)議AODV基礎(chǔ)上設(shè)計的按需多播路由協(xié)議，可以同時支持單播、廣播、多播三種通信方式。其主要過程如下：
1) 巡徑表
主要是維護(hù)兩個巡徑表和一個多播請求表。
2) 分組格式
RREQ分組格式是，其中，J_flag為加入標(biāo)志；R_flag為路由修復(fù)標(biāo)志；
RREP的分組格式是，其中R_flag和U_flag兩個標(biāo)志用于多播維護(hù)。
MACT的分組格式是,其中，
3) 多播成員的加入
(1) RREQ分組的產(chǎn)生及處理
節(jié)點發(fā)送RREQ分組加入多播組，RREQ的信宿地址設(shè)置為多播地址，新宿序列號設(shè)為其所了解的該組多播的最大序列號，J_flag設(shè)為‘1’。RREQ的發(fā)送方式為兩種，如果通過查詢“多播請求表”可獲得首領(lǐng)節(jié)點，并有到首領(lǐng)成員的有效路由，則單播RREQ到首領(lǐng)節(jié)點；否則，廣播RREQ分組。
(2) RREP的產(chǎn)生和處理
多播成員發(fā)RREP響應(yīng)RREQ，RREP沿反方向路徑單播到加入節(jié)點。RREP分組包括多播序列號、首領(lǐng)地址、多播跳數(shù)。反向路徑上的節(jié)點添加一個多播路由表項，用于建立向前路徑。
(3) 當(dāng)加入節(jié)點廣播RREQ時，它可能收到多個RREP。每個RREP都建立一個多播路由，加入節(jié)點選擇一個具有最大序列號和最小跳數(shù)的路由，并向該路由的下一跳單播MACT分組，接收到MACT分組的下一跳，把（1）創(chuàng)建的多播路由表項的“路由使能”=有效。
如果下一跳時多播樹的成員，則不傳播MACT；否則，選擇下一跳，單播MACT，其下一跳的多播路由表項的“路由使能”=有效；重復(fù)這個過程，直至到達(dá)一個多播樹的成員節(jié)點。
4) 多播路由的維護(hù)
首領(lǐng)成員通過周期性的廣播“Group hello”消息，來維護(hù)多播組的序列號，每廣播一個“Group hello”消息，其序列號加1。多播組成員自己決定退出某多播組。在一定時間內(nèi)未收到鄰居的任何分組，則鏈路不可用，多播樹不可用鏈路的修復(fù)。當(dāng)鏈路不可用時，由鏈路的下游節(jié)點負(fù)責(zé)修復(fù)。
下面介紹一些其它基于樹的多播路由協(xié)議：
LGT協(xié)議是一個基于分組封裝技術(shù)的小規(guī)模多播路由協(xié)議。其思想類似于DDM。LGT以單播路由協(xié)議為基礎(chǔ)，在其上構(gòu)建一個多播路由樹。多播數(shù)據(jù)被封在單播分組中，分組中包括有信宿地址表。節(jié)點基于分組中的信宿列表，使用LGK(位置指示K排列樹，location-guided k-array)和(位置指示Steiner樹，location-guided Steiner)算法進(jìn)行分組轉(zhuǎn)發(fā)樹。這兩種算大不需要網(wǎng)絡(luò)拓?fù)湫畔ⅲ昧诵潘薰?jié)點的地理位置信息，并假設(shè)地理位置越遠(yuǎn)，到達(dá)信宿的跳數(shù)越大，啟發(fā)式地進(jìn)行樹的構(gòu)造。
ABAM協(xié)議(Associativity-Based Ad Hoc Multicast Protocol)：該協(xié)議采用源節(jié)點為根的轉(zhuǎn)發(fā)樹結(jié)構(gòu)，其特點是在網(wǎng)絡(luò)中維護(hù)每條鏈路的一個關(guān)聯(lián)屬性(Ass -ociativity).其屬性包括：鏈路的穩(wěn)定度、鏈路發(fā)送的成功率、無線信號的接收強(qiáng)度、電源的壽命預(yù)期等等。源節(jié)點以廣播方式發(fā)送尋路信息，在傳遞過程中收集所經(jīng)路徑的關(guān)聯(lián)屬性。接收節(jié)點從接收到的多個消息中根據(jù)關(guān)聯(lián)屬性選擇一條路徑，接入到轉(zhuǎn)發(fā)樹。ABAM對轉(zhuǎn)發(fā)樹的連通性維護(hù)采取兩步策略，首先嘗試局部維護(hù)機(jī)制，如失敗則啟動全局的維護(hù)機(jī)制。鏈路通斷檢測采用與MAODV類似的機(jī)制，需要節(jié)點周期性地發(fā)送Hello消息。
ADMR協(xié)議(Adaptive Demand-Driven Multicast Routing)：該協(xié)議采用源節(jié)點為根的轉(zhuǎn)發(fā)樹，由源節(jié)點的數(shù)據(jù)驅(qū)動轉(zhuǎn)發(fā)結(jié)構(gòu)的建立和維護(hù)。路由算法描述如下：源節(jié)點啟動的建樹機(jī)制是數(shù)據(jù)驅(qū)動的，有數(shù)據(jù)發(fā)送到新的組時，節(jié)點在數(shù)據(jù)頭部附帶控制消息，在全網(wǎng)范圍廣播。節(jié)點處理消息的過程中，建立反向最短路徑樹，接收成員節(jié)點接收到源節(jié)點的控制消息后，選擇最短路徑連接到轉(zhuǎn)發(fā)樹。接收節(jié)點加入到新的組時，發(fā)送一個廣播消息，該組源節(jié)點接收后，將選擇一條路徑建立到接收節(jié)點的轉(zhuǎn)發(fā)樹枝。
4 基于格網(wǎng)的多播路由
基于格網(wǎng)的多播路由中，參與多播的節(jié)點的拓?fù)浣Y(jié)構(gòu)為格狀網(wǎng)。基于樹的多播路由源于固定格網(wǎng)的樹多播路由協(xié)議的改造和擴(kuò)展，并不太適合拓?fù)渥兓l繁的Ad Hoc網(wǎng)絡(luò)。基于格網(wǎng)的多播路由，由于多播發(fā)送者與接受者之間存在多條路徑，這些冗余的路徑提高了網(wǎng)絡(luò)的動態(tài)適應(yīng)能力，健壯性好，不需要因為少量鏈路的失效而重新配置多播網(wǎng)結(jié)構(gòu)，路由維護(hù)開銷少。
基于格網(wǎng)的多播路由協(xié)議主要有按需多播路由協(xié)議ODMRP(on demand multicast routing protocol)、核心輔助的格網(wǎng)協(xié)議CAMP(core assisted mesh protocol)、向前轉(zhuǎn)發(fā)多播路由協(xié)議(forwarding group multicast protocol)等。
以下是幾種典型的基于格網(wǎng)的移動Ad Hoc網(wǎng)絡(luò)多播路由協(xié)議：
A) ODMRP協(xié)議是由美國加州大學(xué)洛杉磯分校WAM實驗室的Sung-Ju Lee等人提出的，它是使用“轉(zhuǎn)發(fā)組”概念的格網(wǎng)多播路由協(xié)議，并使用“軟狀態(tài)”來維護(hù)多播成員關(guān)系，不需要顯示的控制消息來退出多播組。在ODMRP中，組成員和路由的建立和更新由發(fā)送者按需進(jìn)行。具體如下：
1) 構(gòu)造格網(wǎng)（形成組）
當(dāng)源節(jié)點有多播數(shù)據(jù)要發(fā)送，但沒有路徑或成員消息時，就在全網(wǎng)廣播一個Join-Query分組。當(dāng)一個多播成員節(jié)點收到一個非重復(fù)的Join-Query分組，就保存上游節(jié)點的ID，并在Join-Query分組中記錄該節(jié)點，以建立反方向路徑；然后再廣播新的Join-Query分組。如果這個節(jié)點同時是多播接收者，它就構(gòu)造一個Join-Reply分組并廣播給鄰居節(jié)點。
Join-Reply分組包括了多播接收者到各個源節(jié)點的反向路徑的下一跳節(jié)點的ID。當(dāng)鄰居節(jié)點收到Join-Reply分組時，如果它的ID和Join-Reply中的某個下一跳節(jié)點的ID匹配，該節(jié)點意識到自己是多播路由的一個節(jié)點，且是轉(zhuǎn)發(fā)組的成員，然后它就設(shè)置FG-flag標(biāo)志，把自己加入到多播格網(wǎng)中，構(gòu)造并廣播自己的Join-Reply。
這樣Join-Reply就被每一個轉(zhuǎn)發(fā)組成員轉(zhuǎn)播，直到它通過最短路徑到達(dá)源節(jié)點。這個過程構(gòu)造或更新了從源節(jié)點到接收點的路徑，并且建立了轉(zhuǎn)發(fā)群組。多播發(fā)送者通過周期性發(fā)送Join-Query分組，來刷新組成員關(guān)系信息并更新路由信息。
2) 多播數(shù)據(jù)轉(zhuǎn)發(fā)
來自源節(jié)點的多播數(shù)據(jù)通過轉(zhuǎn)發(fā)組到達(dá)各個接收者，即當(dāng)傳送多播數(shù)據(jù)時，如果當(dāng)前節(jié)點是轉(zhuǎn)發(fā)節(jié)點，并且收到的分組是不重復(fù)的，節(jié)電將轉(zhuǎn)發(fā)這些數(shù)據(jù)。由于所有的轉(zhuǎn)發(fā)節(jié)點都中繼數(shù)據(jù)，當(dāng)主路徑由于節(jié)點移動而失效時，冗余路徑有助于數(shù)據(jù)的遞交。
3) 移動性預(yù)測
ODMRP依靠周期性地洪泛Join-Reply分組來刷新路由和維護(hù)組成員的關(guān)系。因此，ODMRP的發(fā)送間隔必須隨移動類型和速度自適應(yīng)調(diào)整，以使泛洪帶來的通信開銷盡量小。
4) 軟狀態(tài)
在ODMRP中，成員的退出不需要特殊的控制消息。當(dāng)一個發(fā)送者退出時，不再發(fā)送Join-Query分組；接受者退出時，不再發(fā)Join-Reply分組；中間轉(zhuǎn)發(fā)節(jié)點在一段時間內(nèi)未收到Join-Reply分組時，將取消FG-flag標(biāo)志，降級為非轉(zhuǎn)發(fā)節(jié)點.
B) CAMP協(xié)議是基于格網(wǎng)的協(xié)議，接收者發(fā)起的、通過創(chuàng)建一個共享的格網(wǎng)結(jié)構(gòu)支持多播。它依賴于單播路由協(xié)議，格網(wǎng)包含從所有接收者到所有發(fā)送者的反向最短路徑，不需要通過廣播（泛洪）方式建立格網(wǎng)，而是通過若干個核心節(jié)點創(chuàng)建多播格網(wǎng)，每個格網(wǎng)可以有多個核心節(jié)點，核心節(jié)點可以不是格網(wǎng)組成員。CAMP協(xié)議將節(jié)點分為雙工、單工成員和非成員節(jié)點，雙工成員是多播網(wǎng)的完全成員，負(fù)責(zé)轉(zhuǎn)發(fā)接收的多有該多播組的數(shù)據(jù)包；單工成員用于創(chuàng)建兩個成員之間的單向連接，負(fù)責(zé)轉(zhuǎn)發(fā)唯一的上游節(jié)點送來的數(shù)據(jù)包，節(jié)電根據(jù)需要選擇成為單工節(jié)點還是雙工節(jié)點。
CAMP協(xié)議基本思想是設(shè)置若干個“核心”節(jié)點，普通節(jié)點通過“核心”節(jié)點發(fā)送Join-Request來加入群組，這樣能夠起到限制Join-Request分組流量的作用，然后，目的節(jié)點再根據(jù)單播路由信息來優(yōu)化。
CAMP協(xié)議的優(yōu)點是不需要通過廣播方式建立格網(wǎng)，當(dāng)發(fā)送者數(shù)量和群組成員數(shù)量增加時，CAMP不會引起多播更新分組的指數(shù)增長，性能優(yōu)于ODMRP，缺點是依賴于單播路由協(xié)議，各節(jié)點緩存有大量的路由信息，當(dāng)節(jié)點移動時，需要更新大量的數(shù)據(jù)，不適合高移動的Ad Hoc網(wǎng)絡(luò)。
5 混合的多播路由
基于樹的多播路由協(xié)議可提供較高的分組轉(zhuǎn)發(fā)有效性，但是魯棒性較差:而基于格網(wǎng)的多播路由協(xié)議可提供較好的魯棒性，但有較高的數(shù)據(jù)轉(zhuǎn)發(fā)通信量和增加網(wǎng)絡(luò)的負(fù)載。混合多播路由協(xié)議能較好地發(fā)揮基于樹的多播路由協(xié)議和基于格網(wǎng)的多播路由協(xié)議的優(yōu)點。
AMRoute協(xié)議是主動路由協(xié)議，它基于用戶多播樹和動態(tài)核心，創(chuàng)建一個雙向的共享分發(fā)樹。在建立分發(fā)樹之前先創(chuàng)立網(wǎng)絡(luò)，利用虛擬網(wǎng)絡(luò)鏈路建立多播樹，這樣當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時，只要邏輯核心節(jié)點和多播樹成員之間通過格網(wǎng)鏈路的路徑依然存在，樹就不需要調(diào)整。
AMRoute協(xié)議主要包括兩個過程：構(gòu)造格網(wǎng)和形成共享分發(fā)樹，這兩個過程可同時進(jìn)行。
1) 構(gòu)造格網(wǎng)
AMRoute的組成員包含所有成員圖，每個成員初始化時，先建立一個僅有自己的單節(jié)點格網(wǎng)，自己是核心節(jié)點，核心節(jié)點以不斷遞增的TTL發(fā)送JOIN-REQ分組，用于發(fā)現(xiàn)其它成員。即當(dāng)成員節(jié)點A收到B的JOIN-REQ分組，A用JOIN-ACK分組回應(yīng)，并將B視為鄰節(jié)點，而B收到JOIN-ACK分組后，也將A作為它的同組鄰居，然后A和B利用分布式的核心選舉算法決定誰保留核心地位。這樣不斷進(jìn)行下去，最終形成一個格網(wǎng)。
2) 形成共享分發(fā)樹
共享分發(fā)樹是在成員格網(wǎng)的基礎(chǔ)上建立的，核心節(jié)點周期性地向格網(wǎng)中的與之有關(guān)的連路發(fā)送TREE-CREATE消息。當(dāng)成員節(jié)點接收到一個非重復(fù)TREE-CREATE的時候，將其轉(zhuǎn)發(fā)到所有其它鏈路上，并將輸入和輸出鏈路標(biāo)記為“樹鏈路”。當(dāng)節(jié)點收到的是一個重復(fù)的TREE-CREATE分組時，丟棄該分組，并沿接收鏈路返回一個TREE-CREATE-NAK分組，將該鏈路標(biāo)記為“格網(wǎng)鏈路”。
AMRoute固然有其優(yōu)點，但在有些時候是不實用的，比如某些臨時環(huán)境，創(chuàng)建的樹就是非理想的了。
6 多播路由協(xié)議的比較
多播路由協(xié)議設(shè)計的基本思想是以最小的冗余創(chuàng)建成員之間的路徑，前面敘述的各種協(xié)議都試圖以不同的機(jī)制來達(dá)到這個目標(biāo)。
有表1可看出，在移動環(huán)境下，基于格網(wǎng)的協(xié)議明顯優(yōu)于基于樹狀的多播協(xié)議，因為當(dāng)節(jié)點移動導(dǎo)致鏈路斷開時，格網(wǎng)中的冗余路徑為傳遞數(shù)據(jù)提供了可選擇的路徑。一個自組網(wǎng)的路由協(xié)議除了支持移動性外，其健壯性和高效率也是重要指標(biāo)。在網(wǎng)絡(luò)結(jié)構(gòu)上，基于樹的多播路由具有最短路徑的高效性，網(wǎng)狀結(jié)構(gòu)則提供較好的魯棒性。
參考文獻(xiàn)：
[1] Sung-Ju Lee, Mario Gerla, Ching-Chuan Chiang. On-demand multicast routing protocol[C]. New Orleans: Proceedings of IEEE WCNC’99, 1999. 1298-1302.
[2] Lee S J. A performance comparison study of Ad Hoc wireless multicast protocols[C]. New York: Proceedings of IEEE INFOCOM, 2000:565-574.
[3] Jason Xie. AMRoute: Ad-Hoc multicast routing protocol[J]. Mobile Networks and Applications, 2002,(7):429-439.