Month: July 2018

Clock synchronisation in systems communication

Motive

Starting with that, Guide to implementing a Clock synchronisation algorithm on low power wireless sensor networks.

following will be some pointers and papers to read before wandering in the wild to get things done and reinventing the wheel.

Literature survey

  • Message Time-stamping in Sensor Networks
  • Flooding time synchronisation protocol [1]
    • this protocol is very good in terms of single of time synchronisation
    • it uses linear regression, get ready to do some compute on your MCU
    • very good numbers and explanation in those slides [2]
    • Global Clock Skew
  • for multi-hop networks, this one is a good paper to read
  • Temperature Compensated Time Sync [4]
    • The only requirement on that time synchronization protocol is that it can calculate the current frequency error with respect to the reference node’s clock. Unlike other time synchronization protocols, TCTS also records the current temperature during a synchronization exchange. Both the temperature and frequency error at the end of the synchronization exchange is cached in a frequency vs. temperature table in memory. [5]
    • Before attempting subsequent resynchronization, TCTS will measure the current temperature and consults its internal calibration table. If the current frequency error for the measured temperature is cached, TCTS will not attempt to resynchronize with the reference node since a new time estimate is not required. Eventually, when all of the operating temperatures have been observed, TCTS will have auto-calibrated the low-stability clock, essentially providing a TCXO timebase. [5]

    • In addition, since we know that the curve should fit a quadratic function of the form

      fe(T) = −A · (T − T0)2 + B,

      where A is the temperature coefficient, T0 = 20◦C represents room temperature, and B is a frequency error offset, we can fit the measured calibration points to this curve and obtain frequency error estimates for previously unobserved temperatures, thus drastically improving the range and accuracy while eliminating a factory calibration step and allowing on-demand calibration. [5]

  • Virtual High-Resolution Time (VHT) [5]
    • basic idea behind VHT

        • During active periods, the high-frequency clock is turned on, and a hardware counter counts the number of high-frequency clock ticks that occur during each low-frequency clock interval, i.e., there are high-frequency clock ticks during each low-frequency one.

          φ0 = fL / fH

        • At the time of the event, the system records not only the value of the counter sourced by the low-frequency clock but also the value of the counter sourced by the high-frequency clock which was reset at the end of the most recent clock tick of the low-frequency clock. Thus, this second timer will indicate the phase φ within a low-frequency clock tick, allowing an effective resolution to be up-sampled to the high-frequency clock (modulo one cycle of jitter). The event time is sampled as

          tevent=CL ·φ0 +φ.

        • While the high-frequency clock is not phase-locked with the low-frequency clock, the phase error is limited to < 1/fH, and thus is of the same order as the quantization error.

Implementation of VHT in microcontrollers

The requirement is quite simple and the target chipset used in this project has additional two timers.

  1. 2 clocks driven by two oscillators
  2. 2 timers with capture and compare modes.

The Capture mode which will retrieve a timer value based on a signal event.

The Compare mode which will constantly monitor a timer counter value and compare it to a value set in the application. When they match, it will trigger an event.

The target implementation is on CC1350 chipset [6]. They have Four General-Purpose Timer Modules (Eight 16-Bit or Four 32-Bit Timers). With newest hardware revision CC1352r, almost same chip can be used to run Bluetooth 5.0. This has a M4 instead of a ARM M3 processor. This optimization with the increase in the memory footprint can be attributed to the new Bluetooth 5.0 standard.

The application framework used will be Contiki-OS [7]. I will use the latest version that is on development which also supports the SensorTag board and the launchpad [8]. A toolchain setup and compilation of the Contiki-OS is done in this post.

Illustration of the Virtual High-resolution Time event time-stamping mechanism on a micro- controller [5].

The two capture are connected to the event. The paper expects to make the interrupt for start of the frame delimited (SFD) which is previously justified for better resolution on clock synchronisation in figure 2 [5].

An additional capture unit on the fast timer captures the counter on every low frequency rising edge. As the Sync event, where the value of h0 is stored in one of the capture units. Later, when the SFD line rises, the two capture units on the two timers store l0 (the value of the low-frequency counter) and wh1 (the value of the high frequency counter), respectively. Using these three captured values, the event time can be calculated as

tevent=l0·φ0+(h1−h0) modφ0.

Counter overflows are an issue to be tackled. Overflows of the high-frequency counter are not a problem since they run only on a short burst when the system is synchronising / listening for packet. The low-frequency clock must have a counter width of 64-bit since 32-bit counters will overflow by 5 minutes since the low-frequency counters are used for long intervals.

As per the suggestion on [5] a 32KHz and 8MHz clocks are used for the timers. The MCU has Clock Speed up to 48-MHz.

References:

[1] http://www.isis.vanderbilt.edu/sites/default/files/Maroti_M_11_3_2004_The_Floodi.pdf

[2] https://www.tik.ee.ethz.ch/file/5562ed988ca095af8331114dd81c6c70/sensys09_slides.pdf

[3] https://people.mpi-inf.mpg.de/~clenzen/pubs/LSW09optimal.pdf

[4] https://ieeexplore.ieee.org/document/5170185/

[5] https://web.eecs.umich.edu/~prabal/pubs/papers/schmid10vht.pdf

[6] http://www.ti.com/lit/ds/symlink/cc1350.pdf

[7] http://contiki-ng.org/

[8] https://github.com/contiki-ng/contiki-ng/wiki/Platform-srf06-cc26xx

 

decentralized and distributed systems

Pointers for distributed vs decentralised:

Some bookmarks to read if you are a distributed systems researcher [1]

  • A decentralized system is a subset of a distributed system.
  • The primary difference is how/where the “decision” is made and how the information is shared throughout the control nodes in the system.
  • Decentralized means that there is no single point where the decision is made.
  • Every node makes a decision for it’s own behaviour and the resulting system behaviour is the aggregate response.
  • A key characteristic of decentral systems is that typically no single node will have complete system information.
  • “Distributed means that the processing is shared across multiple nodes, but the decisions may still be centralized and use complete system knowledge” says coinbase in their blog post
  • A scenario to think of:
    • Some control algorithms I’ve seen for multiple quad-copter control are purely distributed in that a central over-seer gives optimization problems to each copter to solve then return the solution.
    • The over-seer will then issue commands based on the aggregate result.
  • Here’s a philosophical question:
    • if the over-seer is “voted” into office by the nodes, is it decentralized or centralized?
    • I’d have to say decentralized, but it is arguable says MaRi Eagar
    • then I tend to ask what is distributed systems?

Keywords that matter

when you start the debate (here central systems are included): [2]

  • Points of Failure / Maintenance
  • Fault Tolerance / Stability
  • Scalability / Max Population
  • Ease of development / Creation
  • Evolution / Diversity

References:

  1. What is the difference between decentralized and distributed systems?
  2. Centralized vs Decentralized vs Distributed