Vertex coloring approach for Q-coverage problem in wireless sensor network

Article type: Research Article

Authors: Arivudainambi, D. | Pavithra, R.^{; *}

Affiliations: Department of Mathematics, Anna University, Chennai, India

Correspondence: [*] Corresponding author. R. Pavithra, Department of Mathematics, Anna University, 600025, Chennai, India. E-mail: pavithraravikumar94@gmail.com.

Abstract: Wireless Sensor Network (WSN) has emerged recently due to its advancements and applications in various scientific and industrial fields. WSN consists a set of low cost and readily deployable sensors to monitor targets and recognise the physical phenomena. The principal challenge in WSN is to deploy these sensor nodes in optimal positions to achieve efficient network. Such network should satisfy the quality of service requirements in order to achieve high performance levels. Hence, this paper focuses on target Q-coverage problem where each target requires different number of sensors to monitor them. A Sequential Vertex Coloring based Sensor Placement (SVC-SP) algorithm is proposed to determine the number of sensors required and its optimal spot to satisfy the coverage quality requirement. The SVC-SP algorithm determines sensor requirement by partitioning the target set into independent subsets depending on the target’s position and the sensor’s sensing range. Each independent set consists set of targets that are nearer in the network such that a common sensor is sufficient to monitor them. The cardinality of such independent subsets provides the sensor requirement for target coverage. The optimal spot for each target is determined by the mean positioning of the targets in each independent set. This process is repeated until the q-requirement for each target is satisfied. Further, to improve the optimal spot for sensors, the random based SVC-SP algorithm, cuckoo search based SVC-SP algorithm and the genetic algorithm based SVC-SP algorithm are utilized. The simulation results show that genetic algorithm based SVC-SP algorithm performs better than other existing algorithms.

Keywords: Optimal sensor placement, target coverage, Q-coverage, vertex coloring, sequential vertex coloring

DOI: 10.3233/JIFS-191795

Journal: Journal of Intelligent & Fuzzy Systems, vol. 40, no. 5, pp. 8683-8695, 2021