田雨露,米志超，周雁翎,王 海,路顏霞

(1.陸軍工程大學(xué) 通信工程學(xué)院, 南京 210007； 2.解放軍93303部隊(duì)，沈陽 110000)

1 引言

無線可充電傳感器網(wǎng)絡(luò)[1](wireless rechargeable sensor networks，WRSNS)由多個(gè)可充電的無線傳感器組成，具有穩(wěn)定，抗干擾能力強(qiáng)，功耗低等優(yōu)點(diǎn)，在許多方面有著廣泛的應(yīng)用，而無線傳感器網(wǎng)絡(luò)的能量補(bǔ)充成為了制約其發(fā)展的主要問題[2]。目前較普遍的方式是通過無人機(jī)等移動(dòng)充電設(shè)備對(duì)無線傳感網(wǎng)絡(luò)進(jìn)行電能的補(bǔ)充，這樣既能節(jié)省成本，也不會(huì)導(dǎo)致網(wǎng)絡(luò)失效中斷。

無人機(jī)具有體積小、質(zhì)量輕，飛行速度快，能夠輕松的越過地面障礙到達(dá)指定區(qū)域，所以無人機(jī)攜帶大容量充電模塊為無線傳感網(wǎng)絡(luò)進(jìn)行補(bǔ)充能量的方式已經(jīng)逐漸成為大家研究的熱點(diǎn)[3-5]。目前主要的充電模式分為2種，一種是按需充電[6-7]，另一種是周期性充電[8]。在小規(guī)模無線可充電傳感網(wǎng)絡(luò)中，采取單移動(dòng)設(shè)備為傳感網(wǎng)絡(luò)充電的情況較為普遍[9]。在大規(guī)模傳感器網(wǎng)絡(luò)中，部分傳感器可能會(huì)出現(xiàn)長(zhǎng)期得不到充電而失效死亡的情況。為解決大規(guī)模無線可充電網(wǎng)絡(luò)充電問題，就需要引入多個(gè)移動(dòng)充電設(shè)備，文獻(xiàn)[10]中提出了一種多移動(dòng)充電設(shè)備充電調(diào)度方法，每個(gè)設(shè)備都按照預(yù)先規(guī)劃的路徑對(duì)自己所分配的傳感器進(jìn)行周期性充電，任務(wù)結(jié)束后回到基站。文獻(xiàn)[11]中提出將行駛距離、充電時(shí)間以及成本進(jìn)行加權(quán)處理，構(gòu)造新的成本目標(biāo)模型，采用改進(jìn)的鴿群混合遺傳算法求解加權(quán)后最小成本的充電路徑。文獻(xiàn)[12]中描述多無人機(jī)對(duì)多目標(biāo)進(jìn)行搜索，求解完成所有任務(wù)的最短時(shí)間，首先利用K-means聚類算法將目標(biāo)點(diǎn)進(jìn)行分類，再將分好的目標(biāo)點(diǎn)分配給多架無人機(jī)，利用改進(jìn)的遺傳算法對(duì)每架無人機(jī)的飛行路徑分別進(jìn)行求解。文獻(xiàn)[13]中提出一種基于節(jié)點(diǎn)重要級(jí)別的雙移動(dòng)設(shè)備協(xié)同充電的路徑規(guī)劃算法，將節(jié)點(diǎn)失效率與路徑能耗比總能量作為評(píng)價(jià)指標(biāo)，首先將傳感器與移動(dòng)充電設(shè)備的距離和移動(dòng)充電設(shè)備在移動(dòng)充電過程所剩余的能量作為匹配的依據(jù)，根據(jù)匹配度為兩個(gè)移動(dòng)充電設(shè)備分配待充電的傳感器，分配任務(wù)后根據(jù)傳感器所剩余的時(shí)間以及與移動(dòng)充電設(shè)備的距離確定傳感器充電的順序。

