Clients selection method based on knapsack model in federated learning

Jiahui GUO; Zhuoyue CHEN; Wei GAO; Xijun WANG; Xinghua SUN; Lin GAO

doi:10.11959/j.issn.2096-3750.2022.00299

您当前的位置：

首页 >

文章列表页 >

Clients selection method based on knapsack model in federated learning

Theory and Technology | 更新时间：2024-08-16

- Clients selection method based on knapsack model in federated learning
- Chinese Journal on Internet of Things Vol. 6, Issue 4, Pages: 158-168(2022)
- 作者机构：
  
  1. 中山大学，广东广州 510006
  2. 哈尔滨工业大学（深圳），广东深圳 518055
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-3750.2022.00299
  CLC： TP391.4
- Online First：2022-12，
  
  Published：30 December 2022
- 稿件说明：
移动端阅览
Jiahui GUO, Zhuoyue CHEN, Wei GAO, et al. Clients selection method based on knapsack model in federated learning[J]. Chinese Journal on Internet of Things, 2022, 6(4): 158-168.
DOI：

Jiahui GUO, Zhuoyue CHEN, Wei GAO, et al. Clients selection method based on knapsack model in federated learning[J]. Chinese Journal on Internet of Things, 2022, 6(4): 158-168. DOI： 10.11959/j.issn.2096-3750.2022.00299.

摘要

近年来，为了打破数据“壁垒”，联邦学习被广泛关注。联邦学习不需要客户端上传原始数据就能完成模型训练，保护了用户的隐私。针对客户端设备具有异构性的问题，考虑各个客户端对加速全局模型收敛的贡献程度和系统的通信开销，以最大化客户端在本地训练模型的权重变化量为优化目标，解决在一定系统训练周期下的联邦学习中的客户端选择优化问题。由此，提出了两个基于背包模型的联邦学习协议，分别是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.

关键词

Keywords

references

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 .

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 .

KONEČNÝ J . Stochastic,distributed and federated optimization for machine learning [J ] . arXiv preprint , 2017 ,arXiv:1707.01155.

SAHU A K , LI T , SANJABI M , et al . Federated optimization for heterogeneous networks [J ] . arXiv preprint , 2018 ,arXiv:1812.06127.

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 .

KONEČNÝ J , MCMAHAN H B , YU F X , et al . Federated learning:strategies for improving communication efficiency [J ] . arXiv preprint , 2016 arXiv:1610.05492.

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.

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 .

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 .

TAHIR A , CHEN Y , NILAYAM P . FedSS:federated learning with smart selection of clients [J ] . arXiv preprint , 2022 ,arXiv:2207.04569.

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 .

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 .

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 .

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 .

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 .

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 .

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 .

RIBERO M , VIKALO H . Communication-efficient federated learning via optimal client sampling [EB ] . 2020 .

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 .

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 .

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 .

MARNISSI O , HAMMOUTI H E , BERGOU E H . Client selection in federated learning based on gradients importance [J ] . arXiv preprint , 2021 ,arXiv:2111.11204.

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

马嘉华 , 孙兴华 , 夏文超 , 等 . 基于标签量信息的联邦学习节点选择算法 [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 .

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 .

CHAKRABARTY D , ZHOU Y , LUKOSE R . Online knapsack problems [C ] // Workshop on Internet and Network Economics (WINE) . 2008 .

YANN L . The MNIST database of handwritten digits [EB ] . 1998 .

Views

507

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Client selection for federated learning against label flipping attacks

Research on low-latency transmission migration method for federated learning models in the Internet of vehicles

Latency-aware semi-synchronous federated learning client resource co-scheduling scheme for IIoT

Joint multi-dimensional resource optimization for model compression in wireless federated learning

Related Author

LI Jianxin

CHEN Siguang

Zhang Yin

Zhang Ke

Jiang Chi

Yin Hongbo

Wang Shuai

XIA Tianle

Related Institution

School of Internet of Things, Nanjing University of Posts and Telecommunications

Guangdong Intelligent Robot Research Institute

School of Information and Communication Engineering, University of Electronic Science and Technology of China

Shenzhen Institute for Advanced Study, UESTC

School of Communications and Information Engineering, Nanjing University of Posts and Telecommunications

⁰