Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (10): 248-257.doi: 10.11896/jsjkx.220900211

• Computer Network • Previous Articles     Next Articles

Edge Server Placement Algorithm Based on Spectral Clustering

GUO Yingya1,2, WANG Lijuan1,2, GENG Haijun3   

  1. 1 College of Computer and Data Science,Fuzhou University,Fuzhou 350108,China
    2 Fujian Key Laboratory of Network Computing and Intelligent Information Processing,Fuzhou University,Fuzhou 350108,China
    3 School of Automation and Software Engineering,Shanxi University,Taiyuan 030006,China
  • Received:2022-09-22 Revised:2022-11-28 Online:2023-10-10 Published:2023-10-10
  • About author:GUO Yingya,born in 1990,Ph.D,associate professor,master supervisor,is a member of China Computer Federation.Her main research interests include computer network,traffic engineering and routing optimization.GENG Haijun,born in 1983,Ph.D,associate professor,master supervisor,is a member of China Computer Federation.His main research interests include computer network and multi-path routing.
  • Supported by:
    National Natural Science Foundation of China(62002064,62072109) and Natural Science Foundation of Fujian Province,China(2020J05110).

PDF (PC)

2020

Abstract: With the rapid development of the Internet of Things(IoT) and 5G networks,mobile edge computing has attracted widespread attention from industry and academia for its low access latency,low bandwidth costs,and low energy consumption.In mobile edge computing,edge servers provide services for mobile user requests,and the placement of edge servers has an important impact on edge computing performance and user experience.At present,the placement algorithm of edge servers only considers the geographical location of server placement,and lacks the consideration of the number of users connected to the base station.Therefore,in the case of uneven distribution of actual users,the average user access delay caused by the server placement position obtained by the existing algorithm is large.In order to better solve the above problems,this paper proposes a latency minimization edge server placement algorithm based on spectral clustering.When solving the problem of edge server placement,the algorithm not only considers the geographical location of the base station,but also takes into account the important parameter of the number of users connected to different base stations,which can effectively reduce the average access latency of users and make the workload of each edge server more balanced at the same time.In the simulation experiment,this paper uses the real base station dataset of Shanghai Telecom to test the performance of the proposed server placement algorithm.Simulation experiment results show that the user-distributed access delay minimization edge server placement algorithm has significant advantages in solving the edge server placement problem.In terms of access latency,the performance of LAMP algorithm is increased by 37.9% compared with K-means algorithm.Compared with the K-means algorithm,the performance of the LAMP algorithm can be improved by up to 82.85% in terms of load balancing.The LAMP algorithm exhibits superior performance in reducing access latency and balancing edge server workloads.

Key words: Mobile edge computing, Edge server placement, User distribution, Spectral clustering, Access delay, Workload balancing

CLC Number: 

  • TP393
[1]SHI W S,ZHANG X Z,WANG Y F,et al.Edge Computing:State-of-the-Art and Future Directions [J].Journal of Computer Research and Development,2019,56(1):69-89.
[2]QU Z,YE B,CHEN G,et al.State-of-the-art Survey on Re-source Optimization in Edge Computing[J].Big Data Research,2019,5(2):17-33.
[3]LI Z Y,WANG Q,CHEN Y F,et al.A Survey of Task Offloa-ding Research in Vehicle Edge Computing Environment [J].Chinese Journal of Computers,2021,44(5):963-982.
[4]LI S Y,LIU H,ZHANG Z Y,et al.A Smart Home-orientedEdge Computing Bandwidth Resource Allocation Method and System,China,CN113507519A[P].2021-10-15.
[5]LI Y,ZHOU A,MA X,et al.Profit-aware Edge Server Place-ment [J].IEEE Internet of Things Journal,2023,9(1):55-67.
[6]ZHOU Y Z,ZHANG D.Near-end Cloud Computing:Opportunities and Challenges in the Post-cloud Computing Era [J].Chinese Journal of Computers,2019,42(4):677-700.
[7]LIU Y,WANG T,PENG S L,et al.Edge-based FederatedLearning Model Cleaning and Device Clustering Methods [J].Chinese Journal of Computers,2021,44(12):2514-2528.
[8]SHI W S,SUN H,CAO J,et al.Edge Computing:An emerging Computing Model for the Internet of Everything Era [J]. Journal of Computer Research and Development,2017,54(5):907-924.
[9]ZHANG Y L,LIANG Y Z,YIN M J,et al.A Review of Research on Computing Offload Schemes in Mobile Edge Computing [J].Chinese Journal of Computers,2021,44(12):2406-2430.
[10]XIANG H,XU X,ZHENG H,et al.An Adaptive CloudletPlacement Method for Mobile Applications over GPS Big Data[C]//2016 IEEE Global Communications Conference(GLOBECOM).2016:1-6.
[11]ZHANG Y,WANG K,ZHOU Y,et al.Enhanced AdaptiveCloudlet Placement Approach for Mobile Application on Spark[C]//Security and Communication Networks.2018:1-12.
[12]FAJARDO J O,LIBERAL F,GIANNOULAKIS I,et al.Intro-ducing Mobile Edge Computing Capabilities through Distributed 5G Cloud Enabled Small Cells [J].Mobile Networks & Applications,2016,21(4):564-574.
[13]MA L,WU J,CHEN L,et al.DOTA:Delay Bounded OptimalCloudlet Deployment and User Association in WMANs[C]//2017 17th IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing(CCGRID).2017:196-203.
[14]FAN Q,ANSARI N.Cost Aware Cloudlet Placement for BigData Processing at the Edge[C]//Proceedings of the 2017 IEEE International Conference on Communications(ICC).2017:1-6.
[15]YANG S,LI F,SHEN M,et al.Cloudlet Placement and TaskAllocation in Mobile Edge Computing [J].IEEE Internet of Things Journal,2019,6(3):5853-5863.
[16]ZENG F,REN Y,DENG X,et al.Cost-Effective Edge Server Placement in Wireless Metropolitan Area Networks [J].IEEE Internet of Things Journal,2019,19(1):5853-5863.
[17]SANTOYO-GONZÁLEZ A,CERVELLÓ-PASTOR C.EdgeNodes Infrastructure Placement Parameters for 5G Networks[C]//2018 IEEE Conference on Standards for Communications and Networking(CSCN),2018:1-6.
[18]DAYARATHNA M,WEN Y,FAN R.Data Center EnergyConsumption Modeling:A Survey[J].IEEE Communications Surveys Tutorials,2016,18(1):732-794.
[19]WANG S,LIU Z,ZHENG Z,et al.Particle Swarm Optimization for Energy-aware Virtual Machine Placement Optimization in Virtualized Data Centers[C]//2013 International Conference on Parallel and Distributed Systems.2013:102-109.
[20]WANG S,ZHAO Y,XU J,et al.Edge Server Placement in Mo-bile Edge Computing[J].Journal of Parallel and Distributed Computing,2019,127:160-168.
[21]GUO Y,WANG S,ZHOU A,et al.User Allocation-aware Edge Cloud Placement in Mobile Edge Computing [J].Software:Practice and Experience,2020,50(5):489-502.
[22]WANG S,GUO Y,ZHANG N,et al.Delay-Aware Microservice Coordination in Mobile Edge Computing:A Reinforcement Learning Approach [J].IEEE Transactions on Mobile Computing,2021,20(3):939-953.
[23]LIANG Y,LIU H,DINESH R.Optimal Placement and Configu-ration of Roadside Units in Vehicular Networks[C]//Procee-dings of the 2012 IEEE 75th Vehicular Technology Conference(VTC Spring).2012:1-6.
[24]ASLAM B,AMJAD F,ZOU C C.Optimal roadside units placement in urban areas for vehicular networks[C]//2012 IEEE Symposium on Computers and Communications.2012:423-429.
[25]TRULLOLS O,FIORE M,CASETTI C,et al.Planning Road-side Infrastructure for Information Dissemination in Intelligent Transportation Systems [J].Computer Communications,2010,33(4):432-442.
[26]BALOUCHZAHI N M,FATHY M,AKBARI A.Optimal Road Side Units Placement Model Based on Binary Integer Programming for Efficient Traffic Information Advertisement and Discovery in Vehicular Environment[C]//IET Intelligent Transport Systems.2015:851-861.
[27]WANG Z H,ZHENG J,WU Y,et al.A Centrality-based RSU Deployment Approach for Vehicular Ad Hoc Networks[C]//Proceedings of the 2017 IEEE International Conference on Communications(ICC).2017:1-5.
[28]ZHANG R,YAN F,XIA W,et al.An Optimal Roadside UnitPlacement Method for Vanet Localization[C]//2017 IEEE Global Communications Conference(GLOBECOM 2017).2017:1-6.
[29]XU X L,FANG Z J,QI L Y,et al.Distributed Service Offload Method Based on Deep Reinforcement Learning in the Edge Computing Environment of the Internet of Vehicles [J].Chinese Journal of Computers,2021,44(12):2382-2405.
[30]PREMSANKAR G,GHADDAR B,FRANCESCO M,et al.Efficient Placement of Edge Computing Devices for Vehicular Applications in Smart Cities[C]//2018 IEEE/IFIP Network Ope-rations and Management Symposium(NOMS 2018).2018:1-9.
[31]CESELLI A,PREMOLI M,SECCI S.Cloudlet Network Design Optimization[C]//2015 IFIP Networking Conference.2015:1-9.
[32]SHI W,CAO J,ZHANG Q,et al.Edge Computing:Vision and Challenges [J].IEEE Internet of Things Journal,2016,3(5):637-646.
[33]DASHTI S E,RAHMANI A M.Dynamic VMs placement for energy efficiency by PSO in cloud computing [J].Journal of Experimental & Theoretical Artificial Intelligence,2016,28:97-112.
[34]JIA M,CAO J,LIANG W.Optimal Cloudlet Placement andUser to Cloudlet Allocation in Wireless Metropolitan Area Networks [J].IEEE Transactions on Cloud Computing,2017,5(4):725-737.
[35]CHEN X,JIAO L,LI W,et al.Efficient Multi-User Computation Offloading for Mobile-Edge Cloud Computing [J].IEEE/ACM Transactions on Networking,2016,24(5):2795-2808.
[36]MANASVI G,CHAKRABORTY A,MANOJ B S.Social Net-work Aware Dynamic Edge Server Placement for Next-Generation Cellular Networks[C]//2020 International Conference on COMmunication Systems & NETworkS(COMSNETS).2020:499-502.
[37]MARK C,NIYATO D,CHEN-KHONG T.Evolutionary Optimal Virtual Machine Placement and Demand Forecaster for Cloud Computing[C]//2011 IEEE International Conference on Advanced Information Networking and Applications.2011:348-355.
[38]XU Z,LIANG W,XU W,et al.Capacitated Cloudlet Placements in Wireless Metropolitan Area Networks[C]//Proceedings of the 2015 IEEE 40th Conference on Local Computer Networks(LCN).2015:570-578.
[39]MENG J,SHI W,TAN H,et al.Cloudlet Placement and Minimum-delay Routing in Cloudlet Computing[C]//Proceedings of the 2017 3rd International Conference on Big Data Computing and Communications(BIGCOM).2017:297-304.
[40]WAGSTAFF K L,CLAIRE C,SETH R,et al.Constrained K-means Clustering with Background Knowledge[C]//ICML.2001.
[41]WANG G,ZHAO Y,HUANG J,et al.A K-means-based Net-work Partition Algorithm for Controller Placement in Software Defined Network[C]//2016 IEEE International Conference on Communications(ICC).2016:1-6.
[42]CUI G,HE Q,XIA X,et al.Robustness-oriented k Edge Server Placement[C]//2020 20th IEEE/ACM International Sympo-sium on Cluster,Cloud and Internet Computing(CCGRID).2020:81-90.
[43]FAN Q,ANSARI N.On Cost Aware Cloudlet Placement forMobile Edge Computing [J].IEEE/CAA Journal of Automatica Sinica,2019,6(4):926-937.
[44]GUO F,TANG B.Mobile Edge Server Placement Method Based on User Latency-aware [J].Computer Science,2021,48(1):103-110.
[45]ZHAO X B,ZHAO Y F,LI B,et al.Edge Server Placement Method Based on Latency and Energy Perception [J].Computer Engineering,2021,47(11):37-43.
[46]ZHANG P C,WEI X M,JIN H Y.Dynamic QoS Optimization Based on Federated Learning Under Mobile Edge Computing [J].Chinese Journal of Computers,2021,44(12):2431-2446.
[47]HUANG D,WANG C,WU J,et al.Ultra-Scalable SpectralClustering and Ensemble Clustering [J].IEEE Transactions on Knowledge and Data Engineering,2020,32(6):1212-1226.
[48]CHEN W,SONG Y,BAI H,et al.Parallel Spectral Clustering in Distributed Systems [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(3):568-586.
[49]LI Z,WU X,CHANG S.Segmentation Using Superpixels:A Bipartite Graph Partitioning Approach[C]//2012 IEEE Confe-rence on Computer Vision and Pattern Recognition.2012:789-796.
[1] LIU Xingguang, ZHOU Li, ZHANG Xiaoying, CHEN Haitao, ZHAO Haitao, WEI Jibo. Edge Intelligent Sensing Based UAV Space Trajectory Planning Method [J]. Computer Science, 2023, 50(9): 311-317.
[2] LIN Xinyu, YAO Zewei, HU Shengxi, CHEN Zheyi, CHEN Xing. Task Offloading Algorithm Based on Federated Deep Reinforcement Learning for Internet of Vehicles [J]. Computer Science, 2023, 50(9): 347-356.
[3] ZHANG Naixin, CHEN Xiaorui, LI An, YANG Leyao, WU Huaming. Edge Offloading Framework for D2D-MEC Networks Based on Deep Reinforcement Learningand Wireless Charging Technology [J]. Computer Science, 2023, 50(8): 233-242.
[4] CHEN Xuzhan, LIN Bing, CHEN Xing. Stackelberg Model Based Distributed Pricing and Computation Offloading in Mobile Edge Computing [J]. Computer Science, 2023, 50(7): 278-285.
[5] LEI Xuemei, LIU Li, WANG Qian. MEC Offloading Model Based on Linear Programming Relaxation [J]. Computer Science, 2023, 50(6A): 211200229-5.
[6] CHEN Che, ZHENG Yifeng, YANG Jingmin, YANG Liwei, ZHANG Wenjie. Dynamic Energy Optimization Strategy Based on Relay Selection and Queue Stability [J]. Computer Science, 2023, 50(6A): 220100082-8.
[7] CHEN Yipeng, YANG Zhe, GU Fei, ZHAO Lei. Resource Allocation Strategy Based on Game Theory in Mobile Edge Computing [J]. Computer Science, 2023, 50(2): 32-41.
[8] ZHENG Hongqiang, ZHANG Jianshan, CHEN Xing. Deployment Optimization and Computing Offloading of Space-Air-Ground Integrated Mobile Edge Computing System [J]. Computer Science, 2023, 50(2): 69-79.
[9] XU Xia, ZHANG Hui, YANG Chunming, LI Bo, ZHAO Xujian. Fair Method for Spectral Clustering to Improve Intra-cluster Fairness [J]. Computer Science, 2023, 50(2): 158-165.
[10] ZHANG Ximei, XIE Bin, MI Jusheng, XU Tongtong, ZHANG Yiling. Adaptive Spectral Clustering Algorithm Combining Shared Nearest Neighbors and Manifold Distance [J]. Computer Science, 2023, 50(10): 59-70.
[11] YU Bin, LI Xue-hua, PAN Chun-yu, LI Na. Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning [J]. Computer Science, 2022, 49(7): 248-253.
[12] LI Meng-fei, MAO Ying-chi, TU Zi-jian, WANG Xuan, XU Shu-fang. Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient [J]. Computer Science, 2022, 49(7): 271-279.
[13] FANG Tao, YANG Yang, CHEN Jia-xin. Optimization of Offloading Decisions in D2D-assisted MEC Networks [J]. Computer Science, 2022, 49(6A): 601-605.
[14] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[15] XIE Wan-cheng, LI Bin, DAI Yue-yue. PPO Based Task Offloading Scheme in Aerial Reconfigurable Intelligent Surface-assisted Edge Computing [J]. Computer Science, 2022, 49(6): 3-11.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.