鐘云峰，宋偉寧

(東華理工大學(xué) 信息工程學(xué)院，江西 南昌 330013)

0 引 言

近年來(lái)，隨著互聯(lián)網(wǎng)、無(wú)線(xiàn)接入技術(shù)和智能終端技術(shù)的發(fā)展，極大推動(dòng)了物聯(lián)網(wǎng)(Internet of Things，IoT)產(chǎn)業(yè)的發(fā)展。物聯(lián)網(wǎng)垂直應(yīng)用領(lǐng)域的研究也在快速推進(jìn)，產(chǎn)生了許多的應(yīng)用場(chǎng)景[1]。隨著工業(yè)4.0、“中國(guó)制造2025”的提出，工業(yè)互聯(lián)網(wǎng)成為解決智能工廠(chǎng)中許多問(wèn)題的主要方案[2]。作為云計(jì)算的拓展和補(bǔ)充，邊緣計(jì)算受到越來(lái)越多人的重視[3]。針對(duì)由于云計(jì)算采用集中式計(jì)算造成的網(wǎng)絡(luò)擁塞以及傳輸時(shí)延較大的問(wèn)題，邊緣計(jì)算采用了分布式計(jì)算方式，由分布在網(wǎng)絡(luò)中的多個(gè)服務(wù)器接受用戶(hù)的計(jì)算任務(wù)，從而降低設(shè)備上傳數(shù)據(jù)至云服務(wù)器的需求，減小了網(wǎng)絡(luò)擁塞[4]。邊緣計(jì)算是工業(yè)互聯(lián)中的關(guān)鍵技術(shù)，云計(jì)算和邊緣計(jì)算優(yōu)勢(shì)互補(bǔ)，共同促進(jìn)整個(gè)工業(yè)IT和OT的深度融合。

目前大多數(shù)研究針對(duì)的都是移動(dòng)邊緣計(jì)算，計(jì)算卸載技術(shù)解決了用戶(hù)等待時(shí)延高和電池電量快速消耗的問(wèn)題。葉桓宇[5]利用邊緣計(jì)算(Edge Computing，EC)和軟件定義網(wǎng)絡(luò)(Software Defined Networks，SDN)的技術(shù)特點(diǎn)，提出了一種新型SDIN架構(gòu)，并在該架構(gòu)的基礎(chǔ)上，設(shè)計(jì)實(shí)現(xiàn)多QoS的優(yōu)先級(jí)隊(duì)列計(jì)算卸載算法。Liu Juan等人[6]根據(jù)建立的模型，使用馬爾可夫決策過(guò)程對(duì)每個(gè)任務(wù)的平均能耗和平均時(shí)延進(jìn)行分析，并提出了一種有效的一維搜索算法，以找到最佳的任務(wù)調(diào)度策略，降低了任務(wù)時(shí)延。Mao Y等人[7]提出了一種基于Lyapunov優(yōu)化的動(dòng)態(tài)計(jì)算卸載(LODCO)算法，有效降低了時(shí)延。還有Jia M、Kao Y H[8-9]也提出了以?xún)?yōu)化時(shí)延為目標(biāo)的在線(xiàn)任務(wù)卸載算法。以上是以?xún)?yōu)化時(shí)延為目標(biāo)的，還有以權(quán)衡時(shí)延和能耗為目標(biāo)的研究。例如，代美玲等人[10]以最小化任務(wù)時(shí)延和設(shè)備能耗為目標(biāo)，把問(wèn)題描述為資源約束下的最小化能耗和時(shí)延加權(quán)和的凸優(yōu)化問(wèn)題，提出基于乘子法的計(jì)算卸載與資源分配解決該問(wèn)題。孟陳融[11]提出了權(quán)衡時(shí)延和能耗的任務(wù)卸載模型，設(shè)計(jì)了一種啟發(fā)式算法來(lái)解決該問(wèn)題，有效降低了任務(wù)的時(shí)延和設(shè)備的能耗。Nan Y、Wang W、Liu L Q[12-14]等人也提出了能耗和時(shí)延的權(quán)衡優(yōu)化的卸載方案。周鵬等人[15]提出了一種工業(yè)物聯(lián)網(wǎng)中計(jì)算任務(wù)跨域卸載模型，將資源分配與計(jì)算卸載分為兩個(gè)子問(wèn)題，分別得出兩個(gè)子問(wèn)題的最優(yōu)解，最終就是整個(gè)優(yōu)化問(wèn)題的最優(yōu)解。

