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

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

0 概述

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

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

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

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

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

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

1 基于路徑規(guī)劃的無人機網(wǎng)絡加權高效分簇

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

1.1 基于POS的無人機路徑規(guī)劃

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

圖1 在20 km×20 km的仿真監(jiān)控區(qū)域中3架無人機的路徑規(guī)劃

1.2 WHEA-P原理

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

1.2.1 相對移動速率的弊端

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

(1)

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

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

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

1.2.2 穩(wěn)定度計算

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

算法1t時刻節(jié)點i的穩(wěn)定度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開始階段,依次給每個無人機節(jié)點按照從小到大分配ID號,然后利用最小ID號算法對無人機網(wǎng)絡進行初始分簇。

步驟2每個簇首選舉周期,各節(jié)點根據(jù)其剩余電量、穩(wěn)定度及節(jié)點度計算權值W:

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

(2)

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

步驟3簇首獲取簇內(nèi)簇成員的權值W。

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

步驟5簇首向其成員節(jié)點發(fā)送新的ID號。

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

1.3 WCAA-P原理

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

1.3.1 WCAA-P具體步驟

WCAA-P步驟如下:

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

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

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

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

(3)

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

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

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

(4)

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

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

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

2 仿真與結果分析

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

表1 仿真參數(shù)

2.1 WHEA-P中穩(wěn)定度的權重系數(shù)取值

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

ws∈[0.45,0.55]

(5)

圖3 穩(wěn)定度的權重系數(shù)ws對網(wǎng)絡生存周期的影響

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

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

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

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

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

圖5 網(wǎng)絡終止后無人機的平均剩余能量

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

圖6 單位周期內(nèi)平均重入簇次數(shù)

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

圖7 單位周期內(nèi)無人機簇統(tǒng)治集更新次數(shù)

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

3 結束語

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