다중 안테나 시스템의 비약적인 발달로 MIMO(Multiple-Input Multiple-Output)는 무선 네트워크의 핵심 기술로 자리 잡았다[1]. 네트워크 용량 증대와 안정적인 무선 통신 지원과 같은 MIMO의 혁신적인 기능은 이미 WLAN과 3G, 4G, 5G등의 이동통신 네트워크에 일찍이 적용되어 무선 네트워크 시장을 주도하고 있다. 또한 메시 네트워크의 출현과 더불어 어디서든지 쉽게 MIMO 장비가 구축된 네트워크 시스템을 접할 수 있게 되었다. MIMO가 미래 무선 통신의 핵심 기술이 될 것이라는 사람들의 기대와 더불어 MIMO는 지속적으로 기능이 향상되어 특히 물리계층에서 성과를 이루었다[2].

이러한 새로운 기술의 성능향상을 위해 기존에는 라우팅, 스케줄링, 그리고 MAC 프로토콜과 같은 측면에서 처리율(throughput) 최적화 문제에 대해 고민해왔다. 이러한 노력은 주로 물리계층의 연구에 집중되었던 SU-MIMO (Single-User MIMO)를 넘어서 MU-MIMO (Multi-User MIMO)로 확장되었다. 한편 SISO 네트워크 혹은 SU-MIMO에서의 다양한 이슈들이 MU-MIMO 에서는 보다 복잡한 문제로 변화된다. 멀티 홉 MIMO (Multi-hop MIMO) 네트워크에서는 기존의 SISO보다 복잡해진 MU-MIMO의 물리계층 연산이 스케줄링과 같은 다른 계층의 문제와 연계되었을 때 그 복잡도가 기하급수적으로 커지는 특성이 있다. 특히 문제가 LP (Linear Programming) 등으로 쉽게 표현될 수 없는 점이나, 표현한다고 해도 수 많은 변수들로 인해 최적화 어려움이 있다.

본 논문은 주어진 트래픽 요구량을 만족시키는 최소 길이 스케줄링(minimum length scheduling) 문제를 멀티 홉 MIMO 네트워크에 적용하여 계층간 최적화 문제로 해결하는 데 목적이 있다. 또한 이과정 중에 나타나는 복잡도 문제를 해결하는 방법에 대하여 논한다. 제안한 해결방법은 컬럼 제너레이션 (column generation)을 통한 LP decomposition을 기반으로 하여 최적화된 스케줄링 알고리즘을제안한다.

본 논문의 주요 공헌점은 다음과 같다.

1. MIMO 시스템의 제약사항을 최소 길이 스케줄링 문제로 재정의했다.

2. column generation을 사용해서 복잡도 문제를 해결하고 효율적인 스케줄링 알고리즘을 제안했다.

3. 수학적 모델을 제시하고 성능 평가를 통해 제안한 모델과 알고리즘의 효용성을 입증하였다.

본 논문은 다음과 같이 구성된다. 2장에는 관련 연구를 소개하고 3장에서는 시스템 모델에 관해 설명한다. 4장에서는 스케줄링 알고리즘을 소개하고 5장에서 성능 평가를 통해 제안의 타당성을 검증하며 6장에서 결론을 맺는다.

Link Scheduling : 주로 컬러링 문제로 변형되는 링크 스케줄링 문제는 기본적으로 NP-hard이기 때문에 수많은 근사 알고리즘이 제안되어 왔다. [3]은 주어진 링크의 트래픽 요구량을 만족시키는 최소 길이 스케줄 방법을 찾기 위해 복잡도 O(N⁵)의 알고리즘을 제안했다. 하지만 이 알고리즘은 단지 half-duplex constraint만을 고려하였다. [4]는 SINR 제약사항을 추가했을 때 적용할 수 있는 방법을 제시했지만, 트래픽 요구량을 나타내는 벡터가 superincreasing 성질을 갖는 특정한 상황에서만 적용될 수 있는 한계점을 지니고 있다.

MIMO 스케줄링 : [5]에서는 무선랜에서 MIMO AP를 통해 다수의 수신자들에게 동시에 데이터를 보낼 수 있도록 하여 MU-MIMO의 공간적 멀티플렉싱 (spatial multiplexing) 이득의 최대화 문제를 다루었다. [6]에서는 SIC를 고려한 MIMO 애드혹 네트워크에서의 링크 스케줄 문제를 다루었다.

계층간 최적화 : [7]는 최초로 멀티 홉 MIMO 네트워크에 적용할 수 있는 계층간 최적화를 위한 프레임워크를 제안했다. 또한 이들이 제안한 프레임워크는 처리량 최대화를 고려한 전형적인 스케줄링 문제에 적합하도록 설계되어 풀고자 하는 최소 길이 스케줄링 문제 (일반적으로 최소길이 스케줄링 문제가 더 큰 복잡도를 갖는다) 에는 직접적으로 적용될 수 없는 한계가 있다. [8]은 본 논문과 가장 비슷한 문제를 풀고 있다. 하지만 이 논문은 MU-MIMO의 특성을 활용하지 않았다는 한계점을 지니고 있다. [9]에서 저자들은 SINR based의 스케줄링 방법을 제시한다. Column generation 방법을 이용한 이 문제는 MIMO를 고려하지 않았다.

이번 절에서는 풀려고 하는 최소길이 스케줄링 문제를 수학적으로 정형화 (formulation) 하고 여기서 생기는 부가적인 문제를 해결하기 위한 방법을 제시한다. 아래 문제 정형화에 사용된 용어 및 그 의미는 <표 1>에 정의하였다.

<표 1>의 항목에 기반하여 아래와 같이 문제를 정의한다.

매칭(s∈S) : 하나의 매칭은 링크(e)와 링크에 할당된 데이터 스트림의 개수 (n(e))의 집합이다. 즉, 매칭은 스케줄을 구성하는 하나의 요소가 되어 매칭을 구성하는 모든 링크들은 같은 타임슬롯에 서비스된다. 다시 말해서 하나의 매칭안의 모든 링크들은 각자 할당된 개수만큼 데이터 스트림을 동시에 보내도 문제가 없음을 의미한다.

풀려는 스케줄링 문제의 목적은 주어진 트래픽 요구량을 만족시킬 수 있는 가장 빠른 스케줄이 되는 매칭의 집합을 찾는 것이다. 어떤 매칭(s)이 지속되는 시간을 λ_s라 할 때 스케줄의 총 길이는 가능한 모든 매칭의 합이 되므로 아래 식으로 표현 가능하다.

따라서 풀고자 하는 스케줄링 문제는 주어진 매칭의 합을 τ라고 했을 때 이를 최소화 시키는 문제가 된다. 이것을 MR-MSP (Multi-data Rate Minimum Scheduling Problem)으로 표기한다.

이때 모든 링크는 각자 주어진 트래픽 요구량(de)을 만족해야 하므로 다음과 같은 식으로 제약사항을 추가 할 수 있다.

주어진 식에서 r_s,e는 링크(e)가 주어진 매칭(s)에서 보낼 수 있는 데이터 속도를 의미한다. 또한 각 매칭의 길이는 음수가 될 수 없으므로 다음의 제약사항을 추가한다.

제약사항 <식 (1)>, <식 (2)>로 주어진 문제 Ρ₁ ∶MR-MSP은 매우 간단한 형태의 LP로 형성되었지만, 최적 값을 구하기 위해 고려해야 할 변수의 개 수가 많아 큰 복잡도를 야기한다. 고려하는 모델은 각 링크당 A개의 데이터 스트림을 보낼 수 있기 때문에 가능한 모든 매칭의 개수는 실제로 (A+1)^e이 될 것이고, 이를 모두 고려하여 계산하는 것은 매우 비효율적이다.

이러한 복잡도 문제는 불가능한 매칭을 미리 제거하여 많은 도움을 얻을 수 있다. 하지만 MIMO의 경우 데이터 스트림을 다수의 수신단에게 동시전송 하거나 다수의 송신단으로부터 수신하는 경우도 가능한 매칭으로 만들어진다. 따라서 위의 방법은 여전히 직접적인 해결책이 될 수 없다.

이 문제를 column generation 방법을 이용해 해결하고 이를 바탕으로 스케줄링 알고리즘을 제안한다. column generation은 주어진 문제의 형태를 변경하지 않고 복잡도를 낮춰 실질적으로 문제 해결 가능성을 높여준다.

노드 수와 링크 수를 변경하며 랜덤한 토폴로지를 생성하고, 각각의 트래픽 요구량 및 채널 역시 랜덤하게 생성했다. 제안한 알고리즘의 정상 동작을 위해선 Ρ₂에서 초기 매칭 집합 M을 결정해줄 필요가 있다. 링크의 개수만큼의 매칭을 형성해서 각 매칭에 하나의 링크가 최대의 스트림을 가질때를 구성해서 초기값을 설정했다.

