图2节点建立视频流行度的估计关系2.3查找跳数TTL的确定 在查找算法里多次调用了参数不同的SearchSP(T,v)函数，其主要作用是向不同类型的邻居节点请求查找视频v，如果邻居缓存了v则向请求的节点返回响应，如果没有缓
图2节点建立视频流行度的估计关系2.3查找跳数TTL的确定
在查找算法里多次调用了参数不同的SearchSP(T,v)函数，其主要作用是向不同类型的邻居节点请求查找视频v，如果邻居缓存了v则向请求的节点返回响应，如果没有缓存则继续向邻居的邻居进行查找。这里需要重点考虑的一个问题是如何确定查找跳数TTL(hop)。在NetTube中，简单地设置查找跳数TTL为2跳，目的是为了降低Flooding带来的开销。而在实际情况下，节点对点播视频v的查找跳数TTL存在如下几个特点：1)TTL和视频v的“流行度”密切关联，“流行度”越高的视频被点播节点缓存的概率也越大，因此在TTL较小的情况下能达到较好的查找效率；2)TTL和类型为T(v)的簇的局部紧密程度相关。簇中节点的邻居数较少则局部紧密度也就较小，因此适当增加TTL不会带来较大的网络开销。文献［5，10］通过大量实验数据得出在线视频分享中视频的点播次数和“流行度”排名基本满足Zipf分布。假设节点单播的视频v的流行度排名为k，而FastSearch中所有视频文件数量为M，Zipf分布是指数特性参数为S。则根据Zipf分布的性质，节点点播流行度排名为k的视频v的概率可表示为：
f(k;s,M)=1/ks∑Mn=1(1/ns)=1ksHM,s(1)
HM,S为谐参数(Harmonic number)，HM,S=∑Mk=11ks，设S=1时，HM,1=∑Mk=11k=ln M+γ，γ是Euler.Mascheroni系数，值为0.5772156649。通过式(3)可以看到排名越靠前(k越小)则节点点播了该视频的概率越大。另外设在线的点播节点数为N，那么在线节点中点播并缓存视频v的节点数Nk可粗略估计为：
Nk=N·f(k;s,M)=Nk(ln M+γ)(2)
因此节点i要查找到视频v需要访问的节点数量为:
Nv=「NNk=「k(ln M+γ)(3)
通过式(5)也可以看到如果视频v的流行度越高则需要访问较少的节点就可以找到缓存了该视频的节点。另外，还需要考虑的是类型为T(v)的簇的紧密程度，这里采用文献［11］中的方法，对一个属于类型为T(v)兴趣簇的节点j其局部簇系数可表示为CCj=|E(Γj)|C2Nbj,其中:Γj为节点j的邻居
集合;|Γj|为节点j的邻居的总数;|E(Γj)|表示Γj集合中实际的连接总数;C2Nbj表示Γj集合中可能产生的连接总数，CCj越大就表示簇的紧密程度越大。再假设FastSearch中一个节点的强邻居节点个数为x，那么在TTL跳内可以访问到的T(v)类型簇的节点个数为∑TTLt=1(x′)t，其中x′=x·(1－CCj)。所以有：
∑TTLt=1(x′)t≥Nv(4)
TTL≥logx′((x′－1)Nvx′+1)(5)
FastSearch通过式(2)～(5)粗略求出一个“流行度”排名为k的视频v的查找跳数TTL。由于FastSearch按照节点的主要点播兴趣偏好把节点进行了分簇，并把视频文件之间的关联考虑进去。所以实际需要的TTL值通常比式(5)求出的理论值更小就可以达到较好的查找效率。
2.4查找策略的性能分析
假设节点i点播的视频v的流行度Pv,和视频v关联的视频个数为M个，而每个节点平均有N个邻居节点。另外，定义第l层节点到第l+1层节点的查询请求转发表示请求消息增加1跳，如图1(a)中节点i向N2和N3发送查询请求为第1跳，而N2转发请求消息给N4,N5和N6及N3转发消息给N8均属于第2跳。Pik,j(1≤k≤N)表示节点i的第k个邻居节点在第j跳能够找到视频v的源节点的概率。如果节点间在没有视频关联关系信息的时候，在第j跳能够找到视频v的概率为pv，即只与流行度相关。而在邻居节点间具备邻居缓存的视频列表，并有关联意识的进行查询时第j跳能够找到视频v的概率不仅和pv相关，同时还和第j－1跳的节点所缓存的关联视频个数有关。给出如下条件概率Pj, 表示在第j－1跳的节点缓存有λ个和视频v相关联的视频的条件下(具备关联关系)，如果把查询消息转发给该节点则在第j跳成功查找到视频v的概率：
P jnbi = P(Fnbi j > 0|B j-1i = λ) = (1+λMv).pv (6)
pv =|Sv |n(7)
在式(6)中：B j－1i表示第j－1跳的某个节点i缓存的与v相关的视频个数为λ；F jnbi表示节点i把查询消息转发给自己的邻居节点即第j跳，能够找到视频v的个数；Mv表示和视频v相关联的视频个数；Sv表示当前在线的n个节点中缓存了视频v的节点集合；|Sv|表示缓存了视频v的节点的数量。式(7)中pv则表示视频v的流行程度。显然，能够查找到视频v的概率和不仅和视频v自身的流行程度相关同时还和视频关联关系的紧密程度相关，如果节点i缓存的和视频v相关的视频个数越多，则表明i的邻居节点缓存了越多的和v相关的视频，λ越大则表明下一条邻居节点那里越容易找到视频v。
假设FastSearch中一个节点的平均邻居节点个数为k，而节点i的邻居节点中如果有θ(θ
下面对比在k个邻居节点中任意选择θ个发送查找请求的查找效率。当不可考虑视频之间的关联关系，也即节点i发送k个查询消息给各个邻居节点。由于不考虑关联关系，查找成功查找概率只和视频v的流行度pv相关。因此在k个邻居处查找到θ个缓存了视频v的源节点概率为:
Pj′=P(Fj=θ)=pθv(1－pv)n－θ(10)
而PjPj′=(1+λ1Mv)…(1+λθMv)(1－pv)n－θ>1，也即FastSearch中通过有选择性地发送θ个查询消息比任意选择θ个发送的查找成功率更高。3实验仿真
本文采用OverSim系统［7,12］对FastSearch仿真，在关联度较大的时候，通过Flooding策略和FastSearch算法通常都可以得到较好的资源命中率。FastSearch的主要优势是能够在视频关联度不大的时候可以获得可接受的视频查找效率。所以，这里重点比较前后两次视频点播的视频节目在没有强关联性的时候的查找效率。通过图3的对比可以看到FastSearch的查找效率显著优于NetTube这类采用Flooding策略的典型系统，在这种情况下IShare的平均查找效率基本达到了60%，而部分情况下NetTube却基本无法直接通过P2P的方式找到源节点而必须借助于服务器的帮助，而这显然又增加了服务器的压力。
图片 (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）
顶一下
(0)
0%
踩一下
(0)
0%
版权声明：因本文均来自于网络，如果有版权方面侵犯,请及时联系本站删除.
