On Energy Reserving Policies And Algorithms For Wireless Sensor Networks

Wireless sensor networks are multi-hop wireless networks, which usually consist of small-sized and low-power sensing devices with wireless communications capabilities. They efficiently combine the technologies in distributed information sensing, processing and wireless communications. Wireless sensor networks are characterised by data centric, application orientation and resource constraints, which lend themselves to countless applications and, at the same time, offer numerous challenges. Due to the stringent energy constraints to which the sensing nodes are subjected, energy efficiency is one the greatest challenges offered by wireless sensor networks, and poses direct impacts on their designs. This dissertation studies the energy reserving strategies and algorithms in wireless sensor networks, which focuses upon the design of the maximum network lifetime routing problems under single-point, multi-point and multi- point-multi-path aggregation routing strageties, and the optimal sink position selection problems under space tessellation strageties that aimed at minimizing the overall network energy consumption.In data aggregated wireless sensor networks, the key to prolong network lifetime is to utilize data aggregation to reduce the network load while balance the energy consumption for the sensors, which depends on the selection of data aggregation strategies. In chapter 2, the single-point aggregation routing strategy is studied. In this strategy, each sensor selects a single aggregator for data aggregation. An optimal aggregator selection algorithm based on the minimum energy cost tree is proposed, which combines the optimization power of genetic algorithm and gradient hill-climbing method. The energy consumption of the sensors is balanced, and the network lifetime is improved.Following chapter 2, chapter 3 relaxes the singularity on the selection of aggregators, and considers the multi-point aggregation routing strategy. In this strategy, sensors are allowed to distribute their raw data to every neighboring sensor for data aggregation. A raw data distribution algorithm based on minimum energy cost forest is presented, and linear programming method is used to optimize the allocation of raw data. Subgradient method is adopted to design the distributed algorithm, and the optimization of the raw data distribution is achieved by inter-node data exchange and computations.Chapter 4 further relaxes the single path constraint for the transmission of aggregated data from chapter 3, and studies the multi-point aggregation multi-path routing strategy. In the strategy, aggregated data are forward via multiple paths. A routing algorithm is designed based on linear programming method, the maximum network lifetime is obtained, and the possible loops in aggregated data flow are eliminated. A routing algorithm is designed to optimize network lifetime under aggregated data rate constraint, and the tradeoffs between network aggregated data rate and network lifetime are discussed.Chapter 5 studies the minimum energy sink position selection problems in wireless sensor networks. According to the piecewise smoothness of the overall network energy consumption objective function, a space tessellation strategy based on shortest path tree is proposed to divide and conquer the problem. In the strategy, the space is divided into tessellation cells, and each cell offers invariability for minimum energy routing. The structure of the tessellation cells and an algorithm for searching neighboring cells are discussed. An optimal sink selection algorithm for 1-D space is given; and three heuristic algorithms are presented for 2-D space, which are able to obtain sink positions with good performance.Finally, chapter 6 summarizes the dissertation, concludes the highlights in the studies, and presents the outlooks of directions and hotspots for future work.