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

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.

• Publication year

  2021

• Venue

  Journal of Intelligent & Fuzzy Systems

• Publication date

  2021-03-29

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.3233/JIFS-191795
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Coverage and Connectivity-Based 3D Wireless Sensor Deployment Optimization

  2020cited by this paper
• Coverage Degree-Coverage Model in Wireless Visual Sensor Networks

  2019cited by this paper
• Optimal Deployement of Sensors in 3D - Terrain with Q-Coverage Constraints

  2018cited by this paper
• Optimization of Target Q-Coverage Problem for QoS Requirement in Wireless Sensor Networks

  2018cited by this paper
• Optimization of Target Q-Coverage Problem for QoS Requirement in Wireless Sensor Networks

  2018cited by this paper
• Enhancing Quality of Coverage for Target Coverage Problem Using Discrete Haar Wavelet

  2018cited by this paper
• Selective α-Coverage Based Heuristic in Wireless Sensor Networks

  2017cited by this paper
• Sensor deployment for target coverage in underwater wireless sensor network

  2017cited by this paper
• An Improved DSATUR‐Based Branch‐and‐Bound Algorithm for the Vertex Coloring Problem

  2017cited by this paper
• An Efficient Deployment Approach for Improved Coverage in Wireless Sensor Networks Based on Flower Pollination Algorithm

  2016cited by this paper
• Research on the target coverage algorithms for 3D curved surface

  2016cited by this paper
• Genetic algorithm approach for k-coverage and m-connected node placement in target based wireless sensor networks

  2016cited by this paper
• Performance evaluation of sensor deployment using optimization techniques and scheduling approach for K-coverage in WSNs

  2016cited by this paper
• A Comparison of p-median and Maximal Coverage Location Models with Q–coverage Requirement☆

  2016cited by this paper
• Evolutionary-Based Wireless Sensor Deployment for Target Coverage

  2015cited by this paper
• On Deployment of Wireless Sensors on 3-D Terrains to Maximize Sensing Coverage by Utilizing Cat Swarm Optimization With Wavelet Transform

  2014cited by this paper
• Sensor Deployment and Scheduling for Target Coverage Problem in Wireless Sensor Networks

  2014cited by this paper
• Matheuristic approaches for Q-coverage problem versions in wireless sensor networks

  2013cited by this paper
• Method for Optimal Sensor Deployment on 3D Terrains Utilizing a Steady State Genetic Algorithm with a Guided Walk Mutation Operator Based on the Wavelet Transform

  2012cited by this paper
• A Heuristic to Maximize Network Lifetime for Target Coverage Problem in Wireless Sensor Networks

  2011cited by this paper
• A Deterministic Sensor Node Deployment Method with Target Coverage and Node Connectivity

  2011cited by this paper
• Energy-Efficient Algorithm for the Target Q-coverage Problem in Wireless Sensor Networks

  2010cited by this paper
• Q-Coverage Problem in Wireless Sensor Networks

  2009cited by this paper
• QoS-aware target coverage in wireless sensor networks

  2009cited by this paper
• GRAPH COLORING ALGORITHMS

  1972cited by this paper

• A Survey of Three-Dimensional Wireless Sensor Networks Deployment Techniques

  2025cites this paper
• Grundy Number-Based Optimal Sensor Placement in 3D Wireless Sensor Network

  2024cites this paper
• Indoor millimeter wave D2D communication resource optimization based on improved PMVC and CTRA algorithms

  2023cites this paper