多目标优化的SWIPT-MEC任务分级卸载架构与优化算法

张泽维,李陶深*,2,杨林峰

(1.广西大学计算机与电子信息学院, 广西南宁530004;2.南宁学院中国-东盟综合交通国际联合实验室, 广西南宁530200)

0 引言

近年来，移动终端设备的应用模式日渐丰富，其收集的网络数据量也呈现爆炸性增长。为了解决网络的高负荷问题，且满足用户对于终端设备低时延、高带宽、低能耗的要求，人们在云计算的基础上提出了移动边缘计算(mobile edge computing，MEC)的概念。MEC旨在将服务平台设置在网络边缘端，降低终端用户因设备自身计算能力与网络数据传输处理过程中引发的操作复杂度与响应时延，提升用户在移动过程中的体验质量，减少端到端的延迟和回程网络的负担[1-2]。简而言之，边缘计算将服务器部署到用户附近的边缘节点，在网络边缘(如无线接入点)给用户提供服务，避免了长距离数据传输，给用户提供更加快速的响应[3]。为了充分利用MEC服务器带来的计算资源，设计合理、高效的计算卸载策略已成为当前MEC中的重要技术[4]。

MEC大多数是在计算任务密集的应用场景下，根据用户数量可分为单用户和多用户2种模式架构。单用户模式是指单一移动设备对计算任务的处理问题，并根据任务类型选择将移动设备中的计算任务，执行本地计算或者卸载操作，最大限度满足任务的需求，例如医院挂号或学校选课的预约服务系统中，存在某一时段内任务请求密集，需要构建有效的卸载策略，提升系统的整体执行效率。

目前，众多学者从移动设备能耗与时延两方面，对单用户的MEC卸载问题展开了深入广泛研究，取得了系列研究成果。文献[5]提出一种基于马尔可夫决策过程的单用户MEC系统的延迟最优任务调度策略，根据任务缓冲区的排队状态、本地处理单元的执行状态以及传输单元的状态来调度计算任务。文献[6]考虑多个异构服务器的计算卸载策略优化问题，设计一种高效的数值方法，实现对系统的平均响应时间、平均能耗和代价性能比进行优化；文献[7]研究多个独立计算任务的卸载调度策略和功率分配问题，确定了最优的任务卸载调度策略和系统时延与能耗间的权衡关系。上述文献主要针对单用户MEC系统的卸载问题，通过建立具体的问题分析，对卸载过程中的参数变量进行联合优化，提升整体系统的执行效率；但由于当前电池技术的发展太慢，无线通信网络的性能受到设备电池寿命限制，电池的手动更换或充电导致无线设备的频繁中断，因此很多时候无法完全满足当前用户设备对于计算能耗的需求[8-9]。为了有效权衡时延与能耗之间的关系，人们在原有的MEC架构体系上引入能量收集( energy harvesting，EH)技术，使得设备在处理计算任务的同时，可以获取源源不断的能量，进一步增强有限的能量支持设备的运行能力[10]。在无线能量传输技术中，无线携能通信(simultaneous wireless information and power transfer，SWIPT)技术利用射频(radio frequency，RF)信号同时携带能量与信息的特点使节点可以在接收信息的同时收集能量[11-12]。文献[13]提出一种单用户单核服务器的完全任务卸载优化算法，通过运用李雅普诺夫优化的动态计算，将设备中的任务在本地执行或全部卸载到MEC服务器上，以获取最小的任务执行成本，同时在设备中安装EH部件，以便在执行任务过程中有效收集补充能量。文献[14]通过将无线能量传输(wireless energy transmission，WPT)与MEC相结合，结合用户WPT-MEC系统中的节能资源分配策略，提出了一种能效最大化策略。上述研究在保证MEC系统执行效率的基础上，增加了对设备计算过程中能量补充的考虑，利用能量收集技术，提高设备的续航能量，为移动设备的卸载提供了更为完善和高效的策略。

综合而言，单用户模式的MEC卸载策略主要集中在构建高效的任务处理机制，并通过合理规划执行过程中的性能模式，在保证计算任务正常执行的同时，可以有效解决移动设备执行计算任务过程中的资源管理问题，最大限度提升了移动设备的执行效率，但在计算密集的场景下，单用户MEC卸载模型缺少合理的卸载策略和对多任务的有效分配机制，在任务数量较大时,任务的执行效率下降明显。MEC卸载模型中的目标函数较为单一，多采取单目标优化的方式求解，未能有效地权衡移动设备在计算过程中的能耗与时耗。为此，本文结合SWIPT和MEC技术，构建一种单用户多任务模式的多目标任务分级卸载架构与数学模型，在卸载操作过程中，建立不同的卸载模式，根据计算任务的个体性质(计算所需的时延和能耗)，为任务选择合适的卸载方式，解决某时段内任务密集场景下的任务卸载问题，提升设备整体执行效率；在此模型基础上，提出一种基于多目标优化的任务分级卸载架构与优化算法(improved strength Pareto evolutionary algorithm, SPEA2)，最大限度地权衡MEC卸载的低能耗与低时耗；最后通过仿真实验说明该任务分级卸载优化策略的有效性。

