基于自適應蜂鳥算法的飛行自組網拓撲優化

劉 琰 趙海濤 張 姣 龔廣偉 潘筱茜 陳海濤 魏急波

①(國防科技大學電子科學學院 長沙 410073)

②(中國人民解放軍31401部隊 哈爾濱 150090)

1 引言

無人機(Unmanned Aerial Vehicles,UAVs)集群能夠克服單無人機系統通信距離短、處理能力有限和承載能力低等局限性，是當前研究的熱點領域[1,2]。飛行自組網(Flying Ad hoc NETworks, FANET)能夠利用動態的拓撲結構保障無人機間的通信協同，是無人機集群通信問題的有效解決方案[3]。各無人機節點之間進行正常的信息傳輸是保證FANET系統可生存性與可操作性的重要條件，而由節點間鏈路構建的網絡拓撲成為關注的重點。無人機在飛行過程中存在多種不斷變化的因素，節點的高速移動造成地理位置和節點之間的距離不斷變化，不同的任務需求造成無人機數量、飛行路線不斷變化，受限頻譜競爭或者惡意干擾造成各節點的實際可用信道不斷變化。這些因素將導致節點之間的鏈路頻繁變化，網絡拓撲也將隨之發生變化，加重了FANET對網絡拓撲的管理難度。

分簇是優化網絡拓撲管理的有效手段之一，該結構將網絡劃分為相互連接的簇群，通常每個簇群由一個簇首及其若干簇成員組成[4]。文獻[5]提出了一種基于加權的分簇算法，考慮了剩余能量比、節點度、相對移動性和平均距離，但算法的分簇效果會隨著節點數量增加而降低，無法滿足大規模無人機集群的通信需求。文獻[6]使用了低復雜度的層次分析法和逼近理想點法對FANET進行分簇，但算法的參數矩陣將直接影響分簇結果，無法準確設置參數矩陣以適應不同的場景。文獻[7]利用K-means方法對節點進行分簇，但算法對K值的學習效率較低，不能快速給出最適合當前網絡狀態的分簇方案。值得注意的是，在實際應用場景中頻譜資源通常是多信道的，同一時間不同位置節點的可用信道可能存在差異，只有節點之間存在相同的可用信道時才有可能直接建立連接。上述算法雖然能夠從節點移動性的角度出發對FANET進行了分簇，但是僅通過傳輸范圍判斷兩個節點是否為一跳鄰居，沒有考慮節點之間是否存在相同的可用信道。

當無人機節點的數量較多時，對網絡進行分簇是一個復雜的優化問題，利用傳統方法直接求解過于復雜[8]。近年來，研究人員根據仿生學原理提出了群智能優化算法，并且已經用于解決FANET的分簇問題。文獻[9]采用飛蛾撲火優化算法進行網絡構建和節點部署。文獻[10]利用蝙蝠優化算法得到了負載均衡的分簇方案。文獻[11]設計了一種改進的粒子群優化算法，根據節點位置均勻地對無人機進行分簇。文獻[12]使用螢火蟲優化算法和磷蝦優化算法對網絡進行拓撲管理。目前基于群智能優化的分簇算法雖然在相應的模型上取得了不錯的效果，但是算法建立的模型都沒有考慮可用信道差異對分簇的影響，并且所使用的群智能優化算法在尋優結果和效率上還有待改善的空間。人工蜂鳥算法(A rtificial Humm ingbird A lgorithm,AHA)是最新提出的優化算法，相較于其他算法具有尋優精度高、收斂速度快、魯棒性強等特點[13]。本文在AHA算法的基礎上，提出了尋優性能更好的自適應蜂鳥算法(ADap tive Humm ingb ird A lgorithm,ADHA)。一個移動自主網絡需要解決節點移動導致的簇動態變化的問題，本文在考慮無人機移動性的基礎上，重點關注節點可用信道差異造成的影響，提出了一種基于自適應蜂鳥算法的FANET拓撲優化方法。

2 系統模型

2.1 通信場景

FANET網絡由無人機節點組成，網絡采用分簇結構進行拓撲的管理，利用分簇算法將FANET網絡劃分為不重疊的簇群，同一簇群內的節點使用一條對所有簇內節點皆可用的主用信道進行通信，具體通信場景如圖1所示。實際環境中節點的移動性、通信半徑、可用信道差異等因素都將影響分簇的過程。

圖1 通信場景示例

2.2 拓撲優化模型

2.2.1簇結構

節點集合為U={U1,U2,...,U N}，編號構成集合N={1,2,...,N}，N為節點數量。將整個頻域劃分為非重疊信道，所有信道表示為集合C={C1,C2,...,C M}，編號構成集合為M={1,2,...,M}，M為總信道數量。節點Ui的實際可用信道構成可用信道集CUi∈C。按照分簇算法得到一種拓撲優化策略A對網絡進行分簇，第K個簇群的所有節點構成集合CLk，簇首用C Hk表示。整個網絡中簇群總數量稱為簇數量，用K(A)表示。

2.2.2負載偏差

E k(A)表 示第K個簇群中簇成員的數量，稱為簇負載。負載偏差是簇負載的標準差，用S(A)表示，具體公式為

2.2.3簇移動度

假設無人機的移動僅由其任務決定，可以在任意方向上隨機移動。如圖2所示，在一個簇群中，簇首U i形成以R為通信半徑的通信范圍，簇成員U j可能接近或者遠離簇首。將簇首的通信范圍劃分為安全區和危險區，其中安全區是半徑為0.5R的圓形區域，而危險區是半徑0.5R與R之間的環形區域。

圖2 區域劃分

簇首與簇成員之間的相對移動方向表示為

簇首與簇成員之間的距離用dist(U i,U j)表示，則簇首與簇成員之間的移動度R D(U i,U j)可通過式(4)求得

在拓撲優化策略A下，簇群C Lk的簇移動度表示為

整個網絡的簇移動度表示為

2.2.4優化問題

本文解決的問題是：在分簇結構特征、可用信道差異、最大通信半徑等多種約束下，如何對FANET拓撲進行優化，使網絡的簇數量、負載偏差和簇移動度最小。優化問題的表達式為

其中，A={CHk,CLk,ξi,m}是一種拓撲優化策略，主要包括確定拓撲的簇首、簇成員和簇內主用信道等。式(8)保證每個節點必須加入簇群，式(9)保證每個節點只能加入一個簇群，式(10)和式(11)保證每個節點只能選擇1個可用信道進行簇內通信，式(12)保證一個簇內的所有節點使用1條公共可用信道作為主用信道。式(13)保證簇首與簇成員之間的距離小于最大通信半徑。

3 基于自適應蜂鳥算法的拓撲優化

3.1 人工蜂鳥算法(AHA)

人工蜂鳥優化算法AHA的靈感來自蜂鳥的采蜜行為，利用L只蜂鳥在D維搜索空間進行運動，尋找待優化問題(適應度函數)的最優解。在AHA算法中，每只蜂鳥個體的位置是其訪問的食物源，代表待優化問題的一個可行解，用X i=(x i,1,x i,2,...,x i,D)表示。食物源的花蜜補充率代表可行解對應的適應度值。AHA設計了蜂鳥的覓食方式有效更新蜂鳥位置X i，覓食方式包括引導覓食、區域覓食和遷移覓食。

引導覓食是指蜂鳥向著目標食物源方向進行覓食，區域覓食則是在當前食物源的鄰近區域覓食，兩種覓食方式找到的候選食物源分別表示為

當迭代次數t達到遷移系數M C時，蜂鳥通過遷移覓食找到的新食物源表示為

其中，L ow和U p分別表示D維問題的下邊界和上邊界，r是取值范圍在0～1的隨機向量。本文對AHA算法進行了簡要介紹，其詳細過程可以參考文獻[13]及相關文獻。

