CN109857546A - 基于Lyapunov优化的多服务器移动边缘计算卸载方法及装置 - Google Patents

Abstract

本发明提供了一种基于Lyapunov优化的多服务器移动边缘计算卸载方法及装置，其中的方法包括：首先为每个移动设备的产生的任务构建任务缓存队列，并为每个移动设备需要卸载但未被处理的任务创建虚拟任务缓存队列；并建立终端功耗模型、带宽模型和QoE模型；然后在每个预设时间片，收集移动设备的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况；再根据收集的信息，构建李雅普诺夫漂移加惩罚函数；再基于李雅普诺夫漂移加惩罚函数，求解出当前时间片内的计算卸载决策。本发明实现了基于多服务器MEC计算卸载，有效降低任务的完成时间以及减少移动设备能耗的技术效果。

Description

基于Lyapunov优化的多服务器移动边缘计算卸载方法及装置

技术领域

本发明涉及移动边缘计算技术领域，具体涉及一种基于Lyapunov优化的多服务器移动边缘计算卸载方法及装置。

背景技术

在5G无线系统中，将部署超密集边缘设备，包括小型蜂窝基站，无线接入点，笔记本电脑，平板电脑和智能手机，每种设备的计算能力都与计算机相当。而且，在每个时刻都有大量设备空闲。如果能够收集网络边缘可用的巨大计算和存储资源，这将足以实现普遍存在的移动计算。简而言之，从1G到4G的无线系统的主要目标是追求越来越高的无线速度，以支持从以语音为中心到以多媒体为中心的流量的过渡。随着无线网络速度接近有线网络速度，5G的使命变得更为复杂，以支持物联网和互联网的爆炸式发展。在功能方面，5G系统将支持通信，计算，控制和内容交付。在应用方面，基于5G的各种新应用和服务正在兴起，例如实时在线游戏，虚拟现实和超高清视频流，这需要前所未有的高访问速度和低延迟。在过去十年中，下一代互联网的不同愿景也有所起飞，包括物联网，触觉互联网(具有毫秒级延迟)和社交网络。

根据思科预测，到2020年，互联网将增加约500亿个物联网设备(如传感器、可穿戴设备)，其中大部分资源用于计算，通信和存储，并且必须依赖云或边缘设备，以增强其能力。目前，现有技术中，通常采用的是传统的移动云计算(Mobile Cloud Computing，MCC)模式，即通过移动网络以按需、易扩展的方式获得所需的基础设施、平台、软件(或应用)的一种IT资源或(信息)服务的交付与使用模式。

本发明申请人在实施本发明的过程中，发现现有技术中的方法至少存在如下技术问题：

仅依靠云计算技术不足以满足5G中新型应用和服务所需的毫秒级延迟。此外，终端用户和远程云之间的数据交换将会导致数据海啸，并使回程网络瘫痪。

由此，可知现有技术中的方法存在计算资源有限而导致任务延迟和能耗大的技术问题。

发明内容

有鉴于此，本发明提供了一种基于Lyapunov优化的多服务器移动边缘计算卸载方法及装置，用以解决或者至少部分解决现有技术中的方法存在计算资源有限而导致任务延迟和能耗大的技术问题。

本发明第一方面提供了基于Lyapunov优化的多服务器移动边缘计算卸载方法，包括：

步骤S1：为每个移动设备的产生的任务构建任务缓存队列，并为每个移动设备需要卸载但未被处理的任务创建虚拟任务缓存队列；

步骤S2：建立终端功耗模型、带宽模型和QoE模型；

步骤S3：在每个预设时间片，收集移动设备的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况；

步骤S4：根据收集的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况，构建李雅普诺夫漂移加惩罚函数；

步骤S5：基于李雅普诺夫漂移加惩罚函数，求解出当前时间片内的计算卸载决策，其中，计算卸载决策用以表征移动终端产生的计算任务在本地执行的任务量以及卸载到边缘服务器执行的任务量。

在一种实施方式中，在步骤S5之后，所述方法还包括：

步骤S6：对构建的李雅普诺夫漂移加惩罚函数进行拆分与求解，针对不同的计算卸载决策进行资源分配。

在一种实施方式中，步骤S1具体包括：

步骤S1.1：每个移动设备为每个正在运行的应用构建一个任务缓存队列，任务缓存队列Q_i(t)的迭代公式为式(1)：

Q_i(t+1)＝max{Q_i(t)-D_Σ，i(t),0}+A_i(t) (1)

其中，D_Σ,i(t)表示在第t个时间片，第i个移动设备本地执行和卸载到边缘服务器上的任务量之和，Q_i(t)表示在第t个时间片，第i个移动设备的本地任务队列长度，A_i(t)表示在第t个时间片，第i个移动设备产生的任务量；Q_i(t+1)表示在第t+1个时间片，第i个移动设备的本地任务队列长度；

步骤S1.2：为每个移动设备创建虚拟任务缓存队列H_i(t)，该虚拟队列中存储有已经被卸载还未被处理的任务，其迭代公式为式(2)：

H_i(t+1)＝max{H_i(t)-D_s,i(t),0}+D_r,i (2)

其中，D_s,i(t)表示在第t个时间片，被服务器执行的属于第i个移动设备的任务量，D_r,i(t)表示在第t个时间片内第i个移动设备卸载到边缘服务器的任务量，H_i(t)表示在第t个时间片，第i个移动设备的虚拟队列长度，H_i(t+1)表示在第t+1个时间片，第i个移动设备的虚拟队列长度。

在一种实施方式中，步骤S2中，

终端功耗模型包括本地执行的CPU功耗和信号发射功耗，其中，移动设备的本地CPU频率根据本地执行的任务量而定，具体公式如下：

f_l,i(t)＝L_iD_l,i(t)τ^-1 (3)

其中，f_l,i(t)表示在第t个时间片第i个移动设备的CPU频率，D_l,i(t)表示在第t个时间片第i个移动设备本地执行的任务量，L_i表示CPU每处理1bit任务所需要的CPU周期；移动设备的本地执行功耗p_l,i(t)与CPU的频率成正比，其公式如下：

其中，k_mod,i表示第i个移动设备的CPU的有效开关电容；

移动设备的无线发射功率为p_r,i(t)的公式如下：

D_r,i(t)＝∑_j∈Sr_i,j(t)τ (6)

其中，r_i,j(t)表示移动设备i到服务器j之间的数据传输速率，B_j表示服务器给每个移动设备分配的带宽大小，Γ_i,j(t)表示移动设备i与服务器j之间信道衰落功率，τ表示时间片的间隔，在第t个时间片，x_i,j(t)＝1表示第i个移动设备向第j个服务器卸载任务，否则表示不卸载；

带宽模型通过频分多址技术将信道划分为不同的子信道；

QoE模型，包括任务延迟和移动设备功耗，根据预设规则对任务延迟和移动设备功耗进行线性加权构成用户的QoE评价标准，其中，QoE的任务延迟部分的计算公式为：

其中，α为加权参数，且α∈[0,1]，

QoE的功耗部分的计算公式为：

综合得到QoE的计算公式为：

其中，β为加权参数，且β∈[0,1]。

在一种实施方式中，步骤S4具体包括：

步骤S4.1：构建Lyapunov函数，具体构建公式如下：

其中，Θ(t)表示在第t个时间段内，所有任务缓存队列的状态，Q_i(t)表示第t个时间段内第i个移动设备本地的任务缓存队列长度，H_i(t)表示第t个时间段内第i个移动设备在服务器上的虚拟任务缓存队列长度；

步骤S4.2：构建Lyapunov漂移函数，其具体公式如下：

其中，表示求期望；

步骤S4.3：构建Lyapunov漂移加惩罚函数：

其中，V表示惩罚因子，ξ(t)表示用户的QoE花费，该函数具有一个上限，其上限为：

其中，C为常数。

在一种实施方式中，步骤S6具体包括：

对于本地执行的任务量，将Lyapunov漂移加惩罚函数展开并拆分后得到移动设备本地CPU频率调节方案，具体公式化表示为：

求出式(14)取得最小值时则为本地执行CPU频率，本地执行CPU频率表示为：

对于卸载到边缘服务器执行的任务量，将Lyapunov漂移加惩罚函数展开并拆分后，获得计算卸载和移动设备传输功率决策方案，公式化表示为：

min_P(t),x(t)∑_i∈U[-(Q_i(t)-H_i(t)+V·αβ)D_r,i(t)+V·(1-β)·p_r,i(t)] (16)。

在一种实施方式中，获得计算卸载和移动设备传输功率决策方案，具体包括：

将式(16)拆分为移动设备的无线信号传输功率和计算卸载决策，其中，移动设备的无线信号传输功率，拆分后的优化公式化表示为：

当式(17)取得最小值时的为得到的无线传输功率，可公式化表示为：

计算卸载决策的优化公式可表示为：

其中，对于每个移动设备，当Q_i(t)-H_i(t)+V·αβ≤0时，表示第i个移动设备卸载一部分任务到边缘服务器上。

在一种实施方式中，对于卸载到边缘服务器执行的任务量，所述方法还包括：

进行服务器计算资源分配，其优化公式可表示为：

min_D(t)∑_i∈U[-[V·(1-α)β+H_i(t)]·D_s,i(t)] (20)。

基于同样的发明构思，本发明第二方面提供了基于Lyapunov优化的多服务器移动边缘计算卸载装置，包括：

队列构建模块，用于为每个移动设备的产生的任务构建任务缓存队列，并为每个移动设备需要卸载但未被处理的任务创建虚拟任务缓存队列；

模型建立模块，用于建立终端功耗模型、带宽模型和QoE模型；

信息收集模块，用于在每个预设时间片，收集移动设备的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况；

函数构建模块，用于根据收集的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况，构建李雅普诺夫漂移加惩罚函数；

卸载决策模块，用于基于李雅普诺夫漂移加惩罚函数，求解出当前时间片内的计算卸载决策，其中，计算卸载决策用以表征移动终端产生的计算任务在本地执行的任务量以及卸载到边缘服务器执行的任务量。

基于同样的发明构思，本发明第三方面提供了一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如第一方面所述的方法。

本申请实施例中的上述一个或多个技术方案，至少具有如下一种或多种技术效果：

在本发明提供的方法，首先为每个移动设备的产生的任务构建任务缓存队列，并为每个移动设备需要卸载但未被处理的任务创建虚拟任务缓存队列，并建立终端功耗模型、带宽模型和QoE模型；然后在每个预设时间片，收集移动设备的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况；接着根据收集的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况，构建李雅普诺夫漂移加惩罚函数；再基于李雅普诺夫漂移加惩罚函数，求解出当前时间片内的计算卸载决策，从而实现基于多服务器MEC计算卸载，可以有效的降低任务的完成时间，并减少移动设备能耗。

相对于现有技术中通过传统的移动云计算方式而言，本发明提出的是一种基于Lyapunov优化的多服务器MEC计算卸载方法，其适用范围是多服务器多用户的移动边缘计算环境，通过收集收集移动设备的任务缓存队列信息、服务器的任务缓存队列信息以及服务器的带宽情况，并将收集到的信息和构建的模型，基于Lyapunov优化进行计算任务卸载的决策，得出当前时间片内的计算卸载决策，其中，即计算任务在本地执行的任务量以及卸载到边缘服务器执行的任务量。

进一步地，采用基于李雅普诺夫优化技术，针对求解出的计算卸载决策进行资源分配，从而对资源进行优化。

进一步地，通过对对计算资源和无线电资源的分配的调节，进一步减少任务延迟和终端设备能耗，从而提升用户体验质量。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例中基于Lyapunov优化的多服务器移动边缘计算卸载方法的流程图；

图2为本发明实施例中构建的任务队列模型示意图；

图3为本发明实施例中基于Lyapunov优化的多服务器移动边缘计算卸载装置的结构框图；

图4为本发明实施例中一种具体示例中多服务器移动边缘计算卸载与资源分配的框架图；

图5为本发明实施例中计算机设备的结构图。

具体实施方式

本发明的目的在于针对现有计算资源有限而导致任务延迟和能耗大的技术问题，提供出的一种基于Lyapunov优化的多服务器移动边缘计算卸载方法，其适用范围是多服务器多用户的移动边缘计算环境。通过收集移动设备的任务缓存队列信息、卸载至服务器的虚拟任务缓存队列信息以及服务器的带宽情况，将收集到的信息作为决策子模块的输入。决策子模块采用基于Lyapunov优化的多用户多服务器协同的移动边缘计算环境的针对延迟容忍应用的计算卸载和资源分配联合决策算法对数据进行处理，得出决策方案。

进一步地，根据决策方法进行资源分配，具体通过对对计算资源和无线电资源的分配的调节，进一步减少任务延迟和终端设备能耗，从而提升用户体验质量。

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例一

本实施例提供了一种基于Lyapunov优化的多服务器移动边缘计算卸载方法，请参见图1，该方法包括：

首先执行步骤S1：为每个移动设备的产生的任务构建任务缓存队列，并为每个移动设备需要卸载但未被处理的任务创建虚拟任务缓存队列。

具体来说，对于延迟容忍的应用，其产生的任务不会被立即执行，而是先存放在缓存队列中。同样地，对于移动设备产生的任务中需要卸载到服务器执行的任务，会构建一个虚拟任务缓存队列。

本申请发明人通过大量的研究和实践发现：移动边缘计算(Mobile Edge ComputeMEC)是在无线接入网络中提供IT服务和云计算功能的新范例，在未来，移动边缘计算服务器将分布在超密集小型蜂窝基站旁。在这样的环境中，移动用户的计算任务可以卸载到边缘服务器上，以减少其服务延迟和功耗。移动用户可以从这种模式中受益。例如，多个基站覆盖的移动用户可以从多个移动边缘计算服务器中进行选择，以根据无线传输条件和可用边缘计算资源卸载其计算任务。当有大量终端向边缘服务器提交卸载请求时，边缘服务器会为请求做出卸载决策并分配合理的资源，但由于边缘服务器部署在移动终端的网络边缘，计算和存储等资源有限，并不能总是立即为请求分配资源，同时用户之间的卸载策略会相互影响。因此，针对在边缘服务器资源受限的计算卸载问题，如何减少应用的完成时间和降低终端的能量消耗亟待解决。基于这种背景下，本发明提出了一种基于Lyapunov优化的多服务器移动边缘计算卸载方法。

在一种实施方式中，步骤S1具体包括：

步骤S1.1：每个移动设备为每个正在运行的应用构建一个任务缓存队列，任务缓存队列Q_i(t)的迭代公式为式(1)：

Q_i(t+1)＝max{Q_i(t)-D_Σ,i(t),0}+A_i(t) (1)

其中，D_Σ,i(t)表示在第t个时间片，第i个移动设备本地执行和卸载到边缘服务器上的任务量之和，Q_i(t)表示在第t个时间片，第i个移动设备的本地任务队列长度，A_i(t)表示在第t个时间片，第i个移动设备产生的任务量；Q_i(t+1)表示在第t+1个时间片，第i个移动设备的本地任务队列长度；

步骤S1.2：为每个移动设备创建虚拟任务缓存队列H_i(t)，该虚拟队列中存储有已经被卸载还未被处理的任务，其迭代公式为式(2)：

