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

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.