基于AODV的無線自組織網絡負載均衡路由算法

陳昕韡，袁曉兵，李寶清

（中國科學院上海微系統與信息技術研究所微系統技術國防科技重點實驗室，上海200050）

基于AODV的無線自組織網絡負載均衡路由算法

陳昕韡，袁曉兵，李寶清

（中國科學院上海微系統與信息技術研究所微系統技術國防科技重點實驗室，上海200050）

傳統無線自組織網絡的負載不均，導致端到端時延增大、傳輸比下降、節點大量死亡等問題。為此，以無線自組織網絡按需距離矢量（AODV）路由協議為基礎，提出一種改進的負載均衡算法。采用單路徑負載均衡方法，考慮節點的即時負載和過往負載，使用節點緩沖區的隊列長度、節點剩余能量等指標反映節點的負載情況，并關注瓶頸處的關鍵節點對網絡性能的影響。仿真結果表明，與AODV、改進能量路徑等傳統算法相比，該算法在不同負載情況下的適應性較好，能提供較為穩定的網絡性能。

無線自組織網絡；排隊等待時間；負載均衡；路由算法；網絡時延

1 概述

無線自組織網絡（M obile Ad Hoc Network，MANET）是一種無線節點以動態、自組的方式互連形成的網絡［1-2］。網絡中的節點可以隨機移動，拓撲結構的變化難以預測［3］。因此，路由問題是自組網研究的難點。Pham等人通過理論分析［4］，證明了傳統路由算法會造成負載不均的問題。文獻［5］通過仿真驗證了Pham的理論。無線自組織網絡中的負載不均現象會造成嚴重的后果：在重負載節點上出現的擁塞，會增加分組的排隊等待時間甚至引起分組丟失，導致傳輸比下降，傳輸時延增加［6］；重負載節點能量消耗大甚至因能量耗盡而死亡，導致網絡連通性下降甚至造成網絡分裂，網絡生存時間下降。因此，對負載均衡問題的研究具有重要意義。

無線自組織網絡按需距離矢量（Mobile Ad Hoc Network On-demand Distance Vector，AODV）路由協議是一種在自組網中廣泛應用的協議，仿真結果顯示，它在負載問題中有更好的表現［7］。負載均衡優化算法主要分為單路徑算法和多路徑算法。在單路徑算法中，一對源、目的節點之間只建立一條路徑。在多路徑算法中，一對源、目的節點之間將建立多條路徑。研究顯示，單路徑算法在自組網路由負載均衡問題中更有效［5，8］。因此，本文采用單路徑算法，選擇AODV協議作為基礎協議，從負載均衡的角度對該協議進行優化。

2 改進的負載均衡路由算法

網絡中的負載可以從2個方面進行分析：即時負載和過往負載。即時負載反映了節點當前的負載情況。例如，當節點的緩沖隊列較長，說明節點當前的負載較重，較多的分組經由該節點轉發，緩沖區內的分組將經歷較長的等待時延，甚至被丟棄，節點的能量也將被迅速消耗。過往負載反映了自網絡開始運行至當前時刻節點所承擔的負載。某個節點可能當前的即時負載不大，但是在過去曾經承擔大量的轉發任務，消耗了大量的能量。此時如果讓該節點繼續承擔較多的轉發任務，則容易導致節點的死亡。節點的剩余能量是反映節點過往負載的較好指標，剩余能量較小說明節點在過去承擔的負載較重，之后應該盡量減小該節點的負載。因此，在改進中將綜合考慮即時負載和過往負載這2種負載的均衡。

2.1 節點即時負載

節點緩沖區的隊列長度是反映節點即時負載的較好指標［9］。在已有的負載均衡算法中，通常采用虛擬呼叫準入的方式處理隊列長度信息，即在轉發路由請求（Route Request，RREQ）分組時，若轉發節點的緩沖區隊列長度較大，則丟棄RREQ不進行轉發，從而迫使最終形成的路徑避開該節點［10］。但是，由于需要丟棄RREQ分組，隊列長度閾值的選擇對于算法的性能影響較大。并且，直接丟棄的方式容易造成路由發現的失敗，導致源節點重啟路由發現過程，不但增加了網絡的時延，也造成了更多的能量消耗。因此，本文通過將隊列長度信息記錄在AODV的控制分組中，使得節點可以在比較不同路徑的情況下決定是否丟棄分組，避免了直接丟棄導致的路由發現失敗。具體地，在RREQ、路由應答（Route Reply，RREP）和節點的路由表項中增加一項，用于存儲路徑中節點的最大隊列長度max-qlen。選取一個閾值，當max-qlen大于等于該閾值時，認為節點負載較重。因此，當節點收到一個新的RREQ分組時，將路由表項中已有路徑和RREQ中的max-qlen分別和一個閾值進行比較，若兩者均小于閾值，則說明2條路徑上的節點負載都較輕，根據其他指標進行選路。若一條路徑的max-qlen小于閾值，而另一條大于等于閾值，則選用負載較輕的路徑。若2條路徑的max-qlen均大于等于閾值，此時，將綜合考慮2個max-qlen的大小差異和其他指標。特殊的，當只存在一條路徑時，即使路徑上存在重負載節點，該路徑也將被使用，從而避免虛擬呼叫準入算法中路由發現失敗的問題。節點在轉發AODV控制分組的時候，會根據自身隊列長度對分組中的max-qlen進行更新。

2.2 節點過往負載

節點剩余能量能夠反映節點的過往負載。廣播是路由發現過程的重要組成部分［11］，在已有的算法中，通常在廣播RREQ的過程中將路徑中節點的剩余能量累加，用累加剩余能量最小替代原有的跳數最小準則。但是，一條路徑的性能主要受到瓶頸節點的限制。因此，路徑上剩余能量最小的節點的影響更值得算法考慮，因為該節點的死亡將直接導致路徑的失效，而且用于存儲單個節點的剩余能量所需要的存儲空間遠小于存儲累加剩余能量的空間，所以可以在一定程度上減小算法的開銷。因此，在RREQ、RREP和節點的路由表項中增加一項，用于存儲路徑中節點的最小剩余能量。對于跳數相差不大的多條路徑，選擇最小剩余能量最大的路徑。

2.3 算法改進

改進的算法綜合考慮節點的即時負載和過往負載，路由表更新過程如圖1所示。

圖1 路由表更新過程

當中間節點接收到RREQ分組時，首先根據分組中的序列號以及節點本地記錄的信息判斷是否已經接收過該分組。若已經收到過，則丟棄，否則進行進一步處理。節點在自身的路由表中查找該分組的源節點，若不存在相應的表項，則將信息寫入路由表中。否則判斷是否需要更新相應的路由表項。將RREQ和路由表中的max-qlen分別和閾值th進行比較。若rq-max-qlen＜th而rt-max-qlen≥th，說明出現了負載更輕的路徑，則更新路由表。否則比較2條路徑的跳數。改進算法對原有的跳數準則進行了放寬，引入寬松因子ε。只要新出現的路徑的跳數和原有路徑相差不大，均根據最小剩余能量進行選路。若2條路徑的最大隊列長度均小于閾值，則選擇最小剩余能量較大的路徑。若2條路徑的最大隊列長度均大于等于閾值，則同時比較隊列的長度和最小剩余能量。隊列長度較小并且剩余能量較大時才進行路由表的更新。經過改進，算法可以選擇剩余能量較大、隊列較短的路徑，避開負載較重的瓶頸節點。

3 仿真場景與評價準則

3.1 仿真場景與參數

使用NS2軟件進行仿真。仿真場景及參數如表1所示。節點的移動場景使用NS2軟件內置的setdest工具自動生成。使用CBR流，用NS2軟件中的cbrgen.tcl生成。使用cbrgen工具時采用的種子數分別取1 500，2 000，2 500，仿真結果是這3種情況下結果的平均值。

表1 仿真參數設置

3.2 評價準則

算法的評價指標包括2類：路徑有效性指標和能量有效性指標。路徑有效性指標主要包括傳輸比和端到端時延，定義如式（1）、式（2）所示。

其中，ratio為傳輸比；ns為成功傳輸的分組數；nt為發送的總分組數；delay為端到端時延；ti為第i個分組的傳輸時延；pi為第i個分組；sucess為成功傳輸的分組集合。

能量有效性指標主要包括分組平均能耗、節點死亡數、網絡生存時間。其中，網絡生存時間通常以第一個死亡節點的死亡時間來表示。分組平均能耗如式（3）所示。

其中，ep為分組平均能耗；et為網絡總能耗。

由于負載不均主要導致網絡的吞吐能力下降、時延增大、節點過早死亡等，因此傳輸比、端到端時延、分組平均能耗、節點死亡數、網絡生存時間這些指標對于評價負載均衡路由算法的性能具有重要的意義［12］。

分別對4種算法進行仿真與性能比較，分別為AODV算法、本文提出的改進負載均衡算法、改進的能量路徑算法和隊列虛擬呼叫準入算法。其中，改進的能量路徑算法選用文獻［13］中的M LNR-LM算法，使用路徑中節點剩余能量的累加和代替AODV算法中的跳數作為首要選路準則，當2條路徑的剩余能量累加值相等時，將跳數最小作為第2準則。隊列虛擬呼叫準入算法在中間節點收到RREQ廣播時，根據節點當前的緩沖隊列長度進行判斷，超過一定的閾值則不進行RREQ的轉發。

4 結果分析

4.1 仿真結果

在節點最大速度為20 m/s，連接數為60的情況下對4種算法進行仿真。成功傳輸分組數隨時間的變化如圖2所示。

圖2 成功傳輸分組數隨時間的變化

隊列虛擬呼叫準入算法使用了2個不同的閾值，分別為緩沖區的9/10和1/2。

從圖中可以看出，負載均衡算法成功傳輸的分組數最多，較AODV算法和能量路徑算法，性能有了很大的提高。而隊列虛擬呼叫準入算法受閾值的影響較大，當閾值選擇較好時，網絡中成功傳輸的分組數較大，但是當閾值選擇不當時，性能較差。

AODV、負載均衡算法、能量路徑算法、隊列虛擬呼叫準入算法（9/10）的時延分別為0.096 s，0.065 s，0.006 02 s，0.224 72 s。傳輸比分別為89.7%，93.1%，86%，90.5%。分組平均能耗分別為3.614 J/packet，2.239 J/packet，3.233 J/packet，2.745 J/packet。平均死亡節點數分別為1.33，0.67，2.67，5。第一個死亡節點的死亡時間均為100 s。改進能量路徑算法的時延最小，但是傳輸比也是最低的，并且節點死亡數量最多。因此，該算法是犧牲了其他性能來實現網絡傳輸時延性能的提高。而本文提出的負載均衡算法的綜合效果最好。具有較小的網絡傳輸時延，最大的傳輸比，最低的節點死亡數量，每個分組消耗的能量也最少。

圖3和圖4比較了端到端時延以及傳輸比隨連接數的變化情況。能量路徑算法具有不錯的時延性能，但是傳輸比性能不理想。隊列虛擬呼叫準入算法（9/10）的傳輸比性能不錯，但是時延性能較差。而本文提出的負載均衡算法，在時延和傳輸比上均有較好的表現。尤其在連接數較多的重負載情況中，較AODV算法的性能有了大幅度的提升。和其他3種算法相比，改進算法在不同的負載情況下的適應性較好，能提供較為穩定的網絡性能。

圖3 端到端時延與連接數的變化

圖4 傳輸比與連接數的變化

死亡節點數隨連接數的變化如圖5所示。本文的改進算法在不同的連接數下均能保持較小的節點死亡數量，具有較好的性能。

圖5 死亡節點數與連接數的變化

4.2 參數敏感度分析

改進算法中使用了隊列長度閾值th和寬松因子ε，為了了解算法對這2個參數的敏感度，分別對這2個參數取不同的值進行仿真。仿真參數如表1所示。連接數取60，節點最大速度為20 m/s。仿真結果如表2、表3所示。

表2 寬松因子ε敏感度

表3 隊列長度閾值th敏感度

由表2可以看出，當寬松因子ε取不同值時，仿真結果不變。對改進算法進行分析，可以發現寬松因子的存在主要對2種特殊情況進行限制。一種情況，當最小剩余能量較大的路徑的跳數遠大于另一條路徑時，由于仍存在跳數限制，因此可以避免選擇跳數過大的路徑。另一種情況，當2條路徑的跳數相差不大時，可以讓跳數略大，但是在能量上有優勢的路徑有機會成為最終選擇的路由。從仿真結果可以看出，這2種情況在仿真中較少出現，因此，在最終的平均結果中，它們的影響幾乎可以忽略不計。改進算法的性能提升，主要來自于選路準則在節點能量問題上的強化。但是從考慮全面性的角度來說，仍然在算法中加入帶寬松因子的跳數限制。一方面，雖然之前提到的2種特殊情況出現較少，但是一旦出現可能會造成不良的后果，尤其是第一種情況，跳數過大的路徑，由于存在大量的轉發節點，會造成大量的能量浪費，跳數過大同時也意味著更大的時延，甚至造成分組的丟失。另一方面，對于一些擴展的需求，例如文獻［13］中提出的不同類型電源供電的情況，在考慮能量的同時對跳數的考量也具有重要的意義。因此，改進算法仍然保留對跳數的考慮，保證算法今后的可擴展性。從仿真結果可以看出，改進算法對寬松因子ε不敏感。在一定范圍內可以自由選擇ε。

由表3可以看出。改進算法在不同的th下的性能較為穩定。從圖2中可以看出，隊列虛擬呼叫準入算法取不同的閾值時，算法的性能差異非常大，而本文提出的改進算法可以克服這個問題。這是由于，改進算法并不會由于緩沖區隊列長度超過閾值就直接將新到的RREQ分組丟棄，而是會記錄下緩沖區隊列的長度，將它作為選路的參考。在隊列虛擬呼叫準入算法中，當較多節點均具有較重的負載時，將沒有可用的路徑，導致路由發現的失敗，重傳等機制又進一步加重了網絡的負擔，造成網絡性能的下降。改進算法在較多節點負載較重時，仍能從中選擇負載相對較輕的路徑建立路由，保證了網絡的性能。因此，閾值th的大小對算法性能的影響較小。

5 結束語

針對傳統無線自組織網絡路由協議存在的負載不均問題，本文在AODV協議的基礎上提出一種改進的負載均衡算法。考慮到節點的負載分為即時負載和過往負載。即時負載反映了節點當前的繁忙程度，而過往負載反映了節點在過去所承擔的負載的總和，兩者并不一定相同。因此，對兩者進行綜合考慮。用節點緩沖區隊列的長度反應即時負載，在RREQ分組中記錄路徑經過節點的最大隊列長度，盡量避免使用當前負載較重的節點進行分組的轉發，用節點剩余能量表征節點的過往負載。重視瓶頸關鍵節點對網絡性能的影響，在RREQ分組中記錄路徑經過節點的最小剩余能量，利用寬松因子對經典AODV協議的跳數準則進行放松，在選路時傾向于選擇具有較大的最小剩余能量的路徑。仿真結果表明，改進算法在網絡時延、傳輸比、分組平均能耗等方面均有較好的性能。今后還需要對算法的擴展性進行進一步的研究，例如在節點異構、節點供電方式不同、節點分布不均等情況下算法的擴展，從而提高算法對不同應用場景的適應性。

［1］ 姚忠邦，曹志剛.移動Ad Hoc網絡中的負載均衡路由算法［J］.電訊技術，2004，6（1）：45-49.

［2］ Sunsook J，Nisar H，A lex Z.Node Caching Enhancement of Reactive Ad Hoc Routing Protocols［C］//Proceedings of IEEE Wireless Communications and Networking Conference.Washington D.C.，USA：IEEE Press，2005：1970-1975.

［3］ Hsiao P H，Hwang A，Kung H T，et al.Load-balancing Routing for Wireless Access Networks［C］//Proceedings of IEEE International Conference on Computer Communications.Washington D.C.，USA：IEEE Press，2001：986-995.

［4］ Pham P P，Perreau S.Performance Analysis of Reactive Shortest Path and Multi-path Routing Mechanism with Load Balance［C］//Proceedings of IEEE International Conference on Computer Communications.Washington D.C.，USA：IEEE Press，2003：251-259.

［5］ Souihli O，Frikha M，Hamouda M B.Load-balancing in MANET Shortest-path Routing Protocols［J］.Ad Hoc Networks，2009，7（2）：431-442.

［6］ 王莎莎，朱國暉，王 鑫.Ad Hoc網絡負載均衡路由協議研究［J］.現代電子技術，2013，35（3）：40-46.

［7］ 賈站峰.Ad Hoc網絡按需路由算法優化研究［D］.哈爾濱：哈爾濱工程大學，2010.

［8］ Ganjali Y，Keshavarzian A.Load Balancing in Ad Hoc Networks：Single-path Routing vs.Multi-path Routing［C］// Proceedings of IEEE International Conference on Computer Communications.Washington D.C.，USA：IEEE Press，2004：1120-1125.

［9］ Young JY，George F R.A Workload-based Adaptive Loadbalancing Technique for Mobile Ad Hoc Networks［C］// Proceedings of IEEE Wireless Communications and Networking Conference.Washington D.C.，USA：IEEE Press，2005：2002-2007.

［10］ Sunsook J，Nisar H，Alex Z.Energy Efficiency of Load Balancing in MANET Routing Protocols［C］//Proceedings of the 6th International Conference on Software Engineering，Artificial Intelligence，Networking and Parallel/ Distributed Computing and ACIS International Workshop on Self-assembling Wireless Networks.Washington D.C.，USA：IEEE Press，2005：476-483.

［11］ Xiao Shiliang，Pei Jun，Chen Xinwei，et al.Minimum Latency Broadcast in the SINR Model：A Parallel Routing and Scheduling Approach［J］.IEEE Communications Letters，2014，18（6）：1027-1030.

［12］ 鄭相全，郭 偉.自組網中的負載均衡路由協議［J］.計算機科學，2004，31（13）：40-45.

［13］ Javad V R，Venkatesha P，Ertan O，et al.Enery-aware Routing Algorithm s for Wireless Ad Hoc Networks with Heterogeneous Power Supplies［J］.Computer Networks，2011，55（15）：3256-3274.

編輯 劉 冰

Load Balancing Routing Algorithm Based on AODV for Mobile Ad Hoc Network

CHEN Xinwei，YUAN Xiaobing，LI Baoqing
（Key Laboratory of National Defense for Science and Technology on Microsystem，Shanghai Institute of Microsystem and Information Technology，Chinese Academy of Sciences，Shanghai200050，China）

Unbalanced load of traditional Mobile Ad Hoc Network（MANET）results in bad consequences such as the increase of end-to-end delay，the decrease of delivery ratio and the death of nodes.In order to solve this problem，this paper proposes amodified load balancing routing algorithm based on Ad Hoc On-demand Distance Vector（AODV）.The algorithm adopts the single path method and considers both current load and occurred load.Queue lens and energy consumption of the nodes are used to evaluate the loads.The modified algorithm pays attention to the importance of the bottleneck nodes. Simulation results show that compared with the traditional algorithm such as AODV，improvement of energy path，this algorithm has good adaptability in different load cases，and can provide more stable network performance.

Mobile Ad Hoc Network（MANET）；queue waiting time；load balancing；routing algorithm；network delay

10.3969/j.issn.1000-3428.2015.11.025

陳昕韡，袁曉兵，李寶清.基于AODV的無線自組織網絡負載均衡路由算法［J］.計算機工程，2015，41（11）：142-146.

英文引用格式：Chen Xinwei，Yuan Xiaobing，Li Baoqing.Load Balancing Routing Algorithm Based on AODV for M bile Ad Hoc Network［J］.Computer Engineering，2015，41（11）：142-146.

1000-3428（2015）11-0142-05

A

TP391

國家部委基金資助項目。

陳昕韡（1990-），女，碩士研究生，主研方向：無線傳感器網絡；袁曉兵、李寶清，研究員。

2014-11-21

2014-12-17 E-m ail：xinw eichen08@163.com