CSAIL Research Abstracts - 2005 link to http://publications.csail.mit.edu/abstracts/abstracts05/index.html link to http://www.csail.mit.edu
bullet Introduction bullet Architecture, Systems
& Networks
bullet Language, Learning,
Vision & Graphics
bullet Physical, Biological
& Social Systems
bullet Theory bullet

horizontal line

Efficiency Issues in Highly Dynamic Networks

Daniela Tulone & Nancy Lynch

Introduction

The design of distributed primitives in wireless networks introduces challenges that are substantially different from those present in infrastructure-based networks, such as limited energy and network bandwidth, dynamic topology, and higher failure rate. In this project we intend to address these aspects, and in particular study strategies such as trade-offs or optimistic approaches to reconcile energy efficiency and fault-tolerance. The idea is to exploit “physical properties” inherent to mobile networks and to the problem in consideration. We have focused our attention on two particular fundamental building blocks for ad hoc networks: the time estimation service, and the implementation of atomic read/write shared memories.  We have shown in the first case how properties related to the deviation of the hardware clock can be applied to improve both robustness and energy consumption, and in the second case how node reliability and mobility can support data consistency in highly mobile networks.

Time Estimation in Wireless Sensor Networks

Time synchronization is a critical building block in many sensornet tasks, such as TDMA medium access scheduling, object tracking, surveillance, duplicate detection, distributed beam-forming, or data fusion. Despite the large volume of work in infrastructure-based networks none of these solutions suits well the wireless sensor networks (WSN). In fact, time synchronization in WSN has to meet challenges which are substantially different from those in infrastructure-based networks such as limited energy and bandwidth, higher failure rate, dynamic topology or intermittent connectivity.  All these elements lead to strong energy-efficiency, robustness and self-configuration requirements.

Approach

Despite their diversity, all clock synchronization protocols for WSN share a common viewpoint: each node derives a notion of time through messages exchanged with its neighbors. We studied the time synchronization problem from a novel perspective which is complementary to the well-studied clock synchronization problem. We addressed the following question: "what time accuracy can be provided in case of node isolation or low-energy?" More precisely, we analyzed the case in which a sensor node is temporarily unable to run a clock synchronization protocol due to intermittent connectivity, or node failures, or low-energy, but still requires an accurate estimate of the reference time.  

Progress

We proposed two simple and efficient clock reading methods, one deterministic and the other probabilistic, which are designed to work in synergy with a clock synchronization protocol. The deterministic method achieves a better time accuracy by exploiting the sign of the global deviation of the hardware clock from the reference time. It can be applied to reduce the frequency of the periodic clock adjustments by a factor 2, while maintaining the same error bound. We propose also a generalization which can lead to a better accuracy depending on the degree of the “current” clock instability. Both methods are significant for showing how a stronger but realistic clock model can lead to a refinement of the lower bound for the maximum deviation of a clock which is periodically synchronized. The probabilistic method is based on time series forecasting, and provides a probabilistically accurate estimate of the reference time with a constant error bound. It is more flexible than the deterministic methods since it does not depend on the frequency at which clock synchronization occurs, and it is easily tunable according to the higher level application requirements and to the resource availability. All these methods can be employed either to enhance the robustness of the time estimate, or to save energy by reducing the frequency of clock adjustments.

Future Work

These techniques, especially the probabilistic method, are not limited to the time synchronization problem, but they can be generalized to the evaluation problem in which a node has to evaluate within some maximum error, some physical measurement sent by a source in the presence of noise. Notice that time is a particular case of the evaluation problem where the noise is represented by the message delay from the source to the node.

Data Consistency in Highly Mobile Networks
Problem

The dynamic topology of mobile networks, their higher failure rate, along with the limited energy of the mobile nodes make the design of coordination protocols in wireless sensor networks more challenging. The focal point model introduced by Dolev et al. in [3], provides a powerful tool for masking the dynamic nature of wireless networks by a static model: it associates abstract nodes with fixed geographical locations. Dolev et al. proposed also an implementation of an atomic read/write shared memory based on their abstract model. However, their implementation tolerates only a threshold of focal point failures during the entire system lifetime, since it does not allow faulty focal points to recover. Clearly, this can represent a strong limitation in highly mobile networks where mobile nodes continue moving from one geographical location to another.  

Approach and Progress

We have studied the problem of how to enhance the robustness of their implementation, by allowing faulty focal points to recover, thus tolerating any number of failures, provided a limited number during an a-priori known failure window. We do not rely on a synchronous network, unstable conditions of the network might occur but the system eventually recovers.  Our approach is optimistic: the recovery protocol consists of a procedure executed in case of network stability and based on dissemination quorum systems, and a self-stabilizing procedure invoked in case of prolonged unstable conditions of the network. The self-stabilizing procedure is based on the reliability of the underlying physical nodes and their mobility.

Future work

This protocol can be generalized and be used as a building block to study data consistency in a more general setting where the geographical area of the system is not bounded and a-priori known.

Research Support

This project is supported by DARPA Air Force contract number FA9550-04-C-0084, DARPA Award number F33615-01-C-1896, NSF Award numbers CCR-0326277 and CCR-0121277, NSF-Texas Engineering Experiment Station grant 64961-CS, DARPA/AFOSR MURI Award F49620-02-1-0325 and MURI AFOSR Award Number SA2796PO 1-0000243658.

References:

[1] Shlomi Dolev, Seth Gilbert, Nancy A. Lynch, Alexander A. Shvartsman, Jennifer L.Welch. GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks. Journal submission.

[2] Daniela Tulone, Nancy Lynch. Implementing atomic memory in highly mobile networks. In preparation.

[3] Daniela Tulone. On the feasibility of global time estimation under isolation conditions in wireless sensor networks. Journal submission.

[4] Daniela Tulone. A resource-efficient time estimation for wireless sensor networks. In Proc. of the 4th Workshop of Principles of Mobile Computing (DIALM-POMC '04), pp. 52-59, Philadelphia, October 2004.

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu
(Note: On July 1, 2003, the AI Lab and LCS merged to form CSAIL.)