Custom response time from slaves to avoid data collision

[Remark]

Hello,

For some time and for learning purposes I try to program my custom protocol based on the UART serial communication. With this 'protocol' I am polling some devices connected to tx rx lines. However, I had a big problem with those devices responding at the same time. After polling one device, I get an answer from several and so the data becomes erroneous... I have been trying to solve this problem for a long time but i don't know how I can delay the response time of those devices. Maybe there is some mechanism that allows data to be queued or sorted so that it can be read? I am thinking of generating a random time interval between responses but i don't know if this is the right solution if there are multiple devices on the line. This increases the overall response time. Maybe you’ve done something like this and could you steer me in some direction? Thanks for any thoughts.

[SiliconWizard]

Not quite sure I get your setup here, you don't give many details. But the easiest and most common way of dealing with multiple devices on the same bus is to assign them some kind of "address", and having a "master" initiate the communication. Like with I2C. So only the device being addressed would reply.

[ataradov]

If those devices are try UART's then they would be driving the bus no matter what, even when they are not actively responding. Your transmitting devices will be fighting over the bus, this is not great.

So you need both individual addressing and ability of transmitting devices to go into Hi-Z state to not drive the bus when they are not active. Depending on your MCUs that may be doable by temporarily switching TX pin to a GPIO input.

Or just switch to I2C.

[NorthGuy]

Use RS-485 - this is a hardware configuration for sharing UART communications. The easierst is to install a RS-485 driver chip for every device. The driver allows the device to decide when it wants to transmit and when it wants to receive. There are many protocols for RS-485, most common one is ModBus.

[fourfathom]

Are these devices known before they are attached to your comms bus?  If so you can do as SiliconWizard suggests, or if you want to hear from them all with one query them you can pre-assign each with their own delay (or relative timeslot), perhaps using their ID # to determine the delay value.  You can still send an ID#Query for a non-delayed response from a single addressed device.

If the devices are initially anonymous then you might need some sort of ACK/NAK protocol with something like the ethernet exponential backoff technique.

And yes, ataradov is correct about the drivers needing Hi-Z on idle.

[jwet]

This is a very classic problem in networking and has been solved in a myriad of ways.  Assigning addresses is common.  Each slave would have some way of being assigned an address.  In many industrial networks, this is something like a DIP switch.  There are also automatically configured network who get an address at start up or on demand.  This often involves each slave having a way to block any downstream traffic, respond themselves, accept an address, open its downstream port and let the next downstream slave do its thing while it remains quiet.  Often these downstream switches are relays that  drop out without power so that let the signal flows through on an unpowered node.  Once everyone has an address in either system, the master polls each address.  One of the downsides of this is that if a node drops off and then returns, the string has to be reconfigured- this can take some time because of all the nodes and the necessary timeouts, etc.    A twist on this is to use a 9 bit scheme on your uart (many do this or you can use parity and manually set the parity bit).  Only the first message that address a new node has the ninth bit set from the master.  This allows the slaves to ignore all message traffic until another ninth bit interrupt occurs.  This is a pretty good system but you can imagine places where it will fail.  Stuck nodes and dead nodes is one first order problem.

More sophisticated systems like early ethernet used carrier sense multiple access with collision detect (CSMA-CD).  Wikipedia explains this better than I can but in brief it involves checking the bus for activity and not transmitting if there is stuff on the bus.  Coupled with this is collision detection system because two nodes could choose the exact same moment to start  talk.  This requires messages to have checksums or CRC codes embedded to tell if the message got clobbered- on some busses like 485, you can read back what you sent in the common half duplex case.  Often there is a random back-off after a collision so the two don't just fight each other forever.  This works well if the bus is fairly lightly loaded- you have short messages and a fast medium.  As the bus gets busier, its harder for anyone to find a slot and the collisions increase and the whole thing falls apart.  You can also have a stuck node that just keeps talking and can take down the bus.  Various schemes have been used to fix these issues.

IBM networks and some industrial networks use a "token" passing system.  There is a token- a permission command- that is passed around and the node with the token can talk and then relinquish the token.  This can be pretty efficient but provisions have to made to create a new token if it gets clobbered (usually with a timeout).  This can all be masterless, ie peer to peer if the token is passed from node to node and instantly relinquished if not needed.

Still other systems uses things like TDMA where each node is given a time slot that depends on it address.  If it has something to send, it waits for its slot and sends otherwise the slot goes unused.  This has the disadvantage of wasting bandwidth but is robust and deterministic if all the nodes talk pretty often.

