Close

The Beginnings of an API

A project log for Low power mesh networking for small sensor grids

Tiny MQTT-interoperable broadcast mesh networking with simple radios

DanielDaniel 06/10/2017 at 14:260 Comments

The core of this project, the inelegant C++ as mentioned, is a heap priority queue linked with a sorted list of key-values and trickle algorithm instances. The key-value pairs point back to the corresponding position in the heap, so that once you have used binary search to find the key you can update its priority without having to do a linear search through the heap. It is easy to have either a heap or a sorted list, but a bit fiddly to link the two together. You must make sure that every time you update one data structure you also update the other.

The reason these data structures are useful is because every time you receive a packet, you must look it up in the list, and every time the clock ticks, you must check to see which key has the lowest priority. With a heap the most common operation is O(1), just heap_array[0].get_priority().

All of this will be invisible to the implementor. The API will be, just ask the radio if it got a packet, feed the packet to the mesh stack along with the current time (number of clock ticks since start), and ask the mesh stack if there is anything to transmit.

Discussions