基于主从博弈的分层联邦学习激励机制研究

贾云健; 黄宇; 梁靓; 万杨亮; 周继华

doi:10.11999/JEIT220175

基于主从博弈的分层联邦学习激励机制研究

doi: 10.11999/JEIT220175

1.
重庆大学微电子与通信工程学院重庆 400044
2.
95696部队重庆 400030
3.
重庆金美通信有限责任公司复杂环境通信重庆市重点实验室重庆 400030

基金项目: 国家自然科学基金(62071075, 61971077)，重庆市自然科学基金(cstc2020jcyj-msxmX0704)

详细信息

作者简介:
贾云健：男，博士，教授，研究方向为新一代移动通信网络、网络内生安全

黄宇：男，硕士生，研究方向为联邦学习

梁靓：女，博士，副教授，研究方向为移动通信网络、可信网络

万杨亮：女，硕士，工程师，研究方向为计算机网络与无线通信

周继华：男，博士，研究员，研究方向为无线通信

通讯作者:
梁靓　liangliang@cqu.edu.cn

中图分类号: TN92
计量
- 文章访问数: 803
- HTML全文浏览量: 853
- PDF下载量: 241
- 被引次数: 7
出版历程
- 收稿日期: 2022-02-25
- 修回日期: 2022-06-27
- 录用日期: 2022-08-15
- 网络出版日期: 2022-08-16
- 刊出日期: 2023-04-10

Research on Hierarchical Federated Learning Incentive Mechanism Based on Master-Slave Game

1.
School of Microelectronics and Communication Engineering, Chongqing University, Chongqing 400044, China
2.
95696 Troops, Chongqing 400030, China
3.
Chongqing Key Laboratory of Complex Environment Communication, Chongqing Jinmei Communication Co. Ltd. Chongqing 400030, China

Funds: The National Natural Science Foundation of China (62071075, 61971077), The Natural Science Foundation of Chongqing (cstc2020jcyj-msxmX0704)

摘要

摘要: 为了优化分层联邦学习(FL)全局模型的训练时延，针对实际场景中终端设备存在自私性的问题，该文提出一种基于博弈论的激励机制。在激励预算有限的条件下，得到了终端设备和边缘服务器之间的均衡解和最小的边缘模型训练时延。考虑终端设备数量不同，设计了基于主从博弈的可变激励训练加速算法，使得一次全局模型训练时延达到最小。仿真结果显示，所提出的算法能够有效降低终端设备自私性带来的影响，提高分层联邦学习全局模型的训练速度。
- 分层联邦学习 /
- 博弈论 /
- 激励机制
Abstract: In order to optimize the training delay of the hierarchical Federated Learning (FL) global model, focusing on the selfishness of the terminal devices in the actual scene, an incentive mechanism based on game theory is proposed. Under the condition of limited incentive budget, the equilibrium solution between terminal devices and edge servers and the minimum edge model training delay are obtained. Considering the different number of terminal devices, a variable incentive training acceleration algorithm based on Stackelberg game is designed to minimize the training delay of a global model. Simulation results demonstrate that the proposed algorithm can effectively reduce the impact of terminal devices selfishness and improve the training speed of hierarchical federated learning global model.
- Hierarchical Federated Learning (FL) /
- Game theory /
- Incentive mechanism

HTML全文

1. 引言

随着各种智能设备的不断普及，依赖数据和计算能力的机器学习技术得到了迅速发展。为了解决机器学习模型训练面临的数据安全问题，2017年谷歌提出了一种新的分布式机器学习方法——联邦学习(Federated Learning, FL)^[1]。在联邦学习的架构中，设备用户的原始数据不会上传至数据中心，而是留在设备本地进行模型训练，设备只上传训练出的模型参数^[2]。联邦学习将机器学习与在中心服务器中获取、存储和训练数据分离开来，实现了用户数据隐私保护^[3]。

自从谷歌提出联邦学习这个概念后，联邦学习就成为机器学习领域的一个研究热点。McMahan等人^[4]提出了一个基于模型平均的联邦学习实用模型，并进行了广泛的实证评估，这篇文章提出的联邦平均算法(Federated Average algorithm, FedAvg)成为一个经典的联邦学习算法。在此基础上，研究者针对FedAvg算法优化，进行了一系列研究。Li等人^[5]在FedAvg的基础上引入了一个修正项，提出了FedProx (FedAvg with the Proximal term)算法，它允许在设备之间局部地执行可变量的工作，并且依赖这个修正项来确保方法的稳定性，解决了联邦学习固有的系统异质性和统计异质性问题。Mills等人^[6]采用分布式Adam优化技术和模型压缩技术，提出了一种改进的FedAvg算法CE-FedAvg(Communication-Efficient FedAvg)，该算法可以减少达到目标精度所需的通信轮次和每一轮需要加载的数据量，解决了联邦学习在物联网边缘计算的高效通信问题。Li等人^[7]则从算法的公平性角度出发，提出了q-Fair FL算法，它重新权衡了FedAvg算法中的目标函数，在损失函数中分配更高的权重给损失较高的设备，从而使训练精度分布更加均匀。为了进一步优化联邦学习的性能，有研究者对传统联邦学习框架进行了改进。Liu等人^[8]将基于边缘和基于云的联邦学习结合起来，提出了分层联邦学习架构，该分层联邦学习架构与基于云的联邦学习架构相比，模型训练时间和终端设备的能耗都得到了降低。Abad等人^[9]通过分簇法研究了在蜂窝网中的分层联邦问题，优化了分层联邦学习的全局通信时延。

然而不管是针对传统联邦学习框架还是分层联邦学习框架，目前已有的研究大多集中在优化联邦学习算法以提高模型训练性能上，用于激励终端设备参加模型训练的激励机制在很大程度上却被忽视了。大多数流行的分布式训练算法都是使用小批量随机梯度下降^[10]，这在实际训练中，需要等待每一个同步批次中最慢的设备，导致随机优化的完全同步往往很慢，即受到“掉队效应”^[11]的影响，这在异构网络中更为明显。同时，目前的大多数研究都做出了一个乐观的假设，即所有的终端设备在受到邀请时，都将无条件地参与联邦学习。这在现实世界中是不实际的，因为在联邦模型训练过程中，终端设备在计算和通信方面承受着相当大的开销^[12]，如果没有精心设计的激励机制，具有自私性的终端设备将不会拿出足够的资源甚至不愿意加入到联邦学习任务中来，这将导致十分严重的“掉队效应”，使得模型的训练时间大大增加，影响联邦学习的使用。

