移动边缘计算中资源受限的动态服务部署策略

袁景凌，毛慧华，王娜娜，向尧

移动边缘计算中资源受限的动态服务部署策略

袁景凌1，2，毛慧华1，2，王娜娜3，向尧2*

（1.武汉理工大学 三亚科教创新园，海南 三亚 572019； 2.武汉理工大学 计算机与人工智能学院，武汉 430070； 3.武汉理工大学 土木工程与建筑学院，武汉 430070）（*通信作者电子邮箱hbycxiangyao@163.com）

移动边缘计算（MEC）的出现使移动用户能够以低延迟访问部署在边缘服务器上的服务。然而，MEC仍然存在各种挑战，尤其是服务部署问题。边缘服务器的数量和资源通常是有限的，只能部署数量有限的服务；此外，用户的移动性改变了不同服务在不同地区的流行度。在这种情况下，为动态请求部署合适的服务就成为一个关键问题。针对该问题，通过了解动态用户请求来部署适当的服务以最小化交互延迟，将服务部署问题表述为一个全局优化问题，并提出了一种基于集群划分的资源聚合算法，从而在计算、带宽等资源约束下初步部署合适的服务。此外，考虑动态用户请求对服务流行度及边缘服务器负载的影响，开发了动态调整算法来更新现有服务，以确保服务质量（QoS）始终满足用户期望。通过一系列仿真实验验证了所提出策略的性能。仿真结果表明，与现有基准算法相比，所提出的策略可以降低服务交互延迟并实现更稳定的负载均衡。

服务部署；移动边缘计算；资源约束；动态需求感知；服务流行度

0 引言

随着互联网和无线通信技术的快速发展，移动计算已经极大地改变了人们的日常生活；然而，许多新的服务和时延敏感的应用不断出现，如虚拟现实（Virtual Reality， VR）和增强现实（Augmented Reality， AR）等［1］。此外，在工程领域，一些现代化的项目往往结合人工智能、VR等智能化技术，通过终端来进行管理和控制，如大坝的监测和预警。移动设备的资源（如计算和存储）限制了这些复杂服务的普及［2］。为了克服移动设备电池容量和计算能力的限制，一些解决方案［3］将任务卸载到云计算中心以解决资源短缺的问题。然而，由于广域网通信延迟较高，将任务卸载到云端可能带来较低的服务质量（Quality of Service， QoS）。

移动边缘计算（Mobile Edge Computing， MEC）的出现提供了新的思路［4-5］。通过在终端用户附近部署边缘服务器（Edge Server）来提供服务，用户可以直接访问并获得更好的QoS，而无需求助于云端，与传统方案相比，可以进一步缩短服务响应时间。

但是MEC也存在各种挑战，尤其是服务部署问题［6］。与具有丰富计算资源和巨大存储空间的云计算中心相比，边缘服务器的规模更小，通常只配备轻量级的计算组件和有限的存储、带宽等资源，所以边缘服务器只能部署数量有限的服务，因此，需要仔细选择所要部署的服务来提高QoS［7］。此外，服务部署和任务卸载具有高度耦合性，服务部署策略会影响任务卸载决策，进而影响MEC系统的性能［8］。由于用户的移动性，用户需求会随着时间的推移而动态变化，从而影响服务的流行程度，使较早部署的服务不再适用。在这种情况下，为动态变化的服务需求自适应地调整服务就成为一个关键问题。

随着移动计算的发展和边缘云的出现，移动边缘系统中的服务部署问题也得到了广泛研究［9-12］。对于优化目标，一些研究方法侧重于服务成本［9］或者服务提供商（Service Provider， SP）的利润［10］，而另一些研究方法则关注于减少服务部署的延迟［12］或者服务响应时间［13-14］。例如，文献［9］中考虑成本，提出了一种基于认证的云服务组合方法，该方法同时考虑了部署和认证/验证的成本；文献［10］中的目标是最大化所有服务提供商的总利润，提出了一种基于李雅普诺夫优化的在线算法来研究联合服务放置和请求调度问题；文献［11］中主要关注跨多个软件定义网络（Software Defined Network， SDN）的动态网络服务部署问题，并利用Dijkstra算法提出了一种启发式服务部署方法来解决这个问题；文献［13］中研究了复合云服务的部署和请求调度问题，提出了负载感知的服务部署方法和基于任务排序机制的服务请求调度方法。

本文旨在根据动态服务需求为每个边缘服务器设计服务部署策略，以使用户的交互延迟最小化；此外，还考虑了边缘服务器的资源限制以及如何平衡边缘服务器的请求负载。

本文主要工作总结如下：

1）提出了一种基于集群划分的资源聚合算法，将边缘服务器划分成集群，在计算、存储和带宽资源的约束下初步部署合适的服务。

2）考虑了动态用户需求对服务流行度及边缘服务器负载的影响，提出了一种动态调整算法来更新现有服务，保持整个边缘网络的稳定性。

3）实施了仿真实验来评估本文所提出策略的性能，与遗传算法（Genetic Algorithm， GA）、模拟退火（Simulated Annealing， SA）算法、随机算法（Random）和贪婪算法（Greedy）等基准算法相比，本文的策略可以有效地减少交互延迟并实现更稳定的负载均衡。

