## 6 Clustering, Virtual Backbone and Minimum Connected Dominating Set
### Cluster Routing Protocols  
Clustering is an effective way to achieve efficient routing in WSNs [4; 76]. It can reduce the communication overhead, and simplify routing and management operations in densely deployed WSNs. Under clustering routing, the whole WSN is partitioned into several clusters, each of which contains nodes in close proximity. In each cluster, there is a cluster head. Inter-cluster communications can only occur between cluster heads, hence nodes in different clusters must connect to their cluster heads first if they need to communicate with each other. Examples of cluster-based routing schemes include LEACH [77], HCR [78], CBRP [79], and CEDAR [80]. CEDAR and CBRP are general cluster-based routing algorithms for wireless ad hoc networks, while LEACH and its extension HCR are specialized for WSNs. Other cluster-based routing algorithms for WSNs include TEEN [81] and APTEEN [82]. The usage of cluster-based routing in WSNs is also motivated by the requirements of in-network processing and data aggregation to reduce energy consumption, as such operations can be spontaneously performed at cluster head nodes. It should be noted that once the clusters are formed in a WSN, traditional proactive routing schemes such as distance vector routing and link state routing, as well as reactive routing approaches such as DSR [83] and AODV [84] can be used among those cluster head nodes, either for routing information updates or for data delivery. Cluster-based routing is a special example of backbone-based routing [85], if nodes in a backbone are considered as cluster heads. To emphasise that a backbone comprises selected wireless nodes rather than being a wired backbone of base stations, the former is often called a \"virtual\" backbone. A virtual backbone in a WSN is a set of nodes that are connected together, and routing operations are restricted to those nodes in the backbone. Therefore, to ensure its communications to other nodes, each sensor should connect to at least one node in the virtual backbone in a single hop, while virtual backbone nodes can communicate with each other via multi-hop paths. It is clear that the nodes in the virtual backbone need to maintain the connectivity among each others. A virtual backbone also has other functions, such as route maintenance, transmission scheduling, and broadcasting [86]. A virtual backbone of a WSN can be modelled by a **C**onnected **D**ominating **S**et (CDS) in the connectivity graph representing the WSN. For a graph \(G=(V,E)\), in which \(V\) is the set of vertices with cardinality \(n\), and \(E\) is the set of edges, a dominating set (DS) is defined as a subset of \(V\), such that any vertex in \(V\) is either an element of the DS or has at least one neighbour in the DS. If such a dominating set is connected, i.e., any arbitrary pair of vertices in the DS are connected by a path containing only elements of DS, then it is called a connected dominating set (CDS). A graph can have multiple DS and CDS. The CDS that has the smallest cardinality is named a **M**nimum **C**onnected **D**ominating **S**et (MCDS). Just like a CDS, an MCDS need not be unique. Figure 2 illustrates the concept of MCDS by a simple example. A network is modelled as a connected graph \(G=(V,E)\), in which \(V=\{a,b,c,d,e,f\}\) is the set of vertices, representing all the nodes in the network, while an edge between two vertices in the graph stands for the existence of a direct connection between the corresponding sensor nodes, and the edges set \(E=\{(a,f),(b,f),(b,c),(c,d),(c,e),(d,e),(b,e)(e,f)\}\) is the collection of all the connections. According to the previous definition, the MCDS of \(G\) in Figure 2 is the subset \(U=\{e,f\}\subseteq V\). Since we model WSNs by graph models, a connected dominating set in the corresponding graph can form the virtual backbone for a WSN. Also, if we can find the MCDS in the graphs, we can construct a virtual backbone with the least number of nodes.