基于混合策略博弈的无人机辅助移动边缘计算任务卸载

摘 要：在单无人机辅助的移动边缘计算系统中， 为使无人机能服务于大区域中的所有用户设备， 可将大区域分成多个子区域， 并设定无人机以固定路线在各个子区域间飞行来为用户设备提供计算服务。 考虑到用户设备计算资源较匮乏且无人机覆盖区域外的用户可选择移动至覆盖区域内进行任务卸载以最大化自身效用， 可将用户设备的部分卸载问题转化为每个用户设备的效用最大化问题， 并利用混合策略博弈和子模博弈来分别确定用户设备的移动概率和卸载数据量， 从而得出最优卸载策略， 且分别证明了混合策略纳什均衡和纯策略纳什均衡的存在性。 仿真结果表明， 所提方案与MBO（Binary Offloading Based on Mixed Strategy Game）等经典方案相比可有效提高用户设备的效用， 并验证了其收敛性和稳定性。

关键词：无人机； 移动边缘计算； 计算卸载； 混合策略博弈； 子模博弈

中图分类号：TJ760； V279

文献标识码：    A

文章编号：1673-5048（2024）04-0112-09

DOi： 10.12132/iSSN.1673-5048.2023.0246

0 引  言

无人机（Unmanned Aerial Vehicle， UAV）因其具有灵活性高、 成本低、 鲁棒性强等诸多优点， 已广泛渗透至交通监管、 公共安全、 搜救等多个行业。 由于无人机的高海拔使无线设备能够有效地建立通信链路， 从而减轻潜在的信号阻塞和阴影， 因此无人机可以充当无线中继或空中基站， 扩大地面无线设备的覆盖范围［1］， 这一优势也促进了其在物联网和边缘计算等新一代通信技术中的推广应用。

移动边缘计算（Mobile Edge Computing， MEC）是为解决终端设备资源匮乏， 无法满足各类时延敏感型和计算密集型任务需求的问题而提出的一种有效方法［2］。 将计算任务卸载到离终端设备更近的MEC服务器， 不仅为任务的执行提供了较充足的计算资源， 而且相比云计算， 在传输过程中产生的时延和能耗成本也显著降低。 相对于固定的边缘服务， UAV搭载的边缘服务器具有更高的灵活性， 可以获得良好的空对地视距［3］。 此外， 突发事件发生时， 在基站受损、 地面服务器难以快速部署的情况下， UAV辅助的MEC系统可以很好地弥补传统边缘服务器的不足， 为用户提供灵活且高质量的计算服务。

目前已有很多相关UAV辅助的MEC系统的研究。 文献［4］研究了UAV辅助的MEC系统中相关公平感知的任务数据分配和轨迹优化问题， 目的在于最小化移动终端的能耗。 文献［5］解决了非均匀异构蜂窝网络移动用户的计算卸载问题， 提出一种面向小区边缘移动用户的基站协作和地空卸载方案， 并采用定期调度的方式使边缘用户可在地面基站和无人机之间进行选择卸载。 此外， 该文也提出了分析频谱效率和平均网络吞吐量的框架。 文献［6］设计了一个基于贪婪算法的无人机轨迹模型来预测用户坐标， 并为用户选择合适的边缘服务器进行卸载， 从而联合优化无人机的通信、 缓存和计算的能源效率。 文献［7］通过联合优化用户关联和无人机部署， 最小化MEC排队延迟，  从而降低任务的平均延迟。  此外， 引入了最优传输理论来分析用户关联子问题， 采用经典粒子群优化算法来优化无人机部署。 文献［8］研究了一种基于蜂窝连接的多UAV辅助的MEC网络， 联合优化无人机-地面基站的关联卸载、 无人机发射功率、 无人机轨迹和能量收集时间， 从而最小化无人机的总能量消耗， 并提出一种基于联合块坐标下降的资源分配和无人机轨迹算法， 以解决整体优化问题。 上述文献主要解决的是最小化UAV辅助的MEC网络中的任务执行能耗和时延等成本问题， 并未考虑设备在卸载过程中的收益， 而且大部分文献都以研究UAV的移动轨迹为主， 而较少研究可移动用户设备之间的协作。

博弈论可解决在多个决策主体间存在利益冲突的情况下， 利益相关者或参与者如何根据决策者自身的能力和决策者掌握的信息做出有利于决策者自身的决策， 适用于MEC场景中各个用户之间决策相互影响的情况。 文献［9］通过最小化系统中多个UAV的总能耗来确定任务的卸载目标， 提出服务器选择博弈算法SSGT， 并提出一种卸载激励机制为MEC服务器的资源定价， 将无人机的能耗和移动用户的意愿建模为Stackelberg博弈， 基于算术下降的多轮迭代博弈算法来实现最优解。 文献［10］提出一个针对UAV辅助的MEC系统中基于非合作博弈的两阶段计算卸载策略。 第一阶段通过动态调整移动用户的CPU频率和传输功率， 实现社会效益的最大化； 第二阶段针对无人机计算资源的分配进行优化， 旨在最小化无人机在此过程中的能源消耗。 文献［11］提出一种基于博弈论的GTCS方法， 用于在MEC和无人机网络中选择最合适的无人机服务提供商。 通过考虑用户需求和无人机提供商的特点、 限制和价格， 利用博弈论选择最佳的服务提供商。 文献［8］提出一种在灾难或偏远地区为物联网设备提供空中计算服务的计算框架。 首先基于匹配博弈理论处理物联网设备到无人机的卸载决策， 然后利用启发式算法处理无人机和高空平台之间的卸载决策。 上述文献说明利用博弈论算法解决计算卸载问题可以更全面地考虑卸载过程中其他用户以及无人机对用户决策带来的影响是可靠且有效的。

本文主要研究了无人机辅助的移动边缘网络中的计算卸载策略。 为了使区域内所有用户设备（User Equipments， UEs）都有卸载任务至UAV的机会， 规定无人机按照固定路线飞行过所有子区域， 并且服务区域外的UE可根据自身效用情况判断是否移动到该时隙的UAV服务覆盖范围。 首先利用混合策略博弈计算UE的移动概率， 并结合UE和UAV的偏好函数构建双边匹配博弈， 确定区域内可服务的UE。 然后将UE的部分卸载问题转化为每个UE的效用最大化问题， 并作为UE之间的非合作博弈进行处理。 在子模博弈理论的基础上， 证明了该非合作博弈存在纯纳什均衡点， 并利用最佳响应算法获得UE的最佳卸载数据量。

1 系统模型

图1给出了一个包含多个UE和搭载MEC服务器的UAV的两层网络架构， 其中UE的集合可表示为K{1， 2， …， K}。 该网络模型利用软件定义网络（Software Defined Network， SDN）技术实现了集中式的控制和资源管理， 使得基于UAV的MEC系统能够高效地为服务覆盖区域内的UE提供服务。 系统内的基站可以将包括UE位置、 UAV位置、 数据信息等实时信息进一步分发给各UE和UAV， 进行所需的信息交换。 基于这一机制， 设UAV能够获取服务区域内所有UE设备的先验信息。

设定系统在T时隙序列中运行， 整个序列可定义为T{1， 2， …， T}。 第k个UE在每个时隙都有一个需要执行的任务， 可具体表示为fk（t）={bk（t）， ak（t）}， 其中： bk（t）为计算任务所需输入的数据量； ak（t）表示任务的计算密度， 即计算任务所需的CPU周期与任务数据量之间的比例。 由于UAV服务的区域一般较大， 为了让大面积区域内所有UE都有被服务的机会， 整个区域被平均分割成若干个子区域， 并设定UAV采用巡逻的方式在各个子区域之间按照固定路线飞行。 出于服务的公平性， UAV处理任务时悬停于每个子区域的中心位置的正上方。 由于UE自身资源有限且每个UE都是自私的， 为了获得UAV的服务权限， 服务覆盖区域之外的UE有可能会移动到UAV的覆盖区域， 将部分任务进一步传输到UAV上的MEC服务器来执行， 而这样会导致选择移动的UE与原本在服务覆盖范围内的UE在资源上竞争， 因此需要制定一个有效的移动策略使得每个UE都能获得最大的收益。

