能量收集下的D2D-MEC 计算卸载

曾耀平，刘月强，关赛莘，江伟伟，夏玉婷

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

在5G 和人工智能快速发展下，计算密集型和潜在关键型应用急剧增加(如虚拟现实、自动驾驶和大规模实时视频监控)[1-2].由于设备资源和计算能力有限，难以满足这些应用程序的计算需求.D2DMEC(device-to-device mobile edge computing)技术应运而生，它整合了移动边缘计算与D2D 通信技术[3]，旨在改善通信性能、降低延迟，并减轻核心网络负担[4-6].

现有的D2D-MEC 研究大多忽略了D2D 通信中的社会关系属性，这在很大程度上影响了D2DMEC 系统[7-9]的性能.Gao 等[8]提出通过用户的社会关系决定D2D 传输过程的功率分配和D2D 连接的补偿机制.Li 等[9]设计存在社会关系的中继设备选择机制，使更多的设备参与了D2D 的合作计算.关于社会意识的D2D-MEC 网络中的长期随机优化问题及资源分配问题仍存在许多不足.

李雅普诺夫优化方法可以根据实时输入的数据在线计算系统控制参数，解决了长期时变的问题.Sun 等[10]研究在D2D 辅助的MEC 系统中，使用李雅普诺夫优化理论进行UEE 和网络稳定性之间的权衡，但没有考虑D2D 之间的匹配问题.Jiang 等[11]研发了新的支持MEC 的多请求者协作者模型，但是没有考虑协作者卸载到MEC 的计算过程.Long 等[12]研究具有社会感知的长期D2D 协作MEC 网络节能计算卸载框架，但仅考虑了D2D 之间的一对一卸载，所使用的匹配理论算法复杂度较高.此外，传统电池供电设备的总能量有限[13]，可能会因为能量耗尽而导致计算性能受损.

针对上述问题，本文提出考虑不同设备下能量收集(energy harvesting,EH)技术和用户间社会信任关系的D2D-MEC 网络架构，此架构可以有效地降低系统的能量损耗，提高D2D 链路的安全性.设计基于李雅普诺夫的在线决策和资源分配(online decision matching and resource allocation,ODMRA)算法，最小化所有用户的长期平均服务成本，将原始随机优化问题转化为单时隙独立的确定性问题，然后分别求解.仿真结果验证了ODMRA 算法在系统服务成本和队列稳定性方面具有性能优势.

1 系统模型

如图1 所示为能量收集下的D 2 D 辅助MEC 网络系统，由物理域和社会域2 个部分组成.其中物理域由一个配备MEC 服务器的基站(base station,BS)和多个移动设备组成.移动设备分为远程发送设备(distant transmitters,DTs)和近端发送设备(nearby receivers,NRs)2 种类型，其中DTs 的集合为 N，NRs 的集合为 K.考虑细粒度的卸载方式，DTs 生成的任务可以在本地、NRs 和MEC 服务器上3 处并行执行.定义(t)为DTi在时隙t 内执行的任务量.由于DTs 与BS 距离较远，信道连接很差，DTs 不能直接将任务卸载到MEC 服务器.NRs 距离BS 较近，且有空闲的计算能力来协助DTs 计算任务.Dij(t)为从 DTi 传输到NRj 的任务量，其中NRj 为在时隙t 内执行(t)的数据量，由于NR 处的计算和传输能力有限，剩余的数据量在NR 处的任务缓冲区中等待进一步执行.

图1 能量收集下的D2D 辅助MEC 网络系统模型图Fig.1 System model of D2D-assisted MEC network with energy harvesting

将时间离散为时隙的形式，用 t∈T表示，其中每个时隙长度为 τ0.引入二进制指示器 xij(t)表示用户的关联决策[14]，在每个时隙开始的时刻，DTi 通过D2D 卸载决策 xij(t)决定卸载到哪个NRj，若DTi 决定将任务卸载到NRj，则 xij(t)=1，否则 xij(t)=0.一个DT 在一个时隙内只能将任务卸载到一个NR 上，一个NR 最多辅助 Nmax个DTs，因此D2D 设备间关联的约束条件如下.

假设DTi 在每个时隙产生的计算任务量为Ai(t).在不失一般性的情况下，Ai(t)在每个时隙内服从 Ai(t)∈[Amin,Amax]的均匀分布，即任务量服从E[Ai(t)]=λi的独立同分布函数.由于下行传输中任务的数据量较小，忽略数据返回能耗和传输时间.

本节阐述了物理域中移动设备的基本关系.物理域包含队列模型、传输模型、任务计算模型和EH 模型，其中每个DT 和NR 对应社会域中的单个用户.在社会域中，将用户之间的社会关系量化为社会信任矩阵后，作为D2D 匹配过程中决策选择的重要依据.下面详细介绍各个模型.

1.1 任务队列模型

由于D2D 的传输速率大于本地任务的生成速率，DT 生成的任务在本地计算一部分后，剩余部分可以通过D2D 快速上传到匹配的NR 上.一个NR 最多可以接收 Nmax个DT 的部分计算任务，考虑本身计算能力的限制,在每个NR 处都设置任务缓冲区 QNjR(t)，用于储存从DT 卸载到NR 上的任务.NR 处过多的任务量将存储在任务缓冲区中，在后续的时隙中进行计算或卸载.QNjR(t)可以用下式表示：

1.2 传输模型

为了避免不同卸载用户间的严重干扰，系统采用正交频分多址（OFDMA）技术.D2D 传输过程中分为N 个相同大小的子信道，从NRj 卸载到MEC 的可用带宽被划分为K 个相同大小的子信道，N+K 个子信道的带宽均为W Hz.从DTi 到NRj 的信道功率增益为 Hij(t)=hij(t)g0(d0/dij)θ.从NRj 到MEC 的蜂窝链路信道功率增益设置为Hjs(t)=hjs(t)g0(d0/djs)θ.其中 hij(t)和 hjs(t)为小尺度的瑞利衰落系数，符合单位均值的指数分布，g0为路径损失函数，θ为路径损失指数，d0为参考距离，dij为从DTi 到NRj 的距离，djs为从NRj 到边缘服务器MEC 的距离.通过香农公式可知，从DTi 到NRj 的D2D 传输速率为 rij(t)=Wlog2(1+从NRj 到边缘服务器MEC 的传输速率为其中为DTi 的发射功率，为NRj 的发射功率，σ2为背景噪声方差.

1.3 任务计算模型

为了确保MEC 的可持续使用，搭载MEC 的基站通常由电网供电，所以忽略MEC 计算过程的能量消耗.令 fiDT(t)为DTi 在t 时刻的本地CPU 循环频率，γi为DTi 的计算负载，单位为cycles/bit.DTi 在单个时隙内的计算任务大小为执行DTi 本地计算任务的能耗为.其中 κ1为DT 芯片架构的功率系数.

1.4 EH 模型

每个移动设备都配备EH 装置，可以捕获可再生能源供能.在时隙开始的时刻，DTi 的能量为，NRj 的能量为，它们服从在不同时隙的最大值为和的独立同分布模型.ei(t)、ej(t)为被收集并存储在电池中的能量，用于本时隙的任务计算和下一个时隙的任务卸载.在每个时隙中，ei(t)、ej(t)满足以下约束：

采用虚拟电池能量队列来量化DTi 和NRj 的电池能量水平，在每个时隙开始时，将DTi 和NRj 的虚拟电池队列记为 Bi(t)和 Bj(t).在本文中Bi(0)=0,Bj(0)=0,Bi(t)＜∞,Bj(t)＜∞,DTi 和NRj在t 时刻消耗的能量记为

两者受到以下能量关系的约束：

DT 和NR 的虚拟电池能量队列动态模型为

1.5 社会信任矩阵

在社会域中，社会关系为用户通过社交网络中的连接、交流和互动构建的关系网络，反映了用户间的信任度和亲密程度.利用贝叶斯技术，将不同社交网络平台下收集到的历史记录进行整合，获得用户之间的社会关系，用社会信任矩阵表示一个时隙内DTi 和NRj 的社会关系强度.社会关系的强度越大，移动设备之间越有可能建立D2D 通信链接.社会关系属性在D2D 匹配决策中发挥了关键作用.

1.5.1 社会信任矩阵的获取方案 在互联网的社交领域，系统在微博、抖音、Twitter 等社交平台上获取用户间的社会关系，如发布的帖子、评论、点赞、分享等.这些记录不仅可以揭示用户的兴趣、观点和偏好，还反映用户之间的社交关系.利用贝叶斯技术，可以对不同社交网络平台收集到的历史记录进行整合，得到社会信任矩阵[9,15].

具体过程如下.使用贝叶斯技术对不同的社交网络平台上收集的数据进行整合，通过用户选择相似内容的概率密度分布函数来表示用户行为的相似性，决定社会关系的强度.量化社会关系的强度，在得到社会信任值后，可得社会信任矩阵.该模型在获取用户之间的社会信任关系模型中得到了广泛应用[8,12].

1.5.2 社会信任矩阵在本文的应用 在利用上述方案得到多个社交网络的数据整合模型后，社会信任矩阵 Ω(t)=[ω1(t),ω2(t),···,ωN(t)]表示用户之间的社会关系.其中社会信任矩阵 Ω(t)的列向量为 ωi(t)=[ωi1(t),ωi2(t),···,ωiK(t)]T，其中 ωij(t)为DTi 和NRj 之间的社会信任值，用来表示一个时隙内DTi 和NRj 的社会关系强度.时变的社会信任值 ωij(t)为

ωij(t)=0表示DTi 和NRj 之间不存在社会关系，因此他们之间不会建立D2D 链接.从D2D 传输的信息安全性和传输可靠性的方面考虑，用户之间更喜欢与其社会关系较高的用户建立D2D 链接，传输DT 产生的计算任务.

2 问题公式化

2.1 性能度量

本文的优化目标为在计算资源和队列稳定性约束下尽量减少系统服务成本，其中系统服务成本主要包括系统能耗成本、任务丢失成本和安全成本3 部分.当DT 或NR 没有足够的能量或者无线信道条件较差时，放弃到达的任务.考虑这方面的因素，对每一个放弃的任务都加一个单位成本惩罚因子[16-17].此时，将系统的服务成本定义为所有设备的计算能耗和传输能耗、任务丢失成本和社会信任值的加权和.

式中：xij(t)∈{0,1}为在t 时刻的D2D 链接指示器，若DTi 与NRj 在t 时刻建立链接，则 xij(t)=1，否则 xij(t)=0 ;Di(t)、Dj(t)∈{0,1}为DTi 和NRj 的任务丢弃指示器，等于1 表示不丢弃任务，否则为丢弃；φi(t)、φj(t)为DTi 和NRj 的丢弃任务惩罚成本；ϕ为社会信任值的惩罚成本，社会信任值与系统安全成本间存在近似反比关系，应选择尽可能大的社会信任值来降低系统服务成本.

2.2 最小化系统服务成本

由于 Bi(t)和 Bj(t)为理想化状态下的电池能量队列，将扰动参数 θi和 θj加入其中表示消耗的实际电池能量水平，则2 种设备的虚拟能量队列和表示为

扰动参数 θi和 θj满足下列不等式[16,18]：

不等式（19a）～（19d）表示每个设备的计算频率和发射功率不超过它们的最大值.式（19e）表示社会信任值的约束.不等式（19f）、（19g）表示DTs 和NRs 的电池输出量不超过它们的电池放电约束.式(19h)保证了任务缓冲队列是有界的，即平均速率稳定.P1是随机的混合整数规划问题，其中包括的连续变量和二元变量是耦合且时变的，到达的计算任务和队列积压是随机且不可预测的，很难推导出长期的最优策略.李雅普诺夫优化技术是解耦长期问题的有效方法，可以根据系统实时输入的数据，在线计算系统的控制参数，实现对系统的在线控制和调整，在解决资源分配问题上得到了广泛应用[19-20].

2.3 李雅普诺夫优化框架

为了解决随机优化问题 P1，在队列稳定条件下最小化系统服务成本问题转化为漂移加惩罚函数，通过漂移函数满足队列稳定，利用惩罚函数满足系统成本最小化.当前时刻的队列积压为,引入二次的李雅普诺夫函数：

式中：L(Θ(t))表示队列积压的标量度量，L(Θ(t))＞0 .L(Θ(t))越小，所有任务的队列积压数量越少.

引入李雅普诺夫漂移函数：

通过将队列稳定性纳入执行成本性能中，定义李雅普诺夫漂移加惩罚函数来解决上述问题：

式中：V 为目标函数对漂移惩罚的权值，可以作为调整系统成本和队列稳定性的控制参数[21].

在每个时隙中，通过最小化 ΔV(Θ(t))，将系统成本最小化的同时，稳定了队列水平.由于 ΔV(Θ(t))是非线性的，没有直接最小化 ΔV(Θ(t))，而是推导出李雅普诺夫漂移加罚函数的上界，并设计在线卸载算法，最小化 ΔV(Θ(t))在可行区域 O(t)的上界，使得队列稳定.

在每个时隙中，对于任意队列积压 Θ(t)和系统服务成本 W(t)，在可行决策 O(t)下的漂移加惩罚函数 ΔV(Θ(t))满足

证明：将队列积压公式(4)的两边平方，得到

将式(25)的所有移动设备相加，得到以下不等式：

对2 种设备的虚拟能量队列(15)、(16)开展与式(4)相同的操作，如下所示：

将式(26)～(28)相加，可得

将C 和式(29)代入式(22)，可得漂移加罚函数的上界(23).

根据漂移加罚函数的上界，设计基于李雅普诺夫的在线优化方法.通过最小化式(23)的右侧，将长期优化问题转化为基于单个时隙的优化问题P2，将其拆分后逐个进行处理，使得优化问题更加容易、高效地求解.

3 ODMRA 算法的设计

该部分的目标是将长期平均优化问题转化为如下4 个单时隙优化问题：1)能量收集；2)计算资源分配；3)发射功率分配；4）D2D 匹配决策.结合凸分解和子模块优化理论，提出基于李雅普诺夫优化的D2D 在线决策匹配和资源分配(ODMRA)算法，分别解决这些子问题.

3.1 收获的最佳能量

通过如下问题求解DTs 和NRs 收获的能量.

3.2 最优卸载决策和资源分配

将P3从问题 P2中解耦后，则转化为问题 P4.通过解决以下问题，获得DTs 和NRs 的最优CPU 频率、最优的D2D 传输功率、最优的上传功率和最佳的D2D 匹配决策.

P4是混合整数规划问题，若使用蛮力方法求解，则计算复杂度非常高.观察到可行区域是f(t)、p(t)、x(t)的笛卡尔乘积，使用高斯-赛德尔迭代法交替[22-23]最小化求解，可以有效地保证 P4的收敛性.设计ODMRA 算法，提出利用迭代的方法交 替求解问题 P4.

3.2.1 最优的CPU 频率 假设发射功率和D2D 匹配决策固定，最优的CPU 周期频率调度问题为

将P4.1分解为DTs 的CPU 频率问题和NRs 的CPU 频率问题.由于DTs 的CPU 频率问题是非凸的，将放缩后，得到原问题的上界为

3.2.2 功率分配问题 通过固定DTs 和NRs 的CPU 循环频率和D2D 连接决策，功率分配问题可以写成如下形式：

接下来解决NR 到MEC 的传输功率问题：

3.2.3 D2D 决策选择问题 给定最优的发射功率和设备的CPU 频率，关于社会信任关系的D2D 匹配决策问题表述如下：

子模块优化是解决组合问题的强大工具[23-24]，适用于求解策略选择问题.与其他的策略选择算法相比，它具有高效性、复杂度更低、资源分配更加公平等优点，因此子模块优化在网络问题中被广泛应用.

利用子模块优化来寻找D2D 之间的决策.具体来说，将约束下的2 种移动设备DT 和NR 之间的决策约束(1)和(2)写为拟阵的形式，严格证明了D2D 决策选择的效用函数 xij(t)Uij(t)存在单调性和子模性.将问题 P4.3转化为拟阵约束下的子模函数最大化问题，用“边际效用递减”性质结合低复杂度的贪婪算法，可得保证系统性能最优的D2D 匹配决策.

G(t)包含所有可能的关联策略，这些策略可以划分为N 个不相交的集合，如G(t)=∪i∈NAi(t),Ai(t)∩Ai′(t)=ϕ,i ≠i′.其中Ai(t)={x˜i1(t),···,x˜iK(t)},∀i∈N，表示DTi 与NR 配对的集合.这些策略可以划分为K 个不相交的集合，如G(t)=∪j∈KBj(t),Bj(t)∩Bj′(t)=ϕ,j ≠j′.其中Bj(t)={x˜1j(t),···,x˜Nj(t)},∀j∈K表示NR 与DTs 配对的集合.

