Added reviewers comments.

[fusion.git] / chapitre-2009 / Fusion-chapter.tex

\documentclass{svmult}%
%\documentclass[]{llncs}
\usepackage{amsmath}

\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}%
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{amsmath}
%\setcounter{MaxMatrixCols}{30}
%\newtheorem{theorem}{Theorem}
%\newtheorem{acknowledgement}[theorem]{Acknowledgement}
%\newtheorem{algorithm}[theorem]{Algorithm}
%\newtheorem{axiom}[theorem]{Axiom}
%\newtheorem{case}[theorem]{Case}
%\newtheorem{claim}[theorem]{Claim}
\newtheorem{assumption}{Assumption}
%\newtheorem{conclusion}[theorem]{Conclusion}
%\newtheorem{condition}[theorem]{Condition}
%\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{criterion}[theorem]{Criterion}
%\newtheorem{definition}[theorem]{Definition}
%\newtheorem{example}[theorem]{Example}
%\newtheorem{exercise}[theorem]{Exercise}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{notation}[theorem]{Notation}
%\newtheorem{problem}[theorem]{Problem}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{remark}[theorem]{Remark}
%\newtheorem{solution}[theorem]{Solution}
%\newtheorem{summary}[theorem]{Summary}
%\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
%
%
%
%\documentclass[]{llncs}
%
%\smartqed
 %\usepackage{graphicx}
 \usepackage{amsmath}
% %\usepackage{amsthm}
 \usepackage{amssymb}
\usepackage{times}
 \usepackage{algorithm}
\usepackage{algorithmic}
% %\newtheorem{definition}{Definition}

\begin{document}
%\renewcommand{\baselinestretch}{1}
\title{Distributed Average Consensus in Large Asynchronous Sensor Networks}

\author{Jacques M. Bahi, Arnaud Giersh, Abdallah Makhoul and Ahmed Mostefaoui}
      \institute{Computer Science Laboratory, University of Franche-Comt\'e (LIFC) \at
       Rue Engel-Gros, BP 527\\
       90016 Belfort Cedex, France\\
       \email{\{firstname.lastname\}@univ-fcomte.fr}
}


\maketitle 

\abstract { One important issue in sensor networks is parameters
  estimation based on nodes measurements. Several approaches have been
  proposed in the literature (centralized and distributed
  ones). Because of the particular noisy environment, usually observed
  in sensor networks, centralized approaches are not efficient and
  present several drawbacks (important energy consumption, routing
  information maintaining, etc.). In distributed approaches however,
  nodes exchange data with their neighbours and update their own data
  accordingly until reaching convergence to the right parameters
  estimate. These approaches, although provide some robustness against
  nodes failure, does not address important issues as communication
  delay tolerance and asynchronism (i.e., they require that nodes
  remain synchronous in communication and processing). In this
  chapter, we tackle these issues by proposing a totally asynchronous
  scheme that is communication delay tolerant. The extensive
  simulations series we conducted have showed the effectiveness of our
  approach.  }

%------------------------------------------------------------------------------------------------------------------------
\section{Introduction}
Recent years have witnessed significant advances in wireless sensor
networks which emerge as one of the most promising technologies for
the 21$^{st}$ century~\cite{12}. In fact, they present huge potential
in several domains ranging from health care applications to military
applications. In general, the primary objective of a wireless sensor
network is to collect data from the monitored area and to transmit it
to a base station (sink) for processing. Many applications envisioned
for sensor networks consist of low–power and low–cost nodes. For
instance, applications such as data fusion and distributed
coordination require distributed function computation/parameter
estimation under topology changes and power constraints. Distributed
average consensus, in ad hoc networks, is an important issue in
distributed agreement and synchronization problems~\cite{22} and is
also a central topic for load balancing (with divisible tasks) in
parallel computers~\cite{23}. More recently, it has also found
applications in distributed coordination of mobile autonomous
agents~\cite{24,20} and distributed data fusion in sensor
networks~\cite{21,25}. In this chapter, we focus on a particular class
of iterative algorithms based on information diffusion for average
consensus, widely used in the applications cited above. Each node
broadcasts its data to its neighbours and updates its estimation
according to a weighted sum of the received data until the algorithm
convergence.

To illustrate the average consensus problem, let us consider the
example of petrol tanks. We suppose that in a oil station we have
large number of tanks related to each other in mechanical and sensor
networks. The role of sensors is to dectect the level of each oil
tank. The objective of this application is to keep the level of oil
on all tanks the same. When a sensor node detects some changes in its
level, it launchs an average consenus process to calculate the
average level of all tranks and then thanks to the mechanical network
an oil transfer operation is done to regulate the level. The average
consensus process is used to compute the average level, each sensor
node exchanges its information with its neighbors by iterative manner
until the convergence to the average consensus.

%\subsection {Motivations} The above data processing scheme is usually
%known as {\it centralized data fusion}. In this scheme, each sensor
%sends its data either directly, if it is located in the immediate
%neighbourhood of the sink, or by multi hops relays to the data fusion
%center via wireless communications. Besides the important cost in term
%of energy resources consumption due mainly to wireless communications
%(i.e., sensors that are located very far away from the base station,
%requires an important amount of energy to send/receive data to/from
%the sink), this scheme does not hold good robustness against
%communication loss neither against nodes failures. Furthermore, it
%requires that each node maintains rooting information to reach the
%sink. This is particularly challenging and resources consuming in case
%where network topology is constantly changing due either to nodes
%failures or communications unreliability or nodes mobility.

%Distributed approaches were proposed as interesting alternates based
%on {\it in-network} processing which may, in many cases, significantly
%decrease the energy consumed. In fact, in such approaches, nodes do
%not need to hold global knowledge about the current network topology
%since each node communicates only with its immediate neighbours. The
%unknown parameter estimate is then successively carried out through
%local computation from the exchanged data. The advantages of such
%approaches are numerous: (a) no central data fusion base station is
%required as every node holds the estimate of the unknown parameter;
%(b) multi-hop communications are avoided (only direct communications
%between neighbours are needed) and consequently maintaining rooting
%data is not needed any more; (c) better behaviour is observed in front
%of communication unreliability; (d) Network scalability is better
%supported than in centralized approach due mainly to direct
%communications between neighbours; etc.

To calculate the average consensus, many distributed approaches have
been proposed. On the other hand, these existing approaches present
some insufficiencies (see next section). For instance, the flooding
approach requires that each node holds a relatively important storage
space. Other approaches make the unpractical assumption of
communication synchronization between sensors~\cite{2,20} and do not
tolerate communication delays neither nodes failures. These weaknesses
remain very restrictive in sensor network environment where on one
hand nodes are prone to frequent failures as they are driven by
batteries and on the other hand communications are almost unreliable
and prone to delays. Moreover, these two limitative features lead, in
addition to nodes mobility, to dynamically changing network
topologies.

