An Autonomous Connectivity Restoration Algorithm Based on Finite State Machine for Wireless Sensor-Actor Networks

Ying Zhang, Jun Wang, Guan HaoSensors 2018 · DOI

TL;DR

This paper introduces a novel algorithm, DCRMF, for autonomously restoring network connectivity in Wireless Sensor-Actor Networks (WSANs) when nodes fail. It leverages a finite state machine and the concept of connected dominating sets to efficiently identify critical nodes and minimize the movement of other nodes during restoration, outperforming existing methods in terms of total movement distance and number of relocated nodes.

What Problem Does This Paper Address?

Wireless Sensor-Actor Networks (WSANs) are increasingly used in critical applications like border protection and search and rescue, often in harsh environments. A key challenge in these networks is maintaining connectivity when individual sensor or actor nodes fail or become abnormal. Node failures can lead to network partitioning, disrupting data exchange and collaborative tasks. Existing solutions often involve either pre-provisioning redundant nodes (increasing cost and complexity) or reactive approaches that can incur significant movement overhead for node relocation, impacting energy efficiency and network performance. This paper addresses the need for an efficient, autonomous, and energy-conscious method to restore connectivity in WSANs, particularly when critical nodes fail.

Methods

The core of the proposed solution is the Distributed Autonomous Connectivity Restoration Algorithm Based on Finite State Machine (DCRMF). Key aspects include:

  • Finite State Machine (FSM) for Node Criticality: Each node is assigned a state (initial, unstable, non-dominating, stable dominance) managed by an FSM. This allows the network to dynamically assess the criticality of nodes.
  • Connected Dominating Set (CDS): The algorithm utilizes the concept of a CDS to identify critical nodes. A node is considered critical (a "cut-vertex") if its failure would partition the network. The FSM helps filter and update the CDS to adapt to dynamic network changes.
  • Selective Node Relocation: When an abnormal node is identified as critical, DCRMF selects the "optimal alternative node" from its neighbors. This selection prioritizes non-dominating nodes to minimize impact, followed by distance and node degree.
  • Distributed Regional Restoration: For scenarios with multiple simultaneous node failures in different regions, DCRMF employs a distributed strategy. It identifies independent regions and applies the single-node restoration algorithm within each region, preventing interference and improving efficiency.
  • Minimizing Movement Overhead: The algorithm's primary goal is to reduce the total distance moved by all nodes and the number of nodes that need to be relocated, thereby conserving energy and minimizing disruption.

Datasets

Not discussed in the paper. The authors conducted simulations using a custom setup.

Key Insights and Ideas

  • Criticality Matters: Not all node failures are equal. Identifying and prioritizing the restoration of "critical" nodes (cut-vertices) is crucial for efficient network recovery.
  • FSM for Dynamic Adaptability: Using a finite state machine allows the network to continuously adapt its understanding of node criticality as the network topology changes, a significant advantage in dynamic WSANs.
  • Non-Dominating Nodes as First Responders: Prioritizing the relocation of non-dominating nodes significantly reduces the cascade effect of failures and minimizes the overall number of nodes involved in restoration.
  • Regional Approach for Multiple Failures: Breaking down the problem of multiple failures into independent regional restorations is an effective way to manage complexity and maintain efficiency.

Key Results

Simulations comparing DCRMF with DARA, RIM, and LDMR showed that DCRMF consistently outperformed the others in:

  • Total Moving Distance: DCRMF achieved significantly lower total moving distances across various network sizes and densities. For example, with 200 nodes, DCRMF's total moving distance was approximately 75.1m, compared to DARA (212.4m), LDMR (92.3m), and RIM (572.8m).
  • Number of Relocated Nodes: DCRMF dramatically reduced the number of relocated nodes. In many scenarios, the average number of relocated nodes was around 1, whereas other algorithms involved significantly more. For instance, with 200 nodes, DCRMF averaged 1.2 relocated nodes, compared to DARA (6.1), LDMR (13.4), and RIM (20.4).
  • Message Overhead: DCRMF also demonstrated an advantage in the total number of messages sent, especially in larger networks, due to its efficient selection of non-dominating nodes.

Limitations and Future Work

  • Limited Discussion on Coverage: The paper acknowledges that while it focuses on connectivity restoration, the movement of nodes might impact network sensing coverage. This aspect is not deeply explored, and for applications with high sensitivity to coverage, further quantitative analysis of position optimization might be needed.
  • Future Work: The authors suggest that for applications requiring guaranteed sensing coverage, further research into quantitative position optimization for node relocation would be beneficial. The current work focuses on solving the critical problem of network connectivity restoration.

Summary updated

BibTeX
@article{zhang2018autonomous,
  author = {Ying Zhang and Jun Wang and Guan Hao},
  title = {{An Autonomous Connectivity Restoration Algorithm Based on Finite State Machine for Wireless Sensor-Actor Networks}},
  journal = {Sensors},
  year = {2018},
  doi = {10.3390/s18010153},
}
Figure