陶梅霞，王棟，孫瑞，張乃夫

（上海交通大學(xué)電子信息與電氣工程學(xué)院，上海 200240）

1 引言

隨著5G 移動(dòng)網(wǎng)絡(luò)在全球范圍內(nèi)逐漸普及，萬(wàn)物互聯(lián)時(shí)代已到來(lái)，人工智能技術(shù)的應(yīng)用也正從云端向網(wǎng)絡(luò)邊緣延伸?；谥悄苁謾C(jī)、可穿戴設(shè)備、無(wú)人機(jī)等邊緣設(shè)備的智能應(yīng)用需求，如人臉識(shí)別、智能監(jiān)控、智能駕駛、路徑規(guī)劃等不斷涌現(xiàn)。傳統(tǒng)的機(jī)器學(xué)習(xí)算法（包括訓(xùn)練和推理）通常部署在云數(shù)據(jù)中心。為了訓(xùn)練更準(zhǔn)確的人工智能模型，邊緣設(shè)備需要將所采集的海量原始數(shù)據(jù)通過移動(dòng)網(wǎng)絡(luò)發(fā)送至云端，這會(huì)給網(wǎng)絡(luò)帶來(lái)巨大的帶寬壓力，并面臨用戶隱私泄露的風(fēng)險(xiǎn)。得益于移動(dòng)邊緣計(jì)算架構(gòu)的發(fā)展[1]，將機(jī)器學(xué)習(xí)部署在網(wǎng)絡(luò)邊緣成為可能。邊緣學(xué)習(xí)[2-4]允許終端設(shè)備將原始數(shù)據(jù)保留在本地，在邊緣服務(wù)器的協(xié)調(diào)下參與模型訓(xùn)練和推理，從而有效緩解網(wǎng)絡(luò)帶寬壓力，降低響應(yīng)時(shí)延，并提升數(shù)據(jù)隱私性。邊緣學(xué)習(xí)是通信與計(jì)算學(xué)科融合的前沿方向，被認(rèn)為是“人工智能的最后一千米”[3]。

聯(lián)邦學(xué)習(xí)是一種非常有潛力的邊緣學(xué)習(xí)框架，由Google 研究人員于2016 年提出[5]，受到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。聯(lián)邦學(xué)習(xí)允許多個(gè)分布式邊緣設(shè)備在邊緣服務(wù)器的協(xié)調(diào)下，共同訓(xùn)練一個(gè)模型，而不需要上報(bào)各自的原始數(shù)據(jù)樣本。在典型的聯(lián)邦學(xué)習(xí)過程中，每個(gè)參與用戶會(huì)先從服務(wù)器中下載當(dāng)前最新的全局模型，然后利用本地?cái)?shù)據(jù)樣本進(jìn)行局部訓(xùn)練，并將梯度信息上傳給服務(wù)器，服務(wù)器聚合各個(gè)用戶的梯度信息后更新模型參數(shù)，再將更新后的模型返回給參與用戶。

聯(lián)邦學(xué)習(xí)雖是一種特殊的分布式學(xué)習(xí)，但基于無(wú)線網(wǎng)絡(luò)邊緣，其性能受限于可用的無(wú)線網(wǎng)絡(luò)通信資源及邊緣設(shè)備自身的計(jì)算能力。由于聯(lián)邦學(xué)習(xí)是一個(gè)多輪次的迭代更新過程，如果每輪都有大量的用戶將自己的梯度信息上傳給服務(wù)器，那么整個(gè)訓(xùn)練過程會(huì)消耗大量的通信資源。目前，提高無(wú)線網(wǎng)絡(luò)中聯(lián)邦學(xué)習(xí)的通信效率已有不少研究。一類方法是降低單次模型聚合中的通信消耗，如模型量化[6]、稀疏化[7]等。另一類方法是用戶調(diào)度，即在每一輪模型更新中選擇部分用戶參與訓(xùn)練。調(diào)度的用戶數(shù)越少，通信資源消耗越小，但是模型收斂越慢。因此，用戶調(diào)度需要在資源消耗與模型收斂性能之間找到最佳的平衡。此外，邊緣設(shè)備的算力和數(shù)據(jù)分布的異構(gòu)性也為用戶調(diào)度增加了挑戰(zhàn)性。因此，用戶調(diào)度策略是聯(lián)邦學(xué)習(xí)的主要研究?jī)?nèi)容。有學(xué)者提出采用空中計(jì)算來(lái)提升聯(lián)邦學(xué)習(xí)中模型聚合的通信效率，即利用無(wú)線信道天然的疊加特性，讓所有參與學(xué)習(xí)的用戶同時(shí)傳輸模擬信號(hào)，在空中完成模型聚合運(yùn)算[8-11]，但是這種方法在實(shí)際過程中需要非常嚴(yán)格的同步。

本文旨在提出一種新的用戶調(diào)度策略，并對(duì)基于該策略的學(xué)習(xí)模型收斂性進(jìn)行分析。該策略采用時(shí)分多址接入（TDMA,time division multiple access）方式，允許每個(gè)尚未被調(diào)度的用戶在其他用戶上傳梯度信息的時(shí)間段內(nèi)繼續(xù)訓(xùn)練本地樣本數(shù)據(jù)，直到被調(diào)度，實(shí)現(xiàn)系統(tǒng)整體“邊算邊傳”的計(jì)算通信高效融合，從而提升無(wú)線網(wǎng)絡(luò)中聯(lián)邦學(xué)習(xí)的性能。

本文的主要貢獻(xiàn)如下。

1) 提出了一種充分挖掘TDMA 系統(tǒng)邊算邊傳特性的用戶調(diào)度策略。該策略考慮用戶信道增益與計(jì)算能力的異構(gòu)性，在每一輪模型更新時(shí)，以滿足所有參與用戶的訓(xùn)練樣本總量不少于給定門限為約束，通過優(yōu)化參與用戶集、用戶上傳順序及各自訓(xùn)練所用的樣本數(shù)量，最小化模型更新時(shí)延。本文證明最優(yōu)的用戶調(diào)度順序應(yīng)滿足計(jì)算能力和信道狀態(tài)相對(duì)較強(qiáng)的用戶較后上傳。通過將原問題退化為一維背包問題，以當(dāng)前用戶的已計(jì)算樣本量作為背包價(jià)值，運(yùn)用動(dòng)態(tài)規(guī)劃算法獲得最優(yōu)的調(diào)度用戶集。

2) 由于用戶間數(shù)據(jù)的異構(gòu)性，單純滿足計(jì)算樣本量無(wú)法保證非獨(dú)立同分布（Non-IID,non independent and identically distributed）場(chǎng)景下模型收斂。本文考慮用戶數(shù)據(jù)的類別分布差異，在獨(dú)立同分布（IID,independent and identically distributed）場(chǎng)景用戶調(diào)度策略的基礎(chǔ)上，引入約束樣本均衡度的數(shù)學(xué)模型，讓邊緣服務(wù)器自動(dòng)決策用戶的計(jì)算樣本類別和各類數(shù)量，提高調(diào)度用戶訓(xùn)練樣本的均衡性，在降低系統(tǒng)時(shí)延的基礎(chǔ)上提高模型訓(xùn)練的準(zhǔn)確率。

3) 分析了模型的收斂性能，并基于所提出的用戶調(diào)度策略，分析收斂性能與系統(tǒng)總時(shí)延之間的均衡關(guān)系，探討了在給定收斂性能目標(biāo)下能夠最小化系統(tǒng)總時(shí)延的批大小選擇。

4) 仿真結(jié)果表明，本文算法具有良好的降低通信系統(tǒng)時(shí)延的性能。與基準(zhǔn)調(diào)度策略的比較，驗(yàn)證了本文算法的有效性。

2 現(xiàn)有相關(guān)工作

有很多工作對(duì)聯(lián)邦學(xué)習(xí)的用戶調(diào)度策略進(jìn)行了研究。其中，文獻(xiàn)[12-15]主要關(guān)注在給定通信資源與計(jì)算資源的情況下用戶的調(diào)度策略。具體來(lái)說(shuō)，文獻(xiàn)[12]以更新樣本的年齡（AoU,age of update）作為性能指標(biāo)，提出了一種用戶調(diào)度策略，通過聯(lián)合考慮用戶的AoU 與信道狀態(tài)，提升聯(lián)邦學(xué)習(xí)的運(yùn)行效率。文獻(xiàn)[13]通過貪心算法選擇時(shí)延最小的用戶，最小化單輪傳輸?shù)目倳r(shí)延。文獻(xiàn)[14]分析了用戶調(diào)度策略與小區(qū)間干擾對(duì)模型收斂率的影響，并比較了隨機(jī)調(diào)度、輪詢和比例公平調(diào)度策略的收斂性。文獻(xiàn)[15]提出了一種用戶調(diào)度策略，聯(lián)合考慮用戶信道特性與用戶本地模型的“重要性”，與只考慮單一用戶特性的調(diào)度策略相比，提升了模型的收斂率與準(zhǔn)確度。文獻(xiàn)[16-20]研究了用戶調(diào)度策略與無(wú)線資源分配的聯(lián)合優(yōu)化。具體地，文獻(xiàn)[16]提出了一種基于非正交多址接入的用戶調(diào)度策略，通過聯(lián)合優(yōu)化用戶調(diào)度和功率分配最大化加權(quán)數(shù)據(jù)速率和，以提高學(xué)習(xí)效率。文獻(xiàn)[17]提出了一種啟發(fā)式的調(diào)度和資源分配策略，聯(lián)合考慮信道狀況和本地更新模型的重要性，并分析了該策略的模型收斂性。文獻(xiàn)[18]聯(lián)合優(yōu)化了用戶調(diào)度策略與帶寬分配，最小化系統(tǒng)能量消耗。文獻(xiàn)[19]聯(lián)合優(yōu)化了上行鏈路資源分配和調(diào)度用戶數(shù)目，最大化聯(lián)邦學(xué)習(xí)的漸近收斂性能。以上研究均優(yōu)化單輪的用戶調(diào)度策略，沒有給出收斂率與總資源消耗（如時(shí)間）的關(guān)系，且無(wú)法從理論上確定全局最優(yōu)用戶調(diào)度策略。文獻(xiàn)[20]提出了一種聯(lián)合用戶調(diào)度和資源分配策略，通過分析模型收斂率與調(diào)度用戶數(shù)量和迭代次數(shù)的關(guān)系，找到最優(yōu)的用戶調(diào)度數(shù)量，最大化模型收斂速度。

一般來(lái)說(shuō)，聯(lián)邦學(xué)習(xí)傳輸過程通常采用正交多址接入的方式，如OFDMA（orthogonal frequency division multiple access）和TDMA 與邊緣服務(wù)器通信，文獻(xiàn)[18-20]均采用OFDMA 的傳輸模型。OFDMA 被長(zhǎng)期演進(jìn)（LTE,long term evolution）系統(tǒng)采用，允許所有參與調(diào)度的用戶在完成計(jì)算任務(wù)的前提下，在不同的頻譜資源塊上同時(shí)傳輸更新的模型。而TDMA 傳輸被Wi-Fi 系統(tǒng)所采用，在同一時(shí)間只允許單個(gè)用戶上傳任務(wù)，但可以占用整個(gè)帶寬資源。與基于OFDMA 的聯(lián)邦學(xué)習(xí)相比，基于TDMA的聯(lián)邦學(xué)習(xí)在一個(gè)用戶上行傳輸時(shí)允許其他用戶利用此時(shí)間繼續(xù)任務(wù)計(jì)算。因此，基于TDMA 的學(xué)習(xí)在消耗同等傳輸帶寬與傳輸時(shí)間的情況下，不需要額外消耗計(jì)算時(shí)間，可以降低系統(tǒng)的總時(shí)延，并且模型更新的計(jì)算量越大，時(shí)延降低越顯著。

然而，現(xiàn)有工作都沒有充分挖掘TDMA 的這一優(yōu)勢(shì)。文獻(xiàn)[13]雖提出了一種基于TDMA 方式的用戶調(diào)度策略，但是沒有考慮所選用戶的計(jì)算任務(wù)對(duì)模型的貢獻(xiàn)度。另一方面，文獻(xiàn)[13]假設(shè)用戶用于模型更新的樣本量固定，本地更新模型所需計(jì)算資源固定。然而，在異構(gòu)網(wǎng)絡(luò)中，計(jì)算能力強(qiáng)的設(shè)備，在同等時(shí)間內(nèi)可以計(jì)算更多的樣本，從而加快模型的收斂。因此，上述工作的假設(shè)無(wú)法充分利用設(shè)備計(jì)算資源。

與現(xiàn)有工作對(duì)比，本文提出的基于TDMA 的用戶調(diào)度策略不僅充分利用了系統(tǒng)邊算邊傳的優(yōu)勢(shì)，還考慮了設(shè)備的計(jì)算能力和信道增益的異構(gòu)性，分別在IID 數(shù)據(jù)集與Non-IID 數(shù)據(jù)集下，優(yōu)化了用戶調(diào)度集合和用戶訓(xùn)練的數(shù)據(jù)量，最小化單輪模型更新時(shí)延。本文還進(jìn)一步基于模型收斂率分析，探討了批大小與訓(xùn)練總時(shí)延的關(guān)系。

3 系統(tǒng)模型

3.1 聯(lián)邦學(xué)習(xí)模型

