分布式联邦学习结合联盟博弈在物联网中的应用

Application of Distributed Federated Learning Combined with Coalition Game in the Internet of Things

摘要

联邦学习作为一种新兴的分布式机器学习范式， 在物联网应用中能有效保护数据隐私， 但仍存在模型更新效率低和实时性差等问题。为此， 提出将分布式联邦学习与联盟博弈相结合的新模型， 在该模型中客户端通过权衡形成联盟的收益和成本合作进行联邦学习。由于物联网中设备资源的有限性， 提出在联盟中选择领导者协调训练过程。为了引导客户端自适应地形成联盟， 同时确保更新模型的精度和效率， 设计了一种分布式联盟形成算法。通过联盟合并和拆分操作的不断执行， 寻找到最终的联盟分区， 最大化合作设备的效用。为了实现联盟成本的公平分配， 提出了一种成本分摊机制， 维持算法给定结果的稳定性。最后， 通过与其他策略的实验对比分析， 验证了所提出模型的有效性。

Abstract

As a new distributed machine learning paradigm， federated learning can effectively protect data privacy in Internet of Things （IoT） applications， but it still faces challenges such as low model update efficiency and poor real-time performance. To address these issues， a new model combining distributed federated learning and coalition games is proposed， where clients collaborate in federated learning by weighing the benefits and costs of forming a coalition. Given the limited resources of devices in the IoT， a leader is selected within the coalition to coordinate the training process. To guide clients in adaptively forming coalitions while ensuring the accuracy and efficiency of model updates， a distributed coalition formation algorithm was designed. Through continuous execution of coalition mergers and splits， the ultimate coalition partition is achieved to maximize the utility of cooperative devices. To ensure a fair distribution of coalition costs， a cost allocation mechanism is proposed to maintain the stability of the algorithm's results. Finally， experimental comparisons with other strategies validate the effectiveness of the proposed model.

Graphical abstract

关键词

联邦学习 / 模型更新效率 / 联盟博弈 / 选择领导者 / 分布式联盟形成

Key words

federated learning / model update efficiency / coalition game / leader selection / distributed coalition formation

0 引　言

在当今的人工智能时代， 深度学习技术取得了显著性进展， 促进了高级应用程序与物联网设备数量的急剧增长^［1］。在物联网环境下， 大量的智能设备收集了海量的数据， 其中可能包含用户的隐私信息。因为现有的通用数据保护条例日益严苛^［2］， 这些数据的收集和处理面临着诸多挑战， 特别是数据安全和隐私保护方面。联邦学习（Federated Learning， FL）作为一种新兴的机器学习范式， 其原始数据保留在客户端上， 在中央服务器的协调下多客户端协作学习共享模型更新^［3］， 极大地提高了数据的隐私性和安全性。

在实际应用中， FL也面临着诸多挑战。传统的FL依靠服务器聚合更新全局模型， 随着客户端数量的增加， 容易出现通信瓶颈和单点故障等问题。为了解决上述问题， 研究者们正在探索各种新的FL架构和方法， 如去中心化FL、 基于区块链的FL等^［4‐5］， 以提高FL系统的鲁棒性和可拓展性。去中心化FL可以采用分布式架构， 在客户端中选取领导者来代替服务器进行模型聚合。

在物联网场景下， 设备合作进行FL需要耗费大量的时间和成本， 而物联网设备拥有的计算和通信等资源一般都是有限的， 因此， 高效地更新模型至关重要。然而， 现有的方法大多依赖于服务器的存在， 不仅增加了单点故障的风险， 还不利于系统的可拓展性。例如， Tsouvalas等^［6］提出了FedCompress， 其结合动态权重聚类和服务器端知识蒸馏的方法， 在保证模型精度的情况下显著降低了通信成本， 但仍依赖于服务器执行模型聚合操作。Hijazi等^［7］提出了支持物联网智慧城市的一种安全的FL方法， 通过结合全同态加密与FL， 在提供强大隐私保护的同时， 有效减少了通信开销和延时。该方法将客户端随机分配到集群中， 不考虑实际物联网设备的地理位置， 且仍需解决存在的单点故障问题。Chen等^［8］提出了动态调整客户端聚类数量的方法， 在不影响模型性能的前提下， 通过减少参与训练的客户端数量来降低通信成本。然而， 这种方法忽略了每个客户端可能都有模型更新的需求。为了进一步降低通信开销， Singh等^［9］提出了一种新的边缘网络分层FL框架， 该框架将同步边缘雾模型聚合和异步雾云模型聚合相结合， 但模型的聚合更新依赖于边缘雾设备和云服务器。因此， 如何在分布FL中高效更新设备模型是一个值得研究的问题。

