Fault tolerance performance of self-stabilizing independent set algorithms on a covering-based problem: The case of link monitoring in WSNs
- 1 May 2018
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 1, 423-427
Abstract
Vertex cover (VC) is one of the most fundamental graph-theoretical problems and has been widely used in wireless sensor networks (WSNs), particularly for the link monitoring problem. It is well known that a solution to the independent set problem (IS), which is another fundamental graph-theoretical problem, is complement of a VC. Self- stabilization is an important concept for designing fault tolerance systems. There have been many self-stabilizing VC and IS algorithms in the field. Even though a self-stabilizing IS algorithm can provide VC solutions, it does not give a theoretical guarantee on approximation ratio. In this work, we focus on practical fault tolerance performance of self- stabilizing IS algorithms in case of a vertex cover problem, particularly link monitoring in WSNs. We implement all existing self-stabilizing VC and IS algorithms and make simulations assuming a WSN in which nodes run synchronously. Results show that self-stabilizing IS algorithms in general are able to find better covers than VC algorithms, as they provide roughly 15% smaller solution sets. Furthermore, IS algorithms that run under distributed scheduler converges to a desired configuration in considerably less number of rounds than VC algorithms.Keywords
This publication has 31 references indexed in Scilit:
- A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphsJournal of Parallel and Distributed Computing, 2010
- Practical Beacon Placement for Link Monitoring Using Network TomographyIEEE Journal on Selected Areas in Communications, 2006
- Randomized Self-stabilizing Algorithms for Wireless Sensor NetworksLecture Notes in Computer Science, 2006
- On efficient fixed-parameter algorithms for weighted vertex coverJournal of Algorithms, 2003
- TOSSIM2003
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and HypergraphsSIAM Journal on Computing, 2002
- Some optimal inapproximability resultsJournal of the ACM, 2001
- Self-stabilization over unreliable communication mediaDistributed Computing, 1993
- A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem1985
- Depth-first search and the vertex cover problemInformation Processing Letters, 1982