Title:
|
Sensor field: a computational model
|
Author:
|
Álvarez Faura, M. del Carme; Duch Brown, Amalia; Gabarró Vallès, Joaquim; Serna Iglesias, María José
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals |
Abstract:
|
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. |
Abstract:
|
Peer Reviewed |
Subject(s):
|
-Àrees temàtiques de la UPC::Enginyeria electrònica::Instrumentació i mesura::Sensors i actuadors -Sensor networks -Tiny artifacts -Sensors -Computational models -Data streams -Average monitoring problem -Alerting problem -Static synchronous sensor field -Xarxes de sensors |
Rights:
|
Attribution-NonCommercial-NoDerivs 3.0 Spain
http://creativecommons.org/licenses/by-nc-nd/3.0/es/ |
Document type:
|
Article - Submitted version Conference Object |
Share:
|
|