一种改进的最小代价网络编码算法  

An improved algorithm for minimal cost network coding

作　　者：陶少国[1] 黄佳庆[1] 杨宗凯[1] 程文青[1] 

机构地区：[1]华中科技大学电子与信息工程系,湖北武汉430074

出　　处：《华中科技大学学报（自然科学版）》2008年第5期1-4,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60572049);华为公司科技基金资助项目(YJCB2006049RE)

摘　　要：分析了网络编码内在特性,指出网络编码区别于传统多播并提升多播传输性能的根本原因在于网络中存在被不同传输路径所重用的关键链路.通过在构建网络编码多播的传输路径时形成较少的关键链路,提出了一种基于关键链路的最小代价网络编码算法.该算法是在最大流算法的基础上加以改进的,并结合了网络增广链和最小截集的性质,是一种有效的最小代价网络编码算法.基于随机网络的仿真实验证明,在实现多播理论容量的前提下,该算法能有效降低网络编码的代价.This paper analyzed the inherent characteristics of network coding, and concludes that the key reason of network coding improving the performance of multicast communication is that some key links were shared by different paths in the multicast network. Reducing the number of key links at the same time of constructing transmission paths is an effective way to minimize the additional cost of network coding. Following this idea, a key links-based minimal cost network coding algorithm is proposed. The algorithm is based on the improved maximum flow theorem and complies with the properties of augmenting paths. The random network-based simulation results show that the proposed algorithm reduces the cost of network coding obviously while achieving the theoretical multicast capacity.

关 键 词：网络编码 多播 最大流 最小代价 关键链路 理论容量 

分 类 号：TN911.22[电子电信—通信与信息系统]