Large Deviations Performance of Consensus+Innovations Distributed Detection with Non-Gaussian Observations

I Introduction

Consider a distributed detection scenario where $N$ sensors are connected by a generic network with intermittently failing links. The sensors perform consensus+innovations distributed detection; in other words, at each time $k$, each sensor $i$ updates its local decision variable $x_{i}(k)$ by: 1) sensing and processing a new measurement to create an intermediate variable; and 2) weight averaging it with its neighbors’ intermediate decision variables. We showed in that, when the sensor observations are Gaussian, the consensus+innovations distributed detector exhibits a phase transition. When the network connectivity is above a threshold, then the distributed detector is asymptotically optimal, i.e., asymptotically equivalent to the optimal centralized detector that collects the observations of all sensors.

This paper establishes the asymptotic performance of distributed detection over random networks for generic, non-Gaussian sensor observations. We adopt as asymptotic performance measure the exponential decay rate of the Bayes error probability (error exponent). We show that phase transition behavior emerges with non-Gaussian observations and demonstrate how the optimality threshold is a function of the log-moment generating function of the sensors’ observations and of the number of sensors $N$. This reveals a very interesting interplay between the distribution of the sensor observations (e.g., Gaussian or Laplace) and the rate of diffusion (or connectivity) of the network (measured by a parameter $|\log r|\in[0,\infty)$ defined in Section II): for a network with the same connectivity, a distributed detector with say, Laplace observations distributions, may match the optimal asymptotic performance of the centralized detector, while the distributed detector for Gaussian observations may be suboptimal, even though the centralized detectors for the two distributions, Laplace and Gaussian, have the same optimal asymptotic performance.

For distributed detection, we determine the range on the detection threshold $\gamma$ for which each sensor achieves exponentially fast decay of the error probability (strictly positive error exponent), and we find the optimal $\gamma$ that maximizes the error exponent. Interestingly, above the critical (phase transition) value for the network connectivity $|\log r|$, the optimal detector threshold is $\gamma=0$, mimicking the (asymptotically) optimal threshold for the centralized detector. However, below the critical connectivity, we show by a numerical example that the optimal distributed detector threshold might be non zero.

Brief review of the literature. Distributed detection has been extensively studied, in the context of parallel fusion architectures, e.g., , consensus-based detection , and, more recently, consensus+innovations distributed inference, see, e.g., for distributed estimation, and for distributed detection. Different variants of consensus+innovations distributed detection algorithms have been proposed; we analyze here running consensus, the variant in .

Reference considers asymptotic optimality of running consensus, but in a framework that is very different from ours. Reference studies the asymptotic performance of the distributed detector where the means of the sensor observations under the two hypothesis become closer and closer (vanishing signal to noise ratio (SNR)), at the rate of $1/\sqrt{k}$, where $k$ is the number of observations. For this problem, there is an asymptotic, non-zero, probability of miss and an asymptotic, non-zero, probability of false alarm. Under these conditions, running consensus is as efficient as the optimal centralized detector, , as long as the network is connected on average. Here, we assume that the means of the distributions stay fixed as $k$ grows. We establish, through large deviations, the rate (error exponent) at which the error probability decays to zero as $k$ goes to infinity. We show that connectedness on average is not sufficient for running consensus to achieve the optimality of centralized detection; rather, phase change occurs, with distributed becoming as good as centralized, when the network connectivity, measured by $|\log r|$, exceeds a certain threshold.

We distinguish this paper from our prior work on the performance analysis of running consensus. In , we studied deterministically time varying networks and Gaussian observations, and in , we considered a different consensus+innovations detector with Gaussian observations and additive communication noise. Here, we consider random networks, non-Gaussian observations, and noiseless communications. Reference considers random networks and Gaussian, spatially correlated observations. In contrast, here the observations are non-Gaussian spatially independent. We proved our results in by using the quadratic nature of the Gaussian log-moment generating function. For general non-Gaussian observations, the log-moment generating function is no longer quadratic, and the arguments in no longer apply; we develop a more general methodology that establishes the optimality threshold in terms of the log-moment generating function of the log-likelihood ratio. We derive our results from generic properties of the log-moment generating function like convexity and zero value at the origin. Finally, while reference and our other prior work considered zero detection threshold $\gamma=0$, here we extend the results for generic detection thresholds $\gamma$. Our analysis reveals that, when $|\log r|$ is above its critical value, the zero detector threshold $\gamma=0$ is (asymptotically) optimal. When $|\log r|$ is below the critical value, we compute the best detector threshold $\gamma=\gamma^{\star}$, which may be non-zero in general.

