최대 피에프 선택을 기반으로 하는 상향 링크 스케쥴링 방법 및 이를 수행하는 스케쥴링 장치(Uplink Scheduling Method Based On Maximum PF Selection And Apparatus For Performing The Same)

(19) 대한민국특허청(KR)
(12) 등록특허공보(B1)
(45) 공고일자 2013년03월11일
(11) 등록번호 10-1242049
(24) 등록일자 2013년03월05일
(51) 국제특허분류(Int. Cl.)
H04W 72/12 (2009.01) H04J 11/00 (2006.01)
H04W 72/04 (2009.01)
(21) 출원번호 10-2011-0087877
(22) 출원일자 2011년08월31일
심사청구일자 2011년08월31일
(56) 선행기술조사문헌
KR1020070116685 A*
KR1020050084908 A
US20110077016 A1
KR1020040096790 A
*는 심사관에 의하여 인용된 문헌
(73) 특허권자
성균관대학교산학협력단
경기도 수원시 장안구 서부로 2066, 성균관대학교
내 (천천동)
(72) 발명자
추현승
경기도 과천시 별양로 111, 주공apt. 507-808 (별
양동)
김홍석
경기도 수원시 장안구 서부로2105번길 26-14,
C/103 (율전동, 미래하우스)
차명수
경기도 수원시 장안구 덕영대로381번길 78, 102호
(율전동)
(74) 대리인
김삼용
전체 청구항 수 : 총 14 항 심사관 : 정헌주
(54) 발명의 명칭 최대 피에프 선택을 기반으로 하는 상향 링크 스케쥴링 방법 및 이를 수행하는 스케쥴링 장치
(57) 요 약
상향링크 스케쥴링 방법 및 스케줄링 장치가 개시된다. 상기 상향링크 스케쥴링 방법은 복수의 단말과 무선 채널
을 통하여 연결된 기지국의 스케쥴링 장치에서 N-N은 양의 정수-개의 단말에 대응되는 N개의 행과 K-K는 양의 정
수-개의 자원 블록(Resource Block, RB)에 대응되는 K개의 열로 이루어진 N x K 2차원 배열로 각 RB별로 상기 N
개의 단말의 메트릭 값을 입력받는 단계와, 상기 스케쥴링 장치에서 K개 RB 열의 각 RB 열 별로 최대 매트릭 값
을 기반으로 상기 N x K 2차원 배열에서 자원 할당을 수행하는 단계를 포함한다. 기존의 자원할당을 이웃 RB로
만 확장하는 스케줄링 기법보다 자원 할당 경로 고려를 조금 더 유동적으로 수행할 수 있으며, 기존 RME와 IRME
스케줄링 알고리즘보다 낮은 복잡도를 가지고 간단하면서도 높은 처리율을 가질 수 있으며, 향상된 수준의 공평
성(fairness)을 보장할 수 있다.
대 표 도 - 도6
등록특허 10-1242049
- 1 -
특허청구의 범위
청구항 1
복수의 단말과 무선 채널을 통하여 연결된 기지국의 스케쥴링 장치에서 수행되는 상향링크 스케쥴링 방법에 있
어서,
N-N은 양의 정수-개의 단말에 대응되는 N개의 행과 K-K는 양의 정수-개의 자원 블록(Resource Block, RB)에 대
응되는 K개의 열로 이루어진 N x K 2차원 배열로 각 RB별로 상기 N개의 단말의 메트릭 값을 입력받는 단계; 및
상기 스케쥴링 장치에서 K개 RB 열의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2차원 배열에서 자
원 할당을 수행하는 단계를 포함하되,
상기 상향링크 스케쥴링 방법은 상향링크에서 SC-FDMA를 사용하는 LTE 이동통신 시스템에서 자원블록(RB)의 연
속적 할당을 위해 적용되는 것을 특징으로 하는 상향링크 스케쥴링 방법.
청구항 2
제1항에 있어서, 상기 스케쥴링 장치에서 K개 RB 열의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2
차원 배열에서 자원 할당을 수행하는 단계는
상기 K개 RB 열에 속하는 각 RB 열 별 최대 매트릭 값들을 모두 고려되어 모든 RB에 대해 자원 할당이 완료될
때까지 수행하는 것을 특징으로 하는 상향링크 스케쥴링 방법.
청구항 3
제2항에 있어서, 상기 스케쥴링 장치에서 K개 RB 열의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2
차원 배열에서 자원 할당을 수행하는 단계는
상기 K개 RB 열의 각 RB 열별로 최대 메트릭값을 선택하여 제1 집합을 구성하는 단계; 및
상기 제1 집합에 포함된 최대 매트릭 값들을 내림차순으로 선택하여 자원의 연속성 제약 조건을 만족하는지 여
부를 확인하는 단계를 포함하는 것을 특징으로 하는 상향링크 스케쥴링 방법.
청구항 4
제3항에 있어서, 상기 스케쥴링 장치에서 K개 RB 열의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2
차원 배열에서 자원 할당을 수행하는 단계는
상기 선택된 최대 메트릭값이 해당 단말에 이미 할당된 다른 메트릭 값과 연속적인 RB에 위치하지 않아 자원의
연속성 제약 조건을 만족하지 않아 자원 할당을 할 수 없게 된 경우 상기 선택된 최대 메트릭 값을 포함하고 있
는 RB 열의 다른 단말의 메트릭 값들을 내림차순으로 하나씩 확인하여 자원 할당을 수행하는 단계를 더 포함하
는 것을 특징으로 하는 상향링크 스케쥴링 방법.
청구항 5
제4항에 있어서, 상기 스케쥴링 장치에서 K개 RB 열의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2
차원 배열에서 자원 할당을 수행하는 단계는
상기 자원 할당 도중 선택된 최대 메트릭 값을 가지고 있는 RB 열내에서 가지고 있는 모든 매트릭 값이 할당 가
능하지 않은 경우 해당 RB열의 할당을 보류하고 다음 높은 메트릭 값을 선택하여 자원 할당을 수행하는 단계를
더 포함하는 것을 특징으로 하는 상향링크 스케쥴링 방법.
청구항 6
제1항에 있어서, 상기 메트릭값은 매 타임 슬롯마다 각 단말의 채널 정보와 HARQ 정보를 바탕으로 계산되는
PF(Proportional Fair) 매트릭 값인 것을 특징으로 하는 상향링크 스케쥴링 방법.
청구항 7
등록특허 10-1242049
- 2 -
삭제
청구항 8
복수의 단말과 무선 채널을 통하여 연결된 기지국의 스케쥴링 장치에 있어서,
N-N은 양의 정수-개의 단말에 대응되는 N개의 행과 K-K는 양의 정수-개의 자원 블록(Resource Block, RB)에 대
응되는 K개의 열로 이루어진 N x K 2차원 배열로 각 RB별로 상기 N개의 단말의 메트릭 값을 입력받아 K개 RB 열
의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2차원 배열에서 자원 할당을 수행하는 스케줄러를 포
함하되,
상기 스케줄러는 상향링크에서 SC-FDMA를 사용하는 LTE 이동통신 시스템에서 자원블록(RB)의 연속적 할당을 위
해 적용되는 것을 특징으로 하는 스케쥴링 장치.
청구항 9
제8항에 있어서, 상기 스케줄러는
상기 K개 RB 열에 속하는 각 RB 열 별 최대 매트릭 값들을 모두 고려되어 모든 RB에 대해 자원 할당이 완료될
때까지 수행하는 것을 특징으로 하는 스케쥴링 장치.
청구항 10
제9항에 있어서, 상기 스케줄러는
상기 K개 RB 열의 각 RB 열별로 최대 메트릭값을 선택하여 제1 집합을 구성하고,
상기 제1 집합에 포함된 최대 매트릭 값들을 내림차순으로 선택하여 자원의 연속성 제약 조건을 만족하는지 여
부를 확인하는 것을 특징으로 하는 스케쥴링 장치.
청구항 11
제10항에 있어서, 상기 스케줄러는
상기 선택된 최대 메트릭값이 해당 단말에 이미 할당된 다른 메트릭 값과 연속적인 RB에 위치하지 않아 자원의
연속성 제약 조건을 만족하지 않아 자원 할당을 할 수 없게 된 경우 상기 선택된 최대 메트릭 값을 포함하고 있
는 RB 열의 다른 단말의 메트릭 값들을 내림차순으로 하나씩 확인하여 자원 할당을 수행하는 것을 특징으로 하
는 스케쥴링 장치.
청구항 12
제11항에 있어서, 상기 스케줄러는
상기 자원 할당 도중 선택된 최대 메트릭 값을 가지고 있는 RB 열내에서 가지고 있는 모든 매트릭 값이 할당 가
능하지 않은 경우 해당 RB열의 할당을 보류하고 다음 높은 메트릭 값을 선택하여 자원 할당을 수행하는 것을 특
징으로 하는 스케쥴링 장치.
청구항 13
제8항에 있어서, 상기 메트릭값은 매 타임 슬롯마다 각 단말의 채널 정보와 HARQ 정보를 바탕으로 계산되는
PF(Proportional Fair) 매트릭 값인 것을 특징으로 하는 스케쥴링 장치.
청구항 14
삭제
청구항 15
제8항에 있어서, 상기 스케쥴링 장치는
각 단말의 채널 정보와 HARQ 정보를 바탕으로 계산되는 PF(Proportional Fair) 매트릭 값을 포함하는 스케쥴링
정보를 저장하는 저장부를 더 포함하는 것을 특징으로 하는 스케쥴링 장치.
등록특허 10-1242049
- 3 -
청구항 16
복수의 단말과 무선 채널을 통하여 연결된 이동통신 기지국에서 사용하기 위한 프로세서를 포함하는 통신 장치
로서,
상기 프로세서는,
N-N은 양의 정수-개의 단말에 대응되는 N개의 행과 K-K는 양의 정수-개의 자원 블록(Resource Block, RB)에 대
응되는 K개의 열로 이루어진 N x K 2차원 배열로 각 RB별로 상기 N개의 단말의 메트릭 값을 입력받아 K개 RB 열
의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2차원 배열에서 자원 할당을 수행하되, 상향링크에서
SC-FDMA를 사용하는 LTE 이동통신 시스템에서 RB의 연속적 할당을 위해 적용되도록 구성되는 프로세서를 포함하
는 통신 장치.
명 세 서
기 술 분 야
본 발명은 이동 통신 기지국에서의 스케쥴링에 관한 것으로, 더욱 상세하게는 이동 통신 기지국에서의 상향 링[0001]
크 스케쥴링 방법 및 스케쥴링 장치에 관한 것이다.
배 경 기 술
3GPP(3rd Generation Partnership Project)에서는 차세대 이동통신기술인 LTE(Long Term Evolution)으로 최근[0002]
이동 단말에서의 데이터 서비스에 대한 수요 증가로 인한 방대한 무선 자원 처리 문제의 해결이 이슈가 되고 있
다.
LTE의 다운링크에서는 OFDMA(Orthogonal Frequency Domain Multiple Access)가 사용되며, 업링크에는 SC-[0003]
FDMA(Single Carrier Frequency Division Multiple Access)가 사용된다. OFDMA는 다중경로 페이딩에 강하고 높
은 주파수 효율과 확장성이 뛰어나지만, OFDMA는 다중 반송파 변조과정을 거치면서 하나의 OFDM 심볼 안에서도
RF 전력 변동이 급격하게 변하면서 발생하는 높은 PAPR(peak-to-average power ratio)로 인해 이동 단말의 전
력에 문제를 야기한다. SC-FDMA는 단일 반송파 특징을 가지면서도 다중 접속이 가능하기 때문에 LTE 업링크에서
사용된다.
LTE 주파수 측 자원할당은 기본적으로 12개의 반송파가 하나의 물리자원블록(physical resource block; PRB)로[0004]
묶여 수행된다. SC-FDMA와 OFDMA는 무선 채널의 상태를 고려하여 시스템 주파수 자원의 일정부분인 RB(resource
block)를 각 사용자에게 할당하는 FDPS(Frequency Domain Packet Scheduling)에 의해 수행된다.
LTE 업링크에서의 FDPS에서는 주파수영역에서 각 사용자들의 채널 이득을 스케줄러의 입력으로 사용한다. 이를[0005]
위해 각 사용자는 SRS(sounding reference signal)를 스케줄링 노드- 기지국(eNodeB)-로 전송하고, SRS 신호는
업링크에 대한 CQI(Cchannel quality indicator) 리포팅 용도로 사용된다. 상기 CQI 정보는 매
TTI(Transmission Time Interval)마다 기지국에서 갱신된다. FDPS에서는 이렇게 얻어진 CQI정보와 HARQ 관리자
(manager)로부터 받는 재전송을 수행해야 할 사용자의 수의 정보를 이용하여 스케줄링을 수행할 전체 사용자의
수와 RB 값을 결정한다. RB는 12개의 부반송파(subcarrier)로 구성되어 있으며 사용자 위치와 각 주파수 별 채
널 상태가 다르기 때문에 모든 RB 값은 다른 상태 값을 가진다. RB의 상태 값으로 구성된 각 사용자의 스케줄링
매트릭 값으로 비례적 공정(Proportional Fair; 이하 PF) 알고리즘을 사용할 수 있다. PF 알고리즘은 스케줄링
의 수행과정에서 채널상태가 좋은 특정 사용자에게 자원할당이 집중되는 것을 막고 모든 사용자에게 일정 수준
의 자원을 할당하여 처리율(throughput)과 동시에 공평성(fairness)도 만족시키기 위해 필요하다.
SC-FDMA는 특별히 낮은 PAPR을 유지하기 위해 LFDMA(Localized Frequency Division Multiple Access)가 요구됨[0006]
으로 각 사용자에게 할당될 RB가 연속적이어야 하는 연속성 제약(contiguity constraint)을 가진다. 업링크에서
의 자원할당은 상기와 같은 연속성 제약(contiguity constraint)과 함께 높은 다중 사용자 다이버시티 이득
(multi-user diversity gain)이 가능한 채널-인식 스케줄링 (channel-aware scheduling)을 사용한다. 업링크
스케줄링은 각 사용자의 채널에 대한 연속적인 라디오 채널의 정보 (i.e., signal to interference and noise
ratio, SINR)를 이용하여 만들어지는 스케쥴링 매트릭(scheduling metric)을 바탕으로 수행된다. 예를 들어, 일
정 수준의 공평성(fairness)를 보장하기 위해 PF(proportional fair) 매트릭을 바탕으로 수행된다.
앞서 서술한 것처럼, LTE 업링크의 자원할당은 단일 반송파 특성을 유지하기 위해 각 타임슬롯마다 (i.e., sub-[0007]
등록특허 10-1242049
- 4 -
frame) 한 사용자에게 할당될 RB가 주파수 영역에서 연속적으로 할당되어야 한다("Proportional Fair
Scheduling of Uplink Single-Carrier FDMA Systems," IEEE Proc. of the PIMRC, Sep. 2006, J. Lim, H.G.
Myung, 및 D.J. Goodman).
"Channel-Aware Scheduling Algorithms for SC-FDMA in LTE Uplink"(IEEE Proc. of the PIMRC, Dec. 2008, L.[0008]
Temino, G. Berardinelli, S. Fattasi, 및 P. Mogensen)에서는 PF 매트릭이 가장 높은 사용자를 기준으로 이웃
에게 확장하는 방법인 세 가지 기법이 제안되었다. 제안된 세 가지 스케줄링 기법에 대한 성능평가 결과 가장
우수한 기법은 RME(Recursive Maximum Expansion)이다.
도 1은 RME 알고리즘이 주어진 4명의 UE와 7개의 RB으로 구성된 배열에서 수행되었을 경우의 자원 할당 상태를[0009]
나타낸 개념도이다.
RME 알고리즘은 주파수 영역 스케쥴러(frequency domain scheduler)가 입력 받은 PF 매트릭으로 구성된 다차원[0010]
배열에서 최대 PF 매트릭 값을 선택한 후, 최대 PF 매트릭 값을 기준으로 이웃 RB로 자원 할당을 확장하여 스케
쥴링을 수행한다.
구체적으로, 도 1을 참조하면, RME 알고리즘의 수행은 다음과 같은 절차로 수행된다. 먼저, 2차원 배열 M에서[0011]
가장 큰 PF 매트릭값을 가지는 UE와 RB를 찾고 자원을 할당한다. 그 다음 할당된 매트릭 값을 기준으로 오른쪽
과 왼쪽의 이웃 RB의 값이 해당 RB가 가지고 있는 모든 UE의 값 중 가장 높은지 확인하고 할당 여부를
결정한다. 이 자원 할당의 확장은 비교대상이 되는 매트릭 값보다 해당 RB의 더 높은 값을 가진 다른 UE가 나타
날 때까지 계속해서 수행한다. 자원 할당의 확장이 끝나면 할당된 UE (row)와 RB들 (columns)은 배열에서 삭제
한다. 스케줄러는 남아 있는 배열 중 가장 높은 PF 매트릭을 선택하여 모든 UE가 할당될 때까지 위 과정을 반복
해서 수행한다. 만약, 모든 UE가 할당되고 RB는 모두 할당되지 않았다면, 남아 있는 RB의 할당은 자원의 연속성
제약에 따라 이미 할당된 양쪽의 UE중 높은 매트릭 값을 가진 UE에 의해 결정된다.
구체적으로, 도 1을 참조하면, RME 알고리즘의 수행은 다음과 같은 절차로 수행된다. 전체 2차원 배열 M에서 가[0012]
장 높은 PF 메트릭 값을 가지는 UE 및 RB(도 1에서 UE 2의 RB 6의 50)를 찾아 자원을 할당한다. 그 다음 상기
할당된 가장 높은 PF 메트릭 값(UE2 및 RB 6)을 기준으로 이웃(좌우) RB의 메트릭값들이 해당 RB 열(해당 RB를
가지고 있는 모든 UE들을 포함)의 값 중에서 가장 큰 값을 가지는지 체크하여 가장 큰 값을 가지는 경우에 이를
할당(좌측 RB5 열에서 42가 가장 크므로 42는 할당하고 우측 RB7에서 40은 RB7열에서 가장 큰 값이 아니므로 할
당하지 않음)으로써 이웃 RB에 확장시킨다. 이와같은 자원 할당의 확장은 비교 대상이 되는 매트릭 값보다 해당
RB의 더 높은 값을 가진 다른 UE가 나타날 때까지 계속해서 수행한다. 자원 할당의 확장이 끝나면 할당된 UE가
속하는 행(row)과 할당된 RB가 속하는 열(columns)은 배열에서 삭제한다. 스케줄러는 남아 있는 배열 중 가장
높은 PF 매트릭값을 선택하여 모든 UE가 할당될 때까지 상기 과정을 반복해서 수행한다. 만약, 모든 UE가 할당
되고 RB는 모두 할당되지 않았다면, 남아 있는 RB의 할당은 자원의 연속성 제약에 따라 이미 할당된 양쪽의 UE
중 높은 매트릭 값을 가진 UE에 의해 결정된다. 구체적으로, 상기 배제된 UE 2 및 RB 5열, RB 6열을 제외한 나
머지에서 UE1 및 RB 7의 45가 가장 큰 값이므로 자원 할당하고, UE1에 속하는 RB 7의 좌우 RB들에 대해 상기 RB
확장 과정을 적용하면 RB 6의 43은 할당하지 않게 된다. 그 다음 남아 있는 배열 중 UE3 및 RB 4의 35가 가장
큰 메트릭 값이므로 자원 할당하고, UE3에 속하는 RB 4의 좌우 RB 들에 대해 RB 확장을 다시 적용하면 RB 3의
28은 배제된 UE 및 RB를 제외한 RB 3열에서 가장 크므로 자원 할당하고 RB 5의 25는 이미 배제된 RB 5에 속하므
로 자원 할당하지 않는다. 그 다음 상기 배제된 UE 및 RB 열을 제외한 나머지 배열에서 UE 4 및 RB 2의 34가 가
장 큰 메트릭값을 가지므로 자원 할당하고, UE 4에 속하는 RB 2의 좌우 RB들에 대해 RB 확장을 다시 적용하면
RB1의 30은 배제된 UE 및 RB를 제외한 RB 1열에서 가장 크므로 자원 할당하고 RB 3의 15는 이미 배제된 RB 3에
속하므로 할당하지 않는다. 기존의 RME 알고리즘은 이와 같은 PF 스케줄링을 통하여 메트릭값을 각 UE에게 할당
한다.
그러나, 전술한 기존의 RME 알고리즘은 항상 이웃 RB에 의해 자원 할당을 확장하기 때문에 다양한 자원 할당 경[0013]
로를 고려하지 못하므로 처리율 관점에 비교적 효율적이지 못한 단점이 있다.
"Improved Recursive Maximum Expansion Scheduling Algorithms for Uplink Single Carrier FDMA[0014]
System"(IEEE Proc. of the VTC Spring, Jun. 2010, F. Liu, X. She, L. Chen, and H. Otsuka)에서는
IRME(Improved Recursive Maximum Expansion) 기법이 제안되어, 기존의 RME 알고리즘의 처리율 관점에서의 단
점을 보완한다.
도 2는 IRME 알고리즘이 주어진 4명의 UE와 7개의 RB으로 구성된 배열에서 수행되었을 경우의 자원 할당 상태를[0015]
등록특허 10-1242049
- 5 -
나타낸 개념도이다.
도 2를 참조하면, IRME는 2010년에 최초 발표된 기법으로서 이웃 RB에게만 확장하며 자원 할당을 수행하던 RME[0016]
알고리즘보다 랭킹 스레시홀드(ranking threshold; Tr value)를 통해 자원 할당 경로를 조금 더 유연하게 고려
하며 수행한다. Tr 값은 입력 값으로 설정된 값만큼 이웃 RB에게 수행하는 자원 확장의 범위를 의미하며 구체적
으로 해당 RB 열에서 RB가 가지는 Tr번째 값을 의미한다. 즉, Tr 값에 의해 이웃 RB가 가진 매트릭 값 중 Tr 번
째 높은 값까지 자원 할당 여부를 고려한다.
IRME는 알고리즘은 다음과 같이 수행된다. 이하 랭킹 스레시홀드 값 Tr이 2인 경우를 예로 들어 설명한다.[0017]
먼저, RME와 마찬가지로, 전체 2차원 배열 M에서 가장 큰 메트릭값을 가지는 UE 및 RB(도 2에서 UE 2의 RB 6의
50)를 찾아 자원 할당을 수행한 후 상기 가장 높은 메트릭값을 가지는 UE 2 및 RB 6의 이웃(좌우) RB 메트릭 값
에 대해 RB 확장을 수행하고 해당 RB의 다른 UE가 가진 더 높은 값이 나타날 때까지 연속적으로 할당한다. RB
확장 절차가 끝나면 할당된 UE가 속하는 행(row)과 할당된 RB가 속하는 열(column)은 전체 배열에서 제외하고,
남아 있는 매트릭 값에서 Tr 값을 적용하여 할당할 값을 찾는다. 만약 Tr 값이 1이라면 RME의 할당과정과 동일
하게 수행된다. 위 과정을 반복 수행하고 주어진 Tr 값의 수만큼 고려되는 자원 할당 가능한 경로 중 전체 매트
릭 값들의 합이 가장 높은 경로를 최종적으로 결정하여 자원을 할당한다. IRME는 결과적으로 Tr 값을 제외한 알
고리즘의 조건은 RME와 동일하다. 예를 들어, UE 2 및 RB 6의 이웃(좌우) RB 메트릭 값에 대한 RB 확장은 Tr
값이 2인 경우 UE 2가 속하는 RB 6의 좌측 RB5에서 첫번째 및 두번째 큰 값을 선택하되 Global 메트릭값(전체
매트릭스의 매트릭값의 합)이 가장 높은 경우의 결과를 최종 할당 경로로 선택하도록 상기 첫번째 및 두번째 큰
값에서 선택하여 자원을 할당한다. 즉, RB 5 열에서 42가 가장 크므로 42는 할당하고 40은 RB 7열에서 두번째
큰 값이므로 Global 메트릭 값을 고려하여 할당한다.
그러나 전술한 IRME는 RME보다 복잡도가 높으며 공평성(fairness)이 낮고 다양한 자원 할당 경로를 고려하지 못[0018]
하므로 여전히 유연하게 자원을 할당하지 못하는 단점이 있다.
일반적으로 채널의 상태(예를 들어, SINR)는 시간과 주파수에 밀접한 연관성을 가지지만 주파수 영역에서 연관[0019]
성은 시간 영역에서의 연관성보다 강하지 못하다 (frequency selective fading distortion). 이것은 전체적인
주파수 영역에서 채널 상태는 어느 정도 연관성을 가지지만 한 개의 RB 단위로는 그렇지 못하다는 것을 의미한
다(small-scale variation).
발명의 내용
해결하려는 과제
기존 RME와 IRME 알고리즘은 2차원 배열의 최대 PF 매트릭 값 탐색 이후 최대 PF 매트릭 값의 양쪽의 이웃 RB가[0020]
가진 값들을 비교하는 방법에 의존하여 확장하는 스케줄링이다.
기존 RME와 IRME 알고리즘은 선택한 매트릭 값을 기준으로 이웃한 값으로 스케줄링을 확장하여 자원 할당을 시[0021]
도하므로 주파수 선택 페이딩에 효과적으로 대처하지 못한다.
또한, 기존 RME와 IRME 알고리즘의 자원할당 방식은 스케줄링의 유연성에 한계가 있을 뿐 아니라, IRME의 경우[0022]
많은 할당 경로를 고려할수록 복잡도가 증가하는 단점이 있다.
상기 도 1 및 2의 각 알고리즘에 의해 스케줄링을 수행하게 되면, Tr 값 2의 IRME 알고리즘이 자원할당의 경로[0023]
를 하나 더 많이 고려하게 되어 RME보다 좋은 결과를 가진다. RME 알고리즘은 간단하고 라운드 로빈(round
robin)과 같은 정적 스케줄링 알고리즘보다는 좋은 처리율 (즉, 최종 할당이 결정된 매트릭 값들의 합)을 제공
한다.
그러나 RME 알고리즘은 오직 이웃 RB의 매트릭값에 의존적으로 수행되는 알고리즘으로서 유연한 스케줄링을 제[0024]
공하지 못한다. IRME 알고리즘은 Tr 값을 통해 자원 할당 경로를 다양하게 고려함으로써 RME의 단점을 어느 정
도 보완한다. 그러나 고정된 Tr 값은 급격하게 변하는 UE의 수에 민첩하고 유연하게 대응하지 못하고 스케줄링
의 복잡도가 높아지는 결과를 가져오는 단점이 있다.
본 발명의 제1 목적은 RB가 주파수 영역에서 연속적으로 할당되어야 한다는 연속성 제약을 만족시키면서 시스템[0025]
의 처리율을 높이고 기존 스케줄링 알고리즘보다 낮은 복잡도와 향상된 수준의 공평성(fairness)을 보장할 수
있는 상향링크 스케쥴링 방법을 제공하는 것이다.
등록특허 10-1242049
- 6 -
또한, 본 발명의 제2 목적은 상기 상향링크 스케쥴링 방법을 수행하는 스케쥴링 장치를 제공하는 것이다. [0026]
또한, 본 발명의 제3 목적은 상기 상향링크 스케쥴링 방법을 수행하는 프로세서를 포함하는 장치를 제공하는 것[0027]
이다.
과제의 해결 수단
상술한 본 발명의 제1 목적을 달성하기 위한 본 발명의 일 측면에 따른 상향링크 스케쥴링 방법은, 복수의 단말[0028]
과 무선 채널을 통하여 연결된 기지국의 스케쥴링 장치에서 N-N은 양의 정수-개의 단말에 대응되는 N개의 행과
K-K는 양의 정수-개의 자원 블록(Resource Block, RB)에 대응되는 K개의 열로 이루어진 N x K 2차원 배열로 각
RB별로 상기 N개의 단말의 메트릭 값을 입력받는 단계와, 상기 스케쥴링 장치에서 K개 RB 열의 각 RB 열 별로
최대 매트릭 값을 기반으로 상기 N x K 2차원 배열에서 자원 할당을 수행하는 단계를 포함한다.
상기 스케쥴링 장치에서 K개 RB 열의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2차원 배열에서 자[0029]
원 할당을 수행하는 단계는 상기 K개 RB 열에 속하는 각 RB 열 별 최대 매트릭 값들을 모두 고려되어 모든 RB에
대해 자원 할당이 완료될 때까지 수행할 수 있다.
상기 스케쥴링 장치에서 K개 RB 열의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2차원 배열에서 자[0030]
원 할당을 수행하는 단계는 상기 K개 RB 열의 각 RB 열별로 최대 메트릭값을 선택하여 제1 집합을 구성하는 단
계와, 상기 제1 집합에 포함된 최대 매트릭 값들을 내림차순으로 선택하여 자원의 연속성 제약 조건을 만족하는
지 여부를 확인하는 단계를 포함할 수 있다.
상기 스케쥴링 장치에서 K개 RB 열의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2차원 배열에서 자[0031]
원 할당을 수행하는 단계는 상기 선택된 최대 메트릭값이 해당 단말에 이미 할당된 다른 메트릭 값과 연속적인
RB에 위치하지 않아 자원의 연속성 제약 조건을 만족하지 않아 자원 할당을 할 수 없게 된 경우 상기 선택된 최
대 메트릭 값을 포함하고 있는 RB 열의 다른 단말의 메트릭 값들을 내림차순으로 하나씩 확인하여 자원 할당을
수행하는 단계를 더 포함할 수 있다.
상기 스케쥴링 장치에서 K개 RB 열의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2차원 배열에서 자[0032]
원 할당을 수행하는 단계는 상기 자원 할당 도중 선택된 최대 메트릭 값을 가지고 있는 RB 열내에서 가지고 있
는 모든 매트릭 값이 할당 가능하지 않은 경우 해당 RB열의 할당을 보류하고 다음 높은 메트릭 값을 선택하여
자원 할당을 수행하는 단계를 더 포함할 수 있다.
상기 메트릭값은 매 타임 슬롯마다 각 단말의 채널 정보와 HARQ 정보를 바탕으로 계산되는 PF(Proportional[0033]
Fair) 매트릭 값일 수 있다. 상기 상향링크 스케줄링 방법은 상향링크에서 SC-FDMA 를 사용하는 LTE 이동통신
시스템에서 RB의 연속적 할당을 위해 적용될 수 있다.
상술한 본 발명의 제2 목적을 달성하기 위한 본 발명의 일 측면에 따른 복수의 단말과 무선 채널을 통하여 연결[0034]
된 기지국의 스케쥴링 장치는 N-N은 양의 정수-개의 단말에 대응되는 N개의 행과 K-K는 양의 정수-개의 자원 블
록(Resource Block, RB)에 대응되는 K개의 열로 이루어진 N x K 2차원 배열로 각 RB별로 상기 N개의 단말의 메
트릭 값을 입력받아 K개 RB 열의 각 RB 열 별로 최대 매트릭 값을 기반으로 상기 N x K 2차원 배열에서 자원 할
당을 수행하는 스케줄러를 포함한다.
상술한 본 발명의 제3 목적을 달성하기 위한 본 발명의 일 측면에 따른 복수의 단말과 무선 채널을 통하여 연결[0035]
된 이동통신 기지국에서 사용하기 위한 프로세서를 포함하는 장치로서, 상기 프로세서는 N-N은 양의 정수-개의
단말에 대응되는 N개의 행과 K-K는 양의 정수-개의 자원 블록(Resource Block, RB)에 대응되는 K개의 열로 이루
어진 N x K 2차원 배열로 각 RB별로 상기 N개의 단말의 메트릭 값을 입력받아 K개 RB 열의 각 RB 열 별로 최대
매트릭 값을 기반으로 상기 N x K 2차원 배열에서 자원 할당을 수행하도록 구성된다.
발명의 효과
상술한 바와 같은 상향 링크 스케쥴링 방법 및 이를 수행하는 스케쥴링 장치에 따르면, 모든 UE에게 주파수 영[0036]
역에서 자원(RB)을 연속적으로 할당해야 하는 연속성 제약을 준수하면서 각 RB열 별로 최대 매트릭 값을 우선
고려하여 어떤 채널 변경에도 효과적으로 스케줄링을 수행할 수 있도록 한다. 즉, 기존 IRME 알고리즘에서 사용
하는 랭킹 스레시 홀드(ranking threshold)와 달리 입력 파라미터 값을 더욱 다양하게 고려하기 스케쥴링을 수
행한다.
등록특허 10-1242049
- 7 -
구체적으로, 상향 링크 스케쥴링 방법은 2차원 배열 M에 입력된 각 UE와 RB에 대한 PF 매트릭 값들 중 각 RB 열[0037]
마다 최대 메트릭 값을 선택하여 큰 메트릭 값부터 하나씩 자원의 연속성 제약에 따른 자원 할당 여부를 확인함
으로써 기존의 자원할당을 이웃 RB로만 확장하는 스케줄링 기법보다 자원 할당 경로 고려를 조금 더 유동적으로
수행할 수 있다. 또한, 기존 RME와 IRME 스케줄링 알고리즘보다 낮은 복잡도를 가지고 간단하면서도 높은 처리
율을 가질 수 있으며, 향상된 수준의 공평성(fairness)을 보장할 수 있다.
또한, RB 열 별로 최대 PF 매트릭 값을 고려하여 스케줄링하기 때문에 사용자의 수의 급격한 변화에도 더욱 유[0038]
연한 스케줄링 수행이 가능하다.
도면의 간단한 설명
도 1은 기존의 RME 알고리즘이 주어진 4명의 UE와 7개의 RB으로 구성된 배열에서 수행되었을 경우의 자원 할당[0039]
상태를 나타낸 개념도이다.
도 2는 기존의 IRME 알고리즘이 주어진 4명의 UE와 7개의 RB으로 구성된 배열에서 수행되었을 경우의 자원 할당
상태를 나타낸 개념도이다.
도 3은 매 타임 슬롯마다 각 사용자 UE와 RB를 바탕으로 생성되는 PF 매트릭 값으로 구성된 2차원 배열 M을 나
타낸다.
도 4는 본 발명의 일실시예에 따른 스케쥴링 알고리즘이 적용되는 기지국 및 단말을 포함하는 이동통신 시스템
을 나타낸다.
도 5는 본 발명의 일실시예에 따른 스케쥴링 알고리즘이 4명의 사용자 UE와 7개의 RB으로 구성된 배열에서 수행
되었을 경우의 자원 할당 상태를 나타낸 개념도이고, 도 6은 본 발명의 일실시예에 따른 스케쥴링 알고리즘을
설명하기 위한 순서도이다.
도 7은 본 발명의 일실시예에 따른 스케쥴링 알고리즘을 의사 코드(Pseudo Code)로 구현할 경우의 동작 순서도
이다.
도 8은 기존의 RME 및 IRME 기법과 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법에 대해 사용자 수에 따른 공
평성(fairness) 변화를 나타낸 그래프이다.
도 9는 기존의 RME 및 IRME 기법과 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법에 대해 사용자 수에 따른 시
스템 처리율의 변화를 나타낸 그래프이다.
발명을 실시하기 위한 구체적인 내용
본 발명은 다양한 변경을 가할 수 있고 여러 가지 실시예를 가질 수 있는 바, 특정 실시예들을 도면에 예시하고[0040]
상세하게 설명하고자 한다.
그러나, 이는 본 발명을 특정한 실시 형태에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포[0041]
함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다.
제1, 제2 등의 용어는 다양한 구성요소들을 설명하는데 사용될 수 있지만, 상기 구성요소들은 상기 용어들에 의[0042]
해 한정되어서는 안 된다. 상기 용어들은 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만 사용된
다. 예를 들어, 본 발명의 권리 범위를 벗어나지 않으면서 제1 구성요소는 제2 구성요소로 명명될 수 있고, 유
사하게 제2 구성요소도 제1 구성요소로 명명될 수 있다. 및/또는 이라는 용어는 복수의 관련된 기재된 항목들의
조합 또는 복수의 관련된 기재된 항목들 중의 어느 항목을 포함한다.
어떤 구성요소가 다른 구성요소에 "연결되어" 있다거나 "접속되어" 있다고 언급된 때에는, 그 다른 구성요소에[0043]
직접적으로 연결되어 있거나 또는 접속되어 있을 수도 있지만, 중간에 다른 구성요소가 존재할 수도 있다고 이
해되어야 할 것이다. 반면에, 어떤 구성요소가 다른 구성요소에 "직접 연결되어" 있다거나 "직접 접속되어" 있
다고 언급된 때에는, 중간에 다른 구성요소가 존재하지 않는 것으로 이해되어야 할 것이다.
본 출원에서 사용한 용어는 단지 특정한 실시예를 설명하기 위해 사용된 것으로, 본 발명을 한정하려는 의도가[0044]
아니다. 단수의 표현은 문맥상 명백하게 다르게 뜻하지 않는 한, 복수의 표현을 포함한다. 본 출원에서, "포함
하다" 또는 "가지다" 등의 용어는 명세서상에 기재된 특징, 숫자, 단계, 동작, 구성요소, 부품 또는 이들을 조
합한 것이 존재함을 지정하려는 것이지, 하나 또는 그 이상의 다른 특징들이나 숫자, 단계, 동작, 구성요소, 부
등록특허 10-1242049
- 8 -
품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 미리 배제하지 않는 것으로 이해되어야 한다.
다르게 정의되지 않는 한, 기술적이거나 과학적인 용어를 포함해서 여기서 사용되는 모든 용어들은 본 발명이[0045]
속하는 기술 분야에서 통상의 지식을 가진 자에 의해 일반적으로 이해되는 것과 동일한 의미를 가지고 있다. 일
반적으로 사용되는 사전에 정의되어 있는 것과 같은 용어들은 관련 기술의 문맥 상 가지는 의미와 일치하는 의
미를 가진 것으로 해석되어야 하며, 본 출원에서 명백하게 정의하지 않는 한, 이상적이거나 과도하게 형식적인
의미로 해석되지 않는다.
이하, 첨부한 도면들을 참조하여, 본 발명의 바람직한 실시예를 보다 상세하게 설명하고자 한다. 본 발명을 설[0046]
명함에 있어 전체적인 이해를 용이하게 하기 위하여 도면상의 동일한 구성요소에 대해서는 동일한 참조부호를
사용하고 동일한 구성요소에 대해서 중복된 설명은 생략한다.
단말은 이동국(MS), 사용자 장비(UE; User Equipment), 사용자 터미널(UT; User Terminal), 무선 터미널, 액세[0047]
스 터미널(AT), 터미널, 가입자 유닛(Subscriber Unit), 가입자 스테이션(SS; Subscriber Station), 무선 기기
(wireless device), 무선 통신 디바이스, 무선송수신유닛(WTRU; Wireless Transmit/Receive Unit), 이동 노드,
모바일 또는 다른 용어들로서 지칭될 수 있다. 단말의 다양한 실시예들은 셀룰러 전화기, 무선 통신 기능을 가
지는 스마트 폰, 무선 통신 기능을 가지는 개인 휴대용 단말기(PDA), 무선 모뎀, 무선 통신 기능을 가지는 휴대
용 컴퓨터, 무선 통신 기능을 가지는 디지털 카메라와 같은 촬영장치, 무선 통신 기능을 가지는 게이밍 장치,
무선 통신 기능을 가지는 음악저장 및 재생 가전제품, 무선 인터넷 접속 및 브라우징이 가능한 인터넷 가전제품
뿐만 아니라 그러한 기능들의 조합들을 통합하고 있는 휴대형 유닛 또는 단말기들을 포함할 수 있으나, 이에 한
정되는 것은 아니다.
기지국은 일반적으로 단말과 통신하는 고정된 지점을 말하며, 베이스 스테이션(base station), 노드-B(Node-B),[0048]
e노드-B(eNode-B), BTS(base transceiver system), 액세스 포인트(access point) 등 다른 용어로 불릴 수
있다.
도 3은 매 타임 슬롯마다 각 사용자 UE와 RB를 바탕으로 생성되는 PF 매트릭 값으로 구성된 2차원 배열 M을 나[0049]
타낸다.
M은 [i x j]의 크기를 가진다. 는 사용자 i와 RB j의 PF 매트릭값을 의미하기 때문에 M은 로[0050]
나타낼 수 있다 (즉, ).
FDPS 스케줄러는 결과적으로 매 타임슬롯마다 도 3의 입력 매트릭 값으로 하기 수학식 1을 만족하며 수행되는[0051]
것을 목적으로 한다.
수학식 1
[0052]
는 0 또는 1값을 가지는 지시자(indicator)로서 해당 값에 대한 최종적인 자원 할당 여부를 나타낸[0053]
다 (즉, ).
도 4는 본 발명의 일실시예에 따른 스케쥴링 알고리즘이 적용되는 기지국 및 단말을 포함하는 이동통신 시스템[0054]
을 나타낸다.
등록특허 10-1242049
- 9 -
도 4를 참조하면, 본 발명의 일실시예에 따른 이동통신 시스템은 복수의 단말(200) 및 기지국(100)을 포함한다. [0055]
기지국(100)은 유선망(400)을 통하여 코아망(core network)과 연결되며, 복수의 단말(200)과 무선 채널 환경[0056]
(300)을 통하여 데이터를 송수신한다. 상기 복수의 단말은 UE 1(20-1), UE 2(20-2), ..., UE N(20-N)(N은 양의
정수)를 포함한다. 기지국(100)은 스케쥴러(122)를 포함하는 스케쥴링 장치(120)를 포함한다.
기지국(100)의 스케쥴링 장치(120)는 스케쥴러(122)에서 단말(200)로부터 제공되는 스케쥴링 정보를 토대로 본[0057]
발명의 일실시예에 따른 해당 단말의 상향 링크 채널에 대한 MSCC(Maximum PF Selection with Contiguity
Constraint) 스케쥴링을 수행한다. 상기 스케쥴링 정보는 각 단말의 채널 정보와 HARQ 정보를 바탕으로 계산되
는 PF(Proportional Fair) 매트릭 값을 포함할 수 있다. 상기 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법에
대해서는 후술한다.
스케쥴링 장치(120)는 상기 스케쥴링 정보를 저장하는 저장부(120)를 더 포함할 수 있다. [0058]
본 발명의 일실시예에 따른 MSCC 스케쥴링 방법의 적용은 LTE 상향링크 SC-FDMA으로 한정되는 것은 아니며, 이[0059]
하에서는 예를 들어 LTE 상향링크 SC-FDMA에서의 FDPS을 위해 스케쥴러(122)에서 수행되는 스케쥴링 알고리즘을
설명한다. 이하에서는, 4명의 사용자 UE와 RB1 부터 RB7까지 7개의 RB로 구성된 2차원 배열을 가진 경우를 예로
들어 설명한다.
도 5는 본 발명의 일실시예에 따른 스케쥴링 알고리즘이 4명의 사용자 UE와 7개의 RB으로 구성된 배열에서 수행[0060]
되었을 경우의 자원 할당 상태를 나타낸 개념도이고, 도 6은 본 발명의 일실시예에 따른 스케쥴링 알고리즘을
설명하기 위한 순서도이다.
본 발명의 일실시예에 따른 스케쥴링 알고리즘은 각 RB 열별로 최대 메트릭값을 찾고 자원의 연속성 제약 조건[0061]
을 만족하는지 여부를 확인하면서 각 RB 열별로 최대 매트릭 값을 우선 고려하여 자원을 할당한다.
도 6을 참조하면, 먼저 각 RB 열별로 모든 UE의 메트릭값을 2차원 배열 M으로 입력받고(단계 601), 각 RB 열별[0062]
로 최대 메트릭값을 선택하여 집합 S를 구성한다(단계 620). 집합 S에서 최대 매트릭값을 찾고 자원의 연속성
제약 조건을 만족하는지 여부를 확인한다(단계 630).
선택된 최대 메트릭값이 해당 단말에 이미 할당된 다른 메트릭 값과 연속적인 RB에 위치하지 않아 자원의 연속[0063]
성 제약 조건을 만족하지 않아 할당할 수 없게 된 경우 선택된 최대 메트릭값을 포함하고 있는 RB 열의 다른 UE
의 메트릭 값들을 내림차순으로 하나씩 확인하여 자원 할당을 수행한다(단계 640).
상기 자원 할당 도중 선택된 최대 메트릭값을 가진 RB 열내에서 모든 메트릭값이 자원 할당이 가능하지 않은 경[0064]
우 현재 선택된 최대 메트릭값을 포함하고 있는 RB 열의 자원 할당을 보류하고 다음 높은 메트릭 값을 선택하여
자원할당을 수행한다(단계 650).
모든 RB에 자원할당을 완료하였는지 판단하여(단계 660) 모든 RB에 자원할당을 완료한 경우에는 자원 할당 과정[0065]
을 종료하고, 모든 RB에 자원할당이 완료되지 않은 경우에는 단계 620부터 다시 수행한다.
도 5를 참조하여, 4명의 사용자 UE와 7개의 RB으로 구성된 배열을 예로 들어 본 발명의 일실시예에 따른 스케쥴[0066]
링 알고리즘을 설명한다.
1) 주어진 2차원 배열에서 각 RB 열 별로 가장 높은값을 선택하여 집합 S를 구성하고, 집합 S에 포함된 값들을[0067]
내림차순으로 정리한다(50-45-42-38-33-34-30).
2) 상기 집합 S에 포함된 값들을 내림차순으로 정리한 상태에서 높은 순서대로 자원 할당을 확인한다(50-45-[0068]
42).
3) 선택된 RB 열 별 최대 메트릭 값이 해당 UE에 이미 할당된 다른 메트릭값과 연속적인 RB에 위치하지 않아 자[0069]
원의 연속성 제약 조건을 만족하지 않을 경우, 선택된 RB 열 별 최대 메트릭 값이 포함된 RB의 다음 높은 메트
릭값 순서대로 할당 여부를 확인한다 (40 대신 38, 33 대신 30).
4) 자원 할당 도중 선택된 메트릭 값을 가지고 있는 RB 열 내에서 가지고 있는 모든 매트릭 값이 할당 가능하지[0070]
않은 경우 해당 RB열의 할당을 보류하고 다음 높은 메트릭 값을 선택하여 자원 할당을 수행한다. 즉, 만약 RB 4
열에서 UE 1 내지 UE 4까지 가지고 있는 매트릭 값 모두가 할당이 되지 않을 경우 RB 4열의 할당을 보류하고 다
음 메트릭 값인 RB 2열의 할당을 먼저 수행한 후 RB 4를 다시 확인한다.
도 7은 본 발명의 일실시예에 따른 스케쥴링 알고리즘을 의사 코드(Pseudo Code)로 구현할 경우의 동작 순서도[0071]
등록특허 10-1242049
- 10 -
이다. 표 1은 본 발명의 일실시예에 따른 스케쥴링 알고리즘을 의사 코드(Pseudo Code)로 나타낸 표이다. 도 7
에서 사용되는 모든 표기(notation)들은 표 1의 의사 코드와 동일하게 사용된다.
스케줄러(122)는 기본적인 FDPS 시스템과 동일하게 각 RB 열마다 모든 UE의 PF 매트릭 값들을 입력받아 모든 RB[0072]
의 할당이 결정될 때까지 스케줄링을 수행한다.
본 발명의 일실시예에 따른 MSCC의 자원 할당 절차는 초기화 과정(단게 701)을 거친 후 크게 스텝 A(단계 703,[0073]
705, 707, 709, 711)와 스텝 B(단계 721, 723, 725, 727, 729, 731)의 2 단계의 절차를 가진다.
초기화 과정에서 스케줄러(122)는 입력된 매트릭 값으로 UE와 RB에 대한 2차원 배열 (i.e., 집합 U)을 생성하고[0074]
각 RB 열 별로 최대 메트릭 값을 찾는다(단계 701). 집합 U는 이러한 N개의 UE와 K개의 RB를 바탕으로 만들어진
모든 스케줄링 매트릭 값들의 모임을 의미한다. 집합 S는 이러한 각 RB 별 최대 메트릭값들로 구성된다. 선택된
매트릭 값은 로 정의되며 n과 k는 각각 해당 메트릭값을 가리키는 UE와 RB를 의미한다. 집합 A는 자원 할
당 여부를 나타내는 지시자(indicator) 들의 집합으로 S와 동일한 크기의 배열에 모든 값은 0으로 초기화
된다.
Step A[0075]
스텝 A에서는 집합 S에서 가장 높은 매트릭 값을 찾고 선택된 매트릭 값 이 자원의 연속성 제약 만족 여부[0076]
를 확인한다(단계 703, 705, 707, 709, 711).
자원의 연속성 제약은 선택된 매트릭 값 을 가지고 있는 UE에게 자원 할당이 처음이거나 할당받기로 결정[0077]
된 자원과 연속적인 RB에 위치해야 하는 것을 의미한다.
선택된 매트릭 값 이 자원의 연속성 제약 만족하여 자원 할당이 결정되면, 스케줄러(122)는 최종 할당된[0078]
PF 매트릭 값들을 나타내는 집합 A의 지시자(indocator) 를 1로 변경한다( ←1, 단계 711). 변경된
지시자의 값은 해당 UE에게 그 RB가 할당되는 것을 의미한다. 또한, 집합 A에 선택된 매트릭 값이 포함되면, 스
케줄러(122)는 집합 U에서 할당된 RB의 모든 메트릭 값들 (i.e., 집합 R)을 제외한다(U ← U - R, 단계 711).
집합 R은 선택된 매트릭 값 을 가지고 있는 RB의 모든 값들의 구성을 의미하며 선택된 값이 할당될 수 없
게 된 경우 사용된다. 집합 U는 각 RB 열별 최대 매트릭 값들이 구성된 집합 S에서 선택된 메트릭 값이 제외되
고 남은 값들의 모임을 의미한다.
Step B[0079]
단계 709의 판단결과, 선택된 매트릭 값 이 자원의 연속성 제약으로 자원 할당을 할 수 없게 된 경우, 선택[0080]
된 메트릭 값 을 포함하고 있는 RB 열의 다른 UE의 값(i.e., )들을 내림차순으로 하나씩 확인하여
자원 할당을 시도한다(단계 721, 723, 725, 727, 729, 731).
해당 RB 열이 가지고 있는 모든 매트릭 값 비교 후에도 자원 할당이 결정될 수 없다면, 현재 선택된 메트릭 값[0081]
을 포함하고 있는 RB 열의 자원 할당을 보류하고, 각 RB 열 별 최대 메트릭 값들의 집합 중 다음 높은 메트릭
값을 선택하여 스케줄링을 진행한다 (i.e., X ← X 1, 단계 720 내지 단계 727).
보류된 RB 열의 자원 할당은 진행되고 있는 RB의 할당이 결정될 때마다 다시 확인한다. 본 발명의 일실시에에[0082]
따른 스케줄링 방법은 집합 S가 비어있는지 확인하여 집합 A에 따라서 모든 RB가 할당될 때까지 수행되므로(단
계 741, 743), 보류된 RB 열는 결국 어떤 매트릭 값을 할당받을 수 밖에 없다.
다시 5를 참조하면, 도 5의 2차원 배열은 기존의 RME와 IRME 기법을 설명하면서 사용하였던 예를 본 발명의 일[0083]
실시예에 따른 MSCC 스케줄링 방법에 적용하였을 때 나타난 결과이다. 도 7의 순서도에서 설명한 바와 같이 주
어진 2차원 배열 M에서 각 RB 열의 최대 매트릭 값들을 찾고, 찾은 메트릭 값들로 가장 높은 메트릭 값부터 하
나씩 자원의 연속성을 비교한다. 도 5의 점선의 원은 해당 RB 열에서 최대 매트릭 값으로 선택되었지만, 자원의
등록특허 10-1242049
- 11 -
연속성 제약을 만족하지 못하여 해당 RB 열의 다른 메트릭 값이 할당되었기 때문에 제외됨을 의미한다. 도 7의
순서도에 따라 수행한 결과, 모든 RB에 할당하기로 결정된 매트릭 값들의 합은 272로써 RME (264)와 IRME (26
6)를 수행했을 때 얻어진 합보다 큼을 알 수 있다.
본 발명의 일실시예에 따른 MSCC 스케쥴링 방법이 기존의 RME 및 IRME 기법보다 더 높은 매트릭 합을 가질 수[0084]
있는 이유는 기존의 RME 및 IRME 기법과 같이 하나의 최대 매트릭 값 선택 이후 해당 RB의 이웃으로 확장하여
메트릭 값을 비교하여 자원 할당을 수행하는 것이 아니라, 각 RB 열별로 최대 메트릭 값들을 우선적으로 할당하
였기 때문이다. 그러므로 본 발명의 일실시예에 따른 스케줄링 방법은 매 수행마다 좀 더 동적으로 유연하게 자
원할당을 수행할 수 있다.
의사 코드(Pseudo Code)[0085]
본 발명의 일실시예에 따른 MSCC의 의사 코드 절차는 표 1에 나타내었다. 의사 코드는 도 7의 순서도와 동일한[0086]
절차와 표기를 가진다. 전체 스케줄링은 각 RB 열 별 최대 매트릭 값들이 모두 고려되어 해당 RB의 자원할당이
완료될 때까지 수행한다. 이는 집합 S에 구성된 매트릭 값이 완전히 없어질 때까지 반복됨을 의미한다 (step
A). 스케줄러(122)는 선택된 매트릭 값 의 자원의 연속성을 만족 여부를 파악한다. 만약 선택된 메트릭 값
이 연속성 제약을 만족하지 못하면, 변수 y를 이용하여 선택된 매트릭 값 을 포함하고 있는 RB 열의
다른 값이 큰 순서대로 반복 확인된다(i.e., step B). 선택된 RB 열의 모든 매트릭 값이 연속성을 만족하지 못
하는 경우, 변수 x를 증가시켜 집합 S의 다음 메트릭 값을 우선 수행하게 된다 (i.e., 변수 y가 step B에서 N값
을 초과했을 경우). 선택된 새 매트릭 값의 자원 할당이 완료되면 스케줄러(122)는 보류한 이전 메트릭 값을 새
롭게 바뀐 배열 상태에서 자원할당이 가능한지 다시 확인한다.
등록특허 10-1242049
- 12 -
표 1
1: x ←1 , y ← 2[0087]
2: Let the set S be the highest metric of each RB
3: Let , all indicators in the set A, be 0
4: while (S ≠ 0 ) do // step A.
5: ← x-th highest metric in the set S
6: Let the set R be the set of all scheduling metric s in RBk
7: if (mn,k is the first RB assigned to user n) or ( is adjacent to RB assigned to user
n) then
8: ←1, U ← U - R, S ← S - { }
9: x ←1
10: Else
11: while (y ≤N) do // step B.
12: x ←x 1
13: ← y-th highest metric in the set R
14; if ( is adjacent to RB assigned to user ) then
15: ←1, U ← U - R, S ← S - { }
16; x ←1 , y ← 2
17; break
18: else
19: y ←y 1
본 발명의 일실시예에 따른 MSCC 스케쥴링 방법에 따르면, 각 UE의 채널정보와 HARQ 정보를 바탕으로 계산된 스[0088]
케줄링 매트릭 값들을 바탕으로 구성된 이차원 배열에서 자원 할당을 수행한다. 본 발명의 일실시예에 따른
MSCC 스케쥴링 방법은 기존의 RME와 IRME 기법과는 달리, 자원의 연속성을 위해 이웃 RB에게 확장하며 스케줄링
을 수행하지 않고 각 RB 열 별 최대 매트릭 값을 기반으로 스케줄링이 수행된다. 그러므로 본 발명의 일실시예
에 따른 MSCC 스케쥴링 방법은 모든 UE마다 발생할 수 있는 채널 이득의 급격한 변화 (sudden drop)에 보다 효
율적으로 대처할 수 있는 장점을 가진다. 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법은 기존 IRME기법처럼
정적인 입력 값 (i.e., ranking threshold)을 가지지 않고 모든 입력 배열 값마다 동적으로 스케줄링 수행이 가
능하기 때문에 UE의 수 및 채널 환경의 급격한 변화에 동적으로 유연하게 대처할 수 있다. 본 발명의 일실시예
에 따른 MSCC 스케쥴링 방법은 스케줄링 수행에 필요한 복잡도 관점에서도 정렬된 최대 매트릭 값을 기반으로
수행되므로 기존 RME 및 IRME 기법에 비해 낮다.
등록특허 10-1242049
- 13 -
성능 평가(Performance Evaluation)[0089]
이하에서는 복잡도 분석 및 시뮬레이션 분석을 통해 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법의 성능 평[0090]
가 결과를 설명한다.
우선, 복잡도 분석 부분(Complexity Analysis)에서는 기존 RME, IRME 및 본 발명의 일실시예에 따른 MSCC 스케[0091]
쥴링 방법의 알고리즘 복잡도를 시간 측면에서 분석한다.
각 알고리즘 기법마다 최악의 경우를 고려하여 UE가 RB보다 큰 경우, RB가 UE보다 큰 경우의 복잡도를 고려하여[0092]
최종적으로 계산된 복잡도를 보여준다. 시뮬레이션 분석 부분(Simulation Analysis)에서는 스케줄링을 수행하는
데 필요한 시뮬레이션 파라미터를 정의하고 관련 수식에 대해 세부적으로 설명하며, 시뮬레이션 결과를 보여주
고 분석한다.
복잡도 분석(Complexity Analysis)[0093]
먼저 RME의 복잡도를 분석한다. RME는 주어진 이차원 배열에서 최대 매트릭 값을 기준으로 좌우 양방향에 위치[0094]
한 이웃 RB에게 자원 할당을 시도한다. 여기에서는 각 스케줄링이 최악의 경우를 고려하여 이웃 RB에게 확장한
자원 할당은 시도되지 않는다고 가정한다. 첫 번째 경우는 UE의 수가 RB의 수보다 큰 상태이다(i.e., N>K). RME
는 K 값이 1이 될 때까지 스케줄링을 수행하게 되므로 최초 스케줄링 매트릭 값을 찾는데 필요한 복잡도는 NK
에서 (N-(K-1))·(K-(K-1)) 만큼의 시간 비용이 필요하다. 이 복잡도를 정리하면
로 표현될 수 있으며 등차수열 및 등비수열 정리를 통해 로 정리된
다. 반대로, K > N 의 경우, NK에서 (N-(N -1))·(K-(N-1))까지 비용이 필요하게 되며
로 나타난다. 정리된 복잡도는 로 나타나게 되므로, 두 경우를 종합하
여 도출되는 최종 복잡도는 이다.
다음은 IRME의 복잡도 분석이다. IRME 기법은 RME의 스케줄링 방식과 유사하게 수행하지만 처리율 측면에 조금[0095]
더 유연한 스케줄링을 제공하기 위해 랭킹 스레시홀드(ranking threshold) 값과 같은 임계값이 필요하다. 상기
임계 값은 스케줄링을 수행하기 이전에 입력되는 값으로 스케줄러(122)에게 정적으로 제공되는 정적인 값이다.
그러므로 IRME가 수행되는데 가장 최악의 경우는 UE의 수만큼 랭킹 스레시홀드(ranking threshold)가 적용이 되
어 모든 스케줄링을 수행할 때마다 임계 값을 수행하는 경우이다. 이 경우의 복잡도는 N > K의 경우, UE 만큼의
임계값과 RME의 복잡도가 필요하므로 로 계산되어 정리된 결과는 가 된다. 반대로 K >
N 의 경우, 복잡도는 가 필요하게 되어 로 정리된다. 두 경우를 모두 고려하여 계산
된 최종 비용은 이다.
마지막으로 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법의 복잡도를 분석한다. 본 발명의 일실시예에 따른[0096]
MSCC 스케쥴링 방법은 입력된 2차원 배열에서 각 RB별로 찾아낸 최대 매트릭 값들을 기준으로 스케줄링을 수행
한다. 여기서, 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법의 알고리즘 수행에서 최악의 경우로 선택된 각
RB 열 별 최대 매트릭 값들이 모두 자원의 연속성 제약을 만족하지 못하고 선택된 매트릭 값을 가진 RB 열의 모
든 매트릭 값을 비교해야 한다고 가정한다.
먼저 스케줄러(122)가 각 RB 열의 최고 매트릭 값들을 찾기 위해 모든 매트릭 값을 가지고 이진 검색(Binary[0097]
Search)을 수행하게 되는 필요 복잡도는 NKlog2N이다. 선택된 각 RB 열 별 최대 매트릭 값들은 높은 값부터 순
등록특허 10-1242049
- 14 -
차적으로 스케줄링을 하려면 내림차순 정렬을 수행해야 하므로 Klog2K 만큼의 복잡도도 필요하다. 마지막으로 선
택된 매트릭 값이 속한 RB 열의 모든 매트릭 값이 자원의 연속성 제약을 확인하는데 필요한 복잡도는 NK가
된다. N > K 의 경우, 의 복잡도는 정리되어 로 나타난다. K > N 의
경우, 복잡도는 로 정리되어 두 경우를 종합하여 최종적으로 나타낼 수 있는 복잡도는
가 된다. 만약 UE나 RB 둘 중 한 값이 극도로 작은 환경에서 복잡도가 고려된다면 결과
는 다를 수 있겠지만, 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법의 복잡도는 현재 이동통신 환경에서 고려
될 때 세 기법 중 항상 가장 낮은 값을 가진다.
표 2는 각 기법들의 복잡도(complexity)를 정리한 것이다. [0098]
표 2
[0099]
시뮬레이션 분석(Simulation Analysis)[0100]
본 발명의 일실시예에 따른 MSCC 스케쥴링 방법과 기존 RME 및 IRME 알고리즘의 공평성(fairness) 및 처리율[0101]
(throughput) 성능을 비교 분석하기 위해 3GPP LTE 시스템 모델에 기반하여 SC-FDMA의 시스템 레벨 시뮬레이션
을 수행한다.
표 3
[0102]
등록특허 10-1242049
- 15 -
여기서는, 주변 간섭을 주는 셀이 없는 단일 셀 환경에서 성능 측정을 수행한다. Typical Urban 채널 모델을 기[0103]
반으로 표 3은 시뮬레이션을 수행하는데 사용하는 파라미터를 나타낸다. 여기서는, 보다 현실적인 결과값을 분
석하기 위해 새논 용량보다 MCS table을 이용한다. 기법과 상관없이 일정 수준 이상의 공평성(fairness)을 보장
하기 위해 스케쥴링 매트릭은 PF(Proportional Fair)방식을 사용하며 수학식 2와 같이 표현한다.
수학식 2
[0104]
여기서, 는 UE i가 t시간에 RBj를 할당받을 수 있는 데이터 레이트(data rate)를 의미한다. 는 UE[0105]
i가 t시간까지 할당받은 RB의 누적 데이터 레이트(data rate)를 의미한다.
PF를 스케쥴링 매트릭으로 사용함으로써 해당 시각 t에 상대적으로 불공평하게 제공받은 UE는 다음 t에 보상받[0106]
을 수 있게 된다.
공평성(Fairness) 측면 시뮬레이션 수행을 위해서는 JFI(Jain's fairness index)를 사용하였는데 수식은 수학식[0107]
3에 나타난다.
수학식 3
[0108]
여기서, 는 시간 간격(time interval) 동안 i의 실제 데이터 전송률을 나타내고, N은 전체 시스템에[0109]
있는 사용자의 수를 나타낸다.
시뮬레이션 결과(Simulation Results)[0110]
시뮬레이션에서는 공평성(fairness) 및 시스템 처리율 관점에서 각 기법을 분석하여, 본 발명의 일실시예에 따[0111]
른 MSCC 스케쥴링 방법이 기존 RME 및 IRME 기법보다 전반적인 구간에서 높은 성능으로 수행되고, 최대 공평성
(fairness)은 3%, 처리율은 19% 향상됨을 보여준다.
도 8은 기존의 RME 및 IRME 기법과 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법에 대해 사용자 수에 따른 공[0112]
평성(fairness) 변화를 나타낸 그래프이다.
도 8을 참조하면, 기법에 상관없이 전체적으로 사용자 수가 많아 질수록 공평성(fairness)이 감소함을 알 수 있[0113]
다. 이것은 사용자 수가 점점 늘어나게 되면 그와 반비례로 사용자마다 할당받을 수 있는 RB의 수가 줄어들어
자원을 선택할 수 있는 폭이 줄어들기 때문이다.
세 기법은 스케줄링 매트릭 값이 PF로 계산되어 어느 정도 수준의 공평성(fairness) 보장이 가능하기 때문에 대[0114]
체적으로 모두 비슷한 공평성(fairness)를 가진다. 도 8에 도시된 바와 같이, IRME기법(820)은 RME에서 처리율
등록특허 10-1242049
- 16 -
측면에서 향상시킨 기법이므로 RME(830)보다 전체적으로 낮은 공평성(fairness)를 가짐을 알 수 있다. 본 발명
의 일실시예에 따른 MSCC 스케쥴링 방법(810)은 RME와 유사한 공평성(fairness)을 보장하며 사용자 40명에서 80
명 구간에 IRME 보다 최대 약 12%, RME보다 최대 약 3% 정도의 높은 공평성(fairness)을 나타낸다. 따라서 본
발명의 일실시예에 따른 MSCC 스케쥴링 방법이 기존 RME 및 IRME 기법과 유사한 공평성(fairness)을 보장함을
보여준다.
도 9는 기존의 RME 및 IRME 기법과 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법에 대해 사용자 수에 따른 시[0115]
스템 처리율의 변화를 나타낸 그래프이다. 세 기법 모두 사용자 수가 증가할수록 처리율은 높아지며 일정 수준
에서 포화상태에 이른다. 포화상태에 이르는 이유는 MCS(Modulation and Coding) 테이블을 이용하여 처리율이
계산되었기 때문이다. 사용자가 증가할수록 기법에 상관없이 시스템 처리율이 증가하는 이유는 점점 더 좋은 수
행능력을 가진 사용자에게 자원을 배분할 수 있기 때문이다. 이것은 멀티 유저 다이버시티 이득(multi-user
diversity gain)이라고 정의한다. 도 9를 참조하면, IRME(920)는 RME(930)보다 모든 구간에서 높은 처리율을
가지며 사용자 10명과 20명 지점에서 최대 17%의 차이를 보인다. 이것은 랭킹 스레시 홀드(ranking threshold)
를 통해 RME보다 더욱 유연한 스케줄링을 수행하기 때문이다. 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법
(930)은 이러한 IRME(920) 보다 모든 구간에서 높은 처리율을 나타내며 사용자 40명 구간에서 IRME(920)보다 최
대 12% 증가한 처리율을 보임으로써 수학식 1을 가장 근접하게 만족함을 보여준다.
상기에서는, LTE 업링크에서 낮은 PAPR을 위해 요구되는 SC-FDMA에서 적용되는 경우를 예를 들어 FDPS 기법을[0116]
제안하였다. 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법은 SC-FDMA의 자원의 연속성 제약을 만족하면서 높
은 시스템 처리율과 일정 수준의 공평성(fairness)를 보장하면서, 낮은 복잡도로 스케줄링을 수행할 수 있다.
본 발명의 일실시예에 따른 MSCC 스케쥴링 방법에서는 스케줄링 매트릭으로 PF 매트릭값을 이용하여 기존의 RME[0117]
와 IRME 알고리즘과 함께 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법의 성능을 비교하였고, 시뮬레이션이
진행된 거의 모든 구간에서 높은 처리율을 가짐을 확인하였다. 또한 빅오 표기법(Big O notation)을 통해 분석
된 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법의 시간 복잡도는 LTE 이동통신 환경을 기준으로 항상 기존의
두 기법보다 낮은 복잡도를 가지면서 수행됨을 확인하였다. 본 발명의 일실시예에 따른 MSCC 스케쥴링 방법이
기존의 두 기법보다 우수한 이유는 이웃 RB에게 확장하며 자원 할당을 수행하는 방식이 아닌 각 RB별 최대 매트
릭 값을 기반으로 스케줄링이 수행되기 때문이다. 그러므로 하나의 UE의 채널 상태 속에서도 급격히 이득이 변
할 수 있는 주파수 선택 페이딩 (frequency selective fading)환경에서 기존 기법들보다 더 향상된 스케줄링을
제공할 수 있다.
이상 실시예를 참조하여 설명하였지만, 해당 기술 분야의 숙련된 당업자는 하기의 특허 청구의 범위에 기재된[0118]
본 발명의 사상 및 영역으로부터 벗어나지 않는 범위 내에서 본 발명을 다양하게 수정 및 변경시킬 수 있음을
이해할 수 있을 것이다.
부호의 설명
100: 기지국 120: 스케쥴링 장치[0119]
122: 스케쥴러 124: 저장부
등록특허 10-1242049
- 17 -
도면
도면1
도면2
도면3
등록특허 10-1242049
- 18 -
도면4
도면5
등록특허 10-1242049
- 19 -
도면6
등록특허 10-1242049
- 20 -
도면7
도면8
등록특허 10-1242049
- 21 -
도면9
등록특허 10-1242049
- 22 -