0

# Slotted ALOHA Pr(All nodes successful @ time t)

Sun 31 Mar, 2013 02:35 pm
I'm trying to understand slotted ALOHA and I have a question regarding the probabilities.

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.

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 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!
• Topic Stats
• Top Replies
Type: Question • Score: 0 • Views: 2,666 • Replies: 10

markr

1
Sun 31 Mar, 2013 07:48 pm
@testietester,
The second one is close. You need to multiply instead of add:
3(0.5)(0.5)^(3-1) * 2(0.5)(0.5)^(2-1) * 1(0.5)(0.5)^(1-1)
You need the first one to succeed AND the second one to succeed AND the third one to succeed. "AND" implies multiplication when the events are independent - which they are in this case.
testietester

1
Sun 31 Mar, 2013 11:07 pm
@markr,
@markr

Thanks! But the problem I see with using the 2nd version is that I cannot extend it to t = 4. Unless I have the 4th one be 0(0.5)(0.5)^(0-1) = 0. Making the whole thing = 0. Doesn't seem right. I my way of thinking flawed?

Thanks again!
markr

1
Mon 1 Apr, 2013 10:32 am
@testietester,
If the frames are all sent by t=3, then the probability of 0 frames being sent at t=4 is 1. If you want the probability of 3 frames requiring 4 time slots to be sent, you have to recompute how that can happen - exactly one of the first 3 time slots must have had a collision.
testietester

1
Mon 1 Apr, 2013 12:15 pm
@markr,
So you're saying that it should be:
P(1 node successful) * P(unsuccessful) * P(next node " ") * P(last node " ") =
3(0.5)(0.5)^(3-1) * [1-2(0.5)(0.5)^(2-1)] * 2(0.5)(0.5)^(2-1) * 1(0.5)(0.5)^(1-1)

If this is the case, what if the collision happens in the first frame? Making it
[1-3(0.5)(0.5)^(3-1)] * 3(0.5)(0.5)^(3-1) * 2(0.5)(0.5)^(2-1) * 1(0.5)(0.5)^(1-1)

Should I OR(add) these 2 parts together?

markr

2
Mon 1 Apr, 2013 01:40 pm
@testietester,
Since the collision has to happen when there are 2 or more frames to be sent:
P(3, collision) * P(3, success) * P(2, success) * P(1, success)
+ P(3, success) * P(2, collision) * P(2, success) * P(1, success)
testietester

1
Mon 1 Apr, 2013 05:55 pm
@markr,
Thanks mark! +1
0 Replies

testietester

1
Mon 1 Apr, 2013 06:02 pm
@markr,
Actually, using t = 3 and p = 1/2 I get:

3(0.5)(0.5)^(3-1) * 2(0.5)(0.5)^(2-1) * 1(0.5)(0.5)^(1-1) = 0.04375

That doesnt seem right. Anybody know what went wrong? I already checked my calculations.
markr

1
Mon 1 Apr, 2013 07:00 pm
@testietester,
Isn't that 3/8 * 2/4 * 1/2 which equals 0.09375?
0 Replies

markr

3
Mon 1 Apr, 2013 11:19 pm
@markr,
Quote:
Since the collision has to happen when there are 2 or more frames to be sent:
P(3, collision) * P(3, success) * P(2, success) * P(1, success)
+ P(3, success) * P(2, collision) * P(2, success) * P(1, success)

I messed that up. Collisions aren't the only way to fail. All nodes (including the last one remaining) could opt not to send. Therefore, it should be:

P(3, failure) * P(3, success) * P(2, success) * P(1, success)
+ P(3, success) * P(2, failure) * P(2, success) * P(1, success)
+ P(3, success) * P(2, success) * P(1, failure) * P(1, success)
testietester

1
Tue 2 Apr, 2013 09:44 pm
@markr,
Thanks Mark!
0 Replies

### Related Topics

Probability of 11 cards - Question by ptkaisen
Probability - Question by sean2
Exercise in Probability!!! - Question by evinda
Winning chance - Question by ghodhereek
Family Wine Tasting - Question by mrmac
what is the probability of... #4 - Question by w0lfshad3

1. Forums
2. » Slotted ALOHA Pr(All nodes successful @ time t)