针对上述问题，本文在分层联邦学习框架下，考虑实际场景中每个边缘服务器下连接的终端设备数量不同，首先对模型训练过程进行了建模分析，得出一次全局模型训练的时间消耗和资源消耗。然后在终端设备和边缘服务器之间设计了两层主从博弈(即Stackelberg博弈^[13])，通过调整分配给每个边缘服务器的激励预算值，提出了基于主从博弈的可变激励训练加速算法。该算法能够刺激终端设备更加积极地参与到联邦学习的任务中来，有效地减小“掉队效应”的影响，从而最小化全局模型训练时间。

2. 系统模型

如图1所示在分层FL架构中，假设有一个云服务器 $C$ ，边缘服务器集合为 $\mathcal{N} = \{ {i}:{i = }1,2, \cdots ,{N}\}$ ，边缘服务器 $i$ 下连接的终端设备集合为 ${\mathcal{M}_{i}} = \{ {m}: {m = }1,2, \cdots ,{M}\}$ ，每个终端设备集合大小不相同。考虑完全同步的FL，完成一次全局训练过程如下：

图 1 系统模型图

下载: 全尺寸图片幻灯片

终端设备端。终端设备 $m$ 基于本地的数据集来进行本地模型训练，假设所有的终端设备的本地数据集大小相同，为了达到相同的本地模型精度 $\theta \in (0,1)$ ，终端设备 $m$ 需要进行迭代的次数可以表示为^[14]

$L(\theta ) = \mu {\log _2}\left(\frac{1}{\theta }\right)$

(1)

其中， $\mu$ 是一个取决于数据集大小和机器学习任务的参数。 ${f_{i:m}}$ 表示边缘服务器 $i$ 下的终端设备 $m$ 进行本地计算时的CPU频率， ${C_m}$ 表示完成1次本地迭代计算任务需要的总的CPU转圈数。那么完成 $L(\theta )$ 次本地迭代，边缘服务器 $i$ 下的终端设备 $m$ 所消耗的能量和时间可以分别表示为

$\qquad\qquad e_{i:m}^{{\rm{cmp}}} = L(\theta )k{C_m}{({f_{i:m}})^2}$

(2)

$\qquad\qquad t_{i:m}^{{\rm{cmp}}} = L(\theta )\frac{{{C_m}}}{{{f_{i:m}}}}$

(3)

其中， $k$ 是一个取决于芯片结构的系数。为了使终端设备投入更多的计算资源以减小本地训练模型所花的时间，边缘服务器端会引入激励机制，即边缘服务器 $i$ 向其下面的终端设备提供奖励， ${q_{i:m}}$ 表示边缘服务器 $i$ 对其服务范围内的终端设备 $m$ 提供的CPU频率单价，那么终端设备 $m$ 迭代一次获得的收入为 ${q_{i:m}}{f_{i:m}}$ 。本地模型精度达到 $\theta$ 之后，终端设备向对应的边缘服务器上传训练得到的参数。假设每个边缘服务器能够分配给终端设备的信道总带宽均为 $B$ ，边缘服务器将其均分给下面的每一个终端设备，那么传输率可以表示为

${r_{m \to i}} = \frac{B}{m}{\log _2}\left(1 + \frac{{{h_m}{u_m}}}{{{N_0}}}\right)$

(4)

其中， ${N_0}$ 为噪声功率， ${u_m}$ 为传输功率， ${h_m}$ 为信道增益。终端设备 $m$ 完成一次参数传输至边缘服务器 $i$ 所需要的时间为

$t_{m \to i}^{{\rm{com}}} = \frac{{{d_m}}}{{{r_{m \to i}}}}$

(5)

其中， ${d_m}$ 表示终端设备 $m$ 传输的参数量，所需要的能量为

$e_{m \to i}^{{\rm{com}}} = t_{m \to i}^{{\rm{com}}}{u_m}$

(6)

边缘服务器端。边缘服务器 $i$ 在收到终端设备传来的参数后，会进行聚合然后再分发下去。以上的过程会迭代多次，直到所有的边缘服务器达到一个相同边缘服务器模型精度 $\varepsilon$ 。为了达到所需精度，对于一个凸的机器学习任务，边缘服务器需要迭代的次数可以表示为^[14]

$I(\varepsilon ,\theta ) = \frac{{\delta \left({\log_2}\left(\dfrac{1}{\varepsilon }\right)\right)}}{{1 - \theta }}$

(7)

其中， $\delta$ 是取决于学习任务的参数。由于边缘服务器通常拥有强大的计算能力和稳定的能量供给，所以边缘服务器端的模型参数聚合和分发所产生的时间与能量消耗在本文中没有考虑。对于终端设备来说，接收分发下来的参数所消耗的时间和能量相比于它上传参数要小得多，在这里本文也不予考虑。因此，边缘服务器 $i$ 完成 $I(\varepsilon ,\theta )$ 次迭代，所需要的时间为

${T_i} = I(\varepsilon ,\theta )[\mathop {\max }\limits_{m \in {\mathcal{M}_i}} (t_{i:m}^{{\rm{cmp}}}) + t_{m \to i}^{{\rm{com}}}]$

(8)

终端设备 $m$ 消耗的总能量为

${E_{i:m}} = I(\varepsilon ,\theta )(e_{i:m}^{{\rm{cmp}}} + e_{m \to i}^{{\rm{com}}})$

(9)

边缘服务器会向云服务器上传满足精度要求的边缘服务器模型参数，假设边缘服务器的传输率都为 ${r_i}$ ，上传的参数量为 ${d_i}$ ，那么上传1次参数，边缘服务器的时间和能量消耗分别为

