基于匹配的模型卸載邊緣聯(lián)邦學(xué)習(xí)方法

摘 要：針對(duì)邊緣計(jì)算環(huán)境下聯(lián)邦學(xué)習(xí)中因資源異質(zhì)性導(dǎo)致的“滯后者”效應(yīng)等問(wèn)題，提出基于匹配的模型卸載邊緣聯(lián)邦學(xué)習(xí)方法（Fed-MBMO）。該方法通過(guò)收集邊緣設(shè)備的性能分析結(jié)果，將設(shè)備分別劃分為強(qiáng)、弱客戶(hù)端，考慮了模型訓(xùn)練的四個(gè)階段時(shí)間占比，弱客戶(hù)端通過(guò)凍結(jié)部分模型以節(jié)省在特征層上反向傳播的時(shí)間，并將模型卸載至“強(qiáng)客戶(hù)端”進(jìn)行額外的訓(xùn)練，最后將強(qiáng)客戶(hù)端模型的特征層與弱客戶(hù)端的全連接層進(jìn)行模型重構(gòu)。為提高模型卸載效率，綜合考慮模型特征層的相似度與任務(wù)完成時(shí)間構(gòu)建了卸載成本矩陣，并將問(wèn)題轉(zhuǎn)換為迭代求解基于二部圖的最優(yōu)匹配問(wèn)題，提出基于Kuhn-Munkres（KM）的模型卸載算法并進(jìn)一步分析了Fed-MBMO算法的時(shí)間復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，在資源與數(shù)據(jù)極端異質(zhì)的情況下，該方法能夠加速模型收斂，模型訓(xùn)練時(shí)間與FedAvg、FedUE和Aergia相比分別平均減少46.65%、12.66%、38.07%。實(shí)驗(yàn)結(jié)果證明了所提的Fed-MBMO算法能夠有效解決“滯后者”效應(yīng)問(wèn)題并顯著提高聯(lián)邦學(xué)習(xí)效率。

關(guān)鍵詞：聯(lián)邦學(xué)習(xí)；滯后者效應(yīng)；模型卸載；強(qiáng)弱匹配；資源異質(zhì)性；模型重構(gòu)；邊緣計(jì)算

中圖分類(lèi)號(hào)：TP393"" 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2025）01-020-0139-10

doi： 10.19734/j.issn.1001-3695.2024.06.0199

Match-based model offloading for edge federated learning

Abstract：Aiming at problems such as the “straggler effect” caused by resource heterogeneity in federated learning in edge computing environments， this paper proposed a match-based model offloading for edge federated learning （Fed-MBMO） . This method collected performance analysis results of edge devices， divided devices into strong and weak clients， and considered the time proportion of the four phases of model training， weak clients saved the time of backpropagation on the feature layers by freezing part of the model， and offload the model to the strong client for additional training， finally， the strong clients’ feature layers were then reconstructed with the weak clients’ fully connected layers. In order to improve the efficiency of model offloading， the offloading cost matrix is constructed by comprehensively considering the similarity of model feature layers and task completion time， and transform the problem into an iterative solution of the optimal matching problem based on bipartite graph， the proposed approach used a KM-based model offloading algorithm and further analyzed the time complexity of the Fed-MBMO algorithm. Experimental results show that in the case of extremely heterogeneous resources and datasets， this method can accelerate model convergence， and the model training time can be reduced by an average of 46.65 percent， 12.66 percent and 38.07 percent compared to FedAvg， FedUE and Aergia， respectively. The experimental results show that the Fed-MBMO algorithm can effectively solve the “straggler effect ”problem and significantly improve the efficiency of federated learning.

Key words：federated learning; stragglers’ effect; model offloading; strong and weak matching; resource heterogeneity; model reconstruction; edge computing

0 引言

在如今的5G時(shí)代下，數(shù)億的物聯(lián)網(wǎng)（IoT）設(shè)備（如傳感器、攝像頭、智能手機(jī)）從環(huán)境中收集原始數(shù)據(jù)，并將數(shù)據(jù)上傳至云端處理，再通過(guò)互聯(lián)網(wǎng)進(jìn)行傳輸[1]。根據(jù)華為在2020年發(fā)布的《全球聯(lián)接指數(shù)白皮書(shū)》中指出的數(shù)據(jù)，到2025年終端設(shè)備的連接數(shù)量將會(huì)達(dá)到一千億之多，而物聯(lián)網(wǎng)帶來(lái)的經(jīng)濟(jì)附加值也會(huì)多達(dá)11.1 萬(wàn)億美元[2]。然而，集中式的云計(jì)算架構(gòu)如今面臨著巨大的挑戰(zhàn)，2025年物聯(lián)網(wǎng)設(shè)備將會(huì)產(chǎn)生79.4 ZB的數(shù)據(jù)，如此驚人的數(shù)據(jù)量需要大量的帶寬和計(jì)算資源，而邊緣計(jì)算能夠在更靠近數(shù)據(jù)產(chǎn)生源頭的網(wǎng)絡(luò)邊緣提供IT服務(wù)和云計(jì)算能力，用戶(hù)也可以享受超低延遲和高帶寬帶來(lái)的高質(zhì)量服務(wù)[3]。

物聯(lián)網(wǎng)的快速發(fā)展導(dǎo)致網(wǎng)絡(luò)邊緣生成的數(shù)據(jù)呈指數(shù)級(jí)增長(zhǎng)，集中式地處理數(shù)據(jù)在物聯(lián)網(wǎng)時(shí)代仍面臨極高的通信和存儲(chǔ)開(kāi)銷(xiāo)，也更加容易引發(fā)隱私泄露問(wèn)題，帶來(lái)數(shù)據(jù)安全隱患[4]。為應(yīng)對(duì)這一問(wèn)題，歐盟在2018年出臺(tái)了通用數(shù)據(jù)保護(hù)條例（GDPR）[5]，中國(guó)則于2021年通過(guò)了《個(gè)人信息保護(hù)法》。面對(duì)政策和法規(guī)的監(jiān)管，Google在2016年提出的聯(lián)邦學(xué)習(xí)（federated learning）則成為解決數(shù)據(jù)孤島和隱私問(wèn)題的最佳方案[6]。具體而言，它允許各參與方在不共享數(shù)據(jù)的前提下進(jìn)行合作建模，每個(gè)客戶(hù)端在本地訓(xùn)練模型，僅上傳模型參數(shù)至中央服務(wù)器，服務(wù)器加權(quán)聚合后生成全局模型，因此既保護(hù)隱私，又符合數(shù)據(jù)安全法規(guī)。

邊緣聯(lián)邦學(xué)習(xí)（edge federated learning）作為邊緣智能的一個(gè)分支，它將邊緣計(jì)算與聯(lián)邦學(xué)習(xí)相結(jié)合，能夠在大規(guī)模網(wǎng)絡(luò)和異構(gòu)設(shè)備中使用AI技術(shù)并進(jìn)行通信，是一種能夠在多個(gè)邊緣設(shè)備中訓(xùn)練機(jī)器學(xué)習(xí)模型的有效方法[7，8]。隨著邊緣設(shè)備傳感能力和計(jì)算能力的顯著提高，許多物聯(lián)網(wǎng)設(shè)備可以在網(wǎng)絡(luò)邊緣中對(duì)數(shù)據(jù)進(jìn)行預(yù)測(cè)和分類(lèi)，聯(lián)邦學(xué)習(xí)這一技術(shù)則可以使客戶(hù)端在不交換原始數(shù)據(jù)的條件下完成訓(xùn)練，例如在智能醫(yī)療保健中涉及敏感數(shù)據(jù)，對(duì)于可穿戴設(shè)備用戶(hù)例如智能手表，他們需要在設(shè)備上訓(xùn)練模型，用于預(yù)測(cè)心臟病發(fā)作等情況[9]?；蛘咭患軣o(wú)人機(jī)可以觀察來(lái)往車(chē)輛進(jìn)行訓(xùn)練，通過(guò)聯(lián)邦學(xué)習(xí)的方法，其他無(wú)人機(jī)無(wú)須觀察車(chē)輛即可學(xué)習(xí)到相關(guān)的特征[10]。

然而，物聯(lián)網(wǎng)設(shè)備的異構(gòu)特性降低了模型訓(xùn)練的效率[11]。連接到聯(lián)邦學(xué)習(xí)中央服務(wù)器的物聯(lián)網(wǎng)設(shè)備可能具有不同的計(jì)算能力，這些因計(jì)算能力較弱需要長(zhǎng)時(shí)間進(jìn)行訓(xùn)練的設(shè)備，稱(chēng)為“滯后者”（stragglers）[11～17]。目前，大多數(shù)聯(lián)邦學(xué)習(xí)的實(shí)現(xiàn)依賴(lài)于同步訓(xùn)練來(lái)確保良好的收斂性能，同步訓(xùn)練要求服務(wù)器在所有設(shè)備都完成訓(xùn)練后才能將客戶(hù)端的模型加權(quán)聚合。因此，中央服務(wù)器必須等待最慢的設(shè)備完成訓(xùn)練，在這種情況下，隨著計(jì)算能力差異和集群規(guī)模的增加，總訓(xùn)練時(shí)間的延遲將逐漸擴(kuò)大。減少訓(xùn)練時(shí)間在邊緣聯(lián)邦學(xué)習(xí)領(lǐng)域意義重大。例如在車(chē)載智能設(shè)備中，邊緣智能設(shè)備中的聯(lián)邦學(xué)習(xí)模型可以用于識(shí)別道路上的障礙物、行人和其他車(chē)輛等信息。通過(guò)減少訓(xùn)練時(shí)間，模型可以更快地適應(yīng)新的交通狀況，從而提高實(shí)時(shí)響應(yīng)速度，降低事故風(fēng)險(xiǎn)[18]。在可穿戴設(shè)備中，健康檢測(cè)設(shè)備可以更快地檢測(cè)健康風(fēng)險(xiǎn)，并及時(shí)提供醫(yī)療建議[9]。另一方面，由于物聯(lián)網(wǎng)設(shè)備的功能和采樣頻率存在差異，這些設(shè)備間的數(shù)據(jù)通常是非獨(dú)立同分布的（non-independent and identically distri-buted，Non-IID）[19，20]。這種Non-IID帶來(lái)的統(tǒng)計(jì)異質(zhì)性挑戰(zhàn)會(huì)顯著影響邊緣聯(lián)邦學(xué)習(xí)的準(zhǔn)確性。

減少滯后者的訓(xùn)練時(shí)間對(duì)于提高訓(xùn)練效率，增強(qiáng)用戶(hù)體驗(yàn)，提升實(shí)時(shí)應(yīng)用的可擴(kuò)展性至關(guān)重要。因此，為了加速在資源和數(shù)據(jù)異構(gòu)的物聯(lián)網(wǎng)下的聯(lián)邦學(xué)習(xí)訓(xùn)練過(guò)程，本文提出了一種基于匹配的模型卸載邊緣聯(lián)邦學(xué)習(xí)方法（Fed-MBMO）。首先，通過(guò)在不同CNN上注冊(cè)Hook回調(diào)計(jì)時(shí)函數(shù)，本文分析了神經(jīng)網(wǎng)絡(luò)模型在不同階段的耗時(shí)比例，基于此分析，提出凍結(jié)弱客戶(hù)端的特征層以節(jié)省反向傳播的時(shí)間。此外，提出簡(jiǎn)單高效的滯后者鑒別方法，該方法根據(jù)模型訓(xùn)練速度將客戶(hù)端劃分為強(qiáng)客戶(hù)端和弱客戶(hù)端，并基于此為每個(gè)客戶(hù)端制定模型卸載策略。最后，將模型卸載問(wèn)題建模為基于二部圖的強(qiáng)弱匹配問(wèn)題，以提高異構(gòu)物聯(lián)網(wǎng)環(huán)境下的聯(lián)邦學(xué)習(xí)訓(xùn)練效率，本文具體貢獻(xiàn)如下：

a）提出模型卸載策略以減輕“滯后者”效應(yīng)。指出計(jì)算能力較弱的邊緣設(shè)備是邊緣聯(lián)邦學(xué)習(xí)訓(xùn)練效率的瓶頸。通過(guò)分析模型訓(xùn)練的四個(gè)階段，采用凍結(jié)模型的方法省去反向傳播特征層階段，從而減少“滯后者”的訓(xùn)練時(shí)間，顯著提高聯(lián)邦系統(tǒng)訓(xùn)練的效率。

b）設(shè)計(jì)基于二部圖的強(qiáng)弱匹配算法。通過(guò)運(yùn)行性能分析程序，將客戶(hù)端劃分為強(qiáng)客戶(hù)端和弱客戶(hù)端，并將問(wèn)題建模為基于二部圖的最優(yōu)匹配問(wèn)題。根據(jù)任務(wù)完成時(shí)間與模型特征層相似度構(gòu)建成本矩陣，尋找最優(yōu)匹配，并減少極弱客戶(hù)端的訓(xùn)練量。該算法能夠綜合考慮預(yù)期完成時(shí)間與全局模型精度，優(yōu)化訓(xùn)練過(guò)程。

c）通過(guò)模擬實(shí)驗(yàn)驗(yàn)證算法的有效性。采用Docker容器化技術(shù)和分布式并行訓(xùn)練框架對(duì)邊緣聯(lián)邦學(xué)習(xí)進(jìn)行模擬實(shí)驗(yàn)。對(duì)比分析了權(quán)重參數(shù)與CPU設(shè)置對(duì)算法性能的影響。實(shí)驗(yàn)結(jié)果表明，所提方法在保證精度的前提下，有效減少“滯后者”訓(xùn)練時(shí)間，基于KM算法的迭代匹配算法能夠平衡預(yù)期完成時(shí)間與全局模型精度的要求，并在Non-IID條件下有不錯(cuò)表現(xiàn)。

1 相關(guān)工作

現(xiàn)代物聯(lián)網(wǎng)設(shè)備的傳感器每天會(huì)實(shí)時(shí)監(jiān)測(cè)并產(chǎn)生大量的數(shù)據(jù)。例如自動(dòng)駕駛汽車(chē)需要構(gòu)建交通模型以確保安全運(yùn)行。用于預(yù)測(cè)心臟病發(fā)作等健康風(fēng)險(xiǎn)的可穿戴設(shè)備[9]，隨著人們對(duì)個(gè)性化建模和保護(hù)用戶(hù)隱私需求的增加，McMahan等人[6]提出了聯(lián)邦學(xué)習(xí)這一方法，而分布式網(wǎng)絡(luò)設(shè)備的計(jì)算和存儲(chǔ)能力的增長(zhǎng)，為聯(lián)邦學(xué)習(xí)的實(shí)施提供了支持。

然而，將聯(lián)邦學(xué)習(xí)應(yīng)用到實(shí)際的邊緣設(shè)備上訓(xùn)練時(shí)會(huì)出現(xiàn)一個(gè)嚴(yán)重的問(wèn)題，即“滯后者”效應(yīng)（如圖1所示）。當(dāng)服務(wù)器將相同結(jié)構(gòu)的模型和相同的工作負(fù)載部署到異構(gòu)設(shè)備時(shí)，由于這些設(shè)備的計(jì)算資源（例如CPU/GPU頻率、內(nèi)存大小等）不同，在計(jì)算能力較弱的設(shè)備上進(jìn)行局部訓(xùn)練將花費(fèi)更長(zhǎng)時(shí)間。雖然單純地將“滯后者”排除出訓(xùn)練可以在一定程度上緩解這一問(wèn)題，但“滯后者”往往保留著不同的數(shù)據(jù)集，這些數(shù)據(jù)集中可能包含獨(dú)特和關(guān)鍵的特征，直接丟棄會(huì)損壞全局模型性能[21]，因此，通過(guò)減少“滯后者”效應(yīng)，全局模型性能也會(huì)受益[22]。

針對(duì)此問(wèn)題，現(xiàn)有研究提出了多種解決方案。Ji等人[23]提出邊緣輔助聯(lián)邦學(xué)習(xí)（EAFL），提出將“滯后者”部分計(jì)算卸載到邊緣服務(wù)器并利用其強(qiáng)大的計(jì)算能力輔助訓(xùn)練?！皽笳摺蓖ㄟ^(guò)上傳一定量的數(shù)據(jù)來(lái)減少模型更新延遲。服務(wù)器首先分析客戶(hù)端的信道狀態(tài)信息（CSI），并將其建模為基于閾值的延遲最小化問(wèn)題。隨后，作者將非凸問(wèn)題解耦為凸問(wèn)題并求解以確定客戶(hù)端應(yīng)上傳的數(shù)據(jù)量。EAFL在一定程度上緩解了“滯后者”效應(yīng)，但作者假設(shè)完美信道狀態(tài)信息并不現(xiàn)實(shí)，且卸載策略的求解時(shí)間過(guò)長(zhǎng)，上傳數(shù)據(jù)量的做法也違背了聯(lián)邦學(xué)習(xí)保護(hù)數(shù)據(jù)隱私的初衷。Chai等人[24]提出基于層的聯(lián)邦學(xué)習(xí)（TIFL），通過(guò)自適應(yīng)地選擇每輪訓(xùn)練時(shí)間相似的客戶(hù)端，根據(jù)分析的訓(xùn)練時(shí)間對(duì)設(shè)備進(jìn)行分組，基于TIFL的自適應(yīng)客戶(hù)端選擇算法從同一層中隨機(jī)選擇客戶(hù)端。雖然TIFL通過(guò)選擇具有相似訓(xùn)練時(shí)間的客戶(hù)端，減輕了資源異質(zhì)性的問(wèn)題，但是采用隨機(jī)選擇的策略，無(wú)視了組內(nèi)客戶(hù)端之間數(shù)據(jù)分布的差異，影響了全局模型的精度。

通過(guò)分析發(fā)現(xiàn)滯后者效應(yīng)的本質(zhì)是時(shí)間發(fā)散問(wèn)題，減少每一輪中客戶(hù)端的時(shí)間發(fā)散就會(huì)減輕滯后者效應(yīng)，Zang等人[15]提出了一種基于用戶(hù)設(shè)備物理屬性的分組方法，并抽取同組內(nèi)的客戶(hù)端，但是此方法會(huì)導(dǎo)致客戶(hù)端等待時(shí)間不穩(wěn)定。而Zeng等人[14]提出深度強(qiáng)化學(xué)習(xí)方法來(lái)學(xué)習(xí)網(wǎng)絡(luò)條件和客戶(hù)端的能力，并為訓(xùn)練強(qiáng)度較低（較高）的客戶(hù)端分配較少（更多）的本地訓(xùn)練輪次。同樣作為減少訓(xùn)練量的做法，Guo等人[13]提出FedCore，以分布式的方式直接在每個(gè)客戶(hù)端上創(chuàng)建核心集，并把將核心集優(yōu)化問(wèn)題轉(zhuǎn)為更易處理的K-medoids聚類(lèi)問(wèn)題。

