Synchronization

Owned by Thomas Watteyne
Last updated: Mar 08, 2013 by Branko KerkezVersion comment

A new mote joins (or synchronizes) to the network by:

  • aligning its slot boundary to the slot boundary of the of other motes in the network. We call this slot synchronization.
  • using the same ASN value as the other motes in the network. We call this ASN synchronization.

Install GoLogic2

The discussion on this page is illustrated by screen captures of the Gologic 2 software with comes with NCI's GoLogic logic analyzer. Throughout this discussion, we provide links to GoLogic traces. We recommend you install Gologic 2 in "demo mode" so you can manipulate the trace by yourself.

  • Refer to TschEnvironment for installation instructions.
  • Refer to TschTraces for a discussion of how these traces were acquired.

Slot Synchronization

All nodes which implement IEEE802.15.4e run a timer which fires at (and defines) the beginning every slot. How to setup this timer is discussed in TschTimer. The length of the timer is discussed in TschTiming#TsSlotDuration.

The screenshot below shows the mote's timer firing every 10ms.

(source file at before_connected.prj)

The only convention to enable synchronization is that every packet is sent exactly TsTxOffset ms after the beginning of the slot. That is, the start-of-frame delimiter of the packet needs to leave the radio at that time.

The image below shows the ADV slot. TsTxOffset is measured between the beginning of the slot and the time the receiver gets the start of frame event from the radio.

(source file at nine_slots_final.prj)

For every packet, the receiver timestamps the reception of the SFD. If this receiver were perfectly synchronized, that timestamp would be TsTxOffset. However, if it got desynchronized, that timestamp will be less or more than TsTxOffset.

Resynchronization always consists in the slave aligning the boundary of its next slot to the same boundary on the master.

The time master is that mote in the network which never synchronizes to any other mote. All other motes in the network synchronize to it. Yet, communication is independent and a packet can go from the master to slave, or from the slave to the master:

  • Packet-based synchronization is used when the master sends a packet to the slave;
  • ACK-based synchronization is used when the slave sends a packet to the master;

The implication here is that, even though the time relationship between nodes in the network can be described for example by a tree, the communication scheme resides in a totally independent and rather general graph. We shall see in the Multi-Hop section on this page the common practices.

Packet-based Synchronization

A simple case where the master sends a data packet to the child is depicted below:

Here, the child expected the packet TsTxOffset into the slot, but received it correction later. To ensure that its next slot is perfectly aligned, it temporarily increases the size of the current slot to TsSlotDuration+correction. When the next slot starts, it sets the slot duration back to TsSlotDuration.

The counterpart is also true:

Here, the child receives the packet early. In this case, it temporarily decreases the size of the current slot.

ACK-based Synchronization

In many cases, most of the packets go from the slave to the master and the master rarely sends a packet to the slave. The technique to synchronize is still the same, but it's now the master which measures the time correction. IEEE802.15.4e defines a new format for the acknowledgement, which now contains space for the master to indicate the correction to the child.

In the following figure, the master receives the data early. In indicates the correction value in its ACK. After receiving the ACK, the slave temporarily increases its current slot length by correction.

Finally, in the following figure, the master receives the data late. It indicates the correction value in its ACK. After receiving the ACK, the slave temporarily decreases its current slot length by correction.

In Practice

In practice, every mote measures correction whenever it receives a data packet, and writes that value in the ACK. Then, if the child is the sender, it uses ack-based synchronization; however, if it is the receiver, it uses packet-based synchronization. In the latter case, the correction field in the ACK is unused.

Clock drift

The clock driving the timer should be the most stable clock source on the board (see TschTimer), which is often a 32kHz crystal. But even the best clocks have some drift. Manufacturing conditions or temperature a difference can cause crystals to beat at slightly different frequency. The amount of discrepancy in frequency is called clock drift. Good 32kHz crystals have a clock drift of 10 ppm (parts-per-million).

Against a perfectly stable clock source, if the crystal is 10ppm slow/fast, it "loses"/"gains" 10sec every million seconds, or 10used every second. To measure the relative drift between two motes, you can have them toggle a pin at regular intervals and observe the edges on a scope (when no communication or synchronization is taking place). If you zoom in enough, you'll see the edge drift one against the other, as shown in the following video:

Here, the upper edge moves at about 1us per second, which corresponds to a 10ppm relative drift. If you put one mote in an oven, and the other in a fridge, then drift becomes several times that value.

In practice, motes need to resynchronize every now-and-then to compensate for that drift. The video below shows this happening:

Guard Time

The Timeslot template indicate that we are using a guard time of 1ms. That is, the receiver starts listening for a packet 1ms before its supposed to (TsTxOffset) and keeps listening for 1ms after. This means that the sender can transmit up to 1ms late or early.

The figure below shows a slot where mote 1 is listening, but mote 2 is not sending. Mote 1 starts listening 1ms into the slot, then listens for 2*1ms, and goes back to sleep since nothing is received.

(source file at nine_slots_final.prj)

The guard time indicates how often one needs to resynchronize. At 10ppm, it takes 100s for mote to desynchronize by 1ms. With a security factor of 3, this means that motes need to resynchronize every 30s.

Clock drift, guard time and resynchronization periods are linked. A smaller clock drift allows the guard time to be smaller, or the resynchronization period to be larger. A shorter guard time means that motes need to resynchronize more frequently, etc.

Keep alive

As per the calculation above, master and slave need to communicate at least every 30s to keep synchronized. If they are exchanging data more frequently than that, synchronization is kept "for free". If that is not the case, the slave has to send an data packet with an empty payload just to receive the ACK to resynchronize. These packets are called keep-alive packets. Handling those packets is done exactly the same way as real data packets. However, since the payload is empty, the packet is simply not handed to the higher layer.

Multi-hop

So far, we've considered only star networks with slave motes talking directly to the time master mode. In a multi-hop scenario, each mote indicates in its neighbor table which of its neighbor is its time parent. It synchronizes only to that neighbor; i.e. if it received packets from a different neighbor, it handles the data, but does not use it to resynchronize.

The idea is that the parent-child relationship forms a DAG (Directed Acyclic Graph) in the network, rooted at the time master. In practice, the time master is often also the DAGroot (in RPL parlance), and so a mote's preferred parent (as identified by RPL) is also its time parent.

ASN Synchronization

All nodes in the network share the same ASN (Absolute Slot Number). When the manager starts the network, it sets ASN to zero. From then on, ASN increments by 1 in each slot, thus coarsely keeping track of absolute time. Once a mote is synchronized to a network, it sets its ASN to the network's ASN, thus allowing for every mote in the network to share the same sense of absolute time. Through advertisement packets, the current (5-byte) ASN is shared. Once a node has joined, it can in theory stop listening for ADV packets and use keep-alive packets to stay synchronized.

With a 10ms slot, the ASN loops every 350 years.