地空異構(gòu)網(wǎng)絡(luò)中無人機輔助的文件協(xié)作緩存算法①

鄭 云,徐哲鑫,陳錦峰,吳 怡

1(福建師范大學(xué) 醫(yī)學(xué)光電科學(xué)與技術(shù)教育部重點實驗室,福州 350117)

2(福建師范大學(xué) 福建省光電傳感應(yīng)用工程技術(shù)研究中心,福州 350117)

每次地震、泥石流等自然災(zāi)害發(fā)生后,災(zāi)區(qū)附近的通信等電力設(shè)施都遭到嚴(yán)重破壞.因災(zāi)后建筑掩埋,短時間內(nèi)難以恢復(fù)通信線路,受災(zāi)人員無法聯(lián)系外界,無法發(fā)送求救信息,因此建立應(yīng)急通信網(wǎng)絡(luò)服務(wù)顯得尤其重要.無人機憑借靈活多變的特性,在救援人員到達前可用其搭載無線設(shè)備進入災(zāi)區(qū),建立應(yīng)急通信架構(gòu),也可通過無人機攜帶或投放無線mesh 路由,在短期內(nèi)保障受災(zāi)人員的通信需求,方便受災(zāi)人員向外界發(fā)送求救信息.災(zāi)區(qū)內(nèi)的文件請求預(yù)測中,大多為災(zāi)區(qū)救援重建以及與親友聯(lián)系的內(nèi)容,通信請求的內(nèi)容重復(fù)性較高,短時間內(nèi)某些文件被重復(fù)請求,產(chǎn)生大量的數(shù)據(jù)冗余.因此需建立地面mesh 緩存功能,減少網(wǎng)絡(luò)內(nèi)的重復(fù)能量消耗與路由開銷,縮短獲取內(nèi)容的時間,同時減輕用于中繼通信的無人機負(fù)載,改善受災(zāi)人員的通信體驗感.目前,無人機和通信設(shè)備資源有限,災(zāi)后短時間內(nèi)無法籌集足夠的設(shè)備,且大部分災(zāi)區(qū)面積大、區(qū)域分散等,故在無線mesh 混合網(wǎng)絡(luò)中選擇簇狀網(wǎng)絡(luò)作為應(yīng)急通信網(wǎng)絡(luò).

在應(yīng)急通信方面,衛(wèi)星、無人機、海岸、艦船、水下可構(gòu)成的一體化應(yīng)急通信系統(tǒng)建設(shè)[1].物聯(lián)網(wǎng)高速公路應(yīng)急救援平臺也可快速獲取事故信息[2].已設(shè)計的電力應(yīng)急現(xiàn)場指揮通信方案優(yōu)化設(shè)計路由協(xié)議[3],開發(fā)出集定位、信息交互的軟件,可移動和可部署資源單元用于災(zāi)難網(wǎng)絡(luò)快速恢復(fù)[4].災(zāi)后應(yīng)急救援網(wǎng)絡(luò)把無人機網(wǎng)絡(luò)與無線mesh 網(wǎng)絡(luò)共同構(gòu)建簇狀網(wǎng)絡(luò)的架構(gòu)[5],使用節(jié)點流量感知的無人機動態(tài)調(diào)度算法,有效提升網(wǎng)絡(luò)吞吐量.對mesh 網(wǎng)絡(luò)節(jié)點布放要求和節(jié)點覆蓋能力進行估算[6].構(gòu)建無線mesh 網(wǎng)絡(luò)內(nèi)部干擾模型[7],驗證無線mesh 節(jié)點休眠策略有效性.優(yōu)化無線網(wǎng)絡(luò)拓?fù)涓采w方案[8],調(diào)整天線的覆蓋角度易于用戶接收信號；增大功率可以增加天線的發(fā)送距離并且保證信號的暢通性.加入衛(wèi)星通信系統(tǒng)在應(yīng)急領(lǐng)域的應(yīng)用[9].基于3G/4G 的應(yīng)急指揮車輛管理信息系統(tǒng)設(shè)計方案可簡化監(jiān)測與維護難度[10].優(yōu)化應(yīng)急通信網(wǎng)絡(luò)架構(gòu)和指揮中心保證前、后方?jīng)Q策部門之間通信無堵塞[11].

在無人機搜尋救治人員方面,提出海上落水傷員救援決策方案[12],對落水傷員搜索定位、傷員傷情監(jiān)測、救援物資投送.建立無人機搜索系統(tǒng)[13],制定短距離通信協(xié)議,獲得野外遇險人員的地理位置.多無人機協(xié)同區(qū)域監(jiān)視的航路規(guī)劃方法[14],使用遺傳算法達到無人機監(jiān)視覆蓋率最大.蟻群算法在災(zāi)區(qū)無人機搜救場景遍歷所有區(qū)域形成封閉環(huán)狀搜救路徑[15].野外生命搜救探測的無人機探測系統(tǒng)利用攝像頭、熱釋電紅外識別系統(tǒng)[16]、雷達生物識別系統(tǒng)對野外遇險人員的準(zhǔn)確定位.具有體征監(jiān)測功能的UAV 搜救系統(tǒng),待搜救人員提前攜帶的救援信標(biāo)機和體征監(jiān)測儀[17],將體征信息通過與無人機的通信鏈路傳給救援中心來實施針對性救援.

在協(xié)作緩存方面,結(jié)合基站緩存容量大小及文件請求的分布[18],構(gòu)造了基于最小時延傳輸?shù)?-1 整數(shù)規(guī)劃最優(yōu)化問題.ICN 方案[19]對數(shù)據(jù)內(nèi)容的流行度分布視圖偏向于緩存不同的數(shù)據(jù)內(nèi)容,減少冗余的緩存.基于用戶偏好下不同緩存容量節(jié)點間的協(xié)同緩存放置策略利用坐標(biāo)下降算法對子問題進行迭代得到近似最優(yōu)解[20].CCPNC 緩存策略對不同流行度的內(nèi)容對象分類緩存[21],調(diào)動網(wǎng)絡(luò)內(nèi)核心路由節(jié)點與非核心路由節(jié)點協(xié)同工作.基于鄰域可用性的協(xié)作緩存策略充分利用節(jié)點的鄰域緩存信息[22],提升系統(tǒng)性能.基于緩存管理的網(wǎng)絡(luò)編碼中繼傳輸方案[23]結(jié)合編碼流速率增加編碼機會,獲得中繼處不同流的緩存閾值實現(xiàn)編碼決策.基于半定松弛的方法來獲得緩存策略在緩存命中率和端到端時延方面具有競爭力[24].協(xié)作組緩存策略選擇具有最低內(nèi)容緩存概率的相鄰節(jié)點作為最佳候選者來減少內(nèi)容冗余[25].

上述研究的角度多種多樣,但是這些沒有考慮災(zāi)區(qū)應(yīng)急通信中無線mesh 路由的協(xié)作緩存與無人機調(diào)度的配合.本文使用Matlab 遺傳算法工具箱,綜合考慮地面無線mesh 路由的協(xié)作緩存與空中的中繼無人機的飛行情況,將無人機作為傳輸中繼與地面mesh路由協(xié)作緩存結(jié)合,提升用戶獲取文件的效率.以中繼無人機轉(zhuǎn)彎角為基因完成軌跡規(guī)劃,協(xié)作緩存以各個地面無線mesh 路由所存儲的文件塊為基因優(yōu)化緩存分布.仿真表明,可將用戶的平均時延收斂在較低水平.

1 系統(tǒng)模型

1.1 系統(tǒng)整體架構(gòu)

基礎(chǔ)設(shè)施破壞嚴(yán)重的情況下,需要使用空中無線設(shè)備,即無人機攜帶通信設(shè)備.又因單個無人機能量與覆蓋范圍有限,故使用多個中繼無人機共同組成聯(lián)合網(wǎng)絡(luò),使得災(zāi)區(qū)通信受損嚴(yán)重的地方得以聯(lián)系外界.本文采用簇狀網(wǎng)絡(luò)結(jié)構(gòu)搭建應(yīng)急通信網(wǎng)絡(luò),即以一個無人機作為簇頭,與地面無線mesh 路由共同組成地面-空中無線mesh 網(wǎng)絡(luò).應(yīng)急通信網(wǎng)絡(luò)的整體組網(wǎng)[5]如圖1所示,整體由分布在受災(zāi)區(qū)域的mesh路由器、外界基站,起到中繼作用的無人機組成.圖中災(zāi)區(qū)整體分為2 個受災(zāi)區(qū)域,每個受災(zāi)區(qū)域按大小分配有一架中繼無人機與6 個無線mesh 路由器,組成區(qū)域內(nèi)的應(yīng)急通信系統(tǒng).區(qū)域內(nèi)無人機起到傳輸中繼作用,向其余區(qū)域或外界請求文件塊,實際上并不緩存.地面無線mesh路由主要緩存文件塊,協(xié)同為用戶提供文件.基站負(fù)責(zé)傳輸中繼無人機請求的文件塊.每個區(qū)域的中繼無人機連接外界基站時,使用一架中繼無人機作為橋梁.

圖1 地面-空中無線mesh 網(wǎng)絡(luò)整體構(gòu)架

本文僅考慮一處區(qū)域的地面-空中無線mesh 網(wǎng)絡(luò)的無線mesh 路由緩存情況與中繼無人機的飛行.借助于中繼無人機節(jié)點的可移動性,僅需確保與部分地面無線mesh 路由連接,減少能量消耗以及路由開銷.

1.2 系統(tǒng)流程

如圖2所示,每個區(qū)域的人員首先連接最近的mesh 路由請求文件,若該mesh 路由一跳與兩跳連接的mesh 路由均未存儲該文件,則通過中繼無人機傳遞請求,向外界的基站或其余區(qū)域的mesh 路由請求該文件塊,然后逐個傳遞回來.以上過程作為中繼無人機與無線mesh 路由不改變下,一個周期內(nèi)用戶請求文件的流程.待下一個周期開始,將上一個周期用戶請求情況輸入,使用遺傳算法計算得出最佳無人機位置與無線mesh 緩存情況,控制無人機飛到指定位置,使用集中式緩存控制對無線mesh 路由器直接進行緩存.

2 基于無人機中繼的mesh 路由緩存策略

2.1 基于遺傳算法的中繼無人機軌跡規(guī)劃

無人機只負(fù)責(zé)作為傳輸中繼,不進行緩存.初始條件為中繼無人機的初始位置和速度,中繼無人機每次飛行的角度小于無人機飛行的最大轉(zhuǎn)彎角.在約束條件下,中繼無人機飛行轉(zhuǎn)彎角選擇下一時刻最優(yōu)結(jié)果.即下一時刻區(qū)域范圍內(nèi)用戶的平均時延最低.然后根據(jù)航路——位置坐標(biāo)公式[14]更新中繼無人機的位置和坐標(biāo),接著重復(fù)以上步驟,更新中繼無人機的位置,直到用戶平均時延收斂.

其中,xE和yE分別為目標(biāo)節(jié)點E的橫坐標(biāo)和縱坐標(biāo)；xA和yA分別為無人機之前的起始點A的橫坐標(biāo)和縱坐標(biāo)；vp為無人機的飛行速度；Δt為固定的時間間隔；α為目標(biāo)節(jié)點E相對于起始點A的位置偏轉(zhuǎn)角；v2為無人機在目標(biāo)節(jié)點E處的速度角度；v1為無人機在之前起始點A處的速度角度；θ為無人機由起始點A飛到目標(biāo)節(jié)點E時速度變化的角度.下一次飛行時,將公式中的目標(biāo)節(jié)點作為此次的起始點,不斷迭代飛行.

圖2 用戶請求流程

將中繼無人機的飛行角度作為基因.中繼無人機可以由轉(zhuǎn)彎角與當(dāng)前的位置速度得出一定時間后無人機的位置與速度,故此處使用中繼無人機的轉(zhuǎn)彎角進行編碼[14]；此種編碼方式保證之后的選擇交叉變異后,得出的新生代種群個體依舊可實現(xiàn)中繼無人機的飛行.中繼無人機約束條件是轉(zhuǎn)彎角大小,設(shè)定無人機飛行的轉(zhuǎn)彎角不大于最大轉(zhuǎn)彎角θmax,即轉(zhuǎn)彎角θ ∈[?θmax,θmax][14].

2.2 基于遺傳算法的無線mesh 路由器協(xié)作緩存

地面無線mesh 路由器主要負(fù)責(zé)緩存,同時可以與兩跳內(nèi)的路由器或中繼無人機傳輸文件.路由器節(jié)點作為主要的緩存設(shè)備,可配備較大的緩存空間.系統(tǒng)采用集中式緩存控制,根據(jù)之前周期區(qū)域內(nèi)的所有用戶的請求情況進行計算后統(tǒng)一緩存,隨著系統(tǒng)運行時間累積以及用戶請求量的增加,系統(tǒng)統(tǒng)計出的文件流行度分布將趨于用戶整體請求分布.另外,采用遺傳算法等啟發(fā)式算法對于請求分布的約束不大,故本文將文件塊流行度設(shè)為經(jīng)典的Zipf 分布[26-28].初始條件為mesh 路由的存放位置,mesh 路由在用戶曾經(jīng)請求過的文件塊集群中選擇文件塊緩存.在約束條件下,地面無線mesh 路由篩選并緩存合適的文件塊,以使下一時刻區(qū)域范圍內(nèi)用戶的平均時延最低.通過不斷迭代更新地面無線mesh 路由的緩存分布,直到用戶平均時延收斂.

遺傳算法中使用緩存的文件塊編碼作為緩存情況的基因,將地面無線mesh 路由所緩存的文件塊作為編碼.地面無線mesh 路由的約束條件設(shè)為同一個mesh路由的緩存空間內(nèi)不能重復(fù)緩存同一個文件,設(shè)備數(shù)為N,每個設(shè)備緩存F個文件,緩存的文件塊編碼為1到NF,即每個設(shè)備的緩存情況為令其緩存編碼為X.

2.3 代價函數(shù)及算法流程

根據(jù)編碼方式初始化種群G,如式(4)所示,S代表種群中的個體數(shù).每一行表示種群中個體的基因,即一種地面無線mesh 路由的協(xié)作緩存情況與中繼無人機的飛行情況,這代表二者協(xié)同考慮,經(jīng)過選擇交叉變異的迭代后,其中的個體越來越優(yōu)秀,適應(yīng)值越來越高,并在最后達到收斂.

適應(yīng)度函數(shù)設(shè)置.地面無線mesh 路由的協(xié)作緩存與中繼無人機飛行情況協(xié)同考慮,目標(biāo)是降低用戶的平均時延.所以使用用戶的平均時延作為適應(yīng)度函數(shù)FIX.

式(5)中,D表示每個用戶的時延,SP表示用戶總數(shù)；HC0表示用戶在連接的mesh 路由上直接取到文件；HC1表示用戶在連接的mesh 路由上經(jīng)過一跳取到文件；HC2表示用戶在連接的mesh 路由上經(jīng)過二跳取到文件；dAM表示用戶取得文件經(jīng)過的距離；dMU表示中繼無人機傳遞給mesh 路由的距離；AU表示用戶在連接的mesh 路由上取不到文件,需要借助中繼無人機取得文件.式中0.1 表示一跳需要經(jīng)歷的額外時延,0.2 表示一跳需要經(jīng)歷的額外時延,0.5 表示通過中繼無人機獲取文件需要的額外時延.因災(zāi)區(qū)建筑遭到破壞,無論救援還是臨時居住地,無線mesh 路由間的障礙較多,故設(shè)定每秒傳輸距離為100 m,因無線mesh 路由與中繼無人機間障礙較少,故每秒傳輸距離為1000 m.

在用戶請求模型中,用戶的位置是均勻隨機分布于區(qū)域內(nèi),連接到距離最近的地面無線mesh 路由,用戶請求的文件按照預(yù)設(shè)的Zipf 分布隨機生成.

遺傳算法中,計算個體適應(yīng)值后,直接把前5%的優(yōu)秀個體作為子代一部分.父代使用隨機遍歷抽樣法,抽取152%的父代個體,經(jīng)過交叉步驟,得到76%的子代個體.父代抽取19%的父代進行變異.最終由選擇交叉變異得到所有的子代個體.交叉操作選擇多點交叉,即在個體編碼串中選擇部分基因段,以間隔交換的方式交換基因.本文設(shè)置6 個地面無線mesh 路由,每個設(shè)備可存儲2 個文件塊,文件塊編碼為1-20.選擇第1、3、5 段基因進行交叉操作后結(jié)果如表1所示.

