Slotted ALOHA Pr(All nodes successful @ time t)

Forums: Probability, Computers, Events, Networking, Combinatorics
Email this Topic • Print this Page

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
Link to this Topic

Type: Question • Score: 0 • Views: 2,817 • Replies: 10

[+3] - markr - 04/01/2013[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,...

@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.

1 Reply

@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!

1 Reply

@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.

1 Reply

@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?

Thanks for all your help!

1 Reply

@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)

3 Replies

@markr,

Thanks mark! +1

0 Replies

@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.

1 Reply

@testietester,

Isn't that 3/8 * 2/4 * 1/2 which equals 0.09375?

0 Replies

@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)

1 Reply

@markr,

Thanks Mark!

0 Replies

Slotted ALOHA Pr(All nodes successful @ time t)

Related Topics

Quick Links

My Account

able2know