CN109343904B - 一种基于Lyapunov优化的雾计算动态卸载方法 - Google Patents

Abstract

本发明提出了一种基于优化的雾计算动态卸载方法，属于无线网络通信领域。本发明将计算请求分为局部计算部分和雾计算部分。通过将计算密集型的请求卸载到雾节点，可以显著提高应用程序的性能。利用一种基于Lyapunov优化的在线联合无线电和计算资源算法，推导了Lyapunov偏移惩罚函数的上界。通过从不同决策变量的角度最小化上界。利用凸优化方法，得到局部处理器的最优CPU周期频率。利用预定义的卸载优先函数，得出最优子信道的最优传输功率。而在雾节点上，通过反证法证明，获得最优请求调度决策。

Description

一种基于Lyapunov优化的雾计算动态卸载方法

技术领域

本发明涉及无线网络通信领域，尤其涉及一种基于Lyapunov优化的雾计算动态卸载方法，利用该方法可以有效得提高系统的计算性能。

背景技术

移动设备已经成为我们日常生活中不可或缺的一部分，因为它们几乎可以随时随地提供方便的通讯。先进的移动技术和高数据率的无线网络也刺激了移动应用市场。然而，由于资源和电池寿命的限制，有限的计算能力和执行复杂应用程序的需求之间的差距正在逐渐增大。许多计算密集型和对时延敏感的移动应用程序在智能手机上执行时表现不佳，如图像处理、棋类游戏等。

最近的研究表明，移动云计算技术提供了一个很有希望的机会，通过将计算密集型的计算请求卸载到云上进行执行，以克服移动设备的硬件限制，并且节省能耗。目前已有移动云架构类型有传统的中心云、临时移动云和微云等。传统的中心云可以提供巨大的存储空间、强大的计算能力以及可靠的安全性等。但是传统的中心云通常是远程定位，与用户距离远，会产生较高的延迟。因此，远端云不适合对延迟敏感的移动应用。雾计算被称为“云边缘”，更加接近移动设备和终端用户，降低延迟，提升应用程序的性能。雾计算使计算和无线电资源更加接近终端用户，从而提高计算和无线电方面的扩展性。使用移动云计算，对来自物联网应用程序的移动请求可以在本地执行，也可以将其卸载到云上进行处理。一般来说，根据决策时间，计算卸载包括静态卸载和动态卸载。静态卸载是指在启动前确定卸载方案，在完成前不做任何更改，效率很低。与随机计算需求、时变无线衰落信道和不断变化的计算资源等相协调，动态计算卸载更具有实用性和挑战性。

发明内容

本发明的目的在于提供一种基于Lyapunov优化的雾计算动态卸载方法，利用该方法可以有效得提高系统的计算性能。得到最优的CPU周期频率，最优的功率与及请求调度决策。

为实现上述目的，采用了以下技术方案：一种基于Lyapunov优化的雾计算动态卸载方法，主要设备包括移动设备、接入节点、雾节点、雾服务器，其特征在于，所述方法包括以下步骤：

步骤1：移动设备执行密集型计算应用并且产生一系列计算服务请求任务；

步骤2：移动设备将步骤1中部分计算请求任务通过接入接点卸载到雾服务器上；

步骤3：建立雾服务器计算服务请求任务分配模型：在时间段t，移动设备i计算请求数量D_i,o(t)，每个移动设备请求雾节点缓存区的队列长度T(t)＝max{T₁(t),...,T_i(t),...,T_N(t)}，T_i(t)是移动设备i的请求队列长度，确定该分配模型雾节点的平均能耗

基于该分配模型的总决策V(t)＝[f(t),ρ(t),p_up(t),D_f(t),f_s(t)]对平均能耗

进行最小化，其中，f(t)＝[f₁(t),...,f_i(t),...,f_N(t)]为每个移动设备在时间段t内的CPU周期频率。ρ(t)＝[ρ₁(t),...,ρ_i(t),...,ρ_N(t)]表示所有的移动设备在时间段t内的子信道分配矩阵。其中ρ_i(t)＝[ρ_i,1(t),...,ρ_i,k(t),...,ρ_i,K(t)]表示移动设备i在时间段t上的子信道分配向量。p_up(t)＝[p₁(t),...,p_i(t),...,p_N(t)]表示为所有的移动设备在时间段t上的上行链路传输功率矩阵。其中p_i(t)＝[p_i,1(t),...,p_i,k(t),...,p_i,K(t)]表示为移动设备i在时间段t子信道的传输功率的集合。D_f(t)＝[D_f,1(t),...,D_f,i(t),...,D_f,N(t)]表示每个移动设备在时间段t内的雾计算的请求数量。f_s(t)表示每个雾服务器的CPU周期频率。

步骤4：集成雾服务器的雾节点依据步骤3中的分配模型对步骤2卸载的计算服务请求任务进行分配；

步骤5：基于Lyapunon函数

获取移动设备和雾节点的请求缓存区Ω(t)＝(Q(t),T(t))，其中Q(t)为移动设备请求缓存的队列长度；基于平均能耗

进行最小化对步骤4分配过程中的总决策进行求解，获取基于Lyapunov优化的雾计算动态卸载方法的最佳总决策

进一步的技术方案在于：步骤1中计算服务请求任务具体计算步骤如下：在时间段t内，移动设备产生的计算任务到达过程，遵循平均速率为A_i(t)的泊松分布过程；计算服务请求任务分移动设备本地执行和雾服务器雾计算执行；本地执行计算请求的数据大小为D_l,i(t)(bits)，雾计算执行的数据大小为D_i,o(t)(bits)；到达但尚未在本地执行或卸载的计算请求，将在具有足够大容量的移动设备中的缓存区域的请求缓冲区中排队，在时间段t内，请求缓存的队列长度为Q(t)＝[Q₁(t),...,Q_i(t),...,Q_N(t)]，则t+1时间段的缓存队列长度表示为：Q_i(t+1)＝max{Q_i(t)-D_E,i(t),0}+A_i(t)；

其中D_E,i(t)＝D_l,i(t)+D_o,i(t)表示从移动设备的请求缓冲区发出的请求量，A_i(t)表示移动设备i在时间段t内所产生的计算服务请求量。

进一步的技术方案在于：步骤2中具体卸载步骤如下：移动设备i选择第k个子信道通道以频分多址的方式向无线接入点卸载计算请求任务，进行数据的传输；数据的传输速率为：

在时间段t内，从移动设备i上卸载的计算请求数量为：

在卸载过程中，上行链路传输上消耗的能量为：

其中ρ_i,k(t)∈{0,1}作为子通道分配指示器，B表示子信道带宽，h_i,k(t)表示信道收益，p_i,k(t)表示数据传输功率。

进一步的技术方案在于：在步骤3中，首先雾节点将为每一个移动设备保留一个请求缓冲区来存储已经卸载但是没有被雾服务器执行的请求；每个移动设备在时间段t开始时的请求缓存区的队列长度表示为T(t)＝max{T₁(t),...,T_i(t),...,T_N(t)}，T_i(t)是移动设备i的请求队列长度；在时间段t内的雾节点请求调度决策可以表示为：

D_f(t)＝[D_f,1(t),...,D_f,i(t),...,D_f,N(t)]，表示在时间段t内由雾节点服务器执行的请求量；则在t+1时间段中，T_i(t+1)＝max{T_i(t)-D_f,i(t),0}+D_o,i(t)

雾节点服务器在时间段t中的动态能耗为：E_f(t)＝ck_f,sf³(t)τ

在时间段t内总的能量消耗为：

在T时间段内，该雾计算系统的平均能耗为：

基于V(t)对

进行最小化，设用P1表示该平均能耗最小化的问题，表示为：

P1:

受到的约束集s.t表示：0<f_i(t)<f_i,max,0<p_i,k(t)<p_i,max,0<f_s(t)<f_s,max；

其中ω_i为移动设备i的能量消耗权重，ω_N+1为雾节点的能量消耗权重，并且

用V(t)＝[f(t),ρ(t),p_up(t),D_f(t),f_s(t)]表示在时间段t内该雾计算系统的总的决策。

进一步的技术方案在于：在步骤5中，具体计算步骤如下：

(1)首先定义了Lyapunov函数为：

条件Lyapunov偏移惩罚函数可以表示为：Δ(Ω(t))＝E[L(Ω(t+1))-L(Ω(t))|Ω(t)]；

Lyapunov偏移惩罚函数可表示为:Δ_v(Ω(t))＝Δ(Ω(t))+VE[E_total(t)|Ω(t)]；

其V是算法中的一个控制参数，并且基于任何V(t)的可行集合，都能够找到一个Δv(Ω(t))的上界值，其上确界可以表示为：

由于CT是一个常数，要得到Δv(Ω(t))的上界值，则可以通过最小化

得出；

(2)在初始的时间段t内，获得Ω(t)；其中Ω(t)＝(Q(t),T(t))是表示移动设备和雾节点的请求缓存区；

(3)通过解决问题P2，确定分配模型的总决策集合V(t)＝[f(t),ρ(t),p_up(t),D_f(t),f_s(t)]；

其中，问题P2：

约束集为s.t：0<f_i(t)<f_i,max,0<p_i,k(t)<p_i,max,0<f_s(t)<f_s,max，

(4)在时间段t+1，获得Ω(t+1)，重复第(2)步和第(3)步，直到获得系统所有时间段的系统决策，即基于Lyapunov优化的雾计算动态卸载方法的的最佳总决策

进一步的技术方案在于：由于步骤5中的问题P2求解比较困难和复杂，所以，基于Lyapunov优化的雾计算动态卸载方法的的最佳总决策的最优频率、传输功率和雾节点的最优决策分别依据下述三个子问题进行求解：

(1)子问题1：

约束为：0<f_i(t)<f_i,max

可以求解出本地处理器的最优CPU周期的频率为：

(2)子问题2：

约束为：0<p_i,k(t)<p_i,max,

可以求出最优的传输功率为：

(3)子问题3：

约束为：0<f_s(t)<f_s,max,0<D_f,i(t)<T_i(t),

可以求出请求调度决策为：

采用上述技术方案的有益效果为：本文提出通过将计算密集型的请求卸载到雾节点，可以显著提高应用程序的性能。利用一种基于Lyapunov优化的在线联合无线电和计算资源算法，推导了Lyapunov偏移惩罚函数的上界。通过从不同决策变量的角度最小化上界。利用凸优化方法，得到局部处理器的最优CPU周期频率。利用预定义的卸载优先函数，得出最优子信道的最优传输功率。而在雾节点上，通过反证法证明，获得服务器的最优CPU周期频率和最优请求调度决策。

附图说明

图1为本发明的系统模型。

图2为本发明的实施实例中的一个流程图。

图3为本发明的Lyapunov联合优化无线和计算资源的在线算法流程图。

图4为本发明的移动设备的CPU周期频率图。

图5为本发明的移动设备在各个子信道上的优先权函数图。

图6为本发明的移动设备的传输功率图。

图7为雾服务器的CPU周期频率图。

具体实施方式

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

在下面的描述中阐述了很多具体细节以便于充分理解本发明，但是本发明还可以采用其他不同于在此描述的其它方式来实施，本领域技术人员可以在不违背本发明内涵的情况下做类似推广，因此本发明不受下面公开的具体实施例的限制：

本发明提出了一种基于Lyapunov优化的雾计算动态卸载方法，主要设备包括移动设备、接入节点、雾节点、雾服务器，其特征在于，所述方法包括以下步骤：

