Grid coverage for surveillance and target location in distributed sensor networks

TLDR

The sensor field is modeled as a two‑ or three‑dimensional grid of points, with target location defined as finding a target at a grid point at any instant. The study introduces novel grid coverage strategies, including an ILP‑based approach to minimize sensor cost for full field coverage in distributed sensor networks. The authors formulate an ILP model solved with a public‑domain solver, employ a divide‑and‑conquer technique for large instances, and use identifying codes with coding‑theoretic bounds to determine efficient sensor placement. The results demonstrate that grid‑based sensor placement yields asymptotically complete, unambiguous localization of multiple targets.

Abstract

We present novel grid coverage strategies for effective surveillance and target location in distributed sensor networks. We represent the sensor field as a grid (two or three-dimensional) of points (coordinates) and use the term target location to refer to the problem of locating a target at a grid point at any instant in time. We first present an integer linear programming (ILP) solution for minimizing the cost of sensors for complete coverage of the sensor field. We solve the ILP model using a representative public-domain solver and present a divide-and-conquer approach for solving large problem instances. We then use the framework of identifying codes to determine sensor placement for unique target location, We provide coding-theoretic bounds on the number of sensors and present methods for determining their placement in the sensor field. We also show that grid-based sensor placement for single targets provides asymptotically complete (unambiguous) location of multiple targets in the grid.