無人機自組網中改進型反應-貪婪-反應路由協議

梅家棟， 南建國

(空軍工程大學航空工程學院， 西安， 710038)

隨著電子技術、傳感器技術和通信技術的發展，無人機是執行情報、監視和偵察任務的空中傳感器平臺，開始具備武器打擊能力，在軍事領域中發揮著更大的作用[1-3]。通過建立無人機集群，可實現大量單無人機系統無法高效完成的任務[4]。無人機集群高效運轉的基礎是建立穩定可靠的通信網絡，保證無人機節點間的高效通信[5]。而移動自組織網絡具有無中心、組網高度靈活、拓撲動態可變、抗毀性強等特點，可有效滿足無人機集群組網通信的需求。無人機集群采用移動自組網的通信架構，形成了無人機自組網[6-7](flying Ad Hoc networks, FANETs)。由于無人機節點的高機動性，無人機自組網具有網絡拓撲變化劇烈，鏈路斷開頻繁等特點[8-9]。因此，設計能夠適應網絡環境高度動態變化的路由協議是一項重要研究課題[10]。

基于拓撲和基于地理位置信息是兩種重要的路由發現策略[11-12]，各有其優勢和局限性。若能將兩者有機結合，實現優勢互補，可有效提高路由協議的性能。文獻[13]提出了反應-貪婪-反應(reactive-greedy-reactive,RGR)路由協議，通過有效結合AODV和貪婪地理轉發策略(greedy geographic forwarding,GGF)，RGR路由協議能在高動態環境下具有較好的網絡性能。但RGR協議存在4個主要問題：①路由發現階段沿用AODV路由協議盲目洪泛RREQ消息的方式，網絡開銷大；②以最小跳數標準選擇路徑，沒有考慮節點的負載狀況，容易造成網絡中的“熱點”問題，當業務量大時，會產生較大的排隊時延，甚至出現緩存溢出丟棄數據分組的情況；③在切換到GGF模式進行數據傳輸時，將向前距離作為下一跳節點的選擇依據，忽略了無人機節點的高動態性以及節點的負載狀況；④節點的高機動性帶來鏈路斷開頻繁的問題，使得提高GGF模式分組轉發成功概率十分關鍵，RGR協議則未考慮這一問題。文獻[14]為降低路由開銷，提出了受限洪泛機制，同時為了提高對鏈路斷開的快速反應能力，引入了移動預測機制，一定程度上提高了網絡的性能。文獻[15]針對GGF模式失敗提出了3種解決方案，并未對提高GGF模式的成功轉發概率提出有效措施。文獻[16～17]提出了一種Improved-RGR路由協議及路徑請求延遲機制，降低了網絡的控制開銷，但是未考慮網絡中節點的負載均衡問題。GGF模式是本地修復的替換策略，文獻[18]針對AODV協議的本地修復存在的延遲問題，提出了一種自適應修復算法，有效改善了AODV路由協議的性能。

基于國內外的研究現狀及RGR協議存在的問題，本文提出了一種基于負載均衡和高GGF成功概率的改進RGR路由協議(load balancing and high GGF success probability-RGR,LBHGS-RGR)。

1 LBHGS-RGR路由協議

1.1 基于節點負載狀態和地理位置信息輔助的受限洪泛機制

在無人機自組網中，無人機節點移出通信范圍或發生擁塞都會導致鏈路發生中斷[19-21]，嚴重影響網絡性能。RGR協議在選擇路徑時，以最小跳數標準選擇路徑，沒有考慮節點的負載狀況，某些中間節點需要轉發大量數據，容易造成網絡中的“熱點”問題。如圖1所示，位于網絡中心的節點4和節點7在多條路徑中作為中間節點，承擔更多的分組轉發任務，負載較重。由于有限的鏈路帶寬和數據處理能力的限制，這類節點更易發生節點的擁塞。此外，RGR協議在進行路由發現時，沿用AODV協議向全網進行盲目洪泛的策略，會帶來大量的網絡開銷，導致節點緩存溢出和網絡擁塞，嚴重影響網絡的性能[22]。當網絡中節點數增多時，帶來的影響更加嚴重。

圖1 節點擁塞示意圖

1.1.1 節點負載狀態劃分

節點的負載通過MAC層隊列中的數據長度來度量，并將節點的負載狀態分為擁塞和正常[23]。通過計算緩存區的隊列長度與最大隊列長度的比值，確定負載狀態函數Li(t)：

