基于用户行为特征的SVC分片调度算法

唐朝伟,张 希,王雪锋,周 旭,宋俊平

(1.重庆大学通信工程学院,重庆400030;2.中国科学院声学研究所高性能网络实验室,北京100190)

基于用户行为特征的SVC分片调度算法

唐朝伟1,张 希1,王雪锋1,周 旭2,宋俊平2

(1.重庆大学通信工程学院,重庆400030;2.中国科学院声学研究所高性能网络实验室,北京100190)

针对异构环境中网络和终端的复杂性,以及用户随机搜索行为造成的视频点播服务中播放进度的突变性,提出一种异构环境中基于用户行为特征的可扩展视频编码分片调度算法。设计2类调度窗口,即根据当前播放时刻保证顺序播放数据持续功能的播放窗口和依据服从Weibull分布的用户随机搜索行为设计的加入数据预取机制的锚点窗口。对播放窗口和第一个锚点窗口采用逐层调度策略,以保证数据的及时性,其余锚点窗口使用rarestfirst策略,以平衡整个系统的分片分布。在OverSim平台上的仿真结果表明,与现有的逐层调度算法和权值调度算法相比,该算法在发生用户随机搜索行为的应用场景中能提高节点分片调度性能,缩短响应时延,降低服务器负载,提高用户观看视频的质量和流畅度。

异构环境;用户行为;分片调度;锚点窗口;对等网络;可扩展视频编码

1 概述

近年来,互联网行业中对等网络(Peer-to-Peer Network,PPN)技术发展迅速,这归功于它不仅能够明显地缓解传统C/S(客户端/服务器)网络架构中服务器端负载压力过大、单点失效等瓶颈问题,具有低成本、可扩展、健壮等优势,又能充分利用和分享各终端的丰富资源,在现今网络视频需求和流量的飞速增长的大环境下,基于对等网络的视频流媒体技术在当前互联网领域得到广泛的应用[1]。

随着无线移动互联网日新月异的发展以及三网融合产业蒸蒸日上的趋势,当前所面临的是一个越发丰富和复杂的异构环境。主要表现在:(1)网络异构,表现为接入网类型多样化,如3G、以太网、WLAN、LTE等;(2)终端异构,表现为用户所使用客户终端类型多样化。除了传统的电脑作为视频流媒体系统客户终端,电子产品的发展也使智能电视机、便携的平板电脑、智能手机等成为当下流行的流媒体播放载体[2]。

要处理好异构环境中所普遍存在的用户带宽、处理能力、分辨率、在网时间等方面的差异,可扩展视频编码(Scalable Video Coding,SVC)技术在对等网络视频流媒体系统中的应用已获得越来越多的关注。SVC技术将同一视频文件编码成一个基础层(Base Layer,BL)和若干增强层(Enhancement Layer, EL),用户可根据自身网络状况和终端能力合理选择接受层数,形成同一视频文件以不同的播放质量适应不同的用户终端的模式,更加适用于异构环境[2]。

在基于对等网络+SVC流媒体系统的视频点播服务中,客户端的分片调度方法举足轻重,直接影响用户观看质量和整个系统的负载及分发效率。随着快餐速食文化模式的发展,一个用户体验质量高且生命力长的视频点播服务,不但要满足用户随意选择观看内容,还要支持用户在观看视频过程中类似使用传统录像机的一些交互式操作(VCR操作)。如在客户端播放过程中可随意暂停、恢复播放,以及一些随机搜索的行为即随机改变播放进度,如前向搜索、后向搜索等[3]。研究表明,用户行为是服从一定统计分布的高频行为[3-4],所以,在分片调度算法中还应考虑到此因素,使用户尽可能流畅地欣赏视频内容,缩短由于发生VCR行为特别是其中的随机搜索行为引起的响应时间。

