配電網(wǎng)中任務(wù)卸載決策與邊緣資源分配優(yōu)化方法

朵春紅，匡 竹，齊國梁，梅華威，李保罡，李永倩

1.華北電力大學(xué)河北省能源電力知識計算重點實驗室，河北 保定 071003

2.華北電力大學(xué)計算機系，河北 保定 071003

3.華北電力大學(xué)電子與通信工程系，河北 保定 071003

隨著配電網(wǎng)的建設(shè)推進及規(guī)模擴大，其運行形態(tài)和技術(shù)特征面臨重大變革[1]。一方面，體量龐大且分布廣泛的配電設(shè)備、量測終端產(chǎn)生了海量異構(gòu)數(shù)據(jù)，如果這些數(shù)據(jù)都遷移到云計算中心進行處理，將給云中心及通信信道帶來巨大的負載壓力[2]。另一方面，多元利益主體產(chǎn)生了差異化的業(yè)務(wù)需求，如計算密集型任務(wù)和時延敏感型任務(wù)；大多數(shù)終端設(shè)備電池容量有限，需要控制其任務(wù)通信和計算過程中產(chǎn)生的能耗。計算能力、時延及能耗等各方面約束限制了系統(tǒng)性能和用戶體驗。

作為云計算的延伸和補充，移動邊緣計算（mobile edge computing，MEC）可以減少端到端時延，減輕回程鏈路負擔(dān)，提高用戶服務(wù)質(zhì)量。隨著現(xiàn)代信息技術(shù)與電力系統(tǒng)的深度融合，邊緣計算成為提升配電網(wǎng)穩(wěn)定運行、實時分析及控制能力的有效手段。如何高效利用配電網(wǎng)邊緣有限的通信及計算資源，降低時延及能耗成本，提升系統(tǒng)計算性能和吞吐量，是保證配電物聯(lián)網(wǎng)高效運作的關(guān)鍵問題。

邊緣計算中的任務(wù)卸載與資源分配問題相互耦合，現(xiàn)有研究通常將兩者協(xié)同優(yōu)化。文獻[3]提出一種基于李雅普諾夫優(yōu)化的聯(lián)合計算卸載和無線資源分配算法。文獻[4]考慮車聯(lián)網(wǎng)中移動車輛和固定基礎(chǔ)設(shè)施的任務(wù)協(xié)作，設(shè)計了一種啟發(fā)式算法——容錯粒子群優(yōu)化算法，以最大化延遲約束下的可靠性性能。傳統(tǒng)優(yōu)化方法計算復(fù)雜度高，耗時長，基于啟發(fā)式的方法可以降低計算復(fù)雜度，但通常需要大量的迭代才能達到滿意的解決方案。與上述優(yōu)化方法相比，深度強化學(xué)習(xí)（deep reinforcement learning，DRL）算法具有強大的學(xué)習(xí)能力，可以在沒有先驗知識的情況下快速地做出自適應(yīng)決策，因此被廣泛用于解決大規(guī)模動態(tài)優(yōu)化及復(fù)雜的協(xié)作、博弈問題。使用DRL算法處理資源分配問題時，將問題建模為馬爾可夫決策過程（Markov decision process，MDP）。隨著用戶數(shù)量的增加，MDP模型的規(guī)模呈指數(shù)增長，出現(xiàn)維度詛咒。文獻[5]采用深度確定性策略梯度（deep deterministic policy gradient，DDPG）來處理動作空間和狀態(tài)空間的高維連續(xù)性，減少任務(wù)的長期處理延遲。文獻[6]結(jié)合DDPG，長短期記憶網(wǎng)絡(luò)和注意力機制提出A-DDPG，制定了任務(wù)卸載問題以最小化所有任務(wù)完成時延和能量消耗的總成本。文獻[7]設(shè)計一種改進的深度Q網(wǎng)絡(luò)（deep Q network，DQN）算法求解物聯(lián)網(wǎng)邊緣計算系統(tǒng)中的資源協(xié)同優(yōu)化問題，用多個重放存儲器來降低樣本之間的相關(guān)性，在Q網(wǎng)絡(luò)的末端添加濾波層來過濾無效動作的狀態(tài)動作值。文獻[8]研究多用戶MEC 系統(tǒng)中卸載決策和資源分配的聯(lián)合優(yōu)化問題，提出一種基于雙深度Q 網(wǎng)絡(luò)（double deep Q network，DDQN）方法，最大化用戶的計算效率。

近年來，配電網(wǎng)等工業(yè)物聯(lián)網(wǎng)場景下的計算卸載與資源分配引起了廣泛關(guān)注。配電網(wǎng)中未知的動態(tài)環(huán)境和巨大的狀態(tài)和動作空間，與深度強化學(xué)習(xí)的優(yōu)勢高度契合。文獻[9]分別針對靜態(tài)和動態(tài)信道環(huán)境，制定多任務(wù)計算卸載、NOMA 傳輸和計算資源分配的聯(lián)合優(yōu)化方案，在滿足每個任務(wù)的延遲約束下，實現(xiàn)物聯(lián)網(wǎng)設(shè)備的總能耗最小化。文獻[10]考慮到工業(yè)物聯(lián)網(wǎng)環(huán)境的高度分布性及動態(tài)性，提出基于DQN 的資源分配方案以最大化系統(tǒng)的帶寬利用率及能源效率。智能電網(wǎng)中有大量具有不同延遲要求的服務(wù)，文獻[11]結(jié)合神經(jīng)網(wǎng)絡(luò)和基于DRL的輪詢方法，解決了其中的聯(lián)合通信、計算和緩存資源分配問題。文獻[12]采用異步優(yōu)勢動作評價算法處理微電網(wǎng)能量交易中的區(qū)塊鏈計算任務(wù)卸載問題，減少任務(wù)處理的時延并提高系統(tǒng)吞吐量。

相較于對時延[5]、能耗[8]等的單一優(yōu)化，多目標(biāo)優(yōu)化更適合高度復(fù)雜的物聯(lián)網(wǎng)環(huán)境。較為普遍的是對時延、能耗等多因素進行權(quán)衡，如考慮最小化用戶設(shè)備執(zhí)行能耗與計算時間的加權(quán)和[13]、在最小化任務(wù)能耗和延遲加權(quán)和的同時實現(xiàn)系統(tǒng)的負載平衡和通信負載優(yōu)化[14]。文獻[8]、文獻[15]提出計算能效這一性能指標(biāo)，將其定義為計算比特數(shù)與能耗的比值，并研究其最大化問題。這一指標(biāo)旨在實現(xiàn)系統(tǒng)計算能力和能量消耗的同步優(yōu)化[16]。

上述研究考量了用戶需求和系統(tǒng)性能，忽視了邊緣節(jié)點的利潤。實際上，配電網(wǎng)中利益主體在請求資源時往往呈現(xiàn)出自私性，即追求自身利益的最大化而忽略整體利益。同時，隨著用戶數(shù)量的增加，資源有限的邊緣節(jié)點無法完成所有計算任務(wù)，必須選擇性地為卸載任務(wù)分配資源。因此，有必要設(shè)計一種機制來激勵邊緣節(jié)點為用戶提供通信及計算服務(wù)，并且維持資源的公平競爭。拍賣是一種兼具公平性和高效率的分配機制，然而由于資源的地理分散性及資源請求的多樣性，傳統(tǒng)拍賣模型并不直接適用于邊緣計算場景。針對邊緣計算中基于拍賣的資源分配問題，文獻[17]將移動邊緣計算中的資源管理建模為雙邊拍賣，同時優(yōu)化服務(wù)器的收益和物聯(lián)網(wǎng)設(shè)備的效用。文獻[18]設(shè)計了一種促進邊緣云與移動設(shè)備之間資源交易的多輪拍賣機制。

綜上所述，現(xiàn)有文獻更多關(guān)注MEC 中的任務(wù)卸載及資源分配問題，但對具體場景的考慮并不充分，較少考慮邊緣服務(wù)器的資源限制問題和多個用戶之間的資源競爭關(guān)系?；诂F(xiàn)有研究工作，本文針對配電網(wǎng)場景中邊緣計算卸載和資源分配的聯(lián)合優(yōu)化問題，提出一種基于DRL 的任務(wù)卸載算法與基于拍賣的資源分配機制。所提卸載方法能在異構(gòu)任務(wù)需求和時變信道的條件下，同時考量邊緣節(jié)點負載平衡及任務(wù)排隊時延等因素，使用戶在動態(tài)環(huán)境下自適應(yīng)地遷移任務(wù)，并選定最優(yōu)的離散化資源請求策略。所提拍賣方案適用于配電網(wǎng)邊緣計算系統(tǒng)，且能提高邊緣節(jié)點的利潤及資源利用率。本文的主要貢獻包括：

（1）考慮配電網(wǎng)中多邊緣節(jié)點、多用戶設(shè)備的復(fù)雜場景。具體而言，資源有限且計算能力不均衡的邊緣節(jié)點以分布式方式部署；用戶任務(wù)隨機到達，這些任務(wù)具有不同數(shù)據(jù)大小、計算量、資源需求和時延要求，競爭有限的資源。將邊緣通信和計算資源的分配問題建模為雙目標(biāo)長期優(yōu)化問題，即最大化系統(tǒng)計算能效和邊緣節(jié)點效益。

（2）提出一種基于DRL的在線任務(wù)卸載算法，在算法中同時考慮邊緣節(jié)點負載平衡及任務(wù)排隊時延等因素，讓用戶任務(wù)在動態(tài)環(huán)境下自適應(yīng)地調(diào)整遷移策略，以實現(xiàn)時延約束下系統(tǒng)計算能效的最大化。

（3）提出一種基于補償策略的多輪迭代拍賣算法解決邊緣節(jié)點的資源分配問題，通過用戶競價及動態(tài)的價格調(diào)整提高邊緣節(jié)點的收益。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

本文構(gòu)建了一個配電網(wǎng)中的云-邊-端三層邊緣計算卸載及資源分配模型。

如圖1 所示，云層擁有豐富的通信資源與計算資源[19]。云層中的服務(wù)器，如配電網(wǎng)調(diào)控中心，負責(zé)任務(wù)卸載模型的訓(xùn)練及更新。同時它可以作為拍賣商，從用戶設(shè)備收集資源需求和邊緣服務(wù)器的資源使用情況，通過專用的控制通道進行資源分配決策。

圖1 配電網(wǎng)邊緣計算系統(tǒng)模型Fig.1 Edge computing system model of distribution network

邊緣層由J個邊緣節(jié)點組成，定義為j∈{1,2,…,J},每個邊緣節(jié)點包括一個小基站和一個邊緣服務(wù)器。邊緣節(jié)點具有一定的通信、并行計算能力，邊緣服務(wù)器的計算能力用CPU 速率表征，即CPU 每秒可運轉(zhuǎn)的最大周期數(shù)。

用戶層由K個用戶設(shè)備（user equipment，UE）組成，定義為k∈{}1,2,…,K，如配電終端、傳感器等。用戶k可以生成多個計算任務(wù)i∈{}1,2,…,I并接收返回的計算結(jié)果。用戶k的第k個計算任務(wù)定義為ik=為任務(wù)數(shù)據(jù)大??；cik為任務(wù)的計算量，即任務(wù)計算所需的CPU 周期次數(shù)；為任務(wù)的最大容忍時延。任務(wù)隨機到達，任務(wù)的特征參數(shù)均勻分布在一定范圍內(nèi)。用戶利用云端下發(fā)的訓(xùn)練模型，生成遷移決策，進行局部數(shù)據(jù)的傳輸和計算。

