THE UNIVERSITY OF SYDNEY © MAHYAR SHIRVANIMOGHADDAM 1
Tutorial 3-Solutions ELEC5518: IoT for Critical Infrastructure
Multiple Access Techniques
I. OBJECTIVES
In this tutorial, we see some examples on different multiple access techniques for Internet of Things.
EXAMPLE 1: SLOTTED ALOHA
Consider a slotted ALOHA system, where N users want to send their messages to the base station within only M time slots, where M > N. Each user attempts a transmission with probability p until it receives an acknowledgment from the base station. That is upon receiving an acknowledgment by the user, it stops the transmission.
• Calculate the probability that at least one user can deliver its message to the base station.
• Find the optimal transmission probability which maximizes the probability that at least one device
can deliver its message.
Solution:
For a user to deliver its message at the base station, none of the other users should simultaneously transmit with it. That is user i can deliver its message in a particular time slot, only if none of the other users transmit in the same time slot. Let p1 denote the probability that at least one user can deliver its message to the base station. Let p0 denote none of the users can deliver its message at the base station. It is clear that p1 = 1−p0.
To calculate p0, we need to find the probability that all M time slots are either collision slots or idle slot. The collision slot is a time slot, in which more than one user is transmitting. An idle slot is a time slot, in which none of the users is transmitting. Let q1 denote the probability that in a given time slot, only one user is transmitting. It can be calculated as follows:
N−1
1 − q1. Therefore, p0 can be simply found as follows:
p0 =(1−q1)M =1−Np(1−p)N−1M , (2)
which is the probability that all M time slots are collision or idle time slots. The probability that at least one user can deliver its message at the BS is then given by:
p1 = 1−p0 = 1−1−Np(1−p)N−1M . (3)
Fig. 1 shows the probability that at least one device can deliver its message at the base station versus the transmission probability and the number of devices. As can be seen, when the number of devices is large
N N−1 q1 = 1 p(1−p)
=Np(1−p)
then it is clear that the probability that a given time slot is either a collision time slot or idle time slot is
, (1)
THE UNIVERSITY OF SYDNEY
© MAHYAR SHIRVANIMOGHADDAM 2
1
0.5
0
50
p1
1 0.8
0.6
0.4
10 p
0
and the transmission probability is large, p1 is almost zero, since all the devices are always transmitting and as a result the collision probability increases. It is also clear that for a particular number of devices, there is an optimal transmission probability which maximizes p1. This means that the base station needs to estimate the traffic and determine the optimal transmission probability to maximize the success rate.
To find the optimal value of p, we need to solve the following optimization problem, for given N and M:
popt = arg max{1 − 1 − Np(1 − p)N−1M }. (4) p
For this aim, we find the derivative of p1 with respect to p and set it to zero,
∂p1 =N(1−Np)(1−p)N−21−Np(1−p)N−1M−1 =0. (5)
∂p
Three simple solutions for the above equations are p = 1, p = 1/N , and p(1 − p)N −1 = 1/N . The last solution does not return real value for p, then the only solution which maximizes p1 is p = 1/N. Then we have:
popt = 1 . (6) N
It is important to note that popt does not depend on M, and is a function of only the number of devices N.
40
30
20
0.2
N0
Fig. 1. The probability that at least one user can deliver its message at the base station versus the transmission probability p and the number
of devices N.
THE UNIVERSITY OF SYDNEY © MAHYAR SHIRVANIMOGHADDAM 3
EXAMPLE 2: COORDINATED TDMA AND FDMA
Consider a cellular system with a single base station at the origin and N devices randomly distributed in cell of radius R. The total available bandwidth is W and the time slot duration is T. Each device is assumed to have a message of length L bits. The received signal to noise ratio (SNR) for the ith device transmitting with full power over bandwidth Wt is given by
μr = W μgi, (7) Wt
where μ is the reference SNR and gi is the channel gain for the ith device. According to Shannon’s Channel capacity theorem, a message of length L bits can be sent over a channel of time duration τ and bandwidth w and SNR μ, if and only if the following condition is satisfied:
L ≤ wt log2(1 + μ). (8)
• Find the maximum number of devices which can be supported using the coordinated TDMA strategy.
• Find the maximum number of devices which can be supported using the coordinated FDMA strategy.
• Now consider that gi = 1, for all devices, that is we assume that the devices perform power control
to eliminate fading and path loss. Compare TDMA and FDMA, when T = 1sec, W = 1MHz, and
μ = −3dB.
Solution:
Optimal Throughput TDMA Strategy: In TDMA, the whole spectrum is used by each device in
separate time instances. TDMA is an interesting multiple access strategy due to its simplicity, but it is not efficient for M2M applications with a large number of devices. Moreover, with increasing the number of devices, each device’s transmission will be delayed which is not appropriate for delay-sensitive M2M applications.
Assuming a capacity approaching code and using Shannon’s capacity equation, the time required for a device located at distance r from the base station to deliver its packet to the destination is given by:
tmini = L . (9) W log2(1 + μgi)
The maximum number of devices which can be supported in a resource block of duration T and bandwidth W can then be found as follows:
N
Nmax=max N:tmini≤T . (10)
i=1
Optimal Throughput FDMA Strategy: In FDMA, the spectrum is partitioned between the devices and each device will transmit in a portion of the spectrum. Using Shannon’s capacity formula, the minimum bandwidth required for the transmission of L bits by the ith device over time T is given by the solution of the following equation [? ]:
W
L=TWmini log2 1+μW
gi . (11)
mini
THE UNIVERSITY OF SYDNEY © MAHYAR SHIRVANIMOGHADDAM 4
The maximum load that can be supported in a resource block of duration τs and bandwidth W is given by:
K
Kmax=max K:Wmini≤W . (12)
i=1
Comparison: For a TDMA system, the minimum time duration to deliver a message of length L = 1000
bits is:
tmin = L = 1000
W log2(1 + μgi) 106 log 2(1 + 10−0.3)
= 1.7msec. (13)
(14)
The maximum number of devices can then be found as follows:
NTDMA= T =586. max tmin
For a FDMA system, the minimum bandwidth to deliver a message of length L = 1000 bits is the solution of the following equation:
1000 = 1 × Wmin log2
which is given by Wmin = 80 Hz. The maximum load that can be supported in a resource block of
duration τs and bandwidth W is given by:
NFDMA = W = 12500. (16)
This shows that FDMA can support a larger number of devices than TDMA. The main reason behind this is that in FDMA the devices will transmit over a smaller bandwidth, which also reduces the total noise power and effectively increases the SNR. In this example, FDMA can support about 22 times larger number of devices than TDMA. This is the reason why FDMA and using very narrow-band communications are used in NB-IoT to support a large number of devices in massive IoT
EXAMPLE 3: CODE DIVISION MULTIPLE ACCESS
Consider a CDMA system that N users want to simultaneously communicate with a single base station. Each user has been allocated with an orthogonal code of length L bits.
• Consider that c1 = [−1, 1, −1, 1] and c2 = [1, 1, 1, 1]. Show that c1 and c2 are orthogonal.
• Consider that user 1 uses c1 as the spreading sequence. User 1 wants to send message m1 =
[0, 1, 0, 0, 0]. What is the transmitted message from user 1 using CDMA?
• The base station received the following message y = [−2, 0, −2, 0, 0, −2, 0, −2, 0, −2, 0, −2, 0, 2, 0, 2].
Determine the message from each user.
Solution:
To show that c1 and c2 are orthogonal, we need to show that Li=1 c1,ic2,i = 0. For this example we have:
4
c1,ic2,i =(−1×1)+(1×1)+(−1×1)+(1×1)=0. (17)
i=1
max Wmin
−0.3 106
1 + 10 W
, (15)
min
THE UNIVERSITY OF SYDNEY © MAHYAR SHIRVANIMOGHADDAM 5
User 1 want to send message m1, that is for each 0 it sends c1 and for each 1 it sends −c1. In other words, each bit is spread to L = 4 bits using the CDMA strategy. Therefore, message m1 is converted as follows:
u1 = [c1,−c1,c1,c1,c1] = [−1,1,−1,1,1,−1,1,−1,−1,1,−1,1,−1,1,−1,1,−1,1,−1,1]. (18) To detect the message from each user, the base station multiply the received signal by the spreading
sequences.
y.c1 =[(−2×−1)+(0×1)+(−2×−1)+(0×1), (0×−1)+(−2×1)+(0×−1)+(−2×1), (0×−1)+(−2×1)+(0×−1)+(−2×1), (0×−1)+(2×1)+(0×−1)+(2×1)]
= [4,−4,−4,4] = [0,1,1,0] = m1.
y.c2 =[(−2×1)+(0×1)+(−2×1)+(0×1), (0×1)+(−2×1)+(0×1)+(−2×1), (0×1)+(−2×1)+(0×1)+(−2×1), (0×1)+(2×1)+(0×1)+(2×1)]
= [−4,−4,−4,4] = [1,1,1,0] = m2.
EXAMPLE 4: RANDOM ACCESS IN CELLULAR SYSTEMS
In cellular systems, users perform random access to initiate their access to the base station. In the current LTE standard, each user can select among M = 64 available preambles. An access attempt for a particular user is called successful, when only one user selects a preamble and that preamble is successfully detected at the base station.
Consider that N users want to simultaneously communicate with a single base station. They perform random access, that is each selects a preamble randomly.
1. Determinetheprobabilitythataparticularuserisgrantedaccesstothebasestationinasinglerandom access attempt.
2. What is the average number of users that will be granted access in a single random access attempt?
3. Consider that we have initially N0 users. what is the probability that a user access the base station
after l access attempts. Assume that M = 64 and N0 = 100 and l = 2.
Solution
[1.] A user will be granted access to the base station once it selects a preamble that has not been selected by any other devices. The probability that this user has a successful access attempt is given by:
1 1 N−1 ps(N,M)=M×M 1−M ,
THE UNIVERSITY OF SYDNEY © MAHYAR SHIRVANIMOGHADDAM 6
which follows from the fact that a user can select a given preamble with probability 1/M and this preamble is not selected by any other user with probability 1 − 1/M .
[2.] The average number of users that will be granted access in a single random access attempt is then given by S1 = N 1 − 1 N−1.
M
[3.] Let us assume that in the ith access attempt Ni−1 devices are contending for access that is only Si
users will be granted access. We will have
Ni−1 N Ni−1 −Si P(Si|Ni−1)= S ps(Ni−1,M) i (1−ps(Ni−1,M)) ,
i
which follows from the fact that in the ith random access attempt the successful access probability is ps(Ni−1,M) as there are Ni−1 users contending for access. To calculate the probability that a user access the base station after l access attempts is then given by:
l−2 l−1
p(i=l)= ps(Nl−1,M)(1−ps(Nj,M))P(Nj−1 −Nj|Nj−1),
N1,N2,··· ,Nl−1 j=0 j=1
which follows from the fact that a user will be granted access in the lth attempt, if the previous (l − 1)th attempts are unsuccessful, with the condition that N1, N2, · · · , and Nl−1 users are contending for acees in the first, second, · · · , and (l − 1)th attempts, respectively. When l = 2, we have:
N0 N
p(i=2)= ps(N1,M)(1−ps(N0,M) 0 ps(N0,M)N0−N1 (1−ps(N0,M))N1 .
N1=0 N0 −N1
For N0 = 100 and M = 64, we have ps(100, 64) = 0.2103, therefore we have:
100 100
p(i=2)= ps(N1,M) 100−N 0.2103100−N10.7897N1+1 =0.2282.
N1=0 1