無人機自組網GPSR路由協議研究

祝 經，周新力，宋斌斌，王程民

(海軍航空大學， 山東 煙臺 264001)

1 引言

隨著無人機集群組網應用的發展，無人機自組網協議受到廣泛關注，在諸如MAC協議、路由協議、跨層協議、機會網絡傳輸協議等方面均有大量研究[1-2]，其中路由協議是保障無人機自組織網絡運行穩定性和節點間可靠通信的關鍵。根據是否需要地理位置信息輔助，無人機自組網路由協議可分為基于拓撲結構的路由協議和基于地理位置的路由協議兩大類[3]。

參考現有文獻可以看出，基于地理位置的路由協議在維護鄰居列表時所需的開銷遠小于基于拓撲結構的路由協議在建立和維護路由表時所需的開銷[4]。而且，基于地理位置的路由協議具有更強的擴展性且無需考慮網絡收斂問題[5]。另外，中小型無人機大多都具有定位功能，對基于地理位置路由協議的運行也提供便利。因此，綜合考慮以上特性，在高動態的無人機自組網中，基于地理位置的路由協議具有良好的應用前景。而GPSR協議作為一種典型的基于節點地理位置信息的路由協議，具有擴展性強、健壯性好和適應高動態拓撲等特點，從而已成為最適用于無人機自組網的路由協議之一。

為此，梳理GPSR協議相關研究現狀，分析需要進一步優化和改進的研究發展方向，為基于地理位置信息輔助的路由協議更好地用于無人機網絡提供進一步深入研究的思路，具有很強的現實意義。

2 GPSR協議概述

GPSR協議中，每個節點將位置、標識符等信息封裝在數據包的包頭中，并通過周期性相互交換控制消息的方式，獲取鄰居一跳節點的位置信息，建立鄰居列表和節點之間的路由，從而實現對數據包的傳輸。GPSR協議有貪婪轉發(greedy forwarding)和周邊轉發(perimeter forwarding)[6]2種數據包轉發方式。

2.1 貪婪轉發

貪婪轉發是基于歐幾里得距離的鄰近度量，其通過選擇到目的節點最近的鄰居節點作為數據包轉發的下一跳節點[7]。此外，貪婪轉發通過交換信標消息來進行預先鄰居節點發現，使得每個節點在一次交換中擁有其鄰居節點的地理位置信息。如圖1所示，數據包從源節點S傳輸至目的節點D。通過選擇傳輸范圍內距離目的地最近的節點作為下一跳，數據包被一跳一跳地轉發。在目的地移動性非常高的情況下，這種路由模式提供了相當接近有線網絡的成功率。但是，當發送節點在其通信范圍內沒有比本節點距離目的節點更近的節點時，就會出現路由空洞，即局部最小化現象。如圖1所示，節點S在尋找到達節點D的路由時，發現單跳通信范圍內不存在比S節點距離D節點更近的鄰居節點。此時則認為貪婪轉發失效，S節點稱為局部最小化點。路由空洞就是所有相鄰局部最小化點之間的連線所構成的多邊形區域。

圖1 貪婪轉發過程示意圖Fig.1 Greedy forwarding process

2.2 周邊轉發

當數據包傳輸過程中遇到路由空洞，即貪婪轉發算法失敗時，為了能將數據包繞過路由空洞繼續向前轉發，則需切換至周邊轉發。在周邊轉發模式中，首先基于平面化算法將網絡平面化，然后空洞節點采用右手規則，在比自身距離目的節點遠的鄰居節點中作出選擇，選出下一跳轉發節點。如圖2所示，節點S的傳輸范圍內，所有其他節點與目的節點之間的距離都大于其自身。因此，節點S切換至周邊轉發模式，按照右手準則，順時針遍歷該多邊形，形成路徑:S-A-F，繞過路由空洞。當在節點F處再次符合貪婪轉發條件時，則切換模式，形成路徑F-D，節點將數據包轉發至目的節點D。

圖2 周邊轉發過程示意圖Fig.2 Perimeter forwarding process

