Fault tolerance performance of self-stabilizing independent set algorithms on a covering-based problem: The case of link monitoring in WSNs
Conference paper > Full Text · 2018
Authors: Yasin Yigit, CAN UMUT İLERİ, Orhan DAĞDEVİREN
2018 5th International Conference on Electrical and Electronic Engineering (ICEEE), Turkey, İstanbul, International, Verbal, Full Text, 2018-2018, vol , pp 423-427
DOI: 10.1109/iceee2.2018.8391375
Summary
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.