| 摘要: |
| 在多对单传输模式下,数据分配是P2P分层流媒体中的核心问题.为了提高请求节点服务质量,同时也为了减少对Root节点带宽的占用,分两种情形予以讨论.一种是Root节点不参与的情形,其目标是最大化请求节点的服务质量.对此提出了一种基于多叉树搜索裁剪的精确算法和一种启发式近似算法.另一种是Root节点可参与的情形,其目标是在满足请求节点服务质量的同时,最大化节约Root节点的带宽资源.分析了该情形下目标问题的复杂性,提出一种启发式近似算法.仿真实验表明,在不同参数条件下,所提出的算法比同类算法都有性能上的改进. |
| 关键词: P2P 分层流媒体 数据分配 NP难 算法 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60433040, 90104001 (国家自然科学基金); the National Grand Fundamental Research 973 Program of China under Grant No.2003CB314002 (国家重点基础研究发展规划(973)) |
|
| Data Allocation Algorithms in Layered P2P Streaming |
|
LIU Ya-Jie,ZHANG He-Ying,DOU Wen-Hua,CHEN Jun-Feng
|
| Abstract: |
| Data allocation is a key problem in layered peer-to-peer streaming with the pattern of multiple senders and single receiver. To improve the requesting nodes’ streaming qualities and to reduce the bandwidth consumption of the root node, the above problem is discussed in two scenarios. The first scenario is that the root node doesn’t participate in the allocation session, and the allocation goal is to maximize the requesting nodes’ streaming qualities. A search and cut accurate algorithm and a heuristic approximation algorithm are presented. The second scenario is with the root node’s participation, and the goal is to satisfy the request nodes’ streaming qualities and to maximally save the bandwidth consumption of the root node. The problem’s computing complexity in the latter scenario is analyzed and a heuristic approximation algorithm is also presented. Simulation studies show that the proposed algorithms have improved performances than the related proposed algorithms with different parameters. |
| Key words: P2P layered streaming data allocation NP hard algorithm |
