[Mesh] Distributed frequency hopping synchronization schemes?

taylor 2015-03-30 21:38:27 UTC #1

Flutter's original campaign promised true mesh networking, and we intend to deliver that. However I failed to anticipate the need for frequency hopping for maximum performance with regulatory compliance. We can also operate the radios in wideband mode like zigbee, and this would eliminate the need for frequency hopping, but performance is reduced by more than half due to the increased data rates needed for wideband coding gain.

The ideal solution would be frequency hopping mesh, but apparently there are some real technical challenges with making such a system work. Well needless to say, I am not one to back down from any important problem and this is one that clearly needs to be solved. Even if it is technically difficult, I know Flutter's hardware is up to the task and would make a great development platform for frequency hopping mesh solutions.

I wanted to investigate schemes for doing this. In the next post I'll detail how Flutter currently works and describe a scheme I think may get us going in the right direction.

taylor 2015-03-30 21:48:35 UTC #2

System description

Right now Flutter networks operate with one host device, which sends control and timing information on one channel every time the 50-channel pattern repeats. Orphan devices wait on this channel until they receive timing information, and then synchronize with it when the host loops around.

This works very well for even quite large networks as long as no one needs to be more than 1km from another device, so it's a fine behavior for initial delivery. However many people have been attracted to Flutter due to the promise of mesh, and I wanted to start talking with others about how we might accomplish that.

My ideas

I have some ideas that involve using multiple channels pseudo-simultaneously. Flutter devices communicate in 20 millisecond windows, and if no packet is transmitted in the first few milliseconds the device knows none will be transmitted. All devices in the network could hop once to the initial channel for listening to the main network, and then hop to alternative channels to listen for orphans for the remaining of each 20 millisecond window. Orphans could ping a series of orphan channels until they find a networked device listening on their channel. The networked device would need to send timing information to the orphan and tell it how to get onto the main network and hopping sequence.

The issue then becomes how to synchronize devices beyond the main network. To do this, I think I should write another post that details how the CC1200 radio on Flutter works. For those who already know how digital radios work, I will say that I think our timing scheme needs to be changed. Right now I send a digital packet containing the exact system time down to microseconds over the air. It's six bytes plus control characters. I think a short burst of preamble for the first millisecond after hopping may be a useful alternative signal to synchronize remote devices. If all radios transmitted 1ms of preamble after hopping, this may help distant devices stay synchronized. Perhaps the host still sends packetized timing information to nearby devices, but the network in unison does the preamble burst.

Orphans could listen on random channels and then respond when they hear a preamble burst. Networked devices that hear the orphan request could continue hopping, negotiate who should talk to the orphan (based on RSSI) and then hop back to that channel and bring the orphan into the network.

At some point, we will need to build some automatic system-level communications into Flutter beyond the timing synchronization. Devices should all store information about system topology so they can determine who routes data to who. That will be something to talk about too.

Requests

I haven't researched existing proposals for frequency hopping mesh yet. Does anyone have any links to research in this area?

jeffcraighead 2015-04-02 01:54:02 UTC #3

I started drawing up a meshing protocol (for another project I am working on) I'll dig up my notes and post the details here. It is similar to what you've come up with, but uses a shared key and a single byte in the packet to synchronize the timing switching. It also allows for a hop limit, discover, and addressing a target node.

jeffcraighead 2015-04-07 21:18:49 UTC #4

Finally getting some time to work on Flutter again. Here it goes:

I was basing this on the CC1110, but I think the radio packet format for the CC1200 is the same. Something like this

Where Preamble [4], Sync [4], Len [1] are part of the TI radio packet and perform the functions specified in the CC1200 documentation.

Addr [1] does not address a specific device as in the CC1110 docs, but specifies the something like a subnet. Addr also defines the FHSS random seed. This way each subnet will hop on its own pattern across the 50 channels instead of all Flutter devices using the same hop pattern.

Ver [1] allows us to update the format of the packet and hopefully be able to handle various packet formats/be backwards compatible by agreeing on the lowest common packet format for the mesh.

ID [1] is the address of the sending device.

Peers [1] is the number of peers that the sending node can hear.

Next Seq [1] is the next hop in the sequence. Not the channel number, but the sequence number, 1-50.

% Complete [1] is the % of time through the current sequence the packet was transmitted.

User Data [244 max] Payload data the user wants to send

CRC [1] CRC as as documented in TI CC1110/1200 user guides.

The Next Seq. and % Complete fields could probably be packed into a single byte or eliminated all together if we stick with a 20ms hop time. I was planning on a 400ms hop time so the complete rotation though the channels would take 20s instead of 1s, so those fields would allow faster/tighter hop synchronization once a device joined a network and reduce the overhead from 6 bytes to 1 or 2. While attempting to join a device could either sit on channel 1 and wait until it hears another node with the same Addr or hop through a smaller set and wait longer than 400ms while listening only. So maybe sequence numbers 10,20,30,40,50 and sit on each one for 1/3 of the cycle time. So 6666ms if using 400ms hops or 333ms if using 20ms hops. Additionally, I was thinking that once a device was connected it would be able to keep track of the approximate time till the next hop (via the % Complete variable) to determine if there is enough time to transmit the queued message(s).

Discovery of peers would happen by listening through the hop sequence and recording the Addr and RSSI. This list of peers could then be used for routing in the mesh. We could also have some control packets where the various nodes exchange information about the nodes that are visible to them. This way each node can build a complete routing table so it can forward packets to the best next node. Another thought on peers and forwarding packets is to have a 1 byte num hops variable that is decremented on each hop so that a packet doesn't roam around the mesh indefinitely. We may also need a packet number byte so that a receiving node can discard duplicate packets (in case multiple nodes retransmit a packet).

Any thoughts on this?

Jarrod_s 2015-05-13 20:30:59 UTC #5

Hi All,
Have you guys looked at RadioHead? They already have a decent Mesh system worked out and support Frequency Hopping. This way you could Focus on just the Model Driver and Model Config and then the Library would handle the Mesh and Routing. Here is the Abstract Class for building the Driver.

I was looking at the RFM69 Driver and Modem Config for reference and then at the Flutter Wireless Library and It's REG settings. Structurally they look compatible at the SPI level but to be honest I am not sure if this would work due to the hoops Talor had to go through for FCC.

Does this look like it might be an Option? Maybe someone with More Experience on the RF side and the CC1200 could Weigh in on this. I think it would be great if we could use RadioHead, cause then people that have been already using RadioHead with other Arduino boards can port their code or at least have an simple transition with a good amount of documentation out there.

-Jarrod