兼顾公平与效率的无人机应急中继通信选址优化问题*

2023-02-24黄禄平曹策俊王文轲

中国安全生产科学技术 2023年1期

黄禄平，杨琴，曹策俊，王文轲

（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优化目标得到大幅度改善，反而增加无人机的成本，同时也有可能造成应急救援设备数量的紧缺。