朱霏霏，王立松，劉 亮，葛子淵

(南京航空航天大學 計算機科學與技術(shù)學院，南京 210000)E-mail ：zhu_feifei95@163.com

1 引 言

無人機是全球新一輪科技革命和產(chǎn)業(yè)革命的熱點，其產(chǎn)業(yè)發(fā)展關(guān)乎國家利益.對于很多需要無人機的任務，往往需要一個無人機組協(xié)同作業(yè)完成任務[1].此時，如何根據(jù)無人機組網(wǎng)絡(luò)特性運用路由策略將消息快速傳回到地面站就成了一個重要的技術(shù)問題[2].

無人機間通過無線傳輸建立高吞吐量鏈路，形成一個臨時的、多跳的區(qū)域連接，是一種移動自組織網(wǎng)絡(luò)[3].然而，由于無人機的高速不斷運動，無人機的網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化頻繁.傳統(tǒng)的MANET路由方法運用在無人機上出現(xiàn)投遞率低、消息傳輸時間延遲大等問題，大大影響網(wǎng)絡(luò)性能[4].

因此有必要對無人機網(wǎng)絡(luò)路由策略提出更高的要求，有針對性地開展相關(guān)研究.由于現(xiàn)階段利用無人機的很多場景都是基于任務驅(qū)動的[5]，人為地事先規(guī)劃好無人機的運動軌跡，無人機只需按照規(guī)劃好的軌跡運動即可[6]，現(xiàn)有很多方法[7，8]僅考慮無人機的當前位置狀態(tài)，沒有充分考慮現(xiàn)階段的無人機基于任務驅(qū)動的這一特性，導致難以找到消息傳輸?shù)淖顑?yōu)對象.

針對以上問題，對于無人機基于任務驅(qū)動每時刻位置可知的情況，本文充分利用該特性提出了一種動態(tài)規(guī)劃下的無人機消息傳輸路徑優(yōu)化方法，該方法通過全局考慮所有無人機每一時刻的位置，得到每一時刻消息傳輸?shù)淖顑?yōu)對象，進而得到消息到達目的節(jié)點的最優(yōu)路徑，減少消息傳輸?shù)摹捌古倚睆亩_到減少時間延遲的目的.此外，由于該方法避免了消息的很多不必要傳輸，使得更多消息能到達地面站，達到提高消息傳輸投遞率的目的.

2 相關(guān)工作

針對無人機組的拓撲結(jié)構(gòu)頻繁變化的網(wǎng)絡(luò)特性，很多研究者對其進行了研究，路由方法主要包括：

1)傳統(tǒng)的無線自組織路由方法：文獻[9]將傳統(tǒng)的路由協(xié)議OLSR等運用在兩個微型飛機和地面站的網(wǎng)絡(luò)中，結(jié)果表明由于無人機的高速運動，傳統(tǒng)的路由協(xié)議無法適應和快速應對快速變化的拓撲結(jié)構(gòu).主要原因在于傳統(tǒng)的移動自組織路由協(xié)議都需要一定程度的鏈路穩(wěn)定性來收斂[10]，而無人機的網(wǎng)絡(luò)拓撲變化極快、鏈路的建立和斷裂極度頻繁，難以在極短的連接時間內(nèi)改變傳輸對象，使得消息傳輸?shù)膶ο蠛芸赡懿皇亲顑?yōu)傳輸對象，造成傳輸效率低下[11].

2)DTN路由算法：由于無人機的消息允許存儲攜帶，另一類方法是基于DTN網(wǎng)絡(luò)考慮[12]，DTN玩過是一種適用間歇性連接的方法，純粹的DTN路由方法如Epidemic Routing、Spray and Wait算法，通常適用于移動節(jié)點的有限泛洪且網(wǎng)絡(luò)處于長時間斷開狀態(tài)[13]，使得網(wǎng)絡(luò)中節(jié)點攜帶很多不必要的信息，易造成網(wǎng)絡(luò)擁堵，同時也增大消息傳輸?shù)拈_銷，造成很大的時間延遲，不利于消息的傳輸[14].

