# #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 ≥ 2$, for $1 ≤ j ≤ k$) and the remaining bins have one or zero ball. $p_k(M, N_1)$ is given by
$$p_k(M, N_1)={C_k^{N_1}\over N^{M}_1}\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^M_{i_1}...C_{i_k}^{\sum_{j=1}^{k-1}i_j}C^{N_1-k}_{\sum_{j=1}^{k}i_j}\ \ (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}{M\over 2}{\rfloor}\}}kp_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}{M\over 2}{\rfloor}\}}{C_k^{N_1}\over N^{M}_1}\sum_{i_1=2}^{M-2(k-1)}...\sum_{i_k=2}^{M-\sum_{j=1}^{k-1}i_j}C^M_{i_1}...C_{i_k}^{\sum_{j=1}^{k-1}i_j}C^{N_1-k}_{\sum_{j=1}^{k}i_j}\ (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 ≥ 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 $1\over N_1$ time unit.
- Therefore, we use a slotted Aloha system with Poisson arrival rate $M$ devices in a time unit and slot duration $1\over 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 $1\over N_i$ that is, $({K_i\over N_i})e^{-K_i\over 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^{-K_i\over 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^{-K_i\over N_i}-K_i e^{-K_i\over 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^{-K_i\over N_i})$$
- The access success probability is estimated by $$P_s=\sum_{i=1}^{I_{max}} {N_{S,i}\over M}$$
- The mean access delay $T_a$ is estimated by $$T_a={\sum_{i=1}^{I_{max}} iN_{S,i} \over \sum_{i=1}^{I_{max}} N_{S,i}}$$
- The collision probability $P_C$ is estimated by $$P_C={\sum_{i=1}^{I_{max}} N_{C,i} \over \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, $vector\ size=(1,M)$ | $-1$~$0$ for each element (station) |
| $R_n$ |The number of packets being sent in RAO n | Vector of Integer, $vector \ size=(1, N)$ | $1$~$M$ in each element (channel)|
| $i$ | Access Cycle (Timeslot) ID | Integer | $1$~$I{max}$ |
| $success\_pckt\_i$ | the number of successful transmission in access cycle $i$| Integer | $0$ ~ $N$ |
| $success\_pckt$ | the sum of successful transmission in all access cycles | Integer | $0$ ~ $M$ |
| $success\_prob$ | $success\_pckt\over M$ | Float | $0$ ~ $1$ |
| $total\_success$ | the sum of all $success\_prob$ in all simulations| Vector of Float | $vector\ size=(1, N_{num})$, each element has range $0$ ~ $S$ |
| $collision\_pckt$ | the number of failed transmission in all access cycles| Integer | $0$ ~ $NI_{max}$ |
| $collision\_prob$ | $collision\_pckt\over {I_{max}\ N}$ | Float | $0$ ~ $1$ |
| $total\_coll$ | the sum of all $collision\_prob$ in all simulations | Vector of Float | $vector\ size=(1, N_{num})$, each element has range $0$ ~ $S$ |
| $delay$ | ${\sum_{i=1}^{I_{max}} i×success\_pckt\_i}$ | Integer | $0$ ~ $MI_{max}$ |
| $mean\_access\_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={delay\over success\_pckt}$ | Float | $0$ ~ $I_{max}$ |
| $total\_mean\_access\_delay$ | the sum of all $mean\_access\_delay$ in all simulations | Vector of Float | $vector\ size=(1, N_{num})$, each element has range $0$ ~ $SI_{max}$ |

#### Output Data structure
| O/P | Meaning | Data Type| range |
| -------- | -------- | -------- |-------- |
| $average\_success\_prob$ | $$total\_success\over S$$ or the average access success probability of $S$ simulations| Vector of Float | $vector\ size=(1, N_{num})$, each element has range $0$~$1$ |
| $average\_coll\_prob$ | $$total\_coll\over S$$ or the average collision probability of $S$ simulations| Vector of Float | $vector\ size=(1, N_{num})$, each element has range $0$~$1$ |
| $average\_mean\_access\_delay$ | $$total\_mean\_access\_delay\over S$$ or the average mean access delay of $S$ simulations| Vector of Float | $vector\ size=(1, N_{num})$, each element has range $0$~$I{max}$ |
#### 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

st=>start: Start
e=>end: End
op0=>operation: total_success=0
total_coll=0
total_mean_access_delay=0
op=>operation: s=1
op1=>operation: N=5
op2=>operation: success_pckt=0, 
collision_pckt=0,
delay=0
op2_5=>operation: stationState(1)=0,
stationState(2)=0,
...
stationState(M)=0
op3=>operation: i=1
op3_5=>operation: success_pckt_i=0
op4=>operation: Rn(1)=0, 
Rn(2)=0, 
..., 
Rn(N)=0
op5=>operation: m=1
op6=>operation: choose one of 
N RAOs randomly, 
namely RAO n
op7=>operation: STA m is transmitting 
packet in RAO n
op8=>operation: increment Rn(n)
op9=>operation: increment m
op10=>operation: n=1
op11=>operation: packet successfully transmitted, 
increment success_pckt,
increment success_pckt_i
op12=>operation: Collision detected,
increment collision_pckt
op13=>operation: increment n
op14=>operation: delay=delay+i*success_pckt_i
op15=>operation: increment i
op16=>operation: calculate success_prob,
collision_prob, 
on this N 
RAOs system
op16_5=>operation: mean_access_delay=delay/success_pckt
op17=>operation: increment N
op18=>operation: total_success=total_success+success_prob
total_coll=total_coll+collision_prob
total_mean_access_delay=total_mean_access_delay+
mean_access_delay
op19=>operation: increment s
op20=>operation: calculate average_success_prob,
average_coll_prob,
average_mean_access_delay
op21=>operation: plot Y:average_success_prob, X:N
Y:average_coll_prob, X:N
Y:average_delay, X:N
cond=>condition: is stationState(m)=0?
cond2=>condition: is m=M?
cond3=>condition: is 
Rn(n)=1?
cond4=>condition: is 
Rn(n)>1?
cond5=>condition: is 
n=N?
cond6=>condition: is 
i=Imax?
cond7=>condition: is 
N=45?
cond8=>condition: is s=S?
st->op0->op->op1->op2->op2_5->op3->op3_5->op4->op5->cond
cond(yes)->op6->op7->op8->cond2
cond(no)->cond2
cond2(no)->op9->cond
cond2(yes)->op10->cond3
cond3(yes)->op11->cond5
cond3(no)->cond4
cond4(yes)->op12->cond5
cond4(no)->cond5
cond5(no)->op13->cond3
cond5(yes)->op14->cond6
cond6(no)->op15->op3_5
cond6(yes)->op16->op16_5->cond7
cond7(no)->op17->op2
cond7(yes)->op18->cond8
cond8(no)->op19->op1
cond8(yes)->op20->op21->e

## 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$)