Low power mesh networking for small sensor grids

This project is dead.

The nrf24 used to be a cheap way to add a disappointing radio to your project, but its reign is long over.

Now you can buy a complete, FCC certified, bluetooth system on module - including a powerful arm processor with a floating point unit - from a reputable distributor - for less than $6. I've tried The BGM113 from silabs at mouser, and there are even cheaper Nordic modules. The whole system for less than you could put together a nrf24 + processor.

Plop that down on a PCB and go.

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.

This project is written in embedded C++11, using prepackaged algorithms to build an efficient key/value store with a pleasingly small amount of code. Frustratingly I know how to write working C++ but I don't know how to make it beautiful, with brute force stacking of pointers, parens and references everywhere to coax the necessary type out of each expression, until the compiler is happy.

auto element = reinterpret_cast<Contained *>(malloc(packet->len));
trickle_timer_reset(&(element->trickle), time_now);
memcpy(&(element->payload), packet, packet->len);
consistent(&((*existing)->payload), packet);

My point of comparison is the stm32plus library https://github.com/andysworkshop/stm32plus, mostly templates, which makes the stm32 much easier to program. Sure, you may have to stare at it for an hour to figure out how the recursive variadic template inherits from itself but it is written with a purpose and clarity that I have yet to find in my own C++.

I usually program in Python but I love the completely different challenge of programming for these tiny microcontrollers where every byte matters.

I've added some code to work on the MAC (media access control) protocol, linked from the project page. The purpose of the MAC is to keep track of when the radio should listen or transmit. The implementation is a very simple state machine that takes a single tick(time) event and transitions between states for idle, tx, and rx. We send commands to the radio when entering and leaving states, and can easily avoid trying to transmit when we should be receiving and vice versa.

The state machine is based on this popular C++ implementation by David Lafreniere.

I've added a link to the mesh source code so far and to the board files. To validate the idea, I've wrapped the Open Mesh implementation of the trickle algorithm in Python and have written a rudimentary event queue based network simulator. The network simulator shows how values travel between nodes over time. They do indeed hop from node to node and eventually become synchronized everywhere.

The case I was most interested in understanding is what will happen when the network is 'full', that is, when nodes cannot hold all the values that are currently being transmitted through the network. When this happens, a 'full' node might rapidly retransmit every new item it receives, wasting power; it could choose to forget newer values, or older values, or random values. The right choice will be a tradeoff between reachability and power consumption. The best option I've found so far seems to be to slow down the retransmission rate of every value on the node when a new value would take it over capacity. It might be possible to transmit more data than an individual node can hold at once by spreading the load out over time.

It will be important to handle a full network gracefully, but recall that the network is not likely to be full before you have a couple dozen nodes. If that happens you would want to partition the network into multiple separate meshes.

The second part of the source is a re-orderable priority queue plus key / value lookup data structure. The mesh network is always checking for the next expired message (values are retransmitted on timeout) and must be able to change their priority when it hears the same value on the network. The priority queue makes it very efficient to find the next item to retransmit, but normally does not allow re-ordering. Our priority queue maintains a sorted list of keys, for quick, memory efficient binary search to compare against incoming values, and maintains backlinks from the keys to their position in the priority queue. Combined we can efficiently search for values by key, change their priority, and update their position in the priority queue.

I've also been able to make a memory improvement to the OpenMesh trickle structure. The timeouts are always (minimum_timeout * (2**n)). The original code uses 13 bytes to store an instance of the trickle algorithm, storing (2**n) in a uint32_t, but we save 3 bytes per trickle by only storing n in a uint8_t.

The source repository also includes the Kicad board files for the pictured node.

This board features both Micro-USB and JST-PH power connectors, depending on whether you want to use a battery, but you must not connect them both at the same time. The through-hole JST-PH connector is also more firmly attached to the board than the Micro-USB. In an attempt to be compatible with Adafruit batteries, the ground pin is on the right when looking into the right-angle header.

These connectors and the larger JST-XH connectors are very popular but were a bit of a mystery. You buy them directly from JST. They are cheap. A couple of weeks later you have a little box of plastic and metal pieces. To make a connection you need the matching header, housing, and contacts. The header goes on the board, the contacts are crimped onto your wires, and clip permanently into the housing. You cannot make a proper crimp with pliers; you need a crimping tool. You can buy one from JST for about $489.89 but I bought this one. However you might want to look for one that is also compatible with slightly larger connectors.

Happily it appears that since the last time I looked JST's connectors are also available on Digikey. It's worth having a box or two of these around for whenever you need to make a wire to board connection.

This board has a nifty little RGB LED called the Cree CLV1A. It's a 4-pin SMD part in what's called a 4-PLCC package. It looks like they are designed for video walls, but they also make great little indicators. The main problem is that they are way too bright at 20mA. On a previous project I used a small square of coroplast (plastic cardboard) as a diffuser to avoid blinding myself, lately I just put in much higher value (e.g. 180 Ohm) resistors.

The other problem with the CLV1A is that they are a bit expensive. The next board design will probably spec in several individual SMD LEDs, available in bulk for next to nothing.

The pictured board is my third attempt to assemble a working unit. After the first one didn't work, I got discouraged for quite some time. The second board was coming along nicely, but an overzealous application of a heat gun formed a bubble in the solder mask, lifting the parts off in a wave. It probably doesn't work. Then the third one was gently assembled with a more relaxed 325 degree iron temperature, first with the MCU rotated 90 degrees, second with it placed correctly, and now it is working great.

Lessons learned include putting the largest orientation marker you can afford on the soldermask layer of your footprints. Also, it took a long time to get the programmer working correctly. It's still possible that board #1 actually works, just the programmer wasn't able to connect.