Data Collection in Wireless Sensor Networks

This thesis is principally concerned with effcient energy consumption in wireless sensor networks from two distinct aspects from a theoretical point of view. The thesis addresses the issue of reducing idle listening states in a restricted tree topology to minimise energy consumption by proposing an optimisation technique: the extra-bit technique. This thesis also focuses on showing lower bounds on the optimal schedule length, which are derived for some special cases of the tree, such as a single chain, balanced chains, imbalanced chains, three and four level k-ary trees and Rhizome trees. Then, we propose an algorithm which can exactly match the lower bound for a single chain, balanced chains and Rhizome trees individually and which is a few steps away from the optimal solution for imbalanced chains. Finally, we propose the use of two frequencies to further save energy and minimize latency. Recent research has shown that significant energy improvements can be achieved in WSNs by exploiting a mobile sink for data collection via single hop communications. A mobile sink approaches the transmission range of sensors to receive their data and deposit the data at the base station. The thesis, as a second problem, focuses on the design issues of an energy efficient restricted tour construction for sink mobility. We propose two different techniques. The first one is heuristic and uses a criterion based on maximum coverage and minimum energy consumption called the "max-ratio". Although its time complexity is polynomial, this heuristic algorithm cannot always produce a good solution. As a result, we propose the sec- ond algorithm. Despite the time complexity of the second algorithm being pseudo polynomial, the optimal solution can be found if one exists. For each algorithm men- tioned, two scenarios are taken into account with regard to the transmission. In the first scenario, one assumes that there is no upper bound on the transmission range while in the second setting the nodes can adjust their transmission range between 0 and the maximum range. The algorithms have been implemented and simulated in Matlab.