Experiments with mesh networks

I’ve started building a mesh network in C++, it’s a small library intended for use on Raspberry Pi and Arduino. Currently I want to support one kind of radio, an NRF24L01+ which you can get pretty cheap on ebay.

These radios provide us with a Layer 1 (Physical) of a OSI network but to build a functional mesh network we need a Layer 2 (Data link, addressing) and Layer 3 (Packets), once we have those two layers we need a Layer 4 (Segments, connection management) then onto the final layer, Layer 5 (Data).

I’m stopping at layer 5 this far because those are the 5 layers needed for a mesh network to work. The mesh needs only to facilitate the communication between two hosts on the mesh. In order to do that the mesh will have some basic described functions.

  • A packet must have an intended source and destination
  • A packet must be relayable by any node in the mesh
  • A message must be fragmentable into many packets within reason of the memory available on a device (Arduino has very little memory)
  • Each packet sent must have an acknowledgement so we know that it has been received.
  • Each node must be able to scan other nodes and receive information regarding which nodes can be heard, even recursively.
  • Packets will retain only the last hop in their journey thus limiting the amount of replay.
  • Collisions should be avoided where possible.
  • The mesh must be able to survive unreachable nodes and be able to report their unreachable status.
  • We’re going to make it difficult to inject packets into the stream by using sequence numbers to limit the predictability and therefore validity of packets in a sequence.
  • The API provided will allow a user to build on top of it as a form of read/write pipeline of some kind. (Layer 6 & 7)

The initial goals of the mesh network is to be able to have a small 50mm square device which is connected to a network of wireless nodes. I’ll likely want to build 10-20 of these nodes. Two of which will be Raspberry Pi’s.

Data from each of these nodes and actions performed with each node will be managed by a web service which provides an interface for us with mobile devices and web browsers.

Hardware Wiring

circuit

Packet design

We want to keep the packet design to a minimum, the intention should be to have a small simple packet which can be quickly error checked and processed. We’re going to use sequence numbers which will increment in some predictable way to ensure that the fragments are aligned and injection of rogue packets is more difficult. We’re using a simple 16bit addressing system and limiting the size of the packets/messages to 1 byte for size and fragment counts.

Packet

figure 1: A Simple Packet

Lets look at these items individually

  • Source Address – The 16 bit address of the device sending the packet.
  • Destination Address – The 16 bit address of the device receiving the packet.
  • Hop – The 16 bit address of the last system to relay the packet, this is used as the jumping off point of the return path. Hop can be set to the destination address in order to prevent relaying, and set to zero in order to request open relaying.
  • Size – The size of the packet (bytes) including header.
  • Packet Type – The type of packet, connection negotiation, ping, scan etc…
  • Sequence & Response – The sequence and response are maintained using a counter and an initial random number which means that only the two systems involved in the communication will easily be able to insert packets into the network directed toward each other. This is not intended as a security measure, only as a mechanism to make it more difficult to inject rogue packets and to allow the mesh to easily maintain connections without using much memory.
  • CRC16 – Cyclic Redundancy Check 16bit, the CRC is generated by setting CRC16, Hop, Hops and Attempts to zero when these bytes are in the zero state the packet can be summed and the sum inserted before transmission.
  • Fragment & Fragments – Only required for packets which have data, and the data exceeds 239 bytes, the packet will be broken down into a maximum of 255 fragments and each fragment numbered for reassembly on the far side.
  • Attempts – The attempts counter.
  • Hops – The hop counter

I’ve considered the merits of maintaining an internal routing table for each node, knowing in which direction each address is reachable via a tree of addresses but this will take up far too much memory on an Arduino, in fact, more than two or three active connections will likely kill the Arduino program until I get some better allocation management in place. The other option was to retain an entire list of hop addresses in the packet, but you will quickly run out of memory.

By limiting to the first degree of separation the hop address can relay the packet in the right direction which is likely to create a win in the routing regardless of other rebroadcasts of the packet. The hop will initially be set to zero unless the destination is directly accessible from source and the return packet will define the hop, therefore the system will have already chosen the best route.

The other option is to retain a stack of hops which is limited in size and has a pairing of some kind e.g. for address a hop through relay b. However we only maintain that list up to about 32 devices which is 128 bytes in memory minimum. I will explore these avenues if I have routing issues or lots of replay traffic.

Code Listing: Packet Structure

typedef uint16_t twobytes;

typedef enum PacketTypes {
 PACKET_TYPE_SYN,
 PACKET_TYPE_ACK,
 PACKET_TYPE_CMD,
 PACKET_TYPE_RSP,
 PACKET_TYPE_FIN,
 PACKET_TYPE_PING,
 PACKET_TYPE_PONG,
 PACKET_TYPE_SCAN,
 PACKET_TYPE_RSCAN,
 PACKET_TYPE_LAST
} PacketType;

typedef struct Packet_ {
  twobytes src;
  twobytes dst;
  twobytes hop; 
  byte     size;
  byte     type;
  byte     sequence;
  byte     response;
  twobytes crc;
  byte     fragment;
  byte     fragments;
  byte     attempt;
  byte     hops;
  byte     data[];
} Packet;

#define NETWORK_KEY 0xAE

// Simple sequence number generation
byte nextSequence(byte value, int packet_number) {
  if (packet_number == 0) return random(255);
  return (value + packet_number) ^ NETWORK_KEY;
}
// Allocate a new packet
struct Packet_ *NewPacket(byte datasize) {
  Packet *p = (Packet *)malloc(sizeof(Packet) + datasize);
  // Zero all bytes
  int i;
  for (i = 0; i < sizeof(Packet) + datasize; i++) {
    byte *b = (byte *) p + i;
    *b = 0; 
  }
  p->size = sizeof(Packet) + datasize;
  return p;
}

// Release the memory for packet
void ReleasePacket(struct Packet_ *packet) {
  free(packet);
}

// Print the contents of a packet as a series of hex bytes
void PrintPacket(struct Packet_ *packet) {
  int i;
  Serial.println("Packet ----");
  for (i = 0; i < sizeof(Packet); i++) {
    byte *b = (byte *) packet + i;
    Serial.print(*b, HEX);
    Serial.print(" "); 
    if (i % 2 == 1) {
      Serial.println();
    }
  }
  Serial.println("-----------");
}

Limitations

Messages are limited in size to packet size (239) * max fragments (255) which is 64k of data. That’s not entirely much but it is more than an Arduino will be able to allocate, which is where the further limitation comes in. As this has to run on an Arduino Mini Pro this limitation is currently intentional.

Addresses are limited to 65535 devices. Which is more than enough for us to get something working.

There’s no provision in the transport layer for assigning ports or running multiple services, that’s because we really don’t want to run multiple services on this hardware we just want to run a simple single application.

Arduino First Steps

First thing is to get the initial packet design implemented and working on Arduino, the platform isn’t as flexible in C++ terms as a modern computer so we’ll try our best to get a few packets to fit. For the first test we’re going to build the C++ code for Arduino and Raspberry Pi and test the Ping routines to see what’s happening. This is just a simple exchange of packets so it should work easily enough.

In order to achieve this quickly, I’m going to create a basic test application around a single Packet, the ping packet. On the Arduino I will construct a packet, and address it accordingly for the purposes of sending a ping. The packet will then be dumped to the Serial as bytes and sent via RF24.

On the Raspberry Pi I’ll receive the Packet and dump the bytes to the screen, I’ll then cast the packet into the structure, and send an appropriate response.

The test application will print out the time difference between the ping and pong.

Code Listing: Create Ping

#define THIS_DEVICE 42
#define FAR_DEVICE 69

