一种云环境下用于实时协同计算的节点选择方法

摘要

本发明公开了一种云环境下用于实时协同计算的节点选择方法，包括：步骤1，搜集可用于实时协同计算的候选节点，同时用户提出资源需求并表示为一个用户节点，采用谱聚类算法将候选节点和用户节点进行聚类，得到一组小集群和离群点；步骤2，在用户所处的小集群中，采用稳定婚姻模型进行节点匹配，选择符合用户需求的多个节点作为资源提供者；步骤3，根据集群内的已出售资源，计算各提供者的牺牲百分比；步骤4，在离群点中，根据各提供者的牺牲百分比，采用稳定婚姻模型进行节点匹配，选择匹配的节点作为提供者的后备转移节点，作为提供者发生意外宕机时的后备保障。最终得到用于实时协同计算的普通节点和后备转移节点。

说明书

技术领域

本发明涉及计算机实时计算领域，特别是一种云环境下用于实时协同计算的节点 选择方法。

背景技术

随着数据量的不断增大，一台个人计算机有时仍很难满足用户的计算需求，同时， 在全球范围内，大量的个人电脑设备在大多数情况下都未得到充分使用，存在大量的 闲置计算资源，这促使了协同云计算的兴起和蓬勃发展。

协同云计算是一种流行的计算模式，同时也是目前世界上主流的分布式计算平台 之一，它能组织来自世界各地的不同组织和个人的闲置计算资源，用于提供服务。近 十年以来，协同云计算已成为最具有成本效益的分布式计算系统之一，参与者能通过 提供闲置资源进行获利。

在协同云计算中，一个关键的问题是服务节点的选择问题，智能的资源选择方式 能促使任务高效有序完成，反之采用性能较差的调度策略会降低平台性能，同时降低 用户体验。近年来，协同云计算中的服务节点选择问题已得到广泛关注，例如对伯克 利开放式网络计算平台(BOINC)节点选择、调度策略问题的研究，BOINC旨在为各 研究者提供汇集全球各地大量个人电脑的强大运算能力。

现随着个人数据量的增加，用户所需的处理能力大幅上升，单一提供者难以满足 需求，通常需要多个提供者进行协作服务，然而，传统节点选择方法在进行协作节点 选择时，很少考虑已选中提供者的偏好，这在一定程度上会影响协作的效率和可靠性。

现有的协同云计算节点选择方法并不能很好满足用户的实际需求，一种个性化的 智能服务节点的选择方法会被更加的需要。其能在考虑用户的需求的同时，同时结合 已参与协作的提供者偏好，例如位置相近程度和信誉评分数据。该协同云计算节点选 择方法能全面利用位置信息对节点进行聚类，缩小匹配域，然后，在聚类后的同一匹 配域中，根据节点间主观、个性化的信誉评价，利用稳定婚姻模型进行节点匹配。该 协同云计算节点选择方法能保障协作云计算服务的高效和可靠运行，即使在提供者发 生不可预期的宕机行为等特殊情况下，仍能保证服务继续稳定执行。

发明内容

发明目的：本发明所要解决的技术问题是针对现有技术的不足，提供一种云环境 下用于实时协同计算的节点选择方法。

为了解决上述技术问题，本发明公开了一种基于谱聚类算法的景点路线推荐方法， 包括以下步骤：

步骤1，搜集可用于实时协同计算的候选节点，同时用户提出资源需求并表示为一 个用户节点，采用谱聚类算法将候选节点和用户节点进行聚类，得到一组小集群和离 群点；

步骤2，在用户所处的小集群中，采用稳定婚姻模型进行节点匹配，选择符合用户 需求的多个节点作为资源提供者(普通节点)；

步骤3，根据提供者的已出售资源，计算各提供者的牺牲百分比；

步骤4，在离群点中，根据各提供者的牺牲百分比，采用稳定婚姻模型进行节点匹 配，选择匹配的节点作为提供者的后备转移节点，作为提供者发生意外宕机时的后备 保障。最终得到用于实时协同计算的普通节点和后备转移节点。

本发明的步骤1中，采用谱聚类算法将候选节点和用户节点进行聚类，包括以下 步骤：

步骤1-1，根据用户所在节点、候选节点间的RTT_ij计算出节点间的权值，构成无 向有权图：

$w_{\mathrm{ij}}=\frac{1}{{\mathrm{RTT}}_{\mathrm{ij}}}$

其中，w_ij表示带权无向图中节点i和节点j两者间的权值，1≤i，j≤n+1，n表 示所有候选节点的总数，RTT_ij表示通信测量得到的节点i和节点j间的RTT(Round-trip time)往返时延值。

步骤1-2，选取高斯核函数作为相似性函数构造所有节点的相似度矩阵S，根据相 似度矩阵S构造度矩阵D和拉普拉斯矩阵L：

$s_{\mathrm{ij}}=\exp (-\frac{w_{\mathrm{ij}}^2}{2{\sigma }^2}),$

$d_i={\Sigma }_{j=1}^n{s}_{\mathrm{ij}},$

L＝D-S

其中，s_ij表示节点i和节点j之间的相似度，1≤i，j≤n+1，n表示所有候选节点 的总数，所有的s_ij构成相似矩阵S，w_ij表示带权无向图中节点i和节点j间的权值，将 所有的w_ij进行从小到大排序，最小值记为最短权值d_min，最大值记为最大权值d_max， σ表示图中最大权值d_max与图中最短权值d_min之差的5％，σ＝(d_max-d_min)*5％，d_i表示节点i的度，所有的d_i构成度矩阵D；

步骤1-3，计算出拉普拉斯矩阵L的前n+1个特征值及其对应的特征向量u_c， 1≤c≤n+1，，根据特征值对其对应特征向量进行升序排序，u_c表示排序后第c个 位置的特征值对应的特征向量，即第c个最小特征值对应的特征向量，所有的特征向 量组成特征向量矩阵U；

步骤1-4，将步骤1-3中得到的特征向量矩阵U进行归一化，得到矩阵H，公式如 下：

$H_{\mathrm{va}}=\frac{u_{\mathrm{va}}}{\sqrt{{\Sigma }_{y=1}^{\delta }{u}_{\mathrm{vy}}^2}},$

其中，H_va表示归一化矩阵中第v行第a列的值，u_va表示特征向量矩阵U中第v 行第a列的值，1≤v≤n+1，1≤a≤δ；u_vy表示特征向量矩阵U第v行第y列的 值，1≤y≤δ，表示特征向量矩阵U中第v行的所有列的值之和；

步骤1-5，设归一化矩阵H的第v行向量为y_v，1≤v≤n+1，对求得的这n个行 向量采用K-均值方法进行聚类，产生K个聚类，5≤K≤15，向量y_v所属的类别即为 节点v所属的小集群，只有一个节点的聚类称为离群点。

步骤2包括以下步骤：

步骤2-1，用户需要运行R个协同计算的任务，表示为R个请求者，用户所在集 群的所有节点表示为Q个资源提供者；

步骤2-2，每个请求者分别对每个资源提供者打分，按照评分进行降序排序，得到 评分矩阵req_b＝{req_b1，req_b2，…，req_bk，…，req_bQ}，req_bk＝T表示请求者b对资源提供 者T的评分排在第k位；

步骤2-3，每个资源提供者分别对每个请求者打分，评分矩阵 sup_z＝{sup_z1，sup_z2，…，sup_zg，…，sup_zR}，sup_zg＝P表示资源提供者z对请求者g的评 分为P；

步骤2-4，选择一个尚未配对的请求者b，在它的评分矩阵req_b矩阵中找出目前尚 未拒绝它的排名最高的资源提供者z，1≤b≤R。；若资源提供者z仍处于空闲状态， 则将该请求者与资源提供者z进行匹配，否则资源提供者z已有配对的请求者α，比较 sup_zb和sup_zα的大小，若前者大于后者，则资源提供者z不再和请求者α配对，而是和 请求者b进行配对；否则标记资源提供者z拒绝了请求者b。

步骤2-5，重复2-4直到所有请求者均配对完毕，得到R个提供者。

