Indoor localization algorithm based on WLAN using modified database and selective operation

1. 서 론

최근 실내 WLAN(Wireless LAN)의 보급은 실외뿐만 아니라 실내에서도 통신의 음영지역을 최소화하는데 기여하고 있다. 이와 더불어 송수신 노드를 이용해서 위치를 인식하던 기존의 실내 위치인식 방식보다 고정노드의 설치에 따른 추가 비용이 없는 WLAN을 이용한 Fingerprint 기법이 많은 관심을 받고 있다[1]-[3]. 기존에 많이 연구되어 온 고정노드를 이용한 TOF(Time of flight)방식의 위치측정은 NLOS(Non line of sight)환경에서 발생하는 전파의 굴절 및 반사에 취약하여 위치 오차가 크게 발생하는 단점이 있다[4]-[6]. 하지만 WLAN을 이용한 방식의 경우 신호세기의 측정을 통한 데이터베이스 기반의 위치인식 방식이므로 공간적 구조 및 AP(Access point)의 변화가 없다면 전파의 굴절 및 반사에 의한 위치측정 오차가 발생하지 않는다. 하지만 현재 신뢰도 높은 위치 인식률을 획득하기 위한 신호의 최소 구분 거리가 3m로서 기술적인 한계에 의한 오차가 발생한다. Kim et al. [7]은 WLAN 기반 AP들의 주변 환경정보를 이용하여 AP와 이동 객체간의 거리를 산출하여 위치를 추정함으로써 Training 단계에서의 시간적 소모를 크게 해소하였지만 위치의 정확도와 정밀도는 개선이 필요하다. Jo et al. [8]은 BLIDx 프로토콜 개선을 위해 변형된 Fingerprint 중첩 방법을 제안하였다. 이 방법은 BLIDx에 특화된 시스템을 구축하기 때문에 다른 시스템에 적용하는데 변형이 필요하며 지도 생성 단계에서 오차 발생 시 인식 결과가 흔들리는 단점이 있다. Teuber et al. [9]는 비행 격납고에서 유클리드 거리법과 퍼지이론을 Fingerprint에 접목하여 실내 위치인식오차 범위를 3m로 줄였다. 하지만 일반적인 환경이 아닌 특수한 실내에서의 적용에 따른 좁은 실내지역, 복층구조 등의 신호변화에 따른 추가적인 연구가 필요하다.

본 논문에서는 실내위치인식 방법 중 하나인 Fingerprint 기법을 이용하여 위치에 따른 신호수집을 위한 데이터베이스 구성 시 데이터 수집 시간을 줄이고 데이터의 미수신 구간과 실시간 신호의 불규칙 측정에 의한 신호의 수집의 효율성을 해결하기 위하여 선형 보간과 문턱치를 이용하고 연산량 감소를 위한 선택적 연산을 제안한다. 제안한 알고리즘은 신호의 수집 단계에서 신호의 세기에 따라 수집한 데이터를 변형하여 데이터베이스의 크기를 줄이는 기법과 측정 구간에 따라 AP 신호가 가지는 세기를 이용하여 필요한 AP신호만 연산하는 선택적 연산을 이용하여 연산량을 줄였다.

2. 위치추정 관련 이론

2.2 Basic Fingerprint algorithm

Figure 1 과 같이 WLAN을 이용하여 위치를 인식하기 위해서는 각 위치에 따른 AP의 신호를 수집하여 데이터베이스를 구성하는 Training 단계와 이를 통해 구성된 데이터베이스와 실제 수신기에서 측정되는 신호 세기의 값을 비교하여 위치를 추정하는 Positioning 단계로 나누어진다[11].

Training 단계에서 WLAN 신호는 측정하는 수신기의 내재적 오차와 환경적인 요인에 의해 변동하기 때문에 보통 3m 간격으로 각 위치에서 측정 가능한 모든 AP를 수집한다. 하지만 기기의 수신 상태나 위치에 따른 신호 세기 등에 의해서 수신율이 매우 낮은 AP가 존재하므로 이러한 방법은 시간적 소모가 많다. 위치가 i 인 지점에서의 수집된 모든 AP 신호를 P 라고 할 때 위치에 따른 수집된 신호 Pⁱ는 아래 식 (3)과 같다.

이러한 배열을 통하여 측정하고자 하는 공간의 크기에 따라 데이터베이스를 구성한다.

Positioning 단계에서 측정하고자 하는 위치에서 실시간 측정되는 AP가 아래 식 (4)와 같을 경우,

Training 단계에서 구축한 데이터베이스와 현 위치에서 실시간로 측정된 AP를 아래 식 (5)를 통해 비교한다.

실시간으로 측정되는 P_r의 AP의 수와 신호세기는 수신 상태에 따라 계속 변동한다. 모든 데이터베이스 구간의 연산을 통해 신호의 세기가 가장 근접한 위치 즉 식 (6)을 통해 독립적인 Dist(i)의 값 중 가장 작은 위치인 P_S를 현재의 위치로 추정한다.

Figure 1

The block Diagram for conventional Fingerprint

3. 제안한 Fingerprint 알고리즘

3.1 데이터베이스 및 선택적 연산 알고리즘

제안한 Fingerprint 알고리즘의 블록다이어그램은 아래 Figure 2와 같다. 먼저 위치를 인식하고자 하는 공간에서 일정한 간격으로 각 위치의 AP 신호를 측정하여 이 신호를 기반으로 모든 구간의 데이터베이스를 만든다. 하지만 신호 수집 시 신호의 세기 및 측정 기기의 감도 등 여러 환경적인 요인에 의해 모든 신호를 수신하는데 많은 시간이 필요하다. 이를 해결하기 위해 신호 측정의 횟수를 줄이고 이를 통해 수집된 데이터로 데이터베이스 구성 시 신호의 세기와 거리에 따른 특성에 의해 선형 보간을 사용하여 측정되지 못한 신호 구간의 신호 값을 추가한다. 보간 과정에서 실시간 위치 인식을 통해 신호 측정이 어렵고 오차가 큰 –90 dbm 이상의 신호는 제거하여 데이터베이스의 크기 및 연산량을 줄일 수 있는 장점이 있다. 제안한 변형된 데이터베이스 방식을 이용하여 Positioning 단계에서 위치인식을 시작한다. 기본적인 Fingerprint기법은 매번 측정된 신호와 모든 데이터베이스의 수집 구간을 비교하기 때문에 연산량이 많다. 이러한 많은 연산량을 줄이기 위해 본 논문에서 제안한 방법은 최초 인식 시 식 (5)를 이용하여 5회 연산을 수행하여 위치 추정의 오류를 최소화하고 이후부터는 신호의 세기를 이용한 선택적 연산을 수행함으로써 정확한 위치 측정과 연산량을 줄일 수 있다. 선택적 연산은 실시간 위치인식 시 측정되는 신호를 이용하여 신호의 세기가 가장 강한 5개의 AP만을 이용하여 지속적인 연산을 통해 최종적인 위치를 추적한다.

Figure 2

Block diagram for proposed algorithm

3.2 신호수신 특성 및 데이터베이스 구성

신호의 측정 및 실험은 한국해양대학교 공과 대학 건물의 3층 NLOS을 포함하는 45m 구간 복도에서 AP의 추가적인 설치 없이 기존의 AP를 이용하여 실시하였다. 신호의 수집은 3m 단위로 수집하였으며 데이터베이스는 MySQL을 이용하여 제작하였으며 mobile 기기는 안드로이드 운영체제의 휴대폰을 이용하여 신호를 수집 및 위치 측정을 실시하였다. 초당 2회의 신호 측정을 통해 데이터베이스 구축 및 위치인식을 진행하였으며 휴대폰으로 측정된 신호는 블루투스 통신을 이용하여 PC로 측정데이터를 전송하여 수신된 데이터에 제안한 알고리즘을 적용하였다.

고가의 정밀 수신 장비에 비해 휴대가 가능한 mobile기기는 신호의 수신율 및 신호 수신 특성이 다르기 때문에 휴대성을 위해서는 mobile기기에 대한 분석이 필요하다.

Figure 3

The Data reception rate according to the number of measurements

Figure 3는 데이터베이스 구성을 위한 데이터 수집 횟수를 나타낸다. 한 위치에서 수신될 수 있는 모든 데이터 수집을 위해 많은 시간이 소비됨을 확인할 수 있다. Figure 4은 매회 신호 측정 시 신호의 세기에 따른 측정률을 나타낸다. 실험환경에서 측정된 모든 AP 신호는 –50~-90 dbm 사이의 신호세기를 보였으며 신호가 약한 –80~-90 dbm신호의 수신이 어렵다는 것을 확인할 수 있다. 이러한 신호의 수신율은 데이터베이스의 구성에 있어서 시간소비가 늘어나는 가장 큰 원인이다. 이러한 시간 소모를 줄이기 위하여 Training 단계의 데이터베이스를 구성할 경우 신호의 세기가 강한 AP는 10회 이내의 측정 시 대부분 수집되기 때문에 신호가 약해 측정이 어려운 AP는 문턱치를 통해 –85 dbm이상의 신호만 수집함으로써 수집을 용이하게 하고 향후 위치 인식 연산량을 줄였다. 이렇게 수집된 데이터는 보간이 필요한 미수집 구간도 존재하며 RSSI의 변화는 AP와의 거리에 따라 비례해서 선형적인 증가와 감소를 보이므로 AP의 위치에 따른 신호의 선형 보간법을 적용하였다. Figure 5과 같이 대부분의 신호는 수집된 구간이 AP와 가장 가까운 지점을 중심으로 선형적인 증가와 감소를 보이게 된다. 신호의 수집이 어려운 지점은 대부분 평균 –80 dbm 이하로 신호가 매우 약한 부분이다. -90 dbm 대역의 신호는 신뢰성이 매우 떨어지며 수신 확률도 매우 낮다. 따라서 실험적인 결과에 의해 연산을 줄이고 데이터베이스 구성량을 줄이기 위하여 아래 식 (7)과 같이 신뢰도 높은 신호의 데이터만 수집한다.

Figure 4

The Data reception rate according to the RSSI

Figure 5

The change of RSSI according to the distance

Figure 6

The measured screen on mobile and PC

4. 알고리즘 실험 및 고찰

4.1 제안한 Fingerprint 알고리즘 적용 실험

본 논문에서 제안한 Fingerprint 기법의 성능 확인을 위한 실험은 좁은 복도구간의 특성상 일차원적인 데이터베이스 수집 및 위치 측정을 통하여 실시하였다. 데이터 수집 과정 및 실시간 위치 측정 과정에서 신호를 측정하고 수집하는 휴대폰의 위치는 0.65m의 높이로 이동하며 측정하였다. Figure 6은 C#을 이용하여 제작한 위치측정 프로그램이다. mobile에서 측정된 신호는 Bluetooth를 이용하여 PC로 전송되어 초당 2회의 위치를 표시하도록 구성하였으며 이동하며 각 신호를 수집한 위치에서의 결과 비교를 하였다. Figure 7는 측정 위치에 따른 데이터베이스 구성 시 보간을 이용한 기본적인 Fingerprint방식의 위치인식과 보간을 이용하지 않은 위치인식의 정확성을 실험 비교한 결과를 나타낸다. 이 실험을 통해 선형보간을 이용함으로써 전체적인 인식성능이 향상됨을 확인할 수 있다. 중요한 데이터의 보간은 최소값을 찾는 알고리즘에 영향을 많이 주기 때문에 특정 구간의 데이터에 정확성을 떨어뜨리는 요인이 될 수도 있지만 제안한 방식의 경우 신뢰성이 높은 신호들만 이용하여 연산을 수행하기 때문에 신호의 정확도는 평균 17.8% 향상되었음을 확인하였다. Figure 8은 제안한 알고리즘을 적용한 후 측정한 위치 정확도를 나타낸 것으로서 이를 통해 제안한 방식의 최종 실험 결과는 정확도의 차이는 거의 없고 연산량은 크게 감소하였다는 결과를 얻을 수 있다.

Figure 9은 데이터베이스 구성단계와 위치인식단계에서의 연산량을 기본 Fingerprint기법과 비교한 그래프이다. Training 단계에서의 연산량은 평균 20% 감소하였으며 제안한 Positioning 알고리즘까지 적용한 후 측정된 결과는 평균 46% 감소를 보였다.

Figure 7

Performance comparison of localization

Figure 8

Performance comparison of localization

Figure 9

Experiment of the computational comparison

4. 결 론

