劉澤原，趙文棟，李艾靜，劉存濤

(陸軍工程大學(xué)通信工程學(xué)院，江蘇南京210000)

1 引言

當(dāng)前，由于無人機(jī)的高機(jī)動性、靈活控制性和經(jīng)濟(jì)性等優(yōu)勢，無人機(jī)偵察在搶險救災(zāi)、邊境巡查敵情獲取、戰(zhàn)場態(tài)勢感知等民用和軍用領(lǐng)域均得到了廣泛應(yīng)用。其一般過程如下：用戶基于自身對偵察目標(biāo)的信息需求，向無人機(jī)基地發(fā)送偵察服務(wù)請求；基地響應(yīng)用戶的請求并派遣無人機(jī)前往偵察區(qū)域?qū)ο鄳?yīng)目標(biāo)實(shí)施偵察；無人機(jī)獲取偵察信息后，將其直接或間接地回傳至無人機(jī)基地；而后由無人機(jī)基地將獲取的偵察信息分發(fā)給對應(yīng)的用戶[1，2]。目前，針對無人機(jī)偵察的研究大多數(shù)集中在多無人機(jī)服務(wù)于單用戶的情況[3-7]，且無人機(jī)不直接參與偵察信息的分發(fā)任務(wù)。

在實(shí)際應(yīng)用過程中，當(dāng)無人機(jī)基地與用戶之間的信道條件較差而無法實(shí)現(xiàn)高速數(shù)據(jù)傳輸時，采用DF(Data ferry)機(jī)制讓無人機(jī)直接參與到信息分發(fā)任務(wù)中不失為一個好的選擇。此時，如果無人機(jī)基地同時處理多個用戶的偵察服務(wù)請求，且不同用戶的信息需求存在重疊時，基于各用戶請求單獨(dú)進(jìn)行任務(wù)分配必然存在服務(wù)于不同用戶的無人機(jī)重復(fù)訪問同一偵察點(diǎn)的情況?；诙嘤脩舻男枨蠛霞M(jìn)行統(tǒng)一的任務(wù)分配，則會存在一架無人機(jī)獲取到多個用戶的需求信息的情況，從而在信息分發(fā)時造成多無人機(jī)對同一用戶的重復(fù)訪問。

本文提出了一種基于信息共享的多無人機(jī)協(xié)同偵察方法(Information Sharing based Cooperative Reconnaissance，ISCR)，采用集中式信息共享機(jī)制實(shí)現(xiàn)無人機(jī)信息獲取和信息交付的有機(jī)銜接：在信息獲取階段，采用基于多用戶需求聚合的任務(wù)分配策略實(shí)現(xiàn)對多個偵察任務(wù)的統(tǒng)一分配，避免多無人機(jī)對同一目標(biāo)的重復(fù)偵察；在信息共享階段，采用單用戶需求驅(qū)動的信息共享策略實(shí)現(xiàn)各個無人機(jī)偵察信息的補(bǔ)全，以使得各個無人機(jī)獲取其服務(wù)用戶所需的完整的偵察信息；在信息交付階段，實(shí)現(xiàn)無人機(jī)與用戶之間一對一的信息分發(fā)，避免多無人機(jī)對同一用戶的重復(fù)訪問。將上述問題建模為帶約束的無人機(jī)路徑規(guī)劃問題，并基于改進(jìn)的遺傳算法提出了一種低能耗的IETP(Information Exchange based Trajectory Planning)算法，對服務(wù)不同用戶的無人機(jī)進(jìn)行協(xié)同路徑規(guī)劃。

2 相關(guān)工作

通過任務(wù)規(guī)劃節(jié)省無人機(jī)能耗方面，當(dāng)前工作主要集中在單用戶下的任務(wù)規(guī)劃[3-7]，缺少對多用戶任務(wù)規(guī)劃的研究。文獻(xiàn)[3]構(gòu)建了一個多無人機(jī)協(xié)同偵察的場景，在同時考慮飛行能耗和懸停能耗的情況下對各無人機(jī)進(jìn)行了任務(wù)分配和路徑規(guī)劃，但其只把基地當(dāng)作唯一用戶，而沒有考慮基地為多個用戶服務(wù)的情況。文獻(xiàn)[4]考慮了無人機(jī)在目標(biāo)區(qū)域內(nèi)的停留時間對獲取的偵察信息大小的影響，研究了無人機(jī)能耗與收益平衡的問題。文獻(xiàn)[5]中利用地面?zhèn)鞲衅魈崆笆占瘋刹煨畔?，無人機(jī)則通過傳感器獲取相應(yīng)信息，降低了其在目標(biāo)區(qū)域獲取信息的時間及對應(yīng)的懸停能耗。同時學(xué)者還對無人機(jī)具有一定偵察范圍[6]以及各無人機(jī)飛行速度和起飛時間不同[7]等情況下的任務(wù)規(guī)劃問題進(jìn)行了研究，但這些研究同樣都只局限在滿足單一用戶的需求，多用戶下的無人機(jī)任務(wù)規(guī)劃仍有待研究。

在多目標(biāo)任務(wù)規(guī)劃方面，文獻(xiàn)[8]研究了無人機(jī)的協(xié)同合作問題，綜合考慮無人機(jī)任務(wù)類型的重疊互補(bǔ)關(guān)系，使無人機(jī)根據(jù)任務(wù)屬性形成相應(yīng)的群組執(zhí)行任務(wù)。文獻(xiàn)[9]在無人機(jī)提供信息傳遞的場景中考慮了不同用戶的服務(wù)質(zhì)量需求并對無人機(jī)進(jìn)行任務(wù)分配。文獻(xiàn)[10]考慮了多無人機(jī)協(xié)同偵察決策問題，在多目標(biāo)約束下平衡多任務(wù)區(qū)間的偵察收益。文獻(xiàn)[11]提出了一種事件驅(qū)動的無人機(jī)數(shù)據(jù)采集方法，使無人機(jī)能夠處理多目標(biāo)任務(wù)，最大化收集的總信息價值。然而在多用戶信息偵察的場景中，都沒有綜合考慮信息獲取和分發(fā)多用戶信息的過程。

3 系統(tǒng)模型與問題建模

3.1 系統(tǒng)模型

如圖1所示，假設(shè)基地附近存在多個用戶，基地中停靠多架無人機(jī)為用戶提供服務(wù)，同時在目標(biāo)區(qū)域中的每個偵察點(diǎn)放置一個傳感器為無人機(jī)提供偵察信息。無人機(jī)、傳感器和用戶分別表示為：U={u1，ui，…，um}，S={s1，sk，…，sr}和B={b1，bj，…，bn}。當(dāng)前考慮無人機(jī)數(shù)量較少的情況，假設(shè)無人機(jī)數(shù)量小于用戶數(shù)量。用Cj={sj(1)，sj(2)，…，sj(k)}表示當(dāng)前聯(lián)合規(guī)劃中的用戶bj需要集合內(nèi)傳感器的所有信息。首先，無人機(jī)從基地出發(fā)對被分配的目標(biāo)進(jìn)行偵察，隨后前往信息共享位置共享信息。進(jìn)行信息共享的無人機(jī)得到其服務(wù)用戶需要的完整信息，最后各無人機(jī)前往所服務(wù)的用戶附近分發(fā)信息。

圖1 ISCR偵察過程示意圖

3.2 ISCR過程

(1)

(2)

同時，當(dāng)無人機(jī)共享信息時，只能向其它無人機(jī)傳輸其已經(jīng)采集的信息，其約束條件表示為

(3)

(4)

(5)

3.3 問題建模

無人機(jī)路徑規(guī)劃的優(yōu)化目標(biāo)是在用戶能夠獲得需求信息集合內(nèi)的所有信息前提下，使無人機(jī)系統(tǒng)總能耗最小。無人機(jī)系統(tǒng)能耗主要由飛行能耗和懸停能耗組成，通信能耗相較飛行和懸停能耗過小，因而忽略。假設(shè)無人機(jī)以恒定速度v飛行，約束如式(6)所示

(6)

(7)

Li為ui的最終飛行長度，Pf(v)表示旋翼無人機(jī)推進(jìn)功率，可以表示為[12]

(8)

其中P0和Pi分別表示懸停狀態(tài)下的葉型功率和誘導(dǎo)功率，Utip為旋翼的葉邊速度，v0為懸停狀態(tài)下旋翼的誘導(dǎo)速度。d0為機(jī)身阻力比，s為轉(zhuǎn)子穩(wěn)定性。ρ和A分別表示空氣密度和旋翼旋轉(zhuǎn)的面積。同時，懸停功率表示為：

Ph=P0+Pi

(9)

無人機(jī)懸停能耗取決于無人機(jī)的懸停時間和懸停功率。在信息獲取階段，無人機(jī)懸停能耗來自于采集傳感器信息的過程，假設(shè)傳感器以恒定速率R傳輸信息，傳感器sk的信息量大小為Nk，則無人機(jī)在傳感器sk處的懸停能耗表示

(10)

無人機(jī)在信息共享階段，無人機(jī)懸停能耗來自于信息共享過程，假設(shè)調(diào)整各無人機(jī)出發(fā)時間，以保證其在同一時間到達(dá)信息共享區(qū)域，則無人機(jī)在信息共享點(diǎn)的懸停時間由接收信息大小和發(fā)送信息大小決定，則其在信息共享點(diǎn)的懸停能耗表示為

(11)

(12)

無人機(jī)i的總能耗為

(13)

綜上，本問題為采集信息共享機(jī)制情況下對多無人機(jī)進(jìn)行路徑規(guī)劃，使得無人機(jī)系統(tǒng)總能耗最小，形式化描述為式(14)

(14)

4 IETP算法描述

多無人機(jī)的路徑規(guī)劃可以轉(zhuǎn)化為每個無人機(jī)分配需要訪問的偵察目標(biāo)和所服務(wù)的用戶，即規(guī)劃函數(shù)f，χ和g，隨后根據(jù)每架無人機(jī)需要訪問的目標(biāo)點(diǎn)并確定組合順序。在該路徑規(guī)劃問題中，目標(biāo)分配問題和組合順序優(yōu)化問題兩者相互耦合，極大增加了求解的復(fù)雜度，其類似于同樣作為NP-hard問題的旅行商問題[13]或車輛路由問題[14]，難以求出最優(yōu)解或需要耗費(fèi)大量時間進(jìn)行求解。對于已確定所分配的目標(biāo)點(diǎn)的情況下的組合優(yōu)化問題，通常運(yùn)用遺傳算法[15]等啟發(fā)式算法進(jìn)行求解，其能夠在規(guī)定的迭代次數(shù)內(nèi)得出次優(yōu)解。而整數(shù)拆分方法則是一種可以遍歷對各無人機(jī)可能的目標(biāo)分配方案的數(shù)學(xué)方法。本文提出啟發(fā)式算法IETP，將遺傳算法與整數(shù)拆分相結(jié)合，并更改遺傳算法中適應(yīng)度函數(shù)值的計算方式，在多次迭代后尋找最佳路徑。下面簡單介紹遺傳算法和整數(shù)拆分，并對IETP算法細(xì)節(jié)進(jìn)行詳細(xì)介紹。

4.1 整數(shù)拆分

