KR100623000B1

KR100623000B1 - 직교주파수 분할 다중 접속 시스템의 비용함수 기반적응형 자원 할당 방법

Info

Publication number: KR100623000B1
Application number: KR1020040075239A
Authority: KR
Inventors: 김강희; 김기선
Original assignee: 광주과학기술원
Priority date: 2004-09-20
Filing date: 2004-09-20
Publication date: 2006-09-19
Anticipated expiration: 2024-09-20
Also published as: KR20060026357A

Abstract

본 발명은 직교주파수 분할 다중 접속 시스템의 비용함수 기반 적응형 자원할당방법에 있어서, a) 비용함수를 이용하여 각각의 사용자가 전송할 하위패킷을 정렬하고, 상기 정렬된 하위패킷을 각각의 부채널에 할당하는 단계; 및 b) 상기 부채널의 상태에 따라서 각각의 파워를 할당하는 단계를 포함하는 것을 특징으로 한다.

직교주파수, OFDMA, 부채널, 파워

Description

직교주파수 분할 다중 접속 시스템의 비용함수 기반 적응형 자원 할당 방법{Method of Cost-based adaptive resource allocation in OFDMA systems}

도 1은 직교 주파수 분할 다중 접속 (OFDMA) 시스템의 구조도.

도 2는 채널 품질에 따른 서로 다른 파워량을 할당하는 워터-필링(Water-filling) 기법의 개념도.

도 3은 서비스 품질을 서로 다른 보장 수준으로 고려하였을 때와 고려하지 않았을 때의 각 부채널의 데이터 처리율.

도 4는 두 개의 지연 민감 실시간 트래픽의 서비스 품질을 각각 두 개의 보장 수준 (0.01, 0.03)으로 설정 하였을때 최대 허용 지연을 초과할 확률.

도 5는 각 지연 민감 실시간 트래픽의 서비스 품질을 각각 두 개의 보장 수준 (0.01, 0.03)으로 설정 하였을때 평균 지연 시간.

도 6은 각 데이터 전송률 민감 트래픽의 목표량과 제안된 자원 할당 기법으로 얻은 결과의 비교.

본 발명은 무선 통신 시스템의 매체 접근 제어 및 물리 계층을 포함하는 하위 계층에서 서비스 품질을 보장하기 위한 기법에 관한 연구로, 더욱 상세하게는 직교 주파수 분할 다중 접속 시스템의 하위 계층에서 각 사용자의 서비스 품질과 채널 품질을 동시에 반영하는 비용 함수를 사용하여 부채널을 할당하는 방법과 이를 이용하여 시스템에서 효율적으로 구현하기 위한 방법에 관한 것이다.

직교 주파수 분할 다중(OFDM) 방식은 무선 채널의 다중 경로에서 생기는 열화를 극복할 수 있으며 이로 인해 광대역 고속 통신 시스템에 적합한 특성을 가짐으로써 차세대 무선 네트워크의 물리계층으로 각광 받아 왔다. 직교 주파수 분할 다중(OFDM) 방식은, 무선에서는 단일 사용자 환경의 전송 기법으로 고려 되어왔으나 휴대 인터넷이나 차세대 이동 통신 시스템 등의 차세대 시스템에서 다중 사용자 환경에 대해 다양하게 연구되어 왔으며, 직교 주파수 분할 다중 접속(OFDMA) 시스템으로써 직교 주파수 분할 다중(OFDM) 방식의 장점을 가지면서 다중 사용자 환경을 고려하게 되었다. 이로써, 직교 주파수 분할 다중 접속(OFDMA) 시스템은 다수의 사용자가 다중 경로 무선 채널 환경에서 고속의 전송 속도를 보장할 수 있으며, 기존의 직교 주파수 분할 다중(OFDM) 방식에서 연구되었던 채널 상태 및 전송 가능한 파워 등에 기반한 적응형 변조 및 코딩 (AMC)을 사용 할 수 있게 되었으며 이는 전송 가능한 데이터 처리율을 높이고 데이터 전송 속도에 기반한 서비스 품질을 높이는 데 기여했다. 일반적으로, 직교 주파수 분할 다중 접속 시스템의 할당 가능한 하위 계층의 자원은 주파수 분할된 "부채널"과 각 부채널에 할당되는 "파워"이며, "부채널"은 단수 또는 복수개의 부 반송파로 구성되어 있으며 "파워"는 정해진 부채널에 파워를 할당함으로 인해서 생기는 데이터의 할당을 포함하여 정의된다.

하지만, [표 1]에서 볼 수 있듯이 직교 주파수 분할 다중 접속 시스템의 대표적인 종래 기술은 수학적 최적화 기법을 이용하여 문제를 해결함으로써, 목표로 하는 서비스 품질의 대상은 전송 속도만 고려되었으며 전송 속도를 보장함에 있어서도 다양한 종류의 전송속도 제한을 유연하게 지원할 수 없으며 최적화 해를 구하는 과정의 계산량도 부채널의 수에 따라서 기하 급수적으로 증가하게 된다.

따라서, 직교 주파수 분할 다중 접속 시스템을 이용하여 다수 사용자에게 그들이 필요로 하는 지연 민감, 전송 속도 민감, 최대 노력(best-effort: BE) 등 다양한 서비스 품질을 시스템 구현 가능한 방법으로 제공하기 위해서는 다양한 서비스 품질에 대해서 적은 계산량으로 유연하게 대처하면서 시스템 전체 전송 처리율을 일정 수준 이상으로 유지할 수 있는 방법이 필요하다.

	①	②	③	④
제안자	C.Y. Wong et al.	W. Rhee et al.	J. Jang et al.	Z. Shen et al.
목표	시스템 전체 전송 속도를 일정하게 유지하면서 시스템 사용 파워의 최소화	각 사용자의 최저 전송속도를 만족시키면서 전체 전송 처리율 최대화	총 전송 처리율 (각 사용자 용량의 합)의 최대화	각 사용자의 전송 속도 비례를 만족하면서 전체 전송 처리율 최대화
해결방안	최적화 부채널 할당	최적화 부채널 할당	최적화 부채널 할당	최적화 파워 할당

본 발명의 목적은 상기와 같은 문제점을 해결하기 위하여 안출된 것으로써, 종래 기술이 가지고 있는 전송 속도에 관한 단일 서비스 품질만을 제공하는 한계와 복잡한 최적화 과정을 극복하여, 다수 사용자에게 지연민감, 전송속도 민감, 최대 노력 서비스 등의 다양한 서비스 품질을 손쉽게 제공하는 데 있다.

본 발명의 직교주파수 분할 다중 접속 시스템의 비용함수 기반 적응형 자원할당방법은 a) 비용함수를 이용하여 각각의 사용자가 전송할 하위패킷을 정렬하고, 상기 정렬된 하위패킷을 각각의 부채널에 할당하는 단계; 및 b) 상기 부채널의 상태에 따라서 각각의 파워를 할당하는 단계를 포함한다.

본 발명에서 상기 단계 a)는 a1) 모든 사용자에 대하여 사용자 k의 부채널 n에 대한 채널품질을 갱신하고, 모든 사용자에 대하여 하위패킷 j의 서비스 품질 상태를 갱신하는 단계; a2) 모든 하위 패킷 j에 대하여, 비용함수를 이용하여 사용자 k가 소유하는 하위패킷 j의 부채널 n에 대한 비용을 산출하는 단계; a3) 상기 산출된 비용에 따라서 큰 순서로 정렬하는 단계; a4) 가장 큰 비용을 가지는 사용자 k의 하위패킷 j에게 부채널 n을 할당하고, 상기 할당된 부채널을 할당 가능한 부채널에서 제외하며, 상기 할당된 하위 패킷을 할당할 하위 패킷 리스트에서 제외하는 단계; 및 a5) 상기 할당 가능한 부채널과 하위패킷이 존재하지 않을 때까지 상기 단계 a4)를 되풀이하는 단계를 포함하는 것이 바람직하다.

