高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

面向移动边缘计算中多应用服务的虚拟机部署算法

李光辉 周辉 胡世红

李光辉, 周辉, 胡世红. 面向移动边缘计算中多应用服务的虚拟机部署算法[J]. 电子与信息学报, 2022, 44(7): 2431-2439. doi: 10.11999/JEIT210415
引用本文: 李光辉, 周辉, 胡世红. 面向移动边缘计算中多应用服务的虚拟机部署算法[J]. 电子与信息学报, 2022, 44(7): 2431-2439. doi: 10.11999/JEIT210415
LI Guanghui, ZHOU Hui, HU Shihong. Virtual Machine Placement Algorithm for Supporting Multiple Applications to Mobile Edge Computing[J]. Journal of Electronics & Information Technology, 2022, 44(7): 2431-2439. doi: 10.11999/JEIT210415
Citation: LI Guanghui, ZHOU Hui, HU Shihong. Virtual Machine Placement Algorithm for Supporting Multiple Applications to Mobile Edge Computing[J]. Journal of Electronics & Information Technology, 2022, 44(7): 2431-2439. doi: 10.11999/JEIT210415

面向移动边缘计算中多应用服务的虚拟机部署算法

doi: 10.11999/JEIT210415
基金项目: 国家自然科学基金(62072216)
详细信息
    作者简介:

    李光辉:男,1970年生,教授,博士生导师,研究方向为边缘计算、物联网

    周辉:男,1996年生,硕士生,研究方向为移动边缘计算

    胡世红:女,1993年生,博士生,研究方向为边缘计算

    通讯作者:

    周辉 6191910044@stu.jiangnan.edu.cn

  • 中图分类号: TN919.2; TP393

Virtual Machine Placement Algorithm for Supporting Multiple Applications to Mobile Edge Computing

Funds: The National Natural Science Foundation of China (62072216)
  • 摘要: 移动边缘计算(MEC)通过在用户近端以虚拟机(VM)形式部署应用服务,能有效降低服务响应延迟并减少核心网络数据流量。然而,当前MEC中虚拟机部署的大多数研究尚未具体考虑用户对多种应用服务的需求。因此,该文针对MEC中多应用服务的虚拟机部署问题,提出两种启发式算法,即基于适应度的启发式部署算法(FHPA)和基于分治的启发式部署算法(DCBHPA),通过在边缘网络中配置支持多种应用服务的虚拟机来最大限度地减少网络中的数据流量。FHPA和DCBHPA分别基于边缘服务器的网络连接特征和用户对应用请求的差异性,定义了不同的适应度计算模型。在此基础上,通过子问题划分机制实现VM配置。仿真结果表明,相比于基准算法,所提算法能更好地控制系统数据流量,有效地提高边缘网络服务资源的利用率。
  • 图  1  提供多种应用服务的移动边缘计算架构

    图  2  不同VM数对数据流量的影响

    图  3  移动用户数对数据流量的影响

    图  4  网络规模对数据流量的影响

    图  5  应用服务种类数对数据流量的影响

    图  6  不同应用服务下VM部署取得的数据流量

    图  7  不同VM数对归一化服务配置总成本的影响

    图  8  应用服务种类数对归一化服务配置总成本的影响

    表  1  聚类过程

     初始化图$G$的直径$E$,根据适应度定义集合$ {X_i} $,令$ Y $为空集
     (1) for $j \leftarrow 1$to $ E $ do
     (2)  for $i \leftarrow 1$to $ k $ do
     (3)   对于距离集合$ {X_i} $中初始AS跳数为$ j $的元素$ y $
     (4)   if $ y \notin Y $ then
     (5)    更新集合$ Y \leftarrow Y \cup \{ y\} $
     (6)    更新集合$ {X_i} \leftarrow {X_i} \cup \{ y\} $
     (7)   end if
     (8)  end for
     (9) end for
    下载: 导出CSV

    表  2  基于适应度的启发式部署算法

     输入:$ G,k,A,U,\delta ,E,X $
     输出:最优VM分配策略
     (1)计算和极值正规化$ {\alpha _s},\forall s \in S,\forall \alpha \in F $
     (2)根据式(9)计算熵权$ {\omega _\alpha },\alpha \in F $
     (3)根据式(10)计算$ {W_s},\forall s \in S $
     (4)对$ W $进行降序排序,选择前$ k $个MEC服务器分别分配到集合
       ${X_i},i = 1,2, \cdots, k$
     (5)执行表1中的聚类过程将所有MEC服务器划分到${X_i},i = 1,2\cdots, k$
     (6)for $ a \in A $ do
     (7)  for $ i \leftarrow 1 $ to $ k $ do
     (8)   for $ s \in {X_i} $ do
     (9)    将应用$ a $的一个VM配置到$ s $上,通过式(2)计算集合
          $ {X_i} $内的数据流量
     (10)    end for
     (11)  将应用服务$ a $的一个VM部署在最小化$ {X_i} $内数据流量的边
         缘服务器上
     (12) end for
     (13) end for
    下载: 导出CSV

    表  3  基于分治的启发式部署算法

     输入:$ G,k,A,U,\delta ,E,X $
     输出:最优VM分配策略
     (1)计算并归一化$ R_s^a,\forall s \in S,\forall a \in A $
     (2) for $ a \in A $ do
     (3)  $Y = \varnothing$
     (4)  for $ i \leftarrow 1 $ to $ k $ do
     (5)   for $ s \in S $ do
     (6)    通过式(11)计算影响因子$ {\beta _s} $
     (7)   end for
     (8)   $ P = \left\{ {{P_s} = 0,\forall s \in S} \right\} $
     (9)   for $ s \in S $ do
     (10)    根据式(12)计算$ {P_s} $
     (11)   end for
     (12) 对$ P $降序排序,选择第1个$ {P_s} $,将满足$ s \notin Y $的$ s $加入集合$ {X_i} $
     (13) 更新集合$ Y = Y \cup \{ s\} $
     (14) end for
     (15) 执行表1中的聚类过程将所有MEC服务器划分到
        ${X_i},i = 1,2, \cdots,k$
     (16) end for
     (17) 根据表2的步骤(7)—步骤(12)找到最优VM部署位置
     (18) end for
    下载: 导出CSV

    表  4  网络拓扑表

    拓扑图节点数链路数
    spiralight1516
    noel1925
    agis2530
    shentel2835
    evolink3745
    下载: 导出CSV
  • [1] JIANG Congfeng, FAN Tiantian, GAO Honghao, et al. Energy aware edge computing: A survey[J]. Computer Communications, 2020, 151: 556–580. doi: 10.1016/J.COMCOM.2020.01.004
    [2] KHAN W Z, AHMED E, HAKAK S, et al. Edge computing: A survey[J]. Future Generation Computer Systems, 2019, 97: 219–235. doi: 10.1016/J.FUTURE.2019.02.050
    [3] PAN Jianli and MCELHANNON J. Future edge cloud and edge computing for internet of things applications[J]. IEEE Internet of Things Journal, 2018, 5(1): 439–449. doi: 10.1109/JIOT.2017.2767608
    [4] ZHOU Yuchen, YU F R, CHEN Jian, et al. Resource allocation for information-centric virtualized heterogeneous networks with in-network caching and mobile edge computing[J]. IEEE Transactions on Vehicular Technology, 2017, 66(12): 11339–11351. doi: 10.1109/TVT.2017.2737028
    [5] SUN Xiang and ANSARI N. EdgeIoT: Mobile edge computing for the internet of things[J]. IEEE Communications Magazine, 2016, 54(12): 22–29. doi: 10.1109/MCOM.2016.1600492CM
    [6] HA K, ABE Y, EISZLER T, et al. You can teach elephants to dance: Agile VM handoff for edge computing[C]. The 2nd ACM/IEEE Symposium on Edge Computing, San Jose, USA, 2017: 12.
    [7] ZHAO Lei and LIU Jiajia. Optimal placement of virtual machines for supporting multiple applications in mobile edge networks[J]. IEEE Transactions on Vehicular Technology, 2018, 67(7): 6533–6545. doi: 10.1109/TVT.2018.2808171
    [8] GAO Siyi, ZHOU Ao, CHEN Xican, et al. Redundant virtual machine placement in mobile edge computing[C]. The 1st International Conference on Blockchain and Trustworthy Systems, Guangzhou, China, 2019: 371–384.
    [9] SUN Xiang and ANSARI N. Latency aware workload offloading in the cloudlet network[J]. IEEE Communications Letters, 2017, 21(7): 1481–1484. doi: 10.1109/LCOMM.2017.2690678
    [10] KUO J J, YANG H H, and TSAI M J. Optimal approximation algorithm of virtual machine placement for data latency minimization in cloud systems[C]. The IEEE Conference on Computer Communications, Toronto, Canada, 2014: 1303–1311.
    [11] ZENG Deze, GU Lin, GUO Song, et al. Joint optimization of task scheduling and image placement in fog computing supported software-defined embedded system[J]. IEEE Transactions on Computers, 2016, 65(12): 3702–3712. doi: 10.1109/TC.2016.2536019
    [12] GU Lin, ZENG Deze, GUO Song, et al. Cost efficient resource management in fog computing supported medical cyber-physical system[J]. IEEE Transactions on Emerging Topics in Computing, 2017, 5(1): 108–119. doi: 10.1109/TETC.2015.2508382
    [13] 张海波, 刘香渝, 荆昆仑, 等. 车联网中基于NOMA-MEC的卸载策略研究[J]. 电子与信息学报, 2021, 43(4): 1072–1079. doi: 10.11999/JEIT200017

    ZHANG Haibo, LIU Xiangyu, JING Kunlun, et al. Research on NOMA-MEC-based offloading strategy in internet of vehicles[J]. Journal of Electronics &Information Technology, 2021, 43(4): 1072–1079. doi: 10.11999/JEIT200017
    [14] 张海波, 李虎, 陈善学, 等. 超密集网络中基于移动边缘计算的任务卸载和资源优化[J]. 电子与信息学报, 2019, 41(5): 1194–1201. doi: 10.11999/JEIT180592

    ZHANG Haibo, LI Hu, CHEN Shanxue, et al. Computing offloading and resource optimization in ultra-dense networks with mobile edge computation[J]. Journal of Electronics &Information Technology, 2019, 41(5): 1194–1201. doi: 10.11999/JEIT180592
    [15] YANG Song, LI Fan, SHEN Meng, et al. Cloudlet placement and task allocation in mobile edge computing[J]. IEEE Internet of Things Journal, 2019, 6(3): 5853–5863. doi: 10.1109/JIOT.2019.2907605
    [16] AGRYZKOV T, TORTOSA L, VICENT J F, et al. A centrality measure for urban networks based on the eigenvector centrality concept[J]. Environment and Planning B:Urban Analytics and City Science, 2019, 46(4): 668–689. doi: 10.1177/2399808317724444
    [17] WANG Yamin, CAO Zhiying, ZHANG Xiuguo, et al. Clustering-based algorithm for services deployment in mobile edge computing environment[C]. The 2019 IEEE 25th International Conference on Parallel and Distributed Systems, Tianjin, China, 2019: 963–966.
    [18] CHIN T L, CHEN Y S, and LYU K Y. Queuing model based edge placement for work offloading in mobile cloud networks[J]. IEEE Access, 2020, 8: 47295–47303. doi: 10.1109/ACCESS.2020.2979479
    [19] KNIGHT S, NGUYEN H X, FALKNER N, et al. The internet topology zoo[J]. IEEE Journal on Selected Areas in Communications, 2011, 29(9): 1765–1775. doi: 10.1109/JSAC.2011.111002
    [20] ZHAO Lei, LIU Jiajia, SHI Yongpeng, et al. Optimal placement of virtual machines in mobile edge computing[C]. 2017 IEEE Global Communications Conference, Singapore, 2017: 1–6.
    [21] JIA Mike, CAO Jiannong, and LIANG Weifa. Optimal cloudlet placement and user to cloudlet allocation in wireless metropolitan area networks[J]. IEEE Transactions on Cloud Computing, 2017, 5(4): 725–737. doi: 10.1109/TCC.2015.2449834
  • 加载中
图(8) / 表(4)
计量
  • 文章访问数:  567
  • HTML全文浏览量:  251
  • PDF下载量:  114
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-05-12
  • 修回日期:  2021-10-29
  • 录用日期:  2021-10-29
  • 网络出版日期:  2021-12-24
  • 刊出日期:  2022-07-25

目录

    /

    返回文章
    返回