[개념 공부] Proportional Fair Scheduling Algorithm #2

Opportunisitic Scheduling

Idea: 채널 컨디션이 좋은 유저에게 데이터를 몰아주면, 그만큼 data-rate가 높아지면서 더 좋은 채널을 유지할 수 있다.

 

Proportional-Fair Scheduling Algorithm

목표: multiuser 상태에서 개별 사용자의 만족도를 보장하기

 

Schedular는 기지국이 이전에 모바일로부터 받은 요청된 전송률을 기반으로 각 시간 슬롯에서 정보를 전송할 사용자를 결정

- 간단한 스케줄러: RR, 근데 이건 user channel 상태 신경 안 씀

- IS0856 스케줄러

1) 각 사용자의 평균 처리령 T_k[m]을 window크기 t_c 안에서 추적함

2) 특정 시간슬롯 m에서 기지국은 모든 사용자로부터 요청된 속도(각 사용자가 전송하고 싶은 데이터율)을 수신 = R_k[m]

3) k들 중에서 R_k[m]/T_k[m]이 가장 큰 유저를 선택

(= BS에게 요청된 데이터 수신율은 높은데 평균 처리량은 낮은 user을 선택)

4) 그리고 T_k[m]을 업데이트

 

<업데이트 과정 직관적으로 이해하기>

6.14 그림 설명 (두 사용자의 fading 통계가 동일함)

=> x축은 매 time slot, y축은 사용자로부터 수신된 요청된 데이터율

스케줄링 알고리즘은 항상 가장 높은 요청 속도를 가진 사용자를 선택하는 것으로 축소됨

따라서 각 사용자는 채널이 양호할 때 스케줄링 되며, 동시에 스케줄링 알고리즘은 장기적으로 fair하다.

 

6.15 그림 설명 (다중 경로 페이딩 발생 / e.g. BS와 각 user의 거리 차이)

두 채널이 모두 변동하더라도 한 사용자의 채널이 평균적으로 다른 사용자의 채널보다 훨씬 더 강함

6.14와 달리 요청 속도가 가장 높은 사용자를 선택 ~> 통계적으로 더 강한 사용자에게 모든 시스템 리소스를 제공하는 것을 의미

 

따라서 PFS는 사용자가 직접 요청한 속도 ❌, 각자의 평균 처리량으로 정규화된 속도를 기준으로 리소스를 놓고 경쟁한다.

 

따라서 알고리즘은 시간 규모 t_c에 따른 평균 채널 상태에 비해 순간 채널 품질이 높을 때 사용자를 스케줄링 한다는 것!

즉, 채널이 자체 피크에 가까워질 때, 사용자에게 데이터가 전송된다.

 

t_c: 애플리케이션의 지연 시간 규모에 연결된다. 피크는 이 시간 척도와 관련하여 정의된다.
latency time scale이 크면, 처리량이 더 긴 시간 규모에 걸쳐 평균화되고 스케줄러는 채널이 매우 높은 피크에 도달할 때 사용자를 스케줄링하기 전에 더 오래 기다릴 수 있다.

 

따라서 이 알고리즘의 주요 이론적 특성: t_c가 매우 큰 경우, 알고리즘은 모든 스케줄러 중에서 다음의 식을 최대화 한다.

이때 T_k는 사용자 k의 long-term average throughput이다.