基于路徑規劃的無人機加權高效分簇方法

嚴 磊,雷 磊,蔡圣所,路志勇

(1.南京航空航天大學 電子信息工程學院,南京 210016; 2.中國電子科技集團公司第五十四研究所,石家莊 050081)

0 概述

無人機編隊網絡不依賴任何固定的基礎設施,由具有無線收發功能的無人機節點組成。為了提高編隊網絡的可擴展性,無人機編隊網絡普遍采用分級式的網絡結構,即對網絡實施分簇管理[1]。

均衡網絡中無人機節點的負載和能耗,延長網絡的最大生存周期是無人機分簇算法的一個重要實現目標。在網絡中,簇首負責簇內成員之間的通信和簇內成員與其他簇成員之間的通信服務,因此,實現分簇算法的關鍵在于選擇合理的無人機節點擔任簇首[2]。

文獻[3]提出的最小ID號算法通過節點的ID號對網絡進行分簇。在分簇過程中,選取相鄰節點中ID號最小的節點擔任簇首,簇首的一跳范圍內還未加入其他簇的鄰居節點加入該簇;在剩余未確定身份的節點中,重復以上步驟,直至每個無人機節點獲得自己的身份。雖然該算法具有實現方便,計算量小等優點,但是由于較小ID號的節點頻繁地被最小ID號算法選擇擔當簇首,而簇首需要負責簇內成員以及簇間成員通信任務,因此電池能耗遠大于簇成員?？赡軙驗榇厥椎碾娏垦杆俸谋M,導致網絡的生命周期[4]被嚴重的縮短。

文獻[5]提出的加權分簇算法(WCA)。在最小ID號算法的基礎上,綜合考慮了節點的相對移動性、理想節點度[6]及電池電量[7]等因素,對每一種影響因素分別賦予不同的權重比例,從而生成最終的權重,以此評價節點擔任簇首的能力。在該算法中,優先選擇相對移動性低,剩余電量較多且節點度合理的節點擔任簇首,實現節點間的負載均衡,延長了網絡的生命周期。

最小ID號算法和WCA雖然在一定程度上延長了網絡的生命周期,但是它們都沒有充分考慮到網絡中無人機編隊的拓撲變化對分簇結構的影響。在現有的無人機分簇算法中,無人機普遍采用自由運動模型實現無人機的飛行運動,而這并不符合無人機飛行的實際情況。事實上,由于無人機飛行一般都攜帶任務,它們的航線軌跡都是被提前規劃好的。所以在無人機的高效分簇算法的設計中,為了實現網絡的負載均衡[8],達到延長網絡的生命周期的目的,還必須同時考慮無人機編隊拓撲變化帶來的影響[9]。

本文通過無人機路徑規劃算法實現對無人機編隊飛行線路的設計,同時充分考慮在路徑規劃條件下無人機編隊網絡拓撲變化對分簇結構的影響。在此基礎上,提出基于路徑規劃的簇首加權選舉算法(Weighted Head Election Algorithm based on Path-planning,WHEA-P)和基于路徑規劃的簇成員加權調整算法 (Weighted Hluster Adjustment Algorithm based on Path-planning,WCAA-P)。

1 基于路徑規劃的無人機網絡加權高效分簇

針對現有的無人機分簇算法沒有充分考慮路徑規劃條件下,無人編隊網絡拓撲變化對分簇結構的影響帶來的弊端,本文在基于粒子群算法(POS)的無人機路徑規劃的基礎上,實現了2種基于路徑規劃的無人機網絡加權高效分簇方法(WHEA-P和WCAA-P)。

1.1 基于POS的無人機路徑規劃

POS[10]是一種受到飛鳥集群活動規律啟發而提出的進化算法,已廣泛應用于無人機網絡部署[11]。本文采用文獻[12]提出的POS實現了無人機在多障礙物的環境下的路徑規劃。POS相比遺傳算法而言,沒有變異和交叉運算,僅僅借助于粒子的速度完成搜索,因此具有搜索速度快、實現簡單等優點。此外它還擁有記憶性,記憶粒子群體的歷史最好位置并且將它傳遞給其他粒子,優化粒子的迭代結果,提高粒子的適應度。在該算法中,首先在無人機初始位置放置一群隨機粒子,然后通過計算每個粒子的適應度[13]進行迭代,直至找到最終目標。在生成的所有粒子路徑軌跡中,找到一條遠離威脅區且距離最短的路線,即為無人機的最佳飛行線路。圖1給出了在20 km×20 km的仿真監控區域中3架無人機的路徑規劃,其中小圓圈代表無人機的起點,x代表無人機的終點,大圓圈代表威脅區。

圖1 在20 km×20 km的仿真監控區域中3架無人機的路徑規劃

1.2 WHEA-P原理

WHEA-P在簇首選舉階段考慮了相對移動速率這一指標的弊端,用穩定度S替代相對移動速率,作為分簇的重要權重指標進行考慮。穩定度S反映了每個競選簇首的節點擁有的穩定的鄰居節點的個數。穩定的鄰居節點是競選簇首的節點的鄰居節點,并且在分簇周期內到競選簇首的節點的距離始終小于最大傳輸距離。競選簇首的節點擁有的穩定的鄰居節點的數目越多,則它的穩定度越高,當選簇首的概率也就越大。此外,選舉節點擔任簇首還需要考慮節點的剩余能量P和節點的節點度d。簇成員的能耗要遠低于簇首的能耗,因此應當優先選擇電量充足的節點擔任簇首。簇首節點擁有的成員節點的數量超出所能承受的門限值,會帶來網絡性能下降和簇首節點能耗的大幅提高等弊端,嚴重情況下會導致網絡的癱瘓。因此,在簇首選舉時,節點的理想節點度D和節點度d的差值也是一個重要的影響因素。

1.2.1 相對移動速率的弊端

在WCA中,無人機的相對移動速率是評判無人機能否成為簇首的一個重要指標。文獻[14]提出可以根據計算各節點的平均運動速度計算節點的相對移動性。假設節點u的鄰居節點集合為Nu,節點u相對鄰居節點v的速度為V(u-v),則節點u相對于所有鄰居節點的平均運動速度定義為:

(1)

節點的相對移動速率越小,擔任簇首的概率越大。但在實際情況下,無人機相對移動速率這一指標很難客觀準確地評定無人機之間的相對移動性。[t,t+Δt]時刻簇內無人機運動情況如圖2所示。

圖2 [t,t+Δt]時刻簇內無人機的運動情況

由圖2觀察可以看出,鄰居節點v1、v2朝向簇首u運動,鄰居節點v3、v4遠離簇首u運動。雖然根據式(1)計算得出的在t+Δt時刻無人機的相對移動速率減小,但是由于鄰居節點v3、v4到簇首u的距離超過最大傳輸距離R,導致簇首u的簇成員反而減少,因此簇首u不適合繼續擔任簇首。

1.2.2 穩定度計算

在[t,t+Δt]分簇周期內,在選舉t時刻的簇首時,需要計算t時刻每個競選簇首的節點i的穩定度Si(t)。借助路徑規劃獲取的無人機飛行路線,可以計算[t,t+Δt]分簇周期內t時刻節點i的穩定度Si(t)。Nnbr,i(t)是t時刻競選簇頭的節點i的鄰居節點的集合,Si(t)初始化為Nnbr,i(t)集合中鄰居節點的數目。在[t,t+Δt]分簇周期內,選取n個均勻離散的時間點,在每個離散的時間點分別計算Nnbr,i(t)集合中的每個鄰居節點到競選簇首節點i的距離,如果它們的距離超過傳輸距離R,那么就將當前鄰居節點從Nnbr,i(t)集合中移除,同時Si(t)做減1處理。最終就可以求得t時刻節點i的穩定度Si(t)。計算穩定度的偽代碼如下所示。

算法1t時刻節點i的穩定度Si(t)

