💻 computer science

WASP: Adaptive Weighted Multi-Objective Scheduling in UAV-Assisted Edge Computing

본 논문은 적응형 부하 기반 스코어링과 강건한 작업 수락 정책을 통해 이익, 지연 시간, 에너지 및 안전 목표를 동적으로 균형 있게 조절하는 경량화된 학습 불필요 온라인 스케줄링 프레임워크인 WASP를 제안하며, 기존의 최첨단 방법들과 비교하여 UAV 지원 엣지 컴퓨팅 환경에서 우수한 성능을 입증한다.

원저자: Moslem Kaviani, Keyhan Khamforoosh

게시일 2026-10-07

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Moslem Kaviani, Keyhan Khamforoosh

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

현대 컴퓨팅의 세계에서, 무거운 처리 작업들이 거대한 중앙 집중형 데이터 센터를 떠나 이를 생성하는 기기들에 더 가까이 이동함에 따라 조용한 혁명이 일어나고 있습니다. 에지 컴퓨팅(edge computing)이라고 알려진 이러한 변화는 더 빠른 응답을 가능하게 하고 먼 곳에 있는 네트워크의 부담을 줄여줍니다. 그러나 무인 항공기, 즉 드론이 비행하는 서버 역할을 하게 되면서 새로운 차원의 복잡성이 등장했습니다. 드론은 재난 지역이나 외딴 농장 상공에 머물며 컴퓨로 파워가 존재하지 않는 곳에 연산 능력을 제공하는 놀라운 유연성을 제공합니다. 하지만 이들은 독특하고 어려운 과제에 직면해 있습니다. 바로 제한된 배터리로 구동되며, 속도에 대한 욕구, 이윤에 대한 갈망, 그리고 비행 중 배터리가 방전되지 않아야 한다는 엄격한 요구 사항 사이에서 균형을 맞추는 동시에, 어떤 작업을 처리할지, 얼마나 멀리 날아갈지, 그리고 언제 멈출지에 대해 순식간에 결정을 내려야 한다는 점입니다.

연구자들은 오랫동안 이러한 드론들이 상충하는 요구 사항들을 조율할 수 있는 규칙 세트를 만드는 데 어려움을 겪어 왔습니다. 전통적인 방법들은 종로 종종 수익 극대화나 에너지 최소화와 같이 단 하나의 목표에만 집중하곤 하는데, 이는 보통 다른 분야에서 문제를 일으킵니다. 수익만을 쫓는 시스템은 너무 멀리 날아가 전력이 바닥날 수 있고, 속도에만 집중하는 시스템은 가치 있는 작업들을 무시할 수 있습니다. 이를 해결하기 위해 한 컴퓨터 과학자 팀은 WASP라고 불리는 새로운 스케줄링 프레임워크를 개발했습니다. 이 시스템은 수년간의 훈련이 필요한 복잡한 학습 알고리즘에 의존하는 대신, 시스템이 얼마나 바쁜지에 따라 실시간으로 우선순위를 변경하는 스마트하고 적응적인 규칙 세트를 사용합니다.

WASP의 핵심 아이디어는 단순하면서도 효과적입니다. 드론의 행동은 작업량에 따라 변화해야 한다는 것입니다. 시스템이 한산하고 드론의 배터리가 충분할 때, 스케줄러는 가장 많은 이익을 가져다주는 작업을 우선시합니다. 그러나 대기 중인 작업의 수가 늘어나고 시스템이 혼잡해지면, 스케줄러는 자동으로 초점을 바꿉니다. 시스템이 밀리는 것을 방지하기 위해 더 가깝고 빠르게 완료할 수 있는 작업을 선택하며 속도와 근접성을 우선시하기 시작합니다. 이러한 동적 조정은 인간의 개입이나 사전 프로그래밍된 훈련 없이 발생하며, 드론이 변화하는 조건에 즉각적으로 반응할 수 있게 합니다.

공정성을 보장하기 위해, 이 시스템은 단 하나의 작업이라도 영원히 무시되는 것을 방지하는 메커니즘을 포함하고 있습니다. 만약 낮은 우선순위의 작업이 너무 여러 번 건너뛰어지면, 시스템은 해당 작업을 표시하고 드론이 이를 처리하도록 강제하여 어떤 작업도 무기한 기다리게 되지 않도록 보장합니다. 또한, 시스템은 엄격한 안전 마진을 갖추도록 설계되어, 드론이 안전하게 귀환할 수 있도록 항상 일정량의 배터리를 남겨두어 결코 완전히 바닥나지 않도록 합니다. 이러한 접근 방식은 경제적 목표, 속도, 그리고 안전이 모두 동시에 고려되는 균형 잡힌 환경을 만듭니다.

연구진은 여러 대의 드론과 지상 스테이션을 포함하는 광범위한 컴퓨터 시뮬레이션을 통해 이 새로운 방법을 테스트했습니다. 그들은 WASP를 현재 해당 분야에서 최고로 간주되는 일부 방법들을 포함한 7가지 기존 스케줄링 방법들과 비교했습니다. 결과는 WASP가 모든 경쟁자를 압도한다는 것을 보여주었습니다. WASP는 작업의 거의 95%를 마감 시한 내에 성공적으로 완료하면서도 54초가 조금 넘는 빠른 평균 응답 시간을 유지함으로써 가장 높은 종합 점수를 달아냈습니다. 이와 대조적으로, 이윤에 크게 집중했던 다른 방법들은 안전율이 현저히 떨어졌으며, 일부 드론은 에너지가 고갈되어 임무를 완수하지 못하기도 했습니다.

또한 연구는 WASP의 적응적인 특성이 성공의 핵심임을 밝혀냈습니다. 연구진이 배터리 크기가 변하거나 드론의 수가 변하는 등 다양한 조건 하에서 시스템을 테스트했을 때, WASP는 높은 성능을 유지하기 위해 전략을 일관되게 적응시켰습니다. WASP는 시스템이 심한 압박을 받는 상황에서도 드론을 안전하게 지키고 작업을 계속 진행할 수 있도록 관리했습니다. 연구진은 부하에 따라 우선순위를 변경하는 능력이나 기아(starvation) 현상을 방지하는 규칙과 같은 시스템의 특정 부분을 하나라도 제거하면 전체적인 성능이 저하된다는 것을 발견했습니다. 이는 이러한 특정 기능들의 조합이 비행 에지 컴퓨팅의 복잡한 현실을 다루는 데 필수적임을 확인시켜 주었습니다.

궁극적으로, 이 연구는 드론 함대가 과거의 실수로부터 배우기 위한 슈퍼컴퓨터 없이도 효과적으로 관리될 수 있음을 입증합니다. 순간에 맞춰 조정되는 명확하고 투명한 규칙 세트를 사용함으로써, 이 시스템은 이전의 방법들이 할 수 없었던 수준의 균형을 달 achieves 합니다. 연구 결과는 긴급 대응이나 공공 안전 모니터링과 같은 안전이 중요한 응용 분야에서, 이윤과 속도를 최적화하면서도 공정성과 안전을 보장하는 결정론적 접근 방식이 복잡한 학습 기반 대안보다 더 가능할 뿐만 아니라 우월하다는 것을 시사합니다. 연구진은 시스템이 서로 다른 목표를 실시간으로 평가하는 방식을 신중하게 조정함으로써, 역동적인 세계의 요구를 처리할 수 있는 견고하고 신뢰할 수 있는 비행 컴퓨터 네트워크를 구축하는 것이 가능하다는 것을 보여주었습니다.

기술 요약: WASP – UAV 지원 에지 컴퓨팅을 위한 적응형 가중치 다목적 스케줄링

1. 문제 정의

본 논문은 UAV 지원 에지 컴퓨팅 환경에서의 온라인 작업 스케줄링 문제를 다룹다. 이 시스템은 지상 스테이션의 IoT 장치들이 생성한 계산 작업을 처리하기 위해 이동형 에지 서버 역할을 하는 무인 항공기(UAV)를 포함한다. 핵심적인 어려움은 동적인 실시간 조건 하에서 상충하는 네 가지 목적을 동시에 최적화하는 것이다:

이익 극대화 (Profit Maximization): 작업 완료로부터 얻는 경제적 가치.
지연 시간 최소화 (Latency Minimization): 응답 시간 및 이동 지연 감소.
에너지 효율성 (Energy Efficiency): 제한된 UAV 배터리 용량 보존.
운용 안전성 (Operational Safety): 데드라인 준수 보장 및 배터리 고갈로 인한 UAV 실패 방지.

기존 방식들은 이러한 목적들을 효과적으로 균형 있게 조절하지 못한다는 비판을 받는다. 고전적인 휴리스틱(예: FCFS, Round Robin)은 유틸리티 인식이 부족하다. 최신 기법인 CECO(탄소 효율적 계산 오프로딩)와 LBO(Lyapunov-Benders 최적화)는 다른 요소들을 희생하면서 특정 단일 목적(예: 이익 또는 부하 분산)을 우선시하는 경향이 있어, 안전율 저하, 데드라인 미준수, 또는 다목적 맥락에서의 하위 파레토 프런트(sub-optimal Pareto fronts) 문제를 야기한다. 또한, 강화 학습과 같은 학습 기반 접근 방식은 광범적인 오프라인 훈련이 필요하며 해석 가능성이 부족하여, 안전이 중요한 UAV 배치 환경에서는 문제가 될 수 있다.