$t_{i \to C}^{{\rm{com}}} = \frac{{{d_i}}}{{{r_i}}}\qquad$

(10)

$e_{i \to C}^{{\rm{com}}} = {u_i}t_{i \to C}^{{\rm{com}}}$

(11)

其中， ${u_i}$ 表示边缘服务器的传输功率。

云服务器端：在接收到边缘服务器端传来的模型参数后，云服务器端进行参数聚合并更新模型，这样就完成了一次全局迭代。相较于其他环节，这个聚合时间非常短，本文也不考虑。那么，一次全局迭代，所需要的总时间为

$T = \mathop {\max }\limits_{i \in \mathcal{N}} {T_i} + t_{i \to C}^{{\rm{com}}}$

(12)

云服务器负责分配激励预算给每个边缘服务器，总预算为 $V$ 。边缘服务器 $i$ 所分配到的激励预算为 ${W_i}$ 。定义边缘服务器 $i$ 对于一次全局迭代的时间贡献度为 $\dfrac{1}{{{T_i}}}$ ，时间贡献度越大，表示边缘服务器 $i$ 迭代到所要求的精度的时间越短。云服务器会基于每个边缘服务器的时间贡献度来给予边缘服务器奖励，云服务器端总的奖励为 ${R_c}$ ，边缘服务器 $i$ 从云服务器端获得的奖励定义为 ${R_c}\dfrac{1}{{{T_i}}}$ 。

3. 基于主从博弈的激励机制

3.1 博弈问题定义

本文考虑信息对称场景，即每个终端设备会在训练开始前向其所连接的边缘服务器报告自己能够提供的最大算力、本地数据集大小等先验信息。在终端设备层和边缘服务器层之间引入主从博弈(即Stackelberg博弈)。将终端设备作为跟随者(follower)，边缘服务器作为领导者(leader)。边缘服务器 $i$ 决定给每个终端设备 $m$ 的CPU频率单价 ${q_{i:m}} = {q_{i:1}}, {q_{i:2}}, \cdots ,{q_{i:m}}$ 。根据报价，每个边缘服务器服务范围内的各个终端设备向其报告自己用于参与训练的CPU频率 ${f_{i:m}} = {f_{i:1}},{f_{i:2}}, \cdots ,{f_{i:m}}$ ，然后边缘服务器再调整单价 ${q_{i:m}}$ 。边缘服务器 $i$ 下的终端设备 $m$ 的效用函数可以表示为

${U_{i:m}} = I(\varepsilon ,\theta )L(\theta ){q_{i:m}}{f_{i:m}} - \eta {E_{i:m}}$

(13)

其中，第1项为终端设备 $m$ 完成一次全局迭代获得的激励奖励，第2项为总的计算和传输能耗。系数 $\eta$ 用于匹配效用函数前后两项的数量级。边缘服务器 $i$ 的效用函数可以表示为

${U_i} = {R_c}\frac{1}{{{T_i}}} - \sum\limits_{m \in {\mathcal{M}_i}} {{q_{i:m}}} {f_{i:m}} - \eta e_{i \to C}^{{\rm{com}}}$

(14)

其中，第1项为边缘服务器 $i$ 从云服务器获得的奖励，第2项为边缘服务器 $i$ 向下面的终端设备支出的激励总和，第3项为边缘服务器 $i$ 上传参数的传输能耗。

博弈框架如图2所示。首先明确引入激励机制的目的是减小完成一次全局迭代的时间。云服务器作为激励预算分配者(Allocator)，负责为每个边缘服务器分配用于激励的预算 ${W_i}$ ，然后每个边缘服务器和其服务范围内的终端设备形成1个博弈簇，进行Stackelberg博弈。在1个博弈簇内，每个终端设备 $m \in {\mathcal{M}_i}$ 根据边缘服务器 $i$ 的激励报价，决定自己投入训练任务的CPU频率，从而最大化自己的效用函数。故会产生 $m$ 个下层子博弈问题。边缘服务器 $i$ 根据其服务范围内的所有终端设备的CPU频率投入情况，再重新调整自己给出的激励报价，最大化自己的效用函数。故产生一个上层子博弈问题。一个博弈簇内上下两层子博弈反复进行，直到达到纳什均衡点。

图 2 博弈框架图

下载: 全尺寸图片幻灯片

下层子博弈问题定义为

$\left.\begin{split} & \mathop {\max {\text{ }}}\limits_{{f_{i:m}}} {U_{i:m}} = I(\varepsilon ,\theta )L(\theta ){q_{i:m}}{f_{i:m}} - \eta {E_{i:m}} \\ & {\text{ s}}{\text{.t}}{\text{. }}f_{i:m}^{\min } \le {f_{i:m}} \le f_{i:m}^{\max } \end{split}\right\}$

(15)

上层子博弈问题定义为

$\left.\begin{split} & \mathop {\max {\text{ }}}\limits_{{q_{i:m}}} {U_i} = {R_c}\frac{1}{{{T_i}}} - \sum\limits_{m \in {\mathcal{M}_i}} {{q_{i:m}}} {f_{i:m}} - \eta e_{i \to C}^{{\rm{com}}} \\ & {\text{ s}}{\text{.t}}{\text{. }}\sum\limits_{m \in {\mathcal{M}_i}} {{q_{i:m}}} {f_{i:m}} \le {W_i} \\ & \qquad \sum\limits_{i \in \mathcal{N}} {{W_i} \le V} \end{split}\right\}$

(16)

3.2 博弈均衡解分析

3.2.1 下层子博弈求解

为了找到下层子博弈的均衡解，首先对 ${U_{i:m}}$ 求1阶导数，可以得到

$\frac{{\partial {U_{i:m}}}}{{\partial {f_{i:m}}}} = I(\varepsilon ,\theta )L(\theta ){q_{i:m}} - 2\eta I(\varepsilon ,\theta )L(\theta )k{C_m}{f_{i:m}}$

(17)

因为

$\frac{{{\partial ^2}{U_{i:m}}}}{{\partial f_{i:m}^2}} = - 2\eta I(\varepsilon ,\theta )L(\theta )k{C_m} < 0$

