KR101486462B1

KR101486462B1 - 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템 및 기법

Info

Publication number: KR101486462B1
Application number: KR1020130165399A
Authority: KR
Inventors: 유재수; 박준호; 손인국; 류은경
Original assignee: 충북대학교 산학협력단
Priority date: 2013-12-27
Filing date: 2013-12-27
Publication date: 2015-01-27
Anticipated expiration: 2033-12-27

Abstract

본 발명은 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템 및 기법에 관한 것으로서, 무선 센서 네트워크 환경에서 홀(Hole)을 감지하기 위한 밀도 검사 및 홀-경계 노드 검출을 수행하고, 홀에 의한 위치 오류를 보정하기 위한 앵커 노드 위치 정보 및 누적 홀-경계 노드 수의 수집 메시지 전파와 노드 간 거리 추정을 수행하고, 누적 홀-경계 노드 수를 기반으로 거리 오차 보정을 수행한다. 본 발명에 따르면, 현존하는 센서 네트워크에서의 센서 노드 위치 측위 기법 중에서 센서 네트워크에서 위치 측위의 기준 노드인 앵커 노드를 가장 적게(4개) 활용함으로써 기반 환경 구축비용을 최소화할 수 있고, 또한 홀이 존재하는 센서 네트워크 환경에서 홀에 인접한 센서 노드의 주변 센서 노드 밀도가 감소하는 특성을 적용하여 홀-경계 노드를 검출하는 기법을 수행함으로써 홀을 효과적으로 탐지할 수 있으며, 노드마다 거리가 다른 밀집도의 특성을 적용하여 거리를 추정하는 밀집 확률 모델링 기법을 수행함으로써 홀이 존재하는 센서 네트워크 환경에서도 높은 품질의 위치 측정 결과를 얻을 수 있다.

Description

무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템 및 기법{Sensor Positioning System and Scheme Considering Holes in Wireless Sensor Networks}

본 발명은 무선 센서 네트워크에서의 센서 노드의 위치 인식 기법에 관한 것으로, 더욱 상세하게는 센서 네트워크를 구성하는 센서 노드의 실제 배포 과정에서 홀이 발생하였을 경우, 이웃 센서 노드의 밀도를 기반으로 홀-감지 알고리즘 및 누적 홀-경계 노드 수를 기반으로 거리 보정을 통해 센서 노드의 위치를 추정하는 위치 측정 모델링 알고리즘을 수행함에 따라 홀이 존재하는 환경에서 센서 노드의 위치 측정 오차율을 경감시키는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템 및 기법에 관한 것이다.

최근 컴퓨팅 기술의 비약적인 발전과 신호 처리 기술, 소형 전자 장치 개발 기술, 무선 통신 기술이 발전함에 따라 센서 네트워크에서 사용되는 센서 노드는 소형화, 저비용화, 저전력화가 가능하게 되었다. 무선 센서 네트워크의 주요 목적은 주변 환경이나 관찰하고자 하는 대상의 상태와 관련된 정보를 사용자에게 전달하는 것이다. 이러한 목적에 따라 수집 데이터를 기반으로 효과적인 상황 감지를 수행하는 분야를 무선 센서 네트워크(WSN: Wireless Sensor Networks)라는 용어를 사용한다.

센서 네트워크에서 사용되는 센서 노드는 크기가 매우 작고, 소형 배터리로 구동되므로, 에너지 사용에 대한 제약, 약한 연산 능력으로 인한 데이터 처리의 제한, 네트워크 대역폭의 제한의 특성이 있다. 일반적으로 센서 네트워크는 재해나 전쟁터, 사막과 같이 인간이 접근하기 힘든 지역과 산불, 재난과 같은 지역에서 데이터를 수집하거나 감시하기 위한 용도로 활용된다. 일반적으로 군사 응용 분야에서 전장의 상황을 감시하고, 핵 또는 화학 공격을 탐지하기 위한 목적으로 활용되고, 화재 및 홍수 감지, 토양 및 대기 상황 인지 등의 환경 모니터링 및 동물의 생태를 감시하기 위한 목적으로 활용된다. 이런 다양한 분야에 모니터링 응용으로 사용되는 센서 네트워크는 이벤트에 대한 데이터 수집뿐 아니라 해당 이벤트가 발생한 위치에 대한 표현은 가장 필수적이고 일반적인 기반 기술이다.

