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