劉 偉 張驍宇 杜 薇,2 彭若濤

1 （武漢理工大學(xué)計算機(jī)與人工智能學(xué)院 武漢 430070）

2 （交通物聯(lián)網(wǎng)湖北重點實驗室（武漢理工大學(xué)） 武漢 430070）

3 （嵌入式系統(tǒng)與服務(wù)計算教育部重點實驗室（同濟(jì)大學(xué)） 上海 201804）

4 （處理器芯片全國重點實驗室（中國科學(xué)院計算技術(shù)研究所） 北京 100190）（wliu@whut.edu.cn）

近幾年，虎牙直播、嗶哩嗶哩直播、斗魚TV等互動直播平臺倍受關(guān)注并且發(fā)展迅速.特別是在疫情的影響下，直播應(yīng)用的用戶數(shù)量得到了前所未有的增長.思科視覺網(wǎng)絡(luò)指數(shù)統(tǒng)計，2022年的直播視頻流量占互聯(lián)網(wǎng)視頻總流量的17%[1].不同于傳統(tǒng)的視頻流媒體，互動直播不僅為用戶提供視頻內(nèi)容，還允許用戶通過發(fā)送彈幕和贈送虛擬禮物的形式和主播進(jìn)行實時互動.隨著互動直播的快速發(fā)展，為廣大用戶提供高質(zhì)量的直播視頻體驗也變得越來越重要.

目前直播視頻主要采用了基于內(nèi)容分發(fā)網(wǎng)絡(luò)[2]的視頻分發(fā)方案或基于云數(shù)據(jù)中心[3]的視頻分發(fā)方案.隨著直播用戶數(shù)量的增加，在網(wǎng)絡(luò)高峰期需要對大量的直播視頻進(jìn)行處理和分發(fā)，這給服務(wù)器帶來了巨大的帶寬和計算壓力.現(xiàn)有研究表明，熱門的直播視頻在互聯(lián)網(wǎng)網(wǎng)關(guān)上容易產(chǎn)生很多流量瓶頸[4].另外，從主播到云端服務(wù)器再到用戶的整個直播視頻分發(fā)路徑過長，這給直播服務(wù)帶來了一定的延遲.在直播中，用戶需要和主播進(jìn)行實時互動，延遲過高會影響直播用戶的體驗.

為了解決目前直播中面臨的問題，文獻(xiàn)[5]中提出了一種基于邊緣計算的移動網(wǎng)絡(luò)直播視頻分發(fā)方案，并且很多優(yōu)秀的工作也對邊緣計算技術(shù)進(jìn)行了深入的研究.邊緣計算是一種新型計算模式，它通過將服務(wù)從云端下沉到網(wǎng)絡(luò)邊緣，確保更短的響應(yīng)時間和更高的可靠性[6].邊緣計算的應(yīng)用有效減小了系統(tǒng)延遲，緩解了云端網(wǎng)絡(luò)帶寬和計算功耗的壓力，并保護(hù)了用戶隱私和數(shù)據(jù)安全[7].目前已有相關(guān)學(xué)者在此領(lǐng)域取得了一定的成果.文獻(xiàn)[8]中提出了一種面向多邊緣協(xié)作的任務(wù)卸載和服務(wù)緩存聯(lián)合優(yōu)化機(jī)制，將聯(lián)合優(yōu)化問題耦合為2個子問題，分別設(shè)計了算法，降低了服務(wù)時延，同時實現(xiàn)了邊緣負(fù)載均衡.文獻(xiàn)[9]針對車輛邊緣計算下的任務(wù)卸載進(jìn)行了深入分析，并從算法復(fù)雜度、隱私安全以及移動性等方面對任務(wù)卸載目前面臨的挑戰(zhàn)進(jìn)行了總結(jié)歸納.文獻(xiàn)[10]結(jié)合邊緣計算技術(shù)對目標(biāo)追蹤算法的部署策略進(jìn)行了研究，降低了任務(wù)響應(yīng)和處理的時間.邊緣計算技術(shù)的應(yīng)用降低了服務(wù)的延遲，提升了任務(wù)的執(zhí)行效率.

在直播應(yīng)用領(lǐng)域中引入邊緣計算可以提升直播的服務(wù)體驗.文獻(xiàn)[11]提出了一種云邊緣直播分發(fā)架構(gòu)，該架構(gòu)顯著減少了云端的轉(zhuǎn)碼和帶寬負(fù)載.由于邊緣服務(wù)器更接近用戶，可以通過將用戶分配到附近的邊緣服務(wù)器來降低延遲，同時實現(xiàn)了靈活和細(xì)粒度的網(wǎng)絡(luò)管理.文獻(xiàn)[12]指出直播視頻的編解碼過程需要消耗大量的計算資源和時間.通過在邊緣云輔助異構(gòu)網(wǎng)絡(luò)中尋找一種高效、高質(zhì)量和低延遲的直播視頻編解碼方案，提高了直播的服務(wù)質(zhì)量.文獻(xiàn)[13]提出了一個基于邊緣的直播臨時緩存方案，通過上下文感知的方式在邊緣緩存最少數(shù)量的直播視頻片段，避免了視頻緩沖，并大幅度減少了初始啟動延遲和直播延遲，在全球互聯(lián)網(wǎng)上實現(xiàn)了無縫的4K直播.文獻(xiàn)[14]針對360°全景視頻直播中延遲高、數(shù)據(jù)處理量大等問題，提出了一種用于全景視頻的移動邊緣輔助實時流媒體系統(tǒng)，可以智能地將處理任務(wù)卸載到邊緣服務(wù)器中，實現(xiàn)了低延遲全景視頻直播.文獻(xiàn)[11-14]在把邊緣計算技術(shù)應(yīng)用到視頻直播領(lǐng)域的同時，充分發(fā)揮了邊緣計算的優(yōu)勢，改善了直播中延遲過高、服務(wù)器資源開銷大等問題，提升了直播的服務(wù)質(zhì)量，優(yōu)化了用戶體驗.

在邊緣計算的典型架構(gòu)中，邊緣服務(wù)器通常被部署在基站上[15].為了研究邊緣服務(wù)器在現(xiàn)實場景中的覆蓋情況，本文處理并分析了澳大利亞墨爾本地區(qū)基站數(shù)據(jù)集[16]，發(fā)現(xiàn)有91%的終端用戶所在位置可連接到的基站數(shù)量超過10個，即大多數(shù)用戶處于多個邊緣服務(wù)器的重疊覆蓋區(qū)域內(nèi).如果這些用戶是直播觀眾，由于各邊緣服務(wù)器可用資源和傳輸延遲的差異，用戶通過不同的邊緣服務(wù)器獲取視頻會對直播體驗產(chǎn)生不同的影響，邊緣計算環(huán)境中的互動直播面臨新的挑戰(zhàn).目前已有相關(guān)工作研究了多邊緣服務(wù)器場景中的用戶分配問題，文獻(xiàn)[16]在邊緣服務(wù)器密集重疊分布的場景中，從應(yīng)用程序供應(yīng)商角度出發(fā)，采用博弈論的方法，盡可能租用少的邊緣服務(wù)器為更多的用戶提供服務(wù).文獻(xiàn)[17]設(shè)計了一種支持移動感知和遷移的方法，用于實時分配用戶.在邊緣服務(wù)器容量約束下，最大化用戶的覆蓋率，最小化用戶的重分配次數(shù).但文獻(xiàn)[16-17]研究工作均是一種通用的應(yīng)用場景，忽略了邊緣服務(wù)器的選擇對用戶體驗的影響，并不適用于解決互動直播中的問題.綜上，將邊緣計算應(yīng)用到互動直播中，在多邊緣服務(wù)器場景下如何對直播用戶進(jìn)行分配來提升用戶體驗的問題仍有待解決.

