基于缓存优化的移动边缘计算资源分配策略

司强毅 陈祎鹏 杨哲

摘 要：移动边缘计算研究中，边缘服务器通过缓存任务数据可以有效节约计算资源，但如何分配缓存资源解决边缘服务器的竞争关系，以及能耗和效益问题，达到系统性能最优是一个NP难问题。为此提出基于缓存优化的在线势博弈资源分配策略OPSCO（online potential-game strategy based on cache optimization），采用新的緩存替换策略CASCU（cache allocation strategy based on cache utility），最大化缓存的效用。通过优化边缘服务器的效益指示函数，将缓存替换代价等因素与李雅普诺夫优化、势博弈以及EWA（exponential weighting algorithm）算法结合，对边缘服务器的竞争关系建模，进行势博弈相关证明和分析。仿真结果表明，OPSCO相比于其他资源分配策略，可以明显提升任务完成率和缓存效用，并降低设备能耗和时间开销，解决了移动边缘计算在线缓存场景中的资源分配以及数据缓存问题。

关键词：移动边缘计算； 资源分配； 缓存优化； 势博弈； 李雅普诺夫优化

中图分类号：TP393   文献标志码：A

文章编号：1001-3695（2024）03-025-0818-06

doi：10.19734/j.issn.1001-3695.2023.07.0325

Resource allocation strategy for mobile edge computingbased on cache optimization

Si Qiangyi1， Chen Yipeng2， Yang Zhe2

（1.Information Construction & Management Center， Suzhou City University， Suzhou Jiangsu 215104， China; 2.School of Computer Science & Technology， Soochow University， Suzhou Jiangsu 215006， China）

Abstract：In mobile edge computing research， the edge server can effectively save computing resources by caching task data. But how to allocate cache resources to solve the competitive relationship between edge servers， as well as energy consumption and efficiency issues， and achieve optimal system performance is a NP-hard problem. Therefore， this paper proposed an online potential-game resource allocation strategy OPSCO based on cache optimization， using a new cache replacement strategy CASCU to maximize the utility of the cache. By optimizing the efficiency indicator function of edge servers， combining factors such as cache replacement cost with Lyapunov optimization， potential game， and EWA algorithm， it modeled the competitive relationship of edge servers， and conducted potential game related proofs and analyses. The simulation results show that compared with other resource allocation strategies， OPSCO can significantly improve the task completion rate and cache utility， reduce equipment energy consumption and time overhead， and solve the resource allocation and data cache problems in mobile edge computing online cache scenarios.

Key words：mobile edge computing; resource allocation; cache optimization; potential game; Lyapunov optimization

0 引言

随着通信技术以及智能设备的发展，移动设备上需要完成的计算密集型任务越来越多，这些任务的数据量和计算量大，且对时延敏感［1］。受到电池容量和计算能力的限制，移动设备一般无法独立完成任务，于是出现了移动边缘计算（mobile edge computing，MEC）框架［2～5］。在MEC中，移动设备可以将计算密集型任务卸载至边缘服务器进行计算。然而边缘服务器的计算资源也是有限的，且边缘服务器之间存在任务竞争关系。因此如何制定有效的资源分配策略来提升整体性能，是MEC研究中的一个关键问题［6～10］。一般来说，边缘服务器都拥有一定的缓存资源，可以提前对任务数据进行缓存，从而提升性能。但目前利用边缘服务器缓存提升MEC性能的研究相对较少［11～15］。因为，利用缓存设计资源分配策略时存在许多挑战，包括缓存替换、信息不完全、多目标优化等问题。资源分配策略需要确定边缘服务器接收哪些任务，从而能最大化MEC系统的性能，这是一个NP-hard问题［14］。

本文提出了一种基于缓存优化的在线势博弈资源分配策略（online potential-game strategy based on cache optimization，OPSCO），使用势博弈结合在线学习的方式求解近似最优解。同时针对在线缓存场景，结合李雅普诺夫优化和缓存函数提升策略性能。本文主要工作和贡献如下：

a）提出了一种缓存替换策略，考虑了数据传输成本、缓存替换代价等因素，使得任务数据可以高效存储在边缘服务器缓存中，从而最大化缓存的效用。

b）基于缓存替换策略，优化了边缘服务器的效益指示函数，将缓存替换代价等因素与李雅普诺夫优化、势博弈以及在线更新算法进行结合，推导出相应的目标函数。然后对边缘服务器的竞争关系建模，进行势博弈相关证明和分析。最后结合多种优化方法构造OPSCO策略，进一步提高系统性能。

c）最后通过仿真实验对OPSCO的效果进行验证，与多种基准方法进行对比，结果表明，OPSCO均可以达到较好的优化效果。

1 相关工作

在线缓存MEC场景中，可以使用边缘服务器的缓存对计算任务进行加速。Chen等人［16］利用位置感知用户的偏好，提出了二进制缓存布局、边缘计算资源和带宽分配的联合优化，可以有效节省能耗。Wang等人［17］研究了一种基于相似性的车辆网络缓存策略，并采用改进的分枝定界算法来获得最优卸载决策和计算资源分配策略。Chen等人［18］考虑了蜂窝网络中计算卸载和任务缓存的联合优化，允许用户主动缓存或卸载服务器上的任务，有效降低了系统成本。Zhou等人［19］根据联盟博弈和凸优化定理开发一种交替优化算法，可以实现更低的网络延迟。Zhang等人［20］考虑了双向计算任务模型，每个任务都通过三种机制提供服务，即具有本地缓存的本地计算、没有本地缓存的局部计算和移动边缘计算服务器上的计算。仿真表明，其在带宽性能和时间效率方面均有提升。这些研究工作利用边缘服务器上的缓存提升整体MEC性能，构造了相应的资源分配策略，但主要针对任务完成率和能耗进行优化，未考虑边缘服务器的资源竞争问题。

也有部分研究者将博弈论用于解决资源竞争问题。Yang等人［21］引入博弈论以优化区块链网络中边缘计算服务器和用户的利益，提出了基于不同定价方法和不同缓存奖励方法的四种算法。Wu等人［22］基于Hedonic博弈，提出了一种动態联盟算法，以引导每个成员在每个时间段，从其自身的利润角度出发，加入或退出联盟，可以有效提高利润。以上研究将博弈论用于在线缓存场景，解决边缘服务器之间的竞争问题，但未能同时对任务完成率、能耗以及边缘服务器效益进行较好的优化。

2 系统模型

2.1 网络模型

图1为本文的在线缓存MEC网络模型，移动设备的任务数据可以缓存在边缘服务器上。边缘服务器中存在一个任务队列，任务会动态到来，同时需要对缓存任务集进行分配。在缓存优化的基础上，结合李雅普诺夫优化、势博弈以及在线更新算法构建了资源分配策略。因此本文提出的OPSCO中包含多个部分，其中缓存替换策略CASCU进行缓存优化，基于缓存优化的博弈分配策略GASCO（game allocation strategy based on cache optimization）负责处理边缘服务器之间的竞争问题，在线更新算法EWA提升整体任务完成率。其中缓存优化包括缓存价值的评估、流行任务的发现以及缓存替换惩罚的设计，这些因素共同决定了任务缓存的质量。这是边缘服务器决定如何缓存任务数据的指导性模型，从而实现提升缓存质量、任务完成效率以及边缘服务器自身效益的目标。

4 仿真实验结果与分析

4.1 实验参数

针对在线缓存场景，本文仿真实验中将边缘服务器缓存大小等参数设置为：时隙数为500，时隙长度为3 s，边缘服务器数量为30，移动设备任务类型分为10种。设置不同任务类型的目的是为了研究缓存的性能提升，同类型任务可以通过缓存进行计算加速，在实际场景中可以体现为同一软件处理的任务等［28］。其他参数参照其他文献设置各自的取值区间［25，26］，如表1所示。

4.2 评价指标

本文采用的评价指标如下：

a）任务完成率DHR（deadline hit rate），如式（39）所示。

DHR=M-∑Mi=1θiM（39）

b）边缘服务器平均效益AB（average benefit），如式（40）所示。

AB=∑Tt=1benefit（t）N（40）

c）移动设备总能耗EC（energy consumption），如式（41）所示。

EC=∑Tt=1E（t）（41）

其中：E（t）为时隙t的移动设备能耗，如式（42）所示。

E（t）=∑Mm=1Em（t）（42）

4.3 对比策略

本文设置了五个对比策略，比较不同指标的优化效果，五种策略分别为

a）LOTUS［29］：使用李雅普诺夫优化结合势博弈等方法对多个目标进行了优化，但并未使用缓存进行计算加速。

b）PSO（particle swarm optimization）［30］：使用基于高速缓存的智能粒子群优化方法进行策略求解。

c）CEDCO（collaborative edge data caching online）［31］：使用在线算法解决边缘数据缓存问题，针对动态场景以及缓存使用进行了优化。

d）贪婪策略GS（greedy strategy）：边缘服务器总是选取数据量大的任务进行缓存，并且总是选择效益最大的任务。

e）随机策略RS（random strategy）：边缘服务器的缓存选取以及任务决策均随机确定。

4.4 实验结果分析

4.4.1 任务完成率

图2对比了不同任务数量情况下各个策略的任务完成率。由于边缘服务器数量不变，任务数量的增加会导致整体任务完成率降低。在不同任务数的情况下，本文OPSCO的任务完成率都是最优的。这得益于缓存替换策略的设计以及EWA算法对于任务完成率的优化。OPSCO的任务完成率比PSO平均提高23%，比CEDCO平均提高13%。

图3对比了不同时延粒度情况下各个策略的任务完成率，其中任务数量区间设置为［5，10］，模拟常见的任务数量。随着时延粒度的增大，完成任务的时延要求变低，任务完成率也呈总体上升的趋势。各个策略的效果与图2结果类似，GS和RS的效果都不理想。OPSCO的边缘服务器任务完成率比PSO平均提高18%，比CEDCO平均提高12%。

4.4.2 边缘服务器平均效益

图4对比了不同任务数量情况下各个策略的边缘服务器平均效益，通过改变任务数量来模拟不同的任务与边缘服务器的数量比例。由于OPSCO仍然使用势博弈对边缘服务器效益进行针对性优化，允许其选取效益最大化的任务，所以效果优于其他策略。OPSCO的边缘服务器平均效益比PSO提高33%，比CEDCO平均提高29%。

图5对比了不同时延粒度情况下各个策略的边缘服务器平均效益。同样地，该实验中任务数量取值设置为［5，10］。OPSCO对于边缘服务器效益的优化效果仍然最优。PSO以及CEDCO的表现仍然略低于LOTUS以及OPSCO，这由于其未对边缘服务器效益进行优化。GS以及RS的效果仍然受限于其自身的策略设计。OPSCO的边缘服务器平均效益比PSO提高35%，比CEDCO平均提高26%。

4.4.3 移动设备总能耗

图6对比了不同任务数量下各个策略的移动设备总能耗。由于任务本地计算能耗通常比卸载至边缘服务器高，所以移动设备总能耗不仅受到策略针对其自身的优化影响，还会受到任务完成率的优化影响。因此OPSCO的移动设备总能耗较其他基准策略更低。OPSCO的移动设备总能耗比PSO平均降低10%，比CEDCO平均降低12%。

图7对比了不同时延粒度情况下各个策略的移动设备总能耗。该实验中任务数量取值设置为［5，10］。从图中可以看出，时延粒度的增大使得任务完成率上升，因此移动设备总能耗呈下降趋势。在各个场景下，OPSCO仍然具有最低的能耗。PSO與CEDCO的表现与前文类似。RS和GS由于策略自身的性能问题，导致多种场景下的表现都不佳。OPSCO的移动设备总能耗比PSO平均降低11%，比CEDCO平均降低16%。

4.4.4 缓存效用

图8对比了几种策略在不同任务数量下的总缓存效用。其中OPSCO、PSO以及CEDCO均设计了相应的缓存优化策略，其中OPSCO和CEDCO针对动态系统也进行了一定的优化，因此缓存效用略优于PSO。由于求解策略构造的不同，OPSCO得益于基于势博弈的策略设计，对于信息不完全场景的优化更加优秀，使得边缘服务器可以根据自身状态作出最优决策，所以OPSCO的缓存效用要优于其他基准策略。在五种不同的任务数量下，OPSCO的缓存效用CU相较PSO平均提高17%，相较CEDCO平均提高11%。

4.4.5 时间性能

图9展现了OPSCO在不同任务数量情况下的时间性能。由于OPSCO相较LOTUS的博弈论策略部分总体迭代方式趋同，所以收敛性能相近，使得OPSCO仍然具有较优的时间性能。加入缓存效用的评估，边缘服务器需要进行缓存迭代以及相关计算，OPSCO的时间性能相较LOTUS更弱。因为产生的额外时间开销并不高，所以OPSCO在现实场景中依然具有非常好的时间性能。

4.4.6 控制参数分析

图10展示了目标函数P3中控制参数V的变化对于平均队列积压的影响。随着V的增大，平均队列积压也在不断变大，随着任务数量的增多，平均队列积压也会变大。而OPSCO相对LOTUS加入了缓存进行计算加速，使得边缘服务器可以更快地完成任务计算，从而减小了平均队列积压。

5 结束语

本文针对在线缓存场景中的资源分配以及数据缓存问题设计了OPSCO，同时优化MEC系统中的多个性能指标。在OPSCO中使用了李雅普诺夫优化、势博弈以及EWA算法实现多目标求解，同时设计了缓存相关函数指导边缘服务器的缓存使用。仿真实验结果表明，OPSCO相比于其他资源分配策略，可以明显提升任务完成率和缓存效用，并降低设备能耗和时间开销。

当然在某些隐私敏感的场景下，用户数据具有一定的隐私保护要求，在分配边缘服务器的缓存资源时是部分受限的。此外，让所有边缘服务器无条件服从资源分配策略的调度也是较为理想化的假设，在现实中该条件很难实现。这对于本文OPSCO策略的实际应用提出了挑战，是未来需要进一步研究的内容。

参考文献：

［1］Zhao Hailiang， Deng Shuiguang， Zhang Cheng， et al. A mobility-aware cross-edge computation offloading framework for partition able applications［C］//Proc of International Conference on Web Services. Piscataway， NJ： IEEE Press， 2019： 193-200.

［2］Mao Yuyi， You Changsheng， Zhang Jun， et al. A survey on mobile edge computing： the communication perspective［J］. IEEE Communications Surveys & Tutorials， 2017，19（4）： 2322-2358.

［3］Rodrigues T G， Suto K， Nishiyama H， et al. Hybrid method for minimizing service delay in edge cloud computing through VM migration and transmission power control［J］. IEEE Trans on Computers， 2016，66（5）： 810-819.

［4］Rodrigues T G， Suto K， Nishiyama H， et al. Cloudlets activation scheme for scalable mobile edge computing with transmission power control and virtual machine migration［J］. IEEE Trans on Compu-ters， 2018，67（9）： 1287-1300.

［5］Wang Chenmeng， Liang Chengchao， Yu F R， et al. Computation offloading and resource allocation in wireless cellular networks with mobile edge computing［J］. IEEE Trans on Wireless Communications， 2017，16（8）： 4924-4938.

［6］Xia Junxu， Cheng Geyao， Gu Siyuan， et al. Secure and trust-oriented edge storage for Internet of things［J］. IEEE Internet of Things Journal， 2019，7（5）： 4049-4060.

［7］Xing Jiarong， Dai Hongjun， Yu Zhilou. A distributed multi-level model with dynamic replacement for the storage of smart edge computing［J］. Journal of Systems Architecture， 2018，83（5）： 1-11.

［8］Nicolaescu A C， Mastorakis S， Psaras I. Store edge networked data（SEND）： a data and performance driven edge storage framework［C］//Proc of IEEE International Conference on Computer Communications. Piscataway， NJ： IEEE Press， 2021： 1-10.

［9］Lyu Feng， Ren Ju， Cheng Nan， et al. LEAD： large-scale edge cache deployment based on spatio-temporal Wi-Fi traffic statistics［J］. IEEE Trans on Mobile Computing， 2020，20（8）： 2607-2623.

［10］Lyu Feng， Cai Xinyao， Wu Fan， et al. Dynamic pricing scheme for edge computing services： a two-layer reinforcement learning approach［C］//Proc of IEEE/ACM International Symposium on Quality of Service. Piscataway， NJ： IEEE Press， 2022： 1-10.

［11］Huang Xiaowen， Zhang Wenjie， Yang Jingmin， et al. Market-based dynamic resource allocation in mobile edge computing systems with multi-server and multi-user［J］. Computer Communications， 2021，165（2）： 43-52.

［12］Lin Hai， Zeadally S， Chen Zhihong， et al. A survey on computation offloading modeling for edge computing［J］. Journal of Network and Computer Applications， 2020，169（4）： 102-115.

