Geometric aspects in wireless sensor networks

Abstract

In wireless sensor networks, geometric properties have many typical applications on optimization problems of energy and time performance. They can be used in controlling power of sensors and minimizing the time in gathering information. Therefore, discussion about geometry problems in wireless sensor networks is important and necessary. The thesis will discuss linear-coverage, data collection and guards of independent set problems using some special geometrical techniques. Coverage is one of the performance evaluation metrics of wireless sensor networks. Finding a min-energy cost coverage with adjustable ranges is one of the most fundamental tasks in wireless sensor networks. Solution of this problem requires geometric structures of networks. The other topic of the thesis is information transmission model. On this topic, we consider data collection and guards of independent sets problems. The fundamental task of data collection problem is finding the minimal time performance while the fundamental task of guards problem is finding the the maximum guard number of a given link under physical interference model. There are three parts in our thesis. In the first part, we study the coverage of a line segment with a set of wireless sensors with adjustable coverage ranges. Each coverage range of a sensor is an interval centered at that sensor whose length is decided by the power the sensor chooses. The objective is to find a range assignment with minimum cost. There are two variants of the optimization problem. In the discrete variant, each sensor can only choose from a finite set of powers while in the continuous variant, each sensor can choose power from a given interval. For the discrete variant of the problem, we present a polynomial-time exact algorithm. For the continuous variant of the problem, we develop constant-approximation algorithms when the cost for all sensors is proportional to rĸ for some constant ĸ ≥ 1, where r is the covering radius corresponding to the chosen power. Specifically, if ĸ = 1, we show that this problem is NP-hard and we give a simple 1.25-approximation algorithm and a fully polynomial-time approximation scheme (FPTAS); if ĸ > 1, we give a simple 2-approximation algorithm. In the second part, we study the time complexity of data collection in sensor networks. A simple mathematical model for sensor networks is defined. When networks are lines, multi-lines and trees, corresponding optimal schedules are provided. A lower bound of data collection time on general networks is also derived. Furthermore, we discuss the data collection problem where each node can transmit arbitrary hops per time slot. An optimal schedule is derived where each node can transmit 2 hops, when each node carries 0 or 1 data packet. We also prove the schedule is nearly optimal if each node can transmit k (k ≥ 2) hops when each node carries any number of data packets (with 1 time slot possible difference to the optimal result). In the last part, we consider k−Guard problem which is used in constructing approximation algorithms of maximum independent set of links under physical interference model. We proved that for path-loss exponent β ≥ 1, the upper bound of guard number of a given link is 8. As for the lower bound, an example with 6 guards can be constructed for β > 1 and an example with 7 guards can be constructed for β ≤ 1.

Date of Award	15 Feb 2013
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Minming LI (Supervisor)