Solving the k-Coverage and m-Connected Problem in Wireless Sensor Networks through the Imperialist Competitive Algorithm

摘要

This study presents a new method based on the imperialist competitive algorithm (ICA-based) to solve the k-coverage and m-connected problem in wireless sensor networks (WSNs) through the least sensor node count, where the candidate positions for placing nodes are pre-specified. This dual featured problem in WSNs is a nondeterministic polynomial (NP)-hard problem therefore, ICA the social-inspired evolutionary algorithm is assessed and ICA-based scheme is designed to solve the problem. This newly proposed ICA-based scheme provides an efficient algorithm for representing the imperialistic competition among some of the best solutions to the problem in order to decrease the network cost. The mathematical formulation is presented for the node placement problem. The main issue of concern here is the deployed sensor node count. The simulation results confirm that ICA-based method can reduce the required sensor node count unlike other genetic-based and biogeography-based evolutionary algorithms. The experimental results are presented for WSN_Random and WSN_Grid scenarios.