Location and Time In Sensor Networks

Speaker Dr. Ryo Sugihara,
University of California, San Diego
CECS Host Elaheh Bozorgzadeh
Location Donald Bren Hall (DBH) 4011
Date & Time April 30, 2010
Refreshments at 10:30 am, Lecture begins at 11:00 am
Abstract In this talk I will present two of my projects related to location and time in sensor networks. First is location-based job scheduling. Specifically I will talk about the use of controlled mobility for data collection in sensor networks. As controllable mobile nodes (called “data mules”) travel across the sensor field to bring the data back to the base station, how the data mules choose their paths, change speed, and schedule communication are important problems for minimizing the data collection latency. We formulated the problem as a scheduling problem called data mule scheduling (DMS) problem. This is an interesting extension to traditional job scheduling problem: each job has release and deadline on the location axis instead of the time axis. We have analyzed the complexity for several different mobility models and designed optimal and approximate algorithms. I will also talk about the similarity with dynamic voltage scaling problem.

In the second part, I will introduce our recent work on clock synchronization protocol in sensor networks. Although clock synchronization has been studied for a long time in sensor networks as well as in distributed systems, recent synchronization protocols for sensor networks have been mostly focused on achieving good average accuracy. While these protocols achieve microsecond-order accuracy, many of them do not have any guarantees on the worst case. However, as sensor networks become used more widely or incorporated into larger systems in the form of CPS (cyber-physical system), the notion of guaranteed performance increases importance much more than ever. To deal with this, our work is focused on providing guaranteed accuracy in clock synchronization. Based on observation of the characteristics of crystal oscillators on sensor nodes, our synchronization protocol achieves much tighter accuracy guarantee than the classical methods (sometimes called “interval-based clock synchronization algorithms”) can provide.

Biography Ryo Sugihara received the BE and ME degrees in mechanical engineering from the University of Tokyo, Japan, in 1997 and 1999, respectively. He received the PhD degree in computer science in 2009 from the University of California, San Diego, where he is currently working as a postdoctoral researcher. Previously, he worked at the IBM Tokyo Research Laboratory, where he was engaged in research and development on video digital watermarking and large-scale video streaming. His current research interests include sensor networks and mobile ad hoc networks. He was a recipient of the Best Paper Award of the Systems track at IEEE DCOSS 2008.