Study On Network Coding Optimization

Network coding is a kind of novel network technology. With network coding, the intermediate nodes are allowed to code with different data and send the coded data rather than only forward the received data. Then the original data can be retrieved through decoding operation. With network coding, the multicast capacity of the network can be achieved under most environments. But sometimes only forwarding data may not.Like most other technologies, the advantage of network coding gets along with some overhead. Network coding takes more CPU operations than forwarding. The network equipments which is capable of coding are dearer than original forwarding network equipments. And of course the decoding operation also means more overhead than receiving data which is not coded. So how to reduce these overhead becomes a challenge.This thesis is about my study on this problem, how to reduce the overhead attached with network coding while keeping the network multicast rate still be max? Based on the research of using Genetic Algorithm to solve the optimization problem of network coding operation overhead, the thesis presents the problem of network overhead optimization problem of the sum cost of coding cost and link cost with network coding. After that, the thesis analyses the main parameter of this problem, presents the necessary condition of this optimization problem and discusses the different form of this problem under some applications.The main contributions of this thesis are: 1) this thesis presents some improvements to the common Genetic Algorithm. The experiment result shows that the new algorithm is more efficiency. 2) This thesis presents the problem of network overhead optimization problem of the sum cost of coding cost and link cost with network coding. This optimization takes not only the link transmission overhead but also the network coding overhead incurred by network coding into consideration.3) This thesis use two different network information flow models to formulate this problem and give the general definition of both kinds of the overhead.4) In the experiment, the thesis evaluates algorithms based on different information flow models. The experiment also derives the lower bound of the network coding overhead when our optimization is necessary.