Tree-based object tracking without mobility statistics in wireless sensor networks

Object tracking in wireless sensor networks is to track mobile objects by scattered sensors. These sensors are typically organized into a tree to deliver report messages upon detecting object's move. Existing tree construction algorithms all require a mobility profile that characterizes the movement statistics of the target object. Mobility profiles are generally obtained based on historical running traces. The contribution of this work is twofold. We first show that the problem of finding an optimal message report tree that requires the least amount of report messages is NP-hard. We then propose analytic estimates of mobility profiles based on Markov-chain model. This profiling replaces an otherwise experimental process that generates and analyzes running traces. Simulation results show that the analytic profiling works well and can replace costly statistical profiling without noticeable performance degradation.