ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2021, Vol. 58 ›› Issue (9): 2025-2039.doi: 10.7544/issn1000-1239.2021.20200338

• 人工智能 • 上一篇    下一篇

一种基于K-shell影响力最大化的路径择优计算迁移算法

乐光学1,3,陈光鲁1,2,3,卢敏3,杨晓慧1,3,刘建华1,黄淳岚1,3,杨忠明1,3   

  1. 1(嘉兴学院信息科学与工程学院 浙江嘉兴 314001);2(国网冀北电力有限公司大城县供电分公司 河北廊坊 065000);3(江西理工大学理学院 江西赣州 341000) (cmgjlj@163.com)
  • 出版日期: 2021-09-01
  • 基金资助: 
    国家自然科学基金项目(U19B2015);浙江省“鲲鹏行动”计划支持项目

A Computation Offloading Algorithm with Path Selection Based on K-shell Influence Maximization

Yue Guangxue1,3, Chen Guanglu1,2,3, Lu Min3, Yang Xiaohui1,3, Liu Jianhua1, Huang Chunlan1,3, Yang Zhongming1,3   

  1. 1(College of Information Science and Engineering, Jiaxing University, Jiaxing, Zhejiang 314001);2(State Grid Jibei Dacheng Power Supply Co ., Ltd, Langfang, Hebei 065000);3(College of Science, Jiangxi University of Science and Technology, Ganzhou, Jiangxi 341000)
  • Online: 2021-09-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (U19B2015) and the Top-level Talent Project of Zhejiang Province.

摘要: 在移动边缘计算网络中,高效的计算迁移算法是移动边缘计算的重要问题之一.为了提高计算迁移算法性能,应用同类问题的相互转换性和最大化影响力模型,利用K-shell算法对边缘服务器进行等级划分,考虑边缘服务器负载过重问题,构建路径重叠(path overlap, PO)算法,引入通信质量、交互强度、列队处理能力等指标进行边缘服务器路径优化,将优化计算任务迁移路径问题转化为社会网络影响力最大化问题求解.基于K-shell影响力最大化思想,联合优化改进贪心与启发式算法,提出一种K-shell影响力最大化计算迁移(K-shell influence maximization computation offloading, Ks-IMCO)算法,求解计算迁移问题.与随机分配(random allocation, RA)算法、支持路径切换选择的(path selection with handovers, PSwH)算法在不同实验场景下对比分析,Ks-IMCO算法的能耗、延迟等明显提升,能有效提高边缘计算网络计算迁移的效率.

关键词: 移动边缘计算, 计算迁移, 影响力最大化, 路径选择, K-shell

Abstract: As edge computing and cloud computing develop in a rapid speed and integrate with each other, resources and services gradually offload from the core network to the edge of the network. Efficient computation offloading algorithm is one of the most important problems in mobile edge computing networks. In order to improve the performance of the algorithm, a computation offloading algorithm with path selection based on K-shell influence maximization is proposed. The K-shell method is used to grade the edge servers by applying the convertibility and maximizing influence model of similar problems. Otherwise, considering the problem of excessive load of edge servers, path overlap (PO) algorithm is constructed, and indicators such as the communication quality, interaction strength, and queue processing ability, etc. are introduced to optimize the performance of the algorithm. The offloading path problem of the optimization calculation task is transformed into the social network impact maximization problem. Based on the idea of maximizing K-shell influence, greedy and heuristic algorithms are optimized and improved, and the K-shell influence maximization computation offloading (Ks-IMCO) algorithm is proposed to solve the problem of computational offloading. Through the comparative analysis of Ks-IMCO and random allocation (RA), path selection with handovers (PSwH) algorithm experiments, the energy consumption and delay of Ks-IMCO algorithm have been significantly improved, which can effectively improve the efficiency of edge computing network computing offloading.

Key words: mobile edge computing, computation offloading, influence maximization, path selection, K-shell

中图分类号: