DocumentCode
1480370
Title
An efficient approximation for minimum latency broadcast in multi-channel multi-hop wireless networks
Author
Shan, Shan ; Wang, Wei ; Du, Hongjie ; Gao, Xiaofeng ; Wu, Weili
Author_Institution
Dept. of Comput. Sci., Univ. of Texas at Dallas, Richardson, TX, USA
Volume
14
Issue
5
fYear
2010
fDate
5/1/2010 12:00:00 AM
Firstpage
435
Lastpage
437
Abstract
In this paper, we discuss the minimum latency broadcast problem (MLB) in multi-channel multi-hop wireless networks (MLB-MC). This problem is NP-hard since its special version, MLB in single-channel network (MLB-SC) is proved to be NP-hard . We design an efficient approximation for MLB-MC, analyze its approximation ratio, and evaluate its performance via numerical experiments. Furthermore, we give a general theorem as an upper bound to compare the performance between approximations for MLB-MC and MLB-SC.
Keywords
broadcasting; computational complexity; radio networks; NP-hard problem; minimum latency broadcast; multichannel multihop wireless networks; single channel network; Bandwidth; Broadcasting; Computer science; Delay; Interference; Performance analysis; Spread spectrum communication; Upper bound; Wireless networks; Wireless sensor networks; Wireless network, broadcast, approximation;
fLanguage
English
Journal_Title
Communications Letters, IEEE
Publisher
ieee
ISSN
1089-7798
Type
jour
DOI
10.1109/LCOMM.2010.05.100070
Filename
5456057
Link To Document