On Constructing k-Connected k-Dominating Set in Wireless Networks

Abstract

An important problem in wireless networks, such as 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. We propose to construct a k-connected k-dominating set (k-CDS) as a backbone to balance efficiency and fault tolerance. Three localized k-CDS construction protocols are proposed. The first protocol randomly selects virtual backbone nodes with a given probability p/sub k/, where p/sub k/ depends on network condition and the value of k. The second 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.