基于博弈论的多无人机覆盖策略研究

谢祥洲， 谢 玲， 罗一欣

(1.电子科技大学机械与电气工程学院，成都 611000； 2.重庆城市管理职业学院，重庆 401000；3.吉林省教育学院，长春 130000)

0 引言

无人机(UAV)以其体积小、机动性强、通信成本低等特点在军事和民用领域得到了广泛应用，然而单架UAV往往不能满足复杂任务的需要[1-2]。为了解决这一问题,需要组建一个多UAV协作小组来提高效率，特别是在信息收集和处理方面，UAV之间的协作已成为UAV网络发展的关键技术之一[3-4]。

目前UAV研究热点主要集中在区域覆盖问题上，目的是使UAV更好地完成侦察、通信、测绘等任务[5]。文献[6]提出了一种无人机网络覆盖优化算法，通过对最少无人机节点数目和热点区域覆盖范围进行估计，并应用改进的布谷鸟算法重构优化目标函数，从而实现热点区域覆盖概率的重点优化;文献[7]提出了一种基于相对距离的无人机基站传感器网络部署方法，通过感知地面的未覆盖区域，以及覆盖边界或障碍物的位置实现按需覆盖，并在3个相对距离的影响下保持稳定的无线电覆盖，有效提高无人机网络覆盖效率。但上述方法难以最大程度地提高覆盖质量以及覆盖区域，并难以最小化发射功率，不能实现无人机辅助的无缝覆盖。文献[8]提出了一种基于飞行时间约束的无人机无线通信性能优化策略，通过使用最佳运输理论数学框架，提出了一种基于梯度的优化算法，用于根据用户的分布、飞行时间和无人机的位置对地理区域进行最佳划分，从而最大程度地提高覆盖质量、覆盖区域；文献[9]提出了一种用于无人机基站(UAV-BS)的最佳放置算法，在垂直和水平方向上解耦UAV-BS的部署问题，并将UAV-BS在水平维度上的部署建模为圆形放置问题，从而使用最小发射功率达到最大化用户覆盖数量；文献[10]提出一种无人机蜂群中紫外光隐秘通信能耗均衡路由算法，在保持UAV编队的基础上，根据无线紫外光散射通信的优点，在网络选择过程中结合通信链路损耗和节点剩余能量构建权值函数，从而平衡无人机蜂群节点的能耗，有效延长无人机蜂群的生命周期。但上述研究仅对发射功率进行了优化，未考虑无人机在推进过程中的能量消耗，与无人机网络通信的实际服务时间存在较大偏差，实用性较差。

为更好地解决在节能通信场景下UAV区域覆盖的问题，本文提出了一种基于博弈论的多无人机覆盖部署策略。

1 系统模型构建

图1所示为本文所探讨的多UAV合作覆盖示意图。对于任务单元i，假设某个给定UAVj的覆盖概率为qj,i，则采用软覆盖的概念计算网络中任务单元i的覆盖概率qi为qi=1-(1-q1,i)×(1-q2,i)×(1-q3,i)，该式表明探测到的UAV越多，任务单元的覆盖概率qi越高。

图1 任务区多UAV覆盖示意图

考虑到天线增益和路径损耗等因素，如何准确地描述任务点的覆盖效用是一个值得思考的问题。本文建立了由多UAV组成的空对地网络，连续区域I∈R2被均匀地划分成离散单元。UAVn的状态定义为sn={ln,pn}，其中，ln和pn分别表示UAVn的水平位置(xn，yn)和载波传输功率。假设固定翼UAV在固定的低空平台上水平飞行，UAV的定向天线波束宽度用θ表示，与均匀平面阵列(Uniform Planar Array,UPA)下的天线方向图相对应，从而得到了UAV的天线增益为

(1)

式中：Gm为主瓣增益；N0为天线元数。覆盖概率由路径损耗、位置、载波传输功率和环境等因素综合决定。此时，空对地通信的路径损耗LdB为

(2)

式中：n0为路径损耗指数；fc为UAV的载频；c为电磁波速度；di,n为UAVn与任务单元i之间的距离。

无线网络传输存在有视距和无视距链路。具体来说，UAVn的有视距概率表示为PLoS,n，而无视距概率表示为PNLoS，n。单架UAVn相对任务单元i覆盖概率qi(Sn)可表示为

(3)

式中：pn为UAVn的载机传输功率；pmin为成功检测时最小功率要求；μLoS，σLoS和μNLoS，σNLoS分别为有视距和无视距链路阴影衰减的均值和方差。

为了研究整个任务区的总覆盖率影响程度，本文引入了任务区重要性的概念。据此，任务单元i的UAV网络覆盖能力gi,N可表示为

