[Quorum] Quorum MAC::Paper 1–1

맹주현 (Juhyun Maeng)

무선 센서 네트워크에서 노드의 저 전력을 구현하는 것은 매우 중요합니다. 그래서 Quorum으로 MAC 프로토콜의 저 전력을 구현한 논문을 분석하면서 노드의 저 전력을 구현할 방안을 찾고자 합니다.

이번 게시글은 “A Quorum-Based Energy-Saving MAC Protocol Design for Wireless Sensor Networks” 논문에 대한 글로써, 논문을 분석한 내용의 전반부를 다룹니다.

Executive Summary

무선 센서 네트워크는 주로 환경 모니터링에 사용된다. 이 환경 모니터링에서 노드들은 정보 수집을 위하여 협력 통신을 한다. 협력 통신을 하는 노드들은 배터리로 구동하기 때문에 배터리 자원을 효율적으로 사용할 수 있도록 하는 것은 중요하다. 그래서 배터리 자원을 효율적으로 사용하도록 하는 기존 Power Saving 프로토콜은 주기적으로 노드를 Sleep 모드로 전환해서 Power Saving을 구현한다.

이 Sleep 모드의 지속시간은 트래픽에 맞춰서 정해지기 때문에 저 전력과 저 지연을 구현하지 못할 수 있다. 또한, 노드는 전송에 방해를 받는 환경에 배치될 수 있기 때문에 예상하지 못한 전송 실패를 겪을 수 있다. 그리고 Power Saving 프로토콜은 노드 사이의 무선 링크 파손에 즉각적으로 대응하지 못하기 때문에 전송 지연을 증가 시킬 수 있다.

이와 같은 한계점을 개선하기 위하여 QMAC(A Quorum-based Medium Access Control)을 제안한다. 이 MAC 프로토콜로 구동하는 노드는 적은 트래픽에 대하여 더 긴 Sleep 모드로 구동하면서 저 전력을 구현한다. 또한, 데이터의 흐름이 싱크 노드로 향하는 무선 센서 네트워크에서 노드 사이의 전송 지연을 줄이기 위한 방안으로 Next-hop group을 제안한다.

실험 결과를 통하여 제안하는 QMAC으로 저 전력과 저 지연을 구현할 수 있다는 사실을 증명한다.

Introduction

최근에 무선 센서 네트워크(WSN)는 많은 관심을 받고 있으며, 이 WSN에 대한 많은 애플리케이션이 언급되고 있다. 언급되는 애플리케이션은 환경 모니터링, 모바일 객체 추적, 내비게이션 등이 있다.

WSN는 매우 저렴한 노드로 구성되고, 노드들은 분산 배치되어서 협력통신을 통하여 데이터를 처리, 공유, 저장한다.

노드는 배터리로 구동하기 때문에 충전이 필요하며, 충전할 수 없는 경우를 대비해야 한다. 그래서 WSN에서 구동하는 노드를 위한 Power Saving 프로토콜의 설계는 중요하다. 최근, WSN의 Network Lifetime을 연장하기 위하여 배치 프로토콜[14,17,22], Power Efficient MAC 프로토콜[3,4,78,15,18,24,26], 라우팅 프로토콜[2,9,20]이 제안되었다.

WSN에서 모든 노드는 지속해서 하나의 싱크 노드(A Many to One Communication Model)로 데이터를 보내기 때문에 싱크 노드와 가까운 노드일수록 배터리 소모가 크다. 이처럼 싱크 노드 주변의 노드가 배터리를 빠르게 소모하면서 에너지 홀 문제가 발생할 수 있다. 이 문제를 해결하기 위하여 배치 프로토콜[14,17,22]은 싱크 노드 주변에 더 많은 노드를 배치하는 방안을 제시한다. 그러나 환경에 따라서 노드는 균등하게 배치되어야 하기 때문에 싱크 노드 주변에 더 많은 노드를 배치하는 방안을 구현하는 것은 어려울 수 있다. 이럴 경우, 제안하는 배치 기법으로는 Network Lifetime을 연장할 수 없을 것이다.

Network Lifetime을 연장하는 한 가지 방안은 Energy Efficient MAC 프로토콜을 설계하여서 사용하는 것이다. 에너지 낭비의 주된 원인은 Idel Listening 때문이다. 그래서 방안[3,7,8,15,18,24,26]은 노드의 Idel Listening 지속시간을 줄여서 Network Lifetime을 연장하려 한다.

