鏈路穩定的Ａｄ　Ｈｏｃ網絡組播路由協議

劉　琳

摘 要：Ad Hoc網絡中，組播路由協議具有廣泛的應用前景。但由于網絡拓撲的變化，設計具有可靠數據傳輸能力的組播路由協議比較困難。綜合考慮Ad Hoc網絡中節點的移動性和節點能量對路由穩定性的影響，選取具有較高性能的鏈路，使得路由具有較好的穩定性。仿真結果證明，與MAODV協議相比，設計的路由協議明顯提高了數據投遞率，并大大降低了丟包數。

關鍵詞：Ad Hoc網絡；組播路由協議；穩定性；生存時間

中圖分類號：TP393文獻標識碼：B

文章編號：1004-373X(2009)03-007-04

Stable Link Multicast Routing Protocol for Ad Hoc Network

LIU Lin

(School of Electronic Information Engineering,Beijing University of Science and Technology,Beijing,100083,China)

Abstract：In Ad Hoc network,multicast has a wide range of applications.But it is hard to design a reliable routing protocol for the change of topology.On considering the mobility and energy of nodes in Ad Hoc network,this paper proposes a new stable routing protocol,which selects better performance link to make routes stable.The simulation results indicate that it has a higher packet delivery ratio,lower dropped packets than MAODV.

Keywords：Ad Hoc network；multicast routing protocol；stability；life time

0 引 言

Ad Hoc網絡終端具有路由功能,是由一組帶有無線收發裝置的可移動節點組成的一個多跳的臨時性自治系統。Ad Hoc網絡不依賴于任何基礎固定設施，不相鄰的節點間進行通信需要中間節點中繼。由于網絡中的節點可以任意移動，所以網絡拓撲是動態變化的。Ad Hoc網絡具有獨立組網能力，以及自組織性、無中心、動態性、易于鋪設等特點，因而被廣泛應用于緊急救援、道路交通、軍事戰場、偏遠野外和探險等臨時信息系統的建設［1-3］，成為當今的一個研究熱點。

路由協議的設計大多著眼于最小跳數路由的研究，即需要通信的源節點和目的節點在選擇路由時，選擇利用最少數量的中間節點中繼就可以到達的路徑。由于Ad Hoc網絡采用無線通信，并且網絡中的通信終端可以自由移動，因此通信能力受到節點移動性、節點能量和通信范圍等的影響較大。這就造成了無線鏈路頻繁斷裂的可能。當一條路徑上的任何一個鏈路斷裂時，這一路徑就必須找到另一條可用的鏈路來恢復連接，或者斷裂路徑被新發現的另一路徑所代替［4］。這些重路由操作大大消耗了有限的網絡資源和節點能量，從而極大地降低了網絡的通信性能。因此設計一個選擇穩定路徑的路由協議，盡量減少重路由操作，具有非常重要的意義。

目前也出現了一些對穩定路由的研究,文獻［5］利用一種權重的思想進行穩定路由的選擇，文獻［6］利用GPS定位獲得節點位置的思想進行穩定路由的選擇，文獻［7］利用預測路由生存時間的方法來選擇穩定路由。這些都只考慮到節點的移動對路由穩定性的影響，并沒有考慮節點能量對穩定性的影響。由于Ad Hoc網絡中，節點能量是有限的，一旦能量耗盡，節點將無法工作，使得兩節點間的鏈路斷裂，整條路由就會失效。因此考慮路由的穩定性必須考慮能量的影響。

1 鏈路穩定性模型

在Ad Hoc網絡中，整條路由是由兩個節點間的鏈路組成的，因此考慮路由的穩定性，需要選擇具有穩定性的鏈路。兩個節點間鏈路的穩定性主要由兩個因素來決定：節點間的距離和節點的能量。信號的強度與信號的傳輸距離有關，所以鏈路連接需要兩個節點間的距離小于節點信號的有效傳輸距離。節點的可利用能量越多，在數據發送過程中才能保證路由不會因能量的消耗而失效。

1.1 節點間距離

假設在Ad Hoc網中所有節點的有效傳輸距離相同，均為R，節點的信號傳輸能力一致，信號的強度僅與信號的傳輸距離有關。所以在某一時刻，鏈路保持連接只需要兩個節點之問的距離小于節點信號的有效傳輸距離R。在移動自組織網中，節點不是固定的，而是可以自由移動的。兩節點在這一時刻處在有效傳輸距離內，在下一時刻可能已經移出這一距離范圍。因此，不能用某一時刻的節點間距作為衡量指標。鏈路保持連接的時間越長，這條鏈路才能越穩定。

文獻［8］提出通過GPS獲得移動節點的位置、運動速度和運動方向對鏈路可能保持連接的時間LET(Link Expiration Time)進行了預測。設某時刻節點i，j可以直接通信，(xi,yi)，(xj,yj)分別為它們的位置坐標，用vi，vj分別表示兩節點的速度，用θi，θj分別表示兩節點的方向，則節點i，j保持連接的時間預測公式為：

Tij=(a2+c2)R2－(ad－bc)2－(ab+cd)a2+c2

(1)

其中:a=vicos θi－vjcos θj，b=xi－xj，c=visin θi－vjsin θj，d=yi－yj。

1.2 節點能耗

Ad Hoc網絡中的節點不僅能看作數據傳輸的終端，而且可作為路由器來幫助超出傳輸范圍的終端交換數據時進行中繼。Ad Hoc網的一個重要問題是活動的節點是能量受限的。目前考慮到能量問題的路由協議并不多。MTPR(The Minimum Total Transmission Power Routing)［9］提出最小化傳輸中需用的能量，但是它并沒有考慮到剩余節點的能量，不能延長每個節點的生存時間。MMBCR(The Min-Max Battery Cost Routing)［10］考慮到了剩余節點的能量問題，它比較每條路由剩余能量最小的節點，選擇這些節點中具有最大能量的節點所在路由，但是它卻沒有考慮到整體的能量消耗問題。

在實際應用中，自組織網中節點通信能量的開銷要遠遠大于數據計算的能量開銷，因此可以主要考慮節點在通信時的能量消耗。根據文獻［11］提出的模型：

Ec=a?size+ΔE

(2)

其中：Ec表示節點消耗的能量;a為發送單位數據所需消耗的能量;size為數據包的大小;ΔE為節點其他情況下的能量消耗。

從(2)式可以看出能量的消耗與數據傳輸的大小成線性關系。數據的傳輸存在發送和接收兩種狀態，在這兩種狀態下所消耗的能量不同，設節點初始能量為E0，由(2)式可得節點i的剩余能量：

Ei =E0-Eci=

E0-(ri ? sizeri+si?sizesi +ΔEi)

(3)

其中：Eci表示節點已消耗的能量，ri表示節點i接收單位數據消耗的能量，sizeri是節點i接收數據包的大小，si表示節點i發送單位數據消耗的能量，sizesi是節點i發送數據包的大小。

可以看出，每個節點根據自己的數據包的發送和接收就可以得到自己的剩余能量，這樣可以節省網絡中節點能量信息的傳遞，節省了開銷。

1.3 組播路由穩定性指標設計

由于節點間距和節點能量均對路由穩定性產生影響，因此可以采用通用加權的思想將兩者結合起來。設節點i為節點j的下游節點，它們之間的鏈路為Lij，將由式(1)和式(3)得到的鏈路生存時間Tij及下游節點i的能量作為鏈路Lij的穩定性指標，設為Wij，將兩個指標的權值分別設為aij和bij，其中aij+bij=1，則該指標為：

Wij=aijTij+bijEi

(4)

Wij值越大，說明Lij穩定性越好。當Tij很小，而Ei很大時，由式(4)得出的結果可能也會符合要求，為避免這樣的結果，將上式的權值公式用相乘的形式來寫：

Wij = TijaijEibij

(5)

由式(5)得到的Wij只要有一項指標為零，不論其余的指標有多大，得到的總指標都將為零，這樣可以避免由式(4)帶來的極端情況。將式(5)兩端取對數，得到：

lg Wij=Tijlg aij+Eilg bij

此式又成為通用加權公式的形式。因此鏈路Lij的穩定性指標Wij可用式(5)得到的公式表示。

2 LSMRP路由協議

路由是由兩個節點間的鏈路組成的，將上面得到的鏈路穩定性指標設計到組播路由協議中，該協議稱為LSMRP(Link Stability for Multicast Routing Protocol)。LSMRP是按需驅動的組播樹路由協議。

2.1 組播樹的創建

組播樹的創建過程如下：

(1) 每個組播組有一個組長，負責維護和更新本組的序列號，并定期用Group Hello包向全網廣播該組序列號。節點通過發送RREQ-J發起加入組播組請求。如果該節點的組長表中有該組的項目，RREQ-J以單播發送給該組的組長；否則，RREQ-J以廣播發送。接收到RREQ-J的節點在組長列表中檢查是否有該組的項目，如果沒有，節點將RREQ-J的組地址以及RREQ的源地址記錄入組長列表。每個RREQ-J包都包含發送該包節點的位置信息，每個接收到RREQ-J包的節點通過計算W值，對鏈路進行穩定性判斷。將W與預先設定好的門限值V進行比較，若W≥V就認為該條鏈路是穩定的，建立到源節點的反向鏈路，并將RREQ-J重新廣播，否則就認為該條鏈路不穩定，丟棄該包。

(2) 收到RREQ-J的組播樹成員向源節點單播發送RREP-J以回復加入請求。 RREP-J沿RREQ-J傳輸時建立的反向路徑傳送。RREP-J傳輸時，沿途節點在組播路由表中創建對應該組的項目，并把上游節點設置成將RREP-J轉發給它的鄰居節點。

(3) 源節點在發送完RREQ-J等待一段時間后，通常會接收到多個RREP-J。源節點選擇具有最大序列號和最小跳數的路徑，并向下游節點單播發送MACT-J。MACT-J沿RREP-J傳播時建立的正向路徑傳輸。所有接收到MACT-J的節點在組播路由表中設置下游節點，這樣一個更新的組播樹就建立好了。

如果源節點在重試若干次加入請求后仍然沒有接收到回復，說明該組播組在網絡上不存在或者不可達。源節點成為新組的組長，并負責維護該組的信息。

2.2 組播樹的維護

(1) 若非葉節點想離開組播組，則需要作為樹成員保留。若葉節點要離開組播組，它首先將組播路由表中對應該組的路由項刪除，并向上游鏈路發送MACT-P通知上游節點它要離開組播樹。接收到MACT-P的上游節點將退出組播樹的下游節點從組播路由表中刪除。如果上游節點刪除自己的下游節點后成為葉節點且不是組成員，該節點也向上游節點發送MACT-P退出組播組。上述的過程會重復進行直到達到一個組成員或者非葉節點。

(2) 由于節點的移動以及能量的消耗，每條鏈路的W是變化的。因此每隔一段時間，鏈路的下游節點就對鏈路穩定性進行重新判斷，若發現W

由于多次局部重建，會導致組播樹是一個非最優樹，因此每隔一段時間要由源節點重新發起一個路由發現過程，以連接到組播樹上。

3 仿真分析

為了評測LSMRP協議的性能，使用NS-2［12,13］仿真工具對其性能進行模擬研究，并與Ad Hoc網絡中典型的組播路由協議MAODV［14］進行比較。

3.1 仿真環境設置

在800×800單位的平面區域，隨機布置50個節點，仿真時間為100 s，數據包大小為512 B，節點平均移動速度分別為1 m/s，5 m/s，10 m/s，15 m/s，20 m/s和25 m/s，研究節點不同的移動速度下丟包數和投遞率的變化。為了防止仿真中極端環境的影響，每個不同速度，產生多個場景環境，記錄所得數據的平均值。

3.2 仿真結果及其分析

圖1為丟包數隨節點移動速度的變化。可以看到，隨著節點移動速度的增大，MAODV和LSMRP的丟包數均增大。這是因為節點速度變大,網絡的拓撲變化也加快了。在相同移動速度下，LSMRP明顯比MAODV的丟包數少，而且速度越大，丟包數差值越大。這是因為，LSMRP在建立路由前對鏈路的性能進行比較，選出具有較高連接性的鏈路，可大大降低丟包數。

