Bringing Network Coding into Multi-Robot Systems: Interplay Study for Autonomous Systems over Wireless Communications

1. 문제 정의 (Problem Statement)

• 배경: 다중 로봇 시스템 (MRS) 은 로봇 간 상태 정보 교환, 행동 조정, 안전 제약 준수를 위해 통신에 의존합니다. 그러나 실제 무선 채널은 지연 (delay), 패킷 소실 (erasures), 순서 왜곡 (ordering stalls) 을 발생시킵니다.
• 핵심 문제:
  • 대부분의 자율성 알고리즘은 신뢰성 있고 즉각적인 메시지 전달을 가정하지만, 실제 통신 환경은 이를 충족하지 못합니다.
  • 기존의 재전송 기반 (Retransmission-based) 프로토콜 (예: SR-ARQ) 은 패킷 손실 시 재전송을 위해 왕복 시간 (RTT) 을 기다려야 하므로, **순차적 전달 지연 (In-order delivery delay)**이 크게 증가합니다.
  • 이러한 지연은 로봇의 상태 추정 (Estimation) 을 왜곡하거나, 안전 결정 (예: 충돌 회피) 을 위한 기한 (Deadline) 을 놓치게 만들어 치명적인 결과를 초래할 수 있습니다.
• 연구 목표: 통신 계층의 동작이 자율성 루프 (Autonomy loop) 에 미치는 영향을 분석하고, 지연과 손실 환경에서 데이터의 적시성 (Timeliness) 과 신뢰성을 보장하는 새로운 통신 메커니즘을 제안하는 것.

2. 방법론 (Methodology)

저자는 통신 계층과 자율성 계층을 분리하여 평가하는 대신, 두 계층을 통합적으로 분석하는 두 가지 사례 연구 (Case Studies) 를 수행했습니다.

A. 사용된 통신 프로토콜 비교

1. UDP (Best-effort): 재전송 및 순서 보장이 없음. 패킷 손실 시 복구 불가.
2. SR-ARQ (Selective-Repeat ARQ): 손실된 패킷만 재전송하는 신뢰성 기반 프로토콜. 하지만 순차 전달을 강제하므로, 앞선 패킷이 손실될 경우 뒤따르는 패킷도 대기하게 되어 Head-of-Line Blocking이 발생하고 지연이 증가함.
3. AC-RLNC (Adaptive Causal Random Linear Network Coding):
   • 핵심 원리: 특정 패킷을 재전송하는 대신, 여러 원본 패킷을 선형 결합하여 인코딩된 패킷 (Coded packets) 을 전송합니다.
   • 적응성: 채널 상태에 따라 인코딩된 중복 데이터 (Redundancy) 를 능동적/수동적으로 조절합니다.
   • 장점: 수신 측에서 충분한 수의 독립적인 인코딩 패킷만 받으면 원본 복구가 가능하므로, 특정 패킷의 손실에 구애받지 않고 복구가 이루어져 지연을 줄입니다.

B. 사례 연구 1: 협력적 국소화 (Cooperative Localization)

• 시나리오: 여러 로봇이 GPS 및 상호 거리 측정 (LiDAR) 을 통해 위치를 추정합니다.
• 모델: 확장 칼만 필터 (EKF) 를 사용하며, 지연된 측정값을 처리하기 위해 두 가지 접근법을 비교합니다.
  • Naive Approach: 지연된 패킷이 도착하면 즉시 처리 (순서 불일치 발생).
  • I-ReE (Iterative Re-estimation): 지연된 측정값이 도착하면 과거 상태 창 (Sliding window) 을 다시 계산하여 시간적 일관성을 유지하며 추정치를 갱신하는 통신 인지 (Communication-aware) 방법.
• 평가: 다양한 패킷 소실률 ($\epsilon$) 과 지연 조건에서 추정 오차를 분석.

C. 사례 연구 2: 안전 필수 과속 추월 (Safety-Critical Overtaking)

• 시나리오: 자차 (Ego vehicle) 가 트럭 뒤를 추월하다가, 반대 차선에서 접근하는 차량을 V2V 통신으로 감지해야 합니다.
• 조건: 자차는 반대 차선 차량을 직접 볼 수 없으므로, V2V 패킷을 일정 개수 ($N_{req}$) 이상 수신해야만 추월을 중단 (Abort) 할 수 있습니다.
• 평가: 패킷 수신 지연으로 인해 '중단 기한 (Abort Deadline)'을 지키지 못할 확률을 분석합니다.

3. 주요 기여 (Key Contributions)

1. 자율성 - 통신 공동 설계 (Co-design) 의 필요성 강조: 통신 계층의 지연과 손실 패턴이 자율성 알고리즘의 성능과 안전성을 직접적으로 결정함을 입증했습니다.
2. 재전송 프로토콜의 한계 규명: 기존 SR-ARQ 와 같은 재전송 기반 프로토콜은 지연 환경에서 '순차적 전달 지연'을 유발하여 로봇 작업에 불필요한 데이터 지연을 초래함을 보였습니다.
3. AC-RLNC 의 효과성 입증: 네트워크 코딩을 적용한 AC-RLNC 가 지연과 손실 환경에서 **지연 - 처리량 트레이드오프 (Delay-Throughput Tradeoff)**를 최적화하여, 재전송 방식보다 훨씬 빠른 데이터 전달과 높은 신뢰성을 제공함을 증명했습니다.
4. 지연 인지 추정기 (Delay-aware Estimator) 제안: 협력적 국소화 시 I-ReE 알고리즘을 통해 지연된 측정값을 올바르게 처리하여 추정 정확도를 회복하는 방법을 제시했습니다.

4. 실험 결과 (Results)

A. 협력적 국소화 결과 (Fig. 3)

• 지연의 영향: 패킷 손실보다 **지연 (Delay)**이 추정 오차를 증가시키는 주된 요인임을 확인했습니다. 지연된 데이터를 순서대로 처리하지 않으면 (Naive approach) 오차가 급증합니다.
• 프로토콜 비교:
  • UDP: 패킷 손실 시 데이터가 영구적으로 손실되어 오차가 커집니다.
  • SR-ARQ: 중간 정도의 손실률에서는 잘 작동하지만, 손실률이 높아지면 재전송 대기 시간으로 인해 패킷이 추정 유효 창을 넘어서 도착하여 성능이 급격히 저하됩니다.
  • AC-RLNC + I-ReE: 높은 패킷 소실률 (1 에 근접) 에서도 거의 이상적인 (Near-ideal) 성능을 유지했습니다. 인코딩된 패킷의 누적 덕분에 지연 없이 데이터를 복구하고, I-ReE 를 통해 지연된 정보를 일관되게 통합했습니다.

B. 안전 필수 추월 결과 (Fig. 4)

• 기한 준수 확률: 자차가 추월을 중단하기 위해 필요한 25 개의 패킷을 기한 ($t=110$) 내에 수신할 확률을 평가했습니다.
  • SR-ARQ: 재전송 지연으로 인해 긴 지연 꼬리 (Latency tail) 가 발생하여 기한 준수 확률이 약 **60%**에 그쳤습니다.
  • AC-RLNC: 적응형 코딩으로 인해 패킷이 기한보다 훨씬 일찍 도착하여 기한 준수 확률이 약 **80%**로 크게 향상되었습니다.
• 시각화: 시뮬레이션 결과, SR-ARQ 를 사용할 경우 충돌 회피 실패 (Collision) 가 발생하지만, AC-RLNC 를 사용할 경우 성공적으로 중단 (Abort) 하는 것을 확인했습니다.

5. 의의 및 결론 (Significance & Conclusion)

• 핵심 통찰: 다중 로봇 시스템에서 통신은 단순한 데이터 전송 수단이 아니라, 자율성 파이프라인의 핵심 구성 요소입니다. 통신 프로토콜의 구조적 특성 (재전송 vs 코딩) 이 로봇이 수신하는 정보의 '적시성'과 '신뢰성'을 근본적으로 결정합니다.
• 실용적 가치: 네트워크 코딩 (특히 AC-RLNC) 은 단순한 처리량 향상 도구가 아니라, 지연과 손실 환경에서도 로봇의 상태 추정 일관성을 유지하고 안전 기한을 준수하게 하는 신뢰성 메커니즘으로 작용합니다.
• 미래 방향: 자율성 알고리즘과 통신 메커니즘을 분리하여 설계하는 관점을 넘어, 작업의 중요도 (Criticality) 와 데이터의 신선도 (Freshness) 를 고려한 공동 설계 (Co-design) 프레임워크가 필요함을 강조합니다.

이 논문은 무선 통신 환경이 열악한 실제 다중 로봇 시스템에서, 네트워크 코딩 기반의 적응형 통신 프로토콜이 기존 재전송 방식보다 안전성과 성능 면에서 우월함을 체계적으로 입증한 중요한 연구입니다.