文摘

随着物联网的发展(物联网),它形成大数据,生成的大量数据和处理大数据的复杂性带来的挑战在边缘计算资源调度。为了解决资源调度的问题,提高用户的满意度在边缘计算环境中,我们提出一个面向用户的改进的谱聚类调度算法(或弹性体)。基于改进的k - means算法,或弹性体算法解决问题的聚类结果对初始值很敏感和实现重新集群,使获得的聚类结果更稳定。最后,边缘计算资源调度方案获得基于聚类的结果。实验结果表明,基于改进的谱聚类算法的资源调度方案优于传统的谱聚类算法在边缘计算环境。

1。介绍

边缘计算是云计算的扩展;它是一种快速处理数据在网络的边缘1- - - - - -3]。

物联网的发展的目标(物联网)是连接电子设备,移动终端,家用电器等等4- - - - - -6]。这些设备不仅数量大,而且在地理分布广泛。在现实世界中,当用户使用这些物联网设备,云计算有不同的要求,如低延迟和位置识别7- - - - - -10]。此外,随着大数据时代的到来,传统的数据分析方法和存储技术遇到瓶颈。大数据具有数据量大的特点,数据结构的多样性,和快速处理的要求11,12]。然而,大量数据的接收和传输之间的I / O瓶颈可能会导致云计算数据中心和终端;传输速度和处理速度大大降低,甚至造成大量资源调度延迟。

处理范围的边缘计算更接近数据源。处理数据收集之后,它在网络的边缘,而不是在中央服务器;它提供智能服务近边缘低延迟和位置感知和其他特性和支持移动性。在物联网中,边缘计算通过数据分析和处理不仅实现了传感,互动,和控制对象之间,还为用户提供了实时的资源调度和分配(13]。很明显,边缘计算可以满足这些物联网设备的需要。

与各种用户需求(14),用户可以选择将数据存储到本地计算边缘或将其发送到云计算。在这种情况下,资源分配和调度是面向用户的,所以不适用面向任务的调度算法。目前,大多数现有的调度算法应用于网格计算和虚拟机调度;它不能满足计算边缘的特点,如低延迟、接近最终用户,广泛的地理分布,和其他特征,一般调度算法不能满足用户的多样化需求。要解决这些问题,本文提出了最终用户的资源调度算法,旨在解决资源调度问题的计算。

2。相关工作

作为一个更成熟的服务平台,云计算处理大数据中发挥着重要作用。此外,有许多云计算资源调度和资源分配算法15- - - - - -23]。

2016年,崔HeeSeok et al。24]提出了基于任务的任务合并算法分类和资源利用率的云数据中心。此外,他们设计了一个VM合并算法来平衡任务执行时间和能源消耗在不违反一个预定义的服务水平协议(SLA)。

2016年,吴et al。25)提出了一种连续集群移动云计算资源调度方案的基础上改进的FCM (IGAFCM)算法来减少匹配需求在搜索过程的大小。此外,实验证明了匹配策略可以动态地调整根据匹配分数和反馈培训。

2016年,Cheol-Ho香港et al。26)提出了一种新的机制,称为小区(先进的网络信用调度器),保证QoS通过动态分配网络资源虚拟化。满足云用户的各种网络的要求,小区旨在同时提供多个性能政策;这些包括体重依赖型剂量比例共享、最小带宽的预订和最大带宽限制。

边缘的计算是一个新的平台,可以为当地的移动设备。边缘计算使得资源共享或资源缓存中广泛部署边缘计算集群。接下来,我们介绍一些学者关于边缘的工作计算资源管理。

2015年,苏et al。27]研究了资源缓存方案在边缘计算基于Steiner树。当计算边缘服务器缓存资源,首先生成Steiner树最小化总路径的权值(成本);这个Steiner树可以最小化资源缓存的成本。然后这篇文章给了一个运行的例子,并与最短路径方案,结果表明,基于Steiner树方案可以更有效地工作。

2015年,Aazam et al。28)提出了一种动态资源分配通过雾微数据中心,它认为,边缘计算是在物联网和云计算之间。它的目的是管理资源,实现数据过滤、数据预处理和数据加密。为此,本文提出了一种计算环境资源管理架构的优势。本文考虑的因素放弃客户,服务的类型,服务价格,和不同的豁免概率波动。实验结果表明,这些因素可以帮助服务提供者正确估计资源的数量。

2015年,达塔等。29日)提出了边缘计算和以消费者为中心的网络,讨论了边缘计算范例,以及它如何以消费者为中心的物联网。计算架构可以集成到一个边缘M2M标准系统。

资源调度算法提出了基于聚类方法。聚类分析是多元统计分析和非监督模式识别的一部分30.- - - - - -32]。与k - means聚类算法相比,谱聚类具有显著的优点,它可以识别任何集群的形状,如凸集群,并且很难落入局部最优解,使得聚类算法有一定程度的提高较传统的聚类算法。2015年,周et al。33)提出了谱聚类算法来解决云计算的资源调度和分配问题。然而,不难看到的谱聚类算法的实现步骤,和k - means算法中需要最后一步。因为k - means算法对初始值敏感,谱聚类算法很难保证稳定的聚类结果。在这方面,段等。34)提出了一种改进的k - means算法,改进的k - means算法使用“射击目标”的原则来搜索聚类中心。

3所示。资源调度体系结构

边缘的计算环境的支持物联网,有两种形式的服务提供给最终用户:一个是基于任务的数量和负载的大小,和最终用户提交任务计算边缘微数据中心(35,36]。另一种是用户提交的资源计算边缘微数据中心,数据中心和边缘计算微观分配资源根据最终用户提交的请求(37]。有两种形式的服务,面向前我们称之为任务,后者我们称之为面向用户的。这两种形式的服务之间的区别如下。面向任务的资源调度,没有明确的需求资源的计算能力。根据提交的任务负载和任务量计算,计算边缘微数据中心分配资源与相应的处理能力来执行任务。面向用户的资源调度,用户提交请求资源分配到边缘计算微数据中心。用户的请求包括明确要求资源的计算能力和清晰的资源占用的时间间隔。在这篇文章中,我们考虑问题的资源调度和分配在边缘计算根据面向用户的服务形式。

在物联网的框架下,边缘计算是云计算和物联网设备之间38,39),三个层次如图1。边缘计算预处理所收集的数据,然后上传它到云数据中心;这可以极大地减少了云数据中心的压力。

在边缘计算、资源调度过程的体系结构如图2用户提交请求,边缘微数据中心(EMDC)和边缘服务器根据用户的请求分配资源。如果当前用户所请求的资源是暂时的边缘中心(Edge1),边缘服务器可以发送广播消息的相邻边中心(Edge2)。Edge1提交请求Edge2过程;如果Edge2没有用户想要的资源请求,然后Edge2可以上传周边Edge3来处理用户的请求。边缘服务器在边缘计算大多由电脑表现不佳,和系统资源是有限的。当一些用户提交请求,如果超出能力范围的边缘计算处理数据,然后计算边缘会选择用户的数据转移到云服务器。在本文中,我们研究了在边缘计算资源调度问题,所以我们不考虑后的资源调度过程数据上载到云。

4所示。解决调度问题

4.1。调度问题的数学描述

请求是指资源配置要求用户提交边缘计算微数据中心。它主要包括以下几个方面:计算资源能力(通常表达的数以百万计的指令每秒);时间间隔(包括开始时间、完成时间)。为了简化计算过程,计算资源的数量是用于表示用户对计算资源的需求的能力。

资源是指资源在边缘计算微数据中心,如计算资源、通信资源和存储资源。当用户请求资源分配到边计算,如果相同的计算单位是需要不同的用户,有一个重叠的使用时间间隔的资源,导致资源争用,降低资源利用率和服务延迟。在这篇文章中,我们称之为重叠的时间间隔是重叠的程度。重叠程度的大小取决于用户占用的时间间隔的计算单位。

摘要聚类算法解决问题,减少用户请求的重叠程度和提高资源利用率。聚类的目的是请求的用户。聚类是基于时间请求之间重叠的程度。重叠程度越大,相似度越高。通过集群,请求大重叠度可以在同一类别,并请求小程度的重叠可以分配给不同的类别。在调度过程中,资源可以分配给不同类别的请求同时减少资源争用的可能性,提高服务质量。

每个请求的用户有一个明确的资源占用的时间间隔(包括开始时间和完成时间),和不同的用户请求可以重叠的时间间隔。所有用户之间的重叠程度构成一个矩阵,由米。

矩阵米有n个n个元素,每一种都可以定义如下:

在公式(1),P_ij是我和用户之间的重叠时间j。T是分隔的时间间隔由边缘计算,有多个请求到达这个时间间隔。如图3时间间隔T从0到9,总共10个时间间隔,T = 10。最早开始请求user1,最新user4完成请求。user1请求的时间间隔 ,和user4请求的时间间隔 。时间重叠的程度存在当且仅当两个用户请求相同的资源。阴影的削减额度,当user1和user2请求相同的资源时,有一个时间间隔的两个用户之间的重叠。因此,根据公式(1),用户1和用户2之间的重叠程度 。

假设0时刻计算边缘微数据中心接收N服务请求,可用资源的数量米,单个资源的计算能力是常数,所以我们相信没有区别两个独立的计算单元(节点)的能力。不同的用户有不同的计算能力的要求。根据用户的需求,多个资源可以分配给一个用户在同一时间。

让 用户组,将计算单元上执行r;集年代是指所有用户的集合。两个不同的单位和 ,一个用户可以申请两个计算单元的使用和 ,所以集之间的十字路口和不是空的。事实上,因为请求可以占用多个计算单元,这增加了问题的复杂性。因此,我们需要将请求占用多个单位。如果请求的用户需要单位,应该分成要求有相同的时间间隔与以前的请求。所以请求 可以扩展到准备好了吗 在哪里 和是单位所需的数量代表了吗请求。

我们假设服务请求年代是随机生成的, ,n= 30。假设30请求依次分为6组;每组的数量单位被由一组表示G =G₁G₂G₃G₄G₅G₆ 在G₁= 3 G₂= 2 G₃G = 5,₄= 1,G₅= 2 G₆= 1。根据这个公式 ,所以请求设置 可以扩展到准备好了吗 ,我们得到 ,所以一组 。

对资源分配的过程中,计算单元操作的数量k,k最小值;即有一个边界之外的边际计算微数据中心服务。显然,这个最小值对应于所有用户所需的最大值的计算能力。让是最小值,我们知道 从先前的分析。例如,如果要求计算能力是五个单元,计算边缘微数据中心不四个或更少的单位分配给用户。同时,计算单位的数量操作也有最大值。很明显,最大不会超过可用的计算单位的数量。让最大值, 。很明显, 。

4.2。调度的目标

在边缘计算、资源利用率和服务质量(QoS)应该考虑终端用户的资源调度。资源调度(这些都是非常重要的参考因素40- - - - - -43]。资源利用率影响经济效益,以及QoS影响客户满意度。

有两个用户服务请求和 ; 意味着重叠的程度。我们考虑标准化和计算的简化,让 ,在那里β是一个常数, 。由此,我们可以看到,重叠程度越高,越高是多少。

因此,调度的目标之一,可以以这种方式被表达,并找到策略满足以下公式:

由公式(2),我们可以为用户最满意的政策。然而,它并不考虑资源的优化问题,这也是调度的目标之一。例如,当用户需求并不要求计算能力,边缘计算微数据中心将派遣一个小数量的计算单元来满足用户的要求,而且可以提高资源利用率,减少的数量计算单位。

已知的时间间隔的长度T和为每个计算单元 ,资源利用率可以表示为

从用户的角度来看,用户请求包括资源的使用时间和数量的资源,这意味着时间T和每个用户应用程序资源的数量是固定的。因此,价值是常数,与的价值k。根据公式(3),资源利用率的大小是由k。回应用户的需求时,为了提高资源利用率,减少资源的操作。然而,资源的减少,可以投入使用将不可避免地增加了重叠的程度。这就产生了一个问题,系统之间必须做出选择的资源数量和重叠的程度。

如前所述,重叠影响服务质量(QoS),降低用户满意度。我们都知道,有许多因素影响服务质量(QoS)。本文关注的是资源调度和分配问题。摘要QoS表示为延迟程度,实际完成时间比预期完成时间的服务。QoS条件定义为如下表示:

总之,在满足QoS的前提条件下,我们的资源调度的目标可以表示为

4.3。解决方案

正如前面所提到的,我们的目标是找到一个满足公式(公式5)。如果我们认为重叠程度是欧几里得距离,那么大规模的请求应该形成一个集群结构,以及不同簇之间的距离非常大;此外,不同集群之间的重叠程度很小。然而,集群中的节点之间的距离越小,集群中的节点之间的重叠程度越大。这意味着我们可以将调度问题变成一个聚类问题。

的详细过程调度问题转化为一个聚类问题如下。

首先,一组年代设置存储用户的请求,和边缘计算分配资源所需的用户。

其次,每个两个请求之间的重叠度的设置年代根据公式计算1)。应该注意的是,某些用户请求可能需要多个资源与其他多次请求和重叠。在这种情况下,请求需要被分成多个subrequests。一组年代扩大为一组吗 ,和之间的欧几里得距离请求构建一个矩阵计算的重叠程度。

最后,改进的谱聚类算法是用来解决聚类问题。重叠度矩阵被认为是一种相似性矩阵,和矩阵的谱聚类算法减少了尺寸。改进的k - means用于完成聚类。

根据最终的聚类结果,以便于寻找一个更好的调度策略,选择请求位于不同的集群,和一组调度策略需要建立存储选中的请求。显然,请求之间的重叠度调度策略的组内很小,和请求之间的重叠程度不同的调度集很大。

4.3.1。改进的k - means算法

为了使聚类结果对初始值,在本文中,我们使用段等人提出的改进的k - means算法,然后结合它与谱聚类算法实现相对稳定的聚类结果。

改进的k - means算法(称为myk-means)主要增加了初始聚类中心选择算法。最初的数字集群中心k搜索的数量C,一组B用于存储C k集群中心, 。循环搜索算法聚类中心,每次选择结果放入 ,一组H商店最终聚类中心的选择结果,H =最小值变形( ) 。

在聚类算法中,由于初始聚类中心选择算法是补充道。在选择最优的初始中心下一个集群,相似度矩阵(数据集所有点之间的距离)的整个数据集需要计算每一步,使得该算法时间成本非常大或者需要存储计算相似度矩阵,进而需要大量的存储空间。简而言之,当该算法应用于一个数据集的数据量较大,有一个问题,计算时间太长,或存储空间不足,它不适合大规模系统与许多节点。

为了解决上述问题,降低了聚类算法的计算复杂度,在本节中,我们使用赵提出的改进的聚类算法(44]。

当我们选择下一个集群的集群中心,如果选中的点是在靠近发现集群中心,然后将会有很少的中心值差两个集群在最后的聚类结果。显然,这是毫无意义的,所以一个点周围一定范围内发现集群中心可能不是集群中心的下一个集群。当选择最佳的初始中心的下一个集群,这些点需要首先被排除在外。具体实现过程如下。

如果我们知道最终结果 (k - 1)集群的聚类问题,我们得到的所有集群 与 随着集群中心。首先我们计算的平均距离所有数据点之间在每个集群和集群中心 。

在哪里所有数据点的数量吗 。

我们把参数 (44),很明显 。让 ,在那里是一个足够小的正数。我们引入一个参数 ;很明显 ,( )。

所有的点在该地区 随着半径为中心了,下一个集群的初始聚类中心选择从剩下的点,这将有效地减少数据点的数量需要计算。这减少了大量的计算。在增量方法,k增加,获得集群的结构也越来越稳定,所以参数的值可以相应地增加排除更多的点。

4.3.2。谱聚类算法

谱聚类算法中,我们首先需要解决相似矩阵,我们定义重叠度矩阵P的相似性矩阵。对于任意的 ;也就是说,对角元素是0。然后重叠度矩阵可以表示为

在哪里 。然后我们可以计算出归一化矩阵 ,拉普拉斯算子的矩阵 。

我们可以假定所有的请求分为k₁,k₂两类,分类标准;本文使用标准的部门(归一化)方法。让问是一个向量。的元素定义如下:

其中,D₁重叠的总和在吗k₁,再加上削减(k₁k₂),D₂重叠的总和在吗k₂,再加上削减(k₁k₂),d=d₁+d₂-切(G₁,G₂)。