H_i(t+1)＝max{H_i(t)-D_s,i(t),0}+D_r,i (2)

其中，D_s,i(t)表示在第t个时间片，被服务器执行的属于第i个移动设备的任务量，D_r,i(t)表示在第t个时间片内第i个移动设备卸载到边缘服务器的任务量，H_i(t)表示在第t个时间片，第i个移动设备的虚拟队列长度，H_i(t+1)表示在第t+1个时间片，第i个移动设备的虚拟队列长度。

具体请参见2，为本发明实施例中构建的任务队列示意图。

然后执行步骤S2：建立终端功耗模型、带宽模型和QoE模型。

具体来说，构建的模型用于后续的计算卸载以及资源分配。

在一种实施方式中，步骤S2中，

终端功耗模型包括本地执行的CPU功耗和信号发射功耗，其中，移动设备的本地CPU频率根据本地执行的任务量而定，具体公式如下：

f_l,i(t)＝L_iD_l,i(t)τ^-1 (3)

具体地，本发明采用动态频率调节技术和动态电压调节技术对移动设备的本地CPU频率和无线电发射功率进行调节，从而减少终端能耗。移动设备的本地CPU频率根据本地执行的任务量而定。其中，f_l,i(t)表示在第t个时间片第i个移动设备的CPU频率，D_l,i(t)表示在第t个时间片第i个移动设备本地执行的任务量，L_i表示CPU每处理1bit任务所需要的CPU周期；移动设备的本地执行功耗

p_l,i(t)与CPU的频率成正比，其公式如下：

其中，k_mod,i表示第i个移动设备的CPU的有效开关电容；

移动设备的无线发射功率为p_r,i(t)的公式如下：

D_r,i(t)＝∑_j∈Sr_i,j(t)τ (6)

其中，r_i,j(t)表示移动设备i到服务器j之间的数据传输速率，B_j表示服务器给每个移动设备分配的带宽大小，Γ_i,j(t)表示移动设备i与服务器j之间信道衰落功率，τ表示时间片的间隔，在第t个时间片，x_i,j(t)＝1表示第i个移动设备向第j个服务器卸载任务，否则表示不卸载；

带宽模型通过频分多址技术将信道划分为不同的子信道；

具体地，本实施方式中可以针对频分多址的无线信道，通过频分多址技术将信道划分为多个子信道。每个移动设备在进行计算卸载时，独占一个子信道。

QoE模型，包括任务延迟和移动设备功耗，根据预设规则对任务延迟和移动设备功耗进行线性加权构成用户的QoE评价标准，其中，QoE的任务延迟部分的计算公式为：

其中，α为加权参数，且α∈[0,1]，

QoE的功耗部分的计算公式为：

综合得到QoE的计算公式为：

其中，β为加权参数，且β∈[0,1]。

具体地，对于不同的任务而言，其QoE侧重的标准不一样，可通过调节QoE的加权参数来调节任务延迟和移动设备功耗之间的比例。任务延迟又可分为本地任务延迟和服务器任务延迟，本发明对本地任务延迟和服务器任务延迟进行了线性加权，可通过调节加权参数改变本地任务延迟和服务器任务延迟的权重，满足不同任务的需求。根据利特尔法则，在一个稳定的非抢占式的系统中，任务的平均等待时间和任务在队列中的停留时间成正比，因此可用任务队列长度来表示任务的延迟。

接下来执行步骤S3：在每个预设时间片，收集移动设备的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况。

具体来说，可以通过信息收集模块在每个时间片内负责收集所有移动设备的任务队列信息、无线信道质量信息和各个服务器上任务队列信息。所有收集到的信息将会作为决策子模块的输入，用于后续计算卸载方案。其中，无线信道质量信息是指无线信道衰落功率，即f_l,i(t)，在计算最优传输功率时用。

再执行步骤S4：根据收集的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况，构建李雅普诺夫漂移加惩罚函数。

具体来说，李雅普诺夫稳定性(Lyapunov stability，或李亚普诺夫稳定性)可以用来描述一个动力系统的稳定性。如果此系统任何初始条件在平衡态附近的轨迹均能维持在平衡态附近，那么可以称为在处李雅普诺夫稳定。

在一种实施方式中，步骤S4具体包括：

步骤S4.1：构建Lyapunov函数，具体构建公式如下：

其中，Θ(t)表示在第t个时间段内，所有任务缓存队列的状态，Q_i(t)表示第t个时间段内第i个移动设备本地的任务缓存队列长度，H_i(t)表示第t个时间段内第i个移动设备在服务器上的虚拟任务缓存队列长度；

步骤S4.2：构建Lyapunov漂移函数，其具体公式如下：

其中，表示求期望；

步骤S4.3：构建Lyapunov漂移加惩罚函数：

其中，V表示惩罚因子，ξ(t)表示用户的QoE花费，该函数具有一个上限，其上限为：

其中，C为常数。

再执行步骤S5：基于李雅普诺夫漂移加惩罚函数，求解出当前时间片内的计算卸载决策，其中，计算卸载决策用以表征移动终端产生的计算任务在本地执行的任务量以及卸载到边缘服务器执行的任务量。

