ACapDS: An Energy-Efficient and Fault-Tolerant Distributed Capacitated Dominating Set Algorithm for Industrial IoT

Abstract

Design and analysis of energy-efficient and fault-tolerant dominating set (DS) algorithms are vital tasks for Industrial Internet of Things (IIoT) scenarios, as operational efficiency is a key objective in most industries. Such algorithms must maintain topology control, clustering, routing, and data aggregation. An IIoT deployment is said to pose the self-stabilization property if it can always recover to a steady state in a bounded time without any interruption whenever it is started at an unstable state. Self-stabilization is a fruitful principle for building fault-tolerant IIoT deployments. This paper proposes a novel distributed fault-tolerant capacitated DS (capDS) algorithm for IIoT systems. The algorithm is the first self-stabilizing capDS approach to the best of our knowledge. Proofs concerning the asynchronous behaviors of the algorithm, as well as the self-stabilization feature with regard to convergence and closure properties, are provided. R2C1 Besides, our theoretical analysis showed that the algorithm’s approximation ratio is 6 for IIoT setups implemented as unit disk graphs. Measurements made using our testbed of 40 IRIS motes and the extensive TOSSIM simulations revealed that the proposed algorithm is up to 55% better in terms of coefficient of variation, requires up to 61% fewer moves, causes up to 13% less data traffic, and consumes up to 14% less energy when compared to a randomized approach and a minimum ID priority-based approach.

Keywords

• Industrial Internet of Things (IIoT)
• minimum capacitated dominating set
• distributed algorithms
• self-stabilizing algorithms
• fault tolerance