3.2 自適應蜂鳥算法(ADHA)

3.2.1覓食行為動態調整

3.2.2柯西高斯擾動變異

本文采取一種根據迭代次數自適應調節的柯西、高斯融合變異算子進行擾動，具體公式為

本文使用改進的sigm oid函數作為自適應調節因子A F(t)。具體公式為

3.3 針對拓撲優化問題的編碼映射

用ADHA算法來求解本文模型中的問題時，需要對蜂鳥個體進行有效的編碼，從而建立蜂鳥個體與優化策略的映射關系。假設算法中的蜂鳥種群由L只蜂鳥個體組成，其中每只蜂鳥個體代表一種優化策略，由向量Xi=(x i,1,x i,2,...,x i,D)表示。蜂鳥個體Xi的維度D與 節點總數M相等，每一維的元素x i,j代 表網絡中節點Uj的決策。元素xi,j的取值范圍為(0,2)，其中整數部分和小數部分表示不同的含義，融合了身份決策、信道決策和入簇決策。身份決策是指確定節點身份為簇首或簇成員，信道決策是指確定簇首的主用信道，入簇決策是指確定簇成員連接的簇首。

整數部分表示節點的身份，若整數部分為1，則節點身份是簇首，若整數部分為0，則節點身份是簇成員。小數部分表示信道決策和入簇決策，按照由整數部分確定的節點身份可以分為兩種情況。

若節點身份是簇首，則小數部分代表節點的簇內主用信道即信道決策，具體表達式為

其中，D Cj表 示信道決策即簇首節點Uj選擇的簇內主用信道，{x i,j}表示xi,j的小數部分，A VC(U j)表示節點U j的可用信道集，| AVC(U j)|表示可用信道數量，是向上取整函數。式(22)是一種序號生成算法，通過x i,j的小數部分和可用信道數量生成序號a。式(21)中I ndex(AVC(U j),a)表示選擇可用信道集A VC(U j)中的第a個信道。

若節點身份是簇成員，則小數部分代表入簇決策，具體表達式為

其中，DCHj表示節點需要連接的簇首，BCH(U j)表示節點U j的鄰居簇首集，| BCH(U j)|表示鄰居簇首數量。節點U j的鄰居簇首是指在節點通信范圍內的簇首，并且簇首的主用信道必須在節點的可用信道集之中，節點所有的鄰居簇首構成其鄰居簇首集。

圖3給出了8個節點的網絡進行編碼映射的具體過程，其中蜂鳥個體為一種可能的取值情況。第1,3,4,7維元素的整數部分是1，則相應節點的身份為簇首，其余元素相應節點的身份為簇成員。然后，簇首依據小數部分和可用信道情況做出信道決策。例如，簇首U4的可用信道集是{C2,C4,C5}，小數部分是0.95，利用式(22)的序號生成算法求得序號a=3，則根據式(21)選擇其可用信道集的第3個信道(C5)作為主用信道。最后，簇成員依據小數部分和鄰居簇首情況做出入簇決策。例如，簇成員U8的鄰居簇首集是{U1,U5,U7}，小數部分是0.48，利用式(24)的序號生成算法求得b=2，則根據式(23)選擇加入其鄰居簇首集的第2個簇首(U5)。

圖3 編碼映射示例

3.4 適應度函數的構造

每只蜂鳥個體Xi=(x i,1,x i,2,...,x i,D)能夠編碼映射為一種優化策略，結合2.2節的系統模型，蜂鳥個體X i對應的簇數量、負載偏差和簇移動度分別為K(X i),S(X i)和G(X i)。針對式(7)建立的優化目標，蜂鳥個體Xi的適應度函數設計為

3.5 拓撲優化具體流程

