## 2 Resilient WSNs: _k-Connected_ Network
### \(k-Connected\) and \(k-Coverage\) Network  
In this section, the definitions of network connectivity and coverage are introduced.  
**Definition 1**.: _Connected graph: For any two distinct vertexes, if they can communicate with each other either directly or via a limited number of intermediate vertexes, then the graph is called a connected graph._  
**Definition 2**.: \(k\)_-connected graph: Given integer \(k\geq 1\), if the graph is still connected after removing no more than \(k-1\) vertexes, then \(G\) is called \(k-vertex-connectivity\) graph, or a \(k-vertex-connected\) graph, usually simply denoted as a \(k-connectivity\) graph or \(k-connected\) graph. The value \(k\) is called \(connectivity\). The vertex connectivity \(\kappa\) of the graph is the maximum \(k\), such that the graph is a \(k-connected\) graph._  
**Definition 3**.: \(k\)_-edge-connected: Given integer \(k\geq 1\), the graph is still connected after removing no more than \(k-1\) edges; \(G\) is named the \(k-edge-connectivity\) graph, or \(k-edge-connected\) graph. The vertex connectivity \(\kappa^{\prime}\) of the graph is the maximum \(k\), such that the graph is a \(k-edge-connected\) graph._  
Figure 2: WSN topology example. (1) \(|V|\) = 7, \(|E|\) = 11; (2) This is the non-negative weighted edge undirected connected graph; (3) Four nodes, 6, 3, 7 and 4, are neighbors of Node 5, so \(d(v_{5})=4\); (4) Network degree \(\delta=2\); (5) This is two-connected and two-edge-connected.  
For example, in Figure 2, if two, Nodes 2 and 6, are removed, the resulting network is disconnected because Node 1 will be isolated; at the same time, removing only one node is unable to disconnect the network. The relation between vertex and edge connectivity is given by the following well-known Equation (1), which is called [PERSON]'s theorem [14; 16]:  
\[\kappa\leq\kappa^{\prime}\leq\delta\leq\frac{2|E|}{|V|} \tag{1}\]  
Apparently, the connectivity \(k\) helps to evaluate the WSNs' fault tolerance capability. The higher \(\kappa\) or \(\kappa^{\prime}\) is, the more resilient the WSNs will be. The upper bound of connectivity \(\kappa\) can be achieved by Harary graphs. The lower bound of \(\kappa\) is zero or \(|E|-\frac{(|V|-1)(|V|-2)}{2}\)[16].  
On the one hand, the connectivity in most cases is a desirable feature. A \(k-connected\) network is important for the key distribution problem in WSNs. For instance, [17; 18; 19; 20; 21; 22; 23; 24] analyze the probability on the reliable connectivity of WSNs under the random key distribution scheme. More specifically, they study the conditions for how to scale the model parameters in a random key pre-distribution scheme called Eschenauer-Gligor (EG), so that the random key graph is \(k-connected\). They show the correlation between the probability of being \(k-connected\) and the parameters in the EG scheme. The probability that a random key graph has a minimum node degree no less than \(k\), but that is not \(k-connected\) converges to zero as \(0\rightarrow\infty\)[3]. The transmission model used in these works is Erdos-Renyi, rather than a disk model. A high degree also helps to detect failures. The work in [25] shows that optimal error detection decreases exponentially with the increase of degree. On the other hand, in a few cases, it is in fact an unwanted feature, e.g., virus propagation [26].  
To some extent, improving network resilience means increasing, maintaining or constructing the required \(\kappa\) or \(\kappa^{\prime}\). In this paper, when we mention that the network is \(k-connected\), this means \(\kappa-connected\); if the network is \(k-edge-connected\), this means \(\kappa^{\prime}-edge-connected\).  
**Definition 4**.: _k-coverage network: the network is called a \(k-coverage\) network where \(k\) is the biggest positive integer, such that any point in the deployment area is covered by at least \(k\) distinct sensor nodes via sensing range._