Our analysis shows the impact of the distribution of the sensor observations on the performance of distributed detection: distributed detectors (with different distributions of the sensors observations) can have different asymptotic performance, even though the corresponding centralized detectors are equivalent, as we will illustrate in detail in Section IV.

Paper outline. Section II introduces the network and sensor observations models and presents the consensus+innovations distributed detector. Section III presents and proves our main results on the asymptotic performance of the distributed detector. For a cleaner exposition, this section proves the results for (spatially) identically distributed sensor observations. Section IV illustrates our results on several types of sensor observation distributions, namely, Gaussian, Laplace, and discrete valued distributions, discussing the impact of these distributions on distributed detection performance. Section V extends our main results to non-identically distributed sensors’ observations. Finally, Section VI concludes the paper.

II Problem formulation

This section introduces the sensor observations model, reviews the optimal centralized detector, and presents the consensus+innovations distributed detector. The section also reviews relevant properties of the log-moment generating function of a sensor’s log-likelihood ratio that are needed in the sequel.

We study the binary hypothesis testing problem $H_{1}$ versus $H_{0}$. We consider a network of $N$ nodes where $Y_{i}(t)$ is the observation of sensor $i$ at time $t$, where $i=1,\ldots,N$, $t=1,2,\ldots$

The sensors’ observations $\left\{Y_{i}(t)\right\}$ are independent and identically distributed (i.i.d.) both in time and in space, with distribution $\nu_{1}$ under hypothesis $H_{1}$ and $\nu_{0}$ under $H_{0}$:

By spatial independence, the joint distribution of the observations of all sensors

at any time $t$ is $\nu_{1}^{N}$ under $H_{1}$ and $\nu_{0}^{N}$ under $H_{0}$. Our main results in Section III are derived under Assumption 1. Section V extends them to non-identical (but still independent) sensors’ observations.

II-B Centralized detection, log-moment generating function (LMGF), and optimal error exponent

The log-likelihood ratio of sensor $i$ at time $t$ is $L_{i}(t)$ and given by

where, $f_{l}(\cdot)$, $l=0,1,$ is 1) the probability density function corresponding to $\nu_{l}$, when $Y_{i}(t)$ is an absolutely continuous random variable; or 2) the probability mass function corresponding to $\nu_{l}$, when $Y_{i}(t)$ is discrete valued.

Under Assumption 1, the log-likelihood ratio test for $k$ time observations from all sensors, for a threshold $\gamma$ is: In (3), we re-scale the spatio-temporal sum of the log-likelihood ratios $L_{i}(t)$ by dividing the sum by $Nk$. Note that we can do so without loss of generality, as the alternative test without re-scaling is: $\sum_{t=1}^{k}\sum_{i=1}^{N}L_{i}(t)\stackrel{{\scriptstyle[}}{{H}}_{0}]{H_{1}}{\gtrless}\gamma^{\prime},$ with $\gamma^{\prime}=Nk\gamma.$

Log-moment generating function (LMGF). We introduce the LMGF of $L_{i}(t)$ and its properties that play a major role in assessing the performance of distributed detection.

Let $\Lambda_{l}$ ($l=0,1$) denote the LMGF for the log-likelihood ratio under hypothesis $H_{l}$:

In (4), $L_{1}(1)$ replaces $L_{i}(t)$, for arbitrary $i=1,...,N$, and $t=1,2,...$, due to the spatial and temporal identically distributed observations, see Assumption 1.

Consider Assumption 1. For $\Lambda_{0}$ and $\Lambda_{1}$ in (4) the following holds:

For a proof of (a) and (b), see . Part (c) follows from the definitions of $\Lambda_{0}$ and $\Lambda_{1}$, which we show here for the case when the distributions $\nu_{1}$ and $\nu_{0}$ are absolutely continuous (the proof for discrete distributions is similar):

We further assume that the LMGF of a sensor’s observation is finite.

In the next two remarks, we give two classes of problems when Assumption 2 holds.

Remark I. We consider the signal+noise model:

In (8) and (10), we can also allow either (or both) $\mu_{+},\mu_{-}$ to equal 1, but then the corresponding $\rho$ is in $(1,\infty)$. Note that $f_{n}(\cdot)$ need not be symmetric, i.e., $f_{n}(y)$ need not be equal to $f_{n}(-y)$. Intuitively, the tail of the density $f_{n}(\cdot)$ behaves regularly, and $g(y)$ grows either like a polynomial of arbitrary finite order in $y$, or slower, like a power $y^{\tau}$, $\tau\in(0,1)$, or like a logarithm $c(\log y)^{\mu}$. The class of admissible densities $f_{n}(\cdot)$ includes, e.g., power laws $cy^{-p}$, $p>1$, or the exponential families $e^{\theta\,\phi(y)-A(\theta)}$, $A(\theta):=\log\int_{y=-\infty}^{+\infty}e^{\theta\phi(y)}\chi(dy)$, with: 1) the Lebesgue base measure $\chi$; 2) the polynomial, power, or logarithmic potentials $\phi(\cdot)$; and 3) the canonical set of parameters $\theta\in\Theta=\left\{\theta:\,\,A(\theta)<+\infty\right\}$, .

Remark II. Assumption 2 is satisfied if $Y_{i}(k)$ has arbitrary (different) distributions under $H_{1}$ and $H_{0}$ with the same, compact support; a special case is when $Y_{i}(k)$ is discrete, supported on a finite alphabet.

Denote by $I_{l}(\cdot)$, $l=0,1,$ the Fenchel-Legendre transform of $\Lambda_{l}(\cdot)$:

It can be shown that $I_{l}(\cdot)$ is nonnegative, strictly convex, $I_{l}(\gamma_{l})=0$, for $l=0,1$, and $I_{1}(z)=I_{0}(z)-z$, . We now state the result on the centralized detector’s asymptotic performance.

Let Assumption 1 hold, and consider the family of centralized detectors (3) with constant threshold $\gamma=\gamma\in(\gamma_{0},\gamma_{1}).$ Then, the best (maximal) error exponent:

Denote by $\Lambda_{0,N}$ the LMGF for the log-likelihood ratio $\sum_{i=1}^{N}L_{i}(t)$ for the observations of all sensors at time $t$. Then, $\Lambda_{0,N}(\lambda)=N\Lambda_{0}(\lambda)$, by the i.i.d. in space assumption on the sensors’ observations. The Lemma now follows by the Chernoff lemma (Corollary 3.4.6, ):

II-C Distributed detection algorithm

We now consider distributed detection when the sensors cooperate through a randomly varying network. Specifically, we consider the running consensus distributed detector proposed in . Each node $i$ maintains its local decision variable $x_{i}(k)$, which is a local estimate of the global optimal decision variable $D(k)$ in (3). Note that $D(k)$ is not locally available. At each time $k$, each sensor $i$ updates $x_{i}(k)$ in two ways: 1) by incorporating its new observation $Y_{i}(k)$ to make an intermediate decision variable $\frac{k-1}{k}x_{i}(k-1)+\frac{1}{k}L_{i}(k)$; and 2) by exchanging the intermediate decision variable locally with its neighbors and computing the weighted average of its own and the neighbors’ intermediate variables.

More precisely, the update of $x_{i}(k)$ is as follows:

Here $O_{i}(k)$ is the (random) neighborhood of sensor $i$ at time $k$ (including $i$), and $W_{ij}(k)$ are the (random) averaging weights. The sensor $i$’s local decision test at time $k$ is:

i.e., $H_{1}$ (respectively, $H_{0}$) is decided when $x_{i}(k)\geq\gamma$ (respectively, $x_{i}(k)<\gamma$).

Write the consensus+innovations algorithm (13) in vector form. Let $x(k)=(x_{1}(k),x_{2}(k),...,x_{N}(k))^{\top}$ and $L(k)=(L_{1}(k),...,L_{N}(k))^{\top}$. Also, collect the averaging weights $W_{ij}(k)$ in the $N\times N$ matrix $W(k)$, where, clearly, $W_{ij}(k)=0$ if the sensors $i$ and $j$ do not communicate at time step $k$. The algorithm (13) becomes:

Network model. We state the assumption on the random averaging matrices $W(k)$.

The averaging matrices $W(k)$ satisfy the following:

The sequence $\left\{W(k)\right\}_{k=1}^{\infty}$ is i.i.d.

$W(k)$ is symmetric and stochastic (row-sums equal 1 and $W_{ij}(k)\geq 0$) with probability one, $\forall k$.

There exists $\eta>0$, such that, for any realization $W(k)$, $W_{ii}(k)\geq\eta$, $\forall i$, and, $W_{ij}(k)\geq\eta$ whenever $W_{ij}(k)>0$, $i\neq j$.

$W(k)$ and $Y(t)$ are mutually independent over all $k$ and $t$.

Condition (c) is mild and says that: 1) sensor $i$ assigns a non-negligible weight to itself; and 2) when sensor $i$ receives a message from sensor $j$, sensor $i$ assigns a non-negligible weight to sensor $j$.

It is easy to verify from (15) that $x(k)$ equals:

Network connectivity. From (17), we can see that the matrices $\Phi(k,t)$ should be as close to $J$ as possible for enhanced detection performance. Namely, the ideal (unrealistic) case when $\Phi(k,t)\equiv J$ for all $k,t$, corresponds to the scenario where each sensor $i$ is equivalent to the optimal centralized detector. It is well known that, under certain conditions, the matrices $\Phi(k,t)$ converge in probability to $J$:

The following Lemma easily follows from (18).

Let Assumption 3 hold. Then, for any $\delta>0$, there exists a constant $C(\delta)\in(0,\infty)$ (independent of $\epsilon\in(0,1)$) such that:

III Main results: Asymptotic analysis and error exponents for distributed detection

Subsection III-A states our main results on the asymptotic performance of consensus+innovations distributed detection; subsection III-B proves these results.

where, we recall, $\pi_{1}$ and $\pi_{0}$ are the prior probabilities.

and define $\gamma_{l}^{-},\gamma_{l}^{+}$, $l=0,1$ by

Then, for every $\gamma\in(\gamma_{0},\gamma_{1})$, at each sensor $i$, $i=1,\ldots,N$, we have:

Let Assumptions 1-3 hold and consider the family of distributed detectors in (13) and (14) parameterized by detector thresholds $\gamma\in(\gamma_{0},\gamma_{1})$. Then:

and the lower bound in (24) is maximized for the point $\gamma^{\star}\in(\gamma_{0},\gamma_{1})$As we show in the proof, such a point exists and is unique. at which $B_{0}(\gamma^{\star})=B_{1}(\gamma^{\star}).$

Figure 1 (left) illustrates the error exponent lower bounds $B_{0}(\gamma)$ and $B_{1}(\gamma)$ in Theorem 5, while Figure 1 (right) illustrates the quantities in (21). ( See the definition of the function $\Phi_{0}(\lambda)$ in (36) in the proof of Theorem 5.) We consider $N=3$ sensors and a discrete distribution of $Y_{i}(t)$ over a 5-point alphabet, with the distribution $[.2,.2,.2,.2,.2]$ under $H_{1}$, and $[0.01,0.01,0.01,0.01,0.96]$ under $H_{0}$. We set here $r=0.4.$

Corollary 6 states that, when the network connectivity $|\log r|$ is above a threshold, the distributed detector in (13) and (14) is asymptotically equivalent to the optimal centralized detector. The corresponding optimal detector threshold is $\gamma=0$. When $|\log r|$ is below the threshold, Corollary 6 determines what value of the error exponent the distributed detector can achieve, for any given $\gamma\in(\gamma_{0},\gamma_{1})$. Moreover, Corollary 6 finds the optimal detector threshold $\gamma^{\star}$ for a given $r$; $\gamma^{\star}$ can be found as the unique zero of the strictly decreasing function $\Delta_{B}(\gamma):=B_{1}(\gamma)-B_{0}(\gamma)$ on $\gamma\in(\gamma_{0},\gamma_{1})$, see the proof of Corollary 6, e.g., by bisection on $(\gamma_{0},\gamma_{1})$.

Corollary 6 establishes that there exists a “sufficient” connectivity, say $|\log r^{\star}|$, so that further improvement on the connectivity (and further spending of resources, e.g., transmission power) does not lead to a pay off in terms of detection performance. Hence, Corollary 6 is valuable in the practical design of a sensor network, as it says how much connectivity (resources) is sufficient to achieve asymptotically optimal detection.

Equation (24) says that the distribution of the sensor observations (through LMGF) plays a role in determining the performance of distributed detection. We illustrate and explain by examples this effect in Section IV.

III-B Proofs of the main results

Consider the probability of false alarm $\alpha_{i}(k,\gamma)$ in (19). We upper bound $\alpha_{i}(k,\gamma)$ using the exponential Markov inequality parameterized by $\zeta\geq 0$:

Next, by setting $\zeta=N\,k\,\lambda$, with $\lambda\geq 0$, we obtain:

The terms in the sum in the exponent in (28) are conditionally independent, given the realizations of the averaging matrices $W(t)$, $t=1,\ldots,k$, Thus, by iterating the expectations, and using the definition of $\Lambda_{0}$ in (4), we compute the expectation in (28) by conditioning first on $W(t)$, $t=1,\ldots,k$:

Partition of the sample space. We handle the random matrix realizations $W(t)$, $t=1,\ldots,k$, through a suitable partition of the underlying probability space. Adapting an argument from , partition the probability space based on the time of the last successful averaging. In more detail, for a fixed $k$, introduce the partition $\mathcal{P}_{k}$ of the sample space that consists of the disjoint events $\mathcal{A}_{s,k}$, $s=0,1,...,k$, given by:

for $s=1,...,k-1$, $\mathcal{A}_{0,k}=\{\|\Phi(k,1)-J\|>\epsilon\}$, and ${A}_{k,k}=\left\{\|\Phi(k,k)-J\|\leq\epsilon\right\}$. For simplicity of notation, we drop the index $k$ in the sequel and denote event $\mathcal{A}_{s,k}$ by $\mathcal{A}_{s}$, $s=0,\ldots,k$. for $\epsilon>0$. Intuitively, the smaller $t$ is, the closer the product $\Phi(k,t)$ to $J$ is; if the event $\mathcal{A}_{s}$ occurred, then the largest $t$ for which the product $\Phi(k,t)$ is still $\epsilon$-close to $J$ equals $s$. We now show that $\mathcal{P}_{k}$ is indeed a partition. We need the following simple Lemma. The Lemma shows that convergence of $\Phi(k,s)-J$ is monotonic, for any realization of the matrices $W(1),W(2),...,W(k).$

Let Assumption 3 hold. Then, for any realization of the matrices $W(1),...,W(k)$:

Since every realization of $W(t)$ is stochastic and symmetric for every $t$, we have that $W(t)1=1$ and $1^{\top}W(t)=1^{\top}$, and, so: $\Phi(k,s)-J=W(k)\cdots W(s)-J=(W(k)-J)\cdots(W(s)-J)$. Now, using the sub-multiplicative property of the spectral norm, we get

To show that $\mathcal{P}_{k}$ is a partition, note first that (at least) one of the events $\mathcal{A}_{0},...,\mathcal{A}_{k}$ necessarily occurs. It remains to show that the events $\mathcal{A}_{s}$ are disjoint. We carry out this by fixing arbitrary $s=1,...,k$, and showing that, if the event $\mathcal{A}_{s}$ occurs, then $\mathcal{A}_{t}$, $t\neq s$, does not occur. Suppose that $\mathcal{A}_{s}$ occurs, i.e., the realizations $W(1),...,W(k)$ are such that $\|\Phi(k,s)-J\|\leq\epsilon$ and $\|\Phi(k,s+1)-J\|>\epsilon$. Fix any $t>s.$ Then, event $\mathcal{A}_{t}$ does not occur, because, by Lemma 7, $\|\Phi(k,t)-J\|\geq\|\Phi(k,s+1)-J\|>\epsilon.$ Now, fix any $t<s.$ Then, event $\mathcal{A}_{t}$ does not occur, because, by Lemma 7, $\|\Phi(k,t+1)-J\|\leq\|\Phi(k,s)-J\|\leq\epsilon.$ Thus, for any $s=1,...,k$, if the event $\mathcal{A}_{s}$ occurs, then $\mathcal{A}_{t}$, for $t\neq s$, does not occur, and hence the events $\mathcal{A}_{s}$ are disjoint.

Using the total probability law over $\mathcal{P}_{k}$, the expectation (29) is computed by:

where, we recall, $\mathcal{I}_{\mathcal{A}_{s}}$ is the indicator function of the event $\mathcal{A}_{s}$. The following lemma explains how to use the partition $\mathcal{P}_{k}$ to upper bound the expectation in (30).

For any realization of the random matrices $W(t)$, $t=1,2,...,k$:

Further, consider a fixed $s$ in $\{0,1,...,k\}$. If the event $\mathcal{A}_{s}$ occurred, then, for $i=1,\ldots,N$: $\Lambda_{0}\left(N\lambda\Phi_{i,j}(k,t)\right)\leq\max\left(\Lambda_{0}\left(\lambda-\epsilon N\sqrt{N}\lambda\right),\Lambda_{0}\left(\lambda+\epsilon N\sqrt{N}\lambda\right)\right),\>\forall t=1,\ldots,s,\,\forall j=1,\ldots,N.$

To prove part (b) of the Lemma, suppose that event $\mathcal{A}_{s}$ occurred. Then, by the definition of $\mathcal{A}_{s}$,

Using the fact that each realization $W(t)$, $t=1,2,\ldots$, is doubly stochastic, and using the sub-multiplicative property of the spectral norm, we have that

for every $t\leq s$. Then, by the equivalence of the 1-norm and the spectral norm, it follows that:

Finally, since $\Lambda_{0}$ is convex (Lemma 1, part (a)), its maximum in $\left[\lambda-\epsilon N\sqrt{N}\lambda,\lambda+\epsilon N\sqrt{N}\lambda\right]$ is attained at a boundary point and the claim follows. ∎

We now fix $\delta\in(0,|\log r|)$. Using the results from Lemma 4 and Lemma 8, we next bound the expectation in (30) as follows:

To simplify the notation, we introduce the function:

We need the following property of $g_{0}(\cdot,\cdot)$.

Since $\Lambda_{0}(\cdot)$ is convex, for $\epsilon^{\prime}<\epsilon$ and for fixed $\lambda$, we have that

Thus, for fixed $\lambda$, $f(\cdot,\lambda)$ is non-increasing, and the claim of the Lemma follows. ∎

We proceed by bounding further the right hand side in (31), by rewriting $e^{-(k-(s+1))(|\log r|-\delta)}$ as $\frac{1}{re^{\delta}}\,e^{-(k-s)(|\log r|-\delta)}$:

The second inequality follows by introducing $\theta:=\frac{s}{k}$ and by enlarging the set for $\theta$ from $\left\{0,\frac{1}{k},\ldots,1\right\}$ to the continuous interval $$. Taking the$\log$and dividing by$k$, from (27) and (33) we get:

Taking the $\limsup$ when $k\rightarrow\infty$, the first two terms in the right hand side of (34) vanish; further, changing the sign, we get a bound on the exponent of $\alpha_{i}(k)$ that holds for every $\epsilon>0$:

By Lemma 9, as $\epsilon\rightarrow 0$, $Ng_{0}(\epsilon,\lambda)$ decreases to $N\,\Lambda_{0}(\lambda)$; further, letting $\delta\rightarrow 0$, we get

The previous bound on the exponent of the probability of false alarm holds for any $\lambda\geq 0$. To get the best bound, we maximize the expression on the right hand side of (35) over $\lambda\in[0,\infty)$. (We refer to figure 1 to help illustrate the bounds $B_{0}(\gamma)$ and $B_{1}(\gamma)$ for a discrete valued observations $Y_{i}(t)$ over a 5-point alphabet.) To this end, introduce

We show that the best bound equals $B_{0}(\gamma)$ in (23), i.e.:

From the first order optimality conditions, for a fixed $\gamma$, an optimizer $\lambda^{\star}=\lambda^{\star}(\gamma)$ (if it exists) of the objective in (37) is a point that satisfies:

where last inequality is by Theorem 5. We now show that $\min\{B_{0}(\gamma),B_{1}(\gamma)\}>0$ for all $\gamma\in(\gamma_{0},\gamma_{1}).$ First, from the expression for $B_{0}(\gamma)$ in Theorem 5, for $|\log r|>0$, we have: $B_{0}(\gamma_{0})=NI_{0}(\gamma_{0})=0$, and $B_{0}^{\prime}(\gamma)=NI_{0}^{\prime}(\gamma)>0$ for any $\gamma\in(\gamma_{0},\gamma_{0}^{-})$. As the function $B_{0}(\cdot)$ is convex, we conclude that $B_{0}(\gamma)>0$, for all $\gamma>\gamma_{0}.$ (The same conclusion holds under $|\log r|=0,$ by replacing $NI_{0}(\gamma)$ with $I_{0}(\gamma)+|\log r|=I_{0}(\gamma).$) Analogously, it can be shown that $B_{1}(\gamma)>0$ for all $\gamma<\gamma_{1}$, and so $\min\{B_{0}(\gamma),B_{1}(\gamma)\}>0$, for all $\gamma\in(\gamma_{0},\gamma_{1}).$

We now calculate $\max_{\gamma\in(\gamma_{0},\gamma_{1})}\min\{B_{0}(\gamma),B_{1}(\gamma)\}$. Consider the function $\Delta_{B}(\gamma):=B_{1}(\gamma)-B_{0}(\gamma)$. Using the definition of $B_{0}(\gamma)$ in Theorem 5, and taking the subdifferential of $B_{0}(\gamma)$ at any point $\gamma\in(\gamma_{0},\gamma_{1})$, it is easy to show that $B_{0}^{\prime}(\gamma)>0$, for any subgradient $B_{0}^{\prime}(\gamma)\in\partial B_{0}(\gamma)$, which implies that $B_{0}(\cdot)$ is strictly increasing on $\gamma\in(\gamma_{0},\gamma_{1})$. Similarly, it can be shown that $B_{1}(\cdot)$ is strictly decreasing on $\gamma\in(\gamma_{0},\gamma_{1})$. Further, using the properties that $I_{0}(\gamma_{0})=0$ and $I_{1}(\gamma_{1})=0$, we have $\Delta_{B}(\gamma_{0})=B_{1}(\gamma_{0})>0$, and $\Delta_{B}(\gamma_{1})=-B_{0}(\gamma_{1})<0$. By the previous two observations, we have that $\Delta_{B}(\gamma)$ is strictly decreasing on $\gamma\in(\gamma_{0},\gamma_{1})$, with $\Delta_{B}(\gamma_{0})>0$ and $\Delta_{B}(\gamma_{1})<0$. Thus, $\Delta_{B}(\cdot)$ has a unique zero $\gamma^{\star}$ in $\gamma\in(\gamma_{0},\gamma_{1})$. Now, the fact that $\max_{\gamma\in(\gamma_{0},\gamma_{1})}\min\{B_{0}(\gamma),B_{1}(\gamma)\}=B_{0}(\gamma^{\star})=B_{1}(\gamma^{\star})$ holds trivially because $B_{0}(\cdot)$ is strictly increasing on $\gamma\in(\gamma_{0},\gamma_{1})$ and $B_{1}(\cdot)$ is strictly decreasing on $\gamma\in(\gamma_{0},\gamma_{1})$. This completes the proof of part (a).

IV Examples

This section illustrates our main results for several examples of the distributions of the sensor observations. Subsection IV-A compares the Gaussian and Laplace distributions, both with a finite number of sensors $N$ and when $N\rightarrow\infty$. Subsection IV-B considers discrete distributions with finite support, and, in more detail, binary distributions. Finally, Subsection IV-C numerically demonstrates that our theoretical lower bound on the error exponent (24) is tight. Subsection IV-C also shows trhough a symmetric, tractable example how distributed detection performance depends on the network topology (nodes’ degree and link occurrence/failure probability.)

Gaussian distribution. We now study the detection of a signal in additive Gaussian noise; $Y_{i}(t)$ has the following density:

Applying Corollary 6, we get the sufficient condition for optimality:

Since $\Lambda_{0}(\lambda)=\Lambda_{1}(\lambda)$, the two conditions from the Corollary here reduce to a single condition in (24).

Laplace distribution. We next study the optimality conditions for the sensor observations with Laplace distribution. The density of $Y_{i}(t)$ is:

Again, the minimum is at $\lambda^{\bullet}=\frac{1}{2}$, and the per sensor Chernoff information is

The optimality condition in (24) becomes:

Hence, the required $|\log r|$ to achieve the optimal error exponent grows much slower with the Laplace distribution than with the Gaussian distribution.

IV-B Discrete distributions

We now consider the case when the support of the sensor observations under both hypothesis is a finite alphabet $\{a_{1},a_{2},...,a_{M}\}$. This case is of practical interest when, for example, the sensing device has an analog-to-digital converter with a finite range; hence, the observations take only a finite number of values. Specifically, the distribution of $Y_{i}(k)$, $\forall i$, $\forall k$, is given by:

Combining (51) and (52), and applying Corollary 6 (equation (24)), we get that a sufficient condition for asymptotic optimality is:

We further assume a very simplified sufficient condition for optimality:

IV-C Tightness of the error exponent lower bound in (24) and impact of the network topology

Impact of the network topology. We have seen in the previous two subsections how detection performance depends on $r$. In order to understand how $r$ depends on the network topology, we consider a symmetric network structure, namely a regular network. For this case, we can express $r$ as an explicit (closed form) function of the nodes’ degrees and the link occurrence probabilities. (Recall that the smaller $r$ is, the better the network connectivity.)

Consider a connected regular network with $N$ nodes and degree $d\geq 2$. Suppose that each link is a Bernoulli random variable, equal to $1$ with probability $p$ (link online) and with probability $1-p$ (link offline,) with spatio-temporally independent link occurrences. Then, it can be shown that $r$ equals:

This expression is very intuitive. When $p$ increases, i.e., when the links are online more often, the network (on average) becomes more connected, and hence we expect that the network connectivity $|\log r|$ increases (improves). This is confirmed by (54): when $p$ increases, $r$ becomes smaller and closer to zero. Further, when $d$ increases, the network becomes more connected, and hence the network speed again improves. Note also that $|\log r|=d|\log(1-p)|$ is a linear function of $d$.

V Non-identically distributed observations

We extend Theorem 5 and Corollary 6 to the case of (independent) non-identically distributed observations. First, we briefly explain the measurement model and define the relevant quantities. As before, let $Y_{i}(t)$ denote the observation of sensor $i$ at time $t$, $i=1,\ldots,N$, $t=1,2,\ldots$.

Assumption A The observations of sensor $i$ are i.i.d. in time, with the following distribution:

(Here we assume that $\nu_{i,1}$ and $\nu_{i,0}$ are mutually absolutely continuous, distinguishable measures, for $i=1,\ldots,N$). Further, the observations of different sensors are independent both in time and in space, i.e., for $i\neq j$, $Y_{i}(t)$ and $Y_{j}(k)$ are independent for all $t$ and $k$.

Under Assumption A, the form of the log-likelihood ratio test remains the same as under Assumption 1:

where the log-likelihood ratio at sensor $i$, $i=1,...,N$, is now:

Denote by $\Lambda_{i,0}$ the LMGF of $L_{i}(t)$ under hypothesis $H_{0}$:

We assume finiteness of the LMGF’s of all sensors. Assumption 2 is restated explicitly as Assumption B.

The optimal centralized detector, with highest error exponent, is the likelihood ratio test with zero threshold $\gamma=0$ , its error exponent is equal to the Chernoff information of the vector of all sensors observations, and can be expressed in terms of the LMGF’s as:

Let Assumptions A, B and 3 hold, and let, in addition, $|\log r|>0.$ Consider the family of distributed detectors in (13) and (14) with thresholds $\gamma\in(\overline{\gamma}_{0},\overline{\gamma}_{1})$. Then, at each sensor $i$:

Let Assumptions A, B and 3 hold, and let, in addition, $|\log r|>0.$ Consider the family of distributed detectors in (13) and (14) with thresholds $\gamma\in(\overline{\gamma}_{0},\overline{\gamma}_{1})$. Then:

and the lower bound in (58) is maximized for the point $\gamma^{\star}\in(\overline{\gamma}_{0},\overline{\gamma}_{1})$ at which $B_{0}(\gamma^{\star})=B_{1}(\gamma^{\star}).$

Comparing Theorem 5 with Theorem 10, we can see that, under non-identically distributed observations, it is no longer possible to analytically characterize the lower bounds on the error exponents, $B_{0}(\gamma)$ and $B_{1}(\gamma)$. However, the objective functions (in the variable $\lambda$) in (56) and (57) are concave (by convexity of the LMGF’s) and the underlying optimization variable $\lambda$ is a scalar, and, thus, $B_{0}(\gamma)$ and $B_{1}(\gamma)$ can be efficiently found by a one dimensional numerical optimization procedure, e.g., a subgradient algorithm .

The proof of Theorem 10 mimics the proof of Theorem 5; we focus only on the steps that account for different sensors’ LMGF’s. First, expression (29) that upper bounds the probability of false alarm $\alpha_{i}(k,\gamma)$ for the case of non-identically distributed observations becomes:

Next, we bound the sum in the exponent of the previous equation, conditioned on the event $\mathcal{A}_{s}$, for a fixed $s$ in $\{0,1\ldots,k\}$, deriving a counterpart to Lemma 8.

For any realization of $W(t)$, $t=1,2,...,k$:

Consider a fixed $s$ in $\{0,1,...,k\}$. If the event $\mathcal{A}_{s}$ occurred, then, for $i=1,...,N$:

The remainder of the proof proceeds analogously to the proof of Theorem 5. ∎

VI Conclusion

We analyzed the large deviations performance (error exponent) of consensus+innovations distributed detection over random networks. The sensors’ observations have generic (non-Gaussian) distribution, independent, not necessarily identical over space, and i.i.d. in time. Our results hold assuming that the log-moment generating functions of each sensor’s log-likelihood ratio are finite. We showed that the distributed detector exhibits a phase transition behavior with respect to the network connectivity, measured by $|\log r|$, where $r$ is the (exponential) rate of convergence in probability of the product $W(k)W(k-1)\cdots W(1)$ to the consensus matrix $J:=(1/N)11^{\top}$. When $|\log r|$ is above the threshold, the distributed detector has the same error exponent as the optimal centralized detector. We further showed that the optimality threshold depends on the type of the distribution of the sensor observations. Numerical and analytical studies illustrated this dependence for Gaussian, Laplace, and binary distributions of the sensors’ observations.

Appendix A Appendix

where we use the fact that the density under $H_{1}$ is $f_{1}(y)=f_{n}(y-m)$, i.e., $f_{1}(\cdot)$ is the shifted density $f_{n}(\cdot)$ (of the noise) under $H_{0}$. With $f_{n}(y)=ce^{-g(y)}$, (60) is rewritten as:

Now, by (7), for any $\epsilon_{1}\in(0,\infty)$, there exists $M_{1}\in(0,\infty)$, so that

Also, for any $\epsilon_{2}\in(0,\infty)$, there exists $M_{2}\in(0,\infty)$, such that:

To upper bound the integral $\int_{y=0}^{+\infty}e^{-g(y)\left[1-\lambda\left(1-\frac{g(y-m)}{g(y)}\right)\right]}dy$, we note that, by (63), we can choose $M_{3}$ large enough, so that: $\left|1-\frac{g(y-m)}{g(y)}\right|\leq\frac{\epsilon_{3}}{|\lambda|},\>\>\ \forall y\geq M_{3},$ for arbitrary $\epsilon_{3}\in(0,1)$. Thus, we have:

References