無人機集群網絡分簇優化算法

張 然，高瑩雪，丁元明

(1.大連大學 信息工程學院，遼寧 大連 116622； 2.大連大學 通信與網絡重點實驗室，遼寧 大連 116622)

0 引 言

無人機集群是指多個無人機為了達成同一個任務目標而形成的一個整體，進而組成通信網絡，能夠沖破單個無人機在技術和功能上的局限性，并通過組織多種功能不同、性能各異的無人機聯合合作，最大程度地發揮作戰效能[1]。然而，無人機節點移動速度高，導致網絡拓撲結構頻繁變化，這使得無人機集群網絡管理復雜。優化無人機網絡最有效的方法就是將網絡劃分為多個簇結構，并選擇適當的節點成為簇首。因此，需要對無人機集群網絡的分簇算法進行優化，以適應復雜的作戰環境，使網絡結構更加穩定。

經典的分簇算法有最小ID號分簇算法(low ID clustering algorithm，LID)[2]、最高節點度分簇算法(highest node degree clustering algorithm，HD)[3]、最低移動性分簇算法(lowest mobility clustering algorithm，LM)[4]、加權分簇算法(weighted clustering algorithm，WCA)[5]等。前3種分簇算法都沒有考慮影響網絡性能的因素，而加權分簇算法能夠綜合考慮不同影響因素，更好地適應不同的應用需求，因此，國內外眾多學者對加權分簇算法進行改進，以適用于不同的應用場景。

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

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

1 無人機集群網絡模型

無人機集群通信方式為移動自組織網絡，即移動Ad Hoc網絡，可以是平面式、分級式[13]，其體系結構如圖1所示。

圖1 移動自組織網絡結構

在平面式結構中，網絡中的所有節點地位相等，處于相同等級。平面式的網絡結構相對簡單，因為節點可以互相取代，不會因為某一節點失效使網絡無法正常運行，所以不需要進行簇首的選舉，也不需要進行簇維護。

在分級式結構中，網絡被劃分成多個獨立的簇結構，進行分簇管理。分簇是指將整個網絡劃分為幾個小的、可自我管理的簇結構[14]。分簇結構規模不受限，有良好的可擴充性，這使得網絡路由開銷減少[15]。每個簇結構都由一個簇首和多個成員節點構成。其中，簇首需要對簇內進行統籌和規劃，掌握簇內的成員節點的狀態和信息、分配信道資源以及簇間通信等；成員節點負責執行簇首的控制指令，向簇首匯報狀態和信息。

由于無人機集群網絡節點數量較多、節點移動性強，平面式結構會存在處理能力弱、網絡控制開銷大、網絡生命周期短等缺點，對網絡整體管理和控制的難度大，因此分級式結構更適用于無人機集群網絡。基于分級式結構，本文設計一種適用于無人機集群網絡的分簇算法，將網絡分成多個簇結構，并選取合適的簇首，以便進行網絡管理。

2 基于改進灰狼算法的分簇優化

基于灰狼算法的無人機集群網絡分簇包括簇的形成、簇首的選舉、簇的維護3個階段。在簇的形成階段，根據速度相似度和距離相似度對網絡中的所有節點進行分簇；在簇首的選舉階段，綜合考慮剩余能量、最高節點度、通信情況、任務種類，基于灰狼算法選舉簇首；在簇的維護階段，依據網絡拓撲結構變化頻率，采用周期性維護機制對簇進行維護。

2.1 簇的形成

本文依據節點的速度和距離相似度對無人機集群網絡的節點分簇，即將一定距離范圍內相對靜止的無人機節點分成一個簇。同時，要保證簇結構數目適中，平衡每個簇中成員節點的個數。當一個網絡的簇結構過少時，簇首負擔過大，導致其存活時間過短，網絡生命周期短；簇結構過多時，簇間通信頻繁，會導致網絡通信開銷和端到端延遲的增大。因此，在依據速度和距離相似度初步分簇完成后，需檢測每個簇中節點個數，并設置每個簇中的最大允許節點個數為nmax，以保證分簇的平衡度。

2.1.1 節點的速度相似度

由于無人機節點移動速度高，單個無人機運動航線不是事先預定的，飛行方案會在飛行中更改。因此，本文將從節點移動速度的大小和方向兩個方面綜合考慮，采用標準差的方式來計算節點速度相似度。標準差用來衡量簇內節點速度的離散程度，標準差越小，簇內節點速度越接近平均值，即這些節點的速度相似度越高；標準差越大，簇內節點速度和平均速度差異越大，即這些節點的速度相似度越低。速度相似度計算如圖2所示。

圖2 節點i與節點j的速度差

設節點i是節點j在下一跳通信范圍內的任意節點，將節點速度的大小和運動方向在三維坐標系中計算，則節點i與節點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為節點j在x、y、z軸上的速度；Vix、Viy、Viz為節點i在x、y、z軸上的速度；αj、αi分別為節點j、i與x軸的夾角；βj、βi分別為節點j、i與y軸的夾角；γj、γi分別為節點j、i與z軸的夾角。

則節點j與N個鄰居節點i在x軸、y軸、z軸上的平均速度差為

(4)

(5)

(6)

節點j與鄰居節點i在x軸、y軸、z軸上的速度差的標準差為

(7)

(8)

(9)

由勾股定理可知，節點j與鄰居節點i的速度差的標準差如下所示

(10)

(11)

設定速度差的標準差閾值為q，當速度差的標準差δjv小于速度閾值q時，節點j與其鄰居節點i在運動速度大小和運動方向上都具有相似性，即具有速度相似度。

如果以10個無人機節點為例，假設每個節點具有不同的初始速度，則基于速度相似度的分簇結果如圖3所示。

圖3 速度相似度分簇結果

2.1.2 節點的距離相似度

現有的計算節點間距離的方法基本都需要額外增加輔助設備，如GPS等。但對于無人機集群來說，不僅增加了成本而且還加大了網絡能耗。因此，本文通過節點接收和發送的功率，依據損耗衰減空間的近似信號傳播公式來計算節點間距離差。

設節點i為節點j在下一跳通信范圍內的任意節點，則節點j與鄰居節點i的距離差為

(12)

其中，Pt為節點發射功率；Gt為發射天線增益；ht為發射天線高度；hr為接收天線高度；Pr為節點接收功率。

則節點j與N個鄰居節點i的平均距離差的標準差為

(13)

(14)

設定距離差的標準差閾值為p，當距離差的標準差δjd小于距離閾值p時，節點j與其鄰居節點i具有相似性，即具有距離相似度。

對于圖3中的10個節點，基于距離相似度的分簇結果如圖4所示。

圖4 距離相似度分簇結果

2.1.3 節點的綜合相似度

當節點速度差的標準差和距離差的標準差都小于速度閾值q和距離閾值p時，則認為節點j與其鄰居節點i同時具有速度相似度和距離相似度，即節點j與其鄰居節點i符合成簇條件。該成簇條件具有傳遞性，即節點j與節點i符合成簇條件，節點j與節點k符合成簇條件，那么節點i與節點k也符合成簇條件，即節點j、節點i、節點k成為一個簇。

無人機集群網絡根據速度和距離相似度對網絡分簇，其具體步驟如下：

步驟1 判斷速度標準差是否大于速度閾值q；

步驟2 當速度標準差大于速度閾值q時，舍棄與節點j速度差最大的鄰居節點i，并執行步驟1；否則執行步驟3；

步驟3 判斷距離標準差是否大于距離閾值p；

步驟4 當距離標準差大于距離閾值p時，舍棄與節點j距離差最大的鄰居節點i，并執行步驟3；否則執行步驟5；

步驟5 判斷小于速度閾值的節點和小于距離閾值的節點是否為相同節點；

步驟6 當符合兩個條件的節點為相同節點時，執行步驟7；

步驟7 節點個數檢測，判斷每個簇中成員節點數是否小于等于最大允許節點個數nmax；

步驟8 當每個簇中成員節點數大于nmax時，舍棄與節點j速度差和距離差之和最大節點，并執行步驟7；

步驟9 當每個簇中成員節點數都小于等于nmax時，完成分簇。

按上述步驟，對于圖3中的10個節點，綜合速度相似度和距離相似度的分簇結果如圖5所示。

