Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1975-6291(Print)
ISSN : 2287-3961(Online)
Journal of Korea Robotics Society Vol.12 No.3 pp.350-355
DOI : https://doi.org/10.7746/jkros.2017.12.3.350

Single Outlier Removal Technology for TWR based High Precision Localization

Chang-Eun Lee1
, Tae-Kyung Sung†
1Intelligent and Robot Control Research Laboratory, ETRI
()
Corresponding author: Information and Communication Engineering, Chungnam University (tksaint@cnu.ac.kr)
20170417 20170531 20170703

Abstract

UWB (Ultra Wide Band) refers to a system with a bandwidth of over 500 MHz or a bandwidth of 20% of the center frequency. It is robust against channel fading and has a wide signal bandwidth. Using the IR-UWB based ranging system, it is possible to obtain decimeter-level ranging accuracy. Furthermore, IR-UWB system enables acquisition over glass or cement with high resolution. In recent years, IR-UWB-based ranging chipsets have become cheap and popular, and it has become possible to implement positioning systems of several tens of centimeters. The system can be configured as one-way ranging (OWR) positioning system for fast ranging and TWR (two-way ranging) positioning system for cheap and robust ranging. On the other hand, the ranging based positioning system has a limitation on the number of terminals for localization because it takes time to perform a communication procedure to perform ranging. To overcome this problem, code multiplexing and channel multiplexing are performed. However, errors occur in measurement due to interference between channels and code, multipath, and so on. The measurement filtering is used to reduce the measurement error, but more fundamentally, techniques for removing these measurements should be studied. First, the TWR based positioning was analyzed from a stochastic point of view and the effects of outlier measurements were summarized. The positioning algorithm for analytically identifying and removing single outlier is summarized and extended to three dimensions. Through the simulation, we have verified the algorithm to detect and remove single outliers.


TWR 기반 고정밀 측위를 위한 단일 이상측정치 제거 기술

이 창 은1
, 성 태 경†