定義一個離散的時隙模型t∈{1,2,…,T}，每個時隙t的持續(xù)時間為τ。用戶可以在本地計算任務(wù)，也可以將任務(wù)遷移到邊緣節(jié)點。將用戶本地和邊緣節(jié)點表示為可選擇的集合m∈{0,1,2,…,J},任務(wù)卸載決策變量xikm∈{0,1}, xikm=0,m=0 表示任務(wù)在本地執(zhí)行任務(wù)，xikm=1,m≥1 表示任務(wù)卸載至邊緣節(jié)點。本文假設(shè)用戶的計算任務(wù)是不可分割的，即只能在一個節(jié)點上執(zhí)行。

整個任務(wù)卸載及資源分配過程可以分成5個步驟。

（1）用戶用訓(xùn)練好的最優(yōu)遷移策略選擇將任務(wù)本地執(zhí)行或卸載至邊緣節(jié)點進行處理。如果選擇邊緣卸載，則加入對應(yīng)節(jié)點的拍賣備選隊列。

（2）根據(jù)邊緣節(jié)點的資源容量、用戶的資源需求情況和報價來選擇拍賣獲勝的用戶，拍賣成功的任務(wù)準(zhǔn)備卸載，拍賣失敗的任務(wù)對出價進行調(diào)整并重新進入第一步。

（3）基站為用戶任務(wù)分配相應(yīng)的帶寬資源，任務(wù)通過無線接入網(wǎng)絡(luò)或者蜂窩移動網(wǎng)絡(luò)上傳至邊緣節(jié)點，等待邊緣服務(wù)器計算資源空閑時進行執(zhí)行。

（4）邊緣服務(wù)器分配相應(yīng)的計算資源用于處理任務(wù)。

（5）任務(wù)執(zhí)行完成，用戶按定價規(guī)則支付費用，邊緣節(jié)點將執(zhí)行結(jié)果返回給用戶，釋放任務(wù)占用的資源。

上述步驟主要解決兩個問題：

（1）用戶側(cè)的卸載決策階段：結(jié)合任務(wù)在本地運行和計算卸載的時間消耗和能量消耗來共同決策該任務(wù)是否需要卸載執(zhí)行以及傾向于卸載到哪個邊緣節(jié)點。

（2）邊緣側(cè)的資源分配階段：當(dāng)任務(wù)需要卸載執(zhí)行時，通過改進拍賣算法對任務(wù)進行調(diào)度，在合適的邊緣節(jié)點上執(zhí)行任務(wù)，以實現(xiàn)邊緣節(jié)點的利益最大化。

在MEC 系統(tǒng)中，計算卸載包括將該計算任務(wù)傳輸?shù)皆摼W(wǎng)絡(luò)邊緣的通信過程和執(zhí)行該任務(wù)的計算過程。為了完成計算任務(wù)，用戶同時需要通信資源和計算資源。當(dāng)終端所需的兩種資源都得到滿足時，用戶和邊緣節(jié)點之間可以成功地達成一次拍賣交易。

1.2 通信模型

用戶選擇將任務(wù)卸載至邊緣服務(wù)器時，需要考慮任務(wù)數(shù)據(jù)上傳帶來的傳輸時延。假設(shè)多用戶干擾已通過正交頻分復(fù)用技術(shù)消除。每個用戶遷移到不同的邊緣節(jié)點有不同的上下行鏈路速率，任務(wù)ik遷移到邊緣節(jié)點的上行鏈路速率如下所示：

其中，Bj表示邊緣節(jié)點j的基站帶寬；pk表示用戶k上傳數(shù)據(jù)的傳輸功率；gk表示用戶k在無線信道中的信道增益；N0表示高斯白噪聲功率譜密度；λik j表示邊緣節(jié)點j分配給用戶k的任務(wù)ik的帶寬占比。

則在遷移計算中用戶上傳計算任務(wù)ik到邊緣節(jié)點j的傳輸延遲可表示為：

根據(jù)傳輸延遲，得到相應(yīng)的傳輸能耗：

由于計算結(jié)果的大小遠小于輸入任務(wù)的大小，因此忽略下行鏈路傳輸延遲和能耗[19]。

1.3 計算模型

（1）本地執(zhí)行

任務(wù)采用本地計算執(zhí)行時，本地執(zhí)行延遲與本地CPU的處理能力有關(guān)。因此任務(wù)的本地計算延遲為：

其中，βik表示本地用戶分配給任務(wù)ik的CPU 資源占比；f l k表示用戶的本地計算能力。則任務(wù)ik在本地計算時產(chǎn)生的能耗為：

其中，表示本地用戶k的計算功率。

（2）邊緣節(jié)點執(zhí)行

如果用戶選擇將任務(wù)卸載至邊緣節(jié)點，當(dāng)數(shù)據(jù)傳輸?shù)竭吘壒?jié)點后，利用邊緣服務(wù)器分配的CPU 資源來進行計算，可以得到用戶任務(wù)ik在邊緣節(jié)點j上的計算時間為：

其中，βik j表示邊緣節(jié)點j分配給用戶任務(wù)ik的計算資源占比，fej表示邊緣節(jié)點j的計算能力。

另外，任務(wù)時延還包括隊列等待時延，定義為。包括任務(wù)等待傳輸?shù)臅r延和等待執(zhí)行的時延，由動態(tài)變化的信道和計算資源情況決定。在本文中，使用SimPy模擬任務(wù)的處理流程和隊列模型，根據(jù)任務(wù)生成時間和結(jié)束時間計算出等待時延。

結(jié)合式（2）和（6），可以得到用戶任務(wù)ik遷移到邊緣節(jié)點j的執(zhí)行過程總延遲為：

基于此得到任務(wù)ik遷移到邊緣節(jié)點ik過程中，用戶k本地的等待能耗為：

其中，為用戶k在等待狀態(tài)過程中設(shè)備的閑置功率。結(jié)合式（3）和（8），可以得到，任務(wù)ik遷移至邊緣節(jié)點j過程中用戶端消耗的總能耗為：

1.4 優(yōu)化問題描述

通過聯(lián)合設(shè)計卸載決策、資源拍賣機制、帶寬和計算資源分配策略，最大化系統(tǒng)的計算能效，同時優(yōu)化邊緣節(jié)點的效益。優(yōu)化過程分為兩部分，在卸載決策階段，優(yōu)化目標(biāo)是選擇最優(yōu)策略以最大化總計算比特數(shù)與能量消耗的比值；在拍賣階段，優(yōu)化目標(biāo)是最大化邊緣節(jié)點拍賣資源所得效益。本部分將給出系統(tǒng)計算能效和邊緣節(jié)點效益的具體量化，并建立優(yōu)化問題。

（1）系統(tǒng)計算能效

計算能效是評估資源分配方案的一種性能指標(biāo)，定義為計算比特數(shù)與能量消耗的比值[16]。假設(shè)系統(tǒng)持續(xù)時間內(nèi)用戶k在本地完成的任務(wù)列表為，在邊緣服務(wù)器j完成的任務(wù)列表為，系統(tǒng)中完成的總計算比特數(shù)為：

系統(tǒng)中用戶總能耗為：

系統(tǒng)計算能效為：

（2）邊緣節(jié)點效益

為了量化邊緣節(jié)點的收益，本節(jié)引入拍賣理論將系統(tǒng)模型構(gòu)建為一個多輪拍賣問題[20]。拍賣機制有四要素，包括買家、賣家、拍賣商及商品。拍賣商由所有買家和賣家共同信任的第三方擔(dān)任，決定資源分配規(guī)則和支付規(guī)則，以保障拍賣的公平進行。在本文中，云層作為拍賣商，從用戶設(shè)備收集資源需求和邊緣服務(wù)器的資源使用情況，通過專用的控制通道進行資源分配決策。

在拍賣機制中，出價是一個用戶對任務(wù)所請求資源的估值，是愿意支付的最高價格，意味著對資源的偏好程度。常見的用戶出價策略包括根據(jù)終端的性能改進、用戶任務(wù)在邊緣節(jié)點執(zhí)行得到的收益來估計資源價值。具體的評價指標(biāo)包括減少的能耗值、降低的響應(yīng)時延、提升的服務(wù)質(zhì)量等。邊緣節(jié)點對單位資源的要價與其持有資源決定。要價代表邊緣節(jié)點執(zhí)行計算任務(wù)所要求的最低報酬。要價不能低于運行成本，運行成本包括單位計算成本、單位通信成本和額外成本等。本文假設(shè)用戶任務(wù)的原始出價和邊緣節(jié)點的要價均勻分布在一定數(shù)值范圍內(nèi)。

在拍賣階段，用戶作為買家向第三方拍賣商提供出價，邊緣節(jié)點作為賣家給出要價，由拍賣商來確定獲勝的用戶任務(wù)和最終的交易價格。拍賣商代理被部署在擁有大量計算能力的云計算中心上，可以快速促成買賣雙方之間的交易[21]。

用戶為其產(chǎn)生的任務(wù)向邊緣節(jié)點請求不同數(shù)目的CPU計算資源和通信資源，且用戶對緊迫程度不同的任務(wù)有不同的出價策略。用戶提交真實需求及出價，任務(wù)請求的資源數(shù)即邊緣節(jié)點分配的資源數(shù)，任務(wù)的傳輸與執(zhí)行時延由獲取的資源數(shù)確定。將用戶任務(wù)ik的出價與請求向量表示為，其中表示單位通信資源的出價，表示單位計算資源的出價，表示任務(wù)ik單位時隙請求的帶寬資源，表示任務(wù)ik單位時隙請求的計算資源量。出價是用戶對任務(wù)所請求資源的估值，是愿意支付的最高價格。

邊緣節(jié)點根據(jù)自身資源數(shù)量、成本等因素制定價格策略。用pj來表示邊緣節(jié)點j的基礎(chǔ)要價，即邊緣節(jié)點可接受的最低價格。其中表示邊緣節(jié)點的單位帶寬資源要價，表示邊緣節(jié)點的單位計算資源要價。

用拍賣補償策略不斷調(diào)整任務(wù)出價，具體設(shè)計在下文中詳述。定義用戶任務(wù)ik與邊緣節(jié)點j最終成交的價格為uik j,uik j=0 時表示兩者之間未產(chǎn)生交易。當(dāng)任務(wù)執(zhí)行完成時，用戶向邊緣節(jié)點支付最終成交價格，用戶效益可表示為：

邊緣節(jié)點的總效益Uj定義為通過拍賣機制獲得的總收入與相應(yīng)資源所需的基礎(chǔ)要價之差：

本文只考慮最大化邊緣節(jié)點的效益。對用戶效益，僅保證其非負性，使拍賣能滿足個體理性。

（3）優(yōu)化問題建立

具體優(yōu)化問題構(gòu)建如下：

上述優(yōu)化問題中，目標(biāo)函數(shù)即為最大化系統(tǒng)計算能效Us和邊緣節(jié)點拍賣效益Uj。式（16）表示無論任務(wù)選擇本地計算還是邊緣節(jié)點計算，其時延不能大于任務(wù)最大容忍時延。式（17）表示在某個時隙中，邊緣節(jié)點分配給各任務(wù)的計算資源βik j的總和不能超過其計算能力。式（18）表示時隙中，邊緣節(jié)點分配給各任務(wù)的帶寬資源λik j的總和不能超過其帶寬資源。式（19）表示任務(wù)卸載決策變量xikm的取值只能為0或為1。式（20）表示每個任務(wù)只能選擇一個邊緣節(jié)點進行處理。式（21）表示用戶效益Uk需滿足非負性，即用戶的最終成交價格不能高于用戶的出價。

2 任務(wù)卸載與資源分配方案設(shè)計

本文將任務(wù)處理過程分為計算卸載和資源拍賣兩個階段。在計算卸載決策階段，將問題建模為MDP 模型，詳細定義模型中的元素，并設(shè)計一種基于DRL的在線卸載決策算法，及時做出最優(yōu)決策。在拍賣階段，設(shè)計了一種資源分配與定價機制，用于處理用戶的異構(gòu)資源請求，激勵邊緣節(jié)點提供服務(wù)。

2.1 任務(wù)卸載算法設(shè)計

任務(wù)到達后，用戶將根據(jù)邊緣節(jié)點信道負載情況、等待傳輸隊列、等待執(zhí)行隊列以及任務(wù)需求，選擇節(jié)點開始遷移，其目標(biāo)是最大化系統(tǒng)總計算比特數(shù)與總能耗的比值。深度強化學(xué)習(xí)可以充分?jǐn)M合最優(yōu)策略、適應(yīng)復(fù)雜環(huán)境，是一種解決高維問題的有效方法?；诖?，本文采用DQN 及它的兩種改進Double DQN 和Dueling DQN來訓(xùn)練策略。

（1）馬爾可夫模型

本部分將公式化的問題轉(zhuǎn)化為一個有限時間范圍內(nèi)的馬爾可夫決策過程。MDP由一個五元組(S,A,P,R,γ)組成，其中S表示狀態(tài)空間，A表示動作空間，P表示狀態(tài)轉(zhuǎn)移概率，R表示獎勵函數(shù)，γ是折扣因子，γ∈[0,1]用于調(diào)整短期和長期獎勵對智能體的影響。具體描述如下：

在每個時隙t開始時，部署在用戶端的智能體將收集當(dāng)前局部環(huán)境的信息。狀態(tài)空間包括系統(tǒng)中每個邊緣節(jié)點的信道資源占用率信道中正在傳輸?shù)娜蝿?wù)數(shù)量及剩余傳輸時間,計算資源占用率正在計算的任務(wù)數(shù)量及剩余執(zhí)行時間，任務(wù)的特征信息。狀態(tài)空間定義為：

根據(jù)觀察到的環(huán)境狀態(tài)，智能體根據(jù)策略π 做出任務(wù)卸載決策。用一個長度為J+1的序列{xik0,xik1,…,xik J}表示卸載決策。動作空間定義為：

一旦根據(jù)觀察到的狀態(tài)s(t)采取了動作a(t)，智能體即可獲得獎勵r(t)并進入下一個狀態(tài)s(t+1)。在訓(xùn)練階段，智能體根據(jù)獲得的獎勵迭代策略π，直到收斂。獎勵函數(shù)通常與優(yōu)化目標(biāo)相關(guān)，因此，將獎勵函數(shù)定義為此任務(wù)比特數(shù)與能耗的比值：

考慮到任務(wù)的時延要求，當(dāng)任務(wù)耗時超過其最大容忍時延時，視為任務(wù)失敗，用戶將獲得懲罰。懲罰定義為當(dāng)前獎勵絕對值的負值：

（2）基于DQN的任務(wù)卸載算法設(shè)計

深度強化學(xué)習(xí)的核心思想是通過基于系統(tǒng)狀態(tài)觀察的獎勵來指導(dǎo)智能體行動。DQN將智能體在環(huán)境中的動作、觀測、獎勵作為一個序列。在每個時間間隔，智能體從動作空間中選擇一個可用動作。該動作會使得環(huán)境發(fā)生改變，從而根據(jù)環(huán)境的變化來獲得獎懲。DQN研究動作和觀測序列，并通過該序列學(xué)習(xí)某種策略。

DQN 用神經(jīng)網(wǎng)絡(luò)Q(s,a,ω)來近似動作價值函數(shù)，其中，ω表示神經(jīng)網(wǎng)絡(luò)的參數(shù)。某時刻t，智能體觀察到環(huán)境狀態(tài)s(t),根據(jù)策略選擇一種動作a(t)進行執(zhí)行。本文使用Epsilon-Greedy 算法作為動作選擇的策略，即確定一個正數(shù)ε(ε ＜1)作為隨機選擇動作的概率，剩下1-ε的概率選擇Q(s,a,ω)中得到的價值最大的動作。

在環(huán)境中執(zhí)行動作a(t)，獲得新的狀態(tài)s(t+1)、獎勵r(t) 。如果將觀察到的狀態(tài)轉(zhuǎn)移序列{s(t),a(t),r(t),s(t+1)}按照時間順序輸入神經(jīng)網(wǎng)絡(luò)，則訓(xùn)練結(jié)果會受到鄰近的序列的影響，這種相似性導(dǎo)致神經(jīng)網(wǎng)絡(luò)收斂到一個局部最優(yōu)解。采用經(jīng)驗回放方法解決這一問題，將這些序列存儲在經(jīng)驗池中，每次訓(xùn)練隨機抽取一小批（W個）樣本，計算目標(biāo)價值為：

其中，γ的取值范圍為(0,1]，用于調(diào)節(jié)未來獎勵對當(dāng)前狀態(tài)的影響。γ越大，智能體做決策時會考慮得越長遠，但訓(xùn)練難度也越高。

使用L2 均方誤差損失函數(shù)來計算Q(s,a;ω)與yt之間的差距，損失函數(shù)定義為：

用梯度下降法更新神經(jīng)網(wǎng)絡(luò)參數(shù)，降低損失函數(shù)值，提高神經(jīng)網(wǎng)絡(luò)擬合動作價值函數(shù)的精度。參數(shù)更新速度由學(xué)習(xí)率α控制。算法的具體流程如算法1所示。

算法1基于DQN的任務(wù)卸載算法

（3）Double DQN

在DQN 中，訓(xùn)練是為了使神經(jīng)網(wǎng)絡(luò)Q(s,a;ω)盡可能地接近目標(biāo)價值yt，而在yt中使用到了神經(jīng)網(wǎng)絡(luò)在t+1 時刻的估計值，用估算來更新同類的估算會導(dǎo)致自舉。同時，在yt中計算最大動作價值會導(dǎo)致對動作真實Q 值的高估，自舉會將這一高估回傳給神經(jīng)網(wǎng)絡(luò)，使得高估越來越嚴(yán)重。不同狀態(tài)下動作出現(xiàn)的概率是不均勻的，神經(jīng)網(wǎng)絡(luò)對概率高的動作會進行更頻繁的估值更新，產(chǎn)生失衡的高估并影響正確決策。

Double DQN 通過將選擇動作和評估動作分割開來避免過高估計的問題。具體而言，增加一個target 網(wǎng)絡(luò)用于估計動作的價值，用原來的神經(jīng)網(wǎng)絡(luò)選擇最優(yōu)動作，即yt變?yōu)椋?/p>

（4）Dueling DQN

Dueling DQN 算法從網(wǎng)絡(luò)結(jié)構(gòu)上改進了DQN。其前半部分與原始DQN一致，在輸出處，Dueling DQN將輸出映射到兩個全連接層值函數(shù)V(s;ωv) 和勢函數(shù)A(s,a;ωA)，分別用于評估狀態(tài)價值和動作優(yōu)勢，其中ωV和ωA是兩個全連接層網(wǎng)絡(luò)的參數(shù)。最后，Dueling DQN 通過合并兩個全連接層得到最終的Q值輸出，如式所示：

狀態(tài)價值函數(shù)V(s;ωv)等于在該狀態(tài)下所有可能動作所對應(yīng)的動作值乘以采取該動作的概率的和。優(yōu)勢函數(shù)A(s,a;ωA)是當(dāng)前動作價值相對于平均價值的優(yōu)勢大小，如果優(yōu)勢大于零，則說明該動作比平均動作好，比平均動作好的動作將會有更大的輸出，從而加速網(wǎng)絡(luò)收斂過程。

直接使用式計算Q值會出現(xiàn)可識別性問題，即給定一個Q值，無法得到唯一的V和A，使得模型的性能變差。因此，Dueling DQN強制優(yōu)勢函數(shù)估計量在選定的動作處沒有任何優(yōu)勢，得到式（30）：

使用優(yōu)勢函數(shù)的平均值代替上述的最大化操作，可以提升網(wǎng)絡(luò)穩(wěn)定性，最終得到式（31）：

2.2 資源拍賣方案設(shè)計

拍賣算法本質(zhì)上是各個拍賣參與者根據(jù)自身利益，依次對商品進行報價，通過多個輪次的競標(biāo)，最終得到相對滿意的商品?；谂馁u的算法機制，將任務(wù)分配過程定義為動態(tài)拍賣過程。通過用戶任務(wù)與邊緣節(jié)點的動態(tài)拍賣過程，實現(xiàn)用戶任務(wù)的合理化分配。

本節(jié)設(shè)計了一種基于補償策略的多輪迭代拍賣機制（compensation strategy-based multi-round iterative auction，CSMRⅠA），限定最大拍賣輪數(shù)為10，每一輪包含獲勝者確定和定價兩個步驟。在獲勝者確定階段，用戶提交其任務(wù)的資源需求和出價，拍賣機制根據(jù)邊緣節(jié)點要價、用戶任務(wù)的資源需求情況和出價來確定獲勝的用戶，使邊緣節(jié)點與用戶任務(wù)形成匹配。在定價階段，確定獲勝用戶最終應(yīng)為其任務(wù)支付的價格。

實現(xiàn)拍賣方案，需要先分別設(shè)計用戶的出價策略和邊緣節(jié)點的要價策略。

（1）用戶出價策略

假設(shè)用戶任務(wù)的原始出價均勻分布在一定數(shù)值范圍內(nèi)?？紤]到時延敏感的任務(wù)在單位時隙內(nèi)占有的通信資源與計算資源量更多，需要提交更高的單位資源價格來贏得拍賣并優(yōu)先執(zhí)行；同時為防止用戶請求不真實的資源，本文將任務(wù)原始出價與用戶資源占有量、的乘積作為首輪拍賣的出價、。

如果用戶任務(wù)在某一輪拍賣中失敗，用戶將采用補償因子調(diào)整當(dāng)前出價[22]，本文將補償因子定義為η=Sum指的是系統(tǒng)允許的最大拍賣總輪數(shù)，Numik是任務(wù)在此次報價之前拍賣失敗的次數(shù)。隨著任務(wù)失敗次數(shù)的增加，補償因子增大，任務(wù)會以更快的速度提高出價。

（2）邊緣節(jié)點報價策略

邊緣節(jié)點對單位帶寬資源和單位計算資源的要價與其持有資源決定。持有更多資源的邊緣節(jié)點適當(dāng)降低報價以提升在拍賣中的競爭力，獲得更多的任務(wù)，提高自身資源利用率。

（3）具體流程

基于出價及報價策略，參考文獻[23]，設(shè)計一種多輪迭代拍賣算法。

