异构边缘计算环境下异步联邦学习的节点分组与分时调度策略

doi:10.11959/j.issn.1000-436x.2023196

通信学报 ›› 2023, Vol. 44 ›› Issue (11): 79-93.doi: 10.11959/j.issn.1000-436x.2023196

• 专题：复杂环境下分布式边缘智能 • 上一篇

异构边缘计算环境下异步联邦学习的节点分组与分时调度策略

马千飘¹, 贾庆民¹, 刘建春²^,³, 徐宏力²^,³, 谢人超¹^,⁴, 黄韬¹^,⁴

¹ 网络通信与安全紫金山实验室未来网络研究中心，江苏南京 211111
² 中国科学技术大学计算机科学与技术学院，安徽合肥 230026
³ 中国科学技术大学苏州高等研究院，江苏苏州 215123
⁴ 北京邮电大学网络与交换技术国家重点实验室，北京 100876

修回日期:2023-10-08 出版日期:2023-11-01 发布日期:2023-11-01
作者简介:马千飘（1993− ），男，贵州遵义人，博士，网络通信与安全紫金山实验室研究员，主要研究方向为边缘计算、联邦学习、分布式机器学习等
贾庆民（1990− ），男，山东泰安人，博士，网络通信与安全紫金山实验室研究员，主要研究方向为算力网络、确定性网络、边缘智能、工业互联网等
刘建春（1996− ），男，江苏盐城人，中国科学技术大学特任副研究员、硕士生导师，主要研究方向为物联网、边缘计算、分布式机器学习等
徐宏力（1980− ），男，浙江宁波人，中国科学技术大学教授、博士生导师，主要研究方向为物联网、边缘计算、软件定义网络等
谢人超（1984− ），男，福建南平人，博士，北京邮电大学副教授、硕士生导师，主要研究方向为信息中心网络、移动网络内容分发技术和移动边缘计算等
黄韬（1980− ），男，重庆人，博士，北京邮电大学教授、博士生导师，主要研究方向为新型网络体系架构、内容分发网络、软件定义网络等
基金资助:
国家自然科学基金资助项目(U1709217);国家自然科学基金资助项目(61936015);国家自然科学基金资助项目(92267301)

Client grouping and time-sharing scheduling for asynchronous federated learning in heterogeneous edge computing environment

Qianpiao MA¹, Qingmin JIA¹, Jianchun LIU²^,³, Hongli XU²^,³, Renchao XIE¹^,⁴, Tao HUANG¹^,⁴

¹ Future Network Research Center, Purple Mountain Laboratories, Nanjing 211111, China
² School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China
³ Suzhou Institute for Advanced Research, University of Science and Technology of China, Suzhou 215123, China
⁴ State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China

Revised:2023-10-08 Online:2023-11-01 Published:2023-11-01
Supported by:
The National Natural Science Foundation of China(U1709217);The National Natural Science Foundation of China(61936015);The National Natural Science Foundation of China(92267301)

摘要/Abstract

摘要：

为了克服异构边缘计算环境下联邦学习的3个关键挑战，边缘异构性、非独立同分布数据及通信资源约束，提出了一种分组异步联邦学习（FedGA）机制，将边缘节点分为多个组，各个分组间通过异步方式与全局模型聚合进行全局更新，每个分组内部节点通过分时方式与参数服务器通信。理论分析建立了 FedGA 的收敛界与分组间数据分布之间的定量关系。针对分组内节点的通信提出了分时调度策略魔镜法（MMM）优化模型单轮更新的完成时间。基于FedGA的理论分析和MMM，设计了一种有效的分组算法来最小化整体训练的完成时间。实验结果表明，FedGA和MMM相对于现有最先进的方法能降低30.1%～87.4%的模型训练时间。

关键词: 边缘计算, 联邦学习, 非独立同分布数据, 异构性, 收敛分析

Abstract:

To overcome the three key challenges of federated learning in heterogeneous edge computing, i.e., edge heterogeneity, data Non-IID, and communication resource constraints, a grouping asynchronous federated learning (FedGA) mechanism was proposed.Edge nodes were divided into multiple groups, each of which performed global updated asynchronously with the global model, while edge nodes within a group communicate with the parameter server through time-sharing communication.Theoretical analysis established a quantitative relationship between the convergence bound of FedGA and the data distribution among the groups.A time-sharing scheduling magic mirror method (MMM) was proposed to optimize the completion time of a single round of model updating within a group.Based on both the theoretical analysis for FedGA and MMM, an effective grouping algorithm was designed for minimizing the overall training completion time.Experimental results demonstrate that the proposed FedGA and MMM can reduce model training time by 30.1%～87.4% compared to the existing state-of-the-art methods.

Key words: edge computing, federated learning, Non-IID, heterogeneity, convergence analysis

中图分类号:

TP301

马千飘, 贾庆民, 刘建春, 徐宏力, 谢人超, 黄韬. 异构边缘计算环境下异步联邦学习的节点分组与分时调度策略[J]. 通信学报, 2023, 44(11): 79-93.

Qianpiao MA, Qingmin JIA, Jianchun LIU, Hongli XU, Renchao XIE, Tao HUANG. Client grouping and time-sharing scheduling for asynchronous federated learning in heterogeneous edge computing environment[J]. Journal on Communications, 2023, 44(11): 79-93.

图/表 15

图1

图2

图3

图4

图5

图6

图7

图8

表1

图9

图10

图11

图12

图13

图14

参考文献 25

[1]	彭安妮, 周威, 贾岩 ,等. 物联网操作系统安全研究综述[J]. 通信学报, 2018,39(3): 22-34.
	PENG A N , ZHOU W , JIA Y ,et al. Survey of the Internet of things operating system security[J]. Journal on Communications, 2018,39(3): 22-34.
[2]	谢人超, 廉晓飞, 贾庆民 ,等. 移动边缘计算卸载技术综述[J]. 通信学报, 2018,39(11): 138-155.
	XIE R C , LIAN X F , JIA Q M ,et al. Survey on computation offloading in mobile edge computing[J]. Journal on Communications, 2018,39(11): 138-155.
[3]	MCMAHAN H B , MOORE E , RAMAGE D ,et al. Communication-efficient learning of deep networks from decentralized data[J]. arXiv Preprint,arXiv:1602.05629, 2016.
[4]	LI M , ZHOU L , YANG Z C ,et al. Parameter server for distributed machine learning[C]// Big Learning NIPS Workshop. Massachusetts:MIT Press, 2013: 1-10.
[5]	KONE?NY J , MCMAHAN H B , RAMAGE D ,et al. Federated optimization:distributed machine learning for on-device intelligence[J]. arXiv Preprint,arXiv:1610.02527, 2016.
[6]	WANG S Q , TUOR T , SALONIDIS T ,et al. Adaptive federated learning in resource constrained edge computing systems[J]. IEEE Journal on Selected Areas in Communications, 2019,37(6): 1205-1221.
[7]	MAO Y Y , YOU C S , ZHANG J ,et al. A survey on mobile edge computing:the communication perspective[J]. IEEE Communications Surveys ＆ Tutorials, 2017,19(4): 2322-2358.
[8]	ZHAO Y , LI M , LAI L ,et al. Federated learning with non-IID data[J]. arXiv Preprint,arXiv:1806.00582, 2018.
[9]	XIE C , KOYEJO S , GUPTA I . Asynchronous federated optimization[J]. arXiv Preprint,arXiv:1903.03934, 2019.
[10]	CHEN Y J , NING Y , SLAWSKI M ,et al. Asynchronous online federated learning for edge devices with non-IID data[C]// Proceedings of IEEE International Conference on Big Data (Big Data). Piscataway:IEEE Press, 2021: 15-24.
[11]	CHAI Z , CHEN Y J , ZHAO L ,et al. FedAT:a communication-efficient federated learning method with asynchronous tiers under Non-IID data[J]. arXiv Preprint,arXiv:2010.05958, 2020.
[12]	FEYZMAHDAVIAN H R , AYTEKIN A , JOHANSSON M . A delayed proximal gradient method with linear convergence rate[C]// Proceedings of 2014 IEEE International Workshop on Machine Learning for Signal Processing (MLSP). Piscataway:IEEE Press, 2014: 1-6.
[13]	LUO B , LI X , WANG S Q ,et al. Cost-effective federated learning in mobile edge networks[J]. IEEE Journal on Selected Areas in Communications, 2021,39(12): 3606-3621.
[14]	陶梅霞, 王栋, 孙瑞 ,等. 联邦学习中基于时分多址接入的用户调度策略[J]. 通信学报, 2021,42(6): 16-29.
	TAO M X , WANG D , SUN R ,et al. TDMA-based user scheduling policies for federated learning[J]. Journal on Communications, 2021,42(6): 16-29.