초록


    1.서 론

    초광대역 무선 시스템(UWB : Ultra Wide Band) 은 500MHz이상의 대역폭을 사용한 무선통신 혹은 비대역 폭(중심 주파수에 대응하는 대역폭) 이 20% 이상인 시스 템을 말하며, 채널 페이딩에 강인하며 신호의 대역폭이 넓어 다중경로에 강하다[1]. 특히, 이러한 UWB 신호를 이용하여 거리를 추정하는 표준은 크게 CSS (Chirp Spread Spectrum) 및 IR (Impulse Radio) UWB 기술로 나뉜다[2]. IR-UWB 기반 ranging 시스템은 데시미터급 정확도를 획득할 수 있으며, 유리, 플라스틱 등을 투과하 고도 고정밀 측정치를 획득할 수 있다는 장점이 있다[3]. 또한 IR-UWB 기반 ranging 칩셋이 저가화·대중화되면 서 수십 센티미터급의 측위 시스템 구현이 가능한 실정 이다[4]. TWR (Two-way ranging) 기반 측위 시스템[5]은 무선 통신 신호의 RTT (Round Trip Time)를 이용하여 두 개의 노드 간 거리를 측정하는 방식으로써 무선통신 망의 시각 동기화가 필요 없어서 군집 협업 측위 방식[6] 에 적합한 기법이며 양방향 무선통신과 거리 측정이 동 시에 가능한다. 이러한 TWR 기반 측위 시에 획득되는 측정치는 노드와 노드 간 거리 측정치가 장애물 등의 요인으로 인하여 실제 측정치보다 길게 추정되는 문제[7] 가 있으며, 이를 이상측정치(Outlier)라고 한다. 이러한 이상측정치의 경우, TWR 기반 측위 오차의 원인[8]이 되며, 일반 잡음과는 달리 신호 처리 기법을 통하여 오차 가 경감되지 않으므로, 이러한 이상측정치로 인한 오차 를 근본적으로 줄이기 위해서는 이상측정치를 검출 및 제거하여 협업 측위를 수행하여야 한다.

    본 논문에서는 우선, 2차원 TWR 기반 협업 측위를 확률적인 관점에서 분석하고 이러한 특징을 이용하여 이상측정치를 해석적으로 제거하기 위한 확률적인 이상 측정치 검출 및 제거 알고리즘에 대하여 제안한다. 마지 막으로 제안된 방법이 최종 측위 오차에 대한 성능 향상 을 제공함을 시뮬레이션을 통해 검증 한다.

    2.확률적TWR 해석

    2.1.TWR 측위의 확률적 접근

    본 절에서는 TWR 측정치 식을 기반으로 TWR 측정 치의 확률적인 해석을 수행하였다. 우선, 두 단말간의 TWR 측정치는 다음과 같은 식으로 나타낼 수 있다.(1)

    r 12 = ( x 2 -x 1 ) 2 + ( y 2 -y 1 ) 2 + w 12
    (1)

    여기에서 r12 는 1번과 2번 단말의 TWR 측정치, (x1, y1) 은 1번 단말의 위치, (x2, y2) 는 2번 단말의 위치 를 나타내며 w12 는 측정치 잡음을 나타낸다. 이러한 측 정치의 의미를 확률분포로 표현하면 다음과 같다.(2)

    p w 12 = A 12 exp ( ( ( x 2 -x 1 ) 2 + ( y 2 -y 1 ) 2 r 12 ) 2 2 σ 2 )
    (2)

    여기에서 A12 는 정규화 상수이다. 상기 수식을 하나의 태그에서 i번째 앵커에 대한 식으로 나타내면 다음과 같다.(3)

    p w i j = A i j  exp ( ( ( x j x i ) 2 + ( y j y i ) 2 r i j ) 2 2 σ 2 )
    (3)

    측정치의 개수가 증가하는 경우, 태그의 위치 분포 함 수는 다음과 같이 확률분포함수의 곱으로 나타낼 수 있다.(4)

    p t a g = i p w i
    (4)

    우선, 측정치가 하나일 경우 확률분포함수는 1번 앵커 에서 1번 측정치만큼 떨어져 있는 띠와 같은 형태로 나 타낼 수 있으며, 측정치가 두 개일 경우 확률분포함수는 두 개의 포인트를 가지게 되며, 이는 두 원의 교점이 된 다. 측정치가 늘어나면서 이 두 개의 포인트는 하나로 결정된다.

    Fig. 1은 태그가 임의의 4개의 앵커로부터 거리 측정 치를 획득한다고 가정하였을 때, 측정치의 개수별로 태 그 위치의 확률분포함수를 구한 것이다.

    2.2.TWR 측위의 확률적 검출 기법

    전술한 확률적 해석 기법을 이용하면 TWR 측정치 기 반의 측위가 가능하다. 한편, 확률적 검출 기법을 통해 이상측정치의 영향에 대하여 검증할 수 있다. 이상측정 치의 경우 실제 거리에 비하여 길이가 길거나 짧게 측정 되는 측정치를 말하며, 이러한 측정치에 해당하는 확률 함수를 곱하게 되면 실제 위치에서의 확률분포함수의 값 이 작아지며 또한 확률밀도함수의 값이 작아지게 된다.

    이는 Aij 를 통하여 확인이 가능하다. 매 측정치가 곱해 지면 정규화 상수 Aij 는 다시 계산이 가능하며, 측정치가 추가될 경우 확률밀도함수는 실제 위치 근방에 모이거 나 일정한 수준을 유지하여야 한다. 그러나 이상측정치 가 곱해지게 되면 실제위치에서의 확률밀도함수가 감소 하는 경향이 있으며, Aij 는 작아진다.

    Fig. 2에서는 임의의 8개의 앵커 배치 하에서 5번째 측정치에 측정치 표준편차의 정수배만큼의 변화를 준 후 확률적으로 측위를 수행한 것이다.

    한편, 이러한 이상측정치를 포함하는 측위를 수행할 경우 회복이 가능한 경우와 회복 불가능한 경우가 존재 한다. 이상측정치의 양이 측정치의 분산에 비하여 크지 않으면 Aij 는 감소하였다가 추가적인 측정치 획득 후에 증가가 가능하나, 이상측정치의 양이 큰 경우에는 Aij 는 감소한 이유 회복되지 않는다.

    TWR 이상측정치의 확률적 검출 기법은 다음과 같다. 측정치를 하나씩 추가하면서 얻은 정규화 상수의 변화 를 통하여 이상측정치를 검출한다. 이 때, 측정치를 추가 하는 순서에 변화를 줄 수 있으며 측위 결과에 영향을 주지 않기 위해서는 처음 두 측정치에 포함된 이상측정 치 성분은 소량이어야 하며, 반대로 이상측정치 성분이 큰 경우 검출이 용이하다.

    3.해석적 이상측정치 제거 알고리즘

    3.1.TWR 기반 단일 이상측정치 제거 알고리즘

    전 절에서의 확률적 검출 기법은 수학적인 모델로, 실 제 측위 시스템에 적용하여 사용하기가 불편하다. 이러 한 문제를 해결하기 위하여, 본 절에서는 TWR 이상측정 치의 해석적 제거 기법에 대하여 제안한다.

    이상측정치란 오차요인에 의하여 둘 사이의 측정치의 거리가 증가하여 측정된 것으로 가정한다. 측정치가 실 제 길이보다 길게 측정되면 측위 시에 수정 불가능한 문제가 있다. 전술한 바와 같이, 이러한 이상측정치의 양이 크면 측위 결과에 영향을 주며, 특히 반복법으로 측위를 수행할 경우 측위 결과가 발산하는 문제가 있으 므로, 이를 사전에 탐지하고 제거하는 기술 개발이 필요 하다. 이상측정치를 포함하는 측정식은 다음과 같이 다 시 작성할 수 있다.(5)

    r i j = ( x j x i ) 2 + ( y j y i ) 2 + o i j + w i j
    (5)

    여기서 oij 는 i번째 단말과 j번째 단말 간 측정치와 실 제 거리를 차분한 양으로, 모델링 오차에 해당한다. IR-UWB 신호는 콘크리트 벽을 투과하나 이러한 콘크리 트 매질 내에서의 전파 전파속도는 공기중과 다르며, 이 러한 오차를 사전 정보 없이 파악하여 보정하는 것은 MIMO (Multi input multi output) 시스템을 이용하여 채 널을 추정 및 보상하여야 하며, SISO (Single input single output) 시스템으로는 불가능하다. 한편, MIMO 시스템 은 배열 안테나를 탑재하여야 하므로 실제 운용에 어려 움이 있다.

    획득한 N개의 측정치에 포함된 하나의 이상측정치를 제거하는 방법은 다음과 같다. N개의 측정치 중 측정치 일부를 이용하여 측위를 수행하였을 때 측위 결과는 이 상측정치를 포함하는 경우와 포함하지 않는 경우로 나 누어지며 이러한 경우의 수는 다음과 같은 통계적 특성 을 가진다.

    5개의 측정치를 획득하였을 때 5개의 측정치를 모두 이용하여 측위하는 조합의 수는 1가지(5C5)이며 이 때 이상측정치를 포함하지 않는 조합의 수는 없다. 5개의 측정치 중 4개의 측정치를 선택하여 측위하는 조합의 수는 5가지(5C4)이며 이 중 이상측정치를 포함하지 않 는 조합의 수는 1가지(4C4)이다. 마지막으로 5개의 측정 치 중 3개의 측정치를 선택하여 측위를 수행하는 경우 선택 가능한 조합은 10가지(5C3)이며 이 경우 중에 이상 측정치를 포함하지 않는 조합은 4가지(4C3)이다. Table 1은 이상측정치를 포함하지 않는 경우의 수와 이상측정 치를 포함하는 경우의 수를 측정치의 수, 측위하는 조합 의 수에 따라 정리한 결과이다.

    Table 1의 마지막 Column에서의 같이 측정치가 6개가 획득되었고 이중 하나의 이상측정치가 존재한다고 가정 하였을 때, 6개의 측정치를 선택하는 경우, 5개의 측정치 를 선택하는 경우, 4개의 측정치를 선택하는 경우, 그리 고 3개의 측정치를 선택하는 경우에 대하여 가능한 측위 결과를 Fig. 3에 도시하였다. 빨간색은 이상측정치를 포 함하는 조합의 측위 결과이고, 파란색은 이상측정치를 포함하지 않는 측위 결과를 나타낸다.

    3.2.시뮬레이션

    본 절에서는 단일 이상측정치 제거 측위 기법에 대한 성능평가를 수행하였다. 5개의 측정치 및 6개의 측정치 가 획득된 경우에 있어서 3개의 측정치를 선택하는 조합 의 통계적 분포를 이용하여 이상측정치 여부를 결정하 였다. 이상측정치 크기에 따른 이상 측정치 검출 확률을 비교해 보기 위해서 측정치의 잡음은 0.1 m를 가정하였 으며, 측정치 잡음에 2배, 3배, 5배에 해당하는 거리오차 를 포함하고 있는 이상측정치를 생성하여 시뮬레이션을 수행하였다. 각 시뮬레이션은 10,000회 반복하여 이를 Table 2에 정리하였다. 이때 같은 측정치 수를 선택하여 조합하는 경우, 조합의 대상이 되는 획득된 측정치의 수 가 많을수록 이상측정치 검출에 유리하며, 또한 이러한 이상측정치 양이 클수록 이상측정치 검출이 용이함을 시뮬레이션 결과를 통해 확인하였다.

    측정치 중의 조합 가능한 모든 경우의 수로 가설을 만들어 측위를 수행하여 이상측정치를 판단할 경우 Table 1 및 Table 2 결과로부터 다음을 알 수 있다. Table 1에서와 같이 N개의 측정치를 획득하여 N개의 측정치 중 조합 가능한 일정부분의 측정치만을 이용하여 측위 를 수행하였을 때 이 때의 측위 결과는 이상측정치를 포함하는 경우와 포함하지 않는 경우로 나누어진다. 이 때 Table 2로부터 같은 측정치 선택 수를 적용할 경우 측정치의 수가 많은 경우(6개)가 이상 측정치 검출 확률 (100%)이 높으며 또한 이상측정치 성분이 클 경우(5σ) 이상 측정치 검출 확률(100%)이 높음을 확인 할 수 있다. 따라서 이상측정치 검출 및 제거하는 알고리즘의 경우, 선택가능한 조합수를 늘릴수록 이상측정치 클러스터링 에 유리하며 또한 측정치의 수가 많고(6개) 이상측정치 의 크기가 클수록 이상 측정치 검출 확률이 높다는 것을 알 수 있다.

    4.결 론

    TWR 기반 측위 시에 획득되는 측정치는 노드와 노드 간 거리 측정치가 장애물 등의 요인으로 인하여 실제 측정치보다 길게 추정되는 문제가 있으며, 이를 이상측 정치(Outlier)라고 한다. 이러한 이상측정치의 경우, TWR 기반 측위 오차의 원인이 되며, 일반 잡음과는 달리 신호 처리 기법을 통하여 오차가 경감되지 않으므로, 이러한 이상측정치로 인한 오차를 근본적으로 줄이기 위해서는 이상측정치를 검출 및 제거해야 한다. 따라서 본 논문에 서는 TWR 기반 고정밀 측위를 위한 이상측정치 제거 기술을 제시하였다. TWR 기반 협업 측위를 확률적인 관점에서 분석하고 이러한 특징을 이용하여 이상측정치 를 해석적으로 제거하기 위한 새로운 방법인 확률적인 이상측정치 검출 및 제거 알고리즘에 대하여 제안하였으 며 마지막으로 제안된 방법이 최종 측위 오차에 대한 성 능 향상을 제공함을 시뮬레이션을 통해 확인하였다. 향후 다중 이상측정치가 포함되었을 경우에 대한 해석적 이상 측정치 제거 및 경감 기술, 그리고 MIMO 기반 고정밀 측정 기술 등에 대한 연구가 필요하다.

    Figure

    JKROS-12-350_F1.gif
    The operational change on probability distribution according to increasing the number of TWR-based measurements
    JKROS-12-350_F2.gif
    The operational change on a normalization constant according to increasing the magnitude of outlier
    JKROS-12-350_F3.gif
    The comparison about outlier (RED) and normal (BLUE) distribution according to the number of possible combination (number of measurements = 6)

    Table

    Ranging configuration for measurements
    Detection probability of outlier according to the number of measurements and the magnitude of outlier error

    Reference

    1. Sahinoglu Z. , Gezici S. , Guvenc I. (2008) Ultra-wideband positioning systems,
    2. Bensky A. (2008) Wireless positioning technologies and applications,
    3. Ye T. , Walsh M. , Haigh P. , Barton J. , Mathewson A. , O’Flynn B. (2011) Experimental impulse radio IEEE 802.15.4a UWB based wireless sensor localization technology: characterization, reliability and ranging,
    4. Wang J. , Khalid Raja A. , Pang Z. (2015) Prototyping and experimental comparison of IR-UWB based high precision localization technologies,
    5. Park J. , Lim J. , Lee K. , Sung T. (2013) A two-way ranging WPAN location system with clock offset estimation , Journal of Institute of Control, Robotics and Systems, Vol.19 (2) ; pp.125-130
    6. Kurazume R. , Hirose S. , Nagata S. , Sashida N. (1996) Study on cooperative positioning system (basic principle and measurement experiment , Proc. of IEEE International Conference on Robotics and Automation, Vol.vol. 2 ; pp.1421-1426
    7. McElroy C. , Neirynck D. , McLaughlin M. Comparison of wireless clock synchronization algorithms for indoor location systems,
    8. Lee C-E. , Im H-J. , Lim J-M. , Cho Y-J. , Sung T-K. (2015) Seamless routing and cooperative localization of multiple mobile robots for search and rescue application , ETRI J, Vol.37 (2) ; pp.262-272

    저자소개

    • 이 창 은 (Chang-Eun Lee)
    • 1996 한양대학교 전자공학과 졸업
    • 1998 동 대학원 전자공학과 석사졸업
    • 2014~현재 충남대학교 정보통신공학과 박사 과정
    • 2001년~현재 한국전자통신연구원 책임연구원
    • 관심분야: 인공지능, 분산 및 협업 로봇 제어, WPAN 기반 로봇 위치 측위

    • 성 태 경 (Tae-Kyung Sung)
    • 1984 서울대학교 제어계측공학과 졸업
    • 1986 동 대학원 제어계측공학과 석사졸업
    • 1992 동 대학원 제어계측공학과 졸업(박사)
    • 1997~현재 충남대학교 정보통신공학과 교수
    • 관심분야: GPS/ GNSS, 지상파 측위, UWB WPAN 측위, 위치인지 신 호처리
    오늘하루 팝업창 안보기 닫기