[Principle] Slotted Aloha Throughput

* This is not a class material for commercial purpose. It's free for student.* 

본 포스팅은 Pure Aloha를 먼저설명하고, Slotted Aloha를 유도한다.

1. ALOHA란?

Random access method의 한 방법으로 1970년대에 제안되었으며 여전히 셀룰러 시스템에서 그 Simplicity를 장점으로 사용된다. assumption

알로하(ALOHA)는 하와이 대학에서 개발되었으며 시분할 다중접속 기술을 사용해 위성과 지구 사이의 무선 전송을 하는 프로토콜이다. 원래의 알로하에서 사용자는 언제든지 전송할 수 있지만, 다른 사용자들의 메시지는 충돌할 위험이 있다. 패킷이 준비되면 브로드캐스트되며, 만약 충돌이 일어나면 일정시간 후에 재전송된다. Slotted Aloha는 채널을 시간대별로 나누어서 충돌 위험을 줄이는 것으로, 각 사용자는 시간대의 시작에서만 전송이 가능하다.

2. Basic working

- 노드는 데이터 전송을 언제든지 할수있고 ACK를 받는다

- 만약 하나의 Frame 이상이 같은 시간에 전송된다면, 그들은 서로 간섭을 겪기때문에 충돌하거나 패킷을 잃어버린다. 

   (Collision or Lost)

- 만약 ACK 패킷이 지정된 시간안에 도착하지 않으면 Timeout이 발생하고 전송을 한 노도는 Backoff time만큼 기다린후 

   다시 전송을 시도한다. 

2-2. Vulnerable period

- Frame의 길이 (전송할 패킷의 사이즈)를 L이라고 둔다면, L 길이 패킷을 전송하는 소요시간은 X = L/R (data rate)이 됨.

- consider a frame with starting transmission time to the frame will be successfully transmitted if no other frame 

   collides with it.

     -> any transmission that begins in interval [t0, t0+X], or in the prior X seconds leads to collision

    vulnerable period = [ t0 – X, t0+ X ]

위의 그림은 Unslotted Aloha의 취약구간을 보여준다. L길이 만큼의 패킷이 전송될 동안 앞뒤로 2L길이만큼 다른 노드들의 전송시도가 없어야만 성공적인 전송이 가능하다.

3. Throughput =(def. Number of packets per unit time)

1) Successful throughput : X시간(unit time) 동안의 성공적인 Frame 전송의 평균값을 의미한다.

2) G-load : X시간 동안의 평균적인 전송시도를 의미한다. 

(큰 개념은 굵은 제목들만 봐도 충분히 이해가 된다. 하지만 이를 직접 Code로 구현하기 위해서는 아래의 확률과정에 대해서 충분히 이해해야 한다. G의 개념과 Qa, Qr의 개념만 안다면 코딩가능하다. 필요없는 분은 바로 3)으로 가세요)

"G" refer to the mean used in the Poisson distribution over transmission-attempts that is, on average, there are G transmission-attempts per frame-time in state n.

State (n) of system is number of backlogged nodes.

If a transmission has a collision, node becomes backlogged

– While backlogged, transmit in each slot with probability qr until successful.

Infinite nodes where each arriving packet arrives at a new node

– Equivalent to no buffering at a node (queue size = 1)

– Pessimistic assumption gives a lower bound on Aloha performance

G(n) = λ + n*Qr

( Qr : re-transmission probability of backlogged stations. ) 

The number of attempted packets per slot in state n is approximately a Poisson random variable of mean g(n)

– P (m attempts) = {(G(n)^k)*exp^-G(n)}/m!

– P (idle) = probability of no attempts in a slot = exp^-G(n)

– p (success) = probability of one attempt in a slot = G(n)*exp^-G(n)

    : idel한 채널상태에서 혼자서 전송을 시도하는 경우 = 성공확률.

– P (collision) = P (two or more attempts) = 1 - P(idle) - P(success)

For any frame-time, the probability of there being k transmission-attempts during that frame-time is: 

{(G^k)*e^(-G)} / k!

If throughput is represented by S, under all load, S = G*Ps, where Ps is the probability that the frame does not suffer collision. A frame does not have collision if no frame are send during the frame time. Thus, in t time Ps=exp^-G.

In pure Aloha, Ps=exp^(-2G), as mean number of frames generated in 2t is 2G. From the above, throughput in pure Aloha S = G*exp^-2G.

*혼잣말: G= a node transmission-attempts , k= k nodes라면.. 2)과 3)의 설명에서 G와 k의 연결고리가 없는 느낌인데..

3) Successful  Probability (Ps): 성공적인 Frame전송의 확률

따라서 Successful throughput = Ps * G-load.가 된다.

if general, if frame arrivals are equally likely at any instant in time, and arrivals occur at an average rate of λ [arrivals per sec]

