Artificial bee colony based sensor deployment algorithm for target coverage problem in 3-D terrain

Abstract

In this paper we address sensor deployment problem to achieve different types of target coverage, viz; simple coverage, k-coverage and Q-coverage. Energy which is an important and scarce resource is not being optimally used if sensor nodes are randomly deployed in a region. This energy wastage can significantly be reduced if the deployment positions can be optimally computed. It is important to provide required coverage by keeping the required sensing range at minimum which will require less energy for sensing. We find out the optimal deployment positions in a 3-D terrain using Artificial Bee Colony (ABC) algorithm, which is based on swarm intelligence, and also compare the sensing range requirement for simple, k and Q-coverage problems. Experimental results reveal that for dense networks, the required sensing range does not increase in same proportion for increased value of k and increased value of average number of sensor nodes in Q for k-Coverage and Q-Coverage problems respectively. Sensitivity analysis is done to study the change in the required sensing range if the sensor nodes cannot be deployed exactly in the optimal positions. The analysis reveals that there is no significant change in the sensing range if the sensor nodes are deployed in near optimal positions. © 2011 Springer-Verlag.