Radio Resource Allocation for Beam Hopping Scheduling in LEO Satellite Communications: A Spatio-Temporal Perspective

기술 요약: LEO 위성 통신을 위한 빔 호핑 스케줄링의 무선 자원 할당

문제 정의
저궤도(LEO) 위성 네트워크는 동적인 트래픽 수요와 엄격한 간섭 제약 조건으로 인해 무선 자원 할당 측면에서 상당한 도전에 직면해 있습니다. 빔 호핑(Beam Hopping, BH) 기술은 공간 및 시간 영역 전반에 걸쳐 동적으로 빔 자원을 할당할 수 있게 함으로써 해결책을 제시합니다. 그러나 BH 스케킹 문제는 근본적으로 고차원 이산 조합 최적화 작업입니다. 이는 송신 전력, 대역폭 및 서비스 품질(QoS) 제약 조건 하에서 빔 활성화 시퀀스를 공동으로 최적화하고 간섭을 관리하는 것을 요구합니다. 기존 방식들은 다음과 같은 실질적인 한계에 부딪힙니다:

• 탐욕적 휴리스틱(Greedy Heuristics): 복잡도는 낮지만, 고정된 이웃 설계를 기반으로 하며 지역 최적점(local optima)에 빠지기 쉽습니다. 이는 다중 모드(multimodal) 지형에서 처리량, 공정성 및 간섭 사이의 균형을 맞추는 데 종종 실패합니다.
• 진화 알고리즘(Evolutionary Algorithms): 유전 알고리즘(GA)과 같은 방법은 전역 탐색 능력을 제공하지만, 계산 집약적일 수 있으며 수렴 속도 측면에서 어려움을 겪을 수 있습니다.
• 학습 기반 접근 방식(Learning-Based Approaches): 심층 강화 학습(DRL) 및 기타 지능형 알고리즘은 방대한 학습 데이터와 높은 계산 예산을 필요로 하며, 환경 변화(예: 궤도 역학 또는 트래픽 모델 변화)에 따른 해석 가능성과 일반화 능력이 부족한 경우가 많습니다.

방법론
본 논문은 시뮬레이티드 어닐링(Simulated Annealing, SA) 수용 기준이 통합된 2단계 생성-평가(generate-evaluate) 프레임워크를 사용하는 타부 탐색(Tabu Search, TS) 기반 시공간 BH 자원 할당 전략을 제안합니다. 방법론의 핵심 구성 요소는 다음과 같습니다:

1. 문제 정식화: BH 스케줄링 문제를 스케줄링 기간 동안 총 공급 용량과 사용자 수요 사이의 제곱 차이를 최소화하여 사용자 수요 충족을 극대화하도록 모델링하며, 이는 간섭 거리 제약 및 동시에 활성화되는 빔 수($N_b$)의 제한을 준수해야 합니다.
2. 2단계 솔루션 프레임워크:
   • 1단계 (타당성 및 초기화): 초기 타당한 솔루션은 탐욕적 휴리스틱을 사용하여 구축됩니다. 이 과정은 잔여 트래픽 수요가 높은 셀을 우선시하는 동시에, 위성 내 간섭 거리 제약(활성 빔이 최소 임계값 $D_{thr}$ 이상 떨어져 있도록 보장)을 엄격히 준고합니다.
   • 2단계 (효과성 및 최적화): 알고리즘은 특정 최적화 목표(예: 커버리지-처리량-공정성 트레이드오프)에 맞춤화된 이웃 탐색 및 선택을 수행합니다.
3. 주요 알고리즘 혁신:
   • 적응형 타부 테너 제어(Adaptive Tabu Tenure Control): 고정된 파라미터의 타부 리스트와 달리, 테너 길이($L_{tabu}$)는 문제의 차원($N_b \times N_m$)에 따라 동적으로 구성됩니다. 이를 통해 탐색 강도를 문제 크기에 따라 확장할 수 있어, 탐색(exploration)과 이용(exploitation) 사이의 균형을 맞출 수 있습니다.
   • 확률적 수용 (시뮬레이티드 어닐링): 조기 수렴과 탐색 정체를 방지하기 위해, 본 방법은 SA 수용 기준을 통합합니다. 이는 알고리즘이 "더 나쁜" 솔루션을 확률적으로 수용할 수 있게 하여, 지역 최적점에서 벗어나 사용자 커버리지와 시변 트래픽 수요 사이의 균형을 개선하도록 돕습니다.
   • 이웃 이동 전략(Neighborhood Move Strategy): 알고리즘은 우선순위 기반 및 간섭 회피 휴리스틱에 의해 유도되는 무작위 빔 개수 및 무작위 빔 인덱스 전략을 사용하여 후보 솔루션을 생성합니다.

주요 기여
본 논문은 세 가지 주요 기여를 주장합니다:

1. 시공간 자원 할당 체계: 문제 크기에 따라 탐색 강도를 조절하여 수동 파라미터 튜닝에 대한 의존도를 줄이는 문제 크기 적응형 타부 테너 제어 메커니즘을 도입했습니다.
2. 2단계 생성-평가 프레임워크: 타당성(간섭 인지 초기화)과 효과성(목표 인지 이웃 탐색)을 분리하는 구조적 접근 방식을 통해, 로컬 탐색 효율성과 전역 탐색 가능성 사이의 균형을 보장합니다.
3. 강건성 및 해석 가능성: 제안된 방식은 환경 변화(궤도 역학, 트래픽 변화)에 더 강건하도록 설계되었으며, 블랙박스 학습 모델에 비해 명확한 결정 로직을 제공하는 동시에 엔드 투 엔드 학습 대비 데이터 및 계산 요구량을 줄입니다.

결과
제안된 TS+SA 방법과 GBH-AIC(간섭 제어가 포함된 탐욕적 빔 호핑) 및 GBH-WIC(간섭 제어가 없는 탐욕적 빔 호핑), 그리고 GA 베이스라인을 비교하기 위해 광범위한 시뮬레이션을 수행했습니다. 결과는 다음과 같습니다:

• 처리량: 제안된 방법은 GBH-AIC 대비 17.2%, GA 대비 6.5% 향상된 시스템 처리량을 보여주었습니다.
• 사용자 만족도: 서비스 만족도는 GBH-AIC 대비 11.7%, GA 대비 4.4% 증가했습니다.
• 링크 품질: 본 방법은 더 높은 평균 SINR(GA의 9.7 dB 대비 10.2 dB)을 달와냈으며, 중단율(outage rate)을 베이스라인보다 현저히 낮은 **2.3%**로 감소시켰습니다.
• 강건성: 제안된 방법과 탐욕적 베이스라인 간의 성능 격차는 편향된 트래픽 분포(예: 파레토 80/20 법칙) 하에서 더 넓어졌으며, 여기서 제안된 방법은 탐욕적 베이스라인 대비 **36.7%**의 처리량 개선을 보여주며 이질적인 수요를 처리하는 탁월한 능력을 입증했습니다.
• 복잡도: 알고리즘은 합리적인 계산 오버헤드(표준 CPU에서 스케줄링 주기당 약 5초)를 유지하여, 40ms 타임 슬롯을 가진 오프라인 계산에 적합합니다.

의의
본 논문은 간섭 제한이 있는 LEO 위성 네트워크의 동적 자원 할당을 위한 실질적인 솔루션을 제시합니다. 이는 휴리스틱의 단순성, 진화 알고리즘의 전역 탐색 능력, 그리고 학습 기반 방식의 데이터 집약적 특성 사이의 트레이드오프를 다룹니다. 타부 탐색의 메모리 메커니즘과 시뮬레이티드 어닐링의 확률적 탈출 능력을 결격함으로써, 제안된 프레임워크는 BH 스케줄링을 위한 확장 가능하고 강건하며 해석 가능한 접근 방식을 제공합니다. 저자들은 이 전략이 로컬 최적화 효율성과 전역 탐색 가능성 사이의 균형을 효과적으로 맞추며, 딥러닝과 관련된 높은 계산 및 데이터 비용 없이도 미래의 지능형 BH 제어 시스템을 위한 실행 가능한 대안을 제공한다고 결론짓습니다.