Implementing a Connected Dominating Set Algorithm for Clustering Mobile Ad Hoc Networks

Advances in network technology have tremendously changed the way people communicate. The relatively recent introduction of wireless networking technology has the potential to play an even more influential role in our daily lives. However, the nature of wireless technology makes it a more difficult platform on which to build useful systems. Some particularly troubling aspects of wireless networks include high mobility, frequent failures, limited power, and low bandwidth. A core component of a networked system is its routing protocol. Several ad-hoc wireless routing protocols have been proposed which depend on a flood-and-cache design. However, these algorithms suffer from scalability problems whenever the hit rate in the cache is low, such as when most connections are short-lived. This paper describes the design and implementation of a Deployable Connected Dominating Set (DCDS) algorithm. As in other CDS algorithms, DCDS provides a scalable routing scheme by constructing and maintaining a backbone across the network. To make our CDS algorithm truly deployable in an IEEE 802.11 network, we eliminate three unrealistic assumptions on which previous designs are based: reliable broadcast, accurate neighbouring information, and a static setup phase. We have implemented the DCDS algorithm and simulated it using Glomosim. The evaluations show that DCDS has significantly better scalability than AODV. We also show that our algorithm can maintain an effective backbone which appropriately balances setup time and size.