Si(t):Stability of node i at t moment

Nnbr,i(t):Set of nodes at range of cluster head’s transmission distance R at t moment

BEGIN

1.initial Si(t) which equals the number of neighbor nodes in Nnbr,i(t)

2.initial ttemp←t,r←0

3.while ttemp

4. for each neighbor node j in Nnbr,i(t)

5.if distance between neighbor node j and node i >transmission distance R then

6.Si(t)←Si(t)-1

7.remove neighbor node j from Nnbr,i(t)

8.end if

9.end

10.r←r+1

11.ttemp←t+r*Δt/n

12.end while

1.2.3 WHEA-P具體步驟

WHEA-P步驟如下:

步驟1開始階段,依次給每個無人機節點按照從小到大分配ID號,然后利用最小ID號算法對無人機網絡進行初始分簇。

步驟2每個簇首選舉周期,各節點根據其剩余電量、穩定度及節點度計算權值W:

W=wpP+wsS+wd|d-D|

(2)

其中,wp、ws、wd為權值系數,權值大小可以根據實際情況進行設定,但是必須滿足wp+ws+wd=1,d為鄰居一跳范圍內無人機節點的個數,D為理想節點度,可以考慮無人機的架數除以仿真范圍內簇的數目求得,當然也可以根據實際情況動態調整,S為無人機節點的穩定度,P為無人機節點的剩余能量。

步驟3簇首獲取簇內簇成員的權值W。

步驟4簇首將接收到的權值按照從大到小的順序進行排序,然后重新向簇內成員分配ID號。分配原則如下:擁有最大權值W的節點獲得最小ID號,擁有最小權值W的節點獲得最大ID號。若存在擁有相同W值的2個節點,則簇首隨機選擇一個節點,使它獲得較小的ID號。

步驟5簇首向其成員節點發送新的ID號。

步驟6成員節點用新的ID號替換舊的ID號,然后調用最小ID號算法進行重新分簇。

1.3 WCAA-P原理

WCAA-P分為簇首選舉和簇成員調整2個階段,其中簇成員調整階段是WCAA-P的主要創新之處。簇首選舉階段通過WCA確定簇首;簇成員調整階段每個簇成員節點借助無人機路徑規劃生成的飛行線路,分別考慮與每個簇首的飛行線路的接近程度和該簇首的簇內成員個數。計算簇成員到每個簇首的飛行線路的接近程度,可以通過在簇成員飛行線路上選取n個有代表性的離散點,再計算出簇成員到簇首的平均歐拉距離,用來反映飛行線路的接近程度。此外為了避免簇內成員過多導致負載不均衡,還須要考慮簇成員選擇加入的簇,它的簇內成員個數與理想節點度D的差值的情況。最終求出權值,綜合考慮后選擇最合適的簇首,加入該簇。每個簇成員依次重復上面的過程,計算出到每個簇首的權值,然后選擇最合適的簇首,加入該簇。該算法確保每個簇成員都能選擇合適的簇首,并且保證每個簇首擁有合理的簇成員數。

1.3.1 WCAA-P具體步驟

WCAA-P步驟如下:

步驟1開始階段,依次給每個無人機節點按照從小到大分配ID號,然后利用最小ID號算法對無人機網絡進行初始分簇。

步驟2每個簇首選舉周期,各節點根據WCA計算出的權值W進行分簇,確定簇首。

步驟3借助路徑規劃獲得的無人機編隊的拓撲結構和飛行線路,計算每個簇成員到每個簇首節點i平均歐拉距離Li和對應簇首i的節點度di。

例如,在t時刻進行分簇,執行完步驟2確定簇首后,在[t,t+Δt]分簇周期內選取n個均勻的離散時間點并且根據路徑規劃中[t,t+Δt]時間內的無人機編隊的飛行線路,求出每個簇成員到每個簇首節點i的n個時刻平均歐拉距離Li和對應簇首i的節點度di。

(3)

其中,Li,j為j時刻簇成員到簇首i的歐拉距離,j為[t,t+Δt]分簇周期內取得的n個均勻離散的時間點,i=1,2,…,N且i為簇首。

步驟4簇成員根據平均歐拉距離Li和節點度di計算到每個簇首的權值Wi,每個簇成員依次選取權重值最大的簇首,加入該簇,成為簇成員。

Wi=εLi+(1-ε)|di-D|

(4)

其中,i=1,2,…,N且i為簇首,ε為權重系數,可以根據實際需求進行設定,Wi為當前簇成員到簇首i的權值,Li當前簇成員到簇首i的平均歐拉距離,di為簇首i的節點度,D為理想節點度。

1.3.2 WHEA-P和WCAA-P比較分析

WHEA-P和WCAA-P分別在簇首選舉階段和簇成員調整階段考慮無人機編隊的拓撲結構和飛行線路的影響,實現節點的負載均衡,達到延長網絡生存時間的目的。相比較而言,WHEA-P選擇穩定度高的節點擔任簇首,簇內穩定的簇成員數目較多。因此簇首相比WCAA-P變動頻率更低,簇首結構更加穩定,很少存在簇首由于簇內沒有任何簇成員而尋求加入其他簇成為簇成員的情況。而WCAA-P中簇成員相比WHEA-P更加穩定,變動頻率更低,這是因為每個簇成員依照自己的飛行線路,優先選擇與自身飛行線路最為接近的簇首,并加入該簇。因此簇成員脫離原有簇的概率大大降低,簇結構更加穩定。

2 仿真與結果分析

本文在Matlab環境中實現了2種無人機加權分簇的改進算法(WHEA-P和WCAA-P),并且對2種改進算法與最小ID號算法和WCA的性能進行了對比和分析。在無人機分簇算法中,網絡生存時間是重要的性能指標。網絡生存時間定義為從無人機網絡初始化到網絡中首個節點死亡的時間[15]。主要仿真參數如表1所示。

表1 仿真參數

2.1 WHEA-P中穩定度的權重系數取值

本文通過改變WHEA-P中穩定度的權重大小ws,研究該算法中網絡生存周期(算法執行周期數)與穩定度的權重大小的關系。圖3指出了無人機網絡生存周期與穩定度的權重在不同仿真實驗環境下的變化關系。由圖3所示的仿真結果可知,在20 km×20 km的仿真監控區域中,當穩定度的權重系數ws接近0.5時,網絡生存周期取得最大值。因為當算法中穩定度的權重系數過小,無法充分體現出路徑規劃條件下,無人機編隊網絡拓撲變化對分簇結構的影響;而當穩定度權重系數過大,也不能充分反映WHEA-P中其他因素(例如節點剩余能量和無人機節點度與理想節點度的差)帶來的影響。本文給出參數ws的建議取值區間為:

ws∈[0.45,0.55]

(5)

圖3 穩定度的權重系數ws對網絡生存周期的影響

2.2 基于路徑規劃的無人機分簇算法仿真

假定每個簇成員節點的能耗與該節點到其簇首節點的距離成正比,簇首的能耗與簇內成員節點的數目成正比。設置無人機的初始能量值為2 000。本文借助于路徑規劃,對最小ID號算法(本文所有圖中標為LeastID)、WCA及2種改進的無人機加權分簇算法(WHEA-P和WCAA-P)的性能進行了詳細的仿真實驗與對比分析。圖4展示了在20 km×20 km的仿真實驗區域中無人機節點的數量由20到100架的情況下,基于路徑規劃的4種算法的仿真對比結果。

圖4 基于路徑規劃的4種算法仿真結果對比

由圖4可以看出,根據WHEA-P和WCAA-P獲得的網絡生存時間比最小ID號算法和WCA的網絡生存時間長。無人機的網絡生存時間會隨著無人機的架數的增多而減小。產生這種變化的原因在于隨著無人機架數的增多,簇內簇成員的數目不斷增加,由于簇首的能耗與其成員節點的個數成比例,簇首的能量會急劇損耗,最終導致整個網絡生存周期的縮短。但是隨著無人機架數的增加,WHEA-P和WCAA-P性能要遠遠優于最小ID號算法和WCA。當無人機架數等于100的時候,WHEA-P和WCAA-P的網絡生存時間要比WCA延長50%左右。

網絡終止時無人機的平均剩余能量也是反映網絡生命周期的一個重要指標。網絡終止時,無人機的平均剩余能量越多,則網絡負載越不均衡,網絡的生存周期越短。結合圖5可以看出,當無人機架數大于60架時,WHEA-P和WCAA-P的平均剩余能量要遠小于最小ID號算法和WCA。

圖5 網絡終止后無人機的平均剩余能量

無人機平均重入簇次數是評價簇結構穩定性的一個重要指標。無人機節點重新加入其他簇的次數越少,那么簇的結構越穩定。如圖6所示,單位時間內節點重入簇次數隨節點的傳輸距離增大而減小。因為傳輸范圍越大,簇的統治范圍越大,節點脫離原有簇的概率減小。由于WCAA-P在簇成員調整階段,每個簇成員根據拓撲結構的變化,選擇飛行線路與自身最為接近的簇首,并加入該簇,因此相對其他3種算法而言性能最好,簇的穩定性最強。

圖6 單位周期內平均重入簇次數

無人機簇統治集更新次數[16]也可以用來評價簇結構的穩定性。本算法規定當節點脫離原來的簇,而無法加入其他簇,則自己成為簇首,并觸發統治集更新。圖7反映了單位周期內無人機簇統治集更新次數隨無人機傳輸距離變化的情況。隨著傳輸距離的增大,無人機簇統治集更新次數變少。同樣也是因為隨著傳輸范圍變大,簇的統治范圍變大,節點脫離原有簇的概率變小。相比較而言,由于WHEA-P在簇首選舉階段選取的簇首節點具有鄰居節點數目多,變動頻率低和穩定性強的優點,因此很少存在簇首節點由于簇內沒有任何簇成員節點而尋求加入其他簇,成為簇成員的情況?？梢钥闯?WHEA-P簇首結構穩定度高,性能要略優于其他3種算法。

圖7 單位周期內無人機簇統治集更新次數

WHEA-P和WCAA-P性能要優于最小ID號算法和WCA,它們的仿真指標曲線都非常接近。這是因為WHEA-P和WCAA-P分別在簇首選舉階段和簇成員調整階段考慮無人機編隊網絡的拓撲變化對分簇結構的影響。WHEA-P中通過穩定度S這一參數,選擇最合適的無人機節點擔任簇首,保證了無人機簇內簇成員的個數的穩定和數量的合理,實現了負載均衡,降低了簇首的能耗負擔,從而增大了網絡的生存周期。而WCAA-P在確定簇首后,每個簇成員借助于路徑規劃獲得的飛行線路,通過比較自身與每個簇首的飛行線路的接近程度,并考慮每個簇首的簇內成員個數,選擇最合適的簇首,成為其簇成員,也實現了網絡的負載均衡和節點能耗的降低,延長了網絡的生存周期。

3 結束語

本文針對現有的無人機分簇算法在沒有充分考慮路徑規劃條件下,無人編隊網絡拓撲變化對分簇結構的影響所帶來的弊端,采用基于PSO的無人機路徑規劃,實現了2種基于路徑規劃的無人機加權高效分簇方法(WHEA-P和WCAA-P)。WHEA-P和WCAA-P分別在簇首選舉階段和簇成員調整階段考慮無人機編隊網絡的拓撲結構變化帶來的影響,從而實現均衡節點負載,延長網絡生存時間的設計目標。仿真結果表明,WHEA-P和WCAA-P的性能要優于最小ID號算法和WCA,它們的網絡生存周期更長并且負載更加均衡。在今后的研究工作中,將會繼續考慮通信方式、服務質量、網絡安全對無人機編隊網絡能耗的影響,進一步改進分簇方法,延長網絡生存周期。