然后 ;的限制

这时,拉普拉斯算子矩阵的归一化(规范化的拉普拉斯算子,对角元素都是1)= D-1/2 L D-1/2特征值和相应的特征向量。因为L和特征值是相同的,特征向量之间的关系是什么= D^1/2问,所以我们可以得到的特征值对应的特征向量 ,最后我们可以得到乘以D^1/2。

4.3.3。改进的谱聚类算法(或弹性体)

基于改进的k - means算法,我们提出了一种改进的谱聚类算法(或弹性体)。该算法不仅解决了初始值的问题,而且实现了二次聚类。如上所述,根据QoS条件,我们考虑的参数 。在执行算法时,我们可以通过法官的大小参数是否需要二次聚类。如果当前QoS满足用户需求的资源调度算法执行后,没有必要recluster。接下来,谱聚类优化调度算法的实现步骤介绍了。

调度算法的详细步骤如下:

将一组 为一组 。

根据集合中的元素之间的重叠程度 ,重叠度矩阵计算P,和的值根据公式计算吗 。

L构造拉普拉斯算子矩阵和计算矩阵的特征值L。

特征值所对应特征向量构造矩阵R。

计算和 。

为 。

使用改进的k - means集群行向量矩阵R的方法。

计算延迟E, QoS的条件 ,和系统资源利用率U,根据公式(3): 。

如果 ,停止循环;否则,返回上一步,重新启动。

获得的调度策略可以根据k集群。

或弹性体算法的流程图如图4。

4.4。资源调度

4.1.1。调度过程

资源调度过程中边计算,如图5最终用户提交服务请求,边缘微数据中心(EMDC)通过计算边缘。EMDC资源监控器设置,和动态资源监控器将检测随时可用资源的状态信息并保存在EMDC这些资源的状态信息。集群服务请求或弹性体算法集,分类成几个不同的请求,然后安排资源。最后,这些请求的资源分配安排。

10/24/11。或弹性体算法的伪代码

通过上述步骤,资源调度问题转化为一个聚类问题,和资源调度方案可以根据获得的聚类结果。或弹性体算法可以有效地解决在边缘计算资源调度问题。

或弹性体算法如算法的伪代码1。

4.5。算法的正确性和性能分析

该算法包括三个阶段;第一阶段计算之间的重叠度用户服务请求集;每个服务请求包含开始时间和结束时间;重叠度矩阵可获得根据重叠的时间间隔。在第二阶段,重叠度矩阵是对角化,和拉普拉斯算子矩阵是由使用正常的切割方法,建立和特征向量。在第三阶段,我们使用myk-means集群算法,和原来的k - means算法的基础上,添加初始聚类中心选择算法,多次遍历搜索数据样本k最好的初始聚类中心。然后,根据初始聚类中心,k获取集群形成调度策略。在上面的三个阶段中,用户之间的时间重叠程度被认为是数据样本之间的相似性,以及调度问题转化为聚类问题。我们大重叠度请求划分为一个类,并将他们分成不同的类小重叠的程度。聚类算法可以使样本之间的相似性最大,和样品之间的相似性是最低,因此我们的算法是正确的。

定理4 - 1或弹性体算法可以完成在边缘计算资源调度;时间复杂度是O (nck)。n表示数据样本的数量,c代表了初始聚类中心的次数搜索,和k代表集群的数量。

在大规模数据集,搜索的数量c比样品的数量要少得多,所以时间复杂度的算法避免陷入最糟糕的O (n²)。

根据常见的聚类算法性能指标,如表所示1相比之下,本文或弹性体算法,传统的谱聚类算法和k - means算法。

5。仿真结果

我们的仿真实验是基于MATLAB平台,假设已知的服务质量(QoS)条件= 0.1,T= 60,米= 5(这意味着每个用户可以申请5计算单位最多)。的忙碌时间5计算单位T表示为T₁,T₂,T₃,T₄,T₅分别和他们的价值观35,20.,30.,39,53。

