基于AODV的無線自組織網(wǎng)絡(luò)負(fù)載均衡路由算法

陳昕韡，袁曉兵，李寶清

（中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所微系統(tǒng)技術(shù)國防科技重點(diǎn)實(shí)驗(yàn)室，上海200050）

基于AODV的無線自組織網(wǎng)絡(luò)負(fù)載均衡路由算法

陳昕韡，袁曉兵，李寶清

（中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所微系統(tǒng)技術(shù)國防科技重點(diǎn)實(shí)驗(yàn)室，上海200050）

傳統(tǒng)無線自組織網(wǎng)絡(luò)的負(fù)載不均，導(dǎo)致端到端時(shí)延增大、傳輸比下降、節(jié)點(diǎn)大量死亡等問題。為此，以無線自組織網(wǎng)絡(luò)按需距離矢量（AODV）路由協(xié)議為基礎(chǔ)，提出一種改進(jìn)的負(fù)載均衡算法。采用單路徑負(fù)載均衡方法，考慮節(jié)點(diǎn)的即時(shí)負(fù)載和過往負(fù)載，使用節(jié)點(diǎn)緩沖區(qū)的隊(duì)列長度、節(jié)點(diǎn)剩余能量等指標(biāo)反映節(jié)點(diǎn)的負(fù)載情況，并關(guān)注瓶頸處的關(guān)鍵節(jié)點(diǎn)對網(wǎng)絡(luò)性能的影響。仿真結(jié)果表明，與AODV、改進(jìn)能量路徑等傳統(tǒng)算法相比，該算法在不同負(fù)載情況下的適應(yīng)性較好，能提供較為穩(wěn)定的網(wǎng)絡(luò)性能。

無線自組織網(wǎng)絡(luò)；排隊(duì)等待時(shí)間；負(fù)載均衡；路由算法；網(wǎng)絡(luò)時(shí)延

1 概述

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

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

2 改進(jìn)的負(fù)載均衡路由算法

網(wǎng)絡(luò)中的負(fù)載可以從2個(gè)方面進(jìn)行分析：即時(shí)負(fù)載和過往負(fù)載。即時(shí)負(fù)載反映了節(jié)點(diǎn)當(dāng)前的負(fù)載情況。例如，當(dāng)節(jié)點(diǎn)的緩沖隊(duì)列較長，說明節(jié)點(diǎn)當(dāng)前的負(fù)載較重，較多的分組經(jīng)由該節(jié)點(diǎn)轉(zhuǎn)發(fā)，緩沖區(qū)內(nèi)的分組將經(jīng)歷較長的等待時(shí)延，甚至被丟棄，節(jié)點(diǎn)的能量也將被迅速消耗。過往負(fù)載反映了自網(wǎng)絡(luò)開始運(yùn)行至當(dāng)前時(shí)刻節(jié)點(diǎn)所承擔(dān)的負(fù)載。某個(gè)節(jié)點(diǎn)可能當(dāng)前的即時(shí)負(fù)載不大，但是在過去曾經(jīng)承擔(dān)大量的轉(zhuǎn)發(fā)任務(wù)，消耗了大量的能量。此時(shí)如果讓該節(jié)點(diǎn)繼續(xù)承擔(dān)較多的轉(zhuǎn)發(fā)任務(wù)，則容易導(dǎo)致節(jié)點(diǎn)的死亡。節(jié)點(diǎn)的剩余能量是反映節(jié)點(diǎn)過往負(fù)載的較好指標(biāo)，剩余能量較小說明節(jié)點(diǎn)在過去承擔(dān)的負(fù)載較重，之后應(yīng)該盡量減小該節(jié)點(diǎn)的負(fù)載。因此，在改進(jìn)中將綜合考慮即時(shí)負(fù)載和過往負(fù)載這2種負(fù)載的均衡。

2.1 節(jié)點(diǎn)即時(shí)負(fù)載

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

2.2 節(jié)點(diǎn)過往負(fù)載

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

2.3 算法改進(jìn)

改進(jìn)的算法綜合考慮節(jié)點(diǎn)的即時(shí)負(fù)載和過往負(fù)載，路由表更新過程如圖1所示。

圖1 路由表更新過程

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

3 仿真場景與評價(jià)準(zhǔn)則

3.1 仿真場景與參數(shù)

使用NS2軟件進(jìn)行仿真。仿真場景及參數(shù)如表1所示。節(jié)點(diǎn)的移動(dòng)場景使用NS2軟件內(nèi)置的setdest工具自動(dòng)生成。使用CBR流，用NS2軟件中的cbrgen.tcl生成。使用cbrgen工具時(shí)采用的種子數(shù)分別取1 500，2 000，2 500，仿真結(jié)果是這3種情況下結(jié)果的平均值。

表1 仿真參數(shù)設(shè)置

3.2 評價(jià)準(zhǔn)則

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

其中，ratio為傳輸比；ns為成功傳輸?shù)姆纸M數(shù)；nt為發(fā)送的總分組數(shù)；delay為端到端時(shí)延；ti為第i個(gè)分組的傳輸時(shí)延；pi為第i個(gè)分組；sucess為成功傳輸?shù)姆纸M集合。

能量有效性指標(biāo)主要包括分組平均能耗、節(jié)點(diǎn)死亡數(shù)、網(wǎng)絡(luò)生存時(shí)間。其中，網(wǎng)絡(luò)生存時(shí)間通常以第一個(gè)死亡節(jié)點(diǎn)的死亡時(shí)間來表示。分組平均能耗如式（3）所示。

其中，ep為分組平均能耗；et為網(wǎng)絡(luò)總能耗。

由于負(fù)載不均主要導(dǎo)致網(wǎng)絡(luò)的吞吐能力下降、時(shí)延增大、節(jié)點(diǎn)過早死亡等，因此傳輸比、端到端時(shí)延、分組平均能耗、節(jié)點(diǎn)死亡數(shù)、網(wǎng)絡(luò)生存時(shí)間這些指標(biāo)對于評價(jià)負(fù)載均衡路由算法的性能具有重要的意義［12］。

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

4 結(jié)果分析

4.1 仿真結(jié)果

在節(jié)點(diǎn)最大速度為20 m/s，連接數(shù)為60的情況下對4種算法進(jìn)行仿真。成功傳輸分組數(shù)隨時(shí)間的變化如圖2所示。

圖2 成功傳輸分組數(shù)隨時(shí)間的變化

隊(duì)列虛擬呼叫準(zhǔn)入算法使用了2個(gè)不同的閾值，分別為緩沖區(qū)的9/10和1/2。

從圖中可以看出，負(fù)載均衡算法成功傳輸?shù)姆纸M數(shù)最多，較AODV算法和能量路徑算法，性能有了很大的提高。而隊(duì)列虛擬呼叫準(zhǔn)入算法受閾值的影響較大，當(dāng)閾值選擇較好時(shí)，網(wǎng)絡(luò)中成功傳輸?shù)姆纸M數(shù)較大，但是當(dāng)閾值選擇不當(dāng)時(shí)，性能較差。

AODV、負(fù)載均衡算法、能量路徑算法、隊(duì)列虛擬呼叫準(zhǔn)入算法（9/10）的時(shí)延分別為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。平均死亡節(jié)點(diǎn)數(shù)分別為1.33，0.67，2.67，5。第一個(gè)死亡節(jié)點(diǎn)的死亡時(shí)間均為100 s。改進(jìn)能量路徑算法的時(shí)延最小，但是傳輸比也是最低的，并且節(jié)點(diǎn)死亡數(shù)量最多。因此，該算法是犧牲了其他性能來實(shí)現(xiàn)網(wǎng)絡(luò)傳輸時(shí)延性能的提高。而本文提出的負(fù)載均衡算法的綜合效果最好。具有較小的網(wǎng)絡(luò)傳輸時(shí)延，最大的傳輸比，最低的節(jié)點(diǎn)死亡數(shù)量，每個(gè)分組消耗的能量也最少。

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

圖3 端到端時(shí)延與連接數(shù)的變化

圖4 傳輸比與連接數(shù)的變化

死亡節(jié)點(diǎn)數(shù)隨連接數(shù)的變化如圖5所示。本文的改進(jìn)算法在不同的連接數(shù)下均能保持較小的節(jié)點(diǎn)死亡數(shù)量，具有較好的性能。

圖5 死亡節(jié)點(diǎn)數(shù)與連接數(shù)的變化

4.2 參數(shù)敏感度分析

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

表2 寬松因子ε敏感度

表3 隊(duì)列長度閾值th敏感度

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

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

5 結(jié)束語

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

［1］ 姚忠邦，曹志剛.移動(dòng)Ad Hoc網(wǎng)絡(luò)中的負(fù)載均衡路由算法［J］.電訊技術(shù)，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，F(xiàn)rikha M，Hamouda M B.Load-balancing in MANET Shortest-path Routing Protocols［J］.Ad Hoc Networks，2009，7（2）：431-442.

［6］ 王莎莎，朱國暉，王 鑫.Ad Hoc網(wǎng)絡(luò)負(fù)載均衡路由協(xié)議研究［J］.現(xiàn)代電子技術(shù)，2013，35（3）：40-46.

［7］ 賈站峰.Ad Hoc網(wǎng)絡(luò)按需路由算法優(yōu)化研究［D］.哈爾濱：哈爾濱工程大學(xué)，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］ 鄭相全，郭 偉.自組網(wǎng)中的負(fù)載均衡路由協(xié)議［J］.計(jì)算機(jī)科學(xué)，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的無線自組織網(wǎng)絡(luò)負(fù)載均衡路由算法［J］.計(jì)算機(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

國家部委基金資助項(xiàng)目。

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

2014-11-21

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