Convergence Rate Estimate of Distributed Localization Algorithms in Wireless Sensor Networks

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.

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. Section 2 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. $\left|·\right|$ denotes the Euclidean norm of a vector; $I_{\mathrm{2}}$ is the identity matrix; $\text{int}(K)$ denotes the set of interior of set K; $P_K$ is the projection operator onto closed convex set K; ${\left|·\right|}_K$ denotes the distance function from closed convex set K; $z^T$ denotes the transpose of vector z; ⊗ denotes the Kronecker product; $\text{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 graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ , where $\mathcal{V}=\{\mathrm{1,2},\dots ,N\}$ is the node set (sensors are represented by nodes in this graph) and $\mathcal{E}\subseteq \mathcal{V}\times \mathcal{V}$ is the arc set. Let ${\mathcal{N}}_i=\{j\in \mathcal{V}\hspace{0.17em}|\hspace{0.17em}(j,i)\in \mathcal{E}\}$ denote the set of all neighbors of node i in this graph. $j\in {\mathcal{N}}_i$ means that sensor i can receive the transmitted information from sensor j. In this paper, we assume that graph $\mathcal{G}$ contains all self-loops (i.e., $(i,i)\in \mathcal{E}$ for all i). Associated with graph $\mathcal{G}$ , there is a nonnegative (weighted) adjacency matrix $A=(a_{ij})\in {\mathfrak{R}}^{N\times N}$ to describe the weights among agents, where $a_{ij}>\mathrm{0}$ if and only if $(j,i)\in \mathcal{E}$ , or equivalently node j is a neighbor of node i. A path from i to j in graph $\mathcal{G}$ is an alternating sequence $i(i,i_{\mathrm{1}})i_{\mathrm{1}}(i_{\mathrm{1}},i_{\mathrm{2}})\cdots i_s(i_s,j)j$ . Graph $\mathcal{G}$ is said to be strongly connected if there is a path from i to j for any node pair $i,j\in \mathcal{V}$ .

We introduce the following properties for convex projection operator $P_K$ .

Lemma 1 (see [10, 15, 16]).

Let K be a closed convex set in ${\mathfrak{R}}^m$ . Then

• (i)

$f(z)={\left|z\right|}_K$ is a convex function;

(ii)

$\left|P_K\left(y\right)-P_K\left(z\right)\right|\le \left|y-z\right|$ for any y and z;

(iii)

$|y{|}_K\le |z{|}_K+|y-z|$ for any y and z;

(iv)

$|P_K(y)-z{|}^{\mathrm{2}}\le |y-z{|}^{\mathrm{2}}-|y{|}_K^{\mathrm{2}}$ for any $y\in {\mathfrak{R}}^m$ and $z\in 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 $P_K(·)$ is continuous over ${\mathfrak{R}}^m$ .

The following lemma can be found in [17].

Lemma 2.

Let K be a closed convex set in ${\mathfrak{R}}^m$ . Then $|x{|}_K^{\mathrm{2}}$ is continuously differentiable and

$$\begin{array}{cc}& \nabla {\left|x\right|}_K^{\mathrm{2}}=\mathrm{2}\left(x-P_K\left(x\right)\right).\end{array}$$

(1)

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 $\theta =({\theta }_{\mathrm{1}},{\theta }_{\mathrm{2}})\in {\mathfrak{R}}^{\mathrm{2}}$ , which emits a signal with power level P. We assume that there are N sensors in the sensor network with known coordinate pairs ${\rho }_i=(y_i,z_i)$ , $i=\mathrm{1},\dots ,N$ , to perform sensing based on energy detection, where the received signal of sensor i can be written as

$$\begin{array}{cc}& P_{{\rho }_i}=c_i\frac{P}{{\left|{\rho }_i-\theta \right|}^{\mathrm{2}}}+{ϵ}_i,\end{array}$$

(2)

where $c_i$ 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 ${\sigma }_i^{\mathrm{2}}$ . 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 ${\theta }^{\ast }$ :

$$\begin{array}{cc}& {\theta }^{\ast }\in \text{arg}\hspace{0.17em}\text{min}{\displaystyle \sum }_{i=\mathrm{1}}^N{\left|P_{{\rho }_i}-c_i\frac{P}{{\left|{\rho }_i-\theta \right|}^{\mathrm{2}}}\right|}^{\mathrm{2}}.\end{array}$$

(3)

It is easy to see that the objective function $|P_{{\rho }_i}-c_i(P/|{\rho }_i-\theta {|}^{\mathrm{2}}){|}^{\mathrm{2}}$ achieves its minimum on the circle ${\mathcal{C}}_i≔\{\theta \in {\mathfrak{R}}^{\mathrm{2}}\hspace{0.17em}|\hspace{0.17em}\left|\theta -{\rho }_i\right|=\sqrt{c_{i}P/P_{{\rho }_i}}\}$ . However, the source may not appear exactly on the circles $\{{\mathcal{C}}_i,i=\mathrm{1},\dots ,N\}$ due to the observation noise but appear in some sensing areas described by some rings as the following forms:

$$\begin{array}{l}{\mathcal{D}}_i\\ ≔\left\{\theta \in {\mathfrak{R}}^{\mathrm{2}}\hspace{0.17em}|\hspace{0.17em}\sqrt{\frac{c_{i}P}{P_{{\rho }_i}+{\xi }_i{\sigma }_i}}\le \left|\theta -{\rho }_i\right|\le \sqrt{\frac{c_{i}P}{P_{{\rho }_i}-{\xi }_i{\sigma }_i}}\right\},\\ i=\mathrm{1},\dots ,N,\end{array}$$

(4)

where ${\xi }_i{\sigma }_i$ indicates the area of noise distribution of sensor i.

Due to the nonconvexity of rings ${\mathcal{D}}_i$ s, 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 $X_i$ s instead of ${\mathcal{D}}_i$ s:

$$\begin{array}{l}{X}_i≔\left\{\theta \in {\mathfrak{R}}^{\mathrm{2}}\hspace{0.17em}|\hspace{0.17em}\left|\theta -{\rho }_i\right|\le \sqrt{\frac{c_{i}P}{P_{{\rho }_i}-{\xi }_i{\sigma }_i}}\right\},\\ i=\mathrm{1},\dots ,N.\end{array}$$

(5)

Then the source localization problem can be solved by letting the estimator be an optimal point $x^{\ast }$ of the optimization problem $\text{min}{\sum }_{i=\mathrm{1}}^N‍|x{|}_{X_i}^{\mathrm{2}}$ . That is,

$$\begin{array}{cc}& x^{\ast }\in \text{arg}\hspace{0.17em}\text{min}{\displaystyle \sum }_{i=\mathrm{1}}^N{\left|x\right|}_{X_i}^{\mathrm{2}},x\in {\mathfrak{R}}^{\mathrm{2}}.\end{array}$$

(6)

It is easy to see that the optimal solution set of (6), denoted as $X^{\ast }$ , is nonempty due to the boundedness of $X_i$ s and the convexity of ${\left|·\right|}_{X_i}^{\mathrm{2}}$ . Note that the balls $X_i$ s maybe have an empty intersection since the amount of observation noise may be large or small.

In this paper, we term the case ${\bigcap }_{i=\mathrm{1}}^N‍X_i\ne \varnothing$ as the consistent case and ${\bigcap }_{i=\mathrm{1}}^N‍X_i=\varnothing$ the inconsistent 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 $X_i$ s, that is, $X^{\ast }={\bigcap }_{i=\mathrm{1}}^N‍X_i$ , and the optimal solution for the inconsistent case is unique since functions ${\left|·\right|}_{X_i}^{\mathrm{2}}$ s 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 $\mathcal{V}=\{\mathrm{1},\dots ,N\}$ and their sensing balls $X_{\mathrm{1}},\dots ,X_N\subseteq {\mathfrak{R}}^{\mathrm{2}}$ given in (5). The interaction graph among these sensors is described by a directed graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ . Each sensor i only knows its own sensing set $X_i$ 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:

$$\begin{array}{l}{x}_i\left(k+\mathrm{1}\right)={\displaystyle \sum }_{j\in {\mathcal{N}}_i}{a}_{ij}\left(\left(\mathrm{1}-{\alpha }_k\right)x_j\left(k\right)+{\alpha }_k{P}_{X_j}\left(x_j\left(k\right)\right)\right),\\ i=\mathrm{1},\dots ,N,\end{array}$$

(7)

where $x_i(k)$ is the estimate of sensor i at time k and $\mathrm{0}\le {\alpha }_k\le \mathrm{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 ${\alpha }_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:

$$\begin{array}{l}{x}_i\left(k+\mathrm{1}\right)=\left(\mathrm{1}-{\alpha }_k\right){\displaystyle \sum }_{j\in {\mathcal{N}}_i}{a}_{ij}{x}_j\left(k\right)\\ +{\alpha }_k{P}_{X_i}\left({\displaystyle \sum }_{j\in {\mathcal{N}}_i}{a}_{ij}{x}_j\left(k\right)\right),\end{array}$$

(8)

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 intersection $X_{\mathrm{0}}≔{\bigcap }_{i=\mathrm{1}}^N‍X_i$ of some closed convex sets $X_i$ s. 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 ${\alpha }_k\equiv \mathrm{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 matrix A and the interaction graph $\mathcal{G}$ , which are standard in multiagent literature [10, 14].

Assumption 5.

(i) The adjacency matrix A is stochastic; that is, ${\sum }_{j=\mathrm{1}}^N‍a_{ij}=\mathrm{1}$ for each i.

(ii) The adjacency matrix A is doubly stochastic; that is, ${\sum }_{j=\mathrm{1}}^N‍a_{ij}={\sum }_{r=\mathrm{1}}^N‍a_{ri}=\mathrm{1}$ for each i.

Assumption 6.

The interaction graph $\mathcal{G}$ 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: $X_{\mathrm{0}}≔{\bigcap }_{i=\mathrm{1}}^N‍X_i\ne \varnothing$ . Suppose ${\sum }_{k=\mathrm{0}}^{\infty }‍{\alpha }_k=\infty$ and Assumptions 5 (i) and 6 hold. Then Algorithm (7) will achieve an optimal consensus; that is, for any initial condition $x_i(\mathrm{0})$ , there exists $x^{\ast }\in X_{\mathrm{0}}$ such that ${\mathrm{l}\mathrm{i}\mathrm{m}}_{k\to \infty }{x}_i(k)=x^{\ast }$ , $i=\mathrm{1},\dots ,N$ .

(ii)

Inconsistent case: ${\bigcap }_{i=\mathrm{1}}^N‍X_i=\varnothing$ . Suppose ${\sum }_{k=\mathrm{0}}^{\infty }‍{\alpha }_k=\infty$ , ${\sum }_{k=\mathrm{0}}^{\infty }‍{\alpha }_k^{\mathrm{2}}<\infty$ , and Assumptions 5 (ii) and 6 hold. Then Algorithm (7) will achieve an optimal consensus; that is, for any initial condition $x_i(\mathrm{0})$ , ${\mathrm{l}\mathrm{i}\mathrm{m}}_{k\to \infty }{x}_i(k)=x^{\ast }$ , $i=\mathrm{1},\dots ,N$ , where $x^{\ast }$ is the unique optimal solution of $\mathrm{m}\mathrm{i}\mathrm{n}{\sum }_{i=\mathrm{1}}^N‍{\left|x\right|}_{X_i}^{\mathrm{2}}$ .

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 ${\alpha }_k=\mathrm{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 still open for general directed graphs.

Here we formally introduce the nonempty interior assumption.

Assumption 8.

When $X_{\mathrm{0}}≔{\bigcap }_{i=\mathrm{1}}^N‍X_i\ne \varnothing$ , the intersection set $X_{\mathrm{0}}$ has nonempty interior; that is, there exists $z\in X_{\mathrm{0}}$ such that $\mathit{B}(z,ϵ)\subseteq X_{\mathrm{0}}$ for some $ϵ>\mathrm{0}$ .

Note that the optimal consensus result for consistent case does not require Assumption 8. 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 be exponential when the constant projection stepsize ${\alpha }_k\equiv \alpha$ is sufficiently small (Section 4). That is, for any initial condition $x_i(\mathrm{0})$ , $i=\mathrm{1},\dots ,N$ , there exist $x^{\ast }\in X_{\mathrm{0}}$ , $M>\mathrm{0}$ , and $\mathrm{0}<\lambda <\mathrm{1}$ such that

$$\begin{array}{cc}& \left|x_i\left(k\right)-x^{\ast }\right|\le M{\lambda }^k,i=\mathrm{1},\dots ,N,\hspace{0.17em}\hspace{0.17em}k\ge \mathrm{0}.\end{array}$$

(9)

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 $X_{\mathrm{0}}≔{\bigcap }_{i=\mathrm{1}}^N‍X_i\ne \varnothing$ . 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.

Let K be a closed convex set in ${\mathfrak{R}}^m$ . Let $\{z_k{\}}_{k\ge \mathrm{0}}$ be a sequence converging to $z^{\ast }\in K$ and satisfy that $|z_{k+\mathrm{1}}-z|\le |z_k-z|+{\epsilon }_k$ for all $z\in K$ and all k, where ${\sum }_{k=\mathrm{0}}^{\infty }‍{\epsilon }_k<\infty$ . Then

$$\begin{array}{cc}& \left|z_k-z^{\ast }\right|\le \mathrm{2}{\left|z_k\right|}_K+{\displaystyle \sum }_{p=k}^{\infty }{\epsilon }_p\forall k\ge \mathrm{0}.\end{array}$$

(10)

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 $X_{\mathrm{0}}≔{\bigcap }_{i=\mathrm{1}}^N‍X_i\ne \varnothing$ , the projection stepsize $\mathrm{0}<{\alpha }_k\equiv \alpha <\mathrm{1}$ is a constant, and Assumptions 5 (i), 6, and 8 hold. Then there exists ${\alpha }^{\ast }>\mathrm{0}$ such that when $\mathrm{0}<\alpha \le {\alpha }^{\ast }$ , Algorithm (7) will achieve an optimal consensus with an exponential convergence rate.

If the interaction graph is fixed and completely connected with the same weight $a_{ij}=\mathrm{1}/N$ , for all $i,j$ , then $h(r)=\mathrm{0}$ and $x_i(k)=\bar{x}(k)$ for all i and $r\ge \mathrm{1}$ . From (A.2) and (A.4) in the Appendix, we have that, for each i,

$$\begin{array}{cc}& {\left|x_i\left(k+\mathrm{1}\right)\right|}_{X_{\mathrm{0}}}\le \left(\mathrm{1}-\alpha +\alpha \bar{\rho }\right){\left|x_i\left(k\right)\right|}_{X_{\mathrm{0}}},k\ge \mathrm{0}.\end{array}$$

(11)

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 graph $\mathcal{G}$ is completely connected with weights $a_{ij}=\mathrm{1}/N$ , for all $i,j$ , then an optimal consensus will be achieved with exponential convergence rate $\mathrm{1}-\alpha +\alpha \bar{\rho }$ (<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 $\mathcal{V}=\{\mathrm{1,2},\mathrm{3,4}\}$ . Suppose the centers of the sensing balls $X_i\subseteq {\mathfrak{R}}^{\mathrm{2}}$ , $i=\mathrm{1,2},\mathrm{3,4}$ , are ${\rho }_{\mathrm{1}}=(\mathrm{1,0})$ , ${\rho }_{\mathrm{2}}=(\mathrm{0,1})$ , ${\rho }_{\mathrm{3}}=(-\mathrm{1,0})$ , and ${\rho }_{\mathrm{4}}=(\mathrm{0},-\mathrm{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

$$\begin{array}{cc}& A_{\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{i}\mathrm{n}}=\left(\begin{array}{cccc}\frac{\mathrm{1}}{\mathrm{2}}& \frac{\mathrm{1}}{\mathrm{2}}& \mathrm{0}& \mathrm{0}\\ \frac{\mathrm{1}}{\mathrm{3}}& \frac{\mathrm{1}}{\mathrm{3}}& \frac{\mathrm{1}}{\mathrm{3}}& \mathrm{0}\\ \mathrm{0}& \frac{\mathrm{1}}{\mathrm{3}}& \frac{\mathrm{1}}{\mathrm{3}}& \frac{\mathrm{1}}{\mathrm{3}}\\ \mathrm{0}& \mathrm{0}& \frac{\mathrm{1}}{\mathrm{2}}& \frac{\mathrm{1}}{\mathrm{2}}\end{array}\right),\\ A_{\mathrm{c}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}}=\left(\begin{array}{cccc}\frac{\mathrm{1}}{\mathrm{2}}& \mathrm{0}& \mathrm{0}& \frac{\mathrm{1}}{\mathrm{2}}\\ \frac{\mathrm{1}}{\mathrm{2}}& \frac{\mathrm{1}}{\mathrm{2}}& \mathrm{0}& \mathrm{0}\\ \mathrm{0}& \frac{\mathrm{1}}{\mathrm{2}}& \frac{\mathrm{1}}{\mathrm{2}}& \mathrm{0}\\ \mathrm{0}& \mathrm{0}& \frac{\mathrm{1}}{\mathrm{2}}& \frac{\mathrm{1}}{\mathrm{2}}\end{array}\right),\\ A_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}}=\left(\begin{array}{cccc}\frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}\\ \frac{\mathrm{1}}{\mathrm{2}}& \frac{\mathrm{1}}{\mathrm{2}}& \mathrm{0}& \mathrm{0}\\ \frac{\mathrm{1}}{\mathrm{2}}& \mathrm{0}& \frac{\mathrm{1}}{\mathrm{2}}& \mathrm{0}\\ \frac{\mathrm{1}}{\mathrm{2}}& \mathrm{0}& \mathrm{0}& \frac{\mathrm{1}}{\mathrm{2}}\end{array}\right),\end{array}$$

(12)

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 from $k=\mathrm{0}$ to $k=\mathrm{500}$ , where the interaction graph is a chain with adjacency matrix $A_{\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{i}\mathrm{n}}$ . The initial condition is $x_i(\mathrm{0})=(-\mathrm{5,5})$ , $i=\mathrm{1,2},\mathrm{3}$ , $x_{\mathrm{4}}(\mathrm{0})=(-\mathrm{5},-\mathrm{5})$ , and the constant projection stepsize is $\alpha =\mathrm{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 set $X_{\mathrm{0}}={\bigcap }_{i=\mathrm{1}}^{\mathrm{4}}‍X_i$ has nonempty interior. Let the initial condition be $x_i(\mathrm{0})=(-\mathrm{500,500})$ , $i=\mathrm{1,2},\mathrm{3,4}$ . We present the convergence rate estimate in terms of the measure

$$\begin{array}{cc}& C\left(\alpha \right)={\displaystyle \sum }_{i=\mathrm{1}}^{\mathrm{4}}\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{0}}^{\mathrm{29}}\frac{\left|x_i\left(k+\mathrm{1}\right)-x^{\ast }\right|/\left|x_i\left(k\right)-x^{\ast }\right|}{\mathrm{120}},\end{array}$$

(13)

where $x^{\ast }={\sum }_{i=\mathrm{1}}^{\mathrm{4}}‍x_i(\mathrm{59})/\mathrm{4}$ is used to approximately substitute the consensus point of the four agents in the network.

Figure 5 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 $\mathrm{0}<{\alpha }_k\equiv \alpha \le \mathrm{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 ${\bigcap }_{i=\mathrm{1}}^N‍X_i=\varnothing$ , 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.

Let K be a ball in ${\mathfrak{R}}^m$ , $\bar{z}\notin K$ . Then for any bounded set S that contains $\bar{z}$ , there exists $\mathcal{l}(S)>\mathrm{0}$ such that

$$\begin{array}{cc}& 〈z-\bar{z},\nabla {\left|z\right|}_K^{\mathrm{2}}-\nabla {\left|\bar{z}\right|}_K^{\mathrm{2}}〉\ge \mathcal{l}\left(S\right){\left|z-\bar{z}\right|}^{\mathrm{2}},\forall z\in S.\end{array}$$

(14)

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 ${\bigcap }_{i=\mathrm{1}}^N‍X_i=\varnothing$ and Assumptions 5 (ii) and 6 hold.

(i) If $\text{det}(A)\ne \mathrm{0}$ and Algorithm (7) achieves an optimal consensus for any initial condition, then ${\mathrm{l}\mathrm{i}\mathrm{m}}_{k\to \infty }{\alpha }_k=\mathrm{0}$ .

(ii) Suppose the graph $\mathcal{G}$ is completely connected with the same weight $a_{ij}=\mathrm{1}/N$ , $\forall i,j$ , and the projection stepsize is a constant: $\mathrm{0}<{\alpha }_k\equiv \alpha <\mathrm{1}$ . Let $S=\mathrm{c}\mathrm{o}\{x_i(k),X_i,i=\mathrm{1},\dots ,N,k\ge \mathrm{0}\}$ be the bounded set containing all agents’ estimates. Then

$$\begin{array}{cc}& {\left|\bar{x}\left(k+\mathrm{1}\right)-x^{\ast }\right|}^{\mathrm{2}}\le \left(\mathrm{1}-\frac{\alpha }{N}\mathcal{l}\left(S\right)\right){\left|\bar{x}\left(k\right)-x^{\ast }\right|}^{\mathrm{2}}+{\alpha }^{\mathrm{2}}L,\end{array}$$

(15)

where $L≔{\mathrm{s}\mathrm{u}\mathrm{p}}_{z\in S,\hspace{0.17em}i=\mathrm{1},\dots ,N}|z{|}_{X_i}^{\mathrm{2}}<\infty$ .

Theorem 14 (i) reveals that generally the convergence rate for the inconsistent case is impossible to be exponential. Intuitively, when the projection stepsize $\{{\alpha }_k\}$ diminishes, the optimization term (played by ${\alpha }_k(P_{X_i}(x_i(k))-x_i(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 α ( $\alpha \le \sqrt{ϵ/L}$ ) such that the convergence error $|\bar{x}(k)-x^{\ast }{|}^{\mathrm{2}}$ between agents’ estimates $\bar{x}(k)$ and the optimal point $x^{\ast }$ falls within the given error ϵ with an exponential rate $\mathrm{1}-(\alpha /N)\mathcal{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 $X_i\subseteq {\mathfrak{R}}^{\mathrm{2}}$ , $i=\mathrm{1,2},\mathrm{3,4}$ , are ${\rho }_{\mathrm{1}}=(\mathrm{1.5,0})$ , ${\rho }_{\mathrm{2}}=(\mathrm{0,1.5})$ , ${\rho }_{\mathrm{3}}=(-\mathrm{1.5,0})$ , and ${\rho }_{\mathrm{4}}=(\mathrm{0},-\mathrm{1.5})$ and all the radiuses are one. It is easy to see that the intersection of $X_i$ s is empty and the unique optimal solution of $\text{min}{\sum }_{i=\mathrm{1}}^{\mathrm{4}}‍|x{|}_{X_i}^{\mathrm{2}}$ is the origin point $(\mathrm{0,0})$ .

(i) We first present the convergence of optimal consensus from $k=\mathrm{0}$ to $k=\mathrm{5000}$ , where the interaction graph is a chain with the following doubly stochastic adjacency matrix $A_{\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{i}\mathrm{n}}^d$ :

$$\begin{array}{cc}& A_{\mathrm{c}\mathrm{h}\mathrm{a}\mathrm{i}\mathrm{n}}^d=\left(\begin{array}{cccc}\frac{\mathrm{1}}{\mathrm{2}}& \frac{\mathrm{1}}{\mathrm{2}}& \mathrm{0}& \mathrm{0}\\ \frac{\mathrm{1}}{\mathrm{2}}& \frac{\mathrm{1}}{\mathrm{3}}& \frac{\mathrm{1}}{\mathrm{6}}& \mathrm{0}\\ \mathrm{0}& \frac{\mathrm{1}}{\mathrm{6}}& \frac{\mathrm{1}}{\mathrm{3}}& \frac{\mathrm{1}}{\mathrm{2}}\\ \mathrm{0}& \mathrm{0}& \frac{\mathrm{1}}{\mathrm{2}}& \frac{\mathrm{1}}{\mathrm{2}}\end{array}\right).\end{array}$$

(16)

Let the initial condition be $x_i(\mathrm{0})=(-\mathrm{5,5})$ , $i=\mathrm{1,2},\mathrm{3}$ , $x_{\mathrm{4}}\left(\mathrm{0}\right)=(-\mathrm{5},-\mathrm{5})$ , and let the time-varying projection stepsize be ${\alpha }_k=\mathrm{1}/(k+\mathrm{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 Theorem 14 (i). The interaction graph, adjacency matrix, and the initial condition are the same as those in (i). The projection stepsize is $\alpha =\mathrm{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 $(\mathrm{0,0})$ .

(iii) We now present an example to validate Theorem 14 (ii). The interaction graph is completely connected with doubly stochastic adjacency matrix

$$\begin{array}{cc}& A_{\mathrm{c}\mathrm{o}\mathrm{m}}=\left(\begin{array}{cccc}\frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}\\ \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}\\ \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}\\ \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}& \frac{\mathrm{1}}{\mathrm{4}}\end{array}\right),\end{array}$$

(17)

and the initial condition is $x_i(\mathrm{0})=(-\mathrm{100,100})$ , $i=\mathrm{1,2},\mathrm{3,4}$ .

We use the measure $D(\alpha )={\sum }_{k=\mathrm{1}}^{\mathrm{100}}‍(|\bar{x}(k+\mathrm{1}){|}_{\mathbf{B}\left(\mathrm{0},r_{\mathrm{0}}\right)}/|\bar{x}(k){|}_{\mathbf{B}\left(\mathrm{0},r_{\mathrm{0}}\right)})/\mathrm{100}$ with $r_{\mathrm{0}}=|\bar{x}(\mathrm{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 $|\bar{x}(\mathrm{101})|$ between agents’ estimate $\bar{x}(\mathrm{101})$ at time $\mathrm{101}$ and the optimal solution $(\mathrm{0,0})$ as the final convergence error.

Figure 6

The trajectories show that the four agents converge to the optimal solution $(\mathrm{0,0})$ . The diamond indicates the unique optimal solution $(\mathrm{0,0})$ .

Figure 7

Agents will not converge to the optimal solution $(\mathrm{0,0})$ when the projection stepsize is a positive constant.

From Figure 8 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 $\mathrm{1}-(\alpha /N)\mathcal{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.