On Colliding First Messages in Slotted ALOHA (Invited Paper)
Christian Bettstetter, Günther Brandner, Robert Vilzmann · 2008
Abstract —Considering n nodes performing random accessusing ALOHA with s slots, we study the probability that thereoccurs a non-colliding message in the first non-empty slot. If eachnode transmits with probability p in each slot and the number ofslots is sufficiently large, a non-colliding first message occurs withprobability Φ=1 −np/ 2 for large n and small np . If the numberof slots is limited, the probability Φ is lower but can be maximizedchoosing an optimal p . To maximize Φ further, nodes can applya slot-dependent transmit probability p i with i =1 ,...,s .Itisshown that a “slow start strategy,” in which p i is low for low i andincreases with increasing i , is beneficial. Our main contributionis an equation for the p i values that maximize Φ . We analyzehow a higher probability of a non-colliding first message comesat the price of an increased delay of such a message. Besidesbeing of interest for the theory of random access, the results arepractically applicable to node selection protocols, such as relayselection in cooperative wireless networks.