聯邦學習中基于時分多址接入的用戶調度策略

2021-07-16 13:04:44陶梅霞王棟孫瑞張乃夫

通信學報 2021年6期

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

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

1 引言

隨著5G 移動網絡在全球范圍內逐漸普及，萬物互聯時代已到來，人工智能技術的應用也正從云端向網絡邊緣延伸。基于智能手機、可穿戴設備、無人機等邊緣設備的智能應用需求，如人臉識別、智能監控、智能駕駛、路徑規劃等不斷涌現。傳統的機器學習算法（包括訓練和推理）通常部署在云數據中心。為了訓練更準確的人工智能模型，邊緣設備需要將所采集的海量原始數據通過移動網絡發送至云端，這會給網絡帶來巨大的帶寬壓力，并面臨用戶隱私泄露的風險。得益于移動邊緣計算架構的發展[1]，將機器學習部署在網絡邊緣成為可能。邊緣學習[2-4]允許終端設備將原始數據保留在本地，在邊緣服務器的協調下參與模型訓練和推理，從而有效緩解網絡帶寬壓力，降低響應時延，并提升數據隱私性。邊緣學習是通信與計算學科融合的前沿方向，被認為是“人工智能的最后一千米”[3]。

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

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

本文旨在提出一種新的用戶調度策略，并對基于該策略的學習模型收斂性進行分析。該策略采用時分多址接入（TDMA,time division multiple access）方式，允許每個尚未被調度的用戶在其他用戶上傳梯度信息的時間段內繼續訓練本地樣本數據，直到被調度，實現系統整體“邊算邊傳”的計算通信高效融合，從而提升無線網絡中聯邦學習的性能。

本文的主要貢獻如下。

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

2) 由于用戶間數據的異構性，單純滿足計算樣本量無法保證非獨立同分布（Non-IID,non independent and identically distributed）場景下模型收斂。本文考慮用戶數據的類別分布差異，在獨立同分布（IID,independent and identically distributed）場景用戶調度策略的基礎上，引入約束樣本均衡度的數學模型，讓邊緣服務器自動決策用戶的計算樣本類別和各類數量，提高調度用戶訓練樣本的均衡性，在降低系統時延的基礎上提高模型訓練的準確率。

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

4) 仿真結果表明，本文算法具有良好的降低通信系統時延的性能。與基準調度策略的比較，驗證了本文算法的有效性。

2 現有相關工作

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

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

然而，現有工作都沒有充分挖掘TDMA 的這一優勢。文獻[13]雖提出了一種基于TDMA 方式的用戶調度策略，但是沒有考慮所選用戶的計算任務對模型的貢獻度。另一方面，文獻[13]假設用戶用于模型更新的樣本量固定，本地更新模型所需計算資源固定。然而，在異構網絡中，計算能力強的設備，在同等時間內可以計算更多的樣本，從而加快模型的收斂。因此，上述工作的假設無法充分利用設備計算資源。

與現有工作對比，本文提出的基于TDMA 的用戶調度策略不僅充分利用了系統邊算邊傳的優勢，還考慮了設備的計算能力和信道增益的異構性，分別在IID 數據集與Non-IID 數據集下，優化了用戶調度集合和用戶訓練的數據量，最小化單輪模型更新時延。本文還進一步基于模型收斂率分析，探討了批大小與訓練總時延的關系。

3 系統模型

3.1 聯邦學習模型

考慮如圖1 所示的聯邦學習系統，M個邊緣設備（用戶）在一個邊緣服務器（無線接入點）的協調下共同訓練一個學習模型。邊緣設備與邊緣服務器之間通過無線信道進行上下行通信。主要系統參數如表1 所示。

表1 主要系統參數

圖1 聯邦學習系統

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

1) 用戶選擇。邊緣服務器根據一定的策略進行用戶選擇，記Mt?M 為第t輪被調度的用戶集合。本文提出的用戶調度策略將在第4 節詳細介紹。

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

3) 本地訓練。被調度的用戶m∈Mt接收到全局模型wt后，基于本地數據集，采用隨機梯度下降（SGD,stochastic gradient descent）法執行本地模型訓練。本文參考有監督的機器學習任務，定義損失函數f(wt,x)表示在模型wt下的對訓練樣本x的預測誤差。如果值較大，則預測誤差較大；反之則較小。定義為第t輪用戶m本地訓練用到的數據集，記該數據集大小為，則損失函數定義為

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

其中，?是梯度操作。

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

在這一過程中，用戶可以對梯度信息進行量化和壓縮，來減少通信資源的消耗和系統的時延。

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

