사용자 스케줄링 알고리즘편집자 확인

사용자 스케줄링 알고리즘은 무선 통신 시스템에서 제한된 무선 자원을 다수의 사용자에게 효율적으로 할당하는 절차와 규칙을 말한다. 이 알고리즘은 기지국이 특정 시간과 주파수 자원을 어떤 사용자에게 우선적으로 배정할지 결정하는 핵심적인 역할을 한다. 주로 셀룰러 네트워크의 다운링크에서 적용되며, LTE, 5G, 그리고 향후 6G와 같은 이동 통신 표준의 성능을 좌우하는 중요한 요소이다.

사용자 스케줄링의 기본 목적은 시스템 전체의 처리량을 최대화하거나, 사용자 간의 공정성을 유지하거나, 특정 사용자의 서비스 품질을 보장하는 것이다. 이러한 목표들은 서로 상충관계에 있기 때문에, 네트워크 운영자의 정책과 서비스 요구사항에 따라 다양한 알고리즘이 설계되고 적용된다. 예를 들어, 최대 처리량을 추구하는 알고리즘은 채널 상태가 좋은 사용자에게만 자원을 집중시킬 수 있어 공정성이 떨어지는 반면, 균등한 기회를 주는 알고리즘은 전체 시스템 효율을 저하시킬 수 있다.

사용자 스케줄링의 효율성은 채널 상태 정보(CSI)의 정확성과 적시성에 크게 의존한다. 사용자는 주기적으로 또는 요청에 따라 자신의 채널 품질을 기지국에 보고하며, 스케줄러는 이 정보를 바탕으로 최적의 자원 할당 결정을 내린다. 또한, 최근에는 음성 통화나 실시간 비디오 스트리밍과 같은 실시간 트래픽과 웹 브라우징이나 파일 다운로드와 같은 비실시간 트래픽을 동시에 처리하면서 각각의 서비스 품질 요구사항을 만족시키는 것이 중요한 과제가 되었다.

스케줄링은 제한된 통신 자원을 여러 사용자에게 효율적으로 할당하는 과정이다. 무선 네트워크에서 이 자원은 일반적으로 시간, 주파수, 공간, 전력 등을 의미한다. 스케줄링 알고리즘은 이러한 자원을 어떤 사용자에게, 얼마나, 언제 할당할지를 결정하는 일련의 규칙이다.

스케줄링의 주요 목표는 시스템 전체의 성능을 최적화하는 것이다. 이를 평가하는 대표적인 성능 지표로는 총 처리량, 셀 에지 사용자 처리량, 공정성, 지연, 패킷 손실률 등이 있다. 총 처리량은 단위 시간당 시스템이 성공적으로 전송할 수 있는 데이터의 총량을 의미하며, 네트워크 용량을 나타내는 핵심 지표이다. 공정성은 모든 사용자가 최소한의 서비스 수준을 보장받는 정도를 말하며, 셀 에지 사용자 처리량은 기지국에서 멀리 떨어진 사용자의 성능을 개선하는 데 중점을 둔다. 이러한 지표들은 서로 상충 관계에 있어, 알고리즘 설계 시 균형을 고려해야 한다.

사용자 스케줄링은 특히 무선 채널 환경에서의 특수성을 가진다. 유선 네트워크와 달리, 무선 채널 상태는 페이딩, 간섭, 사용자의 이동성 등으로 인해 시간과 공간에 따라 급격히 변한다. 따라서 알고리즘은 사용자별로 실시간으로 측정된 채널 상태 정보를 반드시 고려해야 한다. 또한, 각 사용자의 서비스 요구 사항도 다르다. 예를 들어, 파일 다운로드와 같은 비실시간 트래픽과 화상 통화와 같은 실시간 트래픽은 요구하는 대역폭과 지연 허용치가 크게 다르다.

결국, 효과적인 사용자 스케줄링 알고리즘은 변동하는 채널 조건, 다양한 성능 지표, 그리고 상이한 서비스 품질 요구사항 사이에서 최적의 자원 할당 결정을 내리는 것을 목표로 한다. 이는 단순히 자원을 나누는 것을 넘어, 네트워크의 전체 효율성과 사용자 경험을 결정하는 핵심 기능이다.

