基于邊云協(xié)同的流數(shù)據(jù)處理任務(wù)卸載優(yōu)化研究

徐揚(yáng) 張萌萌

(1.天津易華錄信息技術(shù)有限公司,天津 300350;2.北方工業(yè)大學(xué)信息學(xué)院,北京 100144)

如今,伴隨著科技的飛速發(fā)展,物聯(lián)網(wǎng)和5G也不斷發(fā)展,其設(shè)備產(chǎn)生大量的數(shù)據(jù),帶來的最直接的改變就是數(shù)據(jù)爆炸式增長,對于數(shù)據(jù)處理的問題也日益迫切。為了能夠快速的處理日益膨脹的數(shù)據(jù),云計算成為了處理數(shù)據(jù)的首選方式。云計算將全部數(shù)據(jù)都上傳到云數(shù)據(jù)中心也會給網(wǎng)絡(luò)帶寬帶來很大的壓力,云計算已經(jīng)不能滿足一些對實時性比較敏感的應(yīng)用,邊緣計算[1]應(yīng)運(yùn)而生。邊緣計算與云計算數(shù)據(jù)中心不同的是其資源相對匱乏,而云計算中心資源較為豐富,因此本文研究基于邊云協(xié)同的大數(shù)據(jù)處理方式。

1 邊云系統(tǒng)模型建模

在以云計算模型為核心的物聯(lián)數(shù)據(jù)接入系統(tǒng)中,數(shù)據(jù)和計算任務(wù)都會傳輸?shù)皆浦行纳线M(jìn)行存儲和執(zhí)行,但會出現(xiàn)的問題是對于大規(guī)模的數(shù)據(jù)傳輸將會加劇時間延遲和網(wǎng)絡(luò)帶寬負(fù)載問題,最終導(dǎo)致物聯(lián)系統(tǒng)中的計算需求無法及時滿足,此時出現(xiàn)了邊緣計算。邊緣計算系統(tǒng)的架構(gòu)大致可以劃分為三個層:邊緣設(shè)備層、邊緣計算層和云中心層。如圖1所示。

圖1 邊云協(xié)同模型Fig.1 Edge-cloud collaboration model

1.1 資源圖建模

在介紹完邊云協(xié)同的架構(gòu)后,我們對其進(jìn)行建模,將其抽象為DAG圖,稱之為資源圖,表示為 (GresDevices∪=,Devices代表著一系列邊緣設(shè)備, ζ代表的是云計算單元,包含著多個節(jié)點(diǎn)。我們將云節(jié)點(diǎn)聚合到一個邏輯節(jié)點(diǎn)中,在收集數(shù)據(jù)后,可以運(yùn)行整個工作流程。Eres表示邊緣設(shè)備和云之間的物理鏈接,Wres代表的是在邊緣和云之間每秒鐘傳輸?shù)臄?shù)據(jù)量,單位為Mb/s。

在資源圖中,每一個服務(wù)器(包括邊緣和云端)擁有受限的資源,在本文中將其表示為CPU速率,其單位為MIPS。其中MIPS全稱為Million Instructions Per Second,表示的是每秒處理的百萬級的機(jī)器語言指令數(shù),是衡量CPU速度的一個指標(biāo)。

1.2 流圖建模

在大數(shù)據(jù)處理中,每一個數(shù)據(jù)處理的過程都可看做一個計算任務(wù)。對于每一個計算任務(wù),在內(nèi)部將其分解成為若干個子任務(wù),將這些子任務(wù)之間的邏輯關(guān)系或順序構(gòu)建成有向無環(huán)圖(Directed Acyclic Graph,DAG)結(jié)構(gòu),所以我們將數(shù)據(jù)的處理的過程抽象為一個DAG模型。在流處理引擎中,將流數(shù)據(jù)處理服務(wù)抽象為“流圖”,是一個DAG模型。在流處理引擎中,DAG流圖的生成需要指定數(shù)據(jù)來源。在本文中,將流圖的概念細(xì)化為加權(quán)有向無環(huán)圖,將其表示為,Vst表示的是操作算子集合,Est表示的是數(shù)據(jù)流的集合,Wst表示的是網(wǎng)絡(luò)使用量,單位為Mb。

對于每一個操作算子,是指一個處理函數(shù),包括一個輸入、一個處理邏輯、一個輸出,作用為完成數(shù)據(jù)的轉(zhuǎn)換,且具有以下3個屬性:(1)名稱:用Name表示。常見的操作算子有Filter、Map等。(2)類型:用Type表示,取值為0或1。類型1代表的是能同時在邊緣和云端執(zhí)行的操作算子,類型0代表的是只可在云端執(zhí)行的操作算子。對于操作算子分類的原因為:由于邊緣設(shè)備的計算能力、內(nèi)存、電池壽命有限,或者因為一些操作算子無法在邊緣分析框架的執(zhí)行,或者對于用戶來說,擔(dān)心在云中心處理可能會造成隱私的泄露,所以在這里將操作算子進(jìn)行了分類。(3)復(fù)雜度:用Complexity表示,每一個處理函數(shù)的執(zhí)行次數(shù),其單位為MPIS。

2 邊云任務(wù)卸載

提出了一種在資源約束下尋找DAG模型計算任務(wù)的卸載算法,使其在邊緣和云端兩部分運(yùn)行時,從邊緣設(shè)備傳輸至云端的總帶寬與時延最小。首先采用標(biāo)記的方式對無法在邊緣計算的節(jié)點(diǎn)進(jìn)行染色,而后然后采用深度優(yōu)先遍歷的方式將對已有染色節(jié)點(diǎn)有依賴的節(jié)點(diǎn)染色,之后使用FF算法將未染色的子圖完成最小割的切分卸載,得到一種或多種切割方式。最后,對于多種切割方式得到的不同的邊緣和云端任務(wù)子圖,根據(jù)邊云之間的資源進(jìn)行篩選得到最佳的流圖切割方式。

