ETD system

Electronic theses and dissertations repository

 

Tesi etd-05132010-115235


Thesis type
Tesi di dottorato di ricerca
Author
TULONE, DANIELA
URN
etd-05132010-115235
Title
Mechanisms for energy conservation in wireless sensor networks
Settore scientifico disciplinare
INF/01
Corso di studi
INFORMATICA
Commissione
tutor Prof. Bonuccelli, Maurizio
Parole chiave
Data inizio appello
26/06/2006;
Consultabilità
parziale
Data di rilascio
26/06/2046
Riassunto analitico
In this thesis we address the problem of reducing energy consumption in wireless<br>sensor networks. We propose a suit of techniques and strategies imported from other<br>research areas that can be applied to design energy-e±cient protocols in sensor net-<br>works. They include time series forecasting, quorums systems, and the interaction<br>between sensor properties and protocol design. We apply these techniques to the time<br>synchronization problem, to e±ciently collecting data from a sensor network, and to<br>ensuring stronger data consistency guarantees in mobile networks.<br>We show in [118, 119, 40, 41] that time series forecasting techniques, and in<br>particular autoregressive (AR) models, can be applied to sensor networks to conserve<br>energy. We study a simple type of time series models with a short prediction window.<br>We have chosen this model because it is capable of predicting data produced by real{<br>world sensors measuring physical phenomena, and it is computationally tractable on<br>modern-generation sensor networks. We apply these models to solve two relevant<br>problems in sensor networks: the problem of e±ciently collecting sensor data at the<br>sink, and the time synchronization problem.<br>We propose an energy{e±cient framework, called SAF (Similarity{based Adapt-<br>able query Framework [118, 119]), for approximate querying and detecting outlier<br>values in sensor networks. The idea is to combine local AR models built at each<br>node into a global model stored at the root of the network (the sink) that is used<br>to approximately answer user queries. Our approach uses dramatically fewer trans-<br>missions than previous approximate approaches by using AR models and organizing<br>the network into clusters based on data similarity between nodes. Our de¯nition of<br>data similarity is based on the coe±cients of the local AR models stored at the sink,<br>which reduces energy consumption over techniques that directly compare data values,<br>and allows us to derive an e±cient clustering algorithm that is provably optimal in<br>the number of clusters formed by the network. Our clusters have several interesting<br>features that make them suitable also for mobile networks: ¯rst, they can capture<br>similarity between nodes that are not geographically adjacent; second, cluster mem-<br>bership adapts at no additional cost; third, nodes within a cluster are not required<br>to track the membership of other nodes in the cluster. Furthermore, SAF provides<br>provably correct error bounds and allows the user to dynamically tune answer quality<br>to answer queries in an energy and resource e±cient manner.<br>In addition, we apply the AR models to solve the time synchronization problem<br>from a novel perspective which is complementary to the well-studied clock synchro-<br>nization problem [40, 41]. More precisely, we analyze the case in which a sensor node<br>decides to skip one or more clock adjustments to save energy, or it is temporarily<br>isolated, but still requires an accurate estimate of the time. We propose a provably<br>correct clock method based on AR models, which returns a time estimate within a<br>constant (tunable) error bound and error probability. This method is highly adapt-<br>able and allows the sensor to decide how many clock adjustments it can skip while<br>maintaining the same time accuracy, thus saving energy. In addition, we propose<br>a suit of deterministic methods that reduce the time estimation error by at least a<br>factor 2. More precisely, we propose a provably correct deterministic clock reading<br>method, called the DCR method, which exploits information regarding the sign of the<br>clock deviation, and can be applied to reduce by half the frequency of the periodic<br>clock adjustments, while maintaining the same error bound [40, 41]. This method<br>is of both practical and theoretical interest. In fact, it leads to a noticeable energy<br>saving, and shows that a stronger but realistic clock model can lead to a re¯nement<br>of the optimality bound for the maximum deviation of a clock that is periodically<br>synchronized. In addition, we propose a generalized version of the DCR method that<br>enhances its accuracy depending on the clock stability, and a method that guarantees<br>the monotonicity of the time values produced.<br>We analyze for the ¯rst time quorum system techniques in the context of sensor<br>networks: we redesign them and show their bene¯ts in terms of energy consumption<br>[85]. Quorum systems have the potential to save energy in sensor networks since<br>they can reduce noticeably the amount of communication, improve the load balance<br>among sensor nodes, and enhance the scalability of the system. However, previous<br>quorum systems and quorum metrics, proposed for wired networks, are unsuitable<br>for sensor networks since they do not address their properties and limitations. These<br>observations have motivated us to redesigning quorum systems and their metrics,<br>taking into account the limitations and characteristics of sensors (e.g., transmission<br>costs, limited energy source, physical radio broadcast), and the network topology.<br>More precisely, we rede¯ne the following quorum metrics: load balance, access cost<br>and quorum capacity, and devise some strategies based on some characteristics of<br>sensor networks that reduce the amount of communication when designing quorum<br>systems for sensor networks. We apply these strategies to design a family of energy-<br>e±cient quorum systems with high resiliency. In particular, we propose a quorum<br>construction that reduces the quorum access cost, and propose an energy-e±cient<br>data di®usion protocol built on top of it that reduces the energy consumption by<br>reducing the amount of transmissions and collisions.<br>In addition, we analyze quorum systems in case of high node mobility. More<br>precisely, we study the di±cult problem of guaranteeing the intersection between two<br>quorums in case nodes move continuously along unknown paths [149]. We address<br>this problem by de¯ning a novel mobility model that provides a minimum set of<br>constraints su±cient to derive strong data guarantees in highly mobile networks.<br>Also in this case, we show the unsuitability of previous quorum systems, and provide<br>a condition which is necessary to guarantee data availability and atomic consistency<br>under high node mobility. We propose a new class of quorum systems, called Mobile<br>Dissemination (MD) quorums, suitable for highly mobile networks, and propose a<br>quorum construction which is optimal with respect to the quorum size (i.e., message<br>transmissions) [149]. Then, we apply the MD quorum system to implement a provably<br>correct atomic read/write shared memory for mobile and sparse networks.
File