劉先鋒，梁 賽，李 強(qiáng)，張 錦

（湖南師范大學(xué)信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410081）

0 概述

近年來(lái)，隨著計(jì)算機(jī)與通信技術(shù)的高速發(fā)展，網(wǎng)絡(luò)邊緣設(shè)備數(shù)量及其所產(chǎn)生的數(shù)據(jù)量呈現(xiàn)爆炸式增長(zhǎng)趨勢(shì)。深度神經(jīng)網(wǎng)絡(luò)（Deep Neural Network，DNN）［1］作為支持現(xiàn)代智能移動(dòng)應(yīng)用的關(guān)鍵技術(shù)，因其高精度和可靠的推理性能，在計(jì)算機(jī)視覺(jué)［2］、自然語(yǔ)言處理［3］、機(jī)器翻譯［4］等大規(guī)模數(shù)據(jù)處理場(chǎng)景中得到廣泛應(yīng)用與研究。由于DNN 是計(jì)算密集型網(wǎng)絡(luò)，通常包含十個(gè)以上的網(wǎng)絡(luò)層及大量的神經(jīng)元節(jié)點(diǎn)，對(duì)存儲(chǔ)和計(jì)算資源要求很高，難以部署在資源受限的邊緣設(shè)備?，F(xiàn)有基于云計(jì)算的解決方案存在帶寬資源消耗大、通信延遲無(wú)法預(yù)測(cè)和圖像數(shù)據(jù)隱私泄露等問(wèn)題。為了解決此類問(wèn)題，文獻(xiàn)［5-6］提出基于云邊協(xié)同的DNN 分布式推理，通過(guò)將DNN 推理部分計(jì)算從云端下推到移動(dòng)邊緣，以緩解云服務(wù)器的負(fù)載壓力，實(shí)現(xiàn)DNN 推理的低延遲和高可靠性［7］。然而，現(xiàn)有工作僅考慮同構(gòu)設(shè)備下的靜態(tài)劃分策略，未考慮網(wǎng)絡(luò)傳輸速率、邊緣設(shè)備資源和云服務(wù)器負(fù)載等變化對(duì)DNN 推理計(jì)算最佳劃分點(diǎn)的影響以及異構(gòu)邊緣設(shè)備集群間DNN 推理任務(wù)的最佳卸載策略。

針對(duì)動(dòng)態(tài)環(huán)境下邊緣設(shè)備與云服務(wù)器間DNN 推理計(jì)算劃分以及異構(gòu)邊緣設(shè)備集群（Edge Device Cluster，EDC）間DNN 推理任務(wù)卸載問(wèn)題，本文提出基于深度強(qiáng)化學(xué)習(xí)（Deep Reinforcement Learning，DRL）的自適應(yīng)DNN 推理計(jì)算劃分和任務(wù)卸載（DNN Inference Computation Partition and Task Offloading Based on Deep Reinforcement Learning，DPTO）算法。DPTO 算法對(duì)DNN 模型各網(wǎng)絡(luò)層的計(jì)算資源需求和輸出數(shù)據(jù)大小進(jìn)行分析。根據(jù)模型結(jié)構(gòu)特征，在資源受限的邊緣設(shè)備和云服務(wù)器間建立分布式DNN 協(xié)作推理框架，以此優(yōu)化DNN 推理時(shí)延。在DNN 推理計(jì)算劃分的基礎(chǔ)上，考慮推理任務(wù)在異構(gòu)邊緣集群間的卸載問(wèn)題，對(duì)DNN 推理計(jì)算劃分和任務(wù)卸載的優(yōu)化目標(biāo)和約束條件進(jìn)行分析，建立DNN 推理計(jì)算劃分和任務(wù)卸載的數(shù)學(xué)模型。DPTO算法具有自適應(yīng)學(xué)習(xí)能力，能根據(jù)當(dāng)前環(huán)境為DNN推理計(jì)算劃分和推理任務(wù)卸載選擇近似最優(yōu)策略。最終選取3 種常用的DNN 模型、不同類型的邊緣設(shè)備和網(wǎng)絡(luò)傳輸速率驗(yàn)證DPTO 算法的有效性。

1 相關(guān)工作

目前，為在算力和存儲(chǔ)等資源受限的邊緣設(shè)備上部署和實(shí)現(xiàn)低時(shí)延DNN 推理，研究人員提出了一系列關(guān)于DNN 推理的優(yōu)化技術(shù)?，F(xiàn)有優(yōu)化技術(shù)包括設(shè)計(jì)輕量級(jí)模型、模型壓縮方法和模型提前退出機(jī)制。文獻(xiàn)［8］提出SqueezeNet 小型DNN 模型，其將參數(shù)量縮減為原來(lái)的1/50，極大降低了模型復(fù)雜度。文獻(xiàn)［9-10］提出模型壓縮方法，通過(guò)參數(shù)共享、剪枝不敏感或冗余的權(quán)重參數(shù)，降低模型復(fù)雜度和資源需求，實(shí)現(xiàn)在資源受限邊緣設(shè)備上的低延遲和低能耗DNN 模型推理。文獻(xiàn)［11-12］提出模型分支退出機(jī)制，通過(guò)僅處理較為靠前的若干網(wǎng)絡(luò)層來(lái)加速DNN 推理。以上技術(shù)雖然能有效降低資源需求、加速DNN 推理速度，但同時(shí)也會(huì)帶來(lái)模型精度的損失，難以適應(yīng)實(shí)際應(yīng)用場(chǎng)景中DNN 推理愈加嚴(yán)格的精度要求。