포아송 프로세스를 따라서 동일 프레임들K개가 T시간동안에 도착한다고 가정한다면, 위의 식으로 표현된다.

in our case, λ=G/X [arrivals per second] and T=2X, hence

그러나 앞서 이야기했듯이 Pure Aloha는 프레임길이의 2배동안 다른 노드들의 프레임전송이 없어야 충돌이 없기 때문에 전송이 성공하기 위한 조건들을 대입하면 아래와 같이 다시 쓸수가 있다. 

accordingly, probability of successful transmission (no collision) is:

이를 푸아송 프로세스의 성질을 이용하여, 어떠한 전송이 없을 확률을 구하면 = 다른 노드들이 모두 전송하지 않을 확률 = 성공확률을 의미한다. 

따라서 Throughput 은 평균적인 전송시도량 * 패킷전송 성공확률로 표현이 된다. 

4. Slotted Aloha

Slotted Aloha는 pure Aloha보다 향상된 성능을 가지는데, 이는 충돌량이 감소했기 때문이다. 

1) Assumption

   - 각각의 슬롯사이즈들은 X=L/R 의 크기로 나눠어 진다. (하나의 프레임전송에 맞는 시간)

   - 노드들은 전송을 슬롯의 시작부분에만 시작한다.

   - 노드들은 동기화를 통해서 슬롯의 시작을  알고있다고 가정한다.      

2) Operation

   (1) when node has a fresh frame to send, it waits until next frame slot and transmits

   (2) if there is a collision, node retransmits the frame after a backoff-time

        (backoff-time = multiples of time-frames)

위의 그림을 보면 왜 Slotted Aloha가 더 좋은 성능을 가지는지 알수있다. 사실 직관적으로 2배정도의 성능을 보일것이라고 생각이 든다.

3) Throughput

packet P will be transmitted successfully if no other packet becomes available for transmission during the same time slot. Pure Aloha에서 전송시 Vulnerable period가 패킷사이즈(L)의 2배시간동안 다른 노드들의 전송이 있다면 충돌이 발생한다고 했다면, Slotted Aloha의 경우는 Packet Size의 길이만큼만 충돌이 없도록 보장이 되기에 2배의 성능을 보인다.

vulnerable period = [ t0 – X, t0 ]

따라서, Slotted ALOHA와  Pure Aloha 의 성능을 비교해보면 아래와 같다. 

Slotted ALOHA의 MAX Throughput 은 G=1일때 0.36을 보인다. 

따라서 실질적인 Channel capacity는 36%이다.  
(legend가 반대로 들어갔습니다. 붉은색 = pure, 파란색이 slotted 입니다. 참고하시길 바랍니다.)

clear;

clc;

lambda=0.36;

q_r=0.18;

m=30;

%***********************************************************************************

%function out=s_aloha(lambda,q_r,m); 

%lambda: total arrival rate of all stations

% q_r: retransmission prob. of backlogged stations

% m: the number of stations  

%***********************************************************************************

if lambda<=0 | lambda >1

  fprintf ('Syntax: s_aloha(lambda,q_r,m)');

  error ('Bad parameter: lambda shoud be between 0 and 0.36 ');

elseif m~=ceil(m)|m==0

  fprintf ('Syntax: s_aloha(lambda,q_r,m)');

  error ('Bad parameter: m should be a positive integer ');

end

q_a=1-exp(-lambda/m); % the prob. of an unbacklogged node send

fprintf('q_a is %f \n',q_a);

if q_r<q_a | q_r>=1

  fprintf ('Syntax: s_aloha(lambda,q_r,m)');

  error ('Bad parameter: q_r should be between q_a and 1 ');

end

fprintf('lambda is %f \n',lambda);

fprintf('q_r is %f \n',q_r);

fprintf('m is %d \n',m);

% We use n to represent the number of backlogged stations

for n=0:m,

 G(n+1)=(m-n)*q_a+n*q_r; % the expected number of attempted transmissions in a slot

 P_succ_approx(n+1)=G(n+1)*exp(-G(n+1)); % Approximated succ. prob.

 Arriv_rate(n+1)=(m-n)*q_a;

 

 Q_a_1_n=(m-n)*((1-q_a)^(m-n-1))*q_a;

 Q_r_0_n=(1-q_r)^n;

 Q_a_0_n=(1-q_a)^(m-n);

 Q_r_1_n=n*(1-q_r)^(n-1)*q_r;

 

 P_succ(n+1)=Q_a_1_n*Q_r_0_n + Q_a_0_n*Q_r_1_n; %P_succ(1) is the succ. prob. at state 0

end

figure;

plot([0:m],P_succ,'k-');

hold on;

plot([0:m],P_succ_approx,'k+-');

hold on;

plot([0:m],Arriv_rate,'k--');

hold off;

set(gca,'FontSize',18);

xlabel('Number of backlogged nodes');

legend('P_{succ}','Approx. P_{succ}','Arrival rate');