基于多领导者Stackelberg博弈的分层联邦学习激励机制设计

doi:10.11772/j.issn.1001-9081.2022111727

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (11): 3551-3558.DOI: 10.11772/j.issn.1001-9081.2022111727

基于多领导者Stackelberg博弈的分层联邦学习激励机制设计

耿方兴¹^,², 李卓¹^,²(), 陈昕²

^1.网络文化与数字传播北京市重点实验室（北京信息科技大学），北京 100101
^2.北京信息科技大学计算机学院，北京 100101

收稿日期:2022-11-21 修回日期:2023-04-03 接受日期:2023-04-04 发布日期:2023-05-08 出版日期:2023-11-10
通讯作者: 李卓
作者简介:耿方兴（1999—），男，河南驻马店人，硕士研究生，主要研究方向：边缘计算
李卓（1983—），男，河南南阳人，副教授，博士，CCF会员，主要研究方向：移动无线网络、分布式计算 lizhuo@bistu.edu.cn
陈昕（1965—），男，江西南昌人，教授，博士，CCF会员，主要研究方向：网络性能评价、网络安全。
基金资助:
北京市自然科学基金资助项目(4232024);国家重点研发计划项目(2022YFF0604502);国家自然科学基金资助项目(61872044);北京市青年拔尖人才项目

Incentive mechanism design for hierarchical federated learning based on multi-leader Stackelberg game

Fangxing GENG¹^,², Zhuo LI¹^,²(), Xin CHEN²

^1.Beijing Key Laboratory of Internet Culture and Digital Dissemination Research （Beijing Information Science and Technology University），Beijing 100101，China
^2.Computer School，Beijing Information Science and Technology University，Beijing 100101，China

Received:2022-11-21 Revised:2023-04-03 Accepted:2023-04-04 Online:2023-05-08 Published:2023-11-10
Contact: Zhuo LI
About author:GENG Fangxing， born in 1999， M. S. candidate. His research interests include edge computing.
LI Zhuo， born in 1983， Ph. D.， associate professor. His research interests include mobile wireless network， distributed computing.
CHEN Xin， born in 1965， Ph. D.， professor. His research interests include network performance evaluation， network security.
Supported by:
Beijing Natural Science Foundation(4232024);National Key Research and Development Program of China(2022YFF0604502);National Natural Science Foundation of China(61872044);Beijing Municipal Program for Young Talents

摘要/Abstract

摘要：

分层联邦学习中隐私安全与资源消耗等问题的存在降低了参与者的积极性。为鼓励足够多的参与者积极参与学习任务，并针对多移动设备与多边缘服务器之间的决策问题，提出基于多领导者Stackelberg博弈的激励机制。首先，通过量化移动设备的成本效用与边缘服务器的支付报酬，构建效用函数并定义最优化问题；其次，将移动设备之间的交互建模为演化博弈，将边缘服务器之间的交互建模为非合作博弈。为求解最优边缘服务器选择和定价策略，提出多轮迭代边缘服务器选择算法（MIES）和梯度迭代定价算法（GIPA），前者用于求解移动设备之间的演化博弈均衡解，后者用于求解边缘服务器之间的定价竞争问题。实验结果表明，所提算法GIPA与最优定价预测策略（OPPS）、历史最优定价策略（HOPS）和随机定价策略（RPS）相比，可使边缘服务器的平均效用分别提高4.06%、10.08%和31.39%。

关键词: 分层联邦学习, 激励机制, 定价策略, 多领导者Stackelberg博弈, 演化博弈

Abstract:

The existence of privacy security and resource consumption issues in hierarchical federated learning reduces the enthusiasm of participants. To encourage a sufficient number of participants to actively participate in learning tasks and address the decision-making problem between multiple mobile devices and multiple edge servers， an incentive mechanism based on multi-leader Stackelberg game was proposed. Firstly， by quantifying the cost-utility of mobile devices and the payment of edge servers， a utility function was constructed， and an optimization problem was defined. Then， the interaction among mobile devices was modeled as an evolutionary game， and the interaction among edge servers was modeled as a non-cooperative game. To solve the optimal edge server selection and pricing strategy， a Multi-round Iterative Edge Server selection algorithm （MIES） and a Gradient Iterative Pricing Algorithm （GIPA） were proposed. The former was used to solve the evolutionary game equilibrium solution among mobile devices， and the latter was used to solve the pricing competition problem among edge servers. Experimental results show that compared with Optimal Pricing Prediction Strategy （OPPS）， Historical Optimal Pricing Strategy （HOPS） and Random Pricing Strategy （RPS）， GIPA can increase the average utility of edge servers by 4.06%， 10.08%， and 31.39% respectively.

Key words: hierarchical federated learning, incentive mechanism, pricing strategy, multi-leader Stackelberg game, evolutionary game

中图分类号:

TP393

耿方兴, 李卓, 陈昕. 基于多领导者Stackelberg博弈的分层联邦学习激励机制设计[J]. 计算机应用, 2023, 43(11): 3551-3558.

Fangxing GENG, Zhuo LI, Xin CHEN. Incentive mechanism design for hierarchical federated learning based on multi-leader Stackelberg game[J]. Journal of Computer Applications, 2023, 43(11): 3551-3558.

图/表 10

图1 分层联邦学习框架

Fig. 1 Framework of hierarchical federated learning

图2 多领导者Stackelberg博弈模型

Fig. 2 Multi-leader Stackelberg game model

表1 模拟参数设置

Tab. 1 Simulation parameters setting

参数	值	参数说明
N	90	移动设备数量
J	3	边缘服务器数量
M	3	种群数量
$D m$	［2 400，4 800］	种群m中的总数据量
$δ$	0.001	移动设备对信息的获取率
$c m υ$	0.001	种群m中单位数据所产生的计算成本
$c m τ$	50	种群m中单位功率传输的成本
$I m$	0.1	种群m中模型数据大小
$λ$	100	移动设备训练迭代的轮次
$ρ m$	10	种群m中传输速率
$ζ j$	［3，3.6］	边缘服务器j收益参数
$μ$	1	网络拥塞系数
$β j$	［2，3］	边缘服务器j定价的改变幅度

表1 模拟参数设置

Tab. 1 Simulation parameters setting

参数	值	参数说明
N	90	移动设备数量
J	3	边缘服务器数量
M	3	种群数量
$D m$	［2 400，4 800］	种群m中的总数据量
$δ$	0.001	移动设备对信息的获取率
$c m υ$	0.001	种群m中单位数据所产生的计算成本
$c m τ$	50	种群m中单位功率传输的成本
$I m$	0.1	种群m中模型数据大小
$λ$	100	移动设备训练迭代的轮次
$ρ m$	10	种群m中传输速率
$ζ j$	［3，3.6］	边缘服务器j收益参数
$μ$	1	网络拥塞系数
$β j$	［2，3］	边缘服务器j定价的改变幅度

图3 a1随迭代次数的变化趋势（m=1）

Fig. 3 Trend of a1 varying with number of iterations （m=1）

图4 不同初始状态下a11随迭代次数的变化趋势（m=1）

Fig. 4 Trend of a11 varying with number of iterations （m=1） under different initial status

图5 边缘服务器定价不变时不同种群中移动设备总效用的对比

Fig. 5 Comparison of total mobile device utility in different populations with constant edge server pricing

图6 有限次迭代后边缘服务器的定价趋势

Fig. 6 Pricing trends for edge servers after finite iterations

图7 不同收益参数下的边缘服务器效用

Fig. 7 Utilities of edge servers with different revenue parameters

图8 不同的定价策略下的边缘服务器的效用对比

Fig. 8 Utility comparison of edge servers under different pricing strategies

图9 不同定价策略下模型的积极程度对比

Fig. 9 Comparison of model positivity under different pricing strategies

参考文献 28

1	谭作文，张连福. 机器学习隐私保护研究综述［J］. 软件学报， 2020， 31（7）：2127-2156. 10.13328/j.cnki.jos.006052
	TAN Z W， ZHANG L F. Survey on privacy preserving techniques for machine learning［J］. Journal of Software， 2020， 31（7）： 2127-2156. 10.13328/j.cnki.jos.006052
2	McMAHAN H B， MOORE E， RAMAGE D， et al. Communication-efficient learning of deep networks from decentralized data［C］// Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. New York： JMLR.org， 2017：1273-1282.
3	ABAD M S H， OZFATURA E， GÜNDÜZ D， et al. Hierarchical federated learning across heterogeneous cellular networks［C］// Proceedings of the 2020 IEEE International Conference on Acoustics， Speech and Signal Processing. Piscataway： IEEE， 2020： 8866-8870. 10.1109/icassp40776.2020.9054634
4	TU X， ZHU K， LUONG N C， et al. Incentive mechanisms for federated learning： from economic and game theoretic perspective［J］. IEEE Transactions on Cognitive Communications and Networking， 2022， 8（3）： 1566-1593. 10.1109/tccn.2022.3177522
5	TIAN M， CHEN Y， LIU Y， et al. A contract theory based incentive mechanism for federated learning［EB/OL］. （2021-08-12）［2022-08-10］.. 10.1007/978-3-031-11748-0_6
6	YU H， LIU Z， LIU Y， et al. A fairness-aware incentive scheme for federated learning［C］// Proceedings of the 2020 AAAI/ACM Conference on AI， Ethics， and Society. New York： ACM， 2020： 393-399. 10.1145/3375627.3375840
7	ZENG R， ZHANG S， WANG J， et al. FMore： an incentive scheme of multi-dimensional auction for federated learning in MEC［C］// Proceedings of the IEEE 40th International Conference on Distributed Computing Systems. Piscataway： IEEE， 2020： 278-288. 10.1109/icdcs47774.2020.00094
8	李从东，黄浩，张帆顺. 基于演化博弈的领先用户知识共享行为激励机制［J］. 计算机应用， 2021， 41（6）：1785-1791. 10.11772/j.issn.1001-9081.2020091449
	LI C D， HUANG H， ZHANG F S. Knowledge sharing behavior incentive mechanism for lead users based on evolutionary game［J］. Journal of Computer Applications， 2021， 41（6）： 1785-1791. 10.11772/j.issn.1001-9081.2020091449
