無人機(jī)集群網(wǎng)絡(luò)分簇優(yōu)化算法

張 然，高瑩雪，丁元明

(1.大連大學(xué) 信息工程學(xué)院，遼寧 大連 116622； 2.大連大學(xué) 通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116622)

0 引 言

無人機(jī)集群是指多個(gè)無人機(jī)為了達(dá)成同一個(gè)任務(wù)目標(biāo)而形成的一個(gè)整體，進(jìn)而組成通信網(wǎng)絡(luò)，能夠沖破單個(gè)無人機(jī)在技術(shù)和功能上的局限性，并通過組織多種功能不同、性能各異的無人機(jī)聯(lián)合合作，最大程度地發(fā)揮作戰(zhàn)效能[1]。然而，無人機(jī)節(jié)點(diǎn)移動(dòng)速度高，導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)頻繁變化，這使得無人機(jī)集群網(wǎng)絡(luò)管理復(fù)雜。優(yōu)化無人機(jī)網(wǎng)絡(luò)最有效的方法就是將網(wǎng)絡(luò)劃分為多個(gè)簇結(jié)構(gòu)，并選擇適當(dāng)?shù)墓?jié)點(diǎn)成為簇首。因此，需要對(duì)無人機(jī)集群網(wǎng)絡(luò)的分簇算法進(jìn)行優(yōu)化，以適應(yīng)復(fù)雜的作戰(zhàn)環(huán)境，使網(wǎng)絡(luò)結(jié)構(gòu)更加穩(wěn)定。

經(jīng)典的分簇算法有最小ID號(hào)分簇算法(low ID clustering algorithm，LID)[2]、最高節(jié)點(diǎn)度分簇算法(highest node degree clustering algorithm，HD)[3]、最低移動(dòng)性分簇算法(lowest mobility clustering algorithm，LM)[4]、加權(quán)分簇算法(weighted clustering algorithm，WCA)[5]等。前3種分簇算法都沒有考慮影響網(wǎng)絡(luò)性能的因素，而加權(quán)分簇算法能夠綜合考慮不同影響因素，更好地適應(yīng)不同的應(yīng)用需求，因此，國內(nèi)外眾多學(xué)者對(duì)加權(quán)分簇算法進(jìn)行改進(jìn)，以適用于不同的應(yīng)用場景。

文獻(xiàn)[6]基于無人機(jī)的路徑規(guī)劃提出了一種加權(quán)分簇的方法，其采用粒子群算法對(duì)無人機(jī)飛行路徑進(jìn)行預(yù)測，并將預(yù)測的信息優(yōu)化加權(quán)分簇的各項(xiàng)權(quán)值。文獻(xiàn)[7]根據(jù)Ad Hoc網(wǎng)絡(luò)的特性，提出了依據(jù)節(jié)點(diǎn)能量ID迭代更換簇首的分簇算法，該算法當(dāng)節(jié)點(diǎn)移動(dòng)速度高時(shí)，丟包率明顯減少，提高了網(wǎng)絡(luò)的穩(wěn)定性。但這兩種算法計(jì)算量過大，使得網(wǎng)絡(luò)開銷大。文獻(xiàn)[8]針對(duì)無人機(jī)的飛行任務(wù)提出了一種動(dòng)態(tài)簇首選擇方案，以最高能量的方案進(jìn)行無人機(jī)的簇首選舉，優(yōu)化了無人機(jī)集群網(wǎng)絡(luò)的生存時(shí)間，但該算法簇首分布不均勻?qū)е麓馗骂l繁，網(wǎng)絡(luò)結(jié)構(gòu)不穩(wěn)定。文獻(xiàn)[9]針對(duì)網(wǎng)絡(luò)能量消耗快的問題，提出了基于LEACH協(xié)議的節(jié)能分簇改進(jìn)算法，該算法增加剩余能量和平均能量的概念，保證簇頭選舉更合理，減少了那些能量小于平均能量的節(jié)點(diǎn)當(dāng)選簇頭的概率。文獻(xiàn)[10]提出了一種能量距離分簇算法，綜合考慮節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)距離的合成因素，將合成因素最高的節(jié)點(diǎn)選舉為簇首，但該算法沒有考慮影響無人機(jī)集群網(wǎng)絡(luò)性能的影響因素，無法直接應(yīng)用于無人機(jī)集群網(wǎng)絡(luò)。文獻(xiàn)[11]針對(duì)無人機(jī)集群網(wǎng)絡(luò)的特點(diǎn)，提出一種改進(jìn)的多參數(shù)組合加權(quán)分簇算法(improved weighted clustering algorithm，IWCA)，該算法計(jì)算復(fù)雜且計(jì)算量大，會(huì)造成嚴(yán)重的網(wǎng)絡(luò)負(fù)擔(dān)。文獻(xiàn)[12]提出了改進(jìn)灰狼優(yōu)化算法的一種分簇算法，把灰狼的行為規(guī)則和狩獵策略相結(jié)合，通過對(duì)比分析粒子群、重力搜索等智能分簇算法，驗(yàn)證了灰狼優(yōu)化算法在最佳適應(yīng)度值上的優(yōu)越性。

