An Energy-Efficient Distributed Cut Vertex Detection Algorithm for Wireless Sensor Networks

Maintaining connectivity is a very important objective of wireless sensor networks (WSNs) in successfully achieving data collection for applications. A cut vertex (node) is defined as a critical vertex whose removal disconnects a network component and partially disables data delivery. Hence, it is crucial that cut vertices be detected and treated with caution. In this paper, we propose an energy-efficient cut vertex detection (CVD) algorithm for WSNs. Our algorithm uses a depth-first search approach and is completely distributed. It benefits from the radio multicast capabilities of sensor nodes and is the first algorithm with a time complexity of O(N) and a sent message complexity of O(N), in which each message is O(log(2)(N)) bits. We show the operation of the algorithm, analyze it in detail, provide testbed experiments and extensive simulations. We compare our proposed algorithm with the other CVD algorithms and show that our algorithm saves up to 6.8 times more energy in less time.