무선 장치를 사용하는 위치 인식 방법은 모든 기기들이 GPS(Global Positioning System) 모듈을 탑재하여 위치 정보를 수집하는 방법이 일반적이다. 하지만 이는 대규모의 센서 네트워크 환경에서 과도한 구축비용 및 GPS 모듈 사용에 따른 에너지 소모 문제를 야기한다. 그러므로 한정된 에너지를 바탕으로 동작하는 센서 네트워크에서 에너지 사용을 감소시키기 위한 위치 측정 기법들이 활발하게 연구되고 있다. 현재 연구는 자신의 위치를 모르는 일반 노드(Unknown Node)와 절대 위치를 알고 있는 앵커 노드(Anchor Node)를 통한 측정 방식으로 이루어지고 있다. 위치를 추정하기 위해서는 앵커 노드 정보를 기반으로 하는데, 앵커 노드는 GPS 모듈을 탑재하고 있어 자신의 위치를 알고 있으며, 위치를 모르는 일반 노드보다 최대 2배의 파워 배율을 가짐으로써, 일반 노드보다 통신 반경이 매우 넓다는 특징을 가지고 있다. 앵커 노드를 기반으로 위치를 추정하면 대부분의 일반 노드는 GPS 모듈을 장착하지 않고도 측정이 가능할 뿐 아니라 구축비용이 감소되는 큰 장점을 가지고 있으므로 이를 통한 측위 연구 기법들이 연구되고 있다.

최근에 연구되는 대표적인 위치 인식 기술은 거리 기반(Range-based) 기법과 거리 비종속(Range-free) 기법으로 나뉜다. 거리 기반 기법은 위치 추정을 할 때 이웃 센서 노드 간의 거리(Distance)나 각(Angle) 정보를 통해 노드 간 거리를 계산하고 이 정보를 통해 위치를 추정하는 방식이다. 거리 기반 기법은 위치 정확도가 높지만 거리 계산 시 노드마다 초음파 모듈과 같은 부수적인 장비가 필요하다는 단점을 가지고 있다. 거리 비종속 기법은 거리 기반 기법과는 달리 거리를 계산하기 위해 노드 간 통신 여부를 판단하여 노드 간의 연결 정보를 통해 거리 연산 과정을 수행한다. 이를 통해 거리를 추정하여 임의의 센서 위치를 추정하는 방식이다. 전체 네트워크에서 앵커 노드만이 GPS 모듈을 장착하고 있으므로 효율적이며 에너지 소모, 네트워크 구축비용을 최소화하는 것이 가능하다. 거리 비종속 측위 기법은 센서 노드가 격자(Grid) 형식과 같이 센서 노드가 일정한 간격을 가지고 배포되는 환경인 균일 네트워크를 전제로 이웃 노드 간 거리 또는 인근 노드와 통신을 통해 정보를 수집하여 센서의 위치를 추정하였다. 하지만 기존 기법에서는 센서 네트워크상에 홀이 존재하는 상황을 고려하지 않았다. 홀은 강 또는 호수와 같이 지형에 의해 노드가 분포하지 못하거나, 재해 또는 공격으로 인한 노드가 파괴될 경우, 혹은 노드의 한정된 에너지를 모두 활용하여 수명이 다하였을 경우와 같이 매우 일반적으로 발생 가능한 상황이다. 따라서 홀이 존재하지 않는 환경에서 제안된 위치 측정 기법들을 실제 응용 환경에 적용하는 것은 부적합하며, 네트워크상에 홀이 존재하는 상황에서 기존 기법을 통한 거리 추정은 오차율이 매우 높다는 문제점이 있다.

