Distributed Detection over Noisy Networks: Large Deviations Analysis

I Introduction

Consider a generic network of sensors that sense the environment to detect an event of interest. In centralized detection, the measurements of all sensors at all times $k$ are available at the detector (fusion center.) Under appropriate conditions, the probability of error $P^{e}(k)$ of the centralized minimum probability of error detector decays in $k$ at an exponential rate, $P^{e}(k)\sim e^{-C\,k}$, where $C$ is the (centralized) Chernoff information. We research in this paper the equivalent question of exponential rate of decay of the probability of error $P^{e}$ for distributed detection at each local sensor. We consider this question when the (local) communications among sensors is through noisy links.

To be specific, we study consensus+innovations distributed algorithms like for example the LMS and RLS adaptive algorithms in , the detectors in , or the estimators in . In consensus+innovations distributed algorithms, at time $k$, each sensor updates its state 1) by a weighted average of the states of its neighbors (consensus); and 2) by incorporating its local measurement (innovations):

Consensus+innovations detectors like in (1) are distributed, stochastic approximation type algorithms, but particular algorithms make different choices of the time-decaying weight sequences $\gamma_{k}^{i}$, $i=1,2$, in (1) by which sensors weigh the consensus (their neighbors’ messages) and the innovations (their own measurements) terms at each time $k$: set $\gamma_{k}^{i}=\mu$, $i=1,2$; in they vanish at the same rate; while consider single but also mixed scale algorithms where these weight sequences vanish at different rates. We will show that key to achieving exponential decay of the distributed detector $P^{e}$ at all sensors is the suitable design of the weights $\gamma_{k}^{i}$, $i=1,2$, in (1).

This paper addresses three natural questions:

SSNR versus CSNR–how much communications noise can distributed detection sustain: What is the highest communications noise level, i.e., lowest CSNR, for which cooperation helps? Let sensor $i$ be the best sensor among all locally detectable sensors and assume that, without cooperation, its $P^{e}\sim e^{-k\,C_{i}}$. Can cooperation over noisy links make the worst sensor under communication better than $i$–the best one without cooperation? We explicitly find a threshold on the ratio CSNR/SSNR above which communication pays off in the latter sense; the threshold is a function of the network algebraic connectivity.

Brief comment on the literature. Consensus+innovations distributed algorithms as in (1) or in , that interleave consensus and innovations at the same time instant contrast with decentralized parallel fusion architectures, e.g., , where all sensors communicate with a fusion sensor or with consensus-based detection schemes (no fusion sensor,) for example, , where sensors in the network, initially, 1) collect a single snapshot of measurements, and, subsequently, 2) run the consensus algorithm to fuse their decision rules.

We consider noisy communications among sensors. Communications imperfections in consensus-based detection in sensor networks are usually modeled via intermittent link failures and additive noise . For consensus+innovations distributed algorithms, the LMS and RLS adaptive algorithms in and the distributed change detection algorithm in do not consider link failures nor additive noise. References consider link failures but no additive communication noise. Reference considers deterministically time varying networks. Reference is concerned with estimation and considers a very general model that includes sensor failures, link failures, and various degrees of either quantized or noisy communications. To the best of our knowledge and within the consensus+innovations detectors, only reference and now this paper consider additive noise in the communications among sensors, but no link failures. We highlight the main differences between our work and .

Reference proposes a consensus+innovations distributed detector that it refers to as $\mathcal{MD}$. Algorithm $\mathcal{MD}$ assumes very general data distributions: temporally independent, spatially correlated sensing noise and temporally independent, spatially correlated additive communication noise, both with generic distributions with finite second moments. Under global detectability and connectedness assumptions, shows that $\mathcal{MD}$’s error probability $P^{e}$ decays to zero at all nodes $i$, but only shows exponential decay rate of the error probability for a modified, $\mathcal{SD}$ scheme, when the noises are Gaussian, and all sensors are locally detectable, with equal Chernoff informations $C_{i}>0$Sensor $i$ can detect the event individually (is locally detectable) if and only if $C_{i}>0$; see ahead Definition 1 and Fact 2. (, Corollary 12.) In fact, as we show in this paper, Appendix A-B, the probability of error $P^{e}$ for $\mathcal{MD}$ is not exponential; it is instead sub exponentialWe show in Appendix A-B that $\max_{i=1,...,N}P^{e}_{i}(k)$–the worst error error probability at time $k$ among all $N$ sensors, is at least $e^{-ck^{\tau}}$, where $\tau\in(0.5,1)$ and $c>0$., i.e., the rate is strictly slower than exponential, when the $C_{i}$’s are not equal, with possibly some $C_{i}$’s equal to zero. The subexponential rate of the $\mathcal{MD}$ and $\mathcal{SD}$ algorithms (with unequal $C_{i}$’s) is due to the decay rates assumed by these algorithms for the stochastic approximation weight sequences. In contrast, in the consensus+innovations algorithm that we propose, we craft carefully these weight sequences; this enables us to show for the Gaussian problem and under global detectability and connectedness that our distributed detector achieves exponential decay rate for $P^{e}$ at every sensor, regardless of the equal or unequal $C_{i}$’s, where some can possibly be zero. Further, we optimize the weight sequences so that sensors achieve the maximum payoff from their (noisy) cooperation with other sensors. We derive our results on the $P^{e}$ under Gaussian assumptions on the sensing and communication noises, but our results extend, to a certain degree, to the non-Gaussian (time-independent and space-independent) zero mean sensing noise with finite second moment and to the non-Gaussian (time-independent and space-correlated) zero mean communication noise with finite second moment.

