An Efficient Approximation for Minimum Latency Broadcast in Multi-Channel Multi-Hop Wireless Networks

作者：Shan Shan^*; Wang Wei; Du Hongjie; Gao Xiaofeng; Wu Weili

来源：IEEE Communications Letters, 2010, 14(5): 435-437.

DOI：10.1109/LCOMM.2010.05.100070

• Wireless network
• broadcast
• approximation

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 [1]. 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.

• 出版日期2010-5
• 单位西安交通大学