Computing average value in  ad  hoc  networks  
           Miroslaw  Kutylowski and Daniel Letkiewicz

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