基于无线能量传输的移动边缘计算联合资源分配

杨 霁 张 林 向 菲 姚楚楠

1(国家电网重庆市电力公司 重庆 400010) 2(重庆大学 重庆 400044)

0 引 言

近年来，无线传能(Wireless Power Transfer, WPT)和移动边缘计算(Mobile Edge Computing，MEC)技术先后被提出并得到广泛研究，前者目的在于降低移动设备对有限容量电池能量供给的依赖，而后者可以有效解决网络业务快速增加带来的高负荷问题[1]。然而，如何有效融合WPT与MEC技术从而进一步提高网络能效和成本效率尚未有充分研究，这是本文工作关注的焦点。

在WPT与MEC融合研究上，学术界已经有初步成果[2-10]。针对二分迁移，文献[2]讨论多用户计算模式选择与传输时间分配以最大化多用户计算速率和问题，作者提出一种基于交替方向乘法器分解的联合优化算法。针对部分迁移，文献[3]讨论无线传能多用户MEC，在给定计算时延为约束下，研究联合优化基站的能量发射波束、中央处理单元(Central Processing Unit，CPU)频率和用户迁移任务量以最小化基站的总能耗，并利用拉格朗日对偶法推导获得最优解的半闭式形式。文献[4]研究基于时分多址的无线传能多用户MEC系统中迁移决策和资源分配，联合优化基站能量发射波束、任务迁移和所有用户的时间分配，以最大化所有用户的计算速率加权和为目标，并基于凸优化理论推导获得最优解的半闭式表达式。文献[5]研究多用户WPT-MEC系统中能量效率和时延折中，以系统稳定性、CPU频率、传输功率峰值和能量因果性为约束，提出一种能实现能效与时延折中的优化方案。针对基于无人机无线传能MEC系统，文献[6]分别研究部分迁移和二元迁移模型下资源分配，以能量采集因果约束和无人机速率为约束，联合CPU频率、用户迁移时间、用户发射功率和无人机轨迹，分别提出一种两阶段算法和一种三阶段替代算法获得最优CPU频率、用户迁移时间和用户发射功率的闭式解。文献[7]研究基于信能同传的多用户MEC系统中联合迁移决策和资源分配，以最小化设备总能耗为目标，优化迁移决策以及用于捕获能量、解码信息的时间、本地计算/迁移计算和迁移功率，进一步分析了路径损耗和任务复杂度对系统性能的影响。文献[8]研究基于信能同传的多用户系统中计算迁移与能量传输资源分配与功率控制，以最小化设备能耗为目标，联合优化设备时钟频率、发射功率和迁移决策。基于微分凸函数规划和线性规划交替优化，设计了一种优化时钟频率控制、传输功率控制、迁移比和功率分配比的迭代算法。文献[9]研究全双工WPT-MEC系统中最大最小能量效率优化，基于广义Dinkelbach算法和变量替换设计了一种迭代算法来获得全局最优解。

可以看出，尽管目前针对移动边缘计算与无线能量传输融合的联合资源分配问题已有初步研究[2-9]，但从问题模型角度来看，针对无线传能使能多用户基于TDD-OFDMA执行迁移计算的联合多维度资源分配问题还未有讨论。事实上，讨论无线传能使能与基于TDD-OFDMA执行迁移计算对于推动相关技术在基于TDD双工与OFDMA多址接入技术的TD-LTE系统中的应用具有重要意义。因此，本文针对时分双工正交频分多址无线传能使能移动边缘计算网络，在保证用户任务截止期要求下，研究联合多用户信道分配、上下行时间分割与功率控制以最小化系统能耗问题。由于所建模型优化问题为混合整数非线性规划非凸问题，缺乏普适性的求解算法框架，本文提出基于问题分解的次优算法设计方法，首先给出启发式信道分配算法，随后在给定信道分配下的次优联合功率与上下行时间比例分割算法，最后对算法性能进行了验证分析。

1 系统模型与优化模型

1.1 网络模型

图1 基于TDD-OFDMA的WPT-MEC系统模型

(1) 双工模式：WPT-MEC网络工作于时分双工(Time Division Duplex，TDD)模式[8-10]，即上下行基于正交时间块，下行为基站到用户的无线传能，上行为用户任务上行迁移传输。假设用户计算任务有相同截止期T，即系统需要在时间T内完成下行能量采集、上行任务迁移及计算。定义T内，用于下行传能时间比例为τ，0<τ<1，剩余时间片用于上行任务迁移计算。与现有工作一样[3,6,9,11-13]，假设用户与基站间信道为准静态衰落信道，信道相干时间大于T，信道上下行满足互易性且系统有完全信道状态信息。

1.2 信道分配模型

(1)

(2)

此外，为确保所有用户均能在时间块T内完成计算任务迁移，基站将分配至少1条子信道给每个用户且每个子信道最多分配给1个用户，因而信道分配需满足:

(3)

(4)

(5)

1.3 能量采集模型

(6)

(7)

(8)

如文献[12]，这里假设边缘服务器计算能力强大且计算反馈数据量小，因此忽略任务计算和结果反馈时间。

综上，用户采集能量应不大于其能耗，因而有：

(9)

1.4 任务迁移模型

(10)

(11)

(12)

(13)

1.5 能耗模型

基站能耗由三部分组成[3,10]：(1) 基站运行静态能耗EB；(2) 基站下行无线传能能耗EBD；(3) 基站边缘服务器计算能耗EMEC。其中：EB在计算时间T内为常数；EBD取决于信道分配、WPT功率分配和τ。

(14)

边缘服务器计算能耗正比于迁移任务数据量，用a表示边缘服务器单位比特计算能量[8]，这里采用如下线性模型刻画边缘服务器计算能耗：

(15)

因此，基站总能耗为:

(16)

1.6 优化模型

针对式(16)，由于基站静态能耗为常量， 虽然MEC服务器计算能耗与任务数据量成正比，但在给定用户计算任务后MEC服务器计算能耗也为常数，而基站下行无线传能能耗EBD与用户资源配置相关。因此，在研究传输与资源分配时，仅考虑下行无线传能能耗。则系统能耗优化面临如下问题：

P1

(17)

C3:0<τ<1

式中：C1为子信道分配约束；C2为子信道发射功率约束；C3为上下行时间分割因子约束；C4为上行迁移速率约束；C5为用户能耗约束，表示每个用户消耗的总能量不能大于该用户采集的总能量，也不能大于基站分配给每个用户用于传能所消耗的能量；n*满足式(5)。

需要指出的是，尽管目前针对移动边缘计算与无线能量传输融合的联合资源分配问题已有初步研究[2-13]，但从问题模型角度来看，关于无线传能使能与多用户基于TDD-OFDMA执行迁移计算的上下行联合资源配置，即联合优化上下行时间分割、多用户信道分配与功率控制的多维资源分配问题还未有讨论。事实上，讨论无线传能使能与基于TDD-OFDMA执行迁移计算对于推动相关技术在基于TDD双工与OFDMA多址接入技术的TD-LTE系统中的应用具有重要意义。另外，从数学结构上来看，由于所建模问题属于典型的混合整数非线性规划(Mix-Integer Non-Linear Programming, MINLP)，既包括上下行信道分配离散决策变量，又有上下行功率分配与时间分割因子连续决策变量，而目前关于MINLP问题缺乏普适性求解方法。为此，本文在分析建模问题结构基础之上，借助于交替优化思想[6,12]，设计问题结构驱动的次优算法从而求解原始非凸混合整数优化问题。

2 联合上下行资源分配和功率控制算法

如前所述，由于问题P1属于典型NP-难的混合整数非线性规划(MINLP)，缺乏普适性求解方法。依据所建模问题特殊的结构特性：即给定信道分配下，用户功率分配可解耦，而时间分割因子可通过一维搜索。本文寻求启发式低复杂度算法求解该问题。具体求解思路是：将原问题P1分解为信道分配子问题和联合功率分配与上下行时间分割比例因子优化子问题。对于信道分配子问题，基于用户任务数据量与信道增益大小排序关系，提出一种启发式信道分配方法；在给定信道分配下，进一步研究联合功率分配与上下行时间分割比例因子优化问题，提出一种基于时间分割比例因子搜索与基于注水的能效交替迭代算法。

2.1 信道分配算法

由于信道分配子问题本质上属于典型NP-难的0-1整数规划问题，难以直接获得普适性最优解算法，为此，本文提出一种启发式算法，其基本思想是：依据用户迁移传输数据量与信道增益大小排序关系来执行次优信道配置。该设计的理论依据是：多用户具有相同的上下行时间分割比例因子，为了降低系统能耗，应该给迁移传输数据量大的用户分配更好的信道，但如果将全部好信号分配给单个用户将导致其他用户能耗过高，因此好信道需要在多用户之间平衡分配。该算法思想的性能增益将在算法对比分析中进行验证。具体地，算法详细流程如算法1所示。

算法1基于任务优先级的周期性信道分配算法(Cyclic Channel Allocation based on Task Priority, CCA-TP)

阶段1：首先依据计算任务数据量定义用户优先级对用户排序，然后按照信道功率增益大小对子信道排序

阶段2：基于阶段1排列结果为各用户周期性分配信道子集

6.1.1.当信道未被分配即xn=0时，xn=1,xk,n=1；

阶段3：基于阶段2获得的信道子集选取传能信道

2.2 能效功率分配算法

在给定信道分配后，原P1简化为固定用户信道分配下的联合上下行功率分配与上下行时间分割比例因子优化问题如下：

P2

(18)

C2:0<τ<1

P3

(19)

对于P3，利用反证法不难得出如下两个结论，为简化描述这里省略证明过程。

(20)

(21)

基于上述命题，由P3可知目标函数由基站到各用户传能之和构成。此外，所有约束条件在不同用户之间相互独立。因此，可将P3转换为P4，即在满足上下行能耗与速率约束以及给定下，各用户传能能耗最小。

P4

(22)

P5

(23)

算法2能效功率分配算法(EE-PA)

4.如果pk,n<0，则i←i-1，跳转到3；否则，跳转到5；

基于P5最优解，可直接计算各用户下行传能信道发射功率和传能能耗，即

(24)

由于P3的解是在给定参数τ下获得，但并未给出获取最优τ的方法，此外，观察可知理论上分析τ与系统能耗关系十分困难。为此，本文提出定步长一维搜索算法(Fixed Step One-dimensional Search Algorithm, FS-OS)来获取最优τ，即对于τ∈(0,1)，定义初始值τ0→0+和步长Δ，按照τ=τ0+(i-1)Δ执行τ迭代；在每个τ值下求解P3；最后选择获得最小系统能耗的τ值作为最优值。算法流程如算法3所示。

算法3定步长一维搜索算法(FS-OS)

1. 初始化τ=τ0，τ∈(0,1)，搜索步长为Δ；

2.基于算法2，计算当前τ值对应P3最优解；

3.更新τ=τ+Δ；

2.3 基于能效的上下行资源分配和功率控制算法

综上，针对P1提出基于能效的资源分配和功率控制算法(Energy Efficiency-based Resource Allocation and Power Control Algorithm, EE-RAPC)，即算法4。首先基于算法1完成用户信道子集分配；接着利用FS-OS算法获得的τ搜索最优上下行时间比例分割因子，并基于τ执行上下行功率调整；最后选择具有最小系统能耗的τ和对应的上下行功率分配作为P3的解，最终输出最优上下行时间比例分割因子τ、上下行功率分配和信道分配。

算法4EE-RAPC算法

1. 基于算法1完成用户子信道集分配；

2. 基于算法3计算给定信道分配方案下P3最优解及最优τ*值；

3 仿真分析

本节对EE-RAPC算法性能进行分析。为对比引入两种次优参考算法，即任务优先信道分配算法(Task Priority, TP)和上行链路等功率信道分配算法(Uplink Equal Power, UEP)。其中，TP算法与EE-RAPC算法相似，不同之处在于，在针对各用户分配信道子集时优先为用户分配信道增益大的所有子信道，若当前子信道已被其他用户占用，则按照信道增益从大到小依次选择子信道。UEP算法也与EE-RAPC算法相似，不同之处在于用户上行链路各子信道基于等功率的功率分配准则。相关仿真参数设置如下：子信道数为64，子信道带宽Ws= 31.25 kHz，噪声功率为10-9W，用户EH模块的能量转换效率ζ=1，路径损耗因子为3，小区半径为10 m。在性能分析时，将围绕用户平均能耗、系统总能耗和信道利用率等指标，仿真结果图中任意数据点都是20 000次蒙特卡洛仿真结果平均。

