Distributed dominant pruning in ad hoc networks

Efficient routing among mobile hosts is an important function in ad hoc networks. Routing based on a connected dominating set is a promising approach, where the search space for a route is reduced to the hosts in the set. A set is dominating if all the hosts are either in the set or neighbors of hosts in the set. The efficiency of dominating-set-based routing mainly depends on the overhead introduced in the formation of the dominating set and the size of the dominating set. In this paper, we first review a distributed formation of a connected dominating set called marking process and dominating-set-based routing. Then a generalization of two existing rules (called rules 1 and 2). We prove that the vertex set derived by applying rule k is still a connected dominating set. When implemented with local neighborhood information. Rule k is more effective in reducing the dominating set derived from the marking process than the combination of rules 1 and 2, and has the same communication complexity and less computation complexity. Simulation results confirm that rule k outperforms rules 1 and 2, especially in relatively dense networks with unidirectional links.