Autodetect slave devices on a bus network (RS485)

In comp.arch.embedded,
David Brown <david@westcontrol.removethisbit.com> 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.

If you are allowed to set the TX/DE on the slaves in I/O mode, you could
just send an acknowledge level. Or use the UART break function to send an
ACK instead. The fixed level prevents colision problems when your slaves
are not fast enough in comparison with the bitrate.

-- 
Stef    (remove caps, dashes and .invalid from e-mail address to reply by mail)

Charm is a way of getting the answer "Yes" -- without having asked any
clear question.

On 09/09/13 16:36, pozzugno@gmail.com wrote:
> 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.

100 m is not long, and 9600 is not fast.

With 100m, the propagation delay will be a few microseconds (depends on
the capacitance and inductance of the line, of course), while a bit time
is 100 us at 9600 baud.  So you should have no problem with the this bus.

As a rule of thumb, if CAN can work on the bus, then this sort of bus
status checking should work (again, assuming the slave microcontrollers
are fast enough that there is no significant delay between checking the
state of the line as a GPIO input, and starting the UART transmission).
 At 100 m, CAN runs fine at 500 kBaud.


> 
> 
>> 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.
> 

It /is/ already implemented - I have used it in an application.  (For
weird "historical" reasons, the bus had CAN drivers rather than RS-485
drivers, but used UARTs rather than CAN controllers.  That bus ran with
several hundred meters at 38400 baud.)

pozzugno@gmail.com wrote:

>> 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.

BTW: Please limit your line length to 70 characters.

It would be also a problem, if two slaves answer at different time,
because they will try to drive the bus to opposite levels causing high
currents, reflections, corrupted UART frames.

>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 

...unless the delay step is larger than the bus delay. But you can't
wait so long.

>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.

that's the problem. As I wrote already in "RS485 bus and
auto-addressing" 2013-04-29, EIA485 likely is not a good choice for
your application.

Oliver
-- 
Oliver Betz, Munich
despammed.com is broken, use Reply-To:

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 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?


If you can reliably detect that overlapping responses have occurred
(either by detecting gibberish - bad CRC, formatting, etc. - or line
noise - framing errors, etc.), this isn't too hard.

Broadcast an "identify" a query, with a range of addresses, initially
the whole address space.  Any device with an address in the specified
range should respond.  If you get one good response (or several, if
you're timing constraints allow that), life is good, record those and
move on.  If, OTOH, you get an error, divide the range in half, and
resend the query for the half range.  Continue the binary-like search
until each range returns either nothing, or good responses.  Of course
you have to probe both sides of the division.

You need to allow enough time between queries to allow the line to
settle (IOW, the slowest possible response plus a bit).

At worst that will run in O(m*n), where m is the number of devices to
be found, and n is the number of bits in the address space.  Actually
I think for cases where both n and m are not close to unity, the
runtime has to be considerably smaller than that.

For robustness, you need to have a little chat with each device to
verify it's existence after you've found it, and then you should tell
each found device to stop responding to ident queries.  And then
repeat the whole process a few times (starting with the "whole address
space" query).

If you can't detect collision reliably, but with some probability, an
appropriate number of repetitions would allow you to reduce the
probability of missing a device to an arbitrarily low value.  This
assumes that there are no systemic problems that would prevent you
from ever detecting a collision between two specific devices
(explicitly adding some random timing jitter to the responses may help
with that).