邊緣環境下交互式視頻應用的資源分配算法研究

蔡園園,甘 靖,陸谞君

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

0 引言

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

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

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

1 系統模型

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

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

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

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

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

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

2 資源分配算法

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

2.1 帶寬分配算法

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

2.2 服務放置算法

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

3 實驗結果與分析

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

圖1 實驗結果

4 結語

針對邊緣環境下交互式視頻應用的資源分配問題,本文以最小化網絡時延和視頻幀率對用戶體驗的不良影響為目標,提出了一種在線內外兩層迭代算法,優化服務放置和帶寬分配決策。 實驗結果表明,相比其他同類算法,本文提出的算法能夠對邊緣計算環境中的資源進行更加高效的管理,提供更好的用戶體驗。