3)基于地理位置的路由方法：文獻[15]中將地理位置路由和DTN算法相結(jié)合，提出DTNgeo算法，將消息轉(zhuǎn)發(fā)給空間上離目的節(jié)點更近的點，但此方法只考慮無人機當前位置，易造成消息的來回傳輸，實驗顯示“乒乓比例”很大.結(jié)合無人機運動信息可用的特點，文獻[15]另外提出兩個啟發(fā)式算法DTNclose、DTNload，根據(jù)無人機當前的運動狀態(tài)預測很短時間之后的未來時刻位置[16]，將消息轉(zhuǎn)發(fā)給未來離目的節(jié)點較近的鄰居節(jié)點，以達到消息盡早到達地面站的目的[17].這兩種啟發(fā)式算法僅僅只考慮下一時刻的位置信息，沒有盡可能多的考慮以后時刻的位置，消息傳輸給目的節(jié)點的路徑可能仍不是最優(yōu)傳輸路徑，實驗結(jié)果顯示“乒乓效應”比例仍然很大，時間延遲仍有可優(yōu)化空間.

3 無人機消息傳輸?shù)臅r間消耗模型

基于無人機消息傳輸?shù)奶攸c，建立無人機消息傳輸消耗時間的數(shù)學模型如下：

minT=F(x，t)

(1)

其中x表示無人機ID，x的范圍為[1，N](N為執(zhí)行任務的無人機的個數(shù))，特別地，我們定義地面站的ID為0；t表示某一時刻；F表示在t時刻x無人機上攜帶的消息最早到達地面站的時刻.

特別地，當消息到達地面站時，消息傳輸過程結(jié)束，由此可以得到公式(1)的一個特殊值：

F(0，t)=t

(2)

此外，無人機在執(zhí)行任務過程中，即使消息沒法以多跳的形式傳輸給地面站，在任務結(jié)束時也會飛回地面站將消息帶回，所以消息最晚到達地面站的時刻為任務結(jié)束時刻，即：

Fmax(x，t)=Final

(3)

結(jié)合無人機消息傳輸?shù)奶匦裕趖時刻無人機x消息的傳輸策略為如下兩種之一：

1)transmit：若將消息傳輸給其某個鄰居節(jié)點可以使消息更早到達地面站，則t時刻將該消息transmit給它的那個鄰居節(jié)點.

2)carry：若當前節(jié)點相比其鄰居節(jié)點可以使消息更早到達地面站，則carry.

t時刻的消息傳輸策的略選擇只要考慮該策略使消息到達地面站的時間順序，選擇消息到達地面站時間較早的作為t時刻無人機x的消息傳輸對象.由此我們可以得到：

(4)

4 DPTM算法

基于第3節(jié)的無人機消息傳輸?shù)臅r間消耗模型，這一節(jié)介紹一種動態(tài)規(guī)劃下的無人機消息傳輸路徑優(yōu)化方法——DPTM算法.首先，介紹DPTM算法中用到的幾個變量及其含義如表1所示.

表1 變量含義表Table 1 Meaning table of variables

對于計算任意i無人機每一時刻的消息傳輸對象next(i，T)，DPTM算法的具體步驟如下：

步驟1.定義狀態(tài)函數(shù)，得到狀態(tài)轉(zhuǎn)移方程及狀態(tài)轉(zhuǎn)移方程的邊界條件.

由上一節(jié)無人機消息傳輸?shù)臅r間消耗模型，得到無人機i在t時刻的狀態(tài)函數(shù)：F(i，t)；

由公式(4)，得出無人機i的狀態(tài)轉(zhuǎn)移方程：

(5)

其中，ζi為t時刻i無人機的鄰居節(jié)點集合.

此外，根據(jù)公式(2)(3)得到i無人機的狀態(tài)轉(zhuǎn)移方程的邊界條件：

F(0，t)=t

(6)

Fmax(i，t)=Final

(7)

步驟2.采集所有無人機每一時刻的位置.

由于無人機的運動軌跡由地面站實現(xiàn)規(guī)劃好，所以地面站可以得到所有無人機每一時刻的位置，得到location(N，T).

步驟3.計算無人機間的距離，得到i無人機t時刻可通信的鄰居節(jié)點.

