城市災區無人機網絡自適應覆蓋優化算法

王 巍，梁雅靜，劉 陽，洪慧君

1.河北工程大學 信息與電氣工程學院，河北 邯鄲 056038

2.河北省安防信息感知與處理重點實驗室，河北 邯鄲 056038

3.江南大學 物聯網工程學院，江蘇 無錫 214122

近年來，每年都會有自然災害發生，例如地震、颶風、火山爆發以及海嘯等。而城市地區因其人口眾多，建筑密集，在災害發生后會受到極其嚴重的損害。突發事件的發生使得城市地面通信基礎設施極易處于擁塞癱瘓狀態或者遭到嚴重毀壞，進一步導致城市災區的環境信息以及救援信息無法得到有效傳輸，進而影響救援行動的有效實施。經研究，災后的72小時是“黃金救援時間”，因此，災后的緊急救援是挽救生命的重要過程[1]。在此期間，救援人員之間的通信以及城市中遇難者的位置信息等是極其重要的，他們需要共享信息來了解更多的災區情況以便更高效地完成救援任務，挽救更多的生命，減少損失。

隨著無人機相關關鍵技術的突破，無人機集群組成的無人機網絡能夠對監測環境進行信息采集、處理和發送，并被廣泛運用于應急通信、環境監控、軍事偵察、物流等領域[2-3]。無人機網絡因其移動性靈活、自主性強等特點，在應急通信領域發揮著越來越重要的作用。其中，覆蓋率是衡量無人機網絡性能的一個重要因素，因此城市災區的網絡覆蓋優化問題成為重要的研究熱點之一。

針對城市災區無人機網絡覆蓋優化的研究，文獻[4]對災區進行模擬得到三維立體圖以及重點區域，對A*算法進行優化，提高了無人機的巡查覆蓋率，但并非網絡覆蓋率。文獻[5]針對城市地震場景，提出一種自適應反饋遺傳算法，但目的是優化任務規劃，并非對網絡的覆蓋優化。文獻[6]研究了城市環境下無人機的軌跡規劃問題，重點優化的是無人機的行動軌跡。文獻[7]提出了一種兩階段優化算法來為城市地區提供無縫的長期覆蓋，但重點是對能源消耗的優化。文獻[8]介紹了一種新型的無人機輔助路由協議，重點對城市環境下的無人機網絡通信服務質量進行優化，但不適用于災害發生的場景。文獻[9]提出了一種改進的自適應車輛跟蹤算法，優化無人機對地面車輛的動態追蹤，但并不適用災區環境。文獻[10]集中于對城市災區的研究，提出了一種無人機在災難場景下進行戰術動作的智能策略。結合了Jaccard距離以及模擬退火算法對地面用戶進行動態覆蓋。這個策略在保證網絡連通的情況下，最大化了無人機服務的受害者的數量。但是還存在較多處在角落的節點未被覆蓋。

針對以上算法的不足，為了對城市災區環境下重點區域的移動地面用戶節點進行覆蓋優化，本文首先對城市災區的節點移動進行模擬，通過模型獲得城市災區中的參數。其次，對布谷鳥算法進行改進，融入從模型中獲得的參數，引入虛擬力對布谷鳥算法的位置更新方程進行調整以保證網絡的連通性，并引入權重系數對目標函數進行歸一化以提高重點區域的覆蓋率。結果表明，該算法適用于城市災區移動節點的覆蓋優化，且在維持網絡連通性的情況下重點提高了無人機網絡對重點區域的覆蓋率。

1 城市場景模擬

本文重點研究無人機網絡對城市災區的通信覆蓋優化問題。而我國城市數量眾多，且城市的人口、面積懸殊，建筑物特征、布局各異。而建筑物功能分類結果可作為推測建筑物內人口密度的依據，服務于配套設施的規劃和緊急情況的應對[11]。因此，在對城市災區進行應急通信網絡覆蓋之前，需要先對城市場景進行模擬。

設待覆蓋城市區域A為二維平面，則A?B,R,P,X，其中B為建筑物，R為道路，P為公園等開放性區域，X為禁止區域（人類無法進入的區域、湖泊、河流等）。文獻[11]通過計算不同類型的興趣點（POI）的加權來識別地圖中的建筑物功能類型，并將建筑物劃分為8類。則建筑物集合B?B1,B2,…,B8，其中B1～B8分別代表居住建筑、公共建筑、商業建筑、商公混合建筑、住公混合建筑、商公混合建筑、其他。文獻[12]以景觀視角將城市的道路劃分為6類，分別為快速通過型道路、穿越通過型道路、景觀旅游型街道、符合共享型街道、居民生活型街道和景觀休閑步行路，則道路集合R?R1,R2,R3,R4,R5,R6。

由于某校區總體空間布局滿足城市空間布局的集中式總體布局特征，因此本文基于文獻[13]提出的城市災區地面用戶節點移動模型，以該校區為例進行建模。公共類建筑，像醫院、學校等較大規模的公共服務機構呈現組團模式的聚集分布[11]。因此該學校區域建筑集合Bs?B1,B2,道路集合Rs?R1,R2,其中，B1,B2?B,R1,R2?R。

根據以上描述對模擬區域進行區域劃分，由于模擬區域中的某些道路兩旁有較大面積的草坪覆蓋，當地震發生后，地面用戶節點可以在草坪上隨機移動，因此本文將此類道路和草坪共同劃分為開放性區域。且由于學校的特殊性，學校的居住建筑以及公共建筑都會有一定的用戶節點分布，因此本文將居住建筑和公共建共同劃分為建筑區。區域劃分情況如圖1所示。

圖1 實際區域劃分情況Fig.1 Actual area division

節點在開放性區域遵循隨機游走（random）的移動規則，會隨機改變速度和方向；在建筑區域中，節點隨機產生四個方向，向建筑區的邊界移動并最終移動到出口，本文將此移動規則定義為B-trend；在街道上，節點線性移動（linear），當街道由于建筑殘骸而被封鎖時節點停止移動，由于節點在街道以及道路在被封鎖之前都是線性移動的，因此本文中街道以及被封鎖的道路采用同一個區域，道路被封鎖通過節點停止移動來體現；本文中的禁止區域是指學校中的湖泊以及無法進入的區域；當地震發生后也可能會發生余震使建筑物坍塌（B-col）的突發情況，此時地面用戶節點被困在區域中，通過使節點消失（fade）來模擬這一情況。

由于學校內建筑特征的不同，受災區域的位置不同，導致不同區域內地面用戶節點的移動規則有所差異，因此本文通過限制節點的移動來實現對城市災區的不同區域類型的模擬。根據待覆蓋區域As內建筑物類型以及道路類型，相應區域內隨機分布有對應密度的地面用戶節點。整個區域內分布的用戶節點的總個數為n，節點集合為G={g1,g2,…,gn}，則節點gi(i=1,2,…,n)所遵循的移動規則如下所示：

2 算法實現

2.1 布谷鳥算法描述

布谷鳥搜索算法（CS）是一種基于巢寄生性以及萊維（Levy）飛行搜索機制的群體智能優化算法。該算法精度較高、復雜度較低、穩定性較好[14]。算法的實現需設定3個理想規則[15]：

（1）每只鳥一次只產一個蛋，并隨機在一個宿主鳥巢中孵化。

（2）從隨機選擇的一組鳥巢中，最好的高品質鳥巢保留到下一代。

（3）可利用的宿主鳥巢的數量n是固定的，一個鳥巢的主人能發現巢中的蛋是外來蛋的概率是Pa，且Pa∈[0,1]。當宿主發現是外來鳥蛋時，會將蛋丟棄或者重新尋找位置來建立新的鳥巢。

基于以上3個理想規則，算法迭代過程中鳥巢的位置更新公式如下：

步長因子α的表達式為：

式中，α0為常數，zbest表示當前的最優解。萊維飛行L(β)的表達式為：

式中，μ和υ均服從標準高斯分布。且φ滿足：

結合公式（1）、（2）和（3），可推導出鳥巢的位置更新公式為：

2.2 布谷鳥搜索算法的改進

傳統的布谷鳥算法對無人機網絡的覆蓋優化，是將地面用戶節點視為靜止節點，不能保證網絡的連通性，并且覆蓋優化的區域是整個目標區域。文獻[16]對熱點區域進行確定，并對布谷鳥算法進行改進，提高了無人機網絡對熱點區域的覆蓋率，但作者并未考慮地面用戶節點的移動性，且適應場景為非城市災區。

在實際的城市災區，地面用戶節點為移動節點，當無人機網絡拓撲結構穩定不變時，隨時會有節點遠離無人機網絡的覆蓋區域，當處于網絡覆蓋區域外的節點過多時，無人機網絡無法對其進行覆蓋。因此本文首先針對災區地面用戶節點的移動特性，對布谷鳥算法的位置更新方程進行改進，以實現無人機網絡對災區的自適應覆蓋，但基于此步改進，并沒有保證無人機網絡的連通性，且可能會出現覆蓋重疊的情況。

針對第一步改進出現的弊端，為了維持無人機網絡的連通性，在改進的基礎上引入虛擬力對位置方程進行調整，當無人機節點為非連通節點時采用引力，當無人機節點為連通節點時，判斷無人機節點間的距離，當距離小于某一閾值時，則采用斥力。

在本文提出的災區地面用戶節點移動模型中，節點并非分布于整個區域，因此無人機網絡只需對用戶節點活動的區域覆蓋即可。基于此，本文對布谷鳥算法的目標函數進行加權優化，引入加權系數，在一定程度上犧牲其他區域的覆蓋率，重點優化用戶節點活動區域的覆蓋率。具體改進如下。

2.2.1 位置更新方程的改進

采用傳統的布谷鳥算法部署無人機網絡，隨著算法迭代結束，無人機網絡拓撲結構趨于穩定，其所覆蓋的地面區域也將恒定不變。而由于受災區域內地面用戶節點的移動特性，當某些用戶節點隨時間變化逐漸移動出應急網絡的覆蓋區域時，將無法獲得用戶節點的相關信息，對應急救援任務帶來不便。因此為了實現無人機網絡的自適應覆蓋，本文通過城市災區人員的移動模型獲得各個時刻地面用戶節點的坐標位置并作為布谷鳥算法的輸入。由于在本文所提出的城市災區的節點移動模型中，各個分區域的內節點移動規則是一致的，除開放性區域，節點最終將分布在某一區域處。因此考慮到無人機網絡的能耗，無人機i選擇當前時刻與其水平距離最近的用戶節點位置方向移動即可覆蓋該區域處多個用戶節點。

首先計算當前時刻所有地面用戶節點與無人機節點集S之間的水平距離，將得到距離矩陣如下：

其中，n為無人機的個數，p為地面移動節點的個數。計算該矩陣每列的最小值以及最小值所在行數即可獲得距離無人機節點集水平距離最小的節點坐標集。計算無人機i與其水平距離最近的節點的坐標差值(Δxi,Δyi)，通過計算得出無人機節點的橫縱坐標改進距離如下：

結合公式（5）和公式（7）可得當前時刻改進的布谷鳥算法的位置更新方程為：

2.2.2 虛擬力向導的布谷鳥算法調整

根據公式（9）的位置更新方程，無人機節點向當前時刻與其水平距離最近的節點移動，可能會出現多個無人機的下一目標位置坐標相近的情況。由于城市災區的建筑特征，部分地面用戶節點分簇分布，當簇與簇之間的距離過大，會導致無人機網絡不連通。因此，為了維持無人機網絡的連通性，本文引力虛擬力對位置更新方程進行調整。

對于任意兩個無人機節點si、sj，節點間的歐式距離為。計算所有無人機節點間的歐氏距離，獲得距離矩陣如下：

矩陣中的對角線元素0表示無人機節點與自身的距離，因此為了方便計算，將對角線的0設置為無窮大，獲得距離矩陣為：

其中，θij表示力的方向，和ωr分別表示引力系數和斥力系數。由于本文假設所有無人機的基本參數相同，因此定義距離閾值為dth=2r[17]，其中r為無人機的通信半徑。

計算無人機si受到區域內所有其他無人機節點的虛擬力的合力為：

定義Fth為虛擬力的閾值，當無人機i所受虛擬力合力大于虛擬力的閾值時，對無人機的位置坐標進行更新，否則無人機i將在該位置保持懸停。因此，虛擬力向導的無人機i的改進距離為：

其中，Fix為無人機i在x軸方向上的受力，Fiy則為無人機i在y軸方向上的受力。由此，結合公式（8）和公式（11），虛擬力向導的布谷鳥算法的位置更新方程為：

2.2.3 加權優化目標函數

本文模擬的學校區域中存在一些禁止區域，地面用戶節點在整個模擬過程中都無法進入該區域，為了避免產生過多覆蓋冗余，本文將地面用戶節點分布的區域視為重點區域，引入加權覆蓋率，在優化覆蓋的過程中需重點提高無人機網絡對重點區域的覆蓋。

無人機網絡為地面用戶提供通信覆蓋，為了更好地研究覆蓋優化問題，本文將待覆蓋區域A數字離散化為a×b個像素點。覆蓋率定義為被覆蓋的像素點的數量與區域A內總像素點數量之比。假設有num個像素點被無人機網絡覆蓋，則無人機網絡的覆蓋率為num/(a×b)。

在目標區域A中，有m個地面用戶節點，節點集合為G={g1,g2,…,gm}；有n個無人機節點，節點集合為S={s1,s2,…,sn}。第i個無人機節點si的位置坐標為(xi,yi,hi)，設像素點j的位置坐標為(xj,yj,0)。則無人機節點si與像素點j之間的水平距離為：

本文采用文獻[18]提出的A2G信道模型，則像素點j和無人機i之間的視距通信（LoS）鏈路概率為：

其中，α和β是環境參數，數值設置與城市的建筑物密度有關[19]。hi為無人機si的飛行高度。此外，非視距通信（NLoS）鏈路的概率為：

由于城市背景復雜，且存在大量的噪聲和干擾[20]。因此，在城市災區，無線傳播信號除了自由空間傳播損耗之外，還有因建筑物遮擋和散射產生的損失。因此，無人機si與像素點j之間的LoS和NLoS鏈路損失模型[17]分別為：

其中，fc為載波頻率；ηLoS和ηNLoS分別為視距通信鏈路和非視距鏈路下的額外路徑損失；c為光速；dij為無人機si與像素點j之間的距離：

因此，在LoS和NLoS模型下，無人機si與像素點j之間A2G的鏈路平均路徑損失為：

為了保證服務質量，像素點j的接收功率必須超過一定的閾值，也就是說，像素點j與無人機si之間的鏈路損耗小于或等于某一個閾值PLmax時，像素點j被無人機si覆蓋，即：

則像素點j可被無人機節點si感知的概率為：

任一像素點都可同時被多個無人機節點感知，因此像素點j被無人機節點集合S感知的聯合概率表示為：

因此，無人機網絡對整個目標區域的覆蓋率為：

同理，將地面移動節點視為像素點可得無人機網絡對重點區域的覆蓋率為：

本文重點研究無人機網絡對重點區域移動節點的覆蓋優化，為此可以在某種程度上犧牲禁止區域的覆蓋率。因此本文引入加權覆蓋率對整體目標區域覆蓋率和重點區域覆蓋率進行歸一化計算：

其中，ω1為目標區域整體覆蓋率的加權系數，ω2為重點區域覆蓋率的加權系數且ω1?ω2。

由此，改進的布谷鳥算法的優化目標函數為：

2.3 算法步驟

改進的布谷鳥搜索算法具體步驟如下：

（1）參數初始化，設置種群個數、鳥巢個數以及初始鳥巢位置、發現概率Pa、最大迭代次數等。

（2）根據公式（29）計算初始目標函數值f(x)，并保留適應度值最大的鳥巢位置到下一代。

（3）根據位置更新公式（15）更新鳥巢位置。

（4）根據新的鳥巢位置，計算目標函數值f(x)，并保留適應度值最大的鳥巢位置到下一代。

