Long-Horizon Wireless Link Scheduling with State-Augmented Graph Neural Networks

기술 요약: 상태 증강 그래프 신경망을 이용한 장기 호라이즌 무선 링크 스케줄링

문제 정의
본 논문은 대규모 디바이스 간(device-to-device) 무선 네트워크에서의 최적 링크 스케줄링 문제를 다룬다. 목표는 시간 호라이즌 $T$ 동안 장기 평균 합계 전송률(sum rate)을 최대화하는 동시에, 모든 링크 $i$가 최소 평균 전송률 요구사항 $\Delta_i$를 달一个하도록 하는 것이다. 실시간 합계 전송률 극대화에 집중하는 전통적인 접근 방식과 달리, 이 문제는 시간적 제약을 충족하고 간섭을 피하기 위해 시변(time-varying) 정책을 필요로 한다.

네트워크는 두 링크가 공통의 디바이스를 공유할 때 서로 간섭한다는 기본 간섭 모델 하에 모델링되며, 이는 인접 행렬 $A$를 가진 충돌 그래프 $G(V, E)$로 표현된다. 스케줄링 문제는 결정 변수가 각 타임 슬롯 $t$에 대한 이진 벡터 $s(t) \in \{0, 1\}^K$인 제약된 조합 최적화 문제(식 3)로 정식화된다. 전체 탐색 공간은 링크의 수 $K$와 시간 호라이즌 $T$의 곱에 대해 조합적으로 증가하므로, 대규모 네트워크에서 정확한 해를 찾는 것은 계산적으로 불가능하다.

방법론
저자들은 라그랑주 쌍대성(Lagrangian duality)과 상태 증강(state augmentation)에 기반한 학습 기반 접근 방식을 제안한다. 방법론은 세 가지 주요 이론적 및 실무적 단계로 진행된다:

1. 쌍대 영역 분석 및 원 문제의 불가능성(Primal Infeasibility):
   저자들은 먼저 라그랑주 쌍대를 사용하여 문제를 분석한다. 그들은 고정된 쌍대 변수 $\lambda$에 대한 라그랑주 극대화값이 시불변(time-invariant)임을 입증한다(명제 1). 즉, 최적의 스케줄 $s^\dagger(t, \lambda)$는 시간에 따라 변하지 않는다. 결과적으로, 단일 최적 쌍대 변수 $\lambda^\star$로부터 유도된 정적 정책은 간섭을 피하기 위해 전송을 교대로 수행하지 못하므로, 모든 링크의 최소 전송률 요구사항을 동시에 만족시킬 수 없다. 이는 단일 최적 $\lambda^\star$와 그에 대응하는 정적 스케줄을 찾는 표준적인 원-쌍대(primal-dual) 접근 방식이 장기 호라이즌 문제에는 불충분함을 보여준다.

2. 쌍대 경사 하강법 역학(Dual Gradient Descent Dynamics):
   시불변의 한계를 극복하기 위해, 본 논문은 쌍대 경사 하강법 역학을 조사한다. 알고리즘은 제약 위반(서브그레이디언트)에 따라 쌍대 변수 $\lambda(u)$를 반복적으로 업데이트하고, 각 단계에서 그에 대응하는 라그랑주 극대화값 $s^\ddagger(u)$를 계산함으로써 일련의 스케줄(sequence of schedules)을 생성한다. 이론적 분석(명제 3)에 따르면, 이 수열 내의 개별 스케줄은 최적이 아닐 수 있지만, 수열 $s^\ddagger(1:T)$의 평균 전송률은 $T \to \infty$일 때 점근적으로 최적이며 실행 가능하다. 이는 장기 호라이즌 문제의 해법이 쌍대 경사 하강법의 궤적을 모방하는 정책을 학습하는 데 있음을 시사한다.

3. 상태 증강 그래프 신경망(State-Augmented Graph Neural Networks, SAGNN):
   매 단계마다 NP-난해(NP-hard)인 라그랑주 극대화를 해결하지 않고 이를 효율적으로 구현하기 위해, 저자들은 그래프 신경망(GNN)을 사용하는 파라미터화된 정책 $\Phi(A, \lambda; H)$를 제안한다.

• 상태 증강: 핵심 혁신은 네트워크 토폴로지 $A$와 함께 쌍대 변수 $\lambda(t)$를 GNN의 내부 상태(또는 입력 신호)로 취급하는 것이다. 이를 통해 정책은 현재의 제약 위반 수준에 따라 스케줄링 결정을 동적으로 조정할 수 있다.
• 학습 (오프라인): GNN 파라미터 $H$는 다양한 네트워크 토폴로지와 쌍대 변수 분포에 대해 순시 라그랑지안 $M(s, \lambda)$를 최대화하도록 오프라인에서 학습된다. 손실 함수는 샘플링된 $\lambda$에 의해 가중치가 부여된 제약 위반을 처벌한다.
• 실행 (온라인): 실행 단계에서 학습된 GNN은 현재 네트워크 상태 $A$와 현재 쌍대 변수 $\lambda(t)$를 기반으로 스케줄 $s(t)$를 생성한다. 이후 쌍대 변수는 제약 위반의 서브그레이디언트(식 21)를 사용하여 온라인으로 업데이트되며, 이는 쌍대 경사 하강법 역학을 모방하는 폐루프(closed-loop) 시스템을 형성한다.

주요 기여

• 이론적 통찰: 본 논문은 최적의 라그랑주 극대화값은 시불변하여 제약된 장기 호ри즌 문제에 부적합하지만, 쌍대 경사 하강법에 의해 생성된 극대화값의 '수열'은 점근적으로 최적의 평균 전송률을 제공한다는 점을 확립하였다.
• 알고리즘 설계: 저자들은 라그랑주 극대화값을 근사하도록 학습되는 상태 증강 GNN(SAGNN)을 도입하였다. 쌍대 변수를 동적 입력으로 포함함으로써, 정책은 시간에 따라 스케줄링 결정을 변화시켜 제약 만족과 성능 극대화 사이의 균형을 효과적으로 맞추는 법을 배운다.
• 확장성: 이 접근 방식는 학습 파라미터화 과정에서 시간 호라이즌 $T$의 복잡성을 분리한다. GNN은 단일 타임 스텝에 대한 매핑을 학습하므로, 길이 $T$의 수열을 직접 학습해야 하는 계산적 난제를 피할 수 있다.

결과
약 500개의 링크를 가진 랜덤 기하 그래프(Random Geometric Graphs, RGGs)를 대상으로 광범위한 수치 시뮬레이션을 수행하였다.

• 제약 만족: 제안된 알고리즘은 대다수의 링크에 대해 최소 전송률 제약을 성공적으로 만족시킨다. 스케줄링이 부족한 소수의 링크에서도 제약 위반은 미미한 수준이다.
• 성능: 이 방법은 평균 합계 전송률 측면에서 여러 베이스라인 휴리스틱보다 우수한 성능을 보였으며, 더 빠른 실행 시간을 달성했다.
• 일반화: 학습된 정책은 다양한 전송 요구사항에 대해 강건함을 보이며 효과적으로 적응하는 일반화 능력을 입증하였다. 정책은 쌍대 변수가 진화함에 따라 제약 위반 수준이 높은 링크를 우선시하며 비간섭 링크 간의 교대 전송을 성공적으로 수행한다.

의의 및 주장
본 논문의 주요 의의는 쌍대 경사 하강법의 이론적 최적성과 효율적인 학습 기반 스케줄링 정책의 실무적 필요성 사이의 간극을 메우는 데 있다. 저자들은 표준적인 시불변 정책이나 직접적인 수열 학습(비용이 너무 많이 드는 방식)으로는 해결할 수 없는, 장기 호리즌 제약에 필요한 시변 정책을 학습하기 위해 상태 증강이 필수적인 기법임을 주장한다. 본 연구는 쌍대 역학을 모방하도록 학습하는 것이 고차원의 제약된 조합 최적화 문제를 계산 효율성을 유지하면서 해결할 수 있음을 검증하였다.