TAPU: Test and pick up-based $k$-connectivity restoration algorithm for wireless sensor networks

Authors: VAHİD KHALİLPOUR AKRAM, ORHAN DAĞDEVİREN

Abstract: A $k$-connected wireless sensor network remains connected if any $k$-1 arbitrary nodes stop working. The aim of movement-assisted $k$-connectivity restoration is to preserve the $k$-connectivity of a network by moving the nodes to the necessary positions after possible failures in nodes. This paper proposes an algorithm named TAPU for $k$-connectivity restoration that guarantees the optimal movement cost. Our algorithm improves the time and space complexities of the previous approach (MCCR) in both best and worst cases. In the proposed algorithm, the nodes are classified into safe and unsafe groups. Failures of safe nodes do not change the $k$ value of the network while failures of unsafe nodes reduce the $k$ value. After an unsafe node's failure, the shortest path tree of the failed node is generated. Each node moves to its parent location in the tree starting from a safe node with the minimum moving cost to the root. TAPU has been implemented on simulation and testbed environments including Kobuki robots and Iris nodes. The measurements show that TAPU finds the optimum movement up to 79.5 % faster with 50 % lower memory usage than MCCR and with up to 59 % lower cost than the greedy algorithms.

Keywords: Wireless sensor networks, network connectivity, movement-assisted $k$-connectivity restoration, fault tolerance, reliability

Full Text: PDF