改進的貪婪算法在無人機組網中的研究與應用

逯建琦， 南建國， 李 雪

(空軍工程大學航空工程學院， 西安， 710038)

隨著無人機技術的發展，無人機正向著軍事化、小型化的方向邁進。早在2016年，美軍就測試成功了“灰山鶉”無人機蜂群，這種無人機相對于普通無人機在體型上有明顯減小，可直接在軍用飛機上發射并進行協同作戰。由于通信范圍有限，此類小型無人機完成一次數據傳輸常需多個節點轉發實現，為保證各節點的信息交互，一般采用構建無線自組網的方式。

移動無線自組網(Mobile Ad-hoc Network)，是一種不依賴于現有基礎通信設備、網絡無中心、各節點平等且可以自由交流的自組織網絡，適用于無人機集群通信[1-5]。研究者們在網絡層上對自組網的研究多集中于路由算法的設計，高效的路由算法能夠提高數據包的傳輸效率，對自組網的應用具有重要意義。

傳統路由算法大多采用單一權值的路徑選擇標準，如Dijkstra算法，選擇路徑最短的路由；動態DSR[6-8]，選擇跳數最少的路由；Bellman-Ford算法則是一種基于泛洪的路由。這些算法的權值選擇過于單一，無法兼顧到網絡的整體性能。

相比于傳統算法，一些新型路由算法雖然在某些方面能顯示出良好性能，但大都是針對傳感器、車輛等平臺設計的。本文在小型軍用無人機集群組網的應用背景下，在AODV的基礎上對路由算法進行改進。利用優化參數過濾掉邊緣節點和低能節點，再用Dijkstra算法對能量-擁塞復合路徑權值進行更新，最后選擇權值最小的路徑進行數據傳輸。

1 Dijkstra算法

1.1 Dijkstra算法簡述

Dijkstra是一種常用的最短路徑算法，可用于計算源節點到目的節點的最短路徑，常以源節點為中心，層層向外擴展，直到擴展到目的節點為止[9]。設Q0表示源節點，Qn表示目的節點，Qi表示其他節點。

步驟1在節點通信范圍內，設節點間通信路由長度為lij，建立單向有源最短路徑矩陣G，用于存放各節點之間的有向距離，當Q0與Qn兩節點距離超出通信閾值時，矩陣中對應元素g0n為∞。

步驟2建立一個一維數組Dis用于存放各節點到Q0的路徑長度。初始時刻除Q0的鄰居節點外，其余節點與Q0的路徑長度定義為∞。因此Dis數組中僅Q0鄰居節點對應的元素dis為常數，其余均為無窮大。

步驟3對路徑進行搜索，當搜索到矩陣G中兩節點間路由長度存在：l0i=g01+g12+…+gmi

步驟4遍歷整個網絡，并記錄路徑，直到找到目的節點Qn與源節點Q0之間的最短路徑長度disn，所記錄的路徑即為最短路徑。

1.2 Dijkstra算法在路由方面的研究與應用

由于Dijkstra算法能夠找到最優解，且原理簡單，編程方便，因此很多研究者將它的最優化理念運用于路由算法中。傳統Dijkstra算法按照最短距離選擇路徑，在此基礎上進行改進，形成了將不同變量作為路徑選擇權值的改進路由算法。

文獻[10]將改進后的Dijkstra算法應用在WOBAN網絡中，形成最小時延算法(MDRA)。MDRA算法不會每次都向所有節點發送廣播，而是結合Dijkstra算法利用數據包的發送情況來預測整個網絡的鏈路狀態，達到簡化DARA算法的目的。文獻[11]提出一種能量高效均衡的圖路由算法，通過構建一種適用于無線HART圖路由的新型層次化網絡拓撲結構，將流量負載指標和鏈路傳輸能耗加入到貪婪算法中，利用改進的Dijkstra算法為節點分配子圖路由，達到平衡網絡中節點能量分布的目的。文獻[12]針對節點約束型路徑問題，將一維平面結構劃分為多層，分別在每一層中尋找約束點。該算法利用分層結構保存搜索進度和方便回溯的優勢，來尋找局部最優路徑以達到全局最優或次優路徑，雖然增加了空間復雜度，但可以減小Dijkstra算法的調用次數。

在當前改進的Dijkstra路由算法中，大多數是將時延和能量進行結合的路由算法[13-15]，很少考慮到節點的運動和數據流量情況，所以并不適合無人機組網。因此，研究一種路由算法能減小節點運動和數據流量對Qos造成的影響，有重要意義。

2 網絡優化參數

問題分析：①高速軍用無人機位置的移動會造成網絡拓撲的頻繁變化，出現通信鏈路斷裂的情況，因此路由算法要盡量避免選用邊緣節點;②無人機不能保證能量實時供應，部分節點會出現擔任中繼任務多能量消耗過快的情況。針對上述問題，本文提出網絡優化參數如下：

2.1 邊界評價因子

處于節點i最大通信范圍邊緣的節點j雖然可與i進行直接通信，但短時間內飛離i通信范圍的概率較大。因此本文設立邊界評價因子[16]來界定鏈路中不穩定的節點：

(1)

式中：Mij為i點與j點之間的邊界評價因子;R為最大通信距離;Lij為兩點之間的距離，可通過信號功率求得。Mij越大表明節點之間脫離通信范圍的概率越大。

2.2 能量均衡參數

在無人機集群中，中介中間性好的節點會因轉發數據造成能量消耗過快，導致其生命周期縮短[17]。為緩解“熱點”問題，本文提出能量均衡參數來避免中繼節點能量過快消耗的問題：

(2)

式中：EBPi為能量均衡參數；Eave為節點i與鄰居節點的平均剩余能量；Ei為i的剩余能量。EBPi越大，表明i點相對剩余能量越少。為防止節點過早死亡，應盡量避免選擇EBP大的節點作為中繼。具體過程見圖1。

圖1 能量均衡原理圖

由于圖中節點4廣泛性最好，因此擔任中繼節點的次數最多，計算可知EBP4較大，為保證網絡節點能量均衡，改選用0→1→3→5路徑對數據包進行轉發。

3 路由算法描述

無人機自組網除節點的移動性外，通信效果還受節點剩余能量、擁塞度的影響。選擇剩余能量小的路徑進行傳輸，會導致路徑上的低能節點增多，加速死亡；選擇擁塞度大的節點，會增加傳輸時延、降低數據包的投遞率，因此本文算法引入這2個參數。

3.1 邊權值的相關參數

1)節點剩余能量參數δen。無人機集群組網中節點是靠無線電進行通信的，通信時除了源節點和目的節點分別只發送和只接收數據包外，路徑中的其他節點都要接收并轉發數據包，我們定義節點能量消耗模型如下：

(3)

式中：ETi為節點i發送數據包消耗的能量；ERi為節點i接收數據包消耗的能量；Eelec為發射電路和接收電路消耗的能量，一般取Eelec=50 nJ/bit；L表示兩節點之間的距離；μ1、μ2分別為發射和接收數據包的比特數；ε是常數，一般取ε=10 pJ/(bit·m-2)。節點能耗表示為:

(4)

本文用節點剩余能量參數來衡量節點的能量狀況：

δen=Ei0/Ei

(5)

式中：Ei0為節點i初始時刻的能量；Ei為節點當前的剩余能量，可根據式(4)求得。δen值小的節點表明從初始時刻到現在，節點能量開銷較小。

2)節點擁塞度參數δco。緩存隊列越長的節點，新來的數據包需等待時間越久。當節點緩存已滿時，甚至會丟棄新來的數據包。為完成數據傳輸，節點需再次發送數據包，在增大時延的同時增加了額外開銷。為此設立節點擁塞度δco來衡量節點是否處于飽和狀態：

(6)

(7)

3.2 復合權值計算

復合型權值綜合考慮了δen、δco，由于衡量參數的量綱不同，因此在進行復合權值計算時要消除量綱差異，本文利用min-max原理對2個參數進行標準化，計算如下：

(8)

式中：定義相關參數X、X*為標準化后的參數指標，Xmin、Xmax分別為參數X在理想條件下的最小值和最大值。經過標準化處理后，所有參數指標都映射到[0，1]。i點的復合權值計算公式如下：

(9)

式中：λ是各參數的加權系數，λ的大小代表參數的重要程度，系數滿足λe+λc=1。

3.3 流程及算法描述

1)根據neighborlist中信息，建立鄰接矩陣。G(E，V)，E是所有節點集合，V是節點間鏈路。ω(i，j)表示i點到j點的路徑權值，當i與j沒有建立路徑時，ω(i，j)為無窮大。網絡中每個節點建立一個statelist，包括2個字段，即記錄字段(記錄源節點和上一跳節點)和權值字段(記錄源節點到當前節點的權值之和，中間節點按照固定周期計算更新自身權值)。

2)向路由維護中的hello消息包中添加節點自身的能量信息，節點定期將自身能量信息告知鄰居節點，并收集鄰居節點能量信息，判斷自身是否為“熱點”。

3)當源節點i要向目的節點j發送數據時，節點i先查看j是否在neighborlist中，若是，則直接利用與j已建立的路由進行數據發送；若否，執行下一步；

4)源節點發送RREQ路由消息包，其中主要包括消息包序號、源節點和目的節點編號、路由跳數、消息包經過的路徑權值ω(i，j)。中間節點接收到消息包后，首先判斷是否已轉發相同序號的RREQ消息包，若有且跳數小于等于此前的RREQ包，則根據Dijkstra算法，更新statelist，只保留ω(i，j)最小的反向路由，并再次轉發RREQ包。在這一過程中，轉發條件的限制可以避免循環重復發送RREQ，防止出現路由環路。由于一段時間內可能會發現權值更優的反向路徑，因此需要發送多個RREQ讓下游節點也進行反向路徑權值的更新，轉發節點每次對權值進行比較后，只保留最優權值。

5)若中間節點沒轉發過序號相同的RREQ包，則節點根據消息包功率大小，判斷是否超出邊界評價因子，若超出，則不轉發消息包，若未超出且自身不是“熱點”，更新statelist后進行轉發；

6)目的節點接收到RREQ后，發送RREP應答包，攜帶目的節點和源節點編號以及經過路徑的權值，當中間節點接收到RREP后，根據statelist中信息，為RREP分配權值小的上游路徑，每個中間節點至多轉發一次RREP；

7)源節點從接收到的前2個RREP中選擇權值最小的路徑進行數據包傳輸,另一條可作為備份，見圖2。

圖2 節點示意圖

其中，節點0為源節點，節點1、2、3、4、5、9為其鄰居節點，源節點0廣播RREQ后，經過步驟4)、5)，根據邊界評價因子，節點4不作為中繼節點，根據能量均衡參數，節點3不作為中繼節點，節點1、2、5、9對RREQ進行轉發；根據式(9)，確定0→1→8路徑權值為11，0→2→8為9，根據Dijkstra，更新節點8的statelist表，記錄字段為0、2，權值字段為9，建立起8→2→0反向路由。

算法流程見圖3。

圖3 算法流程圖

部分偽代碼如下：

輸入：Source i，Destination j

輸出：Route path

While i need to send data to j do

If j is in the neighborlist of i\查找是否可以直接進行通信

Then return route path

Else i broadcasts RREQ

While j doesn’t receive RREQ do

If RREQ is old and route hops are low

Then intermediate nodes update statelists in Dijkstra and broadcast RREQ

\按照Dijkstra規則進行路徑權值更新

Else if RREQ is new and intermediate nodes satisfy M and EBP\利用優化參數進行優化

Then update statelists and broadcast RREQ

