边缘计算中面向互动直播的用户分配策略

刘 伟 张骁宇 杜 薇,2 彭若涛

1 （武汉理工大学计算机与人工智能学院 武汉 430070）

2 （交通物联网湖北重点实验室（武汉理工大学） 武汉 430070）

3 （嵌入式系统与服务计算教育部重点实验室（同济大学） 上海 201804）

4 （处理器芯片全国重点实验室（中国科学院计算技术研究所） 北京 100190）（wliu@whut.edu.cn）

近几年，虎牙直播、哔哩哔哩直播、斗鱼TV等互动直播平台倍受关注并且发展迅速.特别是在疫情的影响下，直播应用的用户数量得到了前所未有的增长.思科视觉网络指数统计，2022年的直播视频流量占互联网视频总流量的17%[1].不同于传统的视频流媒体，互动直播不仅为用户提供视频内容，还允许用户通过发送弹幕和赠送虚拟礼物的形式和主播进行实时互动.随着互动直播的快速发展，为广大用户提供高质量的直播视频体验也变得越来越重要.

目前直播视频主要采用了基于内容分发网络[2]的视频分发方案或基于云数据中心[3]的视频分发方案.随着直播用户数量的增加，在网络高峰期需要对大量的直播视频进行处理和分发，这给服务器带来了巨大的带宽和计算压力.现有研究表明，热门的直播视频在互联网网关上容易产生很多流量瓶颈[4].另外，从主播到云端服务器再到用户的整个直播视频分发路径过长，这给直播服务带来了一定的延迟.在直播中，用户需要和主播进行实时互动，延迟过高会影响直播用户的体验.

为了解决目前直播中面临的问题，文献[5]中提出了一种基于边缘计算的移动网络直播视频分发方案，并且很多优秀的工作也对边缘计算技术进行了深入的研究.边缘计算是一种新型计算模式，它通过将服务从云端下沉到网络边缘，确保更短的响应时间和更高的可靠性[6].边缘计算的应用有效减小了系统延迟，缓解了云端网络带宽和计算功耗的压力，并保护了用户隐私和数据安全[7].目前已有相关学者在此领域取得了一定的成果.文献[8]中提出了一种面向多边缘协作的任务卸载和服务缓存联合优化机制，将联合优化问题耦合为2个子问题，分别设计了算法，降低了服务时延，同时实现了边缘负载均衡.文献[9]针对车辆边缘计算下的任务卸载进行了深入分析，并从算法复杂度、隐私安全以及移动性等方面对任务卸载目前面临的挑战进行了总结归纳.文献[10]结合边缘计算技术对目标追踪算法的部署策略进行了研究，降低了任务响应和处理的时间.边缘计算技术的应用降低了服务的延迟，提升了任务的执行效率.

在直播应用领域中引入边缘计算可以提升直播的服务体验.文献[11]提出了一种云边缘直播分发架构，该架构显著减少了云端的转码和带宽负载.由于边缘服务器更接近用户，可以通过将用户分配到附近的边缘服务器来降低延迟，同时实现了灵活和细粒度的网络管理.文献[12]指出直播视频的编解码过程需要消耗大量的计算资源和时间.通过在边缘云辅助异构网络中寻找一种高效、高质量和低延迟的直播视频编解码方案，提高了直播的服务质量.文献[13]提出了一个基于边缘的直播临时缓存方案，通过上下文感知的方式在边缘缓存最少数量的直播视频片段，避免了视频缓冲，并大幅度减少了初始启动延迟和直播延迟，在全球互联网上实现了无缝的4K直播.文献[14]针对360°全景视频直播中延迟高、数据处理量大等问题，提出了一种用于全景视频的移动边缘辅助实时流媒体系统，可以智能地将处理任务卸载到边缘服务器中，实现了低延迟全景视频直播.文献[11-14]在把边缘计算技术应用到视频直播领域的同时，充分发挥了边缘计算的优势，改善了直播中延迟过高、服务器资源开销大等问题，提升了直播的服务质量，优化了用户体验.

在边缘计算的典型架构中，边缘服务器通常被部署在基站上[15].为了研究边缘服务器在现实场景中的覆盖情况，本文处理并分析了澳大利亚墨尔本地区基站数据集[16]，发现有91%的终端用户所在位置可连接到的基站数量超过10个，即大多数用户处于多个边缘服务器的重叠覆盖区域内.如果这些用户是直播观众，由于各边缘服务器可用资源和传输延迟的差异，用户通过不同的边缘服务器获取视频会对直播体验产生不同的影响，边缘计算环境中的互动直播面临新的挑战.目前已有相关工作研究了多边缘服务器场景中的用户分配问题，文献[16]在边缘服务器密集重叠分布的场景中，从应用程序供应商角度出发，采用博弈论的方法，尽可能租用少的边缘服务器为更多的用户提供服务.文献[17]设计了一种支持移动感知和迁移的方法，用于实时分配用户.在边缘服务器容量约束下，最大化用户的覆盖率，最小化用户的重分配次数.但文献[16-17]研究工作均是一种通用的应用场景，忽略了边缘服务器的选择对用户体验的影响，并不适用于解决互动直播中的问题.综上，将边缘计算应用到互动直播中，在多边缘服务器场景下如何对直播用户进行分配来提升用户体验的问题仍有待解决.

为了研究互动直播中用户的需求差异，本文分析了哔哩哔哩直播网站的用户弹幕数据集.结果显示不同用户的互动行为差异明显，有59%的用户在单位时间内只互动了1次，而有37%的用户互动次数在2～10之间.与很少参与互动的用户相比，经常互动的主动用户对较大的延迟更敏感[11].所以在为直播用户分配边缘服务器资源时，对于经常互动的用户要考虑分配传输延迟更低的边缘服务器；对于很少互动的用户，要将用户体验优化重点放在视频质量上，并分配更多的带宽和计算资源.在构建直播用户体验质量（quality of experience, QoE）模型时，要考虑用户的个性化需求.文献[18]在研究低延迟多方互动直播的自适应码率控制的工作中，分别从直播视频质量、视频质量变化量、缓冲时间以及延迟4个方面表示用户QoE.文献[19]用直播视频的帧率和分辨率来映射用户QoE，并根据直播视频类型来控制这2个因素的权重.文献[18-19]研究工作主要关注直播视频的观看体验，而忽略了直播的互动体验.文献[11]在互动直播的QoE模型中引入了一个互动参数，用来反映观众的互动强度，并从视频码率、延迟和启动延迟3个方面表示用户QoE.但对于多边缘服务器场景下直播用户体验的优化，还应当结合边缘服务器的覆盖范围和用户地理位置考虑服务器的选择对用户体验造成的影响.综上，互动直播中不同用户的互动行为差异明显，在构建直播用户QoE模型时要综合考虑用户的互动体验和视频质量，根据用户的个性化需求为用户分配边缘服务器和系统资源，优化直播用户体验.

本文提出了一种边缘计算中基于用户体验的互动直播用户分配策略.在多边缘服务器多用户的场景下，考虑到边缘服务器的资源有限以及用户的个性化需求，通过为各个用户在当前时段内分配合适的边缘服务器并选择合适的直播视频码率，最大化多边缘服务器覆盖范围内的所有用户整体QoE.本文的主要贡献包括3个方面：

1）通过对真实数据集的处理分析发现.大多数用户处于多个边缘服务器重叠覆盖区域中，且不同直播用户的互动行为差异明显.为了提升边缘计算场景下的直播用户体验，需解决边缘服务器重叠覆盖区域内的用户分配问题.

2）在多边缘服务器、多用户场景中，为直播用户分配不同的边缘服务器对用户体验产生不同的影响.考虑到直播用户的需求不同，提出一个适用于边缘计算场景的直播用户QoE模型，该模型综合考虑了用户互动体验、直播视频质量、边缘服务器切换等因素对QoE的影响.

3）证明了本文提出的用户分配问题为NP-hard问题，并设计了一个直播用户分配算法，高效地解决了根据用户的个性化需求，为用户分配边缘服务器和系统资源提升了直播用户QoE.通过基于真实数据集的仿真实验验证了算法的性能，实验结果表明该算法在保证延迟和码率均有较好表现的同时降低了服务器切换次数和视频质量抖动，使用户QoE相较于对比算法高出了19%.

1 数据分析及问题描述

本节将首先介绍基站用户地理位置数据集和直播用户弹幕数据集的处理工作，并分析现实场景中基站对用户的覆盖情况，以及直播用户互动行为的差异；然后介绍边缘计算场景中的直播视频分发架构；最后对互动直播中的用户分配问题进行详细描述.

1.1 数据处理和分析

本文分析了澳大利亚地区基站数据集[16].该数据集主要包含了墨尔本中央商务区的基站和用户的经纬度位置信息，以及各基站的型号、类别、状态等信息.此数据集的规模可以反映日常工作生活场景中用户和基站的地理分布情况，具有一定的普适性.根据现实场景中的中心城区基站的覆盖范围，将数据集中基站的覆盖半径设定为300 m.由已知基站和用户的经纬度可计算得到各用户可连接到的基站数量，如图1所示.可连接基站数量低于10的用户占总用户数量的8.8%，大部分用户可连接的基站数集中在10～20，人数占总用户数的74.4%，另外有16.8%的用户被20个以上的基站同时覆盖，甚至有部分用户可连接的基站数超过30.如果将边缘服务器部署在部分基站上，在基于边缘计算的互动直播场景中，大多数直播用户处于多个边缘服务器的公共覆盖范围内，由于边缘服务器传输延迟和剩余资源的差异，使用户连接不同的边缘服务器的直播体验不同，需要在多个边缘服务器中进行选择.所以，在多边缘服务器场景下，需要对用户进行合理分配，提升直播用户体验.

Fig.1 Distribution of the proportion of people corresponding to the number of connectable base stations图1 可连接基站数对应的人数占比分布

为了分析直播用户的互动行为，通过编写一个爬虫程序获取了哔哩哔哩直播网站数据集，并重点收集了17个热门直播间内用户的弹幕数据.数据集信息主要包括直播网站每小时的总直播间数量和总用户数量，以及各热门直播间内每条弹幕的内容、发送时间、发送用户ID和当前直播间的用户数量.

首先计算24 h内平均每小时的直播间数量和用户人数的分布情况，如图2所示.在早上6点左右，直播用户数量达到低谷，累计上线的总用户数量为435万左右，累计创建直播间数量为1 982；而在晚上8点左右是观看直播的高峰期，总用户数量为6 883万左右，直播间数量为18 178.在观看直播高峰期，用户和直播间数量的急剧增长给直播平台的服务器带来了巨大的带宽和计算压力，边缘计算可以在网络边缘对直播视频进行转码和传输，为用户提供低延迟的直播服务，缓解云端服务器的压力.

Fig.2 The number of live streaming rooms and distribution of the number of users图2 直播间数量和用户数量分布

然后分析了热门直播间内弹幕的发送情况，统计各用户发送的弹幕数量，结果如图3所示，横坐标表示用户单位时间发送弹幕数量，纵坐标表示各弹幕数量对应的人数相对于总人数的累计比例.经统计发现，有59%的用户平均每小时只互动了1次，并且96%的用户平均每小时互动次数在10以内，高度倾斜的曲线反映出不同用户的互动行为差异明显，其中一部分用户只观看直播视频，很少参与互动，而另一部分用户积极主动地参与互动.对于频繁参与互动的用户，更期望体验低延迟直播服务，较高的延迟会使其无法及时接受到最新的直播内容和互动信息，影响到直播体验；对于很少参与互动的用户，延迟对其直播体验影响相对较小，直播视频的质量会更为重要.因此在优化直播用户体验为用户分配边缘服务器资源时，要考虑用户的个性化需求.

Fig.3 Distribution of cumulative proportion of the number of people corresponding to the number of barrage图3 弹幕数量对应的人数累计占比分布

最后，为了分析影响用户互动行为的因素，统计了17个热门直播间内的弹幕数量.利用各直播间每小时内的总弹幕数量除以用户数量计算出直播间单位时间人均弹幕数，将结果按照从小到大排序，并对直播间进行编号，结果如图4所示.其中有4个直播间单位时间人均弹幕数低于0.01，而有7个直播间人均弹幕数高于0.02，其中人均弹幕数最高达到了0.13.并且不同直播间的用户互动行为也存在着明显差异，部分直播间内用户的平均互动积极性明显高于其他直播间，因此影响用户互动行为的因素不仅和用户自身需求有关，还和用户所在直播间有一定的关系.在分析用户的互动需求时，需要考虑用户所在直播间的影响.

Fig.4 Distribution of the number of barrages per capita in each live streaming room图4 各直播间人均弹幕数分布

1.2 直播视频分发架构

将边缘计算技术应用到互动直播中可以缓解云端服务器的压力，降低互动直播的延迟.基于边缘计算的直播视频分发架构如图5所示，其主要由主播端、基站、主播侧的边缘服务器、传输网络、用户侧的边缘服务器、用户端6部分组成.考虑主播和用户地理位置接近的情况，如同城直播、现场体育赛事直播等，可直接利用边缘服务器提供直播服务.首先，主播将视频采集设备获取的原始视频上传到其附近可连接到的边缘服务器当中；然后，主播侧的边缘服务器将根据直播视频请求，通过边缘服务器之间的网络专线将直播视频分发到对应用户附近的边缘服务器中；最后，用户侧的边缘服务器可以对直播视频进行实时转码处理，将直播视频转换为不同分辨率的版本，并根据网络状况和用户需求将最合适的视频码率版本传输给直播用户.

Fig.5 Live streaming distribution architecture based on edge computing图5 基于边缘计算的直播视频分发架构

1.3 问题描述

通过1.1节中的数据集分析可知，大多数直播用户处于多个边缘服务器重叠覆盖区域中，并且不同直播用户的个性化需求存在差异.如图5中用户A和用户B同时被边缘服务器1，2，3覆盖，假设用户A经常参与直播互动，期望更低的直播延迟；用户B更关注直播视频的质量，期望更高的码率.为了使2个直播用户的QoE之和更优，可以将用户A分配给总延迟更低的边缘服务器2，并选择下载分辨率为480P的直播视频，将用户B分配给剩余资源更多的边缘服务器3，并选择高分辨率1080P的直播视频.考虑到下载直播视频需要占用用户侧边缘服务器的带宽资源，转码需要消耗用户侧边缘服务器的计算资源，在服务器资源有限的情况下，如何为多边缘服务器覆盖范围内的所有用户分配合适的边缘服务器并选择合适的视频码率，使所有用户整体QoE最大化是一个有待解决的问题.

在基于边缘计算的互动直播应用场景中，边缘服务器的覆盖和用户的地理分布情况较为复杂，大多数用户被多个边缘服务器同时覆盖，需要根据用户体验在多个服务器中进行选择，因此互动直播中的用户分配问题具有挑战性和现实意义.本文主要研究在多边缘服务器多用户场景下，考虑到边缘服务器的带宽和计算资源有限，根据直播用户的个性化需求和当前的状态，为多边缘服务器重叠覆盖范围内的所有直播用户分配合适的边缘服务器并选择合适的直播视频码率，使此范围内所有直播用户当前时段的整体QoE最优.

2 系统模型

系统中用户侧的边缘服务器集合可用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存在约束：

在多边缘服务器场景下，重叠区域内的用户虽然可以在多个边缘服务器中进行选择，但在当前时间段每个用户最多只能通过基站连接到1个边缘服务器，因此xv,m同时应满足关系：

2.2 直播用户QoE模型

在互动直播中，用户体验主要分为2个方面：直播互动体验和视频观看体验.直播互动体验和直播延迟有密切的关系，延迟越低，互动体验越优.另外根据前面数据集分析的结论，不同用户的个性化需求差异明显，在优化用户互动体验时，要考虑用户的互动需求，所以互动体验主要受到延迟和互动需求2个因素的影响.对于直播视频观看体验，一方面和当前直播视频的比特率有关，视频比特率越高，对应的视频分辨率越高，用户体验越优.同时直播视频比特率的抖动会对用户体验产生负面影响.另一方面在边缘计算中，边缘服务器的切换会导致切换延迟.因为资源引导、加载配置和文件迁移会增加服务时间[20]，所以若用户当前时间段连接的边缘服务器和前一时间段连接的边缘服务器不同时，服务器切换产生的延迟会导致直播视频缓冲停顿，影响用户的观看体验.

2.2.1 直播互动体验

互动体验主要受延迟的影响，直播视频在各网络节点之间的传播和在边缘服务器中的转码是造成直播延迟的主要原因.直播视频传播延迟主要包括主播到主播侧边缘服务器的延迟、主播侧边缘服务器到用户侧边缘服务器的延迟、用户侧边缘服务器到用户的延迟.根据文献[8，21]中节点之间延迟的计算和预估方法，可依据香农定理得到m与n2节点之间的传输速率rmn，表示为

其中Bmn表示节点m与n之间的信道带宽，Pmn表示2节点间的平均信号功率，σ2表示平均噪声功率，Pmn/σ2即表示信噪比.则边缘服务器m与用户n之间的传输延迟Tmn表 示为

其中，λm表示直播视频数据大小.参考文献[18]的工作，在本文中将各节点之间的传输延迟作为已知条件.转码延迟主要受到原视频码率和用户观看视频码率的影响，原视频码率和用户观看视频码率之差越大，需要处理的视频数据量越多，则转码产生的延迟越多.用户v连接边缘服务器m时的直播视频延迟Lv,m表示：

其中Tbv,mbv为主播bv到边缘服务器mbv之间的直播视频传播延迟，Tmbv,m为边缘服务器mbv到边缘服务器m的直播视频传播延迟，Tm,v为 边缘服务器m到用户v之间的直播传播延迟，G为边缘服务器中转码对应产生的延迟.

互动体验还和互动需求有关，根据1.1节中数据集处理的结论，用户的互动需求会受到直播间的影响，因此互动需求值Iv可 根据用户v在当前直播间内的互动情况得到，并表示为

其中Fv为 用户v在当前直播间内的历史互动频率，互动频率为用户发送弹幕数和相应时间的比值，可从直播用户的历史记录信息中得到，权值γ用于控制互动需求值的范围.

在实时音视频互动中，有研究指出1 s左右的延时会给用户的互动交流带来异步感，必须尽可能将视频播放延迟限制在400 ms以内才能给用户带来较好的交互体验.当延迟控制在400 ms以内时，2个人的音视频互动是实时的，不会有异步感存在[22].所以可以推断在互动直播中存在一个延迟阈值β，当直播延迟小于β时，主播和用户可以实时互动，用户的互动需求值越高，互动越频繁，用户越能体验到互动的畅通感，互动体验越优；当直播延迟大于β时，对用户互动产生负面的影响，如果用户互动需求值越大，越容易感受到异步感的存在，用户互动体验越差.同时从文献[11]中得到启发，延迟越低，互动体验越优，最终直播延迟和互动需求值映射到直播互动体验Q(Iv,Lv,m)的函数式表示为

其中β为延迟阈值，Lv,m为用户的直播延迟，Iv为用户的互动需求值.

对于式（7），由于Iv的值非负，当Iv的取值一定时，Lv,m的值越小，互动体验值越大，并表示为：

所以其满足延迟越低、互动体验越优的结论.当Lv,m的取值一定时，存在关系：

如式（9）所示，当Lv,m≤β时，Iv越大互动体验值越大；如式（10）所示，当Lv,m的值＞β时，Iv越大互动体验值越小.所以式（7）同时也满足当直播延迟小于延迟阈值时，用户的互动需求值越高，互动体验越优；当直播延迟大于延迟阈值时，用户互动需求值越大，用户互动体验越差的结论.综上，互动体验的式（7）符合实际要求.

2.2.2 直播视频观看体验

视频质量是影响视频观看体验的主要因素之一，而视频质量和视频码率有关，参考文献[23]中定义的视频质量表达式，并对其进行修改，用户v的直播视频质量Uv函数表达式为

考虑到用户的个性化需求，其中R*v为用户v所期望的码率，可根据用户观看直播历史记录中主动选择的视频分辨率等级得到.Rv为用户v观看直播的实际码率，当用户观看直播时的码率不低于用户所期望的码率时，用户视频质量达到最优.

视频质量的抖动会对视频观看体验产生影响.视频码率突然下降将会对用户体验产生相应的损失，而当码率上升时就不会对用户体验造成损失.视频质量抖动Ev表 示为

其中[x]+=max{0,x}，为前一个时间段用户的平均码率，k表示用户的码率每降低一个单位对用户体验造成的损失值.

边缘服务器的切换也会对直播视频观看体验造成负面影响.在为边缘服务器重叠覆盖区域内的直播用户作出当前时间段边缘服务器选择决策时，需考虑用户前一时间段的边缘服务器连接状态.边缘服务器的切换会产生一定的服务等待时间，造成直播的缓冲卡顿，降低用户体验质量.边缘服务器切换对用户体验的影响表示为：

综上所述，当用户v选择连接边缘服务器m，并观看码率为Rv的直播视频时，用户的QoE记为QoEv,m，可以表示为4个因素的加权求和，即

用户QoE主要和互动体验质量、视频质量、码率抖动、边缘服务器切换有关，其中a，b，c，d为权值，可根据实际情况进行设定.

2.3 边缘服务器资源约束

对于系统中用户侧的边缘服务器，其带宽和计算资源是有限的，只能为有限数量的直播用户提供直播服务.将码率为Rv的直播视频传输给用户v时，需要分配给用户与码率相对应的带宽资源，用户才可以正常观看相应等级的直播视频.连接到同一个边缘服务器的用户码率之和不超过边缘服务器总网络吞吐量的约束，则满足约束条件：

其中Dm表示边缘服务器m提供给直播用户时获取视频的总带宽资源.

当对直播视频进行转码时，需要占用边缘服务器一定数量的虚拟处理器，连接到同一边缘服务器m的用户转码开销之和不可超过边缘服务器m的总计算资源.转码消耗的计算资源主要和视频的原始码率R以及目标码率Rv有关，码率跨度越大，消耗的资源越多.边缘服务器m的计算资源约束表示为：

其中Cm表示边缘服务器m可供直播转码的总计算资源，H为转码对应的计算资源开销.

2.4 优化目标

优化直播用户体验可以为直播平台吸引更多的用户，提升直播平台的收益和市场竞争力.直播系统的优化方向之一是为那些有价值的观众提供差异化的视频交付服务.例如，系统可以安排更好的网络路径给有价值的观众，提升他们的用户体验.作为回报，这些观众会捐赠更多的虚拟礼物[24].所以本文在优化直播用户QoE时，考虑到了用户捐赠礼物金额，优先提升捐赠金额高的用户QoE，可为直播平台带来更多的利益.为了衡量各用户赠送礼物的金额大小，用Yv表示用户v的赠礼金额影响因素：

其中pv为用户v捐赠礼物的总金额，可根据用户历史信息得到，α为权值.为了提升多边缘服务器覆盖范围内直播用户QoE，问题模型确定为：

目标函数的约束条件主要包括各边缘服务器可供直播视频转码的总计算资源约束（见式（19））、各边缘服务器供直播视频传输的总带宽资源约束（见式（20））.式（21）表示各用户当前时段只能连接1个边缘服务器.式（22）表示用户v是否连接边缘服务器m.赠礼金额影响因素Yv作为权值影响着各直播用户QoE，对于Yv值越大的用户，提升其用户QoE使总QoE增长更多，满足现实需求.最终目标是确定每个直播用户的边缘服务器连接状态xv,m以及视频平均码率Rv，使所有用户加权QoE之和最大化.需要注意的是视频码率Rv的取值和视频分辨率版本的选择相关，直播视频通常会有多个不同分辨率版本，其对应的视频码率Rv的取值并不连续，因此本文提出的互动直播中用户分配问题是一个离散变量优化问题.

3 算法设计

为了解决第2节中的用户分配问题，本文设计了一种基于直播用户体验的用户分配策略.对于多边缘服务器覆盖范围内的各直播用户，当其连接到边缘服务器观看直播时，边缘服务器可以获取到用户的位置信息以及用户直播历史数据信息.由于边缘服务器之间可以通信，各边缘服务器能统一处理用户信息以及边缘服务器状态信息.通过用户位置信息可以确定各用户可连接的边缘服务器集合.根据直播用户历史信息可计算获得用户的互动需求值、赠礼金额影响因素、前一时段平均码率、前一时段服务器连接状态等参数，结合各边缘服务器网络状态和剩余资源等信息，通过执行直播用户分配算法，确定各用户当前时段应该选择的边缘服务器和直播视频码率，并将决策结果通过各边缘服务器传输给用户实施.接下来本节将首先对原问题进行深入分析，然后再设计直播用户分配算法.

定理1.互动直播中的用户分配问题为NP-hard问题.

证明.为了进行证明，首先引入一个经典的NP-hard问题：多维0-1背包问题.假设有n个物品，(y0,y1,…,yn-1)，yi∈{0,1}表示物品是否放入背包中.物品i对应的价值为qi，为了使放入背包中物品价值之和最大，目标函数可表示为

假设物品i的重量为wi， 体积为ei，背包最大能承载的重量为K，容积为N.要使装入背包的物品重量不超过背包最大载重，且体积不超过背包的容积，则约束条件可表示为

现将原问题进行简化处理，假设只考虑1个边缘服务器m，则问题变为在满足边缘服务器m资源约束条件下，如何对边缘服务器m覆盖范围内的用户进行分配，使连接到边缘服务器m的直播用户整体QoE最大化.边缘服务器m覆盖范围内的用户集合为V，用xv表ß示用户和边缘服务器i的连接关系：

参考式（18），则简化后的问题目标函数可表示为

假设可供用户v选择的视频码率版本唯一，码率为Rv，则Yv·QoEv的值可以直接计算得到，用qv表示，则式（27）变为

通过观察可发现，式（23）和式（28）的表示形式一致.假设边缘服务器m的计算资源为Cm，可用带宽资源为Dm，对于边缘服务器网络吞吐量约束以及计算资源约束，参考式（15）和式（16）可分别表示为

由于码率Rv已确定，则可用ev表示(R-Rv)×H，式（23）可变为

通过观察可发现简化后问题的约束条件式（29）（31）与多维背包问题的约束条件式（24）（25）形式一致.综上，将原问题经过简化处理可转化为0-1背包问题，而背包问题为NP-hard问题，所以简化之前的用户分配问题也为NP-hard问题.

证毕.

定理2.互动直播用户QoE是用户码率Rv∈{1,2,…,R}的递增函数.

证明.将直播用户QoE函数式展开，只考虑包含码率Rv，主要包括3个部分：

在第1部分互动体验中，原始码率R的取值一定，因此Rv值的变化会对视频转码延迟产生影响，为了使用户正常观看相应码率版本的直播视频，会提供与码率相对应的直播网络带宽，所以码率Rv的变化不会对视频传输延迟产生影响，因此Rv越大，使得转码产生的延迟越小，互动体验越优；在第2部分视频质量中，当时，Rv的值越大，视频质量越优，当时，视频质量达到最优情况；在第3部分视频质量的抖动影响中，当时，Rv越大，视频质量抖动产生的负面影响越小，而当时，视频质量抖动的负面影响为0.综合分析可知，用户QoE在可选码率范围内是关于Rv的递增函数.

证毕.

然后再根据边缘服务器剩余资源进行调整.当网络带宽资源不足时，选择更低码率版本；当计算资源不足时，选择更高码率版本，使得Rv满足边缘服务器资源约束.

为了对问题进行高效求解，本文设计了一种直播用户分配算法（live streaming user allocation algorithm，LUA）.该算法采用了贪心的思想，具有多项式级的时间复杂度，能够快速获得决策结果，满足现实场景的需求.该算法的主要流程如图6所示.

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

1）初始化各参数，确定Rv的初试值为和中较大的值，计算所有用户赠礼金额影响因素值Yv，并对用户集合中的用户根据赠礼金额影响因素值进行降序排序.

2）按照排序后的用户集合中用户的顺序取出用户v，依次遍历用户v可连接的边缘服务器集合M(ν)中的各边缘服务器.当用户v连接边缘服务器m时，通过定理2对QoEv,m函数式分析可知，QoEv,m是关于Rv的递增函数，则根据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，各节点之间的传播延迟，用户的互动需求值及赠礼金额影响因素值Iv和Yv，用户前一时间段状态；

输出：各用户的边缘服务器连接状态xv,m，各用户直播视频码率Rv.

① 初始化各用户参数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给出了直播用户分配算法的具体流程.其中行①②完成了对用户按优先级排序，行③～㉒实现了依次对各用户进行分配.在分配的过程中，行④～⑯计算了各用户当前状况下分别连接各边缘服务器能获取到的最大QoEv,m，行⑰～⑲给出用户的最优决策结果，而行⑳㉑实现了边缘服务器剩余资源的更新.

算法1基于贪心策略根据赠礼金额影响因素值对用户进行排序，按照顺序依次选取集合V中的直播用户，然后对于当前选择的用户v依次遍历其可连接到的边缘服务器计算QoEv,m，此时循环执行次数为|V|×|M(v)|，最坏情况为所有用户均可访问所有边缘服务器，即|V|×|M|.在计算用户QoEv,m时，需要确定用户此时的码率Rv,m， 若初始化的Rv满足约束条件则不需要调整，否则需要遍历码率集合确定满足约束的码率R，则最坏情况需要遍历所有码率情况，循环执行次数为|V|×|M|×R.最终将用户QoEv,m最大时的情况作为决策结果，并更新边缘服务器剩余资源.复杂性来自对用户集合、各用户可连接边缘服务器集合以及码率集合的遍历，所以时间复杂度为O(|V|×|M|×R).

在现实场景中，一定地理范围内的直播用户数量和边缘服务器的数量是有限的，并且直播视频可选择的分辨率版本较少，对应的码率集合有限，所以该算法可以快速得出决策结果，有较高的执行效率和较低的性能开销，满足直播场景的实时性需求.

4 实验与结果分析

4.1 实验设置

本文使用真实数据集进行仿真实验，为了构建边缘服务器和直播用户的覆盖关系，本文采用了基站数据集[16]，该数据集主要包含墨尔本中心商务区的基站和用户的位置信息.首先从数据集中随机选取一定数量地理位置接近的基站部署边缘服务器，确定基站的覆盖范围；然后根据用户的位置信息，可得到边缘服务器所覆盖的用户情况；最后随机选取其中部分覆盖重叠区域内的用户作为直播用户，确定各直播用户可连接的边缘服务器集合.为了使用户所选择的码率和用户前一时间段观看直播的码率更接近实际情况，本文参考了Twitch直播数据集[25]，该数据集主要包括用户信息、主播信息、直播频道信息、直播分辨率信息等.对该数据集中直播分辨率信息进行统计，根据数据集中用户的直播视频分辨率分布情况生成实验中各直播用户所期望的分辨率和前一时间段观看直播的分辨率.各分辨率对应的码率范围和平均码率设定如表2所示.

Table 2 Video Bit Rate Parameters表2 视频码率参数

实验中，将各边缘服务器可供直播使用的总网络吞吐量设定为40 Mbps，可供直播转码的总计算资源设为15 vCPUs，转码延迟参数G= 50 ms/Mbps，转码所需的边缘服务器计算资源开销参数H= 0.5 vCPU/Mbps.用户QoE各指标权值为a= 5，b= 1，c= 1，d=1.结合现实场景中的情况，将边缘服务器的覆盖半径设置为300 m，将用户到边缘服务器之间的传输延迟设置为5～15 ms，边缘服务器之间的传输延迟设置为100～300 ms，延迟阈值β= 300 ms.实验的主要参数如表3所示.

Table 3 Main Parameters Setting表3 主要参数设置

本文将LUA算法与延迟优先（delay first，DF）算法、改进HAS频道放置（modification of the HAS channel placement，MHCP）算法[19]、随机分配算法Random进行对比.DF主要策略是各用户选择可连接到的直播传输延迟最低的边缘服务器，码率根据连接的服务器剩余资源和用户期望的码率进行调控，使用户体验最优，这是一种比较直观的主流策略.MHCP是对直播频道放置（HAS channel placement，HCP）算法的修改，根据文献[19]中服务器剩余空间RSm的值对服务器进行排序，用户优先连接RSm值最高的边缘服务器并选择最高码率版本视频，使直播视频质量最优.RSm表示为

其中countm为连接到边缘服务器m的人数，RCm为剩余计算资源的比例，RDm为剩余带宽资源的比例.Random中，用户在可连接到的边缘服务器集合中随机进行选择，同时随机选择分辨率版本作为当前的决策结果.由于原问题为NP-hard，最优解算法执行效率过低，算法时间复杂度为指数级，对于实验数据不能在有效的时间内给出决策结果，同时也无法满足现实场景的需求，所以不采用最优解算法.