其中，η≥0 表示學習率。

3.2 通信與計算模型

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

由于下行鏈路的通信速率通常遠大于上行鏈路的通信速率，并且邊緣服務器可以采用廣播的方式與用戶進行下行通信，因此在實際系統中，聯邦學習的通信時延由上行鏈路的通信時延主導。因此，本文不考慮下行鏈路通信引起的時延。本文采用基于TDMA 的上行傳輸，同一時間段只有一個用戶在通信，并且可以占用整個系統帶寬。基于“邊算邊傳”的特點，被調度用戶的梯度上傳順序至關重要。在每一輪模型更新中，將被調度的用戶集Mt按照用戶上傳順序排列，重新定義為有序集，其中，πt(m)表示在第t輪里被選擇第m個上傳梯度的用戶索引，是在該輪被調度的用戶總數（一般來說，每輪調度用戶的總數可能不同，此處為簡化表述，省去了t）。用戶本地計算和梯度傳輸的時隙關系如圖2 所示，其中，用戶π(m)一直處于本地計算狀態，直至前一用戶π(m? 1)上行傳輸結束才停止本地計算，并開始上傳計算所得的梯度。在圖2 中，cπ(m)、Tπ(m)和τπ(m)分別表示用戶π(m)的本地訓練時間、梯度上傳時間點和梯度上傳所需通信時間。

圖2 用戶本地計算和梯度傳輸的時隙關系

由于每個本地梯度包含的元素個數相同，為方便起見，采用Q個比特來量化每個本地梯度。考慮用戶m被調度，則第t輪用戶m梯度上傳時延（單位為s）可以表示為

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

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

如果有計算時間，則用戶m可計算的樣本數量為

從圖2 可以看到，在每一輪全局模型更新里，第一個被調度的用戶π(1) 擁有最短的本地計算時延預算，而最后被調度的用戶π(k)的本地計算時延預算最長。基于上述通信與計算模型，第t輪全局模型更新所需總時延可以用最后一個被調度的用戶的梯度上傳時間點和通信時間來表示，記為。

4 用戶調度策略

4.1 IID 數據分布用戶調度

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

根據3.2 節的時延模型，問題模型可以描述為

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

顯然，上述優化問題屬于NP 完全問題，難以獲得最優解的閉式表達式。通過引入以下2 個引理，可以將原問題的求解退化為一維背包問題，進而獲得該問題的最優數值解。定義λm=pm/τm為用戶m的調度重要度。

引理1任意2 個相鄰的調度用戶滿足上行傳輸時間點無間隙，即滿足cπ(m)?cπ(m?1)=τπ(m?1)。

引理2調度用戶有序集中的最優的用戶調度順序必須滿足

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

基于引理1 和引理2，原問題的求解可以退化為一維背包問題的求解。區別于傳統的背包問題，該問題下物品的價值（即每個用戶能計算的樣本）不是常量。該問題的求解需要上述引理與動態規劃算法的結合，通過對背包空間的搜索和物品價值的度量，尋找在給定的背包空間（單輪迭代總時延）下所能容納的最大物品價值（單輪迭代所能計算的樣本總量），再通過二分法搜集解空間，尋求問題的最優解。

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

算法1基于背包問題的用戶調度策略

算法2基于二分法尋找最優時間

通過算法1 可以解出在給定單輪通信系統時延為Stotal時的最優用戶調度順序集和所能計算的本地數據樣本量。通過算法2 對Stotal的搜索可以找到滿足單輪本地數據樣本量大于或等于B所需的精度在任意ε以內的最小單輪通信系統時延。

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

4.2 Non-IID 數據分布用戶調度

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

基于上述關于數據平衡問題的討論，Non-IID場景下的用戶調度策略不僅要考慮用戶的重要度λm，也要考慮本輪參與調度用戶的總的訓練樣本中每個類別的樣本是否滿足給定的數量要求。因此，問題模型可以描述為

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

由于在建立系統模型時引入了用戶的樣本類別分布參量，此問題若繼續使用背包問題求解則需要建立背包空間與全局計算樣本量以及每類樣本的數據分布的關系，這是十分困難的。根據Weierstrass 定理，存在一個標量非空和有界，因此系統模型一定存在最優解。本文提出2 種啟發式的調度方案，在聯邦學習Non-IID 場景下兼顧數據均衡性和系統時延。

4.2.1 數據平衡優先的用戶調度

由于原問題不能直接求解，一個啟發式的方案為首先按照引理2 定義的用戶重要度規則確定調度用戶有序集；然后，邊緣服務器根據計算出以使更新時延最小化。

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

算法3基于數據平衡優先的用戶調度策略

算法3對處理用戶之間數據不平衡程度較高的場景有很好的效果。因為在做用戶選擇時不僅考慮了用戶的計算能力和通信狀態，同時由于邊緣服務器根據不同類別的樣本數量參與用戶的選擇，使單輪每一種類別的樣本數量都能滿足要求。但是為了平衡某些稀有類樣本到計算能力或者信道狀態不好的用戶設備上，系統會等待直至它完成計算該類別所需的樣本數量，由此會造成單輪系統時延的增加。

4.2.2 更新時延優先的用戶調度

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

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

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

通過合理采用數據平衡優先的用戶調度策略和更新時延優先的用戶調度策略，可以分別在數據不平衡度高和不平衡度低時，兼顧系統時延和模型收斂問題。

4.2.3 計算復雜度分析

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

5 收斂性分析與優化

第4 節討論了單輪聚合時滿足給定計算樣本數量（即批大小）B的前提下，使單次聚合的系統時延最小化的用戶調度問題。本節首先分析單輪總批大小對模型收斂性能的影響；然后，分析所提出的用戶調度策略下單輪系統時延與批大小的關系，從而進一步探究系統總時延與收斂性能之間的均衡關系；最后，探討在給定收斂性能目標下能夠最小化系統總時延的最優批大小的選擇。

5.1 學習算法收斂性

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

其中，B 為批大小為B的數據組成的集合。

本文采用后悔評估函數來刻畫學習算法的收斂性能。后悔值表示損失函數與最優損失的累計誤差，那么N輪聚合結果為

其中，w?是最優解，即模型的最終可達目標，。

假設損失函數滿足如下條件。

1) 凸性。f(?)是一個凸函數。

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

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

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

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

5.2 模型收斂性與系統總時延的關系

本文模型訓練的最終目標是在保證學習的收斂性能的情況下，最小化全局系統時延。下面，首先根據前文中IID 數據分布下的單輪次調度策略推導單輪次時延，即一輪本地訓練和聚合所需的時間。

記T為一輪總的系統時延。根據前文提出的調度策略有

定義pmin為參與調度用戶中計算性能最差用戶的計算能力，則

定義τmax為上傳用戶集中信道狀態最差的用戶的上傳時間，則

進一步地，因為τmax為信道狀態最差的用戶的上傳時間，按照本文的調度規則，即

代入式(19)，則

則T與B的關系為

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

最終系統的總時延為

從式(27)可以看出，系統總時延隨著總批大小B和全局聚合次數N的增大而增大。結合前文所得收斂邊界結果，即式(16)，可以看出增加聚合次數和總批大小會對收斂帶來增益，但是同樣增加了系統總時延，并且性能增益與系統時延處于同一量級。因此，最終肯定存在最優的調度方針使滿足性能需求的前提下最小化總時延。接下來，進一步分析收斂性能與系統總時延之間的關系，設Gmax為所需要達到的收斂邊界，那么必然要求收斂邊界滿足

首先，探討聚合次數為定值的情況下，收斂性能與系統總時延的均衡關系。將總批大小寫成關于聚合次數的表達式，即

在給定聚合輪次下，總系統時延隨著總批大小的增加而增加，因此B取下界，此時總批大小選擇是一個關于系統可達性能的表達式，將結果代入總時延表達式可得

歸一化系統總時延與歸一化收斂性能二者之間的關系如圖3 所示。從式(30)中可以看出，當給定聚合次數N時，系統總時延與收斂性能近似成反比關系，符合圖3 中顯示的變化趨勢。結合式(29)繪制圖3 中選取點的批大小B的取值，可以看出，隨著批大小的增大，收斂邊界值與總批大小的次冪以一定比例值縮小，系統總時延以該比例值近似放大。此外，由于影響因子的存在，收斂邊界存在最小值，即無論如何訓練，收斂總是不能變為零，而只能趨近于一個值。

圖3 收斂邊界與系統總時延的均衡關系（固定聚合次數）

接著，進一步探討最優總批大小選擇的問題。將聚合次數寫成關于總批大小的表達式，則

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

在給定可達目標的情況下，式(32)中存在最小值，即批大小存在最優選擇。由于式(32)存在很多的假設和縮放，因此無法得出實際數值解，只能得到變化趨勢，最優批大小的選擇會通過仿真得到。

6 實驗結果

本文基于開源框架PyTorch，利用真實數據集來驗證所提用戶調度策略相較于其他算法的有效性，并檢驗收斂性分析的準確性。本文實驗使用了以下2 個常用的數據集。

1) MNIST。MNIST 手寫數字數據集是機器學習領域非常經典的數據集，包含手寫數字0～9 共10種類型的圖片。該數據集包含60 000 個用于訓練的訓練樣本和10 000 個用于測試的測試樣本，每個圖片都是28 像素×28 像素、值為0～1 的固定大小。

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

6.1 IID 場景

本節選用3 種常用的用戶調度策略，即隨機調度、輪詢調度和比例公平調度，以文獻[13,18]提出的2 種不同通信接入方式下的用戶調度策略作為基準，與本文所提用戶調度策略進行性能對比。

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

2) 輪詢調度。在每輪迭代中，邊緣服務器輪流選擇用戶集中的用戶上傳，當滿足全局聚合所需的批大小時，用戶停止上傳，邊緣服務器通過聚合將更新的模型廣播給所有用戶，并繼續按照此規則進行下一輪迭代。該算法的優點是簡單，不需要記錄當前的連接狀態，是一種無狀態調度。

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

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

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

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

6.1.1 仿真設置

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

首先，以IID的方式隨機將MNIST和CIFAR-10數據集分配給所有用戶，其中，MNIST 下每個用戶600 個訓練樣本，CIFAR-10 下每個用戶500 個訓練樣本。

6.1.2 仿真結果

基于5.2 節關于最優批大小的探討，本節通過將理論分析與實驗仿真相結合，驗證本文基于通信與計算融合的用戶調度策略下，能達到目標性能所需的總批大小與系統總時延的關系。以MNIST 數據集為例，主要測試了2 個性能目標，即測試精度為80%和90%，以及理論趨勢的結果。

圖4 顯示了理論趨勢與不同測試精度的批大小與總時延的關系。隨著精度的增加，系統總時延不斷增加。對于同一精度目標，雖然總時延隨著批大小的增加存在波動性，但是總體變化符合理論的結果，呈現先減小后增加的趨勢。結合理論分析的結果，初始的總時延急速減小是由于批過小，從而導致模型梯度分散值很大，收斂速度很慢甚至對于過高的精度而言難以進行收斂。由于批大小的增加，需求的用戶調度數目增加，而這種增加帶來的通信時延的增加逐漸超過系統性能的提升，致使系統總時延隨著批大小先減后增，從而存在最優的批大小選擇。

圖4 批大小與總時延的關系

使用卷積神經網絡模型，學習率η=0.01。在MNIST 數據集下，模型組成為2 個卷積層和2 個全連接層。在CIFAR-10 數據集下，模型包括2 個卷積層、一個池化層和3 個全連接層。不同于MNIST 數據集，在該試驗下，用戶的計算能力服從(50,500)的均勻分布。

圖5 給出了MNIST 數據集下B=200時，不同調度策略的性能對比。需要注意的是，文獻[13,18]策略不考慮用戶的上傳順序對全局計算量的影響，比例公平調度不考慮用戶的計算能力，隨機調度和輪詢調度既不考慮信道狀態也不考慮計算能力。由仿真結果可知，在測試精度為80%時，本文所提算法在收斂速度方面，較比例公平調度與文獻[13,18]提出的算法性能提升超過30%，較隨機調度和輪詢調度性能提升近50%。

圖5 MNIST 數據集下的性能對比

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

6.2 Non-IID 場景仿真設置

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

6.2.1 不平衡度較高場景仿真結果

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

圖7 用戶含有一種類別數據性能對比

6.2.2 不平衡度較低場景仿真結果

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

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

圖8 用戶含有2 種數據性能對比

7 結束語

本文首先在聯邦學習用戶IID 數據分布情況下，提出了基于TDMA 的用戶調度策略，以降低系統時延。考慮到Non-IID 場景下用戶的樣本類別不均衡問題，進一步提出了2 種啟發式用戶調度策略，分別應對不平衡度高和不平衡度低的場景。此外，還進行了理論上的收斂分析，并基于此收斂邊界和調度策略提出了全局最優策略。原模型的求解配合數值結果，保證了本文策略具有良好的收斂性能。

附錄1 引理1 的證明

利用反證法證明。假設最小的系統時延滿足2 個相鄰的調度用戶上行傳輸時間點無間隙，則最優系統時延上原系統模型必然滿足用戶計算樣本量等于B，假設當前輪有k個用戶參與調度，那么