基于節點相對速度的“周界轉發”策略改進

楊振偉，許諾

（四川大學電子信息學院，成都610065）

0 引言

在過去的十幾年中，人們對使用無人機進行各種應用和服務的興趣越來越大。無人機（Unmanned Aerial Vehicles，UAVs），已經被證明可以有效地完成更多比較復雜的任務，當它們被部署在同一個系統中時，就形成了一種特殊的飛行自組織網絡（Flying Ad-hoc Networks，FANETs）[1]。FANETs 的部署通常是基于任務目的的，其移動模型[2]由所完成任務的需求和性質決定。相比于移動自組網（Mobile Ad-hoc Networks，MANETs）和車載自組網（Vehicle Ad-hoc Networks，VANETs），FANETs 具有特殊的網絡拓撲結構，其路由協議需要適應FANETs 的高度動態拓撲結構以及所受的飛行約束條件。因此，用于FANETs 的路由協議應充分考慮到多無人機網絡部署的任務需求，網絡拓撲結構和仿真移動模型的特點。

在FANETs 網絡系統中，無法預先部署可以進行數據收發的通信基站節點，每個節點既是發送數據的通信終端，又是轉發數據的路由節點，是一種典型的多跳路由模式。FANETs 網絡的獨特特性引發了傳統網絡中不存在的路由問題，需要新的路由算法組織網絡通信[3]。隨著定位技術的發展和全球定位系統的廣泛應用，地理路由協議為物聯網、無線傳感器網絡和無線網狀網絡等下一代無線網絡[4]的發展提供了較為可靠的路由協議。

FANETs 中UAV 節點的快速移動和網絡拓撲的頻繁更新，導致節點之間的通信鏈路經常發生中斷。路由查詢恢復時，路由開銷會增加數倍。為了解決路由查詢導致路由開銷突然增加的問題，學者們提出了各種新的基于地理位置的預測路由協議[2]。本文基于貪婪周界無狀態路由（Greedy Perimeter Stateless Routing，GPSR）協議[5]對FANETs 中的路由協議性能開展研究，并對GPSR 協議的“周界轉發”策略進行優化。

1 貪婪周界無狀態路由協議

GPSR 協議[5]是一種基于地理位置響應迅速且高效的路由協議，已被設計并應用于車載自組織網絡和傳感器網絡，在無人機網絡中也有較多應用。GPSR 協議使用節點的地理位置信息來計算路由表進行路由查詢，轉發數據和控制消息，并且假設所有節點都在拓撲范圍內的同一高度。

在GPSR 協議中，節點將它們的位置信息封裝在通信數據包的報頭中，每個節點發送包含其位置和標識符的信標消息，以便其他節點可以知道其位置和方向，控制分組消息的定期交換使得節點可以建立網絡內節點位置表。GPSR 協議的優點之一就是每個節點只需要保存其相鄰節點的位置和其他相關信息，減少了節點內存資源的占用。根據不同的網絡密度分布，GPSR 協議通過兩種模式完成數據的通信傳輸：貪婪轉發和周界轉發。

1.1 貪婪轉發模式

貪婪轉發[6]是基于節點間距離的鄰居節點位置計算方法，貪婪轉發模式是在源節點的鄰居節點集中選擇到目的地距離最近的鄰居節點作為通信傳輸的下一跳中繼節點。通過信標消息的定期洪泛，每個節點都保存了其鄰居節點的位置信息，在下一跳選擇中按照貪婪算法選擇中繼節點，如此不斷轉發直至到達目的節點。

如圖1 所示，從源節點25 向目標節點19 發送消息，依次經過節點28、節點10、節點26、節點29，在每一跳中選擇距離目的節點最近的鄰居節點，將數據包逐跳轉發到目的節點。

在目的節點移動性比較低的情況下，貪婪轉發模式提供了相當于有線網絡的數據交付成功率。當數據包到達不能執行貪婪轉發模式的拓撲區域時，則使用周界轉發模式。

圖1 貪婪轉發模式

1.2 周界轉發模式

當貪婪轉發策略失敗時，將使用周界轉發模式。如圖2 所示，在源節點S 的可傳輸范圍之內，除了源節點S 本身以外，不存在其他距離目的節點更近的鄰居節點，這種情況稱之為路由空洞。

如圖2 所示，源節點S 和目的節點D 的覆蓋范圍的重合區域，該區域不包含相鄰節點。在這種情況下，協議使用右手定則發送接收到的數據包，傳輸路徑為SABDECS，這種轉發模式我們稱為周界轉發。

圖2 周界轉發-右手定則

1.3 平面圖

周界轉發模式可以采用右手定則繞過路由空洞，但是，在某些情況下，周界轉發模式可能會進入路由死循環，無法轉發至目標節點。

如圖3 所示，節點1 和節點25 均為彼此鄰居節點集中距離目標節點12 的最近鄰節點，數據包在節點1和節點25 之間無限循環轉發，會增大網絡開銷和通信延遲，造成通信鏈路擁塞。

為解決路由出現死循環的問題，需要刪除通信網絡拓撲圖中功能重合的鏈路，使之成為平面圖。常用的兩種處理方法是RNG 平面圖和GG 平面圖，平面化處理后的網絡拓撲圖可以有效減少以上路由轉發困境，不可達即丟包，減少網絡負載。

圖3 平面圖

2 貪婪周界無狀態路由協議的優化

本節在GPSR 協議的基礎上引入速度矢量，基于速度矢量對通信網絡中的路由中繼節點選擇方法進行優化[7-9]，在路由計算中引入優化函數E，優先選取與目的節點做靠近運動的節點作為中繼節點，對“周界轉發”策略進行改進和優化，提高數據交付和網絡路由開銷。

中繼節點R 與目標節點D 之間的運動狀態可以概括為三種運動形式：相向運動，相對距離不斷縮小；同向運動，相對距離幾乎不變；反向運動，相對距離不斷擴大。

速度矢量包括節點的瞬時移動方向和速度大小，優化函數E 的值

其中θ為目標節點D 與中繼節點R 的速度矢量夾角，v_d 為目標節點D 的速度大小，v_r 為中繼節點R的速度大小。e 越大，中繼節點R 和目標節點D 之間的相對距離縮小的速度越快，節點鏈路越穩定。

改進的GPSR（Enhance Greedy Perimeter Stateless Routing，E-GPSR）協議在節點的位置信息和洪泛的信標信息中加入速度矢量，定時進行信息洪泛更新節點位置坐標和節點速度信息。網絡中的其他節點接收信標信息，然后在路由表中更新其他節點的位置信息和速度矢量信息。

當源節點需要向目標節點發送信息時，在貪婪算法失效的情況下，分別計算各鄰居節點與目標節點的優化函數值e，并結合GPSR 的周界轉發策略選取中繼節點。

圖4 周界轉發-E-GPSR

在圖4 所示的拓撲網絡中，GPSR 協議采用原始的周界轉發模式，會造成較大的網絡擁塞和數據丟包率，并且數據包無法送到目的節點。為解決數據傳輸中可能出現的數據包不可達的問題，本節對GPSR 協議的周界轉發策略進行優化。節點20 與目標節點D 無法建立可靠連接，右手定則失效，采取回饋機制，在節點1和節點25 中選取合適的中繼節點按反方向繼續轉發數據包。GPSR 協議的周界轉發改進策略如下：

GPSR 改進算法

步驟1：洪泛信標消息，更新節點位置信息；

步驟2：源節點S 獲取目標節點D 的編號，從路由表中查詢D 的位置信息；

步驟3：

（1）若源節點S 的鄰居節點中存在距離目的節點D 更近的節點，則采用貪婪轉發策略選擇此節點作為下一跳中繼節點；

（2）若不存在，則采用周界轉發策略的右手定則選擇中繼節點進行轉發；

步驟4：若接收到數據不可達信息，則采用“周界轉發”優化策略；

步驟5：結束。

3 NS2仿真實驗與數據分析

3.1 NS2仿真平臺

NS2 仿真平臺作為國內外學者研究網絡通信的重要模擬平臺之一，底層協議采用C++語言編寫，可以高效地進行數據運算和具體協議的實現；上層使用OTcl語言，方便用戶進行網絡組件和環境參數的設置[10]。仿真實驗主要參數設置如表1 所示。

表1 仿真參數

本節主要通過標準路由開銷和數據包交付率兩個指標對GPSR 協議和E-GPSR 協議的路由性能進行對比分析。按照表1 所列參數，在隨機生成的場景中重復實驗10 次，對實驗結果取平均值。

3.2 實驗對比分析

（1）標準路由開銷（Normalized Routing Overhead）

標準路由開銷為仿真過程中由無人機節點發送的數據包總數與傳輸的所有消息和數據包之和的比值。路由開銷的值可以使用以下公式求得：

圖5 標準路由開銷對比分析

E-GPSR 協議的平均路由開銷比GPSR 協議提高了7.6%。當節點個數增加時，網絡拓撲節點密度增加，可用路由增多，數據包在網絡通信傳輸中所占比例增加，標準路由開銷增加；當節點數目較多時，E-GPSR協議與GPSR 協議性能漸趨一致。

（2）數據包分組到達率（PDR，Packet Delivery Ratio）

數據包分組到達率為網絡中目標節點接收到的數據包數量與源節點發送的數據包數量之比。PDR 的值可由下式求得：

在數據包分組到達率方面，E-GPSR 協議均好于GPSR 協議，平均分組到達率提高了5.8%。E-GPSR 協議在數據轉發過程中對周界轉發模式進行了改進，增加了路由查詢路徑，提高了數據包的分組到達率。

圖6 數據包分組到達率對比分析

4 結語

本文在GPSR 協議周界轉發策略的基礎上，增加了右手定則路由查詢恢復的補充策略。仿真實驗表明，E-GPSR 協議穩定性增加，數據包的分組到達率有了一定的提高，在標準路由開銷方面也增加了通信數據包的占比；另外，在通信時延方面相較于GPSR 協議有了一定的增加，但是對于網絡性能的整體效果影響不大。E-GPSR 協議更加適合低速巡航自組網系統通信。