Seminar by Vinayak Naik
Sprinkler: A Reliable and Energy Efficient Data Dissemination Service for Extreme Scale Wireless Networks of Embedded Devices
Vinayak Naik
Computer Science and Automation, Indian Institute of Science
Date: Thursday, September 10, 2009
Time: 5:00 PM
Venue: CS102.Abstract:
Reprogramming in the field has emerged as a necessary primitive for wireless devices. There are many reasons for this, for instance – resulting from an incomplete knowledge of the deployment environment, planned phases of operation that are instrumented only at runtime or evolution of the operational requirements. Reprogramming necessitates a data dissemination service that is fully reliable, since a program must be delivered in entirety. Further, reprogramming must utilize minimum energy so that the lifetime of the network is maximized and must be scalable for extreme scale wireless networks, such as ExScal.
In this talk, I present Sprinkler, a reliable data dissemination service for wireless embedded devices which are constrained in energy. Sprinkler computes a near minimum connected dominating set (CDS) of the graph induced by the network topology. The nodes in the CDS are used as transmitters, thereby reducing the number of packet transmissions and conserving energy. Sprinkler uses time division multiple access (TDMA) to avoid the packet losses due to collisions. As part of Sprinkler, I will provide CDS and TDMA slot computation algorithms, each of which has O(1) time complexity. Therefore, Sprinkler is suitable for extreme scale networks. Under unit disk radio model, the number of transmitters and the number of time slots are O(1) times the minimum possible. Hence, Sprinkler uses near minimum energy and takes near minimal time to disseminate data. I will present the performance of Sprinkler in terms of number of transmitters and latency for 169 nodes in Kansei – a large scale real testbed. I will also provide a comparison with Deluge, which is a popular sensor network reprogramming service. Sprinkler uses geographic location information and assumes a minimum node density, both of which are inherent in most of the sensing applications, e.g. intruder detection.