(1)

式中：qi(t)為節點i在t時刻MAC層接口的隊列長度；qi max表示為節點i最大MAC層接口最大隊列長度。負載狀態函數會隨時間變化，可以通過采樣獲得觀測值的時間序列Li(k)。

通過比較負載狀態函數的數值與擁塞系數ρ大小，確定節點的負載狀態Mi，將負載狀態分為擁塞(congested)和正常(normal)：

(2)

Li為節點i的負載狀態函數，擁塞系數的大小取值為網絡的歸一化吞吐量的最大值Smax，具體的推導以及證明過程，可見參考文獻[23]。

1.1.2 受限洪泛具體實現過程

為了減少RREQ控制分組的數量，同時考慮節點的負載狀況，本文提出基于節點負載狀況和地理位置信息輔助的受限洪泛機制。在源節點發起路由請求時，處于擁塞狀態的中間節點不參與路由的建立過程，在接收到RREQ分組后直接丟棄，不參與轉發。而負載較輕的節點收到RREQ分組后，未處于擁塞狀態的節點同時滿足與目的節點之間的距離關系時，才能參與路由建立的洪泛過程。

在按需式路由完成初始化后，通過其建立過程，網絡中的節點獲得包括目的節點在內的路由建立相關節點的地理位置信息。同時，相鄰節點間在進行路由維護時，通過在HELLO消息中攜帶的地理位置信息，周期性更新相鄰節點的地理位置信息。在基于網絡中的節點可獲得目的節點的位置信息的前提下，源節點在進行路由發現時，在RREQ消息中添加距離目的節點的距離信息，并設置初始值為零。當源節點向鄰節點廣播RREQ分組后，中間節點接收RREQ分組處理流程圖如圖2所示。當網絡中的節點均未獲得目的節點的地理位置信息，則退化為盲目洪泛機制。

圖2 中間節點接收RREQ分組處理流程圖

1.2 GGF模式下高分組成功傳輸概率的路徑選擇策略

RGR路由協議沿用AODV協議路由建立時最小跳數的衡量標準，進行路徑選取。跳數最小也代表節點之間鏈路的平均距離最大，下一跳節點可能位于通信的邊界，會進一步增大了鏈路斷開的可能性。而提高鏈路斷開后的路由修復的成功概率，可以有效減少路由重啟的頻率，減小傳輸時延和網絡控制開銷，提高分組投遞率。

RGR路由協議采用貪婪地理轉發模式(GGF)，文獻[24]已經驗證過，在節點分布密集的條件下，采用GGF模式的成功概率很高?；诖耍谶M行按需式路由建立后的路徑選擇時，選擇節點的平均鄰居節點數最多的路徑。在RREQ消息中，添加link_number字段，用以存儲建立的路徑上節點鄰居數信息。當節點接收到RREQ消息后，通過查詢自身的鄰居節點列表，將鄰節點個數加到link_number值中，更新后繼續轉發RREQ消息。同時考慮到路徑中跳數會對傳輸時延的影響，采用路徑的平均鄰節點個數，作為路徑選擇的依據。目的節點在首次接收到RREQ消息后，對于后續規定時間內接收到的來自源節點的RREQ消息，并不是直接丟棄。在第一次接收到RREQ分組后，目的節點通過讀取link_number字段數值Nl及hop_count字段數值Kl，通過式(3)來計算對應路徑的平均鄰居節點個數NAl，并將其進行緩存。在后續接收到的RREQ消息中選擇具有最大的NAl的路徑，作為用于傳輸數據分組的反應式路徑：

(3)

1.3 基于節點負載預測和運動特征的分組轉發策略

1.3.1 GGF模式下的負載預測機制

為了避免GGF模式選擇的下一跳節點處于擁塞狀態，導致轉發失敗的情況，因此引入了負載預測機制。每間隔一個HELLO消息周期，節點在MAC層接口對自身的負載狀態進行采樣，獲得一組負載函數序列。利用采樣序列預測下一個HELLO到來時刻節點的負載狀況，并通過HELLO消息攜帶當前時刻的負載狀態觀測值和下一個周期的預測狀態廣播給其鄰居節點。通過交互HELLO消息后，可以獲得鄰居節點的負載狀態信息，并以此作為下一跳決策的依據，避免處于擁塞狀態的節點參與轉發。所以需要選擇合適的預測模型，實時、準確判斷節點是否處于擁塞狀態[25]。

