基于代價函數的改進AODV協議

邱夢華　羅喜伶

摘 要： Ad Hoc網絡中如何設計良好的路由協議使其網絡均衡是當今研究的重點。針對網絡負載和能量均衡等問題，提出了一種基于代價函數的改進按需距離矢量路由協議CF?AODV。該協議在路由建立過程中，通過能量閾值和緩存隊列長度閾值進行RREQ轉發判斷；在目的節點選取路由時采用延遲應答方案，通過以路徑長短、路徑負載、路徑剩余能量作為因子的代價函數進行判決來選取最佳路徑。仿真結果表明，所提協議在網絡負載和能量上得到了均衡，可以延長網絡壽命，減輕網絡擁塞，減少時延和丟包率。

關鍵詞： Ad Hoc； AODV路由協議； 代價函數； 負載； 剩余能量

中圖分類號： TN915.04 ?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2015）05?0009?05

Improved AODV protocol based on cost function

QIU Meng?hua， LUO Xi?ling

（Beihang University， Beijing 100191， China）

Abstract： In Ad Hoc Network， how to design a good routing protocol to make network balancing is the focus of todays research. For network balancing issues of load and energy， an improved demand distance vector routing protocol CF?AODV based on cost function is proposed. The protocol is used to do RREQ forwarding judgment by energy threshold and buffer queue length threshold in the establishing routing process. The delayed response program is used when the destination node selects route. By taking length， load and residual energy of path as cost functions of factor， adjustment for optimal routing selection is made. Si?mulation results show that the proposed protocol can make the network balance on load and energy， extend the network lifetime， reduce network congestion， latency and packet loss rate.

Keywords： Ad Hoc； AODV routing protocol； cost function； load； residual energy

0 引 言

為了解決動態自組網和無法依靠基礎設施等問題，提出了Ad Hoc解決方案。移動Ad Hoc網絡是一種復雜的分布式網絡系統，是自組織、自愈網絡；無線移動節點可以動態的自組織成任意臨時性的網絡拓撲，從而允許人們和裝置在沒有預先存在的通信基礎設施的環境中進行無縫的互聯互通[1]。根據Ad Hoc雙重功能節點、無中心自組織、能量和帶寬有限等特點，設計良好的路由協議滿足其動態變化的拓撲結構是當今研究的重點和難點。

Ad Hoc路由協議根據網絡節點獲取路由信息方法可分為表驅動路由協議（主動式路由協議）、按需驅動路由協議和混合路由協議三種。AODV[2]是經典按需距離矢量路由協議，包括路由建立和路由維護兩個過程。優點在于能快速自適應動態鏈路狀況，處理開銷和存儲開銷低等，但是由于需要臨時建立路徑，會增大時延，路由請求較多時易造成廣播風暴。目前AODV協議研究和改進主要在負載均衡、能量均衡、鏈路修復以及安全保障等方面，但是各種算法并不能同時在多方面顯著改善協議性能。如何合理有效地選取中間方案，實現AODV協議各方面的均衡優化是當前研究的一個重點。

本文綜合考慮了網絡負載均衡和節點剩余能量，提出了基于代價函數的CF?AODV協議。對代價函數進行分析，闡述了CF?AODV協議的基本算法；構建仿真場景，進行了結果分析。

1 相關研究

1.1 負載

按需驅動路由協議在不頻繁進行路由發現時，網絡中控制分組較少，整個網絡的負擔較輕；但是如果網絡中拓撲變化較快，路由信息跟著不斷的變化，網絡的負擔就會加重。如果網絡中選取路由時沒有考慮到節點的負載情況，網絡流量不均衡，會導致重負載節點出現，增加時延和丟包率。為了解決以上問題，關于負載均衡的路由協議應運而生。常見的判斷節點負載的方法有：基于本地信息的、基于流的、基于時延的、基于傳輸速率的負載感知路由協議。在Ad Hoc網絡中，節點負載反映該節點的繁忙程度，較重時可能導致包阻塞，使得端到端延時長，丟包率增大，通信鏈路的傳輸保障降低。

LWR[3]是基于本地信息的負載感知路由協議。該算法根據節點的負載情況判斷對請求報文應采取的操作，其中節點的負載情況由信道使用率、隊列長度、活動鄰居節點數和退避定時器的值決定。MAC層接口等待隊列緩存的數據包是經過過濾后由于競爭機制而未發出的數據包，可以準確實時地體現節點當前的擁塞程度。此方法能較準確地得出節點某時刻的流量，但是選取的參數太多，可能在接收RRRQ到發送RREQ期間內并不能全部得到，從而造成丟包。LBAR[4]是基于流的負載感知路由協議。該協議將經過節點和鄰居節點的路由數作為負載，在路由尋找過程中統計總負載，選取最小的總負載路由。此做法可以預測節點的流量，但是并不能體現出節點當時擁塞程度。

1.2 節點剩余能量

Ad Hoc網絡節點的能量通常是有限的，如果網絡中的某些節點能量快速耗盡，有可能使得源節點不能以較短的路徑到達目的節點，增大了數據傳輸時間以及丟包率等。MTPR[5]以路徑節點傳輸總能量的消耗最小為主，但沒有考慮節點剩余能量，容易造成網絡分割。MMBCR[6]克服MTPR的缺點，卻忽略了跳數、延遲等因素，不能保證鏈路總體能量的消耗是最小的。MRL[7]路由算法提出在節點剩余能量基礎上，考慮節點能量消耗速率，選擇生存時間較長的路由，但是也未能考慮到節點負載和延遲等因素。

1.3 代價函數分析

基于以上分析，本文在路由建立過程中，關于負載和能量的工作主要包括如下：

（1） 節點的負載主要依據經過該節點、其鄰居節點的活動總路由數和活動的鄰居節點數來決定。

（2） 設定負載閾值L0和能量閾值E0。節點收到RREQ時讀取MAC層接口緩存隊列長度L和節點剩余能量E。若L超過L0，將其視為重負載節點，丟棄收到的請求報文，不考慮其為中間節點； 若E小于E0，則丟棄收到的請求報文。

（3） 在RREQ消息和路由表中加入路徑負載總和和負載最大值這兩項；每次轉發控制消息時，將該節點的負載值與接收的控制消息的負載值相加，更新負載最大值，進行轉發控制消息。

在路由選取時，本文采用目的節點延遲應答方案，從所有路徑中根據代價函數選出最佳路徑。代價函數的因子包括路徑長短、路徑負載、路徑剩余能量，如下：

[C=w1i=1N-1di-i+1+w2i=2N-1LOADi+w31i=2N-1Pi] （1）

式中：N為所選路徑的節點總數；[di-i+1]為兩節點之間的距離；[LOADi]為節點i的負載；[Pi]為節點i的剩余能量；wi為各項的權值。

剩余節點能量則根據節點的剩余電池量得到。節點負載大小采用公式（2）計算：

[LOADi=0.5×rt_live_numberrt_all_number+0.5×NEAR_nodesN_nodes] （2）

式中：rt_live_number為節點當前活動路由數目；rt_all_ number為經過該節點和其鄰居節點的路由數總數；NEAR_nodes為鄰居活動節點數；N_nodes為節點總數。

rt_live_number與rt_all_number比值可以體現該節點與其鄰居節點的業務繁忙情況；NEAR_nodes與N_nodes比值直接說明了該節點是否處于密集區，同時可間接預測該節點隨著時間變化的流量。

在目的節點進行路由選取的時候，本文以代價函數最小化為原則。[wi]為可調參數，決定鏈路中各因子所占比例，根據實際情況進行取值。當節點剩余能量越多，[1Pi]越小，且負載越小，則C越小，路徑選取可能性越大。根據代價函數，路由選取過程中可選取一條路徑較短，節點剩余能量較多，預測流量較小的路由，從理論上分析改進協議可以延長網絡壽命，減少時延，降低丟包率。

