Thesis commettee: Paolo Ferraggina, Piero Maestrini

External referees: Stefano Basagni, Mani Srivastava

National commettee: Bugliesi, Meo, and Panzieri

December 27, 2005

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.

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.