［13］Feng Jie， Yu F R， Pei Qinqi， et al. Joint optimization of radio and computational resources allocation in blockchain-enabled mobile edge computing systems［J］. IEEE Trans on Wireless Communications， 2020，19（6）： 4321-4334.

［14］Gao Bin， Zhou Zhi， Liu Fangming， et al. Winning at the starting line： joint network selection and service placement for mobile edge computing［C］//Proc of IEEE International Conference on Computer Communications. Piscataway， NJ： IEEE Press， 2019： 1459-1467.

［15］Ding Haichuan， Guo Yuanxiong， Li Xuanheng， et al. Beef up the edge： spectrum-aware placement of edge computing services for the Internet of Things［J］. IEEE Trans on Mobile Computing， 2018，18（12）： 2783-2795.

［16］Chen Jiechen， Xing Hong， Lin Xiaohui， et al. Joint resource allocation and cache placement for location-aware multi-user mobile-edge computing［J］. IEEE Internet of Things Journal， 2022，9（24）： 25698-25714.

［17］Wang Zhi， Hou Ronghui. Joint caching and computing resource allocation for task offloading in vehicular networks［J］. IET Communications， 2020，14（21）： 3820-3827.

［18］Chen Zhixiong， Zhou Zhaokun， Chen Chen. Code caching-assisted computation offloading and resource allocation for multi-user mobile edge computing［J］.IEEE Trans on Network and Service Management， 2021，18（4）： 4517-4530.

［19］Zhou Tianqing， Yue Yali， Qin Dong， et al. Mobile device association and resource allocation in HCNs with mobile edge computing and caching［J］. IEEE Systems Journal， 2022，17（1）： 976-987.

［20］Zhang Lyutianyang，Sun Yaping，Chen Zhiyong，et al. Communications caching-computing resource allocation for bidirectional data computation in mobile edge networks［J］. IEEE Trans on Communications， 2020，69（3）： 1496-1509.

［21］Yang Yi， Liu Zhixin. Joint optimization of edge computing resource pricing and wireless caching for blockchain-driven networks［J］. IEEE Trans on Vehicular Technology， 2022，71（6）： 6661-6670.

［22］Wu Rui， Tang Gguoming， Chen Tao， et al. A profit-aware coalition game for cooperative content caching at the network edge［J］. IEEE Internet of Things Journal， 2021，9（2）： 1361-1373.

［23］Yan Jia， Bi Suzhi， Zhang Yinjun， et al. Optimal task offloading and resource allocation in mobile-edge computing with inter-user task dependency［J］. IEEE Trans on Wireless Communications， 2019，19（1）： 235-250.

［24］Bi Suzhi， Huang Liang， Wang Hui， et al. Lyapunov-guided deep reinforcement learning for stable online computation offloading in mobile-edge computing networks［J］. IEEE Trans on Wireless Communications， 2021，20（11）： 7519-7537.

［25］Mashhadi F， Monroy S A S， Bozorgchenani A， et al. Optimal auction for delay and energy constrained task offloading in mobile edge computing［J］. Computer Networks， 2020，183（5）： article ID 107527.

［26］Alkhalaileh M， Calheiros R N， Nguyen Q V， et al. Data-intensive application scheduling on mobile edge cloud computing［J］. Journal of Network and Computer Applications， 2020，167（3）： 102-117.

［27］Cesa-Bianchi N， Lugosi G. Prediction， learning， and games［M］. Cambridge：Cambridge University Press， 2006.

［28］Li Weimin， Li Qin， Chen Lin， et al. A storage resource collaboration model among edge nodes in edge federation service［J］. IEEE Trans on Vehicular Technology， 2022，71（9）： 9212-9224.

［29］陳祎鹏. 移动边缘计算中基于博弈论的资源分配策略研究［D］. 苏州： 苏州大学， 2023. （Chen Yipeng. Research on resource allocation strategies based on game theory in mobile edge computing［D］. Suzhou： Soochow University， 2023.）

［30］Zhou Wenqi， Chen Lunyuan， Tang Shunpu， et al. Offloading strategy with PSO for mobile edge computing based on cache mechanism［J］. Cluster Computing， 2021，25（4）： 1-13.

［31］Xia Xiaoyu， Chen Feifei， He Qiang， et al. Online collaborative data caching in edge computing［J］. IEEE Trans on Parallel and Distributed Systems， 2020，32（2）： 281-294.