陳孟雨,賈敏智

(太原理工大學(xué)電氣與動(dòng)力工程學(xué)院,山西 太原 030024)

1 引言

隨著智能設(shè)備在日常生活中越來越流行以及用戶體驗(yàn)要求的不斷提高,推動(dòng)著大數(shù)據(jù)和機(jī)器學(xué)習(xí)領(lǐng)域越來越多復(fù)雜應(yīng)用程序的興起,這些應(yīng)用程序?qū)⑹菙?shù)據(jù)密集型、延遲敏感和實(shí)時(shí)的[1]。傳統(tǒng)的云計(jì)算架構(gòu)將云服務(wù)器部署在遠(yuǎn)離生成應(yīng)用程序數(shù)據(jù)的地方,一些延遲要求比較高的應(yīng)用程序不能容忍云計(jì)算所帶來的巨大且不可預(yù)測(cè)的延遲[2,3]。

為了保證對(duì)延時(shí)敏感的應(yīng)用程序的服務(wù)質(zhì)量(QoS)[4],思科提出了霧計(jì)算框架[5],通過將計(jì)算、存儲(chǔ)和網(wǎng)絡(luò)資源放在更貼近用戶的位置,霧計(jì)算可以減少IoT應(yīng)用程序服務(wù)延遲[6]、網(wǎng)絡(luò)帶寬使用和成本,提供上下文感知,并增強(qiáng)對(duì)延遲敏感的應(yīng)用程序的QoS。然而,某些物聯(lián)網(wǎng)應(yīng)用程序在空間和時(shí)間維度上對(duì)霧中資源的使用是突發(fā)性的,并且對(duì)霧資源的使用會(huì)隨著時(shí)間或空間變化,是一種動(dòng)態(tài)模式。因此,通過在霧資源中動(dòng)態(tài)部署應(yīng)用程序服務(wù)來降低延遲,已經(jīng)成為霧計(jì)算領(lǐng)域中的重點(diǎn)研究問題。

Sami H[7]等人通過動(dòng)態(tài)將軟件模塊推向霧節(jié)點(diǎn),實(shí)現(xiàn)了一個(gè)霧計(jì)算中動(dòng)態(tài)資源重新分配的方案,該研究為霧中的存儲(chǔ)和成本感知?jiǎng)討B(tài)服務(wù)供應(yīng)提供了算法和理論基礎(chǔ),但該方案并未考慮超低延遲要求和延遲違規(guī)度量。Ghobaei-Arani M[8]等人將霧中的服務(wù)布局問題建模為整數(shù)線性規(guī)劃優(yōu)化,它們的優(yōu)化目標(biāo)是在考慮應(yīng)用QoS要求的情況下最大限度地利用霧景。仿真結(jié)果表明,該模型降低了處理成本,且不違反應(yīng)用期限。但該優(yōu)化是一個(gè)NP-hard問題,幾乎不可能大規(guī)模求解。Skarlat O[9]等人提出了一種感知驅(qū)動(dòng)的霧化服務(wù)部署模型,該模型中傳感器發(fā)射數(shù)據(jù)到霧中,利用霧資源對(duì)數(shù)據(jù)進(jìn)行處理,最后驅(qū)動(dòng)執(zhí)行器進(jìn)行必要操作,該模型具有較好的實(shí)際應(yīng)用價(jià)值,但所提出的模型并未考慮物聯(lián)網(wǎng)節(jié)點(diǎn)上引入組件的開銷,以及物聯(lián)網(wǎng)節(jié)點(diǎn)運(yùn)行霧軟件和虛擬化技術(shù)。盡管上述研究對(duì)物聯(lián)網(wǎng)中應(yīng)用程序服務(wù)部署具有實(shí)質(zhì)性貢獻(xiàn),但它們不能直接應(yīng)用于延遲敏感的霧化物聯(lián)網(wǎng)應(yīng)用程序服務(wù)的動(dòng)態(tài)部署。

為解決霧計(jì)算中傳統(tǒng)服務(wù)部署方式在延遲方面存在的不足,本文提出一種霧計(jì)算中延遲優(yōu)化的服務(wù)動(dòng)態(tài)部署方法。通過設(shè)計(jì)霧計(jì)算中應(yīng)用程序服務(wù)部署模型,根據(jù)該模型提出了應(yīng)用程序服務(wù)延遲的計(jì)算方法,并采用改進(jìn)的MDAF算法對(duì)霧計(jì)算中服務(wù)進(jìn)行動(dòng)態(tài)部署,找到動(dòng)態(tài)霧服務(wù)部署方案的最優(yōu)解。通過實(shí)驗(yàn)驗(yàn)證了該方法提高了在霧計(jì)算中動(dòng)態(tài)部署和釋放的物聯(lián)網(wǎng)應(yīng)用程序服務(wù)的速度,減少了應(yīng)用程序服務(wù)的平均服務(wù)延遲,具有良好的適用性和可擴(kuò)展性。

2 霧計(jì)算框架

霧計(jì)算是思科創(chuàng)造的一個(gè)術(shù)語(yǔ),被定義為一種分布式計(jì)算模式,它將云提供的服務(wù)擴(kuò)展到網(wǎng)絡(luò)的邊緣[10]。使從云數(shù)據(jù)中心到網(wǎng)絡(luò)邊緣設(shè)備(包括互聯(lián)網(wǎng)服務(wù)提供商、網(wǎng)關(guān)、蜂窩基站和私有云部署等中間設(shè)備)的基礎(chǔ)架構(gòu)無縫融合到一系列資源中,這些資源將被提供給多個(gè)租戶用于托管應(yīng)用程序[11-13]。

霧計(jì)算的系統(tǒng)架構(gòu)由多層組成,每層負(fù)責(zé)特定的任務(wù),以方便更高層的操作。在該架構(gòu)中,最底層由物聯(lián)網(wǎng)設(shè)備組成,這些設(shè)備與現(xiàn)實(shí)世界交互,是數(shù)據(jù)的來源或接收器,分布在不同的位置,并通過網(wǎng)關(guān)將數(shù)據(jù)發(fā)送到上一層進(jìn)行進(jìn)一步處理。下一個(gè)邏輯層是邊緣層,邊緣設(shè)備位于其中,例如WiFi接入點(diǎn),路由器和交換機(jī)等,邊緣計(jì)算通常在該層的邊緣設(shè)備上進(jìn)行。最頂層是云層,大型云服務(wù)器和配置完善的數(shù)據(jù)中心位于其中,云層中的云服務(wù)器和數(shù)據(jù)中心通常部署在遠(yuǎn)離物聯(lián)網(wǎng)設(shè)備生成數(shù)據(jù)的地方。邊緣層和云層之間發(fā)生霧計(jì)算的整個(gè)資源連續(xù)體稱為霧連續(xù)體,霧連續(xù)體不僅限于邊緣層,它包括邊緣層并擴(kuò)展到云。因此,霧計(jì)算是分層的,它提供了從云層到物聯(lián)網(wǎng)任何地方的計(jì)算,聯(lián)網(wǎng),存儲(chǔ)和控制等,而邊緣計(jì)算往往是邊緣層的計(jì)算[13,14]。

霧計(jì)算系統(tǒng)的基本架構(gòu)如圖1所示。

圖1 霧計(jì)算系統(tǒng)基本架構(gòu)

3 系統(tǒng)模型

用于動(dòng)態(tài)部署霧服務(wù)的系統(tǒng)架構(gòu)如圖2所示。IoT請(qǐng)求到霧節(jié)點(diǎn)的聚合傳入流量率由流量監(jiān)控代理監(jiān)控,這些監(jiān)控代理具有豐富的流量監(jiān)控北行API,用于監(jiān)控應(yīng)用程序級(jí)流量[15,16]。最終,流量率監(jiān)控在霧服務(wù)控制器的流量監(jiān)控模塊中完成。

圖2 動(dòng)態(tài)霧服務(wù)部署系統(tǒng)架構(gòu)

霧服務(wù)控制器是實(shí)現(xiàn)霧服務(wù)動(dòng)態(tài)部署的核心地方,其通過監(jiān)控到霧節(jié)點(diǎn)的傳入流量和其它參數(shù)來決定部署和釋放服務(wù),從本質(zhì)上解決了動(dòng)態(tài)霧服務(wù)部署問題。霧服務(wù)控制器有一個(gè)服務(wù)數(shù)據(jù)庫(kù)模塊,用于存儲(chǔ)接收到的應(yīng)用程序服務(wù)和每個(gè)服務(wù)的延遲及其它參數(shù)。霧服務(wù)控制器根據(jù)服務(wù)數(shù)據(jù)庫(kù)去部署霧節(jié)點(diǎn)所需要的服務(wù),這類似于最近提出的的容器注冊(cè)表[17]。

當(dāng)某一特定服務(wù)的流量需求增加時(shí),控制器的提供計(jì)劃模塊在相應(yīng)霧節(jié)點(diǎn)部署一個(gè)新的服務(wù)來減少IoT服務(wù)延遲。另一方面,如果對(duì)某一特定服務(wù)的需求并不大,則提供計(jì)劃模塊會(huì)釋放該服務(wù),以節(jié)省資源成本。部署和發(fā)布操作都是根據(jù)延遲要求執(zhí)行的,例如,當(dāng)流量需求較低,但某項(xiàng)業(yè)務(wù)的延遲要求比較嚴(yán)格時(shí),會(huì)導(dǎo)致該業(yè)務(wù)不被釋放。

在本文中,提出一種相關(guān)優(yōu)化問題的解決方案以解決動(dòng)態(tài)霧服務(wù)部署問題。

假設(shè)一組霧節(jié)點(diǎn)由F表示,一組云節(jié)點(diǎn)由C表示,一組物聯(lián)網(wǎng)應(yīng)用程序服務(wù)由A表示,并且服務(wù)a所期望的延遲等級(jí)表示為qa∈(0,1),延遲閾值由tha表示。一組霧節(jié)點(diǎn)和云服務(wù)器被建模為曲線圖G=(V,E),其中節(jié)點(diǎn)集V包括霧節(jié)點(diǎn)F和云服務(wù)器C,邊緣集E包括節(jié)點(diǎn)之間的邏輯鏈路。霧節(jié)點(diǎn)和云服務(wù)器可以位于霧連續(xù)體中的任何地方,并且對(duì)物理網(wǎng)絡(luò)拓?fù)錄]有限制。每個(gè)邊緣e(src,dst)∈E與倆個(gè)數(shù)字相關(guān)聯(lián):邏輯鏈路E的傳輸速率re和邏輯鏈路E的傳播延遲de。

優(yōu)化問題的主要決策變量是布局二進(jìn)制變量,定義如下

(1)

(2)

3.1 流量模型

由于不同的IoT請(qǐng)求的處理時(shí)間不同,為了準(zhǔn)確評(píng)估霧節(jié)點(diǎn)或云服務(wù)器的等待時(shí)間,需要考慮不同IoT請(qǐng)求的處理時(shí)間。為此,以每單位時(shí)間內(nèi)的指令(MIPS)表示霧節(jié)點(diǎn)的流量傳入率,vaj表示霧節(jié)點(diǎn)對(duì)于服務(wù)a的指令到達(dá)率。這時(shí),由霧節(jié)點(diǎn)j所接收的傳入請(qǐng)求的指令的到達(dá)率定義如下

(3)

(4)

(5)

3.2 資源模型

霧節(jié)點(diǎn)和云服務(wù)器的資源使用率不應(yīng)該超過它們的容量,如下公式表示:

(6)

(7)

3.3 時(shí)間模型

(8)

(9)

(10)

4 問題形成與解決方案

4.1 問題形成

4.1.1 平均服務(wù)延遲

應(yīng)用程序的服務(wù)延遲定義為IoT節(jié)點(diǎn)發(fā)送服務(wù)請(qǐng)求與接收到該請(qǐng)求的響應(yīng)之間的時(shí)間間隔,則霧節(jié)點(diǎn)j為IoT應(yīng)用程序的服務(wù)a提供的平均服務(wù)延遲為

*(1-xaj)

(11)

式中,Ia是運(yùn)行服務(wù)a的IoT節(jié)點(diǎn)集。

4.1.2 延遲違規(guī)

為了度量給定服務(wù)a的質(zhì)量,需要查看IoT請(qǐng)求中不滿足延遲閾值tha的百分比,稱為延遲違規(guī)。首先檢查由霧節(jié)點(diǎn)j為物聯(lián)網(wǎng)節(jié)點(diǎn)的服務(wù)a提供的平均服務(wù)延遲daj是否大于服務(wù)數(shù)據(jù)庫(kù)中服務(wù)a延遲閾值,定義一個(gè)二進(jìn)制變量uaj表示

(12)

然后根據(jù)定義的延遲要求來度量給定服務(wù)的延遲違規(guī),由于來自物聯(lián)網(wǎng)節(jié)點(diǎn)的超過延遲閾值的延遲樣本的百分比不應(yīng)超過1-qa,則服務(wù)a的延遲違規(guī)定義如下

