基于雾计算的能耗最小化公平计算迁移研究

葛欣炜，段聪颖，陈思光,2

(1.南京邮电大学 江苏省宽带无线通信和物联网重点实验室，江苏 南京 210003；

2.南京邮电大学 江苏省通信与网络技术工程研究中心，江苏 南京 210003)

1 概 述

物联网(Internet of Things，IoT)和人工智能(Artificial Intelligence，AI)是实现智慧城市的两大基础技术[1]。随着智慧城市概念的提出，爆发式增长的智能物联网设备产生了巨大的数据和计算工作量[2]。尤其是，当智能物联网设备在运用深度学习之类的AI算法进行大数据分析时，有可能造成过高的延迟。移动云计算(Mobile Cloud Computing，MCC)通过将计算任务迁移到远程云数据中心来进行计算，以满足智能IoT移动网络中的计算需求[3]，是一种有效的计算模式。但是，由于一般这些远程数据中心距离智能IoT移动设备较远，并且它们与远程云数据中心之间的通信主要依赖于骨干网，因此数据中心很难为网络边缘的智能设备中的延迟敏感型应用提供高质量服务[4]。

移动边缘计算(Mobile Edge Computing，MEC)是解决上述问题的新兴计算模式[5]，通过在智能IoT设备附近部署边缘云服务器来降低计算延迟。雾计算是MEC模式的一个分支，它将计算任务迁移到附近的雾节点(Fog Node，FN)，进一步减少传输延迟并降低智能IoT设备的能耗。这是因为与MCC相比，雾节点更靠近网络边缘，可以提高智能设备和雾节点之间的响应速度[6]。但与MEC不同，雾节点分布相对密集，难以与有利于迁移的智能设备区分开来[7]，且雾节点尺寸更小，资源更少，电池容量更低，这就使得对雾节点的相关资源进行合理分配以及对网络整体性能的优化变得尤为重要。

文献[8-13]通过联合优化网络资源分配与迁移决策，实现延迟与能耗的最小化，改善了整个雾计算网络的性能。文献[13]构建了含能耗与时间延迟约束的雾节点能耗最小化模型，基于对偶分解的加速梯度算法，快速求出最优迁移比，达到最小化雾节点能耗的目的，同时，极大地改善了传统求解方法的收敛速度，降低了计算任务延迟。文献[14]构建了一个系统能效最大化问题，通过联合优化计算频率、发射功率以及迁移时间，采用广义分式规划理论提出一种迭代算法进行求解，从而获得更高的系统计算能效。

文献[15-17]构建了从用户到FN的计算迁移模型，以降低能耗并减少延迟。文献[15]构建了一个混合整数非线性规划问题，提出了一种低复杂度三阶算法，通过平衡终端设备与雾节点的工作负载，实现了计算和传输延迟的最小化。Hu等人在文献[16]中提出了一种基于雾计算的人脸识别机制，可以提高处理效率，有效地识别个人身份，同时减少网络传输的延迟。文献[17]提出了一种针对雾计算网络中的所有FN、数据服务运营商和用户的联合优化机制，以实现最优的分布式资源分配。虽然上述文献所做工作在一定程度上降低了能量消耗并减少了延迟，但其优化结果并不是太理想。尤其是，雾计算网络具有大量的雾节点，其中一些雾节点处于空闲状态，而另一些雾节点几乎一直处于满负荷工作的状态。因此，FN之间的协作在雾计算网络中起着重要的作用。

文献[18]提出了一种众筹算法来整合网络中闲置资源的机制，并对资源提供者进行监督，有效提高了任务完成效率。文献[19]进一步扩展了上述工作，提出了更有效的激励措施来鼓励设备资源共享。文献[20]构建了一种与传统雾模型不同的雾计算模型，提出的基于博弈论的资源共享机制，提高了计算效率，但其并未考虑雾节点本身资源的有限性。文献[21]在多用户边缘计算场景下，考虑了云边资源的协同优化，提出一种基于次模理论的贪心算法，在用户资源受限的情况下仍能够稳定有效的降低系统能耗与时延。文献[22]将协同雾计算与资源分配优化问题结合，提出了一种基于变量拆分的交替方向乘子法的分布式计算迁移优化算法，以实现给定功率下的最优迁移机制。文献[23]构建了一个任务完成时延与能耗加权和的最小化问题，提出了一个基于深度强化学习的迁移算法，以较低的计算成本实现最优迁移策略的快速求解。

