基于無線D2D網絡的分層聯邦學習

劉翀赫，余官定，劉勝利

(浙江大學 信息與電子工程學院，浙江 杭州 310027)

在移動數據流量爆炸式增長的驅動下，機器學習在大量研究領域取得顯著的成功，例如計算機視覺和自然語言處理.隨著越來越多的邊緣設備接入互聯網，無線網絡中的訓練數據可能會被各種設備收集，由于嚴格的隱私協議和稀缺的通信資源，這些數據無法被傳輸到中央服務器.為了克服這些挑戰，最近提出的聯邦學習已經成為一種流行的分布式機器學習技術[1-2]，該技術使許得多設備能夠訓練本地模型并與服務器交換模型參數或梯度.聯邦學習系統中的設備通常是以星形拓撲連接[3]，例如在典型的參數服務器架構中，每個設備根據自己的數據集訓練一個局部模型后上傳到服務器，服務器通常使用加權平均值將其聚合為全局模型[4].在大規模設備共同參與聯邦學習訓練的場景中，由于中央服務器需要聚合來自數百個設備的模型信息，通信資源成為影響聯邦學習系統收斂速率的關鍵因素[5].當系統中可用的網絡帶寬較低時，中心化架構會導致網絡中產生流量擁塞，模型訓練的收斂速率會顯著下降.

Lim等[6]提出分層聯邦學習架構來緩解參數服務器的帶寬壓力，利用簇內聚合避免頻繁地全局聚合，減輕中央節點的通信成本.Wang等[7]提出一種稱為FedCH的聯邦學習機制，通過構建一個特殊的集群拓撲并執行分層聚合進行訓練.一個集群中的設備將本地更新同步發送到中心節點進行聚合，而所有中心節點采用異步的方式進行全局聚合.大多數的分層聯邦學習工作主要是以模型平均的方式進行簇內聚合，這需要在每個簇中存在一個中心節點來收集模型參數或梯度，集中式架構會在中心節點造成擁塞.在簇內無服務器的實際場景中，往往難以找到與簇內其他設備間都有良好通信鏈路的中心節點.

為了實現通信高效的聯邦學習，將傳統的設備到服務器通信與設備直通(device-to-device, D2D)通信相結合[8-9]，提出一種基于無線D2D網絡的分層聯邦學習.依據所處的地理位置將邊緣設備劃分為多個簇，各個簇同時進行去中心化學習[10]，通過共同訓練機器學習模型來確保實現共同的學習目標.在訓練的2個全局聚合間隔期間，設備在各自的數據集上執行若干次隨機梯度下降(stochastic gradient descent, SGD)迭代，通過簇內的無線D2D通信網絡，設備定期地與鄰居設備交換模型參數進行簇內模型聚合.在全局聚合時，每個簇中只有一個設備需要將模型上傳到服務器，這個設備被定義為簇頭.服務器根據模型平均算法，對所有簇頭的本地模型進行全局聚合.簇頭的模型反映其集群經過去中心化訓練后得到的本地模型的特征[11-12].

與大多數傳統的設備需要上傳本地模型的聯邦學習不同，所提方法大大減少了設備與基站之間通信的數據量，降低了中央基站發生流量擁塞的可能性.對于全局聚合期間的簇頭選擇與帶寬分配問題進行聯合優化，使用圖中節點的度來衡量模型性能，并基于動態規劃設計最優簇頭選擇和帶寬分配的算法，使用真實數據集的仿真結果證明無線D2D網絡的分層聯邦學習算法的性能.該算法通過分層聚合和D2D通信，減少模型收斂所需的訓練時間，同時將分層聯邦學習算法的擴展到簇內無服務器的系統結構.

1 系統模型與算法

1.1 系統模型

考慮具有一個邊緣服務器和N個邊緣設備的聯邦學習系統，目的是協作訓練一個機器學習模型，如圖1所示.所有設備根據地理位置的相近性被劃分為C個簇，由集合{S1,···,SC}表 示，第k個簇Sk包含nk=|Sk|個邊緣設備.假設D2D通信是雙向的，簇內設備之間的D2D鏈路是否阻塞根據設備的發射功率、設備之間的信道條件及物理距離確定[13-14].簇Sk中未阻塞的D2D鏈路構成圖為Gk=(Sk,Ek)，其 中Ek為邊的 集 合.為了 確 保簇內 訓練 能夠收斂，假設Gk為連通的圖[15].

