计算机与现代化

• 数据库与数据挖掘 • 上一篇    下一篇

一种结合灰狼和FM算法的云端应用解构方法

  

  1. (1.中国科学院声学研究所国家网络新媒体工程技术研究中心,北京100190;2.中国科学院大学,北京100049)
  • 收稿日期:2019-05-10 出版日期:2020-02-13 发布日期:2020-02-13
  • 作者简介:姜凯华(1992-),男,辽宁营口人,博士研究生,研究方向:嵌入式系统,物联网,E-mail: jiangkh@dsp.ac.cn; 孙鹏(1976-),男,山东淄博人,研究员,博士,研究方向:网络新媒体技术,嵌入式系统,中间件技术; 通信作者:韩锐(1983-),男,副研究员,博士,研究方向:物联网,网络新媒体技术,E-mail: hanr@dsp.ac.cn。
  • 基金资助:
    中国科学院战略性科技先导专项基金资助项目(XDC02010701)

A Cloud Application Decomposition Method Combining GWO with FM Algorithm

  1. (1. National Network New Media Engineering Technology Research Center, Institute of Acoustics, Chinese Academy of Sciences,
    Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China)
  • Received:2019-05-10 Online:2020-02-13 Published:2020-02-13

摘要: 万物互联飞速发展,给云服务数据处理模式带来挑战。对此中科院提出海服务模式及海云协同系统架构。其中,云端应用的解构策略是影响系统性能的重要环节。而现有方法主要针对云计算场景下的无向简单图,不适用于海云协作环境下的有向带权图。为此,本文提出一种结合灰狼算法和FM算法的云端应用解构方法。利用灰狼算法快速收敛的特性,将灰狼算法的结果作为初始划分输入FM算法,以弥补FM算法对初始划分敏感的缺陷。仿真实验表明,混合算法的效果优于现有方法。划分后子图的顶点权和与海端节点资源分布匹配,且割权比明显降低,通信开销减少。

关键词: 海云协同, 应用解构, 图划分问题, 启发式算法

Abstract: The rapid development of the Internet brings challenges to the data process mode in cloud service. In this regard, the Chinese Academy of Sciences proposes the SEA service and SEA-Cloud collaboration system, in which the decomposition strategy of cloud application is an important link to affect the performance of the system. However, current mainstream methods aim to deal with the simple graph in the cloud environments, which mismatch the directed weighted graph in the SEA-Cloud collaboration scenarios. So, this paper proposes a cloud application decomposition method combining Grey Wolf Optimizer(GWO) and〖JP2〗 Fiduccia-Mattheyses(FM) algorithm to solve the problem. Benefitted from the rapid convergence of GWO, the proposed algorithm takes the outcomes of GWO as the initial inputs of FM algorithm to avoid the sensitivity of FM to the initial partitions. The simulation results illustrate that the combination method outperforms the current method. The obtained partition matches the distribution of SEA resources and the rate of edge cut decreases dramatically, which means that the communication overhead is reduced.

Key words: SEA-cloud collaboration, application decomposition, graph partitioning problem, heuristic algorithm

中图分类号: