A.1.  is divisible;

A.2. the network is connected;

A.3. the degree of each node is chosen as ;

2.07.2.2.1 Statistically independent observations

Let us start assuming that the observations taken by different sensors are statistically independent, conditioned to each hypothesis. This is an assumption valid in many cases. Under such an assumption, the LR can be factorized as follows

(7.9)

where denotes the local LR at the nth node. In this case, the global function in (7.9) possesses a clear structure: It is factorizable in the product of the local LR functions. Then, since a factorizable function is divisible, it is possible to implement the efficient mechanisms described in the previous section to achieve an efficient design. The network nodes should cluster as in Figure 7.1. Every relay node should compute the local LR, multiply it to the data received from the relays pertaining to the lower clusters and send the partial result to the relay of the upper cluster, until the result reaches the fusion center. The efficiency comes from the fact that many transmissions can occur in parallel, exploiting spatial reuse of radio resources. This result suggests also that the proper source encoding to be implemented at each sensor node consists in the computation of the local LR.

2.07.2.2.2 Markov observations

The previous result is appealing, but it pertains to the simple situation where the observations are statistically independent, conditioned to the hypotheses. In some circumstances, however, this assumption is unjustified. This is the case, for example, when the sensors monitor a field of spatially correlated values, like a temperature or atmospheric pressure field. In such cases, nearby nodes sense correlated values and then the statistical independence assumption is no longer valid. It is then of interest, in such cases, to check whether the statistical properties of the observations can still induce a structure on the function to be computed that can be exploited to improve network efficiency.

There is indeed a broad class of observation models where the joint pdf cannot be factorized into the product of the individual pdf’s pertaining to each node, but it can still be factorized into functions of subsets of variables. This is the case of Bayes networks or Markov random fields. Here we will recall the basic properties of these models, as relevant to our problem. The interested reader can refer to many excellent books, like, for example, [6] or [7].

In the Bayes network’s case, the statistical dependency among the random variables is described by an acyclic directed graph, whose vertices represent the random variables, while the edges represent local conditional probabilities. In particular, given a node , whose parent nodes are identified by the set of indices , the joint probability density function (pdf) of a Bayes network can be written as

(7.10)

where collects all the variables corresponding to the parents of node i. If a node in (7.10) does not have parents, the corresponding probability is unconditional.

Alternatively, a Markov random field is represented through an undirected graph. More specifically, a Markov network consists of:

Let us denote by the set of all cliques present in the graph. The random vector is Markovian if its joint pdf admits the following factorization

(7.11)

where denotes the vector of variables belonging to the clique c. The functions are called compatibility functions. The term Z is simply a normalization factor necessary to guarantee that is a valid pdf. A node p is conditionally independent of another node q in the Markov network, given some set S of nodes, if every path from p to q passes through a node in S. Hence, representing a set of random variables by drawing the correspondent Markov graph is a meaningful pictorial way to identify the conditional dependencies occurring across the random variables. As an example, let us consider the graph reported in Figure 7.2. The graph represents conditional independencies among seven random variables. The variables are grouped into 3 cliques. In this case, for example, we can say that nodes 1–4 are statistically independent of nodes 6 and 7, conditioned to the knowledge of node 5. In this example, the joint pdf can be written as follows

(7.12)

If the product in (7.11) is strictly positive for any , we can introduce the functions

(7.13)

so that (7.11) can be rewritten in exponential form as

(7.14)

This distribution is known, in physics, as the Gibbs (or Boltzman) distribution with interaction potentials and energy.

The independence graph conveys the key probabilistic information through absent edges: If nodes i and j are not neighbors, the random variables and are statistically independent, conditioned to the other variables. This is the so called pairwise Markov property. Given a subset of vertices, factorizes as

(7.15)

where the second factor does not depend on a. As a consequence, denoting by the set of all nodes except the nodes in a and by the set of neighbors of the nodes in a, reduces to . Furthermore,

(7.16)

This property states that the joint pdf factorizes in terms that contain only variables whose vertices are neighbors.

An important example of jointly Markov random variables is the Gaussian Markov Random Field (GMRF), characterized by having a pdf expressed as in (7.14), with the additional property that the energy function is a quadratic function of the variables. In particular, a vector of random variables is a GMRF if its joint pdf can be written as