研究人員嘗試在邊緣設(shè)備上部署和運(yùn)行完整的DNN 模型，主要分為邊邊協(xié)同和云邊協(xié)同。邊邊協(xié)同通過(guò)將多個(gè)邊緣設(shè)備作為計(jì)算節(jié)點(diǎn)參與DNN 推理以滿足單個(gè)邊緣設(shè)備的計(jì)算需求，提升系統(tǒng)的整體計(jì)算能力。DNN 模型通常由卷積層、池化層和全連接層組成，通常卷積層消耗的算力最多。針對(duì)這一特性，文獻(xiàn)［13］提出DeepThings，利用FTP（Fused Tile Partition）劃分方案在空間上將卷積層劃分成多個(gè)分區(qū)任務(wù)，并分配給不同的移動(dòng)邊緣設(shè)備。文獻(xiàn)［14］提出一種尋找最優(yōu)網(wǎng)絡(luò)層的劃分方式和設(shè)備分區(qū)配置機(jī)制。在良好的網(wǎng)絡(luò)環(huán)境下，文獻(xiàn)［13-14］研究有效提高了DNN 推理速度，然而DNN 卷積層劃分之后，相鄰分區(qū)之間存在重疊數(shù)據(jù)，將導(dǎo)致設(shè)備間高頻的重疊數(shù)據(jù)交互，當(dāng)通信帶寬降低時(shí)，DNN推理時(shí)延顯著增加。

本文通過(guò)在Intel Mini PC CPU 1.9 GHz 上執(zhí)行VGG19 模型［15］來(lái)展示DNN 模型的計(jì)算和通信特征。圖1 給出了VGG19 各層的輸出數(shù)據(jù)內(nèi)存大小和計(jì)算時(shí)延，其中，input 表示輸入層、conv 表示卷積層、fc 表示全連接層、pool 表示池化層。從圖1 中可知：1）VGG19 各層有顯著不同的輸出數(shù)據(jù)內(nèi)存大小，卷積層增加數(shù)據(jù)，池化層減少數(shù)據(jù)，池化層的計(jì)算時(shí)延較小，卷積層和全連接層的計(jì)算時(shí)延較高；2）每一層的計(jì)算時(shí)延和輸出數(shù)據(jù)內(nèi)存大小不成正比關(guān)系，計(jì)算時(shí)延大的層不一定有較大的輸出值?；谝陨辖Y(jié)論，將DNN 模型劃分成兩部分，計(jì)算量小、傳輸時(shí)延大的前幾層放在邊緣設(shè)備端處理，計(jì)算量大、傳輸時(shí)延小的后幾層放在云端處理。該方法充分利用邊緣設(shè)備和云服務(wù)器的資源，不同層級(jí)的計(jì)算設(shè)備承擔(dān)不同算力需求的任務(wù)，有效權(quán)衡了移動(dòng)邊緣設(shè)備和云服務(wù)器的計(jì)算量和通信量。針對(duì)基于云邊協(xié)同的DNN 分布式推理，文獻(xiàn)［5］提出Neurosurgeon，從最小化時(shí)延和能耗的角度出發(fā)，基于回歸模型估算DNN 模型每一層執(zhí)行時(shí)延，結(jié)合當(dāng)前網(wǎng)絡(luò)帶寬返回邊緣設(shè)備和云服務(wù)器間DNN 推理計(jì)算的最優(yōu)劃分點(diǎn)，以此達(dá)到時(shí)延或能耗最優(yōu)。文獻(xiàn)［6］利用邊緣設(shè)備和云服務(wù)器的可用資源，為給定應(yīng)用程序提供有效的模型部署方案。

圖1 VGG19 每層輸出數(shù)據(jù)內(nèi)存大小及計(jì)算時(shí)延Fig.1 Memory size of output data and computation delay of each layer in VGG19

雖然目前已有基于云邊協(xié)同的DNN 分布式推理研究，但是這些研究存在以下不足：

1）對(duì)于邊緣設(shè)備與云服務(wù)器間DNN 推理計(jì)算的劃分，網(wǎng)絡(luò)傳輸速率、邊緣設(shè)備資源以及云服務(wù)器負(fù)載等變化都會(huì)直接影響到DNN 推理計(jì)算的最佳劃分。以VGG19 為例，圖2～圖4 分別給出了DPTO 算法在不同網(wǎng)絡(luò)傳輸速率、邊緣設(shè)備和云服務(wù)器負(fù)載下，以每層作為劃分點(diǎn)的端到端推理時(shí)延以及當(dāng)前環(huán)境下最佳劃分點(diǎn)的選取，其中：第一列input 表示以輸入層作為劃分點(diǎn)，將DNN 推理計(jì)算全部卸載到云服務(wù)器執(zhí)行；最后一列fc3 表示以輸出層作為劃分點(diǎn)，將DNN 推理計(jì)算全部放在邊緣設(shè)備上執(zhí)行；其他列表示以該層作為劃分點(diǎn)，輸入層到該層的推理計(jì)算放在邊緣設(shè)備執(zhí)行，剩余網(wǎng)絡(luò)層的推理計(jì)算放在云服務(wù)器執(zhí)行；箭頭表示當(dāng)前環(huán)境下的最佳劃分策略。

圖2 VGG19 在不同網(wǎng)絡(luò)傳輸速率下以每層作為劃分點(diǎn)的端到端推理時(shí)延Fig.2 End-to-end inference delay of VGG19 at different partition points under different network transmission rates

圖3 VGG19 在不同邊緣設(shè)備下以每層作為劃分點(diǎn)的端到端推理時(shí)延Fig.3 End-to-end inference delay of VGG19 at different partition points under different edge devices

圖4 VGG19 在不同云服務(wù)器負(fù)載下以每層作為劃分點(diǎn)的端到端推理時(shí)延Fig.4 End-to-end inference delay of VGG19 at different partition points under different cloud server loads

