Positioning disk-shaped sensors to optimize certain coverage parameters is a fundamental problem in ad hoc sensor networks. The hexagon lattice arrangement is known to be optimally efficient in the plane, even though 20.9% of the area is unnecessarily covered twice, however, the arrangement is very rigid—any movement of a sensor from its designated grid position (due to, e.g., placement error or obstacle avoidance) leaves some region uncovered, as would the failure of any one sensor. In this article, we consider how to arrange sensors in order to guarantee multiple coverage, that is, k -coverage for some value k > 1. A naive approach is to superimpose multiple hexagon lattices, but for robustness reasons, we may wish to space sensors evenly apart. We present two arrangement methods for k -coverage: (1) optimizing a Riesz energy function in order to evenly distribute nodes, and (2) simply shrinking the hexagon lattice and making it denser. The first method often approximates the second, and so we focus on the latter. We show that a density increase tantamount to k copies of the lattice can yield k ′-coverage, for k ′ > k (e.g., k = 11, k ′ = 12 and k = 21, k ′ = 24), by exploiting the double-coverage regions. Our examples' savings provably converge in the limit to the ≈ 20.9% maximum. We also provide analogous results for the square lattice and its ≈ 57% inefficiency (e.g., k = 3, k ′ = 4 and k =5, k ′ = 7) and show that for multi-coverage for some values of k ′, the square lattice can actually be more efficient than the hexagon lattice. We also explore other benefits of shrinking the lattice: Doing so allows all sensors to move about their intended positions independently while nonetheless guaranteeing full coverage and can also allow us to tolerate probabilistic sensor failure when providing 1-coverage or k -coverage. We conclude by construing the shrinking factor as a budget to be divided among these three benefits.

Positioning disk-shaped sensors to optimize certain coverage parameters is a fundamental problem in ad-hoc sensor networks. The hexagon grid lattice is known to be optimally efficient, but the 20.9% of the area covered by two sensors may be considered a waste. Furthermore, any movement of a sensor from its designated grid position or sensor failure, due to placement error or obstacle avoidance, leaves some region uncovered, as would the failure of any one sensor. We explore how shrinking the grid can help to remedy 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. Second, sufficiently increasing the lattice density will naturally yield k-coverage for k > 1. Moreover, we show that a density increase tantamount to fc copies of the lattice can yield k' -coverage, for kj> k (e.g. k = 11, kj= 12), through the exploitation of the double-coverage regions. Our examples' savings provably converge in the limit to the ap 20.9% maximum. We also provide analogous results for the square lattice and its ap 57% inefficiency, including k = 3, kj= 4, k = 5,kj= 7, indicating that for multi-coverage, the square lattice can actually be more efficient than the hexagon lattice. All these efficiency gains can be used to provide 1-coverage or fc-coverage even in the face of probabilistic sensor failure. We conclude by construing the shrinking factor as a budget to be divided among these three benefits.

An ad-hoc sensor network is composed of sensing devices which can measure or detect features of their environment, communicate with one other and possibly with other devices that perform data fusion. One of the problems motivated by ad-hoc sensor networks is to position sensors in order to maximize coverage, or equivalently to minimize the number of sensors required to cover a given area.