Network coding-based reliable multicast in wireless networks

被引:30
作者
Chi, Kaikai [2 ]
Jiang, Xiaohong [1 ]
Horiguchi, Susumu [1 ]
机构
[1] Tohoku Univ, Grad Sch Informat Sci, Sendai, Miyagi 9808579, Japan
[2] Zhejiang Univ Technol, Coll Comp Sci & Technol, Hangzhou 310023, Zhejiang, Peoples R China
关键词
Wireless networks; Network coding; Reliable multicast; Physical-layer broadcast; Bandwidth saving;
D O I
10.1016/j.comnet.2010.02.010
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Reliable multicast, the lossless dissemination of data from one sender to a group of receivers, has a wide range of important applications. Recently, network coding has been applied to the reliable multicast in wireless networks, where multiple lost packets with distinct intended receivers are XOR-ed together as one packet and forwarded via single retransmission, resulting in a significant reduction of bandwidth consumption. However, the simple XOR operation cannot fully exploit the potential coding opportunities and finding the optimal set of lost packets for XOR-ing is a complex NP-complete optimization problem. In this work, we intend to move beyond the simple XOR to more general coding operations. Specifically, we propose two new schemes (a static scheme which repeatedly retransmits one coding packet until all intended receivers receive it and a dynamic scheme which updates the coding packet once one or more receivers receive it) to encode packets with more general coding operations, which not only can encode lost packets with common intended receivers together to fully exploit the potential coding opportunities but also have polynomial-time complexity. We demonstrate, through both analytical and simulation results, that the proposed schemes can more greatly reduce the bandwidth requirement than the available coding-based schemes, especially in the case of high packet loss probabilities and a larger number of receivers. This reduction can vary from a few percents to over 15% depending on the packet loss probabilities and the number of receivers. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码:1823 / 1836
页数:14
相关论文
共 30 条
[1]   Network information flow [J].
Ahlswede, R ;
Cai, N ;
Li, SYR ;
Yeung, RW .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (04) :1204-1216
[2]  
[Anonymous], IEEE INFOCOM
[3]  
[Anonymous], P 15 ACM S PAR ALG A
[4]  
[Anonymous], 3 WORKSH NETW COD TH
[5]   Throughput optimization of wireless mesh networks with MIMO links [J].
Bhatia, Randeep ;
Li, Li .
INFOCOM 2007, VOLS 1-5, 2007, :2326-+
[6]   A digital fountain approach to asynchronous reliable multicast [J].
Byers, JW ;
Luby, M ;
Mitzenmacher, M .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2002, 20 (08) :1528-1540
[7]  
Chachulski S., 2007, ACM SIGCOMM
[8]  
Fragouli C, 2006, IEEE INFOCOM SER, P75
[9]   Efficient broadcasting using network coding [J].
Fragouli, Christina ;
Widmer, Joerg ;
Le Boudec, Jean-Yves .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2008, 16 (02) :450-463
[10]  
FUJIMURA A, 2008, IEEE MILCOM