## 4 Survey of Existing Works
### Genetic Algorithm
#### 4.3.1 GA in WSN Clustering  
In WSN clustering, the total energy consumption is closely related with the number of cluster heads and their positions, so it is important to find out an energy-efficient clustering technique that can optimize the energy consumption which is directly related to network lifetime. The first works of clustering in WSNs using genetic algorithms can be found in [101]. [PERSON] _et al_. have used a GA-based method to minimize communication distance in sensor networks via clustering. In their work, GA was used in formation of a number of pre-defined clusters which helped in reducing the total minimum communication distance. The cluster heads (CHs) were adjusted based on fitness function. The algorithm was able to find an appropriate number of cluster-heads and their locations. Results indicate that the number of CHs is about 10% of the total number of nodes. The pre-defined cluster formation also decreased the communication distance by 80% as compared with the distance of direct transmission. In one hand it was able to quickly find good solutions; on the other hand, this algorithm is applicable to both uniform and non-uniform network topologies. In [102] [PERSON] _et al_. proposed a genetic algorithm (GA) that was used to create energy efficient clusters for routing in WSNs. In their work, the sink node performed the simultaneous optimization of total dissipated transmission energy and delay by clustering the nodes. The simulation results show that the proposed energy-efficient hierarchical clustering protocol performs better than the traditional cluster- based protocols. The gradual energy depletion in sensor nodes is also investigated. In another work [PERSON] _et al_. [103] improved their idea proposed in [102] by improving the fitness function used for GA. This fitness function is based on parameters like cluster size, energy consumption, number of clusters, direct distance to sink _etc_. They extended their work using GA to obtain the optimum number of clusters, CHs, cluster members and transmission schedule. It was  
Figure 7: A simple procedure of Genetic Algorithm  
shown that their updated method conserves relatively more energy than the method proposed by [PERSON] _et al._ in [101]. They also compared their proposed method with the LEACH protocol in different layouts along with increased number of nodes in the sensor network. The results of energy saving approaches can vary significantly depending on the number and size of clusters and the distance among the sensor nodes. The authors in [104] aim to find an optimal cluster formation by applying a GA based method in which the chromosome contains the information about the relative position of the nodes. They proposed a location-aware two-dimensional genetic algorithm (LA2D-GA) that performs more efficient in gene evolution than general approach with one-dimensional genetic algorithm (1D-GA). It gives unique location information to each node (chromosome). Thus, when crossover and mutation operations are performed, the optimal clusters can be searched effectively by using this information. The simulation results indicate better performance against LEACH and 1D-GA. In [105] the authors examine the GA as a dynamic technique to find optimum states. As a simple framework it proposes a mathematical formula, which increases coverage against lifetime. This technique makes a tradeoff between energy consumption and distance parameter. Finally, the proposed algorithm performs better than some traditional cluster-based protocols. In [106] GA is used for dynamic clustering which is similar to the works we have discussed in [102] and [103]. They used slightly different parameters such as residual energy of the nodes, required energy to send a message toward the sink node, and number of cluster heads. In order to evaluate the algorithm, they simulated the protocol and compared it to LEACH protocol. The simulation results show the effectiveness of the proposed mechanism.