基于節(jié)點(diǎn)相對(duì)速度的“周界轉(zhuǎn)發(fā)”策略改進(jìn)

楊振偉，許諾

（四川大學(xué)電子信息學(xué)院，成都610065）

0 引言

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

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

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

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

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

在GPSR 協(xié)議中，節(jié)點(diǎn)將它們的位置信息封裝在通信數(shù)據(jù)包的報(bào)頭中，每個(gè)節(jié)點(diǎn)發(fā)送包含其位置和標(biāo)識(shí)符的信標(biāo)消息，以便其他節(jié)點(diǎn)可以知道其位置和方向，控制分組消息的定期交換使得節(jié)點(diǎn)可以建立網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)位置表。GPSR 協(xié)議的優(yōu)點(diǎn)之一就是每個(gè)節(jié)點(diǎn)只需要保存其相鄰節(jié)點(diǎn)的位置和其他相關(guān)信息，減少了節(jié)點(diǎn)內(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é)點(diǎn)間距離的鄰居節(jié)點(diǎn)位置計(jì)算方法，貪婪轉(zhuǎn)發(fā)模式是在源節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集中選擇到目的地距離最近的鄰居節(jié)點(diǎn)作為通信傳輸?shù)南乱惶欣^節(jié)點(diǎn)。通過信標(biāo)消息的定期洪泛，每個(gè)節(jié)點(diǎn)都保存了其鄰居節(jié)點(diǎn)的位置信息，在下一跳選擇中按照貪婪算法選擇中繼節(jié)點(diǎn)，如此不斷轉(zhuǎn)發(fā)直至到達(dá)目的節(jié)點(diǎn)。

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

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

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

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

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

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

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

1.3 平面圖

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

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

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

圖3 平面圖

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

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

中繼節(jié)點(diǎn)R 與目標(biāo)節(jié)點(diǎn)D 之間的運(yùn)動(dòng)狀態(tài)可以概括為三種運(yùn)動(dòng)形式：相向運(yùn)動(dòng)，相對(duì)距離不斷縮小；同向運(yùn)動(dòng)，相對(duì)距離幾乎不變；反向運(yùn)動(dòng)，相對(duì)距離不斷擴(kuò)大。

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

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

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

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

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

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

GPSR 改進(jìn)算法

步驟1：洪泛信標(biāo)消息，更新節(jié)點(diǎn)位置信息；

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

步驟3：

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

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

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

步驟5：結(jié)束。

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

3.1 NS2仿真平臺(tái)

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

表1 仿真參數(shù)

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

3.2 實(shí)驗(yàn)對(duì)比分析

（1）標(biāo)準(zhǔn)路由開銷（Normalized Routing Overhead）

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

圖5 標(biāo)準(zhǔn)路由開銷對(duì)比分析

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

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

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

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

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

4 結(jié)語(yǔ)

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