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.
- 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.Google Scholar
- J. Elson, L. Girod, and D. Estrin. Fine-Grained Network Time Syncrhonization using Reference Broadcasts. In Proc. 5th Symp. Op. Syst. Design Implementation (OSDI), Boston, MA, 2002. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Inform. Theory, 46(2):388--404, 2000. Google ScholarDigital Library
- B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins. GPS: Theory and Practice. Springer-Verlag/Wien, 1997.Google Scholar
- A. Hu and S. D. Servetto. Optimal Detection for a Distributed Transmission Array. In Proc. IEEE Int. Symp. Inform. Theory (ISIT), Yokohama, Japan, 2003.Google Scholar
- C. Kelly IV, V. Ekanayake, and R. Manohar. SNAP: A Sensor Network Asynchronous Processor. In Proc. 9th Int. Symp. Async. Circ. Syst., Vancouver, BC, 2003. Google ScholarDigital Library
- 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/.Google Scholar
- S. M. Kay. Fundamentals of Statistical Signal Processing: Estimation Theory. PTR Prentice Hall, Inc., 1993. Google ScholarDigital Library
- H. Li, A. Lal, J. Blanchard, and D. Henderson. Self-Reciprocating Radioisotope-Powered Cantilever. J. Applied Phys., 92(2):1122--1127, 2002.Google ScholarCross Ref
- H. V. Poor. An Introduction to Signal Detection and Estimation. Springer-Verlag, 1994. Google ScholarDigital Library
- S. I. Resnick. A Probability Path. Birkhäuser, 2001.Google Scholar
- A. Scaglione and Y. W. Hong. Opportunistic Large Arrays. In IEEE Int. Symp. Adv. Wireless Comm. (ISWC02), Victoria, BC, 2002.Google Scholar
- A. Scaglione and S. D. Servetto. On the Interdependence of Routing and Data Compression in Multi-Hop Sensor Networks. In Proc. ACM MobiCom, Atlanta, GA, 2002. Google ScholarDigital Library
- 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/.Google Scholar
- S. D. Servetto. Distributed Signal Processing Algorithms for the Sensor Broadcast Problem. In Proc. 37th Annual Conf. Inform. Sciences Syst. (CISS), Baltimore, MD, 2003.Google Scholar
- S. D. Servetto. Sensing Lena---Massively Distributed Compression of Sensor Images. In Proc. IEEE Int. Conf. Image Proc. (ICIP), 2003. Invited paper.Google ScholarCross Ref
- H. Stark and J. Woods. Probability, Random Processes, and Estimation Theory for Engineers. Prentice Hall, Inc., 2nd edition, 1994. Google ScholarDigital Library
- 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.Google Scholar
- B. Warneke, M. Last, B. Liebowitz, and K. S. J. Pister. Smart Dust: Communicating with a Cubic-Millimeter Computer. IEEE Computer Mag., 34(1):44--51, 2001. Google ScholarDigital Library
Index Terms
- Asymptotically optimal time synchronization in dense sensor networks
Recommendations
Lightweight time synchronization for sensor networks
WSNA '03: Proceedings of the 2nd ACM international conference on Wireless sensor networks and applicationsThis paper presents lightweight tree-based synchronization (LTS) methods for sensor networks. First, a single-hop, pair-wise synchronization scheme is analyzed. This scheme requires the exchange of only three messages and has Gaussian error properties. ...
External Gradient Time Synchronization in Wireless Sensor Networks
Synchronization to an external time source such as Coordinated Universal Time (UTC), i.e., external synchronization, while preserving tight synchronization among neighboring sensor nodes may be crucial for applications such as determining the speed of a ...
Ratio-based time synchronization protocol in wireless sensor networks
Time synchronization plays a key role in the wireless sensor networks (WSNs). Time synchronization is realized by those messages that are time-stamped. But there are several delay times during transmission after time stamping. Most of them are uncertain ...
Comments