Dynamic Pricing Algorithm for Edge Computing Task Offloading Based on Contextual Multi-Armed Bandit

doi:10.19678/j.issn.1000-3428.0069476

Abstract

Abstract:

Existing dynamic pricing algorithms for edge computing are based on game-theoretic models and auction mechanisms. With the optimization objective of maximizing a service provider′s total revenue, existing pricing algorithms face difficulties in obtaining prior information about user utility, and most auction mechanisms favor local optimality over global optimality when selecting prices. To address these problems, this study proposes a dynamic pricing algorithm for offloading edge computing tasks based on a Contextual Multi-Armed Bandit (CMAB). First, the dynamic pricing problem of edge computing is modeled as a CMAB. Next, a dynamic pricing algorithm for task offloading based on Thompson Sampling (TS) is designed that employs a Bayesian posterior to induce service providers to select the price and updates the corresponding parameters by rewarding the revenue in each round, thereby effectively reducing the loss value of the total revenue in the dynamic pricing process. Finally, the effectiveness of the pricing algorithm is verified by simulating a real edge environment. The proposed pricing algorithm outperforms existing Multi-Armed Bandit (MAB) algorithms and pricing algorithms in terms of both the expected cumulative regret value and expected cumulative revenue value.

Key words: edge computing, task offloading, dynamic pricing, Contextual Multi-Armed Bandit (CMAB), Thompson Sampling (TS)

摘要：

现有边缘计算动态定价算法普遍基于博弈论模型与拍卖机制提出。以最大化服务提供商总收益为优化目标，现有定价算法在事先获取用户效用信息方面面临一定的难度，并且多数拍卖机制在选取价格时倾向于局部最优而非全局最优。针对上述问题，提出一种基于上下文多臂赌博机(CMAB)的边缘计算任务卸载动态定价算法。首先，将边缘计算动态定价问题建模为CMAB模型；然后，设计一种基于汤姆森采样(TS)的任务卸载动态定价算法，运用贝叶斯后验来诱导服务提供商进行价格选取，通过每一轮的奖励收益更新对应参数，有效减少了动态定价过程中总收益的亏损值。最后，模拟真实的边缘环境进行实验，验证了定价算法的有效性。仿真实验结果表明，该定价算法在期望累积遗憾值与期望累积收益值方面都优于现有多臂赌博机(MAB)算法和定价算法。

关键词: 边缘计算, 任务卸载, 动态定价, 上下文多臂赌博机, 汤姆森采样

GAN Nan, FU Xiaodong, FENG Yan. Dynamic Pricing Algorithm for Edge Computing Task Offloading Based on Contextual Multi-Armed Bandit[J]. Computer Engineering, 2025, 51(10): 182-190.

甘楠, 付晓东, 冯艳. 基于上下文多臂赌博机的边缘计算任务卸载动态定价算法[J]. 计算机工程, 2025, 51(10): 182-190.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0069476

https://www.ecice06.com/EN/Y2025/V51/I10/182

Figures/Tables 7

Fig.1 Changes in the value of the expected cumulative revenues at different price quantities

Fig.2 Changes in the value of the expected cumulative revenues at different numbers of mobile devices

Fig.3 Comparison of the expected cumulative regret values among different algorithms

Fig.4 Comparison of the expected cumulative regret values of LinUCB, UCB and off_TS

Fig.5 Comparison of the expected cumulative revenue values of different algorithms

References 35

1	WEI Y K , ZHOU S P , ZHANG Y P . Federated learning empowered end-edge-cloud cooperation for 5G HetNet security. IEEE Network, 2021, 35 (2): 88- 94. doi: 10.1109/MNET.011.2000340
2	ZHOU C H , XIA H W , LV X T . Elderly care system based on cloud platform Internet of things. Journal of Physics: Conference Series, 2020, 1544 (1): 1- 6.
3	LYU F , REN J , CHENG N , et al. LEAD: large-scale edge cache deployment based on spatio-temporal WiFi traffic statistics. IEEE Transaction on Mobile Computing, 2021, 20 (8): 2607- 2623. doi: 10.1109/TMC.2020.2984261
4	FAN Z Y , YANG W , WU F , et al. Serving at the edge: an edge computing service architecture based on ICN. ACM Transactions on Internet Technology, 2022, 22 (1): 1- 27.
5	张依琳, 梁玉珠, 尹沐君, 等. 移动边缘计算中计算卸载方案研究综述. 计算机学报, 2021, 44 (12): 2406- 2430.
	ZHANG Y L , LIANG Y Z , YIN M Y , et al. Survey on the methods of computation offloading in mobile edge computing. Chinese Journal of Computers, 2021, 44 (12): 2406- 2430.
6	XIONG Z H , FENG S H , WANG W B , et al. Cloud/fog computing resource management and pricing for blockchain networks. IEEE Internet of Things Journal, 2019, 6 (3): 4585- 4600. doi: 10.1109/JIOT.2018.2871706
7	牛超越, 陈培煜, 张嘉懿, 等. 面向数据中心间网络带宽的在线定价机制设计: 基于强化学习的方法. 计算机学报, 2022, 45 (5): 1068- 1086.
	NIU C Y , CHEN P Y , ZHANG J Y , et al. Reinforcement learning-based online pricing for inter-datacenter bandwidth. Chinese Journal of Computers, 2022, 45 (5): 1068- 1086.
8	SEO H , OH H , CHOI J K , et al. Differential pricing-based task offloading for delay-sensitive IoT application in mobile edge computing system. IEEE Internet of Things Journal, 2022, 9 (19): 19116- 19131. doi: 10.1109/JIOT.2022.3163820
9	YAN J , BI S Z , DUAN L J , et al. Pricing-driven service caching and task offloading in mobile edge computing. IEEE Transactions on Wireless Communications, 2021, 20 (7): 4495- 4512. doi: 10.1109/TWC.2021.3059692
10	WANG R Y, ZANG C Y, HE P, et al. Auction pricing-based task offloading strategy for cooperative edge computing[C]//Proceedings of the 2021 IEEE Global Communications Conference. Washington D. C., USA: IEEE Press, 2021: 1-6.
11	LIU M Y , LIU Y . Price-based distributed offloading for mobile-edge computing with computation capacity constraints. IEEE Wireless Communications Letters, 2018, 7 (3): 420- 423. doi: 10.1109/LWC.2017.2780128
12	吕晓东, 邢焕来, 宋富洪. 移动边缘计算网络中的资源分配与定价. 计算机系统应用, 2022, 31 (10): 99- 107.
	LÜ X D , XING H L , SONG F H . Resource allocation and pricing in mobile edge computing networks. Computer Systems & Applications, 2022, 31 (10): 99- 107.
13	KIM S H , PARK S , CHEN M , et al. An optimal pricing scheme for the energy-efficient mobile edge computation offloading with OFDMA. IEEE Communications Letters, 2018, 22 (9): 1922- 1925. doi: 10.1109/LCOMM.2018.2849401
14	LI F X , YAO H P , DU J , et al. Stackelberg game-based computation offloading in social and cognitive industrial Internet of Things. IEEE Transactions on Industrial Informatics, 2020, 16 (8): 5444- 5455. doi: 10.1109/TII.2019.2961662
15	MIRGHASEMI H, VANDENDORPE L, ASHRAF M. Optimal online resource allocation for swipt-based mobile edge computing systems[C]//Proceedings of the 2020 IEEE Wireless Communications and Networking Conference. Washington D. C., USA: IEEE Press, 2020: 1-8.
16	LIU Z Y , FU J Q . Resource pricing and offloading decisions in mobile edge computing based on the Stackelberg game. The Journal of Supercomputing, 2022, 78 (6): 7805- 7824. doi: 10.1007/s11227-021-04246-w
17	TAO M , OTA K , DONG M X , et al. Stackelberg gamed based pricing and offloading in mobile edge computing. IEEE Wireless Communications Letters, 2022, 11 (5): 883- 887. doi: 10.1109/LWC.2021.3138938
18	LI L X , QUEK T Q S , REN J , et al. An incentive-aware job offloading control framework for multi-access edge computing. IEEE Transactions on Mobile Computing, 2019, 20 (1): 63- 75.
19	刘荆欣, 王妍, 韩笑, 等. 基于Stackelberg博弈的边缘云资源定价机制研究. 计算机科学与探索, 2022, 16 (1): 153- 162.
	LIU J X , WANG Y , HAN X , et al. Research on edge cloud resource pricing mechanism based on Stackelberg game. Journal of Frontiers of Computer Science and Technology, 2022, 16 (1): 153- 162.
20	LIU J G , ZHANG Y M , REN J , et al. Auction-based dependent task offloading for IoT users in edge clouds. IEEE Internet of Things Journal, 2023, 10 (6): 4907- 4921. doi: 10.1109/JIOT.2022.3221431
21	WU B L, CHEN X, CHEN Y, et al. A truthful auction mechanism for resource allocation in mobile edge computing[C]//Proceedings of the 22nd International Symposium on a World of Wireless, Mobile and Multimedia Networks. Washington D. C., USA: IEEE Press, 2021: 21-30.
22	WANG R Y , ZANG C Y , HE P , et al. Auction-based profit maximization offloading in mobile edge computing. Digital Communications and Networks, 2023, 9 (2): 545- 556. doi: 10.1016/j.dcan.2022.03.026
23	MENG Y, WANG Z W. Contextual multi-armed bandit based pricing scheme for cooperative D2D communication[C]//Proceedings of the 2020 IEEE Wireless Communications and Networking Conference. Washington D. C., USA: IEEE Press, 2020: 1-6.
24	JIA H W, SHI C, SHEN S Q. Online learning and pricing with reusable resources: linear bandits with subexponential rewards[C]//Proceedings of the 39th International Conference on Machine Learning. [S. l.]: AAAI Press, 2022: 10135-10160.
25	YE S , WANG T Y , WANG S W . Thompson sampling-based dynamic spectrum access in non-stationary environments. IEEE Transactions on Cognitive Communications and Networking, 2023, 9 (3): 593- 603. doi: 10.1109/TCCN.2023.3237578
26	ABEILLE M, LAZARIC A. Linear Thompson sampling revisited[EB/OL]. [2024-02-01]. https://arxiv.org/pdf/1611.06534.
27	PARK H , FARADONBEH M K S . Analysis of Thompson sampling for partially observable contextual multi-armed bandits. IEEE Control Systems Letters, 2022, 6, 2150- 2155. doi: 10.1109/LCSYS.2021.3137269
28	AGRAWAL S, GOYAL N. Thompson sampling for contextual bandits with linear payoffs[EB/OL]. [2024-02-01]. https://arxiv.org/pdf/1209.3352.
29	DANN C, MANSOUR Y, MOHRI M, et al. Guarantees for Epsilon Greedy reinforcement learning with function approximation[C]//Proceedings of the 39th International Conference on Machine Learning. [S. l.]: AAAI Press, 2022: 4666-4689.
30	HU Y Q , LIU X H , LI S Q , et al. Cascaded algorithm selection with extreme-region UCB bandit. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 44 (10): 6782- 6794. doi: 10.1109/TPAMI.2021.3094844
31	ZHOU D R, LI L H, GU Q Q. Neural contextual bandits with UCB-based exploration[C]// Proceedings of the 37th International Conference on Machine Learning. [S. l.]: AAAI Press, 2020: 11492-11502.
32	LI L H, CHU W, LANGFORD J, et al. A contextual-bandit approach to personalized news article recommendation[C]// Proceedings of the 19th International Conference on World Wide Web. New York, USA: ACM Press, 2010: 661-670.
33	CHENG J M, NGUYEN D T A, WANG L L, et al. A bandit approach to online pricing for heterogeneous edge resource allocation[EB/OL]. [2024-02-01]. https://arxiv.org/pdf/2302.06953.
34	ZHANG X K , AN K , ZHANG B N , et al. Vickrey Auction-based secondary relay selection in cognitive hybrid satellite-terrestrial overlay networks with non-orthogonal multiple access. IEEE Wireless Communications Letters, 2020, 9 (5): 628- 632. doi: 10.1109/LWC.2019.2963863
35	CHEN S Y , LI L X , CHEN Z , et al. Dynamic pricing for smart mobile edge computing: a reinforcement learning approach. IEEE Wireless Communications Letters, 2021, 10 (4): 700- 704. doi: 10.1109/LWC.2020.3039863

[1]	ZHAO Jihong, ZANG Ruoyu, LIU Zhen. Collaborative Computation Offloading Method for Satellite Vehicle-Mounted Mobile Edge Computing Networks [J]. Computer Engineering, 2025, 51(9): 49-58.
[2]	HUANG Yeheng, QIN Tuanfa, SU Zhenlang, WANG Suhong. Efficient Offloading Strategy for Ultra-Dense Wireless Body Area Networks in 6G Networks [J]. Computer Engineering, 2025, 51(9): 201-212.
[3]	CUI Mengmeng, SHI Jingyan, XIANG Haolong. Dynamic Vehicle Edge Task Offloading Method Based on Air-Ground Collaboration [J]. Computer Engineering, 2025, 51(9): 25-37.
[4]	ZHANG Weihang, ZHONG Yongyan, XIANG Yuanzhu, DING Shichan. Revocable Attribute-Based Encryption Scheme Assisted by Edge and Cloud [J]. Computer Engineering, 2025, 51(7): 244-253.
[5]	YANG Libin, ZHAN Cheng, LI Tingting, LIAO Jingrui. Energy-Efficient Resource Allocation Strategies in Multi-Antenna UAV Video Communication [J]. Computer Engineering, 2025, 51(6): 266-274.
[6]	WU Xiaofeng, YUAN Peiyan. Dynamic Placement Strategy for Edge Servers Under Improved Snake Optimization Algorithm [J]. Computer Engineering, 2025, 51(6): 255-265.
[7]	DU Jianbo, DONG Weizhe, JIN Rong, WANG Junxuan, KANG Jiawen, LIU Lei, Celimuge Wu. Task Segmentation and Resource Allocation in MEC-Based Space-Air-Ground Integrated Networks [J]. Computer Engineering, 2025, 51(5): 43-51.
[8]	LIN Shaofu, CHEN Yingying, LI Shuopeng. Method of Joint Optimization for Multi-UAV Energy Transfer and Edge Computing Based on Deep Reinforcement Learning [J]. Computer Engineering, 2025, 51(3): 144-154.
[9]	XU Yuanbo, REN Jing, WANG Liang, FU Ning, YU Zhiwen. Admission Control Mechanism for Offloading Tasks in UAV-Assisted Edge Computing [J]. Computer Engineering, 2025, 51(2): 54-64.
[10]	LIU Liang, MAO Wuping, LI Wenwei, TAN Siyuan, JING Tengxiang. Task Offloading Strategy Based on Game Theory in the Space-Air-Ground Integrated Edge Computing Networks [J]. Computer Engineering, 2025, 51(2): 238-249.
[11]	ZHANG Junna, LI Tianze, ZHAO Xiaoyan, YUAN Peiyan. A Decentralized Priority Offloading Strategy Based on DQN [J]. Computer Engineering, 2024, 50(9): 235-245.
[12]	Ji ZHANG, Wenwen GONG, Chunhong DUO, Guoliang QI. Offloading Algorithm for Multi-Agent and Double-Layer Offloading in Internet of Vehicle [J]. Computer Engineering, 2024, 50(8): 182-197.
[13]	Junhui ZHOU, Peng XU, Shengli SUN. A Service Strategy Based on Age of Information Optimization in Collaborative Perception Systems [J]. Computer Engineering, 2024, 50(8): 165-181.
[14]	Qiong SHI, Hui DUAN, Zhibin SHI. Trusted Task Offloading Scheme Based on Deep Reinforcement Learning [J]. Computer Engineering, 2024, 50(8): 142-152.
[15]	Jiao CHEN, Yan SHEN. Research on Task Offloading of Mobile Edge Computing for Caching Mechanism [J]. Computer Engineering, 2024, 50(7): 194-203.

Please choose a citation manager

Content to export