Evaluating Fault Tolerance Properties of Self-Stabilizing Matching Algorithms in Wireless Sensor Networks
Authors:
- 1 June 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-5
Abstract
Self stabilization is an important paradigm for the autonomous recovery of a distributed system from transient failures such as energy depletion of nodes and disrupted connections. It has been used in wireless sensor networks (WSN) as these networks are expected to automatically recover from a transient fault without human intervention. Graph matching is fundamental a graph theory problem which has a broad application range in WSNs and it has been studied extensively in self-stabilizing settings. In this work, we build a simulation model and perform tests to evaluate the fault tolerance properties of self-stabilizing matching algorithms. To the best of our knowledge, this is the first practical evaluation of these algorithms. Considering WSNs, we assume distributed fair and synchronous schedulers. Simulation results have shown that there is a tradeoff between stabilization time of algorithms and the quality of their results. The improvement algorithms which has better lower bounds give better matchings at the cost of longer durations of instability.Keywords
This publication has 24 references indexed in Scilit:
- Detection of node failure in Wireless Sensor Networks2014
- Self-stabilizing algorithm for efficient topology control in Wireless Sensor NetworksJournal of Computational Science, 2013
- Dynamic decentralised algorithms for cognitive radio relay networks with multiple primary and secondary users utilising matching theoryTransactions on Emerging Telecommunications Technologies, 2013
- A self-stabilizing 23-approximation algorithm for the maximum matching problemTheoretical Computer Science, 2011
- A new self-stabilizing maximal matching algorithmTheoretical Computer Science, 2009
- GS3: scalable self-configuration and self-healing in wireless sensor networksComputer Networks, 2003
- Maximal matching stabilizes in time O(m)Information Processing Letters, 2001
- Self-stabilizing Neighborhood Unique Naming under Unfair SchedulerLecture Notes in Computer Science, 2001
- Maximal matching stabilizes in quadratic timeInformation Processing Letters, 1994
- A self-stabilizing algorithm for maximal matchingInformation Processing Letters, 1992