2）已有基于云邊協(xié)同的DNN 模型推理僅考慮了單個(gè)邊緣設(shè)備與云服務(wù)器的協(xié)作，在實(shí)際場(chǎng)景中通常有多個(gè)異構(gòu)邊緣設(shè)備，當(dāng)把所有任務(wù)全部卸載到單個(gè)邊緣設(shè)備時(shí)，會(huì)使該邊緣設(shè)備超出承載范圍，造成較大的響應(yīng)延遲以及其他邊緣設(shè)備計(jì)算資源的浪費(fèi)。因此，在多個(gè)異構(gòu)邊緣設(shè)備上進(jìn)行任務(wù)卸載，實(shí)現(xiàn)邊緣集群內(nèi)部的協(xié)作以此提高計(jì)算性能是一個(gè)亟待解決的問(wèn)題。

異構(gòu)邊緣集群中共有m臺(tái)邊緣設(shè)備，DNN 模型含有n層，在異構(gòu)邊緣集群上進(jìn)行DNN 推理計(jì)算劃分和任務(wù)卸載的所有情況為m×（n+1）。求解空間隨著DNN 模型層數(shù)和邊緣設(shè)備數(shù)量的增加而增大。傳統(tǒng)解決方法包括遺傳學(xué)算法、啟發(fā)式算法、迭代搜索算法等，這些算法在解決此類問(wèn)題時(shí)取得了一定成果。為了得到最優(yōu)解，這些算法的設(shè)計(jì)需要專家知識(shí)的輔助，這會(huì)導(dǎo)致算法缺乏靈活性、不穩(wěn)定、效果提升不明顯。隨著深度學(xué)習(xí)技術(shù)的發(fā)展，DRL［16-17］將深度學(xué)習(xí)與強(qiáng)化學(xué)習(xí)［18］相結(jié)合作為一種人工智能算法，被廣泛應(yīng)用于組合優(yōu)化、多方博弈等各種復(fù)雜決策求解問(wèn)題，具有重要研究?jī)r(jià)值。DRL的主要思想是在一個(gè)交互環(huán)境中利用創(chuàng)建的智能體（agent）不斷與環(huán)境互動(dòng)，通過(guò)環(huán)境反饋的獎(jiǎng)勵(lì)或懲罰信息，逐步逼近最優(yōu)結(jié)果。相比于傳統(tǒng)算法，DRL具有以下優(yōu)勢(shì)：1）與許多一次性優(yōu)化方法相比，深度強(qiáng)化學(xué)習(xí)可以隨環(huán)境變化調(diào)整策略，更好地適應(yīng)復(fù)雜環(huán)境的變化；2）DRL 在學(xué)習(xí)過(guò)程中不需要了解網(wǎng)絡(luò)狀態(tài)隨時(shí)間變化規(guī)律的相關(guān)先驗(yàn)知識(shí)。DRL 通過(guò)不斷與環(huán)境進(jìn)行交互，能夠?qū)W習(xí)不同狀態(tài)下應(yīng)該采取的最優(yōu)策略。基于以上特點(diǎn)，深度強(qiáng)化學(xué)習(xí)是解決復(fù)雜環(huán)境下決策問(wèn)題的有效方法［19-20］。為此，本文提出基于DRL 的自適應(yīng)DNN 推理計(jì)算劃分和任務(wù)卸載算法，對(duì)于不同的推理任務(wù)，該算法能有效降低推理任務(wù)執(zhí)行總時(shí)延。

2 系統(tǒng)框架和推理時(shí)延

2.1 系統(tǒng)框架

基于深度強(qiáng)化學(xué)習(xí)的云邊協(xié)同DNN 推理框架如圖5 所示。該框架由3 個(gè)部分組成：1）時(shí)間預(yù)估模型，基于當(dāng)前邊緣設(shè)備和云服務(wù)器資源，在不同邊緣設(shè)備和云服務(wù)器上建立不同類型DNN 層的時(shí)間預(yù)估模型；2）DNN 推理計(jì)算劃分和任務(wù)卸載，結(jié)合當(dāng)前網(wǎng)絡(luò)傳輸速率、邊緣設(shè)備資源和云服務(wù)器負(fù)載，通過(guò)DPTO 算法選擇DNN 推理計(jì)算劃分和任務(wù)卸載的最佳策略；3）DNN 分布式推理，根據(jù)DNN 推理計(jì)算劃分和任務(wù)卸載策略，將劃分點(diǎn)之前的DNN 推理計(jì)算卸載到相應(yīng)的邊緣設(shè)備上執(zhí)行，劃分點(diǎn)之后的DNN 推理計(jì)算卸載到云服務(wù)器執(zhí)行。

圖5 基于深度強(qiáng)化學(xué)習(xí)的云邊協(xié)同DNN 推理框架Fig.5 Framework of cloud-edge collaborative DNN inference based on deep reinforcement learning

2.2 時(shí)間預(yù)估模型

在DNN 推理計(jì)算過(guò)程中，主要計(jì)算集中于卷積層和全連接層。卷積層與全連接層的計(jì)算時(shí)間與每秒浮點(diǎn)運(yùn)算次數(shù)（Floating Point Operations，F(xiàn)LOPs）具有相關(guān)性，通過(guò)計(jì)算FLOPs 可以預(yù)估卷積層和全連接層的計(jì)算時(shí)間，為DNN 推理計(jì)算劃分和任務(wù)卸載提供決策依據(jù)。文獻(xiàn)［21］介紹了卷積層和全連接層的FLOPs 計(jì)算公式，如式（1）和式（2）所示：

其中：H和W表示輸入特征圖的高和寬；Cin和Cout表示卷積計(jì)算的輸入和輸出通道數(shù)；K表示卷積核的大??；I、O表示全連接層的輸入和輸出維數(shù)。

假設(shè)FLOPs 與計(jì)算時(shí)間的預(yù)估模型計(jì)算公式如式（3）～式（5）所示：

其中：x表示FLOPs；k表示設(shè)備計(jì)算能力；y表示計(jì)算時(shí)間；b表示卷積層或全連接層計(jì)算的固有時(shí)間開(kāi)銷。通過(guò)設(shè)置不同的輸入特征圖（H×W）、輸入輸出通道數(shù)（Cin，Cout）以及輸入和輸出維數(shù)（I，O）在邊緣設(shè)備上分別做卷積和全連接運(yùn)算，求得FLOPs 和平均計(jì)算時(shí)間。記錄多組FLOPs 與計(jì)算時(shí)間的值，使用最小二乘法求得預(yù)估模型。

2.3 DNN 推理時(shí)延

DNN 模型含有n層，將DNN 推理計(jì)算在邊緣設(shè)備和云服務(wù)器上進(jìn)行劃分，所有可選劃分策略p=｛0，1，…，n｝，其中p=n和p=0 為特殊的分區(qū)點(diǎn)，p=n表示DNN 推理計(jì)算全部放在邊緣設(shè)備上處理，p=0 表示DNN 推理計(jì)算全部上傳到云服務(wù)器處理。0＜p＜n表示輸入層到第p層在邊緣設(shè)備上執(zhí)行，剩余的網(wǎng)絡(luò)層傳輸?shù)皆品?wù)器執(zhí)行，網(wǎng)絡(luò)層第p層的輸出數(shù)據(jù)大小為Dp。當(dāng)采用云邊協(xié)同方式執(zhí)行DNN 推理時(shí)，單個(gè)圖片的推理時(shí)延主要由以下3 個(gè)部分組成：1）邊緣設(shè)備上的執(zhí)行時(shí)延Td；2）中間輸出數(shù)據(jù)上傳到云服務(wù)器的傳輸時(shí)間Tt；3）云服務(wù)器上的執(zhí)行時(shí)延Tc。由于推理結(jié)果往往很小，其返回的傳輸延遲通常忽略不計(jì)。

基于式（6）得到的預(yù)估模型預(yù)測(cè)各層在邊緣設(shè)備和云服務(wù)器上執(zhí)行所需時(shí)間，每一張圖片的推理時(shí)延可以表示如下：

其中：表示第j層在移動(dòng)設(shè)備上執(zhí)行所需的時(shí)間；Dp表示第p層的輸出數(shù)據(jù)大?。籅表示網(wǎng)絡(luò)傳輸速率；表示第j層在云服務(wù)器上的執(zhí)行時(shí)間。任務(wù)T中含有k張圖片，則處理該任務(wù)所需的總時(shí)延如下：

其中：C1、C2、C3為優(yōu)化目標(biāo)的約束條件。在約束條件C1和C2中，M和C分別表示邊緣設(shè)備的內(nèi)存和CPU 資源，t表示正在執(zhí)行的任務(wù)數(shù)，只有當(dāng)所有任務(wù)所需的內(nèi)存和CPU 資源總和少于邊緣設(shè)備的總資源時(shí)，該邊緣設(shè)備才可處理新的任務(wù)。約束條件C3表示所選邊緣設(shè)備和DNN 推理計(jì)算劃分點(diǎn)的策略在所有可選策略中。

3 自適應(yīng)DNN 推理計(jì)算劃分和任務(wù)卸載

3.1 馬爾可夫決策過(guò)程

為利用DRL 方法來(lái)尋找最優(yōu)解，需要把問(wèn)題轉(zhuǎn)化為強(qiáng)化學(xué)習(xí)的基本要素。首先將問(wèn)題建模為馬爾可夫決策過(guò)程（Markov Decision Process，MDP），MDP 可以表示為一個(gè)四元組｛S，A，P，R｝，其中，S表示環(huán)境中的狀態(tài)空間，A表示動(dòng)作空間，P表示狀態(tài)轉(zhuǎn)移函數(shù)，P（s'|s，a）表示在狀態(tài)s上執(zhí)行動(dòng)作a之后轉(zhuǎn)變?yōu)闋顟B(tài)s'的概率，R為獎(jiǎng)勵(lì)值函數(shù)。

1）狀態(tài)空間：S=｛s|s=（B，EED，CCS，D）｝，其中，B表示當(dāng)前網(wǎng)絡(luò)傳輸速率為具有m個(gè)元素的序列，表示當(dāng)前m個(gè)邊緣設(shè)備中各設(shè)備的計(jì)算資源，CCS表示云服務(wù)器的計(jì)算資源，D=（Dinput，D1，D2，…，Dn）表示原始輸入數(shù)據(jù)以及DNN 模型各層的輸出數(shù)據(jù)大小。

2）動(dòng)作空間：由所有可選的決策方案組成。對(duì)于DNN 推理計(jì)算劃分和任務(wù)卸載而言，動(dòng)作就是在邊緣設(shè)備和云服務(wù)器間選擇DNN 推理計(jì)算劃分點(diǎn)以及執(zhí)行該部分任務(wù)的邊緣設(shè)備?；诋?dāng)前狀態(tài)，DNN 模型有n+1 個(gè)推理計(jì)算劃分點(diǎn)，邊緣集群中有m個(gè)邊緣設(shè)備。動(dòng)作空間，其中，｛P0，P1，…，Pn｝表示DNN 推 理計(jì)算劃分點(diǎn)的集合，表示當(dāng)前所有可用的邊緣設(shè)備。