以上無人機(jī)協(xié)同任務(wù)方式均未考慮到無人機(jī)之間任務(wù)分配的公平性。在大規(guī)模充電網(wǎng)絡(luò)任務(wù)背景下，本研究中建立多無人機(jī)協(xié)同充電任務(wù)模型，將整體完成任務(wù)時(shí)間最短作為優(yōu)化目標(biāo)，可以表示為一個(gè)最小-最大的路徑覆蓋(min-max tour cover,MMTC)問題[14],讓所有無人機(jī)中完成任務(wù)最大的時(shí)間最小化，提出了一種路徑分解算法(path decomposition algorithm，PDA)，求得一條能夠覆蓋所有傳感器且飛行距離最短的路徑，通過路徑分解算法對(duì)得到的路徑進(jìn)行平均分解，將分解后得到的路徑片段首尾連接起點(diǎn)形成閉合路徑，在分配給每架無人機(jī)，在對(duì)每架無人機(jī)的路徑重新進(jìn)行規(guī)劃，求整體任務(wù)的完成時(shí)間最小。

2 系統(tǒng)模型與問題描述

2.1 系統(tǒng)模型

無線傳感網(wǎng)絡(luò)充電模型如圖1所示，該網(wǎng)絡(luò)由N個(gè)可充電的無線傳感器、1個(gè)可以對(duì)無人機(jī)進(jìn)行調(diào)度的基站、k架無人機(jī)組成。無線傳感器位置隨機(jī)分布，用來收集和轉(zhuǎn)發(fā)區(qū)域內(nèi)傳感器信息，k架無人機(jī)初始位于基站位置，基站根據(jù)無線傳感器任務(wù)量以及無人機(jī)的數(shù)量對(duì)多架無人機(jī)進(jìn)行任務(wù)調(diào)度同時(shí)并能夠收集區(qū)域內(nèi)所有無線傳感器的信息，多架無人機(jī)為區(qū)域內(nèi)無線傳感器進(jìn)行周期性充電，假設(shè)無人機(jī)在固定高度飛行。

圖1 統(tǒng)模型圖

2.2 問題描述

無人機(jī)對(duì)傳感器充電時(shí)采取懸停在傳感器正上方的方式，傳感器接受功率與無人機(jī)的發(fā)射功率之間的關(guān)系為[15]

(1)

式中：Pr為傳感器接收功率；Pt為無人機(jī)充電發(fā)射功率；d為無人機(jī)與傳感器之間的距離；β為距離改變時(shí)的補(bǔ)償參數(shù)。無人機(jī)完成任務(wù)的時(shí)間分為懸停充電和飛行時(shí)間，無人機(jī)全程勻速飛行，飛行時(shí)間Tf取決于無人機(jī)飛行的路徑長(zhǎng)度，計(jì)算方式為

(2)

(3)

式中：Cmax為無線傳感器滿載時(shí)的電量；Ci表示第i個(gè)傳感器初始狀態(tài)剩余能量；Si為無人機(jī)的第i懸停點(diǎn),在無人機(jī)到達(dá)傳感器之前，傳感器在持續(xù)消耗電量；p為傳感器消耗能量的速率；定義ti為無人機(jī)從開始充電任務(wù)直至到達(dá)第i個(gè)傳感器所花費(fèi)的時(shí)間：

(4)

式中：Li-1,i為無人機(jī)從第i-1個(gè)傳感器到第i個(gè)傳感器的飛行距離。在充電任務(wù)中，不同無人機(jī)負(fù)責(zé)不同的傳感器，一架無人機(jī)同一時(shí)間只能對(duì)一個(gè)傳感器進(jìn)行充電，無人機(jī)完成總?cè)蝿?wù)時(shí)間Ttotal為無人機(jī)飛行時(shí)間和懸停充電時(shí)間之和

Ttotal=Tf+Thv

(5)

(6)

式中：l(x)為無人機(jī)的飛行路徑，本研究的目的是通過對(duì)k架無人機(jī)的路徑規(guī)劃，實(shí)現(xiàn)任務(wù)的平均分配，使得完成區(qū)域內(nèi)所有傳感器充電任務(wù)時(shí)間最短，即耗時(shí)最大的無人機(jī)時(shí)間最少。數(shù)學(xué)模型表達(dá)如下

(7)

(8)

Ci-pti≥Elimit

(9)

3 算法描述

3.1 改進(jìn)的粒子群算法

