Method and apparatus for clock synchronization in a wireless network

• US 20040008661A1
• Filed: 03/29/2002
• Published: 01/15/2004
• Est. Priority Date: 03/29/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Systems Wireless Networking (Australia) Pty Limited (Cisco Systems, Inc.)
• Inventors: Goodall, David S., Myles, Andrew F., Lam, Alex C.K.
• Granted Patent: US 7,151,945 B2
• Time in Patent Office: Days
• US Class Current: 370/350
• CPC Class Codes: H04J 3/0664 unidirectional timestamps
• CPC Class Codes: H04J 3/0697 Synchronisation in a packet node
• CPC Class Codes: H04L 7/08 the synchronisation signals recurring cyclically
• CPC Class Codes: H04W 56/009 Closed loop measurements

Abstract

A method and apparatus for synchronizing a local clock value in a wireless receiver receiving a data unit containing synchronization information. The method includes receiving a first data unit containing synchronization information, extracting the synchronization information from the received first data unit, copying a local free-running clock at a known reference point in time relative to the time the first data unit was received to generate a local timestamp; and calculating an offset to the free-running clock using the extracted synchronization information and the local timestamp, the calculating in non real-time, such that the sum of the calculated offset and the value of the free-running clock provides a local clock value that is approximately synchronized in time. The apparatus implementing the method is part of a node of a wireless station, and provides a time synchronization function, typically at the MAC layer.

Claims

1. A method of synchronizing a local clock value in a wireless receiver receiving a data unit containing synchronization information, the method comprising:

receiving a first data unit containing synchronization information transmitted by a first transmitter having a local clock value;

copying a local free-running clock at a known reference point in time relative to the time the first data unit was received to generate a local timestamp;

extracting the synchronization information from the received first data unit; and

calculating an offset to the free-running clock using the extracted synchronization information and the local timestamp, the calculating in non real-time,

such that the sum of the calculated offset and the value of the free-running clock provides a local clock value for the receiver, and such that the receiver'"'"'s local clock value is approximately synchronized in time to the local clock value of the first transmitter.

2. A method as recited in claim 1, wherein the wireless receiver is part of a node of a wireless data network, and wherein the data unit containing synchronization information is a beacon.

3. A method as recited in claim 2, wherein the node is a station in an ad hoc network.

4. A method as recited in claim 2, wherein the node is a station in an infrastructure network.

5. A method as recited in claim 1, wherein the wireless receiver is part of a node of a wireless data network, and wherein the data unit containing synchronization information is a probe response.

6. A method as recited in claim 1, wherein the offset relates the known reference point in time to the location in the received first data unit of the extracted synchronization information.

7. A method as recited in claim 1, further comprising:

updating thereceiver'"'"'s local clock value from a second data unit containing synchronization information, the updating including;

receiving the second data unit containing synchronization information tranmitted by a second transmitter having a local clock value;

copying the local free-running clock at a second known reference point in time relative to the time the second data unit was received to update the local timestamp;

extracting the synchronization information from the received second data unit; and

re-calculating the offset to the free-running clock using the extracted synchronization information from the second data unit, the re-calculating in non real-time, the re-calculated offset relating the second known reference point to the location in the received second data unit of the extracted synchronization information and to the time the data unit was received, the re-calculating forming a re-calculated offset,

such that the receiver'"'"'s local clock value is approximately synchronized in time to the local clock value of the second transmitter.

8. A method as recited in claim 7, wherein the receiver is part of a station in an infrastructure network, wherein the extracted synchronization information from the received second data unit is a second received timestamp value, and wherein re-calculating the offset includes:

forming the re-calculated offset as the second received timestamp less the copied free running clock value and less the difference between the second known reference point in time and the location in the received second data unit of the extracted synchronization information.

9. A method as recited in claim 8, wherein the difference between the second known reference point and the location in the received second data unit of the extracted synchronization information is a function of the data rate.

10. A method as recited in claim 7, wherein the receiver is part of a station in an ad hoc network and wherein the updating is carried out only if the receiver'"'"'s local clock value lags the time using the re-calculated offset.

11. A method as recited in claim 10, further comprising:

the station canceling any outstanding beacon transmission;

wherein the re-calculating the offset includes;

forming the re-calculated offset as the second received timestamp value less the copied free running clock value and less the difference between the known reference point in time relative to the time the second data unit was received and the location in the received second data unit of the extracted synchronization information.