在一种实施方式中，在步骤S5之后，所述方法还包括：

步骤S6：对构建的李雅普诺夫漂移加惩罚函数进行拆分与求解，针对不同的计算卸载决策进行资源分配。

具体来说，通过前述步骤得到当前的卸载决策后，可以进一步通过李雅普诺夫漂移加惩罚函数，进行资源分配。

具体来说，资源分配包括计算资源分配和无线信道资源的分配，其中，计算资源的分配可分为两个部分：1)本地计算资源的分配；2)服务器计算资源的分配。本地计算资源分配负责决定每个移动设备为自己的本地任务队列分配多少计算资源。服务器计算资源分配负责决定每个服务器给每个虚拟任务队列分配多少计算资源，以及不同服务器之间的数据传输。无线信道资源分配包含两个部分：1)移动设备传输功率调节；2)服务器带宽分配。移动设备传输功率调节负责每个移动设备的信号发射功率的确定。服务器带宽分配负责决定每个服务器给移动设备分配多少带宽资源。

在一种实施方式中，步骤S6具体包括：

对于本地执行的任务量，将Lyapunov漂移加惩罚函数展开并拆分后得到移动设备本地CPU频率调节方案，具体公式化表示为：

求出式(14)取得最小值时则为本地执行CPU频率，本地执行CPU频率表示为：

对于卸载到边缘服务器执行的任务量，将Lyapunov漂移加惩罚函数展开并拆分后，获得计算卸载和移动设备传输功率决策方案，公式化表示为：

min_p(t),x(t)∑_i∈U[-(Q_i(t)-H_i(t)+V·αβ)D_r,i(t)+V·(1-β)·p_r,i(t)] (16)。

具体来说，对于本地执行的任务量，主要包括本地计算资源的分配，即移动设备本地CPU频率调节方案。对于卸载到边缘服务器执行的任务量，则包括服务器计算资源的分配以及无线信道资源的分配。

在一种实施方式中，获得计算卸载和移动设备传输功率决策方案，具体包括：

将式(16)拆分为移动设备的无线信号传输功率和计算卸载决策，其中，移动设备的无线信号传输功率，拆分后的优化公式化表示为：

当式(17)取得最小值时的为得到的无线传输功率，可公式化表示为：

计算卸载决策的优化公式可表示为：

其中，对于每个移动设备，当Q_i(t)-H_i(t)+V·αβ≤0时，表示第i个移动设备卸载一部分任务到边缘服务器上。

具体来说，每个移动设备会遍历其所能连接到的所有服务器，判断卸载到哪台边缘服务器更优，则将任务卸载到这些边缘服务器上。

在一种实施方式中，对于卸载到边缘服务器执行的任务量，所述方法还包括：

进行服务器计算资源分配，其优化公式可表示为：

min_D(t)∑_i∈U[-[V·(1-α)β+H_i(t)]·D_s,i(t)] (20)。

具体来说，可以按照V·(1-α)β+H_i(t)的大小从大到小对移动设备进行排序，优先给排在前面移动设备的任务分配计算资源。其资源分配的方案为：若服务器资源不足，所有的计算资源都被分配给当前移动设备，若服务器资源充足，所有当前移动设备可连接到的服务器按照剩余计算资源的比例，给当前移动设备分配计算资源。选定服务器后，可以根据服务器端的任务缓存队列长度确定服务端有多少任务被执行。相邻的边缘服务器之间可通过数据交换进行负载均衡。

需要说明的是，本发明中涉及的公式和字符含义如表1所示。

表1

基于同一发明构思，本申请还提供了与实施例一中一种基于Lyapunov优化的多服务器移动边缘计算卸载方法对应的装置，详见实施例二。

实施例二

本实施例提供了基于Lyapunov优化的多服务器移动边缘计算卸载装置，请参见图3，该装置包括：

基于Lyapunov优化的多服务器移动边缘计算卸载装置，其特征在于，包括：

队列构建模块201，用于为每个移动设备的产生的任务构建任务缓存队列，并为每个移动设备需要卸载但未被处理的任务创建虚拟任务缓存队列；

模型建立模块202，用于建立终端功耗模型、带宽模型和QoE模型；

信息收集模块203，用于在每个预设时间片，收集移动设备的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况；

函数构建模块204，用于根据收集的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况，构建李雅普诺夫漂移加惩罚函数；

卸载决策模块205，用于基于李雅普诺夫漂移加惩罚函数，求解出当前时间片内的计算卸载决策，其中，计算卸载决策用以表征移动终端产生的计算任务在本地执行的任务量以及卸载到边缘服务器执行的任务量。

在一种实施方式中，所述装置还包括资源分配模块，用于在求解出当前时间片内的计算卸载决策之后：

对构建的李雅普诺夫漂移加惩罚函数进行拆分与求解，针对不同的计算卸载决策进行资源分配。

在一种实施方式中，队列构建模块201具体用于执行下述步骤：

步骤S1.1：每个移动设备为每个正在运行的应用构建一个任务缓存队列，任务缓存队列Q_i(t)的迭代公式为式(1)：

