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 X Y Z  
By number:  2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 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 worstcase 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 TR2005555,
August 2005.
Notify me about new tech reports.
To receive paper copy of a report, by mail, 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 noncommercial 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.
Technical reports collection maintained by David Kotz.