Ⅰ. 서 론

릴레이 시스템은 셀 내의 음영지역 해소와 시스템 처리용량 증가를 위해 IEEE 802.16j, IEEE 802.16m, LTE-advanced와 같은 차세대 이동통신 표준에서 활발한 연구(Kanchei Loa and Chih-Chiang Wu, 2010)가 진행되 고 있다. LTE-Advanced의 릴레이 시스템과 셀간 간섭 제어 기술(Coordinated Multiple Point transmission/reception; CoMP)(3GPP RAN1, 2014)은 LTE-Advanced 시스템의 주요 기술로 IMT-Advanced의 요구사항을 만족시키 기 위해 논의되었다. 릴레이 시스템은 처리량 향상과 셀 경계에 위치한 단말의 전송률 향상을 위한 기술로 LTE-Advanced Release 9에서 제정되었다. LTE-Advanced에 도입된 릴레이 시스템은 기지국과 중계기 사이에 백홀링크를 구성하여 통신이 수행된다. LTE-Advanced 릴레이 시스템의 백홀링크는 무선 자원을 이용하기 때 문에 기지국의 추가나 유선 백홀의 설치가 필요가 없어 비용 효율이 높은 장점이 있다. 그러나 전체 자원의 일부가 백홀링크를 위해 사용되기 때문에 릴레이 시스템 도입에 따른 자원손실을 최소화하기 위한 효율적인 자원할당 알고리즘이 필요하다. 한편, 릴레이 시스템의 도입으로 인한 셀 당 무선 자원 소모량은 기지국-단말 기 간 통신에 있어 중계기 활용여부, 즉 경로선택에 따라 달라진다. 따라서, 자원할당 문제와 경로선택 문제는 통합되어 다루어져야 한다. 대부분의 LTE-Advanced 릴레이 시스템 관련 기존 연구들은 자원할당과 경로선택 문제가 통합되어 고려되지 않았다. 예를 들면, 송신노드와 수신노드 사이의 강도에 따라 경로 선택과 자원 할 당을 수행한 연구들(Hamdi and EI-Khamy, 2012; Ma et al, 2009; Ma et al., 2011; Saleh et al., 2011)이 있다. 그러 나 이러한 연구들은 경로 설정에 따른 무선 자원 소모량을 고려하지 않기 때문에 전체 시스템의 처리율을 최대 화 할 수 없다.

기존 연구로 릴레이 시스템의 시스템 처리율 최대화를 위해 자원할당과 경로선택을 통합하여 해결한 사 례(Hwang, 2013)가 있다. 이 연구에서는 IEEE 802.16j 네트워크에서 시스템 처리량 최대화를 위한 MMKP 기 반의 통합 자원할당 및 경로 선택 기법을 제안하였다. 그러나 IEEE 802.16j와 LTE-Advanced 릴레이 시스템의 프레임 구조가 상이하기 때문에 LTE-Advanced 릴레이 시스템에 적용하는데 문제가 있다. 즉, IEEE 802.16j 멀티 홉 릴레이 시스템은 기지국과 중계기의 전송 영역이 구분된 프레임 구조를 사용하기 때문에 전체 무선 자원의 일부를 반정적(semi-static)으로 할당하여 중계기의 전송 영역으로 사용하는 LTE-Advanced 릴레이 시 스템에 그대로 적용하는 것이 불가능하다.

현재, 릴레이 시스템의 효율 향상을 위한 연구는 다각적으로 진행되고 있다. 그 중 협력통신 기법은 기지 국 또는 중계기를 이용한 협력 통신을 수행하여 다이버시티 이득(Diversity Gain)을 얻기 위해 연구되었다. 예 를 들어, LTE-advanced 릴레이 시스템의 자원 효율 향상과 다이버시티를 개선하기 위한 Intra-cell CoMP 기반 의 협력통신 기법(Li et al., 2012)이 제안되었다.

본 논문에서는 Intra-cell CoMP 기반의 협력 통신을 이용하는 LTE-Advanced 릴레이 시스템의 하향링크 처 리율을 최대화를 위해 통합 자원할당 및 경로선택 문제를 정의하고 MMKP 문제로 변환한다. 또한, 라그랑지 승수를 기반으로 하는 MMKP 휴리스틱 알고리즘을 이용하여 통합 자원 할당 및 경로 선택 기법을 통해 근 사 해를 구한다.

