Writing a efficient & reliable protocol for slow speed links

[Psi]

I'm working on a home automation type system and i need to write a protocol for it to use to communicate between nodes in the system. I've written a few protocols before but this one has to be efficient because the link speed is pretty low, around 200 bits per second (maybe able to get a little more). It needs to respond to events quick enough that there doesn't appear to be a noticeable delay between turning on a light switch and the light turning on etc.

Does anyone know any useful tricks to making an efficient protocol? something that can jam lots of info into a small number of bits.

Also whats the best way to cope with the issue of the start or end of frame maker possibly appearing in the data sometimes and causing confusion.
 
I'm building the physical link electronics myself, so have control over sending individual bits. Its not fixed 8bit ascii or anything like that. I can do whatever i need.

Just thought i'd post here first, before i start building the protocol, in case anyone had any good ideas.

[Jimmy]

Why not use I2C

[ejeffrey]

When you find yourself thinking "this would be so much easier if I had more bits" the first thing to do is ask "why can't I have more bits".  200 bits per second is really, really slow.  If your threshold of perception is around 100 ms, that means you can't use more than 20 bits per command including framing bits.  This is possible, but very limiting.  On a multi-point network where more than one node is allowed to transmit, you are going to have a very difficult time getting acceptable timing performance and reliability.

What is your physical layer that 200 bits/s is a reasonable limit?

[deephaven]

Use ASCII and assign unique characters to signfy the start and end of a packet. Within the packet, you can encode addresses, control codes etc. Make it extensible so you can flag an extended packet in case you need it for future use. Add a checksum if you want to validate the data. Making it ASCII means it's easy to monitor what's going on with Hyperterm or similar.

[Psi]

Why not use I2C

i was hoping for something simpler and faster, but yeah, i should look into I2C and see if it could work.
I have to implement it in myself in code thought, can't use an i2c controller as i am generating the bits using pulses on top of the 50hz mains line.

[Psi]

When you find yourself thinking "this would be so much easier if I had more bits" the first thing to do is ask "why can't I have more bits".  200 bits per second is really, really slow.  If your threshold of perception is around 100 ms, that means you can't use more than 20 bits per command including framing bits.  This is possible, but very limiting.  On a multi-point network where more than one node is allowed to transmit, you are going to have a very difficult time getting acceptable timing performance and reliability.

What is your physical layer that 200 bits/s is a reasonable limit?

How it works is a capacitor charges up from the mains through a diode/triac, so on the positive half of the AC mains cycle the cap charges up, once it reaches the peak and starts to fall the cap remains charged (due to the diode).
The mcu triggers a triac at a specific point to discharge the cap back onto the line causing a small spike which is detectable all around the house. The negative half of the cycle is exactly the same. So two pulses can be generated per one AC cycle.
By dividing up the possible positions where the mcu triggers the triac relative to zero crossing you can get more bits of data sent per cycle.

eg, 4 possible pulse positions means 2 bits on positive half of the waveform and 2 bits on negative half so 4 bits per cycle
or 200 bits per second.

I can divide up the area into more positions to get more date but cant go to far before i get lots of errors.
 

[Mechatrommer]

the compressibility will depend on:
1) how many command and info you want to put in the packet.
2) how much extendibility you will expect in the future.
3) the speed and complexity of the communication including the compression algorithm
4) what processor you will be using
and other things i might forget. once established, then we can talk on "how" it can be.

[Psi]

the compressibility will depend on:
1) how many command and info you want to put in the packet.
2) how much extendibility you will expect in the future.
3) the speed and complexity of the communication including the compression algorithm
4) what processor you will be using
and other things i might forget. once established, then we can talk on "how" it can be.

1) Something like
- room id (5 bits)
- wall id (3 bits)
- device type (3 bits)
- action id (6 bits)
- payload data (6 bits)
- some sort of crc/checksum

2) not a huge amount, but a little, im not really doing it to make money, just want to automate all the power points and lights in the house.