为了全面评估LUA算法的性能，本文选定了3个实验参数：1）边缘服务器数量；2）直播用户数量；3）用户互动需求值范围.同时选取了延迟、码率、互动体验质量、码率抖动值、服务器切换次数、用户QoE这6个性能评价指标.为了模拟不同的现实场景，并分析各实验参数对算法性能的影响，进行了3组实验，实验设置如表4所示.每组实验首先利用基站数据集[16]随机生成相应数量的边缘服务器和用户，根据数据集中的位置信息和边缘服务器覆盖半径确定各用户可连接到的边缘服务器集合，同时根据直播数据集[25]生成各直播用户所期望的分辨率和前一时间段观看直播的分辨率.然后根据表3初始化各参数，将所有用户和边缘服务器信息作为输入依次执行LUA，DF，MHCP，Random算法，分别输出用户的边缘服务器和码率选择情况.最后根据各算法的输出结果计算性能评价指标，并进行对比分析.为了尽可能减少随机参数对实验结果的影响，每组实验进行5次计算，取所有结果的平均值作为最终结果.

Table 4 Experimental Setting表4 实验设置

4.2 性能分析

首先分析直播用户数量对各评价指标的影响.如图7所示，MHCP在平均用户码率上表现最优，平均高出LUA 21%.主要原因是MHCP中用户优先连接剩余资源最多的边缘服务器，并选择最高码率版本视频.但随着用户数量增多，在边缘服务器可供分配资源不充足的情况下，MHCP中用户平均码率表现和LUA接近，均优于其他算法.另外，虽然码率越高用户体验越优，但当服务器资源有限的情况下，只选择最高码率会导致部分用户可用资源不足，可能对整体用户体验产生负面影响.

Fig.7 Effect of the number of users on bit rate图7 用户数量对码率的影响

如图8所示，当直播用户数量为50时，边缘服务器带宽和计算资源充足，MHCP中大部分用户均可以选择最高码率视频，避免了转码产生的延迟，所以延迟表现最优.随着人数增加，导致各用户平均分配到的服务器带宽资源减少，可选择的码率下降，转码产生一定的延迟，使得平均用户延迟呈上升趋势.对于DF，由于用户优先连接延迟最低的边缘服务器，所以平均延迟整体表现最优.LUA在延迟表现上要高出DF 8%，平均延迟仅相差22 ms.

Fig.8 Effect of the number of users on delay图8 用户数量对延迟的影响

在平均用户服务器切换次数的表现上，如图9所示，LUA明显优于其他对比算法，其切换次数相较于表现第2的DF要低49%.主要原因是其他算法在以高码率或低延迟为目标选择边缘服务器时忽略了用户前一时间段边缘服务器的连接状态.边缘服务器切换会对用户体验产生负面影响，LUA考虑到了此因素，较好地控制了服务器的切换.但随着用户人数增多，当服务器资源不足时，用户只能选择其他边缘服务器，这也使得LUA中服务器切换次数随着人数增长而上升.

Fig.9 Effect of the number of users on server switching图9 用户数量对服务器切换的影响

对于直播用户码率抖动指标，如图10所示，LUA表现最优.尽管MHCP针对码率进行优化，在用户人数较少时，码率抖动情况表现较好，但随着人数的增加，剩余服务器资源逐渐减少，受服务器资源的约束，部分用户只能选择低码率视频，导致下降的码率增加，所以MHCP在人数增多的情况下性能表现较差.而LUA通过合理的码率选择，使得在服务器资源不足时，码率抖动也相对其他算法有较优的表现，平均下降码率整体表现上要低MHCP 61%，而Random和DF在码率抖动的控制上性能表现较差.

Fig.10 Effect of the number of users on bit rate jitter图10 用户数量对码率抖动的影响

如图11所示，对于用户互动体验质量，LUA有最优的表现.直播互动体验不仅和直播延迟有关，还和用户的需求有关.所以尽管在平均延迟的表现上LUA并不是最优，但LUA在为用户选择不同延迟的传输路径过程中，考虑到了用户的互动需求.对互动需求高的用户分配低延迟路径，使得在互动体验的表现上不弱于延迟更低的策略.但随着人数增多，平均延迟上升，导致互动体验均呈现下降趋势，用户数量增加到125时，DF的互动体验表现更好，要比LUA高14%，因为DF平均用户延迟相较于其他算法更低，但平均互动体验质量表现上，LUA比DF算法高0.4%.

Fig.11 Effect of the number of users on interactive experience图11 用户数量对互动体验的影响

如图12所示，随着人数的增加，受服务器资源的限制，用户平均可分配到的资源降低，使得用户QoE呈下降趋势.在平均用户QoE表现上，LUA最优，高出第2名DF 19%.综合前面的分析，尽管LUA在平均用户延迟和码率上表现不是最优，但其在选择码率和边缘服务器的过程中考虑到了用户的需求，合理地为用户分配服务器带宽和计算资源，避免了资源的浪费.同时LUA也关注到了边缘服务器切换和码率下降对用户QoE的负面影响，最终使其平均用户QoE结果优于其他算法.

Fig.12 Effect of the number of users on QoE图12 用户数量对用户QoE的影响

接下来分析边缘服务器数量对各实验指标的影响.如图13和图14所示，MHCP平均码率表现最佳，DF平均延迟表现最佳.LUA平均码率要低MHCP 21%，平均延迟高DF 10%.随着边缘服务器数量增加，系统总可用资源增加，用户可分配到的资源充足，使得码率呈递增趋势，转码产生的延迟降低，所以延迟呈下降趋势.当服务数量增加到10以上时，达到系统资源饱和状态，平均用户码率和延迟均趋于稳定.

Fig.13 Effect of the number of edge servers on bit rate图13 边缘服务器数量对码率的影响

Fig.14 Effect of the number of edge servers on delay图14 边缘服务器数量对延迟的影响

如图15和图16所示，LUA在控制码率抖动和边缘服务器切换中均有最优的表现，平均下降码率要低表现第2的MHCP 58%，平均边缘服务器切换次数要低DF 56%.主要原因是其他算法在连接最低延迟和最多剩余资源的边缘服务器的过程中，不可避免地造成了边缘服务器的切换.在LUA中，随着边缘服务器数量的增加，各服务器计算和带宽资源充足，可供用户选择，有效避免边缘服务器切换，所以平均切换次数下降.但当服务器增加到一定数量时，选择连接新的边缘服务器使用户体验增加的几率增加，最终使得平均用户服务器切换次数呈上升趋势.对于码率抖动，当边缘服务器总资源不足时，用户只能选择较低码率，所以码率抖动较大，随着边缘服务器数量增多，码率抖动情况减少，当服务器资源充足时，LUA和MHCP均可避免码率抖动.

Fig.15 Effect of the number of edge servers on server switching图15 边缘服务器数量对服务器切换的影响

Fig.16 Effect of the number of edge servers on bit rate jitter图16 边缘服务器数量对码率抖动的影响

在图17和图18中，原因同之前分析，LUA在QoE的表现上最佳，DF仅次于LUA.随着边缘服务器数量的增加，除Random之外，其他算法在用户体验表现上均递增.主要原因是随着服务器数量增加、人数不变，人均可分配的资源增加，使得用户可选择的码率版本更高，并且可选择的低延迟服务器数量增加，最终用户互动体验和用户QoE增加.但对于边缘服务器数量增加到10和12的情况，平均QoE表现趋于稳定，说明此时边缘服务器的总资源相对于当前用户人数已经过剩，增加边缘服务器对用户的QoE并无太大提升.经计算，LUA的平均QoE相较于DF高出了19.3%.

Fig.17 Effect of the number of edge servers on interactive experience图17 边缘服务器数量对互动体验的影响

Fig.18 Effect of the number of edge servers on user QoE图18 边缘服务器数量对用户QoE的影响

然后通过改变各直播用户互动需求值的取值范围分析其对各算法结果的影响.由于用户互动需求值主要对延迟和互动体验造成影响，所以只对这2个性能评价指标进行分析.如图19和图20所示，在LUA平均用户延迟的表现上，用户的互动需求值的改变对其他3个对比算法均无明显影响，因为对比算法在做决策的过程中并没有考虑到各用户的需求.而LUA考虑到了用户的互动需求差异，为互动需求高的用户分配低延迟的传输路径，所以随着用户的互动需求值范围的增加，用户的平均延迟呈下降趋势，并且在高互动需求用户群体中的平均延迟表现上要优于DF.当互动需求值在（2，3）范围内时，LUA平均延迟比DF低6%.而对于平均用户互动体验，由于各算法中大部分用户延迟低于延迟阈值（300 ms），所以随着互动需求值上升，互动体验质量也上升.在整体表现上，LUA用户互动体验质量优于其他算法，高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值的增加，提升用户互动体验能为优化用户QoE带来更多收益，所以平均用户互动体验质量呈上升趋势.而用户的直播延迟越低，用户的互动体验越优，所以平均用户延迟呈下降趋势.其中a= 11时比a= 1时，用户的平均延迟下降了43.85 ms，平均互动体验质量上升了22%.因为直播用户延迟是存在范围限制的，受传输延迟影响不能无限制下降，所以当a= 9时，用户互动体验和延迟已趋于稳定.权重a对服务器切换和码率的影响如图22所示，随着a值的增加，其他因素对用户体验的影响减小，为了使用户有更好的互动体验，会尽可能地为用户选择更低传输延迟的边缘服务器，所以使得服务器切换次数呈上涨趋势，其中a= 11时，平均用户服务器切换次数达到了0.53，而码率对互动体验的影响较小，所以其表现较为稳定.综上，QoE模型中权重的设定会对LUA的结果产生一定的影响，在实际应用中，可根据需求在一定范围内设定各因素的权重.

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对服务器切换次数和码率的影响

最后，在一组小规模数据上运行了最优解算法，实验设置有2个边缘服务器、20名直播用户、4种直播视频分辨率版本.最优解算法和LUA实验结果如表5所示.在各性能评价指标上，LUA均略低于最优解算法.在平均用户QoE表现上，LUA要比最优解算法低14%.虽然LUA结果离最优解有一定差距，但在现实场景中，直播的实时性要求和网络状态的实时变化需要算法快速作出决策.最优解算法无法针对较大规模数据及时给出决策结果，不满足实际需求.

Table 5 Comparison of Experimental Results表5 实验结果对比

综上，直播用户分配算法在优化延迟和码率时考虑了用户的个性化需求，保证了在平均用户延迟和码率上有较优的表现，同时降低了边缘服务器切换和码率抖动的负面影响，使平均用户QoE表现相较于其他对比算法更优.

5 总 结

在基于边缘计算的互动直播场景中，为了提升多边缘服务器重叠覆盖区域中的直播用户QoE，本文提出了一种面向互动直播的用户分配策略，考虑了边缘服务器资源约束和直播用户的个性化需求，为各用户分配合适的边缘服务器并选择合适的直播视频码率.在基于真实数据集的仿真实验中，验证了所设计的直播用户分配算法LUA相较于DF，MHCP，Random算法能够明显提升直播用户QoE.未来工作将考虑直播用户的移动性，预测用户的移动轨迹，在边缘计算环境下对用户的直播体验进行实时优化.

作者贡献声明：刘伟提供了研究思路和论文创新点；张骁宇负责建模和策略的设计，并撰写论文；杜薇提出指导意见并修改论文；彭若涛负责论文修改和最终版本的修订.