## 4 Topology Control
### Pre-Deployment
#### 4.2.2 Construct \(k-Connected\) Networks  
When the nodes in the WSNs are able to control the locations, the questions are how to construct a \(k-connected\) network or how to verify that the constructed network is \(k-connected\). At the same time, it is necessary to consider the \(k-coverage\) issue in some cases. (1) Construct \(k-Connected\) and \(k-Coverage\) Network:  
There is a well-known result showing that if the communication range is at least two times longer than the sensing range, that is \(s_{c}\geq 2s_{s}\), then \(k-coverage\) can guarantee \(k-connected\)[15]. If the node's location is carefully designed, the ratio can be further optimized. For example, [69] proves that strip-based is the asymptotically optimal deployment for achieving both \(1-coverage\) and \(1-connected\) for all \(\frac{r_{s}}{r_{c}}\leq\sqrt{3}\), and [70] proposes that a diamond pattern can achieve the asymptotic optimality for \(1-coverage\) and \(4-connected\) when \(\frac{r_{s}}{r_{c}}>\sqrt{2}\). For higher connectivity, [71] presents the hexagon-based deployment pattern to achieve \(1\leq k\leq 6\) connectivity. However, the optimal ratio between communication range and sensing range such that the network is \(k-coverage\) and \(k-connected\) for general \(k\) is still an open issue. The work in [55] first shows the conditions that a network is \(k-coverage\) and \(k-connected\). It states that the network is \(k-coverage\) and \(k-connected\) if it is \(k-DPC\). \(k-DPC\) is defined as: if each point on the perimeter of every node is covered by at least \(k\) other nodes through the sensing range, each node has a link to all of its neighbors. Here, two nodes being neighbors means that there exists an intersection between their sensor ranges, rather than the communication ranges. The distributed protocols are proposed to guarantee \(k-coverage\) and \(k-connected\) under the condition that the initial coverage and connectivity are higher than expected. Similarly, [72] also proves that the target field is \(k-coverage\) only when the sensing border of every node is \(k-coverage\). It uses this conclusion to verify whether the network is \(k-coverage\) or a coverage hole exists in a \(d-dimension\) network, where \(d\) is 1, 2, 3. On the contrary, given the ratio between \(r_{c}\) and \(r_{s}\), the connectivity can be calculated. The work in [36] suggests that if communication range \(r_{c}\) is at least equal to sensing range \(r_{s}\) and the network is connected, its connectivity \(k\) is \(\frac{2k\pi r_{c}^{2}}{(\pi-\sqrt{3})r_{s}^{2}}\) for a homogeneous \(k-coverage\) network and \(\frac{2k\pi R_{max}^{2}}{(\pi-\sqrt{3})r_{min}^{2}}\) for heterogeneous \(k-coverage\) networks, where \(r_{min}\) and \(R_{max}\) are minimal sensing range and maximal communication range, respectively, in a heterogeneous network. The sufficient density to guarantee \(k-coverage\) for a homogeneous network is \(\frac{2k}{(\pi-\sqrt{3})r_{s}^{2}}\) and \(\frac{2k}{(\pi-\sqrt{3})r_{min}^{2}}\) for a heterogeneous network [36]. There are practical applications that try to find appropriate locations for sensors to maintain the network connectivity. For example, the work in [73] finds the optimal location for underwater sensors for the purpose of minimizing the transmission loss while maintaining the network connectivity; [74] finds the optimal location for reliable fault detection in a boiler system. (2) Construct New \(k-Connected\) Network from Existing \(k-Connected\) Network:  
Let \(G\) be a \(k-connected\) graph; if \(H\) is a graph obtained from adding a new vertex and joining it to at least \(k\) vertices of \(G\), \(H\) is also \(k-connected\)[14]. In Figure 7, the original \(G\) is a \(2-connected\) network and the new graph \(H\) is constructed by adding the new Node 4. There are two disjoint links connected to \(G\) from Node 4, so \(H\) is a \(2-connected\) network. Likewise, two disjoint \(k-connected\) components form a large \(k-connected\) component if there are \(k-vertex\) disjoint edges connecting them.