面向延遲敏感型物聯(lián)網(wǎng)應用的計算遷移策略

郭棉　李綺琦

摘 要：針對云計算網(wǎng)絡延遲較長、能耗過高和邊緣服務器計算資源有限的問題，提出了一種提高延遲敏感型物聯(lián)網(wǎng)（IoT）應用服務質量（QoS）的邊緣云合作的漂移加懲罰計算遷移策略（DPCO）。首先，建立物聯(lián)網(wǎng)邊緣云系統(tǒng)模型，對業(yè)務模式、計算任務所經(jīng)歷的傳輸延遲和計算延遲、系統(tǒng)產(chǎn)生的計算能耗和傳輸能耗等進行數(shù)學建模;然后，以系統(tǒng)能耗和任務平均延遲為優(yōu)化目標，以邊緣服務器的隊列穩(wěn)定性為限制條件構建邊緣云合作的計算遷移優(yōu)化模型;接著，以優(yōu)化目標為懲罰函數(shù)，基于李雅普諾夫穩(wěn)定性理論推導出計算遷移優(yōu)化模型的漂移加懲罰函數(shù)特性。最后，基于推導結果提出了DPCO計算遷移算法，通過每時隙選擇使當前漂移加懲罰函數(shù)最小化的計算遷移策略來降低長期的單位時間能耗和縮短系統(tǒng)平均延遲。與輕流霧處理（LFP）、基準邊緣計算（EC）、基準云計算（CC）策略相比，DPCO的系統(tǒng)能耗最低，約是CC策略的2/3;任務平均延遲也最小，可減少為CC的1/5。實驗結果表明，DPCO能夠有效降低邊緣云計算系統(tǒng)的能量消耗，減少計算任務的端到端延遲，滿足延遲敏感型IoT應用的QoS要求。

關鍵詞：云計算;邊緣計算;計算遷移;能量消耗;服務質量

中圖分類號： TP393.027文獻標志碼：A

Computation offloading policy for delay-sensitive Internet of things applications

GUO Mian*， LI Qiqi

（School of Electronic and Information Engineering， Guangdong University of Petrochemical Technology， Maoming Guangdong 525000， China）

Abstract： The large network transmission delay and high energy consumption in cloud computing as well as the limited computing resource in edge servers are the bottlenecks for the development of delay-sensitive Internet of Things （IoT） applications. In order to improve the Quality of Service （QoS） of IoT applications while achieving green computing for computing systems， an edge-cloud cooperation Drift-plus-Penalty-based Computation Offloading （DPCO） policy was proposed. Firstly， mathematical modeling was performed on the business model， the transmission delay as well as the computation delay of the computation job， the computation energy as well as the transmission energy generated by the system were modeled by constructing the IoT-Edge-Cloud model. Then， the system consumption and the job average delay were optimized， with the queueing stability of the edge servers as constraint condition， the edge-cloud cooperation computation offloading optimization model was built. After that， with the optimization targets as the penalty function， the drift-plus-penalty function properties of computation offloading optimization model were analyzed based on Liapunov stability theory. Finally， DPCO was proposed based on the above results， the long-term energy consumption per unit time and the average system delay were reduced by selecting the computation offloading policy of minimizing the present drift-plus-penalty function in every time slot. In comparison with Light Fog Processing （LFP）， the benchmarked Edge Computing （EC） and Cloud Computing （CC） policies， DPCO consumes the lowest system energy， which is 2/3 of that of the CC policy; DPCO also provides the shortest average job delay， which is 1/5 of that of the CC policy. The experimental results show that DPCO can efficiently reduce the energy consumption of edge-cloud computing system， shorten the end-to-end delay of the computation job， and satisfy the QoS requirements of delay-sensitive IoT applications.

Key words： cloud computing; edge computing; computation offloading; energy consumption; Quality of Service （QoS）

0 引言