Cox等人[25]提出凍結(jié)慢客戶(hù)端模型并將其傳遞給計(jì)算資源更豐富的客戶(hù)端進(jìn)行訓(xùn)練的方法（Aergia）。但是作者僅考慮數(shù)據(jù)集的標(biāo)簽分布之間的EMD距離來(lái)衡量數(shù)據(jù)集間的相似度，忽略了其他的Non-IID類(lèi)型，如特征分布偏斜、數(shù)量偏斜等[26]。Aergia上傳數(shù)據(jù)集標(biāo)簽分布至Intel SGX飛地，但是此項(xiàng)技術(shù)難以大規(guī)模應(yīng)用，且數(shù)據(jù)集分布在一定程度上仍然會(huì)泄露隱私。許多研究通過(guò)異步聚合減輕“滯后者”效應(yīng)[12，27]，客戶(hù)端可以獨(dú)立異步地進(jìn)行通信和模型更新，其中Zhang等人[27]提出異步并行聯(lián)邦學(xué)習(xí)機(jī)制（Asynchronous PFL），指出訓(xùn)練效率低下的原因在于服務(wù)器依賴(lài)所有客戶(hù)端上傳的本地更新，以及客戶(hù)端依賴(lài)服務(wù)器全局聚合后的模型，為了提高訓(xùn)練效率，邊緣設(shè)備的本地訓(xùn)練過(guò)程和中心服務(wù)器的聚合應(yīng)同時(shí)進(jìn)行。然而“滯后者”過(guò)長(zhǎng)的本地訓(xùn)練時(shí)間才是降低訓(xùn)練效率的主要原因。雖然異步訓(xùn)練確實(shí)減輕了“滯后者”效應(yīng)，但是也會(huì)造成全局模型的僵化，并導(dǎo)致全局模型向更新頻率更高的邊緣設(shè)備偏斜[13，14，28]。

基于上述研究，本文設(shè)計(jì)了一種基于匹配的模型卸載邊緣聯(lián)邦學(xué)習(xí)方法，針對(duì)邊緣計(jì)算環(huán)境下聯(lián)邦學(xué)習(xí)中出現(xiàn)的“滯后者”效應(yīng)問(wèn)題，提出了一種高效鑒別“滯后者”的方法。該方法將所有設(shè)備劃分為強(qiáng)、弱客戶(hù)端，并建立一個(gè)基于二部圖的強(qiáng)、弱匹配問(wèn)題，構(gòu)建任務(wù)完成時(shí)間及特征層相似度的成本矩陣，結(jié)合二分查找和KM算法迭代求解最優(yōu)匹配，制定相應(yīng)的卸載策略，在資源與數(shù)據(jù)極端異質(zhì)的環(huán)境下提高聯(lián)邦系統(tǒng)訓(xùn)練效率的同時(shí)保證了全局模型精度。

2 系統(tǒng)模型

在傳統(tǒng)聯(lián)邦學(xué)習(xí)架構(gòu)中，如圖1所示，多個(gè)客戶(hù)端連接到一個(gè)中央服務(wù)器。服務(wù)器首先將模型廣播至邊緣設(shè)備，然而由于不同邊緣設(shè)備具有不同的底層硬件架構(gòu)和軟件實(shí)現(xiàn)，所以完成相同任務(wù)量的模型訓(xùn)練所需要的時(shí)間也有所不同。有研究表明，解決“滯后者”效應(yīng)的瓶頸已從通信階段轉(zhuǎn)到移動(dòng)設(shè)備的計(jì)算能力上[29]。因此，本文假設(shè)客戶(hù)端之間能夠相互通信，其帶寬和通信延遲保持穩(wěn)定，并且客戶(hù)端都是誠(chéng)實(shí)的。

2.1 邊緣聯(lián)邦學(xué)習(xí)框架

聯(lián)邦學(xué)習(xí)的目標(biāo)是在邊緣設(shè)備上的數(shù)據(jù)集學(xué)習(xí)一個(gè)全局模型，通過(guò)與中央服務(wù)器定期通信更新全局模型，目標(biāo)通常是最小化目標(biāo)函數(shù)：

但是由于系統(tǒng)中會(huì)存在許多計(jì)算能力較弱的慢速設(shè)備（以下稱(chēng)為弱客戶(hù)端）。當(dāng)所有客戶(hù)端執(zhí)行相同小批量的訓(xùn)練后，其性能分析結(jié)果會(huì)發(fā)送至服務(wù)器，服務(wù)器根據(jù)其性能分析結(jié)果將所有客戶(hù)端劃分為強(qiáng)客戶(hù)端和弱客戶(hù)端。設(shè)C=C1，C2，…，Cn為所有參與聯(lián)邦學(xué)習(xí)的邊緣設(shè)備的集合，n為客戶(hù)端總數(shù)?？蛻?hù)端被劃分為強(qiáng)、弱客戶(hù)端S=Cs1，Cs2，…，CsS和W=Cw1，Cw2，…，CwW，其中S∩W=。

2.2 模型訓(xùn)練階段

本文模型采用卷積神經(jīng)網(wǎng)絡(luò)（CNN），卷積神經(jīng)網(wǎng)絡(luò)由提取特征的卷積層與起“分類(lèi)器”作用的全連接層構(gòu)成。每當(dāng)小批量的數(shù)據(jù)集進(jìn)入網(wǎng)絡(luò)訓(xùn)練時(shí)，需要經(jīng)過(guò)以下四個(gè)階段：a）前向傳播卷積層（FF）；b）前向傳播全連接層（FC）；c）反向傳播全連接層（BC）；d）反向傳播卷積層（BF）。如圖2所示。

前向傳播是指數(shù)據(jù)輸入通過(guò)網(wǎng)絡(luò)的各層逐層傳遞，經(jīng)過(guò)權(quán)重和激活函數(shù)的計(jì)算，最終產(chǎn)生輸出結(jié)果的過(guò)程。反向傳播則是一種通過(guò)逆向計(jì)算梯度信息以更新網(wǎng)絡(luò)參數(shù)的優(yōu)化算法，目的是最小化預(yù)測(cè)值與實(shí)際值之間的差距。通過(guò)在不同數(shù)據(jù)集上的CNN注冊(cè)捕獲時(shí)間的Hook計(jì)時(shí)函數(shù)，測(cè)量四個(gè)階段耗費(fèi)的時(shí)間，發(fā)現(xiàn)第四階段反向傳播卷積層是最為耗時(shí)的，占總訓(xùn)練時(shí)間的比例高達(dá)52.02%～59.56%，如圖3所示。

2.3 問(wèn)題建模

設(shè)客戶(hù)端k的待執(zhí)行訓(xùn)練的小批量數(shù)目為SRBk，對(duì)一個(gè)小批量數(shù)據(jù)完成一次訓(xùn)練的四個(gè)階段耗時(shí)為

tk=tFFk+tFCk+tBCk+tBFk（2）

弱客戶(hù)端省去耗時(shí)最長(zhǎng)的BF階段，其耗時(shí)變化為t′k=tk－tBFk。則凍結(jié)模型后的弱客戶(hù)端w的一輪本地訓(xùn)練總時(shí)間為T(mén)w=tw·sd+t′w·ss，其中sd為弱客戶(hù)端w在本地完整訓(xùn)練的小批量數(shù)，ss為模型凍結(jié)后僅訓(xùn)練前三個(gè)階段的小批量數(shù)。輔助弱客戶(hù)端w訓(xùn)練的強(qiáng)客戶(hù)端s的本地訓(xùn)練時(shí)間為T(mén)s=ts·SRBs+ts·re，其中ts·SRBs為強(qiáng)客戶(hù)端本地訓(xùn)練的時(shí)間， ts·re為接收到弱客戶(hù)端w卸載的模型后進(jìn)行額外訓(xùn)練的時(shí)間。為減少訓(xùn)練時(shí)間的同時(shí)保證客戶(hù)端訓(xùn)練量以提高模型精度，設(shè)匹配運(yùn)行時(shí)間Tmedianw，s為相互匹配的強(qiáng)、弱客戶(hù)端原運(yùn)行時(shí)間的中值：

為提高訓(xùn)練效果，強(qiáng)弱客戶(hù)端都應(yīng)在指定運(yùn)行終止時(shí)間內(nèi)“盡力而為”，弱客戶(hù)端應(yīng)在完成所有批次數(shù)據(jù)訓(xùn)練的條件下盡可能多地完成完整的訓(xùn)練，強(qiáng)客戶(hù)端盡可能幫助弱客戶(hù)端在本地?cái)?shù)據(jù)集上進(jìn)行模型訓(xùn)練。在提高訓(xùn)練效率的同時(shí)保證模型的訓(xùn)練效果，因此弱客戶(hù)端w需要調(diào)整sd與ss的比例以達(dá)到Tmedianw，s時(shí)間限制要求，而強(qiáng)客戶(hù)端s需要輔助w額外執(zhí)行re數(shù)目的小批量訓(xùn)練。因此，一對(duì)強(qiáng)弱客戶(hù)端（w，s）的模型卸載策略（sd，ss，re）可表示成以下問(wèn)題：

s∈S）}，M為所有可行匹配的集合，為最小化一輪訓(xùn)練的時(shí)間，需要尋找一個(gè)匹配使得最小化最遲完成時(shí)間，即：

問(wèn)題式（9）需要在一個(gè)可行匹配的集合M中尋找一個(gè)最優(yōu)匹配m使得一輪的聯(lián)邦學(xué)習(xí)時(shí)間最短，則問(wèn)題式（9）轉(zhuǎn)換為在最小化最大任務(wù)完成時(shí)間的同時(shí)，最小化相互匹配的客戶(hù)端之間的模型相似度差異，問(wèn)題目標(biāo)為

其中：α∈［0，1］；Scale為最大最小歸一化函數(shù)。

問(wèn)題的難點(diǎn)在于最小化最大完成時(shí)間的同時(shí)，最小化匹配客戶(hù)端之間模型特征層相似度的差異。由于完成時(shí)間項(xiàng)不是一個(gè)累加值，無(wú)法用已有的算法直接進(jìn)行最優(yōu)匹配求解。

為解決上述問(wèn)題，接下來(lái)將回答以下關(guān)鍵問(wèn)題：

a）如何鑒別系統(tǒng)中的滯后者以及合理地劃分強(qiáng)、弱客戶(hù)端？

b）弱客戶(hù)端模型卸載的具體流程是什么，強(qiáng)客戶(hù)端如何協(xié)助弱客戶(hù)端進(jìn)行額外訓(xùn)練？

c）如何尋找最少的任務(wù)完成時(shí)間和與其相應(yīng)最小的成本之和的匹配，并分析Fed-MBMO算法的時(shí)間復(fù)雜度？

3 客戶(hù)端劃分和模型卸載策略

為了鑒別“滯后者”，本文提出一種性能分析方法。邊緣設(shè)備通過(guò)執(zhí)行相同任務(wù)量的訓(xùn)練，并統(tǒng)計(jì)完成時(shí)間。服務(wù)器收集到完成時(shí)間后能夠了解各個(gè)邊緣設(shè)備的計(jì)算能力，從而識(shí)別拖慢整個(gè)聯(lián)邦學(xué)習(xí)過(guò)程的“滯后者”。

具體地，服務(wù)器隨機(jī)選擇邊緣設(shè)備加入邊緣聯(lián)邦學(xué)習(xí)，并將全局模型發(fā)送至邊緣設(shè)備。首先邊緣設(shè)備需在本地模型上注冊(cè)Hook回調(diào)計(jì)時(shí)函數(shù)，每當(dāng)客戶(hù)端對(duì)最后一層卷積層求導(dǎo)和前向傳播時(shí)第一層全連接層時(shí)，都會(huì)進(jìn)行計(jì)時(shí)。在執(zhí)行固定數(shù)量的小批量訓(xùn)練（本文中設(shè)定為100次mini-batches）后，邊緣設(shè)備可以分別統(tǒng)計(jì)FF，F(xiàn)C，BC，BF階段平均耗時(shí)，并將性能分析結(jié)果包含模型參數(shù)發(fā)送至服務(wù)器進(jìn)行分析，以便作出決策。

服務(wù)器在獲取所有被選邊緣設(shè)備的性能分析結(jié)果后，計(jì)算其預(yù)期剩余運(yùn)行時(shí)間，并由此得出中值運(yùn)算時(shí)間（median compute time，MCT）。預(yù)期剩余運(yùn)行時(shí)間小于等于MCT的客戶(hù)端為強(qiáng)客戶(hù)端，而預(yù)期運(yùn)行時(shí)間大于MCT的客戶(hù)端則被定義為弱客戶(hù)端，即“滯后者”。Aergia[25]將平均運(yùn)算時(shí)間當(dāng)作目標(biāo)完成時(shí)間容易造成弱客戶(hù)端遺漏，中值在邊緣設(shè)備計(jì)算能力分布偏斜的情況下更能反映大多數(shù)邊緣設(shè)備的典型計(jì)算能力。因此，本文將MCT當(dāng)作劃分強(qiáng)、弱客戶(hù)端的標(biāo)準(zhǔn)。

根據(jù)式（4）可得出，強(qiáng)弱客戶(hù)端都需接近其匹配運(yùn)行時(shí)間Tmedianw，s，弱客戶(hù)端需要凍結(jié)模型特征層并停止反向傳播階段（BF階段），以此節(jié)省訓(xùn)練時(shí)間，并將模型卸載至強(qiáng)客戶(hù)端。強(qiáng)客戶(hù)端在收到卸載的模型后，繼續(xù)在此模型上進(jìn)行額外的訓(xùn)練。然而本文在實(shí)驗(yàn)中發(fā)現(xiàn)，即使某些弱客戶(hù)端在接收到服務(wù)器指令后立即凍結(jié)模型特征層，它們?nèi)匀粫?huì)拖慢整個(gè)訓(xùn)練進(jìn)程，即某些弱客戶(hù)端節(jié)省所有剩余待執(zhí)行訓(xùn)練的小批量的BF階段后仍然會(huì)成為整個(gè)系統(tǒng)的效率短板，因此將這種弱客戶(hù)端定義為極弱客戶(hù)端。

算法1 臨近卸載點(diǎn)算法（approach offloading point algorithm）

如算法1第4行所示，弱客戶(hù)端需要逐步增加凍結(jié)模型的訓(xùn)練次數(shù)、減少模型完整訓(xùn)練的部分，直至弱客戶(hù)端預(yù)期訓(xùn)練時(shí)間小于匹配運(yùn)行時(shí)間Tmedianw，s，以滿(mǎn)足時(shí)間限制的要求。如圖4所示，弱客戶(hù)端B若要卸載模型到強(qiáng)客戶(hù)端C時(shí)，需要在運(yùn)行sd個(gè)小批量的完整訓(xùn)練后，凍結(jié)模型以達(dá)到TmedianB，C時(shí)間限制。盡管模型凍結(jié)的方法加快了弱客戶(hù)端的訓(xùn)練速度，節(jié)約了弱客戶(hù)端的計(jì)算資源和成本，但這會(huì)對(duì)其本地模型造成損傷，最終導(dǎo)致降低全局模型精度。因此，弱客戶(hù)端的模型需要在凍結(jié)后卸載至強(qiáng)客戶(hù)端進(jìn)行額外訓(xùn)練，如圖4強(qiáng)客戶(hù)端C所示，需協(xié)助B執(zhí)行額外的訓(xùn)練。并且強(qiáng)客戶(hù)端的額外訓(xùn)練時(shí)間也需受到Tmedianw，s的限制，如算法第10～14行所示，強(qiáng)客戶(hù)端需要逐步迭代得出額外的訓(xùn)練次數(shù)。值得注意的是，極弱客戶(hù)端即使凍結(jié)剩余的全部訓(xùn)練，仍然會(huì)拖慢效率，因此需要縮減訓(xùn)練量，而縮減比例shrink為T(mén)medianw，s與其預(yù)期運(yùn)行時(shí)間之比，以此減少任務(wù)量，所以shrinklt;1。

最后返回預(yù)期運(yùn)行時(shí)間、凍結(jié)批量數(shù)、額外訓(xùn)練批量數(shù)等信息。

4 基于最優(yōu)匹配的模型卸載方法

針對(duì)式（11）完成時(shí)間項(xiàng)不是個(gè)累計(jì)值，因此無(wú)法用已有算法直接求解的問(wèn)題，本章提出了一種基于KM算法的迭代匹配算法，在最小化最大完成時(shí)間的同時(shí)，最小化匹配客戶(hù)端之間模型特征層相似度的差異。

4.1 基于KM算法的迭代匹配算法

為解決問(wèn)題式（11），引入KM算法尋找最優(yōu)匹配，引入基于二分查找的迭代解決最小化任務(wù)完成時(shí)間的問(wèn)題。

在最大最小歸一化完成之后，所有的任務(wù)完成時(shí)間與余弦相似度均歸一到0～1內(nèi)。因此，需構(gòu)建最大任務(wù)完成時(shí)間與總相似度加權(quán)之和的卸載成本函數(shù)：

Cost（w，s）=α·z+（1－α）·Scale（Simw，s）（17）

其中：0≤z≤1，根據(jù)輔助變量z構(gòu)建式（18）的成本矩陣COST，求解最優(yōu)匹配m，判斷匹配m中所有客戶(hù)端的預(yù)期訓(xùn)練時(shí)間是否都符合Tm≤z·Tmmax－Tmmin+Tmmin。盡管有研究指出客戶(hù)端數(shù)據(jù)集的標(biāo)簽分布之間的EMD距離與全局模型的測(cè)試精度成反比[19]，Aergia也因此將其作為平衡模型精度與計(jì)算時(shí)間的參考因素，但是模型的重構(gòu)則會(huì)打破這一規(guī)則，全局模型的測(cè)試精度也會(huì)受到一定程度的影響。因此二分查找需在逐漸逼近最短運(yùn)行時(shí)間的同時(shí)，最大化模型特征層之間的相似度。

則基于匹配的模型卸載問(wèn)題可以轉(zhuǎn)為基于二分查找的最優(yōu)匹配問(wèn)題。

算法2 二分搜索成本構(gòu)建算法（binary-search construct cost algorithm，BSCC）

輸入：預(yù)期運(yùn)行時(shí)間矩陣CT；模型特征層相似度矩陣SIM；時(shí)間輔助變量z;收斂參數(shù)ε。

輸出：匹配m。

4.2 基于KM算法的匹配

若頂點(diǎn)V可分割為兩個(gè)互不相交的子集，并且圖中的每條邊依附的兩個(gè)頂點(diǎn)分屬于這兩個(gè)互不相交的子集，則此無(wú)向圖為二部圖。在本文中，弱客戶(hù)端在收到服務(wù)器的卸載指令后需要執(zhí)行sd數(shù)量的小批量訓(xùn)練，再將模型特征層進(jìn)行凍結(jié)，以節(jié)省本地訓(xùn)練時(shí)在特征層中反向傳播的時(shí)間，極弱客戶(hù)端還需進(jìn)一步減少訓(xùn)練量。在凍結(jié)的同時(shí)，弱客戶(hù)端還需直接與強(qiáng)客戶(hù)端建立通信，將模型卸載至強(qiáng)客戶(hù)端進(jìn)行re數(shù)量小批量的額外訓(xùn)練。因此，模型卸載只發(fā)生在弱客戶(hù)端與強(qiáng)客戶(hù)端之間，并且W∩S=，所以可以將客戶(hù)端及其卸載模型的行為建模為帶權(quán)二部圖的形式。

服務(wù)器的主要目標(biāo)就是通過(guò)正確匹配強(qiáng)弱客戶(hù)端以提高訓(xùn)練效率，從而在保證訓(xùn)練效率的同時(shí)最大限度地減少客戶(hù)端數(shù)據(jù)集之間的異質(zhì)性。具體流程如算法3所示。

算法3 KM-匹配算法（KM-match algotrithm）

定義1 可行頂標(biāo)。給集合W，S中的每個(gè)弱、強(qiáng)客戶(hù)端分別分配一個(gè)權(quán)值uw、vs，對(duì)于所有的邊都滿(mǎn)足Cost（w，s）≤uw+vs。