본 논문의 구성은 다음과 같다. 2 장에서는 LTE-Advanced 릴레이 시스템의 본 연구와 관련된 특징들에 대 한 개요를 간략히 기술하며, 3 장에서는 통합 자원 할당-라우팅 문제정의하고 MMKP 문제로 변환하는 방법 을 기술한다. 그리고 MMKP 휴리스틱 알고리즘을 통해 문제의 근사 해를 구하기 위한 기법에 대하여 기술 한다. 4 장에서는 시뮬레이션을 통해 통합 자원 할당 및 경로 선택 기법의 성능을 분석하고 5 장에서 본 연 구의 결론을 맺는다.

Ⅱ. LTE-Advanced 릴레이 시스템

LTE-Advanced의 릴레이 시스템은 데이터 처리율 향상과 커버리지 확장, 음영지역 해소, 셀 가장자리 사용 자의 성능 향상을 위해 도입되어 3GPP LTE Release-9 물리계층 표준에 포함되었다. LTE-Advanced의 릴레이 시스템은 3GPP LTE Release-9 이전 단말들의 지원을 위해 MBSFN(Multimedia Broadcast multicast service Single Frequency Network) 서브프레임을 사용하여 백홀링크를 구성한다. LTE-Advanced 릴레이 시스템의 동 작 방식은 Type-1과 Type-2의 두 가지 방식으로 나누어진다. Type-1 릴레이 방식은 각 중계기가 기지국과 다 른 별도의 셀 ID를 가진다. 단말은 중계기를 독립적인 기지국으로 인식하고 동기 채널, 레퍼런스 심볼, 스케 줄링 정보 및 HARQ(Hybrid ARQ) 피드백 등을 요청할 수 있다. Type-2 릴레이 방식의 중계기는 별도의 PID(Physical Cell ID)를 갖지 않고 단말은 중계기의 존재를 유무를 인식하지 못한다. Type-2 릴레이는 기지국 과 PID 및 셀 제어 메시지를 공유한다. 때문에 중계기는 PDSCH(Physical Downlink Shared Channel)만을 전송 할 수 있고 CRS(Cell Specific Reference Signal) 및 PDCCH(Physical Downlink Control Channel)등의 제어채널은 전송하지 못한다. 프로토콜 계층 구현에 따라 중계기의 종류를 분류할 수 있다. 중계기는 프로토콜 계층 구 현에 따라 L1(Layer1), L2, L3로 분류 된다. L1 중계기는 수신된 신호를 증폭하여 재전송하는 amplify-and-forward의 기능을 수행하고 L2 중계기는 수신된 신호를 복호화 하여 전송하는 decode-and-forward 기능을 수행한다. L3 중계기는 기지국과 다른 별도의 PID를 갖고 기지국이 서비스 하는 대부분의 기능을 단 말에게 제공하며, 중계기가 기지국과 동일한 역할을 수행하기 때문에 별도의 프로토콜 구현이 필요 없다. L2 중계기와 L3중계기는 스케줄링 기능 구현 여부에 따라 기지국이 스케줄링을 수행하는 중앙 집중형 방식으 로 동작하거나 중계기가 독립적으로 분산형 방식으로 스케줄링을 수행 할 수 있다. 분산형 방식의 스케줄링 을 사용할 경우 협력통신을 위해 기지국은 스케줄링 정보를 중계기로부터 수신 받아야 하지만 중앙 집중형 방식으로 스케줄링의 경우 협력중계를 위한 별도의 정보 교환이 필요 없다.

