Clocks

Some time geeks (should I say Time Lords) checked out my clocks.

Seems they are impressed, saying sub microsecond.

I have spent all day trying to improve on that, and I think I have.

The issues are several - the PPS interrupt that captures the time signal works well, but can randomly have extra latency. The original signal can have jitter, drift, and ever sawtooth (actually have not seen this).

What I did not realise is that there is also noticeable clock drift on the processor, probably temperature related.

I previously assumed clean "on the second" PPS. I have changed it so that is used as a reference on longer term (moving average 5 mins) for frequency, and shorter term phase offset tweaks.

This means my per second reference CPU cycle counts change by 1 at a time as things change, the main change being clock frequency drift. This result is reference ticks varying by 4ns or less.

I need to get the Time Lords to check my latest code and see what they find.

Tick Tock

I am pleased to say that my new time servers are in the UK NTP pool now.

Dave has done a nice report on how well they are performing, here.

And this is actually on an ADSL line...

(available from my shop obviously)

Time for something new...

Latest project is a time server.

So why? Well, they exist - you can buy a really nice LeoNTP server, with impressive specs. We see response times of 0.1ms, and it claims 100,000 requests a second. They also have a PPS output, and can do a calibrated 10MHz output apparently (I can't do that).

Can I get close using an ESP32? Well, sort of.

Challenges

It should be simple, in theory - a GPS module, capture CPU cycle count on PPS interrupt and use to get clock rate. Capture NMEA to get time for PPS. Capture cycle count on NTP packet and use reference cycle count, clock rate, and reference time to know exact time of day to fill in NTP reply. yay!

Of course it is never entirely that simple. I did all this and got a working system, but I could do better. My latency as measured on a FireBrick was 2.5ms. I did averaging of the PPS intervals to get a more consistent clock rate, and often the standard deviation on that was below 10ns! But not always. I then did a best of last 5 seconds in terms of a PPS interval to use as a reference - that way the odd delayed interrupt had no impact. That seems to work.

One thing I wanted was PPS interrupt at higher priority than Ethernet, but all GPIOs on an ESP32 are the same interrupt source. Bugger. Do a search and you see plenty of people pissed off about this. I found a fix, make the PPS a PCNT (Pulse count) which has an interrupt (count to 1) which can be set separately to the Ethernet interrupt. There is a trick to remember.

The hardware

The PCB design is not that hard now I have cracked Ethernet. A main PCB, with USB-C, DC input, PoE, and Ethernet.

I have since made an even more compact design.

This then connects to a GPS module, which you can hang out the window (or better, fit in a Stevenson screen). Link with 5 core cable (solid cat5 is ideal), and it can handle a few metres.

Then put both in a nice 3D printed case. See https://shop.revk.uk/ if you want to buy. £60 not £600!

Making it faster

The fact my response times where around 2.5ms was not ideal. I wanted better, but how.

First bodge was hook in to the Ethernet driver receive code and check for NTP packets as they come in, and do a direct reply. I got latency down to 1ms, yay!

But I can do better :-)

Scrap the Ethernet controller altogether. Write my own custom low latency driver. Dedicate CPU1 to PPS and Ethernet only. My custom driver can...

• Be reactive only - reply immediately to ARP, ND, and NTP.
• Being reactive, no need for mutex wrap on access to Ethernet chip.
• Work in interrupt (yes, nasty, but dedicated CPU) so not task switching.
• Know state of registers to avoid read-modify-write as used a lot in standard driver code.
• Do read fifo and write fifo with no clean-up between

And guess what - latency down to 0.1ms - bang on what I wanted. Indeed I have seen 0.077ms even.

Now, the logic is fun - it makes the Ethernet no use for anything but NTP. So I have made it (a) optional, and (b) normal Ethernet for first 2 mins so you can access it via Ethernet if needed (assuming you can control power/PoE to reset).

But once switched to low latency NTP only Ethernet, you have to use the WiFi for any access, management, MQTT, and so on.

Bugs

I found bugs in the Ethernet chip (KSZ8851SNL) which does not check IPv6 UDP checksums correctly!

I also found it almost impossible to convince the Ethernet chip to give me unicast, multicast, and broadcast packets - in spite of a lot of reading the data sheet and trial and error. It is now in promiscuous and relying on the switch to protect it. Even that makes no sense - you have to set "Allow any packet" and "Invert the input filter" which to mean means "allow no packets!". I may yet find a working setting. I have already spent a day on this.

I also found it used edge triggered interrupt with a check in task for ISR set as well on timer, I changed to level triggered and that seems to work without hanging.

I also found it nearly impossible to cleanly decommission the Ethernet driver in ESP IDF. I managed to take over interrupts and kill the task, and that was all. Anything more thorough was a nightmare. But that works.

What is it good for?

