MEC环境下多维属性感知的边缘服务二次聚类方法及系统

技术领域

本发明属于边缘服务领域，尤其涉及一种MEC环境下多维属性感知的边缘服务二次聚类方法及系统。

背景技术

本部分的陈述仅仅是提供了与本发明相关的背景技术信息，不必然构成在先技术。

近年来，随着移动边缘计算(Mobile Edge Computing,MEC)技术的快速发展与成熟，网络上出现了大规模种类繁多、位置各异、服务质量(QoS)不同的边缘服务。边缘服务聚类成为MEC环境下提高服务发现、服务选择以及服务管理效率的关键技术之一。然而，已有的研究工作大都集中于Web服务与云服务聚类，而MEC环境下的边缘服务具有更多的属性，使得已有的服务聚类方法不能直接应用于MEC环境下的边缘服务聚类。

在MEC环境下，边缘服务通常部署在多个不同的边缘服务器上，使得边缘服务具有明显的位置特性以及与所在服务器的相关性。而已有的服务聚类方法，没有充分考虑这些特性，无法直接应用于MEC环境下边缘服务的聚类。

发明内容

为了解决上述背景技术中存在的技术问题，本发明提供一种MEC环境下多维属性感知的边缘服务二次聚类方法及系统，其首先提取并建立了MEC环境下边缘服务聚类指标模型，将边缘服务的地理位置与其所在服务器的质量作为一级聚类指标，将服务质量(QoS)与信誉度作为二级聚类指标；之后，提出了一种基于密度的最小生成树启发式分段聚类算法(Density-based MST Heuristic Segmented Clustering，DMSC)，并基于DMSC算法依据一级指标对边缘服务进行一次聚类，得到地理位置相近、服务器质量相似的服务类簇；最后，将密度峰值算法中γ值引入到层次聚类中(γ表示局部密度与高局部密度点距离的乘积)，构建了基于密度峰值的层次聚类算法(Hierarchical Clustering based on DensityPeak，HCDP)，并利用该算法对边缘服务进行二次聚类，得到非功能性属性具有较高相似性的边缘服务簇。

为了实现上述目的，本发明采用如下技术方案：

本发明的第一个方面提供一种MEC环境下多维属性感知的边缘服务二次聚类方法。

MEC环境下多维属性感知的边缘服务二次聚类方法，包括：

将边缘服务所在服务器的地理位置与边缘服务器的硬件配置作为一级聚类指标；

将服务质量与信誉度作为二级聚类指标；

采用基于密度的最小生成树启发式分段聚类算法，依据一级聚类指标，对边缘服务进行一级聚类，得到地理位置相近、服务器质量相似的服务类簇；

采用基于密度峰值的层次聚类算法，依据二级聚类指标，对所述地理位置相近、服务器质量相似的服务类簇进行二级聚类，得到边缘服务聚类结果。

进一步地，所述边缘服务器的硬件配置包括：CPU性能、内存、硬盘和数据传输。

进一步地，所述服务质量包括：服务费用、服务执行时间、服务可用性和服务可靠性；

所述服务费用表示用户使用服务时所需要支付的费用；所述服务执行时间表示从用户发出服务请求到服务结束所用的时间；所述服务可用性表示服务正常运行时间占总时间的百分比；所述服务可靠性表示在用户输入错误、网络过载或被有意攻击情况下，服务正常运行的能力。

进一步地，所述基于密度的最小生成树启发式分段聚类算法通过改进结合最大最小距离和加权密度的K-means算法得到，改进点包括：将平均局部密度设为阈值，增加初始类簇中心的个数，将所含聚类对象少于设定值的类簇判定为离群点，排除离群点；针对同一半径内聚类对象数量相同、紧密程度不同的情况，设计局部密度函数，将服务间相似度作为计算服务局部密度的一部分。

进一步地，所述基于密度峰值的层次聚类算法通过将密度峰值算法中γ值引入到层次聚类算法中，依据各边缘服务的γ值有序地对边缘服务进行层次聚类得到。

进一步地，所述采用基于密度的最小生成树启发式分段聚类算法，依据一级聚类指标，对边缘服务进行一级聚类，得到地理位置相近、服务器质量相似的服务类簇的过程包括：

获取边缘服务集合，将服务平均相似度作为截断距离，基于聚类结果的簇间相似度与簇内相似度计算每个服务的局部密度，基于每个服务的局部密度得到边缘服务集合的平均局部密度；

将平均局部密度设置为阈值，将大于阈值的服务加入初始聚类中心集合中，并根据最大最小距离准则将剩余服务进行分配；

计算各类簇的簇内相似度与簇间相似度，并利用克鲁斯卡尔算法算法选取权值W最大的边生成最小生成树MST，并将其作为类簇数为1的聚类结果；

对MST中W最小的边进行分段操作，得到两个新的类簇，将所含服务小于设定值的类簇判定为离群簇，并按最大最小距离准则对其类簇内服务进行分配，将结果作为新的聚类结果；

循环执行分段操作，直至W大于设定的阈值时停止分段操作；最后，通过比较簇间相似度与簇内相似度的比值，将比值最小的聚类结果作为一级服务聚类的结果。

进一步地，所述采用基于密度峰值的层次聚类算法，依据二级聚类指标，对所述地理位置相近、服务器质量相似的服务类簇中的一个类簇进行二级聚类，得到边缘服务类簇的过程包括：

根据输入的所述地理位置相近、服务器质量相似的服务类簇中各服务的局部密度与服务距离计算各服务的γ值；其中，服务距离指的是比服务s

依次选取类簇所述地理位置相近、服务器质量相似的服务类簇中γ值最大的服务进行分簇操作，直到OldGroup中没有新的服务可分配给NewGroup停止循环，得到边缘服务聚类结果。

本发明的第二个方面提供一种MEC环境下多维属性感知的边缘服务二次聚类系统。

MEC环境下多维属性感知的边缘服务二次聚类系统，包括：

一级聚类指标确定模块，其被配置为：将边缘服务所在服务器的地理位置与边缘服务器的硬件配置作为一级聚类指标；

二级聚类指标确定模块，其被配置为：将服务质量与信誉度作为二级聚类指标；

一级聚类模块，其被配置为：采用基于密度的最小生成树启发式分段聚类算法，依据一级聚类指标，对边缘服务进行一级聚类，得到地理位置相近、服务器质量相似的服务类簇；

二级聚类模块，其被配置为：采用基于密度峰值的层次聚类算法，依据二级聚类指标，对所述地理位置相近、服务器质量相似的服务类簇进行二级聚类，得到边缘服务聚类结果。

本发明的第三个方面提供一种计算机可读存储介质。

一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如上述第一个方面所述的MEC环境下多维属性感知的边缘服务二次聚类方法中的步骤。

本发明的第四个方面提供一种计算机设备。

一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如上述第一个方面所述的MEC环境下多维属性感知的边缘服务二次聚类方法中的步骤。

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

本发明为了提高服务聚类的效果，增强服务聚类的精度，深入考虑了MEC环境边缘服务具有的特性，提出并建立了MEC环境下服务聚类指标模型。根据MEC环境下边缘服务所具有的特性，将边缘服务所在服务器的地理位置与服务器配置作为一级聚类指标；将边缘服务的服务质量(QoS)与信誉度作二级聚类指标；该指标模型有助于提高边缘服务聚类的精度。

本发明为了提高MEC环境下边缘服务聚类的效率，提出了一种基于密度的最小生成树启发式分段聚类算法，并应用该算法完成边缘服务的一次聚类；引入局部密度并作为初始类簇中心选取的依据，能够快速得到初始聚类结果，加速算法的收敛速率；同时，根据最小生成树(MST)所具有的稀疏性，选用MST来存储初始聚类结果并依据簇间相似度进行分段操作，产生新的聚类结果，可以有效地降低算法的时间复杂度。