본 발명에서 상기 비용함수(C_Q)는

로 정의되는 것이 바람직하다.

본 발명에서 상기 파워할당은 워터-필링(water-filling)기법에 의한 것이 바람직하다.

이하, 본 발명의 바람직한 실시예를 첨부한 도면을 참조하여 설명하기로 한다. 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 공지 기능 및 구성에 대한 상세한 설명은 생략하며, 사용하는 용어 및 기호는 다음과 같이 정의한다.

* 하위계층: 매체 접근 제어 계층 및 물리 계층

* 부채널 (Subchannel): 직교 주파수 분할 다중 접속 시스템의 단수 또는 복수개의 반송파로 이루어진 부 반송파 집합

* 파워: 각 부채널에 할당되는 파워로 할당된 파워는 변조 방식에 따른 전송 데이터 량으로 환산될 수 있으며, 부채널 n에 할당되는 파워를 P_n으로 표현

* 비용함수 (C_Q): 고려하는 서비스 품질이나 채널 품질에 따른 비용을 수치로 나타내는 함수로써 수학식 1과 같이 정의되며, 수치의 값이 높을수록 높은 우선순위를 가짐을 의미

* 비용 (Cost): 비용 함수를 통해서 산출된 수치로써 cos t_j _(k),n는 하위 패킷 j(사용자 k의 패킷)가 부채널 n에 대해서 가지는 비용을 나타냄

* 지연 민감 (Delay-sensitive) 서비스: 패킷이 발생되어 목적지에 송신되는 데 까지 걸리는 지연시간에 대한 제한이 있는 서비스

* 전송 속도 민감 (Data rate-sensitive) 서비스: 패킷의 평균 전송량에 일정 제한이 있는 서비스

* 최대 노력 (Best-effort) 서비스: 서비스 품질을 보장해야 하는 패킷에 먼저 자원을 할당하고 남은 자원을 통해서 제공되는 서비스로써 서비스 품질을 보장 받을 수 없는 서비스

* N: 직교 주파수 분할 다중 접속 시스템의 부채널 수

* K: 하나의 직교 주파수 분할 다중 접속 시스템 네트워크에 존재하는 전체 사용자 수

* 할당 단위: 하나의 부채널을 통해서 전송 가능한 최소 단위의 데이터 량

* 하위 패킷: 상위 계층에서 발생한 패킷이 하위 계층에서 할당 단위로 쪼개어져 상위 계층에서 부여된 서비스 품질을 상속받은 하나의 할당 단위 패킷

* 필요 서비스 품질: 상위 계층에서 패킷이 처음 발생될 때 부여받은 서비스 품질로써, 시스템에 의해서 제공되어야 하는 서비스 품질

* 서비스 품질 상태 (QS: Quality-of-service Status): 발생된 패킷이 제공받은 서비스나 지연된 시간 등 변화된 환경을 고려하여 특정 시점에서 평가된 상태로 qs_j는 하위패킷 j의 서비스 품질 상태를 나타냄

* 부채널 품질 (CS: Channel Status): 특정 시점에서 평가된 부채널의 상태 로써 크기가 클수록 같은 데이터를 적은 에너지로 전송할 수 있음을 의미하고, cs_n는 부채널의 채널 품질을 cs_k,n은 사용자 k에 대한 부채널 n의 채널 품질을 의미

* 프레임: 직교 주파수 분할 다중 접속 시스템의 물리계층 전송 심볼

* 프레임 주기: 전송 심볼이 반복되는 주기로써, 매번 자원 (부채널, 파워) 할당을 실시

도 1은 본 발명의 일 실시예에 따른 직교 주파수 분할 다중 접속 시스템의 하향링크 전체를 나타낸 블록도이다.

도 1을 참조하면, 기지국 송신기에서는 각 사용자에게 전송되어질 패킷의 서비스 품질 상태(QS)와 미리 확보된 각 사용자에 따른 부채널 품질(CS)을 고려하여, '부채널 및 파워 할당 기법'을 통해서 각 부채널에 적절한 하위 패킷이 다중화 되어 전송된다. 각 사용자는 직교 주파수 분할 다중 시스템을 통하여 전송된 프레임을 복조하고 본인의 정보를 다시 복조 해낸다.

본 발명에서 가정한 시스템 모델을 다음과 같다. 하나의 기지국에 접속한 총 사용자 수는 k이며 각 사용자는 전송할 하위 패킷을 항상 가지고 있고, 직교 주파수 분할 다중 접속 시스템의 총 부채널의 수는 n개로 가정한다.

본 발명은 도 1에 도시된 바와 같이 부채널 및 파워할당 과정을 두 개의 분리된 과정으로 진행한다. 이는 지연 민감 서비스 등의 수치화가 어려운 서비스나 다수의 서로 다른 특성을 가진 서비스 들이 동시에 존재할 때, 매번 수학적 최적화 가정을 통해서 계산할 경우 생기는 복잡한 계산량으로 인한 구현 불가능성을 낮추는 데 크게 도움이 된다.

먼저, 부채널 할당 과정에서는 각 사용자의 하위 패킷의 서비스 품질 상태 (qs_j)와 부채널 품질(cs_k,n)을 반영하는 수식(1)의 비용함수(C_Q)를 이용하여 큰 순서로 정렬하여 최대 크기의 비용을 가지는 하위 패킷 j(사용자 k의 하위패킷)부터 그 비용 cos t_j _(k),n의 해당 부채널을 할당한다.

여기서 f(·)는 함수를 의미하고 C_Q는 최소한 상기 수학식 1과 같이 서비스 품질 상태 (qs_j)와 부채널 품질 (cs_k,n)의 두 가지 파라미터를 포함해야 한다.

하나의 하위패킷이 특정 부채널에 할당되면 그 하위 패킷과 부채널은 할당과정에서 제외되고, 남은 하위 패킷의 비용들로 할당과정은 반복되게 된다. 위의 과정을 통하여 각 사용자가 가지는 비용의 크기 순서대로 부채널을 할당받아서 모든 부채널이 할당된 후 마치게 된다.

본 발명에서 제안된 부채널 할당 기법은 다음과 같이 정리될 수 있고, 매 프레임마다 반복된다.

우선 사전준비 단계로써, 모든 사용자에 대하여, 사용자 k의 부채널 n의 채널품질 (cs_k,n)을 갱신하고, 모든 사용자에 대하여, 하위패킷 j의 서비스 품질 상태 (qs_j)를 갱신한다.

다음은 비용산출단계로써, 모든 하위 패킷 j에 대하여, 하위 패킷 j(사용자 k소유)의 부채널 n에 대한 비용, cos t_j _(k),n 를 상기 수학식 1의 비용함수를 이용하여 산출한다.

이 후, 산출된 비용에 따라서 큰 순서로 정렬하고, 가장 큰 비용 cos t_j _(k),n을 가지는 하위 패킷 j(사용자 k)에게 부채널 n을 할당하며, 할당된 부채널을 할당 가능한 부채널에서 제외하고, 할당된 하위 패킷을 할당할 하위 패킷 리스트에서 제외하며, 할당 가능한 부채널과 하위패킷이 있는 동안 반복하여 모든 부채널이 할당되는 순간까지 반복한다.

부채널 할당에 이은 파워 할당 기법에서는 주어진 부채널 할당과 할당 가능한 총 파워량의 제한 조건에서 전체 시스템의 전송 속도를 최대화 할 수 있도록 도 2와 같이 워터-필링(Water-filling) 방식에 의해서 파워를 할당한다. 부채널 n에 할당된 파워는 p_n으로 표시되고, 이는 파워 할당 레벨 (Water-filling level)과 Γ/cs_n와의 차이가 할당되는 파워를 나타낸다. 여기서 cs_n은 부채널에 대한 채널 품질 상태, Γ는 변조 방식 및 전송 제한 (목표 Bit error rate 등)에 따른 상수이며, 채널 상태가 좋을수록 큰 값을 가지므로 채널 상태가 좋을수록 많은 파워가 할당된다.

이하, 제안된 기법의 예로서 다음과 같이 지연 민감, 전송 속도 민감, 최대 노력 서비스 등 크게 세가지의 서비스 군이 있는 경우를 고려하여, 비용 함수를 이용한 부채널 할당과 그 구현 방법의 성능을 살펴본다.

< 지원서비스군 >

지연 민감, 전송 속도 민감, 최대 노력 서비스의 세 개의 군으로써 각 지연 민감과 전송속도 민감 서비스의 경우에는 서로 다른 지연 제한과 전송속도 제한을 가질 수 있다. 성능 평가에 사용된 네트워크 트래픽 환경은 표 2에서 보여진다. 지연 민감 서비스와 전송 속도 민감 서비스는 다음과 같은 서비스 품질의 제한으로 정의 된다. 지연 민감 서비스의 제한 조건은 다음의 수학식 2와 같이 정의된다.

여기에서, W_j는 하위패킷 j의 지연, T_j는 최대 허용 지연, σ_j는 지연초과 허용확률이다. 따라서, 패킷 j의 지연이 정해진 최대 허용지연을 초과할 확률을 지연초과 허용 확률 σ_j이하로 유지해야 한다. 본 예에서는 σ_j를 0.03과 0.01의 두가지 상황을 고려하고 결과도에서 다룬다.

전송 속도 민감 서비스의 제한 조건은 수학식 3과 같이 정의된다.

R_j≥dr_j

여기서, R_j는 하위 패킷 _j의 전송속도, dr_j는 목표 전송 속도이다. 따라서, 패킷 j의 전송속도가 정해진 목표 전송 속도 dr_j이상 되어야 한다.

서비스 군	지연 민감		전송 속도 민감			최대 노력
발생 트래픽	64	128	64	128	384	64
서비스 목표	지연9ms	지연4.5ms	전송속도 64	전송속도 128	전송속도 384	없음
사용자 수	12	20	12	8	4	8

< 비용함수 >

예에서는 3세대 이동 통신의 무선 스케쥴링에 이용되었던 M-LWDF 방식함수를 이용한다. 본 비용함수는 수학식 4와 같이 주어진다.

,

로 정의된다. 여기서,

는 평균 품질 상태이며 β는 임의의 상수이다. 또한,

는 현재 채널의 품질상태로써, k의 부채널 n에 대한 채널 품질 상태를 나타낸다.

수학식 4에서 보여지는 지연 W_j는 지연시간이지만, 전송속도 민감 서비스도 남은 하위패킷의 양과 전송해야할 패킷의 비율을 이용하여 손쉽게 지연 시간으로 표현 가능하다.

<직교 주파수 분할 다중 접속 시스템 하위 계층 모델과 무선 채널 모델>

본 예에서는 휴대 인터넷의 유력한 하위 계층 모델인 IEEE 802.16a 의 매체접근제어 및 물리계층을 직교 주파수 분할 다중 접속 시스템의 예제 모델로 사용한다.

* 반송파 주파수: 2.3

* 전체 반송파 개수: 2048

* 전체 부채널 개수 (N): 8

* 변조 방식: QPSK, 16QAM, 64QAM

* 무선 채널 모델: Modified SUI model

* 목표 Bit error rate: 10-6

* 파워 제한: 평균

< 성능평가결과 >

도 3은 서비스 품질을 고려하지 않은 상태에서 각 부채널에서 최고 좋은 채널 성능을 보이는 사용자에게 파워만을 할당하여 얻은 전송 처리율 결과 (1Mbps)와 서비스 품질을 두 가지 확률 (δ_j=0.03, 0.01)로 고려하였을 때의 전송 처리율을 비교하였다. 사용자의 서비스 품질을 전혀 고려하지 않았을 때에 비해서 약 27% 정도 의 전송 처리율이 감소함을 볼 수 있으나, 이는 일반적으로 서비스 품질을 고려할 때 발생되는 희생이다.

도 4에서는 두 가지 지연 민감 서비스(64Kbps, 128Kbps) 최대 허용 지연 시간 초과 확률이 미리 설정해 놓은 초과 허용 확률(δ_j=0.03, 0.01)을 만족하는 것을 알 수 있다. 또한, 도 5에서는 사용자에 따른 평균 지연 시간이 최대 허용 지연 시간을 만족하고 고르게 분포함을 알 수 있다.

도 6에서는 연속된 시물레이션에서 반복 횟수에 따라서 설정된 목표 전송 속도(dr_j)에 따른 실제 전송 속도의 변화를 살펴 본 것으로, 시도 횟수에 상관없이 설정된 목표 전송 속도는 유지됨을 알 수 있다.

상기와 같이, 본 발명의 바람직한 실시예를 참조하여 설명하였지만 해당 기술 분야의 숙련된 당업자라면 하기의 특허청구범위에 기재된 본 발명의 사상 및 영역으로부터 벗어나지 않는 범위 내에서 본 발명을 다양하게 수정 및 변경시킬 수 있음을 이해할 수 있을 것이다.

상술한 바와 같이 본 발명에 의하면, 지금까지 보장하기 어려웠던 지연 민감 서비스 등의 서비스와, 다양한 서비스가 동시에 존재하는 상황에서 수학적으로 어려웠던 접근을 비용함수를 사용하여 부채널을 할당함으로써, 비교적 간단하게 서비 스 품질을 만족시킬 수 있다.

또한, 직교 주파수 분할 다중 접속 시스템이 휴대 인터넷이나 차세대 이동 통신 시스템 등의 주요한 기반 기술로 고려되고 있는 시점에서, 그 중요성은 증폭 된다.

Claims

직교주파수 분할 다중 접속 시스템의 비용함수 기반 적응형 자원할당방법에 있어서,

a) 비용함수를 이용하여 각각의 사용자가 전송할 하위패킷을 정렬하고, 상기 정렬된 하위패킷을 각각의 부채널에 할당하는 단계; 및

b) 상기 부채널의 상태에 따라서 각각의 파워를 할당하는 단계를 포함하는 것을 특징으로 하는 직교주파수 분할 다중 접속 시스템의 비용함수 기반 적응형 자원할당방법.
제 1항에 있어서, 상기 단계 a)는

a1) 모든 사용자에 대하여 사용자 k의 부채널 n에 대한 채널품질을 갱신하고, 모든 사용자에 대하여 하위패킷 j의 서비스 품질 상태를 갱신하는 단계;

a2) 모든 하위 패킷 j에 대하여, 비용함수를 이용하여 사용자 k가 소유하는 하위패킷 j의 부채널 n에 대한 비용을 산출하는 단계;

a3) 상기 산출된 비용에 따라서 큰 순서로 정렬하는 단계;

a4) 가장 큰 비용을 가지는 사용자 k의 하위패킷 j에게 부채널 n을 할당하고, 상기 할당된 부채널을 할당 가능한 부채널에서 제외하며, 상기 할당된 하위 패킷을 할당할 하위 패킷 리스트에서 제외하는 단계; 및

a5) 상기 할당 가능한 부채널과 하위패킷이 존재하지 않을 때까지 상기 단계 a4)를 되풀이하는 단계를 포함하는 것을 특징으로 하는 직교주파수 분할 다중 접속 시스템의 비용함수 기반 적응형 자원할당방법.
제 1항에 있어서, 상기 비용함수(C_Q)는

로 정의되는 것을 특징으로 하는 직교주파수 분할 다중 접속 시스템의 비용함수 기반 적응형 자원할당방법.

단, 상기 cs_k,n은 부채널의 품질을 나타내고, 상기 qs_j는 서비스의 품질상태를 나타낸다.
제 1항에 있어서, 상기 파워할당은 워터-필링(water-filling)기법에 의한 것을 특징으로 하는 직교주파수 분할 다중 접속 시스템의 비용함수 기반 적응형 자원할당방법.