自適應ANP-CRITIC的無人機集群網絡優化算法*

黨元章，華 翔，張金金，石成瀧，蔣天啟

(1.西安工業大學 電子信息工程學院,西安 710021;西安工業大學 兵器科學與技術學院,西安 710021;3.西安工業大學 機電工程學院,西安 710021)

隨著通信及其相關技術快速發展,相比于單個無人機,無人機集群在態勢感知、臨場決策和干擾對抗等方面有質的提升[1-4]。而無人機集群以編隊形式執行任務是當前研究的熱點[5],由于無人機集群在編隊飛行過程中節點隨機失效和任務場景復雜多變,導致網絡拓撲結構頻繁變化,網絡管理變得尤為困難,而分簇是優化網絡管理的有效手段。無人機集群網絡采用分簇結構有許多優點,諸如減少路由開銷、避免簇內沖突、便于網絡管理以及延長網絡壽命等[6-8]。

目前針對不同的應用環境和組網要求已存在許多類型的分簇算法,包括最小ID分簇算法(Low ID Clustering Algorithm,LID)[9]、最高連通度分簇算法[10]和加權分簇算法(Weighted Clustering Algorithm,WCA)[11],前兩種算法的不足在于簇首選取判定依據的參數單一,基于最小ID和節點最大連通度為依據導致簇首選取缺乏準確性;而加權分簇算法則加入了多方面的因素指標,具有很強的可塑性。因此,許多學者在加權分簇算法的基礎上進行改進,提出新的算法。文獻[12]提出了一種智能的多參數無人機集群組網算法,該算法首先將節點位置信息和剩余能量作為適應度函數來選取簇首,接著提出簇首重選機制,以實現穩定的集群維護和拓撲管理。文獻[13]提出了一種基于改進灰狼算法的分簇算法,首先通過節點相對移動性和距離進行簇范圍劃分,接著選取簇內節點的剩余能量、節點度、通信情況、任務種類等多個參數指標選取簇首,實現了簇首位置的均勻分布。文獻[14]提出的一種基于權值優化的分簇算法,該算法綜合考量節點度、節點通信距離、剩余能量和節點移動性等指標,并動態調整簇的規模。文獻[15]提出了一種基于層次分析法(Analytic Hierarchy Process,AHP)-熵權的分簇算法,通過運用AHP與熵權法計算各因素指標的主客觀權重,接著綜合分析并計算組合權重,提高了權重的可靠性。由此可見,分簇算法在集群組網領域應用已久,簇首選取對于分簇網絡的性能至關重要。上述研究在簇首選取過程中仍存在指標權重適應性差、分簇規模差異性大等問題。

因此,文中提出一種基于自適應ANP-CRITIC的無人機集群網絡優化算法(Adaptive ANP-CRITIC Weighted Clustering Algorithm,AAC-WCA),擬加入節點負載失衡度指標均衡成簇規模,結合五個關鍵因素指標,設置安全閾值區間并采用Z-Score法對指標數據進行標準化以提高簇首選取客觀性;針對編隊飛行場景與執行任務種類設計ANP法對各因素指標主觀權重進行預求解,無人機集群在編隊飛行過程中采用CRITIC法對各指標客觀權重實時求解;引入博弈論將實現納什均衡作為協調主客觀權重的優化目標,獲得自適應簇首權值;根據簇首權值選取最優簇首。以期提高簇首選取自適應性,均衡分簇規模,增強整個網絡的性能的同時也延長無人機集群網絡壽命。

1 場景和指標分析

1.1 應用場景

無人機集群在組成編隊執行任務過程中會受到各種各樣外界因素的干擾,影響一個無人機節點能否可以成為簇首的影響因素有很多,針對不同的應用場景,因素指標的重要程度也不同[16]。

文中的應用場景為無人機集群編隊飛行穿過某區域執行偵查探測任務,從出發點穿過任務區的飛行過程中存在已探查的威脅干擾以及可能遭受的不確定因素干擾,出發前需要對集群網絡進行分簇以優化網絡管理,在飛行過程中需要根據實際的飛行狀況對網絡進行調整,確保集群始終保持著良好的飛行狀態。無人機集群在飛行過程以編隊形式自主飛行,編隊內無人機節點模型應保持移動特性和群體的飛行態勢,簇結構在高速移動狀態下相對動態平衡。在充分考慮編隊網絡拓撲變化對分簇結構的影響后,文中擬選取節點連通度、節點負載失衡度[17]、節點平均通信距離、節點剩余能量和節點相對移動性作為影響無人機集群網絡分簇的性能指標。

1.2 因素指標

1.2.1 因素指標計算

節點連通度指標。節點連通度是指節點與網絡中所有其它節點建立一跳與兩跳通信鏈路數的和。連通度表示分簇網絡中節點建立通信連接的能力,當編隊網絡中節點總個數為n,鄰接矩陣的冪次為v,節點i與節點j一跳路徑條數表示為Nij,則節點i的連通度Ci表示為

(1)

節點負載失衡度指標。節點負載失衡度是指本節點的連通度與網絡中其它節點的連通度的均值之差。該指標可以將分簇規?？刂圃谳^優范圍,節點負載失衡度Li表示為

(2)

節點平均通信距離指標。節點平均通信距離是指節點與所有可以建立一跳通信鏈路鄰居節點的通信距離之和的平均值。該指標與分簇網絡中節點間的通信能耗和網絡開銷密切相關,當與節點i可建立通信連接的鄰居節點總數為t,節點i與第j個鄰居節點的通信距離為dij,則節點i的平均通信距離Di表示為

(3)

節點剩余能量指標。節點剩余能量是衡量節點是否能充當簇首的重要指標。節點剩余能量與分簇網絡生存壽命密切相關,節點i的剩余能量Ei表示為

Ei=Eires,

(4)

節點相對移動性指標。節點相對移動性指節點與鄰居節點在連續兩次數據傳輸時通信距離的差異。編隊形式自主飛行過程中節點間相對移動,移動性越小分簇結構就越穩定,當節點i的與鄰居節點j的相對移動性為mij,則通信范圍內有k個鄰居節點數據交互的節點i的相對移動性Mi表示為

(5)

1.2.2 因素指標標準化

文中根據具體任務場景,定義各因素指標的閾值區間[ymin,ymax],當節點指標數據值不在閾值區間內,則該節點退出簇首的競選,節點的各項指標值滿足ymin<|yi|≤ymax條件。

綜合考慮以上各因素指標的計算維度差異,文中采用Z-Score法對指標數據進標準化,使得各指標數據應對外界干擾時魯棒性更強,可以更好的適用于網絡中存在異常節點或孤立節點的情況。

假設所有節點的某一項因素指標數據組成一個序列為x1,x2,…,xn,對其進行變換得

(6)

2 基于自適應ANP-CRITIC的無人機集群網絡優化

2.1 主觀權重計算

網絡層次分析法(Analytic Network Process,ANP)是一種適應非獨立的遞階層次結構的決策方法,可以反映因素指標間相互依賴性和反饋關系的過程,并準確的對復雜網絡系統進行評價,計算的主觀權重更符合實際場景。執行本次任務之前,根據無人機集群執行任務種類與已知的應用場景,用ANP法評估無人機集群網絡中各因素指標的重要程度,通過構造判別矩陣得出因素指標間的依賴與反饋關系,對各指標的主觀權重進行分析預求解。根據ANP法設計改進步驟如下:

① 將節點連通度Ci、節點負載失衡度Li、節點平均通信距離Di、節點剩余能量Ei和節點相對移動性Mi五個因素指標用集合T={Ci,Li,Di,Ei,Mi}來表示。根據Satty給出的重要性定量對因素指標進行縮放,其中Scale=1表示比較對象同等重要,Scale=9表示比較對象極端重要,反之用倒數表示,見表1。

表1 Satty標度

② 將各個因素指標間的依賴反饋關系轉換為從1到9的定量尺度范圍。根據已知飛行場景信息分別將第i行和第j列對應的因素指標進行比較賦值來創建判別矩陣。判別矩陣A表示為

(7)

對判別矩陣進行歸一化處理,求出每個元素占相對應列總和的比例。相應位置元素bij為

(8)

歸一化矩陣B為

(9)

相對重要性是通過比較矩陣的特征值和特征向量計算的。元素的權重是在元素規范化時獲得的。

③ 對歸一化矩陣的每一行進行求和,求得均值獲得特征向量矩陣EV表示為

EV=(EV1,EV2,…,EVn)-1。

(10)

為了驗證所得判別矩陣的可靠性,引入一致性指標進行評估,包括一致性度量CM、一致性指數CI和一致性比率CR。一致性度量CM表示為

(11)

一致性指數CI表示為

(12)

ANP法中的九階平均隨機一致性系數RI對應表見表2。

表2 九階平均隨機一致性系數

一致性比率CR為

(13)

當CR≤0.1時說明權重評估準確,否則需要對矩陣中的參數進行調整。

④ 重復上述步驟,計算出所有因素指標的特征向量矩陣EV,并確保判別矩陣的一致性比率小于0.1。并將所有特征向量矩陣構造為未加權超矩陣,進行加權處理獲得極限超矩陣[18]。得到各因素指標的主觀權重向量w1j=(w11,w12,w13,w14,w15)。

本節通過特定場景下無人機集群各因素指標的重要度差異來分析計算得到因素指標的主觀權重,表明了各因素指標之間、因素指標與備選節點之間都存在依賴或反饋關系。ANP法的總體結構關系如圖1所示。

圖1 簇首節點選擇ANP結構關系圖

2.2 客觀權重計算

CRITIC法是一種基于指標數據相關性和指標信息變異程度的客觀賦權法,該方法會綜合考慮了指標所含信息量的大小、指標數據的波動性與相關關系對權重結果的影響以及對比強度與各指標間的沖突性。

計算指標間對比強度為

(14)

求解相關系數和沖突性量化指標值,第i項指標與第j項指標間的相關系數rij為

(15)

式中:Cov(i,j)為因素指標i與j之間的協方差,Var[i],Var[j]為因素指標i與j的方差。第j個因素指標沖突量化指標值Rj為

(16)

計算指標信息量和歸一化權重,各指標的客觀權重是根據對比強度和沖突性來綜合衡量的。若Cj表示第j個因素指標所包含的信息量,則第j個指標的信息量Cj可以表示為

(17)

式中:Vj為第j個指標與其它指標間的標準差,Cj越大表示第j個指標所包含的信息量越大,即指標的相對重要程度越高,權重也越大。第j個指標的客觀權重w2j為

(18)

客觀權重不需要考慮無人機節點在特定環境下的主觀影響,網絡中的所有節點都使用統一標準去計算客觀權重,各因素指標客觀權重向量為

w2j=(w21,w22,w23,w24,w25)。

2.3 自適應ANP-CRITIC權重計算

ANP法和CRITIC法在求解過程中都充分考慮了指標間的關聯性和影響程度,可以有效提升簇首選取過程中權值評估準確度。文中引入博弈論的思想修正主客觀權重,優化權重組合系數,將實現納什均衡[19]作為協調主客觀權重的優化目標,在各項權重之間盡可能的尋找某個均衡點,使得最終修正的組合權重與基礎權重間偏差最小,以獲得最優綜合權重。具體步驟如下:

① 設采用D種方法確定了m個指標因素的權重,則得到基礎組合權重為Wnj={w1j,w2j,…,wnj},(n=1,2,…D) ,式中wnj表示在第n種方法中第j項指標的權重,文中D=2。設線性組合系數向量δ={δ1,δ2},則綜合權重向量W的線性組合表示為

(19)

② 按照博弈論聚合模型原理,以W與Wnj之間的最小化偏差為目標得到最佳權重。目標函數Z為

(20)

根據矩陣的微分性質,確保目標函數Z最小時其最佳一階導數條件方程為

(21)

③ 對上式中獲得優化的線性組合系數δ={δ1,δ2}歸一化處理為

(22)

計算綜合權重向量W為

(23)

④ 將計算得到的各因素指標綜合權重帶入如下權重公式得到第i個節點簇首權值為

weight(i)=W1·Ci+W2·Li+W3·Di+W4·Ei+W5·Mi,

(24)

從式(24)得到每個備選節點的簇首權值,從而選出最優的簇首。本章簇首權值計算過程的偽代碼為

輸入:

網絡拓撲信息

網絡中n個節點自身信息

閾值參數[ymin,ymax]

ANP方法與CRITIC方法參數

輸出:

節點簇首權值

Begin

網絡拓撲與節點狀態初始化

For節點i=1到ndo:

計算節點i連通度指標Ci

計算節點i負載失衡度指標Li

計算節點i平均通信距離指標Di

計算節點i剩余能量指標Ei

計算節點i相對移動性指標Mi

約束和標準化各項指標值yi

End for

While (網絡中節點的綜合簇首權值未全被計算) do:

基于ANP法計算主觀權重w1j

基于CRITIC法計算客觀權重w2j

基于博弈論方法計算自適應綜合權重Wj

計算節點i的綜合簇首權值weight(i)

End while

Return網絡中所有節點簇首權值weight(i)

End

2.4 網絡分簇

在編隊網絡分簇過程中,網絡進行初始化,鄰居節點交互信息,根據飛行過程中的節點各因素指標數據和自適應ANP-CRITIC權重求得簇首權值,根據權值選出簇首,節點優先選擇通信距離更近的簇首并加入該簇[20]。其中網絡中節點負載失衡度指標可以有效均衡分簇規模,算法初始化階段可能需要進行多次迭代,無人機集群網絡初始化與分簇結果示意如圖2所示。

圖2 網絡初始化與分簇示意圖

3 仿真與分析

文中采用MATLAB仿真軟件環境中對AAC-WCA算法的性能進行仿真驗證。并與最小標識分簇算法LID、加權分簇算法WCA和改進的加權分簇算法(Improved Weighted Clustering Algorithm,IWCA)[21]對比文中算法的性能差異。通過隨機成簇規?？刂?、簇內平均通信距離、網絡生存壽命、節點間通信質量、節點平均重入簇次數5個網絡性能指標驗證AAC-WCA算法的有效性。無人機集群采用編隊形式自主飛行,在1 000 m2區域范圍內起飛100架無人機節點,節點運動模型為RWP(Random Waypoint Model)[22],且各節點初始能量相同,簇首權值計算過程中各指標權重之和為1,具體仿真實驗參數見表3,為了降低實驗隨機性干擾導致的實驗誤差,最終結果為10次仿真實驗均值。

表3 仿真參數

如圖3仿真結果表明,4種算法的簇首數目都隨著節點通信距離的增加而減少,最佳簇首數目σ=10,由于文中AAC-WCA算法引入節點負載失衡度指標對簇首數目有限制作用,自適應選取簇首使得整個網絡結構的簇首數目變化趨勢更加平穩,隨著節點通信距離的增加,整體簇首數目更加接近最優值,工作能耗更小;文中綜合了多種指標因素,并求得自適應權重,最優簇首的選取可以使得每一輪網絡能量消耗降到最小,極大的減少網絡維護的次數。

圖3 簇首數目隨節點傳輸距離的變化

如圖4仿真結果所示,表明了簇內平均通信距離隨節點傳輸距離的關系。在相同節點通信距離的前提下,簇內平均通信距離越小,簇首的能量消耗就越少,從而簇維護次數也越小,它也能反應網絡中簇分布的相對均衡程度。由圖得4種算法的簇內平均通信距離都隨著節點通信距離增加而增加,由于文中AAC-WCA算法的簇首選取時考慮了節點通信距離指標,并定義閾值對簇首與簇成員節點間的距離進行限制,將簇內平均通信距離控制在合理范圍內,盡可能的達到簇分布最優與降低簇首能量損耗。相比于其它3種算法,文中算法中無人機集群分簇網絡的簇分布與簇首能量下降速度得到了明顯的優化。

圖4 簇內平均通信距離隨節點傳輸距離的變化

圖5表示在特定實驗環境下,LID、WCA、IWCA以及ACC-WCA的節點存活數量隨運行輪次變化的情況。仿真可以看出,在整個過程中,四種算法網絡中出現第一個節點失效對應運行輪次分別大約在1 015輪、1 294輪、1 628輪、1 834輪;網絡中節點失效比例為20%時,四種算法對應運行輪次分別在大約1 612輪、2 271輪、2 886輪、3 379輪;網絡中節點失效比例為50%時,四種算法對應運行輪次分別在大約2 408輪、3 219輪、4 381輪、4 825輪。通過計算可得AAC-WCA分別在節點失效率為1%、20%、50%的情況下,節點平均運行輪數比WCA、LID、IWCA分別提高了約99.36%、47.97%和12.85%,可見AAC-WCA很大程度上均衡了節點能量損耗。同時,在約7 500輪其它3種算法的節點相繼全部死亡,而 AAC-WCA的節點在約8 600輪才全部死亡。由此表明,文中所提的AAC-WCA的網絡壽命最長。

圖5 節點存活數量與運行輪次的關系

圖6表示在特定實驗環境下,LID、WCA、IWCA以及ACC-WCA的簇首累計接收數據包數量隨運行輪次變化的情況?？梢钥闯?隨著運行輪次的增加,LID與WCA算法的簇首接收數據包數量增長更為平緩,分別在4 300輪與5 500輪左右停止增長,這表明此時網絡中節點都已經失效,簇首接收數據包數量分別為0.4×105個,0.85×105個左右;運行至大約7 500輪時,IWCA網絡簇首接收數據包數量不再增長,大約為1.6×105個;而文中的AAC-WCA網絡簇首接收的數據包在8 600輪時大約為2.1×105個,通過計算可得較WCA,LID,IWCA簇首累計接收數據包數量分別提高了約425%,147%和31%;可見文中所提的AAC-WCA算法大大提高了無人機集群編隊飛行時節點的通信質量。

圖6 簇首累計接收數據包數量與運行輪次的關系

圖7表示在特定實驗環境下,LID,WCA,IWCA以及ACC-WCA的節點平均重入簇次數隨運行輪次變化的情況。對比4種算法在未出現死亡節點時運行至1 000輪的情況,隨著運行輪次的增加,節點平均重入簇次數逐漸增加。節點平均重入簇次數是評估網絡分簇結構性能的重要指標,當無人機節點受到自身或外界因素影響時,部分節點會脫離原來的簇并重新加入其他簇,平均重入簇次數越少,表明分簇網絡管理的效果更好。由圖可見文中算法相比于其它3種算法的平均重入簇次數更少,分簇網絡的穩定性更強,可以實現對網絡的更優管理。

圖7 節點平均重入簇次數與運行輪次的關系

綜上所述,文中提出的AAC-WCA算法相較于其它3種算法對比,使無人機集群在編隊飛行過程中的主要性能參數如網絡分簇規模、簇內通信距離、網絡整體壽命、節點通信質量以及分簇網絡穩定性得到了明顯的優化。

4 結 論

1) 文中針對無人機集群編隊飛行過程中網絡管理問題,提出了一種基于自適應ANP-CRITIC的無人機集群網絡優化算法。引入節點負載失衡度指標來均衡成簇規模,增加安全閾值以及采用Z-Score法對指標數據進標準化,提高簇首選取客觀性;根據不同的實際應用場景與任務種類,設計ANP-CRITIC自適應機制,通過ANP法預先求解因素指標主觀權重,在編隊飛行過程中根據CRITIC法求解客觀權重;引入博弈論的思想,將實現納什均衡作為協調主客觀權重的優化目標,獲得自適應綜合簇首權值;根據簇首權值選取簇首。

2) 通過仿真驗證,在特定的網絡仿真環境中,文中所提AAC-WCA算法與LID、WCA、IWCA算法相比,控制了成簇規模與簇內平均通信距離,降低了網絡通信過程中的能量損耗,延長了網絡壽命的同時提升了網絡的通信質量,從而實現對無人機集群網絡的更優管理。