Polynomial Algorithm for Node Deployment in Hybrid Wireless Sensor Networks

Lili Zhang, Jing Yuan, Yingchi Mao, Xiwei Zhang, Guihai ChenInternational Journal of Wireless and Microwave Technologies 2011 · DOI

Abstract

When detecting a target or monitoring a physical phenomenon in a region, the deployment problem is fundamental in these applications. Traditionally, stationary sensor networks are deployed to carry out the sensing operations. It is well known that the mobility of sensor nodes can improve the coverage and the probability of the detecting, so we deal with the problem of detecting a target using hybrid sensor networks which contain both stationary sensors and mobile sensors. In this paper, to begin with, we prove that the node deployment problem is NP-complete. Then, one polynomial algorithm for node deployment in hybrid wireless sensor networks is proposed, which aims at minimizing the number of all sensors to reduce the cost. The simulations verify the efficiency of our algorithm.

Introduction

In Wireless Sensor Networks (WSNs), deployment refers to the strategic placement of sensors to monitor a specific region. While stationary sensors are the traditional choice, they often face challenges in high-density requirements and the inevitable formation of coverage "holes." Hybrid Wireless Sensor Networks (HWSNs) address these issues by incorporating mobile sensors that can relocate to bridge gaps or respond to dynamic events.

The primary challenge in HWSN design is the cost-coverage-connectivity trade-off. An effective deployment must cover the entire target area and ensure all sensors can communicate with a central base station, all while minimizing the total number of hardware units to reduce costs. This paper provides a mathematical framework to automate this deployment strategy.

Theoretical Foundation and Complexity

The authors first establish the theoretical difficulty of the deployment problem. By demonstrating its relationship to the Minimum Disk Cover (MDC) problem, they prove that the node deployment problem under coverage constraints is NP-complete. This proof justifies the development of a polynomial-time approximation algorithm rather than attempting a computationally prohibitive brute-force solution.

Proposed Two-Stage Algorithm

The proposed algorithm operates in two distinct phases to address coverage and connectivity sequentially.

Stage 1: Area Coverage via Static Nodes

The monitoring field is discretized into a grid. The algorithm employs a polynomial-time approximation for the MDC problem to determine the optimal placement of static sensors ($V$). This ensures that the entire monitoring area is covered with high probability using the minimum number of stationary units.

Stage 2: Network Connectivity via Mobile Nodes

Static nodes, once placed, may be too distant for reliable communication. The algorithm treats these static nodes as "terminals" and utilizes a Steinerized Minimum Spanning Tree (MST) approach. By calculating the shortest paths required to connect all static clusters, the algorithm identifies optimal "Steiner points." Mobile sensors ($U$) are then deployed at these points to act as communication relays. The model assumes a disc model for sensing and communication, where static sensors have a range $r$ and mobile sensors have a range $R$ (where $R \ge r$).

Experimental Evaluation

The algorithm was evaluated through numerical simulations in a square monitoring field of 100m x 100m ($a=100$). Key parameters included a static sensor range ($r$) of 5m, a mobile sensor range ($R$) of 8m, and a mobile node speed ($v$) of 0.5m/s. The simulations varied the grid side length ($x$) from 2m to 10m to observe the impact of granularity on network composition.

Distribution of static and mobile nodes across different grid sizes.

As shown in the results, there is a clear inverse relationship between grid size and sensor count. When the grid size increased from 2m to 10m, the total number of deployed nodes dropped from approximately 260 to 110. Notably, as the deployment becomes more sparse with larger grid sizes, the role of mobile sensors becomes more critical, representing a larger proportion of the total network to maintain connectivity over longer distances.

Average reaction delay as a function of grid granularity.

Performance was also measured by "reaction delay"—the sum of detection, transmission, and motion delay. The algorithm maintained an average reaction delay of approximately 9 to 12 seconds across various grid sizes, validating the practical utility of the Steiner-based connectivity approach for real-time monitoring.

Conclusion

This research demonstrates that hybridity is a powerful tool for WSN efficiency. Mobile sensors are most effective when used as the "connective tissue" between static clusters. Future work will explore scenarios with a fixed number of mobile sensors, shifting the optimization goal from minimum cost to minimum relay time, and accounting for more complex communication environments where propagation delay cannot be ignored.

Summary updated

Abstract

When detecting a target or monitoring a physical phenomenon in a region, the deployment problem is fundamental in these applications. Traditionally, stationary sensor networks are deployed to carry out the sensing operations. It is well known that the mobility of sensor nodes can improve the coverage and the probability of the detecting, so we deal with the problem of detecting a target using hybrid sensor networks which contain both stationary sensors and mobile sensors. In this paper, to begin with, we prove that the node deployment problem is NP-complete. Then, one polynomial algorithm for node deployment in hybrid wireless sensor networks is proposed, which aims at minimizing the number of all sensors to reduce the cost. The simulations verify the efficiency of our algorithm.
BibTeX
@article{zhang2011polynomial,
  author = {Lili Zhang and Jing Yuan and Yingchi Mao and Xiwei Zhang and Guihai Chen},
  title = {{Polynomial Algorithm for Node Deployment in Hybrid Wireless Sensor Networks}},
  journal = {International Journal of Wireless and Microwave Technologies},
  year = {2011},
  doi = {10.5815/ijwmt.2011.03.02},
}
Figure