基于能量均衡和擁塞程度的改進AODV路由協議

陳書旺,宋樹麗,宋彤彤,王真真,尹曉偉,黃 濤

(1.河北科技大學信息科學與工程學院，石家莊 050000；2.河北科技大學教務處，石家莊 050000)

無線自組網(wireless Ad Hoc network)是由一組移動節點動態形成的網絡，以無線鏈路的方式進行數據傳輸，且不需基礎設施的臨時性網絡[1]。并且具有無中心性、拓撲動態性、抗毀性等特點。主要應用在軍事和民用方面，尤其是應用在通信設施資源匱乏的場合中。而自組網節點進行通信的前提是路由協議，因此路由協議成為目前自組網體系結構中的熱門研究對象。中外的一些學者提出了許多路由協議標準，路由協議的性能不同導致所適用的環境不同。根據路由發現策略的不同分為兩類：①反應式表驅動路由協議，如DSDV(destination sequenced distance vector routing)、WRP(wireless routing protocol)等；②反應式按需基于源端路由協議，如DSR(dynamic source routing)[2]、AODV等[3]；其中表驅動路由協議需要周期性地廣播路由更新消息，這類路由協議需要較高的資源代價，路由成本大、能量利用率較低。而按需路由協議非常適用于自組網，不需要實時維護路由消息。可以節省網絡資源，提高能量利用率，減少擁塞，適應網絡的拓撲變化，延長網絡的生存時間。

AODV[4-5](Ad Hoc on demand distance vector routing)是一種典型的按需路由協議，包括路由發現和路由維護兩個階段。當源節點需要與目的節點建立通信鏈路時，首先要在通信范圍內廣播RREQ(routing request)，中間節點會根據是否是首次收到RREQ來決定是否轉發，目的節點收到RREQ后需要向源節點回復RREP(routing reply)。報文RREP會經過中間節點回到源節點，此時就建立了路由路徑。通信過程中在遇到鏈路中斷時AODV會發起本地路由修復進行維護。

相比于其他路由協議，AODV路由協議的只有在需要時才會發起路由尋找，這樣提高了網絡資源利用率，減少延遲。AODV路由協議能快速響應網路的拓撲變化，并且不會形成環路。由于人們對網絡性能的要求不斷提高，近年來許多學者對AODV路由協議在不同方面進行了優化。Ranjan等[6]提出了IOAS-AODV(improved optimum angle selection-AODV)一種新的路由算法，通過基于象限位置，電池狀態，隊列長度，選擇一組交替路徑的有限節點來避免擁塞和修復斷鏈。陸偉等[7]對于能量損耗提出了一種新的改進機制，構造了一種數學模型，其中包含節點的信號屬性。根據鏈路質量和能量的消耗情況來選擇路徑。此協議在通信中不僅能保證能量消耗最小還能選擇最優的路徑。何王吉等[8]提出了一種電量估算策略，將復合期望傳輸次數和節點的剩余能量作為路由度量。改進后的算法有效減少能量損耗,延長網絡生存時間。文獻[9]針對擁塞問題提出了一種新的機制，根據路由度量得到函數擬合曲線，根據擬合曲線來設定不同的閾值。由平均隊列與閾值的關系決定是否丟棄報文。這種新的機制在路由性能方面都優于傳統的AODV。李愛武等[10]對路由協議在擁塞方面進行了優化，在平均隊列的基礎上提出了動態檢測的方式，根據擁塞程度向相鄰節點發出信號，鄰居節點嘗試找出一條可替代的路徑來進行通信。這種改進的算法提高了路由協議的性能。文獻[11]針對擁塞提出了兩種優化協議：EDAODV(early detection congestion and control routing protocol)和AODV-I(improved Ad-Hoc on-demand distance vector routing protocol)，其中EDAODV采用雙向路徑發現，預先檢測擁塞，而AODV-I協議在RREQ中添加了擁塞處理，可以避免選擇忙路由，同時RREQ還添加了路由修復機制，這種改進使資源能充分利用。

自組網中由于每個無線節點的能量可用性有限，在通信過程中節點的能量會不斷減少直至耗盡，所以在數據轉發過程中考慮能量是非常必要的。而保證鏈路穩定傳輸就必須要考慮擁塞問題，擁塞的后果會導致數據丟失甚至網絡發生崩潰。因此路由度量的選擇對于通信質量至關重要。AODV路由協議只將跳數作為選擇路徑的標準，學者們在選擇路徑時只加入了能量或擁塞因素，這使得路徑的選擇變得局限。

基于以上的背景和分析，以AODV協議為基礎，將路徑擁塞和能量損耗同時考慮在內，并且將能量狀態和擁塞狀態分成不同的等級并用不同的跳數來表示。引入了跳數代價和路徑判斷因子，根據跳數代價和實際跳數得出每段路徑的總跳數，最后利用路徑判斷的公式將每段路徑的跳數累加得到最終的跳數，選擇跳數最少的路徑進行數據的傳輸。改進后的路由協議有效地減少網絡擁塞，減少延遲，提高節點的存活率。