Network Lifetime을 연장하는 다른 방안[7,15,24,26]은 동기 MAC 프로토콜로 저 전력을 구현하는 것이다. 동기 MAC 프로토콜로 저 전력을 구현하는 것은 적합하다. 왜냐하면 노드는 Active 상태에서 통신하려는 다른 노드의 상태를 확인해야 하는데, Active 상태의 시점을 관리하는 Schedule에 따라서 특정 시점에만 Active 상태를 유지하면 되기 때문에 에너지 낭비를 줄이면서 저 전력을 구현할 수 있는 것이다. 그러나 동기 MAC 프로토콜은 전송 지연을 증가시킬 수 있으며, 동적인 트래픽 처리에는 적합하지 않다.

비동기 MAC 프로토콜과 관련한 다른 제안[3,8,18]은 독립적으로 각 노드가 주기적으로 채널 상태를 확인하기 위하여 노드들의 Awake 주기를 Schedule을 통하여 관리하는 것이다.

데이터를 전송하려는 노드는 목적지 노드를 검색하기 위하여 충분히 긴 프리엠블을 전송한다. 목적지 노드가 프리엠블을 수신하면, 데이터를 받기 위하여 Awake 상태를 유지할 것이다.

비동기 MAC 프로토콜은 노드 사이의 Sync를 맞추기 위하여 제어 데이터를 사용하기 때문에 오버헤드가 발생한다. 그러나 프리엠블이 크면 전송 지연은 증가할 수 있으므로 노드의 에너지 소모량은 늘어날 것이다.

동기와 비동기 MAC 프로토콜을 포함한 앞서 말한 모든 프로토콜로 구동하는 노드는 예상하지 못한 전송 실패에 대해서는 고려하지 않았다. 전송 실패는 노드 사이의 링크를 파손시키기 때문에 성공적인 데이터 전송은 보장되지 않는다. 게다가, 노드 사이의 전송 지연은 증가할 수 있다.

제안하는 방안은 동기 MAC 프로토콜 기반이고, 핵심 기법은 Quorum으로 노드의 Wake-up을 관리 하는 것이다. Wake-up의 빈도는 각 노드의 트래픽에 맞춰서 정해진다. 즉, 노드가 처리해야 하는 트래픽이 적다면, 노드의 Sleep 모드 지속시간은 증가할 것이다.

Quorum은 Mobile Ad Hoc Network 에서 Energy Conservation MAC 프로토콜 설계를 위하여 사용되기도 한다.[5]

제안하는 기법은 Sensor-to-sink 전송 지연을 줄이는 방안을 제공한다. WSN에서 Quorum을 사용하는 MAC 프로토콜의 효율성을 분석하고, 전송 실패가 발생할 수 있는 환경에서 제안하는 기법의 효과를 분석할 것이다. 그리고 이 기법의 우수함을 시뮬레이션 결과로 증명하려 한다.

Related Work

1. S-MAC

S-MAC[24]은 클러스터 기반의 프로토콜이다. 만약, S-MAC으로 구동하는 각 노드가 통신에 관여하지 않는다면, 주기적으로 노드는 Sleep 모드로 전환하여서 Idle Listening을 하지 않을 것이다. 이와 같은 방식은 IEEE 802.11의 Power Saving 모드와 유사하다. Active 상태인 노드는 채널 상태를 확인하기 위하여 각 Beacon Interval의 초기시점에서 Wake-up 한다. S-MAC으로 구동하는 노드는 다른 노드와 Sync를 맞추기 위하여 각 Listen 구간의 초기시점에 인접한 노드와 Schedule을 교환한다. 이 정보로 각 노드는 이웃 노드의 전송 상황을 Listen 하며, 이웃 노드의 전송을 Listen 하지 않으면, Sleep 모드로 전환하면서 에너지 소모량을 줄인다. 같은 Schedule로 구동하는 노드는 가상의 클러스터를 구성하며, 두 개의 다른 Schedule을 수신한 노드는 두 개의 다른 가상 클러스터에 속한다. Adaptive Listening은 전송 지연을 줄이는 방안이다.[25] 만약, 노드가 CTS(Clear to Send)를 Overhear(다른 노드로 전송되는 패킷을 불필요하게 수신하면서 에너지 낭비) 하면, 그 노드는 다른 노드의 Next Hop으로 역할을 하기 위하여 전송의 마지막 시점에서 잠깐 Wake-up을 해서 에너지를 낭비한다. S-MAC은 작은 Duty Cycle로 구동하기 때문에 노드의 에너지 소모를 줄인다. 그러나 몇 가지 단점이 있다. 첫째, Duty Cycle이 작아서 전송 지연이 증가할 수 있다. 둘째, 가상 클러스터에서 노드는 같은 Schedule로 구동하기 때문에 동적인 트래픽 처리에는 적절하지 않을 수 있다. 왜냐하면 각 노드가 다른 트래픽 량을 처리해야 할 경우, 모든 노드가 같은 Schedule로 구동한다면, 트래픽 처리가 제대로 되지 않을 수 있기 때문이다.

2. T-MAC