本发明中，牺牲百分比表示提供者愿意根据其受欢迎程度进行一定的妥协，付出 其收入的一定牺牲百分比购买后备转移节点，计算提供者牺牲百分比的公式如下：

$X_e=\frac{f_e}{r_e}$

其中，X_e表示提供者e的牺牲百分比，1≤e≤R，R表示提供者的总数，f_e表示 提供者e的已被使用的资源数，r_e表示提供者e的总资源数。

本发明中，考虑到提供者节点的两个特性：第一个是当某个节点出错时，如何保障 未完成的任务迅速定位到可用的节点，使得服务正常进行；第二个是在服务的后期， 各提供者完成任务的进度可能不完全一样，速度快的提供者希望能迅速脱离该任务， 到市场中寻找下一个合作项目，但需要等待最慢的节点完成任务后才能离开，此时提 供者需要将该任务转移到性能并不够优的节点上。故本发明鼓励提供者通过购买一定 的转移节点以支持上述两个特性。

本发明中，后备转移节点是由提供者购买的冗余后备保障节点，故后备转移节点 的定价要低于普通节点的定价。而离群点不和其他节点在一个集群内，所以它不可能 作为普通节点提供服务，其价格低于普通节点，故后备转移节点在离群点内选择。

本发明中，当市场需求多时，提供者会更倾向于进行转移节点，以此带来盈利。 本文定义牺牲百分比表示提供者愿意根据其受欢迎程度进行一定的妥协，付出其收入 的一定牺牲百分比购买转移服务

本发明中，采用提供者的牺牲百分比计算出提供者对离群点的加权评分，公式如 下：

p_eh＝X_eq_eh

其中，p_eh表示提供者e对离群点h的加权评分，1≤h≤β，β表示离群点的总数， q_eh表示提供者e对离群点h的评分，X_e表示提供者e的牺牲百分比。

步骤4包括以下步骤：

步骤4-1，R个提供者对应R个待转移者，将β个离群点表示为β个后备者；

步骤4-2，每个待转移者分别对每个后备者打分，并乘以牺牲百分比，得到加权评 分，按照评分进行降序排序，得到评分矩阵 tran_e＝{p_e1tran_e1，p_e2tran_e2，…，p_ehtran_eh，…，p_eβtran_eβ}，p_ehtran_eh＝Y表示待转移 者e对后备者Y的加权评分排在第h位；

步骤4-3，每个后备者分别对每个待转移者打分，评分矩阵 rec_h＝{rec_h1，rec_h2，…，rec_he，…，rec_hR}，rec_he＝V表示后备者h对待转移者e的评分为 V；

步骤4-4，选择一个尚未配对的待转移者e，在它的评分矩阵tran_e矩阵中找出目前 尚未拒绝它的排名最高的后备者h，1≤e≤R；若后备者h仍处于空闲状态，则将该待 转移者与后备者h进行匹配，否则后备者h已有配对的请求者θ，比较rec_he和rec_hθ的大 小，若前者大于后者，则后备者h不再和待转移者θ配对，而是和待转移者e进行配对； 否则标记后备者h拒绝了待转移者e；

步骤4-5，重复4-4直到所有待转移者均配对完毕，得到R个后备转移节点。

本发明中，采用稳定婚姻模型进行提供者和离群点的匹配，计算出后备转移节点。 最终得到用于实时协同计算的普通节点和后备转移节点。

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

(1)在不影响用户的性能体验基础上，鼓励提供者通过购买一定的转移节点便于自 己在任务后期进行任务转移，并同时能在提供者发生不可预期的宕机时，迅速承接服 务提供保障。

附图说明

下面结合附图和具体实施方式对本发明做更进一步的具体说明，本发明的上述和/ 或其他方面的优点将会变得更加清楚。

图1是本发明的系统工作过程图。

具体实施方式

下面结合附图对本发明作具体说明。应该指出，所描述的实施例仅是为了说明的目 的，而不是对本发明范围的限制。

本发明公开了一种云环境下用于实时协同计算的节点选择方法，该系统的示意图 如图1所示，包括以下步骤：

