한국컴퓨터정보학회 동계학술대회 논문집 제24권 제1호 (2016. 1)
65
WSN의 연결 복구 기법 및 알고리즘 연구 동향
송병후*, 김경태*, 이정준O, 윤희용*
*O성균관대학교 정보통신공학과
e-mail: [email protected]*, [email protected]*, {jungjune86, youn7147}@skku.eduO*
A survey of connectivity restoration thchniqus & algorithm in wireless sensor network
Byung-Hoo Song*, Kyung-Tae Kim*, Jung-June LeeO, Hee-Young Youn*
*ODept. of Electronical and Computer Engineering, Sungkyunkwan University
● 요 약 ●
최근 과학의 발달로 사물에 대한 다양한 센서와 통신 기능을 부여하여 사람 대 사람 또는 사물 대 사물 서로 교류하는 개념인 IoT(Internet of Things)가 화제이다. IoT를 구성하는 요소 중에 하나인 Wireless Sensor Networks(WSN)에 대한 연구를 한 다. WSN은 전쟁터의 정찰과 같은 가혹한 환경에 적용되며 이를 구성하는 센서는 제한된 자원을 가지고 있기 때문에 고장에 취약한 특성이 있다. 따라서 상호 통신이 외부 요인에 의해 단절된 네트워크의 연결 복구에 대한 연구가 지속적으로 이루어지 고 있다. 본 논문에서는 이러한 WSN 네트워크의 연결 복구 방식, 연결 복구기법 및 알고리즘의 연구 동향에 대해서 서술한다.
키워드: 무선 센서 네트워크(WSN), 복구(restoration), 연결(connectivity)
I. Introduction
최근 과학의 발달로 사물에 다양한 센서와 통신 기능을 부여하여 사람 대 사람 또는 사람 대 사물이 서로 교류하는 개념인 IOT(Internet of Things)과 이슈가 된다. 본 논문에서는 IOT를 구현하는 블루투스, 와이파이, 임베디드 시스템, WSN들 중 WSN에 대한 연구를 한다.
WSN의 기술은 전쟁터의 정찰, 해안 탐사, 목표 추적, 환경 탐사 등과 같은 가혹한 환경에서 많이 적용된다.[1] 센서들은 작은 크기와 제한된 에너지를 가지고 있어 가혹한 환경에서 고장에 취약하다.
따라서 끊어진 네트워크와 네트워크 사이의 연결 복구는 중요하다.
본 논문에서는 이러한 WSN을 연결하는 모델링이나 끊어진 네트워크 를 복구하는 여러 효율적인 방식 및 알고리즘의 연구 동향을 서술한다.
II. Preliminaries
1. Related works
WSN 구조
WSN을 구성하는 센서 장비는 각 회사의 제원에 따라 상이한 구조를 가지지만, 크게 센서 각각의 노드와 그리 전체적인 네트워크로 구성된다. Fig.1.은 WSN의 구성도를 보여준다. WSN은 크게 Sensing부, Processing부, Tranceiver부, Power source부로 나누어 진다. Sensing부는 센서의 배열 및 측정을 담당하며, Processing부는
센서 노드 하나는 마이크로컨트롤러의 일을 수행한다. Tranceiver부 는 메시지의 무선 송수신을 담당하며, Power source부는 구성 요소의 전원 공급을 담당한다.
Fig. 1. WSN Block diagram
III. The Proposed Scheme
WSN를 구성하는 모델링 방식으로는 3가지가 있다. 첫 번째 Undirected graph이다. 정점들은 센서 노드를 나타내고 간선들은 두 노드의 상호 소통을 나타난다. 모든 무선 센서 네트워크는 무 방향 그래프로 표현 가능하다. 해당 모델에서 통신 단절이 일어날 경우 이러한 그래프 개념을 이용하여 복구하는데, 부모노드와 자식노 드 개념을 활용한다. 해당 방식의 단점은 자식노드의 연결이 끊어
한국컴퓨터정보학회 동계학술대회 논문집 제24권 제1호 (2016. 1)
66
졌을 때 연결성을 보장하지 못하는 점이다. 하지만 부모노드가 고장 난다면 이것은 그것의 이웃 노드를 사용한다거나 또는 새로운 노드를 재배열 하여 연결을 복구할 수 있다. 두 번째 방식은 Minium spanning tree이다. 이 모델은 연결 복구과정에서 최소신장트리를 이용한다.
무선 센서 노드를 트리형태로 구성 가능하고 이 과정에서 프림(prim) 이나 크러스칼(kruskal) 알고리즘을 사용한다. 이후, 유클리드 거리를 이용하여 노드 사이에 가중치를 구하고 최소신장트리를 찾는다. 마지 막으로 Steiner tree 모델이 있다. 해당 모델은 노드의 위치를 스타이너 트리 정점을 찾거나 또는 노드가 이동 위치에 따라 재배치하기 위해 결정한다. 이 스타이너 트리에 문제점은 전형적인 적당한 적합 알고리 즘이 존재하지 않는 문제이다. 때문에 극도의 가혹한 환경 네트워크에 는 적하지 않다. 반면에, 해당 방법은 노드의 위치를 재배열할 경우는 비교적 높은 효율을 보인다. 일반적인 WSN 네트워크의 손실은 피해가 적으나 큰 손실일 경우에는 전체 네트워크를 분해해서 별도로 복구하 여야 한다. 이러한 복구기법으로는 세 가지가 존재한다. 활동적인 복구는 전 처리 과정이나 결정 작업을 고장이전에 준비하여, 고장 즉시 복구를 가능케 하는 방식이다[2]. 수동적인 복구는 해당하는 노드가 고장이 났을 경우 고장 상태에 적합한 복구 작업을 진행하는 방식이다.[3] 위의 두 가지 방식을 합친 활동적/수동적인 복구는 전처리 과정을 하지만 노드 장애가 발생할 경우에만 복구를 진행한다 [4]. WSN 복구기법을 위한 알고리즘으로는 크게 중앙처리와 분산처 리가 존재한다. 중앙처리 알고리즘은 모든 노드들은 함께 작동하며 이때 알고리즘이 실행된다. 해당 방식은 상호관계를 전부 파악 가능하 여 복구 진행이 간단하다는 장점이 있지만 알고리즘이 증가할수록 문제의 사이즈가 커져 버린다는 단점이 있다. 때문에 대규모의 네트워 크에는 적합하지 않다. 마지막으로 분산처리 알고리즘이 있다. 해당 방식은 문제를 지역적으로 처리하는 방식이다. 분배화의 장점은 큰 규모의 네트워크에는 적합하지만 이를 구현하기가 복잡한 단점이 있다.
IV. Conclusions
본 논문에서는 WSNs의 특징과 구조에 대해 서술하고 모델링 방식과 복구기법 그리고 알고리즘에 대해서 서술했다. 이를 바탕으로 차세대 기술인 IoT에 대해 서술을 하지 않았지만 한발 다가갈 수 있다.
Acknowledgment
본 연구는 BK21Plus 사업, 한국연구재단 기초연구사업 (2013R1A1A2060398), 삼성전자, 미래창조과학부 및 정보통신기술 연구진흥센터의 정보통신·방송 연구개발사업 (1391105003)의 일환 으로 수행하였음.
References
[1] Jennifer Yick and Biswanath Mukherjee and Dipak Ghosal, "Wireless sensor network survey.", Computer networks, Vol. 52, Issue 12, pp. 2292-2330, August, 2008
[2] Sudip Misr and Ankur Jain, "Policy controlled self-configuration in unattended wireless sensor networks.", Journal of Network and Computer Applications, Vol 34, Issue 5, pp. 1530-1544, September, 2011
[3] Ameer Ahmed Abbasi and Younis Mohamed and and Kemal Akkaya. "Movement-assisted connectivity restoration in wireless sensor and actor networks.", Parallel and Distributed Systems, IEEE Transactions on, Vol 20, Issue 9, pp. 1366-1379, Sept, 2009
[4] Imran, Muhammad, et al. "Localized motion-based connectivity restoration algorithms for wireless sensor and actor networks." Journal of Network and Computer Applications, Vol 35, Issue 2, pp. 844-856 March 2012