2.3 平面化算法

GPSR協議采用的平面化算法有：相關鄰接圖算法(relative neighbor graph，RNG)和加百利圖算法(gabriel graph，GG)[7]。2種算法的原理圖如圖3所示。

RNG算法定義為：節點A，B之間的距離大于或等于任意節點X到2個節點的距離。其表達式為：

?X≠A，B∶d(A，B)≤max[d(X，A)，d(X，B)]

(1)

GG算法定義為：在以節點A，B間距離為直徑的圓內，若不存在任意節點X，則存在兩節點A，B之間的邊(A，B)。其表達式為：

?X≠A，B∶d2(A，B)≤[d2(X，A)+d2(X，B)]

(2)

圖3 RNG和GG平面化算法原理示意圖Fig.3 RNG and GG planarization algorithm

3 GPSR協議研究現狀

針對無人機自組織網絡中由于節點部署稀疏、節點高速移動等特性可能帶來的影響，學者們對GPSR協議展開了廣泛的研究和改進，其中主要有如下幾個方面。

3.1 協議控制開銷優化

基于拓撲結構的路由協議需要知道全局節點的拓撲信息，并建立和維護路由表，而傳統的GPSR協議作為典型基于地理位置的路由協議，僅需知道所有一跳鄰居節點當前時刻的位置信息，再根據這些位置信息即可完成數據的轉發，不需要建立和維護路由表[8]。因此相比基于拓撲結構的路由協議，GPSR協議具有更少的控制開銷，傳輸效率更高，更適用于拓撲結構變化頻繁的無人機網絡。然而GPSR協議仍可能面臨著開銷過大的問題[9]，如周邊轉發模式下的冗余現象，見圖4所示。

圖4 周邊轉發冗余現象示意圖Fig.4 Perimeter forwarding redundancy

由圖4(a)可知，數據包在轉發過程中遇到了路由空洞，在網絡平面化之后，根據右手規則選擇下一跳節點，形成了S-A-B-C-E-F-D的傳輸路徑。而從圖4(b)可以發現，如果節點S在遇到路由空洞之后直接將E作為下一跳節點，形成S-E-F-D，將比原來的方式具有更短的路徑，即傳統的周邊轉發模式可能會出現繞路的現象。

為了降低車載自組網(vehicular ad hoc network，VANET)中遇到局部最優的可能性，文獻[10]設計了一種改進的基于流量密度分層的GPSR協議。在稀疏區域，每個節點維護一個記錄其多跳鄰居節點的列表，而在稠密區域，每個節點只維護其單跳鄰居節點。每個節點會根據外圍流量密度的變化而改變策略。仿真結果表明，相比傳統GPSR協議，改進后的GPSR協議具有更高的傳輸速率和更小的控制開銷。

文獻[11]提出了一種改進版的E-GPSR協議，采用了一種新的機制來代替傳統的周邊轉發模式進行下一跳節點的選擇。新的選擇機制基于源節點(或中繼節點)到目的地的距離加上源節點(或中繼節點)到下一跳的距離，從而使得下一跳為總距離最小的鄰居。改進的E-GPSR協議經過驗證，可以有效地減少傳輸延遲和控制開銷。

文獻[12]基于虛擬坐標映射提出了一種有效的空洞繞過路由協議(EVRP)。EVRP通過映射邊緣節點在虛擬圓上的坐標，將空白邊緣的隨機結構轉化為規則結構。經過聚類和冗余調度后，每個節點都有一個能量閾值。如果節點的能量低于閾值，則向集群頭發送故障消息，集群頭利用與故障節點的交角，將其所有鄰居視為預備邊界節點，同時判斷每個預備邊界節點。這樣就構造了一個虛擬矩形，覆蓋產生動態中間目的節點的路由空洞，提高了數據包傳輸過程中繞過路由空洞的效率和成功率。仿真和分析結果表明，EVRP在尋找最短路由路徑方面具有更高的傳輸率、更小的控制開銷和能量消耗。

3.2 路由空洞處理算法優化

由于無人機網絡具有稀疏性，節點密度較為稀疏，且當路徑上出現阻擋或是通信鏈路不穩定導致的節點斷開，都不可避免地會出現路由空洞現象[13-15]。該空洞既可以是物理上網絡無法覆蓋的內部區域，也可以是應用程序定義的無法進行數據包路由的交通阻塞區域。

當傳統GPSR協議在貪婪轉發過程中出現路由空洞現象時，節點根據目標節點和一跳鄰居節點的位置信息構造平面圖，再使用周邊轉發的方式，繞開路由空洞，直至滿足條件回到貪婪轉發狀態。在網絡節點密度足夠密集的條件下，貪婪轉發一定可以找到一條最優路徑[16]。但是當出現空洞之后，周邊轉發算法在選擇節點時具有一定的隨意性，只能保證能夠找到一條到達目的節點的路徑，但不一定是最優路徑，即貪婪轉發方法將終止在局部最優，而不是全局最優。并且傳統的周邊轉發方式不僅需要進行多次的轉發才能回到貪婪轉發狀態，在過程中也極容易出現繞路的現象，增加不必要的多跳節點和端到端延時。如果無人機網絡部署在不理想的環境中，則將頻繁地遇到空洞，從而頻繁地切換數據包轉發方式，以致可能會帶來更多不必要的跳數。同時數據包轉發方式的頻繁切換，將使數據包的生存周期降低，從而導致數據包丟失的概率增加。因此，傳統路由空洞處理算法在應用時仍存在一定的問題，如何優化路由空洞處理算法以提升協議的傳輸效率，已成為GPSR協議研究的熱點。

文獻[17]提出了一種新的空洞處理算法，其首先檢測出空洞的邊界，然后選取邊界凸包中的一個節點作為中繼節點，最后利用中繼節點的信息，將數據包繞空洞轉發，從而構造出跳數較少的路徑。新提出算法能夠較好地處理路由空洞，提高數據包投遞率，但由于其較高的算法復雜度，仍面臨著端到端延時和控制開銷較高的問題。

文獻[18]為最大限度地提高分組轉發效率，在貪婪轉發模式下采用了一種新的路由算法IAPS(interference aware progress speed)，該算法可以估計下一跳節點的轉發距離、鏈路質量和信道訪問難度。當數據包轉發達到局部最小值時，算法IAPS采用一種基于競爭優勢的機會轉發方法來繞過空洞區域，從而可以有效地提高網絡資源利用率和平均吞吐量，降低無線多跳網絡的擁塞損失率。

3.3 鏈路建立穩定性優化

GPSR協議在工作時，源節點掌握自身位置信息、一跳范圍內鄰居節點以及目的節點的地理位置信息，并在使用貪婪算法時，根據歐幾里得距離來選擇下一跳節點[19-20]。下一跳節點通常是鄰居節點列表中與目的節點歐幾里得距離最小的節點，因此，這樣選擇的下一跳節點通常處于節點通信范圍的邊緣。而無人機自組網中通常以無人機作為通信節點，其具有的高速移動特性可能會使所選擇的下一跳節點在數據包到達之前就已移出通信范圍。如圖5所示，源節點S向目的節點D傳輸數據包。在數據包傳輸之前，根據貪婪轉發的原則，節點S將選擇距離目的節點D最近的B作為下一跳節點。當數據包傳輸的過程中，節點發生移動，S移動到了S′，B移動到了B′，然而B′已經不在S′的通信范圍之內，即B′不在S′的鄰居節點列表中。這樣就會造成數據包無法從S′傳輸到B′，導致傳輸鏈路出現斷裂，數據包將出現回傳或丟失現象，降低網絡的整體性能。

除此之外，由于無人機自組織網絡部署環境的復雜性、資源有限性等特點，建立的鏈路容易由于節點間的通訊干擾、節點休眠、電力耗盡以及數據擁塞等因素而失效[21]，由此就會造成鏈路穩定性下降，增加丟包率和端到端延時，影響數據包的傳輸。因此，面對無人機節點高速移動等特性，傳統的GPSR協議仍存在一定的局限性，不能夠保證節點選擇和鏈路建立的準確性和可靠性，還需進行相關優化來更好地解決問題。

