基于背包模型的联邦学习客户端选择方法

doi:10.11959/j.issn.2096-3750.2022.00299

物联网学报 ›› 2022, Vol. 6 ›› Issue (4): 158-168.doi: 10.11959/j.issn.2096-3750.2022.00299

基于背包模型的联邦学习客户端选择方法

郭佳慧¹, 陈卓越¹, 高玮¹, 王玺钧¹, 孙兴华¹, 高林²

¹ 中山大学，广东广州 510006
² 哈尔滨工业大学（深圳），广东深圳 518055

修回日期:2022-09-12 出版日期:2022-12-30 发布日期:2022-12-01
作者简介:郭佳慧（2000- ），女，中山大学电子与通信工程学院在读，主要研究方向为联邦学习等
陈卓越（2000- ），男，中山大学电子与通信工程学院硕士生，主要研究方向为拥塞控制、在线学习、联邦学习等
高玮（1999- ），男，中山大学电子秘通信工程学院硕士生，主要研究方向为联邦学习、无人机集群、目标跟踪等
王玺钧（1984- ），男，博士，中山大学电子与信息工程学院副教授，主要研究方向为信息年龄、强化学习等
孙兴华（1985- ），男，博士，中山大学电子与通信工程学院副教授，主要研究方向为下一代无线通信网络、智能通信等
高林（1980- ），男，博士，哈尔滨工业大学（深圳）电子与信息工程学院副教授，主要研究方向为移动边缘计算、群智计算、群体智能、博弈论、强化学习、联邦学习等
基金资助:
国家重点研发计划(2021YFB2900300);国家自然科学基金资助项目(62271513);国家自然科学基金资助项目(61972113);广东省基础与应用基础研究基金资助项目(2021A1515012631);深圳市科技研发基金资助项目(JCYJ20190806112215116);深圳市科技研发基金资助项目(KQTD20190929172545139);深圳市科技研发基金资助项目(ZDSYS20210623091808025)

Clients selection method based on knapsack model in federated learning

Jiahui GUO¹, Zhuoyue CHEN¹, Wei GAO¹, Xijun WANG¹, Xinghua SUN¹, Lin GAO²

¹ Sun Yat-sen University, Guangzhou 510006, China
² Harbin Institute of Technology (Shenzhen), Shenzhen 518055, China

Revised:2022-09-12 Online:2022-12-30 Published:2022-12-01
Supported by:
The National Key Research and Development Program of China(2021YFB2900300);The National Natural Science Foundation of China(62271513);The National Natural Science Foundation of China(61972113);Guangdong Basic and Applied Basic Research Foundation(2021A1515012631);The Shenzhen Science and Technology Program(JCYJ20190806112215116);The Shenzhen Science and Technology Program(KQTD20190929172545139);The Shenzhen Science and Technology Program(ZDSYS20210623091808025)

摘要/Abstract

摘要：

近年来，为了打破数据“壁垒”，联邦学习被广泛关注。联邦学习不需要客户端上传原始数据就能完成模型训练，保护了用户的隐私。针对客户端设备具有异构性的问题，考虑各个客户端对加速全局模型收敛的贡献程度和系统的通信开销，以最大化客户端在本地训练模型的权重变化量为优化目标，解决在一定系统训练周期下的联邦学习中的客户端选择优化问题。由此，提出了两个基于背包模型的联邦学习协议，分别是OfflineKP-FL协议和OnlineKP-FL协议。OfflineKP-FL协议基于离线背包模型选择合适的客户端参与全局模型的聚合更新。为了降低OfflineKP-FL协议的复杂度，进一步基于在线背包模型选择用户提出了OnlineKP-FL协议。通过仿真发现，在特定情况下OfflineKP-FL协议有更高的收敛速度，优于之前提出的方法。而与OfflineKP-FL协议和FedCS协议相比，OnlineKP-FL协议下，系统不仅每轮选择更少的用户，而且能够在FedCS协议所需时间的64.1%内完成模型训练，使全局模型达到相同精度。

关键词: 联邦学习, 客户端选择, 背包模型

Abstract:

In recent years, to break down data barriers, federated learning (FL) has received extensive attention.In FL, clientscan complete the model training without uploading the raw data, which protects the user’s data privacy.For the issue of clients’ heterogeneity, the contribution of each client to accelerating convergence of the global model as well as the communication cost in the system was considered, aiming at maximizing the weight change of the client's local training model, a client selection optimization problem in FL under theconstraint ofthe delay foreach training round was solved.Subsequently, two federated learning protocols based on the knapsack model were proposed, namely OfflineKP-FL protocol and OnlineKP-FL protocol.OfflineKP-FL protocol was based on the offline knapsack model to select appropriate clients to participate in the aggregation and update of the global model.In order to reduce the complexity of the OfflineKP-FL protocol, OnlineKP-FL protocol based on the online knapsack model to select clients was proposed.Through simulations, it is found that OfflineKP-FL protocol converges faster than the previously proposed methods in certain cases.Furthermore, compared with OfflineKP-FL protocol and FedCS protocol, underthe proposed OnlineKP-FL protocol, not only does the system select fewer clients per round, but also it can complete the model training in 64.1% of the time required by FedCS protocol to achieve the same accuracy for the global model.

Key words: federated learning, client selection, knapsack model

中图分类号:

TP391.4

郭佳慧, 陈卓越, 高玮, 王玺钧, 孙兴华, 高林. 基于背包模型的联邦学习客户端选择方法[J]. 物联网学报, 2022, 6(4): 158-168.

Jiahui GUO, Zhuoyue CHEN, Wei GAO, Xijun WANG, Xinghua SUN, Lin GAO. Clients selection method based on knapsack model in federated learning[J]. Chinese Journal on Internet of Things, 2022, 6(4): 158-168.

图/表 9

图1

图2

图3

表1

图4

图5

表2

图6

表3

参考文献 45