图2是三种算法下用户平均能耗随用户数变化曲线。此时，任务截止期，各用户迁移任务数据量在区间(5 000,15 000) bits上均匀分布取值。可以看出，EE-RAPC算法和TP算法用户平均能耗随用户数增多而变大，其原因在于：用户数增多导致用户上传数据量增多，此时基站需要传输更多能量给这些用户；此外，当子信道数不变时，用户数增多导致用户平均可用信道数变少，用户获得更好信道的概率变小，导致用户获得单位能量时基站下行传能增加，用户任务数据上行速率变小能耗增大。对于UEP算法，其用户平均能耗先下降后随用户数增加开始上升，其原因在于：UEP算法采用CCA-TP算法执行信道分配，但任务迁移阶段采用上行传输等功率分配，用户在得到较多子信道时会使得分配相同功率在低增益信道上造成能量浪费，因而平均能耗先下降后上升。还可以看出，EE-RAPC算法的用户平均能耗性能优于TP算法和UEP算法，且在信道数/用户数比值趋于1时三种算法性能逐渐收敛到相同值，这符合理论与直觉分析。

图2 平均用户能耗随用户数变化曲线

图3为系统总能耗随平均用户子信道数变化曲线。可以看出，三种算法(EE-RAPC算法、TP算法和UEP算法)的系统总能耗均随用户分配子信道的增加而减小，EE-RAPC算法能耗表现最优，其原因在于：随着为用户分配子信道的增多，各用户用于传能的信道选择也变多，系统能够分配信道增益大的子信道给用户，用户用于上行迁移的信道增多也会优化能耗，所以三种算法的系统总能耗会随用户分配子信道的增多而整体降低，EE-RAPC算法的信道分配较TP算法更均衡，任务迁移较UEP算法更优，故其能耗最低。随着用户信道数的增加，三种算法的能耗减小幅度逐渐变小，主要原因是随着子信道变多，信道环境整体变好，各用户均能分配到信道状态较好的信道子集，而随着子信道继续增加，不会导致更明显的性能提升，所以优化幅度变小。

图3 系统总能耗随用户信道数变化曲线

图4为用户平均能耗随平均任务数据量变化曲线，可以看出，在三种算法下，用户平均能耗均随平均任务数据量增大而增大，其原因在于：随着平均任务数据量的增大，需要迁移计算的数据量变多，用户需要收集更多能量用于数据迁移，整体能耗也将增加。此外，还可以看出，当用户迁移计算任务数据量较小时，TP算法与UEP算法的用户平均能耗性能差异较小，随着用户迁移计算任务数据量的增加，两种算法对应的用户平均能耗逐渐增大，其原因在于：当迁移任务数据量较小时，在当前环境下所能优化的信道分配与EE-PA算法的优化效果较为折中，即信道分配的优化性能与传能迁移过程中最小能耗的优化性能较平均；随着迁移任务数据量的增加，两种算法的信道分配方案不变，各信道将分配更大功率用于迁移，但EE-PA算法优化能耗效果会更显著。此外，三种算法中，EE-RAPC算法在任意用户迁移计算任务数据量下都获得了最小用户平均能耗。

图4 用户平均能耗随平均任务数据量变化曲线

4 结 语

本文针对现移动边缘计算与无线传能使能融合在多用户与时分双工及正交频分多址接入系统研究上的不足，讨论WPT使能基于TDD-OFDMA的MEC网络研究联合多用户信道分配、上下行时间分配与功率控制以最小化系统能耗问题。由于所建模问题属于典型NP-难MINLP问题，缺乏普适性方法。基于问题结构的特殊性，提出启发式信道分配算法，以及给定信道分配下基于交替优化的次优联合功率与上下行时间比例分割算法。算法数值仿真分析结果表明，在不同系统参数配置下本文算法在平均用户能耗与系统总能耗上均优于参考机制，验证了本文算法的有效性。