基于以上分析，本文提出一種基于灰狼算法的分簇算法(grey wolf-based clustering optimization algorithm，GWCOA)，依據(jù)速度和距離相似度對(duì)網(wǎng)絡(luò)分簇，并采用計(jì)算量小、收斂速度快、便于實(shí)現(xiàn)的灰狼算法對(duì)簇首進(jìn)行選舉，以克服由于簇首失效導(dǎo)致整個(gè)網(wǎng)絡(luò)重新分簇所造成的網(wǎng)絡(luò)開銷過大的問題，使網(wǎng)絡(luò)結(jié)構(gòu)更加穩(wěn)定，同時(shí)使得簇首分布均勻，均衡節(jié)點(diǎn)能耗，延長網(wǎng)絡(luò)生命周期。

1 無人機(jī)集群網(wǎng)絡(luò)模型

無人機(jī)集群通信方式為移動(dòng)自組織網(wǎng)絡(luò)，即移動(dòng)Ad Hoc網(wǎng)絡(luò)，可以是平面式、分級(jí)式[13]，其體系結(jié)構(gòu)如圖1所示。

圖1 移動(dòng)自組織網(wǎng)絡(luò)結(jié)構(gòu)

在平面式結(jié)構(gòu)中，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)地位相等，處于相同等級(jí)。平面式的網(wǎng)絡(luò)結(jié)構(gòu)相對(duì)簡單，因?yàn)楣?jié)點(diǎn)可以互相取代，不會(huì)因?yàn)槟骋还?jié)點(diǎn)失效使網(wǎng)絡(luò)無法正常運(yùn)行，所以不需要進(jìn)行簇首的選舉，也不需要進(jìn)行簇維護(hù)。

在分級(jí)式結(jié)構(gòu)中，網(wǎng)絡(luò)被劃分成多個(gè)獨(dú)立的簇結(jié)構(gòu)，進(jìn)行分簇管理。分簇是指將整個(gè)網(wǎng)絡(luò)劃分為幾個(gè)小的、可自我管理的簇結(jié)構(gòu)[14]。分簇結(jié)構(gòu)規(guī)模不受限，有良好的可擴(kuò)充性，這使得網(wǎng)絡(luò)路由開銷減少[15]。每個(gè)簇結(jié)構(gòu)都由一個(gè)簇首和多個(gè)成員節(jié)點(diǎn)構(gòu)成。其中，簇首需要對(duì)簇內(nèi)進(jìn)行統(tǒng)籌和規(guī)劃，掌握簇內(nèi)的成員節(jié)點(diǎn)的狀態(tài)和信息、分配信道資源以及簇間通信等；成員節(jié)點(diǎn)負(fù)責(zé)執(zhí)行簇首的控制指令，向簇首匯報(bào)狀態(tài)和信息。

由于無人機(jī)集群網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量較多、節(jié)點(diǎn)移動(dòng)性強(qiáng)，平面式結(jié)構(gòu)會(huì)存在處理能力弱、網(wǎng)絡(luò)控制開銷大、網(wǎng)絡(luò)生命周期短等缺點(diǎn)，對(duì)網(wǎng)絡(luò)整體管理和控制的難度大，因此分級(jí)式結(jié)構(gòu)更適用于無人機(jī)集群網(wǎng)絡(luò)?；诜旨?jí)式結(jié)構(gòu)，本文設(shè)計(jì)一種適用于無人機(jī)集群網(wǎng)絡(luò)的分簇算法，將網(wǎng)絡(luò)分成多個(gè)簇結(jié)構(gòu)，并選取合適的簇首，以便進(jìn)行網(wǎng)絡(luò)管理。

2 基于改進(jìn)灰狼算法的分簇優(yōu)化

基于灰狼算法的無人機(jī)集群網(wǎng)絡(luò)分簇包括簇的形成、簇首的選舉、簇的維護(hù)3個(gè)階段。在簇的形成階段，根據(jù)速度相似度和距離相似度對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行分簇；在簇首的選舉階段，綜合考慮剩余能量、最高節(jié)點(diǎn)度、通信情況、任務(wù)種類，基于灰狼算法選舉簇首；在簇的維護(hù)階段，依據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化頻率，采用周期性維護(hù)機(jī)制對(duì)簇進(jìn)行維護(hù)。

2.1 簇的形成

本文依據(jù)節(jié)點(diǎn)的速度和距離相似度對(duì)無人機(jī)集群網(wǎng)絡(luò)的節(jié)點(diǎn)分簇，即將一定距離范圍內(nèi)相對(duì)靜止的無人機(jī)節(jié)點(diǎn)分成一個(gè)簇。同時(shí)，要保證簇結(jié)構(gòu)數(shù)目適中，平衡每個(gè)簇中成員節(jié)點(diǎn)的個(gè)數(shù)。當(dāng)一個(gè)網(wǎng)絡(luò)的簇結(jié)構(gòu)過少時(shí)，簇首負(fù)擔(dān)過大，導(dǎo)致其存活時(shí)間過短，網(wǎng)絡(luò)生命周期短；簇結(jié)構(gòu)過多時(shí)，簇間通信頻繁，會(huì)導(dǎo)致網(wǎng)絡(luò)通信開銷和端到端延遲的增大。因此，在依據(jù)速度和距離相似度初步分簇完成后，需檢測每個(gè)簇中節(jié)點(diǎn)個(gè)數(shù)，并設(shè)置每個(gè)簇中的最大允許節(jié)點(diǎn)個(gè)數(shù)為nmax，以保證分簇的平衡度。

2.1.1 節(jié)點(diǎn)的速度相似度

由于無人機(jī)節(jié)點(diǎn)移動(dòng)速度高，單個(gè)無人機(jī)運(yùn)動(dòng)航線不是事先預(yù)定的，飛行方案會(huì)在飛行中更改。因此，本文將從節(jié)點(diǎn)移動(dòng)速度的大小和方向兩個(gè)方面綜合考慮，采用標(biāo)準(zhǔn)差的方式來計(jì)算節(jié)點(diǎn)速度相似度。標(biāo)準(zhǔn)差用來衡量簇內(nèi)節(jié)點(diǎn)速度的離散程度，標(biāo)準(zhǔn)差越小，簇內(nèi)節(jié)點(diǎn)速度越接近平均值，即這些節(jié)點(diǎn)的速度相似度越高；標(biāo)準(zhǔn)差越大，簇內(nèi)節(jié)點(diǎn)速度和平均速度差異越大，即這些節(jié)點(diǎn)的速度相似度越低。速度相似度計(jì)算如圖2所示。

圖2 節(jié)點(diǎn)i與節(jié)點(diǎn)j的速度差

設(shè)節(jié)點(diǎn)i是節(jié)點(diǎn)j在下一跳通信范圍內(nèi)的任意節(jié)點(diǎn)，將節(jié)點(diǎn)速度的大小和運(yùn)動(dòng)方向在三維坐標(biāo)系中計(jì)算，則節(jié)點(diǎn)i與節(jié)點(diǎn)j在x軸、y軸、z軸上的速度差如下所示

ΔVjx=Vjx-Vix=Vjcosαj-Vicosαi

(1)

ΔVjy=Vjy-Viy=Vjcosβj-Vicosβi

(2)

ΔVjz=Vjz-Viz=Vjcosγj-Vicosγi

(3)

其中，Vjx、Vjy、Vjz為節(jié)點(diǎn)j在x、y、z軸上的速度；Vix、Viy、Viz為節(jié)點(diǎn)i在x、y、z軸上的速度；αj、αi分別為節(jié)點(diǎn)j、i與x軸的夾角；βj、βi分別為節(jié)點(diǎn)j、i與y軸的夾角；γj、γi分別為節(jié)點(diǎn)j、i與z軸的夾角。

則節(jié)點(diǎn)j與N個(gè)鄰居節(jié)點(diǎn)i在x軸、y軸、z軸上的平均速度差為

(4)

(5)

(6)

節(jié)點(diǎn)j與鄰居節(jié)點(diǎn)i在x軸、y軸、z軸上的速度差的標(biāo)準(zhǔn)差為

(7)

(8)

(9)

由勾股定理可知，節(jié)點(diǎn)j與鄰居節(jié)點(diǎn)i的速度差的標(biāo)準(zhǔn)差如下所示

(10)

(11)

設(shè)定速度差的標(biāo)準(zhǔn)差閾值為q，當(dāng)速度差的標(biāo)準(zhǔn)差δjv小于速度閾值q時(shí)，節(jié)點(diǎn)j與其鄰居節(jié)點(diǎn)i在運(yùn)動(dòng)速度大小和運(yùn)動(dòng)方向上都具有相似性，即具有速度相似度。

如果以10個(gè)無人機(jī)節(jié)點(diǎn)為例，假設(shè)每個(gè)節(jié)點(diǎn)具有不同的初始速度，則基于速度相似度的分簇結(jié)果如圖3所示。

圖3 速度相似度分簇結(jié)果

2.1.2 節(jié)點(diǎn)的距離相似度

現(xiàn)有的計(jì)算節(jié)點(diǎn)間距離的方法基本都需要額外增加輔助設(shè)備，如GPS等。但對(duì)于無人機(jī)集群來說，不僅增加了成本而且還加大了網(wǎng)絡(luò)能耗。因此，本文通過節(jié)點(diǎn)接收和發(fā)送的功率，依據(jù)損耗衰減空間的近似信號(hào)傳播公式來計(jì)算節(jié)點(diǎn)間距離差。

設(shè)節(jié)點(diǎn)i為節(jié)點(diǎn)j在下一跳通信范圍內(nèi)的任意節(jié)點(diǎn)，則節(jié)點(diǎn)j與鄰居節(jié)點(diǎn)i的距離差為

(12)

其中，Pt為節(jié)點(diǎn)發(fā)射功率；Gt為發(fā)射天線增益；ht為發(fā)射天線高度；hr為接收天線高度；Pr為節(jié)點(diǎn)接收功率。

則節(jié)點(diǎn)j與N個(gè)鄰居節(jié)點(diǎn)i的平均距離差的標(biāo)準(zhǔn)差為

(13)

(14)

設(shè)定距離差的標(biāo)準(zhǔn)差閾值為p，當(dāng)距離差的標(biāo)準(zhǔn)差δjd小于距離閾值p時(shí)，節(jié)點(diǎn)j與其鄰居節(jié)點(diǎn)i具有相似性，即具有距離相似度。

對(duì)于圖3中的10個(gè)節(jié)點(diǎn)，基于距離相似度的分簇結(jié)果如圖4所示。

圖4 距離相似度分簇結(jié)果

2.1.3 節(jié)點(diǎn)的綜合相似度

當(dāng)節(jié)點(diǎn)速度差的標(biāo)準(zhǔn)差和距離差的標(biāo)準(zhǔn)差都小于速度閾值q和距離閾值p時(shí)，則認(rèn)為節(jié)點(diǎn)j與其鄰居節(jié)點(diǎn)i同時(shí)具有速度相似度和距離相似度，即節(jié)點(diǎn)j與其鄰居節(jié)點(diǎn)i符合成簇條件。該成簇條件具有傳遞性，即節(jié)點(diǎn)j與節(jié)點(diǎn)i符合成簇條件，節(jié)點(diǎn)j與節(jié)點(diǎn)k符合成簇條件，那么節(jié)點(diǎn)i與節(jié)點(diǎn)k也符合成簇條件，即節(jié)點(diǎn)j、節(jié)點(diǎn)i、節(jié)點(diǎn)k成為一個(gè)簇。

無人機(jī)集群網(wǎng)絡(luò)根據(jù)速度和距離相似度對(duì)網(wǎng)絡(luò)分簇，其具體步驟如下：

步驟1 判斷速度標(biāo)準(zhǔn)差是否大于速度閾值q；

步驟2 當(dāng)速度標(biāo)準(zhǔn)差大于速度閾值q時(shí)，舍棄與節(jié)點(diǎn)j速度差最大的鄰居節(jié)點(diǎn)i，并執(zhí)行步驟1；否則執(zhí)行步驟3；

步驟3 判斷距離標(biāo)準(zhǔn)差是否大于距離閾值p；

步驟4 當(dāng)距離標(biāo)準(zhǔn)差大于距離閾值p時(shí)，舍棄與節(jié)點(diǎn)j距離差最大的鄰居節(jié)點(diǎn)i，并執(zhí)行步驟3；否則執(zhí)行步驟5；

步驟5 判斷小于速度閾值的節(jié)點(diǎn)和小于距離閾值的節(jié)點(diǎn)是否為相同節(jié)點(diǎn)；

步驟6 當(dāng)符合兩個(gè)條件的節(jié)點(diǎn)為相同節(jié)點(diǎn)時(shí)，執(zhí)行步驟7；

步驟7 節(jié)點(diǎn)個(gè)數(shù)檢測，判斷每個(gè)簇中成員節(jié)點(diǎn)數(shù)是否小于等于最大允許節(jié)點(diǎn)個(gè)數(shù)nmax；

步驟8 當(dāng)每個(gè)簇中成員節(jié)點(diǎn)數(shù)大于nmax時(shí)，舍棄與節(jié)點(diǎn)j速度差和距離差之和最大節(jié)點(diǎn)，并執(zhí)行步驟7；

步驟9 當(dāng)每個(gè)簇中成員節(jié)點(diǎn)數(shù)都小于等于nmax時(shí)，完成分簇。

按上述步驟，對(duì)于圖3中的10個(gè)節(jié)點(diǎn)，綜合速度相似度和距離相似度的分簇結(jié)果如圖5所示。

圖5 綜合相似度分簇結(jié)果

2.2 簇首的選舉

對(duì)所有網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分簇后，本文綜合考慮節(jié)點(diǎn)剩余能量、最高節(jié)點(diǎn)度、通信情況、任務(wù)種類4個(gè)影響因素的聯(lián)合度量指標(biāo)，并采用改進(jìn)灰狼算法選取簇首。

2.2.1 聯(lián)合度量指標(biāo)的計(jì)算

(1)剩余能量

在進(jìn)行簇首選舉時(shí)，如果某一節(jié)點(diǎn)的剩余能量Eres小于所有鄰居節(jié)點(diǎn)的平均能量Eavg(所有鄰居節(jié)點(diǎn)剩余能量之和除以鄰居節(jié)點(diǎn)個(gè)數(shù))，則退出簇首的競選。其中，剩余能量通過地面控制站獲取。對(duì)剩余能量歸一化處理，即剩余能量Eres除以初始能量E0，歸一化后的剩余能量Eτ為

(15)

(2)節(jié)點(diǎn)度

節(jié)點(diǎn)度是指節(jié)點(diǎn)在通信范圍內(nèi)鄰居節(jié)點(diǎn)的個(gè)數(shù)。同一個(gè)網(wǎng)絡(luò)中，節(jié)點(diǎn)度越高，簇首數(shù)量越少，網(wǎng)絡(luò)時(shí)延越少。對(duì)節(jié)點(diǎn)度歸一化處理即鄰居節(jié)點(diǎn)數(shù)Ni除以簇內(nèi)總節(jié)點(diǎn)數(shù)Ns，歸一化后的節(jié)點(diǎn)度Nτ為

(16)

(3)通信情況

節(jié)點(diǎn)通信成功的概率fs(i)取決于M次獨(dú)立重復(fù)實(shí)驗(yàn)中通信成功的次數(shù)y和通信失敗的次數(shù)n，則節(jié)點(diǎn)通信成功的概率fs(i)為

(17)

其中，通信成功是在一個(gè)周期內(nèi)收到了鄰居節(jié)點(diǎn)的HELLO消息；通信失敗是一個(gè)周期內(nèi)，沒有收到鄰居節(jié)點(diǎn)的報(bào)文或收到鏈路斷裂的錯(cuò)誤信息。

(4)任務(wù)種類

軍事戰(zhàn)爭中，由于無人機(jī)執(zhí)行的作戰(zhàn)任務(wù)不同，其性能也各不相同。執(zhí)行探測任務(wù)的無人機(jī)主要任務(wù)是搜集戰(zhàn)場情報(bào)、觀察作戰(zhàn)區(qū)域，增強(qiáng)顯示和預(yù)警能力；執(zhí)行偵察任務(wù)的主要任務(wù)是深入到地方防御縱深進(jìn)行監(jiān)視、目標(biāo)指示和損傷評(píng)估等；執(zhí)行救援任務(wù)的無人機(jī)是在其它無人機(jī)失效時(shí)代替其繼續(xù)執(zhí)行作戰(zhàn)任務(wù)；執(zhí)行打擊任務(wù)的無人機(jī)則需攜帶攻擊武器，對(duì)目標(biāo)進(jìn)行精準(zhǔn)打擊。因此，需要考慮無人機(jī)執(zhí)行任務(wù)種類對(duì)簇首選舉的影響，依據(jù)無人機(jī)任務(wù)種類的危險(xiǎn)程度，設(shè)置節(jié)點(diǎn)簇首選舉的優(yōu)先級(jí)權(quán)Tτ，見表1。

表1 任務(wù)種類與優(yōu)先級(jí)權(quán)值

由上述過程得到了節(jié)點(diǎn)i的剩余能量、鄰居節(jié)點(diǎn)數(shù)、通信情況和任務(wù)種類，對(duì)4種影響因素進(jìn)行加權(quán)求和。根據(jù)加權(quán)分簇算法綜合考慮這4個(gè)因素得到的復(fù)合權(quán)值如下

Mi=ω1Eτ+ω2Nτ+ω3fs(i)+ω4Tτ

(18)

其中，ω1、ω2、ω3、ω4的取值范圍為[0，1]，并且滿足ω1+ω2+ω3+ω4=1，其具體大小可以根據(jù)實(shí)際情況取值。

2.2.2 改進(jìn)灰狼優(yōu)化算法

灰狼優(yōu)化算法(grey wolf optimization，GWO)[16]模擬自然界中灰狼的等級(jí)制度與狩獵行為，將灰狼群體劃分為α狼、β狼、γ狼3個(gè)等級(jí)，在灰狼群體的搜索過程中，利用α狼、β狼、γ狼判斷獵物的大概位置如下

(19)

(20)

(21)

其中，Dα、Dβ、Dγ分別為α狼、β狼、γ狼與獵物的距離；C1、C2、C3是一個(gè)隨機(jī)向量，分別為α狼、β狼、γ狼的搜索范圍；Xα(t)、Xβ(t)、Xγ(t)分別為α狼、β狼、γ狼的當(dāng)前位置；X為當(dāng)前灰狼位置向量；A1、A2、A3是一個(gè)自適應(yīng)向量分別為α狼、β狼、γ狼的攻擊范圍。

由于灰狼優(yōu)化算法的α狼、β狼、γ狼共同影響獵物的位置，因此，需要對(duì)其采用權(quán)重分配策略。本文改進(jìn)的權(quán)重比例為

(22)

(23)

(24)

其中，M1、M2、M3分別為改進(jìn)灰狼算法中α狼、β狼、γ狼對(duì)獵物位置的權(quán)重影響因子，即α狼、β狼、γ狼對(duì)獵物位置的學(xué)習(xí)率。

根據(jù)改進(jìn)灰狼優(yōu)化算法計(jì)算獵物位置如下

(25)

X′(t+1)=M1X1+M2X2+M3X3

(26)

本文采用灰狼算法對(duì)無人機(jī)網(wǎng)絡(luò)的簇首選舉進(jìn)行優(yōu)化，將狼群看作無人機(jī)集群網(wǎng)絡(luò)，灰狼看作無人機(jī)集群網(wǎng)絡(luò)中的節(jié)點(diǎn)，獵物看作每個(gè)簇的簇首。在每一個(gè)簇中，選擇M值最大的3個(gè)節(jié)點(diǎn)，分別作為M1、M2、M3，根據(jù)式(26)計(jì)算出簇內(nèi)所求的獵物，即為簇首。

2.3 簇的維護(hù)

由于無人機(jī)集群網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化的快速、復(fù)雜，所選擇的簇頭可能在一段時(shí)間后飛離原簇，或耗盡能量，或通信中斷，所以對(duì)簇的維護(hù)有著至關(guān)重要的作用。

簇的維護(hù)方式主要有離散時(shí)間機(jī)制和周期性維護(hù)機(jī)制。離散時(shí)間機(jī)制是一次選定簇首后，基本不再更換簇首，并不適用于無人機(jī)集群網(wǎng)絡(luò)。因此，在對(duì)無人機(jī)集群網(wǎng)絡(luò)簇結(jié)構(gòu)進(jìn)行維護(hù)時(shí)采用周期性維護(hù)機(jī)制，確保在一個(gè)簇首選舉周期內(nèi)，由聯(lián)合度量指標(biāo)最高的節(jié)點(diǎn)擔(dān)任簇首。除此之外，簇首選舉周期根據(jù)無人機(jī)集群網(wǎng)絡(luò)拓?fù)渥兓潭榷ǎ?dāng)無人機(jī)集群網(wǎng)絡(luò)拓?fù)渥兓^慢時(shí)，則將選舉周期適當(dāng)延長，避免頻繁重新選舉簇首產(chǎn)生大量開銷；當(dāng)無人機(jī)集群網(wǎng)絡(luò)拓?fù)渥兓^快時(shí)，則適當(dāng)縮短簇首選舉時(shí)間，避免因簇首失效造成簇結(jié)構(gòu)與整個(gè)網(wǎng)絡(luò)脫離。

2.4 算法的實(shí)現(xiàn)流程

