面向异构无人机中继网络的负载均衡：一种分层博弈方法*

杨婷婷 ，宋 绯 ，孙有铭 ，姚凯凌 ，杨 旸

（1.陆军工程大学 通信工程学院，江苏 南京 210007；2.中国人民解放军61062部队，北京 100091)

0 引 言

随着无人机技术的发展与成熟，它已广泛应用于中继Ad-hoc网络、搜索与救援、目标侦查和跟踪、森林火灾监控和遥远感知等民用或军事领域。无人机网络通常呈现大规模、超密集、异构任务驱动、异构位置部署等特点，面临能量受限、资源紧缺的困难。因此，如何提升无人机网络吞吐量性能是一个巨大的挑战。无人机作为中继可以缓解不断增长的流量需求和扩大动态通信系统的覆盖面积。文献[1]先划分子区域内的流量需求，再通过局部搜索优化无人机的位置部署和服务区域，实现无人机之间所覆盖区域的负载均衡。文献[2]针对宏蜂窝网络存在的负载不均衡和功率资源浪费的问题，引入无人机作为宏蜂窝和微蜂窝的中节点扩大覆盖和提高容量，并提出基于神经系统的开销函数，将无人机匹配到合理位置，实现远程连接和流量卸载问题。文献[3]研究D2D（Device-to-Device）用户对在无线小蜂窝网络中的两种通信模式：（1）用户对可以通过小蜂窝提供可靠的回程传输通信，但受限于共信道干扰和回程容量限制；（2）距离相近的D2D用户对直接通信，但受限于频谱复用的干扰，每个用户根据流量需求选择一种最优的传输通信模式。现有研究主要考虑无人机作为中继协助地面蜂窝网络实现负载均衡问题，以及直接传输与中继辅助传输的通信模式优化问题。上述研究主要直接面向优化问题本身，缺乏对驱动无人机作为中继节点的激励机制研究。此外，现有研究主要针对地面网络、无人机辅助地面网络的场景，缺乏对无人机网络内部存在的负载均衡问题的研究。因此，本文针对无人机中继网络中的负载均衡问题展开研究。

斯坦博格博弈是一种优化不同优先级参与者相互利益的策略选择方法，被广泛用于分层无线网络结构下的无线资源分配问题[3-4]。文献[3]应用斯坦博格博弈模型分析了D2D用户对在回程容量受限的无线小蜂窝网络中通信模式的选择问题，每个用户通过优化由性能和开销构成的效用函数来选择最好的通信模式。文献[4]研究了异构中继网络中动态宏用户接入宏蜂窝网络存在的两种方式，分别是直传链路和中继协助的两跳链路。其中，两跳链路需要共享频谱资源。为了给回程提供足够的容量，并保证宏用户资源共享的公平性，通过建模为斯坦博格博弈模型保证回程链路和接入链路吞吐量平衡，并提高用户速率和系统资源利用率。然而，现有研究主要针对每个用户仅选择中继传输模式下接入链路和回程链路的吞吐量平衡，不适用于单用户兼具直接传输和中继传输两种传输模式。

本文针对无人机网络内部负载不均的情况，研究直传和中继回程传输两种策略共存的功率资源分配问题。覆盖的网络边缘无人机可根据业务和无线环境约束，同时通过直传和中继两种通信链路回传数据。上述两种通信链路需要考虑不同的优化约束：中继链路可能获得潜在的容量增益，但需要考虑中继无人机回程链路容量的限制；直传链路容量受到通信距离和传输功率的约束。网络边缘无人机需要在两种传输特性异构的通信链路上对业务负载进行优化分配。为了更充分利用无人机网络空闲中继资源，首先引入中继激励机制，并将异构中继网络负载均衡优化问题建模为斯坦伯格博弈模型。其中，中继无人机为领导者，网络边缘无人机为跟随者。网络边缘无人机的效用函数综合考虑了直接传输和中继传输获得的吞吐量增益和支付给中继节点的价格开销。中继无人机的效用函数为其所协助传输的无人机支付的总和，并对所提出的博弈模型的性质进行了分析。考虑到中继回程容量受限的实际约束，采用粒子群优化（Particle Swarm Optimization）算法，将粒子群的搜索范围限制在约束簇内，实现可行解域内最大效用函数对应解的搜索。

1 系统模型和问题描述

