CHAIN： edge computing node placement algorithm based on overlapping domination

doi:10.11772/j.issn.1001-9081.2022081250

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (9): 2812-2818.DOI: 10.11772/j.issn.1001-9081.2022081250

• Advanced computing • Previous Articles Next Articles

CHAIN： edge computing node placement algorithm based on overlapping domination

Xuyan ZHAO¹^,²^,³, Yunhe CUI¹^,²^,³(), Chaohui JIANG¹^,²^,³, Qing QIAN⁴, Guowei SHEN¹^,²^,³, Chun GUO¹^,²^,³, Xianchao LI⁵

^1.College of Computer Science and Technology，Guizhou University，Guiyang Guizhou 550025，China
^2.Engineering Research Center of Ministry of Education for Text Computing and Cognitive Intelligence （Guizhou University），Guiyang Guizhou 550025，China
^3.State Key Laboratory of Public Big Data （Guizhou University），Guiyang Guizhou 550025，China
^4.School of Information，Guizhou University of Finance and Economics，Guiyang Guizhou 550025，China
^5.Guizhou Xiangming Technology Company Limited，Guiyang Guizhou 550000，China

Received:2022-08-25 Revised:2023-01-11 Accepted:2023-01-16 Online:2023-02-28 Published:2023-09-10
Contact: Yunhe CUI
About author:ZHAO Xuyan， born in 1998， M. S. candidate. His research interests include edge computing， edge server deployment.
JIANG Chaohui， born in 1965， M. S.， professor. His research interests include cloud computing， information security， database， software engineering.
QIAN Qing， born in 1986， Ph. D.， associate professor. Her research interests include multimedia security， multimedia forensics， information hiding.
SHEN Guowei， born in 1986， Ph. D.， professor. His research interests include big data， cyberspace security， high-performance network communication.
GUO Chun， born in 1986， Ph. D.， associate professor. His research interests include malware analysis， intrusion detection， data mining.
LI Xianchao， born in 1979， M. S. His research interests include data center， cloud computing， internet of things.
Supported by:
National Natural Science Foundation of China(62102111);Science and Technology Program of Guizhou Province(［2020］1Y267);Guizhou Province Youth Science and Technology Talents Development Project of Colleges and Universities （Qian Jiaohe KY ［2021］136）

CHAIN：基于重合支配的边缘计算节点放置算法

赵徐炎¹^,²^,³, 崔允贺¹^,²^,³(), 蒋朝惠¹^,²^,³, 钱清⁴, 申国伟¹^,²^,³, 郭春¹^,²^,³, 李显超⁵

^1.贵州大学计算机科学与技术学院, 贵阳 550025
^2.文本计算与认知智能教育部工程研究中心(贵州大学), 贵阳 550025
^3.公共大数据国家重点实验室(贵州大学), 贵阳 550025
^4.贵州财经大学信息学院, 贵阳 550025
^5.贵州翔明科技有限责任公司, 贵阳 550000

通讯作者: 崔允贺
作者简介:赵徐炎（1998—），男，陕西韩城人，硕士研究生，主要研究方向：边缘计算、边缘服务器部署
蒋朝惠（1965—），男，贵州贵阳人，教授，硕士，主要研究方向：云计算、信息安全、数据库、软件工程
钱清（1986—），女，贵州贵阳人，副教授，博士，CCF会员，主要研究方向：多媒体安全、多媒体取证、信息隐藏
申国伟（1986—），男，湖南邵阳人，教授，博士，主要研究方向：大数据、网络空间安全、高性能网络通信
郭春（1986—），男，贵州贵阳人，副教授，博士，主要研究方向：恶意软件分析、入侵检测、数据挖掘
李显超（1979—），男，贵州贵阳人，硕士，主要研究方向：数据中心、云计算、物联网。
基金资助:
国家自然科学基金资助项目(62102111);贵州省科技计划项目(［2020］1Y267);贵州省普通高等学校青年科技人才成长项目(黔教合KY字［2021］136)

Abstract

