Automatic node naming algorithm?

[Artlav]

On a single wire UART bus there is a bunch of nodes and a master.
All nodes have identical code and memory.
Thus, none have a node id assigned, or any other means of addressing them directly.

Is it possible, in general case, to assign node ids to all of them automatically (i.e. without going to each one with a programmer and flashing it), using the bus?

Case A - general case, with ideal parts and no differences.
I can't think of any algorithm that can do this - there is nothing for any two of the nodes to diverge on.
But maybe i'm just missing one?

Case B is more real-world - there would be differences in the nodes, since they are based on a real world attiny85 MCU.
Attiny85 have an RC oscillator, that is factory-set to within 10% of it's nominal value.

This can be used to differentiate the nodes.
1. All of them start with a last_node variable with a value of 1.
2. Wait for a large amount of cycles, while monitoring the bus. The wait amplifies the small oscillator differences.
3. The first to emerge from the wait pulls the bus low.
4. Every other node sees this, abort their count, and start listening.
5. The first node takes the id of last_node, increments it, transmits it, and goes into standby.
6. The other nodes set their last_node to the received value, then goto 2.

If there are no nodes left, then after no activity on the bus for several maximum wait periods all the named nodes go out of standby.

In case new nodes are added or process being terminated before completion, it can be restarted by a broadcast command including a highest known node number, upon which the named nodes go into standby, and unnamed ones begin the enumeration as described.

Obvious problem #1: If two nodes get perfectly matched oscillators, then they will get the same number, and no way to tell them apart or detect a collision.

Would this work?
Any way to do it better?
Finally, does this have a name i can google?

[mikeselectricstuff]

There are a few ways, depending on your requirements.
In most cases you will want to know the mapping between the ID of a node at a particular physical location.
One way of doing this is to have some local input  that can be locally sensed - e.g. a pushbutton, pads that can be shorted, a light sensor, accelerometer etc.
You broadcast a command on the bus that says "You are node x, but only if you see your external input active".
You then go round activating each node in turn while incrementing the address being sent by the master.
A development of this is if you can arrange for the master to get status back - either by a node sending on a bidirectional bus, or by sensing a change in power draw.
Then the master can detect when a node has been programmed, and increment the address by itself.
That way you just start it off and activate each node in turn - job done.
 

[free_electron]

Simgle wire id prom
Or, allocate a few bytes at top of flash to hold a serial number. During firmware flash you then write different numbers there.

[AndyC_772]

There has to be some unique way to differentiate them, at least once during initial bring-up.

It's easy if instead of being on a multi-drop bus they're daisy chained. You just send a message that means "you are node zero; increment that number then pass it on".

If they're all in parallel, though, then you'll have to do something unique on each one in turn. In any case, the chances that you'd want them assigned randomly are pretty small, I'd have thought.

I like Mike's idea, and I'm guessing it's probably something he's done on a fair number of occasions...!

[T3sl4co1l]

Hmm...

If you have a source of randomness (a few bits worth during configuration), you could do something shitty like...

Master: "Generate random address."
Master: "Report address."

(in unison)
Node 0: "I'm node 0"
Node 1: "I'm node 10"
Node 2: "I'm node 6"
Node 3: "I'm node 0"
...

(You'll need something like I2C to arbitrate different nodes -- at least, the ones that split up.)
The lowest (bitwise) wins arbitration, so the master records address 0.

Master: "Everyone but node 0, report address."

(in unison)
Node 1: "I'm node 10"
Node 2: "I'm node 6"
...

Master reads 10 (or 6, depending on which direction the bitstream goes; I forget).

And so on.  Repeat until no more unique node addresses are reported.

Now we have addresses, but we don't know if we have collisions.  So,

Master: "Node 0, pick a new random address."
Node 0: "I'm node 27"
Node 3: "I'm node 0"

And so on, through the same enumeration process.

Now: this will NOT guarantee zero collisions.  If the statistics of your RNG are good, you can guarantee a probability, and after repeating the splitting process over all nodes (so this becomes an O(N^2) or worse algorithm), you can guarantee P chance of getting no collisions within O(N^2 / P) sort of time.  Or something like that.  That's very crude, and the real answer depends on choice between space (do you reserve the 127 addresses of I2C, or implement your own identifier of whatever size in the data format?) and number of nodes (>64 nodes is very likely to have a collision for each split command, <12 is fairly unlikely to).

If the master has knowledge of total nodes, it can count them, and terminate the algorithm when all have been found, but it has no way to tell which ones have collided, so the process still goes slowly.

Problems like these are best avoided at design time (e.g., daisy chain), or with external means (IDs, manual enumeration, etc.).

Tim

[mikeselectricstuff]

(You'll need something like I2C to arbitrate different nodes -- at least, the ones that split up.)

You can use time-slotting to avoid most collisions on a 1-wire bus.

[T3sl4co1l]

(You'll need something like I2C to arbitrate different nodes -- at least, the ones that split up.)

You can use time-slotting to avoid most collisions on a 1-wire bus.

That sounds rather tight for an MCU implementation (slot times limited by... propagation delay..?).  Assigning random response delays would probably result in a wider spread than assigning addresses, good point.

I don't see that a fixed (master defined, or preprogrammed) slot time would avoid the problem though?

Tim

[mikeselectricstuff]

(You'll need something like I2C to arbitrate different nodes -- at least, the ones that split up.)

You can use time-slotting to avoid most collisions on a 1-wire bus.

That sounds rather tight for an MCU implementation (slot times limited by... propagation delay..?).  Assigning random response delays would probably result in a wider spread than assigning addresses, good point.

That's what I meant - response delay derived from device ID

[Artlav]

All but Mike's proposals require some sort of randomness or a presence of an id in each node, which is exactly what i was looking for to avoid.

But i like Mike's idea the best - just add a microswitch to each board.

The idea was to have a few dozen LED modules one one power+signal line, each individually controlled.
I didn't want to recompile the code with a node ID in each one of them, but to send one firmware instead, and let it do the naming.
The order of assignments didn't matter much - i could blink them one by one and write down whatever numbers they came up with.

However, now that sounds like an overcomplicated software solution to a problems that is solvable simply by adding a single switch.

Thanks all for input.

[Dago]

Very many microcontrollers already have a factory programmed unique ID. Check if yours does and use that. For example STM32 ARMs have a 96bit unique ID.

If your bus has the nodes in parallel then I can't think of any way to ID them without extra hardware features or a programmed ID. If the nodes are daisy chained then you can number them based on their order.

[mikeselectricstuff]

I didn't want to recompile the code with a node ID in each one of them,

Many device programmers have the option to put a sequential number into a location in eeprom or flash

[Svuppe]

All but Mike's proposals require some sort of randomness or a presence of an id in each node, which is exactly what i was looking for to avoid.

If random values are needed, I usually make a little transistor based noise source, and input that to an A/D channel (if the cpu has one). Then just use a few of the least significant bits X times, until the random word is the size needed.

[nctnico]

The best way is to use one or more rotary switches with 16 positions. That way people can tell which device is where. If you shop around a bit these can be found quite cheap (Wurth for example).
Creating a 'random' ID is also possible. There is an algorithm to have a device self assign an IP number on a network (auto IP).

[AndyC_772]

Are all the nodes powered up simultaneously? Can you not devise an algorithm in which there's a dialogue along the lines of:

Master: "If you don't already have an ID, then you are node 1. Tell me when you've taken this ID"
Master: "If you don't already have an ID, then you are node 1. Tell me when you've taken this ID"
Master: "If you don't already have an ID, then you are node 1. Tell me when you've taken this ID"
<new node powers on>
Master: "If you don't already have an ID, then you are node 1. Tell me when you've taken this ID"
Node: "I claim ID 1"
Master: "If you don't already have an ID, then you are node 2. Tell me when you've taken this ID"
Master: "If you don't already have an ID, then you are node 2. Tell me when you've taken this ID"

Repeat until all nodes have been powered up.

[mikeselectricstuff]

The ATtiny85 has an on-chip temperature sensor that is a great source of random noise. Just use the ADC to sample some random low order bits and generate a random ID. Alternatively you can use the random bits to do a listen-before-talk mode for your comms, and then just have the master send out "set ID" messages until all nodes have a unique ID.

You could also use the temp sensor as a manual input for my scheme - have it adopt the transmitted ID if it sees a sudden temp change - trigger with finger, hot-air gun or freezer spray

[Rufus]

What is the point assigning node numbers randomly?

What commands is the master going to be sending to a specific node on the bus without knowing or caring which specific node it is?

[nctnico]

In some cases you don't need to know where a unit is. A couple of years ago I designed an audio distribution system with remote controllers (pushbuttons and a display). The remote controllers on that system can be paralleled. It is handy to know how many are connected to make sure every remote controller has received the  message or whether it has to be send again.

[T3sl4co1l]

If you don't mind adding one more line, you could get an analog count based on how many resistors are pulling it down.  Well, this doesn't even need to be an additional line, it could be mux'd onto an existing line as a special function.  For large numbers of nodes, you'd probably want to have multiple "ranges" available so you can still get an accurate measurement; even so, good luck over 50 or thereabouts (unless you want to buy better than 1% resistors), unless an approximate count is okay.

Tim

[David_AVD]

In some cases you don't need to know where a unit is. A couple of years ago I designed an audio distribution system with remote controllers (pushbuttons and a display). The remote controllers on that system can be paralleled. It is handy to know how many are connected to make sure every remote controller has received the  message or whether it has to be send again.

Can you elaborate on what method you used?

[nctnico]

I used the delay of the LCD display to get a random number (0..255) to create an ID. When a remote controller receives an 'initialise' message it sends this random number to the master as a cookie. The master uses the number of answers to an 'initialise' message to count the number of slave devices and give them a unique number. To avoid collisions the remote controllers use the random number also a variable delay for sending a response. There is some recursion to sort out double numbers etc.

[Frant]

On a single wire UART bus there is a bunch of nodes and a master.
All nodes have identical code and memory.
Thus, none have a node id assigned, or any other means of addressing them directly.

Is it possible, in general case, to assign node ids to all of them automatically (i.e. without going to each one with a programmer and flashing it), using the bus?

I assume that you use the UART TX and RX lines hard-wired together in each node. Instead of that you can use a normally open CMOS switch between the two lines and allow the node's microcontroller to connect the two signals only when needed. Instead of a bus, this would lead to a daisy-chain topology where the TX line of a previous node is connected to the RX line of the next. The first node (i.e. the one closest to the master) will see the TX signal coming from the master, and the last node will have its TX line unconnected. Before the address assigning procedure begins, the TX lines of all nodes should be in their inactive state, and each node should be able to receive data over its RX line. Now the master sends a special addressing message and only the first node receives it. The first node obtains its address from the master. After that it connects its TX line to the RX line, thus enabling two-way communication with the master. The master interrogates the node in order to check its presence. Since the TX and RX lines of the first node are now connected, the second node can receive all the messages sent by both the master and the first node. It should react to the addressing message sent by the master in the same way the first node did (the only difference is the address). The process continues until all the nodes have their addresses assigned. At the same time, the initial daisy-chain topology has been transformed into a single-wire two-way bus.

The proposed method has the following advantages: it uses only 2 digital lines per node and only 1 digital line on the master side, it does not depend on analog signals or mechanical switches, it is deterministic and it detects the relative positions of the nodes. One disadvantage is that if one of the nodes fails during the address assigning procedure, all the subsequent nodes will be inaccessible.