선박의 WLAN 환경에서 K-최근접 이웃 알고리즘 기반 Fingerprinting 방식을 적용한 위치 추정 방법

Location Estimation Method Employing Fingerprinting Scheme based on K-Nearest Neighbor Algorithm under WLAN Environment of Ship

  • cc icon
  • ABSTRACT

    GPS 신호가 도달하지 않는 실내 환경에서 위치를 추정하는 연구는 지금까지 많이 이루어져 왔다. 또한 추정 기법도 여러 가지 기법들이 제안되었다. 본 논문에서는 다층 구조의 선박에서 위치를 추정하는 문제를 심도있게 고찰하였고 K-최근접 이웃 알고리즘 기반 Fingerprint 기법에 의한 위치 추정 방법에 대해 알아보았다. Fingerprint 기법을 쓰기 위해 39개의 RP에서 각각 N=100회의 수신신호를 측정함으로써 신뢰성 있는 DB를 구축하였고 이를 토대로 임의의 위치에 있는 단말기의 위치를 추정하는 모의실험을 하였다. 모의실험을 통해 Fingerprint 기법에 의한 위치 추정 성능은 아주 우수함을 알 수 있었다.


    Many studies have been made on location estimation under indoor environments which GPS signals do not reach, and, as a result, a variety of estimation methods have been proposed. In this paper, we deeply consider a problem of location estimation in a ship with a multi-story structure, and investigate a location estimation method using the fingerprint scheme based on the K-Nearest Neighbor algorithm. A reliable DB is constructed by measuring 100 received signals at each of 39 RPs in order to employ the fingerprint scheme, and, based on the DB, a simulation to estimate the location of a randomly-positioned terminal is performed. The simulation result confirms that the performance of location estimation by the fingerprint scheme is quite satisfactory.

  • KEYWORD

    GPS 신호 , 선박의 실내 환경 , K-최근접 이웃 알고리즘 , Fingerprint 기법 , 위치 추정 방법

  • Ⅰ. 서 론

    그림 1과 같이 GPS 신호가 도달하지 않는 선박의 실내 환경에서 단말기의 위치를 추정하는 문제를 생각해 보자. 첫째는 실내 네트워크 환경을 어떤 통신방식으로 구성해야 할 것인가와 그에 따른 장비의 간소화는 어떠한가를 생각해 보야 한다. 둘째는 위치 추정의 정확도는 어느정도 수준인가를 생각해 보아야 한다. 셋째는 선박의 환경에서 위치 추정은 평면상의 추정문제인가 아니면 공간상의 추정문제인가를 생각해 보아야 한다.

    첫째의 관점에서 보면 선박의 실내 환경에서는 IEEE 802. 11의 표준인 WLAN으로 네트워크를 구성하는 것이 좋다는 것을 알 수 있다. 그 이유는 WLAN은 AP(Access Point)와 NIC 카드만으로 네트워크를 구성할 수 있다는 장점이 있기 때문이다[1-4]. 둘째의 관점에서 보면 실내 측위의 방법은 AOA(Angle of Arrival), TOA(Time of Arrival), RSS(Received Signal Strength), TDOA(Time Difference of Arrival), Fingerprint 방식이 있는데 선박환경에서 가장 효과적인 방법이 무엇인가를 선택해야 한다는 것이다[5-8]. 선박의 실내 환경은 도심지 건물의 실내 환경에 비해 상대적으로 환경정보의 변화가 적다고 할 수 있다.

    이러한 이유 때문에 주변정보의 DB화에 의해 단말의 위치를 추정하는 Fingerprint 방식을 선택하는 것이 타당성이 있다고 할 수 있다. 셋째의 관점에서는 선박은 여러개의 층으로 구성되어 있고 각 층은 두꺼운 철판으로 막혀있는 공간이 상대적으로 많다는 특성을 갖고 있기 때문에 이러한 다층 구조의 환경에서 단말기의 위치 추정은 매우 어려운 문제로 생각할 수 있다는 것이다. 이를 정확하게 보면 각 층마다 평면상의 추정이 아닌 공간상의 3차원 추정 문제로 접근해야 한다는 것이다. 그러나 공간상의 추정문제는 상대적으로 많은 계산량을 필요로 하기 때문에 평면상의 추정문제로 접근하는 것이 현실적으로 타당성이 있다고 할 수 있다. 이는 선박내에서 단말기의 위치에 대한 의미가 정확히 어느 지점에 있는가가 아니라 어느 공간에 있는가가 중요하기 때문이다. 따라서, 본 논문에서 Fingerprint 방법을 쓴 평면상의 위치를 추정하는 문제를 다룬다.

    Ⅱ. 관련기술

    위치를 추정하는 일반적인 방법은 GPS(Global Positioning System)를 이용하는 방법이다. GPS는 3개 이상의 위성을 이용하여 삼각측량법에 의해 추정하는 방법이다. 그런데 GPS 신호가 도달하지 않는 환경에서는 무선신호를 이용하여 위치를 추정한다. 도심지의 실내 환경이거나 밀폐된 환경에서 이루어지는 위치추정 방법으로는 AOA(Angle of Arrival), TOA(Time of Arrival), TDOA(Time Difference of Arrival), RSS (Received Signal Strength), Fingerprint 방식이 있다. AOA 기법은 두 개 이상의 AP를 써서 단말기로부터 들어오는 신호의 방향, 즉, θ1, θ2,⋯,θn를 추정하여 위치를 찾는 방법이고. TOA 기법은 AP를 중심으로 반지름 r1,r2,⋯,rn을 갖는 원을 그려 모든 원들이 교차하는 지점을 추정하는 방법이다. 또한, TDOA 기법은 AP와 단말기 간의 신호의 전달 시간차인 t1,t2,⋯,tn를 구해 위치를 찾는 방법이며, RSS 기법은 신호의 세기를 이용하여 거리를 추정하는 방법이다. 마지막으로 Fingerprint 기법은 위치를 추정하고자 하는 구역을 격자 모양의 셀로 나누어 각 교차점에 RP를 배치하여 사전에 수신신호의 정보를 DB로 만들어 놓고, 임의의 위치에서 오는 신호에 대한 정보와 비교하여 가장 가까운 RP를 위치로 결정하는 방법이다.

    일반적으로 선박의 환경은 육지의 실내 환경에 비해 위치를 추정하기 위한 별도의 무선 장비를 설치하는 것이 어렵다고 볼 수 있다. 육지의 환경은 여러 가지 네트워크 구성이 상대적으로 잘 되어 있는 반면, 선박의 환경은 네트워크의 구성이 비교적 열악하다. 따라서, 선박내 환경에서는 WLAN를 이용한 Fingerprint 기법을 적용하여 위치를 추정하는 방법이 다른 방법에 비해 현실적으로 더 적합하다고 할 수 있다[9-18].

    Ⅲ. K-최근접 이웃 알고리즘 기반 Fingerprint 방법을 적용한 위치 추정 방법

    그림 1과 같은 선박의 실내 환경에서 2개 이상의 AP를 써서 Fingerprint 방식에 의해 단말의 위치를 추정하는 문제를 생각해 보자. 먼저 고찰해야 하는 점은 하나의 AP를 써서 직선상의 거리를 추정하는 것이 가능하다는 것을 생각해 보아야 한다. AP로부터 r만큼 떨어진 지점에서 수신신호의 세기 P(r)은 (1)과 같다.

    image

    여기서, P(r0)는 기준거리에서 이전에 측정된 신호세기이며 n은 경로손실 지수이고 mAP와 단말사이에 존재하는 벽 감쇄 계수를 나타낸 것이다. 경로 손실지수는 AP와 단말 사이의 장애물의 종류에 따라 다르며, LOS( Line of Sight)인 경우 n = 2이며 장애물이 있는 경우 2에서 4사이의 값을 갖는다.

    식(1)의 의미는 거리를 추정하기 전에 기준거리에서 신호의 세기에 대한 사전 정보가 있다면 이를 토대로 AP로부터 r만큼 떨어진 지점에서의 수신신호를 측정하여 거리 r를 구할 수 있다는 것이다. 이는 직선을 x축상에 놓으면 rx가 되기 때문에 AP가 원점에 있다고 가정하면 x의 거리를 추정하는 문제로 생각할 수 있다. 이제 직선상의 추정 문제를 평면상의 추정문제로 확대해 보자. 이는 임의의 (x,y)지점에서 두 개의 AP로부터 거리를 변수 r′과 r″ 으로 표기하면 (2)와 (3)을 얻을 수 있다. 직관적으로 (2)와 (3)에 의해 (x,y)의 추정값 를 구할 수 있다는 것으로 알 수 있다.

    image
    image

    더 구체적으로 두 개 이상의 AP를 써서 AP로부터 단말로 전파되어 오는 신호의 세기를 측정하여 위치를 추정하는 방법을 알아보자. Fingerprint 추정은 두단계로 이루어지는데 첫 번째 단계는 Database Correlation을 구축하는 과정이고 두 번째 단계는 임의의 위치에 있는 단말의 위치를 추정하는 Estimation 과정이다. 먼저 Database Correlation 과정을 보자. 선박에서 위치를 추정하고자 하는 공간을 n × m 격자 모양으로 그리고 모든 교차점에 RP(1,1),RP(1,2), ⋯,RP(n,m)을 둔다. 그런 다음 각 RP에서 N회 만큼 L개의 AP, 즉, AP1, AP2,⋯,APL로부터 오는 신호의 세기를 측정한다. 마지막으로 각 RP에서 측정된 값을 평균하여 이를 DB화 한다. 그러면 DB화된 값은 (4)와 같다. 여기서 는 APj에서 들어오는 신호를 N번 측정한 값의 평균값으로 가 된다.

    image

    이제 Database Correlation 과정에서 구축된 DB를 토대로 하여 임의의 위치에 있는 단말의 위치를 추정하는 문제를 그림 2를 보면서 생각해 보자. 이는 단말이 있는 위치에서 L개의 AP, 즉, AP1, AP2, ⋯, APL로부터 오는 신호의 세기를 측정하여 측정된 값인 (SNR1, SNR2, ⋯, SNRL)로부터 추정값 를 구하는 문제가 된다.

    이를 단순히 생각하면 측정된 값 (SNR1, SNR2, ⋯, SNRL)를 DB에 있는 각 RP의 값과 비교하여 Distance가 가장 작은 것을 택해 그 RP의 위치를 단말의 위치로 결정하는 것으로 생각할 수 있다. 그러나 이러한 방법은 단말의 위치 P(x,y)가 격자점에 있지 않기 때문에 근본적으로 추정에러를 내포하고 있다는 문제점이 있다.

    그러면 이러한 문제를 해결하기 위한 방법은 무엇일까를 생각해보자. 하나의 해결방법으로 K-최근접 이웃 알고리즘을 쓰는 것을 생각할 수 있다. K-최근접 이웃 알고리즘은 최근접하는 K개의 이웃을 이용한다는 의미를 뜻한다. 이 방법은 학습 데이터 집합에 있는 표본들 간의 유사도에 따라 라벨이 붙여져 있지 않는 표본들을 분류하는 매우 직관적인 방법이라고 할 수 있다. 즉, 라벨이 없는 표본 xuRDD가 주어질 경우, 학습 데이터 집합에서 K개의 가장 가까운 라벨이 있는 표본을 찾아내고 K개의 부분 집합 내에 가장 빈도가 많이 나타나는 클래스에 xu를 할당하는 방법이다. K-최근접 이웃 알고리즘은 단지 상수 K, 라벨이 있는 학습 데이터 집합의 표본, 거리 척도 만이 필요하다.

    위치 추정이라는 측면에서 K-최근접 이웃 알고리즘을 보면 단말의 위치 P(x,y)에서 측정된 값 (SNR1, SNR2, ⋯, SNRL)과 DB에 있는 n × m 개수의 값을 비교해 보았을 때 유사도가 근접하는 의 수는 몇 개인가를 결정하는 것이다. 여기서, Distance를 유클리드로 쓸 때 유사도는 (5)와 같이 된다.

    image

    여기서, DiP(x,y)에서 측정된 값 (SNR1, SNR2, ⋯, SNRL)과 DB에 저장된 RP(1,1), RP(1,2), ⋯, RP(n,m)i째 값 과의 유사도이고, sjP(r)에서 APj로부터 들어오는 신호의 측정값이며 는 DB의 iRP에서 APjSNR의 평균값이다.

    식 (5)에 의해 계산된 유사도 값 중에서 가장 가까운 K개 값을 결정할 수 있기 때문에 (6)을 이용하여 단말의 위치에 대한 추정값 를 구할 수 있다.

    image

    즉, 단말이 있는 위치에서 측정된 신호세기의 값과 가장 가까운 K개의 RP를 결정하여, x방향으로 평균값과 y방향으로의 평균값을 구해 와 를 구한다.

    Ⅳ. 모의실험

    선박의 실내 환경에서 Fingerprint 기법을 적용하여 위치를 추정하는 문제를 모의실험을 통해 검증하였다. 선박의 실내 환경과 유사하게 가로 25m × 세로 4m인 공간을 만들고 1m간격으로 39개의 RP를 배치하고 두개의 AP가 설치되어 있는 장소에서 단말로 Samsung 노트북 R530을 써서 실험을 하였다.

      >  [ SNR DB 구축 ]

    WLAN 환경에서 AP1과 AP2로부터 각 RP로 들어오는 신호의 세기를 Netstumbler를 써서 1초 단위로 100회를 측정하였다. 각 RP에서 측정된 값으로부터 와 를 구하여 표 1과 같이 DB화 하였다.

      >  [ Example ]

    그림 3의 Test Point 위치인 (7.5, 0.7)에 단말이 있을때, 그 지점에서 AP1과 AP2로부터 들어오는 신호의 세기를 측정하여 측정된 값으로부터 단말의 위치를 추정하는 모의실험을 하였다.

    단말이 있는 지점에서 신호의 SNR를 측정하였는데 SNR1 = 5이고, SNR2 = 3 나타난다. AP1로부터 수신된 신호와 DB의 각 RP에 구축되어 있는 값과의 차이인 과 AP2로부터 수신된 신호와 DB의 각 RP에 구축되어 있는 값과의 차이인 를 구하여 각 RP에서 Distance 를 구하였는데 표1에서 그 결과를 보여주고 있다. 그런 후 K-최근접 이웃 알고리즘을 적용하기 위해 K값을 구하였다. 그림 4에서 보면 알 수 있듯이 K = 10일 때 Mean Error 값이 최소가 되기 때문에 K를 10으로 결정하였다.

    표 1에서 Distance Di가 작은 순으로 10개의 RP를 선택하였고 와 를 구하였다. 즉, K=10일 때의 선택된 RP의 좌표값은 (x,y) = {(0,0), (4,2), (6,0), (6,2), (8,1), (8,2), (10,0), (11,1), (11,2) (12,1)}이 되기 때문에 x방향의 추정값은 =7.6이고, y방향의 추정값은 =0.8됨을 알 수 있었다.

    Ⅴ. 결 론

    본 논문에서는 GPS 신호가 도달하지 않는 선박의 실내 환경에서 위치를 추정하는 문제를 고찰하였다. 추정 방법으로는 K-최근접 이웃 알고리즘 기반 Fingerprint 기법에 의한 위치 추정 방법을 적용하였다. Fingerprint 기법을 쓰기 위해 가로 25m × 세로 4m인 공간을 만들고 1m간격으로 39개의 RP를 배치하고 두 개의 AP가 설치되어 있는 장소에서 단말로 Samsung 노트북 R530을 써서 실험을 하였다. 39개의 RP에서 각각 N=100회의 수신신호를 측정함으로써 신뢰성 있는 DB를 구축하였고 이를 토대로 (7.5, 0.7)위치에 단말기가 있을 때 위치를 추정하는 모의실험을 하였다. 모의실험 결과 x방향의 추정값은 =7.6이었고, y방향의 추정값은 =0.8이었다.

    모의실험을 통해 알 수 있는 사실은 선박의 환경에서는 정확한 위치보다는 어느 공간에 단말을 갖고 있는 선원이 있는가를 아는 것이 중요하기 때문에, 이런 관점에서 보았을 때 추정 성능은 대체적으로 우수함을 알 수 있었고, 비교적 적은 무선 장비를 사용하는 Fingerprint 기법을 적용하여 위치를 추정하는 것에 대한 타당성을 검증할 수 있었다.

  • 1. Lee Jang-Jae, Kwon Jang-Woo, Jung Min-A, Lee Seong-Ro 2010 “Fingerprinting Bayesian Algorithm for Indoor Location Determination,” [The Journal of Korea Information and Communications Society] Vol.35 P.888-894 google
  • 2. Lee Jang-Jae, Jung Min-A, Lee Seong-Ro, Song Iick-Ho 2011 “KNN/ANN Hybrid Location Determination Algorithm for Indoor Location Base Service,” [The Journal of Institute Of Electronics And Information Engineers] Vol.48 P.109-115 google
  • 3. Lee Jang-Jae, Song Lick-Ho, Kim Jong-Hwa, Lee Seong-Ro 2011 “Optimized KNN/IFCM Algorithm for Efficient Indoor Location,” [The Journal of Institute Of Electronics And Information Engineers] Vol.48 P.125-133 google
  • 4. Lee Jang-Jae, Jung Min-A, Lee Seong-Ro 2010 “KNN/PFCM Hybrid Algorithm for Indoor Location Determination in WLAN,” [The Journal of Institute Of Electronics And Information Engineers] Vol.47 P.146-153 google
  • 5. Jo Hyeong-Gon, Jeong Seol-Young, Kang Soon-Ju 2012 “Enhanced Accurate Indoor Localization System Using RSSI Fingerprint Overlapping Method in Sensor Network,” [The Journal of Korea Information and Communications Society] Vol.37C P.731-740 google doi
  • 6. Kim Taehoon, Tak Sungwoo 2013 “Modeling and Performance Evaluation of AP Deployment Schemes for Indoor Location-Awareness,” [Journal of the Korea Institute of Information and Communication Engineering] Vol.17 P.847-856 google doi
  • 7. Cha Jae-Young, Kong Young-Bae, Choi Jeung-Won, Ko Jong-Hwan, Kwon Young-Goo 2012 "IEEE 802.15.4a based Localization Algorithm for Location Accuracy Enhancement in the NLOS Environment," [Journal of the Korea Institute of Information and Communication Engineering] Vol.16 P.1789-1798 google doi
  • 8. Son Sanghyun, Choi Hoon, Cho Hyuntae, Baek Yunju 2013 "Location Information Reliability-Based Precision Locating System Using NLOS Condition Estimation," [The Journal of Korea Information and Communications Society] Vol.38C P.97-108 google doi
  • 9. Amundson I., Sallai J., Koutsoukos X., Ledeczi A., Maroti M. 2011 “RF angle of arrival-based node localisation,” [Int. J. Sensor Networks] Vol.9 P.209-224 google
  • 10. Ravindra S, Jagadeesha S N 2013 “TIME OF ARRIVAL BASED LOCALIZATION IN WIRELESS SENSOR NETWORKS: A LINEAR APPROACH,” [Signal & Image Processing : An International Journal (SIPIJ)] Vol.4 P.13-30 google
  • 11. Cong L., Weihua Zhuang 2001 “Non-line-of-sight error mitigation in TDOA mobile location,” [IEEE Global Telecommunications Conference] Vol.1 P.680-684 google
  • 12. Kamol K., Prashant K. “Properties of Indoor Received Signal Strength for WLAN Location Fingerprinting,” [IEEE First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (Mobi Quitous’04)] google
  • 13. Lim Yujin, Park Jaesung, Ahn Sanghyun 2008 “A Geometric Approach for the Indoor Localization System,” [The Journal of Institute Of Electronics And Information Engineers] Vol.45TC P.1058-1065 google
  • 14. Ahn Daye, Ha Rhan 2014 “Indoor Localization Methodology Based on Smart Phone in Home Environment,”'14-04 [The Journal of Korea Information and Communications Society] Vol.39C P.315-325 google doi
  • 15. Woo Sung-Hyun, Jeon Hyun-Sik, Park Hyun-Ju 2006 “A Study on NLOS Error Solution Method in Indoor Location Estimate,” [Korea Computer Conference] Vol.33 P.178-180 google
  • 16. Chan Solomon, Sohn Gunho May 16-17, 2012 “INDOOR LOCALIZATION USING WI-FI BASED FINGERPRINTING AND TRILATERATION TECHIQUES FOR LBS APPLICATIONS,” [International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences] Vol.XXXVIII-4/C26 google
  • 17. Jun MA, Xuansong LI, Xianping TAO, Jian LU 23-26 June 2008 “Cluster Filtered KNN:A WLAN-Based Indoor Positioning Scheme,” [WOWMOM '08 Proceedings of the 2008 International Symposium on a World of Wireless, Mobile and Multimedia Networks] google
  • 18. Papadopoulos S., Bakiras S., Papadias D. September 13,2010 “Nearest Neighbor Search with Strong Location Privacy,” [The 36th International Conference on Very Large Data Bases] P.619-629 google
  • [그림 1.] 선박내 구조 및 위치 추정에 대한 개념도
    선박내 구조 및 위치 추정에 대한 개념도
  • [] 
  • [] 
  • [] 
  • [] 
  • [그림 2.] Fingerprint 기법에 의한 위치 추정
    Fingerprint 기법에 의한 위치 추정
  • [] 
  • [] 
  • [표 1.] AP1과 AP2에 대한 각 RP에서의 수신 SNR의 평균값과 거리값
    AP1과 AP2에 대한 각 RP에서의 수신 SNR의 평균값과 거리값
  • [그림 3.] Fingerprint 기법에 의한 위치 추정 [Test Point 위치 (x,y) = (7.5,0.7)]
    Fingerprint 기법에 의한 위치 추정 [Test Point 위치 (x,y) = (7.5,0.7)]
  • [그림 4.] K에 따른 Mean Error (K = 10일 때 최소값)
    K에 따른 Mean Error (K = 10일 때 최소값)