计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (10): 248-257.doi: 10.11896/jsjkx.220900211

• 计算机网络 • 上一篇    下一篇

基于谱聚类的边缘服务器放置算法

郭迎亚1,2, 王丽娟1,2, 耿海军3   

  1. 1 福州大学计算机与大数据学院 福州350108
    2 福州大学网络计算和智能信息处理重点实验室 福州350108
    3 山西大学自动化与软件学院 太原030006
  • 收稿日期:2022-09-22 修回日期:2022-11-28 出版日期:2023-10-10 发布日期:2023-10-10
  • 通讯作者: 耿海军(ghj123025449@163.com)
  • 作者简介:(guoyy@fzu.edu.cn.)
  • 基金资助:
    国家自然科学基金(62002064,62072109);福建省自然科学基金(2020J05110)

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)

2015

摘要： 随着物联网(IoT)和 5G 技术的快速发展,移动边缘计算以其低访问延迟、低带宽成本和低能源消耗的优点引起了工业界和学术界的广泛关注。在移动边缘计算中,边缘服务器为移动端用户的请求提供服务,其放置位置对边缘计算性能和用户体验具有重要影响。目前边缘服务器的放置算法只考虑基站的地理位置,而缺乏对基站连接的用户数目因素的考虑。因此在实际用户分布不均的情况下,现有算法得到的服务器放置位置导致用户平均访问延迟较大。为了更好地解决上述问题,提出了基于谱聚类的延迟最小化边缘服务器放置算法LAMP。该算法在考虑边缘服务器放置位置时,不仅考虑了基站的地理位置,而且考虑了不同基站连接的用户数目这一重要参数,能够有效地降低用户的平均访问时延,同时实现边缘服务器的工作负载均衡。在仿真实验中,使用了上海电信的真实基站数据集来测试LAMP算法的性能。大量的实验结果表明,在用户访问延迟方面,LAMP算法的性能比传统的K-means 算法提高了37.9%。在负载均衡方面,LAMP算法的性能与K-means算法相比最大可提高82.85%。LAMP算法在降低访问延迟和平衡边缘服务器工作负载方面均表现出了优越的性能。

关键词: 移动边缘计算, 边缘服务器放置, 用户分布, 谱聚类算法, 访问时延, 工作负载

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

中图分类号: 

  • 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发