Robust tracking of piecewise linear trajectories with binary sensor networks

We present a novel approach to the problem of tracking objects moving along smooth trajectories using a network of simple inexpensive binary sensors. Specifically, we consider object trajectories that can be well-approximated by piecewise linear curves and sensors that can only detect whether an object is in their sensing range. We start by considering objects moving along straight-line trajectories with an unknown speed and show that such objects can be tracked using the measurements of just three generically placed binary sensors whose sensing ranges intersect the trajectory. Next, we present an asymptotic analysis that shows that a trajectory consisting of a finite number of straight line segments can be recovered with high probability using an arbitrarily low spatial density of sensors in the limit when the area to be covered gets larger and larger. We also present efficient algorithms that effectively recover piecewise linear trajectories. Finally we present analysis and simulations to demonstrate the high tracking accuracy of our approach and its robustness to sensing errors.