嚴(yán) 磊,雷 磊,蔡圣所,路志勇

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

0 概述

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

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

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

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

最小ID號(hào)算法和WCA雖然在一定程度上延長(zhǎng)了網(wǎng)絡(luò)的生命周期,但是它們都沒(méi)有充分考慮到網(wǎng)絡(luò)中無(wú)人機(jī)編隊(duì)的拓?fù)渥兓瘜?duì)分簇結(jié)構(gòu)的影響。在現(xiàn)有的無(wú)人機(jī)分簇算法中,無(wú)人機(jī)普遍采用自由運(yùn)動(dòng)模型實(shí)現(xiàn)無(wú)人機(jī)的飛行運(yùn)動(dòng),而這并不符合無(wú)人機(jī)飛行的實(shí)際情況。事實(shí)上,由于無(wú)人機(jī)飛行一般都攜帶任務(wù),它們的航線軌跡都是被提前規(guī)劃好的。所以在無(wú)人機(jī)的高效分簇算法的設(shè)計(jì)中,為了實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡[8],達(dá)到延長(zhǎng)網(wǎng)絡(luò)的生命周期的目的,還必須同時(shí)考慮無(wú)人機(jī)編隊(duì)拓?fù)渥兓瘞?lái)的影響[9]。

本文通過(guò)無(wú)人機(jī)路徑規(guī)劃算法實(shí)現(xiàn)對(duì)無(wú)人機(jī)編隊(duì)飛行線路的設(shè)計(jì),同時(shí)充分考慮在路徑規(guī)劃條件下無(wú)人機(jī)編隊(duì)網(wǎng)絡(luò)拓?fù)渥兓瘜?duì)分簇結(jié)構(gòu)的影響。在此基礎(chǔ)上,提出基于路徑規(guī)劃的簇首加權(quán)選舉算法(Weighted Head Election Algorithm based on Path-planning,WHEA-P)和基于路徑規(guī)劃的簇成員加權(quán)調(diào)整算法 (Weighted Hluster Adjustment Algorithm based on Path-planning,WCAA-P)。

1 基于路徑規(guī)劃的無(wú)人機(jī)網(wǎng)絡(luò)加權(quán)高效分簇

針對(duì)現(xiàn)有的無(wú)人機(jī)分簇算法沒(méi)有充分考慮路徑規(guī)劃條件下,無(wú)人編隊(duì)網(wǎng)絡(luò)拓?fù)渥兓瘜?duì)分簇結(jié)構(gòu)的影響帶來(lái)的弊端,本文在基于粒子群算法(POS)的無(wú)人機(jī)路徑規(guī)劃的基礎(chǔ)上,實(shí)現(xiàn)了2種基于路徑規(guī)劃的無(wú)人機(jī)網(wǎng)絡(luò)加權(quán)高效分簇方法(WHEA-P和WCAA-P)。

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

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

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

1.2 WHEA-P原理

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

1.2.1 相對(duì)移動(dòng)速率的弊端

在WCA中,無(wú)人機(jī)的相對(duì)移動(dòng)速率是評(píng)判無(wú)人機(jī)能否成為簇首的一個(gè)重要指標(biāo)。文獻(xiàn)[14]提出可以根據(jù)計(jì)算各節(jié)點(diǎn)的平均運(yùn)動(dòng)速度計(jì)算節(jié)點(diǎn)的相對(duì)移動(dòng)性。假設(shè)節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)集合為Nu,節(jié)點(diǎn)u相對(duì)鄰居節(jié)點(diǎn)v的速度為V(u-v),則節(jié)點(diǎn)u相對(duì)于所有鄰居節(jié)點(diǎn)的平均運(yùn)動(dòng)速度定義為:

(1)

節(jié)點(diǎn)的相對(duì)移動(dòng)速率越小,擔(dān)任簇首的概率越大。但在實(shí)際情況下,無(wú)人機(jī)相對(duì)移動(dòng)速率這一指標(biāo)很難客觀準(zhǔn)確地評(píng)定無(wú)人機(jī)之間的相對(duì)移動(dòng)性。[t,t+Δt]時(shí)刻簇內(nèi)無(wú)人機(jī)運(yùn)動(dòng)情況如圖2所示。

圖2 [t,t+Δt]時(shí)刻簇內(nèi)無(wú)人機(jī)的運(yùn)動(dòng)情況

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

1.2.2 穩(wěn)定度計(jì)算

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

算法1t時(shí)刻節(jié)點(diǎn)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開(kāi)始階段,依次給每個(gè)無(wú)人機(jī)節(jié)點(diǎn)按照從小到大分配ID號(hào),然后利用最小ID號(hào)算法對(duì)無(wú)人機(jī)網(wǎng)絡(luò)進(jìn)行初始分簇。

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

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

(2)

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

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

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

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

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

1.3 WCAA-P原理

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

1.3.1 WCAA-P具體步驟

WCAA-P步驟如下:

步驟1開(kāi)始階段,依次給每個(gè)無(wú)人機(jī)節(jié)點(diǎn)按照從小到大分配ID號(hào),然后利用最小ID號(hào)算法對(duì)無(wú)人機(jī)網(wǎng)絡(luò)進(jìn)行初始分簇。

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

步驟3借助路徑規(guī)劃獲得的無(wú)人機(jī)編隊(duì)的拓?fù)浣Y(jié)構(gòu)和飛行線路,計(jì)算每個(gè)簇成員到每個(gè)簇首節(jié)點(diǎn)i平均歐拉距離Li和對(duì)應(yīng)簇首i的節(jié)點(diǎn)度di。

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

(3)

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

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

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

(4)

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

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

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

2 仿真與結(jié)果分析

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

表1 仿真參數(shù)

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

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

ws∈[0.45,0.55]

(5)

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

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

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

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

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

網(wǎng)絡(luò)終止時(shí)無(wú)人機(jī)的平均剩余能量也是反映網(wǎng)絡(luò)生命周期的一個(gè)重要指標(biāo)。網(wǎng)絡(luò)終止時(shí),無(wú)人機(jī)的平均剩余能量越多,則網(wǎng)絡(luò)負(fù)載越不均衡,網(wǎng)絡(luò)的生存周期越短。結(jié)合圖5可以看出,當(dāng)無(wú)人機(jī)架數(shù)大于60架時(shí),WHEA-P和WCAA-P的平均剩余能量要遠(yuǎn)小于最小ID號(hào)算法和WCA。

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

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

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

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

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

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

3 結(jié)束語(yǔ)

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