On constructing k-connected k-dominating set in wireless ad hoc and sensor networks

An important problem in wireless ad hoc and sensor networks is to select a few nodes to form a virtual backbone that supports routing and other tasks such as area monitoring. Previous work in this area has focused on selecting a small virtual backbone for high efficiency. In this paper, we propose the construction of a k-connected k-dominating set (k-CDS) as a backbone to balance efficiency and fault tolerance. Four localized k-CDS construction protocols are proposed. The first protocol randomly selects virtual backbone nodes with a given probability p(k), where p(k) depends on the value of k and network condition, such as network size and node density. The second one maintains a fixed backbone node degree of B-k, where B-k also depends on the network condition. The third protocol is a deterministic approach. It extends Wu and Dai's coverage condition, which is originally designed for 1-CDS construction, to ensure the formation of a k-CDS. The last protocol is a hybrid of probabilistic and deterministic approaches. It provides a generic framework that can convert many existing CDS algorithms into k-CDS algorithms. These protocols are evaluated via a simulation study. (C) 2006 Elsevier Inc. All rights reserved.