Improvements to Flutter's Frequency Hopping Code

I spent the last week working on code, and thought it would be nice to write about it to give people more insight into what I have been working on. This is a long post, but if you want to learn more about the nitty-gritty of frequency hopping read on!

As I mentioned in the middle of the Summer, I needed to implement a frequency hopping algorithm for our code. The laws don't allow you to use a radio transmitter in this band with any appreciable amount of power unless you keep the system constantly changing channels. This helps reduce interference between different wireless devices. That's pretty important, since we are all sharing one common communications medium when it comes to wireless. My radio space is my neighbor's radio space, and a system that sat on one channel and blasted at high power could interfere with similar systems for miles around. Things didn't always do this frequency hopping - cordless phones in the 1990's had buttons to cycle through the channel you would sit on, and if your neighbor used the same channel you'd get interference (and often get to hear each other's phone calls). That wasn't a very efficient use of the airspace, and as wireless devices have become more prevalent, frequency hopping (sometimes called frequency hopping spread spectrum or FHSS) became a requirement for most new wireless devices. In frequency hopping, your radio device rapidly switches to different communications frequencies in a given wireless band. Flutter, for example, runs on the "915MHz" band in North America. The 915MHz band is actually a range of frequencies from 902MHz to 928MHz. Flutter takes up a tiny fraction of that space - around 20 kilohertz or 0.02 MHz. The FCC, who regulates wireless devices in the US, requires our radio to use at least 50 channels, spending no more than 400 milliseconds on a channel every 20 seconds (right now we hop every 40ms). What this all means is that, rather than sit on one wireless frequency (aka channel), the Flutter radio is rapidly changing frequencies. The FCC requires that the pattern be "pseudo random", so we pick a chunk of channels and hop in a somewhat random manner between them. This is all handled automatically by the Flutter library code, so you don't have to worry about it. If you want to control a remote control car, the code you write just needs to pick the data to send and call a function in our library. The Flutter code automatically sends the message on the right frequency, and lets your code know if the message was received or failed (with optional automatic retries on the way). The radio may be transmitting on 906.26MHz one moment, 923.04MHz the next, and then 917.98MHz after that, etc. That's frequency hopping!

The thing is, frequency hopping is pretty complex. All the devices in the network need to know what channel to be on at any given moment. The system hits 25 channels every second, and you need to be on the same channel as your target if you're trying to send a message. If you have even a slight timing error, your messages will be lost. Luckily, Flutter has an extremely powerful processor for devices of this type, and we're taking full advantage of it to ensure we have a tight timing system. Part of the reason I chose an ARM processor over an Arduino's typical AVR chip is the ARM's expandability. Whatever code we need to write to get the most out of this radio, the CPU can handle it.

This week I worked on cleaning up the timing code that runs the frequency hopping system. A couple months ago I wrote the initial implementation of the hopping code, but it wasn't very efficient. I was repeatedly running a routine that took a few CPU cycles every time. The chip has plenty of CPU cycles to spare, so this was initially fine, but I found that certain user programs would mess up the timing. We want the Flutter radio code to be as invisible as possible, so that was no good at all. I knew my code was messy though and I had hardware to finish, so I put that issue away for a while. As long as I wrote my demos a certain way, it would all work. I had a plan to improve things, and this week I implemented that plan.

To quickly implement the frequency hopping test code, I did all the timing calculations in software. The Arduino code normally runs the system timer in 1 millisecond ticks. 1000 times a second, a small function runs that adds 1 to a counter. When you run a function like "delay(20)", the delay function checks that counter value and then waits till it gets to 20 above what it was when you first called the function. Simple! Unfortunately, I needed better than 1ms precision with my timing adjustments. To quickly see how well my frequency hopping plan would even work, I just turned up the speed on the chip's timer so that it would fire once every 100 microseconds, or 10,000 times a second. Instead of ticking the millisecond timer, I made a microsecond variable and ticked that every time, making it bump the millisecond timer every tenth call. That gave me much higher resolution timing to mess with. It was definitely a quick and dirty way, but I still didn't even know if my frequency hopping scheme would work and had quite a bit of other code to write.

Once I could adjust the timing with high precision, I wrote a routine to send the time from one board to another, and programed them to both twitch a pin at the same interval. They needed to hop channels at the same time, and this let me use my oscilloscope to see how accurately I could align their clocks. Keeping timing between remote radio devices can be a tricky problem, but after a day or two of fiddling I had about 300 microsecond accuracy. That's pretty good! It's actually better than we need, but that just means relaxed requirements elsewhere in the protocol. Once I got the timing synchronized, I was able to start working on making them hop channels in a synchronized way.

I still had that function running 10,000 times a second though, and when I tried to talk to an I2C display, I noticed that the timing would drift and the boards would get out of sync. My timing code constantly needed the CPU, and slight interruptions were messing up the frequency hopping. That was no good! So this week I finally fixed it. After a few months of testing, I now know exactly what our scheme is for frequency hopping, so I was able to go in and just eliminate a lot of the uneccesary CPU access. I also improved my timing code by moving from software timing to hardware timing. The CPU has several internal hardware timers that count up on their own while leaving the processor free to do other stuff. The one I had ticking off 10,000 times per second was one of those. I changed the way I synchronize the radios so that I could move that timer back to just 1,000 ticks per second. I only ever schedule things in the radio at millisecond intervals, so the microsecond timing was only useful for adjusting the clocks. Now I adjust the clocks in hardware rather than software. If I need to adjust the clock by, say, 200 microseconds, I just reprogram the hardware timer to fire in 800 microseconds instead of the usual 1000 microseconds. Then after it fires once I move it back to 1000 microsecond (1ms) intervals. This is a MUCH more efficient way of keeping time, and the results are well worth it.

Most of the time, the timer just adds one to a millisecond variable - something all Arduinos do. But once every 40 milliseconds, the system also hops channels (which takes around 600 us). Otherwise, it mostly leaves the chip for you to use. It does a few other things - if a packet comes in over the radio it will process it so it can send an acknowlegement. And every once in a while one of the nodes sends timing information, which the other nodes will take the time to read and adjust their clocks. Making a system like this is a complex balance between system performance and user accessibility. We want most arduino applications to "just work", despite this background code constantly running. I'm happy to say, that I2C display code that gave me grief before now runs beautifully without interfering with the timing code! Of course, we give you all the knobs and levers to pull too - if your application absolutely cannot be interrupted, you can delay the hopping until your routine is complete.

I found a decent bug in some of my Arduino system code too. When I was writing the original software timing routines, I ran into a serious issue. If doing a frequency hop takes 600 microseconds, how could I run that same function every 100 microseconds to update the clock? Well, I couldn't. Technically the chip might support it, but it didn't even feel like the right avenue to explore. Instead, I needed a sort of "multi-threaded" approach. Of course, this is a single core, single threaded CPU, but it does have a powerful interrupt system. Interrupts are bits of code you can schedule to run based on hardware events, like a pin change, new USB data, or internal timers. Each interrupt has a priority level, so more important interrupts can run in the middle of less important ones. The chip supports software interrupts too, so code running at one priority can fire off something with another priority. That was just what I needed for the frequency hopping code. Unfortunately, Arduino didn't have any built in support for software interrupts, so I had to add it. It turns out, it was pretty easy to implement. Unfortunately, this week I found a bug in the implemenation that caused it to sometimes fail to fire. I ran it more often than necessary in my original code so I never actually noticed, but when I tightened everything up to run only as often as was needed I started to see problems. After a few hours of digging through code in GDB, the command line debugger for GCC, I isolated and fixed the problem. Now Flutter has a sweet software interrupt. Once we push the code to the main Arduino repos, Due users get software interrupts too!

A short gif showing the timing accuracy of two boards synchronized wirelessly. I was clicking the oscilloscope between 250us, 500us, and 1000us per division. Video here.

The code is really lean and mean now, and I am excited to make this progress. Until now, the frequency hopping felt like a bit of a hack. With this update, our low level link code will be a reliable foundation onto which we can build the broader communications system. The Flutter communications protocol will be an evolving beast, determined by user tests, community input, and performance improvements. Mesh networking protocols are still evolving as engineers work to determine the best scheme for high performance and low power use. Frequency hopping makes things even more complex, as there is an additional step to keep devices synchronized. By developing Flutter as an open source project, we will ensure that countless methods are tested to see which schemes work the best. Protocols such as 802.15.4g are designed to drive communications in low power wireless devices like Flutter, and we may find that simply implementing that standard is the best way to move forward. But there are other schemes like IPv6 using Contiki-OS that may suit us best. In the same way that the Raspberry Pi is a platform for many different firmwares, we hope Flutter users help us develop a rich ecosystem of options for running your Flutter networks.

We had originally hoped that we'd be much farther along on the code development by the time the hardware was ready for release, but we've found that we were just a bit too optimistic there. Instead, we will be releasing Flutter with a simple but rock solid basic communications layer. Once the initial hardware shipment is out, we will start pushing software updates to github as often as we can. We have been waiting to stabilize things for the initial release, but once the code is out there all development will be in the open. We hope to engage with the community on development. Flutter is a big project, but it's one of increasing importance. As the internet of things becomes more popular, the data your devices have will become more valuable than your own needs, and that will make it all too tempting for closed source products to exploit you. Having an open source system you can trust - and one that doesn't even need to use the cloud to operate - is going to be the best way to ensure that your things work for you, and no one else.

Next week, I'll be nailing down all of the final code needed to get through FCC testing. That is going to get us approval for one data rate and one board. The Pro board will ship to backers as a kit and will require soldering, but the Basic board will be fully assembled and certified for operation at a moderate speed. Speed and range are inversely proportional, so we are settling on a speed that nets us relatively long range (over 500 meters) without so much latency that real time operation becomes a problem (exact specs next week - target is 20kbps and 600m range). We have tested the boards at very low data rates and even the Basic achieves 1000+ meter range, but such configurations will for now be considered experimental and only for licensed radio hobbyists. We hope that in the future we can release a software update that allows longer range or higher speeds for everyone.

-Taylor


7 responses
Thank you for the very detailed progress update. I remain confident in your ability, and hope all goes well with the FCC later this month. Your Friend and Investor David
Very nice technical overview. Looking forward to getting the hardware!
That's very exciting news. I'll keep my fingers crossed for the FCC testing. That frequency hopping is pretty cool. I'm glad that you've got that lean and mean stuff baked in so when we get our boards we can just start playing with the wireless stuff right away. Thanks for the update!
nice adding the bit about the IOT, good way to get flutter more popular
Would it be possible to make the range and data rate accessible for editing through the arduino programming interface? This would allow users to toggle the Flutter functionality depending on their needs.
Loved your details. Question; environmental temperature range? In other words can I use outside? And what would one expect bit-rate versus distance be? Gee your is wonderful.
Since Flutter's frequencies fall inside the 33cm amateur radio band, how difficult is it to bypass the frequncy hopping and use the radio section for a single stable frequency? There seems to be a use for amateur DTV if Flutter can be successfully hacked and re-purposed by digital hams.