（5）產生一個隨機數r,比較r與Pa的大小，若r＞Pa,則返回步驟（3）。

（6）當算法達到最大迭代次數或適應度函數值不再發生變化時，結束進程。否則，返回步驟（3）。

算法的具體步驟流程圖如圖2所示。

3 仿真與結果分析

3.1 實驗環境

本文在Windows10系統下，基于MATLAB2014a軟件對提出的算法進行仿真，仿真的區域采用的是某校區平面圖，近似為正方形區域，正方形區域內用戶節點隨機分布在學校的不同可活動區域。

圖2 改進的布谷鳥算法步驟流程圖Fig.2 Improved cuckoo algorithm step flow chart

3.2 實驗參數設置

待覆蓋區域是二維（2D）的，平面圖近似為1 000 m×1 000 m的矩形區域。每個可活動區域都隨機分布有一定數量的地面用戶節點，用戶節點的總數量為m。地面用戶節點的移動速度為vg，在整個目標區域中，每個劃分區域內的節點速度都會隨機改變。最大速度代表地面用戶節點正在從危險區域逃出，或在尋求幫助。靜止節點或者以最小速度移動的節點，代表該節點因受傷或周圍環境惡劣而行動困難。

無人機節點個數為n，初始時隨機分布在整個目標區域，其移動最大步長為Dmax；所有無人機都在相同高度h的上空盤旋，并以恒定的速度vuav移動；所有無人機的無線傳輸范圍均為r，可以覆蓋以無線傳輸范圍R為半徑的地面圓形區域，且在通信范圍內，無人機之間可以相互通信[7]。算法的最大迭代次數為tmax。具體的實驗參數設置如表1中所示。

表1 實驗參數Table 1 Experiment parameter

3.3 實驗仿真

3.3.1 城市災區節點移動

根據所劃分區域的面積以及所屬類型，放入相應數量的用戶節點。初始時，所有用戶節點都是隨機分布的。圖3是移動模型程序運行500 s時，用戶節點在目標區域的分布情況。由圖中可以看出，在開放性區域，節點遵從隨機游走移動規則，最終的節點分布情況是隨機分布；在建筑區，節點最終聚集在邊界區域或出口處，其中未在邊界處的節點可能因建筑殘骸擁堵或受傷而行動緩慢；在被封鎖的街道區域，節點最終停止在街道封鎖處；而在禁止區域，無用戶節點進入。

圖3 500 s時節點分布情況Fig.3 Distribution at 500 s

在地震發生后的應急救援過程中，可能會有余震的發生而造成新的建筑物坍塌。此時，該區域內的用戶節點會被困在建筑殘骸中而失去信號，導致無人機網絡無法獲知地面用戶節點的位置信息。可通過使相應區域內用戶節點的消失來模擬這一情況[12]，如圖4所示。對比圖4（a）和（b）可發現，目標區域內，有兩個分區域內的用戶節點消失，即該兩處區域發生了余震導致建筑物坍塌，用戶節點被困其中。

3.3.2 網絡覆蓋情況

為了驗證本文方法的有效性，采用本文所提出改進布谷鳥算法對第1章提出的城市環境災后地面用戶節點移動模型進行覆蓋優化，并進行500次獨立實驗驗證。實驗結果如圖5所示。

圖5（a）為初始狀態，地面用戶節點以及無人機節點隨機分布在目標區域。為了更清楚地展示算法覆蓋效果，圖5（b）及圖5（c）為將區域的劃分邊界去掉的效果圖。圖5（b）為程序運行到100 s時的實驗結果，由圖中可以看出，建筑區域內的用戶節點逐漸在向建筑區的邊界移動，開放性區域的節點，因其遵從隨機游走的移動規則，依舊是隨機分布。而無人機網絡的拓撲結構已隨著地面用戶節點的移動發生變化。圖5（c）為程序運行到500 s時的實驗結果。由圖中可以看出，建筑區域內的節點在建筑區的邊界以及出口處聚集，無人機網絡幾乎覆蓋了災區內的所有地面用戶節點，且對禁止區域的覆蓋率較小，以及保持了網絡的連通性。

