Asymptotically optimal time synchronization in dense sensor networks

ABSTRACT

We consider the problem of synchronization of all clocks in a sensor network, in the regime of asymptotically high node densities. We formulate this problem as one in which all clocks must line up with the clock of an arbitrary node in the network (of course without assuming that this clock can be observed everywhere in the network, nor assuming that this node has any special hardware--this node could be any). We give a state-space description for the generation of observable data as a function of the ideal clock, and we derive an optimal estimator for determining the state of the ideal clock. A salient feature of our approach is that nodes collaborate to generate an aggregate waveform that can be observed simultaneously by all nodes, and that contains enough information to synchronize all clocks. This aggregate waveform effectively simulates the presence of a "super-node" capable of generating a high-power, network-wide time reference signal.

REFERENCES

• 1: J. Barros and S. D. Servetto. Coding Theorems for the Sensor Reachback Problem with Partially Cooperating Nodes. In Discrete Mathematics and Theoretical Computer Science (DIMACS) series on Network Information Theory, Piscataway, NJ, 2003.
• 2: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844143]
• 3: J. Elson and K. Römer. Wireless Sensor Networks: A New Regime for Time Synchronization. In Proc. First Workshop on Hot Topics In Networks (HotNets-I), Princeton, NJ, 2002.
• 4: P. Gupta and P. R. Kumar. Critical Power for Asymptotic Connectivity in Wireless Networks. In W. M. McEneany, G. Yin, and Q. Zhang, editors, Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming. Birkhauser, 1998.
• 5: P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Inform. Theory, 46(2):388--404, 2000.
• 6: B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins. GPS: Theory and Practice. Springer-Verlag/Wien, 1997.
• 7: A. Hu and S. D. Servetto. Optimal Detection for a Distributed Transmission Array. In Proc. IEEE Int. Symp. Inform. Theory (ISIT), Yokohama, Japan, 2003.
• 8: Clinton Kelly, IV , Virantha Ekanayake , Rajit Manohar, SNAP: A Sensor-Network Asynchronous Processor, Proceedings of the 9th International Symposium on Asynchronous Circuits and Systems, p.24, May 12-15, 2003
• 9: R. Karp, J. Elson, D. Estrin, and S. Shenker. Optimal and Global Time Synchronization in Sensornets. Technical Report~9, Center for Embedded Network Sensing, UCLA, 2003. Available from http://lecs.cs.ucla.edu/.
• 10: Steven M. Kay, Fundamentals of statistical signal processing: estimation theory, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 11: H. Li, A. Lal, J. Blanchard, and D. Henderson. Self-Reciprocating Radioisotope-Powered Cantilever. J. Applied Phys., 92(2):1122--1127, 2002.
• 12: H. Vincent Poor, An introduction to signal detection and estimation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1994
• 13: S. I. Resnick. A Probability Path. Birkhäuser, 2001.
• 14: A. Scaglione and Y. W. Hong. Opportunistic Large Arrays. In IEEE Int. Symp. Adv. Wireless Comm. (ISWC02), Victoria, BC, 2002.
• 15: Anna Scaglione , Sergio D. Servetto, On the interdependence of routing and data compression in multi-hop sensor networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570663]
• 16: S. D. Servetto. Quantization with Side Information: Lattice Codes, Asymptotics, and Applications in Wireless Networks. Submitted to the IEEE Trans. Inform. Theory, March 2002. Available from http://cn.ece.cornell.edu/.
• 17: S. D. Servetto. Distributed Signal Processing Algorithms for the Sensor Broadcast Problem. In Proc. 37th Annual Conf. Inform. Sciences Syst. (CISS), Baltimore, MD, 2003.
• 18: S. D. Servetto. Sensing Lena---Massively Distributed Compression of Sensor Images. In Proc. IEEE Int. Conf. Image Proc. (ICIP), 2003. Invited paper.
• 19: Henry Stark , John W. Woods, Probability, random processes, and estimation theory for engineers, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 20: H. Wang, L. Yip, D. Maniezzo, J. C. Chen, R. E. Hudson, J. Elson, and K. Yao. A Wireless Time-Synchronized COTS Sensor Platform: Applications to Beamforming. In Proc. IEEE CAS Workshop Wireless Comm. Networking, Pasadena, CA, 2002.
• 21: Brett Warneke , Matt Last , Brian Liebowitz , Kristofer S. J. Pister, Smart Dust: Communicating with a Cubic-Millimeter Computer, Computer, v.34 n.1, p.44-51, January 2001 [doi>10.1109/2.963443]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Reliability, Theory