■ Case-study 1. Algorithm procedure

본 케이스 스터디에서는 제안한 알고리즘의 성능을 검증하여 그 적정성을 보였다. <그림 2>의 토폴로지에서 각각 트래픽 요구량은 <표 2>와 같다.

<표 3>의 결과를 통해 제안한 알고리즘이 정상적으로 최소 길이 스케줄 결과를 보임을 확인했다.이 예에선 최적해를 위한 매칭이 10개였고, 8, 9의 매칭에서는 3개의 링크가 동시에 전송되고, 대부분의 경우 알고리즘이 간섭이 없는 링크 셋을 찾아(1, 2, 4, 6) 최대의 스트림을 할당하였다.

■ Case-study 2. Algorithm comparison

아래 2가지 알고리즘을 비교하였다.

1. Approximation : 알고리즘 속도 성능 개선을 위해서 sub-problem P_3의 objective function을 wTrs에서 wTzs로 바꾸고 제약사항 (13)을 제거했다. 이를 통해 sub-problem의 각 매칭의 데이터 속도를 스트림의 개수로 근사했다.

2. DoF : [8]에서 제안한 DoF 방식을 적용하였다. 데이터 속도를 고려하지 않은 채 스트림의 개수를 최대화하는 목적함수를 풀었다.

10개의 노드, 3개의 안테나가 있는 상황에서 각각 링크의 개수를 10~50개로 변경시켰고 결과는 <표 4>와 같다.

<표 4>의 결과에서 알 수 있듯이 approximation 방법은 제안한 방법과는 달리 최적해에서 훨씬 멀어지는 것을 확인할 수 있었다. 이는 특히 링크 수가 많아지면서 더욱 심해졌다. 이를 통해 approximation이나 DoF 처럼 단지 데이터 스트림의 개수의 최대화가 잘못된 결과를 나타낼 수 있음을 확인했다. 또한 DoF 방식처럼 다중 전송 속도를 고려하지 않을 경우 minimum length scheduling 문제에서 approximation 보다도 훨씬 떨어지는 결과를 나타내는 것을 확인 할 수 있었다. 이는 곧 채널 상황에 따른 데이터 속도가 MU-MIMO에서의 전체적인 스케줄 결과에 민감하게 작용하기 때문이라고 해석할 수 있다. 반면 멀티 데이터 속도를 고려했던 방법은 다른 알고리즘에 비해 정확한 결과를 얻을 수 있었다.

■ Case-study 3. Convergence time analysis

최적해를 구하는데 까지 걸리는 시간과 알고리즘 반복 횟수를 측정해 convergence analysis를 수행했다. 첫 번째 케이스 스터디는 Ρ₁와 제안한 알고리즘을 통해 최적화된 해를 구하는데 걸리는 시간을 측정했다. 두 번째 케이스 스터디로는 노드개수를 10개로 고정한 채, 링크의 개수와 안테나 개수를 변화시켜가며 알고리즘의 반복 횟수를 측정하였다. 각 실험은 20회씩 하여 그 평균값을 구하였고, 각각의 결과는 <표 5>와 <표 6>과 같다.

<표 5>를 보면 모든 매칭을 통해 계산하는 Ρ₁은 링크의 개수가 20개만 되어도 지나치게 오랜 시간이 걸려는 문제가 있다. 이에 비해 제안한 방법은 링크 개수가 50개일 경우에도 1분 안에 문제를 해결하였다.

<표 6>의 평균 반복 횟수를 보고 알 수 있었던 흥미로운 점은 알고리즘이 안테나 개수보다는 주로 링크의 개수에 더 많은 영향을 받고 있다는 사실이다. 이는 sub-problem Ρ₃에서 제약사항의 개수에 직접적으로 영향을 주는 요소는 안테나의 개수보다는 링크의 개수이기 때문이라고 해석할 수 있다.

본 논문에서는 각 링크의 트래픽 요구량을 만족시키는 최소 길이 스케줄링 문제를 멀티 홉 MIMO 네트워크에서 적용하여 문제를 새롭게 형성하고 이를 해결하는 방법을 제안했다. 주어진 문제를 LP로 형성하고 이때 생기는 복잡도 문제를 column generation 방법을 이용하여 해결했다. 다수의 케이스 스터디를 통해 제안한 column generation을 통한 알고리즘은 멀티 홉 MIMO 네트워크를 고려한 계층간 최적화 문제를 푸는데 적절함을 보였다.