Q_i(t+1)＝max{Q_i(t)-D_Σ,i(t),0}+A_i(t) (1)

其中，D_Σ,i(t)表示在第t个时间片，第i个移动设备本地执行和卸载到边缘服务器上的任务量之和，Q_i(t)表示在第t个时间片，第i个移动设备的本地任务队列长度，A_i(t)表示在第t个时间片，第i个移动设备产生的任务量；Q_i(t+1)表示在第t+1个时间片，第i个移动设备的本地任务队列长度；

步骤S1.2：为每个移动设备创建虚拟任务缓存队列H_i(t)，该虚拟队列中存储有已经被卸载还未被处理的任务，其迭代公式为式(2)：

H_i(t+1)＝max{H_i(t)-D_s，i(t)，0}+D_r，i (2)

其中，D_s，i(t)表示在第t个时间片，被服务器执行的属于第i个移动设备的任务量，D_r，i(t)表示在第t个时间片内第i个移动设备卸载到边缘服务器的任务量，H_i(t)表示在第t个时间片，第i个移动设备的虚拟队列长度，H_i(t+1)表示在第t+1个时间片，第i个移动设备的虚拟队列长度。

在一种实施方式中，模型建立模块202中，

终端功耗模型包括本地执行的CPU功耗和信号发射功耗，其中，移动设备的本地CPU频率根据本地执行的任务量而定，具体公式如下：

f_l,i(t)＝L_iD_l,i(t)τ^-1 (3)

其中，f_l,i(t)表示在第t个时间片第i个移动设备的CPU频率，D_l,i(t)表示在第t个时间片第i个移动设备本地执行的任务量，L_i表示CPU每处理1bit任务所需要的CPU周期；移动设备的本地执行功耗p_l,i(t)与CPU的频率成正比，其公式如下：

其中，k_mod，i表示第i个移动设备的CPU的有效开关电容；

移动设备的无线发射功率为p_r，i(t)的公式如下：

D_r，i(t)＝∑_j∈Sr_i，j(t)τ (6)

其中，r_i,j(t)表示移动设备i到服务器j之间的数据传输速率，B_j表示服务器给每个移动设备分配的带宽大小，Γ_i,j(t)表示移动设备i与服务器j之间信道衰落功率，τ表示时间片的间隔，在第t个时间片，x_i,j(t)＝1表示第i个移动设备向第j个服务器卸载任务，否则表示不卸载；

带宽模型通过频分多址技术将信道划分为不同的子信道；

QoE模型，包括任务延迟和移动设备功耗，根据预设规则对任务延迟和移动设备功耗进行线性加权构成用户的QoE评价标准，其中，QoE的任务延迟部分的计算公式为：

其中，α为加权参数，且α∈[0，1]，

QoE的功耗部分的计算公式为：

综合得到QoE的计算公式为：

其中，β为加权参数，且β∈[0，1]。

在一种实施方式中，函数构建模块204具体用于执行下述步骤：

步骤S4.1：构建Lyapunov函数，具体构建公式如下：

其中，Θ(t)表示在第t个时间段内，所有任务缓存队列的状态，Q_i(t)表示第t个时间段内第i个移动设备本地的任务缓存队列长度，H_i(t)表示第t个时间段内第i个移动设备在服务器上的虚拟任务缓存队列长度；

步骤S4.2：构建Lyapunov漂移函数，其具体公式如下：

其中，表示求期望；

步骤S4.3：构建Lyapunov漂移加惩罚函数：

其中，V表示惩罚因子，ξ(t)表示用户的QoE花费，该函数具有一个上限，其上限为：

其中，C为常数。

在一种实施方式中，资源分配模块具体用于：

对于本地执行的任务量，将Lyapunov漂移加惩罚函数展开并拆分后得到移动设备本地CPU频率调节方案，具体公式化表示为：

求出式(14)取得最小值时则为本地执行CPU频率，本地执行CPU频率表示为：

对于卸载到边缘服务器执行的任务量，将Lyapunov漂移加惩罚函数展开并拆分后，获得计算卸载和移动设备传输功率决策方案，公式化表示为：

min_p(t)，x(t)∑_i∈U[-(Q_i(t)-H_i(t)+V·αβ)D_r，i(t)+V·(1-β)·p_r,i(t)] (16)。

在一种实施方式中，资源分配模块还用于：

将式(16)拆分为移动设备的无线信号传输功率和计算卸载决策，其中，移动设备的无线信号传输功率，拆分后的优化公式化表示为：

当式(17)取得最小值时的为得到的无线传输功率，可公式化表示为：

计算卸载决策的优化公式可表示为：

其中，对于每个移动设备，当Q_i(t)-H_i(t)+V·αβ≤0时，表示第i个移动设备卸载一部分任务到边缘服务器上。

在一种实施方式中，对于卸载到边缘服务器执行的任务量，资源分配模块还用于：

进行服务器计算资源分配，其优化公式可表示为：

min_D(t)∑_i∈U[-[V·(1-α)β+H_i(t)]·D_s,i(t)] (20)。

为了更清楚地说明本发明中装置的具体实施方式，下面通过一个模型示例予以详细介绍，具体参见图4。

