TY - JOUR
T1 - Network coding based schemes for imperfect wireless packet retransmission problems
T2 - A divide and conquer approach
AU - Gao, Zhenguo
AU - Yang, Mei
AU - Wang, Jianping
AU - Nahrstedt, Klara
AU - Cai, Shaobin
AU - Li, Xiang
AU - Wang, Huiqiang
N1 - Funding Information:
Zhenguo Gao is a professor in Harbin Engineering University, Harbin, China. He is now a visiting scholar in University of Illinois at Urbana-Champaign. He received his B.S. and M.S. degree in Mechanical and Electrical Engineering from Harbin Institute of Technology, Harbin, China, in 1999 and 2001, respectively. Then he received his Ph.D. degree in Computer Architecture from Harbin Institute of Technology, Harbin, China, in 2006. He is now a faculty member of College of Automation of Harbin Engineering University. His research interests include wireless ad hoc network, cognitive radio network, network cod-ing, game theory application, etc. He is a senior member of China Computer Federation. He received National Science Foundation Career Award in 2007 and Outstanding Junior Faculty Award of Harbin Engi-neering University in 2008. He is severing as a viewer for project pro-posals for National science foundation of China, Ministry of Education of China, Science Foundation of HeiLongJiang Province, China. He is also serving as a viewer for some journals including IEEE Transactions on Mobile Computing, Wireless Networks and Mobile Computing, Journal of Parallel and Distributed Computing, IETE Technical Review, Journal of Electronics (Chinese), Journal of Astronautics (Chinese).
Funding Information:
Acknowledgments We deeply appreciate the valuable comments and suggestions made by the anonymous reviewers, which have significantly helped us to improve the quality of the manuscript. Thanks to Miss Boumediene Latifa for improving the representation of the manuscript. This work is jointly supported by: National Science Foundation of China (60703090, 60603059, 60973027, 90718003), National High Technology Research and Development Program of China (863) (2007AA01Z401), Fundamental Research Funds for the Central Universities (HEUCFT1007), Young Promising Researcher Supporting Project of Harbin Engineering University (No. 0811), and Natural Science Foundation of Heilongjiang Province (No. F200902).
Funding Information:
Klara Nahrstedt is a Ralph M. and Catherine V. Fisher Profes-sor at the University of Illinois at Urbana-Champaign, Computer Science Department. Her research interests are directed towards mul-timedia middleware systems, quality of service (QoS), QoS routing, QoS-aware resource management in distributed multimedia systems, and multimedia security. She is the coauthor of the widely used mul-timedia book ‘Multimedia: Computing, Communications and Applica-tions’ published by Prentice Hall, the recipient of the Early NSF Career Award, the Junior Xerox Award, and the IEEE Communication Soci-ety Leonard Abraham Award for Research Achievements. She is the editor-in-chief of the ACM/Springer Multimedia Systems Journal, and the Ralph and Catherine Fisher Associate Professor. Klara Nahrstedt received her BA in mathematics from Humboldt University, Berlin, in 1984, and M.Sc. degree in numerical analysis from the same university in 1985. She was a research scientist in the Institute for Informatik in Berlin until 1990. In 1995 she received her Ph.D. from the University of Pennsylvania in the Department of Computer and Information Science. She is the member of ACM and IEEE.
PY - 2012/2
Y1 - 2012/2
N2 - NC (Network Coding) provides a new approach to packet retransmission problems in wireless networks, which are named as WPRTPs (Wireless Packet Retransmission Problems) in this paper. Some research has been conducted on P-WPRTPs (Perfect WPRTPs) where, for one receiver, a packet is either being requested by or already known to it. However, very few efforts are focused on IP-WPRTPs (Imperfect WPRTPs) where, for one receiver, a packet can be neither requested by nor already known to it. In this paper, we focus on IP-WPRTPs. Firstly, a WPRTP reduction theorem for simplifying WPRTPs is proposed and proved. Then, the upper and lower bounds of the number of necessary packet transmissions in optimal NC-based solutions to IP-WPRTPs are analyzed. Next, a scheme named as IP-WPRTP-DC (Divide and Conquer based scheme for IP-WPRTPs) is proposed based on the WPRTP reduction theorem using a divide and conquer approach. Extensive simulations show that the IP-WPRTP-DC scheme is effective in saving the number of packet transmissions for solving IP-WPRTPs.
AB - NC (Network Coding) provides a new approach to packet retransmission problems in wireless networks, which are named as WPRTPs (Wireless Packet Retransmission Problems) in this paper. Some research has been conducted on P-WPRTPs (Perfect WPRTPs) where, for one receiver, a packet is either being requested by or already known to it. However, very few efforts are focused on IP-WPRTPs (Imperfect WPRTPs) where, for one receiver, a packet can be neither requested by nor already known to it. In this paper, we focus on IP-WPRTPs. Firstly, a WPRTP reduction theorem for simplifying WPRTPs is proposed and proved. Then, the upper and lower bounds of the number of necessary packet transmissions in optimal NC-based solutions to IP-WPRTPs are analyzed. Next, a scheme named as IP-WPRTP-DC (Divide and Conquer based scheme for IP-WPRTPs) is proposed based on the WPRTP reduction theorem using a divide and conquer approach. Extensive simulations show that the IP-WPRTP-DC scheme is effective in saving the number of packet transmissions for solving IP-WPRTPs.
KW - Divide and conquer approach
KW - Imperfect wireless packet retransmission problems
KW - Problem reduction
KW - Random network coding
UR - http://www.scopus.com/inward/record.url?scp=84856714749&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84856714749&partnerID=8YFLogxK
U2 - 10.1007/s11277-010-0102-9
DO - 10.1007/s11277-010-0102-9
M3 - Article
AN - SCOPUS:84856714749
VL - 62
SP - 937
EP - 958
JO - Wireless Personal Communications
JF - Wireless Personal Communications
SN - 0929-6212
IS - 4
ER -