DocumentCode :
1094492
Title :
Efficient Directional Network Backbone Construction in Mobile Ad Hoc Networks
Author :
Yang, Shuhui ; Wu, Jie ; Dai, Fei
Author_Institution :
Dept. of Comput. Sci., Rensselaer Polytech. Inst., Troy, NY
Volume :
19
Issue :
12
fYear :
2008
Firstpage :
1601
Lastpage :
1613
Abstract :
In this paper, we consider the issue of constructing an energy-efficient virtual network backbone in mobile ad hoc networks (MANETs) for broadcasting applications using directional antennas. In directional antenna models, the transmission/reception range is divided into several sectors and one or more sectors can be switched on for transmission. Therefore, data forwarding can be restricted to certain directions (sectors), and both energy consumption and interference can be reduced. We develop the notation of directional network backbone using the directional antenna model, and form the problem of the directional connected dominating set (DCDS) which is an extreme case of the directional network backbone using an unlimited number of directional antennas. The minimum DCDS problem is proved to be NP-complete. A localized heuristic algorithm for constructing a small DCDS and two extensions of the algorithm are proposed. Performance analysis includes an analytical study in terms of an approximation ratio and a simulation study on the proposed algorithms using both a custom simulator and ns2.
Keywords :
ad hoc networks; computational complexity; directive antennas; radio broadcasting; NP-complete problem; broadcasting applications; data forwarding; directional connected dominating set; directional network backbone construction; energy-efficient virtual network backbone; localized heuristic algorithm; mobile ad hoc networks; Simulation; Wireless systems;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/TPDS.2008.43
Filename :
4468704
Link To Document :
بازگشت