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

Fundamentals of Wireless Communication

CH.6 Multiuser Capacity and Opportunistic Communication

4장까지 : (여러 사용자 간에 채널을 공유하도록 설계된) 몇 가지 특정 다중 액세스 기술(TDMA/FDMA, CDMA, OFDM)에 대해 알아보았습니다. 

그렇다면 "최적의" 다중 접속 방식은 무엇일까요? => 이번 챕터의 Main Topic

 

6.7.1 Fair Scheduling and Multiuser Diversity

사례 연구로, multiuser diversity를 활용하면서 지연 및 공정성 제약 문제(delay and fairness constraints)를 해결하기 위해 설계된 proportional fair scheduling이라는 간단한 스케쥴링 알고리즘을 설명합니다. 

이는 5장에서 소개한 3세대 데이터 표준인 IS-856의 다운링크에 대한 기본 스케줄러입니다.

IS-856의 다운링크는 TDMA 기반이며, 사용자가 요청하는 속도를 기준으로 1.67ms 길이의 시간 슬롯에 사용자가 스케줄링된다는 점을 기억하세요(그림 5.25). 5장에서 이미 속도 적응 메커니즘에 대해 논의했으므로 여기서는 스케줄링 측면을 살펴 보겠습니다.

 

Proportional fair scheduling: hitting the peaks

스케줄러는 기지국이 이전에 모바일로부터 받은 rates를 기반으로 각 시간 슬롯에서 어떤 사용자에게 정보를 전송할지 결정합니다. 가장 간단한 스케줄러는 사용자의 채널 조건에 관계없이 라운드 로빈 방식으로 각 사용자에게 데이터를 전송합니다. IS-856에서 사용되는 스케줄링 알고리즘은 다중 사용자 다양성을 활용하기 위해 채널 종속적인 방식으로 스케줄링합니다. 다음과 같이 작동합니다.

각 사용자의 평균 처리량 T_k[m]을 기하급수적으로 가중치가 부여된 길이 t_c의 window에서 추적합니다.

( It keeps track of the average throughput T_k[m] of each user in an exponentially weighted window of length t_c )

 

1) 시간 슬롯 m에서, 기지국은 모든 사용자로부터 "요청된 속도" R_k[m], k = 1,...,K를 수신하고

2) 스케줄링 알고리즘은 시스템의 모든 활성 사용자 중 R_k[m]/T_k[m]이 가장 큰 사용자 k를 선택하고

3) k^*를 전송합니다.

In time slot m, the base-station receives the “requested rates” R_k[m], k = 1,...,K, from all the users

and the scheduling algorithm simply k^* transmits to the user k with the largest R_k[m]/T_k[m]

among all active users in the system.

 

<잠깐, terminology>
R_k[m] : BS로부터 온 requested rate (요청된 속도)
T_k[m] : average throughput (평균 처리량)
m : 시간 슬롯
k : k 번째 user. 즉, user의 인덱스
k^* : 스케줄링 알고리즘에 따라 선택된 사용자의 인덱스 (주어진 시간 슬롯에서 전송할 사용자를 결정하는 데 사용)
K : 시스템에 활성화된 모든 사용자의 수
t_c : scheduling time scale (window 크기)

 

 

그러니까, R_k[m]/T_k[m]이 크다는 뜻은, 사용자 k가 평균 처리량은 낮은데, 요청된 속도는 높은 곳.

즉, 처리할 수 있는 것은 많지만 실제로 사용되는 것은 낮은 애들 (= 노는 애들)

 

 

T_k[m]은 updated된다. using an exponentially weighted low-pass filter.

그림 6.14와 6.15를 보면 이 알고리즘이 어떻게 작동하는지 직관적으로 알 수 있습니다. 

두 사용자의 요청된 데이터 전송률의 샘플 경로를 시간 슬롯의 함수로 표시합니다(각 시간 슬롯은 IS-856에서 1.67ms). 

We plot the sample paths of the requested data rates of two users as a function of time slots (each time slot is 1.67 ms in IS-856)

그림 6.14에서 두 사용자의 페이딩 통계는 동일합니다. 스케줄링 시간 스케일 tc가 채널의 코히어런시보다 훨씬 크면 대칭에 의해 각 사용자의 처리량 Tkm는 동일한 양으로 수렴합니다. 

If the scheduling time scale tc is much larger than the coherence time of the channels, then by symmetry the throughput of each user Tkm converges to the same quantity. 

스케줄링 알고리즘은 항상 가장 높은 요청 속도를 가진 사용자를 선택하는 것으로 축소됩니다. 따라서 각 사용자는 채널이 양호할 때 스케줄링되며 동시에 스케줄링 알고리즘은 장기적으로 완벽하게 공정합니다. 
The scheduling algorithm reduces to always picking the user with the highest requested rate. Thus, each user is scheduled when its channel is good and at the same time the scheduling algorithm is perfectly fair in the long-term. 
그림 6.15에서는 기지국과의 거리가 다르기 때문에 다중 경로 페이딩으로 인해 두 채널이 모두 변동하더라도 한 사용자의 채널이 평균적으로 다른 사용자의 채널보다 훨씬 더 강합니다. 

항상 요청 속도가 가장 높은 사용자를 선택하는 것(picking the user with the highest requested rate)은 통계적으로 더 강한 사용자에게 모든 시스템 리소스를 제공하는 것을 의미하며 매우 불공평할 수 있습니다. 

이와는 대조적으로, 위에서 설명한 스케줄링 알고리즘에서는 사용자가 직접 요청한 속도가 아니라 각자의 평균 처리량으로 정규화된 속도를 기준으로 리소스를 놓고 경쟁합니다. 통계적으로 더 강력한 채널을 가진 사용자가 더 높은 평균 처리량을 갖게 됩니다.

