An Implicit Prioritized Access Protocol for Wireless Sensor Networks

느낀점

 

 

Problem Statement

전통적인 MAC(Medium Access Control) 프로토콜과 제안하는 것과 차이는?

논문에 따르면 전통적인 MAC 프로토콜은 센서 네트워크에 적합하지 않다. 이는 센서 네트워크가 기존 Ad hoc 네트워크와 근본적인 면에서 다르기 때문이다. 주요 차이점은 아래와 같다.

• 트래픽  특성: 전통적인 프로토콜은 네트워크 트래픽이 본질적으로 무작위라고 가정하는 경향이 있다. 그러나 이 가정은 센서 네트워크에서는 적용되지 않는다. 센서 네트워크의 메시지는 주로 주기적이며 유한한 지연이 보장되어야 한다. 
• 목표: 전통적인 CSMA 및 그 변형은 시스템 처리량 극대화에 초점을 맞춘다. 센서 네트워크에서는 최적화 목표가 원시 처리량에서 타이밍 제약 조건을 충족하는 비 중복 데이터 처리량으로 변경되어야 한다.
• 인프라: 전통적인 무선 네트워크는 유선 BackBone에 연결된 기지국으로 구성된 인프라에 의존하는 경우가 많다. 비용 제약과 센서 네트워크의 동적인 특성때문에 유선 BackBone을 사용하는 기지국의 존재를 가정하는 것은 바람직하지 않다. 대신 완전한 무선 솔류션이 선호된다. 
• Node 이동성: 에드훅 네트워크와 달리, 센서 네트워크의 노드는 일반적으로 고정되어 있다. (센서 Node의 이동성 문제는 이 논문의 향후 연구작업의 일부이다.)
• 채널 접근 및 예약: 대부분의 기존 MAC 프로토콜은 채널 예약을 위해 제어 패킷을 교환해야 한다. 이는 상당한 오버헤드를 유발 할 수 있다. 반면, 제안된 센서 네트워크 아키텍쳐는 트레픽의 주기적인 특성을 활용하여 제어 패킷 교환 없이 암시적으로 충돌을 해결한다.
• 데이터 중복성: 센서 네트워크에서는 센서가 동일한 정보를 수집하여 많은 중복 데이터를 생성할 수 있다. 제안된 셀루러 구조 및 멀티캐스트 전송은 중복 데이터 양을 효과적으로 줄인다.

셀루러 구조는 어떻게 구성되는지?

• 공간 분할: 네트워크는 여러 개의 셀로 공간적으로 분할된다.
• 주파수 분할 다중화(FDM): 인접한 셀 간의 충돌을 피하기 위해 주파수 분할 다중화(FDM)가 사용된다. 이 논문에서는 7개의 서로 다른 채널을 사용하여 동일 채널 간섭을 피한다. 이는 전통적인 셀룰러 시스템의 클러스터 개념과 유사하지만, 유선 백본에 연결된 기지국에 의존하지 않는다는 점에서 다르다.
• 셀 내 연결성: 각 셀 내부에서는 Node들이 완전히 연결되어 있다고 가정한다. 모든 Node가 서로의 전송 범위 내에 있도록 공통 전력 레벨이 사용된다. 이 가정은 Hidden Node 문제를 피하고, 전체 네트워크가 완전히 연결되어 있다고 가정하는 다른 프로토콜보다 덜 제한적이다.
• 유선 BackBone없음: 비용 제약과 센서 네트워크의 동적인 특성 때문에 유선 백본을 사용하는 기지국의 존재를 가정하지 않는 것이 바람직하며, 완전한 무선 솔류션이 선호된다. 
• 라우터 Node: 인접 셀 간의 셀 간(inter-Cell) 통신은 라우터 노드를 통해 이루어진다. 라우터 노드는 각 셀의 중심 영역에 위치하며, 두 개의 트랜시버를 갖추어 서로 다른 두 채널을 사용하여 동시에 송수신할 수 있다. 라우터는 자신이 속한 셀의 채널로 셀 간 메시지를 전송하고, 메시지를 수신할 셀의 채널로 수신한다. 
• 메시지 종류: Intra-cell message, Inter cell message
  • 셀 내 메시지는 각 셀 내부에서 교환되며, 멀티 캐스트 방식으로 전송된다. 이는 동일한 정보를 수집하는 센서들로 인해 발생하는 데이터 중복성을 효과적으로 줄이는데 도움이 된다.
  • 셀 간 메시지는 라우터 노드를 통해 이웃 셀간 교환되며, hop by hop으로 전달된다.
