ISSN 1000-1239 CN 11-1777/TP

• 论文 • 上一篇    下一篇

网络编码下的编码开销-链路开销联合优化

邓亮 赵进 王新   

  1. (复旦大学计算机科学技术学院 上海 200433) (综合业务网理论及关键技术国家重点实验室 西安 710071) (jzhao@fudan.edu.cn)
  • 出版日期: 2010-03-15

On the Joint Optimization of Coding Cost and Link Cost with Network Coding

Deng Liang, Zhao Jin, and Wang Xin   

  1. (School of Computer Science, Fudan University, Shanghai 200433) (State Key Laboratory of Integrated Service Networks, Xian 710071)
  • Online: 2010-03-15

摘要: 网络编码是一种新的网络传输技术,能够充分利用网络的理论组播速率上限.讨论了在网络编码下综合考虑编码开销和网络链路开销的网络总开销优化问题,将由网络编码引起的编码开销同样纳入优化问题的考虑范围.给出了2种各有优劣的网络信息流模型描述这一问题,并在不同模型下定义了2种开销的一般形式.由于这一优化问题属于NP难问题,目前一般采用启发式算法获得近似的优化解.随后的实验中,在不同规模的拓扑下对比了基于2种不同信息流模型的启发式算法的性能.由于考虑了编码开销使得联合优化问题远比链路开销优化问题复杂,模拟实验显示,只有当编码开销与链路开销价值系数之比达到1000以上时,才能获得比单纯链路优化更小的总开销.在提出基于遗传算法的方案之前,还简单地讨论了联合优化问题的复杂度.

关键词: 网络编码, 联合优化, 编码开销, 遗传算法, 网络信息流

Abstract: Network coding is a kind of novel network transmission technology, which can achieve the network multicast capacity. In this paper, an overhead optimization problem (OOS) is presented to minimize the sum cost of network coding and network link in networks with network coding. This optimization takes not only the link transmission overhead but also the coding overhead incurred by network coding into consideration. By using two different network information flow models, which are the receivers data flow mixture model and the data element flow model, the general forms of both kinds of overhead are presented separately. As this problem is NP-hard, only the approximately optimized solution can be got through heuristic algorithms. In the experiments, different genetic algorithms performance are evaluated under two different information flow models and different random generated topologies. Because it makes the optimization problem even more complex that takes the network coding overhead into consideration, the computed approximate solution may be poorer than only considering the network link cost. Simulation results show that only under the condition of the overhead coefficient γ>1000, the joint optimization can get a better solution. This result may have considerable importance when network coding comes into practice in the future.

Key words: network coding, joint optimization, coding overhead, genetic algorithm, network information flow