摘要
在边缘计算环境中,为用户匹配合适的服务器是一个关键问题,可以有效提升服务质量。文中将边缘用户分配问题转换为一个受距离和服务器资源约束的二分图匹配问题,并将其建模为一个0-1整数规划问题进行优化。在离线状态下,基于精确式算法的优化模型可以求得最优分配策略,但其求解时间过长,无法处理规模较大的数据,不适用于现实服务环境。因此,提出了基于启发式策略的在线分配方法,以在时间有限的情况下优化用户-服务器的分配。实验结果显示,基于近邻启发式的在线方法的竞争比能够接近100%,可以在可接受的时间范围内求得较优的分配解。同时,近邻启发式方法比其他基础启发式方法的表现更优秀。
In edge computing environment,matching suitable servers for users is a key issue,which can effectively improve the quality of service.In this paper,the edge user assignment(EUA)problem is converted into a bipartite graph matching problem constrained by distance and server resources,and it is modeled as a 0-1 integer programming problem for optimal assignment solution.In the offline state,the optimization model based on exact algorithm can obtain the optimal assignment strategy,but its solution time is too long,and it cannot process large-scale of data,which is not suitable for the real service environment.Therefore,the online user assignment method based on heuristic strategy is proposed to optimize the user-server assignment under limited time.The experimental results show that the competitive ratio obtained by Proximal Heuristic online method(PH)can reach close to 100%,and can obtain a better assignment solution within an acceptable time.At the same time,the online PH method performs better than other basic heuristic methods.
作者
唐文君
刘岳
陈荣
TANG Wen-jun;LIU Yue;CHEN Rong(Department of Information Science and Technology,Dalian Maritime University,Dalian,Liaoning 116026,China)
出处
《计算机科学》
CSCD
北大核心
2021年第1期58-64,共7页
Computer Science
基金
国家自然科学基金(61672122,61902050,61602077)
中央高校基本科研业务费专项基金(3132019355)
赛尔创新项目(NGII20190627)
中国博士后科学基金(2020M670736)。
关键词
边缘计算
计算卸载
边缘用户分配
二分图匹配
启发式方法
Edge computing
Computing offloading
Edge user allocation
Bipartite graph matching
Heuristic method