(7.17)

where is the expected value of , is the covariance matrix of and is the so called precision matrix. In this case, the Markovianity of manifests itself through the sparsity of the precision matrix. As a particular case of (7.16), the coefficient of is different from zero if and only if nodes i and j are neighbors.

Having recalled the main properties of GMRF’s, let us now go back to the problem of organizing the flow of information in a WSN aimed at deciding between two alternative hypotheses of GMRF. Let us consider for example the decision about the two alternative hypotheses:

(7.18)

(7.19)

where the sets of cliques involved in the two cases are, in general, different. The factorizations in (7.18, 7.19) suggest how to implement the computation of the LRT:

In general, different grouping may occur depending on the hypothesis. This organization represents a generalization of the distributed computation observed in the conditionally independent case, where the groups are simply singletons, i.e., sets composed by exactly one element. In that case, the clustering among nodes is only instrumental to the communication purposes, i.e., to enable spatial reuse of radio resources. In the more general Markovian case, the organization of the communication network in clusters (cells) should take into account, jointly, the grouping suggested by the cliques of the underlying dependency graph and the spatial grouping of nodes to enable concurrent transmission over the same radio resources without incurring in undesired interference. To visualize this general perspective, it is useful to have in mind two superimposed graphs, as depicted in Figure 7.3: the communication graph (top), whose vertices are the network nodes while the edges are the radio links; the dependency graph (bottom), whose vertices represent random variables, while the arcs represent statistical dependencies. Each communication cluster should incorporate at least one clique. Furthermore, in each cluster there is a relay node that is responsible for the exchange of data with nearby clusters. The whole communication network has a hierarchical tree-structure. Each node in the tree is a relay node belonging to a cluster. This node collects the measurements from the nodes belonging to its cluster, computes the potential (or the product of potentials if more cliques belong to the same cluster) and forwards this value to its relay parents. While we have depicted the two graphs as superimposed in Figure 7.3, it is useful to clarify that the nodes of the communication network are located in space and their relative position is well defined in a metric space. Conversely, the nodes of the Markov graph represent random variables for which there is no well defined notion of distance or, even if we define one, it is a notion that in general does not have a correspondence with distance in space. In other words, while the neighborhood of nodes in the top graph has to do with the concept of spatial distance among the nodes, the neighborhood of the nodes in the Markov graph has only to do with statistical dependencies. Nevertheless, it is also true that in the observation of physical entities like a temperature field, for example, it is reasonable to expect higher correlation among nearby (in the spatial sense) nodes (variables). An example of GMRF where the statistical dependencies incorporate the spatial distances was suggested in [8]. In summary, the previous considerations suggest that an efficient design of the communication network topology should keep into account the structure, if any, of dependency graph describing the observed variables. At the same time, the design of the network topology should keep into account physical constraints like the power consumption necessary to maintain the links with sufficient reliability (i.e., to insure the sufficient signal-to-noise ratio at the receiver). This is indeed an interesting line of research: How to match the network topology to the dependency graph, under physical constraints dictated by energy consumption, delay, etc. Some works have already addressed this issue. For example, in [9] the authors addressed the problem of implementing data fusion policies with minimal energy consumption, assuming a Markov random field observation model, and established the scaling laws for optimal and suboptimal fusion policies. An efficient message-passing algorithm taking into account the communication network constraints was recently proposed in [10].

a. If the graph is strongly connected, the dynamical system in(7.35)converges to a weighted consensus, for any initial state vector , i.e.,

(7.36)

where , , and . In this case, since the graph is strongly connected, is an irreducible matrix. Then, applying Gershgorin theorem [23], it can be deduced that there exists a single eigenvalue with maximum modulus. Then is a primitive nonnegative matrix and from Theorem 1 the convergence in (7.36) is straightforward. In this case, every node contributes to the final consensus value. Furthermore, the consensus value is a weighted combination of the initial observations, where the weights are the entries of the left eigenvector associated to the null eigenvalue of (or the unit eigenvalue of ).

b. If the digraph is strongly connected and balanced, i.e.,and, the systems achieves an average consensus or. In fact, for balanced graphs, is a double stochastic matrix with ;

c. If the digraphis weakly connected (WC), but not strongly connected, and it contains a forest with K strongly connected root components, the graph splits in K disjoint clusters ,⁵ and all the nodes pertaining to each cluster converge to the consensus values

(7.37)

In words, there is no single consensus, in this case, but there is a local consensus within each cluster. Different clusters typically converge to different consensus values.

d. If the digraphis composed of a single spanning tree, every node converges to the value assumed by the root node.

1. Node positions: The first randomness is related to the spatial positions of the nodes, which are in general unknown. We model the spatial distribution of nodes as a random geometric graph composed of N nodes. In graph theory, a random geometric graph (RGG) is a random undirected graph drawn on a bounded region, eg. the unit disk, generated by:

a. Placing vertices at random uniformly and independently on the region,

b. Connecting two vertices, if and only if the distance between them is inside a threshold radius , i.e., .

Several probabilistic results are known about RGG’s. In particular, as shown in [3], if N nodes are placed in a disc of unit area in and each node transmits with a power scaling with N as in (7.2), the resulting network is asymptotically connected with probability one, as .

2. Random link failures model: In a realistic communication scenario, the packets exchanged among sensors may be received with errors, because of channel fading or noise. The retransmission of erroneous packets can be incorporated into the system, but packet retransmission introduces a nontrivial additional complexity in decentralized implementations and, most important, it introduces an unknown delay and delay jitter. It is then of interest to examine simple protocols where erroneous packets are simply dropped. Random packet dropping can be taken into account by modeling the coefficient describing the network topology as random variables that assume the value 1 or 0, if the packet is correctly delivered or not, respectively. In this case, the Laplacian varies with time as a sequence of i.i.d. matrices , which can be written, without any loss of generality, as

(7.39)

where denotes the mean matrix and are i.i.d. perturbations around the mean. We do not make any assumptions about the link failure model. Although the link failures and the Laplacians are independent over time, during the same iteration, the link failures can still be spatially correlated. It is important to remark that we do not require the random instantiations of the graph be connected for all k. We only require the graph to be connected on average. This condition is captured by requiring .

3. Dithered quantization: We assume that each node encodes the message to be exchanged with the other nodes using a uniform quantizer, with a finite number of bits , defined by the following vector mapping, ,

(7.40)

where the entries of the vector , the quantization step , and the error satisfy

(7.41)

(7.42)

The quantization alphabet is

(7.43)

Conditioned on the input, the quantization error is deterministic. This induces a correlation among the quantization errors resulting at different nodes and different times, which may affect the convergence properties of the distributed algorithm. To avoid undesired error correlations, we introduce dithering, as in [30,31]. In particular, the dither added to randomize the quantization effects satisfies a special condition, namely the Schuchman conditions, as in subtractively dithered systems, [32]. Then, at every time instant k, adding to each component a dither sequence of i.i.d. uniformly distributed random variables on independent of the input sequence, the resultant error sequence becomes

(7.44)

The sequence is now an i.i.d. sequence of uniformly distributed random variables on , which is independent of the input sequence.

2.07.4.1.1 Conditionally independent observations

A case amenable for finding distributed solutions is given by the situations where the observations collected by different sensors are conditionally independent. In such a case, the joint pdf can be factorized as follows

(7.54)

where is the pdf of the vector observed by node i. Taking the of this expression, the optimization problem can be cast, equivalently, as

(7.55)

Even if the objective function to be maximized is written as a sum of functions depending each on a local observation vector, the solution of the previous problem still requires a centralized approach because the vector to be estimated is common to all the terms. A possible way to find a distributed solution to the problem in (7.55) consists in introducing an instrumental common variable and rewriting the previous problem in the following form

(7.56)

This is a constrained problem, whose Lagrangian is

(7.57)

where are the vectors whose entries are the Lagrange multipliers associated to the equality constraints in (7.56). In many cases, it is useful to introduce the so called augmented Lagrangian [45]:

(7.58)

where is a penalty parameter. Minimizing the augmented Lagrangian leads to the same solution as minimizing the original Lagrangian because any feasible vector satisfying the linear constraint yields a zero penalty. Nevertheless, there are some benefits in working with the augmented Lagrangian, namely: i) the objective function is differentiable under milder conditions than with the original Lagrangian; ii) convergence can be achieved without requiring strict convexity of the objective function (see [45] for more insight into the augmented Lagrangian method).

If the pdf’s involved in (7.58) are log-concave functions of , the problem in (7.58) is strongly convex and then it admits a unique solution and there are efficient algorithms to compute the solution. Here, we are interested in deriving decentralized solutions.

A possible method to find a distributed solution of the problem in (7.58) is the alternating direction method of multipliers (ADMM)[45]. An excellent recent review of ADMM and its applications is [46]. The application of ADMM to distributed estimation problems was proposed in [35]. The method used in [35] relied on the introduction of the so called bridge nodes. Here, we will describe methods that do not require the introduction of any special class of nodes (in principle, every node has the same functionality as any other node). This is useful to simplify the estimation method as well as network design and management.

The ADMM algorithm applied to solve (7.58) works through the following steps:

(7.59)

The first and second steps aim at minimizing the primal function (i.e., the augmented Lagrangian) over the unknown variables and , for a given value of the Lagrange multipliers’ vectors , as computed in the previous iteration.

The third step is a dual variable update, whose goal is to maximize the dual function, as in the dual ascent method. We recall that, in our case, the dual function is defined as

(7.60)

In ADMM, the dual ascent step uses a gradient ascent approach to update in order to maximize , for a given value of vectors and , with the important difference that the step size used to compute the update is exactly the penalty coefficient .

In our case, the second step can be computed in closed form as follows

(7.61)

(7.62)

(7.63)

From this formulation, we can see that the first and third steps can be run in parallel, over each node. The only step that requires an exchange of values among the nodes is the second step that requires the computation of an average value. But, as we know from previous section, the average value can be computed through a distributed consensus algorithm. The only condition for the convergence of consensus algorithm to the average value is that the graph representing the links among the nodes is connected.

The step in (7.62) can be further simplified as follows. Let us denote with the averaging operation across the nodes, i.e.,

(7.64)

Using this notation, the -update can be written as

(7.65)

Similarly, averaging over the -update yields

(7.66)

Substituting (7.65) in (7.66), it is easy to check that, after the first iteration, . Hence, using , the overall algorithm proceeds as indicated in Table 7.1.

The convergence criterion used in the steps of the algorithm is based on the relative absolute difference at two successive iterations: Given a sequence , the algorithm stops when , with a small positive value.

Equations (7.67)–(7.68) give rise to an interesting interpretation: the primal update (first equation) aims at implementing a local optimization, with a penalty related to the disagreement between the local solution and the global one; the dual update (second equation) aims at driving all the local solutions to converge to a common (consensus) value, which coincides with the globally optimal solution.

The straightforward implementation of (16.1) and (16.1) requires running, at each step k of the ADMM algorithm, a consensus algorithm. A possible alternative approach can be envisaged by reformulating the optimization problem as follows:

(7.69)

where denotes the set of node i’s neighbors. To make more clear the interaction among the nodes, it is useful to introduce the graph notation, as in previous section. Using the adjacency matrix , the previous problem can be rewritten as follows:

(7.70)

This formulation does not require the introduction of the instrumental variable . We keep enforcing the constraint that all the local estimates converge to the same value. However, the penalty is now formulated as the disagreement between the local estimates. From consensus algorithm, we know that nulling the disagreement is equivalent to forcing all the vectors to reach the same value if the graph describing the interactions among the nodes is connected. Hence, if the network is connected, at convergence, the disagreement goes to zero and there is no bias resulting from the introduction of the disagreement penalty.

The formulation in (7.70) is more amenable for an implementation that does not require, at any step of the algorithm, the convergence of consensus algorithms. In fact, applying ADMM to the solution of (7.70) yields the algorithm described in Table 7.2.

Some examples of applications are useful to grasp the main features of these algorithms.

2.07.4.1.2 Distributed ML estimation under Gaussian noise

Let us consider the common situation where the measured vector is related to the parameter vector , with , through a linear observation model, as:

(7.73)

where and is a vector of jointly Gaussian random variables with zero mean and covariance matrix , i.e., .

In such a case, algorithm A.1 in (7.67) simplifies as the first step of (7.67) can be expressed in closed form

(7.74)

