邊緣計算環(huán)境下服務質(zhì)量感知的資源調(diào)度機制

鄒云峰 陳宇 邱文瑋 官國飛

摘要：隨著數(shù)據(jù)分析實時性要求的提高，邊緣計算被提出以更好地利用邊緣設備的資源，可以大大降低應用的延遲時間。本文討論了在邊緣計算中利用基于延遲感知的虛擬機部署來保證數(shù)據(jù)驅(qū)動應用的服務質(zhì)量。在給定的場景下，用帶權(quán)有向無環(huán)圖來描述應用的業(yè)務邏輯和數(shù)據(jù)需求，結(jié)合云環(huán)境下的資源分布情況，提出了一種虛擬機部署算法來降低應用延遲。

【關(guān)鍵詞】延遲感知 數(shù)據(jù)驅(qū)動 虛擬機部署邊緣計算

1 簡介

云計算在過去十年中得到了重點研究。其目的在于為人們提供彈性的資源，這些資源集成在多個數(shù)據(jù)中心中。云提供商以虛擬機的形式為租戶提供計算資源，并且每個虛擬機作為一個完整和獨立的系統(tǒng)運行。一種高效的虛擬機調(diào)度機制不僅能幫助云提供商降低成本，還能為租戶提供高質(zhì)量的服務，數(shù)據(jù)中心具有強大的計算能力以及科學研究和應用的存儲能力。然而，物聯(lián)網(wǎng)設備，視頻監(jiān)控和傳感器等每天產(chǎn)生從幾十兆字節(jié)到千兆字節(jié)的大量數(shù)據(jù)。此外，應用程序的實時性要求越來越嚴格，例如導航、社交網(wǎng)站、電子商務和基于互聯(lián)網(wǎng)的游戲等應用，需要在極短的時間內(nèi)做出響應，這些應用程序通常處理大量的數(shù)據(jù)以獲得租戶所需的信息。例如，波音787每秒將產(chǎn)生大約5千兆字節(jié)的數(shù)據(jù)，但是飛機與地面衛(wèi)星或基站之間的帶寬不足以在短時間內(nèi)傳輸大量數(shù)據(jù)。并行計算越來越多地被用于處理這些應用程序，并且應用的業(yè)務流程可以描述為帶權(quán)有向無環(huán)圖，如MapReduce。因此，租戶需要多個VM來協(xié)作處理應用程序請求，并且每個VM完成應用程序的子任務。然而，由于用戶向數(shù)據(jù)中心傳輸大量的數(shù)據(jù)，很難滿足實時性的要求。

邊緣計算的出現(xiàn)在很大程度上緩解了大量數(shù)據(jù)傳輸引起的服務延遲問題。為了減少數(shù)據(jù)傳輸帶來的延遲，充分利用網(wǎng)絡邊緣設備有限的計算能力，對原始數(shù)據(jù)進行處理，得到中間結(jié)果，減少傳輸數(shù)據(jù)量。這種邊緣計算方法可以大大減少數(shù)據(jù)傳輸?shù)难舆t，滿足高實時性的要求。但是，與云計算相比，邊緣計算在計算能力上仍存在一些不足，雖然邊緣計算可以在一定程度上滿足租戶對延遲敏感的應用程序的需求，但是當處理大型任務時，會出現(xiàn)高延遲。

為彌補云計算高延遲的不足，本文研究了邊緣計算環(huán)境下的虛擬機部署問題。如圖1所示，有多個邊緣設備通過有限帶寬的廣域網(wǎng)連接到數(shù)據(jù)中心。假設邊緣設備計算能力有限，即可以承載有限個虛擬機，而數(shù)據(jù)中心擁有足夠多的資源提供給租戶使用。租戶的請求是具有某種業(yè)務邏輯的一組虛擬機，包括對CPU、內(nèi)存和磁盤等的需求以及虛擬機之間的通信關(guān)系，另外還包括需要處理的輸入數(shù)據(jù)和其他約束條件，如對應時間的要求。虛擬機之間的通信關(guān)系由帶權(quán)有向無環(huán)圖表示，頂點和邊分別表示虛擬機以及虛擬機之間的通信關(guān)系，這意味著某一個虛擬機的輸出被用作下一個虛擬機的輸入，而權(quán)重表示中間結(jié)果的數(shù)據(jù)量。輸入數(shù)據(jù)可以是傳感器收集的原始數(shù)據(jù)，也可以是存儲在數(shù)據(jù)中心的歷史數(shù)據(jù)。為了滿足應用的實時性要求，本文研究了邊緣云環(huán)境下的延遲最小化的虛擬機調(diào)度問題。通過分析虛擬機之間的通信關(guān)系和虛擬機所需輸入數(shù)據(jù)的在網(wǎng)絡中的位置，提出了一種虛擬機部署算法。