如图1所示，考虑一个正交频分多接入上行通信的异构无人机网络。每个簇由一架簇头无人机和多架簇成员无人机（包含网络边缘无人机和空闲的中继无人机）构成。假设簇成员密集部署且业务需求异构。系统直传和中继传输在正交信道上且带宽均为b MHz[5]，网络边缘无人机在上传信息给簇头时，可同时选择直传链路和中继协助传输链路。本文中的中继无人机可以协助多个源节点（网络边缘无人机）进行传输，但每个源节点最多只允许接入一个中继无人机。由于全双工操作对中继的设备要求较高[3]，为了便于分析，中继无人机工作在半双工中继模式，中继回程容量为Rth，中继转发的回程和接入链路使用时分复用方式。

图1 异构中继网络模型

本文在现有关于异构中继网络分层资源配置[6]的基础上提出，当用户负载差异大时，超负载的网络边缘无人机同时选择直传和中继传输两种传输接入方式，在功率资源受限的情况下，最大化系统吞吐量性能。为激励空闲迷你无人机充当中继协助传输，提出了一种考虑经济效用驱动的激励机制。空闲迷你无人机中继传输单位流量可以获得收益β。假设每个超负载网络边缘无人机的最大发射功率为pmaxi，其中αipmaxi分给中继回程传输（0≤αi≤1），剩余功率(1-αi)pmaxi用于直传链路传输。

网络边缘无人机i通过直传链路获得的吞吐量为：

其中，h是相关距离d0=1时的信道增益常数，diu为无人机i直传链路到簇头节点的距离，α是路径损耗指数，其信道功率增益为hd-αiu[4]，N0为信道高斯噪声功率。

网络边缘无人机i通过中继链路获得的吞吐量可表示为[4]：

为简化其表达式，通过调整中继对单位速率的售价β（将在推论2中给出证明），使得所有接入同一中继的用户的第一段接入中继链路的总速率之和小于中继回程速率门限Rth，可表示为：

可以进一步简化为：

由于无人机网络具有高动态性，迷你无人机没有稳定的直传或回程链路。价格作为一种无人机网络流通的帮助激励机制，空闲迷你无人机作为中继通过开放接入获得经济回报，网络边缘用户由于位于覆盖区域边缘且负载很大需要协助传输，希望在功率资源限制下得到最大吞吐量，故愿意付出一部分经济代价换取性能提升。

2 斯坦伯格博弈模型

斯坦伯格博弈是一种典型具有双层结构的非合作博弈模型。上层博弈参与者为领导者，有优先决策权，因而具有先发优势；下层博弈参与者作为跟随者，根据上层领导者做出的决策再做出相应的最佳响应，从而最大化自身效用。本文中的斯坦伯格博弈模型为单领导者多跟随者形式。具体而言，中继无人机作为领导者确定中继传输单位速率的定价β并广播给接入的网络边缘无人机；网络边缘无人机作为跟随者根据中继流量定价β选择最佳的负载分配策略。

根据式（1）和式（4），下层用户（网络边缘无人机）i效用函数可表示为：

对于上层中继无人机，它的效用函数为所有接入该无人机的网络边缘无人机支付的中继流量价格之和，可表示为：

上层中继无人机的优化目标为：

本文的斯坦伯格博弈分别利用式（7）和式（5）构成上层和下层的效用函数。通过分析所提博弈，确定存在斯坦伯格均衡（Stackelberg Equilibrium，SE）状态。在斯坦伯格均衡状态下，上下层用户都无法通过单方面改变动作策略而提高其效用。

提出的斯坦伯格博弈表示为：

3 斯坦伯格均衡

定义1（斯坦伯格均衡[7]）：若上层中继无人机选择流量定价策略β*，下层用户i选择功率分配策略，可以分别使得上层效用函数UL和下层效用函数Ui取最大值，且对每个参与者的任何策略集 {β,αi}都满足：

则策略集(β*,)∈β⊗α被称为该博弈的斯坦伯格均衡点，⊗是笛卡尔积，是除了下层用户i的其他用户的最佳策略。

当没有参与者可以通过单方面改变策略提高自己的效用函数时，即达到了斯坦伯格均衡稳定解。

下面引理1将给出该博弈具有稳定SE的证明。

定理1：本文提出的斯坦伯格博弈中总是存在SE。

引理1[8]：博弈总是存在纳什均衡（NE），如果对于所有用户i=1,2,…,N，必须满足以下两个条件：

（2）Ui是关于αi的连续拟凹函数。

