無人機自組網(wǎng)中AODV路由協(xié)議的改進

梁 青, 張文飛, 上官藝偉, 熊 偉

(1.西安郵電大學 電子工程學院， 陜西 西安 710121； 2.西京學院 信息工程學院， 陜西 西安 710123)

由車載自組網(wǎng)[1-2]發(fā)展而來的無人機自組網(wǎng)[3]，通過動態(tài)組網(wǎng)方式完成無人機之間的通信，具有高動態(tài)拓撲、自組織、無中心以及多跳性等特點[4-5]，但鏈路容易斷裂，難以滿足軍用無人機[6]對網(wǎng)絡性能的要求。采用AODV路由協(xié)議[7-8]的無人機自組網(wǎng)，受節(jié)點移動速度和能量[9]的局限，易發(fā)生鏈路中斷，且鏈路生存期限低，丟包率嚴重[10]。

針對無人機自組織網(wǎng)絡路由問題，已有不少改進措施?；谀芰扛倪M型的AODV-E路由協(xié)議[11]選擇跳數(shù)少、節(jié)點能量高的鏈路進行數(shù)據(jù)傳輸，以避免斷裂問題，但沒有從根本上降低節(jié)點能量的耗費?；谡J知的AODV路由協(xié)議[12]選擇平均鄰居節(jié)點數(shù)多的鏈路發(fā)送數(shù)據(jù)，以提高鏈路修復的成功率，但增加了存儲空間?；诰植柯酚尚迯偷腁ODV路由協(xié)議[13]采用兩跳本地修復機制，以節(jié)約資源和減少端到端的時延，但鏈路的修復方式受斷裂位置的限制，且修復速度慢。這些改進措施主要針對節(jié)點移動速度低的網(wǎng)絡，不適用于移動速度快的無人機自組網(wǎng)。為最大程度地延長鏈路的生命周期，在綜合考慮各種因素的同時，利用鄰居節(jié)點的特性改進鏈路的修復很必要。

本文針對節(jié)點間能耗大、鏈路連接不穩(wěn)定和鏈路維護效率低等問題，擬給出一種新的改進型AODV(I_AODV)路由協(xié)議，綜合考慮路由開銷、平均鄰節(jié)點數(shù)量及鏈路失效時間這三個因素[14-15]，以建立穩(wěn)定的鏈路，并在鏈路斷裂時，通過斷裂處上下游節(jié)點能量最高的共同鄰居節(jié)點進行鏈路的快速修復，使其更好地適應高速變動的網(wǎng)絡環(huán)境。

1 AODV協(xié)議

1.1 AODV路由協(xié)議

AODV路由協(xié)議是一種按需式路由協(xié)議，綜合了目的節(jié)點序列距離矢量(destination sequenced distance vector，DSDV) 路由協(xié)議、動態(tài)源路由 (dynamic source routing，DSR) 協(xié)議的優(yōu)點[16]，不僅按照DSDV協(xié)議為每個節(jié)點維護了一個單調(diào)遞增的計數(shù)器，以更新路由緩存中相關項目，可以更有效地利用網(wǎng)絡中的帶寬資源，防止產(chǎn)生環(huán)路，還根據(jù)DSR形成了鏈路發(fā)現(xiàn)和鏈路維護過程，通過路由表象的動態(tài)建立，使節(jié)點可以維護最新的路由信息。

AODV路由協(xié)議的控制消息包括路由請求(route request，RREQ)、路由回復(route reply，RREP)和路由錯誤(route error，RERR)等。

1.2 鏈路發(fā)現(xiàn)

當源節(jié)點需要發(fā)送數(shù)據(jù)到目標節(jié)點時，先檢查路由表是否有到目標節(jié)點的鏈路，若有到目標節(jié)點的鏈路，直接發(fā)送數(shù)據(jù)；否則，廣播路由請求，建立到達目標節(jié)點的鏈路，并建立反向鏈路。目標節(jié)點或者含有到目標節(jié)點路徑的中間節(jié)點收到路由請求，沿著反向鏈路發(fā)送路由回復；同時，建立正向路徑，源節(jié)點收到路由回復，會沿著此鏈路發(fā)送數(shù)據(jù)。