传统的调度算法采取将视频数据根据大小分块[5],没有考虑到异构环境的适用性以及对网络动态变化的弹性自适应。随着异构环境的复杂度增加,需要在异构环境中生存的对等网络+SVC分片调度算法越来越受到重视。在调度算法中引入窗口概念也成为热点,其将视频数据的下载范围局限在一个或多个实时的窗口中,这样通过窗口的规划、下载策略和滑动可以有条不紊地合理利用资源,实现优化调度。文献[6-8]采用了视频SVC分层的处理方法以及单窗口分层以固定顺序下载的策略,在调度上利用了SVC的分层特性,保证了播放的实时性,但该方法只考虑到顺序播放中靠近播放点的数据到达的实时性,未考虑到整个系统的分发效率。文献[9-10]采取窗口内下载顺序根据分片权值的大小来决定的策略,综合考虑待下载分片距离播放点远近、分片稀有程度(在邻居节点存在的拷贝数目)、基础层分片等因素,但未考虑用户行为。文献[11]提出一种考虑用户行为、跳转受限、流行度感知的数据预取机制,但是没有把异构环境纳入考虑因素。

基于对等网络+SVC技术,通过在视频点播系统客户端上引入数据预取功能以解决上述问题。数据预取即根据现在的播放情况预测用户的将来数据需求,更好地利用合理的空闲资源预先获取部分数据[5],以便在用户人为改变播放进度时,系统各终端能够作出及时响应,优先使用本地资源。

本文基于对等网络和SVC技术的视频点播系统,考虑用户随机搜索行为,运用窗口概念,提出一种基于用户行为特征的Anchor-对等网络SVC分片调度算法(UACS),该算法在纵向(“层”的角度)上根据网络和终端条件选择下载SVC层数,在横向(“时间”的角度)采用一个播放窗口+若干锚点窗口的模式。前者保证顺序播放条件下的数据持续,后者根据用户随机搜索行为特征的数学模型生成,从而保证在发生用户随机搜索行为时能优先利用预取数据,缩短响应时间,提高用户体验质量。

2 用户行为数学模型

流媒体系统在为用户提供视频点播服务时,在客户端可发生一系列随机搜索的用户行为,文献[3]的测量、分析、总结显示,用户在观看视频过程中发生的随机搜索行为(随机跳转长度)符合Weibull分布,概率密度函数如下:

视频文件的长度不同(分为长视频、短视频),随机搜索的方向不同(分为跳转到大于当前播放点时刻的前向搜索,跳转到小于当前播放点时刻的后向搜索),所满足的Weibull分布参数也不一样,如表1所示。

表1 随机搜索跳转长度特征参数设置

流媒体点播服务支持客户端用户边看边下载,看过的内容得以保存,则小于播放点播放时刻的后向搜索易于实现。因此,本文在设计调度算法时主要考虑的应用场景是用户发生的长视频前向搜索跳转行为。由表1可知,其跳转长度分布服从参数α=0.10916,β=0.54129的Weibull分布。

3 本文算法设计

在本文基于异构环境中用户行为特征的Anchor-对等网络SVC分片调度算法中,运用原有窗口概念,除设计保证数据及时性的播放窗口外,引入考虑用户行为的锚点窗口。其中,播放窗口采用已有的逐层调度策略;锚点窗口则根据用户行为特征模型对播放窗口进行补偿以及分段辐射整个播放区间,并根据播放进度周期更新。通过播放窗口+锚点窗口的机制,既保证播放的实时性,又缩短用户行为引起的响应时延。

主要步骤如下:

Step1根据当前播放时刻状况,依据上述窗口设计的原则规划播放窗口和锚点窗口的数据范围。

Step2首先申请下载播放窗口中分片,然后为第一锚点窗口分片,最后为剩下锚点窗口分片。

Step3判定缓存达到解码播放条件,进行播放。

Step43种情况下播放窗口被触发滑动,则重复Step1。

Step5播放结束。

3.1 播放窗口的设计

播放窗口的设计准则是保证顺序播放中数据的及时性,因此,在设计上紧紧结合当前播放点Pcurrent。设计如下:

(1)窗口size:初始化播放窗口的size为固定值。

(2)窗口的滑动:播放窗口从播放时间为0时开始生成,窗口滑动的触发模式有3种:

1)窗口的周期更新:系统中每次触发窗口滑动更新后会在指定的周期时间后再次滑动窗口,每次滑动步长为一个播放窗口size。

2)窗口内数据下载完毕后即时更新:当前窗口内所有的数据申请下载完毕或判定放弃后,距离上次周期更新的时间还未达到周期更新时间,那么会自动触发即时更新机制,每次滑动步长为一个播放窗口size,周期更新计时刷新。

3)用户行为的影响:系统内发生用户前向搜索的行为,播放窗口需要及时反应,窗口起始点更新为用户跳转后的当前播放时刻Pcurrent。

(3)窗口内数据块的调度:由于播放窗口中的数据是所有窗口中数据紧急度最高的区域,具有最高的优先级,因此采用逐层依次调度的策略,即规划到播放窗口的数据块依次从基础层到增强层对分层中缺失的分片进行请求下载。同一分层内,距离播放点越近的分片具有越高的请求下载优先级。

3.2 锚点窗口的设计

除了保证用户在顺序播放过程中数据块的及时性所设置的播放窗口,本文根据用户行为的特征模型设计了实现数据预取功能的锚点窗口。根据播放点离结束点的距离计算锚点窗口个数,根据锚点辐射区间范围内用户跳转累计概率,计算该锚点窗口大小。参数说明如表2所示,其中,调整参数根据分片长度和缓存能力设置。

表2 锚点窗口参数描述

锚点窗口的个数、长度计算原理如下:

(1)锚点窗口实时个数:

(2)锚点分区长度:

(3)第n个锚点辐射区间范围:

第n个锚点辐射区间对应窗口比重:

第n个锚点辐射区间锚点窗口长度:

在确定锚点窗口数目和长度后,数据的调度策略为:第1个锚点窗口是紧跟着播放窗口,根据在Weibull分布的特征,用户搜索步长落在第1个锚点窗口内的数据被搜索的概率也最大,故将其视为对播放窗口的补偿。在此窗口内数据的下载调度采取逐层的方式。

为了均衡整个流媒体视频点播系统的数据片分布,在余下锚点窗口内,采取rarest-first策略,即是将剩下窗口内的数据片根据邻居节点中拥有的拷贝数目进行从小到大排列,先下载拷贝数最少的片,如果拷贝数相等则依次优先考虑所在层数越低、距离播放越近的分片。

4 仿真实验与性能评估

本文基于OverSim仿真平台,搭建一个对等网络流媒体系统,模拟异构环境,基于等时长分片的方式[12]采用SVC可扩展视频编码技术将视频源文件分成一个可独立解码的基础层和17个依赖于低层解码的增强层,每个客户端节点根据自身入网类型需求申请可下载的SVC视频层数。

4.1 关键性能指标

本文选择2个重要参数作为分片调度算法的关键性能指标,也是此仿真实验的重要测量对象:

(1)平均接收SVC视频层数:在客户端节点使用点播服务过程中,平均接收SVC视频层数直接反映了客户端观看视频的质量,实际接收SVC视频层数越多,则获得的视频质量越好。

(2)数据块本地命中率:除了需要测量用户观看视频的质量,观看视频时流畅度也是一个重要的性能。在发生用户跳转行为时,播放点所在数据块(即将解码播放的当前数据块)若已下载,满足即时播放的条件,则将其视为数据块本地命中。数据块本地命中率越高,则视频播放越流畅。

4.2 结果分析

为了评估以上调度算法的性能,在OverSim仿真系统中,将基于用户行为特征的Anchor-对等网络SVC分片调度算法与基于逐层(Layer by Layer,LL)的分片调度算法[7]和基于权值的分片调度(Score Based Chunk Scheduling,SCS)算法[11]进行实验。

仿真实验拓扑如图1所示。

图1 仿真实验拓扑

仿真实验节点生成为4类:1个Traker,负责索引服务;5个种子节点(Seeds),其拥有视频文件的所有分片;100个Client节点,分为固网、WLAN、3G,如表3所示。在初始阶段,网络中除了Traker,还有5个以太网方式接入的种子节点。将100个Client节点逐个加入网络,每个新加入的节点从Traker服务器获取邻居节点列表,交换bitmap获取各邻居节点的分片拥有情况。

表3 3类Clients节点参数

仿真实验采用播放时长为60 min(代表长视频)的视频源,SVC编码后共18层。仿真过程中利用Weibull随机序列发生器模拟系统中各Client节点的发生跳转的用户行为,每隔1s统计各Client节点的实际播放层数,以及每次发生跳转时统计跳转播放点所在数据块是否下载。播放结束后,计算实际播放层数的平均值和数据块本地命中率。

从图2可以看出,Wired节点、WLAN节点及3G节点客户端在发生用户随机搜索操作行为(LLVCR和SCS-VCR)时的平均接收层数相比只考虑顺序播放(LL、SCS)分别降低约36%,24%及18%。说明用户随机搜索行为会对只考虑顺序播放的算法中的视频点播体验造成严重影响。

图2 Client节点平均实际接收视频层数

从图3～图5的Wired、WLAN、及3G用户节点的实验结果可以看出,与LL和SCS算法相比,在发生用户跳转行为的视频播放过程中,综合考虑异构环境和用户行为的本文算法在不同终端所统计的平均实际解码接收SVC视频层数都集中于高质量部分,如WLAN Clients节点统计结果中,使用本文算法有63.1%的用户可以观看8层及以上质量的视频,而LL和SCS算法分别为43.4%和22.9%,明显看出,本文算法在发生用户跳转的应用场景中都优于对比算法,即能使用户享受到更好的视频质量。从图6可以看出,使用本文算法在不同终端所统计的数据块本地命中率比2种对比算法都有所提高。综上,使用该算法能从整体上降低响应用户随机搜索操作所需要的时间,从而提高观看过程中的流畅度,减小服务器的负载。

图3 Wired类型节点平均接收视频层数

图4 WLAN类型节点平均接收视频层数

图5 3G类型节点平均接收视频层数

图6 节点数据块本地命中率平均值

5 结束语

本文研究异构环境下基于对等网络+SVC流媒体系统中的分片调度问题。在分析视频点播用户随机搜索行为特征的基础上,提出一种基于用户行为特征的Anchor-对等网络SVC分片调度算法。其优势在于在客户端建立播放窗口+锚点窗口的机制,并分别采取不同的调度策略,在保证数据及时性和分片分发效率的同时,解决了用户随机搜索行为对播放质量的干扰。仿真结果表明,该算法综合考虑异构环境和用户行为,保证用户观看视频时的质量和流畅度,提高用户体验,同时也减少了服务器的负载。

[1] 张春红,裘晓峰,弭 伟,等.P2P技术全面解析[M].北京:人民邮电出版社,2010.

[2] 宋俊平,张 棪,周 旭,等.基于SVC的P2P流媒体系统研究综述[J].计算机应用研究,2013,30(4): 965-970.

[3] Garcia R,PanedaXG,GarciaV,etal.Statistical Characterization of a Real Video on Demand Service:User Behavior and Streaming-media Workload Analysis[J]. Simulation Modeling Practice and Theory,2007,15(6):627-689.

[4] Choi J,Reaz A,Mukherjee B.A Survey of User Behavior in VoD Service and Bandwidth-saving Multicast Streaming Schemes[J].IEEECommunicationsonSurveys& Tutorials,2012,14(1):156-169.

[5] 朱子荣,寿志勤.P2P点播系统中资源下载算法的研究[J].计算机应用与软件,2008,25(10):175-178.

