無人機(jī)自組網(wǎng)快速穩(wěn)定加權(quán)分簇算法

郭建 任智 邱金 陳春宇 姚毅

摘 要：在無人機(jī)自組網(wǎng)中，網(wǎng)絡(luò)規(guī)模增大會使節(jié)點(diǎn)間平均跳數(shù)增加，網(wǎng)絡(luò)管理和路由協(xié)議運(yùn)行更艱難。分簇結(jié)構(gòu)可用來優(yōu)化網(wǎng)絡(luò)管理，提高網(wǎng)絡(luò)的可拓展性。針對無人機(jī)高移動造成的簇結(jié)構(gòu)不穩(wěn)定以及分簇結(jié)構(gòu)魯棒性差的問題，提出了一種快速穩(wěn)定加權(quán)分簇算法。該算法對比現(xiàn)有的加權(quán)分簇算法，對鏈路保持率、節(jié)點(diǎn)度和相對速度三個(gè)指標(biāo)的選取進(jìn)行改進(jìn)。針對戰(zhàn)場和應(yīng)急場景下簇頭節(jié)點(diǎn)掉線帶來的簇振蕩，提出了一種高效的簇維護(hù)機(jī)制。最后通過仿真驗(yàn)證該算法的性能，結(jié)果表明，與現(xiàn)有改進(jìn)型加權(quán)分簇算法相比，該算法可以有效降低成簇的時(shí)間，同時(shí)在簇頭節(jié)點(diǎn)掉線的情況下快速恢復(fù)，更適用于復(fù)雜環(huán)境下的網(wǎng)絡(luò)部署。

關(guān)鍵詞：無人機(jī)自組網(wǎng)；加權(quán)分簇算法；魯棒性；節(jié)點(diǎn)度

中圖分類號：TP393?? 文獻(xiàn)標(biāo)志碼：A?? 文章編號：1001-3695（2024）01-039-0248-06

doi：10.19734/j.issn.1001-3695.2023.05.0204

Fast and stable weighted clustering algorithm for unmanned aerial vehicle Ad hoc network

Abstract：In unmanned aerial vehicle Ad hoc network（UANET），increasing the network size will increase the average number of hops between nodes，making network management and routing protocol operation more difficult.Clustering structure can be used to optimize network management and improve network scalability. This paper proposed a fast and stable weighted clustering algorithm to address the instability and poor robustness of cluster structures caused by the high mobility of drones.Compared with existing weighted clustering algorithms，this algorithm improved the selection of four indicators：link retention rate，node degree and relative speed.It proposed an efficient cluster maintenance mechanism to address the cluster oscillation caused by cluster head node disconnection in battlefield and emergency scenarios.Finally，it verified the performance of this algorithm through simulation.The results show that compared with existing improved weighted clustering algorithms，this algorithm can effectively reduce clustering time，and quickly recover in the event of cluster head nodes dropping，making it more suitable for network deployment in complex environments.

Key words：UANET；weighted clustering algorithm；robustness；node degree

0 引言

無人機(jī)（unmanned aerial vehicle，UAV）技術(shù)的應(yīng)用在軍事場景下，有結(jié)構(gòu)簡單、造價(jià)低廉、飛行在高空平臺帶來的隱蔽性等特點(diǎn)?；谝陨蟽?yōu)點(diǎn)，多無人機(jī)組成的無人機(jī)蜂群經(jīng)常被部署在戰(zhàn)場環(huán)境中，無論是對敵打擊還是偵察試探均能表現(xiàn)出優(yōu)異的成績［1］。多無人機(jī)系統(tǒng)采用傳統(tǒng)Ad hoc架構(gòu)組成無人機(jī)自組網(wǎng)（UANET）。相比較移動自組網(wǎng)（mobile Ad hoc network，MANET），無人機(jī)自組網(wǎng)由無人機(jī)搭載通信設(shè)備作為網(wǎng)絡(luò)節(jié)點(diǎn)，飛行在三維的空域，移動方向隨機(jī)性強(qiáng)且速度更快，網(wǎng)絡(luò)拓?fù)渥兓l繁。同時(shí)為了適應(yīng)戰(zhàn)場災(zāi)區(qū)等危險(xiǎn)惡劣環(huán)境，充分發(fā)揮集群通信的優(yōu)勢，要保證網(wǎng)絡(luò)部署節(jié)點(diǎn)多、覆蓋范圍廣。引入分簇結(jié)構(gòu)，提高網(wǎng)絡(luò)性能的同時(shí)便于網(wǎng)絡(luò)管理［2］。

文獻(xiàn)［3］針對MANET的分簇問題提出了完全基于分布式的加權(quán)分簇算法（weighted clustering algorithm，WCA），該算法綜合考慮節(jié)點(diǎn)的最優(yōu)節(jié)點(diǎn)度、節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的距離之和、節(jié)點(diǎn)的移動性以及節(jié)點(diǎn)能量，以四個(gè)測量值加權(quán)計(jì)算出權(quán)值通過權(quán)值選取簇頭。文獻(xiàn)［4］通過仿真確定簇頭輪換的能量閾值和安全距離閾值，但是這種方法缺乏普適性，不能應(yīng)用在所有分簇算法中。文獻(xiàn)［5］在分簇階段先剔除網(wǎng)絡(luò)邊緣的噪聲節(jié)點(diǎn)，避免影響分簇準(zhǔn)確性，延長了網(wǎng)絡(luò)壽命。文獻(xiàn)［6］使用K值算法建立初始簇，之后通過WCA選舉簇頭，在簇間通信的時(shí)候通過預(yù)測節(jié)點(diǎn)位置動態(tài)調(diào)整發(fā)生功率，延長網(wǎng)絡(luò)生存時(shí)間。文獻(xiàn)［7］提出一種雙簇頭的加權(quán)分簇算法，通過備用簇頭來維護(hù)簇結(jié)構(gòu)穩(wěn)定，并且構(gòu)建了一種基于馬爾可夫過程的生存性分析方法，分析證明了雙簇頭方案相較單簇頭穩(wěn)定性和生存性提高了35%。

文獻(xiàn)［8］針對航空自組網(wǎng)高度動態(tài)造成的分簇不穩(wěn)定的問題，設(shè)計(jì)了一種基于位置和速度信息的分簇維護(hù)方法，提出備份簇頭的概念，從成員節(jié)點(diǎn)位置和運(yùn)動的角度構(gòu)造備份簇頭選擇因子，簇頭節(jié)點(diǎn)據(jù)此完成備用簇頭節(jié)點(diǎn)的選取。該方案的局限性在于無法適應(yīng)復(fù)雜環(huán)境。文獻(xiàn)［9］提出了一種改進(jìn)的加權(quán)分簇算法（improved weighted clustering algorithm，IWCA），IWCA假設(shè)在一段時(shí)間內(nèi)節(jié)點(diǎn)的移動速度不變，結(jié)合鄰居節(jié)點(diǎn)此時(shí)的位置，預(yù)測出鄰居節(jié)點(diǎn)的鏈路保持時(shí)間，反映節(jié)點(diǎn)間位置和運(yùn)動關(guān)系。文獻(xiàn)［10］提出了一種基于加權(quán)的穩(wěn)定分簇算法（weight stable clustering algorithm，WSCA）。WSCA在權(quán)值系數(shù)計(jì)算的過程中引入最大熵準(zhǔn)則，通過構(gòu)建評價(jià)矩陣和拉格朗日函數(shù)，動態(tài)地調(diào)整各個(gè)指標(biāo)的權(quán)值。因?yàn)楣?jié)點(diǎn)只是收集局部位置信息使用極大熵準(zhǔn)則，所以得到的只是局部最優(yōu)，并不能保證分簇結(jié)果的合理性。

基于以上分析，現(xiàn)有對于加權(quán)分簇算法的研究存在指標(biāo)選取不合理以及簇維護(hù)機(jī)制不合理的問題。針對這些問題提出一種快速穩(wěn)定加權(quán)分簇算法（fast and stable weighted clustering algorithm，F(xiàn)SWCA）。首先，該方法提出平均速度跟隨意識因子、平均鏈路保持率以及節(jié)點(diǎn)度差三種分簇指標(biāo)量，并且將各指標(biāo)量推導(dǎo)在三維場景中，同時(shí)優(yōu)化了分簇過程，使網(wǎng)絡(luò)的分簇過程更快速。其次，針對現(xiàn)有方案中簇維護(hù)方法帶來較大的控制開銷以及簇維護(hù)方案對簇頭意外掉線之后的處理時(shí)延較大，受影響節(jié)點(diǎn)較廣泛的問題，提出了一種快速穩(wěn)定的高效簇維護(hù)方法。

1 簇頭選擇指標(biāo)

FSWCA默認(rèn)無人機(jī)節(jié)點(diǎn)會搭載慣導(dǎo)系統(tǒng)，可以直接獲得無人機(jī)節(jié)點(diǎn)的速度和位置信息。節(jié)點(diǎn)的位置信息表示為Positioni=（Xi，Yi，Zi）。

1.1 速度跟隨意識因子

節(jié)點(diǎn)i根據(jù)節(jié)點(diǎn)j傳來的HELLO消息中攜帶速度信息vj以及本節(jié)點(diǎn)的速度信息vi得到節(jié)點(diǎn)對節(jié)點(diǎn)的相對速度：

vji=vj-vi=（v cos α，v cos β，v cos γ）（1）

定義節(jié)點(diǎn)j對i的移動跟隨意識因子為

對于節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)，可以得到節(jié)點(diǎn)i的平均移動跟隨意識因子Fi為

其中：degi表示節(jié)點(diǎn)i的對稱一跳鄰居數(shù)；Ni表示節(jié)點(diǎn)i的一跳對稱鄰居集合。

平均移動跟隨意識因子體現(xiàn)了節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)對節(jié)點(diǎn)i的速度跟隨性，相對速度vji的大小與節(jié)點(diǎn)i的速度，vi的比值越小，表示節(jié)點(diǎn)j對于節(jié)點(diǎn)i的跟隨意識越好；反之，比值越大表示跟隨意識越弱，且隨著比值的增加跟隨意識指標(biāo)呈指數(shù)型下降。

1.2 優(yōu)化的平均鏈路保持率

現(xiàn)有文獻(xiàn)對于節(jié)點(diǎn)鏈路保持概率的計(jì)算都假定節(jié)點(diǎn)的移動速度在一段時(shí)間內(nèi)不改變，然而事實(shí)是節(jié)點(diǎn)的移動是隨機(jī)的，因此對于鏈路保持率的預(yù)測缺乏合理性。

r（t）=vmax（T-t）（4）