定義2 相等子圖。在一組可行頂標(biāo)下原圖的生成子圖，包含所有的點(diǎn)但只包含滿(mǎn)足Cost（w，s）=uw+vs的邊。

定義3 頂點(diǎn)覆蓋。圖的一個(gè)頂點(diǎn)覆蓋是由一些頂點(diǎn)構(gòu)成的集合，它使得圖中的每條邊上至少有一個(gè)頂點(diǎn)屬于這個(gè)集合。

定義4 最大匹配。匹配是一組兩兩沒(méi)有公共點(diǎn)的邊集，最大匹配是指匹配邊數(shù)量最多的匹配。

該算法首先對(duì)傳入的成本矩陣COST中的可行頂標(biāo)進(jìn)行初始化，規(guī)則是對(duì)每個(gè)弱客戶(hù)端頂標(biāo)置為與其相連的所有邊的權(quán)重中的最大值，強(qiáng)客戶(hù)端頂標(biāo)全部置為0，并初始化原圖的相等子圖為G，直至G的最大匹配為完美匹配時(shí)，迭代停止。在權(quán)值均為有理數(shù)的情況下，迭代有限次數(shù)的KM算法必然能停止。本文中需要尋找一個(gè)匹配m使得其成本之和最小，為方便處理，需要對(duì)COST矩陣進(jìn)行reverse處理。具體地，找到矩陣中最大的元素，并用其對(duì)每個(gè)元素進(jìn)行相減。

完成初始化后，弱、強(qiáng)客戶(hù)端W和S分別為矩陣的行和列，其中成本矩陣COST中弱客戶(hù)端w與強(qiáng)客戶(hù)端s的成本為Cost（w，s），兩頂標(biāo)之和與其成本相減uw+vs－Cost（w，s）得到的差額DM（w，s），所有差額構(gòu)成差額矩陣DM。其中，相等子圖中的邊對(duì)應(yīng)的是差額矩陣中的0元素。標(biāo)記出差額矩陣的0元素，并畫(huà)出對(duì)應(yīng)的相等子圖G，找出相等子圖G中的頂點(diǎn)覆蓋Q，Q中屬于弱客戶(hù)端的頂點(diǎn)覆蓋為Euclid Math OneRAp，屬于強(qiáng)客戶(hù)端的頂點(diǎn)覆蓋為Euclid Math OneTAp。在相等子圖G中標(biāo)記分屬于Euclid Math OneRAp和Euclid Math OneTAp的頂點(diǎn)，計(jì)算未被覆蓋的行或列中的最小差額中的最小值ε，并將不屬于Euclid Math OneTAp的行標(biāo)簽uw減去ε和屬于Euclid Math OneTAp的列標(biāo)簽vs加上ε。一直迭代直到相等子圖G有一個(gè)原圖的完美匹配，停止迭代，返回匹配結(jié)果m。

服務(wù)器完成最優(yōu)匹配后，得到了在最少任務(wù)完成時(shí)間下所有弱客戶(hù)端卸載模型至強(qiáng)客戶(hù)端后成本最小的匹配。最后，服務(wù)器需要將匹配結(jié)束后的指令發(fā)送回各個(gè)邊緣設(shè)備。根據(jù)臨近卸載點(diǎn)算法的結(jié)果，邊緣設(shè)備中的“滯后者”則需在執(zhí)行完sd輪小批量數(shù)的完整階段的模型更新后，將模型發(fā)送至服務(wù)器指定的強(qiáng)客戶(hù)端，并把模型凍結(jié)，執(zhí)行簡(jiǎn)化后的本地訓(xùn)練。此外，若被服務(wù)器判斷為極弱客戶(hù)端，則需縮減本地訓(xùn)練量到shrink倍。而邊緣設(shè)備中的強(qiáng)客戶(hù)端在接收到“滯后者”發(fā)送的模型后，需協(xié)助“滯后者”執(zhí)行額外的re輪小批量訓(xùn)練，訓(xùn)練完畢后需將額外的訓(xùn)練模型返送至對(duì)應(yīng)的弱客戶(hù)端，弱客戶(hù)端將額外訓(xùn)練的模型中的特征層與自身本地模型中的全連接層進(jìn)行重構(gòu)，得到弱客戶(hù)端的模型，最后進(jìn)行聯(lián)邦平均，完成一輪完整的全局訓(xùn)練。

4.3 基于匹配的模型卸載算法

結(jié)合上述的三個(gè)算法，算法4完整地展示了基于模型卸載的強(qiáng)弱匹配算法。

算法4 基于匹配的模型卸載算法（KM-based model offloading algorithm，MBMO）

輸入：消息封裝message；權(quán)重α；時(shí)間輔助變量z；收斂參數(shù)ε。

1 //服務(wù)器執(zhí)行：

2 for each client∈C in parallel do

3 ""接收客戶(hù)端client性能分析結(jié)果的消息封裝message

4 end for

5 初始化SIM，CT矩陣

6 for each weak w∈W do

7 ""for each strong s∈S do

8 """"ct，sd，ss，re，shrink=ApproachOffloadingPoint（message）

9 """"計(jì)算w與s模型特征層余弦相似度Sim（w，s）

10 ""end for

11 end for

12 生成SIM，CT矩陣

13 匹配集合m=BSCC（CT，SIM，z，ε）

14 發(fā)送匹配結(jié)果m，sd，shrink至弱客戶(hù)端for client∈W

15 發(fā)送匹配結(jié)果m，re ，shrink至強(qiáng)客戶(hù)端for client∈S

16 //客戶(hù)端執(zhí)行：

17 執(zhí)行性能分析程序，并將分析結(jié)果message發(fā)送至服務(wù)器

18 接收匹配結(jié)果m，sd，re，shrink

19 if client∈W

20 ""for i=1 to all_minibatches do

21 """"if sd==0 and i==all_minibatches*shrink

22 """"""then 停止訓(xùn)練 end if

23 """"if ilt;sd

24 """"""then 完整的本地批次訓(xùn)練

25 """"else if i==sd then凍結(jié)模型特征層，發(fā)送模型至匹配m中指定的強(qiáng)客戶(hù)端s

26 nbsp;"""else 執(zhí)行簡(jiǎn)化后的本地批次訓(xùn)練 end if

27 ""end for

28 end if

29 //等待強(qiáng)客戶(hù)端s接收模型

30 從強(qiáng)客戶(hù)端s接收模型，模型重構(gòu)

31 if client∈S

32 ""for i=1 to all_minibatches do