圖5 節點移出通信范圍現象示意圖Fig.5 Node moving out of communication range

文獻[22]在原有GPSR路由協議基礎上進行了改進，通過選取鄰居節點移動方向、鏈路風險、鄰居節點密度和鄰近度等4個指標來評估鏈路質量，可有效地提升包投遞率，增加鏈路的穩定性。

文獻[23]提出一種基于預測地理位置的路由協議PGRP，以減少數據包的丟失，提升網絡的性能。在PGRP中，每個節點將根據節點的移動方向和角度給相鄰節點一個權重，并根據節點移動的加速度預測每個節點在發送hello數據包時的位置。相比傳統GPSR協議，PGRP在數據包投遞率、平均跳數等方面均有所提升，能夠有效地提高鏈路的穩定性。

文獻[24]結合移動預測，提出了一種高效可行的更新算法DBUM。DBUM由主動更新和強制更新2種模式構成，其能夠在較少信標流量情況下提高節點位置信息的準確性。評估結果表明：采用DBUM算法的GPSR協議，在提高了地理位置信息準確性的同時，減少了控制開銷和端到端延時，較好地克服了節點高移動性對網絡整體性能的影響。

3.4 節點能量均衡優化

在無人機自組網中，無人機作為其中的移動節點，能量因素將對其載荷能力產生較大的影響[25]。而GPSR路由協議的貪婪轉發機制通常基于歐氏距離來選擇下一跳節點進行數據的轉發，雖然比較容易實現，但也易造成網絡中節點能量分布不均衡，影響網絡的整體性能，主要原因如下：

在數據轉發過程中，路徑上的節點既是主機又是路由器，將承擔數據處理和數據轉發雙重任務，能量消耗較快，容易導致網絡中節點的能量不均衡[26]。

貪婪算法在選擇下一條節點時，通常只考慮了距離因素，沒有考慮節點能量消耗的差異，如圖6所示。源節點S在向目的節點D轉發數據包時，在N1，N2，N3，N4中往往選取距離目的節點更近的N2作為下一跳節點。當出現熱點路由問題時，即如果目的節點D為熱點數據源，數據包頻繁地傳至D，則S-N2-D將成為一條熱點路由。熱點路由頻繁地承擔數據轉發的任務，例如N2這樣熱點路由上的節點就可能會出現過早的能量耗盡，從而縮短網絡的生存時間。

因此，如何均衡網絡中節點的能量，延長網絡的生存周期，從而提高協議工作效率成為了GPSR路由協議研究的熱點問題[27-28]。

圖6 熱點路由現象示意圖Fig.6 Hotspot routing

文獻[29]提出了一種基于地理路由協議的能量均衡貪婪轉發路由(EBGR)協議，以實現路由路徑的均衡能耗，同時保持分層網絡的良好效率和可擴展性。該方法使用剩余跳數代替傳統貪婪轉發機制中的歐氏距離，結合節點的剩余能級，建立起源節點與匯聚節點之間的路徑。

文獻[30]引入興趣梯度和能量梯度的概念來對GPSR協議進行改進。首先，當查詢路徑建立后，進行數據傳輸時，根據匯聚節點與事件區域節點發生數據內容的匹配程度確定興趣閾值，并根據路徑能量損耗數據包和傳感器節點剩余能量，得到一個固定值作為能量閾值；然后，當節點接近閾值時，網絡及時地根據遞歸貪婪算法和右手規則提前找出一條新的路徑到目標區域，從而使節點負載相對均衡。通過這種改進方案，優化后的GPSR協議可以有效地減少網絡能耗，并均衡節點能量，達到了延長網絡生存周期的目的。

4 GPSR協議研究發展方向

近幾年，隨著對GPSR協議研究的深入，為更好地適應無人機自組網的工作特點，對一些新穎算法進行優化和改進，逐漸成為專家學者們新的研究發展方向。

4.1 三維優化算法

傳統的GPSR路由協議在貪婪轉發模式轉變至周邊轉發模式之前，通常需要先采用GG和RNG等2種方式來構建一個二維的平面，再從中根據右手規則進行對下一跳節點的選擇[31]。通過這2種平面化算法，可以較好地選擇出下一跳節點，保證數據包存在一個路徑傳至目的節點。但是對于無人機自組網來說，無人機節點通常工作在三維空間中，在二維平面圖上的節點選擇通常會存在一些偏差，使節點無法找到正確的中間節點，從而可能導致數據包的傳輸錯誤，影響數據包傳輸的效率以及正確性[32]。

文獻[33]提出一種改進的GPSR-3D路由協議，其采用表面轉發模式來代替周邊轉發模式。表面轉發模式首先基于一種新的三維幾何結構將整個網絡空間劃分為一組子空間，然后根據一種并行多面體遍歷算法來恢復局部極小值。仿真結果表明，GPSR-3D具有較高的可靠性、節能性和存儲效率，但其控制開銷較大且更多地適用于靜止的網絡中，難以滿足無人機自組網中節點高速移動等特性。由此，設計出一種貼合無人機自組網三維工作環境特點的節點選擇算法，成為未來的研究熱點。

4.2 粒子群優化算法

GPSR協議根據地理位置信息來建立無人機自組網路由，在其貪婪轉發選擇下一跳節點時，當前節點通常只考慮在其一跳范圍內距離目的節點最近的鄰居節點，而忽略了丟包嚴重、節點能量消耗和邊界節點易受干擾等問題，網絡傳輸效率和質量實際上并不高[34]。因此，如何更全面地考慮多因素對節點選擇的影響已成為協議優化重點關注的問題。

粒子群優化算法是一種較為成熟的群智能優化技術[35]，其可以在每次迭代過程中通過當前所找的個體極值和全局極值來不斷更新自己的位置和速度，從而不斷向目標位置靠近，最終找到最優解[36]。因此，為盡可能考慮到節點下一跳選擇時的多方面因素，實現對無人機自組網中GPSR協議的進一步優化，利用粒子群算法來進行均衡處理可成為下一步研究的方向。

4.3 多徑路由算法

傳統的GPSR協議采用單路徑、多跳的方式來實現數據包的轉發。協議中數據包通過多個中間無線節點在單條路徑上進行協作轉發，每個中間節點將數據包從上一跳轉發到下一跳節點。此種傳輸方式在拓撲變化較小且負載較低的網絡中具有控制復雜度低、路徑質量高等優點[21]。然而由于無人機自組網節點的高速移動性、部署環境的復雜性以及資源有限性等特點，單條路徑容易發生斷裂，如何提高鏈路傳輸的穩定性已成為一個不可避免的問題。

為解決GPSR協議中單路徑傳輸所面臨的問題，多徑路由算法能夠同時構造和維護多條自源節點到目的節點的路徑，并根據網絡要求將任務流量分配到一條或多條路徑上。與單徑路由相比，多徑路由算法除了可靠性更高以外，還具有資源利用高效、QoS保證等優點。目前大部分多徑路由算法，多以AODV和DSR為代表的基于拓撲結構的路由協議來進行設計，結合基于地理位置的路由協議的研究較少。如何設計出適合GPSR等基于地理位置的路由協議的多徑路由算法，還需要研究者們展開更深入的研究工作。

5 結論

近年來，無人機自組網在現代化無人機作戰形式中得到越來越多的重視和應用，而無人機自組網路由協議作為無人機自組網通信技術的重要組成部分，更是需要進行大量的研究來滿足實際作戰的需求。GPSR協議作為一種典型的基于地理位置的無人機自組網路由協議，被實驗證明在無人機自組網中具有良好的性能，但仍存在一些問題，影響其更好地應用。本文在闡述了GPSR協議基本概念的同時，對其在無人機自組網中的研究現狀和發展方向等方面進行了梳理和討論，可為無人機自組網GPSR協議的研究提供重要參考。