(18)

所以 ${U_{i:m}}$ 是严格凹的，保证了纳什均衡解存在且唯一。可得均衡解为

$f_{i:m}^ * ({q_{i:m}}) = {\rm{max}}\left\{ \frac{{{q_{i:m}}}}{{2\eta k{C_m}}},f_{i:m}^{\max }\right\}$

(19)

3.2.2 上层子博弈求解

边缘服务器 $i$ 的效用函数式(14)由3部分组成，(1) ${R_c}\dfrac{1}{{{T_i}}}$ ，(2) $- \displaystyle\sum\limits_{m \in {\mathcal{M}_i}} {{q_{i:m}}} {f_{i:m}}$ ，(3) $- \eta e_{i \to C}^{{\rm{com}}}$ 。由前面系统模型的描述中可知， $- \eta e_{i \to C}^{{\rm{com}}}$ 可视为一个常量，所以下面分析(1)和(2)的凹凸情况。

分析(1)，令 $h = {R_c}\dfrac{1}{{{T_i}}}$ 并代入 $f_{i:m}^ *$ 可得表达式

$h({q_{i:m}}) = {R_c}\frac{1}{{I(\varepsilon ,\theta ) \left[\mathop {\max }\limits_{m \in {\mathcal{M}_i}} \left( {{2\eta kC_m^2L(\theta )}}/{{{q_{i:m}}}}\right) + t_{m \to i}^{{\rm{com}}}\right]}}$

(20)

$h({q_{i:m}})$ 的黑塞矩阵定义为

${\mathbf{A}} = \left( {\begin{array}{*{20}{c}} {\dfrac{{{\partial ^2}h}}{{\partial q_{i:1}^2}}}& \cdots &{\dfrac{{{\partial ^2}h}}{{\partial {q_{i:1}}\partial {q_{i:m}}}}} \\ \vdots & \ddots & \vdots \\ {\dfrac{{{\partial ^2}h}}{{\partial {q_{i:m}}\partial {q_{i:1}}}}}& \cdots &{\dfrac{{{\partial ^2}h}}{{\partial q_{i:m}^2}}} \end{array}} \right)$

(21)

由于

$\frac{{{\partial ^2}h}}{{\partial q_{i:m}^2}} = \frac{{ - 4\eta k{R_c}L(\theta )I{{(\varepsilon ,\theta )}^2}C_m^2t_{m \to i}^{{\rm{com}}}}}{{{{(2\eta kL(\theta )I(\varepsilon ,\theta )C_m^2 + I(\varepsilon ,\theta )t_{m \to i}^{{\rm{com}}}{q_{i:m}})}^3}}}$

(22)

${\text{ }}\frac{{{\partial ^2}h}}{{\partial {q_{i:m}}\partial {q_{i:n}}}} = 0{\text{ }}(m \ne n)$

(23)

所以 $h({q_{i:m}})$ 的黑塞矩阵可进一步表示为

${\mathbf{A}} = \left( {\begin{array}{*{20}{c}} {\dfrac{{ - 4\eta k{R_c}L(\theta )I{{(\varepsilon ,\theta )}^2}C_m^2t_{1 \to i}^{{\rm{com}}}}}{{{{(2\eta kL(\theta )I(\varepsilon ,\theta )C_m^2 + I(\varepsilon ,\theta )t_{1 \to i}^{{\rm{com}}}{q_{i:1}})}^3}}}}& \ldots &0 \\ \vdots & \ddots & \vdots \\ 0& \cdots &{\dfrac{{ - 4\eta k{R_c}L(\theta )I{{(\varepsilon ,\theta )}^2}C_m^2t_{m \to i}^{{\rm{com}}}}}{{{{(2\eta kL(\theta )I(\varepsilon ,\theta )C_m^2 + I(\varepsilon ,\theta )t_{m \to i}^{{\rm{com}}}{q_{i:m}})}^3}}}} \end{array}} \right)$

(24)

矩阵 ${\mathbf{A}}$ 的所有特征值均小于等于0，矩阵 ${\mathbf{A}}$ 负定，所以 $h({q_{i:m}})$ 为凹函数。

分析(2)，令 $g = - \displaystyle\sum\limits_{m \in {\mathcal{M}_i}} {{q_{i:m}}} {f_{i:m}}$ ，代入 $f_{i:m}^ *$ 可得表达式

$g({q_{i:m}}) = - \sum\limits_{m \in {\mathcal{M}_i}} {\frac{1}{{2\eta k{C_m}}}} {q_{i:m}}^2$

(25)

$g({q_{i:m}})$ 对 ${q_{i:m}}$ 求2阶导可得

$\frac{{{\partial ^2}g}}{{\partial q_{i:m}^2}} = - \frac{1}{{\eta k{C_m}}} < 0$

(26)

所以 $g({q_{i:m}})$ 为严格凹的。根据以上分析可知，边缘服务器 $i$ 的效用函数 ${U_i}$ 为一个凹函数。

下面求解上层子博弈。式(16)等效于

$\left.\begin{split} & \mathop {\min {\text{ }}}\limits_{{q_{i:m}}} {U_i} = - {R_c}\frac{1}{{{T_i}}} + \sum\limits_{m \in {\mathcal{M}_i}} {{q_{i:m}}} f_{i:m}^ * + \eta e_{i \to C}^{{\rm{com}}} \\ & {\text{ s}}{\text{.t}}{\text{. }}{{{y}}_1} = \sum\limits_{m \in {\mathcal{M}_i}} {{q_{i:m}}} f_{i:m}^ * - {W_i} \le 0 \\ & \qquad {{{y}}_2} = \sum\limits_{i \in \mathcal{N}} {{W_i} - V \le 0} \end{split} \right\}$

(27)

上述问题变成一个凸问题，可以用拉格朗日乘数法来解。其拉格朗日函数可以表示为