考慮如圖1 所示的聯(lián)邦學(xué)習(xí)系統(tǒng)，M個(gè)邊緣設(shè)備（用戶）在一個(gè)邊緣服務(wù)器（無(wú)線接入點(diǎn)）的協(xié)調(diào)下共同訓(xùn)練一個(gè)學(xué)習(xí)模型。邊緣設(shè)備與邊緣服務(wù)器之間通過無(wú)線信道進(jìn)行上下行通信。主要系統(tǒng)參數(shù)如表1 所示。

表1 主要系統(tǒng)參數(shù)

圖1 聯(lián)邦學(xué)習(xí)系統(tǒng)

由于通信和計(jì)算資源受限，在每一輪的模型更新過程中，邊緣服務(wù)器只選擇部分邊緣設(shè)備參與梯度聚合。第t∈{1,2,…} 輪的學(xué)習(xí)過程包括以下步驟。

1) 用戶選擇。邊緣服務(wù)器根據(jù)一定的策略進(jìn)行用戶選擇，記Mt?M 為第t輪被調(diào)度的用戶集合。本文提出的用戶調(diào)度策略將在第4 節(jié)詳細(xì)介紹。

2) 全局模型廣播。邊緣服務(wù)器將最新的全局模型wt通過無(wú)線信道廣播給全體用戶。

3) 本地訓(xùn)練。被調(diào)度的用戶m∈Mt接收到全局模型wt后，基于本地?cái)?shù)據(jù)集，采用隨機(jī)梯度下降（SGD,stochastic gradient descent）法執(zhí)行本地模型訓(xùn)練。本文參考有監(jiān)督的機(jī)器學(xué)習(xí)任務(wù)，定義損失函數(shù)f(wt,x)表示在模型wt下的對(duì)訓(xùn)練樣本x的預(yù)測(cè)誤差。如果值較大，則預(yù)測(cè)誤差較大；反之則較小。定義為第t輪用戶m本地訓(xùn)練用到的數(shù)據(jù)集，記該數(shù)據(jù)集大小為，則損失函數(shù)定義為

用戶m由此可獲得本地梯度值為

其中，?是梯度操作。

4) 梯度聚合。所有被調(diào)度的用戶將本地梯度通過無(wú)線信道上傳至邊緣服務(wù)器，邊緣服務(wù)器收到后，執(zhí)行聚合操作，獲得全局梯度為

在這一過程中，用戶可以對(duì)梯度信息進(jìn)行量化和壓縮，來(lái)減少通信資源的消耗和系統(tǒng)的時(shí)延。

5) 全局模型更新。邊緣服務(wù)器根據(jù)全局梯度信息更新全局模型，更新過程為

其中，η≥0 表示學(xué)習(xí)率。

3.2 通信與計(jì)算模型

聯(lián)邦學(xué)習(xí)過程所消耗的時(shí)延包括通信時(shí)延和計(jì)算時(shí)延兩部分。通信時(shí)延通常與用戶的信道狀態(tài)、通信帶寬、傳輸功率以及梯度量化比特有關(guān)。計(jì)算時(shí)延的主要影響因素通常有設(shè)備的計(jì)算能力、數(shù)據(jù)集的大小、單個(gè)數(shù)據(jù)樣本的特性和訓(xùn)練算法的選擇。下面分別介紹2 種時(shí)延的建模方法。

由于下行鏈路的通信速率通常遠(yuǎn)大于上行鏈路的通信速率，并且邊緣服務(wù)器可以采用廣播的方式與用戶進(jìn)行下行通信，因此在實(shí)際系統(tǒng)中，聯(lián)邦學(xué)習(xí)的通信時(shí)延由上行鏈路的通信時(shí)延主導(dǎo)。因此，本文不考慮下行鏈路通信引起的時(shí)延。本文采用基于TDMA 的上行傳輸，同一時(shí)間段只有一個(gè)用戶在通信，并且可以占用整個(gè)系統(tǒng)帶寬?；凇斑吽氵厒鳌钡奶攸c(diǎn)，被調(diào)度用戶的梯度上傳順序至關(guān)重要。在每一輪模型更新中，將被調(diào)度的用戶集Mt按照用戶上傳順序排列，重新定義為有序集，其中，πt(m)表示在第t輪里被選擇第m個(gè)上傳梯度的用戶索引，是在該輪被調(diào)度的用戶總數(shù)（一般來(lái)說(shuō)，每輪調(diào)度用戶的總數(shù)可能不同，此處為簡(jiǎn)化表述，省去了t）。用戶本地計(jì)算和梯度傳輸?shù)臅r(shí)隙關(guān)系如圖2 所示，其中，用戶π(m)一直處于本地計(jì)算狀態(tài)，直至前一用戶π(m? 1)上行傳輸結(jié)束才停止本地計(jì)算，并開始上傳計(jì)算所得的梯度。在圖2 中，cπ(m)、Tπ(m)和τπ(m)分別表示用戶π(m)的本地訓(xùn)練時(shí)間、梯度上傳時(shí)間點(diǎn)和梯度上傳所需通信時(shí)間。

圖2 用戶本地計(jì)算和梯度傳輸?shù)臅r(shí)隙關(guān)系

由于每個(gè)本地梯度包含的元素個(gè)數(shù)相同，為方便起見，采用Q個(gè)比特來(lái)量化每個(gè)本地梯度?？紤]用戶m被調(diào)度，則第t輪用戶m梯度上傳時(shí)延（單位為s）可以表示為

其中，W為傳輸帶寬，為用戶m在第t輪的信噪比。

定義pm為用戶m的計(jì)算能力，若考慮用戶m的計(jì)算樣本數(shù)量為dm，則用戶m計(jì)算用時(shí)（單位為s）可以表示為

如果有計(jì)算時(shí)間，則用戶m可計(jì)算的樣本數(shù)量為

從圖2 可以看到，在每一輪全局模型更新里，第一個(gè)被調(diào)度的用戶π(1) 擁有最短的本地計(jì)算時(shí)延預(yù)算，而最后被調(diào)度的用戶π(k)的本地計(jì)算時(shí)延預(yù)算最長(zhǎng)?；谏鲜鐾ㄐ排c計(jì)算模型，第t輪全局模型更新所需總時(shí)延可以用最后一個(gè)被調(diào)度的用戶的梯度上傳時(shí)間點(diǎn)和通信時(shí)間來(lái)表示，記為。

4 用戶調(diào)度策略

4.1 IID 數(shù)據(jù)分布用戶調(diào)度

定義B為聯(lián)邦學(xué)習(xí)單輪參與全局梯度更新的所有用戶訓(xùn)練的數(shù)據(jù)樣本量。在已知B的情況下，只需要滿足每輪調(diào)度用戶的數(shù)據(jù)樣本總量大于或等于B即進(jìn)入下一輪迭代訓(xùn)練過程，那么必然存在一個(gè)基于TDMA 通信方式的用戶調(diào)度策略來(lái)最小化總的模型更新時(shí)延。

根據(jù)3.2 節(jié)的時(shí)延模型，問題模型可以描述為

其中，Tπ(m)表示用戶π(m)的上傳時(shí)間點(diǎn)。結(jié)合圖2所示的時(shí)隙圖，上述約束條件式(9a)表示用戶π(m)的上傳時(shí)間點(diǎn)至少要等到它的前一個(gè)上傳用戶π(m? 1)上傳完畢，式(9b)表示用戶π(m)的計(jì)算時(shí)間不能超過其上傳時(shí)間點(diǎn)，式(9c)表示本輪調(diào)度用戶集的全部計(jì)算樣本量不能少于門限值B。

顯然，上述優(yōu)化問題屬于NP 完全問題，難以獲得最優(yōu)解的閉式表達(dá)式。通過引入以下2 個(gè)引理，可以將原問題的求解退化為一維背包問題，進(jìn)而獲得該問題的最優(yōu)數(shù)值解。定義λm=pm/τm為用戶m的調(diào)度重要度。

引理1任意2 個(gè)相鄰的調(diào)度用戶滿足上行傳輸時(shí)間點(diǎn)無(wú)間隙，即滿足cπ(m)?cπ(m?1)=τπ(m?1)。

引理2調(diào)度用戶有序集中的最優(yōu)的用戶調(diào)度順序必須滿足

引理1 和引理2 的證明過程分別如附錄1 和附錄2 所示。

基于引理1 和引理2，原問題的求解可以退化為一維背包問題的求解。區(qū)別于傳統(tǒng)的背包問題，該問題下物品的價(jià)值（即每個(gè)用戶能計(jì)算的樣本）不是常量。該問題的求解需要上述引理與動(dòng)態(tài)規(guī)劃算法的結(jié)合，通過對(duì)背包空間的搜索和物品價(jià)值的度量，尋找在給定的背包空間（單輪迭代總時(shí)延）下所能容納的最大物品價(jià)值（單輪迭代所能計(jì)算的樣本總量），再通過二分法搜集解空間，尋求問題的最優(yōu)解。

將單輪迭代總時(shí)延Stotal定義為總的背包空間大??；U[i][j]定義為背包空間大小為j時(shí)，放入物品i后的價(jià)值大小。在本問題中，物品i的價(jià)值V[i]定義為用戶i的計(jì)算樣本量，即

算法1基于背包問題的用戶調(diào)度策略

算法2基于二分法尋找最優(yōu)時(shí)間

通過算法1 可以解出在給定單輪通信系統(tǒng)時(shí)延為Stotal時(shí)的最優(yōu)用戶調(diào)度順序集和所能計(jì)算的本地?cái)?shù)據(jù)樣本量。通過算法2 對(duì)Stotal的搜索可以找到滿足單輪本地?cái)?shù)據(jù)樣本量大于或等于B所需的精度在任意ε以內(nèi)的最小單輪通信系統(tǒng)時(shí)延。

計(jì)算復(fù)雜度分析。在該算法中計(jì)算和排序的復(fù)雜度均為 O(Mlog(M))，由一維背包問題的復(fù)雜度可知其復(fù)雜度為O(MStotal/s)，二分法尋找最優(yōu)解的復(fù)雜度為，則總的計(jì)算復(fù)雜度為，其中N為總的通信輪次。

4.2 Non-IID 數(shù)據(jù)分布用戶調(diào)度

4.1 節(jié)討論了在IID 場(chǎng)景下最優(yōu)的用戶調(diào)度策略。聯(lián)邦學(xué)習(xí)實(shí)際場(chǎng)景中，由于不同設(shè)備所處的環(huán)境不同，用戶行為習(xí)慣也不同，因此用戶本地的數(shù)據(jù)樣本會(huì)呈現(xiàn)Non-IID 特性。如果仍然以最快達(dá)到邊緣服務(wù)器單輪訓(xùn)練所需的數(shù)據(jù)樣本數(shù)量為目標(biāo)，那么全局模型更新方向必然偏向重要度較大的用戶，導(dǎo)致部分用戶在整個(gè)訓(xùn)練過程中被調(diào)度的概率非常小。以分類問題為例，要保證模型收斂，必須使全部調(diào)度用戶集已訓(xùn)練的樣本呈現(xiàn)均衡的特性。因此在Non-IID 場(chǎng)景下，在最小化單輪系統(tǒng)時(shí)延的同時(shí)，需要考慮用戶之間數(shù)據(jù)樣本不平衡的問題。為了解決該問題，本文引入數(shù)據(jù)分布的特性，令邊緣服務(wù)器知曉每個(gè)參與聯(lián)邦學(xué)習(xí)的用戶的每一類樣本數(shù)量。假設(shè)全體數(shù)據(jù)集共有Y類樣本，分別定義和Bj為用戶m所擁有的第j類樣本的數(shù)量、邊緣服務(wù)器需要用戶m所計(jì)算的第j類樣本的數(shù)量以及邊緣服務(wù)器在每一輪對(duì)第j類樣本的需求量。

基于上述關(guān)于數(shù)據(jù)平衡問題的討論，Non-IID場(chǎng)景下的用戶調(diào)度策略不僅要考慮用戶的重要度λm，也要考慮本輪參與調(diào)度用戶的總的訓(xùn)練樣本中每個(gè)類別的樣本是否滿足給定的數(shù)量要求。因此，問題模型可以描述為

其中，π(k)表示優(yōu)化調(diào)度集中的最后一個(gè)上傳用戶；式(12c)表示邊緣服務(wù)器要求用戶π(m)所計(jì)算的第j類樣本數(shù)量不能超過它自身所擁有的第j類樣本數(shù)量；式(12d)表示邊緣服務(wù)器要求用戶π(m)計(jì)算的所有類別的樣本數(shù)量不能大于其單輪最大的樣本計(jì)算數(shù)量；式(12e)表示邊緣服務(wù)器要求本輪所有參與調(diào)度的用戶計(jì)算的第j類樣本數(shù)量總和需滿足預(yù)先設(shè)定最低要求Bj，同時(shí)不能超過B j+μ，否則不同類別的不均衡度會(huì)增加。

由于在建立系統(tǒng)模型時(shí)引入了用戶的樣本類別分布參量，此問題若繼續(xù)使用背包問題求解則需要建立背包空間與全局計(jì)算樣本量以及每類樣本的數(shù)據(jù)分布的關(guān)系，這是十分困難的。根據(jù)Weierstrass 定理，存在一個(gè)標(biāo)量非空和有界，因此系統(tǒng)模型一定存在最優(yōu)解。本文提出2 種啟發(fā)式的調(diào)度方案，在聯(lián)邦學(xué)習(xí)Non-IID 場(chǎng)景下兼顧數(shù)據(jù)均衡性和系統(tǒng)時(shí)延。

4.2.1 數(shù)據(jù)平衡優(yōu)先的用戶調(diào)度

由于原問題不能直接求解，一個(gè)啟發(fā)式的方案為首先按照引理2 定義的用戶重要度規(guī)則確定調(diào)度用戶有序集；然后，邊緣服務(wù)器根據(jù)計(jì)算出以使更新時(shí)延最小化。

由于邊緣服務(wù)器需要每個(gè)本地用戶計(jì)算的第j類樣本數(shù)量大于或等于jB，因此在調(diào)度用戶時(shí)必須滿足調(diào)度用戶集中單個(gè)類別的樣本總量大于或等于Bj，算法3 需要根據(jù)這一規(guī)則選擇合理的調(diào)度用戶集，基于此提出基于數(shù)據(jù)平衡優(yōu)先的調(diào)度策略。該策略的思想是，首先按照重要度從大到小對(duì)全體用戶進(jìn)行傳輸排序，然后邊緣服務(wù)器按照此順序遍歷每個(gè)用戶的數(shù)據(jù)樣本使其滿足式(12)的約束條件，在每個(gè)可能的用戶組合下，通過簡(jiǎn)化問題式(12)為約束條件式(12c)～式(12e)。顯然，上述3 個(gè)約束條件都為凸函數(shù)，因此原問題轉(zhuǎn)換為凸優(yōu)化問題，通過常用的求解凸優(yōu)化的工具包（如CVX）可解出最優(yōu)的調(diào)度集合和，其中π(m)∈。

算法3基于數(shù)據(jù)平衡優(yōu)先的用戶調(diào)度策略

算法3對(duì)處理用戶之間數(shù)據(jù)不平衡程度較高的場(chǎng)景有很好的效果。因?yàn)樵谧鲇脩暨x擇時(shí)不僅考慮了用戶的計(jì)算能力和通信狀態(tài)，同時(shí)由于邊緣服務(wù)器根據(jù)不同類別的樣本數(shù)量參與用戶的選擇，使單輪每一種類別的樣本數(shù)量都能滿足要求。但是為了平衡某些稀有類樣本到計(jì)算能力或者信道狀態(tài)不好的用戶設(shè)備上，系統(tǒng)會(huì)等待直至它完成計(jì)算該類別所需的樣本數(shù)量，由此會(huì)造成單輪系統(tǒng)時(shí)延的增加。

4.2.2 更新時(shí)延優(yōu)先的用戶調(diào)度

為了解決算法3 遺留的某些稀有類樣本恰好處于計(jì)算能力和信道狀態(tài)都不好的用戶上所帶來(lái)的系統(tǒng)時(shí)延較高的問題，本文提出了一種不改變單輪通信系統(tǒng)最小時(shí)延的情況下提升數(shù)據(jù)平衡度的用戶調(diào)度策略。問題描述如下。

其中，優(yōu)化目標(biāo)式(13)是由當(dāng)前所有參與調(diào)度用戶所能貢獻(xiàn)的每一類樣本實(shí)際訓(xùn)練數(shù)與所期望的每一類樣本訓(xùn)練數(shù)之間的均方差。均方差目標(biāo)函數(shù)由于其可導(dǎo)性更易于目標(biāo)函數(shù)的求解是一種常用的逼近目標(biāo)值的數(shù)學(xué)建模方法，通過最小化該均方差，可以有效保證數(shù)據(jù)的平衡性。當(dāng)全體用戶的數(shù)據(jù)樣本不均衡度較低，每輪調(diào)度需要的調(diào)度用戶數(shù)目滿足一定數(shù)量時(shí)，選擇的調(diào)度用戶便有很大概率包含全體全部類別樣本，因此在這一場(chǎng)景下本文更關(guān)心系統(tǒng)時(shí)延，只要使參與調(diào)度的用戶計(jì)算樣本均衡，就能獲得較好的收斂特性。由于問題式(13)的求解需要已知當(dāng)前參與的調(diào)度用戶以及調(diào)度順序，通過將式(9)的結(jié)果用于該問題的求解，可以在最小化單輪時(shí)延的基礎(chǔ)上，同時(shí)做到聯(lián)邦學(xué)習(xí)下的用戶類別均衡，加快Non-IID 場(chǎng)景下的模型收斂速率。

同樣地，問題式(13)滿足Weierstrass 定理，在算法1 和算法2 后通過簡(jiǎn)單的解優(yōu)化工具便能找到滿足約束條件下問題式(13)的最優(yōu)解。

通過合理采用數(shù)據(jù)平衡優(yōu)先的用戶調(diào)度策略和更新時(shí)延優(yōu)先的用戶調(diào)度策略，可以分別在數(shù)據(jù)不平衡度高和不平衡度低時(shí)，兼顧系統(tǒng)時(shí)延和模型收斂問題。

4.2.3 計(jì)算復(fù)雜度分析

在該算法中排序的復(fù)雜度為O(M)，通過資料查閱可知，本文問題解優(yōu)化工具的計(jì)算復(fù)雜度為，由于需要遍歷所有用戶，因此總的復(fù)雜度為，其中N為總的通信輪次。

5 收斂性分析與優(yōu)化

第4 節(jié)討論了單輪聚合時(shí)滿足給定計(jì)算樣本數(shù)量（即批大小）B的前提下，使單次聚合的系統(tǒng)時(shí)延最小化的用戶調(diào)度問題。本節(jié)首先分析單輪總批大小對(duì)模型收斂性能的影響；然后，分析所提出的用戶調(diào)度策略下單輪系統(tǒng)時(shí)延與批大小的關(guān)系，從而進(jìn)一步探究系統(tǒng)總時(shí)延與收斂性能之間的均衡關(guān)系；最后，探討在給定收斂性能目標(biāo)下能夠最小化系統(tǒng)總時(shí)延的最優(yōu)批大小的選擇。

5.1 學(xué)習(xí)算法收斂性

由于每輪全局模型聚合時(shí)用戶的本地迭代次數(shù)為1，收斂性分析可以等價(jià)為分布式小批量隨機(jī)梯度下降算法的收斂性分析。令全體樣本空間為D，那么訓(xùn)練對(duì)于該空間中樣本x的損失函數(shù)為f(w,x)，其中w是模型參數(shù)向量，使用大小為B的數(shù)據(jù)進(jìn)行一輪更新的全局損失函數(shù)為

其中，B 為批大小為B的數(shù)據(jù)組成的集合。

本文采用后悔評(píng)估函數(shù)來(lái)刻畫學(xué)習(xí)算法的收斂性能。后悔值表示損失函數(shù)與最優(yōu)損失的累計(jì)誤差，那么N輪聚合結(jié)果為

