基于极大团的边缘云节点聚合算法  

Edge Cloud Clustering Algorithm Based on Maximal Clique

作　　者：朱金彬 武继刚[1,2] 隋秀峰[2] ZHU Jin-bin;WU Ji-gang;SUI Xiu-feng(School of Computer Science and Technology,Guangdong University of Technology,Guangzhou 510006,China;State Key Laboratory of Computer Architecture,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China)

机构地区：[1]广东工业大学计算机科学与技术学院,广州510006 [2]中国科学院计算技术研究所计算机体系结构国家重点实验室,北京100190

出　　处：《计算机科学》2018年第4期60-65,共6页Computer Science

基　　金：本文受国家自然科学基金项目(61672171),广东省教育厅重大科研项目(2016KZDXM052),广东省应用型科技研发专项(重点)(2015B010129014)资助。

摘　　要：组合多个边缘云可以向用户提供更强大的云计算服务,在大量边缘云节点集合中选择适当的节点进行组合是一项具有挑战性的任务。该问题被建模成由云节点作为顶点、节点之间的链路作为边的资源拓扑图。云组合的构建过程等同于在该图中选择子图的过程,这是一个NP完全问题。子图的选择策略是决定云组合性能的重要因素,现有的minStar算法贪心地选择节点之间通信延迟最小的子图,将最优资源分配给当前用户,导致了局部最优和全局性能不良的问题。鉴于此,提出基于极大团的边缘云资源分配算法,提取图中的极大团并将其划分为若干互不重叠的规模较小的完全子图,以子图为单位构建资源块,以资源块为单位进行资源的分配。实验结果表明,与minStar算法相比,新算法将全局最大通信延迟降至原来的50%。Effective combination of edge clouds can offer more powerful computing capacity,which is a promising research direction in cloud computing.It is a challenging work to select multiple edge clouds to combine,because a bad strategy will make a negative impact on the computational power of the obtained group.The problem is generally modeled as a resource topology graph in which cloud nodes are represented as vertices,and the links between nodes are represented as edges.The selection of edge cloud is equivalent to subgraph extraction of the resource topology graph,and this is a typical NP problem.The current minStar algorithm extracts the subgraph with the smallest communication delay between nodes,and then assigns the corresponding resources to the customer.It is a greedy strategy,resulting in local optimal and poor global performance.The proposed algorithm based on maximal clique divides maximal cliques into several smaller but complete subgraphs which do not overlap each other,then constructs resource block in unit of complete subgraph,and assigns the cloud resource in unit of resource block.Compared with minStar algorithm,simulation results show that the global maximum communication delay is reduced by 50%with the proposed algorithm.

关 键 词：边缘云 云组合 极大团 资源块 全局最优 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]