라운드 로빈 스케줄링은 시간을 일정한 단위(타임 슬롯)로 나누어 모든 활성 사용자에게 순차적으로 자원을 할당하는 방식이다. 이 방식은 모든 사용자에게 균등한 전송 기회를 보장하여 공평성을 높이는 장점이 있다. 그러나 각 사용자의 채널 상태 정보나 데이터 요구량을 고려하지 않기 때문에, 채널 상태가 나쁜 사용자에게 자원이 할당될 경우 시스템 전체의 스펙트럼 효율이 크게 저하될 수 있다. 따라서 처리량 최적화보다는 간단한 구현과 공정성 보장이 중요한 환경에서 주로 사용된다.

최대 C/I 스케줄링은 매 순간 가장 좋은 채널 상태(가장 높은 신호 대 간섭 잡음비)를 가진 단일 사용자에게 모든 자원을 할당하는 방식이다. 이 방식은 시스템의 총 처리량을 극대화할 수 있다는 장점이 있다. 그러나 채널 상태가 지속적으로 좋은 사용자(예: 기지국 근처 사용자)가 자원을 독점하게 되어, 채널 상태가 상대적으로 나쁜 사용자(예: 셀 경계 사용자)는 기아 상태에 빠질 수 있다. 이로 인해 공평성이 매우 낮아지는 단점이 있다.

비례 공정 스케줄링은 최대 C/I의 처리량 극대화와 라운드 로빈의 공평성을 절충한 알고리즘이다. 이 알고리즘은 각 사용자의 현재 즉시 가능한 전송률(현재 채널 상태에 기반)과 과거 평균 전송률의 비율을 메트릭으로 계산하여, 이 값이 가장 큰 사용자를 선택한다. 수식으로 표현하면 사용자 *i*의 우선순위는 *R_i(t) / T_i(t)*로 결정된다[2]. 이 방식을 통해 채널 상태가 좋을 때 우선 전송할 기회를 주면서도, 장기적으로는 모든 사용자에게 공정한 서비스 기회를 제공한다. 결과적으로 시스템 처리량과 사용자 간 공평성 사이에 좋은 균형을 달성한다.

다양한 네트워크 환경과 서비스 요구사항에 따라 이들 기본 알고리즘을 변형하거나 혼합하여 사용한다. 예를 들어, 지연에 민감한 트래픽을 처리하기 위해 대기 시간을 우선순위 메트릭에 반영하거나, 다중 사용자 MIMO 환경에서 여러 사용자를 동시에 스케줄링하기 위해 그룹 기반 알고리즘을 적용하기도 한다.

채널 상태 정보는 사용자 스케줄링 알고리즘의 핵심 입력 요소로, 무선 채널의 품질을 정량화한 데이터이다. 이 정보는 주로 사용자 단말기가 기지국으로 피드백하며, 신호 대 잡음비(SNR)나 채널 용량과 같은 지표로 표현된다. 스케줄러는 이 CSI를 바탕으로 어떤 사용자에게 어떤 시간-주파수 자원을 할당할지 결정한다. 정확하고 시의적절한 CSI는 네트워크의 전반적인 스펙트럼 효율과 사용자 경험 품질을 크게 좌우한다.

CSI의 활용 방식은 알고리즘의 목표에 따라 달라진다. 최대 C/I(Max C/I) 스케줄링은 단순히 현재 채널 상태가 가장 좋은 사용자를 선택하여 시스템 처리량을 극대화한다. 반면, 비례 공정(Proportional Fair) 스케줄링은 현재 채널 상태와 과거 평균 전송률을 함께 고려한다. 이는 채널이 좋은 사용자에게만 유리하게 자원이 편중되는 현상을 완화하면서도 전체 시스템 처리량을 높이는 균형 잡힌 방식을 제공한다.

CSI의 정확성과 피드백 오버헤드 사이에는 트레이드오프 관계가 존재한다. 더 자주, 더 세밀하게 채널 정보를 보고하면 스케줄링 정확도는 높아지지만, 상향링크 자원을 많이 소모하고 보고 지연이 발생할 수 있다. 따라서 현실 시스템에서는 채널 상태 예측, 압축 피드백, 피드백 주기 조절 등의 기법을 사용하여 오버헤드를 관리한다. 또한 다중 사용자 MIMO(MU-MIMO) 기술에서는 사용자 간 간섭을 최소화하기 위해 더 정교한 채널 행렬 정보가 필요하다.

