基于无线D2D网络的分层联邦学习

刘翀赫，余官定，刘胜利

(浙江大学 信息与电子工程学院，浙江 杭州 310027)

在移动数据流量爆炸式增长的驱动下，机器学习在大量研究领域取得显著的成功，例如计算机视觉和自然语言处理.随着越来越多的边缘设备接入互联网，无线网络中的训练数据可能会被各种设备收集，由于严格的隐私协议和稀缺的通信资源，这些数据无法被传输到中央服务器.为了克服这些挑战，最近提出的联邦学习已经成为一种流行的分布式机器学习技术[1-2]，该技术使许得多设备能够训练本地模型并与服务器交换模型参数或梯度.联邦学习系统中的设备通常是以星形拓扑连接[3]，例如在典型的参数服务器架构中，每个设备根据自己的数据集训练一个局部模型后上传到服务器，服务器通常使用加权平均值将其聚合为全局模型[4].在大规模设备共同参与联邦学习训练的场景中，由于中央服务器需要聚合来自数百个设备的模型信息，通信资源成为影响联邦学习系统收敛速率的关键因素[5].当系统中可用的网络带宽较低时，中心化架构会导致网络中产生流量拥塞，模型训练的收敛速率会显著下降.

Lim等[6]提出分层联邦学习架构来缓解参数服务器的带宽压力，利用簇内聚合避免频繁地全局聚合，减轻中央节点的通信成本.Wang等[7]提出一种称为FedCH的联邦学习机制，通过构建一个特殊的集群拓扑并执行分层聚合进行训练.一个集群中的设备将本地更新同步发送到中心节点进行聚合，而所有中心节点采用异步的方式进行全局聚合.大多数的分层联邦学习工作主要是以模型平均的方式进行簇内聚合，这需要在每个簇中存在一个中心节点来收集模型参数或梯度，集中式架构会在中心节点造成拥塞.在簇内无服务器的实际场景中，往往难以找到与簇内其他设备间都有良好通信链路的中心节点.

为了实现通信高效的联邦学习，将传统的设备到服务器通信与设备直通(device-to-device, D2D)通信相结合[8-9]，提出一种基于无线D2D网络的分层联邦学习.依据所处的地理位置将边缘设备划分为多个簇，各个簇同时进行去中心化学习[10]，通过共同训练机器学习模型来确保实现共同的学习目标.在训练的2个全局聚合间隔期间，设备在各自的数据集上执行若干次随机梯度下降(stochastic gradient descent, SGD)迭代，通过簇内的无线D2D通信网络，设备定期地与邻居设备交换模型参数进行簇内模型聚合.在全局聚合时，每个簇中只有一个设备需要将模型上传到服务器，这个设备被定义为簇头.服务器根据模型平均算法，对所有簇头的本地模型进行全局聚合.簇头的模型反映其集群经过去中心化训练后得到的本地模型的特征[11-12].

与大多数传统的设备需要上传本地模型的联邦学习不同，所提方法大大减少了设备与基站之间通信的数据量，降低了中央基站发生流量拥塞的可能性.对于全局聚合期间的簇头选择与带宽分配问题进行联合优化，使用图中节点的度来衡量模型性能，并基于动态规划设计最优簇头选择和带宽分配的算法，使用真实数据集的仿真结果证明无线D2D网络的分层联邦学习算法的性能.该算法通过分层聚合和D2D通信，减少模型收敛所需的训练时间，同时将分层联邦学习算法的扩展到簇内无服务器的系统结构.

1 系统模型与算法

1.1 系统模型

考虑具有一个边缘服务器和N个边缘设备的联邦学习系统，目的是协作训练一个机器学习模型，如图1所示.所有设备根据地理位置的相近性被划分为C个簇，由集合{S1,···,SC}表 示，第k个簇Sk包含nk=|Sk|个边缘设备.假设D2D通信是双向的，簇内设备之间的D2D链路是否阻塞根据设备的发射功率、设备之间的信道条件及物理距离确定[13-14].簇Sk中未阻塞的D2D链路构成图为Gk=(Sk,Ek)，其 中Ek为边的 集 合.为了 确 保簇内 训练 能够收敛，假设Gk为连通的图[15].

图1 基于无线D2D网络的分层联邦学习系统模型Fig.1 System model of hierarchical federated learning system based on wireless D2D networks

边缘设备i∈Sk通过感知物理环境来收集数据，并构成本地数据集由于簇内不存在可以与所有设备通信的中央节点，考虑在每个簇内以去中心化学习的方式训练模型.对于边缘设备i∈Sk，用Ni⊆Sk表示在连通图Gk中与其相邻的设备集合.为了减小传输时间和提高模型的性能，在服务器上实现一个调度器来执行簇头选择[16]和带宽资源分配联合优化算法.

1.2 分层联邦学习算法

在联邦学习系统中，每个设备i基于自身的数据集Di训练出一个本地 模 型.设 备i处的 数据分布的局部经验损失函数为

式中：ωi为本地模型参数；ξ为参与迭代 训练的数据样 本；L(ωi,ξ) 为样本损失函数，量化数据样本ξ上的预测误差.

分层联邦学习算法主要目标是优化全局模型参数 ω，以最小化与所有设备关联的全局损失函数为

在无线D2D网络的分层联邦学习中，训练过程分为本地模型更新、簇内聚合和全局聚合3个步骤， 这些步骤的组合称为一个训练轮次.

1)本地模型更新：每个设备使用 SGD 算法更新本地模型.在训练的第t轮过程中，第l次迭代更新过程为

2)簇内聚合：簇内设备进行φ次迭代更新后，进行一次簇内模型聚合.基于无线D2D网络，设备i∈Sk将模型参数以广播[17]的方式发送到每个相邻设备j∈Ni，并且同时从Ni中接收模型参数计算邻域平均值，以更新本地模型.当迭代次数l是φ的整数倍时，进行簇内模型参数聚合得

式中：常数 α为与图拓扑相关的设计参数，以确保快速收敛[11].

3)全局聚合：当所有的簇进行 τ次簇内聚合，每个设备基于本地数据集进行L=φτ次SGD迭代更新后，服务器以同步的方式执行全局聚合.在服务器上实现簇头选择和带宽资源分配联合优化算法来确定每个簇中的簇头，簇头设备将此时模型的参数上传至服务器.服务器接收C个簇头的本地模型参数，通过参数平均更新全局模型为

最后，服务器将全局模型广播到所有设备.重复上述步骤，直到全局模型收敛.

为了更清楚地说明提出算法的训练过程，在图2中给出示例，其中有4个设备，分别编号为1～4，每个矩形的长度表示相应操作的时间消耗.对于分层去中心化联邦学习，根据设备的位置将分为2个簇，即设备1和2属于簇1，设备3和4属于簇2，然后每个集群独立执行去中心化训练过程.从第t轮开始，簇1、2分别执行3次本地更新、簇内聚合后，进行一次全局聚合.选择设备1和设备4分别作为2个簇的簇头，将模型上传至参数服务器进行全局聚合.

图2 分层联邦学习算法时序模型Fig.2 Sequence model of hierarchical federated learning

2 通信模型

2.1 带宽资源分配概述

无线联邦学习系统的可用带宽资源为B.将所有带宽资源分割成2个部分：B=B(1)+B(2),分别用于簇内聚合和全局聚合.对于簇内聚合阶段，所有簇内的D2D通信共用带宽B(1).考虑D2D链路可靠的通信场景，在整个训练过程中所有簇的D2D连通图保持不变.由于D2D信道估计的信令开销非常昂贵，因此假设所有D2D链路的瞬时信道状态信息未知.假设已知的所有链路的路径损耗主要取决于位置信息，并且变化缓慢.对于全局聚合阶段，簇头与基站通信使用的带宽资源为B(2)，基站和设备通过无线链路连接.

