The recent packet relay and Extended node ID posts set the stage for a very simple way to create a fairly long-range (and very low-cost) little Wireless Sensor Network around the house.

Say hello to the Poor Man’s Mesh Network :)

(the main computer doesn’t have to be a PC/Mac, an embedded Linux box would also work fine)

Well, that’s a bit presumptuous. It’s not really “mesh” in the sense that there is no dynamic or adaptive routing or re-configuration involved at all. All the packet routes are static, so failure in one of the relays for example, will make everything “behind” it unreachable. In the world of wireless, that matters, because there are always unexpected sources of interference, and occasionally they completely wipe out the ability of a network to communicate on a given frequency band. For example, a couple of times a year, the data I’m collecting from my electricity and gas meters here at JeeLabs just stops getting in. Not sure what’s going on, but I’m not touching that setup in any way, and it’s unrelated to power outages. It might not be an RF issue, but who knows.

So what I’m referring to is not a super-duper, full-fledged, kitchen-sink-included type of wireless network. But given the extremely low cost of the nodes, and the fact that the software needs less than 4 kb of code, I think it’s a good example of how far you can get when using simplicity as guiding principle. Even an 8-bit MPU with 8 Kb of flash and 512 bytes of RAM would probably be sufficient for sensor nodes – so with the ATmega328’s used in JeeNodes, we really have oodles of spare capacity to implement pretty nifty applications on top.

Most of the details of how this works have already been presented in previous posts.

The one extra insight, is that the packet relay mechanism can be stacked. We can get data across N relays if we’re willing to limit our data packets to 66-N bytes. So by sacrificing a slight reduction in payload length we can extend the number of relays, and hence the total maximum range, as much as we like. Wanna get 10 times as far? No problem, just place a bunch of relays in the right spots along the whole path. Note that ACK round-trip delays will increase in such a setup.

The big design trade-off here is that all packet routing is static, i.e. it has to be set up manually. Each sensor node (the stars in that diagram) needs to have a netgroup which matches a relay or central node nearby, and within each netgroup each sensor node has to have a unique ID.

It’s not as bad as it may seem though. First of all, the range of the RFM12B on 433, 868, and 915 MHz is pretty good, because sub-GHz radio waves are far less attenuated by walls and concrete floors than units operating at 2.4 GHz. This means that in a small home, you wouldn’t even need a relay at all. I get almost full coverage from one centrally-placed node here at JeeLabs, even though the house is full of stone walls and reinforced concrete floors. As I mentioned before, I expect to get to curb and to the far end of our (small) garden with one or two relay hops.

Second, this star topology is very easy to adjust when you need to extend it or make changes – especially if all packet relays are one “hop” away from the central node, i.e. directly talking to it. You can turn one relay off, make changes to the nodes behind it, and then turn it back on, and the rest of the network will continue to work just fine during this change.

I’ve extended the groupRelay.pde sketch a bit further, to be able to configure all the parameters in it from the serial/USB side. These settings are saved in EEPROM, and will continue to work across power loss. This means that a relay node can now be as simple as this:

IOW, a JeeLink, plugged into a tiny cheapo USB power adapter. All you need to do is pre-load the groupRelay sketch on it (once), adjust its settings (as often as you like), and plug it in where you need it. How’s that as maintenance-free solution? And you can add/drop/alter the netgroup structure of the entire network at any time, as long as you’re willing to re-configure the affected nodes. If some of them turn out to be hard to reach because they are at the limit of the range, just insert an extra relay and tell the central software about the topology change.

It doesn’t have to be a JeeLink of course. A JeeNode, or some home-brew solution would work just as well.

Now that this design has become a reality, I intend to sprinkle a lot more sensors around the house. There have been lots of little projects waiting for this level of connectivity, from some nodes outside near the entrance, to a node to replace one of the first projects I worked on at JeeLabs!

So there you go. Who needs complexity?

The packet relay implementation shown a few days ago has some properties which somewhat limit its usability.

It all has to do with node IDs. As a relay it all works fine, i.e. packets will get relayed as intended. But the problem is that with a relay, all the packets relayed into another netgroup appear to come from that single relay node.

To go into this, let’s first set up a relay with the following configuration:

• the main netgroup is #1, the relay listens on netgroup #2
• the central node in netgroup 1 is node 31
• the relay node listens on netgroup 2 as node 31
• the relay sends packets out to netgroup 1 as node 30

Here’s that setup:

So – in principle – we could have up to 59 sensor nodes for getting actual work done. But there’s a problem: all packets sent by nodes 1..30 in netgroup 2 look like packets coming from node 30 once they reach the central node in netgroup 1!

Note that this is no problem if the relay is only used to extend the range of a single node: all we have to do is give the relay the same number of the node in netgroup 1 as what is assigned to that single node in netgroup 2.

But with more nodes behind the relay, we’re losing all their node ID’s. This is not very practical if we need to know exactly where the reported sensor data was generated, for example. We’re hitting the limitation that there are only 31 different ways to identify all incoming packets!

The solution is to insert the node ID of the original node as first byte of the payload data. So a packet coming from say node 7 in netgroup 2, will come in as a packet from node 30 (the relay), with an extra byte inserted in front of the packet, containing the value 7. The groupRelay.pde sketch has been extended to support this “multi-node relaying” capability.

On the receiving end, the software needs to know that node 30 in netgroup 1 is a relay. It then knows that the first byte is not data but an “extended” node ID, and it can use that to re-identify the packet as coming from a node in netgroup 2.

The extra data byte means that the maximum payload length across a relay is one byte less than what the nodes in netgroup 1 can send to the central node, i.e. 65 bytes instead of the 66 bytes supported by the RF12 driver.

Let’s use some conventions for node ID’s to support this mechanism. Node ID’s will be assigned as follows:

• node ID’s 1..26 are available for “real” end points, e.g. sensor nodes
• node ID’s 27..30 are available for relays and other “management” nodes
• node ID 31 is to be used as standard ID for the central receiver
• node ID 31 is also used by relays on the listening side
• lastly, node 31 is normally the node which always listens, and which sends out ACKs

Note that there is nothing in the RF12 driver implementation which enforces such a numbering scheme. It’s just a convention to simplify configuration, and to simplify the software later on.

This scheme has the following implications:

• the maximum number of end point sensor nodes is 26 x 250 = 6,500 nodes
• each netgroup can have at most 4 group relays, i.e. the “fanout” is up to 4
• each relay introduces a “hop” and may reduce the max payload size by one byte

Tomorrow, I’ll describe how to use this in a larger context.

In yesterday’s post I introduced a groupRelay.pde sketch, which implements a packet relay.

This can be used to (approximately) double the range between sensor nodes and the central data-collecting node. I’ve got two uses for this myself:

• To try and get through two layers of reinforced concrete here at JeeLabs, i.e. from the garage to the living room to the office floor where my central data-collecting node is. I can get through one floor just fine (easily, even with a few extra walls), but two is giving me trouble.

• To have a simple way to work with multiple groups of JeeNodes around here for testing and experimentation, while still allowing me to “merge” one of the test groups with the main, eh, “production” group. This can easily be accomplished by turning a suitably-configured relay on or off.

Note that all traffic takes place in the same 868 MHz frequency band. This isn’t a way to double the amount of bandwidth – all the packets flying around here have to compete for the same RF air space. All it does is separate the available space into distinct logical groups, i.e. net groups, which can be used together.

To summarize from yesterday’s post, this is how the relay code works right now:

If you think of time as advancing from top to bottom in this diagram, then you can see how the packet comes in, then gets sent out, then the ACK comes in, and finally the ACK gets sent back to the originating node. Let’s call this the Packet pass-through (PPT) approach.

This is very similar to how web requests work across the internet. There is an “end-to-end” communication path, with replies creating one long “round trip”.

But that’s not the only way to do things. The other way is to use a Store-and-forward (SAF) mechanism:

In this case, the relay accepts the packet, stores it, and immediately sends back an ACK to the originating node. Then it turns around and tries to get the stored packet to its destination.

This is how email works, BTW. The SMTP servers on which email is built can all store emails, and then re-send those emails one step closer to their intended destination.

There are several differences between PPT and SAF:

• with PPT, it takes longer for the originating node to get back an ACK
• with SAF, you get an ACK right away, even before the destination has the data
• with PPT, all failures look the same: no proper ACK is ever received
• with SAF, you might have gotten an ACK, even though the destination never got the data
• with PPT, the logic of the code is very simple, and little RAM is needed
• with SAF, you need to store packets and implement timeouts and re-transmission

But perhaps most importantly for our purposes, PPT allows us to place payload data in the ACK packet, i.e. ACKs can contain replies, whereas with SAF, you can’t put anything in an ACK, because the originating node already got an empty ACK from the relay.

Since SAF is harder to implement, needs more storage, and can’t handle ACK reply data, it just an inferior solution compared to PPT, right?

Not so fast. The main benefit of SAF, is that it can deal with nodes which don’t have to be available at the same time. If the relay is always on, then it will always accept requests from originating nodes. But the destination nodes need not be available at that time. In fact, the destination node might use polling, and ask the intermediate relay node whether there is data waiting to be sent out to it. In effect, the SAF relay now becomes sort of a PO box which collects all incoming mail until someone picks it up.