The two updates can be computed in parallel by all the nodes, after having computed the average values through the consensus algorithm.

Alternatively, algorithm A.2 becomes

(7.75)

In this case, there is no need of running the consensus algorithm for every iteration. Some numerical results are useful to compare the methods. As an example, we considered a connected network composed of sensors. We set and assumed an observation vector of size . In Figure 7.6 we report the estimates , for , versus the iteration index m, for the two algorithms A.1 (left plot) and A.2 (right plot). The iteration index m includes also the iterations necessary for the consensus algorithm to converge within a prescribed accuracy (in this case, we stopped the consensus algorithm as soon as the absolute difference between two consecutive updates is below of for all the nodes). In both figures, we report, as a benchmark, the maximum likelihood estimate (horizontal x-marked line) achievable by a centralized node that knows all the observation vectors and all the model parameters, i.e., . From Figure 7.6, we can see that the estimates obtained with both methods converge to the optimal ML estimates.

In the specific case where the observation model is as in (7.73), with additive Gaussian noise, and the noise vectors pertaining to different sensors are mutually uncorrelated, the globally optimal ML estimate is

(7.76)

This formula is a vector weighted sum of the observations. Recalling that consensus algorithms, if properly initialized, can be made to converge to a weighted sum of the initial states, we can use the consensus algorithm directly to compute the globally optimal ML estimate through a totally distributed mechanism. In particular, in this case, the consensus algorithm proceeds as in Table 7.3.

Using again the basic properties of consensus algorithm, if the graph is connected and the step size is sufficiently small, the iterations in (7.77) converge to the globally optimal estimate (7.76).

2.07.4.1.3 Distributed Bayesian estimation under Gaussian noise and Laplacian prior

Let us consider now the case where the parameter vector is a random vector with known prior probability density function. Following a Bayesian approach, as in (7.50), the practical difference is that in such a case the objective function must include a term depending on the prior probability. Let us consider, for instance, the interesting case where the observation is Gaussian, as in the previous example, and the prior pdf is Laplacian, i.e.,

(7.78)

with , where denotes the norm of vector . In this case, the problem to be solved is the following

(7.79)

where denotes the weighted norm of , i.e., .

Interestingly, this formulation coincides with the formulation resulting from having no prior pdf, but incorporating an norm in order to drive the solution towards a sparse vector. This is the so called least-absolute shrinkage and selection operator (lasso) method [47]. A distributed algorithm to solve a linear regression problem with sparsity constraint was proposed in [48]. Here we provide a similar approach, with the important difference that, in each iteration, the update is computed in closed form. A decentralized solution can be found by reformulating the problem as follows

(7.80)

Using the ADMM approach, the algorithm proceeds through the following updates

(7.81)

The second equation can also be expressed in closed form. Moreover, defining the vector threshold function as the vector whose entries are obtained by applying the scalar thresholding function to each element of vector , where

(7.82)

the overall algorithm is as in Table 7.4.

As a numerical example, in Figure 7.7 we report the behavior of the estimated variable obtained using Algorithm A.4 versus the iteration index m, which includes the convergence times of two consensus algorithms in the equation (7.84).

The example refers to a network of nodes, using . The horizontal x-marked line represents the centralized optimal solution. The parameter vector of this example has two components, one of which has been set to zero to test the capability to recover the sparsity. We can notice from Figure 7.7 that, as expected, the algorithm converges to the globally optimal values.

To show the impact of the penalty coefficient on the sparsity of the estimated vector, in Figure 7.8 we have reported the average mean square estimation error versus the coefficient , defined as the fraction of zeros entries in the vector to be estimated, for different values of . It can be noted from Figure 7.8 that for the optimal solution is independent by and it coincides with the optimal (centralized) ML solution. Furthermore, we can observe that, as and increase, the average estimation error decreases thanks to the recovering sparsity property of the ADMM approach with the lasso constraint.

2.07.4.1.4 Distributed recursive least square estimation with sparsity constraint

In some applications, the parameters to be estimated may be changing over time. In these cases, it is more advisable to adopt recursive procedure rather than the batch approach followed until now. We show now how to obtain a distributed recursive least square (RLS) estimation incorporating a sparsity constraint.

Let us assume a linear observation model

(7.86)

where denotes the observation taken by node i at time is a known, possibly time-varying, mixing matrix and is the observation noise, supposed to have zero mean and covariance matrix .

In RLS estimation with a sparsity constraint, the goal is to find the parameter vector , at each time instant n, that minimizes the following objective function

(7.87)

where is a forgetting factor used to weight more the most recent observations with respect to the older ones. The coefficient weights the importance of the sparsity constraint.

Proceeding as in the previous examples, a distributed solution can be found by formulating the problem, at each time n, as a constrained problem incorporating an instrumental variable to force all the nodes to converge to a common estimate. The problem can be made explicit as

(7.88)

Again, the solution can be achieved by applying ADMM and the result is given by the algorithm described in Table 7.5

As before, the only step requiring the interaction among the nodes is a consensus algorithm to be run to compute the averages appearing in equation (7.89).

To test the convergence of Algorithm A.5, we considered a possible application to cooperative sensing for cognitive radio. We assumed the presence of a macro base station transmitting using a multicarrier scheme. We considered for simplicity of representation four channels, but the method can be easily extended to a larger number of channels. The sensing nodes aim to recover the activity of the macro transmitter, represented by a vector composed of four entries, one for each channel. To improve the accuracy of the local estimation, the sensors cooperate with each other by running Algorithm A.5. At some time, the activity level switches from on to off or viceversa. As an example, in Figure 7.9 we report the four parameters to be estimated, indicated by the unmarked lines. At time , the parameters switch to test the tracking capability of the proposed method.

In Figure 7.9 we draw also the estimated parameters for versus the current observation index n. We used and two values of the sparsity coefficient: and . We can notice from Figure 7.9 that the method is able to track the true parameters. It is also interesting to see that, as the penalty coefficient increases, the zero coefficients are estimated with greater accuracy. Conversely, the positive coefficients are recovered with a slightly larger bias.

To evaluate the impact of the forgetting factor on the accuracy and tracking capability of the distributed RLS method, in Figure 7.10 we reported the estimated parameters. using and , having set . It can be noted that, as increases, the larger memory of the filter yields more accurate estimates. At the same time, having a larger memory implies slower time to reaction to the parameter switch, as evidenced in Figure 7.10.

For any given forgetting factor , the only possibility to improve the estimation accuracy is to have more nodes sensing a common macro base station. As an example, in Figure 7.11 we report the behavior of the estimates obtained with different number of nodes, for a forgetting factor . We can notice that, as expected, increasing the number of nodes, the estimation accuracy increases as well. This reveals a trade-off between forgetting factor (time memory) and number of nodes involved in cooperative sensing.

2.07.4.1.5 Distributed parameter estimation in spatially correlated observations

So far, we have analyzed the case of conditionally independent observations. Let us consider now the case where the observation noise is spatially correlated. More specifically, we assume here the following observation model, for each sensor

(7.90)

where the noise variables are jointly Gaussian with zero mean and covariance matrix , or precision matrix . Furthermore, we assume that is a Gaussian Markov random field, so that the precision matrix is typically a sparse matrix. The joint pdf of the observation vector can then be written as in (7.17), i.e.,

(7.91)

where can be rewritten as follows

(7.92)

with , and

(7.93)

As in the previous cases, also here a decentralized solution can be reached by formulating the problem as the minimization of the augmented Lagrangian

(7.94)

subject to . Applying the ADMM algorithm to this case, we get the following algorithm

(7.95)

It is important to notice that, in this case, even if the global problem concerning the minimization of the augmented Lagrangian in (7.94) is certainly convex, the local problem in (7.95) is not necessarily convex because there is no guarantee that the term is a positive definite function. Nevertheless, the quadratic penalty present in (7.95) can make every local problem in (7.95) convex. At the same time, at convergence the penalty goes to zero and thus it does not induce any undesired bias on the final result.

The first step in (7.95) can be made explicit, so that the algorithm assumes the form described in Table 7.6.

As an example, in Figure 7.12 we report the estimation versus the cumulative iteration index m that includes the consensus steps and the iterations over k. The results refer to a connected network with nodes; has been chosen equal to 10 to guarantee that every local problem is convex. It can be noticed from Figure 7.12 that the distributed solution converges to the optimal centralized solution (horizontal x-marked line).