為了研究互動直播中用戶的需求差異，本文分析了嗶哩嗶哩直播網(wǎng)站的用戶彈幕數(shù)據(jù)集.結(jié)果顯示不同用戶的互動行為差異明顯，有59%的用戶在單位時間內(nèi)只互動了1次，而有37%的用戶互動次數(shù)在2～10之間.與很少參與互動的用戶相比，經(jīng)?；拥闹鲃佑脩魧^大的延遲更敏感[11].所以在為直播用戶分配邊緣服務(wù)器資源時，對于經(jīng)?；拥挠脩粢紤]分配傳輸延遲更低的邊緣服務(wù)器；對于很少互動的用戶，要將用戶體驗優(yōu)化重點放在視頻質(zhì)量上，并分配更多的帶寬和計算資源.在構(gòu)建直播用戶體驗質(zhì)量（quality of experience, QoE）模型時，要考慮用戶的個性化需求.文獻(xiàn)[18]在研究低延遲多方互動直播的自適應(yīng)碼率控制的工作中，分別從直播視頻質(zhì)量、視頻質(zhì)量變化量、緩沖時間以及延遲4個方面表示用戶QoE.文獻(xiàn)[19]用直播視頻的幀率和分辨率來映射用戶QoE，并根據(jù)直播視頻類型來控制這2個因素的權(quán)重.文獻(xiàn)[18-19]研究工作主要關(guān)注直播視頻的觀看體驗，而忽略了直播的互動體驗.文獻(xiàn)[11]在互動直播的QoE模型中引入了一個互動參數(shù)，用來反映觀眾的互動強(qiáng)度，并從視頻碼率、延遲和啟動延遲3個方面表示用戶QoE.但對于多邊緣服務(wù)器場景下直播用戶體驗的優(yōu)化，還應(yīng)當(dāng)結(jié)合邊緣服務(wù)器的覆蓋范圍和用戶地理位置考慮服務(wù)器的選擇對用戶體驗造成的影響.綜上，互動直播中不同用戶的互動行為差異明顯，在構(gòu)建直播用戶QoE模型時要綜合考慮用戶的互動體驗和視頻質(zhì)量，根據(jù)用戶的個性化需求為用戶分配邊緣服務(wù)器和系統(tǒng)資源，優(yōu)化直播用戶體驗.

本文提出了一種邊緣計算中基于用戶體驗的互動直播用戶分配策略.在多邊緣服務(wù)器多用戶的場景下，考慮到邊緣服務(wù)器的資源有限以及用戶的個性化需求，通過為各個用戶在當(dāng)前時段內(nèi)分配合適的邊緣服務(wù)器并選擇合適的直播視頻碼率，最大化多邊緣服務(wù)器覆蓋范圍內(nèi)的所有用戶整體QoE.本文的主要貢獻(xiàn)包括3個方面：

1）通過對真實數(shù)據(jù)集的處理分析發(fā)現(xiàn).大多數(shù)用戶處于多個邊緣服務(wù)器重疊覆蓋區(qū)域中，且不同直播用戶的互動行為差異明顯.為了提升邊緣計算場景下的直播用戶體驗，需解決邊緣服務(wù)器重疊覆蓋區(qū)域內(nèi)的用戶分配問題.

2）在多邊緣服務(wù)器、多用戶場景中，為直播用戶分配不同的邊緣服務(wù)器對用戶體驗產(chǎn)生不同的影響.考慮到直播用戶的需求不同，提出一個適用于邊緣計算場景的直播用戶QoE模型，該模型綜合考慮了用戶互動體驗、直播視頻質(zhì)量、邊緣服務(wù)器切換等因素對QoE的影響.

3）證明了本文提出的用戶分配問題為NP-hard問題，并設(shè)計了一個直播用戶分配算法，高效地解決了根據(jù)用戶的個性化需求，為用戶分配邊緣服務(wù)器和系統(tǒng)資源提升了直播用戶QoE.通過基于真實數(shù)據(jù)集的仿真實驗驗證了算法的性能，實驗結(jié)果表明該算法在保證延遲和碼率均有較好表現(xiàn)的同時降低了服務(wù)器切換次數(shù)和視頻質(zhì)量抖動，使用戶QoE相較于對比算法高出了19%.

1 數(shù)據(jù)分析及問題描述

本節(jié)將首先介紹基站用戶地理位置數(shù)據(jù)集和直播用戶彈幕數(shù)據(jù)集的處理工作，并分析現(xiàn)實場景中基站對用戶的覆蓋情況，以及直播用戶互動行為的差異；然后介紹邊緣計算場景中的直播視頻分發(fā)架構(gòu)；最后對互動直播中的用戶分配問題進(jìn)行詳細(xì)描述.

1.1 數(shù)據(jù)處理和分析

本文分析了澳大利亞地區(qū)基站數(shù)據(jù)集[16].該數(shù)據(jù)集主要包含了墨爾本中央商務(wù)區(qū)的基站和用戶的經(jīng)緯度位置信息，以及各基站的型號、類別、狀態(tài)等信息.此數(shù)據(jù)集的規(guī)?？梢苑从橙粘９ぷ魃顖鼍爸杏脩艉突镜牡乩矸植记闆r，具有一定的普適性.根據(jù)現(xiàn)實場景中的中心城區(qū)基站的覆蓋范圍，將數(shù)據(jù)集中基站的覆蓋半徑設(shè)定為300 m.由已知基站和用戶的經(jīng)緯度可計算得到各用戶可連接到的基站數(shù)量，如圖1所示.可連接基站數(shù)量低于10的用戶占總用戶數(shù)量的8.8%，大部分用戶可連接的基站數(shù)集中在10～20，人數(shù)占總用戶數(shù)的74.4%，另外有16.8%的用戶被20個以上的基站同時覆蓋，甚至有部分用戶可連接的基站數(shù)超過30.如果將邊緣服務(wù)器部署在部分基站上，在基于邊緣計算的互動直播場景中，大多數(shù)直播用戶處于多個邊緣服務(wù)器的公共覆蓋范圍內(nèi)，由于邊緣服務(wù)器傳輸延遲和剩余資源的差異，使用戶連接不同的邊緣服務(wù)器的直播體驗不同，需要在多個邊緣服務(wù)器中進(jìn)行選擇.所以，在多邊緣服務(wù)器場景下，需要對用戶進(jìn)行合理分配，提升直播用戶體驗.

Fig.1 Distribution of the proportion of people corresponding to the number of connectable base stations圖1 可連接基站數(shù)對應(yīng)的人數(shù)占比分布

為了分析直播用戶的互動行為，通過編寫一個爬蟲程序獲取了嗶哩嗶哩直播網(wǎng)站數(shù)據(jù)集，并重點收集了17個熱門直播間內(nèi)用戶的彈幕數(shù)據(jù).數(shù)據(jù)集信息主要包括直播網(wǎng)站每小時的總直播間數(shù)量和總用戶數(shù)量，以及各熱門直播間內(nèi)每條彈幕的內(nèi)容、發(fā)送時間、發(fā)送用戶ID和當(dāng)前直播間的用戶數(shù)量.

首先計算24 h內(nèi)平均每小時的直播間數(shù)量和用戶人數(shù)的分布情況，如圖2所示.在早上6點左右，直播用戶數(shù)量達(dá)到低谷，累計上線的總用戶數(shù)量為435萬左右，累計創(chuàng)建直播間數(shù)量為1 982；而在晚上8點左右是觀看直播的高峰期，總用戶數(shù)量為6 883萬左右，直播間數(shù)量為18 178.在觀看直播高峰期，用戶和直播間數(shù)量的急劇增長給直播平臺的服務(wù)器帶來了巨大的帶寬和計算壓力，邊緣計算可以在網(wǎng)絡(luò)邊緣對直播視頻進(jìn)行轉(zhuǎn)碼和傳輸，為用戶提供低延遲的直播服務(wù)，緩解云端服務(wù)器的壓力.

Fig.2 The number of live streaming rooms and distribution of the number of users圖2 直播間數(shù)量和用戶數(shù)量分布

然后分析了熱門直播間內(nèi)彈幕的發(fā)送情況，統(tǒng)計各用戶發(fā)送的彈幕數(shù)量，結(jié)果如圖3所示，橫坐標(biāo)表示用戶單位時間發(fā)送彈幕數(shù)量，縱坐標(biāo)表示各彈幕數(shù)量對應(yīng)的人數(shù)相對于總?cè)藬?shù)的累計比例.經(jīng)統(tǒng)計發(fā)現(xiàn)，有59%的用戶平均每小時只互動了1次，并且96%的用戶平均每小時互動次數(shù)在10以內(nèi)，高度傾斜的曲線反映出不同用戶的互動行為差異明顯，其中一部分用戶只觀看直播視頻，很少參與互動，而另一部分用戶積極主動地參與互動.對于頻繁參與互動的用戶，更期望體驗低延遲直播服務(wù)，較高的延遲會使其無法及時接受到最新的直播內(nèi)容和互動信息，影響到直播體驗；對于很少參與互動的用戶，延遲對其直播體驗影響相對較小，直播視頻的質(zhì)量會更為重要.因此在優(yōu)化直播用戶體驗為用戶分配邊緣服務(wù)器資源時，要考慮用戶的個性化需求.

Fig.3 Distribution of cumulative proportion of the number of people corresponding to the number of barrage圖3 彈幕數(shù)量對應(yīng)的人數(shù)累計占比分布

最后，為了分析影響用戶互動行為的因素，統(tǒng)計了17個熱門直播間內(nèi)的彈幕數(shù)量.利用各直播間每小時內(nèi)的總彈幕數(shù)量除以用戶數(shù)量計算出直播間單位時間人均彈幕數(shù)，將結(jié)果按照從小到大排序，并對直播間進(jìn)行編號，結(jié)果如圖4所示.其中有4個直播間單位時間人均彈幕數(shù)低于0.01，而有7個直播間人均彈幕數(shù)高于0.02，其中人均彈幕數(shù)最高達(dá)到了0.13.并且不同直播間的用戶互動行為也存在著明顯差異，部分直播間內(nèi)用戶的平均互動積極性明顯高于其他直播間，因此影響用戶互動行為的因素不僅和用戶自身需求有關(guān)，還和用戶所在直播間有一定的關(guān)系.在分析用戶的互動需求時，需要考慮用戶所在直播間的影響.

Fig.4 Distribution of the number of barrages per capita in each live streaming room圖4 各直播間人均彈幕數(shù)分布

1.2 直播視頻分發(fā)架構(gòu)

將邊緣計算技術(shù)應(yīng)用到互動直播中可以緩解云端服務(wù)器的壓力，降低互動直播的延遲.基于邊緣計算的直播視頻分發(fā)架構(gòu)如圖5所示，其主要由主播端、基站、主播側(cè)的邊緣服務(wù)器、傳輸網(wǎng)絡(luò)、用戶側(cè)的邊緣服務(wù)器、用戶端6部分組成.考慮主播和用戶地理位置接近的情況，如同城直播、現(xiàn)場體育賽事直播等，可直接利用邊緣服務(wù)器提供直播服務(wù).首先，主播將視頻采集設(shè)備獲取的原始視頻上傳到其附近可連接到的邊緣服務(wù)器當(dāng)中；然后，主播側(cè)的邊緣服務(wù)器將根據(jù)直播視頻請求，通過邊緣服務(wù)器之間的網(wǎng)絡(luò)專線將直播視頻分發(fā)到對應(yīng)用戶附近的邊緣服務(wù)器中；最后，用戶側(cè)的邊緣服務(wù)器可以對直播視頻進(jìn)行實時轉(zhuǎn)碼處理，將直播視頻轉(zhuǎn)換為不同分辨率的版本，并根據(jù)網(wǎng)絡(luò)狀況和用戶需求將最合適的視頻碼率版本傳輸給直播用戶.

Fig.5 Live streaming distribution architecture based on edge computing圖5 基于邊緣計算的直播視頻分發(fā)架構(gòu)

1.3 問題描述

通過1.1節(jié)中的數(shù)據(jù)集分析可知，大多數(shù)直播用戶處于多個邊緣服務(wù)器重疊覆蓋區(qū)域中，并且不同直播用戶的個性化需求存在差異.如圖5中用戶A和用戶B同時被邊緣服務(wù)器1，2，3覆蓋，假設(shè)用戶A經(jīng)常參與直播互動，期望更低的直播延遲；用戶B更關(guān)注直播視頻的質(zhì)量，期望更高的碼率.為了使2個直播用戶的QoE之和更優(yōu)，可以將用戶A分配給總延遲更低的邊緣服務(wù)器2，并選擇下載分辨率為480P的直播視頻，將用戶B分配給剩余資源更多的邊緣服務(wù)器3，并選擇高分辨率1080P的直播視頻.考慮到下載直播視頻需要占用用戶側(cè)邊緣服務(wù)器的帶寬資源，轉(zhuǎn)碼需要消耗用戶側(cè)邊緣服務(wù)器的計算資源，在服務(wù)器資源有限的情況下，如何為多邊緣服務(wù)器覆蓋范圍內(nèi)的所有用戶分配合適的邊緣服務(wù)器并選擇合適的視頻碼率，使所有用戶整體QoE最大化是一個有待解決的問題.

在基于邊緣計算的互動直播應(yīng)用場景中，邊緣服務(wù)器的覆蓋和用戶的地理分布情況較為復(fù)雜，大多數(shù)用戶被多個邊緣服務(wù)器同時覆蓋，需要根據(jù)用戶體驗在多個服務(wù)器中進(jìn)行選擇，因此互動直播中的用戶分配問題具有挑戰(zhàn)性和現(xiàn)實意義.本文主要研究在多邊緣服務(wù)器多用戶場景下，考慮到邊緣服務(wù)器的帶寬和計算資源有限，根據(jù)直播用戶的個性化需求和當(dāng)前的狀態(tài)，為多邊緣服務(wù)器重疊覆蓋范圍內(nèi)的所有直播用戶分配合適的邊緣服務(wù)器并選擇合適的直播視頻碼率，使此范圍內(nèi)所有直播用戶當(dāng)前時段的整體QoE最優(yōu).

2 系統(tǒng)模型

系統(tǒng)中用戶側(cè)的邊緣服務(wù)器集合可用M={m1,m2,…,m|M|}表示.當(dāng)前時間段多邊緣服務(wù)器覆蓋范圍內(nèi)的直播用戶可用集合V={v1,v2,…,v|V|}表示.直播用戶v所觀看的主播用bv表示.假設(shè)主播bv連接的邊緣服務(wù)器為mbv，且所有主播上傳的原始直播視頻的比特率均為R，即最高碼率版本.用戶v當(dāng)前時段觀看直播的平均碼率用Rv表示，則Rv∈{r1,r2,…,rv}.用戶v所在位置附近可連接到的邊緣服務(wù)器集合為M(v)，可知M(v)?M.為了便于理解，表1展示了本文中主要符號的含義.

Table 1 Key Notations Meanings表1 主要符號含義

2.1 邊緣服務(wù)器選擇模型

對于當(dāng)前時間段多邊緣服務(wù)器覆蓋范圍內(nèi)的各直播用戶，需要通過連接到邊緣服務(wù)器來獲取直播視頻.用戶v和邊緣服務(wù)器m之間的連接關(guān)系用xv,m表示，當(dāng)用戶v和邊緣服務(wù)器m連接時，xv,m=1，此時邊緣服務(wù)器m應(yīng)滿足m∈M(v)，若xv,m=0，表示此時用戶v和邊緣服務(wù)器m不連接.xv,m存在約束：

在多邊緣服務(wù)器場景下，重疊區(qū)域內(nèi)的用戶雖然可以在多個邊緣服務(wù)器中進(jìn)行選擇，但在當(dāng)前時間段每個用戶最多只能通過基站連接到1個邊緣服務(wù)器，因此xv,m同時應(yīng)滿足關(guān)系：

2.2 直播用戶QoE模型

在互動直播中，用戶體驗主要分為2個方面：直播互動體驗和視頻觀看體驗.直播互動體驗和直播延遲有密切的關(guān)系，延遲越低，互動體驗越優(yōu).另外根據(jù)前面數(shù)據(jù)集分析的結(jié)論，不同用戶的個性化需求差異明顯，在優(yōu)化用戶互動體驗時，要考慮用戶的互動需求，所以互動體驗主要受到延遲和互動需求2個因素的影響.對于直播視頻觀看體驗，一方面和當(dāng)前直播視頻的比特率有關(guān)，視頻比特率越高，對應(yīng)的視頻分辨率越高，用戶體驗越優(yōu).同時直播視頻比特率的抖動會對用戶體驗產(chǎn)生負(fù)面影響.另一方面在邊緣計算中，邊緣服務(wù)器的切換會導(dǎo)致切換延遲.因為資源引導(dǎo)、加載配置和文件遷移會增加服務(wù)時間[20]，所以若用戶當(dāng)前時間段連接的邊緣服務(wù)器和前一時間段連接的邊緣服務(wù)器不同時，服務(wù)器切換產(chǎn)生的延遲會導(dǎo)致直播視頻緩沖停頓，影響用戶的觀看體驗.

2.2.1 直播互動體驗

互動體驗主要受延遲的影響，直播視頻在各網(wǎng)絡(luò)節(jié)點之間的傳播和在邊緣服務(wù)器中的轉(zhuǎn)碼是造成直播延遲的主要原因.直播視頻傳播延遲主要包括主播到主播側(cè)邊緣服務(wù)器的延遲、主播側(cè)邊緣服務(wù)器到用戶側(cè)邊緣服務(wù)器的延遲、用戶側(cè)邊緣服務(wù)器到用戶的延遲.根據(jù)文獻(xiàn)[8，21]中節(jié)點之間延遲的計算和預(yù)估方法，可依據(jù)香農(nóng)定理得到m與n2節(jié)點之間的傳輸速率rmn，表示為

其中Bmn表示節(jié)點m與n之間的信道帶寬，Pmn表示2節(jié)點間的平均信號功率，σ2表示平均噪聲功率，Pmn/σ2即表示信噪比.則邊緣服務(wù)器m與用戶n之間的傳輸延遲Tmn表 示為

其中，λm表示直播視頻數(shù)據(jù)大小.參考文獻(xiàn)[18]的工作，在本文中將各節(jié)點之間的傳輸延遲作為已知條件.轉(zhuǎn)碼延遲主要受到原視頻碼率和用戶觀看視頻碼率的影響，原視頻碼率和用戶觀看視頻碼率之差越大，需要處理的視頻數(shù)據(jù)量越多，則轉(zhuǎn)碼產(chǎn)生的延遲越多.用戶v連接邊緣服務(wù)器m時的直播視頻延遲Lv,m表示：

其中Tbv,mbv為主播bv到邊緣服務(wù)器mbv之間的直播視頻傳播延遲，Tmbv,m為邊緣服務(wù)器mbv到邊緣服務(wù)器m的直播視頻傳播延遲，Tm,v為 邊緣服務(wù)器m到用戶v之間的直播傳播延遲，G為邊緣服務(wù)器中轉(zhuǎn)碼對應(yīng)產(chǎn)生的延遲.

互動體驗還和互動需求有關(guān)，根據(jù)1.1節(jié)中數(shù)據(jù)集處理的結(jié)論，用戶的互動需求會受到直播間的影響，因此互動需求值Iv可 根據(jù)用戶v在當(dāng)前直播間內(nèi)的互動情況得到，并表示為

其中Fv為 用戶v在當(dāng)前直播間內(nèi)的歷史互動頻率，互動頻率為用戶發(fā)送彈幕數(shù)和相應(yīng)時間的比值，可從直播用戶的歷史記錄信息中得到，權(quán)值γ用于控制互動需求值的范圍.

在實時音視頻互動中，有研究指出1 s左右的延時會給用戶的互動交流帶來異步感，必須盡可能將視頻播放延遲限制在400 ms以內(nèi)才能給用戶帶來較好的交互體驗.當(dāng)延遲控制在400 ms以內(nèi)時，2個人的音視頻互動是實時的，不會有異步感存在[22].所以可以推斷在互動直播中存在一個延遲閾值β，當(dāng)直播延遲小于β時，主播和用戶可以實時互動，用戶的互動需求值越高，互動越頻繁，用戶越能體驗到互動的暢通感，互動體驗越優(yōu)；當(dāng)直播延遲大于β時，對用戶互動產(chǎn)生負(fù)面的影響，如果用戶互動需求值越大，越容易感受到異步感的存在，用戶互動體驗越差.同時從文獻(xiàn)[11]中得到啟發(fā)，延遲越低，互動體驗越優(yōu)，最終直播延遲和互動需求值映射到直播互動體驗Q(Iv,Lv,m)的函數(shù)式表示為

其中β為延遲閾值，Lv,m為用戶的直播延遲，Iv為用戶的互動需求值.

對于式（7），由于Iv的值非負(fù)，當(dāng)Iv的取值一定時，Lv,m的值越小，互動體驗值越大，并表示為：

所以其滿足延遲越低、互動體驗越優(yōu)的結(jié)論.當(dāng)Lv,m的取值一定時，存在關(guān)系：

如式（9）所示，當(dāng)Lv,m≤β時，Iv越大互動體驗值越大；如式（10）所示，當(dāng)Lv,m的值＞β時，Iv越大互動體驗值越小.所以式（7）同時也滿足當(dāng)直播延遲小于延遲閾值時，用戶的互動需求值越高，互動體驗越優(yōu)；當(dāng)直播延遲大于延遲閾值時，用戶互動需求值越大，用戶互動體驗越差的結(jié)論.綜上，互動體驗的式（7）符合實際要求.

2.2.2 直播視頻觀看體驗

視頻質(zhì)量是影響視頻觀看體驗的主要因素之一，而視頻質(zhì)量和視頻碼率有關(guān)，參考文獻(xiàn)[23]中定義的視頻質(zhì)量表達(dá)式，并對其進(jìn)行修改，用戶v的直播視頻質(zhì)量Uv函數(shù)表達(dá)式為

考慮到用戶的個性化需求，其中R*v為用戶v所期望的碼率，可根據(jù)用戶觀看直播歷史記錄中主動選擇的視頻分辨率等級得到.Rv為用戶v觀看直播的實際碼率，當(dāng)用戶觀看直播時的碼率不低于用戶所期望的碼率時，用戶視頻質(zhì)量達(dá)到最優(yōu).

視頻質(zhì)量的抖動會對視頻觀看體驗產(chǎn)生影響.視頻碼率突然下降將會對用戶體驗產(chǎn)生相應(yīng)的損失，而當(dāng)碼率上升時就不會對用戶體驗造成損失.視頻質(zhì)量抖動Ev表 示為

其中[x]+=max{0,x}，為前一個時間段用戶的平均碼率，k表示用戶的碼率每降低一個單位對用戶體驗造成的損失值.

邊緣服務(wù)器的切換也會對直播視頻觀看體驗造成負(fù)面影響.在為邊緣服務(wù)器重疊覆蓋區(qū)域內(nèi)的直播用戶作出當(dāng)前時間段邊緣服務(wù)器選擇決策時，需考慮用戶前一時間段的邊緣服務(wù)器連接狀態(tài).邊緣服務(wù)器的切換會產(chǎn)生一定的服務(wù)等待時間，造成直播的緩沖卡頓，降低用戶體驗質(zhì)量.邊緣服務(wù)器切換對用戶體驗的影響表示為：

綜上所述，當(dāng)用戶v選擇連接邊緣服務(wù)器m，并觀看碼率為Rv的直播視頻時，用戶的QoE記為QoEv,m，可以表示為4個因素的加權(quán)求和，即

用戶QoE主要和互動體驗質(zhì)量、視頻質(zhì)量、碼率抖動、邊緣服務(wù)器切換有關(guān)，其中a，b，c，d為權(quán)值，可根據(jù)實際情況進(jìn)行設(shè)定.

2.3 邊緣服務(wù)器資源約束

對于系統(tǒng)中用戶側(cè)的邊緣服務(wù)器，其帶寬和計算資源是有限的，只能為有限數(shù)量的直播用戶提供直播服務(wù).將碼率為Rv的直播視頻傳輸給用戶v時，需要分配給用戶與碼率相對應(yīng)的帶寬資源，用戶才可以正常觀看相應(yīng)等級的直播視頻.連接到同一個邊緣服務(wù)器的用戶碼率之和不超過邊緣服務(wù)器總網(wǎng)絡(luò)吞吐量的約束，則滿足約束條件：

其中Dm表示邊緣服務(wù)器m提供給直播用戶時獲取視頻的總帶寬資源.

當(dāng)對直播視頻進(jìn)行轉(zhuǎn)碼時，需要占用邊緣服務(wù)器一定數(shù)量的虛擬處理器，連接到同一邊緣服務(wù)器m的用戶轉(zhuǎn)碼開銷之和不可超過邊緣服務(wù)器m的總計算資源.轉(zhuǎn)碼消耗的計算資源主要和視頻的原始碼率R以及目標(biāo)碼率Rv有關(guān)，碼率跨度越大，消耗的資源越多.邊緣服務(wù)器m的計算資源約束表示為：

其中Cm表示邊緣服務(wù)器m可供直播轉(zhuǎn)碼的總計算資源，H為轉(zhuǎn)碼對應(yīng)的計算資源開銷.