本发明为了进一步增强服务聚类的精度，将密度峰值算法同层次聚类算法相结合，依据边缘服务的γ值有序地对边缘服务进行层次聚类，在一定程度上解决了层次聚类不可逆所导致的聚类效果不理想的问题。

本发明附加方面的优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

构成本发明的一部分的说明书附图用来提供对本发明的进一步理解，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。

图1是本发明示出的K-means算法聚类效果图；

图2是本发明示出的KWDM算法聚类效果；

图3是本发明示出的ESSC算法聚类效果图；

图4是本发明示出的人工数据集-迭代次数与准确率关系图；

图5是本发明示出的Iris-迭代次数(切割次数)与准确率关系图；

图6是本发明示出的Wine-迭代次数(切割次数)与准确率关系图；

图7是本发明示出的Seed-迭代次数(切割次数)与准确率关系图；

图8是本发明示出的MEC环境下多维属性感知的边缘服务二次聚类方法的流程图。

具体实施方式

下面结合附图与实施例对本发明作进一步说明。

应该指出，以下详细说明都是例示性的，旨在对本发明提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本发明所属技术领域的普通技术人员通常理解的相同含义。

需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本发明的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。

需要注意的是，附图中的流程图和框图示出了根据本公开的各种实施例的方法和系统的可能实现的体系架构、功能和操作。应当注意，流程图或框图中的每个方框可以代表一个模块、程序段、或代码的一部分，所述模块、程序段、或代码的一部分可以包括一个或多个用于实现各个实施例中所规定的逻辑功能的可执行指令。也应当注意，在有些作为备选的实现中，方框中所标注的功能也可以按照不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并行地执行，或者它们有时也可以按照相反的顺序执行，这取决于所涉及的功能。同样应当注意的是，流程图和/或框图中的每个方框、以及流程图和/或框图中的方框的组合，可以使用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以使用专用硬件与计算机指令的组合来实现。

实施例一

如图1所示，本实施例提供了一种MEC环境下多维属性感知的边缘服务二次聚类方法，包括以下步骤：

将边缘服务所在服务器的地理位置与边缘服务器的硬件配置作为一级聚类指标；

将服务质量与信誉度作为二级聚类指标；

采用基于密度的最小生成树启发式分段聚类算法，依据一级聚类指标，对边缘服务进行一级聚类，得到地理位置相近、服务器质量相似的服务类簇；

采用基于密度峰值的层次聚类算法，依据二级聚类指标，对所述地理位置相近、服务器质量相似的服务类簇进行二级聚类，得到边缘服务聚类结果。

本实施例的具体技术方案，可见如下具体内容：

1.背景介绍

在MEC环境下，边缘服务通常部署在多个不同的边缘服务器上，使得边缘服务具有明显的位置特性以及与所在服务器的相关性。而已有的服务聚类方法，没有充分考虑这些特性，无法直接应用于MEC环境下边缘服务的聚类。

针对上述问题，本实施例提出了一种MEC环境下多维属性感知的边缘服务二次聚类方法。该方法首先提取并建立了MEC环境下边缘服务聚类指标模型，将边缘服务所在服务器的地理位置与硬件配置作为一级聚类指标；将服务质量(QoS)、信誉度等其他属性作为二级聚类指标，并建立二级聚类指标模型；然后，提出了一种基于密度的最小生成树启发式分段聚类算法(Density-based MST Heuristic Segmented Clustering,DMSC)，基于DMSC算法依据一级指标对边缘服务进行一次聚类，得到地理位置相近、服务器质量相似的服务类簇。最后，将密度峰值算法同层次聚类算法相结合，构建了基于密度峰值的层次聚类算法(Hierarchical Clustering based on Density Peak，HCDP)，基于HCDP算法依据边缘服务的二次聚类指标对其进行二次聚类，最终形成相似度更强的边缘服务类簇；通过模拟数据验证了本实施例所提出方法的有效性。本实施例的主要贡献如下：

