基于邊云協同的流數據處理任務卸載優化研究

徐揚 張萌萌

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

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

1 邊云系統模型建模

在以云計算模型為核心的物聯數據接入系統中,數據和計算任務都會傳輸到云中心上進行存儲和執行,但會出現的問題是對于大規模的數據傳輸將會加劇時間延遲和網絡帶寬負載問題,最終導致物聯系統中的計算需求無法及時滿足,此時出現了邊緣計算。邊緣計算系統的架構大致可以劃分為三個層:邊緣設備層、邊緣計算層和云中心層。如圖1所示。

圖1 邊云協同模型Fig.1 Edge-cloud collaboration model

1.1 資源圖建模

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

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

1.2 流圖建模

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

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

2 邊云任務卸載

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

2.1 節點染色

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

2.2 流圖切分

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

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

2.3 任務卸載

在單純的云計算場景下,任務采用的是根據云端節點的資源情況分配不同的計算任務即可,但是對于邊云協同的計算方式,由于存在大量的邊緣設備,邊緣設備計算結果數據無法通過現有的邊緣設備的帶寬資源進行快速的傳輸,所以如何減少從邊緣設備傳輸到云端節點的數據量為邊云任務卸載的主要優化方向。

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

2.4 切割方式選擇

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

3 仿真實驗分析

本文中,評價指標有傳輸數據量和時間延遲。在本文中,我們使用C++來實現我們的算法。為了使實驗結果的信服力更強,我們使用Google cluster trace數據集作為我們的實驗數據集。我們選擇的對比算法為數據全部在云端執行,稱其為CloudMethod。本文中所提出的算法命名為TaskOffload。對比效果如下:

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

圖3 數據量結果對比圖Fig.3 Data volume result comparison chart

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

4 結語

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