移動(dòng)邊緣計(jì)算環(huán)境中面向機(jī)器學(xué)習(xí)的計(jì)算遷移策略

郭 棉，張錦友

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

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

0 引言

隨著人工智能和物聯(lián)網(wǎng)（Internet of Things，IoT）技術(shù)的發(fā)展，涌現(xiàn)了越來(lái)越多的先進(jìn)物聯(lián)網(wǎng)應(yīng)用，例如，虛擬現(xiàn)實(shí)、自動(dòng)駕駛和工業(yè)自動(dòng)化等［1］。這些應(yīng)用以數(shù)據(jù)為驅(qū)動(dòng)，通過(guò)機(jī)器學(xué)習(xí)算法獲取數(shù)據(jù)價(jià)值，進(jìn)而實(shí)現(xiàn)預(yù)測(cè)、控制以及其他智能化操作。通常，機(jī)器學(xué)習(xí)算法是部署在網(wǎng)絡(luò)中心的高性能云服務(wù)器上的，應(yīng)用產(chǎn)生的海量數(shù)據(jù)需要上傳到云端的機(jī)器學(xué)習(xí)服務(wù)器上才能被處理。然而，該范式已經(jīng)難以滿足物聯(lián)網(wǎng)應(yīng)用的海量連接、超低延遲的服務(wù)要求。首先，從數(shù)據(jù)源到云端機(jī)器學(xué)習(xí)服務(wù)器的網(wǎng)絡(luò)傳輸延遲一般為幾百毫秒以上，已成為低延遲的瓶頸［2］；其次，數(shù)據(jù)往往具有安全性和隱私性要求，僅僅為了數(shù)據(jù)分析的目的而將數(shù)據(jù)傳輸?shù)焦苍频姆绞讲⒉豢扇。?］。

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

研究學(xué)者對(duì)如何在移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)中部署機(jī)器學(xué)習(xí)進(jìn)行了積極的研究。Li等［9］提出了一種深度強(qiáng)化學(xué)習(xí)方法來(lái)將任務(wù)分配到不同的邊緣服務(wù)器進(jìn)行處理；Zhu 等［10］設(shè)計(jì)了一套在無(wú)線網(wǎng)絡(luò)邊緣運(yùn)行機(jī)器學(xué)習(xí)的通信和計(jì)算規(guī)則；Mahmoudi 等［11］提出了一種在無(wú)線環(huán)境中實(shí)現(xiàn)分布式機(jī)器學(xué)習(xí)的優(yōu)化算法；羅長(zhǎng)銀等［12］提出了一種面向區(qū)塊鏈的在線聯(lián)邦增量學(xué)習(xí)算法。但是，現(xiàn)有的研究?jī)H考慮移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)中的一種機(jī)器學(xué)習(xí)模型，例如，文獻(xiàn)［9］面向的是移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)的集中學(xué)習(xí)，文獻(xiàn)［11-12］面向的是分布式機(jī)器學(xué)習(xí)。實(shí)際上，隨著物聯(lián)網(wǎng)終端（數(shù)據(jù)源）和物聯(lián)網(wǎng)應(yīng)用的快速增長(zhǎng)，由于無(wú)線網(wǎng)絡(luò)資源受限性、終端能耗和計(jì)算節(jié)點(diǎn)計(jì)算能力的異構(gòu)性，在一個(gè)移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)內(nèi)僅運(yùn)行單一的機(jī)器學(xué)習(xí)模式（例如，僅采用集中學(xué)習(xí)，或僅采用聯(lián)邦學(xué)習(xí)）將使機(jī)器學(xué)習(xí)性能非常低下。

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

1 系統(tǒng)建模

1.1 系統(tǒng)架構(gòu)

