逯建琦， 南建國， 李 雪

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

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

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

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

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

1 Dijkstra算法

1.1 Dijkstra算法簡述

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

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

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

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

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

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

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

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

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

2 網絡優(yōu)化參數

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

2.1 邊界評價因子

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

(1)

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

2.2 能量均衡參數

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

(2)

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

圖1 能量均衡原理圖

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

3 路由算法描述

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

3.1 邊權值的相關參數

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

(3)

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

(4)

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

δen=Ei0/Ei

(5)

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

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

(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是所有節(jié)點集合，V是節(jié)點間鏈路。ω(i，j)表示i點到j點的路徑權值，當i與j沒有建立路徑時，ω(i，j)為無窮大。網絡中每個節(jié)點建立一個statelist，包括2個字段，即記錄字段(記錄源節(jié)點和上一跳節(jié)點)和權值字段(記錄源節(jié)點到當前節(jié)點的權值之和，中間節(jié)點按照固定周期計算更新自身權值)。

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

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

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

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

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

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

圖2 節(jié)點示意圖

其中，節(jié)點0為源節(jié)點，節(jié)點1、2、3、4、5、9為其鄰居節(jié)點，源節(jié)點0廣播RREQ后，經過步驟4)、5)，根據邊界評價因子，節(jié)點4不作為中繼節(jié)點，根據能量均衡參數，節(jié)點3不作為中繼節(jié)點，節(jié)點1、2、5、9對RREQ進行轉發(fā)；根據式(9)，確定0→1→8路徑權值為11，0→2→8為9，根據Dijkstra，更新節(jié)點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規(guī)則進行路徑權值更新

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

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 路由維護

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

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

4 仿真分析

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

表1 仿真環(huán)境參數設置

圖4 仿真結果

1)投遞成功率

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

2)歸一化路由開銷

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

3)端到端時延

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

4)網絡生存周期

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

5 結語

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