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

doi:10.11959/j.issn.2096-3750.2022.00299

Abstract

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

CLC Number:

TP391.4

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.

Figures/Tables 9

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

参数	取值
所有客户端在本地训练模型的速率服从的均匀分布的均值	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

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 45

Related Articles 5

Metrics

Recommended 0

[1]	Guanglei GENG, Bo GAO, Ke XIONG, Pingyi FAN, Yang LU, Yuwei WANG. A survey of federated learning for 6G networks [J]. Chinese Journal on Internet of Things, 2023, 7(2): 50-66.
[2]	Yingyun GUO, Bo GAO, Zhifei ZHANG, Yu ZHANG, Ke XIONG. An incentive mechanism with bandwidth allocation for federated learning [J]. Chinese Journal on Internet of Things, 2022, 6(4): 82-92.
[3]	Jiahua MA, Xinghua SUN, Wenchao XIA, Xijun WANG, Hongzhou TAN, Hongbo ZHU. Node selection based on label quantity information in federated learning [J]. Chinese Journal on Internet of Things, 2021, 5(4): 46-53.
[4]	Guangming SHI, Yong XIAO, Yingyu LI, Dahua GAO, Xuemei XIE. Semantic communication networking for the intelligence of everything [J]. Chinese Journal on Internet of Things, 2021, 5(2): 26-36.
[5]	Xiaoran CAI,Xiaopeng MO,Jie XU. D2D computation task offloading for efficient federated learning [J]. Chinese Journal on Internet of Things, 2019, 3(4): 82-90.