Increasing Sensor Measurements to Reduce Detection Complexity in Large-Scale Detection Applications
Rachlin,Yaron
Carnegie Mellon University
Negi,Rohit
Carnegie Mellon University
Khosla,Pradeep
Carnegie Mellon University
Dolan,John
Carnegie Mellon University
Balakrishnan,Narayanaswamy
Carnegie Mellon University
Large-scale detection problems, where the number of hypotheses is exponentially large, characterize
many important sensor network applications. In such applications, sensors whose output is
simultaneously affected by multiple target locations in the environment pose a significant
computational challenge. Conditioned on such sensor measurements, separate target locations become
dependent, requiring computationally expensive joint detection. Therefore there exists a tradeoff
between the computational complexity and accuracy of detection. In this paper we demonstrate that
this tradeoff can be altered by collecting additional sensor measurements, enabling algorithms that
are both accurate and computationally efficient. We draw the insight for this tradeoff from our
work on the sensing capacity of sensor networks, a quantity analogous to the channel capacity in
communications. To demonstrate this tradeoff, we apply sequential decoding algorithms to a
large-scale detection problem using a realistic infrared temperature sensor model and real
experimental data. We explore the tradeoff between the number of sensor measurements, accuracy, and
computational complexity. For a sufficient number of sensor measurements, we demonstrate that
sequential decoding algorithms have sharp empirical performance transitions, becoming both
computationally efficient and accurate. We provide extensive comparisons with belief propagation
and a simple heuristic algorithm. For a temperature sensing application, we empirically demonstrate
that given sufficient sensor measurements, belief propagation has exponential complexity and sequential
decoding has linear complexity in sensor field of view.
Despite this disparity in complexity, sequential decoding was significantly more accurate.
Yaron Rachlin completed his B.S. in electrical engineering, and B.S. in mathematics at Virginia Tech in 2000. He received an M.S. in 2002 in electrical and computer engineering at Carnegie Mellon University, and plans on defending his Ph.D. thesis at CMU this winter. His thesis proves information theoretic limits for sensor networks in large-scale detection applications. Based on this theoretical work, he has also developed fast detection algorithms, and used these algorithms in experiments to obtain obtain accurate sensing results using cheap, low resolution sensors. He is interested in speaking with potential employers.