（计算机软件与理论专业论文）下一代移动通信网络中可伸缩视频多播研究.pdf

摘要 摘要 近几年来，移动通信网络发展迅速，下一代的无线通信网( u 卫，l t e a d v a n c e d ， w i 删8 0 2 1 6 ) 将为终端用户提供更高的带宽和数据传输速率，这使得视频业 务在移动通信网络中的传输成为可能，其中主要包括一些有严格时延、错误率限 制的实时视频多播业务，例如数字视频直播、视频会议、在线游戏和i p t v 等等。 对于移动通信网络中的视频多播，最主要的两项关键技术是可伸缩视频编码 s v c 和自适应调制编码a m c 。基于a m c 的可伸缩视频多播所要解决的关键问 题就是在系统有限的资源限制下，如何为可伸缩视频的每个视频层选择合适的 m c s 并分配资源以使得多播组中的用户得到最好的视频服务质量。当系统中存 在多个需要进行多播的可伸缩视频流时，应该如何对各个视频流进行资源分配以 及如何为视频流各个层选择m c s ，来使系统达到最好的性能。基于此，本文针 对可伸缩视频的多播机制进行研究，主要工作包括以下三个方面： ( 1 ) 提出了可伸缩视频多播的基础算法和扩展算法。本文首先对基于自适应 调制编码的可伸缩视频多播问题进行分析，建立了该问题的基础模型，证明了该 问题为n p 难解问题，提出了用于解决该问题的伪多项式时间的最优基础算法， 仿真实验证明该算法的性能比同类的一些贪心算法和启发式算法优秀，能够使系 统达到最优的服务质量。然后，对基础模型进行了扩展，在扩展模型的基础上提 出了计算复杂度更低的可伸缩视频多播扩展算法，仿真实验证明该扩展算法保持 了最优的性能，同时提高了算法运行的速度。最后，在基础模型的基础上加入了 视频流覆盖策略的需求，对基础模型进行了修正，使得基站可以针对各个视频流 配置不同的覆盖策略，提出了最优的可伸缩视频多播扩展算法，仿真实验证明该 算法在保持视频流覆盖要求的同时，能够使系统达到最优的性能。 ( 2 ) 提出了基于跨层资源分配的可伸缩视频多播最优算法和近似算法。为了 进一步的节省带宽资源，提高网络带宽的利用率，本文提出了跨层资源分配的概 念，允许系统对使用相同调制编码方式进行传输的多个视频层进行联合资源分配。 然后在可伸缩视频多播基础模型的基础上，建立了基于跨层资源分配的可伸缩视 频多播系统模型，证明了该问题为n p 难解问题，然后提出了用于解决该问题的 伪多项式时间的最优算法和全多项式时间的近似算法。仿真实验证明基于跨层资 源分配的最优算法比基础算法更加优秀，进一步提高了系统性能，而近似算法在 一些参数配置下也能够使系统保持较好的性能，同时也大大缩短了算法的运行时 间。 ( 3 ) 提出了基于混合f e c a r q 的可伸缩视频多播算法。为了提高视频传输 的可靠性，本文将混合f e c a r q 机制引入到可伸缩视频的多播中，为了防止多 摘要 播组中用户反馈信息过多，本文提出了基于单用户反馈的可伸缩视频多播机制和 基于组代表用户反馈的可伸缩视频多播机制。在单用户反馈机制中，多播组中选 择一个代表用户进行信息反馈。本文对该机制建立了数学模型，并提出了基于 f e 咄q 的可伸缩视频多播最优算法和快速的基于贪心策略的算法。在组代表 用户反馈机制中，多播组的用户按照信道状况分为多个组，然后在每个组中选择 一个组代表用户进行信息反馈。本文对该机制建立了数学模型，并且提出了一个 快速的基于贪心策略的算法。 关键词：可伸缩视频编码自适应调制编码多载波系统多播资源调度 混合f e c a r q a b s t r a c t a bs t r a c t r e c e n t l y , m o b i l ec o m m u n i c a t i o nn e t w o r k s a t ed e v e l o p i n gv e r yf a s t n e x t g e n e r a t i o n m o b i l ec o m m u n i c a t i o n n e t w o r k s ( l a x ，l t e a d v a n c e d ， a n d w i m a x 8 0 2 t 6 ) a r ef e a t u r e dw i t hh i g hd a t ar a t ea n di m p r o v e dc o v e r a g e ，w h i c hw i l l e n a b l er e a l t i m ev i d e om u l t i c a s ta n db r o a d c a s ts e r v i c e sw i t ht h er e q u i r e m e n t so fs h o r t d e l a ya n dl o we r r o rr a t e ，i n c l u d i n gl i v ev i d e os t r e a m i n g , v i d e oc o n f e r e n c e ，o n l i n e g a m e s ，a n d 叭 s c a l a b l ev i d e oc o d i n g ( s v c ) a n da d a p t i v em o d u l a t i o na n dc o d i n g ( a m c ) a r e t w ok e yt e c h n i q u e sf o rv i d e om u l t i c a s ti nm o b i l ec o m m u n i c a t i o nn e t w o r k s i ti s i m p o r t a n tt oc h o o s ea p p r o p r i a t em c s f o re a c hv i d e ol a y e ra n dt od e t e r m i n et h er i g h t i e s o u r c ea l l o c a t i o na m o n gm u l t i p l ev i d e os e s s i o n s t h e r e f o r e ，t h ek e yi s s u ef o rt h i s s c a l a b l ev i d e om u l t i c a s t i n gp r o b l e mi sh o wt oa l l o c a t et h er a d i or e s o u r c e st om u l t i p l e m u l t i c a s tv i d e os e s s i o n sa n dt om u l t i p l es v cl a y e r sw i t h i nas e s s i o n ，a n dh o wt o a s s i g nm c s f o re a c ha l l o c a t e dv i d e ol a y e r , i no r d e rt oa c h i e v et h eb e s tv i d e os e r v i c e f o ra ut h eu s e r si nt h em u l t i c a s ts y s t e m t h ed i s s e r t a t i o nf o c u s e so nt h er e s e a r c ho f s c a l a b l ev i d e om u l t i c a s tm e c h a n i s m sa n dc o n s i s t so ft h ef o l l o w i n gt h r e ea s p e c t s ： ( 1 ) r e s e a r c ho ns c a l a b l ev i d e om u l t i c a s tw i t ha m c f i r s tt h eb a s i cm o d e lf o r s c a l a b l em u l t i c a s t i n gp r o b l e mi sb u i l ta n dt h ep r o b l e mi sp r o v e dt ob en p h a r d a p s e u d o p o l y n o m i a lb a s i ca l g o r i t h mt h a tf i n d st h eo p t i m a lt o t a ls y s t e mu t i l i t yi st h e n p r o p o s e dt os o l v et h i sp r o b l e m s i m u l a t i o nr e s u l t ss h o wt h a tt h ep r o p o s e db a s i c a l g o r i t h mp e r f o r m sb e t t e rt h a nag r e e d ya l g o r i t h ma n d ah e u r i s t i ca l g o r i t h m t h e n ，t h e b a s i cm o d e li se x t e n d e da n da n o t h e rp s e u d o - p o l y n o m i a la l g o r i t h mt h a ta l s of i n d st h e o p t i m a lt o t a ls y s t e mu t i l i t yb u tr u n sf a s t e r t h a nt h eb a s i ca l g o r i t h mi sp r o p o s e d s i m u l a t i o nr e s u l t ss h o wt h a tt h i sa l g o r i t h mp e r f o r m st h es a m ea st h eb a s i ca l g o r i t h m b u tw i t hl o w e rr u n n i n gt i m e f i n a l l y , t h eb a s i cm o d e li se x t e n d e dw i t hs u p p o r to f c o n f i g u r a b l ef u l ls e s s i o nc o v e r a g er e q u i r e m e n t i nt h i se x t e n d e dm o d e l ，t h eb a s e s t a t i o nc a nc o n f i g u r ew h i c hv i d e os e s s i o ns h o u l db et r a n s m i t t e dw i t hs u p p o r to ff u l l s e s s i o nc o v e r a g e ap s e u d o p o l y n o m i a la l g o r i t h mi sp r o p o s e dt os o l v et h en e w p r o b l e m s i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h mc a l l a c h i e v et h eb e s ts y s t e m p e r f o r m a n c ew i t hs u p p o r to f f u l ls e s s i o nc o v e r a g ef o rs o m ev i d e os e s s i o n s ( 2 ) r e s e a r c ho ns c a l a b l ev i d e om u l t i c a s tw i t hj o i n tl a y e rr e s o u r c ea l l o c a t i o n i n o r d e rt o i m p r o v et h eb a n d w i d t hu t i l i z a t i o nr a t i o ，t h ec o n c e p to fj o i n tl a y e rr e s o u r c e a l l o c a t i o ni sb r o u g h ti n t ot h eb a s i cm o d e l ，w h i c ha l l o w st h eb a s es t a t i o nt oj o i n t l y i i i a b s t r a c t a l l o c a t er e s o u r c e st om u l t i p l ev i d e ol a y e r st h a ta r ea s s i g n e dt h es a m em c s t h i sn e w p r o b l e m i sf o r m u l a t e da n dp r o v e dt ob en p - h a r d t h e nap s e u d o - p o l y n o m i a l a l g o r i t h mt h a tf i n d st h eo p t i m a lt o t a ls y s t e mu t i l i t yi sd e v e l o p e d t or e d u c et h e c o m p l e x i t yo ft h ea l g o r i t h m ，f u l l yp o l y n o m i a lt i m ea p p r o x i m a t i o ns c h e m e ( f p t a s ) f o rt h i sp r o b l e mi sa l s op r o p o s e d s i m u l a t i o nr e s u l t ss h o wt h a tt h eo p t i m a la l g o r i t h m o f f e r ss i g n i f i c a n ti m p r o v e m e n to ns y s t e mu t i l i t yo v e rt h eb a s i co p t i m a la l g o r i t h m w h i c hd o e sn o ts u p p o r tj o i n tl a y e rr e s o u r c ea l l o c a t i o n t h ep r o p o s e da p p r o x i m a t i o n a l g o r i t h mp r o v i d e sc o n t r o l l a b l et r a d e o f fb e t w e e np e r f o r m a n c ea n dc o m p u t a t i o n a l c o m p l e x i t ya n di t c a na c h i e v eg o o dp e r f o r m a n c ea n dl o wr u n n i n gt i m ew i t h a p p r o p r i a t e l yc h o s e np a r a m e t e r s ( 3 ) r e s e a r c ho nr e l i a b l es c a l a b l ev i d e om u l t i c a s tw i t hh y b r i df e c a r q i no r d e r t oi m p r o v et h er e l i a b i l i t yf o rt h ev i d e om u l t i c a s t ，h y b r i df e c a r qe r r o rc o r r e c t i o n t e c h n i q u ei se m p l o y e di nt h es c a l a b l ev i d e om u l t i c a s tm e c h a n i s m t oc o n t r o lt h e a m o u n to ft h ef e e d b a c kp a c k e t sf r o mt h eu s e r si nt h em u l t i c a s tg r o u p ，t w os c h e m e si s d e v e l o p e d ：s i n g l er e p r e s e n t a t i o n u s e rf e e d b a c ka n dg r o u pr e p r e s e n t a t i o nu s e r f e e d b a c k i nt h es i n g l er e p r e s e n t a t i o nu s e f e e d b a c ks c h e m e ，o n l yo n eu s e ri nt h e m u l t i c a s tg r o u pi ss e l e c t e dt os e n dt h ef e e d b a c kp a c k e t s b o t ha no p t i m a la l g o r i t h m a n daf a s tg r e e d ya l g o r i t h ma r ep r o p o s e dt os o l v et h i sp r o b l e m i nt h eg r o u p r e p r e s e n t a t i o nu s e rf e e d b a c ks c h e m e ，u s e r sa r eg r o u p e di n t os e v e r a ls u b - g r o u p sb a s e d o nt h e i rc h a n n e lc o n d i t i o n s e a c hs u b g r o u ps e l e c t sar e p r e s e n t a t i o nu s e rt or e t u r nt h e f e e d b a c kp a c k e t s af a s tg r e e d ya l g o r i t h mi sp r o p o s e dt os o l v et h i sp r o b l e m k e yw o r d s ：s c a l a b l ev i d e oc o d i n g ，a d a p t i v em o d u l a t i o na n dc o d i n g ，m u l t i - c a r r i e r s y s t e m ，m u l t i c a s t ，r e s o u r c es c h e d u l i n g ，h y b r i df f _ , c a r q i v 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：拢签字日期：丝丝! ：兰2 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 白么开口保密(年) 作者签名： 导师签名 第1 章绪论 1 1 研究背景和意义 第1 章绪论 近几年来，移动通信网络发展迅速，在3 g 移动通信网普及的同时，下一 代的无线通信网( u e ，l t e a d v a n c e d ，w i m a x ) 也在迅速的发展中，将为终 端用户提供更高的带宽和数据传输速率。国际电信联盟( 丌u ) 提出4 g 通信技术 应该为高速移动设备提供高达1 0 0m b p s 的数据传输速率峰值，为低速移动设备 提供高达1g b p s 的数据传输速率峰值( c o s t a ，2 0 0 7 ) ，这样的高带宽使得在移动 通信网络中进行实时的视频业务传输成为可能，其中包括一些有严格时延、错 误率限制的实时视频业务，例如数字视频直播、v o d 、视频会议、游戏、v o i p 、 i p l v 等等( r e t n a s o t h i ee ta 1 2 0 0 6 ；s h ee ta 1 2 0 0 7 ) 。 然而，在移动通信网络中，传输信道带宽资源由网络中的用户所共享，而 且用户的数量在不断的增加。无线网络中的一些视频业务可能会占用很多的带 宽资源并且需要严格的时延限制。所以，通信网络中资源分配的方法和策略非 常重要，将会影响用户的视频服务质量。当多个用户同时访问一个视频资源时 ( 例如，多个用户同时使用手机观看一个体育比赛直播或者热门新闻) ，无线多 播成为视频内容传输的有效方法。下一代的移动通信网络，诸如 w i m a x 8 0 2 1 6 ( i e e e ，2 0 0 8 ) 和3 g p p l t e ( 3 g p p , 2 0 0 6 ) ，都增加了基站对数据进 行多播的能力。基站只需要使用某些信道对视频资源进行广播，然后通知多播 组的用户在这些信道上接收数据，这样就很大的节省了信道带宽资源。所以， 如何利用有限的频谱资源对实时视频进行多播以达到最大的终端用户满意度成 为当今的一个核心研究问题。 为了在传输中节省带宽和提高网络吞吐量，自适应调制编码a m c ( a d a p t i v em o d u l a t i o na n dc o d i n g ) 技术被广泛的应用于移动通信网络中。a m c 可以根据无线信道变化选择合适的调制和编码方式，根据用户瞬时信道质量状 况和目前资源选择最合适的链路调制和编码方式，使用户达到尽量高的数据吞 吐率。当用户的信道状况较好时( 如靠近基站或存在视距链路) ，用户数据发送 可以采用高速率的信道调制和编码方式m c s ( m o d u l a t i o na n dc o d i n gs c h e m e ) ， 例如：6 4 q a m 和3 4 编码速率，从而得到高的峰值速率；而当用户信道状况较 差时( 如位于小区边缘或者信道深衰落) ，基站则选取低速率的m c s ，例如：q p s k 和1 4 编码速率，来保证通信质量。然而，对于视频多播，如果多播组中用户 的信道状况各不相同，基站就会选取一个最可靠的低速率m c s 以保证最差信道 1 第1 章绪论 状况用户的通信质量。这样就导致视频多播的速率和视频质量被那些较差信道 状况的用户所限制。 为了解决这样的问题，人们在移动通信网络中引入了可伸缩视频编码国际 标准s v c ( s c a l a b l ev i d e oc o d i n g ) 。s v c 是h 2 6 4 a v c 标准的可伸缩性扩展档次 ( f r o ta n di s o i e cj t c1 ，2 0 0 7 ) ，它可以根据需求将视频流分割为一个基础层 和多个增强层，基础层为用户提供最基本的视频质量、帧率和分辨率，而增强 层则对视频质量进行完善。终端用户接收到的s v c 层数越多，得到的视频质量 越高。当在移动通信网中对s v c 编码的视频流进行多播时，可以针对不同的 s v c 层采用不同的m c s ，基础层和低级增强层使用低速率的m c s 以使得信道 状况较差的用户获得基本的视频服务，而对于高端增强层使用高速率m c s 以使 得信道状况好的用户得到更好的视频服务。当系统中存在对多个可伸缩视频流 进行多播时，基站需要在带宽资源的限制下选择合适的算法来根据各个视频流 的特点进行资源分配，并且要对视频流的各个视频层选择合适的m c s 进行传输。 由于移动通信网中无线信道的不稳定性，无线数据可靠多播研究渐渐进入 人们的视线，成为当今的研究热点之一。合适的数据纠错机制可以避免数据的 反复传输，有效的节省带宽资源。在通信网中比较常用的纠错机制是应用层前 向纠错机制f e c 、自动重传请求机制a r q 以及混合的f e c a r q 机制。而用于 多播的纠错机制主要有两种：f e c 和混合f e c a r q 。基于f e c 机制的多播中， 每个多播数据块将被编码为j v 个数据包，多播组中的每个用户必须接收到 k ( o k ) 个以上的数据包才能正确解码该数据块( l u b y e ta 1 2 0 0 2 b ) 。基于 混合f e c a r q 机制的多播( a d a m s o n e ta 1 2 0 0 4 b ) 中，一个数据块仍然通过f e c 编码为个数据包，但这个数据块的发送将被分为多个轮，如果一个接收者在 一轮结束时没有接收到k ( 0 k f ，1 m m ，0 t t 时的所有取值，下一步需要得到一个递归式来计算u ( 1 , m , o 在1 z l ，1 m m ，0 t t 时的所有值。在“亿力的场景中，视频层z 使用m c sm 进行调制编码，对于第z 视频层以上的资源约束为t 。那么，根据定理( 3 3 ) ，可 以根据第l + 1 视频层的2 种情况来分别计算u ( 1 , m , o 的值，如下所示： i 第“j 视频层不被传输。在这种情况下，第，视频层是被传输的最高的 1 9 第3 章可伸缩视频多播机制设计 层，集合m 中的所有用户都将接收到最多z 个视频层。所以，m 集合 中所有用户的效用值为u ( t ，m ，) = e ( i m ) p ( f ，z ) 。 i i 第1 + 1 视频层传输时使用的m c s 为m i n 。在这种情况下，既然第l + 1 视频层需要使用m c sm 进行调制编码，那么资源粒子数目必须能够保 证第1 + 1 视频层使用m c sm 7 进行调制编码，即，t 瓢+ 1m ，。为了计 算u ( 1 , m , o ，首先将用户集合m 分为两个不相交的子集：和m 一m ， 如图3 2 所示。对于在集合一n m ( 当m = m 时该集合为空集) 中 的用户f ，它可以解码m c sm ，但是无法解码m c s “。所以用户可以 接收到的有效视频层数目为z ，它的效用值为地f 。对于在集合m ，中的 用户，它们所能得到的最大的效用值为t ( - i - 1 ，m ，t t l + l , m ，) ，这个值 是已知的，因为它是在递归过程中前面的步骤所得到的结果。通过以上 的分解，可以得到，当第l + 1 视频层使用m c s 仇7 进行调制编码时，m 中 所有用户的总效用值为让( z ，m ，m ，力= 乱( z + 1 ，m ，c t l + l , m t ) + f n m n 。，p f ，l 。由于第l + 1 视频层所使用的m c sm 可以是从m 到m 的任何一个值，所以u ( 1 , m , o 应该是在m m m ，气+ 1 m ，t 条件约束 下的u 7 ( 2 ，m ，m 7 ，t ) 的最大值，最p u ( 1 ，m ，t ) = m a x ，l ，m ) u ( 1 ，仉m 7 ，d ， 其中q ( f ，n ，d = m 7 ：7 n m 7 m ，t l + l , m p t ) 。 第上层 籀7 + l 层 第，层 基础层 可伸缩视频流 图3 2 第f + 1 视频层使用m c st n 用户的效用值 综合以上两种情况的讨论，可以得到u ( t , m , o 的递归式，如下所示： “( lm ，d = m a x ( e j m 晰，l ，m a x m ，q ( 1 仇，c ) “7 ( z ，m ，m 7 ，c ) ) ( 3 6 ) 其中，乱( f ，m ，) = 札( z + 1 ，m 7 ，t t l + 1 ，m ，) + e i m 一m ，心f ， 第3 章可伸缩视频多播机制设计 q ( l7 7 t ，t ) = ( m ：m m m ，t + l ，m ，t ) 。表3 1 总结了辅助函数“隔砂的 递推关系式。 表3 1u ( t , m , o 的递推关系式 初始值： u ( l ，m ，) = 罗i e n m 1 i lv1 优m ，0 t t u ( t ，r e , t ) = m a x ( 诞h 研q , l ，m a x m ，o ( 1 ，t ，l ，0u ( ，m ，m ，) ) v1 l l ，1 m m ，0 t t 递归式： 其中，l 工( 1 ，m , m ，0 = l ( 王+ 1 ，m 7 ，t f + 1 ，m ，) 4 罗1 e n m 一m ，p 啦 q ( t ，仉t ) = ( m ：仇m m ，q + 1 m ，s ) 。 通过公式( 3 5 ) 初始值的计算和公式( 3 6 ) 递归的过程，最终可以得到当 1 i l ，1 m m ，0 t t 时u c t ，m ，t ) 的所有取值。由于视频流的基 层( 第一层) 可以使用m c si m 进行调制编码，所以可以得到视频流的 最大效用值u + 应该是在- f 1 m t 限制条件下当1 m m m , o ，讯，丁一 t 1 m ) 的最大值，即： 扎+ = m a x ( 乱( 1 ，m ，t q ，m ) ：1 m m ，l 1 ，m 丁) ( 3 7 ) 需要说明的是，当对一个空集求最大值时，本文将其设置为0 。 另外，为了配合下一节中的视频流资源分配算法，需要计算对于一个视频 流在资源约束为t 的情况下所能达到的最大效用值1 c l ( ) ，即： 缸( ) = m a x ( u ( 1 ，m ，t r 1 j 讥) ：1 m m ，t 1 m t ) ( 3 8 ) 下面讨论本节的视频层m c s 选择算法的时间复杂度。在递归过程之前，胁 和f e m 地f 的值可以在d ( ，l ) 的时间内同时进行计算，其中，是视频流中用户的 数目。对于递归过程的最坏情况，需要计算当1 z z i ，1 m m ，1 冬t 丁时距传砂的所有值。根据公式( 3 6 ) ，递归过程的每一步的计算复杂度为d ( m ) ， 所以整个递归过程的最差计算复杂度为d ( l m 2 t ) 。所以，对于单个视频流m c s 选择算法的时间复杂度为o ( j l + l m 2 n 。 3 2 2 i2 视频流资源分配 本节主要介绍用于解决视频流间资源分配问题的动态规划算法。算法的目 标是通过合理的对各个视频流进行资源分配来得到如公式( 3 3 ) 所示的最大系统 效用值。假定丁0 ) 表示分配给视频流s 的资源粒子数目，0 t 0 ) t 。本节使 用两步分解技术( l i ue ta 1 2 0 0 3 ) ，利用上一节视频层m c s 选择算法的运行结果 来最优化视频流间的资源分配。 上一节已经得到了所有霞吲( 亡) ( 1 s s0 t n 的值，表示视频流s 在资 源约束为t 的条件下所能达到的最大的效用值。根据u ue ta 1 ( 2 0 0 3 ) 提出的引理 2 1 第3 章可伸缩视频多播机制设计 h i1 ，公式( 3 3 ) 所示的系统效用值优化问题可以等价的表示为： m a x u = ；1 ( 洲( r ( s ) ) ) ( 3 9 ) 约束条件为：i 嘉1 口( s ) ) t( 3 1 0 ) 本节依然采用动态规划算法来解决视频流的资源分配问题。首先定义一个 辅助函数p “f ) ，表示视频流l s 在资源约束为t 的条件下所能达到的最大效用 值，如图3 3 所示。目的是要递归的从s = 1 n s = s 计算v ( s ，订的值，而最终的 结果p r ) 就是系统中s 个视频流能达到的最大的效用值，而此时各个视频流 的资源分配方案就是优化问题( 3 3 1 的虽优解决方案。 桃颧流： p 0 ，) j? s 一、厂 视频漉i s 在资i | _ ；f 约求为时的最人效川值 图3 3 辅助函数v ( $ ) 的定义 首先，需要计算递归的初始值口( 1 ，0 。在v ( 1 ，t ) 所代表的场景中，视频流1 的 资源约束为。根据视频层m c s 分配算法的结果，可以得到： u ( 1 ，亡) = f i 1 l ( ) ，0 t t ( 3 1 1 ) 在得到初始值之后，需要得n u ( s ，) 的递归式。假定在递归的过程中需要计 算v ( s ，) ( 1 ss 印。之前的递归过程已经得到y v ( s ，亡) 在1 s s ，0 t 丁时的所有值。根据u ue la 1 ( 2 0 0 3 ) 提出的引理1 1 1 1 ，视频流s 的效用值是独立 于其它视频流的资源分配策略，而仅仅依赖于它自身的资源约束。假定分配给 视频流s 的资源粒子数目为+ ( o r 曲，那么视频流j 叶的最大效用值可以 表示为豇m ( ) + v ( s 一1 t r ) ，如图3 4 所示。所以，只要考虑所有t 的可能 取值，就可以得n v ( s ，c ) 的值。于是可以得蛩j v ( s 0 的递归式，如下所示： v ( s ，t ) = m a x 一：o ( 矗m ( ) + f 0 1 ，t t7 ) ) 1 1 时，同贪心算法和启发式算法相比，最优算法将用户平 均效用值分别提升了0 1 5 加2 4 和o 1 0 0 6 9 。与之相应，折算到用户的平均速 率，与贪心算法和启发式算法相比分别提升了1 6 一2 7 和1 0 5 。9 9 ，如图 3 9 所示。当s = 1 时，系统资源足够使用最可靠的m c s 对一个视频流进行传输， 所以三个算法都达到了最优的系统效用值。在两个图中可以看到随着s 增加，三 个算法的系统效用值和平均用户速率都会下降，这是因为当系统中有更多的视 2 9 第3 章可伸缩视频多插机制设计 频流需要传输时，单个视频流相对得到更少的资源粒子数目，所以能够传输的 视频层数目也随之减少。 另外，本节也比较了三个算法中不同s n r 值的用户的吞吐量，以观察算法 对不同信道状况的用户服务质量的影响。选择的场景中有6 个视频流需要传输， 扩展视频层可分配的资源粒子数目为1 6 0 。首先将2 0 0 个用户按照s n r 值从小 到大的顺序进行排序，然后将它们按顺序分为1 0 组。对每个组中的2 0 个用户t 计算三个算法中这些用户的平均接收速率。图31 0 给出了结果，可以看到最优 算法提升了除第一组之外的所有组的用户平均速率尤其是对于信道状况较好 的第6 1 0 组。而对信道状况差的第1 组用户造成了轻微的性能损失。 32 33 标准视频测试流 图3 1 1 各个视频流的平均用户p s n r 值 在这个仿真场景中，使用5 个标准视频测试流作为视频输入。首先单独使 用各个视频流作为视频输入，来衡量三个算法的单视频流中视频层m c s 分配算 法的性能。因为5 个测试视频的数据速率相差很大所以需要针对它们选择不 同的可分配资源粒子数目n 分别为9 6 ( m o b i l e ) ，9 6f h a r b o u 0 ，6 4 ( c r e w ) 3 2 ( f o r e m a n ) 和1 6 ( m o t h e r - a n d d a u g h t e r ) 。在该场景中的r 与上一节不同，是指 视频流中所有视频层的可分配资源粒子数目，不仅包括增强层，也包括基层。 从图31 1 可以看出，最优算法与贪心算法和启发式算法相比，将用户的平均 p s n r 分别提升了33d b 和4 1d b ，也就意味着提供了更好的视频服务质量。 一izr； 8 2 芷 z 跫 正 匮 曰 洚 畲 已 芷 z v l 仅 匠 霸 舟 第3 章可伸缩视频多播机制设计 资源粒予数目 图3 1 2 平均用户p s n r 值随资源粒子数的变化 图3 1 3 不同s n r 的用户组的平均用户p s n r 值 进而将5 个测试视频流同时作为视频输入，并且改变系统可分配资源粒子 3 1 第3 章可伸缩视频多播机制设计 数目丁，来比较三个算法的性能。丁从o 变化到4 9 6 ，间隔值为1 6 。图3 1 2 三个 算法中的用户平均p s n r 值。可以看到，最优算法比启发式算法取得了更好的 性能，平均的p s n r 提升值为7 3d b 每用户，最大的p s n r 提升值为1 4 7d b 。 随着可分配资源粒子数目的减少，最优算法的性能得到了更大的提升，直到资 源粒子数目降为o 。当系统中没有足够的资源粒子来对所有视频流的基层进行 调制编码时，贪心算法将不能运行，所以可以看到在图3 。1 2 中当t 2 0 8 时贪心 算法没有数据产生。而当资源充足时( 丁2 0 8 ) ，最优算法也比贪心算法取得了 更好的性能，将平均的p s n r 值提升了5 2d b 。 最后，同上一节相似，本节也比较了三个算法中不同s n r 值的用户的吞吐 量，以观察算法对不同信道状况的用户服务质量的影响。选择的场景中包括全 部5 个视频测试流，视频层可分配的资源粒子数目为3 2 0 。依然将2 0 0 个用户 按照s n r 值从d , n 大的顺序进行排序，然后将它们按顺序分为1 0 组。对每个 组中的2 0 个用户，计算三个算法中这些用户的平均用户p s n r 。图3 1 3 给出了 结果，可以看到对于贪心算法和启发式算法，每个用户组得到的平均p s n r 值 大致相同：而对于最优算法，信道状况好的用户组取得了很大的性能提升。 3 。3 扩展算法设计：更高效的m c s 分配策略 3 3 1 扩展模型 为了提出更高效的m c s 分配算法，本节将在第3 2 1 节的基础上，对可伸 缩视频多播的系统模型从另外一个角度进行数学描述。 本节描述的模型将沿用第3 2 1 节所使用的部分符号标识。但在已有标识的 基础上，增加了一些新的标志量，用于更清晰和高效的描述多播系统模型。在 基本模型中，使用表示系统中所有用户的集合， m 表示可以解码m c s 仇的 用户集合。在本节的扩展模型中，增加一个标识砜，用来表示能够解码m c s m 但是无法解码m c sm + 1 的用户集合。如果一个用户可以解码m c sm ，那 么该用户也能够解码所有索引低于m 的m c s ，所以可以得到m = u 纂，- m 砜，。 假定在最终的多播方案中，对第 视频层进行调制编码的m c s 为m ( f ) 。如 果第z 视频层被指定为不被传输，将设置m ( 0 = + ，相应的设置尺= + 和 n o o = 咖。于是可以将系统的资源约束表示为： l _ 1 - t l ，m ( 0 t ( 3 1 5 ) 如在基本模型中的描述，可伸缩视频的各个层存在依赖性，任何一层没有 被用户正确解码，那么所有这一层以上的视频层对用户都是无效的，尽管用户 3 2 第3 章可伸缩视频多播机制设计 可能接收到并正确解码。也就是说，只有所有的第一到第1 个视频层被用户接收 并正确解码后，视频层+ 1 才对该用户是有效的。对于在