2. 방법론: WASP 프레임워크

저자들은 **WASP (Weighted Adaptive Scheduler for Profit and Speed)**를 제안한다. 이는 가볍고, 결정론적이며, 훈련이 필요 없는 온라인 스케줄링 프레임워크이다. WASP는 오프라인 훈련 없이 대신 폐쇄형 규칙(closed-form rules)과 실시간 시스템 상태 관측에 의존하여 작동한다.

2.1 시스템 모델

아키텍처: IoT 장치, 지상 스테이션(작업 소스), 그리고 이기종 UAV(계산 자원)로 구성된 3계층 시스템.
작업 모델: 작업은 독립적이고 분할 불가능하며, 도착 시간, 크기(MCycles), 데드라인, 기본 이익의 특성을 갖는다. 데드라인은 작업 크기와 긴급도에 따라 동적으로 결정된다.
제약 조건:
- 에너지 타당성: UAV가 이동 및 실행을 위한 충분한 배터리를 보유한 경우에만 작업 할당이 가능하다.
- 안전 예비량: 치명적인 비행 중 실패를 방지하기 위해 20%의 배터리 예비량을 강제하는 엄격한 제약 조건을 적용한다.
- 실패 역학: UAV는 배터리 고갈 및 시스템 혼잡과 상관관계가 있는 확률적 실패 위험에 직면에 한다.

2.2 핵심 메커니즘

WASP는 다목적 균형을 달성하기 위해 세 가지 상호 연결된 메커니즘을 통합한다:

부하 적응형 하이브리드 스코어링 (Load-Adaptive Hybrid Scoring):
- WASP는 네 가지 정규화된 구성 요소인 속도(실행 시간), 이익(시간당 가치), 거리(근접성), 긴급도(데드라인 근접성)를 기반으로 후보 작업에 대한 복합 점수를 계산한다.
- 적응형 가중치 부여: 이 구성 요소들에 할당되는 가중치는 실시간 **큐 부하 계수( $\rho$ $ρ$ )**의 선형 함수이다.
  - 경부하 (Light Load): 시스템은 이익을 우선시한다.
  - 중부하 (Heavy Load): 시스템은 지연 시간과 혼잡을 줄이기 위해 속도와 거리를 우선시하는 방향으로 전환한다.
- 이를 통해 재학습 없이도 문맥 인식형 트레이드오프를 수행할 수 있다.
2단계 타당성 인지 입실 제어 (Two-Stage Feasibility-Aware Admission Control):
- 1단계 (타당한 집합): 스케줄러는 먼저 데드라인 전에 완료 가능한 작업을 식별한다. 이 집합이 비어 있지 않으면, 가장 높은 복합 점수를 가진 작업을 선택한다.
- 2단계 (타당하지 않은 집합): 타당한 작업이 없는 경우(과부하 시), 스케줄러는 최소 지연(Least-Lateness) 규칙으로 전환하여 데드라인 대비 지연이 가장 적은 작업을 선택한다. 이는 UAV의 유휴 상태를 방지하고 처리량을 유지한다.
재입력 카운팅을 통한 기아 방지 (Starvation Prevention via Rejection Counting):
- 공정성을 보장하기 위해, WASP는 각 작업에 대한 **재입력 카터(rejection counter)**를 추적한다. 특정 작업이 반복적으로 건너뛰어지면(임계값 = 2), 해당 작업은 "기아(starved)" 상태로 표시된다.
- 기아 상태의 작업은 일반적인 스코어링 로직을 우회하여, 다른 기아 후보들 사이에서 최단 작업 우선(SJF) 규칙을 사용하여 스케줄링된다. 이는 알고리즘의 결정론적 특성을 해치지 않으면서 대기 시간을 유계(bounded)로 보장한다.

3. 주요 기여

본 논문은 다음과 같은 구체적인 기여를 주장한다:

지속적 적응형 가중치 부여: 큐 부하에 따라 가중치가 동적으로 조정되는 4차원 스코어링 함수를 통해, 오프라인 훈련 없이도 이익, 속도, 근접성, 긴급도 간의 트레이드오프를 가능하게 한다.
2단계 입실 제어: 데드라인 준수가 가능한 작업을 우선시하되, 과부하 시에도 최소 지연 작업을 선택함으로써 처리량을 유지하는 정책을 통해, 타당성 전용 정책 대비 종합 성능을 2.4% 향상시킨다.
경량 기아 방지: 대기 시간을 유계로 보장하기 위해 재입력 카운터를 사용하는 제로 오버헤드 메커니즘을 제공하며, 이는 CECO 및 LBO를 포함한 기존 베이스라인에는 없는 기능이다.
통합 에너지 인식 타당성: 20%의 하드 예비량을 강제하는 2계층 배터리 관리 체계를 통해, 경쟁력 있는 이익을 유지하면서도 안전한 고갈을 방지한다.
엄격한 평가 프레임워크: 6개의 지상 스테이션과 10개의 이기종 UAV를 포함하는 재현 가능한 시뮬레이션 환경을 통해 파레토 프런트 분석, 하이퍼볼륨 계산, 통계적 유의성 검정(Bonferroni 교정을 적용한 Kruskal-Wallis)을 사용하여 WASP를 7개의 베이스라인과 비교하였다.

4. 실험 결과

저자들은 6개의 지상 스테이션과 10개의 이기종 UAV를 포함하는 30회의 독립적인 시뮬레이션 실행을 통해 WASP를 평가하였다.

4.1 비교 성능

WASP는 **가장 높은 종합 점수(0.790)**를 기록하며 8개의 알고리즘 중 1위를 차지했다. 주요 지표는 다음과 같다:

데드라인 준수율: 94.7% (모든 알고리즘 중 최고).
평균 응답 시간: 54.3초 (모든 알고리즘 중 최저).
총 이익: 25,100 (LBO보다 7.0% 높고, Profit-Aware보다 29.4% 높음).
안전율: 59.0% (CECO의 43.7%보다는 유의미하게 높지만, Profit-Aware의 70.0%보다는 낮음).
에너지 효율성: 0.1237 (LBO 및 Profit-Aware와 경쟁 가능한 수준).

반면, CECO는 가장 높은 단일 목적 이익(29,825)을 달eric했으나, 낮은 안전율(43.7%)과 높은 응답 시간(98.0초)으로 인해 종합 순위에서 3위를 기록했다. LBO는 2위를 차지했으나 이익 최적화를 무시했다. 고전적 휴리스틱(FCFS, Round Robin 등)은 모든 다목적 지표에서 저조한 성능을 보였다.

4.2 파레토 분석

파레토 프런트 분석 결과, WASP는 이익 vs 응답 시간 및 안전성 vs 이익의 트레이드오프에서 다른 방법론들을 압도함을 확인했다. WASP는 가장 높은 **하이퍼볼륨(hypervolume)**을 달성하였으며, 이는 다목적 솔루션 공간에 대한 우수한 커버리지를 나타낸다.

4.3 민감도 및 절제 연구 (Ablation Study)

민감도: WASP는 다양한 배터리 용량(70k, 100k, 150k)과 UAV 함대 규모(6개 vs 10개) 변화에도 최상위 순위를 유지하며, 자원 제약에 따라 가중치 구성을 자동으로 적응시켰다.
절제 연구: 단일 구성 요소(2단계 입실 제어, 부하 적응형 가중치 부여, 또는 거리 가중치)를 제거했을 때 종합 점수와 순위가 모두 하락하였으며, 이는 세 가지 메커니즘 모두가 균형 잡힌 성능을 위해 필수적임을 입증한다.

5. 의의 및 주장

본 논문은 WASP를 안전이 중요한 UAV 환경에서 계산 효율성과 다목적 최적성 사이의 간극을 메우는 솔루션으로 포지셔닝한다.

결정론 및 투명성: 학습 기반 접근 방식과 달리, WASP는 완전히 해석 가능한 폐쇄형 결정을 제공하여 안전이 중요한 시나리오에서의 검증에 적합하다.
균형 잡힌 트레이드오프: 저자들은 동적인 UAV 환경에서의 적응형 스케줄링이 반드시 블랙박스 학습 방법을 필요로 한다는 가설을 WASP가 성공적으로 반박한다고 주장한다. WASP는 특정 목적(예: 이익)을 다른 목적(예: 안전 또는 지연 시간)을 희생하면서까지 추구하지 않고도 균형 잡힌 파레토 최적 성능을 달행한다.
강건성: WASP는 다양한 부하 조건과 자원 제약 하에서도 강건함을 유지하며, 높은 데드라인 준수율(>93.5%)과 시뮬레이션 실행 간의 낮은 변동성을 보여준다.

저자들은 WASP가 실시간 UAV 에지 스케줄링을 위한 실용적이고 훈련이 필요 없는 대안을 제공하며, 경제적 이익, 운용 속도, 그리고 시스템 안전 사이의 내재적 모순을 효과적으로 관리한다고 결론짓는다. 향후 연구로는 확률적 채널 모델, 가변 속도 프로파일 탐색 및 강화 학습의 구조적 토대로서의 WASP 통합이 제안되었다.