무선랜(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].

본 논문에서 제시하는 알고리즘은 두 가지 방법으로 이루어져 있다. 첫 번째는 네트워크에 참여하는 노드 중 하나의 노드를 전송범위가 넓은 N_CU(Central Unit)를 배치하는 것이다. 이 방법은 2-홉 이상의 무선 네트워크 환경에서 사용되는 AP(Access Point)와 BS(Base Station)같은 중앙제어장치에서 영감을 받아 이용하였으며, N_CU는 중앙제어기능을 가지고 있다. 두 번째는 모든 노드가 동기화 상태 완료 시점까지의 지연시간을 보장하기 위해서 DESYNC의 간단한 규칙을 가진 이벤트를 이용하여 전체 노드의 개수를 파악하고, 노드 자신의 이벤트 이전과 이후의 이벤트를 이용하여 동기화 상태 완료까지의 지연시간을 보장하는 방법이다. 본 논문은 위 두 가지 방법을 이용하여 2-홉 네트워크로 이루어진 소규모 무선 네트워크 환경에서 동기화 상태 완료까지 걸리는 지연시간을 보장하는 동기화 방법을 제안한다.

DESYNC는 단일홉 형태의 무선 네트워크에서 간단한 규칙으로 공정한 이벤트를 사용해 동기화를 이루기 위한 알고리즘이다. 기존 TDMA 방식은 동기화를 위한 신호 및 추가 작업이 필요하지만 DESYNC는 이러한 추가 작업이 필요 없다. 또한, 네트워크에 참여하는 노드의 개수에 상관없이 노드 스스로 동기화를 이루고 유지하며, 네트워크를 구성하는 노드가 결함, 추가, 삭제가 되어도 스스로 네트워크 유지가 가능하다.

DESYNC의 각 노드들은 일정한 간격마다 주기적으로 펄스신호를 발생시킨다. 펄스신호는 firing이라 하며, 노드는 firing시 자신의 주기정보를 전송 범위 내에 노드들에게 전송 한다. t는 전체 시간을 나타내며, 주기는 T로 정의한다. 모든 노드들은 T에서 오직 한번씩 firing한다. 네트워크의 노드들이 n개 존재할 때 각각의 노드들은 N_i(0 ≤ i ≤ n-1)라 하고, Փ_Ni(t) = 0으로 초기화한다. 0과 1은 주기 T에서 동일한 위치를 의미한다. 그림 1-(a)와 같이 Փ_N3(t) = 0.25이면, N₃는 T에서 25% 위치에 해당한다. T내에서 firing한 노드는 직전과 직후에 firing한 노드와의 시간차를 이용하여, 자신의 다음 firing 위치를 정하게 된다. 모든 N_i(0 ≤ i ≤ n-1)에 대해 동기화 상태 완료를 수식 (1)과 같이 정의한다[1, 4].

T내에 모든 노드들의 간격이 일정해지면 DESYNC 상태가 되며, 수식(2)에 의해 노드들의 간격이 결정된다.

DESYNC에서 노드들의 초기 firing 시각은 T내에서 임의로 정해지게 된다. 그림 1의 큰 원은 T를 의미하며, 작은 원은 노드를 의미한다. T내에서의 노드는 자신의 위치를 통해 firing까지의 시간을 알 수 있으며, 1이 되면 firing을 하고 0으로 초기화 된다. 그림 1-(a)는 노드들의 초기 배치 상태를 나타내며, 네 개의 노드들은 T내에서 시계방향으로 회전한다. 각 노드들은 1이 되면 firing한다. 그림 1-(a)의 N₃는 T의 25%의 위치한다. 노드들은 자신의 firing 직전과 직후의 firing한 노드의 정보를 얻을 수 있다. firing한 노드의 직전과 직후에 firing한 노드를 인접 노드로 정의한다. 그림 1-(c)는 노드가 firing 정보를 이용하여 자신의 다음 firing 시간을 결정한다. 그림 1-(c)의 N₂는 인접노드 N₁과 N₃의 firing 시간차를 이용하여 자신의 다음 firing 위치를 정하게 된다. 여러 주기를 반복하여 그림 1-(d) 처럼 모든 노드들의 간격이 일정해지게 되면 동기화 상태 완료에 이르게 된다[5, 6].

