绿色能源驱动的移动边缘计算动态任务卸载

马惠荣 陈 旭 周 知 于 帅

(中山大学数据科学与计算机学院 广州 510006)mahr3@mail2.sysu.edu.cn)

随着移动通信技术的空前发展(如5 G)，移动设备的数量呈爆炸式增长，预计数十亿物联网(Internet of things, IoT)设备[1](如移动设备、可穿戴设备、传感器等计算节点)将通过蜂窝网、低功耗广域网等方式连接到互联网.在这一背景下，各种各样的IoT应用[2]应运而生，如车联网、智能监控、增强现实[3]、智慧城市等，物联网系统发展迅速[4].随着IoT应用类型的不断丰富、功能的日益强大，IoT设备将产生大量的中间数据，并且需要庞大的算力和能源以支撑相应的IoT服务.但在实际生活中，出于便携的考虑，较小的移动设备受物理尺寸的限制难以提供足够的资源以实现令人满意的IoT服务.

为解决上述问题，任务卸载被广泛认为是一种有效的任务处理方式.任务卸载是将数据处理任务从计算资源缺乏的、能量匮乏的IoT设备卸载到有充足计算资源和能量的计算结点，从而为IoT设备任务的执行提供更多可用的资源和能量.围绕任务卸载学者们做了许多研究[5-6].传统的移动云计算[7](mobile cloud computing, MCC)是将任务上传到强大的云端服务器(例如Google公有云计算引擎)进行处理.大量实践证明，移动云计算对具有中等时延容忍度的移动应用程序(例如个人云存储服务)是非常有效的计算卸载方式[7].但对于新兴的IoT应用来说，传统的云计算模型是不适用的.一方面，如果将本地的IoT应用卸载至远端的云服务器，海量中间数据的传输将对骨干网络造成极大的负担.此外，长距离的通信将导致网络时延不稳定，难以达到时延敏感任务的要求(通常为几十毫秒)，移动设备服务质量将会下降.

作为移动云计算模式的延伸，移动边缘计算[8-10](mobile edge computing, MEC)被业界认为是一种很有前景的解决方案.在移动边缘计算模式中，网络边缘设备(如基站、接入点和路由器)被赋予了计算和存储能力，以代替云服务器提供服务.这种将远端云的网络资源下沉至网络边缘的方式，使得用户可以近距离地使用边缘节点的网络资源.相比于移动云计算，移动边缘计算不仅能够极大地降低传输时延，还能够避免因上传大量数据而引起的骨干网络拥塞.因此，近年来移动边缘计算吸引了工业界[11]和学术界[12-13]的广泛关注.

尽管MEC能够有效降低IoT设备的能耗及网络传输时延，边缘服务器端的能效(power usage efficiency, PUE)却是实现MEC可持续计算的瓶颈.具体而言，云服务器通常位于气候和地理环境优越的农村地区，因而其PUE较高且容易获得丰富的可再生能源，例如太阳能和风能.而边缘服务器通常位于难以吸纳可再生能源的城市与人群中心，因此使用电网电力.相比于云服务器，边缘服务器的PUE更低，因此面临着绿色可持续问题.

为了解决上述问题，本文利用信息和通信技术(information and communication technology, ICT)行业的2项技术.第1种是绿色能源收集(energy harvesting, EH)技术[14-15]，该技术使得设备能够捕获环境中可回收的能量，包括太阳能、风能以及人体运动能量[16]等绿色能源，从而促进电池的自我可持续性和不间断运行.第2种是IoT设备间通信(device-to-device communication, D2D)[17-18]技术，该技术允许2个移动设备不经过基站就直接在设备之间进行高效通信.直观上来说，将EH技术和D2D技术引入到MEC系统中，可以促进MEC系统可持续发展，并实现绿色计算(green computing)[19-21].特别是当执行任务的设备中绿色能源供应不足时，可以通过D2D技术将能耗较大的任务卸载到绿色能源供应充足的设备上执行.

因此，为了促进MEC系统的可持续发展并实现绿色计算，本文设计了一种基于能量收集(EH)技术和设备间通信(D2D)技术的绿色任务卸载框架，具体结构如图1所示.此外本文还提出了一种高效的动态任务卸载策略，优化系统内任务执行所造成的边缘服务器端电网电力能源成本及云服务器端云资源租用成本.图1中，一个边缘服务器服务范围内有多个配备EH模块的IoT设备，每个IoT设备可以与基站建立蜂窝链接，也可以与临近其他IoT设备建立D2D链接，还可以通过基站与云服务器建立链接.本文中运营商可以针对不同IoT应用的类型和对时延的需求调整相应的任务执行策略以优化系统的服务性能：如为减少系统内总的任务执行成本，选择本地端执行、卸载到其他设备端执行、卸载到边缘服务器端执行，以及卸载到云服务器端执行.

Fig. 1 An illustration of the proposed architecture图1 本文提出的架构的说明

在本文所提出框架中，每个IoT设备均能收集绿色能源储存在设备的电池中，并将收集到的绿色能源作为IoT设备电池唯一的能量来源，这不仅可以为任务执行提供可持续的能源，还能延长电池的使用寿命.因而，本文假设任务在本地端执行和将任务卸载到其他IoT设备执行时在设备端所消耗的能源不计入系统内总的任务执行成本.系统总的任务执行成本主要由2部分构成：一部分是IoT设备将任务卸载到边缘服务器端执行时，边缘服务器为执行该任务所消耗的电网电力能源成本；另一部分是将IoT设备上时延不敏感的任务卸载到云端服务器执行时，云端服务器为执行该任务所产生的云资源租用成本.因此，本文以最小化系统内总的执行成本为优化目标.

本文的主要贡献包括3个方面：

1) 本文框架中，引入D2D技术使得IoT设备之间可以动态、有益地共享计算和通信资源，这有助于在节约成本的同时提高能效.考虑到IoT设备的资源可能被其他设备过度使用(即某些设备向临近设备大量卸载任务但极少接收临近设备卸载过来的计算任务)，本文引入激励约束，该约束确保一个IoT设备只有向其他设备提供足够多的资源时才能使用其他IoT设备的计算资源.该约束不仅能够有效防止设备资源被其他设备过度使用，还能够有效促进设备间的协作.

2) 针对本文提出的优化问题，考虑到不同时间片各个设备EH模块的缓存与设备所消耗的绿色能源之间的动态耦合性，以及设备任务特性和绿色能源到达等系统参数的随机性和突发性，要想离线求解本文提出问题的最优解是极其困难的.因此，本文利用李雅普诺夫优化技术[22]提出了一种在线任务卸载算法.作为该算法的核心模块，本文针对每个时间片设备任务的卸载执行情况设计了基于图变换的任务卸载分配策略，该算法仅依赖系统的当前状态信息，通过调用爱德蒙带花树算法[23]即可求得近似最优解.

3) 本文对所提出算法的性能进行了严格的理论分析，论证了系统最小化长期成本和队列长度之间存在[O(1V),O(V)]的折中.实验中通过与现有文献中常见的4种任务卸载机制相比较，验证了所提出算法的优越性能.通过调控参数V的值，本文评估了其对系统内总的任务执行成本和队列积压的影响，并验证了本文所提出的在线任务卸载算法所得的系统执行成本可以接近离线最优的结果.通过对引入激励约束参数的设置，有效验证了本文提出激励约束对系统任务执行成本节省率的有效性.

1 相关工作

在过去的几年里，许多研究MEC的科研人员致力于解决计算效率的最大化和IoT设备能耗的最小化问题[24-29].文献[24]主要研究联合任务卸载和计算资源分配的MEC系统的能量效率最大化问题，提出一种计算效率指标，通过迭代和梯度下降方法解决了这一问题.文献[25]提出了一种基于非正交多路访问MEC环境的节能任务卸载算法，该算法确定了网络链路的上行功率控制解决方案，解决了任务卸载划分和时间分配问题.针对MEC服务器可以为IoT设备充电的任务卸载问题，文献[26]提出了有时延约束的卸载算法，该算法能够将能耗降至最低.文献[27]以最小化IoT设备任务在基于正交频分多址协议的上行网络链路传输的能耗为目标，综合使用计算分流、子载波分配和计算资源分配等3种优化策略来降低IoT设备能耗.文献[28]提出了一种在无线电力传输环境中的IoT设备卸载调度算法，在此算法中，IoT设备会决定是在本地计算任务还是将任务卸载到MEC服务器进行计算.文献[29]主要研究MEC和云服务器协同计算卸载，并针对MEC和云服务器环境提出了一种协同部分计算卸载算法.该文使用分支限界方法解决了单个MEC服务器的计算卸载问题，然后将其扩展到多个MEC服务器和云服务器场景中.针对多种场景，该文提出了一种迭代的启发式MEC资源分配算法.上述研究[24-29]专注于IoT设备的能效，却并未考虑利用能量收集技术为设备提供能源.