$\begin{split} L({q_{i:m}},{\lambda _1},{\lambda _2}) =& - {R_c}\frac{1}{{{T_i}}} + {\lambda _1}\left(\sum\limits_{m \in {\mathcal{M}_i}} {{q_{i:m}}f_{i:m}^ * } - {W_i}\right)\\ & + {\lambda _2}\left(\sum\limits_{i \in \mathcal{N}} {{W_i} - V} {\text{ }}\right)\\[-21pt] \end{split}$

(28)

通过KKT条件，可以推导出充分必要条件

$\begin{split} \frac{{\partial L}}{{\partial {q_{i:m}}}} =& - \frac{{2\eta k{R_c}L(\theta )I(\varepsilon ,\theta )C_m^2}}{{{{(2\eta kL(\theta )I(\varepsilon ,\theta )C_m^2 + I(\varepsilon ,\theta )t_{m \to i}^{{\rm{com}}}{q_{i:m}})}^2}}} \\ & + {\lambda _1}\frac{1}{{\eta k{C_m}}}{q_{i:m}} = 0 \end{split}$

(29)

$\begin{split} {\lambda _1}{y_1} & = {\lambda _1}\left(\sum\limits_{m \in {\mathcal{M}_i}} {{q_{i:m}}f_{i:m}^ * } - {W_i}\right) \\ & = {\lambda _1}\left(\sum\limits_{m \in {\mathcal{M}_i}} {\frac{1}{{2\eta k{C_m}}}q_{i:m}^2} - {W_i}\right) = 0 \end{split}$

(30)

${\lambda _1} \ge 0$

(31)

由条件式(31)可得

${\lambda _1} = \frac{{2{\eta ^2}{k^2}{R_c}L(\theta )I(\varepsilon ,\theta )C_m^3}}{{{q_{i:m}}{{(2\eta kL(\theta )I(\varepsilon ,\theta )C_m^2 + I(\varepsilon ,\theta )t_{m \to i}^{{\rm{com}}}{q_{i:m}})}^2}}} > 0$

(32)

所以

$\sum\limits_{m \in {\mathcal{M}_i}} {\frac{1}{{2\eta k{C_m}}}q_{i:m}^2} - {W_i} = 0$

(33)

表明解是存在的。当边缘服务器 $i$ 给每一个终端设备 $m$ 的 ${q_{i:m}}$ 相同时，可解得

${q_{i:m}} = \sqrt {\frac{{2\eta k{C_m}}}{m}{W_i}}$

(34)

这个特殊解的实际意义在于如果 ${q_{i:m}}$ 不相同，那么时间会由算得最慢的那个终端设备决定，从而使得边缘服务器 $i$ 的效用函数降低。只有当边缘服务器 $i$ 将激励预算 ${W_i}$ 全部使用，且分配下去的 ${q_{i:m}}$ 相等时，边缘服务器 $i$ 以及终端设备 $m$ 这一簇的时间消耗 ${T_i}$ 才能达到最小，从而使得边缘服务器 $i$ 的效用函数达到最大值。

3.3 博弈执行过程

初始化阶段，云服务器将总预算 $V$ 均分给每个边缘服务器，此时 ${W_1} = {W_2} = \cdots = {W_i} = \dfrac{V}{i}$ 。

步骤1　边缘服务器 $i$ 刚开始随意分配激励单价 ${q_{i:m}}$ ，终端设备 $m$ 会提供相应的算力，使得自己的效用函数 ${U_{i:m}}$ 达到最大。此时边缘服务器 $i$ 会发现它完成 $I(\varepsilon ,\theta )$ 次迭代的时间是受限于计算最慢的那个终端设备，故它会重新分配 ${q_{i:m}}$ ，激励最慢的终端设备增加算力，从而减小 ${T_i}$ ，增加自己的效用函数 ${U_i}$ 。最终边缘服务器 $i$ 会根据终端设备的个数，均分 ${W_i}$ ，此时的 ${q_{i:m}}$ 即为前面求出的特殊解式(34)。

步骤2　当每个边缘服务器和它连接的终端设备达到均衡点后，边缘服务器 $i$ 得到了 ${T_i}$ 和最终的效用函数 ${U_i}$ 。此时每个边缘服务器 $i$ 会将最终的 ${T_i}$ 上报给云服务器。为了使得一次全局迭代的总时间达到最小，云服务器会根据每个边缘服务器的 ${T_i}$ 大小值调整激励预算分配比例。

步骤3　得到重新分配的激励预算后，每个边缘服务器再重复步骤1，然后云服务器重复步骤2，直到每个边缘服务器的 ${T_i}$ 值最终相等。整个系统达到稳定的状态，且完成一次全局迭代的时间达到最短。

根据上述过程，本文提出了全局模型训练的加速算法，如算法1所示。

算法1　基于主从博弈的可变激励训练加速算法
输入： $\mathcal{N} = \{ {i}:{i = }1,2, \cdots ,{N}\}$ ， ${\mathcal{M}_{i}} = \{ {m}:{m = }{\text{1,2,}} \cdots {\text{,}}{M}\}$ ，计算任务Task，数据集 $D$ ， ${W_1} = {W_2} = \cdots = {W_i} = \dfrac{V}{i}$ 。
输出：激励预算分配的均衡点 ${\mathcal{W}_i} = \{ {W_i},i \in \mathcal{N}\}$ ， ${\mathcal{Q}_{i:m}} = \{ {q_{i:m}},m \in {\mathcal{M}_i}\}$ ，终端设备 $m$ 提供的算力均衡解 $\mathcal{F}_{i:m}^{\text{}} = \{ f_{i:m}^ ,m \in {\mathcal{M}_i}\}$ 。
(1) repeat
(2) for $i$ in $N$ do 　(3) 边缘服务器 $i$ 分配激励单价 $\{ {q_{i:m}},m \in {\mathcal{M}_i}\}$ ，激励单价需满足条件 $\displaystyle\sum\limits_{m \in {\mathcal{M}_i} } { {q_{i:m} } } {f_{i:m} } \le {W_i}$ 。终端设备 $m$ 会提供相应的算力　　　 $\left\{ f_{i:m}^ * = {\rm{max}}\left\{ \dfrac{ { {q_{i:m} } } }{ {2\eta k{C_m} } },f_{i:m}^{\max }\right\} ,m \in {\mathcal{M}_i}\right\}$ ，使得自己的效用 ${U_{i:m}}$ 达到最大。
(4) if $t_{i:m}^{{\rm{cmp}}} \ne t_{i:n}^{{\rm{cmp}}}(m \ne n)$ then
(5) 边缘服务器 $i$ 重新分配 ${q_{i:m}}$ ，使得自己的效用函数 ${U_i}$ 达到最大，同时得到时间 ${T_i}$ 。
(6) end for
(7) if ${T_i} < {T_j}(i \ne j)$ then
(8) 云服务器重新分配 $V$ (减小 ${W_i}$ ，增大 ${W_j}$ )。
(9) Until ${T_i} = {T_j}(i \ne j)$