經(jīng)過計算卸載決策階段，拍賣商按照用戶的決策，將任務(wù)加入其所選邊緣節(jié)點j的拍賣備選隊列Qj,j∈{1,2,…,J}。在每一輪拍賣中，用戶向拍賣商提交任務(wù)的資源需求及出價向量，邊緣節(jié)點向拍賣商提交基礎(chǔ)要價pj。本文的拍賣涉及兩種資源，將每個賣/買家看作是兩個虛擬賣/買家，而每個虛擬賣/買家提供/請求單一的通信或者計算資源[24]。以通信資源的拍賣為例，在獲勝者確定階段，拍賣商將邊緣節(jié)點的拍賣隊列中的任務(wù)按其出價降序排序，將降序出價隊列表示為。拍賣商執(zhí)行一種貪婪策略，即每輪拍賣遍歷，比較任務(wù)出價和邊緣節(jié)點要價，如果用戶任務(wù)ik對于通信資源的出價高于邊緣節(jié)點ik對應(yīng)資源的要價，同時邊緣節(jié)點的剩余資源大于任務(wù)請求的單位時隙通信資源，視為任務(wù)請求節(jié)點的通信資源成功，加入獲勝隊列，反之視為兩者拍賣失敗。如果在某一輪拍賣中，任務(wù)與所選邊緣節(jié)點匹配失敗，用戶將調(diào)整任務(wù)的出價并重新進入卸載決策階段。在定價階段，任務(wù)的最終出價應(yīng)獨立于其自身出價。用戶任務(wù)在降序出價隊列中的序號用l表示，根據(jù)第二價格密封拍賣規(guī)則，假設(shè)任務(wù)在邊緣節(jié)點j某輪拍賣中獲勝，則其最終應(yīng)支付給邊緣節(jié)點的單位通信資源價格，是位于其后的任務(wù)出價和節(jié)點要價之間的較高值，即。邊緣節(jié)點對通信資源的獲勝用戶進行計算資源的拍賣，過程與通信資源類似。兩種資源都拍賣成功視為用戶與節(jié)點匹配成功，最終成交價格。以通信資源的拍賣為例，算法的具體流程如算法2所示。

算法2基于補償策略的多輪迭代資源拍賣算法

輸入：邊緣節(jié)點拍賣備選列表Oj，用戶任務(wù)的資源需求及出價向量bik,i∈{1,2,…,I},k∈{1,2,…,K}，邊緣節(jié)點的基礎(chǔ)要價pj,j∈{1,2,…,J}

輸出：用戶任務(wù)與邊緣節(jié)點j最終單位資源價格

3 仿真分析

3.1 實驗設(shè)置

本節(jié)通過仿真測試來評估所提出的任務(wù)卸載與資源分配算法的性能。系統(tǒng)包括1 個云服務(wù)器、4 個邊緣節(jié)點和K個配電網(wǎng)終端，用戶隨機分布在200 m×200 m的區(qū)域內(nèi)。系統(tǒng)時間步長τ設(shè)置為10 ms，每一次仿真持續(xù)3 000 個時間步長。在不同用戶數(shù)量的情況下，通過調(diào)整系統(tǒng)任務(wù)到達率，使每個用戶在系統(tǒng)持續(xù)時間中生成100 個左右的任務(wù)。實驗中設(shè)定資源占有量超過0.9 時為負載過重，不再執(zhí)行新需求。實驗中的主要參數(shù)設(shè)置見表1。

表1 實驗參數(shù)Table 1 Experimental parameters

本文的神經(jīng)網(wǎng)絡(luò)由一個輸入層、一個輸出層和兩個隱藏層組成。隱藏層的神經(jīng)元數(shù)量為20。采用ReLU作為激活函數(shù)，使用Adam 進行優(yōu)化，優(yōu)化學(xué)習(xí)率為0.001。經(jīng)驗池大小為2 000，每次訓(xùn)練批處理大小為32，網(wǎng)絡(luò)參數(shù)每200次迭代進行一次替換。折扣因子設(shè)為0.9，探索概率設(shè)為0.1。

為了驗證本文基于DQN的卸載算法結(jié)合CSMRⅠA拍賣的DQN-CSMRⅠA 方案效果，與以下三種方案進行對比實驗：（1）隨機卸載（random，RAN）-固定補償因子η的多輪迭代拍賣（fixed compensation factor multiround iterative auction，F(xiàn)CFMRⅠA），即RAN-FCFMRⅠA方案；（2）RAN-CSMRⅠA 方案；（3）DQN-FCFMRⅠA 方案。圖2～圖5主要驗證所提算法的在計算卸載方面的性能，圖6～圖8主要驗證所提算法在資源分配方面的性能。

圖2 DQN卸載算法的收斂性Fig.2 Convergence of DQN offloading algorithm

3.2 仿真結(jié)果

圖2 顯示了基于DQN、Double DQN、Dueling DQN的三種任務(wù)卸載算法的收斂性能。三種算法在40輪左右的迭代之后，收斂到一個相對穩(wěn)定的值，說明智能體學(xué)習(xí)到了最優(yōu)策略。

圖3顯示了用戶數(shù)量不同的情況下，使用隨機卸載方案和基于DQN、Double DQN、Dueling DQN 的任務(wù)卸載算法時的系統(tǒng)平均計算能效?？梢园l(fā)現(xiàn)，隨機卸載方案下的系統(tǒng)能效一直保持較低的水平，而基于DQN及其改進算法能大幅提高系統(tǒng)能效，其中基于Dueling DQN的卸載算法效果最佳。在用戶數(shù)為30時，Dueling DQN、Double DQN 和DQN 算法下的系統(tǒng)計算能效分別比隨機方案下的系統(tǒng)計算能效高出88.6%、80.2%、80.1%。這是因為智能體通過觀測當(dāng)前時隙各節(jié)點的負載情況和任務(wù)需求，能做出更優(yōu)越的決策，實現(xiàn)節(jié)點之間的負載平衡，減少隊列擁塞，減少任務(wù)的排隊等待時延和能耗，保證任務(wù)的成功率，從而提高系統(tǒng)的計算能效。隨著用戶數(shù)量增多，幾種卸載方案下的系統(tǒng)計算能效均出現(xiàn)下降。這種下降趨勢是因為任務(wù)數(shù)量持續(xù)增多時，資源競爭情況變得激烈，邊緣節(jié)點的通信和計算能力到達了瓶頸，計算性能變差。

圖3 不同用戶數(shù)量下的系統(tǒng)計算能效Fig.3 System computing energy efficiency with different number of users

圖4 顯示了用戶數(shù)為50，任務(wù)數(shù)據(jù)大小分布不同、其他特征參數(shù)分布情況一致的情況下，四種卸載方案的系統(tǒng)計算能效的變化。一開始，隨著任務(wù)數(shù)據(jù)大小增加，各節(jié)點在相同的時間步長中計算比特數(shù)更多，雖然通信時延和能耗也隨之增加，但是任務(wù)總能耗的其他部分變化較小，因此總的計算能效仍有一定幅度的提高。隨著數(shù)據(jù)大小進一步增大到4 Mbit及以上，計算能效出現(xiàn)回落。這是因為系統(tǒng)的信道資源開始緊缺，任務(wù)需要等待較長時間才能分配到資源，甚至?xí)驗槌瑫r導(dǎo)致任務(wù)失敗。另外，基于DQN 及其改進算法的卸載方案下的計算能效總是優(yōu)于隨機卸載方案下的計算能效，其中基于Dueling DQN 算法的卸載算法在大部分情況下略優(yōu)于其他兩種深度強化學(xué)習(xí)算法。任務(wù)數(shù)據(jù)大小均勻分布在3 Mbit 時，Dueling DQN、Double DQN 和DQN算法下的系統(tǒng)計算能效分別比隨機方案下的系統(tǒng)計算能效高出36.2%、35.3%、34.0%。

圖4 不同數(shù)據(jù)大小下的計算能效Fig.4 System computing energy efficiency with different data sizes

圖5 顯示了系統(tǒng)在不同用戶數(shù)量及不同卸載方案下的任務(wù)失敗率。當(dāng)用戶數(shù)量小于30 時，四種方案的任務(wù)失敗率都較低。在這一階段，邊緣節(jié)點的資源充足，可以滿足用戶任務(wù)的時延需求。隨著用戶數(shù)量持續(xù)增加，任務(wù)請求的資源超過了邊緣節(jié)點的通信、計算能力，四種方案的任務(wù)失敗率都有所增長。在邊緣資源緊張時，相較于隨機卸載，基于DQN及其改進算法的三種卸載方案失敗率增長較為迅速，這是因為用戶決策對彼此產(chǎn)生了干擾。

圖5 不同用戶數(shù)量下的任務(wù)失敗率Fig.5 Task failure rate under different number of users

圖6顯示了本文所提DQN-CSMRⅠA方案與三種對比方案在不同用戶數(shù)量情況下的效益。從圖中可以看出，無論是結(jié)合基于DQN的卸載還是隨機卸載，本文所提的CSMRⅠA 方案的節(jié)點收益均優(yōu)于FCFMRⅠA 方案。當(dāng)用戶數(shù)小于45時，隨著用戶數(shù)量增加，邊緣節(jié)點能服務(wù)于更多任務(wù)，四種方案的效益都隨之增長。用戶數(shù)等于45 時，DQN-CSMRⅠA 比RAN-FCFMRⅠA 方案的效益高出13.7%，RAN-CSMRⅠA 比RAN-FCFMRⅠA 方案的效益高出7.0%。而當(dāng)用戶數(shù)超過45，邊緣節(jié)點資源有限，能服務(wù)的任務(wù)數(shù)已經(jīng)趨于飽和，采用CSMRⅠA方案的節(jié)點效益增長趨于平緩，而采用FCFMRⅠA 方案的節(jié)點效益開始減少。這是因為大量用戶搶占資源導(dǎo)致任務(wù)失敗率變高，F(xiàn)CFMRⅠA 不能克服資源競爭帶來的負面影響，而CSMRⅠA中用戶通過動態(tài)調(diào)整出價提升競爭力，以優(yōu)先獲取任務(wù)所需的資源，能有效增加邊緣節(jié)點的效益。

圖6 不同用戶數(shù)量下的卸載-拍賣方案效益對比Fig.6 Benefit comparison of offloading-auction schemes with different numbers of users

圖7、圖8分別顯示了本文所提DQN-CSMRⅠA方案與三種對比方案在不同用戶數(shù)量情況下的通信、計算資源利用率對比。兩種多輪迭代拍賣方案的資源利用率總體較為接近；基于DQN的方案與隨機卸載相比，能使資源得到更高效的利用。除此之外，在CSMRⅠA 方案中，用戶會為時延更敏感的任務(wù)支付更高的價格來搶占資源、避免過長的等待延遲，這種出價策略能增加這類高時延要求的任務(wù)的優(yōu)先級，提高用戶的滿意度。

圖7 通信資源利用率Fig.7 Communication resource utilization rate

圖8 計算資源利用率Fig.8 Computing resource utilization rate

4 結(jié)束語

本文針對配電網(wǎng)中任務(wù)卸載決策和邊緣計算資源、帶寬資源分配的聯(lián)合優(yōu)化問題，在任務(wù)卸載方面，提出基于DQN及兩種改進Double DQN和Dueling DQN方法的任務(wù)卸載算法，評估節(jié)點資源利用和負載情況，在動態(tài)變化的環(huán)境中快速得到最優(yōu)卸載決策，以實現(xiàn)系統(tǒng)計算能效的最大化；在資源分配方面，提出一種基于多輪迭代拍賣的資源分配算法，使資源受限的邊緣節(jié)點選擇性地為用戶提供服務(wù)，獲取最大利益。通過仿真驗證了任務(wù)卸載算法的收斂性，并從系統(tǒng)計算能效、任務(wù)失敗率、邊緣節(jié)點效益、通信資源/計算資源利用率的多個評價指標(biāo)，將DQN-CSMRⅠA 卸載-拍賣方案與RANCSMRⅠA、Dueling DQN-CSMRⅠA、Double DQN-CSMRⅠA三種方案作對比，證實了所提算法可有效提高計算能效和邊緣節(jié)點效益。在未來的研究工作中，將考慮用戶的數(shù)據(jù)敏感性和隱私保護的問題，研究更具安全性的資源分配方案。