Distributed connected dominating set techniques for energy-efficient topology control in wireless sensor networks.

Despite the considerable research efforts devoted to extending the lifetime of wireless sensor networks (WSNs) by making them more energy efficient, there are still a number of unresolved issues. Among the possible solutions for improving their overall energy efficiency, topology control has significant potential. Distributed topology control is a difficult problem, and optimal solutions are not possible except for very simple topologies. Because of this, heuristic methods are used, but the solutions proposed in the research literature are usually tested with overly simplistic simulation models and consequently they fail to perform satisfactorily in real networks. The research project reported in this thesis proposes three new topology control methods that are tested on highly realistic simulation models calibrated with data collected on an experimental wireless sensor network. These models accurately handle interference effects, realistic transmission ranges and imperfect communication links. Additionally, the correctness of the proposed methods was verified using theoretical analysis. Two leading algorithms were used as benchmarks. Based on the outcomes of a thorough literature review and analysis of existing techniques, distributed connected dominating set (CDS) approach was selected as the starting point for the design of the proposed algorithms. The proposed algorithms are not only distributed but also use localized information for computing a CDS. Given that the CDS serves various tasks in a WSN, a fair load distribution strategy was adopted to prolong the network lifetime. This strategy takes into account the remaining energy levels at each node when choosing the eligible CDS nodes. The first topology control technique called the three-phase single initiator (TPSI) was developed to form a small CDS for medium and dense networks (i.e., in deployments when average node degree is relatively high) with minimal communication overhead, computational complexity and energy consumption. The simulation results demonstrate that the TPSI algorithm generates a small CDS for both medium and dense networks but not for sparse networks. These results also prove that the impact of network density on performance of an algorithm is significant and cannot be ignored. The second technique, single-phase single initiator (SPSI) on the other hand was proposed for applications that require fast convergence, and is best suited to WSN applications that have sparse topologies. The simulation results show that SPSI can generate a small CDS for sparse networks using low message overhead and energy consumption, and compute a CDS faster than the TPSI algorithm. The third one, the Two-phase multiple initiator (TPMI) algorithm adapts well to dynamic topology changes, thus it is suitable for applications that require frequent topology updates. Instead of relying on a single initiator to construct the CDS as in the TPSI and SPSI, the TPMI algorithm uses multiple initiators. The simulation results show that although the CDS size of TPMI is larger than the ones generated by TPSI or SPSI, it outperforms them in terms of energy consumption, network lifetime and convergence time in networks with rapidly changing topologies. Best suited algorithm for a particular installation can be selected manually, or by using some measurement techniques, the structure of a network can be probed to activate the optimal method automatically.