考慮一個(gè)由多個(gè)具有計(jì)算能力的移動(dòng)節(jié)點(diǎn)和一個(gè)邊緣服務(wù)器構(gòu)成的MEC 系統(tǒng)。在該系統(tǒng)中，移動(dòng)節(jié)點(diǎn)隨機(jī)地分布在無(wú)線網(wǎng)絡(luò)的覆蓋區(qū)域，邊緣服務(wù)器位于無(wú)線網(wǎng)絡(luò)的中心（例如，基站）。每個(gè)移動(dòng)節(jié)點(diǎn)接收來(lái)自附近物聯(lián)網(wǎng)傳感器的數(shù)據(jù)（例如，視頻、溫濕度數(shù)據(jù)等），然后產(chǎn)生計(jì)算任務(wù)（例如，自動(dòng)駕駛的路況識(shí)別［13］、工作區(qū)間的環(huán)境監(jiān)測(cè)［14］等）。由于每個(gè)移動(dòng)節(jié)點(diǎn)僅接收附近物聯(lián)網(wǎng)傳感器的數(shù)據(jù)，其數(shù)據(jù)集樣本僅包含了物聯(lián)網(wǎng)應(yīng)用所需的局部信息，具有非獨(dú)立同分布性。因此，機(jī)器學(xué)習(xí)的準(zhǔn)確性要求使用多個(gè)數(shù)據(jù)集進(jìn)行訓(xùn)練。此外，本文假設(shè)每個(gè)計(jì)算節(jié)點(diǎn)，包括移動(dòng)節(jié)點(diǎn)和邊緣服務(wù)器，都部署了機(jī)器學(xué)習(xí)算法，而且移動(dòng)節(jié)點(diǎn)的計(jì)算能力低于邊緣服務(wù)器的計(jì)算能力。

假設(shè)該MEC 系統(tǒng)主要提供兩種機(jī)器學(xué)習(xí)模型，包括集中學(xué)習(xí)模型和聯(lián)邦學(xué)習(xí)模型。每個(gè)移動(dòng)節(jié)點(diǎn)僅能選擇其中一種模型來(lái)執(zhí)行計(jì)算任務(wù)。若某個(gè)移動(dòng)節(jié)點(diǎn)選擇集中學(xué)習(xí)，如圖1 所示，它的計(jì)算任務(wù)和數(shù)據(jù)集都將遷移到邊緣服務(wù)器。邊緣服務(wù)器匯聚數(shù)據(jù)集后執(zhí)行機(jī)器學(xué)習(xí)算法訓(xùn)練模型，然后將訓(xùn)練的結(jié)果返回給該節(jié)點(diǎn)。

圖1 集中學(xué)習(xí)模型Fig.1 Centralized learning model

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

圖2 聯(lián)邦學(xué)習(xí)模型Fig.2 Federated learning model

基于上述分析，機(jī)器學(xué)習(xí)模型的選擇問(wèn)題可以等效為計(jì)算遷移問(wèn)題。令Ω={1，2，…，M}表示MEC 系統(tǒng)的移動(dòng)節(jié)點(diǎn)集合。令π=(I1，I2，…，IM)表示移動(dòng)節(jié)點(diǎn)的計(jì)算遷移決策向量。對(duì)任意的移動(dòng)節(jié)點(diǎn)m∈Ω，當(dāng)Im=0時(shí)，表示數(shù)據(jù)不遷移，等效于移動(dòng)節(jié)點(diǎn)m選擇聯(lián)邦學(xué)習(xí)模型；否則，Im=1 表示選擇集中學(xué)習(xí)，此時(shí)，該節(jié)點(diǎn)需要將數(shù)據(jù)集和任務(wù)遷移到邊緣服務(wù)器。接下來(lái)分析移動(dòng)節(jié)點(diǎn)選擇不同的機(jī)器學(xué)習(xí)模型時(shí)所經(jīng)歷的學(xué)習(xí)延遲。

1.2 集中學(xué)習(xí)延遲

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

其中：DC，Tx是數(shù)據(jù)上傳延遲；DC，CPU是集中學(xué)習(xí)訓(xùn)練延遲。