[1]	HAN M Q , SUN X H , ZHENG S H ,et al. Resource rationing for federated learning with reinforcement learning[C]// 2021 Proc.ComComAp.[S.l.:s.n], 2021: 150-155.
[2]	XU B , XIA W C , ZHANG J ,et al. Dynamic client association for energy-aware hierarchical federated learning[C]// 2021 IEEE Wireless Communications and Networking Conference (WCNC). Piscataway:IEEE Press, 2021: 1-6.
[3]	KONE?NY J . Stochastic,distributed and federated optimization for machine learning[J]. arXiv preprint, 2017,arXiv:1707.01155.
[4]	SAHU A K , LI T , SANJABI M ,et al. Federated optimization for heterogeneous networks[J]. arXiv preprint, 2018,arXiv:1812.06127.
[5]	LIU Y , MUPPALA J K , VEERARAGHAVAN M ,et al. Data center networks:topologies,architectures and fault-tolerance characteristics[M]. Heidelberg: Springer Science ＆ Business Media, 2013.
[6]	KONE?NY J , MCMAHAN H B , YU F X ,et al. Federated learning:strategies for improving communication efficiency[J]. arXiv preprint, 2016arXiv:1610.05492.
[7]	CALDAS S , KONE?NY J , MCMAHAN H B ,et al. Expanding the reach of federated learning by reducing client resource requirements[J]. arXiv preprint, 2018,arXiv:1812.07210.
[8]	NISHIO T , YONETANI R . Client selection for federated learning with heterogeneous resources in mobile edge[C]// Proceedings of ICC 2019- 2019 IEEE International Conference on Communications. Piscataway:IEEE Press, 2019: 1-7.
[9]	SHIN J , LI Y C , LIU Y X ,et al. FedBalancer:data and pace control for efficient federated learning on heterogeneous clients[C]// Proceedings of the 20th Annual International Conference on Mobile Systems,Applications and Services. New York:ACM Press, 2022: 436-449.
[10]	TAHIR A , CHEN Y , NILAYAM P . FedSS:federated learning with smart selection of clients[J]. arXiv preprint, 2022,arXiv:2207.04569.
[11]	REN J K , HE Y H , WEN D Z ,et al. Scheduling for cellular federated edge learning with importance and channel awareness[J]. IEEE Transactions on Wireless Communications, 2020,19(11): 7690-7703.
[12]	LEE J , KO H , PACK S . Adaptive deadline determination for mobile device selection in federated learning[J]. IEEE Transactions on Vehicular Technology, 2022,71(3): 3367-3371.
[13]	XIA W C , QUEKT Q S , GUO K ,et al. Multi-armed bandit-based client scheduling for federated learning[J]. IEEE Transactions on Wireless Communications, 2020,19(11): 7108-7123.
[14]	HUANG T S , LIN W W , WU W T ,et al. An efficiency-boosting client selection scheme for federated learning with fairness guarantee[J]. IEEE Transactions on Parallel and Distributed Systems, 2021,32(7): 1552-1564.
[15]	YANG H H , LIU Z Z , QUEK T Q S ,et al. Scheduling policies for federated learning in wireless networks[J]. IEEE Transactions on Communications, 2020,68(1): 317-333.
[16]	XU J , WANG H Q . Client selection and bandwidth allocation in wireless federated learning networks:along-term perspective[J]. IEEE Transactions on Wireless Communications, 2021,20(2): 1188-1200.
[17]	SHI W Q , ZHOU S , NIU Z S ,et al. Joint device scheduling and resource allocation for latency constrained wireless federated learning[J]. IEEE Transactions on Wireless Communications, 2021,20(1): 453-467.
[18]	RIBERO M , VIKALO H . Communication-efficient federated learning via optimal client sampling[EB]. 2020.
[19]	ABDULRAHMAN S , TOUT H , MOURAD A ,et al. FedMCCS:multicriteria client selection model for optimal IoT federated learning[J]. IEEE Internet of Things Journal, 2021,8(6): 4723-4735.
[20]	FRABONI Y , VIDAL R , KAMENI L ,et al. Clustered sampling:low-variance and improved represent ativity for clients selection in federated learning[C]// International Conference on Machine Learning. New York:PMLR, 2021: 3407-3416.
[21]	WANG L , GUO Y X , LIN T ,et al. Client selection in non convex federated learning:improved convergence analysis for optimal unbiased sampling strategy[EB]. 2022.
[22]	MARNISSI O , HAMMOUTI H E , BERGOU E H . Client selection in federated learning based on gradients importance[J]. arXiv preprint, 2021,arXiv:2111.11204.
[23]	NAGALAPATTI L , NARAYANAM R . Game of gradients:mitigating irrelevant clients in federated learning[C]// Proceedings of the AAAI Conference on Artificial Intelligence. 2021,35(10): 9046-9054.
[24]	TABATABAI S , MOHAMMED I , QOLOMANY B ,et al. Exploration and exploitation in federated learning to exclude clients with poisoned data[C]// Proceedings of 2022 International Wireless Communications and Mobile Computing (IWCMC). Piscataway:IEEE Press, 2022: 407-412.
[25]	WANG H , KAPLAN Z , NIU D ,et al. Optimizing federated learning on non-IID data with reinforcement learning[C]// Proceedings of IEEE INFOCOM 2020 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2020: 1698-1707.
[26]	ZHANG W Y , WANG X M , ZHOU P ,et al. Client selection for federated learning with non-IID data in mobile edge computing[J]. IEEE Access, 9: 24462-24474.
[27]	KANG J W , XIONG Z H , NIYATO D ,et al. Incentive mechanism for reliable federated learning:a joint optimization approach to combining reputation and contract theory[J]. IEEE Internet of Things Journal, 2019,6(6): 10700-10714.
[28]	KANG J W , XIONG Z H , NIYATO D ,et al. Reliable federated learning for mobile networks[J]. IEEE Wireless Communications, 2020,27(2): 72-80.
[29]	MAHMOOD A , SHENGQ Z , SIDDIQUIS A ,et al. When trust meets the Internet of vehicles:opportunities,challenges,and future prospects[C]// Proceedings of 2021 IEEE 7th International Conference on Collaboration and Internet Computing. Piscataway:IEEE Press, 2021: 60-67.
[30]	MAHMOOD A , SIDDIQUIS A , SHENGQ Z ,et al. Trust on wheels:towards secure and resource efficient IoV networks[J]. Computing, 2022,104(6): 1337-1358.
[31]	LIU Y N , LI K Q , JIN Y W ,et al. A novel reputation computation model based on subjective logic for mobile ad hoc networks[J]. Future Generation Computer Systems, 2011,27(5): 547-554.
[32]	ZOU Y , SHEN F , YAN F ,et al. Reputation-based regional federated learning for knowledge trading in blockchain-enhanced IoV[C]// Proceedings of 2021 IEEE Wireless Communications and Networking Conference. Piscataway:IEEE Press, 2021: 1-6.
[33]	SONG Z D , SUN H G , YANG H H ,et al. Reputation-based federated learning for secure wireless networks[J]. IEEE Internet of Things Journal, 2022,9(2): 1212-1226.
[34]	PERAZZONE J , WANG S Q , JIM Y ,et al. Communication-efficient device scheduling for federated learning using stochastic optimization[C]// Proceedings of IEEE INFOCOM 2022 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2022: 1449-1458.
[35]	WU H D , WANG P . Node selection toward faster convergence for federated learning on non-IID data[J]. IEEE Transactions on Network Science and Engineering, 2022,PP(99): 1.
[36]	MA J H , SUN X H , XIA W C ,et al. Client selection based on label quantity information for federated learning[C]// Proceedings of 2021 IEEE 32nd Annual International Symposium on Personal,Indoor and Mobile Radio Communications. Piscataway:IEEE Press, 2021: 1-6.
[37]	ZHAO J X , CHANG X Y , FENG Y H ,et al. Participant selection for federated learning with heterogeneous data in intelligent transport system[J]. IEEE Transactions on Intelligent Transportation Systems, 2022,PP(99): 1-10.
[38]	WANG S , LEEM Y , HOSSEINALIPOUR S ,et al. Device sampling for heterogeneous federated learning:theory,algorithms,and implementation[C]// Proceedings of IEEE INFOCOM 2021 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2021: 1-10.
[39]	WU W T , HE L G , LIN WW ,et al. Accelerating federated learning over reliability-agnostic clients in mobile edge computing systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2021,32(7): 1539-1551.
[40]	NGUYEN H T , SEHWAG V , HOSSEINALIPOUR S ,et al. Fast-convergent federated learning[J]. IEEE Journal on Selected Areas in Communications, 2021,39(1): 201-218.
[41]	YEGANEH Y , FARSHAD A , NAVAB N ,et al. Inverse distance aggregation for federated learning with non-IID data[C]// Domain Adaptation and Representation Transfer,and Distributed and Collaborative Learning, 2020: 150-159.
[42]	马嘉华, 孙兴华, 夏文超 ,等. 基于标签量信息的联邦学习节点选择算法[J]. 物联网学报, 2021,5(4): 46-53.
	MA J H , SUN X H , XIA W C ,et al. Node selection based on label quantity information in federated learning[J]. Chinese Journal on Internet of Things, 2021,5(4): 46-53.
[43]	MCMAHAN B , MOORE E , RAMAGE D ,et al. Communication-efficient learning of deep networks from decentralized data[C]// Artificial Intelligence and Statistics. New York:PMLR, 2017: 1273-1282.
[44]	CHAKRABARTY D , ZHOU Y , LUKOSE R . Online knapsack problems[C]// Workshop on Internet and Network Economics (WINE). 2008.
[45]	YANN L . The MNIST database of handwritten digits[EB]. 1998.

参数	取值
所有客户端在本地训练模型的速率服从的均匀分布的均值	5 bit/s
客户端k在本地训练局部模型的迭代次数c_k	5次
模型大小M_k	50 bit
客户端的传输功率 p_k	10^-3W
噪声功率σ²	10^-3W
客户端在本地训练模型时数据的批次大小	50个

协议每轮时间上限	FedCS协议	OnlineKP-FL协议	OfflineKP-FL协议
协议每轮时间上限		ToA@0.95
T_round=1 000	36 060	23 100	35 460
T_round=1 500	48 360	38 700	51 660
T_round=2 000	63 060	44 760	67 560

协议每轮时间上限	FedCS协议	OnlineKP-FL协议	OfflineKP-FL协议
协议每轮时间上限		平均每轮选择的客户端数量
T_round=1 000	8.8	2.8	9.2
T_round=1 500	14.2	4.8	12.0
T_round=2 000	17.0	6.3	13.8

基于背包模型的联邦学习客户端选择方法

Clients selection method based on knapsack model in federated learning

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 45

相关文章 4

Metrics

推荐阅读 0

[1]	耿光磊, 高博, 熊轲, 樊平毅, 陆杨, 王煜炜. 联邦学习赋能6G网络综述[J]. 物联网学报, 2023, 7(2): 50-66.
[2]	郭英芸, 高博, 张志飞, 张煜, 熊轲. 一种基于带宽分配的联邦学习激励机制[J]. 物联网学报, 2022, 6(4): 82-92.
[3]	马嘉华, 孙兴华, 夏文超, 王玺钧, 谭洪舟, 朱洪波. 基于标签量信息的联邦学习节点选择算法[J]. 物联网学报, 2021, 5(4): 46-53.
[4]	石光明, 肖泳, 李莹玉, 高大化, 谢雪梅. 面向万物智联的语义通信网络[J]. 物联网学报, 2021, 5(2): 26-36.