On Connected Target k-Coverage in Heterogeneous Wireless Sensor Networks

Jiguo Yu, Ying Chen, Liran Ma, Baogui Huang, Xiuzhen ChengSensors 2016 · OpenReview

TL;DR

This paper tackles the challenge of ensuring both comprehensive coverage and reliable connectivity in heterogeneous wireless sensor networks (HWSNs). The authors introduce two novel algorithms, a centralized CCTCk and a distributed DCTCk, designed to create energy-efficient "connected cover sets" that guarantee each target is monitored by at least k sensors while maintaining network connectivity to a sink. These algorithms outperform existing methods by considering sensor capabilities, remaining battery life, and target coverage needs.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are crucial for monitoring environments, but their effectiveness hinges on two key factors: coverage (ensuring all areas or targets are observed) and connectivity (allowing sensor nodes to communicate data back to a central sink). In heterogeneous WSNs (HWSNs), sensor nodes have varying capabilities (e.g., battery life, sensing range, communication power), adding complexity.

The core problem is achieving connected target k-coverage (CTCk). This means not only ensuring every target is covered by at least k sensors (for reliability and accuracy, especially in applications like military surveillance), but also that all active sensors can communicate with a sink, forming a connected network. Traditional approaches often struggle with energy efficiency, as keeping all sensors active drains batteries quickly. This paper aims to create energy-efficient "cover sets" where only a subset of sensors is active at any given time, but these sets collectively provide the required k-coverage and maintain network connectivity, thereby extending the network's overall lifetime.

Methods

The paper proposes two algorithms:

  • Centralized Connected Target k-Coverage Algorithm (CCTCk): This algorithm operates centrally, gathering information from all nodes to make optimal decisions. It selects sensor nodes for a cover set based on a SET(Si) function that balances three crucial aspects:
  • Coverage Priority: Favoring nodes that cover targets not yet adequately covered (k-covered).
  • Energy Availability: Prioritizing nodes with more remaining battery life.
  • Target Coverage Degree: Considering nodes that cover targets with fewer current sensors. The SET(Si) function is a weighted combination of these factors, allowing tuning for different network priorities. CCTCk iteratively builds a cover set, ensuring each selected sensor can communicate with a sink, either directly or through relay nodes.

  • Distributed Connected Target k-Coverage Algorithm (DCTCk): Designed for large-scale HWSNs, this algorithm allows nodes to make decisions locally based on information from their neighbors. The network lifetime is divided into rounds, each with an initial phase (sensing coverage and communication relay) and a working phase. DCTCk operates in two main stages:

  • Coverage Stage: Nodes determine if they should be active or in a wait state to achieve k-coverage.
  • Connectivity Stage: Nodes that are active but not connected to a sink actively seek relay nodes to establish a path to the sink. DCTCk uses a message-passing mechanism (Active, Candidate, Connect, Sink, Reply, Ask) to coordinate coverage and connectivity.

Both algorithms utilize a more realistic irregular convex sensing and communication model, moving beyond the simpler binary disk model. They also consider the remaining battery life and sensing capabilities of each sensor node when making selection decisions.

Datasets

Not discussed in the paper. The evaluation is based on simulations with randomly deployed sensor nodes and targets.

Key Insights and Ideas

  • Balancing Coverage and Connectivity is Key: The paper emphasizes that achieving both k-coverage and network connectivity simultaneously is critical for reliable WSN operation, especially in heterogeneous environments.
  • Heterogeneity Matters: Sensor nodes having different capabilities (energy, sensing range) is not just a challenge but an opportunity. The algorithms leverage this heterogeneity to optimize energy usage and network lifetime.
  • Non-Disjoint Cover Sets Extend Lifetime: By allowing sensor nodes to be part of multiple cover sets (non-disjoint), the network can achieve a longer operational lifetime compared to strictly disjoint sets.
  • A Unified Selection Metric: The SET(Si) function in CCTCk provides a principled way to select sensor nodes by integrating coverage needs, energy status, and target coverage depth.
  • Distributed Approach for Scalability: DCTCk's distributed nature makes it suitable for large-scale HWSNs where centralized control is impractical.

Key Results

The paper presents theoretical analysis and simulation results demonstrating the effectiveness of their proposed algorithms:

  • Outperforms State-of-the-Art: Both CCTCk and DCTCk are shown to outperform existing connected k-coverage protocols for HWSNs.
  • Energy Efficiency: DCTCk demonstrates significantly less energy consumption per round compared to EETC, a comparable algorithm.
  • Reduced Active Nodes: DCTCk requires fewer active sensor nodes in connected cover sets compared to EETC, indicating better resource utilization.
  • More Connected Cover Sets: DCTCk generates more connected cover sets than EETC and LADCS, suggesting better network robustness and coverage flexibility.
  • Load Balancing and Lifetime Extension: The algorithms' consideration of sensing capabilities, remaining battery life, and target coverage contributes to load balancing among sensor nodes, thereby prolonging network lifetime.

Limitations and Future Work

  • Limitations:
    • The paper assumes a stationary network where sensor nodes do not move after deployment.
  • The irregular convex sensing and communication models are considered for tractability, but real-world sensor behavior might be more complex.
  • The binary disk model is still used in some parts of the analysis and figures, though the proposed algorithms aim for more realistic models.
  • The centralized algorithm (CCTCk), while effective, may not be scalable for very large networks.
  • Future Work:
    • The authors plan to study multi-connectivity in the future to further enhance network robustness.
  • Investigating algorithms for mobile sensor nodes would be a natural extension.
  • Exploring more sophisticated sensing and communication models that better reflect real-world scenarios.

Summary updated

Abstract

Coverage and connectivity are two important performance evaluation indices for wireless sensor networks (WSNs). In this paper, we focus on the connected target k-coverage (CTC k ) problem in heterogeneous wireless sensor networks (HWSNs). A centralized connected target k-coverage algorithm (CCTC k ) and a distributed connected target k-coverage algorithm (DCTC k ) are proposed so as to generate connected cover sets for energy-efficient connectivity and coverage maintenance. To be specific, our proposed algorithms aim at achieving minimum connected target k-coverage, where each target in the monitored region is covered by at least k active sensor nodes. In addition, these two algorithms strive to minimize the total number of active sensor nodes and guarantee that each sensor node is connected to a sink, such that the sensed data can be forwarded to the sink. Our theoretical analysis and simulation results show that our proposed algorithms outperform a state-of-art connected k-coverage protocol for HWSNs.
BibTeX
@inproceedings{yu2016connected,
  author = {Jiguo Yu and Ying Chen and Liran Ma and Baogui Huang and Xiuzhen Cheng},
  title = {{On Connected Target k-Coverage in Heterogeneous Wireless Sensor Networks}},
  booktitle = {Sensors},
  year = {2016},
  url = {https://openreview.net/forum?id=qg9bW7rN_q8},
}
Figure