[Quorum] Quorum MAC::Paper 1–2

맹주현 (Juhyun Maeng)

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

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

Protocol Description

Quorum의 개념과 제안하는 Quorum 기반의 MAC(QMAC) 프로토콜을 설명한다.

1. Quorum Concept

Quorum 시스템을 구성하기 위해서는 항상 특정 두 Quorum 집합 사이에 교차점이 필요하다. Quorum은 Majority-based Quorum[21], Tree-based Quorum[1], Grid-based Quorum[6,16], 그 외[11,13,23]와 같이 다양하다.

Quorum 집합은 Time Slot을 나타내며, 이 Time Slot에서 노드는 Wake-up 한다. 노드는 Non-quorum Time Slot에서 에너지 소모량을 절감하기 위하여 Sleep 모드로 전환할 수 있다. Quorum을 사용하는 두 노드는 집합의 원소에 해당하는 시점에서 Wake-up 하고, 같은 Time Slot에서 통신한다.

Grid-based Quorum을 사용해 제안하는 QMAC 프로토콜을 설명한다. 아래 그림처럼 각 노드는 N X N 그리드 내 Quorum 집합으로 한 행과 한 열을 선택한다.

그리드 기반 Quorum 예시

노드 A는 Quorum 집합으로 행 R(a)와 열 C(a)를 선택하고, 노드 B는 Quorum 집합으로 행 R(b)와 열 C(b)를 선택한다. 노드 A와 B 사이에는 두 개의 교차점이 생기며, 하나의 교차점은 R(a)와 C(b) 사이에서, 다른 교차점은 R(b)와 C(a) 사이에서 생긴다. 앞서 말한 것처럼, 노드는 Quorum 집합의 원소에 해당하는 시점에서 Wake-up 하므로 교차점에 해당하는 시점을 통하여 두 노드의 통신은 보장된다.

아래 그림은 Left-to-right 그리고 Top-to-bottom 방식으로 3 X 3 그리드 내에서 9개의 연속적인 Time Slot에 대한 Quorum 집합을 나타낸다.

3 X 3 그리드 예시

아래 그림은 각 노드가 선택한 Quorum 집합에 따라서 정해진 Time Slot의 예시이다.

두 Host 사이의 교차점을 통한 통신 예시

Host A는 Quorum 집합으로 3번째 행과 3번째 열을 선택하고, Host B는 1번째 행과 1번째 열을 선택한다. 그래서 Host A는 Time Slot 2, 5, 6, 7, 8에서 Wake-up 하고, Host B는 Time Slot 0, 1, 2, 3, 6에서 Wake-up 한다. 결국, 두 노드 A와 B의 교차점은 Time Slot 2와 6이고, 이 시점에서 통신할 수 있다.

2. Quorum-Based Wake-up Schedule

QMAC의 주된 목표는 에너지 소모량을 절감하는 것이다. 그리고 트래픽에 따라서 각 노드의 Sleep 모드에 대한 전환 빈도를 결정한다.

각 노드는 무작위, 독립적으로 한 행과 한 열을 선택하여서 Quorum 집합을 구성한다. 그리고 에너지 소모량을 절감하기 위하여 Wake-up 하는 Time Slot의 수를 줄였다.

Quorum 집합을 사용하는 이유는 노드가 Wake-up 하는 Time Slot을 나타내기 위함이다.

Wake-up 하는 Time Slot에서 노드가 항상 Awake 상태를 유지하는 것은 아니므로 통신에 관여하지 않으면, Sleep 모드로 전환할 수 있다. 게다가, T(d) 동안 채널이 Idle 하다면, 노드는 Sleep 모드로 전환할 것이다. 이 논문에서 T(d)의 값은 Time Slot에 대하여 1/5로 정해지고, N X N 그리드를 사용하는 노드는 N²중에서 2N-1 만큼 Wake-up 한다.

싱크 노드와 가까운 내부 원형의 노드들은 많은 트래픽을 처리하기 때문에 작은 그리드를 사용하며, 반면에, 싱크 노드에서 먼 외부 원형의 노드는 큰 그리드를 사용한다.

QMAC으로 구동하는 각 노드는 트래픽에 따라서 그리드의 크기를 정하는 방식으로 Fixed-listen/sleep Frequency Problem을 해결한다.

두 노드가 다른 크기의 그리드를 사용하여도 통신을 할 수 있기 때문에[5] QMAC으로 WSN을 구성하는 것에 문제는 없다. 그리고 Pending 된 트래픽이 있는 노드는 Quorum Time Slot의 시작 여부와 상관없이 트래픽 전송을 완료할 때까지 Sleep 모드로 전환할 수 없다.

각 노드의 그리드 크기를 정하는 방법은 다음과 같다. 그리고 Many-to-one과 Constantly Reporting Model을 사용한다고 가정하기 때문에 각 노드의 그리드 크기를 미리 정할 수 있다. 노드가 자체적으로 발생시키는 트래픽을 제외하고, 내부 원형의 노드는 외부 원형에 있는 노드들로부터의 트래픽을 싱크 노드로 전달해야 하므로 싱크 노드에 가까운 노드일수록 많은 트래픽을 처리해야 한다. 각 노드가 갖는 트래픽을 정확히 계산하려면, 내부의 특정 한 노드가 싱크 노드로 향하는 패킷의 전달을 담당해야 하는 외부 노드의 평균수를 알아야 한다. 앞선 “[Quorum] Quorum MAC::Paper 1–1”의 [네트워크 구성 예시]처럼 4개의 광원으로 구성된 네트워크를 사용하는 QMAC으로 설명을 한다. 평균 Hop 거리는 R이라고 가정하며, 다른 원형 C(1) : C(2) : C(3) : C(4)에 대한 영역의 비율은 1 : 3 : 5 : 7이다.

각 원형에 대한 영역의 면적 계산 예시

이 계산 결과를 이용하여서 평균적으로, C(3)의 노드는 C(4)의 노드에 대하여 7/5의 트래픽을, C(2)의 노드는 C(3)의 노드에 대하여 5/3의 트래픽을, C(1)의 노드는 C(2)의 노드에 대하여 3/1의 트래픽을 전달해야 한다는 것을 확인할 수 있다.

이 계산 결과로 각 원형의 노드가 처리해야 하는 트래픽 부하를 확인할 수 있다. 우선, 각 노드는 한 단위의 트래픽을 생성한다고 가정한다. C(4)의 노드는 자체적으로 발생시킨 트래픽만을 전송하면 되기 때문에 트래픽 부하는 1이다. 각 원형의 노드가 처리해야 하는 트래픽 부하는 다음과 같다.

각 원형의 노드가 처리해야 하는 트래픽 부하 계산 예시

노드의 트래픽 부하에 따라서 그리드 크기를 정하는 것은 적합하다. 만약 C(1)의 노드가 2 X 2 그리드를 사용한다면, Wake-up Time Slot의 비율은 0.75일 것이다. 그래서 각 원형의 트래픽 부하 비율인 C(1) : C(2) : C(3) : C(4) = 16 : 5 : 2.4 : 1에 따라서, 각 원형 C(2), C(3), C(4)의 노드가 갖는 Wake-up Time Slot의 비율은 각각 0.234, 0.112, 0.047이다. 그리고 각 원형 C(2), C(3), C(4)의 노드가 사용하는 그리드 크기는 각각 8 X 8, 17 X 17, 42 X 42이다.

일반적으로 같은 트래픽을 발생시키는 노드가 분포된 네트워크에서 C(i)의 노드가 갖는 트래픽 부하는 T(C(i))로 나타내고, 아래 식으로 계산한다.

C(i)의 각 노드가 갖는 트래픽 부하를 계산하는 수식

|C(i)|는 i번째 원형을 나타내며, 아래 표처럼 다른 수의 원형으로 구성된 네트워크 트래픽 부하에 대한 비율을 나타낼 수 있다.