首先，獲取部署區域內的各無人機的位置、可用信道情況和移動速度等實際網絡情況。然后，根據實際網絡情況設置算法參數，如蜂鳥個體維度D、蜂鳥種群規模L、最大迭代次數Tmax等。將每只蜂鳥個體編碼映射為相應的拓撲優化策略，并且構建以最小化簇數量、負載偏差和簇移動性為目標的適應度函數。隨后，執行ADHA算法迭代求解使適應度值最小的最優蜂鳥個體。最后，按照最優蜂鳥個體代表的優化策略進行實際拓撲連接。拓撲優化流程如圖4所示。

圖4 拓撲優化流程圖

4 仿真實驗與結果分析

4.1 參數設置

節點隨機分布在50 km×50 km的矩形區域，從總信道中隨機選取部分信道作為各節點的可用信道，選擇應用最廣泛的隨機路點模型[14]模擬節點的移動。仿真場景的具體設置如表1所示。

表1 仿真參數設置

利用麻雀搜索算法(Sparrow Search A lgorithm,SSA)[15]、野馬優化算法(W ild Horse Optim ization,WHO)[16]、AHA[13]和ADHA共4種群智能優化算法進行對比。對比算法的基礎程序均從相應文獻作者處獲取，參數設置與相應文獻保持一致，具體參數設置如表2所示。

表2 算法參數設置

4.2 實驗結果與分析

4.2.1節點數量的影響

為了驗證節點數量變化對分簇結果的影響，設置總信道數量為10，最大通信半徑為15 km，節點數量在50～300變化，仿真結果如圖5所示。由圖5(a)、圖5(b)和圖5(d)可見，隨著節點數量不斷增加，各算法的適應度值、平均簇數量、平均簇移動度都會增加，這是因為在部署范圍固定不變的情況下，節點數量增加會導致節點密度增大。值得注意的是，ADHA算法取得的適應度值在不同節點數量下均是最低的。由圖5(c)可見，SSA, WHO和AHA算法的平均負載偏差隨著節點數量的增加不斷增大，而ADHA算法的簇負載偏差基本保持在1附近，說明ADHA算法的拓撲結構更加均勻。

4.2.2總信道數量的影響

為了驗證總信道數量變化對分簇結果的影響，設置最大通信半徑為15 km，節點數量為150，總信道數量在5～20變化，仿真結果如圖6所示。由圖6(a)和圖6(b)可見，隨著總信道數量不斷增加，各算法的適應度值、平均簇數量也相應增加。這是因為各節點的可用信道從總信道中隨機選取，總信道數量增加會使各節點可用信道差異增大。由圖6(c)和圖6(d)可見，ADHA算法的平均負載偏差和平均簇移動度明顯小于其他算法，說明算法得到的簇群更加均勻和穩定。整體來看，在不同總信道數量下，ADHA算法的各項優化結果仍是最好的。

圖6 總信道數量變化對算法分簇結果的影響

4.2.3通信半徑的影響

為了驗證最大通信半徑變化對分簇結果的影響，設置節點數量為150，總信道數量為15，最大通信半徑在5～15 km變化，仿真結果如圖7所示。由于ADHA算法求解拓撲優化問題的過程中能夠自適應調整尋優動作，其可以獲得最小的適應度值、平均數量、平均負載偏差和平均簇移動度。

圖7 最大通信半徑變化對算法分簇結果的影響

5 結論

本文研究了FANET網絡中的拓撲優化問題，重點考慮節點移動性和可用信道差異的影響，提出了一種基于自適應蜂鳥算法的拓撲優化方法。建立了以最小化簇數量、負載偏差和簇移動度為目標的拓撲優化模型，提出了尋優能力更強的自適應蜂鳥算法(ADHA)。設計了一種新穎的編碼映射機制，使蜂鳥個體代表具體的拓撲優化策略，進而利用自適應蜂鳥算法求解拓撲優化問題。仿真實驗表明，所提算法在拓撲優化問題上的優勢明顯。在此基礎上，未來還有更多的工作有待研究：首先，可以研究簇間路由問題，進一步提高無人機之間的數據轉發效率。其次，可以考慮群體移動模型，進一步提高多無人機的協同能力。