CN112379999B - 一种基于联盟博弈的雾节点任务卸载方法 - Google Patents

Abstract

本发明提供了一种基于联盟博弈的雾节点任务卸载方法，所述方法包括以下步骤：S1：收集所有雾节点的基本信息和任务信息；S2：将每个雾节点和该雾节点上的任务合并组成初始化联盟结构；S3：计算雾节点的负载和负载方差；S4：计算卸载单位任务所需要的虚拟货币；S5：遍历雾节点上的所有任务，计算得到初始化联盟结构获得的效益；S6：重复S5，遍历一遍所有雾节点，根据整体效益最大化确定任务归属，构建出稳定联盟结构；S7：确定总卸载策略。根据总卸载策略进行任务卸载，能够使所有雾节点参与计算卸载，并使雾节点间的负载尽可能均衡。

Description

一种基于联盟博弈的雾节点任务卸载方法

技术领域

本发明涉及雾计算技术卸载领域，更具体地，涉及一种基于联盟博弈的雾节点任务卸载方法。

背景技术

随着物联网的高速发展，出现了一大批需要实时渲染的新兴应用(如增强现实和虚拟现实)，这些新兴应用需要计算节点提供低延迟和高吞吐量的高质量服务。与传统的云计算相比，雾计算利用位于用户附近的计算节点完成数据处理，能够有效降低传输时延以及提高吞吐量。

一般而言，用户倾向于将其计算任务卸载到最近的可信雾节点。因此，在雾节点的地理位置不同的情况下，存在某些雾节点的计算负载过重而其他雾节点处于空闲状态的现象，从而导致雾网络中节点负载不均衡；特别在流量高峰期时，部分节点严重过载，处理请求响应变慢，甚至出现宕机的情况。因此，应尽力避免单个节点负载过重的情况，从而提升用户体验。

大多数已有的关于雾计算的工作主要考虑使任务的响应时间和能耗最小化，没有考虑到雾节点之间的负载均衡，以及雾节点对响应时间以及能耗之间的偏好。此外，这些现有工作也没有考虑到雾节点的个体理性约束，即雾节点不愿意共享自身计算资源和不参与其他节点的任务卸载。

2020年9月4日公布的中国专利CN 111625287 A提供了一种基于诱饵效应的雾节点任务卸载方法、系统、介质及设备，该发明考虑了诱饵效应对用户的激励作用，建立了能够影响雾节点行为决策的任务发布环境，并向环境中卸载任务提供了任务吸引力值，通过任务发布和任务吸引力值有指向性地引导雾节点决策；通过设置诱饵任务，提高了目标任务的客观吸引力值；在此基础上引入偏好系数，反映雾节点的真实决策行为，诱饵任务的加入提高了部分雾节点主观偏好值，使更多雾节点参与任务阈值得到满足，提高了雾节点的参与数量。该发明能够有效激励雾节点参与计算卸载，但仍没有解决雾节点间负载不均衡的问题。

发明内容

本发明为克服上述现有技术所述雾节点间负载不均衡的缺陷，提供一种基于联盟博弈的雾节点任务卸载方法。

本发明的技术方案如下：

本发明提供一种基于联盟博弈的雾节点任务卸载方法，所述方法包括以下步骤：

S1：收集所有雾节点的基本信息和任务信息；

S2：将雾节点和该雾节点上的任务合并组成初始化联盟结构F_i；

S3：计算雾节点的负载C_i和负载方差D；

S4：计算卸载单位任务所需要的虚拟货币η；

S5：遍历雾节点i的所有任务，计算得到初始化联盟结构F_i获得的效益v(F_i)；

S6：对所有雾节点遍历一遍S5，根据整体效益最大化确定任务归属，构建出稳定联盟结构F_i ^*,i＝1,2,…,M，获得稳定联盟结构集合F^*＝{F₁ ^*,F₂ ^*,…,F_M ^*}；

S7：根据稳定联盟结构集合F^*确定总卸载策略X。

优选地，所述S1中基本信息和任务信息的收集是利用雾节点控制器通过无线通信完成的。

优选地，所述S1中雾节点的基本信息包括雾节点的CPU频率f、雾节点对响应时延的权重因子α和雾节点的最大容忍能耗e^max；所述任务信息包括任务传输所需数据量d，任务计算量w和任务最大容忍时间t^max。

优选地，所述S2中的具体方法为：

定义S_i为雾节点集合，i＝1,2,…,M；定义r_ia为第i个雾节点的第a个任务，i＝1,2,…,M,a＝1,2,…,N；定义R_i为第i个雾节点的所有任务的集合，r_ia∈R_i，将雾节点i和雾节点i上所有任务的集合R_i进行合并，得到初始化联盟结构F_i，即F_i＝i∪R_i。

优选地，所述S3中的C_i通过下式计算：C_i＝α·t_i+(1-α)·e_i，其中，t_i表示雾节点i响应时延，e_i表示雾节点i响应能耗，α表示响应时延的权重因子，(1-α)表示响应能耗的权重因子；

所有雾节点的负载方差

优选地，所述S4中的虚拟货币η通过下式计算：η＝η₀·D，其中η₀表示单位任务量的基础价格，D表示所有雾节点的负载方差。

优选地，所述S5的具体的方法为：

S5.1：在初始化联盟结构F_i中，雾节点i将R_i中的每个任务卸载至除雾节点i以外的每个雾节点一次；

S5.2：每个任务卸载到每个雾节点得到一个效益u_ia和相对应的卸载关系x_ia；

S5.3：对同一任务卸载至每个雾节点的效益进行比较，得到最大效益值与最大效益值相对应的卸载关系成立，记为1，剩下的卸载关系不成立，记为0；保留成立的卸载关系x_ia，即x_ia＝1时被保留，被保留的卸载关系组成总卸载策略；

S5.4：对雾节点i上的所有任务遍历S5.3；

S5.5：对每个任务的最大效益值求和，得到初始化联盟结构F_i的效益v(F_i)。

优选地，所述S5.2中的效益u_ia由下面公式求出：

其中：α表示响应时延的权重因子，w_a表示任务a的计算量，/>表示雾节点i处理任务a的能耗，/>表示雾节点i处理任务b的能耗，/>表示雾节点i传输任务a的能耗，d_a表示任务a传输数据量，d_b表示任务b传输数据量。

优选地，所述S5.5中的效益由v(F_i)下面公式求出：

优选地，所述S6中构建稳定联盟的具体方法为：

遍历一遍所有雾节点，所有初始化联盟结构的效益和为v(F)，根据以下限定条件，即整体效益最大化，构建稳定联盟结构F_i ^*；

max v(F)

s.t.t≤t^max，e≤e^max

∑x_ia＝1

v(F_i)≥0

其中t表示任务完成时间，t^max表示最大容忍时间，e表示任务完成能耗，e^max表示最大容忍能耗，∑x_ia＝1表示一个任务只能分配到一个执行设备上执行。

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

本发明收集雾节点的基本信息和任务信息，构建初始化联盟结构；通过遍历所有雾节点上的所有任务，计算得到初始化联盟结构的效益并比较出最大效益，根据最大效益选择卸载的联盟，得到稳定联盟结构和卸载关系；整体效益最大化时，稳定联盟结构组成稳定联盟结构集合，并获得总卸载策略。根据总卸载策略，能激励雾节点，使雾节点负载尽可能均衡。

附图说明

图1为实施例1所述的一种基于联盟博弈的雾节点任务卸载方法的流程图。

具体实施方式

附图仅用于示例性说明，不能理解为对本专利的限制；

为了更好说明本实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；

对于本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。

下面结合附图和实施例对本发明的技术方案做进一步的说明。

实施例1

本实施例提供一种基于联盟博弈的雾节点任务卸载方法，如图1所示，所述方法包括以下步骤：

S1：收集所有雾节点的基本信息和任务信息；

S2：将雾节点和该雾节点上的任务合并组成初始化联盟结构F_i；

S3：计算雾节点的负载C_i和负载方差D；

S4：计算卸载单位任务所需要的虚拟货币η；

S5：遍历雾节点i的所有任务，计算得到初始化联盟结构F_i获得的效益v(F_i)；

S6：对所有雾节点无重复的遍历S5，根据整体效益最大化确定任务归属，构建出稳定联盟结构F_i ^*,i＝1,2,…,M，获得稳定联盟结构集合F^*＝{F₁ ^*,F₂ ^*,…,F_M ^*}；

S7：根据稳定联盟结构集合F^*确定总卸载策略X。

所述S1中基本信息和任务信息的收集是利用雾节点控制器通过无线通信完成的。

所述S1中雾节点的基本信息包括雾节点的CPU频率f、雾节点对响应时延的权重因子α和雾节点的最大容忍能耗e^max；所述任务信息包括任务传输所需数据量d，任务计算量w和任务最大容忍时间t^max。

所述S2中的具体方法为：

定义S_i为雾节点集合，i＝1,2,…,M；定义r_ia为第i个雾节点的第a个任务，i＝1,2,…,M,a＝1,2,…,N；定义R_i为第i个雾节点的所有任务的集合，r_ia∈R_i，将雾节点i和雾节点i上所有任务的集合R_i进行合并，得到初始化联盟结构F_i，即F_i＝i∪R_i。

所述S3中的C_i通过下式计算：C_i＝α·t_i+(1-α)·e_i，其中，t_i表示雾节点i响应时延，e_i表示雾节点i响应能耗，α表示响应时延的权重因子，(1-α)表示响应能耗的权重因子；

所有雾节点的负载方差

所述S4中的虚拟货币η通过下式计算：η＝η₀·D，其中η₀表示单位任务量的基础价格，D表示所有雾节点的负载方差。

所述S5的具体的方法为：

S5.1：在初始化联盟结构F_i中，雾节点i将R_i中的每个任务卸载至除雾节点i以外的每个雾节点一次；

S5.2：每个任务卸载到每个雾节点得到一个效益u_ia和相对应的卸载关系x_ia；

S5.3：对同一任务卸载至每个雾节点的效益进行比较，得到最大效益值与最大效益值相对应的卸载关系成立，记为1，剩下的卸载关系不成立，记为0；保留成立的卸载关系x_ia，即x_ia＝1时被保留，被保留的卸载关系组成总卸载策略；

S5.4：对雾节点i上的所有任务遍历S5.3；

S5.5：对每个任务的最大效益值求和，得到初始化联盟结构F_i的效益v(F_i)。

所述S5.2中的效益u_ia由下面公式求出：

其中：α表示响应时延的权重因子，w_a表示任务a的计算量，/>表示雾节点i处理任务a的能耗，/>表示雾节点i处理任务b的能耗，/>表示雾节点i传输任务a的能耗，d_a表示任务a传输数据量，d_b表示任务b传输数据量。

在具体实施过程中，一个雾节点会将自己的任务卸载至其他雾节点，同时也接受其他雾节点卸载来的任务，所以一个雾节点的效益包括将自己的任务卸载的效益和接受其他节点的任务的效益。

所述S5.5中的效益由v(F_i)下面公式求出：

所述S6中构建稳定联盟的具体方法为：

遍历一遍所有雾节点，所有初始化联盟结构的效益和为v(F)，根据以下限定条件，即整体效益最大化，构建稳定联盟结构F_i ^*；

max v(F)

s.t.t≤t^max，e≤e^max

∑x_ia＝1

v(F_i)≥0

其中t表示任务完成时间，t^max表示最大容忍时间，e表示任务完成能耗，e^max表示最大容忍能耗，∑x_ia＝1表示一个任务只能分配到一个执行设备上执行。

相同或相似的标号对应相同或相似的部件；

附图中描述位置关系的用语仅用于示例性说明，不能理解为对本专利的限制；

显然，本发明的上述实施例仅仅是为清楚地说明本发明所作的举例，而并非是对本发明的实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式的变化或变动。这里无需也无法对所有的实施方式予以穷举。凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明权利要求的保护范围之内。

Claims (2)

1.一种基于联盟博弈的雾节点任务卸载方法，其特征在于，所述方法包括以下步骤：

S1：收集所有雾节点的基本信息和任务信息；

所述雾节点的基本信息包括雾节点的CPU频率f、雾节点对响应时延的权重因子α和雾节点的最大容忍能耗e^max；所述的任务信息包括任务传输所需数据量d，任务计算量w和任务最大容忍时间t^max；

S2：将雾节点和该雾节点上的任务合并组成初始化联盟结构F_i，具体方法为：

定义S_i为雾节点集合，i＝1,2,…,M；定义r_ia为第i个雾节点的第a个任务，i＝1,2,…,M,a＝1,2,…,N；定义R_i为第i个雾节点的所有任务的集合，r_ia∈R_i，将雾节点i和雾节点i上所有任务的集合R_i进行合并，得到初始化联盟结构F_i，即F_i＝i∪R_i；

S3：计算雾节点的负载C_i和负载方差D；

C_i通过下式计算：C_i＝α·t_i+(1-α)·e_i，其中，t_i表示雾节点i响应时延，e_i表示雾节点i响应能耗，α表示响应时延的权重因子，(1-α)表示响应能耗的权重因子；

所有雾节点的负载方差

S4：计算卸载单位任务所需要的虚拟货币η，通过下式计算：η＝η₀·D，其中η₀表示单位任务量的基础价格，D表示所有雾节点的负载方差；

S5：遍历雾节点i的所有任务，计算得到初始化联盟结构F_i获得的效益v(F_i)，具体方法为：

S5.1：在初始化联盟结构F_i中，雾节点i将R_i中的每个任务卸载至除雾节点i以外的每个雾节点一次；

S5.2：每个任务卸载到每个雾节点得到一个效益u_ia和相对应的卸载关系x_ia；

效益u_ia由下面公式求出：

其中：α表示响应时延的权重因子，w_a表示任务a的计算量，/>表示雾节点i处理任务a的能耗，/>表示雾节点i处理任务b的能耗，/>表示雾节点i传输任务a的能耗，d_a表示任务a传输数据量，d_b表示任务b传输数据量；

S5.3：对同一任务卸载至每个雾节点的效益进行比较，得到最大效益值与最大效益值相对应的卸载关系成立，记为1，剩下的卸载关系不成立，记为0；保留成立的卸载关系x_ia，即x_ia＝1时被保留，被保留的卸载关系组成总卸载策略；

S5.4：对雾节点i上的所有任务遍历S5.3；

S5.5：对每个任务的最大效益值求和，得到初始化联盟结构F_i的效益v(F_i)，由下面公式求出：

S6：对所有雾节点遍历一遍S5，根据整体效益最大化确定任务归属，构建出稳定联盟结构F_i ^*,i＝1,2,…,M，获得稳定联盟结构集合F^*＝{F₁ ^*,F₂ ^*,…,F_M ^*}，具体方法为：

遍历一遍所有雾节点，所有初始化联盟结构的效益和为v(F)，根据以下限定条件，即整体效益最大化，构建稳定联盟结构F_i ^*；

max v(F)

s.t.t≤t^max，e≤e^max

∑x_ia＝1

v(F_i)≥0

其中t表示任务完成时间，t^max表示最大容忍时间，e表示任务完成能耗，e^max表示最大容忍能耗；

S7：根据稳定联盟结构集合F^*确定总卸载策略X。

2.根据权利要求1所述的一种基于联盟博弈的雾节点任务卸载方法，其特征在于，所述S1中基本信息和任务信息的收集是利用雾节点控制器通过无线通信完成的。