ARIMA模型實現簡單、運算速度快、短期預測精度較高、時效性強，具有強線性預測的特點，但無法準確預測負載時間序列的非線性關系。小波神經網絡(wavelet neural network，WNN)有效結合了小波分析和神經網絡，對復雜非線性不確定系統具備較好的預測效果。因此，文中采用基于ARIMA-WNN組合預測模型，實現對節點負載狀態信息的預測。通過將負載狀態函數看作由線性部分和非線性部分組成，組合預測的步驟如下：

步驟1得到負載函數采樣序列后，通過差分法將非平穩的負載時間序列進行平穩化處理，通過建立ARIMA模型后，得到線性部分的預測值。負載時間序列的非線性特征通過將預測結果與原序列的殘差得到。ARIMA模型數學表達如式(4)所示：

(4)

步驟2將步驟1獲得的殘差值代入到WNN模型中，通過不斷修正神經元之間的連接權值和閾值，通過預測得到殘差的修正值，即為負載時間序列的非線性特征預測值。WNN模型描述如下：

圖3 WNN模型結構圖

圖3中隱含層節點的輸出為：

j=k,k+1,…,k-1+m

(5)

式中：fj(x)為小波基函數；aj、bj分別小波基函數的伸縮參數和平移參數；f(j)為第j個節點的輸出值。

隱含層選取Morlet函數作為激勵函數，其數學表達式為：

(6)

模型的輸出結果為：

(7)

步驟3通過將步驟1得到的線性部分的預測值和步驟2得到的非線性部分的預測值相加，得到下一時刻負載的預測值。

1.3.2 基于運動特征的分組轉發策略

當鏈路斷開時，RGR路由協議切換到貪婪地理向前轉發模式進行數據傳遞，通過選擇距離目的節點最近的鄰節點作為下一跳節點，以保證數據分組具有最大的向前距離。這種僅考慮節點間的距離關系的轉發策略適合于節點運動能力弱或基本靜止的網絡。對于無人機自組網，網絡中的節點具有高動態性，所以在進行轉發決策時，不僅要考慮到節點間的位置關系，還要考慮節點的運動特征。

如圖4所示，在直角坐標系中，節點j的坐標(xj,yj)，目的節點d的坐標為(xd,yd)，節點j是i的下一跳。節點j的運動速度為νj=vjcosθji+vjsinθjj，目的節點的運動速度為vd=vdcosθdi+vdsinθdj，式中vj和vd是節點j和的d的運動速率，θj和θd為節點j和節點d運動速度與x軸正向的夾角。

圖4 節點相對運動關系示意圖

可計算出節點j和節點d的相對運動速度為：

νjd=vj-νd

(8)

相對運動速率為

Δv=|vjd|=

(9)

節點j和d間的相對距離矢量為：

ljd=(xj-xd)i+(yj-yd)j

(10)

則相對距離為：

(11)

節點j和d的相對距離矢量與相對運動速度之間的夾角可表示為：

(12)

如圖4所示，節點d的通信半徑為R，則滿足節點j進入d通信范圍內，相對距離矢量與運動速度的最大夾角為：

(13)

定義進入目的節點通信范圍時間：

(14)

在選擇下一跳節點時，首先選取Te<0的節點，此時說明該節點已經處于目的節點的通信范圍內，對于Te>0的候選節點，選擇Te最小的節點，對于Te=0的節點則不做考慮，因為該節點背離目的節點運動。

當節點通過GGF模式找不到下一跳節點時，啟用SCF的路由機制，等待下一個HELLO周期再進行判斷。當處于低負載狀態的節點進入其通信范圍內或擁塞節點重新恢復為正常狀態時，轉發數據包。

2 實驗結果及分析

2.1 仿真環境設置

本文通過OPNET14.5網絡仿真軟件對LBHGS-RGR路由協議的性能，進行仿真驗證。比較對象選取AODV協議、文獻[13]中的RGR協議和文獻[17]中的Improved-RGR協議、文獻[18]中的AR-AODV協議。仿真區域大小設置為100 km×100 km×20 km，100個節點在區域內隨機分布，各個節點參數設置相同，節點的通信半徑為20 km。節點運動模型為RWP模型[26](暫停時間為0)，通信模型采用CBR數據源，數據包大小為512 B,MAC協議采用IEEE802.11，信道傳輸速率為2 Mbit/s，信號傳播損失模型為Friis模型，MAC層隊列緩存區最大長度為50，仿真運行時間為20 min。通過改變網絡中的節點發包速率以及節點的運動速度，設置不同的仿真場景，通過分組投遞率、平均端到端時延和路由開銷3項性能指標的對比分析，實驗結果取10次實驗的平均值。