本文假設(shè)同步訓(xùn)練模式，也就是邊緣服務(wù)器等待所有數(shù)據(jù)到達(dá)后才開始訓(xùn)練。因此，數(shù)據(jù)上傳延遲DC，Tx是從移動(dòng)節(jié)點(diǎn)將數(shù)據(jù)集上傳給邊緣服務(wù)器到邊緣服務(wù)器接收到所有選擇集中學(xué)習(xí)的移動(dòng)節(jié)點(diǎn)的數(shù)據(jù)集的時(shí)間間隔。假設(shè)這些移動(dòng)節(jié)點(diǎn)同時(shí)上傳數(shù)據(jù)，則數(shù)據(jù)上傳延遲等效為：所有選擇集中學(xué)習(xí)的移動(dòng)節(jié)點(diǎn)當(dāng)中，數(shù)據(jù)上傳延遲最大的節(jié)點(diǎn)所經(jīng)歷的數(shù)據(jù)上傳延遲。因此，集中學(xué)習(xí)的數(shù)據(jù)上傳延遲為：

根據(jù)機(jī)器學(xué)習(xí)原理［15-16］，當(dāng)邊緣服務(wù)器運(yùn)行集中學(xué)習(xí)時(shí)，需要對(duì)數(shù)據(jù)集進(jìn)行多輪分批訓(xùn)練，直到得到一個(gè)穩(wěn)定的優(yōu)化模型。因此，邊緣服務(wù)器的集中學(xué)習(xí)訓(xùn)練延遲可以表示為單批樣本訓(xùn)練延遲的函數(shù)：

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

1.3 聯(lián)邦學(xué)習(xí)延遲

設(shè)MEC 中選擇本地計(jì)算（即聯(lián)邦學(xué)習(xí)模型）的移動(dòng)節(jié)點(diǎn)集合為ΩF?Ω，則對(duì)于任意的m∈ΩF，Im=0 成立。根據(jù)1.1節(jié)的MEC 系統(tǒng)聯(lián)邦學(xué)習(xí)機(jī)制，聯(lián)邦學(xué)習(xí)延遲是多輪訓(xùn)練延遲的總和，而每輪延遲可以進(jìn)一步分為一個(gè)通信來(lái)回的延遲（移動(dòng)節(jié)點(diǎn)上傳本地模型參數(shù)和聯(lián)邦服務(wù)器下發(fā)全局模型參數(shù)的延遲之和）以及單輪聯(lián)邦學(xué)習(xí)的訓(xùn)練延遲，因此，移動(dòng)節(jié)點(diǎn)m∈ΩF的聯(lián)邦學(xué)習(xí)延遲可以表示為：

其中：NF表示聯(lián)邦學(xué)習(xí)的輪數(shù)；是單輪通信來(lái)回的延遲；DF，CPU是單輪聯(lián)邦學(xué)習(xí)的訓(xùn)練延遲。

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

由于移動(dòng)節(jié)點(diǎn)本地訓(xùn)練的初始化模型參數(shù)是由聯(lián)邦服務(wù)器下發(fā)，而且移動(dòng)節(jié)點(diǎn)上傳的模型參數(shù)數(shù)據(jù)類型與聯(lián)邦服務(wù)器下發(fā)的全局模型參數(shù)的類型也一致，因此，在式（5）中，本文假設(shè)了移動(dòng)節(jié)點(diǎn)上傳的模型參數(shù)數(shù)據(jù)包與聯(lián)邦服務(wù)器下發(fā)的全局模型參數(shù)數(shù)據(jù)包大小相等，從而單輪通信延遲可表示為單向通信延遲的2倍。

文獻(xiàn)［7］指出，為了減少通信次數(shù)（減小NF），可以增大單輪本地訓(xùn)練的次數(shù)，等效于每個(gè)移動(dòng)節(jié)點(diǎn)可以在單輪中進(jìn)行多次迭代的本地訓(xùn)練。因此，移動(dòng)節(jié)點(diǎn)m的單輪本地訓(xùn)練延遲可以表示為：