以上大多數(shù)研究都是針對(duì)移動(dòng)邊緣計(jì)算的，在工廠(chǎng)中大多數(shù)設(shè)備都是有線(xiàn)供電，移動(dòng)邊緣計(jì)算的模型和卸載策略不適用。該文設(shè)計(jì)了一種基于云邊協(xié)同的工業(yè)互聯(lián)網(wǎng)環(huán)境下多任務(wù)計(jì)算卸載模型和以?xún)?yōu)化時(shí)延為目標(biāo)的計(jì)算卸載策略。首先融合邊緣云與遠(yuǎn)端云構(gòu)建了一種面向多終端的網(wǎng)絡(luò)架構(gòu)，依此建立系統(tǒng)模型；在此模型基礎(chǔ)上，構(gòu)造了以?xún)?yōu)化卸載時(shí)延的目標(biāo)函數(shù)；最后，設(shè)計(jì)求解算法，求出最優(yōu)解，合理實(shí)施計(jì)算卸載。

1 系統(tǒng)模型及問(wèn)題描述

1.1 系統(tǒng)模型

基于云邊協(xié)同的計(jì)算卸載框架如圖1所示，由一個(gè)遠(yuǎn)端的云計(jì)算中心、多個(gè)近處的邊緣服務(wù)器以及多個(gè)工廠(chǎng)中的終端設(shè)備組成。在工廠(chǎng)中的邊緣服務(wù)器不一定只有一個(gè)，可以根據(jù)終端設(shè)備數(shù)量或者任務(wù)請(qǐng)求量來(lái)劃分出幾個(gè)區(qū)域，在每個(gè)區(qū)域放置一個(gè)邊緣服務(wù)器。遠(yuǎn)端云服務(wù)中心與邊緣服務(wù)中心、邊緣服務(wù)中心與終端設(shè)備分別存在著一對(duì)多的映射關(guān)系，邊緣服務(wù)器通過(guò)互聯(lián)網(wǎng)接入云服務(wù)中心，終端設(shè)備通過(guò)有線(xiàn)網(wǎng)或者無(wú)線(xiàn)網(wǎng)接入到邊緣服務(wù)器。終端設(shè)備把要執(zhí)行的任務(wù)信息發(fā)送到邊緣服務(wù)器，包括任務(wù)需要上傳的數(shù)據(jù)量大小、需要的CPU時(shí)鐘周期數(shù)、任務(wù)的返回?cái)?shù)據(jù)量大小等信息，服務(wù)器根據(jù)任務(wù)信息和邊緣服務(wù)器的資源信息來(lái)作出決策，下發(fā)至終端。

圖1 基于云邊協(xié)同的計(jì)算卸載框架

1.2 時(shí)延模型

采用邊緣計(jì)算的目的就是為了任務(wù)能夠快速響應(yīng)，所以能耗優(yōu)化不是該文考慮的方面，系統(tǒng)優(yōu)化的目標(biāo)是時(shí)延。系統(tǒng)時(shí)延由計(jì)算時(shí)延和通信時(shí)延組成，計(jì)算時(shí)延有本地計(jì)算時(shí)延、邊緣計(jì)算時(shí)延、云端計(jì)算時(shí)延；通信時(shí)延有數(shù)據(jù)上傳傳輸時(shí)延和結(jié)果返回傳輸時(shí)延。由于一般回傳的數(shù)據(jù)量相對(duì)較小，所以該文不考慮結(jié)果回傳時(shí)延。

1.3 終端計(jì)算模型

假設(shè)一個(gè)區(qū)域內(nèi)有N個(gè)終端設(shè)備，表示為N=[1,2,…,n]，其中每個(gè)終端都有M個(gè)任務(wù)需要執(zhí)行，表示為M=[1,2,…,m]。每個(gè)計(jì)算任務(wù)定義為元組Ai,j=(Di,j,Wi,j,Ri,j)(i∈N,j∈M)，Di,j表示當(dāng)前任務(wù)的數(shù)據(jù)量，Wi,j表示當(dāng)前計(jì)算任務(wù)所需要的CPU時(shí)鐘周期數(shù)，Ri,j表示響應(yīng)數(shù)據(jù)大小。任務(wù)在終端設(shè)備上執(zhí)行的時(shí)延為計(jì)算時(shí)延tlocal，可表示為：

(1)

1.4 邊緣計(jì)算模型

任務(wù)卸載到邊緣服務(wù)器的時(shí)延有數(shù)據(jù)上傳時(shí)延、計(jì)算時(shí)延、等待時(shí)延，所以任務(wù)在邊緣服務(wù)器上執(zhí)行的時(shí)延tedge可表示為：

(2)

其中，twait為基于排隊(duì)論的等待時(shí)延預(yù)測(cè)[16]。

根據(jù)排隊(duì)論的Little法則，在平衡條件下，任務(wù)在服務(wù)器等待的平均時(shí)間為系統(tǒng)的平均等待隊(duì)長(zhǎng)除以任務(wù)的平均進(jìn)入率，即：

(3)

在時(shí)長(zhǎng)為t的時(shí)間段內(nèi)，等待的任務(wù)數(shù)為Nt-S，隨著時(shí)間的增加，計(jì)算平均等待隊(duì)長(zhǎng)為：

(4)

其中，Nt為t時(shí)刻的全部任務(wù)數(shù)，S為邊緣服務(wù)器同時(shí)服務(wù)的最大任務(wù)數(shù)。同時(shí)得到任務(wù)平均進(jìn)入率。

(5)

其中，N0為決策開(kāi)始時(shí)系統(tǒng)內(nèi)的任務(wù)數(shù)。由此，可以得到排隊(duì)等待時(shí)間的預(yù)測(cè)值。

1.5 云端計(jì)算模型

任務(wù)卸載到云服務(wù)中心的時(shí)延有數(shù)據(jù)上傳時(shí)延和計(jì)算時(shí)延，所以任務(wù)在云服務(wù)器上執(zhí)行的時(shí)延tcloud可表示為：

(6)

1.6 問(wèn)題描述

一個(gè)任務(wù)Ai,j有可能在本地執(zhí)行或者卸載到邊緣服務(wù)器、云服務(wù)器，設(shè)xi,j為1表示在本地執(zhí)行，xi,j為0表示卸載執(zhí)行；yi,j為0表示沒(méi)有卸載到邊緣服務(wù)器，yi,j為1表示卸載到邊緣服務(wù)器；zi,j為0表示沒(méi)有卸載到云服務(wù)器，zi,j為1表示卸載到云服務(wù)器。所以任務(wù)Ai,j的執(zhí)行時(shí)延ti,j可表示為：

(7)

優(yōu)化的目標(biāo)是總時(shí)延最小即：

(8)

約束條件為：

xi,j+yi,j+zi,j=1，xi,j,yi,j,zi,j∈0,1

(9)

變量標(biāo)識(shí)如表1所示。

表1 變量標(biāo)識(shí)

續(xù)表1

2 卸載策略

根據(jù)上面描述，問(wèn)題變成了一個(gè)01整數(shù)規(guī)劃問(wèn)題，只需要求得最優(yōu)解然后按照最優(yōu)解進(jìn)行任務(wù)卸載。求解01規(guī)劃的方法有很多，一般的有分支定界法、枚舉法和模擬退火法，當(dāng)M和N比較大時(shí)分支定界法和枚舉法會(huì)出現(xiàn)收斂速度慢的問(wèn)題。所以該文選取了混合整數(shù)線(xiàn)性規(guī)劃算法來(lái)求解上述問(wèn)題，混合整數(shù)線(xiàn)性規(guī)劃算法具有求解速度快且是精確解的優(yōu)點(diǎn)。

混合整數(shù)線(xiàn)性規(guī)劃算法求解步驟：

01整數(shù)規(guī)劃是特殊的整數(shù)規(guī)劃，這類(lèi)問(wèn)題被分類(lèi)為NP困難問(wèn)題?；旌险麛?shù)線(xiàn)性規(guī)劃算法使用此基本策略來(lái)求解混合整數(shù)線(xiàn)性規(guī)劃?；旌险麛?shù)線(xiàn)性規(guī)劃算法可以在任一階段完成問(wèn)題的求解。如果它在某個(gè)階段成功求解了問(wèn)題，算法不會(huì)執(zhí)行后面的階段。

(1)使用線(xiàn)性規(guī)劃預(yù)處理縮減問(wèn)題的規(guī)模。預(yù)處理步驟旨在消除冗余變量和約束，改善模型的尺度和約束矩陣的稀疏性，加強(qiáng)變量的邊界，檢測(cè)模型的原始和對(duì)偶不可行性。

(2)使用線(xiàn)性規(guī)劃求解初始松弛(非整數(shù))問(wèn)題。

(3)執(zhí)行混合整數(shù)規(guī)劃預(yù)處理以收緊混合整數(shù)問(wèn)題的LP松弛?；旌险麛?shù)規(guī)劃預(yù)處理的主要目標(biāo)是簡(jiǎn)化后續(xù)的分支定界計(jì)算。預(yù)處理包括快速預(yù)檢查和消除一些無(wú)用的子問(wèn)題候選項(xiàng)，以免分支定界算法對(duì)其進(jìn)行分析。

(4)嘗試切割生成以進(jìn)一步收緊混合整數(shù)問(wèn)題的LP松弛。

(5)嘗試使用啟發(fā)式方法求得整數(shù)可行解。

(6)使用分支定界算法系統(tǒng)地搜索最優(yōu)解。

最后根據(jù)求解出來(lái)的最優(yōu)解來(lái)執(zhí)行卸載策略。

3 仿真結(jié)果與分析

為了驗(yàn)證云邊協(xié)同多任務(wù)計(jì)算卸載策略的有效性，首先比較文中方法與局部卸載方法的差異，即任務(wù)只在本地或者邊緣服務(wù)器執(zhí)行，不卸載到云服務(wù)中心；再將文中的卸載時(shí)延策略與最小時(shí)延能耗策略[10]進(jìn)行比較；然后研究在用上述兩種方法求解的情況下，計(jì)算任務(wù)總時(shí)延和任務(wù)數(shù)量的關(guān)系；最后比較模擬退火算法和混合整數(shù)線(xiàn)性規(guī)劃算法在計(jì)算任務(wù)的總時(shí)延和算法執(zhí)行時(shí)間方面的差異。

仿真實(shí)驗(yàn)在Matlab環(huán)境下進(jìn)行，系統(tǒng)的各個(gè)仿真參數(shù)如表2所示。表2中給出了任務(wù)數(shù)據(jù)量大小、任務(wù)所需要的CPU時(shí)鐘周期數(shù)、終端設(shè)備的計(jì)算能力、邊緣服務(wù)器的計(jì)算能力、云服務(wù)器的計(jì)算能力、終端到邊緣服務(wù)器的傳輸速率、邊緣服務(wù)器到云服務(wù)器的傳輸速率。

表2 系統(tǒng)的仿真參數(shù)設(shè)置

首先，通過(guò)設(shè)置不同的任務(wù)數(shù)量，來(lái)比較不同卸載策略完成任務(wù)的總時(shí)延。計(jì)算任務(wù)總時(shí)延與任務(wù)數(shù)量的關(guān)系如圖2所示。圖2比較了云邊協(xié)同多任務(wù)計(jì)算卸載策略(文中方法)與局部卸載方法完成任務(wù)的總時(shí)延，從圖中可以看出文中方法優(yōu)于局部卸載方法，相比局部卸載方法時(shí)延降低了4%。所以在實(shí)際的部署中，將邊緣服務(wù)器與云服務(wù)器聯(lián)動(dòng)起來(lái)能夠有效地降低任務(wù)時(shí)延，提高服務(wù)質(zhì)量。

圖2 不同卸載策略下任務(wù)完成時(shí)間的比較

再將文中卸載策略與最小時(shí)延和能耗卸載策略進(jìn)行比較，比較結(jié)果如圖3所示。從圖3可以看出，與最小時(shí)延和能耗的卸載策略相比，文中的最小時(shí)延卸載策略完成任務(wù)的時(shí)延更低，時(shí)延降低了10%。在時(shí)延要求很高的情況下，不考慮能耗的卸載策略能夠更好地降低時(shí)延。

圖4為不同任務(wù)數(shù)量下文中策略分配任務(wù)的情況。從圖中可以看到任務(wù)會(huì)卸載到不同的位置，卸載策略會(huì)根據(jù)任務(wù)的數(shù)據(jù)量大小、計(jì)算量大小等信息將任務(wù)卸載到最適合的位置來(lái)減小時(shí)延。隨著任務(wù)數(shù)量的增加，邊緣設(shè)備的壓力會(huì)增加，所以會(huì)有更多的任務(wù)卸載到云端和設(shè)備終端。

圖3 不同卸載策略下任務(wù)完成時(shí)間的比較

圖4 任務(wù)卸載位置分配

模擬退火算法與混合整數(shù)線(xiàn)性規(guī)劃算法的比較如圖5所示。從圖5可以看出，兩種算法中時(shí)延都隨著任務(wù)數(shù)量的增加而增加。混合整數(shù)線(xiàn)性規(guī)劃算法在不同任務(wù)數(shù)量下的性能都優(yōu)于模擬退火算法，這是因?yàn)榛旌险麛?shù)線(xiàn)性規(guī)劃算法能夠求解出01整數(shù)規(guī)劃的最優(yōu)解，而模擬退火算法作為啟發(fā)式算法，不一定能夠求出最優(yōu)解。

圖5 模擬退火算法與混合整數(shù)線(xiàn)性規(guī)劃算法的比較

當(dāng)設(shè)備數(shù)量增加時(shí)，假設(shè)每臺(tái)設(shè)備有10個(gè)任務(wù)，比較模擬退火算法與混合整數(shù)線(xiàn)性規(guī)劃算法的算法執(zhí)行時(shí)間，如表3所示。從表3可以看出，模擬退火算法的執(zhí)行時(shí)間隨著設(shè)備數(shù)量的增多而增加，隨著設(shè)備規(guī)模的增加，混合整數(shù)線(xiàn)性規(guī)劃算法的算法執(zhí)行時(shí)間基本沒(méi)太大的增加。因此，仿真結(jié)果表明混合整數(shù)線(xiàn)性規(guī)劃算法明顯優(yōu)于模擬退火算法。

表3 模擬退火算法與混合整數(shù)線(xiàn)性規(guī)劃

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

研究了基于云邊協(xié)同的多任務(wù)計(jì)算卸載問(wèn)題，設(shè)計(jì)了基于云邊協(xié)同的計(jì)算卸載框架；基于此系統(tǒng)模型，以最小化任務(wù)時(shí)延為目標(biāo)，設(shè)計(jì)了一種多任務(wù)計(jì)算卸載方法。針對(duì)現(xiàn)實(shí)中任務(wù)排隊(duì)時(shí)延計(jì)算問(wèn)題，采用了一種基于排隊(duì)論的等待時(shí)延預(yù)測(cè)方法。針對(duì)根據(jù)系統(tǒng)模型建立的01整數(shù)規(guī)劃問(wèn)題，提出了混合整數(shù)線(xiàn)性規(guī)劃算法的解法。仿真結(jié)果表明，與局部卸載方法和最小時(shí)延和能耗卸載方法相比，提出的基于云邊協(xié)同的計(jì)算卸載方法在時(shí)延上有所優(yōu)化，在算法執(zhí)行時(shí)間上也有很大的提升。