ESP32 Bibliothek zum Offline-Suchen der Zeitzone für gegebene GPS Koordinaten

In einem Artikel vor drei Monaten habe ich beschrieben, wie man anhand von GPS Koordinaten die Zeitzone bestimmen kann und damit auch die korrekte Uhrzeit setzen kann. Inzwischen arbeite ich aber kaum mehr mit dem Raspberry, sondern verwende für meine Projekte einen ESP32 Mikrocontroller. Mit dem Raspberry ist das recht leicht, da es eine fertige Bibliothek dafür gibt. Leider habe ich nichts Vergleichbares für den ESP32 gefunden. Daher musste ich mir meine eigene Bibliothek schreiben, die ich hier vorstellen möchte.

Die Problemstellung

Speziell im Mikrocontroller Bereich kann es vorkommen, dass man die genaue Uhrzeit benötigt, ohne eine Möglichkeit, diese per Eingabe oder Netzwerk zu bekommen. Eine einfache Option ist das GPS Signal, mit dem nicht nur die Position ermittelt werden kann, sondern auch die genaue Uhrzeit übertragen wird. Allerdings handelt es sich dabei um die UTC Zeit. Um die lokale Uhrzeit zu bestimmen, wird die Zeitzone benötigt, in der man sich befindet. Damit erhält man die Zeitverschiebung zur UTC Zeit inklusive den lokalen Regeln für die Sommerzeit.

Dieses Bild von Wikipedia gibt einen Überblick über die weltweiten Zeitzonen:

Für eine allgemeine Lösung braucht man also die Umrisse aller Länder und den zugehörigen Namen der Zeitzone. Über die GPS Koordinaten lässt sich dann das Land bestimmen und folglich die Zeitzone. 

Die Zeitzonen Datenbank

Glücklicherweise existiert schon eine Zeitzonen-Datenbank. Evan Siroky hat das Tool timezone-boundary-builder entwickelt, das basierend auf den Daten von OpenStreetMap eine Datenbank generiert, in der alle Länder der Erde als Polygone abgelegt sind. Die aktuelle Version kann man von GitHub herunterladen. Die Datenbank basiert auf dem Shapefile Format und ist ca. 100 MB groß. Für einen Mikrocontroller ist das eine beachtliche Größe. Es gäbe zwar die Option, die Datenbank auf einer SD-Karte zu speichern, aber dann bräuchte ich immer noch eine Software, um mit dem Mikrocontroller das Shapefile Format lesen zu können. 

Ich habe mich daher für eine andere Variante entschieden. Mein Ziel war es, die Datenbank so weit zu komprimieren, dass sie auf einen 128 MBit W25Q128 SPI Flash Chip passt. Außerdem sollte das Datenbank Format so simpel wie möglich sein, damit sich der Programmieraufwand für den ESP32 in Grenzen hält. 

Die Generierung der Zeitzonen Datenbank übernimmt ein Java Programm. Für das Lesen des Shapefiles verwende ich eine Open Source Bibliothek von GeoTools. Die Komprimierung der Daten ist sehr einfach gehalten, aber es reicht aus, die Daten auf unter 16 MB zu bringen. Dazu eine kleine Statistik der Daten:

Die eigentliche Kompression besteht aus mehreren Teilen

1. Eine Koordinate besteht aus Längen- und Breitengrad im Fließkommaformat. Diese Koordinaten werden mit einer Funktion in eine ganze Zahl konvertiert, wobei über einen Parameter festgelegt werden kann, wie viele Bits diese Zahl haben soll. Das entspricht einer Rundung auf eine bestimmte Anzahl von Nachkommastellen.
2. Durch die Rundung kann es sein, dass aufeinanderfolgende Koordinaten den gleichen Wert haben. Diese Koordinaten werden ignoriert.
3. Der exakte Wert einer Koordinate muss nur für den ersten Wert eines Polygons gespeichert werden. Bei den übrigen Werten genügt das Delta zum vorherigen Wert.
4. Die Beträge der Deltas sind deutlich kleiner als die ursprünglichen Koordinaten. Zum Speichern werden nur so viele Bytes verwendet, wie der Wert tatsächlich braucht. Die Verteilung der Deltas sieht folgendermaßen aus:

   x < 256	10.460.006
   256 <= x < 65536	1.619.509
   x >= 65536	1095

   Entsprechend den Beträgen reicht es also aus, jeweils nur ein Byte, zwei Bytes oder 4 Bytes zu verwenden. 

Mit diesen einfachen Maßnahmen schrumpft die Größe der Datenbank auf 15,4 MB und passt somit problemlos auf den Flash Chip.

