Distributed k-Connectivity Detection and Restoration Algorithms for Wireless Sensor and Actor Networks
Project no. 536 · Status: Kapanmış · 2015
Summary
In Wireless Sensor and Actor Networks (WSAN), some node failures break the connection of the network and prevent communication of other active nodes. Any k-1 node failures in k-connected networks can not corrupt the network connection. Overall, in this project we focused on two problems and proposed efficient algorithms for solving problems. The first problem is the determination of the value of k for WSAN. In this project we propose three different algorithms that better predict the state of connectivity and an algorithm that finds k precisely. By defining new rules for the dominator sets in CDSCUT algorithm we proposed, the nodes are detected more effectively. In our DEV algorithm, the smallest minimum cut sets are found using an evolutionary search method. The PACK that we proposed colors the path between the nodes and finds k correctly. In the DECK algorithm, which is the last distributed algorithm we propose, the value of k is always correct. The second problem we are working on is the restoration of the network's k-connectivity by moving the nodes. We proposed three movemenent-based central algorithms and three distributed algorithms, identifying the new movement models. In the proposed central TAPU1, TAPU2 and PINC algorithms, the k-connectivity restoration can be done best in position constrained and position-edge constrained motion models. In the distributed L-PINC, LINAR and DKR algorithms, the restoration process is performed on the local information of each node. Space, time, bit and computational complexity analyzes of the proposed algorithms are performed. The proposed algorithms are applied on the TOSSIM simulation environment. It was also applied on a testbed consisting of IRIS nodes and Kobuki robots and compared with the other algorithms in the literature.