基于博弈论的闲置云资源调度方法和装置

摘要

本申请涉及一种基于博弈论的闲置云资源调度方法、系统、计算机设备和存储介质。所述方法包括：获取云环境市场下用户的数据集，用户包括拥有闲置云资源的临时云提供商和没有闲置云资源的纯云用户，数据集包括任务需求数据集和闲置云资源数据集；基于数据集，确定各用户在各预设时间节点的当前云资源调度策略和对应的效益；当各用户在各预设时间节点的当前云资源调度策略满足迭代条件时，寻找当前云资源调度策略对应的效益的纳什均衡点，当当前资源调度策略对应的效益满足纳什均衡存在条件时，根据纳什均衡点对应的资源调度策略，更新当前云资源调度策略。采用本方法能够解决临时云提供商的闲置云资源浪费问题。

说明书

技术领域

本申请涉及云资源调度技术领域，特别是涉及一种基于博弈论的闲置云资源调度方法、装置、计算机设备和存储介质。

背景技术

在云环境市场下，用户从云提供商购买云资源，当用户购买的云资源满足其自身需求后，剩余的部分构成本地资源，拥有本地资源的用户由于对本地资源的开发和利用不足，使得该部分资源保持闲置，造成资源浪费。

发明内容

基于此，有必要针对上述技术问题，提供一种基于博弈论的闲置云资源调度方法、装置、计算机设备和存储介质。

一种基于博弈论的闲置云资源调度方法，所述方法包括：

获取云环境市场下用户的数据集，所述用户包括临时云提供商和纯云用户，所述数据集包括任务需求数据集和闲置云资源数据集，所述任务需求数据集包括各所述临时云提供商和各所述纯云用户分别在各预设时间节点的任务需求量，所述闲置云资源数据集包括各所述临时云提供商在各所述预设时间节点的闲置资源量；

基于所述数据集，确定各所述用户在各所述预设时间节点的当前云资源调度策略和对应的效益；

当各所述用户在各所述预设时间节点的当前云资源调度策略满足迭代条件时，寻找所述当前云资源调度策略对应的效益的纳什均衡点，当所述当前资源调度策略对应的效益满足纳什均衡存在条件时，根据所述纳什均衡点对应的资源调度策略，更新所述当前云资源调度策略。

一种基于博弈论的闲置云资源调度装置，所述装置包括：

数据集获取模块，用于获取云环境市场下用户的数据集，所述用户包括临时云提供商和纯云用户，所述数据集包括任务需求数据集和闲置云资源数据集，所述任务需求数据集包括各所述临时云提供商和各所述纯云用户分别在各预设时间节点的任务需求量，所述闲置云资源数据集包括各所述临时云提供商在各所述预设时间节点的闲置资源量；

数据处理模块，用于基于所述数据集，确定各所述用户在各所述预设时间节点的当前云资源调度策略和对应的效益；

策略优化模块，用于当各所述用户在各所述预设时间节点的当前云资源调度策略满足迭代条件时，寻找所述当前云资源调度策略对应的效益的纳什均衡，当所述当前资源调度策略对应的效益满足纳什均衡存在条件时，根据所述纳什均衡对应的资源调度策略，更新所述当前云资源调度策略。

一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现所述基于博弈论的闲置云资源调度方法的步骤。

一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现基于博弈论的闲置云资源调度方法的步骤。

上述基于博弈论的闲置云资源调度方法、装置、计算机设备和存储介质，将云环境中的用户划分为临时云提供商和纯云用户，其中，临时云提供商为拥有闲置云资源的用户，纯云用户为没有闲置云资源的用户，利用博弈论进行数学建模，在博弈竞争中达到纳什均衡状态，实现临时云提供商在满足自身云任务需求的情况下再对纯云用户出售闲置云资源，从而使得闲置云资源得到充分利用，以解决临时云提供商的闲置云资源浪费问题。

附图说明

图1为一个实施例中基于博弈论的闲置云资源调度方法的流程示意图；

图2为一个实施例中基于博弈论的闲置云资源调度方法的流程示意图；

图3为一个实施例中不同用户在不同迭代次数下的利润；

图4为一个实施例中临时云提供商占100％时在不同时间节点下的资源请求总量；

图5为一个实施例中市场份额为60％的临时云提供商在不同时间节点下的资源请求总量；

图6为一个实施例中不同用户在不同时间节点下的利润；

图7为一个实施例中不同用户在销售闲置云资源前和销售闲置云资源后的利润比较；

图8为一个实施例中不同用户的利润增长率；

图9为一个实施例中基于博弈论的闲置云资源调度装置的结构框图；