系统中的每个时隙都可以分割为两个部分： 第一部分为UAV的飞行时间tf； 第二部分为UE的任务处理时间tp。 考虑一个3维的欧几里得空间， 设定UAV在UE的任务处理时间内保持固定位置且具体位置可以表示为s（t）=［x（t）， y（t）， H］， 其中： x（t）， y（t）表示UAV在时隙t的水平位置； H为UAV的固定飞行高度。 为了防止UE无法接收到任务处理的结果， tp不小于UE移动的最大时延以及执行任务的最大时延之和。 移动最大时延和任务执行最大时延分别用离UAV最远的UE移动至服务覆盖区域的时间和所有UE本地执行任务的最大时延来表示， 即tp≥Tmo， max（t）+Tl， max（t）。 第k个UE在第t个时隙的位置为wk（t）=［xk（t）， yk（t）］， 可得UAV与各个UE之间的空间距离为dk（t）=H2+（x（t）－xk（t））2+（y（t）－yk（t））2， 水平距离为lk（t）=（x（t）－xk（t））2+（y（t）－yk（t））2。

1.1 通信模型

设定UAV与UE之间的通信信道为视距（Line of Sight， LOS）传输链路［12］， 对每个时隙t， UAV和UE之间的信道功率增益为

hk（t）=g0·（dk（t））－2 （1）

式中： g0为基准距离等于1 m的情况下的信道增益。 设定系统采用正交频分多址的通信制式并且具有服务权限的UE平均分配MEC服务器中的资源， 那么在第t个时隙， 第k个UE与UAV之间的信息传输速率可表示为

rk（t）=BY·log21+τk·hk（t）N0（2）

式中： B为系统带宽； Y为UAV在一个时隙内可以服务的UE数量； τk为第k个UE的传输功率； N0为白噪声功率。 若第k个UE选择将任务卸载到UAV搭载的MEC服务器上处理， 则上行链路的传输时延可表示为

Tutk（t）=buk（t）rk（t）（3）

式中： buk（t）表示第k个UE在时隙t卸载至UAV的数据量。 在卸载过程中UE的能耗为上行链路所需要的传输能耗。 需要说明的是， 由于任务处理结果的数据量一般较小， 因此本文不考虑UE接收任务处理结果需要的时间和消耗的能量。 在此情况下， 传输能耗可以表示为

Eutk（t）=τk·buk（t）rk（t）（4）

1.2 计算模型

设定UE所需执行的任务可任意划分为两部分， 由于UE的能量不足且计算资源有限， 所以当UE位于UAV的服务范围时， 为了减小能耗和时延成本并获得最大收益， 可将部分任务卸载至UAV上的MEC服务器进行计算。 定义fu为UAV搭载的MEC服务器的计算频率， Y为UAV每时隙可以服务的UE数量， 并且计算资源同样平均分配给每一个确定卸载的UE， 那么可得MEC服务器在第t个时隙处理第k个UE任务的计算时延为

Tuek（t）=buk（t）·ak（t）·Yfu（5）

在UE卸载部分任务至MEC服务器的同时， UE本地也需执行未传输至服务器的部分任务。 UE本地执行剩余任务的时延和能耗为

Tulk（t）=（bk（t）－buk（t））·ak（t）fk（6）

Eulk（t）=κ·（fk）2·（bk（t）－buk（t））·ak（t）（7）

式中： fk为第k个UE的计算频率； κ为CPU的有效电容系数（其取决于其处理芯片的结构）。 结合通信模型和计算模型可以得到， UE在MEC上的计算时延为

Tutek（t）=Tutk（t）+Tuek（t）（8）

当UE选择以部分卸载的方式执行任务时， UE的任务执行时延需要综合考虑本地执行的时延Tulk（t）和卸载至MEC服务器执行的总时延Tutek（t）， 并取两者中的最大值作为任务执行的实际时延。 而部分卸载时UE的任务执行能耗则是UE本地的计算能耗Eulk（t）与其传输能耗Eutk（t）之和。 因此当UE选择将任务卸载至MEC服务器时， 任务执行时延和能耗可分别表示为