基于超图染色的网络编码重传方案研究  

STUDY ON NETWORK CODING RETRANSMISSION SCHEME BASED ON HYPERGRAPH COLOURING

作　　者：李璐瑶[1,2] 王静[1] 戴明[1,2] 樊娜[1] 

机构地区：[1]长安大学信息工程学院,陕西西安710064 [2]中国交通通信信息中心,北京100011

出　　处：《计算机应用与软件》2015年第8期106-109,共4页Computer Applications and Software

基　　金：国家自然科学基金项目(61040005;61072064);交通运输部科技项目(2012-364-208-600)

摘　　要：考虑到现有的基于时间的网络编码重传方案具有指数复杂度,不适合大规模网络,提出一种基于超图染色的网络编码重传方案,以提高传输效率。该方案采用超图染色算法,根据数据包丢失矩阵构造超图并对其进行染色,从而确定进行网络编码的丢失数据包。仿真实验表明,基于超图染色的网络编码重传方案具有与基于时间的网络编码重传方案相同的传输效率,且计算复杂度较低。Considering that current time-based network coding retransmission scheme has exponential complexity and thus is not suitable for large-scale network,in this paper we propose a hypergraph colouring-based network coding retransmission scheme to improve the transmission efficiency. More specifically,the scheme adopts hypergraph colouring algorithm to construct the hypergraph according to the packet-loss matrix and then to colour it,so as to determine the lost packets for network coding. It is shown by simulation experiment that the hypergraph colouring-based network coding retransmission scheme can acquire almost the same transmission efficiency as the time-based network coding retransmission scheme,and has lower computational complexity.

关 键 词：超图染色 网络编码 传输效率 计算复杂度 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]