The Theory of Trackability with Applications to Sensor Networks

In this article, we formalize the concept of tracking in a sensor network and develop a quantitative theory of trackability of weak models that investigates the rate of growth of the number of consistent tracks given a temporal sequence of observations made by the sensor network. The phenomenon being tracked is modelled by a nondeterministic finite automaton (a weak model) and the sensor network is modelled by an observer capable of detecting events related, typically ambiguously, to the states of the underlying automaton. Formally, an input string of symbols (the sensor network observations) that is presented to a nondeterministic finite automaton, M , (the weak model) deter- mines a set of state sequences (the tracks or hypotheses) that are capable of generating the input string. We study the growth of the size of this candidate set of tracks as a function of the length of the input string. One key result is that for a given automaton and sensor coverage, the worst-case rate of growth is either polynomial or exponential in the number of observations, indicating a kind of phase transition in tracking accuracy. These results have applications to various tracking prob- lems of recent interest involving tracking phenomena using noisy observations of hidden states.