兼顧公平與效率的無人機應急中繼通信選址優化問題*

黃祿平，楊 琴，曹策俊，王文軻

（1.四川師范大學商學院，四川 成都 610101；2.重慶工商大學管理科學與工程學院，重慶 400067）

0 引言

近年來自然災害頻發，造成大量人力、物力和財力的損失。自然災害（如地震、洪澇災害等）的發生，會嚴重損壞基礎通信設施，造成受災區域通訊中斷，不僅會對救援行動造成極大困擾，還會加劇受災群眾恐慌心理。同時，由于受災群眾分布較分散以及通信覆蓋范圍限制，不同地區受災群眾接收的通信信號質量存在差異，因而，應急中繼通信資源的分配會使受災群眾產生不公平感，如何緩解受災群眾的不公平感是應急決策者需要考慮的問題。應急中繼通信選址對自然災害救援工作十分重要，既要兼顧效率，也要考慮通信資源分配的公平性。技術的進步和生產成本的降低，使得無人機（unmanned aerial vehicle，UAV）廣泛應用于監測、攝影、交通控制、搜索和救援、包裹遞送、通信等領域。無人機具有輕便、靈活、可快速部署、信號覆蓋面積廣等特點，在應急中繼通信中具有較大優勢[1]。

學者關于無人機在應急通信領域的研究主要集中在無人機軌跡優化和部署問題、資源分配問題及聯合優化方面。針對應急通信背景下無人機軌跡優化問題，Tran 等[2]通過聯合優化帶寬、功率分配和無人機軌跡，實現服務數量最大化，并設計迭代算法求解該問題；Zhang等[3]考慮實現用戶全覆蓋的應急通信網絡軌跡優化問題，提出2 種基于k-means的軌跡規劃算法。針對應急通信背景下無人機部署、資源分配問題，Feng等[4]提出基于NOMA系統的多無人機聯合部署和資源分配方案，并將問題分解成3 個子問題，使用多目標進化算法、基于FP的算法及分支定界法進行求解；Arafat等[5]提出無人機網絡應急通信選址與聚類方案，設計基于粒子群算法的群智能聚類算法；Do等[6]為解決災區通信網絡及時恢復問題，提出基于k-means的快速用戶聚類模型及聯合最優功率和時間轉移分配方法；Lin 等[7]為解決災后無人機輔助地面節點通信的覆蓋問題，提出自適應無人機部署方案，利用迭代算法結合功率控制，求解無人機最優選址及地面節點的最優傳輸功率。在求解方法上，針對軌跡優化問題主要有深度學習算法[8]、迭代算法以及基于k-means的改進算法；針對部署、選址覆蓋問題主要有多目標進化算法、改進的傳統啟發式算法與聚類算法相結合等。

綜上，針對無人機在應急通信領域的應用仍存在以下問題：1）已有成果更多聚焦于應急通信背景下無人機軌跡優化問題、部署問題、通信資源分配問題等，較少涉及無人機應急中繼通信選址優化問題；2）已有成果大多以效率評價指標，如服務數量、功率、覆蓋面積、吞吐量作為優化目標，較少考慮公平性目標，而公平性感知[9-12]對應急救援效果的評價十分重要。

本文針對無人機應急中繼通信選址優化問題，借鑒亞當斯公平理論，引入公平評價指標，構建以最大化系統吞吐量為效率目標、最小化受災群眾公平損失值為公平目標的無人機應急中繼通信選址多目標0-1 非線性整數規劃模型，并通過基于k-means的模擬退火算法求解該模型，以得到兼顧公平與效率的無人機應急中繼通信選址方案。

1 問題描述