3) i wasn't planing on doing compression , may need to do error correction though.

4) Probably an ATmega of some sort, might need two

[baljemmett]

3) i wasn't planing on doing compression , may need to do error correction though.

You might want to look at something like Huffman coding for some of your fields -- a pretty simple form of compression, admittedly, but if you can rank commands by frequency/immediacy it might be useful.  For instance, you might decide 'on' and 'off' are operations that are either going to happen often or need to happen with the shortest delay to avoid the system seeming slow to react, and so code them as 0 and 10; similar logic might apply to your room IDs (maybe the rooms where most interactions will happen get the shortest codes, or something).

[Psi]

3) i wasn't planing on doing compression , may need to do error correction though.

You might want to look at something like Huffman coding for some of your fields -- a pretty simple form of compression, admittedly, but if you can rank commands by frequency/immediacy it might be useful.  For instance, you might decide 'on' and 'off' are operations that are either going to happen often or need to happen with the shortest delay to avoid the system seeming slow to react, and so code them as 0 and 10; similar logic might apply to your room IDs (maybe the rooms where most interactions will happen get the shortest codes, or something).

interesting, i'd not thought of that.
There definitly will be commands that need to be sent quickly and others that dont.
I will definitly look into that
Thanks.

[Rufus]

I'm working on a home automation type system and i need to write a protocol for it to use to communicate between nodes in the system.

You haven't specified requirements on which a suitable protocol is very dependant. If all 'nodes' are peers and can talk to each other you have a whole extra can of worms trying to avoid, detect, and recover from collisions.

A master controlling slaves is easier and a master which only broadcasts to slaves is easier again.

With the 1 bit per half mains cycle scheme you propose you get a free clock so an optimal solution will almost certainly be synchronous in some way to use it.

If this is just for control/status compression is useless because you won't design redundancy into your control/status encoding.

Your physical layer isn't going to be very reliable so in addition to error detection forward error correction could be useful.

[Jimmy]

You can get much higher speeds off of a powerline than 200bit.  just send the data over the line at a higher frequency at voltage zero point at about 200khz that will give you more than enough data to send.  You could even use a cheap radio transmitter like http://littlebirdelectronics.com/products/rf-link-transmitter-315mhz to inject the signal into the line just remember only one transmitter can transmit at any one time so if a button is pushed send the data more than once. This will limit collisions when more than one button is pushed at a time.

This is sending voltage over the same cable as the power using the 50hrz as a clock pulse to start and then injecting short pulse into the circuit. You just have to make sure that your circuit board has no reference to neutral or to the house earth. You may need to put a line filter on your switchboard to stop noise interference. My power is starting to get very noisy the more people that connect solar power the worse it gets.

Or you can just hide some antennas in the walls behind you switch plates just let them hang down the walls and not even use the power line for communication.

Before you go too much further with design check to see how they wired the lights, is it loop at the light or loop at the switch (if it is loop at light there will only be 2 wires at the switch) as this will change your design because you need to allow for it.

Also are you going to use switch plates with leds as indication?

I have worked on a system at my old bosses house that I helped him create so the when someone wakes up in the middle of the night (especially guest rooms) and stand up the light will come on 10% then if they open there door the hallway light will come on 15% and the toilet light on %30 at the same time. There was lots of wires in that house and the switchboard was as big as an normal wardrobe. He was going to put all electric locks and key-less entry in everywhere but I made him put a keyed door in the laundry with a hidden key, in five years he has not used it but one day the ups will fail and he won't be able to open his front door. But it does look cool 

[Bloch]

Interesting subject. I hope that you will open project then you have some thing that works 

My first concern is 200bit that is slow for 256 ID´s

Not sure why you have room and wall id ?

