楊振偉，許諾

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

0 引言

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

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

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

1 貪婪周界無狀態(tài)路由協(xié)議

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

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

1.1 貪婪轉(zhuǎn)發(fā)模式

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

如圖1 所示，從源節(jié)點25 向目標節(jié)點19 發(fā)送消息，依次經(jīng)過節(jié)點28、節(jié)點10、節(jié)點26、節(jié)點29，在每一跳中選擇距離目的節(jié)點最近的鄰居節(jié)點，將數(shù)據(jù)包逐跳轉(zhuǎn)發(fā)到目的節(jié)點。

在目的節(jié)點移動性比較低的情況下，貪婪轉(zhuǎn)發(fā)模式提供了相當于有線網(wǎng)絡(luò)的數(shù)據(jù)交付成功率。當數(shù)據(jù)包到達不能執(zhí)行貪婪轉(zhuǎn)發(fā)模式的拓撲區(qū)域時，則使用周界轉(zhuǎn)發(fā)模式。

圖1 貪婪轉(zhuǎn)發(fā)模式

1.2 周界轉(zhuǎn)發(fā)模式

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

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

圖2 周界轉(zhuǎn)發(fā)-右手定則

1.3 平面圖

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

如圖3 所示，節(jié)點1 和節(jié)點25 均為彼此鄰居節(jié)點集中距離目標節(jié)點12 的最近鄰節(jié)點，數(shù)據(jù)包在節(jié)點1和節(jié)點25 之間無限循環(huán)轉(zhuǎn)發(fā)，會增大網(wǎng)絡(luò)開銷和通信延遲，造成通信鏈路擁塞。

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

圖3 平面圖

2 貪婪周界無狀態(tài)路由協(xié)議的優(yōu)化

本節(jié)在GPSR 協(xié)議的基礎(chǔ)上引入速度矢量，基于速度矢量對通信網(wǎng)絡(luò)中的路由中繼節(jié)點選擇方法進行優(yōu)化[7-9]，在路由計算中引入優(yōu)化函數(shù)E，優(yōu)先選取與目的節(jié)點做靠近運動的節(jié)點作為中繼節(jié)點，對“周界轉(zhuǎn)發(fā)”策略進行改進和優(yōu)化，提高數(shù)據(jù)交付和網(wǎng)絡(luò)路由開銷。

中繼節(jié)點R 與目標節(jié)點D 之間的運動狀態(tài)可以概括為三種運動形式：相向運動，相對距離不斷縮?。煌蜻\動，相對距離幾乎不變；反向運動，相對距離不斷擴大。

速度矢量包括節(jié)點的瞬時移動方向和速度大小，優(yōu)化函數(shù)E 的值

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

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

當源節(jié)點需要向目標節(jié)點發(fā)送信息時，在貪婪算法失效的情況下，分別計算各鄰居節(jié)點與目標節(jié)點的優(yōu)化函數(shù)值e，并結(jié)合GPSR 的周界轉(zhuǎn)發(fā)策略選取中繼節(jié)點。

圖4 周界轉(zhuǎn)發(fā)-E-GPSR

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

GPSR 改進算法

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

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

步驟3：

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

（2）若不存在，則采用周界轉(zhuǎn)發(fā)策略的右手定則選擇中繼節(jié)點進行轉(zhuǎn)發(fā)；

步驟4：若接收到數(shù)據(jù)不可達信息，則采用“周界轉(zhuǎn)發(fā)”優(yōu)化策略；

步驟5：結(jié)束。

3 NS2仿真實驗與數(shù)據(jù)分析

3.1 NS2仿真平臺

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

表1 仿真參數(shù)

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

3.2 實驗對比分析

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

標準路由開銷為仿真過程中由無人機節(jié)點發(fā)送的數(shù)據(jù)包總數(shù)與傳輸?shù)乃邢⒑蛿?shù)據(jù)包之和的比值。路由開銷的值可以使用以下公式求得：

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

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

（2）數(shù)據(jù)包分組到達率（PDR，Packet Delivery Ratio）

數(shù)據(jù)包分組到達率為網(wǎng)絡(luò)中目標節(jié)點接收到的數(shù)據(jù)包數(shù)量與源節(jié)點發(fā)送的數(shù)據(jù)包數(shù)量之比。PDR 的值可由下式求得：

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

圖6 數(shù)據(jù)包分組到達率對比分析

4 結(jié)語

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