从上述分析可以发现，现有文献大都未考虑计算迁移过程中雾节点选择的公平性，而是侧重于最大程度地减少处理延迟与能耗，这可能会给终端节点(Terminal Node，TN)或FN带来极大的计算负担，导致FN过早失效。这是因为，部分雾节点可能具有强大处理能力和充足电源，而其他的则可能是电源有限甚至是电池供电的节点，显然，电池寿命对于这些FN至关重要。考虑到FN的不同处理效率和可持续性，在追求低能耗任务迁移的同时，可以通过在FN之间公平地进行计算任务迁移，从而防止FN由于任务过载而过早失效。

针对上述挑战，面向雾计算网络，该文提出一种能耗最小化公平计算迁移机制，主要贡献如下：

·在雾计算网络场景下，构建了一个最小化所有任务完成总能耗的优化问题，通过对任务迁移比、传输功率和雾节点选择的联合优化，在一定延迟约束条件下，实现总能耗的最小化。

·基于上述优化问题，提出一个任务迁移候选目的节点集生成算法，该算法通过二分法，以较低的复杂度获得各个雾节点在相应延迟约束下的最低能耗及其对应的迁移比和传输功率，生成任务迁移候选目的节点集。进一步，为了在低能耗与目的节点选择的公平性之间取得平衡，基于公平调度指标，提出一个目的节点公平选择算法，以公平、节能的方式实现计算任务分配，防止雾节点过早失效。

·仿真结果表明，该机制可以在低能耗的情况下保证各雾节点之间的公平性，较最大等效处理速率机制，平均雾节点存活率提升了10.9%。

2 系统模型

2.1 网络模型

构建的计算任务迁移模型如图1所示，考虑一个由1个终端节点TN和N个雾节点FN组成的雾簇，该雾簇中的终端节点可以是手机、电脑等智能设备，N个雾节点(路由设备、运营商提供的各种服务器等)随机分布在终端节点周围。该雾簇中的雾节点分为主动雾节点和被动雾节点，主动雾节点由电网供电，对能量消耗不太敏感，而被动雾节点由电池供电，电池寿命有限，对能耗敏感。

图1 计算任务迁移模型

当终端生成计算任务时，可以在终端设备本地进行处理，也可以分为多个子任务，将一部分或全部任务迁移到雾节点，再将结果发送回终端节点。

2.2 计算模型

定义处理1 bit数据所需的CPU周期为c，雾节点i的CPU频率fi和终端节点的CPU频率floc。一旦在TN上生成了具有延迟约束Tmax的计算任务，除了在本地处理任务之外，TN会根据已知的FN信息和任务的约束条件，要求控制器为此任务的迁移服务分配一个选定的目的节点FNi。然后，根据迁移比ai将任务分为两个子任务，分别在本地和FNi上处理。最后，结果从FNi返回TN。

(1)计算延迟。

根据上述迁移过程，任务延迟包括三个部分，即计算任务迁移到雾节点i的传输延迟ttra，雾节点i的计算延迟ti，以及终端节点本地的计算延迟tloc。

子任务迁移到雾节点i的传输延迟可以表示为：

(1)

其中，w是总需要处理的任务大小，Ri是终端节点到雾节点i的数据传输速率，可以用香农公式表示为：

(2)

其中，B是上行链路带宽，Pi是终端到雾节点i的数据传输速率，G是上行链路的无线信道增益，n是上行链路的噪声功率谱密度。

雾节点i的计算延迟可以表示为：

(3)

在终端节点本地计算的延迟可以表示为：

(4)

终端节点只有在接收到所有子任务的处理结果后才能做出下一步决策，因此，总任务延迟定义为所有子任务延迟的最大值，即总延迟表示为：

T=max[(ttra+ti),tloc]

(5)

(2)能量消耗。

根据前面所描述的计算任务迁移到雾节点i的子任务的传输延迟ttra，终端节点的传输能耗表示为：

(6)

雾节点i的能耗可以表示为：

(7)

本地处理的能耗可以表示为：

(8)

其中，κ表示有效电容系数。

一般地，雾节点处理完成后的数据大小远小于源数据，所以结果返回给终端节点的传输能耗可以忽略不计。因此，整个模型处理任务的总能耗为：

E=etra+ei+eloc

(9)

3 优化问题描述

任务延迟和能耗由任务迁移比ai和传输功率Pi决定。在满足延迟约束的条件下，恰当地分配ai和Pi，进而使总能耗最小，从而将优化问题表述为：

(10)

s.t. C1 0≤ai≤1

C2 0≤Pi≤Pmax

C3T≤Tmax

C1是任务迁移比约束，ai=0表示终端生成的任务将全部在本地计算，ai=1表示任务将全部迁移到雾节点i上进行计算。C2是传输功率约束，确保终端设备到雾节点i的传输功率不超过Pmax。C3是延迟约束，确保总任务延迟不超过Tmax。

4 联合任务迁移比、传输功率与目的节点选择的公平计算迁移算法

4.1 任务迁移候选目的节点集生成算法

由于P1是非凸优化问题，所以将其转换成关于终端传输功率Pi的单变量问题。通过二分法，以较低的复杂度获得各个雾节点在相应延迟约束下的最低能耗及其对应的迁移比和传输功率，生成任务迁移候选目的节点集。

首先，在满足T≤Tmax的条件下，总能耗E最小时，迁移总时延满足ttra+ti=Tmax，即：

(11)

则有：

(12)

为了保证优化问题P1可解，必须满足tloc≤Tmax的条件，结合公式(12)，可知当且仅当满足以下两个条件时，总任务时延T可以小于上界Tmax，即：

(13)

(14)

其中，

(15)

由于P1的非凸性，原问题P1转化为：

(16)

其中，

(17)

现在，针对ai和Pi的优化问题P1被转换为针对TN传输功率Pi的能量最小化问题P2。

通过对传输功率Pi求二阶导数可知，总能耗E随传输功率Pi单调递增，则最优的传输功率Pi*将直接由Pi定义域中的最小值给出，那么，在问题P2的取值范围中，若满足如下条件:

(18)

总能耗E是关于传输功率Pi的严格单调递增函数。因此，Pi最优值等于Pi取值范围内的最小值，即:

(19)

对于系统参数不满足上述条件的情况,当Pi∈[0,+∞)时，若满足如下条件：

(20)

(21)

所以,

(22)

算法1：任务迁移候选目的节点集生成算法。

1.输入：任务大小w，雾节点i的CPU频率fi

3.BEGIN

5.for eachi

9.else

10.if 条件 (18) 满足,then

12.else

14. end if

17. end if

18.end for

20.END

4.2 目的节点公平性选择

各个雾节点FN之间的能耗均衡对于雾计算网络的可持续性和稳定性至关重要。在这一部分，基于上述任务迁移候选目的节点集生成算法，提出一种目的节点的公平性选择算法。因此，在延迟约束下，总能耗和计算任务公平分配之间实现了平衡。

首先，为每个雾节点定义公平调度指标，如下:

(23)

历史平均功耗更新如下：

(24)

其中，μ是遗忘因子，0<μ<1。

引入Jain’s公平指数：

(25)

其中,Jain’s公平指数F在1/N到1之间，F越大，表示计算任务迁移机制的公平性越高。

基于算法1得到的候选目的节点集和公平性调度指标，提出如下算法2。

算法2：目的节点公平选择算法。

2.输出：最优目的节点i*

3.BEGIN

5.i*is null；

6.else

7.for eachi∈do

8. 基于公式(23)，计算公平调度指标Mi；

9.end for

10. 选择公平性指数最高的雾节点进行迁移，

11.returni*

12.end if

13.END

5 仿真结果

在本节中，将进行仿真以验证提出的能耗最小化公平迁移算法的性能。在多种网络场景下，对最小化的迁移能耗、迁移服务的可行性以及雾节点选择的公平性进行了验证分析。

在本仿真环境中，设定每个雾节点的带宽B=10 Mb/s，上行链路的噪声功率谱密度n=-100 dBm/Hz，总的雾节点个数为10个，任务总数为20个，终端节点的计算速率floc=2 Mbps。

图2是总能耗与雾节点的任务处理速率关系图。可以看出，随着fi的增加，雾节点的处理速率上升，雾节点处理的能效比本地处理的能效高，通过将计算任务迁移到雾节点进行处理，减少了总能量消耗。随着FNi的CPU频率的进一步提高，该任务将完全迁移到FNi上进行处理，这导致恒定的总能耗。因此，当fi足够大时，总能量消耗趋于收敛。从图中还可以看出，当生成的计算任务量越大，进行计算迁移需要任务处理速率越快。

图2 总能耗与雾节点的任务处理速率关系图

图3是不同雾节点分布半径下三种任务迁移机制的Jain’s公平性指标图。可以看出，随着雾节点分布半径增大，最大等效处理速率机制和完全相等任务迁移机制的公平性指标均大幅下降，远低于该文所提机制的公平性指标。这是因为半径越大雾节点分布越稀疏，选择远程雾节点进行任务迁移的概率越小。该文提出的公平迁移机制在雾节点半径变化时始终保持较高的公平性指数，这是由于它在所有备选雾节点之间采取公平的迁移策略。

图3 雾节点分布半径与Jain’s指数关系图

图4是任务迁移概率与最大传输功率的关系图。可以看出，随着终端发射功率上限的增大，任务迁移的概率从0增加到1，并且增加的幅度近似线性。图5是任务迁移概率与最大容忍延迟的关系图。可以看出，随着延迟上限的增加，计算任务迁移概率从0增加到1。当最大容忍延迟为2 s时，4 MB大小的任务可以全部在本地处理以满足延迟上限，因此该情况下任务迁移概率始终为0。结果表明，更严格的延迟和传输功率约束导致能够为TN提供可行的任务迁移服务的FN减少。

图4 任务迁移概率与最大传输功率关系图

图5 任务迁移概率与最大容忍延迟关系图

图6 雾节点存活率与生成任务数关系图

图6是雾节点存活率与生成任务数的关系图，可以看出，随着生成任务数的不断增加，三种机制的雾节点存活率都呈下降趋势，这是因为随着任务数的不断增加，能量有限的雾节点能量不断消耗殆尽，最终当能量耗尽时雾节点也就随之死亡。而该文的公平迁移机制雾节点的存活率始终更高，比完全相等任务迁移机制和最大等效处理速率机制的平均雾节点存活率分别高31.9%和10.9%。这是因为该文考虑了雾节点之间迁移的公平性，终端节点始终倾向于将任务迁移给剩余能量较高且历史平均能耗较低的雾节点，保证了雾节点之间的公平性，从而保证了雾节点不会过早耗尽能量而失效。

6 结束语

该文提出了一个基于雾计算的能耗最小化公平计算迁移机制，通过联合优化迁移比、传输功率和雾节点选择达到公平且低能耗的计算迁移。提出任务迁移候选目的节点集生成算法, 通过二分法获得雾节点在相应延迟约束下的最低能耗及其对应的迁移比和传输功率；基于公平调度指标，通过目的节点公平选择算法，以低能耗且公平的方式进行计算任务分配，实现低能耗与目的节点选择公平性之间的平衡。仿真结果表明，该机制可以在总能耗较低的情况下保证各个雾节点之间的公平性。