Else throw RREQ

End If

End

j returns RREP with reverse path

i choose route path with smallest ω

Return route path

End

3.4 路由維護

無人機自組網中節點i每隔周期T向外廣播hello數據包來檢驗與鄰居節點之間的鏈路是否連通。若鄰居節點收到i節點的數據包，則證明鏈路通暢，直接將i節點的信息放入neighborlist中，若超過規定時間未收到i節點的hello包，則認為i節點已經脫離通信范圍，將i節點從neighborlist中刪除。

在i節點向目的節點傳輸數據包的過程中，若路徑上i的鄰居節點j由于移動導致i與j之間的鏈路斷裂，無法繼續傳輸，則i向上游節點發送RERR，并將j節點信息從neighborlist中刪除，上游節點收到RERR后，重新規劃路徑。

4 仿真分析

為驗證本文算法有效性，將本文算法與傳統算法進行對比驗證，仿真環境設置見表1,結果見圖4。

表1 仿真環境參數設置

圖4 仿真結果

1)投遞成功率

投遞成功率是指一定時間內正確接收的報文數量與發送報文總量的比值，是衡量網絡傳輸效率的重要指標。如圖4(a)所示，隨著節點移動速度的增大，網絡拓撲結構變化頻繁，導致3種算法的投遞成功率均有所下降。相比之下CWRA算法的投遞成功率較高，是因為算法中引入的邊界評價因子能夠避免選用處于通信范圍邊緣的節點，克服了邊緣效應，一定程度上可以減小鏈路斷裂的概率；權值中的擁塞度參數能避免選擇擁堵路徑，防止出現因節點緩存已滿導致數據包丟失的情況。

2)歸一化路由開銷

歸一化路由開銷是指每發送一個數據分組所需要的控制分組的數量，它可以反映網絡傳輸效率，從圖4(b)中可以看出，當節點速度較小時，相比于AODV，CWRA需要節點更多的信息，因此開銷相對較大。隨著節點速度的增長，3種算法的路由開銷均有所增加，CWRA算法上升趨勢較緩，是因為速度的增大導致另外2種算法路徑出現斷裂，產生額外的路由發現開銷。邊界評價因子的引入使得CWRA所選路徑對拓撲變化的適應性變強，減小了路由發現頻率。

3)端到端時延

端到端時延主要包括路由發現時延、數據包在接口隊列中的等待時延、發送時延、重傳時延等，時延在一定程度上影響著工作效能的發揮，結果如圖4(c)所示。隨著流量負載的增加，3種算法的時延都有明顯上升，是因為負載的增大導致部分節點出現擁塞。CWRA算法在權值中加入節點擁塞度，可以緩解擁塞路徑的傳輸壓力，減小數據包在接口隊列中的等待時延，達到減小端到端時延的效果。

4)網絡生存周期

網絡生存周期的定義為：網絡中出現第1個能量耗盡節點的時間。網絡生存周期能夠反映出網絡中節點能量均衡性，網絡體系越完整，對無人機集群任務的完成越有利。從圖4(d)中可以看出，隨著發包速率的增加網絡生存周期呈下降趨勢，CWRA算法在權值中加入的節點剩余能量參數使得源節點在選擇路徑的過程中可以選擇能量狀況良好的路徑，另外優化參數中的能量均衡參數可以避免相對能量低的節點出現在回溯路徑中，延長低能節點的生命周期。

5 結語

針對無人機集群組網的特點，本文在貪婪算法的基礎上提出能量-擁塞復合權值，能夠在兼顧時延的基礎上，篩選出穩定性較高的路徑。引入的網絡優化參數有效地提高了路徑對拓撲變化的適應性和網絡能量的均衡性。實驗結果表明，相比于另外2種路由算法，CWRA算法在投遞成功率、網絡生命周期、端到端時延、路由開銷等方面都有良好性能，這對于小型軍用無人機集群組網路由算法的研究和實際應用具有一定的參考價值。