You can also have protocols like CAN where the address with the most zero's (or 1's) wins,  If the bus is open collector- like, the node that pulls the bus down with the most zero's will win.  This kind of creates a priority structure for the nodes.  This takes a bus like CAN that has dominant and recessive states.  Cars and a lot of industrial system uses CAN.  This is just the PHY layer of CAN, CAN is also a protocol.  Some industrial networks use the CAN protocol running with RS-485 phy's- some industrial fieldbusses.

 Cars have several networks these days- Fly by Wire- steering and brakes use protocols like Flex-Ray that is completely deterministic at the cost other things.  Drivetrain systems often use CAN bus which is very robust and expandable.  Body electronics can use low Speed CAN, single wire CAN, LIN or other simple one wire protocols that don't require much sophistication in the nodes (a window button cluster).  Mutlimedia in cars use a variety of protocols like MOST or MOST over copper.  Increasingly Ethernet is finding its way into modern cars especially for streaming and infotainment.

Do some web searching- this is well travelled but interesting ground and a lot  of clever solutions have been put together.  Like all of engineering, each solution has its tradeoffs, in efficiency, bus utilization, determinism, software or hardware simplicity, robustness, etc.  A very rich topic worthy of some study.

[ajb]

In a true polled system--where no device sends a message except in response to a message from the controller--addresses are probably the simplest way to solve this problem, and they provide a lot of other useful or necessary functionality as well.  The trick is reliably assigning them uniquely.  With a large enough address space, each device can have a permanent unique ID, but then you need a method for determining what those IDs are (you can't simply query every single one, that would take too long).  Smaller address spaces can be discovered by brute force, but will need to be explicitly configured to ensure there are no collisions.

ANSI E1.20 has a nice way of dealing with this, allowing a controller to discover the unique fixed 48-bit unique ID of every device on a bus relatively quickly via binary search.  That unique ID can then be used to direct subsequent messages, and/or to assign an address.

- Controller broadcasts a discovery message asking every device with an address >= X and <= Y to send a response.  Responding devices send a message containing an encoded form of their unique ID and a checksum. 
- No response means no devices in that range and the controller will try the next range.
- A correct response means there is exactly one device in that range, and the controller now knows its ID.  So the controller can add that device to its internal list, and send a message to "mute" the device, so that it will not respond to further discovery messages.
- A garbled response means there is more than one device in the range (because their responses collided), so the controller will bisect the range and try again.

By the end of the process, the controller has a list of the unique IDs of all devices present.  The controller can periodically send discovery messages covering the entire address range to see if any new devices have joined the bus--because all of the previously discovered devices should be muted, only undiscovered devices or devices that have been power cycled or otherwise reset will respond.

[TomS_]

I am thinking of generating a random time interval between responses but i don't know if this is the right solution if there are multiple devices on the line.

Random delay is not likely to fix the problem. For one, what is to stop two devices deciding to use the same or very close random interval and clashing with each other again anyway? And then how do you know which device has replied at any given time to handle its data appropriately?

As others have suggested, you need to be able to address a specific slave to ask it for its data, so that only one transmitter will be active at a time.

If the master and slaves are in close proximity to each other, then as ataradov suggests, switching the TX pin of the slaves into a high impedance state when they are not addressed and needing to transmit is a near zero cost solution. If the devices are spread far and wide, then RS485 would very likely be a good idea for signal integrity - but only once you have the software sorted out to not cause collisions.

But simply adding RS485 drivers wont fix the problem if the software doesnt control the transmitter correctly and they still try to talk over each other.

[Siwastaja]

Logic level uart (straight from microcontroller) allows you to tri-state the slave's TX pin (for example in STM32 by setting the IO from AF mode to GPIO mode and configuring the pin as input), making this physically possible. In RS232, this isn't physically possible without extra switch ICs. RS485 OTOH is physically designed to do this, so use it if you need better signaling robustness than logic-level UART allows.

Contrary to the impression you get from some of the above posts, RS485 solves absolutely nothing for you, it's still up to you to provide the right software logic. And if you are fine with the signal integrity from logic level signaling, RS485 has then no advantages.

Software logic is indeed very easy using the addressed polling scheme:

Each slave has unique address, for example 1, 2, 3, 4, 5.
Slave keeps its TX pin hi-Z, and never initiates communication.
Slaves always listen to their RX pins, though.
Master initiates communication by sending an initiation command containing the slave address. This same message can contain the full command of whatever.
Only the slave which has address match reacts to the message, enables its TX pin, and sends reply. This reply must contain some way to signify when it ends. Slave disables its TX pin again.
Master gets the message, knows it ended, and knows it can safely poll the next slave.

In the simple logic-level version, using a series resistor (say 47R) at each slave TX pin greatly reduces the risk of MCU IO cell damage in case of software errors causing two slaves to enable their TX at the same time.

[tggzzz]

After polling one device, I get an answer from several and so the data becomes erroneous...

That is the problem you have to sort out: you aren't polling one device. It sounds like either it is a hardware problem or a configuration problem.

[Siwastaja]

Of course, having deterministic timing like in UART where every baud takes the same time to transmit, there is nothing wrong in implementing a system where you have a general "poll all" command, and then every slave uses a different, fixed delay so that they shout the results back-to-back, with just enough margin to make up for crystal differences and those few CPU cycles of jitter you get triggering the transfer. This way, you can save time by avoiding sending many poll messages.

Or you don't even need to use fixed delays, make the slaves transmit in predefined order, swap the UART RX/TX pins (many MCUs can do that in peripheral configuration) so you can listen what other slaves are transmitting, then slave 2 waits for the end-of-transmission of slave 1, swaps the pins back and starts its own transmission, and so on. This way no extra guardbands are needed.

But this is order of magnitude more difficult to engineer right. It's not impossible, but you should start from simple and avoid premature optimization. If you keep the poll command short, there is little potential for time savings.

[DavidAlfa]

What's your MCU? It might support RS485 by itself, but if it doesn't, you don't need any additional circuitry, just smart software.

- Use simple packets like  { [address][total packet size][data][checksum] }
- Since there's just one master, receivers answer can use the same address.
- Using 8-bit address will be enough up to ~250 devices.
- Like in IP, 0 and 255 addresses are reserved. 255 is broadcast.
- All receivers disable their TX lines when not transferring data.
- Master sends reset command using broadcast address to reset all receivers.
- Master starts sending "Anyone" cmd using broadcast address to discover the devices.
- Each device waits (address value * 10us) before trying to answer. Lower addresses answer first. Response includes the address.
- Any device waiting to send its address will go back to idle when detecting communication (A lower address answered first).
- Devices that have already answered to Anyone request won't answer to it anymore unless there's a master reset.
- Master stores the slave address and repeats "Anyone" procedure until timeout, then assumes there's nobody else.
- The timeout value should be 255*10us=2.55ms, + UART transmission time.
- From now, master will send addressed packets to talk to receivers.
- All receivers will be listening, but unless it's broadcast or own address, packet will be ignored.

That should remove any collision.

[Remark]

Thank you very much for all the comments. I want to say I have to assign slave addresses automatically. I am currently working on data collision detection. And now I am writing a handler that should detect this and allow all slaves to respond in a row.

[tggzzz]

How do you ensure that all slave addresses are different? If two happen to have identical addresses, then fairly obviously that could cause collisions.

[DavidAlfa]

What's clear is slave devices should have different delays when answering to a broadcast message (Ex. when sending "Who's there?" ), otherwise they'll all try to answer at the same time.
Most MCUs have some kind of unique ID/serial, or user programmable ID.
Also, there're cheap eeproms that come with a unique MAC address programmed inside.
Ex. AT24CSW010-STUM-T, $0.13 each, comes with a unique 128bit number.
If 128bit is excessive for the protocol, it could be converted to ex. 8bit using some checksum calculation like CRC-8, only would need to be done at power-on.

[tggzzz]

What's clear is slave devices should have different delays when answering to a broadcast message (Ex. when sending "Who's there?" ), otherwise they'll all try to answer at the same time.

If that is assured, then it is equivalent to having different addresses.

[Siwastaja]

Using the unique chip ID as the address is simplest but results in quite long addresses, unless you hash them but the shorter the hash, then the higher the possibility of collisions. The best would be if you find information on how manufacturer builds the unique ID and remove any unnecessary bits.

You can of course assign unique addresses based on randomization and collision detection, but the end result is that if you reassign the IDs, the result will be different each time. With pseudorandom algorithm (say, seed = unique chip id), it may practically look like the result is the same every time, but it's hard to guarantee.

What is wrong with manually setting the addresses? You are going to flash the microcontrollers one by one anyway, yeah? Assign addresses during that. It can be a value on a separate flash page that won't get cleared during FW updates.

[SmallCog]

If you’re looking for inspiration have a read about SDI12. It’s a very simple protocol that’s lasted a long time.

Most commonly used in environmental/weather/agricultural sensors

I have no idea what you’re making, perhaps it’s irrelevant, perhaps it’s interesting

[Berni]

Even using a chip ID as a address can be problematic because these IDs are very long like 64bit for example. So you can't scan trough all of them to find who is on there, instead you need to develop an identification protocol much like what Dallas OneWire sensors do.

The easy way out might be to instead use a bus that is itself collision avoiding such as CAN Bus. It supports messages with a 29 bit long address so you could just stuff the LSB of the chip ID in there. Even if there are two devices with the same address they will still collision avoid each other(they can still collide on the rare occasion they transmit exactly simultaneously, but they will know and re transmit). All of this is handled by the CAN controller itself so once you have a working driver it should just magically work.

[DavidAlfa]

Well, that's exactly what I said, computing CRC-8 from 8/16bytes is not NASA tech.
But you don't need to, and while improbable, it's not impossible to get the same CRC in different devices, so I'd try to avoid that.

Bruteforcing is an extremely unefficient method, I keep thinking creating different delays from the address, then simply poll the bus and wait for the slaves to identify themselves, is the best option.

You could dynamically assign addresses, but still need some kind of randomizer to reduce bus collision. Like a random numer generator (Ex. reading an ADC pin connected to an antenna to pick random noise)

Most programmers have factory production mode where you can set a serial number, and will increase the counter after each programming.
Still, not ideal and might slow down the production. A MAC eeprom will completely avoid this.

The easiest way would be to use daisy-chain bus, so the message would be passed to the next one if not belonging to the current device.

This is a good reading:
https://users.ece.cmu.edu/~koopman/ece649/lectures/13_protocols.pdf

[Siwastaja]

CAN is indeed a very good - and still simple enough - pre-engineered solution, the priority-based collision detection and retry mechanism works well, all you need to do is a napkin/Excel calculation proving the intended messages fit into the bus bandwidth.

If you are not familiar with CAN, the idea is that you come up with an identifier number for the data, which works also as a header telling you what the payload describes. This ID can contain some bits describing your node ID, some bits what data it is... It's up to you.

Then, if multiple devices try to transmit similarly, higher-priority identifier (lower number) wins and the lower-priority message waits. Your task is then defining which packets are more important to receive without delay, and come up with identifier number accordingly. Availability of CAN peripherals in microcontrollers enable automated whitelisting of just the data you want to hear.

This being said, anything with CAN is even more unobtanium than everything else right now.

But quite seriously, I'd consider going with programmable IDs. What's wrong with that? Too much automation, at some point, makes things difficult.

[Remark]

Yes, of course it's not a nasa level prolem. Sorry I didn't provide more information about the issue. My "slaves" are just simple 32-bit STM32 microcontrollers, running multiple adc channel scans. And my master is also STM32 but it running slightly different software. It's not some serious device, just trying to make some kind of communication protocol based on uart.

Currently, I have generated smaller ID for each slave. And one of my tries was to discover them by using bruteforce. For a small amount of slaves, this method has proved its worth. Now I'm wondering if I had more devices, in theory, there would certainly be a chance that the ID addresses would collide someday. You have given a lot of good advice, I will try to rely on them and try to solve this problem.

[free_electron]

intel came up with a nice solution for that. they use the 9th bit in the uart as an address/data flag.
so you can transmit the first byte with the 9th bit set to send out the" address" . the rest of the data telegram is sent with the bit cleared.

so {[1][0xTT]}{[0][0xLL]}{payload0 .. payloadn}

TT = target address
LL = packet Length

every packet MUST be acknowledged. so after reception of the last byte ( that's why you transmit length ) the slave must respond with at least an 'acknowledge' byte. followed by a payload

now the trick lies in the ability of the uart. intel's uart ( in 8051 and 8096 micros) has the ability to fire an "interrupt on receive" but can discriminate between 9th bit set or cleared. certain version of the uart can actually do the compare on the byte received. so the interrupt will only fire if the byte matches. your main program only gets an interrupt when you are being adressed.
if you make the byte frames all the same length you can make a time deterministic system.

https://community.silabs.com/s/article/uart-using-9-bit-mode-of-the-uart?language=en_US
https://www.electronicdesign.com/technologies/embedded-revolution/article/21763399/use-the-pcs-uart-with-9bit-protocols

[Siwastaja]

9-bit UART, if supported (sadly, not all MCU peripherals do that), is indeed a lifesaver if you want to add easy and robust framing.

Though, that does not address (pun intended) the OP's question at all, which was about how to assign the addresses without collisions, not about framing, which, I assume, has been taken care of somehow already.

I prefer to use fixed, configurable addresses and just come up with some easy way to configure them. For example, a software tool which instructs the user to power up just one unit at a time, then program it with the ID of your choice using some special sequence recognized regardless of the configured ID - which would cause collisions if multiple units are powered on. And the user can attach a label.

One option is to change the topology from bus to a chain, still doable with UART. In a chain, automatic assignment of addresses is trivial and results in nice incrementing numbers if that is what you want. Then, a command would be relayed until it hits the target, after which the others relay the reply. A special "assign ID" message would contain an ID field, starting from 1 for example, and every node would increment this field and relay the command.

[DavidAlfa]

The 9 bit uart doesn't fix anything, just provides an easier way of addressing.
Checking the 1st byte as address would be the same thing.
Every stm32 has a UID, so that's a start.