%\subsection {Contributions} 

In order to overcome the above mentioned weaknesses, we propose and
investigate in this chapter a novel approach for data fusion in sensor
networks. The key idea behind is to develop a consensus algorithm that
allows all nodes of the sensor network to track the average of their
previous measurements~\cite{21,2,20,5,9,10,16,17,18}. More
specifically, our proposition is based on an {\it in-network
  asynchronous iterative algorithm}, run by each node and in which
nodes communicate with only their immediate neighbours. 

In this context, let us discuss the primary contributions of this chapter:

\begin{itemize}

\item Our approach does not require any synchronization between nodes
  as it is basically asynchronous. In other words, each node
  communicates its data to its instantaneous neighbours at its own
  "rhythm" i.e., no delays between nodes are observed in our
  approach. This is particularly important because in the synchronous
  schemes, as the one reported in~\cite{2}, any delay between two
  nodes in the network will result in a global delay over the whole
  network since all the nodes are synchronous. This is particularly
  limitative in heterogeneous sensor networks where nodes have
  different processing speeds.

\item As a consequence of its asynchronism, our proposed approach
  totally tolerates communication delays. This feature is of an
  important matter because sensor networks, as it is commonly known,
  are prone to environmental perturbations~\cite{1} when communication
  delays occur more frequently.

\item The proposed distributed algorithm, as proven theoretical and
  validated experimentally, supports dynamic topologies and guarantees
  that each sensor node will converge to the average consensus.

\end{itemize} 


However, as for any iterative approach, our approach could, under
certain environmental conditions, consume more network resources,
mainly communications, than other centralized approaches, specifically
in "perfect environment" where nodes and communications are totally
reliable and the network topology is fixed.  Nevertheless, we note
here that our concern is more focused on {\it "noisy environment"} in
which communication unreliability and nodes failures are usual.

%-----------------------------------------------------------------------------------------------------------------------

\section{Overview of Averaging Problem in Sensor Networks}

The first and the simplest approach for distributed average estimation
in sensor networks is called {\it flooding} approach~\cite{2}. In this
approach, each sensor node broadcasts all its stored and received data
to its neighbours. After a while, each node will hold all the data of
the network and acts as a fusion center to compute the estimate of the
unknown parameter. This technique has however several
disadvantages~\cite{2}. First, it results in huge amount of exchanged
duplicate messages, which represents a real limitation in environments
like sensor networks.  Second, flooding requires that each node stores
at least one message per node (in order to compute the average). This
could lead to an important storage memory requirement in case of a
large sensor network with the associated operations (reads and
writes). Finally, it is obvious that those requirements will consume
much resources leading to an important decrease of the whole network
lifetime.

Alternatively, in~\cite{3} the authors proposed a scalable sensor
fusion scenario that performs fusion of sensor measurements combined
with local Kalman filtering. They developed a distributed algorithm
that allows the sensor nodes to compute the average of all of their
measurements. It is worthy to note that many other sensor data fusion
approaches are based on Kalman filters and mobile
agents~\cite{4,5,11,16,17}.

An iterative method for distributed data fusion in sensor networks
based on the calculation of an average consensus~\footnote{In the rest
  of the paper, the terms "average consensus" and "parameter
  estimation" are used to denote the same mechanism of finding an
  estimate of the unknown parameter average.}  has been proposed
in~\cite{2}. The authors consider that every node takes a noisy
measurement of the unknown parameter. Each node broadcasts its data to
its neighbours and updates its estimation according to a weighted sum
of the received data. In this scheme all the communications are direct
ones.

Although the above mentioned works and other existing data fusion
scenarios guarantee some level of robustness to nodes failures and
dynamic topology changes~\cite{2,3,4,10,20}, they either put some
unpractical assumptions like nodes synchronization or do not support
practical issues as the communication delays.

To the best of our knowledge, the above issues which are extremely
important, especially in noisy environments, are not taken into
account in previous data fusion approaches. In this chapter, we
present an asynchronous data fusion scheme, particularly tailored to
perturbed sensor networks. It focuses on a distributed iterative
algorithm for calculating averages over asynchronous sensor
networks. The sensor nodes exchange and update their data by the mean
of a weighted sum in order to achieve the average consensus. The
suggested algorithm does not rely on synchronization between the nodes
nor does it require any knowledge of the global topology. To round up,
the convergence of the proposed algorithm is proved in a general
asynchronous environment.

%-----------------------------------------------------------------------------------------------------------------

\section{Asynchronous Distributed Consensus with Messages Loss}

\subsection{Problem Formulation}

A sensor network is modelled as a connected undirected graph $G = (V,
E)$. The set of nodes is denoted by $V$ (the set of vertices), and the
links between nodes by $E$ (the set of edges). The nodes are labelled
$i = 1,2, \ldots, n$, and a link between two nodes $i$ and $j$ is
denoted by $(i, j)$. The dynamic topology changes are represented by
the time varying graph $G(t) = (V, E(t))$, where $E(t)$ is the set of
active edges at time $t$. The set of neighbours of node $i$ at time
$t$ is denoted by $N_{i}(t) = \{j\in V \mid (i,j) \in E(t)\}$, and the
degree (number of neighbours) of node $i$ at time $t$ by $\eta_{i}(t)
= |N_{i}(t)|$.

Each node takes initial measurement $z_{i}$. For sake of simplicity
let us suppose that $z_{i}\in\mathbb{R}$. Then, $z$ will refer to the
vector whose $i$th component is $z_{i}$ in case we are concerned with
several parameters.  Each node on the network also maintains a dynamic
state $x_{i}(t)\in\mathbb{R}$ which is initially set to $x_{i}(0) =
z_{i}$.

Intuitively each node's state $x_{i}(t)$ is its current estimate of
the average value $\sum_{i=1}^{n} z_{i} / n$. The goal of the
averaging algorithm, is to let all the states $x_{i}(t)$ go to the
average $\sum_{i=1}^{n} z_{i} / n$, as $t \rightarrow \infty$. This
will be done through data exchange between neighbouring nodes where
each node at every time iteration $t$ performs weighted sum of the
received data as follows~\cite{20,2}:

\begin{equation}
  x_{i}(t+1) = x_{i}(t) - \sum_{j\in{N}_{i}}\alpha_{ij}(t)(x_{i}(t) - x_{j}(t)) , i = 1, \ldots, n.
 \label{eqno1}
 \end{equation}