33 """"完整的本地批次訓(xùn)練

34 ""end for

35 "nbsp;//準(zhǔn)備接收弱客戶(hù)端卸載的模型

36 ""接收匹配m中指定的弱客戶(hù)端w的模型

37 ""幫助w執(zhí)行額外的re輪本地批次訓(xùn)練

38 ""發(fā)送額外訓(xùn)練完畢的模型至弱客戶(hù)端w

39 end if

如算法4所示，每個(gè)客戶(hù)端執(zhí)行性能分析程序，并將分析結(jié)果報(bào)告給服務(wù)器。如第3行所示，服務(wù)器并行接收客戶(hù)端的消息封裝message，其中包含算法1中的各個(gè)輸入?yún)?shù)和本地模型。算法第8～12行展示了服務(wù)器依次計(jì)算每個(gè)弱客戶(hù)端與強(qiáng)客戶(hù)端之間的模型特征層相似度與預(yù)期運(yùn)行時(shí)間，隨后將其初始化為SIM和CT矩陣，通過(guò)二分搜索成本構(gòu)建算法迭代生成矩陣COST，并運(yùn)用算法3的基于KM的匹配算法求解最優(yōu)匹配m。然后將匹配結(jié)果m與算法1求出的強(qiáng)弱客戶(hù)端的凍結(jié)、額外小批量數(shù)等信息一起發(fā)送給一對(duì)客戶(hù)端。如果客戶(hù)端被判斷為“滯后者”，則需要在執(zhí)行sd輪的小批量訓(xùn)練后將模型凍結(jié)，并與指定的強(qiáng)客戶(hù)端建立直接的通信聯(lián)系后，將模型卸載。而強(qiáng)客戶(hù)端則需在本地訓(xùn)練完成后，繼續(xù)執(zhí)行額外的訓(xùn)練，并將額外訓(xùn)練的模型返回至服務(wù)器指定的“滯后者”?！皽笳摺痹谑盏侥Ｐ秃螅瑢⒃撃Ｐ偷奶卣鲗优c自身簡(jiǎn)化訓(xùn)練的全連接層進(jìn)行重構(gòu)，得到自己的本地模型。圖5為Fed-MBMO框架。

4.4 Fed-MBMO時(shí)間復(fù)雜度分析

本節(jié)將分析二分搜索成本構(gòu)建算法的時(shí)間復(fù)雜度，并進(jìn)一步分析基于模型卸載的聯(lián)邦學(xué)習(xí)框架（Fed-MBMO）的時(shí)間復(fù)雜度。首先將介紹以下定理：

定理1 KM算法找到一個(gè)最大權(quán)值匹配和最小代價(jià)覆蓋[31]。

定理2 對(duì)于加權(quán)二部圖G的一個(gè)完美匹配和加權(quán)覆蓋（u，v），∑ui+∑vj≥w（M）。且∑ui+∑vj=w（M）當(dāng)且僅當(dāng)M是由滿(mǎn)足∑ui+∑vj=w（M）的邊xiyj組成的。此時(shí)，M是（u，v）最優(yōu)的[32]。

在Fed-MBMO算法運(yùn)用MCT劃分強(qiáng)弱客戶(hù)端時(shí)，所有客戶(hù)端均可相互建立通信，原問(wèn)題二部圖是一個(gè)完全二部圖，生成COST矩陣為方陣，所以服務(wù)器在運(yùn)行KM-匹配算法時(shí)，以原問(wèn)題二部圖的相等子圖G中的頂點(diǎn)覆蓋Q開(kāi)始，算法直至相等子圖G中存在完美匹配M時(shí)結(jié)束。

從第一個(gè)頂點(diǎn)覆蓋Q開(kāi)始，大小為|Q|的匹配由|Euclid Math OneRAp|條從Euclid Math OneRAp到S－Euclid Math OneTAp的邊和|Euclid Math OneTAp|條從Euclid Math OneTAp到W－Euclid Math OneRAp的邊組成。為了在相等子圖G中尋找更大的匹配，根據(jù)定理2的要求，需要在保持匹配m中所有邊上相等關(guān)系成立的情況下，引進(jìn)從到S－Euclid Math OneTAp的一條邊來(lái)對(duì)覆蓋（u，v）進(jìn)行修改，但是G中并不存在這樣一條邊，并且其差額為正，另這些最小差額為ε，對(duì)w∈W－Euclid Math OneRAp， uw－ε，但是為了保持Euclid Math OneIAp到W－Euclid Math OneRAp的覆蓋條件仍然成立，需要s∈Euclid Math OneTAp，vs+ε，此時(shí)，相等子圖增加一條邊。若該算法需要權(quán)值為實(shí)數(shù)的情況下可行，在尋找相等子圖G中的頂點(diǎn)覆蓋Q中需至多迭代n2次。而相等子圖中的最大匹配M最多增加n次，因此該算法在O（n3）的時(shí)間復(fù)雜度內(nèi)尋找到了原問(wèn)題二部圖的最小覆蓋∑uw+∑vs=Cost（M），根據(jù)定理1，m為最優(yōu)匹配。

5 實(shí)驗(yàn)分析

為驗(yàn)證Fed-MBMO在訓(xùn)練時(shí)間、模型收斂時(shí)間及全局模型精度上的效果，以及Non-IID對(duì)該算法的影響，分別在四個(gè)圖像數(shù)據(jù)集上進(jìn)行分類(lèi)任務(wù)實(shí)驗(yàn)，其中包括MNIST、Fashion MNIST（FMNIST）、CIFAR10、EMNIST-Balanced（EMNIST-B），并在時(shí)間、精度方面與現(xiàn)有算法FedUE[15]、Aergia[25]、FedAvg[6]比較。

5.1 實(shí)驗(yàn)設(shè)置與環(huán)境

實(shí)驗(yàn)環(huán)境：本文實(shí)驗(yàn)的硬件環(huán)境，處理器為Intel Xeon CPU E5-2697 v3×2，內(nèi)存為2133 MHz Reg ECC 16 GB×2。在本文實(shí)驗(yàn)中，所有的客戶(hù)端相互獨(dú)立，并為每個(gè)客戶(hù)端分配一個(gè)單獨(dú)的CPU核心。

本文的軟件環(huán)境如下，實(shí)驗(yàn)在Windows環(huán)境下進(jìn)行，采用Docker容器虛擬化技術(shù)來(lái)隔離不同CPU核心上的容器，容器中的客戶(hù)端相互隔離并且互不影響，Docker Desktop版本為4.26.1。采用PyTorch分布式訓(xùn)練框架提供P2P通信和張量（Tensor）傳遞，以實(shí)現(xiàn)分布式并行訓(xùn)練場(chǎng)景，每個(gè)客戶(hù)端僅能通過(guò)通信來(lái)實(shí)現(xiàn)消息傳遞。

a）資源異構(gòu)設(shè)置：為模擬物聯(lián)網(wǎng)環(huán)境下不同邊緣設(shè)備具有不同計(jì)算資源的這種異質(zhì)性，本文將為每個(gè)容器分配0.1～1.0個(gè)CPU來(lái)模擬現(xiàn)實(shí)中的所有設(shè)備計(jì)算能力之間的差異。本文為18個(gè)客戶(hù)端分別分配0.1～1.0和0.1～0.8個(gè)CPU，并為每個(gè)客戶(hù)端創(chuàng)建獨(dú)立的Docker容器使其相互隔離，最后隨機(jī)抽取8個(gè)客戶(hù)端參與訓(xùn)練。由于不同客戶(hù)端擁有0.1 CPU與1.0 CPU計(jì)算能力相差巨大，所以在運(yùn)行不同算法時(shí)需要固定抽取客戶(hù)端的隨機(jī)數(shù)種子，以保證不同的算法在相同的全局輪次抽取到完全相同的客戶(hù)端。

b）數(shù)據(jù)集與網(wǎng)絡(luò)：MNIST和FMNIST數(shù)據(jù)集都包含60 000個(gè)訓(xùn)練樣本和10 000個(gè)測(cè)試樣本，共10個(gè)類(lèi)別，數(shù)據(jù)集由大小為28×28像素的灰度圖像組成。前者包含0～9的手寫(xiě)數(shù)字圖像，后者包含10個(gè)不同類(lèi)別的時(shí)尚產(chǎn)品。CIFAR10數(shù)據(jù)集的每個(gè)示例都是一張32×32像素的RGB圖像，數(shù)據(jù)集包含10不同類(lèi)別的50 000個(gè)訓(xùn)練樣本和10 000個(gè)測(cè)試樣本。EMNIST-B數(shù)據(jù)集包含112 800個(gè)訓(xùn)練樣本和18 800個(gè)測(cè)試樣本，共47個(gè)類(lèi)別，每張示例都是一張28×28像素的灰度圖像。

前三個(gè)數(shù)據(jù)集的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)與Aergia實(shí)驗(yàn)中使用的模型結(jié)構(gòu)相同。其中，MNIST CNN包括兩個(gè)卷積層（5×5卷積核，分別有10和20個(gè)通道），每個(gè)卷積層后面都有ReLU激活函數(shù)和2×2最大池化層，第二個(gè)卷積層后有一個(gè)dropout層，最后是兩個(gè)全連接層。EMNIST-B CNN結(jié)構(gòu)僅與MNIST CNN在dropout概率和輸出層不同，其余結(jié)構(gòu)一致。具體結(jié)構(gòu)如圖6所示。FMNIST CNN包括兩個(gè)卷積層和一個(gè)全連接層，每個(gè)卷積層都有ReLU激活函數(shù)、批歸一化層和2×2最大池化層。CIFAR10 CNN由6個(gè)卷積層與兩個(gè)共138個(gè)神經(jīng)元的全連接層構(gòu)成。

為驗(yàn)證算法在IID和Non-IID條件下的有效性，實(shí)驗(yàn)還模擬了現(xiàn)實(shí)中不同的數(shù)據(jù)分布。本實(shí)驗(yàn)采用分布參數(shù)β=0.5的Dirichlet分布來(lái)模擬Non-IID環(huán)境[32]。

c）超參數(shù)設(shè)置。權(quán)重參數(shù)α=0.5，全局輪次為50，本地訓(xùn)練輪次為5輪，本地批次大小為16，學(xué)習(xí)率固定為0.01，性能分析小批量數(shù)（profiling）為100，隨機(jī)數(shù)種子為2 023。其中，Non-IID的實(shí)驗(yàn)條件為分布參數(shù)為β=0.5的Dirichlet分布[33]。優(yōu)化器為動(dòng)量等于0.1的SGD優(yōu)化器。

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

本文實(shí)驗(yàn)在不同數(shù)據(jù)分布、資源異構(gòu)設(shè)置的條件下，與Aergia、FedAvg、FedUE基線算法進(jìn)行了比較。

圖7展示了在數(shù)據(jù)分布IID和Non-IID的條件下，不同數(shù)據(jù)集在CNN模型下的全局模型的訓(xùn)練時(shí)間-精度圖。

由圖7可以看出，即使在18個(gè)客戶(hù)端計(jì)算資源極端異質(zhì)并且在其數(shù)據(jù)IID和Non-IID的情況下，F(xiàn)ed-MBMO仍然能夠達(dá)到收斂。從圖7（b）（e）可以看出，在Dirichlet分布參數(shù)β=0.5的數(shù)據(jù)極端異質(zhì)分布下，收斂速度仍快于FedUE，在IID條件下，F(xiàn)ed-MBMO算法在收斂速度和訓(xùn)練效率上顯示出明顯的優(yōu)勢(shì)。

這得益于Fed-MBMO的滯后者模型卸載匹配機(jī)制，避免了因弱客戶(hù)端計(jì)算資源不足而凍結(jié)模型導(dǎo)致的訓(xùn)練效果不佳的問(wèn)題，并且達(dá)到相同精度的收斂速度比Aergia、FedAvg和FedUE快。因此Fed-MBMO算法在IID、Non-IID條件下且計(jì)算能力差異巨大的情況下能夠達(dá)到目前主流算法的水平。

然而，如表1所示，在EMNIST-B 的β=0.5的Dirichlet分布下，F(xiàn)ed-MBMO算法有1.37～2.36百分點(diǎn)的下降，這是因?yàn)镋MNIST-B有47個(gè)類(lèi)別，因此，模型特征層在面對(duì)更多類(lèi)別的樣本并不能很好地表征數(shù)據(jù)集的特征，所以匹配后的強(qiáng)客戶(hù)端的額外訓(xùn)練模型的全連接層并不能很好地適應(yīng)弱客戶(hù)端的特征層。相反，在對(duì)應(yīng)的IID環(huán)境下，平均精度高于其他三個(gè)算法，表明了本文的匹配機(jī)制更加適合IID分布的情況。因此在面對(duì)擁有更多類(lèi)別且Non-IID分布的數(shù)據(jù)集條件下，滯后者停止更新卷積層將會(huì)對(duì)全局模型造成較大傷害，將式（11）中的特征層相似度替換為其他方法則更加合適，例如基于數(shù)據(jù)集標(biāo)簽分布的EMD距離等?？傮w來(lái)說(shuō)，F(xiàn)ed-MBMO算法在達(dá)到相同精度的條件下，訓(xùn)練效率全面優(yōu)于FedAvg、Aergia和FedUE。

圖8分別展示了Fed-MBMO算法在訓(xùn)練時(shí)間上的優(yōu)越性，各算法在不同數(shù)據(jù)集下的訓(xùn)練時(shí)間如表2所示。在18個(gè)客戶(hù)端計(jì)算資源極端異質(zhì)且保證精度的條件下，本文算法具體訓(xùn)練時(shí)間提升幅度如表3所示，比FedUE平均快12.66%，比Aergia和FedAvg平均快38.07%和46.65%。Aergia和FedUE算法在處理極弱的“滯后者”時(shí)存在不足。其中Aergia仍會(huì)因?yàn)闃O弱客戶(hù)端簡(jiǎn)化后的本地訓(xùn)練量而拖延了訓(xùn)練時(shí)長(zhǎng)，而FedUE則通過(guò)聚類(lèi)將計(jì)算能力類(lèi)似的客戶(hù)端分在同一組，雖然減少了客戶(hù)端等待時(shí)間的差異，但仍然無(wú)法消除極弱客戶(hù)端的影響。在這一方面，F(xiàn)ed-MBMO很好地削減了極弱客戶(hù)端的無(wú)效訓(xùn)練。并且該算法通過(guò)合理的強(qiáng)弱匹配機(jī)制保證了弱客戶(hù)端在不同全局輪次中卸載目的地的多樣性，這種合理的匹配和訓(xùn)練任務(wù)分配確保弱客戶(hù)端凍結(jié)部分模型節(jié)約訓(xùn)練時(shí)長(zhǎng)的同時(shí)不會(huì)顯著影響模型的精度，在處理了制約訓(xùn)練時(shí)長(zhǎng)的短板的同時(shí)，保證了全局模型的泛化能力，因此該方法能夠加速全局模型收斂，減少“滯后者”效應(yīng)帶來(lái)的影響。

收斂時(shí)間和訓(xùn)練時(shí)間的減少對(duì)醫(yī)療物聯(lián)網(wǎng)設(shè)備與智能駕駛領(lǐng)域中的聯(lián)邦學(xué)習(xí)應(yīng)用十分重要，減少收斂所需時(shí)間能夠使相關(guān)的邊緣設(shè)備作出更快速且精準(zhǔn)的反應(yīng)，從而更加準(zhǔn)確快速地預(yù)測(cè)和判斷各類(lèi)健康疾病和交通事故等。

本研究使用Fed-MBMO算法在IID和Non-IID（使用Dirichlet分布，β=0.5）下的各個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)對(duì)比，其平均精度結(jié)果如表1所示。表1凸顯了本文方法在精度方面的魯棒性。同時(shí)，表2展示了本文在縮短訓(xùn)練時(shí)間方面取得的顯著成果，而表3則詳細(xì)統(tǒng)計(jì)了訓(xùn)練時(shí)間減少的百分比。

圖9展示了所有客戶(hù)端在不同數(shù)據(jù)集和劃分的情況下，每輪客戶(hù)端的平均等待時(shí)間（mean wait time，MWT）的數(shù)據(jù)分布與密度。由圖9可知，F(xiàn)edAvg的MWT向上聚集，并且小提琴上寬下窄，進(jìn)而導(dǎo)致MWT的中位數(shù)也偏上，說(shuō)明制約聯(lián)邦學(xué)習(xí)訓(xùn)練效率的是小提琴下半部分的少數(shù)計(jì)算能力較低的滯后者，所以導(dǎo)致剩余的多數(shù)客戶(hù)端等待時(shí)間過(guò)長(zhǎng)。而Aergia降低了小提琴的高度，如圖9（c）所示，極大地減少了訓(xùn)練時(shí)間，但是仍受到極弱客戶(hù)端的制約，圖（c）中的小提琴仍然上寬下窄，所以Aergia并沒(méi)有解決大多數(shù)客戶(hù)端等待時(shí)間過(guò)長(zhǎng)的問(wèn)題。

FedUE減少了訓(xùn)練時(shí)間，并且降低了客戶(hù)端的等待時(shí)間，但與此相比，F(xiàn)ed-MBMO中位數(shù)更小，并且四分位差更短且密集，說(shuō)明了本文算法客戶(hù)端的MWT并不會(huì)像FedUE一樣分散，更長(zhǎng)的四分位差會(huì)導(dǎo)致客戶(hù)端的等待時(shí)間有很強(qiáng)的不確定性，F(xiàn)edUE的MWT因此也存在多個(gè)峰值。

5.3 影響算法性能的因素

根據(jù)式（17）的卸載成本函數(shù)可得，當(dāng)權(quán)重參數(shù)α不同時(shí)，則基于卸載成本函數(shù)構(gòu)成的卸載成本矩陣COST（式（18））所得到的迭代匹配算法結(jié)果也會(huì)有不同。另一方面，客戶(hù)端之間計(jì)算能力的差異也會(huì)對(duì)實(shí)驗(yàn)結(jié)果產(chǎn)生影響。因此，本節(jié)將用實(shí)驗(yàn)驗(yàn)證權(quán)重參數(shù)α和不同客戶(hù)端CPU計(jì)算能力的差異對(duì)本文算法的影響。

圖10為客戶(hù)端計(jì)算能力完全相同的情況下，MNIST 數(shù)據(jù)集在IID分布條件下，不同權(quán)重α對(duì)算法性能的影響。其中左側(cè)為訓(xùn)練時(shí)間（小時(shí)），右側(cè)為全局模型精度百分比。圖中可以看到，當(dāng)α=1.0時(shí)，訓(xùn)練時(shí)間最短，而α=0時(shí)，訓(xùn)練時(shí)間則會(huì)更長(zhǎng)。這是因?yàn)楫?dāng)α=1.0時(shí)卸載成本函數(shù)值權(quán)重全部偏向輔助變量z，導(dǎo)致迭代匹配算法在構(gòu)成的COST矩陣中得到的KM-匹配結(jié)果更傾向時(shí)間最短的匹配。相反，α=0時(shí)間則最長(zhǎng)，精度則趨于穩(wěn)定，一方面是因?yàn)镸NIST IID任務(wù)相對(duì)簡(jiǎn)單，另一方面，除了合理的強(qiáng)弱匹配之外，強(qiáng)客戶(hù)端輔助弱客戶(hù)端訓(xùn)練也起到了一定的作用。

圖11展示了客戶(hù)端在不同計(jì)算能力差異的情況下，對(duì)于算法性能的影響。本實(shí)驗(yàn)分別研究了客戶(hù)端擁有CPU的方差和擁有CPU個(gè)數(shù)對(duì)算法的影響，前者代表了聯(lián)邦學(xué)習(xí)中所有客戶(hù)端算力之和相等的情況下，客戶(hù)端計(jì)算能力差異對(duì)算法的影響，后者代表了客戶(hù)端算力之和對(duì)算法的影響。圖11（b）線-柱圖橫坐標(biāo)符號(hào)含義如表4所示。

首先，顯而易見(jiàn)的是系統(tǒng)中的算力越多，訓(xùn)練時(shí)間越快（圖11（b）中的a和c），但是達(dá)到相同精度的收斂輪次并沒(méi)有大幅減少（圖11（a）），對(duì)全局模型的貢獻(xiàn)也并不突出。

其次，在圖11（a）中可以看出，在所有客戶(hù)端算力之和相等的情況下，隨著方差逐漸升高，達(dá)到收斂精度的輪次也在提前，平均精度也會(huì)更高（圖11（b）折線圖）。這代表了在算力相等的情況下，客戶(hù)端之間算力差異越大，全局模型性能更優(yōu)。但代價(jià)是訓(xùn)練時(shí)間也會(huì)隨之增加，這與上述時(shí)間復(fù)雜度分析相一致。這是因?yàn)槿蹩蛻?hù)端在大方差的情況下會(huì)經(jīng)歷更多的完整訓(xùn)練，增加了計(jì)算負(fù)擔(dān)，所以拖慢了訓(xùn)練速度，但提升了全局模型性能。因此，可以設(shè)置合理的權(quán)重參數(shù)α來(lái)平衡訓(xùn)練時(shí)間和模型精度以滿(mǎn)足不同場(chǎng)合的業(yè)務(wù)需求。

5.4 算法應(yīng)用與展望

弱客戶(hù)端凍結(jié)模型和極弱客戶(hù)端縮減訓(xùn)練量的方法能夠顯著減少計(jì)算能力弱的設(shè)備在聯(lián)邦學(xué)習(xí)中的計(jì)算負(fù)擔(dān)，同時(shí)有效減少訓(xùn)練和收斂所需的時(shí)間，因此算法應(yīng)用廣泛。例如，在醫(yī)療物聯(lián)網(wǎng)領(lǐng)域，更多的設(shè)備能夠參與到聯(lián)邦學(xué)習(xí)中，從而提高模型的整體性能和準(zhǔn)確性。這不僅有助于實(shí)現(xiàn)更精確的患者監(jiān)測(cè)和預(yù)測(cè)，還能為醫(yī)療機(jī)構(gòu)提供更高效的醫(yī)療解決方案。在智能駕駛領(lǐng)域，各類(lèi)車(chē)載傳感器和計(jì)算設(shè)備構(gòu)成了一個(gè)復(fù)雜的物聯(lián)網(wǎng)系統(tǒng)，因計(jì)算能力的異質(zhì)性帶來(lái)了應(yīng)用挑戰(zhàn)。Fed-MBMO通過(guò)模型卸載與強(qiáng)弱匹配，能夠?qū)崿F(xiàn)弱車(chē)機(jī)設(shè)備與強(qiáng)車(chē)機(jī)設(shè)備之間的平衡，從而提高智能駕駛系統(tǒng)的整體性能和安全性。

未來(lái)的研究可以進(jìn)一步探索該算法在其他領(lǐng)域和應(yīng)用場(chǎng)景中的潛力，如工業(yè)物聯(lián)網(wǎng)、智能家居和軍事應(yīng)用等。同時(shí)，隨著邊緣計(jì)算和物聯(lián)網(wǎng)技術(shù)的不斷進(jìn)步，如何進(jìn)一步提高算法復(fù)雜通信環(huán)境下的魯棒性和模型精度，以滿(mǎn)足復(fù)雜和多變的實(shí)際需求，將是一個(gè)值得關(guān)注和研究的重要方向。

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

本文基于邊緣計(jì)算的環(huán)境下，針對(duì)“滯后者”效應(yīng)等困擾聯(lián)邦學(xué)習(xí)訓(xùn)練效率的一系列問(wèn)題，提出了客戶(hù)端劃分方法和模型卸載策略。通過(guò)客戶(hù)端執(zhí)行性能分析程序并將結(jié)果報(bào)告給服務(wù)器，服務(wù)器綜合考慮模型特征層相似度與預(yù)期運(yùn)行時(shí)間，并將問(wèn)題建模為基于匹配的模型卸載問(wèn)題，通過(guò)基于KM的迭代匹配算法求解。此外，本文進(jìn)一步分析了Fed-MBMO算法的性質(zhì)，表明該算法能夠在多項(xiàng)式的時(shí)間復(fù)雜度內(nèi)完成，為解決聯(lián)邦學(xué)習(xí)“滯后者”效應(yīng)提出了新的解決方案。實(shí)驗(yàn)采用P2P通信、分布式框架、虛擬化容器等技術(shù)模擬聯(lián)邦學(xué)習(xí)并行訓(xùn)練場(chǎng)景，實(shí)驗(yàn)結(jié)果展示了在減少訓(xùn)練時(shí)間和收斂時(shí)間等方面均有不錯(cuò)的效果，有效解決“滯后者”效應(yīng)。

參考文獻(xiàn)：

[1]Wen Jie， Zhang Jingbo， Zhang Zhixia， et al. Resource-aware multi-criteria vehicle participation for federated learning in Internet of Vehicles [J]. Information Sciences， 2024， 664： 120344.

[2]崔云龍. EC-IoT [R/OL]. （2021-11-23）. https：//support. huawei. com/enterprise/zh/doc/EDOC1100195298.（Cui Yunlong.EC-IoT [R/OL]. （2021-11-23）. https：//support. huawei. com/enterprise/zh/doc/EDOC1100195298.）

[3]Sun Baoshan， Huang Hao， Chai Zhengyi， et al. Multi-objective optimization algorithm for multi-workflow computation offloading in resource-limited IIoT [J]. Swarm and Evolutionary Computation， 2024， 89： 101646.

[4]Gecer M， Garbinato B. Federated learning for mobility applications [J]. ACM Computing Surveys， 2024， 56 （5）： 1-28.

[5]Sánchez P M S， Celdrán A H， Xie Ning， et al. Federatedtrust： a solution for trustworthy federated learning [J]. Future Generation Computer Systems， 2024， 152： 83-98.

[6]McMahan B， Moore E， Ramage D， et al. Communication-efficient learning of deep networks from decentralized data [C]//Proc of Artificial Intelligence and Statistics.New York：PMLR， 2017： 1273-1282.

[7]何常樂(lè)， 袁培燕. 邊緣聯(lián)邦學(xué)習(xí)的客戶(hù)端選擇機(jī)制 [J]. 計(jì)算機(jī)應(yīng)用， 2023， 43 （S1）： 147-153. （He Changle， Yuan Peiyan. Client selection mechanism of federated learning in edge computing. [J]. Journal of Computer Applications， 2023， 43 （S1）： 147-153.）

[8]Sultana K， Ahmed K， Gu B， et al. Elastic optimization for stragglers in edge federated learning [J]. Big Data Mining and Analytics， 2023， 6 （4）： 404-420.

[9]Gupta A， Misra S， Pathak N， et al. Fedcare： federated learning for resource-constrained healthcare devices in IoMT system [J]. IEEE Trans on Computational Social Systems， 2023， 10 （4）： 1587-1596.

[10]Imteaj A， Mamun Ahmed K， Thakker U， et al. Federated learning for resource-constrained IoT devices： panoramas and state of the art [J]. Federated and Transfer Learning， 2022： 7-27.

[11]Wu Di， Ullah R， Harvey P， et al. Fedadapt： adaptive offloading for IoT devices in federated learning [J]. IEEE Internet of Things Journal， 2022， 9 （21）： 20889-20901.

[12]Lu Renhao， Zhang Weizhe， Li Qiong， et al. Adaptive asynchronous federated learning [J]. Future Generation Computer Systems， 2024， 152： 193-206.

[13]Guo Hongpeng， Gu Haotian， Wang Xiaoyang， et al. FedCore： straggler-free federated learning with distributed coresets [EB/OL]." （2024-01-31）.https：//arxiv.org/abs/2402.00219.

[14]Zeng Manying， Wang Xiumin， Pan Weijian， et al. Heterogeneous training intensity for federated learning： a deep reinforcement learning approach [J]. IEEE Trans on Network Science and Enginee-ring， 2022， 10 （2）： 990-1002.

[15]Zang Tianming， Zheng Ce， Ma Shiyao， et al. A general solution for straggler effect and unreliable communication in federated learning [C]// Proc of IEEE International Conference on Communications. Piscataway，NJ：IEEE Press， 2023： 1194-1199.

[16]Liu Yijing， Feng Gang， Du Hongyang， et al. Adaptive clustering based straggler-aware federated learning in wireless edge networks [J]. IEEE Trans on Communications， 2024：3412763.

[17]Liu Yutao， Zhang Xiaoning， Zhao Yangming， et al. Chronos： acce-lerating federated learning with resource aware training volume tuning at network edges [J]. IEEE Trans on Vehicular Technology， 2022， 72 （3）： 3889-3903.

[18]Zhan Wenhan， Luo Chunbo， Wang Jin， et al. Deep-reinforcement-learning-based offloading scheduling for vehicular edge computing [J]. IEEE Internet of Things Journal， 2020， 7 （6）： 5449-5465.

[19]Zhao Yue， Li Meng， Lai Liangzhen， et al. Federated learning with Non-IIDdata [EB/OL]. （2018-06-02）. https：//arxiv.org/abs/ 1806. 00582.

[20]Zawad S， Ali A， Chen Pinyu， et al. Curse or redemption？How data heterogeneity affects the robustness of federated learning [C]// Proc of AAAI Conference on Artificial Intelligence.Palo Alto，CA：AAAI Press，2021： 10807-10814.

[21]Xu Zirui， Yu Fuxun， Xiong Jinjun， et al. Helios： heterogeneity-aware federated learning with dynamically balanced collaboration [C]// Proc of 58th ACM/IEEE Design Automation Conference. Piscataway，NJ：IEEE Press， 2021： 997-1002.

[22]Li Li， Liu Duo， Duan Moning， et al. Federated learning with workload-aware client scheduling in heterogeneous systems [J]. Neural Networks， 2022， 154： 560-573.

[23]Ji Zhongming， Chen Li， Zhao Nan， et al. Computation offloading for edge-assisted federated learning [J]. IEEE Trans on Vehicular Technology， 2021， 70 （9）： 9330-9344.

[24]Chai Zheng， Ali A， Zawad S， et al. TiFL： a tier-based federated learning system [C]// Proc of the 29th International Symposium on High-Performance Parallel and Distributed Computing. New York：ACM Press，2020： 125-136.

[25]Cox B， Chen L Y， Decouchant J. Aergia： leveraging heterogeneity in federated learning systems [C]// Proc of the 23rd ACM/IFIP International Middleware Conference. New York：ACM Press，2022： 107-120.

[26]Li Qinbin， Diao Yiqun， Chen Quan， et al. Federated learning on Non-IID data silos： an experimental study [C]// Proc of the 38th IEEE International Conference on Data Engineering . Piscataway，NJ：IEEE Press， 2022： 965-978.

[27]Zhang Feilong， Liu Xianming， Lin Shiyi， et al. No one idles： efficient heterogeneous federated learning with parallel edge and server computation [C]// Proc of International Conference on Machine Learning.New York：PMLR，2023： 41399-41413.

[28]馬千飄， 賈慶民， 劉建春， 等. 異構(gòu)邊緣計(jì)算環(huán)境下異步聯(lián)邦學(xué)習(xí)的節(jié)點(diǎn)分組與分時(shí)調(diào)度策略 [J]. 通信學(xué)報(bào)， 2023， 44 （11）： 79-93. （Ma Qianpiao， Jia Qingmin， Liu Jianchun， et al. Client grouping and time-sharing scheduling for asynchronous federated learning in heterogeneous edge computing environment [J]. Journal on Communications， 2023， 44 （11）： 79-93.）

[29]Wang Cong， Yang Yuanyuan， Zhou Pengzhan. Towards efficient scheduling of federated mobile devices under computational and statistical heterogeneity [J]. IEEE Trans on Parallel and Distributed Systems， 2020， 32 （2）： 394-410.

[30]Du Xiangtong， Liu Zhidong， Feng Zunlei， et al. DataMap： dataset transferability map for medical image classification [J]. Pattern Recognition， 2024， 146： 110044.

[31]Munkres J. Algorithms for the assignment and transportation problems [J]. Society for Industrial and Applied Mathematics， 1962， 15： 196-210.

[32]West D B. Introduction to graph theory [M]. Upper Saddle River： Prentice Hall， 2001.

[33]Hsu T M H， Qi Hang， Brown M. Measuring the effects of non-identical data distribution for federated visual classification [EB/OL]. （2019-09-13）. https：//arxiv.org/abs/1909. 06335.