3）獎(jiǎng)勵(lì)值：環(huán)境會(huì)根據(jù)智能體執(zhí)行的動(dòng)作反饋相應(yīng)的獎(jiǎng)勵(lì)值。獎(jiǎng)勵(lì)值越大，表示選擇的動(dòng)作越好。以任務(wù)推理時(shí)延為優(yōu)化目標(biāo)，設(shè)置任務(wù)執(zhí)行響應(yīng)時(shí)延的負(fù)值作為獎(jiǎng)勵(lì)值。

其中：r表示獎(jiǎng)勵(lì)值大小。

3.2 基于深度Q 網(wǎng)絡(luò)的DNN 推理計(jì)算劃分和任務(wù)卸載

Q-Learning（QL）是無(wú)監(jiān)督的自適應(yīng)學(xué)習(xí)算法，從與環(huán)境的交互作用中學(xué)習(xí)知識(shí)，適用于求解馬爾可夫決策問(wèn)題。在Q-Learning 算法中使用二維矩陣存儲(chǔ)每一個(gè)狀態(tài)下所有動(dòng)作的Q 值，即狀態(tài)-動(dòng)作值函數(shù)Q（s，a）。當(dāng)狀態(tài)空間和動(dòng)作空間較大時(shí)，受計(jì)算機(jī)內(nèi)存限制，會(huì)導(dǎo)致Q 表爆炸［22］。本文提出基于深度Q 網(wǎng)絡(luò)（Deep Q-Network，DQN）［23］的任務(wù)卸載和DNN 推理計(jì)算劃分算法，DQN 算法是DRL 中的一種具體算法，使用神經(jīng)網(wǎng)絡(luò)替換Q 表，將Q 表更新轉(zhuǎn)化為函數(shù)擬合問(wèn)題。如圖6 所示，DQN 由兩個(gè)結(jié)構(gòu)相同但參數(shù)不同的神經(jīng)網(wǎng)絡(luò)構(gòu)成，在DQN 算法的訓(xùn)練過(guò)程中，Main 網(wǎng)絡(luò)用來(lái)計(jì)算當(dāng)前狀態(tài)動(dòng)作對(duì)的估計(jì)價(jià)值Q（s，a，w），w表示Main 網(wǎng)絡(luò)的參數(shù)，Target網(wǎng)絡(luò)用于計(jì)算下一狀態(tài)s'在所有動(dòng)作下的Q（s'，a'，w'），并選取最大值所對(duì)應(yīng)的動(dòng)作。根據(jù)所選動(dòng)作a'計(jì)算目標(biāo)價(jià)值函數(shù)，如式（11）所示：

圖6 基于DQN 的自適應(yīng)DNN 推理計(jì)算劃分和任務(wù)卸載框架Fig.6 Framework of adaptive DNN inference computation partition and task offloading based on DQN

其中：r表示獎(jiǎng)勵(lì)值；γ表示折扣因子。在神經(jīng)網(wǎng)絡(luò)的參數(shù)更新過(guò)程中，Main 網(wǎng)絡(luò)使用最新參數(shù)，在每次計(jì)算當(dāng)前狀態(tài)的估計(jì)價(jià)值后都會(huì)更新其參數(shù)。在每隔δ步驟之后，復(fù)制Main 網(wǎng)絡(luò)的參數(shù)到Target 網(wǎng)絡(luò)以更新Target 網(wǎng)絡(luò)。

由于強(qiáng)化學(xué)習(xí)的動(dòng)作選擇是一個(gè)連續(xù)的過(guò)程，因此前后數(shù)據(jù)關(guān)聯(lián)性很大，而神經(jīng)網(wǎng)絡(luò)的訓(xùn)練通常要求數(shù)據(jù)樣本是靜態(tài)獨(dú)立分布。在DQN 算法中，除了構(gòu)建兩個(gè)神經(jīng)網(wǎng)絡(luò)降低狀態(tài)間的相關(guān)性外，還使用經(jīng)驗(yàn)回放方法解決相關(guān)性及非靜態(tài)分布問(wèn)題，具體做法為：對(duì)于狀態(tài)s，用ε-greedy［24］策略選取動(dòng)作a，與環(huán)境交互后生成一個(gè)樣本（s，a，r，s'），將其儲(chǔ)存在經(jīng)驗(yàn)池中。當(dāng)經(jīng)驗(yàn)池中的元組數(shù)目達(dá)到一定值（例如數(shù)量N）時(shí)，隨機(jī)選擇經(jīng)驗(yàn)樣本組成Mini-batch來(lái)訓(xùn)練DQN。當(dāng)經(jīng)驗(yàn)池容量大于N時(shí)，則會(huì)刪除最老的經(jīng)驗(yàn)樣本，僅保留最后的N個(gè)經(jīng)驗(yàn)樣本。

DQN 算法訓(xùn)練的本質(zhì)是使得當(dāng)前Q 值無(wú)限接近于目標(biāo)Q 值，最終達(dá)到收斂狀態(tài)。損失函數(shù)定義如式（12）所示：

在得到損失函數(shù)后，通過(guò)損失的反向傳播機(jī)制調(diào)整神經(jīng)網(wǎng)絡(luò)參數(shù)w，同時(shí)Main 網(wǎng)絡(luò)會(huì)利用Adam優(yōu)化器來(lái)不斷地降低神經(jīng)網(wǎng)絡(luò)的損失函數(shù)，提高神經(jīng)網(wǎng)絡(luò)精度。

3.3 DPTO 算法

DPTO 算法用來(lái)解決異構(gòu)邊緣集群下的任務(wù)卸載以及邊緣設(shè)備與云服務(wù)器之間的DNN 推理計(jì)算劃分問(wèn)題。DPTO 首先實(shí)時(shí)獲取各狀態(tài)特征值，agent 根據(jù)當(dāng)前狀態(tài)輸出任務(wù)卸載和DNN 推理計(jì)算劃分策略。DPTO 算法的偽代碼如算法1 所示。

算法1DPTO 算法

輸入當(dāng)前網(wǎng)絡(luò)傳輸速率B，當(dāng)前各邊緣設(shè)備和云服務(wù)器資源，原始輸入數(shù)據(jù)以及DNN模型各層輸出數(shù)據(jù)大小D=｛Dinput，D1，D2，…，Dn｝，推理任務(wù)T

輸出DNN 推理計(jì)算劃分和任務(wù)卸載策略

1.初始化DQN 模型；

2.初始化實(shí)驗(yàn)參數(shù)；

3.for episode in T do：

4.for each task do：

5.獲取DNN 推理計(jì)算劃分點(diǎn)和可用邊緣設(shè)備集合Ω；

6.設(shè)置各特征值得到狀態(tài)s 并傳輸給agent；

7.使用DQN 方法在Ω 中選擇DNN 推理計(jì)算劃分點(diǎn)和執(zhí)行該任務(wù)的邊緣設(shè)備；

8.if DNN 推理計(jì)算劃分點(diǎn)為n、邊緣設(shè)備計(jì)算節(jié)點(diǎn)為設(shè)備m then

9.任務(wù)僅在邊緣設(shè)備m 上執(zhí)行；

10.計(jì)算任務(wù)執(zhí)行時(shí)延；

11.end

12.else if DNN 推理計(jì)算劃分點(diǎn)為0 then

13.任務(wù)卸載到云服務(wù)器上執(zhí)行；

14.計(jì)算任務(wù)執(zhí)行時(shí)延；

15.end

16.else

17.DNN 推理計(jì)算劃分到邊緣設(shè)備和云服務(wù)器上共同處理；

18.根據(jù)式（7）和式（8）計(jì)算任務(wù)執(zhí)行時(shí)延；

19.end else

20.根據(jù)式（9）計(jì)算獎(jiǎng)勵(lì)值；

21.更新DPTO 算法的最優(yōu)策略；

22.end for

23.返回到步驟3；

24.end for

DPTO 算法的空間復(fù)雜度為：2d（S）+O（l）+H+E+L，其中：d（S）為神經(jīng)網(wǎng)絡(luò)參數(shù)的維度，存儲(chǔ)兩個(gè)參數(shù)相同的神經(jīng)網(wǎng)絡(luò)內(nèi)存空間為2d（S）；O（l）為其他參數(shù)所占的內(nèi)存空間，例如學(xué)習(xí)速率、折扣因子等；H為存儲(chǔ)所有可選動(dòng)作的內(nèi)存空間；E為經(jīng)驗(yàn)池所占內(nèi)存空間；L為從經(jīng)驗(yàn)池中采樣的數(shù)據(jù)樣本數(shù)目的內(nèi)存空間。

DPTO 算法前向推理的計(jì)算復(fù)雜度計(jì)算如下：在DPTO 算法中輸入層的神經(jīng)元個(gè)數(shù)為所有狀態(tài)的集合s，網(wǎng)絡(luò)的第1 個(gè)隱藏層和第2 個(gè)隱藏層的節(jié)點(diǎn)個(gè)數(shù)分別設(shè)為k1和k2，輸出層的神經(jīng)元個(gè)數(shù)為所有可選動(dòng)作的集合m×n，則輸入層到第1 個(gè)隱藏層的矩陣運(yùn)算為［k1×s］×［s×1］，計(jì)算復(fù)雜度為O（k1×s2）。以此類推，第1 個(gè)隱藏層到第2 個(gè)隱藏層的計(jì)算復(fù)雜度為O（k2×），第2 個(gè)隱藏層到輸出層的計(jì)算復(fù)雜度為O（m×n×）。對(duì)于T個(gè)任務(wù)，DPTO 算法的總計(jì)算復(fù)雜度為O（T（k1×s2+k2×+m×n×））。

4 實(shí)驗(yàn)結(jié)果與分析

為測(cè)試DPTO 算法的可行性和有效性，本節(jié)搭建仿真實(shí)驗(yàn)環(huán)境，通過(guò)對(duì)比實(shí)驗(yàn)衡量DPTO 算法中基于深度強(qiáng)化學(xué)習(xí)的DNN 推理計(jì)算劃分和任務(wù)卸載在時(shí)延方面的優(yōu)化效果。

4.1 實(shí)驗(yàn)平臺(tái)

實(shí)驗(yàn)使用阿里云服務(wù)器提供云計(jì)算支持，以Intel Mini PC CPU 900 MHz、Intel Mini PC CPU 2.4 GHz、樹(shù)莓派3B+（1.2 GHz ARM Cortex-A53 處理器，1 GB 內(nèi)存）模擬異構(gòu)邊緣設(shè)備。邊緣設(shè)備和云服務(wù)器都加載已訓(xùn)練好的DNN 模型，邊緣設(shè)備與云服務(wù)器的通信采用TCP/IP 協(xié)議，Wondershaper 設(shè)置邊緣節(jié)點(diǎn)網(wǎng)絡(luò)傳輸速率。DNN 模型推理采用PyTorch1.3 框架，Python3.7.4 編程語(yǔ)言。在DPTO 算法中設(shè)置學(xué)習(xí)速率為0.01，折扣因子為0.9，訓(xùn)練批次大小為32，經(jīng)驗(yàn)池大小為500。DPTO 算法收斂結(jié)果如圖7 所示。

圖7 DPTO 算法收斂結(jié)果Fig.7 Convergence result of DPTO algorithm

4.2 DNN 推理計(jì)算劃分算法評(píng)估

