Thursday, December 27, 2018

Monitoring GPS and NTP: Yet Another Raspberry Pi Project

TechRepublic recently published an article on the history of the Raspberry Pi, the single board computer that changed the way I work. Long time readers (there are a few) will already know that various generations of the Raspberry Pi have been the platform of choice for many of the projects I have written about here.

Because so many of my paying gigs are ARM based, the Pi has become my go-to prototyping platform. Because it's so inexpensive yet so capable - the latest version is about US$35 and has a Broadcom four-core 1.4Ghz ARMv7 processor - it's become my standard platform on which I build almost all of my side projects.
Some of my smaller projects - particularly those that have run on batteries or even on solar power - have been based on one flavor or another of the Arduino board. The Arduino uses an Atmel AVR eight-bit microcontroller, which is perfect for these small projects, but it's too resource limited for more ambitious tasks.
For my really resource intensive projects, even the Raspberry Pi is too limited. I have used the tiny Intel NUC platform with an i7 processor. The Next Unit of Computing is a full blown PC in a tiny form factor, extremely powerful - 3.5GHz for my latest one - but too pricey to permanently dedicate to a single project.
I've also had good experiences with other single board computers like the BeagleBoard. But those other SBCs were, at least initially, too expensive for me to deploy at scale, or lacked the hardware and software ecosystems that make it easy to use the Pi for the kinds of things I do.
Sitting here in my home office, there are four Raspberry Pis running inside projects sitting around, and one more on my LAN that I use as a development platform, all running the Debian-based Raspbian distro of Linux. There's even one sitting in my living room - a "mantle clock" (shown below; you can click on any of the images to see a larger version) that includes a cesium chip-scale atomic clock. In the basement, there are probably a dozen older first and second generation Raspberry Pis sitting in storage boxes, the remnants of one archived project or another.

Astrolabe (O-2)

Cesium

One of my more recent applications of a Raspberry Pi was a tool I built a few months ago to constantly monitor the Global Positioning System (GPS) and the six Network Time Protocol (NTP) servers - two commercial, four home brew, one with the aforementioned atomic clock - on my home LAN. This project is code-named Cesium. Cesium uses a Raspberry Pi 3B with a 7" touch-sensitive LCD display all inside a nice case. Here's a photograph of Cesium sitting on a shelf on my desk.

Lady Heather running on Cesium

When Cesium boots up, it automatically starts three monitoring tools, each in its own window. I implemented this by enabling auto-login on the Pi, and added a script to the default user's .profile that starts each tool in the background using lxterminal. You can select what window you want to view in the foreground just by touching the appropriate tab on the display.

Lady Heather

The first window runs Lady Heather, an open source and remarkably comprehensive tool used to monitor GPS-disciplined oscillators. The tool is configured to use the NaviSys Technology GR-701W, a USB-attached GPS receiver that delivers not just positioning, navigation, and timing (PNT) data via the usual NMEA sentences, but also, via the DCD modem control line, a one pulse per second (1PPS) frequency reference derived from the GPS signal.

Lady Heather can be configured to display all kinds of information. The display shown below is just what I chose as the most useful for my purposes.

Untitled

The sub-displays can be embiggened by just selecting them using the touch-sensitive display. This is particularly useful for the sky map in the lower right-hand corner that shows the positions of the visible GPS satellites according to their current azimuth and elevation, along with some of the more obvious astronomical objects like the sun and the moon.

Lady Heather "Watch" Display

NTP

The second window runs a shell script that periodically queries the NTPsec ntpd NTP daemon on Cesium. This daemon monitors the six NTP servers on my home LAN and compares their results with those of both the NIST NTP servers at time.nist.gov and those of the pool of NTP servers at pool.ntp.org. The configuration file /etc/ntp.conf on Cesium looks like this.

# Copyright 2018 by the Digital Aggregates Corporation, Arvada Colorado USA.
server hourglass
server sundial
server waterclock
server astrolabe
server obelisk
server candleclock
server time.nist.gov
server pool.ntp.org

driftfile /var/lib/ntp/ntp.drift

statistics loopstats peerstats clockstats
filegen loopstats file loopstats type day enable
filegen peerstats file peerstats type day enable
filegen clockstats file clockstats type day enable

restrict -4 default kod notrap nomodify nopeer noquery limited
restrict -6 default kod notrap nomodify nopeer noquery limited
restrict 127.0.0.1
restrict ::1
restrict source notrap nomodify noquery


The output of the NTP query script looks like this.

Untitled

Interestingly enough, over the very long run, the NTP algorithm pretty consistently prefers Astrolabe, the NTP server I built that has the cesium atomic clock, probably because it has the best long term stability of all the NTP servers Cesium monitors. Over time, the algorithm's least favorite time sources are typically Obelisk, an NTP server I built that is disciplined to the WWVB long-wave radio signal from Fort Collins Colorado, and Candleclock, an NTP server I built that uses another GR-701W GPS receiver and whose 1PPS reference is badly jittered by the USB interface. NTP is also usually pretty happy with Hourglass, a GPS-disciplined NTP server I built that uses a Raspberry Pi GPS expansion board the provides NMEA and 1PPS via a serial port, and Sundial, a commercial LeoNTP server that I like a lot.

Hazer gpstool

Hazer is my own C-based library and toolkit that parses standard NMEA sentences, and proprietary UBX packets from those Ublox-brand receivers that provide them. I find Hazer's gpstool utility useful for evaluating new GPS receivers, of which I have tested many.

I also discovered that gpstool is useful for monitoring the GPS and GLONASS satellite constellations, having used it to discover, mostly by accident, that a GPS satellite identified as PRN 4 (that being its Pseudo-Random Noise code number) was transmitting even though it was out of service. (This was intentional and documented, but the exact reason why has never been disclosed as far as I know.)

The gpstool display is continuously refreshed as the second GPS receiver connected to Cesium, a GlobalSat BU-353W10, transmits updates over its USB connection. This GPS receiver has the added capability of being configurable to detect jamming and spoofing.

Untitled

I like this display because it shows more of the low level detail about the output of the GPS receiver than the Lady Heather display. And I wrote the software, so of course it is automatically interesting to me. Plus, this is a kind of long-term test of Hazer.

I Smell Pi

I've successfully used Raspberry Pis in a slew of projects. As have others. I've seen my clients whip up WiFi and LTE test beds, remote embedded web servers, and all sorts of other useful stuff, all because they could buy a powerful Linux system for just a little bit of money. The Raspberry Pi is the little computer that could.

Friday, November 30, 2018

GPS satellite PRN 4

Around 2018-11-29T12:00-07:00 (lunch time yesterday in Denver) I was testing some changes to Hazer, my GPS receiver evaluation project, by comparing its results using the Ublox-8 based BU353-W10 GPS receiver with those of the real-time sky map displayed by the web site in-the-sky.org . I noticed that my BU353-W10 was reporting the satellite GPS PRN 4 as "in view" with a zero elevation and zero azimuth - due north right on the horizon. That vehicle wasn't reported by the sky map.

A little web-search-fu told me that there is no GPS PRN 4. The GPS space vehicle using Pseudo-Random Number code #4 had been decommissioned and its PRN - the numerical key used to uniquely encode data over its CDMA-based air interface - has not yet been reassigned to another satellite. GPS PRN 4 does not appear in the most recent GPS almanac.

Before I could do much else, PRN 4 dropped from view.

PRN 4 reappeared the next morning around 2018-11-30T09:00-07:00 at the same azimuth and elevation. I quickly dumped the raw NMEA strings from the BU353-W10 and verified using [NMEA 0183 Version 4.10 pp. 96-97] that I wasn't decoding the GSV sentences incorrectly.

$GPGSV,4,1,15,04,,,36,05,04,062,22,10,27,253,32,13,32,053,38*43
$GPGSV,4,2,15,15,60,092,39,16,15,289,26,20,53,269,,21,72,336,22*75
$GPGSV,4,3,15,24,06,129,33,26,10,264,15,27,11,322,31,29,36,170,50*78
$GPGSV,4,4,15,46,38,215,45,48,36,220,43,51,44,183,44*43

However, I noticed that the elevation and azimuth for PRN 4 weren't actually zero: they were empty strings, which Hazer numerically converted to a zero. Its signal strength of 36 dBHz was a reasonable value that changed over time. The elevation and azimuth makes sense, considering the vehicle doesn't appear in the GPS constellation's almanac of satellite orbits; the GPS receiver couldn't compute its position. The presence of 04 in the GSV sentence in this case merely means something using PRN 4 is being received, not that the satellite is literally in view in the sky.

I coded up a change to Hazer to detect this and mark it, and to gpstool to display a ? next to that SAT entry. I was able to test this before PRN 4 again dropped from view.

PRN 4 reappeared about twenty minutes later. Here is the new display from the Hazer gpstool. Note the ? marking GPS PRN 4, and a < marking those satellites used as part of the active position fix. (You can click on the images below to see a larger version.)

Screen Shot 2018-11-30 at 10.02.13 AM

GPS PRN 4 continues to drop from view and reappear. Its period of appearance does not coincide with the GPS orbital period.

Neither [NMEA 0183 4.10] nor [Ublox 8 R15] suggests any interpretation of the empty elevation and azimuth fields.

Forty years of experience tells me that this is somehow is a bug in my code, or (less likely) in the GPS receiver. But it does occur to me that PRN 4 would be useful for testing a ground-based GPS transmitter; the erratic daytime period of its appearance would make sense for such an activity in the continental America time zones.

Update (2018-11-30)

In the spirit of We have met the enemy, and he is us, I checked for a Notice To Airmen regarding planned GPS disruptions and found this.

Screen Shot 2018-11-30 at 10.26.46 AM

The UTC time stamps don't quite match up with when I observed GPS PRN 4. But this may yet be more GPS testing at the White Sands Missile Range (WSMR) in New Mexico or (in the last of the three notices) the Yuma Proving Ground (YPG) in Arizona.

Update (2018-12-04)

To give you an idea of the comings and goings of the mysterious GPS PRN 4, here is an excerpt from the system log in which gpstool now logs them, for roughly a twenty-four hour period. An octothorpe indicates an initial state where gpstool has just started and the status of PRN 4 is not yet known. A question mark means GPS PRN 4 came into view (or if the tool had just started, was already in view) with a zero azimuth and elevation. A space means GPS PRN 4 dropped from view. The initial and maximum signal strengths, and the duration in milliseconds, is logged. All times are Mountain Standard.

Dec  3 09:32:06 gpstool: phantom GPS PRN 4 was '#' now '?' at 25dBHz
Dec  3 09:42:03 gpstool: phantom GPS PRN 4 was '?' now ' ' at 38dBHz for 597010ms
Dec  3 09:48:59 gpstool: phantom GPS PRN 4 was ' ' now '?' at 34dBHz
Dec  3 09:58:51 gpstool: phantom GPS PRN 4 was '?' now ' ' at 36dBHz for 592009ms
Dec  3 10:01:11 gpstool: phantom GPS PRN 4 was ' ' now '?' at 35dBHz
Dec  3 10:29:57 gpstool: phantom GPS PRN 4 was '?' now ' ' at 40dBHz for 1726038ms
Dec  3 10:30:11 gpstool: phantom GPS PRN 4 was ' ' now '?' at 38dBHz
Dec  3 10:32:34 gpstool: phantom GPS PRN 4 was '?' now ' ' at 39dBHz for 143006ms
Dec  3 10:33:14 gpstool: phantom GPS PRN 4 was ' ' now '?' at 35dBHz
Dec  3 10:34:27 gpstool: phantom GPS PRN 4 was '?' now ' ' at 40dBHz for 72998ms
Dec  3 10:34:50 gpstool: phantom GPS PRN 4 was ' ' now '?' at 33dBHz
Dec  3 10:35:38 gpstool: phantom GPS PRN 4 was '?' now ' ' at 37dBHz for 48001ms
Dec  3 10:35:50 gpstool: phantom GPS PRN 4 was ' ' now '?' at 37dBHz
Dec  3 11:37:43 gpstool: phantom GPS PRN 4 was '?' now ' ' at 43dBHz for 3713086ms
Dec  3 11:42:22 gpstool: phantom GPS PRN 4 was ' ' now '?' at 29dBHz
Dec  3 11:49:29 gpstool: phantom GPS PRN 4 was '?' now ' ' at 36dBHz for 427014ms
Dec  3 11:59:15 gpstool: phantom GPS PRN 4 was ' ' now '?' at 25dBHz
Dec  3 11:59:16 gpstool: phantom GPS PRN 4 was '?' now ' ' at 25dBHz for 999ms
Dec  3 13:35:06 gpstool: phantom GPS PRN 4 was ' ' now '?' at 23dBHz
Dec  3 13:35:07 gpstool: phantom GPS PRN 4 was '?' now ' ' at 23dBHz for 998ms
Dec  3 16:37:48 gpstool: phantom GPS PRN 4 was ' ' now '?' at 31dBHz
Dec  3 16:45:52 gpstool: phantom GPS PRN 4 was '?' now ' ' at 36dBHz for 484015ms
Dec  3 17:08:03 gpstool: phantom GPS PRN 4 was ' ' now '?' at 29dBHz
Dec  3 17:11:16 gpstool: phantom GPS PRN 4 was '?' now ' ' at 36dBHz for 193003ms
Dec  3 17:14:37 gpstool: phantom GPS PRN 4 was ' ' now '?' at 30dBHz
Dec  3 17:19:16 gpstool: phantom GPS PRN 4 was '?' now ' ' at 34dBHz for 279011ms
Dec  3 17:26:53 gpstool: phantom GPS PRN 4 was ' ' now '?' at 31dBHz
Dec  3 17:41:51 gpstool: phantom GPS PRN 4 was '?' now ' ' at 36dBHz for 898023ms
Dec  3 18:00:33 gpstool: phantom GPS PRN 4 was ' ' now '?' at 30dBHz
Dec  3 18:06:14 gpstool: phantom GPS PRN 4 was '?' now ' ' at 36dBHz for 341011ms
Dec  3 18:09:17 gpstool: phantom GPS PRN 4 was ' ' now '?' at 33dBHz
Dec  3 18:22:07 gpstool: phantom GPS PRN 4 was '?' now ' ' at 37dBHz for 770011ms
Dec  3 18:26:10 gpstool: phantom GPS PRN 4 was ' ' now '?' at 34dBHz
Dec  3 18:59:11 gpstool: phantom GPS PRN 4 was '?' now ' ' at 39dBHz for 1981048ms
Dec  3 19:00:54 gpstool: phantom GPS PRN 4 was ' ' now '?' at 33dBHz
Dec  3 19:30:34 gpstool: phantom GPS PRN 4 was '?' now ' ' at 38dBHz for 1780046ms
Dec  3 19:33:50 gpstool: phantom GPS PRN 4 was ' ' now '?' at 31dBHz
Dec  3 19:44:47 gpstool: phantom GPS PRN 4 was '?' now ' ' at 36dBHz for 657014ms
Dec  3 19:55:24 gpstool: phantom GPS PRN 4 was ' ' now '?' at 27dBHz
Dec  3 20:02:55 gpstool: phantom GPS PRN 4 was '?' now ' ' at 33dBHz for 451009ms
Dec  4 05:52:37 gpstool: phantom GPS PRN 4 was ' ' now '?' at 26dBHz
Dec  4 05:52:39 gpstool: phantom GPS PRN 4 was '?' now ' ' at 26dBHz for 2001ms
Dec  4 05:52:40 gpstool: phantom GPS PRN 4 was ' ' now '?' at 26dBHz
Dec  4 05:52:41 gpstool: phantom GPS PRN 4 was '?' now ' ' at 26dBHz for 1007ms
Dec  4 08:10:39 gpstool: phantom GPS PRN 4 was ' ' now '?' at 31dBHz
Dec  4 08:16:56 gpstool: phantom GPS PRN 4 was '?' now ' ' at 33dBHz for 377014ms
Dec  4 08:19:21 gpstool: phantom GPS PRN 4 was ' ' now '?' at 29dBHz
Dec  4 08:22:17 gpstool: phantom GPS PRN 4 was '?' now ' ' at 31dBHz for 176011ms
Dec  4 08:28:52 gpstool: phantom GPS PRN 4 was ' ' now '?' at 32dBHz
Dec  4 08:40:15 gpstool: phantom GPS PRN 4 was '?' now ' ' at 34dBHz for 683019ms
Dec  4 09:03:34 gpstool: phantom GPS PRN 4 was ' ' now '?' at 33dBHz
Dec  4 09:17:36 gpstool: phantom GPS PRN 4 was '?' now ' ' at 38dBHz for 842031ms
Dec  4 09:22:47 gpstool: phantom GPS PRN 4 was ' ' now '?' at 35dBHz
Dec  4 09:39:55 gpstool: phantom GPS PRN 4 was '?' now ' ' at 35dBHz for 1027038ms

