A Self-adaptive Fault-Tolerant Mechanism in Wireless Sensor Networks

Wei Xiao, Ming Xu, Yingwen ChenInfoscale 2009 · DOI

TL;DR

This paper introduces a novel self-adaptive mechanism for wireless sensor networks (WSNs) that enhances fault tolerance and network throughput. By dynamically adjusting sensor transport attempt probabilities based on their confidence rates, the system can effectively isolate faulty nodes and maintain optimal network performance even under failure conditions.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are increasingly deployed for a wide range of applications, from environmental monitoring to smart spaces. These networks rely on numerous sensors collaborating to collect, process, and transmit data. A critical challenge in WSNs is the inherent unreliability of individual sensor nodes, which can fail due to various reasons like energy depletion, hardware issues, or communication errors. Traditional approaches to optimizing WSN performance, such as forming optimal network topologies for efficient data aggregation and transmission, often overlook the impact of these node failures. This can lead to decreased data reliability and overall network performance. The paper addresses the need for a fault-tolerant mechanism that can adapt to these failures and maintain high throughput and reliability in WSNs, particularly in the context of "in-network" computing where sensors perform local computations before transmitting data.

Methods

The core of the proposed mechanism is a self-adaptive fault-tolerant approach that dynamically adjusts the transport attempt probability (TAP) of each sensor node. This adjustment is based on a confidence rate (CR) assigned to each sensor.

Here's a breakdown of the key techniques:

  • Confidence Rate (CR) Calculation: When a fusion sensor (or sink node) receives data, it first calculates an average value. Then, it determines the dissimilarity of each sensor's reading from this average. This dissimilarity is used to compute a confidence rate for each sensor. Sensors with readings closer to the average receive higher confidence rates, while those with significant deviations receive lower rates. This process is iterative, with confidence rates being re-evaluated in each round to reflect a sensor's historical performance and correlation with the final aggregated result.
  • Transport Attempt Probability (TAP) Adjustment: A relational function is established between the confidence rate (CR) and the transport attempt probability (TAP). Sensors with high confidence rates are assigned higher TAPs, encouraging more data transmission and contributing to higher network throughput. Conversely, sensors with low confidence rates (indicating potential faults) are assigned very low or zero TAPs, effectively isolating them from the network and preventing them from corrupting the aggregated data.
  • Fault-Tolerant Maximum Average-Weighted Spanning Subgraph (FTMAWSS): The paper proposes an algorithm to construct an optimal network subgraph that is fault-tolerant. This is an adaptation of the Maximum Average-Weighted Spanning Subgraph (MAWSS) concept. The FTMAWSS algorithm aims to find a subgraph that maximizes overall network throughput while considering the impact of node failures. It involves identifying the heaviest outgoing edges and then constructing a minimum weight out-branching to approximate the FTMAWSS.

Datasets

Not discussed in the paper. The evaluation is performed using simulations with the NS-2 simulator.

Key Insights and Ideas

  • Dynamic Adaptation is Crucial: The paper highlights that static network topologies are insufficient for robust WSN operation. The ability to dynamically adjust sensor behavior based on real-time performance and fault detection is key to maintaining reliability.
  • Confidence Rate as a Proxy for Faultiness: The confidence rate, derived from the deviation of a sensor's reading from the aggregated average, serves as an effective indicator of a sensor's reliability. This allows the system to implicitly identify and penalize faulty nodes.
  • TAP-CR Relationship is Key to Throughput: The direct correlation between a sensor's confidence rate and its transport attempt probability is a clever way to balance fault tolerance with network throughput. By increasing TAP for reliable nodes, the network can achieve higher data exchange rates.
  • FTMAWSS Outperforms MAWSS in Faulty Scenarios: The proposed FTMAWSS, by explicitly considering node failures during subgraph construction, demonstrates superior performance compared to traditional MAWSS in terms of average delay and packet loss ratio when node failures are present.

Key Results

The simulation results, conducted using the NS-2 simulator, demonstrate the effectiveness of the proposed self-adaptive fault-tolerant mechanism:

  • Reduced Average Delay: FTMAWSS significantly reduces average delay compared to MAWSS, especially in the presence of node failures. For instance, with 20% node failures, the delay in MAWSS was observed to be 90% higher than in FTMAWSS. The increase in delay with a higher proportion of failed nodes is also lower in FTMAWSS.
  • Improved Packet Delivery Ratio: FTMAWSS maintains a higher average effective packet delivery ratio, indicating that more correct packets reach the sink. This ratio remains reasonable even with a high percentage of node failures.
  • Lower Packet Loss Ratio: The packet loss ratio is consistently lower in FTMAWSS compared to MAWSS across various network sizes and failure rates. This is attributed to the algorithm's ability to detect and isolate faulty nodes.
  • Effectiveness of Different Topologies: Experiments comparing FTMAWSS with a randomly constructed topology (RANDOM) showed that FTMAWSS achieves steady average delay even with increasing node failures. While RANDOM's delay increases rapidly with failures, FTMAWSS and MAWSS maintain stability. Interestingly, RANDOM showed a higher effective packet delivery ratio than MAWSS when failure percentages exceeded 12%, a phenomenon the authors suggest might be due to the decreasing probability of transmitting through fault nodes in RANDOM at high densities.

Limitations and Future Work

  • NP-Completeness: The paper acknowledges that constructing an optimal FTMAWSS is NP-complete, similar to MAWSS. The proposed algorithm provides an approximation.
  • Simulation-Based Evaluation: The results are based on simulations using the NS-2 simulator. Real-world deployment and testing would be necessary to fully validate the mechanism.
  • Future Work: The authors suggest that the best bounds for TAP created from CR will be investigated carefully to gain efficient throughput topology in given sensor networks. Further research could explore more sophisticated fault detection mechanisms, different types of faults, and the impact of dynamic network changes (e.g., node mobility).

Summary updated

BibTeX
@inproceedings{xiao2009self,
  author = {Wei Xiao and Ming Xu and Yingwen Chen},
  title = {{A Self-adaptive Fault-Tolerant Mechanism in Wireless Sensor Networks}},
  booktitle = {Infoscale},
  year = {2009},
  doi = {10.1007/978-3-642-10485-5\_17},
}
Figure