# Self-Aware Distributed Consensus Building for Sensor Networks

Authors: Lei Chen; Jeff Frolik
Journal: ISRN Communications and Networking
 (2011)

---

## Abstract

Distributed consensus building promises to
improve the robustness and reliability of sensor networks
and thus is an active topic of research. Whereas extensive
study has been done on the theoretical analysis of the
asymptotic behavior of consensus building, one important
issue that is crucial to the practical implementation of
sensor networks was rarely explored, namely, the criteria
to determine whether consensus has been attained. In this
paper, we propose an approach that allows each node in a
network to make the decision by itself, based on the second
derivatives of its own state. The approach does not rely
on the states of other nodes, leads to substantial saving
of communication resources, and is resilient to connection
failure. We perform a systematic analysis of the approach
and, as a consequence, derive the optimal parameters that
minimize the upper bound of the number of required
iterations to reach consensus.


---

## Body

## 1. Introduction

In past decades, sensor networks have been widely applied in civilian, military, and industrial systems. Despite tremendous efforts that have been devoted to sensor techniques, it remains a great challenge to build a sensor system that works reliably and responsively under varying conditions. Distributed consensus building has emerged as an approach to address such shortcomings. Each individual node updates its“state” (e.g., view of local or global sensed values, actions to be taken, and/or network conditions) while exchanging information with others, until consensus of the state is attained. While individual sensors could have unreliable information or be vulnerable to environmental or network dynamics, all sensors in the network, via effective cooperation, can produce decisions that are higher in reliability because of the reached consensus. Since such consensus building enables the network to act locally based on distributed interactions, we contend that this approach can benefit networks that also involve actuation or otherwise interact with the physical world.In previous work, there has been extensive theoretical study of the distributed consensus building problem. Xiao and Boyd [1] considered the convergence of a distributed averaging problem and proposed to seek the optimal updating weights by solving a semidefinite optimization problem. We note that the derivation in this work was based on the symmetric communication link assumption, which is not always satisfied in real networks. Olshevsky and Tsitsiklis [2] performed a more comprehensive investigation of this problem and derived lower bounds on the worst-case convergence time for different types of distributed consensus methods. Based on the theoretical analysis, they also developed an algorithm whose convergence time can essentially match these bounds. Olfati-Saber et al. [3, 4] developed a theoretical framework of information consensus over a multiagent network. They inspected various theoretical aspects of the problem and established the connections between the spectral properties of complex networks and the convergence rate of the consensus algorithms.Whereas this previous work has laid down a solid theoretical foundation for the research on distributed consensus, it mostly focused on the analysis of asymptotic behaviors. As a consequence, practical issues, which are equally important to the effectiveness of sensor networks, have received less attention. In this paper, we particularly study one of these issues, namely, how might an individual node determine whether consensus (within a tolerable range) has been attained. This is motivated by the consideration that if the consensus status can be detected as soon as it is reached, the sensor network can then be put to rest earlier, which should lead to considerable energy saving.Specifically, our goal here is to develop a consensus determining scheme with two desirable properties. First, it isself-aware, namely, each node in the network decides whether this scheme has reached consensus solely based on its own state, without resorting to the communication with other nodes. Compared to the schemes that detect consensus via information exchange with other nodes, a self-aware scheme does not consume extra communication bandwidth and tends to be more responsive. Second, the scheme should be resilient against noise as well as the variation of propagation delay and link weights. Our approach to achieve this target is inspired by the continuous-time work of Barbarossa et al. [5–7]. In their work, the network consensus is defined with respect to the first derivative of the states, rather than the states themselves. They showed that this new definition can result in improved robustness against noises, delays, and even topology changes. Hence, we adopt this formalism as the basis of our work.The work presented here extends our earlier work [8] which initiates the basic idea of our approach. In that paper, we derived a discrete-time counterpart of the continuous-time formulation given in [5], making it implementable in physical, discrete-time hardware. We also verified the method through both numerical analysis and hardware implementation. In this paper, we further extend our previous exploration. Particularly, we consider the self-aware criterion given by(1)‖ẍ(t)‖≤ε,
where x(t) is the state of a node as a function of time and ε is the tolerance threshold. With this criterion, we obtain an upper bound of the number of iterations needed to achieve consensus and thereon derive the optimal step coefficient δ that minimizes this bound. Moreover, we examined how the optimal solution is related to different factors, including the spectrum of the graph Laplacian as well as the tolerance range, via both theoretical analysis and numerical simulation. We note that our analysis is not restricted to symmetric network, as opposed to some previous analysis, such as that in [1].To sum up, the main contributions of this paper lies in the following aspects. First, we develop a self-aware criterion to detect consensus based on the discrete-time formulation presented in our earlier work [8]. It is simple, cost-effective, and robust to noises as well as network changes. Second, we perform theoretical analysis of the criterion for both symmetric and asymmetric networks and thereon obtain an upper bound of the number of iterations needed to reach consensus. Third, we derive an optimal updating weight and examine its relations to the spectral structure of the network as well as the tolerance threshold.A brief outline of the rest of the paper follows. In Section2, we formulate a discrete-time consensus model and analyzes its asymptotic behavior. In Section 3, we obtain an upper bound of the convergence time based on this model and thereon derive the optimal choice of δ. In Section 4, we give some numerical examples, illustrate the influence of ε to the consensus for both symmetric and asymmetric scenarios, and verify the analytical solution of δ. Finally, Section 5 concludes this work and identifies areas of future research.


## 2. The Formulation of Consensus Model

