2003 International Conference on Parallel Processing Workshops (ICPPW'03)
A Simple Protocol for Dominating Set Construction in Mobile Ad Hoc Networks
Kaohsiung, Taiwan
October 06-October 09
ISBN: 0-7695-2018-9
Dominator set has been used as a virtual backbone in the wireless ad hoc networks by numerous routing and broadcast protocols. Although computing minimum dominating set is known to be a NP-complete problem, many protocols have been proposed to construct a "smaller" dominating set based on local information at individual nodes. However, these protocols are either too complicated or assume too much information at each node. In this paper, we present a Time-based Dominating Set Construction Protocol. In our protocol, each node sets up a defer timer based on the number of uncovered neighbors and determines whether or not to join the dominating set when the timer expires. The protocol is appropriate for mobile ad hoc networks because it is simple, distributed, inexpensive (i.e., with no extra messages), and easy to adopt to nodal mobility. The simulation results show that our protocol performs nicely compared with other distributed dominating set protocols.
Citation:
Donghoon Kim, Bonam Kim, Min-Te Sun, "A Simple Protocol for Dominating Set Construction in Mobile Ad Hoc Networks," icppw, pp.35, 2003 International Conference on Parallel Processing Workshops (ICPPW'03), 2003