图10为一个实施例中计算机设备的内部结构图。

具体实施方式

为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。

在一个实施例中，如图1所示，提供了一种基于博弈论的闲置云资源调度方法，包括以下步骤S102至步骤S106。

S102，获取云环境市场下用户的数据集，所述用户包括临时云提供商和纯云用户，所述数据集包括任务需求数据集和闲置云资源数据集，所述任务需求数据集包括各所述临时云提供商和各所述纯云用户分别在各预设时间节点的任务需求量，所述闲置云资源数据集包括各所述临时云提供商在各所述预设时间节点的闲置资源量。

其中，临时云提供商为拥有闲置云资源的用户，纯云用户为没有闲置云资源的用户，临时云提供商在满足自身云任务需求的情况下可以对纯云用户出售闲置云资源。

S104，基于所述数据集，确定各所述用户在各所述预设时间节点的当前云资源调度策略和对应的效益。

S106，当各所述用户在各所述预设时间节点的当前云资源调度策略满足迭代条件时，寻找所述当前云资源调度策略对应的效益的纳什均衡点，当所述当前资源调度策略对应的效益满足纳什均衡存在条件时，根据所述纳什均衡点对应的资源调度策略，更新所述当前云资源调度策略。

上述基于博弈论的闲置云资源调度方法，将云环境中的用户划分为临时云提供商和纯云用户，其中，临时云提供商为拥有闲置云资源的用户，纯云用户为没有闲置云资源的用户，利用博弈论进行数学建模，在博弈竞争中达到纳什均衡状态，实现临时云提供商在满足自身云任务需求的情况下再对纯云用户出售闲置云资源，从而使得闲置云资源得到充分利用，以解决临时云提供商的闲置云资源浪费问题。

在一个实施例中，将云环境下的用户进行分类，即划分为临时云提供商和纯云用户，临时云提供商(ad hoc cloud provider)的集合用N＝{1,…,N}表示，纯云用户的集合用P＝{1,…,P}表示。将云环境下的时间进行划分成离散的时间序列节点，用H＝{1,…,H}表示。在未来的H个时间节点里，获取每个临时云提供商和纯云用户在时间节点h的任务需求量，用表示，i表示用户序号，相应的，每个临时云提供商和纯云用户在所有时间节点的任务需求量集合用λ_i表示。获取每个临时云提供商和纯云用户在时间节点h的闲置资源量，用表示，i表示用户序号，相应的，每个临时云提供商和纯云用户在所有时间节点的闲置资源量集合用g_i表示，对于纯云用户，其闲置资源量在后续的计算过程中可以恒设为0。

在一个实施例中，利用临时云提供商和纯云用户出于自身优化的心理，生成博弈，将临时云提供商和纯云用户的数据提交到信息交互模块，获得每个临时云提供商和纯云用户在时间节点h的云资源调度策略，用表示，相应的，每个临时云提供商和纯云用户在所有时间节点的云资源调度策略集合用用X_i表示，X_i＝(λ_i,g_i)^T。

在一个实施例中，基于上述以及调度参数，构建临时云提供商和纯云用户的效用函数，根据效用函数确定效用函数值，即效益。其中，调度参数包括收益因子、负载成本参数、闲置成本参数、任务紧急性因子和时间损耗因子。效用函数可以定义如下：

其中，U_i(λ_i,λ_-i)表示用户i的效用函数，表示云资源收益，表示云资源支付费用，表示时间损耗成本，即效益通过云资源收益减去云资源支付费用和时间损耗成本之后的差值确定。λ_-i＝(λ₁,…,λ_i-1,λ_i+1,…,λ_D)，表示除去用户i以外的其他用户的云任务需求量集合，r表示收益因子，ω_i表示任务紧急性因子，δ^h表示时间损耗因子，表示各用户的任务需求满足泊松分布时，按照排队论，在时间节点h完成任务所需的时间平均值。

用户i所支付的云资源费用可以转换为成本计算，包括负载成本和闲置成本两个部分，具体的，费用支付函数可以定义如下：

其中，表示成本函数，第一部分求和式表示负载成本，第二部分求和式表示闲置成本。K^h表示负载成本参数，表示除去用户i以外的其他用户在H个时间节点的任务需求总和，其中，表示所有的纯云用户在时间节点h的任务需求，-i∈N{i}表示在所有的临时云提供商中除去用户i以外的其他临时云提供商。定义σ＝(1,-1)^T，σ_g＝(1,-1)^T，X_i＝(λ_i,g_i)^T。W_i表示闲置云资源维护成本函数，其中a_i表示闲置成本参数。

在一个实施例中，可随机选取一个时间节点，计算每个用户在该时间节点的当前云资源调度策略和对应的效用函数值，该效用函数值即用户在该当前云资源调度策略下的效益。判断该当前云资源调度策略是否满足迭代条件，若满足，则寻找该当前云资源调度策略对应的效益的纳什均衡，若不满足，则退出迭代循环。迭代条件可以是，当各用户在该时间节点的当前云资源调度策略中，至少存在一个用户的当前云资源调度策略与平均策略的差值大于或等于预设的第一误差因子数时，判定该当前云资源调度策略满足迭代条件，所述平均策略为所有用户在该时间节点的当前云资源调度策略的平均策略。

在一个实施例中，寻找当前云资源调度策略对应的效益的纳什均衡之前，首先分析纳什均衡的存在性。分析纳什均衡的存在性的方法具体可以如下：如果一个独立的策略集合在等式是凸的紧的，则博弈G＝<Ω_X,f>在以下等式中有一个非空的并且凸的解集。

其中，Q_i为任务需求联合策略集，Ω_gi为闲置资源联合策略集，f_i为引入的分布式函数，可以用负效用函数表示，f_i(X_i,L_-i)对于任意的可行集L-_i是凸的，很明显是成立的。

因为有那么有

其中，0_d表示一个d维度的0矩阵向量，d表示维度数，上式中的d为2，它是一个半正定的。因为K_h>0(h∈H)的特征值是正的，且矩阵σσ^T是非负的特征值，如果W_i(x)是凸的，即W_i"(x)≥0，汉森矩阵H(f_i)是半正定的，因此，对于的函数f_i(X_i,L_-i)必定是凸的。

采用拉格朗日乘子法，仅计算临时云提供商i(i∈N)，可以构建一个最优目标函数H_i，可以定义如下：

其中，τ表示正则化参数，H_i(X_i,L_-i)中只有变量X_i，为了最小化H_i(X_i,L_-i)，对于足够大的τ，可以使用最佳响应算法以分布式方式计算唯一解。对于约束条件：和有

其中，Λ_i表示用户i的任务需求总和最大值，表示用户i的闲置云资源总和最大值，ξ和ζ表示拉格朗日因子。L_i(X_i,L_-i,ξ,ζ)的偏导数为

以上两个等式可以组成如下方程组

其中，μ表示云计算处理率，τ₁和τ₂表示正则化参数分量，当有

其中，表示所有用户在时间节点h的任务需求总和，表示除用户i以外的其他用户在时间节点h的任务需求总和。以上方程组含有两个未知数和二次求导，得到以下等式

上面的等式都大于0，因此负效用函数的汉森矩阵是半正定的，从而负效用函数的纳什均衡的存在性得以证明。

在一个实施例中，在当前资源调度策略对应的效益满足纳什均衡存在条件时，根据纳什均衡点对应的资源调度策略，更新当前云资源调度策略。纳什均衡存在条件可以是，当各用户在当前资源调度策略对应的效益与平均效益的差值均小于预设的第二误差因子数时，判定各用户在当前资源调度策略对应的效益满足纳什均衡条件，所述平均效益为所有用户在该当前资源调度策略对应的效益的平均效益。

在一个实施例中，若用户i在时间节点h的负效益达到最小，即调度策略时，其中，k表示迭代次数，ε表示误差值，则跳出迭代循环，记录产生的最小负效益数值。

在一个实施例中，计算时间节点h的所有可能的调度策略对应的效益，选择具有最大效益的策略作为待选策略，比较当前策略与待选策略的效益大小，若待选策略的负效益值小于当前策略的负效益值，则更新当前策略为待选策略，并同步更新当前的负效益值，否则不更新。

在一个实施例中，在根据纳什均衡点对应的资源调度策略，更新用户的当前云资源调度策略之后，计算用户的收益，如果用户的效益小于预设保守效益，进行策略置零，即用户不接受该策略。例如，预设保守效益的值可以设为0。

在一个实施例中，如图2所示，提供了一种基于博弈论的闲置云资源调度方法，包括以下步骤S201至步骤S208。

S201，获取云环境市场下用户的数据集，数据集包括各用户在各预设时间节点的任务需求量和闲置云资源量。

S202，对数据集进行预处理，获得各用户在各预设时间节点的当前云资源调度策略和对应的效益。

S203，判断各用户的当前云资源调度策略是否满足迭代条件，若满足，进入步骤S204，若不满足，进入步骤S207。

S204，构建目标函数，寻找纳什均衡点。

S205，判断各用户的当前云资源调度策略对应的效益是否满足纳什均衡存在条件，若满足，进入步骤S206，若不满足，返回至步骤S203。