步骤1：移动设备执行密集型计算应用并且产生一系列计算服务请求任务；

其中，计算服务请求任务具体计算步骤如下：在时间段t内，移动设备产生的计算任务到达过程，遵循平均速率为A_i(t)的泊松分布过程；计算服务请求任务分移动设备本地执行和雾服务器雾计算执行；本地执行计算请求的数据大小为D_l,i(t)(bits)，雾计算执行的数据大小为D_i,o(t)(bits)；到达但尚未在本地执行或卸载的计算请求，将在具有足够大容量的移动设备中的缓存区域的请求缓冲区中排队，在时间段t内，请求缓存的队列长度为Q(t)＝[Q₁(t),...,Q_i(t),...,Q_N(t)]，则t+1时间段的缓存队列长度表示为：Q_i(t+1)＝max{Q_i(t)-D_E,i(t),0}+A_i(t)；

其中D_E,i(t)＝D_l,i(t)+D_o,i(t)表示从移动设备的请求缓冲区发出的请求量，A_i(t)表示移动设备i在时间段t内所产生的计算服务请求量。

步骤2：移动设备将步骤1中部分计算请求任务通过接入接点卸载到雾服务器上；

其中，具体卸载步骤如下：移动设备i选择第k个子信道通道以频分多址的方式向无线接入点卸载计算请求任务，进行数据的传输；数据的传输速率为：

在时间段t内，从移动设备i上卸载的计算请求数量为：

在卸载过程中，上行链路传输上消耗的能量为：

其中ρ_i,k(t)∈{0,1}作为子通道分配指示器，B表示子信道带宽，h_i,k(t)表示信道收益，p_i,k(t)表示数据传输功率。

步骤3：建立雾服务器计算服务请求任务分配模型：在时间段t，移动设备i计算请求数量D_i,o(t)，每个移动设备请求雾节点缓存区的队列长度T(t)＝max{T₁(t),...,T_i(t),...,T_N(t)}，T_i(t)是移动设备i的请求队列长度，确定该分配模型雾节点的平均能耗

基于该分配模型的总决策V(t)＝[f(t),ρ(t),p_up(t),D_f(t),f_s(t)]对平均能耗

进行最小化，其中，f(t)＝[f₁(t),...,f_i(t),...,f_N(t)]为每个移动设备在时间段t内的CPU周期频率。ρ(t)＝[ρ₁(t),...,ρ_i(t),...,ρ_N(t)]表示所有的移动设备在时间段t内的子信道分配矩阵。其中ρ_i(t)＝[ρ_i,1(t),...,ρ_i,k(t),...,ρ_i,K(t)]表示移动设备i在时间段t上的子信道分配向量。p_up(t)＝[p₁(t),...,p_i(t),...,p_N(t)]表示为所有的移动设备在时间段t上的上行链路传输功率矩阵。其中p_i(t)＝[p_i,1(t),...,p_i,k(t),...,p_i,K(t)]表示为移动设备i在时间段t子信道的传输功率的集合。D_f(t)＝[D_f,1(t),...,D_f,i(t),...,D_f,N(t)]表示每个移动设备在时间段t内的雾计算的请求数量。f_s(t)表示每个雾服务器的CPU周期频率。

其中具体的为：首先雾节点将为每一个移动设备保留一个请求缓冲区来存储已经卸载但是没有被雾服务器执行的请求；每个移动设备在时间段t开始时的请求缓存区的队列长度表示为T(t)＝max{T₁(t),...,T_i(t),...,T_N(t)}，T_i(t)是移动设备i的请求队列长度；在时间段t内的雾节点请求调度决策可以表示为：

D_f(t)＝[D_f,1(t),...,D_f,i(t),...,D_f,N(t)]，表示在时间段t内由雾节点服务器执行的请求量；则在t+1时间段中，T_i(t+1)＝max{T_i(t)-D_f,i(t),0}+D_o,i(t)

