#One-Shot Random Access

Topic: 5G Random Access Procedure Bariq Sufi Firmansyah Institut Teknologi Bandung [e-mail]

tags: NTUST-RESEARCH

---

Background

One-Shot Random Access: Analytical Model

In this system, time is divided into fix-length ‘access cycle.’ Each access cycle contains

$N$ RAOs. All of the

$M$ devices transmit their first random-access attempts at a randomly chosen RAO in the first access cycle. The collided devices immediately re-transmit their random-access attempts in the next access cycle. A total of

$I_{max}$ access cycles are reserved.

• Let
  $N_i$ be the number of RAOs reserved for the
  $i^{th}$ access cycle
• Let
  $N_{S,i}$ and
  $N_{C,i}$ be the average number of successful, and collided RAOs observed at the end of the
  $i^{th}$ access cycle.

On the first access cycle,

$M$ devices contend for

$N_1$ RAOs.

$N_{S,1}$ and

$N_{C,1}$ can be determined using a combinatorial model.

• Let
  $p_k(M,N_1)$ be the probability that
  $M$ devices send random access attempts in an access cycle and
  $k$ of the
  $N_1$ RAOs are collided

$p_k(M,N_1)$ is equal to the probability that placing

$M$ balls into

$N_1$ bins and

$k$ bins have at least two balls (

$i_j\ge 2$, for

$1\le j\le k$) and the remaining bins have one or zero ball.

$p_k(M,N_1)$ is given by

$$p_k(M,N_1)=\frac{C_k^{N_1}}{N_1^M}\sum _{i_1=2}^{M-2(k-1)}\sum _{i_2=2}^{M-2(k-2)-i_1}...\sum _{i_k=2}^{M-\sum _{j=1}^{k-1}{i}_j}{C}_{i_1}^M...C_{i_k}^{\sum _{j=1}^{k-1}{i}_j}{C}_{\sum _{j=1}^k{i}_j}^{N_1-k}(M-\sum _{j=1}^k{i}_j)!$$

$N_{C,1}$ is the expected value of the bins that have at least two balls and can be derived as

$$N_{C,1}=\sum _{k=1}^{min\{N_1,\lfloor \frac{M}{2}\rfloor \}}k{p}_k(M,N_1)$$

$N_{S,1}$ is the expected values of the bins that have only one ball and is determined by

$$N_{C,1}=\sum _{k=0}^{min\{N_1,\lfloor \frac{M}{2}\rfloor \}}\frac{C_k^{N_1}}{N_1^M}\sum _{i_1=2}^{M-2(k-1)}...\sum _{i_k=2}^{M-\sum _{j=1}^{k-1}{i}_j}{C}_{i_1}^M...C_{i_k}^{\sum _{j=1}^{k-1}{i}_j}{C}_{\sum _{j=1}^k{i}_j}^{N_1-k}(M-\sum _{j=1}^k{i}_j)!(M-\sum _{j=1}^k{i}_j)$$

However, the computational complexity of the approach is considerably high. Hence, we need to find approximation formulas to derive

$N_{C,i}$ and

$N_{S,i}$ for the second and future access cycles, i.e.

$i\ge 2$.

One-Shot Random Access: Approximation

• The system that
  $M$ devices contending for
  $N_1$ RAOs in a random access slot with duration of one time unit is equivalent to a system has
  $N_1$ mini slots, where each mini slot contains one RAO and has duration of
  $\frac{1}{N_1}$ time unit.
• Therefore, we use a slotted Aloha system with Poisson arrival rate
  $M$ devices in a time unit and slot duration
  $\frac{1}{N_1}$ time unit to approximate the case that
  $M$ devices contend for
  $N_1$ RAOs in one-shot random access.
• Let
  $K_i$ be the average number of devices that transmit their random-access attempts in the
  $i^{th}$ access cycle. Initially,
  $K_1=M$. The successful probability of a mini slot is the probability that only one device transmits in the time duration of
  $\frac{1}{N_i}$ that is,
  $(\frac{K_i}{N_i})e^{\frac{-K_i}{N_i}}$. The success probability in one slot is
  $N_i$ times the success probability in one minislot, therefore
  $N_{S,i}$ can be approximated by
  $$N_{S,i}=K_i{e}^{\frac{-K_i}{N_i}}$$
• The average number of collided RAOs of the one-shot random access observed in one time unit is equal to
  $N_i$ minus the sum of idle RAOs and success RAOs. Therefore,
  $$N_{C,i}=N_i-N_i{e}^{\frac{-K_i}{N_i}}-K_i{e}^{\frac{-K_i}{N_i}}$$
• The number of devices that transmit their random-access attempts in the
  ${(i+1)}^{th}$ access cycle is equal to the number of contending devices minus the number of successful devices in the
  $i^{th}$ access cycle. That is,
  $$K_{i+1}=K_i-N_{S,i}=K_i(1-e^{\frac{-K_i}{N_i}})$$
• The access success probability is estimated by
  $$P_s=\sum _{i=1}^{I_{max}}\frac{N_{S,i}}{M}$$
• The mean access delay
  $T_a$ is estimated by
  $$T_a=\frac{\sum _{i=1}^{I_{max}}i{N}_{S,i}}{\sum _{i=1}^{I_{max}}{N}_{S,i}}$$
