Distributed Average Consensus in Multi-agent Networks with Limited Bandwidth and Time-delays
Ⅰ. INTRODUCTION
The distributed consensus problem of multi-agent
networks has attracted great interests in recent years. It has
gained wide applications in practice,such as information fusion
in sensor networks,load balancing in processor networks,clock
synchronization,and multi-agent coordination and flocking. The
distributed average consensus usually means to design a network
protocol such that the states of all agents asymptotically reach
the average value of their initial states as time goes on. In
practice,the communication bandwidth and time-delays are
important constraint conditions. The conventional consensus
protocols are not appropriate for them. Recently,more and more
researchers study the distributed consensus problem of multi-agent
networks with quantization information and/or time-delays,such as
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] and references therein.
There are many distributed algorithms to achieve consensus
in literature,for example,classical consensus algorithms,
Gossip algorithms[1, 2, 3],sequence averaging algorithm[4],
etc. Here,we emphasize that the design of efficient quantization
ways (namely smart quantization techniques) is very important. In
[5, 6, 7, 8, 9],they have given some quantization techniques,for
example,uniform quantization strategy with
finite-level[5, 6]
or infinite-level[7],the logarithmic quantization
strategy[8, 9] and the ``zoom in-zoom out'' uniform
quantization strategy[8, 9],etc.
In [5, 7, 9],the distributed average consensus problem of
multi-agent systems with quantization information was studied.
However,only the real-time communication was considered. In [10],
the average consensus problem for multi-agent networks with
communication delays and limited data rate was dealt with. Our paper
will further consider the distributed average consensus problem of
multi-agent systems with limited communication data rate and
time-delays.~Generally,in order to control and process a complex
dynamic network,we do not transform it into a single
high-dimensional system by simply increasing dimensions[16].
Thus,our paper will not construct a high-dimensional augmented
system as in [10]. Furthermore,we show that the average consensus
protocol ((4) in this paper,(5) in [10]) is robust to finite
symmetric time-delays,but is sensitive to asymmetric time-delays
(see Remark 3 in Section III-A).
Another main contribution of our paper is that we study two types
of dynamic encoders/decoders. One uses inverse proportion function
as scaling function,while the other uses exponential function as
scaling function. We prove that all agents can reach average
consensus asymptotically with our protocol. We believe that
different encoders/decoders have different applications in
practice.
The remainder of this paper is organized as follows. In Section II,
we present the model of networks,propose a distributed protocol,
and formulate the problem to be investigated. Section III presents
the main results. We prove that the multi-agent network can reach
average consensus asymptotically. The protocol with an inverse
proportion function as scaling function is considered in Section
III-A,and the protocol with an exponential function as scaling
function is considered in Section III-B. Simulation results are
given in Section IV. Section V draws the conclusions.
Notation. $R^{n}$ is $n$-dimensional real Euclidean
space. $A^{\mathrm{T}}$ denotes the transpose of $A$.
$1$ denotes a column vector of all ones. The maximum
integer less than or equal to $x$ is denoted by $\lfloor
x\rfloor$. The minimum integer greater than or equal to $x$ is
denoted by $\lceil x\rceil$. $|\cdot|_{2}$ and $|\cdot|_{\infty}$
respectively denote $2$-norm and $\infty$-norm of vector or
matrix. $\sum_{i=0}^{l}(\cdot)$ is considered as 0 for $l<0$.
Let $\mathcal{G}:=(\mathcal{V},\mathcal{E},A)$ be a simple
weighted digraph,with the set of nodes
$\mathcal{V}=\{1,\cdots,N\}$,the set of edges
$\mathcal{E}\subseteq \mathcal{V}\times \mathcal{V}$,and the
weighted adjacency matrix $A=(a_{ij})_{N\times N}$. $v_{i}$ (or
$i$) denotes the $i$-th node of $\mathcal{G}$. $(i,~j)\in
\mathcal{E}$ denotes a directed edge of $\mathcal{G}$ from $i$ to
$j$. $a_{ij}\geq 0$ is the adjacency elements such that $a_{ij}>0
\Leftrightarrow (j,i)\in \mathcal{E}$. The set of in-neighbours of
the $i$-th node is denoted by $N_{i}:=\{j\in\mathcal{V}:~(j,~i)\in
\mathcal{E}\}$. $d_{i}:=\sum_{j=1}^{N}a_{ij}$ denotes the
in-degree of the $i$-th node. $d^{\ast}:= \max\{d_{1},\cdots,
d_{N}\}$ denotes the maximal in-degree of $\mathcal{G}$. The
Laplacian matrix of $\mathcal{G}$ is defined as $L=D-A$,where
$D=\mathrm{diag} \{ d_{1},\cdots,d_{N}\}$.
$\mathcal{G}=(\mathcal{V},~\mathcal{E},~A)$ is a simple weighted
undirected graph,if $(i,~j)\in \mathcal{V} \Leftrightarrow
(j,~i)\in \mathcal{V}$.
Ⅱ. PRELIMINARIES AND PROBLEM FORMULATION
In this paper,we consider the average consensus problem for a
network of agents with the dynamics of
|
$
\begin{aligned}
&x_{i}(t+1)=x_{i}(t)+hu_{i}(t),\\
&t=0,1,\cdots,\quad i=1,2,\cdots,N,
\end{aligned}
$
|
(1)
|
where $x_{i}(t)\in R$ and $u_{i}(t)\in R$ are,
respectively,the state and input of the $i$-th agent,and $h$ is
the control gain. The communications among agents are modeled as a
simple undirected weighted graph $\mathcal{G}=
(\mathcal{V},\mathcal{E},A)$,where $\mathcal{V}=\{1,\cdots,N\}$
is a nonempty set of $N$ nodes and each node denotes an agent,
$\mathcal{E}$ denotes the edge set and each edge denotes a
communication channel.
Distributed average consensus control means designing a
distributed protocol for the dynamic network,such that the states
of all agents converge to the average value of their initial
values.
Definition 1. The multi-agent network (1) is said to reach
average consensus asymptotically,if for each initial condition
$x_{0}:= [x_{1}(0),\cdots,x_{N}(0)]^{\mathrm{T}}$,
|
$
\lim\limits_{t\rightarrow
\infty}x_{i}(t,~x_{0})=\frac{{\bf
1}^{\mathrm{T}}x_{0}}{N},~~~i=1,2,\cdots,N.
$
|
For the multi-agent network (1),a classic distributed average
consensus protocol was proposed in [11] as
|
$
u_{i}(t)=\Sigma_{j\in N_{i}} a_{ij}(x_{j}(t)-x_{i}(t)).
$
|
(2)
|
The $i$-th agent needs the exact state information of its
neighbours. However,(2) may be too rough when the network links
represent actual digital communication channels. For digital
networks,only symbolic data can be exchanged among
agents[5, 9].
Some distributed protocols which use the quantized information
were proposed as
|
$
\begin{align}
&u_{i}(t)=\Sigma_{j\in N_{i}} a_{ij}(q(x_{j}(t)-q(x_{i}(t))),~\mbox{(see [7])}\notag\\
&u_{i}(t)=\Sigma_{j\in N_{i}}
a_{ij}(\hat{x}_{j}(t)-\hat{x}_{i}(t)),~\mbox{(see [9])}\notag\\
&u_{i}(t)=\Sigma_{j\in
N_{i}}a_{ij}(\hat{x}_{ji}(t)-\xi_{i}(t)),~\mbox{(see [5])}
\end{align}
$
|
(3)
|
where $q(\cdot)$ is a uniform quantizer (see bellow or [7]),
$\hat{x}_{i}(t)$ is the estimate of state $x_{i}(t)$ (see [9]),
$\xi_{i}(t)\in R$ and $\hat{x}_{ji}(t)\in R$ are
the internal state of $\Phi_{i}$ and the output of $\Psi_{ji}$,
respectively (see bellow or [5]).
For the practical multi-agent digital network (1),we assume that
each agent can only exchange symbolic data with its neighbours and
the network has finite time-delays.
We propose a time-delay distributed protocol as
|
$
\begin{aligned}
&u_{i}(t)=\Sigma_{j\in N_{i}} a_{ij}(\hat{x}_{ji}(t-1)-\xi_{i}(t-1)),\\
&t=1,2,\cdots,\quad ~i=1,2,\cdots,N,
\end{aligned}
$
|
(4)
|
where $\xi_{i}(t)\in R$ and $\hat{x}_{ji}(t)\in
R$ are,the internal state of $\Phi_{i}$ and the output
of $\Psi_{ji}$,respectively (see bellow).
The form of encoder $\Phi_{i}$/decoder $\Psi_{ji}$ in this paper
is similar to the one in [5],but they are not exactly the same.
Because we use some different scaling functions for them.
The difference encoder $\Phi_{i}$ of the $i$-th agent is given by
|
$
\begin{aligned}
&\xi_{i}(0)=0,\\
&\xi_{i}(t)=g(t-1)\Delta_{i}(t)+\xi_{i}(t-1),\\
&\Delta_{i}(t)=q(\frac{x_{i}(t)-\xi_{i}(t-1)}{g(t-1)}),~~~t=1,2,\cdots,
\end{aligned}
$
|
(5)
|
where $\xi_{i}(t)\in R$ is the internal state of
$\Phi_{i}$ and $\Delta_{i}(t)$ is the output of $\Phi_{i}$.
$\Delta_{i}(t)$ will be sent to its neighbours along communication
channels. Perhaps these neighbours cannot get data $\Delta_{i}(t)$
on time.
For each communication channel $(j,~i)\in \mathcal{E}$,the $i$-th
agent receives $\Delta_{j}(t)$,and then uses the following
decoder $\Psi_{ji}$ to recover $\xi_{j}(t)$ which is the estimated
value of state $x_{j}$.
|
$
\begin{aligned}
&\hat{x}_{ji}(0)=0,\\
&\hat{x}_{ji}(t)=g(t-1)\Delta_{j}(t)+\hat{x}_{ji}(t-1),~~~t=1,2,\cdots,
\end{aligned}
$
|
(6)
|
where $\hat{x}_{ji}(t)\in R$ is the output of $\Psi_{ji}$.
Here,$q(\cdot)$ is a finite-level uniform quantizer,and
$g(\cdot)>0$ is a scaling function.
The quantizer $q(\cdot)$ is a map from $R$ to the set of
quantized levels $\Gamma:=\{0,\pm1,\cdots,\pm K\}$. In this paper,
the associated quantizer $q(\cdot)$ is given by
|
$
q(x) = \left\{ {\begin{array}{*{20}{c}}
0&{ - \frac{1}{2} < x < \frac{1}{2},}\\
{i,}&{\frac{{2i - 1}}{2} \le x < \frac{{2i + 1}}{2},i = 1, \cdots ,K - 1,}\\
{K,}&{x \ge \frac{{2K - 1}}{2},}\\
{ - q( - x),{\rm{ }}}&{x \le \frac{{ - 1}}{2}.}
\end{array}} \right.
$
|
(7)
|
By observing the encoders and decoders,it is easy to know that
$\hat{x}_{ji}(t)=\xi_{j}(t)$ for $j=1,2,\cdots,N$,$i\in N_{j}$,
$t=0,1,2,\cdots$.
Denote
|
$
\begin{aligned}
&x(t)=[x_{1}(t),\cdots ,x_{N}(t)]^{\mathrm{T}},\\
&\xi(t)=[\xi_{1}(t),\cdots ,\xi_{N}(t)]^{\mathrm{T}},\\
&e(t)=x(t)-\xi(t),\\
&\delta(t)=x(t)-{J}x(t),
\end{aligned}
$
|
where ${J}:= (1/N)11^{\mathrm{T}}$.
Equations (4) and (5) can be respectively rewritten as
|
$
u(t)=-{L}\xi(t-1),~~~t=1,2,\cdots,
$
|
(8)
|
and
|
$
\begin{aligned}
&\xi(0)=0,\\
&\xi(t)=g(t-1)\Delta(t)+\xi(t-1),\\
&\Delta(t)={Q}(\frac{x(t)-\xi(t-1)}{g(t-1)}),~~~t=1,2,\cdots,
\end{aligned}
$
|
(9)
|
where
${Q}([y_{1},\cdots,y_{N}]^{\mathrm{T}}):=[q(y_{1}),\cdots,q(y_{N})]^{\mathrm{T}}$.
Substituting (8),(9) and (6) into system (1) leads to
|
$
\begin{aligned}
&x(t+1)=x(t)-h{L}\xi(t-1),\\
&\xi(t)=g(t-1){Q}(\frac{x(t)-\xi(t-1)}{g(t-1)})+\xi(t-1),\\
&x(1)=x(0)=x_{0},~\xi(0)=0,
\end{aligned}
$
|
(10)
|
for $t=1,2,\cdots$.
Note that ${JL}=0$,we have ${J}x(t+1)={J}x(t)$. That is,
|
$
\frac{1}{N}\sum_{i=1}^{N}x_{i}(t)=\frac{1}{N}\sum_{i=1}^{N}x_{i}(0),~~~t=0,1,\cdots.
$
|
(11)
|
This means that the closed-loop system (10) preserves average
value of the states.
Ⅲ. MAIN RESULTS
For our mentioned multi-agent networks,we make the following
assumptions.
Assumption 1. $\mathcal{G}= (\mathcal{V},~\mathcal{E},~A)$
is fixed undirected connected information exchange topology.
Assumption 2. $|x_{0}|_{\infty}\leq C_{1}$,
$|\delta_{0}|_{\infty}\leq C_{2}$,where $C_{1}$ and $C_{2}$ are
known nonnegative constants.
Remark 1. For Assumption 1,we have
$0=\lambda_{1}<\lambda_{2}\leq\cdots \leq \lambda_{N}$,where
$\lambda_{i}:= \lambda_{i}({L})$ is the eigenvalue of the
Laplacian matrix ${L}$ of $\mathcal{G}$[17]. For Assumption 2,
we accept Remark 6 in [5]. That is,we have a good estimate
with the initial states.
Lemma 1[5]. If Assumption 1 holds and
$0
Lemma 2. If Assumption 1 holds and $0
|
$
\begin{aligned}
&a_{h}:= \max_{2\leq i \leq N}\{(1+\sqrt{1-4h\lambda_{i}})/2\},\\
&b_{h}:= \max_{2\leq i \leq N}\{(1-\sqrt{1-4h\lambda_{i}})/2\}.
\end{aligned}
$
|
Proof. Note that $\mathcal{G}$ is connected. It is easy to
complete the proof,so we omit the details.
Lemma 3. For any positive integers $k$ and $r$,
|
$
\sum_{i=0}^{k-1}\frac{r+k+1}{r+k-1-i}\leq \frac{r+k+1}{r+k-1}\sum_{i=0}^{k-1}(\frac{r+1}{r})^{i}.
$
|
Proof. It is easy to complete the proof,so we omit the
details.
We prove that the network can achieve average consensus
asymptotically with protocol (4). In Section III-A,we choose an
inverse proportion function as scaling function. In Section III-B,
we choose an exponential function as scaling function.
A. Distributed Protocol with an Inverse Proportion Function
as Scaling Function
In Remark 9 of [6],it is claimed that the digital network can
achieve average consensus asymptotically. If we choose
$g(t)=\frac{g_{0}}{(t+q)^{p}}$ $(g_{0}>0,p>0,q>0)$ as scaling
function in encoders/decoders and use the following protocol
|
$
u_{i}(t)=\Sigma_{j\in N_{i}} a_{ij}(t)(\hat{x}_{ji}(t)-\xi_{ij}(t)),
$
|
where $\xi_{ij}(t)\in R$ and $\hat{x}_{ij}(t)\in
R$ are the internal state of $\Phi_{ij}$ and the output
of $\Psi_{ij}$,respectively[6].
In practice,the real-time data may be unavailable for the control
input,so we consider the time-delay distributed protocol (4). For
the sake of convenience,we choose $g(t)=\frac{g_{0}}{t+r}$ as
scaling function.
Theorem 1. Suppose Assumptions 1 and 2 hold. For any given
$h\in (0,~1/(4\lambda_{N}))$,integer $r> {1}/{(1-a_{h})}$,integer
$K\geq \lceil M_{1}(h,~r)\rceil$ and
|
$
g_{0}\geq\max\{ \frac{rC_{1}}{K+\frac{1}{2}},~\frac{2r(C_{2}+h\lambda_{N}C_{1})(1-\frac{r}{r-1}a_{h})}{h\lambda_{N}} \},
$
|
(12)
|
where $a_{h},~b_{h}$ are given by Lemma 2 and
|
$ \begin{aligned}
M_{1}(h,~r):= &\frac{1}{2(r+1)}+\frac{hd^{\ast}(r+2)}{r}+\\
&\frac{h^{2}\lambda_{N}^{2}\sqrt{N}(r+4)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})r}.
\end{aligned}
$
|
Then under the protocol given by (4)-(6) with the $(2K+1)$-level
uniform quantizer (7) and the scaling function
$g(t)=\frac{g_{0}}{t+r}$,the multi-agent network (1) can achieve
average consensus asymptotically. That is,the closed-loop system
(10) satisfies
|
$
\lim\limits_{t\rightarrow \infty}x(t)=Jx_{0}.
$
|
Furthermore,the convergence rate is at least ${\rm
O}(\frac{1}{t})$. Actually,
|
$
\lim_{t\rightarrow\infty} \sup\frac{|x(t)-{J}x(0)|_{2}}{\frac{1}{t}}
\leq
\frac{g_{0}h\lambda_{N}\sqrt{N}(r+3)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})r}.
$
|
Proof. We choose $h,~r,~K,~g_{0}$ which satisfy the
theorem$'$s conditions.
By (10) and ${LJ}={JL}=0$,we have
|
$
x(t+1)-\xi(t)=e(t)+h{L}e(t-1)-h{L}\delta(t-1)$,
$
|
|
$
\delta(t+1)=\delta(t)-h{L}\delta(t-1)+h{L}e(t-1)
$
|
|
$
\begin{aligned}
e(t+1)=&x(t+1)-\xi(t)-g(t){Q}(\frac{x(t+1)-\xi(t)}{g(t)}) =\\
&e(t)+h{L}e(t-1)-h{L}\delta(t-1)-\\
&g(t){Q}(\frac{e(t)+h{L}e(t-1)-h{L}\delta(t-1)}{g(t)}),
\end{aligned}
$
|
for $t=1,2,\cdots$. Specifically,we have
$\delta(1)=\delta(0)=x_{0}-{J}x_{0}$,$e(0)=x_{0}$,
$e(1)=x_{0}-\frac{g_{0}}{r}{Q}(\frac{r}{g_{0}}x_{0})$.
Let $w(t)=\frac{\delta(t)}{g(t)}$ and $z(t)=\frac{e(t)}{g(t)}$ for
$t=0,1,\cdots$. Then we have
|
$
\begin{aligned}
w(t+1)=&\frac{r+t+1}{r+t}w(t)-h\frac{r+t+1}{r+t-1}{L}w(t-1)+\\
&h\frac{r+t+1}{r+t-1}{L}z(t-1),\\
z(t+1)=&\frac{r+t+1}{r+t}D(t),
\end{aligned}
$
|
(13)
|
where
$D(t)=z(t)+h\frac{r+t}{r+t-1}{L}z(t-1)-h\frac{r+t}{r+t-1}{L}w(t-1)-{Q}[z(t)+
h\frac{r+t}{r+t-1}{L}z(t-1)-h\frac{r+t}{r+t-1}{L}w(t-1)]$ for
$t=1,2,\cdots$. Specifically,we have
$w(0)=\frac{r}{g_{0}}\delta(0)$,
$w(1)=\frac{r+1}{g_{0}}\delta(0)$,$z(0)=\frac{r}{g_{0}}x_{0}$,
$z(1)=\frac{r+1}{g_{0}}x_{0}-\frac{r+1}{r}{Q}(\frac{r}{g_{0}}x_{0})$
and $D(1)=z(1)-{Q}(z(1))$.
Now,we claim that the quantizer will never be saturated. That is,
$|\frac{x(t+1)-\xi (t)}{g(t)}{{|}_{\infty }}\le K+\frac{1}{2}$ for
$t\geq 0$.
Indeed,we have
$|\frac{x(1)-\xi(0)}{g(0)}|_{\infty}=|\frac{r}{g_{0}}x_{0}|_{\infty}\leq
\frac{rC_{1}}{g_{0}}\leq K+\frac{1}{2}$ and $|z(1)|_{\infty}\leq
\frac{r+1}{2r}$.
Noting that
|
$
\begin{aligned}
|\frac{x(t+1)-\xi(t)}{g(t)}|_{\infty}
=&|z(t)+h\frac{r+t}{r+t-1}{L}z(t-1)-\\&h\frac{r+t}{r+t-1}{L}w(t-1)|_{\infty},
\end{aligned}
$
|
we only need to prove
|
$
|z(t)+h\frac{r+t}{r+t-1}{L}z(t-1)-h\frac{r+t}{r+t-1}{L}w(t-1)|_{\infty}\leq K+\frac{1}{2}
$
|
for $t=1,2,\cdots $.
Firstly,it is easy to get
$|z(1)+h\frac{r+1}{r}{L}z(0)-h\frac{r+1}{r}{L}w(0)|_{\infty}=|z(1)|_{\infty}\leq
\frac{r+1}{2r}< K+\frac{1}{2}$ and $|D(1)|_{\infty}\leq
\frac{1}{2}$,$|z(2)|_{\infty}\leq \frac{r+2}{2(r+1)}$.
Secondly,we assume that
|
$
|z(t)+h\frac{r+t}{r+t-1}{L}z(t-1)-h\frac{r+t}{r+t-1}{L}w(t-1)|_{\infty}\leq K+\frac{1}{2}
$
|
for $t=1,2,\cdots,k$,then we have $|D(t)|_{\infty}\leq \frac{1}{2}$
and $|z(t+1)|_{\infty}\leq \frac{r+t+1}{2(r+t)}$ for
$t=1,2,\cdots,k$.
Lastly,for $t=k+1$ we will prove
|
$
|z(k+1)+h\frac{r+k+1}{r+k}{L}z(k)-h\frac{r+k+1}{r+k}{L}w(k)|_{\infty}\leq K+\frac{1}{2}.
$
|
Since ${L}$ is a real symmetric matrix,we can take an orthogonal
matrix $U:= [1/\sqrt{N},\phi_{2},\cdots,\phi_{N}]$ which
is defined by
$\phi_{i}^{\mathrm{T}}{L}=\lambda_{i}\phi_{i}^{\mathrm{T}}$,
$i=2,\cdots,N$. Let
$\hat{w}(t)=[\hat{w}_{1}(t),~\hat{w}_{2}^{\mathrm{T}}(t)]^{\mathrm{T}}=U^{\mathrm{T}}w(t)$,
where
|
$
\begin{aligned}
&\hat{w}_{1}(t)=
(1^{\mathrm{T}}/\sqrt{N})w(t)=\frac{1^{\mathrm{T}}}{\sqrt{N}g(t)}[x(t)-{J}x(t)]=0,\\
&\hat{w}_{2}(t)= \phi ^{\mathrm{T}}w(t)=
[\phi_{2},\cdots,\phi_{N}]^{\mathrm{T}}w(t).
\end{aligned}
$
|
By (13),we have
|
$
\begin{aligned}
\hat{w}_{2}(t+1)=&\frac{r+t+1}{r+t}\hat{w}_{2}(t)-\\
&h\frac{r+t+1}{r+t-1}\mathrm{diag}\{\lambda_{2},\cdots,\lambda_{N}\}\hat{w}_{2}(t-1) +\\
&h\frac{r+t+1}{r+t-1}\phi^{\mathrm{T}}{L}z(t-1).
\end{aligned}
$
|
That is,
|
$
\begin{aligned}
\frac{\hat{w}_{2}(t+1)}{r+t+1}
=&\frac{\hat{w}_{2}(t)}{r+t}-\mathrm{diag}\{h\lambda_{2},\cdots,h\lambda_{N}\}\frac{\hat{w}_{2}(t-1)}{r+t-1}+\\
& h\phi^{\mathrm{T}}{L}\frac{z(t-1)}{r+t-1}~~~~t=1,2,\cdots.
\end{aligned}
$
|
Let $X:=\frac{1}{2}\mathrm{diag}\{1+\sqrt{1-4h\lambda_{2}},\cdots,1+\sqrt{1-4h\lambda_{N}}\}$
and $Y:=\frac{1}{2}\mathrm{diag}\{1-\sqrt{1-4h\lambda_{2}},\cdots,1-\sqrt{1-4h\lambda_{N}}\}$,
then $X+Y=I$,
$XY=h\mathrm{diag}\{\lambda_{2},\cdots,\lambda_{N}\}$,
$|X|_{2}=a_{h}$,$|Y|_{2}=b_{h}$ (see Lemma 2).
We have
|
$
\begin{aligned}
&\frac{\hat{w}_{2}(t+1)}{r+t+1}-Y\frac{\hat{w}_{2}(t)}{r+t}=\\
&\qquad X[\frac{\hat{w}_{2}(t)}{r+t}-Y\frac{\hat{w}_{2}(t-1)}{r+t-1}]+h\phi^{\mathrm{T}}{L}\frac{z(t-1)}{r+t-1}=\\
&\qquad
X^{t}[\frac{\hat{w}_{2}(1)}{r+1}-Y\frac{\hat{w}_{2}(0)}{r}]+hX^{t-1}\phi
^{\mathrm{T}}{L}\frac{z(0)}{r}+\\
&\qquad \sum_{i=0}^{t-2}hX^{i}\phi ^{\mathrm{T}}{L}\frac{z(t-i-1)}{r+t-i-1}=\\
&\qquad X^{t+1}\frac{\hat{w}_{2}(0)}{r}+\frac{h}{r}X^{t-1}\phi
^{\mathrm{T}}{L}z(0)+\\
&\qquad \sum_{i=0}^{t-2}hX^{i}\phi
^{\mathrm{T}}{L}\frac{z(t-i-1)}{r+t-i-1},
\end{aligned}
$
|
for $t=1,2,\cdots$,where
$\frac{\hat{w}_{2}(1)}{r+1}-Y\frac{\hat{w}_{2}(0)}{r}=X\frac{\hat{w}_{2}(0)}{r}$.
Then we have
|
$
\begin{aligned}
&\frac{\hat{w}_{2}(t+1)}{r+t+1}=Y\frac{\hat{w}_{2}(t)}{r+t}+f(t)=\\
&\qquad Y^{t}\frac{\hat{w}_{2}(0)}{r}+\sum_{j=0}^{t-1}Y^{j}f(t-j)=\\
&\qquad[Y^{t}+\sum_{j=0}^{t-1}Y^{j}X^{t-j+1}]\frac{\hat{w}_{2}(0)}{r}
+\frac{h}{r}(\sum_{j=0}^{t-1}Y^{j}X^{t-j-1})\phi ^{\mathrm{T}}{L} z(0)+\\
&\qquad \sum_{j=0}^{t-1}\sum_{i=0}^{t-j-2}[hY^{j}X^{i}\phi
^{\mathrm{T}}{L}\frac{z(t-j-i-1)}{r+t-j-i-1}],
\end{aligned}
$
|
where $f(t):=
X^{t+1}\frac{\hat{w}_{2}(0)}{r}+\frac{h}{r}X^{t-1}\phi
^{\mathrm{T}}{L}z(0)
+\sum_{i=0}^{t-2}hX^{i}\phi ^{\mathrm{T}}{L}\frac{z(t-i-1)}{r+t-i-1}$ for $t=1,2,\cdots$.
Noting that $\hat{w}(t)=U^{\mathrm{T}}w(t)$,$\hat{w}_{1}(t)=0$,
and $\hat{w}_{2}(t)=\phi ^{\mathrm{T}}w(t)$,we have
|
$
\begin{aligned}
w(t)=&U\hat{w}(t) =\phi \hat{w}_{2}(t)=\\
&(r+t)\{\phi[Y^{t-1}+\sum_{j=0}^{t-2}Y^{j}X^{t-j}]\frac{\phi
^{\mathrm{T}}w(0)}{r}+\\
& \frac{h}{r}\phi(\sum_{j=0}^{t-2} Y^{j}X^{t-j-2})\phi ^{\mathrm{T}}{L} z(0)+\\
&\phi\sum_{j=0}^{t-2} \sum_{i=0}^{t-j-3}[hY^{j}X^{i}\phi
^{\mathrm{T}}{L}\frac{z(t-j-i-2)}{r+t-j-i-2}]\}
\end{aligned}
$
|
for $t=2,3,\cdots$.
Now we estimate the three terms on the right-hand side of the above
equation,separately.
Noting that $|x|_{\infty}\leq |x|_{2}\leq \sqrt{N}|x|_{\infty}$
for $x\in R^{N}$ and $|\phi|_{2}=1$,we have
|
$
\begin{aligned}
&|\phi[Y^{t-1}+\sum_{j=0}^{t-2}Y^{j}X^{t-j}]\frac{\phi^{\mathrm{T}}w(0)}{r}|_{2} \leq \\
&~~~[b_{h}^{t-1}
+a_{h}^{t}\sum_{j=0}^{t-2}(\frac{b_{h}}{a_{h}})^{j}]\frac{\sqrt{N}|w(0)|_{\infty}}{r} \leq \\
&~~~\frac{\sqrt{N}C_{2}}{g_{0}} b_{h}^{t-1}
+\frac{\sqrt{N}C_{2}a_{h}^{2}}{g_{0}(a_{h}-b_{h})}a_{h}^{t-1}\leq \\
&~~~\frac{\sqrt{N}C_{2}}{g_{0}} b_{h}^{t-1}
+\frac{\sqrt{N}C_{2}}{g_{0}(a_{h}-b_{h})}a_{h}^{t-1},~~~~t=2,3,\cdots,
\end{aligned}
$
|
|
$
\begin{align}
& |\frac{h}{r}\phi (\sum\limits_{j=0}^{t-2}{{{Y}^{j}}}{{X}^{t-j-2}}){{\phi }^{\text{T}}}Lz(0){{|}_{2}}\le \\
& \frac{h}{r}a_{h}^{t-2}[\sum\limits_{j=0}^{t-2}{{{(\frac{{{b}_{h}}}{{{a}_{h}}})}^{j}}}]{{\lambda }_{N}}\sqrt{N}|z(0){{|}_{\infty }}\le \\
& \frac{h{{\lambda }_{N}}\sqrt{N}{{C}_{1}}}{{{g}_{0}}({{a}_{h}}-{{b}_{h}})}a_{h}^{t-1},~~~~t=2,3,\cdots . \\
\end{align}
$
|
We have assumed that $|z(t)|_{\infty}\leq \frac{r+t}{2(r+t-1)}$ for
$t=1,2,\cdots,k+1$,then
|
$
\begin{aligned}
&|\phi\sum_{j=0}^{t-2} \sum_{i=0}^{t-j-3}[h(r+t)Y^{j}X^{i}\phi ^{\mathrm{T}}{L}\frac{z(t-j-i-2)}{r+t-j-i-2}]|_{2}\leq\\
&\quad
\frac{h\lambda_{N}\sqrt{N}}{2}\sum_{j=0}^{t-2}\sum_{i=0}^{t-j-3}[\frac{r+t}{r+t-3}(\frac{r}{r-1})^{j}(\frac{r}{r-1})^{i}b_{h}^{j}a_{h}^{i}]\leq\\
&\quad
\frac{h\lambda_{N}\sqrt{N}(r+t)}{2(1-\frac{r}{r-1}a_{h})(r+t-3)}
\{\frac{1-(\frac{r}{r-1}b_{h})^{t-1}}{1-\frac{r}{r-1}b_{h}}-\\
&\quad (\frac{r}{r-1}a_{h})^{t-2}\frac{a_{h}}{a_{h}-b_{h}}\}\leq \\
&\quad \frac{h\lambda_{N}\sqrt{N}(r+t)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})(r+t-3)}[1-(\frac{r}{r-1}b_{h})^{t-1}]-\\
&\quad
\frac{h\lambda_{N}\sqrt{N}(r+t)}{2(1-\frac{r}{r-1}a_{h})(a_{h}-b_{h})(r+t-3)}(\frac{r}{r-1})^{t-2}a_{h}^{t-1}
\end{aligned}
$
|
for $t=3,4,\cdots,k$.
So we have
|
$
|w(1)|_{2}=|\frac{r+1}{g_{0}}\delta(0)|_{2}\leq\frac{\sqrt{N}C_{2}(r+1)}{g_{0}},
$
|
|
$
|w(2)|_{2}=|\frac{r+2}{g_{0}}\delta(0)|_{2}\leq\frac{\sqrt{N}C_{2}(r+2)}{g_{0}},
$
|
|
$
\begin{aligned}
&|w(t)|_{2}
\leq\frac{h\lambda_{N}\sqrt{N}(r+t)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})(r+t-3)}+\\
&\quad \left[\frac{C_{2}}{g_{0}}+ \frac{h\lambda_{N}C_{1}}{g_{0}}
-\frac{h\lambda_{N}(\frac{r}{r-1})^{t-2}}{2(1-\frac{r}{r-1}a_{h})(r+t-3)}\right]\times\\
&\quad \frac{\sqrt{N}(r+t)a_{h}^{(t-1)}}{a_{h}-b_{h}}+\\
&\quad\left[\frac{C_{2}}{g_{0}}-\frac{h\lambda_{N}(\frac{r}{r-1})^{t-1}}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})(r+t-3)}\right]\times\\
&\quad
\sqrt{N}(r+t)b_{h}^{(t-1)}\leq\\
&\quad
\frac{h\lambda_{N}\sqrt{N}(r+3)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})r},~~~~t=3,4,\cdots,k,
\end{aligned}
$
|
where $\frac{C_{2}+h\lambda_{N}C_{1}}{g_{0}}<
\frac{h\lambda_{N}(\frac{r}{r-1})^{t-2}}{2(1-\frac{r}{r-1}a_{h})(r+t-3)}$
and $\frac{C_{2}}{g_{0}}<
\frac{h\lambda_{N}(\frac{r}{r-1})^{t-1}}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})(r+t-3)}$
by Appendix. By (12),we have $g_{0}\geq
\frac{2r(C_{2}+h\lambda_{N}C_{1})(1-\frac{r}{r-1}a_{h})}{h\lambda_{N}}$,
then we have
$\frac{\sqrt{N}C_{2}(r+2)}{g_{0}}\leq\frac{h\lambda_{N}\sqrt{N}(r+3)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})r}$
and $\frac{h\lambda_{N}\sqrt{N}C_{2}(r+3)}{g_{0}}\leq
\frac{h^{2}\lambda_{N}^{2}\sqrt{N}(r+4)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})r}$.
Thus,
|
$
|w(t)|_{2}\leq\frac{h\lambda_{N}\sqrt{N}(r+3)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})r},~~~t=1,2,\cdots,k,
$
|
and
|
$
\begin{aligned}
&|z(k+1)+h\frac{r+k+1}{r+k}{L}z(k)-h\frac{r+k+1}{r+k}{L}w(k)|_{\infty}\leq\\
&\qquad \frac{r+k+1}{2(r+k)}+\frac{hd^{\ast}(r+k+1)}{(r+k-1)} +\\
&\qquad \left\{
\begin{array}{ll}
\frac{h\lambda_{N}\sqrt{N}C_{2}(r+k+1)}{g_{0}},& k=1,2 \\
\frac{h^{2}\lambda_{N}^{2}\sqrt{N}(r+3)(r+k+1)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})r(r+k)},&k=3,4,\cdots
\end{array}
\right.
\leq
\\
&\qquad \frac{1}{2}+\frac{1}{2(r+1)}+\frac{hd^{\ast}(r+2)}{r}+\\
&\qquad \left\{
\begin{array}{ll}
\frac{h\lambda_{N}\sqrt{N}C_{2}(r+3)}{g_{0}} & k=1,2 \\
\frac{h^{2}\lambda_{N}^{2}\sqrt{N}(r+4)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})r} & k=3,4,\cdots
\end{array}
\right.
\leq \\
&\qquad
\frac{1}{2}+\frac{1}{2(r+1)}+\frac{hd^{\ast}(r+2)}{r}+\\
&\qquad
\frac{h^{2}\lambda_{N}^{2}\sqrt{N}(r+4)}{2(1-\frac{r}{r-1}a_{h})
(1-\frac{r}{r-1}b_{h})r}\leq\\
&\qquad \lceil M_{1}(h,~r)\rceil+ \frac{1}{2}\leq
K+\frac{1}{2},~~~~k=1,2,\cdots.
\end{aligned}
$
|
By induction,we conclude that
|
$
|z(t)+h\frac{r+t}{r+t-1}{L}z(t-1)-h\frac{r+t}{r+t-1}{L}w(t-1)|_{\infty}\leq K+\frac{1}{2}
$
|
for $t=1,2,\cdots$.
Then we have
$|\frac{x(t+1)-\xi(t)}{g(t)}|_{\infty}\leq K+\frac{1}{2}$ for $t\geq
0$.
Indeed,according to the above analysis,we conclude that
$|w(t)|_{\infty}\leq |w(t)|_{2} \leq
\frac{h\lambda_{N}\sqrt{N}(r+3)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})r}<\infty$
for $t=1,2,\cdots$.
Noting that $w(t)=\frac{\delta(t)}{g(t)}$,
$g(t)=\frac{g_{0}}{r+t}$ and (11),we get
|
$
\lim_{t\rightarrow \infty}|\delta(t)|_{\infty}=0,
$
|
|
$
\lim\limits_{t\rightarrow \infty}x(t)=Jx_{0},
$
|
and
|
$
\begin{aligned}
\lim_{t\rightarrow\infty} &\sup\frac{|\delta(t)|_{2}}{\frac{1}{t}}
\leq \\
&\lim_{t\rightarrow\infty}\sup\frac{t}{r+t}\cdot\frac{g_{0}h\lambda_{N}\sqrt{N}(r+3)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})r}=\\
&\frac{g_{0}h\lambda_{N}\sqrt{N}(r+3)}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})r}.
\end{aligned}
$
|
Remark 2. From Theorem 1,we have $x(t)\rightarrow {J}x(0)$
as $t \rightarrow \infty$,and the convergence rate is at least
O$(\frac{1}{t})$. Unfortunately,we only give the feasible region
of parameters,but do not know how to choose the best ones.
Meanwhile,the region of parameters is also conservative.
Actually,the smaller parameters $g_{0}$ and $K$ may be available
(see Examples 1$\sim$3). We emphasize that Theorem 1,and Theorems 2,
3 below have great significance. Because we can always choose the
feasible parameters by the theorems,such that all agents converge
to the average consensus value asymptotically.
In [5],the real-time state of encoder is available for the
control input,and they choose $g(t)=g_{0}r^{t}$ as scaling
function in encoders and decoders. In Theorem 2,we also consider
the protocol which uses the real-time information,but we choose
$g(t)=\frac{g_{0}}{t+r}$ as scaling function.
Under the protocol given by (3),(5) and (6),%with the $(2K+1)$-level uniform quantizer (7) and the scaling function $g(t)=\frac{g_{0}}{t+r}$,
the closed-loop system can be written as
|
$
\begin{aligned}
&x(t+1)=x(t)-h{L}\xi(t),%~t=0,1,\cdots,
\\
%&\xi(t)=g(t-1){Q}(\frac{x(t)-\xi(t-1)}{g(t-1)})+\xi(t-1),%~t=1,2,\cdots,
&\xi(t+1)=g(t){Q}(\frac{x(t+1)-\xi(t)}{g(t)})+\xi(t),
\\
&x(0)=x_{0},~\xi(0)=0,~t=0,1,\cdots.
\end{aligned}
$
|
(14)
|
It is easy to get
$\frac{1}{N}\sum_{i=1}^{N}x_{i}(t)=\frac{1}{N}\sum_{i=1}^{N}x_{i}(0)$
for $t=0,1,\cdots$.
Theorem 2. Suppose Assumptions 1 and 2 hold. For any given
$h\in (0,~2/\lambda_{N})$,integer $r>
\frac{\rho_{h}}{1-\rho_{h}}$,integer $K\geq \lceil
M_{1}(h,~r)\rceil$ and
|
$
g_{0}\geq\max\left\{ \frac{rC_{1}}{K+\frac{1}{2}},~\frac{2(C_{2}+h\lambda_{N}C_{1})[r-(r+1)\rho_{h}]}{h\lambda_{N}}\right\},
$
|
(15)
|
where $\rho_{h}$ is given by Lemma 1 and
|
$
M_{1}(h,~r):= \frac{1}{2r}+\frac{hd^{\ast}(r+1)}{r}+\frac{h\lambda_{N}\sqrt{N}(r+2)}{2[r-(r+1)\rho_{h}]}.
$
|
Then under the protocol given by (3),(5) and (6) with the
$(2K+1)$-level uniform quantizer (7) and the scaling function
$g(t)=\frac{g_{0}}{t+r}$,the multi-agent network (1) can achieve
average consensus asymptotically. That is,the closed-loop
system (14) satisfies
|
$
\lim\limits_{t\rightarrow \infty}x(t)=Jx_{0}.
$
|
Furthermore,the convergence rate is at least O$(\frac{1}{t})$.
Actually,
|
$
\lim_{t\rightarrow\infty} \sup\frac{|x(t)-{J}x(0)|_{2}}{\frac{1}{t}}\leq \frac{g_{0}h\lambda_{N}\sqrt{N}(r+2)}{2[r-(r+1)\rho_{h}]}.
$
|
Proof. We choose $h,~r,~K,~g_{0}$ which satisfy theorem$'$s
conditions. By (14),we have
|
$
x(t+1)-\xi(t)=e(t)+h{L}e(t)-h{L}\delta(t),
$
|
|
$
\delta(t+1)=\delta(t)-h{L}\delta(t)+h{L}e(t),
$
|
|
$
e(t+1)=e(t)+h{L}e(t)-h{L}\delta(t)-g(t){Q}(\frac{e(t)+h{L}e(t)-h{L}\delta(t)}{g(t)}),
$
|
for $t=0,1,\cdots$. Specifically,we have
$\delta(1)=\delta(0)=x_{0}-{J}x_{0}$,$e(0)=x_{0}$.
The rest proof is similar to Theorem 1,so we omit the details.
Remark 3. From the proofs of Theorems 1 and 2,we conclude
that the multi-agent network can achieve average consensus
asymptotically by using the following protocol
|
$
\begin{aligned}
&u_{i}(t)=\Sigma_{j\in
N_{i}}a_{ij}(\hat{x}_{ji}(t-\tau)-\xi_{i}(t-\tau)),\\
&t=\tau,\tau+1,\cdots,\quad ~i=1,2,\cdots,N,\end{aligned}
$
|
where $\tau$ is a
nonnegative integer,$h,~r,~K$ and $g_{0}$ are appropriate
parameters. That is,protocol (4) is robust to finite symmetric time-delays.
Namely,we can choose $\tau$ as $0$,$1$ or other positive
integer. On the other hand,if the protocol changes into
|
$
\begin{aligned}
&u_{i}(t)=\Sigma_{j\in N_{i}}
a_{ij}(\hat{x}_{ji}(t-1)-\xi_{i}(t)),\\
& t=1,2,\cdots,\quad ~i=1,2,\cdots,N,\end{aligned}
$
|
(16)
|
then the
multi-agent network will not achieve average consensus
asymptotically (see Example 4). Therefore,the distributed average
consensus problem of multi-agent digital networks has many
challenges.
B. Distributed Protocol with an Exponential Function as
Scaling Function
In this section,we choose $g(t)=g_{0}r^{t}$ as scaling function
in encoders and decoders.
Theorem 3. Suppose Assumptions 1 and 2 hold. For any given
$h\in (0,~1/4\lambda_{N})$,$r\in (a_{h},~1)$,integer $K\geq
\lfloor M_{1}(h,~r)+\frac{1}{2}\rfloor$,and
|
$
g_{0}\geq\max\{ \frac{C_{1}}{K+\frac{1}{2}},~
\frac{2(C_{2}+h\lambda_{N}C_{1})(r-a_{h})}{h\lambda_{N}}\},
$
|
(17)
|
where $a_{h},~b_{h}$ are given by Lemma 2 and
|
$
M_{1}(h,~r):= \frac{1}{2r}+\frac{hd^{\ast}}{r^{2}}+\frac{h^{2}\lambda_{N}^{2}\sqrt{N}}{2r^{2}(r-a_{h})(r-b_{h})}.
$
|
Then under the protocol given by (4)$\sim$(6) with the $(2K+1)$-level
uniform quantizer (7) and the scaling function $g(t)=g_{0}r^{t}$,
the multi-agent network (1) can achieve average consensus
asymptotically. That is,the closed-loop system (10) satisfies
|
$
\lim\limits_{t\rightarrow \infty}x(t)=Jx_{0}.
$
|
Furthermore,the convergence rate is at least O$(r^{t})$.
Actually,
|
$
\lim_{t\rightarrow\infty} \sup\frac{|x(t)-{J}x(0)|_{2}}{r^{t}}
\leq \frac{g_{0}h\lambda_{N}\sqrt{N}}{2r(r-a_{h})(r-b_{h})}.
$
|
Proof. The proof is similar to Theorem 1,so we will drop
some details. We choose $h,~r,~K$ and $g_{0}$ which satisfy the
theorem$'$s conditions.
By (10),we have
|
$
x(t+1)-\xi(t)=e(t)+h{L}e(t-1)-h{L}\delta(t-1),
$
|
|
$
\delta(t+1)=\delta(t)+h{L}e(t-1)-h{L}\delta(t-1),
$
|
|
$
\begin{aligned}
e(t+1)=&e(t)+h{L}e(t-1)-h{L}\delta(t-1)-\\
&g(t){Q}(\frac{e(t)+h{L}e(t-1)-h{L}\delta(t-1)}{g(t)}),\end{aligned}
$
|
for $t=1,2,\cdots$. Specifically,we have
$\delta(1)=\delta(0)=x_{0}-{J}x_{0}$,$e(0)=x_{0}$,
$e(1)=x_{0}-g_{0}{Q}(\frac{x_{0}}{g_{0}})$.
Let $w(t)=\frac{\delta(t)}{g(t)}$ and $z(t)=\frac{e(t)}{g(t)}$. Then we have
|
$
\begin{aligned}
&w(t+1)=\frac{1}{r}w(t)+\frac{h}{r^{2}}{L}z(t-1)-\frac{h}{r^{2}}{L}w(t-1),\\
&z(t+1)=\frac{1}{r}D(t),
\end{aligned}
$
|
where
$D(t)=z(t)+\frac{h}{r}{L}z(t-1)-\frac{h}{r}{L}w(t-1)-{Q}(z(t)+\frac{h}{r}{L}z(t-1)-\frac{h}{r}{L}w(t-1))$
for $t=1,2,\cdots$. Specifically,we have
$w(0)=\frac{\delta(0)}{g_{0}}$,$w(1)=\frac{\delta(0)}{g_{0}r}$,
$z(0)=\frac{x_{0}}{g_{0}}$,
$z(1)=\frac{1}{r}[\frac{x_{0}}{g_{0}}-{Q}(\frac{x_{0}}{g_{0}})]$
and $D(1)=z(1)-{Q}(z(1))$.
We claim that the quantizer will never be saturated. That is,
$|\frac{x(t+1)-\xi(t)}{g(t)}|_{\infty}\leq K+\frac{1}{2}$ for
$t\geq 0$.
Indeed,we have
$|\frac{x(1)-\xi(0)}{g(0)}|_{\infty}=|\frac{x_{0}}{g_{0}}|_{\infty}\leq\frac{C_{1}}{g_{0}}\leq
K+\frac{1}{2}$ and $|z(1)|_{\infty}\leq \frac{1}{2r}$.
Note that
|
$
|\frac{x(t+1)-\xi(t)}{g(t)}|_{\infty}=|z(t)+\frac{h}{r}{L}z(t-1)-\frac{h}{r}{L}w(t-1)|_{\infty}.
$
|
We only need to prove
|
$
|z(t)+\frac{h}{r}{L}z(t-1)-\frac{h}{r}{L}w(t-1)|_{\infty}\leq K+\frac{1}{2},~~~t=1,2,\cdots.
$
|
Firstly,it is easy to get
$|z(1)+\frac{h}{r}{L}z(0)-\frac{h}{r}{L}w(0)|_{\infty}=|z(1)|_{\infty}\leq
\frac{1}{2r}\leq K+\frac{1}{2}$ and $|D(1)|_{\infty}\leq
\frac{1}{2}$,$|z(2)|_{\infty}\leq \frac{1}{2r}$.
Secondly,we assume that
$$|z(t)+\frac{h}{r}{L}z(t-1)-\frac{h}{r}{L}w(t-1)|_{\infty}\leq K+\frac{1}{2},~~~t=1,2,\cdots,k,$$
then we have $|D(t)|_{\infty}\leq \frac{1}{2}$ and
$|z(t+1)|_{\infty}\leq \frac{1}{2r}$ for $t=1,2,\cdots,k$.
Lastly,for $t=k+1$ we will prove
|
$
|z(k+1)+\frac{h}{r}{L}z(k)-\frac{h}{r}{L}w(k)|_{\infty}\leq K+\frac{1}{2}.
$
|
Since ${L}$ is a real symmetric matrix,we can take an orthogonal
matrix $U:= [1/\sqrt{N},\phi_{2},\cdots,\phi_{N}]$ which
is defined by
$\phi_{i}^{\mathrm{T}}{L}=\lambda_{i}\phi_{i}^{\mathrm{T}}$,
$i=2,\cdots,N$. Let $\hat{w}(t):=
[\hat{w}_{1}(t),\hat{w}_{2}^{\mathrm{T}}(t)]^{\mathrm{T}}=U^{\mathrm{T}}w(t)$,
where $\hat{w}_{1}(t)=(1^{\mathrm{T}}/\sqrt{N})w(t)=0$,
$\hat{w}_{2}(t)= \phi ^{\mathrm{T}}w(t)=
[\phi_{2},\cdots,\phi_{N}]^{\mathrm{T}}w(t)$.
We have
|
$
\begin{aligned}\hat{w}_{2}(t+1)=&\frac{1}{r}\hat{w}_{2}(t)+\frac{h}{r^{2}}\phi
^{\mathrm{T}}{L}z(t-1)-\\
&\frac{h}{r^{2}}\mathrm{diag}\{\lambda_{2},\cdots,\lambda_{N}\}\hat{w}_{2}(t-1)
\end{aligned}
$
|
for $t=1,2,\cdots$
Let
$X=\frac{1}{2r}\mathrm{diag}\{1+\sqrt{1-4h\lambda_{2}},\cdots,1+\sqrt{1-4h\lambda_{N}}\}$
and $Y=\frac{1}{2r}\mathrm{diag}\{1-\sqrt{1-4h\lambda_{2}},\cdots,1-\sqrt{1-4h\lambda_{N}}\}$,
then $X+Y=\frac{1}{r}I$,
$XY=\frac{h}{r^{2}}\mathrm{diag}\{\lambda_{2},\cdots,\lambda_{N}\}$,
$|X|_{2}=\frac{a_{h}}{r}$,$|Y|_{2}=\frac{b_{h}}{r}$ (see Lemma 2).
We have
|
$
\begin{aligned}
&\hat{w}_{2}(t+1)-Y\hat{w}_{2}(t)=\\
&\qquad X(\hat{w}_{2}(t)-Y\hat{w}_{2}(t-1))+\frac{h}{r^{2}}\phi ^{\mathrm{T}}{L}z(t-1)=\\
&\qquad X^{t+1}\hat{w}_{2}(0)+\frac{h}{r^{2}}X^{t-1}\phi
^{\mathrm{T}}{L}z(0)+\\
&\qquad \frac{h}{r^{2}}\sum_{i=0}^{t-2}X^{i}\phi
^{\mathrm{T}}{L}z(t-i-1),
\end{aligned}
$
|
and
|
$
\begin{aligned}
\hat{w}_{2}(t+1)=&Y \hat{w}_{2}(t)+f(t)=\\
&[\frac{1}{r}Y^{t}+\sum_{j=0}^{t-1}Y^{j}X^{t-j+1}]\hat{w}_{2}(0)+\\
&\frac{h}{r^{2}}(\sum_{j=0}^{t-1}Y^{j}X^{t-j-1})\phi ^{\mathrm{T}}{L} z(0)+\\
&\frac{h}{r^{2}}\sum_{j=0}^{t-1}\sum_{i=0}^{t-j-2}[Y^{j}X^{i}\phi
^{\mathrm{T}}{L} z(t-j-i-1)],
\end{aligned}
$
|
where $f(t):=
X^{t+1}\hat{w}_{2}(0)+\frac{h}{r^{2}}\sum_{i=0}^{t-2}X^{i}\phi
^{\mathrm{T}}{L}z(t-i-1)+\frac{h}{r^{2}}X^{t-1}\phi
^{\mathrm{T}}{L}z(0)$.
Noting that $\hat{w}(t)=U^{\mathrm{T}}w(t)$ and
$\hat{w}_{1}(t)=0$,$\hat{w}_{2}(t)=\phi ^{\mathrm{T}}w(t)$,we
have
|
$
\begin{aligned}
w(t)=&[\frac{1}{r}\phi Y^{t-1}+\phi\sum_{j=0}^{t-2}Y^{j}X^{t-j}]\phi
^{\mathrm{T}}w(0)+\\
&\frac{h}{r^{2}}\phi(\sum_{j=0}^{t-2}Y^{j}X^{t-j-2})\phi ^{\mathrm{T}}{L} z(0)+\\
&\frac{h}{r^{2}}\phi\sum_{j=0}^{t-2}\sum_{i=0}^{t-j-3}[Y^{j}X^{i}\phi
^{\mathrm{T}}{L} z(t-j-i-2)]
\end{aligned}
$
|
for $t=2,3,\cdots$.
Now we estimate the three terms on the right-hand side of the
above equation,respectively.
Note that $|x|_{\infty}\leq |x|_{2}\leq \sqrt{N}|x|_{\infty}$ for
$x\in R^{N}$,$|\phi|_{2}=1$,and we have assumed that
$|z(t)|_{\infty}\leq \frac{1}{2r}$ for $t=1,2,\cdots,k+1$,then we
have
|
$
\begin{aligned}
&|[\frac{1}{r}\phi Y^{t-1}+\phi\sum_{j=0}^{t-2}Y^{j}X^{t-j}]\phi^{\mathrm{T}}w(0)|_{2}\leq \\
&\qquad [\frac{1}{r} (\frac{b_{h}}{r})^{t-1}
+\sum_{j=0}^{t-2}(\frac{b_{h}}{a_{h}})^{j}(\frac{a_{h}}{r})^{t}]\sqrt{N}|w(0)|_{\infty}\leq \\
&\qquad \frac{\sqrt{N}C_{2}}{g_{0}r} (\frac{b_{h}}{r})^{t-1}
+\frac{\sqrt{N}C_{2}}{g_{0}(a_{h}-b_{h})r}(\frac{a_{h}}{r})^{t-1},
\end{aligned}
$
|
|
$
\begin{aligned}
&|\frac{h}{r^{2}}\phi(\sum_{j=0}^{t-2}Y^{j}X^{t-j-2})\phi^{\mathrm{T}}Lz(0)|_{2}\leq \\
&\qquad \frac{h}{r^{2}}[\sum_{j=0}^{t-2}(\frac{b_{h}}{a_{h}})^{j}(\frac{a_{h}}{r})^{t-2}]\lambda_{N}\sqrt{N}|z(0)|_{\infty}\leq \\
&\qquad
\frac{h\lambda_{N}\sqrt{N}C_{1}}{g_{0}r(a_{h}-b_{h})}(\frac{a_{h}}{r})^{t-1},
\end{aligned}
$
|
and
|
$
\begin{aligned}
&|\frac{h}{r^{2}}\phi\sum_{j=0}^{t-2}\sum_{i=0}^{t-j-3}[Y^{j}X^{i}\phi ^{\mathrm{T}}{L} z(t-j-i-2)]|_{2}\leq \\
&~~~\frac{h\lambda_{N}\sqrt{N}}{2r^{3}}\sum_{j=0}^{t-2}\sum_{i=0}^{t-j-3}[(\frac{b_{h}}{r})^{j}(\frac{a_{h}}{r})^{i}]\leq\\
&~~~\frac{h\lambda_{N}\sqrt{N}}{2r(r-a_{h})(r-b_{h})}[1-(\frac{b_{h}}{r})^{t-1}]-\\
&~~~\frac{h\lambda_{N}\sqrt{N}}{2r(r-a_{h})(a_{h}-b_{h})}(\frac{a_{h}}{r})^{t-1},~~~~t=3,4,\cdots,k.
\end{aligned}
$
|
So we have
|
$
|w(1)|_{2}=|\frac{\delta(0)}{g_{0}r}|_{2}\leq\frac{\sqrt{N}C_{2}}{g_{0}r},
$
|
|
$
|w(2)|_{2}=|\frac{1}{r}w(1)|_{2}\leq\frac{\sqrt{N}C_{2}}{g_{0}r^{2}},
$
|
|
$
\begin{aligned}
|w(t)|_{2} \leq& \frac{h\lambda_{N}\sqrt{N}}{2r(r-a_{h})(r-b_{h})}+\\[2mm]
&
[\frac{C_{2}}{g_{0}}-\frac{h\lambda_{N}}{2(r-a_{h})(r-b_{h})}]\frac{\sqrt{N}}{r}(\frac{b_{h}}{r})^{t-1}+\\[2mm]
&[\frac{C_{2}}{g_{0}}+\frac{h\lambda_{N}C_{1}}{g_{0}}
-\frac{h\lambda_{N}}{2(r-a_{h})}]
\frac{\sqrt{N}}{r(a_{h}-b_{h})}(\frac{a_{h}}{r})^{t-1}\leq\\[2mm]
&
\frac{h\lambda_{N}\sqrt{N}}{2r(r-a_{h})(r-b_{h})},~~~~t=3,4,\cdots,k,
\end{aligned}
$
|
where $\frac{C_{2}}{g_{0}}\leq
\frac{h\lambda_{N}}{2(r-a_{h})(r-b_{h})}$,
$\frac{C_{2}+h\lambda_{N}C_{1}}{g_{0}}\leq
\frac{h\lambda_{N}}{2(r-a_{h})}$ and
$\frac{\sqrt{N}C_{2}}{g_{0}r^{2}}<
\frac{h\lambda_{N}\sqrt{N}}{2r(r-a_{h})(r-b_{h})}$ by (17).
Thus,
|
$
|w(t)|_{2}\leq \frac{h\lambda_{N}\sqrt{N}}{2r(r-a_{h})(r-b_{h})},~~~~t=1,2,\cdots,k,
$
|
and
|
$
\begin{aligned}
&|z(k+1)+\frac{h}{r}{L}z(k)-\frac{h}{r}{L}w(k)|_{\infty}\leq\\[2mm]
&\qquad \frac{1}{2r}+\frac{hd^{\ast}}{r^{2}}+\frac{h^{2}\lambda_{N}^{2}\sqrt{N}}{2r^{2}(r-a_{h})(r-b_{h})}\leq\\[2mm]
&\qquad \lfloor M_{1}(h,~r)+\frac{1}{2}\rfloor+\frac{1}{2}\leq
K+\frac{1}{2},~~~~k=1,2,\cdots.
\end{aligned}
$
|
By induction,we conclude that
$|z(t)+\frac{h}{r}{L}z(t-1)-\frac{h}{r}{L}w(t-1)|_{\infty}\leq
K+\frac{1}{2}$ for $t=1,2,\cdots.$
Then we have $|\frac{x(t+1)-\xi(t)}{g(t)}|_{\infty}\leq
K+\frac{1}{2}$ for $t\geq 0$.
Indeed,according to the above analysis,we conclude that
$|w(t)|_{\infty}\leq |w(t)|_{2}\leq
\frac{h\lambda_{N}\sqrt{N}}{2r(r-a_{h})(r-b_{h})}<\infty$ for
$t=1,2,\cdots$. Noting that $w(t)=\frac{\delta(t)}{g(t)}$ and
$g(t)=g_{0}r^{t}$ with $r\in (a_{h},~1)$,we get
|
$
\lim_{t\rightarrow \infty}|\delta(t)|_{\infty}=0,
$
|
|
$
\lim_{t\rightarrow\infty} \sup\frac{|\delta(t)|_{2}}{r^{t}}
\leq \frac{g_{0}h\lambda_{N}\sqrt{N}}{2r(r-a_{h})(r-b_{h})}.
$
|
By (11),we have $\lim\limits_{t\rightarrow
\infty}x(t)=Jx_{0}$.
Remark 4. From Theorem 3,we have $x(t)\rightarrow {J}x(0)$
as $t \rightarrow \infty$,and the convergence rate is at least
O$(r^{t})$ with $r\in (a_{h},~1)$.
Remark 5. Comparing these theorems,we have the followings
conclusions.
1) We can always choose some feasible parameters $h,~r,~K$ and
$g_{0}$ by these theorems,such that the multi-agent network can
achieve average consensus asymptotically.
2) The scaling functions can influence the convergence rate.
3) For our mentioned multi-agent digital networks,the average consensus protocol (4)
is robust to finite symmetric time-delays,but is sensitive to asymmetric time-delays. The asymmetric time-delays will destroy the average consensus. %The time-delays can influence the consensus value of digital networks.
Ⅳ. NUMERICAL EXAMPLES
We consider a network with 10 nodes. The interconnection topology
is modeled as a simple undirected circuit graph and shown in
Fig. 1. $A$ is the adjacency matrix,
|
$
A=\frac{1}{3}\begin{bmatrix}
1 & 1 & 0 & \cdots & 0 & 1 \\
1 & 1 & 1 & \cdots & 0 & 0 \\
0 & 1 & 1 & \cdots & 0 & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & \cdots & 1 & 1 \\
1 & 0 & 0 & \cdots & 1 & 1 \\
\end{bmatrix}_{10\times 10}.
$
|
Then we have $\lambda_{2}= 0.3820$,$\lambda_{N}= 4$. The initial
states satisfy $|x(0)|_{\infty}\leq 5$ and
$|\delta(0)|_{\infty}\leq 8$. In the following examples,the
initial state is $x_{i}(0)=-6+i$ for $i=1,\cdots,10$. Then
$\frac{1}{10}\sum_{i=1}^{10}x_{i}(0)=-0.5$.
Based on the above conditions,we choose a set of control
parameters to illustrate the above theorems.
Example 1. For Theorem 1,we choose $h=0.02$,then we have
$a_{h}=0.9923$,$b_{h}=0.0877$. And we choose $r=185$,$K=5$,
$g_{0}=170$. The evolution of the states is shown in Fig. 2 (a).
We only change $g_{0}=3$,and get the evolution of the states
which is shown in Fig. 2 (b). It can be seen that the average
consensus is all achieved asymptotically.
Example 2. For Theorem 2,we choose $h=0.40$,then we have
$\rho_{h}=0.8472$. And we choose $r=7$,$K=104$,$g_{0}=4.5$. The
evolution of the states is shown in Fig. 3 (a). We only change
$K=5$,and get the evolution of the states,which is shown in
Fig. 3 (b). It can be seen that the average consensus is all
achieved asymptotically.
Example 3. For Theorem 3,we choose $h=0.02$,then we have
$a_{h}=0.9923$,$b_{h}=0.0877$. And let $r=0.9950$,$K=5$ and
$g_{0}=1$. The evolution of the states is shown in Fig. 4 (a).
We only change $K=2$,and get the evolution of the states which is
shown in Fig. 4 (b). It can be seen that the average consensus
is all achieved asymptotically.
Example 4. We use protocol (16) to instead protocol (4). We
choose $h=0.05$ and $K=5$. The evolution of the states is shown in
Fig. 5 (a) (with $g(t)=\frac{g_{0}}{t+r}$ as scaling function,
where $r=7$,$g_{0}=3$) and Fig. 5 (b) (with $g(t)=g_{0}r^{t}$
as scaling function,where $r=0.99$,$g_{0}=1$). It can be seen
that the multi-agent network can achieve consensus asymptotically
(the consensus value is $-0.4348$),but can not achieve average
consensus (because $-0.500\neq-0.4348$).
Ⅴ. CONCLUSION AND DISCUSSION
In this paper,the average consensus control problem has been
considered for the undirected networks with finite bandwidth and
time-delays. The average consensus problem can be efficiently
solved by our protocol. Furthermore,we show that the average
consensus protocol
is robust to finite symmetric time-delays,but is sensitive to asymmetric time-delays. The asymmetric time-delays will destroy the average consensus of the networks. %Furthermore,we have shown that time-delays can influence the consensus value of digital network.
Meanwhile,we find that the theoretical results are still quite
conservative from simulations. For future research,how to relax
the selection of parameters and how to choose the best parameters
will be considered.
APPENDIX
If
$g_{0}\geq\frac{2r(C_{2}+h\lambda_{N}C_{1})(1-\frac{r}{r-1}a_{h})}{h\lambda_{N}}$,
then $\frac{C_{2}+h\lambda_{N}C_{1}}{g_{_{_{0}}}}<
\frac{h\lambda_{N}}{2(1-\frac{r}{r-1}a_{h})}\cdot
\frac{(\frac{r}{r-1})^{t-2}}{r+t-3}$ and
$\frac{C_{2}}{g_{_{_{0}}}} <
\frac{h\lambda_{N}}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})}\cdot
\frac{(\frac{r}{r-1})^{t-1}}{r+t-3}$ for $t\geq 3$.
Proof. Noting that integer $r> \frac{1}{1-a_{h}}$,we have
$r\geq 3$,$1-\frac{r}{r-1}a_{h}>0$,$1-\frac{r}{r-1}b_{h}>0$.
It is easy to prove $(\frac{r}{r-1})^{r}> {\rm e}$ for $r\geq 3$.
Then we have $3-r+\frac{1}{\ln\frac{r}{r-1}}<3$ for $r\geq 3$. Let
$f(t):= \frac{(\frac{r}{r-1})^{t-2}}{r+t-3}$,we have $f^{'}(t)=\frac{(\frac{r}{r-1})^{t-2}[(r+t-3)(\ln\frac{r}{r-1})-1]}{(r+t-3)^{2}}.$
It is easy to know $f^{'}(t)\geq 0$ for $t\geq 3$. Furthermore,we
have $f(t)\geq f(3)=\frac{1}{r-1}$ for $t\geq 3$
Note that
$g_{0}\geq\frac{2r(C_{2}+h\lambda_{N}C_{1})(1-\frac{r}{r-1}a_{h})}{h\lambda_{N}}.$
Therefore,
|
$
\begin{aligned} \frac{C_{2}+h\lambda_{N}C_{1}}{g_{0}}
<& \frac{h\lambda_{N}}{2(1-\frac{r}{r-1}a_{h})}
\frac{1}{r-1}\leq\\
& \frac{h\lambda_{N}}{2(1-\frac{r}{r-1}a_{h})}\frac{(\frac{r}{r-1})^{t-2}}{r+t-3},
\end{aligned}
$
|
and
|
$
\begin{aligned}
\frac{C_{2}}{g_{0}}
& < \frac{h\lambda_{N}}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})}\frac{1}{r-1}\leq\\
& \frac{h\lambda_{N}}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})} \frac{(\frac{r}{r-1})^{t-2}}{r+t-3}\leq\\
& \frac{h\lambda_{N}}{2(1-\frac{r}{r-1}a_{h})(1-\frac{r}{r-1}b_{h})}\frac{(\frac{r}{r-1})^{t-1}}{r+t-3}.
\end{aligned}
$
|
2014, Vol.1 
