## 2 Resilient WSNs: _k-Connected_ Network
### Partially-Connected Network  
The definitions above require that the entire network is \(k-connected\) or \(k-coverage\). However, as the WSNs are characterized by high density, only a small number of nodes is needed for connectivity or coverage in order to save energy and prolong the WSNs' lifetime. As a result, maintaining a whole network as connected is not only quite difficult, but also maybe unnecessary. If the goal is not to maintain the whole network as connected, it is called a \(partially\ connected\ network\).  
**Definition 5**.: _Partial \(k-connected\) network: [27; 28] propose a concept called a \(partial\ k-connected\) network. If the original network is damaged, new nodes are added to the network. The goal is not to recover the entire new network as \(k-connected\); instead, it only maintains the original nodes that are \(k-connected\)._Being partially-\(k-connected\) weakens the final objective, but is still useful in the case that only original nodes serve an important purpose, while the added nodes are only used to maintain connectivity. On the other hand, WSNs have many redundant nodes, so maybe only part of them is required to be connected, e.g., the giant component to be connected being as large as possible.  
**Definition 6**.: _Giant component threshold: there exists a critical value, such that whenever the fraction of removed nodes (or links, depending on the context) is lower than \(P_{c}\), the network still holds a giant component almost certainly; whereas, whenever the fraction of removed nodes (or links) is greater than \(P_{c}\), the network is almost sure not to have a giant component anymore._  
For random failures in a large random deployed network, \(P_{c}\) is given by Equation (2) [29]:  
\[P_{c}=1-\frac{<k>}{<k^{2}>-<k>} \tag{2}\]  
where \(<k^{j}>=\sum_{k=0}^{\infty}k^{j}p_{k}\) (where \(j=1,2\)) and \(p_{k}\) is the probability distribution for all \(k\), e.g., Poisson distribution \(p_{k}=e^{-z\frac{k}{k!}}\). Notice that this conclusion is suitable for any degree distribution, e.g., Poisson distribution, continuous and discrete power law. More details about the results under other two conditions are available in [29]: the number of nodes tends to infinity and a given large number \(N\).  
In WSNs, only the most important nodes are needed to be connected together sometimes. This theory is associated with the concept known as the minimal connected dominating set (CDS).  
**Definition 7**.: _Minimal connected dominating set (CDS): the connected dominating set \(D\) is a sub-graph of the graph \(G\), such that: (1) \(D\) is connected to the sub-graph of \(G\); (2) any vertex in \(G\) either belongs to \(D\) or is adjacent to a vertex of \(D\). One graph may have more than one \(D\). The one that has the minimal number of vertexes lower than any other connected dominating set is called the minimal CDS._  
Whether there is a connected dominating set with a size less than a given value is an NP-complete problem. So far, the best approximation of finding the minimal dominating set is a \(O(\log|V|)\)-approximation [30] and a \(O(\log\Delta)\)-approximation distributed algorithm [31], where \(\Delta\) is the maximal degree of the graph. There are several papers, such as [32, 33], that present the topology control algorithms through constructing an optimal-sized CDS to achieve a trade-off between the network lifetime and the network coverage in WSNs.