2 CF?AODV算法實現

2.1 擴展CF?AODV協議消息

（1） RREQ消息的擴展如表1所示。

路由請求識別碼是一個序列號，與源節點IP地址惟一確定一條路由；目的節點序列號為源節點接收到的，到達目的節點的最新序列號；源節點序列號則是源節點正在使用的路由條目中的當前序列號。跳數為從源節點開始達到本節點之間的轉發跳數。在此基礎上，本文在RREQ中新添加節點負載最大值LOADmax、路徑負載總和LOAD?sum、節點剩余能量最小值[Emin]和路徑剩余能量總和Energy?sum字段，其余不變。

（2） 路由表的擴展如表2所示。

每個節點維護一張AODV路由表，該表包括很多個路由條目，每條路由條目都包含：目的節點IP地址、目的節點序列號、目的節點序列號有效標志、其他狀態標志、網絡接口、到達目的節點跳數、下一跳節點IP、預發送節點列表、壽命（本條路由生存時間）等。網絡接口為接收分組的無線接口；預發送節點列表里面存儲這個節點作為中間節點時的所有上個節點的IP地址。本文在路由表中新添加LOADmax_rt和Emin_rt，用以存儲到本節點所經過的所有節點的最大負載和最小剩余能量。

2.2 路由發現過程

如果源目節點間沒有活動路由時，啟動路由發現過程，廣播RREQ消息。在協議實行過程中，每個節點實時監控自身的MAC層接口隊列長度和節點剩余能量。

在圖1所示的網絡拓撲中，存在10個中間節點，每個節點的剩余能量、負載、活動路由數如表3所示，設定能量閾值E0=0.05，L0=50。每個節點的鄰居節點由其通信半徑R確定，在R內的為鄰居節點。路由發現過程如下：

（1） 源節點S到目的節點d之間沒有活動路由，S發動路由請求過程，向外廣播發送RREQ。節點2收到RREQ，計算LOAD、LOAD?sum和Energy?sum，更新RREQ，向外廣播。

（2） 源節點S丟棄收到的節點2轉發的自己廣播的RREQ消息；節點3能量小于閾值E0，丟棄節點2發送的包；節點1、4更新RREQ，繼續廣播，但節點1的全部鄰居節點都已經接收到相同序列號的RREQ消息，所以節點1沒有下一跳節點。此時節點4轉播的RREQ：LOADmax=0.35，Emin=0.45，LOAD?sum=0.68，Energy?sum=1.20。

（3） 節點6的接口緩存隊列長度大于L0，丟棄接收到的包；節點5繼續廣播更新后的RREQ。此時節點5轉發的RREQ：LOADmax=0.49，Emin=0.45，LOAD?sum=1.15，Energy?sum=1.90。

（4） 節點7、8接收節點5發送的消息，更新RREQ，繼續廣播RREQ。

節點7轉發的RREQ：LOADmax=0.49，Emin=0.45，LOAD?sum=1.44，Energy?sum=2.35；

節點8轉發的RREQ：LOADmax=0.49，Emin=0.45，LOAD?sum=1.47，Energy?sum=2.55。

（5） 節點9、10繼續廣播RREQ，目的節點收到來自源節點發送的RREQ，緩存兩條路由。

節點9轉發的RREQ：LOADmax=0.49，Emin=0.45，LOAD?sum=1.82，Energy?sum=2.85；

節點10轉發的RREQ：LOADmax=0.49，Emin=0.45，LOAD?sum=1.85，Energy?sum=3.25。

根據以上分析，節點收到RREQ時的處理流程如下：

Begin

讀取E（i）、MAC層接口緩存隊列長度L（i）、路由表中路由數、路由表中鄰居節點數和其對應的路由數量

if（E（i）L0）

丟棄該RREQ，返回；

else