根据每个请求的开始时间和完成时间,表示和 ,和单位的数量需要占领,用字母表示一个,请求被表示为数据点的三维坐标。如图6集群的数量是资源的数量;超过的时间曲线1和资源利用率1是通过或弹性体算法,相比之下,时间超过曲线2和资源利用率2传统的谱聚类算法。通过计算公式(3),我们可以看到,当集群的数量k = 3,或弹性体算法的资源利用率U = 98%,传统的谱聚类算法的资源利用率U = 94%。或弹性体算法4%比传统光谱集群资源利用率高。

当预期的完成时间60年代至少和集群的数量3,或弹性体算法的运行时间1.9111秒和QoS保证条件。从图可以看出6传统的谱聚类算法的时间超过曲线上下波动;这是因为原来的k - means算法对初始值敏感,导致延误程度的一个显著变化。传统的谱聚类算法。时间超过或弹性体的曲线算法接近稳定,显示低延迟特性。

根据大数据的多样性的实际情况,我们选择两种类型的数据样本集。第一个样本集,分别使用k - means算法和myk-means算法。对于第二个样本集,我们使用传统的谱聚类算法和或弹性体算法,分别;同时,它是相对于k - means算法。

当使用传统的k - means聚类算法,实验结果如图7和8;的X轴代表服务请求的开始时间Y轴代表服务请求的完成时间,以及Z轴代表的数量计算单位所需的服务请求。在这里我们设置5计算单位最多,用户可以适用。不难发现从图8相同的颜色是相同的类,传统的k - means算法聚类结果是错误的,这是由于聚类结果依赖于初始聚类中心。

图9使用myk-means显示了该算法的结果。如图9,相同的颜色是相同的类,相同时间重叠类很大,和用户必须等待资源到资源闲置,所以它容易降低客户的满意度。不同类型的请求可以同时回应,因为没有时间重叠,同时,边缘计算分配资源,从而避免资源争用,因此调度策略。不同类别的要求有不同的颜色;此外,不同类别的请求被组合成一套调度在调度过程中,可以减少重叠程度和服务延迟,提高QoS和资源利用率。

从下两种算法的对比实验结果,我们可以得出结论,myk-means本文中使用聚类算法优于传统的k - means算法,myk-means聚类算法选择合适的初始聚类中心,它可以收敛到一个更好的局部最优解,获得更准确的资源调度。

在图10,蓝线代表传统的谱聚类算法的运行时间,和红色的线代表或弹性体算法的运行时间。从图可以看出10,通过改进的谱聚类算法和减少数据计算,或弹性体算法的执行效率可以有效地改善。此外,随着规模的请求继续增加,time-growth趋势或弹性体的算法比传统的谱聚类算法慢。

为了显示或弹性体算法比k - means算法和传统的谱聚类算法在聚类精度和适用性范围,本文实验结果如图11和12。

在图11,我们可以看到,传统的谱聚类算法的聚类结果不稳定,由于聚类结果取决于选择的初始聚类中心;当选择贫穷的初始聚类中心,传统的谱聚类算法的聚类产生的结果是不稳定的。

在图12,传统的k - means算法不能解决聚类问题,我们的算法可以得到稳定的集群解决方案。此外,当QoS条件不满足用户的需求,该算法将重新集群,直到满足用户需求。总之,本文的算法优于传统的k - means算法和传统的谱聚类算法在解决边缘计算资源调度的问题。比较图11,不难发现或弹性体算法的聚类结果理想。

6。结论

在本文中,我们分析了面向用户的资源调度问题的边缘计算物联网并提出或弹性体算法在边缘计算解决调度问题。在边计算,用户可以同时运用各种资源,从而导致重叠的时间间隔,增加资源调度问题的难度。首先,我们将资源调度的重叠程度问题转换为聚类问题。其次,我们进行重叠度矩阵变换和特征向量聚类。最后进行资源调度与不同颜色的类别。实验表明,该调度算法能稳定聚类结果保证QoS条件下,它可以获得更高的资源利用率。在这个问题中,我们假设每个计算单元具有相同的计算能力,和未来研究工作的重点应该放在不同的计算单元的计算能力的区别。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作是由中国国家自然科学基金(61672321和61672321),山东省研究生教育创新计划(SDYY14052和SDYY15049),曲阜师范大学科技项目(xkj201525)、山东大学科技计划项目(J16LN15),山东省专业学位研究生教学案例图书馆建设项目和山东省研究生教育质量课程建设项目。