Mechanisms for energy conservation in wireless sensor networks
Supervisor: Maurizio Bonuccelli
Thesis commettee: Paolo Ferraggina, Piero Maestrini
External referees: Stefano Basagni, Mani Srivastava
National commettee: Bugliesi, Meo, and Panzieri
December 27, 2005
Abstract
In this thesis we address the problem
of reducing energy consumption in wireless sensor networks. We propose
a suit of techniques and
strategies imported from other
research areas that can be applied to design energy-efficient protocols
in sensor networks. They include
time series forecasting, quorums
systems, and the interaction between sensor properties and protocol
design. We apply these techniques to the time synchronization problem,
to efficiently collecting data from a sensor network, and to ensuring
stronger data consistency guarantees in mobile networks.
We show in [1,2,3,4] that time series forecasting techniques, and in particular autoregressive (AR) models, can be applied to sensor networks to conserve energy. We study a simple type of time series models with a short prediction window. We have chosen this model because it is capable
of predicting data produced by
real-world sensors measuring physical phenomena, and it is
computationally tractable on modern-generation sensor networks. We
apply these models to solve two relevant problems in sensor networks:
the problem of efficiently collecting sensor data at the sink, and the
time synchronization problem.
We propose an energy-efficient framework, called SAF Similarity--based Adaptable query Framework
[1,2] ), for approximate querying and detecting outlier values in
sensor networks. The idea is to combine local AR models built at each
node into a global model stored at the root of the network
(the sink)
that is used to approximately answer user queries. Our approach uses
dramatically fewer transmissions than previous approximate approaches
by using AR models and organizing the network into clusters
based on data similarity between nodes. Our definition of data
similarity is based on the coefficients of the local AR models stored
at the sink, which reduces energy consumption over techniques that
directly compare data values, and allows us to derive an efficient
clustering algorithm that is provably optimal
in the number of clusters formed by the network. Our clusters have
several interesting features that make them suitable also for mobile
networks: first, they can capture similarity between nodes that are not
geographically adjacent; second, cluster membership adapts at no
additional cost; third, nodes within a cluster are not required to
track the membership of other nodes in the cluster. Furthermore, SAF
provides provably correct
error bounds and allows the user to dynamically tune answer quality to
answer queries in an energy and resource efficient manner.
In addition, we apply the AR models to solve the time synchronization problem from a novel perspective which
is complementary to the well-studied clock synchronization problem
[3,4]. More precisely, we analyze the case in which a sensor node
decides to skip one or more clock adjustments to save energy, or it is
temporarily isolated, but still requires an accurate estimate of the
time. We propose a provably correct
clock method based on AR models, which returns a time estimate within a
constant (tunable) error bound and error probability. This method is
highly adaptable and allows the sensor to decide how many
clock adjustments it can skip while
maintaining the same time accuracy, thus saving energy. In addition, we
propose a suit of deterministic methods that reduce the time estimation
error by at least a factor 2. More precisely, we propose a provably correct
deterministic clock reading method, called the DCR method, which
exploits information regarding the sign of the clock deviation, and can
be applied to reduce by half the frequency of the periodic clock
adjustments, while maintaining the same error bound [3,4].
This method is of both practical and theoretical
interest. In fact, it leads to a noticeable energy saving, and shows
that a stronger but realistic clock model can lead to a refinement of
the optimality bound
for the maximum deviation of a clock that is periodically synchronized.
In addition, we propose a generalized version of the DCR method that
enhances its accuracy depending on the clock stability, and a method
that guarantees the monotonicity of the time values produced.
We analyze for the first time quorum system techniques
in the context of sensor networks: we redesign them and show their
benefits in terms of energy consumption [6]. Quorum systems have the
potential to save energy in sensor networks since they can reduce
noticeably the amount of communication, improve the load balance among
sensor nodes, and enhance the scalability of the system. However,
previous quorum systems and quorum metrics, proposed for wired
networks, are unsuitable for sensor networks since they do not address
their properties and limitations. These observations have motivated us
to redesigning quorum systems and their metrics, taking into account
the limitations and characteristics of sensors (e.g., transmission
costs, limited energy
source, physical radio broadcast), and
the network topology. More precisely, we redefine the following quorum
metrics: load balance, access cost and quorum capacity,
and devise some strategies based on some characteristics of sensor
networks that reduce the amount of communication when designing quorum
systems for sensor networks. We apply these strategies to design a
family of energy-efficient quorum systems with high resiliency. In
particular, we propose a quorum construction that reduces the quorum
access cost, and propose an energy-efficient data diffusion protocol
built on top of it that reduces the energy consumption by reducing the
amount of transmissions and collisions.
In addition, we analyze quorum systems
in case of high node mobility. More precisely, we study the difficult
problem of guaranteeing the intersection between two quorums in case
nodes move continuously along unknown paths [7]. We address this
problem by defining a novel mobility model
that provides a minimum set of constraints sufficient to derive strong
data guarantees in highly mobile networks. Also in this case, we show
the unsuitability of previous quorum systems, and provide a
condition which is necessary to guarantee data availability and atomic
consistency under high node mobility. We propose a new class
of quorum systems, called Mobile Dissemination (MD) quorums, suitable for highly mobile networks, and propose a quorum construction which is optimal with respect to the quorum size (i.e., message transmissions) [7]. Then, we apply the MD quorum system to implement a provably correct atomic read/write shared memory for mobile and sparse networks.
Bibliography
[1] D. Tulone, S. Madden. PAQ: Time series forecasting for approximate query answering
in sensor networks. In Proc. of the 3rd European Workshop on Wireless Sensor Networks, pp. 21-37, Feb 2006.
[2] D. Tulone, S. Madden. An energy-efficient querying framework in sensor networks for detecting node similarities.
Submitted to conference.
[3] D. Tulone. On the feasibility of global time estimation under isolation conditions in wireless sensor networks.
To appear in Algorithmica.
[4] D. Tulone. A resource-efficient time estimation for wireless sensor networks. In Proc. of the 4th Workshop of Principles of Mobile Computing, pp. 52-59, Oct 2004.
[5] D. Tulone. How efficiently and accurately can a process get the reference time? Intl. Symp. on Distributed Computing, Oct
2003. Brief announcement, pp. 25-32.
[6] D.Tulone, E. D. Demaine. Redesigning quorum systems for wireless sensor networks. Submitted to conference.
[7] D. Tulone. Is it possible to ensure strong data guarantees in highly mobile networks? Submitted to conference.