大規模災害事件發生后，通信設施損壞嚴重，受災地區面臨大面積通信中斷，受災群眾不僅對救援物資需求巨大，還對通信信號的及時恢復有著迫切要求，通信信號及時恢復能夠在一定程度上緩解受災群眾的恐慌心理。因此，確保為受災群眾提供有效、及時的通信恢復以及應急中繼節點的合理分布，是應急中繼通信過程的核心環節。各受災用戶集群點（disaster user cluster point，DUCP）位置分散，各DUCP與無人機之間距離不同，因而，其所接收的通信信號質量存在差異，并且會對中繼通信服務產生不同的公平性感知。無人機用于應急中繼通信需要考慮救援成本、通信覆蓋范圍、多個受災用戶集群點等限制。考慮以上問題，本文建立兼顧公平與效率的無人機應急中繼通信選址模型，在無人機信號覆蓋范圍、通信容量限制下探究無人機最優選址，以實現最大化系統吞吐量、最小化公平損失的優化目標。無人機應急中繼通信選址如圖1所示。

圖1 無人機應急中繼通信選址Fig.1 UAV emergency r elay communication location

2 無人機中繼通信選址模型

2.1 基本假設

為明確本文研究的應用范圍，做出如下假設：1）受災用戶集群點是由一定區域內部分受災群眾組成，區域內受災群眾接收到的通信信號相等且等價于受災用戶集群點所能接收到的通信信號；2）不同受災用戶集群點由于其距離無人機中繼節點的相對位置不同，其接收到的通信信號強度也存在差異；3）每個受災用戶集群點最多只能接收1 臺無人機發出的通信信號，即最多被1 臺無人機服務；4）考慮到資源的稀缺性，為使資源得到充分利用，1 臺無人機至少要服務1 個受災用戶集群點；5）災害環境下，受災群眾的身心相對脆弱，容易引發焦慮和恐慌情緒，因而對公平的感知十分強烈。

2.2 構建吞吐量函數

災害發生后，受災群眾能夠直接感受到通信中斷、通信信號差等典型特征，而在通信領域，該典型特征由吞吐量體現。文獻[13]考慮無人機通信的半雙工模式，推導上下鏈路的信噪比表達式；文獻[14]將系統吞吐量

定義為系留式無人機到用戶之間的雙向傳輸速率與整個系統進行雙向通信服務所消耗總時間的比值。為簡化運算，將吞吐量用無人機與受災用戶集群點之間的傳輸速率表示，依據香農公式，無人機UAVi與地面受災用戶集群點j之間的傳輸速率Rij如式（1）所示：

式中：ω表示信道帶寬；SNRij表示無人機UAVi對受災用戶集群點j信號傳輸的信噪比。

其中SNRij如式（2）～（4）所示：

式中：g0表示無人機對受災用戶集群點之間的小尺度衰弱系數；σ2表示白噪聲功率；βij表示無人機UAVi與受災用戶集群點j的路徑損失；c表示光速，m/s；f表示載頻；dij表示無人機UAVi與受災用戶集群點j之間的距離；α表示路徑損耗指數；（xi，yi，Hi）表示無人機UAVi的3 維坐標，（xj，yj，0）表示地面DUCPs的3 維坐標，i∈M={1，2，…，m}，m表示UAV數量，0＜Hi＜Hmax，Hmax表示無人機的最大懸停高度；j∈N={1，2，…，n}，n 表示受災區域內的DUCPs數量和無人機懸停點備選點數量；M，N分別表示UAVs和DUCPs的集合。

2.3 構建公平損失函數

考慮災害發生后，不同區域受災群眾接收到的通信信號不同，通信資源分配不均會引發受災群眾的不公平感知問題。將系統內受災用戶集群點所接收的最大吞吐量作為參考值[15]，記為 Rmax=max（Rij），Rmin=min（Rij），公平損失函數定義為式（5）：

式中：函數Zij表示將受災用戶集群點的吞吐量與受災區域的最大吞吐量的差值做歸一化處理之后的比值。由亞當斯的公平理論可知，Zij越小，受災用戶集群點所接收到的通信信號差異越小，則受災群眾感到越公平。

2.4 建立模型

建立兼顧公平與效率的多目標0-1 非線性整數規劃模型如式（6）～（14）所示：

式中：F1表示所有受災用戶集群點的通信吞吐量；F2表示所有受災用戶集群點的公平損失函數值；E表示無人機的額定通信容量；r0表示DUCPs保持通信所需的最低吞吐量；dmax表示無人機最大通信覆蓋范圍；決策變量分別為γik，ρij，當γik=1 時，表示UAVi懸停于受災用戶集群點k，否則，γik=0；當ρij=1 時，表示UAVi用于服務受災用戶集群點j；否則，ρij=0；