S206，根据纳什均衡点对应的资源调度策略，更新当前云资源调度策略。

S207，判断用户在更新后的云资源调度策略对应的效益是否小于零，若是，进入步骤S208，若否，结束该流程。

S208，进行策略置零，确定用户不接受该策略。

对于步骤S201至步骤S208的具体限定可以参见上文实施例，在此不再赘述。

上述基于博弈论的闲置云资源调度方法，将用户划分有具有闲置云资源的子集(即临时云提供商)和没有闲置云资源的另一个不相交的子集(即纯云用户)，重点放在云环境中多个竞争的临时云提供商的竞标策略商，基于博弈论，将多个临时云提供商之间的优化问题表达为非合作博弈。临时云提供商的主要目标是通过将闲置云资源出售给其他云用户来降低维护成本，而不仅仅是满足自身任务需求，每个临时云提供商都是一个自私的玩家，总是考虑其他玩家的决定是否合理，以便计算向其他云用户销售云计算资源的最佳策略。本方法采用了迭代近端算法(IPA)，使用用户之间的最小信息交换，保护用户的隐私并融入纳什均衡，通过分析纳什均衡的存在性，以最大化所有博弈参与者的效益(即利润)。

在一个实施例中，选取50个用户，将连续时间划分为24个时间节点，将任务紧急性因子的变化范围设为(1,1/50)，误差因子的值设为0.01，收益因子的值设为51，时间损耗因子的值设为0.12，采用上述实施例方法获得的调度策略进行调度之后，对其调度效果进行测试。

图3显示了不同用户在不同迭代次数下的利润，该利润包括完成自身任务需求的利润和销售闲置云资源的利润之和。图中的临时云提供商1、11、25、36、49、50为50个用户中随机选取的6个用户，从图中可以看出，所有临时云提供商的利润随着迭代次数的变化而变化，最终达到一个相对稳定的状态。原因是迭代到一定次数之后，所有临时云提供商的策略都保持不变，因此，在十几次迭代之后达到纳什均衡解，这一趋势也反映了上述实施例方法中的算法收敛过程。

图4和图5分别显示了临时云提供商占100％和占60％时在不同时间节点下的资源请求总量，该资源请求总量为任务需求量与收到的任务处理量之间的差异。图中对比了应用算法前和应用算法后的资源请求总量，可以看出，应用算法后的调度策略鼓励临时云提供商出售其相对冗余的闲置云资源，并在一定程度上减轻峰值云策略的请求，达到更平衡的结果，此外，在不同时间节点，资源请求总量几乎相同。

图6显示了不同用户在不同时间节点下的利润，图中的临时云提供商1、15、25、29、35、37、43、46、50为50个用户中随机选取的9个用户，从图中可以看出，不同临时云提供商的利润随着时间推移下降到不同程度，这是由任务紧迫性引起的，任务越紧急(即，任务紧急性因子ω越大)，预期任务越快完成，随着时间推移下降的利润更快。

图7显示了不同用户(也可称为组织机构)在销售闲置云资源前和销售闲置云资源后的利润比较。从图中可以看出，每个临时云提供商在销售闲置云资源后比在不销售闲置云资源的情况下获得更多利润，表明如果用户在本地拥有闲置云资源，不仅会造成资源浪费，还会导致成本增加，即总利润减少。

图8显示了不同用户的利润增长率，图中前30个用户为临时云提供商，30到50之间的用户为纯云用户。从图中可以看出，每个用户的利润增长率是不同的，临时云提供商的利润增长率不一定大于纯云用户的利润增长率，表明临时云提供商的主要利润来自任务完成，而不是来自销售闲置云资源。

应该理解的是，虽然图1-2的流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，图1-2中的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。

在一个实施例中，如图9所示，提供了一种基于博弈论的闲置云资源调度装置，包括：数据集获取模块910、数据处理模块920和策略优化模块930。

数据集获取模块910，用于获取云环境市场下用户的数据集，所述用户包括临时云提供商和纯云用户，所述数据集包括任务需求数据集和闲置云资源数据集，所述任务需求数据集包括各所述临时云提供商和各所述纯云用户分别在各预设时间节点的任务需求量，所述闲置云资源数据集包括各所述临时云提供商在各所述预设时间节点的闲置资源量。

数据处理模块920，用于基于所述数据集，确定各所述用户在各所述预设时间节点的当前云资源调度策略和对应的效益。

策略优化模块930，用于当各所述用户在各所述预设时间节点的当前云资源调度策略满足迭代条件时，寻找所述当前云资源调度策略对应的效益的纳什均衡，当所述当前资源调度策略对应的效益满足纳什均衡存在条件时，根据所述纳什均衡对应的资源调度策略，更新所述当前云资源调度策略。

