기술 요약: CFCO – 차량 에지 컴퓨팅에서의 태스크 오프로딩을 위한 사회적 후생 극대화 협력적 연합 형성 방법론

1. 문제 정의

차량 에지 컴퓨팅(VEC)은 데이터 소스 근처에서 자원을 제공함으로써 지연 시간에 민가하고 계산 집약적인 애플리케ชัน(예: 자율 주행, 협력 인지)을 지원하는 것을 목표로 한다. 그러나 기존 방식들은 다음과 같은 상당한 한계에 직면해 있다:

• 로컬 컴퓨팅: 온보드 CPU 주파수, 에너지 예산 및 열 제한에 의해 제약을 받는다.
• MEC 오프로딩: 불안정한 차량-인프라 간(V2I) 링크, 도로 차단, 핸드오버 실패, 그리고 여러 차량이 동시에 오프로딩할 때 발생하는 자원 경합(대역폭 및 컴퓨팅 코어)으로 인해 어려움을 겪는다.
• D2D 협업: 인접 차량의 유휴 자원을 활용한다는 점에서 유망하지만, 연합 형성, 헤드(head) 선정 및 안정성 측면에서 과제를 안고 있다.

현재의 문헌들은 이러한 모드들을 별개로 다루거나, 해석 가능성이 부족한 복잡한 학습(예: 심층 강화 학습)에 의존하는 경우가 많다. 따라서 이질적인 차량 태스크 전반에 걸쳐 조기 완료 이득, 에너지 비용, 지연 페널티 사이의 균형을 맞추는 메트릭인 **사회적 후생(social welfare)**을 극대화하기 위해 로컬 컴퓨팅, 장치 간(D2D) 협업, 그리고 MEC 오프로딩을 공동으로 최적화하는 해석 가능한 프레임워크가 필요하다.

2. 방법론: CFCO 알고리즘

본 논문은 반복적인 연합 구조 최적화를 통해 사회적 후생을 극대화하도록 설계된 휴리스틱 알고리즘인 CFCO(Collaborative Coalition Formation for Offloading)를 제안한다.

2.1 시스템 모델

• 네트워크 토폴로지: NGSIM 데이터셋의 실제 궤적을 사용한 1차원 도로 토폴로지.
• 태스크 모델: 각 차량 $i$는 입력 크기($L_i$), 계산 밀도($\rho_i$), 데드라인($\tau^{\max}_i$), 지연 이득 가중치($w_i$), 지연 페널티 계수($\lambda_i$)로 정의되는 태스크를 가진다. 데드라인은 차량의 속도와 결합되어, 더 빠르게 이동하는 차량에 대해 더 높은 민감도를 반영한다.
• 실행 모드:
  1. 로컬 컴퓨팅: 차량 자체 CPU에서 실행.
  2. MEC 오프로딩: 대역폭 공유 및 유한한 코어 혼잡을 고려하여 V2I 링크를 통해 로드사이드 유닛(RSU)으로 오프로딩.
  3. D2D 협업: 비(non)-MEC 차량들이 연합을 형성한다. 가장 높은 CPU 주파수를 가진 차량이 연합 헤드(coalition head) 역할을 수행한다. 헤드는 병렬 또는 배치 모드로 태스크를 처리하며, 실행 지연은 연합 내 최대 워크로드에 의해 결정되고, 헤드의 에너지 비용은 전체 워크로드가 누적된다.

2.2 최적화 목표

목표는 개별 순 후생($W$)의 합을 극대화하는 것이다:
$$W = \sum_{i \in V} \left( w_i \max(0, \tau^{\max}_i - T_i) - E_i - \lambda_i T_i \right)$$
여기서 $T_i$는 태스크 지연 시간이고 $E_i$는 에너지 소비량이다. 이 문제는 집합 분할, 이산 모드 선택 및 링크 타당성 제약을 포함한다.

2.3 알고 \리즘 설계

CFCO는 유한한 상태 공간에서 단조 증가(monotonic improvement) 알고리즘으로 작동한다:

1. 초기화: 차량들을 단일 원소(singleton)로 초기화한다. 보수적인 체크를 통해, 모든 차량이 오프로딩을 시도한다고 가정했을 때의 혼잡한 MEC 시나리오와 비교하여 초기 MEC 사용자들을 결정한다.
2. 병합(Merge) 및 분할(Split):
   • 병합: 사회적 후생의 이득이 엄격하게 양(+)인 경우, 비-MEC 연합 쌍을 반복적으로 병합한다.
   • 분할: 연합의 후생보다 개별 로컬 후생의 합이 더 큰 경우, 다중 멤버 연합을 단일 원소로 분할한다.
   • 모드 정제: 사회적 후생의 총합을 엄격하게 증가시킨다면 차량을 MEC와 비-MEC 상태 사이(또는 로컬과 D2D 사이)에서 전환한다.
3. 로컬 탐색: 로컬 옵티마(local optima)를 벗어나기 위해 결정론적인 로컬 이동(MEC 전환 또는 연합 간 차량 이동)을 수행한다.
4. 종료: 더 이상의 엄격한 개선 이동이 발견되지 않거나 최대 반복 횟수에 도달하면 알고리즘이 종료된다.

3. 주요 기여

1. 통합 모델: 로컬, D2D, MEC 모드를 통합하는 일관된 구현 모델. 이는 CPU 주파수를 기반으로 D2D 연합 헤드를 명시적으로 모델링하고, 대역폭 공유 및 코어 제한을 통해 MEC 혼잡을 모델링한다.
2. 사회적 후생 기반 휴리스틱: 지연이나 에너지만을 최적화하는 방법과 달리, CFCO는 복합적인 후생 함수를 공동으로 최적화한다. 이는 유한한 상태 공간에서 해석 가능성을 요구하지 않고도 단조 증가와 수렴을 보장한다.
3. 트레이스 기반 평가: 합성 토폴로지를 넘어, 실제 위치, 속도, 클래스를 반영하여 CPU 주파수와 속도 종속적 데드라인을 매핑하기 위해 실제 NGSIM 차량 궤적을 활용한다.
4. 통계적 엄밀성: 10개의 독립적인 랜덤 시드에 대한 평균값, 95% 신뢰 구간, 정수 선형 계획법(ILP) 솔루션에 대한 소규모 정밀 최적성 갭 연구와 함께 Wilcoxon 부호 순위 검정을 병행하였다.

4. 실험 결과

실험은 $N=60$대의 차량과 0.7의 V2I 가용 확률을 대상으로 수행되었다. CFCO를 MEC 전용, 싱글톤(로컬 전용), 랜덤, 그리디(Greedy), 매칭(Matching), 시뮬레이티드 어닐링(SA), 그리고 최적 대응 로컬 탐색(BR-LS)을 포함한 8개의 베이스라인과 비교하였다.

4.1 성능 지표 (평균값)

• 사회적 후생: CFCO는 481.28을 달성하여, 두 번째로 우수한 베이스라인인 BR-LS(480.24)보다 0.2% 높았으며, MEC 전용 방식보다는 71.0% 높았다.
• 평균 지연 시간: CFCO는 0.225초를 달성하여, BR-LS 대비 1.9%, MEC 전용 방식 대비 50.4% 감소하였다.
• 태스크 성공률: 0.998로 거의 완벽하였다.
• Jain 공정성 지수(Fairness Index): 0.716으로, 차량 간 후생의 균형 잡힌 분포를 나타냈다.
• 실행 모드 분포: CFCO는 차량의 **20.5%**를 로컬 컴퓨팅에, **22.5%**를 MEC에, **57.0%**를 D2D 연합에 할당하였다.

4.2 효율성 및 최적성

• 실행 시간: CFCO는 9.17초 만에 수렴하였으며, 이는 유사한 솔루션 품질을 달면서도 BR-LS 베이스라인(110.85초)보다 12배 빠르다.
• 최적성 갭: $N=12$인 소규모 연구에서 정밀 ILP 솔버와 비교했을 때, CFCO는 평균 **0.03%**의 최적성 갭만을 보여주었다.
• 통계적 유의성: 쌍체 Wilcoxon 검정을 통해 사회적 후생과 평균 지연 시간 측면에서 모든 베이스라인(BR-LS 포함) 대비 CFCO의 개선이 통계적으로 유의미함($p < 0.05$)을 확인하였다.

4.3 파라미터 민감도

CFCO는 다음과 같이 변화하는 환경에서도 우수한 성능을 유지하였다:

• 로컬 CPU 주파수.
• D2D 대역폭 (테스트된 토폴로지에서 1 MHz를 초과할 때 수익 체감 현상 발생).
• MEC 용량.
• 차량 밀도.
• V2I 신뢰도 (V2I 신뢰도가 떨어짐에 따라 CFCO는 동적으로 로컬/D2D 모드로 전환하였으나, MEC 전용 방식은 더 많은 차량이 동시에 오프로딩을 시도함에 따라 혼잡으로 인해 성능이 크게 저하됨).

5. 의의 및 주장

본 논문은 CFCO가 VEC에서의 태스크 오프로딩을 위한 실용적이고, 해석 가능하며, 효율적인 솔루션을 제공한다고 주장한다. 그 의의는 다음과 같다:

• 트레이드오프 균형: 전송 에너지, 계산 지연, 태스크 데드라인 사이의 트레이드오프를 성공적으로 탐색하여 단일 목적 최적화의 함정을 피한다.
• 현실성: NGSM 트레이스를 활용함으로써, 단순 합성 시뮬레이션보다 더 신뢰할 수 있는 통찰력을 제공하는 실제적인 공간적 클러스터링과 차량 역학을 반영한다.
• 확장성: CFCO는 전수 조사 방식의 로컬 탐색 방법보다 훨씬 낮은 계산 오버헤드로 근사 최적해에 도달하여, 동적인 차량 환경에서의 온라인 의사결정에 적합하다.

저자들은 정적 스냅샷 사용, D2D 헤드의 병렬 처리 추상화, 인센티브 호환적 지불 메커니즘의 부재 등을 한계점으로 인정하였다. 향후 연구로는 연속적 모빌리티, 순차적 처리 모델, 그리고 다중 RSU 협력을 다룰 것을 제안하였다.