基于最短路徑的無人機自組網改進路由算法

王朝煒，常新時，馬騰森，龐明亮，王衛東

(北京郵電大學 電子工程學院，北京 100876)

0 引言

無人機自組織網絡(UAV Ad Hoc Network,UANET)是移動自組織網絡(Mobile Ad Hoc Network,MANET)在無人機場景內的一種典型應用。除了具有MANET自組織的特點，還有獨特的移動性、時延性和拓撲動態性等特點，在各領域UANET都具有廣泛的應用，如森林火災監測、搜索和救援行動[1-3]、偵察行動、運輸[4]等。

在無人機通信網絡中，節點通過無線方式相互通信，無人機通信網絡節點可以在不依賴基礎設施的情況下完成與網絡中其他節點的通信，未直接相連的節點可以通過中繼節點進行多跳通信。相較于傳統的無線網絡來說，UANET的移動性更高，這使得無人機的網絡拓撲更加復雜且變化更加頻繁。此外，無人機在高速飛行時需要保持必要的安全距離來避免碰撞，這也給UANET組網和維護帶來挑戰[5]。無線通信網絡的一個很重要研究方向是路由協議的設計；因此，如何有效地選擇適合數據傳輸的鏈路，是衡量一個路由協議是否優秀的標準。基于以上特性，傳統的Ad Hoc網絡路由協議無法直接在UANET中使用。因此，設計一種能夠降低丟包率、減少故障情況恢復時間、提高系統穩定性等指標的路由協議是當前UANET的研究熱點。

在性能提升方面：Sarao等人[6]通過考慮幾個性能指標來分析Ad Hoc網絡的路由協議，如吞吐量、端到端延遲、標準化路由負載，以各種速度和暫停時間接收的數據包，這為路由協議的評估方法提供了思路。Jiang和Han[7]專注于為無人機設計的路線，并旨在對路由協議進行一些完整的調查。此外，還詳細比較了現有路由協議的性能。

在路由協議對比方面：Abbasi和Khan[8]提供了基于仿真的現有動態結點選擇路由協議和靜態結點選擇路由協議的研究，給出了這一領域關于路由技術的深刻見解。Nayyar[9]分析測試UANET中AODV、DSDV、DSR等常見路由協議，以及各路由協議在分組投遞率、端到端時延進而吞吐量的性能指標，驗證最優路由。

在多路徑路由研究方面：針對UANET節點能量有限、移動快、數據多,造成網絡QoS下降的問題，逯建琦[10]提出將改進的螢火蟲算法融入到多徑路由中形成螢火蟲多徑路由算法(AOMDV-FMRA)。首先為減小速度對路徑穩定度的影響，在路由發現過程中引入邊界評價因子以適應拓撲變化，再根據路徑上節點的負載信息，對反向路由進行選擇；最后將能量評價參數映射到螢火蟲算法中對收集到的路徑能量信息進行處理，作為流量分配的依據，提高算法性能。

本文根據UANET的結構特點，以最短路徑路由算法為基礎，提出一種基于最短路徑的改進UANET路由算法，通過對比AODV(Ad Hoc On-demand Distance Vector Routing)和最短路徑算法，以丟包率、平均端到端時延、平均抖動等指標來驗證所提算法的性能。仿真結果表明，所提出算法在無人機節點隨機移動場景中，整體性能有顯著提升。

1 UANET中的路由協議

在UANET中，無人機作為網絡節點組成了多跳自組織網絡。其中，路由協議被定義是通過中間節點查找從源節點到目的節點有效路徑的過程。由于無人機節點的移動性，網絡頻譜隨時發生改變，網絡連接也會因此處于非穩定狀態，造成鏈路間隙性終端。節點移動性、間斷性鏈路、有限的網絡資源，使得無人機中的路由協議成為一項具有挑戰性的研究工作。常見UANET中的路由協議分為主動路由協議和反應式路由協議，其中，反應式路由又分為混合路由協議、基于地理位置的路由協議和受自然啟發的路由協議。UANET示意如圖1所示。

圖1 UANET示意圖Fig.1 Schematic diagram of UANET

1.1 主動路由協議

主動路由協議[11]又稱為表驅動路由協議。在這種路由類型中，為了存儲網絡內部相鄰節點的狀態，每個參與路由的無人機節點需要維護一個或多個路由信息表。當無人機節點移動或者狀態變化時，路由表的信息就會發生變化，此時每個節點都需要更新自己存儲的數據表結構信息[12]。而無論此時是否需要傳輸數據，每個節點都要和網絡中的其他節點交換最新的路由信息。