隨著物聯(lián)網(wǎng)（Internet of Things，IoT）應用的發(fā)展，分布式終端用戶（例如，物聯(lián)網(wǎng)設備）產(chǎn)生了巨量的數(shù)據(jù)，這些數(shù)據(jù)要求被快速計算處理以獲得最大的效益[1]。許多物聯(lián)網(wǎng)應用，如虛擬現(xiàn)實[2]、無人駕駛等，都是延遲敏感和計算密集型[3]。盡管集中式云計算數(shù)據(jù)中心在為計算密集型應用提供高性能計算方面體現(xiàn)了明顯的優(yōu)勢，然而它對延遲敏感型應用服務質量（Quality of Service， QoS）保證的低效性[4]以及巨量的能耗已經(jīng)成為發(fā)展延遲敏感型物聯(lián)網(wǎng)應用的瓶頸[5]。首先，云計算資源主要部署在遠程的數(shù)據(jù)中心，將巨量的分布式數(shù)據(jù)傳輸?shù)竭h程數(shù)據(jù)中心將使得數(shù)據(jù)應用經(jīng)歷較長的網(wǎng)絡延遲。特別地，隨著移動應用的不斷增長，不斷增長的網(wǎng)絡負載將導致不可容忍的網(wǎng)絡延遲。其次，從終端用戶將巨量的數(shù)據(jù)傳輸?shù)竭h程云計算中心的方式也消耗了巨量的網(wǎng)絡帶寬資源和傳輸能量。

近年來，邊緣計算已成為推動延遲敏感型物聯(lián)網(wǎng)應用發(fā)展的分布式數(shù)據(jù)中心范式研究熱點[4-5]。在邊緣計算范式中，網(wǎng)絡邊緣設備，例如基站[6]、無線接入點[6]和邊緣路由器[7]等，有著類似于云數(shù)據(jù)中心的計算和存儲能力[8]，因而用戶網(wǎng)絡的計算請求可以遷移到附近的邊緣服務器來處理，以此達到降低網(wǎng)絡傳輸延遲和減少傳輸能耗的目的。研究學者對面向邊緣計算環(huán)境的計算遷移策略進行了積極的研究。文獻[9]研究了物聯(lián)網(wǎng)邊緣云的計算遷移問題，提出了一種以延遲最小化為優(yōu)化目標的的輕流霧處理（Light Fog Processing， LFP）計算遷移方法。文獻[10]基于馬爾可夫過程構建了面向邊緣計算系統(tǒng)的功率限制延遲最小化計算遷移問題，并提出了一種單維搜索算法來決定是否將計算遷移到邊緣服務器。文獻[11]提出了一種多維搜索和調整計算遷移方法來降低延遲敏感型應用的平均延遲。文獻[12]提出了一種資源優(yōu)化方法來最小化多天線接入點的能耗。文獻[13]設計了一種選擇性計算遷移方法來最小化物聯(lián)網(wǎng)設備的能耗和降低信令開銷。文獻[14]提出了一種基于拉格朗日的計算遷移能耗優(yōu)化策略來縮短移動終端的總計算時間和降低能耗，為移動邊緣計算中計算密集型應用提供保障。文獻[15]提出了一種能夠聯(lián)合優(yōu)化移動終端處理時延與能耗的移動計算遷移方法。文獻[16]也提出了一種能耗感知的工作流計算遷移（Energy-aware computation Offloading for Workflows， EOW）方法來降低移動設備的能源消耗。

上述面向邊緣計算環(huán)境的計算遷移策略的研究主要是研究終端用戶是否決定將計算任務遷移、以及遷移多少到邊緣服務器進行計算，目的是最小化延遲或降低能耗等。然而，與云計算數(shù)據(jù)中心相比，邊緣計算服務器的計算能力是非常有限的[17]，它不能對所有突發(fā)的計算請求作出快速響應。因此，一些計算任務將在邊緣服務器經(jīng)歷超長的排隊延遲，甚至，該排隊延遲將超過從用戶網(wǎng)絡到遠程云計算中心的網(wǎng)絡延遲，給延遲敏感型應用帶來極差的用戶體驗。

為了對用戶提供服務質量保障和綠色化計算系統(tǒng)，本文綜合考慮云計算數(shù)據(jù)中心資源的充裕性和邊緣計算服務器的地域性優(yōu)勢，提出一種面向延遲敏感型物聯(lián)網(wǎng)應用的邊緣云合作計算遷移策略，即基于漂移加懲罰計算遷移（Drift-plus-Penalty-based Computation Offloading， DPCO）策略。該策略首先對物聯(lián)網(wǎng)邊緣云（IoT-Edge-Cloud）計算系統(tǒng)進行數(shù)學建模，包括業(yè)務模式、傳輸延遲和計算延遲、計算能耗和傳輸能耗等。然后以系統(tǒng)能耗和任務平均延遲為優(yōu)化目標、以邊緣服務器的隊列穩(wěn)定性為限制條件構建計算遷移優(yōu)化模型。接著以優(yōu)化目標為懲罰函數(shù)，分析了計算遷移模型的李雅普諾夫漂移加懲罰函數(shù)特性?；诜治鼋Y果，提出了DPCO計算遷移算法，通過每時隙選擇使當前漂移加懲罰函數(shù)最小化的計算遷移策略來降低長期的單位時間系統(tǒng)能耗和減少任務平均延遲。通過與基準邊緣計算（benchmarked Edge Computing， EC）、基準云計算（benchmarked Cloud Computing， CC）策略的對比實驗證實了DPCO策略能夠有效降低系統(tǒng)能耗，減少任務平均延遲，滿足延遲敏感型應用的服務質量要求和綠色化物聯(lián)網(wǎng)邊緣云計算系統(tǒng)。

1 系統(tǒng)模型

1.1 系統(tǒng)架構

IoT-Edge-Cloud系統(tǒng)如圖1所示。系統(tǒng)由用戶網(wǎng)絡、邊緣計算子系統(tǒng)、廣域網(wǎng)（Wide Area Network， WAN）網(wǎng)絡傳輸系統(tǒng)和云計算子系統(tǒng)構成。邊緣計算子系統(tǒng)中的每個邊緣節(jié)點由有限的計算、存儲資源和通信設備組成。邊緣計算和云計算子系統(tǒng)具有不同的計算能力。每一用戶網(wǎng)絡部署了多個物聯(lián)網(wǎng)設備，這些物聯(lián)網(wǎng)設備隨機地產(chǎn)生計算任務。每個用戶網(wǎng)絡與一個本地邊緣節(jié)點直接相連。用戶網(wǎng)絡將產(chǎn)生的計算任務交付給本地邊緣節(jié)點。本地邊緣節(jié)點發(fā)起計算遷移策略，在本地計算、發(fā)送給鄰居邊緣節(jié)點計算或通過WAN通信網(wǎng)絡傳輸?shù)皆朴嬎阕酉到y(tǒng)計算三者之間進行決策選擇。

設系統(tǒng)有M個用戶網(wǎng)絡、M個邊緣節(jié)點。每個邊緣節(jié)點的計算能力為PFi，i∈M*，這里M*={0，1，…，M-1}表示M個網(wǎng)絡用戶或M個邊緣節(jié)點的集合。設云計算子系統(tǒng)的計算資源無限，但是云計算子系統(tǒng)分配給每個計算任務的最大計算能力限制為PC。假設PFi

1.2 業(yè)務模型

設在時隙t（即時間間隔[t，t-1））內(nèi)，用戶網(wǎng)絡i有Xi（t）個計算任務交付到本地邊緣節(jié)點i， i∈M*。令κi（t）={0，1，…， Xi（t）-1}表示Xi（t）個任務的任務集。設第k個任務的文件大小為ski（t）， k∈κi（t），則時隙t內(nèi)交付給本地邊緣節(jié)點i的總業(yè)務量為：

Xwi （t） = ∑k∈κi Ski（t）（1）

用戶網(wǎng)絡i交付給本地邊緣節(jié)點的平均任務數(shù)量速率為：

λi=E[Xi（t））（2）

平均每個任務的大小為：

Si=E[Xwi（t）/Xi（t）]（3）

令Y（i，i）（t）、Y（i，n）（t）和Y（i，C）（t）分別表示這Xi（t）個任務中決定在本地邊緣節(jié)點i、鄰居邊緣節(jié)點n和云計算子系統(tǒng)中計算的任務的數(shù)量。令Yw（i， j）（t）=∑Y（i， j）（t）-1k=0Ski（t）、Yw（i，n）（t）=∑Y（i，n）（t）-1k=0Ski（t）和Yw（i，C）（t）=∑Y（i，C）（t）-1k=0Ski（t）表示對應的業(yè)務量，則它們需滿足如下條件：

Xi（t）=Y（i，i）（t）+Y（i，n）（t）+Y（i，C）（t），

Xwi（t）=Yw（i，i）（t）+Yw（i，n）（t）+Yw（i，C）（t） （4）

1.3 延遲模型

一個計算任務在圖1所示的IoT-Edge-Cloud系統(tǒng)將經(jīng)歷兩類延遲：傳輸延遲和計算延遲。

1）傳輸延遲：圖1所示的IoT-Edge-Cloud系統(tǒng)有兩類傳輸路徑：邊緣邊緣傳輸路徑和邊緣云傳輸路徑。

a）邊緣邊緣傳輸延遲：邊緣邊緣傳輸路徑長度一般為一跳，令B（i， j）表示邊緣i至鄰居邊緣j傳輸鏈路帶寬， α（i， j）表示該鏈路的傳輸延遲因子，即，網(wǎng)絡不穩(wěn)定或擁塞引起的網(wǎng)絡延遲;令Sk表示第k個從邊緣i傳輸?shù)竭吘塲的任務的大小，則該任務在傳輸路徑i-j的傳輸延遲可表述為：

Dkcomm（i， j）=α（i， j）+Sk/B（i， j）（5）

b）邊緣云傳輸延遲：邊緣至云之間通過WAN通信網(wǎng)絡子系統(tǒng)進行信息傳輸。WAN通信網(wǎng)絡子系統(tǒng)匯聚了所有邊緣節(jié)點到云計算子系統(tǒng)的業(yè)務，因此采用滑動平均網(wǎng)絡延遲來估算每個任務從邊緣節(jié)點傳輸?shù)皆朴嬎阕酉到y(tǒng)所需的時間，即，在t+1時隙內(nèi)從邊緣節(jié)點i傳輸至云端C的任務的網(wǎng)絡傳輸延遲為：

Dcomm（i，C）（t+1）=aDcomm（i，C）（t）+（1-a）D^（t）（6）

式中D^（t）表示t時隙內(nèi)平均每個任務的傳輸延遲：

D^（t）=α（i，C）+Yw（i，C）（t）B（i，C）Yi，C（t）（7）

其中α（i，C） 表示W(wǎng)AN通信網(wǎng)絡子系統(tǒng)傳輸延遲因子。

2）計算延遲：由于邊緣節(jié)點的計算資源有限性，邊緣服務器采用排隊系統(tǒng)模型;與邊緣服務器相比，云計算子系統(tǒng)的計算資源是無窮的，因此云計算子系統(tǒng)不考慮排隊模型，即：每個到達云計算子系統(tǒng)的任務都立即能得到服務。

a）邊緣服務器的計算延遲。令Qi（t）表示邊緣服務器i在時刻t等待服務的任務的數(shù)量，則t+1時刻該服務器等待服務的任務數(shù)為：

Qi（t+1）=max[Qi（t）+Yi（t）-ri（t），0]（8）

式中： Yi（t）和ri（t）分別表示在t時隙內(nèi)到達服務器的任務數(shù)和被服務的任務數(shù)。且有：

Yi（t）=∑j∈M*Y（j，i）（t）（9）

令Qwi（t）表示邊緣服務器i在時刻t積壓的業(yè)務量，則t+1時刻該服務器積壓的業(yè)務量為：

Qwi（t+1）=max[Qwi（t）+Ywi（t）-PFi/χ，0]（10）

式中： PFi/χ表示服務器每時隙能處理的比特量; Ywi（t）是在t時隙內(nèi)到達服務器的匯聚業(yè)務量，其計算公式為：

Ywi（t）=∑Yi（t）-1k=0Ski（11）

式中， Ski是第k個到達任務的大小。

采用先進先服務（First-In-First-Service， FIFS）規(guī)則調度隊列內(nèi)的任務，則在t時隙內(nèi)第k （k∈{0，1，…，Yi（t）-1}）個到達邊緣服務器排隊系統(tǒng)的任務的計算延遲為：

D（i，k）comp（t）=χPFi（Qwi（t）+∑kj=0Ski）（12）

該計算延遲由排隊延遲和服務延遲組成。

b）云計算子系統(tǒng)的計算延遲。令Sk表示時隙t內(nèi)第k個到達云計算子系統(tǒng)的任務的大小，則該任務在云計算子系統(tǒng)的計算延遲為：

D（C，k）comp（t）=χSk/PC（13）

3）端到端延遲：因此，對于在時隙t內(nèi)第k個到達計算節(jié)點i（如邊緣計算節(jié)點或云計算子系統(tǒng)）的任務，設其大小為Ski，其端到端延遲可表示為：

D（i，k）（t）=IkF（t）D（i，k）comp（t）+IkNF（t）[Dkcomm（j，i）+

D（i，k）comp（t）]+IkC（t）[Dkcomm（j，C）+D（C，k）comp（t）]（14）

式中：D（i，k）comp（t）和D（C，k）comp（t）分別是邊緣節(jié)點i和云計算子系統(tǒng)C的計算延遲; Dkcomm（j，i）和Dkcomm（j，C）分別是傳輸路徑邊緣j-邊緣i、邊緣j-云C的傳輸延遲;IkF（t）、IkNF（t）和IkC（t）是二值決策指示變量，當IkF（t）=1時，表示該任務在本地邊緣節(jié)點計算;當IkNF（t）=1時，表示該任務在鄰居邊緣節(jié)點計算;當IkC（t）=1時，表示在云計算子系統(tǒng)計算。這3個計算決策變量之間的取值應滿足如下關系：

IkF（t）+IkNF（t）+IkC（t）=1（15）

4）系統(tǒng)平均延遲：則在時隙t內(nèi)計算的所有任務的平均延遲為：

Dsys（t）=∑i∈M*∪CD（i，k）（t）/∑i∈M*∪CYi（t）（16）

數(shù)學期望為：

Dsys=E[Dsys（t）]=limt→∞1t∑t-1τ=0Dsys（τ）（17）

1.4 能耗模型

由于邊緣計算節(jié)點與云計算子系統(tǒng)架構上的區(qū)別性，對邊緣計算節(jié)點和云計算子系統(tǒng)采用不同的能耗模型。

1）邊緣節(jié)點的計算能耗。根據(jù)文獻[18]，邊緣節(jié)點的計算能耗是計算業(yè)務量的凸函數(shù)，因此采用如下的能耗模型：

PwFi（t）=af（Ywi（t））2+bf（Ywi（t））+cf（18）

式中： PwFi（t）是邊緣節(jié)點i在時隙t的計算能耗; af>0，bf，cf≥0是能耗因子; Ywi（t）是該節(jié)點在時隙t的計算業(yè)務量。

2）云計算子系統(tǒng)的計算能耗。根據(jù)文獻[18-19]，在時隙t到達云計算子系統(tǒng)的第k個來自用戶網(wǎng)絡i、任務大小為Ski的任務的計算能耗為：

PwC（i，k）（t）=χSkiPC（Ac fθC（t）+Bc）（19）

式中： χSki/PC是任務執(zhí)行時間; Ai>0、θ∈[2.5，3]和Bc≥0是能耗因子; fc（t）是分配給該任務的中央處理器（Central Processing Unit， CPU頻率。

則處理時隙t內(nèi)到達云計算子系統(tǒng)的所有任務所需的能耗為：

PwC（t）=∑i∈M*∑Y（i，C）（t）-1k=0PwC（i，k）（t）（20）

