On the Optimality of Rate Balancing for Max-Min Fair Multicasting

기술 요약: 최대-최소 공정성(Max-Min Fair) 멀티캐스팅을 위한 전송률 균형의 최적성에 관하여

문제 정의
본 논문은 다중 사용자 MISO(Multiple-Input Single-Output) 시스템의 다운링크에서 발생하는 최대-최소 공정성(Max-Min Fair, MMF) 멀티캐스팅 문제를 다룬다. 목표는 총 송신 전력 제약 조건 하에 모든 $K$ 명의 사용자에 대한 최소 신호 대 잡음비(SNR)를 최대화하는 공통 프리코딩 벡터를 설계하는 것이다. 저자들은 이 문제가 NP-난해(NP-hard) 문제임을 인정한다. 결과적으로, 기존의 최첨단 솔루션들은 일반적으로 내부 점법(interior-point methods, 예: CVX)을 통한 준정부호 완화(Semidefinite Relaxation, SDR), 교대 방향 승수법(ADMM), 또는 휴리스틱 반복 업데이트와 같은 차선책(suboptimal) 설계에 의존한다. 이러한 방법들은 최적해에 근접할 수는 있으나, 높은 계산 복잡도를 수반하거나 폐쇄형 해(closed-form solution)를 제공하지 못하는 경우가 많다. 더욱이, 기존 접근 방식들은 일반적으로 최적해의 구조적 특성, 특히 사용자 전송률 균형과 최적성 사이의 관계에 대해 조사하지 않는다.

방법론
저자들은 분수 계획법(Fractional Programming, FP)과 라그랑주 쌍대성(Lagrangian duality)에 기반하여 최적해를 분석적으로 도출하는 새로운 접근 방식을 제안한다.

1. 재구성: 원래의 비볼록(non-convex) 문제를 보조 변수($\beta_k$)를 사용하여 블록별 볼록(block-wise convex) 문제(P3)로 재구성한다.
2. KKT 분석: 저자들은 카루슈-쿤-터커(Karush-Kuhn-Tucker, KKT) 최적성 조건을 분석한다. 이들은 "활성(active)" 사용자 집합(최소 전송률을 가진 사용자)과 "비활성(inactive)" 사용자 집합(더 높은 전송률을 가진 사용자)을 정의한다.
3. 폐쇄형 해: 쌍대 함수를 유도하고 쌍대 변수에 대해 이를 최소화함으로써, 저자들은 최적의 프리코딩 벡터에 대한 폐쇄형 표현식을 얻는다. 이는 행렬 $D$(채널 벡터 및 보조 변수로부터 유도됨)와 벡터 $d$를 포함하는 선형 방정식 시스템을 푸는 과정을 포함한다.
4. 전송률 균형 등가성: 핵심적인 이론적 단계는 특정 조건 하에서 최적의 MMF 솔루션이 모든 사용자의 전송률(또는 유효 SNR)이 균형을 이루는 상태와 일치함을 증명하는 것이다.

주요 기여
본 논문은 세 가지 주요 기여를 개괄한다:

1. 이론적 유도: 저자들은 전송률 균형과 최적의 MMF 멀티캐스팅 솔루션 사이의 관계를 분석적으로 유도한다.
2. 저복잡도 알고리즘: 이러한 이론적 통찰을 바탕으로, CVX와 같은 반복적 볼록 최적화 솔버를 사용할 필요 없이 폐쇄형 해를 제공하는 알고리즘을 제안한다.
3. 최적성 조건: 전송률 균형이 최적해임이 보장되는 특정 조건을 확립한다. 구체적으로 정리 2(Theorem 2)는 $K$ 명의 채널 벡터가 선형 독립이고 $K \le M$($M$은 송신 안테나 수)인 경우, 균형 잡힌 전송률 솔루션이 최적임을 명시한다. 반대로, $K > 2M$인 경우에는 최적성을 위해 불균형한 전송률이 필요하다. 중간 사례인 $M < K \le 2M$의 경우, 최적성은 유도된 행렬 $A$의 계수(rank)에 따라 결정된다.

결과 및 논의
제안된 알고리즘("Algo RB")을 SDR 기반 방법(CVX Rand, CVX Relaxed), ADMM, 그리고 SNR 증가(SNR Inc.) 휴리스틱 방법과 비교 검증하기 위해 3GPP 채널 규격을 사용하여 수치 시뮬레이션을 수행하였다.

• 저부하 시나리오 ($M=10, K=5$): 제안된 알고리즘은 고복잡도 CVX 솔루션과 유사한 성능을 보이며, ADMM 및 SNR Inc.보다 약간 더 나은 성능을 보인다. 이 영역에서 결과는 모든 최적해가 균형 잡힌 사용자 SNR을 생성함을 확인시켜 준다.
• 과부하 시나리오 ($M=8, K=10$): $K > M$임에도 불구하고, 특정 채널 실현(realization) 결과 행렬 $D$가 가역(invertible)이었기에, 활성 사용자 부분집합을 탐색할 필요 없이 제안된 알고리즘을 직접 적용할 수 있었다. 여기서 제안된 알고리즘은 고복잡도 CVX Rand를 포함한 다른 모든 방법을 능가하였다.
• 전송률 균형 검증: 시뮬레이션은 휴리스틱 방법(ADMM, SNR Inc.)이 최적에 가까운 최소 SNR을 달지만, 종종 불균형한 사용자 전송률을 초래한다는 것을 보여준다. 반면, 제안된 방법과 완화된 CVX 상한(upper bound)은 균형 잡힌 전송률을 달성하며, 이는 시스템 행렬이 가역적일 때 전송률 균형과 최적성 사이의 이론적 연결 고리를 확인시켜 준다.

의의 및 주장
저자들은 본 연구가 전송률 균형과 최적의 MMF 멀티캐스팅 솔루션 사이의 직접적인 연결을 확립한 첫 번째 연구라고 주장한다. 본 연구의 의의는 NP-난해 문제를 실제적인 조건(특히 선형 독립 채널인 $K \le M$인 경우) 하에서 폐쇄형 해를 갖는 저복잡도 알고리즘으로 변환했다는 데 있다. 이는 안테나 수가 사용자 수보다 많은 경우가 많은 매시브 MIMO(massive MIMO) 시스템의 산업적 추세에 비추어 볼 때 매우 중요하다. 저자들은 향후 연구에서 $K > M$이고 행렬 $D$가 가역적이지 않은 경우의 효율적인 활성 사용자 집합 식별 방법과, 공선적(collinear) 채널을 다루는 문제를 다룰 것이라고 겸허히 언급하였다.