Construction K-Dominating Set with Multiple Relaying Technique in Wireless Mobile Ad Hoc Networks

The (k, r)-dominating set problem, (k, r)-DS, is defined as the problem of selecting a minimum cardinality vertex set D (dominating nodes, also referred as cluster-heads) of a graph G=(V, E), such that every vertex u not in D is in r hops from at least k (multiple domination parameter) vertices in D. In mobile ad hoc networks (MANETs), computing dominating set should be distributed, because the topology may change frequently. In this paper, we present a distributed clustering algorithm based on MPR technique, named MPR-KD, to addressing redundancy of dominating nodes in 1-hop for MANETs. 1-CDS is still supported in MPR-KD and extensive simulations are conducted to compare this algorithm with another distributed algorithm DKR. Simulation results show that the new algorithm outperforms DKR in terms of number of dominating nodes, both in dense and sparse networks.