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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本節(jié)將首先介紹基站用戶地理位置數(shù)據(jù)集和直播用戶彈幕數(shù)據(jù)集的處理工作，并分析現(xiàn)實(shí)場景中基站對用戶的覆蓋情況，以及直播用戶互動(dòng)行為的差異；然后介紹邊緣計(jì)算場景中的直播視頻分發(fā)架構(gòu)；最后對互動(dòng)直播中的用戶分配問題進(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)實(shí)場景中的中心城區(qū)基站的覆蓋范圍，將數(shù)據(jù)集中基站的覆蓋半徑設(shè)定為300 m.由已知基站和用戶的經(jīng)緯度可計(jì)算得到各用戶可連接到的基站數(shù)量，如圖1所示.可連接基站數(shù)量低于10的用戶占總用戶數(shù)量的8.8%，大部分用戶可連接的基站數(shù)集中在10～20，人數(shù)占總用戶數(shù)的74.4%，另外有16.8%的用戶被20個(gè)以上的基站同時(shí)覆蓋，甚至有部分用戶可連接的基站數(shù)超過30.如果將邊緣服務(wù)器部署在部分基站上，在基于邊緣計(jì)算的互動(dòng)直播場景中，大多數(shù)直播用戶處于多個(gè)邊緣服務(wù)器的公共覆蓋范圍內(nèi)，由于邊緣服務(wù)器傳輸延遲和剩余資源的差異，使用戶連接不同的邊緣服務(wù)器的直播體驗(yàn)不同，需要在多個(gè)邊緣服務(wù)器中進(jìn)行選擇.所以，在多邊緣服務(wù)器場景下，需要對用戶進(jìn)行合理分配，提升直播用戶體驗(yàn).

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

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

首先計(jì)算24 h內(nèi)平均每小時(shí)的直播間數(shù)量和用戶人數(shù)的分布情況，如圖2所示.在早上6點(diǎn)左右，直播用戶數(shù)量達(dá)到低谷，累計(jì)上線的總用戶數(shù)量為435萬左右，累計(jì)創(chuàng)建直播間數(shù)量為1 982；而在晚上8點(diǎn)左右是觀看直播的高峰期，總用戶數(shù)量為6 883萬左右，直播間數(shù)量為18 178.在觀看直播高峰期，用戶和直播間數(shù)量的急劇增長給直播平臺的服務(wù)器帶來了巨大的帶寬和計(jì)算壓力，邊緣計(jì)算可以在網(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)計(jì)各用戶發(fā)送的彈幕數(shù)量，結(jié)果如圖3所示，橫坐標(biāo)表示用戶單位時(shí)間發(fā)送彈幕數(shù)量，縱坐標(biāo)表示各彈幕數(shù)量對應(yīng)的人數(shù)相對于總?cè)藬?shù)的累計(jì)比例.經(jīng)統(tǒng)計(jì)發(fā)現(xiàn)，有59%的用戶平均每小時(shí)只互動(dòng)了1次，并且96%的用戶平均每小時(shí)互動(dòng)次數(shù)在10以內(nèi)，高度傾斜的曲線反映出不同用戶的互動(dòng)行為差異明顯，其中一部分用戶只觀看直播視頻，很少參與互動(dòng)，而另一部分用戶積極主動(dòng)地參與互動(dòng).對于頻繁參與互動(dòng)的用戶，更期望體驗(yàn)低延遲直播服務(wù)，較高的延遲會使其無法及時(shí)接受到最新的直播內(nèi)容和互動(dòng)信息，影響到直播體驗(yàn)；對于很少參與互動(dòng)的用戶，延遲對其直播體驗(yàn)影響相對較小，直播視頻的質(zhì)量會更為重要.因此在優(yōu)化直播用戶體驗(yàn)為用戶分配邊緣服務(wù)器資源時(shí)，要考慮用戶的個(gè)性化需求.

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

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

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

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