下载: 导出CSV

| 显示表格

4. 仿真结果与分析

本文用MNIST数据集^[15]来评估所提出的激励机制的性能。随机分配相同数量的10个种类的训练数据给每个终端设备，用随机梯度下降来训练本地模型，学习率为0.1。其他一些参数为：完成1次本地迭代计算任务需要的总的CPU转圈数 ${C_m} = 5\;000$ ，边缘服务器 $i$ 下的终端设备 $m$ 进行本地计算时的CPU频率 ${f_{i:m}} \in [1,{10^9}]$ Hz，信道总带宽 $B = {10^6}$ Hz，噪声功率 ${N_0} = {10^{ - 8}}$ W，传输功率 ${u_m} = 200$ mW，终端设备 $m$ 传输的参数量 ${d_m} = 2\;500$ bit，终端设备 $m$ 进行迭代的次数 $L(\theta ) = 2$ ，边缘服务器需要迭代的次数 $I(\varepsilon ,\theta ) = 5$ ，芯片结构的系数 $k = 2 \times {10^{ - 28}}$ ，系数 $\eta = {10^{18}}$ 。

(1) 边缘服务器与终端设备的博弈迭代过程。为了评估这个过程，本文对一个博弈簇进行仿真实验，在激励预算足够的情况下，探究边缘服务器给出的激励单价对终端设备效用以及边缘服务器自身效用的影响，同时验证引入激励机制能够刺激终端设备投入更多的计算资源，减少本地计算时间。

图3显示的是边缘服务器给出的CPU激励单价对单个终端设备效用值的影响。可见，单个终端设备的效用值随着激励单价的增加逐渐上升并最终达到最大值稳定下来。这是因为随着激励单价 $q$ 的增加，终端设备得到的奖励越来越多，导致其效用不断增加。当激励单价增加到某个值，如图中的 $q = 20$ 时，终端设备会将所有的计算资源都投入到本地模型训练任务中，此时它获得的奖励值达到最大，故效用值也达到最大。而如果 $q$ 继续增加，由于该终端设备之前就已投入了全部的CPU频率资源，所以边缘服务器为了节省激励成本，实际上并不会继续增加真正给到该终端设备的激励单价，故该终端设备的效用值保持最大值不变。

图 3 激励单价

$q$ 与单个终端设备效用的关系

下载: 全尺寸图片幻灯片

图3虽然是显示的单个终端设备效用与激励单价的关系，但是该博弈簇中的所有终端设备都遵循这个关系，当每个终端设备效用值达到最大时，下层子博弈达到均衡点。

图4显示的一个边缘服务器给出的激励单价对其效用值的影响。可以看到，边缘服务器的效用值随着激励单价的增加而增加，最后达到最大值并稳定下来。这是因为增加激励单价 $q$ ，能够刺激终端设备提供更多的算力到模型训练任务中来，从而减小时间 ${T_i}$ ，增大了该边缘服务器对于一次全局迭代的时间贡献度。虽然增加激励单价会导致边缘服务器的激励支出增加，但是它能够从云服务器端获得更多的奖励，故其效用值最终增加。当激励单价增加到某个值，比如图中的 $q = 20$ 时，终端设备将全部算力投入计算，时间 ${T_i}$ 达到最小，该边缘服务器效用值达到最大。同样地，之后激励单价如果继续增加，边缘服务器为了节约激励成本，实际上并不会给予已经完全激励了的终端设备更高的激励单价，故终端设备的效用值保持最大值不变。

图 4 激励单价

$q$ 与单个边缘服务器效用的关系

下载: 全尺寸图片幻灯片

当一个博弈簇中的边缘服务器的效用达到最大时，上层子博弈达到均衡点。当上下两层子博弈同时达到均衡点时，该博弈簇内的Stackelberg博弈达到纳什均衡点。

图5显示的是单个终端设备的本地计算时间与边缘服务器给出的激励单价的关系。可以看到，终端设备的本地计算时间随着激励单价 $q$ 的增加逐渐减少，因为终端设备提供了更多的本地计算资源。当激励单价 $q$ 增大到某个值，比如图中的 $q = 20$ 时，该终端设备贡献出全部的算力，本地计算时间达到最小。此后 $q$ 继续增加，由于没有多余的计算资源，本地计算时间不会再继续减小，故保持最小值不变。

图 5 激励单价

$q$ 与单个终端设备本地计算时间的关系

下载: 全尺寸图片幻灯片

以上的仿真实验虽然是对一个博弈簇，在激励预算分配足够的情况下进行的实验，但是所有的博弈簇中的博弈迭代过程都遵循上述分析的结果。并且在激励预算不够的情况下，边缘服务器最终会根据其服务范围内的终端设备个数，均分激励预算，即满足前文解出的特殊解 ${q_{i:m}} = \sqrt {\dfrac{{2\eta k{C_m}}}{m}{W_i}}$ ，从而博弈达到纳什均衡点，最小化本地计算时间 ${T_i}$ 。

(2) 云服务器激励预算分配达到平衡点的过程。假设边缘服务器数量为2，边缘服务器1下连接的终端设备数量为1 000个，边缘服务器2下连接的数量为1 200个，云服务器能够分配的总激励预算 $V = 40\;000$ 。刚开始时分配情况为 ${W_1} = {W_2} = {V}/{2} = 20\;000$ ，然后云服务器会调整分配情况，一部分分给 ${W_1}$ ，剩余部分全部分给 ${W_2}$ ，即 ${W_2} = V - {W_1}$ 。

