# Energy-Efficient Connected-Coverage Scheme in Wireless Sensor Networks
## 4 Algorithm for the Set Coverage Problem
### Minimum Coverage Control Algorithm
#### 4.2.1 Genetic Operation  
The evolutionary process of the GA includes selection, crossover, mutation, and fitness function. The chromosomes are evaluated by the fitness function. Define the \(\ell_{k,j}\) as the working state of node \(s_{j}\) in the \(k\)th chromosome, which is assumed as 0 or 1. The coverage vector \(w(k)\) of the chromosome \(k\) can be expressed as the vector below,  
\[\left\{ \begin{array}{l}[(\ell_{k,1}G_{1,1})\cup(\ell_{k,2}G_{2,1})\cup\cdots \cup(\ell_{k,N}G_{N,1})],\\ [(\ell_{k,1}G_{1,2})\cup(\ell_{k,2}G_{2,2})\cup\cdots\cup(\ell_{k,N}G_{N,2})], \\ \vdots\\ [(\ell_{k,1}G_{1,M})\cup(\ell_{k,2}G_{2,M})\cup\cdots\cup(\ell_{k,N}G_{N,M})] \end{array} \right\} \tag{8}\]  
In (8),(\(\ell_{k,i}G_{j,m}\))represents the coverage of the \(j\)th sensor node on the \(k\)th chromosome to the \(m\)th MTP. When \(((\ell_{k,1}G_{1,M})\cup(\ell_{k,2}G_{2,M})\cup\cdots\cup(\ell_{k,N}G_{N,M})]=1)\), it means that the \(m\)th MTP is covered by at least one sensor node. In this paper, we assume that the channel is ideal. In the full connected network, the sensing data from the \(m\)th MTP can be successfully received by the sink. However, in practice, the wireless channel is unreliable, more than one sensor node with better channel quality is activated to cover one target. Subsequently, the SCP becomes a complicated cross-layer optimization problem, and this is out of the scope of this work. The fitness function is proposed by considering the objectives, as follows. Objective 1, the coverage rate of the MTP \(\varepsilon^{k}\) should be largest. Subsequently, the performance of the network can be ensured. \[f_{1}=\max\varepsilon^{k}=\frac{||w(k)||^{2}}{M}, \tag{9}\]  
where \(||w(k)||\) is the Euclidean norm, \(||w(k)||^{2}\) represents the number of MTPs that can be covered by the sensor nodes on the \(k\)th chromosome. Objective 2, the number of active nodes on the \(k\)th chromosome, should be the least while the objective 1 is ensured. In other words, the sensor node dormancy rate \(\eta\) should be the largest value. Therefore, much more energy can be saved. \[f_{2}=\max\eta=1-\frac{\sum\limits_{i=1}^{N}s_{i}}{N},v_{i}=1, \tag{10}\]  
where \(\sum\limits_{i=1}^{N}s_{i}\) represents the number of active nodes. Objective 3, the selected sensor nodes in set \(\mathbf{s}_{minCoer}\) should have sufficient energy to serve up to a certain rounds. \[f_{3}=\max\frac{E_{r}}{E_{total}}, \tag{11}\]  
Let \(E_{total}\) be the sum of the initial energy of all sensor nodes and \(E_{r}\) be the maximum remaining energy of all sensor nodes. Figure 3: Coding example network. We define \(f(k)\) as the fitness function of \(k\) chromosome. According to the weighted GA, the total objective function is defined as the weighted sum of mentioned objective functions. The fitness function should be maximized to achieve the better performance of the network, which is shown as  
\[ \begin{split}&\max f(k)=\lambda_{1}\cdot(f_{1})+\lambda_{2}\cdot(f_{2 })+\lambda_{3}\cdot(f_{3})\\ =&\lambda_{1}\cdot(\frac{|\left|w(k)\right||^{2}}{M} )+\lambda_{2}\cdot(1-\frac{\sum\limits_{i=1}^{N}s_{i}}{N})+\lambda_{3}\cdot( \frac{E_{r}}{E_{total}})\end{split}  \tag{12}\]  
where \(\lambda_{1}\), \(\lambda_{2}\) and \(\lambda_{3}\) are weighting coefficients and \(\lambda_{1}+\lambda_{2}+\lambda_{3}=1\). It can be noticed that the larger the value of the objective function \(f(k)\), the better the goodness of the chromosome. After achieving the fitness function, the process of determining the minimum coverage set is shown, as follows. Firstly, the tournament selection strategy is used to randomly select 10 chromosomes from the population (each chromosome has the same probability of being selected). The optimal chromosome with the maximum fitness will be put into the next generation population. Such an iteration will stop until the new population size is equal to the original population size. Secondly, randomly choose two parent chromosomes from the current population and use one-point crossover to cross them to produce new child chromosomes.