Autodetect slave devices on a bus network (RS485)

I have a bus network (RS485 based) with one master and N slaves.  Each slave has a different unique 32-bits serial number.

I was thinking on a method for the master to autodetect the serial numbers of the connected slaves. Of course, the brute force method isn't acceptable for the time to test ALL the serial numbers.

A more intelligent approach could be to discover the serial numbers on a bit basis (similar to 1-wire discovery algorithm).

Starting from bit 0, the master could send a broadcast request: are there slaves with bit 0 set to 1? If the serial number matches the request, the slave answers with its complete serial number.
If no answer is detected, the result is simple: all the serial numbers have the bit 0 set to 0.
If N corrected answers are received (so they don't overlap), the master has detected N slaves.
If some bytes are received, but the message isn't correct, most probably more than one slave has a serial number with the same characteristic (bit 0 to 1) and the answers are overlapped. The master should move to bit 1 to solve the collision, sending a request similar to the following: are there serial numbers with bits 1-0 set to 1-1?
And so on...

Do you think this could work in a real situation? Are there implementations similar to this?

Are there other better methods to implement an auto-discovery feature?

pozzugno@gmail.com writes:

> I have a bus network (RS485 based) with one master and N slaves.  Each
> slave has a different unique 32-bits serial number.
>
> I was thinking on a method for the master to autodetect the serial
> numbers of the connected slaves. Of course, the brute force method
> isn't acceptable for the time to test ALL the serial numbers.
>
> A more intelligent approach could be to discover the serial numbers on
> a bit basis (similar to 1-wire discovery algorithm).
>
> Starting from bit 0, the master could send a broadcast request: are
> there slaves with bit 0 set to 1? If the serial number matches the
> request, the slave answers with its complete serial number.
> If no answer is detected, the result is simple: all the serial numbers have the bit 0 set to 0.
> If N corrected answers are received (so they don't overlap), the master has detected N slaves.
> If some bytes are received, but the message isn't correct, most
> probably more than one slave has a serial number with the same
> characteristic (bit 0 to 1) and the answers are overlapped. The master
> should move to bit 1 to solve the collision, sending a request similar
> to the following: are there serial numbers with bits 1-0 set to 1-1?
> And so on...

I think you have to consider the situation where several slaves reply
together, but one "wins" (because it has stronger drivers or is closer).
So that replies get lost without any error detected.

> Do you think this could work in a real situation? Are there implementations similar to this?
>
> Are there other better methods to implement an auto-discovery feature?

You could build in a random reply time delay element (seeded with the
serial number perhaps).

Or consider switching to CAN if that is still possible, which has
arbitration built-in.

-- 

John Devereux

On Mon, 9 Sep 2013 02:35:17 -0700 (PDT), pozzugno@gmail.com wrote:

>I have a bus network (RS485 based) with one master and N slaves.  Each slave has a different unique 32-bits serial number.
>
>I was thinking on a method for the master to autodetect the serial numbers of the connected slaves. Of course, the brute force method isn't acceptable for the time to test ALL the serial numbers.
>
>A more intelligent approach could be to discover the serial numbers on a bit basis (similar to 1-wire discovery algorithm).
>
>Starting from bit 0, the master could send a broadcast request: are there slaves with bit 0 set to 1? If the serial number matches the request, the slave answers with its complete serial number.

If you get a clean response, this slave should be locked out (not
respond) to any further searches.

>If no answer is detected, the result is simple: all the serial numbers have the bit 0 set to 0.
>If N corrected answers are received (so they don't overlap), the master has detected N slaves.
>If some bytes are received, but the message isn't correct, most probably more than one slave has a serial number with the same characteristic (bit 0 to 1) and the answers are overlapped. The master should move to bit 1 to solve the collision, sending a request similar to the following: are there serial numbers with bits 1-0 set to 1-1?
>And so on...

You may have to run this bit search a few times, each time locking out
any successful matches, until there are no conflicts.

>
>Do you think this could work in a real situation? Are there implementations similar to this?
>
>Are there other better methods to implement an auto-discovery feature?

Regarding collisions, with some CANbus style dominat/recessive style
RS-485 like communication, it should be possible to detect one station
correctly and lock it out from the search and try again.

Il giorno luned� 9 settembre 2013 12:06:30 UTC+2, John Devereux ha scritto:
> pozzugno writes:

> I think you have to consider the situation where several slaves reply
> together, but one "wins" (because it has stronger drivers or is closer).
> So that replies get lost without any error detected.

Yes, if two slaves answer at exactly the same time, this could be a problem. One answer could hide the other.

As you suggest later, I can add a delay (calculated from the serial number) to the answer, but there's a not-null probability the delay time for two slaves on the bus are the same. So those slaves will answer always at the same time and the problem remains.


> Or consider switching to CAN if that is still possible, which has
> arbitration built-in.

I have to use a RS485.

On 09/09/13 10:36, pozzugno@gmail.com wrote:

>
> As you suggest later, I can add a delay (calculated from the serial number) to the answer, but there's a not-null probability the delay time for two slaves on the bus are the same. So those slaves will answer always at the same time and the problem remains.
>
>

Not really. If you make the backoff unit time greater than the reply 
message
length / time, then you guarantee that reply frames never overlap, assuming
that all serial numbers are unique...

Chris

On 09/09/13 11:35, pozzugno@gmail.com wrote:
> I have a bus network (RS485 based) with one master and N slaves.
> Each slave has a different unique 32-bits serial number.
> 
> I was thinking on a method for the master to autodetect the serial
> numbers of the connected slaves. Of course, the brute force method
> isn't acceptable for the time to test ALL the serial numbers.
> 
> A more intelligent approach could be to discover the serial numbers
> on a bit basis (similar to 1-wire discovery algorithm).
> 
> Starting from bit 0, the master could send a broadcast request: are
> there slaves with bit 0 set to 1? If the serial number matches the
> request, the slave answers with its complete serial number.
> 
> If no answer is detected, the result is simple: all the serial
> numbers have the bit 0 set to 0.
> 
> If N corrected answers are received (so they don't overlap), the
> master has detected N slaves.
> 
> If some bytes are received, but the message isn't correct, most
> probably more than one slave has a serial number with the same
> characteristic (bit 0 to 1) and the answers are overlapped. The
> master should move to bit 1 to solve the collision, sending a request
> similar to the following: are there serial numbers with bits 1-0 set
> to 1-1?
> 
> And so on...
> 
> Do you think this could work in a real situation? Are there
> implementations similar to this?
> 
> Are there other better methods to implement an auto-discovery
> feature?
> 

A much better way is to stick closer to the 1-wire discovery algorithm.

First, ask on the bus if there are any slaves with 0 in bit 0.  All
slaves that want to answer, should check the bus for communication
(i.e., check that they are not currently reading a byte, and check that
the UART start bit is not on the line already).  If the bus is free,
they start sending with a fixed "Yes" reply.  If the slaves are fast
enough (in comparison to the baud rate), then there should be no
problems with overlap - any slaves that are a bit late compared to other
repliers will keep quiet, and if there are several "winners" in the
reaction time race, then each sends an identical message and there is no
corruption.

If the master sees any "Yes" replies, then it knows there is at least
one node on the bus with 0 in bit 0.  It then asks if there are any
slaves with 00 on the first two bits.  Suppose there are no replies
within the timeout - then it knows 00 is a dead-end.  It can ask for 01
and search down that tree branch.  You continue in this way, doing a
depth-first search until you have identified all nodes (each at a depth
of 32 down the tree).  Whenever a node has been fully identified, the
master sends a "shut up for now" message specifically to that node, so
that it does not reply to the rest of the search.

The slaves never send their serial numbers - they only send a "Yes"
message - this keeps the replies corruption-free.  The serial numbers
are found by the search mechanism.

Alternatively, you might consider allowing corruption - slaves should
send "Yes", immediately followed by their serial number and a CRC check.
 If only one (still unidentified) node exists in the current branch,
then the CRC should pass - you can confirm it when you send a "shut up
for now" message (if this fails, you've hit an unlucky corruption).  If
two or more nodes are on the branch, the CRC will most likely be
corrupted and you continue with your bit-search.

Il giorno luned� 9 settembre 2013 14:37:12 UTC+2, chris ha scritto:
> On 09/09/13 10:36, pozzugno wrote:

> > As you suggest later, I can add a delay (calculated from the serial number) 
> > to the answer, but there's a not-null probability the delay time for two 
> > slaves on the bus are the same. So those slaves will answer always at the 
> > same time and the problem remains.
> 
> Not really. If you make the backoff unit time greater than the reply 
> message length / time, then you guarantee that reply frames never overlap, 
> assuming that all serial numbers are unique...

Are you sure?

A message of 8 bytes on a 9600bps bus takes 80 / 9600 = 8.33ms. If I use 10ms as the delay step (as you suggested, a little bigger than the message length) and the delay must be different for each serial number, I will have a maximum delay of 2^32 * 10ms = 42 million of seconds!!!

If the delay is only derived/calculated from the serial number, the probability to have two slaves with the same delay on the bus is not null.

Il giorno luned� 9 settembre 2013 15:09:11 UTC+2, David Brown ha scritto:
> On 09/09/13 11:35, pozzugno wrote:

> A much better way is to stick closer to the 1-wire discovery algorithm.
> 
> First, ask on the bus if there are any slaves with 0 in bit 0.  All
> slaves that want to answer, should check the bus for communication
> (i.e., check that they are not currently reading a byte, and check that
> the UART start bit is not on the line already).  If the bus is free,
> they start sending with a fixed "Yes" reply.  If the slaves are fast
> enough (in comparison to the baud rate), then there should be no
> problems with overlap - any slaves that are a bit late compared to other
> repliers will keep quiet, and if there are several "winners" in the
> reaction time race, then each sends an identical message and there is no
> corruption.

Do you think this approach works well? I never tried to check the bus status before sending a message. Can a long cable (100meter) cause some problem with this method? Consider the bus is running at 9600bps.


> If the master sees any "Yes" replies, then it knows there is at least
> one node on the bus with 0 in bit 0.  It then asks if there are any
> slaves with 00 on the first two bits.  Suppose there are no replies
> within the timeout - then it knows 00 is a dead-end.  It can ask for 01
> and search down that tree branch.  You continue in this way, doing a
> depth-first search until you have identified all nodes (each at a depth
> of 32 down the tree).  Whenever a node has been fully identified, the
> master sends a "shut up for now" message specifically to that node, so
> that it does not reply to the rest of the search.
> 
> The slaves never send their serial numbers - they only send a "Yes"
> message - this keeps the replies corruption-free.  The serial numbers
> are found by the search mechanism.
> 
> Alternatively, you might consider allowing corruption - slaves should
> send "Yes", immediately followed by their serial number and a CRC check.
>  If only one (still unidentified) node exists in the current branch,
> then the CRC should pass - you can confirm it when you send a "shut up
> for now" message (if this fails, you've hit an unlucky corruption).  If
> two or more nodes are on the branch, the CRC will most likely be
> corrupted and you continue with your bit-search.

Good suggestion. I'll try to think to the best solution.

It's strange this kind of descovery mechanism isn't already implemented.

On 09/09/13 14:25, pozzugno@gmail.com wrote:

> Are you sure?
>
> A message of 8 bytes on a 9600bps bus takes 80 / 9600 = 8.33ms. If I use 10ms as the delay step (as you suggested, a little bigger than the message length) and the delay must be different for each serial number, I will have a maximum delay of 2^32 * 10ms = 42 million of seconds!!!

Depends on how many nodes you have on the network.  Is it really 
necessary to have
the address defined as 2^32, or would fewer bits returned get the job 
done ?. It's
a bit of an extreme example.

You have to design the address protocol to suit the expected number of 
nodes + a
margin and the latency of the network. Design is about optimising this 
juggling
act :-)...

Chris

pozzugno@gmail.com wrote:
> I have a bus network (RS485 based) with one master and N slaves.
> Each slave has a different unique 32-bits serial number.
> 
> I was thinking on a method for the master to autodetect the serial
> numbers of the connected slaves. Of course, the brute force method
> isn't acceptable for the time to test ALL the serial numbers.
> 
> A more intelligent approach could be to discover the serial numbers
> on a bit basis (similar to 1-wire discovery algorithm).
> 
> Starting from bit 0, the master could send a broadcast request: are
> there slaves with bit 0 set to 1? If the serial number matches the
> request, the slave answers with its complete serial number. If no
> answer is detected, the result is simple: all the serial numbers have
> the bit 0 set to 0. If N corrected answers are received (so they
> don't overlap), the master has detected N slaves. If some bytes are
> received, but the message isn't correct, most probably more than one
> slave has a serial number with the same characteristic (bit 0 to 1)
> and the answers are overlapped. The master should move to bit 1 to
> solve the collision, sending a request similar to the following: are
> there serial numbers with bits 1-0 set to 1-1? And so on...
> 
> Do you think this could work in a real situation? Are there
> implementations similar to this?
> 
> Are there other better methods to implement an auto-discovery
> feature?

try a "binary search" on address space:

the master must be able to send request of this kind:

"Is there ANY slave with address between Value1 and Value2 ?"

the slaves reply with a break on serial port (  long low signal ) if the
address match the range

start with request with
Value1=0 and Value2=0xffffffff

next step is ( low half )
Value1=0 and Value2=0x7fffffff
and ( upper half )
Value1=0x80000000 and Value2=0xffffffff

and so on

if no slave reply for a request the block is empty
if ( at least ) a slave reply for a request the block is not empty and
the interval must be halved and visited