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

郭佳慧; 陈卓越; 高玮; 王玺钧; 孙兴华; 高林

doi:10.11959/j.issn.2096-3750.2022.00299

您当前的位置：

首页 >

文章列表页 >

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

理论与技术 | 更新时间：2024-08-16

- 基于背包模型的联邦学习客户端选择方法
- Clients selection method based on knapsack model in federated learning
- 物联网学报 2022年6卷第4期页码：158-168
- 作者机构：
  
  1. 中山大学，广东广州 510006
  2. 哈尔滨工业大学（深圳），广东深圳 518055
- 作者简介：
  
  [ "郭佳慧（2000- ），女，中山大学电子与通信工程学院在读，主要研究方向为联邦学习等" ]
  [ "陈卓越（2000- ），男，中山大学电子与通信工程学院硕士生，主要研究方向为拥塞控制、在线学习、联邦学习等" ]
  [ "高玮（1999- ），男，中山大学电子秘通信工程学院硕士生，主要研究方向为联邦学习、无人机集群、目标跟踪等" ]
  [ "王玺钧（1984- ），男，博士，中山大学电子与信息工程学院副教授，主要研究方向为信息年龄、强化学习等" ]
  [ "孙兴华（1985- ），男，博士，中山大学电子与通信工程学院副教授，主要研究方向为下一代无线通信网络、智能通信等" ]
  [ "高林（1980- ），男，博士，哈尔滨工业大学（深圳）电子与信息工程学院副教授，主要研究方向为移动边缘计算、群智计算、群体智能、博弈论、强化学习、联邦学习等" ]
- 基金信息：
  
  国家重点研发计划;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)
- DOI：10.11959/j.issn.2096-3750.2022.00299
  中图分类号： TP391.4
- 纸质出版日期：2022-12-30，
  
  网络出版日期：2022-12，
- 稿件说明：
移动端阅览
郭佳慧, 陈卓越, 高玮, 等. 基于背包模型的联邦学习客户端选择方法[J]. 物联网学报, 2022,6(4):158-168.

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.
郭佳慧, 陈卓越, 高玮, 等. 基于背包模型的联邦学习客户端选择方法[J]. 物联网学报, 2022,6(4):158-168. DOI： 10.11959/j.issn.2096-3750.2022.00299.

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

federated learningclient selectionknapsack model

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, 2016arXiv: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.

浏览量

319

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于选举策略的低空物联网稳定联邦学习方法

移动边缘计算中通信高效的联邦学习模型剪枝算法

联邦学习赋能6G网络综述

一种基于带宽分配的联邦学习激励机制

基于标签量信息的联邦学习节点选择算法