主動路由協議在維護全局路由表時，時延性能占優，保障了數據包的正確轉發，適用于對時延較敏感的持續性業務；但路由建立和維護的過程會占用部分網絡資源，增加網絡控制開銷，此時該路由協議對于頻繁變化的拓撲結構抵抗性較弱，不適合應用于UANET中。主動路由協議可以分為目的序列距離矢量路由[13](Destination Sequenced Distance Vector，DSDV)和優化鏈路狀態路由協議[14](Optimized Link State Routing，OLSR)。

1.2 反應式路由協議

反應式路由協議，也稱為按需路由協議[15]。在這種路由類型中，當無人機節點發送其數據分組時，且需要確保其自身路由表中不存在到達目的節點的路由，無人機節點才會啟動路由發現過程，該路由表中只存儲活動路由的信息。此時啟動的路由維護機制用于維護有效路由和刪除無效路由[16]，當網絡拓撲發生變化時，失敗的路由將被刪除，路由發現過程將重新開始。此外，路由表會定期更新。因此，與主動路由協議相比，反應式路由協議的效率更高[17]。常見按需式路由協議主要包括按需距離矢量路由(AODV)、Ad Hoc按需多路徑距離矢量路由(AOMDV)和動態源路由(Dynamic Source Routing，DSR)。

1.2.1 混合路由協議

混合式路由協議，結合了先應式和反應式路由協議的特點。在區域內，節點采用先應式路由協議，目的是維護到區域內部其他節點的路由信息，降低區域內節點的通信延遲；在區域外，節點采用反應式路由協議，只有節點發起通信請求時且不存在到目的節點有效路徑時才建立通信路徑，避免了維護到區域外其他無用節點所需的大量網絡開銷。混合路由協議適用于節點數量較大規模的網絡，常見的混合路由協議包括區域路由協議[18]、時序路由協議(TORA)和聚集路由協議(GRP)。

1.2.2 基于地理位置的路由協議

基于地理位置的路由是利用網絡中無人機節點的地理位置信息來輔助路由的選擇[19]，此類協議要求網絡中的每個無人機節點都帶有可以提供自身地理位置信息的硬件設備。首先，通過地理位置信息裝置或者坐標預測技術來估算目的節點的位置；然后，根據得出的位置信息來做出路由決策并完成數據包的轉發。常見的基于地理位置的路由協議是[20]GPSR(Greedy Perimeter Stateless Routing)。

1.2.3 受自然啟發的路由協議

受自然啟發的路由協議源于蟻群、蜂群、鳥群等自然現象。在實際應用中存在一定的缺點，例如會增加通信延遲、通信開銷和能量的消耗[11]。事實上，自然啟發的路由方案是基于拓撲的路由方法的子集，是一種反應式路由[21]。

2 最短路徑算法及改進算法

2.1 最短路徑算法

最短路徑算法是求解單源最短路徑問題的一種算法[22]。給定一個有向圖V=(K,E)，其中K為節點的集合，E為邊的集合，最終以求解得到k.d與k.n為目的，其中k.d為節點k到源節點的最短距離，k.n表示節點k到源節點的下一躍點。最短路徑算法通過迭代操作，對所有的邊進行松弛操作從而更新節點到源節點的最短距離，最終得到所有可能的最短路徑。其偽代碼如算法1所示。

算法1 最短路徑算法(V)偽代碼輸入:V(K,E)輸出:k.d,k.n1:初始化操作2:fori=1to|K|-1do3:foreachedgeE(u,k)∈E4: ifk.d>u.d+w(u,k)5: k.d=u.d+w(u,k)6: k.n=u

算法的步驟流程如下：首先，第1行對所有節點的d值和n值進行初始化，源節點的d值為0，其他節點的d值為無窮大；其次，算法進行了|K|-1次處理，每次處理對應2～6行的一次for循環，每次循環內部都對所有的邊E(u,k) 進行松弛操作；4～6行表示對邊E(u,k) 進行松弛操作，其中w(u,k) 表示邊E(u,k)的權值。圖2為最短路徑算法的執行示例。其中，圖2(a)為算法的輸入拓撲圖，S為源節點；圖2(b)是初始化的結果；圖2(c)～(f)是每次循環迭代操作之后的節點狀態。

最短路徑作為一種主動式路由協議，適用于網絡規模較小、拓撲變化較穩定的網絡環境。當路徑中的節點發生損壞，使得算法失效，導致路徑中斷無法正常傳輸，從而節點再次進行路由發現。這會增加通信網絡的延遲和開銷，還可能會導致網絡堵塞。因此，最短路徑算法不適合拓撲結構迅速變化的UANET。

圖2 最短路徑算法執行示例Fig.2 Example of shortest path algorithm execution

2.2 基于最短路徑的改進路由算法