struct Packet_ *CreatePing(int dst) {
  Packet *ping = NewPacket(0);
  ping->src = THIS_DEVICE;
  ping->dst = dst;
  ping->type = PACKET_TYPE_PING;
  ping->sequence = nextSequence(0,0);
  ping->attempt = 1;
  ping->fragment = 1;
  ping->fragments = 1;
  return ping;
}

struct Packet_ *CreatePong(struct Packet_ *ping) {
  // Don't respond to non-ping packets or packets that
  // are not broadcast pings (0) or addressed to us
  if (ping->type != PACKET_TYPE_PING) return NULL;
  if ((ping->dst != 0) && (ping->dst != THIS_DEVICE))
    return NULL;

  Packet *pong = NewPacket(0);
  pong->src = THIS_DEVICE;
  pong->dst = ping->src;
  pong->type = PACKET_TYPE_PONG;
  pong->response = nextSequence(ping->sequence, 1);
  pong->sequence = nextSequence(pong->response, 2);
  pong->attempt = 1;
  pong->fragment = 1;
  pong->fragments = 1;
  return pong;
}

Now we need to import our RF Library and hook it up so it can send and receive packets. We just want to send and receive packets at this point, we’re going to add more complicated features on top of this.

We’re going to use this library from Stanley Seow which is a couple of forks away from the original driver but includes support for Raspberry Pi.

Download and install the Arduino library, this is different on every platform but there’s documentation to help.

Code Listing: Setup and import

// Include all of the required library components
#include <SPI.h>
#include "nRF24L01.h"
#include "RF24.h"

// Set up the radio
RF24 radio(9,10);
const uint64_t pipes[2] = { 0xF0F0F0F0E1LL, 0xF0F0F0F0D2LL };

void setup() {
  Serial.begin(57600);
  radio.begin();
  radio.setRetries(15,15);
  radio.setAutoAck(1);
  radio.setPALevel(RF24_PA_MAX);
  radio.setChannel(0x4c);
  radio.setDataRate(RF24_2MBPS);
  radio.enableDynamicPayloads();
  radio.openWritingPipe(pipes[0]);
  radio.openReadingPipe(1,pipes[1]);
  radio.startListening();
}

Initial setup of the radio requires that we know which pins we’re plugging in to, in my case I’m using 9 and 10 as the control pins. Once we’ve configured the radio we put it into the listening mode by default. I had some trouble with the radio running at 1Mbps and 250Kbps the reliability was just not good enough with about 10% of the packets getting through. So it’s set here to 2Mbps, the other radio settings seem to work best in this scenario.

Code Listing: Receive Packet

#define PACKET_MAX_SIZE 255

struct Packet_ *ReadPacket() {
  if (!radio.available()) return NULL;
 
  byte hdr[255];
  bool done = false;
  while (!done) {
    done = radio.read(&hdr, 255);
    delay(10);
  }
 
  Packet *p = (Packet *)malloc(sizeof(Packet));
  memcpy(p, &hdr, sizeof(Packet));
 
  byte size = p->size;
  Packet *packet = (Packet *)malloc(size);
  free(p);
 
  memcpy(packet, &hdr, size);
  return packet;
}

Messing with memory a bit here but we should be alright. We’ll find out when things arrive at the Raspberry Pi end.

Code Listing: Send Packet

void SendPacket(struct Packet_ *p) {
  radio.stopListening();
  radio.write(p, p->size);
  radio.startListening();
}

Sending wasn’t so difficult, notice that we have to stop listening in order to send data.

Now we’re going to have a main loop which just constantly sends out pings and reads the responses.

Code Listing: Our main loop

int sent = 0, received = 0;
unsigned long ave = 0;
unsigned long last = 0;

void loop() {
  // Send a ping packet to FAR_DEVICE
  Packet *ping = CreatePing(FAR_DEVICE);
  unsigned long time = millis();
  SendPacket(ping);
  sent++;
  ReleasePacket(ping);

  // Sit in the read loop for a while awaiting a pong
  int i;
  for (i = 0; i < 50; i++) {
    Packet *p = ReadPacket();
    if (p != NULL) {
      unsigned long rcp = millis();
      time = rcp - time;
      ave = (ave + time + last) / 3;
      last = time;
      received++;
      ReleasePacket(p);
    }
    delay(2);
  }
  Serial.print("Packet count, sent: ");
  Serial.print(sent);
  Serial.print(", received: ");
  Serial.print(received);
  Serial.print(", Round trip time(ms): ");
  Serial.print(time);
  Serial.print(", average time(ms): ");
  Serial.print(ave);
  Serial.print(", loss (%): ");
  Serial.println(100.0f-(((float)received/(float)sent) * 100.0f));
}

Again on the Raspberry Pi

Now we’re going to write essentially the same program but this time on the Raspberry Pi. We’re going to make this program listen for pings and send a corresponding response pong packet, most of the code here is identical, but as this is just a first experiment it’s a good idea to keep things simple. I’ve built and installed the RF24 library for Raspberry Pi to build this code listing I just added the file pong.cpp to the examples folder inside of the Raspberry Pi driver ~/RF24/librf24-rpi/librf24/examples

I built and executed the code with the following commands in that folder

$ g++ -Wall -Ofast -mfpu=vfp -mfloat-abi=hard -march=armv6zk -mtune=arm1176jzf-s -L../librf24/  -lrf24 pong.cpp -o pong
$ sudo ./pong

Code Listing: Raspberry Pi Ping Responder

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <string>
#include <getopt.h>
#include <cstdlib>
#include <iostream>
#include "../RF24.h"
 
using namespace std;
RF24 radio("/dev/spidev0.0",8000000 , 25);  //spi device, speed and CSN,only CSN is NEEDED in RPI
const int role_pin = 7;
const uint64_t pipes[2] = { 0xF0F0F0F0E1LL, 0xF0F0F0F0D2LL };

typedef uint8_t byte;
typedef uint16_t twobytes;

typedef enum PacketTypes {
  PACKET_TYPE_SYN,
  PACKET_TYPE_ACK,
  PACKET_TYPE_CMD,
  PACKET_TYPE_RSP,
  PACKET_TYPE_FIN,
  PACKET_TYPE_PING,
  PACKET_TYPE_PONG,
  PACKET_TYPE_SCAN,
  PACKET_TYPE_RSCAN,
  PACKET_TYPE_LAST
} PacketType;

typedef struct Packet_ {
  twobytes   src;
  twobytes   dst;
  twobytes   hop; 
  byte  size;
  byte  type;
  byte  sequence;
  byte  response;
  twobytes   crc;
  byte  fragment;
  byte  fragments;
  byte  attempt;
  byte  hops;
  byte  data[];
} Packet;

#define NETWORK_KEY 0xAE
#define THIS_DEVICE 69
#define FAR_DEVICE 42 
#define PACKET_MAX_SIZE 255

byte nextSequence(byte value, int packet_number) {
  if (packet_number == 0) return random() % 255;
  
  return (value + packet_number) ^ NETWORK_KEY;
}

// Allocate a new packet
struct Packet_ *NewPacket(byte datasize) {
  Packet *p = (Packet *)malloc(sizeof(Packet) + datasize);
  // Zero all bytes
  int i;
  int j = sizeof(Packet) + datasize;
  for (i = 0; i < j; i++) {     
    byte *b = (byte *) p + i;     
    *b = 0;   
  }
  p->size = j;
  return p;
}

// Release the memory for packet
void ReleasePacket(struct Packet_ *packet) {
  free(packet);
}

void PrintPacket(struct Packet_ *packet) {
  int i;
  printf("Packet ----\n");
  for (i = 0; i < packet->size; i++) {
    byte *b = (byte *) packet + i;
    byte c = *b;
    printf("%2x  ", c);
    if (i % 2 == 1) {
      printf("\n");
    }
  }
  printf("-----------\n");
}

struct Packet_ *CreatePing(int dst) {
  Packet *ping = NewPacket(0);
  ping->src = THIS_DEVICE;
  ping->dst = dst;
  ping->type = PACKET_TYPE_PING;
  ping->sequence = nextSequence(0, 0);
  ping->attempt = 1;
  ping->fragment = 1;
  ping->fragments = 1;
  return ping;
}

struct Packet_ *CreatePong(struct Packet_ *ping) {
  // Don't respond to non-ping packets or packets that
  // are not broadcast pings (0) or addressed to us
  if (ping->type != PACKET_TYPE_PING) return NULL;
  if ((ping->dst != 0) && (ping->dst != THIS_DEVICE))
    return NULL;

  Packet *pong = NewPacket(0);
  pong->src = THIS_DEVICE;
  pong->dst = ping->src;
  pong->type = PACKET_TYPE_PONG;
  pong->response = nextSequence(ping->sequence, 1);
  pong->sequence = nextSequence(pong->response, 2);
  pong->attempt = 1;
  pong->fragment = 1;
  pong->fragments = 1;
  return pong;
}

struct Packet_ *ReadPacket() {
  if (!radio.available()) return NULL;
  
  byte hdr[255];
  for (int i = 0; i < 255;i++) {     
    hdr[i] = 0;   
  }
  bool done = false;
  while (!done) {
    done = radio.read(&hdr, 255);
    delay(2);   
  }
  Packet *p = (Packet *)malloc(sizeof(Packet));   
  memcpy(p, &hdr, sizeof(Packet));        
  byte size = p->size;
  Packet *packet = (Packet *)malloc(size);
  free(p);
    
  memcpy(packet, &hdr, size);
  return packet;
}

void SendPacket(struct Packet_ *p) {
  radio.stopListening();
  radio.write(p, p->size);
  radio.startListening();
}

void setup(void){
  //Prepare the radio module
  printf("\nPreparing interface\n");
  radio.begin();
  radio.enableDynamicPayloads();
  radio.setRetries( 15, 15);
  radio.setPALevel(RF24_PA_MAX);
  radio.setDataRate(RF24_2MBPS);
  radio.setChannel(0x4c);
  radio.setCRCLength(RF24_CRC_16);
  radio.openWritingPipe(pipes[0]);
  radio.openReadingPipe(1,pipes[1]);
  radio.startListening();
  radio.printDetails();
}

int main (int argc, char ** argv){
  int rcount = 0;
  setup();
  printf("Starting main loop\n");
  while(1) {
    Packet *p = ReadPacket();
    if (p != NULL) {
      rcount++;
      printf("Received Ping %d\n", rcount);
      PrintPacket(p);
      Packet *pong = CreatePong(p);
      if (pong != NULL) {
        printf("Sending Pong\n");
        SendPacket(pong);
        ReleasePacket(pong);
      }
      ReleasePacket(p);
    }
  }
  printf("Exit main loop\n");
  return 0;
}

Filling in some gaps

There are still a lot of things missing here, firstly packet validation. Incoming packets must be validated and the correct action taken depending on the packet. Right now we’re only expecting ping and pong packets on the network so we handle those directly. What we need to do is introduce the CRC16 sum (this is actually redundant as the NRF radio has this built in too), and also validate sequence numbers which is harder because we need to keep track of them.

The whole keeping track of things gets us to the harder part of the problem, which is managing lists in memory on the Arduino. We need to have lists of integers and lists of pointers and likely a mapping of some kind between integers and integers.

Following On

The next steps to establish the mesh properly are:

  • Develop incoming and outgoing packet management (including relay logic)
  • Develop connection management & fragmentation handling code
  • Develop a simulator to perform stress testing analysis