The Gaussian assumptions allow us to completely characterize the rate of decay of the error probability solely on the basis of the first two moments (mean and variance) of the node’s decision variable or state, say $x_{i}(k)$. With non-Gaussian noises, the first two moments no longer suffice to determine the rate of decay of the error probability $P^{e}$, but they still represent a good measure of detection performance. In this case, we can still show that the (local) detector signal-to noise ratio ${\textbf{DSNR}}_{i}(k)$ at each sensor $i$ that we define by the ratio of the square of the mean over the variance of the sensor $i$ state $x_{i}(k)$ grows at the same rate $\sim k$, as for the optimal centralized detector.

We relate now this paper to our prior work on distributed detection, . While study the effect of link failures on detection performance, this paper addresses additive communication noise in the links among sensors. Our analysis here reveals that communication noise has an effect that is qualitatively different from that of link failures; with link failures, the more communication that is actually achieved among sensors the better the error performance, since when communication does happen sensors receive their neighbors decision variables unencumbered by noise. On the other hand, communication noise leads to a clear tradeoff between communication noise and information flow (degree at which consensus helps), with a cooperation payoff–threshold on the CSNR. To show these results, the analysis we develop here is very different from the analysis we advanced in . In , we consider independent identically distributed (i.i.d.) averaging matrices $W(k)$ (and hence the distribution of the $W(k)$ is time invariant,) and no communication noise. In contrast, this paper considers time-decaying stochastic approximation weights (and hence, time varying weight matrices $W(k)$) and additive communication noise; these additional challenges do not allow for our tools in and demand new analysis. A final comment to distinguish our methods here with those in . Reference uses standard stochastic approximation techniques that yield the exact asymptotic covariance of the decision variable vector (when the local Chernoff informations are equal) the asymptotic covariance is given by a difficult to interpret matrix integration formula. In contrast, we do not pursue the exact asymptotic covariance of the decision variable, but get, instead, tight, simple, easy to interpret lower and upper bounds by exploiting the natural separability between the communication noise and the information flow (averaging) effects.

Paper organization. The next paragraph introduces notation. Section II describes the problem model and presents our distributed detector. Section III states our modeling assumptions and gives preliminary analysis. Section IV presents our main results on the asymptotic performance of our distributed detector. Section V proves our main results. Section VI presents extensions to the non-Gaussian case. Finally, section VII concludes the paper. Appendices A–B provide remaining proofs.

We also make use of the standard $\Omega$ and $O$ notations: $f(k)=\Omega\left(g(k)\right)$ stands for existence of a $K>0$ such that $f(k)\geq cg(k)$, for some $c>0$, for all $k\geq K$; and $f(k)=O\left(g(k)\right)$ means existence of $K>0$ such that $f(k)\leq cg(k)$, for some $c>0$, for all $k\geq K$.

II Binary Hypotheses Testing: Centralized and Distributed

This section presents the network model and our consensus+innovations distributed detector whose performance we analyze in section IV. The current section also considers the centralized and isolated sensor detectors for benchmarking our consensus+innovations detector and defines certain relevant signal-to-noise ratios.

II-B Isolated sensor detector and centralized detector

We consider the known signal in Gaussian noise binary hypotheses test between $H_{1}$ and $H_{0}$. At time $k$, sensor $i$ measures the (scalar) $y_{i}(k)$:

with prior probabilities $0<P(H_{1})=1-P(H_{0})<1$. Here $[m_{l}]_{i}$ is a constant known signal and the sensing noise $\{\zeta_{i}(k)\}$ is a zero mean (z.m.) independent identically distributed (i.i.d.) Gaussian sequence. Introduce the vector notation

The isolated sensor $i$ detector thresholds $\mathcal{D}_{i}(k)$ against a threshold $\tau_{i}(k)$.

Centralized detector. The centralized log-likelihood ratio (cLLR) for the single vector measurement $y(k)$ (all sensors measurements are available at the fusion center) is:

The optimal centralized detector thresholds the cLLR against $\tau(k)$.For future reference we introduce:

Conditioned on $H_{l}$, $l=0,1$, the sequence $\eta(k)$ is i.i.d. Gaussian with mean $m_{\eta}^{(l)}$ and covariance $S_{\eta}$:

With (7), we rewrite the cLLR $L(k)$ at time $k$ as the separable sum of $\eta_{i}(k)$’s:

II-C Distributed detector: Consensus+Innovations

We now consider the consensus+innovations distributed detector, see (1), with structure like the structure of the distributed estimator in or of the $\mathcal{MD}$ distributed detector in . The key to ours is our choice of the consensus weight sequence $\gamma_{k}^{1}$ that we show to be the optimal one and will lead to exponential decay rate of the probability of error of the consensus+innovations distributed detector, which is not the case in general for the $\mathcal{MD}$ distributed detector in as we show in Appendix A-B.

To set-up the distributed detector, let the decision variable or the current state of sensor $i$ at time $k$ be $x_{i}(k)$. Due to the communication noise, when sensor $j$ transmits to sensor $i$ its state, sensor $i$ receives a noisy version:

where $\nu_{ij}(k)$ is the communications noise. Note that (10) is a high level model, i.e., we do not model here the physical communication channel, but rather we model the estimation errors at the receiver.

We propose as distributed detector the single time scale, stochastic approximation, consensus+innovations algorithm where each sensor updates its decision variable two-fold: 1) by consensus, i.e., averaging its decision variable with the decision variables of its immediate neighbors—the sensors with which it communicates; and 2) by innovation, i.e., by incorporating the innovation $\eta_{i}(k)$ in (7), after sensing its local observation. The consensus+innovation update of $x_{i}(k)$ is given by:

We write (12) in matrix form. The communication noise at sensor $i$ from all its neighbors, and the corresponding vector quantity for all sensors, are (see (12))

where $\eta(k)$ is given in (6). When the noises are Gaussian, since (12) and (14) are linear, the decision variables $x_{i}(k)$ and $x(k)$ are Gaussian. For the vector $x(k)$ of the decision variables $x_{i}(k)$, the vector $\mu(k)$ of the means $\mu_{i}(k)$, $1\leq i\leq N$ under $H_{1}$ (respectively, $H_{0}$) and the covariance $S_{\mu}(k)$ under either hypotheses are:

We let the diagonal elements of $S_{\mu}(k)$ be

Weight sequences $\gamma_{k}^{1}$ and $\gamma_{k}^{2}$. Comparing (11) with (1), the consensus and innovations weights are

Due to the communication noise, the $\left\{\alpha_{k}\right\}$ have to be diminishing, i.e., $\alpha_{k}\rightarrow 0$, as pointed out in . The design of the $\left\{\alpha_{k}\right\}$ will be key to the distributed detector achieving exponential decay rate of the error probability: a small and fast-decaying $\alpha_{k}$ injects low communication noise in the decision variable $x_{i}(k)$, but limits the information flow among neighbors (insufficient averaging). We will show that, for appropriately designed constants $a,b_{0}>0$,

balances these two opposing effects—communication noise and information flow. As detailed in Section IV, a large $b_{0}$ yields larger noise injection but also greater inter-sensor averaging.

We compare the consensus+innovations distributed detector (12) with the distributed detectors in and . The detector in , referred to as running consensus, uses constant, non-decaying weights $\alpha_{k}=\alpha$, which is not suitable for noisy communication. To account for communication noise, references propose mixed time scale, stochastic approximation type algorithms. In particular, for detection, proposes the $\mathcal{MD}$ algorithm for the generic case of different signal-to-noise ratios (SNR) at different sensors and the single time scale $\mathcal{SD}$ algorithm when the SNR is the same at all sensors. The algorithm $\mathcal{MD}$ uses the weight sequences (see eqn. (13), )

The algorithm $\mathcal{SD}$ uses the same weights for both consensus and innovations (see eqn. (53) in ) equal to (17) and (18) with $\tau=1$. In contrast with , we propose the single time scale algorithm (12) regardless if the local SNR are mutually different or not. A major contribution here with respect to is to show that the single time scale algorithm (12) yields better asymptotic detection performance than the mixed time scale algorithm $\mathcal{MD}$. Our algorithm (12) and $\mathcal{SD}$ are both single time scale. The main differences between (12) and $\mathcal{SD}$ are that algorithm (12): 1) incorporates $a$ in (II-C); and 2) optimizes the parameter $b_{0}$. We will show that (12) exhibits under appropriate structural conditions exponential rate of decay of the probability of error at every sensor, while $\mathcal{MD}$ in is sub exponential; $\mathcal{SD}$ is shown to be exponential, but only when the sensors are identical, i.e., all operate under the same SNR.

II-D Signal-to-noise ratios (SNR)

We define, for future reference, the following relevant SNRs.

3. Communication SNR is a quantity that accounts for the communication noise and plays a role only with the distributed detector. We define the communication SNR (per sensor) by:

Remark. We give a hint why ${\bf CSNR}$ is defined as (21) and why it plays a significant role in assessing distributed detection performance. With our distributed detector, sensors communicate their local decision variables $x_{i}(k)$; $x_{i}(k)$ is a local approximation of the (scaled) centralized decision variable $\frac{1}{N}\mathcal{D}(k)$ (see (5)). The mean of $x_{i}(k)$ under $H_{1}$, for large $k$, is close to the mean of $\frac{1}{N}\mathcal{D}(k)$, equal to $\frac{1}{2N}{\bf SSNR}$ (as will be shown); the variance of $x_{i}(k)$, as will be shown, vanishes at rate $1/k$. Hence, ${{\bf CSNR}}$ describes how well, in a sense, the signal $x_{i}(k)$ competes against the noise $v_{i}(k)$ in communication, for large $k$. We define also the communication gain as the ratio of the communication SNR and the average (across sensors) sensing SNRNote that CSNR and SSNR are not independent quantities here; larger SSNR means larger CSNR.:

For future reference, we introduce here the following two constants that we will need when assessing distributed detection performance:

III Modeling assumptions and Preliminary results

In this Section, we establish our underlying assumptions and present the asymptotic performance of the isolated sensor and centralized detectors. These will be a prelude to our main results on the asymptotic performance of the consensus+innovations detector in (12) given in Section IV and proven in Section V and Appendix A-A.

As mentioned in Section II, the noises are zero mean Gaussian spatially correlated but temporally independent sequences. In Section VI, we will consider the case where the noises are not Gaussian.

The sensing and the communication noises $\zeta_{i}(k)$ and $\nu_{ij}(k)$ are zero mean, Gaussian spatially correlated and temporally independent noises, and independent of each other:

where the vector $v(k)$ is defined in (13) and $S_{\zeta}$ and $S_{v}$ are assumed to be positive definite.

In distributed processing, the ability for the sensors or agents to cooperate is fundamental; this is captured by the connectivity of the network.

The network $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is connected.

As it is well known, a necessary and sufficient condition for connectedness is $\lambda_{2}(\mathcal{L})>0,$ i.e., the algebraic connectivity of the network is strictly positive. The next assumption is on the weight sequence $\left\{\alpha_{k}\right\}$.

The weight sequence $\left\{\alpha_{k}\right\}$ is:

where the constants $a$ and $b_{0}$ satisfy

The role of these conditions will become clear when we state our main result, Theorem 3, in Section IV. Recall the sensing SNRs in (19). We make the following assumption on $\bf SSNR$.

Note that Assumption 4 is equivalent to having different mean vectors, $m_{1}\neq m_{0}$. To obtain certain specialized results, we will assume a stronger assumption than Assumption 4.

$\mathbf{SSNR}_{i}=\mathbf{SSNR}_{j}>0,\,\,\,\forall i\neq j.$

III-B Asymptotic performance and Chernoff information

For Gaussian decision variables like for the three detectors (isolated sensor, centralized, and consensus+innovations distributed), and equal prior probabilities, the probability of error $P^{e}(k)$ is given by

To determine the exponential decay rate of the error probability, we recall the bounds

The Chernoff information for the isolated and the centralized optimal detectors are then:

Eqns. (31) and (32) justify the following definition of the global and local detectability, after which we relate global and local detectability to sensing (global and local) SNRs by a simple, but important fact.

The network $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is globally detectable if and only if ${\bf SSNR}>0$. The sensor $i\in\mathcal{V}$ is locally detectable if and only if ${\bf SSNR}_{i}>0$.

IV Consensus+Innovations distributed detection: Performance analysis

Subsection IV-A studies the exponential decay of our consensus+innovations detector in (12), subsection IV-B addresses the optimality of the weight sequence $\{\alpha_{k}\}$, and subsection IV-C addresses the potential payoff of distributed detection arising from noisy cooperation among sensors.

The next Theorem establishes under reasonable conditions that the probability of error at every sensor of the consensus+innovations distributed detector in (12) decays exponentially fast. Recall the definitions of SSNR and $\bf{G_{c}}$ in (19) and (22), and the constants $c_{\mu}$ and $c_{\sigma}$ in (23).

Consider the consensus+innovations distributed detector in (12) under the Assumptions 1, 2, 3, and 4. Then:

The moments $\mu(k)$, $\mu_{i}(k)$, and $\sigma_{i}^{2}(k)$ satisfy:

2. Effect of ${{\bf G_{c}}}$. The bound on the rhs of (36) shows quantitatively that higher ${{\bf G_{c}}}$ leads to better detection, confirming the qualitative discussion in the Remark below (21).

3. Effect of the network connectivity $\lambda_{2}(\mathcal{L})$. Theorem 3 shows that the network connectivity plays a role in the detection performance through the algebraic connectivity $\lambda_{2}(\mathcal{L})$. Larger values of $\lambda_{2}(\mathcal{L})$, which allow for faster averaging, increase the bound (36) yielding faster decay rate for the error probability.

4. Tradeoff: Communication noise vs. information flow. With optimal centralized detection (that corresponds to a fully connected network and no additive communication noise) we have that, for all $i$, $P^{e}_{i}(k)\equiv P^{e}(k)$, and: $\lim_{k\rightarrow\infty}-\frac{1}{k}\log P^{e}_{i}(k)=\frac{1}{8}{\bf SSNR}.$ Then, from (36), all the three terms:

decrease the bound and so they quantify the decrease in performance of the distributed detector with respect to the centralized detector. This decrease comes from two effects: 1) communication noise; and 2) insufficient information flow.

From (37)–(39), we can see how the parameter $b_{0}$ affects in opposing ways these two effects: The terms (37) and (38) relate to the information flow, while the term (39) is due to communication noise. We see that the net effect of increasing $b_{0}$ is to increase the effective algebraic connectivity ($b_{0}$ multiplies $\lambda_{2}(\mathcal{L})$), increasing (37) and (38); on the other hand, it reduces CSNR as seen from (39).

The weight choice $\alpha_{k}$ in (II-C) optimally balances these two effects if we tune the parameter $b_{0}$ to maximize the right hand side in (36). This is a scalar optimization problem in $b_{0}$ and can be easily numerically performed. Lemma 6 find the optimal $b_{0}$ in closed form for a simplified case.

5. Tradeoff: Bias-variance. Theorem 3 reveals a certain bias-variance tradeoff. Ideally, we would like the bias-free decision variables:

where $1$ is the vector of ones; i.e., all sensors should have as asymptotic decision variable the asymptotic centralized decision variable. That is, we want the mean of the decision variable at each sensor to converge to the expected value of the centralized decision variable $\mathcal{D}(k)$ (divided by $1/N$.) Our algorithm (12) introduces a bias (see (33) and (34)), but, on the other hand, it decreases the variance at the optimal rate $1/k$. In contrast, $\mathcal{MD}$ in does not have the bias, but it decreases the variance at a slower rate. Compared to $\mathcal{MD}$, our algorithm (12) better resolves the bias-variance tradeoff in terms of the detection performance; algorithm (12) decays the error probability exponentially, while $\mathcal{MD}$ decays it sub exponentially. We now consider a special case where all sensors are identical, or, better said, they operate under the same $\textrm{SSNR}_{i}$, i.e., Assumption 5 holds. Theorem 3 takes a simplified form, where $\mu_{\infty}$ becomes bias free, as in (40). Further, $c_{\mu}=c_{\sigma}=1$ and second condition in (24) becomes $b_{0}>0$; it can also be shown (details omitted) that the factor $3$ in (38) reduces to $1$. The simplified Theorem 3 follows.

Let Assumptions 1 through 3 and 5 hold. Then, the exponential decay rate of the error probability at each sensor $i$ satisfies:

Order-optimality. We consider the role of the weight sequence (II-C), in particular, we show the optimality of the rate $1/k$. To this end, we consider the distributed detector (12) but modify the weight sequence; we refer to the modified sequence as $\beta_{k}$. We find an upper bound on the decay rate of the error probability when the weight sequence is re-set to $\alpha_{k}$.

Let Assumptions 1—3 and 5 hold. Suppose that the weight choice $\alpha_{k}$ in (II-C) is replaced by:

1. Order-optimality of $\alpha_{k}$. Theorem 5 says that the choice $\alpha_{k}$ in (II-C) is the optimal weight choice in the family of choices $\beta_{k}=\frac{b_{0}}{(a+k^{\tau})}$, $a,b_{0}>0,$ parametrized by $\tau\geq 0$. If $\beta_{k}$ decays too slowly ($\tau<1$), then the error probability converges to zero at a rate slower than exponential (if at all it converges to zero.) On the other hand, if $\beta_{k}$ decays too fast ($\tau>1$), then the error probability does decay to zero exponentially, but the rate is no better than the rate of the individual detection, irrespective of $\bf{G_{c}}$.

2. Tightness of the bounds in Theorems 4 and 5. The upper bound (43) for $\tau=1$ explains the tightness of the lower bound in Theorem 4 and the unavoidable simultaneous effects of the communication noise and information flow. The sequence $\{\alpha_{k}\}$ balances these via the parameter $b_{0}$.

Optimal $b_{0}^{\star}$. We now find $b_{0}^{\star}$ that optimizes (maximizes) (42); we pursue (42) rather than (41) as it allows simpler, closed form expressions. Proof of Lemma 6 follows after setting the derivative of the denominator of rhs in (42) to zero and is hence omitted for brevity.

