An energy-efficient, self-stabilizing and distributed algorithm for maximal independent set construction in wireless sensor networks.

Highlights • We propose a maximal independent set algorithm for wireless sensor networks. • The proposed algorithm is fully distributed and self-stabilizing. • The upper bound of the move count is max {3 n − 6 , 2 n − 1 } (n is the node count) and 1.3 moves per node in the average case for random graphs. • We provide theoretical analysis for proof of correctness and average move count. • The proposed algorithm is compared with the previous work through extensive testbed experiments and simulations. Abstract Maximal independent set (MIS) is a very important structure that provides data aggregation, topology control and routing for wireless sensor networks (WSNs). Energy-efficient and fault-tolerant construction of MIS on WSNs is one of the vital tasks. A distributed sensor network is self-stabilizing if it can initially start at any state and regain a legal state in a finite time without any external intervention. Self-stabilization is a considerable method to provide fault tolerance in WSNs. This paper presents a distributed self-stabilizing MIS algorithm which is an improved version of Turau's algorithm under a fully distributed scheduler for WSNs. The proposed algorithm is theoretically analyzed and evaluated with its counterparts. The proposed algorithm is compared with the other studies through testbed experiments on IRIS nodes and simulations on TOSSIM environment. It is shown that the proposed algorithm outperforms other algorithms in terms of move count and energy consumption. [ABSTRACT FROM AUTHOR]