学位论文 > 优秀研究生学位论文题录展示

基于WSP协同的视频副本缓存算法研究

作　者: 张喆
导　师: 郭宇春
学　校: 北京交通大学
专　业: 通信与信息系统
关键词: 协作缓存策略无线服务提供商整数(0-1)规划无线视频点播系统
分类号: TN948.64
类　型: 硕士论文
年　份: 2014年
下　载: 8次
引　用: 0次
阅　读: 论文下载

内容摘要

视频点播服务(VoD)的迅猛发展带来了巨大的带宽开销,在2012年,全球视频流量已经占到了整个互联网流量的57%。随着无线技术的飞速发展,大量3G,4G用户对VoD服务的需求更加加剧了核心带宽资源的需求危机。为了应对无线用户对VoD服务的不断需求,无线服务提供商(WSP)开始在移动交换中心(MSC)上部署高速缓存(Cache),以求提高用户体验,降低骨干网带宽消耗。研究该场景下各WSP的cache策略,不仅有助于提高cache命中率,同时也对降低服务器负载、节省WSP对骨干网的带宽消耗、提高服务质量有着重要的指导意义。本文首先分析了新浪无线视频用户的基本统计特征,研究了新浪无线视频用户的观影行为。通过研究用户行为,不仅可以了解无线用户对视频的需求情况和用户的观影模式,还可以对WSP的cache策略提供重要的参考价值。通过从多角度分析用户的观影行为,包括用户每天的观影模式,用户活跃度,视频流行度分布以及视频流行度变化频率等情况,发现流行度排在前10%的视频带来了80%的流量,虽然无线视频每天的流行度变化比较巨大,但是最热门的视频(如前10名)流行度每天变化都很稳定。这些结果都说明WSP在MSC部署cache,通过缓存热门视频,可以有效将视频带来的流量限制在WSP内部,以此降低WSP与骨干网的数据通信流量,为WSP节省成本的同时提高用户体验。其次,本文以各WSP内部的各个MSC各自缓存本地最流行的视频作为基本cache策略。然后提出了基于WSP协同的视频副本缓存策略,于是本文的研究的重点就是如何决定各WSP内部MSC缓存哪些视频,能够使WSP与骨干网的流量最小,即WSP成本最小。通过对该问题建模,将其抽象为了整数(0-1)规划的数学模型,并假设了两种场景：场景一：WSP间不合作仅内部各MSC合作；场景二：WSP间以及WSP内部各MSC也合作的。并通过分支定界法求得了最优解。发现场景一下的cache策略与基本cache策略相比,能够为WSP节省77.17%的成本。而针对场景二,在实验了多组WSP网间结算成本后,证明了场景二下的cache策略要比场景一的cache策略更能为WSP节省总成本。最后,由于所提的整数(0-1)规划模型是NP-hard的,对于求解36个MSC的数据集的最优解需要3小时13分钟,无法在实际中投入使用,于是本文提出了时间开销更小的启发式算法。并通过提出了两种方案来对启发式算法改进,使得该算法在时间开销上远小于最优解,同时,与基本cache策略相比,能够为WSP节省68.28%的成本。不仅提升效果明显,而且时间开销更小,具有实际使用价值。

全文目录

致谢  5-6
中文摘要  6-8
ABSTRACT  8-10
目录  10-13
1. 引言  13-18
  1.1 研究背景  13-14
  1.2 国内外研究现状及研究意义  14-16
  1.3 本文研究内容  16
  1.4 论文工作及结构安排  16-18
2. 相关技术介绍  18-26
  2.1 CDN技术概述  18-21
    2.1.1 CDN基本原理  18
    2.1.2 CDN主要技术  18-19
    2.1.3 CDN基本工作过程  19-20
    2.1.4 CDN系统架构  20-21
    2.1.5 CDN部署架构  21
  2.2 Cache技术概述  21-22
    2.2.1 Cache基本概念  21-22
    2.2.2 Cache命中率  22
    2.2.3 Cache副本替换算法  22
  2.3 Hadoop技术概述  22-25
    2.3.1 Hadoop基本概念  23
    2.3.2 Hadoop基本组成  23-24
    2.3.3 HDFS特点  24
    2.3.4 Map/Reduce思想  24
    2.3.5 Hadoop的优势  24-25
  2.4 本章小结  25-26
3. 数据分析  26-32
  3.0 数据集介绍  26
  3.1 数据清洗  26-27
  3.2 数据统计概况  27-28
  3.3 用户行为分析  28-31
  3.4 本章小结  31-32
4. 基于WSP协同的视频副本cache策略  32-42
  4.1 优化目标  32-33
  4.2 WSP独立cache策略  33
  4.3 WSP协作cache的整数(0-1)规划模型  33-36
    4.3.1 WSP内部各MSC之间协作cache场景  35
    4.3.2 WSP间协作cache场景  35-36
  4.4 模型求解  36
  4.5 模型改进  36-37
    4.5.1 结合基于内容相似度的聚类算法  37
    4.5.2 结合基于地理位置的聚类算法  37
  4.6 算法评估  37-41
    4.6.1 仿真环境介绍  37-38
    4.6.2 WSP独立cache算法评估(Baseline算法评估)  38
    4.6.3 最优解评估  38-41
  4.7 本章小结  41-42
5. WSP协同cache启发式算法  42-50
  5.1 启发式算法  42-44
    5.1.1 启发式算法设计  42
    5.1.2 理论依据  42-43
    5.1.3 启发式算法流程图  43-44
    5.1.4 启发式算法伪代码  44
  5.2 启发式算法改进  44-46
    5.2.1 方案一：随机指派一个MSC后将剩余视频从排行榜中剔除  45
    5.2.2 方案二：挑选与源MSC通信成本最小的MSC来存储剩余视频  45-46
  5.3 算法评估  46-49
    5.3.1 仿真环境介绍  46-47
    5.3.2 启发式算法改进方案效果评估  47-48
    5.3.3 启发式算法与整数(0-1)规划模型最优解对比  48-49
  5.4 本章小结  49-50
6 结论和展望  50-53
  6.1 本文工作总结  50-51
  6.2 未来工作展望  51-53
参考文献  53-56
作者简历  56-58
学位论文数据集  58

基于WSP协同的视频副本缓存算法研究

内容摘要

全文目录

相似论文