基于Stackelberg博弈的边缘云资源定价机制研究

doi:10.3778/j.issn.1673-9418.2009086

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (1): 153-162.DOI: 10.3778/j.issn.1673-9418.2009086

基于Stackelberg博弈的边缘云资源定价机制研究

刘荆欣¹, 王妍¹^,⁺(), 韩笑¹, 夏长清²^,³^,⁴, 宋宝燕¹

1.辽宁大学信息学院,沈阳 110036
2.中国科学院沈阳自动化研究所机器人学国家重点实验室,沈阳 110016
3.中国科学院沈阳自动化研究所网络化控制系统重点实验室,沈阳 110016
4.中国科学院机器人与智能制造创新研究院,沈阳 110169

收稿日期:2020-08-07 修回日期:2020-10-13 出版日期:2022-01-01 发布日期:2020-10-23
通讯作者: + E-mail: wang_yan@lnu.edu.cn
作者简介:刘荆欣（1996—）,女,山东招远人,硕士研究生,CCF学生会员,主要研究方向为边缘计算资源管理、任务调度等。
王妍（1978—）,女,辽宁抚顺人,博士,教授,硕士生导师,CCF会员,主要研究方向为工业物联网数据处理、任务调度、大数据技术等。
韩笑（1994—）,男,辽宁锦州人,硕士研究生,主要研究方向为边缘计算下的任务调度。
夏长清（1985—）,男,山东威海人,博士,助理研究员,CCF会员,主要研究方向为工业物联网、边缘计算下的任务调度等。
宋宝燕（1965—）,女,辽宁开原人,博士,教授,硕士生导师,CCF高级会员,主要研究方向为数据库理论和技术、大数据管理等。
基金资助:
国家重点研发计划(2019YFB1406002);国家自然科学基金(61903356);机器人学国家重点实验室开放基金(2019-022);辽宁省自然科学基金计划重点项目(20180520029);辽宁省经济社会发展课题(2019lslktqn-023)

Research on Edge Cloud Resource Pricing Mechanism Based on Stackelberg Game

LIU Jingxin¹, WANG Yan¹^,⁺(), HAN Xiao¹, XIA Changqing²^,³^,⁴, SONG Baoyan¹

1. College of Information, Liaoning University, Shenyang 110036, China
2. State Key Laboratory of Robotics, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China
3. Key Laboratory of Networked Control System, Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China
4. Institutes for Robotics and Intelligent Manufacturing, Chinese Academy of Sciences, Shenyang 110169, China

Received:2020-08-07 Revised:2020-10-13 Online:2022-01-01 Published:2020-10-23
About author:LIU Jingxin, born in 1996, M.S. candidate, student member of CCF. Her research interests include edge computing resource management, task scheduling, etc.
WANG Yan, born in 1978, Ph.D., professor, M.S. supervisor, member of CCF. Her research interests include industrial Internet of things data processing, task scheduling, big data technology, etc.
HAN Xiao, born in 1994, M.S. candidate. His research interest is task scheduling under edge computing.
XIA Changqing, born in 1985, Ph.D., assistant researcher, member of CCF. His research interests include industrial Internet of things, task scheduling under edge computing, etc.
SONG Baoyan, born in 1965, Ph.D., professor, M.S. supervisor, senior member of CCF. Her research interests include database theory and techniques, big data management, etc.
Supported by:
National Key Research and Development Program of China(2019YFB1406002);National Natural Science Foundation of China(61903356);Foundation of State Key Laboratory of Robotics(2019-022);Key Project of the Natural Science Foundation of Liaoning Province(20180520029);Economic and Social Development Project of Liaoning Province(2019lslktqn-023)

摘要/Abstract

摘要：

移动边缘计算（MEC）支持终端设备将任务或应用程序卸载到边缘云服务器处理,边缘云服务器处理外来任务会消耗本地资源,为激励边缘云提供资源服务,构建向终端设备收费以奖励边缘云的资源定价机制尤为重要。现有的定价机制依赖中间商的静态定价,费用高且终端任务处理不及时,难以实现边缘云计算资源的有效利用。针对上述问题,提出一种基于Stackelberg博弈的边缘云资源定价机制。首先,针对资源定价时终端设备因资金不足而导致的本地任务搁置问题,提出包含贷款和激励的辅助机制,实现终端设备任务的及时处理;其次,提出影响资源定价的四种价格导向因素,制定了一致性与弹性两种定价方案,提高定价的准确性和效率,并为动态定价做准备;然后,为了使终端设备与边缘云直接进行动态定价,构建基于斯坦克伯格（Stackelberg）博弈的资源定价机制模型,将资源需求与定价问题转化为边缘云收益最大与终端设备支付成本最小问题;最后,通过改进的强化学习SARSA算法得到资源需求及定价的最优策略。实验表明,提出的定价机制在边缘云收益最大化方面优于其他定价算法12%以上,同时弹性定价方案下边缘云的收益优于一致性定价方案24%。

关键词: 移动边缘计算（MEC）, 资源定价机制, Stackelberg博弈, 强化学习

Abstract:

Mobile edge computing (MEC) supports terminal devices to offload tasks or applications to edge cloud server for processing. Edge cloud server will consume local resources when processing external tasks, so it is particularly important to build a resource pricing mechanism that charges terminal devices to reward edge cloud. The existing pricing mechanism relies on the static pricing of intermediaries, and high cost and late processing of terminal tasks make it difficult to realize the effective utilization of edge cloud computing resources. Aiming at the above problems, this paper proposes an edge cloud resource pricing mechanism based on Stackelberg game. Firstly, in view of the local task shelving problem of terminal devices due to insufficient funds during resource pricing, an auxiliary mechanism including loans and incentives is proposed to realize the timely processing of terminal devices tasks. Secondly, four price-oriented factors that affect resource pricing are proposed, and two pricing schemes, consistency and elasticity, are formulated to improve the accuracy and efficiency of pricing and prepare for dynamic pricing. Then, in order to make the dynamic pricing between terminal devices and edge cloud directly, a resource pricing mechanism model based on Stackelberg game is built, and the resource demand and pricing problem is transformed into the problem of maximum revenue of edge cloud and minimum payment cost of terminal devices. Finally, through improved reinforcement learning SARSA (state action reward state action) algorithm, the optimal strategy of resource demand and pricing is obtained. Experiments show that the pricing mechanism proposed in this paper is more than 12% better than other pricing algorithms in terms of edge cloud revenue maximization, and the edge cloud revenue under the elasticity pricing scheme is 24% better than that of the consistency pricing scheme.

Key words: mobile edge computing (MEC), resource pricing mechanism, Stackelberg game, reinforcement learning

中图分类号:

TP399

刘荆欣, 王妍, 韩笑, 夏长清, 宋宝燕. 基于Stackelberg博弈的边缘云资源定价机制研究[J]. 计算机科学与探索, 2022, 16(1): 153-162.

LIU Jingxin, WANG Yan, HAN Xiao, XIA Changqing, SONG Baoyan. Research on Edge Cloud Resource Pricing Mechanism Based on Stackelberg Game[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(1): 153-162.

图/表 7

图1 边缘云资源定价系统模型

Fig.1 Edge cloud resource pricing system model

图2 资源供需双方的Stackelberg博弈过程

Fig.2 Stackelberg game between resource supply and demand

图3 四种求解最优策略的算法比较

Fig.3 Comparison of four algorithms for solving optimal strategies

图4 边缘云效用函数的收敛情况比较

Fig.4 Comparison of convergence of edge cloud utility functions

图5 终端设备数量对最优资源定价的影响

Fig.5 Impact of number of terminal devices on optimal resource pricing

图6 终端设备数目对最优资源需求的影响

Fig.6 Impact of number of terminal devices on optimal resource demand

图7 两种定价方案下终端设备效用函数的收敛情况

Fig.7 Convergence of utility functions of terminal devices under two pricing schemes

参考文献 16

[1]	SHI W S, CAO J, ZHANG Q, et al. Edge computing: vision and challenges[J]. IEEE Internet of Things Journal, 2016, 3(5):637-646. DOI URL
[2]	谢人超, 廉晓飞, 贾庆民, 等. 移动边缘计算卸载技术综述[J]. 通信学报, 2018, 39(11):138-155.
	XIE R C, LIAN X F, JIA Q M, et al. Survey on computation offloading in mobile edge computing[J]. Journal on Com-munications, 2018, 39(11):138-155.
[3]	张开元, 桂小林, 任德旺, 等. 移动边缘网络中计算迁移与内容缓存研究综述[J]. 软件学报, 2019, 30(8):2491-2516.
	ZHANG K Y, GUI X L, REN D W, et al. Survey on com-putation offloading and content caching in mobile edge net-works[J]. Journal of Software, 2019, 30(8):2491-2516.
[4]	邓晓衡, 关培源, 万志文, 等. 基于综合信任的边缘计算资源协同研究[J]. 计算机研究与发展, 2018, 55(3):449-477.
	DENG X H, GUAN P Y, WAN Z W, et al. Integrated trust based resource cooperation in edge computing[J]. Journal of Computer Research and Development, 2018, 55(3):449-477.
[5]	PAN J L, MCELHANNON J. Future edge cloud and edge computing for Internet of things applications[J]. IEEE In-ternet of Things Journal, 2018, 5(1):439-449.
[6]	YAO H P, MAI T L, WANG J J, et al. Resource trading in blockchain-based industrial Internet of things[J]. IEEE Tran-sactions on Industrial Informatics, 2019, 15(6):3602-3609.
[7]	ZHANG Y M, LAN X L, LI Y, et al. Efficient computation resource management in mobile edge-cloud computing[J]. IEEE Internet of Things Journal, 2019, 6(2):3455-3466. DOI URL
[8]	张伊璇, 何泾沙, 赵斌, 等. 一个基于博弈理论的隐私保护模型[J]. 计算机学报, 2016, 39(3):615-627.
	ZHANG Y X, HE J S, ZHAO B, et al. A privacy protection model based on game theory[J]. Chinese Journal of Com-puters, 2016, 39(3):615-627.
[9]	董思岐, 李海龙, 屈毓锛, 等. 移动边缘计算中的计算卸载策略研究综述[J]. 计算机科学, 2019, 46(11):32-40.
	DONG S Q, LI H L, QU Y B, et al. Survey of research on computation unloading strategy in mobile edge computing[J]. Computer Science, 2019, 46(11):32-40.
[10]	LIU M, LIU Y. Price-based distributed offloading for mobile-edge computing with computation capacity constraints[J]. IEEE Wireless Communications Letters, 2018, 7(3):420-423. DOI URL
[11]	LI Z T, KANG J W, YU R, et al. Consortium blockchain for secure energy trading in industrial Internet of things[J]. IEEE Transactions on Industrial Informatics, 2018, 14(8):3690-3700.
[12]	ZHANG H, GUO F, JI H, et al. Combinational auction-based service provider selection in mobile edge computing networks[J]. IEEE Access, 2017, 5:13455-13464. DOI URL
[13]	XIONG Z H, FENG S H, WANG W B, et al. Cloud/fog computing resource management and pricing for blockchain networks[J]. IEEE Internet of Things Journal, 2019, 6(3):4585-4600. DOI URL
[14]	杜威, 丁世飞. 多智能体强化学习综述[J]. 计算机科学, 2019, 46(8):1-8.
	DU W, DING S F. Overview on multi-agent reinforcement learning[J]. Computer Science, 2019, 46(8):1-8.
[15]	张文旭, 马磊, 贺荟霖, 等. 强化学习的地-空异构多智能体协作覆盖研究[J]. 智能系统学报, 2018, 13(2):202-207.
	ZHANG W X, MA L, HE H L, et al. Air-ground heterogen-eous coordination for multi-agent coverage based on rein-forced learning[J]. CAAI Transactions on Intelligent Systems, 2018, 13(2):202-207.
[16]	BUSONIU L, BABUSKA R, DE SCHUTTER B. A com-prehensive survey of multiagent reinforcement learning[J]. IEEE Transactions on Systems, Man and Cybernetics, 2008, 38(2):156-172.

基于Stackelberg博弈的边缘云资源定价机制研究

Research on Edge Cloud Resource Pricing Mechanism Based on Stackelberg Game

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 16

相关文章 11

编辑推荐

Metrics

[1]	陈共驰, 荣欢, 马廷淮. 面向连贯性强化的无真值依赖文本摘要模型[J]. 计算机科学与探索, 2022, 16(3): 621-636.
[2]	王扬, 陈智斌, 吴兆蕊, 高远. 强化学习求解组合最优化问题的研究综述[J]. 计算机科学与探索, 2022, 16(2): 261-279.
[3]	陈斌, 刘卫国. 基于SAC模型的改进遗传算法求解TSP问题[J]. 计算机科学与探索, 2021, 15(9): 1680-1693.
[4]	刘继军, 邹山花, 卢先领. MEC中资源分配与卸载决策联合优化策略[J]. 计算机科学与探索, 2021, 15(5): 848-858.
[5]	严丹，何军，刘红岩，杜小勇. 考虑评级信息的音乐评论文本自动生成[J]. 计算机科学与探索, 2020, 14(8): 1389-1396.
[6]	赵婷婷，孔乐，韩雅杰，任德华，陈亚瑞. 模型化强化学习研究综述[J]. 计算机科学与探索, 2020, 14(6): 918-927.
[7]	郑逢斌，朱东伟，臧文乾，杨劲林，朱光辉. 边缘计算：新型计算范式综述与应用研究[J]. 计算机科学与探索, 2020, 14(4): 541-553.
[8]	刘中强，游晓明，刘升. 启发式强化学习机制的异构双种群蚁群算法[J]. 计算机科学与探索, 2020, 14(3): 460-469.
[9]	杨珉，汪洁. 解决深度探索问题的贝叶斯深度强化学习算法[J]. 计算机科学与探索, 2020, 14(2): 307-316.
[10]	朱芮，马永涛，南亚飞，张云蕾. 融合改进强化学习的认知无线电抗干扰决策算法[J]. 计算机科学与探索, 2019, 13(4): 693-701.
[11]	余雪丽，李志，周昌能，崔倩，胡坤. 强化学习中异构反馈信号的分析与集成[J]. 计算机科学与探索, 2012, 6(4): 366-376.