Type-1 릴레이 방식은 백홀링크와 액세스링크가 사용하는 주파수 대역에 따라 인밴드 릴레이(inband relay) 와 아웃밴드 릴레이(outband relay)로 구분된다. 인밴드 릴레이는 백홀링크와 액세스링크가 동일 주파수 대역 에서 동작하고, 아웃밴드 릴레이는 백홀링크와 액세스 링크가 다른 주파수 대역에서 동작한다. 아웃밴드 릴 레이는 백홀 링크와 액세스 링크 사이의 간섭은 발생하지 않지만 인밴드 릴레이에 비해 주파수 대역 사용 효율이 떨어진다. 인밴드 릴레이는 백홀링크와 액세스링크 사이의 간섭이 발생하기 때문에 두 링크 사이의 동작이 시간적으로 분리 되어야 하지만 주파수 자원의 효율은 아웃밴드 릴레이에 비해 높다. 3GPP LTE Release-9에서는 인밴드 릴레이의 간섭문제를 해결하기 위해 MBSFN 서브프레임을 백홀링크로 사용한다. 중 계기는 MBSFN 서브프레임 구간에서만 기지국으로 부터 데이터를 수신 받을 수 있고, 이때 자기 간섭 발생 을 방지하기 위해 중계기는 단말에게 데이터를 전송할 수 없다. MBSFN으로 사용할 수 있는 서브프레임의 수는 자원할당 설정에 따라 달라진다. 중계기는 기지국으로부터 전송되는 PDCCH를 수신 받을 수 없기 때문 에 LTE Release-10 에서는 중계기를 위한 제어채널인 R-PDCCH을 사용한다. Type-1 릴레이에서 동작하는 협 력중계는 기지국과 중계기 사이의 Intra-cell CoMP를 통해 수행된다. 중계기가 수신 받은 데이터를 단말에게 전송할 때 기지국이 동일 시간에 동일 자원을 이용하여 단말에게 데이터를 송신하여 협력통신을 수행한다.

Ⅱ. 경로선택 및 자원할당 기법의 기존 연구

LTE-Advanced의 릴레이 시스템의 효율적인 자원 사용을 위한 경로선택과 자원할당에 대한 연구는 다음과 같은 사례가 있다. 첫 번째, 하나의 섹터 당 두 개의 릴레이를 배치하여 시스템 용량과 커버리지 향상을 보 인다. 릴레이의 효율을 극대화하기 위한 기하학적 배치와 SINR(Signal-to-Noise-plus_Interference Ratio) 분석 및 시스템의 용량 분석을 통해 중계기를 사용할 때 필요한 추가 자원을 고려한 경로설정 기법(Ma et al., 2009) 을 연구하였다. 그러나 중계기의 위치에 따라 경로 선택의 결과가 재설정 되어야 하는 문제가 있다. 두 번째, 멀티 홉 전송을 위한 SINR 기반의 경로를 선택 기법과 스펙트럼 효율(spectral efficiency) 기반 기법을 사용하 는 경로 선택 기법(Ma et al., 2011)을 제안하였다. 스펙트럼 효율은 샤논 공식이나 SINR을 MCS(Modulation Coding Scheme) 테이블에 매핑하여 계산하였다. 그러나 경로를 선택하고 라운드 로빈 방식의 자원 할당을 수 행하기 때문에 시스템 처리량 최대화를 위해서는 추가적인 자원 할당 기법에 대한 연구가 필요하다. 세 번 째, 공평성과 시스템 처리량 최대화를 위한 기지국과 중계기에 대한 시스템 자원 할당 기법(Saleh et al., 2011)을 연구하였다. 이 연구는 자원 할당을 위해 비례 공평성(proportional fairness)을 기반으로 하는 최적화 문제를 정의하고 라그랑지 승수를 이용한 알고리즘을 통해 근사 해를 구하였다. 분배된 자원은 기지국과 중 계기가 독립적으로 관리한다. 자원분배와 자원할당을 각각 수행하여 시스템 복잡도를 낮추었으나 전체적인 무선 자원을 고려하여 자원할당을 수행하지 않기 때문에 시스템의 처리율을 최대화 할 수 없는 것이 단점이 다. 네 번째, 중계기 사용자 수를 이용한 백홀링크의 자원분배 기법과 백홀링크와 액세스링크의 병목점을 고 려한 자원할당 기법(de Moraes et al., 2012)이 제안되었다. 그러나 경로 선택에 대한 기법이 고려되지 않았기 때문에 추가적인 연구가 필요하다. 다섯 번째, 효율적인 자원사용과 사용자의 QoS 보장을 위한 백홀링크의 자원 할당 기법(Hwang, 2013)이 제안되었다. 이 연구에서는 사용자의 개별 요구 사항에 따라 가장 높은 메트 릭을 가지는 사용자에게 우선적으로 자원할당을 수행하였다. 중계기를 사용하는 사용자의 경우 지연시간을 고려한 별도의 메트릭을 이용한 자원할당을 수행하여 백홀링크의 효율을 높였다. 그러나 백홀링크의 자원할 당을 각각의 중계기가 수행하여 액세스링크의 자원은 고려되지 않기 때문에 시스템 처리량을 최대화를 할 수 없다.