將邊緣計(jì)算技術(shù)應(yīng)用到互動(dòng)直播中可以緩解云端服務(wù)器的壓力，降低互動(dòng)直播的延遲.基于邊緣計(jì)算的直播視頻分發(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)行實(shí)時(shí)轉(zhuǎn)碼處理，將直播視頻轉(zhuǎn)換為不同分辨率的版本，并根據(jù)網(wǎng)絡(luò)狀況和用戶需求將最合適的視頻碼率版本傳輸給直播用戶.

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

1.3 問題描述

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

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

2 系統(tǒng)模型

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

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

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

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

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

2.2 直播用戶QoE模型

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

2.2.1 直播互動(dòng)體驗(yàn)

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

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

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

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

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

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

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

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

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

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

2.2.2 直播視頻觀看體驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算法設(shè)計(jì)

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

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

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

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

現(xiàn)將原問題進(jìn)行簡化處理，假設(shè)只考慮1個(gè)邊緣服務(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的值可以直接計(jì)算得到，用qv表示，則式（27）變?yōu)?/p>

通過觀察可發(fā)現(xiàn)，式（23）和式（28）的表示形式一致.假設(shè)邊緣服務(wù)器m的計(jì)算資源為Cm，可用帶寬資源為Dm，對于邊緣服務(wù)器網(wǎng)絡(luò)吞吐量約束以及計(jì)算資源約束，參考式（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.互動(dòng)直播用戶QoE是用戶碼率Rv∈{1,2,…,R}的遞增函數(shù).

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

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

證畢.

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

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

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

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

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

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

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

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

算法1.LUA算法.

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

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

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

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

③ for 集合V中每個(gè)用戶vdo

④ forM(v)中每個(gè)邊緣服務(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

? 計(jì)算QoEv,m；

? end for

?m=argmax[QoEv,m]；

?xv,m←1；

?Rv←Rv,m；

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

? end for

? 返回xv.m，Rv.

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

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

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

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

4.1 實(shí)驗(yàn)設(shè)置

本文使用真實(shí)數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yà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ù)器集合.為了使用戶所選擇的碼率和用戶前一時(shí)間段觀看直播的碼率更接近實(shí)際情況，本文參考了Twitch直播數(shù)據(jù)集[25]，該數(shù)據(jù)集主要包括用戶信息、主播信息、直播頻道信息、直播分辨率信息等.對該數(shù)據(jù)集中直播分辨率信息進(jìn)行統(tǒng)計(jì)，根據(jù)數(shù)據(jù)集中用戶的直播視頻分辨率分布情況生成實(shí)驗(yàn)中各直播用戶所期望的分辨率和前一時(shí)間段觀看直播的分辨率.各分辨率對應(yīng)的碼率范圍和平均碼率設(shè)定如表2所示.

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

實(shí)驗(yàn)中，將各邊緣服務(wù)器可供直播使用的總網(wǎng)絡(luò)吞吐量設(shè)定為40 Mbps，可供直播轉(zhuǎn)碼的總計(jì)算資源設(shè)為15 vCPUs，轉(zhuǎn)碼延遲參數(shù)G= 50 ms/Mbps，轉(zhuǎn)碼所需的邊緣服務(wù)器計(jì)算資源開銷參數(shù)H= 0.5 vCPU/Mbps.用戶QoE各指標(biāo)權(quán)值為a= 5，b= 1，c= 1，d=1.結(jié)合現(xiàn)實(shí)場景中的情況，將邊緣服務(wù)器的覆蓋半徑設(shè)置為300 m，將用戶到邊緣服務(wù)器之間的傳輸延遲設(shè)置為5～15 ms，邊緣服務(wù)器之間的傳輸延遲設(shè)置為100～300 ms，延遲閾值β= 300 ms.實(shí)驗(yàn)的主要參數(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àn)最優(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為剩余計(jì)算資源的比例，RDm為剩余帶寬資源的比例.Random中，用戶在可連接到的邊緣服務(wù)器集合中隨機(jī)進(jìn)行選擇，同時(shí)隨機(jī)選擇分辨率版本作為當(dāng)前的決策結(jié)果.由于原問題為NP-hard，最優(yōu)解算法執(zhí)行效率過低，算法時(shí)間復(fù)雜度為指數(shù)級，對于實(shí)驗(yàn)數(shù)據(jù)不能在有效的時(shí)間內(nèi)給出決策結(jié)果，同時(shí)也無法滿足現(xiàn)實(shí)場景的需求，所以不采用最優(yōu)解算法.

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

Table 4 Experimental Setting表4 實(shí)驗(yàn)設(shè)置

4.2 性能分析

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

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

如圖8所示，當(dāng)直播用戶數(shù)量為50時(shí)，邊緣服務(wù)器帶寬和計(jì)算資源充足，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ù)器時(shí)忽略了用戶前一時(shí)間段邊緣服務(wù)器的連接狀態(tài).邊緣服務(wù)器切換會對用戶體驗(yàn)產(chǎn)生負(fù)面影響，LUA考慮到了此因素，較好地控制了服務(wù)器的切換.但隨著用戶人數(shù)增多，當(dāng)服務(wù)器資源不足時(shí)，用戶只能選擇其他邊緣服務(wù)器，這也使得LUA中服務(wù)器切換次數(shù)隨著人數(shù)增長而上升.

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

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

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

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

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

如圖12所示，隨著人數(shù)的增加，受服務(wù)器資源的限制，用戶平均可分配到的資源降低，使得用戶QoE呈下降趨勢.在平均用戶QoE表現(xiàn)上，LUA最優(yōu)，高出第2名DF 19%.綜合前面的分析，盡管LUA在平均用戶延遲和碼率上表現(xiàn)不是最優(yōu)，但其在選擇碼率和邊緣服務(wù)器的過程中考慮到了用戶的需求，合理地為用戶分配服務(wù)器帶寬和計(jì)算資源，避免了資源的浪費(fèi).同時(shí)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ù)量對各實(shí)驗(yàn)指標(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以上時(shí)，達(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在控制碼率抖動(dòng)和邊緣服務(wù)器切換中均有最優(yōu)的表現(xiàn)，平均下降碼率要低表現(xiàn)第2的MHCP 58%，平均邊緣服務(wù)器切換次數(shù)要低DF 56%.主要原因是其他算法在連接最低延遲和最多剩余資源的邊緣服務(wù)器的過程中，不可避免地造成了邊緣服務(wù)器的切換.在LUA中，隨著邊緣服務(wù)器數(shù)量的增加，各服務(wù)器計(jì)算和帶寬資源充足，可供用戶選擇，有效避免邊緣服務(wù)器切換，所以平均切換次數(shù)下降.但當(dāng)服務(wù)器增加到一定數(shù)量時(shí)，選擇連接新的邊緣服務(wù)器使用戶體驗(yàn)增加的幾率增加，最終使得平均用戶服務(wù)器切換次數(shù)呈上升趨勢.對于碼率抖動(dòng)，當(dāng)邊緣服務(wù)器總資源不足時(shí)，用戶只能選擇較低碼率，所以碼率抖動(dòng)較大，隨著邊緣服務(wù)器數(shù)量增多，碼率抖動(dòng)情況減少，當(dāng)服務(wù)器資源充足時(shí)，LUA和MHCP均可避免碼率抖動(dòng).

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ù)量對碼率抖動(dòng)的影響

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

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

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

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

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

Fig.20 Effect of user interaction demand on interactive experience圖20 用戶互動(dòng)需求對互動(dòng)體驗(yàn)的影響

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

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

Table 5 Comparison of Experimental Results表5 實(shí)驗(yàn)結(jié)果對比

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

5 總 結(jié)

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

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