本文所提出的無人機(jī)集群網(wǎng)絡(luò)分簇優(yōu)化算法首先考慮節(jié)點(diǎn)速度相似度和距離相似度對(duì)所有節(jié)點(diǎn)分簇，然后綜合考慮簇內(nèi)節(jié)點(diǎn)的剩余能量、最高節(jié)點(diǎn)度、通信情況和任務(wù)種類的影響因素，采用灰狼優(yōu)化算法進(jìn)行簇首位置更新，選舉最佳簇首。該分簇優(yōu)化算法具體實(shí)現(xiàn)步驟如下，其流程如圖6所示。

圖6 算法流程

步驟1 網(wǎng)絡(luò)初始化，定義無人機(jī)集群網(wǎng)絡(luò)中總節(jié)點(diǎn)個(gè)數(shù)為N；

步驟2 考慮節(jié)點(diǎn)的速度相似度和距離相似度對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分簇；

步驟3 判斷簇內(nèi)成員數(shù)量是否大于最大閾值nmax；

步驟4 當(dāng)所有簇內(nèi)成員個(gè)數(shù)都小于最大閾值時(shí)，初步完成分簇；

步驟5 判斷簇內(nèi)各節(jié)點(diǎn)剩余能量Eres是否大于簇內(nèi)平均能量Eavg；

步驟6 當(dāng)節(jié)點(diǎn)能量小于平均能量Eavg，該節(jié)點(diǎn)退出競選簇首；

步驟7 綜合考慮節(jié)點(diǎn)剩余能量、最高節(jié)點(diǎn)度、通信情況、任務(wù)種類4個(gè)影響因素的聯(lián)合度量指標(biāo)，基于改進(jìn)灰狼優(yōu)化算法，選擇最佳簇首。

3 實(shí)驗(yàn)仿真與結(jié)果分析

本節(jié)仿真驗(yàn)證所提出的GWCOA算法性能，其具體參數(shù)設(shè)置見表2。本實(shí)驗(yàn)與LID、HD、WCA、IWCA這4種分簇算法進(jìn)行對(duì)比分析，通過簇首數(shù)目、簇依附關(guān)系變化次數(shù)、分簇的平衡度、統(tǒng)治集更新次數(shù)和節(jié)點(diǎn)生存?zhèn)€數(shù)5個(gè)性能指標(biāo)驗(yàn)證GWCOA算法的有效性。

表2 仿真參數(shù)

圖7 節(jié)點(diǎn)傳輸距離對(duì)簇首數(shù)目的影響

圖8為節(jié)點(diǎn)傳輸距離和簇依附關(guān)系變化次數(shù)的關(guān)系。簇結(jié)構(gòu)越穩(wěn)定，簇依附關(guān)系變化次數(shù)越少。由圖8可知，5種分簇算法的簇依附關(guān)系變化都隨著節(jié)點(diǎn)傳輸距離的先增加后減少。當(dāng)傳輸距離較小時(shí)，節(jié)點(diǎn)脫離簇的概率較小，并隨著節(jié)點(diǎn)傳輸距離的增大而增加。因?yàn)榇藭r(shí)網(wǎng)絡(luò)中簇結(jié)構(gòu)多，每個(gè)簇的成員節(jié)點(diǎn)少，但隨著傳輸距離的增加，簇結(jié)構(gòu)減少，每個(gè)簇的成員節(jié)點(diǎn)多，節(jié)點(diǎn)脫離簇的概率隨著傳輸距離的增大逐漸減少。由于GWCOA算法在選舉簇首時(shí)采用改進(jìn)灰狼優(yōu)化算法，保證簇首分布均勻，其簇依附關(guān)系變化次數(shù)相比于其它4種分簇算法的更小，網(wǎng)絡(luò)結(jié)構(gòu)更穩(wěn)定。

圖8 節(jié)點(diǎn)傳輸距離對(duì)簇依附關(guān)系變化次數(shù)的影響

圖9為節(jié)點(diǎn)傳輸距離和分簇平衡度的關(guān)系。分簇平衡度是指每個(gè)簇的節(jié)點(diǎn)個(gè)數(shù)基本相等，使得網(wǎng)絡(luò)中簇分布相對(duì)均勻。本實(shí)驗(yàn)分簇算法平衡度采用標(biāo)準(zhǔn)差的方式來衡量，即每個(gè)簇所包含節(jié)點(diǎn)數(shù)的標(biāo)準(zhǔn)差，其值越小分簇算法越優(yōu)越。由圖9可知，5種算法的分簇平衡度都隨著節(jié)點(diǎn)傳輸距離的增加而增加。隨著節(jié)點(diǎn)傳輸距離的增大，簇結(jié)構(gòu)減少，每個(gè)簇中的平均節(jié)點(diǎn)數(shù)會(huì)增加，從而導(dǎo)致每個(gè)簇所包含節(jié)點(diǎn)數(shù)的標(biāo)準(zhǔn)差增大，即平衡度增大。由于GWCOA算法在初步分簇后進(jìn)行節(jié)點(diǎn)個(gè)數(shù)檢測，使得每個(gè)簇內(nèi)的節(jié)點(diǎn)數(shù)大致相同，簇分布相對(duì)均勻，其分簇平衡度明顯優(yōu)于其它分簇算法。

圖9 節(jié)點(diǎn)傳輸距離對(duì)分簇平衡度的影響

圖10為仿真時(shí)間和統(tǒng)治集更新次數(shù)的關(guān)系。統(tǒng)治集更新次數(shù)為單位時(shí)間內(nèi)簇首更新次數(shù)，統(tǒng)治集更新次數(shù)越多，簇結(jié)構(gòu)越不穩(wěn)定，分簇算法在分簇過程中越會(huì)產(chǎn)生龐大的計(jì)算量和通信開銷。由圖10可知，5種算法的統(tǒng)治集更新次數(shù)都隨著仿真時(shí)間的增加而增加。由于GWCOA算法先對(duì)網(wǎng)絡(luò)分簇，再進(jìn)行簇首的選舉，當(dāng)成員節(jié)點(diǎn)失效時(shí)，不需要重新分簇、選舉簇首，減少了統(tǒng)治集更新次數(shù)，因此，其統(tǒng)治集更新次數(shù)明顯低于其它3種分簇算法，提高了整個(gè)網(wǎng)絡(luò)的穩(wěn)定性，降低了計(jì)算量，減少了網(wǎng)絡(luò)開銷。

圖10 仿真時(shí)間和統(tǒng)治集更新次數(shù)的關(guān)系

圖11為仿真輪數(shù)和生存節(jié)點(diǎn)個(gè)數(shù)的變化關(guān)系。對(duì)于一個(gè)網(wǎng)絡(luò)來說，隨著仿真輪數(shù)的增加，生存節(jié)點(diǎn)個(gè)數(shù)越多，網(wǎng)絡(luò)生命周期越長。由圖11可知，5種算法生存節(jié)點(diǎn)個(gè)數(shù)都隨仿真輪數(shù)增加而減少。WCA、IWCA、GWCOA由于考慮了節(jié)點(diǎn)的剩余能量，因此經(jīng)過相同輪數(shù)這3種算法的節(jié)點(diǎn)生存?zhèn)€數(shù)明顯多于其它兩種算法，但在IWCA算法中節(jié)點(diǎn)剩余能量權(quán)重設(shè)置比較大且隨鄰居節(jié)點(diǎn)數(shù)變化，因此IWCA算法優(yōu)于WCA算法。由于GWCOA算法不僅考慮了節(jié)點(diǎn)的剩余能量，還采用了計(jì)算量小的灰狼優(yōu)化算法選舉簇首，而且采用周期性維護(hù)機(jī)制對(duì)簇進(jìn)行維護(hù)，因此，GWCOA算法最優(yōu)，其網(wǎng)絡(luò)生命周期最長。

圖11 仿真輪數(shù)和生存節(jié)點(diǎn)個(gè)數(shù)的關(guān)系

4 結(jié)束語

本文針對(duì)無人機(jī)集群網(wǎng)絡(luò)的特點(diǎn)及現(xiàn)有分簇算法的缺點(diǎn)，提出了基于改進(jìn)灰狼算法的無人機(jī)集群網(wǎng)絡(luò)分簇算法。該算法將速度和距離相似度作為形成簇的條件，增加了簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)檢測，并綜合考慮簇內(nèi)節(jié)點(diǎn)的剩余能量、最高節(jié)點(diǎn)度、通信情況、任務(wù)種類4種因素形成的聯(lián)合度量指標(biāo)，同時(shí)在簇首選舉前增加了節(jié)點(diǎn)能量檢測，大大減少了采用灰狼優(yōu)化算法進(jìn)行選舉最佳簇首時(shí)的網(wǎng)絡(luò)開銷。仿真實(shí)驗(yàn)結(jié)果表明，該算法保證了簇首數(shù)目適中和分簇的平衡度，同時(shí)采用的灰狼優(yōu)化算法也保證了簇首分布均勻，改善了無人機(jī)集群網(wǎng)絡(luò)因節(jié)點(diǎn)移動(dòng)而導(dǎo)致的網(wǎng)絡(luò)結(jié)構(gòu)不穩(wěn)定的問題，延長了網(wǎng)絡(luò)生命周期。