[6] Asiolo S,Ramzan N,Izquierdo E.Efficient Scalable Video Streaming over P2P Nextwork[M].Berlin, Germany:Springer,2010.

[7] Ding Yan,Liu Jiangchuan,Wang Dan,et al.Peer-to-peer Video-on-demand with Scalable Video Coding[J]. Computer Communications,2010,33(14):1589-1597.

[8] Lee T C,Liu P C,Shyu W L,et al.Live Video Streaming Using P2P and SVC[M].Berlin,Germany:Springer,2008.

[9] Abboud O,Zinner T,Pussep K,et al.On the Impact of Quality Adaptation in SVC-based P2P Video-on-demand Systems[C]//Proceedings of the 2nd Annual ACM Conference on Multimedia Systems.New York,USA: ACM Press,2011:223-232.

[10] Liu Zhengye,Shen Yanming,Shivendra S P,et al.Using Layered Video to Provide IncentivesinP2PLive Streaming[C]//Proceedings of Workshop on Peer-topeer Streaming and IP-TV.New York,USA:ACM Press,2007:311-316.

[11] 王 娟,纪其进,朱艳琴,等.基于用户行为特征的P2P视频点播系统数据预取机制[J].小微型计算机系统, 2010,31(10):2049-2053.

[12] Zhang Yan,Zhou Xu,Song Junping,et al.Time-stamped Equal Size Segmentation and Chunk Scheduling Algorithms for SVC Based P2P Streaming Systems[C]//Proceedings of the18th IEEE International Conference on Parallel and Distributed Systems.[S.l.]:IEEE Computer Society,2012: 706-707.

编辑 刘 冰

SVC Fragment Schedule Algorithm Based on User Behavior Characteristic

TANG Chaowei1,ZHANG Xi1,WANG Xuefeng1,ZHOU Xu2,SONG Junping2
(1.College of Communication Engineering,Chongqing University,Chongqing 400030,China;
2.High Performance Network Lab,Institute of Acoustics,Chinese Academy of Sciences,Beijing100190,China)

In view of the complexity of the network and terminal in heterogeneous environment,and the mutability of playback progress in the video-on-demand service that is caused by user random seeking,an Scalable Video Coding (SVC)fragment schedule algorithm based on user behavior characteristic is proposed.In the proposed algorithm,two types of windows are designed.One is playback window based on current playtime to ensure order data continues,the other one is anchor window designed with data prefetching,which is based on user random seeking following the Weibull distribution.The Layer-by-Layer(LL)schedule strategy is utilized in playback window and the first anchor window to ensure the timeliness of data,and the rarest-first strategy is used in the other anchor windows to balance the fragment distribution of the whole system.Simulation results in OverSim show that,compared with current LL schedule algorithm and weighted schedule algorithm,the proposed algorithm can improve the fragment scheduling performance,shortens the response time delay,reduces the server load,and improves the quality and fluency of the user in watching video.

heterogeneous environment;user behavior;fragment schedule;anchor window;Peer-to-Peer Network (PPN);Scalable Video Coding(SVC)

唐朝伟,张 希,王雪锋,等.基于用户行为特征的SVC分片调度算法[J].计算机工程,2015, 41(2):248-252,257.

英文引用格式:Tang Chaowei,Zhang Xi,Wang Xuefeng,et al.SVC Fragment Schedule Algorithm Based on User Behavior Characteristic[J].Computer Engineering,2015,41(2):248-252,257.

1000-3428(2015)02-0248-05

:A

:TP301.6

10.3969/j.issn.1000-3428.2015.02.047

国家科技重大专项基金资助项目(2011ZX03005-004-02);国家自然科学青年基金资助项目(61102076)。

唐朝伟(1966-),男,教授、博士后,主研方向:网络多媒体技术;张 希(通讯作者)、王雪锋,硕士;周 旭,副研究员、博士;宋俊平,博士。

2014-03-05

:2014-04-04E-mail:zhangxi1989xi@163.com