HAS: A Heuristic Adaptive Sink Sensor Set Selection for Underwater AUV-Aid Data Gathering Algorithm

Xingwang Wang, Debing Wei, Xiaohui Wei, Jun-Hong Cui, Miao PanSensors 2018 · OpenReview

TL;DR

This paper introduces HAS⁴, a novel algorithm for efficiently gathering data in underwater wireless sensor networks (UWSNs) by strategically selecting which sensors an autonomous underwater vehicle (AUV) should visit. HAS⁴ aims to balance energy consumption, reduce AUV travel costs, and extend network lifetime by intelligently choosing "sink" sensors for direct AUV collection, while others relay data acoustically.

What Problem Does This Paper Address?

Underwater environments present unique challenges for data gathering. Traditional methods of retrieving data are slow and costly. To address this, researchers are exploring the use of Autonomous Underwater Vehicles (AUVs) as mobile data mules. However, AUVs have limited energy and mobility, meaning they can only visit a fraction of the sensors in a network. This creates a problem: how to efficiently select which sensors the AUV should visit (sink sensors) to collect data, while the remaining sensors acoustically transmit their data to these sink sensors. This selection process is critical for minimizing energy consumption, reducing the AUV's travel distance, and ultimately prolonging the overall network lifetime. Existing approaches often struggle to balance these competing objectives, especially in the context of the unique communication constraints of underwater environments.

Methods

The paper proposes a heuristic algorithm called HAS⁴ (Heuristic Adaptive Sink Sensor Set Selection) to tackle the sink sensor selection problem. HAS⁴ is designed to be adaptable and can operate in both centralized and distributed modes.

  • Problem Formulation: The core problem is formulated as a Mixed Integer Linear Program (MILP) that considers energy consumption from acoustic communication, AUV travel distance, and energy balance among sensors to maximize network lifetime.
  • HAS⁴ Algorithm:
    • Centralized HAS⁴: This version leverages complete network information. It first estimates the lifetime of each sensor and sorts them. A trade-off factor l is introduced to balance AUV travel cost and network lifetime. The algorithm greedily selects sensors with shorter lifetimes to be visited by the AUV, aiming to offload their data and prevent them from becoming energy bottlenecks. It then iteratively selects sensors for the AUV to visit, considering their lifetime and network constraints.
  • Distributed HAS⁴: This version operates in a multi-round procedure where sensors self-elect their roles (sink or relay) based on their lifetime and proximity to potential sink nodes. It involves stages like self-elect inquiry, self-elect affirmation, root selection, and channel occupation to achieve a distributed sink selection.

The algorithm utilizes a novel high-speed magnetic-induction (MI) communication system for AUV-sensor communication, complementing the longer-range but lower-bandwidth acoustic communication used between sensors.

Datasets

Not discussed in the paper. The evaluation is based on simulations.

Key Insights and Ideas

  • Balancing Competing Objectives: The paper highlights the inherent trade-off between minimizing AUV travel distance (visiting fewer sensors) and maximizing network lifetime (visiting more sensors to offload their data and reduce acoustic transmissions). HAS⁴'s trade-off factor l is a key mechanism for managing this.
  • Proactive Energy Balancing: By prioritizing sensors with shorter estimated lifetimes for AUV visits, HAS⁴ aims to proactively balance energy consumption across the network, preventing premature failure of individual nodes and extending the overall network's operational period.
  • Leveraging Hybrid Communication: The integration of high-speed MI for AUV-sensor communication and acoustic for sensor-to-sensor communication is crucial. MI offers a significant advantage in terms of speed and energy efficiency for direct data offloading, while acoustic communication is necessary for data relaying in areas not directly visited by the AUV.
  • Centralized vs. Distributed Trade-offs: The paper presents both centralized and distributed versions of HAS⁴, acknowledging that while centralized approaches can achieve better sub-optimal solutions due to global information, distributed approaches are more scalable and practical for large, dynamic underwater networks.

Key Results

  • Improved Network Lifetime: Both centralized and distributed versions of HAS⁴ demonstrated improved network lifetime compared to benchmark methods.
  • Reduced AUV Travel Cost: The algorithms also showed a reduction in the AUV's travel distance.
  • Performance Trends:
    • Network lifetime generally decreases with increasing network size due to higher data forwarding demands.
  • Centralized algorithms outperformed distributed ones in simulations, as expected, due to their access to global information.
  • The trade-off factor l in centralized HAS⁴ positively impacts network lifetime by allowing more sensors to be designated as AUV-visited (SA nodes), thus reducing acoustic communication.
  • In distributed HAS⁴, a higher threshold (representing a longer maximum acoustic path) leads to fewer SA nodes, which also reduces acoustic communication and increases lifetime.

Limitations and Future Work

  • Scalability of Centralized HAS⁴: The paper acknowledges that the centralized HAS⁴ might not be scalable for very large underwater networks due to propagation delays and AUV speed limitations.
  • Simulation-Based Evaluation: The results are based on simulations, and real-world deployment would be necessary for full validation.
  • Future Work: The authors suggest exploring scenarios involving multiple AUVs, task partitioning, and online path planning for more complex underwater data collection challenges in large-scale UWSNs. They also aim to further investigate underwater data collection, including multi-AUV coordination, task partitioning, and online path planning.

Summary updated

Abstract

In this paper, we target solving the data gathering problem in underwater wireless sensor networks. In many underwater applications, it is not quick to retrieve sensed data, which gives us the opportunity to leverage mobile autonomous underwater vehicles (AUV) as data mules to periodically collect it. For each round of data gathering, the AUV visits part of the sensors, and the communication between AUV and sensor nodes is a novel high-speed magnetic-induction communication system. The rest of the sensors acoustically transmit their sensed data to the AUV-visit sensors. This paper deploys the HAS 4 (Heuristic Adaptive Sink Sensor Set Selection) algorithm to select the AUV-visited sensors for the purpose of energy saving, AUV cost reduction and network lifetime prolonging. By comparing HAS 4 with two benchmark selection methods, experiment results demonstrate that our algorithm can achieve a better performance.
BibTeX
@inproceedings{wang2018has,
  author = {Xingwang Wang and Debing Wei and Xiaohui Wei and Jun-Hong Cui and Miao Pan},
  title = {{HAS: A Heuristic Adaptive Sink Sensor Set Selection for Underwater AUV-Aid Data Gathering Algorithm}},
  booktitle = {Sensors},
  year = {2018},
  url = {https://openreview.net/forum?id=6PRM0bZXdK},
}
Figure