Let Assumptions 1 through 3 and 5 hold. The optimal parameter $b_{0}^{\star}$ that maximizes (42) and the corresponding lower bound on $\liminf_{k\rightarrow\infty}-\frac{1}{k}\log P^{e}_{i}(k)$, are, respectively:

We use Lemma 6 to compare the distributed detector with the optimal centralized detector and the optimal single sensor detector. In the very high $\bf{G_{c}}$ regime (weak communication noise), when ${\bf{G_{c}}}\rightarrow\infty$, the distributed detector (at all sensors) achieves the asymptotic performance of the optimal centralized detector. On the other hand, when ${\bf{G_{c}}}$ decreases, at some point, the rhs in (45) falls below $\frac{1}{8}{\bf SSNR}_{i}$ and the distributed detector (12) at sensor $i$ becomes worse than if sensor $i$ worked in isolation. The discussion is formalized in the next Subsection that considers when sensors should cooperate.

IV-C Communication payoff

Eqn. (45) under low $bf{G_{c}}$ raises the issue whether a sensor $i$ should cooperate with its neighbors or not. We next formalize communication payoff.

The network $\mathcal{G}=(\mathcal{V},\mathcal{E})$ achieves communication payoff if:

Definition 7 says that the network achieves a communication payoff if the distributed detector error performance of the worst sensor is better than the isolated detector error performance for the best sensor without communication. Lemma 8 finds a threshold on the ${{\bf G_{c}}}$ above which it does pay off for sensors to communicate with their neighbors. Proofs of Lemma 8 is simple and is omitted.

Let Assumptions 1 through 3 and 5 hold. Set $b_{0}$ to the optimal value in (44). If

then the network achieves the communication payoff in the sense of Definition 7.

V Proof of Theorem 3

Subsection V-A sets up the analysis and Subsection V-B proves Theorem 3.

Define the matrices $\Phi(k,j)$, $k\geq j\geq 1$, as follows:

Then, the solution to the distributed detector (14) is:

In consensus, $W(k)\rightarrow J$, where $J$ is the ideal consensus averaging matrix. The matrix $\widetilde{W}(k)$ and its norm $\|\widetilde{W}(k)\|$ measure, in a sense, the imperfection in the information flow, i.e., how far $\widetilde{W}(k)$ is away from and $W(k)$ from $J$. If (24) holds then it is easy to see that

We see that the role of $a$ in $\alpha_{k}$ is to be an offset that enables (47) to hold for all $k$; that is, $a$ reduces $\|\widetilde{W}(k)\|$ for large $b_{0}$ and small $k$. We will see that $b_{0}$ is the effective tuning parameter that controls the detection performance. We also comment that the ratio $\frac{\lambda_{2}(\mathcal{L})}{\lambda_{N}(\mathcal{L})}$ is maximized by Ramanujan networks, see for details.

V-B Proof

We first study the mean of the decision variable $\mu(k)$. It evolves according to the following recursion (which can be seen by taking the expectation in (14)):

Next, we consider the error $\epsilon(k)$ of $\mu(k)$ wrt the assumed $\mu_{\infty}$ given in (33):

We will show that $\epsilon(k)\rightarrow 0$, which implies (33). Algebraic manipulations show that $\epsilon(k)$ satisfies:

Recall the eigendecomposition of the Laplacian in (3). The matrix $\Gamma(k)$ has the same eigenvectors as $\mathcal{L}$; simple calculations show that the eigenvalue $\lambda_{i}\left(\Gamma(k)\right)$ that corresponds to the eigenvector $q_{i}$ is:

We now decompose $\epsilon(k)$ into the consensus subspace, i.e., the component colinear with the vector $1$, and the component orthogonal to $1$: $\epsilon(k)=\left(I-J\right)\epsilon(k)+J\epsilon(k)=\left(I-J\right)\epsilon(k)+\left(\frac{1}{N}1^{\top}\epsilon(k)\right)1.$ We show separately that:

We first show (52). Multiplying (49) from the left by $1^{\top}$, using the orthogonality of the eigenvectors $q_{i}$, and using the fact that $1^{\top}W(k)=1^{\top}$, we get:

Multiplying (49) from the left by $(I-J)$, we get:

where (54) holds because $J\,W(k)=J$, $\widetilde{W}(k)J=0$, and $\left(I-J\right)\Gamma(k)=\Gamma(k)$. Now, by subadditivity and submultiplicativity of norms, (54) yields:

Before proceeding, we invoke the following deterministic variant of a result due to Robbins and Siegmund (Lemma 11, Chapter 2.2., .)

Let $\{u(k)\}$, $\{\rho(k)\}$, and $\{\kappa(k)\}$ be non-negative deterministic (scalar) sequences. Further, suppose that

Suppose that $\sum_{k=1}^{\infty}\kappa(k)<\infty$. Then: 1) $\sum_{k=1}^{\infty}\rho(k)<\infty$; and 2) $\lim_{k\rightarrow\infty}u(k)=u^{\star}$ exists.

i.e., proves (51). Namely, by Lemma 9, we have that

Also, by Lemma 9, $\lim_{k\rightarrow\infty}u(k)=\lim_{k\rightarrow\infty}\|(I-J)\epsilon(k)\|$ exists, and, hence, $\lim_{k\rightarrow\infty}\|(I-J)\epsilon(k)\|=0.$ This completes the proof of (53).

We now prove (34) using (33). Note first that

Thus, using the fact that $q_{1}=\frac{1}{\sqrt{N}}1$ and $J=q_{1}q_{1}^{\top}$, the matrix $\left(I+b_{0}\,\mathcal{L}\right)^{-1}$ decomposes as:

Finally, the inequality $\left|\left[Q\Lambda^{\prime}Q^{\top}m_{\eta}^{(1)}\right]_{i}\right|\leq\|\Lambda^{\prime}\|\|m_{\eta}^{(1)}\|=\frac{1}{1+b_{0}\lambda_{2}(\mathcal{L})}\|m_{\eta}^{(1)}\|$ yields (34). ∎

We now prove (35); we use the following auxiliary result.

Consider (46). Using the independence of $\eta(j)$ and $\eta(k)$, $k\neq j$, and the independence of $\eta(k)$ and $v(j)$, for all $k,j$, and using the equality $\Phi(k,j)=\widetilde{\Phi}(k,j)+J$, we have:

We next bound from above the quantity $k\sigma_{i}^{2}(k)$, using (V-B) and the following norm arguments: 1) $\|AB\|\leq\|A\|\,\|B\|$; 2) $\|Ab\|\leq\|A\|\,\|b\|$, for square matrices $A$ and $B$, and a vector $b$; 3) $\|e_{i}\|=1$; 4) $\|\Phi(k,j+1)\|=1$. (The latter claim is because $\|\Phi(k,j+1)\|$ is doubly stochastic.) The bound on $k\sigma_{i}^{2}(k)$ is as follows:

Taking the $\limsup$ in (62) yields (59).

We now prove (60). Note that $\mathcal{Z}(k)$ can be written via the following recursion:

The proof of (60) proceeds analogously to the proof of (51), except that the vector quantity $(I-J)\epsilon(k)$ is replaced by the scalar $\mathcal{Z}(k)$, and the vector $m_{\eta}^{(1)}$ is replaced by the scalar $1$. The proof of (61) is trivial. Theorem 3 now follows by combining (34) and (35) with (28) to obtain (36). ∎

VI Extensions to Non-Gaussian case

We have characterized the exponential decay rate of the error probability in the case of Gaussian (spatially correlated and time-uncorrelated) sensing noise, and Gaussian (spatially correlated and time-uncorrelated) additive communication noise. Our results, to a certain degree, extend to the case when: 1) the zero mean sensing noise is spatially and temporally independent, but with a generic distribution with finite second moments; and 2) the zero mean additive communication noise is spatially correlated, temporally independent, and with a generic distribution and finite second moment. In this case, Theorem 3 remains valid, and all the steps in proving Theorem 3, equations (33)-(35) still go through in the generalized case also (see Appendix.) We now explain the implications of Theorem 3 in the general non-Gaussian model.

Consider ${\bf{DSNR}}_{i}(k)$ in (30). In the Gaussian case, ${\bf{DSNR}}_{i}(k)$ determines the exponential decay rate of the error probability, as verified by equations (27) and (28). In general, this is no longer the case as higher order moments play a role; however, ${\bf{DSNR}}_{i}(k)$ still gives a good estimate for detection performance; see, e.g., . With the optimal centralized detector, we have that:

Theorem 3 implies that, with our distributed detector (14), the following holds for all sensors $i$:

VII Conclusion

We designed a consensus+innovations distributed detector that achieves exponential decay rate of the detection error probability at all sensors under noisy communication links, and even when certain (or most sensors) in isolation cannot perform successful detection. This improves over existing work like that achieves a strictly slower rate. We showed how our distributed detector optimally weighs the neighbors’ messages via the optimal sequence $\{\alpha_{k}\}$, balancing the two opposing effects: communication noise and information flow. We found a threshold on the communication noise power above which a sensor that successfully detects the event in isolation still improves its performance through cooperation over noisy links.

Appendix A Appendix

We will need the following two Lemmas (11 and 12), of which Theorem 5 is a direct corollary.

Let Assumptions 1 through 3 hold. In addition, assume Assumption 5. For the weight sequence $\beta_{k}=\frac{b_{0}}{a+k^{\tau}}$, we have the following:

We start by proving (67) for $\tau<1$. To this end, note that $\mathcal{Z}_{\beta}(k)$ updates according to the following recursion:

where $b^{\prime}:=b_{0}\lambda_{N}(\mathcal{L})$. By (74), for sufficiently large $k_{0}$, and for all $k\geq k_{0}$, we have that:

for appropriately chosen $b_{\beta}>0.$ Now, applying Lemma 4 in , we get that $\lim_{k\rightarrow\infty}\mathcal{Z}_{\beta}(k)=0.$

We proceed by proving (67) for $\tau>1$. By (74), and using the fact that $\mathcal{Z}_{\beta}(k)\leq 1$, $\forall k$, the quantity $\mathcal{Z}_{\beta}(k+1)$ can be bounded from below as follows:

for appropriately chosen $b^{\prime\prime}>0$, and for all $k\geq k_{1}$, where $k_{1}$ is sufficiently large. Now, consider the recursion:

Clearly, $\mathcal{Z}_{\beta}(k)\geq\mathcal{U}(k)$, for all $k\geq k_{1}$. Subtracting $1$ from both sides in (76) and applying Lemma 9 yields $\mathcal{U}(k)\rightarrow 0$, and, hence, $\liminf_{k\rightarrow\infty}\mathcal{Z}_{\beta}(k)\geq 1$; on the other hand, $\mathcal{Z}_{\beta}(k)\leq 1$, for all $k$, and, hence, (67) for $\tau>1$ holds.

To prove (67) and $\tau=1$, consider (A-A); as $\tau=1$, we have:

Similarly to the proof of (33) in Theorem 3, it can be shown that $\mathcal{V}(k)\rightarrow\frac{1}{1+2b^{\prime}}$. Noting that $\mathcal{Z}_{\beta}(k)\geq\mathcal{V}(k)$, $k=1,2,...$ yields (67) for $\tau=1$.

The proofs of (71) for $\tau<1$, $\tau>1$, and $\tau=1$ are trivial. ∎

Note that, under the assumptions of Lemma 12, $S_{\eta}={\bf{SSNR}}_{i}I$. Thus, in (V-B), the term

because $J\widetilde{\Phi}(k,j)=0$. Multiplying (V-B) by $k$, and using (77), we get:

We next bound $k\sigma_{i}^{2}(k)$ from above, using the following simple relations:

where (79) holds true because $\Phi(k,j)$ is doubly stochastic. The upper bound on $k\sigma_{i}^{2}(k)$ is as follows:

Taking the $\liminf$ in (80) yields (73). ∎

A-B Decay rate of the error probability for the ℳ​𝒟ℳ𝒟\mathcal{MD} algorithm in [5]

We show that, under Gaussian assumptions, with the Algorithm $\mathcal{MD}$ in (, eqn. (14)), the error probability decays to zero at a rate slower than exponential. Recall that $x_{i}(k)$, $\mu_{i}(k)$, $\sigma_{i}^{2}(k)$, and $P^{e}_{i}(k)$ are the sensor $i$’s decision variable, its mean and variance under $H_{1}$, and its local error probability, respectively. (Now latter quantities correspond to $\mathcal{MD}$ and no longer to (12).) Denote by $P^{e}_{w}(k)$ the worst error probability at time $k$ among sensors:

We show that:By Theorem 3, with (12), $P^{e}_{w}(k)=O(e^{-ck})$, hence better than $\mathcal{MD}.$

Namely, with $\mathcal{MD}$, $\lim_{k\rightarrow\infty}\mu_{i}(k)=\frac{1}{2N}{\bf SSNR},\>\>\forall i.$ Thus, for all $k\geq k^{\prime}$, for appropriate $k^{\prime}>0$:

for all $k\geq k^{\prime}$ and for appropriately chosen $c_{p}>0.$ Now, applying the upper bound on the $\mathcal{Q}$ function in (26) to (84) yields (82). It remains to show (83). Denote by $\mathcal{W}(k):=I-\beta_{k}L-\alpha_{k}I$ the updating matrix in the $\mathcal{MD}$ algorithm, where $\beta_{k}=\frac{b}{(k+1)^{\tau}}$, $\tau\in(\frac{1}{2},1)$, and $\alpha_{k}=\frac{a}{(k+1)^{\tau}}$, $a,b>0$. In our notation, the update rule for $x(k)$ with $\mathcal{MD}$ is as follows:

(Here $S_{\eta}$ and $S_{v}$ denote respectively the covariance matrix of the innovations $\eta(k)$ and of the communication noise $v(k)$, as before.) Taking the trace in (85) and after algebraic manipulations, we get:

Now, consider the sequence $\mathcal{S}(k)$ that evolves according to the recursion:

Clearly, $\gamma(k)\geq\mathcal{S}(k)\geq 0$, for all $k=k_{2},k_{2}+1,...$ It is easy to show that

Namely, subtracting $\frac{c_{v}}{c_{\Sigma}}$ from both sides of equality (86) yields:

which in turn implies (87); now, (87) implies that $\gamma(k)=\Omega\left(1\right)$. Hence, (83) holds.

References