Where $\alpha_{ij}(t)$ is the weight on $x_{j}(t)$ at node $i$, and
 $\alpha_{ij}(t) = 0$ for $j \not\in N_{i}(t)$.

In order to handle communication delays, we consider that at time $t$
a node $i$ gets the state of its neighbour $j$ at time $d_{j}^{i}(t)$,
where $0\leq d_{j}^{i}(t)\leq t$

$d_{j}^{i}(t)$ represents the transmission delay between nodes $i$ and
$j$. Therefore, let us denote
$x_{j}^{i}(t)=x_{j}(d_{j}^{i}(t))\in\mathbb{R}$ the state of node $j$
at time $d_{j}^{i}(t),$ received at time $t$ by node $i$. Then, we
defined the extended neighbourhood of node $i$ at time $t$ as the set:

\begin{equation*}
\overline{N}_{i}(t)=\left\{j \mid \text{ }\exists \ d_{j}^{i}(t)\in\left\{
t-B+1,...,t\right\}  ,\text{such that }j\in N_{i}(d_{j}^{i}(t))\right\};
\end{equation*}

note that $ N_{i}(t) \subset \overline{N}_{i}(t)$.


The problem, as for any distributed algorithmic approach, is how and
under which conditions, will we ensure convergence of the proposed
algorithm? In other terms, are we sure that all the node's $x_{i}$
will converge to the right estimate of the unknown parameter average
value? Also, how can we choose the parameters $\alpha_{ij}(t)$ so to
improve the convergence speed and the quality of the derived estimate?
Hereafter we present and analyse our proposal. We used the notations
reported in Table~\ref{notations}


\begin{table}[h]  
\begin{center}  
\footnotesize
\begin{tabular}{|c|c|}  
\hline  
\cline{1-2}  
\textbf Notation&Description\\  
\hline  
\textbf{$G(t)$}&the time varying graph\\  
\hline  
\textbf{$N_{i}(t)$}&the set of neighbors of node $i$ at time $t$\\  
\hline  
\textbf{$z_{i}$}&the initial measurement of node $i$\\  
\hline   
\textbf{$x_{i}(t)$}&the dynamic state of node $i$\\
\hline
\textbf{$d_{j}^{i}(t)$}&the transmission delay between nodes $i$ and $j$\\  
\hline  
\textbf{$x_{j}^{i}(t)=x_{j}(d_{j}^{i}(t))$}&the state of node $j$ at time $t-d_{j}^{i}(t)$\\  
\hline  
\textbf{$\overline{N}_{i}(t)$}&the extended neighborhood of $i$ at time $t$\\  
\hline
\textbf{$s_{ij}(t)$}& the data sent by $i$ to $j$ at time $t$\\  
\hline
\textbf{$r_{ji}(t)$}&the data received by $i$ from $j$ at time $t$\\  
\hline
\end{tabular}  
\caption{Notations}  
\label{notations}  
\end{center}  
\end{table}  

%--------------------------------------------------------------------------------------------------------------------------------
\subsection{Asynchronous scheme}

Our algorithm to compute the average consensus over the network is
based on information diffusion i.e., each node takes a measurement and
then cooperates with its neighbours in a diffusion manner to estimate
the average of all the collected information.  It is inspired from the
work of Bertsekas and Tsitsiklis~\cite[section~7.4]{6} on load
balancing and extends it to cope with dynamic topologies and messages
loss and delays. Algorithm~\ref{general} presents the main steps of
our proposed algorithm.

\begin{algorithm}[H]
\begin{small}
\caption{The General Algorithm.}
\begin{algorithmic}[1]
\label{general} 
\STATE Each node maintains an instantaneous state $x_{i}(t) \in
\mathbb{R}$, and at $t=0$ (after all nodes have taken
the measurement), each node initializes its state as $x_{i}(0) =
z_{i}$.  \STATE At every step $t$ each node $i$:
\begin{itemize}
\item compares its state to the states of its neighbours;
\item chooses and computes $s_{ij}(t)$. They have to be chosen
  carefully in order to ensure the convergence of the algorithm;
\item diffuses its information;
\item receives the information sent by its neighbours $r_{ji}(t)$;
\item updates its state with a combination of its own state and the states at its
instantaneous and extended neighbours ($\overline{N}_{i}(t)$) as follows:
\begin{equation}
 x_{i}(t+1)=x_{i}(t)-\sum_{j\in N_{i}(t)}s_{ij}(t)+\sum_{j\in\overline 
{N}_{i}(t)}r_{ji}(t).
\label{x_(t+1)}%
\end{equation}
\end{itemize}
\end{algorithmic}
\end{small}
\end{algorithm}

\subsection{Theoretical Analysis (Convergence)}

We now introduce three assumptions that ensure the convergence of our algorithm.

\begin{assumption}
\label{assump:ConnectedGraph} 
$\text{There exists}\ B\in\mathbb{N}$ such that $\forall
t\geqslant0,$\\ $t-B<d_{j}^{i}(t)\leq t$ and the union of communication graphs
$\bigcup_{\tau = t}^{t+B-1}G(\tau)$ is a connected graph.
\end{assumption}

This assumption, known as jointly connected condition~\cite{2,7},
implies that each node $i$ is connected to a node $j$ within any time
interval of length $B$ and that the delay between two nodes cannot
exceeds $B$. Recall that, a graph is connected if for any two vertices
$i$ and $j$ there exists a sequence of edges $(i,\ k_{1}), (k_{1},
k_{2}), \ldots, (k_{l-1},\ k_{l}),\\ (k_{l},\ j)$.

In Figure~\ref{fig:jointly} we show an example of jointly connected
graphs, we notice that at $t = 1$ the graph $G_{1}$ is not connected;
the same case for $G_{2}$ at $t = 2$; while the union $G$ of $G_{1}$
and $G_{2}$ is a connected graph.

\begin{figure}[h]  
\centering  
        \includegraphics[scale=.55]{jointly.eps}  
%\vspace{-1mm}  
\caption{Example of jointly connected graphs}   
\label{fig:jointly}  
\end{figure}


\begin{assumption}
  \label{Inf Assumption} $ \text{There exists}\ \alpha>0,\forall
  t\geqslant0, \\ \forall i\in N,\forall j\in N_{i}(t)$, such that
  $\alpha(x_{i}(t)-x_{j}^{i}(t)) \leq s_{ij}(t).$ \\ $\ \left(s_{ij}(t)=0
    \ \text{if} \ (x_{i}(t) \leq x_{j}^{i}(t)) \ \text{for all} \ j
    \in N_{i}(t)\right) $.