The implications for battery-powered wireless networks are quite important. With an always-on relay node in the middle, all the other nodes can now go to sleep whenever they want, while still allowing any node to get data to any other node. The basic mechanism for this is that the low-power nodes sleep most of the time (yeay, micro power!) and then periodically contact the relay node in one of two ways:

• sending out a packet they want to get to some other place
• polling the relay to get data waiting for them back as ACK reply data

The “sleep most of the time” bit is an essential aspect of low-power wireless networks. They can’t afford to keep a node awake and listening for incoming wireless packets all the time. An RFM12B draws about 15 mA while in receive mode (more than an ATmega!), and keeping it on would quickly deplete any battery.

So if we want to create an ultra low-power wireless network, we will neeed a central relay node which is always on, and then all the other nodes can take control over when they want to send out things and ask for data from that central node whenever they choose to. Which means they could sleep 99.5% of the time and wake up for only a few milliseconds every second, for example. Which is of course great for battery life.

BTW, in case you hadn’t noticed: we’re now entering the world of mesh-networking…

But the drawbacks of SAF remain: more complex logic, and the need to be able to queue up a lot of packets. So we need one node which is always on, and has plenty of memory. Hmmm, ponder, ponder… I remember having seen something suitable.

Of course: the JeeLink! It draws power via USB and has a large DataFlash memory buffer. Whee, nice! :)

Since the RF12 driver does not implement a full OSI network “stack”, there are no such things as routers and mesh networks in Jee-land. This means you’re basically limited to the range of a single 868/915 MHz point-to-point packet connection.

There are a number of ways to increase the range. One is to use a directional antenna (I’ve never tried this, but it has been mentioned on the discussion forum). Another option is to lower the transmission baud rate inside the radio and the bandwidth settings, so that the power is “beamed” into a narrower frequency range. Both of these are based on RF properties.

A third option if you can’t get from here to there in one go is to take multiple “hops”. That’s what a mesh network tries to do fully automatically, adapting on the fly to varying reception conditions and network topologies.

I’m more interested in much simpler approaches, which can easily be implemented in a little 8-bit ATmega with limited code storage. There’s a lot we can do, even within these pretty hard constraints – and it’s fun to push those little boundaries!

So here’s another option: a dedicated “packet relay” node, which listens to a specific RF12 net group most of the time, and when a packet comes in, it turns around and sends the packet out over another net group. Apart from picking two net groups for this, the mechanism should be fairly transparent.

Here’s what happens when you install such a relay:

That only covers packets going one way. A refinement is to also deal with ACK packets. In that case, the relay should wait a little while to see whether an ACK comes in, and if it does, send that ACK back out to the original packet source:

Here’s a groupRelay.pde sketch, which implements this:

It’s pretty straightforward. But it’s only made for broadcast scenarios, i.e. the originating node must be using a broadcast packet (i.e. send to special node “0”). The relay can then simply re-broadcast the information.

In the case of ACKs, the originating node id will be in the header. The relay saves this, sends out a packet with an ACK-type request of its own, waits briefly for such an ACK to come in, and when it does, sends an ACK back to the originating node.

Note how the loss of packets will have the same effect as without a relay. The only difference being that there are 2 hops (or 4 w/ ACK) where packets can be lost or get damaged.

Tomorrow, I’ll explain a little bit what’s going on and what sorts of trade-offs this leads to.

Yesterday’s RF12 driver changes added a new feature to capture packets from different net groups, and to easily send out packets to different netgroups (don’t hold your breath for a “group broadcast” to every node out there).

As reported on the forum, it’s still not perfect due to the high number of false packet triggers.

One effect of this is that correct packets are missed occasionally. Here is the output from yesterday again:

OKG 15 4 248 48
OKG 15 4 250 48
OKG 5 61 7 23 83 97 7 0 155 79
OKG 15 4 251 48
OKG 15 4 252 48
OKG 15 4 7 49
OKG 15 4 255 48

Node 4 in net group 15 is a little test node which sends out a packet once a second (it’s the radipBlip.pde sketch, in fact). And as you can see, 3 packets already got lost in that brief time window.

My hunch is that the radio syncs on far too many bit patterns. This starts the radio off, collecting bytes, until either the proper packet length has been reached or the maximum of 68 bytes (hdr + length + data).

The problem is that a correct preamble and sync pattern right after such a false start will be interpreted as data. It would be possible to solve this in software, by passing a set of valid groups to the RF12 driver, and have it abort the reception immediately if something comes in. Then the driver can immediately restart a fresh sync search, thus hopefulyl capturing a subsequent real packet.

More work will be needed in this direction, but I wanted to get the change in so others can try it out and have a go at coming up with improvements for this code.

Two more small changes were added to the RF12 driver: a way to use it in “buffer-less transmit” mode, and a slightly more flexible way to wait for the completion of packet sending.

Buffer-less transmit mode is a way to avoid having to use extra memory for sending out packets. An example:

    if (rf12_canSend()) {
        struct { ... } *buf = (void*) rf12_buf;
        rf12_len = sizeof *buf;
        // fill in values here, i.e. "buf->temp = 123", etc.
        rf12_sendStart(0);
    }

So instead of passing an area of memory to copy into the rf12_buf area, as done with a traditional call to the 3-argument rf12_sendStart(), you set up a pointer directly into that area and store results directly into them.

The crucial point is that you can only do this between the time when rf12_canSend() returns 1 and a subsequent call to rf12_sendStart(). That is the only time when the data in rf12_buf is guaranteed not to get changed by the RF12 driver itself.

In many cases, you don’t need all this trickery. This is just a way to reduce the amount of (scarce) ram needed to work with packets and the RF12 driver.

The other change in the RF12 driver concerns the following call, which uses the optional “sync” parameter to specify how to wait for send-completion:

    rf12_sendStart(hdr, buf, len, sync);

This recent addition to the RF12 driver is useful for reducing power consumption, because it lets you send out a packet through the RFM12B while the ATmega itself enters a low power mode.

I have added a new function called rf12_sendWait() which now does that waiting side separately. The above call is still available for backward compatibility, but for future use, it should be written as two calls:

    rf12_sendStart(hdr, buf, len);
    rf12_sendWait(sync);

The reason for this change, is that this now also supports the buffer-less transmit mode described above:

    if (rf12_canSend()) {
        struct { ... } *buf = (void*) rf12_buf;
        rf12_len = sizeof *buf;
        // fill in values here, i.e. "buf->temp = 123", etc.
        rf12_sendStart(0);
        rf12_sendWait(2);
    }

Small changes, all in all. This will of course be documented on the cafe/docs site, but since that site is going to be replaced by a more advanced wiki-based setup in the near future, this post will have to do for now. I don’t want to deal with two sets of documentation… maintaining one set is hard enough!

The RF12 driver has been extended with the ability to send and receive packets from any net group. This feature was long overdue – it allows a node to listen to packets coming from different net groups, and could be used to implement a packet forwarding “relay” or a mesh network.

The way to activate this “any net-group” mode, is to initialize the RF12 driver with net group zero:

    rf12_initialize(12, RFM_868MHZ, 0);

This puts the RFM12B in a special 1-byte sync mode. The new rf12_grp variable will contain the net group whenever a packet is received, i.e. whenever rf12_recDone() returns true.

To send a packet to a specific netgroup, say 34, you can now use the following code:

    if (rf12_canSend()) {
        ...
        rf12_grp = 34;
        rf12_sendStart(...);
    }

The RF12demo.pde has been extended to support this “any net-group” mode – simply set the group as “0g”.

When use in this special mode, the format of the reported lines changes slightly: “OK” becomes “OKG” plus the net group number – followed by the header byte + data bytes, as usual.

Here is some sample output, first normal mode, then any net-group mode:

Current configuration:
 A i1* g5 @ 868 MHz 
OK 3 215 66 0 0
OK 61 7 23 83 97 7 0 155 79
OK 61 52 239 0 218 39
OK 61 9 2 8 68 161 75 15 0 16 0
OK 3 217 66 0 0
OK 61 52 240 0 222 39
> 0g
 ?G 45 25 37 209 155 76 99 138 66 247 140 29 251 47 157 163 51 158
 ?G 7 133
 ?G 144 133 255 220 119 254 229 249 92 225 94 213 221 102 160 1 233 59 251
 ?G 255 185 205 23 165 55 175 172 161 229 207 108 141 152 56 127 208 134
> 1q
OKG 15 4 248 48
OKG 15 4 250 48
OKG 5 61 7 23 83 97 7 0 155 79
OKG 15 4 251 48
OKG 15 4 252 48
OKG 15 4 7 49
OKG 15 4 255 48

There is however a serious problem with the promiscuous / any net-group mode: the RFM12B module will report a lot of garbage. I added a “quiet” option to RF12demo to be able to suppress the reporting of bad packets, i.e. dropping “?…” lines. That’s why no “?…” lines were reported once the “1q” command was entered.

As you can see in the output, packets from both net-groups 5 and 15 are picked up and reported. Yippie!

The new version of the RF12 library has been checked into subversion and is also available as a ZIP file, see the software page for details.

There is a bit more to say about these changes… so stay tuned!