노드들은 firing 직전과 직후의 인접노드 정보를 이용하여 자신의 다음 firing 위치를 정하게된다. 그림 2와 같이 N₀, N₁은 각 firing 정보를 참고하여 자신의 다음 firing 위치를 결정한다. 결정된 firing값을 중간값이라고 하며, 수식 (3)에 의해 중간값이 결정된다.

Mimic DESYNC는 기존 DESYNC 알고리즘에서 전송범위를 벗어나 통신이 불가능한 노드들에게 CU를 통하여 통신이 가능하도록 개선된 알고리즘이다. Mimic DESYNC는 n개의 노드 중 N₀의 전송 범위를 다른 노드의 전송 범위보다 넓게 설정하여, N₀는 중앙제어기능을 수행하도록 하고, (N₀=N_CU)라고 정의한다. 모든 노드들은 비동기 방식으로 노드간 통신 시간을 주기적이고 공정하게 수행한다. 노드는 자신의 firing 시간, firing한 직전과 직후의 인접 노드와의 시간차 정보를 가지고 있다.

Mimic DESYNC의 모든 노드들의 초기 배치과정은 자신의 firing 시간을 T내에서 임의로 설정하며, 노드 N_i(0 ≤ i ≤ n-1)의 firing 시간 범위는 수식 (4)의 조건을 만족한다.

수식 (3)을 이용하여 중간값을 계산할 때, 각 노드는 주기마다 새로운 중간값을 가지게 된다. 이 과정을 반복하면 모든 노드들은 중간값이 변동이 없는 하나의 값으로 판단한다. 이러한 상태를 DESYNC라 정의하며, DESYNC 상태를 판별하기 위해 전체 주기를 전체 노드 수로 나눈 평균값은 수식(3)과 같다.

그림 3-(a)의 각 노드 N₁,N₂,N₃은 각 통신범위에서 벗어나기 때문에 통신이 불가능하다. Mimic DESYNC는 각 노드의 전송 범위보다 넓은 N_CU를 배치하여 단일 홉 뿐만이 아닌 2-홉 네트워크에서도 동작하도록 지정한다. N_CU는 중앙제어기능을 통하여 통신범위 내에 모든 노드들이 DESYNC를 지속할 수 있도록 한다. 그림 3-(b)는 DESYNC에 N_CU를 배치하여 전송 범위에서 벗어난 노드들의 통신이 가능하도록 한다. 노드 N₁,N₂,N₃의 firing 정보는 N_CU를 통해 다른 노드들에게 전송한다.

그림 4는 Mimic DESYNC 알고리즘의 모든 노드의 firing 순서를 나타낸다. 그림 4의 N₀는 N_CU를 나타내며 노드들의 firing 정보를 다른 노드들에게 전송한다.

이 과정을 Mimic firing이라고 정의한다. N_CU를 제외한 모든 노드들은 자신의 firing 정보를 인접 노드에게 전송할 때 N_CU를 통해서만 송수신이 가능하다. 실선으로 표시한 N_CU는 일반 노드와 같이 동작을 수행한다. N₃이 firing 하게 되면 N₃의 firing 정보는 N_CU만 수신할 수 있으며, 다른 노드들은 N_CU를 통해서만 N₃의 정보를 얻을 수 있다. 일반 노드들은 Փ_Ni(t) = 1이 될 때까지 다른 노드들의 firing을 감지하고, N_CU는 다른 노드들의 firing이 감지되면 Δ_NCU(t)= Փ_NCU(t) - Փ_Ni-1(t)를 구하고 Mimic firing을 한다. Mimic firing을 통해 각 노드들은 인접 노드의 firing 정보를 알고 수식 (1)을 구한다. 자신의 firing 직후의 firing이 감지되면 다음 인접 노드로 인식하여 Δ_Ni+1(t)를 구한다. 또한 현재의 Δ_Ni(t)을 직전의 인접노드와 자신의 firing시간차로 인식하고 중간 값을 계산하여 FT_Ni를 수정한다[7].

기존 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 위치를 정한다.

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₀,N₁,N₂,N₃의 초기 위치는 임의로 T상에 배치되며, 모든 노드들은 초기 배치시 T만큼의 시간이 지날 때 까지(t = T) 아무런 동작 수행을 하지 않으며, GP신호를 수신하기 위해 대기한다. T시간 내에 GP가 감지되면 LN가 있다고 판단하고, 각 노드들은 네트워크에서 일반 노드의 동작을 수행하게 된다.

T시간 내 GP신호를 감지하지 못할 경우 네트워크에 LN이 없는 것으로 판단하여 LN를 선출하게 된다. 모든 노드들의 시간 흐름은 시계방향으로 회전한다고 가정하고, 12시에 위치하면 firing한다. LN는 firing을 하기전에 주변 노드들에게 자신의 주기 시작 정보를 가지고 있는 GP신호를 주변 노드들에게 전송하고 일반 노드와 같이 동작하게 된다. (그림 5)-(a)는 초기 네트워크에 배치된후 T시간만큼 대기한 모든 노드들이 GP신호를 받지 못하였지 때문에, 처음 firing하는 노드 N₀이 LN₀가 된다. 그림 5-(b)는 LN₀가 보내는 GP신호에 의해 모든 노드들의 주기 시작 시각이 동기화된 상태이다. LN₀는 각 노드들이 주기의 시작을 맞추기 위해 GP를 보내며, 일반 노드의 동작도 수행하게 된다. 그림 5-(c)는 GP신호를 기준으로 T동안 firing한 모든 노드들은 각각 BFC, AFC로 저장한다. 저장된 정보와 수식 (5)를 이용하여, 노드들은 다음 주기의 FT를 결정하게 되며, 그림 5-(d)와 같이 네트워크 동기화 상태 완료가 된다[8].

본 논문에서 제안하는 BC-DESYNC는 기존의 다중 접속 방법의 동기화 과정을 추가적인 장비가 필요 하지 않고, 간단한 규칙과 펄스 신호를 이용하여 동기를 유지 할 수 있기 때문에 비용적인 측면에 있어서 효율적이다.

표 1은 DESYNC, Mimic DESYNC, C-DESYNC의 노드 기본정보와 본 논문에서 제안하는 BC-DESYNC의 노드 기본정보를 비교한 표를 나타낸다.

다음은 (표 1)에서 사용되는 노드 기본정보에 대한 설명이다.

DESYNC 노드 기본정보

Mimic DESYNC 노드 기본정보

C-DESYNC 노드 기본정보

BC- DESYNC 노드 기본정보

기존의 DESYNC는 동기화 상태에 이르기까지 노드의 개수에 따라 동기화 완료시까지 지연시간이 달라지지만, BC- DESYNC는 GP를 기준으로 네트워크에 참가한 모든 노드의 개수를 파악한다. 모든 노드의 개수를 파악하기 위해서 GP를 기준으로 개수를 파악하며 자신의 위치를 파악하기 위해서 자신의 FT를 기준으로 이전에 firing한 노드의 개수 BFC와 이후에 firing한 노드의 개수 AFC의 정보를 이용한다. 또한, 중앙제어기능과 전송범위가 넓은 N_CU를 이용해 firing 신호를 듣지 못하는 일반노드에게도 firing 정보를 전송해 모든 노드의 개수를 파악할 수 있다. 그리고 다음 주기에서 수식 (5)를 이용해 동기화를 이룬다.

본 논문에서 제안하는 BC-DESYNC는 기존 다중접속방법의 동기화 과정에서 필요한 추가적인 장비를 사용하지 않고 간단한 방법을 통한 동기화를 이룰 수 있다. 또한 DESYNC의 단점인 동기화 상대 완료가 되기까지의 지연시간을 보장하고 2-홉 무선네트워크 환경에서도 가능하도록 개선하였다. Mimic DESYNC는 노드 중에서 한 개의 노드를 전송범위를 넓게 하여 N_CU를 배치하고 주변 노드의 주기를 맞추기 위해서 GP를 사용한다[7].

제안하는 알고리즘의 N_i와 N_CU의 전송범위는 Mimic DESYNC의 그림 3과 같이 나타낸다. (a)는 N₁, N₂, N₃는 N₀과 각각 통신이 가능하지만 N₁, N₂, N₃는 서로 통신이 불가능한 상태이다. 하지만 제안하는 알고리즘에서는 (b)와 같이 N₁, N₂, N₃는 중앙제어기능을 가지고 있는 N_CU를 통하여 통신이 가능하도록 하였다.

N_CU의 동작과정은 주변의 노드 N_i가 firing을 하였을 때 전송범위가 넓은 N_CU가 주변 모든 노드에게 firing을 수행하여 모든 노드가 firing을 감지 할 수 있도록 하는 것이다. 본 논문에서는 N_CU가 firing하는 과정을 Mimic firing이라고 정의하고 모든 노드는 일반 노드 의 firing을 감지하지 못하며 오로지 N_CU의 Mimic firing을 가지고 모든 노드의 개수를 파악하고 수식 (5)를 이용해 다음주기의 firing 시간을 조정해 동기화를 이룬다. 그림 6, 그림 7은 BC-DESYNC의 N_i와 N_CU의 동작 알고리즘을 나타낸다. 먼저 그림 6의 N_i 알고리즘은 주기를 맞추기 위해서 GP를 감지하기 전까지는 동작하지 않고 GP신호를 감지한 뒤부터 본인의 FT을 기준으로 Mimic firing을 듣고 이전에 firing한 노드와 이후에 firing한 노드의 개수를 파악하고 ϕ_Ni(t)=1일 때 firing을 한다. 그 다음 다시 한 번 GP를 감지할 때 수식 (5)를 이용하여 다음주기의 firing 시간을 조정해 동기화를 이룬다. 그림 7은 N_CU의 동작 알고리즘이다. N_CU는 주변 노드의 firing을 감지하여 모든 노드에게 Mimic firing을 하고 본인의 AFC와 BFC를 계산한 다음 ϕ_NCU(t)=1일 때 자신의 Mimic firing과 GP를 보낸다. 1 주기의 경우에는 모든 노드는 GP를 이용해 주기를 맞추고 2주기의 경우에는 수식 (5)를 이용해 동기화를 이룬다.

본 논문에서 제안하는 알고리즘을 이용하여 노드를 구성하였을 경우에 동작과정은 그림 8과 같다. 그림 8에서 큰 원은 주기 T를 나타내며 진행 방향은 시계방향으로 firing을 한다. 작은 원은 N_CU와 N₁, N₂를 나타낸다. 그림 8-(a)는 T에서 임의로 생성된 그림이고, 일반 노드들은 N_CU가 GP를 보내기 전까지 firing을 수행하지 않는다.

그림 8-(b)는 N_CU가 GP를 보내어 노드들의 주기의 시작시간을 동기화 한 그림이다. 그리고 그림 8-(c)에서 T동안 firing을 들은 N_CU가 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를 적용한 네트워크는 N_CU를 이용하여 2주기 만에 동기화 상태 완료를 알 수 있다.

표 3은 DESYNC와 C-DESYNC와 BC- DESYNC를 적용한 네트워크에서 각 노드의 개수가 5개일 때, 동기화를 완료 후, 노드 하나가 삭제되었을 때, 동기화 상태 완료가 다시 이루어지기까지의 MTTSC를 비교한 표이다. DESYNC와 Mimic DESYNC를 적용한 네트워크는 노드 하나가 삭제되었을 때, 다시 동기화 상태 완료까지 걸리는 추가 시간이 필요한 반면, C-DESYNC는 3주기 내에 동기화를 이룬다. BC -DESYNC는 N_CU를 통해 통신을 이루기 때문에 2주기 만에 동기화 상태 완료까지의 시간을 단축할 수 있다.

표 4는 DESYNC와 C-DESYNC와 BC- DESYNC를 적용한 네트워크에서 노드가 4개일 때 동기화 상태 완료 후, 노드 하나가 추가되었을 경우, 동기화 상태 완료까지의 MTTSC를 비교한 표이다. DESYNC와 Mimic DESYNC를 적용한 네트워크에서는 하나의 노드가 추가된 후, 다시 동기화 완료 상태가 이루어지기까지 많은 주기가 소모된다. 하지만 C-DESYNC와 BC-DESYNC의 경우에는 모든 노드들이 개수를 파악하여 다음 주기의 firing 시간을 맞추기 때문에 2주기 만에 동기화 상태가 완료된다.

본 논문에서는 DESYNC 알고리즘을 이용한 소규모 네트워크에 적합한 동기화 방식의 BC-DESYNC 알고리즘을 제안한다. 기존 DESYNC는 각 노드들이 동기화를 이루는 지연시간을 보장하지 않는 반면, BC-DESYNC는 다른 노드들보다 전송범위가 넓은 노드 N_CU를 배치하여 중앙제어기능을 수행하도록 한다. 각 노드들의 전송 범위를 벗어나 통신이 불가능한 상태에서 N_CU를 통해서 통신이 가능하다. 즉 모든 노드들은 통신 범위에서 벗어나더라도 노드들과 N_CU가 통신을 할 수 있는 전송 범위 영역이 확장되었다.