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

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

1 引 言

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

minT=F(x，t)

(1)

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

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

F(0，t)=t

(2)

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

Fmax(x，t)=Final

(3)

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

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

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

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

(4)

4 DPTM算法

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

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

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

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

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

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

(5)

其中，ζi為t時(shí)刻i無(wú)人機(jī)的鄰居節(jié)點(diǎn)集合.

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

F(0，t)=t

(6)

Fmax(i，t)=Final

(7)

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

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

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

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

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

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

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

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

表2 DPTM算法Table 2 DPTM algorithm

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

5 仿真實(shí)驗(yàn)及其分析

5.1 仿真設(shè)置

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

圖1 仿真實(shí)驗(yàn)場(chǎng)景圖Fig.1 Simulation experiment scene graph

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

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

表3 實(shí)驗(yàn)參數(shù)表Table 3 Experimental parameters

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

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

1)不同算法在不同間隔實(shí)驗(yàn)中的投遞率比較

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

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

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

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

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

4)不同算法在不同間隔實(shí)驗(yàn)中的乒乓比例比較

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

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

6 總 結(jié)

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

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