In this paper, we consider a sensor network withN nodes (e.g., N=12 in Figure 1). Each node receives input from its sensors, and combines it with the states of its neighboring nodes to adjust its own state. These N nodes constitute a dynamical system. Specifically, for each node i, its dynamical behavior can be described by the following equation:(2)ẋi(t)=yi(t)+∑j∈N(i)aij(xj(t)-xi(t)).
Here, xi is the state of node i as a function of time, yi is the corresponding input signal, 𝒩(i) is the set of neighboring nodes of i, and aij is the coupling coefficient that reflects the contribution of node j to the evolution of node i. Note here that the coupling coefficients need not to be symmetric (aij=aji) in general. In this model, the change of xi is driven by a linear combination of the input signal and state differences from its neighbors. For simplicity, we assume that the input signals are static, that is, yi(t)=yi for each i=1,…,N.Figure 1
Schematic diagram of a sensor network withN=12 nodes.The model given in (2) can be rewritten into the following vectorized form:(3)ẋ(t)=-Lx(t)+y.
Here, x(t)=[x1(t),…,xN(t)]T, y=[y1,…,yN]T, and L denotes the Laplacian matrix of the communication graph whose edge weights are given by the coupling coefficients aij. Particularly, we have(4)L(i,j)={∑j∈N(i)aij(i=j),-aij(j∈N(i)),0(otherwise).
We note that L is symmetric if and only if the coupling coefficients aij are symmetric. A symmetric system implies that all communication links are bidirectional. However, this is not always the case due to packet drops, and different transmit powers and receiver sensitivities of the hardware.


### 2.1. Discrete-Time Formulation

To implement (3) on physical, discrete-time hardware, we reformulate the problem under discrete-time setting, via finite difference approximation, as(5)x(n)=x(n-1)+δẋ(n-1)=(I-δL)x(n-1)+δy.
We note that the updating at each step is controlled by an updating weight δ. Through recursively expanding the formula above, we find the analytic expression for x(n), as(6)x(n)=Φnx(0)+δ∑k=0n-1Φky,
where Φ=I-δL. From this, we further obtain a discrete version of the first derivative, as(7)ẋδ(n)≜1δ(x(n)-x(n-1))=Φn-1(-Lx(0)+y).
Here, ẋδ refers to the discrete derivative obtained with updating weight δ.


### 2.2. The Conditions of Convergence

According to Barbarosa’s definition, the consensus is attained when the first derivatives of the states of all nodes converge to stationary values, which we denote by a vectorω*, as illustrated by Figure 2. However, as we will show below, convergence is guaranteed only under specific conditions, but not in general.Figure 2
Convergence of the state of the sensor network in Figure1.Lemma 1.
The first derivatives of the system given by (7) converge to stationary values  ω* with arbitrary input  y if and only if
(8)ρ(Φ)≤1.
In this case, Φ∞≜limn→∞Φn is finite, and the vector of stationary values ω* is given by
(9)ω*=-Φ∞Lx(0)+Φ∞y.
In particular, when ∥Φ∞L∥=0, one has ω*=Φ∞y, which is independent of the initial states x(0).Here,ρ(Φ) is the spectral radius of Φ, that is, the maximum absolute value of its eigenvalues.Proof of Lemma1.
Ifρ(Φ)≤1, Φn is a convergent sequence and thus so is ẍδ(n) due to continuity of linear operation. Otherwise, if ρ(Φ)>1, there exists an eigenvalue λ of Φ such that |λ|>1. Since y is arbitrary, we can choose y such that -Lx(0)+y=e, where e is the eigenvector associated with λ. As a result, ẍδ(n)=λn-1e, which diverges. Therefore, the system converges for every y if and only if ρ(Φ)≤1.
The fact thatΦn converges implies that Φ∞ is finite. Again, by continuity of linear operation, we obtain
(10)lim⁡n→∞Φn-1(-Lx(0)+y)=(lim⁡n→∞Φn-1)(-Lx(0)+y)=Φ∞(-Lx(0)+y).
This completes the proof of the second statement.Based on this lemma, we derive the conditions of convergence, which as we will see are closely related to the eigenvalues ofL, denoted by λ1,…,λN. Without losing generality, we assume that |λ1|≤⋯≤|λN|. The properties of these eigenvalues are summarized below.(1)
rank(L)=N-K, where K is the number of connected components of the communication graph. The number of null eigenvalues indicates the number of connected components.(2)
L has a null space which contains 1, that is, L1=0. In particular, when K=1, the null space is a one-dimensional space spanned by 1.(3)
|λN|=ρ(L), the spectral radius of L.(4)
WhenL is symmetric, λ1,…,λN are nonnegative real values.The eigenvalues ofΦ=I-δL are then given by 1-δλ1,…,1-δλN. Hence, the spectral radius of Φ is given by(11)ρ(Φ)=max⁡{|1-δλi|:i=1,…,N}.
This immediately leads to an important condition of convergence, as given by the following corollary.Corollary 2.
The system given by (7) converges if and only if
(12)|1-δλi|≤1,∀i=1,…,N.
In particular, when L is symmetric, all eigenvalues are real, and thus this condition is equivalent to
(13)δλN≤2.Proof of Corollary2.
By Lemma1, the system converges if and only if ρ(Φ)≤1. By (11), this is equivalent to maxi=1,…,N|1-δλi|≤1, that is, |1-δλi|≤1 for each i. When L is symmetric, all eigenvalues are real; hence, the maximum here can be either |1-δλ1| or |1-δλN|. Recall that λ1=0, thus |1-δλ1|=1. Therefore, the condition holds if and only if |1-δλN|≤1. Considering that λN>0, this is equivalent to δλN≤2.Suppose that thecondition of convergence given above is satisfied; we have the following discussions in regard to the matrices Φ and Φ∞.(1)
SinceL1=0, we have Φ1=(I-δL)1=1, implying that Φ has an eigenvalue 1, which is associated with an eigenvector 1.(2)
Suppose that the number of connected components of the communication graph isK, then the geometric multiplicity of the eigenvalue 1 of Φ is K, meaning that the dimension of the eigenspace corresponding to the eigenvalue 1 is K.(3)
Φn1=1 for each n=1,2,…. Taking this sequence to the limit leads to an important result, namely, Φ∞1=1.These results provide necessary basis for our later derivation.


### 2.3. Consensus over Connected Networks

In this paper, we focus on the case where the communication graph is connected andL is diagonalizable. For this case, we derive the following results that characterize the asymptotic behavior of the dynamical system.Lemma 3.
Suppose thatL is the Laplacian matrix of a connected graph and is diagonalizable,  Φ=I-δL such that  ρ(Φ)=1, then
(14)Φ∞=1γT,
where γ is a left eigenvector of Φ associated with the eigenvalue 1 that satisfies γT1=1.Proof of Lemma3.
SinceΦ is diagonalizable, it can be written as
(15)Φ=PDP-1,
where D is a diagonal matrix with Dii=1-δλi, and P is a matrix whose columns are the corresponding eigenvectors. Hence,
(16)Φn=PDnP-1.
Note that Dn is also a diagonal matrix with Diin=(1-δλi)n. Under the condition of convergence, as n→∞, D11n remains 1, while all other entries converge to 0. Consequently,
(17)Φ∞=(P)1(P-1)1T.
Here, we use the notation (·)1 to indicate the first column of a matrix. The first column of P is the eigenvector associated with the eigenvalue 1-δλ1=1, which is 1, while the first column of P-1 is a left eigenvector associated with the same eigenvalue, which we denote by γ. Consequently, we can write Φ∞=1γT. Moreover, as we have discussed above, Φ∞1=1, thus 1γT1=1, which implies that γT1=1. The proof is completed.Following this lemma, we derive the following results that characterize the asymptotic behaviors of the dynamical system on a connected communication network.Theorem 4.
Suppose that the dynamical system given by (7) is on a connected network and the Laplacian matrix  L is diagonalizable. If  δ is chosen such that  ρ(Φ)≤1, then the first derivative of each node converges to a common stationary value  ω* given by
(18)ω*=γTy=∑i=1Nγiyi.
Here, γ=[γ1,…,γN]T is a left eigenvector of Φ associated with the eigenvalue 1 that satisfies ∑i=1Nγi=1.Here, convergence to a common stationary value means that all entries ofω* are the same, that is, ω*=[ω*,…,ω*]T. In addition, we can see that the value ω* is a weighted average of the input signals, which reflects the global consensus formed over the sensor network.Proof of Theorem4.
From Lemma3, we can see that, under the condition of convergence, Φn converges to Φ∞=1γT as n→∞. And since L1=0, LΦ∞=L1γT=0. By Lemma 1, we know that the states converge to stationary values given by
(19)ω*=Φ∞y=1γTy.
Let ω*=γTy; this can be further rewritten as ω*=ω*1. The proof is completed.


### 2.4. Determining Consensus

For any practical implementation, the stationary valueω* is not available in advance; hence, one has to resort to other means to determine whether a sensor network has reached consensus. A natural idea is to compare the first derivatives of all nodes and see whether they are close to each other. However, implementation of this strategy might require a centralized process to collect information from every node, which could be expensive or even infeasible in practice.In this paper, we take a different approach. Instead of relying on the first derivatives to detect consensus, we consider the second derivatives. Based on our discrete-time formulation, we define the vector ofsecond derivatives to be(20)ẍδ(n)=1δ(ẋδ(n)-ẋδ(n-1))=LΦn-2(Lx(0)-y).Suppose that the dynamical system is on a connected communication network with diagonalizable Laplacian matrixL; we have LΦn→0 as n→∞. It immediately follows that(21)lim⁡n→∞ẍδ(n)=0.This observation suggests that we may decide whether consensus has been attained by examining whether the second derivatives vanish. Specifically, we devise the following rule. Given a tolerance thresholdε>0, a sensor network is regarded to reach consensus if(22)‖ẍδ(n)‖∞<ε.
Here, ∥·∥∞ denotes the infinity norm. Intuitively, the network is considered to attain consensus when the magnitude of the second derivative at each node is below the given threshold ε.It is worth noting that this rule isself-aware, meaning that each node can decide whether it meets the condition locally, without talking to other nodes. Compared to other rules, its main advantages are three-fold: (1) simplicity of implementation, (2) no consumption of extra communication energy, and (3) resilience to the changes of network conditions.


## 2.1. Discrete-Time Formulation

To implement (3) on physical, discrete-time hardware, we reformulate the problem under discrete-time setting, via finite difference approximation, as(5)x(n)=x(n-1)+δẋ(n-1)=(I-δL)x(n-1)+δy.
We note that the updating at each step is controlled by an updating weight δ. Through recursively expanding the formula above, we find the analytic expression for x(n), as(6)x(n)=Φnx(0)+δ∑k=0n-1Φky,
where Φ=I-δL. From this, we further obtain a discrete version of the first derivative, as(7)ẋδ(n)≜1δ(x(n)-x(n-1))=Φn-1(-Lx(0)+y).
Here, ẋδ refers to the discrete derivative obtained with updating weight δ.


## 2.2. The Conditions of Convergence

According to Barbarosa’s definition, the consensus is attained when the first derivatives of the states of all nodes converge to stationary values, which we denote by a vectorω*, as illustrated by Figure 2. However, as we will show below, convergence is guaranteed only under specific conditions, but not in general.Figure 2
Convergence of the state of the sensor network in Figure1.Lemma 1.
The first derivatives of the system given by (7) converge to stationary values  ω* with arbitrary input  y if and only if
(8)ρ(Φ)≤1.
In this case, Φ∞≜limn→∞Φn is finite, and the vector of stationary values ω* is given by
(9)ω*=-Φ∞Lx(0)+Φ∞y.
In particular, when ∥Φ∞L∥=0, one has ω*=Φ∞y, which is independent of the initial states x(0).Here,ρ(Φ) is the spectral radius of Φ, that is, the maximum absolute value of its eigenvalues.Proof of Lemma1.
Ifρ(Φ)≤1, Φn is a convergent sequence and thus so is ẍδ(n) due to continuity of linear operation. Otherwise, if ρ(Φ)>1, there exists an eigenvalue λ of Φ such that |λ|>1. Since y is arbitrary, we can choose y such that -Lx(0)+y=e, where e is the eigenvector associated with λ. As a result, ẍδ(n)=λn-1e, which diverges. Therefore, the system converges for every y if and only if ρ(Φ)≤1.
The fact thatΦn converges implies that Φ∞ is finite. Again, by continuity of linear operation, we obtain
(10)lim⁡n→∞Φn-1(-Lx(0)+y)=(lim⁡n→∞Φn-1)(-Lx(0)+y)=Φ∞(-Lx(0)+y).
This completes the proof of the second statement.Based on this lemma, we derive the conditions of convergence, which as we will see are closely related to the eigenvalues ofL, denoted by λ1,…,λN. Without losing generality, we assume that |λ1|≤⋯≤|λN|. The properties of these eigenvalues are summarized below.(1)
rank(L)=N-K, where K is the number of connected components of the communication graph. The number of null eigenvalues indicates the number of connected components.(2)
L has a null space which contains 1, that is, L1=0. In particular, when K=1, the null space is a one-dimensional space spanned by 1.(3)
|λN|=ρ(L), the spectral radius of L.(4)
WhenL is symmetric, λ1,…,λN are nonnegative real values.The eigenvalues ofΦ=I-δL are then given by 1-δλ1,…,1-δλN. Hence, the spectral radius of Φ is given by(11)ρ(Φ)=max⁡{|1-δλi|:i=1,…,N}.
This immediately leads to an important condition of convergence, as given by the following corollary.Corollary 2.
The system given by (7) converges if and only if
(12)|1-δλi|≤1,∀i=1,…,N.
In particular, when L is symmetric, all eigenvalues are real, and thus this condition is equivalent to
(13)δλN≤2.Proof of Corollary2.
By Lemma1, the system converges if and only if ρ(Φ)≤1. By (11), this is equivalent to maxi=1,…,N|1-δλi|≤1, that is, |1-δλi|≤1 for each i. When L is symmetric, all eigenvalues are real; hence, the maximum here can be either |1-δλ1| or |1-δλN|. Recall that λ1=0, thus |1-δλ1|=1. Therefore, the condition holds if and only if |1-δλN|≤1. Considering that λN>0, this is equivalent to δλN≤2.Suppose that thecondition of convergence given above is satisfied; we have the following discussions in regard to the matrices Φ and Φ∞.(1)
SinceL1=0, we have Φ1=(I-δL)1=1, implying that Φ has an eigenvalue 1, which is associated with an eigenvector 1.(2)
Suppose that the number of connected components of the communication graph isK, then the geometric multiplicity of the eigenvalue 1 of Φ is K, meaning that the dimension of the eigenspace corresponding to the eigenvalue 1 is K.(3)
Φn1=1 for each n=1,2,…. Taking this sequence to the limit leads to an important result, namely, Φ∞1=1.These results provide necessary basis for our later derivation.


## 2.3. Consensus over Connected Networks

In this paper, we focus on the case where the communication graph is connected andL is diagonalizable. For this case, we derive the following results that characterize the asymptotic behavior of the dynamical system.Lemma 3.
Suppose thatL is the Laplacian matrix of a connected graph and is diagonalizable,  Φ=I-δL such that  ρ(Φ)=1, then
(14)Φ∞=1γT,
where γ is a left eigenvector of Φ associated with the eigenvalue 1 that satisfies γT1=1.Proof of Lemma3.
SinceΦ is diagonalizable, it can be written as
(15)Φ=PDP-1,
where D is a diagonal matrix with Dii=1-δλi, and P is a matrix whose columns are the corresponding eigenvectors. Hence,
(16)Φn=PDnP-1.
Note that Dn is also a diagonal matrix with Diin=(1-δλi)n. Under the condition of convergence, as n→∞, D11n remains 1, while all other entries converge to 0. Consequently,
(17)Φ∞=(P)1(P-1)1T.
Here, we use the notation (·)1 to indicate the first column of a matrix. The first column of P is the eigenvector associated with the eigenvalue 1-δλ1=1, which is 1, while the first column of P-1 is a left eigenvector associated with the same eigenvalue, which we denote by γ. Consequently, we can write Φ∞=1γT. Moreover, as we have discussed above, Φ∞1=1, thus 1γT1=1, which implies that γT1=1. The proof is completed.Following this lemma, we derive the following results that characterize the asymptotic behaviors of the dynamical system on a connected communication network.Theorem 4.
Suppose that the dynamical system given by (7) is on a connected network and the Laplacian matrix  L is diagonalizable. If  δ is chosen such that  ρ(Φ)≤1, then the first derivative of each node converges to a common stationary value  ω* given by
(18)ω*=γTy=∑i=1Nγiyi.
Here, γ=[γ1,…,γN]T is a left eigenvector of Φ associated with the eigenvalue 1 that satisfies ∑i=1Nγi=1.Here, convergence to a common stationary value means that all entries ofω* are the same, that is, ω*=[ω*,…,ω*]T. In addition, we can see that the value ω* is a weighted average of the input signals, which reflects the global consensus formed over the sensor network.Proof of Theorem4.
From Lemma3, we can see that, under the condition of convergence, Φn converges to Φ∞=1γT as n→∞. And since L1=0, LΦ∞=L1γT=0. By Lemma 1, we know that the states converge to stationary values given by
(19)ω*=Φ∞y=1γTy.
Let ω*=γTy; this can be further rewritten as ω*=ω*1. The proof is completed.


## 2.4. Determining Consensus

For any practical implementation, the stationary valueω* is not available in advance; hence, one has to resort to other means to determine whether a sensor network has reached consensus. A natural idea is to compare the first derivatives of all nodes and see whether they are close to each other. However, implementation of this strategy might require a centralized process to collect information from every node, which could be expensive or even infeasible in practice.In this paper, we take a different approach. Instead of relying on the first derivatives to detect consensus, we consider the second derivatives. Based on our discrete-time formulation, we define the vector ofsecond derivatives to be(20)ẍδ(n)=1δ(ẋδ(n)-ẋδ(n-1))=LΦn-2(Lx(0)-y).Suppose that the dynamical system is on a connected communication network with diagonalizable Laplacian matrixL; we have LΦn→0 as n→∞. It immediately follows that(21)lim⁡n→∞ẍδ(n)=0.This observation suggests that we may decide whether consensus has been attained by examining whether the second derivatives vanish. Specifically, we devise the following rule. Given a tolerance thresholdε>0, a sensor network is regarded to reach consensus if(22)‖ẍδ(n)‖∞<ε.
Here, ∥·∥∞ denotes the infinity norm. Intuitively, the network is considered to attain consensus when the magnitude of the second derivative at each node is below the given threshold ε.It is worth noting that this rule isself-aware, meaning that each node can decide whether it meets the condition locally, without talking to other nodes. Compared to other rules, its main advantages are three-fold: (1) simplicity of implementation, (2) no consumption of extra communication energy, and (3) resilience to the changes of network conditions.


## 3. Convergence Time and Optimalδ

In the previous section, we have derived the conditions under which a sensor network is guaranteed to converge to the consensus status. The next important question ishow long does it take to converge? In this section, we are going to seek an answer to this question.For discrete-time implementations, the convergence time is measured by the number of iterationsn needed to reach consensus. Generally, it is impossible to obtain the exact value of this number in design stage, as it depends on both the initial states and the input signals. It is nonetheless possible to derive upper bounds, which would provide guidance for us to choose the optimal design.Recall that we have obtained the analytic expression of the second derivatives, as given by(23)ẍδ(n)=L(I-δL)n-2(Lx(0)-y).Given a tolerance thresholdε, our goal here is to derive an upper bound M(ε) such that(24)‖ẍδ(n)‖∞≤ε,∀n>M(ε).
However, directly working with ẍδ is difficult in general. Our basic idea is to first seek an upper bound U(n;δ) of ∥ẍδ(n)∥ and then find M(ε) such that(25)U(n;δ)≤ε,∀n>M(ε).
Note here that we introduce δ as an argument of U for the purpose of emphasizing the fact that such an upper bound is often closely related to the updating weight δ. Since ∥ẍδ(n)∥≤U(n;δ), the condition given by (25) implies the one given by (24).


### 3.1. Upper Bound Based on Spectral Analysis

Our approach to obtain an upper bound is based on the concept of induced norm. Given a matrixA, its induced norm, denoted by ∥A∥, is defined as follows:(26)‖A‖≜sup⁡x:‖x‖≤1‖Ax‖.
From this definition, we can immediately see that(27)‖Ax‖≤‖A‖⋅‖x‖.
The induced norm is related to the spectral radius. In general, we have ∥A∥≥ρ(A). Particularly, when A is symmetric, the equality holds, that is, ∥A∥=ρ(A).For induced norm, we also have the following result, which is important for our derivation.Lemma 5.
Given a real square matrixA and  α0,α1,…,αK∈ℝ, one has
(28)‖α0I+∑k=1KαkAk‖≤α0+∑k=1K|αk|‖A‖k.This is a well-known result of linear algebra, which states that the induced norm of the matrix obtained by applying a polynomial to a matrixA is upper bounded by the corresponding polynomial of ∥A∥ with the coefficients replaces by their absolute values.Coming back to our problem and considering the norm∥ẍδ(n)∥, we have the following result.Theorem 6.
Letx be the states of a dynamical system on a connected network whose Laplacian matrix  L is diagonalizable. Then, one has
(29)‖ẍδ(n)‖≤‖I-δL-1γT‖n-2‖L‖⋅‖h‖.
Here, γ is a left eigenvector of L associated with the eigenvalue 1 that satisfies γT1=1, and h=Lx(0)-y.Proof of Theorem6.
We first rewriteẍδ(n) as follows:
(30)ẍδ(n)=L(I-δL)n-2h=L(I-δL-1γT+1γT)n-2h=L(I-δL-1γT)n-2h.
Here, we make use of the fact that L1γT=0γT=1. With this expression, (29) in this theorem immediately follows from Lemma 5 and (27). The proof is completed.From this theorem, it is not difficult to show that when(31)n≥log⁡‖L‖+log⁡‖h‖+log⁡(1/ε)log⁡(1/‖I-δL-1γT‖)+2.
The right-hand side of this inequality gives an upper bound of the number of iterations needed to attain consensus.


### 3.2. Optimal Choice ofδ

To minimize the upper bound given by (31), one can choose the optimal updating weight δ̂ that minimizes ∥I-δL-1γT∥, as(32)δ̂=argminδ≥0‖I-δL-1γT‖.


#### 3.2.1. Symmetric Cases

We first consider the cases where the underlying communication network is symmetric. In these cases, the Laplacian matrixL is symmetric. Let 0=λ1≤⋯≤λN be the eigenvalues of L, which are all nonnegative real values. Since the component 1γT that corresponds to the eigenvalue 1 of Φ is subtracted, the eigenvalues of I-δL-1γT are 0,1-δλ2,…,1-δλN. Since L is symmetric, we have(33)‖I-δL-1γT‖=ρ(I-δL-1γT)=max⁡{|1-δλ2|,|1-δλN|}.
Hence, the optimal choice of δ is given by(34)δ̂=argminδ>0max⁡{|1-δλ2|,|1-δλN|}=2λ2+λN.
Note that δ̂≤2/λN. According to Corollary 2, it follows, that with such an optimal choice, convergence is guaranteed. We also note that Xiao and Boyd [1] obtained similar results in different context.


#### 3.2.2. Generic Diagonalizable Cases

In real applications the communication topology is not always symmetric due to difference of devices and deployment environment. Hence, the spectral radius does not necessarily equal the induced norm, we use the spectral radius in place of the induced norm; leading to the following objective in choosing optimalδ:(35)δ̂=argminδ≥0ρ(I-δL-1γT).
In generic cases, the spectral radius is given by(36)ρ(I-δL-1γT)=max⁡{|1-δλi|:i=2,…,N}.
The eigenvalues here can be complex numbers. When solving this problem, it is important to contain the solution within the domain such that convergence is guaranteed. The domain is defined by(37)|1-δλi|≤1,∀i=2,…,N.
Suppose that λi=αi+iβi; we have that |1-δλi|<1 if and only if(38)0≤δ≤2αi|λi|2.
Therefore, the valid range of δ is(39)0≤δ≤min⁡i=2,…,N2αi|λi|2.
We note that there exists no analytic solution to this problem. However, the objective function is a piece-wise quadratic function, which can be readily solved by first delimiting the pieces and then comparing their respective minimum.The derivation above provides an upper bound of the convergence time and a guideline for choosing the optimalδ. We can see that they are closely related to the spectral characteristics of the Laplacian matrix L. In general, the network converges rapidly when the eigenvalues of I-δL (except the one that equals 1) are small.


### 3.3. More Accurate Analysis of the Convergence Time

As mentioned above, the actual convergence time also depends on the initial statesx(0), and the input signals y, as well as the tolerance threshold ε. Here, we take a close examination of such dependency.Suppose thatL is diagonalizable with eigenvalues 0=λ1<λ2≤⋯≤λN. Let ej be the eigenvector associated with the eigenvalue λi for each i=1,…,N. Since L is diagonalizable, these eigenvectors span the entire state space, and as a consequence, the vector h=Lx(0)-y can be expressed as a linear combination of them, as(40)h=∑i=1Nciei.
Let ℛ(L)={Lv:v∈ℝN} be the range space of L. Since the underlying network is connected, the null space of L is one dimensional. Hence, ℛ(L) has dimension N-1 and is spanned by e2,…,eN. Clearly, the second derivatives ẍδ(n)=L(I-δL)n-2h∈ℛ(L) and thus can be expressed to be a linear combination of e2,…,eN, as(41)ẍδ(n)=∑i=2Nciλi(1-δλi)n-2ei.
We can see that the ith term decreases geometrically with shrinking ratio |1-δλi|. Asymptotically, the term with greatest shrinking ratio, namely, the one that attenuates most slowly, will dominate in a long run.LetC:ℛ(L)→ℛ(L) be a coordinate transform that maps each vector in ℛ(L) to the coefficients with respect to the basis {e2,…,eN}. This is a bijective linear map. For each vector v∈ℛ(L), we define(42)‖v‖∞/C=‖C(v)‖∞.
It can be easily shown that ∥·∥∞/C is a norm on ℛ(L). To characterize the relations between ∥·∥∞/C and ∥·∥∞, we define(43)κC≜sup⁡v∈R(L)‖v‖∞‖v‖∞/C.
In other words, κC is the greatest real value that satisfies(44)‖v‖∞≤κC‖v‖∞/C,∀v∈R(L).
By the equivalence of norms on a finite dimensional vector space, we have 0<κC<+∞; that is, κC is a finite positive value. Consider the second derivatives ẍδ(n). To have ∥ẍδ(n)∥∞<ε, it suffices to have(45)‖ẍδ(n)‖∞/C<εκC.
From the definition of ∥·∥∞/C and (41), we get(46)‖ẍδ(n)‖∞/C=max⁡i=2,…,N|ciλi(1-δλi)n-2|.
As a result, when(47)n>max⁡i=2,…,Nlog⁡(κC|ciλi|/ε)log⁡(1/|1-δλi|)+2,∥ẍδ(n)∥<ε, implying that the sensor network attains the consensus within the tolerable range. Based on this bound, the optimal choice δ is given by(48)δ̂=argminδ>0max⁡i=2,…,Nlog⁡⁡(κC|ciλi|/ε)log⁡⁡(1/|1-δλi|).
This result indicates that with the knowledge of input signals, one can derive an improved upper bound, and a proper choice for δ, which relates not only to the underlying graph, but also to the initial states, input signals, and the tolerance threshold ε.However, directly applying this result in practice is infeasible, as the input signals are unavailable in advance; otherwise, we do not even have to deploy a sensor network to measure them. The true significance of this result lies is that it suggests that we can incorporate domain-specific knowledge to make a better design of the sensor network.Specifically, while the exact input is unknown before we really perform the measurement, we generally have some rough knowledge about what the input might be, which could be formulated as a prior distribution of the input signals and then be exploited to guide the choice ofδ. From such a prior model, one can derive the prior distribution of the coefficients c=[c2,…,cN]T, denoted by p(c). Then, we obtain an upper bound of the expected convergence time, as(49)UT(δ;p)=∫max⁡i=2,…,Nlog⁡(κC|ciλi|/ε)log⁡(1/|1-δλi|)p(c)dc.
With this model, one can choose an optimal δ that minimizes UT(δ;p). Though it might be difficult to directly solve this problem, one can resort to various techniques to make further approximation.


## 3.1. Upper Bound Based on Spectral Analysis

Our approach to obtain an upper bound is based on the concept of induced norm. Given a matrixA, its induced norm, denoted by ∥A∥, is defined as follows:(26)‖A‖≜sup⁡x:‖x‖≤1‖Ax‖.
From this definition, we can immediately see that(27)‖Ax‖≤‖A‖⋅‖x‖.
The induced norm is related to the spectral radius. In general, we have ∥A∥≥ρ(A). Particularly, when A is symmetric, the equality holds, that is, ∥A∥=ρ(A).For induced norm, we also have the following result, which is important for our derivation.Lemma 5.
Given a real square matrixA and  α0,α1,…,αK∈ℝ, one has
(28)‖α0I+∑k=1KαkAk‖≤α0+∑k=1K|αk|‖A‖k.This is a well-known result of linear algebra, which states that the induced norm of the matrix obtained by applying a polynomial to a matrixA is upper bounded by the corresponding polynomial of ∥A∥ with the coefficients replaces by their absolute values.Coming back to our problem and considering the norm∥ẍδ(n)∥, we have the following result.Theorem 6.
Letx be the states of a dynamical system on a connected network whose Laplacian matrix  L is diagonalizable. Then, one has
(29)‖ẍδ(n)‖≤‖I-δL-1γT‖n-2‖L‖⋅‖h‖.
Here, γ is a left eigenvector of L associated with the eigenvalue 1 that satisfies γT1=1, and h=Lx(0)-y.Proof of Theorem6.
We first rewriteẍδ(n) as follows:
(30)ẍδ(n)=L(I-δL)n-2h=L(I-δL-1γT+1γT)n-2h=L(I-δL-1γT)n-2h.
Here, we make use of the fact that L1γT=0γT=1. With this expression, (29) in this theorem immediately follows from Lemma 5 and (27). The proof is completed.From this theorem, it is not difficult to show that when(31)n≥log⁡‖L‖+log⁡‖h‖+log⁡(1/ε)log⁡(1/‖I-δL-1γT‖)+2.
The right-hand side of this inequality gives an upper bound of the number of iterations needed to attain consensus.


## 3.2. Optimal Choice ofδ

To minimize the upper bound given by (31), one can choose the optimal updating weight δ̂ that minimizes ∥I-δL-1γT∥, as(32)δ̂=argminδ≥0‖I-δL-1γT‖.


### 3.2.1. Symmetric Cases

We first consider the cases where the underlying communication network is symmetric. In these cases, the Laplacian matrixL is symmetric. Let 0=λ1≤⋯≤λN be the eigenvalues of L, which are all nonnegative real values. Since the component 1γT that corresponds to the eigenvalue 1 of Φ is subtracted, the eigenvalues of I-δL-1γT are 0,1-δλ2,…,1-δλN. Since L is symmetric, we have(33)‖I-δL-1γT‖=ρ(I-δL-1γT)=max⁡{|1-δλ2|,|1-δλN|}.
Hence, the optimal choice of δ is given by(34)δ̂=argminδ>0max⁡{|1-δλ2|,|1-δλN|}=2λ2+λN.
Note that δ̂≤2/λN. According to Corollary 2, it follows, that with such an optimal choice, convergence is guaranteed. We also note that Xiao and Boyd [1] obtained similar results in different context.


### 3.2.2. Generic Diagonalizable Cases

In real applications the communication topology is not always symmetric due to difference of devices and deployment environment. Hence, the spectral radius does not necessarily equal the induced norm, we use the spectral radius in place of the induced norm; leading to the following objective in choosing optimalδ:(35)δ̂=argminδ≥0ρ(I-δL-1γT).
In generic cases, the spectral radius is given by(36)ρ(I-δL-1γT)=max⁡{|1-δλi|:i=2,…,N}.
The eigenvalues here can be complex numbers. When solving this problem, it is important to contain the solution within the domain such that convergence is guaranteed. The domain is defined by(37)|1-δλi|≤1,∀i=2,…,N.
Suppose that λi=αi+iβi; we have that |1-δλi|<1 if and only if(38)0≤δ≤2αi|λi|2.
Therefore, the valid range of δ is(39)0≤δ≤min⁡i=2,…,N2αi|λi|2.
We note that there exists no analytic solution to this problem. However, the objective function is a piece-wise quadratic function, which can be readily solved by first delimiting the pieces and then comparing their respective minimum.The derivation above provides an upper bound of the convergence time and a guideline for choosing the optimalδ. We can see that they are closely related to the spectral characteristics of the Laplacian matrix L. In general, the network converges rapidly when the eigenvalues of I-δL (except the one that equals 1) are small.


## 3.2.1. Symmetric Cases

We first consider the cases where the underlying communication network is symmetric. In these cases, the Laplacian matrixL is symmetric. Let 0=λ1≤⋯≤λN be the eigenvalues of L, which are all nonnegative real values. Since the component 1γT that corresponds to the eigenvalue 1 of Φ is subtracted, the eigenvalues of I-δL-1γT are 0,1-δλ2,…,1-δλN. Since L is symmetric, we have(33)‖I-δL-1γT‖=ρ(I-δL-1γT)=max⁡{|1-δλ2|,|1-δλN|}.
Hence, the optimal choice of δ is given by(34)δ̂=argminδ>0max⁡{|1-δλ2|,|1-δλN|}=2λ2+λN.
Note that δ̂≤2/λN. According to Corollary 2, it follows, that with such an optimal choice, convergence is guaranteed. We also note that Xiao and Boyd [1] obtained similar results in different context.


## 3.2.2. Generic Diagonalizable Cases

In real applications the communication topology is not always symmetric due to difference of devices and deployment environment. Hence, the spectral radius does not necessarily equal the induced norm, we use the spectral radius in place of the induced norm; leading to the following objective in choosing optimalδ:(35)δ̂=argminδ≥0ρ(I-δL-1γT).
In generic cases, the spectral radius is given by(36)ρ(I-δL-1γT)=max⁡{|1-δλi|:i=2,…,N}.
The eigenvalues here can be complex numbers. When solving this problem, it is important to contain the solution within the domain such that convergence is guaranteed. The domain is defined by(37)|1-δλi|≤1,∀i=2,…,N.
Suppose that λi=αi+iβi; we have that |1-δλi|<1 if and only if(38)0≤δ≤2αi|λi|2.
Therefore, the valid range of δ is(39)0≤δ≤min⁡i=2,…,N2αi|λi|2.
We note that there exists no analytic solution to this problem. However, the objective function is a piece-wise quadratic function, which can be readily solved by first delimiting the pieces and then comparing their respective minimum.The derivation above provides an upper bound of the convergence time and a guideline for choosing the optimalδ. We can see that they are closely related to the spectral characteristics of the Laplacian matrix L. In general, the network converges rapidly when the eigenvalues of I-δL (except the one that equals 1) are small.


## 3.3. More Accurate Analysis of the Convergence Time

As mentioned above, the actual convergence time also depends on the initial statesx(0), and the input signals y, as well as the tolerance threshold ε. Here, we take a close examination of such dependency.Suppose thatL is diagonalizable with eigenvalues 0=λ1<λ2≤⋯≤λN. Let ej be the eigenvector associated with the eigenvalue λi for each i=1,…,N. Since L is diagonalizable, these eigenvectors span the entire state space, and as a consequence, the vector h=Lx(0)-y can be expressed as a linear combination of them, as(40)h=∑i=1Nciei.
Let ℛ(L)={Lv:v∈ℝN} be the range space of L. Since the underlying network is connected, the null space of L is one dimensional. Hence, ℛ(L) has dimension N-1 and is spanned by e2,…,eN. Clearly, the second derivatives ẍδ(n)=L(I-δL)n-2h∈ℛ(L) and thus can be expressed to be a linear combination of e2,…,eN, as(41)ẍδ(n)=∑i=2Nciλi(1-δλi)n-2ei.
We can see that the ith term decreases geometrically with shrinking ratio |1-δλi|. Asymptotically, the term with greatest shrinking ratio, namely, the one that attenuates most slowly, will dominate in a long run.LetC:ℛ(L)→ℛ(L) be a coordinate transform that maps each vector in ℛ(L) to the coefficients with respect to the basis {e2,…,eN}. This is a bijective linear map. For each vector v∈ℛ(L), we define(42)‖v‖∞/C=‖C(v)‖∞.
It can be easily shown that ∥·∥∞/C is a norm on ℛ(L). To characterize the relations between ∥·∥∞/C and ∥·∥∞, we define(43)κC≜sup⁡v∈R(L)‖v‖∞‖v‖∞/C.
In other words, κC is the greatest real value that satisfies(44)‖v‖∞≤κC‖v‖∞/C,∀v∈R(L).
By the equivalence of norms on a finite dimensional vector space, we have 0<κC<+∞; that is, κC is a finite positive value. Consider the second derivatives ẍδ(n). To have ∥ẍδ(n)∥∞<ε, it suffices to have(45)‖ẍδ(n)‖∞/C<εκC.
From the definition of ∥·∥∞/C and (41), we get(46)‖ẍδ(n)‖∞/C=max⁡i=2,…,N|ciλi(1-δλi)n-2|.
As a result, when(47)n>max⁡i=2,…,Nlog⁡(κC|ciλi|/ε)log⁡(1/|1-δλi|)+2,∥ẍδ(n)∥<ε, implying that the sensor network attains the consensus within the tolerable range. Based on this bound, the optimal choice δ is given by(48)δ̂=argminδ>0max⁡i=2,…,Nlog⁡⁡(κC|ciλi|/ε)log⁡⁡(1/|1-δλi|).
This result indicates that with the knowledge of input signals, one can derive an improved upper bound, and a proper choice for δ, which relates not only to the underlying graph, but also to the initial states, input signals, and the tolerance threshold ε.However, directly applying this result in practice is infeasible, as the input signals are unavailable in advance; otherwise, we do not even have to deploy a sensor network to measure them. The true significance of this result lies is that it suggests that we can incorporate domain-specific knowledge to make a better design of the sensor network.Specifically, while the exact input is unknown before we really perform the measurement, we generally have some rough knowledge about what the input might be, which could be formulated as a prior distribution of the input signals and then be exploited to guide the choice ofδ. From such a prior model, one can derive the prior distribution of the coefficients c=[c2,…,cN]T, denoted by p(c). Then, we obtain an upper bound of the expected convergence time, as(49)UT(δ;p)=∫max⁡i=2,…,Nlog⁡(κC|ciλi|/ε)log⁡(1/|1-δλi|)p(c)dc.
With this model, one can choose an optimal δ that minimizes UT(δ;p). Though it might be difficult to directly solve this problem, one can resort to various techniques to make further approximation.


## 4. Simulation

In this section, we will illustrate the following key results. First, the consensus rate and the choice of optimal iteration weightδ are dependent on the self-aware criterion ε for a sensor network where communication links are symmetric and asymmetric. Second, the analysis of determining the optimal δ provided in previous section is consistent with the simulation result with various ε’s, which greatly helps designing efficient and energy-saving sensor network for different topologies.


### 4.1. Symmetric Topology

We first consider the symmetric network shown in Figure1, which has 12 nodes and 24 links. This network was randomly generated with arbitrarily chosen initial state value x(0) and input y as follows:(50)x(0)=[0,10,20,…,110],y=[30,30,30,30,70,70,70,70,50,50,50,50].The coupling coefficientaij is defined to equal 1 if there is signal transmitted from node j to node i; otherwise, aij=0. For the network shown in Figure 1, Figure 3 shows through simulation the number of iterations required to achieve consensus as a function of the weight parameter (δ—x-axis) and the self-aware criteria (ε—various curves). For this network, the best iteration weight found from earlier work by (34) is δ̂=0.3802 (illustrated in Figure 3 by the vertical line). However, we can see from Figure 3 that the three curves with ε=0.001, ε=0.01, and ε=0.1 reach the lowest point at about 0.37, 0.36, and 0.35, which means setting the iteration weight δ to each of those values would get convergence by fewest iterations based on each network operator ε. Consensus with these values is achieved in significantly fewer iterations, and, most importantly, convergence is determined by local criterion. As ε increases, the whole curve moves to the left slightly. Though the change in the selection of δ is comparatively small with different threshold ε, we can find that the minimal iterations for reaching consensus drop largely, from 124 to 85, then fall off to 40. If one uses δ̂=0.3802 as determined by (34) and the criteria presented in [1], the system would require much more than 200 iterations to achieve consensus.Figure 3
Minimal number of iterations for aN=12 symmetric network with different consensus criteria ε’s.By solving (41) as a function of criterion ε, we found the relation between ε and minimal number of iterations and the relation between ε and optimal δ. As shown in Figures 4 and 5, the analytical results are very consistent with the simulation. we can see that the minimal number of iterations decreases as the threshold ε increases. When ε goes from 0.001 to 0.1, the minimal number of iterations keeps dropping from 125 to 40, which shows that achieving consensus with slightly different ε would make a difference in the number of communication iterations. There is a tradeoff between the consensus precision and the number of communications, or energy consuming. Realizing that, it is desirable to choose a larger criterion ε to make sensor nodes live longer, as long as it meets the specific application requirement of the sensor network.Figure 4
Minimal number of iterations versusε for a symmetric topology.Figure 5
Optimal iteration weightδ versus ε for a symmetric topology.


### 4.2. Asymmetric Topology

Next, we consider another 12-node network shown in Figure6 with an asymmetric communication topology. Using the same initial value and input as the above example, we show that the optimal iteration weight δ as well as the minimal number of iterations varies with different network operators ε’s in Figure 7. Similar to the symmetric example, it can be seen that as ε increases, the corresponding δ would be reduced slightly, while the minimal number of iterations would decrease in a big way. For this asymmetric network, the theoretical best weight found from (35) is 0.3466, which is also denoted in Figure 7 by the vertical line. Again, this theoretical “best weight" is obviously different with the real practical best choice of δ; applying the “best weight" to the practical systems would yield many more iterations for network to reach consensus. As illustrated by Figures 8 and 9, the performances of minimal number of iterations and optimal δ with ε for asymmetric topology present similar behaviors as those of symmetric topology.Figure 6
Schematic diagram of a asymmetric network,N=12; degree=2.Figure 7
Minimal number of iterations for aN = 12 asymmetric network with different consensus criteria ε’s.Figure 8
Minimal number of iterations versusε for an asymmetric topology.Figure 9
Optimal iteration weightδ versus ε for an asymmetric topology.


## 4.1. Symmetric Topology

We first consider the symmetric network shown in Figure1, which has 12 nodes and 24 links. This network was randomly generated with arbitrarily chosen initial state value x(0) and input y as follows:(50)x(0)=[0,10,20,…,110],y=[30,30,30,30,70,70,70,70,50,50,50,50].The coupling coefficientaij is defined to equal 1 if there is signal transmitted from node j to node i; otherwise, aij=0. For the network shown in Figure 1, Figure 3 shows through simulation the number of iterations required to achieve consensus as a function of the weight parameter (δ—x-axis) and the self-aware criteria (ε—various curves). For this network, the best iteration weight found from earlier work by (34) is δ̂=0.3802 (illustrated in Figure 3 by the vertical line). However, we can see from Figure 3 that the three curves with ε=0.001, ε=0.01, and ε=0.1 reach the lowest point at about 0.37, 0.36, and 0.35, which means setting the iteration weight δ to each of those values would get convergence by fewest iterations based on each network operator ε. Consensus with these values is achieved in significantly fewer iterations, and, most importantly, convergence is determined by local criterion. As ε increases, the whole curve moves to the left slightly. Though the change in the selection of δ is comparatively small with different threshold ε, we can find that the minimal iterations for reaching consensus drop largely, from 124 to 85, then fall off to 40. If one uses δ̂=0.3802 as determined by (34) and the criteria presented in [1], the system would require much more than 200 iterations to achieve consensus.Figure 3
Minimal number of iterations for aN=12 symmetric network with different consensus criteria ε’s.By solving (41) as a function of criterion ε, we found the relation between ε and minimal number of iterations and the relation between ε and optimal δ. As shown in Figures 4 and 5, the analytical results are very consistent with the simulation. we can see that the minimal number of iterations decreases as the threshold ε increases. When ε goes from 0.001 to 0.1, the minimal number of iterations keeps dropping from 125 to 40, which shows that achieving consensus with slightly different ε would make a difference in the number of communication iterations. There is a tradeoff between the consensus precision and the number of communications, or energy consuming. Realizing that, it is desirable to choose a larger criterion ε to make sensor nodes live longer, as long as it meets the specific application requirement of the sensor network.Figure 4
Minimal number of iterations versusε for a symmetric topology.Figure 5
Optimal iteration weightδ versus ε for a symmetric topology.


## 4.2. Asymmetric Topology

Next, we consider another 12-node network shown in Figure6 with an asymmetric communication topology. Using the same initial value and input as the above example, we show that the optimal iteration weight δ as well as the minimal number of iterations varies with different network operators ε’s in Figure 7. Similar to the symmetric example, it can be seen that as ε increases, the corresponding δ would be reduced slightly, while the minimal number of iterations would decrease in a big way. For this asymmetric network, the theoretical best weight found from (35) is 0.3466, which is also denoted in Figure 7 by the vertical line. Again, this theoretical “best weight" is obviously different with the real practical best choice of δ; applying the “best weight" to the practical systems would yield many more iterations for network to reach consensus. As illustrated by Figures 8 and 9, the performances of minimal number of iterations and optimal δ with ε for asymmetric topology present similar behaviors as those of symmetric topology.Figure 6
Schematic diagram of a asymmetric network,N=12; degree=2.Figure 7
Minimal number of iterations for aN = 12 asymmetric network with different consensus criteria ε’s.Figure 8
Minimal number of iterations versusε for an asymmetric topology.Figure 9
Optimal iteration weightδ versus ε for an asymmetric topology.


## 5. Conclusion

In this work, the problem of achieving consensus among distributed sensor nodes has been considered. In particular, a potential answer to the question on how do individual nodes “know” when consensus is achieved is presented. The work introduces a local “self-aware” criterion,ε, which in practice is consensus rate of the parameter under consideration. The work illustrates (1) that ε, as expected, will influence the number of iterations required but more importantly (2) that existing criteria for the weighting functions is not appropriate for that will lead to an increased number of energy-consuming iterations. The work also considers the impact of nonsymmetric links on achieving consensus. These results address practical considerations regarding implementing distributed consensus building in “real" sensor networks. As such, it is hoped that this work will motivate others to consider implementation issues in this domain.



---

*Source: 860936-2011-12-19.xml*