郭英芸，高博，卢宇平，张煜，熊轲

1.北京交通大学计算机与信息技术学院，交通数据分析与挖掘北京市重点实验室，智能高速铁路系统前沿科学中心，北京，100044；2.国网能源研究院有限公司，北京，102209

0 引言

集中式机器学习方式需要移动用户向服务器共享其数据，数据共享会破坏数据隐私，一旦数据遭到泄露，用户将面临严重的信息安全问题。此外，大量的数据传输会给网络通信带来压力。联邦学习[1]（Federated Learning，FL）能够在保护数据隐私的情况下利用移动用户的数据。目前，联邦学习在医疗保健[2]、金融服务[3]等领域受到了广泛关注，并取得了初步的研究成果。

但是，基于无线网络的联邦学习仍面临一些挑战。首先，一个联邦模型的学习过程需要多次迭代，这意味着学习期间需要频繁的网络通信。为减少通信负担，避免大量用户同时使用网络，只能选择部分用户作为训练者参与训练，为训练用户分配带宽资源。其次，模型训练会消耗用户的资源，因此它们通常不愿主动参与服务器的训练任务。为提高用户的参与积极性，需要设计合理的激励机制，以覆盖其训练过程产生的成本。最后，移动用户在数据收集能力、计算能力、通信能力等多方面的差异性意味着用户选择方案将影响模型的训练质量。因此，为了提高模型训练质量，需要设计能够准确评估用户贡献、进而选择最佳训练用户并支付报酬的方案，同时优化带宽资源的分配以降低通信时间。

为提高联邦学习的性能，一些文献从用户选择和资源分配角度开展工作：文献[4]提出了一种结合用户选择的联邦学习框架FedCS，它可以管理众多资源异构的用户，并解决具有约束的用户选择问题，加快了模型学习的速度；文献[5]提出了一种基于bandit算法的用户选择策略UCBCS，该策略以更低的通信开销实现更快的收敛，同时提高选择的公平性；文献[6]提出了一种有偏用户选择策略，根据选择偏差对收敛速度的影响进行用户选择，实验表明该方案有助于加快学习速度。在用户选择与带宽分配联合优化方面，文献[7]提出了一种能够权衡单轮收敛时间与全局迭代次数的联合选择与分配算法；文献[8]提出了一种概率选择方案，并设计了一种基于人工神经网络的算法完成带宽分配，实现了收敛时间与学习时间的平衡；文献[9]提出了基于瞬时信道状态和基于统计粒子群优化的两种带宽分配方案，达到了最大化参与用户数量的目标。但是，上述工作都没有考虑用户自私的问题。

为激励用户参与联邦学习，一些文献以设计激励机制的方式提高用户的参与积极性。文献[10]将多维信息归纳为一维选择标准，并基于服务器对用户信息的不同掌握程度分析了最佳的定价方案，解决了用户与服务器间信息不对称的问题。针对具有不同数据隐私保护需求的用户，文献[11]将用户的贡献和隐私成本进行了分类，并通过合同理论建立与隐私类型对应的支付机制。文献[12]分析了异构用户对联邦学习收敛的影响，提出了一种基于主从博弈的激励机制来平衡每次迭代的时间延迟。考虑用户多维私人信息如训练成本、通信时延、数据量等的不同，文献[13]提出一个多维合同方法来设计服务器的最优激励机制，通过求解不同数据量和通信能力的最佳奖励，获得最佳数据量和最短通信时间。文献[14]通过中继网络构建了支持模型传输及自由交易的协作通信平台，模型通过协作中继网络转发给服务器，作为中继节点的用户可额外获得报酬。上述工作虽然解决了激励问题，但未考虑如何优化网络资源的分配。

为综合解决上述问题并提高联邦学习质量，本文提出了一种基于反向多维拍卖的激励机制，主要贡献概括如下：

（1）设计了一种基于反向多维拍卖的激励机制，同时解决服务器端用户选择、带宽分配及报酬决策问题；

（2）通过解决社会福利函数最大化问题实现了用户选择，将带宽分配纳入激励过程，进一步平衡了训练时间，设计了一种保证用户真实报价的支付方案；

（3）通过设计评分函数来选择训练用户，该函数考虑了用户在数据质量、训练时间等方面的差异，并权衡了异构用户的训练质量、延迟和成本；

（4）将带宽分配引入激励过程，进一步平衡整体训练时间和相关成本，提出了一种支持真实投标等必要经济属性的支付策略；

（5）证明了所提出的激励机制满足个体理性、激励相容性和计算高效性等必要的经济学属性，仿真结果表明，与基线方案相比，所提出的IMRMA能够有效提升训练效果，加快收敛速度，降低训练过程的整体时延。

1 系统模型与问题建模

1.1 IMRMA系统模型

如图1所示，考虑包含一个中央服务器和个移动用户的联邦系统。在训练任务开始之前，服务器和用户需就训练任务展开拍卖博弈。为了获得更好的模型，服务器将综合评价用户，选择最佳用户作为模型训练者。同时，服务器将对带宽资源合理分配，并确定支付给用户的报酬。具体地，首先由服务器根据训练任务发起竞价请求，向每个用户广播训练任务及博弈过程的必要信息，其中与分别表示评分函数和数据质量评估函数，为最大时延限制，表示用户单轮训练时间上限。收到竞价请求后，用户需要就训练过程的资源付出作出决策并计算投标。如果能够满足时延限制，则向服务器发送其投标；否则，不发送任何信息，默认放弃任务。收到用户投标后，服务器进行用户选择、带宽分配和支付决策，被选中的用户为拍卖的赢家，即训练用户。

接下来服务器向训练用户发送初始模型，开始训练过程。使用联邦平均算法进行模型训练[15]，首先由服务器向训练用户广播全局模型，用户收到后利用本地数据训练并更新模型，训练完成后将更新的本地模型上传至服务器，之后服务器将所有本地模型聚合形成新的全局模型，至此完成一次模型的更新过程。更新过程将迭代多次，直到达到服务器规定的迭代次数或模型收敛。训练任务完成后，服务器将按照拍卖阶段的约定价格支付训练用户报酬。

1.2 社会福利与评分函数

为更好地描述用户资源异构对训练质量的影响，将训练质量从训练效果（精度）和训练时间两方面进行分析。

训练效果与用户的数据质量有很大关系，好的训练数据往往带来更高的学习精度。为了准确评估二者间的关系，基于MNIST数据集，进行联邦学习仿真实验，分析数据对训练效果的影响。使用数据量On和非独立同分布程度两个指标描述用户数据质量。使用推土机距离EMD（Earth Mover′s Distance）[19]将非独立同分布程度定义为该用户数据分布与自然社会中该数据集总体分布之间的差异，用户n数据非独立同分布程度定义为：，其中Porj表示数据中类样本占其总样本的比例。合理假设自然社会中该数据集的分布是独立同分布的，即

将数据集按照不同的On与组合，进行蒙特卡洛实验，分析数据量和非独立同分布程度与训练精度的关系，并根据实验结果进行函数拟合。如图2所示，图中蓝色部分为拟合结果。将拟合函数作为评价用户数据质量的函数，并以数据质量作为用户对训练效果贡献的衡量标准。拟合结果为，其中为拟合参数。

将模型学习过程分解为计算过程（模型训练过程）和通信过程（模型传输过程），并进行公式化描述。将一次全局迭代中，用户n的计算时间定义为：

用户n的通信时间定义表示：

用户n的训练时间定义为：

由于用户在拍卖结束前无法确定实际带宽比例，故将在拍卖过程中的带宽分配比例记为，相应地，将训练时间记为。

结合数据质量和训练时间，将用户n对训练质量的贡献定义为，其中表示服务器对贡献评估的权重参数。

将服务器的效用函数定义为：

用户在训练期间会由于消耗资源而产生成本，将其训练成本分解为计算成本和通信成本。将一次全局迭代中，用户n的计算成本定义为：

用户n的通信成本定义为：

用户n的训练成本可表示为：

同样地，将拍卖过程中用户n的成本记为。

将用户n的效用函数定义其报酬与训练成本的差值：

拍卖中通常使用社会福利函数表示拍卖系统的性能。将本文所描述系统的社会福利函数定义为带宽分配前所有训练用户和服务器的效用函数之和：。社会福利反映了系统中所有成员的收益之和，而边际社会福利则反映了每个成员对系统的贡献[20]。

定义用户n的边际社会福利函数为：

2 用户与服务器拍卖决策

2.1 用户：投入资源决策

在收到包含评分函数、数据质量评估函数和最大时延限制的竞价请求后，用户n通过最大化评分函数来决定其投入计算与通信资源：

定理1：问题sub-P1存在唯一最优解。

证明：问题sub-P1的一阶导数为：

二阶导数为：

定理2：问题sub-P2存在唯一最优解。

证明：问题sub-P2的一阶导数为：

二阶导数为：

令：

由拟凸函数[21]定义可知，为上的拟凸函数。通过对求导可得，又因时，为减函数，当时，为增函数，故当时该问题存在唯一最优解，故当时，问题sub-P2存在唯一最优解。

定理1和定理2证明了两个子问题均有唯一最优解。问题sub-P1的最优解可通过凸优化理论中的一阶最优性条件得到。定理2已证明sub-P2问题的单调性，可在定义域上通过二分查找法求得最优解。交替迭代求解问题sub-P1和问题sub-P2的最优解，直至结果收敛。具体求解过程如算法1所示。在求解前用户n会预先判断其最大资源能否满足延迟要求，如果不能则不进行后续求解，该用户退出拍卖。

2.2 服务器：拍卖策略与带宽分配策略

