移動邊緣計算環境中面向機器學習的計算遷移策略

郭 棉，張錦友

（1.廣東技術師范大學電子與信息學院，廣州 510665；2.廣東石油化工學院電子信息工程學院，廣東茂名 525000）

（*通信作者電子郵箱mian.guo123@gmail.com）

0 引言

隨著人工智能和物聯網（Internet of Things，IoT）技術的發展，涌現了越來越多的先進物聯網應用，例如，虛擬現實、自動駕駛和工業自動化等［1］。這些應用以數據為驅動，通過機器學習算法獲取數據價值，進而實現預測、控制以及其他智能化操作。通常，機器學習算法是部署在網絡中心的高性能云服務器上的，應用產生的海量數據需要上傳到云端的機器學習服務器上才能被處理。然而，該范式已經難以滿足物聯網應用的海量連接、超低延遲的服務要求。首先，從數據源到云端機器學習服務器的網絡傳輸延遲一般為幾百毫秒以上，已成為低延遲的瓶頸［2］；其次，數據往往具有安全性和隱私性要求，僅僅為了數據分析的目的而將數據傳輸到公共云的方式并不可?。?］。

移動邊緣計算（Mobile Edge Computing，MEC）的思想是在數據源的附近部署計算節點［4］，既可以降低網絡傳輸延遲，又可以避免數據離開邊緣網絡，提高數據安全性，加強隱私保護［5］。移動邊緣計算已經被認為是支持先進物聯網應用的一種很有發展前景的范式。在移動邊緣計算中，計算節點包括具有計算能力的移動節點（例智能手機）［6］和邊緣服務器。由于電池和體積的限制，移動節點的計算能力遠小于邊緣服務器。但是，移動節點比邊緣服務器更靠近數據源?？紤]到邊緣節點的異構計算能力和網絡位置，有兩種可行的面向移動邊緣計算環境的機器學習模型：1）面向邊緣計算的集中學習，將機器學習從云遷移到邊緣服務器。物聯網終端只需要將其產生的數據傳輸到邊緣服務器，邊緣服務器運行機器學習來處理數據。2）邊緣節點合作的分布式機器學習，每個參與分布式機器學習的邊緣節點執行一部分學習任務，通過結果匯聚就可以得到整體的機器學習結果。在各種現有的分布式機器學習方案中，聯邦學習［7-8］是一個新的范式。

研究學者對如何在移動邊緣計算網絡中部署機器學習進行了積極的研究。Li等［9］提出了一種深度強化學習方法來將任務分配到不同的邊緣服務器進行處理；Zhu 等［10］設計了一套在無線網絡邊緣運行機器學習的通信和計算規則；Mahmoudi 等［11］提出了一種在無線環境中實現分布式機器學習的優化算法；羅長銀等［12］提出了一種面向區塊鏈的在線聯邦增量學習算法。但是，現有的研究僅考慮移動邊緣計算網絡中的一種機器學習模型，例如，文獻［9］面向的是移動邊緣計算網絡的集中學習，文獻［11-12］面向的是分布式機器學習。實際上，隨著物聯網終端（數據源）和物聯網應用的快速增長，由于無線網絡資源受限性、終端能耗和計算節點計算能力的異構性，在一個移動邊緣計算網絡內僅運行單一的機器學習模式（例如，僅采用集中學習，或僅采用聯邦學習）將使機器學習性能非常低下。

為了支持海量物聯網連接和滿足機器學習的低延遲需求，本文綜合考慮了集中學習和聯邦學習對通信、計算資源的差異化需求，提出了一種能量約束的延遲貪婪（Energy-Constrained Delay-Greedy，ECDG）計算遷移策略，自適應地為物聯網終端選擇機器學習模型。該策略首先將機器學習模型的選擇問題轉化為計算遷移問題；然后，分別對集中學習和聯邦學習進行數學建模；接著，以機器學習平均延遲最小化為目標、以能耗和訓練精度為約束條件構建計算遷移優化模型；最后，提出了ECDG 算法，通過延遲貪婪決策和能量約束決策更新二階優化來獲得優化模型的解。通過與集中式貪婪算法和FedCS（Federated learning with Client Selection）算法的對比實驗驗證了ECDG 算法能夠有效降低機器學習延遲，滿足物聯網應用的海量數據源、低延遲服務質量（Quality of Service，QoS）要求。

1 系統建模

1.1 系統架構

考慮一個由多個具有計算能力的移動節點和一個邊緣服務器構成的MEC 系統。在該系統中，移動節點隨機地分布在無線網絡的覆蓋區域，邊緣服務器位于無線網絡的中心（例如，基站）。每個移動節點接收來自附近物聯網傳感器的數據（例如，視頻、溫濕度數據等），然后產生計算任務（例如，自動駕駛的路況識別［13］、工作區間的環境監測［14］等）。由于每個移動節點僅接收附近物聯網傳感器的數據，其數據集樣本僅包含了物聯網應用所需的局部信息，具有非獨立同分布性。因此，機器學習的準確性要求使用多個數據集進行訓練。此外，本文假設每個計算節點，包括移動節點和邊緣服務器，都部署了機器學習算法，而且移動節點的計算能力低于邊緣服務器的計算能力。

假設該MEC 系統主要提供兩種機器學習模型，包括集中學習模型和聯邦學習模型。每個移動節點僅能選擇其中一種模型來執行計算任務。若某個移動節點選擇集中學習，如圖1 所示，它的計算任務和數據集都將遷移到邊緣服務器。邊緣服務器匯聚數據集后執行機器學習算法訓練模型，然后將訓練的結果返回給該節點。

圖1 集中學習模型Fig.1 Centralized learning model

相反地，若有若干移動節點選擇聯邦學習模型，則如圖2所示，這些移動節點（也稱客戶端）和邊緣服務器（也稱聯邦服務器）將按聯邦學習機制［8］協同學習，具體地，將通過多輪的“本地學習→本地模型參數上傳→全局模型參數更新→下發給客戶端作為下一輪本地學習的模型參數”循環學習，直至全局模型收斂。由此可見，選擇該模型的移動節點，它的數據集和計算任務都不需要遷移到聯邦服務器，但是，它需要與邊緣服務器進行多輪的通信，以交換/更新模型參數。

圖2 聯邦學習模型Fig.2 Federated learning model

基于上述分析，機器學習模型的選擇問題可以等效為計算遷移問題。令Ω={1，2，…，M}表示MEC 系統的移動節點集合。令π=(I1，I2，…，IM)表示移動節點的計算遷移決策向量。對任意的移動節點m∈Ω，當Im=0時，表示數據不遷移，等效于移動節點m選擇聯邦學習模型；否則，Im=1 表示選擇集中學習，此時，該節點需要將數據集和任務遷移到邊緣服務器。接下來分析移動節點選擇不同的機器學習模型時所經歷的學習延遲。

1.2 集中學習延遲

設MEC 中選擇計算遷移（即集中學習模型）的移動節點集合為ΩC?Ω。對于任意的m∈ΩC，Im=1 成立。在本文中，集中學習的學習延遲定義為從移動節點將數據集上傳給邊緣服務器到機器學習訓練結束的時間間隔。集中學習模式主要包括數據集上傳和訓練兩個階段，選擇集中學習的移動節點將經歷相同的集中學習延遲。因此，移動節點m∈ΩC的集中學習延遲可采用如下公式計算：

其中：DC，Tx是數據上傳延遲；DC，CPU是集中學習訓練延遲。

本文假設同步訓練模式，也就是邊緣服務器等待所有數據到達后才開始訓練。因此，數據上傳延遲DC，Tx是從移動節點將數據集上傳給邊緣服務器到邊緣服務器接收到所有選擇集中學習的移動節點的數據集的時間間隔。假設這些移動節點同時上傳數據，則數據上傳延遲等效為：所有選擇集中學習的移動節點當中，數據上傳延遲最大的節點所經歷的數據上傳延遲。因此，集中學習的數據上傳延遲為：

根據機器學習原理［15-16］，當邊緣服務器運行集中學習時，需要對數據集進行多輪分批訓練，直到得到一個穩定的優化模型。因此，邊緣服務器的集中學習訓練延遲可以表示為單批樣本訓練延遲的函數：

