Distributed k-connectivity detection and restoration algorithms for wireless sensor and actor networks

In wireless sensor networks (WSNs), failures in some nodes may separate the network to disconnected parts. In k-connected networks, failures in any k-1 nodes do not destroy the network connectivity. In this thesis, we focused on two problems and proposed new algorithms for each one. The first problem is detecting the k value in WSNs. In this thesis, we proposed 3 new algorithms for efficient estimating of k value in WSNs and also proposed a deterministic algorithm for exact k detection. In the proposed CDSCUT algorithm, we defined new rules to find the critical nodes from connected dominating set information. In the second proposed DEV algorithm, the minimum vertex cut sets of WSNs are found using an evolutionary search based method. The proposed PACK algorithm estimates the k value of the network with high accuracy by coloring the edges between the nodes. Finally, in the last proposed DECK algorithm, the exact k value of the network always is detected correctly. The second problem that we focused on is movement based k-connectivity restoration. For this problem we defined 3 new movement models and proposed 3 central and 3 distributed algorithms. In the proposed central TAPU1, TAPU2 and PINC algorithms, the k-connectivity restoration for position bounded and position-edge bounded models can be done with optimum movements. In the proposed distributed L-PINC, LINAR and DKR algorithms, the k-connectivity restoration is done using local information at each node. The space, bit, time and computation complexities of all proposed algorithms have been analyzed. All proposed algorithms have been simulated in the TOSSIM simulator. Also the proposed algorithms have been implemented in the testbeds of IRIS nodes and Kobuki robots and compared with the existing algorithms in the literature.