一种基于P2P内容分发系统带宽分配算法研究

张旋　李铭　李晓强　曹建民

摘 要：针对如何使混合型架构流媒体内容分发系统服务容量最大的问题，文章按照多文件分发的服务容量模型将带宽分配问题映射为背包问题，提出了利用遗传算法进行服务器带宽分配的方法，通过构造修复算子保证了解的可行性。仿真实验证明了该算法可快速提高系统服务容量。

关键词：内容分发；流媒体；带宽分配；遗传算法

近年来的研究和实践表明，结合传统内容分发网络（Content Delivery Network，CDN）和对等网络（Peer to Peer，P2P）流媒体技术的混合式分发框架在可靠性和扩展性方面发挥二者的技术互补性，逐渐成为研究的热点。混合框架中的服务器带宽分配问题是影响系统服务容量的决定性因素之一，Banerjee等[1]提出的双层拓扑分发方案OMNI，Chawathe等[2提出的预部署Proxy的Scattercast方案，以及Dongyan Xu等[3]结合了CDN和P2P流媒体分发技术提出的混合结构流媒体点播方案，通过优化骨干分发网络的组播树以降低源到端的分发时延，但在服务器带宽分配问题上普遍缺乏有效的机制。本文采用文献中提出的CDN与P2P混合分发系统通用模型，分析了区分冷热度多文件点播系统的系统服务容量[4]，将服务器带宽资源分配问题映射为背包问题，提出了基于遗传算法的带宽分配算法（Genetic Algorithm-Bandwidth Distribution Algorithm，GA-BDA），仿真实验证明该算法在执行效率上优于尽力服务的调度算法（Best Effort Based Bandwidth Distribution Algorithm，BEB-BDA）。

1 系统服务容量模型

设CDN服务器上可供点播的视频文件总数为F，视频文件fi，i∈[1，F]。CDN服务器以fi的编码率bi作为该文件的最小带宽分配单位，分配给fi的流数据频道数以xi表示，fi点播服从概率为δi的ZIPF概率分布，点播请求得到响应的概率为φi，于是单个文件fi的请求服务容纳率表示为wi=λδiφi，全局请求服务容纳率。

多文件分发时CDN服务器的带宽资源分配问题，可转换成无限的背包问题（Unbounded Knapsack Problem，UKP）。由于UKP是NP-Completed问题，其求解過程是一个NP-Hard问题。鉴于人工智能里的启发式算法对解决此类问题具有相当的优势，故引入遗传算法解决服务器带宽分配问题。

2 基于遗传算法的带宽分配算法

对于上述提出的带宽分配问题设计如下的染色体编码方案：用位二进制串来表示UKP问题中的一个变量xi，将待求解的染色体表示为长为的二进制编码串S。

目标函数：maximizewixij

约束函数：subject to bixij≤B，xi=0或1，（i=1，2，…n）

适应度函数，其中，qm=wm

2.1 遗传算子

（1）选择：分别从总体中随机抽取的T个个体构造两类个体池，再从两个池中分别选出适应度最大的两个个体作为双亲。

（2）交叉：使用均匀交叉算子作为默认的交叉算子。在均匀交叉算子中，两个双亲只有一个孩子。孩子解中的每一位都是通过拷贝双亲一方相对应的位而来，选择两个双亲里的哪一个是由一个二进制的随机变量决定第一位双亲还是第二位双亲。

（3）变异：随机的选定孩子解中的几位，使该位的值改变。本文变异概率设置为0.01。

2.2 修正算子和初始种群

本文定义的适应度函数的前提是只在可行解的解空间内进行搜索，为了保证经过交叉、变异操作后产生的解具有可行性，现引入基于简单贪心算法的启发性算子，称为修正算子。定义物品的收益率为qi/wi，根据贪心思想，物品的收益率越大，算法产生的解中该物品相对应的那一位变量为1的概率就越大，修正算子依据收益率决定孩子解中的每个变量的取值。修正算子由两部分操作组成，第一步是Drop操作，按物品收益率递增的顺序遍历每个变量，一旦发现该解不可行但变量为1，置该位变量为0。第二步是Add操作，按收益率递减的顺序遍历每个变量，如果发现该解可行但变量为0，置该位变量为1。Drop操作的目的是从不可行解中获取可行的解，Add操作的目的是提高可行解的适应度。为使修正算子达到较高的运行效率，一般需要对每个问题做预处理，本算法采取按照物品收益率做降序排序，显然此排序的时间复杂度为O（n2），且作为预处理只需运行一次，不影响迭代运算的时间复杂度。

为了获得足够的多样性，初始种群为随机产生，初始种群的大小设为N=100。每个初始的可行解是这样构造的，随机选择一个变量，如果该解是可行的，将该变量置为1，直到选中的变量不能加入到解中。

3 仿真实验

采用C++编程给出了BEB-BDA算法和GA-BDA算法的性能仿真，其中仿真参数设定为：P2P系统中Peer节点总数M为300 000个，视频文件总数为F为100，视频文件编码率为300 kbps、400 kbps和500 kbps的视频文件分别占30%、30%和40%。视频播放时长均为4 800 s，Peer节点平均上传带宽为512 kbps，CDN服务器的服务带宽B为100 Mbps，Peer节点进入系统的到达率为λ为20个/s，并且开始点播。将文件的访问热度按照降序进行排列，第i个文件ID为i。

Peer节点按概率δi选中所点播的视频文件fi，，α=可视为Peer节点上传带宽的期望值，本文取值为0.7。

以服务器尽力服务的带宽分配算法（BEB-BDA）与本文提出的GA-BDA算法进行比较，仿真结果为重复试验10次之后的平均值。

图1为GA-BDA算法和BEB-BDA算法对全局服务容纳率的比较。从图1可以看出，在时间刻度t=7时，GA-BDA算法的全局服务容纳率达到了9.8。与BEB-BDA算法相比较，GA-BDA算法提高了P2P系统服务请求接受能力。对于BEB-BDA分配算法，由于其不考虑不同冷热度视频文件的访问对P2P系统总体服务能力的影响，具有较高访问热度的文件由于其对应的服务容量不能快速增加，导致在初始时间刻度t上保持较低的全局服务容纳率并且增长速度较慢，在t=15时才达到最大的值。从仿真结果可知，GA-BDA算法根据不同视频文件热度的带宽分配方法可快速增加系统的总体服务能力。

4 结语

在深入分析混合框架点播系统服务容量模型的基础上，通过利用遗传算法的寻优特性，设计了适用于P2P系统服务器带宽分配问题的遗传编码方案和遗传算子，提出了基于遗传算法的带宽分配算法（GA-BDA），该算法能够提高系统全局容纳率。对于点播热度不同的节目，该算法克服了服务器负载和网络带宽需求瓶颈等问题。通过仿真实验对不同访问热度模式下多文件P2P系统全局请求服务容纳率进行了对比试验，实验结果表明与BEB-BDA算法相比较，GA-BDA算法可快速提高系统服务容量，并且该算法简单、运行可靠，可以增强P2P系统的服务能力。

[参考文献]

[1]BANERJEE S，KOMMAREDDY C，KAR K，et al. Construction of an efficient overlay multicast infrastructure for real-time applications[J].Proceedings of IEEE Infocom Apr，2003（3）：1521-1531.

[2]K SELGUK CANDAN，YUSUF AKCA，AND WEN SYAN LI .An architecture for internet content distribution as an infrastructure service[J].Web Content Delivery，2017（10）：215-216.

[3]XU D，CHAI H K，ROSENBERG C，et al. Analysis of a hybrid architecture for cost-effective streaming media distribution[C].Electronic Imaging，2003.

[4]段翰聪，卢显良.P2P流媒体分发技术研究[D].成都：电子科技大学，2007.