원형 수에 따른 트래픽 부하의 비율 예시

1번째 원형 즉, C(1)의 노드가 사용할 그리드 크기는 전달해야 하는 트래픽에 대한 비율로 정한다. Time Slot은 0.1sec 라고 가정하고, C(1) 노드의 그리드 크기가 2 X 2라면, 이 원형의 노드는 최대 7.5 units of traffic/s 을 처리할 수 있을 것이다. 그래서 C(4)의 노드는 7.5/16 = 0.47 units of traffic/s 을 처리하게 된다.

각 원형의 노드가 단위 시간당 처리하는 트래픽과 한 트래픽에 대한 처리 시간 계산 예시

Tolerable Traffic Arrival Time과 그리드 크기(N은 10 이하) 사이의 관계는 아래 표와 같다. (MAC 계층의 충돌 이슈는 고려하지 않음) 아래 표로 노드가 매 2.13s보다 더 빠르게 싱크 노드로 전송한다면, C(1)의 노드가 사용해야 하는 그리드 크기는 1 X 1이라는 것을 예상할 수 있다.

C(1)의 노드에 대한 Traffic InterArrival Time과 Grid Size 사이의 관계 예시

각 노드는 전체 원형의 수를 알아야만 그리드 크기를 계산할 수 있다. 원형의 수를 아는 방법은 각 노드가 싱크 노드로 Hop 정보를 전송하고, 이 정보를 수집하여서 전체 원형의 수를 알게 된 싱크 노드는 원형 수를 주변 노드로 브로드캐스팅 하는 것이다. 그러면 모든 노드가 전체 원형의 수를 알 수 있을 것이다. 그러나 이 방법은 추가적인 Hop 정보를 전송해야 하므로 트래픽 부하가 증가한다는 단점이 있다. 그리고 다른 방법은 싱크 노드가 전체 원형의 수를 예상하고, 그 정보를 NET_INIT 패킷으로 모든 노드로 브로드캐스팅 하는 것이다. 이 방법은 제어 패킷의 수를 줄일 수는 있겠지만, 예상 값의 정확도가 떨어질 수 있다. 그러나 네트워크 크기를 미리 알고 있고, 각 노드의 전송 범위가 고정적이라면, 예상 값의 정확도를 높일 수 있을 것이다.

3. Latency Reduction

QMAC은 노드가 한 Time Slot보다 더 긴 Sleep 모드를 유지할 수 있도록 하므로 에너지 소모량을 절감할 수 있다. 그러나 Sleep 모드 지속시간이 길어지면 전송 지연은 증가할 것이다.

C(i)의 노드 A가 싱크 노드로 전송하는 패킷을 C(i-1)의 노드 B가 전달한다고 가정한다. 노드 B의 Quorum은 노드 A의 Quorum과 교차점이 없을 수도 있으므로 전송 지연이 증가할 수가 있다. 그래서 노드 A는 노드 B로 패킷을 전송하기 전에 몇몇 Time Slot에서 미리 전송해야 할 수 있다. QMAC으로 구동하는 노드에서 발생할 수 있는 전송 지연을 줄이는 방안으로 Next-hop group을 제안한다.

아래 그림처럼 각 노드, 즉 C(i)의 노드 X는 패킷을 전달할 수 있는 후보 노드를 C(i-1) 내(노드 X의 전송 범위 내)에 있는 노드 중 선택한다.

Next-hop group 구성 예시

노드 X는 이 그룹의 구성 노드로써 Next-hop group을 구성한다. 각 노드는 Next-hop group을 네트워크 초기 설정 단계에서 구성하고, 그 단계에서 노드는 제어 패킷(MEMBER_NOTIFY)으로 Next-hop group의 노드에 구성 노드가 되었음을 알린다.

