基于相互關系的自適應多目標Ad Hoc路由協議研究

徐　偉，汪學明

(貴州大學 大數據與信息工程學院，貴州 貴陽 550025)

?

基于相互關系的自適應多目標Ad Hoc路由協議研究

徐偉，汪學明

(貴州大學 大數據與信息工程學院，貴州 貴陽 550025)

Foundation Item:National Natural Science Foundation of China([2011]61163049);Natural Science Foundation of Guizhou Province([2011]2197)

摘要：在移動Ad Hoc網絡中，基于相互關系的多目標路由協議(ABAM)不能根據節點間移動引起的相互關系變化以及網絡拓撲結構改變對其建立的多目標通信樹做出適時調整，容易造成多余中間轉發節點的出現和節點間相互關系的弱化。針對以上缺點提出了一種基于相互關系的自適應ABAM協議。通過對改進的協議進行仿真進行分析，結果表明新協議在控制開銷方面有所增加，但在分組投遞率、時延、路由跳數方面的性能都優于ABAM協議。

關鍵詞：移動Ad Hoc網絡；自適應ABAM；多目標路由協議；協議分析

0引言

移動Ad Hoc[1](MANET)網絡由于組網方便，不需要建立基站支持通信，在臨時組網方面的優勢是其他基站式通信無法比擬的。近幾年MANET網絡方面的研究一直是學術界研究熱點。

在MANET網絡中路由協議設計的優劣直接影響網絡通信的性能。近幾年MANET網絡的路由協議研究已經取得了豐碩的成果，但由于MANET是無線網絡，網絡節點位置不固定，節點間頻繁移動，使得MANET協議設計變得非常復雜，很多情況下一方面性能的提升是以犧牲其他方面性能為代價的。

在MANET中如共享文本、圖片,召開視頻會議等都需要將數據信息由一點傳送到多點。在點對多點傳輸應用中如果使用點對點傳輸協議，會大大增加網絡開銷，造成網絡擁塞。多目標路由協議正是為了解決這種多目標傳輸應用而設計的。目前多目標路由協議主要有按需距離矢量多目標路由協議(MAODV)、按需驅動多目標路由協議(ODMRP)、自適應按需驅動多目標路由協議(ADMR)[2]、基于相互關系的多目標路由協議(ABAM)[3]。

基于相互關系的多目標路由(ABAM)協議主要是根據節點之間的相互關系穩定性為每個多目標通信建立一棵根部在發送節點的多目標樹。節點之間的相互關系穩定性主要表現在時間、空間、連接以及功率消耗[4]的穩定性方面。ABAM協議確保了多目標樹建立之初的穩定性。但是這種穩定是相對的，多目標樹建立后，除非連接斷開否則協議并不會對多目標樹進行維護。此外ABAM協議對網絡拓撲結構變化也不敏感，不能很好的解決整個通信過程的相對穩定性。自適應ABAM路由協議正是為解決以上所述ABAM的缺點與不足而提出的。

1基于相互關系的自適應多目標MANET路由協議

在自適應ABAM路由協議中從多目標通信的發起到結束分為三個階段：第一是多目標通信的發起階段，這個階段由發送節點發起并建立一棵從發送節點到接收節點的多目標樹；2)第二是多目標通信階段，多目標樹維護、節點加入退出都在此階段完成；3)最后就是多目標通信的結束階段。

1.1自適應ABAM路由協議多目標樹建立

在多目標通信的第一階段，發送節點通過向MANET網絡廣播一條多目標廣播查詢信息(Multicast Broadcast Query，MBQ)來建立多目標通信[5]。MBQ主要用來收集節點間的相互關系并用于多目標樹的建立。最初MBQ信息僅包含發送節點和接收節點信息，MBQ每經過一個節點，節點便將自己的地址信息及相互關系信息(相關信息包括中繼載荷、信號強度、相互關系梯度)寫入MBQ并將其轉發出去。為了防止MBQ無限轉播，節點對被其轉發過的MBQ進行舍棄。

如圖1所示MBQ由發送節點發出并終止于接收節點。接收節點為所要建立的多目標樹收集到達該節點的全部MBQ信息，并根據收到的全部MBQ信息計算出一條到達發送節點的基于相互關系的最佳路徑[6]。隨后，接收節點沿著這條路徑向發送節點發送一條MBQ-REPLY響應信息。對于1對n點的多目標通信，發送節點根據收到的n條MBQ-REPLAY信息后計算出一棵最佳的多目標樹。隨后，發送節點向多目標樹上的所有節點發送一條MC-SETUP，下行節點接收到MBQ- SETUP信息后加入多目標通信并向其下行節點轉發。MBQ-SETUP逐級轉發多目標樹也隨之逐級建立直到樹枝末端，至此一棵從發送節點到接收節點的多目標樹建立完畢。

圖1　自適應ABAM路由協議多目標樹建立過程

移動Ad Hoc網絡中由于節點的可移動性，網絡拓撲結構時刻變化，節點發送的MBQ信息不一定得到全部接收節點響應。為了防止如圖1所示孤立節點不能響應MBQ信息而導致多目標樹建立進入等待狀態，進而導致多目標通信失敗情況發生，自適應ABAM在協議中設置多目標樹建立最大等待時間TWMAX和最小接收MBQ-REPLAY數量NRMIN參數，并把MBQ的生存期規定為TWMAX/2。節點對超過生存期的MBQ進行舍棄處理。在(0，TWMAX)時間內發送接收節點收到的MBQ-REPLAY數NR≥NRMIN時，不再等待接收剩余節點發回的MBQ-REPLAY信息，轉而建立1對NR點的多目標通信。發送節點對于大于TWMAX的MBQ-REPLAY信息進行舍棄處理，并發送一條REJECT信息通知接收節點以新成員方式加入多目標樹。

1.2自適應ABAM路由協議多目標樹維護

在MANET網絡中，節點間的相互關系隨著節點間的移動和網絡拓撲結構的變化而不斷變化[7]，自適應ABAM路由協議具有檢測這種相互關系變化的能力，并實時刪除穩定性差的樹枝重建穩定性好的枝節。

設衡量節點相互關系量為Q，樹枝更新門限值為Qth，Q包含路由中繼載荷、信號強度、相互關系梯度信息。Q值越高代表節點間通信質量，穩定度越好。在自適應ABAM路由協議中樹枝更新發生在以下兩種情況：(1)節點與多目標樹中上行的其他節點存在直通鏈路且相互關系量為Q1，節點與當前連接的上行節點相互關系量為Q2，當Q1-Q2≥Qth時啟動樹枝修復；(2)樹枝斷裂發生后啟動樹枝修復機制。

當一個節點A檢查到與多目標樹中上行節點B存在直接連通鏈路時，A向B發送一個MBQ信息，B接收到MBQ信息后向A發送MBQ-REPLAY應答信息，A獲取A與B之間的相互關系量Q1，當Q1與A當前連接的上行節點的互關系量Q2滿足Q1-Q2≥Qth時，節點便啟動樹枝修復機制。節點A根據B發回的MBQ-REPLAY計算出到達B的基于相互關系的最佳路徑，隨后根據此路徑計算出更新后的多目標樹，并將其寫入MC-UPDATE。A向整個多目標樹節點發送新生成的MC-UPDATE信息，多目標樹也隨之被更新。

檢測到鏈路中斷后，多目標樹修復機制啟動。在鏈接斷裂處的下行節點C廣播一條RLQ(Repeat Link Query)信息來重新取得與上行節點的連接。RLQ只有廣播節點的上行節點響應并向RLQ發送節點發送一條RLQ-REPLY信息，C節點收到來自上行節點的RLQ信息后計算出一條基于相互關系的最佳路徑，隨后向所有多目標樹節點發送一條MC-UPDATE信息通知所有節點更新多目標樹。

1.3自適應ABAM路由協議多目標樹組成成員動態性處理

自適應ABAM路由協議允許新的接收節點動態的加入多目標通信。節點E通過向MANET網絡廣播一條JOIN信息來加入多目標樹。只有多目標樹上的節點才響應JOIN信息，當節點響應JOIN信息后，向E發送一條JOIN—REPLY信息。節點E累計JOIN-REPLY信息并計算出基于相互關系的最佳路徑，隨后向發送節點發送一條JOIN-SETUP信息，發送節點根據JOIN-SETUP計算出節點加入后的多目標樹，并向新樹上的所有節點發送一條MC-UPDATE以更新整棵樹。

1.4自適應ABAM多目標樹刪除

當接收節點退出多目標樹通信時，退出的接收節點向樹上的所有節點發送一個不包含自己的信息的MC-UPDATE信息，樹上的其他節點收到MC-UPDATE信息后整棵樹被更新，接收節點所在的樹枝被修剪掉，從而完成接收節點的退出。當發送節點退出多目標樹時，發送節點向整個樹的所有節點發送一條不包含任何節點信息的MC-UPDATE信息，其他節點接收到空MC-UPDATE信息后自動退出多目標樹，從而整個多目標樹被刪除。

2自適應ABAM與ABAM協議的對比分析

基于相互關系的多目標路由(ABAM)協議主要是根據節點之間的相互關系穩定性為每個多目標通信建立一個根部在發送節點的多目標樹。但ABAM協議只考慮了節點連接斷裂后的多目標樹重建情況，并沒有考慮多目標樹通信過程中由于節點相互移動引起的相互關系的變化以及網絡拓撲結構變化的情況。自適應ABAM協議能夠動態的檢測節點間相互關系和網絡拓撲結構的變化，并相應的調整多目標樹以保持其穩定性。

如圖2(a)所示自適應ABAM協議和ABAM協議在最初建立的多目標樹是一樣的。在MANET網絡中各節點間是相互移動的，節點間的相互關系以及網絡拓撲結構隨時間的變化而不斷變化。如圖2(b)所示網絡拓撲結構發生變化后多目標樹各節點間的連接并未斷開，ABAM協議并不會檢測到這種情況，而是維持原來的多目標樹不變。如圖2(b)所示的多目標樹中發送節點和接收節點間浪費了兩個中間轉發節點從而增加了信號的傳輸距離和端對端延遲，浪費了寶貴的無線信道資源。

自適應ABAM協議可以檢測到網絡拓撲結構和節點相互關系的變化，并對多目標樹進行動態維護。圖2(c)中所示當接收節點A和接收節點B運動到發送節點旁邊時。接收節點A首先在路由表中檢測到發送節點。隨后A向發送節點發送一個MBQ，發送節點接收到MBQ信息后作出響應并將其路由信息及與A的相互關系量寫進MBQ發回給節點A。節點A收到MBQ信息后計算與發送節點之間的相互關系量Q1。當節點A與其連接的上行節點的相關度Q2當滿足Q1-Q2≧Qth時，節點將自己所在的樹枝刪除并鏈接到發送節點上，隨后節點A將新生成的多目標樹信息寫入MC-UPDATE向整個樹的全部節點進行廣播，當其他節點收到MC-UPDATE信息后根據里面的新樹信息調整自己在多目標樹中的角色。新的多目標樹更新后接收節點B發現一條經過A到發送節點且比當前支路更短。于是B發起新一輪的子樹修復過程，當B發出MC-UPDATE信息后，中間兩級轉發節點已經不在多目標樹中，于是中間兩級節點自動退出多目標樹。由圖2(c)可以看到使用了自適應ABAM協議的MANET網絡中多目標通信網絡所需的中間轉發跳數要比ABAM少，從而節省了網絡帶寬，減輕了網絡負擔，減少了端對端延時。

在自適應ABAM協議中多目標樹的更新、刪除以及接收節點的退出和加入均采用統一的消息格式(MC-UPDATE)而多目標樹節點間的相互關系量的獲取統一采用MBQ消息，MBQ消息可以是洪廣播也可以是局部廣播，還可以是點對點通信。采取什么樣的MBQ廣播方式主要取決于MBQ的用途，如發送節點進行多目標樹的建立采用洪廣播方式，接收節點獲取與上行節點間的相互關系信息使用點對點通信?？傊捎媒y一的消息格式有助于簡化自適應ABAM的實現以及節省控制開銷。

