ALCOMFT-TR-02-114

Ioannis Chatzigiannakis, Sotiris Nikoletseas and Paul Spirakis
Smart Dust Local Detection and Propagation Protocols
Patras. Work package 2. May 2002.

Abstract: Smart Dust is a set of a vast number of ultra-small fully autonomous computing and communication devices, with very restricted energy and computing capabilities, that co-operate to quickly and efficienty accomplish a large sensing task. Smart Dust can be very useful in practice i.e. in the local detection of a remote crucial event and the propagation of data reporting its realization. In this work we open the research on smart dust from a basic algorithmic point of view. We first provide a simple but realistic model for smart dust and present an interesting problem, which is how to propagate efficiently an event detected locally. Then we present a set of smart dust protocols for local detection and perform a rigorous average case analysis on their efficiency and energy consumption (and their interplay). This analysis leads to concrete results showing that our protocols are very efficient.

Postscript file: ALCOMFT-TR-02-114.ps.gz (187 kb).