Issue No.09 - September (2006 vol.5)
Jie Wu , IEEE
Fai Dai , IEEE
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TMC.2006.140
Recently, the use of a virtual backbone in various applications in mobile ad hoc networks (MANETs) has become popular. These applications include topology management, point and area coverage, and routing protocol design. In a MANET, one challenging issue is to construct a virtual backbone in a distributed and localized way while balancing several conflicting objectives: small approximation ratio, fast convergence, and low computation cost. Many existing distributed and localized algorithms select a virtual backbone without resorting to global or geographical information. However, these algorithms incur a high computation cost in a dense network. In this paper, we propose a distributed solution based on reducing the density of the network using two mechanisms: clustering and adjustable transmission range. By using adjustable transmission range, we also achieve another objective, energy-efficient design, as a by-product. As an application, we show an efficient broadcast scheme where nodes (and only nodes) in a virtual backbone are used to forward the broadcast message. The virtual backbone is constructed using Wu and Li's marking process  and the proposed density reduction process. The application of the density reduction process to other localized algorithms is also discussed. The efficiency of our approach is confirmed through both analytical and simulation study.
Adjustable transmission range, broadcasting, clustering, connected dominating set (CDS), energy efficiency, mobile ad hoc networks (MANETs).
Jie Wu, Fai Dai, "Virtual Backbone Construction in MANETs Using Adjustable Transmission Ranges", IEEE Transactions on Mobile Computing, vol.5, no. 9, pp. 1188-1200, September 2006, doi:10.1109/TMC.2006.140