본 연구에서는 실내위치인식의 방법 중 하나인 WLAN기반의 Fingerprint 기법의 데이터 구성시간 및 연산량을 줄이는 알고리즘을 제안하였다. 본 논문에서 제안한 방식으로 실험 한 결과 데이터베이스 수집량을 줄이면서 제안한 기법을 통해 정확도를 평균 17.8% 향상시켰으며 이를 바탕으로 실시간 다중위치인식을 위한 선택적 연산 기법을 제안하였다. 기존의 모든 데이터 비교는 신호의 정확도에 크게 영향을 미치지 않는 수신이 어려운 AP까지 모두 연산을 해야 하기 때문에 정확성에 큰 영향을 주지 않는 신호들도 모두 비교하여 위치를 추정하였다. 본 논문에서 제안한 알고리즘을 통하여 수학적 연산량은 46% 감소시켰으며 정확성은 거의 동일한 결과를 보였다. 향후 WLAN을 많이 이용하는 대형 여객선이나 화물선에서의 위치인식을 연구할 계획이며 본 논문에서 제안한 방법을 이용하여 기존의 선내에서 적용이 어려운 TOF방식의 전파 반사 및 굴절의 문제 및 수밀문 등의 변화에 따른 위치인식 문제를 해결하여 향후 선내에서의 설치 비용 절감 및 정확도 향상이 기대된다.

Acknowledgments

“본 과제(결과물)는 국토해양부의 지원으로 수행한 해양에너지 전문인력 양성사업 및 정부(교육과학기술부)의 재원으로 한국연구재단의 지원을 받아 수행된 연구임(No. 20110029766).”

References

• J.-Y. Choi, “Wireless sensor node location management by regression analysis of RSSI”, M.S. Dissertation, School of Electronics & Information Engineering, Kunsan National University, Korea,, (2009), (in Korean).
• W.-Y. Hwang, “Implementation of indoor positioning system using fingerprint for WLAN environment”, M.S. Dissertation, Department of Computer, Information and Telecommunication Engineering, Kangwon National University, Korea, (2008), (in Korean).
• M. Ocana, L. M. Bergasa, M. A. Sotelo, J. Nuevo, and R. Flores, “Indoor robot localization system using WiFi signal measure and minimizing calibration effort”, IEEE ISIE, 20, p1545-1550, (2005). [https://doi.org/10.1109/ISIE.2005.1529162]
• J.-H. Seong, T.-W. Lim, J.-S. Kim, S.-G. Park, and D.-H. Seo, “An improvement algorithm for localization using adjacent node and distance variation analysis techniques in a ship”, Journal of the Korean Society of Marine Engineering, 37(2), p213-219, (2013), (in Korean). [https://doi.org/10.5916/jkosme.2013.37.2.213]
• H.-J. Cho, K.-I. Hwang, D.-S. Noh, and D.-H. Seo, “Real time indoor positioning system using IEEE 802.15.4a and sensors”, Journal of the Korean Society of Marine Engineering, 36(6), p850-856, (2012), (in Korean). [https://doi.org/10.5916/jkosme.2012.36.6.850]
• B.-G. Paik, S.-R. Cho, B.-J. Park, Lee, B.-D. Bae, and J.-H. Yun, “Characteristics of wireless sensor network for full-scale ship application”, Journal of marine science and technology, 14(1), p115-126, (2009). [https://doi.org/10.1007/s00773-008-0038-x]
• M.-K. Kim, Y.-S. Shin, and H.-J. Park, “WLAN-based indoor positioning algorithm using the environment information surround access points”, Journal of the Korean Institute of Maritime Information and Communication Sciences, 15(3), p551-560, (2011), (in Korean). [https://doi.org/10.6109/jkiice.2011.15.3.551]
• H.-G. Jo, S.-Y. Jeong, and S.-J. Kang, “Enhanced accurate indoor localization system using RSSI fingerprint overlapping method in sensor network”, The Journal of Korea Information and Communications Society, 37(8), p731-740, (2012), (in Korean). [https://doi.org/10.7840/kics.2012.37C.8.731]
• Andreas Teuber and Bernd Eissfeller, “WLAN indoor positioning based on Euclidean distances and fuzzy logic”, Proceedings of the 3rd Workshop on Positioning, Navigation and Communication, p159-168, (2006).
• J.-W. Lee, J.-J. Ryu, W.-S. Lee, D.-K. Han, and H.-C. Choi, “Implement of Zigbee Indoor location aware system by RSSI between anchors”, Information and Control Symposium, p43-44, (2008).
• S.-S. Shin, G.-B. Kim, and H.-Y. Bea, “Fingerprint building method using Splite-tree based on Indoor Environment”, Journal of The Korea Society of Computer and Information, 17(6), p173-182, (2012), (in Korean). [https://doi.org/10.9708/jksci.2012.17.6.173]