A timer-based protocol for connected dominating set construction in IEEE 802.11 multihop mobile ad hoc networks

Connected dominating set has been used widely in multihop ad hoc networks (MANET) by numerous routing, broadcast and collision avoidance protocols. Although computing minimum connected dominating set is known to be NP-hard, many protocols have been proposed to construct a suboptimal dominating set. However, these protocols are either too complicated, needing nonlocal information, or not adaptive to topology changes. In this paper, we present a MAC-layer timer-based connected dominating set construction protocol. In our protocol, candidate nodes set up a timer based on the number of uncovered neighbors and determine whether or not to join the dominating set when the timer expires. The protocol is simple, distributed, inexpensive, and adaptive to station mobility. The simulation results show that our protocol can construct connected dominating set using 35% to 60% less nodes than other distributed connected dominating set protocols.