2.4 優(yōu)化目標(biāo)

優(yōu)化直播用戶體驗可以為直播平臺吸引更多的用戶，提升直播平臺的收益和市場競爭力.直播系統(tǒng)的優(yōu)化方向之一是為那些有價值的觀眾提供差異化的視頻交付服務(wù).例如，系統(tǒng)可以安排更好的網(wǎng)絡(luò)路徑給有價值的觀眾，提升他們的用戶體驗.作為回報，這些觀眾會捐贈更多的虛擬禮物[24].所以本文在優(yōu)化直播用戶QoE時，考慮到了用戶捐贈禮物金額，優(yōu)先提升捐贈金額高的用戶QoE，可為直播平臺帶來更多的利益.為了衡量各用戶贈送禮物的金額大小，用Yv表示用戶v的贈禮金額影響因素：

其中pv為用戶v捐贈禮物的總金額，可根據(jù)用戶歷史信息得到，α為權(quán)值.為了提升多邊緣服務(wù)器覆蓋范圍內(nèi)直播用戶QoE，問題模型確定為：

目標(biāo)函數(shù)的約束條件主要包括各邊緣服務(wù)器可供直播視頻轉(zhuǎn)碼的總計算資源約束（見式（19））、各邊緣服務(wù)器供直播視頻傳輸?shù)目値捹Y源約束（見式（20））.式（21）表示各用戶當(dāng)前時段只能連接1個邊緣服務(wù)器.式（22）表示用戶v是否連接邊緣服務(wù)器m.贈禮金額影響因素Yv作為權(quán)值影響著各直播用戶QoE，對于Yv值越大的用戶，提升其用戶QoE使總QoE增長更多，滿足現(xiàn)實需求.最終目標(biāo)是確定每個直播用戶的邊緣服務(wù)器連接狀態(tài)xv,m以及視頻平均碼率Rv，使所有用戶加權(quán)QoE之和最大化.需要注意的是視頻碼率Rv的取值和視頻分辨率版本的選擇相關(guān)，直播視頻通常會有多個不同分辨率版本，其對應(yīng)的視頻碼率Rv的取值并不連續(xù)，因此本文提出的互動直播中用戶分配問題是一個離散變量優(yōu)化問題.

3 算法設(shè)計

為了解決第2節(jié)中的用戶分配問題，本文設(shè)計了一種基于直播用戶體驗的用戶分配策略.對于多邊緣服務(wù)器覆蓋范圍內(nèi)的各直播用戶，當(dāng)其連接到邊緣服務(wù)器觀看直播時，邊緣服務(wù)器可以獲取到用戶的位置信息以及用戶直播歷史數(shù)據(jù)信息.由于邊緣服務(wù)器之間可以通信，各邊緣服務(wù)器能統(tǒng)一處理用戶信息以及邊緣服務(wù)器狀態(tài)信息.通過用戶位置信息可以確定各用戶可連接的邊緣服務(wù)器集合.根據(jù)直播用戶歷史信息可計算獲得用戶的互動需求值、贈禮金額影響因素、前一時段平均碼率、前一時段服務(wù)器連接狀態(tài)等參數(shù)，結(jié)合各邊緣服務(wù)器網(wǎng)絡(luò)狀態(tài)和剩余資源等信息，通過執(zhí)行直播用戶分配算法，確定各用戶當(dāng)前時段應(yīng)該選擇的邊緣服務(wù)器和直播視頻碼率，并將決策結(jié)果通過各邊緣服務(wù)器傳輸給用戶實施.接下來本節(jié)將首先對原問題進(jìn)行深入分析，然后再設(shè)計直播用戶分配算法.

定理1.互動直播中的用戶分配問題為NP-hard問題.

證明.為了進(jìn)行證明，首先引入一個經(jīng)典的NP-hard問題：多維0-1背包問題.假設(shè)有n個物品，(y0,y1,…,yn-1)，yi∈{0,1}表示物品是否放入背包中.物品i對應(yīng)的價值為qi，為了使放入背包中物品價值之和最大，目標(biāo)函數(shù)可表示為

假設(shè)物品i的重量為wi， 體積為ei，背包最大能承載的重量為K，容積為N.要使裝入背包的物品重量不超過背包最大載重，且體積不超過背包的容積，則約束條件可表示為

現(xiàn)將原問題進(jìn)行簡化處理，假設(shè)只考慮1個邊緣服務(wù)器m，則問題變?yōu)樵跐M足邊緣服務(wù)器m資源約束條件下，如何對邊緣服務(wù)器m覆蓋范圍內(nèi)的用戶進(jìn)行分配，使連接到邊緣服務(wù)器m的直播用戶整體QoE最大化.邊緣服務(wù)器m覆蓋范圍內(nèi)的用戶集合為V，用xv表?示用戶和邊緣服務(wù)器i的連接關(guān)系：

參考式（18），則簡化后的問題目標(biāo)函數(shù)可表示為

假設(shè)可供用戶v選擇的視頻碼率版本唯一，碼率為Rv，則Yv·QoEv的值可以直接計算得到，用qv表示，則式（27）變?yōu)?/p>

通過觀察可發(fā)現(xiàn)，式（23）和式（28）的表示形式一致.假設(shè)邊緣服務(wù)器m的計算資源為Cm，可用帶寬資源為Dm，對于邊緣服務(wù)器網(wǎng)絡(luò)吞吐量約束以及計算資源約束，參考式（15）和式（16）可分別表示為

由于碼率Rv已確定，則可用ev表示(R-Rv)×H，式（23）可變?yōu)?/p>

通過觀察可發(fā)現(xiàn)簡化后問題的約束條件式（29）（31）與多維背包問題的約束條件式（24）（25）形式一致.綜上，將原問題經(jīng)過簡化處理可轉(zhuǎn)化為0-1背包問題，而背包問題為NP-hard問題，所以簡化之前的用戶分配問題也為NP-hard問題.

證畢.

定理2.互動直播用戶QoE是用戶碼率Rv∈{1,2,…,R}的遞增函數(shù).

證明.將直播用戶QoE函數(shù)式展開，只考慮包含碼率Rv，主要包括3個部分：

在第1部分互動體驗中，原始碼率R的取值一定，因此Rv值的變化會對視頻轉(zhuǎn)碼延遲產(chǎn)生影響，為了使用戶正常觀看相應(yīng)碼率版本的直播視頻，會提供與碼率相對應(yīng)的直播網(wǎng)絡(luò)帶寬，所以碼率Rv的變化不會對視頻傳輸延遲產(chǎn)生影響，因此Rv越大，使得轉(zhuǎn)碼產(chǎn)生的延遲越小，互動體驗越優(yōu)；在第2部分視頻質(zhì)量中，當(dāng)時，Rv的值越大，視頻質(zhì)量越優(yōu)，當(dāng)時，視頻質(zhì)量達(dá)到最優(yōu)情況；在第3部分視頻質(zhì)量的抖動影響中，當(dāng)時，Rv越大，視頻質(zhì)量抖動產(chǎn)生的負(fù)面影響越小，而當(dāng)時，視頻質(zhì)量抖動的負(fù)面影響為0.綜合分析可知，用戶QoE在可選碼率范圍內(nèi)是關(guān)于Rv的遞增函數(shù).

證畢.

然后再根據(jù)邊緣服務(wù)器剩余資源進(jìn)行調(diào)整.當(dāng)網(wǎng)絡(luò)帶寬資源不足時，選擇更低碼率版本；當(dāng)計算資源不足時，選擇更高碼率版本，使得Rv滿足邊緣服務(wù)器資源約束.

為了對問題進(jìn)行高效求解，本文設(shè)計了一種直播用戶分配算法（live streaming user allocation algorithm，LUA）.該算法采用了貪心的思想，具有多項式級的時間復(fù)雜度，能夠快速獲得決策結(jié)果，滿足現(xiàn)實場景的需求.該算法的主要流程如圖6所示.

Fig.6 Flow chart of LUA algorithm圖6 LUA算法流程圖

1）初始化各參數(shù)，確定Rv的初試值為和中較大的值，計算所有用戶贈禮金額影響因素值Yv，并對用戶集合中的用戶根據(jù)贈禮金額影響因素值進(jìn)行降序排序.

2）按照排序后的用戶集合中用戶的順序取出用戶v，依次遍歷用戶v可連接的邊緣服務(wù)器集合M(ν)中的各邊緣服務(wù)器.當(dāng)用戶v連接邊緣服務(wù)器m時，通過定理2對QoEv,m函數(shù)式分析可知，QoEv,m是關(guān)于Rv的遞增函數(shù)，則根據(jù)Dm和Cm約束在[1,R]]范圍內(nèi)確定合適的Rv并計算相應(yīng)的QoEv,m.

3）確定QoEv,m值最大的邊緣服務(wù)器m*，并將xv,m*=1，更新邊緣服務(wù)器m*的剩余資源Dm*和Cm*.

4） 按照排序后的用戶集合中用戶的順序選擇下一個用戶，轉(zhuǎn)跳至步驟2），直到確定所有用戶的xv,m和Rv的取值.

LUA具體算法如算法1所示.

算法1.LUA算法.

輸入：用戶集合V，邊緣服務(wù)器集合M，碼率集合{1,2,…,R}，當(dāng)前各邊緣服務(wù)器可用資源Dm和Cm，各節(jié)點之間的傳播延遲，用戶的互動需求值及贈禮金額影響因素值Iv和Yv，用戶前一時間段狀態(tài)；

輸出：各用戶的邊緣服務(wù)器連接狀態(tài)xv,m，各用戶直播視頻碼率Rv.

① 初始化各用戶參數(shù)xv,m=0,Rv=max()，計算Yv；

② 按照Yv的取值從大到小的順序，將用戶集合V中的用戶重新排序；

③ for 集合V中每個用戶vdo

④ forM(v)中每個邊緣服務(wù)器mdo

⑤ ifRv＞Dm或(RRv)×H＞Cmthen

⑥ 在[1,R]范圍內(nèi)增加或降低Rv；

⑦ ifRv≤Dm且(R-Rv)×H≤Cmthen

⑧Rv,m=Rv；

⑨ end if

⑩ if 不存在Rv滿足約束 then

?QoEv,m=0；

? end if

? elseRv,m=Rv；

? end if

? 計算QoEv,m；

? end for

?m=argmax[QoEv,m]；

?xv,m←1；

?Rv←Rv,m；

? 更新剩余可用帶寬資源Dm←DmRv；

? end for

? 返回xv.m，Rv.

算法1給出了直播用戶分配算法的具體流程.其中行①②完成了對用戶按優(yōu)先級排序，行③～?實現(xiàn)了依次對各用戶進(jìn)行分配.在分配的過程中，行④～?計算了各用戶當(dāng)前狀況下分別連接各邊緣服務(wù)器能獲取到的最大QoEv,m，行?～?給出用戶的最優(yōu)決策結(jié)果，而行??實現(xiàn)了邊緣服務(wù)器剩余資源的更新.

算法1基于貪心策略根據(jù)贈禮金額影響因素值對用戶進(jìn)行排序，按照順序依次選取集合V中的直播用戶，然后對于當(dāng)前選擇的用戶v依次遍歷其可連接到的邊緣服務(wù)器計算QoEv,m，此時循環(huán)執(zhí)行次數(shù)為|V|×|M(v)|，最壞情況為所有用戶均可訪問所有邊緣服務(wù)器，即|V|×|M|.在計算用戶QoEv,m時，需要確定用戶此時的碼率Rv,m， 若初始化的Rv滿足約束條件則不需要調(diào)整，否則需要遍歷碼率集合確定滿足約束的碼率R，則最壞情況需要遍歷所有碼率情況，循環(huán)執(zhí)行次數(shù)為|V|×|M|×R.最終將用戶QoEv,m最大時的情況作為決策結(jié)果，并更新邊緣服務(wù)器剩余資源.復(fù)雜性來自對用戶集合、各用戶可連接邊緣服務(wù)器集合以及碼率集合的遍歷，所以時間復(fù)雜度為O(|V|×|M|×R).

在現(xiàn)實場景中，一定地理范圍內(nèi)的直播用戶數(shù)量和邊緣服務(wù)器的數(shù)量是有限的，并且直播視頻可選擇的分辨率版本較少，對應(yīng)的碼率集合有限，所以該算法可以快速得出決策結(jié)果，有較高的執(zhí)行效率和較低的性能開銷，滿足直播場景的實時性需求.

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

4.1 實驗設(shè)置

本文使用真實數(shù)據(jù)集進(jìn)行仿真實驗，為了構(gòu)建邊緣服務(wù)器和直播用戶的覆蓋關(guān)系，本文采用了基站數(shù)據(jù)集[16]，該數(shù)據(jù)集主要包含墨爾本中心商務(wù)區(qū)的基站和用戶的位置信息.首先從數(shù)據(jù)集中隨機(jī)選取一定數(shù)量地理位置接近的基站部署邊緣服務(wù)器，確定基站的覆蓋范圍；然后根據(jù)用戶的位置信息，可得到邊緣服務(wù)器所覆蓋的用戶情況；最后隨機(jī)選取其中部分覆蓋重疊區(qū)域內(nèi)的用戶作為直播用戶，確定各直播用戶可連接的邊緣服務(wù)器集合.為了使用戶所選擇的碼率和用戶前一時間段觀看直播的碼率更接近實際情況，本文參考了Twitch直播數(shù)據(jù)集[25]，該數(shù)據(jù)集主要包括用戶信息、主播信息、直播頻道信息、直播分辨率信息等.對該數(shù)據(jù)集中直播分辨率信息進(jìn)行統(tǒng)計，根據(jù)數(shù)據(jù)集中用戶的直播視頻分辨率分布情況生成實驗中各直播用戶所期望的分辨率和前一時間段觀看直播的分辨率.各分辨率對應(yīng)的碼率范圍和平均碼率設(shè)定如表2所示.

Table 2 Video Bit Rate Parameters表2 視頻碼率參數(shù)

實驗中，將各邊緣服務(wù)器可供直播使用的總網(wǎng)絡(luò)吞吐量設(shè)定為40 Mbps，可供直播轉(zhuǎn)碼的總計算資源設(shè)為15 vCPUs，轉(zhuǎn)碼延遲參數(shù)G= 50 ms/Mbps，轉(zhuǎn)碼所需的邊緣服務(wù)器計算資源開銷參數(shù)H= 0.5 vCPU/Mbps.用戶QoE各指標(biāo)權(quán)值為a= 5，b= 1，c= 1，d=1.結(jié)合現(xiàn)實場景中的情況，將邊緣服務(wù)器的覆蓋半徑設(shè)置為300 m，將用戶到邊緣服務(wù)器之間的傳輸延遲設(shè)置為5～15 ms，邊緣服務(wù)器之間的傳輸延遲設(shè)置為100～300 ms，延遲閾值β= 300 ms.實驗的主要參數(shù)如表3所示.

Table 3 Main Parameters Setting表3 主要參數(shù)設(shè)置

本文將LUA算法與延遲優(yōu)先（delay first，DF）算法、改進(jìn)HAS頻道放置（modification of the HAS channel placement，MHCP）算法[19]、隨機(jī)分配算法Random進(jìn)行對比.DF主要策略是各用戶選擇可連接到的直播傳輸延遲最低的邊緣服務(wù)器，碼率根據(jù)連接的服務(wù)器剩余資源和用戶期望的碼率進(jìn)行調(diào)控，使用戶體驗最優(yōu)，這是一種比較直觀的主流策略.MHCP是對直播頻道放置（HAS channel placement，HCP）算法的修改，根據(jù)文獻(xiàn)[19]中服務(wù)器剩余空間RSm的值對服務(wù)器進(jìn)行排序，用戶優(yōu)先連接RSm值最高的邊緣服務(wù)器并選擇最高碼率版本視頻，使直播視頻質(zhì)量最優(yōu).RSm表示為

其中countm為連接到邊緣服務(wù)器m的人數(shù)，RCm為剩余計算資源的比例，RDm為剩余帶寬資源的比例.Random中，用戶在可連接到的邊緣服務(wù)器集合中隨機(jī)進(jìn)行選擇，同時隨機(jī)選擇分辨率版本作為當(dāng)前的決策結(jié)果.由于原問題為NP-hard，最優(yōu)解算法執(zhí)行效率過低，算法時間復(fù)雜度為指數(shù)級，對于實驗數(shù)據(jù)不能在有效的時間內(nèi)給出決策結(jié)果，同時也無法滿足現(xiàn)實場景的需求，所以不采用最優(yōu)解算法.

