Fault tolerance performance of self-stabilizing independent set algorithms on a covering-based problem: The case of link monitoring in WSNs

Yasin Yigit, Can Umut Ileri, Orhan Dagdeviren

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

2 Citations (Scopus)

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.

Original languageEnglish
Title of host publication2018 5th International Conference on Electrical and Electronics Engineering, ICEEE 2018
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages423-427
Number of pages5
ISBN (Electronic)9781538663929
DOIs
Publication statusPublished - 20 Jun 2018
Externally publishedYes
Event5th International Conference on Electrical and Electronics Engineering, ICEEE 2018 - Istanbul, Turkey
Duration: 3 May 20185 May 2018

Conference

Conference5th International Conference on Electrical and Electronics Engineering, ICEEE 2018
CountryTurkey
CityIstanbul
Period3/05/185/05/18

Keywords

  • distributed algorithms
  • fault tolerance
  • independent set
  • link monitoring
  • self-stabilization
  • vertex cover
  • wireless sensor networks

Fingerprint Dive into the research topics of 'Fault tolerance performance of self-stabilizing independent set algorithms on a covering-based problem: The case of link monitoring in WSNs'. Together they form a unique fingerprint.

Cite this