(4)

式中：N表示无人机集合；σi表示任务单元i的重要性。因此，进一步推导出UAV全局覆盖效用U0为

(5)

载波传输能力和能量消耗是多UAV是否能完成任务的关键，受UAV通信能效设计的启发[11]，UAV网络的总能量效率G0为

(6)

式中：τ为给定任务要求的覆盖阈值；G0表示覆盖效用的单位功率，G0值越高，表示传输功率越小，覆盖效用越高。因此，该模型可优化为寻找UAV的最优状态Sopt，即

P∶Sopt=arg maxG0。

(7)

2 合作博弈论框架

文献[12]中建立了一个小型网络集中分布式优化体系结构，并将物理小区网络映射为云中的虚拟决策网络，受该方案的启示，本文采用降维的方法来求解该模型。首先，将任务区的环境参数和所有UAV的位置、机载发射功率等信息报告给地面中心，由地面中心负责将UAV网络映射到虚拟决策网络;然后，设计了一种优化方法来解决该问题;最后，将得到的决策结果Sopt分发给UAV，它将根据Sopt调整载波传输功率并传输到指定位置。

2.1 降维求解过程

由于多维策略(位置和传输功率)的存在，求解问题P具有挑战性，通过将P划分为P1和P2来降低策略选择的复杂性，具体降维方法如下。

(8)

(9)

2.2 UAV覆盖最大化中的合作博弈

问题P1和P2是离散优化问题和NP-hard问题，传统集中式算法不能有效解决这些问题，特别是当任务单元的数量很大时更困难。为了应对这一挑战，本文采用博弈论这一有效的分布式多决策问题解决方法，来消除个体决定带来的相互影响。

在节能多UAV覆盖部署模型的博弈论框架中，覆盖问题被建模为R(N，{Sn,n∈N}，{Un,n∈N})，其中，Sn为UAVn的状态。为方便起见，将位置ln和传输功率pn设置为S1,n和S2,n，即S1,n⊗S2,n=SnS，其中，S1,n和S2,n分别为ln和pn的集合，⊗表示笛卡尔积。UAVn的覆盖效用函数Un可以表示为Un=U1,n⊗U2,n，其中，U1,n和U2,n分别为覆盖最大化和功率控制的效用函数。

另外，sn,u1,n和u2,n分别表示Sn,U1,n和U2,n的一个单元。同时，将s-n定义为一组除了第n架UAV外的所有UAV的操作配置文件。因此，提出的节能型多UAV覆盖部署模型是一个合作博弈模型，在该模型中，参与者(UAVn)的效用属于网络中参与者和其他UAV的状态。

根据势博弈的基本定义，势博弈要求参与者在分布式多主体系统中进行合作控制，使每个参与者的局部效用与全局效用相互关联。以下定义用来分析所建立的博弈论框架的性质。

定义1(纳什均衡(NE))。

(10)

定义2(严格势博弈)。

对于效用函数u(sn，s-n)，如果存在一个势函数φ，当任意策略的选择从sn变为s′n时，存在如下关系

μ(sn,s-n)-μ(s′n,s′-n)=φ(sn,s-n)-φ(s′n,s′-n)

(11)

那么这个博弈称为严格势博弈(Exact Potential Game，EPG)，它至少有一个NE点。

在覆盖最大化阶段，假设该模型主要针对合作型UAV，那么存在重叠检测区域的UAV往往具有合作行为。

定义In为UAVn的可探测区域，若In∩Jn≠0，则Jn为UAVn的邻居的集合。同时定义J′n为经过n次新位置选择后的UAVn的新邻居。需要注意的是，所有UAV都有其最大的发射功率，覆盖最大化中基于合作覆盖博弈的效用函数为

(12)

G1:maxu1，n(Sn,SJn) ∀n∈N

(13)

式中，根据目标G1，UAVn的最优局部效用由其水平位置确定。

定理1将多UAV覆盖问题描述为一个合作覆盖博弈问题，参与者采用式(12)的效用函数。合作覆盖博弈G1是一个EPG，并至少有一个纯策略纳什均衡点。另外，覆盖最大化的最优解P1是G1的纯策略纳什均衡点。

证明 首先，将整个覆盖效用构造为势函数，即

(14)

假设任意一架UAVn的状态从sn变为s′n，则由个体策略选择引起的势函数变化如下

φe(Sn,S-n)-φe(S′n,S-n)=

(15)

直观地说，当UAV不在J1，n集合时，其完全不受上述策略变化的影响。那么式(15)中最后两项的结果等于零。此时，根据式(12)和式(15)可得

u1，n(sn,sJn)-u1，n(s′n,sJn)=φe(sn,s-n)-φe(s′n,s-n) 。

(16)

由式(16)可知，当任意UAV改变其行动策略时，其局部效用函数和势函数的变化值是相同的。由此证明了局部利他博弈G1是一个EPG，并且根据定义2具有至少一个纯策略纳什均衡点。而且，设计的势函数对全局覆盖都具有效用，它保证了每个参与者当前的局部效用与全局覆盖效用相互进行关联，因此P1的最优解变为G1的纯策略纳什均衡点。

2.3 UAV功率控制中的势博弈

从式(3)中可以看出，地面单元的覆盖概率不仅由UAV的位置决定，还与载波传输功率有关。图2为给定UAV地面任务单元的覆盖概率与发射功率之间的关系，从图2比较两个不同位置的UAV可知，地面单元的覆盖概率随着UAV发射功率增加而增加，且随着传输功率的增加，覆盖概率将一直接近峰值并逐渐平缓。

图2 覆盖概率随发射功率的变化

注意在当前固定的UAV部署下，一架UAV的功率选择会影响其可探测的任务区域单元的覆盖概率。因此，功率控制问题是一个潜在的博弈问题。为此构建了UAVn的个体效用函数，以捕获最优传输功率分配，即

(17)

式(17)表示UAVn在固定的最优位置下的最佳能效，其由UAVn的载波传输功率决定；在这个过程中，效用函数也满足势博弈的特点，其使每一架UAV的本地效用与全局效用相关联。式中，In为UAVn的探测区域。因此，设计的UAV功率控制模型可以建立一个势博弈模型目标，即

G2:maxu2，n(pn,p-n) ∀n∈N。

(18)

定理2针对UAV最优功率控制问题，以式(15)作为其单独效用函数，那么UAV势博弈G2是一个EPG，并至少有一个纳什均衡点。此外,问题P2的最优解是G2的纯策略纳什均衡点。

证明 首先能量效率效用可以表示为势函数，即

(19)

式中，对于任意传输功率选择从pn变为p′n，计算出的势函数变化如下

(20)

应该指出的是，任务区域不在UAV探测范围内，其完全不受上述策略变化的影响。因此可得

(21)

注意在式(20)和式(21)中，对于任一架UAVn，其势函数和个体效用函数之间的变化值与UAVn的变化一样，其传输功率策略可表示为

φ(pn,p-n)-φ(p′n,p-n)=u2，n(pn,p-n) -u2，n(p′n,p-n)。

(22)

由式(22)可以看出，G2是根据定义1得出的EPG，并且至少有一个纯策略纳什均衡点。另外，设计的势函数针对的是整个覆盖效用，它保证了每个参与的UAV的当前个体效用与整体覆盖效用相关联。因此，问题P2的最优解是G2的纯策略纳什均衡点。

2.4 空间自适应博弈的多UAV节能覆盖部署算法

由于多UAV节能覆盖部署问题被描述为一个EPG问题，因此需要应用学习算法来探索博弈的纳什均衡，以防止UAV策略陷入局部最优状态。基于空间自适应博弈(Spatial Adaptive Play，SAP)的多UAV节能覆盖部署算法的实现过程如下。

算法1：基于SAP的多无人机节能覆盖部署算法。

目标：在覆盖效用限制下最大限度地减少工作功率建立UAV状态剖面的参数，Sn={ln，pn}，n∈N，和任务区域I的状态(σ)，设置合理的迭代次数。

/*步骤1：在最大载波传输功率下的最大覆盖部署*/

While：未达到预定的最大迭代次数 do

随机选择一架UAVj，将其工作功率调至最大。

从受约束位置S1，n中选择一个位置状态lj(t)，产生sj(t)的变化。

选定的UAVj计算任务区域的当前本地覆盖效用u1，j(sj(t)，sJj(t))和期望效用u1，j(s′j(t)，sJj(t))

UAVj根据式(23)选择一个状态，并更新其状态sj(t+1)。

t=t+1。

End while

计算当前UAV网络的全局覆盖效用U0，如果U0>τ，则保存并利用UAV更新后的状态数据Sn，将Sn输入到以下算法中；否则，结束程序并返回。

/*步骤2：在最大覆盖下的最优功率控制*/

While：未达到预定的最大迭代次数 do

在每次迭代中随机选择一架UAVn。

所有其他UAV重复先前的功率选择，即pk(t+1)=pk(t),k∈Jn。

为选择UAVn，计算其效用函数

u2，n(p′n(t),p-n(t))，不同功率选择p′n∈S2，n/pn，以及电流效用函数u2，n(pn(t),p-n(t)) 。

UAVn根据式(24)更新其功率选择策略。t=t+1。

End While

二进制对数线性学习被证明能保证收敛到最优纳什均衡，用于探索UAV的最优覆盖部署[13]。UAV的行动选择概率函数为

(23)

式中，t表示迭代次数。考虑到多智能体决策的复杂性，采用了一种分布式学习算法用于功率控制。因此，采用空间自适应博弈方法可将传输功率收敛到稳定的分配状态，UAVn的功率选择概率函数为

qn(t)=

(24)

式中，β为学习参数,β>0。

3 实验结果与分析

本章将进行模拟实验以评估所提出方法的有效性。实验中，将UAV通信网络的载波频率设置为2000 MHz，其中，μLoS=1 dB，μNLoS=20 dB，n0=2.5。此外,假设每架UAV都配备了16根天线，即N0=16。考虑到四旋翼UAV的实际需求[13]，设置了一些合理的离散传输功率选择，即pn∈{32，34，36，38，40，42，44，46，48，50}(单位为dBm)，n∈N。另外，设置覆盖阈值τ=0.6，即在不确定策略下的全局覆盖效用必须大于或等于0.6以满足通信要求，根据算法设计模拟过程将其分为两个步骤进行计算。

3.1 覆盖效用分析

假设任务区的信息已知，在此将任务区统一划分为50×50个单元(每个单元的长度为200 m)，任务区的设计概率密度函数服从正态分布。图3所示为不同的UAV数量时的全局覆盖效用U0的变化。当部署5架或更多UAV时，结果可以最终收敛到稳定状态。但当部署4架UAV时，覆盖概率小于0.6，不能满足通信需求，无法进行功率控制。

图3 不同的UAV数量时的总覆盖效用

3.2 基于SAP算法最优覆盖部署分析

前文的计算都是在UAV的数量预先给定的情况下进行的，为了更好地评价所提出方法的效果，将UAV的数量设置为8来验证仿真的有效性，结果见图4。

图4 8架无人机最优覆盖部署

图4(a)为8架UAV在最大载波传输功率下最优覆盖部署的覆盖概率分布图。从图中可以看出，单架UAV离某一特定区域越近，其覆盖性能就越高，而且UAV重叠检测区域的颜色较深，表明多UAV协同检测可以提高检测概率。同时，如果没有紧密部署不同类型的UAV，会导致覆盖效用不足。图4(b)是计算全局覆盖效用U0的收敛性随着迭代次数的变化。为了消除偶然性影响，本文在步骤1中进行了10次计算(见图4(b)中opt.1～opt.10)。从图4(b)中曲线可以看出，总覆盖效用总会收敛到某个特定值，该结果表明此方法至少存在一个纳什均衡点。

3.3 基于SAP算法的最优功率控制分析

由于仿真结果满足通信要求，接下来对UAV高效节能的输电功率分配进行了研究。从图4(b)的放大图中可以看出，选择算法中执行步骤2得到的第10条曲线，其结果也收敛于一个稳定的解τ=0.6。这表明根据上述理论分析，提出的SAP算法可以将结果收敛到纳什均衡点。图5(a)给出了最优部署下最优功率控制覆盖概率分布图。同时，图5(b)给出了UAV发射功率选择的收敛状态，其中每条曲线代表UAV选择的不同发射功率。从图5(b)可以看出，在大约110次迭代之后，每条曲线都收敛于稳定状态，证明了提出的功率控制方法至少有一个纳什均衡点。

图5 SAP算法的最优功率控制分析

图6为所有UAV的传输功率收敛情况，图7为迭代过程中UAV总能量效率G0的变化情况。图6和图7的结果说明了SAP算法的正确性、有效性和收敛性。更重要的是，在探索最优功率选择策略以使UAV网络总能量效率最大化的同时，UAV的总传输功率也趋向于收敛到最小的结果。

图6 所有UAV载波传输功率的收敛图

图7 在迭代过程中UAV总能量效率的变化

4 结论

针对UAV协同覆盖和节能通信技术方面存在的问题，本文提出了一种基于博弈论的多UAV覆盖部署策略，通过计算得到如下结论：

1) 通过准确描述UAV之间的协作关系，构建了一个多UAV协同覆盖部署模型，通过仿真模拟实验验证了该方法的有效性和模型的可靠性；

2) 采用集中分布式优化体系结构，将多维策略问题分为覆盖最大化和功率控制两个步骤，并采用基于空间自适应博弈的多UAV节能覆盖部署算法证明了纳什均衡点的存在；

3) 通过引入能量效率，构建了UAV覆盖场景来解决能量短缺问题，可使覆盖场景更加可靠和有效，在实际的多UAV协同通信场景中具有很大的应用潜力。