무선 센서 네트워크에서 네트워크 연결성 유지를 위한 ＦＦＤ 선정 방법 및 장치 document_id A220623104760

무선 센서 네트워크의 네트워크 디바이스는 가정의 가전기기, 사무기기 및 각종 장치들을 위해 간편한 근거리 무선 네트워크의 표준이 필요하다. 특히 USN은 다양한 장치들에 부착되어 사용하기 위해 무선의 네트워크가 필요하며 제한된 프로세스 파워를 가지고 있는 장치에 기존의 무선 랜 디바이스를 사용하기에는 무리가 있기 때문에 USN에 필요한 네트워크 디바이스는 통신 프로토콜이 가벼워야 한다. 아울러, 플러그앤플레이(Plug and Play) 방식의 간편한 설치로 다양한 장치들간의 상호 협력적 네트워크를 도모하기 위한 확장성이 요구된다. 나아가, USN 네트워크 장치들은 이동성과 휴대성을 고려하여야 하므로 저전력적인 특성과 산업적인 측면에서 가격이 저렴해야 하는 특성이 요구된다. 일반적으로 USN의 네트워크 표준으로 IEEE 802.1x의 무선 네트워크 표준들을 따르게 되는데, 기존의 IEEE 802.11 표준으로부터 LAN보다 작은 범위를 갖는 PAN을 위한 표준으로 IEEE 802.15 표준이 제정되었다. IEEE 802.15 표준안은 WPAN을 구성하고 이를 지원하기 위해 제안된 표준이다. 이에 대한 기반 기술은 WLAN 저전력 소모와 복잡도가 낮은 영역에서 무선 기술을 바탕으로 WPAN WG(WPAN Working Group, IEEE 802.15.4)에서 연구중이며, 개인의 생활 공간 10m 내에서 통신을 가능하게 하는 물리 계층과 데이터 링크 계층의 표준화를 수행하고 있다. IEEE 802.15.4는 LR-WPAN(Low-Rate Wireless Persoal Area) 네트워크의 MAC과 물리계층에 대한 표준이며 저속의 통신 대역과 저전력을 목표로 하는 프로토콜로서 현재 센서 네트워크 구현에 가장 적합한 통신 기술로 인식되고 있다. IEEE 802.15.4는 2.4GHz, 868/915MHz의 3개의 밴드를 지원하며, 네트워크 장치간의 네트워크 접근 방식은 CSMA-CA를 기본으로 한다. 또한, IEEE 802.15.4.의 네트워크 장치는 두 종류의 장치로 구분되는데, 하나는 피어투피어를 지원하고 코디네이터 기능을 지원하는 FFD(Full Fuction Device)이고 다른 하나는 네트워크 말단에서 접속만 가능한 RFD(Reduced Function Device)이다. FFD는 IEEE 802.15.4가 지원하는 모든 네크워크 토폴로지를 지원하며 FFD와 RFD 사이에서 데이터를 주고받을 수 있고 PAN 코디네이터의 역할을 수행할 수도 있으며, IEEE 802.15.4에서 노드가 할 수 있는 모든 기능을 수행한다. 이에 비해, RFD는 더 작고 가벼운 장치에 적합하도록 디자인된 장치로서 단순 기능과 간단한 동작으로 에너지 소모율을 낮추기 위한 장치이다. RFD는 네트워크 토폴로지의 말단에서 접속해서 데이터 전송만이 가능하다. 이는 RFD가 피어투피어 형태로 데이터를 전송할 수 없음을 의미하고 더불어 PAN 코디네이터의 역할을 수행할 수 없음을 의미한다. 즉, RFD는 데이터를 FFD로만 전송가능할 뿐 데이터의 릴레이 기능을 수행할 수는 없다. IEEE 802.15.4 네트워크에서는 노드를 FFD로 동작시킬지 또는 RFD로 동작시킬지 여부를 결정하는 과정이 필요하며, 어떠한 노드를 FFD로 선정할지 결정하기 위해 CDS(Connected Dominant Set)을 이용한 알고리즘들이 제안되었었다. Dominating Set은 네트워크를 하나의 그래프 G로 보았을 때, 그래프 G에 속하는 모든 점들이 어떤 집합에 속하는 점들 중 하나이거나 그 집합에 속하는 점들의 이웃하는 점들이 포함된다면 그 집합을 Dominating Set이라고 한다. CDS는 Dominating Set을 이루고 있는 점들이 모두 연결성을 가지고 있을 경우의 집합을 의미하며, 그 중에서 가장 작은 CDS를 MCDS(Minimum CDS)로 정의한다. 일반적인 그래프에서, MCDS를 찾는 것은 가능하지 않다는 것이 알려져 있으며, CDS의 크기를 줄여나가는 알고리즘들이 제시되었다. 도 1은 CDS를 설명하기 위한 네트워크의 일례를 도시한 도면이다. 도 1에서, 네트워크는 x,y,u,v,z의 5개의 노드가 존재하며, 이중 u 노드 및 v 노드는 다른 모든 노드들과 연결성을 유지하고 있기 때문에, u,v는 CDS로 정의할 수 있다. 특히, v 노드는 모든 노드들과 연결성을 유지하고 있는 바, v 역시 CDS로 정의할 수 있으며, v는 MCDS에 해당된다. CDS를 찾기 위한 종래의 알고리즘으로 마킹 프로세스(Marking Process) 0026# 룰-K가 있다. 이 방식은 마킹 프로세스에 의해 CDS를 찾고 룰-K 방식에 의해 CDS의 사이즈를 줄이는 방식이다. 이 방식은 두 단계에 걸쳐서 연산을 하여야 하므로 FFD를 찾는데 많은 시간이 소요되는 문제점이 있었다. 마킹 프로세스 0026# 룰-K의 문제점을 해결하기 위해 Self-Pruning 방식이 제안되었다. 도 2는 종래의 Self-Pruning 방식을 설명하기 위한 네트워크 구성을 도시한 도면이다. 도 2를 참조하면, Self-Pruning은 싱크(Sink) 노드인 0번 노드를 기준으로 각 노드들에게 순차적으로 아이디를 부여하고 각 노드별로 연결성 테스트를 하는 방식으로 CDS를 찾는 바, 한 번의 단계로 CDS를 찾아낼 수 있다. 그러나, Self-Pruning은 홉수가 작은 노드가 우선권을 가지고 연산이 수행되는 관계로 네트워크를 구성하는 노드들에 순차적으로 아이디가 부여되어야 하는데, 실질적인 분산 네트워크에서 이러한 방식으로 아이디를 부여하는 것은 상당히 어려운 문제점이 있었다. 또한, Self-Pruning은 CDS를 찾기 위해 각 노드에 대해 2-홉(Hop)의 이웃 노드 정보를 필요로 하였다. 그러나, 헬로 메시지들의 충돌로 인해 2-홉 이웃 노드 정보를 획득하는 것은 어려운 문제점이 있었으며 에너지 측면에서 비효율적이기도 하였다.