• The collision probability
  $P_C$ is estimated by
  $$P_C=\frac{\sum _{i=1}^{I_{max}}{N}_{C,i}}{\sum _{i=1}^{I_{max}}{N}_i}$$

System Model

I/P Parameters	Value
$N$: # of RAOs	integer from $5$ to $45$
$N_{num}$: This simulation has $N_{num}$ distinct numbers of $N$, namely $$5,6,7,...,44,45$$	$41$
$M$: # of STAs	$100$
$I_{max}$: # of access cycles	$10$
$S$: # of simulation	${10}^5$ times

Variable Data structure

Variable	Meaning	Data Type	range
$m$	Station ID	Integer	$1$~ $M$
$n$	RAO ID	Integer	$1$~ $N$
$s$	simulation ID	Integer	$1$~ $S$
$stationState$	the state of station $m$. 0 denotes that station $m$ is still contending for RAOs, -1 denotes that station $i$ have successfully transmitted packet	Vector of Integer, $vectorsize=(1,M)$	$-1$~ $0$ for each element (station)
$R_n$	The number of packets being sent in RAO n	Vector of Integer, $vectorsize=(1,N)$	$1$~ $M$ in each element (channel)
$i$	Access Cycle (Timeslot) ID	Integer	$1$~ $Imax$
$success\mathrm{\_}pckt\mathrm{\_}i$	the number of successful transmission in access cycle $i$	Integer	$0$ ~ $N$
$success\mathrm{\_}pckt$	the sum of successful transmission in all access cycles	Integer	$0$ ~ $M$
$success\mathrm{\_}prob$	$\frac{success\mathrm{\_}pckt}{M}$	Float	$0$ ~ $1$
$total\mathrm{\_}success$	the sum of all $success\mathrm{\_}prob$ in all simulations	Vector of Float	$vectorsize=(1,N_{num})$, each element has range $0$ ~ $S$
$collision\mathrm{\_}pckt$	the number of failed transmission in all access cycles	Integer	$0$ ~ $N{I}_{max}$
$collision\mathrm{\_}prob$	$\frac{collision\mathrm{\_}pckt}{I_{max}N}$	Float	$0$ ~ $1$
$total\mathrm{\_}coll$	the sum of all $collision\mathrm{\_}prob$ in all simulations	Vector of Float	$vectorsize=(1,N_{num})$, each element has range $0$ ~ $S$
$delay$	$\sum _{i=1}^{I_{max}}i\times success\mathrm{\_}pckt\mathrm{\_}i$	Integer	$0$ ~ $M{I}_{max}$
$mean\mathrm{\_}access\mathrm{\_}delay$	Delay for each random access procedure between the first random access attempt and the completion of the random access procedure for the successfully accessed devices. $T_a=\frac{delay}{success\mathrm{\_}pckt}$	Float	$0$ ~ $I_{max}$
$total\mathrm{\_}mean\mathrm{\_}access\mathrm{\_}delay$	the sum of all $mean\mathrm{\_}access\mathrm{\_}delay$ in all simulations	Vector of Float	$vectorsize=(1,N_{num})$, each element has range $0$ ~ $S{I}_{max}$

Output Data structure

O/P	Meaning	Data Type	range
$average\mathrm{\_}success\mathrm{\_}prob$	$$\frac{total\mathrm{\_}success}{S}$$ or the average access success probability of $S$ simulations	Vector of Float	$vectorsize=(1,N_{num})$, each element has range $0$~ $1$
$average\mathrm{\_}coll\mathrm{\_}prob$	$$\frac{total\mathrm{\_}coll}{S}$$ or the average collision probability of $S$ simulations	Vector of Float	$vectorsize=(1,N_{num})$, each element has range $0$~ $1$
$average\mathrm{\_}mean\mathrm{\_}access\mathrm{\_}delay$	$$\frac{total\mathrm{\_}mean\mathrm{\_}access\mathrm{\_}delay}{S}$$ or the average mean access delay of $S$ simulations	Vector of Float	$vectorsize=(1,N_{num})$, each element has range $0$~ $Imax$

Timing Diagram

Fig.1 One-Shot Random Access Timing Diagram

• Figure 1 is the timing diagram of one-shot random access system. in that figure, there are 5 RAOs, 10 stations, and 10 Access Cycles
• there are
  $M$ stations contend in first access cycle
• packet
  $m$ corresponds to packet transmitted by station
  $m$
• each station choose RAOs randomly
• the successful station will no longer transmit packet in the next access cycles

Flow Chart

Numerical Results

Fig. 2 Access success probability and its approximation error.

Fig. 3 Mean access delay and its approximation error.

Fig. 4 Collision probability and its approximation error.

Figures 2, 3, and 4 illustrated simulation results and the derived performance metrics of the access success probability, the mean access delay, and the collision probability of the simplified group paging obtained from

$P_c$,

$P_S$, and

$T_a$ for

$M=100$,

$N=5$ to

$45$ and

$I_{max}=10$, respectively.

• The results show that the approximation error of the access success probability is high for small
  $N$
• the approximation error of the collision probability is small for all
  $N$
• the approximation error of the mean access delay is high if
  $N$ is small. (in Dr. Wei's paper, the approximation error is zero when
  $N>10$, in my simulaton, the approximation error is zero when
  $N>20$)