基于緩存優化的移動邊緣計算資源分配策略

司強毅 陳祎鵬 楊哲

摘 要：移動邊緣計算研究中，邊緣服務器通過緩存任務數據可以有效節約計算資源，但如何分配緩存資源解決邊緣服務器的競爭關系，以及能耗和效益問題，達到系統性能最優是一個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.