Robust and Efficient Coverage in Dense Sensor Deployment
Authors
Amotz Bar-Noy, Theodore Brown, Matthew P. Johnson, Thomas La Portaz, Deniz Saroz, Dinesh Vermay Chai, Wah Wuy
Abstract
Submitted paper: Authors: Amotz Bar-Noy, Theodore Brown, Matthew P. Johnson, Thomas La Porta, Deniz Sarıoz, Dinesh Verma, Chai Wah Wu Abstract: Positioning sensors to optimize certain coverage parameters is a fundamental problem in ad-hoc sensor networks. For disk-shaped sensing areas, the hexagon grid pattern is known to be optimally efficient: every point is covered at least once, which is impossible to do with fewer sensors. About 20.9% of the area is covered by two sensors, however, which may be considered a waste. Furthermore, any movement of a sensor from its designated grid position, due to placement error or obstacle avoidance, leaves some region uncovered. We explore how shrinking the grid can help to remedy both of these shortcomings. First, shrinking to obtain a denser hexagonal lattice allows all sensors to move about their intended positions independently while nonetheless guaranteeing full coverage. We study the shape of this wiggle area and prescribe the amount of shrinking required to support a given flexibility requirement. Second, sufficiently increasing the lattice density will yield k-coverage for k > 1. Superimposing k copies of the hexagon lattice will also provide k-coverage, but for robustness reasons, we prefer to maximize the minimum pairwise distance d_min between sensors. Moreover, we improve the efficiency by using k copies to provide k'-coverage, for k' as large as possible (e.g. k' = 12; k = 11). This is done by exploiting of the hexagon lattice’s double coverage areas. We give a series of examples, converging in the limit, in which the percentage of recovered area approaches the 20.9% maximum. We conclude by construing the shrinking factor as a budget to be divided between these two benefits.
Publication Date
October, 2007
Venue
ITA Technical Paper
Published To
None
Publication Type
ITA Technical paper
ITA Area
Project 8, Technical area 3
Download a copy of the paper here
covsecon08_0.pdf
Return to main page