圖1 丟包數的比較結果

圖2為投遞率隨節點移動速度的變化。可以看到，當節點移動速度低于5 m/s時，兩種協議的投遞率都保持在80%以上，但當移動速度加快時，MAODV的投遞率急速下降，當移動速度高于15 m/s時，它的投遞率不能達到70%。而LSMRP協議在節點移動速度為25 m/s時，投遞率仍能高于70%。這是因為LSMRP在路由選擇上對鏈路生存時間和節點能量進行了綜合考慮，并且及時的鏈路修復保證了它較高的投遞率。

4 結 語

LSMRP是一種考慮路由穩定性的組播路由協議。它綜合考慮了節點移動以及節點能量對路由穩定性的影響，所選路徑能夠維持較長時間的連接以及傳輸數據的節點具有較高的能量，并且采用在鏈路斷裂前進行修復的機制。仿真結果證明，LSMRP能夠降低網絡丟包數，并且提高了數據傳輸的可靠性。每條鏈路選擇了具有較優性能的穩定鏈路，因此延長了路由生存時間，從而延長了網絡生存時間。

圖2 投遞率的比較結果

該協議在路由建立時，會對鏈路性能進行比較，會增加網絡時延，對于有快速數據傳輸要求的網絡不適應。另外，在鏈路未斷而即將斷裂時就會進行路由修復，會對資源和節點能量造成浪費。因此還需在路由修復上進行改進。

參考文獻

［1］Magnus Frodigh,Per Johansson.Wireless Ad Hoc Networking-The Art of Networking without a Network ［J］.Ericsson Review,2000(4):248-262.

［2］Ljubica B,Levente B,Srdjan C,et al.Self-organization in Mobile Ad Hoc Network:The Approach of Terminodes ［J］.IEEE Communication Magazine,2001,39(6):166-174.

［3］IETF Secretariat.Mobile Ad Hoc Networks［EB/OL］.http://www.ietf.org/html.charters/manet- charter.html.IETF,2000.

［4］Wang Jianxin，Deng Shuguang,Chen Songqiao,et al.A Route Recovery Method Based on Anycast Policy in Mobile Ad Hoc Networks［J］.Journal of China Institute of Communications，2003，24(10):172-176.

［5］Nen-Chung Wang,Jhu-Chan Chen.A Stable On-demand Routing Protocol for Mobile Ad Hoc Networks with Weight-based Strategy［J］.IEEE PDCAT,2006(12):166-169.

［6］Wu Zhengyu,Song Hantao,Jiang Shaofeng,et al.A Grid-based Stable Routing Algorithm in Mobile Ad Hoc Networks［J］.IEEE AMS,2007(3):181-186.

［7］Chunyen Hsu,Jeanlien C Wu.Finding Stable Routes in Mobile Ad Hoc Networks［J］.IEEE AINA,2004(2):424-427.

［8］William Su，Sungju Lee，Mario Gerla.Mobility Prediction and Routing in Ad Hoc Wireless Networks［J］.International Journal of Network Management，2001(11)：3-30.

［9］Scott K,Bambos N.Routing and Channel Assignment for Low Power Transmission in PCS［A］.Proc.of IEEE Int′l Conf.Universal Personal Comm..1996(2):498 - 502.

［10］Singh S,Woo M,Raghavendra C S.Power-Aware Routing in Mobile Ad Hoc Networks［A］.Proc.of the Fourth Ann.ACM/IEEE Int′l Conf.Mobile Computing and Networking.1998(12):181-190.

［11］Feeney L,Nilsson M.Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment［A］.Proc.of IEEE INFOCOM.2001(3):1 548-1 557.

［12］于斌，孫斌，溫暖，等.NS2與網絡模擬［M］.北京:人民郵電出版社，2007.

［13］NS by Example ［EB/OL］.http://nile.wpi.edu/NS/.

［14］Royer E M,Perkins C E.Multicast Ad Hoc On-demand Distance Vector Routing［Z］.Internet Draft,2000.

作者簡介 劉 琳 女,1981年出生,碩士研究生。主要研究方向為Ad Hoc網絡中基于組播的穩定性路由。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。