(a)自適應ABAM、ABAM初始多目標樹

(b)ABAM多目標樹

(c)自適應ABAM多目標樹

3OPENT仿真分析

下面使用OPNET仿真工具分析自適應ABAM協議和ABAM協議的性能[8]。

仿真MANET網絡由200*200M正方形區域內50個通信節點組成，每個節點在區域內自由隨機游動，節點最大傳輸距離為50米，采用自由空間傳播模型。在MAC層中使用IEEE 802.11協議[9]，網絡層使用ABR路由協議。采用節點隨機移動模型，移動節點數量可變，節點移動速度均勻分布在0~5 m/s范圍內，節點停留時間60 s。

在仿真中設置一個多目標通信，其中包含一個發送節點和5個隨機分布在200*200M正方形區域內的接收節點。每次仿真200 s，采用CBR數據流，UDP[10]發送數據，每秒鐘產生1個分組，有效載荷為500B。每次仿真都采用不同的隨機種子。對協議進行20次相同的仿真，最后將20次仿真結果取均值作為實驗仿真結果。

(a)數據吞吐量

(b)控制開銷

(c)數據分組平均傳輸距離

(d)平均端到端時延

從圖3(b)中可以看出自適應ABAM協議的控制開銷大于ABAM協議，自適應ABAM的平均控制分組數量為3 527，ABAM的平均控制分組數量為3 100。自適應ABAM協議平均控制分組數量略大于ABAM協議，這是因為自適應ABAM在多目標樹連接未斷開時仍然會發送控制分組調整多目標樹從而增加了控制開銷，但隨著移動節點比例的增加，自適應ABAM協議控制開銷表現和ABAM協議相近。這表明自適應ABAM協議更適合工作在大比例移動節點的無線網絡。

從圖3(a)、圖3(c)、圖3(d)中可以看出自適應ABAM協議的平均分組交付率、平均轉發跳數和平均端到端時延分別為87.1%、4.3、43.5 ms，而ABAM協議為81.3%、4.6、47.3 ms。自適應ABAM協議雖然犧牲了控制開銷這一性能但卻帶來了數據吞吐量、平均轉發跳數和端到端延時性能的提升，隨著移動節點比例的增加自適應ABAM協議的表現更加突出。

仿真結果表明平均情況下自適應ABAM協議在分組交付率、轉發跳數和端到端時延性能上比ABAM表現更好。自適應ABAM協議在這些性能上的改善主要得益于新協議主動偵測網絡拓撲結構變化的特性。當發現通信節點間存在穩定性更好，路徑更短的支路時協議便會連到這條路徑，更新整個多目標樹，從而使多目標樹保持最佳狀態。而ABAM協議在節點間連接未斷開時，不會偵測這種變化，也不會對目標樹進行更新，雖然這樣可以節省控制開銷，但是卻以犧牲其他性能為代價的，特別是移動節點比例增加時控制開銷和自適應ABAM相近，但在其他性能上新協議表現的更好。

4結語

針對ABAM協議對網絡拓撲結構變化不敏感，不能自適應地調節多目標樹以適應拓撲結構變化的缺點。本文提出了可以檢測拓撲結構變化的自適應ABAM路由協議。通過OPNET仿真分析，結果表明自適應ABAM協議在分組交付率、轉發跳數和端到端時延性能都比ABAM協議更有優勢，新協議也更適合工作在拓撲結構快速變化的MANET網絡。

新協議還有很多有待改進的地方：在控制開銷方面還需要優化，同時此協議對其他因素如節點能耗，節點處理速度，協議安全性等也欠缺考慮，今后將對這些方面做進一步研究。

參考文獻：

[1]SHEN Chien-Chung, Sundaram Rajagopalan. Protocol-Independent Multicast Packet Delivery Improvement Service for Mobile Ad Hoc Networks[J]. Elsevier Science Publishers B. V.,2007, 5(2):1611-1626.