本文将分布式FL应用到物联网中， 为了提高模型更新效率， 量化一轮次模型更新时间为设备合作的成本。提出将联盟博弈中的联盟形成博弈与FL相结合， 允许设备权衡形成联盟的收益和成本合作进行FL。为了进一步提高联盟内模型更新效率， 提出在联盟设备中的领导者选择方法。为了寻找到最终的联盟分区， 使得客户端形成的联盟在合作有成本的情况下最大化其效用， 设计了一种分布式联盟形成算法。最后， 通过实验验证了在联盟形成博弈策略下， 所提模型对比其他策略的有效性。

1 系统架构

1.1 无线网络上的分布式FL

本文研究物联网环境中的分布式自组织FL系统， 该系统处于一个具有无线通信基础设施的移动网络中。定义H个设备参与到系统中， 设备的集合可以由N=\{n_{\mathrm{1}},n_{\mathrm{2}},\cdots ,n_H\}来表述。每个客户端拥有一个本地数据集， 数据集的大小由d_i来表述。本文假设设备收集的数据是相同质量且独立同分布（Independent Identically Distributed， IID）的， 因此， 客户端在本地训练时使用的数据越多， 在一轮次FL训练结束后获得的模型就越好。

在本文研究的案例中， 客户端可以通过合作的方式形成联盟M进行FL， 为了进一步提高模型更新的效率， 在联盟的设备中选择一个领导者负责协调FL训练过程。在物联网场景中， 设备的能源和通信等资源一般是有限的， 并且联盟中领导者设备的地理位置对于通信路径的优化至关重要， 本文按照式（1）得出联盟中每个客户端的权重^［10］， 权重最大的客户端为领导者。

w_i=\frac{{\gamma }_{\mathrm{1}}{e}_i+{\gamma }_{\mathrm{2}}{\lambda }_i}{{\gamma }_{\mathrm{3}}{\mathrm{𝓁}}_M},（1）

式中： e_i为客户端目前剩余的能量； {\lambda }_i为与客户端相邻设备的数量； {\mathrm{𝓁}}_M为联盟中客户端与其他客户端之间的平均通信距离； {\gamma }_{\mathrm{1}},{\gamma }_{\mathrm{2}},{\gamma }_{\mathrm{3}}为可调参数， 用来调整和平衡这些影响因素的重要性。

按照权重大小选举出联盟中的领导者n_l后， 领导者发送当前的全局模型w_G^k到其他客户端， k为轮次索引； 其次， 成员n_i基于该模型进行训练更新本地模型为w_i^k， 客户端在第k轮次的目标是找到最小化损失函数{\mathrm{ℒ}}_i(w_i^k)； 然后， 客户端将更新后的本地模型上传到领导者； 最后， 领导者执行聚合操作更新全局模型为w_G^{k+\mathrm{1}}， 相应的系统模型如图 1 所示。

对于FL中模型参数的聚合机制， 本文关注同步联邦平均（Federated Averaging， FedAvg）模型聚合算法^［11］， 领导者接收到所有客户端上传的模型后通过加权平均进行更新全局模型。

当客户端面对不同的联盟时， 会有不同的满意度， 为了使用统一的标准表示客户端对联盟更新模型的满意度水平， 本文将客户端对联盟的满意度表示为联盟M最新一轮更新全局模型的估计准确度u(M)。使用\mathrm{l}\mathrm{o}\mathrm{g}函数表示联盟包含的训练数据总量与全局模型准确度之间的关系。

u(M)=\beta \mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{1}+\rho \cdot \phi (M)),（2）

式中： \phi (M)为测量联盟的数据质量函数， 基于之前假定的设备拥有的数据是独立同分布的， \phi (M)为联盟M中客户端参与训练所使用的数据集大小总和， 即\phi (M)=\sum _{i\in M}{d}_i； \beta为模型性能的转换系数。

