时移电视[1](Time-Shifted Television)作为IPTV的一种，允许用户进行暂停、快进和后退等操作，也可以选择几天前的电视节目，是一种极具吸引力的服务。不同于一般的网络电视，时移电视需要对每个用户分配一个信道，不能通过组播的方式将节目数据推送给用户。同时，由于电视信道所需带宽较高[2]，现有内容分发网CDN(Content Distribution Networks)的体系结构难以满足业务要求，对服务提供者提出了挑战。

    P2P技术有效打破了CDN中代理服务器的C/S模式。网络中的节点既是用户又是服务器，使用户能从最近的对等节点中下载相应流式数据，从而有效避免热点服务器过载,减少电视频道切换响应时延[3](Zap Response Time)。
     副本放置技术常用来解决这种热点问题。通过对热门副本进行有策略的放置，减轻相关热点资源节点的负载，缩短请求消息搜索路径，提高消息搜索成功率，降低请求响应时延。P2P网络副本放置方法分为三种：服务端副本放置方法、客户端副本放置方法和路径放置方法。参考文献[4]将纯P2P网络归纳为损失模型（loss network model），将文件按热、中、冷三种类型放置到各个节点中，从而实现各节点上行带宽使用率的最大化。参考文献[5]在结构化P2P网络的基础上，提出了一种最优副本放置算法,有效平衡了性能与开销之间的关系。参考文献[6]通过研究现有P2P网络上运行的IPTV业务的提高方法，指出了一系列缓存管理和副本放置方法。另外，参考文献[7]也对P2P上的流媒体业务进行了分析和建模。但是，现有的研究存在以下问题：首先，现有算法大都是基于P2P存储系统，以整个文件为基础进行处理，不符合流式传输的数据存储方式；其次，没有考虑到不同数据类型的差别，单纯地将数据分为热点数据和冰点数据，降低了冷门节目的服务质量。
    本文针对时移电视系统中的副本放置问题，提出一种混合副本放置策略。通过分析IPTV编码方式和流式数据传输特性,考虑网络拓扑对放置策略的影响，以及负载均衡等要求,自适应地将数据片放置在节点中,就近为用户提供服务,从而有效提高用户体验度和系统性能。
1 问题分析
1.1 系统模型
    本文分析的时移电视系统的结构中，源服务器RS(Resource Server)通过组播的方式将内容推送到各地的代理服务器VHO(Video Hub Office)。本地各设备(如机顶盒、计算机和手机等）间通过无结构P2P网络连接，分享节目数据。VHO中存储着所有当前电视节目内容数据，并通过分层编码技术（Layered Encoding）和多描述编码技术MDC(Multi-description Coding)，将不同质量的视频内容传送到不同用户的设备中。
    本文主要关注时移电视节目数据在系统中的放置问题。由于所有电视数据都已存储在VHO中，因此本文的数据放置问题可进一步简化成流式数据在P2P网络中的管理问题。


    通过上述分析可以发现，对各个频道及其节目的数据帧进行合理的复制，进而放置到靠近用户的位置，是平衡用户请求的消息搜索成功率和副本放置开销之间关系的一种有效途径。
2.2 混合副本放置策略
    在查询消息路由算法一定的条件下，节点Vi收到的查询消息数量由其覆盖的节点数决定，即该节点通过泛洪，在TTL的限制下，转发该节点查询消息的节点数量。设网络中平均连接度为K。当K=1时，节点Vi接收的查询消息转发次数为：

    (2)过期数据片的放置。鉴于实时数据片已经占用了很大一部分缓存空间，过期数据片所能提供的缓存空间相对减小，因此选择其放置策略更要慎重。首先要解决选择哪一个数据片副本需要进行放置，以及缓存空间已满时应该采取怎样的缓存管理策略。用户节点有两个选择查找到需要的过期数据片，以实现快进、快退等操作。①通过洪泛的方式进行搜索；②直接到代理服务器中查找相应数据片。第一种方法虽然能够分担代理服务器的负载，减少请求时延，但是加重了网络负担，且存在消息搜索成功率低的问题。因此，对于过期数据片，可通过代理服务器进行查找。若该内容在节点服务器中的并发数超过OL，且用户节点搜索失败，则将目标数据片放置在沿路连接度最大的路由节点中。若此节点缓存空间已满，则采用LRU为该副本腾出相应空间。
    (3)缓存数据管理。在时移IPTV系统中，每一个数据在一定时间后可用度就大大减少，需要对这些数据进行定期处理，以提高缓存利用率。
     设置数据片生存时间，使各类数据片的生存时间各有不同，其中实时数据片的生存时间应该大于过期数据片的生存时间,以满足用户短时间暂停或快退的需要。
3 仿真及结果分析
3.1 仿真环境
    仿真采用Power law拓扑作为模拟拓扑。拓扑包括1 000个节点，其中包括一个代理服务器，100个路由器节点,其余为用户节点。每个路由节点缓存空间为36 GB，用户节点通过洪泛的方式获取所需节目的相关数据。网络中节点平均连接度为4,设置150套电视节目，同一节点不存在同一数据片对象。用户节点以相同的概率发起查询消息获取随机的节目。
3.2 数据分析
    图3显示了在IPTV系统中节点通过使用洪泛的查询消息路由算法进行搜索，各放置策略对数据片的搜索命中率的影响的比较。图中横坐标为单个路由节点缓存空间与整个数据库内容大小的比值。TTL的值为2。数据表明，在同一网络条件下，采用混合副本放置策略的消息搜索成功率较高。当缓存空间增加时，随机放置策略下的消息搜索成功率也有增加，但是由于其副本放置的随机性，使得性能的提高不是很稳定。

    图4显示了各策略的路由节点缓存空间占用情况的比较。可以看到，随机副本放置策略作为一种贪婪策略，总是随机地选择数据内容将缓存空间填满。这样的好处在于，搜索成功率随着缓存空间的增大而提高。然而，随机地选择数据内容不适合IPTV系统这样数据更新较快的环境，且这种主动而又周期性地盲目数据更新更加重了网络开销。

    时移电视具有数据量大，数据更新频率高等特点。本文针对时移电视系统中的副本放置问题，从IPTV数据流格式特点出发，提出了一种混合副本放置策略。通过分析传输时延以及消息搜索成功率与副本放置的关系，根据节点连接度放置数据片，达到提高热点数据片搜索成功率的效果。同时，分析IPTV数据帧特点，合理分配放置概率，以减小节目初始化时延以及频道切换时延。最后给出了混合副本放置策略。仿真表明，该策略能够在较少的缓存空间下有效提高消息搜索成功率，降低请求时延，提高系统性能。
参考文献
[1] Liu Yaning, SIMON G S. Distributed delivery system for time-shifted streaming systems[C]. 2010 IEEE 35th Conference on Local Computer Networks, Denver, CO, USA, 2010:276-279.
[2] POPESCU A, KOUVATSOS D D, REMONDO D, et al.Content distribution over IP: developments and challenges[J]. Network Performance Engineering, 2011,5233:979-987.
[3] BEJERANO Y,KOPPOL P V. Improving zap response Time for IPTV[C].INFOCOM 2009, IEEE,Rio de Janeiro, 2009:1971-1979.
[4] TAN B, MASSOULIE L, Optimal content placement for peer-to-peer video-on-demand systems[C]. IEEE INFOCOM 2011, shanghai, 2011: 694-702.
[5] Rao Weixiong, Chen Lei, Fu Waichee, et al. Optimal resource placement in structured peer-to-peer networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2010,21(7):1011-1026.
[6] BIERACKI A. Methods of QoS improvement for P2P IPTV based on traffic modelling[C]. 2010 International Conference on Complex,Intelligent and Software Intensive Systems,2010:445-450.
[7] Gao Peng, Liu Tao, Chen Yanming,et al. The measurement and modeling of a P2P streaming video service[J].Networks for Grid Applications, 2009,2:24-34.
[8] Li Zhe, SIMON G. Time-Shifted TV in content centric networks: the case for cooperative in-network caching[C].ICC2011:IEEE International Conference on Communications, Kyoto, Japan, 2011:1-6.
[9] 冯国富, 张金城, 顾庆,等. 一种基于覆盖网络拓扑的无结构P2P主动复制策略[J].软件学报,2007,18(9):2226-2234.