总体来说，本发明主要采取的技术方案为：提供了一种基于Lyapunov优化的多服务器移动边缘计算卸载与资源分配装置，该装置具体包括计算卸载模块和资源分配模块。

图4中，计算卸载模块包括信息收集模块、决策模块。信息收集模块收集负责在每个时间片内负责收集所有移动设备的任务队列信息、无线信道质量信息和各个服务器上任务队列信息。所有收集到的信息将会作为决策模块的输入，最后得出计算卸载方案。

资源分配模块负责计算资源和无线信道资源的分配。计算资源的分配可分为两个部分：1)本地计算资源的分配；2)服务器计算资源的分配。本地计算资源分配负责决定每个移动设备为自己的本地任务队列分配多少计算资源。服务器计算资源分配负责决定每个服务器给每个虚拟任务队列分配多少计算资源，以及不同服务器之间的数据传输。无线信道资源分配包含两个部分：1)移动设备传输功率调节；2)服务器带宽分配。移动设备传输功率调节负责每个移动设备的信号发射功率的确定。服务器带宽分配负责决定每个服务器给移动设备分配多少带宽资源。

本发明提供的基于Lyapunov优化的多服务器MEC计算卸载和资源分配算法，其适用范围是多服务器多用户的移动边缘计算环境。通过信息收集模块收集移动设备的任务缓存队列信息、服务器的任务缓存队列信息以及服务器的带宽情况，将收集到的信息作为决策模块的输入，决策模块采用基于Lyapunov优化的多用户多服务器协同的移动边缘计算环境的针对延迟容忍应用的计算卸载对数据进行处理，得出决策方案，再将决策方案交给资源分配模块进行执行。通过对对计算资源和无线电资源的分配的调节，来减少任务延迟和终端设备能耗，从而提升用户体验质量。

由于本发明实施例二所介绍的装置，为实施本发明实施例一中基于Lyapunov优化的多服务器移动边缘计算卸载方法所采用的装置，故而基于本发明实施例一所介绍的方法，本领域所属人员能够了解该装置的具体结构及变形，故而在此不再赘述。凡是本发明实施例一的方法所采用的装置都属于本发明所欲保护的范围。

实施例三

基于同一发明构思，本申请还提供了一种计算机设备，请参见图5，包括存储401、处理器402及存储在存储器上并可在处理器上运行的计算机程序403，处理器402执行上述程序时实现实施例一中的方法。

由于本发明实施例三所介绍的计算机设备为实施本发明实施例一中基于Lyapunov优化的多服务器移动边缘计算卸载方法所采用的计算机设备，故而基于本发明实施例一所介绍的方法，本领域所属人员能够了解该计算机设备的具体结构及变形，故而在此不再赘述。凡是本发明实施例一中方法所采用的计算机设备都属于本发明所欲保护的范围。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例做出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。

显然，本领域的技术人员可以对本发明实施例进行各种改动和变型而不脱离本发明实施例的精神和范围。这样，倘若本发明实施例的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

Claims (10)

1.基于Lyapunov优化的多服务器移动边缘计算卸载方法，其特征在于，包括：

步骤S1：为每个移动设备的产生的任务构建任务缓存队列，并为每个移动设备需要卸载但未被处理的任务创建虚拟任务缓存队列；

步骤S2：建立终端功耗模型、带宽模型和QoE模型；

步骤S3：在每个预设时间片，收集移动设备的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况；

步骤S4：根据收集的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况，构建李雅普诺夫漂移加惩罚函数；

步骤S5：基于李雅普诺夫漂移加惩罚函数，求解出当前时间片内的计算卸载决策，其中，计算卸载决策用以表征移动终端产生的计算任务在本地执行的任务量以及卸载到边缘服务器执行的任务量。

2.如权利要求1所述的方法，其特征在于，在步骤S5之后，所述方法还包括：

步骤S6：对构建的李雅普诺夫漂移加惩罚函数进行拆分与求解，针对不同的计算卸载决策进行资源分配。

3.如权利要求1所述的方法，其特征在于，步骤S1具体包括：

步骤S1.1：每个移动设备为每个正在运行的应用构建一个任务缓存队列，任务缓存队列Q_i(t)的迭代公式为式(1)：

Q_i(t+1)＝max{Q_i(t)-D_Σ,i(t),0}+A_i(t) (1)

其中，D_Σ,i(t)表示在第t个时间片，第i个移动设备本地执行和卸载到边缘服务器上的任务量之和，Q_i(t)表示在第t个时间片，第i个移动设备的本地任务队列长度，A_i(t)表示在第t个时间片，第i个移动设备产生的任务量；Q_i(t+1)表示在第t+1个时间片，第i个移动设备的本地任务队列长度；

步骤S1.2：为每个移动设备创建虚拟任务缓存队列H_i(t)，该虚拟队列中存储有已经被卸载还未被处理的任务，其迭代公式为式(2)：

H_i(t+1)＝max{H_i(t)-D_s，i(t)，0}+D_r，i (2)

其中，D_s，i(t)表示在第t个时间片，被服务器执行的属于第i个移动设备的任务量，D_r,i(t)表示在第t个时间片内第i个移动设备卸载到边缘服务器的任务量，H_i(t)表示在第t个时间片，第i个移动设备的虚拟队列长度，H_i(t+1)表示在第t+1个时间片，第i个移动设备的虚拟队列长度。

4.如权利要求1所述的方法，其特征在于，步骤S2中，

终端功耗模型包括本地执行的CPU功耗和信号发射功耗，其中，移动设备的本地CPU频率根据本地执行的任务量而定，具体公式如下：

f_l,i(t)＝L_iD_l,i(t)τ^-1 (3)

其中，f_l，i(t)表示在第t个时间片第i个移动设备的CPU频率，D_l，i(t)表示在第t个时间片第i个移动设备本地执行的任务量，L_i表示CPU每处理1bit任务所需要的CPU周期；移动设备的本地执行功耗p_l，i(t)与CPU的频率成正比，其公式如下：

其中，k_mod,i表示第i个移动设备的CPU的有效开关电容；

移动设备的无线发射功率为p_r,i(t)的公式如下：

D_r,i(t)＝∑_j∈Sr_i,j(t)τ (6)

其中，r_i,j(t)表示移动设备i到服务器j之间的数据传输速率，B_j表示服务器给每个移动设备分配的带宽大小，Γ_i,j(t)表示移动设备i与服务器j之间信道衰落功率，τ表示时间片的间隔，在第t个时间片，x_i,j(t)＝1表示第i个移动设备向第j个服务器卸载任务，否则表示不卸载；

带宽模型通过频分多址技术将信道划分为不同的子信道；

QoE模型，包括任务延迟和移动设备功耗，根据预设规则对任务延迟和移动设备功耗进行线性加权构成用户的QoE评价标准，其中，QoE的任务延迟部分的计算公式为：

其中，α为加权参数，且α∈[0,1]，

QoE的功耗部分的计算公式为：

综合得到QoE的计算公式为：

其中，β为加权参数，且β∈[0,1]。

5.如权利要求1所述的方法，其特征在于，步骤S4具体包括：

步骤S4.1：构建Lyapunov函数，具体构建公式如下：

其中，Θ(t)表示在第t个时间段内，所有任务缓存队列的状态，Q_i(t)表示第t个时间段内第i个移动设备本地的任务缓存队列长度，H_i(t)表示第t个时间段内第i个移动设备在服务器上的虚拟任务缓存队列长度；

步骤S4.2：构建Lyapunov漂移函数，其具体公式如下：

其中，表示求期望；

步骤S4.3：构建Lyapunov漂移加惩罚函数：

其中，V表示惩罚因子，ξ(t)表示用户的QoE花费，该函数具有一个上限，其上限为：

其中，C为常数。

6.如权利要求2所述的方法，其特征在于，步骤S6具体包括：

对于本地执行的任务量，将Lyapunov漂移加惩罚函数展开并拆分后得到移动设备本地CPU频率调节方案，具体公式化表示为：

求出式(14)取得最小值时则为本地执行CPU频率，本地执行CPU频率表示为：

对于卸载到边缘服务器执行的任务量，将Lyapunov漂移加惩罚函数展开并拆分后，获得计算卸载和移动设备传输功率决策方案，公式化表示为：

min_p(t)，x(t)∑_i∈U[-(Q_i(t)-H_i(t)+V·αβ)D_r,i(t)+V·(1-β)·p_r，i(t)] (16)。

7.如权利要求6所述的方法，其特征在于，获得计算卸载和移动设备传输功率决策方案，具体包括：

将式(16)拆分为移动设备的无线信号传输功率和计算卸载决策，其中，移动设备的无线信号传输功率，拆分后的优化公式化表示为：

当式(17)取得最小值时的为得到的无线传输功率，可公式化表示为：

计算卸载决策的优化公式可表示为：

其中，对于每个移动设备，当Q_i(t)-H_i(t)+V·αβ≤0时，表示第i个移动设备卸载一部分任务到边缘服务器上。

8.如权利要求7所述的方法，其特征在于，对于卸载到边缘服务器执行的任务量，所述方法还包括：

进行服务器计算资源分配，其优化公式可表示为：

min_D(t)∑_i∈U[-[V·(1-α)β+H_i(t)]·D_s,i(t)] (20)。

9.基于Lyapunov优化的多服务器移动边缘计算卸载装置，其特征在于，包括：

队列构建模块，用于为每个移动设备的产生的任务构建任务缓存队列，并为每个移动设备需要卸载但未被处理的任务创建虚拟任务缓存队列；

模型建立模块，用于建立终端功耗模型、带宽模型和QoE模型；

信息收集模块，用于在每个预设时间片，收集移动设备的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况；

函数构建模块，用于根据收集的任务缓存队列信息、虚拟缓存队列信息以及服务器的带宽情况，构建李雅普诺夫漂移加惩罚函数；

卸载决策模块，用于基于李雅普诺夫漂移加惩罚函数，求解出当前时间片内的计算卸载决策，其中，计算卸载决策用以表征移动终端产生的计算任务在本地执行的任务量以及卸载到边缘服务器执行的任务量。

10.一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现如权利要求1至8中任一项权利要求所述的方法。