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-e±cient protocols in sensor net-
works. 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 e±ciently collecting data from a sensor network, and to
ensuring stronger data consistency guarantees in mobile networks.
We show in [118, 119, 40, 41] 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 e±ciently collecting sensor data at the
sink, and the time synchronization problem.
We propose an energy{e±cient framework, called SAF (Similarity{based Adapt-
able query Framework [118, 119]), 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 trans-
missions than previous approximate approaches by using AR models and organizing
the network into clusters based on data similarity between nodes. Our de¯nition of
data similarity is based on the coe±cients 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 e±cient 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: ¯rst, they can capture
similarity between nodes that are not geographically adjacent; second, cluster mem-
bership 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 e±cient 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 synchro-
nization problem [40, 41]. 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 adapt-
able 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 [40, 41]. 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 re¯nement
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 ¯rst time quorum system techniques in the context of sensor
networks: we redesign them and show their bene¯ts in terms of energy consumption
[85]. 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 rede¯ne 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-
e±cient quorum systems with high resiliency. In particular, we propose a quorum
construction that reduces the quorum access cost, and propose an energy-e±cient
data di®usion 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 di±cult problem of guaranteeing the intersection between two
quorums in case nodes move continuously along unknown paths [149]. We address
this problem by de¯ning a novel mobility model that provides a minimum set of
constraints su±cient 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) [149]. Then, we apply the MD quorum system to implement a provably
correct atomic read/write shared memory for mobile and sparse networks.