Computing stuff tied to the physical world

Extended node IDs

In Software on Jan 15, 2011 at 00:01

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:

Screen Shot 2011 01 14 at 12.05.01

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.

  1. this looks very much like TCP/IP : MAC layer adresses for nodes in a CDMA group (subnet), and IP layer for routing …

  2. Just make sure you use TTL’s when you do multihop relaying or else you will endup in a packet storm ;-)

    If you are really into larger size WSN nets then it might be wise to look at existing protocols like 802.15.4 and 6lowpan to avoid reinventing the wheel.

  3. Loosing a byte over a relay lacks elegance as you need to know that you will be relayed before the packet is sent. Will you start using ‘more’ bits to allow for relaying full size packets? Perhaps further examination of the whole requirement is required.

    • Most packets are well under 66 bytes – the header byte is inserted by the relay (and all data shifted up one byte). The only impact this has on the payload, as far as I can tell, is that the receiving PC/Mac must know which which nodes in which groups are relays, to know where to extract the inserted bytes.

  4. “the header byte is inserted by the relay (and all data shifted up one byte)” Why don’t you do that in the node? Because if you do it in the node you don’t need to shift the data.

    This just work in rfm12b? I’m asking that because rfm12 doesn’t have groups!

  5. Why don’t you do that in the node?

    Because then the node needs to know through how many relays the data passes.

    rfm12 doesn’t have groups!

    Not sure what you mean. By “groups” I mean the “netgroups” implemented by the RF12 driver.

Comments are closed.