Tree-Based Virtual Backbone Construction in Mobile Ad Hoc Networks

The connected dominating set (CDS) has been extensively used for routing and broad-cast in mobile ad hoc networks. While existing CDS protocols are successful in constructing CDS of small size, they either require localized information beyond immediate neighbors, lack the mechanism to properly handle nodal mobility, or involve lengthy recovery procedure when CDS becomes corrupted. In this paper, we introduce the tree-based CDS protocols, which first elect a number of initiators distributively and then utilize timers to construct a CDS from initiators with the minimum localized information. We demonstrate that our CDS protocols are capable of maintaining CDS in the presence of changes of network topol-ogy. Depending on the number of initiators, there are two versions of our tree-based CDS protocols. The Single-Initiator (SI) works the best when the network diameter is given. On the other hand, the Multi-Initiator version (MI) built on top of SI is a localized CDS protocol and possesses all of the advantages of SI. We evaluate our protocols by both the ns-2 simulation and an analytical model. Compared with the other known CDS protocols, the simulation results demonstrate that both SI and MI produce and maintain CDS of ver