P
pozz
I'm programming a small 8-bit microcontroller (AVR from Atmel). This is
the single master in a 2-wires RS485 network where N slaves (AVR based)
are connected. In RS485 networks, only one transmitter can be active at
a time, otherwise the transmitted characters will arrive corrupted to
the receivers. Moreover, the characters transmitted from the active
transmitter are received by all receivers (all other nodes in the
network that are listening if they aren't transmitting).
I want to design and implement a discovery technique: the master should
be able to understand how many slaves are connected and assign them a
different address for further communication.
I can use the 32-bits serial number stored in a non volatile memory in
the slaves and master (each node on the bus has a different serial number).
The discovery algorithm I was thinking of is based on the following
consideration: if two or more slaves answer to a query originated by the
master, two cases could happen.
1. the answer messages are separated in time, so they arrive
uncorrupted to the master;
2. two or more answer messages overlap, so they could arrive
corrupted to the master.
The master is able to detect a corrupted message (through some
mechanisms, such as CRC).
The algorithm I'm implementing is based on binary search: the master
sends a broadcast query with an interval of serial numbers. All the
slaves with a serial number in the interval answers to the master. As
soon as the master receives a valid answer, it assign a new address to
the slave. When a slave receives a new address, it stops responding to
discovery queries from the master.
A test code for the algorithm is:
uint32_t rx_sn;
int
autodetect(void)
{
uint32_t mask = 0;
uint32_t value = 0;
uint32_t vbit = 0;
uint32_t mbit = 0;
int result = 0;
while (result == 0) {
int r = query(mask, value);
if (r == ANSWER_OK) {
assign_new_address(rx_sn);
mask = value = 0;
vbit = 0;
mbit = 0;
continue;
} else if (r == NO_ANSWER) {
if (vbit == 0) {
if (mask == 0) {
result = 1; /* No more slaves to detect */
} else {
value |= mbit;
vbit = 1;
continue;
}
} else {
result = -1; /* Error */
}
} else { /* r == GARBAGE */
if (mask == UINT32_MAX) {
result = -2; /* Error */
} else {
if (mbit) mbit <<= 1; else mbit = 1;
mask |= mbit;
vbit = 0;
}
}
}
return result;
}
The function query() simulates the transmitting on the bus of the
message "Are there any slave with serial numbers in the range defined by
this mask and this value?". The return value of query() could be
ANSWER_OK (just one slave has responded with a correct answer),
NO_ANSWER (no slave has responded at all), GARBAGE (two or more slave
have responded so a corrupted answer is received).
If the result is ANSWER_OK, the serial number of the slave that has
responded is stored in global variable rx_sn.
The function assign_new_address() simulates the transmitting on the bus
of the message "The slave with this serial number will use this address
for further communication. From now on, it won't answer anymore to
discovery queries".
The interval of serial numbers is defined by a 32-bits MASK and a
32-bits VALUE: a serial number SN is in the range if
(SN & MASK) == VALUE
If garbage is received, the algorithm tries to reduce the interval
fixing the value of the least significant bit, first to 0 and after to
1. If more than one slave answer, the successive left bit is fixed.
I think this algorithm works, but it is slow and not optimized. As you
can note, when a new slave is discovered, it starts from the beginning.
This approach will loose some time to sends the same query many times.
Suppose to have three slaves on the network with serial numbers
00000001, 00000003 and 00000007. The previous algorithm will produce 12
queries:
1. mask=00000000 value=00000000: GARBAGE
2. mask=00000001 value=00000000: NO ANSWER
3. mask=00000001 value=00000001: GARBAGE
4. mask=00000003 value=00000001: ANSWER OK
Assigning new address for SN 0x00000001
5. mask=00000000 value=00000000: GARBAGE
6. mask=00000001 value=00000000: NO ANSWER
7. mask=00000001 value=00000001: GARBAGE
8. mask=00000003 value=00000001: NO ANSWER
9. mask=00000003 value=00000003: GARBAGE
10. mask=00000007 value=00000003: ANSWER OK
Assigning new address for SN 0x00000003
11. mask=00000000 value=00000000: ANSWER OK
Assigning new address for SN 0x00000007
12. mask=00000000 value=00000000: NO ANSWER
The query 2 has no answer, so it's a lost of time to send again during
the algorithm (see query 6): it will never be answered.
I think this could be solved avoiding to restart the algorithm from the
beginning every time a new slave is found. I have the impression it
could be optimized with recursion, but I can't use recursion on AVR
small microcontroller (stack space is very small). I know every
recursive algorithm can be written without recursion, so it could be my
solution.
Is someone suggest an optimization of my technique?
Thank you.
the single master in a 2-wires RS485 network where N slaves (AVR based)
are connected. In RS485 networks, only one transmitter can be active at
a time, otherwise the transmitted characters will arrive corrupted to
the receivers. Moreover, the characters transmitted from the active
transmitter are received by all receivers (all other nodes in the
network that are listening if they aren't transmitting).
I want to design and implement a discovery technique: the master should
be able to understand how many slaves are connected and assign them a
different address for further communication.
I can use the 32-bits serial number stored in a non volatile memory in
the slaves and master (each node on the bus has a different serial number).
The discovery algorithm I was thinking of is based on the following
consideration: if two or more slaves answer to a query originated by the
master, two cases could happen.
1. the answer messages are separated in time, so they arrive
uncorrupted to the master;
2. two or more answer messages overlap, so they could arrive
corrupted to the master.
The master is able to detect a corrupted message (through some
mechanisms, such as CRC).
The algorithm I'm implementing is based on binary search: the master
sends a broadcast query with an interval of serial numbers. All the
slaves with a serial number in the interval answers to the master. As
soon as the master receives a valid answer, it assign a new address to
the slave. When a slave receives a new address, it stops responding to
discovery queries from the master.
A test code for the algorithm is:
uint32_t rx_sn;
int
autodetect(void)
{
uint32_t mask = 0;
uint32_t value = 0;
uint32_t vbit = 0;
uint32_t mbit = 0;
int result = 0;
while (result == 0) {
int r = query(mask, value);
if (r == ANSWER_OK) {
assign_new_address(rx_sn);
mask = value = 0;
vbit = 0;
mbit = 0;
continue;
} else if (r == NO_ANSWER) {
if (vbit == 0) {
if (mask == 0) {
result = 1; /* No more slaves to detect */
} else {
value |= mbit;
vbit = 1;
continue;
}
} else {
result = -1; /* Error */
}
} else { /* r == GARBAGE */
if (mask == UINT32_MAX) {
result = -2; /* Error */
} else {
if (mbit) mbit <<= 1; else mbit = 1;
mask |= mbit;
vbit = 0;
}
}
}
return result;
}
The function query() simulates the transmitting on the bus of the
message "Are there any slave with serial numbers in the range defined by
this mask and this value?". The return value of query() could be
ANSWER_OK (just one slave has responded with a correct answer),
NO_ANSWER (no slave has responded at all), GARBAGE (two or more slave
have responded so a corrupted answer is received).
If the result is ANSWER_OK, the serial number of the slave that has
responded is stored in global variable rx_sn.
The function assign_new_address() simulates the transmitting on the bus
of the message "The slave with this serial number will use this address
for further communication. From now on, it won't answer anymore to
discovery queries".
The interval of serial numbers is defined by a 32-bits MASK and a
32-bits VALUE: a serial number SN is in the range if
(SN & MASK) == VALUE
If garbage is received, the algorithm tries to reduce the interval
fixing the value of the least significant bit, first to 0 and after to
1. If more than one slave answer, the successive left bit is fixed.
I think this algorithm works, but it is slow and not optimized. As you
can note, when a new slave is discovered, it starts from the beginning.
This approach will loose some time to sends the same query many times.
Suppose to have three slaves on the network with serial numbers
00000001, 00000003 and 00000007. The previous algorithm will produce 12
queries:
1. mask=00000000 value=00000000: GARBAGE
2. mask=00000001 value=00000000: NO ANSWER
3. mask=00000001 value=00000001: GARBAGE
4. mask=00000003 value=00000001: ANSWER OK
Assigning new address for SN 0x00000001
5. mask=00000000 value=00000000: GARBAGE
6. mask=00000001 value=00000000: NO ANSWER
7. mask=00000001 value=00000001: GARBAGE
8. mask=00000003 value=00000001: NO ANSWER
9. mask=00000003 value=00000003: GARBAGE
10. mask=00000007 value=00000003: ANSWER OK
Assigning new address for SN 0x00000003
11. mask=00000000 value=00000000: ANSWER OK
Assigning new address for SN 0x00000007
12. mask=00000000 value=00000000: NO ANSWER
The query 2 has no answer, so it's a lost of time to send again during
the algorithm (see query 6): it will never be answered.
I think this could be solved avoiding to restart the algorithm from the
beginning every time a new slave is found. I have the impression it
could be optimized with recursion, but I can't use recursion on AVR
small microcontroller (stack space is very small). I know every
recursive algorithm can be written without recursion, so it could be my
solution.
Is someone suggest an optimization of my technique?
Thank you.