為了全面評估LUA算法的性能，本文選定了3個實驗參數(shù)：1）邊緣服務(wù)器數(shù)量；2）直播用戶數(shù)量；3）用戶互動需求值范圍.同時選取了延遲、碼率、互動體驗質(zhì)量、碼率抖動值、服務(wù)器切換次數(shù)、用戶QoE這6個性能評價指標(biāo).為了模擬不同的現(xiàn)實場景，并分析各實驗參數(shù)對算法性能的影響，進(jìn)行了3組實驗，實驗設(shè)置如表4所示.每組實驗首先利用基站數(shù)據(jù)集[16]隨機(jī)生成相應(yīng)數(shù)量的邊緣服務(wù)器和用戶，根據(jù)數(shù)據(jù)集中的位置信息和邊緣服務(wù)器覆蓋半徑確定各用戶可連接到的邊緣服務(wù)器集合，同時根據(jù)直播數(shù)據(jù)集[25]生成各直播用戶所期望的分辨率和前一時間段觀看直播的分辨率.然后根據(jù)表3初始化各參數(shù)，將所有用戶和邊緣服務(wù)器信息作為輸入依次執(zhí)行LUA，DF，MHCP，Random算法，分別輸出用戶的邊緣服務(wù)器和碼率選擇情況.最后根據(jù)各算法的輸出結(jié)果計算性能評價指標(biāo)，并進(jìn)行對比分析.為了盡可能減少隨機(jī)參數(shù)對實驗結(jié)果的影響，每組實驗進(jìn)行5次計算，取所有結(jié)果的平均值作為最終結(jié)果.

Table 4 Experimental Setting表4 實驗設(shè)置

4.2 性能分析

首先分析直播用戶數(shù)量對各評價指標(biāo)的影響.如圖7所示，MHCP在平均用戶碼率上表現(xiàn)最優(yōu)，平均高出LUA 21%.主要原因是MHCP中用戶優(yōu)先連接剩余資源最多的邊緣服務(wù)器，并選擇最高碼率版本視頻.但隨著用戶數(shù)量增多，在邊緣服務(wù)器可供分配資源不充足的情況下，MHCP中用戶平均碼率表現(xiàn)和LUA接近，均優(yōu)于其他算法.另外，雖然碼率越高用戶體驗越優(yōu)，但當(dāng)服務(wù)器資源有限的情況下，只選擇最高碼率會導(dǎo)致部分用戶可用資源不足，可能對整體用戶體驗產(chǎn)生負(fù)面影響.

Fig.7 Effect of the number of users on bit rate圖7 用戶數(shù)量對碼率的影響

如圖8所示，當(dāng)直播用戶數(shù)量為50時，邊緣服務(wù)器帶寬和計算資源充足，MHCP中大部分用戶均可以選擇最高碼率視頻，避免了轉(zhuǎn)碼產(chǎn)生的延遲，所以延遲表現(xiàn)最優(yōu).隨著人數(shù)增加，導(dǎo)致各用戶平均分配到的服務(wù)器帶寬資源減少，可選擇的碼率下降，轉(zhuǎn)碼產(chǎn)生一定的延遲，使得平均用戶延遲呈上升趨勢.對于DF，由于用戶優(yōu)先連接延遲最低的邊緣服務(wù)器，所以平均延遲整體表現(xiàn)最優(yōu).LUA在延遲表現(xiàn)上要高出DF 8%，平均延遲僅相差22 ms.

Fig.8 Effect of the number of users on delay圖8 用戶數(shù)量對延遲的影響

在平均用戶服務(wù)器切換次數(shù)的表現(xiàn)上，如圖9所示，LUA明顯優(yōu)于其他對比算法，其切換次數(shù)相較于表現(xiàn)第2的DF要低49%.主要原因是其他算法在以高碼率或低延遲為目標(biāo)選擇邊緣服務(wù)器時忽略了用戶前一時間段邊緣服務(wù)器的連接狀態(tài).邊緣服務(wù)器切換會對用戶體驗產(chǎn)生負(fù)面影響，LUA考慮到了此因素，較好地控制了服務(wù)器的切換.但隨著用戶人數(shù)增多，當(dāng)服務(wù)器資源不足時，用戶只能選擇其他邊緣服務(wù)器，這也使得LUA中服務(wù)器切換次數(shù)隨著人數(shù)增長而上升.

Fig.9 Effect of the number of users on server switching圖9 用戶數(shù)量對服務(wù)器切換的影響

對于直播用戶碼率抖動指標(biāo)，如圖10所示，LUA表現(xiàn)最優(yōu).盡管MHCP針對碼率進(jìn)行優(yōu)化，在用戶人數(shù)較少時，碼率抖動情況表現(xiàn)較好，但隨著人數(shù)的增加，剩余服務(wù)器資源逐漸減少，受服務(wù)器資源的約束，部分用戶只能選擇低碼率視頻，導(dǎo)致下降的碼率增加，所以MHCP在人數(shù)增多的情況下性能表現(xiàn)較差.而LUA通過合理的碼率選擇，使得在服務(wù)器資源不足時，碼率抖動也相對其他算法有較優(yōu)的表現(xiàn)，平均下降碼率整體表現(xiàn)上要低MHCP 61%，而Random和DF在碼率抖動的控制上性能表現(xiàn)較差.

Fig.10 Effect of the number of users on bit rate jitter圖10 用戶數(shù)量對碼率抖動的影響

如圖11所示，對于用戶互動體驗質(zhì)量，LUA有最優(yōu)的表現(xiàn).直播互動體驗不僅和直播延遲有關(guān)，還和用戶的需求有關(guān).所以盡管在平均延遲的表現(xiàn)上LUA并不是最優(yōu)，但LUA在為用戶選擇不同延遲的傳輸路徑過程中，考慮到了用戶的互動需求.對互動需求高的用戶分配低延遲路徑，使得在互動體驗的表現(xiàn)上不弱于延遲更低的策略.但隨著人數(shù)增多，平均延遲上升，導(dǎo)致互動體驗均呈現(xiàn)下降趨勢，用戶數(shù)量增加到125時，DF的互動體驗表現(xiàn)更好，要比LUA高14%，因為DF平均用戶延遲相較于其他算法更低，但平均互動體驗質(zhì)量表現(xiàn)上，LUA比DF算法高0.4%.

Fig.11 Effect of the number of users on interactive experience圖11 用戶數(shù)量對互動體驗的影響

如圖12所示，隨著人數(shù)的增加，受服務(wù)器資源的限制，用戶平均可分配到的資源降低，使得用戶QoE呈下降趨勢.在平均用戶QoE表現(xiàn)上，LUA最優(yōu)，高出第2名DF 19%.綜合前面的分析，盡管LUA在平均用戶延遲和碼率上表現(xiàn)不是最優(yōu)，但其在選擇碼率和邊緣服務(wù)器的過程中考慮到了用戶的需求，合理地為用戶分配服務(wù)器帶寬和計算資源，避免了資源的浪費(fèi).同時LUA也關(guān)注到了邊緣服務(wù)器切換和碼率下降對用戶QoE的負(fù)面影響，最終使其平均用戶QoE結(jié)果優(yōu)于其他算法.

Fig.12 Effect of the number of users on QoE圖12 用戶數(shù)量對用戶QoE的影響

接下來分析邊緣服務(wù)器數(shù)量對各實驗指標(biāo)的影響.如圖13和圖14所示，MHCP平均碼率表現(xiàn)最佳，DF平均延遲表現(xiàn)最佳.LUA平均碼率要低MHCP 21%，平均延遲高DF 10%.隨著邊緣服務(wù)器數(shù)量增加，系統(tǒng)總可用資源增加，用戶可分配到的資源充足，使得碼率呈遞增趨勢，轉(zhuǎn)碼產(chǎn)生的延遲降低，所以延遲呈下降趨勢.當(dāng)服務(wù)數(shù)量增加到10以上時，達(dá)到系統(tǒng)資源飽和狀態(tài)，平均用戶碼率和延遲均趨于穩(wěn)定.

Fig.13 Effect of the number of edge servers on bit rate圖13 邊緣服務(wù)器數(shù)量對碼率的影響

Fig.14 Effect of the number of edge servers on delay圖14 邊緣服務(wù)器數(shù)量對延遲的影響

如圖15和圖16所示，LUA在控制碼率抖動和邊緣服務(wù)器切換中均有最優(yōu)的表現(xiàn)，平均下降碼率要低表現(xiàn)第2的MHCP 58%，平均邊緣服務(wù)器切換次數(shù)要低DF 56%.主要原因是其他算法在連接最低延遲和最多剩余資源的邊緣服務(wù)器的過程中，不可避免地造成了邊緣服務(wù)器的切換.在LUA中，隨著邊緣服務(wù)器數(shù)量的增加，各服務(wù)器計算和帶寬資源充足，可供用戶選擇，有效避免邊緣服務(wù)器切換，所以平均切換次數(shù)下降.但當(dāng)服務(wù)器增加到一定數(shù)量時，選擇連接新的邊緣服務(wù)器使用戶體驗增加的幾率增加，最終使得平均用戶服務(wù)器切換次數(shù)呈上升趨勢.對于碼率抖動，當(dāng)邊緣服務(wù)器總資源不足時，用戶只能選擇較低碼率，所以碼率抖動較大，隨著邊緣服務(wù)器數(shù)量增多，碼率抖動情況減少，當(dāng)服務(wù)器資源充足時，LUA和MHCP均可避免碼率抖動.

Fig.15 Effect of the number of edge servers on server switching圖15 邊緣服務(wù)器數(shù)量對服務(wù)器切換的影響

Fig.16 Effect of the number of edge servers on bit rate jitter圖16 邊緣服務(wù)器數(shù)量對碼率抖動的影響

在圖17和圖18中，原因同之前分析，LUA在QoE的表現(xiàn)上最佳，DF僅次于LUA.隨著邊緣服務(wù)器數(shù)量的增加，除Random之外，其他算法在用戶體驗表現(xiàn)上均遞增.主要原因是隨著服務(wù)器數(shù)量增加、人數(shù)不變，人均可分配的資源增加，使得用戶可選擇的碼率版本更高，并且可選擇的低延遲服務(wù)器數(shù)量增加，最終用戶互動體驗和用戶QoE增加.但對于邊緣服務(wù)器數(shù)量增加到10和12的情況，平均QoE表現(xiàn)趨于穩(wěn)定，說明此時邊緣服務(wù)器的總資源相對于當(dāng)前用戶人數(shù)已經(jīng)過剩，增加邊緣服務(wù)器對用戶的QoE并無太大提升.經(jīng)計算，LUA的平均QoE相較于DF高出了19.3%.

Fig.17 Effect of the number of edge servers on interactive experience圖17 邊緣服務(wù)器數(shù)量對互動體驗的影響

Fig.18 Effect of the number of edge servers on user QoE圖18 邊緣服務(wù)器數(shù)量對用戶QoE的影響

然后通過改變各直播用戶互動需求值的取值范圍分析其對各算法結(jié)果的影響.由于用戶互動需求值主要對延遲和互動體驗造成影響，所以只對這2個性能評價指標(biāo)進(jìn)行分析.如圖19和圖20所示，在LUA平均用戶延遲的表現(xiàn)上，用戶的互動需求值的改變對其他3個對比算法均無明顯影響，因為對比算法在做決策的過程中并沒有考慮到各用戶的需求.而LUA考慮到了用戶的互動需求差異，為互動需求高的用戶分配低延遲的傳輸路徑，所以隨著用戶的互動需求值范圍的增加，用戶的平均延遲呈下降趨勢，并且在高互動需求用戶群體中的平均延遲表現(xiàn)上要優(yōu)于DF.當(dāng)互動需求值在（2，3）范圍內(nèi)時，LUA平均延遲比DF低6%.而對于平均用戶互動體驗，由于各算法中大部分用戶延遲低于延遲閾值（300 ms），所以隨著互動需求值上升，互動體驗質(zhì)量也上升.在整體表現(xiàn)上，LUA用戶互動體驗質(zhì)量優(yōu)于其他算法，高DF 16%.因為LUA為互動需求值更高的用戶分配延遲更低的邊緣服務(wù)器，有效提升了用戶的互動體驗質(zhì)量.

Fig.19 Effect of user interaction demand on delay圖19 用戶互動需求對延遲的影響

Fig.20 Effect of user interaction demand on interactive experience圖20 用戶互動需求對互動體驗的影響

接著分析QoE模型里互動體驗權(quán)重a的變化對LUA的平均用戶延遲和平均用戶互動體驗質(zhì)量的影響.如圖21所示，隨著a值的增加，提升用戶互動體驗?zāi)転閮?yōu)化用戶QoE帶來更多收益，所以平均用戶互動體驗質(zhì)量呈上升趨勢.而用戶的直播延遲越低，用戶的互動體驗越優(yōu)，所以平均用戶延遲呈下降趨勢.其中a= 11時比a= 1時，用戶的平均延遲下降了43.85 ms，平均互動體驗質(zhì)量上升了22%.因為直播用戶延遲是存在范圍限制的，受傳輸延遲影響不能無限制下降，所以當(dāng)a= 9時，用戶互動體驗和延遲已趨于穩(wěn)定.權(quán)重a對服務(wù)器切換和碼率的影響如圖22所示，隨著a值的增加，其他因素對用戶體驗的影響減小，為了使用戶有更好的互動體驗，會盡可能地為用戶選擇更低傳輸延遲的邊緣服務(wù)器，所以使得服務(wù)器切換次數(shù)呈上漲趨勢，其中a= 11時，平均用戶服務(wù)器切換次數(shù)達(dá)到了0.53，而碼率對互動體驗的影響較小，所以其表現(xiàn)較為穩(wěn)定.綜上，QoE模型中權(quán)重的設(shè)定會對LUA的結(jié)果產(chǎn)生一定的影響，在實際應(yīng)用中，可根據(jù)需求在一定范圍內(nèi)設(shè)定各因素的權(quán)重.

Fig.21 Effect of the values of weight a on delay and interactive experience圖21 權(quán)重a對延遲和互動體驗的影響

Fig.22 Effect of the values of weight a on the number of server switching and bit rate圖22 權(quán)重a對服務(wù)器切換次數(shù)和碼率的影響

最后，在一組小規(guī)模數(shù)據(jù)上運(yùn)行了最優(yōu)解算法，實驗設(shè)置有2個邊緣服務(wù)器、20名直播用戶、4種直播視頻分辨率版本.最優(yōu)解算法和LUA實驗結(jié)果如表5所示.在各性能評價指標(biāo)上，LUA均略低于最優(yōu)解算法.在平均用戶QoE表現(xiàn)上，LUA要比最優(yōu)解算法低14%.雖然LUA結(jié)果離最優(yōu)解有一定差距，但在現(xiàn)實場景中，直播的實時性要求和網(wǎng)絡(luò)狀態(tài)的實時變化需要算法快速作出決策.最優(yōu)解算法無法針對較大規(guī)模數(shù)據(jù)及時給出決策結(jié)果，不滿足實際需求.

Table 5 Comparison of Experimental Results表5 實驗結(jié)果對比

綜上，直播用戶分配算法在優(yōu)化延遲和碼率時考慮了用戶的個性化需求，保證了在平均用戶延遲和碼率上有較優(yōu)的表現(xiàn)，同時降低了邊緣服務(wù)器切換和碼率抖動的負(fù)面影響，使平均用戶QoE表現(xiàn)相較于其他對比算法更優(yōu).

5 總 結(jié)

在基于邊緣計算的互動直播場景中，為了提升多邊緣服務(wù)器重疊覆蓋區(qū)域中的直播用戶QoE，本文提出了一種面向互動直播的用戶分配策略，考慮了邊緣服務(wù)器資源約束和直播用戶的個性化需求，為各用戶分配合適的邊緣服務(wù)器并選擇合適的直播視頻碼率.在基于真實數(shù)據(jù)集的仿真實驗中，驗證了所設(shè)計的直播用戶分配算法LUA相較于DF，MHCP，Random算法能夠明顯提升直播用戶QoE.未來工作將考慮直播用戶的移動性，預(yù)測用戶的移動軌跡，在邊緣計算環(huán)境下對用戶的直播體驗進(jìn)行實時優(yōu)化.

作者貢獻(xiàn)聲明：劉偉提供了研究思路和論文創(chuàng)新點；張驍宇負(fù)責(zé)建模和策略的設(shè)計，并撰寫論文；杜薇提出指導(dǎo)意見并修改論文；彭若濤負(fù)責(zé)論文修改和最終版本的修訂.