兼顧公平與效率的無人機應(yīng)急中繼通信選址優(yōu)化問題*

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

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

0 引言

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

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

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

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

1 問題描述

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

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

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

2.1 基本假設(shè)

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

2.2 構(gòu)建吞吐量函數(shù)

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

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

式中：ω表示信道帶寬；SNRij表示無人機UAVi對受災(zāi)用戶集群點j信號傳輸?shù)男旁氡取?/p>

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

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

2.3 構(gòu)建公平損失函數(shù)

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

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

2.4 建立模型

建立兼顧公平與效率的多目標(biāo)0-1 非線性整數(shù)規(guī)劃模型如式（6）～（14）所示：

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

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

3 基于k-means的模擬退火算法設(shè)計

無人機應(yīng)急中繼通信問題也就是無人機在受災(zāi)區(qū)域的選址問題，即中繼節(jié)點的通信網(wǎng)絡(luò)覆蓋問題以及最大限度保證覆蓋范圍內(nèi)的通信質(zhì)量，可將無人機應(yīng)急中繼通信選址問題轉(zhuǎn)化為多配送中心選址問題。

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

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

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

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

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

步驟4：計算目標(biāo)函數(shù)差Δf=（f（X′）-f（X））/f（X′），其中f為目標(biāo)函數(shù)。

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

4 案例分析

4.1 案例背景及模型化處理

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

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

在該案例中，m=15，n=103，m為無人機的數(shù)量，n為DUCP的個數(shù)，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?？紤]到九寨溝的地形地貌，假設(shè)無人機的懸停高度達到最大，即Hi=100 m，設(shè)置模擬退火算法的初始溫度為T0=300 ℃，馬爾可夫鏈長為L=300，采用Matlab2019（b）在11th Gen Inter（R） Core（TM） i5-1135G7 @ 2.4GHz、RAM 16GB的計算機上進行模擬仿真。

4.3 多目標(biāo)求解分析

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

1）僅考慮系統(tǒng)吞吐量優(yōu)化目標(biāo)

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

圖2 僅考慮系統(tǒng)吞吐量優(yōu)化目標(biāo)結(jié)果Fig.2 Results considering system throughput as optimization object only

2）僅考慮公平損失優(yōu)化目標(biāo)

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

圖3 僅考慮公平損失優(yōu)化目標(biāo)結(jié)果Fig.3 Results considering fairness loss as optimization objective only

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

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

4.4 參數(shù)敏感性分析

無人機數(shù)量對各指標(biāo)的影響如表1所示，隨無人機數(shù)量增多，無人機設(shè)備成本逐漸增加，系統(tǒng)吞吐量逐漸增加，公平損失函數(shù)值逐漸減少?；诙ɑ治龇ㄋ悸?，選取無人機數(shù)量由14 增加至19 時，指標(biāo)F1，F(xiàn)2及計算用時的變化幅度作為固定基期，計算僅考慮F1優(yōu)化目標(biāo)情況下各指標(biāo)的變化趨勢，發(fā)現(xiàn)無人機數(shù)量由14增加到15 時，F(xiàn)1增加22%，F(xiàn)2降低22%，計算用時降低69%；無人機數(shù)量由15 增加16 時，F(xiàn)1增加14%，F(xiàn)2降低13%，計算用時降低12%；無人機數(shù)量由16 增加到17、由17 增加到18、由18 增加到19 時，F(xiàn)1分別增加19%，16%，29%，F(xiàn)2分別降低15%，27%，23%，計算用時分別降低14%，4%，2%。綜合各指標(biāo)因素，15 臺無人機為最優(yōu)數(shù)量，原因在于由14 臺增加15 臺，計算用時大幅度降低，說明15 臺無人機可以得到較為優(yōu)質(zhì)的解，繼續(xù)增加無人機數(shù)量，并不會使F1，F(xiàn)2優(yōu)化目標(biāo)得到大幅度改善，反而增加無人機的成本，同時也有可能造成應(yīng)急救援設(shè)備數(shù)量的緊缺。

表1 無人機數(shù)量對各指標(biāo)的影響Table 1 Influence of UAVs number on each index

5 結(jié)論

1）基于公平理論構(gòu)建的公平損失函數(shù)，量化受災(zāi)群眾對通信質(zhì)量差異的心理感知，本文所構(gòu)建模型能夠保證所有受災(zāi)用戶集群點獲得通信覆蓋，同時，系統(tǒng)吞吐量優(yōu)化目標(biāo)與公平損失優(yōu)化目標(biāo)存在悖反關(guān)系，應(yīng)急決策者應(yīng)根據(jù)實際情況選擇相應(yīng)的救援方案。

2）通過參數(shù)敏感性分析可知，無人機設(shè)備存在1 個最優(yōu)數(shù)量，達到最優(yōu)數(shù)量后，并不會使F1，F(xiàn)2優(yōu)化目標(biāo)得到大幅度改善。

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