An Implicit Prioritized Access Protocol for Wireless Sensor Networks

서준표·2025년 6월 3일

실시간 시스템

목록 보기

3/3

실시간 시스템 수업의 마지막 과제로 해당 논문을 발표하게 되었습니다. 본 논문 중 Intra-cell 통신 및 암시적 EDF 스케줄링에 초점을 맞추어 구성했습니다. 실제로 논문에는 Inter-cell 통신 구조 및 Router 기반 전달 방식 또한 정교하게 설계되어 있으나, 제한된 12분 발표 시간 안에 내용을 효과적으로 전달하기 위해 부득이하게 생략하게 되었습니다. 발표 자료는 아래에서 확인하실 수 있습니다:

🔗 발표 자료 링크

특히 저는 그동안 시스템 구조나 스케줄링 이론과는 다소 거리를 두고 있었는데, 이번 실시간 시스템 과목을 수강하면서 다시금 스케줄링, 네트워크 설계, 그리고 리얼타임 통신의 핵심 개념들을 체계적으로 마주할 수 있어 매우 뜻깊은 시간이었습니다. 기존에 접해보지 않았던 implicit contention resolution 개념이나 Frame Sharing 전략(예: FRASH)이 특히 인상 깊었고, 실제 시스템에서 어떻게 적용될 수 있을지 상상하며 공부하는 과정이 무척 흥미로웠습니다.

1. 배경

센서 네트워크는 에너지 제약, 동적 구성, 낮은 비용 등의 이유로 기존 ad hoc 네트워크와는 본질적으로 다른 요구사항을 가집니다. 특히, 다수의 센서가 주기적으로 실시간 데이터를 생성하는 특성 때문에, 무선 채널의 효율적인 스케줄링이 필수적입니다.

기존 MAC 프로토콜은 랜덤 트래픽에 기반하거나, 충돌 회피를 위한 제어 패킷 오버헤드가 존재하는 반면, 이 논문은 다음을 제안합니다:

Earliest Deadline First (EDF) 기반 메시지 우선순위 스케줄링
암시적 충돌 해소 (Implicit Contention) 메커니즘
FRASH (FRAme SHaring): 남은 프레임 재활용 기법
셀 기반 무선 네트워크 구조로 공간 분할

2. 네트워크 구조

셀룰러 구조 (Cellular Architecture)

네트워크는 헥사곤 셀 구조로 분할되고, 각 셀은 자체 채널을 사용
셀 내부 노드는 fully connected multicast 구조를 가짐
두 종류의 메시지 존재:
- Intra-cell 메시지: 셀 내부 전파
- Inter-cell 메시지: 라우터를 통한 셀 간 전달

Inter-cell 구조는 라우터가 두 트랜시버를 이용해 양방향 통신을 수행하며, 프레임 차단 시간(T_block)을 스케줄링에 반영함으로써 intra-cell 스케줄링에 영향을 미치게 됩니다.

3. 암시적 EDF 스케줄링

각 노드는 동일한 EDF 기반의 메시지 테이블을 가지며, 중앙 제어 없이도 충돌 없이 송신 노드를 식별할 수 있습니다.

모든 노드가 동일한 메시지 순서 테이블을 공유
각 프레임마다 누가 전송할지 알고 있음 → 충돌 없음
메시지는 (length mᵢ, period Tᵢ, deadline Dᵢ=Tᵢ)로 정의됨
무선 매체 특성을 고려해 멀티캐스트로 전파

제어 패킷 없이도 deterministic MAC 스케줄링이 가능한 점이 핵심입니다.

FRASH는 하드 리얼타임 메시지의 보장을 유지하면서, 사용되지 않은 프레임을 aperiodic 메시지 서버가 활용할 수 있도록 하는 기법입니다.

🔧 주요 메커니즘:

각 메시지는 예약된 프레임 수만큼 전송 가능
실제로 사용하지 않은 프레임은 NULL 메시지로 표시됨
다른 노드가 해당 프레임을 사용할 수 있도록 헤더에 메시지 ID 포함
모든 노드가 이를 수신하면 스케줄러가 프레임을 재활용

이는 CPU 스케줄링에서의 CASH(Capacity Sharing) 기법과 유사한 이론 구조를 따릅니다.

5. 성능 실험

실험 조건

시뮬레이터: ns-2 기반
비교 대상: CSMA/CA, EDCF, Black-Burst
트래픽: VBR + aperiodic (각 50%)
지표:
- 시스템 throughput
- aperiodic 메시지 평균 지연

결과 요약

I-EDF 및 I-EDF + FRASH가 가장 높은 throughput (95~100%)
aperiodic 지연 측면에서도 FRASH 적용 시 개선 효과 큼

고밀도 네트워크 환경, 높은 offered load(90%)에서도 안정성 유지

6. 이론적 타당성

논문은 다음 이론적 조건들을 통해 정형적 보장을 제공합니다:

Liu & Layland schedulability condition (Σ Cᵢ/Tᵢ ≤ 1)
Processor Demand Criterion을 통한 T_block 반영
EDF 동기화된 노드 스케줄 테이블을 통한 deterministic 스케줄
FRASH 적용 시에도 모든 하드 메시지는 기한 내 전송 보장
패킷 유실 상황에서도 다음 세 가지 케이스 외에는 발생하지 않으며, 모두 전송 충돌이 없음을 증명:
1. 동일한 메시지를 모든 노드가 알고 있음
2. 일부 노드만 마지막 메시지 수신 → NULL 메시지 처리
3. 전부 비어있거나 NULL 메시지만 존재 → 채널 idle

하드 메시지 세트의 스케줄 가능성

하드 메시지 세트 $\mathcal{M}_h = \{M_1, M_2, \dots, M_n\}$ 에 대해, 각 메시지는 다음 정보를 가집니다:

$m_i$ : 메시지 길이 (전송에 필요한 프레임 수)
$T_i$ : 메시지 주기
$D_i = T_i$ : 상대 기한
$U_i = \frac{m_i}{T_i}$ : 메시지 사용률

[Theorem 2] Liu & Layland 기반 조건

EDF 스케줄러 하에서, 하드 메시지 집합이 기한 내에 스케줄되기 위한 필요충분조건은 다음과 같습니다:

\sum_{i=1}^{n} \frac{m_i}{T_i} \leq 1

이는 프로세서 기반 EDF 조건을 무선 MAC 구조에도 확장한 형태입니다.

T_block 포함한 스케줄 조건 (Intra + Inter-cell 통합)

셀 내에서 일부 프레임은 inter-cell 통신을 위해 block됩니다. 이때, block 프레임은 주기적 메시지 $M_{\text{block}}$ 로 모델링됩니다:

$m_{\text{block}} = 1$
$T_{\text{block}}$ : inter-cell 프레임 주기
$D_{\text{block}} = 1$

그러므로 intra-cell 메시지의 schedulability를 판단하는 Processor Demand Criterion은 다음과 같습니다:

\sum_{i=1}^{n} \frac{m_i}{T_i} + \frac{1}{T_{\text{block}}} \leq 1

Aperiodic 메시지를 포함한 Hybrid 조건

Soft aperiodic 메시지는 polling server로 처리되며, 각 서버는 다음 파라미터를 가집니다:

$Q_j$ : 서버 용량 (한 주기 내 사용할 수 있는 프레임 수)
$T_j$ : 서버 주기

이를 포함한 전체 schedulability 조건은 다음과 같습니다:

\sum_{i \in \mathcal{M}_h} \frac{m_i}{T_i} + \sum_{j \in \text{servers}} \frac{Q_j}{T_j} \leq 1

핵심: FRASH는 예약된 프레임을 reclaim할 뿐이고, 스케줄 가능성에는 영향을 주지 않음.

충돌 없음 보장

패킷 유실에도 불구하고 전송 충돌(conflict)이 발생하지 않는다는 것은 다음 두 개의 Lemma와 하나의 Theorem으로 증명됩니다.

Lemma 1: 예약 프레임은 기한 내에 반드시 전송됨

주어진 메시지 집합 $\mathcal{M}$ 이 FRASH를 포함한 EDF 알고리즘으로 스케줄될 때, 모든 예약 프레임은 해당 메시지 기한 내에 소비됩니다.

\forall i, \quad m_i \text{개의 프레임은 } D_i = T_i \text{ 이내에 모두 사용됨}

결과: 모든 하드 메시지는 기한 내 완료됨.

Lemma 4: 로컬 ready queue의 3가지 가능한 상태

패킷 유실이 발생해도, 각 노드의 local ready queue는 아래 세 가지 상태 중 하나만을 갖습니다:

일부는 메시지 $M_{\text{old}}$ , 일부는 $M_{\text{null}}$
모두 동일한 $M_{\text{new}}$ 를 유지
모두 비어 있거나 $M_{\text{null}}$ 만 존재

이 구조는 induction으로 증명됨: 유실이 반복되더라도 ready queue가 위 조건을 유지함.

Theorem 6: 충돌 불가성

위 Lemma 4에 따라 어떤 경우에도 동일 프레임에 서로 다른 메시지를 두 노드가 동시에 전송하는 경우는 발생하지 않음:

(Case A) 모든 노드가 동일한 메시지를 전송하려 할 때 → 송신자는 유일
(Case B) 일부는 메시지를 끝낸 상태, 일부는 전송 시도 → 송신자는 유일 또는 없음
(Case C) 모두 NULL 상태 → 채널 idle

따라서 다음이 성립합니다:

\text{∀ 패킷 유실 시나리오에 대해 } \quad \text{No MAC-level collision}

7. 마무리

이 논문은 센서 네트워크의 주기성(periodicity)과 fully-connected 지역 구조를 기반으로, 제어 패킷 없는 deterministic MAC 스케줄링을 가능하게 한다는 점에서 매우 독창적입니다. 특히, 실시간성과 유연한 자원 활용(aperiodic 처리)을 양립시키는 구조를 제시했다는 점에서 이론적으로도 가치가 높습니다.

서준표

이전 포스트

An Implicit Prioritized Access Protocol for Wireless Sensor Networks

실시간 시스템

1. 배경

2. 네트워크 구조

셀룰러 구조 (Cellular Architecture)

3. 암시적 EDF 스케줄링

🔧 주요 메커니즘:

5. 성능 실험

실험 조건

결과 요약

6. 이론적 타당성

하드 메시지 세트의 스케줄 가능성

[Theorem 2] Liu & Layland 기반 조건

T_block 포함한 스케줄 조건 (Intra + Inter-cell 통합)

Aperiodic 메시지를 포함한 Hybrid 조건

충돌 없음 보장

Lemma 1: 예약 프레임은 기한 내에 반드시 전송됨

Lemma 4: 로컬 ready queue의 3가지 가능한 상태

Theorem 6: 충돌 불가성

7. 마무리

Response-Time Analysis for globally scheduled Symmetric Multiprocessor Platforms

0개의 댓글

An Implicit Prioritized Access Protocol for Wireless Sensor Networks

실시간 시스템

1. 배경

2. 네트워크 구조

셀룰러 구조 (Cellular Architecture)

3. 암시적 EDF 스케줄링

4. FRASH (FRAme SHaring)

🔧 주요 메커니즘:

5. 성능 실험

실험 조건

결과 요약

6. 이론적 타당성

하드 메시지 세트의 스케줄 가능성

[Theorem 2] Liu & Layland 기반 조건

T_block 포함한 스케줄 조건 (Intra + Inter-cell 통합)

Aperiodic 메시지를 포함한 Hybrid 조건

충돌 없음 보장

Lemma 1: 예약 프레임은 기한 내에 반드시 전송됨

Lemma 4: 로컬 ready queue의 3가지 가능한 상태

Theorem 6: 충돌 불가성

7. 마무리

Response-Time Analysis for globally scheduled Symmetric Multiprocessor Platforms

0개의 댓글