1.2 时延模型

在联盟M中进行一轮次模型更新的总时延包括以下几个部分。

1.2.1 计算时延

在联盟内为了改善全局模型， 客户端n_i使用自身计算资源在本地数据上独立进行若干次模型迭代训练， 客户端更新本地模型的计算时延可表示为

t_i^{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}}=\frac{a{\varsigma }_i{d}_i}{f_i},（3）

式中： a为客户端本地训练的迭代次数； {\varsigma }_i为客户端处理一个数据样本所需要的CPU周期数； f_i为其在训练时所使用的CPU周期频率^［12］。此外， 现在的物联网设备也拥有较强的计算能力， 且本文采用的是同步联邦平均模型聚合算法， 因此领导者设备对于成员发送的模型参数进行简单的加权平均即可更新全局模型， 将模型聚合的计算时延表示为t_l^{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}}。

1.2.2 通信时延

在联盟内成员客户端下载和发送模型参数的通信时延是不可避免的， 客户端在本地训练完成后， 将更新后的模型上传到领导者， 本文将w_i作为客户端更新的本地模型参数， 在带宽为B的通信系统中， 客户端上传模型的时间可以表示为

t_{i,l}^{\mathrm{c}\mathrm{o}\mathrm{m}}=\frac{w_i}{r_{i,l}},（4）

式中： r_{i,l}为成员到领导者的传输速率， 根据香农公式， 可以表示为

r_{i,l}=B\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\left(\mathrm{1}+\frac{P_i{h}_{i,l}^{\mathrm{2}}}{B{N}_{\mathrm{0}}}\right),（5）

式中： P_i为客户端的发射功率； N_{\mathrm{0}}为噪声功率谱密度； h_{i,l}为成员到领导者的信道增益。同样的， 每个成员需要下载联盟内领导者更新后的全局模型w_G。客户端下载模型的时间可以表示为

t_{l,i}^{\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}}=\frac{w_G}{r_{l,i}},（6）

式中： r_{l,i}为联盟内领导者到成员客户端的传输速率。在一轮次的模型更新中， 本文将客户端下载全局模型最大的时延记为t_l^{\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}}。r_{l,i}具体可以表示为

r_{l,i}=B\mathrm{l}\mathrm{o}{\mathrm{g}}_{\mathrm{2}}\left(\mathrm{1}+\frac{P_l{h}_{l,i}^{\mathrm{2}}}{B{N}_{\mathrm{0}}}\right),（7）

式中： P_l为领导者设备的发射功率； h_{l,i}为领导者到成员的信道增益。

由于联盟内领导者采用同步FL的聚合方式， 每轮次模型更新的总时间主要取决于参与训练最慢的设备^［13］， 结合这4种时延， 将在联盟内一轮次更新全局模型的总时延表示为

T_M^{}=\mathrm{m}\mathrm{a}{\mathrm{x}}_{i\in M}(t_i^{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}}+t_{i,l}^{\mathrm{c}\mathrm{o}\mathrm{m}})+t_l^{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}}+t_l^{\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}}\mathrm{。}（8）

2 客户端之间的合作： 联盟形成博弈

联盟形成博弈涉及H个设备， 这些设备希望通过形成联盟进行合作， 以提高所获得模型的准确度。本文首先从联盟博弈的相关定义出发， 这些定义有助于分布式联盟形成算法的推导。

定义 1　联盟分区被定义为一个集合\Pi =\left\{M_{\mathrm{1}},\cdots ,M_l,\cdots ,M_L\right\}， 其中M_l\subseteq N是由不相交的联盟组成， 并满足{\cup }_{l=\mathrm{1}}^L{M}_l=N。

在联盟分区中每个联盟M与3个不同的量相关联：

1） 收益u(M_l)\ge \mathrm{0}量化了联盟的收益， u(\mathrm{\varnothing })=\mathrm{0}， 该收益的制定取决于联盟博弈的目标。在本文中， 联盟的收益设置为客户端对联盟更新模型的满意度u(M_l)， 即联盟最新一轮次更新模型的估计准确度。

