邊緣環(huán)境下交互式視頻應(yīng)用的資源分配算法研究

蔡園園,甘 靖,陸谞君

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

0 引言

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

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

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

1 系統(tǒng)模型

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

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

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

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

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

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

2 資源分配算法

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

2.1 帶寬分配算法

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

2.2 服務(wù)放置算法

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

3 實(shí)驗(yàn)結(jié)果與分析

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

圖1 實(shí)驗(yàn)結(jié)果

4 結(jié)語

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