对 Ui(αi,β)关于 αi求两阶偏导数：

其中[]+=max(·,0)，可看出功率分配比例αi是关于上层流量定价β的函数，表示功率分配比例非负，且须满足约束[0,1]之间。

根据下层用户效用函数公式可知，−β＞0。所以公式成立，由此证明了下层效用函数Ui(β,α)关于αi是严格凹的。根据引理1，下层子博弈中存在NE。定义NE(β)表示在给定上层中继无人机策略β时所有网络边缘无人机的最佳动态响应，则存在SE的条件可以转化为以下形式：

可知，上层中继的效用函数是其优化变量β可行域内的连续函数。所以，中继无人机存在最优的流量定价策略满足)，即总是存在β*满足以下条件：因此，所提博弈总是存在SE。证毕。

4 SE搜索算法

4.1 迭代算法

中继流量定价迭代算法流程如下。

步骤1：初始化。每个下层用户到中继无人机的距离dib，直传链路到簇头的距离diu，当前用户i最大可用功率pmaxi，信道高斯噪声N0，信道增益h，中继到簇头距离distance，中继可负载功率power，迭代步长η=10-4，迭代次数k=1。

步骤2：初始化第一次迭代上层中继流量定价β=0.5。

（3）计算此时下层所有用户传输给中继的总吞吐量：

（4）判断是否满足式（14），若满足，计算：

中继流量定价迭代算法可计算出推论1、推论2中给出的上层中继用户售价策略上下限。

证明：定义上层中继用户流量定价可行域的上界为βmax。当流量定价取到最大值βmax时，下层用户的最佳策略为将全部功率用于直传链路，即=0，∀i∈。由此，可计算βmax：

证毕。

推论2：上层中继无人机协助传输单位速率定价的可行域存在下界βmin。当β＜βmin时，上层用户效用函数恒为 UL(β)=βRth。

证明：为了保证下层网络边缘无人机到达簇头无人机的速率能够表示为，即要使网络边缘无人机采用中继传输到达簇头无人机的速率等于其传输给中继的速率的一半。需要满足下层网络边缘无人机传给中继无人机的速率总和小于回程速率的限制条件，即。

因此，需要中继无人机太高价格并确定下层用户帮助传输单位速率的最低售价βmin，以此限制下层的网络边缘无人机向中继无人机传输的速率总量不超过其可以承载的门限值Rth。中继流量定价迭代算法可通过迭代的方式得到β的最小值。当β＜βmin时，中继的负载将保持为Rth，此时上层效用函数为UL(β)=βRth，成为关于β的减函数。此时，即使中继无人机降低其售价，也不会带来自身效用函数的提升。

4.2 PSO学习算法

PSO[9]是一种仿生物群鸟觅食寻找最佳决策的自适应随机优化算法，用到了个体自学与经验传授的理念。所以，在每次更新决策时同时考虑个人的尝试经验和他人的选择经验。在经典PSO中，每个个体被视为一个粒子，鸟群被视为一个粒子群。每个粒子在一个D维空间进行目标搜索，假设有m个粒子构成一个群体，可将第i个粒子(i=1,2,…m)的位置表示为Xi=(,,…)，每个粒子的位置就是一个所寻找的潜在最优解，下一个位置的更新由飞行速度矢量V=(,…,)决定。将每个粒子i的当前位置矢量Xi代入目标函数，即可得其对应的适应值（Fitness Value），然后根据适应值的大小判断当前位置的优劣。每个粒子把自己当前已搜索过的最优位置P=(,…,记录下来作为个i人经验。就整个群体而言，需要在每一次位置更新后记录下群体对应最优适应值下的全局最优位置Pg=(,…,)。

粒子群算法采用的速度和位置更新公式如下：

其中，i=1,2,…,m；d=1,2,…,D；w是速度惯性因子非负数；c1和c2分别是个人经验和他人经验对速度造成影响的非负加速常数；r1和r2是[0,1]内变换的随机数；a为控制速度权重的约束因子。此外，

PSO算法流程图具体步骤如下。

步骤1：初始化种群中粒子数目m；惯性因子w；加速常数c1和c2；约束因子a；最大速度常数；每个下层用户到中继距离dib，直链路到簇头距离diu，当前最大可用功率，信道高斯噪声N0，信道增益h，中继到簇头距离distance，中继可负载功率power，由中继流量定价迭代算法中的中继流量定价可行域迭代算法计算得到的∈ [βmin,βmax]；最小误差 E0；最大迭代次数 Num。

步骤2：计算每个粒子的初始适应值，并将初始适应值作为当前位置下每个粒子的局部最优适应值，各适应值的位置对应于局部最优位置。

步骤3：根据式（19）、式（20）更新每个粒子的飞行速度，并约束在最大值范围内和更新位置。

步骤4：比较更新位置后的适应值与历史局部最优适应值，更新局部最优适应值及其对应位置，再更新全局最优适应值及所在位置。

步骤5：重复步骤3和步骤4，直到满足最小误差或到达最大迭代次数。

步骤6：输出粒子群全局最优适应值及其对应位置。

5 仿真结果

本节对所提迭代算法和PSO算法进行仿真验证和分析。仿真参数设置如下：空中相关距离为1 m时的信道增益常数h=0.000 1，路径损耗因子α=3.75，噪声功率σ=-110 dBm，空闲中继无人机负载功率为1 W，其到簇头距离为600 m时，对两算法进行对比分析。在下面的仿真图中，中继负载能力等价于中继的总功率或当前可用最大功率。

5.1 算法对比

如图2所示，由PSO算法搜索到的最大上层效用函数值为UL(β)=0.188 37，对应中继售价β=0.435 52。相比迭代算法得到的最大上层效用函数UL(β)=0.188 3更加精确。以下分析将采用中继流量定价迭代算法计算出相应参数设置下的中继售价β的取值范围，再由PSO算法搜索最大上层效用函数和中继最优售价。

图2 迭代算法与PSO算法搜索结果对比

图3 为迭代算法与PSO算法搜索次数对比。图3（a）为迭代步长为0.01的迭代算法比较，图3（b）为使用误差精度为0.884的PSO算法运行次数比较。可知，为了找到最优解，PSO算法搜索了16次，迭代算法为39次。因此，PSO比迭代算法更优。

图3 迭代算法与PSO算法搜索次数对比

5.2 中继到簇头距离对上层效用函数的影响

图4 给出了中继无人机到簇头无人机距离变化范围从450～700 m，并且分别给出了中继无人机在接入2～5个网络边缘用户时的上层效用函数曲线。峰值点对应中继无人机收益最好时到簇头无人机的距离。由图4可见，随着负载用户数目的增加，中继无人机到簇头的最优距离随之减小。

5.3 中继总功率对上层效用函数的影响

由图5可得，随着中继总功率的增大，可以为下层用户提供更多的服务，因此上层收益会相应提升。但是，用户数为2时出现平滑现象，原因是下层用户的需求量达到了饱和值。

图4 上层效用函数随中继到簇头距离变化曲线

图5 中继总功率对上层效用函数的影响

5.4 中继到簇头的距离对系统吞吐量的影响

图6 描述了中继总功率为1 W时，改变其到簇头无人机的距离，分别负载2～5个用户时，下层网络边缘无人机负载均衡模式相比仅采用直传链路传输对系统速率提升量的影响。

图6 中继到簇头距离对负载均衡时系统速率提升的影响

由图6可知，中继距簇头越远，速率提升越小，而中继负载下层用户数越小，对系统吞吐量的提升越大。

式（21）的含义是采用本文提出的负载均衡机制相比仅采用直传链路传输对系统吞吐量的提升量。式（22）计算了采用负载均衡相比全部用户采用直传链路传输时系统吞吐量提升的百分比。

5.5 中继总功率对下层效用函数的影响

由图7可知，改变中继的总功率对下层用户的效用函数影响不大，但是每个用户因自身参数不同，接受中继帮助的程度也不同。

图7 下层各用户效用函数

6 结 语

本文研究了大规模无人机中继网络中的负载均衡问题。为激励空闲无人机充当中继协助网络边缘无人机将采集的信息回传到簇头大无人机，提出一种价格激励机制以提升系统吞吐量，并将直传链路和中继回程协助传输链路两种通信模式共存的负载均衡问题建模为斯坦博格博弈模型。空闲无人机中继作为领导者，网络边缘无人机作为跟随者，它们分别通过优化传输单位速率的收价和分配给中继传输的功率比例最大化其效用函数。理论证明了所提分层博弈模型SE的存在性，并使用迭代算法和PSO算法搜索到了全局最优解。最后，对不同中继到簇头距离或不同中继总功率对系统吞吐量性能提升的影响做出分析。