Die Struktur der Datenbank ist darauf optimiert, vom Mikrocontroller sehr einfach und ohne großen Speicherbedarf gelesen werden zu können:

Die Zeitzonen sind der Größe nach sortiert. Dadurch werden auch solche Fälle korrekt gefunden, wo ein Land innerhalb eines anderen Landes liegt. Ein Beispiel ist der Vatikan, der innerhalb Italiens liegt. Eine entsprechende Koordinate würde dann zwei Länder liefern. Da aber der Vatikan vor Italien einsortiert ist, wird dieser auch zuerst gefunden. 

Vor der Erstellung der Datenbank muss das Shapefile heruntergeladen werden. Dies geschieht mit dem Maven Goal download:wget. Danach muss nur noch die Hauptklasse gestartet werden. Die Ausgabedatei wird im Zielverzeichnis unter target/classes/output/ gespeichert.

Der Source Code des Generators ist auf GitHub: https://github.com/HarryVienna/ESP32-Timezone-Database-Generator

ESP32 Komponente

Hardware

Die Daten mit den Zeitzonen sind zu groß, um direkt auf dem ESP32 Modul gespeichert werden zu können. Daher werden die Daten auf einem externen Winbond W25Q128 SPI Flash Chip gespeichert, der mit dem SPI3 (auch VSPI genannt) Controller des ESP32 verbunden ist. 

Die generierte Datenbank wird mit diesem Kommando auf den Flash Chip gespeichert:

esptool.py --chip esp32 write_flash --flash_mode dio --spi-connection 18,19,23,21,5 0x0000 timezones.bin

Dieser Vorgang kann einige Minuten dauern. Sollte nur ein 64 MBit Flash Chip zur Verfügung stehen, kann man den Precision Parameter im Generator zu reduzieren. Bei einem Wert von 18 ist die erzeugte Datei nur noch 7,5 MB groß. Natürlich ist dann die Genauigkeit der Daten nicht mehr so hoch.  

Software

Um auf den Flash Chip zugreifen zu können, muss zunächst die SPI Schnittstelle initialisiert und eine Partition eingerichtet werden. Das API wird auf der Espressif Website sehr gut beschrieben. Der Code dazu schaut folgendermaßen aus:

const spi_bus_config_t bus_config = {
        .mosi_io_num = w25q128->config.mosi_io_num,
        .miso_io_num = w25q128->config.miso_io_num,
        .sclk_io_num = w25q128->config.sclk_io_num,
        .quadwp_io_num = -1,
        .quadhd_io_num = -1,
    };

    const esp_flash_spi_device_config_t device_config = {
        .host_id =  w25q128->config.host_id,
        .cs_id = 0,
        .cs_io_num = w25q128->config.cs_io_num,
        .io_mode = w25q128->config.io_mode,
        .speed = w25q128->config.speed
    };

    // Initialize the SPI bus
    ret = spi_bus_initialize(SPI3_HOST, &bus_config, SPI_DMA_CH_AUTO);
    if (ret != ESP_OK) {
        ESP_LOGE(TAG, "Failed to initialize SPI bus: %s (0x%x)", esp_err_to_name(ret), ret);
        return ret;
    }

    // Add device to the SPI bus
    esp_flash_t* ext_flash;
    ret = spi_bus_add_flash_device(&ext_flash, &device_config);
    if (ret != ESP_OK) {
        ESP_LOGE(TAG, "Failed to add Flash: %s (0x%x)", esp_err_to_name(ret), ret);
        return ret;
    }

    // Probe the Flash chip and initialize it
    ret = esp_flash_init(ext_flash);
    if (ret != ESP_OK) {
        ESP_LOGE(TAG, "Failed to initialize external Flash: %s (0x%x)", esp_err_to_name(ret), ret);
        return ret;
    }

    // Print out the ID and size
    uint32_t id;
    ret = esp_flash_read_id(ext_flash, &id);
    if (ret != ESP_OK) {
        ESP_LOGE(TAG, "Failed to read id: %s (0x%x)", esp_err_to_name(ret), ret);
        return ret;
    }
    ESP_LOGI(TAG, "Initialized external Flash, size=%d KB, ID=0x%x", ext_flash->size / 1024, id);

    const char *partition_label = "storage";
    ESP_LOGI(TAG, "Adding external Flash as a partition, label=\"%s\", size=%d KB", partition_label, ext_flash->size / 1024);

    ret = esp_partition_register_external(ext_flash, 0, ext_flash->size, partition_label, ESP_PARTITION_TYPE_DATA, ESP_PARTITION_SUBTYPE_DATA_FAT, &w25q128->partition);
     if (ret != ESP_OK) {
        ESP_LOGE(TAG, "Failed to register external partition: %s (0x%x)", esp_err_to_name(ret), ret);
        return ret;
    }

