雾计算网络中基于交替方向乘子法的分布式资源分配方法

摘要

本发明公开了一种雾计算网络中基于交替方向乘子法的分布式资源分配方法，该方法主要包括两阶段，雾节点信息收集和分布式资源分配。本发明基于多凸不等式约束交替方向乘子法和凸优化理论，充分利用雾计算网络内雾节点的计算资源，通过雾节点间协作的方式，降低了雾计算网络的开销。相较于集中式资源分配算法，本发明中的分布式资源分配算法利用了雾计算网络的分布式特性，将资源分配问题的求解均匀地分散到雾计算网络中的每个节点上，解决了集中式资源分配问题造成单个节点负载过重的问题。同时基站在资源分配问题的求解中只负责任务卸载向量的收集和广播而不用收集所有雾节点的任务，有效降低了基站的负载和网络的传输负载。

说明书

技术领域

本发明属于雾计算领域，具体涉及一种雾计算网络中基于交替方向乘子法的分布式资源分配方法。

背景技术

随着物联网(Internet of Things,IoT)技术的快速发展，以及智能终端的快速普及，虚拟现实，增强现实，视频通话等技术逐渐走进人们的生活中，给人们带来全新的体验。然而，移动终端(Mobile Terminal,MT)是资源受限，电池容量受限的设备，其计算能力较弱，内存有限，从而制约了它的响应速度。各种各样的互联网应用在丰富人们的日常生活的同时，也在消耗着有限的移动终端的各种资源，从而降低人们对于互联网应用的体验质量(Quality of Experience,QoE)。

云计算(Cloud Computing,CC)是利用云计算服务器的强大处理能力，基于现有计算机网络和虚拟化技术为用户提供弹性的计算和存储服务。移动云计算(Mobile CloudComputing,MCC)作为云计算的进一步延伸，为众多的移动终端提供了强大的计算能力和存储服务。但是，移动云计算的服务器集群与终端的距离很远，任务的传输时延变得不可忽略，严重影响了用户的QoE。移动边缘计算应运而生(Mobile Edge Computing,MEC)，移动边缘计算将服务器部署在基站(Base Station,BS)等距离终端更近的地方，并且也提供了相对强大的计算能力和存储能力，有效降低了任务的传输时延，提高了用户的QoE。此外，MEC技术还有如下一些优点：①蜂窝内的终端数据集中在MEC服务器中，能够进行小规模的数据分析和数据处理。②通过集中式的管理和控制，能够实现智能的负载均衡，从而降低管理成本。但是MEC仍然有一些缺陷，随着物联网的发展，在现有异构网络(HeterogeneousNetwork,HN)环境下，网络中存在诸多拥有计算和存储能力的设备，诸如智能网关(SmartGateway,SG)，接入点(Access Points,AP)等，它们的计算能力和存储能力并没有被MEC和MCC所利用。因此，雾计算网络(Fog Computing Network,FCN)被提出，将这部分智能网关等设备的计算和存储能力利用起来。

雾计算将MCC和MEC扩展到了网络的边缘，从而实现了新型的应用程序和服务。雾计算的定义特征是：①低时延和位置感知；②地理分布广泛；③具有流动性特征；④节点数量众多；⑤异构性。上述特性使雾计算能够成为许多关键的物联网服务和应用程序的运行平台，比如车联网、智能电网、智慧城市和无线传感器网络(Wireless Sensor Networks,WSN)等。同时，雾节点分布更广泛，节点间距离更近，这也为雾节点间的协作提供了可能。通过这种协作的方式进一步降低了雾计算网络处理任务的时延和能量消耗，提升了用户的QoE。雾计算网络分布式的特性决定了用户数据不会像MCC或者MEC那样集中于某一台服务器之上，在这种架构下，如果再采用集中式算法，则会加重网络的负载。

在雾计算网络中，由于雾节点和移动终端在地理分布上不均匀、终端任务负载的不均匀和雾节点计算资源不均匀的特性，就会导致雾计算网络中某些节点收到过多的任务负载，从而导致雾网络中某些节点响应时间过长，QoE下降。同时，随着雾计算网络中雾节点数量的增多，执行集中式资源分配算法所需要的计算资源也越多，让单个雾节点来执行集中式资源分配算法消耗的时间过长。因此，如何平衡雾节点的任务负载，合理分配计算和通信资源，利用雾网络分布式的特性，让雾节点通过节点间协作的方式降低任务处理的时延和能耗，成为亟待解决的问题。

发明内容

为解决上述问题，本发明公开了一种雾计算网络中基于交替方向乘子法的分布式资源分配方法，本方法利用了雾计算网络的分布式特性，将全局资源分配问题分解为多个子问题，雾节点通过求解子问题的方式，实现全局资源分配问题的分布式求解。

为达到上述目的，本发明的技术方案如下：

雾计算网络中基于交替方向乘子法的分布式资源分配方法，通过雾计算网络中雾节点间的协作，实现全局资源分配问题的分布式求解；包括如下步骤：

(1)基站首先收集网络中的所有雾节点的任务负载、计算资源和通信资源，并建立雾计算节点的损失函数然后将信息下发给网络中所有的雾节点，并进入步骤(2)；

(2)在雾节点获取到其他雾节点的信息后，就可以在本地建立起全局的资源分配问题模型，计算雾计算网络代价函数的初值。代价函数主要由两部分组成：

(3)各雾节点对自己收到的任务卸载向量

(4)在所有的雾节点都完成本轮迭代，获得了本轮迭代中最优的任务卸载向量后，基站会对全局资源分配问题中的对偶变量

(5)对偶变量广播完成后，基站会计算前后两次迭代，网络代价函数差值的绝对值和迭代次数，来判断是否结束算法。前后两次优化的代价函数值之差的绝对值，如果大于阈值且迭代次数少于上限，则返回步骤(3)，如果小于阈值，则流程结束。

本发明的有益效果是：

本发明所设计一种基于交替方向乘子法的分布式资源分配方法，针对雾计算场景，基于多凸不等式约束交替方向乘子法和凸优化理论，以最小化雾计算网络代价函数为目标，通过全局资源分配问题分解，雾节点分布式执行的方式实现雾计算节点间协作；相较于传统的集中式资源分配算法，于多凸不等式约束交替方向乘子法的分布式资源分配方法利用了雾计算网络的分布式特性，避免将全局资源分配问题的求解限制在某个雾节点上，占用该节点过多的计算资源；在分布式求解过程中，每个节点只需要通过无线的方式广播自己优化后的任务卸载向量，接收其他节点优化后的任务卸载向量，而不用像集中式资源分配算法中，将卸载任务都传输到单一雾节点上，减轻了网络的传输负载。

本发明的有益效果是：

本发明通过分布式的方式来求解雾计算网络中的全局资源分配问题，相较于集中式资源分配算法，将算法的执行过程分摊给所有的雾节点，避免消耗单一节点过多的计算资源。同时，这种分布式的方式有效利用了雾计算网络的分布式特性，降低了网络的传输开销。

附图说明

图1是本发明提出的基于交替方向乘子法的分布式资源分配方法适用的雾计算网络示意图。

图2是本发明提出的基于交替方向乘子法的分布式资源分配方法的流程图。

具体实施方式

下面结合附图和具体实施方式，进一步阐明本发明，应理解下述具体实施方式仅用于说明本发明而不用于限制本发明的范围。

如图2所示，本发明研究的基于雾计算网络的场景包括宏基站，宏基站服务器，雾节点、移动终端和核心网。雾节点是独立的计算和存储单元，雾节点可与宏基站通过长期演进(Long Term Evolution，LTE)/5G网络进行无线通信，获取基站所下发的指令、路况等信息；宏基站之间是通过可靠的光纤进行连接至核心网；宏基站服务器中保存了该宏蜂窝内的所有雾节点的坐标，计算资源和通信资源信息，宏基站将只负责算法中的数据交换和对偶变量更新，资源分配问题的求解由所有雾节点执行。雾节点用于将中心云功能扩展到高度分布式的移动基站环境中，使数据和应用程序能够在移动用户附近进行处理，向移动用户提供存储和计算的功能，从而减少数据和应用程序的处理时间；雾计算节点之间通过D2D(Device to Device)的方式进行协作，通过任务卸载，计算资源共享的方式来为满足雾计算网络中低时延，高可靠的应用需求提供保证。

