摘要：针对采用了网络编码技术的对等网（P2P）流媒体系统应用，提出一种基于负载转移的节点带宽资源均衡策略，尽可能避免节点选择邻居节点并请求带宽资源的随意性形成的节点过载。在策略中，当某些节点过载后将选取部分带宽资源负载较轻的节点作为负载转移节点，同时将请求节点所需数据通过阶梯型带宽分配方式推送给这些选择出的负载转移节点。数值仿真表明，这种负载转移的策略能够有效降低过载节点的带宽资源占用，避免网络热区的出现。
关键词：资源过载；网络编码；负载转移；对等网
中图分类号： TP393.03 文献标志码：A
英文摘要
Abstract： To the PeertoPeer （P2P） streaming application based on network coding， a load transferbased node bandwidth resource balancing policy was proposed to avoid the overloaded node， which was due to random neighbor node selection and bandwidth resource requestion. When some nodes overloaded， the nodes with spare bandwidth resource could be selected as load transfer nodes to alleviate the load of overloaded peers. Through the ladderbased bandwidth allocation mechanism， the coded data required by the request nodes could be pushed to the selected load transfer nodes. The numerical simulation results show that the proposed load transfer policy can efficiently alleviate the bandwith resource consumption of overloaded nodes， and the hot area of network can be avoided.
英文关键词
Key words：
resource overload； network coding； load transfer； PeertoPeer （P2P）
0 引言
基于对等网（PeertoPeer，P2P）技术的视频流媒体应用已成为当今互联网中最为重要的应用[1]。在这类系统中，观看视频的节点自组织成一个独立于物理网络拓扑的重叠网络（Overlay Network）。每个节点维护了一定数量的邻居节点并周期性地交换缓存信息，这使得节点从邻居节点获取需要的视频流数据的同时也能够将自己缓存的视频流数据分发给邻居节点。通过节点之间的协作，有效避免了所有节点都向流媒体服务器请求数据，进而有效降低服务器的带宽消耗。
因此，P2P流媒体具有良好的可扩展性和较低的服务器带宽开销等优势。另外，由于每个节点都有一定数量的邻居节点，任意邻居节点的意外退出不会严重影响到其他节点正常获取流媒体数据，这使得P2P流媒体系统具有良好的系统健壮性。正因为P2P流媒体系统的诸多优点，众多商用流媒体系统都采用了P2P技术实现，如：PPLive[2]、UUSee[3]、Coolstreaming[4]等。
另一方面，网络编码[5]是一种融合了编码和路由的信息交换技术，并有望最终成为改善现有网络性能的新的技术手段。在使用网络编码后，网络中的节点可以通过采用随机产生的编码系数对收到的数据包进行编码，这使得编码数据与原始数据无直接关联，接收数据的节点也并不关心自己是否接收到完全的源数据包，它只关心自己是否接收到足够的线性不相关系数的新数据包以便能够通过解码运算恢复出原始数据。近年来，网络编码技术已经被运用于P2P流媒体系统中[3，6-7]，研究结果表明采用网络编码在提高系统健壮性、改善节点视频播放质量、缩短初始缓存时间等方面都有良好的表现。
在P2P流媒体系统引入网络编码技术后，编码后的数据对接收节点而言变得比较对象是谁？与谁同样重要。这个地方熟悉网络编码的读者完全能够理解，请不要单纯的去抠字面意思！变得相同重要指多个采用编码的节点在对各自数据进行编码后变得相同重要，和数据内容无关了。相同的重要，这也使节点不需要调度算法决定向哪些邻居节点获取具体哪些数据段，而只需要向邻居节点请求分配一定的带宽以保证原始数据段能够尽可能快地解码。由于节点随机地选择邻居节点并随机请求带宽资源，这就导致不同节点的带宽利用率不均的问题。换句话说，系统中的部分节点可能带宽资源的利用率很高（负载很重），而部分节点可能带宽资源利用率却很低（负载很轻）。本文重点研究采用网络编码技术的P2P流媒体系统中节点带宽分配的问题，通过负载转移的策略使系统中各节点的带宽的利用率尽可能均衡，避免系统中“热区”的出现。
1 相关研究工作
2 节点带宽的不均衡利用问题
首先给出P2P视频播放异构性的概念，这主要指在基于网络编码的P2P 流媒体系统中一个节点和其邻居节点在视频播放位置（Playback Point）及所缓存的流媒体数据的多寡方面存在的差异。图1所示的网络场景描述了节点进行带宽请求可能导致的服务节点带宽利用不均衡的问题。
若假设视频流速率为r，而在一个固定时间周期t（常数）内，节点要保证正常的视频播放至少需要获取到的编码流数据量为urt（u为流数据因子，且u≥1），节点带宽负载L可定义为单位时间内节点同时收到流服务请求的数与请求的流数据量之积。另外，假设节点i的邻居中可以为其提供流数据服务的节点集合为Si，该集合中节点个数为|Si|，节点i当前缓存流数据的进度（如：已经缓存的流媒体数据段的最大的编号）为Bi，定义随机变量Xj，i（Xj，i∈{0，1}），当Xj，i=1表示节点j被节点i选中作为节点i的数据服务节点，当Xj，i = 0表示节点j未被节点i选中，则节点j成为节点i的流数据服务节点的概率等于：
从式（2）可以分析出当一个节点i在观看视频过程中同时缓存的流媒体数据也在不断增加（Bi也会不断地增加），而满足Bj> Bi的邻居节点数量则会越来越少，也即使得ki的值不断减小。而如果采用随机选择邻居节点请求数据流，使得邻居节点j成为节点i的流数据服务节点的概率1/ki变大。可以看到，对于一个缓存值为Bu的节点u和一个缓存值为Bv的节点v，如果有Bu> Bv在随机选择策略下通常会出现Lu > Lv。特别是当Bu-原文中B的前面下角有个下标负号，作者确认是否没有该下标，确实存在，表示节点u和节点v之间的数据缓存之差。应该是Bu Bv，文章现在有问题。Bv越大，Lu -Lv也会越大，这意味着节点u和节点v的负载越不均衡。更严重的情况，如果节点u的上行带宽容量Ou小于节点v的上行带宽容量Ov，则导致节点u的上行带宽严重过载，而节点v的带宽的利用率却相对很低。
通过上述分析，可知在基于网络编码的P2P流媒体系统中，节点之间存在着一定的负载不均衡的问题。如果不对该问题进行有效的控制则会导致网络中出现较多的“热区”，而严重影响那些通过“热区”获取编码数据的节点的解码效率，从而进一步影响视频播放的质量。因此需要研究均衡节点负载的策略，尽可能避免“热区”出现。
3 过载节点的负载转移策略
3.1 网络场景说明及问题分析
本文考虑如图2所示的网络场景。
在上述采用负载转移节点的例子中，每一个请求节点所请求的带宽都不超过Bmax，除带宽请求值最大的节点最终从负载转移节点所获取的带宽正好等于请求的带宽值之外，其他请求节点所获取到的带宽比请求的带宽都要多，这样更有利于降低解码时延。对于源节点如N1，只需要分配Bmax的带宽资源并推送编码数据给负载转移节点即可实现；而对于负载转移节点需付出n・Bmax的带宽（n为带宽请求节点的个数）。上述网络编码方案的本质是将源节点的大部分带宽负载转移到负载转移节点。这对于有效降低负载过重的节点的带宽压力是很有效的。另外，本策略会增加这些负载转移节点的带宽消耗，特别当请求节点较多的时候可能会在较短时间内使得这些负载转移节点过载。因此，为了达到既转移源节点的带宽负载又减轻中间节点的负载压力的目的，必须适当增加负载转移节点的数量，并将负载压力分摊到多个负载转移节点。 定理1 对于一个带宽过载的节点需要为n个带宽请求节点服务时，若存在多个负载较轻的节点能够和过载节点及请求节点相连，则源节点从中任意选择k个中间节点作为其负载转移节点。若采用适当的网络编码方案，过载节点需分配给n个请求节点的带宽不大于k・Bmax。
证明 选择如下数据编码和传输方案。网络中每一个中间节点连接特定的若干个请求数据的节点，这里要求所有请求数据的节点能够连接到中间节点，且单位时间内请求数据的多个节点分别将Bmax的数据段以固定大小数据包的形式发送给每一个中间节点，中间节点再将收到的数据包编码并发送给和自己连接的其他节点。其他节点接收到所有编码后的数据包后再解码出原始数据包。此段逻辑不通，改后请作者确认是否正确〗要求必须将所有请求节点连接到，单位时间内源节点分别将Bmax的数据以固定大小源数据包的形式发送给每一个中间节点，然后这些中间节点再将源数据包编码发送给自己连接的请求节点；请求节点接收到所有编码后的数据包之后再解码出源数据包。这样，每一个节点都接收到不小于自己请求的带宽。而在整个过程中，源节点总共消耗了k ・Bmax的带宽。上述方案的带宽分配效率为：
当负载转移节点数量增加时，单个负载转移节点的负载压力将会大大降低，平均每一个编码节点需要消耗n・Bmax/k的带宽资源。当k值选择合理的时候，中间节点是可以负担这些带宽负载的。
3.2 基于负载转移的过载节点带宽分配模型
步骤2 对于同属于一个带宽区间的请求带宽值，取这些请求带宽值的最大值（或者该区间的最大极限值），过载节点S按照这个带宽值将编码数据传送给负载转移节点，中间节点编码后发送给所有同属于一个区间的请求节点，这样属于同一个区间的请求节点能从负载转移节点获得了不小于自己请求的带宽值的数据。按照这种方式，源节点为了满足所有n个请求节点所付出的带宽资源C为：
需要说明的是，因为在每一个区间内，所有节点请求的带宽都不大于该区间的最大值，故源节点为了满足某一区间内的所有节点的请求，它需要付出的上传带宽都不大于该区间的右侧值。比如在区间（kr・ xmax/D， （k+1）r・xmax/D]，源节点需要上传的带宽不会大于（k+1）r・xmax/D，故源节点上传的带宽不会大于D个区间带宽极值之和。进一步将式（7）化简，对于过载节点S而言，它可以获知所有请求节点向其请求的带宽值，而如果区间数量D取定后，r・xmax/D为常数，所以：
3.3 负载转移节点的选取
通过3.1～3.3节的描述，可以得到一个基于负载转移的带宽资源分配算法，该算法首先找到过载节点和负载转移节点（潜在的能够承担过载节点带宽资源负荷的节点），然后利用阶梯型网络编码方式实现负载转移。算法执行流程如下：
4 实验结果与讨论
3）图中是节点负载程度与请求节点数量关系，核实这句描述是否有问题，节点越多，分配效率越低，这个逻辑对吗，前面2）不是说随着请求节点增加，带宽分配效率显著增加吗，这两部分内容是否冲突？当图中横坐标为请求带宽节点，而非负载转移节点，核实描述是否有误？
请将这句话去掉。前后有重复描述的情况。后面一句话已经解释得很清楚。即当节点数量增加到一定值后，例如：60，带宽分配效率变化很缓慢了，同时导致节点的平均负载变化也非常缓慢。
请求带宽资源的节点数量继续增加，可以发现带宽分配效率变化非常缓慢，几乎固定不变。
.这里有笔误，应该改为“网络中节点的负载程度与请求节点数量的变化关系”
如表1所示。
5 结语
采用了网络编码的P2P流媒体应用中，在线节点容易出现的带宽资源利用不均衡的问题，本文针对此问题进行研究。先通过构建数学模型分析了节点进行资源请求和分配时候的场景，通过求解该模型得到了带宽分配区间和带宽分配效率之间的关联关系，从而给出了一种基于负载转移的带宽资源请求分配策略。另外，本文通过构建一个基于Matlab的离散事件仿真平台对策略进行验证，实验结果表明本文提出的策略能有效降低过载节点的带宽资源使用，达到均衡利用节点带宽资源的目的。
参考文献：
文献已查
[4]XIE S， LI B， KEUNG G Y， et al. Coolstreaming： design， theory and practice [J]. IEEE Transactions on Multimedia， 2007， 9（8）： 1661-1671.
[7]THOMOS N， CHAKARESKI J， FROSSARD P. Prioritized distributed video delivery with randomized network coding [J]. IEEE Transactions on Multimedia， 2011， 13（4）： 776-787.
[8]WANG M， LI B. R2： random push with random network coding in live peertopeer streaming [J]. IEEE Journal on Selected Areas in Communications， 2007， 25（9）：1655-1666.
[9]CLEJU N， THOMOS N， FROSSARD P. Selection of network coding nodes for minimal playback delay in streaming overlays [J]. IEEE Transactions on Multimedia， 2011， 13（5）： 1103-1115.