2.2 簇内D2D通信

基于无线D2D网络进行簇内聚合,考虑簇Sk中的任意设备(比如设备i)和去中心化训练的任意一轮(比如第l轮)，这一轮训练中的时延由2个阶段决定：计算阶段和通信阶段.

1)本地模型的计算时延：设备进行φ次本地模型梯度下降更新的时延与设备的计算能力有关[17].计算能力越差，该计算时延越大.

2）D2D通信时延：为了利用设备的接近性并缩短通信时间，D2D链路用于簇内设备之间的数据传输.设备向邻居集合Ni广播本地模型，并从其他设备接收模型参数以聚合全局模型.假设D2D链路的信道在一次训练迭代中是静态的，并且在不同的迭代中会有所变化[18].所有簇内的D2D通信共用带宽B(1)，因为簇与簇之间的地理距离较远，属于不同簇的设备使用，所以可以将相同频带通信时的相互之间干扰视为噪声[19].假设D2D通信是使用正交频分技术进行的，不考虑簇内通信的干扰， 将B(1)划分为nk个正交的子信道，每个子信道分配给簇Sk中的一个设备.从设备i到设备j的 链路信道功率增益为hi,j.设备i将模型参数广播发送到相邻设备所需的通信时延为

为了提高收敛速率，在可用带宽资源为B(1)的约束条件下最小化每一轮簇内去中心化学习的训练时延：

式中：P 1是一个凸优化问题，当簇Sk中所有设备的训练时延都相等，即时 ，设备i用于广播的带宽Bi是最优分配的.

2.3 簇头与基站通信

在所有的簇都经过 τ轮簇内聚合后，进行一次全局模型聚合.从每个簇中选择一个簇头，考虑任意 一个簇(比如簇Sk)，它 的簇 头 为Hk.簇头Hk经过τ轮簇内聚合后得到的本地模型作为整个簇的代表，上传模型参数至基站.采用正交频分技术将B(2)划分成C个正交子信道，Bk为 簇 头Hk分 配 到的带宽，hk为簇头的上行信道增益，pk为簇头的发射功率，簇头上传模型参数至基站所需的时间为

基站 使用 带宽B(2)来广播全局模型.p为基 站的发射功率，|hmin|为所有簇头设备中最小的下行信道增益，那么基站广播全局模型所需的时间为

Td为下行广播通信时延.

基站上的服务器对所有簇头模型参数进行平均所需的计算时延为Ta，那么一轮全局聚合的时延 为

3 簇头选择与带宽分配

3.1 问题建模

为了降低全局聚合时的通信时延，优化簇头与基站通信的带宽资源分配方法以及提高全局模型的性能表现，需要确定合理的簇头选择方法.簇头的本地模型能够精确地反映集群经过训练后得到的模型特征.在全局聚合阶段，从每个簇内选择作为簇头设备的集合为 {H1,···,HC}.用布尔变量wk,i表示设备i∈Sk是 否被选择为第k个簇的簇头.wk,i=1 表示被选择为簇头，否则wk,i=0.没有被选为簇头的设备不上传模型，上传时间为零，因此设备i∈Sk的上传时间为

簇头通过无线链路与基站相互通信，进行模型参数的传输，基站收集到所有簇头上传的数据后才能进行全局参数聚合.为了避免链路质量差的设备被选为簇头进而限制整体的收敛速率，根据所有设备的上传时间确定一个常量TBound，作为传输时间的上界[20]，上传时间超过上界的设备禁 止被选择.决定簇头选择的布尔变量wk,i和决 定B(2)在每个簇之间分配的变量Bk都存在于设备上传时间式(10)中，因此簇头选择和带宽分配是相互影响的.

