Abstract: The efficient deployment of applications is a significant challenge in the field of factory smart manufacturing.To address this challenge,an Application Deployment algorithm based on Multiple Graph Partitioning (MGPAD) in edge cloud environment was proposed to optimize the total deployment cost and delay to improve the deployment efficiency while meeting the constraints of data center capacity limit and node latency limit.This method integrated the impact of computing cost,storage cost and communication cost on total cost,and the optimization process was divided into three stages:coarsening,initial partitioning and refining.A coarsening operation was used in the coarsening stage to reduce the graph size.The optimal partition scheme was found from the smallest coarsened graph in the initial partition stage.Finally,the partitioning scheme was projected onto the original graph layer by layer in the refining stage,and locally optimized by calculating the gain of the switching nodes.The application deployment cost optimization problem was also proved to be NP-hard.The experimental results showed that the proposed algorithm effectively reduced the total deployment cost and delay by about 3.2% and 99.2% respectively by comparing with the optimal benchmark algorithm.

Key words: cloud computing, edge computing, application deployment, cost optimization

摘要： 应用程序的高效部署一直是工厂智能制造领域的重要挑战。针对该挑战,提出一种边缘云环境下基于多图划分的应用程序部署算法(MGPAD),旨在满足数据中心容量限制和节点时延限制的约束条件下,优化部署总成本和时延,以提升部署效率。该方法综合考虑了计算成本、存储成本和通信成本对总成本的影响,优化过程可以分为粗化阶段、初始划分阶段和细化阶段3个阶段。首先,在粗化阶段采用粗化操作以缩小图的规模;其次,在初始划分阶段从最小的粗化图上找到最优的划分方案;最后,在细化阶段将划分方案逐层投影到原始图上,并通过计算交换节点的增益进行局部优化。同时证明了该应用程序部署成本优化问题是NP-hard问题。实验结果表明,所提出的算法能够有效降低部署总成本和时延,与表现最优的对比算法相比,成本和时延分别降低了约3.2%和99.2%。

关键词: 云计算, 边缘计算, 应用程序部署, 成本优化