表1 多點交叉分析表

變異操作選擇單段基因進行變異,如染色體“(2,5),(3,4),(18,1),(20,5),(10,7),0.023”含義為編號為1 的設(shè)備緩存文件塊2 和文件塊5,編號為2 的設(shè)備緩存文件塊3 和文件塊4,以此類推；中繼無人機的轉(zhuǎn)彎角為0.023 rad.某一路由的緩存變異后將重新緩存不同的2 個文件塊.對轉(zhuǎn)彎角進行變異時,轉(zhuǎn)彎角取值范圍為[ ?θmax,θmax],并設(shè)無人機最大轉(zhuǎn)彎角θmax為π/4.

3 仿真與分析

3.1 參數(shù)設(shè)置

如表2所示,仿真區(qū)域范圍設(shè)為280 m×280 m,無人機一般飛行速度為13 m/s 以內(nèi)[5],速度過高會導(dǎo)致無人機難以飛行到起始點附近的位置,故限定為3 m/s.無人機高度均衡用戶通信效果與建筑高度約束,設(shè)為100 m,約30 層樓高.本實驗中6 個地面mesh 路由器的位置分別為(40.2,74.8),(66.6,225.9),(152.8,227.8),(249.6,213.8),(136.2,78.1),(235.1,70.3).無線mesh 路由器的位置均衡通信覆蓋范圍最大[14]與路由器兩跳范圍內(nèi)有盡可能多的路由器.文件塊數(shù)量設(shè)為20,其流行度設(shè)為Zipf 分布,其中參數(shù)α取0.7.設(shè)定使用48 頂應(yīng)急救援帳篷并均勻分布于該區(qū)域,每頂帳篷設(shè)5 人,故用戶數(shù)為240 人.

表2 遺傳算法仿真參數(shù)表

3.2 仿真實驗

仿真實驗中場景示意圖,正方形代表受災(zāi)區(qū)域,圓心代表無線mesh 路由器的坐標(biāo),圓代表無線mesh 路由器的通信范圍.圖中圓心附近的數(shù)字代表該無線路由器所緩存的文件塊編號,如(1,2)表示該路由器緩存文件塊1 與文件塊2.無人機始終從坐標(biāo)(150,150)出發(fā),飛行軌跡以星號表示,軌跡收斂位置為(150,150)小圓圈所在坐標(biāo).

3.2.1 中繼無人機懸停場景下用戶平均時延

單獨考慮緩存情況,中繼無人機位置在(150,150)處,保持原地飛行時,僅地面無線mesh 路由進行協(xié)作緩存,由圖3可知,當(dāng)?shù)恋?0 代時,種群中出現(xiàn)了更加優(yōu)秀的個體,曲線產(chǎn)生跳變,此后用戶的平均時延就已經(jīng)基本位于0.726 s 附近,隨后在第50 代與第70 代分別微小跳變,直到結(jié)束.當(dāng)用戶平均時延相等的最優(yōu)緩存結(jié)果可能不同,由圖4可知協(xié)作緩存結(jié)果.

圖3 中繼無人機懸停場景下用戶平均時延

圖4 中繼無人機懸停場景下協(xié)作緩存示意圖

3.2.2 地面mesh 路由緩存不變場景下用戶平均時延

單獨考慮中繼無人機飛行情況,地面無線mesh 路由的緩存情況為(1,2),(3,4),(5,6),(7,8),(9,10),(11,12)時,保持無線mesh 路由緩存的文件塊不變,僅調(diào)動中繼無人機飛行,結(jié)果如圖5所示,迭代至第11 代時,用戶平均時延開始產(chǎn)生均勻的波動,波動范圍小于0.001,第11 代至第100 代波動仍舊存在且不變.可知,遺傳算法面對有無窮多候選解時,結(jié)果產(chǎn)生小幅度波動.產(chǎn)生這一結(jié)果的原因在于中繼無人機的基因編碼為轉(zhuǎn)彎角,經(jīng)過不斷的迭代,最佳的轉(zhuǎn)彎角基本確定,那么中繼無人機則會按照轉(zhuǎn)彎角進行近似圓軌跡飛行,在用戶平均時延上則體現(xiàn)為周期性波動.如圖6及圖7所示,無人機從坐標(biāo)不斷轉(zhuǎn)彎飛行,最后盤旋飛行,軌跡為橢圓形,體現(xiàn)在圖5上為不斷波動的平均用戶時延,在坐標(biāo)(124,175)處為用戶平均時延最低,為1.113 s.