随着绿色计算的提出和能量收集技术的进步，具有能量收集功能的MEC系统的研究受到了研究人员的极大关注[30-31].文献[30]研究了能量收集MEC系统的联合卸载和自动扩容问题.该文指出能量收集MEC可靠、高效运行的关键在于其前瞻性和适应性.为了在系统参数未知的情况下快速学习，该文利用问题的特殊结构，提出了一种基于PDS的强化学习算法来学习最优卸载和自动扩容策略.文献[31]将可再生能源集成到MEC系统，提出了一种考虑MEC电池和服务体验质量(QoE)的卸载调度算法.该文所提算法包括卸载请求的准入控制和MEC服务器频率的计算.但是上述算法均不适用于本文提出的为每个IoT设备配备EH模块，并对设备任务进行绿色任务卸载调度的情况.

当然，具有能量收集功能的IoT系统的研究也受到了很多研究人员的关注[32-34].文献[32]提出了一种能量收集IoT设备根据电池电量确定卸载速率的基于强化学习的卸载算法.文献[33]提出了一种着重于MEC服务器计算能力的动态计算卸载算法.该算法仅仅提及能量收集对延长网络寿命的作用，并没有将能量收集作为系统任务卸载调度的主要考虑方面.文献[34]假设IoT设备具有能量收集模块，并利用李雅普诺夫优化技术提出了一种IoT设备根据能量收集状态决定其计算频率的算法.然而，该文仅仅考虑了单个IoT设备任务的卸载调度情况，本文考虑了多个能够利用绿色能源的IoT设备任务卸载调度情况.

在这些研究的基础上，本文重点研究在边缘系统中利用绿色能源的多个IoT设备任务的计算卸载调度问题.考虑为每个IoT设备配备EH模块，同时利用D2D技术促进设备间的协作，充分利用各个设备的绿色能源，从而实现最小化任务执行所造成的边缘服务器端电网电力能源成本和云服务器端云资源租用成本的优化目标.

2 系统模型与问题形式化

本文研究的框架模型如图1所示，考虑一个边缘服务器基站服务范围内的一组IoT设备{Dev1,Dev2,…,DevN}，每个IoT设备Devi,i∈{1,2,…,N}既可以与基站建立蜂窝链路，也可以与临近的IoT设备建立D2D链路，还可以通过基站与云服务器建立链接.本文考虑以时间片为单位运行，单位时间片t∈{t1,t2,…,tT}，且每一个任务都可以在单一时间片内完成.由于基站一般具有完整的网络信息和较高的计算能力，本文考虑基站在每个时间片为IoT设备制定任务卸载策略的网络辅助架构.

本文所提出框架中，每个IoT设备均配备EH模块，该模块能够收集绿色能源并储存在设备的电池中，这不仅可以为任务执行提供可持续的能源，还能延长电池的使用寿命.由于本文将收集到的绿色能源作为IoT设备电池唯一的能量来源，因而，本文假设设备任务在本地端执行和卸载到其他IoT设备执行所消耗的IoT设备的能源不计入系统的任务执行成本.因而，本文以最小化系统内的任务执行成本为优化目标，动态优化各个设备任务的执行模式.表1中列出了本文中主要符号及其意义.

Table 1 Main Notations and Their Meanings表1 主要符号及其意义

Continued (Table 1)

2.1 设备资源模型

1) 计算能力.一般来说，有许多种方法控制现代移动设备处理器的处理能力，例如随需应变调控器(即通过DVFSD实时调整CPU的频率)或性能调控器(即锁定设备CPU的最大频率).本文中，对每个IoT设备Devi,i∈{1,2,…,N}，定义Fi(t)为其CPU工作频率，从而该设备总的计算能力即为Fi(t)(即单位时间内CPU周期的数目).此外，定义Yi(t)为设备当前的负载(即处理能力的占比).考虑到设备可能运行一些从后台加载或者不能卸载的任务，设备闲置的计算能力可表示为ci(t)=(1-Yi(t))Fi(t).

需要强调的是，与蜂窝链路类似，上述与D2D链路相关的参数均是随时间变化的，因而这些参数并不是本文的控制变量.此外，根据本文框架中设定的时间长度，基站可以在一个时间片内为每一个设备建立和维护一个或多个D2D链接.然而，考虑到系统内时间和资源的限制，本文参考FlashlinQ[35]，引入一个实用的相关性约束，即每个时间片内执行任务卸载期间每一个IoT设备允许最多建立和维护一个D2D链路.

2.2 云资源模型

为了进一步简化任务执行的模式，本文假定运营商在网络中部署一个云服务器.该云服务器由一组虚拟机{VM1,VM2,…,VMM}构成，其中每一个虚拟机VMi,i∈{1,2,…,M}都可以运行一个从IoT设备到来的任务.具体来说，时间片t内，IoT设备Devi,i∈{1,2,…,N}的任务将被分配给一个专用的虚拟机进行处理.本文定义ai(t)来表示相应的虚拟机是否激活，当ai(t)=1时虚拟机激活，反之虚拟机处于休眠状态.

2.3 移动任务模型

为了描述IoT设备Devi,i∈{1,2,…,N}的任务特性，本文采用了一个参数元组Ii(t),Oi(t),Ci(t)，其中Ii(t)表示设备Devi上计算任务输入数据的大小，Oi(t)表示计算任务输出数据的大小，Ci(t)表示计算该任务所需要的计算资源(即CPU周期的数目).值得一提的是，通过在元组中引入其他的参数，任务的资源模型可以很容易地扩展到其他类型的资源(例如存储资源).此外，为了描述一个任务是否是时延敏感的、能否卸载到云端服务器进行处理，本文定义0-1变量σi(t)来表示.当σi(t)=1时，表示设备Devi的任务可以卸载到云服务器端执行，反之，则表示该任务是时延敏感的任务，仅能卸载到设备本地端、其他设备端或者是边缘服务器端执行，不能卸载到云服务器端执行.

2.4 任务执行模型

接下来，将介绍任务执行模型.正如引言所介绍的，为减少系统内总的任务执行成本，IoT设备Devi,i∈{1,2,…,N}可以选择本地端执行、卸载到其他设备端执行、卸载到边缘服务器端执行，以及卸载到云服务器端执行(设备任务对时延不敏感时).

2.5 任务分配决策

关于IoT设备的任务卸载问题，有以下一些约束.首先，定义0-1变量hi(t).其中hi(t)=1表示IoT设备Devi,i∈{1,2,…,N}在时间片t内有任务需要执行;反之，则表示设备Devi在时间片t内没有要执行的任务.此外，本文对每一个设备Devi定义一个0-1向量xi(t)=(xi1(t),…,xi i(t),…,xiN(t),xie(t),xic(t))表示时间片t内所有任务的卸载决策.其中，xi j(t)=1表示设备Devi的任务卸载到设备Devj,j∈{1,2,…,N}上执行(当j=i时，任务即在本地移动端执行)，相应地，xi e(t)=1及xi c(t)=1分别表示将任务卸载到边缘服务器端和云服务器端执行.此外，每一个时间片设备的任务都会被分配到一个且仅一个执行节点.为了描述不同时间设备之间链接的变化情况，本文引入一个随时间变化的卸载图G(t)=(Vex(t),E(t))，其中Vex(t)代表节点集合，E(t)代表图中边的集合.任务分配约束条件为

(1)

(2)

(3)

(4)

约束条件式(2)表示所有IoT设备的任务只能调度一次；约束条件式(3)表示由于IoT设备资源有限，在一轮任务卸载过程中，一个IoT设备最多只执行一个任务(可以是设备自己的任务，也可以是其他设备的任务)；约束条件式(4)表示：1)如果2个IoT设备都有任务要计算，并且它们之间建立了一个D2D链路来交换各自要执行的任务，则xi j(t)=xji(t)=1.这是很容易理解的，即在任务卸载过程中如果一对设备已经建立了D2D链接，它们就不能与其他IoT设备建立任何其他D2D链接.2)如果2个IoT设备都有任务要执行，但是它们不想在彼此之间建立D2D链接来交换执行任务，则设备Devi(设备Devj，类似地)可以在本地端执行任务，也可以将任务卸载到另一个IoT设备Devs执行，也可以将任务卸载到边缘服务器端执行，对于时延不敏感的任务，还可以将任务卸载到云服务器端执行，即xi j(t)=xji(t)=0.换句话说，当hi(t)=1时，可以得到xji(t)=hj(t)xi j(t).

因而当每个IoT设备选择不同的执行方式时，根据对设备端所消耗的绿色能源以及在边缘服务器端产生的电力能源成本和云服务器端云资源租用成本建立的模型，任意IoT设备Devi,i∈{1,2,…,N}通过D2D链路将任务卸载至其他设备以及通过蜂窝链路将任务卸载至边缘服务器或云服务器端执行所消耗的绿色能源可以表示为

和

相应地，IoT设备Devi在本地端执行任务所消耗的绿色能源和通过D2D链路帮助其他设备Devj,j∈{1,2,…,N}执行任务所消耗的绿色能源可以汇总为

那么，有任务需要执行的IoT设备Devi(也就是hi(t)=1的设备)在时间片t内消耗的绿色能源总和为

没有任务执行的IoT设备Devi(也就是hi(t)=0)在时间片t内消耗的绿色能源为

综上，IoT设备Devi在时间片t内消耗的绿色能源的总和为

为处理IoT设备Devi的任务，时间片t内边缘服务器端产生的电网电力能源成本为

为处理IoT设备Devi的任务，时间片t内云服务器端产生的云资源租用成本为

2.6 绿色能量收集模型

本文假设每个IoT设备都配有一个EH模块，该模块由太阳能电池板、风力涡轮机、动能瓦片或它们的组合构成.由于自然界中绿色能源的可获得量是随机的和突发的，本文假设在给IoT设备供电前，EH模块所收集的能量均被缓存在一个能量存储电池中，以确保为设备提供持续的能源供应.此外，每一个EH模块的充电和放电过程都是可以同时进行的.

Qi(t+1)=max[Qi(t)-Ei(t)+ri(t),0],

(5)

其中，ri(t)可以视作能量队列Qi(t)中的“到达率”，而Ei(t)则可以视作能量队列Qi(t)的“服务率”.

在式(5)中，IoT设备Devi中EH模块收集到的储存在电池中的绿色能源ri(t)受可用性约束

ri(t)∈[0,Ri(t)],

(6)

此外，还有

(7)

设备所消耗的绿色能源受电池能量约束

Ei(t)≤Qi(t).

(8)

由于电池容量有限，缓存的能量Qi(t)也应该满足最大电池容量约束

(9)

需要强调的是，配备EH模块的IoT设备的任务执行卸载调度策略比由电池驱动的移动边缘计算系统的卸载调度策略要复杂得多.为了解决本文提出的绿色任务卸载调度问题，最直接的想法是通过对每个单独的时间片进行渐进优化，进而实现最小化系统内总的任务执行成本的优化目标.然而，这种针对每个时间片的局部最优决策可能会影响到全局最优的决策.因为各个EH模块的缓存与不同时间片各个设备所消耗的绿色能源是动态耦合的.因此，任何时间段的任务卸载调度和能量收集对未来边缘服务器端所产生的电网电力能源成本和云服务器端云资源的租用成本的影响都是不可忽视的.此外，由于设备任务特性和绿色能源到达等系统参数具有随机性和突发性，离线计算该调度问题的最优解是不切实际的.值得庆幸的是，本文在第4节提出了一种在线任务卸载算法.该算法仅依赖于系统的当前状态信息，在每个时间片，通过求解一个图匹配问题就能得到近似最优解.

3 问题建立

在上述框架的基础上，本文提出了一种具有一系列必要约束条件的多个EH IoT设备任务执行的卸载调度问题.

3.1 激励约束

由于IoT设备间进行协作时，存在某些设备向临近设备大量卸载任务却极少接收临近设备卸载过来的计算任务的情况，这可能导致一些设备的资源被过度使用.为了防止IoT设备的资源被其他设备过度使用，并促进IoT设备间的协作，本文引入一个激励约束.该约束确保一个IoT设备只有向其他设备提供足够多的资源时才能使用其他IoT设备的计算资源.此外，系统还可以考虑将资源贡献量作为设备的信用值，由系统中的基站来维护，并以每个IoT设备的信用值作为任务调度决策的重要参考因素，以此来促进设备间协作，防止资源的过度使用.

考虑到约束式(4)，进一步得到

(10)

(11)

此处，对每一个IoT设备Devi,i∈{1,2,…,N}，αi∈[0,1].

3.2 系统任务执行成本问题最小化

本节进一步描述多个配备EH模块的IoT设备执行任务的卸载问题.本文所提绿色任务卸载框架的优化目标不再是最小化网络中的能耗，而是最小化任务执行所造成的边缘服务器端电网电力能源成本和云服务器端云资源租用成本，表示为

(12)

s.t.式(1)～(8)，式(10)，(11)成立.

其中，

4 在线算法设计

求解问题式(12)面临的主要挑战是需要知道系统未来不可预测的信息，例如可获得的绿色能源、设备资源以及D2D链接的情况等.考虑到不同时间片内各个设备EH模块的缓存与设备所消耗能源之间的动态耦合性，以及设备任务特性和绿色能源到达等系统参数的随机性和突发性，离线求解最优解是不切实际的.因此，通过利用李雅普诺夫drift-plus-penalty方法[22]，本文设计了一个在线任务卸载算法.作为该算法的核心模块，本文针对每个时间片设备任务卸载执行设计了基于图变换的任务卸载分配策略，该算法仅依赖系统的当前状态信息.

4.1 问题转化

针对优化问题式(12)，本文制定了以下关键概念.

(13)

此外，本文还引入以下虚拟队列来捕获时间平均的激励约束的变化：

特别地，本文先定义一个二次李雅普诺夫函数

(14)

此处Θ(t)表示本文系统中所有虚拟队列和真实队列积压的向量.在李雅普诺夫函数[22]中，本文针对约束式(5)和式(13)引入广泛用于保证队列稳定性的L1，对激励约束式(10)和式(11)引入广泛用于保证队列稳定性的L2.应该强调的是，虚拟队列的负积压没有违反系统定义的时间平均约束，所以不需要考虑.

接着，定义one-slot李雅普诺夫drift-plus-penalty表达式：

其中，V是系统目标最优性和队列稳定性之间的非负权衡参数(即本文所提框架对于最小化边缘服务器端电网电力能源成本及云服务器端资源租用成本的重视程度).本文中第5节将会通过仿真来研究V值与系统性能之间的关系.就李雅普诺夫drift-plus-penalty表达式而言，式(12)可以被转换为以下问题：

(15)

s.t.式(1)～(8)，式(13)成立.值得注意的是，此时平均时间约束式(10)和式(11)已包含在ΔΘ(t)中.

由于目标函数中包含的二次项很难处理，因此本文最小化目标函数的一个上界，该上界将在引理1中给出.

引理1.时间片t内，给定任务卸载决策x*(t)，以下不等式成立：

(16)

其中，

此处，F*在任何时间片都是一个常数，而f(t)不涉及任何系统内的调度因子.因而，在任务分配算法的设计中，本文不予考虑.由于页面限制，具体的表述和详细证明留至本文的在线技术报告中[38].

根据转化后的问题和引理1，本文提出了满足约束条件式(1)～(8),(13)情况下，使drift-plus-penalty上界(式(16)右侧后4项)最小化的在线任务调度算法，并证明通过求解问题式(12)能够获得问题的近似最优解，且具有很好的性能.因此，本文提出的在线任务卸载算法的核心是解决下面的优化问题，使drift-plus-penalty上界最小化，即

(17)

s.t. 式(1)～(8)，式(13)成立.

算法1.在线任务卸载算法.

① for each time slott∈{t1,t2,…,tT}

② 调用最优任务卸载算法求每一个时刻的解x*(t)=arg min (Equ(17))；

③ 基于当前的卸载策略更新系统中的策略；

④ end for

算法1详细描述了本文的在线卸载算法实现的过程.对每一个IoT设备，通过算法1第2步的求解，可以得到系统时间片t内所有任务调度决策的近似最优解，接着更新电池队列以及2个虚拟队列的积压，以便下一时间片的任务卸载调度计算.该算法仅利用了当前时间片的系统信息和队列积压.不幸的是，由于其耦合性，该实时优化问题通常是NP难的.然而根据本文建模及约束条件，对每个有任务执行的IoT设备而言，其任务只能被分配到一个任务执行点(即本地移动执行、D2D卸载执行、边缘服务器端卸载执行或云服务器端卸载执行).受任务卸载模式的启发，本文设计了一个基于多个EH IoT设备的任务卸载问题的图匹配方法，该方法能够在满足电池能量队列长度的情况下，最大限度地降低系统内总的任务执行成本.

4.2 在线任务卸载算法

本文将求解每个时间片内算法1中的在线任务卸载算法的关键部分(即问题式(17))的近似最优解.针对式(17)中的任务卸载问题，本文提出一种图匹配算法，该算法的关键在于图结构的正确定义.具体而言，在D2D链接图的基础上构建系统最初的基本图结构，然后通过以下步骤对基本图进行修改：

1) 修剪节点.对于当前时间片中没有任务要执行的IoT设备Devi，如果它的所有相邻设备也都没有任务需要执行，则删除该设备节点Devi(例如，删除图2步骤1中的节点6)，因为设备Devi不会被分配任何任务.

2) 生成节点.对于一个有任务需要执行的IoT设备Devi(即hi(t)=1)，首先生成可以执行设备Devi的任务的设备节点(如节点2～4有任务需要执行，因此在图2步骤2中生成5个白色节点1,2′,3′,4′和5).第2步生成虚拟边缘节点，也就是用来表示设备Devi的任务可以在边缘服务器端执行的节点(例如，节点2～4有任务需要执行，因此在图2步骤2中生成了3个正方形的节点).第3步生成虚拟云节点，用来表示设备Devi的任务可以在云服务器端执行(例如，节点2～4有任务需要执行，其中节点3的任务是时延敏感的，不能卸载到云服务器端执行，即σ3(t)=0，因此，图2步骤2中生成2个椭圆形的节点).

Fig. 2 Illustration of modelling the task offloading problem as weighted graph matching图2 将任务卸载问题建模为加权图匹配