拟阵 I表示每个DT 可以关联的NRs 的约束(1)和每个NR 可以关联的DTs 的约束(2)，|·|表示基数.

定理1：给定地面集合 G(t)和它的一个子集X(t)∈G(t)，则是基于X(t)∈G(t)的单调子模函数.

证明：因为

令ε(t)⊂X(t)，v∈X(t)ε(t)，则

接下来证明目标函数 F(X(t))的子模性.若F(X(t))满足“边际效应递减”性质，则它具有子模性.向集合 ε(t)中添加一个元素的边际增益至少与它的超集中添加一个元素的边际增益相等，即满足

式中：ε(t)⊆ε(t)′∈X(t),a(t)∈G(t)ε′(t).根据式(46)，可以推导出如下的边际效应关系.

可以看出，ΔF(t)(a(t)|ε(t))=ΔF(t)(a(t)|ε′(t))，满足“边际效应递减”性质，证明了函数 F(X(t))的子模性，从而证明了定理1 存在的合理性.此时，可以将最小化问题 P4.3转化为最大化问题，求解最优策略.

将问题 P4.3重新表示为拟阵约束的单调子模问题的最大问题：

在拟阵约束的情况下，根据“边际效应递减”性质，结合贪婪算法的思想，设计策略选择算法，解决问题 P4.4.设置定义函数F(X(t))的边际增益为

初始化集合 X(t)、Xi(t)、Xj(t)(∀i∈N,∀j∈K)为空集ϕ，其中 X(t)为D2D 的策略选择集合.Xi(t)包含了DTi 将任务卸载到哪个NR 的决策集合.Xj(t)表示NRj 辅助哪些DTs 的决策集合.在初始化完成后，用 户匹配策略选择算法设计如下.

3.2.4 ODMRA 算法和最优值分析 通过考虑D2D 用户卸载决策、CPU-周期频率、传输功率分配和收集的电池能量，将ODMRA 算法总结在算法2 中.求解问题 P3的计算复杂度为 O(N+K)，本方案通过交替迭代解决子问题 P4.1、P4.2和 P4.3来优化目标问题 P4，假设迭代过程中的最大迭代次数为 κ，在每次迭代中复杂度为 O(2(N+K)+NK)，因为在地面集合 G(t)中有NK 个元素，求解 P4.3的时间复杂度为 O(NK).本文所提ODMRA 算法的计算复杂度为 O(N+K+κ(2(N+K)+NK)).通过对算法复杂度进行理论分析可知，与匹配博弈算法相比，本文算法的复杂度更低，可以更好地应用于 实际系统.

4 仿真分析

考虑半径为200 m 的圆形区域，配备了MEC服务器的BS 位于该区域的中心.NRs 和DTs 分别随机分布在半径分别为50～150 m 和150～200 m 的环状区域内.仿真参数基于文献[12]和[16]设置.DT 生成的任务在 1.0×104～2.0×104bits/s 内呈均匀分布.信道功率增益呈平均值为 g0(d/d0)-4的指数分布.时隙数T=200,DTs 的数量Nmax=10,NRs的数量K=4,W=1 MHz,τ0=0.1 s,σ2=10-12W,γi=γj=[1,1.1,1.2,1.3] cycles/bit，κ1=10-12，κ2=10-16,d0=1,g0=-40 dB.为了评估本文算法的性能，最大程度地消除单次运行的随机性对仿真结果造成的误差，因此进行100 次蒙特卡罗模拟，对最终的仿真结果取平均值.

本文的对比算法如下.1)基线1：只考虑MEC 服务器的执行和本地执行，而附近的设备只作为中继设备，无法执行计算任务.2)基线2：NRs 仅用于通过D2D 通信卸载任务，不作为中继设备.3)随机算法：DTs 和NRs 在D2D 中随机匹配的算法.4)SADLS 算法：Long 等[12]提出的使用匹配博弈的方法进行D2D 的策略选择算法.5)Qlearning 算法.

近端发送设备NR 的队列长度随时隙数t 变化的图像如图2 所示.随着时间的增加，近端发送设备的队列长度逐渐增加并趋于稳定.这是由于ODMRA 算法可以通过最小化目标函数，调整惩罚函数的大小来调整任务到达率和任务处理率之间的动态关系，使得李雅普诺夫漂移项逐渐减小，系统逐渐趋于稳定状态.仿真图像显示了李雅普诺夫漂移惩罚函数的上界，证明了本文算法的有效性.

图2 辅助设备队列长度随时隙数的变化Fig.2 NR’s queue length with number of time slot

2 种设备的虚拟电池队列随着时间变化的图像如图3 所示.NRs 的计算能力大于DTs，故NRs 的电池容量大于DTs.随着时间的增加，2 种设备的虚拟电池队列长度在本文算法的优化下逐渐减小并逐渐稳定在扰动参数 θi和 θj附近,验证了电池水平的下界.

图3 电池队列长度随时隙数的变化Fig.3 Battery queue length with number of time slot

如图4、5 所示，比较了2 种移动设备数量改变时辅助设备队列长度的变化，图4 显示了辅助设备数量为4 时，队列长度随着DT 数量NDTs的增加而增加.随着任务数量的增加，D2D 传输和辅助设备计算的任务量增加.在系统任务处理能力不变的情况下，移动设备产生的计算任务将会在NR 中不断积累，导致队列长度增加，近端设备的队列需要更长的时间达到稳定状态.图5 中，当DT 的数量固定为10 时，队列长度随着NR 数量NNRs的增加而减小.这是因为随着辅助设备数量的增加，在任务到达率不变的情况下，系统的任务处理能力提升，队列积压减小.

图4 不同数量DTs 下队列长度随时隙数的变化Fig.4 Change of queue length with number of time slot under different quantities of DTs

图5 不同数量NRs 下队列长度随时隙数的变化Fig.5 Change of queue length with number of time slot under different quantities of NRs

如图6 所示为不同算法下时隙长度对系统性能的影响.可知，执行延迟越长，系统的服务成本越小.所有算法的系统服务成本都随着 τ0的增加而减小，其中本文算法的平均服务成本性能最好，验证了该算法的有效性.随着 τ0的增加，本文算法、随机匹配算法和SADLS 算法均可达到相似的平均服务成本.由于信道条件的不确定性，基线1 和基线2 的算法性能明显最差.

图6 平均服务成本随时隙长度的变化Fig.6 Change of average service cost with length of time slot

如图7 所示为不同算法下平均任务到达率 λi的变化对系统性能的影响.图中，E¯为平均能量消耗.由于未能充分利用系统资源，基线1、基线2 和随机算法的平均能耗随着 λi的增加而出现大幅度上升.Q-learning 算法、SADLS 算法和本文算法都设计了卸载决策和资源分配方案，显著降低了系统平均能耗.其中Q-learning 算法通过训练过程生成的Q 表是静态的，这意味着Q 表一旦被创建，它就不能根据系统状态的实时变化（如队列积压或长期成本的变化）进行动态调整，故会导致平均能耗较高.SADLS 算法采用匹配博弈，每个用户追求自身利益最大化，各方之间的利益冲突可能会导致参与者失去利益，得到较差的纳什均衡解，故算法性能较差且不稳定.本文算法在决策选择时，从系统的整体性能出发，将问题拆分成单个子模块后逐个进行优化，每个参与者可以分配相对公平和合理的资源.在该模型中，本文算法相较于其他算法能耗更低且更加稳定.

图7 平均能量消耗随平均任务到达率的变化Fig.7 Change of average energy consumption with average task arrival rate

5 结 语

本文研究具有社会关系属性的D2D-MEC 网络的任务卸载和资源分配框架，即具有空闲计算能力的附近设备发挥中继作用，帮助远程发送设备执行或进一步将其任务转移到MEC 服务器.将具有QoS 和能量队列稳定性约束的平均服务成本最小化的随机优化问题表述为一系列的短期确定性优化问题.设计基于李雅普诺夫优化的ODMRA 算法解决该问题.该算法对设备收集的能量、CPU 计算频率、发射功率及D2D 链路匹配决策进行优化.仿真结果和理论分析表明，在任务随机到达、系统状态时变的情况下，该算法提高了队列稳定性，减少了能量消耗，且算法复杂度较低，优于其他算法.