雾节点服务器在时间段t中的动态能耗为：E_f(t)＝ck_f,sf³(t)τ

在时间段t内总的能量消耗为：

在T时间段内，该雾计算系统的平均能耗为：

基于V(t)对

进行最小化，设用P1表示该平均能耗最小化的问题，表示为：

P1:

受到的约束集s.t表示：0<f_i(t)<f_i,max,0<p_i,k(t)<p_i,max,0<f_s(t)<f_s,max；

其中ω_i为移动设备i的能量消耗权重，ω_N+1为雾节点的能量消耗权重，并且

用V(t)＝[f(t),ρ(t),p_up(t),D_f(t),f_s(t)]表示在时间段t内该雾计算系统的总的决策。

步骤4：集成雾服务器的雾节点依据步骤3中的分配模型对步骤2卸载的计算服务请求任务进行分配；

步骤5：基于Lyapunon函数

获取移动设备和雾节点的请求缓存区Ω(t)＝(Q(t),T(t))，其中Q(t)为移动设备请求缓存的队列长度；基于平均能耗

进行最小化对步骤4分配过程中的总决策进行求解，获取基于Lyapunov优化的雾计算动态卸载方法的最佳总决策

其中具体计算步骤如下：

(1)首先定义了Lyapunov函数为：

条件Lyapunov偏移惩罚函数可以表示为：Δ(Ω(t))＝E[L(Ω(t+1))-L(Ω(t))|Ω(t)]；

Lyapunov偏移惩罚函数可表示为:Δ_v(Ω(t))＝Δ(Ω(t))+VE[E_total(t)|Ω(t)]；

其V是算法中的一个控制参数，并且基于任何V(t)的可行集合，都能够找到一个Δv(Ω(t))的上界值，其上确界可以表示为：

由于CT是一个常数，要得到Δv(Ω(t))的上界值，则可以通过最小化

得出；

(2)在初始的时间段t内，获得Ω(t)；其中Ω(t)＝(Q(t),T(t))是表示移动设备和雾节点的请求缓存区；

(3)通过解决问题P2，确定分配模型的总决策集合V(t)＝[f(t),ρ(t),p_up(t),D_f(t),f_s(t)]；

其中，问题P2：

约束集为s.t：0<f_i(t)<f_i,max,0<p_i,k(t)<p_i,max,0<f_s(t)<f_s,max，

(4)在时间段t+1，获得Ω(t+1)，重复第(2)步和第(3)步，直到获得系统所有时间段的系统决策，即基于Lyapunov优化的雾计算动态卸载方法的的最佳总决策

基于Lyapunov优化的雾计算动态卸载方法的的最佳总决策的最优频率、传输功率和雾节点的最优决策分别依据下述三个子问题进行求解：

(1)子问题1：

约束为：0<f_i(t)<f_i,max

可以求解出本地处理器的最优CPU周期的频率为：

(2)子问题2：

约束为：0<p_i,k(t)<p_i,max,

可以求出最优的传输功率为：

(3)子问题3：

约束为：0<f_s(t)<f_s,max,0<D_f,i(t)<T_i(t),

可以求出请求调度决策为：

如图1所示为本发明的系统模型。图1呈现了一个移动设备请求任务卸载的高效动态雾计算系统模型图。在该模型图中，有N个单核移动设备，一个无线接入点，一个雾节点。每个移动设备都包含一个具有DVFS技术的处理器、一个缓存，其中包含一个先进先出(FIFO)队列，用于存储已到达但尚未在本地执行的请求或未卸载的请求，以及一个连接无线网络的无线接口。无线接入点主要负责以频分多址的方式将数据传输到雾节点。雾节点包含一个容量较大的缓存，用于存储已从不同移动设备卸载的，但是未执行的请求，一个前端调度程序，将分配的数据流统一分配到服务器中。雾节点主要是为移动设备执行计算请求。

图2为本发明的一个具体实施例的具体方法流程图，主要包括以下步骤：

步骤1：移动设备执行密集型计算应用并且产生一系列计算服务请求；

步骤2：移动设备将部分计算请求通过无线接入点卸载到雾服务器上进行计算；

步骤3：集成了服务器的雾节点对卸载的任务进行计算与及分配服务资源；步骤4：提出了一种基于Lyapunov优化联合无线和计算资源的在线算法，用于最小化Lyapunov偏移惩罚函数的上确界；

步骤5：基于上确界的值，分别从三个子问题求出局部处理的最优频率、传输功率和雾节点的最优决策。

图3为基于Lyapunov联合优化无线和计算资源的在线算法。如果通过解决问题P2，得到了所有时间段的系统决策，则结束循环，否则将继续进行解决下一个时间段的系统决策。

1、基于不同的控制参数V的值，求出最优的CPU周期频率。假设时间段τ＝10^-6s.切换电容为k_i＝10^-19，卸载数据的大小为Q_i＝10⁶bits,处理1-bits所需要的CPU周期频率为L＝10⁵，权重为ω_i＝0.1。下图则为基于不同的控制参数V的值，最优的CPU周期频率值。如图4所示。在图4中，V的取值有V＝10⁸，V＝2*10⁸，V＝3*10⁸，V＝4*10⁸。当V取不同值时，目标函数的值在可行解的区域内是先递减，后递增，所以目标函数在拐点处能够取得最小的值，即为最优的CPU周期频率。

2、对卸载优先权函数和子信道分配情况进行建立模型。假设有6个移动设备和8个子信道需要在雾计算系统中进行分配。子信道的带宽为10⁶HZ，噪声功率为N_o＝10^-9W。下图为所有移动设备在每个子信道上的优先权函数值。如图5所示。由图5可以看出，基于不同的ω_i值，移动设备的卸载优先权函数值也就不同。每个移动设备可以选择优先权值最大的子信道进行任务的传输。移动设备1选择子信道6，移动设备2选择子信道2，移动设备3选择子信道7，移动设备4选择子信道5，移动设备5选择子信道1，移动设备6选择子信道8。可以看出移动设备选择了信道增益最大的子信道。

3、基于不同值的控制参数V和权重因子ω，求出移动设备的最优传输功率。如图6所示。图中分别取了4组不同的值，分别为V＝6*10⁹,ω＝0.40，V＝6*10⁹,ω＝0.20，V＝4*10⁹,ω＝0.25，V＝9*10⁹,ω＝0.25。从图中可以看出，目标函数值在可行解范围内，是先递减，后递增的，所以每个曲线的拐点恰好是移动设备在所选择的子信道上的最优传输功率。

4、基于不同的权重因子ω_N+1的值，求出雾计算系统中的雾服务器的最优CPU周期频率。如图7所示。由图中可以看出，分别取ω_N+1的值为ω＝0.03，ω＝0.05，ω＝0.08，ω＝0.100，目标函数的值在可行解的区域内是先递减，后递增，所以在拐点处取得最优解。

Claims (6)

1.一种基于Lyapunov优化的雾计算动态卸载方法，主要设备包括移动设备、接入节点、雾节点、雾服务器，其特征在于，所述方法包括以下步骤：

步骤1：移动设备执行密集型计算应用并且产生一系列计算服务请求任务；

步骤2：移动设备将步骤1中部分计算请求任务通过接入接点卸载到雾服务器上；

步骤3：建立雾服务器计算服务请求任务分配模型：雾计算执行的数据大小为D_i,o(t)，每个移动设备请求雾节点缓存区的队列长度T(t)＝max{T₁(t),...,T_i(t),...,T_N(t)}，T_i(t)是移动设备i的请求队列长度，确定该分配模型雾节点的平均能耗