\end{assumption}

The second assumption postulates that when a node $i$ detects a
difference between its state and the states of its neighbours, it
therefore computes non negligible $s_{ij}$ to all nodes $j$ where
$(x_{i}(t) > x_{j}^{i}(t))$.

\begin{assumption}
\label{PingPong}%
\begin{equation}
x_{i}(t)-\sum_{k\in N_{i}(t)}s_{ik}(t)\geq x_{j}^{i}(t)+s_{ij}(t)
\label{h5_2}%
\end{equation}
\end{assumption}
The third assumption prohibits node $i$ to compute very large $s_{ij}$
which creates a ping-pong state. Recall that, the ping-pong state is
established when two nodes keep sending data to each other back and
forth, without ever reaching equilibrium. Note that these two
assumptions are similar to assumption 4.2 introduced
in~\cite[section~7.4]{6}.

\begin{theorem}
\label{THE}
if the assumptions \ref{assump:ConnectedGraph}, \ref{Inf Assumption}
and \ref{PingPong} are satisfied, Algorithm~\ref{general} guarantees that

\begin{equation}
\lim_{t\rightarrow\infty}x_{i}(t)=\frac{1}{n} {\displaystyle\sum\limits_{i=1}^{n}} x_{i}(0)
\end{equation}

i.e., all node states converge to the average of the initial measurements of the network.
\end{theorem}

%------------------------------------------------------------preuve 
\noindent{\it Proof}
%\begin{small}

Let $m(t)=\min_{i}\min_{t-B<\tau\leq t}x_{i}(\tau).$ Note that $x_{j}^{i}%
(\tau)\geq m(t),$ $\forall i,j,t.$\newline Lemma \ref{lemma:1} and
\ref{lemma:2} below can be proven similarly to the lemma of pages 521 and 522
in~\cite{6}.

Denote by $v_{ij}(t)=\sum\limits_{s=0}^{t-1}\left( s_{ij}(s)-r_{ij}%
  (s)\right) ,$ the data sent by $i$ and not yet received by
$j$ at time $t.$ We suppose that $v_{ij}(0)=0.$ Then by data
conservation, we obtain%
\begin{equation}
\sum_{i=1}^{n}\left(  x_{i}(t)+\sum_{j\in N_{i}(t)}v_{ij}(t)\right)
=\sum_{i=1}^{n}x_{i}(0),\qquad\forall t\geqslant0\label{conservation}%
\end{equation}
%
>From assumption~\ref{assump:ConnectedGraph} we can conclude that the
data $v_{ij}(t)$ in the network before time $t$ consists in
data sent in the interval time $\left\{ t-B+1,...,t-1\right\} ,$ so
$v_{ij}(t)\leq\sum_{\tau=t-B+1}^{t-1}s_{ij}(t),$ $\forall node
i,\forall j\in N_{i}(t).$

\begin{lemma}
\label{lemma:1}The sequence $m(t)$ is monotone, nondecreasing and converges
and $\forall i,\forall s\geq0,$%
\begin{equation*}
x_{i}(t+s)\geq m(t)+\left(  \frac{1}{n}\right)  ^{t_{1}-t_{0}}(x_{i}(t)-m(t))
\end{equation*}

\end{lemma}

Let $i\in V,t_{0}\in\mathbb{N},$ and $t\geq t_{0},$ $j\in V,$ we say that the
event $E_{j}(t)$ occurs if there exists $j\in\overline{N}_{i}(t)$ such
that
\begin{equation}
x_{j}^{i}(t)<m(t_{0})+\frac{\alpha}{2n^{t-t_{0}}}\left(  x_{i}(t_{0}%
)-m(t_{0})\right)  \label{Event E_1}%
\end{equation}
and%
\begin{equation}
s_{ij}(t)\geq\alpha\left(  x_{i}(t)-x_{j}^{i}(t)\right)  ,\label{Event E_2}%
\end{equation}
where $\alpha$ is defined in assumption \ref{Inf Assumption}, and $V$ is the set of all nodes.

\begin{lemma}
\label{lemma:2}Let $t_{1}\geq t_{0},$ if $E_{j}(t_{1})$ occurs, then
$E_{j}(\tau)$ doesn't occur for any $\tau\geq t_{1}+2B$.
\end{lemma}

\begin{lemma}
\label{lemma:3}$\forall i\in V,\forall t_{0}\in\mathbb{N},\forall
j\in\overline{N}_{i}(t),$%
\begin{equation*}
t\geq t_{0}+3nB\Rightarrow x_{j}(t)\geq m(t_{0})+\eta\left(  \frac{1}%
{n}\right)  ^{t-t_{0}}(x_{i}(t_{0})-m(t_{0})).
\end{equation*}
where $\eta=\frac{\alpha}{2}\left(  \frac{1}{n}\right)  ^{B}.$
\end{lemma}

\begin{proof}
Let us fix $i$ and $t_{0}.$ Let us consider $t_{1},...,t_{n}$ such that
$t_{k-1}+2B\leq t_{k}\leq t_{k-1}+3B.$ Lemma \ref{lemma:2} implies that if
$k\neq l,$ then $E_{j}(t_{k})$ and $E_{j}(t_{l})$ doesn't occur together.
Hence, there exists $t_{k}$ for which (\ref{Event E_1}) is not satisfied for
all $d_{j}^{i}(t_{k})\in\left\{  t_{k}-B+1,...,t_{k}\right\}  ,$ and $j\in
N_{i}(d_{j}^{i}(t_{k})).$

Let $j^{\ast}\in N_{i}(d_{j}^{i}% 
(t_{k}))$ such that $x_{j^{\ast}}^{i}(t_{k})\leq x_{j}^{i}(t_{k}), \forall
j\in N_{i}(d_{j}^{i}(t_{k})).$ Since (\ref{Event E_1}) is not satisfied for
$j=j^{\ast},$ we have%

\begin{equation*}
\begin{array}
[c]{rl}%
x_{j}^{i}(t_{k})\geq & x_{j^{\ast}}^{i}(t_{k}) \\
x_{j^{\ast}}^{i}(t_{k}) \geq & m(t_{0})+\frac{\alpha}%
{2}\left(  \frac{1}{n}\right)  ^{t_{k}-t_{0}}\left(  x_{i}(t_{0}%
)-m(t_{0})\right), \text{ }\forall j\in N_{i}(d_{j}^{i}(t_{k})).
\end{array}
\end{equation*}


