高速飛行器自組網(wǎng)快速高效加權(quán)分簇算法

摘 要：針對高速飛行器自組織網(wǎng)絡(luò)中組網(wǎng)時間較長、維護開銷較大、網(wǎng)絡(luò)恢復(fù)較慢等問題，提出了一種快速高效的加權(quán)分簇算法。該算法與現(xiàn)有的加權(quán)分簇算法進行了比較，對平均節(jié)點間距離、平均移動相似度以及節(jié)點度三個指標(biāo)進行了改進；針對梯度抑制導(dǎo)致的組網(wǎng)周期延長問題，優(yōu)化了現(xiàn)有的組網(wǎng)流程；針對備用簇首維護開銷較大的問題，提出了一種高效備用簇首選舉和跨層通告機制；針對簇首節(jié)點突發(fā)損壞的情況下，簇成員反應(yīng)較慢的問題，提出了一種簇成員快速響應(yīng)切換機制。通過OPNET軟件進行仿真模擬，該算法在組網(wǎng)時間、控制開銷及恢復(fù)時間等指標(biāo)上，相較于現(xiàn)有加權(quán)分簇算法均有一定提升。仿真結(jié)果表明，該算法能夠有效提升網(wǎng)絡(luò)性能，更加適用于復(fù)雜環(huán)境下的高速飛行器自組織網(wǎng)絡(luò)。

關(guān)鍵詞：高速飛行器自組網(wǎng)；分簇算法；簇維護；快速恢復(fù)

中圖分類號：TP393"" 文獻標(biāo)志碼：A""" 文章編號：1001-3695（2025）03-032-0888-07

doi： 10.19734/j.issn.1001-3695.2024.07.0257

Rapid and efficient weighted clustering algorithm for high-speed flight vehicle Ad hoc network

Zhang Linquana，b，c， Ren Zhia，b，c， Yang Jianjuna，b，c， Wang Huaia，b，c， Zhang Weia，b，c

（a. School of Communication amp; Information Engineering， b. Key Laboratory of Mobile Communications Technology of Chongqing， c. Enginee-ring Research Center of Mobile Communications of the Ministry of Education， Chongqing University of Posts amp; Telecommunications， Chongqing 400065， China）

Abstract：This paper proposed a fast and efficient weighted clustering algorithm. It addressed long network setup time， high maintenance costs， and slow recovery in self-organizing networks of high-speed aircraft. The algorithm improved three metrics， such as average inter-node distance， average movement similarity， and node degree. It optimized the networking process to reduce setup time caused by gradient suppression. An efficient backup cluster head election and cross-layer notification mechanism lowered maintenance costs. A rapid response switching mechanism for cluster members handled slow responses during sudden cluster head failures. Simulations with OPNET software show significant improvements in setup time， control overhead， and recovery time compared to existing algorithms. Simulation results indicate that the algorithm improves network perfor-mance. It is more suitable for self-organizing networks of high-speed aircraft in complex environments.

Key words：high-speed flight vehicle Ad hoc network; clustering algorithm; cluster maintenance; rapid recovery

0 引言

高速飛行器自組網(wǎng)是一種熱門的網(wǎng)絡(luò)架構(gòu)，其節(jié)點由高速飛行器如戰(zhàn)斗機、高速無人機、高超音速導(dǎo)彈等［1］組成。高速飛行器的應(yīng)用已經(jīng)逐漸成為一種重要的戰(zhàn)術(shù)和戰(zhàn)略資源。然而，與傳統(tǒng)移動自組網(wǎng)相比，高速飛行器自組網(wǎng)呈現(xiàn)出一些獨特的特點。首先，高速飛行器的移動速度極快，可達數(shù)百乃至上千公里/小時［2］，這給網(wǎng)絡(luò)拓撲維護和信息傳輸帶來巨大挑戰(zhàn)；其次，高速飛行器自組網(wǎng)往往涉及大規(guī)模節(jié)點，網(wǎng)絡(luò)規(guī)模龐大且拓撲變化迅速，給網(wǎng)絡(luò)管理和協(xié)調(diào)增添了不少困難；此外，高速飛行環(huán)境下，要求通信的時延可控以及在損傷后快速恢復(fù)［3］方面有非常高的要求。因而，通常采用分簇結(jié)構(gòu)，提高網(wǎng)絡(luò)的可擴展性和可管理性、增強節(jié)點間的協(xié)調(diào)控制、優(yōu)化資源分配和路由選擇［4，5］，從而更好地滿足高速飛行場景下的嚴苛需求。

針對大規(guī)模節(jié)點場景，早期已有最小節(jié)點ID算法和最高連通度算法相關(guān)的研究。兩者均在靜態(tài)場景下有較好應(yīng)用。但前者易產(chǎn)生過多的簇首，引起平均投遞時延增加；后者簇間節(jié)點個數(shù)不一，對含有較多節(jié)點的簇，每個簇成員的吞吐量將急劇下降，降低整體的性能。后續(xù)研究人員綜合考慮節(jié)點間平均距離、移動性、節(jié)點度、能量等指標(biāo)［6～8］，提出適用于完全分布式自組織網(wǎng)絡(luò)場景下的加權(quán)分簇算法（weighted clustering algorithm，WCA）。在部分應(yīng)用場景下，研究人員又考慮了任務(wù)類型。根據(jù)網(wǎng)絡(luò)需求，調(diào)整指標(biāo)所占權(quán)重的方式進行簇首選舉，以此提升網(wǎng)絡(luò)的整體性能。文獻［9］提出了一種加權(quán)K-means算法，在成簇階段綜合考慮節(jié)點轉(zhuǎn)發(fā)能力、移動相似度和能量三者進行簇首輪換，同時引入備用簇首加速拓撲快速恢復(fù)。然而該類算法初始要進行簇首節(jié)點指定，在完全分布式的應(yīng)用場景難以應(yīng)用。

文獻［10］提出了一種基于相對移動性預(yù)測的加權(quán)分簇算法。選舉指標(biāo)不依賴定位信息，采用接收功率來估算節(jié)點間距離，利用多普勒頻移計算相對移動速度，根據(jù)兩者預(yù)測鏈路的維持時間進行選舉。然而，當(dāng)節(jié)點距離較小時，應(yīng)用多普勒頻移計算相對速度對硬件要求較高，在速度較小時不準確，導(dǎo)致其關(guān)鍵選舉指標(biāo)鏈路維持時間誤差較大，影響組網(wǎng)和后續(xù)簇維護。文獻［11］針對軍用飛行器由于高速移動帶來的結(jié)構(gòu)不穩(wěn)定問題，借助地理位置信息與移動性進行簇首選舉。然而，該算法缺少對備用簇首的定期維護，并且附屬簇成員改變了原有的單跳簇結(jié)構(gòu)，增大了傳輸時延和丟包率。文獻［12］提出了一種基于加權(quán)的穩(wěn)定分簇算法（weight stable clustering algorithm，WSCA），改進了權(quán)值賦值方法，使得分簇算法能夠加入一定的主觀性。采用動態(tài)閾值進行簇首輪換，卻存在簇維護開銷過大的問題，降低了整體的吞吐量。文獻［13］提出一種動態(tài)尺度加權(quán)分簇算法（dynamic scale weighted clustering algorithm，DSWCA），引入了動態(tài)集群尺度來減少孤立通信節(jié)點，根據(jù)簇首能力閾值來進行備用簇首輪換。該算法僅根據(jù)單一指標(biāo)進行簇首更替，導(dǎo)致在高動態(tài)、不以能量因素為主導(dǎo)的應(yīng)用場景下表現(xiàn)不佳。文獻［14］提出一種快速穩(wěn)定加權(quán)分簇算法（fast and stable weighted clustering algorithm，F(xiàn)SWCA）。該算法改進了選舉指標(biāo)，緩解了梯度依賴現(xiàn)象；改進了備用簇首通告機制，降低了簇維護階段的開銷；改進了簇成員響應(yīng)機制，加速了網(wǎng)絡(luò)恢復(fù)。然而，其簇成員響應(yīng)機制容易產(chǎn)生簇首損壞的“虛警”，即因丟包造成備用簇首誤認為簇首損壞，并執(zhí)行簇首輪換操作，影響正常通信。

基于以上分析，現(xiàn)有加權(quán)分簇算法仍存在指標(biāo)選取不合理、組網(wǎng)較慢、簇維護開銷較大及拓撲恢復(fù)不及時等問題，為此提出了一種功率感知的快速高效加權(quán)分簇算法（power-aware weighted clustering algorithm，PWCA）。在組網(wǎng)階段，該算法提出了平均節(jié)點間距離、平均節(jié)點間移動相似度和連接可靠性因子修正的節(jié)點度三個分簇選舉指標(biāo)量，并對組網(wǎng)流程進行優(yōu)化，加速了組網(wǎng)進程。在簇維護階段，該算法提出一種備用簇首選舉和高效跨層通告機制，降低了簇維護階段的開銷；提出了一種簇內(nèi)成員快速響應(yīng)切換機制，加快了損傷后的拓撲恢復(fù)。

1 網(wǎng)絡(luò)模型與問題描述

1.1 網(wǎng)絡(luò)模型

如圖1所示，將飛行器節(jié)點分成多個簇群，下層是集中式的單跳網(wǎng)絡(luò)，簇群內(nèi)的節(jié)點采用相同發(fā)射頻段，經(jīng)簇首節(jié)點進行通信。上層網(wǎng)絡(luò)是簇首組成的分布式多跳網(wǎng)絡(luò)，簇內(nèi)成員節(jié)點通信要經(jīng)由簇首轉(zhuǎn)發(fā)。單跳簇的網(wǎng)絡(luò)架構(gòu)具有時延低、結(jié)構(gòu)穩(wěn)定及損傷快速恢復(fù)等優(yōu)勢。因而，在高速飛行器網(wǎng)絡(luò)中，往往采用該網(wǎng)絡(luò)模型。

1.2 問題描述

在深入研究分簇算法后，發(fā)現(xiàn)其存在以下問題：

a）現(xiàn)有選舉指標(biāo)，如平均節(jié)點間距離、鏈路的維持時間、節(jié)點的移動性等［11～14］，往往依賴于衛(wèi)星定位提供的位置信息。在受到惡意攻擊而無法使用衛(wèi)星定位時，這些基于位置信息的指標(biāo)計算就會受到影響，從而影響正常的網(wǎng)絡(luò)組建進程。為了解決這一問題，該算法采用接收功率來估計節(jié)點間距離，據(jù)此基于無線信號強度對加權(quán)分簇常用的指標(biāo)進行計算，減少對于定位信息的依賴，令其更廣泛地適用于高速飛行器編隊網(wǎng)絡(luò)場景，即使在遭受惡意干擾而無法獲取可靠的位置信息時，也能夠正常進行簇首選舉和后續(xù)維護。

b）現(xiàn)有分布式移動場景下的組網(wǎng)流程，對于梯度依賴現(xiàn)象沒有很好的解決辦法。如圖2所示，是一個典型的梯度依賴現(xiàn)象。節(jié)點C被B抑制成簇，節(jié)點D同理，在隨機分布的情況下，位于網(wǎng)絡(luò)中心的節(jié)點往往權(quán)值呈現(xiàn)梯度差的形式。已有相關(guān)研究通過改善選舉指標(biāo)［14］，或通過旁聽更新自身權(quán)值的方式來減緩權(quán)值梯度依賴帶來的影響。然而更新權(quán)值后的節(jié)點并不一定適合成為簇首、或者因更新消息碰撞，帶來的部分節(jié)點遲入網(wǎng)甚至無法入網(wǎng)，組網(wǎng)失敗的情況。例如，已入網(wǎng)節(jié)點B向C發(fā)送更新通告包，然而C未收到該包，導(dǎo)致節(jié)點C始終等待B成簇，周圍節(jié)點受到節(jié)點C的抑制無法成簇，遲遲不能入網(wǎng)。

c）在網(wǎng)絡(luò)正常運行中，周期性地選舉備用簇首與通告全簇，存在維護開銷較大的問題，且選舉周期主觀性較強，具體如下：（a）較長的周期會導(dǎo)致備用簇首更新不及時，在簇首節(jié)點突然損壞的情況下，不合適的備用簇首節(jié)點接管原簇，會導(dǎo)致大量的節(jié)點掉線；（b）較短的周期會增大控制開銷，影響正常通信，降低了整體的吞吐量。

同時，在簇首節(jié)點突發(fā)損壞時，存在簇內(nèi)成員響應(yīng)較慢的問題。因而，從簇首選舉指標(biāo)改善、組網(wǎng)流程改進和簇維護機制改進三方面來解決上述問題。

2 簇首選舉指標(biāo)

PWCA包含平均節(jié)點間距離、平均移動相似度和改進后的節(jié)點度三個選舉指標(biāo)。其中平均節(jié)點間距離反映了整個網(wǎng)絡(luò)的節(jié)點分布情況；平均移動相似度是利用兩節(jié)點間的變異系數(shù)來反映的，用于衡量節(jié)點的穩(wěn)定程度；而改進后的節(jié)點度，能反映節(jié)點的鄰居數(shù)量以及與鄰居通信質(zhì)量好壞。節(jié)點通過周期性地交換控制消息來計算分簇權(quán)重，用于完成后續(xù)簇首選舉。

2.1 平均節(jié)點間距離

假定飛行器節(jié)點的發(fā)射功率是恒定的。節(jié)點滿足自由空間路徑損耗模型，其中L（dB）是信號功率損耗，路徑損耗是指信號從發(fā)射機到接收機傳播過程中功率損失的程度。Pt是發(fā)射功率，Pr是接收功率。發(fā)射功率Pt與接收功率Pr的比值反映了信號功率的衰減程度，電磁波在自由空間中傳播時，其功率密度會隨著距離d的平方而衰減。Gl是收發(fā)增益之積，λ是載波波長，如式（1）所示。

3 分簇算法具體實現(xiàn)

3.1 組網(wǎng)過程

在高速飛行器網(wǎng)絡(luò)場景中，由于飛行器運行速度較快，拓撲的變化情況較為復(fù)雜。在分簇過程中，若因丟包使得未入網(wǎng)節(jié)點未能更新已入網(wǎng)節(jié)點的權(quán)重，導(dǎo)致部分區(qū)域節(jié)點始終受到梯度抑制，進而引發(fā)組網(wǎng)進程延緩甚至組網(wǎng)失敗。未能入網(wǎng)的節(jié)點需要周期性地廣播自身消息，以重新進行下一輪次的簇首選舉，直至所有節(jié)點完成入網(wǎng)。

3.1.1 組網(wǎng)流程

圖3是PWCA一個輪次內(nèi)的組網(wǎng)流程，未能在當(dāng)前輪次入網(wǎng)的節(jié)點要進行下一輪次的簇首選舉和入簇流程，直到所有節(jié)點均成為已入網(wǎng)節(jié)點，組網(wǎng)結(jié)束。

PWCA的具體組網(wǎng)流程如下：

a）節(jié)點啟動后，節(jié)點處于“未決”節(jié)點狀態(tài)（N-node）。

b）節(jié)點通過周期性地廣播hello消息進行鄰居感知，計算出本節(jié)點的權(quán)重值，并在下一個hello消息中廣播。

c）根據(jù)節(jié)點收到的鄰居節(jié)點權(quán)值集合和本地存儲的鄰居權(quán)值表中的權(quán)值大小，判斷自身是否成為簇首。將節(jié)點類型分為以下五類，并執(zhí)行相應(yīng)入網(wǎng)流程：

（a）自舉為簇首節(jié)點，修改自身節(jié)點狀態(tài)為“入網(wǎng)”狀態(tài)（I-node）；廣播CH成簇消息，在接收到節(jié)點入簇請求消息后，回復(fù)入簇答復(fù)消息，完成簇成員節(jié)點的入網(wǎng)。

（b）未能自舉為簇首，但能收到CH成簇消息后修改自身節(jié)點狀態(tài)為“等待”狀態(tài)（W-node）；向簇首節(jié)點發(fā)送入簇請求消息；接收到入簇答復(fù)消息后，完成入網(wǎng)。修改自身節(jié)點狀態(tài)為“入網(wǎng)”狀態(tài)（I-node）。

（c）未能自舉為簇首，未能收到成簇消息，但能聽到鄰居節(jié)點的入簇請求消息的節(jié)點N-node；一段時間后額外廣播一個Q-hello消息更新自身在鄰居節(jié)點中的權(quán)值。

（d）未能自舉為簇首，未能收到成簇消息、鄰居節(jié)點的入簇請求消息，但能聽到Q-hello消息的節(jié)點N-node；一段時間后重新進入簇首選舉狀態(tài)，該類型節(jié)點重新判斷自身能否二次成簇。

（e）未能自舉為簇首，未能收到成簇消息、鄰居節(jié)點的入簇請求消息，以及Q-hello消息的節(jié)點N-node；等待進入下一輪周期性選舉。

d）一個選舉輪次周期內(nèi)未能完成入網(wǎng)的節(jié)點，將自身節(jié)點狀態(tài)修改為N-node，執(zhí)行完轉(zhuǎn)步驟b）。

e）所有節(jié)點狀態(tài)均進入I-node，組網(wǎng)流程結(jié)束。

3.1.2 例證分析

在節(jié)點數(shù)較多且分布不均的場景下，梯度依賴現(xiàn)象十分常見。如圖4所示，對于傳統(tǒng)的周期性選舉的組網(wǎng)流程，包含area_1與area_2區(qū)域內(nèi)的節(jié)點不能在當(dāng)前輪次實現(xiàn)入網(wǎng)，增加了選舉輪次，開銷更大，并且組網(wǎng)時間更長。

文獻［12］中，WSCA組網(wǎng)流程是，通過不斷探測鄰居狀態(tài)信息，更新權(quán)值再選舉，直至所有節(jié)點入網(wǎng)。這在高動態(tài)的環(huán)境中并不適用，節(jié)點動態(tài)移動導(dǎo)致的權(quán)值更新滯后，且由于碰撞或其他原因接收不到更新信息時，該種組網(wǎng)方式會導(dǎo)致節(jié)點入網(wǎng)時間延長，甚至部分節(jié)點始終無法完成入網(wǎng)操作。如圖4中的節(jié)點C，未能收到節(jié)點B的信息的情況下，始終被節(jié)點B所抑制，最終該部分節(jié)點無法入網(wǎng)成功，等待若干時間后自舉為簇首，增加了孤立通信節(jié)點的數(shù)量。

文獻［14］中，在FSWCA的組網(wǎng)流程中，節(jié)點沒有額外的Q-hello操作，未能收到成簇消息及鄰居節(jié)點的入簇請求消息的節(jié)點無法更新鄰居節(jié)點的權(quán)值，因而僅有area_1可以完成入網(wǎng)；在area_2區(qū)域中，節(jié)點C僅在本地更新了自身權(quán)值，卻被節(jié)點D所抑制無法自舉成簇首，該區(qū)域節(jié)點在一段時間后重新進入下一輪選舉。

在PWCA的組網(wǎng)流程中，節(jié)點A的權(quán)值最高成為簇首，執(zhí)行成簇操作；節(jié)點B未能自舉為簇首，但能收到CH成簇消息，執(zhí)行入網(wǎng)操作；節(jié)點C偵聽到節(jié)點B的入簇申請，且自身處于N-node狀態(tài)，更新自身權(quán)值和廣播Q-hello消息；節(jié)點D收到C的權(quán)值更新hello消息，消除了梯度抑制，被選舉為簇首節(jié)點，在當(dāng)前輪次內(nèi)實現(xiàn)節(jié)點入網(wǎng)，增加了單輪入網(wǎng)節(jié)點個數(shù)，減少了組網(wǎng)輪次，實現(xiàn)更快速的入網(wǎng)。

3.2 簇維護機制

在高速飛行器網(wǎng)絡(luò)場景中，對時延的可控和頻譜利用率有較高的要求。因而，在分簇完成后，MAC層技術(shù)切換至TDMA協(xié)議。簇首根據(jù)分簇階段中收集的同頻干擾信息計算和切換至不同頻段進行簇內(nèi)通信，簇間通信采用CSMA/CA協(xié)議。

簇首在損壞前，視為能夠正常執(zhí)行簇首節(jié)點的功能，為保證通信的可靠以及減少額外的開銷，極少主動進行簇首的更換。簇首節(jié)點與簇成員節(jié)點之間通過存活消息的方式來維護兩者之間的聯(lián)系。對部分離開通信范圍的節(jié)點，簇首在其存活周期過期后，刪除對應(yīng)的成員表和路由信息。在簇首節(jié)點遭受打擊損壞時，備用簇首快速響應(yīng)和完成簇內(nèi)成員的接管。因而簇的維護機制主要在于備用簇首的選舉和通告，以及簇首非正常損壞下的簇內(nèi)節(jié)點的快速響應(yīng)。

3.2.1 備用簇首選舉機制

簇首作為整個網(wǎng)絡(luò)的中心，依照簇內(nèi)成員節(jié)點與自身的相似程度來指定初始備用簇首。簇成員向簇首發(fā)送的入簇請求消息中，攜帶該節(jié)點與本簇簇首的移動相似度及連接可靠性因子。簇首根據(jù)兩者以及本地存儲的最新距離信息計算最合適的初始備用簇首，并廣播通告全簇成員。

網(wǎng)絡(luò)正常運行中，一段時間內(nèi)簇內(nèi)節(jié)點必須向簇首發(fā)送通信消息或存活消息，以供簇首更新簇成員存活周期。簇內(nèi)成員正常通信要經(jīng)過簇首節(jié)點轉(zhuǎn)發(fā)。簇首通過節(jié)點的數(shù)據(jù)包或存活消息的接收功率信息來收集一段時間內(nèi)節(jié)點與自身的距離變化情況。分簇完成后，備用簇首的更新采用按需更新機制。當(dāng)成員數(shù)發(fā)生變化或者設(shè)定時間過期時，簇首節(jié)點將根據(jù)備用簇首權(quán)值來進行備用簇首更替，并通過跨層通告機制來通告全簇。

3.2.2 備用簇首高效跨層通告機制

如圖5所示，一個時幀內(nèi)包含了固定分配時隙、動態(tài)分配時隙及自由競爭時隙。簇首節(jié)點在每個時幀的第一個時隙廣播beacon幀，簇內(nèi)成員節(jié)點提取自身時隙，并在自身時隙內(nèi)發(fā)送數(shù)據(jù)包。

針對備用簇首更新消息不及時和開銷大的問題，提出了一種高效的跨層通告機制。簇首節(jié)點在廣播beacon幀時，對時隙進行排序。第一個時隙分配給當(dāng)前的簇首節(jié)點自身使用。將第二個時隙分配給備用簇首節(jié)點使用。普通節(jié)點在提取自身時隙分配的同時，根據(jù)位次可以讀取到備用簇首節(jié)點的信息，進而更替本地的備用簇首信息。通過時隙順序的信息來進行備用簇首通告，避免了原有的備用簇首通知分組的開銷，也避免了由于備用簇首通告分組的丟失導(dǎo)致簇成員節(jié)點無法及時更新備用簇首信息的問題。備用簇首選舉與通告機制偽代碼如下。

算法1 備用簇首選舉與通告機制

輸入： Node_List， //簇內(nèi)節(jié)點列表

Distance_Record。//簇首與每個成員節(jié)點的距離變化數(shù)組

輸出： Backup_CH。 //備用簇首節(jié)點

說明： Node_List： 簇內(nèi)所有節(jié)點的列表

Distance_Record： 簇首與每個成員節(jié)點的距離變化數(shù)組

Node.is_Backup_CH： 備用簇首標(biāo)志位

Backup_CH： 備用簇首節(jié)點

CH_node： 簇首節(jié)點

Node.Backup_CH： 每個節(jié)點本地存儲的備用簇首 ID

初始化： t = 0; Node_List; Node.is_Backup_CH = 1;

Node.Backup_CH = none /*初始化運行時間、成員節(jié)點列表、節(jié)點備用簇首標(biāo)志位、備用簇首*/

while t lt; T and Node_List unchanged：

Collect_Distance_Records（Node_List， Distance_Record）

//收集距離變化數(shù)據(jù)

end while

if t gt; T or Node_List changed

a） for CH_node： //簇首節(jié)點

Calc_Node_Weight（node， Distance_Record）

//計算節(jié)點作為備用簇首的權(quán)重

Node_List.max（x：x.weight， reverse=true）

//選擇最大權(quán)值的節(jié)點作為備用簇首節(jié)點

Backup_CH = Node_List［0］.id

//簇首更新備用簇首

Network_Layer.Notify_MAC_Layer（Node_List）

//簇首節(jié)點MAC層更新成員節(jié)點列表

MAC_Layer.Update_Beacon_Timeslots（Node_List）

//簇首節(jié)點更新beacon幀時隙順序

MAC_Layer.Broadcast_Beacon（）

//下一個beacon時段進行廣播

b） for node in Node_List： //成員節(jié)點更新本地備用簇首

if MAC_Layer.Received_Beacon（）

node.is_Backup_CH = true

else

Backup_CH = Node_List［0］.id

end if

3.2.3 簇內(nèi)成員快速響應(yīng)切換機制

為保證飛行器節(jié)點能不間斷地進行通信，正常運行狀態(tài)下極少進行主動切換。主動切換狀態(tài)下，簇首廣播退網(wǎng)，偵聽到退網(wǎng)通告的簇內(nèi)成員節(jié)點根據(jù)本地存儲的備用簇首信息直接申請入網(wǎng)。而在簇首突發(fā)損壞時，通信的恢復(fù)速度與簇內(nèi)成員的響應(yīng)機制有關(guān)。

圖6為簇首突發(fā)損壞后，簇內(nèi)成員快速響應(yīng)的流程。如果備用簇首節(jié)點在當(dāng)前輪次未能收到beacon消息，則旁聽簇內(nèi)其他成員節(jié)點是否有通信活動。若在本輪內(nèi)也未能聽到簇內(nèi)其他節(jié)點的信息，則認為簇首節(jié)點已經(jīng)損壞。備用簇首節(jié)點根據(jù)上一個beacon幀包含的時間信息計算出本簇的時幀長度和下一個競爭入網(wǎng)時隙的具體時間點。備用簇首將在其本地計算得到的競爭入網(wǎng)時隙內(nèi)，廣播成簇通知消息。

普通成員節(jié)點如果本輪內(nèi)沒有收到簇首的beacon消息，此時存在簇首節(jié)點損壞或自身離開通信范圍兩種情況。若能偵聽到備用簇首成簇通知消息，則立即向備用簇首申請入簇。少數(shù)未能收到成簇通知消息的節(jié)點，在連續(xù)未能偵聽到三個beacon幀后，根據(jù)本地存儲的備用簇首節(jié)點信息發(fā)送入簇申請消息，并執(zhí)行簇首選舉流程。若收到答復(fù)入簇請求，則說明備用簇首檢測到簇首損壞，且在自身通信范圍內(nèi)，則終止簇首選舉流程，完成入簇。若收到其他簇首節(jié)點的beacon幀消息，在對應(yīng)自由競爭時隙，向該簇首節(jié)點發(fā)送入簇請求消息加入對應(yīng)簇。若均未收到，則進行簇首選舉流程，成為簇首或者簇成員，完成入網(wǎng)。備用簇首快速響應(yīng)機制偽代碼如下。

算法2 備用簇首快速響應(yīng)機制

輸入： Node_List， //簇內(nèi)節(jié)點列表

Backup_CH， //備用簇首節(jié)點

Beacon_Frame。 //接收到的 beacon 幀

說明： Node_List： 簇內(nèi)所有節(jié)點的列表

Node.is_CH： 簇首標(biāo)志位

Backup_CH： 備用簇首節(jié)點

CH_node： 簇首節(jié)點

Node.Backup_CH： 每個節(jié)點本地存儲的備用簇首 ID

初始化： t = 0， Node_List， Node.is_CH = 1，

Node.Backup_CH = none /*初始化運行時間、成員節(jié)點列表、簇首標(biāo)志位、備用簇首*/

while t lt; T and receive_beacon（Beacon_Frame）：

t = 0 //監(jiān)聽 beacon 消息，重置過期時間

calculate time_frame_length，next_slot

//計算時幀長度和競爭入網(wǎng)時隙

end while

if ?。╮eceive_beacon（） || receive_cluster_member_info（））

//監(jiān)聽簇內(nèi)其他節(jié)點信息

a） for Backup_CH_Node：//備用簇首節(jié)點響應(yīng)

Node.is_CH = true; //更改節(jié)點狀態(tài)為簇首

broadcast_cluster_notification（next_slot）

//在競爭入網(wǎng)時隙內(nèi)廣播成簇通知消息

backup_cluster_head_election（Node_List）：

//調(diào)用備用簇首選舉通告機制，更新beacon幀并廣播

MAC_Layer.Update_Beacon_Timeslots（Node_List）

MAC_Layer.Broadcast_Beacon（）

b） for node in Node_List： //成員節(jié)點相關(guān)操作

member_node_response（node） //簇成員節(jié)點申請入網(wǎng)

node.extract_timeslot（Beacon frame）

//提取自身時隙

end if

3.3 復(fù)雜度分析與性能評估

3.3.1 算法復(fù)雜度分析

從時間、空間兩個方面分析PWCA的復(fù)雜度。設(shè)網(wǎng)絡(luò)規(guī)模為N，節(jié)點的平均節(jié)點度為D。由于組網(wǎng)階段每個節(jié)點都需要進行鄰居感知和權(quán)重計算，時間復(fù)雜度與節(jié)點數(shù)量N和鄰居數(shù)量D成正比，即O（N×D）。每個節(jié)點需要存儲鄰居信息、權(quán)值信息和狀態(tài)信息，空間復(fù)雜度與節(jié)點數(shù)量N和鄰居數(shù)量D成正比，即O（N×D）。在組網(wǎng)階段，時間復(fù)雜度和空間復(fù)雜度均可認為是O（N）。在簇維護機制上采用了跨層設(shè)計，利用了節(jié)點的數(shù)據(jù)消息和存活消息的接收功率計算節(jié)點間距離和移動相似度，據(jù)此進行備用簇首的維護和選擇，減少了部分控制開銷。簇首收集距離變化數(shù)據(jù)的空間復(fù)雜度為O（K），其中K為本簇內(nèi)節(jié)點數(shù)量，所有簇首占用的總空間復(fù)雜度為O（N）。簇首選舉備用簇首的時間復(fù)雜度為O（K）?？焖夙憫?yīng)機制中，備用簇首監(jiān)聽簇首狀態(tài)，自舉為簇首后，也要調(diào)用備用簇首選舉和通告機制。因此，整個算法的時間復(fù)雜度為O（N），空間復(fù)雜度為O（N）。

3.3.2 算法性能評估

PWCA組網(wǎng)過程充分利用了單輪選舉中收集到的信息，在入網(wǎng)過程中，消除了梯度抑制帶來的部分區(qū)域遲入網(wǎng)的問題，加快了組網(wǎng)進程。借助正常通信和心跳信息感知接收功率變化，選舉備用簇首，減少了一定的備用簇首選舉開銷。通過beacon幀的時隙順序來通告?zhèn)溆么厥椎倪x擇與更替，去除了備用簇首通告的開銷，同時更加可靠地傳遞了備用簇首信息。假設(shè)簇首在廣播beacon幀前掉線，那么備用簇首節(jié)點能在當(dāng)前時幀的自由競爭時隙內(nèi)完成切換。在最差的情況下，即簇首節(jié)點廣播完beacon幀消息后掉線，備用簇首節(jié)點能在下一個時幀的自由競爭時隙內(nèi)完成身份切換，實現(xiàn)簇首損壞的快速發(fā)現(xiàn)和簇成員接管，加快了網(wǎng)絡(luò)的恢復(fù)。

4 仿真分析

使用OPNET 14.5仿真軟件對PWCA的性能進行仿真驗證。對比選取的協(xié)議有WCA、文獻［9］、WSCA［12］、DSWCA［13］及FSWCA［14］，仿真參數(shù)如表1所示。仿真通過調(diào)整節(jié)點數(shù)量、損壞程度及運行速度來反映不同場景下各算法的相關(guān)性能。從分簇個數(shù)、組網(wǎng)輪次和組網(wǎng)開銷三個方面來反映組網(wǎng)階段算法性能。簇首損壞后，通過掉線節(jié)點數(shù)量、恢復(fù)時間以及總控制開銷來反映簇維護階段的算法性能。

仿真場景中，設(shè)置若干打擊目標(biāo)，節(jié)點以不超過設(shè)定最大速度向目標(biāo)靠近執(zhí)行打擊任務(wù)，簇首節(jié)點在損壞前，視為能夠正常執(zhí)行簇首節(jié)點功能，不進行簇首切換。簇內(nèi)通信MAC層初始使用CSMA/CA協(xié)議進行組網(wǎng)和收集同頻干擾信息，在入網(wǎng)完成后切換至TDMA協(xié)議，簇首根據(jù)組網(wǎng)階段收集到的同頻干擾信息切換至不同頻段。簇間通信使用CSMA/CA協(xié)議。

組網(wǎng)階段，選取了網(wǎng)絡(luò)架構(gòu)同為單跳簇的WCA、DSWCA、FSWCA與PWCA進行對比。圖7、8是成簇個數(shù)、成簇輪次與節(jié)點總數(shù)的關(guān)系變化圖。隨著節(jié)點數(shù)的增加，簇的數(shù)量和組網(wǎng)輪次呈現(xiàn)不斷增加的趨勢。WCA隨著節(jié)點數(shù)量增加，孤立簇首不斷增多。DSWCA引入了動態(tài)集群尺度來減少孤立通信節(jié)點，因而成簇個數(shù)也表現(xiàn)較好，然而組網(wǎng)流程與原始的WCA協(xié)議沒有差別，故而組網(wǎng)較慢。在組網(wǎng)過程中，F(xiàn)SWCA設(shè)置了入簇閾值，減少了較遠節(jié)點入簇的概率，一定程度上減少了孤立通信節(jié)點的產(chǎn)生。FSWCA協(xié)議對節(jié)點度進行了改進，緩解了部分梯度抑制問題，因而組網(wǎng)輪次相較于WCA與DSWCA更少。PWCA對于組網(wǎng)流程中的改進，降低了上一輪選舉與下一輪選舉區(qū)域之間的節(jié)點成為孤立通信節(jié)點的可能，令一跳以外的受抑制節(jié)點也參與到本輪的簇首選舉中，進一步縮短了組網(wǎng)輪次，加快了組網(wǎng)進程。在成簇個數(shù)方面，PWCA表現(xiàn)較好，同時也能較快地完成組網(wǎng)。

如圖9所示，是組網(wǎng)開銷和節(jié)點個數(shù)之間的關(guān)系。由于當(dāng)前輪次選舉入網(wǎng)的節(jié)點不會參與到下一輪的信息交互和選舉中，所以組網(wǎng)開銷與組網(wǎng)輪次基本呈正相關(guān)。由于引入了Q-hello的額外開銷，每輪組網(wǎng)開銷實際上高于其他算法，例如在36節(jié)點時，能看到PWCA的組網(wǎng)開銷高于FSWCA。而隨著節(jié)點數(shù)的增加，PWCA協(xié)議所需組網(wǎng)輪次更少。隨著節(jié)點數(shù)增多，相對于其他算法，PWCA的組網(wǎng)開銷更小。

簇維護階段選取了文獻［9］、WSCA、DSWCA、FSWCA與PWCA進行對比。圖10顯示了不同算法在簇首損壞時節(jié)點掉線數(shù)量的表現(xiàn)對比。DSWCA中，在簇首能量降低到閾值前，不會主動進行備用簇首的重新選擇。雖然開銷較小，但在簇首突發(fā)損壞的情況下，此時的備用簇首節(jié)點并不適合接管原簇，導(dǎo)致掉線節(jié)點較多。文獻［9］、FSWCA和WSCA中均是采用了周期性更新備用簇首的模式，因而簇首突發(fā)損壞時掉線節(jié)點數(shù)均明顯低于DSWCA。而WSCA在簇維護中引入附屬簇成員機制，可以連接一跳外的掉線節(jié)點，作為附屬簇成員，擴展了簇的范圍，因而其掉線節(jié)點數(shù)最少。但附屬簇成員會帶來平均傳輸時延的增加，也會影響傳輸成功率。PWCA選舉備用簇首節(jié)點考慮了與簇首之間的移動相似度，并且備用簇首節(jié)點更新更加及時，通告機制更加可靠，使得在簇首損壞時，掉線節(jié)點數(shù)較少。在不改變單跳簇網(wǎng)絡(luò)模型的情況下，PWCA相比其他算法表現(xiàn)更優(yōu)。

圖11是節(jié)點于不同最大運動速度的突發(fā)損壞場景下，不同算法最長恢復(fù)時間。其中節(jié)點總數(shù)為90個，損壞簇首數(shù)設(shè)置為5個。WSCA、DSWCA以及文獻［9］均是通過心跳消息感知簇首狀態(tài)，仿真設(shè)置心跳消息為2 s，備用簇首在三個周期內(nèi)接收不到簇首的心跳消息則認為簇首節(jié)點損壞，執(zhí)行接管簇成員操作。FSWCA改進了簇成員響應(yīng)機制，備用簇首能夠快速響應(yīng)并且完成接管操作。然而，在仿真過程中發(fā)現(xiàn)，F(xiàn)SWCA出現(xiàn)虛警現(xiàn)象的概率高于其他算法，即備用簇首節(jié)點因丟包未收到心跳消息，誤以為簇首損壞而準備接管簇成員，影響正常通信。PWCA借助beacon幀消息與簇內(nèi)通信活動兩方面感知簇首狀態(tài)，降低了虛警概率，同時令備用簇首能夠在最長兩個時隙內(nèi)感知到簇首損壞并執(zhí)行簇首輪換操作，因而表現(xiàn)較好。

圖12展示了在30%損壞率下，不同算法在不同節(jié)點數(shù)下的總控制開銷變化情況?？刂崎_銷來源于節(jié)點的存活消息、維護備用簇首的開銷，以及拓撲改變后的入簇申請和答復(fù)開銷。DSWCA對于備用簇首的維護開銷較小，但其掉線節(jié)點數(shù)較多，重新入網(wǎng)的節(jié)點較多，增加了部分開銷。文獻［9］對備用簇首選舉指標(biāo)進行了改進，減少了備用簇首選舉的部分開銷，因而低于WSCA。FSWCA通過在簇首心跳消息中攜帶備用簇首通告，減少了部分控制開銷，因而相較于WSCA和文獻［9］，控制開銷較少。PWCA設(shè)計了跨層備用簇首選舉和通告機制，減少了備用簇首維護和通告帶來的開銷，因而控制開銷相較于現(xiàn)有算法更低。

5 結(jié)束語

針對高速飛行器自組網(wǎng)的組網(wǎng)流程較長、簇維護開銷較大、簇首損壞恢復(fù)較慢的問題，提出一種功率感知的快速高效加權(quán)分簇算法PWCA。該算法改進了分簇指標(biāo)量的選取、組網(wǎng)流程及簇維護機制。仿真驗證了該算法能有效減少成簇輪次，降低簇維護階段的控制開銷，縮短簇首損壞后的恢復(fù)時間。在后續(xù)的研究中，將針對當(dāng)網(wǎng)絡(luò)拓撲發(fā)生巨大變化時，例如簇首突發(fā)損壞、簇融合與分裂，如何加速拓撲信息的收斂，圍繞更加快速恢復(fù)網(wǎng)絡(luò)通信作進一步研究。

參考文獻

［1］陳大薇， 張永亮， 段鵬飛， 等. 高超聲速飛行器數(shù)據(jù)鏈關(guān)鍵技術(shù)分析及展望 ［J］. 航空兵器， 2023， 30（4）： 26-32. （Chen Dawei， Zhang Yongliang， Duan Pengfei， et al. Analysis and prospect of key technologies for hypersonic vehicle data link ［J］. Aero Weaponry， 2023， 30（4）： 26-32.）

［2］陳曉楠， 張廣林， 褚世永， 等. 美軍空中裝備體系作戰(zhàn)能力評估方法研究 ［J］. 指揮控制與仿真， 2023， 45（2）： 60-64. （Chen Xiaonan， Zhang Guanglin， Chu Shiyong， et al. Research on the eva-luation method of the combat capability of the U. S. air equipment system ［J］. Command Control amp; Simulation， 2023， 45（2）： 60-64.）

［3］洪潔， 張德海. 高動態(tài)飛行器自組織網(wǎng)絡(luò)組網(wǎng)研究 ［J］. 計算機工程與科學(xué)， 2019， 41（11）： 1930-1938. （Hong Jie， Zhang Dehai. A networking scheme for highly dynamic flying Ad hoc networks ［J］. Computer Engineering amp; Science， 2019， 41（11）： 1930-1938.）

［4］王書省， 李林琳， 李曉青， 等. 小型飛行器無線組網(wǎng)系統(tǒng)設(shè)計與實現(xiàn) ［J］. 測控技術(shù)， 2020， 39（11）： 133-140. （Wang Shusheng， Li Linlin， Li Xiaoqing， et al. Design and implementation of wireless networking communication system for small aircrafts ［J］. Measurement amp; Control Technology， 2020， 39（11）： 133-140.）

［5］Abdulhae O T， Mandeep J S， Islam M. Cluster-based routing protocols for flying Ad hoc networks （FANETs） ［J］. IEEE Access， 2022，2022（10）： 32981-33004.

［6］孟暉， 王海濤. Ad hoc網(wǎng)絡(luò)中典型分簇算法的性能分析 ［J］. 解放軍理工大學(xué)學(xué)報： 自然科學(xué)版， 2006（6）： 531-536. （Meng Hui， Wang Haitao. Performance analysis of typical algorithms in Ad hoc network ［J］. Journal of PLA University of Science and Technology： Natural Science， 2006（6）： 531-536.）

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

［8］Park J H， Choi S C， Hussen H R， et al. Analysis of dynamic cluster head selection for mission-oriented flying Ad hoc network ［C］// Proc of the 9th International Conference on Ubiquitous and Future Networks. Piscataway， NJ： IEEE Press， 2017： 21-23.

［9］Khayat G， Mavromoustakis C X， Pitsillides A， et al. Multiple redundant K-means clustered scheme based on weighted cluster head selection for damaged S-UAV ［C］// Proc of IEEE Global Communications Conference. Piscataway， NJ： IEEE Press， 2023： 6177-6182.

［10］孟洛明， 江彥馥， 劉彥君， 等. 基于相對移動性預(yù)測的k跳Ad Hoc網(wǎng)絡(luò)分簇算法 ［J］. 電子與信息學(xué)報， 2018， 40（12）： 2954-2961. （Meng Luoming， Jiang Yanfu， Liu Yanjun， et al. Relative mobility prediction based k-hop clustering algorithm in Ad hoc networks ［J］. Journal of Electronics amp; Information Technology， 2018， 40（12）： 2954-2961.）

［11］代家銘， 宋玉龍， 尚亞黎， 等. 高動態(tài)環(huán)境下航空自組網(wǎng)分簇算法設(shè)計 ［J］. 計算機應(yīng)用研究， 2015， 32（4）： 1193-1198. （Dai Jiaming， 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.）

［12］梅家棟， 南建國. 無人機自組網(wǎng)基于加權(quán)的穩(wěn)定分簇算法 ［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.）

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

［14］郭建， 任智， 邱金， 等. 無人機自組網(wǎng)快速穩(wěn)定加權(quán)分簇算法 ［J］. 計算機應(yīng)用研究， 2024， 41（1）： 248-253. （Guo Jian， Ren Zhi， Qiu Jin， et al. Fast and stable weighted clustering algorithm for unmanned aerial vehicle Ad hoc network ［J］. Application Research of Computers， 2024， 41（1）： 248-253.）