Abstract of Paper

Computing Average Value in ad hoc Networks
by Miroslaw Kutylwski and Daniel Letkiewicz

Abstract:

We consider an single-hop sensor network with $\Theta(N)$ stations using  R
independent  communication  channels. Communication between the stations
can fail at random or be scrambled by an adversary so that it cannot  be
distinguished from a random noise.

Assume that each station $S_i$ holds an integer  value  $T_i$.  The  problem
that  we consider is to replace the values $T_i$ by their average (rounded
to integer values). A typical situation is that we have a  local  sensor
network  that  needs  to  make  a  decision  based on the values read by
sensors by computing the average value or some kind of voting.

We design a protocol that solves this problem in $O(N/R  \cdot  \log  N)$
steps.  The  protocol  is robust: a constant random fraction of messages
can be lost (by communication channel failure, by action of an adversary
or  by  synchronization  problems). Also a constant fraction of stations
may  go  down  (or  be  destroyed  by  an  adversary)  without   serious
consequences  for  the  rest.  The  algorithm is well suited for dynamic
systems, for which the values $T_i$  may  change  and  the  protocol  once
started works forever.

Keywords: mobile computing, radio network, sensor network