T-MAC[7]은 Adaptive Duty Cycle로 구동하는 S-MAC의 향상된 프로토콜이다. 특정 시간 T 동안, 노드가 Active 모드를 끝내기 전까지는 Sleep 모드로 전환할 수 없다. 이와 같은 Power Down 방식은 초기 Sleeping 문제를 발생시킬 수 있다. 이 문제가 발생하면 잠재적인 수신 노드가 빠르게 Sleep 모드로 전환할 수 있어서 Time Slot 내 패킷을 전송할 수 있는 Hop 수가 줄어들면서 전송을 보장할 수 없게 된다. 그리고 노드의 Active 주기를 정하는 방법을 제공하고는 있지만, 전송 지연은 증가시킨다는 단점이 있다.

3. DMAC

DMAC[15]은 Adaptive Duty Cycle로 구동하는 또 다른 프로토콜이다. Data-gathering Tree에 따라서 Active 모드 주기에 시간 차이를 두어 A Many to One Communication Model에서의 전송 지연을 줄인다. S-MAC과 비교하면 전송 지연, 전송률, 에너지 소모량 절감에서 더 나은 성능을 보여준다.

S-MAC, T-MAC, DMAC의 유사점은 주기마다 모든 노드가 Wake-up 해야한다는 점이다. 그래서 부하가 적은 노드는 주기마다 Idel 상태를 유지하면서 불필요하게 에너지를 낭비할 수 있다는 단점이 있다.

4. PMAC

PMAC[26]은 Listening 주기를 관리하는 프로토콜이다. 각 노드는 처리해야 할 트래픽에 따라서 Sleep/Awake 주기를 정한다. 더 많은 트래픽을 처리해야 하는 노드는 더 긴 Awake 주기를 가진다. 각 Time Slot에서 그 주기에 따라서 노드는 Sleep 모드로 전환할지 말지를 결정한다. 각 노드에 대한 Sleep과 Awake 주기는 해당 노드의 주기와 이웃 노드의 주기를 모두 고려하여서 정한다. 즉, 노드의 트래픽 량에 맞춰서 주기를 정하고, 그에 따라서 구동한다. PMAC은 노드 사이에서 교환되는 주기 정보에 의존한다는 단점이 있다. 그래서 노드가 이웃한 노드의 주기 정보를 정확하게 수신하지 못하면, 성공적인 전송을 보장할 수 없다. 그래서 Idle Listening으로 인한 에너지 낭비와 전송한 패킷의 손실이 발생할 수 있다. 또한, 전송 지연이 증가할 수도 있다.

5. B-MAC

B-MAC[18]은 Low Power Operation을 위하여 Lower Power Listening과 긴 프리엠블을 사용하는 비동기 MAC 프로토콜이다. B-MAC으로 구동하는 노드의 패킷 전송을 보장하기 위하여 노드는 목적지 노드로 충분히 긴 프리엠블을 전송해서 노드 사이의 Sync를 맞춘다. 예를 들면, 목적지 노드가 20ms 마다 채널을 확인한다면, 노드가 보내는 프리엠블은 최소 20ms이어야 하는 것이다. 목적지 노드가 프리엠블을 수신하면, 그 노드는 패킷을 수신하기 위하여 Awake 상태로 전환한다. 목적지 노드를 확인하기 위하여 각 노드는 프리엠블 전송을 끝낼 때까지 Awake 상태를 유지해야 하고 긴 프리엠블을 사용하기 때문에 에너지를 낭비하며, 전송 지연도 증가할 수 있다는 단점이 있다.

6. WiseMAC

WiseMAC[8]은 B-MAC과 유사한 방식으로 구동하는 프로토콜이다. WiseMAC으로 구동하는 목적지 노드는 ACK 패킷 내 추가 필드(특정 데이터 저장 영역)를 사용하여서 이웃 노드에 다음 Awake 시점을 알려준다. 이 정보를 받은 노드는 목적지 노드가 Wake-up 하기 직전부터 프리엠블을 전송하면 된다. 그래서 각 ACK 패킷 내 Expense of A Field에 긴 프리엠블과 이웃 노드의 주기 정보를 저장하고 이용하여서 에너지 소모량을 절감한다. 그러나 동적인 트래픽 처리에는 적합하지 않다는 단점이 있다.

7. X-MAC

X-MAC[3]은 B-MAC의 향상된 프로토콜이다. B-MAC에서 사용하는 긴 프리엠블은 X-MAC에서는 연속적인 Small Pause에 의해서 분리된 여러 개의 짧은 프리엠블로 대체된다. Pause는 목적지 노드가 요구하는 것보다 먼저 ACK 패킷을 보내도록 하여서 프리엠블의 전송을 예정된 것보다 빠르게 끝내도록 한다. 각각의 짧은 프리엠블은 목적지 노드의 주소를 포함하고 있기 때문에 목적지가 아닌 노드가 에너지를 낭비하는 문제를 개선할 수 있다. B-MAC에 비해서 짧은 프리엠블을 사용하여서 전송 지연을 줄이고, 에너지 소모량을 절감할 수 있다는 장점이 있다. 그러나 동기 MAC 프로토콜보다는 더 많은 프리엠블을 전송하기 때문에 에너지 소모를 증가시킨다는 단점도 있다.

Preliminaries

다음과 같은 가정을 한다.

• 전체 시간은 연속적인 Time Slot으로 나누어진다.
• 모든 노드의 Sync는 맞춰진 상태이다.
• 각 노드는 유일무이한 ID를 가진다.
• 노드는 균등하게 배치된다.
• 모든 노드는 패킷을 공통의 싱크 노드로 전송한다.
• 모든 노드는 같은 전송 범위를 가진다.
• 모든 노드는 배치된 후, 고정된다.

모든 노드는 [22]처럼 싱크 노드를 중심으로 한 원형에 배치된다. 이 원형은 아래 그림처럼 싱크 노드를 기준으로 한 거리(By Hop Count)차에 따라서 대략 같은 폭의 여러 광원으로 부터 구성된다.

네트워크 구성 예시

원형을 구성하기 위하여 싱크 노드는 네트워크 초기 설정 단계에서 Field Hop Count=1을 갖은 제어 패킷인 NET_INIT을 가장 인접한 노드에 전송한다. 이 패킷을 수신한 각 노드는 Hop Count Field를 1 증가시키고, 해당 패킷을 다른 인접한 노드들에 브로드캐스팅 한다. 즉, Hop Count=i인 NET_INIT을 수신한 노드는 C(i)에 속하는 것이다. 다수의 NET_INIT 패킷을 수신한 노드는 가장 작은 Hop Count의 값만을 처리한다.

C(i)의 노드는 싱크 노드로부터 i Hop 수 만큼 떨어진 곳에 있는 것이고, C(i)의 노드가 싱크 노드로 전송되는 패킷을 전달하기 위하여 C(i-1)에 있는 노드의 영향을 받는다.

1. 문제 정의

에너지 홀 문제의 기존 해결 방안은 적절하게 노드를 분포시키는 것이다. 그러나 적절하게 노드를 분포하는 것이 가능하지 않은 환경이 있다. 그래서 Network Lifetime을 연장하려면, 다른 Power Saving 프로토콜(S-MAC, T-MAC, DMAC, PMAC)이 필요하다.

그러나 S-MAC, T-MAC, DMAC으로 구동하는 노드의 문제 중 하나는 Pending 된 패킷이 있는지를 확인하기 위하여 Time Slot마다 Wake-up 해야 한다는 것이다.

모든 노드가 같은 Schedule로 구동하는 상황에서 각 노드가 처리해야 하는 트래픽(싱크 노드에 가까운 노드일수록 부하가 큼)이 다르면, Listen/Sleep 모드로 인하여 패킷을 효율적으로 처리하지 못하면서 에너지를 낭비할 수 있다.

PMAC은 노드들이 다른 Listen/Sleep 빈도를 갖도록 하여서 에너지를 효율적으로 사용하게 하지만, 노드 사이에서 교환되는 정보에 의존한다.

각 노드가 Wake-up Schedule을 선택하는 방식은 에너지 사용의 효율성을 증가시킬 수는 있겠지만, 노드들이 잘 관리되지 않으면, 안정적인 전송을 보장하지 못할 수가 있다.

예를 들면, 아래 그림처럼, Host B가 Host A보다 항상 한 Time Slot 후에 Wake-up 한다면, 두 Host 즉, 0.5(두 Time Slot마다 Wake-up)의 같은 Wake-up Schedule을 갖는 A와 B는 결코 통신을 할 수가 없다.

두 Host 사이의 통신 불능 예시

결국, 계획적으로 노드를 배치할 수 없는 환경에서 에너지 홀 문제를 해결할 수 있는 방안은 Power Efficient 프로토콜이다. 이 프로토콜은 노드들의 트래픽에 따라서 각 노드의 Listen/Sleep 빈도를 맞출 수 있기 때문에 노드 사이의 안정적인 통신을 보장할 수 있다.

Edit by

맹주현
한양대학교 컴퓨터·소프트웨어학과 박사과정
maengjuhyun@gmail.com
관심 분야 : Blockchain, Network

참고 문헌

• A Quorum-Based Energy-Saving MAC Protocol Design for Wireless Sensor Networks, 2010

그림 출처

• 네트워크 구성 예시
  A Quorum-Based Energy-Saving MAC Protocol Design for Wireless Sensor Networks
• 두 Host 사이의 통신 불능 예시
  A Quorum-Based Energy-Saving MAC Protocol Design for Wireless Sensor Networks