Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Optimal Clock Synchronization Under Energy Constraints in Wireless Ad-Hoc Networks

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 3974))

Included in the following conference series:

  • 677Accesses

Abstract

Clock synchronization is a crucial service in many distributed systems, including wireless ad-hoc networks. This paper studiesexternal clock synchronization, in which nodes should bring their clocks close to the value of some external reference time, which is provided in the system by one or moresource clocks.

Reference broadcast synchronization (RBS) is a known approach that exploits the broadcast nature of wireless networks for a single hop. However, when networks are large in physical extent, additional mechanisms must be employed.

Using multi-hop algorithms that re-broadcast time information to short distances reduces the energy consumed for clock synchronization. The reason is that energy costs grow more than linearly with the broadcast distance. On the other hand, the quality of the clock synchronization, as measured in the closeness of the clocks, deteriorates as the number of hops increases.

This paper shows how to balance these two contradictory goals, achieving optimal clock synchronization while adhering to an energy budget at each node. In particular, a distributed algorithm is presented that uses multi-hop broadcasting over a shallow infrastructure to synchronize the clocks. The closeness of clock synchronization achieved by the algorithm is proved to be optimal for the given energy constraints.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Afek, Y., Ricklin, M.: Sparser: A paradigm for running distributed algorithms. Journal of Algorithms 14, 316–328 (1993)

    Article MathSciNet MATH  Google Scholar 

  2. Ambühl, C., Clementi, A.E.F., Di Ianni, M., Lev-Tov, N., Monti, A., Peleg, D., Rossi, G., Silvestri, R.: Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 418–427. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  3. Attiya, H., Herzberg, A., Rajsbaum, S.: Optimal clock synchronization under different delay assumptions. SIAM Journal on Computing 25(2), 369–389 (1996)

    Article MathSciNet MATH  Google Scholar 

  4. Attiya, H., Welch, J.L.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. John Wiley& Sons, Chichester (2004)

    Book MATH  Google Scholar 

  5. Awerbuch, B., Gallager, R.G.: A new distributed algorithm to find breadth first search trees. IEEE Transactions on Information Theory 33(3), 315–322 (1987)

    Article MATH  Google Scholar 

  6. Banerjee, S., Khuller, S.: A clustering scheme for hierarchical control in multi-hop wireless networks. In: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM), pp. 1028–1037 (2001)

    Google Scholar 

  7. Biaz, S., Welch, J.L.: Closed form bounds for clock synchronization under simple uncertainty assumptions. Information Processing Letters 80, 151–157 (2001)

    Article MathSciNet MATH  Google Scholar 

  8. Blum, P., Meier, L., Thiele, L.: Improved interval-based clock synchronization in sensor networks. In: Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN), pp. 349–358 (April 2004)

    Google Scholar 

  9. Cao, G.: Distributed Services in Mobile Ad Hoc Networks. PhD thesis, Texas A&M University (April 2005)

    Google Scholar 

  10. Cormen, T.H., Lieserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge (1990)

    Google Scholar 

  11. Deo, N., Pang, C.: Shortest path algorithms: Taxonomy and annotation. Networks 14(2), 275–323 (1984)

    Article MathSciNet MATH  Google Scholar 

  12. Elson, J., Girod, L., Estrin, D.: Fine-grained network time synchronization using reference broadcasts. In: Proceedings of the 5th Symposium on Operating System Design and Implementation (OSDI) (2002)

    Google Scholar 

  13. Elson, J., Karp, R., Papadimitriou, C., Shenker, S.: Global synchronization in sensornets. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 609–624. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  14. Elson, J., Römer, K.: Wireless sensor networks: a new regime for time synchronization. Computer Communication Review 33(1), 149–154 (2003)

    Article  Google Scholar 

  15. Fan, R., Chakraborty, I., Lynch, N.: Clock synchronization for wireless networks. In: Higashino, T. (ed.) OPODIS 2004. LNCS, vol. 3544, pp. 400–414. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  16. Fan, R., Lynch, N.: Gradient clock synchronization. In: Proceedings of the 23rd ACMSymposium on Principles of Distributed Computing (PODC), pp. 320–327 (2004)

    Google Scholar 

  17. Ganeriwal, S., Kumar, R., Srivastava, M.B.: Timing-sync protocol for sensor networks. In: Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys), pp. 138–149 (2003)

    Google Scholar 

  18. Halpern, J.Y., Megiddo, N., Munshi, A.A.: Optimal precision in the presence of uncertainty. In: Proceedings of the 17th ACM Symposium on Theory of Computing (STOC), pp. 346–355 (1985)

    Google Scholar 

  19. Li, L., Halpern, J.Y., Bahl, P., Wang, Y.-M., Wattenhofer, R.: Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks. In: Proceedings of the 20th ACM Symposium on Principles of Distributed Computing (PODC), pp. 264–273 (2001)

    Google Scholar 

  20. Lundelius, J., Lynch, N.A.: An upper and lower bound for clock synchronization. Information and Control 62(2/3), 190–204 (1984)

    Article MathSciNet MATH  Google Scholar 

  21. Meier, L., Thiele, L.: Gradient clock synchronization in sensor networks. In: Proceedings of the 24th ACM Symposium on Principles of Distributed Computing (PODC), p. 238 (July 2005)

    Google Scholar 

  22. Mills, D.L.: Internet time synchronization: The Network Time Protocol. IEEE Transactions on Communications 39(10), 1482–1493 (1991)

    Article  Google Scholar 

  23. Mitra, S., Rabek, J.: Energy efficient connected clusters for mobile ad hoc networks. In: 3rd Annual Mediterranean Ad Hoc Networking Workshop (MED-HOC-NET) (2004)

    Google Scholar 

  24. Moy, J.: RFC 2328 - OSPF version 2 (April 1998)

    Google Scholar 

  25. Ostrovsky, R., Patt-Shamir, B.: Optimal and efficient clock synchronization under drifting clocks. In: Proceedings of the 18th ACM Symposium on Principles of Distributed Computing (PODC), pp. 3–12 (1999)

    Google Scholar 

  26. PalChaudhuri, S., Saha, A.K., Johnson, D.B.: Adaptive clock synchronization in sensor networks. In: Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN), pp. 340–348 (2004)

    Google Scholar 

  27. Park, V.D., Corson, M.S.: A highly adaptive distributed routing algorithm for mobile wireless networks. In: Proceedings of the Conference on Computer Communications (IEEE INFOCOM), pp. 1405–1413 (1997)

    Google Scholar 

  28. Patt-Shamir, B., Rajsbaum, S.: A theory of clock synchronization. In: Proceedings of the 26th ACM Symposium on Theory of Computing (STOC), pp. 810–819 (1994)

    Google Scholar 

  29. Römer, K.: Time synchronization in ad hoc networks. In: Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc), pp. 173–182 (2001)

    Google Scholar 

  30. Sivrikaya, F., Yener, B.: Time synchronization in sensor networks: A survey. IEEE Network, 45–50 (July/August 2004)

    Google Scholar 

  31. Sundararaman, B., Buy, U., Kshemkalyani, A.D.: Clock synchronization for wireless sensor networks: A survey. Ad Hoc Networks 3(3), 281–323 (2005)

    Article  Google Scholar 

  32. The Official U.S. time,http://www.time.gov/

  33. van Greunen, J., Rabaey, J.: Lightweight time synchronization for sensor networks. In: Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications (WSNA), pp. 11–19 (2003)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Technion, Israel

    Hagit Attiya & David Hay

  2. Computer Science Department, Texas A&M University, USA

    Jennifer L. Welch

Authors
  1. Hagit Attiya

    You can also search for this author inPubMed Google Scholar

  2. David Hay

    You can also search for this author inPubMed Google Scholar

  3. Jennifer L. Welch

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of North Carolina at Chapel Hill, USA

    James H. Anderson

  2. Università di Pisa, Italy

    Giuseppe Prencipe

  3. ETH Zurich, 8092, Zurich, Switzerland

    Roger Wattenhofer

Rights and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Attiya, H., Hay, D., Welch, J.L. (2006). Optimal Clock Synchronization Under Energy Constraints in Wireless Ad-Hoc Networks. In: Anderson, J.H., Prencipe, G., Wattenhofer, R. (eds) Principles of Distributed Systems. OPODIS 2005. Lecture Notes in Computer Science, vol 3974. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11795490_18

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp