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

作者：吴纯; 陈龙; 孙一飞; 武继刚^*

来源：计算机科学, 2023, 50(S2): 746-753.

• 边缘计算
• 服务缓存
• 任务卸载
• 最大最小公平
• 随机舍入

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

• 单位
  广东工业大学