3) 图匹配.首先，需要得到表示设备任务卸载策略的图UG(t)=(U(t)∪W，E(t)).具体而言，在图2中，设备集合S={Dev2,Dev3,Dev4}是顶点集合，集合W表示所有可以执行任务的节点的集合，包括设备节点集合(即白色节点{node1,node2′,node3′,node4′,node5})、边缘服务器端节点集合(即正方形节点{node2,node3,node4})、云服务器端节点集合(即椭圆形节点{node2,node4})，而E(t)={(Devi,nodej):ei j(t)=1,Devi∈S,nodej∈W,t∈{t1,t2,…,tT}}.这样做，就得到了基本的连接图(即图2步骤3).其次，为了满足约束式(3)，检查集合U(t)中任意2个设备Devi和Devj之间是否存在边ei j∈E(t)和eji∈E(t)，如果存在，就从图UG(t)中删除这条边，并在集合U(t)中增加一条边，该边的权值为两条边的权重之和(如图2步骤4所示).根据修改后的图UG(t)，很容易证明问题式(17)的求解就是得到一个适应集合U(t)的最小权值匹配(即集合U(t)中所有设备在匹配中都有边连接，如图2步骤5所示).通过调用爱德蒙带花树算法[23]，即可求得每个时间片的图匹配问题的解.基于上述图匹配问题的解决方案，可以有效解决问题式(17)的求解.算法2总结了该求解过程.在4.3节中将证明本文所提出的在线任务卸载算法(算法1)长远看是可以获得卓越性能的，且该性能与离线优化的性能差距非常小.

算法2.最优任务卸载算法.

输出：匹配x*(t).

① 对每一条边ei j∈E(t) do

② 更新E(t)中边ei j(t)的权重为-wi j(t)+ζ;

③ ifDevi∈U(t) &&Devj∈U(t) then

④ ifeji(t)∈E(t) then

⑤ 从集合E(t)中删除ei j(t)和eji(t)两条边,并在集合U(t)中增加一条设备Devi到设备Devj的边，权重为两边权重之和;

⑥ end if

⑦ else

⑧ 根据约束式(3)，将ei j从E(t)中删除;

⑨ end if

⑩ 调用带花树算法求解UG(t).

4.3 性能分析

定理1.在线任务卸载算法中系统所有设备任务执行的平均时间成本、平均时间的真实队列及虚拟队列的积压满足

从定理1可以得知，通过调控参数V的值，本文提出的在线任务卸载算法求得的系统成本接近离线求解问题的结果.此外，时间平均的电池队列积压和虚拟队列积压也由参数V决定.简而言之，本文提出的在线算法在最小化系统成本和限制队列长度之间存在[O(1V),O(V)]的折中.

5 实验结果

本节中将通过数值研究来评估本文所提出的在线任务卸载算法在降低系统任务执行成本方面的性能.表2给出了实验中典型参数的详细值.本文将所提出算法与4种机制相比较：

1) Naive edge and cloud execution strategy.即将所有设备的任务卸载到边缘服务器端或者云服务器端进行处理.

2) Greedy execution strategy.即为每个设备的任务贪心地选择本地端、D2D端、边缘服务器端或者云服务器端进行处理.

3) Random execution strategy.即为每个设备的任务随机选择本地端、D2D端、边缘服务器端或者云服务器端进行处理.

4) No energy harvesting strategy(No EH).每个设备的电池充电成本是计入系统总成本的，设备端有足够电量时任务在本地端执行，否则卸载至边缘服务器端或者云服务器端进行处理.

Table 2 Simulation Parameter Description and Setup表2 仿真参数描述及对应值设置

前3种机制中设备电池的配置与本文相同，均使用绿色能源为设备电池提供能源.实验中以naive edge and cloud execution strategy作为系统任务执行成本节省率的基准.

1) 电池最大容量Qmax对系统性能的影响.从图3中可以明显看出随着电池容量的增加，系统任务执行成本减少率动态增加，这验证了在系统任务执行成本降低方面较大的电池容量可以为任务卸载的优化提供更多潜力的事实.

Fig. 3 Reduction ratio of costs vs control parameter V under different Qmax图3 不同Qmax下的成本降低率与控制参数V

Fig. 4 Reduction ratio of costs vs control parameter V图4 成本降低率与控制参数V

2)V值对系统性能的影响.图4展示了不同的V值对于系统性能的影响.在李雅普诺夫优化理论[35]中，V是权衡目标函数最优性和队列稳定性之间的参数.在本文提出的算法中，V用来权衡系统内总的任务执行成本和队列的稳定性.V值越大，代表更多的关注系统任务执行成本的降低，而较少关注队列的积压状况.通过设置不同的V值，本文评估了其对系统内总的任务执行成本和队列积压的影响.本文中，实验结果与理论分析相符.分析实验结果可以看出，随着V值的增大，系统任务执行成本进一步降低，系统任务执行成本减少率增加，当V值增加到一定的值时，系统任务执行成本降低率会趋于平缓，这是因为此时系统任务执行成本降低率已经接近理论最优值.

从图4可以看出，Greedy的选择执行任务的模式所得到的系统任务执行成本降低率相比Random的选择任务执行模式要高10%以上.这是因为Greedy策略是基于贪心选择方法来选择任务执行模式，会优先选择系统任务执行成本最低的卸载策略，而Random策略不考虑这些，是随机选择各个任务的卸载方式，所以产生的系统内总的任务执行成本会高一些.与这些均能收集绿色能源的基准策略相比，本文提出的算法在系统总成本降低率方面确实有明显的改进.具体而言，当控制参数V=5时，本文提出算法的性能提高了78.6%，明显优于其他2种策略.

图5将本文所提出利用绿色能量实现绿色任务卸载框架与没有使用能量收集技术(即系统成本中包含每一时刻电池的充电成本)的卸载框架进行对比.从实验结果来看，本文所提出算法远远优于不使用能量收集技术的方法.这是因为当设备的电池不能收集绿色能源时，电池的充电成本会计入系统总成本中，如果一直不对电池充电，则该种方法需要的成本和naive edge and cloud execution strategy大致一致，而当对电池进行充电时，所产生的系统总成本可能高于naive edge and cloud execution strategy的成本，也可能低于naive edge and cloud execution strategy的成本，这取决于仿真实验对于设备充电成本的系数设置.本文实验中，所提出算法是远远优于no energy harvesting strategy算法的.

Fig. 5 Reduction ratio of costs vs control parameter V图5 不同控制参数V下本文算法的成本降低率的比较

实验中，随着V值的增加，系统队列的变化情况如图6所示.可以看出，V增加时，电池容量队列和虚拟队列均以近似线性的方式增加，这与定理1相符.因而，结合图3可以得出，系统内总的任务执行成本性能和队列变化服从[O(1V),O(V)]的权衡，这与理论分析相符.

Fig. 6 Sum of queue vs control parameter V图6 队列之和与控制参数V

从图7可以看出，无论V值的大小，队列的变化曲线都会随着时间逐渐趋于稳定，这说明当电池最大容量一定时，本文提出的算法能够为系统任务执行提供可持续的能源.

Fig. 7 Sum of all queue backlogs vs time slot图7 所有队列之和随时间变化情况与控制参数V

3) 激励约束参数对系统性能的影响.图8描述了V=10时不同α值下系统任务执行成本节省率的变化.可以看到系统任务执行成本节省率随着α的减少而增加.这是因为，根据本文提出激励约束的定义，一个较小的α意味着设备在与其他设备协作时更加无私，更愿意在帮助其他设备的过程中牺牲更多的资源，其结果是，系统性能得到了改善.而当α的值较大时，意味着设备不愿意贡献太多自己的资源，会限制其他设备使用自己的资源.本文其他实验中，α的值均设置为0.5.

Fig. 8 Reduction ratio of costs vs control parameter V under different values of α图8 不同激励参数α下成本节省率与控制参数V

4) 设备数对系统性能的影响.设备数量对系统任务执行成本节省率的影响如图9所示.可以看到随着系统中设备数量的增多，本文提出算法的性能稳定优于其他2种算法(相比Greedy和Random策略，分别有超过10%和25%的系统任务执行成本节省率的提升).这些实现现象均表明本文提出的算法具有很好的扩展性，能够很好地适应系统设备数量的变化.

Fig. 9 Reduction ratio of costs vs user amount under various online algorithms图9 多种在线算法下的成本节省率与设备数量

6 总 结

为了提高MEC系统的PUE并实现绿色计算，本文提出了一种绿色任务卸载框架.该框架考虑多个配备EH模块的IoT设备任务的卸载调度问题，旨在最小化任务执行所造成的边缘服务器端电网电力能源成本和云服务器端云资源租用成本.在系统中，IoT设备通过关联到最合适的基站，可以将任务卸载到本地端、其他设备端、边缘服务器端以及云服务器端执行.为有效促进设备间的协作，并防止设备资源被其他设备过度使用，本文引入激励约束，该约束确保一个IoT设备只有向其他设备提供足够多的资源时才能使用其他IoT设备的计算资源.考虑到系统未来信息的不确定性，例如绿色能源的可获得性，本文利用李雅普诺夫优化技术提出了一种在线任务卸载算法.作为该算法的核心模块，本文针对每个时间片设备任务卸载执行情况设计了基于图变换的任务卸载分配策略，该算法仅依赖系统的当前状态信息，通过调用爱德蒙带花树算法即可求得近似最优解.严格的理论分析和充分的实验均验证了本文所提出框架的优越性能.