Dartmouth College Computer Science Technical Report series	CS home TR home TR search TR listserv
By author:	A B C D E F G H I J K L M N O P Q R S T U V W Y Z
By number:	2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Abstract: In this paper, we formalize the concept of tracking in a sensor network and develop a rigorous theory of {\em trackability} that investigates the rate of growth of the number of consistent tracks given a sequence of observations made by the sensor network. The phenomenon being tracked is modelled by a nondeterministic finite automaton and the sensor network is modelled by an observer capable of detecting events related, typically ambiguously, to the states of the underlying automaton.

More formally, an input string, $Z^t$, of $t+1$ symbols (the sensor network observations) that is presented to a nondeterministic finite automaton, $M$, (the model) determines a set, ${\cal H}_M(Z^t)$, of state sequences (the tracks or hypotheses) that are capable of generating the input string $Z^t$. We study the growth of the size of this set, $|{\cal H}_M(Z^t)|$, as a function of the length of the input string, $t+1$. Our main result is that for a given automaton and sensor coverage, the worst-case rate of growth is either polynomial or exponential in $t$, indicating a kind of phase transition in tracking accuracy.

The techniques we use include the Joint Spectral Radius, $\rho(\Sigma)$, of a finite set, $\Sigma$, of $(0,1)$-matrices derived from $M$. Specifically, we construct a set of matrices, $\Sigma$, corresponding to $M$ with the property that $\rho(\Sigma) \leq 1$ if and only if $|{\cal H}_M(Z^t)|$ grows polynomially in $t$. We also prove that for $(0,1)$-matrices, the decision problem $\rho(\Sigma)\leq 1$ is Turing decidable and, therefore, so is the problem of deciding whether worst case state sequence growth for a given automaton is polynomial or exponential. These results have applications in sensor networks, computer network security and autonomic computing as well as various tracking problems of recent interest involving detecting phenomena using noisy observations of hidden states.

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
   Valentino Crespi, George V. Cybenko, and Guofei Jiang, "The Theory of Trackability with Applications to Sensor Networks." Dartmouth Computer Science Technical Report TR2005-555, August 2005.

Want to be notified about new tech reports? Join our mailing list.

Want to search our technical reports?

Want us to mail you a paper copy of a report? Send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.