[Quorum] Quorum MAC::Paper 2

Published in

juhyun.maeng

33 min readJan 11, 2020

무선 센서 네트워크에서 노드의 저 전력을 구현하는 것은 매우 중요합니다. 그래서 Quorum으로 MAC Protocol의 저 전력을 구현한 논문을 분석하면서 노드의 저 전력을 구현할 방안을 찾고자 합니다.
이번 게시글은 “An Adaptive Quorum-Based Energy Conserving Protocol for IEEE 802.11 Ad Hoc Networks” 논문에 대한 글로써, 이 논문을 분석한 내용을 다룹니다.

Abstract

Mobile Ad Hoc Network(MANET)의 Lifetime은 Mobile Host의 배터리 자원에 영향을 받는다. IEEE 802.11의 Power Saving 모드로 구동하는 Host는 Awake 상태를 유지해야 하는지를 판단하기 위하여 Beacon Interval마다 Wake-up 한다. 그러한 기법은 Power Efficiency를 줄이기 때문에 트래픽에 따라서 Sleep Duration을 정하는 것에 실패할 수 있다.

그래서 Single Hop MANET에서 Power Saving 하는 새로운 MAC Protocol을 제안한다. 이 프로토콜의 핵심은 Quorum-based Sleep/Wake-up 메커니즘이다. 만약, 특정 Host가 전송에 조금이라도 관여하면, 그 메커니즘은 Host가 한 Beacon Interval 이상 동안, Sleep 모드를 유지하도록 하여서 에너지를 보존한다.

시뮬레이션 결과로 제안하는 프로토콜이 더 많은 에너지를 보존하고, MANET의 Lifetime을 연장한다는 것을 증명한다.

INTRODUCTION

MANET은 사전 구축한 Base Station Infrastructure 없이도 Mobile Host의 클러스터로 구성할 수 있다. MANET에서 Host는 다른 Host와 Roam과 통신을 한다. 만약, 두 Host가 가까이 위치한다면, 전송 파워는 제한되므로, Host의 전송되는 패킷을 Relay 하는 중개 Mobile Host를 통하여 두 Host는 서로 직접 혹은 간접적으로 통신한다.

모든 Host가 서로의 전송 범위 내에 있다면, 각 Host는 Single Hop MANET을 구성한다. 제안하는 프로토콜은 Single Hop MANET에서 구동한다.

MANET의 이점 중 하나는 Base Station이나 Network Infrastructure가 필요 없으므로 빠르고 쉽게 네트워크를 구성할 수 있다는 점이다. 그리고 Network Infrastructure의 사전 구축이 어렵거나 불가능한 곳에서도 MANET을 구성할 수 있다.

Host를 에너지 없이는 이용할 수 없으므로 MANET의 중요한 이슈 중 하나는 Power Saving이다. Host의 배터리는 제한된 에너지만을 제공한다. 그래서 Host에 대한 Energy Efficient Protocol을 설계하는 것은 MANET의 운영에 매우 중요하다. 최근, 무선 센서 네트워크를 위한 많은 Power Saving Protocol이 제안되었다. Operation Layer에 따라서, Power Saving Protocol은 MAC(Medium Access Control) Layer Protocol[5, 6, 13, 23, 24], Routing Layer Protocol[7, 8, 26], Transport Layer Protocol[4, 27]로 분류된다. 대부분의 MAC Layer Power Saving Protocol은 ATIM Window의 크기를 조절하거나[13] 혹은 새로운 Access Mechanism[23]으로 ATIM(Ad hoc Traffic Indication Message) Window를 개선하려고 한다. 제안하는 프로토콜은 MAC Layer Protocol이다. Routing Layer Power Saving Protocol은 에너지 소모량을 최소화하는 경로 탐색[8]과 에너지 소모량을 최소화하는 전송기법[26]의 모색에 집중한다. Transport Layer Energy Efficient Protocol은 전송하는 패킷을 줄여서[4] 에너지 소모량을 절감하려고 한다.

무선 인터페이스 카드는 세 가지 상태(Awake, Doze, Off) 중 하나로 구동한다. Awake 상태 동안, Host는 다른 양의 에너지를 소모하면서 Transmit, Receive, Idle 모드로 구동한다. Doze 상태 동안, Host는 Sleep 모드를 유지하며, Active 모드 동안 소모하는 에너지보다 적은 양의 에너지로는 패킷의 송·수신을 할 수 없다. 그리고 Host는 250 us 내에 Awake 상태로 전환할 수 있다.(WaveLan-II PCMCIA Card[14]) Off 상태 동안, Host는 Off 하면서 에너지를 소모하지 않는다. Transmit, Receive, Idle, Sleep 모드에 대한 Lucent IEEE 802.11 WaveLan Card의 에너지 소모량은 각각 284mA, 190mA, 156mA, 10mA이다.

Host는 전송에 관여하지 않으면, 에너지를 보존하기 위하여 Sleep 모드를 유지한다.

IEEE 802.11은 채널에 접근하는 두 메커니즘(Distributed Coordinated Function(DCF), Point Coordinated Function(PCF))을 정의한다. DCF는 접근 메커니즘으로 CSMA/CA를 사용하는 Contention-based Scheme이고, 완전히 분산된 프로토콜이다. PCF는 Coordinator로 AP(Access Point)를 사용하는 Contention-free Scheme이고, 중앙화된 프로토콜이다. 이 논문에서는 DCF Operation 기반으로 에너지 소모량을 절감하는 메커니즘을 제안한다.

IEEE 802.11 Power Saving Mode(PSM)[12]로 구동하는 각 Host는 다른 Host와 Sync가 맞춰진 상태인 것으로 가정한다. 시간은 연이은 Beacon Interval로 분할된다.

각 Beacon Interval의 초기에, 각 Host는 AITM Window라고 불리는 특정 Duration 동안 Awake 상태를 유지한다. ATIM Window는 Pending 된 패킷을 가진 Host가 이 사실을 주변 Host에 알리는 데 사용하는 Duration이다. 주변 Host는 Awake 상태를 유지해야 할지를 판단하기 위하여 이 알림을 Listen 한다. 이 기법은 트래픽에 따라서 Host의 Sleep Duration을 조절하는 것을 실패시킬 수 있다.

많은 패킷을 전송하려는 Host가 빈번하게 Wake-up 하는 것은 적합하다. 그리고 적은 패킷을 전송하려는 Host는 에너지를 보존하기 위하여 Sleep Duration을 연장할 수 있다. 그러나 Sleep Duration을 연장하면 에너지 소모량을 절감하지만 지연을 발생시킬 수 있다. 그래서 이 논문에서는 Host가 에너지를 보존하기 위하여 덜 빈번하게 Wake-up(연이은 Interval 동안 Sleep) 하면서 지연과 Awake 유지시간 사이에 대한 최적의 Trade-off를 구현하는 확률을 찾고자 한다.

연이은 Beacon Interval 동안, Host의 Sleep으로 Lifetime을 연장하는 Quorum-based Protocol을 제안한다. Quorum의 특징을 따르는 Host는 동시에 발생하는 Beacon Interval 동안 Awake 상태가 된다. 제안하는 프로토콜의 기본 아이디어는 에너지를 보존하기 위하여 Host의 Sleep Duration을 연장하는 것이다. 이 연장으로 지연은 증가할 수 있다. Wake-up 빈도는 Host의 트래픽 부하에 따라서 정한다. 제안하는 기법으로 다른 Quorum 크기를 가지는 다수의 Host는 Power Efficiency와 지연 사이의 균형을 맞출 수 있을 것이다.

PRELIMINARIES

모든 Host는 서로 시간 동기화를 하고, IEEE 802.11 PSM처럼, 완전히 연결된 방식으로 구성된다고 가정한다.

1. Power Saving Modes in IEEE 802.11 DCF

앞서 말한 것처럼, 시간은 연이은 Beacon Interval로 나뉜다. Clock 동기화를 하기 위하여 사용되는 각 Beacon Interval의 초기에, Host는 Beacon Frame을 전송하기 위해 다른 Host와 경쟁한다. 각 Host는 경쟁으로 무작위의 지연을 할 것이기 때문에 지연 시간 동안 대기한다. 만약, 특정 Host가 또 다른 Host로부터의 Beacon을 수신하면, 그 Host는 타이머가 만기 되기 전에 무작위의 지연 타이머를 무효화 한다. 그렇지 않으면 무작위의 지연 타이머가 만기 될 때, Host는 Beacon을 전송한다.

IEEE802.11 PSM으로 구동하는 Host는 Awake 상태나 혹은 Sleep 모드 중 하나이다. Host는 Awake 상태 동안 구동하므로, 이 상태에서는 언제든지 패킷을 송·수신할 수 있지만, Host가 Sleep 모드면, 송·수신을 할 수 없다.

Host는 Pending 된 패킷이 있는지를 확인하기 위하여 모든 Beacon Interval 초기의 ATIM Window 동안 Awake 상태가 된다. 패킷이 있다면, Host는 Awake 상태를 유지한다. 또 다른 Host에 전송할 Pending 된 패킷을 가진 Host는 ATIM Window 동안 다른 Host에게 이 사실을 알린다. 이 알림은 ATIM Frame을 전송하면서 수행된다. 각 Host는 나머지 Beacon Interval 동안, Awake 상태를 유지해야 할지를 결정하기 위하여 이 알림을 관찰한다. ATIM Frame을 수신한 Host는 바로 ATIM-ACK Frame으로 응답한다. ATIM Frame을 수신하지 못한 Host는 ATIM Window의 마지막 시점에서 Sleep 모드로 전환한다.

실제 패킷의 이동은 ATIM Window 후, 수행된다. IEEE 802.11 PSM의 구동과정(Host B -> Host C)은 아래 그림과 같다.

첫 Beacon Interval 동안, Host A는 Beacon을 브로드캐스팅 한다. ATIM Window 후, 모든 Host는 Sleep 모드로 전환하고, 이후 어떠한 Host도 패킷 전송을 하지 못한다. 두 번째 Beacon Interval 동안, Host C가 Beacon을 브로드캐스팅 한 후, Host B는 ATIM Window 동안, ATIM Frame을 Host C로 전송하고, Host C로부터 ATIM-ACK Frame을 수신한다. Host B와 C는 전체 Beacon Interval 동안, Awake 상태를 유지한다. ATIM Window 후, Host B는 Host C로 패킷을 전송한다.

2. Problem Statement

IEEE 802.11 PSM으로 구동하는 Host는 모든 Beacon Interval 내에서 Wake-up하고, ATIM Window 동안, Awake 상태를 유지한다. 그리고 Host는 송·수신을 하지 않으면, Sleep 모드로 전환한다. 만약, Host가 몇몇 연이은 Beacon Interval 동안, 송·수신에 관여하지 않으면, 빈번한 Doze-to-awake와 Awake-to-doze의 전환으로 불필요하게 많은 에너지를 소모할 수 있다. 게다가, IEEE 802.11 PSM은 ATIM Window(Beacon Interval의 1/5)의 고정값, Host의 Sleep Duration의 고정값, Host가 트래픽에 따라서 Sleep Duration을 조절할 수 없다는 것을 나타내는 Beacon Interval(0.1s or 0.2s) 값을 정한다.

IEEE 802.11 PSM의 Power Inefficiency Problem을 해결하기 위하여 Host의 트래픽 부하가 적으면, 그 Host의 Sleep Duration은 연장된다. 그러나 Sleep Duration의 적절한 관리가 없다면, 두 Host는 동시에 Wake-up 하지 못하면서 통신을 할 수 없을 수도 있다. 즉, Power Saving뿐만 아니라 패킷의 전송을 보장하는 프로토콜은 Power Inefficiency Problem을 해결하는 데 필요하다. 게다가, IEEE 802.11 PSM으로 구동하는 Host는 과도한 경쟁으로 많은 Beacon 전송에 실패하면서 추가적인 에너지를 소모할 수 있다. Host의 Sleep Duration을 증가시키면 경쟁 확률을 줄일 수는 있을 것이다.

RELATED WORKS

DPSM[13]으로 구동하는 각 Host는 네트워크 상태에 따라서 ATIM Window의 크기를 동적으로 정한다. Host는 허용되는 값의 유한 집합 내에서 특정 ATIM Window의 크기를 정할 것이다.

DPSM은 ATIM Window의 크기를 증가 및 감소시키는 조건을 정의한다. 처음에 각 Host는 가장 작은 ATIM Window를 사용한다. 만약, 증가에 대한 조건이 충족되면, Host는 이 크기를 허용되는 집합 내에서 다음보다 더 큰 값으로 증가시킨다. 만약, 감소에 대한 조건이 충족되면, Host는 ATIM Window의 크기를 허용되는 집합 내에서 다음보다 더 작은 값으로 감소시킨다.

DPSM은 IEEE 802.11 PSM을 개선한 것이다. 동적 Window의 크기는 Throughput과 Energy Efficiency를 향상시킬 수 있다. 그러나 DPSM으로 구동하는 Host는 여전히 모든 Beacon Interval 동안 Awake 상태이어야 한다. 그래서 IEEE 802.11 PSM처럼, 적은 부하를 가진 Host는 불필요한 에너지를 소모할 수 있다.

Span[8]은 또 다른 Energy Saving Protocol이다. Span으로 구동하는 각 Host는 Coordinator가 되기 위한 조건의 충족 여부에 따라서 Coordinator 혹은 Non Coordinator가 될 수 있다. Span Coordinator는 패킷 라우팅을 수행하기 위하여 지속해서 Awake 상태를 유지하고, 반면에 Span Non Coordinator는 IEEE 802.11 PSM의 운영 방식을 따른다. Pending 된 패킷을 가진 Host는 ATIM Window 동안 ATIM 알림을 한다. 이 기법으로 Host는 여전히 Pending 된 패킷이 있는지를 주기적으로 확인하기 위하여 Wake-up 한다.

Multi-hop MANET을 위하여 설계된 몇몇 Power Saving Protocol은 Tseng 외[23]에서 확인할 수 있다. 이러한 프로토콜은 어떠한 Clock 동기화 메커니즘도 사용될 수 없는 환경을 고려하면서 설계되었다.

비동기 ATIM Window를 가진 Host는 다른 시간에 Wake-up 할 수도 있다. 이 경우, IEEE 802.11 Power Saving Mode는 잘 구동되지 않을 수 있다. 이 문제(동시에 Host가 구동하지 않음)를 해결하는 방안은 Host의 Active 시간을 연장하여서 Overlapping Awake Interval을 사용하는 것이다. 그러나 분산된 시간 동기화 메커니즘은 Single Hop MANET[11, 16]과 Multi-hop MANET[20]에 존재한다. 그러므로 Overlapping Awake Interval을 사용하기 위하여 과도한 에너지 소모를 하는 Host의 Active Duration을 연장하는 것은 불필요하다.

ATSP[11]는 MANET에서 시간 동기화를 구현하기 위하여 제안되었다. ATSP는 IEEE 802.11처럼, 나중에 다른 Host와 시간 동기화를 하는 기법을 분석하면서 고안하였다. 그러므로 ATSP는 Beacon 전송 빈도를 증가시키면서, 가장 빠른 타이밍을 가진 Host에 Beacon을 전송할 수 있는 가장 높은 우선권을 준다. 그래서 타이밍이 늦은 Host의 Beacon 전송 빈도는 감소한다. ATSP는 시간 비동기 문제를 개선한다. 그러나 가장 빠른 타이밍을 가진 Host가 네트워크를 이탈하면, 몇몇 다른 Host의 Clock은 수백 us까지 변할 수 있다. 이 문제를 해결하기 위하여, ATSP를 수정한 TATSP가 제안되었다.[16] ATSP와 TATSP는 Single Hop MANET에서 Host의 Clock 동기화를 구현한다. 그러나 두 가지 알고리즘은 Multi-hop MANET에는 적용할 수 없다.

ASP[20]는 Multi-hop MANET에서의 시간 동기화 문제를 해결하는 방안이다. 만약, 충분한 타이밍 정보를 수집하면, ASP는 Host가 Self-synchronization을 수행할 수 있도록 한다. 더 빠른 타이밍의 Host에 대한 전송 확률은 높아져야 하고, 더 빠른 타이밍 정보는 모든 네트워크에 공유되어야 한다. ASP는 처음에 더 빠른 타이밍의 Host에 대한 Beacon 전송의 우선권을 증가시키고, 다른 Host의 우선권은 감소시킨다. 그리고 더 느린 타이밍의 Host가 직접 동기화를 위하여 정보를 모으려 할 때, Host에 대한 Beacon 전송의 우선권은 증가할 수 있다.

PROTOCOLS DESCRIPTION

Quorum-Based Energy Conserving(QEC)와 Adaptive Quorum-Based Energy Conserving(AQEC) MAC Protocol을 제안한다. 두 프로토콜은 에너지를 보존하고, Quorum으로 동일 Beacon Interval 동안, 특정 두 Host가 동시에 Wake-up 하도록 한다.

두 프로토콜의 상세한 설명과 지연을 줄이는 기법을 설명한다.

1. Quorum-Based Energy Conserving (QEC) Protocol

IEEE 802.11 PSM처럼, QEC의 시간은 Beacon Interval로 나뉘고, 각 연이은 n²의 Beacon Interval은 Quorum Group으로 정의된다. 이 n²의 Interval은 n X n 그리드로 배열되고, n은 Global Parameter를 나타낸다. 시스템 내 모든 Host는 같은 n을 선택한다.

QEC는 많은 Awake Interval을 줄여서 에너지 소모량을 절감한다. n X n의 그리드를 사용하는 각 Host는 2n-1/n² Interval 동안 Awake 상태를 유지한다. IEEE 802.11 PSM처럼, ATIM 알림을 하기 위하여 Host는 최소 ATIM Window의 Duration 동안, Awake 상태에서 한 행과 한 열을 무작위로 Quorum Interval로 선택한다. Non-quorum Interval의 Host는 전체 Beacon Interval 동안 Sleep 한다.

모든 Host 사이의 Quorum 그룹에 대한 시작점은 동기화를 하였다고 가정한다.

Theorem 1

만약, 모든 Host 사이의 Quorum 그룹에 대한 시작점이 동기화를 하였다면, Grid-based QEC로 구동하는 두 Host는 모든 n²의 연이은 Beacon Interval 동안 적어도 두 교차점을 가질 것이다.

그리고 특정 Host가 QEC 운영에 참여하려면, 우선 다른 Host와 동기화를 해야 한다. 새로운 Host는 다른 Host와 동기화를 한 후, 다음 Beacon Interval에서 QEC 운영에 참여한다. 만약, n의 Beacon Interval 후, 새로운 Host가 특정 Beacon Frame을 수신하지 못하면, 주변에 Host가 없다고 판단하고, 자체 QEC 운영을 시작한다.

Power Saving 운영에 합류하는 새로운 Host는 다음과 같이 구동한다.

Host는 다른 Host와 동기를 맞추기 위하여 최대 n의 Beacon Interval 동안 채널을 관찰한다.
n의 Beacon Interval 동안, Beacon을 수신하면, Host는 기존 Host와 동기를 맞출 수 있고, 다음 Beacon Interval에서 QEC로 구동한다.
n의 Beacon Interval 후, 어떠한 Beacon도 수신하지 못하면, Host는 주변에 다른 Host가 없다고 판단하고, 다음 Beacon Interval에서 QEC로 구동한다.