收到全部用户的投标后，服务器依次进行用户选择、带宽分配及报酬确定。首先，服务器通过评分函数进行用户选择。由边际社会福利函数和评分函数的定义可知，选择评分最高的用户便是选择边际贡献最大的用户，同时也是令社会福利最大的用户。如算法2中“用户选择”所述，首先根据用户投标计算用户评分并降序排序：

之后，为保证拍卖的激励相容性，需确保拟定用户数K小于或等于评分大于0的用户数K′。若，则调整，以保证激励相容性。最后将评分最高的前K名用户选作训练者。

用户选择完成后进行带宽分配。服务器期望通过带宽分配降低时延，而系统时延取决于训练用时最长的用户，因此将带宽分配问题定义如下：

可将原K维优化问题转化为满足公式（22）约束的1维优化问题：

详细过程如算法2中“带宽分配”，通过二分查找算法解决最小化时间问题，并计算最佳带宽分配。

接下来证明所提出的拍卖方案满足个体理性、激励相容性及计算高效性。

定理3：IMRMA满足个体理性。

定理4：IMRMA满足激励相容性。

证明：通过证明IMRMA满足单调性与关键支付原则证明其满足激励相容性[22-23]。假设赢家用户的投标为，其中为资源报价：为成本报价：

（1）单调性。当其他用户不改变其策略时，用户n以更好的投标参与竞标时，其评分将满足：，则此时用户n的评分排名更靠前，故用户仍可赢得拍卖。故满足单调性。

（2）关键支付原则。当其他用户不改变其策略时，用户n以高于其真实投标所对应的报酬报告成本（即）时，有则有那么此时用户n在公式（20）中的位置将在用户之后，故用户将成为第个K赢家，而用户n将无法赢得拍卖。故满足关键支付原则。得证满足激励相容性。

定理5：IMRMA满足计算高效性。

证明：服务器的决策分三部分。用户选择的时间复杂取决于排序算法的时间复杂度；带宽分配的时间复杂度为；报酬确定的时间复杂度为。故IMRMA的时间复杂度为，满足多项式时间要求。得证满足计算高效性。

3 实验结果与分析

3.1 实验设置

设置一个与基站相连的服务器，并在其100米范围内随机生成20个移动用户，总带宽B=5MHz，噪声ZO=-114dBm。小尺度衰落为方差为1的瑞利分布，阴影衰落为标准差为8dBm的对数正态分布，路径损耗模型为为基站与用户发射端的欧几里得距离。模型的大小为3.4×106bits，单位样本大小为6272bits，处理单位比特所需CPU周期数，用户数据量介于[100，1500]个之间，所有用户数据均为非独立同分布。基于MNIST数据集进行联邦训练任务，模型为带有ReLu激活函数的三层全连接层网络。

3.2 实验结果与分析

首先，将所提出的IMRMA拍卖方案与资源无限的用户选择方案和随机选择用户方案作比较，其中资源无限为理想状态，网络条件允许所有用户参与训练；随机选择用户即按照传统的联邦平均算法随机选择K个用户。图3为在N=20，K=10设置下完成100次迭代的学习结果，可以看出，拍卖方案的训练精度与理想状态下的选择方案相当。相比于随机选择方案，拍卖方案具有更高的收敛精度与更快的收敛速度。

为分析三种选择方案在收敛速度方面的不同，以精度0.9为目标，统计了三种选择方案测试精度达到0.9所需的迭代次数（设置最大迭代次数为250次）。结果如图4所示，横坐标代表实验任务的重复次数。结果表明，相比于随机选择，IMRMA拍卖方案的收敛速度更接近理想状态下的收敛速度，受环境中用户随机性的影响更小，整体更稳定。

为分析所提出的激励方案中融入带宽分配对系统训练时间的影响，设置两个对照组进行对比实验：（1）平均带宽分配；（2）随机带宽分配。对照组在决策过程中仅带宽分配方式与IMRMA不同，完成用户选择后，平均分配方式将带宽资源平均分配给训练用户，随机分配方式将带宽资源随机分配给训练用户。进行了1000次重复实验并取三种方式下单轮训练时间的平均值，结果如图5所示，可以看出，随机分配的训练时间最长，平均分配次之，以最小化单轮训练时间为目标的分配方式训练时间最短。每个学习任务都需要多次迭代方可达到收敛，因此三种选择方案的时间差将会更大，故所提出的引入带宽分配的激励机制能够有效降低训练时间，提高学习效率。

4 结语

为解决联邦学习中激励与资源分配问题，本文设计了一种基于反向多维拍卖的激励机制IMRMA。在IMRMA中，用户通过最大化评分函数确定其资源贡献，以提高其赢得拍卖的机会；服务器通过综合考虑用户的训练数据、计算和通信能力及成本来选择最佳训练用户以提高训练质量，通过带宽分配进一步优化训练时延，通过合理的报酬确定方案保证用户的诚实报价。最后，从理论上证明了IMRMA满足必要的拍卖属性，实验结果表明，IMRMA可以有效地提高训练精度，降低训练时间。