Advanced
A Centralized DESYNC Scheme in Small-Scale Wireless Networks
A Centralized DESYNC Scheme in Small-Scale Wireless Networks
Journal of the Korea Institute of Information and Communication Engineering. 2015. Mar, 19(3): 731-740
Copyright © 2015, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : January 16, 2015
  • Accepted : February 12, 2015
  • Published : March 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
남권 이
상현 현
제율 이
규원 이
동민 양
dongmin.yang@gamil.com

Abstract
최근 기기간 통신에 따른 소규모 네트워크에 적합한 통신 방법들에 대한 관심이 급증하면서 수요가 증가하고 있다. 소규모 네트워크의 기본적 시스템은 TDMA(Time Division Multiple Access)방식이 사용될 수 있다. 하지만 TDMA는 동기화 방식이 복잡하고 추가 장비가 필요하며 비용적인 측면에서 비효율 적이다. 때문에 본 논문에서는 DESYNC(DESYNChronization)를 이용하여 소규모 네트워크에 적합한 동기화 방법을 제안한다. 기존 DESYNC는 동기화 완료까지의 시간이 걸리고 지연시간을 보장하지 않는다. 본 논문에서는 DESYNC 알고리즘을 개선하여 BC(Bridge Count)-DESYNC를 제안한다. BC-DESYNC는 통신 범위를 초과한 노드들 사이에 CU(Central Unit)을 배치하여 중앙제어장치 기능을 통해 노드들의 통신이 가능하도록 하며, Mimic DESYNC와 C-DESYNC를 이용하여 동기화 상태 완료 시간을 보장한다.
Keywords
Ⅰ. 서 론
무선랜(Wireless LAN), 블루투스(Bluetooth), 지그비(Zigbee) 등의 무선 통신 방식으로 데이터를 교환하는 근거리 통신망은 효율적인 통신을 위해 한정된 채널을 다수의 단말기들이 공유하기 위한 다중 접속(Multiple Access)기술이 필요하며, FDMA(Frequency Division Multiple Access), TDMA(Time Division Multiple Access), CDMA(Code Division Multiple Access) 등의 기법들이 대표적이다. 본 논문에서는 가용 대역폭을 슬롯으로 나누어 자신에게 할당된 시간 슬롯에서 모든 대역폭을 이용하여 통신하는 TDMA에 초점을 맞추고 있다. 이러한 TDMA에서 모든 노드가 슬롯에 대한 동일한 기준을 갖기 위해서는 동기화 과정이 선행되어야 한다. 본 논문은 동기화 과정을 단순화하기 위해 DESYNC 알고리즘을 이용하는 기법을 제안하고자 한다.
최근에는 기기간 통신, 웨어러블 디바이스, 홈 네트워크에 대한 수요가 증가하면서 소규모 무선 네트워크에 적합한 통신 방법들에 대한 관심이 급증하였다. 또한 소규모 무선 네트워크는 군의 근본적인 전략적 특성과 작전 수행 능력의 최적화를 위해 미래에 군용 시스템에 활용될 가능성이 크다. 이러한 시스템에는 기본적으로 TDMA 방식이 사용될 수 있다. 그러나 TDMA는 지속적으로 동기화를 이루기 위하여 추가 장비가 필요하고 구현하기 복잡하며 비용적인 측면에서 비효율 적이기에 무선 랜, 블루투스, 홈 네트워크, 군용 시스템 같은 소규모 네트워크에서는 적합하지 않다. 무선 랜의 경우 동기화를 위해 LAN card와 같은 추가 장비를 필요로 하며 무선 채널의 특성상 신호품질이 불안정하고 신호 간섭이 발생할 수 있다. 또한 상당히 많은 양의 전력을 사용하는 단점이 있다. 때문에 소규모 네트워크에는 단순한 동기화 방식이 필요하다. 간단한 규칙을 이용하여 주기적이고 공정하게 주변에 이벤트를 발생시켜 동기화를 이루는 DESYNC는 이벤트 신호에 매우 적은 에너지를 사용하기 때문에 비용측면에서 효율적이다 [1 , 2] .
하지만 소규모 네트워크에 DESYNC를 적용한다면 해결해야 할 두 가지 문제가 존재한다. 첫 번째는 DESYNC의 모든 노드는 전송 범위 내에 있어야 하고, 모든 노드는 연결되어 있어야 한다는 점이다. 이는 단일 홉 무선 네트워크에서는 적합하지만 2-홉(Hop) 이상의 무선 네트워크에서는 적합하지 않다. 두 번째는 모든 노드가 균등한 채널을 공유하기 때문에 동기화 상태 완료까지의 지연시간을 보장하지 않고, 동기화 상태 완료까지 걸리는 시간이 길다는 점이다 [1 - 3] .
본 논문에서 제시하는 알고리즘은 두 가지 방법으로 이루어져 있다. 첫 번째는 네트워크에 참여하는 노드 중 하나의 노드를 전송범위가 넓은 NCU (Central Unit)를 배치하는 것이다. 이 방법은 2-홉 이상의 무선 네트워크 환경에서 사용되는 AP(Access Point)와 BS(Base Station)같은 중앙제어장치에서 영감을 받아 이용하였으며, NCU 는 중앙제어기능을 가지고 있다. 두 번째는 모든 노드가 동기화 상태 완료 시점까지의 지연시간을 보장하기 위해서 DESYNC의 간단한 규칙을 가진 이벤트를 이용하여 전체 노드의 개수를 파악하고, 노드 자신의 이벤트 이전과 이후의 이벤트를 이용하여 동기화 상태 완료까지의 지연시간을 보장하는 방법이다. 본 논문은 위 두 가지 방법을 이용하여 2-홉 네트워크로 이루어진 소규모 무선 네트워크 환경에서 동기화 상태 완료까지 걸리는 지연시간을 보장하는 동기화 방법을 제안한다.
Ⅱ. 관련연구
- 2.1. DESYNC 알고리즘
DESYNC는 단일홉 형태의 무선 네트워크에서 간단한 규칙으로 공정한 이벤트를 사용해 동기화를 이루기 위한 알고리즘이다. 기존 TDMA 방식은 동기화를 위한 신호 및 추가 작업이 필요하지만 DESYNC는 이러한 추가 작업이 필요 없다. 또한, 네트워크에 참여하는 노드의 개수에 상관없이 노드 스스로 동기화를 이루고 유지하며, 네트워크를 구성하는 노드가 결함, 추가, 삭제가 되어도 스스로 네트워크 유지가 가능하다.
DESYNC의 각 노드들은 일정한 간격마다 주기적으로 펄스신호를 발생시킨다. 펄스신호는 firing이라 하며, 노드는 firing시 자신의 주기정보를 전송 범위 내에 노드들에게 전송 한다. t 는 전체 시간을 나타내며, 주기는 T 로 정의한다. 모든 노드들은 T 에서 오직 한번씩 firing한다. 네트워크의 노드들이 n 개 존재할 때 각각의 노드들은 Ni (0 ≤ i n -1)라 하고, ՓNi ( t ) = 0으로 초기화한다. 0과 1은 주기 T 에서 동일한 위치를 의미한다. 그림 1 -(a)와 같이 ՓN3 ( t ) = 0.25이면, N 3 T 에서 25% 위치에 해당한다. T 내에서 firing한 노드는 직전과 직후에 firing한 노드와의 시간차를 이용하여, 자신의 다음 firing 위치를 정하게 된다. 모든 Ni (0 ≤ i n -1)에 대해 동기화 상태 완료를 수식 (1)과 같이 정의한다 [1 , 4] .
PPT Slide
Lager Image
DESYNC 알고리즘 수행 과정 Fig. 1 DESYNC procedure
PPT Slide
Lager Image
T 내에 모든 노드들의 간격이 일정해지면 DESYNC 상태가 되며, 수식(2)에 의해 노드들의 간격이 결정된다.
PPT Slide
Lager Image
DESYNC에서 노드들의 초기 firing 시각은 T 내에서 임의로 정해지게 된다. 그림 1 의 큰 원은 T 를 의미하며, 작은 원은 노드를 의미한다. T 내에서의 노드는 자신의 위치를 통해 firing까지의 시간을 알 수 있으며, 1이 되면 firing을 하고 0으로 초기화 된다. 그림 1 -(a)는 노드들의 초기 배치 상태를 나타내며, 네 개의 노드들은 T 내에서 시계방향으로 회전한다. 각 노드들은 1이 되면 firing한다. 그림 1 -(a)의 N 3 T 의 25%의 위치한다. 노드들은 자신의 firing 직전과 직후의 firing한 노드의 정보를 얻을 수 있다. firing한 노드의 직전과 직후에 firing한 노드를 인접 노드로 정의한다. 그림 1 -(c)는 노드가 firing 정보를 이용하여 자신의 다음 firing 시간을 결정한다. 그림 1 -(c)의 N 2 는 인접노드 N 1 N 3 의 firing 시간차를 이용하여 자신의 다음 firing 위치를 정하게 된다. 여러 주기를 반복하여 그림 1 -(d) 처럼 모든 노드들의 간격이 일정해지게 되면 동기화 상태 완료에 이르게 된다 [5 , 6] .
노드들은 firing 직전과 직후의 인접노드 정보를 이용하여 자신의 다음 firing 위치를 정하게된다. 그림 2 와 같이 N 0 , N 1 은 각 firing 정보를 참고하여 자신의 다음 firing 위치를 결정한다. 결정된 firing값을 중간값이라고 하며, 수식 (3)에 의해 중간값이 결정된다.
PPT Slide
Lager Image
DESYNC의 중간값 계산 과정 Fig. 2 DESYNC median calculation algorithm
PPT Slide
Lager Image
- 2.2. Mimic DESYNC 알고리즘
Mimic DESYNC는 기존 DESYNC 알고리즘에서 전송범위를 벗어나 통신이 불가능한 노드들에게 CU를 통하여 통신이 가능하도록 개선된 알고리즘이다. Mimic DESYNC는 n 개의 노드 중 N 0 의 전송 범위를 다른 노드의 전송 범위보다 넓게 설정하여, N 0 는 중앙제어기능을 수행하도록 하고, ( N 0 = NCU )라고 정의한다. 모든 노드들은 비동기 방식으로 노드간 통신 시간을 주기적이고 공정하게 수행한다. 노드는 자신의 firing 시간, firing한 직전과 직후의 인접 노드와의 시간차 정보를 가지고 있다.
Mimic DESYNC의 모든 노드들의 초기 배치과정은 자신의 firing 시간을 T 내에서 임의로 설정하며, 노드 Ni (0 ≤ i n -1)의 firing 시간 범위는 수식 (4)의 조건을 만족한다.
PPT Slide
Lager Image
수식 (3)을 이용하여 중간값을 계산할 때, 각 노드는 주기마다 새로운 중간값을 가지게 된다. 이 과정을 반복하면 모든 노드들은 중간값이 변동이 없는 하나의 값으로 판단한다. 이러한 상태를 DESYNC라 정의하며, DESYNC 상태를 판별하기 위해 전체 주기를 전체 노드 수로 나눈 평균값은 수식(3)과 같다.
그림 3 -(a)의 각 노드 N 1 , N 2 , N 3 은 각 통신범위에서 벗어나기 때문에 통신이 불가능하다. Mimic DESYNC는 각 노드의 전송 범위보다 넓은 NCU 를 배치하여 단일 홉 뿐만이 아닌 2-홉 네트워크에서도 동작하도록 지정한다. NCU 는 중앙제어기능을 통하여 통신범위 내에 모든 노드들이 DESYNC를 지속할 수 있도록 한다. 그림 3 -(b)는 DESYNC에 NCU 를 배치하여 전송 범위에서 벗어난 노드들의 통신이 가능하도록 한다. 노드 N 1 , N 2 , N 3 의 firing 정보는 NCU 를 통해 다른 노드들에게 전송한다.
PPT Slide
Lager Image
Mimic DESYNC의 NCU배치과정 Fig. 3 Mimic NCU of DESYNC allocate
그림 4 는 Mimic DESYNC 알고리즘의 모든 노드의 firing 순서를 나타낸다. 그림 4 N 0 NCU 를 나타내며 노드들의 firing 정보를 다른 노드들에게 전송한다.
PPT Slide
Lager Image
Mimic DESYNC의 firing 순서 Fig. 4 Mimic DESYNC procedure
이 과정을 Mimic firing이라고 정의한다. NCU 를 제외한 모든 노드들은 자신의 firing 정보를 인접 노드에게 전송할 때 NCU 를 통해서만 송수신이 가능하다. 실선으로 표시한 NCU 는 일반 노드와 같이 동작을 수행한다. N 3 이 firing 하게 되면 N 3 의 firing 정보는 NCU 만 수신할 수 있으며, 다른 노드들은 NCU 를 통해서만 N 3 의 정보를 얻을 수 있다. 일반 노드들은 ՓNi ( t ) = 1이 될 때까지 다른 노드들의 firing을 감지하고, NCU 는 다른 노드들의 firing이 감지되면 Δ NCU ( t )= ՓNCU ( t ) - Փ Ni-1 ( t )를 구하고 Mimic firing을 한다. Mimic firing을 통해 각 노드들은 인접 노드의 firing 정보를 알고 수식 (1)을 구한다. 자신의 firing 직후의 firing이 감지되면 다음 인접 노드로 인식하여 Δ Ni+1 ( t )를 구한다. 또한 현재의 Δ Ni ( t )을 직전의 인접노드와 자신의 firing시간차로 인식하고 중간 값을 계산하여 FTNi 를 수정한다 [7] .
- 2.3. C-DESYNC 알고리즘
기존 DESYNC의 동기화 방식은 간단한 규칙과 펄스 신호를 이용하여 동기화를 이루기 때문에 비용측면에서 효율적이다. 하지만 DESYNC는 네트워크가 동기화에 이르는 지연시간을 보장하지 않기 때문에 노드의 초기 firing 시각과, 노드의 개수에 따라 동기화 상태 완료에 이르는 지연시간이 달라진다. C-DESYNC는 기존 DESYNC의 지연 시간 보장을 위한 문재점 개선에 의해 제안되는 알고리즘이다. 기존 DESYNC에서의 각 노드들은 T 에서 인접 노드의 firing 시간차 정보 Δ Ni ( t ), Δ Ni+1 ( t )과 자신의 firing 시각을 가지고 주기마다 수식 (1)에 의해 firing 위치를 정한다. DESYNC는 인접 노드들의 firing 시간차를 이용하는 반면에 C-DESYNC는 네트워크를 구성하는 전체 노드들의 개수를 파악하여 네트워크 안정화를 이룬다.
C-DESYNC의 각 노드들은 자신이 firing한 시각과 진전과 직후의 firing한 노드의 정보인 BFC (Before Firing Count), AFC (After Firing Count)를 가지고 있으며, 동기화를 위하여, GP (Global Packet), GPR (Global Packet Recent)을 가지고 있다. C-DESYNC의 firing 시각 또한 DESYNC와 같이 초기 T 에서 임의로 배치되고, BFC , AFC 를 이용하여 주기마다 전체 노드의 개수를 파악하고, 수식 (5)를 이용하여 firing 위치를 정한다.
PPT Slide
Lager Image
C-DESYNC는 자신이 firing하기 이전의 firing한 노드들의 정보 BFC 를 이용하여 자신이 몇 번째로 firing 하는지 알 수 있다. 또한 이후의 firing 노드들의 정보 AFC를 이용하여 전체 노드 개수를 파악할 수 있다.
C-DESYNC의 노드들이 초기에 배치될 경우, 노드들은 GP 를 수신하기 위하여 초기 배치시 ( t = T ). T 만큼의 시간이 지날 때까지 대기한다( t = T ). T 시간 내에 GP 를 수신하면 네트워크에 LN 이 존재한다고 판단하고 일반 노드와 같이 동작한다. GP 를 수신하지 못한 노드는 네트워크에 LN 이 존재하지 않는다고 판단하고, T 시간 이후, 제일 먼저 firing하는 노드가 LN 의 역할을 수행하게 되어, T 마다 한번씩 GP 신호를 주변 노드들에게 전송한 후, 일반 노드의 동작도 같이 수행한다. GP 신호는 노드의 주기 시작 정보를 가지고 있기 때문에 이 신호를 받은 일반 노드들은 LN (Leader Node)의 시간과 동기화를 이루게 된다.
LN 선출시 초기 배치된 노드가 네트워크에 참여했을 때 노드는 t = T 까지 GP 신호를 수신대기하며, 수신 여부에 따라 자신이 LN 가 되어 동작할 것인지 일반 노드가 동작할 것인지 결정한다. LN Փ ( t ) = 1이 되면 GP 를 주변 노드들에게 전송하고, 일반 노드와 같이 동작하게 된다. GP신호를 받고 LN 의 주기에 맞추 동작하는 일반 노드들은 BFC , AFC 를 이용하여 전체노드 개수를 구한 후, 자신의 다음 FT 를 결정하게 된다.
그림 5 는 C-DESYNC의 동작 수행과정을 보여준다. 큰 원은 T 를 의미하고, 작은 원은 노드를 의미한다. N 0 , N 1 , N 2 , N 3 의 초기 위치는 임의로 T 상에 배치되며, 모든 노드들은 초기 배치시 T 만큼의 시간이 지날 때 까지( t = T ) 아무런 동작 수행을 하지 않으며, GP 신호를 수신하기 위해 대기한다. T 시간 내에 GP 가 감지되면 LN 가 있다고 판단하고, 각 노드들은 네트워크에서 일반 노드의 동작을 수행하게 된다.
PPT Slide
Lager Image
C-DESYNC 동작 수행과정 Fig. 5 C-DESYNC procedure
T 시간 내 GP 신호를 감지하지 못할 경우 네트워크에 LN 이 없는 것으로 판단하여 LN 를 선출하게 된다. 모든 노드들의 시간 흐름은 시계방향으로 회전한다고 가정하고, 12시에 위치하면 firing한다. LN 는 firing을 하기전에 주변 노드들에게 자신의 주기 시작 정보를 가지고 있는 GP 신호를 주변 노드들에게 전송하고 일반 노드와 같이 동작하게 된다. ( 그림 5 )-(a)는 초기 네트워크에 배치된후 T 시간만큼 대기한 모든 노드들이 GP 신호를 받지 못하였지 때문에, 처음 firing하는 노드 N 0 LN 0 가 된다. 그림 5 -(b)는 LN 0 가 보내는 GP 신호에 의해 모든 노드들의 주기 시작 시각이 동기화된 상태이다. LN 0 는 각 노드들이 주기의 시작을 맞추기 위해 GP 를 보내며, 일반 노드의 동작도 수행하게 된다. 그림 5 -(c)는 GP 신호를 기준으로 T 동안 firing한 모든 노드들은 각각 BFC , AFC 로 저장한다. 저장된 정보와 수식 (5)를 이용하여, 노드들은 다음 주기의 FT 를 결정하게 되며, 그림 5 -(d)와 같이 네트워크 동기화 상태 완료가 된다 [8] .
Ⅲ. 본 론
- 3.1. 시스템 모델
본 논문에서 제안하는 BC-DESYNC는 기존의 다중 접속 방법의 동기화 과정을 추가적인 장비가 필요 하지 않고, 간단한 규칙과 펄스 신호를 이용하여 동기를 유지 할 수 있기 때문에 비용적인 측면에 있어서 효율적이다.
표 1 은 DESYNC, Mimic DESYNC, C-DESYNC의 노드 기본정보와 본 논문에서 제안하는 BC-DESYNC의 노드 기본정보를 비교한 표를 나타낸다.
DESYNC와 Mimic DESYNC와 C-DESYNC와 BC-DESYNC의 노드 기본정보Table. 1 Node information of DESYNC and Mimic DESYNC and C-DESYNC and BC-DESYNC
PPT Slide
Lager Image
DESYNC와 Mimic DESYNC와 C-DESYNC와 BC-DESYNC의 노드 기본정보 Table. 1 Node information of DESYNC and Mimic DESYNC and C-DESYNC and BC-DESYNC
다음은 ( 표 1 )에서 사용되는 노드 기본정보에 대한 설명이다.
DESYNC 노드 기본정보
  • FT(Firing Time)
  • : 자신이 firing하는 시간.(0
  • ΔNi(t)
  • : 자신이 firing하기 직전에 firing한 노드와의 firing 시간차.
  • ΔNi+1(t)
  • : 자신이 firing하기 직후에 firing한 노드와의 firing 시간차.
Mimic DESYNC 노드 기본정보
  • FT(Firing Time)
  • : 자신이 firing하는 시간.(0
  • ΔNi(t)
  • : 자신이 firing하기 직전에 firing한 노드와의 firing 시간차.
  • NCU(Central Unit)
  • : 중앙제어기능
  • ΔNi+1(t)
  • : 자신이 firing하기 직후에 firing한 노드와의 firing 시간차.
C-DESYNC 노드 기본정보
  • FT(Firing Time)
  • : 자신이 firing하는 시간.(0
  • BFC(Before Firing Count)
  • :T내에서 자신의FT이전에 firing한 노드의 개수.
  • AFC(After Firing Count)
  • :T내에서 자신의FT이후에 firing한 노드의 개수.
  • GP(Global Packet)
  • : 노드주기의 시작.
  • GPR(Global Packet Recent)
  • :GP를 수신한 시각.
BC- DESYNC 노드 기본정보
  • FT(Firing Time)
  • : 자신이 firing하는 시간.(0
  • BFC(Before Firing Count)
  • :T내에서 자신의FT이전에 firing한 노드의 개수.
  • AFC(After Firing Count)
  • :T내에서 자신의FT이후에 firing한 노드의 개수.
  • GP(Global Packet)
  • : 노드주기의 시작.
기존의 DESYNC는 동기화 상태에 이르기까지 노드의 개수에 따라 동기화 완료시까지 지연시간이 달라지지만, BC- DESYNC는 GP 를 기준으로 네트워크에 참가한 모든 노드의 개수를 파악한다. 모든 노드의 개수를 파악하기 위해서 GP 를 기준으로 개수를 파악하며 자신의 위치를 파악하기 위해서 자신의 FT 를 기준으로 이전에 firing한 노드의 개수 BFC 와 이후에 firing한 노드의 개수 AFC 의 정보를 이용한다. 또한, 중앙제어기능과 전송범위가 넓은 NCU 를 이용해 firing 신호를 듣지 못하는 일반노드에게도 firing 정보를 전송해 모든 노드의 개수를 파악할 수 있다. 그리고 다음 주기에서 수식 (5)를 이용해 동기화를 이룬다.
본 논문에서 제안하는 BC-DESYNC는 기존 다중접속방법의 동기화 과정에서 필요한 추가적인 장비를 사용하지 않고 간단한 방법을 통한 동기화를 이룰 수 있다. 또한 DESYNC의 단점인 동기화 상대 완료가 되기까지의 지연시간을 보장하고 2-홉 무선네트워크 환경에서도 가능하도록 개선하였다. Mimic DESYNC는 노드 중에서 한 개의 노드를 전송범위를 넓게 하여 NCU 를 배치하고 주변 노드의 주기를 맞추기 위해서 GP 를 사용한다 [7] .
제안하는 알고리즘의 Ni NCU 의 전송범위는 Mimic DESYNC의 그림 3 과 같이 나타낸다. (a)는 N 1 , N 2 , N 3 N 0 과 각각 통신이 가능하지만 N 1 , N 2 , N 3 는 서로 통신이 불가능한 상태이다. 하지만 제안하는 알고리즘에서는 (b)와 같이 N 1 , N 2 , N 3 는 중앙제어기능을 가지고 있는 NCU 를 통하여 통신이 가능하도록 하였다.
NCU 의 동작과정은 주변의 노드 Ni 가 firing을 하였을 때 전송범위가 넓은 NCU 가 주변 모든 노드에게 firing을 수행하여 모든 노드가 firing을 감지 할 수 있도록 하는 것이다. 본 논문에서는 NCU 가 firing하는 과정을 Mimic firing이라고 정의하고 모든 노드는 일반 노드 의 firing을 감지하지 못하며 오로지 NCU 의 Mimic firing을 가지고 모든 노드의 개수를 파악하고 수식 (5)를 이용해 다음주기의 firing 시간을 조정해 동기화를 이룬다. 그림 6 , 그림 7 은 BC-DESYNC의 Ni NCU 의 동작 알고리즘을 나타낸다. 먼저 그림 6 Ni 알고리즘은 주기를 맞추기 위해서 GP 를 감지하기 전까지는 동작하지 않고 GP 신호를 감지한 뒤부터 본인의 FT 을 기준으로 Mimic firing을 듣고 이전에 firing한 노드와 이후에 firing한 노드의 개수를 파악하고 ϕNi ( t )=1일 때 firing을 한다. 그 다음 다시 한 번 GP 를 감지할 때 수식 (5)를 이용하여 다음주기의 firing 시간을 조정해 동기화를 이룬다. 그림 7 NCU 의 동작 알고리즘이다. NCU 는 주변 노드의 firing을 감지하여 모든 노드에게 Mimic firing을 하고 본인의 AFC BFC 를 계산한 다음 ϕNCU ( t )=1일 때 자신의 Mimic firing과 GP 를 보낸다. 1 주기의 경우에는 모든 노드는 GP 를 이용해 주기를 맞추고 2주기의 경우에는 수식 (5)를 이용해 동기화를 이룬다.
PPT Slide
Lager Image
BC-DESYNC의 Ni 알고리즘 Fig. 6 Ni algorithm of BC-DESYNC
PPT Slide
Lager Image
BC-DESYNC의 NCU 알고리즘 Fig. 7 NCU algorithm of BC-DESYNC
본 논문에서 제안하는 알고리즘을 이용하여 노드를 구성하였을 경우에 동작과정은 그림 8 과 같다. 그림 8 에서 큰 원은 주기 T 를 나타내며 진행 방향은 시계방향으로 firing을 한다. 작은 원은 NCU N 1 , N 2 를 나타낸다. 그림 8 -(a)는 T 에서 임의로 생성된 그림이고, 일반 노드들은 NCU GP 를 보내기 전까지 firing을 수행하지 않는다.
PPT Slide
Lager Image
BC-DESYNC의 동작 수행과정 Fig. 8 BC-DESYNC procedure
그림 8 -(b)는 NCU GP 를 보내어 노드들의 주기의 시작시간을 동기화 한 그림이다. 그리고 그림 8 -(c)에서 T 동안 firing을 들은 NCU 가 mimic firing을 모든 노드에게 전송하여 이전, 이후 노드의 개수를 파악한 다음 수식 (5)를 이용해 그림 8 -(d)와 같이 동기화를 이룬다 [7 , 8] .
Ⅳ. 실험 및 고찰
본 논문의 BC-DESYNC 알고리즘의 성능 평가를 위해 JAVA환경에서 개발 및 실험하였다. DESYNC와 BC- DESYNC의 동기화 과정을 비교하고, 비교 평가요소는 네트워크의 동기화 상태 완료까지의 최대 지연시간 MTTSC(Maximum Time To Synch Completion)을 측정하였다. 실험 결과는 T =1000일 때, 1,000번씩 반복한 평균을 구하였다.
표 2 는 DESYNC와 C-DESYNC, BC-DESYNC를 적용한 네트워크에 각 노드를 5, 10, 20, 40, 10, 200, 250, 500개를 추가하였을 때, 동기화 상태 완료의 MTTSC를 비교한 표이다. DESYNC와 Mimic DESYNC를 적용한 네트워크는 노드 개수에 따라 MTTSC가 증가한 것을 알 수 있고, C-DESYNC를 적용한 네트워크는 노드의 개수에 관계없이 3주기 이내에 동기화 상태 완료를 이룬다. BC-DESYNC를 적용한 네트워크는 NCU 를 이용하여 2주기 만에 동기화 상태 완료를 알 수 있다.
DESYNC와 C-DESYNC와 개선된 DESYNC의 MTTSCTable. 2 MTTSC of DESYNC and C-DESYNC and BC-DESYNC
PPT Slide
Lager Image
DESYNC와 C-DESYNC와 개선된 DESYNC의 MTTSC Table. 2 MTTSC of DESYNC and C-DESYNC and BC-DESYNC
표 3 은 DESYNC와 C-DESYNC와 BC- DESYNC를 적용한 네트워크에서 각 노드의 개수가 5개일 때, 동기화를 완료 후, 노드 하나가 삭제되었을 때, 동기화 상태 완료가 다시 이루어지기까지의 MTTSC를 비교한 표이다. DESYNC와 Mimic DESYNC를 적용한 네트워크는 노드 하나가 삭제되었을 때, 다시 동기화 상태 완료까지 걸리는 추가 시간이 필요한 반면, C-DESYNC는 3주기 내에 동기화를 이룬다. BC -DESYNC는 NCU 를 통해 통신을 이루기 때문에 2주기 만에 동기화 상태 완료까지의 시간을 단축할 수 있다.
노드 삭제시 MTTSCTable. 3 MTTSC at the removal of a node
PPT Slide
Lager Image
노드 삭제시 MTTSC Table. 3 MTTSC at the removal of a node
표 4 는 DESYNC와 C-DESYNC와 BC- DESYNC를 적용한 네트워크에서 노드가 4개일 때 동기화 상태 완료 후, 노드 하나가 추가되었을 경우, 동기화 상태 완료까지의 MTTSC를 비교한 표이다. DESYNC와 Mimic DESYNC를 적용한 네트워크에서는 하나의 노드가 추가된 후, 다시 동기화 완료 상태가 이루어지기까지 많은 주기가 소모된다. 하지만 C-DESYNC와 BC-DESYNC의 경우에는 모든 노드들이 개수를 파악하여 다음 주기의 firing 시간을 맞추기 때문에 2주기 만에 동기화 상태가 완료된다.
노드 추가시 MTTSCTable. 4 MTTSC at the addition of a node
PPT Slide
Lager Image
노드 추가시 MTTSC Table. 4 MTTSC at the addition of a node
Ⅴ. 결 론
본 논문에서는 DESYNC 알고리즘을 이용한 소규모 네트워크에 적합한 동기화 방식의 BC-DESYNC 알고리즘을 제안한다. 기존 DESYNC는 각 노드들이 동기화를 이루는 지연시간을 보장하지 않는 반면, BC-DESYNC는 다른 노드들보다 전송범위가 넓은 노드 NCU 를 배치하여 중앙제어기능을 수행하도록 한다. 각 노드들의 전송 범위를 벗어나 통신이 불가능한 상태에서 NCU 를 통해서 통신이 가능하다. 즉 모든 노드들은 통신 범위에서 벗어나더라도 노드들과 NCU 가 통신을 할 수 있는 전송 범위 영역이 확장되었다.
Acknowledgements
이 논문은 2012년도 정부(교육과학기술부)의 재원으로 한국연구재단의 기초연구사업 지원을 받아 수행된 것임(NRF-2012R1A1A1042703). 본 논문은 미래창조과학부의 2015년 고용계약형 SW석사과정 지원사업을 지원받아 수행한 결과임(H0116-15-1007)
BIO
이남권(Nam-kwon Lee)
2014년 대전대학교 정보통신공학과(학사)
2014~현재 대전대학교 정보통신공학과 석사과정
※관심분야 : 무선이동통신, 센서네트워크
현상현(Sang-hyun Hyun)
2013년 대전대학교 정보통신공학과(학사)
2013년 ~현재 대전대학교 정보통신공학과 석사과정
※관심분야 : 센서네트워크, 모바일 어플리케이션
이제율(Je-Yul Lee)
2013년 대전대학교 정보통신공학과(공학사)
2013년~2015년 대전대학교 대학원 정보통신공학과 석사 과정
※관심분야 : 무선이동통신, 사물인터넷
이규원(Ku-won Lee)
1988년~1989년 LG산전(주)연구소 연구원
1989년~2000년 한국전자통신연구원 선임연구원
1994년~1998년 연세대학교 신호처리연구센터 연구원
2002년~2003년 한국전자통신연구원 초빙연구원
2003년~2004년 Univ. of Massachusettes 방문연구원
2009년~2011년 대전대학교 신문방송사 주간
2000년~현재 대전대학교 정보통신공학과 교수
※관심분야 : 영상처리, 멀티미디어
양동민(Dong-min Yang)
2000년 POSTECH 컴퓨터공학과(공학사)
2003년 POSTECH 컴퓨터공학과(공학석사)
2011년 POSTECH 컴퓨터공학과(공학박사)
2011년~현재 대전대학교 정보통신공학과 교수
※관심분야 : 무선이동통신, 인지 라디오 네트워크
References
Degesys J. , Rose I. , Patel A. , Nagpal R. “DESYNC: Self-Organizing Desynchron ization and TDMA on Wireless Sensor Networks” Information Processing in Sensor Networks, 2007. IPSN 2007, 6th International Symposium on April, 2007
Jung Ji Young , Kim Un Ha , Kim Young Jae , Jin Mei Hua , Yu Ui Seong , Choi Hyun Ho , Choi Jeung Won , Roh Bong Soo , Seo Nan Sol , Lee Jung Ryun 2015 “Weighted DESYNC for Efficient Distributed Wireless Resource Allocation” Journal of the Korea Institute of Communications and Information Sciecnes 56 (1) 0445 - 0446
Nam Jaehyun 2014 “A Node Activation Protocol using Priority-Adaptive Channel Access Scheduling for Wireless Sensor Networks” Journal of the Korea Institute of Information and Communication Engineering 18 (01) 0469 - 0472
Hwang Soyoung 2014 “Mesh Routing Algorithm for TDMA Based Low-power and Ad-hoc Networks” Z. Ben, D. K. John, and Anthony, “Tapestry: An infrastructure for fault-tolerant wide-area location and routing” Journal of the Korea Institute of Information and Communication Engineering 18 (08) 1955 - 1960    DOI : 10.6109/jkiice.2014.18.8.1955
Degesys Julius , Nagpal Radhika “Towards desynchronization of multi-hop topologies.” Self-Adaptive and Self-Organizing Systems, 2008. SASO'08. Second IEEE International Conference on. IEEE 2008
Mühlberger Clemens , Kolla Reiner (2009) “Extended desynchronization for multi-hop topologies.” Institut für Informatik Universität Würzburg Tech. Rep 460
Lee Jeyul , Hyun Sanghyun , Yang Dongmin 2013 “Asynchronous TDMA Scheme using DESYNC in Wireless Networks” the 40th Korea Information Processing Sotiety Fall Conference Journal 20 (2)
Hyun Sanghyun , Lee Jeyul , Yang Dongmin An Enhanced DESYNC Scheme for Simple TDMA Systems in Single-Hop Wireless Ad-Hoc Networks KIPS Tr. Comp. and Comm. Sys. 3 (9) 293 - 300