An adaptive, energy-aware and distributed fault-tolerant topology-control algorithm for heterogeneous wireless sensor networks

Thesis Type: Doctorate

Institution Of The Thesis: Orta Doğu Teknik Üniversitesi, Faculty of Engineering, Department of Computer Engineering, Turkey

Approval Date: 2016


Consultant: ADNAN YAZICI


Wireless sensor networks (WSNs) are being used in numerous fields, such as battlefield surveillance, environmental monitoring and traffic control. They are typically composed of large numbers of tiny sensor nodes with limited resources. Because of their limitations and because of the environments they are being used, there are problems unique to WSNs. Due to the error-prone nature of wireless communication, especially in harsh environments, fault-tolerance emerges as an important property in WSNs. Also, because of the battery limitations, solutions to reduce energy consumption and prolong network lifetime are quite valuable. In this thesis, we propose two algorithms, namely Adaptive Disjoint Path Vector (ADPV) and Minimum Supernode Disjoint Path Vector (MSDPV), for heterogeneous WSNs. In this heterogeneous model, we have resource-rich supernodes as well as ordinary sensor nodes that are supposed to be connected to the supernodes. MSDPV algorithm considers the desired fault-tolerance degree and the positions of ordinary sensor nodes to determine optimal number of supernodes and their locations. It provides a novel optimization based on the well-known set-cover problem. ADPV is an adaptive, energy-aware and distributed fault-tolerant topology-control algorithm. Unlike the static alternative Disjoint Path Vector (DPV) algorithm, the focus of ADPV is to secure supernode connectivity in the presence of node failures, and ADPV achieves this goal by dynamically adjusting the sensor nodes' transmission powers. The ADPV algorithm involves two phases: a single initialization phase, which occurs at the beginning, and restoration phases, which are invoked each time the network's supernode connectivity is broken. Restoration phases utilize alternative routes that are computed at the initialization phase by the help of a novel optimization based on the well-known set-packing problem. Through extensive simulations, we demonstrate that ADPV is superior in preserving supernode connectivity. In particular, ADPV achieves this goal up to a failure of 95% of the sensor nodes; while the performance of DPV is limited to 5%. In turn, by our adaptive algorithm, we obtain a two-fold increase in supernode-connected lifetimes compared to DPV algorithm.