Clock synchronization in a distributed system

• US 20050013394A1
• Filed: 07/24/2002
• Published: 01/20/2005
• Est. Priority Date: 07/26/2001
• Status: Active Grant

• Current Assignee: BMW AG (Bayerische Motoren Werke AG), DaimlerChrysler AG (Mercedes-Benz Group AG), Freescale Semiconductor, Inc. (NXP Semiconductors NV), Robert Bosch GmbH
• Original Assignee: Freescale Semiconductor, Inc. (NXP Semiconductors NV)
• Inventors: Schedl, Anton, Muller, Bernd, Hedenetz, Bernd, Rausch, Mathias
• Granted Patent: US 7,349,512 B2
• Time in Patent Office: Days
• US Class Current: 375/356
• CPC Class Codes: G04G 7/00 Synchronisation radio-controlled time-pieces G04R
• CPC Class Codes: G06F 1/14 Time supervision arrangements, e.g. real time clock
• CPC Class Codes: H04J 3/0652 Synchronisation among time division multiple access [TDMA] nodes, e.g. time triggered protocol [TTP] bus network with centralized control in which slots are of a TDMA packet structure H04L12/4035
• CPC Class Codes: H04J 3/0676 Mutual

Abstract

The present invention provides an improved clock synchronization algorithm for a distributed system intended for real time applications by performing at the same time an off-set correction and a clock read correction at each node of the distributed system. Expensive oscillators can be avoided and synchronization can be established faster and with higher precision.

Claims

1. A method for synchronizing nodes (1) of a distributed system for real time applications, the nodes (1) of the distributed system are interconnected by a communication link (3) and each of the nodes (1) includes a local clock (2) and information indicating when messages are to be received from other nodes (1), each node (1) from at least a subset of all nodes (1) performs the following steps for synchronizing its local clock (2):

(a) receiving messages from other nodes (1),

(b) determining a set of time deviations between its own local clock (2) and all other nodes (1) of the subset of nodes (1), a time deviation being determined by measuring the difference between an expected receiving time of a received message and an actual receiving time observed based on the time of its own local clock (2),

(c) determining a set of clock rate deviations between its own local clock (2) and all other nodes (1) of the subset of nodes (1) based on two subsequently received messages from each of the other nodes (1) of the subset,

(d) calculating an off-set correction value based on said determined set of time deviations and calculating a clock rate correction value based on said set of determined clock rate deviations, and

(e) adjusting the local clock (2) based on the calculated off set correction value and said calculated clock rate correction value.

2. A method according to claim 1 wherein

said first determining step (b) determines a first and a second set of time deviations, and said second determining step (c) calculates said set of clock rate deviations by calculating differences between corresponding time deviations of said first and second set of determined time deviations.

3. A method according to claim 2 wherein said calculation step (d) calculates an off-set correction value based on said second set of determined time deviations.

4. A method according to claim 1 wherein said second determining step (c) determines a clock rate deviation by measuring the difference between an expected time interval and an observed time interval, said expected time interval being a time interval between expected receiving times of subsequently received messages of a particular node and said observed time interval being a time interval between the actual receiving times of the messages observed based on the time of its own local clock (2).

5. A method according to claim 4 wherein said second determining step (c) determines each clock rate deviation of said set of clock rate deviations by performing the steps of (cl) counting a time interval between actual receiving times of subsequently received messages for a particular node (1) of the subset of nodes (1) based on the time of its own local clock (2), and (c2) calculating a clock rate difference between the counted time interval for the particular node (1) and an expected time interval based on the expected receiving times of the messages for the particular node (1).

6. A method according to claim 1 wherein said distributed system is a time triggered system.

7. A method according to claim 1 wherein said information included in the node'"'"' (1) defines for every node (1) of the distributedsystem certain time slots in which a particular node. (1) is allowed to send messages on said communication link (3).

8. A method according to claim 1 wherein said information included in the nodes (1) defines access for every node (1) to said communication link (3) once within a predefined time interval.

9. A method according to claim 8 wherein a time interval having the same predefined temporal access pattern for the nodes (1) of the distributed system to the communication link (3) is continuously repeated.

10. A method according to claim 8 wherein each of the nodes (1) transmits own messages when having access to said communication link (3) according to said predefined access pattern.

11. A method according to claim 1 wherein said calculating step (d) calculates said clock rate correction value based on two clock rate deviations of said set of determined clock rate deviations according to a first predetermined rule.

12. A method according to claim 11, wherein said first predetermined rule selects two clock rate deviations which have the largest difference with respect to each other.

13. A method according to claim 11 wherein said first predetermined rule excludes clock rate deviations according to a second predetermined rule.

14. A method according to claim 1 wherein said calculating step (d) calculates said clock rate correction value by incrementing the clock rate correction value applied during the previous adjusting step with the currently calculated clock rate correction value.

15. A method according to claim 1 further comprising a step of changing the clock rate correction value provided by said calculating step (d) according to a third predetermined rule.

16. A method according to claim 15 wherein said third predetermined rule replacing said calculated clock rate correction value by a value having a slightly reduced amount.

17. A method according to claim 1 wherein said adjusting step (e) for adjusting the local clock (2) based on the calculated clock rate correction value and the calculated off-set correction value is performed for both correction values after a predetermined number of time intervals each of which defining access for every node to said communication link (2) once per time interval.

18. A computer program comprising code means adapted to perform the method according to claim 1.

19. A synchronizing unit for synchronizing a node (1) in a distributed system for real time applications, the nodes (1) in the distributed system are interconnected by a communication link (3), the synchronizing unit comprises:

a local clock (2),

a memory (6) for storing information indicating when messages are to be received from particular nodes (1),

a deviation detector for determining a set of time deviations between its own local clock (2) and other nodes (1), a time deviation being determined by measuring the difference between an expected receiving time of a received message and the receiving time observed based on the time of its own local clock (2), and for determining a set of clock rate deviations between its own local clock (2) and other nodes (1) based on two subsequently received messages for a node (1),

a correction calculation unit for calculating an off-set correction value based on said determined set of time deviations and for calculating a clock rate correction value based on said determined set of clock rate deviations, and

an adjusting unit for adjusting the local clock based on the calculated offset correction value and on the calculated clock rate correction value.

20. A synchronizing unit according to claim 19 wherein said deviation detector being adapted to determine a first and a second set of time deviations and to determine said set of clock rate deviations by calculating differences between corresponding time deviations of said first and second set of time deviations.

21. A synchronizing unit according to claim 20 wherein said correction calculation unit calculates an off-set correction value based on said second set of determined time deviations.

22. A synchronizing unit according to claim 19 wherein said deviation detector being adapted to determine a clock rate deviation by measuring the difference between an expected time interval and an observed time interval, said expected time interval being a time interval between expected receiving times of subsequently received messages of a particular node and said observed time interval being a time interval between the actual receiving times of the messages observed based on the time of its own local clock (2).

23. A synchronizing unit according to claim 22 wherein said deviation detector comprises a counter for counting a time interval between actual receiving times of subsequently received messages for a particular node (1) based on the time of its own local clock (2).

24. A synchronizing unit according to claim 19 wherein said memory (6) storing information defining for every node (1) of the distributed system a certain temporal access pattern allowing a particular node (1) to send messages on said communication link (3).

25. A synchronizing unit according to claim 19 wherein said information included in the nodes (1) defines access for every node (1) to said communication link (3) once within a predefined time interval.

26. A synchronizing unit according to claim 19 wherein each node further comprises a transmitter for transmitting own messages when having access to said communication link (3) according to said predefined access pattern.

27. A synchronizing unit according to claim 19 further comprising a deviation memory for storing time deviations determined between the local clock (2) and the clocks (2) of other nodes (1).

28. A synchronizing unit according to claim 27 wherein said memory being adapted to store two sets of time deviations.

29. A synchronizing unit according to claim 19 further comprising a drift protection means for changing the clock rate correction value provided by said correction calculating unit and forwarding a changed clock rate correction value to said adjusting unit