式（6）表示最大化通信系統吞吐量的優化目標；式（7）表示最小化公平損失優化目標；式（8）表示任意1臺無人機至少服務1 個DUCP；式（9）表示1 個DUCP最多只能被1 臺無人機服務；式（10）表示無人機通信中繼覆蓋范圍的約束；式（11）表示任意1 個DUCP的吞吐量不小于滿足其保持通信的最低吞吐量；式（12）表示無人機服務區域內DUCPs的總吞吐量不能超出無人機的額定通信容量；式（13）～（14）均表示決策變量的取值。

3 基于k-means的模擬退火算法設計

無人機應急中繼通信問題也就是無人機在受災區域的選址問題，即中繼節點的通信網絡覆蓋問題以及最大限度保證覆蓋范圍內的通信質量，可將無人機應急中繼通信選址問題轉化為多配送中心選址問題。

多配送中心選址問題是帶有復雜約束的非線性模型，屬于典型的NP-hard 問題[16]，而求解NP-hard 問題需要使用啟發式算法，如遺傳算法、粒子群算法、蟻群算法、模擬退火算法等，模擬退火算法具有計算過程簡單、魯棒性強、適合并行處理等特點，能有效解決NPhard 問題，避免陷入局部最優解。k-means算法在歸類數據上具有顯著優勢，能夠快速、精準地找到最優解。本文擬設計1 種基于k-means的模擬退火算法求解該問題。

基于k-means的模擬退火算法設計包括以下6 個步驟：

步驟1：初始化溫度T=T0，每個T值的迭代次數為L，利用k-means算法求解聚類中心，創造初始解X=X0，設置溫度冷卻系數τ。

步驟2：對k=1，2，3，…，L，進行步驟3～步驟6。

步驟3：利用k-means算法計算新的聚類中心，產生新解X′。

步驟4：計算目標函數差Δf=（f（X′）-f（X））/f（X′），其中f為目標函數。

步驟6：若終止條件得到滿足，則直接輸出當前解。

4 案例分析

4.1 案例背景及模型化處理

2017年8月8日，四川省九寨溝縣發生里氏7.0 級地震，地震導致通信設施、基站等基礎設施破壞嚴重。中國移動用系留式無人機高空基站為受災地區提供應急服務，為約1 200 部手機提供通話上網等基本通信服務。本文以“8·8”九寨溝地震作為研究背景，選取九寨溝縣103 個行政村作為DUCPs，利用百度地圖拾取出每個DUCP的經緯度，利用ArcMap 10.7 將DUCPs的經緯度轉換成平面XY坐標，選擇新的參考點作為坐標系原點，并轉換單位。根據所選取的103 個DUCPs的相對位置、分布情況以及系留式無人機的信號覆蓋范圍，擬調用m臺無人機為受災區域內的DUCPs提供中繼通信服務。

4.2 參數設置

在該案例中，m=15，n=103，m為無人機的數量，n為DUCP的個數，Hmax=100 m，dmax=10 km[17]，g0=2 dB，f=2 GHz，σ2=-120 dBm，τ=0.99，ω=1 Hz[13，17]，α=2，C=28 萬元（C表示1 臺無人機的購置成本，單位為萬元），E=120 kbps（E表示無人機的額定通信容量），r0=2.67 kbps。考慮到九寨溝的地形地貌，假設無人機的懸停高度達到最大，即Hi=100 m，設置模擬退火算法的初始溫度為T0=300 ℃，馬爾可夫鏈長為L=300，采用Matlab2019（b）在11th Gen Inter（R） Core（TM） i5-1135G7 @ 2.4GHz、RAM 16GB的計算機上進行模擬仿真。

4.3 多目標求解分析

由于本文研究的問題是多目標問題，求解方法有線性加權法、理想點法、主要目標法、分層序列法、多目標單純形法等。本文借鑒分層序列法的求解思路，先以系統吞吐量函數目標值作為唯一優化目標求解，再以公平損失函數值作為唯一優化目標求解，然后將對方的相對最優值作為約束條件代入求解。