其中：vmax為無人機(jī)節(jié)點(diǎn)的最大移動速度。節(jié)點(diǎn)j的運(yùn)動范圍在節(jié)點(diǎn)i的通信范圍的概率可以用兩個(gè)球體重合部分的體積與小球體的體積之比表出，這個(gè)概率值即為t時(shí)刻的節(jié)點(diǎn)間鏈路保持率。節(jié)點(diǎn)i和j之間的距離Dij（t）由式（5）給出：

根據(jù)t時(shí)刻節(jié)點(diǎn)間距離Dij（t）可分為兩種情況：

a）如圖1，節(jié)點(diǎn)j依然在節(jié)點(diǎn)i的通信范圍內(nèi)，即Dij（t）≤R。

b）如圖2，節(jié)點(diǎn)j已經(jīng)在節(jié)點(diǎn)i的通信范圍之外，即Dij（t）>R。

對于平均鏈路保持時(shí)間的推導(dǎo)過程如下：

由空間幾何定理可知兩球球心與兩球相交截面圓的圓心三點(diǎn)共線且球心線垂直截面。基于此對圖1和圖2建立方程：

由以上公式可以解出：

進(jìn)而得到截面圓與大球體所圍成的球冠高h(yuǎn)1：

截面圓與小球體所圍成的球冠高h(yuǎn)2：

h2=r（t）-jg（9）

由球冠體積公式可得

t時(shí)刻節(jié)點(diǎn)間鏈路保持率：

對于0～T做積分即為所求的T周期內(nèi)的節(jié)點(diǎn)i與j間鏈路保持率：

而對于節(jié)點(diǎn)i的鄰居集合Ni，計(jì)算平均鏈路保持率：

計(jì)算節(jié)點(diǎn)鏈路保持率的時(shí)候可采取簡便算法，對于t時(shí)刻，計(jì)算臨界條件：

r（t）+Dij（t）=R t∈［0，T］（15）

如果能解出臨界時(shí)間t0，則節(jié)點(diǎn)i與j在T周期內(nèi)的鏈路保持率計(jì)算可優(yōu)化為

通過第一步計(jì)算臨界條件，以此減少積分部分的計(jì)算，優(yōu)化計(jì)算過程。

1.3 節(jié)點(diǎn)度差

分簇之后的簇規(guī)模會對網(wǎng)絡(luò)的性能有很大的影響，因此在分簇之前應(yīng)該對理想簇規(guī)模進(jìn)行計(jì)算，對于單跳簇來說也就是計(jì)算理想節(jié)點(diǎn)度。

首先，文獻(xiàn)［11］給出了在理想無干擾協(xié)議模型下，具有n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的吞吐量至少可以達(dá)到：

其中：Θ（）表示一個(gè)正相關(guān)函數(shù)；W表示通信帶寬。為了平衡簇間通信的流量均衡，假設(shè)分簇?cái)?shù)為m，節(jié)點(diǎn)均勻分布則每個(gè)簇的規(guī)模n/m，于是在理想情況下有

其中：Binter-cluster表示簇間帶寬；Binner-cluster表示簇內(nèi)帶寬。理想狀態(tài)下，簇間帶寬平均分給m個(gè)簇，則有Binter-cluster=mBinner-cluster?；诖丝梢越獬鲎顑?yōu)分簇個(gè)數(shù)：

所以理想節(jié)點(diǎn)度為

基于理想節(jié)點(diǎn)度可定義理想節(jié)點(diǎn)度差Di為

Di=|degi-degideal|（21）

在實(shí)際的應(yīng)用中，部分節(jié)點(diǎn)的節(jié)點(diǎn)度高于理想節(jié)點(diǎn)度，但是通過式（21）計(jì)算出的節(jié)點(diǎn)度差指標(biāo)會變小，在其余的指標(biāo)量體現(xiàn)不出差別的情況下，最終計(jì)算出的權(quán)值小于節(jié)點(diǎn)度差大的節(jié)點(diǎn)，所以會導(dǎo)致節(jié)點(diǎn)計(jì)算出的權(quán)值普遍呈梯度型，從節(jié)點(diǎn)度差計(jì)算值大的節(jié)點(diǎn)向小的節(jié)點(diǎn)梯度遞減，這樣的權(quán)值梯度會造成分簇過程的梯度依賴，從而大幅減緩網(wǎng)絡(luò)的分簇過程。如圖3，節(jié)點(diǎn)B的鄰居節(jié)點(diǎn)A具有更大的權(quán)值，所以節(jié)點(diǎn)B會等待節(jié)點(diǎn)A當(dāng)選簇頭之后邀請其入簇，而節(jié)點(diǎn)C又在等待節(jié)點(diǎn)B當(dāng)選簇頭，節(jié)點(diǎn)D在等待節(jié)點(diǎn)C當(dāng)選簇頭。現(xiàn)有文獻(xiàn)中并未對這樣的梯度依賴對分簇過程的影響作出分析和解決。本文對于以上問題的解決思路主要分為兩個(gè)方面：

a）在避免造成熱區(qū)問題的同時(shí)，加快節(jié)點(diǎn)分布稠密部分節(jié)點(diǎn)的分簇過程。

b）對于等待成簇的節(jié)點(diǎn)，快速感知周圍鄰居節(jié)點(diǎn)是否入簇，進(jìn)而更新本節(jié)點(diǎn)的權(quán)值，剔除已入簇節(jié)點(diǎn)，等待下個(gè)周期廣播新的權(quán)值。

基于以上第一個(gè)解決思路，對于計(jì)算出的理想節(jié)點(diǎn)度差做修正：