2） 成本c(M_l)量化了合作的成本， 在本文中， 量化联盟内一轮次模型更新的时间作为客户端合作形成联盟的成本c(M_l)=\eta T_M， \eta为时间与成本的转换参数， 因为模型更新时间对于物联网中有着模型快速更新和实时性需求的设备是非常重要的。

3） v(M_l)被定义为客户端合作形成联盟的收益与成本的差： v(M_l)=u(M_l)-c(M_l)。

为了推导出客户端权衡形成联盟的收益和成本来合作形成联盟的分布式算法， 本文参考合作博弈论将客户端之间的合作建模为(N,v)联盟博弈， 其中N为所有客户端的集合， v(M)为联盟的值或效用， 该值体现客户端对合作形成联盟在获得收益和成本之间的权衡。联盟M的值v(M)可以如下给出

\begin{array}{c}v(M)=u(M)-c(M)=\\ \beta \mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{1}+\rho \phi (M))-\eta T_M^{}\mathrm{。}\end{array}（9）

在联盟博弈中， 参与者通过结成联盟以优化个人和联盟的效用函数。研究者们通常认为所有参与者合作形成的大联盟是最优结构， 可以显著提高联盟的合作效用^［14］。在本文研究的案例中， 形成联盟是有成本的， 虽然客户端形成大联盟可以提高客户端的收益， 但是由于合作成本的因素将会限制这一收益。对于所提出的联盟博弈， 接下来将证明大联盟是无法形成的， 因此本文关注如何寻找到客户端之间最优的合作方式， 客户端在权衡形成联盟的收益和成本的情况下如何实现合作效用最大化。

