# Convergence Rate Estimate of Distributed Localization Algorithms in Wireless Sensor Networks

Authors: Shujuan Pang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

Localization is one of the most important problems in wireless sensor networks. In this paper, we investigate the convergence rate estimate problem of a distributed localization algorithm which approximately formulates the localization problem as the convex feasibility problem including the consistent case and the inconsistent case. Although existing works established optimal consensus convergence analysis for this algorithm, they did not provide the convergence rate estimate. In this paper, we mainly show that for the consistent case the convergence rate of the optimal consensus will be exponential under some basic conditions, while for the inconsistent case we provide a necessary condition for the optimal consensus and a convergence rate estimate inequality. Furthermore, numerical examples are also provided to validate the established convergence and convergence rate results.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) have attracted considerable research interest from the scientific community and localization is one of the most important problems in WSNs. The objective of localization is to locate the source sensor based on a large number of low-cost sensor nodes with limited computational capacities. Recently, some methods have been proposed in the literature for localization in WSNs, for instance, the maximum likelihood estimation [1], nonlinear least squares [2], convex relaxation methods [3], and projection-based methods [4, 5].In recent years, distributed algorithms also appear to solve the localization problems [6–9]. Compared with distributed algorithms, a main disadvantage of centralized algorithms, for example, the parallel projection approaches in [4, 5], is that they require a fusion center to gather, compute, and process the information received from all the sensor nodes, and then centralized algorithms are prone to a single point of failure. In distributed algorithms, sensor nodes can accomplish the localization task cooperatively by only local information exchange with their closest neighboring sensors over a strongly connected graph.The authors in [7] proposed a distributed incremental gradient algorithm to solve the nonlinear least squares problem. The authors in [8] proposed a distributed asynchronous algorithm to deal with the maximum likelihood convex relaxation problem. A well-known distributed projection-based algorithm was proposed in [6] to solve the localization problem, where the authors formulated approximately the localization problem as a convex feasibility problem including the consistent case (the intersection of sensors’ sensing sets is nonempty) and inconsistent case (the intersection of sensors’ sensing sets is empty) following detailed convergence analysis. Recently, the authors in [9] also proposed a similar projection-based distributed algorithm to solve the localization problem, where the authors formulated the localization problem as a ring intersection problem instead of the ball intersection problem given in [6].In this paper, we will consider the convergence rate estimate problem of the distributed localization algorithm proposed in [6]. Although the authors in [6] provided the detailed convergence analysis, they did not give the convergence rate estimate. To be specific, we will show that, for the consistent case, the convergence rate of the distributed localization algorithm in [6] is exponential under some basic conditions. For the inconsistent case, we will show that generally diminishing projection stepsize is necessary to guarantee the optimal consensus for the inconsistent case. Moreover, we also provide a convergence rate estimate inequality for the inconsistent case.In fact, the optimal convergence problem for the consistent case is equivalent to convex intersection problem (CIP) that aims to find a point in the nonempty intersection set of many closed convex sets. Distributed algorithms have been proposed to solve CIP in the literature [10–14]. The authors in [10] proposed a distributed projected consensus algorithm to solve CIP with detailed optimal consensus convergence analysis. The authors also showed that the convergence rate of the optimal consensus is exponential for the special case of completely connected network graphs with the same weight. The authors in [14] proposed an approximate projected consensus algorithm to solve CIP in the presence of projection uncertainties described by approximate angles and projection accuracy, where the authors claimed that the convergence rate of optimal consensus for the special case with exact projection (or, equivalently, the projected consensus algorithm in [10]) is not possible to be exponential if the intersection of convex sets has no interior, and the convergence rate estimate problem is still open for general directed graphs. Moreover, to the best of our knowledge, there are also very few results about the convergence rate estimate for the inconsistent case.Motivated by the claim in [14], in this paper we will consider the convergence rate estimate problem of the distributed localization algorithm proposed in [6] (or, equivalently, the distributed approximate projected algorithm in [14] with zero approximate angle) for general directed graphs. The studied algorithm is a generalization of the algorithm in [10] with a projection stepsize, where, before processing the estimates received from their neighboring sensors, sensors first take a weighted average of their current estimates and the projections onto their individual sensing sets (balls) with the projection stepsize as the weighting factor. The main contribution of this paper is summarized as follows:(i)
For the consistent case, we show that, under the conditions of strongly connected interaction graph, nonempty interior assumption of the intersection of sensors’ sensing sets, and sufficiently small constant projection stepsize, the convergence rate of the optimal consensus for the consistent case is exponential. According to the claim in [14], the required exponential convergence rate conditions are basic. To the best of our knowledge, this is the first theoretical result on the convergence rate estimate for general directed graphs.(ii)
For the inconsistent case, we show that, for the optimal consensus convergence, generally it is necessary that the projection stepsize needs to diminish. Moreover, we also present a convergence rate estimate inequality in the presence of the constant projection stepsize, which reveals that, for any specified tolerable convergence error, we can select sufficiently small projection stepsize such that the convergence error between sensors’ estimates and the optimal point falls within the given tolerable error with an exponential rate.The rest of the paper is organized as follows. Section2 shows some preliminary knowledge about graph theory and convex analysis and introduces the source localization problem. Section 3 formulates the convergence rate estimate problem. Section 4 presents the exponential convergence rate result for the consistent case, while Section 5 presents that for the inconsistent case. Finally, the conclusion is provided in Section 6.Notations. · denotes the Euclidean norm of a vector; I2 is the identity matrix; int⁡(K) denotes the set of interior of set K; PK is the projection operator onto closed convex set K; ·K denotes the distance function from closed convex set K; zT denotes the transpose of vector z; ⊗ denotes the Kronecker product; det⁡(A) denotes the determinant of matrix A.


## 2. Preliminaries

In this section, we first present preliminaries about graph theory, convex analysis, and then a localization problem in wireless sensor networks.


### 2.1. Preliminaries

The interaction among the sensors in the wireless sensor network can be conveniently described by a directed graphG=(V,E), where V={1,2,…,N} is the node set (sensors are represented by nodes in this graph) and E⊆V×V is the arc set. Let Ni={j∈V∣(j,i)∈E} denote the set of all neighbors of node i in this graph. j∈Ni means that sensor i can receive the transmitted information from sensor j. In this paper, we assume that graph G contains all self-loops (i.e., (i,i)∈E for all i). Associated with graph G, there is a nonnegative (weighted) adjacency matrix A=(aij)∈RN×N to describe the weights among agents, where aij>0 if and only if (j,i)∈E, or equivalently node j is a neighbor of node i. A path from i to j in graph G is an alternating sequence i(i,i1)i1(i1,i2)⋯is(is,j)j. Graph G is said to be strongly connected if there is a path from i to j for any node pair i,j∈V.We introduce the following properties for convex projection operatorPK.Lemma 1 (see [10, 15, 16]).
LetK be a closed convex set in Rm. Then(i)
f(z)=zK is a convex function;(ii)
PKy-PKz≤y-z for any y and z;(iii)
|y|K≤|z|K+|y-z| for any y and z;(iv)
|PK(y)-z|2≤|y-z|2-|y|K2 for any y∈Rm and z∈K.Here (i) is Example  3.16 in [16], (ii) is the standard nonexpansiveness property of convex projection operator, (iii) takes from Exercise 1.2 (c) on page 23 in [15], and (iv) is borrowed from Lemma 1 (b) in [10]. From (ii) we know that PK(·) is continuous over Rm.The following lemma can be found in [17].Lemma 2.
LetK be a closed convex set in Rm. Then |x|K2 is continuously differentiable and (1)∇xK2=2x-PKx.


### 2.2. Localization in Wireless Sensor Networks

The objective of localization is to determine the location of an active source in a sensor network. Let the unknown coordinate pair of the active source beθ=(θ1,θ2)∈R2, which emits a signal with power level P. We assume that there are N sensors in the sensor network with known coordinate pairs ρi=(yi,zi), i=1,…,N, to perform sensing based on energy detection, where the received signal of sensor i can be written as (2)Pρi=ciPρi-θ2+ϵi,where ci is the gain factor of sensor i and ϵi is the received noise of sensor i, which is assumed to be zero-mean uncorrelated Gaussian process with variance σi2. Here we assume that the signal power P is known by all sensors.By solving the following least squares problem with Gaussian noise, we can obtain the maximum likelihood estimatorθ∗: (3)θ∗∈argmin⁡∑i=1NPρi-ciPρi-θ22.It is easy to see that the objective function |Pρi-ci(P/|ρi-θ|2)|2 achieves its minimum on the circle Ci≔{θ∈R2∣θ-ρi=ciP/Pρi}. However, the source may not appear exactly on the circles {Ci,i=1,…,N} due to the observation noise but appear in some sensing areas described by some rings as the following forms: (4)Di≔θ∈R2∣ciPPρi+ξiσi≤θ-ρi≤ciPPρi-ξiσi,i=1,…,N,where ξiσi indicates the area of noise distribution of sensor i.Due to the nonconvexity of ringsDis, it is extremely difficult to design projection-based algorithms to accomplish the task of localization. As the method given in [6], in this paper we approximately deem that the source appears on the (convex) balls Xis instead of Dis:(5)Xi≔θ∈R2∣θ-ρi≤ciPPρi-ξiσi,i=1,…,N.Then the source localization problem can be solved by letting the estimator be an optimal point x∗ of the optimization problem min⁡∑i=1N‍|x|Xi2. That is,(6)x∗∈argmin⁡∑i=1NxXi2,x∈R2.It is easy to see that the optimal solution set of (6), denoted as X∗, is nonempty due to the boundedness of Xis and the convexity of ·Xi2. Note that the balls Xis maybe have an empty intersection since the amount of observation noise may be large or small.In this paper, we term the case⋂i=1N‍Xi≠∅ as theconsistent case and ⋂i=1N‍Xi=∅ theinconsistent case [6] (see Figure 1 for an illustrative description about the two cases). Clearly, the optimal solution set for the consistent case is the intersection set of Xis, that is, X∗=⋂i=1N‍Xi, and the optimal solution for the inconsistent case is unique since functions ·Xi2s are strictly convex.Figure 1
The consistent case and inconsistent case.


## 2.1. Preliminaries

The interaction among the sensors in the wireless sensor network can be conveniently described by a directed graphG=(V,E), where V={1,2,…,N} is the node set (sensors are represented by nodes in this graph) and E⊆V×V is the arc set. Let Ni={j∈V∣(j,i)∈E} denote the set of all neighbors of node i in this graph. j∈Ni means that sensor i can receive the transmitted information from sensor j. In this paper, we assume that graph G contains all self-loops (i.e., (i,i)∈E for all i). Associated with graph G, there is a nonnegative (weighted) adjacency matrix A=(aij)∈RN×N to describe the weights among agents, where aij>0 if and only if (j,i)∈E, or equivalently node j is a neighbor of node i. A path from i to j in graph G is an alternating sequence i(i,i1)i1(i1,i2)⋯is(is,j)j. Graph G is said to be strongly connected if there is a path from i to j for any node pair i,j∈V.We introduce the following properties for convex projection operatorPK.Lemma 1 (see [10, 15, 16]).
LetK be a closed convex set in Rm. Then(i)
f(z)=zK is a convex function;(ii)
PKy-PKz≤y-z for any y and z;(iii)
|y|K≤|z|K+|y-z| for any y and z;(iv)
|PK(y)-z|2≤|y-z|2-|y|K2 for any y∈Rm and z∈K.Here (i) is Example  3.16 in [16], (ii) is the standard nonexpansiveness property of convex projection operator, (iii) takes from Exercise 1.2 (c) on page 23 in [15], and (iv) is borrowed from Lemma 1 (b) in [10]. From (ii) we know that PK(·) is continuous over Rm.The following lemma can be found in [17].Lemma 2.
LetK be a closed convex set in Rm. Then |x|K2 is continuously differentiable and (1)∇xK2=2x-PKx.


## 2.2. Localization in Wireless Sensor Networks

The objective of localization is to determine the location of an active source in a sensor network. Let the unknown coordinate pair of the active source beθ=(θ1,θ2)∈R2, which emits a signal with power level P. We assume that there are N sensors in the sensor network with known coordinate pairs ρi=(yi,zi), i=1,…,N, to perform sensing based on energy detection, where the received signal of sensor i can be written as (2)Pρi=ciPρi-θ2+ϵi,where ci is the gain factor of sensor i and ϵi is the received noise of sensor i, which is assumed to be zero-mean uncorrelated Gaussian process with variance σi2. Here we assume that the signal power P is known by all sensors.By solving the following least squares problem with Gaussian noise, we can obtain the maximum likelihood estimatorθ∗: (3)θ∗∈argmin⁡∑i=1NPρi-ciPρi-θ22.It is easy to see that the objective function |Pρi-ci(P/|ρi-θ|2)|2 achieves its minimum on the circle Ci≔{θ∈R2∣θ-ρi=ciP/Pρi}. However, the source may not appear exactly on the circles {Ci,i=1,…,N} due to the observation noise but appear in some sensing areas described by some rings as the following forms: (4)Di≔θ∈R2∣ciPPρi+ξiσi≤θ-ρi≤ciPPρi-ξiσi,i=1,…,N,where ξiσi indicates the area of noise distribution of sensor i.Due to the nonconvexity of ringsDis, it is extremely difficult to design projection-based algorithms to accomplish the task of localization. As the method given in [6], in this paper we approximately deem that the source appears on the (convex) balls Xis instead of Dis:(5)Xi≔θ∈R2∣θ-ρi≤ciPPρi-ξiσi,i=1,…,N.Then the source localization problem can be solved by letting the estimator be an optimal point x∗ of the optimization problem min⁡∑i=1N‍|x|Xi2. That is,(6)x∗∈argmin⁡∑i=1NxXi2,x∈R2.It is easy to see that the optimal solution set of (6), denoted as X∗, is nonempty due to the boundedness of Xis and the convexity of ·Xi2. Note that the balls Xis maybe have an empty intersection since the amount of observation noise may be large or small.In this paper, we term the case⋂i=1N‍Xi≠∅ as theconsistent case and ⋂i=1N‍Xi=∅ theinconsistent case [6] (see Figure 1 for an illustrative description about the two cases). Clearly, the optimal solution set for the consistent case is the intersection set of Xis, that is, X∗=⋂i=1N‍Xi, and the optimal solution for the inconsistent case is unique since functions ·Xi2s are strictly convex.Figure 1
The consistent case and inconsistent case.


## 3. Problem Formulation

In this section, we first introduce the distributed localization algorithm given in [6] and then the convergence rate estimate problem for this algorithm.


### 3.1. Distributed Localization Algorithms

We first present a distributed localization algorithm that was introduced in [6]. Consider a sensor network consisting of N sensor nodes with node set V={1,…,N} and their sensing balls X1,…,XN⊆R2 given in (5). The interaction graph among these sensors is described by a directed graph G=(V,E). Each sensor i only knows its own sensing set Xi and can only exchange information with their neighboring sensors. In order to accomplish the localization task, sensors not only need to utilize the information of their own sensing sets, but also need to exchange information with their neighboring sensors.In this paper, we consider the following distributed localization algorithm:(7)xik+1=∑j∈Niaij1-αkxjk+αkPXjxjk,i=1,…,N,where xi(k) is the estimate of sensor i at time k and 0≤αk≤1 is referred to as the projection stepsize. In Algorithm (7), sensors first take a weighted average of their current estimates and the projection points onto their individual sensing sets with αk as the weighting factor and then take a weighted average of the estimates received from their neighboring sensors to generate their estimates at the next step.Remark 3.
The distributed localization algorithm introduced in [6] takes the following form:(8)xik+1=1-αk∑j∈Niaijxjk+αkPXi∑j∈Niaijxjk,which in fact is equivalent to Algorithm (7). Moreover, a lot of distributed algorithms have also been proposed to solve various problems, for example, consensus problems [18, 19], tracking problems [20, 21], and distributed optimization problems [10, 22].Remark 4.
The source localization problem for the consistent case is equivalent to CIP that aims to find a point in the intersectionX0≔⋂i=1N‍Xi of some closed convex sets Xis. Many distributed algorithms have also been proposed to solve CIP, for example, the projected consensus algorithm [10], dynamical system solution method [12], random flip-coin algorithm [11], and approximate projected consensus algorithm [14]. Moreover, notice that the projected consensus algorithm presented in [10] is a special case of Algorithm (7) with αk≡1, and Algorithm (7) is a special case of the approximated projected consensus algorithm in [14] with zero approximate error angle.We next make two assumptions on the adjacency matrixA and the interaction graph G, which are standard in multiagent literature [10, 14].Assumption 5.
(i) The adjacency matrixA is stochastic; that is, ∑j=1N‍aij=1 for each i.
(ii) The adjacency matrixA is doubly stochastic; that is, ∑j=1N‍aij=∑r=1N‍ari=1 for each i.Assumption 6.
The interaction graphG is strongly connected.Here we introduce an optimal consensus convergence result of Algorithm (7), where the first one for consistent case can be obtained from Theorem 4.1 in [14] or Theorem 1 in [6], while the second one for inconsistent case can be found from Proposition 4 in [10].Proposition 7 (optimal consensus convergence).
Consider distributed localization algorithm (7). For the consistent and inconsistent cases, one has the following:(i)
Consistent case:X0≔⋂i=1N‍Xi≠∅. Suppose ∑k=0∞‍αk=∞ and Assumptions 5 (i) and 6 hold. Then Algorithm (7) will achieve an optimal consensus; that is, for any initial condition xi(0), there exists x∗∈X0 such that limk→∞xi(k)=x∗, i=1,…,N.(ii)
Inconsistent case:⋂i=1N‍Xi=∅. Suppose ∑k=0∞‍αk=∞, ∑k=0∞‍αk2<∞, and Assumptions 5 (ii) and 6 hold. Then Algorithm (7) will achieve an optimal consensus; that is, for any initial condition xi(0), limk→∞xi(k)=x∗, i=1,…,N, where x∗ is the unique optimal solution of min∑i=1N‍xXi2.


