MDP-based Energy-aware Task Scheduling for Battery-less IoT

기술 요약: 배터리 없는 IoT 를 위한 MDP 기반 에너지 인식 작업 스케줄링

문제 제기
배터리 없는 사물인터넷 (IoT) 장치는 주변 에너지 수확에 의존하므로, 에너지 인식 스케줄링을 통해 관리해야 하는 간헐적 운영이 발생합니다. 이 과제는 감지, 로컬 컴퓨팅, 무선 전송과 같은 특정 작업 체인이 고정된 보고 주기 내에 완료되어야 하는 주기적 모니터링 응용 분야에서 특히 심각합니다. 핵심적인 어려움은 에너지 간헐성과 경성 시간 제약이라는 두 가지 경쟁하는 제약 조건을 균형 있게 맞추는 데 있습니다.

• 에너지 제약: 작업을 실행하려면 커패시터 전압이 작업 완료 전에 장치가 전원 고장 (전압이 꺼짐 임계값 이하로 떨어짐) 을 경험하지 않도록 충분한 수준이어야 합니다.
• 시간 제약: 작업은 엄격한 선후 관계 (감지 $\to$ 컴퓨팅 $\to$ 전송) 와 허용 가능한 시작 창을 준수해야 합니다. 더 많은 에너지를 수확하기 위해 작업을 지연시키면 후속 작업이나 주기 자체의 기한을 놓칠 위험이 있으며, 에너지가 부족할 때 너무 일찍 작업을 시작하면 전원 고장의 위험이 있습니다.

기존 접근 방식은 종종 단기 실현 가능성, 단일 주기 최적화, 또는 단순화된 에너지 모델에 초점을 맞추어, 경성 제약과 확률적 에너지 도착 하에서 장기 성능을 공동으로 최적화하는 데 실패했습니다.

방법론
저자들은 스케줄링 문제를 **장기 평균 보상 마르코프 의사결정 과정 (MDP)**으로 공식화했습니다. 이 프레임워크는 에너지 안전성과 기한 준수 간의 트레이드오프를 포착하기 위해 시스템 동역학을 명시적으로 모델링합니다.

1. 시스템 모델:

   • 장치는 $T_s$ 지속 시간의 주기적 사이클에서 작동하며, 이는 이산 시간 단위로 나뉩니다.
   • 에너지는 에너지 수확 (EH) 변환기를 통해 수확되어 커패시터에 저장됩니다. 전압 변화는 수확 중 충전과 작업 실행 또는 수면 중 방전을 고려하여 RC 회로 동역학을 사용하여 모델링됩니다.
   • 커패시터 전압이 꺼짐 임계값 $V_{out}$ 이하로 떨어지지 않고 작업이 완료될 확률을 정량화하는 "안전 실행" 확률 지표가 정의됩니다.

2. MDP 공식화:

   • 상태 공간: 커패시터 전압, 로컬 시계 (주기 내 시간), 작업 체인의 진행 상황을 나타내는 작업 플래그 (0: 감지 대기, 1: 감지 완료, 2: 컴퓨팅 완료, 3: 전송 완료) 로 정의된 세트로 구성됩니다. 연속적인 전압은 유한 상태 MDP 방법을 가능하게 하기 위해 양자화됩니다.
   • 행동 공간: 장치는 현재 상태의 허용 가능한 창에 따라 수면, 감지, 컴퓨팅, 또는 전송을 선택할 수 있습니다.
   • 보상 설계: 두 가지 보상 함수가 제안됩니다. 기본 보상은 스케줄링 결정과 안전 실행 확률을 결합합니다. 시그모이드 기반 보상은 위험한 저에너지 실행을 더 강력하게 처벌하기 위해 임계값 매개변수를 도입하여, 중간 에너지 상태에서 전원 고장을 줄이기 위해 보수적인 스케줄링을 장려합니다.

3. 정책 유도:

   • 저자들은 유도된 마르코프 체인이 단일 체인 (unichain) (정확히 하나의 재발 클래스를 포함함) 임을 증명하여, 장기 평균 보상이 초기 상태와 무관함을 보장합니다.
   • 최적 정상 정책이 커패시터 전압에 대해 임계값 구조를 가진다는 것을 확립합니다. 이는 주어진 시간 단계와 작업 단계에 대해, 장치가 작업을 실행해야 하는 전압 임계값 이상과 수면해야 하는 임계값 이하가 존재함을 의미합니다.
   • 이는 선형 계획법 (LP) 을 사용하여 오프라인으로 계산할 수 있는 최적 정상 임계값 기반 (OSTB) 스케줄러로 이어집니다.

4. 상관된 에너지로 확장:

   • 에너지 도착이 시간적으로 상관되어 있는 현실적인 시나리오 (예: 변하는 조명 조건) 를 다루기 위해, 유한 상태 마르코프 과정에 의해 지배되는 EH 모드 변수로 상태를 확장하여 프레임워크가 확장됩니다.
   • 임계값 기반 구조가 이 상관된 설정에서도 최적임을 보여주기 위한 충분 조건이 제공되며, 이제 임계값은 시간 단계와 현재 EH 모드 모두에 의존합니다.

주요 기여

1. 경성 제약 MDP 공식화: 이 논문은 커패시터 동역학에서 유도된 안전 실행 조건, 작업 선후 관계, 그리고 경성 허용 시작 창을 명시적으로 강제하는 유한 상태 MDP 로 주기적 배터리 없는 작업 스케줄링을 제시하여, 기존 연구에서 사용된 소프트 유틸리티 페널티를 넘어서는 접근을 제공합니다.
2. 보수적 보상 설계: 중간 에너지 상태에서 보수적인 스케줄링을 명시적으로 장려하는 새로운 시그모이드 기반 보상 함수가 도입되어, 장기 작업 완료 목표를 유지하면서 전원 고장을 효과적으로 줄입니다.
3. 구조적 특성화: 저자들은 MDP 의 단일 체인 속성을 증명하고 최적 정책이 임계값 기반임을 입증합니다. 이는 정책 탐색 공간을 일반적인 매핑에서 전압 임계값 집합으로 축소하여 OSTB 스케줄러의 효율적인 계산을 가능하게 합니다.
4. 상관된 EH 확장: 유한 상태 마르코프 모델을 통해 상관된 에너지 수확을 처리하도록 프레임워크가 확장되었으며, 특정 조건 하에서 임계값 기반 최적성을 유지합니다.
5. 종합 평가: 제안된 OSTB 스케줄러는 에너지 가드付き 최선 기한 우선 (EDF-EG) 휴리스틱 및 가능한 한 늦게 (ALAP) 정책과 비교하여 벤치마킹되었습니다.

결과
수치 시뮬레이션은 OSTB 스케줄러의 우월성을 보여줍니다:

• 성능: OSTB 는 특히 수확된 에너지가 부족할 때 EDF-EG 및 ALAP 보다 높은 장기 전체 체인 완료율 (성공적인 감지 - 컴퓨팅 - 전송 사이클) 을 달성합니다.
• 신뢰성: 시그모이드 기반 보상 설계는 기본 보상 함수에 비해 전원 고장 수를 현저히 줄입니다.
• 지연 시간: 저에너지 영역에서 OSTB 는 에너지 수확과 작업 실행을 적응적으로 균형 있게 조정하여 기저선보다 낮은 실행 지연 시간을 달성하는 반면, ALAP 은 "마지막 순간까지 기다리기" 전략으로 인해 최대 지연 시간을 겪습니다.
• 상관된 EH: 상관된 에너지 시나리오에서 확장된 OSTB 정책은 현재 EH 모드에 기반하여 임계값을 적응시켜 종단 간 완료율을 추가로 향상시킵니다.
• 확장성: 오프라인 계산 복잡도는 이산화된 상태 차원에 대해 다항식이며, 온라인 구현 복잡도는 시간 단계당 $O(1)$로, 전압 임계값 조회만 필요합니다.

의의
이 논문은 제안된 프레임워크가 배터리 없는 IoT 의 에너지 인식 작업 스케줄링을 위한 엄격하고 분석적으로 다루기 쉬운 솔루션을 제공한다고 주장합니다. 적응형 임계값 정책을 통해 에너지 가용성과 기한의 긴급성을 명시적으로 결합함으로써, OSTB 스케줄러는 더 많은 에너지를 기다리는 것과 기한을 놓칠 위험 사이의 근본적인 트레이드오프를 효과적으로 관리합니다. 이 연구는 제한된 에너지 저장 장치를 가진 장치의 경우, 안전성과 타이밍을 공동으로 최적화하는 것이 이러한 요소 중 하나만을 최적화하는 휴리스틱보다 상당한 성능 향상을 가져온다는 점을 강조합니다. 최적 정책의 구조적 특성화는 복잡한 온라인 학습이나 무거운 실시간 계산을 피하고 실용적인 구현 경로를 제공합니다.