Abstract:

In edge computing， computing resources are deployed at edge computing nodes closer to end users， and selecting the appropriate edge computing node deployment location from the candidate locations can enhance the node capacity and user Quality of Service （QoS） of edge computing services. However， there is less research on how to place edge computing nodes to reduce the cost of edge computing. In addition， there is no edge computing node deployment algorithm that can maximize the robustness of edge services while minimizing the deployment cost of edge computing nodes under the constraints of QoS factors such as the delay of edge services. To address the above issues， firstly， the edge computing node placement problem was transformed into a minimum dominating set problem with constraints by building a model about computing nodes， user transmission delay， and robustness. Then， the concept of overlapping domination was proposed， so that the network robustness was measured on the basis of overlapping domination， and an edge computing node placement algorithm based on overlapping domination was designed， namely CHAIN （edge server plaCement algoritHm based on overlAp domINation）. Simulation results show that CHAIN can reduce the system latency by 50.54% and 50.13% compared to the coverage oriented approximate algorithm and base station oriented random algorithm， respectively.

Key words: edge computing, edge computing node placement, robustness, deployment cost, overlapping domination

摘要：

边缘计算将计算资源部署在离终端用户更近的边缘计算节点，从待选的位置中选择合适的边缘计算节点部署位置能提升边缘计算服务的节点容量以及用户服务质量（QoS）。然而，目前对于如何放置边缘计算节点以降低边缘计算成本的研究较少。此外，在边缘服务的时延等QoS因素的约束下，目前尚没有一种边缘计算节点部署算法能最大限度地提高边缘服务的鲁棒性同时最小化边缘节点部署成本。针对上述问题，首先，通过建立计算节点、用户传输时延和鲁棒性的模型将边缘计算节点放置问题转化为带约束条件的最小支配集问题；随后，提出重合支配的概念，基于重合支配衡量网络鲁棒性，设计了基于重合支配的边缘计算节点放置算法——CHAIN（edge server plaCement algoritHm based on overlApping domINation）。仿真实验结果表明，与面向覆盖的近似算法和面向基站的随机算法相比，CHAIN的系统时延降低了50.54%与50.13%。

关键词: 边缘计算, 边缘计算节点放置, 鲁棒性, 部署成本, 重合支配

CLC Number:

TP391

Xuyan ZHAO, Yunhe CUI, Chaohui JIANG, Qing QIAN, Guowei SHEN, Chun GUO, Xianchao LI. CHAIN： edge computing node placement algorithm based on overlapping domination[J]. Journal of Computer Applications, 2023, 43(9): 2812-2818.

