A new local algorithm for backbone formation in ad hoc networks
Hossein Kassaei, Mona Mehrandish, Lata Narayanan, Jaroslav Opatrný · 2009
Several researchers have considered using a routing backbone to perform routing in a wireless ad hoc network. Such a backbone can be created by finding a connected dominating set (CDS) in the underlying graph. We present a new distributed local algorithm to find a CDS in a unit disk graph (UDG), which is a commonly used model for ad hoc wireless networks. We assume that the nodes have information about their locations. The CDS produced by our algorithm is provably at most a constant times the size of the optimal CDS. We evaluate the performance of our algorithm in comparison with previously proposed algorithms in [6],[7],[15] and [17] via extensive simulations on randomly generated UDGs. Our results show that the CDS produced by our algorithm is 25% better than the next-best algorithm (which is however not local), and 28% better than the next-best local algorithm. Our algorithm is also computationally efficient and highly scalable.