其中：DC，CPU，B是一批樣本訓練的延遲；NC是進行模型訓練所需的輪數（在每輪中，數據集中的所有樣本都參與了訓練）；是集中學習的總樣本數；BC是一批樣本的數量；表示總樣本可以分為多少批。

1.3 聯邦學習延遲

設MEC 中選擇本地計算（即聯邦學習模型）的移動節點集合為ΩF?Ω，則對于任意的m∈ΩF，Im=0 成立。根據1.1節的MEC 系統聯邦學習機制，聯邦學習延遲是多輪訓練延遲的總和，而每輪延遲可以進一步分為一個通信來回的延遲（移動節點上傳本地模型參數和聯邦服務器下發全局模型參數的延遲之和）以及單輪聯邦學習的訓練延遲，因此，移動節點m∈ΩF的聯邦學習延遲可以表示為：

其中：NF表示聯邦學習的輪數；是單輪通信來回的延遲；DF，CPU是單輪聯邦學習的訓練延遲。

令SMsg表示攜帶模型參數的數據包的大小，則單輪通信延遲表示為：

由于移動節點本地訓練的初始化模型參數是由聯邦服務器下發，而且移動節點上傳的模型參數數據類型與聯邦服務器下發的全局模型參數的類型也一致，因此，在式（5）中，本文假設了移動節點上傳的模型參數數據包與聯邦服務器下發的全局模型參數數據包大小相等，從而單輪通信延遲可表示為單向通信延遲的2倍。

文獻［7］指出，為了減少通信次數（減小NF），可以增大單輪本地訓練的次數，等效于每個移動節點可以在單輪中進行多次迭代的本地訓練。因此，移動節點m的單輪本地訓練延遲可以表示為：

假設采用同步聯邦學習模型，也就是聯邦服務器等所有的本地訓練模型參數都上傳后才匯聚更新全局模型參數，則單輪的聯邦學習的本地訓練延遲就是所有參與聯邦學習的移動節點所提供的本地訓練延遲中最大的一個延遲，因此，單輪聯邦學習的本地訓練延遲表示為：

需要注意的是，與通信延遲和本地訓練延遲相比，集中學習的數據集匯聚延遲和聯邦學習的全局模型參數更新延遲非常小，因此本文忽略這兩類延遲。

2 問題建模

本章首先分析移動節點的能耗模型，然后對基于機器學習的計算遷移問題進行數學建模。

2.1 能耗建模

由于邊緣服務器可以通過持續供電的方式提供能源，本文只考慮能量受限的移動節點的能耗。根據1.1 節所述的系統模型，移動節點m∈Ω的能耗可以表述為：

進一步地，在集中學習模式中，移動節點僅需要將數據上傳給邊緣服務器。當選擇該模型時，移動節點僅消耗網絡傳輸能耗。根據參考文獻［17］，網絡傳輸能耗與數據所經歷的網絡傳輸延遲相關，因此，可表述為：

在聯邦學習模型中，移動節點既要參與計算又要傳輸模型參數。因此，當移動節點m∈Ω選擇聯邦學習模型進行任務處理時，其能耗是傳輸能耗與計算能耗的和，根據文獻［17］中的邊緣計算系統的傳輸能耗和計算能耗模型，經過簡單的計算和推導，有：

2.2 優化目標

根據1.1節的系統模型，移動節點的學習延遲可表述為：

則系統的平均學習延遲是所有移動節點的學習延遲的均值，即：

因此，能耗限制的多機器學習模型下移動邊緣計算系統的延遲優化計算遷移問題可以建模為：

其中：式（13）是移動節點的能量約束，是移動節點的最大可用能量；式（14）是集中學習需要訓練的輪次；式（15）是聯邦學習需要訓練的輪次。不管是集中學習還是聯邦學習，模型的準確度都與參與訓練的數據集多少（等效于，參與訓練的移動節點數）相關［16］，因此，在模型準確度限制下，集中學習和聯邦學習的訓練輪次可以分別表示為：

其中：‖ · ‖表示數組內元素的數量；αC和αF分別是模型訓練輪次因子。此外，為了避免訓練時間過長，本文為集中學習和聯邦學習分別設置了最大輪次，分別如式（14）和（15）右邊所示。

3 ECDG

3.1 計算遷移博弈分析

針對2.2 節的計算遷移優化問題，本文考慮分布式決策：每個移動節點基于系統狀態和其他移動節點的決策執行自己的計算遷移（等效于機器學習模型選擇）決策。假設每個移動節點都是自私的，而且以自身的能量為約束（見式（13））、以最小化自己的學習延遲為目標執行計算遷移決策。當且僅當計算遷移決策更新（例如，從集中學習模式轉換為聯邦學習模式）能降低學習延遲時，移動節點才執行計算遷移決策更新。

令Ι-m=(I1，I2，…，Im-1，Im+1，…，IM)表示移動節點m獲得的其他移動節點的計算遷移決策，給定I-m，則根據式（12）～（15），移動節點m的計算遷移決策就是使得它自身的學習延遲最?。簊.t.式（13）～（15）。

上述問題可以構建為一個計算遷移策略博弈G=)。其中，博弈選手集合就是移動節點集合Ω，選手m的策略就是移動節點m的計算遷移策略Im={0，1}，選手m期望最小化的成本函數就是移動節點m的學習延遲Dm(Im，I-m)。

為了求解上述博弈問題，定義計算遷移博弈的納什均衡如下：

定義1計算遷移博弈的納什均衡。當在均衡點π*，沒有任何移動節點可以通過單方面修改自身的決策來進一步減少自身的成本時，該決策配置π*=被稱為計算遷移博弈的納什均衡，因此，對所有m∈Ω，該決策配置滿足條件：

定義1 表明，當達到納什均衡時，當前的計算遷移策略是相互滿足的策略，任一移動節點都不能通過單方面的策略調整來進一步降低自身的學習延遲，因而沒有節點愿意更改決策。

為了進一步獲得納什均衡的計算遷移決策，接下來定義計算遷移博弈的最佳策略如下：

定義2最佳計算遷移策略。給定其他移動節點的策略I-m，當移動節點m∈Ω的計算遷移策略滿足條件式（18）時，該策略被稱為最佳計算遷移策略。

根據定義2 可知，在給定其他移動節點的策略下，當移動節點采用最佳計算遷移策略時將獲得自身最小的學習延遲。

根據定義1～2，對于2.2 節所述的計算遷移問題，有如下引理。

引理1對于任意的移動節點m∈Ω，假設Em≤成立，則給定其他移動節點的計算遷移決策I-m，該移動節點的最佳策略如下：

由此，可得如下定理。

定理1潛在函數為式（20）的分布式計算遷移博弈是潛在博弈，因此總有一個納什均衡和具有限改進特性。

3.2 優化算法

由引理1 可知，當移動節點按式（19）進行計算遷移決策時，該決策是最佳計算遷移策略。根據定理1，當所有移動節點都執行最佳計算遷移策略時，通過有限策略改進，總能達到一個納什均衡，使得所有節點都相互滿意，從而達到系統總的學習延遲最小?；谝陨戏治?，本文提出一種啟發式算法——能量約束的延遲貪婪算法來求解2.2 節的計算遷移優化問題。如算法1 所示，ECDG 由二階決策組成。在第一階段，設計一種延遲貪婪決策，使得每個移動節點按式（19）來確定自身初步的計算遷移策略。然后在第二階段，采用能量約束決策更新來改進部分移動節點的計算遷移決策。通過有限次改進，最終使系統達到計算遷移納什均衡。此時，任一移動節點都不能通過調整自身的策略來進一步降低自身的學習延遲，該計算遷移策略就是能使系統平均學習延遲最小化的最佳計算遷移策略，也就是2.2節問題的解。

如算法1 的步驟2 所示，在延遲貪婪決策階段，當移動節點的能量同時支持集中學習和聯邦學習這兩個機器學習模型時，則根據引理1，選擇一個使學習延遲最小的動作（最佳策略），見算法1的步驟2.3。例如，如果集中學習能使學習延遲最小，則決策為計算遷移，等效于選擇集中學習模型；否則，選擇一個可以滿足能量約束的動作。

由于學習模型中移動節點的數量會影響每個加入的移動節點的學習延遲，某些先加入的移動節點在更改其計算遷移決策后將會獲得更低的學習延遲。因此，為了達到系統和每個移動節點的最低延遲，從而達到系統納什均衡，在能量約束決策更新階段，通過迭代更新的方式將某些移動節點的計算遷移策略進行更新，使每次決策更新都能降低移動節點和系統的學習延遲（見算法1的步驟3.2.3～3.2.4），直到更新不能進一步降低系統延遲（見算法1的步驟3.3），則此時的計算遷移決策就是使系統平均學習延遲最低的決策，具體如算法1的步驟3所示。

4 仿真與分析

4.1 仿真環境

本文使用Matlab2016Rb 結合TensorFlow 進行MEC 系統的仿真。仿真采用圖1～2 所示的系統架構和機器學習模型：一個MEC 系統中有多個具有計算能力的移動節點和一個邊緣服務器。在每次仿真中，每個移動節點都有一個目標分類的計算任務和獨立的圖像數據集。每個移動節點的數據集來源于MNIST［19］。所述MNIST圖像數據庫包含了6萬個訓練樣本和1 萬個具有10 個對象類別（10 個數字）的測試樣本。當移動節點的計算遷移決策是遷移計算時，表示該移動節點選擇集中學習模型，并要將數據集遷移到邊緣服務器；否則，表示選擇聯邦學習模型進行數據訓練，移動節點本地執行計算任務，數據集不需要離開本地。

仿真用到的參數包括：移動節點數量M=300，數據集大小在區間［160，640］KB 內均勻分布，樣本數量在區間［1 000，4 000］內均勻分布，聯邦學習模型參數數據包大小為SMsg=1 500 B，平均數據傳輸速率Rm=1.0 Mb/s，移動節點m∈Ω的最大可用能量均勻分布在區間［10-6，0.1］W。發射功率因子為=0.18×10-3，βm=10-14，集中學習的每批樣本的大小為BC=100，聯邦學習的每批樣本的大小為Bm=100，聯邦學習模型中本地訓練迭代次數NL=5，集中學習和聯邦學習的模型訓練輪次因子為αC=αF=10 000，集中學習和聯邦學習模型的最大輪次=2 000，移動節點和邊緣服務器的平均每批樣本的訓練延遲分別為=0.32 s（從1.5 GHz CPU 的Raspberry PI 4B測試獲?。┖?0.13 s（從RTX2080TI-GPU的服務器測試獲?。?，模型訓練目標精度為0.95。

將本文算法ECDG 與集中式貪婪算法和面向聯邦學習模型的客戶選擇（FedCS）算法［20］進行對比。在集中式貪婪算法中，除了能量受限的節點，所有移動節點都貪婪地選擇集中學習模型。在FedCS 算法中，將移動節點按本地計算延遲升序排列，從本地計算延遲最小的節點開始，逐漸將節點加入聯邦學習模型，當聯邦學習的單輪訓練延遲超過閾值時，停止增加移動節點，剩下的移動節點將選擇集中學習模型，但是，在加入聯邦學習的移動節點中，可用能量小于消耗能量的節點將從聯邦學習模型修改為集中學習模型。在仿真中，設置了兩個聯邦學習單輪訓練延遲閾值，分別是=10 s 和=30 s。

4.2 不同移動節點數量下的算法性能比較

為了評估ECDG 計算遷移策略的有效性，在仿真中通過改變移動節點的數量來觀察不同算法下系統平均學習延遲的性能，結果如圖3所示。從圖3可看出，當移動節點數量M≥50時，ECDG 的平均學習延遲明顯低于基準算法，約是集中式貪婪算法的1/10，是FedCS 算法的1/5，因此其延遲性能優于基準算法。

圖3 平均學習延遲vs.移動節點數量Fig.3 Average learning delay vs.number of mobile nodes