在图2中，每个蜂窝中共有I个移动终端，使用集合

本发明针对当前雾计算网络中，对传统的基于凸优化理论的集中式资源分配算法中存在的问题进行改进，提出基于交替方向乘子法的分布式资源分配方法，以实现高可靠，低时延的雾计算节点间协作。该方法通过分布式的方式，对全局资源分配问题进行求解，充分利用网络中所有节点的计算资源。该方法主要分为两部分，雾节点信息收集和分布式资源分配，资源分配问题可以建模为一个线性约束的单目标资源分配问题，将全局资源分配问题拆分为K个子问题，利用所有雾节点的计算资源，避免了单一节点执行集中式资源分配算法时计算负载过重的问题。

本发明设计了一种基于交替方向乘子法的分布式资源分配方法，用于实现雾计算网络中资源分配问题的分布式求解，从而实现雾节点间协作，降低雾计算网络的开销；如图1所示，实际应用中，具体包括如下步骤：

(1)基站首先收集网络中的所有雾节点的任务负载、计算资源和通信资源，并将雾节点的信息下发给网络中所有的雾节点，并进入步骤(2)；

(2)在雾节点获取到其他雾节点的信息后，就可以在本地建立起全局的资源分配问题模型，计算雾计算网络代价函数的初值。代价函数主要由两部分组成：

(3)各雾节点对自己收到的任务卸载向量

(4)在所有的雾节点都完成本轮迭代，获得了本轮迭代中最优的任务卸载向量后，基站会对全局资源分配问题中的对偶变量

(5)对偶变量广播完成后，基站会计算前后两次迭代，网络代价函数差值的绝对值和迭代次数，来判断是否结束算法。前后两次优化的代价函数值之差的绝对值，如果大于阈值且迭代次数少于上限，则返回步骤(3)，如果小于阈值，则流程结束。

其中，在上述步骤(1)中，μ

在步骤(2)中，首先将任务卸载矩阵写为向量的形式：

第j个雾节点的代价函数可以写为：

雾计算网络中的第k个雾节点时延

其中，

s.t.C1:φ

约束条件C1保证所有的卸载任务都为正数；约束条件C2保证雾节点接收的任务都被处理；约束条件C3保证雾节点接收的总任务不能超过自身的处理能力上限。可以观察到该全局资源分配问题的代价函数是由K个子代价函数有关，并且每个子代价函数都只和第j个雾节点收到的任务卸载向量

在步骤(3)中，雾节点j都要对自己收到的任务卸载向量

s.t.C1:φ

在步骤(4)中，所有雾节点都优化并广播任务卸载向量

其中ρ是惩罚因子，惩罚因子越大，对约束条件的满足越好。

上述技术方案所设计一种基于交替方向乘子法的分布式资源分配方法，针对雾计算场景，基于多凸不等式约束交替方向乘子法和凸优化理论，以最小化雾计算网络代价函数为目标，通过对全局资源分配问题进行拆分，雾节点协作的方式，分布式地进行求解；相较于集中式资源分配算法，基于交替方向乘子法的分布式资源分配方法利用了雾计算网络的分布式特性，让所有雾节点都参与到资源分配问题的求解中，避免了集中式资源分配问题造成的单个雾节点计算负载过重的问题。同时，在求解的过程中，雾节点只需要广播任务卸载向量，减少了网络的传输负载。

上面结合附图对本发明的实施方式作了详细说明，但是本发明并不限于上述实施方式，在本领域普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前提下做出各种变化。