2.2 仿真結果分析

圖5～7為節點在發包速率為20 packets/s保持不變的條件下，不同的節點最大運動速度對不同路由協議的網絡性能的影響。其中，圖5顯示了不同路由協議下，無人機節點最大移動速度與分組投遞率之間的關系曲線。從圖中可得，隨著運動速度的增大，5種不同的路由協議的數據分組投遞率都會不同程度的下降。這是因為運動速度的增大會使得節點間的鏈路更加不穩定，鏈路斷開的可能性增大，路由失敗機率增加。由于LBHGS-RGR路由協議在數據傳輸過程中，出現鏈路斷開的情況后，則切換至GGF模式，同時提高了GGF模式下的分組成功轉發概率，能很好應對網絡拓撲的劇烈變化。因此，相較于其他4種路由協議具有更高的分組投遞率。

圖5 節點最大移動速度與分組投遞率關系圖

從圖6可以看出隨著節點速度增大，5種路由協議的平均端到端時延都在增大。相較于AODV和AR-AODV協議，在節點移動速度較大時，RGR協議及其改進型因為不需要進行本地路由修復，時延相對較低，同時LBHGS-RGR協議考慮了節點的負載，減小了數據傳輸過程中的排隊時延，進一步降低了平均端到端時延。

圖6 節點最大移動速度與平均端到端時延關系圖

由圖7可知，當網絡中節點的運動速度較小時，5種路由協議的路由開銷較為接近。隨著節點運動速度的增大，由于鏈路斷開頻繁，路由開銷都在增大，LBHGS-RGR協議采用受限的洪泛機制，減少了路由開銷，但是相較于Improved-RGR在路由開銷方面提升不大。

圖7 節點最大移動速度與路由開銷關系圖

圖8～10顯示了網絡節點在最大運動速度保持在50 m/s不變的條件下，數據包產生速率對不同種類路由協議性能的影響。

圖8 數據包產生速率與分組投遞率關系圖

由圖8可知，隨著數據包產生速率的增加，網絡出現擁塞的概率增大，部分節點由于緩存溢出開始丟棄數據分組，5種路由協議的分組投遞率都在下降，其中AODV協議下降最快，并隨著負載增大，下降趨勢更加明顯，AR-AODV和Improved-RGR性能相近，LBHGS-RGR協議下降趨勢則最緩。這是由于LBHGS-RGR協議均衡了網絡負載，有效避免了擁塞節點的發生，減少了丟包。

圖9為數據包產生速率對網絡的平均端到端時延的影響，相比于其他4種路由協議，LBHGS-RGR協議能有效減少平均端到端時延，這主要得益于LBHGS-RGR協議減少了網絡擁塞發生的概率，有效降低了數據傳輸過程中的排隊時延。

圖9 數據包產生速率與平均端到端時延關系圖

由圖10可知，當數據包產生速率較小時，網絡中的節點負載較輕，5種路由協議的開銷相近，隨著數據包產生速率的增大，路由協議的開銷都在增大。其中，AODV協議和RGR協議的網絡開銷增加較劇烈，兩者的性能相近。AR-AODV和Improved-RGR都未進行負載的均衡，隨著數據包產生速率的增加，路由開銷相較于LBHGS-RGR協議也較大。而LBHGS-RGR協議通過受限洪泛機制減少了路由請求分組的數量，同時采用負載均衡機制，減少節點擁塞的發生，提高了鏈路的穩定性，降低了網絡的控制開銷。

圖10 數據包產生速率與路由開銷關系圖

3 結語

本文針對無人機自組網提出了LBHGS-RGR路由協議，對協議的基于節點負載狀態和地理位置信息輔助的受限洪泛機制、GGF模式下高分組成功傳輸概率的路徑選擇策略和基于節點負載預測和運動特征的分組轉發策略3項關鍵措施進行了闡述。在分別改變節點最大運動速度和數據包產生速率條件下，通過將LBHGS-RGR路由協議與AODV和RGR協議及其改進型下進行了對比分析。仿真結果表明，LBHGS-RGR路由協議有效改善了網絡性能，提高了應對高動態網絡環境的能力，能更好地適應無人機自組網。