赵徐炎, 崔允贺, 蒋朝惠, 钱清, 申国伟, 郭春, 李显超. CHAIN：基于重合支配的边缘计算节点放置算法[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2812-2818.

Figures/Tables 6

Fig. 1 Base station dominating set

Tab. 1 Experimental parameter setting

n	r_e/m	工作负载o	t/ms
60	200，250，300	999	10
70	200，250，300	3，5，8，10，12，999	10，15，20，25，30
80	200，250，300	999	10
90	200，250，300	999	10
100	200，250，300	999	10

Fig. 2 System delay comparison under different base stations and coverage radii

Fig. 3 Service robustness comparison under different base stations and coverage radii

Fig. 4 Delay variance comparison under different base stations and coverage radii

Fig. 5 Comparison of number of computing nodes

References 18

1	KIRAN N， PAN C Y， WANG S H， et al. Joint resource allocation and computation offloading in mobile edge computing for SDN based wireless networks［J］. Journal of Communications and Networks， 2020， 22（1）：1-11. 10.1109/jcn.2019.000046
2	宁振宇，张锋巍，施巍松. 基于边缘计算的可信执行环境研究［J］. 计算机研究与发展， 2019， 56（7）：1441-1453. 10.7544/issn1000-1239.2019.20180522
	NING Z Y， ZHANG F W， SHI W S. A study of using TEE on edge computing［J］. Journal of Computer Research and Development， 2019， 56（7）：1441-1453. 10.7544/issn1000-1239.2019.20180522
3	黄韬，刘江，汪硕，等. 未来网络技术与发展趋势综述［J］. 通信学报， 2021， 42（1）：130-150.
	HUANG T， LIU J， WANG S， et al. Survey of the future network technology and trend［J］. Journal on Communications， 2021， 42（1）：130-150.
4	LV Z H， XIU W Q. Interaction of edge-cloud computing based on SDN and NFV for next generation IoT［J］. IEEE Internet of Things Journal， 2020， 7（7）：5706-5712. 10.1109/jiot.2019.2942719
5	MAO Y Y， YOU C S， ZHANG J， et al. A survey on mobile edge computing： the communication perspective［J］. IEEE Communications Surveys and Tutorials， 2017， 19（4）：2322-2358. 10.1109/comst.2017.2745201
6	MACH P， BECVAR Z. Mobile edge computing： a survey on architecture and computation offloading［J］. IEEE Communications Surveys and Tutorials， 2017， 19（3）：1628-1656. 10.1109/comst.2017.2682318
7	TAKEDA A， KIMURA T， HIRATA K. Evaluation of edge cloud server placement for edge computing environments［C］// Proceedings of the 2019 IEEE International Conference on Consumer Electronics - Taiwan. Piscataway： IEEE， 2019：1-2. 10.1109/icce-tw46550.2019.8991970
8	ESHRAGHI N， LIANG B. Joint offloading decision and resource allocation with uncertain task computing requirement［C］// Proceedings of the 2019 IEEE International Conference on Computer Communications. Piscataway： IEEE， 2019：1414-1422. 10.1109/infocom.2019.8737559
9	LI Y Z， ZHOU A， MA X， al at. Profit-aware edge server placement［J］. IEEE Internet of Things Journal， 2022， 9（1）： 55-67. 10.1109/jiot.2021.3082898
10	WANG S G， ZHAO Y L， XU J L， et al. Edge server placement in mobile edge computing［J］. Journal of Parallel and Distributed Computing， 2019， 127：160-168. 10.1016/j.jpdc.2018.06.008
11	LIU Z， ZHANG J W， WU J Y. Joint optimization of server placement and content caching in mobile edge computing networks［C］// Proceedings of the 8th International Conference on Networks， Communication and Computing. New York： ACM， 2019：149-153. 10.1145/3375998.3376024
12	LEE S， LEE S， SHIN M K. Low cost MEC server placement and association in 5G networks［C］// Proceedings of the 2019 International Conference on Information and Communication Technology Convergence. Piscataway： IEEE， 2019：879-882. 10.1109/ictc46691.2019.8939566
13	CAO K， LI L Y， CUI Y G， et al. Exploring placement of heterogeneous edge servers for response time minimization in mobile edge-cloud computing［J］. IEEE Transactions on Industrial Informatics， 2021， 17（1）：494-503. 10.1109/tii.2020.2975897
14	WANG F T， HUANG X X， NIAN H F， et al. Cost-effective edge server placement in edge computing［C］// Proceedings of the 5th International Conference on Systems， Control and Communications. New York： ACM， 2019：6-10. 10.1145/3377458.3377461
15	LU D Y， QU Y B， WU F， et al. Robust server placement for edge computing［C］// Proceedings of the 2020 IEEE International Parallel and Distributed Processing Symposium. Piscataway： IEEE， 2020：285-294. 10.1109/ipdps47924.2020.00038
16	CUI G M， HE Q， XIA X Y， et al. Robustness-oriented k edge server placement［C］// Proceedings of the 20th IEEE/ACM International Symposium on Cluster， Cloud and Internet Computing. Piscataway： IEEE， 2020：81-90. 10.1109/ccgrid49817.2020.00-85
17	YANG S， LI F， SHEN M， et al. Cloudlet placement and task allocation in mobile edge computing［J］. IEEE Internet of Things Journal， 2019， 6（3）：5853-5863. 10.1109/jiot.2019.2907605
18	赵兴兵，赵一帆，李波，等. 基于时延与能量感知的边缘服务器放置方法［J］. 计算机工程， 2021， 47（11）：37-43.
	ZHAO X B， ZHAO Y F， LI B， al at. Edge server placement method based on time delay and energy awareness［J］. Computer Engineering， 2021， 47（11）：37-43.

[1]	Xuebin CHEN, Zhiqiang REN, Hongyang ZHANG. Review on security threats and defense measures in federated learning [J]. Journal of Computer Applications, 2024, 44(6): 1663-1672.
[2]	Junna ZHANG, Xinxin WANG, Tianze LI, Xiaoyan ZHAO, Peiyan YUAN. Task offloading method based on dynamic service cache assistance [J]. Journal of Computer Applications, 2024, 44(5): 1493-1500.
[3]	Xiaoyan ZHAO, Wei HAN, Junna ZHANG, Peiyan YUAN. Collaborative offloading strategy in internet of vehicles based on asynchronous deep reinforcement learning [J]. Journal of Computer Applications, 2024, 44(5): 1501-1510.
[4]	Weina DONG, Jia LIU, Xiaozhong PAN, Lifeng CHEN, Wenquan SUN. High-capacity robust image steganography scheme based on encoding-decoding network [J]. Journal of Computer Applications, 2024, 44(3): 772-779.
[5]	Jintao RAO, Zhe CUI. Electronic voting scheme based on SM2 threshold blind signature [J]. Journal of Computer Applications, 2024, 44(2): 512-518.
[6]	Ming ZHANG, Le FU, Haifeng WANG. Relay control model for concurrent data flow in edge computing [J]. Journal of Computer Applications, 2024, 44(12): 3876-3883.
[7]	Jie HUANG, Ruizi WU, Junli LI. Efficient adaptive robustness optimization algorithm for complex networks [J]. Journal of Computer Applications, 2024, 44(11): 3530-3539.
[8]	Han WANG, Yuan WAN, Dong WANG, Yiming DING. Robust weight matrix combination selection method of broad learning system [J]. Journal of Computer Applications, 2024, 44(10): 3032-3038.
[9]	Wanzhen CHEN, En ZHANG, Leiyong QIN, Shuangxi HONG. Privacy-preserving federated learning algorithm based on blockchain in edge computing [J]. Journal of Computer Applications, 2023, 43(7): 2209-2216.
[10]	Xiaolin LI, Yusang JIANG. Task offloading algorithm for UAV-assisted mobile edge computing [J]. Journal of Computer Applications, 2023, 43(6): 1893-1899.
[11]	Tengfei CAO, Yanliang LIU, Xiaoying WANG. Edge computing and service offloading algorithm based on improved deep reinforcement learning [J]. Journal of Computer Applications, 2023, 43(5): 1543-1550.
[12]	Jian GAO, Zhi LI, Bin FAN, Chuanxian JIANG. Efficient robust zero-watermarking algorithm for 3D medical images based on ray-casting sampling and quaternion orthogonal moment [J]. Journal of Computer Applications, 2023, 43(4): 1191-1197.
[13]	Mengting GE, Minghua WAN. Feature extraction model based on neighbor supervised locally invariant robust principal component analysis [J]. Journal of Computer Applications, 2023, 43(4): 1013-1020.
[14]	Xianbojun FAN, Lijia CHEN, Shen LI, Chenlu WANG, Min WANG, Zan WANG, Mingguo LIU. Robust joint modeling and optimization method for visual manipulators [J]. Journal of Computer Applications, 2023, 43(3): 962-971.
[15]	Mengdi SUN, Zhonggui SUN, Xu KONG, Hongyan HAN. Design of guided adaptive mathematical morphology for multimodal images [J]. Journal of Computer Applications, 2023, 43(2): 560-566.

CHAIN： edge computing node placement algorithm based on overlapping domination

CHAIN：基于重合支配的边缘计算节点放置算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 18

Related Articles 15

Recommended Articles

Metrics