{尋找到源節點的反向路由；

if（未找到反向路由）

建立反向路由；

if（RREQ_ID>路由表中存儲或LOADmax_rt < LOADmax或 Emin_rt

更新路由表相關項；

if（本機是目的節點）

緩存該RREQ；

else{

if（存在到目的節點的路由）

發送RREP；

else{

計算LOAD（i）；

If（LOAD（i）>LOADmax） LOADmax = LOAD（i）；

If（E（i）< Emin） Emin = E（i）；

LOAD_sum=LOAD_sum+LOAD（i）；

Energy_sum=Energy_sum+ E（i）；

轉發該RREQ；

}

}

}

2.3 路由選擇過程

目的節點采用延遲應答方案，接收第一個相同序列號的RREQ消息時啟動一個計時器，負責記錄當前時間。時間達到后，向源節點發送RREP消息。在這段時間內，到達的RREQ消息存儲在目的節點緩存項中，每個消息對應一條路由。在圖1所示拓撲中，目的節點緩存項中存在兩條路由，即：

路徑1：S→2→4→5→7→9→d；

路徑2：S→2→4→5→8→10→d；

在代價函數公式中，令[w1]=[w2=13，][di-i+1]為跳數，兩條路徑都為6跳。將剩余能量總和歸一化處理，令[w3=63，]則路徑1中，C=3.31；路徑2中，C=3.23。根據代價函數取小值，選擇路徑2作為最優路徑。

根據以上分析，設[Si]表示從源節點到目的節點的所有可能路由，i=1，2，3，[…]；路由選擇算法程序如下：

Begin

For（緩存中的每一個RREQ消息）

{A=Hop Count的最小值；}

For（緩存中的每一個RREQ消息）

{if（Hop Count>=A且Hop Count<=A+3）

該RREQ消息放入集合G1；}

For（G1中的RREQ消息）

{根據代價函數計算Ci，則Min（Ci）；

將Ci最小的RREQ放入集合G2；}

If（G2只有一個）

發送RREP消息；

Else

{比較Emin，選取Emin最大的RREQ消息；

If（只有一個）發送RREP；

Else

{比較Loadmax，選取最小值；

發送RREP消息；}

}

3 實驗仿真與結果分析

本文在Matlab平臺上對CF?AODV協議進行仿真。整個網絡的工作機制如下：通過設置50個網絡節點，在1 000[×]2 000的場景中，進行節點隨機坐標的分布，設置整個網絡的仿真時間（輪數）為200輪；不同節點之間信息傳遞的信道模型根據節點距離選擇Free space[8]和Two?ray ground reflection[9]；路由協議設置AODV和AODV改進兩種類型。參數設置完成后整個網絡按輪數開始運作，每一輪將剩余的節點數隨機排列組合配對，按照不同的協議生成相應的路徑，并開始發送數據。每個節點的能量消耗根據能量損耗模型計算，負載按照公式（2）計算，節點當前活動路由數為該輪中該節點所在路徑的總數。期間，路徑搜索時節點的能量和負載實時變化。每一輪結束后，該輪的所有路徑清空，下一輪重新統計。在仿真時間結束后，得到某個時刻路徑顯示、網絡能耗、死亡節點數、標準化路由載荷、無效路由數等指標。

本文節點能量損耗模型[10]采用傳感器能量消耗模型，且僅考慮消耗能量較大的無線通信模塊，該模塊如圖2所示。

節點傳輸m b信息，傳送距離為d時的能耗如下所示：

發送端能量消耗模型：

[ET（m，d）=mEelec+mεfsd2，ddc] （3）

接收端能量消耗模型：

[ER（m）=mEelec] （4）

式中：[Eelec]為單位比特數據電路耗能；[εfs]和[εtgr]為放大器傳輸單位比特數據耗能大小。其中[dc]為無線信道傳輸模型自由空間模型（Free Space）、雙徑地面反射模型（Two?ray Ground Reflection）的分界點。距離小于[dc]時使用自由空間模型，反之使用雙徑傳播模型。[dc]計算式為：

[dc=sqrtεfsεtgr] （5）

整個網絡的仿真參數設置如表4所示。

圖3比較了兩個路由協議的死亡節點數。死亡節點數為每輪結束后，從網絡開始運行到該輪的全部能量為0的節點數量。剛開始時由于節點初始能量和負載一樣，兩種協議選擇的路徑基本一樣，所以節點死亡速率也基本一樣；隨著仿真時間的推移，到某個時間點時，死亡節點數突增，節點死亡速率兩者都增大，但是從圖中可看出CF?AODV增長速率明顯小于AODV，突增時間點也比AODV延后。這是因為CF?AODV在路徑選擇時首先進行了閾值判斷，使得網絡內RREQ消息廣播數量比AODV少，節點消耗能量也減少；其次考慮了路徑剩余能量和總負載，選擇了路徑剩余能量較高，負載較小的路徑，避免了部分節點因為成為較多路徑中間節點而能量損耗迅速，造成網絡分割的情況發生，使整個網絡的能量消耗比較均勻，延長了網絡的生存時間。

圖4比較了兩種算法在不同時刻的標準化路由[1]。標準化路由載荷即每交付給目的節點一個數據分組所需要發送的路由分組的數量，作為評價路由的效率。路由載荷低，網絡擁塞減輕。路由分組每當被傳輸一跳，則計算一次路由分組發送。從圖4中可看出，在網絡中剩余節點數差別不大的情況下，CF?AODV協議的標準化路由載荷相對于AODV來說較少，這是因為在路徑選取過程中通過閾值的判斷，減少了廣播RREQ消息的數量，減輕了網絡的負擔。

4 結 論

本文提出了一種基于代價函數的AODV路由協議。在轉發RREQ時通過設置能量閾值和緩存隊列閾值，來選擇剩余能量較高和當前擁塞程度較低的節點來保障鏈路的有效性，避免節點過早死亡而造成斷路；同時減少控制信息的廣播，避免廣播風暴，減輕網絡擁塞。目的節點采用延時應答方案，根據代價函數的值來選取一條能量、負載均衡的最佳路由，使整個網絡消耗能量更為平均，同時避免部分節點任務過重，提高整個網絡的性能。仿真結果表明，CF?AODV能延長網絡壽命，改善網絡擁塞。

參考文獻

[1] 陳林星，曾曦，曹毅.移動Ad Hoc網絡?自組織分組無線網絡技術[M].北京：電子工業出版社，2006.

[2] PERKINS C， ROYER E. Ad?Hoc on demand distance vector routing [C]// Proceedings of IEEE WMCSA. New Orleans： IEEE， 1999： 90?100.

[3] YI Y， KWON T J， GERLA M. A load aware routing （LWR） based on local information [C]// Proceeding of the 12th IEEE International Symposium on Personal， Indoor and Mobile Radio Communications. San Diego， CA： IEEE， 2001： 65?69.

[4] ZHOU A， HASSANEIN H. Load ? balanced wireless ad hoc routing [C]// Canadian Conference on Electrical and Computer Engineering. Canada： [s.n.]， 2001， 2： 1157?1161.

[5] SCOTT K， BAMBOS N. Routing and channel assignment for low power transmission in PCS [C]// Proceeding of the 5th IEEE International Conference on Universal Personal Communications. Cambridge： IEEE， 1996： 498?502.

[6] SINGH S， WOO M， RAGHAVENDRA C S. Power?aware rou?ting in mobile Ad Hoc networks[C]// Proceeding of the 4th annual ACM/IEEE international conference on mobile computing and networking. Dallas： [s.n.]， 1998： 181?190.

[7] 劉大偉，金偉，王曉潔.一種節能的Ad Hoc網絡路由協議[J].計算機工程與應用，2011（26）：93?94.

[8] 張力軍，張宗橙，鄭寶玉.數字通信[M].4版.北京：電子工業出版社，2003.

[9] RAPPAPORT T S. Wireless communications： principles and practice [M]. New Jersey： Prentic Hall PTR， 1996：40?60.

[10] 張偉偉.無線傳感器網絡仿真平臺的設計與實現[D].合肥：中國科學技術大學，2009.