定义 2　如果对于任意两个不相交的联盟M_l,M_{l\mathrm{\text{'}}}\subset N,v(M_l\bigcup M_{l\mathrm{\text{'}}})\ge v(M_l)+v(M_{l\mathrm{\text{'}}})， 那么具有可转移效用的联盟博弈(N,v)是超加性的。

定理　在客户端合作形成联盟有成本的情况下， 本文提出的联盟博弈(N,v)通常不是超加性的。

证明　本文按照文献［15］中的步骤对定理进行证明， 考虑系统中存在两个不相交的联盟M_i,M_j\subset N， 它们各自的效用可以表示为：

v(M_i)=\beta \mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{1}+\rho {\phi }_i)-\eta T_{M_i},（10）

v(M_j)=\beta \mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{1}+\rho {\phi }_{{}_j})-\eta T_{M_j},（11）

式中： {\phi }_i,{\phi }_j为相应联盟客户端训练数据量的总和。

如果联盟M_i,M_j合并成一个联盟M_g， 该联盟相应的数据总量为\phi (M_g)=\phi (M_i)+\phi (M_j)。因此， 合并后联盟的效用为

v(M_g)=\beta \mathrm{l}\mathrm{o}\mathrm{g}(\mathrm{1}+\rho {\phi }_g)-\eta T_{M_g}\mathrm{。}（12）

合并后联盟M_g的效用与合并前联盟M_i,M_j效用总和之间的差可以表示为

\begin{array}{c}v(M_g)-[v(M_i)+v(M_j)]=\\ \beta \mathrm{l}\mathrm{o}\mathrm{g}\frac{\mathrm{1}+\rho {\phi }_{i\bigcup j}}{\mathrm{1}+\rho {\phi }_{i\bigcup j}+{\rho }^{\mathrm{2}}{\phi }_i{\phi }_j}-\eta [T_{M_g}-(T_{M_i}+T_{M_j})]\mathrm{。}\end{array}（13）

显然， ， 该等式前一项为负值， 如果合并后联盟中每一轮次更新模型的时间大于M_i,M_j中一轮次模型更新时间的总和， 则该等式小于零恒成立。实际上， 当联盟M_i,M_j合并后， 如果有成员训练缓慢或与领导者通信延时过大， 都会严重影响模型聚合更新的时间， 从而急剧增加联盟的成本， 使得联盟效用低于合并前的总和。因此， 在客户端合作形成联盟有成本的情况下， 联盟博弈(N,v)一般不是超加性的。

接下来证明在本文研究案例下联盟博弈的核心是空的。假设所有客户端合作形成一个大联盟， 其效用可以表示为\mathit{v}(N)， 把\mathit{y}=\left\{{\breve{y}}_{\mathrm{1}},\cdots ,{\breve{y}}_H\right\}作为收益向量， 将客户端n_i从大联盟中获得的收益表示为{\breve{y}}_i。

如果{\displaystyle \sum _{i=\mathrm{1}}^H}\breve{\mathit{y}}=v(N)， 则收益向量\breve{\mathit{y}}是群体理性的。当每个客户端都能获得不少于单独行动时的收益， 即{\breve{y}}_i\ge v(\left\{n_i\right\}),\forall i， 那么收益向量\breve{\mathit{y}}是个体理性的。根据文献［16］， 分配是群体理性和个体理性的收益向量。

定义 3　联盟的核心是存在一组稳定的分配， 对于任意的联盟\forall M_l\in \Pi， 客户端都没有动机拒绝收益分配{\breve{y}}_i， 离开大联盟去形成联盟M_l。联盟的核心定义为

\varpi =\left\{y:\sum _{i\in H}{\breve{y}}_i=v(N)\mathrm{a}\mathrm{n}\mathrm{d}\sum _{n_i\in M_l}{\breve{y}}_i\ge v(M_l),\forall M_l\in \Pi \right\}\mathrm{。}

正如之前所证明的， 合并后联盟的效用可能为负值， 这与客户端的个体理性相冲突， 即， 此时客户端合作形成大联盟所获得的效用远少于客户端单独行动时的效用。如果联盟M_i,M_j不合并为一个更大的联盟， 其各自的联盟效用将会更高。因此， 客户端有动机拒绝收益分配{\breve{y}}_i， 不形成大联盟， 那么上述所提议的联盟博弈的核心就是空的。

由于本文提出的联盟博弈(N,v)一般不具有超加性， 同时其核心是空的， 所以物联网中的设备不会形成大联盟。相较于大联盟， 客户端更倾向于形成分布式且不相交的小联盟， 因为这种合作方式能够更有效地提高联盟的效用， 接下来将讨论分布式联盟形成算法。

3 分布式联盟形成算法及成本分摊

3.1 联盟形成博弈算法

根据文献［17‐18］， 本文定义两个简单的拆分和合并操作来修改客户端合作形成的联盟分区\mathrm{\Pi }。

定义 4　合并和拆分操作

1） 合并操作： 合并任意一组联盟集合\left\{M_{\mathrm{1}},\cdots ,M_l\right\}， 如果v({\displaystyle \underset{i=\mathrm{1}}{\overset{l}{\cup }}}{M}_i)>{\displaystyle \sum _{i=\mathrm{1}}^l}v(M_i)， 则进行联盟合并操作， \left\{M_{\mathrm{1}},\cdots ,M_l\right\}\to {\displaystyle \underset{i=\mathrm{1}}{\overset{l}{\cup }}}{M}_i。

2） 拆分操作： 拆分任意一组联盟集合{\displaystyle \underset{i=\mathrm{1}}{\overset{l}{\cup }}}{M}_i， 若{\displaystyle \sum _{i=\mathrm{1}}^l}v(M_i)>v({\displaystyle \underset{i=\mathrm{1}}{\overset{l}{\cup }}}{M}_i)， 则{\displaystyle \underset{i=\mathrm{1}}{\overset{l}{\cup }}}{M}_i→\left\{M_{\mathrm{1}}\right.，…，\left.M_l\right\}。

联盟的每次合并或拆分操作的执行都会导致联盟分区发生变化， 即{\Pi }_{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}}\to {\Pi }_{\mathrm{n}\mathrm{e}\mathrm{w}}^{\mathrm{\text{'}}}， 为了比较分区之间的关系， 使用联盟值的顺序作为标准。对于同一设备集合N构成的联盟分区{\Pi }_{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}}和{\Pi }_{\mathrm{n}\mathrm{e}\mathrm{w}}^{\mathrm{\text{'}}}， 其中联盟分区{\Pi }_{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}}=\left\{M_{\mathrm{1}},\cdots ,M_L\right\}， {\Pi }_{\mathrm{n}\mathrm{e}\mathrm{w}}^{\mathrm{\text{'}}}=\left\{M_{\mathrm{1}}^{\mathrm{\text{'}}},\cdots ,M_J^{\mathrm{\text{'}}}\right\}， 若{\displaystyle \sum _{j=\mathrm{1}}^J}v(M_j^{\mathrm{\text{'}}})>{\displaystyle \sum _{i=\mathrm{1}}^L}v(M_i)， 则说明联盟分区{\Pi }_{\mathrm{n}\mathrm{e}\mathrm{w}}^{\mathrm{\text{'}}}优于{\Pi }_{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}}， 即{\Pi }_{\mathrm{n}\mathrm{e}\mathrm{w}}^{\mathrm{\text{'}}}⊳{\Pi }_{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}}。