結合以上所述問題，本文提出了一種適用于無人機網絡的基于最短路徑的改進算法。改進流程如下：首先，最短路徑算法屬于集中式思想，而UANET網絡是一個分布式的系統，最短路徑算法無法直接運用。改進的方式為相鄰節點之間的路由信息先通過交換，再進行最短路徑中的松弛操作，進而觸發鏈式更新操作，就可以實現將最短路徑算法分布化，使其能運行在無人機網絡中；其次，調整了路由表的結構。在原始路由表中增添了記錄下一跳節點的列表，列表信息包括三部分，分別是待選下一跳的IP地址集合、其他下一跳的接口集合和待選下一跳對應到達目的節點的跳數集合。這樣路由信息表更新時不僅更新下一跳的信息，還會同時更新備選下一跳集合，使得每個節點均有多個下一跳可供選擇，與此同時要保證待選集合更新時，所有的備選下一跳均不同，這樣才能確保在路徑切換時無人機節點均跳躍到不同的下一跳上。通過以上改進操作，實現在最短路徑算法的基礎上進行多路徑傳輸的思想。

2.2.1 路由發現過程

改進路由算法的路由發現過程，通過路由信息廣播，無人機節點間進行信息交換可以發現多個下一跳節點并保存至下一跳集合；通過松弛操作，發現N條最短路徑，并保存其中前兩條路徑。選擇先被發現的路徑作為傳輸主路徑，另外一條作為備選路徑；若最短路徑只有一條，那么次短路徑有若干條，則選取最短路徑作為傳輸主路徑，次短路徑作為備選路徑。路由發現過程如圖3所示。

圖3 路由發現流程Fig.3 Route discovery flowchart

2.2.2 路由維護過程

無人機節點移動時，會導致路由網絡拓撲結構發生改變，節點A的鄰居節點也會隨之改變。當節點A發生故障情況時，傳輸路徑斷開，降低了通信網絡的穩定性。此時，路由維護對于增強網絡結構的可靠性十分重要。路由維護的原理是通過檢測本地路由表中的路由是否超過所設時限，如果有路由在一定的時間范圍內沒有進行更新操作，則認為該路由失效，就將該路由從路由表中刪除；然后對外進行廣播；如果在傳輸過程中路徑發生斷裂，則會再次進行路由發現。

在改進路由算法中，網絡中的節點每隔固定時間就會主動廣播并更新路由信息，若發現的新路徑比現有路徑長，則保持使用現有路徑，并更新備選路徑，這樣可以減小路由開銷；如果新的路徑比現有路徑更短，則切換到新路徑，并更新備選路徑，這在一定程度上增加了網絡的穩定性。當網絡運行時，若傳輸路徑上的節點A發生故障或丟包次數達到所設閾值，便會觸發路徑切換機制，將傳輸路徑切換至備選路徑；與此同時節點A的上一跳便會向鄰居節點廣播節點A故障的消息。鄰居節點收到消息，對比自身路由信息，若它的下一跳集合中有節點A，那么它將會更新自身路由信息并廣播；若沒有，則不會廣播。如果備選路徑也斷開傳輸，則無人機節點會重新發起路由發現操作。

當路徑失效且路由表更新后，無人機節點會將更新后的信息廣播給鄰居節點，但向外廣播只會使得其他節點的路由狀態更準確，并沒有對自身節點失效的路由信息做出補償。改進算法在此方面做出了一定的優化，具體方法是：在鏈路失效后節點會廣播更改后的路由信息，在此路由信息廣播包中加入一個標志位，當鄰居節點收到此廣播信息后會反饋相關的路由信息，用于對失效的路由進行補償。

3 改進路由算法的仿真實現

3.1 仿真參數設置

本文采用EXata作為仿真驗證平臺，EXata 是用來研究、開發、測試、評估的工具包，它表現、互動和行為的精確程度同真實網絡相似[23]，用戶能夠根據網絡模擬器對網絡模型的擬合來計算網絡的基礎行為和評估網絡能達到的綜合性能。EXata 創建了一個數字網絡副本，該副本使用真實的應用程序與現實網絡實時連接。

本文的仿真場景中，在有32個隨機分布的無人機的UANET網絡上進行模擬仿真。無人機節點分布在3 000 m×3 000 m的地域范圍內，模擬運行120 s。在網絡中建立一對一通信鏈接，32個無人機隨機移動，設置不同的運動速度(分別為1～2 m/s、4～5 m/s、8～10 m/s、12～13 m/s)，網絡拓撲實時發生變化，鏈路狀態也隨之發生變化。詳細的仿真參數如表1所示。

表1 仿真參數設置Tab.1 Simulation parameter settings

在EXata系統中，固定比特率傳輸(Constant Bit Rate,CBR)采用的是盡力而為的發送策略，也就是說CBR沒有如TCP傳輸協議一樣對數據包的到達率做出保證，因此采用CBR數據傳輸能在仿真中更好地反映出路由協議的真實性能，無人機節點仿真示意如圖4所示。

