Optimal retransmission algorithm for a broadcast channel

Question

I have a number of microcontrollers which can communicate over a broadcast medium (in this case, IR). Each node wants to announce its presence to all the other nodes on a regular basis, but since it's a broadcast medium, two nodes transmitting at the same time will create a collision, and neither message will be transmitted correctly.

To further complicate things, when a node receives an invalid message, it doesn't seem practical to reliably determine if this is due to a collision or due to background noise or weak signal. Also, while node visibility will usually be reflexive (A seeing B means B can see A), it will usually be the case that not all nodes can see all other nodes.

Leaving aside external interference for a moment, it seems like a rational approach is to create timeslots, with each node transmitting in each time slot with a small (and ideally similar between nodes) probability. If there are n nodes that transmit with probability p, then no message will be transmitted (1 - p)ⁿ of the time; exactly one message will be transmitted n * p * (1 - p)^n-1 of the time, and the remainder of the time there will be a collision. The maximum incidence of successful collisions occurs when each of the n nodes transmits 1/nth of the time, and this results in a fairly stable 38% successful transmissions and 24% collisions; this value changes only slightly with increasing numbers of nodes.

Given that, it would seem we could observe the rate of successful transmissions and/or collisions, and adjust our own transmission rate to try and force them towards their expected values. What I'm not sure about is what the best feedback mechanism to achieve this is, such that everyone ends up with similar probabilities. This also doesn't account for external interference, which will cause us to keep decreasing our transmission rate in a doomed effort to avoid collisions that don't exist.

What is the optimal algorithm - either a refinement of the above or a totally different approach - to maximize the proportion of announcement messages each node can receive without collision?

Answer 1

What you want is actually a wireless mesh network, which is a whole reseach field by itself. Apart from that acknowledgement messages are a good idea. You can piggyback them with the announcements themselves if packet overhead is a concern. They allow to distinguish between collisions and background noise by observing how many neighbors answered and allow basic rate limiting by waiting until (most) neighbors acknowledge each transmission (stop-and-go). This gets of course even more complicated if the controllers are very mobile.

It will be very hard (and probably not desirable) to maintain a equal update rate over the whole network, because transmission quality can vary wildly in different areas and points in time.