圖4 余震情況模擬圖Fig.4 Simulation of aftershocks

對比圖5（a）和（b），圖5（a）和（c）可以看到采用本文所提算法，無人機網絡對重點區域的覆蓋率得到了提高。對比圖5（a）、（b）和（c）可以看出隨著地面用戶節點的移動，無人機網絡的拓撲結構也隨著發生變化，且無人機網絡對禁止區域的覆蓋逐漸減少。

3.4 實驗評價方式

為了評價本文城市災區無人機網路自適應覆蓋優化算法的優劣，引入了覆蓋率、網絡連通度和路徑損耗三種評價指標。其中覆蓋率為公式（26）中的全局覆蓋率以及公式（28）中的加權覆蓋率；網絡連通度為無人機網絡節點中所有節點直接通信范圍內的節點個數的算數平均值；路徑損耗為地面用戶節點的平均路徑損耗。為了對比不同城市環境參數α、β的設置下，本文所提算法的性能，分別在α=0.1,β=750、α=0.3,β=110,以及α=0.5,β=300的情況下進行10次實驗，記錄10次實驗同一時刻的結果，分別對比三組城市環境參數下三種評價指標的變化情況。其中，α=0.1,β=750代表稀疏城市，相當于郊區；α=0.3,β=110是本文的環境設置；α=0.5,β=300代表密集城市[19]。由于本文是針對城市災區地面移動用戶的通信覆蓋，而在實際情況下，郊區的地面用戶節點較少，且空曠區域較多，節點分布比較稀疏，而密集城市中，建筑物比較密集，用戶節點密度大，因此為了方便比較，本文的郊區環境和密集城市環境是同本文的城市環境相同大小的區域，其中郊區分布有150個隨機移動的節點，密集城市分布有400個節點，節點移動采取本文城市災區用戶節點的移動規則。

圖5 各時刻網絡覆蓋情況Fig.5 Network coverage at different times

其次為了評價本文算法的全局尋優以及局部尋優能力，引入6種多峰測試函數，并且為了更直觀地體現本文算法的優劣性，分別采用標準布谷鳥算法（CSA）、灰狼算法（GWO）、烏鴉算法（CS）與本文算法對函數求最優值并獲得函數的進化曲線。

若三種評價指標的變化幅度在適當范圍內，且算法的局部尋優以及局部尋優能力優于其他算法，則證明本文所提出的算法有較好的應用價值。

3.5 實驗結果和分析

3.5.1 實驗評價結果

（1）全局覆蓋率和加權覆蓋率

分別記錄三組參數下10次實驗中全局覆蓋率和加權覆蓋率的值，對比結果如圖6所示。由于本文的郊區環境中節點是隨機移動的，因此不存在重點區域，即不存在加權覆蓋率。由柱狀圖可以清晰地看出，郊區環境下的覆蓋率最低，這是由于地面節點分布稀疏，無人機需要飛到更高的高度對用戶節點進行覆蓋，由此造成了更多的路徑損耗。而密集城市環境下的覆蓋率略低于本文城市災區下的覆蓋率，這是由于密集城市建筑物遮擋和散射造成了更多的鏈路損耗。

圖6 覆蓋率對比圖Fig.6 Coverage comparison chart

但三種環境參數下的全局覆蓋率和加權覆蓋率都穩定在一定的范圍內，且每次實驗的加權覆蓋率值都高于全局覆蓋率值。說明采用本文所提方法優化后的無人機網絡的覆蓋率較為穩定，提高了無人機網絡對目標區域中重點區域的覆蓋率，且更加適用于城市環境。

（2）網絡連通度

為了衡量應用本文方法后無人機網絡的連通性，采用連通度指標對該方法進行評價。圖7為三組城市環境參數下分別進行10次實驗后，相同時刻的無人機網絡的連通度值變化曲線。由折線圖可以清晰地看出，三種環境參數設置下的實驗結果中，相同時刻的無人機網絡的連通度變化相差都不大，這是由于本文算法引入了虛擬力保證了網絡的連通性，說明應用本文方法在不同的城市參數下無人機網絡連通性能穩定。

圖7 網絡連通度變化曲線Fig.7 Change curve of network connectivity

（3）用戶路徑損耗

圖8為相同實驗參數設置下，在三組實驗環境參數設置下，10次實驗后，相同時刻的用戶路徑損耗情況。由圖中可得，郊區環境下90%左右的地面用戶節點的路徑損耗在閾值（85 dB）以下，有10%左右的節點的路徑損耗超過了閾值，說明該時刻只有90%左右的節點被覆蓋。而在本文的城市災區環境中只有5%左右的地面用戶節點的路徑損耗超過了閾值，有95%左右的節點被覆蓋。密集城市環境中有7%左右的節點未被覆蓋。說明無人機網絡能夠更適用于為城市環境中地面用戶節點提供應急通信，且網絡質量穩定。

圖8 不同路徑損耗的用戶比例Fig.8 Proportion of users with different path loss

（4）網絡的動態覆蓋性能

由于本文所提方法是針對城市災區移動的地面用戶節點的網絡覆蓋優化，因此為了衡量無人機網絡的動態覆蓋性能，分別記錄三組城市環境參數下實驗中不同時刻三種評價指標的值。由于以上針對三種評價指標的實驗結果表明，無人機網絡的性能相對穩定。因此，此部分分別記錄三種環境參數下一次實驗中不同時刻三種評價指標的值。由圖9中可以看出，環境參數密集城市的覆蓋率以及平均路徑損耗均略差于α=0.3,β=110時的情況，這是由于密集城市環境下的建筑物遮擋及散射更多，而郊區環境的覆蓋率最低，且路徑損耗最多，說明本文所提方法更適應于對城市災區的通信進行覆蓋優化。而隨著時間變化，三種城市環境參數下的無人機網絡的加權覆蓋率、網絡連通度以及地面用戶節點的平均鏈路損耗變化穩定，說明無人機網絡的動態覆蓋性能較好。

圖9 評價指標隨時間的變化情況Fig.9 Change of evaluation index with time

（5）全局和局部尋優能力

由于多峰測試函數局部極值多，因此多峰測試函數可以測試算法是否陷入局部最優并評價算法的全局尋優能力[14]。因此，為了評價本文算法的全局及局部尋優能力，本文分別采用CSA、本文算法、烏鴉算法（CS）、灰狼算法（GWO）對6個多峰測試函數求極值。多峰測試函數信息如表2所示。

表2 測試函數Table 2 Test function

由于本文算法是針對城市災區的特定場景所進行的改進，融入了地面用戶節點的坐標信息，而運用于函數中則是在定義域內求一個最優值。因此在使用本文算法進行尋優時，為了與本文算法保持一致，在定義域內隨機生成n個節點，相當于本文中的地面用戶節點，然后采用本文算法的位置更新規則尋優，相當于在函數的定義域內求1架無人機的最優位置問題。

分別對4種算法獨立運行100次，取實驗的平均結果并畫出進化圖像，結果如圖10～圖15所示。

圖10 F1進化曲線Fig.10 Evolution curve of F1

圖11 F2進化曲線Fig.11 Evolution curve of F2

圖12 F3進化曲線Fig.12 Evolution curve of F3

圖13 F4進化曲線Fig.13 Evolution curve of F4

由圖10可以看出，4種算法都達到了全局最優，且尋優速度和收斂速度都很快。由圖12、圖14、圖15可以看出，都存在算法陷入了局部最優。圖12中GWO算法陷入了局部最優，其他3種算法都達到全局最優，但CSA算法和CS算法的尋優速度和收斂速度更快。圖14中，CS算法和GWO算法陷入局部最優值，CSA算法和本文算法都達到了全局最優，但尋優速度劣于其他兩種算法。圖15中CSA算法和GWO算法很早地陷入了局部最優且始終未能跳出局部最優解，CS算法出現幾次局部極值，且最終未達到全局最優，而本文算法局部尋優速度快，且最終達到全局最優，但由于函數的復雜性，算法的收斂速度較慢。由圖11和圖13可以看出本文算法出現了幾次局部最優值的變化并最終收斂在局部最優，圖11中GWO算法達到了全局最優，CSA算法和CS算法陷入局部最優，且距離全局最優值有一定距離。圖13中CS算法和GWO算法都達到了全局最優，CSA算法和本文算法都出現幾次局部極值并最終收斂到局部最優，但在兩個函數中本文算法的解都更接近于全局最優值且尋優速度較快。

圖14 F5進化曲線Fig.14 Evolution curve of F5

圖15 F6進化曲線Fig.15 Evolution curve of F6

總體上說，本文算法的尋優速度以及收斂速度都較快，且算法的局部尋優能力和全局尋優能力都優于其他算法。這是由于本文算法對布谷鳥算法位置更新方程的改進，使得算法在全局搜索時種群多樣性更強，從而使得算法在全局尋優和局部尋優上更好地達到平衡。

3.5.2 實驗比較

為了進一步驗證本文算法的有效性，在相同實驗參數設置下，將本文的加權覆蓋率作為目標函數，在相同實驗環境下多次運行文獻[10]提出的模擬退火算法（SAA）、標準布谷鳥搜索算法（CSA）以及本文提出的改進的布谷鳥算法，分別進行500次獨立性實驗。

圖16為進行一次實驗后，三種算法的適應度值函數曲線圖。從圖中可以看出，本文算法的加權覆蓋率高達95.43%，而標準布谷鳥搜索算法和模擬退火算法的覆蓋率則分別為89.14%和86.16%。對比數據，本文算法的加權覆蓋率明顯高于其他兩種算法。

圖16 算法性能對比Fig.16 Algorithm performance comparison

3.5.3 實驗分析

為了更加公平地獲得實驗結果并對其分析，本文分別取三種算法500次實驗結果性能指標的平均值，具體結果如表3所示。

表3 算法性能對比Table 3 Algorithm performance comparison

對比表中的算法的各個性能指標，可以看出經過本文對布谷鳥搜索算法的改進，無人機網絡的加權覆蓋率達到的94.32%，比文獻[10]中的模擬退火算法的覆蓋率高出了2.98個百分點，比標準布谷鳥算法的覆蓋率高出了1.87個百分點。

綜上所述，本文提出的城市災區無人機網絡自適應覆蓋優化算法不僅綜合考慮了地面用戶節點的移動特性，以及待覆蓋區域的重要程度差異，且重點提高了無人機網絡對重點區域的覆蓋率，能夠實現無人機網絡對目標區域的自適應覆蓋且保證了網絡的連通性，此外本文算法的全局尋優以及局部尋優能力較強，證明本文所提算法能夠更加有效地對城市災區無人機網絡的覆蓋率進行優化。

4 結束語

傳統的對無人機應急網絡覆蓋優化的研究，大多不針對城市災區環境，且將地面用戶節點視為靜止節點，與災害發生后的實際情況不符。

針對此，本文提出了一種城市災區無人機網絡自適應覆蓋優化算法來對城市環境下移動的地面用戶節點進行覆蓋優化。以某校區地圖為例，對地震發生后地面用戶節點的移動情況進行模擬。從移動模型中獲得各個時刻地面用戶節點的坐標，融入到布谷鳥算法的位置更新方程中，使無人機網絡能夠對地面用戶節點進行動態覆蓋同時實現對重點區域的覆蓋率優化。考慮到無人機網絡的連通性，引入虛擬力對布谷鳥算法的位置更新方程再次改進。使無人機網絡在維持網絡連通性的情況下適應了城市災區場景中用戶節點的動態移動性。

將本文算法同傳統布谷鳥算法以及改進的模擬退火算法進行多次實驗對比，本文所提算法針對城市環境下地面用戶節點的移動特性覆蓋優化有效。采用本文所提算法，無人機網路的覆蓋率、連通性以及路徑損耗在動態環境下穩定，全局尋優能力以及局部尋優能力強并能保持平衡性，且在覆蓋率上優于其他兩種算法。以上證明本文所提算法具有一定的應用價值。