Abstract:
Based on the linear network coding, this paper proposes the maximum decodable linear network coding. It proves that whether there exists a maximum decodable linear network code for a given network is NP-hard, and gives an approximate polynomial algorithm with a heuristic rule to construct such a network code. Simulation proves that the maximum decodable linear network coding helps to gain better network capacity.
Key words:
network coding,
maximum decodable,
complexity,
construction
摘要: 在传统线性网络编码的基础上提出一种网络编码,即最大可解线性网络编码,并证明对于一个给定网络,判定是否存在一个最大可解线性网络编码是NP-困难问题,给出单源情况下该网络编码的启发式近似构造算法。实验模拟证明,相比传统线性多播网络编码,采用最大可解线性网络编码的网络容量有了较大的提高。
关键词:
网络编码,
最大可解,
复杂性,
构造
CLC Number:
LIU Guan-qun. Approximate Construction of Maximum Decodable Linear Network Coding for Single Source[J]. Computer Engineering, 2010, 36(9): 94-96.
刘冠群. 单源最大可解线性网络编码的近似构造[J]. 计算机工程, 2010, 36(9): 94-96.