基于聯(lián)盟圖博弈的地下空間無人機(jī)應(yīng)急通信網(wǎng)絡(luò)拓?fù)淇刂扑惴?/h1>
2022-03-30 09:14:18王博文孫彥景
電子與信息學(xué)報(bào) 2022年3期
王博文 孫彥景
(中國(guó)礦業(yè)大學(xué)信息與控制工程學(xué)院 徐州 221008)
(徐州市智能安全與應(yīng)急協(xié)同工程研究中心 徐州 221008)
1 引言
近年來，地下大型綜合體、地鐵、礦井等地下空間規(guī)?；_發(fā)利用造成了地下空間災(zāi)害事故頻發(fā)。當(dāng)塌陷、火災(zāi)、礦井沖擊地壓等地下空間災(zāi)害事故發(fā)生時(shí)，首要的任務(wù)就是實(shí)時(shí)獲取災(zāi)情信息并建立臨時(shí)通信網(wǎng)絡(luò)，為后續(xù)的救援工作提供支撐。我國(guó)地下空間事故應(yīng)急救援體系尚未建立健全，導(dǎo)致地下空間應(yīng)急救援網(wǎng)絡(luò)的研究工作相對(duì)滯后[1]。輕小型、高負(fù)載、高續(xù)航無人機(jī)(Unmanned Aerial Vehicle, UAV) 技術(shù)的突破，使得UAV在地下空間應(yīng)急救援的應(yīng)用成為可能?？仗斓匾惑w化網(wǎng)絡(luò)是6G的核心方向之一，現(xiàn)有關(guān)于6G潛在關(guān)鍵技術(shù)的預(yù)研工作中，明確將災(zāi)后應(yīng)急救援作為6G空天地一體化網(wǎng)絡(luò)的主要應(yīng)用場(chǎng)景[2,3]。
UAV網(wǎng)絡(luò)作為空天地一體化網(wǎng)絡(luò)的重要組成部分，可在地下空間突發(fā)災(zāi)害事故應(yīng)急救援的“探、搜、救”不同階段發(fā)揮關(guān)鍵作用[4]。2018年，應(yīng)急管理部發(fā)布《應(yīng)急管理信息化發(fā)展戰(zhàn)略規(guī)劃框架》，要求整合UAV等空基網(wǎng)絡(luò)資源，實(shí)現(xiàn)對(duì)地下空間等災(zāi)害事故易發(fā)、多發(fā)、頻發(fā)區(qū)域全方位、立體化、無盲區(qū)的災(zāi)情監(jiān)測(cè)與通信覆蓋[5]。如圖1所示，應(yīng)急指揮中心在災(zāi)情探測(cè)階段對(duì)災(zāi)情進(jìn)行推演預(yù)判后，派遣全地形可移動(dòng)的UAV集群深入地下空間對(duì)可疑目標(biāo)點(diǎn)進(jìn)行協(xié)同搜索，攜帶不同類型傳感與通信設(shè)備的UAV終端共同形成UAV應(yīng)急通信網(wǎng)絡(luò)，為后續(xù)的災(zāi)害救援工作提供支撐。
圖1 地下空間災(zāi)后UAV應(yīng)急通信網(wǎng)絡(luò)
與傳統(tǒng)的地面自組織網(wǎng)絡(luò)或智能化自主網(wǎng)絡(luò)相比，其相同之處在于地下空間無人機(jī)應(yīng)急通信網(wǎng)絡(luò)同樣需要分布式自組織的決策能力作為實(shí)現(xiàn)地下空間無人機(jī)集群拓?fù)淇刂频幕A(chǔ)；其不同之處在于地下空間的復(fù)雜不確定性與無人機(jī)節(jié)點(diǎn)的高速移動(dòng)性需要地下空間無人機(jī)應(yīng)急通信網(wǎng)絡(luò)具備無人機(jī)群的群體智能與高效的信息交互能力，并通過更高效快速的群體決策以適應(yīng)快變網(wǎng)絡(luò)拓?fù)洹Ｎ墨I(xiàn)[6]詳細(xì)綜述了UAV集群在礦井應(yīng)急場(chǎng)景中的典型應(yīng)用。文獻(xiàn)[7]針對(duì)災(zāi)后應(yīng)急場(chǎng)景UAV中繼與空中基站兩種典型應(yīng)用中的路徑規(guī)劃與功率控制問題展開研究。上述文獻(xiàn)忽略了UAV集群協(xié)同作業(yè)時(shí)的組網(wǎng)需求，考慮到地下空間災(zāi)害事故具有復(fù)雜繼發(fā)、耦合疊加等特性，具備抗毀、容錯(cuò)性的網(wǎng)絡(luò)架構(gòu)是UAV集群智能與高效任務(wù)協(xié)同的關(guān)鍵。文獻(xiàn)[8,9]詳細(xì)分析了UAV自組網(wǎng)的網(wǎng)絡(luò)特性與拓?fù)淇刂品椒?，?dāng)前有關(guān)UAV組網(wǎng)的相關(guān)文獻(xiàn)主要針對(duì)低動(dòng)態(tài)場(chǎng)景，研究以網(wǎng)絡(luò)持續(xù)連通為目標(biāo)的拓?fù)淇刂?，較少考慮場(chǎng)景的動(dòng)態(tài)不確定性。基于網(wǎng)絡(luò)連通性的拓?fù)淇刂仆ㄟ^功率控制，節(jié)點(diǎn)移動(dòng)控制等措施實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)溥B通。拓?fù)涔β士刂萍赐ㄟ^調(diào)整部分節(jié)點(diǎn)的傳輸功率構(gòu)建遠(yuǎn)程傳輸鏈路(Long-range Links, LLs)，從而獲取更豐富的端到端路徑；節(jié)點(diǎn)移動(dòng)控制通過改變節(jié)點(diǎn)的移動(dòng)軌跡進(jìn)而改善網(wǎng)絡(luò)節(jié)點(diǎn)間的相對(duì)位置，從而獲取期望的連通特性[10]。地下空間災(zāi)后應(yīng)急救援場(chǎng)景UAV節(jié)點(diǎn)移動(dòng)性與搜救、覆蓋任務(wù)緊密關(guān)聯(lián)，因此本文主要通過功率控制實(shí)現(xiàn)網(wǎng)絡(luò)持續(xù)連通性。文獻(xiàn)[11]提出一種基于功率與軌跡聯(lián)合控制的UAV集群自組網(wǎng)拓?fù)淇刂品椒?，但該方法僅能實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)涞膯芜B通性，任意節(jié)點(diǎn)的離開均會(huì)造成連通性失效。考慮到地下空間應(yīng)急場(chǎng)景UAV的易毀性，需要通過更高等級(jí)的連通性確保網(wǎng)絡(luò)的容錯(cuò)抗毀性。
文獻(xiàn)[12]利用塊-割樹(Block-Cut Tree, BCT)提取連通圖中的關(guān)鍵信息，通過構(gòu)建強(qiáng)化邊實(shí)現(xiàn)最小代價(jià)的2-連通性。文獻(xiàn)[13]利用Prim算法搜索BCT中的強(qiáng)化邊，進(jìn)而指導(dǎo)LLs構(gòu)建的方向，實(shí)現(xiàn)UAV自組網(wǎng)拓?fù)鋱D的2-連通性。然而，該方法沒有考慮不同LLs對(duì)于網(wǎng)絡(luò)連通性、鏈路損耗、端到端時(shí)延的差異化影響。在聯(lián)盟博弈(Coalitional Game, CG)中，聯(lián)盟內(nèi)參與者之間的關(guān)聯(lián)性會(huì)對(duì)聯(lián)盟的總效用值產(chǎn)生重要影響[14]。其中，聯(lián)盟圖博弈(Coalitional Graph Game, CGG)將圖論與聯(lián)盟博弈結(jié)合，利用圖中節(jié)點(diǎn)間的關(guān)聯(lián)刻畫效用獨(dú)立關(guān)系，即聯(lián)盟效用與參與者之間的連接方式有關(guān)[15]。因此，可將CG引入時(shí)變拓?fù)鋱D，利用CGG對(duì)LLs構(gòu)建進(jìn)行問題建模，從而實(shí)現(xiàn)多種指標(biāo)的權(quán)衡優(yōu)化，保證網(wǎng)絡(luò)連通性的同時(shí)，提升容錯(cuò)能力。文獻(xiàn)[16]分別提出一種啟發(fā)式LLs構(gòu)建算法與基于轉(zhuǎn)換操作的CGG算法，然而上述算法并沒有考慮連通性的優(yōu)化，且算法復(fù)雜度較高、決策時(shí)間較長(zhǎng)，極易造成組網(wǎng)決策與快變拓?fù)洳黄ヅ洌B通性頻繁失效，不適用于拓?fù)浣Y(jié)構(gòu)隨災(zāi)情演變快速變化的UAV應(yīng)急通信網(wǎng)絡(luò)。
地下空間災(zāi)后特殊的應(yīng)用環(huán)境要求UAV應(yīng)急通信網(wǎng)絡(luò)減少端到端傳輸時(shí)延，保證穩(wěn)定可靠的信息交互與災(zāi)情實(shí)時(shí)回傳。地下空間無人機(jī)集群的拓?fù)浣Y(jié)構(gòu)同時(shí)受到搜救任務(wù)需求、組網(wǎng)決策與有限遮蔽空間結(jié)構(gòu)的影響，如井下巷道狹長(zhǎng)的帶狀空間中，無人機(jī)集群的飛行活動(dòng)受限，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)呈“一”字形。此外，UAV集群在執(zhí)行搜救任務(wù)時(shí)，地下空間災(zāi)害事故的高動(dòng)態(tài)不確定性導(dǎo)致網(wǎng)絡(luò)拓?fù)溲杆僮兓?，連通性頻繁失效，UAV應(yīng)急通信網(wǎng)絡(luò)在滿足機(jī)群間低時(shí)延通信需求的同時(shí)，還需通過保障網(wǎng)絡(luò)的韌性(容錯(cuò)抗毀)與柔性(按需動(dòng)態(tài)重構(gòu))維護(hù)網(wǎng)絡(luò)的持續(xù)連通性，實(shí)現(xiàn)傳輸?shù)倪B續(xù)性，亟需設(shè)計(jì)高效低復(fù)雜度的拓?fù)淇刂品椒▽?shí)現(xiàn)對(duì)拓?fù)渥兓目焖夙憫?yīng)。為此，本文首先將UAV應(yīng)急通信網(wǎng)絡(luò)拓?fù)淇刂茊栴}建模為CGG，然后通過BCT對(duì)時(shí)變拓?fù)鋱D中的關(guān)鍵信息提取，用以指導(dǎo)CGG中決策空間的簡(jiǎn)化與連通性優(yōu)化；最后提出一種分布式低復(fù)雜度的輪轉(zhuǎn)互操作方法得到納什穩(wěn)定均衡(Nash-Stable Equilibrium, NSE)的聯(lián)盟結(jié)構(gòu)。仿真結(jié)果表明，與其他現(xiàn)有算法相比，所提算法能更好地實(shí)現(xiàn)拓?fù)溥B通性、端到端平均傳輸時(shí)延與鏈路損耗3種性能之間的權(quán)衡優(yōu)化，且具有較快的收斂速度，能夠?qū)崿F(xiàn)災(zāi)后動(dòng)態(tài)不確定場(chǎng)景下組網(wǎng)決策與快變拓?fù)涞倪m配。
2 系統(tǒng)模型與問題表述
如圖2所示，將時(shí)變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抽象為一組連續(xù)時(shí)隙的無向圖(G1,G2,...,Gt,...,GT),Gt=(V(t),E(t))表示t時(shí)刻的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，其中V(t)表示點(diǎn)集合，即t時(shí)刻的節(jié)點(diǎn)集合；當(dāng)兩個(gè)節(jié)點(diǎn)處于彼此的一跳通信范圍內(nèi)，在兩個(gè)節(jié)點(diǎn)之間添加一條無向邊，E(t)表示傳輸鏈路集合?？紤]到UAV通信范圍的有限性，網(wǎng)絡(luò)拓?fù)渲腥我鈨牲c(diǎn)大多通過多跳鏈路傳輸，造成了端到端時(shí)延難以保障。UAV應(yīng)急通信網(wǎng)絡(luò)需要把災(zāi)情信息匯聚至接近中心度(Closeness Centrality, CC)最高的節(jié)點(diǎn)uD后，由uD實(shí)時(shí)回傳至地面應(yīng)急指揮中心，則t時(shí)刻整個(gè)網(wǎng)絡(luò)的端到端平均傳輸時(shí)延可表示為
圖2 時(shí)變網(wǎng)絡(luò)拓?fù)鋱D與BCT轉(zhuǎn)化
因此，可通過在距離較遠(yuǎn)的兩節(jié)點(diǎn)之間構(gòu)建LLs的方式建立直連通信，減少ui～uD的跳數(shù)|Hi,D|，進(jìn)而縮短傳輸時(shí)延。在圖論中，k-連通圖是指最少移除k個(gè)節(jié)點(diǎn)后，連通性失效，k為圖的連通度。移除后使單連通圖失效的節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn)，也稱為割點(diǎn)。首先，為了確保式(6)成立，即任一節(jié)點(diǎn)ui與uD間均存在通路，需至少確保網(wǎng)絡(luò)的單連通性，因此本文采用文獻(xiàn)[17]中的集群移動(dòng)模型，該模型既能模擬UAV集群的協(xié)同行為，又能保障兩點(diǎn)間的距離在一跳通信范圍內(nèi)，進(jìn)而保障網(wǎng)絡(luò)的單連通性，避免出現(xiàn)孤立節(jié)點(diǎn)。復(fù)雜地形環(huán)境下的無人機(jī)航路規(guī)劃問題中的避障飛行是核心難題，現(xiàn)有的工作大多將多個(gè)啟發(fā)式算法的優(yōu)勢(shì)進(jìn)行結(jié)合，采用鯨魚算法等新型群體智能算法實(shí)現(xiàn)對(duì)優(yōu)化問題更高效的求解。文獻(xiàn)[18]提出一種改進(jìn)鯨魚優(yōu)化算法，實(shí)現(xiàn)了兩點(diǎn)之間的代價(jià)最優(yōu)的避障飛行。通過對(duì)無人機(jī)節(jié)點(diǎn)與通信鏈路的圖論建模，可用節(jié)點(diǎn)之間的連通性刻畫無人機(jī)的高速移動(dòng)性，因此移動(dòng)模型的選擇僅影響拓?fù)溥B通性變化的頻率。復(fù)雜環(huán)境下可將集群移動(dòng)模型與鯨魚優(yōu)化算法結(jié)合，通過群體感知與信息交互實(shí)現(xiàn)集群避障。此外，移動(dòng)模型的選擇不影響算法性能且縱深較長(zhǎng)的地下空間災(zāi)后應(yīng)急場(chǎng)景，可通過合理設(shè)置飛行高度避障，因此本文主要研究無人機(jī)集群高速移動(dòng)場(chǎng)景下的拓?fù)淇刂茊栴}，重點(diǎn)關(guān)注拓?fù)溥B通性變化頻率。
在單連通圖中，割點(diǎn)UAV的移除與移動(dòng)均會(huì)導(dǎo)致網(wǎng)絡(luò)連通性失效。因此，LLs的建立有助于進(jìn)一步提升網(wǎng)絡(luò)的連通度，從而提升UAV應(yīng)急通信網(wǎng)絡(luò)的容錯(cuò)性與抗毀性，其中容錯(cuò)性與抗毀性表示多跳傳輸鏈路中單一中繼節(jié)點(diǎn)失效時(shí)，可通過其他連通鏈路實(shí)現(xiàn)斷點(diǎn)續(xù)傳，實(shí)現(xiàn)傳輸連續(xù)性。考慮到連通度提升與遠(yuǎn)程鏈路能耗的權(quán)衡，本文擬設(shè)計(jì)滿足基本的2-連通的LLs建立方案，即單一節(jié)點(diǎn)的失效不影響網(wǎng)絡(luò)的連通性。為了實(shí)現(xiàn)拓?fù)涞?-連通，需要添加強(qiáng)化邊消除拓?fù)渲械母铧c(diǎn)，可通過式(3)控制功率構(gòu)建LLs來實(shí)現(xiàn)。
將圖2所示的網(wǎng)絡(luò)拓?fù)渲械母铧c(diǎn)、塊及消除割點(diǎn)的強(qiáng)化邊進(jìn)行標(biāo)記，其中割點(diǎn)所關(guān)聯(lián)的最大2-連通子圖稱為塊，即在該連通子圖中任一節(jié)點(diǎn)的移除不影響連通性且任一相鄰節(jié)點(diǎn)的加入均造成該子圖的2-連通失效。進(jìn)而將左圖中的整個(gè)塊映射為右圖中一個(gè)塊點(diǎn)，將關(guān)聯(lián)同一個(gè)割點(diǎn)和塊點(diǎn)的邊合并，并映射為樹邊，再將關(guān)聯(lián)同一個(gè)割點(diǎn)和同一個(gè)塊點(diǎn)的強(qiáng)化邊合并(如E1與E2可合并為一條邊)，可以將時(shí)變拓?fù)鋱D的非關(guān)鍵信息簡(jiǎn)化，建立右圖所示的BCT?；贐CT，可以判斷每條LLs的構(gòu)建對(duì)于拓?fù)溥B通性的貢獻(xiàn)St(i,j)，S(i,j)為強(qiáng)化邊(i,j)的建立所消除的割點(diǎn)數(shù)，如E1對(duì)于拓?fù)溥B通性的貢獻(xiàn)為1，E3的貢獻(xiàn)為0。此外，強(qiáng)化邊(i,j)的建立往往伴隨著功率的消耗，用Ct(i,j)=c·Pi(t)表示LLs的鏈路損耗，其中c為單位功率下的損耗常數(shù)。
綜上所述，地下空間UAV應(yīng)急通信網(wǎng)絡(luò)中LLs構(gòu)建的優(yōu)化目標(biāo)可表示為端到端平均傳輸時(shí)延、網(wǎng)絡(luò)連通性與鏈路損耗的權(quán)衡優(yōu)化
3 基于聯(lián)盟圖博弈的自適應(yīng)拓?fù)淇刂扑惴ㄔO(shè)計(jì)
3.1 CGG建模
傳統(tǒng)的CG通過合并-拆分準(zhǔn)則將用戶集合分割為多個(gè)不相交的聯(lián)盟，解決用戶分簇、資源分配等問題，實(shí)現(xiàn)所有聯(lián)盟效用函數(shù)的最優(yōu)化。CGG將圖論引入CG，使得聯(lián)盟效用與聯(lián)盟內(nèi)成員的連接方式相關(guān)，即將同一條邊相連的兩點(diǎn)劃分為同一聯(lián)盟。因此，可將LLs構(gòu)建問題抽象為CGG，即將在圖Gt=(V(t),E(t))上建立LLs的兩點(diǎn)劃分為同一聯(lián)盟?；谏鲜龇治觯蓪⒃揅 G G 表示為Gt=(Nt,Xt,Ut)，其中Nt代表t時(shí)刻的博弈參與者，即UAV節(jié)點(diǎn)集合V(t)。Xt為UAV節(jié)點(diǎn)的策略集合，每個(gè)UAV節(jié)點(diǎn)的決策空間為當(dāng)前時(shí)刻除自身外的其他UAV節(jié)點(diǎn)，即通過2元決策變量選擇與其他UAV節(jié)點(diǎn)建立LLs。定義每個(gè)UAV節(jié)點(diǎn)的決策為xi(t)∈Xi(t)，其中Xi(t)={1,2,...,N(t)}為節(jié)點(diǎn)i在t時(shí)刻的可行策略空間。xi(t)可由2元決策變量xi,j,t一一映射，如xi,j,t=1表示xi(t)=j。此外，令x?i(t)=(x1(t),...,xi?1(t),xi+1(t),...,xN(t)(t))表示除xi(t)外其他節(jié)點(diǎn)的策略集集合。為了進(jìn)一步簡(jiǎn)化決策空間，本文通過BCT指導(dǎo)無連通性貢獻(xiàn)節(jié)點(diǎn)的刪減。如圖2所示，對(duì)于塊點(diǎn)B1內(nèi)的節(jié)點(diǎn)1，可通過BCT首先排除與塊內(nèi)節(jié)點(diǎn)建立LLs，再通過強(qiáng)化邊的指向判斷與該塊內(nèi)節(jié)點(diǎn)建立LLs是否有助于消除割點(diǎn)，進(jìn)而縮減每個(gè)節(jié)點(diǎn)的策略集合。
Ut為UAV應(yīng)急通信網(wǎng)絡(luò)中所有節(jié)點(diǎn)的總效用，考慮到無人機(jī)集群的協(xié)同性，在本文所提模型中，所有節(jié)點(diǎn)通過相互協(xié)作共同提升Ut。對(duì)于節(jié)點(diǎn)i，其t時(shí)刻的效用函數(shù)應(yīng)與優(yōu)化目標(biāo)式(7)保持一致。值得注意的是，本文的優(yōu)化目標(biāo)為最小化時(shí)延、損耗與連通性貢獻(xiàn)度3者之間的權(quán)衡值，而CGG的優(yōu)化目標(biāo)一般為效用的最大化，因此效用函數(shù)可表示為
3.2 算法設(shè)計(jì)與性能分析
傳統(tǒng)求解CGG的方法大多采用局部最優(yōu)反應(yīng)(Local Best Response,LBR)策略求得局部最優(yōu)的納什均衡解，但該方法的收斂速度較慢且容易收斂至質(zhì)量較差的局部最優(yōu)解。文獻(xiàn)[16]提出一種基于轉(zhuǎn)換操作的聯(lián)盟博弈算法(Coalition Game algorithm based on SWitch operation, CG-SW)，能夠在有限的轉(zhuǎn)換次數(shù)內(nèi)得到質(zhì)量較好的近似最優(yōu)解。然而，該算法的轉(zhuǎn)換操作僅在兩個(gè)聯(lián)盟間進(jìn)行，忽略了多聯(lián)盟互操作所帶來的收斂速度與求解質(zhì)量?jī)煞矫娴奶嵘?。考慮到頻譜資源的限制以及能量的有限性，假設(shè)t時(shí)刻最多建立M(t)條LLs，本文令M為實(shí)現(xiàn)2-聯(lián)通所需建立的最小強(qiáng)化邊數(shù)。進(jìn)一步地，定義聯(lián)盟集合Πt=(π1,π2,...,πK)，其中Kt=N(t)-M(t)表示最終形成的聯(lián)盟數(shù)目，其中由M(t)個(gè)聯(lián)盟內(nèi)有兩節(jié)點(diǎn)，N(t)-2·M(t)個(gè)聯(lián)盟內(nèi)為單節(jié)點(diǎn)。
本文用(v1→πv2)表示節(jié)點(diǎn)v1離開當(dāng)前聯(lián)盟πv1，轉(zhuǎn)而替換v2加入πv2，即斷開與πv1中與另一節(jié)點(diǎn)建立的LLs轉(zhuǎn)而替換v2與πv2中的另一節(jié)點(diǎn)建立LLs，實(shí)現(xiàn)xi(t)的轉(zhuǎn)換。考慮到單節(jié)點(diǎn)聯(lián)盟與兩節(jié)點(diǎn)聯(lián)盟之間的互操作，可用v1→πv2且?→πv1表示v1加入聯(lián)盟πv2且不替換πv2內(nèi)的任何聯(lián)盟成員。CGG通過聯(lián)盟的劃分得到滿足NSE的聯(lián)盟結(jié)構(gòu)，NSE表示在當(dāng)前的策略集合中不存在任一策略使得聯(lián)盟總效用得到提升，結(jié)合上述輪轉(zhuǎn)互操作聯(lián)盟的定義，可將NSE進(jìn)一步轉(zhuǎn)換為如下定義。
定義2 聯(lián)盟Πt為NSE聯(lián)盟當(dāng)且僅當(dāng)聯(lián)盟間不存在輪轉(zhuǎn)互操作聯(lián)盟。
進(jìn)一步地，用v1→v2表示v1替換v2加入πv2且v2離開πv2，用ΔU(v1→v2)表示該操作所引發(fā)的總效用值變化，則ΔU(v1→v2)可表示為
推論2 CGG-ATC算法能在有限次迭代后收斂至NSE。
證明：由于時(shí)變拓?fù)鋱DGt與有向圖的點(diǎn)集合與邊集合均為有限集合，因此CGG的策略空間有限，又因?yàn)檩嗈D(zhuǎn)互換操作v1→v2→,...,vi?1→vi →v1的性能非減性且消除輪轉(zhuǎn)互操作聯(lián)盟所提升的性能有上界，因此CGG-ATC算法步驟2的迭代次數(shù)有上界。當(dāng)算法收斂時(shí)，代表當(dāng)前聯(lián)盟策略Πt中不存在輪轉(zhuǎn)互操作聯(lián)盟，根據(jù)推論1可證當(dāng)前聯(lián)盟策略Πt為NSE聯(lián)盟。此外，CGG-ATC算法通過BCT進(jìn)一步簡(jiǎn)化了策略空間，因此具有較快的收斂速度。
表1 最大權(quán)輪轉(zhuǎn)互操作聯(lián)盟搜索(MWRS)算法
表2 基于聯(lián)盟圖博弈的自適應(yīng)拓?fù)淇刂?CGG-ATC)算法
4 仿真結(jié)果與性能分析
為了驗(yàn)證上述章節(jié)關(guān)于所提算法理論分析的可靠性，本節(jié)通過數(shù)值仿真對(duì)所提算法的端到端平均時(shí)延、功率損耗、連通性以及收斂性進(jìn)行綜合評(píng)估。本文仿真場(chǎng)景設(shè)置為全長(zhǎng)1000 m、寬200 m、埋深40 m的地下空間，總?cè)蝿?wù)時(shí)長(zhǎng)為10000 s，共劃分為5000個(gè)持續(xù)時(shí)長(zhǎng)為2 s的等間隔時(shí)隙。為了更好地模擬UAV節(jié)點(diǎn)執(zhí)行任務(wù)的協(xié)同性并保障網(wǎng)絡(luò)的連通性，本文采用文獻(xiàn)[17]中的集群移動(dòng)模型，且移動(dòng)模型參數(shù)、能量模型參數(shù)與充電行為參數(shù)的設(shè)置均與文獻(xiàn)[17]保持一致。此外，在通信模型中，單位距離信道增益為η0=-60 dB，路徑損耗系數(shù)為α=2，噪聲功率為–120 dBm，發(fā)送功率范圍為20～30 dBm，SNR閾值γth設(shè)為30 dB，每條鏈路分配的信道帶寬為5 MHz，包長(zhǎng)大小的范圍為1～10 Mbit，控制變量ω1=ω2=ω3=1/3?？紤]到每時(shí)刻開始UAV節(jié)點(diǎn)的位置與進(jìn)退網(wǎng)行為(離開當(dāng)前網(wǎng)絡(luò)到地面站充電或充電結(jié)束回到當(dāng)前網(wǎng)絡(luò))的動(dòng)態(tài)隨機(jī)性，本文采用蒙特卡羅仿真評(píng)估1000次仿真下算法的平均性能。
為了更好地驗(yàn)證所提算法的有效性，本文將以下3種算法作為對(duì)照算法進(jìn)行性能對(duì)比：
圖3–圖6繪制了以上所提算法在1000次仿真下端到端平均時(shí)延、功率損耗、連通性以及收斂性隨場(chǎng)景中UAV節(jié)點(diǎn)數(shù)目變化的情況。其中在收斂性能的評(píng)估時(shí)，由于ES算法復(fù)雜度極高，僅對(duì)比本文算法與LPCBA和CG-SW的收斂速度。
從圖3結(jié)果來看，隨著UAV數(shù)量的增加，網(wǎng)絡(luò)規(guī)模逐漸擴(kuò)大，可構(gòu)建的LLs逐漸增多，CGG-ATC的聯(lián)盟的結(jié)構(gòu)也更加復(fù)雜。隨著任意兩節(jié)點(diǎn)之間跳數(shù)的增加，端到端平均時(shí)延逐漸上升，LLs的構(gòu)建在一定程度上緩和了時(shí)延上升趨勢(shì)。與兩兩聯(lián)盟互換的CG-SW算法相比，本文所提CGG-ATC算法通過多聯(lián)盟的互操作得到更高質(zhì)量的近似最優(yōu)解。
圖3 端到端平均時(shí)延性能對(duì)比
圖4繪制了網(wǎng)絡(luò)連通性隨UAV數(shù)量變化的趨勢(shì)，本文用當(dāng)前網(wǎng)絡(luò)中存在的平均割點(diǎn)數(shù)衡量該性能。由圖4可知即使是可以得到全局最優(yōu)解的ES算法仍會(huì)存在一定數(shù)量的割點(diǎn)，這是因?yàn)閁AV節(jié)點(diǎn)功率上界的限制導(dǎo)致部分LLs無法構(gòu)建。由于CGSW算法僅優(yōu)化端到端平均時(shí)延與鏈路損耗，忽略了網(wǎng)絡(luò)連通性的維護(hù)，導(dǎo)致容錯(cuò)性與抗毀性較差，可能會(huì)由于割點(diǎn)UAV的損壞導(dǎo)致當(dāng)前網(wǎng)絡(luò)拓?fù)鋫鬏斶B續(xù)性難以保障。
圖4 網(wǎng)絡(luò)拓?fù)溥B通性對(duì)比
圖5展示了鏈路損耗隨UAV數(shù)量變化的趨勢(shì)，本文用平均發(fā)送功率來評(píng)估該性能。隨著UAV數(shù)量的增加，可構(gòu)建的LLs逐漸增多，越來越多的UAV節(jié)點(diǎn)通過提升功率來構(gòu)建LLs，但當(dāng)網(wǎng)絡(luò)規(guī)模增加到一定程度時(shí)，由于地下空間的區(qū)域限制，UAV節(jié)點(diǎn)活動(dòng)范圍有限，網(wǎng)絡(luò)連通性逐漸增強(qiáng)，可構(gòu)建的LLs數(shù)目逐漸減緩，最終出現(xiàn)平均發(fā)送功率的上升趨勢(shì)減緩。該項(xiàng)仿真中，ES算法的優(yōu)化目標(biāo)為單一性能(連通性或時(shí)延，選用連通性)保障下的鏈路損耗最小化，LPCBA由于僅考慮鏈路損耗的最小化而忽略了時(shí)延的優(yōu)化，可達(dá)到該項(xiàng)性能的近似最優(yōu)。
圖5 鏈路損耗性能對(duì)比
圖6進(jìn)一步對(duì)比了本文算法與LPCBA和CG-SW的收斂速度，與LPCBA算法相比，CGG-ATC算法雖然迭代次數(shù)略高，單次迭代所需的時(shí)間復(fù)雜度遠(yuǎn)低于LPCBA算法；與CG-SW算法相比，雖然單次迭代所需的時(shí)間復(fù)雜度相近，但CGG-ATC通過最大權(quán)有向環(huán)搜索大大減少了迭代次數(shù)，能更好地適配快變拓?fù)洹?/p>
圖6 收斂性能對(duì)比
綜上所述，相較于全局最優(yōu)的集中式ES算法，本文算法通過犧牲部分端到端平均時(shí)延、連通性與鏈路損耗性能實(shí)現(xiàn)了高動(dòng)態(tài)場(chǎng)景的適用性；與啟發(fā)式的LPCBA算法相比，本文算法在復(fù)雜度相近的情況下，通過少量連通性與鏈路損耗的犧牲提升了端到端平均時(shí)延；與傳統(tǒng)的聯(lián)盟圖博弈算法CG-SW相比，本文算法實(shí)現(xiàn)了性能的全面提升。
5 結(jié)束語
針對(duì)地下空間災(zāi)后應(yīng)急場(chǎng)景，本文從圖論簡(jiǎn)化、博弈論決策的角度，將圖論與博弈論結(jié)合，把LLs構(gòu)建問題轉(zhuǎn)化為CGG；然后通過BCT簡(jiǎn)化博弈空間，將CGG的效用最大化問題進(jìn)一步轉(zhuǎn)化為圖論中的最大權(quán)有向環(huán)搜索問題，并提出一種MWRS算法搜尋最大權(quán)輪轉(zhuǎn)互操作聯(lián)盟；最后提出一種高效低復(fù)雜度的CGG-ATC算法快速收斂至NSE聯(lián)盟結(jié)構(gòu)。仿真結(jié)果表明，與現(xiàn)有算法相比，本文所提CGG-ATC算法不僅能更好地實(shí)現(xiàn)端到端平均傳輸時(shí)延、拓?fù)溥B通性與鏈路損耗3種性能之間的權(quán)衡優(yōu)化，且具有更快的收斂速度，能夠?qū)崿F(xiàn)高動(dòng)態(tài)場(chǎng)景下的高效自適應(yīng)拓?fù)淇刂?。未來將進(jìn)一步研究災(zāi)后極端環(huán)境下網(wǎng)絡(luò)動(dòng)態(tài)重構(gòu)與確定性調(diào)度方法，為構(gòu)建韌性可重構(gòu)、柔性自適變的地下空間UAV應(yīng)急通信網(wǎng)絡(luò)提供理論基礎(chǔ)和方法支撐。
猜你喜歡
偏序集及其相關(guān)拓?fù)涞倪B通性?湖南文理學(xué)院學(xué)報(bào)(自然科學(xué)版)(2022年4期)2022-10-13 14:03:54 基于通聯(lián)關(guān)系的通信網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法網(wǎng)絡(luò)安全與數(shù)據(jù)管理(2022年2期)2022-05-23 13:25:46 擬莫比烏斯映射與擬度量空間的連通性數(shù)學(xué)物理學(xué)報(bào)(2019年5期)2019-11-29 07:46:26 基于GCC-nearest時(shí)延估計(jì)的室內(nèi)聲源定位電子制作(2019年23期)2019-02-23 13:21:12 電子制作(2018年23期)2018-12-26 01:01:16 基于改進(jìn)二次相關(guān)算法的TDOA時(shí)延估計(jì)測(cè)控技術(shù)(2018年6期)2018-11-25 09:50:10 河道-灘區(qū)系統(tǒng)連通性評(píng)價(jià)研究水利規(guī)劃與設(shè)計(jì)(2017年6期)2017-07-18 10:56:27 勞斯萊斯古斯特與魅影網(wǎng)絡(luò)拓?fù)鋱D汽車維修技師(2017年10期)2017-03-17 02:25:01 FRFT在水聲信道時(shí)延頻移聯(lián)合估計(jì)中的應(yīng)用系統(tǒng)工程與電子技術(shù)(2016年7期)2016-08-21 13:59:18 高穩(wěn)定被動(dòng)群集車聯(lián)網(wǎng)連通性研究通信學(xué)報(bào)(2016年11期)2016-08-16 03:20:04
王博文 孫彥景
(中國(guó)礦業(yè)大學(xué)信息與控制工程學(xué)院 徐州 221008)
(徐州市智能安全與應(yīng)急協(xié)同工程研究中心 徐州 221008)
1 引言
近年來，地下大型綜合體、地鐵、礦井等地下空間規(guī)?；_發(fā)利用造成了地下空間災(zāi)害事故頻發(fā)。當(dāng)塌陷、火災(zāi)、礦井沖擊地壓等地下空間災(zāi)害事故發(fā)生時(shí)，首要的任務(wù)就是實(shí)時(shí)獲取災(zāi)情信息并建立臨時(shí)通信網(wǎng)絡(luò)，為后續(xù)的救援工作提供支撐。我國(guó)地下空間事故應(yīng)急救援體系尚未建立健全，導(dǎo)致地下空間應(yīng)急救援網(wǎng)絡(luò)的研究工作相對(duì)滯后[1]。輕小型、高負(fù)載、高續(xù)航無人機(jī)(Unmanned Aerial Vehicle, UAV) 技術(shù)的突破，使得UAV在地下空間應(yīng)急救援的應(yīng)用成為可能?？仗斓匾惑w化網(wǎng)絡(luò)是6G的核心方向之一，現(xiàn)有關(guān)于6G潛在關(guān)鍵技術(shù)的預(yù)研工作中，明確將災(zāi)后應(yīng)急救援作為6G空天地一體化網(wǎng)絡(luò)的主要應(yīng)用場(chǎng)景[2,3]。
UAV網(wǎng)絡(luò)作為空天地一體化網(wǎng)絡(luò)的重要組成部分，可在地下空間突發(fā)災(zāi)害事故應(yīng)急救援的“探、搜、救”不同階段發(fā)揮關(guān)鍵作用[4]。2018年，應(yīng)急管理部發(fā)布《應(yīng)急管理信息化發(fā)展戰(zhàn)略規(guī)劃框架》，要求整合UAV等空基網(wǎng)絡(luò)資源，實(shí)現(xiàn)對(duì)地下空間等災(zāi)害事故易發(fā)、多發(fā)、頻發(fā)區(qū)域全方位、立體化、無盲區(qū)的災(zāi)情監(jiān)測(cè)與通信覆蓋[5]。如圖1所示，應(yīng)急指揮中心在災(zāi)情探測(cè)階段對(duì)災(zāi)情進(jìn)行推演預(yù)判后，派遣全地形可移動(dòng)的UAV集群深入地下空間對(duì)可疑目標(biāo)點(diǎn)進(jìn)行協(xié)同搜索，攜帶不同類型傳感與通信設(shè)備的UAV終端共同形成UAV應(yīng)急通信網(wǎng)絡(luò)，為后續(xù)的災(zāi)害救援工作提供支撐。
圖1 地下空間災(zāi)后UAV應(yīng)急通信網(wǎng)絡(luò)
與傳統(tǒng)的地面自組織網(wǎng)絡(luò)或智能化自主網(wǎng)絡(luò)相比，其相同之處在于地下空間無人機(jī)應(yīng)急通信網(wǎng)絡(luò)同樣需要分布式自組織的決策能力作為實(shí)現(xiàn)地下空間無人機(jī)集群拓?fù)淇刂频幕A(chǔ)；其不同之處在于地下空間的復(fù)雜不確定性與無人機(jī)節(jié)點(diǎn)的高速移動(dòng)性需要地下空間無人機(jī)應(yīng)急通信網(wǎng)絡(luò)具備無人機(jī)群的群體智能與高效的信息交互能力，并通過更高效快速的群體決策以適應(yīng)快變網(wǎng)絡(luò)拓?fù)洹Ｎ墨I(xiàn)[6]詳細(xì)綜述了UAV集群在礦井應(yīng)急場(chǎng)景中的典型應(yīng)用。文獻(xiàn)[7]針對(duì)災(zāi)后應(yīng)急場(chǎng)景UAV中繼與空中基站兩種典型應(yīng)用中的路徑規(guī)劃與功率控制問題展開研究。上述文獻(xiàn)忽略了UAV集群協(xié)同作業(yè)時(shí)的組網(wǎng)需求，考慮到地下空間災(zāi)害事故具有復(fù)雜繼發(fā)、耦合疊加等特性，具備抗毀、容錯(cuò)性的網(wǎng)絡(luò)架構(gòu)是UAV集群智能與高效任務(wù)協(xié)同的關(guān)鍵。文獻(xiàn)[8,9]詳細(xì)分析了UAV自組網(wǎng)的網(wǎng)絡(luò)特性與拓?fù)淇刂品椒?，?dāng)前有關(guān)UAV組網(wǎng)的相關(guān)文獻(xiàn)主要針對(duì)低動(dòng)態(tài)場(chǎng)景，研究以網(wǎng)絡(luò)持續(xù)連通為目標(biāo)的拓?fù)淇刂?，較少考慮場(chǎng)景的動(dòng)態(tài)不確定性。基于網(wǎng)絡(luò)連通性的拓?fù)淇刂仆ㄟ^功率控制，節(jié)點(diǎn)移動(dòng)控制等措施實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)溥B通。拓?fù)涔β士刂萍赐ㄟ^調(diào)整部分節(jié)點(diǎn)的傳輸功率構(gòu)建遠(yuǎn)程傳輸鏈路(Long-range Links, LLs)，從而獲取更豐富的端到端路徑；節(jié)點(diǎn)移動(dòng)控制通過改變節(jié)點(diǎn)的移動(dòng)軌跡進(jìn)而改善網(wǎng)絡(luò)節(jié)點(diǎn)間的相對(duì)位置，從而獲取期望的連通特性[10]。地下空間災(zāi)后應(yīng)急救援場(chǎng)景UAV節(jié)點(diǎn)移動(dòng)性與搜救、覆蓋任務(wù)緊密關(guān)聯(lián)，因此本文主要通過功率控制實(shí)現(xiàn)網(wǎng)絡(luò)持續(xù)連通性。文獻(xiàn)[11]提出一種基于功率與軌跡聯(lián)合控制的UAV集群自組網(wǎng)拓?fù)淇刂品椒?，但該方法僅能實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)涞膯芜B通性，任意節(jié)點(diǎn)的離開均會(huì)造成連通性失效。考慮到地下空間應(yīng)急場(chǎng)景UAV的易毀性，需要通過更高等級(jí)的連通性確保網(wǎng)絡(luò)的容錯(cuò)抗毀性。
文獻(xiàn)[12]利用塊-割樹(Block-Cut Tree, BCT)提取連通圖中的關(guān)鍵信息，通過構(gòu)建強(qiáng)化邊實(shí)現(xiàn)最小代價(jià)的2-連通性。文獻(xiàn)[13]利用Prim算法搜索BCT中的強(qiáng)化邊，進(jìn)而指導(dǎo)LLs構(gòu)建的方向，實(shí)現(xiàn)UAV自組網(wǎng)拓?fù)鋱D的2-連通性。然而，該方法沒有考慮不同LLs對(duì)于網(wǎng)絡(luò)連通性、鏈路損耗、端到端時(shí)延的差異化影響。在聯(lián)盟博弈(Coalitional Game, CG)中，聯(lián)盟內(nèi)參與者之間的關(guān)聯(lián)性會(huì)對(duì)聯(lián)盟的總效用值產(chǎn)生重要影響[14]。其中，聯(lián)盟圖博弈(Coalitional Graph Game, CGG)將圖論與聯(lián)盟博弈結(jié)合，利用圖中節(jié)點(diǎn)間的關(guān)聯(lián)刻畫效用獨(dú)立關(guān)系，即聯(lián)盟效用與參與者之間的連接方式有關(guān)[15]。因此，可將CG引入時(shí)變拓?fù)鋱D，利用CGG對(duì)LLs構(gòu)建進(jìn)行問題建模，從而實(shí)現(xiàn)多種指標(biāo)的權(quán)衡優(yōu)化，保證網(wǎng)絡(luò)連通性的同時(shí)，提升容錯(cuò)能力。文獻(xiàn)[16]分別提出一種啟發(fā)式LLs構(gòu)建算法與基于轉(zhuǎn)換操作的CGG算法，然而上述算法并沒有考慮連通性的優(yōu)化，且算法復(fù)雜度較高、決策時(shí)間較長(zhǎng)，極易造成組網(wǎng)決策與快變拓?fù)洳黄ヅ洌B通性頻繁失效，不適用于拓?fù)浣Y(jié)構(gòu)隨災(zāi)情演變快速變化的UAV應(yīng)急通信網(wǎng)絡(luò)。
地下空間災(zāi)后特殊的應(yīng)用環(huán)境要求UAV應(yīng)急通信網(wǎng)絡(luò)減少端到端傳輸時(shí)延，保證穩(wěn)定可靠的信息交互與災(zāi)情實(shí)時(shí)回傳。地下空間無人機(jī)集群的拓?fù)浣Y(jié)構(gòu)同時(shí)受到搜救任務(wù)需求、組網(wǎng)決策與有限遮蔽空間結(jié)構(gòu)的影響，如井下巷道狹長(zhǎng)的帶狀空間中，無人機(jī)集群的飛行活動(dòng)受限，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)呈“一”字形。此外，UAV集群在執(zhí)行搜救任務(wù)時(shí)，地下空間災(zāi)害事故的高動(dòng)態(tài)不確定性導(dǎo)致網(wǎng)絡(luò)拓?fù)溲杆僮兓?，連通性頻繁失效，UAV應(yīng)急通信網(wǎng)絡(luò)在滿足機(jī)群間低時(shí)延通信需求的同時(shí)，還需通過保障網(wǎng)絡(luò)的韌性(容錯(cuò)抗毀)與柔性(按需動(dòng)態(tài)重構(gòu))維護(hù)網(wǎng)絡(luò)的持續(xù)連通性，實(shí)現(xiàn)傳輸?shù)倪B續(xù)性，亟需設(shè)計(jì)高效低復(fù)雜度的拓?fù)淇刂品椒▽?shí)現(xiàn)對(duì)拓?fù)渥兓目焖夙憫?yīng)。為此，本文首先將UAV應(yīng)急通信網(wǎng)絡(luò)拓?fù)淇刂茊栴}建模為CGG，然后通過BCT對(duì)時(shí)變拓?fù)鋱D中的關(guān)鍵信息提取，用以指導(dǎo)CGG中決策空間的簡(jiǎn)化與連通性優(yōu)化；最后提出一種分布式低復(fù)雜度的輪轉(zhuǎn)互操作方法得到納什穩(wěn)定均衡(Nash-Stable Equilibrium, NSE)的聯(lián)盟結(jié)構(gòu)。仿真結(jié)果表明，與其他現(xiàn)有算法相比，所提算法能更好地實(shí)現(xiàn)拓?fù)溥B通性、端到端平均傳輸時(shí)延與鏈路損耗3種性能之間的權(quán)衡優(yōu)化，且具有較快的收斂速度，能夠?qū)崿F(xiàn)災(zāi)后動(dòng)態(tài)不確定場(chǎng)景下組網(wǎng)決策與快變拓?fù)涞倪m配。
2 系統(tǒng)模型與問題表述
如圖2所示，將時(shí)變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抽象為一組連續(xù)時(shí)隙的無向圖(G1,G2,...,Gt,...,GT),Gt=(V(t),E(t))表示t時(shí)刻的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，其中V(t)表示點(diǎn)集合，即t時(shí)刻的節(jié)點(diǎn)集合；當(dāng)兩個(gè)節(jié)點(diǎn)處于彼此的一跳通信范圍內(nèi)，在兩個(gè)節(jié)點(diǎn)之間添加一條無向邊，E(t)表示傳輸鏈路集合?？紤]到UAV通信范圍的有限性，網(wǎng)絡(luò)拓?fù)渲腥我鈨牲c(diǎn)大多通過多跳鏈路傳輸，造成了端到端時(shí)延難以保障。UAV應(yīng)急通信網(wǎng)絡(luò)需要把災(zāi)情信息匯聚至接近中心度(Closeness Centrality, CC)最高的節(jié)點(diǎn)uD后，由uD實(shí)時(shí)回傳至地面應(yīng)急指揮中心，則t時(shí)刻整個(gè)網(wǎng)絡(luò)的端到端平均傳輸時(shí)延可表示為
圖2 時(shí)變網(wǎng)絡(luò)拓?fù)鋱D與BCT轉(zhuǎn)化
因此，可通過在距離較遠(yuǎn)的兩節(jié)點(diǎn)之間構(gòu)建LLs的方式建立直連通信，減少ui～uD的跳數(shù)|Hi,D|，進(jìn)而縮短傳輸時(shí)延。在圖論中，k-連通圖是指最少移除k個(gè)節(jié)點(diǎn)后，連通性失效，k為圖的連通度。移除后使單連通圖失效的節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn)，也稱為割點(diǎn)。首先，為了確保式(6)成立，即任一節(jié)點(diǎn)ui與uD間均存在通路，需至少確保網(wǎng)絡(luò)的單連通性，因此本文采用文獻(xiàn)[17]中的集群移動(dòng)模型，該模型既能模擬UAV集群的協(xié)同行為，又能保障兩點(diǎn)間的距離在一跳通信范圍內(nèi)，進(jìn)而保障網(wǎng)絡(luò)的單連通性，避免出現(xiàn)孤立節(jié)點(diǎn)。復(fù)雜地形環(huán)境下的無人機(jī)航路規(guī)劃問題中的避障飛行是核心難題，現(xiàn)有的工作大多將多個(gè)啟發(fā)式算法的優(yōu)勢(shì)進(jìn)行結(jié)合，采用鯨魚算法等新型群體智能算法實(shí)現(xiàn)對(duì)優(yōu)化問題更高效的求解。文獻(xiàn)[18]提出一種改進(jìn)鯨魚優(yōu)化算法，實(shí)現(xiàn)了兩點(diǎn)之間的代價(jià)最優(yōu)的避障飛行。通過對(duì)無人機(jī)節(jié)點(diǎn)與通信鏈路的圖論建模，可用節(jié)點(diǎn)之間的連通性刻畫無人機(jī)的高速移動(dòng)性，因此移動(dòng)模型的選擇僅影響拓?fù)溥B通性變化的頻率。復(fù)雜環(huán)境下可將集群移動(dòng)模型與鯨魚優(yōu)化算法結(jié)合，通過群體感知與信息交互實(shí)現(xiàn)集群避障。此外，移動(dòng)模型的選擇不影響算法性能且縱深較長(zhǎng)的地下空間災(zāi)后應(yīng)急場(chǎng)景，可通過合理設(shè)置飛行高度避障，因此本文主要研究無人機(jī)集群高速移動(dòng)場(chǎng)景下的拓?fù)淇刂茊栴}，重點(diǎn)關(guān)注拓?fù)溥B通性變化頻率。
在單連通圖中，割點(diǎn)UAV的移除與移動(dòng)均會(huì)導(dǎo)致網(wǎng)絡(luò)連通性失效。因此，LLs的建立有助于進(jìn)一步提升網(wǎng)絡(luò)的連通度，從而提升UAV應(yīng)急通信網(wǎng)絡(luò)的容錯(cuò)性與抗毀性，其中容錯(cuò)性與抗毀性表示多跳傳輸鏈路中單一中繼節(jié)點(diǎn)失效時(shí)，可通過其他連通鏈路實(shí)現(xiàn)斷點(diǎn)續(xù)傳，實(shí)現(xiàn)傳輸連續(xù)性。考慮到連通度提升與遠(yuǎn)程鏈路能耗的權(quán)衡，本文擬設(shè)計(jì)滿足基本的2-連通的LLs建立方案，即單一節(jié)點(diǎn)的失效不影響網(wǎng)絡(luò)的連通性。為了實(shí)現(xiàn)拓?fù)涞?-連通，需要添加強(qiáng)化邊消除拓?fù)渲械母铧c(diǎn)，可通過式(3)控制功率構(gòu)建LLs來實(shí)現(xiàn)。
將圖2所示的網(wǎng)絡(luò)拓?fù)渲械母铧c(diǎn)、塊及消除割點(diǎn)的強(qiáng)化邊進(jìn)行標(biāo)記，其中割點(diǎn)所關(guān)聯(lián)的最大2-連通子圖稱為塊，即在該連通子圖中任一節(jié)點(diǎn)的移除不影響連通性且任一相鄰節(jié)點(diǎn)的加入均造成該子圖的2-連通失效。進(jìn)而將左圖中的整個(gè)塊映射為右圖中一個(gè)塊點(diǎn)，將關(guān)聯(lián)同一個(gè)割點(diǎn)和塊點(diǎn)的邊合并，并映射為樹邊，再將關(guān)聯(lián)同一個(gè)割點(diǎn)和同一個(gè)塊點(diǎn)的強(qiáng)化邊合并(如E1與E2可合并為一條邊)，可以將時(shí)變拓?fù)鋱D的非關(guān)鍵信息簡(jiǎn)化，建立右圖所示的BCT?；贐CT，可以判斷每條LLs的構(gòu)建對(duì)于拓?fù)溥B通性的貢獻(xiàn)St(i,j)，S(i,j)為強(qiáng)化邊(i,j)的建立所消除的割點(diǎn)數(shù)，如E1對(duì)于拓?fù)溥B通性的貢獻(xiàn)為1，E3的貢獻(xiàn)為0。此外，強(qiáng)化邊(i,j)的建立往往伴隨著功率的消耗，用Ct(i,j)=c·Pi(t)表示LLs的鏈路損耗，其中c為單位功率下的損耗常數(shù)。
綜上所述，地下空間UAV應(yīng)急通信網(wǎng)絡(luò)中LLs構(gòu)建的優(yōu)化目標(biāo)可表示為端到端平均傳輸時(shí)延、網(wǎng)絡(luò)連通性與鏈路損耗的權(quán)衡優(yōu)化
3 基于聯(lián)盟圖博弈的自適應(yīng)拓?fù)淇刂扑惴ㄔO(shè)計(jì)
3.1 CGG建模
傳統(tǒng)的CG通過合并-拆分準(zhǔn)則將用戶集合分割為多個(gè)不相交的聯(lián)盟，解決用戶分簇、資源分配等問題，實(shí)現(xiàn)所有聯(lián)盟效用函數(shù)的最優(yōu)化。CGG將圖論引入CG，使得聯(lián)盟效用與聯(lián)盟內(nèi)成員的連接方式相關(guān)，即將同一條邊相連的兩點(diǎn)劃分為同一聯(lián)盟。因此，可將LLs構(gòu)建問題抽象為CGG，即將在圖Gt=(V(t),E(t))上建立LLs的兩點(diǎn)劃分為同一聯(lián)盟?；谏鲜龇治觯蓪⒃揅 G G 表示為Gt=(Nt,Xt,Ut)，其中Nt代表t時(shí)刻的博弈參與者，即UAV節(jié)點(diǎn)集合V(t)。Xt為UAV節(jié)點(diǎn)的策略集合，每個(gè)UAV節(jié)點(diǎn)的決策空間為當(dāng)前時(shí)刻除自身外的其他UAV節(jié)點(diǎn)，即通過2元決策變量選擇與其他UAV節(jié)點(diǎn)建立LLs。定義每個(gè)UAV節(jié)點(diǎn)的決策為xi(t)∈Xi(t)，其中Xi(t)={1,2,...,N(t)}為節(jié)點(diǎn)i在t時(shí)刻的可行策略空間。xi(t)可由2元決策變量xi,j,t一一映射，如xi,j,t=1表示xi(t)=j。此外，令x?i(t)=(x1(t),...,xi?1(t),xi+1(t),...,xN(t)(t))表示除xi(t)外其他節(jié)點(diǎn)的策略集集合。為了進(jìn)一步簡(jiǎn)化決策空間，本文通過BCT指導(dǎo)無連通性貢獻(xiàn)節(jié)點(diǎn)的刪減。如圖2所示，對(duì)于塊點(diǎn)B1內(nèi)的節(jié)點(diǎn)1，可通過BCT首先排除與塊內(nèi)節(jié)點(diǎn)建立LLs，再通過強(qiáng)化邊的指向判斷與該塊內(nèi)節(jié)點(diǎn)建立LLs是否有助于消除割點(diǎn)，進(jìn)而縮減每個(gè)節(jié)點(diǎn)的策略集合。
Ut為UAV應(yīng)急通信網(wǎng)絡(luò)中所有節(jié)點(diǎn)的總效用，考慮到無人機(jī)集群的協(xié)同性，在本文所提模型中，所有節(jié)點(diǎn)通過相互協(xié)作共同提升Ut。對(duì)于節(jié)點(diǎn)i，其t時(shí)刻的效用函數(shù)應(yīng)與優(yōu)化目標(biāo)式(7)保持一致。值得注意的是，本文的優(yōu)化目標(biāo)為最小化時(shí)延、損耗與連通性貢獻(xiàn)度3者之間的權(quán)衡值，而CGG的優(yōu)化目標(biāo)一般為效用的最大化，因此效用函數(shù)可表示為
3.2 算法設(shè)計(jì)與性能分析
傳統(tǒng)求解CGG的方法大多采用局部最優(yōu)反應(yīng)(Local Best Response,LBR)策略求得局部最優(yōu)的納什均衡解，但該方法的收斂速度較慢且容易收斂至質(zhì)量較差的局部最優(yōu)解。文獻(xiàn)[16]提出一種基于轉(zhuǎn)換操作的聯(lián)盟博弈算法(Coalition Game algorithm based on SWitch operation, CG-SW)，能夠在有限的轉(zhuǎn)換次數(shù)內(nèi)得到質(zhì)量較好的近似最優(yōu)解。然而，該算法的轉(zhuǎn)換操作僅在兩個(gè)聯(lián)盟間進(jìn)行，忽略了多聯(lián)盟互操作所帶來的收斂速度與求解質(zhì)量?jī)煞矫娴奶嵘?。考慮到頻譜資源的限制以及能量的有限性，假設(shè)t時(shí)刻最多建立M(t)條LLs，本文令M為實(shí)現(xiàn)2-聯(lián)通所需建立的最小強(qiáng)化邊數(shù)。進(jìn)一步地，定義聯(lián)盟集合Πt=(π1,π2,...,πK)，其中Kt=N(t)-M(t)表示最終形成的聯(lián)盟數(shù)目，其中由M(t)個(gè)聯(lián)盟內(nèi)有兩節(jié)點(diǎn)，N(t)-2·M(t)個(gè)聯(lián)盟內(nèi)為單節(jié)點(diǎn)。
本文用(v1→πv2)表示節(jié)點(diǎn)v1離開當(dāng)前聯(lián)盟πv1，轉(zhuǎn)而替換v2加入πv2，即斷開與πv1中與另一節(jié)點(diǎn)建立的LLs轉(zhuǎn)而替換v2與πv2中的另一節(jié)點(diǎn)建立LLs，實(shí)現(xiàn)xi(t)的轉(zhuǎn)換。考慮到單節(jié)點(diǎn)聯(lián)盟與兩節(jié)點(diǎn)聯(lián)盟之間的互操作，可用v1→πv2且?→πv1表示v1加入聯(lián)盟πv2且不替換πv2內(nèi)的任何聯(lián)盟成員。CGG通過聯(lián)盟的劃分得到滿足NSE的聯(lián)盟結(jié)構(gòu)，NSE表示在當(dāng)前的策略集合中不存在任一策略使得聯(lián)盟總效用得到提升，結(jié)合上述輪轉(zhuǎn)互操作聯(lián)盟的定義，可將NSE進(jìn)一步轉(zhuǎn)換為如下定義。
定義2 聯(lián)盟Πt為NSE聯(lián)盟當(dāng)且僅當(dāng)聯(lián)盟間不存在輪轉(zhuǎn)互操作聯(lián)盟。
進(jìn)一步地，用v1→v2表示v1替換v2加入πv2且v2離開πv2，用ΔU(v1→v2)表示該操作所引發(fā)的總效用值變化，則ΔU(v1→v2)可表示為
推論2 CGG-ATC算法能在有限次迭代后收斂至NSE。
證明：由于時(shí)變拓?fù)鋱DGt與有向圖的點(diǎn)集合與邊集合均為有限集合，因此CGG的策略空間有限，又因?yàn)檩嗈D(zhuǎn)互換操作v1→v2→,...,vi?1→vi →v1的性能非減性且消除輪轉(zhuǎn)互操作聯(lián)盟所提升的性能有上界，因此CGG-ATC算法步驟2的迭代次數(shù)有上界。當(dāng)算法收斂時(shí)，代表當(dāng)前聯(lián)盟策略Πt中不存在輪轉(zhuǎn)互操作聯(lián)盟，根據(jù)推論1可證當(dāng)前聯(lián)盟策略Πt為NSE聯(lián)盟。此外，CGG-ATC算法通過BCT進(jìn)一步簡(jiǎn)化了策略空間，因此具有較快的收斂速度。
表1 最大權(quán)輪轉(zhuǎn)互操作聯(lián)盟搜索(MWRS)算法
表2 基于聯(lián)盟圖博弈的自適應(yīng)拓?fù)淇刂?CGG-ATC)算法
4 仿真結(jié)果與性能分析
為了驗(yàn)證上述章節(jié)關(guān)于所提算法理論分析的可靠性，本節(jié)通過數(shù)值仿真對(duì)所提算法的端到端平均時(shí)延、功率損耗、連通性以及收斂性進(jìn)行綜合評(píng)估。本文仿真場(chǎng)景設(shè)置為全長(zhǎng)1000 m、寬200 m、埋深40 m的地下空間，總?cè)蝿?wù)時(shí)長(zhǎng)為10000 s，共劃分為5000個(gè)持續(xù)時(shí)長(zhǎng)為2 s的等間隔時(shí)隙。為了更好地模擬UAV節(jié)點(diǎn)執(zhí)行任務(wù)的協(xié)同性并保障網(wǎng)絡(luò)的連通性，本文采用文獻(xiàn)[17]中的集群移動(dòng)模型，且移動(dòng)模型參數(shù)、能量模型參數(shù)與充電行為參數(shù)的設(shè)置均與文獻(xiàn)[17]保持一致。此外，在通信模型中，單位距離信道增益為η0=-60 dB，路徑損耗系數(shù)為α=2，噪聲功率為–120 dBm，發(fā)送功率范圍為20～30 dBm，SNR閾值γth設(shè)為30 dB，每條鏈路分配的信道帶寬為5 MHz，包長(zhǎng)大小的范圍為1～10 Mbit，控制變量ω1=ω2=ω3=1/3?？紤]到每時(shí)刻開始UAV節(jié)點(diǎn)的位置與進(jìn)退網(wǎng)行為(離開當(dāng)前網(wǎng)絡(luò)到地面站充電或充電結(jié)束回到當(dāng)前網(wǎng)絡(luò))的動(dòng)態(tài)隨機(jī)性，本文采用蒙特卡羅仿真評(píng)估1000次仿真下算法的平均性能。
為了更好地驗(yàn)證所提算法的有效性，本文將以下3種算法作為對(duì)照算法進(jìn)行性能對(duì)比：
圖3–圖6繪制了以上所提算法在1000次仿真下端到端平均時(shí)延、功率損耗、連通性以及收斂性隨場(chǎng)景中UAV節(jié)點(diǎn)數(shù)目變化的情況。其中在收斂性能的評(píng)估時(shí)，由于ES算法復(fù)雜度極高，僅對(duì)比本文算法與LPCBA和CG-SW的收斂速度。
從圖3結(jié)果來看，隨著UAV數(shù)量的增加，網(wǎng)絡(luò)規(guī)模逐漸擴(kuò)大，可構(gòu)建的LLs逐漸增多，CGG-ATC的聯(lián)盟的結(jié)構(gòu)也更加復(fù)雜。隨著任意兩節(jié)點(diǎn)之間跳數(shù)的增加，端到端平均時(shí)延逐漸上升，LLs的構(gòu)建在一定程度上緩和了時(shí)延上升趨勢(shì)。與兩兩聯(lián)盟互換的CG-SW算法相比，本文所提CGG-ATC算法通過多聯(lián)盟的互操作得到更高質(zhì)量的近似最優(yōu)解。
圖3 端到端平均時(shí)延性能對(duì)比
圖4繪制了網(wǎng)絡(luò)連通性隨UAV數(shù)量變化的趨勢(shì)，本文用當(dāng)前網(wǎng)絡(luò)中存在的平均割點(diǎn)數(shù)衡量該性能。由圖4可知即使是可以得到全局最優(yōu)解的ES算法仍會(huì)存在一定數(shù)量的割點(diǎn)，這是因?yàn)閁AV節(jié)點(diǎn)功率上界的限制導(dǎo)致部分LLs無法構(gòu)建。由于CGSW算法僅優(yōu)化端到端平均時(shí)延與鏈路損耗，忽略了網(wǎng)絡(luò)連通性的維護(hù)，導(dǎo)致容錯(cuò)性與抗毀性較差，可能會(huì)由于割點(diǎn)UAV的損壞導(dǎo)致當(dāng)前網(wǎng)絡(luò)拓?fù)鋫鬏斶B續(xù)性難以保障。
圖4 網(wǎng)絡(luò)拓?fù)溥B通性對(duì)比
圖5展示了鏈路損耗隨UAV數(shù)量變化的趨勢(shì)，本文用平均發(fā)送功率來評(píng)估該性能。隨著UAV數(shù)量的增加，可構(gòu)建的LLs逐漸增多，越來越多的UAV節(jié)點(diǎn)通過提升功率來構(gòu)建LLs，但當(dāng)網(wǎng)絡(luò)規(guī)模增加到一定程度時(shí)，由于地下空間的區(qū)域限制，UAV節(jié)點(diǎn)活動(dòng)范圍有限，網(wǎng)絡(luò)連通性逐漸增強(qiáng)，可構(gòu)建的LLs數(shù)目逐漸減緩，最終出現(xiàn)平均發(fā)送功率的上升趨勢(shì)減緩。該項(xiàng)仿真中，ES算法的優(yōu)化目標(biāo)為單一性能(連通性或時(shí)延，選用連通性)保障下的鏈路損耗最小化，LPCBA由于僅考慮鏈路損耗的最小化而忽略了時(shí)延的優(yōu)化，可達(dá)到該項(xiàng)性能的近似最優(yōu)。
圖5 鏈路損耗性能對(duì)比
圖6進(jìn)一步對(duì)比了本文算法與LPCBA和CG-SW的收斂速度，與LPCBA算法相比，CGG-ATC算法雖然迭代次數(shù)略高，單次迭代所需的時(shí)間復(fù)雜度遠(yuǎn)低于LPCBA算法；與CG-SW算法相比，雖然單次迭代所需的時(shí)間復(fù)雜度相近，但CGG-ATC通過最大權(quán)有向環(huán)搜索大大減少了迭代次數(shù)，能更好地適配快變拓?fù)洹?/p>
圖6 收斂性能對(duì)比
綜上所述，相較于全局最優(yōu)的集中式ES算法，本文算法通過犧牲部分端到端平均時(shí)延、連通性與鏈路損耗性能實(shí)現(xiàn)了高動(dòng)態(tài)場(chǎng)景的適用性；與啟發(fā)式的LPCBA算法相比，本文算法在復(fù)雜度相近的情況下，通過少量連通性與鏈路損耗的犧牲提升了端到端平均時(shí)延；與傳統(tǒng)的聯(lián)盟圖博弈算法CG-SW相比，本文算法實(shí)現(xiàn)了性能的全面提升。
5 結(jié)束語
針對(duì)地下空間災(zāi)后應(yīng)急場(chǎng)景，本文從圖論簡(jiǎn)化、博弈論決策的角度，將圖論與博弈論結(jié)合，把LLs構(gòu)建問題轉(zhuǎn)化為CGG；然后通過BCT簡(jiǎn)化博弈空間，將CGG的效用最大化問題進(jìn)一步轉(zhuǎn)化為圖論中的最大權(quán)有向環(huán)搜索問題，并提出一種MWRS算法搜尋最大權(quán)輪轉(zhuǎn)互操作聯(lián)盟；最后提出一種高效低復(fù)雜度的CGG-ATC算法快速收斂至NSE聯(lián)盟結(jié)構(gòu)。仿真結(jié)果表明，與現(xiàn)有算法相比，本文所提CGG-ATC算法不僅能更好地實(shí)現(xiàn)端到端平均傳輸時(shí)延、拓?fù)溥B通性與鏈路損耗3種性能之間的權(quán)衡優(yōu)化，且具有更快的收斂速度，能夠?qū)崿F(xiàn)高動(dòng)態(tài)場(chǎng)景下的高效自適應(yīng)拓?fù)淇刂?。未來將進(jìn)一步研究災(zāi)后極端環(huán)境下網(wǎng)絡(luò)動(dòng)態(tài)重構(gòu)與確定性調(diào)度方法，為構(gòu)建韌性可重構(gòu)、柔性自適變的地下空間UAV應(yīng)急通信網(wǎng)絡(luò)提供理論基礎(chǔ)和方法支撐。
猜你喜歡
湖南文理學(xué)院學(xué)報(bào)(自然科學(xué)版)(2022年4期)2022-10-13 14:03:54
網(wǎng)絡(luò)安全與數(shù)據(jù)管理(2022年2期)2022-05-23 13:25:46
數(shù)學(xué)物理學(xué)報(bào)(2019年5期)2019-11-29 07:46:26
電子制作(2019年23期)2019-02-23 13:21:12
測(cè)控技術(shù)(2018年6期)2018-11-25 09:50:10
水利規(guī)劃與設(shè)計(jì)(2017年6期)2017-07-18 10:56:27
汽車維修技師(2017年10期)2017-03-17 02:25:01
系統(tǒng)工程與電子技術(shù)(2016年7期)2016-08-21 13:59:18
通信學(xué)報(bào)(2016年11期)2016-08-16 03:20:04