粒子群算法容易早熟，并容易陷入局部最優(yōu)值，收斂速度慢，針對(duì)粒子群算法的缺點(diǎn)，在傳統(tǒng)粒子群算法的基礎(chǔ)上引入了線性遞減權(quán)重的方法(linearly decreasing weight，LDW)和遺傳算法中的交叉變異過程(genetic algorithm，GA)。粒子群算法中慣性因子ω對(duì)于粒子群算法的收斂性有較大的影響，慣性因子ω增大，有利于增強(qiáng)全局搜索能力，ω減小，有利于增強(qiáng)局部搜索能力，引入慣性權(quán)重遞減方法，使慣性因子ω隨迭代次數(shù)衰減，使得在搜索后期可以加速收斂，這種采用慣性權(quán)重根據(jù)迭代次數(shù)去進(jìn)行自適應(yīng)變化，相比于傳統(tǒng)粒子群收斂速度更快，算法后期局部搜索能力強(qiáng)，權(quán)重遞減為

(10)

式(10)中：ωmax、ωmin分別為慣性因子的最大和最小值，一般將ωmax設(shè)置為0.9，ωmin設(shè)置為0.2；k為當(dāng)前迭代次數(shù)，kmax為最大迭代次數(shù)。改進(jìn)后的粒子群速度位置更新表達(dá)式為

c1r1(pid-xid)+c2r2(pgd-xid)

(11)

xid=xid+vid

(12)

式(11)、式(12)是改進(jìn)后的粒子速度位置更新公式，但LDW改進(jìn)方法由于種群缺乏多樣性，仍存在陷入局部最優(yōu)的缺點(diǎn)，而遺傳算法種群規(guī)模較大，通過交叉變異不斷地?cái)U(kuò)大種群的多樣性，交叉操作是在種群中選取較大比例的個(gè)體，對(duì)選出的個(gè)體相互之間部分結(jié)構(gòu)進(jìn)行交叉互換，變異操作是在種群中選出小部分個(gè)體，使個(gè)體自身中部分結(jié)構(gòu)進(jìn)行改變，遺傳算法能夠求出優(yōu)化問題的全局最優(yōu)解，具有較強(qiáng)的魯棒性，適合于求解復(fù)雜的優(yōu)化問題，應(yīng)用較為廣泛。但是遺傳算法的收斂速度慢，局部搜索能力差。本文中將2種改進(jìn)方式結(jié)合，在粒子群算法基礎(chǔ)之上所改進(jìn)的算法簡(jiǎn)稱為L(zhǎng)G-PSO算法。首先對(duì)染色體進(jìn)行設(shè)置，將N個(gè)傳感器節(jié)點(diǎn)從1到N進(jìn)行編號(hào)，從左至右表示點(diǎn)被訪問的順序。一個(gè)完整的染色體就是無人機(jī)對(duì)N個(gè)傳感器充電訪問的次序，整個(gè)種群即為這N個(gè)傳感器訪問順序的全排列。即一個(gè)完整的序列表示一個(gè)解。對(duì)適應(yīng)度函數(shù)設(shè)置為

(13)

式中：fit代表適應(yīng)度函數(shù)，目標(biāo)函數(shù)Ttotal(max)為所有無人機(jī)路徑中飛行時(shí)間的最大時(shí)間最小，即目標(biāo)函數(shù)是求最小值，而適應(yīng)度值是越大越好，因此設(shè)定適應(yīng)度值等于目標(biāo)函數(shù)值的倒數(shù)，這樣適應(yīng)度越大表示目標(biāo)函數(shù)值越小，也就是解的質(zhì)量越高，LG-PSO算法實(shí)現(xiàn)過程為：

輸入：染色體數(shù)量、迭代次數(shù)、種群規(guī)模、交叉概率Pc、變異概率Pm、

輸出：充電路徑

初始化種群

whileiter

計(jì)算種群當(dāng)前適應(yīng)度fit

根據(jù)fit輪盤度選擇2個(gè)優(yōu)秀父代a,b；

ifrand(0,1)

c=cross(a,b)//選取的父代個(gè)體之間染色體交叉,交叉產(chǎn)生新的子代

end

ifrand(0,1)

d=meta(a)

e=meta(b)//選取的父代個(gè)體部分染色體變異,變異產(chǎn)生新的子代

addcde到新種群

end

選取當(dāng)前最優(yōu)個(gè)體作為粒子群初代個(gè)體成員；

利用粒子群算法機(jī)制進(jìn)行鄰域搜索；

更新種群個(gè)體；

end

Return充電路徑

LG-PSO算法算法具體步驟如下：

1) 初始化粒子群和遺傳算法參數(shù)，加速因子c1,c2設(shè)置為2，隨機(jī)數(shù)r1,r2在0,1之間隨機(jī)設(shè)置，遺傳交叉概率設(shè)置為0.9，變異概率設(shè)置為0.1，種群規(guī)模設(shè)置為200，隨機(jī)生成每個(gè)粒子的初始位置和速度。

2) 根據(jù)適應(yīng)度函數(shù)計(jì)算出每個(gè)粒子的適應(yīng)度值，求得粒子群的全局最優(yōu)和個(gè)體最優(yōu)，利用線性權(quán)重遞減公式來更新粒子的位置和速度。

3) 保留步驟2)中最優(yōu)個(gè)體，對(duì)剩下的粒子通過遺傳算法的交叉、變異等方式增強(qiáng)粒子群多樣性，最后對(duì)遺傳算法獲得的粒子群進(jìn)行適應(yīng)度值計(jì)算。

4) 將保留下來的最優(yōu)個(gè)體與遺傳算法獲得的粒子群適應(yīng)度值進(jìn)行比較，去除重復(fù)路徑，對(duì)粒子的適應(yīng)度進(jìn)行排序，按照種群規(guī)模保留較優(yōu)粒子。

5) 重復(fù)步驟2)—4)，設(shè)置最大迭代次數(shù)為1 000次，當(dāng)達(dá)到最大迭代次數(shù)時(shí)停止搜索，輸出最佳結(jié)果。

3.2 路徑分解算法

路徑分解算法過程如圖2所示，對(duì)其采用圖論的方式進(jìn)行描述，表示G=〈S,L〉,S中的每個(gè)節(jié)點(diǎn)代表無人機(jī)為傳感器充電的懸停位置，S=(S0,S1,…,Si,…,SN,)，L中的每條邊代表無人機(jī)在傳感器之間的飛行路徑,L=(L0,L1,…,Li,…,LN),定義路徑分界點(diǎn)為B=(B1,…,Bi,…,BN-1),分界點(diǎn)的作用是將路徑等分為k段，考慮到任務(wù)公平分配原則，將時(shí)間作為任務(wù)分配的依據(jù)，包括無人機(jī)飛行時(shí)間和為傳感器充電懸停的時(shí)間。

圖2 路徑分解流程

算法步驟為:

2) 根據(jù)路徑上累計(jì)的飛行時(shí)間和平均時(shí)間求得分界點(diǎn)，采用路徑分解算法分解路徑后分配給無人機(jī)。以第一個(gè)分界點(diǎn)為例，從無人機(jī)起飛點(diǎn)開始累計(jì)在此條路徑上飛行、懸停充電的時(shí)間Tj,當(dāng)Tj=Tave時(shí)，記錄下在路徑上無人機(jī)的位置點(diǎn)，作為第一個(gè)路徑分界點(diǎn)記為B1，分界點(diǎn)位置存在2種情況；

情況1：當(dāng)分界點(diǎn)位于節(jié)點(diǎn)Si上

圖3為分界點(diǎn)位于節(jié)點(diǎn)Si上的情況。將節(jié)點(diǎn)Si-1以及節(jié)點(diǎn)Si-1之前的路徑和節(jié)點(diǎn)分配給第1架無人機(jī)，節(jié)點(diǎn)Si-1作為第一架無人機(jī)的終點(diǎn)，刪除邊Li-1，得到第1架無人機(jī)的路徑。將節(jié)點(diǎn)Si作為第2架無人機(jī)的起點(diǎn)，無人機(jī)從節(jié)點(diǎn)Si累計(jì)在此條路徑上飛行、懸停充電的時(shí)間，當(dāng)再次達(dá)到Tj=Tave時(shí)，判斷分界點(diǎn)B2位于節(jié)點(diǎn)S還是位于邊L上，若B2位于節(jié)點(diǎn)S上，繼續(xù)按照此步驟尋找下一分界點(diǎn)B3，若B2位于邊上，則按照情況2步驟執(zhí)行。直至尋找到第k-1個(gè)分界點(diǎn)，將k個(gè)路徑片段完全分配給無人機(jī)結(jié)束。

圖3 路徑分解圖

情況2：分界點(diǎn)位于邊Li上

