用户公平保障的边缘服务缓存与任务卸载算法

Fairness-aware Service Caching and Task Offloading with Cooperative Mobile Edge Computing

在边缘服务器中缓存服务可缩短请求响应时间,提升用户体验。现有研究主要从整体上优化系统性能,例如最大化系统吞吐量,而无法保障个体用户请求异构服务的公平性。针对用户异构计算任务的不公平服务问题,研究边缘协同计算中的服务缓存和任务卸载策略,基于最大最小公平原则,构建了一个最大化最小服务完成率问题,并证明了其NP难解性。为此,利用线性松弛将原问题从0-1整数规划转化为线性规划,设计了一种近似比为M S/N(S-2 ln S)的随机舍入算法,其中S为边缘服务器数,N为服务数,M为终端设备数。同时,基于优先缓存和卸载完成率最小的服务及其任务,提出了一种快速高效的贪心算法。实验结果表明,与已有最大化系统吞吐量算法相比,提出的随机舍入算法和贪心算法将最小服务完成率分别提升至少44.1%和90.6%,并且其额外的系统吞吐量损失分别不超过22.4%和27.0%。

Caching services in edge servers can reduce the response time of user requests and improve user experience.Most of existing works focus on optimizing the overall system performance,i.e.,maximizing the system throughput,which cannot gua-rantee the user fairness in requesting heterogeneous services.To fill this gap,this paper investigates fairness-aware joint service caching and task offloading strategy with cooperative edge computing.A minimum service completion rate maximization problem is formulated based on max-min fairness principle,which is proved to be NP-hard.A randomized rounding algorithm with M S/N(S-2 ln S)-approximation ratio is proposed by transforming the original problem from 0-1 integer programming into linear programming using linear relaxation,where S,N and M are the numbers of edge servers,services and end devices,respectively.Moreover,a fast and efficient greedy algorithm is proposed by caching the service with the minimum completion rate and offloa-ding its corresponding tasks preferentially.Extensive simulation results demonstrate that not only the minimum service completion rate can be improved by at least 44.1%and 90.6%by our two algorithms,but also the extra loss of system throughput is no more than 22.4%and 27.0%,respectively,compared with the existing algorithms for maximizing system throughput.