Next-hop group의 주된 목표는 패킷을 전달할 수 있는 노드를 많이 확보하는 것이다. 그래서 이 개념으로 외부 원형의 노드는 싱크 노드로 패킷을 전송할 때, 다수의 Next Hop 노드 중 가장 빠른 전달을 할 수 있는 노드를 선택할 수가 있다. Next-hop group 내 한 노드만이 패킷을 전달할 수 있다.

노드가 Next-hop group이 제대로 구동하지 않는다는 것을 인지하면, 제어 패킷(MEMBER_NOTIFY)을 노드들에 재전송하여서 Next-hop group을 다시 구성한다.

Original QMAC과 제안하는 기법을 적용한 QMAC을 구별하기 위하여, QMAC_LR이라고 이름 지었다. QMAC_LR로 구동하는 노드는 Four-way “Request-to-send(RTS/CTS/DATA/ACK)”에 따라서 패킷을 전송한다. 위 그림[Next-hop group 구성 예시]의 노드 X가 패킷을 전송할 때, Relay 노드를 선택하는 절차는 다음과 같다.

• 노드 X는 RTS 패킷을 Next-hop group의 노드에 멀티캐스팅한다.
• RTS를 수신한 모든 Awake 상태인 노드 X의 구성 노드는 CTS 패킷으로 응답하기 전에 대기(Back-off)한다. 이때, 각 노드의 잔여 에너지양에 따라서 Back-off Time을 정한다. 즉, 잔여 에너지가 절반 이상인 노드는 Contention Window의 전반부(First Half)에 Back-off를 시작하고, 잔여 에너지가 절반 이하인 노드는 Contention Window의 후반부(Second Half)에 Back-off를 시작한다.
• 노드 X가 Next-hop group 노드 중 하나(노드 Y)로부터 CTS를 수신하면, 노드 X는 노드 Y로 패킷을 전송한다. 그리고 이 전송 상황을 Next-hop group의 다른 Awake 상태인 노드들에 알린다.
• 이 전송 상황을 인지한 노드들은 대기 상태를 중단하고, Sleep 모드로 전환한다.
• 노드 X로부터의 패킷을 수신한 노드 Y는 ACK 패킷으로 응답한다.

전송 지연을 줄이기 위한 절차는 다음과 같다.

아래 그림처럼 노드는 Four-way에 따라서 패킷을 전송한다. 노드 A의 Next-hop group이 된 노드 B, C, D는 RTS 패킷을 수신한다. 그리고 노드 A의 Next-hop group이 아닌 노드 E는 RTS를 무시하고, Sleep 모드로 전환한다. 목적지인 노드 C는 노드 A로 CTS 패킷을 전송한다. 이후 노드 C는 노드 A로부터의 패킷을 수신하고, 다른 노드 B, C, D는 Sleep 모드로 전환한다. 노드 C는 패킷 수신 후, ACK 패킷으로 노드 A에 응답한다.

[전송 지연을 줄이는 방안 예시]

Next-hop group의 크기를 적절하게 설정하면 전송 지연을 줄일 수 있다. 그리고 크기를 작게 하면 에너지 소모량을 절감할 수 있지만, 전송 지연은 증가할 것이다. 반대로 크기를 크게 하면, 필요 이상의 후보 Relay 노드가 생기면서 에너지를 낭비할 수 있다. 그래서 Next-hop group의 적절한 크기를 설정하기 위하여 전송하려는 노드가 후보 Relay 노드 중 Awake 상태인 적어도 한 노드와 통신할 확률을 계산할 필요가 있다.

• Theorem

C(i+1)의 노드 A가 Wake-up 할 때, C(i)의 Awake 상태인 노드 중 Next Hop 노드로 최소 하나가 검색될 확률은 다음과 같다.

C(i)의 노드가 사용하는 그리드 크기는 n(g) X n(g)이며, n(h)는 노드 A의 Next-hop group 크기를 나타낸다.

• Proof

각 Time Slot에서 Next-hop group의 노드가 Sleep 모드일 확률은 다음과 같다.

각 Time Slot에서 Next-hop group의 모든 n(h) 노드가 Sleep 모드일 확률은 다음과 같다.

각 Time Slot에서 Next-hop group의 한 노드가 Awake 상태일 확률은 다음과 같다.

위 정리에 따라서 P(1) = P(2) = P(3)이 0.9 이상이 되려면, 다른 원형 수에 대한 Quorum의 크기는 각각 2, 9, 19이어야 한다. 이때, n(h)는 위 식을 사용하여서 다음과 같이 구할 수 있다.

그리드 크기별 n(h)의 계산 예시

마지막으로, Contention Window 크기는 Next-hop group 크기에 따라서 정해져야 한다. Contention Window 크기가 m이고, 경쟁 노드 수가 n인 상황에서 전송의 성공을 위한 수치는 [10]에서 확인할 수 있다. 전송에 성공하기 위하여 1보다 큰 수로 설정할 때, 2, 9, 19에 대하여 필요한 Contention Window의 크기는 각각 4, 8, 8이다.

Simulation Results

제안하는 MAC의 성능평가는 NS2로 하였다. DMAC은 전송 지연을 가장 많이 줄이고, PMAC은 Adaptive Energy Saving 프로토콜이기 때문에 DMAC과 PMAC을 가지고 제안하는 MAC과 성능 비교를 하였다. 참고로 PMAC은 라우팅 메커니즘을 갖지 않는다.

Next-hop group은 전송하는 노드에 대하여 하나의 구성 노드를 갖도록 한다. 400개의 노드를 무작위로 반지름 250m의 원형 내 배치하고, 각 노드의 최대 전송 범위는 75m로 구현한다. 이 범위를 사용하여서 4개의 원형으로 이루어진 네트워크를 구성한다. C(1), C(2), C(3), C(4)에서 제곱미터(m²) 마다 배치한 평균 노드의 수는 각각 0.0021, 0.0021, 0.0020, 0.0021이고, 각 노드의 채널 용량(Channel Capacity)은 10kb/s이다.

각 노드는 매 2.5s마다 128B의 패킷을 생성한다. 그래서 싱크 노드와 가장 가까운 1번 원형 내 노드가 사용하는 그리드의 크기는 2 X 2이다. 그리고 Time Slot은 100ms로 설정한다. [15]에서 설명한 Energy Consumption Model을 사용하며, [15]에서는 transmit, receive, idle, sleep mode에 대한 에너지 소모 정도는 각각 0.66, 0.395, 0.35, 0W이다. 각 노드는 초기 50J의 에너지를 가진다. 각 실험은 평균 50번을 수행하고, 700s(7,000 Time Slot) 동안 진행한다.

첫째로, QMAC_LR에 대한 Next-hop group의 크기를 결정해야 한다. 적절한 그룹의 크기를 정하기 위하여, 노드의 그리드 크기와 인접한 노드에 대한 그룹 크기가 전송률에 미치는 영향을 분석한다. 전송률은 모든 노드가 전송하는 전체 패킷에 대한 싱크 노드가 수신한 총 패킷 수의 비율이다. C(1)의 그리드 크기에 따라서 C(2)의 전송률에 대한 실험 결과는 아래 표와 같다. 괄호 안의 값은 소수점 두 자리 이하를 버린 P(1)이며, P(2) = P(3) = P(1)으로 설정한다.

C(1)의 그리드 크기별 C(2)의 그룹 크기에 따른 전송률의 비율 예시

위 표에 따라서 C(1)에 대한 C(2), C(3), C(4) 그룹 크기의 비율은 아래 표와 같다.

C(1)의 그리드 크기에 따른 원형별 그룹 크기의 비율 예시

위 표[C(1)의 그리드 크기별 C(2)의 그룹 크기에 따른 전송률의 비율 예시]처럼, C(1)의 그리드 크기별 C(2)의 그룹 크기가 커짐에 따라서 전송률은 증가한다. 원형 C(1)의 노드가 갖는 그리드 크기에 대한 그룹 크기를 증가시킬 때 임계 값이 존재한다. P(1)의 값을 0.9 이상으로 하기 때문에 C(1)의 각 그리드 크기 2 X 2, 3 X 3, 4 X 4, 5 X 5에 대한 임계 값은 각각 2, 3, 5, 6이다. 그룹의 크기는 에너지 소모 정도와 관련이 있으므로 임계 값을 사용하면 더욱 효율적인 에너지 사용을 사용할 수 있다.

