Genetic algorithm approach for k-coverage and m-connected node placement in target based wireless sensor networks
In target based wireless sensor networks (WSNs), coverage and connectivity are the two most important issues for guaranteed data forwarding from each target to a remote base station (BS). Given a set of target points, finding minimum number of potential positions to place sensor nodes fulfilling both coverage and connectivity is an NP-complete problem. In this paper, we propose a genetic algorithm (GA) based scheme to solve this problem. Keeping in mind that the sensor nodes are prone to failure, the proposed scheme provides k-coverage to all targets and m-connectivity to each sensor node. Our GA based approach is presented with efficient chromosome representation, derivation of efficient fitness function along with the usual GA operators. The scheme is simulated extensively with various scenarios of WSN. The simulation results are compared with some related existing algorithms to demonstrate the efficacy of the proposed scheme.
genetic algorithm k-coverage m-connectivity wireless sensor networks node deployment np-hard