### 3.2. Convergence Rate Estimate Problem

Although the optimal consensus convergence has been established for distributed localization algorithm (7), the convergence rate results are still few in the literature. The authors in [10] showed that the convergence of optimal consensus of their projected consensus algorithm (or, equivalently, Algorithm (7) with αk=1 for the consistent case) is exponential when the interaction graph is completely connected, the weights between all agents are the same, and the intersection set has nonempty interior. The authors in [14] revealed by an example that the nonempty interior assumption is basic for exponential convergence of optimal consensus for the projected consensus algorithm in [10], and they claim that the convergence rate problem is stillopen for general directed graphs.Here we formally introduce the nonempty interior assumption.Assumption 8.
WhenX0≔⋂i=1N‍Xi≠∅, the intersection set X0 has nonempty interior; that is, there exists z∈X0 such that B(z,ϵ)⊆X0 for some ϵ>0.Note that the optimal consensus result for consistent case does not require Assumption8. In this paper, we will show that, under the additional condition of Assumption 8, the optimal consensus of Algorithm (7) for the consistent case will beexponential when the constant projection stepsize αk≡α is sufficiently small (Section 4). That is, for any initial condition xi(0), i=1,…,N, there exist x∗∈X0, M>0, and 0<λ<1 such that (9)xik-x∗≤Mλk,i=1,…,N,k≥0.Moreover, for the inconsistent case, we will provide a necessary condition for the optimal consensus and a convergence rate estimate inequality (Section 5).


## 3.1. Distributed Localization Algorithms

We first present a distributed localization algorithm that was introduced in [6]. Consider a sensor network consisting of N sensor nodes with node set V={1,…,N} and their sensing balls X1,…,XN⊆R2 given in (5). The interaction graph among these sensors is described by a directed graph G=(V,E). Each sensor i only knows its own sensing set Xi and can only exchange information with their neighboring sensors. In order to accomplish the localization task, sensors not only need to utilize the information of their own sensing sets, but also need to exchange information with their neighboring sensors.In this paper, we consider the following distributed localization algorithm:(7)xik+1=∑j∈Niaij1-αkxjk+αkPXjxjk,i=1,…,N,where xi(k) is the estimate of sensor i at time k and 0≤αk≤1 is referred to as the projection stepsize. In Algorithm (7), sensors first take a weighted average of their current estimates and the projection points onto their individual sensing sets with αk as the weighting factor and then take a weighted average of the estimates received from their neighboring sensors to generate their estimates at the next step.Remark 3.
The distributed localization algorithm introduced in [6] takes the following form:(8)xik+1=1-αk∑j∈Niaijxjk+αkPXi∑j∈Niaijxjk,which in fact is equivalent to Algorithm (7). Moreover, a lot of distributed algorithms have also been proposed to solve various problems, for example, consensus problems [18, 19], tracking problems [20, 21], and distributed optimization problems [10, 22].Remark 4.
The source localization problem for the consistent case is equivalent to CIP that aims to find a point in the intersectionX0≔⋂i=1N‍Xi of some closed convex sets Xis. Many distributed algorithms have also been proposed to solve CIP, for example, the projected consensus algorithm [10], dynamical system solution method [12], random flip-coin algorithm [11], and approximate projected consensus algorithm [14]. Moreover, notice that the projected consensus algorithm presented in [10] is a special case of Algorithm (7) with αk≡1, and Algorithm (7) is a special case of the approximated projected consensus algorithm in [14] with zero approximate error angle.We next make two assumptions on the adjacency matrixA and the interaction graph G, which are standard in multiagent literature [10, 14].Assumption 5.
(i) The adjacency matrixA is stochastic; that is, ∑j=1N‍aij=1 for each i.
(ii) The adjacency matrixA is doubly stochastic; that is, ∑j=1N‍aij=∑r=1N‍ari=1 for each i.Assumption 6.
The interaction graphG is strongly connected.Here we introduce an optimal consensus convergence result of Algorithm (7), where the first one for consistent case can be obtained from Theorem 4.1 in [14] or Theorem 1 in [6], while the second one for inconsistent case can be found from Proposition 4 in [10].Proposition 7 (optimal consensus convergence).
Consider distributed localization algorithm (7). For the consistent and inconsistent cases, one has the following:(i)
Consistent case:X0≔⋂i=1N‍Xi≠∅. Suppose ∑k=0∞‍αk=∞ and Assumptions 5 (i) and 6 hold. Then Algorithm (7) will achieve an optimal consensus; that is, for any initial condition xi(0), there exists x∗∈X0 such that limk→∞xi(k)=x∗, i=1,…,N.(ii)
Inconsistent case:⋂i=1N‍Xi=∅. Suppose ∑k=0∞‍αk=∞, ∑k=0∞‍αk2<∞, and Assumptions 5 (ii) and 6 hold. Then Algorithm (7) will achieve an optimal consensus; that is, for any initial condition xi(0), limk→∞xi(k)=x∗, i=1,…,N, where x∗ is the unique optimal solution of min∑i=1N‍xXi2.


## 3.2. Convergence Rate Estimate Problem

Although the optimal consensus convergence has been established for distributed localization algorithm (7), the convergence rate results are still few in the literature. The authors in [10] showed that the convergence of optimal consensus of their projected consensus algorithm (or, equivalently, Algorithm (7) with αk=1 for the consistent case) is exponential when the interaction graph is completely connected, the weights between all agents are the same, and the intersection set has nonempty interior. The authors in [14] revealed by an example that the nonempty interior assumption is basic for exponential convergence of optimal consensus for the projected consensus algorithm in [10], and they claim that the convergence rate problem is stillopen for general directed graphs.Here we formally introduce the nonempty interior assumption.Assumption 8.
WhenX0≔⋂i=1N‍Xi≠∅, the intersection set X0 has nonempty interior; that is, there exists z∈X0 such that B(z,ϵ)⊆X0 for some ϵ>0.Note that the optimal consensus result for consistent case does not require Assumption8. In this paper, we will show that, under the additional condition of Assumption 8, the optimal consensus of Algorithm (7) for the consistent case will beexponential when the constant projection stepsize αk≡α is sufficiently small (Section 4). That is, for any initial condition xi(0), i=1,…,N, there exist x∗∈X0, M>0, and 0<λ<1 such that (9)xik-x∗≤Mλk,i=1,…,N,k≥0.Moreover, for the inconsistent case, we will provide a necessary condition for the optimal consensus and a convergence rate estimate inequality (Section 5).


## 4. Consistent Case

In this subsection, we present the convergence rate result of Algorithm (7) for the consistent case X0≔⋂i=1N‍Xi≠∅. We first introduce two lemmas. The first one can be shown similarly by the arguments in the proof of Lemma 5 in [10].Lemma 9.
LetK be a closed convex set in Rm. Let {zk}k≥0 be a sequence converging to z∗∈K and satisfy that |zk+1-z|≤|zk-z|+εk for all z∈K and all k, where ∑k=0∞‍εk<∞. Then (10)zk-z∗≤2zkK+∑p=k∞εp∀k≥0.Here is the exponential convergence rate result for consistent case. Its proof is given in the Appendix.Theorem 10 (exponential convergence rate for consistent case).
Consider distributed localization algorithm (7). Suppose X0≔⋂i=1N‍Xi≠∅, the projection stepsize 0<αk≡α<1 is a constant, and Assumptions 5 (i), 6, and 8 hold. Then there exists α∗>0 such that when 0<α≤α∗, Algorithm (7) will achieve an optimal consensus with an exponential convergence rate.If the interaction graph is fixed and completely connected with the same weightaij=1/N, for all i,j, then h(r)=0 and xi(k)=x¯(k) for all i and r≥1. From (A.2) and (A.4) in the Appendix, we have that, for each i, (11)xik+1X0≤1-α+αρ¯xikX0,k≥0.It follows from Lemma 9 that the following corollary holds, which is consistent with the convergence rate result in [10] (referring to Proposition 3 therein for details). Figure 2 presents a completely connected graph with four sensor nodes.Figure 2
A completely connected graph with four nodes.Corollary 11.
If the graphG is completely connected with weights aij=1/N, for all i,j, then an optimal consensus will be achieved with exponential convergence rate 1-α+αρ¯(<1).Example 12.
Here we give an example to validate the convergence and convergence rate results of Algorithm (7) with the consistent case. Consider a network consisting of four sensors with node set V={1,2,3,4}. Suppose the centers of the sensing balls Xi⊆R2, i=1,2,3,4, are ρ1=(1,0), ρ2=(0,1), ρ3=(-1,0), and ρ4=(0,-1) and all the radiuses are 1.4.We consider the following three classes of interaction graphs: chains, cycles, and stars with respective adjacency matrices(12)
A
c
h
a
i
n
=
1
2
1
2
0
0
1
3
1
3
1
3
0
0
1
3
1
3
1
3
0
0
1
2
1
2
,
A
c
y
c
l
e
=
1
2
0
0
1
2
1
2
1
2
0
0
0
1
2
1
2
0
0
0
1
2
1
2
,
A
s
t
a
r
=
1
4
1
4
1
4
1
4
1
2
1
2
0
0
1
2
0
1
2
0
1
2
0
0
1
2
,which are shown in Figure 3.Figure 3
Three classes of interaction graphs: chains, cycles, and stars.(i) We first present the state trajectories of the four agents fromk=0 to k=500, where the interaction graph is a chain with adjacency matrix Achain. The initial condition is xi(0)=(-5,5), i=1,2,3, x4(0)=(-5,-5), and the constant projection stepsize is α=0.2. Figure 4 shows that the four agents achieve an optimal consensus; that is, all nodes converge to a common point in the intersection set.Figure 4
The trajectories show that the four agents achieve an optimal consensus.(ii) Here we present the convergence rate estimate for the above three classes of graphs. It is easy to see the intersection setX0=⋂i=14‍Xi has nonempty interior. Let the initial condition be xi(0)=(-500,500), i=1,2,3,4. We present the convergence rate estimate in terms of the measure (13)Cα=∑i=14∑k=029xik+1-x∗/xik-x∗120,where x∗=∑i=14‍xi(59)/4 is used to approximately substitute the consensus point of the four agents in the network.Figure5 roughly shows that the convergence rate of the four agents is exponential. From Figure 5 we can also find that the convergence rate depends on the interaction graph structure and the projection stepsize, as revealed in [14]. Moreover, Figure 5 also roughly shows that the larger projection stepsize will lead to a faster convergence rate. Based on these observations, we conjecture that the convergence rate of the optimal consensus for Algorithm (7) is always exponential for any constant projection stepsize 0<αk≡α≤1. However, the strict proof of the above conjecture is extremely hard and is also open.Figure 5
The exponential convergence rate estimate for graphs: chains, cycles, and stars.


## 5. Inconsistent Case