다음 실험에서 P(1) = P(2) = P(3)을 0.9 이상이 되도록 설정하고, 6가지 측면에서 분석한다.

1. Impact on Live Nodes

Network Lifetime을 얼마나 연장할 수 있는지에 대하여 여러 MAC 프로토콜의 성능을 비교 분석하였다. MAC 프로토콜에 대한 Network Lifetime의 실험 결과는 아래 그림과 같다. QMAC과 QMAC_LR은 Network Lifetime을 상당히 많이 연장시킨다는 것을 확인할 수 있다. PMAC으로 구동하는 내부 원형의 노드는 다른 노드와의 주기 정보 교환에 실패하면 불필요한 Idle Listening과 전송을 하므로 에너지 낭비를 할 수 있다.

시간대별 Alive Nodes

100s부터 DMAC과 PMAC으로 구동하는 노드가 에너지를 소모하기 시작한다. 그리고 160s부터 QMAC과 QMAC_LR로 구동하는 노드가 에너지를 소모하기 시작한다. QMAC과 QMAC_LR은 거의 유사한 Power Saving 성능을 보여준다.

시간대별 다른 원형에 있는 노드의 성능을 여러 프로토콜과 비교 분석한 결과는 아래 그림과 같다.

시간 및 위치별 Alive Nodes

100s에서 DMAC과 PMAC은 C(1)의 몇몇 노드가 에너지를 소모한다. 이와 유사한 경향(내부 원형 C(1)의 노드가 에너지를 더 빠르게 소모해 버림)은 200s와 300s에서도 확인할 수 있다. 그리고 200s에서 C(1)의 DMAC과 PMAC 노드는 35%, 43%만이 Alive 상태이기 때문에 무선 센서 네트워크는 제대로 구동하지 않을 수 있다. 또한, 시간 300s에서 C(1)에 있는 DMAC의 모든 노드는 에너지를 전부 소모하였기 때문에 무선 센서 네트워크는 더 구동하지 않을 것이다. PMAC의 노드는 8%만이 Alive 상태이다. 그리고 시간 200s와 300s에서 C(2), C(3), C(4)의 QMAC과 QMAC_LR 노드가 DMAC과 PACM 노드보다 더 많은 노드가 Alive 상태라는 것을 확인할 수 있다.

2. Impact on the Transmission Latency

전송 지연에 대하여 여러 MAC 프로토콜의 성능을 비교 분석하였다. MAC 프로토콜에 대한 전송 지연의 실험 결과는 아래 그림과 같다. 각 0~100s, 100~200s, 200~300s에서 평균 전송 지연과 전체 평균 전송 지연을 분석하였다. DMAC은 전송 지연이 가장 작다는 것을 확인할 수 있다. 이것은 DMAC이 갖는 Active 시간이 가장 길기 때문이다.

시간대별 Latency

PMAC은 매 Time Slot의 초반 시점에서 Awake 상태를 유지하기 때문에 0~100s에서 QMAC_LR보다 약간 더 작은 전송 지연을 가진다. 그리고 다른 시간대에서 DMAC과 QMAC_LR의 성능 차이는 그리 크지 않다.

QMAC_LR 노드는 Next-hop group으로 Relay 할 수 있는 다수의 Next Hop 노드를 가질 수 있으므로 전송률을 높일 수 있다. 그래서 QMAC 보다 전송 지연이 작은 것이다.

시간이 지날수록, 모든 MAC 프로토콜의 전송 지연은 증가한다. DMAC의 전송 지연이 증가하는 이유는 노드의 전송 실패로 Data-gathering Tree 복원이 발생하기 때문이고, PMAC, QMAC, QMAC_LR의 전송 지연이 증가하는 이유는 Pending 된 패킷을 갖은 노드 사이에서 전송 경쟁이 발생하기 때문이다.

3. Impact on the Transmission Success Ratio

전송률에 대하여 여러 MAC 프로토콜의 성능을 비교 분석하였다. MAC 프로토콜에 대한 전송률의 실험 결과는 아래 그림과 같다.

시간대별 Successful Delivery Ratio

각 0~100s, 100~200s, 200~300s에서 평균 전송률과 전체 평균 전송률을 분석하였다. 0~100s에서 DMAC은 전송률이 가장 높다는 것을 확인할 수 있다. 이것은 DMAC이 갖는 Active 시간이 가장 길어서 싱크 노드가 더 많은 패킷을 수신할 수 있기 때문이다. 더 많은 노드가 에너지 소모를 줄이면서 전송 지연이 증가하기 때문에 100~200s에서 모든 MAC 프로토콜의 전송률은 낮아진다. C(1)의 노드가 에너지를 모두 소모하여서 200~300s에서 DMAC의 전송률이 급격하게 낮아지기 때문에 싱크 노드는 패킷을 잘 수신할 수 없다. DMAC, PMAC, QMAC, QMAC_LR에 대한 평균 전송률은 각각 80%, 82%, 77%, 87%이다.

4. Impact on the Failure Rate

전송에 방해를 받는 환경에 노드가 배치될 수 있기 때문에 전송 실패가 발생할 수 있다. 그래서 전송 실패율에 대하여 여러 MAC 프로토콜의 성능을 비교 분석하였다. 처음으로 Signaling Overhead에 대한 MAC 프로토콜의 성능 평가를 하였다. Signaling Overhead는 관리를 위하여 전달하는 패킷의 크기를 나타내고, DMAC에 대해서는 Data-gathering Tree Construction/Reconstruction, PMAC에 대해서는 패킷 교환, QMAC과 QMAC_LR에 대해서는 RTS/CTS가 관련이 있다.

MAC 프로토콜에 대한 전송 실패율(0%)의 실험 결과는 아래 그림과 같다. QMAC_LR은 CTS를 경쟁 방식으로 전송하기 때문에 QMAC_LR의 Signaling Overhead 크기와 QMAC의 Signaling Overhead 크기는 비슷하다. 그리고 PMAC의 노드는 다른 노드와 주기 정보를 교환하기 때문에 Signaling Overhead는 가장 크다. DMAC의 Signaling Overhead는 가장 작다.

MAC 프로토콜에 대한 전송 실패율(1.5% chance/min)의 실험 결과는 아래 그림과 같다. DMAC의 노드가 갖는 전송 실패율은 1.5% chance/min이다. 시간이 지나면서 모든 프로토콜의 노드가 갖는 Signaling Overhead는 점점 커진다. 그리고 DMAC의 증가율이 가장 낮다.

시간대별 Signaling Overhead

전송 지연에 대하여 여러 MAC 프로토콜의 성능을 비교 분석하였다. MAC 프로토콜에 대한 전송 지연의 실험 결과는 아래 그림과 같다.

시간대별 Latency

앞선 [시간대별 Latency]와 비교하면, DMAC의 전송 지연은 예상치 못한 노드의 전송 실패로 발생한다는 것을 확인할 수 있다. 100~200s와 200~300s에서 DMAC의 노드는 QMAC_LR의 노드에 비해서 평균 전송 지연이 크다. 이것은 QMAC_LR 노드에 전송 실패가 발생하더라도 Next-hop group으로 전송 지연을 줄일 수 있기 때문이다. 그리고 그룹의 노드가 Relay에 실패하면, Next Hop 구성 노드를 재선택한다. PMAC과 QMAC은 시간이 지나면서 전송 지연이 증가한다.

실험으로 제안하는 MAC 프로토콜의 우수성을 증명하였다. 다음으로 QMAC과 QMAC_LR에 대한 트래픽 부하와 원형 수 사이의 관계성을 분석한다.