以上結(jié)果是歸一化之后的結(jié)果，當(dāng)節(jié)點(diǎn)的節(jié)點(diǎn)度大于理想節(jié)點(diǎn)度的時(shí)候直接取最大值。

1.4 權(quán)值計(jì)算過程

綜上，計(jì)算出三個(gè)分簇指標(biāo)量之后，通過加權(quán)方法得到節(jié)點(diǎn)i的分簇權(quán)重值為

Wi=ωF·Fi+ωP·Pi+ωD·Di（23）

其中：ωF、ωP、ωD、ωE分別是四個(gè)分簇指標(biāo)的權(quán)值系數(shù)，要保證ωF+ωP+ωD+ωE=1。具體可根據(jù)網(wǎng)絡(luò)環(huán)境動態(tài)選取。

對于節(jié)點(diǎn)度大于理想節(jié)點(diǎn)度的節(jié)點(diǎn)來說，權(quán)重值應(yīng)該是鄰居節(jié)點(diǎn)中滿足理想節(jié)點(diǎn)度的鄰居節(jié)點(diǎn)組合中計(jì)算出的最大權(quán)重值，具體的計(jì)算方法是對于每一個(gè)鄰居節(jié)點(diǎn)，僅計(jì)算權(quán)重部分中的速度跟隨意識因子和優(yōu)化的鏈路保持率兩部分，記為Win，并將計(jì)算所得的Win從大到小排列，取其中的前degideal個(gè)作為權(quán)值計(jì)算的依據(jù)。同時(shí)為了避免產(chǎn)生熱區(qū)問題，導(dǎo)致一個(gè)簇內(nèi)節(jié)點(diǎn)數(shù)過多，在HELLO消息中增加一個(gè)閾值字段，該字段的值設(shè)置為權(quán)值計(jì)算中不計(jì)入權(quán)值的節(jié)點(diǎn)的Win。

2 分簇算法實(shí)現(xiàn)

2.1 組網(wǎng)過程

本文提出的FSWCA采取分布式的組網(wǎng)過程，步驟如下：

a）網(wǎng)絡(luò)創(chuàng)建的時(shí)候，所有節(jié)點(diǎn)都處于“未決”狀態(tài)。節(jié)點(diǎn)通過周期性地廣播HELLO消息進(jìn)行鄰居感知，并收集鄰居節(jié)點(diǎn)的位置信息、節(jié)點(diǎn)速度信息，通過式（23）計(jì)算出本節(jié)點(diǎn)的權(quán)值W和入簇閾值Win，并在下一個(gè)HELLO周期到來的時(shí)候隨HELLO消息廣播。

b）通過收集鄰居節(jié)點(diǎn)的W，與自己的W比較，如果收到的W集合中沒有比自己更大的，則自舉為簇頭節(jié)點(diǎn)，開始廣播CH通告消息，消息中包含本節(jié)點(diǎn)的W和節(jié)點(diǎn)入簇閾值；如果收到的W集合中存在比自己更大的值，則等待CH通告消息。

c）如果節(jié)點(diǎn)收到CH通告消息，則首先判斷是否滿足入簇閾值要求。

（a）如果通過本節(jié)點(diǎn)和相應(yīng)簇頭節(jié)點(diǎn)的位速信息計(jì)算出的入簇權(quán)值滿足入簇閾值，則向簇頭節(jié)點(diǎn)發(fā)送申請入簇消息，等待簇頭回復(fù)即可完成入簇過程，標(biāo)記本節(jié)點(diǎn)為簇成員節(jié)點(diǎn)。

（b）如果計(jì)算出的入簇權(quán)值不滿足入簇要求，則重新計(jì)算當(dāng)前節(jié)點(diǎn)的權(quán)值W，計(jì)算時(shí)剔除簇頭節(jié)點(diǎn)以及周圍滿足入簇要求的鄰居節(jié)點(diǎn)，等待下一個(gè)HELLO廣播新的權(quán)值W。

d）對于等待入簇的節(jié)點(diǎn)，未能等到有節(jié)點(diǎn)的CH通告消息，說明存在權(quán)值的梯度關(guān)系，如圖3中的C節(jié)點(diǎn)，未能等到節(jié)點(diǎn)B的CH通告消息，因?yàn)楣?jié)點(diǎn)B已經(jīng)加入節(jié)點(diǎn)A為簇頭的簇。為了避免過多的等待以及保證節(jié)點(diǎn)當(dāng)權(quán)簇頭的權(quán)值W的計(jì)算準(zhǔn)確，對每個(gè)節(jié)點(diǎn)的MAC層進(jìn)行改進(jìn)，不再將目的節(jié)點(diǎn)地址不是本節(jié)點(diǎn)的單播消息直接丟棄，而是判斷如果是本節(jié)點(diǎn)的鄰居節(jié)點(diǎn)作為源節(jié)點(diǎn)的申請入簇消息，本節(jié)點(diǎn)在MAC層不將其過濾，而是發(fā)送到網(wǎng)絡(luò)層進(jìn)行處理。網(wǎng)絡(luò)層收到消息之后判斷有鄰居節(jié)點(diǎn)已經(jīng)入簇，則重新計(jì)算權(quán)值，重新判斷本節(jié)點(diǎn)是否自舉為簇頭。

e）重復(fù)步驟b）～d）直至所有節(jié)點(diǎn)都改變自己的身份為簇頭或者簇成員，組網(wǎng)過程結(jié)束。

2.2 簇維護(hù)機(jī)制

2.2.1 節(jié)點(diǎn)出簇入簇

在成簇過程之后，部分簇成員節(jié)點(diǎn)可能會因?yàn)橐苿有远x開舊簇頭的通信范圍，加入其他簇頭的通信范圍。節(jié)點(diǎn)通過自己維護(hù)的與舊簇頭的鏈接保持時(shí)間判定自己是否離開了當(dāng)前簇。如果發(fā)現(xiàn)與簇頭節(jié)點(diǎn)的鏈接保持時(shí)間過期，則認(rèn)為其離開了簇范圍，查找自己的一跳鄰居表中是否有簇頭節(jié)點(diǎn)。如果有，則向其單播請求入簇消息；如果沒有，則將本節(jié)點(diǎn)的狀態(tài)標(biāo)為“未決”，立刻廣播一個(gè)請求入簇消息。如果在本節(jié)點(diǎn)的下一個(gè)HELLO周期到來之前收到了簇頭的同意入簇消息，則標(biāo)記自己為簇成員；如果未能收到同意入簇消息，則證明周圍一跳之內(nèi)無簇頭節(jié)點(diǎn)，在下一個(gè)HELLO周期到來的時(shí)候自舉成簇頭。

2.2.2 高效備用簇頭機(jī)制

分簇結(jié)構(gòu)中的簇頭節(jié)點(diǎn)作為簇內(nèi)成員節(jié)點(diǎn)與簇外節(jié)點(diǎn)通信的轉(zhuǎn)發(fā)節(jié)點(diǎn)，如果簇頭節(jié)點(diǎn)掉線，對應(yīng)的簇成員節(jié)點(diǎn)的通信都會受到影響，所以分簇結(jié)構(gòu)的魯棒性相比分布式結(jié)構(gòu)的魯棒性更弱一些。同時(shí)簇內(nèi)節(jié)點(diǎn)重新進(jìn)行分簇過程會帶來大量的控制開銷，因此提出一種高效的備用簇頭機(jī)制，可以在只增加有限開銷的前提下，大幅減少無人機(jī)自組網(wǎng)分簇結(jié)構(gòu)在簇頭掉線之后的恢復(fù)時(shí)間。簇頭節(jié)點(diǎn)通過周期性地收集簇內(nèi)節(jié)點(diǎn)的權(quán)值信息，選取權(quán)值最高的成員節(jié)點(diǎn)作為備用簇頭，備用簇頭節(jié)點(diǎn)周期性地更新，在簇頭節(jié)點(diǎn)下一個(gè)HELLO周期到來之前計(jì)算新的備用簇頭。

1）備用簇頭通告機(jī)制

如圖4所示，備用簇頭的通告交由簇頭節(jié)點(diǎn)的HELLO消息完成，將備用簇頭的信息放在簇頭節(jié)點(diǎn)HELLO消息中一跳對稱鄰居部分的第一個(gè)條目。

被選為備用簇頭的節(jié)點(diǎn)收到后會標(biāo)記本節(jié)點(diǎn)為備用簇頭節(jié)點(diǎn)。成員節(jié)點(diǎn)收到之后提取第一個(gè)條目，之后查找自己的鄰居表。

a）如果有該節(jié)點(diǎn)的信息，則標(biāo)記該節(jié)點(diǎn)作為本節(jié)點(diǎn)的備用簇頭，并標(biāo)記本節(jié)點(diǎn)為BCH接管節(jié)點(diǎn)。

b）如果鄰居表中沒有相關(guān)條目，且到達(dá)BCH的中繼節(jié)點(diǎn)僅有CH，則標(biāo)記本節(jié)點(diǎn)為不敏感節(jié)點(diǎn)，并且將自己的簇頭保持周期縮短至兩個(gè)HELLO消息，這樣在CH失效之后能快速作出出簇反應(yīng)。同時(shí)，為了保證出簇入簇一致性，在CH層也對敏感節(jié)點(diǎn)進(jìn)行更改保持時(shí)間的操作，具體方法是判斷收到的第三方成員節(jié)點(diǎn)HELLO消息中是否同時(shí)存在該敏感節(jié)點(diǎn)和BCH，如果有則不能被標(biāo)記為敏感節(jié)點(diǎn)；沒有則標(biāo)記為敏感節(jié)點(diǎn)，更改保持時(shí)間。

c）如果鄰居表中沒有相關(guān)條目，且到達(dá)BCH的中繼節(jié)點(diǎn)除了CH還有其他CM，則保存BCH信息，但并不將其認(rèn)做自己的備用簇頭節(jié)點(diǎn)。

2）簇頭切換機(jī)制

主要分為兩個(gè)部分，一個(gè)是正常的簇頭輪換過程（圖4），另一個(gè)是簇頭節(jié)點(diǎn)突然掉線之后的非正常簇頭輪換過程（圖5）。

當(dāng)簇頭節(jié)點(diǎn)發(fā)現(xiàn)本節(jié)點(diǎn)狀態(tài)不足以繼續(xù)擔(dān)任簇頭的時(shí)候啟動正常的簇頭切換機(jī)制。簇頭節(jié)點(diǎn)將自己的狀態(tài)改為“備用簇頭”，之后將維護(hù)的備用簇頭信息作為自己HELLO消息的第一個(gè)條目，廣播新的HELLO消息。等待收到備用簇頭接管簇頭之后的新的HELLO或者成員節(jié)點(diǎn)的新HELLO消息之后就可以確定完成簇頭輪換；如果未收到會重新發(fā)送HELLO。

