Search ETDs:
Sparse Deployment of Large Scale Wireless Networks for Mobile Targets
Zheng, Zizhan

2010, Doctor of Philosophy, Ohio State University, Computer Science and Engineering.

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
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 α 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.

Prasun Sinha (Advisor)
Ness Shroff (Committee Member)
Yusu Wang (Committee Member)

Recommended Citations

Hide/Show APA Citation

Zheng, Z. (2010). Sparse Deployment of Large Scale Wireless Networks for Mobile Targets. (Electronic Thesis or Dissertation). Retrieved from

Hide/Show MLA Citation

Zheng, Zizhan. "Sparse Deployment of Large Scale Wireless Networks for Mobile Targets." Electronic Thesis or Dissertation. Ohio State University, 2010. OhioLINK Electronic Theses and Dissertations Center. 19 Oct 2018.

Hide/Show Chicago Citation

Zheng, Zizhan "Sparse Deployment of Large Scale Wireless Networks for Mobile Targets." Electronic Thesis or Dissertation. Ohio State University, 2010.


osu1275444923.pdf (1.41 MB) View|Download