[1] M. Yeo, D. Seong, J. Yoo, "In Network Data Centric Storage Scheme Considering Geographical Routing and Data Hot Spots in Sensor Networks," Journal of KIISE: Databases, vol.38, no.3, pp.165-173, 2011.(in Korean) [2] P. Huang, J. Chen, Y. Larosa, T. Chiang, "Estimation of Distributed Fermat-Point Location for Wireless Sensor Networking," Sensors 2011, no.4, pp.4358-4371, 2011. [3] T. He, C. Huang, B. Blum, J. Stankovic, T. Abdelzaher, "Range-Free Localization Schemes for Large Scale Sensor Networks," Proc. of Annual International Conference on Mobile Computing and Networking(MOBICOM '03), pp.81-95, 2003. [4] D. Niculescu, B. Nath, "DV Based Positioning in Ad hoc Networks," Telecommunication Systems, vol.22, no.1-4, pp.267-280, 2003. [5] I. Son ,H. Park, E. Ryu, J. Park, J. Yoo, "A Sensor Positioning Scheme Considering Holes in Wireless Sensor" Proc. of the Korea Computer Congress(KCC) 2013, pp.871-873, 2013. [6] A. William, "Central Limit Theorem," International Encyclopedia of the Social Sciences, pp.486-487, 2008.

따라서, 본 발명은 상기한 종래 기술의 문제점을 해결하기 위해 이루어진 것으로서, 본 발명의 목적은 센서 네트워크를 구성하는 센서 노드의 실제 배포 과정에서 홀이 발생하였을 경우, 홀-경계 노드의 인식 및 이를 활용한 홀-감지 알고리즘과 센서 노드의 밀집도의 특성을 적용하여 거리를 추정하는 밀집 확률 모델링 알고리즘과 홀을 포함한 센서 노드의 추정 거리 보정 알고리즘을 통해 무선 센서 네트워크의 특성을 고려하여 센서 위치 인식 기법을 핵심으로 최소의 앵커 노드만을 활용하여 높은 정확도의 위치 추정 결과를 산출할 수 있도록 하는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템 및 기법을 제공하는데 있다.

상기와 같은 목적을 달성하기 위한 본 발명의 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템은, 이웃 노드의 수를 통한 밀도 검사 및 센서 노드 밀도를 통한 홀-경계 노드 검출을 수행하는 홀 검출부; 센서 노드에서의 이웃한 노드의 밀집도에 따라 추정 거리를 산출하는 추정거리 산출부; 및 상기 추정 거리와 앵커 노드 간 실제 거리 차이의 오차 비율을 연산하여 상기 추정 거리를 보정하는 오차 보정부를 포함하는 것을 특징으로 한다.

상기 홀 검출부는, 통신 반경 내에 비콘 메시지를 전파하여 이웃 노드의 수로부터 이웃 노드의 밀도를 검사하는 밀도 검사부; 및 앵커 노드간 홀-경계 노드 검출 메시지에 대응하여 일반 노드에서 통신 반경 내의 센서 노드 밀도와 이웃 노드들을 기준으로 수집한 센서 노드 평균 밀도를 비교하여 홀-경계 노드 여부를 검출하는 홀-경계 노드 검출부를 포함한다.

한편, 본 발명의 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법은, (a) 무선 센서 네트워크 환경에서 홀(Hole)을 감지하기 위한 밀도 검사 및 홀-경계 노드 검출을 수행하는 단계; (b) 상기 홀에 의한 위치 오류를 보정하기 위한 앵커 노드 위치 정보 및 누적 홀-경계 노드 수의 수집 메시지 전파와 노드 간 거리 추정을 수행하는 단계; 및 (c) 누적 홀-경계 노드 수를 기반으로 거리 오차 보정을 수행하는 단계를 포함하는 것을 특징으로 한다.

상기 단계 (a)의 밀도 검사는, 상기 네트워크 내의 일반 노드가 자신의 통신 반경 내에 비콘 메시지를 전파하여 이웃 노드의 수를 구하는 단계; 및 상기 이웃 노드의 수를 기반으로 통신 반경 내의 이웃 노드의 밀도를 산출하는 단계를 포함한다.

상기 단계 (a)의 홀-경계 노드 검출은, 임의의 한 개의 앵커 노드에서 홀-경계 노드 검출 메시지를 나머지 앵커 노드로 전파하는 단계; 일반 노드가 자신을 기준으로 한 통신 반경 내의 센서 노드 밀도와 통신 반경 내의 이웃 노드들을 기준으로 수집한 센서 노드 평균 밀도를 비교하는 단계; 및 이웃 노드들을 기준으로 수집한 평균 밀도보다 작을 경우 해당 노드가 초기 홀-경계 노드로서 선택되는 단계를 포함한다.

상기 단계 (b)는, 각 앵커 노드가 자신의 위치 정보 메시지를 일반 노드에 전파하는 단계; 상기 앵커 노드 및 일반 노드가 메시지를 전송한 앵커 노드 정보, 홉-수와 노드 ID 리스트를 포함하는 경로 정보, 홀-경계 노드 수를 저장하는 단계; 모든 노드에서 앵커 노드와 일반 노드의 정보를 유지하는 단계; 및 상기 모든 노드가 정규분포(Normal Distribution) 확률의 중심극한정리(Central Limit Theorem)를 토대로 이웃 노드의 수에 따라 거리를 측정하는 단계를 포함한다.

상기 단계 (c)는, 위치 측정 대상 일반 노드가 자신과 가장 인접한 앵커 노드와 위치 정보 메시지를 전송한 앵커 노드를 선정하는 단계; 및 최단 경로 안에 홀-경계 노드로 검출된 노드 간의 거리 보정을 수행하는 단계를 포함한다.

상술한 바와 같이, 본 발명에 의한 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템 및 기법에 따르면, 현존하는 센서 네트워크에서의 센서 노드 위치 측위 기법 중에서 센서 네트워크에서 위치 측위의 기준 노드인 앵커 노드를 가장 적게(4개) 활용함으로써 기반 환경 구축비용을 최소화할 수 있다.

또한, 본 발명은 홀이 존재하는 센서 네트워크 환경에서 홀에 인접한 센서 노드의 주변 센서 노드 밀도가 감소하는 특성을 적용하여 홀-경계 노드를 검출하는 기법을 수행함으로써 홀을 효과적으로 탐지할 수 있다.

그리고, 본 발명은 노드마다 거리가 다른 밀집도의 특성을 적용하여 거리를 추정하는 밀집 확률 모델링 기법을 수행함으로써 홀이 존재하는 센서 네트워크 환경에서도 높은 품질의 위치 측정 결과를 얻을 수 있다.

도 1은 본 발명의 일 실시예에 따른 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템의 구성도이다.
도 2는 본 발명의 일 실시예에 따른 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법을 설명하기 위한 동작 흐름도이다.
도 3은 본 발명의 일 실시예에 따른 홀이 존재하는 무선 센서 네트워크의 배포 형태 및 센서 노드의 위치 측정을 기반 정보를 제공하는 앵커 노드의 배포 형태 및 환경에 대하여 설명하기 위한 도면이다.
도 4는 본 발명의 일 실시예에 따른 무선 센서 네트워크에서 홀-경계 노드 선정 과정을 설명하기 위한 도면이다.
도 5는 본 발명의 일 실시예에 따른 홀-경계 노드의 검출 결과를 설명하기 위한 도면이다.
도 6은 본 발명의 일 실시예에 따른 무선 센서 네트워크에서 발생 가능한 홀의 형태에 따른 검출 과정 중 홀의 형태가 직선 형태인 경우를 설명하기 위한 도면이다.
도 7은 본 발명의 일 실시예에 따른 무선 센서 네트워크에서 발생 가능한 홀의 형태에 따른 검출 과정 중 홀의 형태가 위로 볼록한 형태인 경우를 설명하기 위한 도면이다.
도 8은 본 발명의 일 실시예에 따른 무선 센서 네트워크에서 발생 가능한 홀의 형태에 따른 검출 과정 중 홀의 형태가 아래로 볼록한 형태인 경우를 설명하기 위한 도면이다.
도 9는 본 발명의 일 실시예에 따른 앵커 노드에서의 일반 노드로의 정보 전송을 위한 패킷 구조 및 해당 패킷을 수신한 일반 노드에서의 앵커 노드 정보 저장 테이블의 구조를 설명하기 위한 도면이다.
도 10은 본 발명의 일 실시예에 따른 일반 노드에서의 1-홉 내에 위치한 이웃 노드 정보 저장 테이블의 구조를 설명하기 위한 도면이다.
도 11은 본 발명의 일 실시예에 따른 1차원 상에서의 밀집 확률에 따른 추정 위치를 설명하기 위한 도면이다.
도 12는 본 발명의 일 실시예에 따른 2차원 상에서의 밀집 확률에 따른 추정 위치를 설명하기 위한 도면이다.
도 13은 본 발명의 일 실시예에 따른 홀에 의한 추정 거리와 실제 거리 사이에 오차가 발생하는 상황을 설명하기 위한 도면이다.

본 발명에서는 기존 연구가 홀이 존재하는 센서 네트워크에서 위치 측정 정확도가 크게 낮아지는 문제점을 보완하도록 홀이 존재하는 센서 네트워크 환경에서 위치 측정 오차를 줄여 높은 수준의 정확도를 갖는 위치 측정 결과를 반환한다. 또한, 홀이 존재하는 센서 네트워크 환경에서 정확도를 향상시키기 위해, 많은 수의 앵커 노드를 배치해야 하므로 높은 네트워크 구축비용이 소요되는 문제점이 발생한다. 본 발명에서는 최소의 앵커 노드인 총 4개의 앵커 노드를 센서 필드의 경계점에 배치하며, 이를 통해 기반 환경 구축비용을 최소화한다.

이하, 본 발명의 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템 및 기법에 대하여 첨부된 도면을 참조하여 상세히 설명하기로 한다.

본 발명은 여러 가지 상이한 형태로 구현될 수 있으며, 여기에서 설명하는 실시예에 한정되지 않는다. 그리고 도면에서 본 발명을 명확하게 설명하기 위해서 설명과 관계없는 부분은 생략하기로 하며, 명세서 전체를 통하여 유사한 부분에 대해서는 유사한 도면 부호를 부여하기로 한다.

명세서 전체에서, 어떤 부분이 어떤 구성요소를 "포함"한다고 할 때, 이는 특별히 반대되는 기재가 없는 한 다른 구성요소를 제외하는 것이 아니라 다른 구성 요소를 더 포함할 수 있는 것을 의미한다.

도 1은 본 발명의 일 실시예에 따른 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템의 구성도이다.

도 1을 참조하면, 본 발명의 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템은, 이웃 노드의 수를 통한 밀도 검사 및 센서 노드 밀도를 통한 홀-경계 노드 검출을 수행하는 홀 검출부(1)와, 센서 노드에서의 이웃한 노드의 밀집도에 따라 추정 거리를 산출하는 추정거리 산출부(2)와, 추정 거리와 앵커 노드 간 실제 거리 차이의 오차 비율을 연산하여 추정 거리를 보정하는 오차 보정부(3)를 포함한다.

여기서, 홀 검출부(1)는, 통신 반경 내에 비콘 메시지를 전파하여 이웃 노드의 수로부터 이웃 노드의 밀도를 검사하는 밀도 검사부(11)와, 앵커 노드간 홀-경계 노드 검출 메시지에 대응하여 일반 노드에서 통신 반경 내의 센서 노드 밀도와 이웃 노드들을 기준으로 수집한 센서 노드 평균 밀도를 비교하여 홀-경계 노드 여부를 검출하는 홀-경계 노드 검출부(12)를 포함한다.

한편, 센서 노드의 저장부(미도시)는, 센서 노드의 위치 측정의 기반 정보로 활용되는 앵커 노드에서 일반 노드로의 메시지를 수신한 일반 노드에서의 앵커 노드 정보를 저장하는 앵커 노드 정보 저장부와, 센서 노드의 위치 추정의 기반 정보로 활용되는 센서 노드에서의 1-홉 내에 위치한 이웃 노드 정보를 저장하는 이웃 노드 정보 저장부를 포함한다.

그러면, 여기서 상기와 같이 구성된 시스템을 이용한 본 발명의 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법에 대해 설명하기로 한다.

도 2는 본 발명의 일 실시예에 따른 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법을 설명하기 위한 동작 흐름도이다.

도 2를 참조하면, 본 발명의 위치 측정 과정으로서 초기 위치 정보 질의가 내려지면(S1) 홀의 감지 및 앵커 정보를 통해 일반 노드의 초기 거리를 추정하고 이 후, 노드 간 센싱 반경 내에 존재하는 이웃 노드에 따라 보정 거리를 산출하여 위치를 측정한다.

본 발명 동작 과정은 크게 3단계로 구분된다.

<단계 1> 무선 센서 네트워크 환경에서 홀을 감지하기 위한 밀도 검사 및 홀-경계 노드 검출 메시지 전파(S2~S3)

<단계 2> 홀에 의한 위치 오류를 보정하기 위한 앵커 노드 위치 정보 및 누적 홀-경계 노드 수의 수집 메시지 전파와 노드 간 거리 추정(S4~S7)

<단계 3> 누적 홀-경계 노드 수를 기반으로 하는 오차 보정(S8)

상기한 단계 S1 내지 S8을 진행하여 최종 위치 데이터 결과를 반환한다(S9).

도 3은 본 발명의 일 실시예에 따른 홀이 존재하는 무선 센서 네트워크의 배포 형태 및 센서 노드의 위치 측정을 기반 정보를 제공하는 앵커 노드의 배포 형태 및 환경에 대하여 설명하기 위한 도면이다.

도 3을 참조하면, 센서 네트워크는 실제 응용에서와 같이 홀이 임의의 형태로 존재한다. 또한, 자신의 절대 위치 정보를 알고 있는 앵커 노드(A = { A₁ , … , A₄ })는 양 끝에 배치된다. 앵커 노드는 일반 센서 노드의 위치 측정을 위한 기준 정보를 제공하는 노드로서, 본 발명의 수행을 위해 앵커 노드의 정보를 모든 일반 노드에게 브로드캐스트한다.

센서 네트워크상에 홀이 존재할 경우, 앵커 노드와 일반 노드들이 서로 통신을 할 때 최단 경로로 수행하는 것이 불가능하므로 홉-수가 증가한다. 결과적으로 홉-수의 증가는 센서 노드의 위치를 측정 할 때 홀이 존재하지 않는 상황보다 큰 오차를 발생시킨다. 이를 고려하여, 본 발명에서는 홀 감지를 위해 네트워크 내의 모든 일반 노드는 자신의 통신 반경 내에 비콘 메시지를 전파하여 이웃 노드의 수를 구한다. 이를 기반으로 통신 반경 내의 이웃 노드의 밀도를 산출한다. 식(1)은 통신 반경 내의 이웃 노드의 밀도 산출식을 나타내며, r은 통신 반경, n는 노드 i의 통신 반경 내에 위치한 이웃 노드의 수를 나타낸다.

--- 식(1)

도 4는 본 발명의 일 실시예에 따른 무선 센서 네트워크에서 홀-경계 노드 선정 과정을 설명하기 위한 도면이다.

도 4를 참조하면, 센서 네트워크상의 홀 감지를 위해 홀 주위에 위치한 홀-경계 노드를 인지할 필요가 있다. 홀-경계 노드를 검출하기 위해, 먼저 4개의 앵커 노드 중 임의의 한 개의 앵커 노드를 선정한 후, 홀-경계 노드 검출 메시지를 나머지 앵커 노드 방향으로 전파한다. 홀-경계 노드 검출 메시지는 { 최초 홀-경계 노드 ID, 홀-경계 노드 리스트 } 정보로 구성된다. 홀-경계 노드 검출 메시지를 수신한 일반 노드는 자신을 기준으로 한 통신 반경 내의 센서 노드 밀도와 통신 반경 내의 이웃 노드들을 기준으로 수집한 센서 노드 평균 밀도를 비교한다. 평균 밀도를 비교한 후, 이웃 노드들을 기준으로 수집한 평균 밀도보다 작을 경우 해당 노드는 초기 홀-경계 노드로서 선택된다. 식(2)은 홀-경계 노드 검출 조건을 나타낸다.

--- 식(2)

도 5는 본 발명의 일 실시예에 따른 홀-경계 노드의 검출 결과를 설명하기 위한 도면이다.

도 5를 참조하면, 이웃 노드의 밀도를 기반으로 하는 홀-경계 노드 검출 기법을 통해 직선(도 6), 볼록(도 7), 오목(도 8)과 같이 발생 가능한 모든 홀의 형태에 대해 경계 노드를 검출하는 것이 가능하다.

도 9는 본 발명의 일 실시예에 따른 앵커 노드에서의 일반 노드로의 정보 전송을 위한 패킷 구조 및 해당 패킷을 수신한 일반 노드에서의 앵커 노드 정보 저장 테이블의 구조를 설명하기 위한 도면이며, 도 10은 본 발명의 일 실시예에 따른 일반 노드에서의 1-홉 내에 위치한 이웃 노드 정보 저장 테이블의 구조를 설명하기 위한 도면이다.

홀-감지 및 홀-경계 노드의 검출이 완료된 후, 일반 센서 노드의 1차 거리 추정을 위해 각 앵커 노드는 자신의 위치 정보 메시지를 모든 일반 노드에 전파한다. 이를 수신한 모든 앵커 및 일반 노드는 메시지를 전송한 앵커 노드 정보, 메시지를 전송한 앵커 노드에서 이를 수신한 노드까지의 경로 정보(홉-수, 노드 ID 리스트) 그리고 홀-경계 노드 수를 저장한다. 모든 노드는 도 9 및 도 10과 같이 앵커 노드와 일반 노드의 정보를 유지한다. 수신한 노드까지의 경로 정보(홉-수, 노드 ID 리스트)는 1차 거리 추정을 위한 기반 정보로 사용되며, 홀-경계 노드 수는 오차 보정에 활용된다.

이 후, 모든 각 노드들은 정규분포(Normal Distribution) 확률의 중심극한정리(Central Limit Theorem)를 토대로 이웃 노드의 수에 따라 거리를 측정한다.

정규분포 또는 가우시안 분포란 어느 대상 표본들의 분포가 좌우대칭인 종 모양을 이루는 형태로써, 표본의 객체 수가 증가하거나 표본을 여러 번 시행횟수를 거칠수록 정규분포곡선을 나타낸다.

센서 네트워크 환경이 정규분포모델에 부합한다는 증명을 할 수 있는 이론이 중심극한정리이다. 다음은 중심극한정리의 정의이다.

<정의 1> 평균이 μ이고 분산이 σ2인 임의의 모집단에서 n개의 표본을 추출할 경우 n이 충분히 크다면(n≥30), 모집단의 확률분포형태와 상관없이 표본평균(X)의 확률분포는 평균=E(X)=μ이고, 표준편차=σ/√n인 정규분포에 근사하며, n이 무한대로 커지면 정규분포와 일치하게 된다.

<정의 2> 정규분포를 따르는 확률변수 X를 표준정규분포의 확률변수로 변환한 Z=(X-μ)/(σ/√n)는 근사적으로 N(0,1)인 표준정규분포를 따르게 된다.

두 정의를 토대로, 정규분포모델은 평균이 0인 지점으로 속하기 위해서는 표본의 개수가 30개 이상이어야 한다는 조건이 필요하며, 표본의 개수가 커질수록 정규분포의 μ로 가까워지게 된다. 이를 센서 네트워크 환경에서 보게 되면 표본의 개수는 수 천 개의 센서 노드가 배포되는 대규모 네트워크 환경이므로 표준정규분포곡선 중 평균이 0인 지점에 위치하게 된다. 즉, 확률 값이 1을 갖는다는 것은 주위 노드가 한 개라도 있다는 것을 표현한다. 따라서 중심극한정리와 정규분포모델을 센서 노드가 이웃하는 거리 추정 시 적용한다. 추정 거리는 정규분포표의 값을 토대로 산출하게 되는데, 노드는 자신의 통신 반경이 R일 경우 통신 범위는 Rㅧ범위각(θ=360ㅀ)의 면적을 갖는다. 거리 추정 기법을 적용하기 위해 1차원에서 노드 추정 지점을 고려한 후, 2차원에서 실제적으로 노드 거리를 추정하도록 한다.

도 11은 본 발명의 일 실시예에 따른 1차원 상에서의 밀집 확률에 따른 추정 위치를 설명하기 위한 도면이며, 도 12는 본 발명의 일 실시예에 따른 2차원 상에서의 밀집 확률에 따른 추정 위치를 설명하기 위한 도면이다.

도 11과 같이 1차원인 직선상에서 임의의 노드가 존재하는 지점은 간단히 평균이 0인 1/2지점으로써 직선에서 안쪽의 범위 길이와 바깥쪽의 길이가 같아지는 부분에 존재하게 된다. 반경 r을 갖는 면적인 2차원에서는 도 12와 같이 실질적으로 노드가 가지고 있는 통신 반경과 통신 범위각(θ=360ㅀ)으로 확장된다.

원을 그리게 되면 1차원 상 추정 위치 지점(m)보다 더 멀어져 내원과 외원의 면적이 같아지는 부분인 곡선 지점(n)에 존재한다. 이를 통해 노드 간 거리는 정규분포표의 수치를 통해 추정 가능하다. 식(3)은 정규분포표의 수치를 토대로 이웃 노드 간 분포에 따른 거리 산출식이다.

--- 식(3)

r은 센서 노드의 통신 반경이고, n은 자신의 이웃 노드 수이다. 초기 브로드캐스트를 통해 이웃한 노드에게 메시지를 수신한 후, 도 9와 도 10의 정보를 가지므로 모든 노드들은 식(3)을 이용하여 자신들의 이웃 노드 간 1-홉 거리를 추정한다.

예를 들면 Node ID=k인 노드가 1-홉 거리 추정 시 n=1, r=15인 경우 식(3)은 통신 반경 15m를 갖는 센서 노드에서 이웃 노드 1개가 존재할 경우 1-홉 거리 추정에 대한 식이다. 식(3)을 통해 노드 k의 1-홉 거리는 약 10.6m만큼 떨어져 있는 것으로 이웃 노드 간 추정 거리를 산출한다. 따라서 각 각의 센서 노드는 거리 추정 시 이웃 노드의 분포에 따라 1-홉 거리가 다르게 산출되며, 이는 밀집도가 다른 비 균일 네트워크 환경에서 좀 더 실제적인 거리 추정을 가능하게 한다.

각 노드는 이웃 노드 수에 근거하여 밀집 확률 이론을 토대로 1-홉 거리를 추정한다. 그러나 초기 각 노드가 추정한 1-홉 거리에서 오차가 발생하는 상황을 고려하여 이를 보정해주는 과정을 수행한다.

도 13은 본 발명의 일 실시예에 따른 홀에 의한 추정 거리와 실제 거리 사이에 오차가 발생하는 상황을 설명하기 위한 도면이다.

추정 거리는 최단 경로 기반의 노드 간 누적 거리를 활용하여 산출한다. 하지만 도 13과 같이 네트워크에 홀이 존재할 경우, 실제 최단 경로와 많은 오차가 발생한다. 도 13에서 앵커 노드 A₁부터 앵커 노드 A₂까지 실 거리는 120m이다. 하지만 홀이 존재하는 환경에서 노드 간의 누적 거리를 사용하면 145m가 산출된다. 따라서 추정 거리의 오차를 보정하기 위해 위치 측정 대상 노드의 홀-경계 노드 수를 기반으로 하는 보정을 수행한다.

위치 측정 대상 일반 노드는 거리 보정을 위해 2개의 앵커 노드를 필요로 한다. 이를 위해, 위치 측정 대상 일반 노드는 자신과 가장 인접한 앵커 노드와 위치 정보 메시지를 전송한 앵커 노드를 선정하고, 최단 경로 안에 홀-경계 노드로 검출된 노드 간의 거리 보정을 수행한다. 식(4)는 홀-경계 노드 간의 거리 보정 연산을 나타낸다. 식(4)에서 dEst_All는 위에서 선정된 두 앵커 노드 간의 누적 거리를 나타내며, dReal는 두 앵커 노드 간의 실제 직선거리를 나타낸다. 이를 기반으로 하는 오차 비율(error_rate)을 활용하여, 홀-경계 노드로 검출된 노드 간의 1-홉 거리를 산출한다.

--- 식(4)

위와 같은 과정을 통해, 모든 일반 노드의 1-홉 거리를 산출한 후, 이러한 1-홉 거리를 기반으로 4개의 앵커 노드와의 거리를 산출한다. 그리고 식(5)-식(8)을 사용하여 일반 노드의 위치를 측정한다. 식(5)-식(8)에서 (x, y)는 측정 노드의 좌표이고, (x_i, y_i)는 각 앵커 노드의 좌표 정보로써, 모든 노드들은 위치 추정 시 양 끝에 배치된 총 4개의 앵커 노드를 통해 측위 한다. 따라서 보정된 노드들의 추정 거리 d를 통해 오차를 감소시켜 전체 센서 노드의 위치를 추정한다.

--- 식(5)

--- 식(6)

--- 식(7)

--- 식(8)

이상에서 설명한 본 발명의 실시예는 장치 및/또는 방법을 통해서만 구현이 되는 것은 아니며, 본 발명의 실시예의 구성에 대응하는 기능을 실현하기 위한 프로그램, 그 프로그램이 기록된 기록 매체 등을 통해 구현될 수도 있으며, 이러한 구현은 앞서 설명한 실시예의 기재로부터 본 발명이 속하는 기술 분야의 전문가라면 쉽게 구현할 수 있는 것이다.

이상에서 본 발명의 실시예에 대하여 상세하게 설명하였지만 본 발명의 권리 범위는 이에 한정되는 것은 아니고 다음의 청구범위에서 정의하고 있는 본 발명의 기본 개념을 이용한 당업자의 여러 변형 및 개량 형태 또한 본 발명의 권리 범위에 속하는 것이다.

1 : 홀 검출부
11 : 밀도 검사부
12 : 홀-경계 노드 검출부
2 : 추정거리 산출부
3 : 오차 보정부

Claims

이웃 노드의 수를 통한 밀도 검사 및 센서 노드 밀도를 통한 홀-경계 노드 검출을 수행하는 홀 검출부;
센서 노드에서의 이웃한 노드의 밀집도에 따라 추정 거리를 산출하는 추정거리 산출부; 및
상기 추정 거리와 앵커 노드 간 실제 거리 차이의 오차 비율을 연산하여 상기 추정 거리를 보정하는 오차 보정부를 포함하는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템.
제1항에 있어서,
상기 홀 검출부는,
통신 반경 내에 비콘 메시지를 전파하여 이웃 노드의 수로부터 이웃 노드의 밀도를 검사하는 밀도 검사부; 및
앵커 노드간 홀-경계 노드 검출 메시지에 대응하여 일반 노드에서 통신 반경 내의 센서 노드 밀도와 이웃 노드들을 기준으로 수집한 센서 노드 평균 밀도를 비교하여 홀-경계 노드 여부를 검출하는 홀-경계 노드 검출부를 포함하는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 시스템.
(a) 무선 센서 네트워크 환경에서 홀(Hole)을 감지하기 위한 밀도 검사 및 홀-경계 노드 검출을 수행하는 단계;
(b) 상기 홀에 의한 위치 오류를 보정하기 위한 앵커 노드 위치 정보 및 누적 홀-경계 노드 수의 수집 메시지 전파와 노드 간 거리 추정을 수행하는 단계; 및
(c) 누적 홀-경계 노드 수를 기반으로 거리 오차 보정을 수행하는 단계를 포함하는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법.
제3항에 있어서,
상기 단계 (a)의 밀도 검사는,
상기 네트워크 내의 일반 노드가 자신의 통신 반경 내에 비콘 메시지를 전파하여 이웃 노드의 수를 구하는 단계; 및
상기 이웃 노드의 수를 기반으로 통신 반경 내의 이웃 노드의 밀도를 산출하는 단계를 포함하는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법.
제4항에 있어서,
상기 이웃 노드의 밀도(
)는 아래의 식(1)을 통해 계산하는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법.

--- 식(1)
여기서, r은 통신 반경, n은 노드 i의 통신 반경 내에 위치한 이웃 노드의 수를 각각 나타낸다.
제3항에 있어서,
상기 단계 (a)의 홀-경계 노드 검출은,
임의의 한 개의 앵커 노드에서 홀-경계 노드 검출 메시지를 나머지 앵커 노드로 전파하는 단계;
일반 노드가 자신을 기준으로 한 통신 반경 내의 센서 노드 밀도와 통신 반경 내의 이웃 노드들을 기준으로 수집한 센서 노드 평균 밀도를 비교하는 단계; 및
이웃 노드들을 기준으로 수집한 평균 밀도보다 작을 경우 해당 노드가 초기 홀-경계 노드로서 선택되는 단계를 포함하는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법.
제6항에 있어서,
상기 홀-경계 노드 검출의 조건은 아래의 식(2)와 같은 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법.

--- 식(2)
여기서,
은 이웃 노드의 밀도, n은 노드 i의 통신 반경 내에 위치한 이웃 노드의 수를 각각 나타낸다.
제3항에 있어서,
상기 단계 (b)는,
각 앵커 노드가 자신의 위치 정보 메시지를 일반 노드에 전파하는 단계;
상기 앵커 노드 및 일반 노드가 메시지를 전송한 앵커 노드 정보, 홉-수와 노드 ID 리스트를 포함하는 경로 정보, 홀-경계 노드 수를 저장하는 단계;
모든 노드에서 앵커 노드와 일반 노드의 정보를 유지하는 단계; 및
상기 모든 노드가 정규분포(Normal Distribution) 확률의 중심극한정리(Central Limit Theorem)를 토대로 이웃 노드의 수에 따라 거리를 측정하는 단계를 포함하는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법.
제8항에 있어서,
상기 모든 노드가 아래의 식(3)을 이용하여 자신들의 이웃 노드 간 1-홉 거리(
)를 추정하는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법.

--- 식(3)
여기서, r은 센서 노드의 통신 반경이고, n은 자신의 이웃 노드 수이다.
제3항에 있어서,
상기 단계 (c)는,
위치 측정 대상 일반 노드가 자신과 가장 인접한 앵커 노드와 위치 정보 메시지를 전송한 앵커 노드를 선정하는 단계; 및
최단 경로 안에 홀-경계 노드로 검출된 노드 간의 거리 보정을 수행하는 단계를 포함하는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법.
제10항에 있어서,
오차 비율(error_rate)을 활용하여 홀-경계 노드로 검출된 노드 간의 1-홉 거리(
)는 아래의 식(4)를 통해 계산하는 무선 센서 네트워크 환경에서 홀을 고려한 센서 위치 측정 기법.

--- 식(4)
여기서,
는 이웃 노드 간 1-홉 거리,
는 선정된 두 앵커 노드 간의 누적 거리,
는 두 앵커 노드 간의 실제 직선거리를 각각 나타낸다.