1 问题描述与建模

本章详细阐述服务部署问题和系统模型。

图1 边缘服务器上的服务部署示例

2 动态服务部署策略

对于第一章中描述的问题，本文提出了一种动态需求感知和负载均衡（Dynamic Requirement Awareness and Load Balance， DRLB）的策略来动态更新服务。该策略包括初始服务部署和动态调整两个阶段。

2.1 初始服务部署阶段

在部署服务之前，一般需花费巨大的成本收集所有边缘服务器的状态。为了使服务部署和动态调整更容易，将边缘服务器划分为多个集群。

集群划分过程如算法1所示，主要包括三个步骤：

3）对于剩下未分配到集群中的边缘服务器，将其划分到最近的中心边缘服务器所在的集群。

算法1 集群划分算法。

算法2 服务部署算法。

6） 根据式（3）～（5）计算约束条件；

7） If 不满足约束条件 then

8） 按照排序次序补选；

9） End If

10） End For

2.2 动态服务调整阶段

算法3 服务动态更新算法。

输出 该集群调整后的服务部署方案。

4） End For

9） End If

12） End If

15） End If

16） End For

17） End For

3 仿真与分析

本文将遗传算法（GA）、模拟退火（SA）算法、随机算法（Random）和贪婪算法（Greedy）作为基准算法。

表1 实验参数设置

如第2章所述，问题的规模主要与集群、服务和边缘服务器的数量。本文参考了文献［6］中的实验方法来测试这三个参数对本文策略DRLB性能的影响。考虑了三组参数，如表2所示。在每组参数中，其中一个参数是变化的，另外两个参数保持不变。所有实验均重复10次，使用平均值作为结果。

表2 变量设置

图2 集群数量对平均交互延迟的影响

图3 集群数量对负载均衡的影响

图4、5显示了不同服务数量对平均交互延迟和负载均衡的影响。从图4中可以看出，本文策略DRLB在所有情况下的平均交互延迟均最小。从图5中还可以发现，本文策略DRLB的服务请求量的方差均值也是对比算法中最小的，这表明本文策略在面对更复杂的用户请求时保证了更稳定的QoS。

不同数量的边缘服务器对平均交互延迟的影响如图6所示，可以看出所有方法的平均交互延迟随着边缘服务器数量的增加而增加，这是因为边缘服务器的数量对优化空间有影响，会增加问题解决的复杂性。边缘服务器数量对负载均衡的影响如图7所示，可以看出本文策略DRLB的服务请求量的方差更小，明显优于其他基准算法，图5中也体现了这一点。综上所述，可以得出结论，本文策略能够解决不同规模的服务部署问题，具有良好的可扩展性；此外，该策略的动态调整算法还具有提高边缘服务器负载均衡的能力。。

图4 服务数量对平均交互延迟的影响

图5 服务数量对负载均衡的影响

图6 边缘服务器数量对平均交互延迟的影响

图7 边缘服务器数量对负载均衡的影响

4 结语

本文重点研究了边缘计算系统中的服务部署和更新机制，提出了资源受限的动态服务部署策略DRLB。借助服务流行度来动态调整服务的部署，本文策略可以实现更稳定的负载均衡。实验结果表明，与传统方法相比，本文策略可以实现更低的平均交互延迟。未来将会在更实际的场景中考虑这个问题，比如预测用户的路径以及边缘之间的服务协作，以进一步提高部署质量。

[1] REN J， ZHANG D Y， HE S W， et al. A survey on end-edge-cloud orchestrated network computing paradigms： transparent computing， mobile edge computing， fog computing， and cloudlet［J］. ACM Computing Surveys， 2020， 52（6）： No.125.

[2] XIANG Z， DENG S， TAHERI J， et al. Dynamical service deployment and replacement in resource-constrained edges［J］. Mobile Networks and Applications， 2020， 25（2）： 674-689.

[3] GUO S T， XIAO B， YANG Y Y， et al. Energy-efficient dynamic offloading and resource scheduling in mobile cloud computing［C］// Proceedings of the 35th Annual IEEE International Conference on Computer Communications. Piscataway： IEEE， 2016： 1-9.

[4] FERRER A J， MARQUÈS J M， JORBA J. Towards the decentralised cloud： survey on approaches and challenges for mobile， ad hoc， and edge computing［J］. ACM Computing Surveys， 2019， 51（6）： No.111.

[5] YIN J W， ZHENG B P， DENG S G， et al. Crossover service： deep convergence for pattern， ecosystem， environment， quality and value［C］// Proceedings of the IEEE 38th International Conference on Distributed Computing Systems. Piscataway： IEEE， 2018： 1250-1257.

[6] PENG Q L， XIA Y N， FENG Z， et al. Mobility-aware and migration-enabled online edge user allocation in mobile edge computing［C］// Proceedings of the 2019 IEEE International Conference on Web Services. Piscataway： IEEE， 2019： 91-98.

[7] WU H Y， DENG S G， LI W， et al. Mobility-aware service selection in mobile edge computing systems［C］// Proceedings of the 2019 IEEE International Conference on Web Services. Piscataway： IEEE， 2019： 201-208.

[8] LI X， ZHANG X L， HUANG T S. Asynchronous online service placement and task offloading for mobile edge computing［C］// Proceedings of the 18th Annual IEEE International Conference on Sensing， Communication， and Networking. Piscataway： IEEE， 2021： 1-9.

[9] ANISETTI M，ARDAGNA C A， DAMIANI E， et al. Cost-effective deployment of certified cloud composite services［J］. Journal of Parallel and Distributed Computing， 2020， 135： 203-218.

[10] LEI Z， XU H， HUANG L， et al. Joint service placement and request scheduling for multi-SP mobile edge computing network［C］// Proceedings of the IEEE 26th International Conference on Parallel and Distributed Systems. Piscataway： IEEE， 2020： 27-34.

[11] ZHANG C C， WANG X W， DONG A W， et al. Dynamic network service deployment across multiple SDN domains［J］. Transactions on Emerging Telecommunications Technologies， 2020， 31（2）： No.e3709.

[12] ZHANG S L， LIU C， WANG J W， et al. Latency-aware deployment of IoT services in a cloud-edge environment［C］// Proceedings of the 2019 International Conference on Service-Oriented Computing. Cham： Springer， 2019： 231-236.

[13] ZHOU J Y， FAN J X， WANG J， et al. Dynamic service deployment for budget-constrained mobile edge computing［J］. Concurrency and Computation： Practice and Experience， 2019， 31（24）： No. e5436.

[14] LU Y C， LIN C K， LAI K C， et al. Service deployment and scheduling for improving performance of composite cloud services［J］. Computers and Electrical Engineering， 2019， 74： 616-634.

[15] 陈玉平，刘波，林伟伟，等. 云边协同综述［J］. 计算机科学， 2021， 48（3）： 259-268.（CHEN Y P， LIU B， LIN W W， et al. Survey of cloud-edge collaboration［J］. Computer Science， 2021， 48（3）： 259-268.）

[16] NEWMAN M E J. Power laws， Pareto distributions and Zipf’s law［J］. Contemporary Physics， 2005， 46（5）： 323-351.

Dynamic service deployment strategy in resource constrained mobile edge computing

YUAN Jingling1，2， MAO Huihua1，2， WANG Nana3， XIANG Yao2*

（1，，572019，；2，，430070，；3，，430070，）

The emergence of Mobile Edge Computing （MEC） enables mobile users to easily access services deployed on edge servers with low latency. However， there are various challenges in MEC， especially service deployment issues. The number and resources of edge servers are usually limited and only a limited number of services can be deployed on the edge servers； in addition， the mobility of users changes the popularities of different services in different regions. In this context， deploying suitable services for dynamic service requests becomes a critical problem. To address this problem， by deploying appropriate services by awareness of the dynamic user requirements to minimize interaction delay， the service deployment problem was formulated as a global optimization problem， and a cluster-based resource aggregation algorithm was proposed， which initially deployed suitable services under the resource constraints such as computing and bandwidth. Moreover， considering the influence of dynamic user requests on service popularity and edge server load， a dynamic adjustment algorithm was developed to update the existing services to ensure that the Quality of Service （QoS） always met user expectations. The performance of this deployment strategy was verified through a series of simulation experiments. Simulation results show that compared with the existing benchmark algorithms， the proposed strategy can reduce service interaction delay and achieve a more stable load balance.

service deployment; Mobile Edge Computing (MEC); resource constraint; dynamic requirement awareness; service popularity

This work is partially supported by National Natural Science Foundation of China （61303029）， Major Science and Technology Project of Sanya Yazhou Bay Science and Technology City Administration （SKJC-KJ-2019KY02）.

YUAN Jingling， born in 1975， Ph. D.， professor. Her research interests include machine learning， distributed parallel processing， intelligent analysis.

MAO Huihua， born in 1996， M. S. candidate. His research interests include edge intelligence， edge computing.

WANG Nana， born in 1978， Ph. D. Her research interests include intelligent method， safety monitoring.

XIANG Yao， born in 1989， Ph. D. His research interests include mobile edge computing， intelligent computing.

TP393

A

1001-9081（2022）06-1662-06

10.11772/j.issn.1001-9081.2021061615

2021⁃09⁃13；

2021⁃11⁃19；

2021⁃11⁃24。

国家自然科学基金资助项目（61303029）；三亚崖州湾科技城管理局重大科技项目（SKJC‑KJ‑2019KY02）。

袁景凌（1975—），女，湖北武汉人，教授，博士，CCF会员，主要研究方向：机器学习、分布式并行处理、智能分析；毛慧华（1996—），男，江西宜春人，硕士研究生，CCF会员，主要研究方向：边缘智能、边缘计算；王娜娜（1978—），女，山东青岛人，博士，主要研究方向：智能方法、安全监测；向尧（1989—），男，湖北宜昌人，博士，CCF会员，主要研究方向：边缘计算、智能计算。