  We propose a distributed Bayesian quickest change detection algorithm for
sensor networks, based on a random gossip inter-sensor communication structure.
Without a control or fusion center, each sensor executes its local change
detection procedure in a parallel and distributed fashion, interacting with its
neighbor sensors via random inter-sensor communications to propagate
information. By modeling the information propagation dynamics in the network as
a Markov process, two-layer large deviation analysis is presented to analyze
the performance of the proposed algorithm. The first-layer analysis shows that
the relation between the probability of false alarm and the conditional
averaged detection delay satisfies the large deviation principle, implying that
the probability of false alarm according to a rare event decays to zero at an
exponentially fast rate when the conditional averaged detection decay
increases, where the Kullback-Leibler information number is established as a
crucial factor. The second-layer analysis shows that the probability of the
rare event that not all observations are available at a sensor decays to zero
at an exponentially fast rate when the averaged number of communications
increases, where the large deviation upper and lower bounds for this rate are
also derived, based on which we show that the performance of the distributed
algorithm converges exponentially fast to that of the centralized one, by
proving that the defined distributed Kullback-Leibler information number
converges to the centralized Kullback-Leibler information number.
