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

Basit Öğe Kaydı
dc.contributor.authorYigit, Yasin
dc.contributor.authorIleri, Can Umut
dc.contributor.authorDagdeviren, Orhan
dc.date.accessioned2019-10-27T10:44:16Z
dc.date.available2019-10-27T10:44:16Z
dc.date.issued2018
dc.departmentEge Üniversitesien_US
dc.description5th International Conference on Electrical and Electronics Engineering (ICEEE) -- MAY 03-05, 2018 -- Istanbul, TURKEYen_US
dc.description.abstractVertex 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.en_US
dc.description.sponsorshipIEEEen_US
dc.description.sponsorshipTUBITAK (Scientific and Technical Research Council of Turkey)Turkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK) [215E115, BIDEB-1001]en_US
dc.description.sponsorshipThis study was supported by TUBITAK (Scientific and Technical Research Council of Turkey) within the scope of 215E115 numbered project grant and the Ph.D. research grant (BIDEB-1001).en_US
dc.identifier.endpage427en_US
dc.identifier.isbn978-1-5386-6392-9
dc.identifier.startpage423en_US
dc.identifier.urihttps://hdl.handle.net/11454/30940
dc.identifier.wosWOS:000454450100085en_US
dc.identifier.wosqualityN/Aen_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.language.isoenen_US
dc.publisherIeeeen_US
dc.relation.ispartof2018 5Th International Conference on Electrical and Electronic Engineering (Iceee)en_US
dc.relation.publicationcategoryKonferans Öğesi - Uluslararası - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectself-stabilizationen_US
dc.subjectfault toleranceen_US
dc.subjectwireless sensor networksen_US
dc.subjectvertex coveren_US
dc.subjectindependent seten_US
dc.subjectdistributed algorithmsen_US
dc.subjectlink monitoringen_US
dc.titleFault Tolerance Performance of Self-stabilizing Independent Set Algorithms on a Covering-Based Problem: The Case of Link Monitoring in WSNsen_US
dc.typeConference Objecten_US

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu