Packet routing along transit routes
Fresh Data
Our arrival signs will need a way to get — well everything they show riders. They need schedules and route information and delay reports and the current time and information about their peer signs. They need to get updates to that information as they run so that they can stay deployed for long periods, can adjust to changes in the sign system or bus routes, and can recover from temporary failures
So we will need a plan to reach them via radio. On a hardware layer we’re using LoRa packet radio1, which is designed for more or less this application — long-range, low-speed radio links that use fairly cheap hardware and don’t require licensing
While LoRa provides impressive range at very lower power, from a street-height antenna in a city we typically only get reliable coverage at distances under a mile. That’s much further than WiFi but not nearly far enough to reach a series of stops up and down a bus route. Luckily we are building multiple signs, and they will naturally form a line leading down each route, so we can teach them to pass messages to each other down that line
I’ve done some range testing using the prototype radio pieces. You may have seen me wandering about at bus stops, holding an antenna in the air and staring at a radio log on my phone screen to see how it’s working. I know I can reach reliably reach stop 34960, which is about 0.5 miles straight-line distance (and on the back side of a hill). The furthest I’ve had any signal is up on Mount Baker Station, but it wasn’t good enough to do anything useful (and presumably wouldn’t work at all from street level). As I collect more data I might to publish a map or something; for now I have pictures of my hand at bus stops where I took samples
Distributed Networks
There are some existing options for relayed LoRa networking, including public mesh networks like Meshtastic or MeshCore or Reticulum. These are useful and fairly community-oriented, but they tuned for a model not entirely aligned to our bus needs. They attempt to deliver messages to a changing list of local peers and to discover non-local routes dynamically. They provide encryption and anonymity and global routing. They permit messaging between any two nodes and don’t require much setup to join a network
Our network does not need most of those things, and some of them work against us. Our messages will only ever need routing along a known set of nodes with fixed locations. It will mostly not encrypt traffic2 so that anyone listening can benefit from the services it provides3 even without joining the network. It will mostly send data from the central server out along routes, with only a small amount of data coming from any arrival sign. It does not need to discover routes or nodes and does not seek to provide any anonymity or large-scale routing
Contention-Based Forwarding
Knowing exactly where each of our radios is lets us use a technique called Contention-Based Geographic Forwarding, wherein we try to send the message along the physically shortest path towards its destination. Sometimes that will be to the next sign along the bus route, but sometimes we’ll be able transmit much further and skip nodes along the way. CBF lets us pick the best relay for every individual packet, skipping as many nodes as possible while letting closer nodes provide a backup if the further nodes don’t receive our message
There is some nuance I’m omitting in this short description, but basically CBF works like this:
- A radio message is sent
- Several nodes are listening for this message
- If a node hears message it considers re-sending that message down the chain
- Before sending the node waits for a short period, listening for other senders
- The amount of time a node waits is based on how far along the chain it sits —nodes closer to the destination wait less time
- If a waiting node hears someone else re-send, it stops waiting — job done, someone further along did it for us
- If our waiting ends without hearing anyone else, it’s our turn to re-send
It’s a lot like a game of telephone, except instead of whispering you shout to move the message as quickly as possible down the line. Conveniently computers are much better at telephone than (whispering or shouting) humans, and our computers will use cryptography to ensure their messages are verifiably accurate
This scheme helps messages get as far as they can on each attempt, to reduce both the number of retransmission hops and the time it takes to send a message down the chain. It also usually lets the sender know their message was heard without needing an explicit ACK. It requires knowing where nodes are but that’s easy to do with our network because our nodes are arranged in a line along a road and rarely move4. That lets us pre-calculate the distance of each node so it’s easy to tell which one is closest to the destination even across non-linear topologies
Next Steps
Continued radio surveys I will collect reception data from a bunch of different bus stops, to see what range I can expect to cover directly. It should also help me estimate the maximum distance between nodes that we can expect to work along a route. At the same time I am collecting data about buses themselves, to see if they have any convenient tracking tags our signs might be able to read
CBF relay testing I have ordered a 2nd pair of radio nodes, so I will have a total of 3 mobile units and 1 fixed radio at my home. This should be enough to let me do on-air testing of the relay network, to make sure this network plan actually works. There’s more than a little software I need to write to make that happen, but I’ve got a good start on the design and I’m quickly building experience using LoRa modules
- Other options exist. It would definitely be possible to build a network using cellular networks to connect signs directly to the internet, or to make use of nearby WiFi at cooperative locations. Future versions of these signs might support multiple connection methods. But I picked LoRa so that our base network doesn’t depend on any telecom services, and doesn’t have any subscription costs ↩︎
- All traffic will be HMAC-signed so that network participants can authenticate it. Some traffic will be signed against a public key so that anyone can validate it. A small portion of traffic will be encrypted to each node, to allow for key exchanges, secure updates, and private logs ↩︎
- Public services like: Coarse time beacons, fine time sync, route information and schedules, live tracking data ↩︎
- Work on CBF includes mobile nodes that know (and sometimes beacon) their location, and is becoming an important part of communications systems for road vehicles and roadside infrastructure ↩︎