通過(guò)在不同環(huán)境下執(zhí)行VGG19［15］、AlexNet［25］、YOLOv2［26］3 種DNN 模型，對(duì)比以下3 種經(jīng)典DNN推理算法來(lái)衡量基于深度強(qiáng)化學(xué)習(xí)的DNN 推理計(jì)算劃分（DNN Computation Partition Based on Deep Reinforcement Learning，DP）算法對(duì)DNN 推理時(shí)延的優(yōu)化效果：

1）純?cè)朴?jì)算（EC）：DNN 推理計(jì)算全部卸載到云服務(wù)器執(zhí)行，云服務(wù)器將推理結(jié)果返回給移動(dòng)設(shè)備。

2）純邊緣計(jì)算（EM）：DNN 推理計(jì)算全部放在邊緣設(shè)備上執(zhí)行。

3）離線劃分（OF）：通過(guò)在離線階段多次測(cè)量所有DNN 推理計(jì)算劃分點(diǎn)的執(zhí)行時(shí)延，選擇具有最小平均時(shí)延的劃分點(diǎn)作為云邊協(xié)同的DNN 推理計(jì)算劃分點(diǎn)。

4.2.1 不同網(wǎng)絡(luò)傳輸速率下DNN 推理時(shí)延評(píng)估

圖8 給出了EC、EM、OF、DP 4 種DNN 推理算法在不同網(wǎng)絡(luò)傳輸速率下處理單一圖片推理所消耗的時(shí)間。對(duì)于VGG19、AlexNet、YOLOv2 3 種不同類型的DNN 模型，DP 明顯優(yōu)于EC、EM、OF。與EC 相比，DP 的DNN 推理時(shí)延減少了約23.45%～60.32%。在EC 中，所有數(shù)據(jù)需上傳到云服務(wù)器，當(dāng)網(wǎng)絡(luò)傳輸速率過(guò)低時(shí)，其傳輸時(shí)延過(guò)大，導(dǎo)致整個(gè)DNN 推理時(shí)延增大。與EM 相比，DP 的DNN 推理時(shí)延減少了約31.86%～62.77%，這是由于邊緣設(shè)備資源有限，DNN 推理計(jì)算都在邊緣執(zhí)行，響應(yīng)時(shí)延較大。與OF相比，DP 的模型推理時(shí)延減少了約0.29%～22.87%，因?yàn)樵诓煌W(wǎng)絡(luò)傳輸速率下，DNN 推理計(jì)算的最佳劃分點(diǎn)不同。在OF 中，固定的DNN 推理計(jì)算劃分點(diǎn)不一定是當(dāng)前環(huán)境下的最佳劃分點(diǎn)。當(dāng)傳輸速率較高時(shí)，DP 的推理時(shí)延接近于EC，其選擇將整個(gè)DNN 推理計(jì)算全部上傳到云服務(wù)器執(zhí)行。在傳輸速率較低時(shí)，云邊協(xié)同DP 通過(guò)結(jié)合當(dāng)前環(huán)境選擇最佳DNN 推理計(jì)算劃分點(diǎn)，以使DNN 推理時(shí)延最小化。

圖8 不同網(wǎng)絡(luò)傳輸速率下4 種算法的DNN 推理時(shí)延Fig.8 DNN inference delay for four algorithms under different network transmission rates

4.2.2 不同邊緣設(shè)備下DNN 推理時(shí)延評(píng)估

VGG19、AlexNet、YOLOv2 3 種DNN 模型在不同推理算法和邊緣設(shè)備（高性能邊緣設(shè)備Intel Mini PC CPU 900 MHz 和低性能邊緣設(shè)備Intel Mini PC CPU 2.4 GHz）下的推理時(shí)延如圖9 所示。DP 的DNN推理時(shí)間相比于EM 減少了約18.35%～39.36%，相比于EC 減少了約46.48%～61.35%。當(dāng)邊緣設(shè)備計(jì)算能力較強(qiáng)時(shí)，DP 的推理時(shí)延接近于EM，其選擇將整個(gè)DNN 推理計(jì)算全部放在邊緣設(shè)備上執(zhí)行，避免數(shù)據(jù)傳輸帶來(lái)較大的響應(yīng)延遲。當(dāng)邊緣設(shè)備計(jì)算能力較弱時(shí)，DP 在邊緣設(shè)備和云服務(wù)器之間自適應(yīng)分配DNN推理計(jì)算或?qū)⒄麄€(gè)DNN 推理計(jì)算全部上傳到云服務(wù)器執(zhí)行。由于DP 能在動(dòng)態(tài)環(huán)境下做出最優(yōu)決策，DNN 推理時(shí)間相比于OF減少了約6.22%～10.29%。

圖9 不同邊緣設(shè)備下4 種算法的DNN 推理時(shí)延Fig.9 DNN inference delay for four algorithms under different edge devices

4.2.3 不同云服務(wù)器負(fù)載下DNN 推理時(shí)延評(píng)估

圖10 給出了4 種算法在不同云服務(wù)器負(fù)載下的DNN 推理時(shí)延。DP 的DNN 推理時(shí)延相比于EM 減少了約0.24%～55.39%，相比于EC 減少了約28.12%～48.88%。當(dāng)云服務(wù)器負(fù)載相對(duì)較高時(shí)，DP 的DNN推理時(shí)延接近于EM，其選擇將整個(gè)DNN 推理計(jì)算全部放在邊緣設(shè)備上執(zhí)行，避免云服務(wù)器負(fù)載過(guò)高帶來(lái)巨大的響應(yīng)延遲。當(dāng)云服務(wù)器負(fù)載相對(duì)較低且網(wǎng)絡(luò)狀況良好時(shí)，DP 將DNN 推理計(jì)算全部上傳到云服務(wù)器執(zhí)行。在其他情況下，DP 將DNN 推理計(jì)算劃分成兩部分，分別在邊緣設(shè)備和云服務(wù)器上共同執(zhí)行。DP 的推理時(shí)延相比于OF 減少了約14.41%～27.12%，因?yàn)镈P 能在動(dòng)態(tài)環(huán)境下自適應(yīng)選擇最佳DNN 推理計(jì)算劃分點(diǎn)。

圖10 不同云服務(wù)器負(fù)載下4 種算法的DNN 推理時(shí)延Fig.10 DNN inference delay of four algorithms under different cloud server loads

4.3 DPTO 算法評(píng)估

在4.2 節(jié)中驗(yàn)證了基于深度強(qiáng)化學(xué)習(xí)的DNN 推理計(jì)算劃分對(duì)DNN 推理時(shí)延的優(yōu)化效果，根據(jù)不同任務(wù)的推理情況，其中任務(wù)1、任務(wù)2、任務(wù)3、任務(wù)4分別包含1、30、50、100 張不同圖片，對(duì)比以下3 種算法來(lái)評(píng)估DPTO 算法在DNN 推理時(shí)延上的進(jìn)一步優(yōu)化效果：

1）DP：僅考慮DNN 推理計(jì)算的劃分，未考慮DNN推理任務(wù)在異構(gòu)邊緣集群上的卸載優(yōu)化，其將所有任務(wù)分配給當(dāng)前計(jì)算資源最多的邊緣設(shè)備處理。

2）輪詢（RR）：將任務(wù)隨機(jī)分配給邊緣設(shè)備進(jìn)行處理。

3）QL：具有良好學(xué)習(xí)效果的經(jīng)典強(qiáng)化學(xué)習(xí)算法，基于Q 表選擇卸載策略。

圖11 給出了4 種不同任務(wù)在不同算法下的執(zhí)行時(shí)間。對(duì)于4 種不同的任務(wù)，DPTO 的任務(wù)執(zhí)行時(shí)間相比于DP 減少了48.08%，在DP 中把所有任務(wù)全部卸載到單個(gè)邊緣設(shè)備時(shí)，會(huì)導(dǎo)致該邊緣設(shè)備出現(xiàn)資源競(jìng)爭(zhēng)問(wèn)題，任務(wù)等待時(shí)間變長(zhǎng)。而其他邊緣設(shè)備上的計(jì)算資源處于空閑狀態(tài)，造成響應(yīng)時(shí)延的增加和計(jì)算資源的浪費(fèi)。與RR 相比，DPTO 的任務(wù)執(zhí)行時(shí)間減少了29.18%，由于RR 沒(méi)有考慮邊緣設(shè)備計(jì)算能力的差異性，邊緣設(shè)備之間的負(fù)載不平衡導(dǎo)致任務(wù)執(zhí)行產(chǎn)生較大時(shí)延。與QL 相比，DPTO 的任務(wù)執(zhí)行時(shí)間減少了3.99%，QL 基于Q 表選擇卸載策略，Q 表采用二維數(shù)組存儲(chǔ)每一狀態(tài)下的動(dòng)作值函數(shù)，隨著任務(wù)和邊緣設(shè)備數(shù)量的增加，QL 中的狀態(tài)和動(dòng)作數(shù)量增多，通過(guò)遍歷整個(gè)Q 表尋找最優(yōu)卸載策略的開(kāi)銷時(shí)延增大，從而導(dǎo)致任務(wù)執(zhí)行時(shí)延也增大。綜上，不同的卸載策略對(duì)任務(wù)的執(zhí)行時(shí)延有著較大的影響。當(dāng)只有一個(gè)任務(wù)時(shí)，邊緣設(shè)備的計(jì)算壓力較小，選擇最好的邊緣設(shè)備就能應(yīng)對(duì)該任務(wù)。但隨著任務(wù)的不斷增加，根據(jù)任務(wù)的大小選擇合適的邊緣設(shè)備計(jì)算節(jié)點(diǎn)對(duì)時(shí)延的優(yōu)化具有重要的作用。

圖11 不同任務(wù)數(shù)量下4 種算法的執(zhí)行總時(shí)延Fig.11 Total execution delay of four algorithms under different number of tasks

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

目前，深度神經(jīng)網(wǎng)絡(luò)發(fā)展迅速，廣泛應(yīng)用于計(jì)算機(jī)視覺(jué)、自然語(yǔ)言處理和機(jī)器翻譯等智能任務(wù)。為了優(yōu)化DNN 推理性能，本文提出基于深度強(qiáng)化學(xué)習(xí)的云邊協(xié)同DNN 推理算法。將動(dòng)態(tài)環(huán)境下邊緣設(shè)備和云服務(wù)器間DNN 推理計(jì)算劃分以及異構(gòu)邊緣集群間任務(wù)卸載轉(zhuǎn)換為馬爾可夫決策過(guò)程下的最優(yōu)策略確定問(wèn)題，利用深度強(qiáng)化學(xué)習(xí)方法在經(jīng)驗(yàn)池中學(xué)習(xí)異構(gòu)動(dòng)態(tài)環(huán)境下DNN 推理計(jì)算劃分和任務(wù)卸載最佳策略。實(shí)驗(yàn)結(jié)果表明，對(duì)于不同的DNN 推理任務(wù)和DNN 模型，DPTO 算法在不同環(huán)境下相比于已有算法推理時(shí)延平均降低了約28.83%。下一步將對(duì)邊緣設(shè)備宕機(jī)和惡意攻擊等異常情況進(jìn)行研究，提出高效的容錯(cuò)解決方案，以保證云邊協(xié)同DNN 推理的可靠性和安全性。