Network Coding-based Reliable Broadcast Transmission in Wireless Networks  

作　　者：Wang Jing Chi Kaikai Wang Xinmei 

机构地区：[1]School of Information Engineering, Chang an University, Xi an 710064, China [2]College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China [3]State Key Lab. of Integrated Service Networks, Xidian University, Xi an 710071, China

出　　处：《China Communications》2010年第2期71-77,共7页中国通信（英文版）

基　　金：supported by the National Natural Science Foundation of China (60502046, 60573034);863 Foundation of China (2007AA01Z215)

摘　　要：Recently, network coding has been applied to the loss recovery of reliable broadcast transmission in wireless networks. Since it was proved that fi nding the optimal set of lost packets for XOR-ing is a complex NP-complete problem, the available time-based retransmission scheme and its enhanced retransmission scheme have exponential computational complexity and thus are not scalable to large networks. In this paper, we present an efficient heuristic scheme based on hypergraph coloring and also its enhanced heuristic scheme to improve the transmission efficiency. Basically, our proposed schemes fi rst create a hypergraph according to the packet-loss matrix. Then our schemes solve the problem of generating XORed packets by coloring the edges of hypergraph. Extensive simulation results demonstrate that, the heuristic scheme based on hypergraph coloring and its enhanced scheme can achieve almost the same transmission efficiency as the available ones, but have much lower computational complexity, which is very important for the wireless devices without high computation capacity.Recently, network coding has been applied to the loss recovery of reliable broadcast transmission in wireless networks. Since it was proved that finding the optimal set of lost packets for XOR-ing is a complex NP-complete problem, the available time-based retransmission scheme and its enhanced retransmission scheme have ex- ponential computational complexity and thus are not scalable to large networks. In this paper, we present an efficient heuristic scheme based on hypergraph coloring and also its enhanced heuristic scheme to improve the transmission efficiency. Basically, our proposed schemes first create a hypergraph according to the packet-loss matrix. Then our schemes solve the problem of generating XOR- ed packets by coloring the edges of hypergraph. Extensive simulation results demonstrate that, the heuristic scheme based on hypergraph coloring and its enhanced scheme can achieve almost the same transmission efficiency as the available ones, but have much lower computational complexity, which is very important for the wireless devices without high computation capacity.

关 键 词：network coding reliable broadcast wireless networks transmission bandwidth computational complexity 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP393.08[自动化与计算机技术—计算机科学与技术]