Abstract
Wireless sensor network (WSN) has been an active research area in recent years. One reason is because the wireless sensors can be deployed in the target area easily without requiring costly wiring. However, this does not imply that the sensors can be deployed at will without considering issues such as cost, application requirements, and system qualities. In fact, different applications require different deployment strategies to fulfill their respective needs. In this thesis, we consider three different kinds of applications and develop efficient deployment algorithms to meet their respective optimization goals. We first study WSN tracking applications, in which the behavior of the targets is known and can be modeled. While previous work on sensor deployment has considered only sensor and environment models, we show that considering also target models can greatly reduce the deployment cost. We use robot navigation as a case study, in which a WSN is deployed to provide external location references to correct the robot's configuration errors. The goal is to find the minimum number of sensors to provide the required bound on configuration errors. We show that this minimization problem is NP-hard and a number of heuristics are then proposed. The presented algorithms are evaluated through extensive simulations. We next consider problems in which the sensors can only be deployed at the periphery of the target area to be monitored. The question is what is the minimum number of sensors to be deployed at the periphery to cover as much as possible the activities inside the target area. As a case study, we consider the problem of deploying base stations at the periphery to collect information from mobile sensors moving inside the target area. We first formulate the periphery deployment problem and then analyze its performance bounds in terms of coverage percentage under both ideal and practical deployments. Next, we propose a deployment procedure that consists of initial construction and refinement for solving the periphery deployment problem with polynomial time. Proposed algorithms are evaluated through extensive simulations and a watercourse monitoring system for debris flow. Finally, we study the problem that deploys wireless sensors at fixed locations. The sensors have to transmit their sensed data back to the sink through multihop communications, but they can only carry battery packs of a fixed capacity. The question is, given a target system lifetime, what is the minimum number of battery packs needed at each location so that the target lifetime can be satisfied. The factor that can be controlled to achieve the above goal is the routing path of each sample data to the sink. We formulate the problem as a constrained multiple deployment problem. We first derive the optimal solution using integer linear programming and a lower bound of the deployment cost. A heuristic is then developed that solves the problem in polynomial time. The heuristic consists of (1) a battery-aware routing algorithm that gives an initial solution by selecting routing paths based on the battery usage, and (2) a refinement procedure to improve the initial solution by adjusting traffic to reduce the number of battery packs required. We performed extensive simulations to evaluate the proposed algorithms in terms of the deployment cost and residual energy. The results show that our algorithm generates deployments close to the lower bound.