一种基于李雅普诺夫优化的计算卸载与资源分配方法

摘要

本发明公开了一种基于李雅普诺夫优化的计算卸载与资源分配方法，应用于移动边缘计算任务卸载系统，移动边缘计算任务卸载系统包括M个车载移动终端和N个移动边缘计算服务器。本方法确定移动边缘计算任务卸载系统的总时延、总消耗能耗以及总任务迁移开销的加权和为系统开销，并对此建模。随后通过使用李雅普诺夫优化理论对系统总开销最小化问题进行求解，并使用迭代的方法计算卸载决策、车载移动终端对任务的计算速率、车载移动终端的发射功率以及移动边缘计算服务器对任务的计算速率，得到最优的系统开销，进而降低系统的总开销，相对于现有技术中没有考虑移动终端动态越区所带来的额外开销，这样的计算结构更加准确。

说明书

技术领域

本发明属于移动边缘计算技术领域，具体涉及一种基于李雅普诺夫优化的计算卸载与资源分配方法。

背景技术

5G提供了一种高度灵活且可扩展的网络技术，使得万事万物均可以相互连接，即支持了万物互联。随着物联网和无线通信技术不断发展并完善，各类新型移动应用蜂拥而至，导致移动终端的数量呈爆炸性增长，造成移动资源的大量消耗。作为5G的关键技术，移动边缘计算服务器可以看作一种新型架构，相较移动云计算，移动边缘计算服务器计算为任务卸载提供了更低的时延和更好的计算灵活度。移动终端任务可以下沉至部署在移动边缘计算服务器上进行处理，从而降低计算的时延与能耗，还可以有效提高服务质量与用户体验质量。

现有技术中，将车载移动终端所产生的任务迁移开销纳入考虑比较困难。在复杂移动性场景下，此类问题分析都是基于用户一维随机均匀运动或二维随机均匀运动场景下进行，而真实场景用户一般都是处于二维非匀速随机运动的移动场景。目前边缘计算任务卸载的研究中针对多移动终端多移动边缘计算服务器的情况，最小化平均处理时延以及处理能耗的研究已经较为完善，但是都没有考虑移动终端动态越区所带来的额外开销，导致计算偏差较大。

发明内容

本发明的目的在于针对解决背景技术中提出的问题，提出基于李雅普诺夫优化的计算卸载与资源分配方法。

为实现上述目的，本发明所采取的技术方案为：

本发明提出的基于李雅普诺夫优化的计算卸载与资源分配方法，应用于移动边缘计算任务卸载系统，移动边缘计算任务卸载系统包括M个车载移动终端和N个移动边缘计算服务器，基于李雅普诺夫优化的计算卸载与资源分配方法，包括：

以移动边缘计算任务卸载系统的总时延、总消耗能耗以及总任务迁移开销的加权和为系统开销，建立优化模型如下：

其中，

其中，E

在优化模型中引入时延惩罚函数Φ(t)，将优化模型简化为：

П

s.t.C2,C3,C7,C8

根据时间片段对П

П

s.t.C2,C3,C7,C8

根据李雅普诺夫理论对能耗建立虚拟队列与惩罚函数并计算李雅普诺夫的漂移上边界，将优化模型的子问题转换为：

Π

s.t.C2,C3,C7,C8

其中，Q

根据∏

随机生成卸载决策、车载移动终端对任务的计算速率、车载移动终端的发射功率以及移动边缘计算服务器对任务的计算速率的初始解，然后利用迭代算法进行迭代计算，并每次迭代后更新系统开销，直至系统开销的值处于收敛，输出最终的系统开销为最优系统开销。

优选地，总时延表示如下：

T

其中，

H

其中，

优选地，总开销表示如下：

其中，

当车载移动终端发生区域迁移时，满足：

q

当车载移动终端不发生区域迁移时，满足：

q

其中，ε表示车载移动终端发生区域迁移产生的开销，

优选地，根据李雅普诺夫理论对能耗建立虚拟队列与惩罚函数并计算李雅普诺夫的漂移上边界，将优化模型的子问题转换为∏

由于车载移动终端的能耗积压量受到当前剩余电量的影响，而当前剩余电量又取决于上一时刻总消耗能耗，根据李雅普诺夫理论建立虚拟队列Q

Q

其中，Q

根据李雅普诺夫理论，t时刻的二次李雅普诺夫函数表示为：

其中，L(t)表示虚拟队列Q

t+1时刻虚拟队列总积压的标量与t时刻虚拟队列总积压的标量的差叫做李雅普诺夫漂移ΔL(t)，且表示为：

ΔL(t)＝L(t+1)-L(t)

将李雅普诺夫漂移代入漂移定理，表示为：

其中，V是一个恒正的控制参数，表示系统开销与虚拟队列之间的权衡；

利用漂移定理代入能耗积压量的推导：

因此，

且，

其中，E

B(t)≤B

且，

得到漂移定理满足：

由于B为常量，将公式(1)即可转化为∏

优选地，根据∏

∏

∏

车载移动终端的当前剩余电量E

其中，

则车载移动终端的当前剩余电量的最优解

建立总消耗能耗与系统开销模型∏

∏

s.t.C2,C3,C7,C8

计算卸载决策：定义车载移动终端对任务的计算速率、移动边缘计算服务器对任务的计算速率、车载移动终端的发射功率已知，在单时隙τ下求解卸载决策，将∏

∏

s.t.

将Π

其中，λ

由此可以得到卸载策略S

计算车载移动终端对任务的计算速率：定义卸载决策、移动边缘计算服务器对任务的计算速率以及车载移动终端的发射功率已知，在单时隙下求解车载移动终端对任务的计算速率，将Π

Π

s.t.(1-s

其中，E

将Π

其中，s

则车载移动终端对任务的计算速率f

计算车载移动终端的发射功率：定义卸载决策、车载移动终端对任务的计算速率以及移动边缘计算服务器对任务的计算速率已知，在单时隙下求解车载移动终端的发射功率，将Π

将Π

构建辅助函数

且，

对辅助函数求一阶导数：

令：

对

当

根据公式(2)中总时延T

再根据公式(2)中的第二个约束条件进行求解，当

则得到公式(2)中的第二个约束条件还为：

则车载移动终端的发射功率

其中，

计算移动边缘计算服务器对任务的计算速率：定义最佳卸载决策、车载移动终端对任务的计算速率以及车载移动终端的发射功率已知，在单时隙下求解移动边缘计算服务器对任务的计算速率，将∏

Π

s.t.

将Π

函数

根据Π

则计算服务器对任务的计算速率

与现有技术相比，本发明的有益效果为：

本方法确定移动边缘计算任务卸载系统的总时延、总消耗能耗以及总任务迁移开销的加权和为系统开销，并对此建模。随后通过使用李雅普诺夫优化理论对系统总开销最小化问题进行求解，并使用迭代的方法计算卸载决策、车载移动终端对任务的计算速率、车载移动终端的发射功率以及移动边缘计算服务器对任务的计算速率，得到最优的系统开销，进而降低系统的总开销，相对于现有技术中没有考虑移动终端动态越区所带来的额外开销，这样的计算结构更加准确。

附图说明

图1为本发明基于李雅普诺夫优化的计算卸载与资源分配方法的模块框图；

图2为本发明基于李雅普诺夫优化的计算卸载与资源分配方法的流程图。

具体实施方式

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

需要说明的是，当组件被称为与另一个组件“连接”时，它可以直接与另一个组件连接或者也可以存在居中的组件。除非另有定义，本文所使用的所有的技术和科学术语与属于本申请的技术领域的技术人员通常理解的含义相同。本文中在本申请的说明书中所使用的术语只是为了描述具体的实施例的目的，不是在于限制本申请。

如图1-2所示，一种基于李雅普诺夫优化的计算卸载与资源分配方法，应用于移动边缘计算任务卸载系统，移动边缘计算任务卸载系统包括M个车载移动终端和N个移动边缘计算服务器，基于李雅普诺夫优化的计算卸载与资源分配方法，包括：

需要说明的是，如图1所示，每个区域内有一个移动边缘计算服务器，多个车载移动终端，由于车载移动终端的计算能力有限，每个车载移动终端都可以将其任务全部或部分卸载到其所在区域内的移动边缘计算服务器进行远程执行。除此之外，车载移动终端的位置是随机分布的，且处于持续移动的状态，而边缘计算服务器是处于静止状态，每一个时隙下车载移动终端的位置静止。

步骤S1、以移动边缘计算任务卸载系统的总时延、总消耗能耗以及总任务迁移开销的加权和为系统开销，建立优化模型如下：

其中，

其中，E

具体为，车载移动终端的集合M＝{1,2,..m.,M}，移动边缘计算(Mobile EdgeComputing，MEC)服务器的集合N＝{1,2,..n..,N}，不同时刻t∈T＝{1,2,...,T}，各移动边缘计算服务器的工作时隙为τ，且时隙τ为时刻t的一个时间片段。

车载移动终端的每个任务用五元组表示{λ

车载移动终端的任务之间相互独立。

由于下行数据量较上行数据量十分小(即移动边缘计算服务器处理完任务反馈回的数据量较传输给移动边缘计算服务器的任务较小)，因此移动边缘计算服务器回传计算结果给车载移动终端的时延可以忽略不计。

总时延表示如下：

T

其中，

H

其中，

总消耗能耗表示如下：

其中，

其中，

总开销表示如下：

其中，

当车载移动终端发生区域迁移时，满足：

q

当车载移动终端不发生区域迁移时，满足：

q

其中，ε表示车载移动终端发生区域迁移产生的开销，

步骤S2、在优化模型中引入时延惩罚函数Φ(t)，将优化模型简化为：

П

s.t.C2,C3,C7,C8

当t时刻车载移动终端执行能耗超过车载移动终端的当前剩余电量，或车载移动终端的执行时延超过该任务的最大容忍时延时，Φ(t)＝+∝，当t时刻车载移动终端执行能耗不超过车载移动终端的当前剩余电量，或车载移动终端的执行时延不超过该任务的最大容忍时延时，Φ(t)＝0。

步骤S3、根据时间片段对П

П

s.t.C2,C3,C7,C8

步骤S4、根据李雅普诺夫理论对能耗建立虚拟队列与惩罚函数并计算李雅普诺夫的漂移上边界，将优化模型的子问题转换为：

Π

s.t.C2,C3,C7,C8

其中，Q

具体为，由于车载移动终端的能耗积压量受到当前剩余电量的影响，而当前剩余电量又取决于上一时刻总消耗能耗，根据李雅普诺夫理论建立虚拟队列Q

Q

其中，Q

根据李雅普诺夫理论，t时刻的二次李雅普诺夫函数表示为：

其中，L(t)表示虚拟队列Q

t+1时刻虚拟队列总积压的标量与t时刻虚拟队列总积压的标量的差叫做李雅普诺夫漂移ΔL(t)，且表示为：

ΔL(t)＝L(t+1)-L(t)

将李雅普诺夫漂移代入漂移定理，表示为：

其中，V是一个恒正的控制参数，表示系统开销与虚拟队列之间的权衡；

利用漂移定理代入能耗积压量的推导：

因此，

且，

其中，E

B(t)≤B

且，

得到漂移定理满足：

由于B为常量，将公式(1)即可转化为Π

步骤S5、根据Π

具体为，Π

П

车载移动终端的当前剩余电量E

其中，

则车载移动终端的当前剩余电量的最优解

建立总消耗能耗与系统开销模型∏

∏

s.t.C2,C3,C7,C8

计算卸载决策：定义车载移动终端对任务的计算速率、移动边缘计算服务器对任务的计算速率、车载移动终端的发射功率已知，在单时隙τ下求解卸载决策，将∏

∏

s.t.

将Π

其中，λ

由此可以得到卸载策略S

计算车载移动终端对任务的计算速率：定义卸载决策、移动边缘计算服务器对任务的计算速率以及车载移动终端的发射功率已知，在单时隙下求解车载移动终端对任务的计算速率，将Π

Π

s.t.(1-s

其中，E

将Π

其中，s

则车载移动终端对任务的计算速率f

计算车载移动终端的发射功率：定义卸载决策、车载移动终端对任务的计算速率以及移动边缘计算服务器对任务的计算速率已知，在单时隙下求解车载移动终端的发射功率，将П

将Π

构建辅助函数

且，

对辅助函数求一阶导数：

令：

对

当

根据公式(2)中总时延T

再根据公式(2)中的第二个约束条件进行求解，当

则得到公式(2)中的第二个约束条件还为：

则车载移动终端的发射功率

其中，

计算移动边缘计算服务器对任务的计算速率：定义最佳卸载决策、车载移动终端对任务的计算速率以及车载移动终端的发射功率已知，在单时隙下求解移动边缘计算服务器对任务的计算速率，将П

Π

s.t.

将Π

函数

根据П

则计算服务器对任务的计算速率

步骤S6、随机生成卸载决策、车载移动终端对任务的计算速率、车载移动终端的发射功率以及移动边缘计算服务器对任务的计算速率的初始解，然后利用迭代算法进行迭代计算，并每次迭代后更新系统开销，直至系统开销的值处于收敛，输出最终的系统开销为最优系统开销。

具体为，如图2所示，本实施例中的迭代算法基于python实现，向算法中输入车载移动终端的数量M、移动边缘计算服务器的数量N、信道带宽ω、车载移动终端对任务的计算的最大速率

本方法确定移动边缘计算任务卸载系统的总时延、总消耗能耗以及总任务迁移开销的加权和为系统开销，并对此建模。随后通过使用李雅普诺夫优化理论对系统总开销最小化问题进行求解，并使用迭代的方法计算卸载决策、车载移动终端对任务的计算速率、车载移动终端的发射功率以及移动边缘计算服务器对任务的计算速率，得到最优的系统开销，进而降低系统的总开销，相对于现有技术中没有考虑移动终端动态越区所带来的额外开销，这样的计算结构更加准确。

以上所述实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。

以上所述实施例仅表达了本申请描述较为具体和详细的实施例，但并不能因此而理解为对申请专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护范围。因此，本申请专利的保护范围应以所附权利要求为准。