Asymptotically Optimal Quickest Change Detection in Distributed Sensor Systems

Abstract

In the standard formulation of the quickest change-point detection problem, a sequence of observations, whose distribution changes at some unknown point in time, is available to a decision maker, and the goal is to detect this change as quickly as possible, subject to false alarm constraints. In this paper, we study the quickest change detection problem in the setting where the information available for decision-making is distributed across a set of geographically separated sensors, and only a compressed version of observations in sensors may be used for final decision-making due to communication bandwidth constraints. We consider the minimax, uniform, and Bayesian versions of the optimization problem, and we present asymptotically optimal decentralized quickest change detection procedures for two scenarios. In the first scenario, the sensors send quantized versions of their observations to a fusion center where the change detection is performed based on all the sensor messages. In the second scenario, the sensors perform local change detection and send their final decisions to the fusion center for combining. We show that our decentralized procedures for the latter scenario have the same first-order asymptotic performance as the corresponding centralized procedures that have access to all of the sensor observations. We also present simulation results for examples involving Gaussian and Poisson observations. These examples show that although the procedures with local decisions are globally asymptotically optimal as the false alarm rate (or probability) goes to zero, they perform worse than the corresponding decentralized procedures with binary quantization at the sensors, unless the false alarm rate (or probability) is unreasonably small.

Keywords:

• Change-point detection
• CUSUM procedure
• Distributed decision-making
• Optimal fusion
• Shiryaev procedure
• Shiryaev–Roberts procedure

Subject Classification:

• 62L10
• 62L15
• 60G40
• 62F12
• 62F05

ACKNOWLEDGMENTS

The work of Alexander Tartakovsky was supported in part by the U.S. Office of Naval Research grant N00014-06-1-0110 and the U.S. Army Research Office MURI grant W911NF-06-1-0094 at the University of Southern California and by the U.S. ARMY SBIR contract W911QX-04-C-0001 at ADSANTEC. The work of Venugopal Veeravalli was supported in part by the U.S. Army Research Office MURI grant W911NF-06-1-0094, through a subcontract from Brown University at the University of Illinois, and the U.S. National Science Foundation grant CCF-0049089 at the University of Illinois. The authors would like to thank Hongjoong Kim for the help in MC simulations in Example 1.

Notes

¹Note that Figure 4 shows the natural logarithm of PFA.

Recommended by Wolfgang Schmid