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 link monitoring problem. It well known that a solution to independent set problem (IS), which another problem, complement VC. Self- stabilization an important concept designing fault tolerance systems. There have many self-stabilizing VC IS algorithms field. Even though algorithm can provide solutions, it does not give theoretical guarantee on approximation ratio. In this work, we focus practical performance self- stabilizing case vertex WSNs. We implement all existing make simulations assuming WSN nodes run synchronously. Results show general are able find better covers than algorithms, as they roughly 15% smaller sets. Furthermore, under distributed scheduler converges desired configuration considerably less number rounds algorithms.