其中，w?是最優(yōu)解，即模型的最終可達(dá)目標(biāo)，。

假設(shè)損失函數(shù)滿足如下條件。

1) 凸性。f(?)是一個(gè)凸函數(shù)。

2) 平滑性。對(duì)于任意樣本x～D，f(?,x) 滿足L?平滑條件，即對(duì)任意的模型參數(shù)向量w和w'，都存在。

3) 梯度分散邊界。對(duì)于任意的模型參數(shù)向量w，其梯度分散情況存在一個(gè)邊界值σ，即。

4) 模型參數(shù)邊界。對(duì)于任意輪次t的全局模型參數(shù)向量wt，存在邊界值使。

基于以上假設(shè)，根據(jù)文獻(xiàn)[21]的分析結(jié)果，可得到后悔值上界，記為收斂邊界函數(shù)R(N,B) 。

5.2 模型收斂性與系統(tǒng)總時(shí)延的關(guān)系

本文模型訓(xùn)練的最終目標(biāo)是在保證學(xué)習(xí)的收斂性能的情況下，最小化全局系統(tǒng)時(shí)延。下面，首先根據(jù)前文中IID 數(shù)據(jù)分布下的單輪次調(diào)度策略推導(dǎo)單輪次時(shí)延，即一輪本地訓(xùn)練和聚合所需的時(shí)間。

記T為一輪總的系統(tǒng)時(shí)延。根據(jù)前文提出的調(diào)度策略有

定義pmin為參與調(diào)度用戶中計(jì)算性能最差用戶的計(jì)算能力，則

定義τmax為上傳用戶集中信道狀態(tài)最差的用戶的上傳時(shí)間，則

進(jìn)一步地，因?yàn)棣觤ax為信道狀態(tài)最差的用戶的上傳時(shí)間，按照本文的調(diào)度規(guī)則，即

代入式(19)，則

則T與B的關(guān)系為

對(duì)上述不等式取等得到最終的T(B)表達(dá)式為

最終系統(tǒng)的總時(shí)延為

從式(27)可以看出，系統(tǒng)總時(shí)延隨著總批大小B和全局聚合次數(shù)N的增大而增大。結(jié)合前文所得收斂邊界結(jié)果，即式(16)，可以看出增加聚合次數(shù)和總批大小會(huì)對(duì)收斂帶來(lái)增益，但是同樣增加了系統(tǒng)總時(shí)延，并且性能增益與系統(tǒng)時(shí)延處于同一量級(jí)。因此，最終肯定存在最優(yōu)的調(diào)度方針使?jié)M足性能需求的前提下最小化總時(shí)延。接下來(lái)，進(jìn)一步分析收斂性能與系統(tǒng)總時(shí)延之間的關(guān)系，設(shè)Gmax為所需要達(dá)到的收斂邊界，那么必然要求收斂邊界滿足

首先，探討聚合次數(shù)為定值的情況下，收斂性能與系統(tǒng)總時(shí)延的均衡關(guān)系。將總批大小寫成關(guān)于聚合次數(shù)的表達(dá)式，即

在給定聚合輪次下，總系統(tǒng)時(shí)延隨著總批大小的增加而增加，因此B取下界，此時(shí)總批大小選擇是一個(gè)關(guān)于系統(tǒng)可達(dá)性能的表達(dá)式，將結(jié)果代入總時(shí)延表達(dá)式可得

歸一化系統(tǒng)總時(shí)延與歸一化收斂性能二者之間的關(guān)系如圖3 所示。從式(30)中可以看出，當(dāng)給定聚合次數(shù)N時(shí)，系統(tǒng)總時(shí)延與收斂性能近似成反比關(guān)系，符合圖3 中顯示的變化趨勢(shì)。結(jié)合式(29)繪制圖3 中選取點(diǎn)的批大小B的取值，可以看出，隨著批大小的增大，收斂邊界值與總批大小的次冪以一定比例值縮小，系統(tǒng)總時(shí)延以該比例值近似放大。此外，由于影響因子的存在，收斂邊界存在最小值，即無(wú)論如何訓(xùn)練，收斂總是不能變?yōu)榱?，而只能趨近于一個(gè)值。

圖3 收斂邊界與系統(tǒng)總時(shí)延的均衡關(guān)系（固定聚合次數(shù)）

接著，進(jìn)一步探討最優(yōu)總批大小選擇的問題。將聚合次數(shù)寫成關(guān)于總批大小的表達(dá)式，則

在給定總批大小下，總系統(tǒng)時(shí)延隨著聚合輪次的增加而增加，因此N取下界，將結(jié)果代入總時(shí)延表達(dá)式(30)可得

在給定可達(dá)目標(biāo)的情況下，式(32)中存在最小值，即批大小存在最優(yōu)選擇。由于式(32)存在很多的假設(shè)和縮放，因此無(wú)法得出實(shí)際數(shù)值解，只能得到變化趨勢(shì)，最優(yōu)批大小的選擇會(huì)通過仿真得到。

6 實(shí)驗(yàn)結(jié)果

本文基于開源框架PyTorch，利用真實(shí)數(shù)據(jù)集來(lái)驗(yàn)證所提用戶調(diào)度策略相較于其他算法的有效性，并檢驗(yàn)收斂性分析的準(zhǔn)確性。本文實(shí)驗(yàn)使用了以下2 個(gè)常用的數(shù)據(jù)集。

1) MNIST。MNIST 手寫數(shù)字?jǐn)?shù)據(jù)集是機(jī)器學(xué)習(xí)領(lǐng)域非常經(jīng)典的數(shù)據(jù)集，包含手寫數(shù)字0～9 共10種類型的圖片。該數(shù)據(jù)集包含60 000 個(gè)用于訓(xùn)練的訓(xùn)練樣本和10 000 個(gè)用于測(cè)試的測(cè)試樣本，每個(gè)圖片都是28 像素×28 像素、值為0～1 的固定大小。

2) CIFAR-10。CIFAR-10 是一個(gè)用于識(shí)別通用對(duì)象的小型數(shù)據(jù)集，由10 類共60 000 個(gè)32 像素×32 像素的彩色圖像組成。每類有6 000 個(gè)圖像。這些圖像分為50 000 個(gè)訓(xùn)練圖像和10 000 個(gè)測(cè)試圖像，包含飛機(jī)、汽車、鳥、貓、鹿、狗、青蛙、馬、船、卡車。

6.1 IID 場(chǎng)景

本節(jié)選用3 種常用的用戶調(diào)度策略，即隨機(jī)調(diào)度、輪詢調(diào)度和比例公平調(diào)度，以文獻(xiàn)[13,18]提出的2 種不同通信接入方式下的用戶調(diào)度策略作為基準(zhǔn)，與本文所提用戶調(diào)度策略進(jìn)行性能對(duì)比。

