Mechanisms for energy conservation in wireless sensor networks

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.