Fault Tolerance Performance of Self-stabilizing Independent Set Algorithms on a Covering-Based Problem: The Case of Link Monitoring in WSNs

Yigit Y., Ileri C. U. , DAĞDEVİREN O.

5th International Conference on Electrical and Electronics Engineering (ICEEE), İstanbul, Turkey, 3 - 05 May 2018, pp.423-427 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume:
  • Doi Number: 10.1109/iceee2.2018.8391375
  • City: İstanbul
  • Country: Turkey
  • Page Numbers: pp.423-427


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.