Multi-objective Evolutionary Algorithms for Coverage and Connectivity Aware Relay Node Placement in Cluster-Based Wireless Sensor Networks

Wireless sensor networks (WSNs) have been extensively explored due to their incredible capabilities and ever-growing field of applications. In cluster-based WSNs, cluster heads (CHs) deplete their energy quickly due to the extra workload of data aggregation and data forwarding as relay nodes (RNs) from the member sensor nodes (SNs). While placing the RNs in the application areas to form the clusters, coverage of all the SNs and connectivity amongst the RNs are essential for the proper function of the networks. Moreover, reducing the intra-cluster distances between the RNs and SNs is important to save the transmission energy of the SNs. Moreover, the problem of placement of RNs in cluster-based WSNs is known as NP-Hard. To address the challenge of deploying RNs while managing multiple conflicting objectives, we present a range of evolutionary algorithms (EAs) as potential solutions. These include techniques such as differential evolution (DE), particle swarm optimization (PSO), multi-objective DE (MODE), and multi-objective PSO (MOPSO). First, a mathematical formulation of the problem is given. The solution vectors are efficiently encoded. All the objective functions are efficiently derived to evaluate the solution vectors. An extensive simulation is performed over the proposed algorithms. The results are analyzed to determine the robust algorithm to be recommended for the studied problem. The simulated results claimed that the MODE is comparably better than others for the studied problem. The analysis of variance (ANOVA) is also performed, followed by a post-hoc analysis using the least significant difference (LSD) method.