Energy efficiency in two-tiered wireless sensor networks

Jun Guo, Erdem Koyuncu, Hamid Jafarkhani

TL;DR

This paper tackles the critical problem of minimizing energy consumption in two-tiered wireless sensor networks (WSNs) by optimizing the placement of access points (APs) and base stations (BSs). They introduce novel algorithms, inspired by Lloyd's clustering method, that significantly reduce power usage compared to random deployments, achieving up to a 79% saving.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are crucial for data collection in various applications, but their limited battery life poses a significant challenge. In many WSN architectures, energy consumption is dominated by communication. This paper focuses on two-tiered WSNs, where sensors first send data to Access Points (APs), which then forward it to Base Stations (BSs). The problem is that the optimal placement of these APs and BSs to minimize overall energy consumption is not well-understood. Existing work often focuses on either sensor placement or AP placement in simpler network structures, leaving a gap in optimizing the joint deployment of APs and BSs in a hierarchical WSN for energy efficiency.

Methods

The authors formulate the energy consumption as a distortion measure, combining the power required for sensors to transmit to APs and for APs to transmit to BSs, with a weighting factor to prioritize sensor energy. They then propose a two-pronged approach:

  1. Analytical Solutions for Special Cases: For simpler scenarios (e.g., one BS), they derive analytical solutions for optimal AP and BS placement. This involves showing that optimal AP locations are linear transformations of optimal quantizer reproduction points, and the BS should be at the geometric centroid of the sensing area.
  2. Lloyd-like Algorithms for General Cases: For more complex scenarios with multiple APs and BSs, they develop two novel algorithms:
  3. One-Tiered Lloyd (OTL) Algorithm: This algorithm uses two independent Lloyd algorithms. One optimizes BS placement, and the other optimizes AP placement and partitioning.
  4. Two-Tiered Lloyd (TTL) Algorithm: This algorithm directly addresses the two-tiered structure by iteratively optimizing AP movement, AP partitioning (using energy Voronoi diagrams), BS movement, and clustering.

Both algorithms are designed to iteratively refine the deployment and partitioning to minimize the defined distortion.

Datasets

Not discussed in the paper. The authors use simulated environments with defined target regions and traffic density functions for evaluation.

Key Insights and Ideas

  • Two-tiered optimization is crucial: Simply optimizing APs or BSs independently is insufficient; their joint placement significantly impacts overall energy efficiency.
  • Geometric centroid is key for BSs: In simpler, single-BS scenarios, placing the BS at the geometric centroid of the sensing area is optimal.
  • APs are "shrunk" quantizers: Optimal AP locations are derived from optimal quantizer locations, effectively "shrinking" them towards their assigned BS.
  • Energy Voronoi Diagrams (EVDs): The concept of EVDs is introduced to define optimal AP partitioning based on both sensor-to-AP and AP-to-BS energy costs.
  • Lloyd's algorithm adaptation: The paper successfully adapts the well-established Lloyd algorithm for clustering to solve the more complex two-tiered deployment problem, demonstrating its versatility.
  • Significant energy savings: The proposed algorithms offer substantial energy savings, highlighting the practical impact of optimized deployment.

Key Results

The paper demonstrates significant energy savings through simulations:

  • WSN1 (1 BS, 20 APs): OTL saves 53.61% and TTL saves 53.71% of the weighted power on average compared to random deployment.
  • WSN2 (4 BSs, 20 APs): OTL saves 79.29% and TTL saves 79.16% of the weighted power on average.
  • The TTL algorithm, which directly models the two-tiered structure, generally achieves slightly better or comparable results to OTL.
  • The analytical solutions for special cases provide theoretical underpinnings and benchmarks for the algorithmic approaches.

Limitations and Future Work

  • Homogeneous network assumption: The current work assumes homogeneous sensors, APs, and BSs (e.g., identical antenna gains, SNR thresholds). Future work could explore heterogeneous scenarios.
  • Uniform density assumption in some analytical parts: While general algorithms are proposed, some analytical derivations rely on uniform data density. Extending these to non-uniform densities would be valuable.
  • Limited discussion on dynamic environments: The current work focuses on static deployment. Future research could investigate how to adapt deployments in dynamic environments where nodes may fail or move.
  • Scalability for very large networks: While the algorithms show good performance, their scalability to extremely large numbers of nodes could be further investigated.

Summary updated

Abstract

We study a two-tiered wireless sensor network (WSN) consisting of N access points (APs) and M base stations (BSs). The sensing data, which is distributed on the sensing field according to a density function f, is first transmitted to the APs and then forwarded to the BSs. Our goal is to find an optimal deployment of APs and BSs to minimize the average weighted total, or Lagrangian, of sensor and AP powers. For M = 1, we show that the optimal deployment of APs is simply a linear transformation of the optimal N-level quantizer for density f, and the sole BS should be located at the geometric centroid of the sensing field. Also, for a one-dimensional network and uniform f, we determine the optimal deployment of APs and BSs for any N and M. Moreover, to numerically optimize node deployment for general scenarios, we propose one-and two-tiered Lloyd algorithms and analyze their convergence properties. Simulation results show that, when compared to random deployment, our algorithms can save up to 79% of the power on average.
BibTeX
@inproceedings{guo2017energy,
  author = {Jun Guo and Erdem Koyuncu and Hamid Jafarkhani},
  title = {{Energy efficiency in two-tiered wireless sensor networks}},
  booktitle = {ICC},
  year = {2017},
  url = {https://openreview.net/forum?id=kaLFpaBcsV},
}
Figure