In contrast, under the scheduling algorithm described above, users compete for resources not directly based on their requested rates but based on the rates normalized by their respective average throughputs. 

The user with the statistically stronger channel will have a higher average throughput.

 

따라서 알고리즘은 time scale t_c에 대한 자체 평균 채널 상태에 비해 순간 채널 품질이 높을 때 (R_k[m] / T_k[m]가 높을 때) 사용자를 스케줄링합니다.

Thus, the algorithm schedules a user when its instantaneous channel quality is high relative to its own average channel condition over the time-scale t_c. 
즉, 채널이 자체 피크에 가까울 때 사용자에게 데이터가 전송됩니다. 

In short, data are transmitted to a user when its channel is near its own peaks. 

 

"자체 피크"는 각 사용자의 채널에서 발생하는 최고의 신호 강도 또는 채널 품질을 나타냅니다. 여기서 "자체"라는 용어는 사용자마다 각자의 채널을 가지고 있다는 의미입니다. 따라서 각 사용자는 자신의 채널에서 최고의 신호 강도를 가질 수 있습니다.

이러한 자체 피크는 특정 사용자가 데이터를 전송받을 때 사용되는 중요한 지표입니다. 즉, 해당 사용자의 채널 품질이 피크에 도달했을 때 데이터를 전송함으로써 효율적인 데이터 전송을 보장할 수 있습니다. 이것은 다중 사용자 다양성 (Multiuser diversity) 이점을 활용하여 시스템 성능을 최적화하는 데 도움이 됩니다.

 

여러 사용자의 채널은 독립적으로 변동하므로 시스템에 충분한 수의 사용자가 있는 경우 언제든지 피크에 가까운 사용자가 있을 가능성이 높기 때문에 다중 사용자 다양성 이점을 여전히 추출할 수 있습니다. 

Multiuser diversity benefit can still be extracted because channels of different users fluctuate independently 

so that if there is a sufficient number of users in the system, most likely there will be a user near its peak at any one time. 
매개변수 t_c는 애플리케이션의 지연 시간 규모에 연결됩니다. 피크는 이 시간 척도와 관련하여 정의됩니다. 

The parameter t_c is tied to the latency time-scale of the application. Peaks are defined with respect to this time-scale.

지연 시간 규모가 크면 처리량은 더 긴 시간 규모에 걸쳐 평균화되며, 스케줄러는 채널이 매우 높은 피크에 도달했을 때 사용자를 스케줄링하기 전에 더 오래 기다릴 여유가 있습니다.

If the latency time-scale is large, then the throughput is averaged over a longer time-scale and the scheduler can afford to wait longer before scheduling a user when its channel hits a really high peak.
이 알고리즘의 주요 이론적 특성은 다음과 같습니다: t_c가 매우 큰 경우(∞에 가까워짐), 이 알고리즘은 모든 스케줄러 중에서 아래 식을 최대화합니다(연습 6.28 참조).

여기서 T_k는 사용자 k의 장기 평균 처리량입니다.

The main theoretical property of this algorithm is the following: With a very large t_c (approaching ∞), the algorithm maximizes A among all schedulers (see Exercise 6.28). Here, T_k is the long-term average throughput of user k.

 

비례 공정 스케줄링은 직교 다중 접속 제약(IS-856의 경우 TDMA) 내에서 비대칭 사용자 간의 공정성을 처리하기 위한 접근 방식입니다. 그러나 6.2.2절에서 AWGN 채널의 경우 SIC와 함께 중첩 코딩을 사용하면 이러한 비대칭 환경에서 직교 다중 액세스보다 훨씬 더 나은 성능을 얻을 수 있다는 것을 알 수 있습니다. 
페이딩 채널에서도 비슷한 이득을 기대할 수 있으며, 중첩 코딩의 이점을 다중 사용자 다이버시티 스케줄링과 결합하는 것은 당연한 일입니다. 
한 가지 접근 방식은 셀의 사용자를 기지국 근처 또는 셀 에지 근처에 있는지 여부에 따라 두 개의 클래스로 나누어 각 클래스의 사용자가 통계적으로 비슷한 채널 강도를 갖도록 하는 것입니다. 현재 채널이 자신의 클래스에서 순간적으로 가장 강한 사용자는 중첩 코딩을 통해 동시 전송되도록 예약됩니다(그림 6.16).

기지국 근처에 있는 사용자는 멀리 있는 사용자로 향하는 신호를 제거한 후 자신의 신호를 디코딩할 수 있습니다.

각 클래스에서 가장 강력한 사용자에게 전송함으로써 다중 사용자 다이버시티 이점을 포착할 수 있습니다. 반면에 가까운 사용자는 매우 강력한 채널과 전체 자유도를 사용할 수 있으므로(직교 다중 접속에서는 일부만 사용할 수 있는 것과는 대조적으로) 매우 좋은 속도를 누리기 위해 일부의 전력만 할당받으면 됩니다. 가까운 사용자에게 소량의 전력을 할당하면 이 사용자의 존재가 셀 에지 사용자의 성능에 미치는 영향을 최소화할 수 있다는 장점이 있습니다. 따라서 적절한 전력 배분을 통해 공정성을 유지할 수 있습니다.

비례 공정 TDMA 스케줄링에 비해 이 접근 방식의 효율성은 연습 6.20에서 정량화됩니다. 연습 6.19는 이 전략이 실제로 다운링크 페이딩 채널 용량 영역의 경계에 있는 모든 지점을 달성하는 데 최적임을 보여줍니다(전체적으로 가장 좋은 채널을 가진 사용자에게 전송하는 전략과는 대조적으로 이 비대칭 시나리오에서는 합산 속도에만 최적이며 불공정한 작동 지점입니다).