Über den Zeiger auf die Partition kann jetzt auf die Daten des Flash Chips zugegriffen werden. Die wichtigste Funktion dafür ist

esp_err_t esp_partition_read(const esp_partition_t* partition, size_t src_offset, void* dst, size_t size);

Zum Suchen der Zeitzone wird die Struktur der Datenbank gelesen und Land für Land durchsucht. Um die Geschwindigkeit zu erhöhen, ist für jedes Land ein Rechteck mit den minimalen und maximalen Werten der Längen- und Breitengrade gespeichert. Liegt der Punkt nicht innerhalb dieses Rechtecks, kann gleich mit dem nächsten Land weitergemacht werden. Die Kernfunktion bildet die sogenannte Strahl-Methode, mit der man feststellen kann, ob ein Punkt in einem Polygon liegt. Da diese Funktion die Daten rein sequentiell abarbeitet, ist der RAM-Bedarf der Funktion sehr gering und somit kein Problem für einen Mikrocontroller.

p1.latitude = start_point.latitude;
p1.longitude = start_point.longitude;

p2.latitude = start_point.latitude;
p2.longitude = start_point.longitude;

double x_inters;
bool odd = false;

for (int k = 0; k < deltas; k++) {
    p2.latitude += next_value(partition, &shape_position);
    p2.longitude += next_value(partition, &shape_position);

    // y muss zwischen min und max der Linie sein
    if (latitude_int > MIN(p1.latitude, p2.latitude) && latitude_int <= MAX(p1.latitude, p2.latitude)) {
        // x muss kleiner gleich dem großeren x Wert der Linie sein
        if (longitude_int <= MAX(p1.longitude, p2.longitude)) {
            // Horizontale Linie wird ignoriert da schon beim Endpunkt einer anderen Linie gezählt
            if (p1.latitude != p2.latitude) {
                // Geradengleichung nach x aufgelöst  
                x_inters = (latitude_int-p1.latitude) * (p2.longitude-p1.longitude) / (p2.latitude-p1.latitude) + p1.longitude;
                if (longitude_int <= x_inters) {
                    odd = !odd;
                }
            }
        }

    }
    p1 = p2;
}

return odd;

Eine Ausgabe der Suchfunktion sieht beispielsweise für eine Koordinate in Österreich folgendermaßen aus:

I (9567) w25q128: Timezone Database info: Version: 1   Signature: TZDB   Precision: 24   Creation Date 2022-01-13
I (9572) w25q128: Search Latitude: 47.497700 4427106
I (9578) w25q128:        Longitude: 9.947400 463582
I (9583) w25q128: Entries in TOC: 426
I (9595) w25q128: Inside Bounding Box
I (11259) w25q128: Inside Bounding Box
I (11499) w25q128: Crossed line P1: 47.497696 10.870113   P2: 47.497650 10.870092
I (11980) w25q128: Crossed line P1: 47.497597 11.412392   P2: 47.497715 11.412327
I (12406) w25q128: Crossed line P1: 47.498562 12.906361   P2: 47.496944 12.908721
I (12425) w25q128: Crossed line P1: 47.496418 13.048067   P2: 47.498146 13.048282
I (14309) w25q128: Crossed line P1: 47.497757 16.653557   P2: 47.496845 16.653986
I (17213) w25q128: Crossed line P1: 47.497715 9.988052   P2: 47.497051 9.988675
I (17586) w25q128: Crossed line P1: 47.497555 10.434566   P2: 47.497986 10.434458
I (17601) w25q128: Inside timezone: Europe/Vienna
I (17601) test: 8034.229000 milliseconds

Der komplette Source Code dieser Komponente zum Bestimmen der Zeitzone befindet sich auf GitHub: https://github.com/HarryVienna/ESP32-Timezone-Finder-Component.

Performance

Die Geschwindigkeit der Suche hängt vor allem von der Anzahl der Punkte des jeweiligen Landes ab. Bei meinen Tests liegen die Werte zwischen 47 ms und 8000 ms. Die Datenbank hatte dabei eine Genauigkeit von 24 Bit. Reduziert man die Genauigkeit, erhöht sich natürlich auch die Geschwindigkeit. 

Ein interessantes Detail zu der Anzahl der Punkte pro Land ist noch, welches Land die meisten Punkte hat. Ich hätte hier auf eines der ganz großen Länder wie China, Russland oder die USA getippt. Tatsächlich ist es aber Deutschland mit über 150.000 Punkten. Ob das etwas mit der Gründlichkeit der Deutschen zu tun hat, kann ich aber nicht sagen :)