一种改进的多播网络编码算法

Improved multicast network coding algorithm

在多播网络通信中,网络编码的应用,实现了最大流最小割定理所决定的多播传输的最大理论传输容量。对这一问题,可采用线性multicast,线性broadcast,线性dispersion,以及generic等线性网络编码构造算法进行求解。但这些方法,计算复杂度较高。在研究generic线性网络编码算法的基础上,结合离散路由的使用,对其进行了改进,提出了一种改进的多播网络编码算法,并给出了算法的合理性证明。复杂度分析表明,该算法较generic线性网络编码算法,复杂度有显著的下降。

The application of network coding in the multicast communication network,which has achieved the maximum value of network traffic determined by the Max-flow and Min-cut theorem.The problem can be solved by linear network coding algorithms such as linear multicast, linear brodcast, linear dispersion as well as generic linear network coding algorithm. However,all of these methods have high degrees of computational complexity.Based on the generic linear network coding algorithm, and combined with the usage of discrete routing, a novel improved multicast network coding algorithm is proposed in this paper.The rationality of the algorithm has been proved.Complexity analysis indicates that, compared with generic algorithm,the algorithm in this paper reduces the computational complexity obviously.