圖5 地面mesh 路由緩存不變場景下用戶平均時延

圖6 地面mesh 路由緩存不變場景下結(jié)果示意圖

3.2.3 中繼無人機飛行且地面mesh 路由協(xié)作緩存場景下用戶平均時延

同時考慮中繼無人機飛行加上地面無線mesh 路由的緩存情況,中繼無人機起始點設(shè)為(150,150),如圖8所示,曲線呈階梯下降趨勢.最終用戶平均時延收斂于0.72.如圖9及圖10所示,無人機處于盤旋狀態(tài).

圖7 中繼無人機飛行軌跡圖

圖8 中繼無人機保持飛行且地面mesh 路由協(xié)作緩存場景下用戶平均時延

圖9 中繼無人機飛行且地面mesh 路由協(xié)作緩存場景下示意圖

3.2.4 不同初始種群下所收斂的用戶平均時延

同時考慮中繼無人機飛行加上地面無線mesh 路由的緩存情況,設(shè)置不同的初始種群,觀察它們的結(jié)果,如圖11所示,在10 個初始種群種內(nèi)用戶平均時延收斂結(jié)果波動在0.008 范圍內(nèi),在一定程度上可認(rèn)為遺傳算法迭代結(jié)果近似于最優(yōu)解.如表3所示,每一行代表一種收斂情況,第一種收斂情況中,路由器1 表示編號為1 的路由器緩存文件塊1 和文件塊5,以此類推.橫坐標(biāo)x及縱坐標(biāo)y表示中繼無人機的最終位置坐標(biāo),第一種收斂情況中無人機最終坐標(biāo)為(135.2,146.8).路由器緩存結(jié)果各異,中繼無人機位置亦不同,故收斂的結(jié)果未必一致.

圖10 中繼無人機飛行軌跡圖

綜合上述仿真結(jié)果分析可得,無論是單獨考慮緩存情況,中繼無人機保持不動,或是單獨考慮中繼無人機飛行情況,地面無線mesh 路由的緩存情況不變,亦或二者都發(fā)生改變,不論何種,在遺傳算法的迭代下,用戶平均時延均呈現(xiàn)下降趨勢.但僅考慮緩存改變的情況下平均用戶時延為0.726 s,僅考慮中繼無人機飛行時,用戶平均時延為1.113 s,二者都考慮時,用戶平均時延為0.72 s,顯然,綜合考慮地面無線mesh 路由緩存與中繼無人機調(diào)度,對用戶體驗的提升更為明顯.觀察各個無人機軌跡圖,可知待時延趨于收斂時,無人機飛行角應(yīng)基本不變,軌跡近圓形.不同種群迭代收斂結(jié)果有一定波動,但相差不大,在一定程度上可認(rèn)為遺傳算法對求解問題有積極意義.

圖11 不同種群收斂的平均用戶時延

表3 不同初始種群的迭代收斂結(jié)果

4 總結(jié)與展望

本文從災(zāi)后通信設(shè)施遭到破壞,人員難以發(fā)送求救信息與居民對外通信受到影響的角度出發(fā),研究地面與空中的混合mesh 網(wǎng)絡(luò),以及地面無線mesh 路由器協(xié)作緩存,作為傳輸中繼的無人機飛行情況.本文重點考慮災(zāi)后通信的mesh 網(wǎng)絡(luò)組建后,無線mesh 路由的協(xié)作緩存與傳輸中繼無人機的飛行情況,使用遺傳算法保證區(qū)域內(nèi)用戶取得文件的平均時延收斂在較低水平.通過設(shè)置不同的初始種群,判斷遺傳算法結(jié)果是否為最優(yōu)解.后續(xù)研究將同時考慮多個中繼無人機的情況,研究多個區(qū)域的通信情況.目前僅采用遺傳算法,后續(xù)可以多采用幾種算法比較,如退火算法,深度強化學(xué)習(xí),比較它們的運行時間、準(zhǔn)確度、收斂性等因素.