1. 협력통신 기반의 통합 자원 할당 및 경로 선택

본 논문에서 해결하고자 하는 문제는 Type-1 인밴드 방식으로 동작하는 LTE-Advance 릴레이 시스템의 하 향링크 처리율을 최대화하는 것이다. 이를 위해 기지국과 단말 사이의 경로 선택과 자원할당 문제를 통합하 여 다룬다. 본 논문에서 고려하는 LTE-Advance 릴레이 시스템 모델은 <Fig. 2>와 같다. 하나의 기지국 (eNodeB)과 M 개의 중계기(Relay Node), N 개의 단말(User Equipment)을 고려한다. 기지국은 단말에게 직접 데이터를 보내거나 또는 중계기를 경유하는 경로를 통해 데이터 전송을 수행할 수 있다. 기지국과 단말 사이 의 데이터 전송은 하나의 경로를 통해서만 수행될 수 있고, LTE-Advance의 Type-1 릴레이 시스템은 non-transparent 모드로 동작하기 때문에 기지국과 직접 통신을 수행을 할 수 없는 단말이 존재한다. 프레임 내의 각 리소스 블록은 하나의 노드에 의해서만 사용되고, 하나의 리소스 블록을 통해 전송되는 데이터의 양 (bit/resource block)은 CQI(Channel Quality Indicator) 인덱스를 통해 결정된다. CQI 인덱스는 송신 노드와 수신 노드 사이의 MCS 레벨의 인덱스와 동일하다. MCS 레벨의 인덱스는 동일 프레임 내에서 변하지 않는다고 가정한다. 제어채널을 위해 필요한 자원은 고려하지 않는다. <Fig. 1>

협력 통신을 사용하지 않는 LTE-Advance 릴레이 시스템의 하향링크 처리율 최대화는 식 (1)-(5)와 같이 표 현할 수 있다.(2)

위 식에서 i(i = 1, …, M + 2)는 기지국 (i = 1, 2) 과 중계기 (i = 3, …, M + 2) 의 인덱스를 의미하고, j(i = j, …, N) 는 단말의 인덱스를 의미한다. 기지국과 단말 사이의 직접 통신은 백홀링크와 액세스링크 모 두에서 수행될 수 있기 때문에 백홀 링크를 통한 전송에는 i = 1 을 이용하였고 액세스링크를 통한 전송에서 는 i = 2 로 구분하였다. 식 (1)의 R_ij는 단말 j 가 단말이 요구하는 평균 데이터 전송률이다. R_ij는 단말 j 가 어떤 경로를 사용해도 보장해 주어야하기 때문에 경로 선택의 결과와 무관하다. x_ij는 경로 선택에 대한 이 진 값으로 0 또는 1의 값을 갖는다. 기지국에서 단말로의 데이터 전송은 하나의 경로만을 이용할 수 있기 때 문에 식 (3)에서 단말 j 로 통하는 모든 경로 i 에 대한 x_ij의 합은 1이 된다. r_ij는 송신 노드 i 가 수신 노드 j 에게 데이터를 전송할 때 필요한 리소스 블록의 수이다. RB_{back haul} 과 RB_access 은 백홀링크와 액세스링크 에서 사용할 수 있는 리소스 블록의 최대 수를 의미한다. T_ij는 리소스 블록 하나를 이용하여 송신 i노드가 수신 노드 j 에게 보낼 수 있는 데이터(bits/resource block)의 양을 의미 한다. 백홀링크와 액세스링크에서 사 용할 수 있는 자원의 양은 한정되어 있기 때문에 식 (1)의 하향링크 처리율 최대화는 제약식 (4), (5)를 만족 해야 한다. 식 (4)와 식 (5)의 첫 번째 항은 각각 백홀링크와 액세스링크를 통해 기지국이 단말에게 직접 데 이터를 전송할 때 필요한 자원의 양이다. 식 (4)의 두 번째 항은 중계기 i 를 경유하여 단말에게 데이터를 전 송할 때 필요한 백홀링크 자원의 양 이다. r_ijT_ij를 이용하여 단말에게 전송할 데이터의 크기를 구한 후, 기 지국과 중계기 사이의 전송 블록 T_1j를 사용하여 전송에 필요한 리소스 블록의 수가 결정된다. 식 (5)의 두 번째 항은 중계기 i 를 통해 단말에게 데이터를 전송할 때 필요한 액세스링크 자원의 양이다.

본 논문에서 고려하는 협력 통신 기법은 중계기가 단말에게 데이터를 전송할 때 기지국이 동시에 동일자 원을 이용하여 수행된다. 때문에 협력 통신에 대한 이득은 액세스링크에서 발생하기 때문에 처리율 최대화 의 식 (5)는 식 (6)으로 변환된다. 식 (6)의 r_ij′는 중계기 i가 단말 j 에게 데이터 전송할 때 기지국이 협력 통 신을 수행할 경우 필요한 리소스 블록의 수이다. 협력 통신 수행 시 MCS 레벨의 인덱스는 기국과 단말 사이 의 수신 전력과 중계기와 단말 사이의 수신 전력의 합을 이용하여 계산된 SINR을 통해 얻어진다. 협력 통신 을 수행하면 단말이 데이터 수신에 필요한 MCS 레벨의 인덱스가 높아지기 때문에 r_ij′는 r_ij보다 작은 값을 갖게 된다.

위에서 정의한 하향링크 처리량 최대화 문제는 상호 독립적인 두 개의 제약 식으로 표현되기 때문에 배낭 문제(0-1 Knapsack Problem)에 적용하여 최적화 문제를 해결할 수 있다. 일반적으로 배낭문제는 각 그룹에 속 하는 아이템을 제약 조건을 만족시키면서 아이템의 가치의 합이 최대가 되도록 배낭에 집어넣는 방법을 찾 는 문제이다. 1차원 배낭문제는 하나의 제약조건만을 고려하기 때문에 제약조건이 다수인 LTE-Advanced 릴 레이 시스템의 하향 링크 처리량 최대화 문제 그대로 적용할 수 없다. 따라서 LTE-Advanced 릴레이 시스템 의 하향링크 처리량 최대화 문제는 1차원 배낭문제를 확장한 다중차원 다중선택 배낭 문제(MMKP)로 다루 어져야 한다. MMKP는 다수의 그룹이 존재하는 상황에서 각 그룹이 다수의 제약조건을 만족시키는 하나의 물건을 선택하는 방법을 찾는 문제이다. LTE-Advanced 릴레이 시스템의 하향링크 처리량 최대화 문제를 MMKP 기법을 적용하면 그룹은 단말, 그룹에서 선택할 수 있는 물건은 단말이 선택할 수 있는 경로로 생각 할 수 있다. 배낭문제에서 각 물건은 가치를 지니는데, LTE-Advanced 릴레이 시스템의 경우, 단말이 각각의 경로를 통해 데이터를 전송하였을 때의 평균 데이터 전송률로 설정했다. 위의 식 (6)의 두 제약조건에 의해 우리가 다룰 MMKP는 2차원 MMKP로 표현이 가능하다.

제약이 있는 최적화 문제를 풀기 위한 방법으로 Joseph L. Lagrange에 의해 고안된 라그랑지 승수 법이 있 다. MMKP 문제는 라그랑지 승수를 사용하여 제약이 있는 최적화 문제를 제약이 없는 최적화 문제로 변환 (Yoon and Kim, 2010; Kawser et al., 2012)할 수 있다. 식 (5)와 (6)의 두 제약식의 라그랑지 승수를 μ₁, μ₂라고 한다면, 라그랑지 승수 법을 이용하여 본 논문에서 제안하는 하향링크 처리율 최대화 문제 (1)-(5)를 다음과 같이 제약식이 없는 최대화 문제 (7)로 변환할 수 있고 협력 통신을 사용한 최대화 문제 (1-4), (6)은 (8)로 변 환 할 수 있다.