圖5 綜合相似度分簇結果

2.2 簇首的選舉

對所有網絡節點進行分簇后，本文綜合考慮節點剩余能量、最高節點度、通信情況、任務種類4個影響因素的聯合度量指標，并采用改進灰狼算法選取簇首。

2.2.1 聯合度量指標的計算

(1)剩余能量

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

(15)

(2)節點度

節點度是指節點在通信范圍內鄰居節點的個數。同一個網絡中，節點度越高，簇首數量越少，網絡時延越少。對節點度歸一化處理即鄰居節點數Ni除以簇內總節點數Ns，歸一化后的節點度Nτ為

(16)

(3)通信情況

節點通信成功的概率fs(i)取決于M次獨立重復實驗中通信成功的次數y和通信失敗的次數n，則節點通信成功的概率fs(i)為

(17)

其中，通信成功是在一個周期內收到了鄰居節點的HELLO消息；通信失敗是一個周期內，沒有收到鄰居節點的報文或收到鏈路斷裂的錯誤信息。

(4)任務種類

軍事戰爭中，由于無人機執行的作戰任務不同，其性能也各不相同。執行探測任務的無人機主要任務是搜集戰場情報、觀察作戰區域，增強顯示和預警能力；執行偵察任務的主要任務是深入到地方防御縱深進行監視、目標指示和損傷評估等；執行救援任務的無人機是在其它無人機失效時代替其繼續執行作戰任務；執行打擊任務的無人機則需攜帶攻擊武器，對目標進行精準打擊。因此，需要考慮無人機執行任務種類對簇首選舉的影響，依據無人機任務種類的危險程度，設置節點簇首選舉的優先級權Tτ，見表1。

表1 任務種類與優先級權值

由上述過程得到了節點i的剩余能量、鄰居節點數、通信情況和任務種類，對4種影響因素進行加權求和。根據加權分簇算法綜合考慮這4個因素得到的復合權值如下

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

(18)

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

2.2.2 改進灰狼優化算法

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

(19)

(20)

(21)

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

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

(22)

(23)

(24)

其中，M1、M2、M3分別為改進灰狼算法中α狼、β狼、γ狼對獵物位置的權重影響因子，即α狼、β狼、γ狼對獵物位置的學習率。

根據改進灰狼優化算法計算獵物位置如下

(25)

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

(26)

本文采用灰狼算法對無人機網絡的簇首選舉進行優化，將狼群看作無人機集群網絡，灰狼看作無人機集群網絡中的節點，獵物看作每個簇的簇首。在每一個簇中，選擇M值最大的3個節點，分別作為M1、M2、M3，根據式(26)計算出簇內所求的獵物，即為簇首。

2.3 簇的維護

由于無人機集群網絡拓撲結構變化的快速、復雜，所選擇的簇頭可能在一段時間后飛離原簇，或耗盡能量，或通信中斷，所以對簇的維護有著至關重要的作用。

簇的維護方式主要有離散時間機制和周期性維護機制。離散時間機制是一次選定簇首后，基本不再更換簇首，并不適用于無人機集群網絡。因此，在對無人機集群網絡簇結構進行維護時采用周期性維護機制，確保在一個簇首選舉周期內，由聯合度量指標最高的節點擔任簇首。除此之外，簇首選舉周期根據無人機集群網絡拓撲變化程度而定，當無人機集群網絡拓撲變化較慢時，則將選舉周期適當延長，避免頻繁重新選舉簇首產生大量開銷；當無人機集群網絡拓撲變化較快時，則適當縮短簇首選舉時間，避免因簇首失效造成簇結構與整個網絡脫離。

2.4 算法的實現流程

本文所提出的無人機集群網絡分簇優化算法首先考慮節點速度相似度和距離相似度對所有節點分簇，然后綜合考慮簇內節點的剩余能量、最高節點度、通信情況和任務種類的影響因素，采用灰狼優化算法進行簇首位置更新，選舉最佳簇首。該分簇優化算法具體實現步驟如下，其流程如圖6所示。

圖6 算法流程

步驟1 網絡初始化，定義無人機集群網絡中總節點個數為N；

步驟2 考慮節點的速度相似度和距離相似度對網絡中的節點進行分簇；

步驟3 判斷簇內成員數量是否大于最大閾值nmax；

步驟4 當所有簇內成員個數都小于最大閾值時，初步完成分簇；

步驟5 判斷簇內各節點剩余能量Eres是否大于簇內平均能量Eavg；

步驟6 當節點能量小于平均能量Eavg，該節點退出競選簇首；

步驟7 綜合考慮節點剩余能量、最高節點度、通信情況、任務種類4個影響因素的聯合度量指標，基于改進灰狼優化算法，選擇最佳簇首。

3 實驗仿真與結果分析

本節仿真驗證所提出的GWCOA算法性能，其具體參數設置見表2。本實驗與LID、HD、WCA、IWCA這4種分簇算法進行對比分析，通過簇首數目、簇依附關系變化次數、分簇的平衡度、統治集更新次數和節點生存個數5個性能指標驗證GWCOA算法的有效性。

表2 仿真參數

圖7 節點傳輸距離對簇首數目的影響

圖8為節點傳輸距離和簇依附關系變化次數的關系。簇結構越穩定，簇依附關系變化次數越少。由圖8可知，5種分簇算法的簇依附關系變化都隨著節點傳輸距離的先增加后減少。當傳輸距離較小時，節點脫離簇的概率較小，并隨著節點傳輸距離的增大而增加。因為此時網絡中簇結構多，每個簇的成員節點少，但隨著傳輸距離的增加，簇結構減少，每個簇的成員節點多，節點脫離簇的概率隨著傳輸距離的增大逐漸減少。由于GWCOA算法在選舉簇首時采用改進灰狼優化算法，保證簇首分布均勻，其簇依附關系變化次數相比于其它4種分簇算法的更小，網絡結構更穩定。

圖8 節點傳輸距離對簇依附關系變化次數的影響

圖9為節點傳輸距離和分簇平衡度的關系。分簇平衡度是指每個簇的節點個數基本相等，使得網絡中簇分布相對均勻。本實驗分簇算法平衡度采用標準差的方式來衡量，即每個簇所包含節點數的標準差，其值越小分簇算法越優越。由圖9可知，5種算法的分簇平衡度都隨著節點傳輸距離的增加而增加。隨著節點傳輸距離的增大，簇結構減少，每個簇中的平均節點數會增加，從而導致每個簇所包含節點數的標準差增大，即平衡度增大。由于GWCOA算法在初步分簇后進行節點個數檢測，使得每個簇內的節點數大致相同，簇分布相對均勻，其分簇平衡度明顯優于其它分簇算法。

圖9 節點傳輸距離對分簇平衡度的影響

圖10為仿真時間和統治集更新次數的關系。統治集更新次數為單位時間內簇首更新次數，統治集更新次數越多，簇結構越不穩定，分簇算法在分簇過程中越會產生龐大的計算量和通信開銷。由圖10可知，5種算法的統治集更新次數都隨著仿真時間的增加而增加。由于GWCOA算法先對網絡分簇，再進行簇首的選舉，當成員節點失效時，不需要重新分簇、選舉簇首，減少了統治集更新次數，因此，其統治集更新次數明顯低于其它3種分簇算法，提高了整個網絡的穩定性，降低了計算量，減少了網絡開銷。

圖10 仿真時間和統治集更新次數的關系

圖11為仿真輪數和生存節點個數的變化關系。對于一個網絡來說，隨著仿真輪數的增加，生存節點個數越多，網絡生命周期越長。由圖11可知，5種算法生存節點個數都隨仿真輪數增加而減少。WCA、IWCA、GWCOA由于考慮了節點的剩余能量，因此經過相同輪數這3種算法的節點生存個數明顯多于其它兩種算法，但在IWCA算法中節點剩余能量權重設置比較大且隨鄰居節點數變化，因此IWCA算法優于WCA算法。由于GWCOA算法不僅考慮了節點的剩余能量，還采用了計算量小的灰狼優化算法選舉簇首，而且采用周期性維護機制對簇進行維護，因此，GWCOA算法最優，其網絡生命周期最長。

圖11 仿真輪數和生存節點個數的關系

4 結束語

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