基于改進混合粒子群算法的無人機協同充電路徑規劃

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

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

1 引言

無線可充電傳感器網絡[1](wireless rechargeable sensor networks，WRSNS)由多個可充電的無線傳感器組成，具有穩定，抗干擾能力強，功耗低等優點，在許多方面有著廣泛的應用，而無線傳感器網絡的能量補充成為了制約其發展的主要問題[2]。目前較普遍的方式是通過無人機等移動充電設備對無線傳感網絡進行電能的補充，這樣既能節省成本，也不會導致網絡失效中斷。

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

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

2 系統模型與問題描述

2.1 系統模型

無線傳感網絡充電模型如圖1所示，該網絡由N個可充電的無線傳感器、1個可以對無人機進行調度的基站、k架無人機組成。無線傳感器位置隨機分布，用來收集和轉發區域內傳感器信息，k架無人機初始位于基站位置，基站根據無線傳感器任務量以及無人機的數量對多架無人機進行任務調度同時并能夠收集區域內所有無線傳感器的信息，多架無人機為區域內無線傳感器進行周期性充電，假設無人機在固定高度飛行。

圖1 統模型圖

2.2 問題描述

無人機對傳感器充電時采取懸停在傳感器正上方的方式，傳感器接受功率與無人機的發射功率之間的關系為[15]

(1)

式中：Pr為傳感器接收功率；Pt為無人機充電發射功率；d為無人機與傳感器之間的距離；β為距離改變時的補償參數。無人機完成任務的時間分為懸停充電和飛行時間，無人機全程勻速飛行，飛行時間Tf取決于無人機飛行的路徑長度，計算方式為

(2)

(3)

式中：Cmax為無線傳感器滿載時的電量；Ci表示第i個傳感器初始狀態剩余能量；Si為無人機的第i懸停點,在無人機到達傳感器之前，傳感器在持續消耗電量；p為傳感器消耗能量的速率；定義ti為無人機從開始充電任務直至到達第i個傳感器所花費的時間：

(4)

式中：Li-1,i為無人機從第i-1個傳感器到第i個傳感器的飛行距離。在充電任務中，不同無人機負責不同的傳感器，一架無人機同一時間只能對一個傳感器進行充電，無人機完成總任務時間Ttotal為無人機飛行時間和懸停充電時間之和

Ttotal=Tf+Thv

(5)

(6)

式中：l(x)為無人機的飛行路徑，本研究的目的是通過對k架無人機的路徑規劃，實現任務的平均分配，使得完成區域內所有傳感器充電任務時間最短，即耗時最大的無人機時間最少。數學模型表達如下

(7)

(8)

Ci-pti≥Elimit

(9)

3 算法描述

3.1 改進的粒子群算法

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

(10)

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

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

(11)

xid=xid+vid

(12)

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

(13)

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

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

輸出：充電路徑

初始化種群

whileiter

計算種群當前適應度fit

根據fit輪盤度選擇2個優秀父代a,b；

ifrand(0,1)

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

end

ifrand(0,1)

d=meta(a)

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

addcde到新種群

end

選取當前最優個體作為粒子群初代個體成員；

利用粒子群算法機制進行鄰域搜索；

更新種群個體；

end

Return充電路徑

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

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

2) 根據適應度函數計算出每個粒子的適應度值，求得粒子群的全局最優和個體最優，利用線性權重遞減公式來更新粒子的位置和速度。

3) 保留步驟2)中最優個體，對剩下的粒子通過遺傳算法的交叉、變異等方式增強粒子群多樣性，最后對遺傳算法獲得的粒子群進行適應度值計算。

4) 將保留下來的最優個體與遺傳算法獲得的粒子群適應度值進行比較，去除重復路徑，對粒子的適應度進行排序，按照種群規模保留較優粒子。

5) 重復步驟2)—4)，設置最大迭代次數為1 000次，當達到最大迭代次數時停止搜索，輸出最佳結果。

3.2 路徑分解算法

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

圖2 路徑分解流程

算法步驟為:

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

情況1：當分界點位于節點Si上

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

圖3 路徑分解圖

情況2：分界點位于邊Li上

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

圖4 路徑分解圖

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

4 仿真性能和結果分析

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

圖5為目標區域設置為200 m2，無人機數量設置為3，傳感器數量設置為100，3種算法下無人機為地面傳感器充電的飛行軌跡。

表1 仿真參數Table 1 Simulation parameters

圖5 不同算法下無人機飛行軌跡

4.1 傳感器數目的影響

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

圖6 最大時間與傳感器數量的關系

圖7 平均時間與傳感器數量的關系

圖8 時間方差與傳感器數量的關系

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

圖9 不同傳感器數量下每架無人機完成任務的時間

4.2 傳感器數目的影響

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

圖10 最大時間與無人機數量的關系

圖11 平均時間與無人機數量的關系

圖12 時間方差與無人機數量的關系

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

圖13 不同無人機數量下每架無人機完成任務的時間

4.3 目標區域大小的影響

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

圖14 最大時間與目標區域的關系

圖15 平均時間與目標區域的關系

圖16 時間方差與目標區域的關系

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

圖17 不同區域下每架無人機完成任務時間

4.4 無人機起點不同的影響

為了驗證PDA+LG-PSO算法的優越性，設置了不同的無人機起飛點，測試當無人機起飛點不同對3種算法無人機最大時間的影響。圖18為3種算法下無人機最大時間與不同起飛點坐標之間的關系，目標區域設定為200 m2，無人機架數設置為3，區域傳感器節點數目設置為100個，起點坐標從(0.0)到(200.200)，測試了5組坐標下3種算法無人機的最大時間。從測試結果來看，PDA+LG-PSO算法相比于其他2種算法在無人機最大值上仍然有明顯的優勢，起飛點坐標的變化對并沒有影響3種算法的最大時間。

圖18 最大時間與起點坐標的關系

5 結論

本文中研究了大規模無線可充電傳感網絡充電任務下的多無人機協同路徑規劃問題，以無人機完成任務時間作為優化目標，針對傳統多無人機路徑規劃任務分配不均衡的問題，提出了一種路徑分解算法，在對每架無人機進行路徑規劃時，又對粒子群算法進行了改進，在多個方面與KTSP-GA算法和K-MEANS+LG-PSO兩種算法進行了對比，根據仿真結果得出結論如下：

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

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

3) PDA+LG-PSO算法最大限度地實現了任務的平均分配，在大規模無線可充電網絡中非常適用。