一種動態(tài)規(guī)劃下的無人機(jī)消息傳輸路徑優(yōu)化方法

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

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

1 引 言

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

minT=F(x，t)

(1)

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

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

F(0，t)=t

(2)

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

Fmax(x，t)=Final

(3)

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

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

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

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

(4)

4 DPTM算法

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

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

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

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

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

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

(5)

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

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

F(0，t)=t

(6)

Fmax(i，t)=Final

(7)

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

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

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

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

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

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

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

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

表2 DPTM算法Table 2 DPTM algorithm

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

5 仿真實驗及其分析

5.1 仿真設(shè)置

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

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

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

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

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

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

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

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

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

2)不同算法在不同間隔實驗中的平均時間延遲比較圖3結(jié)果表明，DPTM算法較其他幾個算法，在不同的F下時間延遲均得到了減少.原因在于DPTM算法根據(jù)所有無人機(jī)每一時刻的位置信息，得到消息能盡快到達(dá)地面站的最優(yōu)路徑.DTNgeo只考慮當(dāng)前時刻的位置信息，DTNclose和DTNload也都只考慮了下一時刻的位置，如此得到的消息傳輸對象對于當(dāng)前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來說是最優(yōu)的，然而對于不斷變化的無人機(jī)網(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ù)所有無人機(jī)每一時刻的位置信息，事先規(guī)劃好最優(yōu)傳輸路徑，讓無人機(jī)記住每一時刻的傳輸對象，若能建立通信鏈路則傳輸，否則攜帶，這樣減少了消息傳輸?shù)牟槐匾獊砘亍捌古摇?，從而得到較少的平均跳數(shù).DTNgeo只考慮當(dāng)前時刻的位置信息，DTNclose和DTNload也都只考慮了下一時刻的位置，如此得到的消息傳輸對象對于當(dāng)前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來說是最優(yōu)的，然而對于不斷變化的無人機(jī)網(wǎng)絡(luò)，消息很可能在未來某一時刻又被重新傳回來，這就導(dǎo)致不必要的來回“乒乓”傳輸，造成平均跳數(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)傳輸路徑、完全消除乒乓比例.然而在無人機(jī)實際執(zhí)行任務(wù)過程中，消息傳輸速率雖快，但也需消耗時間，所以對于一些連接時間極短、負(fù)載過多的情況，有無人機(jī)可能不能將消息按照規(guī)劃全部傳輸給當(dāng)前規(guī)劃好的下一跳，使部分消息錯過最優(yōu)對象可能造成小比例的乒乓.即便如此DPTM算法還是大幅的降低了乒乓比例，減少了時間延遲.

6 總 結(jié)

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

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