2 問題建模

假設云計算中心可容納的虛擬機數(shù)量M1，共有N個邊緣云，每個邊緣云可容納的虛擬機數(shù)量M2，邊緣設備與云計算中心之間的網(wǎng)絡帶寬B，用F_ij表示虛擬機i輸出的數(shù)據(jù)量或虛擬機j從虛擬機i中讀取的輸入數(shù)據(jù)量；x表示虛擬機被部署的位置，O表示云計算中心，1表示邊緣設備；d表示某個請求需要的數(shù)據(jù)的位置，0表示存放在云計算中心的歷史數(shù)據(jù)，1表示由邊緣設備生成的原始數(shù)據(jù)；rd表示某個請求輸入的數(shù)據(jù)量；則某個請求的數(shù)據(jù)傳輸時延可以有如下表示：其中i，j，k表示虛擬機；而某個虛擬機的計算時延不僅與輸入數(shù)據(jù)量有關(guān)，而且與所在計算節(jié)點的負載有關(guān)，某個虛擬機j的輸入數(shù)據(jù)量為input_j=∑_iF_ij，該虛擬機的計算時延可以有如下表示：delay_i=（a'input2_j+β'input_j+γ）'load，其中α，β，γ為參數(shù)，load為該虛擬機所在節(jié)點的計算資源負載，則某請求的計算時延可表示為：delay_c=∑_jdelay；該請求的總時延為delay=delay_t+delay_c。通過將虛擬機部署到云計算中心或者邊緣設備來最小化請求的總時延。

3 解決方案

若請求r需要歷史數(shù)據(jù)作為輸入，則將請求r部署到云計算中心；否則，查找r中所有負責處理原始輸入數(shù)據(jù)的虛擬機并標記為集合S，為S查找一個最佳的邊緣設備，若找到，則把S部署到該邊緣設備；若未找到滿足要求的邊緣設備，則將請求r部署到云計算中心。對于r中剩余的虛擬機r-S，若找到的邊緣設備剩余資源足夠多，則把r中剩余未部署的虛擬機部署到該邊緣設備；否則，對r中剩余未部署的虛擬機按照輸入數(shù)據(jù)量的大小做降序排列，并把排序后的虛擬機記為S，將S中的虛擬機優(yōu)先部署到之前找到的邊緣設備，并將S中剩余未部署的虛擬機部署到云計算中心。具體算法如算法1。

4 結(jié)論

本文研究了在邊緣云環(huán)境下通過考慮輸入數(shù)據(jù)在網(wǎng)絡中的位置來最小化總延遲的虛擬機部署問題。對虛擬機部署問題進行形式化處理，根據(jù)輸入數(shù)據(jù)建立時延模型。通過分析輸入數(shù)據(jù)的位置，提出了一種數(shù)據(jù)驅(qū)動的虛擬機部署算法?；舅枷胧强紤]負責處理請求輸入數(shù)據(jù)的虛擬機，將請求放置在盡可能靠近輸入數(shù)據(jù)的位置。

參考文獻

[1]陳全，鄧倩妮，云計算及其關(guān)鍵技術(shù)[J].計算機應用，2009 （29）.

[2]王保云，物聯(lián)網(wǎng)技術(shù)研究綜述[J].電子測量與儀器學報，2009 （23）.

[3]W. Shi，J.Cao，Q.Zhang，Y.Li， andL. Xu， “Edge computing： Vision andchallenges，”IEEE Internet of ThingsJournal， vol.3， no.5， pp. 637-646，2 016.