1) 隨機(jī)調(diào)度。在每一輪迭代中，邊緣服務(wù)器隨機(jī)選擇部分用戶作為當(dāng)前輪次調(diào)度用戶集，當(dāng)滿足全局聚合所需的批大小時(shí)，用戶停止上傳，邊緣服務(wù)器通過聚合將更新的模型廣播給所有用戶，并繼續(xù)按照此規(guī)則進(jìn)行下一輪迭代。

2) 輪詢調(diào)度。在每輪迭代中，邊緣服務(wù)器輪流選擇用戶集中的用戶上傳，當(dāng)滿足全局聚合所需的批大小時(shí)，用戶停止上傳，邊緣服務(wù)器通過聚合將更新的模型廣播給所有用戶，并繼續(xù)按照此規(guī)則進(jìn)行下一輪迭代。該算法的優(yōu)點(diǎn)是簡(jiǎn)單，不需要記錄當(dāng)前的連接狀態(tài)，是一種無(wú)狀態(tài)調(diào)度。

3) 比例公平調(diào)度。該算法保證用戶間的長(zhǎng)期公平性，能兼顧信道狀態(tài)較好的用戶與信道狀態(tài)較差的用戶，在選擇用戶時(shí)考慮瞬時(shí)速率和長(zhǎng)期平均速率的比值，按照比值從大到小的順序調(diào)度用戶。注意到，該算法僅考慮用戶在傳輸速率上的公平性，并不考慮用戶在計(jì)算能力上的公平性。

4) 文獻(xiàn)[13]策略。該文獻(xiàn)采用TDMA 的接入方式，通過每輪選擇總時(shí)延τm+Tm較小的若干用戶進(jìn)行上傳，在仿真中本文選擇總時(shí)延小的用戶逐一上傳，直到滿足所需計(jì)算的樣本量B為止。

5) 文獻(xiàn)[18]策略。該文獻(xiàn)采用OFDMA 的接入方式，通過約束用戶m的上傳時(shí)間小于給定的閾值，設(shè)計(jì)用戶選擇方案與帶寬分配方案以最小化單輪的全局能量消耗。用戶選擇方案為

其中，βm表示用戶m是否參與當(dāng)前輪調(diào)度，βm=0表示不參與，βm=1 表示參與；μm表示帶寬分配比率；pm表示用戶m單位帶寬的傳輸功率，單位為watt/Hz。

6.1.1 仿真設(shè)置

本仿真實(shí)驗(yàn)使用 64 bit Intel(R) Core(TM)i5-4460@3.20 GHz 處理器，運(yùn)行內(nèi)存大小為12 GHz。用戶數(shù)目M=100，傳輸帶寬為500 kHz，發(fā)送信噪比=5 dB，pm=2 ×10?6watt/Hz，不考慮大尺度衰落對(duì)用戶的上行傳輸帶來(lái)的影響，每個(gè)用戶的上行信道隨時(shí)間變化服從均值為1 的瑞利分布。默認(rèn)情況下，用戶的計(jì)算能力服從(100,900)的均勻分布，且不隨時(shí)間變化。

首先，以IID的方式隨機(jī)將MNIST和CIFAR-10數(shù)據(jù)集分配給所有用戶，其中，MNIST 下每個(gè)用戶600 個(gè)訓(xùn)練樣本，CIFAR-10 下每個(gè)用戶500 個(gè)訓(xùn)練樣本。

6.1.2 仿真結(jié)果

基于5.2 節(jié)關(guān)于最優(yōu)批大小的探討，本節(jié)通過將理論分析與實(shí)驗(yàn)仿真相結(jié)合，驗(yàn)證本文基于通信與計(jì)算融合的用戶調(diào)度策略下，能達(dá)到目標(biāo)性能所需的總批大小與系統(tǒng)總時(shí)延的關(guān)系。以MNIST 數(shù)據(jù)集為例，主要測(cè)試了2 個(gè)性能目標(biāo)，即測(cè)試精度為80%和90%，以及理論趨勢(shì)的結(jié)果。

圖4 顯示了理論趨勢(shì)與不同測(cè)試精度的批大小與總時(shí)延的關(guān)系。隨著精度的增加，系統(tǒng)總時(shí)延不斷增加。對(duì)于同一精度目標(biāo)，雖然總時(shí)延隨著批大小的增加存在波動(dòng)性，但是總體變化符合理論的結(jié)果，呈現(xiàn)先減小后增加的趨勢(shì)。結(jié)合理論分析的結(jié)果，初始的總時(shí)延急速減小是由于批過小，從而導(dǎo)致模型梯度分散值很大，收斂速度很慢甚至對(duì)于過高的精度而言難以進(jìn)行收斂。由于批大小的增加，需求的用戶調(diào)度數(shù)目增加，而這種增加帶來(lái)的通信時(shí)延的增加逐漸超過系統(tǒng)性能的提升，致使系統(tǒng)總時(shí)延隨著批大小先減后增，從而存在最優(yōu)的批大小選擇。

圖4 批大小與總時(shí)延的關(guān)系

使用卷積神經(jīng)網(wǎng)絡(luò)模型，學(xué)習(xí)率η=0.01。在MNIST 數(shù)據(jù)集下，模型組成為2 個(gè)卷積層和2 個(gè)全連接層。在CIFAR-10 數(shù)據(jù)集下，模型包括2 個(gè)卷積層、一個(gè)池化層和3 個(gè)全連接層。不同于MNIST 數(shù)據(jù)集，在該試驗(yàn)下，用戶的計(jì)算能力服從(50,500)的均勻分布。

圖5 給出了MNIST 數(shù)據(jù)集下B=200時(shí)，不同調(diào)度策略的性能對(duì)比。需要注意的是，文獻(xiàn)[13,18]策略不考慮用戶的上傳順序?qū)θ钟?jì)算量的影響，比例公平調(diào)度不考慮用戶的計(jì)算能力，隨機(jī)調(diào)度和輪詢調(diào)度既不考慮信道狀態(tài)也不考慮計(jì)算能力。由仿真結(jié)果可知，在測(cè)試精度為80%時(shí)，本文所提算法在收斂速度方面，較比例公平調(diào)度與文獻(xiàn)[13,18]提出的算法性能提升超過30%，較隨機(jī)調(diào)度和輪詢調(diào)度性能提升近50%。

圖5 MNIST 數(shù)據(jù)集下的性能對(duì)比

圖6 給出了CIFAR-10 數(shù)據(jù)集下不同算法的收斂性能。不同于MNIST 數(shù)據(jù)集，CIFAR-10 數(shù)據(jù)集下的收斂相對(duì)較慢，在該場(chǎng)景下，設(shè)置B=20 000。由仿真結(jié)果可知，以測(cè)試精度為70%為參考，本文算法在收斂速度方面，較比例公平調(diào)度與文獻(xiàn)[13,18]算法性能提高近25%，較隨機(jī)調(diào)度和輪詢調(diào)度性能提升近50%。