整數(shù)拆分方法將一個正整數(shù)用多個整數(shù)之和表示，IETP算法中，采集樹的形式表示整數(shù)拆分結(jié)果。在拆分樹中，層級0為虛擬層，僅代表根節(jié)點(diǎn)，且對于i，j(i>j)，層級i的值不小于層級j的值，層級中的一個整數(shù)值表示一架無人訪問偵察點(diǎn)的數(shù)量，同時拆分過程不考慮拆分順序以避免出現(xiàn)重復(fù)結(jié)果。假設(shè)3架無人機(jī)總共需要訪問5個目標(biāo)，則如圖4所示，其共有5種拆分方案。根據(jù)整數(shù)拆分方案，按順序?qū)⒁粭l個體拆分為各無人機(jī)的子路徑。例如，根據(jù)第4種拆分方案M4={1，1，3}，則無人機(jī)1需要訪問一個目標(biāo)點(diǎn)，無人機(jī)2訪問一個目標(biāo)點(diǎn)，無人機(jī)3訪問三個目標(biāo)點(diǎn)。

圖2 整數(shù)拆分示意圖

4.2 改進(jìn)遺傳算法

遺傳算法是依靠染色體編碼和變異原理衍生出的進(jìn)化算法，得出其具體操作包括染色體編碼、種群初始化、染色體選擇、并使用遺傳算子產(chǎn)生新的個體。多個遺傳個體構(gòu)成一個遺傳種群，其中個體表示一條遍歷所有偵察目標(biāo)和用戶的完整組合順序，個體中的一個染色體代表一個偵察點(diǎn)或用戶。利用整數(shù)拆分方法拆分遺傳個體，每個拆分方案可以將遺傳個體拆分為多個染色體片段，每個片段表示一架無人機(jī)被分配的訪問點(diǎn)及對應(yīng)的訪問順序。能夠滿足第3節(jié)中無人機(jī)偵察服務(wù)約束的拆分方案為正確的拆分方案，不能夠滿足偵察約束的拆分方案為錯誤的拆分方案。

圖3 遺傳個體拆分示意圖

如圖3所示，1-5號染色體為偵察目標(biāo)，6-7號染色體為用戶，按照拆分方案(1)對遺傳個體(2，4，6，3，8，1，5，7)進(jìn)行拆分并獲得三個染色體片段，片段1代表無人機(jī)1依次訪問染色體2，4，6代表的訪問點(diǎn)，表示無人機(jī)偵察目標(biāo)點(diǎn)2，4并為用戶6傳遞信息。無人機(jī)2偵察目標(biāo)3并為用戶8提供信息，無人機(jī)3偵察1，5并為用戶7提供信息。無人機(jī)根據(jù)訪問偵察目標(biāo)情況及其所服務(wù)用戶需求情況確定無人機(jī)之間的信息共享關(guān)系，以補(bǔ)足所服務(wù)用戶需求的所有信息。按照拆分方案(2)對遺傳個體拆分獲得染色體片段(2，4)，(6，4，8，1)以及(5，7)，按照此訪問順序無人機(jī)在訪問用戶6和8時無法為其提供需要的所有信息，則該拆分方案為錯誤拆分方案。

遺傳算法通過遺傳算子對種群中的遺傳個體進(jìn)行遺傳操作，遺傳個體完整保留的概率取決于該個體的適應(yīng)度函數(shù)值。在IETP算法中遺傳個體中使無人機(jī)系統(tǒng)總能耗最小的正確拆分方案作為該個體的最優(yōu)拆分方案，最小能耗值為該遺傳個體的適應(yīng)度函數(shù)值。遺傳算法是一個非常成熟的技術(shù)，這里不再對如何進(jìn)行遺傳操作詳細(xì)介紹。

4.3 IETP算法步驟

IETP算法將整數(shù)拆分和遺傳算法相結(jié)合，首先根據(jù)任務(wù)池內(nèi)所有用戶信息需求的并集得出需要訪問的偵察點(diǎn)集合S，根據(jù)集合S隨機(jī)生成多個初始遺傳個體組成初始遺傳種群，確定每個個體的適應(yīng)度函數(shù)值，并通過不斷進(jìn)行遺傳迭代，達(dá)到最大迭代次數(shù)后，跟遺傳種群中的適應(yīng)度函數(shù)值最小的遺傳個體及其最優(yōu)拆分方案確定各無人機(jī)被分配的偵察目標(biāo)及訪問順序，聯(lián)合其對應(yīng)的信息共享點(diǎn)和服務(wù)用戶確定無人機(jī)飛行路徑。IETP算法具體步驟總結(jié)如下：