步骤1，搜集可用于实时协同计算的候选节点，同时用户提出资源需求并表示为一 个用户节点，采用谱聚类算法将候选节点和用户节点进行聚类，得到一组小集群和离 群点；

谱聚类算法的步骤如下：

(1)根据用户所在节点、候选节点间的RTT_ij计算出节点间的权值，构成无向有权图：

$w_{\mathrm{ij}}=\frac{1}{{\mathrm{RTT}}_{\mathrm{ij}}}$

其中，w_ij表示带权无向图中节点i和节点j两者间的权值，1≤i，j≤n+1，n表 示所有候选节点的总数，RTTi_j表示通信测量得到的节点i和节点j间的RTT(Round-trip time)往返时延值。

(2)选取高斯核函数作为相似性函数构造所有节点的相似度矩阵S，根据相似度矩 阵S构造度矩阵D和拉普拉斯矩阵L：

$s_{\mathrm{ij}}=\exp (-\frac{w_{\mathrm{ij}}^2}{2{\sigma }^2}),$

$d_i={\Sigma }_{j=1}^n{s}_{\mathrm{ij}},$

L＝D-S

其中，s_ij表示节点i和节点j之间的相似度，1≤i，j≤n+1，n表示所有候选节点 的总数，所有的s_ij构成相似矩阵S，w_ij表示带权无向图中节点i和节点j间的权值，将 所有的w_ij进行从小到大排序，最小值记为最短权值d_min，最大值记为最大权值d_max， σ表示图中最大权值d_max与图中最短权值d_min之差的5％，σ＝(d_max-d_min)*5％，d_i表示节点i的度，所有的d_i构成度矩阵D；

(3)计算出拉普拉斯矩阵L的前n+1个特征值及其对应的特征向量u_c，1≤c≤n+ 1，，根据特征值对其对应特征向量进行升序排序，u_c表示排序后第c个位置的特征值 对应的特征向量，即第c个最小特征值对应的特征向量，所有的特征向量组成特征向 量矩阵U；

(4)将特征向量矩阵V进行归一化，得到矩阵H，公式如下：

$H_{\mathrm{va}}=\frac{u_{\mathrm{va}}}{\sqrt{{\Sigma }_{y=1}^{\delta }{u}_{\mathrm{vy}}^2}},$

其中，H_va表示归一化矩阵中第v行第a列的值，u_va表示特征向量矩阵U中第v 行第a列的值，1≤v≤n+1，1≤a≤δ；u_vy表示特征向量矩阵U第v行第y列的 值，1≤y≤δ，表示特征向量矩阵U中第v行的所有列的值之和；

(5)设归一化矩阵H的第v行向量为y_v，1≤v≤n+1，对求得的这n个行向量采 用K-均值方法进行聚类，产生K个聚类，5≤K≤15，向量y_v所属的类别即为节点v 所属的小集群，只有一个节点的聚类称为离群点。

步骤2，在用户所处的小集群中，采用稳定婚姻模型进行节点匹配，选择符合用户 需求的多个节点作为资源提供者(普通节点)；

稳定婚姻模型的步骤如下：

(1)用户需要运行R个协同计算的任务，表示为R个请求者，用户所在集群的节点 表示为Q个资源提供者；

(2)每个请求者分别对每个资源提供者打分，按照评分进行降序排序，得到评分矩 阵req_b＝{req_b1，req_b2，…，req_bk，…，req_bQ}，req_bk＝T表示请求者b对资源提供者T的 评分排在第k位；

(3)每个资源提供者分别对每个请求者打分，评分矩阵 sup_z＝{sup_z1，sup_z2，…，sup_zg，…，sup_zR}，sup_zg＝P表示资源提供者z对请求者g的评 分为P；

(4)选择一个尚未配对的请求者b，在它的评分矩阵req_b矩阵中找出目前尚未拒绝 它的排名最高的资源提供者z，1≤b≤R。；若资源提供者z仍处于空闲状态，则将该 请求者与资源提供者z进行匹配，否则资源提供者z已有配对的请求者α，比较sup_zb和 sup_zα的大小，若前者大于后者，则资源提供者z不再和请求者α配对，而是和请求者b 进行配对；否则标记资源提供者z拒绝了请求者b。