根据联盟合并与拆分的规则和分区之间的比较关系， 如果合并和拆分操作可以提高联盟的效用， 那么客户端将合作形成新的联盟， 否则保持原有的联盟。在分区{\Pi }_{\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{r}}中， 联盟合并和拆分的操作将会持续进行迭代， 直至最终的联盟分区{\Pi }_{\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}}形成， {\Pi }_{\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{l}}是使得客户端合作总效用最大化的稳定联盟分区， 算法如表 1 所示。

3.2 成本分摊

为了维持算法给定联盟形成结果的稳定性， 必须对联盟的成本进行公平的分摊。现有的公平分摊成本的方法主要是衡量客户端在本地训练时使用的数据量^［15］， 或是其更新模型的精度。在典型联盟博弈中沙普利值被广泛用来衡量成员对联盟做出的贡献^［19］。一些研究者考虑平等地分摊成本到每个成员^［20］， 但该种分摊方式会造成客户端在本地进行消极训练， 并可能导致模型参数更新的上传延迟。

模型性能和准确度的提高是客户端的共同目标， 本文假定系统中客户端收集的数据量大小相同， 并且都会如实在本地参与训练并上传模型。所以， 使用客户端本地模型的更新时间t_i^{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}}和其与联盟中领导者之间通信时间t_{i,l}^{\mathrm{c}\mathrm{o}\mathrm{m}},t_{l,i}^{\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}}的总和T_i作为分摊联盟成本的依据， 因为全局模型的计算时间对于联盟中的所有客户端来说是相同的。

T_i=t_i^{\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}}+t_{i,l}^{\mathrm{c}\mathrm{o}\mathrm{m}}+t_{l,i}^{\mathrm{d}\mathrm{o}\mathrm{w}\mathrm{n}}\mathrm{。}（14）

通常情况下， 当客户端使用越多的本地计算资源进行训练时， 其更新模型的时间就越短， 如果客户端本地更新模型的速度越快且与领导者之间的通信时间越短， 其分摊的成本就越少。在联盟M中， 客户端的成本分摊公式可以表示为

c_i=\frac{c(M)T_i}{\sum _{j\in M}{T}_j}\mathrm{。}（15）

4 实验结果与分析

本节通过实验对所提模型进行评估， 同时通过对比典型联盟博弈和非合作策略， 分析本文所提分布式联盟形成算法的优势。

4.1 实验设置

本次实验在10个物联网设备中进行部署， 设备随机分布在1 000 m×1 000 m的方形区域中， 传输带宽B=10 MHz， 相应的发射功率为20 dBm， 路径损耗指数设置为2.75， 噪声功率谱密度为-174 dBm/Hz。每个设备的CPU周期频率最大为1.2 GHz， 设备处理一个数据样本的CPU周期数为{\varsigma }_i=20 cycles/bit， 本地迭代次数a=\mathrm{6}， 全局模型迭代次数为30， 学习率为0.01。将MNIST训练数据样本平均划分到10个设备中， 设备的本地数据样例大小d_i=6 000， 设备更新的模型参数设置为10 MB， 对于全局模型估计准确度的参数设置为\beta =\mathrm{10},\rho =\mathrm{6}\times {\mathrm{10}}^{-\mathrm{5}}， 模型更新时间与成本的转换参数\eta =\mathrm{1}。

4.2 实验结果

图 2 展示了不同策略下联盟分区的总效用。由图可知， 联盟形成策略下的联盟总效用从部署12个设备开始时呈现明显的上升趋势， 同时期的非合作策略下的联盟总效用虽然也呈现上升趋势， 但最终涨幅较小， 趋于平缓。典型联盟博弈中的联盟总效用最低， 尽管呈现上升趋势， 但最终的效用仍为负值。

