# Distributed Function Calculation over Noisy Networks

Authors: Zhidun Zeng; Xin Yang; Ze Zhang; Xiaoyu Mo; Zhiqiang Long
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

Considering any connected network with unknown initial states for all nodes, the nearest-neighbor rule is utilized for each node to update its own state at every discrete-time step. Distributed function calculation problem is defined for one node to compute some function of the initial values of all the nodes based on its own observations. In this paper, taking into account uncertainties in the network and observations, an algorithm is proposed to compute and explicitly characterize the value of the function in question when the number of successive observations is large enough. While the number of successive observations is not large enough, we provide an approach to obtain the tightest possible bounds on such function by using linear programing optimization techniques. Simulations are provided to demonstrate the theoretical results.


---

## Body

## 1. Introduction

Consider a network where each nodei has the knowledge of its initial value x0[i]∈R. The objective for each node is to compute some function relating to the initial values of all nodes, that is, x01,x02,…,x0[n], under the constraint that each node transmits its value to its neighbors and updates its own value with some protocol at each time-step. Such problem is called distributed function calculation (DFC) and it has received considerable attention in recent years [1, 2] due to the development of distributed networks and systems.Various protocols are designed to achieve such a goal, for example, the nearest-neighbor rule [3]. Moreover, it leads to a well-studied field in control theory, distributed consensus [3–5] which can be viewed as a special case of this DFC problem; some model predictive control (MPC) methods are proposed to solve the consensus problem [6–8]. When the observations of each node are noise-free, [2] shows that, instead of requiring asymptotic convergence, finite observations are enough to compute a predefined function. Reference [9] shows that consensus function calculation can be performed in a minimal number of time-steps, and, furthermore, the minimal number of time-steps can be fully characterized algebraically and graphically [10].When it comes to the noisy network where each node only obtains a noisy (or uncertain) measurement of its neighbors’ values (e.g., the transmission channel between nodes is noisy (bounded noise) and quantized (given a certain quantization scheme)), the estimation on initial value becomes a very challenging problem. It has been shown in [11] that each node can obtain an unbiased estimate of any desired linear function as a linear combination of the noisy values received from its neighbors, along with its own values, using only the first-order statistics of the noise. If the second order statistics of the noise are also known, the variance of the estimation error can be minimized distributedly by refining its estimate of the linear function. Quantization and other communication issues are addressed and analyzed in [12].Instead of stimulating the network with different initial conditions [11] to characterize statistical properties, the focus of this paper is on what the best estimation is on the initial condition of the network given a number of successive observations. The main contribution (Section 3) is to propose an algorithm to solve initial values of all nodes with uncertain output measurements, for example, outputs with bounded channel noises and quantization, over a finite (minimal) estimation horizon. Minimal number of time-steps is characterized to fully recover the initial states of all nodes from merely the information of a randomly chosen node and its neighbors.Furthermore, when minimal number of time-steps is not satisfied, we propose an approach to solve the upper and lower bounds on the initial values of all the nodes. These bounds are the tightest possible given the system model, output measurements, and the rough bounds on the unknown initial state. After obtaining the exact value or the tightest bounds, any exact value or bounds of objective function related tox0 can be therefore computed. Simulations about undirected and directed networks are given in Section 4 to verify the theoretical results. Finally, Section 5 summarizes this paper.The notation is fairly standard. For a matrixA∈RM×N, A[i,j]∈R denotes the element in the ith row and jth column. For a column vector α∈RN, α[i] denotes its ith element. Similarly for a row vector β∈R1×N, β[i] denotes its ith element. We denote erT=[0,…,0,1rth,0,…,0]∈R1×N. For vectors x,y∈Rn, x<y and x≤y denote element-wise inequalities. IN denotes the identity matrix with dimension N.


## 2. Problem Formulation

The underlying weighted direct graph of the considered network is denoted byG=V,E,W, where V=ν1,…,νn is the set of nodes, E⊂V×V is the set of edges, and the adjacency matrix W=W[i,j]i,j=1,…,n∈N≥0n×n, with nonnegative element W[i,j]=1 when there is a link from i to j and equaling zero when there is no link from i to j. Let x[i]∈R denote the state of node i, which might represent a physical quantity such as attitude, position, temperature, voltage, and so forth.Considering the classical protocol, the dynamics of a network of discrete-time integrator agents is defined by(1)xik+1=∑j=1ndijkxjk,i=1,…,n,where k∈0,1,… is the discrete-time index; dij[k] is the (i,j) entry of a row-stochastic matrix D=[dij]∈Rn×n at the discrete-time index k with the additional assumption that dij[k]>0 for all i=1,…,n and dij[k]>0,∀i≠j, if (j,i)∈εn and dij[k]=0 otherwise. Intuitively, the information state of each vehicle is updated as the weighted average of its current state and the current states of its neighbors. Equation (1) can be written in matrix form as (2)xk+1=Dnk⊗Imxk.Definition 1 (DFC for theith node [2]).
Letfi be a function of the initial values; that is, fi(x0[1],x0[2],…,x0[n]) is calculable by node i if it can be calculated by node i after running iteration (2) for a sufficiently large number of time-steps.Remark 2.
In particular, we are interested in distributed linear function calculation; that is,f is linear. The distributed average consensus problem [4] can be categorized into this.Definition 3 (distributed asymptotic consensus [13]).
System (2) is said to asymptotically achieve distributed consensus if limk→∞xk=1cTx0, where 1 is the column vector with all components equal to 1 and cT is some constant row vector. In other words, the values of all nodes converge to the same linear combination of the initial node values cTx0.The set of all computable linearfi is characterized and the algorithm for each node i to compute its correspondent fi is proposed in [2] for noiseless case. However, there could be noise, uncertainty caused by quantizations, both at the process and at the observation. By taking uncertainty into account, the system can be generalized and modeled as a discrete-time network system of the form(3)xk+1=Axk+Bddk,yk=Cxk+Dddk,for k∈N, where N≔0,1,…,N-1 is the estimation horizon and xk∈Rn, yk∈Rny, and dk∈Rnd are the state, output, and noise vectors (the word “noise” here has broader meanings, e.g., noise, quantization error, and uncertainty), respectively. A=Pϵ and Bd∈Rn×nd are the interconnection matrix and the transmission channel noise and quantization distribution matrix, respectively, while Dd∈Rny×nd are the output channel disturbance distribution matrices. C is (degi+1)×n matrix (where degi is the degree of node i) with a single 1 at each row denoting the information for the node i: its own and neighbors’ values at each time-step.


## 3. Solution to Robust DFC Problem

### 3.1. Output Model

Assuming that each node in the network has some memory and computational ability, this section proposes a new scheme for each node to solve the DFC problem subject to bounded channel noises by using a system model in (3) together with output measurements over a finite estimation horizon. Firstly, a necessary and sufficient condition for each node obtaining the exact initial state value is derived. It is shown that when this condition is satisfied, the initial state value can be easily solved by doing matrix calculations using the local observations of each node.Then, for the case in which the exact calculation of initial state value is not possible (i.e., the necessary and sufficient condition does not hold), an approach to estimate the initial condition of network is proposed. This approach computes upper and lower bounds on the initial state value by using Linear Programming (LP) optimization techniques and these bounds are the tightest possible given the network model, available output measurements, and the a priori rough bounds on the initial state and noises.The first problem of exact initial state calculation is formulated as follows.Problem 1.
With the system dynamics defined as in (3), assume that y0,y1,…,yN-1 are given and (A1)
(A,C) is observable;(A2)
ny>nd.Find the sufficient and necessary condition such that the exact value of the initial condition x0 can be solved for any d.Here, assume that the successive observationsyk are available for, say node i (we ignore the superscript i for notational convenience), all k∈N. For the estimation horizon N, let (4)x=x0x1⋮xN-1,y=y0y1⋮yN-1,d=d0d1⋮dN-1,d_=d_0d_1⋮d_N-1,d¯=d¯0d¯1⋮d¯N-1,where d∈RNd, y∈RNy, Nd=N×nd, and Ny=N×ny. Using an iterative computation, the system algebraic formulation is described as(5)xN=IA⋮AN-1︷Ax0+00⋯0Bd0⋯0⋮⋮⋱⋮AN-2BdAN-3Bd⋯0︷Bdd,y=CCA⋮CAN-1︷Cy0x0+Dd0⋯0CBdDd⋯0⋮⋮⋱⋮CAN-2BdCAN-3Bd⋯Dd︷Dydd.For the reason for simplicity, the output over the estimation horizon N is represented by (6)y=Cy0x0+Dydd.


### 3.2. Exact Solution to DFC

We will have Theorem4 to solve this problem.Theorem 4.
Let all data and assumptions be as given in Problem1; then the exact value of the initial state x0 can be solved from (6) for any disturbance d if and only if there exists U∈RNy×m which spans the null space of DydT such that(7)rank⁡UTCy0=n.Proof.
It is seen from (6) that x0 can be solved for all d if and only if there always exists M∈Rn×Ny such that (8)MCy0Dyd=In0n×Nd.Note that all M in (8) satisfying MDyd=0n×Nd are given by M=ZUT, where Z∈Rn×m is a free variable and UT spans the null space of Dyd. Then condition (8) is satisfied if and only if there always exists Z such that (9)MCy0=ZUTCy0=Inis satisfied. Note that there always exists Z which is the left inverse of UTCy0 and can be solved from (9) if and only if UTCy0 has full column rank, so that x0=ZUTy, where Z and UT can be obtained by using singular value decomposition [14].Remark 5.
The idea of Theorem4 is that even if the noise/quantization is unknown, we can still cancel the noise/quantization effect by using simple matrix calculations such that finding M satisfies (8).Remark 6.
It is noted thatUT∈Rm×Ny has rank m which increases as the horizon length N increases and that Cy0 has full column rank n as long as N is larger than the observability index of the pair (A,C). Therefore, condition (7) is satisfied if and only if N is large enough such that both UT and Cy0 have rank larger than or equal to n.Corollary 7.
Let all data and assumptions be as given in Theorem4. Assume that Dd has full column rank and take v as the observability index of the pair (A,C); then the exact value of the initial state x0 can be solved from (6) for any disturbance d if and only if the measurement horizon length is (10)N≥max⁡v,nny-nd.Proof.
D
d has full column rank, which implies Dyd always has full column rank. So there exists U∈RNy×(Ny-Nd) with rank Ny-Nd which spans the null space of DydT. Note that rank⁡[UTCy0]=min⁡(Ny-Nd),rank⁡(Cy0); hence (7) is satisfied if and only if Ny-Nd=N×(ny-nd)≥n and N≥v.Theorem4 gives the sufficient and necessary condition which ensures the exact value of x0 can be calculated. However, it may not be always implementable due to the limitation of the number of successive observations in practical network systems. Hence, it is useful to investigate the techniques for estimating initial state when output measurements are not sufficient. The rest of this section studies the case when condition (7) is not satisfied. A state estimation approach is proposed by which the initial state x0 is estimated by solving its tightest upper and lower bounds. LP optimization techniques are used to obtain the bounds and the cases for upper and lower bounds which are dealt with separately.


### 3.3. Optimal Bounds for DFC

Here, assume that the rough upper and lower boundsx_r, x¯r and d_k, d¯k on the initial state and disturbances, respectively, are available and have the form (11)x_r≤x0≤x¯r,d_k≤dk≤d¯k.Letx0[i] represent the ith element of the initial state values x0 and x¯0i; x_0i stand for the tightest upper and lower bounds on x0i, where i=1,2,…,n, given the system model, output measurements over the estimation horizon, and the a priori rough bounds on x0 and d; then the problem formulation for obtaining tightest upper and lower bounds on x0 is described as follows.Problem 2.
Let the system dynamics be as defined in (3). Assume that the rough upper and lower bounds on x0 and d are known and that y0,y1,…,yN-1 are given. Find the upper and lower bounds x¯0i and x_0i, for i=1,2,…,n, defined by (12)min⁡x¯0is.t.x¯0i≥x0ix_r≤x0≤x¯rd_≤d≤d¯y=Cy0x0+Dyddygiven,min⁡x_0is.t.x_0i≤x0ix_r≤x0≤x¯rd_≤d≤d¯y=Cy0x0+Dyddygiven.The following theorem shows that evaluating the upper bound on eachx0[i] can be obtained by solving an LP problem. Note that we use boldface to denote variables in the optimization.Theorem 8.
Let all data be as defined previously andR+m≔v∈Rm:v≥0. Then x0i≤x¯0i for i=1,2,…,n, if and only if there exist μ¯i,μ_i∈R+n, τ¯i,τ_i∈R+N×nd, and λi∈RN×ny such that (13)μ¯i-μ_i+Cy0Tλi=ei,τ¯i-τ_i+DydTλi=0,x¯0i≥μ¯iTx¯r-μ_iTx_r+τ¯iTd¯-τ_iTd_+λiTy.Proof.
As it can be seen thatx0[i]=eiTx0, then a manipulation verifies that the following identity (14)x0i-x¯0i=-μ¯iTx¯r-x0-μ_iTx0-x_r-τ¯iTd¯-d-τ_iTd-d_-λiTy-Cy0x0-Dydd-x0Td1Lx¯0i,μ¯i,μ_i,τ¯i,τ_i,λix0d1is valid for all μ¯i,μ_i∈Rn, τ¯i,τ_i∈RN×nd, and λi∈RN×ny, where(15)Lx¯0i,μ¯i,μ_i,τ¯i,τ_i,λi=0⋆⋆00⋆12μ¯iT-μ_iT+λiTCy0-eiT12τ¯iT-τ_iT+λiTDydμ_iTx_r-μ¯iTx¯r+τ_iTd_-τ¯iTd¯-λiTy+x¯0i,where ⋆ denotes terms readily inferred from symmetry.
It follows that a sufficient condition forx0[i]≤x¯0i subject to x_r≤x0≤x¯r, d_≤d≤d¯, and y=Cy0x0+Dydd is (16)Lx¯1i,μ¯i,μ_i,τ¯i,τ_iλi≥0,μ¯i,μ_i,τ¯i,τ_i≥0.That the condition is necessary follows from Farkas’ Lemma [15]. Note that evaluating x¯0i subject to (16) is equivalent to solving the LP problem as follows: (17)x¯0i=min⁡x¯rT-x_rTd¯T-d_TyTμ¯iμ_iτ¯iτ_iλis.t.μ¯i-μ_i+Cy0Tλi=eiτ¯i-τ_i+DydTλi=0μ¯i,μ_i,τ¯i,τ_i≥0.Therefore, the upper bound on each x0[i] for i=1,2,…,n can be computed by solving (17).Similarly, the next theorem is proposed to solve the optimal lower bound on eachx0[i] for i=1,2,…,n. Since the proof can be obtained by following that of Theorem 8, it is omitted.Theorem 9.
Let all data be as defined above andR-m:=v∈Rm:v≤0. Then x_0i≤x0[i] for i=1,2,…,n if and only if there exist μ¯i,μ_i∈R-n, τ¯i,τ_i∈R-N×nd, and λi∈RN×ny such that L(x_0i,μ¯i,μ_i,τ¯i,τ_i,λi)⪯0, where L(·,·,·,·,·,·) is defined in (16). Similarly to (17), evaluating the tightest lower bound on x0[i] is equivalent to solving the following LP problem: (18)μ¯i-μ_i+Cy0Tλi=ei,τ¯i-τ_i+DydTλi=0,x_0i≤μ¯iTx¯r-μ_iTx_r+τ¯iTd¯-τ_iTd_+λiTy.Remark 10.
From Theorems8 and 9, it can be seen that sufficient and necessary conditions for x¯0i and x_0i to be upper and lower bounds on x0[i] are given in the form of the LP conditions (17) and (18), respectively. Then the tightest bounds on the initial state are obtained by solving 2×n LP problems.Remark 11.
Since LP problems can be easily solved, another benefit of the proposed method is that we can use it as a recursive online implementation; that is, at each time-stepk, node i uses Theorems 8 and 9 to compute the upper and lower bounds on the initial state x0 until condition (7) is satisfied, in which case the initial conditions can be fully recovered.


## 3.1. Output Model

Assuming that each node in the network has some memory and computational ability, this section proposes a new scheme for each node to solve the DFC problem subject to bounded channel noises by using a system model in (3) together with output measurements over a finite estimation horizon. Firstly, a necessary and sufficient condition for each node obtaining the exact initial state value is derived. It is shown that when this condition is satisfied, the initial state value can be easily solved by doing matrix calculations using the local observations of each node.Then, for the case in which the exact calculation of initial state value is not possible (i.e., the necessary and sufficient condition does not hold), an approach to estimate the initial condition of network is proposed. This approach computes upper and lower bounds on the initial state value by using Linear Programming (LP) optimization techniques and these bounds are the tightest possible given the network model, available output measurements, and the a priori rough bounds on the initial state and noises.The first problem of exact initial state calculation is formulated as follows.Problem 1.
With the system dynamics defined as in (3), assume that y0,y1,…,yN-1 are given and (A1)
(A,C) is observable;(A2)
ny>nd.Find the sufficient and necessary condition such that the exact value of the initial condition x0 can be solved for any d.Here, assume that the successive observationsyk are available for, say node i (we ignore the superscript i for notational convenience), all k∈N. For the estimation horizon N, let (4)x=x0x1⋮xN-1,y=y0y1⋮yN-1,d=d0d1⋮dN-1,d_=d_0d_1⋮d_N-1,d¯=d¯0d¯1⋮d¯N-1,where d∈RNd, y∈RNy, Nd=N×nd, and Ny=N×ny. Using an iterative computation, the system algebraic formulation is described as(5)xN=IA⋮AN-1︷Ax0+00⋯0Bd0⋯0⋮⋮⋱⋮AN-2BdAN-3Bd⋯0︷Bdd,y=CCA⋮CAN-1︷Cy0x0+Dd0⋯0CBdDd⋯0⋮⋮⋱⋮CAN-2BdCAN-3Bd⋯Dd︷Dydd.For the reason for simplicity, the output over the estimation horizon N is represented by (6)y=Cy0x0+Dydd.


## 3.2. Exact Solution to DFC

We will have Theorem4 to solve this problem.Theorem 4.
Let all data and assumptions be as given in Problem1; then the exact value of the initial state x0 can be solved from (6) for any disturbance d if and only if there exists U∈RNy×m which spans the null space of DydT such that(7)rank⁡UTCy0=n.Proof.
It is seen from (6) that x0 can be solved for all d if and only if there always exists M∈Rn×Ny such that (8)MCy0Dyd=In0n×Nd.Note that all M in (8) satisfying MDyd=0n×Nd are given by M=ZUT, where Z∈Rn×m is a free variable and UT spans the null space of Dyd. Then condition (8) is satisfied if and only if there always exists Z such that (9)MCy0=ZUTCy0=Inis satisfied. Note that there always exists Z which is the left inverse of UTCy0 and can be solved from (9) if and only if UTCy0 has full column rank, so that x0=ZUTy, where Z and UT can be obtained by using singular value decomposition [14].Remark 5.
The idea of Theorem4 is that even if the noise/quantization is unknown, we can still cancel the noise/quantization effect by using simple matrix calculations such that finding M satisfies (8).Remark 6.
It is noted thatUT∈Rm×Ny has rank m which increases as the horizon length N increases and that Cy0 has full column rank n as long as N is larger than the observability index of the pair (A,C). Therefore, condition (7) is satisfied if and only if N is large enough such that both UT and Cy0 have rank larger than or equal to n.Corollary 7.
Let all data and assumptions be as given in Theorem4. Assume that Dd has full column rank and take v as the observability index of the pair (A,C); then the exact value of the initial state x0 can be solved from (6) for any disturbance d if and only if the measurement horizon length is (10)N≥max⁡v,nny-nd.Proof.
D
d has full column rank, which implies Dyd always has full column rank. So there exists U∈RNy×(Ny-Nd) with rank Ny-Nd which spans the null space of DydT. Note that rank⁡[UTCy0]=min⁡(Ny-Nd),rank⁡(Cy0); hence (7) is satisfied if and only if Ny-Nd=N×(ny-nd)≥n and N≥v.Theorem4 gives the sufficient and necessary condition which ensures the exact value of x0 can be calculated. However, it may not be always implementable due to the limitation of the number of successive observations in practical network systems. Hence, it is useful to investigate the techniques for estimating initial state when output measurements are not sufficient. The rest of this section studies the case when condition (7) is not satisfied. A state estimation approach is proposed by which the initial state x0 is estimated by solving its tightest upper and lower bounds. LP optimization techniques are used to obtain the bounds and the cases for upper and lower bounds which are dealt with separately.


## 3.3. Optimal Bounds for DFC

Here, assume that the rough upper and lower boundsx_r, x¯r and d_k, d¯k on the initial state and disturbances, respectively, are available and have the form (11)x_r≤x0≤x¯r,d_k≤dk≤d¯k.Letx0[i] represent the ith element of the initial state values x0 and x¯0i; x_0i stand for the tightest upper and lower bounds on x0i, where i=1,2,…,n, given the system model, output measurements over the estimation horizon, and the a priori rough bounds on x0 and d; then the problem formulation for obtaining tightest upper and lower bounds on x0 is described as follows.Problem 2.
Let the system dynamics be as defined in (3). Assume that the rough upper and lower bounds on x0 and d are known and that y0,y1,…,yN-1 are given. Find the upper and lower bounds x¯0i and x_0i, for i=1,2,…,n, defined by (12)min⁡x¯0is.t.x¯0i≥x0ix_r≤x0≤x¯rd_≤d≤d¯y=Cy0x0+Dyddygiven,min⁡x_0is.t.x_0i≤x0ix_r≤x0≤x¯rd_≤d≤d¯y=Cy0x0+Dyddygiven.The following theorem shows that evaluating the upper bound on eachx0[i] can be obtained by solving an LP problem. Note that we use boldface to denote variables in the optimization.Theorem 8.
Let all data be as defined previously andR+m≔v∈Rm:v≥0. Then x0i≤x¯0i for i=1,2,…,n, if and only if there exist μ¯i,μ_i∈R+n, τ¯i,τ_i∈R+N×nd, and λi∈RN×ny such that (13)μ¯i-μ_i+Cy0Tλi=ei,τ¯i-τ_i+DydTλi=0,x¯0i≥μ¯iTx¯r-μ_iTx_r+τ¯iTd¯-τ_iTd_+λiTy.Proof.
As it can be seen thatx0[i]=eiTx0, then a manipulation verifies that the following identity (14)x0i-x¯0i=-μ¯iTx¯r-x0-μ_iTx0-x_r-τ¯iTd¯-d-τ_iTd-d_-λiTy-Cy0x0-Dydd-x0Td1Lx¯0i,μ¯i,μ_i,τ¯i,τ_i,λix0d1is valid for all μ¯i,μ_i∈Rn, τ¯i,τ_i∈RN×nd, and λi∈RN×ny, where(15)Lx¯0i,μ¯i,μ_i,τ¯i,τ_i,λi=0⋆⋆00⋆12μ¯iT-μ_iT+λiTCy0-eiT12τ¯iT-τ_iT+λiTDydμ_iTx_r-μ¯iTx¯r+τ_iTd_-τ¯iTd¯-λiTy+x¯0i,where ⋆ denotes terms readily inferred from symmetry.
It follows that a sufficient condition forx0[i]≤x¯0i subject to x_r≤x0≤x¯r, d_≤d≤d¯, and y=Cy0x0+Dydd is (16)Lx¯1i,μ¯i,μ_i,τ¯i,τ_iλi≥0,μ¯i,μ_i,τ¯i,τ_i≥0.That the condition is necessary follows from Farkas’ Lemma [15]. Note that evaluating x¯0i subject to (16) is equivalent to solving the LP problem as follows: (17)x¯0i=min⁡x¯rT-x_rTd¯T-d_TyTμ¯iμ_iτ¯iτ_iλis.t.μ¯i-μ_i+Cy0Tλi=eiτ¯i-τ_i+DydTλi=0μ¯i,μ_i,τ¯i,τ_i≥0.Therefore, the upper bound on each x0[i] for i=1,2,…,n can be computed by solving (17).Similarly, the next theorem is proposed to solve the optimal lower bound on eachx0[i] for i=1,2,…,n. Since the proof can be obtained by following that of Theorem 8, it is omitted.Theorem 9.
Let all data be as defined above andR-m:=v∈Rm:v≤0. Then x_0i≤x0[i] for i=1,2,…,n if and only if there exist μ¯i,μ_i∈R-n, τ¯i,τ_i∈R-N×nd, and λi∈RN×ny such that L(x_0i,μ¯i,μ_i,τ¯i,τ_i,λi)⪯0, where L(·,·,·,·,·,·) is defined in (16). Similarly to (17), evaluating the tightest lower bound on x0[i] is equivalent to solving the following LP problem: (18)μ¯i-μ_i+Cy0Tλi=ei,τ¯i-τ_i+DydTλi=0,x_0i≤μ¯iTx¯r-μ_iTx_r+τ¯iTd¯-τ_iTd_+λiTy.Remark 10.
From Theorems8 and 9, it can be seen that sufficient and necessary conditions for x¯0i and x_0i to be upper and lower bounds on x0[i] are given in the form of the LP conditions (17) and (18), respectively. Then the tightest bounds on the initial state are obtained by solving 2×n LP problems.Remark 11.
Since LP problems can be easily solved, another benefit of the proposed method is that we can use it as a recursive online implementation; that is, at each time-stepk, node i uses Theorems 8 and 9 to compute the upper and lower bounds on the initial state x0 until condition (7) is satisfied, in which case the initial conditions can be fully recovered.


## 4. Simulation

### 4.1. Directed Network Example

Next, we consider a directed network with14 nodes in Figure 1. Its corresponding adjacency matrix W and the underlying graphical representation are shown as follows:(19)W=0010001001000000000000100101100010000010010000000110011010100000011010000100000000100010000000000100001000101010010100010001001000100000001000001001100001010101000000000001110101000001100010001000.Take the sampling time to be ϵ=1/6; then the system matrices are obtained as follows:(20)A=36016000160016000003600000016001601616026016000001600160002600016160016160160160160000161601600001604600000016000160004600000016000016002616016016001601600016260016001600016000036001600000160016160260016016016016000003600000161616016016001600161600016000160026,C=1000000000000001000000000000001000000000000001000000000000001000000000000001000000000000001000000000000001000000,B=014×6,D=100000010000001000000100000010000001111111111111.We randomly choose an initial state(21)x0=-0.4257-0.7771-0.7910.00510.2835-0.4187-0.05550.86080.29720.7322-0.6673-0.0970.7319-0.9849Tto stimulate the system. It is assumed that there are 6 transmission noises between nodes which are zero-mean bounded from [-1,1]. Also, assume that the rough upper and lower bounds on the initial state x¯r and x_r are 1 and -1, respectively. From (7), it can be seen that the minimal number of steps N for direct calculation on x0 is 7.Figure 1
Underlying topology of the considered graph consisted of14 nodes.Therefore, in the scenario that there are enough output measurements over the horizon lengthN=7, condition (7) is satisfied. So there exists M satisfying (8) such that x0=My. By taking the matrix calculation, the initial state x0 is recovered.For the scenario that there are only output measurements over the horizon lengthN=6, the full recovery of x0 is not possible. By using the method given in Theorems 8 and 9, the tightest upper and lower bounds on x0 are solved and given as follows:(22)x_0=-0.5163-0.8193-0.9824-0.09470.2403-0.5145-0.0950.82130.08870.6245-0.7106-0.21410.6975-1.0000T,x¯0=-0.2774-0.6978-0.71710.22260.3036-0.3730.00320.91950.37400.8097-0.5759-0.05260.8341-0.8897T.As it can be seen that the difference between the upper and lower bounds is small, x0 is well-estimated.By using the exact value or the tightest bounds forx0, any exact value or bounds of objective function related to x0 can be therefore obtained. For example, here, the true average consensus value of this system, that is, 1/14(∑i=114‍x0[i]), is -0.0933, while the bounds on it obtained from our method are [-0.1768,-0.0083] when N=6 which are very tight with respect to the noise level ±1.Figure2 illustrates the bounds on the average consensus value as the horizon of output measurements reaches 7 in which the exact average consensus value is solved. It is shown that the bounds become tighter and tighter as more and more measurement information becomes available.Figure 2
Bounds on the average consensus value using output measurements of different horizon lengths.


## 4.1. Directed Network Example

Next, we consider a directed network with14 nodes in Figure 1. Its corresponding adjacency matrix W and the underlying graphical representation are shown as follows:(19)W=0010001001000000000000100101100010000010010000000110011010100000011010000100000000100010000000000100001000101010010100010001001000100000001000001001100001010101000000000001110101000001100010001000.Take the sampling time to be ϵ=1/6; then the system matrices are obtained as follows:(20)A=36016000160016000003600000016001601616026016000001600160002600016160016160160160160000161601600001604600000016000160004600000016000016002616016016001601600016260016001600016000036001600000160016160260016016016016000003600000161616016016001600161600016000160026,C=1000000000000001000000000000001000000000000001000000000000001000000000000001000000000000001000000000000001000000,B=014×6,D=100000010000001000000100000010000001111111111111.We randomly choose an initial state(21)x0=-0.4257-0.7771-0.7910.00510.2835-0.4187-0.05550.86080.29720.7322-0.6673-0.0970.7319-0.9849Tto stimulate the system. It is assumed that there are 6 transmission noises between nodes which are zero-mean bounded from [-1,1]. Also, assume that the rough upper and lower bounds on the initial state x¯r and x_r are 1 and -1, respectively. From (7), it can be seen that the minimal number of steps N for direct calculation on x0 is 7.Figure 1
Underlying topology of the considered graph consisted of14 nodes.Therefore, in the scenario that there are enough output measurements over the horizon lengthN=7, condition (7) is satisfied. So there exists M satisfying (8) such that x0=My. By taking the matrix calculation, the initial state x0 is recovered.For the scenario that there are only output measurements over the horizon lengthN=6, the full recovery of x0 is not possible. By using the method given in Theorems 8 and 9, the tightest upper and lower bounds on x0 are solved and given as follows:(22)x_0=-0.5163-0.8193-0.9824-0.09470.2403-0.5145-0.0950.82130.08870.6245-0.7106-0.21410.6975-1.0000T,x¯0=-0.2774-0.6978-0.71710.22260.3036-0.3730.00320.91950.37400.8097-0.5759-0.05260.8341-0.8897T.As it can be seen that the difference between the upper and lower bounds is small, x0 is well-estimated.By using the exact value or the tightest bounds forx0, any exact value or bounds of objective function related to x0 can be therefore obtained. For example, here, the true average consensus value of this system, that is, 1/14(∑i=114‍x0[i]), is -0.0933, while the bounds on it obtained from our method are [-0.1768,-0.0083] when N=6 which are very tight with respect to the noise level ±1.Figure2 illustrates the bounds on the average consensus value as the horizon of output measurements reaches 7 in which the exact average consensus value is solved. It is shown that the bounds become tighter and tighter as more and more measurement information becomes available.Figure 2
Bounds on the average consensus value using output measurements of different horizon lengths.


## 5. Conclusion

We have studied the problem of distributed function calculation in a connected network operating with noise. In particular, this is not focused on the nearest-neighbor protocol, where each node updates its own value at each step as a linear combination of its own previous values and those of its neighbors. Each node tries to compute a linear function of all the initial states of all nodes. Algorithm to compute the function in question is proposed when the number of successive observations is large enough; we also propose an approach to obtain tightest bounds on such a function based on the available observations while the number of observations is not large enough.



---

*Source: 6093293-2016-04-20.xml*