[15]	MA Q P , XU Y , XU H L ,et al. FedSA:a semi-asynchronous federated learning mechanism in heterogeneous edge computing[J]. IEEE Journal on Selected Areas in Communications, 2021,39(12): 3654-3672.
[16]	MORELLI M , KUO C C J , PUN M O . Synchronization techniques for orthogonal frequency division multiple access (OFDMA):a tutorial review[J]. Proceedings of the IEEE, 2007,95(7): 1394-1427.
[17]	NELSON R , KLEINROCK L . Spatial TDMA:a collision-free multihop channel access protocol[J]. IEEE Transactions on Communications, 1985,33(9): 934-944.
[18]	MO X P , XU J . Energy-efficient federated edge learning with joint communication and computation design[J]. Journal of Communications and Information Networks, 2021,6(2): 110-124.
[19]	CHEN M Z , POOR H V , SAAD W ,et al. Convergence time optimization for federated learning over wireless networks[J]. IEEE Transactions on Wireless Communications, 2021,20(4): 2457-2471.
[20]	XU H L , CHEN M , MENG Z Y ,et al. Decentralized machine learning through experience-driven method in edge networks[J]. IEEE Journal on Selected Areas in Communications, 2022,40(2): 515-531.
[21]	BLAZEWICZ J , ECKER K H , PESCH E ,et al. Handbook on scheduling:from theory to practice[M]. Cham: Springer International Publishing, 2019.
[22]	RAPPAPORT T . Wireless communications:principles and practice[J]. Microwave Journal, 2002,45: 128-129.
[23]	LECUN Y , BOTTOU L , BENGIO Y ,et al. Gradient-based learning applied to document recognition[J]. Proceedings of the IEEE, 1998,86(11): 2278-2324.
[24]	KRIZHEVSKY A . Learning multiple layers of features from tiny images[R]. 2009.
[25]	CHAI Z , ALI A , ZAWAD S ,et al. TiFL:a tier-based federated learning system[C]// Proceedings of the 29th International Symposium on High-Performance Parallel and Distributed Computing. New York:ACM Press, 2020: 125-136.

异构边缘计算环境下异步联邦学习的节点分组与分时调度策略

Client grouping and time-sharing scheduling for asynchronous federated learning in heterogeneous edge computing environment

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 25

相关文章 15

Metrics

推荐阅读 0

[1]	唐冬, 黄栩蔚, 罗至威, 赵赛, 黄高飞. 无线供能智能反射面辅助移动边缘计算系统设计与优化[J]. 通信学报, 2023, 44(9): 79-92.
[2]	期治博, 杜磊, 霍如, 杨帆, 黄韬. 基于边缘计算的多摄像头视频协同分析方法[J]. 通信学报, 2023, 44(8): 14-26.
[3]	陈晓霖, 昝道广, 吴炳潮, 关贝, 王永吉. 面向纵向联邦学习的对抗样本生成算法[J]. 通信学报, 2023, 44(8): 1-13.
[4]	马卓, 金嘉玉, 杨易龙, 刘洋, 应作斌, 李腾, 张俊伟. 基于门限同态加密的自适应联邦学习安全聚合方案[J]. 通信学报, 2023, 44(7): 76-85.
[5]	马鑫迪, 李清华, 姜奇, 马卓, 高胜, 田有亮, 马建峰. 面向Non-IID数据的拜占庭鲁棒联邦学习[J]. 通信学报, 2023, 44(6): 138-153.
[6]	金彪, 李逸康, 姚志强, 陈瑜霖, 熊金波. GenFedRL：面向深度强化学习智能体的通用联邦强化学习框架[J]. 通信学报, 2023, 44(6): 183-197.
[7]	张佳乐, 朱诚诚, 孙小兵, 陈兵. 基于GAN的联邦学习成员推理攻击与防御方法[J]. 通信学报, 2023, 44(5): 193-205.
[8]	田有亮, 吴柿红, 李沓, 王林冬, 周骅. 基于激励机制的联邦学习优化算法[J]. 通信学报, 2023, 44(5): 169-180.
[9]	姜慧, 何天流, 刘敏, 孙胜, 王煜炜. 面向异构流式数据的高性能联邦持续学习算法[J]. 通信学报, 2023, 44(5): 123-136.
[10]	余晟兴, 陈泽凯, 陈钟, 刘西蒙. DAGUARD：联邦学习下的分布式后门攻击防御方案[J]. 通信学报, 2023, 44(5): 110-122.
[11]	李开菊, 许强, 王豪. 冗余数据去除的联邦学习高效通信方法[J]. 通信学报, 2023, 44(5): 79-93.
[12]	谢人超, 文雯, 唐琴琴, 刘云龙, 谢高畅, 黄韬. 轨道交通移动边缘计算网络安全综述[J]. 通信学报, 2023, 44(4): 201-215.
[13]	苏新, 张桂福, 行鸿彦, Zenghui Wang. 基于平衡生成对抗网络的海洋气象传感网入侵检测研究[J]. 通信学报, 2023, 44(4): 124-136.
[14]	鲁蔚锋, 李宁, 徐佳, 徐力杰, 徐建. 多接入边缘计算中相关性任务的联合调度算法[J]. 通信学报, 2023, 44(4): 87-98.
[15]	余雪勇, 邱礼翔, 宋家宁, 朱洪波. 无人机辅助边缘计算中安全通信与能效优化策略[J]. 通信学报, 2023, 44(3): 45-54.

分布	FedGA	TiFL
IID	0	0
Non-IID	0.191	0.394