Self-Stabilizing Capacitated Vertex Cover Algorithms for Internet-of-Things-Enabled Wireless Sensor Networks.

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(n2) step, where