12. A clock synchronization method in a wireless node of a wireless network, the wireless node including a receiver, the method comprising:

generating an offset to the value of a free-running clock such that a local time reference determined as the sum of the value of the free-running clock and the generated offset is approximately synchronized to a previous timestamp in a previously received data unit containing a previous timestamp, the generating forming a determined offset; and

receiving a new data unit containing a new timestamp at the receiver;

extracting the new timestamp from the received new data unit containing the new timestamp;

updating the determined offset after the receipt of the new data unit using the extracted new timestamp and the value of the free-running clock at a known reference point in time relative to the time the new data unit was received.

13. A method as recited in claim 12, wherein the value of the free-running clock at the known reference point in time is obtained by taking a copy of the free-running clock at the known reference point in time.

14. A method as recited in claim 12, wherein the node is a station in an ad hoc wireless network.

15. A method as recited in claim 14, wherein the updating modifies the previously determined offset only if the local synchronized time lags the value the local time reference would have using the received new timestamp.

16. A method as recited in claim 15, wherein the local synchronized time is determined as the sum of the value of the free-running clock at the known reference point, the generated offset, and the difference in time between the known reference point and the point in time where the received timestamp is located.

17. A method as recited in claim 16, wherein the difference in time between the known reference point and the point in time where the received timestamp is located is a function of the data rate.

18. A method as recited in claim 15, wherein the updated offset is the received timestamp less the value of the free-running clock at the known reference point in time and less the difference in time between the known reference point and the point in time where the received timestamp is located.

19. A method as recited in claim 12, wherein the node is a station in an infrastructure wireless network containing an access point that periodically transmits data units containing timestamps.

20. A method as recited in claim 19, wherein the offset is re-calculated every time a data unit is received containing a timestamp transmitted from the access point of the station.

21. A method as recited in claim 20, wherein the local synchronized time is determined as the sum of the value of the free-running clock at the known time reference, the previously determined offset, and the difference in time between the known reference point and the point in time where the received timestamp is located.

22. A method as recited in claim 21, wherein the difference in time between the known reference point and the point in time where the received timestamp is located is a function of the data rate.

23. A method as recited in claim 20, wherein the offset is calculated as the difference of the received timestamp and the sum of the value of the free-running clock at the known reference point in time and the difference in time between the known reference point and the point in time where the received timestamp is located.

24. A method as recited in claim 12, wherein the accuracy of arithmetic used in the updating of the offset is at least 64-bits.

25. A method as recited in claim 12, wherein the data unit containing the timestamp is a beacon conforming to the IEEE 802.11 standard.

26. A method as recited in claim 12, wherein the data unit containing the timestamp is a probe response conforming to the IEEE 802.11 standard.

27. A method as recited in claim 12, wherein the node is a station in a wireless network, the node including a transmitter, the method further comprising:

determining a second offset to the value of the local free-running clock at a second known reference point in time relative to the time a data unit for transmission is to be transmitted;

copying the value of the local free-running clock at the second known reference point to form a second local timestamp;

forming a second timestamp using the second offset and the second local timestamp;

inserting the second timestamp into a second data unit; and

transmitting the second data unit at the time the data unit for transmission is to be transmitted.

28. A method of transmitting a data unit containing synchronization information from a wireless node of a wireless network, the wireless node including a transmitter, the method comprising:

determining an offset to the value of a local free-running clock at a known reference point in time relative to the time a data unit for transmission is to be transmitted;

generating a timestamp corresponding to the sum of the value of the local free-running clock at the known reference point and the determined offset;

inserting the generated timestamp into the data unit for transmission at a known point in the data unit; and

transmitting the data unit for transmission containing the inserted timestamp.

29. A method as recited in claim 28, wherein the wireless node is in an ad hoc network, and wherein the offset is a fixed value.

30. A method as recited in claim 28, wherein the wireless node includes a receiver to receive at least one data unit containing synchronization information, wherein the synchronization information in a received data unit is used to calculate an adjustment factor to the value of the free-running clock, and wherein determining the offset includes forming the sum of a previously determined adjustment factor and the difference between the known reference point in time relative to the time the data unit is transmitted and the location in the data unit of the inserted timestamp.

31. A method as recited in claim 30, wherein the difference is a function of the data rate.

32. A method as recited in claim 28, wherein the accuracy of arithmetic used in the determining of the offset is at least 64-bits.

33. An apparatus to synchronize a clock in a wireless receiver, the apparatus comprising:

a free-running clock;

means for receiving a first data unit containing synchronization information;

means for copying the free-running clock contents at a known reference point in time relative to the time the data unit was received to generate a local timestamp, the copying means coupled to the free-running clock;

means for extracting the synchronization information from the received first data unit to form an extracted timestamp, the extracting means coupled to the receiving means;

means for calculating an offset to the free-running clock using the extracted timestamp and the local timestamp, the calculating means coupled to the extracting means and the copying means,

such that the sum of the calculated offset and the value of the free-running clock provides a local clock value that is approximately synchronized in time.

34. An apparatus as recited in claim 33, wherein the calculating means is further for updating the offset after the receipt of a new data unit that includes new synchronization information, wherein the copying means is for copying the free-running clock contents at a new known reference point in time relative to the time the new data unit was received to generate a new local timestamp, wherein the extracting means is for extracting a new timestamp from the new data unit, and wherein the updating uses the extracted new timestamp and the new local timestamp.

35. An apparatus as recited in claim 34, wherein the receiver is part of a node of a wireless data network, and wherein the data unit containing synchronization information is a beacon.

36. An apparatus as recited in claim 34, wherein the apparatus is part of a station of an ad hoc wireless network.

37. An apparatus as recited in claim 36, wherein the updating modifies the previously determined offset only if the local clock value lags the value the local time would have using the received new timestamp.

38. An apparatus as recited in claim 37, wherein the local clock value is determined as the sum of the local timestamp, the calculated offset, and the difference in time between the known reference point and the point in time where the received synchronization information is located.

39. An apparatus as recited in claim 38, wherein the difference in time between the known reference point and the point in time where the received timestamp is located is a function of the data rate.

40. An apparatus as recited in claim 37, wherein the updated offset is the received timestamp less the local timestamp less the difference in time between the known reference point in time and the point in time where the received synchronization information is located.

41. An apparatus as recited in claim 34, wherein the node is a station in an infrastructure wireless network containing an access point that periodically transmits data units containing synchronization information.

42. An apparatus as recited in claim 41, wherein the offset is re-calculated every time a data unit is received containing a timestamp transmitted from the access point of the station.

43. An apparatus as recited in claim 42, wherein the local clock value is determined as the sum of the local timestamp, the previously determined offset, and the difference in time between the known reference point and the point in time where the received timestamp is located.

44. An apparatus as recited in claim 43, wherein the difference in time between the known reference point and the point in time where the received synchronization information is located is a function of the data rate.

45. An apparatus as recited in claim 42, wherein the offset is calculated to be the difference between the received timestamp and the sum of the local timestamp and the difference in time between the known reference point and the point in time where the synchronization information is located.

46. An apparatus as recited in claim 34, wherein the accuracy of arithmetic used in the updating of the offset is at least 64-bits.

47. An apparatus as recited in claim 35, wherein the received first and new data units containing the synchronization information are beacons conforming to the IEEE 802.11 standard.

48. An apparatus as recited in claim 34, wherein the data unit containing the timestamp is a probe response conforming to the IEEE 802.11 standard.

49. An apparatus as recited in claim 33,

wherein the apparatus is part of a node in a wireless network, and

wherein the means for copying also copies the value of the local free-running clock at a second known reference point in time relative to the time a data unit for transmission is to be transmitted to form a second local timestamp,

the apparatus further comprising:

means coupled to the free-running clock for determining a second offset to the value of the local free-running clock at the second known reference point;

means for forming a second timestamp using the second offset and the second local timestamp, the timestamp forming means coupled to the means for determining the second offset;

means coupled to the timestamp forming means for inserting the second timestamp into a second data unit; and

means coupled to the inserting means for transmitting the second data unit at the time the data unit for transmission is to be transmitted.

50. An apparatus for transmitting a data unit containing synchronization information from a wireless node of a wireless network, the wireless node including a transmitter, the apparatus comprising:

a local free-running clock;

means for copying the value of the free-running clock at a known reference point in time relative to the time a data unit for transmission is to be transmitted, the means for copying coupled to the local free-running clock, the copying providing a local timestamp;

means for generating a timestamp, the generating means including means for determining an offset to the local timestamp, the timestamp corresponding to the sum of the local timestamp and the determined offset, the generating means coupled to the copying means;

means for inserting the generated timestamp into the data unit for transmission at a known point in the data unit, the inserting means coupled to the timestamp generating means; and

means for transmitting the data unit for transmission containing the inserted timestamp, the transmitting means coupled to the timestamp insertion means.

51. An apparatus as recited in claim 50, wherein the wireless node is in an ad hoc network, and wherein the offset is a fixed value.

52. An apparatus as recited in claim 50, further comprising:

means for receiving at least one data unit containing synchronization information;

means for extracting the synchronization information from the received data unit; and

means for forming an adjustment factor to the value of the free-running clock,

wherein determining the adjustment factor includes forming the sum of a previously determined adjustment factor and the difference between the known reference point in time relative to the time the data unit is to be transmitted and the location in the data unit of the inserted timestamp.

53. An apparatus as recited in claim 52, wherein the difference is a function of the data rate.

54. An apparatus as recited in claim 50, wherein the accuracy of arithmetic used in the determining of the offset is at least 64-bits.

55. A MAC controller for a wireless node of a wireless network to operate according to a MAC protocol, the MAC protocol including periodic transmission in the network of a data unit that includes synchronization information, the MAC controller comprising:

a MAC administrator coupled to a data link layer interface;

receive hardware coupled to the physical layer interface and to the MAC administrator, the receive hardware being to receive one or more data units including a first data unit containing synchronization information and to provide the first received data unit to the MAC administrator; and

a free-running clock coupled to the receive hardware and to the MAC administrator to provide a copy of the free running clock value to the receive hardware and to the MAC administrator,

wherein the receive hardware accepts the value of the free running clock value at a known reference point in time relative to the time the first data unit was received to form a local timestamp and provides the local timestamp to the MAC administrator;

wherein the MAC administrator is to extract the synchronization information from the provided received first data unit to form an extracted timestamp, and to determine an offset to the free running clock value using the extracted timestamp and the local timestamp, such that the sum of the determined offset and the value of the free-running clock provides a local clock value that is approximately synchronized in time.

56. A MAC controller as recited in claim 55, wherein the MAC administrator includes a processing system including a processor and a memory, and wherein the processor determines the offset.

57. A MAC controller as recited in claim 55, wherein the receive hardware is further to receive and provide to the MAC administrator a new data unit containing new synchronization information, wherein the receive hardware further is to accept the value of the free running clock value at a new known reference point in time relative to the time the new data unit was received to form a new local timestamp and to provide the new local timestamp to the MAC administrator,

wherein the MAC administrator is further to extract a new timestamp from the new data unit, and to update the offset after the receipt of the new data unit using the extracted new timestamp and the new local timestamp such that the local clock value is monotonic in time.

58. A MAC controller as recited in claim 57, wherein the data unit containing synchronization information is a beacon.

59. A MAC controller as recited in claim 57, wherein the MAC protocol includes a time synchronization function requiring synchronized local time, and wherein the local clock value provides the local synchronized time.

60. A MAC controller as recited in claim 57, wherein the MAC controller is part of a station of an ad hoc wireless network.

61. A MAC controller as recited in claim 60, wherein the updating modifies the previously determined offset only if the local clock value lags the value the local time would have using the received new timestamp.

62. A MAC controller as recited in claim 61, wherein the local clock value is determined as the sum of the value of the local timestamp, the determined offset, and the difference in time between the known reference point and the point in time where the received synchronization information is located.

63. A MAC controller as recited in claim 62, wherein the difference in time between the known reference point and the point in time where the received timestamp is located is a function of the data rate.

64. A MAC controller as recited in claim 61, wherein the updated offset is the received timestamp less the local timestamp less the difference in time between the known reference point in time and the point in time where the received synchronization information is located.

65. A MAC controller as recited in claim 57, wherein the node is a station in an infrastructure wireless network containing an access point that periodically transmits data units containing synchronization information.

66. A MAC controller as recited in claim 65, wherein the MAC administrator re-calculated the offset every time a data unit is received containing synchronization information transmitted from the access point of the station.

67. A MAC controller as recited in claim 66, wherein the local clock value is determined as the sum of the local timestamp, the previously determined offset, and the difference in time between the known reference point and the point in time where the received synchronization information is located.

68. A MAC controller as recited in claim 67, wherein the difference in time between the known reference point and the point in time where the received synchronization information is located is a function of the data rate.

69. A MAC controller as recited in claim 66, wherein the MAC administrator determines the offset to be the difference between the received timestamp and the sum of the local timestamp and the difference in time between the known reference point and the point in time where the synchronization information is located.

70. A MAC controller as recited in claim 57, wherein the MAC administrator updates the offset using arithmetic with an accuracy of at least 64-bits.

71. A MAC controller as recited in claim 58, wherein the received first and new data units containing the synchronization information are beacons conforming to the IEEE 802.11 standard.

72. A MAC controller as recited in claim 57, wherein the first data unit containing the timestamp is a probe response conforming to the IEEE 802.11 standard.

73. A MAC controller as recited in claim 55, wherein the MAC administrator includes a processing system including a processor and a memory, the processor to implement the MAC administrator tasks by executing instructions loadable into the memory, and

wherein the memory is loadable with code to instruct the processor to extract the synchronization information from the provided received first data unit to form the extracted timestamp, and to determine the offset to the free running clock value using the extracted timestamp and the local timestamp.

74. A MAC controller as recited in claim 55, wherein the MAC controller is part of a station in a wireless network, the MAC controller further comprising:

transmit hardware coupled to the free-running clock and to the MAC administrator, and to the physical layer interface,

wherein the MAC administrator further is to determine a second offset to the value of the local free-running clock at a second known reference point in time relative to the time a data unit for transmission is to be transmitted, and to provide the second offset to the transmit hardware;

wherein the free-running clock is also to provide a copy of the free running clock value to the transmit hardware;

wherein the transmit hardware is

to accept a second data unit and the second offset from the MAC administrator and the value of the free-running clock at the second known reference point in time in order to form a second local timestamp,

to insert a second timestamp into the second data unit, the second timestamp value being the sum of the second offset and the second local timestamp, and

to cause the physical layer interface to transmit the second data unit containing the second timestamp, the transmitting being the time the data unit for transmission is to be transmitted.

75. A MAC controller for a wireless station of a wireless network to operate according to a MAC protocol, the MAC controller comprising:

a free-running clock;

a MAC administrator coupled to a data link layer interface; and

transmit hardware coupled to the physical layer interface, to the MAC administrator, and to the free-running clock, the transmit hardware to transmit one or more data units under control of the MAC administrator,

wherein the MAC administrator is to determine an offset to the value of the local free-running clock at a known reference point in time relative to the time a data unit for transmission is to be transmitted, and to provide the second offset and the data unit to the transmit hardware;

wherein the free-running clock is also to provide a copy of the free running clock value to the transmit hardware;

wherein the transmit hardware further is

to accept the second data unit and the second offset from the MAC administrator and to accept the value of the free-running clock at the second known reference point in time in order to form a second local timestamp,

to insert a second timestamp into the second data unit, the second timestamp value being the sum of the second offset and the second local timestamp, and

to cause the physical layer interface to transmit the second data unit containing the second timestamp, the transmitting being the time the data unit for transmission is to be transmitted.

76. A MAC controller as recited in claim 75, wherein the MAC administrator includes a processing system including a processor and a memory, the processor to implement the MAC administrator tasks by executing instructions loadable into the memory.

77. A MAC controller as recited in claim 75, wherein the determining of the offset by the MAC administrator includes the MAC administrator forming the sum of a previously determined offset and the difference between the known reference point in time relative to the time the data unit is to be transmitted and the location in the data unit of the inserted timestamp.

78. A carrier medium carrying computer readable code segments to instruct a processor of a processing system of a wireless station of a wireless data network to carry out a time synchronization method, the carrier medium comprising

(a) one or more code segments to instruct the processor to accept a first data unit from receive hardware, the first data unit received at the receive hardware and containing synchronization information;

(b) one or more code segments to instruct the processor to extract the synchronization information from the received first data unit; and

(c) one or more code segments to instruct the processor to determine an offset to the value of a free-running clock at a known reference point in time relative to the time the first data unit was received, the offset determining using the extracted synchronization information and the free running clock value at the known reference point, the calculating in non real-time,

such that the sum of the calculated offset and the value of the free-running clock provides a local clock value that is approximately synchronized in time and monotonic in time.