Slotted ALOHA P(All nodes successful @ time t)

[testietester]

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.

 

[Stephen Tashi]

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?

 

[testietester]

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

 

[Stephen Tashi]

Also, why is it p(1-p)(1-p)?

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.

Plugging in p=0.5 gives 3!(0.5(0.5)(0.5))^3 = 0.01171875. Seems a little low.

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

 

[blue_raver22]

Hello,

Thank you for your question. Slotted ALOHA is a popular protocol used in wireless communication to improve network efficiency. It works by dividing time into slots and allowing nodes to transmit data only at the beginning of each slot. This helps reduce collisions and improve the chances of successful transmission.

To answer your question, let's first clarify the notation used in your examples. In your first answer, P(node 1 success) refers to the probability of node 1 being successful in transmitting its frame in a given time slot. In your second answer, P(1 node successful) refers to the probability of any one node being successful in transmitting its frame in a given time slot.

Based on this clarification, your first answer is correct. The probability that all 3 nodes will be successful at time 3 is equal to the sum of the individual probabilities of each node being successful. This can be calculated as follows:

P(all nodes successful at time 3) = P(node 1 success) + P(node 2 success) + P(node 3 success)
= 3*[0.5(1-0.5)^(3-1)] (using the formula for P(given node successful))
= 3/8

Your second answer is not correct because it assumes that the success of one node is dependent on the success of the previous node, which is not the case in slotted ALOHA. Each node has an equal chance of being successful in a given time slot, regardless of the success of other nodes.

To extend this calculation to time 4, you can simply use the same formula and replace the values of N and t accordingly. The probability of all 3 nodes being successful at time 4 would be:

P(all nodes successful at time 4) = 3*[0.5(1-0.5)^(4-1)]
= 3/16

I hope this helps clarify your understanding of slotted ALOHA. If you have any further questions, please don't hesitate to ask.