1 MEC任务分级卸载架构

在包含SWIPT系统的单用户单核服务器移动边缘计算网络中，可以根据任务条件的不同，将计算任务分为本地计算、普通级卸载计算和优化级卸载计算。MEC任务分级卸载架构如图1所示，该架构主要由一个多天线接入点(access point, AP)，一台单天线移动设备以及一个MEC服务器组成。AP可以将相关信号信息和能量传输到移动设备上，同时移动设备中都包含着EH部件，可以捕获传输而来的能量，其中能量传输和信息传输选择不同信道进行，且在传输开始时都可以估计出较为准确的信道状态。

图1 包含SWIPT系统的单用户单核服务器移动边缘计算架构Fig.1 Single-user and single-core server mobile edge computing architecture with SWIPT system

在移动设备中，包含N个计算任务，每个任务I∈{1,2，…,N}，可定义其开始时，都包含如下初始指令U。

U={ui|ui∈{0,1},∀i∈N}。

(1)

为了保证卸载任务的合理性，初始指令U随机产生。ui=0表示系统分配该任务为本地计算；ui=1表示系统分配该任务为卸载计算，将该任务卸载到MEC普通级进行计算。在任务开始阶段，将计算任务长度表示为Qibit。对于本地执行的计算任务，CPU的计算能力表示为Xi(cycles/bit)，即移动设备执行一项计算任务所需的时钟周期个数。

在计算任务密集场景下，图1所示的MEC任务分级卸载架构将移动设备中的计算任务，依据不同条件，实现了本地计算或卸载计算。同时，对MEC服务器划分不同的卸载级，将能耗过高或时延过大的计算任务卸载到MEC优化级处理，可提升计算任务的整体执行效率，减少移动设备的能量消耗。

1.1 本地计算

当初始指令ui=0时，表示该计算任务执行本地计算模式。在移动设备执行本地计算消耗的总计算时间可以表示为

(2)

式中fi为移动设备处理该计算任务时的CPU时钟频率。

为了规范模型合理性，对移动设备的CPU时钟频率添加约束条件，

fi∈[fmin,fmax]，∀i∈N，

(3)

式中：fmin为移动设备执行本地计算时的最小CPU时钟频率；fmax为移动设备执行本地计算时的最大CPU时钟频率。

在执行本地计算的过程中，每个CPU执行周期的能耗与fi成正比，由文献[15]可知，单个CPU周期的能耗为

eLC=k(fi)2，

(4)

式中参数k=1×10-24为每个CPU周期能耗和CPU执行频率的关系常数。

本地计算总能耗可表示为

(5)

1.2 计算卸载

当初始指令ui=1时(或执行优化卸载模式时)，表示该计算任务执行计算卸载模式。在移动设备向MEC服务器执行卸载操作的过程中，选择带宽为ω的信道进行信息传输，移动设备到MEC服务器的传输速率为Ri，根据香农公式可知

(6)

式中：hi表示为该传输信道的信道增益；σ2表示为接收端的噪声功率；pi表示计算任务在卸载过程中的传输功率。为了规范模型合理性，对移动设备的传输功率添加约束条件，

pi∈[pmin,pmax]，∀i∈N。

(7)

在执行计算卸载操作过程中，移动设备向MEC服务器发送任务信息，发送信息过程的时间可表示为

(8)

发送信息过程的能量消耗可表示为

(9)

在图1所示的架构中，由于计算结果的长度比计算任务要短得多，因此返回计算结果的时间可以忽略不计。

1.3 MEC服务器计算

为了高效处理具有一定数量的任务集，在MEC服务器处理机制上可划分出2个处理级，分别为优化级和普通级。将不同类型的计算任务卸载到不同的处理级执行，可进一步提高执行过程的效率。根据卸载的处理级不同，分配给任务不同的卸载指令X，

X={xi|xi∈{0,1},∀i∈N}，

(10)

式中xi=0表示计算任务卸载到普通级，xi=1表示计算任务卸载到优化级。

