郭棉　李綺琦

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

關(guān)鍵詞：云計(jì)算;邊緣計(jì)算;計(jì)算遷移;能量消耗;服務(wù)質(zhì)量

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

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

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

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

1 系統(tǒng)模型

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

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

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

1.2 業(yè)務(wù)模型

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

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

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

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

平均每個(gè)任務(wù)的大小為：

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

令Y（i，i）（t）、Y（i，n）（t）和Y（i，C）（t）分別表示這Xi（t）個(gè)任務(wù)中決定在本地邊緣節(jié)點(diǎn)i、鄰居邊緣節(jié)點(diǎn)n和云計(jì)算子系統(tǒng)中計(jì)算的任務(wù)的數(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）表示對(duì)應(yīng)的業(yè)務(wù)量，則它們需滿足如下條件：

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 延遲模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式中， Ski是第k個(gè)到達(dá)任務(wù)的大小。

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

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

該計(jì)算延遲由排隊(duì)延遲和服務(wù)延遲組成。

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

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

3）端到端延遲：因此，對(duì)于在時(shí)隙t內(nèi)第k個(gè)到達(dá)計(jì)算節(jié)點(diǎn)i（如邊緣計(jì)算節(jié)點(diǎn)或云計(jì)算子系統(tǒng)）的任務(wù)，設(shè)其大小為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é)點(diǎn)i和云計(jì)算子系統(tǒng)C的計(jì)算延遲; Dkcomm（j，i）和Dkcomm（j，C）分別是傳輸路徑邊緣j-邊緣i、邊緣j-云C的傳輸延遲;IkF（t）、IkNF（t）和IkC（t）是二值決策指示變量，當(dāng)IkF（t）=1時(shí)，表示該任務(wù)在本地邊緣節(jié)點(diǎn)計(jì)算;當(dāng)IkNF（t）=1時(shí)，表示該任務(wù)在鄰居邊緣節(jié)點(diǎn)計(jì)算;當(dāng)IkC（t）=1時(shí)，表示在云計(jì)算子系統(tǒng)計(jì)算。這3個(gè)計(jì)算決策變量之間的取值應(yīng)滿足如下關(guān)系：

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

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

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

數(shù)學(xué)期望為：

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

1.4 能耗模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

數(shù)學(xué)期望為：

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

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

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

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

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

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

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

ω1Pw+ω2Dsys（25）

1.6 問(wèn)題建模

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

則，對(duì)于來(lái)自用戶網(wǎng)絡(luò)i的任務(wù)，有式（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)計(jì)算遷移問(wèn)題可以建模為能耗延遲均衡函數(shù)最小化問(wèn)題，即：

最小化：

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

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

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

Qwi<∞; i∈M*（30）

式（28）由式（25）而來(lái);式（4）是業(yè)務(wù)限制條件;式（26）～（27）的依據(jù)是的定義;不等式（29）～（30）是邊緣節(jié)點(diǎn)排隊(duì)系統(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)化問(wèn)題（28）～（30）中，決策變量為γ（t）。根據(jù)式（26）～（27），當(dāng)γ（t）確定時(shí)， 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)計(jì)算遷移問(wèn)題等效于找出一系列優(yōu)化的γ*（t）（ t=0， 1， …， ∞）來(lái)獲得最小化的G。

2 DPCO策略

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

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

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

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

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

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

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

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

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

式中B是一個(gè)常數(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）并化簡(jiǎn)，得：

Δ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/χ獨(dú)立于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)化的計(jì)算遷移策略γ*（t）（t=0，1，…，∞）來(lái)最小化G，因此把G（γ（t））作為懲罰函數(shù)加入積壓業(yè)務(wù)量的李雅普諾夫漂移函數(shù)，即，定義李雅普諾夫漂移加懲罰函數(shù)為ΔL（t）+VE[G（γ（t））|Qw（t）]。由此得到引理2。

引理2 每一時(shí)隙，對(duì)任意的Qw（t），在任意計(jì)算遷移策略下，邊緣服務(wù)器排隊(duì)系統(tǒng)積壓業(yè)務(wù)量的李雅普諾夫漂移加懲罰函數(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ù)獨(dú)立于V;V是一個(gè)非負(fù)控制參數(shù)。通過(guò)控制V、ω1和ω2的取值，可獲得能耗和平均延遲的均衡優(yōu)化值。

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

2.2 DPCO算法

根據(jù)引理1和引理2的結(jié)論，本文提出分布式DPCO策略來(lái)找出優(yōu)化的γ*（t）（t=0，1，…，∞），來(lái)最小化不等式（38）的右邊，從而最小化ΔL（t）+VE[G（γ（t））|Qw（t）]，以達(dá)到最小化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） 決策過(guò)程：選取γ*i（t），使其滿足

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

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

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

a） 當(dāng)I（i， k）F（t）=1：將該任務(wù)放入本地邊緣服務(wù)器排隊(duì)系

統(tǒng);

b） 當(dāng)I（i， k）NF（t）=1：將該任務(wù)遷移到鄰居邊緣節(jié)點(diǎn)計(jì)算;

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

End程序后

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

算法2 基于DPCO的任務(wù)分配和調(diào)度過(guò)程。程序前

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

Begin： 對(duì)每一時(shí)隙t≥0，do

1） 任務(wù)分配過(guò)程：

a） 邊緣節(jié)點(diǎn)i收到來(lái)自用戶網(wǎng)絡(luò)i的Xi（t）個(gè)計(jì)算任務(wù)，

執(zhí)行下述步驟：

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

ii） 將步驟i）的結(jié)果代入式（26）、（27），計(jì)算出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。

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

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

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