基于回報加權的Ad Hoc預測路由協議的研究

李 晶 肖忠良 吳桂華

1(婁底市第一人民醫院 湖南 婁底 417000)2(婁底職業技術學院電子信息工程學院 湖南 婁底 417000)3(湖南電子科技職業學院 湖南 長沙 410205)

0 引 言

隨著無線通信技術的發展，可移動終端設備的應用場景越來越廣泛，人們對無線網絡提出了更高的要求[1]。移動Ad Hoc網絡是由一組帶無線收發功能的移動終端設備組成的自組織無線網絡[2]。與傳統的有基站的網絡不同，Ad Hoc網絡沒有固定的基礎設施，無須設置任何中心控制節點，且由于每個節點都是移動的，因此Ad Hoc支持無基站的快速組網和網絡恢復，特別適用于動態網絡拓撲結構中的無線數據傳輸[3]。

Ad Hoc網絡是一種不依賴任何固定網絡設施就能快速布設的自組織網絡技術，具有獨立組網能力自組織特點[4]。每個節點都是動態地保持與其他節點的聯系。無線Ad Hoc網絡的任意某個節點A與另一個節點B在進行數據的分組傳輸，當目的節點B不在節點A的無線頻率覆蓋范圍時，它們可以通過一個或多個中間節點轉發報文進行通信[5]。每個節點都可以提供到其他節點的路由發現以及路由維持功能[6]。

由于Ad Hoc網絡中的節點處于移動中，隨著節點的移動，網絡拓撲結構在不斷變化，斷鏈容易頻繁發生，節點之間的連通性也會快速變化[7]。確保動態環境下兩個節點之間高質量高效率的通信是移動Ad Hoc網絡應用中的一個挑戰，其中路由協議的設計目前仍然是Ad Hoc網絡研究的熱點和難點[8]。

1 相關研究

針對移動Ad Hoc網絡的路由協議已經有了很多研究。在眾多的路由協議中，無線自組網按需平面距離向量路由協議 (Ad hoc On-Demand Distance Vector Routing, AODV)是一種典型的反應式路由協議，是移動Ad Hoc網絡中按需生成路由的典型協議，節點不需要維護及時準確的路由信息，當需要發送數據時才發起路由查找過程，更能適應Ad Hoc網絡的特點[9]。但由于它僅以最小跳數作為路由選擇的依據，容易導致網絡資源分配不均，鏈路經常中斷，節點通信過程中數據丟包嚴重[10]。

近幾年，國內外許多研究者針對標準AODV協議在移動Ad Hoc網絡中的應用[11]做了大量的研究與改進。文獻[12]在MANET的應用場景中提出了一種M-AODV協議，在路由不能維持當前通信時，該協議從源節點開始路由重建的操作，在特定條件下，能獲得比原始AODV路由協議更好的性能；文獻[13]提出了一種基于AODV的能量感知路由協議，該協議將轉發決策與中間節點的節點能量閾值相結合，并基于最小能量算法進行路由，以增加網絡的生命周期，但該路由協議未充分考慮網絡的動態性；文獻[14]提出了基于網格的多路徑路由方案，找出所有可能的路徑，再利用海豚回聲定位算法(Dolphin Echolocation Algorithm，DEA)找到最佳路徑；文獻[15]提出的基于模糊神經網絡的穩定AODV協議改進方案，綜合考慮節點穩定度、鏈路穩定性與跳數，選擇穩定且跳數較小的路徑。以上對AODV協議的研究與改進，在一定程度上改善了Ad Hoc網絡的性能。但這些對路由協議的研究中，一部分協議會較早地建立起備用路由，無法保證啟用備用路由時的路由質量，還有一部分在當前通信路由中斷之后再啟動路由的重建機制，在路由中斷到路由重建完成的這段時間里，源節點和目的節點之間無法進行數據包的傳輸，極大地降低了網絡的吞吐量，增加了數據包傳輸的延時。

路由的斷開和路由的重建是影響Ad Hoc網絡性能的關鍵因素[16]，本文提出一種基于回報加權的預測路由協議(Calculation-AODV, CAODV)。以標準AODV協議為基礎，利用hello消息機制，周期性地計算自身的穩定值，預測通信路由的可靠性。在路由發現的過程中，避免使用不可靠的節點，在路由維護過程中，發現不可靠節點，及時啟動路由的重建機制，提高通信的效率。

2 預測路由模型

2.1 信號功率強度

