Deploying wireless networks at large scale is challenging. Despite various effort made in the design of coverage schemes and deployment algorithms with static targets in mind, how to deploy a wireless network to achieve a desired quality of service for mobile targets moving in a large region without incurring prohibitive cost largely remains open. To address this issue, this dissertation proposes Sparse Coverage, a deployment scheme that provides guaranteed service to mobile targets while trading off service quality with cost in a deterministic way.;The first part of this dissertation discusses two sparse coverage models for deploying WiFi access points (APs) along a city-wide road network to provide data service to mobile vehicles. The first model, called Alpha Coverage, ensures that a vehicle moving through a path of length alpha is guaranteed to have a contact with some AP. This is the first partial coverage model (in contrast to the more expensive full coverage model) that provides a performance guarantee to disconnection-tolerant mobile users. We show that under this general definition, even to verify whether a given deployment provides Alpha Coverage is co-NPC. Thus, we propose two practical metrics as approximations, and design efficient approximation algorithms for each of them. The concept of Alpha Coverage is then extended by taking connectivity into account. To characterize the performance of a roadside WiFi network more accurately, we propose the second sparse coverage model, called Contact Opportunity, which measures the fraction of distance or time that a mobile user is in contact with some AP. We present an efficient deployment method that maximizes the worst-case contact opportunity under a budget constraint by exploiting submodular optimization techniques. We further extend this notion to the more intuitive metric -- average throughput -- by taking various uncertainties involved in the system into account.;The second part of this dissertation studies sparse deployment techniques for placing sensor nodes in a large 2-d region for tracking movements. We propose a sparse coverage model called Trap Coverage, which provides a bound on the largest gap that a mobile target, e.g., an intruder or a dynamic event, is missed by any sensor node. In contrast to the current probabilistic partial coverage models, this is the first 2-d coverage model that can trade off the quality of tracking with network lifetime in a deterministic way. For an arbitrarily deployed sensor network, we propose efficient algorithms for determining the level of Trap Coverage even if the sensing regions have non-convex or uncertain boundaries. We then discuss a roadmap assisted geographic routing protocol to support efficient pairwise routing in large sensor networks with holes, which embodies a novel hole approximation technique and makes desired tradeoff between route-stretch and control overhead.
展开▼