[2]Olimpjon Shurdi, Rozeta Miho, Bexhet Kamo, Vladi Kolici, Alban Rakipi. Performance Analysis of Multicast Routing Protocols MAODV, ODMRP and ADMR for MANETs[C].//Proceedings of the 2011 14th International Conference on Network-based Information Systems,2011:596-601.

[3]陳林星,曾曦,曹毅.移動Ad Hoc網絡-自組織分組無線網絡技術[M].北京：電子工業出版社,2011:392-395.

CHEN Lin-xing, ZENG Xi, CAO Yi. Mobile Ad Hoc Network-Self-Organizing Packet Wireless Network Technology[M]. Electronic Industry Press, 2011:392-395.

[4]WANG Zheng, Hamid Sadjadpour, Jose Joaquin Garcia-Luna-Aceves. The Capacity and Energy Efficiency of Wireless Ad Hoc Networks with Multi-Packet Reception[C]. // Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing,2008:179-188.

[5]Lap Kong Law, Srikanth V Krishnamurthy, Michalis Faloutsos. A Novel Adaptive Protocol for Light Weight Efficient Multicasting in Ad Hoc Networks[J]. Computer Networks: International Journal of Computer and Telecommunications Networking, 2007, 51(3):823-834.

[6]Natarajan Meghanathan. Routing Protocols to Determine Stable Paths and Trees using the Inverse of Predicted Link Expiration Times for Mobile Ad Hoc Networks[J]. International Journal of Mobile Network Design and Innovation, 2012, 4(4):214-234.

[7]Natarajan Meghanathan. A Location Prediction based Routing Protocol and Its Extensions for Multicast and Multi-Path Routing in Mobile Ad Hoc Networks[J].Ad Hoc Networks,2011,9(7):1104-1126.

[8]沈亮光,汪學明.移動Ad Hoc網絡ZRP路由協議的仿真分析[J].通信技術,2013,46(08):71-73.

SHEN Liang-guang, WANG Xue-ming. Simulation Analysis of ZRP Routing Protocol in Mobile Ad Hoc Network[J]. Communications Technology, 2013, 46(08): 71-73.

[9]Hwangnam Kim, Eun-Chan Park, Suk Kyu Lee,HU Chun-yu. Fast Performance Assessment of IEEE 802.11-based Wireless Networks[J]. Elsevier Science Publishers B. V., 2011, 53(11-12): 2173-2191.

[10]Andrei Serjantov, Peter Sewell, Keith Wansbrough. The UDP Calculus: Rigorous Semantics for Real Networking[C].// TACS '01 Proceedings of the 4th International Symposium on Theoretical Aspects of Computer Software,2001:535-559.

徐偉(1989—)，男，碩士研究生，主要研究方向為移動通信、信息安全；

汪學明(1965—)，男，博士，教授，CCF會員，主要研究方向為無線與移動通信、協議分析與模型檢測、密碼學與信息安全。

Adaptive Multi-Objective Ad Hoc Routing Protocol

based on Mutual Relation

XU Wei, WANG Xue-ming

(College of Big Data and Information Engineering, Guizhou University, Guiyang Guizhou 550025, China)

Abstract：In mobile Ad Hoc network, the multi-objective routing protocol (ABAM) based on mutual relation of its multi-objective communication tree could not make timely adjustment in accordance with the change of mutual relation between nodes mobility and network topology, and this would result in the emergency of unnecessary intermediate nodes and the weakening of mutual relation between the nodes. Aiming at the mentioned deficiency, a new adaptive ABAM protocol based on mutual relations is proposed. Analysis and simulation indicate that this modified protocol,although with a slight increase of cost is superior to ABAM protocol in the field of packet delivery ratio, time delay and routing hops.

Key words：mobile Ad Hoc network; adaptive ABAM; multi-objective routing protocol; protocol analysis

作者簡介：

中圖分類號：TP393

文獻標志碼：A

文章編號：1002-0802(2015)12-1384-05

基金項目：國家自然科學基金([2011]61163049);貴州省自然科學基金資助項目(黔科合J字[2011]2197)

收稿日期：2015-07-21；修回日期：2015-11-09Received date:2015-07-21；Revised date：2015-11-09

doi:10.3969/j.issn.1002-0802.2015.12.013