经过若干轮簇内去中心化训练后，选择性能好的模型上传有利于加快全局收敛.为了提高算法的收敛速率，通过联合优化簇头的选择问题与簇头上行链路带宽分配，最大化收敛速率.在给定的传输时间上界TBound内，所有簇头必须完成模型参数上传，尽可能选择每个簇内本地模型学习性能表现好的设备作为簇头.为了对中心化训练得到的模型性能进行度量，研究模型性能与设备在D2D链路连通图中的度(degree)的关系.设备i∈Sk在D2D链路连通图Gk=(Sk,Ek)中所代表节点的度记为Dk,i，度是指和设备i相连接的设备数目，即Dk,i=|Ni|.设备的度越大表示在D2D网络中与该设备相连通的其他设备数量越多，在进行簇内参数聚合时可以与更多设备交换模型数据.经过式(4)的邻域参数平均后，度越大的设备得到的本地模型越接近于簇内所有模型的参数平均值，训练后的本地模型更能够反映出簇内数据分布的真实状况[21].

为了研究连通图中节点的度对去中心化训练得到的模型收敛性能的影响，在数据独立分布的10个设备组成的集群中，进行由式(3)～(5)定义的去中心化分布式训练, 直到与所有设备关联的全局损失函数收敛至ε=0.15.每次实验前随机生成D2D连通图，分别在Cifar-10和MNIST数据集上训练卷积神经网络(CNN)和深度神经网络(DNN)，进行100次实验后，根据数据拟合每个设备的局部经验损失f与设备在连通图中的度D的关系，得到的结果分别为

式中：p1、p2、p3、q1、q2为负二次幂拟合的参数，q1、q2为负一次幂拟合的参数，拟合结果如图3、4所 示.在 Cifar-10 上中心化训练CNN至收敛时，局部经验损失与度成负二次幂关系；在 MNIST 上中心化训练 DNN 至收敛时，局部经验损失与度成负一次幂关系.由此可以得出，度越大的节点，训练后得到的本地模型的性能表现越好.

图3 在Cifar-10上训练CNN局部经验损失与度的关系Fig.3 Local experience loss versus degree for training CNN on Cifar-10

图4 在MNIST上训练DNN局部经验损失与度的关系Fig.4 Local experience loss versus degree for training DNN on MNIST

在本研究中，以设备在连通图中的度来衡量设备的本地模型学习性能，联合优化问题的目标即可建模为：在规定的上行传输时间上界TBound内，使得被选中簇头的设备的度之和最大化：

当wk,i=0 时，=0,约束(17)一定满足；当wk,i=1 时，时最节省带宽.所以为了得到最大化目标值，约束(19)的不等式应该取等号后带入约束(16)，定义变量为优化问题转化为

P3 是一个分组背包问题：有N件物品和一个容量为B(2)的背包，这些物品被划分为C个 组，第k个组中物品数量为nk.第k个 组 中 的 第i件物品的价值为Dk,i，体积 为Vk,i.每个组中的物品 只 能选 一件，目标是求解将某些物品装入背包使得在不超过背包容量的情况下，物品的价值最大.使用动态规划算法对P3求最优解，时间复杂度相对于回溯法和穷举法等其他最优化方法较低[22].建立大小 为C×B(2)的 二维数组F和G，F[k,v] 为 从 前k组中选择能装进容量为v的背包物品的最大价值,G(k,v)为达到此最大价值的状态转移路线，具体描述如下.

1) 将 二维数组F和G初始化为0；

2) f ork=(1,2,···,C)；

3) f orv=(B(2),B(2)-1,···,Vk,i)；

4)F[k,v]=

5)G[k,v]=

6) e nd f or；

7) e nd f or.

从F[C,B(2)] 开 始，根据状态转移路线数组G回溯，得到背包问题的解决方案作为簇头的选择结果.假设第k个簇中被选中的设备的索引下标为j，则簇头Hk的带宽的最优解为

4 仿真实验结果

4.1 实验设置

考虑一个r=300 m的小蜂窝网络.小区内有C=10个设备集群，每个集群有10台设备，每个设备的发射功率为23 dBm.在每个集群中，设备随机分布在r=50 m的D2D网络中,每对设备之间的D2D链路以P=0.5的概率激活,并且保证每个簇的D2D拓扑结构是一个连通的图.无线D2D链路的路径损耗由 98.45+20log10(d)生 成，d为设备之间的距离，单位为km.带有中央服务器的基站位于蜂窝网络的中心，发射功率为46 dBm，每个集群的位置中心与基站的距离为250 m.设备与服务器之间的路径损耗模型为128.1+37.6log10d，d为 设备到服务器的距离，单位为km.小尺度衰落遵循瑞利分布.系统总带宽B=20 M Hz,B(1)=B(2)=10 MHz.

考虑到训练分类器的学习任务，采用经典的CNN模型 VGG19和具有2个隐藏层的DNN模型进行实验.对于CNN，使用著名的Cifar-10数据集，其中包含50000张训练图像和10000张测试图像，具有10个类别；对于DNN，使用手写数据集MNIST中的50000张训练图像和10000张测试图像.由于数据分布可能受地理位置和用户习惯的影响，在不同集群设备之间的数据分布是非独立同分布的，即首先按标签对所有数据样本进行排序，然后将它们分成50个大小为1000的分片，为每个集群分配 5个分片.每个集群只能获得5类训练样本.以独立同分布的方式将数据样本均匀地分配到集群中的设备上.为了避免选择上行信道较差的设备选为簇头而增大全局聚合的时延，传输时间上界TBound由平均分配带宽发送数据时所有设备的上行时延最大值确定：

式中：0 ＜β＜1.0 ，调整 β的大小进行多次实验，根据收敛速率来确定TBound的合理值；TBound对于传输CNN和DNN模型分别设置为5.0 s和0.5 s可以使提出的算法具有较快的收敛速率；本地更新迭 代 次 数φ=20 ,每 两轮全局聚合之间进行τ=10次簇内模型聚合.

4.2 与基线算法对比

为了验证所提利用D2D通信的分层联邦学习可以节约通信开销，加快收敛速率，对所提算法与传统的联邦学习算法FedAVG[4]和现有的分簇联邦学习算法FedCH[7]的性能进行对比.在作为基线的FedAVG算法中，系统带宽B=20 MHz全部用于设备与基站通信，经过φ=20次本地更新迭代后, 在每次全局聚合时所有设备都将其本地模型上传到服务器.在作为基线的FedCH算法中，簇内通信带宽B(1)=10 MHz，簇头与基站通信带 宽B(2)=10 MHz.经 过φ=20次本地更新迭代后,每个集群中的设备将其本地模型同步发送到簇头进行聚合，所有中心节点采用异步的方式进行全局聚合.

使用不同算法训练CNN和DNN测试集准确率A随时间t变化如图5、6所示.从图中可以看出，提出的算法收敛速度比其他2种基线算法更快，并且最终得到的模型精度与FedAVG算法相当，略高于FedCH算法.对于在Cifar-10训练CNN和在MNIST上训练DNN，提出算法的收敛速率比FedAVG算法分别提高了5倍和3倍.由于采用分层的联邦学习架构后，各个簇独立进行去中心化训练，基于D2D网络进行模型参数聚合的传输速率较快，以簇内聚合代替全局聚合使全局的聚合频率和上行链路密集度都降低了10倍.在训练CNN和DNN时分别减少89.4%和82.7%的全局聚合通信时间.

图5 不同算法下CNN在Cifar-10上的准确率随时间变化Fig.5 Accuracy of CNN on Cifar-10 varies with time in different algorithms

图6 不同算法下DNN在MNIST上的准确率随时间变化Fig.6 Accuracy of DNN on MNIST varies with time in different algorithms

不同于FedCH算法，所提算法使用D2D通信在簇内节点之间交换模型参数，避免中心节点收集模型参数时产生拥塞.在训练CNN和DNN时，模型收敛速率提高了61.1%和56.3%.相对于采用异步的方式进行全局聚合的FedCH算法，所提算法同步地对所有簇模型信息进行全局聚合，因此最终得到的模型性能更好.

4.3 不同簇头选择方法的影响

为了验证所提簇头选择与带宽分配联合优化算法的有效性能，在下面的实验中实现了2种作为基线的簇头选择方法，即信道感知调度和连通度感知调度.在信道感知调度中，依据设备与基站的上行信道状态、设备的发射功率，从每个簇中选择与基站通信时间最短的设备作为簇头，使得上传模型所需的总通信时延最小化.被选为簇头的设备集合表示为 {H1,···,HK} ，簇Sk的簇头为

由于D2D链路的连通状态在整个训练过程中是不变的，每轮选择的簇头也固定不变.在连通度感知调度中，为了提高全局模型的性能，从每个簇中选择在连通图中度最大的节点作为簇头即：

按照上述2种策略分别选择出簇头后，假设簇头Hk与基站的上行信道分配到的带宽为Bk,为了使得上传模型所需的通信实验最小化，带宽分配的最优值为

从图7和8中可以看出，提出的簇头选择与带宽分配联合优化算法在整个训练过程中实现了最快的收敛速度和最高的学习性能，原因在于信道感知调度忽略本地模型的性能，选中的簇头可能具有性能较差的本地模型.连通度感知调度没有考虑到信道状况，上传模型所需的通信时间是该策略的瓶颈.由于所提联合优化算法每轮选择的簇头不是固定的，这为整个训练增加了随机性，因此可以得到比固定簇头的连通度感知调度更高的学习性能.实验结果证实了权衡模型性能提升与减少通信时间所提出的簇头选择算法的有效性.

图7 不同簇头选择方法下CNN在Cifar-10上的准确率随时间变化Fig.7 Accuracy of CNN on Cifar-10 varies with time in different cluster head selection methods

4.4 不同全局聚合频率的的影响

图8 不同簇头选择方法下DNN在MNIST上的准确率随时间变化Fig.8 Accuracy of DNN on MNIST varies with time in different cluster head selection methods

为了验证利用D2D网络进行簇内聚合的分层联邦学习对于不同全局聚合频率具有鲁棒性，将每2轮全局聚合之间的簇内模型聚合次数 τ改变，并且保持本地更新迭代次数不变.从图9和图10中可以看出，基于D2D网络进行一次簇内模型聚合所需的通信时延显著小于终端与基站进行全局聚合所需的通信时延，在一定范围内提高簇内模型聚合次数来降低全局聚合的频率有利于缩短训练时间.然而当簇内模型聚合的次数继续增加，全局聚合频率过低会影响模型的性能提升，簇内聚合的次数增加所带来的通信时延下降的收益被抵消.该结果表明，基于D2D通信进行簇内聚合可以减少对中央服务器的依赖，从而实现更分散的模型训练过程.

图9 不同全局聚合频率下CNN在Cifar-10上的准确率随时间变化Fig.9 Accuracy of CNN on Cifar-10 varies with time in different global aggregation frequencies

图10 不同全局聚合频率下DNN在MNIST上的准确率随时间变化Fig.10 Accuracy of DNN on MNIST varies with time in different global aggregation frequencies

5 结语

本研究提出一种基于无线D2D网络的分层联邦学习训练框架，构建集群拓扑并执行分层聚合以进行训练.该系统结构通过D2D网络进行簇内聚合，各个簇同时进行去中心化训练.从簇中选择一个代表集群训练结果的簇头上传模型至基站，进行全局聚合.该框架降低了中央服务器出现流量拥塞的可能性，同时将分层联邦学习应用到簇内无服务器的场景.为了缩短信时间并且提高模型的性能表现，使用图中节点的度来衡量本地模型的收敛性能，通过最大化所有簇头的度之和，对簇头选择与带宽分配问题进行联合优化，并且基于动态规划设计最优的算法.仿真实验结果表明与基线算法相比，该框架可以有效缩短训练时间和提高学习性能.