资源受限移动边缘计算任务拆分卸载调度决策

张艮山 刘旭宁

(石家庄学院 河北 石家庄 050035)

0 引 言

通过将任务拆分并卸载至云端进行数据融合、存储和处理，移动用户可以潜在地降低自身设备的能耗和每个任务的处理延时[1-2]。然而，移动设备与云端之间的数据传输会带来额外的通信延时和传输能耗，这样会影响卸载任务的服务质量以及全局移动设备的能量利用[3]。

在这种移动计算环境下，先前的研究工作主要围绕以下几个方向展开，包括单用户单应用卸载[4]、多用户单应用卸载[5-8]、单用户多任务卸载[9-10]以及多用户多任务卸载[11]。利用传统的移动云计算技术，仅有移动设备和云端服务器可以进行任务处理与调度，加入计算访问点(Computing Access Point,CAP)后[12]，即引入新的具有计算能力的无线访问点或基站后形成的新的计算环境，类似于通过多CAP连接的移动边缘计算环境[13]和朵云环境[14]。此时，移动设备上的任务除了可以在本地设备调度执行，还可以进一步通过CAP卸载至云端执行。在考虑融合CAP之后，系统性能的改善可通过求解集中式卸载优化问题来完成，如文献[12]和文献[15]分别在单用户和多用户环境下求解得到了最优卸载与调度解。然而，已有研究即使考虑了多用户的任务卸载情形，也仅是将用户考虑为同质且目标一致的实体，未考虑在实际环境中各个用户的自私性，以及用户与计算访问点间在制定任务卸载与资源分配调度策略时的相互影响，这样得到的任务卸载结果仅是理想结果，且存在不稳定性，对于移动计算环境是极为不利的。

本文将研究自私型移动用户与计算访问点间的相互影响。该环境中，每个移动用户均拥有轮询式调度策略下的多个顺序排列任务需要调度。本文将在多用户环境下考虑任务的卸载决策和通信与计算资源联合分配问题，并以节省移动设备能耗与维持多用户的服务质量为目标。不同于文献[15]中利用一种启发式方法求解集中式非凸混合线性规则问题，本文将利用博弈的思维使移动用户独立分布式地基于各自的代价函数计算自身的卸载决策，而CAP则同步决策通信与计算资源的分配。笔者证实了所提的博弈模型中存在纳什均衡(Nash Equilibrium,NE)解，并设计了一种分布式算法可在收敛情况下达到该NE解。进一步，证实了移动用户可信任地将其任务信息传输至CAP，使得CAP可以计算NE，没有任一用户会脱离该NE。实验结果也证实了该博弈方法可在动态的参数配置下完成全局代价更低的调度与卸载解。

1 系统模型

考虑一个资源受限的云访问网络环境，由一个运程云端服务器、一个计算访问点CAP和N个移动用户组成，如图1所示。每个移动用户拥有M个顺序的任务，以轮询调度的方式用户的每个任务得到处理。轮询调度过程中，当前一轮任务调度后，新的一轮将启动，直到所有任务完成。该系统模型也可简单扩展为每个用户拥有不同的任务数量的场景。且在轮询调度系统中，移动用户的卸载决策与资源分配均需要考虑最优化目标。相关符号说明见表1。

图1 系统模型

1.1 卸载决策

在任务轮询调度的每一轮中，每个移动用户拥有一个任务可在本地设备执行或卸载执行。卸载任务可在CAP端执行也可在远程云端执行。定义卸载决策满足：

(1)

1.2 本地执行代价

1.3 CAP执行代价

由于在多个卸载至CAP的任务中，仅有某些任务在CAP端执行，需要进一步分配CAP可用的通信与计算资源。对于用户i卸载至CAP的任务，数据的上传与下载时间分别为：

(2)

(3)

(4)

(5)

(6)

1.4 云端执行代价

(7)

(8)

1.5 优化问题

(9)

最优化问题是一个非凸混合线性规化问题，即使可得到最优解，理性的移动用户也不一定会执行该最优解提供的卸载方案。以下将通过博弈的方法，使得用户可以以分布式的方式在CAP决定通信与计算资源分配的前提下计算各自的卸载决策，并在实验中验证博弈方法也能获得近似最优的性能。

2 多用户任务卸载博弈

2.1 博弈模型

首先将移动用户与CAP间的相互影响建立为一个移动环境下的卸载决策博弈模型，并寻找式(9)的最优解。将博弈定义为：

GMCO=(I,(Ai)i∈I,(ui)i∈I)

(10)

式中：I={1,2,…,N}表示由所有移动用户组成的博弈者集合；Ai表示用户i的所有可能策略组成的策略集合；ui表示用户i需要最小化的代价函数。

此时，ui为策略组合a=(ai,a-i)的函数，其中，ai∈Ai，a-i=(a1,a2,…,ai-1,…,ai+1,…,aN)∈∏j≠iAj。定义用户i的策略集合和代价函数分别为：

(11)

(12)

通过选择ai，用户i可以决定在何处处理任务可最小化其代价函数ui，即能耗与延时的权重之和。假设所有移动用户均有意愿参与到博弈中，那么对于每个用户而言，参与博弈的期望代价应小于不参与博弈下的本地处理任务得到的代价。由于每个移动用户拥有多个任务，用户目标是降低每一轮的延时使得下一轮任务调度可以尽早开始。因此，式(12)中的代价函数表明用户目标是均衡其能耗与执行延时。

接收所有用户的卸载决策a后，CAP将分配通信与计算资源至每个用户以最小化总体系统代价，即求解以下的资源分配问题：

(13)

s.t. C2，C3，C4，C5

2.2 博弈结构及性质

定义1表明，博弈者若利用处于纳什均衡NE处的策略组合，将没有任一博弈者可以通过改变自身策略降低其自身代价。由于并不是所有博弈形式均存在纳什均衡，以下将证明所提出的博弈模型GMCO至少存在一个纳什均衡。

(14)

定义3有限改进性质(Finiteimprovement Property，FIP)。博弈G中的一条路径表示一个序列(a[0],a[1],…)，对于每个k≥1，存在一个唯一的博弈者i，使得ai[k]≠ai[k-1]∈Ai，且a-i[k]≠a-i[k-1]。(a[0],a[1],…)为一条改进路径，若对于所有k≥1，ui(ai[k])

推论1每个拥有有限策略集合的OPG均拥有至少一个纯策略纳什均衡和FIP。

推论1的证明参见势博弈相关文献。为了证明本文的博弈模型GMCO总存在一个NE，只需证明GMCO为势博弈即可。

定理1所提博弈模型GMCO为带有势函数的OPG，总存在一个NE和FIP。

证明：构建函数：

(15)

ui(a)-ui(a′)

(16)

由于式(15)中的φ(a)满足式(14)定义的OPG的势函数的条件，故上式为GMCO的一个势函数。因此，GMCO是一个势博弈OPG，故该博弈GMCO总存在一个NE和FIP。证毕。

综合以上分析，卸载博弈模型转化为势博弈的原因在于：本文设计的卸载博弈模型并无直接方法可证明其存在卸载决策的纳什均衡解，因为并非所有博弈都存在纳什均衡解，若卸载博弈算法不存在纳什均衡，则算法将无法收敛，无法收敛即不可行。而拥有有限策略集合的势博弈OPG是必须存在纳什均衡解的，因此将设计的卸载博弈模型转化为势博弈，进而证明其存在纳什均衡解。而在性能提升方面即是势博弈可以通过有限改进性质使得博弈者可以不脱离纳什均衡而走向代价相互最优的策略组合实现的。

2.3 博弈算法

已证明博弈必定存在纳什均衡，本节提出一种基于FIP的卸载博弈算法寻找博弈GMCO的NE。由于CAP拥有来自所有用户的信息，并需要根据策略组合分配通信与计算资源到所有卸载任务上，可以计算GMCO的NEa*并发送a*到所有用户。由于NE具有的性质，用户将执行策略a*且不会有主动脱离它的意愿。

算法流程如算法1所示。由于GMCO是一个势博弈OPG，且FIP的性质使得每个可改进路径都是有限的，故算法最终可以达到NEa*，此时没有任一用户可以通过改变其策略进一步降低自身的代价。

算法1卸载博弈算法

//求解(13)设置初始化策略组合及相应资源分配方案

2. setNE=False andk=0

//设置初始NE及k值

3.whileNE==Falsedoflag==0 andi=1

4.whileflag==0 andi≤Ndo

//计算资源分配

//比较代价函数

8. seta[k+1]=(ai[k+1],a-i[k+1]),flag=1

9.k=k+1

10.elseifi==Nthen

11. setflag=1,NE=True

12.else

13.i=i+1

14.endif

15.endwhile

16.endwhile

3 实验评估与分析

本节利用MATLAB计算仿真的结果研究不同参数配置下的算法性能。设置用户数是N=8，移动设备的CPU速率为500×106cycles/s，单位处理能耗为1/730×106J/cycle。考虑执行一个x264CBR编码任务，任务对于CPU的执行请求为1 900 cycles/byte，任务的本地计算时间为4.75×10-7J/bit，本地计算能耗为3.25×10-7J/bit。每个任务的输入和输出数据量假设服从[10 MB,30 MB]和[1 MB,3 MB]的均匀分布。根据IEEE802.11n标准，设CUL=CDL=72.2 bits。每个移动设备上每bit的传输和接收能耗均设置为1.42×10-7J/bit，CAP的CPU速率为2.5×109cycle/s，远程云端的每台服务器的CPU速率为5×109cycle/s。若卸载任务至云端，传输速率为Rac=15 Mbits，β=3×10-7J/bit，αi=α=0.5 s/J，假设每个用户拥有M=100个任务。

为了性能的比较，选择以下的基准方法作为对比策略：1) 随机映射方法。该方法中的卸载决策与随机映射NE方法得到的a[0]完全相同。2) 共享CAP方法。该方法中的卸载决策与共享CAP的NE方法得到的a[0]完全相同。3) 最优策略。该方法利用穷举法得到最优决策，是理论上的最优解。

随机映射方法云端资源非限制条件下使用的常规资源分配方法，选择该方法进行比较可以证明分布式自主卸载决策的可行性。共享CAP方法由于与共享CAP的NE方法拥有相同的初始策略组合，引入该方法对比可以度量共享CAP的NE方法所使用的通过策略改进和进化得到的纳什均衡解能否降低自身代价，即证明卸载博弈算法的有效性。最优策略是一种理论最优解，在实验规模较小时可以通过穷举法得到卸载的最优决策，但实验规模增大时求解复杂度过高，因此该方法可作为其他可行算法的性能度量参照。

图2研究了系统能耗代价与权重值α间的影响。可以看到，共享CAP方法优于随机映射方法，而本文算法得到的随机映射NE和共享CAP NE均得到了近似最优的性能，这表明即使本文算法采用随机起始策略组合，最终得到的NE同样会在系统总体代价上接近于最优解。

图2 能耗相对比延时的权值αi对代价的影响

图3 相对权重β对总代价的影响

图4 本地设备速率对总代价的影响

图5 用户数量对总代价的影响

图6所示为算法在不同用户数量N值下寻找NE时算法需要的迭代次数。可以看到，随着N值的增加，两类算法仅需要较小的迭代次数即可找到NE，换言之，博弈GMCO中的可改进路径长度也是较小的。尽管随机映射NE需要比共享CAP NE更多的迭代次数，但前者可避免利用半定松驰法求解起始策略组合时的过高计算复杂度。

图6 用户数量对算法迭代的影响

综合以上分析可知，多用户任务卸载决策博弈算法具备较好的有效性和可行性。需要强调的是，本文在考虑多用户对于计算节点的共享时，并未考虑实际环境中可能出现的信道共享情形下数据传输间的干扰问题。这种干扰可能影响多个移动用户与计算访问点间数据上行和数据下行的传输速率，进而影响任务的执行时间和执行能耗，这可作为影响卸载决策的又一重要因素进行研究与考量。

4 结 语

本文提出了一种拥有计算访问点环境下的多用户任务卸载决策博弈算法。在该环境中，每个移动用户拥有多个独立任务以轮询方式调度。为了优化移动设备的能耗与用户任务处理的延时，将该集中式的非凸优化问题建立为分布式的卸载博弈决策问题，证明了算法提供的博弈模型是一种势博弈模型，由此证明了博弈中存在纳什均衡，各个用户可在处于纳什均衡处的解而不脱离出来。仿真实验验证了该博弈算法可以得到与理论最优策略近似的最优解。