Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

2.4 CONNECTED DOMINATING SETS AS BACKBONES

Connected dominating sets are one of the primary techniques used to build backbones for wireless sensor and ad hoc networks. The concept of CDS can be briefly introduced as follows. A dominating set (DS) is a subset of the vertices of a graph where every vertex in the graph is either in the subset or is adjacent to at least one vertex in the subset. A CDS is a connected DS. The nodes in CDS are called dominators, while other nodes are called dominatees. There are several metrics used to evaluate the quality of a backbone protocol. They evaluate its properties such as backbone size, protocol duration, message overhead and backbone robustness (Basagni et al., 2006). It is normally desirable to construct a backbone with the smallest size possible and thus prolong the lifetime of the network and alleviate congestion. That is, it is useful to find the minimum connected dominating set (MCDS). However, finding the MCDS in general graphs has been shown to be equivalent to the set cover problem which is NP-hard (Garey and Johnson, 1978). The MCDS remains NP-hard even in UDGs (Clark et al., 1990). Therefore, approximation algorithms and heuristic algorithms have been proposed in literature to solve the problem. Approximation algorithms are normally evaluated by the approximation/performance ratio, which is upper bound on the ratio of the algorithm's performance to the optimal algorithm's performance. Algorithms introduced next can be classified ...