計算t時刻i無人機與其余任意j無人機的距離d(i，j)，將i與其他無人機間距離記錄至d(N，N).若?j∈N，d(i，j)≤Range，則無人機i與無人機j可進行通信，將j并入集合ζi，最終得到無人機i在t時刻的鄰居節(jié)點集合ζi.

步驟4.根據(jù)狀態(tài)轉(zhuǎn)移方程(5)得到當前時刻的傳輸下一跳，直至迭代更新完所有時刻，得到無人機每一時刻的最優(yōu)消息傳輸對象.

根據(jù)公式(5)-公式(7)，首先比較當前時刻與下一時刻的狀態(tài)函數(shù)值，若下一時刻的狀態(tài)函數(shù)值F較小，則將消息carry.當F(i，t+1)

更新完F(N，T)和next(N，T)后，令t=t+1，并判斷是否到達Final時刻，若t

隨著時間的推移，該算法最終迭代收斂得到無人機在每一時刻的消息傳輸對象next(N，T)，具體算法如表2所示.

表2 DPTM算法Table 2 DPTM algorithm

無人機組在執(zhí)行任務過程中按照DPTM算法得到的傳輸對象進行傳輸，在執(zhí)行過程中若當前無法與其通信，則carry，直到可與該傳輸對象進行通信才transmit.

5 仿真實驗及其分析

5.1 仿真設(shè)置

本文用The ONE仿真器實現(xiàn)對DTNgeo、DTNclose、DTNload和DPTM的路由算法仿真.仿真場景為基于任務驅(qū)動的典型場景-偵查搜救，為了盡快找到目標人物并解救，由地面站事先規(guī)劃好每個無人機的運動軌跡，收集地面消息并快速傳輸回地面站[18].仿真實驗借用文獻[15]中無人機數(shù)目最多的情況，如圖1所示.

圖1 仿真實驗場景圖Fig.1 Simulation experiment scene graph

其中Ground為地面站，MAV7-11為searching MAV，執(zhí)行搜尋任務并收集信息，同時也可以作為消息傳輸?shù)闹欣^；MAV2-5為ferry MAV，只作為中繼，幫助searching MAV將消息快速傳輸?shù)降孛嬲?搜尋軌跡如圖中所示，無人機間相互協(xié)作將搜尋到的消息盡快傳輸?shù)降孛嬲綠round，由地面站拼湊出正片區(qū)域內(nèi)的地形地貌，找到目標人物所在位置.

此外，實驗過程中的具體參數(shù)設(shè)置如表3所示.

表3 實驗參數(shù)表Table 3 Experimental parameters

5.2 仿真結(jié)果和分析

實驗中分別針對不同大小的時間間隔F進行實驗，根據(jù)The one仿真實驗的數(shù)據(jù)，以投遞率、平均時間延遲、平均跳數(shù)、乒乓比例作為評價指標，整理分析得到DPTM與DTNgeo、DTNclose和DTNload算法的結(jié)果.

1)不同算法在不同間隔實驗中的投遞率比較

圖2結(jié)果表明在實驗時間8min中，這四種路由算法的投遞率都很高，均在85%以上，DPTM相比較其他算法，投遞率上升到90%.由于DPTM算法能得到消息的最優(yōu)傳輸路徑，避免了其他算法過程中很多不必要的傳輸，使得更多消息能到達地面站.

2)不同算法在不同間隔實驗中的平均時間延遲比較圖3結(jié)果表明，DPTM算法較其他幾個算法，在不同的F下時間延遲均得到了減少.原因在于DPTM算法根據(jù)所有無人機每一時刻的位置信息，得到消息能盡快到達地面站的最優(yōu)路徑.DTNgeo只考慮當前時刻的位置信息，DTNclose和DTNload也都只考慮了下一時刻的位置，如此得到的消息傳輸對象對于當前的網(wǎng)絡(luò)拓撲結(jié)構(gòu)來說是最優(yōu)的，然而對于不斷變化的無人機網(wǎng)絡(luò)，某一時刻最優(yōu)的對象對于整個過程來說很可能不是最優(yōu)，所以造成較大的平均時間延遲.

圖2 DPTM與DTNgeo、DTNclose和DTNload算法的投遞率對比圖Fig.2 ComparisonofdeliveryratiobetweenDPTMandDTNgeo,DTNcloseandDTNloadalgorithms圖3 DPTM與DTNgeo、DTNclose和DTNload算法的平均時間延遲對比圖Fig.3 ComparisonofaveragedelaybetweenDPTMandDTNgeo,DTNcloseandDTNloadalgorithms

3)不同算法在不同間隔實驗中的平均跳數(shù)比較

圖4結(jié)果表明，DPTM算法較其他幾個算法，在不同的F下跳數(shù)均得到了減少.原因在于DPTM算法根據(jù)所有無人機每一時刻的位置信息，事先規(guī)劃好最優(yōu)傳輸路徑，讓無人機記住每一時刻的傳輸對象，若能建立通信鏈路則傳輸，否則攜帶，這樣減少了消息傳輸?shù)牟槐匾獊砘亍捌古摇?，從而得到較少的平均跳數(shù).DTNgeo只考慮當前時刻的位置信息，DTNclose和DTNload也都只考慮了下一時刻的位置，如此得到的消息傳輸對象對于當前的網(wǎng)絡(luò)拓撲結(jié)構(gòu)來說是最優(yōu)的，然而對于不斷變化的無人機網(wǎng)絡(luò)，消息很可能在未來某一時刻又被重新傳回來，這就導致不必要的來回“乒乓”傳輸，造成平均跳數(shù)增加.

4)不同算法在不同間隔實驗中的乒乓比例比較

圖4 DPTM與DTNgeo、DTNclose和DTNload算法的平均跳數(shù)對比圖Fig.4 ComparisonofaveragehopcountbetweenDPTMandDTNgeo,DTNcloseandDTNloadalgorithms圖5 DPTM與DTNgeo、DTNclose和DTNload算法的乒乓比例對比圖Fig.5 Comparisonofping-pongratiobetweenDPTMandDTNgeo,DTNcloseandDTNloadalgorithms

圖5結(jié)果表明DPTM算法能使乒乓比例大幅下降至5%以下.根據(jù)DPTM算法的理論分析，該算法能找到最優(yōu)傳輸路徑、完全消除乒乓比例.然而在無人機實際執(zhí)行任務過程中，消息傳輸速率雖快，但也需消耗時間，所以對于一些連接時間極短、負載過多的情況，有無人機可能不能將消息按照規(guī)劃全部傳輸給當前規(guī)劃好的下一跳，使部分消息錯過最優(yōu)對象可能造成小比例的乒乓.即便如此DPTM算法還是大幅的降低了乒乓比例，減少了時間延遲.

6 總 結(jié)

本文提出一種動態(tài)規(guī)劃下的無人機消息傳輸路徑優(yōu)化方法，通過全局考慮所有無人機每一時刻的位置，得到每一時刻消息傳輸?shù)淖顑?yōu)對象，進而得到消息到達目的節(jié)點的最優(yōu)路徑，達到降低乒乓比例、減少時間延遲和減少能源損耗的目的.通過仿真實驗將DPTM與DTNgeo、DTNclose和DTNload算法相比較，結(jié)果表明DPTM算法在消息投遞率方面稍有提高；在平均時間延遲上有了近6%的降低，當傳輸重要數(shù)據(jù)比如本文中提到的搜救場景中目標人物的周邊消息時，6%的降低可給搜救節(jié)省很多的時間，提高人物的得救率；在平均跳數(shù)方面，平均跳數(shù)降低至4.8以下，減少傳遞跳數(shù)，可減少無人機用于傳輸過程中的能量浪費，使其將更多的能量用于搜索信息方面；在乒乓比例方面，乒乓比例有了明顯的降低，降低至5%以下，使無人機將盡可能多的能量用于執(zhí)行任務，較少能源浪費.

由于現(xiàn)階段很多無人機的應用場景都是由地面站事先規(guī)劃好運動軌跡，如本文中實驗的偵查搜救場景，無人機只需按地面站事先規(guī)劃好的軌跡運動即可，所以該算法在現(xiàn)階段的無人機組通信中具有重要意義.