劉 琰 趙海濤 張 姣 龔廣偉 潘筱茜 陳海濤 魏急波
①(國(guó)防科技大學(xué)電子科學(xué)學(xué)院 長(zhǎng)沙 410073)
②(中國(guó)人民解放軍31401部隊(duì) 哈爾濱 150090)
無(wú)人機(jī)(Unmanned Aerial Vehicles,UAVs)集群能夠克服單無(wú)人機(jī)系統(tǒng)通信距離短、處理能力有限和承載能力低等局限性,是當(dāng)前研究的熱點(diǎn)領(lǐng)域[1,2]。飛行自組網(wǎng)(Flying Ad hoc NETworks, FANET)能夠利用動(dòng)態(tài)的拓?fù)浣Y(jié)構(gòu)保障無(wú)人機(jī)間的通信協(xié)同,是無(wú)人機(jī)集群通信問(wèn)題的有效解決方案[3]。各無(wú)人機(jī)節(jié)點(diǎn)之間進(jìn)行正常的信息傳輸是保證FANET系統(tǒng)可生存性與可操作性的重要條件,而由節(jié)點(diǎn)間鏈路構(gòu)建的網(wǎng)絡(luò)拓?fù)涑蔀殛P(guān)注的重點(diǎn)。無(wú)人機(jī)在飛行過(guò)程中存在多種不斷變化的因素,節(jié)點(diǎn)的高速移動(dòng)造成地理位置和節(jié)點(diǎn)之間的距離不斷變化,不同的任務(wù)需求造成無(wú)人機(jī)數(shù)量、飛行路線不斷變化,受限頻譜競(jìng)爭(zhēng)或者惡意干擾造成各節(jié)點(diǎn)的實(shí)際可用信道不斷變化。這些因素將導(dǎo)致節(jié)點(diǎn)之間的鏈路頻繁變化,網(wǎng)絡(luò)拓?fù)湟矊㈦S之發(fā)生變化,加重了FANET對(duì)網(wǎng)絡(luò)拓?fù)涞墓芾黼y度。
分簇是優(yōu)化網(wǎng)絡(luò)拓?fù)涔芾淼挠行侄沃唬摻Y(jié)構(gòu)將網(wǎng)絡(luò)劃分為相互連接的簇群,通常每個(gè)簇群由一個(gè)簇首及其若干簇成員組成[4]。文獻(xiàn)[5]提出了一種基于加權(quán)的分簇算法,考慮了剩余能量比、節(jié)點(diǎn)度、相對(duì)移動(dòng)性和平均距離,但算法的分簇效果會(huì)隨著節(jié)點(diǎn)數(shù)量增加而降低,無(wú)法滿(mǎn)足大規(guī)模無(wú)人機(jī)集群的通信需求。文獻(xiàn)[6]使用了低復(fù)雜度的層次分析法和逼近理想點(diǎn)法對(duì)FANET進(jìn)行分簇,但算法的參數(shù)矩陣將直接影響分簇結(jié)果,無(wú)法準(zhǔn)確設(shè)置參數(shù)矩陣以適應(yīng)不同的場(chǎng)景。文獻(xiàn)[7]利用K-means方法對(duì)節(jié)點(diǎn)進(jìn)行分簇,但算法對(duì)K值的學(xué)習(xí)效率較低,不能快速給出最適合當(dāng)前網(wǎng)絡(luò)狀態(tài)的分簇方案。值得注意的是,在實(shí)際應(yīng)用場(chǎng)景中頻譜資源通常是多信道的,同一時(shí)間不同位置節(jié)點(diǎn)的可用信道可能存在差異,只有節(jié)點(diǎn)之間存在相同的可用信道時(shí)才有可能直接建立連接。上述算法雖然能夠從節(jié)點(diǎn)移動(dòng)性的角度出發(fā)對(duì)FANET進(jìn)行了分簇,但是僅通過(guò)傳輸范圍判斷兩個(gè)節(jié)點(diǎn)是否為一跳鄰居,沒(méi)有考慮節(jié)點(diǎn)之間是否存在相同的可用信道。
當(dāng)無(wú)人機(jī)節(jié)點(diǎn)的數(shù)量較多時(shí),對(duì)網(wǎng)絡(luò)進(jìn)行分簇是一個(gè)復(fù)雜的優(yōu)化問(wèn)題,利用傳統(tǒng)方法直接求解過(guò)于復(fù)雜[8]。近年來(lái),研究人員根據(jù)仿生學(xué)原理提出了群智能優(yōu)化算法,并且已經(jīng)用于解決FANET的分簇問(wèn)題。文獻(xiàn)[9]采用飛蛾撲火優(yōu)化算法進(jìn)行網(wǎng)絡(luò)構(gòu)建和節(jié)點(diǎn)部署。文獻(xiàn)[10]利用蝙蝠優(yōu)化算法得到了負(fù)載均衡的分簇方案。文獻(xiàn)[11]設(shè)計(jì)了一種改進(jìn)的粒子群優(yōu)化算法,根據(jù)節(jié)點(diǎn)位置均勻地對(duì)無(wú)人機(jī)進(jìn)行分簇。文獻(xiàn)[12]使用螢火蟲(chóng)優(yōu)化算法和磷蝦優(yōu)化算法對(duì)網(wǎng)絡(luò)進(jìn)行拓?fù)涔芾?。目前基于群智能?yōu)化的分簇算法雖然在相應(yīng)的模型上取得了不錯(cuò)的效果,但是算法建立的模型都沒(méi)有考慮可用信道差異對(duì)分簇的影響,并且所使用的群智能優(yōu)化算法在尋優(yōu)結(jié)果和效率上還有待改善的空間。人工蜂鳥(niǎo)算法(A rtificial Humm ingbird A lgorithm,AHA)是最新提出的優(yōu)化算法,相較于其他算法具有尋優(yōu)精度高、收斂速度快、魯棒性強(qiáng)等特點(diǎn)[13]。本文在AHA算法的基礎(chǔ)上,提出了尋優(yōu)性能更好的自適應(yīng)蜂鳥(niǎo)算法(ADap tive Humm ingb ird A lgorithm,ADHA)。一個(gè)移動(dòng)自主網(wǎng)絡(luò)需要解決節(jié)點(diǎn)移動(dòng)導(dǎo)致的簇動(dòng)態(tài)變化的問(wèn)題,本文在考慮無(wú)人機(jī)移動(dòng)性的基礎(chǔ)上,重點(diǎn)關(guān)注節(jié)點(diǎn)可用信道差異造成的影響,提出了一種基于自適應(yīng)蜂鳥(niǎo)算法的FANET拓?fù)鋬?yōu)化方法。
FANET網(wǎng)絡(luò)由無(wú)人機(jī)節(jié)點(diǎn)組成,網(wǎng)絡(luò)采用分簇結(jié)構(gòu)進(jìn)行拓?fù)涞墓芾?,利用分簇算法將FANET網(wǎng)絡(luò)劃分為不重疊的簇群,同一簇群內(nèi)的節(jié)點(diǎn)使用一條對(duì)所有簇內(nèi)節(jié)點(diǎn)皆可用的主用信道進(jìn)行通信,具體通信場(chǎng)景如圖1所示。實(shí)際環(huán)境中節(jié)點(diǎn)的移動(dòng)性、通信半徑、可用信道差異等因素都將影響分簇的過(guò)程。
圖1 通信場(chǎng)景示例
2.2.1簇結(jié)構(gòu)
節(jié)點(diǎn)集合為U={U1,U2,...,U N},編號(hào)構(gòu)成集合N={1,2,...,N},N為節(jié)點(diǎn)數(shù)量。將整個(gè)頻域劃分為非重疊信道,所有信道表示為集合C={C1,C2,...,C M},編號(hào)構(gòu)成集合為M={1,2,...,M},M為總信道數(shù)量。節(jié)點(diǎn)Ui的實(shí)際可用信道構(gòu)成可用信道集CUi∈C。按照分簇算法得到一種拓?fù)鋬?yōu)化策略A對(duì)網(wǎng)絡(luò)進(jìn)行分簇,第K個(gè)簇群的所有節(jié)點(diǎn)構(gòu)成集合CLk,簇首用C Hk表示。整個(gè)網(wǎng)絡(luò)中簇群總數(shù)量稱(chēng)為簇?cái)?shù)量,用K(A)表示。
2.2.2負(fù)載偏差
E k(A)表 示第K個(gè)簇群中簇成員的數(shù)量,稱(chēng)為簇負(fù)載。負(fù)載偏差是簇負(fù)載的標(biāo)準(zhǔn)差,用S(A)表示,具體公式為
2.2.3簇移動(dòng)度
假設(shè)無(wú)人機(jī)的移動(dòng)僅由其任務(wù)決定,可以在任意方向上隨機(jī)移動(dòng)。如圖2所示,在一個(gè)簇群中,簇首U i形成以R為通信半徑的通信范圍,簇成員U j可能接近或者遠(yuǎn)離簇首。將簇首的通信范圍劃分為安全區(qū)和危險(xiǎn)區(qū),其中安全區(qū)是半徑為0.5R的圓形區(qū)域,而危險(xiǎn)區(qū)是半徑0.5R與R之間的環(huán)形區(qū)域。
圖2 區(qū)域劃分
簇首與簇成員之間的相對(duì)移動(dòng)方向表示為
簇首與簇成員之間的距離用dist(U i,U j)表示,則簇首與簇成員之間的移動(dòng)度R D(U i,U j)可通過(guò)式(4)求得
在拓?fù)鋬?yōu)化策略A下,簇群C Lk的簇移動(dòng)度表示為
整個(gè)網(wǎng)絡(luò)的簇移動(dòng)度表示為
2.2.4優(yōu)化問(wèn)題
本文解決的問(wèn)題是:在分簇結(jié)構(gòu)特征、可用信道差異、最大通信半徑等多種約束下,如何對(duì)FANET拓?fù)溥M(jìn)行優(yōu)化,使網(wǎng)絡(luò)的簇?cái)?shù)量、負(fù)載偏差和簇移動(dòng)度最小。優(yōu)化問(wèn)題的表達(dá)式為
其中,A={CHk,CLk,ξi,m}是一種拓?fù)鋬?yōu)化策略,主要包括確定拓?fù)涞拇厥?、簇成員和簇內(nèi)主用信道等。式(8)保證每個(gè)節(jié)點(diǎn)必須加入簇群,式(9)保證每個(gè)節(jié)點(diǎn)只能加入一個(gè)簇群,式(10)和式(11)保證每個(gè)節(jié)點(diǎn)只能選擇1個(gè)可用信道進(jìn)行簇內(nèi)通信,式(12)保證一個(gè)簇內(nèi)的所有節(jié)點(diǎn)使用1條公共可用信道作為主用信道。式(13)保證簇首與簇成員之間的距離小于最大通信半徑。
人工蜂鳥(niǎo)優(yōu)化算法AHA的靈感來(lái)自蜂鳥(niǎo)的采蜜行為,利用L只蜂鳥(niǎo)在D維搜索空間進(jìn)行運(yùn)動(dòng),尋找待優(yōu)化問(wèn)題(適應(yīng)度函數(shù))的最優(yōu)解。在AHA算法中,每只蜂鳥(niǎo)個(gè)體的位置是其訪問(wèn)的食物源,代表待優(yōu)化問(wèn)題的一個(gè)可行解,用X i=(x i,1,x i,2,...,x i,D)表示。食物源的花蜜補(bǔ)充率代表可行解對(duì)應(yīng)的適應(yīng)度值。AHA設(shè)計(jì)了蜂鳥(niǎo)的覓食方式有效更新蜂鳥(niǎo)位置X i,覓食方式包括引導(dǎo)覓食、區(qū)域覓食和遷移覓食。
引導(dǎo)覓食是指蜂鳥(niǎo)向著目標(biāo)食物源方向進(jìn)行覓食,區(qū)域覓食則是在當(dāng)前食物源的鄰近區(qū)域覓食,兩種覓食方式找到的候選食物源分別表示為
當(dāng)?shù)螖?shù)t達(dá)到遷移系數(shù)M C時(shí),蜂鳥(niǎo)通過(guò)遷移覓食找到的新食物源表示為
其中,L ow和U p分別表示D維問(wèn)題的下邊界和上邊界,r是取值范圍在0~1的隨機(jī)向量。本文對(duì)AHA算法進(jìn)行了簡(jiǎn)要介紹,其詳細(xì)過(guò)程可以參考文獻(xiàn)[13]及相關(guān)文獻(xiàn)。
3.2.1覓食行為動(dòng)態(tài)調(diào)整
3.2.2柯西高斯擾動(dòng)變異
本文采取一種根據(jù)迭代次數(shù)自適應(yīng)調(diào)節(jié)的柯西、高斯融合變異算子進(jìn)行擾動(dòng),具體公式為
本文使用改進(jìn)的sigm oid函數(shù)作為自適應(yīng)調(diào)節(jié)因子A F(t)。具體公式為
用ADHA算法來(lái)求解本文模型中的問(wèn)題時(shí),需要對(duì)蜂鳥(niǎo)個(gè)體進(jìn)行有效的編碼,從而建立蜂鳥(niǎo)個(gè)體與優(yōu)化策略的映射關(guān)系。假設(shè)算法中的蜂鳥(niǎo)種群由L只蜂鳥(niǎo)個(gè)體組成,其中每只蜂鳥(niǎo)個(gè)體代表一種優(yōu)化策略,由向量Xi=(x i,1,x i,2,...,x i,D)表示。蜂鳥(niǎo)個(gè)體Xi的維度D與 節(jié)點(diǎn)總數(shù)M相等,每一維的元素x i,j代 表網(wǎng)絡(luò)中節(jié)點(diǎn)Uj的決策。元素xi,j的取值范圍為(0,2),其中整數(shù)部分和小數(shù)部分表示不同的含義,融合了身份決策、信道決策和入簇決策。身份決策是指確定節(jié)點(diǎn)身份為簇首或簇成員,信道決策是指確定簇首的主用信道,入簇決策是指確定簇成員連接的簇首。
整數(shù)部分表示節(jié)點(diǎn)的身份,若整數(shù)部分為1,則節(jié)點(diǎn)身份是簇首,若整數(shù)部分為0,則節(jié)點(diǎn)身份是簇成員。小數(shù)部分表示信道決策和入簇決策,按照由整數(shù)部分確定的節(jié)點(diǎn)身份可以分為兩種情況。
若節(jié)點(diǎn)身份是簇首,則小數(shù)部分代表節(jié)點(diǎn)的簇內(nèi)主用信道即信道決策,具體表達(dá)式為
其中,D Cj表 示信道決策即簇首節(jié)點(diǎn)Uj選擇的簇內(nèi)主用信道,{x i,j}表示xi,j的小數(shù)部分,A VC(U j)表示節(jié)點(diǎn)U j的可用信道集,| AVC(U j)|表示可用信道數(shù)量,是向上取整函數(shù)。式(22)是一種序號(hào)生成算法,通過(guò)x i,j的小數(shù)部分和可用信道數(shù)量生成序號(hào)a。式(21)中I ndex(AVC(U j),a)表示選擇可用信道集A VC(U j)中的第a個(gè)信道。
若節(jié)點(diǎn)身份是簇成員,則小數(shù)部分代表入簇決策,具體表達(dá)式為
其中,DCHj表示節(jié)點(diǎn)需要連接的簇首,BCH(U j)表示節(jié)點(diǎn)U j的鄰居簇首集,| BCH(U j)|表示鄰居簇首數(shù)量。節(jié)點(diǎn)U j的鄰居簇首是指在節(jié)點(diǎn)通信范圍內(nèi)的簇首,并且簇首的主用信道必須在節(jié)點(diǎn)的可用信道集之中,節(jié)點(diǎn)所有的鄰居簇首構(gòu)成其鄰居簇首集。
圖3給出了8個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)進(jìn)行編碼映射的具體過(guò)程,其中蜂鳥(niǎo)個(gè)體為一種可能的取值情況。第1,3,4,7維元素的整數(shù)部分是1,則相應(yīng)節(jié)點(diǎn)的身份為簇首,其余元素相應(yīng)節(jié)點(diǎn)的身份為簇成員。然后,簇首依據(jù)小數(shù)部分和可用信道情況做出信道決策。例如,簇首U4的可用信道集是{C2,C4,C5},小數(shù)部分是0.95,利用式(22)的序號(hào)生成算法求得序號(hào)a=3,則根據(jù)式(21)選擇其可用信道集的第3個(gè)信道(C5)作為主用信道。最后,簇成員依據(jù)小數(shù)部分和鄰居簇首情況做出入簇決策。例如,簇成員U8的鄰居簇首集是{U1,U5,U7},小數(shù)部分是0.48,利用式(24)的序號(hào)生成算法求得b=2,則根據(jù)式(23)選擇加入其鄰居簇首集的第2個(gè)簇首(U5)。
圖3 編碼映射示例
每只蜂鳥(niǎo)個(gè)體Xi=(x i,1,x i,2,...,x i,D)能夠編碼映射為一種優(yōu)化策略,結(jié)合2.2節(jié)的系統(tǒng)模型,蜂鳥(niǎo)個(gè)體X i對(duì)應(yīng)的簇?cái)?shù)量、負(fù)載偏差和簇移動(dòng)度分別為K(X i),S(X i)和G(X i)。針對(duì)式(7)建立的優(yōu)化目標(biāo),蜂鳥(niǎo)個(gè)體Xi的適應(yīng)度函數(shù)設(shè)計(jì)為
首先,獲取部署區(qū)域內(nèi)的各無(wú)人機(jī)的位置、可用信道情況和移動(dòng)速度等實(shí)際網(wǎng)絡(luò)情況。然后,根據(jù)實(shí)際網(wǎng)絡(luò)情況設(shè)置算法參數(shù),如蜂鳥(niǎo)個(gè)體維度D、蜂鳥(niǎo)種群規(guī)模L、最大迭代次數(shù)Tmax等。將每只蜂鳥(niǎo)個(gè)體編碼映射為相應(yīng)的拓?fù)鋬?yōu)化策略,并且構(gòu)建以最小化簇?cái)?shù)量、負(fù)載偏差和簇移動(dòng)性為目標(biāo)的適應(yīng)度函數(shù)。隨后,執(zhí)行ADHA算法迭代求解使適應(yīng)度值最小的最優(yōu)蜂鳥(niǎo)個(gè)體。最后,按照最優(yōu)蜂鳥(niǎo)個(gè)體代表的優(yōu)化策略進(jìn)行實(shí)際拓?fù)溥B接。拓?fù)鋬?yōu)化流程如圖4所示。
圖4 拓?fù)鋬?yōu)化流程圖
節(jié)點(diǎn)隨機(jī)分布在50 km×50 km的矩形區(qū)域,從總信道中隨機(jī)選取部分信道作為各節(jié)點(diǎn)的可用信道,選擇應(yīng)用最廣泛的隨機(jī)路點(diǎn)模型[14]模擬節(jié)點(diǎn)的移動(dòng)。仿真場(chǎng)景的具體設(shè)置如表1所示。
表1 仿真參數(shù)設(shè)置
利用麻雀搜索算法(Sparrow Search A lgorithm,SSA)[15]、野馬優(yōu)化算法(W ild Horse Optim ization,WHO)[16]、AHA[13]和ADHA共4種群智能優(yōu)化算法進(jìn)行對(duì)比。對(duì)比算法的基礎(chǔ)程序均從相應(yīng)文獻(xiàn)作者處獲取,參數(shù)設(shè)置與相應(yīng)文獻(xiàn)保持一致,具體參數(shù)設(shè)置如表2所示。
表2 算法參數(shù)設(shè)置
4.2.1節(jié)點(diǎn)數(shù)量的影響
為了驗(yàn)證節(jié)點(diǎn)數(shù)量變化對(duì)分簇結(jié)果的影響,設(shè)置總信道數(shù)量為10,最大通信半徑為15 km,節(jié)點(diǎn)數(shù)量在50~300變化,仿真結(jié)果如圖5所示。由圖5(a)、圖5(b)和圖5(d)可見(jiàn),隨著節(jié)點(diǎn)數(shù)量不斷增加,各算法的適應(yīng)度值、平均簇?cái)?shù)量、平均簇移動(dòng)度都會(huì)增加,這是因?yàn)樵诓渴鸱秶潭ú蛔兊那闆r下,節(jié)點(diǎn)數(shù)量增加會(huì)導(dǎo)致節(jié)點(diǎn)密度增大。值得注意的是,ADHA算法取得的適應(yīng)度值在不同節(jié)點(diǎn)數(shù)量下均是最低的。由圖5(c)可見(jiàn),SSA, WHO和AHA算法的平均負(fù)載偏差隨著節(jié)點(diǎn)數(shù)量的增加不斷增大,而ADHA算法的簇負(fù)載偏差基本保持在1附近,說(shuō)明ADHA算法的拓?fù)浣Y(jié)構(gòu)更加均勻。
4.2.2總信道數(shù)量的影響
為了驗(yàn)證總信道數(shù)量變化對(duì)分簇結(jié)果的影響,設(shè)置最大通信半徑為15 km,節(jié)點(diǎn)數(shù)量為150,總信道數(shù)量在5~20變化,仿真結(jié)果如圖6所示。由圖6(a)和圖6(b)可見(jiàn),隨著總信道數(shù)量不斷增加,各算法的適應(yīng)度值、平均簇?cái)?shù)量也相應(yīng)增加。這是因?yàn)楦鞴?jié)點(diǎn)的可用信道從總信道中隨機(jī)選取,總信道數(shù)量增加會(huì)使各節(jié)點(diǎn)可用信道差異增大。由圖6(c)和圖6(d)可見(jiàn),ADHA算法的平均負(fù)載偏差和平均簇移動(dòng)度明顯小于其他算法,說(shuō)明算法得到的簇群更加均勻和穩(wěn)定。整體來(lái)看,在不同總信道數(shù)量下,ADHA算法的各項(xiàng)優(yōu)化結(jié)果仍是最好的。
圖6 總信道數(shù)量變化對(duì)算法分簇結(jié)果的影響
4.2.3通信半徑的影響
為了驗(yàn)證最大通信半徑變化對(duì)分簇結(jié)果的影響,設(shè)置節(jié)點(diǎn)數(shù)量為150,總信道數(shù)量為15,最大通信半徑在5~15 km變化,仿真結(jié)果如圖7所示。由于ADHA算法求解拓?fù)鋬?yōu)化問(wèn)題的過(guò)程中能夠自適應(yīng)調(diào)整尋優(yōu)動(dòng)作,其可以獲得最小的適應(yīng)度值、平均數(shù)量、平均負(fù)載偏差和平均簇移動(dòng)度。
圖7 最大通信半徑變化對(duì)算法分簇結(jié)果的影響
本文研究了FANET網(wǎng)絡(luò)中的拓?fù)鋬?yōu)化問(wèn)題,重點(diǎn)考慮節(jié)點(diǎn)移動(dòng)性和可用信道差異的影響,提出了一種基于自適應(yīng)蜂鳥(niǎo)算法的拓?fù)鋬?yōu)化方法。建立了以最小化簇?cái)?shù)量、負(fù)載偏差和簇移動(dòng)度為目標(biāo)的拓?fù)鋬?yōu)化模型,提出了尋優(yōu)能力更強(qiáng)的自適應(yīng)蜂鳥(niǎo)算法(ADHA)。設(shè)計(jì)了一種新穎的編碼映射機(jī)制,使蜂鳥(niǎo)個(gè)體代表具體的拓?fù)鋬?yōu)化策略,進(jìn)而利用自適應(yīng)蜂鳥(niǎo)算法求解拓?fù)鋬?yōu)化問(wèn)題。仿真實(shí)驗(yàn)表明,所提算法在拓?fù)鋬?yōu)化問(wèn)題上的優(yōu)勢(shì)明顯。在此基礎(chǔ)上,未來(lái)還有更多的工作有待研究:首先,可以研究簇間路由問(wèn)題,進(jìn)一步提高無(wú)人機(jī)之間的數(shù)據(jù)轉(zhuǎn)發(fā)效率。其次,可以考慮群體移動(dòng)模型,進(jìn)一步提高多無(wú)人機(jī)的協(xié)同能力。