Aggregation Methods for Very Large Scale Sensor Networks
LAUKIK CHITNIS

Due to the advancements in producing cheap, sophisticated sensors,
applications of large sensor networks in natural sciences and engineering
will become cost feasible in few years. The ability to efficiently aggregate
information -- for example compute the average temperature -- in such large
networks is crucial for the successful deployment of sensor networks. This
paper addresses the problem of designing \emph{truly scalable} protocols for
computing aggregates in the presence of faults, protocols that can enable
million node sensor networks to work efficiently. More precisely, we make
four distinct contributions. First, we introduce a simple fault model and
analyze the behavior of two existing protocols under the fault model:
\emph{tree aggregation} and \emph{gossip aggregation}. Second, since the
behavior of the two protocols depends on the size of the network and
probability of failure, we introduce a hybrid approach that can leverage the
strengths of the two protocols and minimize the weaknesses; the new protocol
is analyzed under the same fault model. Third, we propose methodology for
determining the \emph{optimal} mix between the two basic protocols; the
methodology consists in formulating an optimization problem, using models of
the protocol behavior, and solving it. Fourth, we propose new methodology
for validating protocols on millions of nodes -- for such large networks
complete simulation is not feasible -- and use the methodology to validate
the hybrid protocol.