備用簇頭節(jié)點(diǎn)收到該HELLO消息之后，也知道發(fā)生了簇頭更換過程，并且本節(jié)點(diǎn)就是新任的簇頭，開始執(zhí)行簇頭的任務(wù)，廣播簇頭HELLO消息。

簇成員節(jié)點(diǎn)收到該HELLO消息之后，提取發(fā)送者信息，發(fā)現(xiàn)與本節(jié)點(diǎn)維護(hù)的CH信息一致，就判斷發(fā)生了簇頭更換過程。如果本節(jié)點(diǎn)標(biāo)記為BCH接管節(jié)點(diǎn)，則將BCH作為新簇頭；其余節(jié)點(diǎn)收到之后判定本節(jié)點(diǎn)出簇，執(zhí)行入簇過程。

當(dāng)簇頭節(jié)點(diǎn)因?yàn)楣艋蛘咂渌饬σ蛩赝蝗坏艟€的情況，簇頭節(jié)點(diǎn)還未能進(jìn)行正常的簇頭切換過程。這種情況執(zhí)行非正常簇頭輪換過程，如圖5所示。

備用簇頭節(jié)點(diǎn)一個(gè)周期未能收到簇頭節(jié)點(diǎn)的HELLO消息，可能是因?yàn)楣?jié)點(diǎn)間存在單向鏈路。備用簇頭向簇頭單播一個(gè)入簇申請消息，如果未能收到簇頭節(jié)點(diǎn)的回復(fù)就認(rèn)為簇頭節(jié)點(diǎn)已經(jīng)失效，將本節(jié)點(diǎn)的狀態(tài)改為“簇頭”，然后廣播新的HELLO消息。

a）當(dāng)BCH接管節(jié)點(diǎn)收到新HELLO消息之后更新本節(jié)點(diǎn)的簇頭信息，自動加入新簇。

b）對于不敏感節(jié)點(diǎn)，等待簇頭過期之后，執(zhí)行出簇入簇過程。

c）對于其他成員節(jié)點(diǎn)，收到同簇節(jié)點(diǎn)更改簇頭之后的新HELLO消息，對比本節(jié)點(diǎn)保存的BCH信息和新HELLO中的CH信息，如果相同則認(rèn)為已經(jīng)執(zhí)行了簇頭輪換過程，本節(jié)點(diǎn)執(zhí)行出簇入簇過程。不同則忽略。

2.3 例證分析

圖6中節(jié)點(diǎn)A為當(dāng)前簇的CH，選擇B為簇的BCH，節(jié)點(diǎn)D、H、C、F與節(jié)點(diǎn)B是一跳鄰居節(jié)點(diǎn)，標(biāo)記為BCH接管節(jié)點(diǎn)；節(jié)點(diǎn)E是B的二跳鄰居節(jié)點(diǎn)，同時(shí)不只有CH做中繼，標(biāo)記為普通成員節(jié)點(diǎn)；節(jié)點(diǎn)G是B的二跳鄰居節(jié)點(diǎn)，且僅由CH做中繼節(jié)點(diǎn)，標(biāo)記為敏感節(jié)點(diǎn)。

簇頭節(jié)點(diǎn)掉線對于簇的影響最大的時(shí)間點(diǎn)是在其剛廣播一次HELLO之后立刻掉線，如圖7所示，以這種最壞的情況分析：A掉線之后經(jīng)歷一個(gè)HELLO周期，節(jié)點(diǎn)B發(fā)現(xiàn)一個(gè)周期未收到A的HELLO消息，由于可能存在單向鏈路的原因，無法判斷是否發(fā)生了CH掉線情況，就向A單播一個(gè)request join，如果A沒有掉線會向B發(fā)送回復(fù)；B等待時(shí)間τ之后未收到回復(fù)信息就判斷A掉線，B將自己作為簇頭，立刻廣播新的HELLO消息。D、H、C、F節(jié)點(diǎn)收到之后將B作為新CH。最壞情況下的BCH接管節(jié)點(diǎn)的簇頭更換時(shí)間為T+τ，平均簇頭更換時(shí)間為T/2+τ。

再假設(shè)是最壞的情況，節(jié)點(diǎn)D在收到B的新HELLO的時(shí)候剛廣播了一次HELLO消息，因此新的HELLO消息要等待周期T之后廣播。節(jié)點(diǎn)E收到新HELLO消息之后判斷自己出簇。所以普通成員節(jié)點(diǎn)的最長出簇反應(yīng)時(shí)間是2T+τ。同樣可以分析出最短的出簇反應(yīng)時(shí)間是τ，所以可以得到普通成員節(jié)點(diǎn)的平均出簇反應(yīng)時(shí)間是T+τ。

對于敏感節(jié)點(diǎn)G來說，最長出簇反應(yīng)時(shí)間是2T，平均出簇反應(yīng)時(shí)間是3T/2。非正常簇頭切換時(shí)序圖如圖7所示。

3 仿真分析

本文使用OPNET 14.5仿真軟件對FSWCA的性能進(jìn)行仿真驗(yàn)證。對比的協(xié)議選擇WCA、文獻(xiàn)［8，9］提出的IWCA、文獻(xiàn)［10］提出的WSCA。