1)確定偵察點(diǎn)集合S，并根據(jù)集合中的偵察點(diǎn)中生成包含N個遺傳個體的遺傳種群，確定最大迭代次數(shù)iter。

2)對每個遺傳個體進(jìn)行整數(shù)拆分，根據(jù)每個拆分方案為各無人機(jī)分配偵察目標(biāo)和用戶以及相應(yīng)的訪問順序，同時確定無人機(jī)之間的信息共享關(guān)系。

3)根據(jù)式(13)計算每個遺傳個體的每個成功拆分方案所產(chǎn)生的無人機(jī)系統(tǒng)總能耗，并判斷出各遺傳個體的適應(yīng)度函數(shù)值。

4)判斷是否達(dá)到最大迭代次數(shù)，達(dá)到最大迭代次數(shù)進(jìn)入步驟5)，否則對種群中的遺傳個體進(jìn)行遺傳操作，生成新的種群，重復(fù)步驟2)。

5)選出該種群中的適應(yīng)度函數(shù)值最小的個體，并將其最優(yōu)拆分方案結(jié)果作為無人機(jī)路徑規(guī)劃結(jié)果。

5 仿真結(jié)果及分析

5.1 仿真設(shè)置

為驗(yàn)證ISCR方法及對應(yīng)的IETP算法的有效性，采用MATLAB軟件進(jìn)行仿真，假設(shè)傳感器隨機(jī)分布在5km x 5km偵察區(qū)域內(nèi)，默認(rèn)傳感器數(shù)量為25。默認(rèn)基地需要同時處理3個用戶的偵察請求，每個用戶的需求信息集隨機(jī)生成。由于用戶之間可能存在相同的信息需求，用Ior表示用戶信息重合率，代表重合的信息需求占用戶總信息需求的比例，默認(rèn)值為30%。無人機(jī)基地的坐標(biāo)為(0，0，0)，能耗模型參數(shù)參考引用文獻(xiàn)[3][12]進(jìn)行設(shè)置，具體參數(shù)如表1所示。將針對用戶請求單獨(dú)進(jìn)行任務(wù)規(guī)劃的方法統(tǒng)一稱為PSTP(Plan Separate Trajectory Plan)，將其作為ISCR的對比方法，并利用遺傳算求解PSTP方法中的無人機(jī)路徑。圖4-圖7為路徑規(guī)劃結(jié)果的能耗對比圖。

表1 仿真參數(shù)

5.2 仿真分析

5.2.1 單架無人機(jī)能耗對比

圖4表示了在默認(rèn)參數(shù)設(shè)置下，PSTP方法和ISCR方法中的每架無人機(jī)能耗對比?？梢钥闯觯cPSTP相比，ISCR中每架無人機(jī)能耗更低，但是其較大的無人機(jī)在滿足用戶時效需求方面表現(xiàn)較差，因?yàn)槠湓诔袚?dān)自己用戶偵察任務(wù)的同時，又過多的承擔(dān)了其他用戶的偵察任務(wù)，因而IETP算法不適用于對信息時效性要求較高的場景。

圖4 無人機(jī)單獨(dú)能耗對比

另一方面，在PSTP中，每架無人機(jī)訪問的偵察點(diǎn)由所服務(wù)用戶的信息需求決定，存在偵察點(diǎn)被重復(fù)偵察的問題，而在ISCR模型中，各用戶的信息需求被合并成一個總的信息需求，并采集系統(tǒng)總能耗最小的方案將偵察點(diǎn)分配給各無人機(jī)，因而與PSTP相比，ISCR中每架無人機(jī)的能耗更小。

5.2.2 傳感器數(shù)目的影響

在默認(rèn)參數(shù)下，用戶信息集內(nèi)傳感器數(shù)量以固定比例隨偵察區(qū)域內(nèi)傳感器數(shù)量變化，則無人機(jī)系統(tǒng)能耗隨偵察區(qū)域內(nèi)傳感器數(shù)量變化的趨勢如圖5所示，與PSTP相比，ISCR中的系統(tǒng)總能耗降低了24%-28%。

圖5 無人機(jī)系統(tǒng)總能耗與傳感器數(shù)量關(guān)系

這是由于無人機(jī)之間通過信息共享的方式建立了一種協(xié)作能力，將距離其大部分偵察點(diǎn)遠(yuǎn)的傳感器交由其它無人機(jī)訪問，進(jìn)而減少無人機(jī)總的飛行路徑。特別的，當(dāng)用戶信息集相交時，通過信息共享方式可以使被重復(fù)需要的偵察信息僅被采集。

5.2.3 用戶數(shù)量的影響

無人機(jī)系統(tǒng)能耗隨用戶數(shù)量變化的趨勢如圖6所示。在給定用戶數(shù)量變化的范圍內(nèi)，與PSTP相比，ISCR中系統(tǒng)總能耗降低了7%-36%，且隨著用戶數(shù)量增加，ISCR的優(yōu)勢更加明顯。這是由于隨著用戶數(shù)量增加，PSTP中無人機(jī)系統(tǒng)需要訪問的傳感器總數(shù)增加，同時無人機(jī)往返于目標(biāo)區(qū)域和用戶之間的總距離增加，因而無人機(jī)系統(tǒng)總能耗增加。而ISCR中，由于信息共享方式存在，無人機(jī)系統(tǒng)需要訪問的傳感器總數(shù)不變，僅無人機(jī)往返于目標(biāo)區(qū)域于用戶之間總距離增加，因而總能耗增加緩慢。

圖6 無人機(jī)系統(tǒng)總能耗與用戶數(shù)量關(guān)系

5.2.5 信息需求重合率影響

無人機(jī)系統(tǒng)總能耗隨Ior變化如圖7所示，相比ISCR方法，PSTP中系統(tǒng)總能耗隨著Ior增大而更快的增長。這是由于當(dāng)Ior增大時，PSTP中無人機(jī)系統(tǒng)冗余訪問的偵察點(diǎn)增多，系統(tǒng)的運(yùn)動和懸停能耗增大，而在ISCR模型中，無人機(jī)系統(tǒng)避免了對偵察點(diǎn)的冗余訪問，隨著Ior增大，僅無人機(jī)在信息交付階段的懸停和通信能耗增加，增加的能耗遠(yuǎn)小于PSTP中增加的運(yùn)動和懸停能耗，因而 ISCR中系統(tǒng)總能耗增長較緩慢。

圖7 無人機(jī)系統(tǒng)總能耗與關(guān)系

6 結(jié)束語

為了解決多用戶無人機(jī)協(xié)同偵察中的多目標(biāo)點(diǎn)重復(fù)偵察問題以及多用戶重復(fù)訪問問題，提出一種基于信息共享機(jī)制的協(xié)同偵察方法ISCR，隨后以無人機(jī)系統(tǒng)總能耗最小為優(yōu)化目標(biāo)，提出一種啟發(fā)式算法IETP對服務(wù)不同用戶的無人機(jī)進(jìn)行路徑規(guī)劃。相比于針對單用戶需求驅(qū)動偵察方法，ISCR偵察方法能夠有效減少無人機(jī)系統(tǒng)能耗，且隨著用戶數(shù)量和信息重合率增加，其能耗節(jié)省優(yōu)勢更加明顯，但是不能采集ISCR為用戶獲取具有時間緊迫性的信息，同時該方法可能會使部分無人機(jī)承擔(dān)較多任務(wù)，產(chǎn)生各無人機(jī)能耗分布不均勻的情況。下一步工作將尋找無人機(jī)存在多個信息共享點(diǎn)并進(jìn)行多階段信息共享的情況，同時對此方法進(jìn)行改進(jìn)，使其能夠?yàn)橛脩魝刹炀哂袝r間敏感性的信息。