TV-Anytime服务器网络中一个映射问题的启发式算法  

Heuristic Solutions for A Mapping Problem in A TV-Anytime Server Network

作　　者：杜鹏[1,2] 周笑波[1,2] 谢立[1,2] 

机构地区：[1]南京大学计算机软件新技术国家重点实验室,南京210093 [2]南京大学计算机科学与技术系,南京210093

出　　处：《计算机学报》2001年第10期1009-1017,共9页Chinese Journal of Computers

摘　　要：介绍了一个称为 TV - Anytim e的新型宽带媒体服务 ,提出了一个基于层次型服务器网络之上的大规模TV- Anytime系统模型 .着重地研究了其中一个关键问题——服务器网络的影像对象映射问题 ,并形式化地将其定义为一个组合优化问题 .基于服务器网络的总存储容量、连接服务器结点之间的主干网通信带宽、用户的服务请求模式 ,来考虑尽大化服务器网络可提供的总服务质量 .给出了基于模拟退火的启发式算法集 ,并基于一套映射问题的基准集实例对算法进行了模拟和性能分析 .算法得到近似最优的方案 .A hierarchical architecture of server network is proposed to support a metropolitan TV-Anytime system. A key issue, video objects mapping problem in such a distributed server network, is studied and formulated as a combinatorial optimization problem. It takes total storage capacity of the server network, communication bandwidth of the backbone networks and access patterns into account. The objective is to provide each requested video stream by use of the highest possible encoding bit-rate. We identify it as the Quality of Service here. A nice feature of media is the fact that a single video stream can be encoded in different bit-rates, providing different presentation quality. It also uses some different storage capacities and communication bandwidths. Thus, the tradeoff that has to be solved by the mapping problem is to provide each client the selected media assets in the highest possible quality, and take the restrictions imposed by the underlying hardware into account. We present a number of heuristic methods based on simulated annealing for the solution of this video object mapping problem. A three-step initial algorithm is proposed to work out an initial solution. A family of two-phase neighborhood structure algorithm is used to find the near to optimal solutions. We use a parallel simulated annealing library (parSA) to test a set of benchmark instances. The performance of presented methods is evaluated by use of the set of benchmark instances. It shows that the solutions based on parSA can get desirable performance and reach an approximately optimal solution in a short time. The performance also reveals that a more effective system could be obtained by redundant connections of server networks and tracing routing.

关 键 词：TV-Anytime 影像对象 映射 编码比特率 层次型服务器网络 启发式算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]