1.3 鏈路維護

活動路由上的節(jié)點會周期性地廣播消息“HELLO”給鄰節(jié)點，以判斷鏈路的連接狀況。若某節(jié)點發(fā)送“HELLO”后，在設定時間內(nèi)未收到任何鄰居節(jié)點廣播消息“HELLO”，說明此條鏈路已斷裂。節(jié)點斷裂處距目標節(jié)點近，則啟用本地修復機制進行修復；在設定的時間內(nèi)本地修復不成功，或斷裂處距源節(jié)點近，斷裂處上游節(jié)點會發(fā)送消息“RERR”給源節(jié)點，重新建立鏈路。

1.4 AODV路由協(xié)議缺點分析

AODV路由協(xié)議在建立鏈路的過程中，由于網(wǎng)絡中節(jié)點的移動性和能量的消耗，兩節(jié)點間已建立的鏈路易斷裂，鏈路的生存時間短。中間節(jié)點和目的節(jié)點僅對第一次收到的RREQ做出反應，以建立反向鏈路和發(fā)送RREP，造成大量RREQ不能得到充分利用，極大地浪費資源。

節(jié)點的路由表中維護了一條到達目的節(jié)點的鏈路，當鏈路發(fā)生斷裂時，只能依據(jù)斷裂處距目的節(jié)點的距離進行本地修復或發(fā)送RERR給源節(jié)點，重新建立鏈路。鏈路頻繁斷裂，導致RREQ的廣播量和傳輸延時大，且斷裂處上游節(jié)點緩存數(shù)據(jù)包的壓力大，數(shù)據(jù)包丟失的概率較大。

2 改進的AODV路由協(xié)議

鏈路發(fā)現(xiàn)階段：綜合考慮路由消耗、節(jié)點間鏈路失效時間及節(jié)點的鄰居節(jié)點數(shù)建立穩(wěn)定的鏈路。目的節(jié)點后續(xù)收到RREQ，不再簡單地丟棄。

鏈路維護階段：根據(jù)鄰居節(jié)點的特性，通過斷裂處上下游節(jié)點的共同鄰居節(jié)點對鏈路進行快速修復。

2.1 鏈路權值計算

無人機自組網(wǎng)中鏈路的穩(wěn)定性受多種因素的影響。無人機節(jié)點的移動速度較快，且每個節(jié)點負載及耗能狀況不同，各個節(jié)點間鏈路的穩(wěn)定性也不同，所以建立一條穩(wěn)定且維持時間較長的鏈路比較困難，且斷裂鏈路重建概率不高。在通信時選擇路由開銷小，節(jié)點間鏈路失效時間長的路由，可以提高鏈路的穩(wěn)定性，延長網(wǎng)絡的壽命。鄰居節(jié)點數(shù)量，在一定程度上反映了網(wǎng)絡的狀況，可以充分利用路由開銷、節(jié)點間鏈路失效時間及節(jié)點的平均鄰居節(jié)點數(shù)等信息設計路由算法。

將最優(yōu)路由選擇問題轉化為路由開銷C、節(jié)的平均鄰居節(jié)點數(shù)N和鏈路失效時間T最優(yōu)的問題，具體是路由開銷小，節(jié)點的平均鄰居節(jié)點數(shù)多和鏈路失效時間長。

為了方便計算，將上述3個條件轉化為權值計算，表示為

(1)

路由開銷越小，節(jié)點的鄰居節(jié)點數(shù)越多，節(jié)點間鏈路維持的時間越長，選擇的鏈路越穩(wěn)定，協(xié)議對動態(tài)網(wǎng)絡的適應能力越強，所以,權值越小建立的鏈路越穩(wěn)定。

(1) 路由開銷

網(wǎng)絡中鏈路上節(jié)點能量的大小及能量消耗的快慢對鏈路質(zhì)量起著決定性作用，鏈路越短，緩沖數(shù)據(jù)包越少，節(jié)點能量消耗越小，數(shù)據(jù)傳輸時延越小，所以，路由開銷可用公式表示為

(2)

其中，hc表示跳數(shù)，q表示鏈路中節(jié)點緩存數(shù)據(jù)包的最大數(shù)目，e表示鏈路中節(jié)點剩余的最小能量值，由式(2)知，路由開銷越小，鏈路的生存時間越長。

(2) 平均鄰居節(jié)點數(shù)

節(jié)點的鄰居節(jié)點數(shù)可以反映出網(wǎng)絡的狀態(tài)信息，節(jié)點的鄰居節(jié)點數(shù)越多，鏈路斷裂時，鏈路重建概率越高。通過平均鄰居節(jié)點數(shù)來判斷鏈路的整體狀態(tài)。所以，平均鄰居節(jié)點數(shù)可以表示為

(3)

其中，NT表示源節(jié)點到當前節(jié)點的所有鄰居節(jié)點數(shù)之和，hc表示節(jié)點轉發(fā)的跳數(shù)。由式(3)知，平均鄰居節(jié)點數(shù)越多，鏈路斷裂時修復成功的概率越大。

(3) 節(jié)點間鏈路失效時間

由于節(jié)點的移動速度快，導致節(jié)點間鏈路不穩(wěn)定，所以，鏈路上節(jié)點間鏈路失效時間是必須考慮的因素。節(jié)點間鏈路失效時間是通過節(jié)點位置及其移動速度計算得出的(通過GPS定位系統(tǒng)獲得節(jié)點的位置和移動速度)。表示為

(4)

其中

a=V1cosθ1-V2cosθ2,b=Xm-Xx,c=V1sinθ1-V2sinθ2,d=Ym-Yx。

(Xm,Ym)為節(jié)點m的坐標，(Xx,Yx)為節(jié)點x的坐標。V1為節(jié)點m的速度，V2為節(jié)點x的速度，θ1為節(jié)點m的方向角，θ2為節(jié)點x的方向角。由式(4)知，鏈路失效時間的值越大，說明鏈路越穩(wěn)定，維持的時間越長。

2.2 鏈路發(fā)現(xiàn)機制

源節(jié)點需要給目的節(jié)點發(fā)送數(shù)據(jù)時，源節(jié)點沒有到目標節(jié)點的路由，就會廣播RREQ進行鏈路建立。RREQ中記錄著節(jié)點的跳數(shù)，節(jié)點剩余能量、鄰居節(jié)點總數(shù)和鏈路中節(jié)點緩存數(shù)據(jù)包的數(shù)目以及計算出的路由開銷、平均鄰居節(jié)點數(shù)、鏈路失效時間的值。建立鏈路時，RREQ每轉發(fā)一次，其數(shù)據(jù)包中的變量會相應更新。

中間節(jié)點收到RREQ，根據(jù)路由表及鄰居列表中維護的相關信息計算并更新路由開銷、平均鄰居節(jié)點數(shù)及鏈路失效時間的值，同時計算權值。

目標節(jié)點或含有目標節(jié)點的中間節(jié)點收到RREQ后，選擇權值最小的鏈路回復RREP，源節(jié)點收到RREP后，沿此鏈路發(fā)送數(shù)據(jù)。之后目標節(jié)點收到RREQ，判斷其權值是否小于已回復給源節(jié)點的RREQ中的權值，若小于，則向源節(jié)點發(fā)送RREP，通知其切換鏈路，否則，直接丟棄。

路由發(fā)現(xiàn)流程如圖1所示。

圖1 路由發(fā)現(xiàn)流程

2.3 鏈路維護機制

由于節(jié)點的移動性及網(wǎng)絡拓撲變化性，活動路由上的節(jié)點會周期性發(fā)送消息“HELLO”檢測鏈路的連接狀況。如果節(jié)點在一定的時間內(nèi)未收到下游節(jié)點發(fā)送的消息，說明鏈路發(fā)生斷裂。斷裂處上游節(jié)點會緩存源節(jié)點發(fā)送的數(shù)據(jù)，尋找斷裂處上下游節(jié)點的共同鄰居節(jié)點重新建立鏈路，恢復數(shù)據(jù)的傳輸。