1）僅考慮系統吞吐量優化目標

以系統吞吐量函數值作為唯一優化目標進行求解，結果如圖2所示，迭代7 次后系統吞吐量函數值和公平損失函數值均收斂，結果趨于穩定，計算用時為183.68 s，系統吞吐量函數值的最優值為526.4，公平損失函數值為90.87。無人機最優選址方案如圖2（c）所示，其中DUCP（51），DUCP（100），DUCP（103）單獨被1 臺無人機服務。

圖2 僅考慮系統吞吐量優化目標結果Fig.2 Results considering system throughput as optimization object only

2）僅考慮公平損失優化目標

以公平損失函數值作為唯一優化目標進行求解，結果如圖3所示，迭代83 次后系統吞吐量函數值和公平損失函數值均收斂，結果趨于穩定，計算用時為187.06 s，公平損失函數值的最優值為56.72，系統吞吐量函數值的最優值為485.9。無人機最優選址方案如圖3（c）所示，其中每1 臺無人機至少服務2 個DUCPs。

圖3 僅考慮公平損失優化目標結果Fig.3 Results considering fairness loss as optimization objective only

通過以上僅考慮單目標優化的求解結果可知，系統吞吐量達到最優值526.4 時，公平損失函數值則為90.87，而公平損失函數值達到最優值56.72 時，系統吞吐量函數值則為485.9，二者均未達到僅考慮單目標優化時自身的最優解，表明系統吞吐量優化目標與公平損失優化目標之間存在一定悖反關系，并不存在滿足二者同時最優的解，只有非劣解。

將F1≥500 作為約束條件加入到模型中，求min F2，結果為F1=519.5，F2=90.92，計算用時為542.06 s；將F2≤70 作為約束條件加入到模型中，求max F1，結果為F1=494，F2=63.57，計算用時為1 044.08 s。增加目標函數值作為約束條件后，求解難度加大，故用時遠大于不增加目標函數值作為約束條件的計算用時，計算用時和解的值進一步驗證優化目標之間的悖反關系，應急決策者應根據決策偏好和救援實際選擇合適的選址方案。

4.4 參數敏感性分析

無人機數量對各指標的影響如表1所示，隨無人機數量增多，無人機設備成本逐漸增加，系統吞吐量逐漸增加，公平損失函數值逐漸減少。基于定基分析法思路，選取無人機數量由14 增加至19 時，指標F1，F2及計算用時的變化幅度作為固定基期，計算僅考慮F1優化目標情況下各指標的變化趨勢，發現無人機數量由14增加到15 時，F1增加22%，F2降低22%，計算用時降低69%；無人機數量由15 增加16 時，F1增加14%，F2降低13%，計算用時降低12%；無人機數量由16 增加到17、由17 增加到18、由18 增加到19 時，F1分別增加19%，16%，29%，F2分別降低15%，27%，23%，計算用時分別降低14%，4%，2%。綜合各指標因素，15 臺無人機為最優數量，原因在于由14 臺增加15 臺，計算用時大幅度降低，說明15 臺無人機可以得到較為優質的解，繼續增加無人機數量，并不會使F1，F2優化目標得到大幅度改善，反而增加無人機的成本，同時也有可能造成應急救援設備數量的緊缺。

表1 無人機數量對各指標的影響Table 1 Influence of UAVs number on each index

5 結論

1）基于公平理論構建的公平損失函數，量化受災群眾對通信質量差異的心理感知，本文所構建模型能夠保證所有受災用戶集群點獲得通信覆蓋，同時，系統吞吐量優化目標與公平損失優化目標存在悖反關系，應急決策者應根據實際情況選擇相應的救援方案。

2）通過參數敏感性分析可知，無人機設備存在1 個最優數量，達到最優數量后，并不會使F1，F2優化目標得到大幅度改善。

3）本文未考慮無人機設備不足最優數量的情況，未來將進一步研究無人機設備動態選址—路徑優化問題以及從演化博弈角度研究不確定條件下無人機設備供應商與應急救援部門的應急協作博弈機制。