For $t\geq t_{0}+3nB,$ we have $t\geq t_{k}\geq d_{j}^{i}(t_{k}).$ Lemma
\ref{lemma:1} gives, $\forall j\in N_{i}(d_{j}^{i}(t_{k}))$%

\begin{equation*}%
\begin{array}
[c]{rl}%
x_{j}(t)\geq & m(d_{j}^{i}(t_{k}))+\left(\frac{1}{n}\right) ^{t-d_{j}%
^{i}(t_{k})}(x_{j}(d_{j}^{i}(t_{k}))-m(d_{j}^{i}(t_{k})))\\
\geq & m(t_{0})+\frac{\alpha}{2}\left(  \frac{1}{n}\right)  ^{B}\left(
\frac{1}{n}\right)  ^{t-t_{0}}\left(  x_{i}(t_{0})-m(t_{0})\right)  .
\end{array}
\end{equation*}
\end{proof}

\begin{definition}
We say that a sensor $j$ is $l$-connected to a sensor $i$ if it is logically
connected to $i$ by $l$ communication graphs, i.e. if there exists $r_{k}%
^{i}(t_{k})\in\left\{  t_{k}-B+1,...,t_{k}\right\}  ,$ where $k\in\left\{
i_{1},...,i_{l}\right\}  $, such that $i=i_{1}\in N_{i_{2}}(r_{i_{1}}%
^{i_{2}}(t_{1})),i_{2}\in N_{i_{3}}(r_{i_{2}}^{i_{3}}(t_{2})),...,\\ i_{l}\in
N_{j}(r_{l}^{j}(t_{l})).$
\end{definition}

\begin{lemma}
\label{lemma:4}If sensor $j$ is $l$-connected to sensor $i$ then%
\begin{equation*}
\forall t\geq t_{0}+3nlB,\text{ }x_{j}(t)\geq m(t_{0})+\left(  \eta\right)
^{l}(\frac{1}{n})^{(t-t_{0})^{l}}\left(  x_{i}(t_{0})-m(t_{0})\right)  .
\end{equation*}

\end{lemma}

\begin{proof}
By induction. Suppose that the lemma is true for $t_{0}+3nlB$ then if $j$ is
$l$-connected to $j$, we have%

\begin{equation*}
x_{l}(t_{0}+3nlB)\geq m(t_{0})+\left(  \eta\right)  ^{l}\left(  (\frac{1}%
{n})^{(3nlB)}\right)  ^{l}\left(  x_{i}(t_{0})-m(t_{0})\right)  .
\end{equation*}

Consider a sensor $k$ connected to $j$ ($k$ is
$\left(l+1\right)$-connected to $i$), Lemma \ref{lemma:3} and the
above inequality give (replacing $t_{0}$ by $t_{0}+3nlB),$

\begin{equation*}%
\begin{array}
[c]{rc}%

x_{k}(t)\geq & \\ m(t_{0}+3nlB)+\eta(\frac{1}{n})^{^{t-t_{0}-3nlB}}\left(
\left(  \eta\right)  ^{l}\left(  (\frac{1}{n})^{(3nlB)}\right)  ^{l}\left(
x_{i}(t_{0})-m(t_{0})\right)  \right)  \\
\geq & \\ m(t_{0})+\left(\eta\right)  ^{l+1}\left((\frac{1}{n})^{(t-t_{0}%
)}\right)  ^{l+1}\left(x_{i}(t_{0})-m(t_{0})\right).
\end{array}
\end{equation*}
\end{proof}

\begin{proof}
[Proof of Theorem 1] Consider a sensor $i$ and a time $t_{0}.$ Assumption
\ref{assump:ConnectedGraph} implies that sensor $i$ is $B$-connected to any
sensor $j.$ Lemma \ref{lemma:4} gives: $\forall t\in\left[  t_{0}%
+3nMB,t_{0}+3nMB+B\right]  ,$ $\forall j\in V,$%
\begin{equation*}
x_{j}(t_{0}+3nMB+B)\geq m(t_{0})+\delta\left( x_{i}(t_{0})-m(t_{0})\right)  ,
\end{equation*}
where $\delta>0.$ Thus,%
\begin{equation*}
m(t_{0}+3nMB+B)\geq m(t_{0})+\delta\left(  \max_{i}x_{i}(t_{0})-m(t_{0}%
)\right)  .
\end{equation*}
Note that $\lim_{t_{0}\rightarrow\infty}\max_{i}x_{i}(t_{0})-m(t_{0})=0$
(otherwise \\$\lim_{t_{0}\rightarrow\infty}m(t_{0})=+\infty$). On the other
hand, as $\lim_{t\rightarrow\infty}m(t)=c$ and as $m(t)\leq x_{j}(t)\leq
\max_{i}x_{i}(t),$ we deduce that $\forall j\in V,$ $\lim_{t\rightarrow\infty
}x_{j}(t)=c,$ which implies that $\lim_{t\rightarrow\infty}s_{ij}(t)=0$.
Thanks to assumption 1, we deduce that $\lim_{t\rightarrow\infty}v_{ij}(t)=0,$
and thanks to (\ref{conservation}), we deduce that $nc=\lim_{t\rightarrow
\infty}x_{i}(t)=\sum_{i=1}^{n}x_{i}(0),$i.e. $c=\sum_{i=1}^{n}x_{i}(0)/n,$
which yields to $\lim_{t\rightarrow\infty}x_{i}(t)=\frac{1}{n}%
%TCIMACRO{\dsum \limits_{i=1}^{n}}%
%BeginExpansion
{\displaystyle\sum\limits_{i=1}^{n}}
%EndExpansion
x_{i}(0)$ proving Theorem 1.
\end{proof}
%\end{small}
%----------------------------------------------------------preuve 


\subsection{Practical Issues}

We now discuss some practical aspects related to the implementation of
Algorithm~\ref{general}. The main two points are how to choose
$s_{ij}(t)$ and how to overcome the loss of messages?
 
Each node updates its state following equation (\ref{x_(t+1)}). This
is achieved, by updating each sensors $s_{ij}(t)$ through time.  For
sake of simplicity, the value of $s_{ij}(t)$ is chosen to be computed
by the weighted difference between the states of nodes $i$ and $j$ as
follows:

\begin{equation*}
  s_{ij}(t) = \left\{
          \begin{array}{ll}
            \alpha_{ij}(t) (x_{i}(t) - x_{j}^{i}(t)) & \qquad \text{if} \quad x_{i}(t) >  x_{j}^{i}(t) \ ,\\
            0 & \qquad \text{otherwise}.\\
          \end{array}
        \right.
\end{equation*}

The choice of $s_{ij}(t)$ is then deduced from the proper choice of
the weights $\alpha_{ij}(t)$. Hence, $\alpha_{ij}(t)$ must be chosen
such that the states of all the nodes converge to the average
$\sum_{i=1}^{n} z_{i} / n$, i.e., assumptions \ref{Inf Assumption} and
\ref{PingPong} must be satisfied.

Denote by $j^{\ast}$ the sensor node satisfying
$x_{j^{\ast}}^{i}=\min_{k\in N_{i}(t)} x_{k}^{i}(t)$ (note that
$j^{\ast}$ depends on $i$ and time $t$)$.$ The values of
$\alpha_{ij}(t)$ must be selected so that to avoid the ping pong
condition presented in assumption~\ref{PingPong}.

This is equivalent to choose $\alpha_{ij}(t)$ so that $\forall
t\geqslant 0,\forall i\in N,$ and $j\neq
j^{\ast}\in\overline{N}_{i}(t)$ satisfying $x_{i}(t)>x_{j}^{i}(t),$

\begin{equation}
0\leq\alpha_{ij}(t)\leq\frac{1}{2}\left(  1-\frac{\sum_{j\neq i}\alpha
_{ik}(t)(x_{i}(t)-x_{i}^{k}(t))}{(x_{i}(t)-x_{i}^{j}(t))}\right)
\label{h5_2bis}%
\end{equation}

The weights $\alpha_{ij}(t)$ must also be chosen in order to respect
assumption~\ref{Inf Assumption}. This assumption can be carried out by
fixing a constant $\beta\in\left[ 0,1\right] $ and choosing

\begin{equation}
\left\{
\begin{array}
[c]{l}%
\sum_{k\neq j^{\ast}\in N_{i}(t)}\alpha_{ik}(t)(x_{i}(t)-x_{k}^{i}%
(t))\leq\beta(x_{i}(t)-x_{j^{\ast}}^{i}(t)),\\
\alpha_{ij^{\ast}}(t)=\frac{1}{2}\left(  1-\frac{\sum_{k\neq j^{\ast}}%
\alpha_{ik}(t)(x_{i}(t)-x_{k}^{i}(t))}{(x_{i}(t)-x_{j^{\ast}}^{i}(t))}\right)
\end{array}
\right.  \label{h6}%
\end{equation}
Indeed, from (\ref{h6}) we deduce%
\begin{equation*}
\alpha_{ij^{\ast}}(t)\geq\frac{(x_{i}(t)-x_{j^{\ast}}^{i}(t))-\beta
(x_{i}(t)-x_{j^{\ast}}^{i}(t))}{2(x_{i}(t)-x_{j^{\ast}}^{i}(t))}=\frac
{1-\beta}{2}=\alpha.
\end{equation*}
Hence, $\forall i,j^{\ast},t$ such that $j^{\ast}\in\overline{N}_{i}(t)$
and $x_{j^{\ast}}^{i}(t)=\min_{k\in N_{i}(t)}x_{k}^{i}(t),$%
\begin{equation*}
s_{ij^{\ast}}(t)=\alpha_{ij^{\ast}}(t)\left(  x_{i}(t)-x_{j^{\ast}}%
^{i}(t)\right) \geq\alpha\left(  x_{i}(t)-x_{j^{\ast}}^{i}(t)\right).
\end{equation*}

The first inequation of (\ref{h6}) can be written as $\sum_{k\neq
  j^{\ast}\in
  V_{i}(t)}s_{ik}(t)\leq\beta(x_{i}(t)-x_{j^{\ast}}^{i}(t)),$ this
means that the totality of data sent to the neighbours of $i$ (except
$j^{\ast }$) doesn't exceed a portion $\beta$ of
$(x_{i}(t)-x_{j^{\ast}}^{i}(t)).$

Equations (\ref{h5_2bis}) and (\ref{h6}) are derived from the
assumptions \ref{Inf Assumption} and \ref{PingPong}. Therefore the
choice of the weights $\alpha_{ij}$ must take into consideration these
two equations.

First let define the deviation $\Delta_{i}^{j}(t)$ of node $i$ as:

\begin{equation*}
  \Delta_{i}^{j}(t) = \left\{
          \begin{array}{ll}
            x_{i}(t) - x_{j}^{i}(t) & \qquad \text{if}  j\in N_{i}(t) \  \text{and} \  x_{i}(t) >  x_{j}^{i}(t) \ ,\\
            0 & \qquad \text{otherwise.}\\
          \end{array}
        \right.
\end{equation*} 

Algorithm~\ref{WeightUpdate} presents our method for temporally
updating the averaging weights. Node $i$ computes the difference
between its current state and current states of its neighbours. The
positive deviations ($\Delta_{i}^{j} > 0$) are then stored in the
array $Delta_{i}$, in a decreasing order. Then, it sets the weight
$\alpha_{ij}$ to $1/(\eta_{i}(t) + 1)$, where $\eta_{i}(t)$ is the
current number of its neighbours, starting by its neighbours nodes $j$
whose have the larger deviations while respecting
assumption~\ref{PingPong}.

\begin{algorithm}[t]
\begin{small}
\caption{Temporally updating weights of node $i$.}
\begin{algorithmic}[1]
\label{WeightUpdate} 
\FOR {$j \gets 1$ to $n$}
\IF {$j \neq i$}
\STATE $s_{ij} \gets 0$
\STATE $\alpha_{ij} \gets 0$
\ENDIF
\ENDFOR
\STATE $k \gets 0$
\STATE $Sum \gets 0$
\STATE find $\ell$ such that $\Delta_{i}^{\ell} = Delta_{i}[k]$
\STATE $\alpha_{i\ell} = 1/(\eta_{i} + 1)$
\STATE $s_{i\ell} = \alpha_{i\ell} \times \Delta_{i}^{\ell}$
\REPEAT
\STATE $Sum \gets Sum + s_{il}$
\STATE $k \gets k+1$
\STATE find $\ell$ such that $\Delta_{i}^{\ell} = Delta_{i}[k]$
\STATE $\alpha_{i\ell} \gets 1/(\eta_{i} + 1)$
\STATE $s_{i\ell} \gets \alpha_{i\ell} \times \Delta_{i}^{\ell}$
\UNTIL{ $NOT$ ($(x_{i}- Sum \geq x_{\ell}^{i}+s_{i\ell})$ $AND$ $(k < n)$)}
\end{algorithmic}
\end{small}
\end{algorithm}


In order to cope with the problem of message loss, we adopted the
following strategy: instead of sending $s_{ij}(t)$ from node $i$ to
node $j$, it is the sum $\Sigma_{s_{ij}}(t) = \sum_{0\leq \tau\leq t}
s_{ij}(\tau)$ that is sent. Symmetrically the receivers maintains the
sum of the received data $\Sigma_{r_{ji}}(t) = \sum_{0\leq \tau\leq t}
r_{ji}(\tau)$. Upon receiving, at a time $t$, a message from node $i$,
a node $j$ can now recover all the data that was sent before time
$d_i^j(t)$. It has only to calculate the difference between the
received $\Sigma_{s_{ij}}(d_i^j(t))$ and the locally stored
$\Sigma_{r_{ji}}(t)$.

To conclude, the state messages exchanged during the execution of the
algorithm are composed of two scalar values : the current state of the
node, $x_i(t)$, and the sum of the sent data $\Sigma_{s_{ij}}(t)$.

\subsection{Illustrative Example}
To illustrate the behaviour of our proposed approach, les us consider
the example presented in Figure~\ref{fig:example}. It consists in a
network of four nodes. The initial measurement of each node $i$ is
known by $z_{i}$ and the initial state $x_{i}(0) = z_{i}$.

\begin{figure}[h]  
\centering  
        \includegraphics[scale=.55]{exampleFusion}  
%\vspace{-1mm}  
\caption{An example of a sensor network composed of four nodes with their initial measurements. }   
\label{fig:example}  
\end{figure}
 
Following the second step of Algorithm~\ref{general}, each node computes the weights $\alpha_{ij}$ for its neighbours. This is done by using Algorithm~\ref{WeightUpdate}.

Let us focus on the case of $node_{4}$ for instance. We notice that it
has three neighbours and the high deviation $\Delta$ corresponds to
$node_{3}$. Therefore, it computes $ \alpha_{43}(0) =
\frac{1}{\eta_{4} + 1} = \frac{1}{4} $ first, such that $\eta_{4}$ is
the number of its neighbours. Then, $s_{43}(0) = \frac{1}{4} (x_{4}(0)
- x_{3}(0)) = 0.175$. For the two reminder neighbours $node_{1}$ and
$node_{2}$, $node_{4}$ computes $\alpha_{42}(0)$ first for the reason
that $\Delta_{4}^{2}$ is higher than $\Delta_{4}^{1}$. We note that
for $node_{2}$ the Assumption~\ref{PingPong} (ping pong condition) is
satisfied while it is not the case for $node_{1}$ which leads to $
\alpha_{41}(0) = 0 $.

All the nodes compute their weights and then diffuse their information
to their neighbours to update their states following
Equation~(\ref{x_(t+1)}). For the above example after the first step
we obtain:

\begin{itemize}
\item[] $x_{1}(1) = 0.7$
\item[] $x_{2}(1) = 0.5 + 0.1 - 0.1 = 0.5$
\item[] $x_{3}(1) = 0.2 + 0.1 + 0.175 = 0.475$
\item[] $x_{4}(1) = 0.9 - 0.1 - 0.175 = 0.625$
\end{itemize}

This process is repeated for several iterations until all the states
of the nodes converge to the average of the initial measurements. We
note that our scheme is robust to the topology changes and the loss of
messages as discussed in details in the next section.

%-----------------------------------------------------------------------------------------------------
\section{Experimental Results}
\label{Exp}
In order to evaluate the performance of our approach, we have
implemented a simulation package using the discrete event simulator
OMNET++~\cite{8}. This package includes our asynchronous algorithm as
well as a synchronous one. As confirmed in previous related
works~\cite{2,20}, distributed approaches out perform centralised
approaches, in particular in noisy networks. For this reason, we have
not included in our comparison centralised approaches, and focuses
instead on synchronous distributed approaches that are more closed to
our work.


We performed several runs of the algorithms (an average of 100
runs). In each experimental run, the network graph is randomly
generated, where the nodes are distributed over a $[0, 100] \times [0,
  100]$ field. The node communication range was set to 30. The initial
node measurements $z_{i}$ were also randomly generated. Each node is
aware of its immediate neighbours through a "hello" message. Once the
neighbourhood is identified, each node run the algorithm i.e., begins
exchanging data until convergence.

We studied the performance of our algorithm with regard to the following parameters:
\begin{itemize}

\item Robustness in front of communication failures: we mainly varied
  the probability of communication failure, noted $p$. This parameter
  allows us to highlight the behaviour of our scheme in noisy
  environment and in dynamic topologies.

\item Scalability: we varied the number of sensor nodes deployed in the same area to see how our proposed approach scales?

\end{itemize} 

The main metrics we measured in this paper are: (a) the mean error
between the current estimate $x_{i}$ and the average of the initial
data, (b) the mean number of iterations necessary to reach convergence
and (c) the overall time before reaching the global convergence. We
note here that in asynchronous algorithms, there is no direct
correlation between the number of iterations and the total time to
convergence, contrary to synchronous approaches. In fact, as there are
no delays between nodes, the number of iterations could be relatively
high. This does not mean that the total time to convergence could be
long too. For this reason, we have made the distinction between the
number of iterations and the time taken to reach convergence. As we
run a discrete event simulation package, this time is the one given by
the discrete simulator OMNET++~\cite{8}; we named it {\it simulated
  time}. For all the experiments, the global convergence state is said
to be reached when $\varepsilon_{i} =| x_{i} - \sum_{i=1}^{n} y_{i} /
n |$ becomes less than some fixed constant $\varepsilon$.

Note that, in the figures next sections, the points represent the obtained results and the curves are an extrapolation of these points.




\subsection{Basic Behaviour} 
\label{BH}

First, we show simulation results for the case where we have a fixed
topology with a fixed number of nodes (50 nodes) and $\varepsilon =
10^{-4}$. The mean error of the nodes $\varepsilon' = \sum_{i=1}^{n}
\varepsilon_{i} / n$ was plotted in Figure~\ref{Error}. As expected,
it can be seen that the convergence in the synchronous mode is faster
than the convergence in the asynchronous one. It is also noticed that
the two graphs have the same pace.

However, in many scenarios an exact average is not required, and one
may be willing to trade precision for simplicity. For instance,
minimizing the number of iterations to reduce the energy consumption
can be privileged in sensor networks applications where exact
averaging is not essential.

\begin{figure}[h]  
\centering  
        \includegraphics[scale=.55]{ErrorNbIteration.ps}  
%\vspace{-1mm}  
\caption{The Mean Error $\varepsilon$}   
\label{Error}  
\end{figure}


\subsection{Dynamic topology}
In a next step, we simulated the proposed sensor fusion scheme with
dynamically changing communication graphs. We generated the sequence
of communication graphs as follows: at each time step, each edge in
the graph is only available with a selected probability $p$,
independent of the other edges and all previous steps. To ensure the
jointly connected condition of the generated graphs, we selected a
period of time $\tau$ in which an edge cannot stay disconnected more
than $\tau$ time.

We fixed the number of sensor nodes to 50 and $\varepsilon =
10^{-4}$. In preliminary results, the period $\tau$ was chosen in a
way that is equal to three times the time of a communication. We show
in figure~\ref{Dynamic} and figure~\ref{DynamicTime} the variation of
the number of iterations and the time simulation with the probability
of link failure $p$. We notice that the number of iterations and the
overall time increase with the increase of the probability, but not in
an exponential way.

%\begin{figure*}[t]
%\vspace{-5mm}
 % \begin{minipage}[t]{.5\textwidth}
\begin{figure}[h]
    \centering
    \includegraphics[scale=.55]{DynamicTopology.ps}
    \caption{Number of Iterations}
    \label{Dynamic}
  %\end{minipage}%
  %\hfill%
%\vspace{-5mm}
\end{figure}

\begin{figure}[h]
  %\begin{minipage}[t]{.5\textwidth}
    \centering
    \includegraphics[scale=.55]{DynamicTopologyTime.ps}
    %\vspace{2.75mm}
    \caption{Simulated Time} 
    \label{DynamicTime}
%  \end{minipage}%
 % \hfill%
\end{figure}

Note that we also tried to run the synchronous algorithm with dynamic
topology changes, but the execution times were so prohibitive, that we
abandoned those experiments. These results confirm that synchronous
algorithms are infeasible for real sensor networks.

\subsection{Larger Sensor Network}

Our scheme can be applied to sensor networks where a large number of
sensor nodes are deployed, since it is fully distributed and there is
no centralized control. In our simulations we varied the number of
sensor nodes from 20 to 200 nodes, deployed in the region $[0, 100]
\times [0, 100]$, we selected for all nodes $i$, $\varepsilon =
10^{-4}$.

However, as shown in the two Figures (Figure~\ref{Density} and
Figure~\ref{DensityTime}), as the number of sensor nodes increases,
the average of the iterations number as well as the time needed to
reach global convergence decreases in the two cases synchronous and
asynchronous. We notice that in the synchronous mode we obtained less
number of iterations, on the other hand it takes more time to reach
the global convergence than the asynchronous one.

%\begin{figure*}[t]
%\vspace{-5mm}
  %\begin{minipage}[b]{.5\textwidth}
\begin{figure}[h]
    \centering
    \includegraphics[scale=.55]{Density.ps}
    \caption{Number of iterations}
    \label{Density}
  %\end{minipage}%
  %\hfill%
\end{figure}
%\vspace{-5mm}
 % \begin{minipage}[b]{.50\textwidth}
\begin{figure}[h]
    \centering
    \includegraphics[scale=.55]{TimeDensity.ps}
    %\vspace{2.75mm}
    \caption{Simulated Time} 
    \label{DensityTime}
  %\end{minipage}%
  %\hfill%
\end{figure}


 \section{Further Discussions and Comparison to Other Existing Works}
\label{DISC}
In this section, we give further consideration to our data fusion
scheme from the viewpoints of robustness to the delays and loss of
messages and energy efficiency in comparison to other existing works.

Sensor nodes are small-scale devices. Such small devices are very
limited in the amount of energy they can store or harvest from the
environment. Thus, energy efficiency is a major concern in a sensor
network. In addition, many thousands of sensors may have to be
deployed for a given task.  An individual sensor's small effective
range relative to a large area of interest makes this a requirement.

Therefore, scalability is another critical factor in the network
design. Sensor networks are subject to frequent partial failures such
as exhausted batteries, nodes destroyed due to environmental factors,
or communication failures due to obstacles in the environment. Message
delays can be rather high in sensor networks due to their typically
limited communication capacity which is shared by nodes within
communication range of each other. The overall operation of the sensor
network should be robust despite such partial failures.

 In our scheme, we presented a scalable asynchronous method for
 averaging data fusion in sensor networks. The simulations we
 conducted show that, the higher the density of the deployed nodes,
 the more the precise of the estimation would be. On the other hand,
 our algorithm is totally asynchronous, where we consider delay
 transmission and loss of messages in the proposed model. These
 aspects which are highly important are not taken into account in
 previous sensor fusion works~\cite{2,18}.

 Another important practical issue in sensor network is the power
 efficiency. Optimizing the energy consumption in sensor networks is
 related to minimize the number of the network communications as the
 radio is the main energy consumer in a sensor
 node~\cite{12}. Considering the distributed iterative procedure for
 calculating averages, the only way to minimize the energy consumption
 is to reduce the number of iterations before attending the
 convergence. To show how well our algorithm saves energy, we compared
 our obtained results to those reported by another diffusive scheme
 for average computation in sensor networks~\cite{2}. For instance, in
 a static topology our algorithm converges after $69$ iterations with
 a mean error of $10^{-4}$ while the best results in the second
 approach reached $85$ iterations for the same mean error. For the
 dynamic topology mode, we obtained $105$ iterations, mean error
 $10^{-4}$ and probability of link failure $0.25$, while the number of
 iterations is very high ($\approx 300$ iterations) in~\cite{2}. In
 figure~\ref{} and figure~\ref{} we present a comparison between our
 approach and the iterative solution presented
 in~\cite{2}. For~\cite{2} we used the metropolis weights that gives
 best convergence and number of iterations results.






\section{Conclusion and Future Work}
In this chapter, we introduced a distributed asynchronous average
consensus in sensor networks. Our approach is based on data diffusion;
the nodes cooperate and exchange their information only with their
direct instantaneous neighbours. In contrast to existing works, our
algorithm does not rely on synchronization nor on the knowledge of the
global topology. We prove that under suitable assumptions, our
algorithm achieves the global convergence in the sense that, after
some iterations, each node has an estimation of the average consensus
overall the whole network. To show the effectiveness of our algorithm,
we conducted series of simulations and studied our algorithm under
various metrics.

In our scenario, we have focused on developing a reliable and robust
algorithm from the view points of asynchronism and fault tolerance in
a dynamically changing topology. We have taken into account two points
which don't have been previously addressed by other authors, namely
the delays between nodes and the loss of messages. Knowing that in
real sensor networks the nodes are prone to failures. One of the near
future goals is to allow nodes to be dynamically added and removed
during the execution of the algorithm. We also plan to test our
algorithm in a real-world sensor network.

\bibliographystyle{unsrt}  
\bibliography{references}

\end{document}