i)为了提高服务聚类的效果，增强服务聚类的精度，深入考虑了MEC环境边缘服务具有的特性，提出并建立了MEC环境下服务聚类指标模型。根据MEC环境下边缘服务所具有的特性，将边缘服务所在服务器的地理位置与服务器配置作为一级聚类指标；将边缘服务的服务质量(QoS)与信誉度作二级聚类指标；该指标模型有助于提高边缘服务聚类的精度。

ii)为了提高MEC环境下边缘服务聚类的效率，本实施例提出了一种基于密度的最小生成树启发式分段聚类算法，并应用该算法完成边缘服务的一次聚类；引入局部密度并作为初始类簇中心选取的依据，能够快速得到初始聚类结果，加速算法的收敛速率；同时，根据最小生成树(MST)所具有的稀疏性，选用MST来存储初始聚类结果并依据簇间相似度进行分段操作，产生新的聚类结果，可以有效地降低算法的时间复杂度。

iii)为了进一步增强服务聚类的精度，将密度峰值算法同层次聚类算法相结合，依据边缘服务的γ值有序地对边缘服务进行层次聚类，在一定程度上解决了层次聚类不可逆所导致的聚类效果不理想的问题。

本实施例的组织结构如下：第2节介绍服务聚类的相关工作；第3节对问题进行描述并详细介绍聚类指标模型的建立；第4节对服务聚类前数据预处理工作进行介绍；第5节详细给出了多维属性感知的边缘服务二次聚类方法；第6节通过与现有方法进行对比实验，验证了本实施例所提出方法的有效性与可行性；最后，进行总结，并对下一步的研究工作进行了展望。

2相关工作

服务聚类对于提高服务发现、服务选择以及服务管理等效率具有重要的支撑作用，服务聚类技术依据服务的不同属性将海量的服务划分为不同的服务类簇，使得同一类簇中的服务具有较高的相似性，而不同类簇中的服务具有较大的差异性。目前，国内外学者针对服务聚类这一问题开展了大量的研究工作，并取得了丰富的研究成果，已有的研究工作可以分为两类：Web服务聚类方法研究以及其他服务资源聚类方法研究。

2.1Web服务聚类方法研究

在MEC环境下，由于服务部署在不同的边缘服务器中，使得边缘服务除了具有服务一般属性之外，还具有位置与所在服务器配置等特性，使得边缘服务具有多维属性。由于MEC环境下服务所具有的特性，使得已有的Web服务聚类方法不能直接应用于MEC环境下的服务聚类。目前，MEC环境下关于服务聚类的研究工作比较少。任丽芳和王文剑提出了一种移动边缘计算环境中服务QoS的预测方法，其在MEC环境下通过服务聚类实现了对QoS的预测，但在聚类指标定义上，没有考虑服务所在服务器的配置以及地理位置属性对聚类结果的影响，使得聚类效果有待提高。

3MEC环境下边缘服务聚类问题描述

在MEC环境下，海量的边缘服务部署在众多位于不同地理区域的边缘服务器上；同时，边缘服务自身又具有服务质量(QoS)、信誉度等其他非功能属性。杂乱无章的边缘服务信息对于服务发现、服务选择与服务管理带来巨大的挑战。MEC环境下的边缘服务聚类能够为服务发现、服务替换以及服务管理效率等服务应用领域问题提供重要的技术支持。在MEC环境下，设有n个边缘服务器ES＝{es

3.2边缘服务聚类指标体系建立

MEC环境下的边缘服务聚类问题，本质上是依据边缘服务重要的非功能性属性，将功能相同或相似的服务集划分为不同的服务类簇。因此，进行边缘服务聚类的第一步为提取边缘服务重要的非功能性属性指标。在MEC环境下，边缘服务器地理位置与其配置对于边缘服务的性能具有较大影响。因此，在MEC环境下，边缘服务器的地理位置与其配置应成为该环境下服务聚类的首要依据。本实施例根据MEC环境下边缘服务所具备的特性及其具备的一般服务非功能属性度量指标，提出了两级服务聚类指标模型，分别作为两次服务聚类的依据。鉴于地理位置与服务器配置是影响服务性能最为重要的因素，本实施例将边缘服务所在边缘服务器的地理位置与边缘服务器的配置(CPU性能、内存、硬盘、数据传输)作为一次聚类指标；其次，将服务质量(QoS)(成本、响应时间、可用性、可靠性)和信誉度作为边缘服务的二次聚类指标。依据两级指标模型对服务进行二次聚类，体现出MEC环境下服务聚类具有位置感知、环境感知的特性，同时也提高了服务聚类的精度。

设边缘服务的非功能性属性集为SNF＝{R

表1 MEC环境下服务聚类一级指标

在MEC环境下，服务质量(QoS)是直观体现服务非功能性的评价指标，本文将服务费用、反应时间、可用性以及可靠性作为QoS的度量因素，定义服务的QoS模型为R

表2 MEC环境下服务聚类二级指标

4边缘服务聚类指标数据预处理及相似度计算公式

由于边缘服务具有多种非功能性能聚类指标，这些聚类指标的取值类型和取值范围不同，当各聚类指标间的量纲和量级差异很大时，如果直接使用原始指标值进行聚类，则会突出数值水平较高的指标在聚类结果中的作用；相对地，数值水平较低的指标的作用则会被削弱。因此，为了提高聚类的可靠性，实现高效的边缘服务聚类，本实施例对原始指标数据进行归一化处理，使得各指标的取值类型和范围具有可比性。进而根据归一化后的服务属性值计算各服务间相似度，从而提高边缘服务聚类的准确性。

4.1指标取值归一化处理

MEC环境下的边缘服务各聚类指标的取值类型通常为实数型与区间型，下面分别给出实数型数据和区间型数据的归一化处理方式。

(1)实数型数据的归一化处理

目前，最常用的数据归一化处理方法是min-max标准化法，它通过对原始数据进行线性变换将数据统一映射到[0,1]区间上。对于正向型指标，比如CPU性能、内存大小等指标，指标值越大表示该指标越好，其归一化转换函数如式(1)所示；

对于逆向指标，比如费用等，指标取值越小表示该指标越好，其归一化公式如式(2)所示。

(2)区间型数据的归一化处理

服务聚类指标中，有一些指标的取值为一定的数据区间，比如可靠性、信誉度等指标。对于这种数据类型，本实施例首先采用三角模糊数对该类属性进行描述，如公式(3)所示。

其中，

其中，

4.2指标相似度计算公式

通过计算服务聚类指标间的相似度，进而计算服务之间的相似度，从而可全面有效刻画服务间的差异，提高聚类的精准度。在本实施例提出的服务聚类多级指标模型中，主要包括实数型数据以及区间型数据，下面分别给出这两种数据类型的相似度计算公式。

(1)实数型数据的相似度计算公式

设x′

sim(r

设(x,y)二元组表示的服务地理位置属性，相似度可根据欧几里得距离公式进行计算，以此来衡量服务间地理位置属性的相似度，计算公式如(7)式所示。

其中，x′

(2)区间型数据的相似度计算公式

对于利用三角模糊数来表示的聚类指标，该类区间型数据的相似度计算公式如(8)式所示。

其中，

簇内相似度表示类簇C

其中，在公式(9)中，C

5MEC环境下边缘服务二次聚类方法

在MEC环境下，对服务池中功能相同或相似的边缘服务进行聚类，可准确地得到非功能属性相似的服务类簇。鉴于MEC环境下，边缘服务具有多种不同的非功能性属性，不同的属性对于边缘服务聚类的影响不同，为了提高边缘服务聚类的效率与效果，本实施例提出一种MEC环境下多维属性感知的服务二次聚类的方法。该方法首先根据服务所在服务器的地理位置与服务器的配置属性进行一次聚类；在一次聚类基础上，根据服务的QoS与信誉度再进行二次聚类。该方法可满足MEC环境下服务对地理位置相近与服务器质量相似的需求，并能有效地对MEC环境下的服务进行精确聚类。

5.1基于DMSC算法的边缘服务一次聚类

K-Means算法具有简单、快速以及适合挖掘大规模数据集等优点，近年来在服务聚类方面得到了广泛的应用并取得了较好的效果。此外，结合最大最小距离和加权密度的K-means算法(KWDM)为一种改进的K-Means聚类算法具有很好的聚类性能，其基本思想是利用各样本点局部密度值排除离群点，从而选出聚类中心点集；通过最大最小距离准则在聚类中心点集中选取聚类中心；最后利用簇内样本距离与簇间样本距离的比值来确定聚类中心K的值。虽然KWDM算法克服了K-means算法对聚类中心选择的随机性，避免了聚类结果陷入局部最优的问题，但该算法仍有一些局限性：

(1)KWDM算法规定聚类中心个数K只能在

(2)在局部密度定义上，未考虑数量相同但紧密程度不同的情况，导致初始聚类中心选取精度不足，对聚类结果的准确性产生不好的影响。

针对上述不足，本实施例对KWDM算法进行了以下改进工作：

(1)针对KWDM算法在聚类对象分布较为离散时聚类结果不准确这一不足，本实施例将平均局部密度设为阈值，增加了初始类簇中心的个数，将所含聚类对象较少的类簇判定为离群点，以此提高聚类的精度。

(2)针对同一半径内聚类对象数量相同、紧密程度不同的情况，设计了新的局部密度函数，将服务间相似度sim(s

本实施例以最小生成树的形式来存储初始聚类结果并处理类簇间的聚合问题，不仅可以保留初始聚类的结果，而且最小生成树是稀疏图，降低了服务聚类的复杂度。基于上述的改进工作，提出了基于密度的最小生成树启发式分段聚类算法(Density-based MSTHeuristic Segmented Clustering，DMSC)，并应用DMSC对边缘服务进行一次聚类，基于DMSC的边缘服务一次聚类过程如算法1所示。

算法1基于密度的最小生成树启发式分段的一次服务聚类算法

输入：边缘服务集合S

输出：边缘服务一次聚类结果：π＝{C

Begin:

对于算法1，在步骤1-4中，首先将服务平均相似度

5.2基于HCDP算法的二次服务聚类

由于边缘服务具有多种非功能属性，通过二次聚类可以进一步提高聚类结果的准确性。层级聚类算法在处理小规模数据集时具有简单、快速等优势，因此，本实施例采用层次聚类算法对边缘服务进行二次聚类。密度峰值算法(DPC)以能够快速发现具有成为聚类中心潜力的样本点而闻名，为了提高层次聚类算法的收敛速度，本实施例将密度峰值算法中γ值引入到层次聚类中，依据各边缘服务的γ值有序地对边缘服务进行层次聚类。边缘服务的γ值越大表示该服务成为聚类中心的潜力越大，通过依次选取γ值最大的服务进行层次聚类，在一定程度上解决了层次聚类不可逆所导致的聚类效果不理想的问题，同时也加速了聚类收敛的速率。因此，本实施例提出了一种基于密度峰值的层次聚类算法(HCDP)，并利用该算法对服务进行二次聚类，得到最终的聚类结果。基于HCDP的边缘服务二次聚类过程如算法2所示。

算法2基于HCDP的二次服务聚类算法

输入：一次聚类结果π

输出：聚类结果：

Begin:

算法2将密度峰值算法中初始聚类中心选取的方法加入层次聚类算法中，避免了层次聚类难以收敛的问题。步骤1-4根据输入的C

6实验

由于MEC环境的特殊性以及服务属性的多元性，在现有开放实验数据库中不存在可用于本实施例算法验证的数据集。因此，本实施例采用随机生成的数值型人工数据集来验证本实施例所提算法的正确性。同时，采用UCI数据集与K-means等算法进行性能对比，验证本文算法的优越性。实验环境为个人电脑，具体配置为：操作系统为Win10系统，CPU

6.1实验数据的生成

在移动边缘计算环境下，大城市周边边缘服务分布较多，小城市周边边缘服务分布较少。为了有效地验证聚类的效果，以下述4条准则为基础，随机生成2000条数值型离散数据作为数据集散布在解空间中，其中每条数据包含地理位置、服务器质量、QoS与信誉度属性。

1)以5座城市为中心，以中心向周围扩散的形式生成地理位置属性；

2)同一城市可能有多个质量不一的边缘服务器，边缘服务器质量数据生成参考亚马逊(Amazon)云服务器质量属性；

3)具有相同功能的边缘服务QoS差值不大，在一定范围内随机生成QoS中费用、反应时间等属性的数值，数值类型为实数型数据与区间型数据；

4)信誉度为区间型数据，用三角模糊数来表示。其中，每位由[1,10]随机生成，值越大表示该边缘服务信誉度越高，更受用户的喜欢。

表3给出了随机生成的人工数据集中部分数据信息，这些信息表示在同一座城市中具有相同功能属性的边缘服务，这些边缘服务分布在质量不同的边缘服务器中。

表3人工数据集部分信息

6.2聚类效果验证

基于所生成的数据，分别采用k-means算法、KWDM算法以及本实施例所提出的边缘服务二次聚类算法(Edge Service Secondary Clustering Algorithm,ESSC)进行聚类，对实验结果进行统计记录，以地理位置属性为基础，绘制聚类效果图。实验结果如图1、图2、图3所示。

图1和图2分别展示了K-means算法与KWDM算法的聚类效果，可以清晰的得出KWDM算法聚类效果要优于K-means算法，KWDM算法能对所属不同城市的服务进行准确分类。然而，在MEC环境下，服务存储于边缘服务器中，因此对边缘服务进行聚类应当首先考虑地理位置与边缘服务器质量属性，之后再考虑QoS等属性，不应一次性对所有属性进行聚类。图3为一次聚类与二次聚类的效果图，通过两次聚类可以大幅度提高聚类结果中簇内相似度值，得到准确率更高的聚类结果，同时可以满足MEC环境下边缘服务对地理位置属性的依赖。人工数据集在三种聚类算法下的准确率实验结果如表4所示，算法迭代次数(MST切割次数)与准确率的变化如图4所示。

表3人工数据集下的算法准确率

6.3聚类算法性能比较分析

为了测试算法准确性等性能优劣，该实验选用UCI数据库中的Iris、Wine和Seeds三组数据集进行实验，同时将本实施例所提出的二次聚类算法中相似度计算部分进行调整以适应实验要求。其中Iris数据集样本数为150，数据属性为4，类数为3；Wine数据集样本个数为178，数据属性个数为13，类数为3；Seeds数据集样本个数为210，数据属性个数为7，类数为3。三个数据集的统计信息如表5所示。

表5三种数据集信息

为验证算法的有效性，k-means算法、KWDM算法、基于ET-SSE的K-means算法以及本实施例的二次服务聚类算法分别在三组数据集上进行实验，从聚类的准确率、迭代次数(最小生成树分割次数)及时间复杂度上进行分析。

四种聚类算法的准确率实验结果如表6所示。从表6中可以看出，二次服务聚类方法得到的平均准确率相比于k-means算法、基于ET-SSE的K-means算法以及KWDM算法分别提高了13.7个百分点、10个百分点和1.9个百分点。由此可以看出，基于ET-SS的K-means算法和KDWM算法优于k-means算法，虽然基于ET-SSE的K-means算法与KDWM算法通过确定k值或通过密度法来确定聚类中心，提高了算法的准确率，但是相较于二次服务聚类算法，其聚类准确率较低。这是因为本实施例所提出的二次服务聚类算法在对初始聚类中心进行选取时，重新定义了局部密度函数公式，提高了初始聚类中心选取的精度，增加了聚类结果的准确率。

表6 UCI数据集下的算法准确率

图5-图7为四种聚类算法在3个数据集上的迭代次数(SMST切割次数)，从图5-图7可以看出二次服务聚类算法的迭代次数(SMST切割次数)要小于或等于k-means算法、基于ET-SSE的K-means算法和KDWM算法。这是因为对局部密度函数的重定义致使初始聚类中心选取的准确率得到了提高，通过设置阈值W，当初始簇间相似度大于W时，停止对SMST的切割，减少了算法迭代次数(SMST切割次数)，加速了算法的收敛。

6.4算法时间复杂度分析

K-means算法的时间复杂度为O(nkT)，其中n为聚类样本个数，k为聚类簇数，T为聚类的迭代次数。KWDM算法的聚类过程主要分为两部分，其中选取初始聚类中心的时间复杂度为O(n

表7算法时间复杂度

从表7可以看出本实施例的算法相较于KWDM算法在时间复杂度上略微高，这是由于该算法进行了两次聚类，而且在一次聚类过程中增加了生成SMST的步骤，但通过增加生成SMST的步骤降低了后续操作的复杂性。通过两次聚类的方法，以时间换取聚类的精度，增加了聚类结果的准确性，在MEC环境下，该算法能更好的体现地理位置与服务器质量属性的重要性。

7总结

本实施例主要针对MEC环境下存在大量无序分布的边缘服务，难以有效地进行聚类的问题，提出一种MEC环境下多维属性感知的边缘服务二次聚类方法。以牺牲时间的方法换取聚类结果的高准确率，分别设计了两种算法来进行二次聚类。其中，为了提高聚类的效率，引入局部密度与MST，提出一种基于密度的最小生成树启发式分段聚类算法用于一次聚类；同时，为了进一步增强服务聚类的精度，将密度峰值算法同层次聚类算法相结合，在一定程度上解决了层次聚类不可逆所导致的聚类效果不理想的问题。实验结果表明，本实施例所提出的服务聚类方法更能符合MEC环境下服务聚类的要求，同一类簇中的服务具有更高的相似性，但是在时间复杂度上还有待提高，这也是今后需要努力研究的方向。

实施例二

本实施例提供了一种MEC环境下多维属性感知的边缘服务二次聚类系统。

MEC环境下多维属性感知的边缘服务二次聚类系统，包括：

一级聚类指标确定模块，其被配置为：将边缘服务所在服务器的地理位置与边缘服务器的硬件配置作为一级聚类指标；

二级聚类指标确定模块，其被配置为：将服务质量与信誉度作为二级聚类指标；

一级聚类模块，其被配置为：采用基于密度的最小生成树启发式分段聚类算法，依据一级聚类指标，对边缘服务进行一级聚类，得到地理位置相近、服务器质量相似的服务类簇；

二级聚类模块，其被配置为：采用基于密度峰值的层次聚类算法，依据二级聚类指标，对所述地理位置相近、服务器质量相似的服务类簇进行二级聚类，得到边缘服务聚类结果。

此处需要说明的是，上述一级聚类指标确定模块、二级聚类指标确定模块、一级聚类模块和二级聚类模块与实施例一中的步骤所实现的示例和应用场景相同，但不限于上述实施例一所公开的内容。需要说明的是，上述模块作为系统的一部分可以在诸如一组计算机可执行指令的计算机系统中执行。

实施例三

本实施例提供了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如上述实施例一所述的MEC环境下多维属性感知的边缘服务二次聚类方法中的步骤。

实施例四

本实施例提供了一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如上述实施例一所述的MEC环境下多维属性感知的边缘服务二次聚类方法中的步骤。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用硬件实施例、软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器和光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于一计算机可读取存储介质中，该程序在执行时，可包括如上述各方法的实施例的流程。其中，所述的存储介质可为磁碟、光盘、只读存储记忆体(Read-Only Memory，ROM)或随机存储记忆体(RandomAccessMemory，RAM)等。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。