(13)

4.2 改進(jìn)MDAF算法

根據(jù)霧計(jì)算環(huán)境下物聯(lián)網(wǎng)應(yīng)用程序服務(wù)的部署模型以及延遲計(jì)算方法,提出一種改進(jìn)MDAF算法以解決霧服務(wù)的動(dòng)態(tài)部署問題,旨在最大程度減少延遲以及延遲違規(guī),算法如下:

算法1 改進(jìn)MDAF算法

輸出:最小延遲違規(guī)時(shí)服務(wù)a的位置

1) 根據(jù)等式(2)部署/發(fā)布云上的服務(wù)a

2) 讀取服務(wù)a到霧節(jié)點(diǎn)的流量傳入率

3) List L 按流量率降序排列霧節(jié)點(diǎn)

5) canDeply=true

7) 從數(shù)組L刪除的下一個(gè)霧節(jié)點(diǎn)j的索引

8) If L is empty then

9) canDeply=false

10) end if

11) If(服務(wù)a沒有部署在霧節(jié)點(diǎn)j上)and(霧節(jié)點(diǎn)j有足夠的存儲(chǔ)和內(nèi)存)

12) 部署服務(wù)a在霧節(jié)點(diǎn)xaj=1

14) end if

15) end while

16) canRelease=true

17) whilecanReleasedo 釋放

18) 從數(shù)組L的尾部獲取一個(gè)已經(jīng)部署服務(wù)a的霧節(jié)點(diǎn)j

19) Setxaj=0

22) 釋放霧節(jié)點(diǎn)j上的服務(wù)axaj=0

23) else

24) Set xaj=1, and canRelease=false exit

25) end if

26) end while

算法2:計(jì)算延遲違規(guī)百分比

2) 根據(jù)等式(11)計(jì)算霧節(jié)點(diǎn)服務(wù)a的延遲daj

3) 根據(jù)等式(12)計(jì)算霧節(jié)點(diǎn)服務(wù)a的uaj

6) end procedure

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

5.1 仿真環(huán)境

為了驗(yàn)證改進(jìn)MDAF算法的動(dòng)態(tài)霧服務(wù)部署方法的有效性,實(shí)驗(yàn)從Ac-cess2000中獲取流量數(shù)據(jù),采用開發(fā)工具JDK7.0實(shí)現(xiàn)改進(jìn)MDAF算法,利用iFogSim模擬器進(jìn)行仿真。系統(tǒng)建模中的符號(hào)定義與模擬器參數(shù)取值如表1所示。

表1 參數(shù)取值與符號(hào)定義

5.2 結(jié)果與分析

根據(jù)上述的參數(shù)取值進(jìn)行仿真,針對(duì)不同閾值情況下,將改進(jìn)MDAF算法的動(dòng)態(tài)霧服務(wù)部署方法與靜態(tài)霧服務(wù)部署以及私有云部署方法進(jìn)行對(duì)比,以此驗(yàn)證改進(jìn)MDAF算法的性能以及動(dòng)態(tài)霧服務(wù)部署的優(yōu)越性。

圖3為不同延遲閾值條件下不同部署方法的平均服務(wù)延遲對(duì)比。當(dāng)延遲閾值小于38毫秒時(shí),所有方法的平均服務(wù)延遲都不會(huì)改變,這是由于當(dāng)前設(shè)置中的仿真參數(shù)值的設(shè)置,所有方法在霧節(jié)點(diǎn)和云服務(wù)器上放置相同數(shù)量的服務(wù)。此時(shí),僅云部署的平均服務(wù)延遲約為58ms,靜態(tài)霧服務(wù)部署的平均服務(wù)延遲約為45ms,而本文改進(jìn)MDAF算法的動(dòng)態(tài)霧服務(wù)部署方法的平均服務(wù)延遲約為27ms,與僅云部署方法和靜態(tài)霧服務(wù)部署方法相比,平均服務(wù)延遲分別降低了大約21ms和18ms,優(yōu)化效果顯著。

圖3 三種方法的平均服務(wù)延遲對(duì)比

當(dāng)延遲閾值大于38ms時(shí),隨著延遲閾值的不斷增大,靜態(tài)霧和動(dòng)態(tài)霧部署方法的平均服務(wù)延遲都會(huì)增加,最終達(dá)到僅云部署的平均服務(wù)延遲58ms。這是因?yàn)?當(dāng)延遲閾值較大時(shí),改進(jìn)MDAF算法傾向于在霧節(jié)點(diǎn)上部署較少的服務(wù),更多的請(qǐng)求將在云中進(jìn)行部署,因此服務(wù)延遲有所提高。另一方面,與僅云部署和靜態(tài)霧部署相比,改進(jìn)MDAF算法的動(dòng)態(tài)霧服務(wù)部署方法的平均服務(wù)延遲最低。由此可知,本文方法能夠在霧計(jì)算中霧服務(wù)靜態(tài)部署的基礎(chǔ)上,得到最優(yōu)部署解,有效降低平均服務(wù)延遲。

圖4為不同延遲閾值條件下不同部署方法的延遲違規(guī)百分比對(duì)比?？梢杂^察到,當(dāng)延遲閾值小于38ms時(shí),由于當(dāng)前實(shí)驗(yàn)中的模擬參數(shù)值進(jìn)行的設(shè)置,所有方法的延遲違反都不會(huì)改變。此時(shí),以僅云部署的延遲違規(guī)率為100%作為參考,靜態(tài)霧服務(wù)部署的延遲違規(guī)率約為82%,改進(jìn)MDAF算法的動(dòng)態(tài)霧服務(wù)部署方法延遲違規(guī)率約為58%,相比僅云部署方法降低接近40%,相比靜態(tài)霧服務(wù)部署方法降低接近15%。并且隨著延遲閾值的不斷增大,所有方法的違規(guī)百分比都將變小,最終趨近于0。由此可知,本文改進(jìn)MDAF算法的動(dòng)態(tài)霧服務(wù)部署方法延遲違規(guī)率最低,而僅云部署的延遲違規(guī)率最高,靜態(tài)霧的違規(guī)是中等的,因?yàn)樗鼈儾⑽瘁槍?duì)最小延遲違規(guī)的目標(biāo)進(jìn)行調(diào)整。

圖4 三種方法延遲違規(guī)百分比對(duì)比

圖5顯示了當(dāng)延遲閾值小于38毫秒時(shí),由于延遲要求較高,動(dòng)態(tài)霧部署將發(fā)揮其性能優(yōu)勢(shì)在霧中部署最多的服務(wù),平均霧服務(wù)約為38個(gè);靜態(tài)霧次之,約為17個(gè);僅云部署方法在霧中沒有服務(wù),平均霧服務(wù)個(gè)數(shù)為0。隨著延遲閾值的不斷增大,當(dāng)其大于38ms時(shí),改進(jìn)MDAF算法將在霧節(jié)點(diǎn)上動(dòng)態(tài)部署了更少的服務(wù),更多的服務(wù)在云服務(wù)器上進(jìn)行部署。當(dāng)延遲閾值大于75ms時(shí),基于以上三種方法的服務(wù)都被部署在云中,沒有在霧節(jié)點(diǎn)上部署服務(wù),因此也不會(huì)發(fā)生延遲違規(guī)。

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

針對(duì)傳統(tǒng)的霧計(jì)算在部署應(yīng)用程序服務(wù)方面存在的高延遲問題,本文提出一種霧計(jì)算中延遲優(yōu)化的服務(wù)動(dòng)態(tài)部署方法。通過對(duì)傳統(tǒng)的應(yīng)用程序服務(wù)部署模型進(jìn)行改進(jìn),提出了一種在霧中動(dòng)態(tài)部署應(yīng)用程序服務(wù)的模型,設(shè)計(jì)了該模型下平均服務(wù)延遲及延遲違規(guī)率的計(jì)算方法,并基于改進(jìn)MDAF算法對(duì)霧中應(yīng)用程序服務(wù)進(jìn)行動(dòng)態(tài)部署。仿真結(jié)果表明,與僅云部署和靜態(tài)霧服務(wù)部署方法相比,基于改進(jìn)MDAF算法的動(dòng)態(tài)霧服務(wù)部署方法將應(yīng)用程序服務(wù)的平均服務(wù)延遲分別降低大約21ms和18ms,延遲違規(guī)率分別降低大約40%和15%。因此,在延遲閾值的約束下,與僅云部署和靜態(tài)霧服務(wù)部署方法相比,本文所提出的霧計(jì)算中延遲優(yōu)化的服務(wù)動(dòng)態(tài)部署方法的平均服務(wù)延遲和延遲違規(guī)率較低,優(yōu)越性能顯著,具有較高的實(shí)用價(jià)值。