Post by thread:Multi-Master, half duplex protocol w/ collision de

Well, I'm still working on my home automation terminal, and have come to the point where I need to decide on a protocol to use for talking on the rs-485 network. Preferably, I would like it to be multi-master, half duplex and have collision detection. I know of only one easy method for collision detection, which is to send the start character first, then the priority code, MSB first. In the low points of the priority code, I need to check the line to see if another node is driving the line high, and thus has a higher priority code than me, and I cease transmitting. I'm using a PIC with a USART, but for this kind of prioritizing I'm assuming I have to bit bang at least the priority code, after which point (if I still have control) I can use the UART to transmit the rest of the message. ie. I have two devices that both see the line available, wait the required byte time to make sure it stays available, and then both start transmitting at once: ___________ ___ A ___| 1 1 1 |_0_| 1 |_0___0___0__... _______ ___________ ___ B ___| 1 1 |_0_| 1 1 1 |_0_| 1 |... The first byte is the priority code of the two devices trying to transmit. Device B can tell the third bit that not only is another device transmitting at the same time as it, but it has a higher code (since the most significant bit is first). Device B then never transmits the 4th bit, and instead waits for the other device to complete its transmission, and processes whatever it needs to process if the other transmission is intended for it. It then increments its priority code, and tries again. Device A never notices anything unusual about the line. The only problem is when two devices choose the same priority code. I suppose I could put the address of the device after the priority code, MSB first, and then the device with the higher address wins the conflict. I'm wondering who has dealt with this issue before, and whether I'm overlooking a simpler or better method of dealing with this issue. Thanks! -Adam Home Automation Terminal pictures and description (soon code and schematic) at: http://ubasics.com/adam/electronics/ha/ 15 buttons, 16x2 LCD, PIC16c66 & rs-232 (soon to be rs-485) All parts from Digikey or Radio Shack (ie, easily obtainable from many sources, if Radio Shack carries it, chances are your local electronics store carries it!) Other PIC resources: http://ubasics.com/adam/pic/

Adam, Unless you have a really big house, you can circumvent the collision detection by adding an arbitration phase. Without going into enormous details, you can create an arbitration phase at the end of every message that goes out on to the bus. The device who last sends a message may initiate the arbitration phase by driving the bus low (opposite of the stop bit) and then releasing it. All nodes listen to this falling edge and start a timer when it occurs. Then all contending devices compete by asserting the bus (driving it high - the same state as the stop bit) at pre-designated time slots. The time slots, or arbitration slots may be derived from the devices' addresses. The first one to assert the rising edge wins the arbitration and will obtain control of the bus on the next cycle. The 'really big house' part comes into play when you start examinging the size needed for the arbitration slots. The larger the separation between devices, the bigger the arbitration slots need to be. Otherwise, propogation delays throughout the network can cause one node's arbitration edges to appear in another's slot. Like I said, I'm skipping the enormous details in what I've just outlined. However I have implemented a variation of this theme with EIA-485 and found it to be quite robust. (Hint: tying the uart RX line to the Input Capture greatly eases the software overhead in capturing those edges). Scott On Mon, 21 Feb 2000, M. Adam Davis wrote: {Quote hidden}> Well, I'm still working on my home automation terminal, and have come to the > point where I need to decide on a protocol to use for talking on the rs-485 > network. > > Preferably, I would like it to be multi-master, half duplex and have collision > detection. I know of only one easy method for collision detection, which is to > send the start character first, then the priority code, MSB first. In the low > points of the priority code, I need to check the line to see if another node is > driving the line high, and thus has a higher priority code than me, and I cease > transmitting. > > I'm using a PIC with a USART, but for this kind of prioritizing I'm assuming I > have to bit bang at least the priority code, after which point (if I still have > control) I can use the UART to transmit the rest of the message. > > ie. I have two devices that both see the line available, wait the required byte > time to make sure it stays available, and then both start transmitting at once: > ___________ ___ > A ___| 1 1 1 |_0_| 1 |_0___0___0__... > > _______ ___________ ___ > B ___| 1 1 |_0_| 1 1 1 |_0_| 1 |... > > The first byte is the priority code of the two devices trying to transmit. > Device B can tell the third bit that not only is another device transmitting at > the same time as it, but it has a higher code (since the most significant bit is > first). Device B then never transmits the 4th bit, and instead waits for the > other device to complete its transmission, and processes whatever it needs to > process if the other transmission is intended for it. It then increments its > priority code, and tries again. Device A never notices anything unusual about > the line. > > The only problem is when two devices choose the same priority code. I suppose I > could put the address of the device after the priority code, MSB first, and then > the device with the higher address wins the conflict. > > I'm wondering who has dealt with this issue before, and whether I'm overlooking > a simpler or better method of dealing with this issue. > > Thanks! > > -Adam > > Home Automation Terminal pictures and description (soon code and schematic) at: > http://ubasics.com/adam/electronics/ha/ > 15 buttons, 16x2 LCD, PIC16c66 & rs-232 (soon to be rs-485) > All parts from Digikey or Radio Shack (ie, easily obtainable from many sources, > if Radio Shack carries it, chances are your local electronics store carries it!) > > Other PIC resources: > http://ubasics.com/adam/pic/ >

My RS485 network works like this. 1 master, it has a list ID's for every slave on the network. First the master sends out a string to the first slave asking if it has anything to say, if the slave says yes then the network is handed over to the slave until the slave is finished with it, once the slave is finished with it the the slave hands it back to the master. If the master hands it over to a slave and there is no network activity for more than a second then the master asumes that the slave is dead and the master takes control of the network again. If the master askes a slave if it has anything to say and there is no reply for 1 second the master goes onto the next slave in it's list. Once the master gets to the end of it's list of slaves it goes back to the start and does it all over again. No colision detection, and it works well. Regards Stuart O'Reilly M. Adam Davis wrote: {Quote hidden}> > Well, I'm still working on my home automation terminal, and have come to the > point where I need to decide on a protocol to use for talking on the rs-485 > network. > > Preferably, I would like it to be multi-master, half duplex and have collision > detection. I know of only one easy method for collision detection, which is to > send the start character first, then the priority code, MSB first. In the low > points of the priority code, I need to check the line to see if another node is > driving the line high, and thus has a higher priority code than me, and I cease > transmitting. > > I'm using a PIC with a USART, but for this kind of prioritizing I'm assuming I > have to bit bang at least the priority code, after which point (if I still have > control) I can use the UART to transmit the rest of the message. > > ie. I have two devices that both see the line available, wait the required byte > time to make sure it stays available, and then both start transmitting at once: > ___________ ___ > A ___| 1 1 1 |_0_| 1 |_0___0___0__... > > _______ ___________ ___ > B ___| 1 1 |_0_| 1 1 1 |_0_| 1 |... > > The first byte is the priority code of the two devices trying to transmit. > Device B can tell the third bit that not only is another device transmitting at > the same time as it, but it has a higher code (since the most significant bit is > first). Device B then never transmits the 4th bit, and instead waits for the > other device to complete its transmission, and processes whatever it needs to > process if the other transmission is intended for it. It then increments its > priority code, and tries again. Device A never notices anything unusual about > the line. > > The only problem is when two devices choose the same priority code. I suppose I > could put the address of the device after the priority code, MSB first, and then > the device with the higher address wins the conflict. > > I'm wondering who has dealt with this issue before, and whether I'm overlooking > a simpler or better method of dealing with this issue. > > Thanks! > > -Adam > > Home Automation Terminal pictures and description (soon code and schematic) at: > http://ubasics.com/adam/electronics/ha/ > 15 buttons, 16x2 LCD, PIC16c66 & rs-232 (soon to be rs-485) > All parts from Digikey or Radio Shack (ie, easily obtainable from many sources, > if Radio Shack carries it, chances are your local electronics store carries it!) > > Other PIC resources: > http://ubasics.com/adam/pic/

Hi, In your example, you are assuming that both device A and B start transmitting at the exact instant in time. This would require a syncronisation scheme of some sort. If you already had a syncronisation scheme, then the priority code would be a bit redundant. Andrew Thoms "M. Adam Davis" wrote: {Quote hidden}> Well, I'm still working on my home automation terminal, and have come to the > point where I need to decide on a protocol to use for talking on the rs-485 > network. > > Preferably, I would like it to be multi-master, half duplex and have collision > detection. I know of only one easy method for collision detection, which is to > send the start character first, then the priority code, MSB first. In the low > points of the priority code, I need to check the line to see if another node is > driving the line high, and thus has a higher priority code than me, and I cease > transmitting. > > I'm using a PIC with a USART, but for this kind of prioritizing I'm assuming I > have to bit bang at least the priority code, after which point (if I still have > control) I can use the UART to transmit the rest of the message. > > ie. I have two devices that both see the line available, wait the required byte > time to make sure it stays available, and then both start transmitting at once: > ___________ ___ > A ___| 1 1 1 |_0_| 1 |_0___0___0__... > > _______ ___________ ___ > B ___| 1 1 |_0_| 1 1 1 |_0_| 1 |... > > The first byte is the priority code of the two devices trying to transmit. > Device B can tell the third bit that not only is another device transmitting at > the same time as it, but it has a higher code (since the most significant bit is > first). Device B then never transmits the 4th bit, and instead waits for the > other device to complete its transmission, and processes whatever it needs to > process if the other transmission is intended for it. It then increments its > priority code, and tries again. Device A never notices anything unusual about > the line. > > The only problem is when two devices choose the same priority code. I suppose I > could put the address of the device after the priority code, MSB first, and then > the device with the higher address wins the conflict. > > I'm wondering who has dealt with this issue before, and whether I'm overlooking > a simpler or better method of dealing with this issue. > > Thanks! > > -Adam > > Home Automation Terminal pictures and description (soon code and schematic) at: > http://ubasics.com/adam/electronics/ha/ > 15 buttons, 16x2 LCD, PIC16c66 & rs-232 (soon to be rs-485) > All parts from Digikey or Radio Shack (ie, easily obtainable from many sources, > if Radio Shack carries it, chances are your local electronics store carries it!) > > Other PIC resources: > http://ubasics.com/adam/pic/

> > Adam, > > Unless you have a really big house, you can circumvent the collision > detection by adding an arbitration phase. Without going into enormous > details, you can create an arbitration phase at the end of every message > that goes out on to the bus. The device who last sends a message may > initiate the arbitration phase by driving the bus low (opposite of the > stop bit) and then releasing it. All nodes listen to this falling edge and > start a timer when it occurs. Then all contending devices compete by > asserting the bus (driving it high - the same state as the stop bit) at > pre-designated time slots. The time slots, or arbitration slots may be > derived from the devices' addresses. The first one to assert the rising > edge wins the arbitration and will obtain control of the bus on the next > cycle. This is close to a scheme I was devising. A couple of questions. First what is the state of the line between the time that the last device releasing and the first device asserting? It's unclear from the description above. Secondly since UARTS are going to be a part of this I presume that the arbitration phase must be less that 1/2 of a normal bit time? That way none of the UART circuity should register the arbitration pulse as an actual start bit right? I was planning on having a separate arbitration line for this reason. Also with a separate arbitration line then the winner can start transmitting instantly instead of waiting for the arbitration cycle to end. Lastly it doesn't look fair which is the battle I had been fighting. In the scheme I devised I have a primary and secondary slot for each device. The secondary slots all fall after all the the primaries. So arbitration would happen like this: 1. Arbitration pulse starts the timers. 2. All primaries would check their slots, If the line is available then assert and start transmitting. After transmitting move to secondary slot. 3. If no primary answers then all current secondaries can move back to their primary slot after the first secondary answers. However if any primary answers then all secondaries stay put. 4. In all cases if the arbitration line is asserted in your slot wait until the next cycle. So this way if everyone wanted to transmit all the time then the bus would get assigned in round robin priority order. Once you've transmitted then everyone who is a primary will get a chance to transmit before you get to transmit again. Initial evaluation seems to give fairness without a chance of starvation. Also I had been in the mode of thinking that a single node would control the arbitration pulse. But clearly the distributed approach of having the last sender initiate the next arbitration cycle is clearly superior. I'm planning on getting a couple of students of mine who are working on a PIC based UDP/SLIP node to implement and test the scheme. I'll let you know how it turns out. {Quote hidden}> > The 'really big house' part comes into play when you start examinging the > size needed for the arbitration slots. The larger the separation between > devices, the bigger the arbitration slots need to be. Otherwise, > propogation delays throughout the network can cause one node's arbitration > edges to appear in another's slot. > > Like I said, I'm skipping the enormous details in what I've just outlined. > However I have implemented a variation of this theme with EIA-485 and > found it to be quite robust. (Hint: tying the uart RX line to the Input > Capture greatly eases the software overhead in capturing those edges). What an excellent idea! I'd just like to say how happy I am that you've rejoined the list. BAJ

> > My RS485 network works like this. 1 master, it has a list ID's for every > slave on the network. First the master sends out a string to the first > slave asking if it has anything to say, if the slave says yes then the > network is handed over to the slave until the slave is finished with it, > once the slave is finished with it the the slave hands it back to the > master. If the master hands it over to a slave and there is no network > activity for more than a second then the master asumes that the slave is > dead and the master takes control of the network again. If the master > askes a slave if it has anything to say and there is no reply for 1 > second the master goes onto the next slave in it's list. Once the master > gets to the end of it's list of slaves it goes back to the start and > does it all over again. No colision detection, and it works well. This is standard polling. It has three major problems though it works well. 1) The network can die if the master goes offline for any reason. 2) It's extremely slow because entire characters must be sent meaning that the arbitration phase can be very long. 3) If you have many secondaries then an extraordinary amount of time can be spend searching for a secondary that wants to transmit. All three of these factors can severely hamper network performance. However for a small number of nodes, it can serve admirably. BAJ

On Tue, 22 Feb 2000, Byron A Jeff wrote: > > > > Adam, > > > > Unless you have a really big house, you can circumvent the collision > > detection by adding an arbitration phase. Without going into enormous > > details, you can create an arbitration phase at the end of every message > > that goes out on to the bus. The device who last sends a message may > > initiate the arbitration phase by driving the bus low (opposite of the > > stop bit) and then releasing it. All nodes listen to this falling edge and > > start a timer when it occurs. Then all contending devices compete by > > asserting the bus (driving it high - the same state as the stop bit) at > > pre-designated time slots. The time slots, or arbitration slots may be > > derived from the devices' addresses. The first one to assert the rising > > edge wins the arbitration and will obtain control of the bus on the next > > cycle. > > This is close to a scheme I was devising. A couple of questions. First what is > the state of the line between the time that the last device releasing and the > first device asserting? It's unclear from the description above. First of all, I must confess that I implemented this in my pre-pic days... But there's no reason why it shouldn't work on a pic. TTL <-> EI485 transcievers have a transmitter disable control signal that proves to be vital for this algorithm. Also, how you terminate the '485 network is equally important. This is what you do. The device that has control of the network and is transmitting data onto it, will be responsible for initiating the arbitration phase. It knows when the last byte is to be transmitted (and depending on your protocol, so will all other nodes too). Once this last byte has gone on to the wire, it will reprogram the UART output as general purpose output and keep the I/O line in the same state as the stop bit (TTL high). After some suitable delay, say 5 bit times, this node will drive the line low and keep it low for some other conveniently suitable time. Now two things have to happen. First, when this edge goes low ALL nodes must capture it with their Input Capture lines (including the one just asserting the edge). Second, when this node releases the line, the '485 bus will be floating. Consequently, you'll need to terminate the bus in a way that will keep it biased in this state. If you chose not to terminate the 485 bus, then simple pull up and pull down resistors are sufficient. Otherwise, you can go ahead use the standard 120 termination and just terminate one side to a plus rail and the other to a minus. > Secondly since UARTS are going to be a part of this I presume that the > arbitration phase must be less that 1/2 of a normal bit time? That way none > of the UART circuity should register the arbitration pulse as an actual > start bit right? I was planning on having a separate arbitration line for > this reason. Also with a separate arbitration line then the winner > can start transmitting instantly instead of waiting for the arbitration cycle > to end. During the arbitration phase, the UARTs are totally disabled. The capture compare module will have control. So it really doesn't matter how big the arbitration intervals are. Practical considerations are the guiding factor. For example, if you were bit banging everything, it may make sense to make the arbitration intervals a little wider and thus ease the timing constraints of a software-based input capture. I found that 1 to 2 bit times worked well (with hardware based IC). So if you have 32 nodes on the bus, then the arbitration may take between 3 and 6 character times. So you may want to shorten the arbitration intervals and/or reduce the number of nodes. {Quote hidden}> > Lastly it doesn't look fair which is the battle I had been fighting. In the > scheme I devised I have a primary and secondary slot for each device. The > secondary slots all fall after all the the primaries. So arbitration would > happen like this: > > 1. Arbitration pulse starts the timers. > 2. All primaries would check their slots, If the line is available then > assert and start transmitting. After transmitting move to secondary slot. > 3. If no primary answers then all current secondaries can move back to their > primary slot after the first secondary answers. However if any primary answers > then all secondaries stay put. > 4. In all cases if the arbitration line is asserted in your slot wait until > the next cycle. > > So this way if everyone wanted to transmit all the time then the bus would get > assigned in round robin priority order. Once you've transmitted then everyone > who is a primary will get a chance to transmit before you get to transmit > again. Initial evaluation seems to give fairness without a chance of > starvation. Absolutely! This is exactly what I did as well. There were some minor differences, but having a primary and secondary slot is crucial. One of the things you may wish to consider is designating one (or perhaps a few) device(s) with more authority than the others. The secondary slots can be reserved for only these devices. Also, if for some reason communication ceases, then these devices could act as network watchdog timers. > Also I had been in the mode of thinking that a single node would control > the arbitration pulse. But clearly the distributed approach of having the last > sender initiate the next arbitration cycle is clearly superior. I think so too. You can sort of compare it to the differences between pre-emptive and semi-pre-emptive multitasking. Distributing control puts a little more pressure on each node involved, but in my opinion the communication efficiency gained is worth it. > I'm planning on getting a couple of students of mine who are working on a > PIC based UDP/SLIP node to implement and test the scheme. I'll let you know > how it turns out. Great! One freebie with this approach is that you almost get automatic time-synchronization. Since every node knows WHEN the arbitration edge is, then one node responsible for keeping the time can tell the others when in real time that edge occured. Depending on your node separation distances, micro-second resolution time synchronization is possible. (I never needed more than 500uS though). Scott

Hello Adam. When you need multi-master network with collision detection, CAN network comes to mind. The good thing is that you can use an RS485 transceiver to imitate the very nice arbitration mechanism of CAN, without having to buy more chips. 1)CAN uses passive(high) and dominant(low) bus states. RS485 transceivers can do it. Just tie driver enable(low active) to TX output of PIC, driver input to 0V, and connect receiver output to RX input. RS485 transceivers treat floating bus state(passive state) as high. 2)To send data, node waits for bus to be free for some fixed interval (minimal pause between messages) and then starts transmission. This alone solves most arbitration problems. For cases when several nodes start transmission at the same time see below. Poll RX input in this interval frequently enough to catch any bits. 3)In CAN, message ID is transmitted first. ID also serves to tell which node has higher priority. If a node sends passive bit(1) and sees a dominant bit(0) instead, it releases the bus to allow the other node with higher priority to continue transmission. At the same time, it doesn't stop receiving data. PIC will have some extra work during arbitration phase. While ID is being sent, you should poll the RX line state before the end of each sent bit. If it detects zero instead of one then other node dominates the bus. Stop transmission immediately. If you clear SPEN bit the receiver also turns off. May be clearing TRISC<6> bit will work(?). You can find additional information on CAN at http://www.can-cia.de Hope it helps. Nikolai On Tuesday, February 22, 2000 M. Adam Davis wrote: > Well, I'm still working on my home automation terminal, and have come to the > point where I need to decide on a protocol to use for talking on the rs-485 > network. > Preferably, I would like it to be multi-master, half duplex and have collision > detection. I know of only one easy method for collision detection, which is to > send the start character first, then the priority code, MSB first. In the low > points of the priority code, I need to check the line to see if another node is > driving the line high, and thus has a higher priority code than me, and I cease > transmitting. [snip]