(5)重复步骤(4)直到所有请求者均配对完毕，得到R个提供者。

步骤3，根据提供者的已出售资源，计算各提供者的牺牲百分比；

本发明中牺牲百分比表示提供者愿意根据其受欢迎程度进行一定的妥协，付出其 收入的一定牺牲百分比购买后备转移节点，计算提供者牺牲百分比的公式如下：

$X_e=\frac{f_e}{r_e}$

其中，X_e表示提供者e的牺牲百分比，1≤e≤R，R表示提供者的总数，f_e表示 提供者e的已被使用的资源数，r_e表示提供者e的总资源数。

步骤4，在离群点中，根据各提供者的牺牲百分比，采用稳定婚姻模型进行节点匹 配，选择匹配的节点作为提供者的后备转移节点，作为提供者发生意外宕机时的后备 保障。最终得到用于实时协同计算的普通节点和后备转移节点。

步骤4中的稳定婚姻模型包括以下步骤：

(1)R个提供者表示为R个待转移者，β个离群点表示为β个后备者；

(2)每个待转移者分别对每个后备者打分，并乘以牺牲百分比，得到加权评分，按 照评分进行降序排序，得到评分矩阵 tran_e＝{p_e1tran_e1，p_e2tran_e2，…，p_ehtran_eh，…，p_eβtran_eβ}，p_ehtran_eh＝Y表示待转移 者e对后备者Y的加权评分排在第h位；

(3)每个后备者分别对每个待转移者打分，评分矩阵 rec_h＝{rec_h1，rec_h2，…，rec_he，…，rec_hR}，rec_he＝V表示后备者h对待转移者e的评分为 V；

(4)选择一个尚未配对的待转移者e，在它的评分矩阵tran_e矩阵中找出目前尚未拒 绝它的排名最高的后备者h，1≤e≤R；若后备者h仍处于空闲状态，则将该待转移者 与后备者h进行匹配，否则后备者h已有配对的请求者θ，比较rec_he和rec_hθ的大小，若 前者大于后者，则后备者h不再和待转移者θ配对，而是和待转移者e进行配对；否则 标记后备者h拒绝了待转移者e；

(5)重复(4)直到所有待转移者均配对完毕，得到R个后备转移节点。

本发明中采用提供者的牺牲百分比计算出提供者对离群点的加权评分，公式如下：

p_eh＝X_eq_eh

其中，p_eh表示提供者e对离群点h的加权评分， 1≤h≤β，β表示离群点的总数，q_eh表示提供者e对离群点h的评分，X_e表示提供者 e的牺牲百分比。

实施例

本实施例使用了电脑仿真的数据进行实验。

首先，搜集可用于实时协同计算的候选节点can_i，1≤i≤7，同时用户提出资源 需求并表示为一个用户节点user，采用谱聚类算法将候选节点和用户节点进行聚类， 得到小集群group₁、group₂和离群点can₂、can₆。其中group₁包含用户节点user、候 选节点can₃、can₅、can₇；group₂包含候选节点can₁、can₄。；

其次，在用户所处的小集群中group₁，采用稳定婚姻模型进行节点匹配，选择符 合用户需求的多个节点作为资源提供者(普通节点)，选择出的普通节点为can₃、can₅；

再次，根据提供者的已出售资源，计算各提供者的牺牲百分比。

最后，在离群点中，根据各提供者的牺牲百分比，采用稳定婚姻模型进行节点匹 配，选择匹配的节点作为提供者的后备转移节点，作为提供者发生意外宕机时的后备 保障，can₃的后备转移节点是离群点can₆，can₅的后备转移节点是离群点can₂。最终 得到用于实时协同计算的普通节点和后备转移节点。

本发明提供了一种云环境下用于实时协同计算的节点选择方法，具体实现该技术 方案的方法和途径很多，以上所述仅是本发明的优选实施方式，应当指出，对于本技 术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和 润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各组成部分 均可用现有技术加以实现。