假設(shè)采用同步聯(lián)邦學(xué)習(xí)模型，也就是聯(lián)邦服務(wù)器等所有的本地訓(xùn)練模型參數(shù)都上傳后才匯聚更新全局模型參數(shù)，則單輪的聯(lián)邦學(xué)習(xí)的本地訓(xùn)練延遲就是所有參與聯(lián)邦學(xué)習(xí)的移動(dòng)節(jié)點(diǎn)所提供的本地訓(xùn)練延遲中最大的一個(gè)延遲，因此，單輪聯(lián)邦學(xué)習(xí)的本地訓(xùn)練延遲表示為：

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

2 問(wèn)題建模

本章首先分析移動(dòng)節(jié)點(diǎn)的能耗模型，然后對(duì)基于機(jī)器學(xué)習(xí)的計(jì)算遷移問(wèn)題進(jìn)行數(shù)學(xué)建模。

2.1 能耗建模

由于邊緣服務(wù)器可以通過(guò)持續(xù)供電的方式提供能源，本文只考慮能量受限的移動(dòng)節(jié)點(diǎn)的能耗。根據(jù)1.1 節(jié)所述的系統(tǒng)模型，移動(dòng)節(jié)點(diǎn)m∈Ω的能耗可以表述為：

進(jìn)一步地，在集中學(xué)習(xí)模式中，移動(dòng)節(jié)點(diǎn)僅需要將數(shù)據(jù)上傳給邊緣服務(wù)器。當(dāng)選擇該模型時(shí)，移動(dòng)節(jié)點(diǎn)僅消耗網(wǎng)絡(luò)傳輸能耗。根據(jù)參考文獻(xiàn)［17］，網(wǎng)絡(luò)傳輸能耗與數(shù)據(jù)所經(jīng)歷的網(wǎng)絡(luò)傳輸延遲相關(guān)，因此，可表述為：

在聯(lián)邦學(xué)習(xí)模型中，移動(dòng)節(jié)點(diǎn)既要參與計(jì)算又要傳輸模型參數(shù)。因此，當(dāng)移動(dòng)節(jié)點(diǎn)m∈Ω選擇聯(lián)邦學(xué)習(xí)模型進(jìn)行任務(wù)處理時(shí)，其能耗是傳輸能耗與計(jì)算能耗的和，根據(jù)文獻(xiàn)［17］中的邊緣計(jì)算系統(tǒng)的傳輸能耗和計(jì)算能耗模型，經(jīng)過(guò)簡(jiǎn)單的計(jì)算和推導(dǎo)，有：

2.2 優(yōu)化目標(biāo)

根據(jù)1.1節(jié)的系統(tǒng)模型，移動(dòng)節(jié)點(diǎn)的學(xué)習(xí)延遲可表述為：

則系統(tǒng)的平均學(xué)習(xí)延遲是所有移動(dòng)節(jié)點(diǎn)的學(xué)習(xí)延遲的均值，即：

因此，能耗限制的多機(jī)器學(xué)習(xí)模型下移動(dòng)邊緣計(jì)算系統(tǒng)的延遲優(yōu)化計(jì)算遷移問(wèn)題可以建模為：

其中：式（13）是移動(dòng)節(jié)點(diǎn)的能量約束，是移動(dòng)節(jié)點(diǎn)的最大可用能量；式（14）是集中學(xué)習(xí)需要訓(xùn)練的輪次；式（15）是聯(lián)邦學(xué)習(xí)需要訓(xùn)練的輪次。不管是集中學(xué)習(xí)還是聯(lián)邦學(xué)習(xí)，模型的準(zhǔn)確度都與參與訓(xùn)練的數(shù)據(jù)集多少（等效于，參與訓(xùn)練的移動(dòng)節(jié)點(diǎn)數(shù)）相關(guān)［16］，因此，在模型準(zhǔn)確度限制下，集中學(xué)習(xí)和聯(lián)邦學(xué)習(xí)的訓(xùn)練輪次可以分別表示為：

