朱金彬,武继刚,隋秀峰.基于极大团的边缘云节点聚合算法[J].计算机科学,2018,45(4):60-65
基于极大团的边缘云节点聚合算法
Edge Cloud Clustering Algorithm Based on Maximal Clique
投稿时间:2017-05-29  修订日期:2017-08-03
DOI:10.11896/j.issn.1002-137X.2018.04.008
中文关键词:  边缘云,云组合,极大团,资源块,全局最优
英文关键词:Edge cloud,Cloud combination,Maximal clique,Resource block,Global optimization
基金项目:本文受国家自然科学基金项目(61672171),广东省教育厅重大科研项目(2016KZDXM052),广东省应用型科技研发专项(重点)(2015B010129014)资助
作者单位E-mail
朱金彬 广东工业大学计算机科学与技术学院 广州510006
中国科学院计算技术研究所计算机体系结构国家重点实验室 北京100190 
jinbinzhu@outlook.com 
武继刚 广东工业大学计算机科学与技术学院 广州510006
中国科学院计算技术研究所计算机体系结构国家重点实验室 北京100190 
asjgwucn@outlook.com 
隋秀峰 中国科学院计算技术研究所计算机体系结构国家重点实验室 北京100190  
摘要点击次数: 268
全文下载次数: 193
中文摘要:
      组合多个边缘云可以向用户提供更强大的云计算服务,在大量边缘云节点集合中选择适当的节点进行组合是一项具有挑战性的任务。该问题被建模成由云节点作为顶点、节点之间的链路作为边的资源拓扑图。云组合的构建过程等同于在该图中选择子图的过程,这是一个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.
查看全文  查看/发表评论  下载PDF阅读器