- room id (32)(5 bits)
- wall id (3 bits) (

And why not X10 http://en.wikipedia.org/wiki/X10_(industry_standard)

[ToBeFrank]

Also whats the best way to cope with the issue of the start or end of frame maker possibly appearing in the data sometimes and causing confusion.

The way that makes coding the easiest is to escape it. That way when the code sees the end frame marker, it is always an end frame. Note that you also have to escape your escape. It makes it easier to debug if you also modify the escaped character. An example would be if we picked 0x7e as our frame marker and 0x7d as our escape character. We'll modify our escaped character by flipping bit 5, in other words 0x7d -> 0x5d and 0x7e -> 0x5e. So if a message being transmitted has 0x7e in it, it becomes 0x7d 0x5e and if it has 0x7d it becomes 0x7d 0x5d. The following message:

0x00 0x7e 0x01 0x7d 0x02

would be transmitted as:

0x00 0x7d 0x5e 0x01 0x7d 0x5d 0x02 0x7e

Obviously, you'd want to pick your end frame and escape such that they are less likely to occur in your data (if possible).

[ivan747]

Why not use I2C

i was hoping for something simpler and faster, but yeah, i should look into I2C and see if it could work.
I have to implement it in myself in code thought, can't use an i2c controller as i am generating the bits using pulses on top of the 50hz mains line.

I2C is designed for IC to IC communication. It will not work on longer distances. I was making a system using I2C as some sort of daisy-chainable expansion port and now I realize CAN is way better for my uses. CAN also supports LIN for cheaper things and can be extended to very long distances. It is now being used in the industrial sector for communications. Ah, and it is reliable, you can trust these things, you have priorities, even if two systems are transmitting at the same time. It is standardized, test equipment available, ready0made hubs, controllers and all sorts of stuff.

[Mechatrommer]

1) Something like
- room id (5 bits)
- wall id (3 bits)
- device type (3 bits)
- action id (6 bits)
- payload data (6 bits)
- some sort of crc/checksum

23bit. let say you can tolerate 4bit header marker (special value), 8 bit checksum, 4bit ending marker, alltogether 39bit, not a good figure, let say add 1bit to checksum (9 bit), so you have 40bits or 5 bytes of data. you may rearrange your packet to align properly into byte or nibble so easier to decode. simpler checksum you can implement odd or even parity (23bit data -> 9bit checksum = ~3bit/parity bit). if you want more bulletproof you can send 2x or 3x of the same packet to increase "integrity", but that can be a paranoia. 5bytes will take 40bits/200bps = 0.2sec, is that acceptable? my 2cnts.

Does anyone know any useful tricks to making an efficient protocol? something that can jam lots of info into a small number of bits.

compression is the trick to jam info in smallest bits. some algorithm are out there, or you can simply analyze your data pattern to avoid repeatability. checksum and data integrity on the other hand will make your data bigger or slower. so you have to compromise. the detail of your implementation is yours. hope this help, from software side of view.

and lastly in case the slave device saw or expect corrupted data, you can program it to escape and re-look for another header marker, so you need to choose a really special value for the marker. ie it will not happening in other part of your data stream.

[alm]

The main issue with I²C for long distances is that it uses open drain outputs with pull up resistors. This limits the amount of capacitance it can tolerate. Implementing an I²C slave in software is also non-trivial, although most micro's have hardware support.

[Psi]

You haven't specified requirements on which a suitable protocol is very dependant. If all 'nodes' are peers and can talk to each other you have a whole extra can of worms trying to avoid, detect, and recover from collisions.

Yeah, ive been thinking about that.
The issue of collision detection and avoidance is pushing me towards a master/slave setup.
But i can see some situations where being able to talk between nodes would be useful.

You can get much higher speeds off of a powerline than 200bit.  just send the data over the line at a higher frequency at voltage zero point at about 200khz that will give you more than enough data to send.  You could even use a cheap radio transmitter...

Before you go too much further with design check to see how they wired the lights, is it loop at the light or loop at the switch (if it is loop at light there will only be 2 wires at the switch) as this will change your design because you need to allow for it.

Also are you going to use switch plates with leds as indication?

Yeah, but a radio transmitter system is much more complex than UPB (universal powerline bus). Im trying to keep this nice and simple so i can build lots of small modules that can fit in the space inside powerpoints and light sockets.

200bit/s is more the minimum speed i know will work. Im pretty sure i can do 300 or 400bit/s
It's just that i've not got to the point where i can physically see just how many possible are possible before things start to fall apart.

(remembering that there are two pulses in one waveform, one in the positive and one in the negative)
4 possible positions for each pules = 2+2=4 bits/cycle = 200bit/s
8 possible positions for each pules = 3+3=6 bits/cycle = 300bit/s
16 possible positions for each pules = 4+4=8 bits/cycle = 400bits/s

Currently i've got a micro generating the pulse at a fixed location and i've confirmed with the scope that the pulse is quite visible on all powerpoints around the house.

You just have to make sure that your circuit board has no reference to neutral or to the house earth.

The part of the circuit that generates the pulse is isolated from everything else with an optotriac so the control logic and I/O is isolated from mains. Currently there is two 1Meg resistors from phase/neutral to the mcu for zero crossing detection but they can be replaced with another opto later on if needed to get complete isolation.

Interesting subject. I hope that you will open project then you have some thing that works 

My first concern is 200bit that is slow for 256 ID´s

Not sure why you have room and wall id ?

Yes, opening the project is definitely something i want to do. But im a little worried about inexperienced arduino enthusiast building/playing with them. Since it will work with mains voltages and the entire circuit will be floating.

The room/wall/device id was just to try and split up a big id number into meaningful sections.
It would be easier for a device in room A to talk to another device in room A if the id number has some meaning to it.

I've seen some X10 circuits, they are a bit too big/complex for the size device i want to make.
The component count for UPB (universal powerline bus)  is quite small.
I currently have it sending pulses out with just a mcu, a triac, two diodes and an opto triac + a few minor filter caps + resistors.

The way that makes coding the easiest is to escape it. That way when the code sees the end frame marker, it is always an end frame. Note that you also have to escape your escape. It makes it easier to debug if you also modify the escaped character. An example would be if we picked 0x7e as our frame marker and 0x7d as our escape character. We'll modify our escaped character by flipping bit 5, in other words 0x7d -> 0x5d and 0x7e -> 0x5e. So if a message being transmitted has 0x7e in it, it becomes 0x7d 0x5e and if it has 0x7d it becomes 0x7d 0x5d. The following message:

0x00 0x7e 0x01 0x7d 0x02

would be transmitted as:

0x00 0x7d 0x5e 0x01 0x7d 0x5d 0x02 0x7e

Obviously, you'd want to pick your end frame and escape such that they are less likely to occur in your data (if possible).

Yeah, i looked into doing escapes, maybe i didn't understand it, but it seemed that it doesn't really solve the problem, only reduce the likelihood of it happening. The escape code + start code could still happen in your data.
Seems like you can go on forever escaping escapes. hehe.

23bit. let say you can tolerate 4bit header marker (special value), 8 bit checksum, 4bit ending marker, alltogether 39bit, not a good figure, let say add 1bit to checksum (9 bit), so you have 40bits or 5 bytes of data. you may rearrange your packet to align properly into byte or nibble so easier to decode. simpler checksum you can implement odd or even parity (23bit data -> 9bit checksum = ~3bit/parity bit). if you want more bulletproof you can send 2x or 3x of the same packet to increase "integrity", but that can be a paranoia. 5bytes will take 40bits/200bps = 0.2sec, is that acceptable? my 2cnts.

0.2s delay is fine, anything quicker than maybe 0.4s id be happy with.
I'm relativity sure i can get 400bit/s out of the system. 200bit/s is really the minimum that im 99.9% sure will work.

