Novel Deployment Schemes for Mobile Sensor Networks

Jiming Chen, Shijian Li, Youxian SunSensors 2007 · DOI

TL;DR

This paper tackles the challenge of efficiently deploying mobile sensor nodes to maximize coverage in a given area. The authors propose two improved Virtual Force Algorithms (VFA) that address limitations of the original VFA, such as slow convergence and wasted energy, leading to better coverage, reduced energy consumption, and faster deployment.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are increasingly deployed for environmental monitoring and data collection. A critical aspect of WSN effectiveness is ensuring adequate coverage of the Region of Interest (ROI). While manual deployment is often impractical, random initial placement of sensor nodes can lead to inefficient resource utilization and coverage gaps. Mobile sensor nodes offer a solution by allowing autonomous adjustment of their positions to optimize coverage. The Virtual Force Algorithm (VFA) is a popular method for this, simulating attractive and repulsive forces between nodes to guide their movement. However, the original VFA suffers from several drawbacks: it can lead to nodes oscillating around their optimal positions without reaching a stable state, it can cause nodes to move unnecessarily outside the ROI, and it can be slow to converge, all of which waste energy and reduce overall efficiency. This paper aims to improve VFA to overcome these limitations.

Methods

The authors propose two novel deployment schemes to enhance the original Virtual Force Algorithm (VFA):

  • Improved VFA (IVFA): This approach introduces an "effective communication distance" ($C_{th}$). Forces are only considered between nodes within this distance. This helps nodes converge faster by preventing long-range attractive forces from pulling nodes unnecessarily. Additionally, IVFA incorporates a "maximum step size" ($Maxstep$) to limit how far a node can move in a single iteration, further preventing excessive movement and energy waste. Boundary constraints are also implemented to keep nodes within the ROI.
  • Exponential VFA (EVFA): This scheme modifies the virtual force relationship to decrease exponentially with distance. This aims to achieve faster convergence and better coverage. The new force function is applied, and node positions are updated using the same boundary and step-size constraints as in IVFA.

Datasets

Not discussed in the paper. The evaluation relies on simulations.

Key Insights and Ideas

  • The "boundary effect" is a significant problem: Mobile sensors can move out of the designated ROI, wasting valuable resources and potentially failing the sensing task, especially in densely deployed networks.
  • Oscillation is a major convergence issue: The original VFA can cause nodes to continuously move without settling into a stable configuration, leading to wasted energy and prolonged deployment times.
  • Effective communication distance is key to faster convergence: Limiting the range of forces considered between nodes helps them reach a stable state more quickly.
  • Exponential force decay can accelerate convergence: By making forces diminish more rapidly with distance, nodes can reach their optimal positions faster.
  • Improved VFA variants are less sensitive to force coefficients: Unlike the original VFA, IVFA and EVFA show more consistent performance across different values of the repulsive force coefficient ($W_r$), making them more robust.

Key Results

  • Improved Coverage: Both IVFA and EVFA consistently achieve higher coverage rates compared to the original VFA. For a network size of 200 nodes, IVFA and EVFA achieve near-perfect coverage (approximately 1), while VFA stabilizes at around 40%.
  • Reduced Energy Consumption: IVFA and EVFA significantly reduce the moving energy consumption of sensor nodes compared to VFA. VFA nodes move almost at the maximum step in every iteration, whereas IVFA and EVFA converge much faster, leading to less overall movement.
  • Faster Convergence: IVFA and EVFA converge to a steady coverage state much faster than VFA. For instance, IVFA and EVFA achieve steady coverage in 8-40 iterations, while VFA requires 80 iterations. EVFA, in particular, shows excellent convergence properties, making nodes static at the end of deployment.
  • Robustness to Coefficients: IVFA and EVFA are not sensitive to the virtual force coefficient ($W_r$), maintaining good performance across different values. VFA's performance improves with larger $W_r$, but it still exhibits oscillations and fails to stabilize even at very high $W_r$.

Limitations and Future Work

  • Distributed Convergence: The paper acknowledges that while simulations show convergence, a theoretical and systematic discussion of distributed convergence for the nodes is left as future work.
  • Scarcely Deployed Networks: The paper notes that VFA struggles to achieve convergence even in small-scale, sparsely deployed WSNs due to its complicated force relationship. While IVFA and EVFA improve this, further research might be needed for extremely sparse scenarios.
  • Real-world Deployment: The current study is based on simulations. Future work could involve testing these algorithms in real-world WSN deployments to validate their performance under practical conditions.

Summary updated

Abstract

Virtual Force Algorithm (VFA) is becoming a main solution to area coverage forhomogeneous wireless sensor networks with random distribution of mobile sensor nodes.Consider the factors of the convergence, the boundary in Region Of Interest (ROI), effec-tive distance of acting force and useless moving, etc, VFA is improved to overcome the aboveproblems. Furthermore, an expression of exponential function for the relationship of vir-tual force is proposed to converge rapidly. Extensive simulation results indicate that theseimproved VFA get better performance in coverage rate, moving energy consumption, conver-gence etc. than original VFA.
BibTeX
@inproceedings{chen2007novel,
  author = {Jiming Chen and Shijian Li and Youxian Sun},
  title = {{Novel Deployment Schemes for Mobile Sensor Networks}},
  booktitle = {Sensors},
  year = {2007},
  doi = {10.3390/s7112907},
}
Figure