최대화 문제의 최적 해가 x^*_ij일 때 식 (8)을 만족하며, 동시에 아래의 제약조건을 갖는 최적화 문제의 해 이기도 하다.(9)(10)

최대화 문제의 최적 해 x^*_ij에 근접한 x_ij는 라그랑지 승수를 이용한 휴리스틱 알고리즘을 통해 구한다. 휴리스틱 알고리즘은 라그랑지 승수를 변경해 가며 x_ij가 최적해 x^*_ij에 최대한 근접한 값을 찾는다. 본 논 문에서 제안하는 라그랑지 승수를 기반으로 하는 휴리스틱 알고리즘은 초기화, 제약조건 위반 완화, 성능 개 선 3단계에 걸쳐 수행된다. 제안하는 알고리즘은 경로에 따라 단말에게 데이터를 전송할 때 필요한 리소스 블록의수는 결정된 상태에서 진행한다. 초기화 단계에서는 단말이 가진 경로의 데이터 전송률을 이용하여 전송률이 가장 높은 경로를 초기 경로로 설정한다. 단말이 요구하는 평균 데이터 전송률은 어떤 경로를 선택 해도 동일하다. 때문에 단말이 요구하는 평균 데이터 전송률을 그대로 사용하게 되면 제약조건 위반 완화 단 계에서 계산되는 δ_ij의 값이 0으로 계산되어 단말의 경로 변경이 불가능한 문제가 발생한다. 이를 해결하기 위해 초기화 단계에서 경로의 품질을 비교하여 경로를 통해 전송되는 데이터 전송률에 ε₁ (0.01)크기의 차등 을 주었다. 이때 동일 품질을 갖는 경로가 존재하는 경우 ε₂ (0 < ε₂ < 0.001) 크기로 경로를 통해 전송되는 데이터 전송률에 차등을 주었다. 각 단말 j는 선택할 수 있는 경로 중 데이터 전송률이 가장 높은 경로를 초 기 경로로 선택 한다. 이후 선택된 경로를 통해 데이터 전송할 때 필요한 자원을 할당한다. 초기 경로 설정 하고 모든 단말에게 자원을 할당하기 때문에 자원 소모량이 제약조건을 초과 할 수 있다. 자원 할당 후 제약 조건이 초과하는 차원이 있다면 제약조건 위반 단계를 진행한다.

제약조건 위반 완화 단계에서는 백홀링크 또는 액세스링크의 제약 조건이 초과하는 경우 하나의 단말을 선택하여 선택된 경로를 변경한다. 백홀링크와 액세스링크의 제약조건이 모두 초과하는 경우 두 경로 중 제 약조건 위반이 큰 제약조건을 선택하여 제약조건 위반 완화 단계를 진행한다. 단말 j는 변경할 수 있는 모든 경로 i에 대한 δ_ij값을 계산한다. 계산된 중 가장 작은 값을 갖는 단말 j와 변경되는 경로 i를 선택하여 경로 변경을 진행한다. 초기화 단계에서 가장 데이터 전송률이 높은 경로를 초기 경로로 사용하였기 때문에 현재 데이터 전송률의 합이 가장 높은 상태이다. 때문에 현재 선택된 경로를 통한 전송률의 적게 변화 되도록 δ_ij 를 선택하여 경로를 변경한다. 경로를 변경할 단말 j′과 경로 i′이 선택 되면 δ i ′ j ′ 를 이용하여 라그랑지 승수 를 업데이트 한다. 경로 선택 변경 하고 백홀링크의 제약조건과 액세스링크의 제약조건을 확인하여 조건 위 반 완화 단계를 반복하여 수행한다.

사용할 수 있는 자원의 양은 한정되어 있기 때문에 자원할당을 받지 못하는 단말이 존재할 수 있다. 단말 이 자원할당을 받지 못하는 경우를 표현하기 위해 자원 사용량이 0이고 가치가 0인 보조 경로를 도입하여 제약조건 완화 단계에서 선택될 수 있도록 하였다.

제약조건 위반 완화 단계 진행 후 선택된 경로보다 높은 가치를 가지면서 경로 변경 시 제약조건을 위반 하지 않는 단말이 존대한다면 해당 단말의 경로를 변경한다. 단말이 선택한 기존경로와 변경 가능한 경로의 가치로 δ_ij를 계산하여 가장 큰 값을 갖는 단말의 경로를 변경 한다. 이 단계는 경로변경이 가능한 단말이 존 재하지 않을 때까지 반복해서 수행된다. 라그랑지 승수 기법을 기반의 휴리스틱 알고리즘은 초기화 단계는 N 개의 단말이 M 개의 경로를 지니기 때문에 모든 경로를 비교하기 때문에 O(MN) 복잡도를 갖는다. 그리고 제약 조건 위반 완화 단계는 O(K(M - N)²) 복잡도를 갖는다. 여기서 K 는 제약조건의 수이다.

Ⅲ. 시뮬레이션 결과

본 절에서는 제안하는 기법의 성능을 분석한다. 제안하는 MMKP 기법의 성능 평가를 위해 소모적 검 색 기법(Exhaustive Search) 및 링크 품질 기반 기법(LQB)과 비교 평가하였다. 소모적 검색은 기지국과 단 말 사이의 경로 설정과 자원할당 순서의 모든 조합을 검색하여 최적 해를 도출하기 위한 기법이다. 시나 리오에서 단말의 수가 N 이고 각 단말이 선택할 수 있는 경로의 수가 M 으로 동일할 때 경로 선택과 자 원할당 조합의 수는 M^N 가 된다. 소모적 검색 기법은 O(M^N)의 복잡도를 가지지 때문에 단말이나 중계 기의 수가 증가 할수록 조합 가능한 경우의 수가 기하급수적으로 증가하게 된다. 링크 품질 기반 기법은 min{r_1j, arg min max (r₁, r_ij)} 을 고려하여 경로 선택을 수행한다. 각 단말은 중계기를 경유하는 경로 중 가 장 우수한 품질을 갖는 경로를 선택하고 선택된 경로와 기지국과 단말이 직접 통신을 수행하는 경로와 품질 을 비교하여 품질이 우수한 경로를 최종적으로 선택한다. 이 때, 기지국과 단말이 직접 통신하는 경로가 선 택된 경우 백홀링크와 액세스링크를 무작위로 사용하였다. 표 1은 실험에서 사용한 주요 시스템 파라미터이 다. 송신 노드와 수신 노드 사이의 SINR에 따라 결정되는 MCS 레벨을 사용하였다. 실험에서 사용한 경로 감쇠 모델은 네트워크 시뮬레이터 OPNET에서 사용되는 모델을 기반으로 하였다. 실험에서 사용한 경로 감 쇠(path loss) 모델은 Erceg Suburban Fixed이고 지형 모델은 terrain A로 나무와 언덕이 많은 산악지형이다. terrain A는 경로 감쇠 지수(path loss exponent)가 4.6으로 경로 감쇠가 심한 지형이다. Fig. 3

실험에서 중계기는 기지국과 약 400m 거리에 위치하며 6개의 중계기를 기지국을 중심으로 정육각형으로 형태로 배치하였다. 인접한 중계기 사이의 거리는 약 400m이다. 단말의 배치는 기지국과 900m 거리 이내에 무작위로 하였고 실험은 단말의 수를 9, 18, 27, 36, 45 증가 시키며 진행하였다. 단말 수가 45개인 시나리오 에서 기지국과 단말 사이의 거리 에 따라 배치된 평균 단말의 분포는 <Fig. 4>와 같다. <Fig. 5>는 단말 개수 변화에 따른 시스템의 처리율을 나타내며 Exhaustive, MMKP, LQB 기법의 성능을 비교하였다. 결과에 사용 된 값은 단말 수에 따라 각각 다른 5개의 시나리오를 실험한 결과 값의 평균이다. 단말의 수가 9, 18, 27, 36, 45 일 때 LQB 기법은 20.8 Mbps, 21.6 Mbps, 23.8 Mbps, 25.6 Mbps, 28 Mbps 의 성능을 보였다. MMKP 기법 은 22.4 Mbps, 25.6 Mbps, 29.6 Mbps, 34.4Mbps, 37.6 Mbps의 성능을 보여 LQB 기법에 비에 평균 5.96 Mbps 우수한 성능을 보였고, 단말의 수가 증가할수록 LQB 기법에 비해 우수한 성능을 보였다. Exhaustive 기법은 23.2 Mbps, 26.4 Mbps, 30.4 Mbps, 36 Mbps, 39.2 Mbps의 성능을 보여 LQB 기법보다 평균 7.08 Mbps 높고 MMKP 기법보다 평균 1.12 Mbps 높은 성능을 보였다. 실험 결과 MMKP 기법은 Exhaustive 기법에 근접한 성 능을 보였다. LQB 기법은 경로가 설정된 되고 변경 되지 않기 때문에 효율적인 자원 사용을 할 수 없기 때 문에 MMKP 기법과 Exhaustive 기법에 비해 낮은 성능을 보인다. 협력중계를 이용할 경우 MMKP 기법의 성 능은 23.2 Mbps, 26.4 Mbps, 30 Mbps, 35.2 Mbps, 38.4 Mbps로 협력중계를 이용하기 전보다 평균 0.74 Mbps 의 성능 향상을 보였다.

<Fig. 6>은 중계기를 경유해 데이터를 수신 받는 단말들의 성능 분석을 위해 단말들을 기지국과 600m 이상 900m 이하 거리에 무작위로 배치한 실험의 결과이다. 단말의 수가 9, 18, 27, 36, 45 일 때 LQB 기법은 6.6 Mbps, 8.8 Mbps, 10.6 Mbps, 11.6 Mbps의 성능을 보였다. MMKP 기법은 9 Mbps, 11 Mbps, 12.2 Mbps, 12.4 Mbps, 13.4 Mbps의 성능을 보여 LQB 기법에 비에 평균 2.04 Mbps 우수한 성능을 보였다. Exhaustive 기법은 9.4 Mbps, 11.64 Mbps, 12.44 Mbps, 12.84 Mbps, 13.64 Mbps의 성능을 보여 LQB 기법보다 평균 2.32 Mbps 높고 MMKP 기법보다 평균 0.28 Mbps 높은 성능을 보였다. 협력중계를 이용할 경우 MMKP 기법의 성능은 10 Mbps, 11.8 Mbps, 12.6 Mbps, 13 Mbps, 14.4 Mbps로 협력중계를 이용하기 전보다 평균 0.76 Mbps 의 성능 향상을 보여 <Fig. 6>의 결과에 사용한 시나리오와 유사한 성능을 보였다. 협력중계를 통한 이득은 기지국과 단말 사이의 링크품질에 따라 다르기 때문에 중계기와 단말 사이의 링크품질이 좋지 않은 경우 이득이 크지 않은 것을 볼 수 있다. 제안하는 MMKP 기법은 LQB 기법 보다 우수하고 Exhaustive 기법에 근접한 성능을 보인다.

Ⅳ. 결 론

본 논문에서는 LTE-Advanced 릴레이 시스템의 하향 링크 처리율을 최대문제를 정의하고 라그랑지 승수를 기반 MMKP 휴리스틱 알고리즘을 이용하여 위한 통합 자원 할당-경로선택 기법을 제안하였다. 소모적 검색 기법과 링크 품질 기반 기법, MMKP 기법을 비교 분석하여 제안하는 기법이 최적 해에 근접한 성능을 나타 내는 것을 보였다. 링크 품질 기반 기법보다 높은 성능을 나타내는 것을 보였다. 본 논문에서는 백홀 링크와 액세스링크의 비율이 고정적인 환경에서 시스템 처리량 문제를 고려하였다. 그리고 시스템 처리량만을 최대 화하기 때문에 단말들 사이의 공정성이 보장 받지 못한다. 향후 유동적으로 변화하는 시스템에서 적용 가능 한 시스템 처리량 최대화 문제 해결을 위한 추가적인 연구와 단말 사이의 공정성을 보장 하면서 시스템 처 리량을 최대화 하는 추가 연구가 요구된다.