Ａｄ Ｈｏｃ網絡中的多播路由協議

摘要：無線Ad Hoc網絡是指一組無線移動節點組成的多跳的，臨時性的，無基礎設施支持的無中心網絡。多播是一種面向群組計算的通信傳播方式，它使用單一的源地址把數據發給一組主機。如何在移動自組網中實現有效的多播路由技術是當前此領域研究中亟待解決的問題。文中對當前一些典型的多播路由協議進行了研究，并對它們各自的工作方式進行了分析，最后對它們各自的特點進行了比較。

關鍵詞：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.

[4] 王金龍，王呈貴.Ad Hoc移動無線網絡[M].北京:國防工業出版社，2004:106-130.

[5] 孫寶林，李臘元.Ad Ho網絡QoS多播路由協議.[J]計算機學報，2004，27(10):1402-1407.