基于该分配模型的总决策V(t)＝[f(t),ρ(t),p_up(t),D_f(t),f_s(t)]对平均能耗

进行最小化，其中，f(t)＝[f₁(t),...,f_i(t),...,f_N(t)]为每个移动设备在时间段t内的CPU周期频率，其中i＝1,2…i,…,N,N为移动设备的总数量；ρ(t)＝[ρ₁(t),...,ρ_i(t),...,ρ_N(t)]表示所有的移动设备在时间段t内的子信道分配矩阵，其中ρ_i(t)＝[ρ_i,1(t),...,ρ_i,k(t),...,ρ_i,K(t)]表示移动设备i在时间段t上的子信道分配向量，其中，k＝1,2…k,…,K,K为子信道的总数量，k表示第k个子信道；p_up(t)＝[p₁(t),...,p_i(t),...,p_N(t)]表示为所有的移动设备在时间段t上的上行链路传输功率矩阵，其中p_i(t)＝[p_i,1(t),...,p_i,k(t),...,p_i,K(t)]表示为移动设备i在时间段t子信道的传输功率的集合；D_f(t)＝[D_f,1(t),...,D_f,i(t),...,D_f,N(t)]表示每个移动设备在时间段t内的雾计算的请求数量；f_s(t)表示每个雾服务器的CPU周期频率；

步骤4：集成雾服务器的雾节点依据步骤3中的分配模型对步骤2卸载的计算服务请求任务进行分配；

步骤5：基于Lyapunov函数

获取移动设备和雾节点的请求缓存区Ω(t)＝(Q(t),T(t))，其中Q(t)为移动设备请求缓存的队列长度；基于平均能耗

构造Lyapunov偏移惩罚函数，推导Lyapunov偏移惩罚函数的上界，进行最小化对步骤4分配过程中的总决策进行求解；利用凸优化方法，得到移动设备的本地执行的最优CPU周期频率；基于预先定义的卸载优先函数，得到卸载策略和卸载过程中的最优传输功率；利用反证法，得到雾服务器的最优执行策略，从而获取基于Lyapunov优化的雾计算动态卸载方法的最佳总决策

2.根据权利要求1所述的一种基于Lyapunov优化的雾计算动态卸载方法；其特征在于：步骤1中计算服务请求任务具体计算步骤如下：在时间段t内，移动设备产生的计算任务到达过程，遵循平均速率为A_i(t)的泊松分布过程；计算服务请求任务分移动设备本地执行和雾服务器雾计算执行；本地执行计算请求的数据大小为D_l,i(t)(bits)，雾计算执行的数据大小为D_i,o(t)(bits)；到达但尚未在本地执行或卸载的计算请求，将在具有足够大容量的移动设备中的缓存区域的请求缓冲区中排队，在时间段t内，请求缓存的队列长度为Q(t)＝[Q₁(t),...,Q_i(t),...,Q_N(t)]，则t+1时间段的缓存队列长度表示为：Q_i(t+1)＝max{Q_i(t)-D_E,i(t),0}+A_i(t)；

其中D_E,i(t)＝D_l,i(t)+D_o,i(t)表示从移动设备的请求缓冲区发出的请求量；D_o,i(t)表示移动设备i卸载到雾服务器服务请求的数量；A_i(t)表示移动设备i在时间段t内所产生的计算服务请求量。

3.根据权利要求2所述的一种基于Lyapunov优化的雾计算动态卸载方法；其特征在于：步骤2中具体卸载步骤如下：移动设备i选择第k个子信道通道以频分多址的方式向无线接入点卸载计算请求任务，进行数据的传输；数据的传输速率为：

在时间段t内，从移动设备i上卸载的计算请求数量为：

在卸载过程中，上行链路传输上消耗的能量为：

其中ρ_i,k(t)∈{0,1}作为子通道分配指示器，B表示子信道带宽，h_i,k(t)表示信道收益，p_i,k(t)表示数据传输功率。

4.根据权利要求3所述的一种基于Lyapunov优化的雾计算动态卸载方法；其特征在于：在步骤3中，首先雾节点将为每一个移动设备保留一个请求缓冲区来存储已经卸载但是没有被雾服务器执行的请求；每个移动设备在时间段t开始时的请求缓存区的队列长度表示为T(t)＝max{T₁(t),...,T_i(t),...,T_N(t)}，T_i(t)是移动设备i的请求队列长度；在时间段t内的雾节点请求调度决策可以表示为：

D_f(t)＝[D_f,1(t),...,D_f,i(t),...,D_f,N(t)]，表示在时间段t内由雾节点服务器执行的请求量；则在t+1时间段中，T_i(t+1)＝max{T_i(t)-D_f,i(t),0}+D_o,i(t)

雾节点服务器在时间段t中的动态能耗为：E_f(t)＝ck_f,sf³(t)τ

在时间段t内总的能量消耗为：

在T时间段内，该雾计算系统的平均能耗为：

基于V(t)对

进行最小化，设用P1表示该平均能耗最小化的问题，表示为：

P1:

受到的约束集s.t表示：0＜f_i(t)＜f_i,max,0＜p_i,k(t)＜p_i,max,0＜f_s(t)＜f_s,max；

其中ω_i为移动设备i的能量消耗权重，ω_N+1为雾节点的能量消耗权重，并且

用V(t)＝[f(t),ρ(t),p_up(t),D_f(t),f_s(t)]表示在时间段t内该雾计算系统的总的决策。

5.根据权利要求4所述的一种基于Lyapunov优化的雾计算动态卸载方法；其特征在于：在步骤5中，具体计算步骤如下：

(1)首先定义了Lyapunov函数为：

条件Lyapunov偏移惩罚函数可以表示为：Δ(Ω(t))＝E[L(Ω(t+1))-L(Ω(t))|Ω(t)]；

Lyapunov偏移惩罚函数可表示为:Δ_v(Ω(t))＝Δ(Ω(t))+VE[E_total(t)|Ω(t)]；

其V是算法中的一个控制参数，E_total(t)表示在时间段t全部移动设备和雾服务器的总的能量消耗；并且基于任何V(t)的可行集合，都能够找到一个Δv(Ω(t))的上界值，其上确界可以表示为：

由于CT是一个常数，D_f,i(t)表示雾服务器执行的移动设备i的服务请求数量，A_i(t)表示移动设备i在时间段t内所产生的计算服务请求量；要得到Δv(Ω(t))的上界值，则可以通过最小化

得出；

(2)在初始的时间段t内，获得Ω(t)；其中Ω(t)＝(Q(t),T(t))是表示移动设备和雾节点的请求缓存区；

(3)通过解决问题P2，确定分配模型的总决策集合V(t)＝[f(t),ρ(t),p_up(t),D_f(t),f_s(t)]；

其中，问题P2：

约束集为s.t：0＜f_i(t)＜f_i,max,0＜p_i,k(t)＜p_i,max,0＜f_s(t)＜f_s,max，

(4)在时间段t+1，获得Ω(t+1)，重复第(2)步和第(3)步，直到获得系统所有时间段的系统决策，即基于Lyapunov优化的雾计算动态卸载方法的最佳总决策

6.根据权利要求5所述的一种基于Lyapunov优化的雾计算动态卸载方法；其特征在于：基于Lyapunov优化的雾计算动态卸载方法的最佳总决策的最优频率、传输功率和雾节点的最优决策分别依据下述三个子问题进行求解：

(1)子问题1：

约束为：0＜f_i(t)＜f_i,max

可以求解出本地处理器的最优CPU周期的频率为：

(2)子问题2：

约束为：

可以求出最优的传输功率为：

(3)子问题3：

约束为：

可以求出请求调度决策为：

Images