# Energy-Efficient Connected-Coverage Scheme in Wireless Sensor Networks
## 4 Algorithm for the Set Coverage Problem
### Minimum Coverage Control Algorithm
#### 4.2.2 Local Wake-up Scheme  
With the continuous operation of the WSN, some sensor node will run out of its energy. The wake-up strategy is also proposed to ensure the full coverage of MTPs. Through waking up the appropriate sensor node from set \(\mathbf{s}_{redCover}\) to replace the dead node, MTPs can be detected continuous.  
The local wake-up scheme is divided into two parts. Firstly, define the set of all MTPs as \(c_{1}(s_{i})\) and the set of the remaining MTPs, except for that which cannot be monitored by nodes as \(c_{2}(s_{i-d})\), respectively. The MTP that cannot be monitored will be found by Boolean exclusive disjunction between sets \(c_{1}(s_{i-d})\) and \(c_{2}(s_{i-d})\), which is shown as  
\[c(s_{i})_{uncovered}=c_{1}(s_{i-d})\oplus c_{2}(s_{i-d}). \tag{13}\]  
Secondly, for the selected sensor node \(s_{j}\) from set \(\mathbf{s}_{redCover}\), it should satisfies (i) the distance \(d_{ij}\) between the selected sensor node \(s_{j}\) and the dead node \(s_{i}\) is no greater than the communication radius \(R_{c}\), and (ii) the distance \(d_{jm}\) between the selected sensor node \(s_{j}\) and the corresponding \(m\)th MTP is no greater than the sensing radius \(R_{s}\). These two constraints are shown, as follows  
\[\left\{\begin{array}{l}d_{ij}=\sqrt{\left(x_{i}-x_{j}\right)^{2}+\left(y_{i }-y_{j}\right)^{2}}<R_{c},\\ d_{jm}=\sqrt{\left(x_{j}-x_{m}^{\prime}\right)^{2}+\left(y_{j}-y_{m}^{\prime} \right)^{2}}<R_{s}.\end{array}\right. \tag{14}\]  
Define the set of all sensor nodes in set \(\mathbf{s}_{redCover}\) that satisfy (13) as \(\mathbf{s}_{sect}\). Subsequently, select the optimal sensor node that has maximum residual energy comparing with others from set \(\mathbf{s}_{sect}\) to monitor the \(m\)th MTP.  
The time complexity of the MCCA is bounded in \(\text{O}(N\cdot M+K\cdot\rho\cdot N)\), where \(N\) is the number of sensor nodes, \(M\) is the number of the MTPs, \(\rho\) is the number of chromosomes, and \(K\) is the size of the population. First, the MCCA needs to calculate the distance between sensor nodes and MTPs. There are a total of \(NM\) operations, so the complexity of the first step is \(O(N\cdot M)\). In genetic operations, we need to traverse \(N\) sensor nodes on each chromosome. Because there are a total of \(K\) populations and \(\rho\) chromosomes in each population, the complexity of the second step is \(O(K\cdot\rho\cdot N)\). Thesetwo operations run independently, thus the complexity of MCCA is bound in O(\(N\cdot M+K\cdot\rho\cdot N\)). More details can be found in Algorithm 1.  
```
Input: The population is \(Pop_{k}\), Let \(chrom_{i}\) be the \(i-th\) individual in \(Pop_{k}\), and \(N\) be the length of \(chrom_{i}\). where \(chrom_{i}\) is a binary string composed of \(\ell_{i,j}\). The number of chromosomes is \(\rho\). Output: The best chromosome.
```
1:Calculate the \(f(k)\);
2:Select elite individuals from initial population according to \(f(k)\);
3:One-point crossover;
4:Then use directed mutations to speed up convergence.
5:for\(i=1\) to \(\rho\)do
6:for\(j=1\) to Ndo
7:\(f_{1}(i)=fit(chrom_{i})\);
8: In \(chrom_{i}\), Let allele 1 mutate to 0.
9:\(f_{2}(i)=fit(chrom_{i})\);
10:if\(f_{1}(i)1<f_{2}(i)\)then
11: Let allele 1 mutate to 0.
12:endif
13:endfor
14:endfor
15:Whether the termination condition is met, output the best individual or return to step 1.
16:if node \(s_{i-d}\) has exhausted its energy then
17: wake up redundant from \(\mathbf{s}_{sect}\).
18:endif ```
**Algorithm 1** MCCA.