Abstract
Coverage problem is one of the fundamental problems in wireless sensor networks since it refiects the sensing quality of a sensor network. Various versions of this problem have been studied, such as object, area, and barrier coverage problems. In this thesis, we study a novel coverage problem in a wireless sensor network, called (k, ω)-angle object coverage problem. Each sensor can only cover a limited angle and range, but can freely rotate to any direction to cover a particular angle. Given a set of sensors and a set of objects, our goal is to use the least number of sensors to (k, ω)-angle-cover the largest number of objects such that each object is covered by at least k sensors satisfying an angle constraint ω. In this thesis, we propose an integer linear programming (ILP) approach to finding the optimal solution. To reduce the computation complexity of solving ILP, we present a divide-and-conquer near-optimal algorithm, which guarantees the total number of used sensors does not exceed four times of the optimal solution in worst case. The numerical results show that our algorithms has better facial covering rate of objects than k-cover strategy using directional sensors without angle constraints. And the results also show that the proposed algorithms can be effective in maximizing the ratio of angle-covered objects even if the angle constraint becomes strict.