Average number of slots needed in slotted-Aloha

Problem Detail: 

Consider 2 stations that share the same bus. Both stations are perfect synchronized each other and when they have packets to transmit, they are starting the transmission in the beginning of a same slot. Transmission is as follows: when base $i$ has a packet to transmit attempts with probability $p_i, i=1,2$. Different stations make the random selection independently and corresponding probabilities are $p_1=0.5, p_2=0.25$. Initially the station 1 has 2 packets for station 2, while the other has no package.

What is the average number of slots in order all packets reach their destinations? Then if station 1 has 1 packet for station 2 and station 2 has 1 packet for station 1, what is the average number of slots? We are using slotted-Aloha.

Asked By : Adasel Pomik

Answered By : Karl Hardr

The protocol you are describing is most probably CSMA or slotted ALOHA.

As @wece mentioned, you need also to specify what you do in case of conflict (this is also the main difference between the above mentioned protocols). I would assume that a station sends regardless of the link-status and that a station will retransmit in the next slot with same probability $p_{i}$ in case of collision. This is basically what happens in slotted ALOHA, just that you have individual transmission probabilities for you stations.

You would not refer to the specified protocol as TDM (time division multiplexing), because the channel access is non-deterministic and non-repetitive, although you do have fixed time slots.

To your calculative questions:

1) Station 1 has 2 packets to send:
The probability that 1 successfully transmits to 2 is:

$$P(transmit_{1,2})=P(send_{1})*(1-P(send_{2}))$$

Since we have no packets at station 2, $P(send_{2})$ is zero. This is repeated over potentially many slots, always with probability $p_{1}=0.5$ that 1 will send in a slot. Note that this is the same problem as a simple coin toss. The expected number of sends in n tries (if we had infinite packets at 1) is $E=n*p$. Let's look at only one packet: We only want to know how many tries it takes on average. We can therefore write: $n=E/p$. This yields 2 tries on average for station 1. We can thereafter reason exactly the same way for the second package, because there is no statistical dependence between the events. We thereby obtain #tries = 4. (The same problem for station two would yield 4 + 4 tries.)

2) Now two stations want to send. We therefore have ($\neg$ means not):

$$ P(send_{1}\&send_{2}) = \frac{1}{2}*\frac{1}{4}=\frac{1}{8} $$ $$ P(send_{1}\&\neg send_{2}) = \frac{1}{2}*\frac{3}{4}=\frac{3}{8} $$ $$ P(\neg send_{1}\&send_{2}) = \frac{1}{2}*\frac{1}{4}=\frac{1}{8} $$ $$ P(\neg send_{1}\&\neg send_{2}) = \frac{1}{2}*\frac{3}{4}=\frac{3}{8} $$

Only the middle two give a first correct transmission. As in the previously calculation we see that we need 2 tries (or time slots) on average for this to happen. Once this happened, we are back to the first problem, sending one packet with the other station being quiet.

However, at this point it could have been the first or the second station which sent the first packet. We therefore need to account for it: We have 3/4 cases where it was station 1 and 1/4 cases where it was station 2 which transmitted correctly in the first step. This means we can simply add up the number of tries as: $$\#tries_{first-packet} + \#tries_{second-packet-from-1}*p_{second-packet-at-1} + \#tries_{second-packet-from-2}*p_{second-packet-at-2}$$ $$= 2 + 2 * \frac{1}{4} + 4 * \frac{3}{4} = 5.5$$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13498