9	CHEN Y， ZHANG Y， WANG S， et al. DIM-DS： dynamic incentive model for data sharing in federated learning based on smart contracts and evolutionary game theory［J］. IEEE Internet of Things Journal， 2022， 9（23）： 24572-24584. 10.1109/jiot.2022.3191671
10	ZOU Y， FENG S， NIYATO D， et al. Mobile device training strategies in federated learning： an evolutionary game approach［C］// Proceedings of the 2019 IEEE International Conference on Internet of Things/ Green Computing and Communications/ Cyber， Physical and Social Computing/ Smart Data. Piscataway： IEEE， 2019： 874-879. 10.1109/ithings/greencom/cpscom/smartdata.2019.00157
11	王月平，徐涛. 基于演化博弈的用户接入机制［J］. 计算机应用， 2020， 40（5）：1392-1396. 10.11772/j.issn.1001-9081.2019112024
	WANG Y P， XU T. User association mechanism based on evolutionary game［J］. Journal of Computer Applications， 2020， 40（5）： 1392-1396. 10.11772/j.issn.1001-9081.2019112024
12	LIM W Y B， NG J S， XIONG Z， et al. Dynamic edge association and resource allocation in self-organizing hierarchical federated learning networks［J］. IEEE Journal on Selected Areas in Communications， 2021， 39（12）： 3640-3653. 10.1109/jsac.2021.3118401
13	FENG S， NIYATO D， WANG P， et al. Joint service pricing and cooperative relay communication for federated learning［C］// Proceedings of the 2019 IEEE International Conference on Internet of Things/ Green Computing and Communications/ Cyber， Physical and Social Computing/ Smart Data. Piscataway： IEEE， 2019： 815-820. 10.1109/ithings/greencom/cpscom/smartdata.2019.00148
14	XIAO G， XIAO M， GAO G， et al. Incentive mechanism design for federated learning： a two-stage Stackelberg game approach［C］// Proceedings of the IEEE 26th International Conference on Parallel and Distributed Systems. Piscataway： IEEE， 2020： 148-155. 10.1109/icpads51040.2020.00029
15	KHAN L U， PANDEY S R， TRAN N H， et al. Federated learning for edge networks： resource optimization and incentive mechanism［J］. IEEE Communications Magazine， 2020， 58（10）： 88-93. 10.1109/mcom.001.1900649
16	NIE J， LUO J， XIONG Z， et al. A Stackelberg game approach toward socially-aware incentive mechanisms for mobile crowdsensing［J］. IEEE Transactions on Wireless Communications， 2019， 18（1）： 724-738. 10.1109/twc.2018.2885747
17	SU Y， FAN W， LIU Y， et al. Game-based pricing and task offloading in mobile edge computing enabled edge-cloud systems［EB/OL］. （2021-01-14）［2022-08-10］.. 10.1016/j.comnet.2021.108523
18	ZHAN Y， LI P， QU Z， et al. A learning-based incentive mechanism for federated learning［J］. IEEE Internet of Things Journal， 2020， 7（7）： 6360-6368. 10.1109/jiot.2020.2967772
19	GONG X， DUAN L， CHEN X， et al. When social network effect meets congestion effect in wireless networks： data usage equilibrium and optimal pricing［J］. IEEE Journal on Selected Areas in Communications， 2017， 35（2）： 449-462. 10.1109/jsac.2017.2659059
20	HAN Z， NIYATO D， SAAD W， et al. Game Theory in Wireless and Communication Networks： Theory， Models， and Applications［M］. Cambridge： Cambridge University Press， 2012： 139-143. 10.1017/cbo9780511895043
21	HOFBAUER J， SIGMUND K. Evolutionary game dynamics［J］. Bulletin of the American Mathematical Society， 2003， 40（4）： 479-519. 10.1090/s0273-0979-03-00988-1
22	GAO X， FENG S， NIYATO D， et al. Dynamic access point and service selection in backscatter-assisted RF-powered cognitive networks［J］. IEEE Internet of Things Journal， 2019， 6（5）： 8270-8283. 10.1109/jiot.2019.2923566
23	PEJÓ B， TANG Q， BICZÓK G. Together or alone： the price of privacy in collaborative learning［EB/OL］. ［2022-08-10］.. 10.2478/popets-2019-0019
24	WENG J， WENG J， HUANG H， et al. FedServing： a federated prediction serving framework based on incentive mechanism［C］// Proceedings of the 2021 IEEE Conference on Computer Communications. Piscataway： IEEE， 2021： 1-10. 10.1109/infocom42981.2021.9488807
25	GONDZIO J. Interior point methods 25 years later［J］. European Journal of Operational Research， 2012， 218（3）： 587-601. 10.1016/j.ejor.2011.09.017
26	LENG Y， WANG M， MA B， et al. A game-based scheme for resource purchasing and pricing in MEC for Internet of Things［J］. Security and Communication Networks， 2021， 2021： No.1951141. 10.1155/2021/1951141
27	DENG Y， LYU F， REN J， et al. Improving federated learning with quality-aware user incentive and auto-weighted model aggregation［J］. IEEE Transactions on Parallel and Distributed Systems， 2022， 33（12）： 4515-4529. 10.1109/tpds.2022.3195207
28	ZHAN Y， ZHANG J， HONG Z， et al. A survey of incentive mechanism design for federated learning［J］. IEEE Transactions on Emerging Topics in Computing， 2022， 10（2）： 1035-1044.

[1]	潘亚楠, 潘庆先, 于兆一, 褚佳静, 于嵩. 时空众包中基于质量感知的在线激励机制[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2091-2099.
[2]	郑万波, 陈慧敏, 吴燕清, 夏云霓. 基于应急救援的信息共享策略仿真[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 306-311.
[3]	毕文婷, 林海涛, 张立群. 基于多阶段演化信号博弈模型的移动目标防御决策算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2780-2787.
[4]	李由之, 胡志华, 陈春, 杨培蓓, 董雅静. 基于双长短期记忆网络组合的网络货运平台成交定价预测模型[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1616-1623.
[5]	龚英, 何彦婷, 曹策俊. 面向重大公共卫生风险治理的应急物流协同演化仿真[J]. 计算机应用, 2021, 41(9): 2754-2760.
[6]	李从东, 黄浩, 张帆顺. 基于演化博弈的领先用户知识共享行为激励机制[J]. 计算机应用, 2021, 41(6): 1785-1791.
[7]	雷鹰, 郑万波, 魏嵬, 夏云霓, 李晓波, 刘诚武, 谢洪. 基于概率性能感知演化博弈策略的“云+边”混合环境中任务卸载方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3302-3308.
[8]	巫光福, 王影军. 基于区块链与云-边缘计算混合架构的车联网数据安全存储与共享方案[J]. 计算机应用, 2021, 41(10): 2885-2892.
[9]	王月平, 徐涛. 基于演化博弈的用户接入机制[J]. 计算机应用, 2020, 40(5): 1392-1396.
[10]	陈秀华, 刘慧, 熊金波, 马蓉. 移动群智感知中面向任务需求的用户选择激励机制[J]. 计算机应用, 2019, 39(8): 2310-2317.
[11]	王西龙, 王继成, 罗成, 田秀霞. 时间尺度与选择倾向性协同作用下的演化博弈模型[J]. 计算机应用, 2019, 39(6): 1824-1828.
[12]	刘保见, 张效义, 李青. 基于演化博弈论的无线传感网监测节点分群算法[J]. 计算机应用, 2016, 36(8): 2157-2162.
[13]	王莹洁, 蔡志鹏, 童向荣, 潘庆先, 高洋, 印桂生. 基于声誉的移动众包系统的在线激励机制[J]. 计算机应用, 2016, 36(8): 2121-2127.
[14]	朱旋, 杨麦顺, 安健, 向乐乐, 杨蔷薇. 群智感知中基于反拍卖模型的众包激励方法[J]. 计算机应用, 2016, 36(7): 2038-2045.
[15]	徐小琼, 周朝荣, 马小霞, 杨柳. 容迟网络中基于演化博弈的合作行为[J]. 计算机应用, 2016, 36(2): 483-487.

基于多领导者Stackelberg博弈的分层联邦学习激励机制设计

Incentive mechanism design for hierarchical federated learning based on multi-leader Stackelberg game

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 28

相关文章 15

编辑推荐

Metrics