6.2 Non-IID 場(chǎng)景仿真設(shè)置

在Non-IID 場(chǎng)景中，使用MNIST 數(shù)據(jù)集作為本文算法的試驗(yàn)驗(yàn)證數(shù)據(jù)集，與IID 下MNIST 數(shù)據(jù)集試驗(yàn)場(chǎng)景設(shè)置相同。研究用戶數(shù)據(jù)不平衡度較低（100 個(gè)用戶，每個(gè)用戶擁有2 類數(shù)據(jù)樣本）和較高（100 個(gè)用戶，每個(gè)用戶擁有一類數(shù)據(jù)樣本）2 種Non-IID 場(chǎng)景下提出算法的性能。

6.2.1 不平衡度較高場(chǎng)景仿真結(jié)果

為了滿足用戶之間的不平衡度較高，設(shè)置用戶0～用戶9 擁有類別為0 的樣本數(shù)據(jù)，用戶10～用戶19擁有類別為1 的樣本數(shù)據(jù)，數(shù)量為600，依次類推。同時(shí)在該實(shí)驗(yàn)下，設(shè)置B=5 000，Bj=500，j=0,1,…,9，μ=100。仿真結(jié)果如圖7 所示。由于用戶的不平衡度較高，雖然更新時(shí)延優(yōu)先的調(diào)度策略一定程度上提高了當(dāng)前調(diào)度用戶的數(shù)據(jù)均衡度，但是由于用戶之間不平衡度較高，調(diào)度的用戶有很大概率不能包含所有類別的樣本，導(dǎo)致仍然存在數(shù)據(jù)不均衡情況。同時(shí)，數(shù)據(jù)平衡優(yōu)先的調(diào)度策略仍然可以滿足當(dāng)前輪調(diào)度的總數(shù)據(jù)樣本每種類別滿足大于或等于500。因此，在用戶數(shù)據(jù)不平衡度較高場(chǎng)景下，數(shù)據(jù)平衡優(yōu)先調(diào)度性能優(yōu)于更新時(shí)延優(yōu)先調(diào)度。雖然隨機(jī)調(diào)度和比例公平調(diào)度分別引入了隨機(jī)性和公平性，由于無(wú)法保證每輪調(diào)度的數(shù)據(jù)樣本保持均衡，因此模型始終處于發(fā)散狀態(tài)。同樣的，文獻(xiàn)[13,18]算法也無(wú)法保證全局樣本類別的均衡性，導(dǎo)致模型收斂性能較差。輪詢調(diào)度由于在實(shí)驗(yàn)中，每輪只有一種樣本被訓(xùn)練上傳，因此，在該場(chǎng)景下模型不收斂。

圖7 用戶含有一種類別數(shù)據(jù)性能對(duì)比

6.2.2 不平衡度較低場(chǎng)景仿真結(jié)果

不平衡度較低場(chǎng)景仿真與不平衡度較高場(chǎng)景仿真的設(shè)置相同，不同的是在該場(chǎng)景下，設(shè)置用戶0～用戶9 和用戶50～用戶59 擁有0 和1 這2 種樣本，用戶10～用戶19 和用戶60～用戶69 擁有2 和3這2 種樣本，依次類推。

如圖8 所示，由于用戶之間數(shù)據(jù)的不平衡度降低，每輪調(diào)度的用戶包含所有類別樣本的概率大大增加，因此更新時(shí)延優(yōu)先調(diào)度策略不僅能在時(shí)間上保證最優(yōu)。同時(shí)，由于包含所有類別樣本的概率增加，使當(dāng)前輪調(diào)度用戶的數(shù)據(jù)均衡度提升，因此在收斂性能上有了明顯的提升。數(shù)據(jù)平衡調(diào)度策略雖然可以保證調(diào)度用戶的調(diào)度數(shù)據(jù)集均衡，但是由4.2 節(jié)的分析可知，其在時(shí)延上的性能下降導(dǎo)致其模型收斂速率小于更新時(shí)延優(yōu)先調(diào)度策略。由于用戶數(shù)據(jù)集的不均衡度降低，隨機(jī)調(diào)度和比例公平調(diào)度以及文獻(xiàn)[13,18]算法的性能也有所提升，但是依然存在模型發(fā)散和收斂速度慢的缺點(diǎn)。

圖8 用戶含有2 種數(shù)據(jù)性能對(duì)比

7 結(jié)束語(yǔ)

本文首先在聯(lián)邦學(xué)習(xí)用戶IID 數(shù)據(jù)分布情況下，提出了基于TDMA 的用戶調(diào)度策略，以降低系統(tǒng)時(shí)延?？紤]到Non-IID 場(chǎng)景下用戶的樣本類別不均衡問題，進(jìn)一步提出了2 種啟發(fā)式用戶調(diào)度策略，分別應(yīng)對(duì)不平衡度高和不平衡度低的場(chǎng)景。此外，還進(jìn)行了理論上的收斂分析，并基于此收斂邊界和調(diào)度策略提出了全局最優(yōu)策略。原模型的求解配合數(shù)值結(jié)果，保證了本文策略具有良好的收斂性能。

附錄1 引理1 的證明

利用反證法證明。假設(shè)最小的系統(tǒng)時(shí)延滿足2 個(gè)相鄰的調(diào)度用戶上行傳輸時(shí)間點(diǎn)無(wú)間隙，則最優(yōu)系統(tǒng)時(shí)延上原系統(tǒng)模型必然滿足用戶計(jì)算樣本量等于B，假設(shè)當(dāng)前輪有k個(gè)用戶參與調(diào)度，那么

假設(shè)在用戶π(i? 1)與π(i)（π(i)≠π(1)）之間存在一個(gè)長(zhǎng)度為τgap>0的時(shí)間間隙，使該情況下全局計(jì)算樣本量為

令A(yù)3=B，因?yàn)橐獫M足約束條件式(9a)，則必然有

則A3=A1，因此當(dāng)A1=B時(shí)必然有A2

證畢。

附錄2 引理2 的證明

假設(shè)當(dāng)前輪有k個(gè)用戶參與調(diào)度，最優(yōu)的有序集為，且滿足條件式(10)。如果隨機(jī)交換中用戶π(a)和π(b)的上傳順序，假設(shè)原始上傳順序用戶π(a)先于π(b)，即a

因?yàn)棣甩?a)≤λπ(b)，假設(shè)其他用戶仍按重要度排序，則有

其中，a

這意味著當(dāng)順序交換后，重要度較大的用戶先于重要度較小的用戶上傳梯度，導(dǎo)致系統(tǒng)在相同時(shí)延下所能計(jì)算的樣本數(shù)量變小。

證畢。