用集合V={v1,v2,…,vN}表示Ad Hoc網絡某個地理區域中的N個無線節點。兩個處在彼此通信范圍內的節點vi、vj，vi，vj∈V，vj節點為vi的鄰居節點，當網絡中的節點移動時，節點之間的距離會變化。對于網絡中的每一個節點，利用無線信號傳輸模型來計算信號功率強度值。假設節點之間的距離為d，接收信號功率值pij可以表述為：

(1)

式中：pi,j為節點vi接收鄰居節點vj的信號功率；pj為鄰居節點vj的發射功率；Gj為發射天線增益；Gi為接收天線增益；λ為波長，單位為m；d為節點vi與鄰居節點vj之間的距離，單位為m；L為與傳播無關的損耗(傳輸線衰減、濾波損耗、天線損耗)。功率與增益的單位都為W。

2.2 路由可靠性維護

Ad Hoc網絡中的節點具有自主性和移動性，有路由器的功能，因此，Ad Hoc網絡中的每個節點都能發現和維護到其他節點的路由。針對Ad Hoc網絡節點位置不固定，通信鏈路容易斷開的特點，在傳統的AODV路由協議的基礎上，綜合物理層、MAC層和網絡層，提出一種預測路由機制。周期性評估節點的穩定性，判斷通信鏈路的傳輸性能，為通信節點是否需要更新路由提供依據。

建立如圖1所示的基于回報加權的路由預測模型。節點之間的相對運動可以分為相向運動和背向運動，根據節點的相對運動定義節點的相對穩定性。Ad Hoc網絡中的節點，通過hello消息周期性地進行信息的交互，假設通信中的節點根據hello消息感知下一跳節點的距離變化和信號強度變化，根據定義的節點相對穩定性，通信節點獲取下一跳節點的穩定值，預測當前路由的可靠性，判斷路由重建的時機。Ad Hoc網絡中的無線通信節點根據預測的結果決定是否更新路由。

圖1 預測路由模型

2.3 路由重建時機的判定

Ad Hoc網絡中節點的移動性會引起網絡拓撲結構的動態變化。標準的AODV協議只維持一條源節點到目的節點之間的路由，若在通信路由發生中斷后節點再啟動路由的重建，此時通信已經中斷，新路由的建立需要一定時間，會降低系統的吞吐量，也會降低數據傳輸的及時性。但是，若在不必要的時候引入備用路由，會增加系統的開銷，增加網絡復雜度，降低系統的效率，且Ad Hoc網絡的拓撲結構不固定，隨著節點的移動，在通信路由中斷而啟用備用路由時，備用路由的可用性變得不可知。選擇合適的時機建立新的路由顯得尤為重要。綜合考慮上述問題，改進了標準AODV協議，提出了一種根據節點的相對運動方式定義節點穩定性的方法，給出判斷啟動路由重建的信號感知判據，在預測到通信路由不穩定時，發出路由重建的信號，以避免增大通信時延和增加系統開銷。圖2為t時刻節點vi周圍的網絡拓撲結構，其中：虛線的圓形區域為節點vi的最大傳輸范圍，傳輸半徑為R，在此范圍之內的圓點表示節點vi的鄰居節點；實線的圓形區域為節點vi的可靠傳輸范圍，在此區域之內的圓點表示節點vi相對可靠的鄰居節點，可靠傳輸半徑為r。

圖2 節點相對穩定性示意圖

經過時間T，節點vi的鄰居節點vj的可能運動方向有四種。當節點vj運動到節點vi的可靠傳輸范圍以外，并且經過時間周期T接收到的信號功率強度與t時間接收到的數據包功率強度相比已經減小時，可以預測網絡[17]中兩個節點正超出彼此的無線信號范圍，鏈路斷開的可能性增大。

四種運動形式如圖3所示，在圖3(a)中，節點vj相對于節點vi最不穩定，如果節點vi與節點vj之間當前正在傳輸數據，則通信中斷的可能性較大。

圖3 節點相對運動示意圖

(2)

根據式(1)，式(2)可變換如下：

(3)

式中：d表示節點vj與節點vi之間的距離；dt代表t時刻vj與vi之間的距離；dt+T代表t+T時刻vj與vi之間的距離；r代表可靠傳輸半徑；任何時刻節點之間相對穩定性均有str(i,j)∈[0, 1]。

當節點vj運動到節點vi的可靠傳輸半徑r之外，即d≥1且str(i,j)<1時，則可以認為鄰居節點vj的信號強度正逐漸減弱，穩定性不能滿足需求，在這種情況下，若節點vi正在通信的路由節點集合B={v1,v2,…,vK}包含鄰居節點vj，則認為路由B已經不可靠，隨時可能中斷通信。

當路由建立成功之后，節點會利用有效的路由進行通信。同時，節點與鄰居節點之間會利用hello消息周期性計算str值。在檢測到通信節點不穩定時，重新啟動路由發現過程。

如圖4所示，節點v21和v22都屬于通信鏈路中的節點，且v22是v21的鄰居節點。在鄰居節點信息交換的過程中，如果v21發現與鄰居節點v22的傳輸距離大于可靠傳輸半徑且穩定值小于1，此時，可以認為路由vs-v21-v22-vd已不可靠，需要立即啟動路由重建機制，在新路由建立成功后，立即將通信鏈路切換到新路由。

圖4 Ad Hoc網絡的路由重建

3 基于回報加權的預測路由機制

3.1 回報權重值函數

3.1.1潛能值Rs

在Ad Hoc網絡中，數據的傳輸是節點能量消耗主要原因。潛能函數R主要考慮傳輸的能耗，定義接收(發送)單位數據所需能量為en，解碼(編碼)單位數據所需能耗為em，則接收轉發lbit數據包消耗的能量為：

E=2l(en+em)

(4)

在Ad Hoc網絡中，若節點vs選擇路由C中的節點作為新的路由，則潛能值可計算如下：

(5)

式中：Ei為Ad Hoc網絡中，路由C中的節點vi的剩余能量；ξC表示路由C包含的節點集合。

3.1.2節點可信度

對于新路徑選擇的可信度評估值為傳輸距離。如圖5所示，假設節點之間的相對距離與網絡中的實際距離成正比且節點的響應時間相同，可以很明顯看出，路徑s1：vs-v31-v32-vd比路徑s2：vs-v41-v42-v43-vd短，如果vs同時通過路徑s1、s2向節點vd發送信息，由于s1的傳輸距離短，則經由s1路徑的信息很可能比s2先達到目的節點vd，即s1比s2可信度更高。

圖5 可選路由的可信度模型

用Fs,d,C表示節點vs與節點vd之間活躍路徑集合C中的節點距離之和，則節點vs的路徑C的可信度Fs,d,C計算如下(考慮響應時間)：

(6)

考慮到一些關鍵任務的重要度，引入權重因子α來表示每一種資源的重要度。節點vs與節點vd的路由C的回報值JC計算如下：

(7)

由于Ad Hoc網絡中的節點的位置和狀態處于動態變化中，對于給定的可靠傳輸半徑r，當節點vj超出節點vi的可靠傳輸距離且穩定值str<1時，則啟動節點vs到vd之間路由的重建機制，根據回報權重值挑選出最佳路徑，立即更新路由。因此，在預測到通信路由中有即將失效或者傳輸性能不能滿足需求的節點時，都要對其他活躍路徑集合的狀態進行實時的評估，在通信中斷之前放棄舊路由，啟用新路由。

3.2 路由協議的改進

在標準AODV路由協議基礎上進行改進，過程如下：

(1) 節點的鄰居信息表增加兩個字段：與鄰居節點的當前通信距離，鄰居節點穩定值。字段里的數值將根據hello消息的發送周期性地更新。路由應答(RouteReply, RREP)包增加兩個字段，即節點剩余能量值和當前節點與下一跳節點之間的距離，用于源節點選擇回報值最大的路徑發送數據。增加一個WARNING警告信息，信息中包含節點的IP地址，當節點不穩定時，會發送WARNING信息給源節點，啟動路由重建。

(2)在路由發現過程中，對于超出節點可靠傳輸距離且穩定值小于1的節點，可以認為是不穩定的節點。

路由發現開始時，源節點會發送RREP包，發起到目的節點的路由發現過程，中間節點接收到RREP包后，會通過當前通信距離與穩定值判斷與上一跳節點之間的穩定性，如果中間節點認為自身相對于上一跳節點不穩定，則將RREP包直接丟棄，如果中間節點認為自身穩定性較好，則進行相應的轉發。與傳統的AODV不同，節點會綜合自身的回報加權值和接收到的RREP包中的參數，計算出新的值取代RREP包中原有的回報加權值，再將數據包轉發出去，完成路由的回報值計算。

目的節點對于接收到的多條路徑的RREP數據包，選取回報值較高的路由發出RREP數據包進行應答。

算法的部分偽代碼如下：

set radiusThreshold=220;

while receive a packet

do

if transrange > radiusThreshold

then

if strengthvalue < 1

then

update. stabilitylist ( );

droppacket ( );

end

else

