蔡園園,甘 靖,陸谞君

(江蘇電力信息技術(shù)有限公司,江蘇 南京 210024)

0 引言

移動邊緣計算(Mobile Edge Computing,MEC)[1-4]將數(shù)據(jù)中心的計算能力下放至網(wǎng)絡(luò)邊緣,構(gòu)成“云-邊-端”3 層結(jié)構(gòu)資源池,協(xié)同為用戶提供計算服務(wù)。 這種新的計算模式促進了眾多交互式視頻應(yīng)用的快速發(fā)展和廣泛普及,如增強現(xiàn)實、虛擬現(xiàn)實、視頻直播、云電腦等,期望以較低的系統(tǒng)代價保證這些應(yīng)用的服務(wù)質(zhì)量和用戶體驗。 具體而言,考慮到移動設(shè)備的計算能力弱,續(xù)航能力差,這類應(yīng)用常被劃分為服務(wù)實體和客戶實體兩部分:服務(wù)實體負責資源密集型任務(wù),如畫面渲染、負責邏輯處理等,部署在資源豐富的邊緣節(jié)點或云數(shù)據(jù)中心上;客戶實體負責輕量級任務(wù),主要為用戶指令輸入和畫面展示,部署在用戶的移動設(shè)備上。 在用戶使用這類應(yīng)用時,客戶實體接收并展示服務(wù)實體發(fā)來的畫面,并上傳輸入的用戶指令,而服務(wù)實體則接收客戶實體上傳的用戶指令,進行相應(yīng)的邏輯處理和畫面渲染后將畫面發(fā)送給客戶實體。

然而,在網(wǎng)絡(luò)邊緣提供交互式視頻服務(wù)并不是一件容易的事情。 相關(guān)研究工作表明,網(wǎng)絡(luò)時延和視頻幀率是影響用戶體驗的兩個重要因素,網(wǎng)絡(luò)時延越低,視頻幀率越高,用戶體驗越好。 因此,應(yīng)將用戶的服務(wù)實體部署在距離用戶最近的邊緣節(jié)點上,并為之分配充足的帶寬,從而使時延盡可能小,幀率盡可能大,用戶體驗盡可能好。 然而,邊緣節(jié)點的資源十分有限,要求必須合理地放置服務(wù)實體、分配帶寬資源。 此外,當用戶從某一區(qū)域移動到另一區(qū)域時,為保證用戶體驗,應(yīng)將服務(wù)實體遷移至新的邊緣節(jié)點,而這一遷移過程會帶來額外的系統(tǒng)開銷,需要權(quán)衡性能和代價。 最后,網(wǎng)絡(luò)環(huán)境是時變的,體現(xiàn)在邊緣節(jié)點的無線帶寬容量受物理環(huán)境影響,邊緣節(jié)點間傳播時延受網(wǎng)絡(luò)狀態(tài)影響。 因此,如何進行自適應(yīng)的服務(wù)放置和帶寬分配決策,高效利用資源,保證用戶體驗,是一個亟待解決的問題。

本文研究了邊緣環(huán)境下交互式視頻應(yīng)用的資源分配算法,以最小化網(wǎng)絡(luò)時延和視頻幀率對用戶體驗的不良影響為目標,在考慮了邊緣節(jié)點異構(gòu)性、用戶移動性、網(wǎng)絡(luò)環(huán)境時變性的基礎(chǔ)上,提出了一種自適應(yīng)調(diào)整服務(wù)放置和帶寬分配的在線內(nèi)外兩層算法:內(nèi)層算法更新帶寬分配決策;外層算法視內(nèi)層算法為子程序,更新服務(wù)放置決策。 本文進行了模擬實驗,實驗結(jié)果表明該算法能夠更高效地利用邊緣節(jié)點的資源,提供更好的用戶體驗。

1 系統(tǒng)模型

首先對邊緣環(huán)境下交互式視頻應(yīng)用系統(tǒng)進行建模。 考慮一個由用戶集合k、邊緣節(jié)點集合ε和一個云數(shù)據(jù)中心組成的系統(tǒng):邊緣節(jié)點之間通過回程網(wǎng)絡(luò)連接,并可通過廣域網(wǎng)連接云數(shù)據(jù)中心;所有用戶分布在邊緣節(jié)點的服務(wù)范圍內(nèi),且任一時間,一個用戶只在一個邊緣節(jié)點的服務(wù)范圍內(nèi),并可通過該節(jié)點接入網(wǎng)絡(luò);系統(tǒng)向用戶提供的交互式視頻應(yīng)用集合為A。 為了刻畫用戶的移動性和網(wǎng)絡(luò)環(huán)境的時變性,將時間離散化為時間片集合P,并在每一時間片初,更新服務(wù)放置決策和帶寬分配決策。

用表示時間片p時用戶k的服務(wù)實體是否放置在邊緣節(jié)點e上,用表示時間片p時分配給用戶k的帶寬資源,則在任意時間片p,用戶k所感知的網(wǎng)絡(luò)時延和視頻幀率分別如下:

其中,表示時間片p時用戶k的本地邊緣節(jié)點和邊緣節(jié)點e之間的傳播時延,a表示視頻畫面壓縮比,rak表示用戶k所使用的交互式視頻應(yīng)用ak的畫面分辨率。 對于任一交互式視頻應(yīng)用a,用Da(d) 表示用戶感知時延為d對用戶體驗的不良影響,用Fa(f) 表示視頻幀率為f對用戶體驗的不良影響。 于是,最小化網(wǎng)絡(luò)時延和視頻幀率對用戶體驗的不良影響,即:

考慮到服務(wù)實體的運行消耗計算資源,客戶實體與服務(wù)實體之間的交互通信消耗帶寬資源,而邊緣節(jié)點的資源是有限的,因此需要引入如下約束:

其中,wak用戶k所使用的交互式視頻應(yīng)用ak的計算資源需求量,we表示邊緣節(jié)點e的計算資源容量,表示時間片p時邊緣節(jié)點e的本地用戶集合,而表示時間片p時邊緣節(jié)點e的帶寬資源容量。 于是,公式(4)表示計算資源約束,公式(5)表示帶寬資源約束。

此外,當用戶從一個區(qū)域移動到另一個區(qū)域,可以遷移用戶的服務(wù)實體以跟隨用戶。 用?a(e,e′,p) 表示在時間片p時將應(yīng)用a的服務(wù)實體從邊緣節(jié)點e遷移到e′的代價,用Cavg表示長期的遷移代價預算,則服務(wù)遷移約束為:

2 資源分配算法

考慮到服務(wù)放置和帶寬分配決策分別屬于整數(shù)域和實數(shù)域,本文將上述問題劃分為服務(wù)放置和帶寬分配兩個子問題,并基于此提出了一個在線內(nèi)外兩層算法:內(nèi)層算法為帶寬分配算法,在當前時間片給定服務(wù)放置決策的情況下,計算最優(yōu)帶寬分配決策;外層算法為服務(wù)放置算法,計算當前時間片的服務(wù)放置決策,計算過程中會調(diào)用內(nèi)層算法。

2.1 帶寬分配算法

結(jié)合各交互式視頻應(yīng)用的用戶體驗模型(即Da(d) 和Fa(f)) 分析,在任一時間片初,給定服務(wù)放置決策所產(chǎn)生的帶寬分配問題為凸優(yōu)化問題。 特別地,當所有Da(d)和Fa(f)均為線性函數(shù)時,帶寬分配問題為線性規(guī)劃問題。 而在一般場景下,Da(d) 和Fa(f) 的函數(shù)形式較為復雜,直接使用KKT 條件難以求解,故本文基于凸分析,提出了一個迭代算法求解帶寬分配問題,亦稱為內(nèi)層算法。 內(nèi)層算法基于當前的系統(tǒng)狀態(tài)信息,以上一時間片的帶寬分配決策為初始決策,并為每一個用戶計算一個關(guān)于帶寬的特定函數(shù)的導數(shù)。 在每次迭代過程中,導數(shù)最大的用戶將取出一些帶寬資源分配給導數(shù)最小的用戶,并在這一新的帶寬分配決策下更新所有導數(shù)。 當最大導數(shù)和最小導數(shù)之差小于某一閾值時,算法輸出此時的帶寬分配決策,即為當前時刻的最優(yōu)帶寬分配決策。

2.2 服務(wù)放置算法

服務(wù)遷移約束是一個長期約束,使得不同時間片的服務(wù)放置決策是時間耦合的,如時間片在前的服務(wù)放置決策會影響時間片在后的服務(wù)放置決策。 李雅普諾夫優(yōu)化是一種專門解決長期優(yōu)化問題的理論框架,可以從理論上保證長期約束不會被打破,同時保證算法在優(yōu)化目標上的性能。 具體做法是為服務(wù)遷移約束構(gòu)造一個虛擬隊列,隊列長度表示該約束被破壞的程度;每一時間片初,基于當前的系統(tǒng)狀態(tài)信息和隊列長度,以此時的服務(wù)放置為決策變量,以同時最小化不良影響和穩(wěn)定隊列為優(yōu)化目標,構(gòu)造服務(wù)放置子問題。經(jīng)證明,該服務(wù)放置子問題是一個NP-hard 問題,在P≠NP的情況下,不可能在多項式時間內(nèi)求得其最優(yōu)解,故而尋求近似解。 馬爾可夫近似算法是一種解決組合優(yōu)化問題的常用算法,依據(jù)馬爾科夫鏈理論,可以從數(shù)學期望上保證算法性能。 故本文基于馬爾可夫近似算法設(shè)計了外層算法,求服務(wù)放置子問題的近似解。

3 實驗結(jié)果與分析

本文研究了邊緣環(huán)境下交互式視頻應(yīng)用的資源分配算法,以最小化網(wǎng)絡(luò)時延和視頻幀率對用戶體驗的不良影響為目標,在考慮了邊緣節(jié)點異構(gòu)性、用戶移動性、網(wǎng)絡(luò)環(huán)境時變性的基礎(chǔ)上,提出了一種優(yōu)化服務(wù)放置和帶寬分配的在線內(nèi)外兩層迭代算法。 為了驗證該算法的可行性和性能,本文進行了模擬實驗,實驗結(jié)果如圖1 所示。 結(jié)果表明,本文所提算法能夠更加合理地進行服務(wù)放置和帶寬分配決策,更加有效的利用邊緣節(jié)點的有限資源,提供更好的用戶體驗。

圖1 實驗結(jié)果

4 結(jié)語

針對邊緣環(huán)境下交互式視頻應(yīng)用的資源分配問題,本文以最小化網(wǎng)絡(luò)時延和視頻幀率對用戶體驗的不良影響為目標,提出了一種在線內(nèi)外兩層迭代算法,優(yōu)化服務(wù)放置和帶寬分配決策。 實驗結(jié)果表明,相比其他同類算法,本文提出的算法能夠?qū)吘売嬎悱h(huán)境中的資源進行更加高效的管理,提供更好的用戶體驗。