圖1 基于無線D2D網絡的分層聯邦學習系統模型Fig.1 System model of hierarchical federated learning system based on wireless D2D networks

邊緣設備i∈Sk通過感知物理環境來收集數據，并構成本地數據集由于簇內不存在可以與所有設備通信的中央節點，考慮在每個簇內以去中心化學習的方式訓練模型.對于邊緣設備i∈Sk，用Ni?Sk表示在連通圖Gk中與其相鄰的設備集合.為了減小傳輸時間和提高模型的性能，在服務器上實現一個調度器來執行簇頭選擇[16]和帶寬資源分配聯合優化算法.

1.2 分層聯邦學習算法

在聯邦學習系統中，每個設備i基于自身的數據集Di訓練出一個本地 模 型.設 備i處的 數據分布的局部經驗損失函數為

式中：ωi為本地模型參數；ξ為參與迭代 訓練的數據樣 本；L(ωi,ξ) 為樣本損失函數，量化數據樣本ξ上的預測誤差.

分層聯邦學習算法主要目標是優化全局模型參數 ω，以最小化與所有設備關聯的全局損失函數為

在無線D2D網絡的分層聯邦學習中，訓練過程分為本地模型更新、簇內聚合和全局聚合3個步驟， 這些步驟的組合稱為一個訓練輪次.

1)本地模型更新：每個設備使用 SGD 算法更新本地模型.在訓練的第t輪過程中，第l次迭代更新過程為

2)簇內聚合：簇內設備進行φ次迭代更新后，進行一次簇內模型聚合.基于無線D2D網絡，設備i∈Sk將模型參數以廣播[17]的方式發送到每個相鄰設備j∈Ni，并且同時從Ni中接收模型參數計算鄰域平均值，以更新本地模型.當迭代次數l是φ的整數倍時，進行簇內模型參數聚合得

式中：常數 α為與圖拓撲相關的設計參數，以確保快速收斂[11].

3)全局聚合：當所有的簇進行 τ次簇內聚合，每個設備基于本地數據集進行L=φτ次SGD迭代更新后，服務器以同步的方式執行全局聚合.在服務器上實現簇頭選擇和帶寬資源分配聯合優化算法來確定每個簇中的簇頭，簇頭設備將此時模型的參數上傳至服務器.服務器接收C個簇頭的本地模型參數，通過參數平均更新全局模型為

最后，服務器將全局模型廣播到所有設備.重復上述步驟，直到全局模型收斂.

為了更清楚地說明提出算法的訓練過程，在圖2中給出示例，其中有4個設備，分別編號為1～4，每個矩形的長度表示相應操作的時間消耗.對于分層去中心化聯邦學習，根據設備的位置將分為2個簇，即設備1和2屬于簇1，設備3和4屬于簇2，然后每個集群獨立執行去中心化訓練過程.從第t輪開始，簇1、2分別執行3次本地更新、簇內聚合后，進行一次全局聚合.選擇設備1和設備4分別作為2個簇的簇頭，將模型上傳至參數服務器進行全局聚合.

圖2 分層聯邦學習算法時序模型Fig.2 Sequence model of hierarchical federated learning

2 通信模型

2.1 帶寬資源分配概述

無線聯邦學習系統的可用帶寬資源為B.將所有帶寬資源分割成2個部分：B=B(1)+B(2),分別用于簇內聚合和全局聚合.對于簇內聚合階段，所有簇內的D2D通信共用帶寬B(1).考慮D2D鏈路可靠的通信場景，在整個訓練過程中所有簇的D2D連通圖保持不變.由于D2D信道估計的信令開銷非常昂貴，因此假設所有D2D鏈路的瞬時信道狀態信息未知.假設已知的所有鏈路的路徑損耗主要取決于位置信息，并且變化緩慢.對于全局聚合階段，簇頭與基站通信使用的帶寬資源為B(2)，基站和設備通過無線鏈路連接.

2.2 簇內D2D通信

基于無線D2D網絡進行簇內聚合,考慮簇Sk中的任意設備(比如設備i)和去中心化訓練的任意一輪(比如第l輪)，這一輪訓練中的時延由2個階段決定：計算階段和通信階段.

1)本地模型的計算時延：設備進行φ次本地模型梯度下降更新的時延與設備的計算能力有關[17].計算能力越差，該計算時延越大.

2）D2D通信時延：為了利用設備的接近性并縮短通信時間，D2D鏈路用于簇內設備之間的數據傳輸.設備向鄰居集合Ni廣播本地模型，并從其他設備接收模型參數以聚合全局模型.假設D2D鏈路的信道在一次訓練迭代中是靜態的，并且在不同的迭代中會有所變化[18].所有簇內的D2D通信共用帶寬B(1)，因為簇與簇之間的地理距離較遠，屬于不同簇的設備使用，所以可以將相同頻帶通信時的相互之間干擾視為噪聲[19].假設D2D通信是使用正交頻分技術進行的，不考慮簇內通信的干擾， 將B(1)劃分為nk個正交的子信道，每個子信道分配給簇Sk中的一個設備.從設備i到設備j的 鏈路信道功率增益為hi,j.設備i將模型參數廣播發送到相鄰設備所需的通信時延為

為了提高收斂速率，在可用帶寬資源為B(1)的約束條件下最小化每一輪簇內去中心化學習的訓練時延：

式中：P 1是一個凸優化問題，當簇Sk中所有設備的訓練時延都相等，即時 ，設備i用于廣播的帶寬Bi是最優分配的.

2.3 簇頭與基站通信

在所有的簇都經過 τ輪簇內聚合后，進行一次全局模型聚合.從每個簇中選擇一個簇頭，考慮任意 一個簇(比如簇Sk)，它 的簇 頭 為Hk.簇頭Hk經過τ輪簇內聚合后得到的本地模型作為整個簇的代表，上傳模型參數至基站.采用正交頻分技術將B(2)劃分成C個正交子信道，Bk為 簇 頭Hk分 配 到的帶寬，hk為簇頭的上行信道增益，pk為簇頭的發射功率，簇頭上傳模型參數至基站所需的時間為

基站 使用 帶寬B(2)來廣播全局模型.p為基 站的發射功率，|hmin|為所有簇頭設備中最小的下行信道增益，那么基站廣播全局模型所需的時間為

Td為下行廣播通信時延.

基站上的服務器對所有簇頭模型參數進行平均所需的計算時延為Ta，那么一輪全局聚合的時延 為

3 簇頭選擇與帶寬分配

3.1 問題建模

為了降低全局聚合時的通信時延，優化簇頭與基站通信的帶寬資源分配方法以及提高全局模型的性能表現，需要確定合理的簇頭選擇方法.簇頭的本地模型能夠精確地反映集群經過訓練后得到的模型特征.在全局聚合階段，從每個簇內選擇作為簇頭設備的集合為 {H1,···,HC}.用布爾變量wk,i表示設備i∈Sk是 否被選擇為第k個簇的簇頭.wk,i=1 表示被選擇為簇頭，否則wk,i=0.沒有被選為簇頭的設備不上傳模型，上傳時間為零，因此設備i∈Sk的上傳時間為

簇頭通過無線鏈路與基站相互通信，進行模型參數的傳輸，基站收集到所有簇頭上傳的數據后才能進行全局參數聚合.為了避免鏈路質量差的設備被選為簇頭進而限制整體的收斂速率，根據所有設備的上傳時間確定一個常量TBound，作為傳輸時間的上界[20]，上傳時間超過上界的設備禁 止被選擇.決定簇頭選擇的布爾變量wk,i和決 定B(2)在每個簇之間分配的變量Bk都存在于設備上傳時間式(10)中，因此簇頭選擇和帶寬分配是相互影響的.

經過若干輪簇內去中心化訓練后，選擇性能好的模型上傳有利于加快全局收斂.為了提高算法的收斂速率，通過聯合優化簇頭的選擇問題與簇頭上行鏈路帶寬分配，最大化收斂速率.在給定的傳輸時間上界TBound內，所有簇頭必須完成模型參數上傳，盡可能選擇每個簇內本地模型學習性能表現好的設備作為簇頭.為了對中心化訓練得到的模型性能進行度量，研究模型性能與設備在D2D鏈路連通圖中的度(degree)的關系.設備i∈Sk在D2D鏈路連通圖Gk=(Sk,Ek)中所代表節點的度記為Dk,i，度是指和設備i相連接的設備數目，即Dk,i=|Ni|.設備的度越大表示在D2D網絡中與該設備相連通的其他設備數量越多，在進行簇內參數聚合時可以與更多設備交換模型數據.經過式(4)的鄰域參數平均后，度越大的設備得到的本地模型越接近于簇內所有模型的參數平均值，訓練后的本地模型更能夠反映出簇內數據分布的真實狀況[21].

為了研究連通圖中節點的度對去中心化訓練得到的模型收斂性能的影響，在數據獨立分布的10個設備組成的集群中，進行由式(3)～(5)定義的去中心化分布式訓練, 直到與所有設備關聯的全局損失函數收斂至ε=0.15.每次實驗前隨機生成D2D連通圖，分別在Cifar-10和MNIST數據集上訓練卷積神經網絡(CNN)和深度神經網絡(DNN)，進行100次實驗后，根據數據擬合每個設備的局部經驗損失f與設備在連通圖中的度D的關系，得到的結果分別為

式中：p1、p2、p3、q1、q2為負二次冪擬合的參數，q1、q2為負一次冪擬合的參數，擬合結果如圖3、4所 示.在 Cifar-10 上中心化訓練CNN至收斂時，局部經驗損失與度成負二次冪關系；在 MNIST 上中心化訓練 DNN 至收斂時，局部經驗損失與度成負一次冪關系.由此可以得出，度越大的節點，訓練后得到的本地模型的性能表現越好.

圖3 在Cifar-10上訓練CNN局部經驗損失與度的關系Fig.3 Local experience loss versus degree for training CNN on Cifar-10

圖4 在MNIST上訓練DNN局部經驗損失與度的關系Fig.4 Local experience loss versus degree for training DNN on MNIST

在本研究中，以設備在連通圖中的度來衡量設備的本地模型學習性能，聯合優化問題的目標即可建模為：在規定的上行傳輸時間上界TBound內，使得被選中簇頭的設備的度之和最大化：

當wk,i=0 時，=0,約束(17)一定滿足；當wk,i=1 時，時最節省帶寬.所以為了得到最大化目標值，約束(19)的不等式應該取等號后帶入約束(16)，定義變量為優化問題轉化為

P3 是一個分組背包問題：有N件物品和一個容量為B(2)的背包，這些物品被劃分為C個 組，第k個組中物品數量為nk.第k個 組 中 的 第i件物品的價值為Dk,i，體積 為Vk,i.每個組中的物品 只 能選 一件，目標是求解將某些物品裝入背包使得在不超過背包容量的情況下，物品的價值最大.使用動態規劃算法對P3求最優解，時間復雜度相對于回溯法和窮舉法等其他最優化方法較低[22].建立大小 為C×B(2)的 二維數組F和G，F[k,v] 為 從 前k組中選擇能裝進容量為v的背包物品的最大價值,G(k,v)為達到此最大價值的狀態轉移路線，具體描述如下.

1) 將 二維數組F和G初始化為0；

2) f ork=(1,2,···,C)；

3) f orv=(B(2),B(2)-1,···,Vk,i)；

4)F[k,v]=

5)G[k,v]=

6) e nd f or；

7) e nd f or.

從F[C,B(2)] 開 始，根據狀態轉移路線數組G回溯，得到背包問題的解決方案作為簇頭的選擇結果.假設第k個簇中被選中的設備的索引下標為j，則簇頭Hk的帶寬的最優解為

4 仿真實驗結果

4.1 實驗設置

考慮一個r=300 m的小蜂窩網絡.小區內有C=10個設備集群，每個集群有10臺設備，每個設備的發射功率為23 dBm.在每個集群中，設備隨機分布在r=50 m的D2D網絡中,每對設備之間的D2D鏈路以P=0.5的概率激活,并且保證每個簇的D2D拓撲結構是一個連通的圖.無線D2D鏈路的路徑損耗由 98.45+20log10(d)生 成，d為設備之間的距離，單位為km.帶有中央服務器的基站位于蜂窩網絡的中心，發射功率為46 dBm，每個集群的位置中心與基站的距離為250 m.設備與服務器之間的路徑損耗模型為128.1+37.6log10d，d為 設備到服務器的距離，單位為km.小尺度衰落遵循瑞利分布.系統總帶寬B=20 M Hz,B(1)=B(2)=10 MHz.

考慮到訓練分類器的學習任務，采用經典的CNN模型 VGG19和具有2個隱藏層的DNN模型進行實驗.對于CNN，使用著名的Cifar-10數據集，其中包含50000張訓練圖像和10000張測試圖像，具有10個類別；對于DNN，使用手寫數據集MNIST中的50000張訓練圖像和10000張測試圖像.由于數據分布可能受地理位置和用戶習慣的影響，在不同集群設備之間的數據分布是非獨立同分布的，即首先按標簽對所有數據樣本進行排序，然后將它們分成50個大小為1000的分片，為每個集群分配 5個分片.每個集群只能獲得5類訓練樣本.以獨立同分布的方式將數據樣本均勻地分配到集群中的設備上.為了避免選擇上行信道較差的設備選為簇頭而增大全局聚合的時延，傳輸時間上界TBound由平均分配帶寬發送數據時所有設備的上行時延最大值確定：

式中：0 ＜β＜1.0 ，調整 β的大小進行多次實驗，根據收斂速率來確定TBound的合理值；TBound對于傳輸CNN和DNN模型分別設置為5.0 s和0.5 s可以使提出的算法具有較快的收斂速率；本地更新迭 代 次 數φ=20 ,每 兩輪全局聚合之間進行τ=10次簇內模型聚合.

4.2 與基線算法對比

為了驗證所提利用D2D通信的分層聯邦學習可以節約通信開銷，加快收斂速率，對所提算法與傳統的聯邦學習算法FedAVG[4]和現有的分簇聯邦學習算法FedCH[7]的性能進行對比.在作為基線的FedAVG算法中，系統帶寬B=20 MHz全部用于設備與基站通信，經過φ=20次本地更新迭代后, 在每次全局聚合時所有設備都將其本地模型上傳到服務器.在作為基線的FedCH算法中，簇內通信帶寬B(1)=10 MHz，簇頭與基站通信帶 寬B(2)=10 MHz.經 過φ=20次本地更新迭代后,每個集群中的設備將其本地模型同步發送到簇頭進行聚合，所有中心節點采用異步的方式進行全局聚合.

使用不同算法訓練CNN和DNN測試集準確率A隨時間t變化如圖5、6所示.從圖中可以看出，提出的算法收斂速度比其他2種基線算法更快，并且最終得到的模型精度與FedAVG算法相當，略高于FedCH算法.對于在Cifar-10訓練CNN和在MNIST上訓練DNN，提出算法的收斂速率比FedAVG算法分別提高了5倍和3倍.由于采用分層的聯邦學習架構后，各個簇獨立進行去中心化訓練，基于D2D網絡進行模型參數聚合的傳輸速率較快，以簇內聚合代替全局聚合使全局的聚合頻率和上行鏈路密集度都降低了10倍.在訓練CNN和DNN時分別減少89.4%和82.7%的全局聚合通信時間.

圖5 不同算法下CNN在Cifar-10上的準確率隨時間變化Fig.5 Accuracy of CNN on Cifar-10 varies with time in different algorithms

圖6 不同算法下DNN在MNIST上的準確率隨時間變化Fig.6 Accuracy of DNN on MNIST varies with time in different algorithms

不同于FedCH算法，所提算法使用D2D通信在簇內節點之間交換模型參數，避免中心節點收集模型參數時產生擁塞.在訓練CNN和DNN時，模型收斂速率提高了61.1%和56.3%.相對于采用異步的方式進行全局聚合的FedCH算法，所提算法同步地對所有簇模型信息進行全局聚合，因此最終得到的模型性能更好.

4.3 不同簇頭選擇方法的影響

為了驗證所提簇頭選擇與帶寬分配聯合優化算法的有效性能，在下面的實驗中實現了2種作為基線的簇頭選擇方法，即信道感知調度和連通度感知調度.在信道感知調度中，依據設備與基站的上行信道狀態、設備的發射功率，從每個簇中選擇與基站通信時間最短的設備作為簇頭，使得上傳模型所需的總通信時延最小化.被選為簇頭的設備集合表示為 {H1,···,HK} ，簇Sk的簇頭為

由于D2D鏈路的連通狀態在整個訓練過程中是不變的，每輪選擇的簇頭也固定不變.在連通度感知調度中，為了提高全局模型的性能，從每個簇中選擇在連通圖中度最大的節點作為簇頭即：

按照上述2種策略分別選擇出簇頭后，假設簇頭Hk與基站的上行信道分配到的帶寬為Bk,為了使得上傳模型所需的通信實驗最小化，帶寬分配的最優值為

從圖7和8中可以看出，提出的簇頭選擇與帶寬分配聯合優化算法在整個訓練過程中實現了最快的收斂速度和最高的學習性能，原因在于信道感知調度忽略本地模型的性能，選中的簇頭可能具有性能較差的本地模型.連通度感知調度沒有考慮到信道狀況，上傳模型所需的通信時間是該策略的瓶頸.由于所提聯合優化算法每輪選擇的簇頭不是固定的，這為整個訓練增加了隨機性，因此可以得到比固定簇頭的連通度感知調度更高的學習性能.實驗結果證實了權衡模型性能提升與減少通信時間所提出的簇頭選擇算法的有效性.

圖7 不同簇頭選擇方法下CNN在Cifar-10上的準確率隨時間變化Fig.7 Accuracy of CNN on Cifar-10 varies with time in different cluster head selection methods

4.4 不同全局聚合頻率的的影響

圖8 不同簇頭選擇方法下DNN在MNIST上的準確率隨時間變化Fig.8 Accuracy of DNN on MNIST varies with time in different cluster head selection methods

為了驗證利用D2D網絡進行簇內聚合的分層聯邦學習對于不同全局聚合頻率具有魯棒性，將每2輪全局聚合之間的簇內模型聚合次數 τ改變，并且保持本地更新迭代次數不變.從圖9和圖10中可以看出，基于D2D網絡進行一次簇內模型聚合所需的通信時延顯著小于終端與基站進行全局聚合所需的通信時延，在一定范圍內提高簇內模型聚合次數來降低全局聚合的頻率有利于縮短訓練時間.然而當簇內模型聚合的次數繼續增加，全局聚合頻率過低會影響模型的性能提升，簇內聚合的次數增加所帶來的通信時延下降的收益被抵消.該結果表明，基于D2D通信進行簇內聚合可以減少對中央服務器的依賴，從而實現更分散的模型訓練過程.

圖9 不同全局聚合頻率下CNN在Cifar-10上的準確率隨時間變化Fig.9 Accuracy of CNN on Cifar-10 varies with time in different global aggregation frequencies

圖10 不同全局聚合頻率下DNN在MNIST上的準確率隨時間變化Fig.10 Accuracy of DNN on MNIST varies with time in different global aggregation frequencies

5 結語

本研究提出一種基于無線D2D網絡的分層聯邦學習訓練框架，構建集群拓撲并執行分層聚合以進行訓練.該系統結構通過D2D網絡進行簇內聚合，各個簇同時進行去中心化訓練.從簇中選擇一個代表集群訓練結果的簇頭上傳模型至基站，進行全局聚合.該框架降低了中央服務器出現流量擁塞的可能性，同時將分層聯邦學習應用到簇內無服務器的場景.為了縮短信時間并且提高模型的性能表現，使用圖中節點的度來衡量本地模型的收斂性能，通過最大化所有簇頭的度之和，對簇頭選擇與帶寬分配問題進行聯合優化，并且基于動態規劃設計最優的算法.仿真實驗結果表明與基線算法相比，該框架可以有效縮短訓練時間和提高學習性能.