计算任务向优化级和普通级的进行卸载操作的过程一致，即传输信道和传输功率的选择遵照相同的计算卸载策略执行。在进行分级卸载操作时，依据每个计算任务中变量性质(初始指令ui、卸载指令xi、计算任务的最大容忍执行时间tb、标准能耗量hb)的不同，将具体的任务卸载到MEC服务器优化级或MEC服务器普通级进行计算。

当计算任务卸载到MEC优化级后，在服务器上消耗的总计算时间可以表示为

(11)

式中Fi为MEC服务器处理该计算任务时的CPU时钟频率。

为了规范模型合理性，对MEC服务器的CPU时钟频率添加约束条件：

Fi∈[Fmin,Fmax]，∀i∈N，

(12)

式中：Fmin为MEC服务器处理计算任务时的最小CPU时钟频率；Fmax为MEC服务器处理计算任务时的最大CPU时钟频率。

普通级针对处理初始指令ui=1的计算任务，即在开始阶段就决策执行计算卸载的任务。为了简化模型，该过程消耗总时间(信息传输时间与服务器计算时间之和)为当前计算任务的最大容忍执行时间tb。

1.4 能量收集

(13)

本文假设该信道是固定的，且信道增益在一段时间内保持不变[18]，同时，当前电池电量更新为

(14)

2 多目标MEC任务分级卸载数学模型

为了最大限度的平衡移动设备在执行计算任务过程中的能耗与时耗，针对如图1所示的MEC任务分级卸载架构，对本地计算频率、任务传输功率和MEC服务器计算频率，构建多目标MEC任务分级卸载数学模型。根据公式(1)、(2)、(8)、(10)、(11)，可将每个计算任务的消耗时间表示为

(15)

结合公式(1)、(5)、(9)，每个计算任务的消耗能量表示为

(16)

计算每个任务后电池剩余电量表示为

bi=Bi-Ei。

(17)

下一个任务开始时电池的电量表示为

Bi+1=bi。

(18)

设最小化时间消耗率为P1，最小化能量消耗率为P2。P1对应的最小化时间消耗率的数学模型可描述如下：

(19-1)

s.t.(1)，(3)，(7)，(10)，(12),

(19-2)

(19-3)

(19-4)

其中公式(19-3)体现了当计算任务在执行本地计算时，其总计算消耗时间应小于计算任务的最大容忍执行时间的约束条件；公式(19-4)体现了当计算任务执行卸载操作时，应满足在计算卸载和MEC服务器计算过程的总消耗时间小于计算任务的最大容忍执行时间的约束条件。

P2对应的最小化能量消耗率的数学模型可描述如下：

(20-1)

s.t.(1)，(3)，(7)，(10)，(12),

(20-2)

(20-3)

(20-4)

其中公式(20-3)体现了移动设备在执行本地计算的过程中的能量消耗不能超过当前电池量与收集的能量之和的约束条件;公式(20-4)体现了移动设备在进行卸载操作的过程中，消耗的能量应小于当前电池量与收集的能量之和的约束条件。

3 多目标优化SPEA2与任务分级卸载策略与优化算法

多目标优化SPEA2与任务分级卸载策略可描述如下：

Step 1:初始化i=0；

Step 2:执行设备计算任务；

Step 3:判定初始变量ui，选择本地计算或卸载到普通级计算；

Step 4:采取SPEA2算法对本地计算频率和任务传输功率进行优化；

Step 5:判定本地计算的时耗和能耗，选择本地计算或卸载到优化级计算；

Step 6:采取SPEA2算法对MEC服务器计算频率和任务传输功率进行优化。

上述分级卸载策略的Step4—Step6涉及到一个多目标优化问题，目的在于权衡最小时间消耗和最小能量消耗之间的关系。如果采取提高CPU频率或增强传输功率的方式来降低计算任务的时间延迟，势必会造成更大的能量消耗，因为二者在实际应用中存在极大的冲突性问题。为了解决最小化时间消耗率P1和最小化能量消耗率P2目标函数之间的冲突性关系，本文采用了多目标优化SPEA2算法权衡P1和P2之间的冲突关系。SPEA2是一种多目标优化算法，具有如下特点：

①通过改进适应度的分配方法，同时考虑了个体支配或被支配的情况；

②使用归档截断方法保证了边界解的保留；

③结合了最近邻密度估计技术，更精确地指导搜索过程。

(21)

根据S的值，更新个体的原始适应度R(i)，计算出个体的原始适应度R(i)，即

(22)

(23)

F(i)=R(i)+D(i)。

(24)

根据计算所得的适应度值，进行环境选择，将满足选择条件的个体放入交配池执行交叉和变异操作，完成相关步骤后迭代执行上述步骤，完成相关迭代次数，得到满足条件的目标函数的最优解。