다중 사용자 MIMO는 하나의 기지국이 동일한 시간-주파수 자원을 사용하여 여러 사용자에게 동시에 데이터를 전송하는 기술이다. 이 기술의 핵심은 공간 다중화를 통해 시스템 용량을 극대화하는 데 있다. 다중 사용자 MIMO 스케줄링은 이러한 동시 전송을 가능하게 하는 사용자 그룹을 선택하고, 각 사용자에게 적절한 빔포밍 가중치를 할당하는 과정을 포함한다. 스케줄러는 사용자 간의 채널 상태 정보와 상관관계를 분석하여, 서로 간섭이 적고 채널 조건이 양호한 사용자들을 한 조로 묶는 작업을 수행한다.

주요 스케줄링 알고리즘으로는 제로 포싱 기반의 방법이 널리 사용된다. 이 방법은 특정 사용자에 대한 신호를 전송할 때, 다른 사용자에게는 신호가 전달되지 않도록(간섭이 '0'이 되도록) 빔포밍 벡터를 설계한다. 이를 통해 사용자 간 간섭을 사전에 제거하거나 최소화한다. 스케줄링의 목표는 주로 시스템의 총 처리량을 최대화하거나, 모든 사용자에게 공정한 서비스 기회를 제공하는 것이다. 사용자 선택은 다음 표와 같은 요소를 고려하여 이루어진다.

실제 시스템에서는 이상적인 조건과 달리 완벽한 채널 정보를 얻기 어렵고, 사용자 수가 많을수록 최적의 사용자 조합을 찾는 계산 복잡도가 기하급수적으로 증가한다. 따라서 복잡도를 줄이기 위해, 채널 이득이 임계값을 넘는 사용자들을 먼저 선별하거나, 채널 방향이 서로 가장 직교하는 소수의 사용자를 탐욕 알고리즘 방식으로 선택하는 등의 휴리스틱 방법이 적용된다. 이러한 스케줄링은 LTE Advanced와 5G NR 시스템의 핵심 기술로 자리 잡아, 셀당 서비스 가능 사용자 수와 데이터 전송률을 크게 향상시켰다.

에너지 효율적 스케줄링은 무선 통신 시스템에서 주어진 성능 목표를 달성하면서도 전체 시스템의 에너지 소비를 최소화하거나, 제한된 에너지 자원(예: 배터리 구동 기지국 또는 사용자 단말) 하에서 가능한 최대 성능을 제공하는 것을 목표로 한다. 이는 지속 가능한 네트워크 운영과 사용자 장치의 배터리 수명 연장이라는 두 가지 측면에서 중요성을 갖는다. 특히 그린 네트워크 구축과 에너지 할당 문제의 핵심 과제로 부상했다.

주요 접근 방식은 전송 전력, 대역폭, 시간 슬롯과 같은 자원을 사용자에게 할당하는 정책을 설계하여 에너지 효율성을 극대화하는 것이다. 일반적인 기법으로는 채널 상태가 좋은 사용자에게 우선적으로 자원을 할당하여 동일한 데이터량을 더 낮은 전력으로 전송하게 하거나, 불필요한 전송을 줄이기 위해 비활성 기간을 최적화하는 것이 포함된다. 또한, 기지국의 동적 셀 크기 조절이나 슬립 모드 운영과 같은 네트워크 수준의 에너지 관리 정책과 연계되기도 한다.

에너지 효율성을 정량화하는 주요 지표는 비트당 에너지 소비량 또는 처리량 대 전력 소비 비율(예: bits/Joule)이다. 알고리즘 설계 시에는 스펙트럼 효율성과 에너지 효율성 사이의 트레이드오프 관계를 고려해야 한다. 최적화 문제는 종종 복잡한 비볼록 문제로, 휴리스틱 방법이나 분산형 알고리즘을 통해 근사해를 구한다. 최근 연구는 재생 에너지원을 활용하는 기지국의 에너지 수확 패턴을 스케줄링에 반영하는 방향으로 확장되고 있다[5].

실시간 트래픽은 음성 통화, 영상 통화, 실시간 게임과 같이 엄격한 지연 시간 요구사항을 가지는 데이터 흐름을 의미한다. 반면, 비실시간 트래픽은 파일 다운로드, 이메일, 웹 브라우징과 같이 상대적으로 느슨한 지연 허용 범위를 가진 트래픽을 말한다. 사용자 스케줄링 알고리즘은 이렇게 서로 다른 특성을 가진 트래픽이 동일한 무선 자원을 공유할 때, 각 서비스의 요구사항을 만족시키면서 전체 시스템 효율을 최적화하는 역할을 한다.

이를 위해 QoS(Quality of Service) 보장 기법이 적용된다. 대표적인 방법으로는 트래픽 분류와 우선순위 큐잉이 있다. 스케줄러는 패킷의 헤더 정보를 분석하여 트래픽 유형을 분류하고, 미리 정의된 규칙에 따라 서로 다른 대기열에 배치한다. 실시간 트래픽은 일반적으로 높은 우선순위 큐에 할당되어 자원 할당 시 우선적으로 고려된다. 또한, 지연 보장을 위해 최대 지연 시간이나 지연 변이와 같은 파라미터를 스케줄링 결정에 반영하는 알고리즘[6]이 사용된다.

비실시간 트래픽의 처리에는 공평성과 처리량이 더 중요한 목표가 된다. 비례 공정(Proportional Fair) 스케줄링과 같은 알고리즘은 채널 조건이 좋은 사용자에게 우선적으로 자원을 할당하면서도, 장기적으로 모든 사용자가 최소한의 서비스 수준을 유지하도록 설계되어 비실시간 트래픽에 적합하다. 때로는 남는 자원을 비실시간 트래픽에 할당하는 베스트 에포트 방식이 활용되기도 한다.

효율적인 트래픽 처리를 위해 하이브리드 스케줄러가 자주 설계된다. 이는 실시간 트래픽에 대해 절대적인 지연 제약을 만족시키는 스케줄링(예: 지연 기반)과, 나머지 자원을 비실시간 트래픽 사용자들에게 처리량이나 공평성을 고려하여 할당하는 스케줄링(예: 처리량 기반)을 결합한 방식이다. 네트워크 운영자는 서비스 수준 계약에 따라 각 트래픽 클래스별로 최소 보장 속도, 최대 지연, 패킷 손실률 등의 목표를 설정하고, 스케줄러는 이러한 목표를 달성하도록 동작한다.

최근 사용자 스케줄링 알고리즘 연구는 무선 채널의 복잡성을 더 정교하게 모델링하고, 네트워크 요구사항의 다양성에 적응하는 방향으로 진화하고 있다. 전통적인 알고리즘은 주로 신호 대 간섭 잡음비(SINR)나 공정성 같은 단일 또는 소수의 메트릭에 기반했으나, 현대의 이종 트래픽과 서비스 품질 요구를 충족시키기 위해 다목적 최적화와 상황 인지형 접근법이 강조되고 있다. 특히, 네트워크 슬라이싱 환경에서 각 슬라이스의 독립적인 QoS(Quality of Service)를 보장하면서 전체 시스템 효율을 극대화하는 지능형 스케줄러 설계가 주요 과제로 부상했다.

머신러닝, 특히 심층 강화 학습(Deep Reinforcement Learning)을 적용한 연구가 활발히 진행되고 있다. 이 방법은 시간에 따라 변화하는 채널 상태, 트래픽 부하, 사용자 분포 등의 복잡한 환경에서 스케줄링 정책을 최적화할 수 있다. 알고리즘은 장기적인 누적 보상(예: 시스템 처리량, 지연, 에너지 효율의 조합)을 극대화하도록 학습하며, 기존의 휴리스틱 기반 방식이 처리하기 어려운 비선형적이고 고차원적인 문제를 해결하는 데 유망하다. 연구는 주로 에이전트(스케줄러)의 상태 정의, 행동 공간 설계, 보함 함수 설계에 초점을 맞추고 있다.

6G 네트워크로의 진전은 사용자 스케줄링에 새로운 패러다임을 요구한다. 초고신뢰 저지연 통신(URLLC), 대규모 기계형 통신(mMTC), 그리고 통합 감지 및 통신(ISAC)과 같은 서비스가 동시에 존재하는 환경에서 스케줄링은 더욱 유연하고 동적이어야 한다. 예를 들어, 테라헤르츠 대역이나 가시광 통신(VLC)과 같은 새로운 주파수 자원의 효율적 스케줄링, 그리고 위성-지상 통합 네트워크에서의 3차원적 사용자 배치를 고려한 스케줄링이 새로운 연구 영역으로 떠오르고 있다. 또한, 에너지 하베스팅 사용자를 위한 스케줄링이나 분산형 AI 모델 학습을 지원하는 자원 할당도 중요한 발전 방향이다.

• Wikipedia - 스케줄링 (컴퓨팅)

• Wikipedia - Process scheduler

• NAVER 지식백과 - 스케줄링 알고리즘

• KOCW - 운영체제 스케줄링

• GeeksforGeeks - CPU Scheduling in Operating Systems

• ScienceDirect - Scheduling Algorithms

• IEEE Xplore - A Survey of Scheduling Algorithms