圖4 無人機隨機運動場景圖Fig.4 Node random motion scenario graph

3.2 仿真結果與分析

本節分析了UANET中不同路由算法的性能，將改進路由算法、AODV算法和最短路徑算法進行對比，在無人機隨機分布隨機運動條件下，AODV路由協議鏈路切換不及時，而改進路由算法的鏈路是周期切換的，可以將鏈路及時快速地切換到更短更新的鏈路，在一定程度上降低時延，提高傳輸效率。通過實驗對丟包率、平均端到端時延、平均抖動等參數進行評估，驗證了改進路由算法的有效性。

各算法的丟包率如圖5所示，當無人機移動速度較低，為1～2 m/s時，由于無人機移動緩慢，網絡拓撲結構變化不大，最短路徑算法優勢明顯，丟包率為16.4%，改進路由算法和AODV表現相差不大，前者略好；隨著無人機移動速度的提高，改進路由算法和AODV丟包率均有下降，最短路徑算法表現較差，丟包率上升，很不穩定。在無人機速度為4～5 m/s時，改進路由算法比最短路徑算法和AODV分別低15.04%和8.94%；當速度上升到8～10 m/s時，改進路由算法比最短路徑算法和AODV分別低16.21%和10.24%；當移動速度繼續上升至12～13 m/s時，改進路由算法比最短路徑算法和AODV分別低22.37%和4.75%。通過對比分析，發現隨著無人機移動速度的提高，改進路由算法丟包率下降最大，因為由于無人機移動造成拓撲結構發生變化時，它能更快地切換到更短路徑，從而實現更小的丟包率?？傮w看來，改進路由算法在無人機移動的情況下有更低的丟包率，優于其他兩種算法。

圖5 無人機隨機運動場景各算法的丟包率Fig.5 Packet loss rate of each algorithm in the node random motion scenario

各算法的平均端到端時延如圖6所示，同樣，在當無人機移動速度為1～2 m/s的條件下，最短路徑算法和AODV時延均超過1 s，只有改進路由算法時延在1 s內；隨著無人機運動速度提高至4～5 m/s，3種算法的端到端時延均有所下降，改進路由算法的時延比最短路徑算法和AODV分別低44.9%和74.0%，AODV延遲仍舊較高，因為AODV在拓撲發生變化時需要重新尋路，導致延遲增加；速度為8～10 m/s時，改進路由算法的時延比最短路徑算法和AODV分別低37.5%和83.6%；在無人機移動速度為12～13 m/s時，改進路由算法的時延比最短路徑算法和AODV分別低12.7%和60.5%。在此場景下，AODV端到端時延表現最差，最短路徑算法表現次之，改進路由算法表現最好。因為當無人機移動造成拓撲結構發生快速變化時，所提出的算法可以更快地發現并切換到更短的傳輸路徑，而更短的傳輸路徑意味著更短的時延。

圖6 無人機隨機運動場景各算法的平均端到端時延Fig.6 Average end-to-end latency of each algorithm in a node stochastic motion scenario

圖7為無人機在不同運動速度下,不同算法的平均抖動。

圖7 無人機隨機運動場景各算法的平均抖動Fig.7 Average jitter of each algorithm in the random motion scenario of the drone

無人機速度為1～2 m/s時，改進路由算法的平均抖動稍高于最短路徑算法和AODV；無人機速度為4～5 m/s時，改進路由算法的抖動比最短路徑算法高0.38 ms，比AODV低0.92 ms；無人機速度上升到8～10 m/s時，改進路由算法的抖動比最短路徑算法高0.22 ms，比AODV低1.24 ms。無人機速度達到12～13 m/s時，改進路由算法仍處于次位。從圖7整體來看，隨著無人機運動速度的提高，各算法抖動程度均有不同程度的降低，最短路徑算法抖動表現更優，改進路由算法次之，AODV表現較差。

從圖5～圖7總體分析，改進路由算法在無人機移動速度為1～2 m/s時丟包率稍差，平均抖動比最短路徑算法稍高；在其他無人機速度運動的狀態下，丟包率低，同時平均端到端時延和平均抖動均較低，整體性能最優。

4 結論

本文針對UANET中的網絡可靠性問題，提出了基于最短路徑的改進路由算法。介紹了UANET中的路由協議和最短路徑算法的原理，詳細闡述了改進算法的設計和路由策略。實驗根據丟包率、平均端到端時延、平均抖動參數指標來評估改進路由算法的性能，將改進路由算法和AODV與最短路徑算法對比仿真并分析結果，可以發現，在無人機隨機分布且隨機運動的高流量場景下，改進路由算法在整體性能上有一定的優勢，均衡了網絡負載，提高了網絡的可靠性和穩定性，進而證明了改進路由算法的有效性。