从图6可以看到，刚开始均分时，由于边缘服务器1连接的终端设备数量更少，故 ${T_1}$ < ${T_2}$ ，全局训练时间取决于较大者。然后云服务器开始减小 ${W_1}$ ，同时等量增大 ${W_2}$ 。 ${T_1}$ 随着 ${W_1}$ 的减小而增大，因为边缘服务器1连接的终端设备得到的激励在减小，用于计算的CPU频率降低，本地计算时间增加，导致最终 ${T_1}$ 增大。 ${W_1}$ 减小，相应地 ${W_2}$ 在增加，边缘服务器2获得更多的激励预算，故 ${T_2}$ 逐渐减小。当云服务器分配 ${W_1} = 8\;700{\text{ }}$ ， ${W_2} = 31\;300$ 时， ${T_1} = {T_2}$ ，如图6中的两条曲线的交点处所示，此时全局训练时间达到最小，激励预算分配达到均衡点。

图 6 不同

${W_1}$ 的值与

${T_1}$ ,

${T_2}$ 的关系

下载: 全尺寸图片幻灯片

(3)将本文提出的基于主从博弈的可变激励训练加速算法与没有设计激励机制的算法^[8]进行比较。边缘服务器个数设置为2个，每个边缘服务器下连接不同数量的终端设备。两个边缘服务器连接的终端设备总数分别设置为800个、1 000个、1 200个。

在没有设计激励机制的算法中，为了反映真实情况下终端设备的自私性，本文假设会有一定比例的终端设备不会完全贡献自己的资源甚至不愿意参与到联邦学习中。

从图7可以看到，在没有激励机制的情况下，全局模型的训练时延随着终端设备数的增加而减小，这是因为虽然设备存在自私性，但是随着设备的基数增加，总的算力资源是增加的。而在本文提出的激励机制算法中，由于激励预算是一定的，所以随着设备数量的增加，每个设备能够分到的激励量在减小，所以总的算力在减小，导致总时间增加。但是，在不同终端设备总数的情况下，与没有激励机制的算法相比，本文提出的带有激励机制的算法均能够有效地刺激终端设备积极参与到训练中来，提供更多的资源到训练过程中，从而有效降低了全局模型训练的总时延。

图 7 两种算法在不同终端设备总数下训练总时间的比较

下载: 全尺寸图片幻灯片

5. 结束语

本文面向分层联邦学习框架，针对联邦学习中终端设备存在自私性而影响全局模型训练时间的问题，设计了基于主从博弈的激励机制。该机制通过对分层联邦学习模型训练过程进行建模，利用可变激励训练加速算法，不断调整分配给边缘服务器的激励预算，使得边缘服务器和终端设备达到纳什均衡点的同时，最小化1次全局模型训练时间。仿真结果表明，本文所提算法能够有效地降低终端设备自私性带来的影响，优化分层联邦学习全局模型的训练时延。

图 1 系统模型图

下载: 全尺寸图片幻灯片

图 2 博弈框架图

下载: 全尺寸图片幻灯片

图 3 激励单价 $q$ 与单个终端设备效用的关系

下载: 全尺寸图片幻灯片

图 4 激励单价 $q$ 与单个边缘服务器效用的关系

下载: 全尺寸图片幻灯片

图 5 激励单价 $q$ 与单个终端设备本地计算时间的关系

下载: 全尺寸图片幻灯片

图 6 不同 ${W_1}$ 的值与 ${T_1}$ , ${T_2}$ 的关系

下载: 全尺寸图片幻灯片

图 7 两种算法在不同终端设备总数下训练总时间的比较

下载: 全尺寸图片幻灯片

算法1　基于主从博弈的可变激励训练加速算法
输入： $\mathcal{N} = \{ {i}:{i = }1,2, \cdots ,{N}\}$ ， ${\mathcal{M}_{i}} = \{ {m}:{m = }{\text{1,2,}} \cdots {\text{,}}{M}\}$ ，计算任务Task，数据集 $D$ ， ${W_1} = {W_2} = \cdots = {W_i} = \dfrac{V}{i}$ 。
输出：激励预算分配的均衡点 ${\mathcal{W}_i} = \{ {W_i},i \in \mathcal{N}\}$ ， ${\mathcal{Q}_{i:m}} = \{ {q_{i:m}},m \in {\mathcal{M}_i}\}$ ，终端设备 $m$ 提供的算力均衡解 $\mathcal{F}_{i:m}^{\text{}} = \{ f_{i:m}^ ,m \in {\mathcal{M}_i}\}$ 。
(1) repeat
(2) for $i$ in $N$ do 　(3) 边缘服务器 $i$ 分配激励单价 $\{ {q_{i:m}},m \in {\mathcal{M}_i}\}$ ，激励单价需满足条件 $\displaystyle\sum\limits_{m \in {\mathcal{M}_i} } { {q_{i:m} } } {f_{i:m} } \le {W_i}$ 。终端设备 $m$ 会提供相应的算力　　　 $\left\{ f_{i:m}^ * = {\rm{max}}\left\{ \dfrac{ { {q_{i:m} } } }{ {2\eta k{C_m} } },f_{i:m}^{\max }\right\} ,m \in {\mathcal{M}_i}\right\}$ ，使得自己的效用 ${U_{i:m}}$ 达到最大。
(4) if $t_{i:m}^{{\rm{cmp}}} \ne t_{i:n}^{{\rm{cmp}}}(m \ne n)$ then
(5) 边缘服务器 $i$ 重新分配 ${q_{i:m}}$ ，使得自己的效用函数 ${U_i}$ 达到最大，同时得到时间 ${T_i}$ 。
(6) end for
(7) if ${T_i} < {T_j}(i \ne j)$ then
(8) 云服务器重新分配 $V$ (减小 ${W_i}$ ，增大 ${W_j}$ )。
(9) Until ${T_i} = {T_j}(i \ne j)$

下载: 导出CSV