You can see that the duration that the transmission using PRN 4 ranged from a second to a half an hour. The times of the transmissions stopped at 20:00 (8PM) MST and resumed at 06:00 (6AM) MST. That's even more evidence to suggest that this is a rogue terrestrial GPS transmitter using PRN 4 somewhere in the continental U.S.

Update (2018-12-04)

The U. S. Coast Guard straightened me out.
*** GENERAL MESSAGE TO ALL GPS USERS ***
ON APPROXIMATELY 10 OCT 2018 SVN36 WILL RESUME TRANSMITTING L-BAND UTILIZING PRN04. AT L-BAND ACTIVATION, SVN36/PRN04 WILL BE UNUSABLE UNTIL FURTHER NOTICE. ADDITIONALLY, NO BROADCAST ALMANACS WILL INCLUDE SVN36/PRN04 UNTIL FURTHER NOTICE.
*** GENERAL MESSAGE TO ALL GPS USERS ***
Mystery solved!

Update (2018-12-06)
"SVN36 was removed from the active GPS constellation on 21 February 2014 (ref. NANU 2014019). It is now a "reserve" satellite, located near slot C2. SVN36 temporarily transmitted L-band signals as PRN10 between 17 September and 16 October 2015 inclusive (ref. IGS monitoring). It was set unhealthy and not included in broadcast almanacs (ref. NANU 2015080). SVN36 transmitted L-band signals as PRN04 between 20 July and 28 November 2017 (ref. NANU 2017070 and IGS monitoring). It was not set healthy and not included in broadcast almanacs."
- from U. of New Brunswick (CA) Geodesy & Geomatics Engineering web site
Update (2019-01-03)

In an interesting turn of events, the recently launched SVN74, a new Block IIIA GPS satellite that is the first of an upgrade to the GPS constellation that will bring a variety of new capabilities, will be using PRN4, the same pseudo-random noise code that was being used by the decommissioned SVN36 that I've been watching.
*** GENERAL MESSAGE TO ALL GPS USERS ***
GPS III SVN74 (PRN04) WAS LAUNCHED ON 23 DEC 2018 (2018 JDAY 357) AT 1351 ZULU. THIS SATELLITE WILL UNDERGO EXTENSIVE ON-ORBIT CHECK OUT AND TESTING PRIOR TO BEING SET HEALTHY.
A USABINIT NANU WILL BE SENT WHEN THE SATELLITE IS SET ACTIVE TO SERVICE.
*** GENERAL MESSAGE TO ALL GPS USERS ***
I have to wonder if the use of PRN4 in SVN36 was some kind of test with ground systems done in advance of the SVN74 launch.

Wednesday, November 07, 2018

Vamoose, Rustler

For the past forty years I've been keeping my eyes open for a new programming language to do the kinds of things I need to do: concurrent, parallel, asynchronous, real-time, close to bare metal, mobile, embedded, and lately, internet of things. Most of my paying gigs are still in C++ or C. But I've seen more than one ginormous C++ code base that was effectively undebuggable. And as productive as I am in C, my PDP-11 experience means I know it for what it is: a portable structured assembler language.

After a few false starts, I've finally arrived at Go and Rust.

Go - also known by the more search-friendly name Golang - is a language that compiles to machine code, unlike Python or Java. It is a product of Google. Go was invented in part by some former Bell Labs folks even older than I am that were among those responsible for the invention of UNIX and C.

Rust is also a language that compiles to machine code. It is product of Mozilla, the folks that brought you among other things the Firefox browser, and a host of other folks that have formed a Rust community. Rust has been recently growing in popularity, if one is to believe more than one survey of programming languages.

If you want to skip the rest of this article and just peruse some open source Go and Rust code that I believe are reasonably idiomatic - that is, that uses these languages in the way in which they are each intended - you can find my repositories on GitHub. They are both licensed under the LGPL 2.1.

Each repository has a README that tells you how to extract the software from GitHub, build it, run the unit tests, and run the functional test. Both projects have been built, unit tested, and run on both an x86_64 Ubuntu system and an ARMv7 Raspbian system.

I will not teach you Go or Rust in this article. It's not even a "Hello, World!" kind of tutorial. I will give you a taste of what the languages look like, tell you what I learned about each language, what I liked and did not like, and what I think they would be useful for, as I solved the same problem in each.

Disclaimer: I am neither a Go nor a Rust expert, as will quickly become obvious.

Approach

My close friends and long-time colleagues will confirm that I have my share of personality defects. One of them is that I can only really learn by doing. Only through the laying on of hands (as I like to say) am I able to internalize new knowledge. One of the ways I choose to do this in a new programming language is to implement a non-trivial piece of code. My non-trivial code of choice is the Generic Cell Rate Algorithm (GCRA).

The GCRA is a rate control algorithm that I first encountered around 1996 when I was writing firmware in C++ at Lucent Technologies for products based on Asynchronous Transfer Mode (ATM). Implementing the GCRA - a library that implements the algorithm, unit tests, some utilities that use the library, and which can be used as a functional test - captures a lot of the day-to-day nuts-and-bolts experience of using a language: its usability, its support for object-oriented design, its build environment, its run-time library, its debuggability, its testability, its documentation, and so forth. I have implemented the GCRA in C++ (which shipped in a product), Java, C, and now Go and Rust.

Each of the two repositories cited above implements the GCRA in a library (Rust: crate), in the form of several functional units (Go: package, Rust: module), that includes an interface (Rust: trait) called Throttle that defines the common API, with two derived classes (Go and Rust: struct) named Gcra and Contract; a Contract is composed of two Gcra objects, one to limit the sustained rate, the other to limit the peak rate of an event stream. Events are whatever you want to rate limit: bits, bytes, packets, what have you. Unit tests are implemented for all functional units. One unit test simulates an event stream through the implementations. Another unit test generates actual events in the form of bytes in data packets through a test harness with multiple concurrent tasks using each language's native concurrency mechanism. The library is used to implement two utilities (Go: command, Rust: executable) named fletch and shape that are in turn used to create a functional test.

Go

Here is a snapshot taken from the GCRA implementation in Go as it renders in the Eclipse IDE. It is just a code snippet to give you a feel for what different portions of the language looks like. You can click on it to see a larger version.

Screen Shot 2018-11-07 at 11.22.50 AM

The package keyword controls visibility; variables and functions inside a package are visible to functions inside the same package. Access is otherwise controlled simply by capitalizing the name of the variable or function, which makes them publicly accessible.

A class is created by defining a struct inside the package. (Several classes can be defined inside the same package). Methods for that class are established by defining a function with an explicit object pointer as a kind of argument list separate from the function argument list.

There is no inheritance, but you can define an interface, which defines method signatures that have no implementation. Interfaces are not associated explicitly with a class but are defined via duck typing ("If it walks like a duck and quacks like a duck, it must be a duck"): if a class implements all the required method signatures of an interface, it is automatically a subclass that interface. There is however a way to inherit the methods of another class via composition (but I didn't use that in this project).

Like Java and Python, Go is a garbage collected language. Variables may be allocated from either the stack or the heap; the syntax of the language is agnostic to this and the developer has no control over it. The compiler performs escape analysis at compile time: if the pointer can escape the scope of the code block in which it was allocated, the object is allocated on the heap and is later deallocated by the garbage collector; otherwise it is allocated on the stack and deallocated when it goes out of scope.

Go has arrays, but unlike C and C++ they aren't ambiguously used sometimes as a variable and sometimes as a pointer. Arrays have Go are first class variables with a fixed length. If you want to use a subset of an array, Go provides an operator to define an array slice: a starting position within an array and a count of the number of elements in the slice. For example: you allocate a buffer as a fixed length array

var buffer = make([] byte, int(burstsize))

but when, for example, you use a standard library function to read data into the buffer, you get back a slice 

buffer[0:length]

depending on how much of the array was used.

Go has explicit width integer types, something every embedded developer will appreciate. Unlike C or C++, there is no implicit conversion between integer (or floating point) types. When you do math with mixed types, you must explicitly cast the types to match.

datum[0] = byte(rand.Int31n(int32('~') - int32(' ') + 1) + int32(' '))

The Go compiler complains if you import a package that you don't use, or if you declare a variable that you don't use. While this is irritating at first, it really contributes to cleaner code.

Here is a code snippet that shows how the unit test harness I wrote in Go creates four different concurrent tasks, one to produce a data stream, one to shape it to conform to a traffic contract, one to police it using another traffic contract, and one to consume it.

Screen Shot 2018-11-07 at 11.36.38 AM
These concurrent tasks in Go aren't POSIX threads. They are goroutines, very low overhead coroutines, all of which run in the context of one or more POSIX threads. Go typically creates a POSIX thread for every logical core on the processor on which the Go program runs. Each thread can multiplex one or more goroutines. Because goroutines are much lighter weight than a POSIX thread, they are much more scalable; a single Go program can consist of dozens, hundreds, or even thousands of goroutines.  This allows you to exploit many processor cores by assigning a new goroutine to, for example, every individual incoming network packet, or to every one of thousands of concurrent incoming data streams.

I've implemented this kind of architecture myself in embedded projects, where each coroutine was one state machine among many, all managed by a single thread (a VxWorks task in my specific case). Each state machine handled one among tens of thousands of simultaneous data streams. But I wrote thousands of lines of C++ code to do that; in Go, I could have done it in just a few pages of code.

This is what I think is Go's real raison d'etre: allowing the developer to exploit large numbers of processor cores by making it easy, even trivial, to write highly parallel or pipelined algorithms.

The go keyword is used to spawn off a function into a goroutine. Above, the function is defined inline, as a kind of closure. I use a WaitGroup, a kind of counting semaphore, to block the main thread of control until every goroutine completes. Inside each goroutine body I use the defer keyword to register a function that will be automatically called when the function that is the goroutine goes out of scope (essentially exits its terminating curley bracket) for any reason. That function signals the WaitGroup. Then I call my own function that actually implements the goroutine intended action.

Although I don't show it here, Go has a built-in message passing mechanism called a channel or chan. My producer and shaper goroutines, and policer and consumer goroutines, communicate over channels. A channel has a type, defining what kind of object it queues, and a depth, defining how many of those objects can be queued before the sender blocks.

My shaper and policer goroutines communicate using UDP sockets. The standard Go library has a comprehensive set of packages that include sockets, encryption, JSON, and other useful stuff.

If you stick to the directory layout expected by the Go tool chain, building a library and applications is as simple as

go build github.com/coverclock/com-diag-vamoose/Vamoose/cmd/fletch
go build github.com/coverclock/com-diag-vamoose/Vamoose/cmd/shape

and running the unit tests is a matter of

go test github.com/coverclock/com-diag-vamoose/Vamoose/pkg/ticks
go test github.com/coverclock/com-diag-vamoose/Vamoose/pkg/fletcher
go test github.com/coverclock/com-diag-vamoose/Vamoose/pkg/throttle
go test github.com/coverclock/com-diag-vamoose/Vamoose/pkg/gcra
go test github.com/coverclock/com-diag-vamoose/Vamoose/pkg/contract

One of the downsides of Go is that it doesn't play well with valgrind. I'd like to think that with its garbage collector, checking for memory leaks isn't necessary. But call me paranoid. Running valgrind on a Go application is an invitation to be inundated with worrisome warning messages that probably have nothing to do with your own code.

Rust

Here is another snapshot taken from the GCRA implementation in Rust as it renders in the Eclipse IDE. It is also just a code snippet to give you a feel for what different portions of the language looks like. You can click on it to see a larger version.

Screen Shot 2018-11-07 at 11.21.45 AM

Visibility in Rust is defined by what is inside the same module defined in the mod code block. Unlike Go, access is controlled using a keyword pub.

A class in Rust is defined with as a struct. More than one class can be defined inside the same module. Methods for a class are defined in the impl code block, and applicable interfaces identified using the post-fix for keyword.

In Rust, an interface is defined as a trait. Like Go, Rust doesn't have inheritance, but a trait can implement actual code.

When I write code in C++, I of course use the new and delete operators to explicitly allocate and deallocate objects on the heap. I always have to come to grips with when it is appropriate to call delete. I go through a kind of static code analysis in my head: if I pass this pointer to this function, is it merely borrowing it (so that it is still the responsibility of the caller to deallocate it), or am I moving the object to the function (so that it is now responsible for either deallocating it, or passing that responsibility on to someone else).

The Rust compiler does this too, at compile time, through the actions of its borrow checker. Rust does not do garbage collection. Instead, memory is allocated when the developer defines a variable. Then the compiler tracks that memory reference at compile time, enforcing hard and fast rules as to whether you can pass that pointer to a function, and whether that pass is a borrow or a move. The memory is automatically deallocated when it goes out of the scope in which is was originally allocated, or in which it was moved into.

There are some exceptions to this. There are containers provided by the Rust standard library that are allocated on the heap and which implement reference counts to determine when they can be deallocated. And you can explicitly deallocate memory before it goes out of scope using the drop operator.

Along with this almost no-cost memory management scheme is a set of rules which are rigidly enforced at compile time: you can have either one and only one read/write (mutable or mut) reference (pointer) to an object, or you can have multiple read-only (immutable) references to an object; and no null references.

Rust implements arrays and array slices very similarly to Go. You allocate a fixed size array

let mut buffer = [0u8; 65536];

and an input function effectively returns a slice

buffer[0..length]

depending on how much data was read in.

Just like Go, Rust has explicit width integer types, and there is no implicit conversion between integer (or floating point) types. When you do math with mixed types, you must explicitly cast the types to match.

let byte: u8 = ((rand() % (maximum as raw::c_int)) + 1) as u8;

Like Go, the Rust compiler complains if you import a module that you don't use, or if you declare a variable that you don't use, or if you initialize a variable to a value when you declare it and then don't use that value, or even if you have extra parenthesis in an expression (that part really irritates me).

Here is a code snippet that shows how the unit test harness I wrote in Rust creates four different concurrent tasks, one to produce a data stream, one to shape it to conform to a traffic contract, one to police it using another traffic contract, and one to consume it, just like I did in Go.

Screen Shot 2018-11-07 at 11.37.41 AM

Rust implements concurrency using full POSIX threads. Above I spawn off a thread defined as a kind of closure, and each thread calls its producer, shaper, policer, or consumer implementation in the form of a function. The main routine uses a POSIX thread join to wait until the four threads complete.

In the spirit of the borrow checker described above, the Rust compiler prevents data races between threads by forcing the developer to protect shared resources using a synchronization mechanism. I use a Mutex, not shown here except for the use of its lock method; the unlock is performed automatically when the variable goes out of scope. The compiler also forces the developer to allocate shared data on the heap, also not shown here except for its use of the unwrap method which returns a pointer to the object from its heap container, an Arc (for Atomic reference counting) in this case. The use of a reference counted container allocated on the heap prevents the object from being deallocated when its original reference goes out of scope in the main thread (which can exit before the child thread), and instead is deallocated when its reference count goes to zero. Like the borrow checker, this is all enforced at compile time.

The Rust standard library also provides the channel as a message passing mechanism, and this implementation uses them in a very similar way to how I used them in Go. UDP sockets are also used similarly to that in the Go implementation, and are provided by the Rust standard library.

One thing that I couldn't find in the Rust standard library was a random number generator, which is needed by my unit test harness. But one of the things I really liked about Rust was how easy it was to interface my code to the standard C library and call its random number function. Go has a way to do this as well, but it's not nearly as straight forward (but then I didn't need to use it in Go).

Screen Shot 2018-11-09 at 10.13.18 AM

If you stick to the expected directory layout, building a Rust library and applications can be done by

cargo build

and running the unit tests is as simple as

cargo test

My Rust applications played just fine with valgrind.

Remarks

I found Go very intuitive to use. Perhaps that was because it was inspired by Communicating Sequential Processes (CSP), a formal language for describing concurrent programs developed by British computer scientist Tony Hoare in 1978, and I recall reading his original paper in graduate school decades ago (and I have his book on CSP around here somewhere).

But more to the point, Go is an excellent fit for the post-Moore's Law world in which processors aren't getting faster, but are providing a lot more execution cores; in which if you want more performance, you need to parallelize your code.

Mostly I think Go is easy to use because it was designed by some pragmatic and experienced software developers who wanted a language in which they could get some work done.

Rust has a well deserved reputation for having a steep and high learning curve. What I did in days in Go took me weeks in Rust. It reminds me of a comment a colleague of mine made decades ago about the Ada programming language: "If you can just get your program to compile, it frequently works the first time." I was sharing my Go and Rust experience with a more contemporary colleague - who has a Ph.D. in physics and had worked at Fermilab - who has also used both languages, and he darkly remarked "I may not be smart enough to use Rust." Which, as we all know, is code for "seems overly complicated". But we both loved Go.

On the other hand, I probably won't be writing any device drivers, hard real-time algorithms, or micro controller firmware - tasks that are absolutely in my wheelhouse - in Go. Its background garbage collector would make that problematic. But I sure would be tempted to do so in Rust. Rust eliminates entire classes of errors regarding memory leaks and data races by simply eliminating your ability to write code with those bugs. Along the way, it eliminates common - and legitimate - design patterns I've used for years with concurrent code. It's Rust's way or the highway. But maybe that's okay.

In addition to its learning curve, a big complaint I have about Rust is that it's under documented. Despite the books and web sites to which Rust aficionados will point you, many of its features are undocumented, and the examples either don't work (because of recent changes in the language) or are too simple to be useful. That makes the Rust learning experience painfully full of reverse engineering and trial and error.

(One of the tricks I learned with Rust was to code a call to some function(s) in the standard library and assign the result to something like an integer variable. The type mismatch error message from the compiler would include the fully qualified type name of the function return. That was often more useful than what little documentation existed. Important safety tip: the "suggestions" made by the compiler were typically not really what I needed to do.)

If you are tempted to use Rust, you have to decide on the economic trade off between climbing the Rust learning curve versus writing in C or C++ and just avoiding making the kinds of mistakes that Rust eliminates. Those of us that have been writing large systems in C or C++ for decades already know how to do that. But since we're all so old as to almost be dead, Rust might be just the thing for the men and women that replace folks like me.
Update 2018-11-15: one feature both Go and Rust have that put them way ahead of C and C++: they do array bounds checking, made possible by the lack of confusion between arrays and pointers. This is a huge win, not just from a reliability point of view, but security as well: no more buffer overflows. That is probably reason enough to use Rust over C or C++.
I don't see Go and Rust as competitors. I believe that every programming language can be considered a domain specific language, and this is true of Go and Rust. The design of every programming language makes a different compromise in its choice between performance, usability, applicability, and so forth. And every successful programming language survived because it found a niche for which it was unusually well suited. There is no programming language that can fulfill all needs for all people. That's why everything isn't written in Lisp or Smalltalk. But while I might well use Rust for the really low-level stuff, I am pretty sure I could happily write everything else in Go.

Monday, October 15, 2018

Tick

I've decided that I might as well accept the Buddhist view of time: that time itself is an illusion and our conception of it is merely a measure. The only way we have to perceive time is in the relative order of events that take place, regardless whether time somehow exists independently of these events or not. All timekeeping ultimately depends on a frequency source - or oscillator - which is nothing but a generator of evenly spaced events. The number of events generated per second is the frequency of the oscillator, and is measured in Hertz.
Update 2021-10-23: While engineers and scientists conventionally measure the frequency of an oscillator in Hertz (Hz), also known as cycles per second, mechanical watch designers and aficionados typically measure in vibrations per hour (VPH) or beats per hour (BPH). I recently learned that while Hertz counts a complete back-and-forth movement, or cycle, of the mechanical part (think of a pendulum), which is a complete tick tock sequence, the vibration or beat considers the tick and tock separately. So an oscillator with a frequency of 4 Hz can be said to beat at 28,000 VPH or BPH. [Ref: Logan Baker, "What Does Watch Frequency Mean?", Hodinkee, 2021-08-21]


(Clock with a 4Hz oscillator using a pendulum resonator and a deadbeat escapement.)

Every oscillator makes use of a resonator, some source of periodicity that we take from nature: the motion of the sun, the fall of a drop of water, the swing of a pendulum, the rotation of a balance wheel, the vibration of a quartz crystal, the hyperfine transition of a cesium atom. If something happens faster than the interval between the beats of that oscillator, the only way to measure that interval is to use an oscillator with a higher frequency, which may mean a different resonator: the transition of an aluminum atom or of a ytterbium atom. How do we use these oscillators? By treating each beat of the oscillator as an event, and counting the number of events that occur during the time interval we want to measure.


(Watch with a 6Hz oscillator using a balance wheel resonator and a lever escapement.)

Is there a maximum possible frequency? Physicists think so: the reciprocal of one Planck time, which is about 5.39 x 10-44 seconds. It's the amount of time it takes a photon to cross a Planck length. One Planck time is the shortest time interval physicists believe can meaningfully occur, the duration it takes for the fastest possible object to cover the shortest possible distance found in nature. My calculator tells me that such a hypothetical Planck-frequency oscillator beats at a frequency of about 1.85 x 1043 Hertz. That's a lot of Hertz.


(Slow motion deadbeat escapement creating the tick tock.)

What happens between the beats of this hypothetical Planck-frequency oscillator? The question has no meaning; we believe one Planck time is the smallest possible interval that can occur. Time might as well not exist between the beats of a Planck-frequency oscillator. If we want to talk about the time between any two events, we have to find a frequency source that generates events more frequently than the interval we want to measure - any other notion of time is purely an abstract concept - and there is nothing faster than a Planck-frequency oscillator. (I'm told there may actually be even shorter time intervals in the field of quantum gravity, but they are apparently impossible to measure; what this might mean is left as an exercise to the reader.)

Capture
(Snapshot of an oscilloscope on a 10MHz oscillator with a cesium atomic resonator.)

I didn't come to this notion by reading about the more esoteric aspects of physics (as much as I enjoy doing that). I did it by developing and debugging real-time firmware that shaped the emission rate of ATM cells on a SONET channel carried over an OC-3 optical fiber. By building a stratum-0 NTP server with a cesium reference oscillator. By assembling an educational model of a mechanical clock.

Untitled
(Ytterbium lattice optical atomic clock at the NIST Boulder Labs.)
Update 2021-10-23: Remarkably, not long ago, I changed my mind, after considering how General Relativity and Special Relativity affects our measurement of time. The former causes time to speed up the further we are from the gravitational influence of a mass, and the latter causes time to slow down the faster we go. These are real measurable effects that systems like the Global Positioning System (GPS) that depend on timekeeping have to take into account. The GPS satellites are in orbit at 20,000 km, so their atomic clocks are further away from the mass of the Earth than those on the surface. This causes them to run faster by about 45 microseconds a day when compared to atomic clocks on the ground at sea level. But the satellites are also moving at 14,000 km/hour. That centripetal acceleration causes them to run slower by about 7 microseconds a day. This requires a net adjustment of 38 microseconds per day relative to clocks on the ground. Whatever time is, it is a real thing, the measurement of which can be affected by physical events and circumstances. [Ref: Richard W. Pogge, Real-World Relativity: the GPS Navigation System, The Ohio State University, 2017-03-11]

Tuesday, September 18, 2018

We have met the enemy, and he is us.

One of the side effects of having five GPS-disciplined NTP servers in your home - three home-brew, two commercial - is that you become sensitized to issues with the Global Positioning System.

The other day I was sitting at my desk in my home office looking at cat memes doing some bleeding edge research and development, when out of the corner of my eye I noticed that the GPS lock LED on the home-built clock on the right side of my desk wasn't blinking. I ssh-ed into it, poked around, and verified that all the software was running; the problem was with its GPS receiver. Then I noticed that the home-built clock on the left side of my desk has just lost GPS sync too.

I whipped my Herman Miller Aeron chair around to look at the two small commercial units on my lab bench. The 1PPS LED on the Time Machines TM 1000A had stopped blinking. While I was trying to wrap my poor old head around that, the tiny color LCD display on the Leo Bodnar Electronics LeoNTP right next to it lit up with a red warning message about GPS lock being lost.

My first inclination was to go down to the basement to prepare for the coming apocalypse. Instead, I exercised some rare (for me) restraint and sent a query to Time Nuts - a mailing list for folks even more obsessed with precision timing than I am (they do exist).

In short order, Graham in Austin Texas kindly pointed me to the FAA web site where one can look up NOTAMs, notices of issues possibly affecting aviation and pilots, one of the categories of which is outages in the Global Positioning System. Here's the specific NOTAM he pointed me to.
ZDV   DENVER (ARTCC),CO. [Back to Top] !GPS 08/260 (KZDV A0287/18) ZDV NAV GPS (WSMR GPS 18-20) (INCLUDING WAAS, GBAS, AND ADS-B) MAY NOT BE AVBL WI A 359NM RADIUS CENTERED AT 333345N1063840W (TCS054036) FL400-UNL, 311NM RADIUS AT FL250, 215NM RADIUS AT 10000FT, 223NM RADIUS AT 4000FT AGL, 169NM RADIUS AT 50FT AGL DLY 1830-2230 1809031830-1809082230
It took some fu on my part to decode it, but it wasn't that hard.

ZDV ARTCC is the Denver Air Route Traffic Control Center.

333345N1063840W is 33°33'45.0"N 106°38'40.0"W, the location at which the source of the GPS interference is centered, which is smack dab in the White Sands Missile Range in New Mexico. (For a good time, click on the Google Maps link I provided, drop into the satellite view, and drill down until you can see the parking lot where they parked their equipment.)

359NM is 359 nautical miles, an area which includes my home near Denver Colorado.

1809031830-1809082230 is 2018-09-03 18:30 UTC to 2018-09-08 22:30 UTC, which is the time window in which I noticed my clocks losing GPS.

GPS disruption has become enough of an problem that there is now a U.S. Coast Guard web site where you can report issues. Most of them appear to be either user error or product failures. But some of them are probably related to testing of deliberate GPS interference - either as a field tactic or to evaluate their ability to deal with it - by our own military. Or others.

Don't say I didn't warn you.

Monday, August 27, 2018

Practical Geolocation II

In Practical Geolocation I mentioned that I had ordered a GlobalSat BU-353W10 GPS receiver. Like most of the receivers I've tested, this device is a puck at the end of a USB cable. The puck contains all the active electronics including an amplified patch antenna.
N.B. If any of the images in this article appear funky, or if you just want to see a larger view, click on the image to be taken to another version. Or try the web version of the article which is accessible from the mobile version via a link at the bottom of my blog. I've noticed that the images in the mobile rendering of this article seem to tickle a bug in both Safari and Firefox on my iPhone, causing wackiness to ensue. This doesn't seem to be an issue on my iPad, or on my Mac. Your mileage may vary.
Untitled

Like the Navlocate GR-803G I described in that previous article, the BU-353W10 is based on the Swiss-made U-Blox 8 chipset. U-Blox 8 has a number of advanced features I crave, like enhanced signal sensitivity, multiple RF stages, seventy-two channels, ensemble fixes based on both the U.S. GPS and the Russian GLONASS satellite constellations, and support for the proprietary UBX binary protocol. I've also had good experiences integrating and using earlier U-Blox chipsets board-mounted in prior embedded projects.

The BU-353W10 is a few dollars more expensive than the GR-803G, but is available from Amazon.com for US$45 with two-day shipping, where as I ordered the GR-803G from eBay and it was shipped from China.

The BU-353W10 is the third in a series of GlobalSat (formerly USGlobalSat) devices, and those models, the BU-353S4 and BU-353S4-5Hz, both based on the SiRF Star IV chipset, have worked flawlessly. (SiRF is now owned by Qualcomm.)

All of this made me kindly disposed towards this new GlobalSat device. What gave me pause regarding the BU-353W10 is all the warnings on both Amazon.com and on the GlobalSat web site about how the devices was specific to Windows 10 and not supported on MacOS or Linux. Even its model designation had a "W10" in its name. So I anticipated having a bit of a mystery to solve.

Since I'm not writing a detective novel, I'll just jump to the conclusion: the BU-353W10 worked just fine with my Hazer software. I haven't tested it with anything else, but I would expect it to work fine with the GPSd and Lady Heather open source tools I mentioned in that prior article, at least on a Linux host. I wondered what exactly Windows 10 required of its GPS receivers, but some web searching hasn't enlightened me in that respect. But I took a conservative approach to reverse engineering the BU-353W10, which I thought someone might find useful for the next under-documented GPS receiver that comes along.

I'm typically wary of new USB devices. So the first thing I did was plug the BU-353W10 into a USB port on a Raspberry Pi - a system whose entire microSD card I could easily reformat and reload with a new OS should the worse case scenario occur - and carefully watched the system log.

GlobalSat BU-353W10 syslog

The device enumerated on the USB bus, and its vendor and product identifiers, 1546 and 01a8 respectively, were exactly what I expected from the U-Blox 8 chip, and were the same as those reported by the enumeration of the GR-803G.

Like that earlier device, the BU-353W10 instantiates a /dev/ttyACM device. Many of the USB GPS devices I've tested instead instantiate as a /dev/ttyUSB device.

BU-353W10 dev

The latter is intended to represent a UART-over-USB device, while the Abstract Control Module (ACM) is more typically intended to be a modem-over-USB. I'm told that the reason many devices appear as ACM devices is that it's a simpler interface, and may place less requirements on the host computer. Other than the device name, I haven't had to make any changes to using either type of device in my Hazer software.

You will notice that the standard behavior is for the /dev/ttyACM0 device to only be usable by user root or members of group dialout. There are several ways to address this. The worst choice would be to run all your applications as root (but lots of embedded Linux projects do exactly that). The best would probably be to alter the rules in /etc/udev/rules.d to change the owner, group, and permissions of the /dev/ttyACM device to something more appropriate when the BU-353W10 enumerates as v1546p01a8 on the USB bus. But I chose instead to add my user, pi in this case, to the dialout group (something I had already done long ago).

BU-353W10 dialout

I could have next just fired up Hazer's gpstool. In retrospect, that would have worked. But while gpstool can log a lot of stuff, it ignores anything its NMEA and UBX state machines do not recognize. Since I was still suspicious of the device, I chose instead to fire up some tools from my Diminuto library that I find useful for reverse engineering serial-port-like devices: serialtool, phex, and dump.

serialtool is a Swiss Army-knife for serial devices. It supports several different kind of loopback tests, but in its most basic use it simply allows you to set the serial port parameters (including modem control) however you see fit, read from the device and write to standard output, and read from standard input and write to the device. serialtool would tell me anything and everything that the BU-353W10 was emitting.

phex (pronounced "fex") reads from standard input and emits whatever it finds to standard output, expanding any non-printable characters to ANSI C-style escape sequences, and handling the wrapping of the screen to whatever width you specify (defaulting, as usual, to eighty, in a continuing tribute to our punch card days).

For devices that produce mostly non-printable output, phex output is a little busy. dump produces a hexadecimal dump along with printable characters that will seem familiar to a lot of old timers.

Here is a snapshot of serialtool used with phex.

BU-353W10 phex

I didn't see anything untoward: typical NMEA sentences.

Here is a snapshot of serialtool used with dump.

BU-353W10 dump 1

Again, nothing unexpected: printable NMEA sentences terminated by a carriage return and a line feed.

Which you find more readable, phex or dump, will depend on the output of the device you are examining, and maybe what you're used to seeing in your own development efforts.
You will have already realized that these tools aren't specific to GPS. I developed them as part of Diminuto long ago for my embedded Linux reverse engineering, integration, and troubleshooting toolkit. The base functionality of these tools are C functions in the Diminuto library, so they can be called from other applications as well, as we'll see with gpstool below. Putting most of the heavy-lifting in a library, and building a relatively simple command line tool around it, facilitates testing by placing the business logic in the library - where it can be exercised by standalone unit test programs - and the user interface in the command line tool - where it can be used from scripts as a functional test. This has been my preferred development pattern in this domain for a long time.
Next step was to use the Hazer ublox8 functional test script. Since the BU-353W10 uses the U-Blox 8 chipset, we would expect this script, which talks to any U-Blox 8 device, to work. The script not only logs all of the output of the device, it sends binary UBX commands to the device to enable it to periodically emit binary UBX packets with additional and more detailed information than can be had just using the ubiquitous NMEA standard output. The script, which is implemented using gpstool, logs all of the input to and output from the device in phex-style format, including the binary UBX packets. (You can ask gpstool to emit UBX packets read from the device in dump-format as well if that's your preference.)

BU-353W10 ublox8

I let this run for a while and didn't see any complaints from gpstool.

The last step was to create and run a new bu353w10 functional test script... which, as it turns out, is actually identical to the gn803g functional test script. I did in fact try the gn803g script first and verified that it worked, before creating a new script specific to the BU-353W10. These scripts use the full screen feature of gpstool which uses ANSI escape sequences, and some output formatting trickery, to create a dynamically updating display.

BU-353W10 bu353w10

Here's the first time we notice something interesting. At the end of every line produced in this format is a timer value that tells you how long the data displayed has until it is considered stale and its output will be suppressed. The GR-803G GPS receiver updates the satellite view, reported by the NMEA GSV sentence, every second, so for that device this lifetime value sticks at the maximum of ten seconds I specified on the gpstool command line in the gr803g script.

But here, the timer decrements in the bu353w10 script's output until the BU-353W10 refreshes it by emitting more GSV sentences, apparently every five seconds. That's completely adequate for my purposes, but it is a difference between the GR-803G and the BU-353W10, two devices that otherwise seem pretty similar. I haven't tried it, but you should be able to use gpstool to send UBX commands to either device to change the frequency at which they emit GSV sentences. (Yeah, you totally can; see below.)

I also noticed that the GR-803G emits the NMEA VTG sentence, providing course over ground (COG) true bearings in decimal degrees, while the BU-353W10 does not. I did this by using gpstool to collect a minute of output, and then post processing the resulting data to find all the unique sentences generated. This is a lot simpler than it sounds.

gpstool -D /dev/ttyACM0 -b 9600 -8 -n -1 -L bu353w10.dat -v
# Wait for a minute and then control-C out of the program.
awk -F, '{print $1;}' < bu353w10.dat | sort | uniq

You can compute COG yourself from the differences in successive position fixes. It is also possible that you can use gpstool to send a UBX command to the BU-353W10 to enable VTG output; I haven't tried it (yet). (No, wait: I did; see below.)

I walked into this little project not knowing whether I'd be spending a morning or a few days getting the BU-353W10 to work. Or maybe it would never work. That's typical of the kind of tasks I am called upon to do. As it turns out, this task was almost a no brainer. Despite all the warnings regarding the support (or lack of it) of the BU-353W10, it was a simple matter to integrate it into Hazer. I wouldn't expect doing something similar with GPSd would be that different. But it was a good example of the kinds of tools I can bring to bear on learning how a new device works just minutes after unboxing it.

Update (2018-08-27)

You can easily alter the frequency of the GSV sentences and enable the emission of the VTG sentence just by adding a couple of -W command line parameters to gpstool to request a configuration change to the U-Blox 8 chip using the proprietary (but printable) $PUBX message.

gpstool -D /dev/ttyACM0 -b 9600 -8 -n -1 -E -t 10 \
    -W '$PUBX,40,GSV,0,0,0,1,0,0' \
    -W '$PUBX,40,VTG,0,0,0,1,0,0'

I've added those parameters to the bu353w10 functional test script and verified it by capturing the output data as described above.

BU-353W10 bu353w10 2

Friday, August 24, 2018

Practical Geolocation

Geolocation, via the Global Positioning System (GPS) or other satellite constellations, keeps cropping up in my line of work, whether I'm working on software for a cellular base station or an in-flight entertainment system for business aircraft. This won't come as a surprise to anyone. Nowadays we are all depending on smartphone apps like Google Maps or the navigation system in our vehicle dashboard to get us from place to place. And even if we somehow know where we're going without a vast infrastructure of global navigation satellite systems, mobile radio telecommunications, and Earth mapping from space, to help us, we're still relying on GPS for other services like precision timing, whether we realize it or not.

The good news is that it's never been easier to make use of what was once an exotic space-based technology available only to the military. As I have enumerated in the past, there is a slew of inexpensive, easily available, and perfectly serviceable GPS receivers, that can be straightforwardly integrated into your embedded application, via USB, serial port, or even wirelessly via Bluetooth. In this article, I'll reiterate the units I've found the most useful, and why, and the tools I've installed or developed to make use of them.

Hardware

GlobalSat BU-353S4

USGlobalSat BU-353S4

The best thing about the BU-353S4 is that it's easily available: US$30 and change from Amazon.com, a few bucks more for two day shipping if you're really desperate. It uses the well regarded SiRF Star IV GPS chipset, has the ubiquitous Prolific chip as its serial-to-USB converter, runs at a modest 4800 baud (useable with the finicky real-time GPS feature of Google Earth Pro), and provides a position update once every second. It has forty-eight radio channels, but only one RF stage, so it only receives GPS (versus receiving both the U.S. GPS and the Russian GLONASS constellations).

If it weren't for the special features of the other receivers I'll describe below, the BU-353S4 might be the only GPS receiver I'd ever need. There is a similar model that reports five times a second, but you're going to pay significantly more for something you probably don't need unless, maybe, you are using it in an aircraft.

(Update 2018-10-18: I've switched to the GlobalSat BU-353W10, and I suggest you do too; see below.)

NaviSys Technology GR-701W

NaviSys Technology GR-701W

The key feature of the GR-701W that is rare amongst inexpensive GPS receivers is that it exports a one pulse per second (1PPS) timing signal via the Data Carrier Detect (DCD) line that is visible to software even over the USB interface. The 1PPS signal is syntonized to the GPS timing signal that is in turn syntonized to the network of atomic clocks in the Global Positioning System. While the USB interface jitters the 1PPS a bit, you can still build a completely serviceable GPS-disiplined stratum-1 Network Time Protocol (NTP) micro-server using not much more than the GR-701W, a Raspberry Pi, and some open source software.

For just geolocation applications, you can ignore the 1PPS, and you have a GPS receiver that is based on the excellent Swiss-made U-blox 7 chipset, also uses the Prolific serial-to-USB converter, runs at 9600 baud, and delivers an update once per second. The receiver has fifty-six radio channels but still just one RF stage.

I have ordered my GR-701W units for US$50 from a seller on Etsy who, as it turns out, is the project manager for the open source NTPsec project; I've used the NTPsec NTP daemon in a number of projects, including my own Cesium atomic clock.

TOPGNSS GN-803G

TOPGNSS GN-803G

I keep a GN-803G in my geolocation kit because it is the first relatively inexpensive USB GPS receiver I found that has multiple RF stages, so it receives and processes signals from both the U.S. GPS constellation and the Russian GLONASS constellation simultaneously. In fact, it computes an ensemble fix, using a mixture of satellites from both constellations, which should allow it to exploit the dynamic orbital geometry of both systems to maximize accuracy by minimizing the Dilution Of Precision (DOP), a measure of accuracy based on the spatial separation of the satellites: broader separation, resulting in lower DOP values, is better.

The GN-803G uses the advanced U-Blox 8 chipset, which natively provides a USB interface, runs at 9600 baud, and updates by default once per second. Like the U-blox 7 chipset used by the GR-701W above, the U-Blox 8 chipset supports the proprietary binary UBX protocol in addition to the standard ASCII NMEA protocol that is ubiquitous among GPS receivers. I have used my own tools to send UBX packets to the GR-701W to enable it to generate periodic UBX packets containing much more detailed information than is available via NMEA. This alone makes the GN-803G of interest to geolocation and precision timing experimenters.

The downside is that I have only found the GN-803G on eBay, shipping from China, albeit for a paltry US$25; it can take a while to get one. I've recently discovered the GlobalSat BU-353W10 - US$45 from Amazon.com - that, like the GN-803G, uses the U-Blox 8 chipset; I'll find out shortly whether it's a usable alternative to the GN-803G.

(Update 2018-10-18: I did, and it is; see below.)
N.B. I do have a twinge of concern from time to time about ordering a USB device from who-knows-where and plugging it into one of my computers. I tend to first plug them into a Raspberry Pi and then carefully watch the system log.
Garmin GLO

Garmin GLO Bluetooth GPS Receiver

I include the Garmin GLO - a battery-operated GPS receiver that connects via Bluetooth - because it solves a problem that the USB-based receivers do not: I can easily use it with my Pixel C tablet. Most smart mobile devices come by GPS because of their cellular chipsets; WiFi-only devices like my Pixel C need a little help. Connecting the GLO, or any Bluetooth GPS receiver, to the Pixel C requires not just Bluetooth, but a Bluetooth GPS Android application that receives the NMEA sentences from the receiver wirelessly and forwards them via an internal "mock GPS" interface.

Garmin is pretty close mouthed about the chipset the GLO uses. But the device updates ten times per second, making it useful for speed daemons (and, I gather, private pilots). The GLO can be had from Amazon.com for about US$100.

Update 2022-11-02: The Garmin website suggests the newer GLO 2 - which is rumored to differ from the GLO only by its longer battery life - uses a MediaTek or MTK chipset. Also, both the GLO and GLO 2 are documented to receive both signals from the GPS (U.S.) and GLONASS (Russian) constellations, but my GLO and both of my GLO 2 units only emit NMEA sentences with the talker field set to "GP", indicating just GPS.

GlobalSat BU-353W10 (added 2018-12-18)

GlobalSAT BU-353W10

This is the USB-connected GPS device I'm using for all of my own geolocation software development now. It's easily found on Amazon.com for a mere US$40. Which is a paltry sum considering all you can do with its U-Blox 8 receiver. The box implies that it's specific to Windows 10, but it worked trivially with my own software on Ubuntu and Raspbian Linux. I've extended my own software to handle not just the usual NMEA sentences but also the proprietary binary UBX messages supposed by U-Blox devices. The amount of capability in this device, specifically in the U-Blox 8 chipset, is truly impressive.

Software

GPSd

The GPS daemon, a standard package available in all the usual Linux distributions like those based on Debian, includes not just software that reads and interprets NMEA sentences from multiple GPS devices concurrently, but a bunch of useful tools including both command-line and window-based clients. A snapshot of the xgps client is shown below.

gpsd client xgps

I've used GPSd in all of my GPS-disciplined timepieces, in conjunction with the NTPsec NTP daemon. It would be my go-to tool in any Linux-based production system needing geolocation or precision timing. I've never had to write my own client to the daemon (the NTPsec NTPd has a built-in interface), but I don't expect it would be hard to do so.

Lady Heather

Lady Heather is an open source software package used to monitor and evaluate GPS-disciplined frequency standards - that is, precision clocks that are disciplined to GPS time by a GPS receiver. It includes a flexible interface with a real-time display that provides a wealth of information - more than I currently understand - about the GPS receiver under test (but it sure is awesome to watch).

Untitled

Of particular interest above is the map in the lower right that shows the positions over time of satellites used in the position fix. The large dark area at the top of the map is in the direction of the inside of my office. The rest of the map indicates satellites received through my office window. The other small dark spots suggest the position of obstructions like trees and buildings outside my office that block reception of satellites low on the horizon. I have found this map useful for GPS antenna placement.

I first used Lady Heather to test my NTP server based on a Chip-Scale Atomic Clock (CSAC). I've since stood up a Raspberry Pi with an LCD display and a GR-701W that sits on my desk, which uses Lady Heather to monitor the Global Positioning System, plus a script that uses tools in NTPsec to keep track of all six NTP servers running on my local network and compare them to the UTC(NIST) time that an ensemble of NTP servers at the U.S. National Institute of Standards and Technology are emitting.

("Lady Heather" is apparently a dominatrix that is a recurring character on the television series CSI: Crime Scene Investigation that takes place in Las Vegas. I've never watched CSI. I've been to Las Vegas many times, but have never checked out the CSI "ride" I've noticed at the MGM Grand resort. Maybe I'm missing something. Maybe next trip.)

Hazer

Hazer, and an underlying library Diminuto, are my own C-based software tools that I've used to test and evaluate GPS receivers. I am fond of saying that I can only learn by doing. So when I wanted to really understand the stuff being emitted by GPS receivers and how to make use of it, I ended up writing my own code to deal with it. The result has turned out to be a useful toolkit.

Hazer is a library of functions that parse NMEA sentences and UBX packets. Because it was intended for embedded systems, it only uses library functions that are typically part of the standard C library (although I have only used it on Linux systems, so exactly how portable Hazer might actually be is open to debate). The Hazer distribution includes a suite of unit and functional tests, some of which make use of less typical Linux capabilities; these depend on my Diminuto library of Linux systems programming functions. Most of the functional tests make use of Hazer's gpstool, a sort of Swiss Army Knife for the Hazer library.

Here is a screen snapshot of gpstool running against a GN-803G.

GN803G and Hazer 8.0.0

The tool emits the latest NMEA sentence or UBX packet received from the device, the most recent sentence or packet transmitted to the device, the time and position information received from the device, and information about what satellites in which constellation were used to generate the solution, the quality of the solution, and information about each individual satellite currently being received (whether it contributed to the fix or not).

Each line has associated with it a timer that indicates when the information will expire and that is reset whenever the data associated with that line is updated; in this example I used a command line option to set the lifetime to ten seconds. This is done because although NMEA does a good job telling you what it is receiving, it isn't always good about telling you when it is no longer receiving something - for example, if the satellite lock is lost - which would place the current solution in doubt.

Each line also indicates from which satellite constellation that data was derived: GPS for the U.S. system, GLONASS for the Russian system, and GNSS (for Global Navigation Satellite System, the generic term for this capability) for an ensemble solution that includes data from more than one system.

gpstool can output data in a sequential log format, but the example above uses ANSI escape sequences to display data that is updated dynamically in a full screen format. It's a lot simpler than it sounds; the tool mostly uses some simple sequences to position the curser, erase the entire screen from there to the end, and then rewrite that entire part of the screen all at once. Thanks to a fast screen display, a persistence of vision effect, and some careful output formatting on my part, individual fields appears to update dynamically. Here is a video of about a minute of gpstool running in full screen mode.



I have found Hazer and gpstool useful for testing and evaluating GPS devices. I have also used it to integrate GPS devices in real-time with tools like Google Earth. For an example much simpler than the one I just cited, the second pair of numbers in the position line of gpstool

POS 39*47'39.07"N, 105*09'12.27"W   39.794186, -105.153411

has latitude and longitude in a decimal degree format that can be cut and pasted directly into either Google Earth or Google Maps.

Hazer has also been instrumental in my understanding how devices like the GR-803G compute and report ensemble fixes. For example, when the GR-803G reports active satellites for an ensemble fix, it emits two GSA sentences, both with the "talker" specified not as GPS or GLONASS but as the generic GNSS. This is ambiguous as to whether the satellites in both messages were used together to compute a position solution, or whether the second GSA message is an update/replacement to the first GSA message. It turns out it's the former. The satellites in each GSA message are all either GPS and WAAS satellites, or all GLONASS and WAAS satellites. Later versions of NMEA include an additional GSA field resolve this ambiguity. But on the GR-803G, Hazer infers this just from the satellite identifiers.

WAAS, for Wide Area Augmentation System, is a system devised by the U. S. Federal Aviation Administration to transmit additional corrective geolocation information from geosynchronous satellites like Inmarsat, based on measurements performed at fixed terrestrial GPS receivers at precisely known locations. Its purpose is to improve the accuracy of position fixes for commercial aircraft. This allowed the FAA to narrow the separation of "air lanes" used in commercial aviation in the United States, increasing the density of air traffic, and to provide accurate enough position fixes to be useful in take-off and landing.

WAAS is an example of a Satellite Based Augmentation System (SBAS). Many of the latest GPS chipsets are capable of receiving SBAS corrections from one or more systems. (Not too long ago on one flight, I happened to see a jet airliner zip by in the opposite direction so close I could almost see inside the cabin windows. I suddenly had a visceral appreciation for precision satellite navigation.)

I have tested Hazer with all the GPS devices I cited above, and many more.

Excuses

You haz none. GPS receivers are available in a broad range of prices, capabilities, and hardware interfaces. There are all sorts of open source software packages available to make using them easy. Get your geolocation groove on.