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

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.