一种联合边缘服务器部署与服务放置的方法

doi:10.19678/j.issn.1000-3428.0068576

摘要/Abstract

摘要：

边缘计算(EC)在靠近用户的网络边缘部署边缘服务器(ES), 并将服务放置在ES上, 从而可以满足用户的服务需求。独立研究ES部署和服务放置问题的成果已有很多, 但两者存在高度耦合关系。考虑到EC系统的收益, 有必要提供付费服务, 使得EC系统处理用户服务请求时会获得相应收入。同时, EC系统处理用户服务请求时会产生时延和能耗成本, 为了最大化EC系统的收益, 在用户服务请求和服务价格不同的约束下, 需要合适的服务放置方案来提高EC系统的收益。为此, 在ES与基站之间的位置关系、ES部署和服务放置之间的耦合关系、服务副本数和服务价格等约束下, 提出一种包括改进的k-means算法和多智能体强化学习算法的两步方法, 使EC系统的收益最大化。首先, 构建一个联合ES部署和服务放置模型, 其中ES部署明确考虑了基站之间的位置关系, 服务放置明确考虑了ES部署的位置, 以及不同的服务请求和价格; 然后, 基于基站的位置关系和基站的服务请求负载, 通过带约束的k-means算法, 在不同约束条件下分别确定最佳的ES部署位置以及ES的协作域; 最后, 以最大化EC系统收益为目标, 通过多智能体强化学习算法在ES上放置服务。实验结果表明, 与对比方法相比, 所提方法能够提高收益7%~23%。

关键词: 边缘计算, 边缘服务器部署, 服务放置, k-means聚类算法, 多智能体强化学习算法

Abstract:

Edge Computing (EC) deploys Edge Servers (ES) at the edge of the network close to the user. Services are placed on the ES to meet users' service needs. Several independent studies have been conducted on ES deployment and service placement. However, a highly coupled relationship exists between the two and they should be studied simultaneously. In addition, the economic benefit of the EC system is a consideration because paid services must be provided for the EC system to earn revenue in processing user service requests; however, the EC system incurs delays and energy costs when processing the user service requests. To maximize the benefits of the EC system under the constraint that user service requests and service prices are different, appropriate service placement solutions are required to increase the overall profit. To that end, this study considers the constraints of the location relationship between ES and base stations, coupling relationship between ES deployment and service placement, number of service replicas, and price of the service and proposes a two-step approach that includes an improved k-means algorithm and a multi-agent reinforcement learning algorithm. The goal is to maximize the benefits of EC systems. First, a joint ES deployment and service placement model is constructed. One of the ES deployments explicitly considers the location relationship between base stations, whereas service placement considers the location of ES deployments as well as different service requests and pricing. Subsequently, based on the location relationship of base stations and service request load of base stations, the k-means algorithm is used under constraints to determine the optimal deployment location and collaborative domain of ES under different constraint conditions. Finally, to maximize the benefits of the EC system, a multi-agent reinforcement learning algorithm is used to place services on the ES. The experimental results show that the proposed algorithm increases the benefits by 7% to 23% relative to the comparison algorithms.

Key words: Edge Computing(EC), Edge Server(ES) deployment, service placement, k-means clustering algorithm, multi-agent reinforcement learning algorithm

张俊娜, 韩超臣, 陈家伟, 赵晓焱, 袁培燕. 一种联合边缘服务器部署与服务放置的方法[J]. 计算机工程, 2024, 50(10): 266-280.

ZHANG Junna, HAN Chaochen, CHEN Jiawei, ZHAO Xiaoyan, YUAN Peiyan. A Method for Joint Edge Server Deployment and Service Placement[J]. Computer Engineering, 2024, 50(10): 266-280.

https://www.ecice06.com/CN/Y2024/V50/I10/266

图/表 15

图1 边缘服务器部署示意图

Fig.1 Schematic diagram of edge server deployment

图2 边缘服务器的协作域示意图

Fig.2 Schematic diagram of collaboration domain of the edge server

图3 服务放置示意图

Fig.3 Schematic diagram of service placement

图4 边缘服务器部署和服务放置示意图

Fig.4 Schematic diagram of edge server deployment and service placement

图5 本文构建的网络模型

Fig.5 The network model constructed in this paper

图6 基站的位置分布

Fig.6 Location distribution of base stations

图7 基站的细粒度位置分布

Fig.7 Fine-grained location distribution of base stations

图8 边缘服务器的位置分布

Fig.8 Location distribution of edge servers

图9 边缘服务器协作域的分布

Fig.9 Distribution of edge server collaboration domains

图10 学习率对收益的影响

Fig.10 Impact of learning rate on revenue

图11 迭代次数对收益的影响

Fig.11 Impact of the number of iterations on revenue

图12 ES数量对不同方法性能的影响

Fig.12 Impact of the number of ES on the performance of different methods

图13 服务请求数量对收益影响

Fig.13 The impact of the number of service requests on revenue

图14 计算和存储资源对不同方法收益的影响

Fig.14 The impact of computing and storage resources on the benefits of different methods

参考文献 29

1	CHEN Y, ZHAO F J, LU Y G, et al. Dynamic task offloading for mobile edge computing with hybrid energy supply. Tsinghua Science and Technology, 2023, 28(3): 421- 432. doi: 10.26599/TST.2021.9010050
2	GHAZINOORY S, ROSHANDEL J, PARVIN F, et al. Smart city maturity models: a multidimensional synthesized approach. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2024, 14(1): e1516. doi: 10.1002/widm.1516
3	TAN T, ZHAO M, ZENG Z W. Joint offloading and resource allocation based on UAV-assisted mobile edge computing. ACM Transactions on Sensor Networks, 2022, 18(3): 1- 21.
4	XU W, YANG Z H, NG D W K, et al. Edge learning for B5G networks with distributed signal processing: semantic communication, edge computing, and wireless sensing. IEEE Journal of Selected Topics in Signal Processing, 2023, 17(1): 9- 39. doi: 10.1109/JSTSP.2023.3239189
5	HUA H C, LI Y T, WANG T H, et al. Edge computing with artificial intelligence: a machine learning perspective. ACM Computing Surveys, 2023, 55(9): 1- 35.
6	GUO C P, LIN Z Q, SONG J. A privacy protection approach in edge-computing based on maximized dnn partition strategy with energy saving. Journal of Cloud Computing, 2023, 12(1): 29. doi: 10.1186/s13677-023-00404-y
7	WU C R, PENG Q L, XIA Y N, et al. Towards cost-effective and robust AI microservice deployment in edge computing environments. Future Generation Computer Systems, 2023, 141, 129- 142. doi: 10.1016/j.future.2022.10.015
8	JIANG X H, HOU P, ZHU H B, et al. Dynamic and intelligent edge server placement based on deep reinforcement learning in mobile edge computing. Ad Hoc Networks, 2023, 145, 103172. doi: 10.1016/j.adhoc.2023.103172
9	LUO F, ZHENG S, DING W C, et al. An edge server placement method based on reinforcement learning. Entropy, 2022, 24(3): 317. doi: 10.3390/e24030317
10	LI Y Z, ZHOU A, MA X, et al. Profit-aware edge server placement. IEEE Internet of Things Journal, 2022, 9(1): 55- 67. doi: 10.1109/JIOT.2021.3082898
11	ZHANG C, ZHOU G H, LI J J, et al. A multi-access edge computing enabled framework for the construction of a knowledge-sharing intelligent machine tool swarm in industry 4.0. Journal of Manufacturing Systems, 2023, 66, 56- 70. doi: 10.1016/j.jmsy.2022.11.015
12	LIU L, FENG J, MU X Y, et al. Asynchronous deep reinforcement learning for collaborative task computing and on-demand resource allocation in vehicular edge computing. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(12): 15513- 15526. doi: 10.1109/TITS.2023.3249745
13	GUO F Y, TANG B, TANG M D, et al. Deep reinforcement learning-based microservice selection in mobile edge computing. Cluster Computing, 2023, 26(2): 1319- 1335. doi: 10.1007/s10586-022-03661-9
14	许小龙, 方子介, 齐连永, 等. 车联网边缘计算环境下基于深度强化学习的分布式服务卸载方法. 计算机学报, 2021, 44(12): 2382- 2405. doi: 10.11897/SP.J.1016.2021.02382
	XU X L, FANG Z J, QI L Y, et al. A deep reinforcement learning-based distributed service off loading method for edge computing empowered Internet of vehicles. Chinese Journal of Computers, 2021, 44(12): 2382- 2405. doi: 10.11897/SP.J.1016.2021.02382