在一个实施例中，数据处理模块920包括策略确定单元和效益确定单元。

策略确定单元，用于基于各所述用户在各预设时间节点的任务需求量和闲置资源量，确定各所述用户在各所述预设时间节点的当前云资源调度策略。

效益确定单元，用于基于各所述用户在各预设时间节点的任务需求量、闲置资源量以及调度参数，得到各所述用户在各所述预设时间节点的效用函数，根据所述效用函数确定对应的效益。

在一个实施例中，所述调度参数包括收益因子、负载成本参数、闲置成本参数、任务紧急性因子和时间损耗因子，效益确定单元用于：基于所述收益因子、以及各所述用户在各预设时间节点的任务需求量，确定各所述用户在各预设时间节点的云资源收益；基于所述负载成本参数、所述闲置成本参数、以及各所述用户在各预设时间节点的任务需求量和闲置资源量，确定各所述用户在各预设时间节点的云资源成本；基于所述任务紧急性因子、所述时间损耗因子、以及除各所述用户自身以外的其它用户在各预设时间节点完成任务的平均时间，确定各所述用户在各预设时间节点的时间损耗成本；基于所述云资源收益、所述云资源成本、以及所述时间损耗成本，得到各所述用户在各所述预设时间节点的效用函数，根据所述效用函数确定对应的效益。

在一个实施例中，策略优化模块930还用于：当各所述用户在一预设时间节点的当前云资源调度策略中，至少存在一个当前云资源调度策略与平均策略的差值大于或等于第一误差因子数时，判定各所述用户在该预设时间节点的当前云资源调度策略满足迭代条件，所述平均策略为所有用户在该预设时间节点的当前云资源调度策略的平均策略。

在一个实施例中，策略优化模块930还用于：当各所述用户在当前资源调度策略对应的效益与平均效益的差值均小于第二误差因子数时，判定各所述用户在当前资源调度策略对应的效益满足纳什均衡条件，所述平均效益为所有用户在该当前资源调度策略对应的效益的平均效益。

在一个实施例中，策略优化模块930还用于：基于所述当前云资源调度策略对应的效用函数，构建目标函数，根据所述目标函数的最小值，确定纳什均衡点。

在一个实施例中，所述装置还包括：策略置零模块，用于当所述用户在更新后的云资源调度策略对应的效益小于预设保守效益，进行策略置零，确定所述用户不接受该更新后的云资源调度策略。

关于基于博弈论的闲置云资源调度装置的具体限定可以参见上文中对于基于博弈论的闲置云资源调度方法的限定，在此不再赘述。上述基于博弈论的闲置云资源调度装置中的各个模块可全部或部分通过软件、硬件及其组合来实现。上述各模块可以硬件形式内嵌于或独立于计算机设备中的处理器中，也可以以软件形式存储于计算机设备中的存储器中，以便于处理器调用执行以上各个模块对应的操作。

在一个实施例中，提供了一种计算机设备，该计算机设备可以是服务器，其内部结构图可以如图10所示。该计算机设备包括通过系统总线连接的处理器、存储器和网络接口。其中，该计算机设备的处理器用于提供计算和控制能力。该计算机设备的存储器包括非易失性存储介质、内存储器。该非易失性存储介质存储有操作系统和计算机程序。该内存储器为非易失性存储介质中的操作系统和计算机程序的运行提供环境。该计算机设备的网络接口用于与外部的终端通过网络连接通信。该计算机程序被处理器执行时以实现一种基于博弈论的闲置云资源调度方法。

本领域技术人员可以理解，图10中示出的结构，仅仅是与本申请方案相关的部分结构的框图，并不构成对本申请方案所应用于其上的计算机设备的限定，具体的计算机设备可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。

在一个实施例中，提供了一种计算机设备，包括存储器和处理器，存储器中存储有计算机程序，该处理器执行计算机程序时实现上述各个方法实施例中的步骤。

在一个实施例中，提供了一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现上述各个方法实施例中的步骤。

需要理解的是，上述实施例中的术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器可包括随机存取存储器(RAM)或者外部高速缓冲存储器。作为说明而非局限，RAM以多种形式可得，诸如静态RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双数据率SDRAM(DDRSDRAM)、增强型SDRAM(ESDRAM)、同步链路(Synchlink)DRAM(SLDRAM)、存储器总线(Rambus)直接RAM(RDRAM)、直接存储器总线动态RAM(DRDRAM)、以及存储器总线动态RAM(RDRAM)等。

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

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