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

1 （武漢理工大學計算機與人工智能學院 武漢 430070）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 問題描述

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

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

2 系統(tǒng)模型

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

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

2.1 邊緣服務器選擇模型

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

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

2.2 直播用戶QoE模型

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

2.2.1 直播互動體驗

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

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

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

其中Tbv,mbv為主播bv到邊緣服務器mbv之間的直播視頻傳播延遲，Tmbv,m為邊緣服務器mbv到邊緣服務器m的直播視頻傳播延遲，Tm,v為 邊緣服務器m到用戶v之間的直播傳播延遲，G為邊緣服務器中轉碼對應產生的延遲.

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

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

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

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

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

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

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

2.2.2 直播視頻觀看體驗

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

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

視頻質量的抖動會對視頻觀看體驗產生影響.視頻碼率突然下降將會對用戶體驗產生相應的損失，而當碼率上升時就不會對用戶體驗造成損失.視頻質量抖動Ev表 示為

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

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

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

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

2.3 邊緣服務器資源約束

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

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

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

其中Cm表示邊緣服務器m可供直播轉碼的總計算資源，H為轉碼對應的計算資源開銷.

2.4 優(yōu)化目標

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

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

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

3 算法設計

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

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

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

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

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

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

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

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

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

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

證畢.

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

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

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

證畢.

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

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

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

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

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

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

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

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

算法1.LUA算法.

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

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

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

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

③ for 集合V中每個用戶vdo

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

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

⑥ 在[1,R]范圍內增加或降低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)了依次對各用戶進行分配.在分配的過程中，行④～?計算了各用戶當前狀況下分別連接各邊緣服務器能獲取到的最大QoEv,m，行?～?給出用戶的最優(yōu)決策結果，而行??實現(xiàn)了邊緣服務器剩余資源的更新.

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

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

4 實驗與結果分析

4.1 實驗設置

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

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

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

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

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

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

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

Table 4 Experimental Setting表4 實驗設置

4.2 性能分析

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

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

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

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

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

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

對于直播用戶碼率抖動指標，如圖10所示，LUA表現(xiàn)最優(yōu).盡管MHCP針對碼率進行優(yōu)化，在用戶人數(shù)較少時，碼率抖動情況表現(xiàn)較好，但隨著人數(shù)的增加，剩余服務器資源逐漸減少，受服務器資源的約束，部分用戶只能選擇低碼率視頻，導致下降的碼率增加，所以MHCP在人數(shù)增多的情況下性能表現(xiàn)較差.而LUA通過合理的碼率選擇，使得在服務器資源不足時，碼率抖動也相對其他算法有較優(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所示，對于用戶互動體驗質量，LUA有最優(yōu)的表現(xiàn).直播互動體驗不僅和直播延遲有關，還和用戶的需求有關.所以盡管在平均延遲的表現(xiàn)上LUA并不是最優(yōu)，但LUA在為用戶選擇不同延遲的傳輸路徑過程中，考慮到了用戶的互動需求.對互動需求高的用戶分配低延遲路徑，使得在互動體驗的表現(xiàn)上不弱于延遲更低的策略.但隨著人數(shù)增多，平均延遲上升，導致互動體驗均呈現(xiàn)下降趨勢，用戶數(shù)量增加到125時，DF的互動體驗表現(xiàn)更好，要比LUA高14%，因為DF平均用戶延遲相較于其他算法更低，但平均互動體驗質量表現(xiàn)上，LUA比DF算法高0.4%.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Table 5 Comparison of Experimental Results表5 實驗結果對比

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

5 總 結

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

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