1 改進的路由選擇算法的度量指標

1.1 擁塞度量——跳數

當鏈路發生擁塞時會造成丟包率增加、端到端時延增加、吞吐量下降等問題。用緩沖區占有率(buffer occupation rate,BOR)來衡量擁塞程度，緩存占用率表示：某一時間段此鏈路的隊列長度與鏈路最大可承載長度的比值。擁塞度(congestion degree,CD)的表示方法：

(1)

式(1)中：Lt為某一時間內鏈路的隊列長度；Lm表示鏈路最大可承載的長度。其中，Lt為一個不斷變化的值，Lm為一個定值。AODV協議中，路徑的選擇是以跳數的大小為標準。所以提出將擁塞以跳數的形式表示，引入一個擁塞因子C(hhops)。將擁塞度轉化為跳數分為以下三種情形。

(1)CD≤20%時，表示鏈路處于穩定的狀態，基本上不會發生擁塞，數據可以正常通信，此時跳數代價為0，即：

C(hhops)=0

(2)

(2)20%

C(hhops)=3

(3)

(3)CD≥60%時，數據緩沖區已經要達到飽和狀態，開始處于丟包階段，丟棄數據包，增加端到端的時間。此時的跳數代價為6，即：

C(hhops)=6

(4)

1.2 剩余能量——跳數

在復雜的網絡環境中，考慮能量因素是至關重要的，由于AODV的重傳次數增加，會引起網絡風暴，造成不必要的能量消耗。選擇剩余能量大的節點進行數據的接收和發送，可以延長網絡的生存時間。剩余能量等級表示為

(5)

式(5)中：Ei為節點i的剩余能量；Es為節點的初始能量。為了將能量以跳數的形式表示出來，引入一個能量因子E(hhops)。分以下四種情況討論。

(1)當Er≥0.5時，表明節點剩余大量能量，可以正常通信，接收和轉發數據。此時的跳數代價為0，即：

E(hhops)=0

(6)

(2)當0.2

E(hhops)=3

(7)

(3)當0.1≤Er≤0.2時，表明節點能量損耗大部分，所剩無幾了，為了在數據傳輸的時候盡量地減少時延，防止此類節點參與通信傳輸。跳數代價設為6，即：

E(hhops)=6

(8)

(4)當Er<0.1時，表明節點已經接近枯竭，只能作為目的節點來接收數據。

1.3 路徑判斷因子ω

在CE-AODV-H協議中，定義了判斷因子ω作為路由選擇的判定依據：

ω=ω0+ω1+…+ωi

(9)

式(9)中：ω0～ωi分別表示每段路徑的穩定判斷因子，ωi表示AODV路由在選擇路徑時的綜合考量，其表達式為

ωi=αC(hhops)+βE(hhops)+μhhops

(10)

式(10)中：α、β、μ為權重因子，均為小于1的正整數，且α+β+μ=1，可以根據自組網的具體應用場景來設定。根據式(9)計算最后的ω。選擇ω最小且目的節點序列號最新的鏈路進行通信。如果ω相同，選擇最先到達目的節點的鏈路。

2 最優路徑的發現和建立

(1)改進后的路由協議在路由表中增加了三個字段，CD、Er和ω。

(2)在路由請求RREQ中增加ω0字段。作為選擇路徑的依據。

(3)運行路由協議前對α、β、μ進行賦值。

2.1 路由發現

源節點需要向目的節點發送數據包時，首先要檢查路由表中是否有到達目的節點的的有效路由，如果沒有就執行路由發現過程，在發送數據前，計算的節點CD和Er算出ω0，填入RREQ報文中的ω0字段處。

2.2 中間節點對RREQ的處理

中間節點在接收到RREQ包時，首先建立一個用于記錄反向路徑的表項，先不分配有效序列號，如果是第一次收到RREQ首先要判斷節點剩余能量的等級Er。

(1)如果Er<0.1時，則直接丟棄該節點。

(2)如果能量-跳數代價為式(6)～式(8)情況下記錄此時的跳數，其次判斷擁塞度，并記錄此時的總跳數ωi。然后繼續RREQ的數據轉發。中間節點轉發流程圖如圖1所示。

圖1 中間節點轉發流程Fig.1 Intermediate node forwarding process

2.3 目的節點對RREQ的處理

為了選擇最優的路徑，目的節點同樣需要對路徑進行能量和擁塞的判斷，當RREQ到達目的節點后，設定等待時間的上限，超過等待時間，此時要更新該節點的路由表信息，根據路由表攜帶的跳數、擁塞、能量計算路徑的ωi，最后選擇ω最小的路徑進行RREP的轉發。