从图 3 可以看出， 在联盟形成博弈策略下， 客户端下载模型的平均时延显著低于典型联盟策略的下载时延。通过本文所提联盟形成算法， 客户端可以合作形成分布式小联盟， 这种分布式小联盟代替大联盟显著缩短了成员与领导者之间的通信距离， 从而大幅度降低了模型传输时延。而在非合作策略下， 客户端仅基于自身的数据集进行模型的本地更新， 不涉及模型传输。

图 4 展示了1 000 m×1 000 m的方形区域中部署14个物联网设备形成的最终联盟分区。在该图所示的联盟分区中共产生了6个联盟， 即｛｛n_{\mathrm{5}}，n_{\mathrm{11}}｝，｛n_{\mathrm{1}}，n_{\mathrm{10}}，n_{\mathrm{13}}｝，｛n_{\mathrm{3}}｝，｛n_{\mathrm{8}}｝，｛n_{\mathrm{9}}，n_{\mathrm{12}}，n_{\mathrm{14}}｝，｛n_{\mathrm{2}}，n_{\mathrm{4}}，n_{\mathrm{6}}，n_{\mathrm{7}}｝｝， 总效用为10.26。如图 2 所示， 在部署14个物联网设备下， 典型联盟博弈和非合作策略下的联盟分区总效用分别为-12.11和4.43。在本实验中， 每个设备的能量是相似的， 由图 4 可以看出， 在多个客户端合作形成联盟的内部会选择靠近中心位置的设备为领导者， 领导者的选取优化了与成员之间的通信路径， 减少模型的传输时间， 进而降低了联盟的成本。在实际的联邦学习训练中， 每个联盟最终更新模型的准确度分别达到｛97.56，97.74，97.31，97.55，97.65，97.97｝， 大联盟的模型精度为98.01， 每个联盟最终更新模型的准确度相差不多， 但实际模型的等待时间却有显著差异， 该差异可以从不同策略下联盟内客户端下载模型的延迟（图 3）中看出。

将上述区域中的物联网设备逐渐增加到50个， 图 5 展示了在不同策略下联盟的平均成本。在典型联盟博弈策略下的联盟成本最高， 在联盟形成策略下， 联盟成本显著降低， 但仍略高于非合作策略的成本。非合作策略的成本主要源于客户端本地训练， 虽然成本较低， 但个体客户端更新模型的准确度通常低于多个客户端合作进行FL模型更新的准确度。

5 结　论

本文提出了结合联盟博弈来解决分布式FL中物联网设备合作分组的问题， 客户端通过权衡收益和成本形成联盟。在客户端合作形成联盟后， 提出了通过选择领导者的方法提高联盟内的模型更新效率， 同时证明了在本文研究案例下， 联盟博弈中典型联盟博弈的非超加性， 联盟形成博弈能更好地改善客户端合作的效用。通过构建分布式联盟形成合并和拆分算法， 使得客户端合作形成总效用最大化的稳定联盟分区。同时， 根据所提出的成本分摊机制， 公平地分配每个形成的联盟成本。最后， 通过实验验证了本文所提模型的有效性。在今后的工作中将考虑在动态场景下， 设备如何高效地形成联盟进行FL， 研究如何使设备快速适应环境变化， 从而提高联邦学习的响应速度和效果。

参考文献

[1] LE H Q， QIAO Y， NGUYEN L X， et al. Federated multimodal learning for IoT applications： a contrastive learning approach［C］//2023 24th Asia-Pacific Network Operations and Management Symposium （APNOMS）， 2023： 201-206.

[2] AZAM N， MICHALA L， ANSARI S， et al. Data privacy threat modelling for autonomous systems： a survey from the GDPR’s perspective［J］. IEEE Transactions on Big Data， 2023， 9（2）： 388-414.

[3] MCMAHAN H B， MOORE E， RAMAGE D， et al. Communication-efficient learning of deep networks from decentralized data［C］//Artificial Intelligence and Statistics， PMLR， 2017： 1273-1282.

[4] GEORGATOS E， MAVROKEFALIDIS C， BERB ERIDIS K. Fully distributed federated learning with efficient local cooperations［C］//2023 IEEE International Conference on Acoustics， Speech and Signal Processing （ICASSP）， 2023： 1-5.