参考文献(15)

[1]	MCMAHAN B and RAMAGE D. Federated learning: Collaborative machine learning without centralized training data[EB/OL]. https://starrymind.tistory.com/180, 2017.
[2]	NIKNAM S, DHILLON H S, and REED J H. Federated learning for wireless communications: Motivation, opportunities, and challenges[J]. IEEE Communications Magazine, 2020, 58(6): 46–51. doi: 10.1109/MCOM.001.1900461
[3]	LIU Yi, PENG Jialiang, KANG Jiawen, et al. A secure federated learning framework for 5G networks[J]. IEEE Wireless Communications, 2020, 27(4): 24–31. doi: 10.1109/MWC.01.1900525
[4]	McMAHAN B, MOORE E, RAMAGE D, et al. Communication-efficient learning of deep networks from decentralized data[C]. The 20th International Conference on Artificial Intelligence and Statistics, Fort Lauderdale, USA, 2017: 1273–1282.
[5]	LI Tian, SAHU A K, ZAHEER M, et al. Federated optimization in heterogeneous networks[C]. Machine Learning and Systems 2020, Austin, USA, 2020, 2: 429–450.
[6]	MILLS J, HU Jia, and MIN Geyong. Communication-efficient federated learning for wireless edge intelligence in IoT[J]. IEEE Internet of Things Journal, 2020, 7(7): 5986–5994. doi: 10.1109/JIOT.2019.2956615
[7]	LI Tian, SANJABI M, BEIRAMI A, et al. Fair resource allocation in federated learning[C]. The 8th International Conference on Learning Representations (ICLR), Addis Ababa, Ethiopia, 2019: 1–27.
[8]	LIU Lumin, ZHANG Jun, SONG S H, et al. Client-edge-cloud hierarchical federated learning[C]. 2020 IEEE International Conference on Communications (ICC), Dublin, Ireland, 2020: 1–6.
[9]	ABAD M S H, OZFATURA E, GUNDUZ D, et al. Hierarchical federated learning ACROSS heterogeneous cellular networks[C]. 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Barcelona, Spain, 2020: 8866–8870.
[10]	SUN Haifeng, LI Shiqi, YU F R, et al. Toward communication-efficient federated learning in the internet of things with edge computing[J]. IEEE Internet of Things Journal, 2020, 7(11): 11053–11067. doi: 10.1109/JIOT.2020.2994596
[11]	SHI Yuanming, YANG Kai, JIANG Tao, et al. Communication-efficient edge AI: Algorithms and systems[J]. IEEE Communications Surveys & Tutorials, 2020, 22(4): 2167–2191. doi: 10.1109/COMST.2020.3007787
[12]	LUO Siqi, CHEN Xu, WU Qiong, et al. HFEL: Joint edge association and resource allocation for cost-efficient hierarchical federated edge learning[J]. IEEE Transactions on Wireless Communications, 2020, 19(10): 6535–6548. doi: 10.1109/TWC.2020.3003744
[13]	KHAN L U, RAJ PANDEY S, TRAN N H, et al. Federated learning for edge networks: Resource optimization and incentive mechanism[J]. IEEE Communications Magazine, 2020, 58(10): 88–93. doi: 10.1109/MCOM.001.1900649
[14]	TRAN N H, BAO Wei, ZOMAYA A, et al. Federated learning over wireless networks: Optimization model design and analysis[C]. IEEE INFOCOM 2019-IEEE Conference on Computer Communications, Paris, France, 2019: 1387–1395.
[15]	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. doi: 10.1109/5.726791

施引文献

期刊类型引用(2)

1.	邓卫民. 基于DAFR的共存无线网络自静态干扰缓解方案. 电视技术. 2014(13): 168-172 . 百度学术
2.	王义君, 钱志鸿, 王雪, 孙大洋. 基于6LoWPAN的物联网寻址策略研究. 电子与信息学报. 2012(04): 763-769 . 本站查看

其他类型引用(5)

资源附件(0)

访问统计

图(7) / 表(1)

计量

文章访问数: 803
HTML全文浏览量: 853
PDF下载量: 241
被引次数: 7

1. 引言
2. 系统模型
3. 基于主从博弈的激励机制
3.1 博弈问题定义
3.2 博弈均衡解分析
3.3 博弈执行过程
4. 仿真结果与分析
5. 结束语

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

基于主从博弈的分层联邦学习激励机制研究

doi: 10.11999/JEIT220175

通讯作者:
梁靓　liangliang@cqu.edu.cn

计量

Research on Hierarchical Federated Learning Incentive Mechanism Based on Master-Slave Game

1. 引言

2. 系统模型

3. 基于主从博弈的激励机制

3.1 博弈问题定义

3.2 博弈均衡解分析

3.2.1 下层子博弈求解

3.2.2 上层子博弈求解

3.3 博弈执行过程

4. 仿真结果与分析

5. 结束语

期刊类型引用(2)

其他类型引用(5)

计量

目录

1. 引言

2. 系统模型

3. 基于主从博弈的激励机制

3.1 博弈问题定义

3.2 博弈均衡解分析

3.3 博弈执行过程

4. 仿真结果与分析

5. 结束语

留言板

基于主从博弈的分层联邦学习激励机制研究

doi: 10.11999/JEIT220175

通讯作者: 梁靓 liangliang@cqu.edu.cn

计量

出版历程

Research on Hierarchical Federated Learning Incentive Mechanism Based on Master-Slave Game

1. 引言

2. 系统模型

3. 基于主从博弈的激励机制

3.1 博弈问题定义

3.2 博弈均衡解分析

3.2.1 下层子博弈求解

3.2.2 上层子博弈求解

3.3 博弈执行过程

4. 仿真结果与分析

5. 结束语

期刊类型引用(2)

其他类型引用(5)

计量

出版历程

目录

1. 引言

2. 系统模型

3. 基于主从博弈的激励机制

3.1 博弈问题定义

3.2 博弈均衡解分析

3.3 博弈执行过程

4. 仿真结果与分析

5. 结束语

通讯作者:
梁靓　liangliang@cqu.edu.cn