15	REN D W, GUI X L, ZHANG K Y. Adaptive request scheduling and service caching for MEC-assisted IoT networks: an online learning approach. IEEE Internet of Things Journal, 2022, 9(18): 17372- 17386. doi: 10.1109/JIOT.2022.3157677
16	MOSTAFA G A, ALI S. A cost-efficient IoT service placement approach using whale optimization algorithm in fog computing environment. Expert Systems With Applications, 2022, 200, 117012. doi: 10.1016/j.eswa.2022.117012
17	XUE J B, WU Q Q, ZHANG H J. Cost optimization of UAV-MEC network calculation offloading: a multi-agent reinforcement learning method. Ad Hoc Networks, 2022, 136, 102981. doi: 10.1016/j.adhoc.2022.102981
18	REN J, LIU J N, ZHANG Y M, et al. An efficient two-layer task offloading scheme for MEC system with multiple services providers[C]//Proceedings of the IEEE Conference on Computer Communications. Washington D. C., USA: IEEE Press, 2022: 1519-1528.
19	HAZRA A, RANA P, ADHIKARI M, et al. Fog computing for next-generation Internet of Things: fundamental, state-of-the-art and research challenges. Computer Science Review, 2023, 48, 100549. doi: 10.1016/j.cosrev.2023.100549
20	WANG Y, TANG Z, HUANG A, et al. Placement of UAV-mounted edge servers for Internet of vehicles. IEEE Transactions on Vehicular Technology, 2024, 22, 1- 10.
21	GUO Y, WANG S G, ZHOU A, et al. User allocation-aware edge cloud placement in mobile edge computing. Software: Practice and Experience, 2020, 50(5): 489- 502. doi: 10.1002/spe.2685
22	WANG S G, GUO Y, ZHANG N, et al. Delay-aware microservice coordination in mobile edge computing: a reinforcement learning approach. IEEE Transactions on Mobile Computing, 2021, 20(3): 939- 951. doi: 10.1109/TMC.2019.2957804
23	HOU W J, WEN H, SONG H H, et al. Multiagent deep reinforcement learning for task offloading and resource allocation in cybertwin-based networks. IEEE Internet of Things Journal, 2021, 8(22): 16256- 16268. doi: 10.1109/JIOT.2021.3095677
24	ZHAO L R, ZHANG Y L, DANG Z H. PRD-MADDPG: an efficient learning-based algorithm for orbital pursuit-evasion game with impulsive maneuvers. Advances in Space Research, 2023, 72(2): 211- 230. doi: 10.1016/j.asr.2023.03.014
25	CHEN Y Y, LIN Y H, ZHENG Z W, et al. Preference-aware edge server placement in the Internet of Things. IEEE Internet of Things Journal, 2022, 9(2): 1289- 1299. doi: 10.1109/JIOT.2021.3079328
26	CHAKRABORTY S, DE D, MAZUMDAR K. DoME: dew computing based microservice execution in mobile edge using Q-learning. Applied Intelligence, 2023, 53(9): 10917- 10936. doi: 10.1007/s10489-022-04087-x
27	AGHAPOUR Z, SHARIFIAN S, TAHERI H. Task offloading and resource allocation algorithm based on deep reinforcement learning for distributed AI execution tasks in IoT edge computing environments. Computer Networks, 2023, 223, 109577. doi: 10.1016/j.comnet.2023.109577
28	WANG M, JIANG H, LI Y Z, et al. Location determination of hierarchical service facilities using a multi-layered greedy heuristic approach. Engineering Optimization, 2023, 55(8): 1422- 1436. doi: 10.1080/0305215X.2022.2086540
29	XU M R, NIYATO D, ZHANG H L, et al. Sparks of GPTs in edge intelligence for metaverse: caching and inference for mobile AIGC services[EB/OL]. [2023-09-10]. http://arxiv.org/abs/2304.08782.

[1]	张俊娜, 李天泽, 赵晓焱, 袁培燕. 一种基于DQN的去中心化优先级卸载策略[J]. 计算机工程, 2024, 50(9): 235-245.
[2]	石琼, 段辉, 师智斌. 基于深度强化学习的可信任务卸载方案[J]. 计算机工程, 2024, 50(8): 142-152.
[3]	周浚辉, 徐鹏, 孙胜利. 协同感知系统中一种基于信息年龄优化的服务策略[J]. 计算机工程, 2024, 50(8): 165-181.
[4]	张冀, 龚雯雯, 朵春红, 齐国梁. 面向多智能体与双层卸载的车联网卸载算法[J]. 计算机工程, 2024, 50(8): 182-197.
[5]	陈姣, 沈艳. 面向缓存机制的移动边缘计算任务卸载研究[J]. 计算机工程, 2024, 50(7): 194-203.
[6]	赵云涛, 肖俊杰, 李维刚, 熊雅婷. 基于改进PPYOLOE-R的信息码矫正研究[J]. 计算机工程, 2024, 50(6): 358-366.
[7]	曾耀平, 夏玉婷, 江伟伟, 刘月强. 加权能耗最小化的无人机辅助移动边缘计算策略研究[J]. 计算机工程, 2024, 50(2): 288-297.
[8]	杨建军, 唐东明, 李驹光, 肖宇峰. 基于改进人工蜂鸟算法的MEC任务卸载策略[J]. 计算机工程, 2024, 50(10): 291-301.
[9]	万昊楠, 吴飞, 尹玲. 基于自适应无人机数量的节时部署优化算法[J]. 计算机工程, 2024, 50(10): 302-312.
[10]	申秀雨, 姬伟峰, 李映岐, 吴玄. 面向边缘计算的TCA1C DDoS检测模型[J]. 计算机工程, 2024, 50(1): 198-205.
[11]	彭世明, 林士飏, 贾硕, 杨苗会. 基于负载预测的多目标优化任务卸载策略[J]. 计算机工程, 2024, 50(1): 206-215.
[12]	班玉琦, 段利国, 温昊宇, 李爱萍, 赵菊敏. 面向移动感知的计算卸载及资源分配策略研究[J]. 计算机工程, 2023, 49(8): 163-173.
[13]	蔡星娟, 郭彦亨, 赵天浩, 张文生. 基于进化多任务的边缘计算服务部署和任务卸载[J]. 计算机工程, 2023, 49(7): 1-9.
[14]	梅晶, 戴龙宝, 童钊, 邓昕, 王嘉珂. 资源约束下基于Lyapunov优化的自适应卸载算法[J]. 计算机工程, 2023, 49(7): 34-46.
[15]	李强, 仪晋辉, 杜婷婷, 王胜春. 移动边缘计算中基于A3C的依赖任务卸载与资源分配[J]. 计算机工程, 2023, 49(6): 42-52.

选择文件类型/文献管理软件名称

选择包含的内容