compression is the trick to jam info in smallest bits. some algorithm are out there, or you can simply analyze your data pattern to avoid repeatability. checksum and data integrity on the other hand will make your data bigger or slower. so you have to compromise. the detail of your implementation is yours. hope this help, from software side of view.

Yeah, thanks

and lastly in case the slave device saw or expect corrupted data, you can program it to escape and re-look for another header marker, so you need to choose a really special value for the marker. ie it will not happening in other part of your data stream.

Yeah, It occurred to me last night, that since i have control over the pulses, i can just add a *special* pulse position that denotes the start /end of frame. That way it wont happen in the data at all.

[ToBeFrank]

The way that makes coding the easiest is to escape it. That way when the code sees the end frame marker, it is always an end frame. Note that you also have to escape your escape. It makes it easier to debug if you also modify the escaped character. An example would be if we picked 0x7e as our frame marker and 0x7d as our escape character. We'll modify our escaped character by flipping bit 5, in other words 0x7d -> 0x5d and 0x7e -> 0x5e. So if a message being transmitted has 0x7e in it, it becomes 0x7d 0x5e and if it has 0x7d it becomes 0x7d 0x5d. The following message:

0x00 0x7e 0x01 0x7d 0x02

would be transmitted as:

0x00 0x7d 0x5e 0x01 0x7d 0x5d 0x02 0x7e

Obviously, you'd want to pick your end frame and escape such that they are less likely to occur in your data (if possible).

Yeah, i looked into doing escapes, maybe i didn't understand it, but it seemed that it doesn't really solve the problem, only reduce the likelihood of it happening. The escape code + start code could still happen in your data.
Seems like you can go on forever escaping escapes. hehe.

There is no infinite problem here. The escape code and start/end code *will not* be in the data anymore unless they are escaping or starting/ending the data frame. On the receiving side, any time you see an escape character, you throw it away and know that the following character is a valid character that you need to convert back to its unescaped value. Any time you see a start/end frame byte, it is always a start/end frame since you know it cannot occur in the data stream.

In the worst case you would double the size of your message that you want to transmit. If you pick your escape and start/end bytes correctly, that will never occur.

[Rufus]

Yeah, It occurred to me last night, that since i have control over the pulses, i can just add a *special* pulse position that denotes the start /end of frame. That way it wont happen in the data at all.

If you have space for another bit then you could be using it for data in every 'symbol'.

Like I said you have a free clock so make a synchronous system to use it. If you have a master you can use it to establish a framing scheme for the whole network.

If say you have a 50 bit frame a master only needs to transmit a recognisable pattern (usually a pseudo random sequence) in one bit of that frame for the slaves to be able to synchronise themselves to it. Once synchronized the nodes receive whole frames carrying 49 bits of data. 2% overhead and no packet starts or ends or restriction on what the 49 bits contain. A master is needed to transmit the framing bit but any node can transmit the data bits for a frame.

For a full peer to peer system you could come up with a scheme for nodes to elect themselves as a framing master for the network. You would still have collision detection recovery etc issues.

[Jimmy]

The part of the circuit that generates the pulse is isolated from everything else with an optotriac so the control logic and I/O is isolated from mains. Currently there is two 1Meg resistors from phase/neutral to the mcu for zero crossing detection but they can be replaced with another opto later on if needed to get complete isolation.

Cool you got your hardware sorted.

Ok then back on topic of minimalistic accurate programing of signals.

Why not look into Serial Infrared Communication protocols there are plenty of libraries already out there and heaps of information on the subject. 

[Psi]

Yeah, It occurred to me last night, that since i have control over the pulses, i can just add a *special* pulse position that denotes the start /end of frame. That way it wont happen in the data at all.

If you have space for another bit then you could be using it for data in every 'symbol'.

Like I said you have a free clock so make a synchronous system to use it. If you have a master you can use it to establish a framing scheme for the whole network.

If say you have a 50 bit frame a master only needs to transmit a recognisable pattern (usually a pseudo random sequence) in one bit of that frame for the slaves to be able to synchronise themselves to it. Once synchronized the nodes receive whole frames carrying 49 bits of data. 2% overhead and no packet starts or ends or restriction on what the 49 bits contain. A master is needed to transmit the framing bit but any node can transmit the data bits for a frame.

For a full peer to peer system you could come up with a scheme for nodes to elect themselves as a framing master for the network. You would still have collision detection recovery etc issues.

Yeah i've been thinking more about it and i don't want to do any polling of the slaves to check for state changes. So it really does have to be a peer-to-peer or elected master system with collision detection and resolution.

I imagine that most of the time no pulses will need to be sent, so collisions should be rare. Only when a node has a state change will it need to send a frame (light switch now set to ON etc).

So a node could synchronously send it's ID code while also monitoring for any pulses it didn't create (proving a collision). If there were no collisions then all other nodes should have received the ID and be in slave mode until the frame is finished. If there was a collision then a random delay is probably the easiest way to solve that.

[Bloch]

I cant find it anyware so here are my question to you PSI.

Will the "units" all be active or will some be pasive ?

One example a person go out the room and turn off the ligth

Something goes wrong and the command did not go through.

Also i am not sure if the switch unit send to a master or direct to all the lamps units ?

• If you have a master that repeats that it did receive then will the light switch know that the master did not get the command
• Or the the person need to press the switch again
• .....

Now if you have a master.

Unit type press switch

- id (8 bits)
- payload data (8 bits)                           "0" = off  / "255" = on
- some sort of crc/checksum (8 bits)

Unit type dimmer switch / Unit type set room temperature

- id (8 bits)
- payload data (8 bits)                           "0" = off  /  "255" = 100 % on
- some sort of crc/checksum (8 bits)

Unit type temperature sensor

- id (8 bits)
- payload data (8 bits)                           data = temp
- some sort of crc/checksum (8 bits)

Unit type Relay
- id (8 bits)
- payload data (8 bits)                           "0" = off  / "255" = on
- some sort of crc/checksum (8 bits)

Unit type dimmer output

- id (8 bits)
- payload data (8 bits)                           "0" = off  /  "255" = 100 % on
- some sort of crc/checksum (8 bits)

The master all ready know that Id number 44 is a switch. And then the master will send a cmd to ID 33 and 34 and 120.

I think that all logic / program must be in the Master unit.

No need for
- device type (3 bits)
- action id (6 bits)

If you hardware is really good and give (all most) no errors i would change
- some sort of crc/checksum (8 bits)
to
- 1 Parity bit

The slim / fast protocol

- id (7 bits) + 1 Parity bit
- payload data (7 bits) + 1 Parity bit                       

[Psi]

I cant find it anyware so here are my question to you PSI.

Will the "units" all be active or will some be pasive ?

active, they will run off the mains using some sort of capacitor based 230v-12v supply.

One example a person go out the room and turn off the ligth
Something goes wrong and the command did not go through.

Yeah, it  may need to have ACK frames to confirm the message was received.

Also i am not sure if the switch unit send to a master or direct to all the lamps units ?

All devices will send their data to a master unit which is connected to a PC. It will read the data and then decide what to do with it. eg, send a frame to the light module to turn the light on. Powerpoints and lightswitches will be pushbutton momentary.

• If you have a master that repeats that it did receive then will the light switch know that the master did not get the command
• Or the the person need to press the switch again
• .....

Yeah, need ACK frame

I think that all logic / program must be in the Master unit.             

yeah

[ndictu]

(I just scanned through this post and also I'm a big noob so if I'm wrong here just ignore this post)

So you are doing communication over power grid right? There are ethernet-wall plugs (like this: http://www.netgear.com/home/products/powerline-and-coax/high-performance/XAV5501.aspx) that claim to do full-speed gigabit connection. I'm not sure how true that is but surely you can put more through than 200bits/s.