In this section, for the inconsistent case⋂i=1N‍Xi=∅, we will establish a necessary condition of optimal consensus and a convergence rate estimate inequality when the graph is completely connected and the projection stepsize is a constant.We first provide a lemma with proof provided in the Appendix.Lemma 13.
LetK be a ball in Rm, z¯∉K. Then for any bounded set S that contains z¯, there exists l(S)>0 such that (14)z-z¯,∇zK2-∇z¯K2≥lSz-z¯2,∀z∈S.Here is the main result for the inconsistent case. Its proof is also given in the Appendix.Theorem 14.
Consider distributed localization algorithm (7). Suppose ⋂i=1N‍Xi=∅ and Assumptions 5 (ii) and 6 hold.
(i) Ifdet⁡(A)≠0 and Algorithm (7) achieves an optimal consensus for any initial condition, then limk→∞αk=0.
(ii) Suppose the graphG is completely connected with the same weight aij=1/N, ∀i,j, and the projection stepsize is a constant: 0<αk≡α<1. Let S=co{xi(k),Xi,i=1,…,N,k≥0} be the bounded set containing all agents’ estimates. Then (15)x¯k+1-x∗2≤1-αNlSx¯k-x∗2+α2L,where L≔supz∈S,i=1,…,N|z|Xi2<∞.Theorem14 (i) reveals that generally the convergence rate for the inconsistent case is impossible to be exponential. Intuitively, when the projection stepsize {αk} diminishes, the optimization term (played by αk(PXi(xi(k))-xi(k))) will become smaller. From Theorem 14 (ii) we can find that, for any specified tolerable convergence error ϵ, we can select sufficiently small projection stepsize α (α≤ϵ/L) such that the convergence error |x¯(k)-x∗|2 between agents’ estimates x¯(k) and the optimal point x∗ falls within the given error ϵ with an exponential rate 1-(α/N)l(S).Example 15.
Here we give an example to validate the convergence and convergence rate estimate results of Algorithm (7) with the inconsistent case. We still consider the network in Example 12. Suppose the centers of balls Xi⊆R2, i=1,2,3,4, are ρ1=(1.5,0), ρ2=(0,1.5), ρ3=(-1.5,0), and ρ4=(0,-1.5) and all the radiuses are one. It is easy to see that the intersection of Xis is empty and the unique optimal solution of min⁡∑i=14‍|x|Xi2 is the origin point (0,0).
(i) We first present the convergence of optimal consensus fromk=0 to k=5000, where the interaction graph is a chain with the following doubly stochastic adjacency matrix Achaind: (16)
A
c
h
a
i
n
d
=
1
2
1
2
0
0
1
2
1
3
1
6
0
0
1
6
1
3
1
2
0
0
1
2
1
2
.Let the initial condition be xi(0)=(-5,5), i=1,2,3, x40=(-5,-5), and let the time-varying projection stepsize be αk=1/(k+5) that satisfies the condition given in Proposition 7 (ii). Figure 6 shows that the optimal consensus can be achieved.
(ii) Here we give an example to validate Theorem14 (i). The interaction graph, adjacency matrix, and the initial condition are the same as those in (i). The projection stepsize is α=0.1. Figure 7 shows that when the projection stepsize is a constant, there is a positive lower bound between agents’ estimates and the optimal solution (0,0).
(iii) We now present an example to validate Theorem14 (ii). The interaction graph is completely connected with doubly stochastic adjacency matrix (17)
A
c
o
m
=
1
4
1
4
1
4
1
4
1
4
1
4
1
4
1
4
1
4
1
4
1
4
1
4
1
4
1
4
1
4
1
4
,and the initial condition is xi(0)=(-100,100), i=1,2,3,4.
We use the measureD(α)=∑k=1100‍(|x¯(k+1)|B0,r0/|x¯(k)|B0,r0)/100 with r0=|x¯(101)| to approximately estimate the convergence rate of agents’ estimates falling within the ball with the final convergence error as the radius. Here we view approximately the distance |x¯(101)| between agents’ estimate x¯(101) at time 101 and the optimal solution (0,0) as the final convergence error.Figure 6
The trajectories show that the four agents converge to the optimal solution(0,0). The diamond indicates the unique optimal solution (0,0).Figure 7
Agents will not converge to the optimal solution(0,0) when the projection stepsize is a positive constant.From Figure8 we can find that a larger projection stepsize α will lead to a faster convergence rate of agents’ estimates falling within the final convergence error. This observation is consistent with the theoretical result of Theorem 14 (ii) (see the established convergence rate 1-(α/N)l(S)).Figure 8
Convergence rate estimate of agents’ estimate falling within the final convergence error.


## 6. Conclusion

In this paper, convergence rate estimate problem of the optimal consensus for a distributed localization algorithm was investigated. We showed that, under the strong connectedness and nonempty interior assumption, the optimal consensus for the consistent case will be achieved with an exponential convergence rate if the constant projection stepsize is sufficiently small. For the inconsistent case, a necessary condition and a convergence rate estimate for optimal consensus were also provided.There are many other topics worth investigating and my future work will mainly focus on the following. (1) As pointed out in this paper, I conjecture that the convergence rate for the consistent case is also exponential for any projection stepsize. The strict proof of this conjecture is extremely difficult and is still open in the literature. The main difficulty lies in that, for general directed graphs, the difference dynamics of agents’ estimate and convergence dynamics to the nonempty intersection set are coupled closely together and it is hard to present a more tight estimate for them to obtain a linear iteration equation with an asymptotically stable system matrix. (2) In this paper, I approximately formulate the localization problem as a convex intersection problem of some balls. However, it is more practical to formulate the localization problem using rings instead of balls. So it is certainly very interesting to extend the current convergence rate results to the more general distributed ring intersection setting.



---

*Source: 523285-2015-06-16.xml*