FSWCA對分簇算法的改進(jìn)體現(xiàn)在分簇指標(biāo)量和簇維護(hù)機(jī)制中。仿真通過改變節(jié)點(diǎn)的最大移動速度和網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量來反映不同的場景。選用網(wǎng)絡(luò)中分簇個(gè)數(shù)、節(jié)點(diǎn)簇間切換次數(shù)以及成簇時(shí)間四種性能指標(biāo)來反映改進(jìn)分簇指標(biāo)量之后的性能。對于簇維護(hù)機(jī)制的改進(jìn)主要體現(xiàn)在選取備用簇頭，備用簇頭的通告以及快速簇頭切換機(jī)制。因此仿真通過比較分簇算法控制開銷以及部分簇頭節(jié)點(diǎn)失效之后網(wǎng)絡(luò)中掉線節(jié)點(diǎn)的數(shù)量以及恢復(fù)時(shí)間來反映簇維護(hù)機(jī)制的性能。分析中的所有結(jié)果均是基于多次仿真取平均值的結(jié)果。表1是仿真參數(shù)設(shè)置。

因?yàn)槲墨I(xiàn)［8］固定了初始簇結(jié)構(gòu)，所以分簇階段的性能指標(biāo)不加入比較。圖8表示網(wǎng)絡(luò)分簇個(gè)數(shù)隨節(jié)點(diǎn)數(shù)變化，從圖中可以看出，隨著節(jié)點(diǎn)數(shù)量的增加，分簇?cái)?shù)量也在增加，其中WCA增加得最為明顯，IWCA和WSCA指標(biāo)相近，IWCA通過計(jì)算全網(wǎng)節(jié)點(diǎn)的平均節(jié)點(diǎn)度來替代最優(yōu)分簇節(jié)點(diǎn)數(shù)所得的分簇結(jié)構(gòu)更符合實(shí)際的網(wǎng)絡(luò)拓?fù)?，WSCA通過引入附屬簇員來減少孤立簇形成，因此兩種算法得到的結(jié)果優(yōu)于WCA。FSWCA優(yōu)化了分簇過程，對于分簇個(gè)數(shù)并沒有帶來負(fù)面的影響，因此得到的分簇個(gè)數(shù)更接近IWCA。

圖9是成簇時(shí)間隨節(jié)點(diǎn)數(shù)變化圖，成簇時(shí)間定義為從網(wǎng)絡(luò)開始運(yùn)行到所有節(jié)點(diǎn)都改變其狀態(tài)為非未定的時(shí)間?？梢钥吹诫S著節(jié)點(diǎn)數(shù)的增加，幾種分簇算法的成簇時(shí)間都有相應(yīng)的增加，這是因?yàn)楣?jié)點(diǎn)數(shù)增加帶來的網(wǎng)絡(luò)中節(jié)點(diǎn)分布不均勻?qū)е麓嬖跈?quán)值的梯度依賴以及孤立節(jié)點(diǎn)自成簇帶來的延遲。FSWCA通過優(yōu)化節(jié)點(diǎn)度大于理想節(jié)點(diǎn)度部分節(jié)點(diǎn)的權(quán)值計(jì)算過程，一定程度上消除了大范圍的權(quán)值梯度依賴；同時(shí)使節(jié)點(diǎn)泛聽周圍節(jié)點(diǎn)的入簇申請消息，對鄰居節(jié)點(diǎn)的入簇快速作出反應(yīng)，加快了分簇的過程。因此FSWCA在成簇時(shí)間方面表現(xiàn)良好。

圖10表示節(jié)點(diǎn)平均簇間切換次數(shù)與節(jié)點(diǎn)最大移動速度的關(guān)系。FSWCA通過考慮當(dāng)前鄰居節(jié)點(diǎn)速度和無人機(jī)節(jié)點(diǎn)的移動隨機(jī)性優(yōu)化了鏈路保持概率的算法，對比其他三種算法只通過當(dāng)前節(jié)點(diǎn)速度計(jì)算出的鏈路保持時(shí)間更能體現(xiàn)節(jié)點(diǎn)與其鄰居節(jié)點(diǎn)的速度和位置相關(guān)性，分簇更合理，因此FSWCA在簇間切換次數(shù)上面表現(xiàn)均比其他四種算法好。

圖11表示分簇算法的控制開銷和節(jié)點(diǎn)數(shù)的關(guān)系，IWCA的額外開銷主要來源于周期性地獲取全網(wǎng)節(jié)點(diǎn)的節(jié)點(diǎn)度信息。由于需要獲取全網(wǎng)信息，所以IWCA的開銷巨大且不可控；WSCA的額外開銷來源于簇維護(hù)期間周期性計(jì)算權(quán)值系數(shù)的時(shí)候獲取鄰居節(jié)點(diǎn)的四個(gè)分簇指標(biāo)信息以及備用簇頭通告的開銷。FSWCA在成簇階段加入一個(gè)字段用來保存入簇閾值增加了開銷，同時(shí)通過優(yōu)化備用簇頭的通告過程，在不增加額外開銷的情況下完成備用簇頭的簇內(nèi)通告，在簇頭切換的時(shí)候部分簇成員節(jié)點(diǎn)無痕切換節(jié)省多余的控制開銷，且在簇維護(hù)期間僅傳遞每個(gè)節(jié)點(diǎn)的權(quán)值作為額外開銷，所以總體開銷比WSCA更小。

為了模擬網(wǎng)絡(luò)運(yùn)行過程中簇頭無人機(jī)收到攻擊或意外碰撞導(dǎo)致失效的情況下各協(xié)議的應(yīng)對情況，設(shè)計(jì)將當(dāng)選簇頭的節(jié)點(diǎn)在運(yùn)行期間內(nèi)隨機(jī)失效。圖12和13分別表示部分簇頭失效之后，網(wǎng)絡(luò)中產(chǎn)生的掉線節(jié)點(diǎn)數(shù)量和恢復(fù)時(shí)間，恢復(fù)時(shí)間定義為簇頭失效的時(shí)間到簇成員節(jié)點(diǎn)作出反應(yīng)并加入新簇的最長時(shí)間。WSCA和文獻(xiàn)［8］在掉線節(jié)點(diǎn)的數(shù)量上表現(xiàn)較好，因?yàn)橛袀溆么仡^節(jié)點(diǎn)接管部分簇成員節(jié)點(diǎn)，但是其余不能被接管的節(jié)點(diǎn)仍會存在很長的恢復(fù)時(shí)間；FSWCA在簇頭掉線之后備用簇頭快速作出反應(yīng)，直接接管部分簇成員節(jié)點(diǎn)，其余的簇成員節(jié)點(diǎn)也能快速作出出簇反應(yīng)，因此在掉線節(jié)點(diǎn)的數(shù)量和恢復(fù)時(shí)間上FSWCA的表現(xiàn)均優(yōu)于其他算法。

4 結(jié)束語

針對無機(jī)自組網(wǎng)中無人機(jī)節(jié)點(diǎn)移動速度快以及節(jié)點(diǎn)規(guī)模更大導(dǎo)致的網(wǎng)絡(luò)管理低效的問題，提出一種快速穩(wěn)定加權(quán)分簇算法FSWCA。該算法從分簇指標(biāo)量的選取以及簇維護(hù)機(jī)制方面作出改進(jìn)。仿真結(jié)果表明該算法可以優(yōu)化分簇結(jié)果，加快成簇過程，以及在只增加有限控制開銷的基礎(chǔ)上很大程度地提高分簇結(jié)構(gòu)中簇結(jié)構(gòu)的魯棒性。

參考文獻(xiàn)：

［1］王祥科，劉志宏，叢一睿，等.小型固定翼無人機(jī)集群綜述和未來發(fā)展［J］.航空學(xué)報(bào)，2020，41（4）：15-40.（Wang Xiangke，Liu Zhihong，Cong Yirui，et al.Miniature fixed-wing UAV swarms：review and outlook［J］.Acta Aeronautica et Astronautica Sinica，2020，41（4）：15-40.）

［2］黃巍，陳俊良，李猶海.無人機(jī)自組網(wǎng)技術(shù)綜述與發(fā)展展望［J］.電訊技術(shù)，2022，62（1）：138-146.（Huang Wei，Chen Junliang，Li Youhai.Technology survey and development forecast on unmanned aerial Ad hoc networks［J］.Telecommunication Engineering，2022，62（1）：138-146.）

［3］Chatterjee M，Das S K，Turgut D.WCA：a weighted clustering algorithm for mobile Ad hoc networks［J］.Cluster Computing，2002，5：193-204.

［4］Wang Xiangyu，Liu Zhengyang，Jian Chunxiao，et al.A dynamic scale UAV weighted clustering algorithm［C］//Proc of the 4th International Conference on Unmanned Systems.Piscataway，NJ：IEEE Press，2021：209-213.

［5］Sun Yifan，Mi Zhichao，Wang Hai，et al.Adaptive enhanced weighted clustering algorithm for UAV swarm［C］//Proc the 20th International Conference on Communication Technology.Piscataway，NJ：IEEE Press，2020：709-714.

［6］Nie Mengchu，Huang Pinghu，Zeng Jie，et al.A novel dynamic transmission power of cluster heads based clustering scheme［J］.Electro-nics，2023，12（3）：619.

［7］Zhang Yujing，Hu Zhiqun，Wang Zhifei，et al.Survivability analysis of unmanned aerial vehicle network based on dynamic weighted clustering algorithm with dual cluster heads［J］.Electronics，2023，12（7）：1743.

［8］代家銘，宋玉龍，尚亞黎，等.高動態(tài)環(huán)境下航空自組網(wǎng)分簇算法設(shè)計(jì)［J］.計(jì)算機(jī)應(yīng)用研究，2015，32（4）：1193-1198.（Dai Jia-ming，Song Yulong，Shang Yali，et al.Cluster algorithm for aeronautical Ad hoc network in highly dynamic environment［J］.Application Research of Computers，2015，32（4）：1193-1198.）

［9］王沁飛，南建國，黃金科，等.基于加權(quán)的無人機(jī)集群組網(wǎng)分簇算法［J］.計(jì)算機(jī)應(yīng)用研究，2019，36（5）：1500-1503.（Wang Qinfei，Nan Jianguo，Huang Jinke，et al.Weighted based clustering algorithm for FA-NET［J］.Application Research of Computers，2019，36（5）：1500-1503.）

［10］梅家棟，南建國.無人機(jī)自組網(wǎng)基于加權(quán)的穩(wěn)定分簇算法［J］.計(jì)算機(jī)應(yīng)用研究，2021，38（11）：3411-3416.（Mei Jiadong，Nan Jianguo.Weighted stable clustering algorithm for flying Ad hoc network［J］.Application Research of Computers，2021，38（11）：3411-3416.）

［11］Gupta P，Kumar P R.The capacity of wireless networks［J］.IEEE Trans on Information Theory，2000，46（2）：388-404.