Achieving Sensing k-Coverage Using Hexagonal Tiling: Are We Done Yet?

Coverage is an essential task in the design of wireless sensor networks. We noticed that the problem of coverage in a two-dimensional (2D) space has similarity with the 2D tiling problem, which can be stated as follows: How can a 2D space be tiled by replicas of a set (or tiles)? This is a 2D instance of the second part of Hilbert's 18th problem: Is there a polyhedron that admits an anisohedral tiling only in three dimensions, i.e., tiles a 3D space, but does not admit an isohedral tiling? In this paper, we investigate the problem of 2D k-coverage, where each point in a 2D field is covered by at least k sensors, k >= 1. In our study, we found that it is helpful to identify a 2D convex tile that best approximates the sensors' sensing range. First, we propose some sensor placement strategies using a hexagonal tiling-based method, and compute the corresponding sensor density. Second, we suggest a more general one using irregular hexagon, denoted by IRH(r/n) where r stands for the radius of the sensors' sensing range, and n >= 2. We show that IRH(r/n) is a 2D tile, and derive the corresponding minimum sensor density. Third, we compute the relationship between the sensors' communication range R and r for each placement strategy. We corroborate our analysis with simulation results.