2.4 改進算法路徑選擇實現

圖2為改進算法的路徑選擇過程，將擁塞和能量考慮在內。從圖2中可以看出，從源節點S到目的節點D共有三條路徑，L1：S→A→B→D；L2：S→A→C→E→D；L3：S→F→G→D。由于此網絡對能量比較敏感，所以將β賦值為0.5，α設為0.2，μ為0.3。設定節點初始能量為100 J,鏈路最大可承受長度為50。某一時刻節點狀態：L1路徑：實際跳數為2，節點A的剩余能量為60 J，擁塞度為2/5，節點B的剩余能量為20 J，擁塞度為3/5。L2路徑：實際跳數為3，節點A的剩余能量為60 J，擁塞度為2/5，節點C的剩余能量為50 J，擁塞度為1/5，節點E的剩余能量為40 J，擁塞度為1/5。L3路徑：實際跳數為2，節點F的剩余能量為30 J，擁塞為2/5，節點G的剩余能量為9 J，擁塞為3/5。

圖2 路由建立過程Fig.2 Route establishment process

傳統的AODV會選擇L1I路徑或L3路徑，但將能量和擁塞考慮在內，在選擇路徑時，由于節點G的剩余能量等級Er<0.1,所以丟棄該節點，排除路徑L3。根據式(9)、式(10)計算鏈路的ω的值，得出路徑L2的ω大于路徑L3的ω。最終選擇L2路徑為最優路徑進行傳輸數據。

3 仿真與結果分析

使用仿真平臺為網絡仿真器NS2(network simulator-2,NS2.35)。仿真參數設置：①區域面積： 1 000 m×500 m；②節點移動速度：0～10 m/s；③模擬時間：100 s；④移動模型：隨機路點模型；⑤無線模型mac：802.11；⑥連接數：10；⑦數據包尺寸：512 B；⑧字節初始能量：100 J；⑨暫停時間：0、25、50、75、100 s。

衡量路由協議的標準為路由開銷、數據包投遞率、節點存活率和端到端時延。路由開銷指路由消息數與節點發送數據包的比值。反映了網絡的路由效率。數據包投遞率表示目的節點所接收的數據包與源節點發送的數據包之比，反映了網絡傳輸的可靠性。端到端時延即包的延時就是指包的接收時間與包的發送時間差。節點存活率指模擬時間結束所存活的節點與總節點數的比值。通過改變暫停時間來仿真AODV、CE-AODV-H和AODV-I路由協議。

圖3 端到端的時延Fig.3 End-to-end delay

圖3表明CE-AODV-H、AODV和AODV-I三種路由協議的端到端時延整體上隨著暫停時間的增大而減少，在暫停時間較小時，節點移動速度快，網絡拓撲結構變化迅速，節點的能量消耗快，鏈路隊列易發生擁塞。AODV-I路由協議只將擁塞考慮在內，在端到端時延方面由于AODV協議，而提出的路由協議中，選取剩余能量大的節點傳輸，控制隊列長度能有效地緩解擁塞，比AODV-I和AODV路由協議的時延都小。

圖4、圖5表明改進后的路由協議CE-AODV-H在數據包投遞率和路由開銷方面方面優于AODV和AODV-I路由協議，暫停時間增加，節點移動變慢，路由轉發次數減少，路由開銷也就減少，數據不易發生丟包，數據包投遞率增加，改進的協議引入了能量和擁塞的等級來選擇最短路徑，有效地提高了數據包投遞率。

圖4 數據包投遞率Fig.4 Packet delivery rate

圖5 路由開銷Fig.5 Routing overhead

圖6 節點存活率Fig.6 Node survival rate

圖6為在整個仿真時間內節點的存活情況，隨著暫停時間的不斷增加，節點的存活率也不斷增加。在仿真的過程中用跳數來表示能量的等級，剩余能量大，跳數代價小，參與通信時可以更好地避免節點死亡，因此相比于AODV和AODV-I路由協議，CE-SODV-H可以更好地提高節點的存活率。

4 結論

針對數據傳輸過程中能量消耗過大導致節點死亡、隊列長度過長導致擁塞，提出了CE-AODV-H改進路由協議，通過緩沖區占有率將擁塞分成不同的等級，同時將剩余能量也劃分等級，丟棄能量小的節點，不同的等級用不同的跳數代價表示。基于能量和擁塞跳數最小建立路由，同時還考慮了權重因子α、β、μ的配置問題，可以根據不同的場景靈活的配置，更好地滿足路由需求。仿真結果表明，CE-AODV-H路由協議相比于普通的AODV路由協議減少了路由開銷和端到端的時延，提高了數據包投遞率和節點的存活率。路由性能進一步得到了改善。