Citation: Yigit, Y.; Dagdeviren, O.;
Challenger, M. Self-Stabilizing
Capacitated Vertex Cover Algorithms
for Internet-of-Things-Enabled
Wireless Sensor Networks. Sensors
2022, 22, 3774. https://doi.org/
10.3390/s22103774
Academic Editor: Omer Gurewitz
Received: 29 March 2022
Accepted: 13 May 2022
Published: 16 May 2022
Publisher’s Note: MDPI stays neutral
with regard to jurisdictional claims in
published maps and institutional affil-
iations.
Copyright: © 2022 by the authors.
Licensee MDPI, Basel, Switzerland.
This article is an open access article
distributed under the terms and
conditions of the Creative Commons
Attribution (CC BY) license (https://
creativecommons.org/licenses/by/
4.0/).
Article
Self-Stabilizing Capacitated Vertex Cover Algorithms for
Internet-of-Things-Enabled Wireless Sensor Networks
Yasin Yigit
1
, Orhan Dagdeviren
1,
* and Moharram Challenger
2,3
1
International Computer Institute, Ege University, Bornova, 35100
˙
Izmir, Turkey; yasin.yigit@hotmail.com.tr
2
Department of Computer Science, University of Antwerp, 2020 Antwerpen, Belgium;
moharram.challenger@uantwerpen.be
3
AnSyMo/Cosys Core-Lab, Flanders Make Strategic Research Center, 3001 Leuven, Belgium
* Correspondence: orhan.dagdeviren@ege.edu.tr
Abstract:
Wireless sensor networks (WSNs) achieving environmental sensing are fundamental
communication layer technologies in the Internet of Things. Battery-powered sensor nodes may
face many problems, such as battery drain and software problems. Therefore, the utilization of
self-stabilization, which is one of the fault-tolerance techniques, brings the network back to its
legitimate state when the topology is changed due to node leaves. In this technique, a scheduler
decides on which nodes could execute their rules regarding spatial and temporal properties. A
useful graph theoretical structure is the vertex cover that can be utilized in various WSN applications
such as routing, clustering, replica placement and link monitoring. A capacitated vertex cover is
the generalized version of the problem which restricts the number of edges covered by a vertex
by applying a capacity constraint to limit the covered edge count. In this paper, we propose two
self-stabilizing capacitated vertex cover algorithms for WSNs. To the best of our knowledge, these
algorithms are the first attempts in this manner. The first algorithm is stabilized under an unfair
distributed scheduler (that is, the scheduler which does not grant all enabled nodes to make their
moves but guarantees the global progress of the system) at most
O(n
2
)
step, where
n
is the count of
nodes. The second algorithm assumes 2-hop (degree 2) knowledge about the network and runs under
the unfair scheduler, which subsumes the synchronous and distributed fair scheduler and stabilizes
itself after
O(n)
moves in
O(n)
step , which is acceptable for most WSN setups. We theoretically
analyze the algorithms to provide proof of correctness and their step complexities. Moreover, we
provide simulation setups by applying IRIS sensor node parameters and compare our algorithms
with their counterparts. The gathered measurements from the simulations revealed that the proposed
algorithms are faster than their competitors, use less energy and offer better vertex cover solutions.
Keywords:
wireless sensor networks; internet of things; self-stabilization; capacitated vertex cover;
energy efficiency
1. Introduction
Wireless sensor networks (WSNs) do not have a predefined structure to maintain
fundamental data-transfer operations. They are crucial communication layer technologies
for providing environmental sensing operations in the Internet of Things (IoT). Most of
the time, WSNs are deployed for various applications in forests, mines and land borders,
where they should bear harsh circumstances [
1
–
3
]. In such environments, tiny sensor motes
can malfunction due to natural challenges. Fault tolerance is an important property to deal
with these kinds of challenges. Self-stabilization is one of the best candidates for WSNs to
provide fault tolerance and to deal with their ad hoc nature.
A sensor node can leave WSN due to software failures, battery drains and other
similar faults. A distributed setting like WSN is considered self-stabilizing if it reaches a
legitimate state in case of node leaves. More formally, a system is self-stabilizing if and only
Sensors 2022, 22, 3774. https://doi.org/10.3390/s22103774 https://www.mdpi.com/journal/sensors
