Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Radio duty cycling has received significant attention in sensor networking literature, particularly in the form of protocols for medium access control and topology management. While many protocols have claimed to achieve significant duty-cycling benefits in theory and simulation, these benefits have often not translated to practice. The dominant factor that prevents the optimal usage of the radio in real deployment settings is time uncertainty between sensor nodes. This paper proposes an uncertainty-driven approach to duty-cycling where a model of long-term clock drift is used to minimize the duty-cycling overhead. First, we use long-term empirical measurements to evaluate and analyze in-depth the interplay between three key parameters that influence long-term synchronization - synchronization rate, history of past synchronization beacons and the estimation scheme. Second, we use this measurement-based study to design a rate-adaptive, energy-efficient long-term time synchronization algorithm that can adapt to changing clock drift and environmental conditions while achieving application-specific precision with very high probability. Finally, we integrate our uncertainty-driven time synchronization scheme with a MAC layer protocol, BMAC, and empirically demonstrate one to two orders of magnitude reduction in the transmit energy consumption at a node with negligible impact on the packet loss rate.

REFERENCES

• 1: Dutta, P., Grimmer, M., Arora A., Bibyk S., Culler D. Design of a wireless sensor network platform for detecting rare, random, and ephemereal events. Special Track on Platform Tools and Design Methods for Network Embedded Sensors (SPOTS), 2005.
• 2: Joseph Polastre , Jason Hill , David Culler, Versatile low power media access for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031508]
• 3: Ye, W., Heidemann, J., Estrin, D. An energy-efficient MAC protocol for wireless sensor networks. In Proceedings of the 21st International Conference of the IEEE Computer and Communications Societies (Infocom), 2002.
• 4: Tijs van Dam , Koen Langendoen, An adaptive energy-efficient MAC protocol for wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958512]
• 5: Miklós Maróti , Branislav Kusy , Gyula Simon , Ákos Lédeczi, The flooding time synchronization protocol, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031501]
• 6: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 7: Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958508]
• 8: CENS habitat sensing group at James Reserve. http://www.jamesreserve.edu/
• 9: Gyula Simon , Miklós Maróti , Ákos Lédeczi , György Balogh , Branislav Kusy , András Nádas , Gábor Pap , János Sallai , Ken Frampton, Sensor network-based countersniper system, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031497]
• 10: Mills, D. L. Internet time synchronization: The network time protocol. Global States and Time in Distributed Systems, IEEE Computer Society Press, 1994.
• 11: Sundararaman, B., Buy, U., Kshemkalyani, D. Clock synchronization for wireless sensor networks: A Survey. Ad-hoc Networks, 3(3): 281--323, May 2005.
• 12: David L. Mills, Adaptive hybrid clock discipline algorithm for the network time protocol, IEEE/ACM Transactions on Networking (TON), v.6 n.5, p.505-514, Oct. 1998 [doi>10.1109/90.731182]
• 13: Rao, C. R. Linear statistical inference and its applications. John Wiley & Sons, New York, 1973.
• 14: Allan Variance. http://www.allanstime.com/AllanVariance.
• 15: Tsiatsis, V., Sim, H., Ganeriwal, S., Ganesan, D., Srivastava, M. B. Implementation of rate adaptive time synchronization protocol in TinyOS. Technical Report, NESL 2005.
• 16: Softfloat. http://www.jhauser.us/arithmetic/SoftFloat.html
• 17: Chip-scale vapor-cell atomic clocks at NIST. http://www.bouldernist.gov/timefreq/ofm/smallclock/

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Experimentation, Performance, Verification

Keywords:
clock drift, polynomial model estimation, rate adaptation, sampling period, sensor networks, time synchronization