3）傳輸能耗：設傳輸路徑（i-j）在時隙t傳輸?shù)臉I(yè)務量為λw（i， j）（t），則該傳輸路徑在該時隙的傳輸能耗為：

Pwcomm（i， j）（t）=a（i， j）λw（i， j）（t）（21）

式中， a（i， j）>0是傳輸路徑能耗因子。

4）系統(tǒng)能耗：因此，IoT-Edge-Cloud系統(tǒng)在時隙t的能耗為：

Pw（t）=∑i∈M*PwFi（t） + PwC（t） +

∑i∈M*∑j∈M*∪C，j≠iPwcomm（i， j） （t）（22）

數(shù)學期望為：

Pw=E[Pw（t））]=limt→∞1t∑t-1τ=0Pw（τ）（23）

1.5 能耗延遲均衡函數(shù)

令G（t）表示系統(tǒng)在時隙t的能耗延遲均衡函數(shù)，定義為：

G（t）=ω1Pw（t）+ω2Dsys（t）（24）

式中：ω1≥0和ω2≥0分別是能耗和系統(tǒng)平均延遲的均衡控制參數(shù)。當ω1=0時，表示不考慮系統(tǒng)能耗;當ω2=0時，表示不考慮任務平均延遲。

則能耗延遲均衡的數(shù)學期望為：

G=E[G（t）]=ω1E[Pw（t）]+ω2E[Dsys（t）]=

ω1Pw+ω2Dsys（25）

1.6 問題建模

令κXi（t）={0，1，…，Xi（t）-1}表示時隙t內(nèi)到達邊緣節(jié)點i、且來自用戶網(wǎng)絡i的任務集合;令γki（t）=（I（i，k）F（t），I（i，k）NF（t），I（i，k）C（t））表示其中第k個任務的計算遷移決策向量;則γi（t）=（γ0i（t）， γ1i（t）， …， γki（t）， …， γXi（t）-1i（t））表示時隙t內(nèi)邊緣節(jié)點i對來自用戶網(wǎng)絡i的所有任務的計算遷移決策向量， γ（t）=（γ0（t）， γ1（t），…， γi（t）， …， γM-1（t））表示時隙t內(nèi)IoT-Edge-Cloud系統(tǒng)所有邊緣節(jié)點的計算遷移決策向量。

則，對于來自用戶網(wǎng)絡i的任務，有式（26）～（27）：

Y（i，i）（t）=∑k∈ΚXiI（i，k）F（t）

Y（i，n）（t）=∑k∈ΚXiI（i，k）NF（t）

Y（i，C）（t）=∑k∈ΚXiI（i，k）C（t） （26）

Yw（i，i）（t）=∑k∈ΚXiI（i，k）F（t）Ski

Yw（i，n）（t）=∑k∈ΚXiI（i，k）NF（t）Ski

Yw（i，C）（t）=∑k∈ΚXiI（i，k）C（t）Ski （27）

因此，能耗延遲優(yōu)化的IoT-Edge-Cloud系統(tǒng)計算遷移問題可以建模為能耗延遲均衡函數(shù)最小化問題，即：

最小化：

G=E[G（γ（t））]（28）

限制條件有式（4）、式（26）～（27）和下面的式（29）～（30）：

Qi<∞;? i∈M*（29）

Qwi<∞; i∈M*（30）

式（28）由式（25）而來;式（4）是業(yè)務限制條件;式（26）～（27）的依據(jù)是的定義;不等式（29）～（30）是邊緣節(jié)點排隊系統(tǒng)穩(wěn)定性條件。Qi、Qwi分別定義為：

Qi=E[Qi（t）]=limt→∞1t∑t-1τ=0Qi（t）（31）

Qwi=E[Qwi（t）]=limt→∞1t∑t-1τ=0Qwi（τ）（32）

在優(yōu)化問題（28）～（30）中，決策變量為γ（t）。根據(jù)式（26）～（27），當γ（t）確定時， Y（i， i）（t）、Y（i， n）（t）、Y（i，C）（t）以及Yw（i， i）（t）、Yw（i， n）（t）、Yw（i，C）（t）也確定，從而獲得G。因此，能耗延遲優(yōu)化的IoT-Edge-Cloud系統(tǒng)計算遷移問題等效于找出一系列優(yōu)化的γ*（t）（ t=0， 1， …， ∞）來獲得最小化的G。

2 DPCO策略

本文基于李雅普諾夫穩(wěn)定性理論[20-21]，提出一種基于漂移加懲罰的計算遷移（DPCO）策略。該策略通過李雅普諾夫漂移加懲罰函數(shù)得出的結論對任務進行計算遷移決策，得到一系列的γ（t），進而得到優(yōu)化問題（28）～（30）的解。

2.1 李雅普諾夫漂移加懲罰函數(shù)

令Qw（t）=（Qw0（t）， Qw1（t）， …， Qwi（t），…， QwM-1（t））表示M個邊緣服務器排隊系統(tǒng)在時刻t的積壓業(yè)務量向量。令L（t）表示積壓業(yè)務量的李雅普諾夫函數(shù)，定義為：

L（t）=12∑i∈M*Qwi（t）2（33）

則，Qw的一步李雅普諾夫漂移定義為：

ΔL（t）=E[L（t+1）-L（t）|Qw（t）]（34）

引理1 每一時隙，對任意的Qw（t），在任意計算遷移策略下，邊緣服務器排隊系統(tǒng)積壓業(yè)務量的李雅普諾夫漂移滿足：

ΔL（t）≤B-∑i∈M*Qwi（t）PFi/χ+

∑i∈M*Qwi（t）E[Ywi（t）|Qw（t）]（35）

式中B是一個常數(shù)。

證明 根據(jù)式（10），有：

Qwi（t+1）2≤（Qwi（t）+Ywi（t）-PFi/χ）2=

Qwi（t）2+（Ywi（t）-PFi/χ）2+

2Qwi（t）（Ywi（t）-PFi/χ）（36）

將（36）、（33）代入（34）并化簡，得：

ΔL（t）≤12∑i∈M*EYwi（t）-PFiχ2|Qw（t）+

∑i∈M*Qwi（t）EYwi（t）-PFiχ|Qw（t）（37）

由于：

0≤Ywi（t）≤∑i∈M*Xwi（t）

以及：

E[∑i∈M*Xwi（t）]=∑i∈M*λiSi=λS

因此，有：

Ywi（t）-PFiχ2≤maxPFiχ2，λS-PFiχ2

令：

B=∑i∈M*max12PFiχ2，12λS-PFiχ2

并代入（37），得：

ΔL（t）≤B+∑i∈M*Qwi（t）EYwi（t）-PFiχ|Qw（t）

此外， PFi/χ獨立于Qw（t），因此：

EPFiχ|Qw（t）=PFiχ

由此可得：

ΔL（t）≤B-∑i∈M*Qwi（t）PFiχ+

∑i∈M*Qwi（t）E[Ywi（t）|Qw（t）]

證畢

由于本文的目的是找出一系列優(yōu)化的計算遷移策略γ*（t）（t=0，1，…，∞）來最小化G，因此把G（γ（t））作為懲罰函數(shù)加入積壓業(yè)務量的李雅普諾夫漂移函數(shù)，即，定義李雅普諾夫漂移加懲罰函數(shù)為ΔL（t）+VE[G（γ（t））|Qw（t）]。由此得到引理2。

引理2 每一時隙，對任意的Qw（t），在任意計算遷移策略下，邊緣服務器排隊系統(tǒng)積壓業(yè)務量的李雅普諾夫漂移加懲罰函數(shù)滿足：

ΔL（t）+VE[G（γ（t））|Qw（t）]≤

B+VE[G（γ（t））|Qw（t）]-∑i∈M*Qwi（t）PFi/χ+

∑i∈M*Qwi（t）E[Ywi（t）|Qw（t）]=

B+Vω1E[Pw（γ（t））|Qw（t）]+

Vω2E[Dsys（γ（t））|Qw（t）]-∑i∈M*Qwi（t）PFi/χ+

∑i∈M*Qwi（t）E[Ywi（t）|Qw（t）]（38）

式中：B是與引理1相同的常數(shù)，且該常數(shù)獨立于V;V是一個非負控制參數(shù)。通過控制V、ω1和ω2的取值，可獲得能耗和平均延遲的均衡優(yōu)化值。

引理2可由引理1兩邊同時加上懲罰函數(shù)直接獲得。

2.2 DPCO算法

根據(jù)引理1和引理2的結論，本文提出分布式DPCO策略來找出優(yōu)化的γ*（t）（t=0，1，…，∞），來最小化不等式（38）的右邊，從而最小化ΔL（t）+VE[G（γ（t））|Qw（t）]，以達到最小化G的目的。具體的DPCO算法如算法1所示。

算法1 DPCO算法。

輸入 Xi（t）、Qw（t）。

輸出 γ*i（t）。程序前

Begin：

1） 初始化： Yw（i， i）（t）=0、Yw（i， n）（t）=0，n∈{i的鄰居列

表};

2） 決策過程：選取γ*i（t），使其滿足

γ*i（t）=arg minri（t）（VG（γi（t））+

∑j={i， n}Qwj（t）Ywj（γi（t）））（39）

3） 處理決策：觀察γ*i（t），對k∈κXi，執(zhí)行

a） 當I（i， k）F（t）=1：將該任務放入本地邊緣服務器排隊系

統(tǒng);

b） 當I（i， k）NF（t）=1：將該任務遷移到鄰居邊緣節(jié)點計算;

c） 否則：將該任務遷移到云計算子系統(tǒng)計算。

End程序后

基于DPCO的IoT-Edge-Cloud系統(tǒng)任務分配和調度過程如算法2所示。

算法2 基于DPCO的任務分配和調度過程。程序前

初始化： Q（0）=0 、Qw（0）=0;

Begin： 對每一時隙t≥0，do

1） 任務分配過程：

a） 邊緣節(jié)點i收到來自用戶網(wǎng)絡i的Xi（t）個計算任務，

執(zhí)行下述步驟：

i） 觀察Qw（t），執(zhí)行DPCO算法，即算法1;

ii） 將步驟i）的結果代入式（26）、（27），計算出Y（i， i）（t）

和Yw（i， i）（t），采用式（40）更新Qi（t）和Qwi（t）。

Qi（t+1）=Qi（t）+Y（i， i）（t）

[20]NEELY M J， WALRAND J. Stochastic Network Optimization with Application to Communication and Queueing Systems [M]. Williston： Morgan and Claypool， 2010： 45-48.

[21]MEYN S P， TWEEDIE R L. Stability of Markovian processes III： Foster-Lyapunov criteria for continuous-time processes [J]. Advances in Applied Probability， 1993， 25（3）： 518-548.

This work is partially supported by the Natural Science Foundation of Guangdong Province （2015A030310287）， the College Students Innovation and Entrepreneurship Training Program of Guangdong University of Petrochemical Technology （733149）.

GUO Mian， born in 1979， Ph. D.， lecturer. Her research interests include edge computing， cloud computing， network quality of service， deep reinforcement learning.

LI Qiqi， born in 1998. Her research interests include edge computing， deep learning.

收稿日期：2019-05-27;修回日期：2019-06-27;錄用日期：2019-07-02。

基金項目：廣東省自然科學基金資助項目（2015A030310287）;廣東石油化工學院大學生創(chuàng)新創(chuàng)業(yè)培育計劃項目（733149）。

作者簡介：郭棉（1979—），女，廣東茂名人，講師，博士，CCF會員，主要研究方向：邊緣計算、云計算、網(wǎng)絡服務質量、深度強化學習;李綺琦（1998—），女，廣東廣州人，主要研究方向：邊緣計算、深度學習。

文章編號：1001-9081（2019）12-3590-07 DOI：10.11772/j.issn.1001-9081.2019050891