KR100828478B1

KR100828478B1 - 멀티 캐리어 통신 시스템에서 저 복잡도 동적 채널 할당장치 및 방법

Info

Publication number: KR100828478B1
Application number: KR1020050114055A
Authority: KR
Inventors: 이종혁; 권종형; 조면균; 서우현; 홍대식
Original assignee: 삼성전자주식회사; 연세대학교 산학협력단
Priority date: 2005-11-28
Filing date: 2005-11-28
Publication date: 2008-05-13
Anticipated expiration: 2025-11-28
Also published as: KR20070055728A; US20070121746A1

Abstract

본 발명은 멀티 캐리어 통신 시스템에서 저 복잡도 동적 채널 할당 장치 및 방법에 관한 것으로서, 전체 사용자들에게 부반송파(들)를 초기 할당한 후, 모든 경우의 수로 상기 전체 사용자 중 두 명의 사용자를 선택하는 과정과, 상기 선택된 두 명의 사용자에게 각각 초기 할당된 부반송파(들)를 서로 교환하여 재할당함으로써 발생할 수 있는 전력 감소 이득을 상기 부반송파별로 계산하는 과정과, 상기 선택된 사용자별로 초기 할당된 부반송파들의 전력 감소 이득을 정렬하고, 상기 두 사용자에 대해 최대 전력 감소 이득을 가지는 부반송파 쌍을 선택하는 과정과, 상기 선택된 부반송파 쌍을 서로 교환하여 상기 두 사용자에게 재할당하는 과정을 포함하여, 제시된 기준에 따라 재 할당회수를 제한함으로써 기존 할당 방식과 비슷한 성능을 유지하면서도 알고리즘 자체의 복잡도를 크게 줄일 수 있는 이점이 있다.

OFDMA, 동적 채널 할당, Wong의 알고리즘, 채널 할당 알고리즘

Description

멀티 캐리어 통신 시스템에서 저 복잡도 동적 채널 할당 장치 및 방법{APPARATUS AND METHOD FOR ALLOCATING DYNAMIC CHANNEL WITH LOW COMPLEXITY IN MULTI-CARRIER COMMUNICATION SYSTEM}

도 1은 종래 기술에 따른 Wong의 알고리즘의 초기 할당 과정을 도시한 예시도,

도 2는 종래 기술에 따른 Wong의 알고리즘의 교환 과정을 도시한 예시도,

도 3은 본 발명에 따른 멀티 캐리어 통신 시스템의 송신기 구조를 도시한 도면,

도 4는 본 발명의 실시 예에 따른 멀티 캐리어 통신 시스템에서 저 복잡도 동적 채널 할당 방법의 절차를 도시한 도면,

도 5는 본 발명의 실시 예에 따른 멀티 캐리어 통신 시스템에서 저 복잡도 동적 채널 할당의 초기 할당 과정을 도시한 예시도,

도 6은 본 발명의 실시 예에 따른 멀티 캐리어 통신 시스템에서 저 복잡도 동적 채널 할당의 교환 과정을 도시한 예시도, 및

도 7은 본 발명에 따른 알고리즘과 종래 기술에 따른 알고리즘의 계산적 복잡도를 비교한 도면.

본 발명은 멀티 캐리어 통신 시스템에 관한 것으로, 특히, 저 복잡도 동적 채널 할당 장치 및 방법에 관한 것이다.

이동 통신 시스템들에서 무선 채널로 신호를 전송하는 경우, 전송된 신호는 송신기와 수신기 사이에 존재하는 다양한 장애물들에 의해 다중경로 간섭을 받는다. 상기 다중경로가 존재하는 무선 채널은 채널의 최대 지연 확산과 신호의 전송 주기로 특성을 규정짓는다. 상기 최대 지연 확산보다 신호의 전송 주기가 긴 경우에는 연속된 신호 사이에 간섭이 발생하지 않으며, 채널의 주파수 특성은 비선택적 페이딩(frequency nonselective fading)으로 주어진다. 그러나, 심벌(symbol) 주기가 짧은 고속 데이터 전송시에 단일 반송파(single carrier)방식을 사용하게 되면, 심벌간 간섭(inter-symbol interference)이 심해지기 때문에 왜곡이 증가하게 되고, 수신단의 등화기(equalizer)의 복잡도도 함께 증가된다. 따라서, 상기 단일 반송파 전송방식에서 등화 문제를 해결하기 위한 대안으로 직교 주파수 분할 다중(Orthogonal Frequency Division Multiplexing; 이하 'OFDM'이라 칭함) 방식을 사용하는 시스템이 제안되었다.

상기 OFDM 방식은 멀티-캐리어(Multi-Carrier)를 사용하여 데이터를 전송하는 방식으로서, 직렬로 입력되는 심벌(Symbol)열을 병렬 변환한 후 이들 각각을 상 호 직교성을 갖는 다수의 부반송파(sub-carrier)들, 즉 다수의 부반송파 채널(sub-carrier channel)들로 변조하여 전송하는 멀티캐리어 변조(MCM : Multi Carrier Modulation) 방식의 일종이다.

상기 OFDM 방식은 상호 직교성을 지닌 여러 개의 반송파를 사용하므로 주파수 이용 효율이 높고, 상기 IFFT 및 FFT를 사용하므로 고속데이터 처리에 용이하며, 'Cyclic Prefix'를 사용하여 다중경로 페이딩에 견고함을 보인다. 또한, 다중 사용자와 다중 안테나(Multiple-Input Multiple-Output; 이하 'MIMO'라 칭함) 시스템으로의 확장이 용이하여 최근 활발한 연구 개발이 진행되고 있으며, 4세대 이동통신 및 차세대 통신방식의 대표적인 방식으로 고려되고 있다.

한편, 다중 사용자를 고려한 OFDM 방식인 멀티 캐리어 통신(Orthogonal Frequency Division Multiple Access; 이하 'OFDMA'라 칭함) 시스템에서는 단일 사용자를 고려한 상기 OFDM 방식과 달리 각 사용자마다 원하는 전송 비트율과 송신 파워를 고려함과 동시에 부반송파가 겹치지 않게 최적으로 할당해야 한다. 이에 따라 다중 사용자를 위한 OFDM 방식, 즉 OFDMA 방식에서 여러 부반송파 할당 기법이 제안되었다.

한편, 상기 OFDMA의 부최적화(suboptimal) 채널 할당 알고리즘 중 가장 널리 알려진 알고리즘으로 Wong의 부반송파 할당 알고리즘(Wong's Sub-carrier Allocation algorithm : 이하 'WSA'라 칭함)이 있다. 상기 WSA의 프로세스는 초기 할당(initial allocation)과 반복 교환(iterative swapping)의 두 단계로 구성된다.

상기 WSA의 초기 할당 과정을 살펴보면, 상기 초기 할당(initial allocation)을 위해 기지국의 부반송파 할당부는, 도 1과 같이, 각 사용자에 대해 부반송파 채널 이득(sub-carrier channel gain)을 내림차순(descending)으로 정렬(ordering)하고, 각 사용자에게 라운드 로빈 방식으로 채널 할당 기회를 준다. 상기 라운드 로빈(round-robin) 방식은 그룹 내에 있는 모든 요소들을 합리적인 순서에 입각하여 뽑는 방법으로서, 대개 리스트의 맨 위에서 아래로 가며 하나씩 뽑고, 끝나면 다시 맨 위로 돌아가는 식으로 진행된다. 다시 말해, 각 사용자들은 상기 정렬된 리스트에 기초하여 기 선택하지 않은 채널 중 가장 상위 순서의 채널, 즉 가장 채널 이득이 좋은 부반송파를 자신의 채널 할당 기회에 선택한다. 만약, 상기 선택한 채널을 다른 사용자가 먼저 선택했다면, 상기 사용자는 다음 자신의 채널 할당 기회에 그 다음 순위의 채널을 선택할 수 있다. 여기서, 사용자는 채널 이득이 좋은 부반송파를 선택하여야 작은 전송 파워로 자신이 원하는 데이터를 전송할 수 있으며, 이 경우, 시스템은 전력에 여유가 생기게 되어 다른 사용자를 더 서비스할 수 있다. 반대의 경우, 사용자가 채널 이득이 나쁜 부반송파를 선택하면, 자신이 원하는 데이터를 전송하기 위해 많은 전송 파워가 들게 되므로 다른 사용자를 서비스할 수 없다.

다음으로 도 2를 예로 들어 상기 반복 교환 과정을 살펴보면, 2명의 사용자에게 6개의 부반송파를 할당하는 부반송파 할당부에서, 상기 초기 할당(initial allocation) 과정을 통해 사용자 1에게는 부반송파 1, 2, 6을 할당하고, 사용자 2에게는 부반송파 3, 4, 5를 할당하였다고 가정한다. 이후, 상기 부반송파 할당부는 상기 사용자 1에게 할당된 부반송파 6(203)과 상기 사용자 2에게 할당된 부반송파 3(201)을 교환한다. 이 경우, 전력 감소 이득(power reduction gain) P_1,2는 △P_3,1,2 + △P_6,2,1로 계산할 수 있다. 여기서, 상기 △P_3,1,2 는 초기 할당 과정에서 사용자 2에게 할당되었던 부반송파 3(201)을 사용자 1에게 할당함으로써 발생하게 되는 전력 감소 이득을 의미하고, 상기 △P_6,2,1는 사용자 1에게 할당되었던 부반송파 6을 사용자 2에게 할당함으로써 발생하게 되는 전력 감소 이득을 의미한다. 여기서, 상기 전력 감소 이득이 두 사용자의 특정 부반송파 쌍(subcarrier pair)에서 발생한다면, 상기 부반송파 할당부는 상기 두 부반송파를 서로 바꾸어 재할당한다.

상기 WSA 알고리즘은 최적화 채널 할당 알고리즘(optimal algorithm)에 비해 단순함에도 불구하고, 모든 사용자들에 대해 데이터 전송률(data rate)과 채널이득(channel gain) 및 다중 사용자 인덱스(multiuser index)를 계산해야하는 상기 최적화 채널 할당 알고리즘과 비슷한 성능을 가짐으로써, 상기 부최적화 알고리즘 중 최고의 성능을 가진다. 하지만, 상기 교환 과정에서 비효율적인 교환으로 인해 상기 복잡도 면에서는 취약한 문제점이 있다.

여기서, 상기 WSA의 복잡도를 계산하면 다음과 같다.

우선, 상기 초기 할당(initial allocation) 과정에서 발생하는 복잡도는 하기 <수학식 1>과 같이 나타낼 수 있다.

여기서, 상기 O는 빅오 표기법(Big O notation)을 나타내고, 상기 K는 사용자의 수를 나타내며, 상기 N은 부반송파의 수를 나타낸다. 즉, 상기 <수학식 1>은 상기 초기 할당 과정에서 전체 K명의 사용자가 전체 N개의 부반송파를 순서대로 정렬(ordering)함으로써 발생하게 되는 복잡도이다.

또한, 상기 교환(swapping) 과정에서 발생하는 복잡도는 하기 <수학식 2>와 같이 나타낼 수 있다.

여기서, 상기 _kC₂는 K 명의 사용자 중 2명의 사용자를 선택하기 위해 발생하는 복잡도이다. 또한, 상기 (N/K)·(N/K)는 2명의 서로 다른 사용자들로부터 부반송파의 최대 전력 감소 쌍(maximum power reduction pair)을 찾는 과정에서 발생하는 복잡도이며, 상기 N/K는 시스템에 N개의 부반송파와 K명의 사용자가 있을 시,각 사용자에게 할당되는 부반송파의 평균 수를 의미한다.

따라서, 상기 WSA의 총 복잡도(Total Complexity)는 하기 <수학식 3>과 같이 나타낼 수 있다.

여기서, 상기 a는 상기 교환(swapping)의 반복(iteration) 수를 의미한다. 상기 WSA의 경우, 상기 전력 감소 이득(power reduction gain)이 발생하지 않을 때까지 상기 교환을 반복한다.

이와 같이, 상기 WSA는 상기 초기 할당(initial allocation)과 반복 교환(iterative swapping)을 통해 전송 전력(transmit power)을 최소화하는 알고리즘이다. 상기 알고리즘에서 상기 초기 할당(initial allocation)의 목적은 각 사용자에게 요구되는 대역폭을 할당하고, 그리디 방법(greedy method)을 사용하여 다중 사용자 다이버시티(Multiuser diversity : 이하 ‘MUDiv’라 칭함) 이득을 획득하는 것이다. 하지만, 상기 MUDiv 이득은 상기 반복 교환(iterative swapping)에 의한 만큼 상기 초기 할당(initial allocation) 과정에 의해서도 생성되기 때문에 같은 과정이 두 스텝 모두에서 반복된다. 또한, 상기 WSA는 전력 감소 이득이 더 이상 발생하지 않을 때까지 상기 반복 과정을 계속 시도하기 때문에 상기 알고리즘의 계산적 복잡도는 상기 <수학식 3>과 같이 높은 문제점이 있다.

따라서, 본 발명의 목적은 멀티 캐리어 통신 시스템에서 저 복잡도 동적 채널 할당 장치 및 방법을 제공함에 있다.

본 발명의 또 다른 목적은 멀티 캐리어 통신 시스템에서 랜덤 초기 할당과 제한 요소를 적용한 반복 교환 과정을 통해 알고리즘의 복잡도를 최소화함으로써 최소 전송 파워를 획득할 수 있는 동적 채널 할당 장치 및 방법을 제공함에 있다.

상기 목적을 달성하기 위해 본 발명의 실시 예에 따르면, 멀티 캐리어 통신 시스템에서 동적 채널 할당 방법은, 전체 사용자들에게 부반송파(들)를 초기 할당한 후, 모든 경우의 수로 상기 전체 사용자 중 두 명의 사용자를 선택하는 과정과, 상기 선택된 두 명의 사용자에게 각각 초기 할당된 부반송파(들)를 서로 교환하여 재할당함으로써 발생할 수 있는 전력 감소 이득을 상기 부반송파별로 계산하는 과정과, 상기 선택된 사용자별로 초기 할당된 부반송파들의 전력 감소 이득을 정렬하고, 상기 두 사용자에 대해 최대 전력 감소 이득을 가지는 부반송파 쌍을 선택하는 과정과, 상기 선택된 부반송파 쌍을 서로 교환하여 상기 두 사용자에게 재할당하는 과정을 포함하는 것을 특징으로 한다.

상기 목적을 달성하기 위해 본 발명의 실시 예에 따르면, 멀티 캐리어 통신 시스템에서 동적 채널 할당 장치는, 전체 사용자들에게 부반송파가 초기 할당되었을 시, 모든 경우의 수로 상기 전체 사용자 중 두 명의 사용자를 선택하고, 상기 선택된 두 명의 사용자에게 각각 초기 할당된 부반송파(들)를 서로 교환하여 재할당함으로써 발생할 수 있는 전력 감소 이득을 상기 부반송파별로 계산한 후, 상기 선택된 사용자별로 초기 할당된 부반송파들의 전력 감소 이득을 정렬하고, 상기 두 사용자에 대해 최대 전력 감소 이득을 가지는 부반송파 쌍을 선택 및 서로 교환하여 상기 두 사용자에게 재할당하는 부반송파 할당부와, 사용자의 복소 신호를 해당 사용자에게 재할당된 부반송파에 매핑하는 부반송파 매핑부를 포함하는 것을 특징으로 한다.
상기 목적을 달성하기 위해 본 발명의 실시 예에 따르면, 멀티 캐리어 통신 시스템에서 동적 채널 할당 방법은, 부반송파(들)가 할당된 전체 사용자 중 두 명의 사용자를 선택하는 과정과, 상기 두 사용자의 부반송파(들)를 서로 교환하여 재할당함으로써 발생할 수 있는 전력 감소 이득을 상기 부반송파별로 계산하는 과정과, 상기 두 사용자에 대해 최대 전력 감소 이득을 가지는 부반송파 쌍을 선택하는 과정을 포함하는 것을 특징으로 한다.
상기 목적을 달성하기 위해 본 발명의 실시 예에 따르면, 멀티 캐리어 통신 시스템에서 동적 채널 할당 장치는, 부반송파(들)가 할당된 전체 사용자 중 두 명의 사용자를 선택하는 수단과, 상기 두 사용자의 부반송파(들)를 서로 교환하여 재할당함으로써 발생할 수 있는 전력 감소 이득을 상기 부반송파별로 계산하는 수단과, 상기 두 사용자에 대해 최대 전력 감소 이득을 가지는 부반송파 쌍을 선택하는 수단을 포함하는 것을 특징으로 한다.

이하 본 발명의 바람직한 실시 예를 첨부된 도면의 참조와 함께 상세히 설명한다. 그리고, 본 발명을 설명함에 있어서, 관련된 공지기능 혹은 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단된 경우 그 상세한 설명은 생략한다.

이하, 본 발명은 멀티 캐리어 통신 시스템에서 저 복잡도 동적 채널 할당 장치 및 방법에 대해 설명한다.

도 3은 본 발명에 따른 멀티 캐리어 통신 시스템의 송신기 구조를 도시한 도면이다. 상기 멀티 캐리어 통신 시스템의 송신기는 부반송파 할당부(301), 부호화기(303), 부반송파 매핑부(305), IFFT기(307), 병/직렬 변환기(309), 보호 구간 삽입기(311), 디지털/아날로그(D/A) 변환기(313), RF 처리기(315)를 포함하여 구성된다.

상기 도 3을 참조하면, 상기 부반송파 할당부(301)는 물리 계층으로부터 수신한 각 사용자의 채널 정보를 기초로 본 발명에 따른 자원 할당 알고리즘을 이용하여 각 사용자에게 자원, 예를 들어, 부반송파를 할당한다. 또한, 상기 부반송파 할당부(301)는 상기 자원 할당 정보를 상기 부반송파 매핑부(305)로 전송하여 상기 자원 할당 정보에 따른 데이터 영역에 송신 데이터가 할당될 수 있도록 상기 부반송파 매핑부(305)를 제어하는 역할을 한다. 여기서, 상기 자원 할당 정보에 따른 데이터 영역은 각 사용자당 할당되는 부반송파 수로 정의되는 자원이다.

상기 부호화기(303)는 다수(예컨대, K개)의 사용자 단말기에 전송할 데이터들을 미리 설정되어 있는 설정 코딩(coding) 방식으로 부호화하고, 상기 부호화된 전송 데이터들을 상기 부반송파 매핑부(305)로 출력한다. 여기서, 상기 코딩 방식은 소정 코딩 레이트(coding rate)를 가지는 터보 코딩(turbo coding) 방식 혹은 컨벌루셔널 코딩(convolutional coding) 방식 등이 될 수 있다.

상기 부반송파 매핑부(305)는 상기 부호화기(303)로부터 입력되는 각 사용자별 상기 부호화된 전송 데이터들을 미리 설정되어 있는 설정 변조 방식에 신호점 사상하여 복소 신호를 생성한 후, 상기 생성한 복소 신호를 상기 부반송파 할당부(301)로부터 입력되는 부반송파 정보에 따라 다수(예컨대, N개)의 부반송파들에 매핑한다. 여기서, 상기 부반송파들에 매핑한다는 것은, 복소 신호들 각각을 IFFT기(307)의 해당 입력(부반송파 위치)들로 제공하는 것을 의미한다. 예를 들어, 상기 변조방식에는 1개의 비트(s=1)를 하나의 복소 신호에 사상하는 BPSK(Binary Phase Shift Keying), 2개의 비트(s=2)를 하나의 복소 신호에 사상하는 QPSK(Quadrature Phase Shift Keying), 3개의 비트(s=3)를 하나의 복소 신호에 사상하는 8QAM(8ary Quadrature Amplitude Modulation), 4개의 비트(s=4)를 하나의 복소 신호에 사상하는 16QAM 등이 있다.

상기 IFFT기(307)는 상기 부반송파 매핑부(305)에 의해 입력 포인트에 매핑된 신호를 N-포인트(N-point) 역 고속 푸리에 변환(IFFT)하여 상기 병/직렬 변환기(309)로 시간영역의 샘플 데이터를 출력한다.

상기 병/직렬 변환기(309)는 상기 IFFT기(307)로부터 입력되는 병렬 신호를 직렬 변환하여 상기 보호 구간 삽입기(311)로 출력한다. 상기 보호 구간 삽입기(311)는 상기 병/직렬 변환기(309)로부터 입력되는 신호에 보호 구간 신호를 삽입하여, 예를 들어, 샘플 데이터의 소정 뒷부분을 복사해서 상기 샘플데이터의 앞에 붙여 OFDM 심볼을 생성하고, 상기 생성된 OFDM 심볼을 상기 디지털/아날로그 변환기(313)로 출력한다.

상기 디지털/아날로그 변환기(313)는 상기 보호 구간 삽입기(311)로부터 입력되는 신호를 아날로그 변환하여 상기 RF 처리기(315)로 출력한다. 상기 RF 처리기(315)는 필터(filter)와 전처리기(front end unit) 등의 구성들을 포함하며, 상기 디지털/아날로그 변환기(313)로부터 입력되는 신호를 실제 에어(air)상에서 전송 가능하도록 RF 처리한 후 송신 안테나(Tx antenna)를 통해 에어(air)상으로 전송한다.

도 4는 본 발명의 실시 예에 따른 멀티 캐리어 통신 시스템에서 저 복잡도 동적 채널 할당 방법의 절차를 도시하고 있다.

상기 도 4를 참조하면, 기지국의 부반송파 할당부(301)는 401단계에서 전체 사용자들에게 전체 채널을 랜덤으로 초기 할당(initial allocation)한다. 여기서, 상기 랜덤 할당(Random Allocation)은 단지 각 사용자의 요구되는 대역폭(Bandwidth)을 만족시키기 위한 과정으로, 상기 채널을 랜덤으로 할당하기 때문에 복잡도가 발생하지 않는다. 도 5를 예로 들어 상기 랜덤 할당을 설명하면, 사용자 1과 2가 각각 3개의 부반송파를 요구하고, 사용자 3이 2개의 부반송파를 요구할 시, 시스템은 상기 사용자 1에게 부반송파 1(501), 2(503), 3(505)을 할당하고, 상기 사용자 2에게 부반송파 4(507), 5(509), 6(511)을 할당하며, 상기 사용자 3에게 나머지 부반송파 7(513), 8(515)을 할당할 수 있다.

이후, 상기 부반송파 할당부(301)는 403단계에서 두 명의 사용자 선택 수를 나타내는 인덱스 n을 1로 설정하고, 405단계로 진행하여 각 사용자에게 할당된 부반송파들 중 상호 교환을 통해 파워 감소 이득이 발생할 수 있는 부반송파 쌍을 서로 교환(swapping)하기 위한 두 명의 사용자를 선택한다.

이후, 상기 부반송파 할당부(301)는 407단계에서 상기 선택된 두 명의 사용자에게 할당된 부반송파들의 재할당으로 발생 가능한 부반송파별 전력 감소 이득(Power reduction gain)을 구한다. 다시 말해, 상기 초기 할당을 통해 두 사용자에게 할당되었던 부반송파를 서로 바꿔(swapping) 재할당함으로써 감소하게 되는 전송 전력(reduced transmit power)을 구한다. 도 6을 예로 들어 설명하면, 상기 부반송파 할당부는 상기 초기 할당(initial allocation)과정을 통해 사용자 k1에게 부반송파 b1과 b2를 할당하고, 사용자 k2에게 부반송파 b3과 b4를 할당한 후, 각 부반송파별로 전력 감소 이득을 구한다. 상기 부반송파 b1에 대한 전력 감소 이득 △P_{b1,(k1, k2)}는 상기 초기 할당(initial allocation)을 통해 사용자 k1에게 할당되었던 상기 부반송파 b1을 사용자 k1을 대신하여 사용자 k2에 할당함으로써 감소하게 되는 전송 전력(reduced transmit power)을 구하는 것이고, 다른 부반송파 b2, b3, b4에 대해서도 같은 방법으로 전력 감소 이득 △P_{b2,(k1, k2),} △P_{b3,(k2, k1),} △P_{b4,(k2, k1)}를 구할 수 있다.

이후, 상기 부반송파 할당부(301)는 409단계에서 상기 추정한 부반송파별 전력 감소 이득을 이용하여 각 사용자별 최대 전력 감소 이득(maximum power reduction gain)을 결정한다. 여기서, 상기 결정된 사용자별 상기 최대 전력 감소 이득은 최대 전력 감소 쌍(maximum power reduction pair)이 된다. 다시 말해, 사용자별로 각 사용자가 상기 초기 할당 과정에서 할당받은 부반송파들에 대한 상기 부반송파별 전력 감소 이득 중 가장 이득이 큰 부반송파를 검출하고, 상기 검출한 부반송파의 전력 감소 이득을 해당 사용자의 최대 전력 감소 이득으로 결정한다. 상기 도 6을 예를 들면, 사용자 k1의 최대 전력 감소 이득 △P_{k1, k2}는 상기 사용자 k1이 점유하고 있던 부반송파 b1, b2를 사용자 k2에게 할당함으로써 얻을 수 있는 전력 감소 이득 △P_b1,(k1,k2), △P_b2,(k1,k2) 중 가장 큰 전력 감소 이득이다. 같은 방법으로 사용자 k2의 최대 전력 감소 이득 △P_{k2, k1}도 결정할 수 있다.

이후, 상기 부반송파 할당부(301)는 411단계로 진행하여 상기 최대 전력 감소 쌍(maximum power reduction pair)으로 결정된 각 사용자의 부반송파를 서로 교환함으로써 재할당한다.

이후, 상기 부반송파 할당부(301)는 413단계에서 상기 n이 상기 두 명의 사용자를 선택하기 위한 모든 경우의 수보다 작은지 검사한다. 상기 n이 상기 두 명의 사용자를 선택하기 위한 모든 경우의 수보다 작을 시, 상기 부반송파 할당부(301)는 415단계로 진행하여 상기 n에 1을 더한 수로 상기 n을 갱신하고, 405단계로 돌아가 다른 경우의 두 명의 사용자를 선택한다. 예를 들어, 처음에 사용자 1과 2를 선택했다면, 그 다음의 선택에서는 사용자 2와 3을 선택할 수 있다.

상기 n이 상기 두 명의 사용자를 선택하기 위한 모든 경우의 수보다 작지 않을 시, 상기 부반송파 할당부(301)는 417단계로 진행하여 상기 결정한 최대 전력 감소 쌍들의 수(The number of maximum power reduction pair)에 대해 실제 재할당시 전력 감소 이득을 획득한 최대 전력 감소 쌍들의 수가 제한 요소(Limitation factor) β보다 작은지 검사한다. 기존의 WSA에서는 상기 최대 전력 감소 쌍이 발생하지 않을 때까지 상기 교환 과정을 반복(iteration)한다. 하지만, 본 발명에 따른 알고리즘은 상기 반복 교환(iteration swapping) 과정에서 최대 전력 감소 이득을 우선적으로 비교하여 자원을 재할당하기 때문에, 상기 반복이 많아질수록 실제 전력 감소 이득을 갖는 부반송파 쌍의 수는 줄어들게 되고, 상기 전력 감소 이득의 크기 또한 줄어들게 된다. 다시 말해, 상기 최대 전력 감소 쌍이 발생하지 않을 때까지 상기 교환 과정을 반복한다 하더라도 뒷부분에서 발생한 상기 전력 감소 이득은 미미한 양이 된다. 따라서, 이득이 수렴하는 부분에서 상기 반복의 수를 제한하는 요소가 필요하다. 본 발명에서는 상기 제한 요소 β를 이용하여 효율적으로 상기 반복 교환의 수를 제한하고자 한다.

여기서, 상기 β는 하기 <수학식 4>과 같이 나타낼 수 있다.

여기서, 상기 제한 요소 β의 값은 상기 제한 요소의 설정으로 인한 시스템의 성능 열화를 최대한 줄이면서 본 발명에서 제안하는 알고리즘에 따라 발생할 수 있는 복잡도를 최대로 줄일 수 있는 크기의 소정 값, 예를 들어, 0.3의 값으로 설정할 수 있다.

상기 최대 전력 감소 쌍들의 수에 대해 실제 재할당시 전력 감소 이득을 획득한 최대 전력 감소 쌍들의 수가 상기 제한 요소(Limitation factor) β보다 작지 않을 시, 상기 부반송파 할당부(301)는 403단계로 돌아간다. 여기서, 상기 부반송파 할당부(301)는 상기 최대 전력 감소 이득을 얻기 위해 전체 사용자에 대해 상기 교환(swapping) 과정을 소정 횟수 반복(iteration)할 수 있다. 상기 최대 전력 감소 쌍들의 수에 대해 실제 재할당시 전력 감소 이득을 획득한 최대 전력 감소 쌍들의 수가 상기 제한 요소(Limitation factor) β보다 작을 시, 상기 부반송파 할당부(301)는 더이상의 반복은 큰 전력 감소 이득을 가져올 수 없음을 판단하고 상기 과정의 반복을 중지한 후, 본 발명에 따른 알고리즘을 종료한다.

도 7은 본 발명에 따른 알고리즘과 종래 기술에 따른 알고리즘의 계산적 복잡도를 비교한 도면이다. 시스템에서 채널은 하나의 OFDM 심볼 간격 이내에 변경되지 않으며, 사용자들의 각 채널의 평균 SNR들도 같다고 가정한다. 상기 시스템에서 DCA(Dynamic Channel Allocation) 스킴(scheme)의 복잡도를 줄이기 위해서 8개의 인접 부반송들로 구성되는 서브 밴드를 기초로 하는 DCA를 채택하며, 각 사용자는 같은 수의 서브밴드에 할당되었다고 가정한다. 시뮬레이션에서 사용된 시스템 파라미터는 하기 <표 1>과 같다.

파라미터	값
변조	16QAM
부반송파의 수	512
서브 밴드의 수	64
서브 밴드의 사이즈	8
사용자 수	16
다중 경로	8
레이라이 페이딩

상기 종래 기술에 따른 WSA의 복잡도는 상기 <수학식 3>과 같이 나타낼 수 있으며, 상기 본 발명에 따른 알고리즘의 총 복잡도(Total Complexity)는 하기 <수학식 5>와 같이 나타낼 수 있다.

여기서, 상기 _kC₂는 K 명의 사용자 중 2명의 사용자를 선택하기 위한 조합 연산(combination operation)이다. 또한, 상기 N/K는 시스템에 N개의 부반송파와 K명의 사용자가 있을 시, 각 사용자에게 할당되는 부반송파의 평균 수를 의미하며, 각 사용자 K가 N/K개의 부반송파를 점유할 때, 최대 전력 감소 이득을 찾기 위해 요구되는 복잡도는 O(N/K)이다. 따라서, 두 사용자에 대한 반복 교환(iterative swapping)의 복잡도는 O(2·N/K)이다. 이때, 상기 랜덤 초기 할당에 대한 복잡도는 0의 값을 가진다.

또한, 상기 교환(swapping) 과정을 소정 횟수 반복(iteration)한다면, 본 발명에 따른 알고리즘의 총 복잡도(Total Complexity)는 하기 <수학식 6>과 같이 나타낼 수 있다.

여기서, 상기 a는 상기 교환(swapping)의 반복 수를 의미한다.

상기 도 7을 참조하면, 제한 요소(Limitation Factor) β가 0일 시, 즉 상기 반복 교환의 수에 제한을 두지 않을 시, 본 발명에 따른 알고리즘과 종래 WSA는 최대 전력 감소 쌍이 발생하지 않을 때까지 반복 과정을 거치기 때문에 높은 복잡도를 가진다. 하지만, 상기 WSA와 본 발명에서 제안된 알고리즘 간의 복잡도 차이가 생기는 이유는 상기 본 발명에서 제안된 알고리즘이 초기 할당(initial allocation) 과정에서 복잡도를 가지지 않기 때문이다.

여기서, 상기 제한 요소 β를 적용하여 상기 반복의 수를 제한할 수 있으며, 상기 β 값을 크게 설정함에 따라 본 발명에 따른 알고리즘의 복잡도는 점점 감소하게 된다. 여기서, 상기 제한 요소의 설정은 시스템의 성능 열화를 가져올 수도 있으나, 상기 제한 요소의 크기를 작은 값, 예를 들어, 0.3 이하의 값으로 설정하면, 상기 제한 요소의 설정으로 인한 성능 열화는 매우 적게 나타난다.

즉, 본 발명에 따른 복잡도를 최소화시키면서도 시스템의 성능 열화를 줄이기 위해서는 상기 복잡도의 감소량이 수렴하게 되는 구간에서 가장 작은 β를 선택해야하며, 따라서, 상기 β의 값은 0.3으로 설정할 수 있다. 상기 β의 값을 0.3으로 설정하였을 시, 상기 본 발명에 따른 알고리즘의 복잡도는 상기 WSA의 1/5로 줄어들 수 있다.

한편 본 발명의 상세한 설명에서는 구체적인 실시 예에 관해 설명하였으나, 본 발명의 범위에서 벗어나지 않는 한도 내에서 여러 가지 변형이 가능함은 물론이다. 그러므로 본 발명의 범위는 설명된 실시 예에 국한되어 정해져서는 안되며 후술하는 특허청구의 범위뿐만 아니라 이 특허청구의 범위와 균등한 것들에 의해 정해져야 한다.

상술한 바와 같이, 본 발명은 멀티 캐리어 통신 시스템에서, 각 사용자의 요구되는 대역폭(bandwidth)을 고려한 랜덤 초기 할당 과정과 최대 전력 감소 이득을 비교하여 재할당하는 교환 과정을 통해 채널을 할당함으로써, 기존 할당 방식과 비슷한 성능을 유지하면서도 실제적인 비교의 횟수를 줄여 알고리즘 자체의 복잡도를 줄일 수 있고, 상기 최대 전력 감소의 효율성에 대한 요소를 첨가함으로써, 상기 전력 감소 이득이 적어진 부분에 대한 복잡도를 감소시킬 수 있는 이점이 있다.

Claims

멀티 캐리어 통신 시스템에서 동적 채널 할당 방법에 있어서,

전체 사용자들에게 부반송파(들)를 초기 할당한 후, 모든 경우의 수로 상기 전체 사용자 중 두 명의 사용자를 선택하는 과정과,

상기 선택된 두 명의 사용자에게 각각 초기 할당된 부반송파(들)를 서로 교환하여 재할당함으로써 발생할 수 있는 전력 감소 이득을 상기 부반송파별로 계산하는 과정과,

상기 선택된 사용자별로 초기 할당된 부반송파들의 전력 감소 이득을 정렬하고, 상기 두 사용자에 대해 최대 전력 감소 이득을 가지는 부반송파 쌍을 선택하는 과정과,

상기 선택된 부반송파 쌍을 서로 교환하여 상기 두 사용자에게 재할당하는 과정을 포함하는 것을 특징으로 하는 방법.
제 1 항에 있어서,

각 사용자의 요구되는 대역폭(Bandwidth)에 따라 전체 사용자에게 부반송파(들)를 랜덤으로 초기 할당하는 과정을 더 포함하는 것을 특징으로 하는 방법.
제 1 항에 있어서,

최대 전력 감소 이득을 얻기 위해 상기 전체 사용자에 대한 상기 부반송파 재할당을 소정 횟수 반복(iteration)하는 과정을 더 포함하는 것을 특징으로 하는 방법.
제 3 항에 있어서,

실제 재할당시 전력 감소 이득(power reduction gain)을 획득한 부반송파 쌍의 수를 상기 반복(iteration) 과정으로 인해 재할당되는 부반송파 쌍의 수로 나누고, 결과값을 제한 요소(Limitation factor)와 비교하는 과정과,

상기 결과값이 상기 제한 요소보다 작을 시, 상기 반복을 중지하는 과정을 더 포함하는 것을 특징으로 하는 방법.
제 4 항에 있어서,

상기 제한 요소(Limitation factor)는 0.3 이하의 값임을 특징으로 하는 방법.
멀티 캐리어 통신 시스템에서 동적 채널 할당 장치에 있어서,

전체 사용자들에게 부반송파가 초기 할당되었을 시, 모든 경우의 수로 상기 전체 사용자 중 두 명의 사용자를 선택하고, 상기 선택된 두 명의 사용자에게 각각 초기 할당된 부반송파(들)를 서로 교환하여 재할당함으로써 발생할 수 있는 전력 감소 이득을 상기 부반송파별로 계산한 후, 상기 선택된 사용자별로 초기 할당된 부반송파들의 전력 감소 이득을 정렬하고, 상기 두 사용자에 대해 최대 전력 감소 이득을 가지는 부반송파 쌍을 선택 및 서로 교환하여 상기 두 사용자에게 재할당하는 부반송파 할당부와,

사용자의 복소 신호를 해당 사용자에게 재할당된 부반송파에 매핑하는 부반송파 매핑부를 포함하는 것을 특징으로 하는 장치.
제 6 항에 있어서, 상기 부반송파 할당부는,

각 사용자의 요구되는 대역폭(Bandwidth)에 따라 전체 사용자에게 부반송파(들)를 랜덤으로 초기 할당하는 것을 특징으로 하는 장치.
제 6 항에 있어서, 상기 부반송파 할당부는,

최대 전력 감소 이득을 얻기 위해 상기 전체 사용자에 대한 상기 부반송파 재할당을 소정 횟수 반복(iteration)하며, 실제 재할당시 전력 감소 이득(power reduction gain)을 획득한 부반송파 쌍의 수를 상기 반복(iteration)으로 인해 재할당되는 부반송파 쌍의 수로 나누고, 결과값을 제한 요소(Limitation factor)와 비교하여, 상기 결과값이 상기 제한 요소보다 크거나 같을 시, 상기 전체 사용자에 대한 부반송파 재할당을 다시 수행하고, 상기 결과값이 상기 제한 요소보다 작을 시, 상기 전체 사용자에 대한 상기 부반송파 재할당의 반복을 중지하는 것을 특징으로 하는 장치.
제 8 항에 있어서,

상기 제한 요소(Limitation factor)는 0.3 이하의 값임을 특징으로 하는 장치.
멀티 캐리어 통신 시스템에서 동적 채널 할당 방법에 있어서,

부반송파(들)가 할당된 전체 사용자 중 두 명의 사용자를 선택하는 과정과,

상기 두 사용자의 부반송파(들)를 서로 교환하여 재할당함으로써 발생할 수 있는 전력 감소 이득을 상기 부반송파별로 계산하는 과정과,

상기 두 사용자에 대해 최대 전력 감소 이득을 가지는 부반송파 쌍을 선택하는 과정을 포함하는 것을 특징으로 하는 방법.
제 10 항에 있어서,

상기 선택된 부반송파 쌍을 서로 교환하여 상기 두 사용자에게 재할당하는 과정을 더 포함하는 것을 특징으로 하는 방법.
제 10 항에 있어서,

각 사용자의 요구되는 대역폭(Bandwidth)에 따라 전체 사용자에게 부반송파(들)를 랜덤으로 초기 할당하는 과정을 더 포함하는 것을 특징으로 하는 방법.
제 11 항에 있어서,

최대 전력 감소 이득을 얻기 위해 상기 전체 사용자에 대한 상기 부반송파 재할당을 소정 횟수 반복(iteration)하는 과정을 더 포함하는 것을 특징으로 하는 방법.
제 13 항에 있어서,

실제 재할당시 전력 감소 이득(power reduction gain)을 획득한 부반송파 쌍의 수를 상기 반복(iteration) 과정으로 인해 재할당되는 부반송파 쌍의 수로 나누고, 결과값을 제한 요소(Limitation factor)와 비교하는 과정과,

상기 결과값이 상기 제한 요소보다 작을 시, 상기 반복을 중지하는 과정을 더 포함하는 것을 특징으로 하는 방법.
제 14 항에 있어서,

상기 제한 요소(Limitation factor)는 0.3 이하의 값임을 특징으로 하는 방법.
멀티 캐리어 통신 시스템에서 동적 채널 할당 장치에 있어서,

부반송파(들)가 할당된 전체 사용자 중 두 명의 사용자를 선택하는 수단과,

상기 두 사용자의 부반송파(들)를 서로 교환하여 재할당함으로써 발생할 수 있는 전력 감소 이득을 상기 부반송파별로 계산하는 수단과,

상기 두 사용자에 대해 최대 전력 감소 이득을 가지는 부반송파 쌍을 선택하는 수단을 포함하는 것을 특징으로 하는 장치.
제 16 항에 있어서,

상기 선택된 부반송파 쌍을 서로 교환하여 상기 두 사용자에게 재할당하는 수단을 더 포함하는 것을 특징으로 하는 장치.
제 16 항에 있어서,

상기 할당된 부반송파는 각 사용자의 요구되는 대역폭(Bandwidth)에 따라 전체 사용자에게 랜덤으로 초기 할당된 부반송파임을 특징으로 하는 장치.
제 17 항에 있어서,

최대 전력 감소 이득을 얻기 위해 상기 전체 사용자에 대한 상기 부반송파 재할당을 소정 횟수 반복(iteration)하는 수단을 더 포함하는 것을 특징으로 하는 장치.
제 19 항에 있어서,

실제 재할당시 전력 감소 이득(power reduction gain)을 획득한 부반송파 쌍의 수를 상기 반복(iteration)으로 인해 재할당되는 부반송파 쌍의 수로 나누고, 결과값을 제한 요소(Limitation factor)와 비교하는 수단과,

상기 결과값이 상기 제한 요소보다 작을 시, 상기 반복을 중지하는 수단을 더 포함하는 것을 특징으로 하는 장치.