• 타아밍 및 스케줄링: 센서 네트워크 트래픽의 대부부은 주기적이며, 유한한 지연이 보장되어야 한다. 이러한 주기적인 특성을 활용하여 메시지의 바운드 지연을 보장하고 모든 가용 대역폭을 사용한다. 이는 EDF(Earliest Deadline First)알고리즘에 기반한 MAC 프로토콜을 통해 달성된다.
• 암묵적 충돌 해결: 메시지의 주기적인 특성 덕분에 대부분의 기존 MAC 프로토콜처럼 채널 예약을 위해 제어 패킷을 교환할 필요없이 충돌을 암묵적으로 해결할 수 있다. EDF 스케줄을 각 노드에 복제하여 (implicit EDF), 각 노드는 다음으로 전송할 메시지를 알 수 있다.
• 고정 노드: 에드혹 모바일 무선 네트워크와 달리, 센서 노드는 일반적으로 고정되어 있다.
• 프레임 구조 및 동기화: 시간은 프레임 단위로 나뉘며, 모든 네트워크 노드는 프레임 기반으로 동기화된다. 셀 간 통신을 위해 일부 프레임이 주기적으로 예약되며, 이러한 셀 간 프레임은 셀 간 동기화되어야 한다.
• 네트워크 초기화: 네트워크 초기화 시, 각 셀 내부의 모든 노드에게 메시지 테이블이 전송되고 각 라우터가 포워딩해야하는 모든 셀 간 메시지가 선언된다. 이는 임의의 셀에서 시작하여 리더가 라우터 노드에게 정보를 보내고, 라우터가 이를 다른 셀로 포워딩한 후 각 셀 내부 노드에게 브로드캐스트하는 방식으로 이루어진다. 센서들은 셀 라우터로부터 메시지 테이블을 수신하기 위해 채널을 청취한다. 메시지 테이블은 런타임에 수정되지 않고 미리 설정된다.

정리하면, 이 셀룰러 구조는 유선 백본없이 무선으로 구성되며, 공간 분할 및 주파수 재사용을 통해 효율성을 높이고, 주기적인 트래픽 특성과 EDF 스케줄링을 활용하여 실시간 성능을 보장하며, 라우터 노드를 통해 셀 간 통신을 처리하고, 멀티캐스트를 통해 셀 내 데이터 중복성을 줄인다. 

 

Contributions

1. EDF(Earliest Deadline First) 스케줄링을 기반으로 한 분산형 MAC 프로토콜 제안 (암묵적 경쟁 해소 방식)
2. 셀 기반 네트워크 구조: 공간 재사용을 위한 주파수 분할 방식(FDM) 도입
3. FRASH(FRAme SHaring) 기법 제안: 미사용 프레임 재활용을 통한 성능 향상
4. 이론적 검증 및 정형적인 스케줄링 조건 증명
5. 시뮬레이션(ns-2)을 통해 다른 방식들과의 성능 비교 및 검증 

 

Key Ideas

• 암묵적 EDF 스케줄링: 모든 노드가 같은 스케줄 테이블을 기반으로 동기적으로 동작하므로 제어 메시지없이 충돌 방지 가능
• 멀티캐스트 전송: 중복 데이터 최소화
• FRASH 기법: 미사용 전송 프레임을 회수하여 비주기 메시지에 활용
• 결정적 충동 회피: 패킷 손실이 있었도 충돌 발생없이 동작함 

 

Mathematic Views

Lemma 1: 스케줄 가능성 조건

정리: 각 메시지의 주기와 길이를 이용해, 다음 조건이 성립하면 모든 메시지는 Deadline 내 전송됨
$$\sum_{i=1}^{n}\frac{m_i}{T_i}\leq 1$$

• $m_i$: 메시지 길이(프레임 수)
• $T_i$: 메시지 주기

증명:

이는 EDF 스케줄링의 고전적인 사용률 조건이다. 하나의 자원을 여러 Job이 사용할 때, 총 사용률이 1 이하이면 모든 Job은 Deadline 내에 완료될 수 있다. 

직관:

모든 메시지가 사용하는 시간 비율의 총합이 전체 시간(=1)을 초과하지 않으면, 각 메시지는 자기 몫의 시간을 확보할 수 있다. 

 

Lermma 3: 스케줄 동기화

모든 노드가 패킷을 정확히 수신하면, 스케줄링 결과는 동일하며 로컬 대기 큐도 동기화됨

증명:

• 모든 노드는 동일한 EDF 규칙 사용
• 메시지 시작 시간, 주기, 마감 시간 동일
• 노드 랭크에 따라 동일한 tie-break 방식 사용 -> 따라서 모두 동일한 결정을 내림

직관:

• 노드들이 같은 정보를 공유하고 동일한 규칙을 따른다면, 결과도 항상 같다.

 

Lemma 4: 패킷 손실 시 가능한 상태

패킷이 유실되어도 다음 3가지 상태만 발생한다:

1. 일부는 NULL 메시지, 일부는 이미 전송된 메시지
2. 모두가 동일한 새로운 메시지 대기 중
3. 대기 큐가 모두 비어있음

증명:

• 처음에는 모두 동기화되어 있음
• 어떤 메시지가 일찍 완료되면 일부 노드는 Mnull로 대체
• 이후에도 동일 패턴이 반족 -> 위 3가지 상태 외에는 없음

직관:

• 손실이 발생해도, 시스템은 항상 안전한 상태에서 동작함

 

Lemma 5: 선행 메시지 프레임 회수 가능성

특정 메시지가 조기에 완료되면, 그 이전의 메시지들도 NULL로 간주 가능

증명:

• 메시지가 완료되었다면, 그 앞의 메시지들도 이미 전송되었거나 NULL임
• 따라서 선행 메시지도 회수 가능

 

Theorem 2: Hard/ Soft 메시지 혼합 시 스케줄 조건

Hard 주기 메시지 $M_h$와 서버로 처리되는 Soft 비주기 메시지 $M_B$가 다음 조건을 만족하면 전체 메시지는 스케줄 가능:
$$\sum_{M_i \in M_h}^{}\frac{m_i}{T_i}+U_{soft}\leq 1$$

• $U_{soft}=\sum \frac{Q_j}{T_j}$: 서버들의 총 사용률

증명:

• Soft 메시지도 서버 형태로 모델링하면, 전체 시스템은 주기적 메시지로 구성된 EDF 모델과 동일
• Lemma 1의 결과를 적용 가능

직관:

• Hard 메시지 + 서버로 처리된 Soft 메시지를 포함한 총 시스템 사용률이 1 이하라면, 모두 Deadline을 만족시킬 수 있음

 

Theorem 6: 패킷 손실이 있어도 충돌 없음

패킷 손실이 발생하더라도, 서로 다른 노드의 메시지 간에는 충돌이 발생하지 않음

증명:

• Lemma 3~5에서 정의된 상태 외에는 존재하지 않음
• 각 상태에서 충돌은 발생하지 않음:
  • 하나의 노드만 메시지를 보냄
  • 다른 노드는 NULL이거나 대기중
• 모든 경우에 대해 무충돌 보장

직관:

• 시스템이 deterministic하게 구성되어 있어서, 실제 메시지를 보내는 노드는 항상 단 하나임 -> 충돌 없음

 

 

REF

G. Buttazzo, M. Caccamo, L. Y. Zhang, and L. Sha, "An implicit prioritized access protocol for wireless sensor networks," Proceedings 23rd IEEE Real-Time Systems Symposium, 2002., Austin, TX, USA, 2002, pp. implicit contention–resolving protocols and EDF-scheduled wireless MAC for sensor networks, doi: 10.1109/REAL.2002.1181574.