计算机工程 ›› 2010, Vol. 36 ›› Issue (9): 94-96.doi: 10.3969/j.issn.1000-3428.2010.09.032

• 网络与通信 • 上一篇    下一篇

单源最大可解线性网络编码的近似构造

刘冠群   

  1. (复旦大学计算机科学技术学院,上海 200433)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-05-05 发布日期:2010-05-05

Approximate Construction of Maximum Decodable Linear Network Coding for Single Source

LIU Guan-qun   

  1. (School of Computer Science, Fudan University, Shanghai 200433)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-05-05 Published:2010-05-05

摘要: 在传统线性网络编码的基础上提出一种网络编码,即最大可解线性网络编码,并证明对于一个给定网络,判定是否存在一个最大可解线性网络编码是NP-困难问题,给出单源情况下该网络编码的启发式近似构造算法。实验模拟证明,相比传统线性多播网络编码,采用最大可解线性网络编码的网络容量有了较大的提高。

关键词: 网络编码, 最大可解, 复杂性, 构造

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

中图分类号: