Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Slotted ALOHA P(All nodes successful @ time t)

  1. Apr 1, 2013 #1
    I'm trying to understand slotted ALOHA and I have a question regarding the probabilities.

    Here is an example: I have 3 nodes, ready to send a frame each. The probability of them sending = 0.5. What is the probability that at time 3 (3 time slots later) they will have all been successful? I know that: P(given node successful) = p(1-p)^(N-1) P(any node successful) = Np(1-p)^(N-1)

    I have a couple versions of the answer and I'm not sure which one is correct(or none at all):

    1) P(node 1 success) + P(node 2 " ") + P(node 3 " ") = 3*[0.5(1-0.5)^(3-1)] = 3/8

    OR

    2) P(1 node successful) * P(next node " ") * P(last node " ") = 3(0.5)(0.5)^(3-1) * 2(0.5)(0.5)^(2-1) * 1(0.5)(0.5)^(1-1)

    I'm leaning towards version 2 of my answer, but I don't see how to extend it to t = 4.

    I don't remember much from my discrete math days. But I'm leaning towards the first one(or a variation of the first one). Please help me clear this up.

    Thanks for looking!

    In case you didn't know slotted ALOHA works like this:
    You have nodes, ready to send "frames" of data. They send every time slot, but when more than one node sends on the same time slot there is a collision and the frames don't make it to its destination. That is why every node sends at the beginning of every time slot based on a certain probability. If there is another crash, the nodes involved resend their frames based on probability p. This continues until eventually only 1 frame is expressed on a time slot, and it is sent successfully.
     
  2. jcsd
  3. Apr 3, 2013 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    If the nodes are numbered 1,2,3 then you can consider all possible orders in which they succeed. There are 3! = (3)(2)(1)=6 possible orders. For each order (such as 2,1,3) the probability of that sequence of successes is the same. Its p(1-p)(1-p) p(1-p)(1-p) p(1-p)(1-p). (For example, if you wrote the factors for the sequence of successes 2,1,3 in order, they would be ((1-p)p(1-p)) ((p)(1-p)(1-p)) ((1-p)(1-p)p) and these factors can be rearranged.) The probability of success is the sum of the probabilities of success in particular ways, so it is 3! (p(1-p)(1-p))^3.

    When you say "extend to t=4", do you mean to extend both the number of nodes and the number of time steps?
     
  4. Apr 3, 2013 #3
    @ Stephen Tashi

    Thanks for the reply. By t=4 I mean the time slots have been extended to 4. There are still 3 nodes with a frame to send. But, we now have 4 time slots to get them all sent.

    Because failures can happen because of collisions, or simply because nodes choose not to send(they send with probability p) I would have to OR(add) in the cases where the first slot empty, 2nd slot empty, and 3rd slot empty. The 1 and 2 slot can be empty due to collisions/choosing not to send. But the only way for the 3rd to be empty is just choosing not to send. I think....

    Also, why is it p(1-p)(1-p)? Plugging in p=0.5 gives 3!(0.5(0.5)(0.5))^3 = 0.01171875. Seems a little low.

    Thanks again!
     
    Last edited: Apr 3, 2013
  5. Apr 3, 2013 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    What do you mean by "it"? p(1-p)(1-p) represents the probability of one node transmitting in a time slot and the other two being quiet.

    I don't know what you are comparing this number to. I glanced at documents on the web that analyze "slotted ALOHA" and they analyze it as a continuous process, not as a synchronous process that proceeds in time steps. So your analysis isn't an analysis of what the web calls "slotted ALOHA".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook