Internal synchronization of drift-constraint clocks in ad-hoc sensor networks

ABSTRACT

Clock synchronization is a crucial basic service in typical sensor networks, since the observations of distributed sensors more often than not need to be ordered ("a happened before b") or otherwise related ("a and b happened within a time window of size x") in time. Ad-hoc networks may exhibit characteristics which make the use of traditional clock-synchronization algorithms infeasible. Recently, algorithms suitable for ad-hoc networks have been presented.We first propose an improvement to an existing algorithm. While needing less computation and no more communication or memory than the original algorithm, our new algorithm always yields equal or better results and thus outperforms the original algorithm. We then examine how even better synchronization can be obtained, possibly at the cost of additional computation, communication, and memory. To this end, we introduce a model for internal synchronization. This model allows us to find an algorithm which makes use of all the data a node can obtain from the network for a given communication pattern and thus provides optimal synchronization in our model.

REFERENCES

• 1: Avrim Blum , Shuchi Chawla , Adam Kalai, Static optimality and dynamic search-optimality in lists and trees, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.1-8, January 06-08, 2002, San Francisco, California
• 2: Benjie Chen , Kyle Jamieson , Hari Balakrishnan , Robert Morris, Span: An energy-efficient coordination algorithm for topology maintenance in Ad Hoc wireless networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.85-96, July 2001, Rome, Italy [doi>10.1145/381677.381686]
• 3: IEEE Computer Society LAN MAN Standards Committee, IEEE 802.11: Wireless LAN medium access control and physical layer specifications, August 1999.
• 4: 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]
• 5: Jason L. Hill , David E. Culler, Mica: A Wireless Platform for Deeply Embedded Networks, IEEE Micro, v.22 n.6, p.12-24, November 2002 [doi>10.1109/MM.2002.1134340]
• 6: Keith Marzullo , Susan Owicki, Maintaining the time in a distributed system, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.295-305, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806730]
• 7: David Mills, Bibliography on computer network time synchronization, available on-line at http://www.eecis.udel.edu/~mills/bib.html.
• 8: David L. Mills, Internet time synchronization: The network time protocol, IEEE Transactions on Communications 39 (1991), no. 10, 1482--1493.
• 9: Michael Mock, Reiner Frings, Edgar Nett, and Spiro Trikaliotis, Clock synchronization in wireless local area networks, Proceedings of the 12th Euromicro Conference on Real Time Systems, June 2000, pp. 183--189.
• 10: Kay Römer, Time synchronization in ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501436.501440]
• 11: Ulrich Schmid , Klaus Schossmaier, Interval-based Clock Synchronization, Real-Time Systems, v.12 n.2, p.173-228, March 1997 [doi>10.1023/A:1007957901560]
• 12: B. Simons , J. L. Welch , N. Lynch, An overview of clock synchronization, Fault-tolerant distributed computing, Springer-Verlag, London, 1990
• 13: Hagen Woesner, Jean-Pierre Ebert, Morten Schlager, and Adam Wolisz, Power saving mechanisms in emerging standards for wireless LANs: The MAC level perspective, IEEE Personal Communications 5 (1998), no. 3, 40--48.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Performance, Reliability, Theory

Keywords:
clock drift, delay, sensor networks, time synchronization