[5] 郭禹江， 张志才.基于声誉机制的区块链赋能多无人机系统联邦学习研究［J］.测试技术学报， 2024， 38（4）： 345-353.

[6] GUO Yujiang， ZHANG Zhicai. Research on federated learning of blockchain enabled multi UAV system based on reputation mechanism［J］. Journal of Test and Measurement Technology， 2024， 38（4）： 345-353. （in Chinese）

[7] TSOUVALAS V， SAEED A， OZCELEBI T， et al. Communication-efficient federated learning through adaptive weight clustering and server-side distillation［C］//2024 IEEE International Conference on Acoustics， Speech and Signal Processing （ICASSP）， 2024： 5805-5809.

[8] HIJAZI N M， ALOQAILY M， GUIZANI M， et al. Secure federated learning with fully homomorphic encryption for IoT communications［J］. IEEE Internet of Things Journal， 2024， 11（3）： 4289-4300.

[9] CHEN Y A， CHEN G L. An adaptive clustering scheme for client selections in communication-efficient federated learning［C］//2023 VTS Asia Pacific Wireless Communications Symposium （APWCS）， 2023： 1-3.

[10] SINGH N， TRIPATHI T， ADHIKARI M. Communication-efficient federated learning for real-time applications in edge networks［C］//2023 IEEE International Conference on Advanced Networks and Telecommunications Systems （ANTS）， 2023： 527-532.

[11] UMBREEN S， SHEHZAD D， SHAFI N， et al. An energy-efficient mobility-based cluster head selection for lifetime enhancement of wireless sensor networks［J］. IEEE Access， 2020， 8： 207779-207793.

[12] NILSSON A， SMITH S， ULM G， et al. A performance evaluation of federated learning algorithms［C］//Proceedings of the Second Workshop on Distributed Infrastructures for Deep Learning， 2018： 1-8.

[13] TRAN N H， BAO W， ZOMAYA A， et al. Federated learning over wireless networks： optimization model design and analysis［C］//IEEE INFOCOM 2019-IEEE Conference on Computer Communications， 2019： 1387-1395.

[14] 范绍帅， 吴剑波， 田辉. 面向能量受限工业物联网设备的联邦学习资源管理［J］. 通信学报， 2022， 43（8）： 65-77.

[15] FAN Shaoshuai， WU Jianbo， TIAN Hui. Federated learning resource management for energy-constrained industrial IoT devices［J］. Journal on Communications， 2022， 43（8）： 65-77. （in Chinese）

[16] GAUTAM M， BENIDRIS M. Coalitional game theory in power systems： applications， challenges， and future directions［C］//2023 IEEE Texas Power and Energy Conference （TPEC）， 2023： 1-6.

[17] JIANG S， WU J. Coalition formation game in the cross-silo federated learning system［C］//2022 IEEE 19th International Conference on Mobile Ad Hoc and Smart Systems （MASS）， 2022： 49-57.

[18] RUAN L， LI G， DAI W， et al. Cooperative relative localization for UAV swarm in GNSS-denied environment： a coalition formation game approach［J］. IEEE Internet of Things Journal， 2022， 9（13）： 11560-11577.

[19] NG J S， LIM W Y B， DAI H N， et al. Joint auction-coalition formation framework for communication-efficient federated learning in UAV-enabled Internet of vehicles［J］. IEEE Transactions on Intelligent Transportation Systems， 2021， 22（4）： 2326-2344.

[20] MASSIN R， LE MARTRET C J， CIBLAT P. A coalition formation game for distributed node clustering in mobile ad hoc networks［J］. IEEE Transactions on Wireless Communications， 2017， 16（6）： 3940-3952.

[21] SUN Q， LI X， ZHANG J， et al. ShapleyFL： robust federated learning based on shapley value［C］//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining， 2023： 2096-2108.

[22] ZHOU Y， CHAU S C K. Multi-user coalition formation for peer-to-peer energy sharing［C］//Proceedings of the Eleventh ACM International Conference on Future Energy Systems， 2020： 386-387.

基金资助

山西省基础研究计划自然科学研究面上资助项目(202103021224024)

山西省基础研究计划青年科学研究资助项目(202103021223021)

山西省重点研发计划资助项目(202202020101004)