基于网络编码的移动D2D视频缓存网络内容布设方法研究.pdf

第 卷 第期 年月金 陵 科 技 学 院 学 报J OUR NA LO FJ I N L I NGI N S T I TUT EO FT E CHNO L O G YV o l ,N o J u n e,D O I:/j c n k i /n 基于网络编码的移动D D视频缓存网络内容布设方法研究胡夏芸,李景仙,胡勇,夏欣然,殷俊(金陵科技学院软件工程学院,江苏南京 ;南京邮电大学物联网学院,江苏南京 )摘要:为了进一步提高移动D D视频缓存网络用户设备的缓存效用,建立了用户设备缓存内容与缓存收益的数学模型,分析了随机缓存策略和基于网络编码的随机缓存策略的理论收益,提出了一种基于网络编码的截断式内容缓存方法N C C F R C.多种测试条件下的数值实验结果表明,N C C F R C方法较已有的随机缓存和截断式缓存等经典方法,内容命中率和适应性均有所提升.关键词:移动D D;视频缓存网络;网络编码;内容布设中图分类号:TN 文献标识码:A文章编号:X()收稿日期:基金项目:江苏高校“大学素质教育与数字化课程建设”专项课题(J D K T )作者简介:胡夏芸(),女,安徽黄山人,实验师,硕士,主要从事智能物联网技术研究.R e s e a r c ho nC o n t e n tP l a c e m e n tM e t h o df o rM o b i l eD DV i d e oC a c h i n gN e t w o r k sB a s e do nN e t w o r kC o d i n gHUX i a y u n,L I J i n g x i a n,HUY o n g,X I AX i n r a n,Y I NJ u n(J i n l i n gI n s t i t u t eo fT e c h n o l o g y,N a n j i n g ,C h i n a;N a n j i n gU n i v e r s i t yo fP o s t sa n dT e l e c o mm u n i c a t i o n s,N a n j i n g ,C h i n a)A b s t r a c t:A i m i n ga t i m p r o v i n gt h ec a c h i n ge f f i c i e n c yo fu s e rd e v i c e s i nm o b i l ed e v i c e t o d e v i c e(D D)v i d e oc a c h i n gn e t w o r k s,am a t h e m a t i c a lm o d e lo fc a c h i n gc o n t e n ta n dc a c h i n gb e n e f i t so nu s e rd e v i c e s i se s t a b l i s h e d T h e t h e o r e t i c a lb e n e f i t so f t h er a n d o mc a c h i n gs t r a t e g ya n dt h en e t w o r kc o d i n gb a s e dr a n d o mc a c h i n gs t r a t e g ya r ea n a l y z e d An e t w o r kc o d i n gb a s e dc u t o f fc o n t e n t c a c h i n gm e t h o d,i e N C C F R C,i sp r o p o s e d T h en u m e r i c a l e x p e r i m e n t a l r e s u l t su n d e rv a r i o u st e s tc o n d i t i o n ss h o wt h eN C C F R Cs t r a t e g yh a sg r e a t i m p r o v e m e n t si nc a c h eh i tr a t ea n da d a p t a b i l i t yc o m p a r e dw i t ht h ee x i s t i n gc l a s s i c a l s t r a t e g i e s s u c ha s t h e r a n d o ma n d t h ec u t o f f r a n d o mc a c h i n gs t r a t e g i e s K e yw o r d s:m o b i l eD D;v i d e oc a c h i n gn e t w o r k s;n e t w o r kc o d i n g;c o n t e n tp l a c e m e n t随着移动互联网的快速普及,用户通过移动设备观看视频已成为工作、学习和生活娱乐的常见方式.在传统的中心化移动蜂窝网络架构中,视频内容往往部署在远离用户的远程数据中心里.当用户发出视频请求时,数据需通过核心网进行数据传输,这不可避免地产生了加载时延;并且在人员密集地区,大量用户的视频传输需求可能超出核心网络的带宽承载能力,尤其是在出行集中时段,会出现视频缓冲和卡顿现象,进一步削弱了网络的用户服务质量.移动视频缓存网络是一种新型的边缘内容分发网络,一方面金陵科技学院学报第 卷允许视频内容直接存储在更靠近请求用户的边缘设备如小基站、用户设备上,另一方面允许用户通过移动终端直传通信(d e v i c e t o d e v i c e,D D)进行内容共享,可为用户提供更流畅、更低价的视频内容服务.由于用户设备存储空间有限,缓存收益成为决定移动D D视频缓存网络服务质量的核心指标.为了提高移动视频缓存网络用户设备存储空间的利用率,提高缓存收益,研究人员开展了多类缓存内容布设方法研究.文献 基于用户内容请求服从相互独立的齐次泊松点过程,将用户设备内容布设问题转化为平均缓存命中率最大化问题,提出了内容的分段式随机缓存策略(s e g m e n t b a s e dr a n d o mc a c h i n gs t r a t e g y,S B R C).文献 考虑了视频内容流行度对缓存内容收益的影响,提出了截断式随机缓存策略(c u t o f fr a n d o mc a c h i n gs t r a t e g y,C F R C),用户设备优先存储流行度较高的视频文件,摒弃流行度较低的,从而避免“长尾效应”,提高缓存命中率.在文献 的基础上,文献 考虑了不同设备缓存空间场景下的内容缓存布设问题,提出了联合内容请求命中率和设备坐标梯度的缓存布设方法.为了最大化缓存收益,后续的研究一方面围绕缓存内容分享的过程展开,另一方面围绕类似兴趣用户的更精确分簇和兴趣内容的更精准预测展开.例如,文献 针对网络中由用户设备异构引起的内容发现和有效控制困难,提出了一种层次化的移动边缘缓存网络内容分享系统架构,以更大限度地提高内容分享效率.文献 基于加权分簇方法对用户兴趣进行分簇,并且对内容进行缓存时以簇为单位进行,从而提高簇内用户的内容请求命中率.文献 构建了用户协作缓存的雾计算网络模型,结合联邦学习算法和推荐算法提出了一种个性化的用户内容缓存方案,以提高内容缓存收益.此外,还有根据地理位置进行缓存布设的方案,如文献 发现内容流行度可能随用户位置而变化,提出了一种基于预测模型的缓存方案,该方案同时考虑了用户移动性和内容受欢迎程度.文献 考虑了一个基于用户行为的布设方案,在用户历史访问数据的基础上,提取出请求内容的偏好特征,最后用线性回归的方法计算用户请求的时空分布.文献 研究了一个多层缓存方案,使得基站和用户都能在其本地缓存空间中存储内容数据,并在典型的未编码和编码缓存策略下分析了边缘缓存无线网络的性能.本文提出了一种新的方案,通过引入网络编码技术,先对视频文件分块进行编码处理,再对编码块进行缓存,因此用户设备缓存和分享的是视频文件的编码块而不再是源数据块.新方案利用编码块的信息混合优势,可以有效应对传统方法中因用户频繁离开而造成的“稀有块”问题;而且,由于内容请求用户只需要获取一定数量的编码块即可解码并获取源文件,因此各编码块在重构整个文件时都具有相等的价值,从而消除了传统方法中普遍存在的数据块调度困境,也易于与已有的方案进行联合部署.移动D D视频缓存网络模型一种典型的移动D D视频缓存网络模型如图所示,网络内的用户可以与其设备D D传输半径内的邻居分享视频内容,即相邻用户的缓存资源可以共享.图一种典型的移动D D视频缓存网络模型第期胡夏芸,等:基于网络编码的移动D D视频缓存网络内容布设方法研究假设用户设备均匀地分布在图的区域内,每个用户请求访问的视频内容均来自同一个文件库,每个用户在其D D最大传输半径(r)范围内存在K个相邻用户,则K服从密度为的泊松分布,即请求用户在以自身为中心的半径为r的覆盖范围内有k个用户的概率可以表示为P rKk(r)kk!er()当某个用户设备发起内容请求时,按顺序有种获得所需内容的方式:)自卸载.当用户已经缓存文件时,可以立即从本地缓存内获得该文件.)D D卸载.当本地未缓存所需文件内容时,可通过D D通信从已缓存目标文件的邻居用户处获取.)蜂窝卸载.当方式)和)均失败时,该用户将转向基站,通过核心网络从远程服务器处获取.显然,方式)和)允许邻近的通信双方可以不经过基站直接通信,有效降低了回程链路流量,提高了内容缓存收益.因此,缓存布设方案的关键在于如何最大化D D缓存网络的访问命中率,降低蜂窝卸载的频率.用户对文件库内各视频文件的请求概率服从Z i p f分布,即流行度排名越靠前的视频文件被用户请求的概率越高.假设文件库包含M个视频文件,则流行度排名为i的视频文件被用户请求的概率fri可以表示为friisMjjs()其中,s为Z i p f分布的指数常数,值越大则用户请求越集中于排名靠前的热点流行文件.视频内容随机缓存方法为了提高文件分发效率和简化调度过程,视频文件的缓存和传输过程均是以分块为单位进行的,用户请求一个视频文件时,就必须得到全部的文件分块,才能还原出完整的请求文件.根据用户内容请求方式,对于本地或者邻居中没有的文件块(即自卸载和D D卸载两种方式均失败),用户需通过宏基站进行下载.下文首先讨论网络内用户随机从文件库选择文件块进行缓存布设方法的性能,然后对比分析引入网络编码方法前后的内容缓存效用,最后再给出基于网络编码的截断式内容缓存策略.假设文件库包括M个视频文件,每个文件包括m个分块,且每个用户设备可缓存c个块.为了表征用户通过方式)或)请求内容的命中率,记fi j为某个用户缓存了第i个视频文件中第j个分块的概率,gi j为文件片i j在某个用户的本地或者邻居中被缓存的平均概率.由于每个用户都是独立进行文件块缓存,所以gi j可以表示为gi jk(fi j)k P rKk()则用户成功请求文件i需要通过方式)从基站下载的平均块数Bi为Bifrim(gi j)()对于整个文件库来说,随机缓存方法下用户请求一个文件需从基站下载的平均块数Br a n d为Br a n dMMiBiMMifrim(gi j)()结合式()及麦克劳林级数(M a c l a u r i ns e r i e s)可得Br a n dmMMifri(fi j)e r fi j()由于此时fi jcMm,代入式(),可得Br a n dmMMifricMme rcMm()金陵科技学院学报第 卷根据式()的第i个流行视频文件的概率质量函数,可得MifrifrfrfrMP r(iM)Fi(M)()其中Fi(M)是用户请求文件i的概率(累积)分布函数,对于有M个流行文件的文件库,根据Z i p f分布的概率密度函数有Fi(M)MjjsMjjs()结合式()和式(),随机缓存方法中用户请求文件需通过基站下载的平均块数Br a n d为Br a n dmMcMme rcMmMjjsMjjsmMcMme rcMm()基于网络编码的缓存策略用户设备缓存编码块时,对视频文件的所有分片进行编码,编码后的文件块数依然为m,因此用户获取任意m个编码块即可解码出完整视频文件.记fi为某用户缓存区中缓存了文件i编码后的文件块的概率,则fi可表示为ficMm,i(,M)()不同用户设备随机缓存文件块的行为是独立的,若某用户请求文件i时,本地或邻居中已有文件i的编码块数目Hi将遵循二项分布,即HiB(c(k),fi).用户请求文件i时,若要得到原始的文件,则Hi大于等于m时用户才可以获取并解码还原原始视频文件,而无需再通过基站下载文件.因此某用户请求文件i时需要通过基站下载的块数Bi有以下两种情况:Bi,Him,c(k)fri(mHi),Hi,m()则根据全概率公式,用户请求文件i时需要下载的平均块数可以表示为Bifrim hP(Hih)(mh)frim hChc(k)fhi(fi)c(k)h(mh)()将fi的值代入式(),可得Bifrim hChc(k)cMmchcMmc(k)(mh)()对于含有M个视频文件的整个文件库来说,用户从基站下载的平均视频(编码)块数BN C r a n d为BN C r a n dMMiBiMMifrim hChc(k)cMmchcMmc(k)(mh)()基于网络编码截断式的缓存策略在基于网络编码的随机缓存策略中,用户对文件库中每个文件的编码块进行缓存的概率是相同的,但是,从用户请求视频文件的概率分布来看,用户请求会倾向于缓存排名靠前的文件.排名靠后的文件可能无法提高缓存命中概率,还占用了缓存空间,浪费了缓存资源.为了解决这一问题,本文提出了基于网络编码的截断式随机缓存策略(n e t w o r k c o d i n gb a s e dc u t o f f r a n d o mc a c h i n g,N C C F R C),其基本思想是:截去文件库中请求概率较低的文件,形成一个新的缓存文件库,再按文件进行文件块网络编码,最后用户以随机的方式缓存新文件库中的文件编码块.下面我们分析N C C F R C的缓存命中率,以求解从原文件第期胡夏芸,等:基于网络编码的移动D D视频缓存网络内容布设方法研究库截去低请求概率文件后形成的新文件库的最优收益率,即新文件库文件数M 的最优值M o p t.记f i为N C C F R C策略下某用户缓存文件i中编码后的文件片的概率,有f icM m,i,M,iM,M()由于用户缓存文件片的概率是随机独立的,因此用户请求文件i(i,M )时,本地或邻居中已有文件i的编码块数目H i遵循二项分布,即H iB(c k,f i);当iM,M 时,用户缓存中未缓存此文件,此时文件i的全部分块都需通过基站从文件库下载.因此,N C C F R C策略下用户成功请求文件i(i,M )时需要下载的块数有Bi,H im,c kfri(mH i),H i,m()用户成功请求文件i(i,M )时需要下载的平均块数B i可以表示为B ifrim nP(H in)(mn)frim nCnc k(f i)n(f i)c kn(mn)()当i,M ,将f i的值代入式(),可得B ifrim nCnc kmn(M)nM c kn()那么,对于整个文件库,用户成功请求文件从基站下载的平均块数BN C C F R C为BN C C F R CM iB i(MM)mMmMM ifrim nCnc kmn(M)nM c knmM()结合式(),可以按式()求得M o p t,即如果截断原文件库进行缓存时,应该保留前M o p t个视频文件,从而使得从基站获取的平均下载块数最小.M o p ta r g m i nM MBN C C F R Ca r g m i nM MmMM ifrim nCnc kmn(M)nM c knmM()仿真实验与性能分析本节将通过数值仿真实验来比较N C C F R C与另外种缓存布设方案,并分析系统参数对算法缓存命中率的影响.种对比算法分别为:分段式随机缓存策略(S B R C)、截断式随机缓存策略(C F R C)、根据缓存容量大小随机缓存不同文件的策略(r a n d o mc a c h e).测试时,网络内用户数N ,视频文件库内文件数M ,基站覆盖范围Rb m,文件平均分片数m.图描绘了内容流行度参数s不同的情况下,N C C F R C与其他种算法的缓存命中率曲线.测试中,每个用户缓存空间容量c,用户通信距离r m.由图可知,在随机选取内容进行缓存的方案(r a n d o mc a c h e)中,由于不受请求概率影响,对应的缓存命中率不随s变化,其他方案的缓存命中率均随s的增加而增加.纵向对比发现,N C C F R C策略的缓存命中率比S B R C、C F R C等算法高,这是因为在N C C F R C策略下节点缓存的是文件分片的编码信息,响应请求时只要确保缓存的文件分片数达到可还原数据的量即可,无需精准缓存文件的所有分片数据.图描绘了用户缓存容量c不同的情况下,N C C F R C策略与其他种算法的缓存命中率曲线.测试中用户D D通信距离r m,流行度参数s.由图可知,种缓存策略的缓存命中率均随用户缓存容量的增大而增加,其中N C C F R C和S B R C策略下,节点容量为 时缓存命中率最佳,随后稍有降低.总体看N C C F R C缓存命中率依然较高,这是因为用户缓存容量越大,每个用户含有被请求文件的可能性就越大,且编码块是源数据块的信息混合,相比直接存储源数据块,相同数据块少,缓存命中率就高.金陵科技学院学报第 卷图缓存命中率随内容流行度参数s的变化曲线图缓存命中率随节点缓存容量c的变化曲线图进一步分析了在D D通信距离r不同的情况下,种算法的性能情况.实验结果表明,随着r增加,每个请求用户周围能够为其提供D D服务的用户数量增多,已经缓存的数据增多,缓存命中率也随之增大.其中,C F R C策略下,通信距离为 m时缓存命中率最高.对比不同算法可知,在r不同的条件下,N C C F R C的性能较好且稳定,适应性更好.由前文可知,N C C F R C根据文件流行度对文件库进行截断后对每个文件进行分片编码缓存,从而达到提高用户缓存命中率的效果,但是文件分片数过多时可能导致数据还原困难,过少时可能导致用户缓存空间利用率低.因此,为了评估文件分片数对算法的影响,图描绘了不同用户缓存容量场景下,使用N C C F R C策略时的用户缓存命中率情况.本次仿真参数为:用户通信距离r m,流行度参数s.从图可以看出,缓存容量c和c 时,缓存命中率均在分片数为时达到最高,分片数为和时次之,因此三片式文件能够实现最大的缓存命中率,两片式、四片式的性能与三片式的十分接近.当分片增加后,缓存命中率下降.这是由于分片越多,用户响应一个请求时需要的片段就越多,该用户需要从更多的邻居节点中获取数据信息,导致还原一个完整数据文件的难度增大,缓存命中率随之降低.此外,需要说明的是最优分片数的选取还需兼顾具体用户设备的编解码能力,因为除了分片数以外,分片引起的分片大小变化也会影响设备编解码的吞吐量.图缓存命中率随用户间D D通信距离r的变化曲线图N C C F R C策略下缓存命中率随文件分片数m的变化曲线 结语随着用户设备缓存空间受限,如何提高用户设备缓存内容的收益是提高移动D D视频缓存网络性能的关键.本文通过引入网络编码技术,对比分析了经典随机缓存策略和基于网络编码的随机缓存策略的(下转第 页)金陵科技学院学报第 卷A u t o m a t i cC o n t r o l,:HANF,WANGZD,D ONGHL,e t a l Al o c a l a p p r o a c ht od i s t r i b u t e dHc o n s e n s u s s t a t e e s t i m a t i o no v e r s e n s o rn e t w o r k su n d e rh y b r i da t t a c k s:d y n a m i c e v e n t t r i g g e r e ds c h e m eJ I E E ET r a n s a c t i o n so nS i g n a l a n d I n f o r m a t i o nP r o c e s s i n go v e rN e t w o r k s,:WAN GF,WAN GZD,L I AN GJL,e t a l R e c u r s i v ed i s t r i b u t e d f i l t e r i n g f o r t w o d i m e n s i o n a l s h i f t v a r y i n gs y s t e m so v e rs e n s o rn e t w o r k su n d e r s t o c h a s t i cc o mm u n i c a t i o np r o t o c o l sJ A u t o m a t i c a,:L ID H,L I AN GJL,WANGF R o b u s tHf i l t e r i n gf o r Ds y s t e m sw i t hR ONu n d e rt h es t o c h a s t i cc o mm u n i c a t i o np r o t o c o lJ I E TC o n t r o lT h e o r y&A p p l i c a t i o n s,():L IM Y,L I ANGJL,WANGF R o b u s ts e t m e m b e r s h i pf i l t e r i n gf o rt w o d i m e n s i o n a ls y s t e m sw i t hs e n s o rs a t u r a t i o nu n d e r t h er o u n d r o b i np r o t o c o lJ I n t e r n a t i o n a l J o u r n a l o fS y s t e m sS c i e n c e,():YANGCY,L I AN GJL,CHE NXY D i s t r i b u t e de v e n t b a s e dHc o n s e n s u sf i l t e r i n gf o r DT Sf u z z ys y s t e m so v e rs e n s o rn e t w o r k ss u b j e c t t oD o Sa t t a c k sJ I n f o r m a t i o nS c i e n c e s,:WAN GJY,DU X,D I N G D W E v e n t t r i g g e r e dc o n t r o lo ft w o d i m e n s i o n a ld i s c r e t e t i m es y s t e m si nF o r n a s i n i M a r c h e s i n i(FM)s e c o n dm o d e lC C h a n g s h a:t hC h i n e s eC o n t r o l a n dD e c i s i o nC o n f e r e n c e(C C D C),:WAN GYY,X I ELH,S OU Z ACE R o b u s tc o n t r o lo fac l a s so fu n c e r t a i nn o n l i n e a rs y s t e m sJ S y s t e m s&C o n t r o lL e t t e r s,():(责任编辑:谭彩霞湛江)(上接第 页)缓存收益,提出了基于网络编码的截断式缓存策略.实验结果验证了所提策略较已有经典方法的优点.下一步将对本方法进行拓展,完善邻居用户的匹配、最优编码块的生成与传输等相关辅助功能,并尝试在A n d r o i d等移动应用平台上开展原型系统的研制.参考文献:GUANY,Z HAN GXG,GUOZM P r e f C a c h e:e d g e c a c h e a d m i s s i o nw i t hu s e rp r e f e r e n c e l e a r n i n g f o r v i d e oc o n t e n t d i s t r i b u t i o nJ I E E ET r a n s a c t i o n so nC i r c u i t sa n dS y s t e m s f o rV i d e oT e c h n o l o g y,():朱霞,靳昊恺基于边缘计算的单任务迁移策略研究J金陵科技学院学报,():朱丽丽基于 G边缘计算技术的智慧校园专网云数据高效存储方法J金陵科技学院学报,():HUAN GXN,Z HAOG D,Z H IC S e g m e n t b a s e dr a n d o mc a c h i n gi nd e v i c e t o d e v i c e(D D)c a c h i n gn e t w o r k sC/I n t e r n a t i o n a lS y m p o s i u mo nW i r e l e s sC o mm u n i c a t i o nS y s t e m s(I S WC S)B r u s s e l s:I E E E,:黄小柠面向无线缓存的D D技术研究D成都:电子科技大学,龙彦汕,吴丹,蔡跃明,等多缓存容量场景下的D D内容缓存布设优化方案J计算机应用,():,湛美琪,殷俊,张兆维,等面向移动边缘缓存网络的层次化内容分享系统架构研究C/中国自动化学会 中国自动化大会论文集中国自动化学会,:CHE NQ,WAN G W,YUFR,e t a l C o n t e n t c a c h i n go r i e n t e dp o p u l a r i t yp r e d i c t i o n:aw e i g h t e dc l u s t e r i n ga p p r o a c hJI E E ET r a n s a c t i o n so nW i r e l e s sC o mm u n i c a t i o n s,():黄晓舸,王凡,陈志,等雾计算网络中联邦学习协同的内容缓存方案J北京邮电大学学报,():MOU HL,L I U Y H,WAN GL L S TMf o rm o b i l i t yb a s e dc o n t e n tp o p u l a r i t yp r e d i c t i o ni nw i r e l e s sc a c h i n gn e t w o r k sC/I E E EG l o b e c o m W o r k s h o p s(G C W k s h p s)W a i k o l o a,H I:I E E E,:任佳智,田辉,范绍帅,等基于用户偏好预测的无人机部署和缓存策略J通信学报,():TANLT,HURQ M o b i l i t y a w a r e e d g e c a c h i n ga n dc o m p u t i n g i nv e h i c l en e t w o r k s:ad e e pr e i n f o r c e m e n t l e a r n i n gJI E E ET r a n s a c t i o n so nV e h i c u l a rT e c h n o l o g y,():(责任编辑:湛江谭彩霞)