update. stabilitylist ( );

sendpacket ( );

end

(3) 在路由維護過程中，隨著通信的進行，當正在通信路由中，有節點發現下一跳節點變得不穩定，會立即給源節點發送一個WARNING信息，源節點收到WARNING信息后，會啟動路由重建，選擇回報值最大的路徑作為新路由，當新路由建立好之后，立即將通信切換到新路由。

算法的部分偽代碼如下：

set radiusThreshold=220;

while receive a packet

do

if transrange > radiusThreshold

then

if strengthvalue < 1

then

send WARNING to source;

rebuild ( link.reward ( ) ) ；

end

else

as before;

end

在路由發現和路由維護的過程中，改進的協議沿用了AODV的hello消息機制，交換節點之間的信息用于判斷鄰居節點的穩定性以及WARNING消息發送的時機，相對于標準的AODV協議，并不會增加系統的時間復雜度和空間復雜度。

4 仿真及性能分析

為了能夠全面分析基于回報加權的預測路由協議的性能，本文通過對標準的AODV協議進行改進，利用NS-2[18]搭建了一個平面網狀結構的Ad Hoc網絡，對提出的路由協議進行性能評估。Ad Hoc網絡中的每一個節點既可以充當路由器，又可以充當終端節點。我們為每個節點添加了鄰居節點狀態表，該表用于節點記錄鄰居節點接收hello消息的功率值以及功率差。

在NS-2仿真平臺下，對AODV協議、M-AODV協議和CAODV協議進行仿真實驗。Pt、Gt、Gr、ht、ht、L采用仿真平臺默認值，即Pt=0.281 838 15 W，傳輸范圍為250 m，可靠傳輸半徑為220 m，接收功率閾值為3.652e-10 W，Gt和Gr均為1，ht和ht為1.5 m，L=1。仿真區域為1 000 m×1 000 m，移動模型采用隨機移動模型(Random Way Point, RWP)，節點采用全向天線(Omni Antenna),數據源采用恒定比特率(Constant Bit Rate, CBR)。移動仿真參數如表1所示。

表1 仿真參數設置

將AODV、M-AODV、CAODV的性能在由50個和100個節點組成的仿真網絡拓撲環境中進行對比，對仿真結果進行比較和評價。

在20 s、30 s、40 s、50 s的仿真時間點，獲取網絡的數據傳輸比率。如圖6所示，CAODV協議的數據傳輸比率比AODV協議增加了7%左右，比M-AODV協議增加了5%左右。如圖7所示，CAODV協議的數據傳輸比率比AODV協議增加了9%左右，比M-AODV協議增加了5%左右。對比圖6和圖7，當仿真節點個數由50個增加到100個時，網絡整體的數據傳輸比率都有一定程度下降，但在仿真節點個數相同的場景下，CAODV協議的數據傳輸比率優于其他兩種協議，能有效降低斷鏈發生的概率。

圖6 50個節點仿真的數據傳輸比率

圖7 100個節點仿真的數據傳輸比率

如圖8所示，CAODV協議的網絡吞吐量比AODV協議和M-AODV協議增加了9%左右。如圖9所示，CAODV協議在20 s到30 s之間，出現吞吐量下降的情況，但隨著仿真時間的推進，CAODV協議的網絡吞吐量高于其他兩種路由協議，CAODV協議的網絡吞吐量比AODV協議和M-AODV協議增加了10%左右。

圖8 50個節點仿真的網絡吞吐量

圖9 100個節點仿真的網絡吞吐量

在100個節點的仿真場景中，每個節點的初始能量為10 J。如圖10所示，從第15 s開始，部分節點會因為能量的消耗而變成無效節點。由于CAODV協議考慮了節點的能耗比和可信度，較好地均衡了網絡負載，使用CAODV協議仿真時，節點的消亡速度較緩慢，能更好地延長網絡的生存時間。

圖10 網絡存活節點數量

從圖11中可以看出，CAODV協議的平均端到端延時整體優于其他兩種協議，這是因為CAODV針對Ad Hoc網絡的動態性，采用預測路由的方法。當感知到通信路由不穩定時，啟動路由重建，實現新舊路由的實時切換，有效地降低了通信時延。

圖11 平均端到端時延

5 結 語

設計一種預測路由模型，提出基于回報加權的預測路由協議CAODV。仿真結果表明，CAODV協議能降低斷鏈發生的概率，有效地提升數據傳輸比率和網絡吞吐量，提升網絡通信質量,從而為Ad Hoc網絡的實際應用提供有效的通信支撐。