Sensor field: a computational model

In this work we introduce a formal model for studying networks of tiny artifacts, the static synchronous sensor field model (SSSF). The model consider that these devices communicate among them by means of a communication graph. A sensor field interacts with the environment with input/output data streams. We start analyzing the behavior of networks in which at every step each sensor takes a new input data item and outputs (with some possible latency) an output data item. Accordingly we introduce adequate performance measures like latency, message number, or message length. We study two sensing problems the Average Monitoring and the Alerting problems. For the Average Monitoring problem we give upper bounds on the latency, number of required messages and their size and optimal algorithms to solve it in specific topologies. We show that the Alerting problem can be solved with sensing devices of constant memory. When the SSSFs are allowed to use only devices with constant memory capacity we demonstrate that the decisional version of the functions computed by such SSSFs are in the class DSPACE(max(n,m)) where n is the number of nodes of the communication graph and m its number of edges. If in this kind of SSSFs we consider the possibility of using more non-sensing tiny devices than input data streams we show that monitoring a property that is polynomial time computable can be solved by SSSFs of polynomial size and latency with respect to the number of input data streams.