其中：‖ · ‖表示數(shù)組內(nèi)元素的數(shù)量；αC和αF分別是模型訓(xùn)練輪次因子。此外，為了避免訓(xùn)練時(shí)間過(guò)長(zhǎng)，本文為集中學(xué)習(xí)和聯(lián)邦學(xué)習(xí)分別設(shè)置了最大輪次，分別如式（14）和（15）右邊所示。

3 ECDG

3.1 計(jì)算遷移博弈分析

針對(duì)2.2 節(jié)的計(jì)算遷移優(yōu)化問(wèn)題，本文考慮分布式?jīng)Q策：每個(gè)移動(dòng)節(jié)點(diǎn)基于系統(tǒng)狀態(tài)和其他移動(dòng)節(jié)點(diǎn)的決策執(zhí)行自己的計(jì)算遷移（等效于機(jī)器學(xué)習(xí)模型選擇）決策。假設(shè)每個(gè)移動(dòng)節(jié)點(diǎn)都是自私的，而且以自身的能量為約束（見式（13））、以最小化自己的學(xué)習(xí)延遲為目標(biāo)執(zhí)行計(jì)算遷移決策。當(dāng)且僅當(dāng)計(jì)算遷移決策更新（例如，從集中學(xué)習(xí)模式轉(zhuǎn)換為聯(lián)邦學(xué)習(xí)模式）能降低學(xué)習(xí)延遲時(shí)，移動(dòng)節(jié)點(diǎn)才執(zhí)行計(jì)算遷移決策更新。

令Ι-m=(I1，I2，…，Im-1，Im+1，…，IM)表示移動(dòng)節(jié)點(diǎn)m獲得的其他移動(dòng)節(jié)點(diǎn)的計(jì)算遷移決策，給定I-m，則根據(jù)式（12）～（15），移動(dòng)節(jié)點(diǎn)m的計(jì)算遷移決策就是使得它自身的學(xué)習(xí)延遲最小：s.t.式（13）～（15）。

上述問(wèn)題可以構(gòu)建為一個(gè)計(jì)算遷移策略博弈G=)。其中，博弈選手集合就是移動(dòng)節(jié)點(diǎn)集合Ω，選手m的策略就是移動(dòng)節(jié)點(diǎn)m的計(jì)算遷移策略Im={0，1}，選手m期望最小化的成本函數(shù)就是移動(dòng)節(jié)點(diǎn)m的學(xué)習(xí)延遲Dm(Im，I-m)。

為了求解上述博弈問(wèn)題，定義計(jì)算遷移博弈的納什均衡如下：

定義1計(jì)算遷移博弈的納什均衡。當(dāng)在均衡點(diǎn)π*，沒(méi)有任何移動(dòng)節(jié)點(diǎn)可以通過(guò)單方面修改自身的決策來(lái)進(jìn)一步減少自身的成本時(shí)，該決策配置π*=被稱為計(jì)算遷移博弈的納什均衡，因此，對(duì)所有m∈Ω，該決策配置滿足條件：

定義1 表明，當(dāng)達(dá)到納什均衡時(shí)，當(dāng)前的計(jì)算遷移策略是相互滿足的策略，任一移動(dòng)節(jié)點(diǎn)都不能通過(guò)單方面的策略調(diào)整來(lái)進(jìn)一步降低自身的學(xué)習(xí)延遲，因而沒(méi)有節(jié)點(diǎn)愿意更改決策。

為了進(jìn)一步獲得納什均衡的計(jì)算遷移決策，接下來(lái)定義計(jì)算遷移博弈的最佳策略如下：

定義2最佳計(jì)算遷移策略。給定其他移動(dòng)節(jié)點(diǎn)的策略I-m，當(dāng)移動(dòng)節(jié)點(diǎn)m∈Ω的計(jì)算遷移策略滿足條件式（18）時(shí)，該策略被稱為最佳計(jì)算遷移策略。

根據(jù)定義2 可知，在給定其他移動(dòng)節(jié)點(diǎn)的策略下，當(dāng)移動(dòng)節(jié)點(diǎn)采用最佳計(jì)算遷移策略時(shí)將獲得自身最小的學(xué)習(xí)延遲。

根據(jù)定義1～2，對(duì)于2.2 節(jié)所述的計(jì)算遷移問(wèn)題，有如下引理。

引理1對(duì)于任意的移動(dòng)節(jié)點(diǎn)m∈Ω，假設(shè)Em≤成立，則給定其他移動(dòng)節(jié)點(diǎn)的計(jì)算遷移決策I-m，該移動(dòng)節(jié)點(diǎn)的最佳策略如下：

由此，可得如下定理。

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

3.2 優(yōu)化算法

由引理1 可知，當(dāng)移動(dòng)節(jié)點(diǎn)按式（19）進(jìn)行計(jì)算遷移決策時(shí)，該決策是最佳計(jì)算遷移策略。根據(jù)定理1，當(dāng)所有移動(dòng)節(jié)點(diǎn)都執(zhí)行最佳計(jì)算遷移策略時(shí)，通過(guò)有限策略改進(jìn)，總能達(dá)到一個(gè)納什均衡，使得所有節(jié)點(diǎn)都相互滿意，從而達(dá)到系統(tǒng)總的學(xué)習(xí)延遲最小?；谝陨戏治觯疚奶岢鲆环N啟發(fā)式算法——能量約束的延遲貪婪算法來(lái)求解2.2 節(jié)的計(jì)算遷移優(yōu)化問(wèn)題。如算法1 所示，ECDG 由二階決策組成。在第一階段，設(shè)計(jì)一種延遲貪婪決策，使得每個(gè)移動(dòng)節(jié)點(diǎn)按式（19）來(lái)確定自身初步的計(jì)算遷移策略。然后在第二階段，采用能量約束決策更新來(lái)改進(jìn)部分移動(dòng)節(jié)點(diǎn)的計(jì)算遷移決策。通過(guò)有限次改進(jìn)，最終使系統(tǒng)達(dá)到計(jì)算遷移納什均衡。此時(shí)，任一移動(dòng)節(jié)點(diǎn)都不能通過(guò)調(diào)整自身的策略來(lái)進(jìn)一步降低自身的學(xué)習(xí)延遲，該計(jì)算遷移策略就是能使系統(tǒng)平均學(xué)習(xí)延遲最小化的最佳計(jì)算遷移策略，也就是2.2節(jié)問(wèn)題的解。

如算法1 的步驟2 所示，在延遲貪婪決策階段，當(dāng)移動(dòng)節(jié)點(diǎn)的能量同時(shí)支持集中學(xué)習(xí)和聯(lián)邦學(xué)習(xí)這兩個(gè)機(jī)器學(xué)習(xí)模型時(shí)，則根據(jù)引理1，選擇一個(gè)使學(xué)習(xí)延遲最小的動(dòng)作（最佳策略），見算法1的步驟2.3。例如，如果集中學(xué)習(xí)能使學(xué)習(xí)延遲最小，則決策為計(jì)算遷移，等效于選擇集中學(xué)習(xí)模型；否則，選擇一個(gè)可以滿足能量約束的動(dòng)作。

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

4 仿真與分析

4.1 仿真環(huán)境

本文使用Matlab2016Rb 結(jié)合TensorFlow 進(jìn)行MEC 系統(tǒng)的仿真。仿真采用圖1～2 所示的系統(tǒng)架構(gòu)和機(jī)器學(xué)習(xí)模型：一個(gè)MEC 系統(tǒng)中有多個(gè)具有計(jì)算能力的移動(dòng)節(jié)點(diǎn)和一個(gè)邊緣服務(wù)器。在每次仿真中，每個(gè)移動(dòng)節(jié)點(diǎn)都有一個(gè)目標(biāo)分類的計(jì)算任務(wù)和獨(dú)立的圖像數(shù)據(jù)集。每個(gè)移動(dòng)節(jié)點(diǎn)的數(shù)據(jù)集來(lái)源于MNIST［19］。所述MNIST圖像數(shù)據(jù)庫(kù)包含了6萬(wàn)個(gè)訓(xùn)練樣本和1 萬(wàn)個(gè)具有10 個(gè)對(duì)象類別（10 個(gè)數(shù)字）的測(cè)試樣本。當(dāng)移動(dòng)節(jié)點(diǎn)的計(jì)算遷移決策是遷移計(jì)算時(shí)，表示該移動(dòng)節(jié)點(diǎn)選擇集中學(xué)習(xí)模型，并要將數(shù)據(jù)集遷移到邊緣服務(wù)器；否則，表示選擇聯(lián)邦學(xué)習(xí)模型進(jìn)行數(shù)據(jù)訓(xùn)練，移動(dòng)節(jié)點(diǎn)本地執(zhí)行計(jì)算任務(wù)，數(shù)據(jù)集不需要離開本地。

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

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

4.2 不同移動(dòng)節(jié)點(diǎn)數(shù)量下的算法性能比較

為了評(píng)估ECDG 計(jì)算遷移策略的有效性，在仿真中通過(guò)改變移動(dòng)節(jié)點(diǎn)的數(shù)量來(lái)觀察不同算法下系統(tǒng)平均學(xué)習(xí)延遲的性能，結(jié)果如圖3所示。從圖3可看出，當(dāng)移動(dòng)節(jié)點(diǎn)數(shù)量M≥50時(shí)，ECDG 的平均學(xué)習(xí)延遲明顯低于基準(zhǔn)算法，約是集中式貪婪算法的1/10，是FedCS 算法的1/5，因此其延遲性能優(yōu)于基準(zhǔn)算法。

圖3 平均學(xué)習(xí)延遲vs.移動(dòng)節(jié)點(diǎn)數(shù)量Fig.3 Average learning delay vs.number of mobile nodes

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

圖4 選擇聯(lián)邦學(xué)習(xí)的移動(dòng)節(jié)點(diǎn)比例vs.移動(dòng)節(jié)點(diǎn)數(shù)量Fig.4 Ratio of mobile nodes selecting federated learning vs.number of mobile nodes

4.3 不同數(shù)據(jù)集范圍下的算法性能比較

為了評(píng)估數(shù)據(jù)集大小對(duì)算法性能的影響，接下來(lái)通過(guò)改變數(shù)據(jù)集的范圍來(lái)比較ECDG、集中式貪婪算法和FedCS算法的性能。在仿真中，設(shè)置移動(dòng)節(jié)點(diǎn)數(shù)量M=300。設(shè)置移動(dòng)節(jié)點(diǎn)的數(shù)據(jù)集大小在Smin和Smax之間均勻分布，其中最小數(shù)據(jù)集的樣本數(shù)為Smin=200；其他參數(shù)按默認(rèn)設(shè)置。所有數(shù)據(jù)集的樣本均來(lái)自MNIST［19］。

從圖5 所示的仿真結(jié)果可看出，集中式貪婪算法的平均學(xué)習(xí)延遲隨著Smax的增加線性上升。這是因?yàn)椋诩惺截澙匪惴ㄖ?，邊緣服?wù)器中的訓(xùn)練樣本總數(shù)隨著Smax的增加線性增加，因此其訓(xùn)練延遲也線性增加。

如圖5 所示，當(dāng)最大數(shù)據(jù)集的樣本數(shù)為Smax=1 000 時(shí)，=30 s 時(shí)的FedCS 算法及ECDG 算法的平均學(xué)習(xí)延遲接近。然而，當(dāng)Smax大于某些值時(shí)，F(xiàn)edCS算法的平均學(xué)習(xí)延遲會(huì)隨著Smax的上升而增大，如，當(dāng)最大數(shù)據(jù)集的樣本數(shù)為1 000 時(shí)，=10 s；當(dāng)最大數(shù)據(jù)集的樣本數(shù)為2 000時(shí)，=30 s。