尋找斷裂處上下游節(jié)點的共同鄰居節(jié)點時，定義一個數(shù)組“common[ ]”來記錄所有共同鄰居節(jié)點。遍歷斷裂處上游節(jié)點的鄰居，如果其也存在于斷裂處下游節(jié)點的鄰居列表，說明該節(jié)點是斷裂處上下游節(jié)點的共同鄰居節(jié)點，將其存放到數(shù)組中。遍歷數(shù)組中的元素即可找到能量最大的共同鄰居節(jié)點。

I_AODV協(xié)議中引入了通知消息包，在本文中的應用是斷裂處上游節(jié)點B發(fā)送通知消息給斷裂處上下游節(jié)點的共同鄰居節(jié)點E，告知其目的節(jié)點是斷裂處下游節(jié)點C。鏈路修復過程如圖2所示。

圖2 鏈路修復

當鏈路正在傳輸數(shù)據(jù)時，節(jié)點B與節(jié)點C之間發(fā)生斷裂，會啟動鏈路修復機制，檢查節(jié)點C的能量，如果大于0，查找節(jié)點B和C能量最強的共同鄰居節(jié)點E來進行鏈路的重建。

鏈路建立的步驟如下。

(1)節(jié)點B通過查看自己鄰居列表的信息，找到所有的鄰居節(jié)點。

(2)遍歷節(jié)點B的所有鄰居節(jié)點，若節(jié)點B的鄰居節(jié)點同時也是節(jié)點C的鄰居節(jié)點，說明該節(jié)點是節(jié)點B和C的共同鄰居節(jié)點，將其存放在數(shù)組“common[ ]”中。

(3)遍歷數(shù)組中的節(jié)點，找出能量最強的節(jié)點，即節(jié)點B和C能量最強的共同鄰居節(jié)點E。

(4)節(jié)點B查看自身路由表，是否存在與節(jié)點E之間的路由。若存在，節(jié)點B先發(fā)送通知消息給節(jié)點E，告知其目的節(jié)點是節(jié)點C，然后發(fā)送數(shù)據(jù)給節(jié)點E；若不存在，直接建立節(jié)點B到節(jié)點E之間路由，因為節(jié)點E是節(jié)點B的鄰居節(jié)點，節(jié)點B的鄰居列表中含有節(jié)點E的信息，故可直接建立節(jié)點B與節(jié)點E之間的路由。節(jié)點B發(fā)送通知消息給節(jié)點E，告知其目的節(jié)點是節(jié)點C，然后發(fā)送數(shù)據(jù)給節(jié)點E。

(5)當節(jié)點E收到通知消息時，查看其路由表，是否有到節(jié)點C的路由。 若存在，節(jié)點E直接發(fā)送數(shù)據(jù)給節(jié)點C，節(jié)點C繼續(xù)傳輸，直至到達目的節(jié)點；若不存在，節(jié)點E建立到節(jié)點C的路由,然后發(fā)送數(shù)據(jù)給節(jié)點C，直至發(fā)送到目的節(jié)點。

若斷裂處上下游節(jié)點的共同鄰居節(jié)點不存在或者共同鄰居節(jié)點存在但能量為0，或斷裂處下游節(jié)點能量為0，依據(jù)斷裂處距離目的節(jié)點的距離，進行原始本地修復或者發(fā)送RERR消息給源節(jié)點，重新建立鏈路。

I_AODV路由協(xié)議鏈路修復的流程如圖3所示。

圖3 I_AODV路由協(xié)議鏈路修復流程

節(jié)點B與節(jié)點E之間鏈路一旦建立，節(jié)點B就會發(fā)送數(shù)據(jù)給節(jié)點E,以緩解節(jié)點B緩存數(shù)據(jù)的壓力，降低節(jié)點B的消耗，同時也可降低丟包率。

如圖2所示，I_AODV協(xié)議的鏈路修復時間為t1+t2,而AODV協(xié)議的鏈路修復時間為t1+t2+t3+t4，可知I_AODV協(xié)議縮短了鏈路修復時間。此外，如果節(jié)點A和B之間發(fā)生斷裂，則AODV協(xié)議不能進行鏈路修復，只能發(fā)送RERR消息重新建立鏈路，而I_AODV協(xié)議仍可進行鏈路修復?？梢姡琁_AODV協(xié)議鏈路修復方法不受鏈路斷裂位置限制，且所建鏈路上節(jié)點的鄰居節(jié)點數(shù)多，斷裂鏈路修復的概率較高，數(shù)據(jù)傳輸延時小。

3 仿真與分析

利用在16.04版Ubuntu下安裝的ns-2.35對AODV、I_AODV協(xié)議進行仿真。仿真的環(huán)境為1 km ×1 km的矩形區(qū)域，隨機產(chǎn)生為50個節(jié)點，節(jié)點的能量為40 J，仿真時間為200 s，傳輸距離為250 m，發(fā)送速率為1 包/s，最大連接數(shù)為30個，傳輸功率為0.660 W，接收功率為0.035 W，隨機中子數(shù)為1，節(jié)點的傳輸模型為TwoRayGround。對節(jié)點速度為10～100 m/s區(qū)域內(nèi)的節(jié)點的丟包率、端到端的延時、節(jié)點平均剩余能量及路由發(fā)現(xiàn)頻率進行仿真，使用trace文件記錄仿真數(shù)據(jù)，用awk程序提取和處理數(shù)據(jù)，使用gnuplot工具畫圖分析。

仿真主要從不同節(jié)點速度下對丟包率、端到端的時延、節(jié)點平均剩余能量及路由發(fā)現(xiàn)頻率等4個方面評價兩種協(xié)議的性能。兩種協(xié)議在不同速度下的性能對比結果如圖4所示。

由圖4(a)可知，隨著節(jié)點速度的增大丟包率也隨之變高。相同速度下I_AODV路由協(xié)議低于AODV協(xié)議的丟包率。其原因在于，I_AODV建立的鏈路更穩(wěn)定，降低了鏈路斷裂的幾率，且鏈路斷裂時修復的速度更快。

由圖4(b)可見，隨著速度的加快，節(jié)點端到端的延時也隨著變大，相同速度下I_AODV路由協(xié)議低于AODV端到端的延時。這是因為，I_AODV路由協(xié)議建立的鏈路穩(wěn)定，不易斷裂，且斷裂鏈路的修復速度快。即使斷裂處距離源節(jié)點近，也不發(fā)送RERR消息重建鏈路而是進行鏈路修復，減少了大量延時。

由圖4(c)可知，隨著速度的增大，節(jié)點的平均剩余能量隨著減小，I_AODV路由協(xié)議的節(jié)點平均剩余能量大。這是由于，改進后的路由協(xié)議所建鏈路性能更穩(wěn)定，路由開銷小，且斷裂鏈路修復時，斷裂處上下游節(jié)點的共同鄰居節(jié)點可以分擔斷裂處上游節(jié)點緩存的數(shù)據(jù)包，降低了節(jié)點的消耗。

由圖4(d)可知，I_AODV路由協(xié)議路由發(fā)現(xiàn)頻率低于AODV協(xié)議。這是因為，鏈路建立時考慮鄰居節(jié)點數(shù)、路由開銷及鏈路失效時間，所建鏈路比較穩(wěn)定，而且，斷裂鏈路的修復不受鏈路斷裂位置的限制，鏈路修復時不需要廣播路由請求消息。

圖4 協(xié)議改進前后不同速度下的性能對比

4 結語

針對無人機自組網(wǎng)不穩(wěn)定的問題，提出新的I_AODV協(xié)議算法。在鏈路建立的過程中，綜合路由開銷，節(jié)點的平均鄰居節(jié)點數(shù)以及鏈路失效時間來建立穩(wěn)定的鏈路，且在鏈路斷裂時由斷裂處上下游節(jié)點與其能量最大的共同鄰居節(jié)點快速建立鏈路進行修復，不受鏈路斷裂位置的限制，且鏈路修復速度快。仿真表明，在端到端的時延、丟包率、節(jié)點平均剩余能量及路由發(fā)現(xiàn)頻率方面均優(yōu)于原始AODV；與原始AODV協(xié)議相比，有效的改善了鏈路的穩(wěn)定性，降低了節(jié)點的能量耗費，增加了節(jié)點的生存時間，延長了網(wǎng)絡的生存周期。但是，還需要進一步增強鏈路的穩(wěn)定性，以適應節(jié)點速度更快的網(wǎng)絡環(huán)境。