2.1 節(jié)點(diǎn)染色

類型為0的操作算子由于資源限制無法在邊緣節(jié)點(diǎn)執(zhí)行。而對于其他對此類有直接或間接依賴的節(jié)點(diǎn)也無法在邊緣設(shè)備運(yùn)行,否則增加大量的邊云節(jié)點(diǎn)的數(shù)據(jù)傳輸和任務(wù)等待。這里提出了通過深度優(yōu)先搜索的染色的方式將由于直接原因或間接原因無法在邊緣運(yùn)行的節(jié)點(diǎn)染色,以此方式確定我們最終可以在邊緣設(shè)備進(jìn)行執(zhí)行的計算任務(wù)子圖。

2.2 流圖切分

本節(jié)是對于做完染色的DAG計算任務(wù)模型進(jìn)行進(jìn)一步的切分得到所有可以在邊緣運(yùn)行節(jié)點(diǎn)的子圖。采用深度優(yōu)先搜索的方式,從v1節(jié)點(diǎn)對圖進(jìn)行遍歷,對于未被染色節(jié)點(diǎn)進(jìn)行保存。如圖2-(1)所示為染色后的DAG計算模型圖,切割后如圖2-(2)所示,包含有節(jié)點(diǎn)v1、v2、v3、v4、v7四個節(jié)點(diǎn)均可在邊緣設(shè)備進(jìn)行。但此時得到的DAG計算模型圖不包含云端節(jié)點(diǎn),需要進(jìn)一步處理才能做邊云任務(wù)的切分卸載。

圖2 流圖切分示意圖Fig.2 Schematic diagram of flow graph segmentation

2.3 任務(wù)卸載

在單純的云計算場景下,任務(wù)采用的是根據(jù)云端節(jié)點(diǎn)的資源情況分配不同的計算任務(wù)即可,但是對于邊云協(xié)同的計算方式,由于存在大量的邊緣設(shè)備,邊緣設(shè)備計算結(jié)果數(shù)據(jù)無法通過現(xiàn)有的邊緣設(shè)備的帶寬資源進(jìn)行快速的傳輸,所以如何減少從邊緣設(shè)備傳輸?shù)皆贫斯?jié)點(diǎn)的數(shù)據(jù)量為邊云任務(wù)卸載的主要優(yōu)化方向。

如上所述,在DAG圖中,邊代表的是每秒鐘所傳輸?shù)臄?shù)據(jù)量。由于邊云之間的帶寬有限,減少邊云之間傳輸?shù)臄?shù)據(jù)量可以有效地降低數(shù)據(jù)傳輸?shù)臅r延,所以要使得切割邊的權(quán)重之和最小。為了使得切割邊的權(quán)重之和最小,在此使用FF最小割算法來達(dá)到目的,進(jìn)而來分別提取邊云的任務(wù)。

2.4 切割方式選擇

在文獻(xiàn)[2]中利用了最小割來進(jìn)行任務(wù)的分割。但是其并沒有結(jié)合邊云之間的資源。由于FF最小割算法對于同一個圖的切割可能會出現(xiàn)多個切割方式。當(dāng)有多種切割方式時,對于每一個切割方式,得到不同的邊緣任務(wù)子圖和云端任務(wù)子圖。對于每一種邊緣任務(wù)子圖個和云端任務(wù)子圖,分別邊緣任務(wù)和云端任務(wù)的每一個任務(wù)的complexity之和,最后計算其比例,計算方式為資源圖中邊緣節(jié)點(diǎn)的總算力與云端節(jié)點(diǎn)的總算力之比,。對于若干種切分方式,為了使得資源利用率更高,我們選擇資源利用率最高的對應(yīng)的任務(wù)的切分方式。預(yù)估使用率Est_Util計算方式為計算方式為

3 仿真實驗分析

本文中,評價指標(biāo)有傳輸數(shù)據(jù)量和時間延遲。在本文中,我們使用C++來實現(xiàn)我們的算法。為了使實驗結(jié)果的信服力更強(qiáng),我們使用Google cluster trace數(shù)據(jù)集作為我們的實驗數(shù)據(jù)集。我們選擇的對比算法為數(shù)據(jù)全部在云端執(zhí)行,稱其為CloudMethod。本文中所提出的算法命名為TaskOffload。對比效果如下:

如圖3所示,對于邊云之間數(shù)據(jù)量的傳輸,TaskOffload算法的效果要比CloudMethod算法更好。如圖4所示,在邊云之間,TaskOffload算法處理DAG模型的時延要比CloudMethod算法更低。

圖3 數(shù)據(jù)量結(jié)果對比圖Fig.3 Data volume result comparison chart

圖4 時間延遲結(jié)果對比圖Fig.4 Time delay result comparison chart

4 結(jié)語

本文提出了在資源約束的條件下,邊云任務(wù)卸載的問題,一共包括四部分,分別為基于節(jié)點(diǎn)類型的節(jié)點(diǎn)染色、流圖切分、任務(wù)卸載以及切割方式的選擇等。在任務(wù)卸載部分利用了FF算法實現(xiàn)了邊緣任務(wù)的提取,之后通過去重的方法完成了云端任務(wù)的提取,最終使得在資源約束的條件下從邊緣節(jié)點(diǎn)傳輸至云端的數(shù)據(jù)量更少,提高了資源利用率,最后證明了本方法的有效性。