특정 두 Host가 n²의 Beacon Interval마다 적어도 두 교차점을 가져야 한다는 조건을 충족하기 위해서 그리드를 무작위로 배열할 수는 없다. 아래 그림은 만족스럽지 못한 4 X 4인 그리드의 예시이다. 두 Host는 Quorum Interval로 각각 1번째 행과 4번째 열을 선택한다. Host B는 Host A보다 한 Beacon Interval만큼 늦은 Quorum의 그룹으로 구동한다. 그래서 아래 그림처럼, 두 Host는 결코 통신할 수 없다.

특정 두 Host 사이에 적어도 두 교차점이 있으려면, n X n의 그리드 g로 n²의 Beacon Interval을 배열할 때, 그리드 할당 규칙을 따라야 한다.

Grid Allocation Rule 1

g의 각 행은 n mod n²의 연이은 Beacon Interval로 구성된다.

Grid Allocation Rule 2

g의 각 열은 ∀m ∈ [1, 2, …, n²], {[m, m+1, …, m+n-1](mod n²)}의 연이은 Beacon Interval로 다른 n 열에 배열된다.

그리드 할당 규칙에 따라서 구성된 그리드는 Legal Grid라고 한다. 행과 열의 역할은 교환될 수 있다. 아래 그림은 Legal Grid의 예시이다.

(a)는 기본적인 그리드이며, 다른 그리드에 대한 변경은 기본 그리드를 기준으로 한다. (b)는 1번째와 3번째 열을 교환한다. (c)는 1번째와 3번째 행을 교환한다. (d)는 각각의 행과 열을 도치한다. (e)는 전체 그리드를 도치한다. (f)는 한 Beacon Interval 만큼 뒤로 이동한다.

Theorem 2

그리드 할당 규칙에 따라서, Grid-based QEC로 구동하는 두 Host는 매 n²의 연이은 Beacon Interval 동안 적어도 두 교차점을 가진다.

2. Adaptive Quorum-Based Energy Conserving(AQEC) Protocol

QEC로 구동하는 모든 Host는 n X n의 동일한 크기의 그리드를 사용한다. 그리드의 크기를 정하는 것은 중요하다. 그리드의 크기가 크면 Power Saving을 하지만, 지연은 증가될 것이다. 반면에, 그리드의 크기가 작으면 에너지 소모량은 증가할 것이다.

각 Host는 다른 트래픽 부하를 처리하고, 다른 성능을 요구받기 때문에 그리드의 크기를 동적으로 조절할 필요가 있다. 이를 위하여, Adaptive Quorum-Based Energy Conserving(AQEC) Protocol을 제안한다. AQEC는 트래픽이 적으면, Sleep Duration을 연장하기 위하여 Host가 사용하는 그리드의 크기를 증가시킨다. 그리고 트래픽 부하가 많으면, 그리드의 크기를 줄이면서 더 빈번하게 Wake-up 한다. AQEC의 Host i는 트래픽 부하(LDi)에 따라서 그리드의 크기를 정하며, 3개의 트래픽 임계값을 사용한다.

AQEC로 구동하는 Host i는 임계값인 Threshold_1, Threshold_2, Threshold_3으로 그리드의 크기를 선택한다.

IEEE 802.11 PSM의 시뮬레이션 결과에 따라서, Channel Capacity는 2Mbps 이다.(Host의 수는 30~150, 패킷의 크기는 128bytes~1,024bytes)

모든 Host의 Packet Arrival Rate이 12Kbps를 초과하면, 지연은 급격히 증가된다. 각 Host의 트래픽 부하가 12Kbps를 넘는 과부하 상태의 네트워크 환경을 고려한다. 그러므로 트래픽 부하가 12Kbps를 초과하면 그리드의 크기를 1 X 1로 설정한다. 즉, Threshold_1을 12Kbps로 설정한다. Threshold_1은 시뮬레이션 시나리오에 따라서 정해지며, Threshold의 값은 환경에 따라 조절할 수 있다. 트래픽 부하가 적으면, Host의 Wake-up 빈도는 줄어야한다. Threshold_2와 Threshold_3은 Wake-up 빈도에 비례하여서 정해진다.

n X n의 그리드에서 n²의 Beacon Interval 중 2n-1을 Quorum Interval로 선택한다. 즉, n X n의 그리드를 사용하는 Host는 2n-1/n² 만큼 Wake-up 한다. Host의 Packet Arrival Rate이 2n-1/n²으로 낮아지면, n X n인 그리드의 크기를 증가시켜야 한다.

Threshold_1은 12Kbps인, Threshold_2와 3의 계산 과정 예시

이러한 값이 설정된 Host는 에너지를 보존하기 위하여 트래픽 부하에 따라서 최상의 그리드 크기를 선택할 수 있다.

다른 그리드의 크기를 사용하는 두 Host는 서로 교차할 것이다. 예를 들면, 아래 그림처럼, Host A는 2 X 2의 그리드를 사용하고, Quorum Interval은 0, 1, 2이다. Host B는 3 X 3의 그리드를 사용하고, Quorum Interval은 2, 5, 6, 7, 8이다. Host A는 Host B보다 더 빈번하게 Wake up하고, 두 Host 사이에는 교차점이 존재한다.

2 X 2의 그리드를 가진 Host A와 3 X 3의 그리드를 가진 Host B 사이의 통신 예시

Theorem 3

그리드 할당 규칙에 따르고, 각 크기가 m X m과 n X n인 그리드를 사용하는 AQEC로 구동하는 두 Host는 Quorum 그룹의 시작점이 동기화를 하지 않았더라도 서로 교차할 수 있다.

제안하는 알고리즘은 크기가 n X m(n≠m)인 그리드에 적용될 수 있다. n X m의 그리드 g에 배열할 때, 그리드 할당 규칙을 따라야 한다.

Grid Allocation Rule 1`

g의 각 행은 m mod n X m의 연이은 Beacon Interval로 구성된다.

Grid Allocation Rule 2`

g의 각 열은 ∀ω ∈ [1, 2, …, n X m], {[ω, ω+1, …, ω+m-1](mod n X m)}의 연이은 Beacon Interval로 다른 m 열에 배열된다.

QEC와 AQEC로 구동하는 Host는 한 Beacon Interval 보다 더 오랫동안 Sleep 할 수 있다. 그러므로 이 두 프로토콜은 IEEE 802.11 PSM보다 더 큰 지연을 발생시킨다. 그래서 지연을 줄일 수 있는 방안을 제안한다. Original Protocol과 구별하기 위하여 QEC+와 AQEC+처럼 프로토콜 명에 +를 붙인다.

QEC+와 AQEC+로 구동하는 Host는 패킷을 전송할 때, Beacon Interval 마다 Awake 상태를 유지한다. 즉, Host는 Packet이 Pending 되면, Quorum Interval 동안만이 아닌, Beacon Interval 마다 Wake-up 해야 한다. 아래 그림처럼, Host A의 Quorum Interval은 0, 1, 2, 3, 6이고, Host B의 Quorum Interval은 2, 5, 6, 7, 8이다. Host A와 B는 Interval 2와 6에서 교차점을 가진다. QEC+와 AQEC+로 구동하는 Host A는 Interval 3에서 Host B로 전송해야 할 패킷을 가지기 때문에 패킷의 전송을 완료할 때까지 Beacon Interval 마다 Wake-up 한다.

QEC+/AQEC+ Protocol로 구동하는 Host A가 Pending 된 패킷을 가지면, 증가하는 Wake-up의 예시

SIMULATION RESULTS

제안하는 QEC/QEC+와 AQEC/AQEC+ 프로토콜은 ns-2[1] 시뮬레이터(CMU 무선과 모바일 확장, Version ns-allinone-2.1b9a[2])로 성능을 평가한다. 채널 접근의 관리를 위하여 CSMA/CA를 사용하고, 시뮬레이터의 기본 무선 전파 모델을 시뮬레이션에 사용한다.(경로 손실 지수는 4로 설정하고, 안테나 이득은 12dB로 설정, 등등)

DPSM과 IEEE 802.11은 비교를 위하여 구현한다. Host는 무작위로 200m X 200m의 영역 내 50개를 배치한다. 이 Host의 절반은 Source이고, 나머지는 Destination이며, Source-destination 쌍은 무작위로 선택한다. 각 Host의 Channel Capacity는 2Mbps이고, 전송 범위는 300m이다. Host는 이동하지 않는다고 가정하고, Beacon Interval은 200ms로 설정한다. DPSM의 ATIM 값은 2ms~100ms이고, 다른 프로토콜의 값은 40ms이다. 패킷의 크기는 128bytes이고, 적은 부하와 많은 부하에 대하여 모두 시뮬레이션하기 위해 Host가 초당 1~24 Packet의 Bit Rate Traffic을 생성하게 한다. Chen 외[8]의 에너지 소모 모델을 사용한다. 이 모델은 2Mbps로 운영되는 Cabletron Roamabout 802.11 DS High Rate network interface card에 의해서 측정된 치수(크기/길이/양)를 사용한다. 각 Transmit, Receive, Idle, Sleep 모드의 에너지 소모량은 1,400mW, 1,000mW, 830mW, 130mW이다. 각 Host의 초기 에너지양은 500J이다.

각 시뮬레이션은 300s 간 변함없는 Bit Rate Connection을 한다. 최대 표준 편차는 약 4%이고, 신뢰 수준(X - 1.96σ/3.16, X + 1.96σ/3.16)은 신뢰 구간을 가진 95%이다. X는 표본평균이고, σ은 표본의 표준편차이다.

아래처럼, 3가지 측면으로 분석한다. 그리고 각 n X n의 그리드를 사용하는 QEC와 QEC+를 QECn과 QECn+로 표기한다.

1. Effect of Different MAC Protocol

제안하는 MAC Protocol의 Alive Hosts에 대한 성능을 분석한다.

시뮬레이션은 1,000s 동안 수행하고, Living Hosts의 수를 50s마다 기록한다. 각 Power Saving Protocol이 낼 수 있는 최상의 결과를 분석하기 위하여 처음 Zero Workload로 실험한다.

아래 그림처럼, 802.11과 802.11 PSM을 비교하면, DPSM과 제안하는 프로토콜은 Network Lifetime을 연장한다. 그리고 제안하는 프로토콜은 DPSM 보다 더 많은 에너지를 보존한다.

아래 그림처럼, 128bytes의 패킷에 대한 성능을 분석한다. 802.11로 구동하는 Host는 550s 후, 에너지를 모두 소모한다. 700s 후, 802.11 PSM으로 구동하는 모든 Host는 에너지 전부를 소모한다. 반면, QEC로 구동하는 Host의 그리드 크기별(2 X 2, 3 X 3, 4 X 4) 각 Alive의 백분율은 28%, 34%, 44%이다. 700s에 QEC+로 구동하는 Host의 그리드 크기별(2 X 2, 3 X 3, 4 X 4) 각 Alive의 백분율은 14%, 20%, 29%이다.

DPSM은 802.11 PSM 보다 더 나은 성능을 내지만, 제안하는 프로토콜보다는 좋지 않다.

다른 MAC Protocol에 대한 One-hop 지연은 아래 표와 같다. 제안하는 프로토콜, 802.11 PSM, DPSM을 포함하는 모든 Power Saving Protocol은 802.11보다 더 큰 지연을 발생시킨다. DPSM은 모든 Power Saving Protocol 중, 가장 짧은 지연을 발생시키는 802.11 PSM 보다 약간 더 긴 지연을 한다. AQEC와 AQEC+는 802.11 PSM 보다 각각 약 30ms와 24ms만큼 지연을 증가시킨다. QEC/AQEC 보다 QEC+/AQEC+가 상대적으로 짧은 지연을 발생시키기 때문에 데모에 QEC+/AQEC+를 사용한다.

여러 MAC 프로토콜에 대한 지연 시간 예시 (괄호 안의 수는 표준 편차)

2. Effect of Packet Size

제안하는 MAC Protocol의 Packet Size에 따른 성능을 분석한다.

패킷의 크기를 달리하면서 시뮬레이션 결과를 분석한다. 128bytes와 1,024bytes에 대한 시뮬레이션 결과는 아래 그림[Alive Hosts]과 같다. AQEC+가 가장 많은 에너지양을 보존한다. 패킷 크기가 128bytes면, 802.11로 구동하는 Host는 550s 후, 에너지를 모두 소모한다. 그리고 700s 후, 모든 802.11 PSM으로 구동하는 Host는 에너지를 전부 소모한다. AQEC+와 DPSM으로 구동하는 각 Host는 36%, 22%만큼 Alive이다. 패킷의 크기가 1,024bytes면, 802.11과 802.11 PSM으로 구동하는 Host는 550s와 700s 후, 에너지를 모두 소모한다. 700s에서 AQEC+와 DPSM으로 구동하는 각 Host는 15%, 8%만큼 Alive이다. 큰 패킷은 트래픽 부하를 증가시키고, 더 많은 에너지를 소모한다.

패킷의 크기가 다른 경우에 발생하는 지연은 아래 그림[Latency]과 같다. 802.11 PSM은 모든 Power Saving Protocol 중, 가장 짧은 지연을 하며, 패킷이 커지면 지연은 증가한다. 왜냐하면, 패킷이 크면 Host는 채널 접근의 권한을 얻기 위하여 더 빈번하게 다른 Host와 경쟁하면서 시스템의 트래픽 부하를 증가시켜서 지연이 길어지게 한다. DPSM은 802.11 PSM 보다 더 긴 지연인 2ms~8ms를 발생시키고, AQEC+는 DPSM 보다 더 긴 지연인 20ms~22ms를 발생시킨다.

모든 프로토콜의 Packet Drop Ratio는 아래 그림[Packet Drop Ratio]과 같다. 일반적으로, Packet Drop Ratio는 패킷이 커지면 증가한다. 왜냐하면, 패킷이 크면 시스템의 부하가 증가하기 때문이다. 802.11은 AQEC+와 802.11 PSM 다음의 성능을 보여준다. DPSM은 가장 큰 Packet Drop Ratio를 발생시킨다. 이것은 ATIM Window 크기의 부적절한 설정 때문이다. DPSM은 큰 트래픽 부하를 빠르게 처리할 수 없는 최소 ATIM Window의 크기(2ms)로 구동한다. QEC+로 구동하는 Host는 그리드가 작으면, 더 나은 성능을 내고, 그리드가 크면, 덜 빈번하게 Awake 상태가 된다. 이것은 다수의 Host가 더 많은 충돌과 Drop Rate를 발생시키는 Intersection Beacon Interval 동안, 패킷을 전송하기 위하여 경쟁한다는 것을 의미한다.

3. Effect of Number of Hosts

제안하는 MAC Protocol의 Number of Hosts에 따른 성능을 분석한다.

Host의 수는 50으로 고정한다. 다수의 Host는 트래픽 부하를 발생시킨다. 아래 그림[Alive Hosts]처럼, Host의 수가 30이면, 802.11과 802.11 PSM으로 구동하는 Host는 각각 550s와 700s 후, 에너지를 모두 소모한다. 700s에서 AQEC+와 DPSM으로 구동하는 각 Host는 40%, 20%만큼 Alive이다. Host의 수가 150이면, AQEC+와 DPSM으로 구동하는 Host는 802.11과 802.11 PSM으로 구동하는 Host보다 Lifetime이 더 크다. 700s에서 AQEC+와 DPSM으로 구동하는 각 Host는 28%, 16%만큼 Alive이다.

다른 수의 Host로부터 발생하는 지연은 아래 그림[Latency]과 같다. Host의 수가 많아지면, 지연은 더 길어진다. 유사한 성능은 다른 프로토콜에서도 보인다. 최상의 성능은 802.11 PSM, 다음은 DPSM 마지막은 제안하는 프로토콜이다. DPSM과 AQEC+ 사이의 차이는 19ms와 45ms이다.

Packet Drop Ratio는 아래 그림[Packet Drop Ratio]과 같다. 충돌 확률은 Host의 수에 비례하여서 증가한다. 그러므로 Host의 수가 많으면, Packet Drop Ratio는 증가한다. Host의 수가 120이거나 이하이면, 모든 프로토콜의 Packet Drop Ratio는 낮아진다.(0.005 이하) 즉, 시스템의 부하가 적으면, 모든 프로토콜의 신뢰도는 높아진다. DPSM의 Packet Drop Ratio는 가장 크다. 시스템의 부하가 크고, Host의 수가 150까지 많아지면, 모든 Power Saving Protocol의 Packet Drop Ratio는 증가한다. 그리드가 커지면, 다수의 Host를 가진 네트워크는 적은 수의 Host를 가진 네트워크보다 에너지를 더 소모한다. 그리고 Host는 덜 빈번하게 Awake 상태가 된다. 이것은 다수의 Host가 Intersection Beacon Interval 동안, 패킷을 전송하기 위하여 경쟁한다는 것을 의미하며, 더 많은 충돌과 에너지를 소모한다.

CONCLUSIONS

무선 센서 네트워크에서 에너지 보존은 중요하다. 에너지를 보존하기 위한 새로운 MAC Protocol(QEC와 AQEC)을 제안한다. IEEE 802.11 PSM으로 설계된 제안하는 프로토콜은 Host가 더 오랫동안 Sleep 모드를 유지하도록 하여서 에너지를 보존한다.

교차점을 명시하는 Quorum을 이용한 이 프로토콜은 에너지 소모량을 절감하고, Host 사이의 통신을 보장한다.

Grid-based Quorum을 이용하여서 프로토콜을 구현한다.

그리드가 크면, 많은 에너지를 보존하지만, 지연은 증가한다. 그러나 AQEC는 Host의 트래픽에 따라서, 동적으로 그리드의 크기를 정하면서 최상의 성능을 내도록 한다. 또한, Sleep 모드가 길어지기 때문에 발생하는 지연을 줄이는 방안으로 QEC+/AQEC+를 제안한다.

시뮬레이션 결과는 Quorum-based Protocol이 Network Lifetime을 연장하고, Packet Drop Ratio를 최소화한다는 것을 보여준다. 이것은 높은 신뢰도와 Power Efficiency를 구현할 수 있음을 의미한다. 그리고 네트워크 부하가 적으면, 제안하는 프로토콜이 가장 적합하다는 것을 증명한다.

제안하는 프로토콜은 간단하고, Power Efficient며, 신뢰도가 높다.

향후, 제안하는 프로토콜을 End-to-end Delay Tolerable을 유지하는 Multi-hop MANET에 적용할 수 있도록 할 것이다. Multi-hop MANET에서 Host가 Off 될 때, Rerouting과 같은 라우팅 이슈, 그리고 Multi-hop Time Synchronization을 고려해야 한다. 게다가, 그러한 환경에서 경로 결정은 Quorum 크기를 정하는 기준에 영향을 미친다.

제안하는 프로토콜을 구동하기 위하여 각 Host가 적절한 Quorum의 크기를 선택하도록 교차 계층, 시간 동기화, 분산 메커니즘이 필요하다.

Edit by

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

참고 문헌

An Adaptive Quorum-Based Energy Conserving Protocol for IEEE 802.11 Ad Hoc Networks, 2006

그림 출처

An Adaptive Quorum-Based Energy Conserving Protocol for IEEE 802.11 Ad Hoc Networks, 2006