Advanced
Localization algorithm by using location error compensation through topology constructions
Localization algorithm by using location error compensation through topology constructions
Journal of the Korea Institute of Information and Communication Engineering. 2014. Sep, 18(9): 2243-2250
Copyright © 2014, The Korea 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. Copyright Ⓒ The Korea Institute of Information and Communication Engineering.
  • Received : February 05, 2014
  • Accepted : March 19, 2014
  • Published : September 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
진호 유
영구 권
ygkwon@konkuk.ac.kr

Abstract
무선센서 네트워크에서, 위치기반의 라우팅 알고리즘은 네트워크의 성능을 향상 시킬 수 있다. 따라서 많은 위치 추적 알고리즘이 제안되고 있다. 하지만, 실제 상황의 무선센서 네트워크에서 각각의 노드가 자신의 위치를 인지할 시 오차가 수반된다. 특히 실내 환경은 콘크리트 벽이나 가구와 같은 NLOS환경을 만드는 장해물을 가지고 있기 때문에 위치 추적 시 심각한 오차가 발생한다. 이러한 문제를 해결하기 위해서, 앵커노드로부터 얻어지는 위치정보로 구축한 토폴로지와 모바일 노드간의 연결을 가중치로 하는 MST 토폴로지 정보의 차이점을 이용해서 위치 오차를 보정하는 알고리즘을 제안한다. 제안한 알고리즘은 NLOS환경이 존재하는 네트워크에서, 위치 오차를 보정하여 위치기반 네트워크의 성능을 개선할 수 있다.
Keywords
Ⅰ. 서 론
최근 무선센서 네트워크는 화제감시, 사람의 출입이 어려운 장소의 모니터링, 군사지역의 보안 모니터링 등 다양한 응용 서비스를 제공하는 연구들을 바탕으로 언제, 어디서나 사용자가 정보 및 서비스를 제공받을 수 있는 유비쿼터스 기술의 실현을 가능하게 되었다 [1] . 이러한 기술들이 더욱 유용한 정보를 제공하기 위해서는 감시대상인 모바일 노드의 위치정보를 제공해야 할 뿐만 아니라, 에너지의 효율적인 사용과 패킷전송의 성공확률을 높이기 위한 토폴로지를 구축해야한다. 하지만 위치인식을 위해서 가장 많이 이용되는 GPS는 실내에서는 사용할 수 없다는 문제가 발생한다. 따라서 무선센서 네트워크에서는 실내 위치 인식을 위해서 노드들 간의 거리나 각도를 측정하여, angle-of-arrival(AOA), time-of-arrival(TOA), time-difference-of-arrival(TDOA), received signal strength(RSS)와 같은 기술들을 사용하고 있다 [2] . 하지만, 이와 같은 기술들은 노드들이 lineof-sight(LOS)환경에 있다는 가정 하에 사용되는 기술로써 실제 실내 환경인 non-line-of-sight (NLOS)환경에서는 심각한 오차가 발생하여 위치기반 네트워크의 성능을 저하시킨다 [3] . 따라서 이러한 위치 오차를 보정하기 위해서 least square estimation(LSE) [4] , min-max bounding box [5] 및 삼변측량법 [6] 과 같은 기법으로 위치추정 및 보정을 하는 많은 연구가 진행되고 있다.
본 논문에서는 서로 다른 정보를 이용해서 두 가지의 토폴로지를 구축하고, 이의 차이점을 이용해서 NLOS 환경에서 정확한 위치를 측정하고, 효율적인 토폴로지를 구축하는 알고리즘을 제안한다. 네트워크의 구성은 자신의 위치를 알고 있는 고정된 노드인 앵커노드와 위치추적의 대상인 모바일 노드로 구성된다. 첫 번째 토폴로지인 위치기반 토폴로지는 앵커노드의 위치로부터 측정된 모바일노드의 위치좌표를 이용해서 구축한다. 모바일노드의 위치좌표는 앵커노드와의 거리 값 정보를 토대로 minimum mean square error(MMSE)와 LSE 알고리즘을 활용하여 위치를 추정한다.
두 번째 토폴로지는 앵커노드를 제외하고 모바일 노드간의 측정된 거리 값을 가중치로 토폴로지를 구성한다. 두 번째 토폴로지는 위치정보를 알 수 없지만, 노드간의 거리 값만을 이용하기 때문에 NLOS환경으로 인한 위치오차의 문제점은 배제할 수 있다.
토폴로지 구축 후 각 모바일 노드는 두 토폴로지에서 각각의 연결과 가중치 값을 비교하여 토폴로지의 차이점을 찾아 위치오차가 있는 모바일노드를 찾고, 오차가 없는 모바일 노드들만을 이용해서 위치를 보정한다.
실제 실험에서 노드간의 거리를 측정하기 위해서 IEEE 802.15.4a에서 정의한 symmetric double sided two way ranging(SDS-TWR) [7] 기술을 이용하는 NanoPAN 5375 [8] 모트를 노드로 사용하여 수행되었다.
본 논문에서는 II장에서는 LOS와 NLOS환경에서 실제 측정되는 거리 값의 비교와 이 오차가 야기할 수 있는 문제점을 제시한 후, III장에서는 이를 해결하기 위한 알고리즘을 위치오차 탐지와 보정의 단계를 거쳐서 제안한다. 그리고 Ⅳ장에서는 실제 실험한 결과를 통하여 알고리즘의 성능을 확인하는 내용과 결론으로 구성된다.
Ⅱ. 문제점 제시
무선센서 네트워크에서의 위치인식을 위해서는 노드 간에 데이터 패킷을 전송하여 거리를 측정해야 한다. 하지만 RF 신호의 특성으로 NLOS환경에서 반사, 굴절, 회절, 산란 등의 현상으로 오차가 발생한다.
그림1 은 실내에서 벽과 가구가 거리측정 값에 미치는 영향을 나타내는 실험 결과로 60개의 RF 패킷을 SDS-TWR기술로 전송할 시 얻어지는 거리 값으로 구성되었다. 그림1에서의 결과는 NLOS환경의 경우는 LOS에 비하여 실제거리보다 멀게 인식이 되는 것을 보여준다. 이러한 결과는 그림2 와 같은 문제를 발생시킬 것이다.
PPT Slide
Lager Image
LOS, NLOS환경에서 SDS-TWR 기술을 이용한 거리 측정값 Fig. 1 Ranging distance measurement result by SDSTWR technique in LOS, NLOS environments
PPT Slide
Lager Image
장해물로 인한 위치 측정오차 예시 Fig. 2 The example of location error by obstacle
그림2 는 무선센서 네트워크에서 발생할 수 있는 위치 인식 오차의 사례를 나타는 것으로 노드(w, z, u)는 모바일 노드이고, 노드(1, 2, 3)은 자신의 위치를 알고있는 앵커노드이다.
모바일 노드 u가 3개의 앵커노드로부터 SDS-TWR 기술을 이용해서 거리를 측정하고 LSE 알고리즘을 이용해서 위치를 추정하는 과정에서, 앵커노드1과 모바일 노드u 사이의 장해물 때문에 u의 위치는 u`로 추정이 된다. 이러한 오차는 위치 인식의 정확성을 떨어뜨린다. 또한 위치적으로 z와 u`의 좌표가 가깝게 인식되기 때문에 MST 알고리즘으로 위치기반 토폴로지를 구축한다면, 그림3(a) 와 같은 이상적인 토폴로지가 아닌 그림 3(b) 와 같이 연결되어 위치기반 네트워크의 성능을 저하시킨다.
PPT Slide
Lager Image
위치측정 오차로 인한 토폴로지 오류의 예시 (a)위치오차가 없을 경우의 토폴로지 (b)위치오차가 있는 경우의 토폴로지 Fig. 3 The example of topology error by estimated location error (a)topology without location error (b)topology with location error
Ⅲ. 문제에 따른 해결방안 제시
실내 환경에서는 장해물에 의해서 NLOS환경이 발생하고, 이에 놓인 모바일 노드는 잘못된 위치 인식과 토폴로지 구축오류를 유발한다.
이러한 문제를 해결하기 위해서 새로운 알고리즘을 제안한다. 알고리즘은 위치 오차를 가지고 있는 모바일 노드를 찾는 단계를 거쳐 위치 오차를 보정하고 효율적인 토폴로지를 구축하는 것으로 구성된다.
- 3.1. 위치오차 감지
위치오차를 감지하는 과정에서는 두 개의 토폴로지를 구축하고 차이점을 갖는 모바일 노드를 찾는 것을 목표로 한다. 우선 모든 앵커노드는 자신의 위치정보를 방송한다. 신호를 받은 모바일 노드는 식별 가능한 거리에 있는 모든 노드들과 서로 패킷을 주고받아 SDS-TWR기술을 통해서 모든 이웃 노드와의 거리와 앵커노드의 위치 정보가 담긴 테이블을 만든다. 각각의 모바일 노드는 테이블의 정보와 MMSE 와 LSE를 근간으로 하는 위치추정 알고리즘을 이용해서 자신의 위치를 추정한다.
추정된 모바일 노드의 좌표를 ( x 0 , y 0 )라고 한다면 위치 추정 오차는 다음과 같은 식으로 나타낼 수 있다.
PPT Slide
Lager Image
xn yn 은 해당 모바일 노드의 이웃 중 n(1~N)번째 앵커노드의 좌표이고,
PPT Slide
Lager Image
은 모바일 노드와 n(1~N)번째 앵커노드와의 좌표 상으로 계산된 거리 값이다. 위치추정 오차인 식(1)을 최소로 하는 미지수 ( x 0 , y 0 )은 linear least square method(LLM)를 이용해서 계산한다. 선형화의 가정으로 ‘ en ( x 0 , y 0 ) = 0’으로 설정하고, 추정 오차를 최소로 한 후 식(1)을 정리하면 다음과 같이 식(2)로 정리 할 수 있다.
PPT Slide
Lager Image
식(2)는 이웃의 수만큼 만들 수 있으며, N번째 이웃의 거리 값과 n(1~N-1)번째 거리 값의 식을 연립하면 다음의 식(3)을 얻을 수 있다.
PPT Slide
Lager Image
연립식인 식(3)은 총 N-1개를 만들 수 있기 때문에 총 이웃의 수인 N이 3이상이라면 ( x 0 , y 0 )의 좌표 값을 얻을 수 있다. 위의 계산과정을 N-1의 행을 갖는 행렬로 연산을 표현하면 식(4)와 같이 정리하여 사용 할 수 있다.
PPT Slide
Lager Image
이렇게 모바일 노드가 자신이 저장한 테이블의 정보로 자신의 위치를 추정한다면, 모든 노드들이 자신의 위치 좌표를 알기 때문에 좌표 상으로 계산된 거리가중치를 갖는 MST 토폴로지 [9] 를 구축할 수 있다.
MST 토폴로지의 구축은 Prim’ 알고리즘 [10] 을 따라서 그림4 와 같은 과정으로 토폴로지를 구축한다.
PPT Slide
Lager Image
Prim’s알고리즘에 따른 MST 토폴로지 Fig. 4 MST topology with Prim’s algorithm
위치 좌료를 이용해서 위치기반인 첫 번째 토폴로지를 구축 후, 모바일 노드는 모바일 노드 상호간의 거리만을 이용해서 두 번째 토폴로지를 구축한다. SDSTWR기술을 이용한 거리측정 결과를 가중치로 하여 MST 토폴로지를 구축하면, 모바일 노드들은 자신들의 위치 정보는 갖지 못하고 노드간의 거리 값과 자신과 연결된 노드의 정보만을 갖게 된다.
첫 번째로 구축한 토폴로지는 그림5(a) 에서 나타내고 있다. 그림5(a) 에서 모바일 노드 a는 위치오차로 인해서 실제로 가장 가까운 모바일 노드인 b가 아닌 d와 연결되어있는 문제가 발생한다. 두 번째로 구축한 토폴로지는 그림5(b) 에서 나타내고 있다. 그림5(b) 에서 각각의 모바일 노드는 자신들의 위치정보를 갖지 못한 상태이지만, 서로간의 거리 값만을 이용하기 때문에 NLOS환경으로 인한 위치오차의 영향을 받지 않는 것을 확인 할 수 있다.
PPT Slide
Lager Image
토폴로지 구축 예 (a)앵커노드로부터 추정된 위치로 구축 한 위치기반 토폴로지 (b)모바일노드 상호간의 거리만을 이용하 여 구축한 토폴로지 Fig. 5 Topology construction example (a)Geographical topology based on the location which is estimated by anchor node location (b)Topology based on the mutual distance from mobile node.
두 가지 토폴로지가 구축되면, 각각의 모바일 노드는 두 토폴로지에서 자신과 연결이 되는 대상노드가 동일한가를 비교하고, 그 연결의 거리 값은 유사한지 파악을 한다. 이 때 연결되는 대상노드가 다르거나, 대상노드와의 거리 차이가 임계값(Δ Th )을 넘어서면, 해당 모바일 노드는 위치오차를 가질 가능성이 있다고 판단한다. 임계값(Δ Th )은 LOS환경에서 측정되는 거리 값의 표준편차(σ d )값에 3배를 한 3σ d 로 설정하여, LOS환경을 NLOS환경으로 판단할 가능성을 1% 미만으로 한다.
위치오차를 가질 가능성이 제기된 모바일 노드들은 다음 단계인 위치 보정의 단계를 거쳐서 위치를 보정하게 된다.
- 3.2. 위치오차 보정
위치오차 감지 단계를 거치면, 모든 모바일 노드는 자신이 위치오차를 가질 가능성이 있는 노드인지 아닌지를 확인 할 수 있다. 만약 모바일 노드가 위치오차를 가질 가능성이 있는 노드라면, 자신의 위치오차 가능성을 방송한다.
패킷 정보를 수신한 모든 노드는 자신의 이웃노드를 Vn(위치오차 가능성이 없는 노드집합)과 Vm(위치오차 가능성이 있는 노드집합)로 구분을 짓는다. 만약 모바일 노드가 위치오차 가능성을 가지고, Vn에 속하는 노드가 3개 이상이라면, 해당 모바일 노드는 Vn의 노드정보를 이용해서 자신의 위치를 보정할 수 있고 식(5)와 같이 정의 할 수 있다.
PPT Slide
Lager Image
PPT Slide
Lager Image
,
PPT Slide
Lager Image
는 보정되는 모바일 노드 a의 좌표이고,
PPT Slide
Lager Image
( a, i )는 모바일 노드 a와 i 간에서 SDS-TWR기술로 측정된 거리 값이며 i = b,c,d ..로 Vn집합에 포함되는 이웃 모바일 노드이다.
만일 t시간 구간에서 Vn 집합의 원소의 수가 3개 미만이라면, 해당 모바일 노드의 보정은 수행할 수 없다. 하지만, 모바일 노드의 위치 보정은 동시에 각 노드마다 수행하기 때문에 시간 구간이 t+1이 되었을 시에는, Vn 집합의 원소의 수가 증가할 것이다. 따라서 모바일 노드 a의 시간 구간 t에서 위치오차를 식으로 표현한다면, 식(6)와 같이 나타낼 수 있다. 이를 토대로 시간이 지나면서 보정과정이 반복된다면, 식(6)의 위치오차 값은 식(7)로 표현할 수 있다.
PPT Slide
Lager Image
PPT Slide
Lager Image
위 식은 각 모바일 노드의 위치오차 값은 점점 작아진다는 것을 보여 주고 있다.
위의 그림5 의 토폴로지로 예를 든다면, 모바일 노드 (a, b, d)는 위치오차의 가능성을 갖게 되고, 자신의 이웃을 Vn과 Vm집합으로 구분을 짓는다. 모바일 노드 a는 Vn집합인 {c, e, f}를 이용해서 자신의 위치를 보정할 수 있다.
Ⅳ. 실험결과
제안된 알고리즘의 성능을 확인하기 위해서, NLOS 환경이 존재하는 실내 환경에서 실험을 하여 성능을 검증하였다. 실험을 수행하기 위해서 Nanotron에서 제공하는 NanoPAN5375 [8] 모트를 노드로써 사용하여 SDS-TWR기술로 거리를 측정하였고, 결과확인을 위해서는 모트로 데이터를 수집하여 결과를 그림6 으로 출력하였다.
PPT Slide
Lager Image
실험결과 (a)앵커노드로부터 추정된 위치로 구축한 위치 기반 토폴로지 (b)모바일노드 상호간의 거리만을 이용하여 구축한 토폴로지 (c)보정된 위치좌표로 구축한 위치기반 토폴로지 Fig. 6 Experiment results (a)Geographical topology based on the location which is estimated by anchor node location (b)Topology based on the mutual distance from mobile node. (c)Geographical topology based on the location which is adjusted by proposed algorithm
실험환경은 10m X 10m의 환경에 4개의 앵커노드와 7개의 모바일 노드를 배치하였다. 모바일 노드 중 3,6번의 2개의 노드에 NLOS환경에 따른 거리 측정오차를 삽입하였고, LSE 알고리즘과 다변측량법으로 위치를 추정하였다.
실험결과인 그림6 에서 (a) 는 첫 번째로 구축되는 토폴로지로 모바일 노드 3, 6번에서 NLOS환경이 적용되어 위치오차가 생기는 것과 위치기반으로 구축된 토폴로지가 비효율적이라는 것을 보여주고 있다. 그림6(b) 는 두 번째로 구축되는 토폴로지로 모바일 노드간의 거리 값만 인지하기 때문에 위치정보는 수정이 안 된 상태이다. 따라서 이웃 모바일 노드와의 거리만을 이용할 뿐 위치정보를 이용하지 않는 토폴로지이기 때문에 위치오차가 없을 경우에 구축될 토폴로지를 나타내고 있다.
그림6(a) , (b) 의 결과를 이용해서 토폴로지의 차이를 비교하면 위치 오차를 가질 가능성을 갖는 모바일 노드를 찾는다. 따라서 모바일 노드(2, 3), (6, 5), (7, 5), (3, 6)의 연결에서 차이점을 찾을 수 있고, 중복적으로 나타나는 3, 5, 6노드를 위치 오차를 가질 가능성이 있는 노드로 판단한다. 이제 각 모바일 노드는 자신의 이웃을 Vn과 Vm의 두 집합으로 구분을 하게 되는데, 3, 5, 6번 노드는 Vm집합에 포함되게 된다.
시간 구간 t에서는 1, 2, 4, 7번의 모바일 노드의 정보만으로 각각 자신의 위치정보를 보정하고, t+1시간 구간에서는 위치오차가 감지된 모바일 노드인 3, 5, 6번 노드가 Vn 집합의 원소로 인식된다. t+1구간에서 Vm 집합이 공집합이 되므로, 반복 보정은 중단되고, 최종적으로 보정된 추정위치를 이용해서 그림6(c) 와 같은 결과를 확인 할 수 있다. 그림6(c) 의 결과는 그림6(a) 와 같은 가장 근거리에 있는 모바일 노드와 연결이 되는 토폴로지를 구축하고 있으며, 동시에 정확한 위치정보까지 알 수 있음을 확인하였고, 그 성능을 표1 로 정리하였다.
실험결과Table. 1experiments results
PPT Slide
Lager Image
실험결과 Table. 1 experiments results
표2 는 제안된 알고리즘의 성능을 확인하기 위해서 동일한 실험 환경을 기준으로 기존의 다른 위치추정 알고리즘을 적용하여 성능을 비교한 결과이다. 기존의 알고리즘은 모바일 노드의 위치추정에 주안점을 두기 때문에 모바일 노드의 위치오차 평균값만을 비교하였다.
비교 실험결과Table. 2comparative experiments results
PPT Slide
Lager Image
비교 실험결과 Table. 2 comparative experiments results
표2 에서 비교하고 있는 알고리즘은 순서대로 linear least square(LLS), non linear least squares(NLS), minmax 그리고 w2 가중치를 이용한 extended min-max [11] 이다. LLS의 경우 구현이 가장 간단한 방법으로 제안된 알고리즘에서 초기위치를 구현할 때 이용된 알고리즘이다. LOS환경에 대해서는 NLS알고리즘이 가장 정확한 위치를 추정 할 수 있지만 위 실험환경과 같은 NLOS환경에서는 가장 부정확한 결과를 보인다. 또한 min-max와 extended min-max 결과에서도 알 수 있듯이 LOS환경에서 정확한 위치를 추정 할 수 있는 알고리즘 일수록 NLOS환경으로 받는 영향은 크다는 것을 알 수 있다.
Ⅴ. 결 론
본 논문은 실내 환경에서 효율적인 토폴로지를 구축함과 동시에 정확한 위치추정을 제공하는 알고리즘을 제안하였다. 기존에 존재하는 위치추정 알고리즘의 경우 LOS환경에 대하여 정확한 위치추정을 가능하게 하지만, NLOS의 경우에는 많은 오차 가능성을 가지고 있다. 그래서 위치인식 없이 노드간의 가중치만으로 토폴로지를 구축하여 기존 위치추정 알고리즘인 LSE알고리즘의 결과와 비교하고, 반복 보정하는 과정을 거쳐 NLOS환경에서의 위치 인식을 정확히 하였다.
Acknowledgements
본 연구는 2012년도 정부(교육과학기술부)의 재원으로 한국연구재단의 기초연구사업(2012R1A1A 2012007529) 지원에 의하여 이루어진 연구로서, 관계부처에 감사드립니다.
BIO
유진호(Jin-Ho You)
2013년 건국대학교 전자공학부 학사
2014년~현재 건국대학교 일반대학원 전자정보통신 공학 석사 수료 중
※관심분야 : Wireless Network and Mobile Computing, localization
권영구(Young-Goo Kwon)
1993년 고려대학교 전자공학부 학사
1996년 고려대학교 전자공학부 석사
2002년 Department of Electrical and Computer Engineering, University of Florida 공학박사
2002~2003년 삼성 R&D 센터 senior member
2004년~현재 건국대학교 전자공학부 부교수
※관심분야 : USN, Wireless Network and Mobile Computing, Powerline Communication and Networking, localization
References
Wang F. , liu J. 2011 “Networked Wireless Sensor Data Collection: Issue, Challenges, and Approaches,” IEEE communications Surveys & Tutorials 13 (4) 673 - 687    DOI : 10.1109/SURV.2011.060710.00066
Mao G. , Fidan B. , Anderson B.D.O. 2007 “Wireless sensor network localization techniques,” Comput. Netw. 51 (10) 2529 - 2553    DOI : 10.1016/j.comnet.2006.11.018
Seada K. , Helmy A. , Govindan R. 2004 “On the effect of localization errors on geographic face routing in sensor networks,” Proc. IPSN Berkely, USA 71 - 80
Huang Yung-Fa , jheng You-Ting 2010 “Performance of MMSE based Localization with Wireless Sensor Networks” NCM,2010 Sixth International Conference on 671 - 675
Savvides A , Park HM , Strivastava MB 2002 “The n-Hop multilateration primitive for node localization problems.” Proceedings of 1st ACM International Workshop on Wireless Sensor Networks and Applications 112 - 121
Boukerche A. , Oliveria H.A.B.F. , Nakamura E.F. , Loureiro A.A. 2007 “Localization systems for wireless sensor networks,” IEEE wireless Communication Special Issue on Wireless Sensor Networks 14 6 - 12
Lee Jian Xing , Lin Zhiwei , Chin Francois , Chin Po Shin 2007 “Symmetric double side two way ranging with Technology” Conference 1980 - 1983
“NanoPAN 5375 Development KIT,” User Guide NA-10-0250-0 009-1.1 Nanotron Technologies GmbH Berlin, Germany
Mooij A.j , Wesselink W. 2003 “A Formal Analysis of a Dynamic Distributed Spanning Tree Algorithm”, Computer Science Report 03-16 Technische Universiteit Eindhoven Eindhoven
http://en.wikipedia.org/wiki/Prim's_algorithm
Robles J.J , Pola J.S , Lehnert R. 2012 “Extended Min-Max Algorithm for Position Estimation in Sensor Networks” Positioning Navigation and Communication (WPNC), 2012 9th workshop 47 - 52