基于主从博弈的分层联邦学习激励机制研究_贾云健.pdf

基于主从博弈的分层联邦学习激励机制研究贾云健黄宇梁靓*万杨亮周继华(重庆大学微电子与通信工程学院重庆400044)(95696部队重庆400030)(重庆金美通信有限责任公司复杂环境通信重庆市重点实验室重庆400030)摘要：为了优化分层联邦学习(FL)全局模型的训练时延，针对实际场景中终端设备存在自私性的问题，该文提出一种基于博弈论的激励机制。在激励预算有限的条件下，得到了终端设备和边缘服务器之间的均衡解和最小的边缘模型训练时延。考虑终端设备数量不同，设计了基于主从博弈的可变激励训练加速算法，使得一次全局模型训练时延达到最小。仿真结果显示，所提出的算法能够有效降低终端设备自私性带来的影响，提高分层联邦学习全局模型的训练速度。关键词：分层联邦学习；博弈论；激励机制中图分类号：TN92文献标识码：A文章编号：1009-5896(2023)04-1366-08DOI:10.11999/JEIT220175Research on Hierarchical Federated Learning IncentiveMechanism Based on Master-Slave GameJIAYunjianHUANGYuLIANGLiangWANYangliangZHOUJihua(School of Microelectronics and Communication Engineering,Chongqing University,Chongqing 400044,China)(95696 Troops,Chongqing 400030,China)(Chongqing Key Laboratory of Complex Environment Communication,Chongqing Jinmei CommunicationCo.Ltd.Chongqing 400030,China)Abstract:InordertooptimizethetrainingdelayofthehierarchicalFederatedLearning(FL)globalmodel,focusingontheselfishnessoftheterminaldevicesintheactualscene,anincentivemechanismbasedongametheoryisproposed.Undertheconditionoflimitedincentivebudget,theequilibriumsolutionbetweenterminaldevicesandedgeserversandtheminimumedgemodeltrainingdelayareobtained.Consideringthedifferentnumberofterminaldevices,avariableincentivetrainingaccelerationalgorithmbasedonStackelberggameisdesignedtominimizethetrainingdelayofaglobalmodel.Simulationresultsdemonstratethattheproposedalgorithmcaneffectivelyreducetheimpactofterminaldevicesselfishnessandimprovethetrainingspeedofhierarchicalfederatedlearningglobalmodel.Key words:HierarchicalFederatedLearning(FL);Gametheory;Incentivemechanism1 引言随着各种智能设备的不断普及，依赖数据和计算能力的机器学习技术得到了迅速发展。为了解决机器学习模型训练面临的数据安全问题，2017年谷歌提出了一种新的分布式机器学习方法联邦学习(FederatedLearning,FL)1。在联邦学习的架构中，设备用户的原始数据不会上传至数据中心，而是留在设备本地进行模型训练，设备只上传训练出的模型参数2。联邦学习将机器学习与在中心服务器中获取、存储和训练数据分离开来，实现了用户数据隐私保护3。自从谷歌提出联邦学习这个概念后，联邦学习就成为机器学习领域的一个研究热点。McMahan等人4提出了一个基于模型平均的联邦学习实用模型，并进行了广泛的实证评估，这篇文章提出的联收稿日期：2022-02-25；改回日期：2022-06-27；网络出版：2022-08-16*通信作者：梁靓基金项目：国家自然科学基金(62071075,61971077)，重庆市自然科学基金(cstc2020jcyj-msxmX0704)FoundationItems:TheNationalNaturalScienceFoundationofChina(62071075,61971077),TheNaturalScienceFoundationofChongqing(cstc2020jcyj-msxmX0704)第45卷第4期电子与信息学报Vol.45No.42023年4月JournalofElectronics&InformationTechnologyApr.2023邦平均算法(FederatedAveragealgorithm,FedAvg)成为一个经典的联邦学习算法。在此基础上，研究者针对FedAvg算法优化，进行了一系列研究。Li等人5在FedAvg的基础上引入了一个修正项，提出了FedProx(FedAvgwiththeProximalterm)算法，它允许在设备之间局部地执行可变量的工作，并且依赖这个修正项来确保方法的稳定性，解决了联邦学习固有的系统异质性和统计异质性问题。Mills等人6采用分布式Adam优化技术和模型压缩技术，提出了一种改进的FedAvg算法CE-FedAvg(Communication-EfficientFedAvg)，该算法可以减少达到目标精度所需的通信轮次和每一轮需要加载的数据量，解决了联邦学习在物联网边缘计算的高效通信问题。Li等人7则从算法的公平性角度出发，提出了q-FairFL算法，它重新权衡了FedAvg算法中的目标函数，在损失函数中分配更高的权重给损失较高的设备，从而使训练精度分布更加均匀。为了进一步优化联邦学习的性能，有研究者对传统联邦学习框架进行了改进。Liu等人8将基于边缘和基于云的联邦学习结合起来，提出了分层联邦学习架构，该分层联邦学习架构与基于云的联邦学习架构相比，模型训练时间和终端设备的能耗都得到了降低。Abad等人9通过分簇法研究了在蜂窝网中的分层联邦问题，优化了分层联邦学习的全局通信时延。然而不管是针对传统联邦学习框架还是分层联邦学习框架，目前已有的研究大多集中在优化联邦学习算法以提高模型训练性能上，用于激励终端设备参加模型训练的激励机制在很大程度上却被忽视了。大多数流行的分布式训练算法都是使用小批量随机梯度下降10，这在实际训练中，需要等待每一个同步批次中最慢的设备，导致随机优化的完全同步往往很慢，即受到“掉队效应”11的影响，这在异构网络中更为明显。同时，目前的大多数研究都做出了一个乐观的假设，即所有的终端设备在受到邀请时，都将无条件地参与联邦学习。这在现实世界中是不实际的，因为在联邦模型训练过程中，终端设备在计算和通信方面承受着相当大的开销12，如果没有精心设计的激励机制，具有自私性的终端设备将不会拿出足够的资源甚至不愿意加入到联邦学习任务中来，这将导致十分严重的“掉队效应”，使得模型的训练时间大大增加，影响联邦学习的使用。针对上述问题，本文在分层联邦学习框架下，考虑实际场景中每个边缘服务器下连接的终端设备数量不同，首先对模型训练过程进行了建模分析，得出一次全局模型训练的时间消耗和资源消耗。然后在终端设备和边缘服务器之间设计了两层主从博弈(即Stackelberg博弈13)，通过调整分配给每个边缘服务器的激励预算值，提出了基于主从博弈的可变激励训练加速算法。该算法能够刺激终端设备更加积极地参与到联邦学习的任务中来，有效地减小“掉队效应”的影响，从而最小化全局模型训练时间。2 系统模型CN=i:i=1,2,.,NiMi=m:m=1,2,.,M如图1所示在分层FL架构中，假设有一个云服务器，边缘服务器集合为，边缘服务器 下连接的终端设备集合为，每个终端设备集合大小不相同。考虑完全同步的FL，完成一次全局训练过程如下：m (0,1)m终端设备端。终端设备基于本地的数据集来进行本地模型训练，假设所有的终端设备的本地数据集大小相同，为了达到相同的本地模型精度，终端设备需要进行迭代的次数可以表示为14L()=log2(1)(1)fi:mimCmL()im其中，是一个取决于数据集大小和机器学习任务的参数。表示边缘服务器 下的终端设备进行本地计算时的CPU频率，表示完成1次本地迭代计算任务需要的总的CPU转圈数。那么完成次本地迭代，边缘服务器 下的终端设备所消耗的能量和时间可以分别表示为ecmpi:m=L()kCm(fi:m)2(2)tcmpi:m=L()Cmfi:m(3)kiqi:mimmqi:mfi:m其中，是一个取决于芯片结构的系数。为了使终端设备投入更多的计算资源以减小本地训练模型所花的时间，边缘服务器端会引入激励机制，即边缘服务器 向其下面的终端设备提供奖励，表示边缘服务器 对其服务范围内的终端设备提供的CPU频率单价，那么终端设备迭代一次获得的收入为。本地模型精度达到 之后，终端设备图1系统模型图第4期贾云健等：基于主从博弈的分层联邦学习激励机制研究1367B向对应的边缘服务器上传训练得到的参数。假设每个边缘服务器能够分配给终端设备的信道总带宽均为，边缘服务器将其均分给下面的每一个终端设备，那么传输率可以表示为rmi=Bmlog2(1+hmumN0)(4)N0umhmmi其中，为噪声功率，为传输功率，为信道增益。终端设备完成一次参数传输至边缘服务器所需要的时间为tcommi=dmrmi(5)dmm其中，表示终端设备传输的参数量，所需要的能量为ecommi=tcommium(6)i边缘服务器端。边缘服务器 在收到终端设备传来的参数后，会进行聚合然后再分发下去。以上的过程会迭代多次，直到所有的边缘服务器达到一个相同边缘服务器模型精度。为了达到所需精度，对于一个凸的机器学习任务，边缘服务器需要迭代的次数可以表示为14I(,)=(log2(1)1 (7)iI(,)其中，是取决于学习任务的参数。由于边缘服务器通常拥有强大的计算能力和稳定的能量供给，所以边缘服务器端的模型参数聚合和分发所产生的时间与能量消耗在本文中没有考虑。对于终端设备来说，接收分发下来的参数所消耗的时间和能量相比于它上传参数要小得多，在这里本文也不予考虑。因此，边缘服务器 完成次迭代，所需要的时间为Ti=I(,)maxmMi(tcmpi:m)+tcommi(8)m终端设备消耗的总能量为Ei:m=I(,)(ecmpi:m+ecommi)(9)ridi边缘服务器会向云服务器上传满足精度要求的边缘服务器模型参数，假设边缘服务器的传输率都为，上传的参数量为，那么上传1次参数，边缘服务器的时间和能量消耗分别为tcomiC=diri(10)ecomiC=uitcomiC(11)ui其中，表示边缘服务器的传输功率。云服务器端：在接收到边缘服务器端传来的模型参数后，云服务器端进行参数聚合并更新模型，这样就完成了一次全局迭代。相较于其他环节，这个聚合时间非常短，本文也不考虑。那么，一次全局迭代，所需要的总时间为T=maxiNTi+tcomiC(12)ViWii1TiiRciRc1Ti云服务器负责分配激励预算给每个边缘服务器，总预算为。边缘服务器 所分配到的激励预算为。定义边缘服务器 对于一次全局迭代的时间贡献度为，时间贡献度越大，表示边缘服务器 迭代到所要求的精度的时间越短。云服务器会基于每个边缘服务器的时间贡献度来