圖5 平均學(xué)習(xí)延遲vs.數(shù)據(jù)集大小Fig.5 Average learning delay vs.dataset size

如圖5 所示，在不同的Smax下，ECDG 算法提供的學(xué)習(xí)平均延遲都低于集中式貪婪算法及FedCS 算法。這是因?yàn)?，由于移?dòng)節(jié)點(diǎn)數(shù)量較大（300個(gè)節(jié)點(diǎn)），ECDG 算法中選擇聯(lián)邦學(xué)習(xí)模型的移動(dòng)節(jié)點(diǎn)比例較高，如圖6 所示。因此，即使數(shù)據(jù)集的最大值Smax增大，但聯(lián)邦學(xué)習(xí)模型中的單輪本地訓(xùn)練延遲上升較慢，因此，其平均學(xué)習(xí)延遲隨著Smax的上升而上升較慢。

圖6 選擇聯(lián)邦學(xué)習(xí)的移動(dòng)節(jié)點(diǎn)比例vs.數(shù)據(jù)集大小Fig.6 Ratio of mobile nodes selecting federated learning vs.dataset size

圖3 和圖5 的仿真結(jié)果表明，在相同的移動(dòng)節(jié)點(diǎn)數(shù)量、數(shù)據(jù)集范圍下，與集中式貪婪算法及FedCS 算法相比，ECDG 的平均學(xué)習(xí)延遲都最小，約是集中式貪婪算法的1/10，是FedCS算法的1/5。當(dāng)MEC 系統(tǒng)的移動(dòng)節(jié)點(diǎn)數(shù)量較大，或數(shù)據(jù)集較大時(shí)，ECDG 算法選擇聯(lián)邦學(xué)習(xí)模型的移動(dòng)節(jié)點(diǎn)比例也高于集中式貪婪算法及FedCS算法。

4.4 算法復(fù)雜度分析

由算法1 可知，算法的復(fù)雜度是移動(dòng)節(jié)點(diǎn)數(shù)量M和決策更新次數(shù)K的函數(shù)，因此，算法1 的復(fù)雜度可以表示為O(KM)。

從圖7 所示的本文算法收斂率可看出，系統(tǒng)平均學(xué)習(xí)延遲隨著決策更新的遞增而下降。一般經(jīng)過(guò)幾次（例如，K=2）更新后，可以達(dá)到算法收斂。

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

5 結(jié)語(yǔ)

為了降低邊緣計(jì)算環(huán)境中機(jī)器學(xué)習(xí)的延遲，提出了集中學(xué)習(xí)和聯(lián)邦學(xué)習(xí)共存的ECDG計(jì)算遷移算法。建立MEC系統(tǒng)中集中學(xué)習(xí)、聯(lián)邦學(xué)習(xí)的模型，對(duì)這兩種機(jī)器學(xué)習(xí)模型的學(xué)習(xí)延遲、能耗進(jìn)行數(shù)學(xué)建模，以移動(dòng)節(jié)點(diǎn)的能量為約束、系統(tǒng)平均學(xué)習(xí)延遲最小化為目標(biāo)建立計(jì)算遷移優(yōu)化模型。接著，提出了ECDG 計(jì)算遷移算法，通過(guò)延遲貪婪決策和能量約束決策更新二階策略來(lái)獲得優(yōu)化的計(jì)算遷移策略，通過(guò)計(jì)算遷移策略自動(dòng)為移動(dòng)節(jié)點(diǎn)選擇合適的機(jī)器學(xué)習(xí)模型（如：集中學(xué)習(xí)或聯(lián)邦學(xué)習(xí)），從而降低系統(tǒng)平均學(xué)習(xí)延遲。實(shí)驗(yàn)結(jié)果表明，ECDG 算法能夠有效降低系統(tǒng)平均學(xué)習(xí)延遲，滿足延遲敏感型機(jī)器學(xué)習(xí)應(yīng)用的服務(wù)質(zhì)量要求。