圖4所示是MEC系統中選擇聯邦學習的移動節點比例隨著移動節點數量的變化而變化的情況。從圖4 可以看出，在ECDG 算法中，隨著移動節點數量的增加，選擇聯邦學習模型的移動節點也隨之增加，因此：a）根據式（15），ECDG 中聯邦學習所需的輪數少于集中式貪婪算法和FedCS 算法；b）由于ECDG 中選擇集中學習的移動節點數量低于集中式貪婪算法和FedCS 算法，根據式（2），其數據上傳延遲也比集中式貪婪算法和FedCS 算法要低。因此，當MEC 系統中的移動節點數量較高（例如M≥50）時，通過給定模型訓練目標精度，與集中式貪婪算法和FedCS 算法相比，ECDG 能有效降低平均學習延遲。

圖4 選擇聯邦學習的移動節點比例vs.移動節點數量Fig.4 Ratio of mobile nodes selecting federated learning vs.number of mobile nodes

4.3 不同數據集范圍下的算法性能比較

為了評估數據集大小對算法性能的影響，接下來通過改變數據集的范圍來比較ECDG、集中式貪婪算法和FedCS算法的性能。在仿真中，設置移動節點數量M=300。設置移動節點的數據集大小在Smin和Smax之間均勻分布，其中最小數據集的樣本數為Smin=200；其他參數按默認設置。所有數據集的樣本均來自MNIST［19］。

從圖5 所示的仿真結果可看出，集中式貪婪算法的平均學習延遲隨著Smax的增加線性上升。這是因為，在集中式貪婪算法中，邊緣服務器中的訓練樣本總數隨著Smax的增加線性增加，因此其訓練延遲也線性增加。

如圖5 所示，當最大數據集的樣本數為Smax=1 000 時，=30 s 時的FedCS 算法及ECDG 算法的平均學習延遲接近。然而，當Smax大于某些值時，FedCS算法的平均學習延遲會隨著Smax的上升而增大，如，當最大數據集的樣本數為1 000 時，=10 s；當最大數據集的樣本數為2 000時，=30 s。

圖5 平均學習延遲vs.數據集大小Fig.5 Average learning delay vs.dataset size

如圖5 所示，在不同的Smax下，ECDG 算法提供的學習平均延遲都低于集中式貪婪算法及FedCS 算法。這是因為，由于移動節點數量較大（300個節點），ECDG 算法中選擇聯邦學習模型的移動節點比例較高，如圖6 所示。因此，即使數據集的最大值Smax增大，但聯邦學習模型中的單輪本地訓練延遲上升較慢，因此，其平均學習延遲隨著Smax的上升而上升較慢。

圖6 選擇聯邦學習的移動節點比例vs.數據集大小Fig.6 Ratio of mobile nodes selecting federated learning vs.dataset size

圖3 和圖5 的仿真結果表明，在相同的移動節點數量、數據集范圍下，與集中式貪婪算法及FedCS 算法相比，ECDG 的平均學習延遲都最小，約是集中式貪婪算法的1/10，是FedCS算法的1/5。當MEC 系統的移動節點數量較大，或數據集較大時，ECDG 算法選擇聯邦學習模型的移動節點比例也高于集中式貪婪算法及FedCS算法。

4.4 算法復雜度分析

由算法1 可知，算法的復雜度是移動節點數量M和決策更新次數K的函數，因此，算法1 的復雜度可以表示為O(KM)。

從圖7 所示的本文算法收斂率可看出，系統平均學習延遲隨著決策更新的遞增而下降。一般經過幾次（例如，K=2）更新后，可以達到算法收斂。

圖7 本文算法的收斂率Fig.7 Convergence rate of proposed algorithm

5 結語

為了降低邊緣計算環境中機器學習的延遲，提出了集中學習和聯邦學習共存的ECDG計算遷移算法。建立MEC系統中集中學習、聯邦學習的模型，對這兩種機器學習模型的學習延遲、能耗進行數學建模，以移動節點的能量為約束、系統平均學習延遲最小化為目標建立計算遷移優化模型。接著，提出了ECDG 計算遷移算法，通過延遲貪婪決策和能量約束決策更新二階策略來獲得優化的計算遷移策略，通過計算遷移策略自動為移動節點選擇合適的機器學習模型（如：集中學習或聯邦學習），從而降低系統平均學習延遲。實驗結果表明，ECDG 算法能夠有效降低系統平均學習延遲，滿足延遲敏感型機器學習應用的服務質量要求。