Prediction-based Monitoring in Sensor Networks: Taking Lessons from MPEG

Abstract

In this paper we discuss the problem of monitoring data sensed in large sensor networks. A sensor typically runs on a battery having a limited lifetime. In order to increase the lifetime of a sensor it is important that the mechanisms used in monitoring them be energy-efficient. In this paper, we propose a new paradigm called Prediction-based monitoring for energy-efficient monitoring. We show that the paradigm can be visualized as a watching of a "sensor movie'' and that concepts from MPEG may be applied to it. We have implemented the proposed algorithms in a test bed of Rene Motes[2]. Experimental results show that the proposed solutions cut down the energy consumption by more than 5 times, considerably increasing sensor lifetimes, and thereby, the lifetime of the networks formed from these sensors.

Summary

In this paper, our focus is on proposing mechanisms for performing monitoring in a sensor network in an energy-efficient way. Clearly the mechanisms associated with a traditional centralized database paradigm are unsuitable for our purposes. In such a system, a central server maintains a database of readings from all the sensors. Sensors update this server when their readings change. Monitoring operation is supported by the server, which maintains the current state of all the sensors involved in the operation. There are too many messages sent in such a system, making it very energy inefficient in many cases. We make two key observations to significantly improve the energy-efficiency of monitoring operation. Firstly, sensors in close proximity are likely to have correlated readings, and in a majority of the cases, one can predict the reading at a sensor given the knowledge of readings of sensors around it and their past history. An entity (for example, base station, cluster-head) may exploit this observation and predict the set of readings that a sensor is going to see in the near future. These predictions are represented concisely as a "prediction-mode" and sent to the sensor. The sensor now needs to transmit its sensed reading to the monitoring-entity only when it differs from the reading given by the prediction model by more than a certain pre-specified threshold. This mode of working gives us a new paradigm of operation in sensor networks. We call this the PREdiction-based MONitoring (PREMON) paradigm.

Our second key observation is that a snapshot of the sensor network may be visualized as an (optical) image - the readings of individual sensors correspond to intensity values of pixels in the image. Since a monitoring operation can be thought of as receiving a sequence of these snapshots on a continuous basis, one may visualize monitoring as watching a continuous sequence of corresponding images; in effect, watching a ``video of sensed values''. Given this visualization, we explore if the concepts of MPEG[19] (a standard for video compression) may be used for compressing this ``video''. We show in section 3 that the MPEG encoder uses a paradigm that is an exact analogue of PREMON. This analogy with MPEG encoding gives us a convenient framework in which to visualize the problem. In addition, it also gives us a unique opportunity to adapt the well-established theory and algorithms of MPEG for use in sensor networks, and to examine the scope for cross-pollination between the two fields.

The PREMON paradigm prevents a sensor from unnecessarily transmitting all the readings that can be successfully predicted at the monitoring entity, thereby saving energy. This saving is obtained at the cost of extra computations at the monitoring-entity for generating prediction-models, and the extra cost of transmitting them. Given this tradeoff, clearly the effectiveness of the proposed paradigm is dependent on the accuracy with which prediction models can be generated and the percentage of readings that can be successfully predicted by them, without too much computational overhead. Based on the above observations, we propose algorithms in this paper and demonstrate their feasibility and effectiveness by implementing them on a test bed of real sensors. We show that it is feasible to generate prediction models for sensors and that significant savings can be achieved even with very simple methods of generating prediction models.

Powerpoint Presentation (PPT, HTML)

References:

• Samir Goel and Tomasz Imielinski, Prediction-based Monitoring in Sensor Networks: Taking Lessons from MPEG. ACM Computer Communication Review, Vol. 31, No. 5, October, 2001. [gzipped postscript] [PDF]

• Samir Goel and Tomasz Imielinski, Prediction-based Monitoring in Sensor Networks: Taking Lessons from MPEG. DIMACS Workshop on Pervasive Networking, May 21, 2001.

• Samir Goel and Tomasz Imielinski, Prediction-based Monitoring in Sensor Networks: Taking Lessons from MPEG. Technical Report DCS-TR-438, Department of Computer Science, Rutgers University, June 2001.