圖4為分界點(diǎn)位于邊Li上的情況，將Si節(jié)點(diǎn)以及Si之前的路徑和節(jié)點(diǎn)分配給第1架無人機(jī)，Si節(jié)點(diǎn)作為第1架無人機(jī)的終點(diǎn)，刪除邊Li，得到第1架無人機(jī)的路徑。將節(jié)點(diǎn)Si+1作為第2架無人機(jī)的起點(diǎn)，無人機(jī)從節(jié)點(diǎn)Si+1累計(jì)在此條路徑上飛行、懸停充電的時(shí)間，當(dāng)再次達(dá)到Tj=Tave時(shí)，判斷分界點(diǎn)B2位于節(jié)點(diǎn)還是位于邊上，若B2位于節(jié)點(diǎn)上，則按照情況1步驟執(zhí)行，若B2位于邊上，繼續(xù)按照此步驟尋找下一分界點(diǎn)B3，直至尋找到第k-1個(gè)分界點(diǎn)，將k個(gè)路徑片段完全分配給無人機(jī)結(jié)束。

圖4 路徑分解圖

3) 路徑分配給k架無人機(jī)后，將路徑片段連接原點(diǎn)形成閉合回路，利用LG-PSO算法對(duì)每架無人機(jī)閉合回路中包含的所有傳感器在進(jìn)行路徑規(guī)劃，求得每架無人機(jī)的耗時(shí)最短充電路徑。

4 仿真性能和結(jié)果分析

為了驗(yàn)證本文中所提出算法的優(yōu)越性，將最大時(shí)間、平均時(shí)間、時(shí)間方差作為評(píng)價(jià)指標(biāo)，分別對(duì)比了均值聚類加改進(jìn)粒子群算法(K-MEANS[12]+LG-PSO)和多旅行商遺傳算法(KTSP-GA[16])，傳感器初始電量在2～3 J之間隨機(jī)生成，部分仿真參數(shù)的設(shè)置如表1所示。

圖5為目標(biāo)區(qū)域設(shè)置為200 m2，無人機(jī)數(shù)量設(shè)置為3，傳感器數(shù)量設(shè)置為100，3種算法下無人機(jī)為地面?zhèn)鞲衅鞒潆姷娘w行軌跡。

表1 仿真參數(shù)Table 1 Simulation parameters

圖5 不同算法下無人機(jī)飛行軌跡

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

目標(biāo)區(qū)域設(shè)置為200 m2，無人機(jī)數(shù)量設(shè)置為3，圖6、圖7、圖8分別為3種算法的無人機(jī)最大時(shí)間、平均時(shí)間、方差的變化，隨著傳感器數(shù)量增多，3種算法的無人機(jī)最大時(shí)間、平均時(shí)間也隨之而增大。PDA+LG-PSO算法相比于KTSP-GA算法在最大時(shí)間上降低了5.45%～11.72%,在平均時(shí)間上降低了2.28%～7.74%，在時(shí)間方差上降低了38.15%～96.91%，相比于K-MEANS+LG-PSO算法在最大時(shí)間上降低了5.4%～29.28%，在平均時(shí)間上降低了1.21%～7.94%，在時(shí)間方差上降低了了24.14%～98.97%。PDA+LG-PSO算法在無人機(jī)最大時(shí)間、平均時(shí)間上能夠穩(wěn)定的增加，時(shí)間方差上變化幅度很小，基本上不受傳感器數(shù)量變化的影響，體現(xiàn)出算法穩(wěn)定的特點(diǎn)。KTSP-GA算法在無人機(jī)最大時(shí)間、平均時(shí)間上也能夠表現(xiàn)出穩(wěn)定的增加，但時(shí)間方差隨著傳感器數(shù)量的增加而增大。而K-MEANS+LG-PSO算法表現(xiàn)的不夠穩(wěn)定，在最大時(shí)間和方差上均波動(dòng)更大，KTSP-GA算法在無人機(jī)最大時(shí)間增加上存在不穩(wěn)定的情況，時(shí)間方差上也存在較大的波動(dòng)。

圖6 最大時(shí)間與傳感器數(shù)量的關(guān)系

圖7 平均時(shí)間與傳感器數(shù)量的關(guān)系

圖8 時(shí)間方差與傳感器數(shù)量的關(guān)系

圖9為在PDA+LG-PSO算法下，傳感器數(shù)量變化時(shí)的每架無人機(jī)完成任務(wù)時(shí)間，從圖9中可以看出，隨著傳感器數(shù)量增多，每架無人機(jī)的任務(wù)時(shí)間也隨之增加，3架無人機(jī)完成任務(wù)的時(shí)間差值很小，仿真結(jié)果證明了傳感器數(shù)量變化的條件下，PDA+LG-PSO算法仍然能夠表現(xiàn)出公平性。

圖9 不同傳感器數(shù)量下每架無人機(jī)完成任務(wù)的時(shí)間

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

目標(biāo)區(qū)域設(shè)定為200 m2,傳感器數(shù)量為100。圖10、圖11、圖12分別為3種算法無人機(jī)最大時(shí)間、平均時(shí)間、方差的變化，從其中可已看出，隨著無人機(jī)數(shù)量的增多，3種算法的無人機(jī)最大時(shí)間、平均時(shí)間隨之而減小，PDA+LG-PSO算法相比于KTSP-GA算法在最大時(shí)間上降低了4.98%～11.72%,在平均時(shí)間上降低了1.16%～7.74%，在時(shí)間方差上降低了了4.29%～94.48%，相比于K-MEANS+LG-PSO算法在最大時(shí)間上降低了16.31%～30.91%，在時(shí)間方差上降低了了56.32%～96.72%。

圖10 最大時(shí)間與無人機(jī)數(shù)量的關(guān)系

圖11 平均時(shí)間與無人機(jī)數(shù)量的關(guān)系

圖12 時(shí)間方差與無人機(jī)數(shù)量的關(guān)系

從圖11可以看出，當(dāng)無人機(jī)數(shù)量超過7架的時(shí)候，PDA+LG-PSO算法在平均時(shí)間上要高于K-MEANS+LG-PSO算法，PDA+LG-PSO算法并沒有體現(xiàn)出優(yōu)勢(shì)。圖12可以看出，K-MEANS+LG-PSO算法在方差上依舊表現(xiàn)出波動(dòng)較大。KTSP-GA算法隨著無人機(jī)數(shù)量的增加，時(shí)間方差變化曲線幅度較小，表現(xiàn)出相對(duì)比較平穩(wěn)，而PDA+LG-PSO算法隨著無人機(jī)數(shù)量的增加，方差也隨之增加，當(dāng)無人機(jī)數(shù)量為10的時(shí)候，基本上與KTSP-GA算法持平。圖13為PDA+LG-PSO算法下不同無人機(jī)數(shù)量時(shí)每架無人機(jī)完成任務(wù)的時(shí)間，從圖13中可以看出，隨著無人機(jī)數(shù)量的增多，每架無人機(jī)完成任務(wù)的時(shí)間隨之減少，但當(dāng)無人機(jī)數(shù)量超過5架的時(shí)候，最后一架無人機(jī)完成任務(wù)的時(shí)間相比于其他無人機(jī)完成任務(wù)的時(shí)間有明顯減少的趨勢(shì)，無人機(jī)數(shù)量的增加，最后一架無人機(jī)完成任務(wù)時(shí)間相比于其他無人機(jī)完成任務(wù)時(shí)間減少得越多，原因是因?yàn)樵诼窂椒纸膺^程中，由于部分路徑片段的刪除，導(dǎo)致分配給最后一架無人機(jī)的任務(wù)減少，所以無人機(jī)數(shù)量越多，刪除的路徑片段越多，最后一架無人機(jī)所分配的任務(wù)量越少，完成任務(wù)時(shí)間就會(huì)越少，這也是PDA+LG-PSO算法隨著無人機(jī)數(shù)量增加時(shí)間方差隨之增加的原因。當(dāng)無人機(jī)數(shù)量控制在一定數(shù)量下，無人機(jī)數(shù)量變化并不影響PDA+LG-PSO算法的公平性。

圖13 不同無人機(jī)數(shù)量下每架無人機(jī)完成任務(wù)的時(shí)間

4.3 目標(biāo)區(qū)域大小的影響

傳感器數(shù)量設(shè)置為100，無人機(jī)架數(shù)為3。圖14、圖15、圖16分別為3種算法無人機(jī)最大時(shí)間、平均時(shí)間、方差的變化，從其中可已看出，隨著傳感器區(qū)域的增大，3種算法的無人機(jī)最大時(shí)間、平均時(shí)間均隨之而增大。PDA+LG-PSO算法相比于KTSP-GA算法在最大時(shí)間上降低了 8.92%～11.72%,在平均時(shí)間上降低了4.86%～7.74%，在時(shí)間方差上降低了了88.16%～97.55%，相比K-MEANS+LG-PSO算法在最大時(shí)間上降低了8%～16.32%，在平均時(shí)間上降低了 2.05%～7.94%，在時(shí)間方差上降低了92.17%～98.51%。PDA+LG-PSO算法、KTSP-GA算法無論是在無人機(jī)最大時(shí)間還是平均時(shí)間上都表現(xiàn)出穩(wěn)定上升，而K-MEANS+LG-PSO算法雖然在無人機(jī)最大時(shí)間和平均時(shí)間上整體呈增加趨勢(shì)，但是仍舊表現(xiàn)的不夠穩(wěn)定，存在一定的波動(dòng)，時(shí)間方差上波動(dòng)更大，PDA+LG-PSO算法在時(shí)間方差上表現(xiàn)的仍然非常穩(wěn)定，并沒有隨著區(qū)域的增大而引起較大的變化。

圖14 最大時(shí)間與目標(biāo)區(qū)域的關(guān)系

圖15 平均時(shí)間與目標(biāo)區(qū)域的關(guān)系

圖16 時(shí)間方差與目標(biāo)區(qū)域的關(guān)系

圖17為采用PDA+LG-PSO算法下不同區(qū)域下每架無人機(jī)完成任務(wù)的時(shí)間，從其中可以看出，隨著目標(biāo)區(qū)域的增大，每架無人機(jī)的任務(wù)時(shí)間也隨之增加，但3架無人機(jī)完成任務(wù)的時(shí)間差值很小，仿真結(jié)果證明了在區(qū)域變化的條件下，PDA+LG-PSO算法仍然能夠表現(xiàn)出公平性。

圖17 不同區(qū)域下每架無人機(jī)完成任務(wù)時(shí)間

4.4 無人機(jī)起點(diǎn)不同的影響

為了驗(yàn)證PDA+LG-PSO算法的優(yōu)越性，設(shè)置了不同的無人機(jī)起飛點(diǎn)，測(cè)試當(dāng)無人機(jī)起飛點(diǎn)不同對(duì)3種算法無人機(jī)最大時(shí)間的影響。圖18為3種算法下無人機(jī)最大時(shí)間與不同起飛點(diǎn)坐標(biāo)之間的關(guān)系，目標(biāo)區(qū)域設(shè)定為200 m2，無人機(jī)架數(shù)設(shè)置為3，區(qū)域傳感器節(jié)點(diǎn)數(shù)目設(shè)置為100個(gè)，起點(diǎn)坐標(biāo)從(0.0)到(200.200)，測(cè)試了5組坐標(biāo)下3種算法無人機(jī)的最大時(shí)間。從測(cè)試結(jié)果來看，PDA+LG-PSO算法相比于其他2種算法在無人機(jī)最大值上仍然有明顯的優(yōu)勢(shì)，起飛點(diǎn)坐標(biāo)的變化對(duì)并沒有影響3種算法的最大時(shí)間。

圖18 最大時(shí)間與起點(diǎn)坐標(biāo)的關(guān)系

5 結(jié)論

本文中研究了大規(guī)模無線可充電傳感網(wǎng)絡(luò)充電任務(wù)下的多無人機(jī)協(xié)同路徑規(guī)劃問題，以無人機(jī)完成任務(wù)時(shí)間作為優(yōu)化目標(biāo)，針對(duì)傳統(tǒng)多無人機(jī)路徑規(guī)劃任務(wù)分配不均衡的問題，提出了一種路徑分解算法，在對(duì)每架無人機(jī)進(jìn)行路徑規(guī)劃時(shí)，又對(duì)粒子群算法進(jìn)行了改進(jìn)，在多個(gè)方面與KTSP-GA算法和K-MEANS+LG-PSO兩種算法進(jìn)行了對(duì)比，根據(jù)仿真結(jié)果得出結(jié)論如下：

1) PDA+LG-PSO算法對(duì)比KTSP-GA算法和K-MEANS+LG-PSO算法，在整體完成任務(wù)時(shí)間、時(shí)間均值、方差等方面上實(shí)現(xiàn)了較大的性能提升。

2) 無人機(jī)起飛點(diǎn)的不同并不影響PDA+LG-PSO算法的性能。

3) PDA+LG-PSO算法最大限度地實(shí)現(xiàn)了任務(wù)的平均分配，在大規(guī)模無線可充電網(wǎng)絡(luò)中非常適用。