5. Effect on the Traffic Load

노드들이 Packet-interarrival Time을 교환하도록 하여서 트래픽 부하가 미치는 영향에 대하여 MAC 프로토콜의 성능을 비교 분석하였다. 그래서 각 그리드 크기 1 X 1, 2 X 2, 3 X 3에 대한(위 표 [C(1)의 노드에 대한 Traffic InterArrival Time과 Grid Size 사이의 관계 예시]로 부터 얻음) Interarrival Time은 각각 2, 2.5, 3s이다.

아래 그림처럼 트래픽 부하가 가장 크면(2sec) 충돌 발생 확률이 높아지기 때문에 전송률이 가장 낮아진다는 것을 확인할 수 있다. 그리고 모든 시간에서 QMAC_LR은 QMAC보다 전송률이 더 높으며, 평균 전송률은 대략 QMAC_LR은 87% 이상이고, QMAC은 77% 이상이다.

Packet-interarrival Times에 따른 Successful Delivery Ratio

6. Effect on the Number of Coronas

원형 수가 미치는 영향에 대하여 MAC 프로토콜의 성능을 비교 분석하였다. 각 노드의 전송 범위는 변경하지 않고, 원형의 수를 달리하면서 다른 네트워크로 실험하였다. 원형의 수가 3, 4, 5인 각 네트워크가 갖은 노드 수는 225, 400, 625이다. 그리고 Packet Interarrival Time은 2.5s이다.

아래 그림처럼 원형 수가 가장 큰(5) 네트워크는 트래픽 부하가 더 많이 발생하기 때문에 전송률이 가장 낮다는 것을 확인할 수 있다. 그리고 모든 시간에서 QMAC_LR은 QMAC보다 전송률이 더 높으며, 평균 전송률도 높다. 이 결과로 Next-hop group 메커니즘의 효과를 입증한다.

네트워크 크기에 따른 Successful Delivery Ratio

Conclusion And Future Work

무선 센서 네트워크(WSN)에서 에너지 소모량의 절감은 매우 중요하다. 보통, 싱크 노드에 가까운 노드일수록 에너지를 더 빠르게 소모한다. 기존 에너지 소모량의 절감 방법은 싱크 노드 주변에 더 많은 노드를 배치하는 것이다. 이 논문에서는 계획적으로 노드를 배치하는 것이 어려운 환경에 적용할 수 있는 Energy-conserving MAC 프로토콜을 제안한다.

모든 노드는 싱크 노드로부터의 거리 차에 따라서 다른 부하를 처리하기 때문에 Quorum을 사용하여서 각 노드의 Sleep 주기를 최적화한다. Sleep 주기가 길면, 전송 지연이 증가할 것이기 때문에 Next-hop group으로 전송 지연을 줄이는 시도를 한다.

실험 결과로 제안하는 QMAC_LR이 에너지 소모량을 절감하고, 전송 지연을 줄일 수 있다는 것을 입증하였다. 그래서 QMAC_LR은 무작위로 배치한 노드로 구성되는 네트워크의 성능을 향상시킬 수 있는 Energy Saving 프로토콜이라고 말할 수 있다.

균등하게 노드를 배치할 수 없는 환경에서 특정 원형의 노드가 고정된 크기의 그리드를 사용하는 것은 적합하지 않다. 왜냐하면 적절한 그리드 크기의 계산이 쉽지 않기 때문이다. 그래서 Pending 된 패킷, 이웃 노드의 수, 전송 실패율, 전송 지연까지 고려해야만 최적의 그리드 크기를 계산할 수 있다. 그리고 이러한 요소들은 Time-varied Factors이기 때문에 노드가 사용할 그리드 크기는 고정적인 것보단 동적인 것이 더욱 효과적일 것이다.

이후, 환경 변화에 따라서 적절하게 그리드 크기를 조절하는 방안을 모색할 것이다.

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, 2010