Well some people are putting in the UK NTP pool, it seems to meet the requirements well and work at a level similar to the rest of the pool.

But it is mainly aimed as being the main server in any business / office. Include with your pool NTP, but being local it will win.

I do not get close to even 10,000 requests a second, more like 5,000, but that is not needed for a typical business, even a large one.

Finding a postcode

My GPS logger is going well (available here) and it logs journeys when back on home WiFi.

One of the requirements that someone requested was to list postcodes visited. I think it was a district nurse, and they need this for expense claims.

So, not a hard task, surely, making it find postcode where you are...

Postcodes are odd shapes

Sadly postcodes are not simple, and odd shapes, but the best I could easily do is find nearest postcode based on the centre for each postcode, which is published free by Ordnance Survey.

Notably the Dutch government does the same but with a bounding box which may help identify when there is ambiguity.

Microcontroller

The challenge is that this is a small micro controller. I cannot just "install mysql". I need a way to look up postcodes and finding the nearest. I cannot sensibly scan 1.7 million UK postcodes each time I want to log a postcode.

The "trick" is simple, make a grid. I picked 1km squares on the OSGB E/N grid. So not quite 1km but close enough. More on that later. That meant I could make a grid for the whole UK, and for each grid square I can make a list of possible postcodes with there centre.

That was simple enough, well, except...

Converting lat/lon to OSGB

First issue is, on device, converting GPS lat/lon to E/N OSGB. There are simple algorithms for this, I have seen them, but some are way off, and ultimately the "official" way to do it is make a guess and check a huge look up table of surveyed points (I think each 10km).

I did not want to do this on device, so my solution is convert the postcode list to lat/lon. This runs on linux and can use the official look up table, but gives me a postcode database which uses lat/lon.

Searching one cell

The next step was a simplification for search. I make each grid square (now based on lat/lon) have a list of postcodes with centre location to find the closest.

The problem is that, at the edge of a square, the closest may be in the next square. So I scan the edges of the squares, binary dividing to find all "near" postcodes for all points along it, whether in the target square or not. I then have all that are in the target square.

This means for each square I have a list of all postcodes that could be the closest postcode for any point in the square. This means some duplication from square to square but makes the lookup simple.

The whole lots ends up in one file. Look up the grid to find the list of postcodes, and scan the list for the closest. Simple.

Distance of point to line in four dimensions (or more)

Why?

I'm writing the blog because searching has not helped me on this. Why do I need to know? well the answer is I am applying a Ramer–Douglas–Peucker algorithm to GPS tracking data.

You can look it up, but it is pretty simple to explain. Imagine you have a set of points starting from A and going to B - in my case it is GPS log data, so points on a map, every second, so lots of points. You want to reduce how many points you have without losing significant information.

Ideally all the intermediate points are on a straight line A to B, and can all be removed leaving just A and B. I practice you allow a tolerance, an allowable deviation from the line. If all of the intermediate points are within that tolerance you can delete them all. If not, you find the most deviant point, call it C. C is effectively a corner point. You apply the algorithm on A to C and C to B recursively.

In the end you have a set of points, which could just be A and B, or A, C, and B, or more. If you join the dots with straight lines you can be sure all of the removed points lay within your tolerance of that line, and so be sure any detail, that is more than the tolerance allowed, has not been missed.

I use this years ago on GPS data.

Before

After

Point to line

The crux of the algorithm is working our the deviation from the line, what wikipedia helpfully just refers to as perpendicularDistance().

Two dimensions

In two dimensions this is simple, and searching finds an algorithm. I used this on latitude and longitude. But this causes problems.

• Latitude and longitude are not a flat plane. This is not likely to be a real issue unless tracking a plane (pun intended) or a ship over a long distance.
• Latitude and longitude are in degrees not metres, so working out your distance is not easy. A degree North is not the same distance as a degree West and changes depending one where you are. You need trigonometry to compensate and convert to distance units.

Three dimensions

Of course, we also have altitude, and so seems sensible to include that - why not. Algorithms for a point to a line in 3D are also easy to find, but there seem to be several different approaches. At least altitude is already in metres.

However, the GPS can provide not just lat/lon/alt, but also ECEF data. This is simple Cartesian X/Y/Z co-ordinates from centre of the Earth. This avoids any need to adjust from degrees, and makes it simple.

Four dimensions

I have to push it one step further, don't I? If you travel in a straight line, but stop for a while, you would remove all points. By including time as a 4th dimension we create a corner when speed changes notably or you stop for a while.

It does mean you have to scale time to a distance, but that can be a simple parameter in the algorithm.

However, there is a snag - finding an algorithm for point to line in four dimensions is not simple. The only ones I could find explain it in vector maths - and even with an A in A-level maths, it was a long time ago and I really did not get on with vector maths. Nobody seems to give me a simple algebraic answer which is driving me mad.

Making it simple

So, back to basics, I am interested in three points, and regardless of how many dimensions that is, they can be said to lie on a flat two dimensional plane. This means working out the deviation is a simple matter of considering a triangle.

So I want to find h. To do this I need distances a, b, and c. But that is easy to find as it is simple Pythagoras, regardless of how many dimensions. For two dimensions it is √((Ax-Bx)²+(Ay-By)²). For three dimensions it is √((Ax-Bx)²+(Ay-By)²+(Az-Bz)²), and so on.

Knowing a, b, and c I can use Heron's formula to find area...

• s = ½(a+b+c)
• 𝔸 = √(s(s-a)(s-b)(s-c))

Then use the formula for area from base and height

• 𝔸 = ½hb
• h = 2𝔸/b
• h = 2√(s(s-a)(s-b)(s-c))/b

So it can be done with any number of dimensions.

Faster

One of the considerations is performance when coding for a microcontroller. They can do integer add/subtract very fast, multiply reasonably fast, division slower, and floating point even slower. As it happens the ESP32 has hardware single precision floating point, which helps.

So can I simplify this?

Thankfully wikipedia helpfully expands Heron's formula to:

• 𝔸 = ¼√(4a²b²-(a²+b²-c²)²)

Which gives us:

• h = 2(¼√(4a²b²-(a²+b²-c²)²)/b)
• h = ½√(4a²b²-(a²+b²-c²)²)/b
• h² = (4a²b²-(a²+b²-c²)²)/4b²

Working our h² is useful as ultimately I am just comparing this distance so no need to apply a square root. I can square my reference threshold.

Why is this helpful? Well, all of the parameters are a², b², and c². This means that I don't need to use a square root to work out a, b, and c in the first place. The whole lot is simple addition, subtraction, multiplication, and just one division.

Turning back

There is another problem with all of the perpendicular distance algorithms, including this one. The all work out a distance of a point to an infinite line which is defined as going through two points.

In this case point C is way off the line A-B, in fact it is c off it, but h is small. If h is within the tolerance  then it would be removed leaving only A-B.

To solve this I can use the fact that if c²-b² is > a² the C must be beyond A and I should use a² as the distance².

Similarly if a²-b² > c² then C is beyond B, meaning I should use c² as the distance².

Fortunately I have a², b², and c² already, so is a simple test.

Of course, what if you have a straight line A-B-C-D and travel A-B-C-B-C-D? No points will be "outside" the A-D range... Well the use of time as a 4th dimension catches that - which means the first case would also have been caught... Even so, this simple test on end points is worth doing I think.

C what I mean...

   inline float dist2 (fix_t * A, fix_t * B)

   {

      float X = x (A) - x (B);

      float Y = y (A) - y (B);

      float Z = z (A) - z (B);

      float T = t (A) - t (B);

      return X * X + Y * Y + Z * Z + T * T;

   }

   float b2 = dist2 (A, B);

   fix_t *m = NULL;

   float best = 0;

   for (fix_t * C = A->next; C && C != B; C = C->next)

   {

      float h2 = 0;

      float a2 = dist2 (A, C);

      if (b2 == 0)

         h2 = a2;               // A/B same, so distance from A

      else

      {

         float c2 = dist2 (B, C);

         if (c2 - b2 >= a2)

            h2 = a2;            // Off end of A

         else if (a2 - b2 >= c2)

            h2 = c2;            // Off end of B

         else

            h2 = (4 * a2 * b2 - (a2 + b2 - c2) * (a2 + b2 - c2)) / (b2 * 4);

      }

      if (m && h2 <= best)

         continue;

      best = h2;

      m = C;

   }

More fun with GPS...

The NMEA sentences from a GPS work on degrees, minutes and fractions. As a format they are horrid - the sign is a separate character N/S, E/W, and the value is fixed length so DDMM.mmmm and DDDMM.mmmm format.

The 4 places for minutes is not that precise, but more than enough for absolute GPS positioning.

But there is an alternative, and it is like the IPv6 of GPS. More precision that you could ever want - ECEF format is X/Y/Z in metres from centre of the Earth to the micrometer!!!

$ECEFPOSVEL,124015.000,3985352.629186,-54462.755461,4962832.255023,-0.008022,0.003776,0.022063

Amazing. So whilst not adding absolute accuracy, it does add some impressive relative precision.

Walking in the road to spell my name, LOL.

GPS trackers

I am playing around with GPS trackers (I'll post more on hardware for this later). This is for commercial vehicles, not anything covert, and I am not going to even touch on GDPR in this post :-)

Reducing the number of points

One of the challenges is managing how often we sample location, and if/how we reduce the number of points. There are a number of reasons to do this:-

Local Storage

One reason to reduce the number of points stored is where the tracker is storing the points - either for download later or for transmission when mobile coverage comes back, etc. The local storage of a small embedded device is likely to be limited. The GPS module I am using has several ways to do this (I have yet to work out how to do other than simple interval). Storing every second, which it will happily do, runs out of space in a few hours.

Transmission

Transmitting the data over a mobile network has costs. Yes, there are SIM packages with unlimited data, but if you have a fleet of hundreds of vehicles you can do better than each of them on a package for tens of pounds a month and unlimited data. There are packages with much lower monthly costs but data usage costs, and there are foreign SIM packages with roaming for better coverage and higher data costs. Reducing the data transmission can get the costs down to pence a month. This means not only reducing the number of points but finding ways to reduce the overhead of transmission of the data itself.

My plan is to pack data in to an encrypted UDP packet, with a simple resend packet sent back if the data has not arrived at the expected time. I.e. an entirely NAK based protocol so that normally it is one packet in one direction, probably every 10 minutes or so. This means really low mobile data usage.

Database storage

Reducing the number of points also helps with back-end storage. Hundreds of vehicles tracked every second means a lot of data. Simply increasing the interval loses useful data so you ideally need a smarter way to reduce the data.

Display

Perhaps a small point, with computers and networks being so fast, but reducing the number of points sent to a browser to display a route can make things much more responsive.

Where to reduce points

At present I have code to reduce the points when pulling from a database and sending to a browser, with an option to also delete the removed points from the database. But ideally you want to do this in the tracker itself - that way you have all of the benefits for local storage and transmission as well.

This also creates an extra advantage - if you have a means to reduce data points effectively you can start by collecting much more data in the tracker. The GPS modules I am using can do 1/10 second fixes, so why not start with this, and reduce points from there.

How to reduce points

I pondered how to do this, and came upon with something based on removing points within a certain distance. I then found there is a standard algorithm which is basically very similar to what I came up with. The Ramer Douglas Peucker algorithm.

It recursively takes a set of points. If all intermediate points are within a specified margin of the straight line between start and end, then those intermediate points are removed. If not, the one furthest away is kept and the point from start to this, and from this to end, are recursively processed. The end result is a path of straight lines where all the removed points must have been within the specified margin of that line.

This works well, and removes points on long straight roads but keeps points driving around a roundabout!

Even setting a margin as small as 1m massively reduces the number of points, and what is even better is that you can start with say 10 times as many points (e.g. 1/10 second fixes) and still end up with similar final number - just that the points you select are more precise (i.e. the exact edge of a turn, not just nearest second).

Of course I won't have a full set of points in the tracker, I'll have to work on time periods, like 10 minutes, collect data, and then apply the algorithm. This means there will be points based purely on time as the end points for the chunks of data I process.

Distances

One issue is that the raw data is lat/lon and not ground distances. There are ways to work out exact ground distances around the curved surface of the Earth, but a simpler way is to just assume we can map lat/lon on to a flat plane. What I do is, for each stage of the algorithm, take all lat/lon relative to the middle, and convert to metres. For latitude this is simply multiple my 111111 (yes, apparently this comes from French definition of a metre). For longitude it is 111111*cos(lat), remembering to convert to radians for cos(). This means I can then work out distance from a line in metres with minimal error. Of course as the algorithm recurses and processes smaller line segments, the error because the Earth is not flat (really, it is not!) reduces.

3D

For a change, I am not talking of 3D printing, but we have altitude as well. So I am including altitude in the calculations. This means that a straight road that has a peak hill gets a point kept at the top of the hill!

4D

Yes, 4D printing would be cool, but no, I am now including time in the algorithm. That way we get points if a vehicle stops and starts or changes speed. The only issue here is deciding how time works as a unit in the distance calculation, so I need a metres/second. I have made this small, treating a 1 second deviation from the line between two points in space and time as a small fraction of a metre, hence you have to change speed or stop for many seconds to create a point you keep. It seems to work well.

GPS made easy

I am surprised how simple GPS is these days. For only £12 or so (from RS of all places, part 908-4085) I can get a small module with built in antenna that runs of 3.3V and provides serial GPS data and a very precise PPS output, is only 15mm square, and easily soldered to a PCB. It even has built in RTC that can run off a small button cell battery for fast fix and retaining time of day.

I have yet to decide on the best applications of this, apart from simple things like a speedo for a bicycle. There are applications with location logging (that dump to WiFi when back in range), or even if you just need a reliable time source for something like a door entry system (or a Brexit countdown clock, LOL).

A clock showing how long until sunset, wherever you are, would be cool :-)

I have made a module with GPS (the Adafruit module, as I found that before the RS part), and a display, so I can have a play around with it.

P.S. I have it set up for my bike, even with amount of daylight left...