采用SPEA2求解最小化时间消耗率P1和最小化能量消耗率P2这2个目标函数的算法描述如下：

输出：目标函数的帕累托最优解集。

①通过以下步骤更新外部帕累托最优集：

在种群中搜索非支配的个体，并将它们复制到外部的帕累托集合中；

搜索非支配个体的外部帕累托集；

④根据它们的概率执行交叉(BLXcrossover)和变异(Random)操作以生成新的种群。

⑤确定结束标准，达到标准即结束操作，输出目标函数的帕累托最优解集。

4 仿真实验与性能分析

表1 仿真实验参数设置Tab.1 Simulation experiment parameter setting

实验1还验证构建的优化级可以低系统的时间消耗率。将所构建的基于SWIPT的MEC分级优化卸载模型与不包含分级优化系统的MEC模型进行对比的实验结果如图2所示。从中可见，在不同的任务数量下，MEC分级优化卸载模型处理计算任务的时间消耗率均低于普通的MEC模型，验证了选择合适的MEC服务器优化计算频率可以降低计算任务的时间消耗的原因，表明了所构建的MEC分级优化卸载模型可以提高处理计算任务时的效率。

图2 不同任务数量时时间消耗率的比较Fig.2 Comparison of time consumption under different task number

图3 不同任务数量时能量消耗率的比较Fig.3 Comparison of energy consumption under different task number

实验3用于验证优化级判定条件对系统架构的影响，主要分析不同任务数量下判定条件差异对时间消耗率和能量消耗率的影响，以及基于SWIPT的MEC分级优化卸载模型在不同的优化级判定条件下对时间消耗率的影响，仿真实验结果如图4所示。实验结果表明，无论判定条件的变化情况如何，设备时间消耗率都会伴随任务数量的增加呈现减小趋势。当增大计算任务的最大容忍执行时间tb并降低标准能耗量hb的值时，设备的时间消耗率整体降低，且下降趋势随着判定值的变化而逐渐平稳，表明时间消耗率与计算任务的最大容忍执行时间tb成反比，与标准能耗量hb成正比，验证了不同优化判定标准的具体性质。

实验4用于验证不同的优化级判定条件对基于SWIPT的MEC分级优化卸载模型能量消耗率的影响，仿真实验结果如图5所示。从图中可见，能量的消耗率随着任务数量的增加整体为减小趋势，当任务数量在80左右时，判定条件的数值对能量消耗率影响较小，且随着任务数量的增加，优化判定条件对能量消耗率影响也逐渐降低。通过对比该图中不同的参数设置可以发现，当计算任务的最大容忍执行时间tb增大时，能量消耗率的减小趋势随之增加；当标准能耗量hb的值增大时，能量消耗率的减小趋势随之减缓。本实验确定了能量消耗率与判定条件的关系，同时通过分析，得到了不同判定条件下的任务数量平衡点。

图4 对优化级判定条件的分析(时间消耗率)Fig.4 Analysis of optimization level judgment conditions (time consumption rate)

图5 对优化级判定条件的分析(能量消耗率)Fig.5 Analysis of optimization level judgment conditions (energy consumption rate)

实验5是分析性能指标在不同任务长度下对时间消耗率的影响，图6给出了仿真实验结果。由图可知，伴随着任务长度的增加，设备的时间消耗率整体呈减小趋势，这是因为当任务长度增加时，设备执行本地计算的压力增加，执行分级优化卸载策略优势效果更为明显；通过同时增加MEC服务器最大CPU频率和信道带宽，可以极大降低任务执行的时间消耗率(图中圆形标识折线所示，折线值在0.000 1左右浮动)，且此时任务大小对时间消耗率影响可以忽略不计。此外，性能指标在不同任务长度下对能量消耗率的影响与时间消耗率影响类似，故此处不作额外分析。

图6 性能指标在不同任务长度时对时间消耗率的影响Fig.6 Impact of performance indicators on time consumption rate under differenttask lengths

5 结语

本文在单用户单核服务器场景下，针对移动设备面对计算任务密集和权衡能耗和时延之间关系的问题，提出了一种单用户单核服务器的多任务分级卸载架构与多目标数学模型和一种基于多目标优化改进的强度帕累托进化算法(SPEA2)的任务分级卸载架构与优化算法，实现了最低能耗和时耗的多目标优化。仿真结果表明，所提出的模型与优化算法可以有效解决在计算任务较多时能耗和时耗的权衡问题，但是应用场景较为单一，且分级模式相对简单。下一步研究工作可以扩展到多用户应用场景，并划分更为细致的卸载级。