The recent explosive proliferation of wireless devices and Wireless Local Area Networks (WLANs) is accelerating the demand for practical pervasive applications in indoor environments, such as indoor navigation, context-dependent content delivery and asset/people monitoring. In such applications, the identification of a user’s location in an indoor space is critical because the Global Positioning System (GPS) is usually unavailable due to signal blocking. Instead, WLAN infrastructure allows a wireless device to be localized by means of WLAN location fingerprinting in an indoor environment. As a result, WLAN-based fingerprinting has become a prevalent approach to indoor localization.
Its widespread adoption, however, has been hindered by the need for the calibration of a localization system. The calibration step usually involves a laborious and time-consuming manual effort to collect training data comprising wireless signal measurements and their location labels. Furthermore, it must be conducted for every new building and repeated whenever the training data become outdated due to changes in the WLAN environment. Therefore, a great attention is paid to the issue of reducing calibration effort in this research field.
In efforts to reduce such calibration effort, several studies have been carried out on semi-supervised learning techniques that utilize both labeled and unlabeled training data. These attempts reduce the need for location labels, thus reducing the cost of calibration. Another research stream focuses on crowdsourcing ap-proach in which general users can participate in the data collection activity. Along with explicit contribution ap-proaches, implicit crowdsourcing methods, which infer collected locations by using additional sensing data from GPS or inertial sensors embedded in wireless devices, have been developed. Although these methods can reduce the manual efforts of participants to some extent, the engagement of additional sensors raises a new set of issues, such as power consumption, availability, device heterogeneity, and accuracy of the sensors. In fact, the needs for manual labeling and deliberate handling of additional sensors are impeding the widespread adoption of indoor localization.
In this dissertation, in order to obviate the need for location labels or other location-related information, a novel unsupervised learning method is proposed that can calibrate a localization model using only unlabeled signal measurements. Aforementioned learning-based techniques (i.e., semi-supervised learnings) have difficul-ties in overcoming their local-optima problems, and projecting a learned model onto an indoor map without some amount of labeled data. In contrast, the proposed method solves these problems by an efficient hybrid optimization strategy incorporating a Hidden Markov Model (HMM) training algorithm into a hybrid global-local optimization scheme of Memetic Algorithm (MA). During the optimization process, the proposed method utilizes the constraints imposed by indoor layouts as well as the physics of radio propagation. The utilization of the constraints dramatically reduces the solution space of the optimization, and consequently can make a localization model to be built without requiring any labeled data.
Unlike previous strategies proposed to reduce calibration effort, the proposed unsupervised learning method does not require any prior knowledge of the WLAN environment, the engagement of additional sensors, or explicit efforts to collect labeled samples from the building of interest. The technique only assumes that par-ticipants turn on their WLAN modules to contribute unlabeled signal measurements while they walk around in a building carrying their wireless devices. Usually, this condition is not considered as a part of calibration effort because online measurements are the essential elements required in the localization phase of WLAN-based localizations. Because of this advantage, the proposed method can reduce the cost of a localization model cali-bration to almost zero.
The contributions of this dissertation to indoor localization and mobile computing are as follows: 1) the dissertation is the first study to apply unsupervised learning of signals for indoor localization, which obviates the need for location labels or other location-related information in localization model calibration; 2) the proposed method generates a training data set that can be used later in conjunction with any WLAN-based fingerprinting technique; 3) the dissertation introduces several automation techniques, each of which can be used in other studies of reducing calibration effort for their enhancements; 4) and it proposes a general framework for the unsupervised learning of RSSI measurements, in which more advanced techniques can easily replace the each steps.
최근 무선 단말기의 사용자가 폭발적으로 증가하고 무선 근거리 통신망 (WLAN)이 널리 설치 됨에 에 따라 무선 단말기를 활용한 실내 위치기반 응용의 개발 요구 또한 증가하고 있다. 이러한 실내 위치기반 응용을 가능하게 하기 위해서는 실내 측위 기술이 필수적이다. 일반적인 실외 환경에서는 GPS를 활용하여 위치 판정이 가능하지만, 실내 환경에서는 신호 수신율이 떨어지므로 측위에 활용되기는 힘들다. 따라서 적외선, RFID, WLAN등을 활용한 여러 대안 기술들이 제안되어 왔다. 그 중 특히 WLAN을 기반으로 하는 실내 측위 기술은 이미 널리 설치되어 있는 WLAN 인프라와 무선 단말기를 그대로 활용할 수 있어 최근 큰 주목을 받고 있다. 또한 WLAN 기반 기술 중, 핑거프린트 (fingerprinting) 기반 기법이 높은 정확도를 제공할 수 있는 장점이 있어 가장 널리 연구되고 있다. 그러나 핑거프린트 기반 기법은 측위 시스템을 위한 핑거프린트 데이터베이스, 혹은 측위 모델을 미리 구축해야 한다는 단점을 지닌다. 측위 모델 구축을 위해서는 각 건물의 모든 위치에서 수작업으로 무선 신호 데이터를 수집해야 하며, 또한 수집된 데이터에 위치 표시 라벨을 부여 해야 하기 때문에 많은 노동력 소요된다. 이러한 단점을 극복하기 위해, 수작업에 소요되는 구축비용의 절감을 위한 많은 기법들이 개발되어 왔다.
준 지도 학습으로 분류되는 기계학습 기법은 수집된 위치 정보가 표시되지 않은 신호 데이터와 표시된 신호 데이터를 모두 활용하여 측위 모델을 학습 할 수 있기 때문에 구축 비용 절감에 도움이 된다. 그러나 준 지도 학습은 일정량의 위치 라벨을 필요로 하기 때문에 구축 비용절감에 있어 그 한계를 가진다. 구축비용 절감을 위한 또 다른 기법으로 크라우드소싱 기반 데이터 수집 시스템을 들 수 있다. 일부 크라우드소싱 기반 시스템은 사용자의 단말기에 설치되어있는 관성센서를 활용하여 핑거프린트 데이터베이스 구축을 위한 위치 라벨를 자동으로 알아내기도 한다. 그러나 추가적인 센서를 사용함에 따라 센서 정확도나 가용성에서 기인하는 한계를 가지고 있고, 추가적 배터리 소모 등과 같은 문제가 있기 때문에 아직 널리 활용되지는 못하고 있다.
본 학위 논문에서는 위치라벨이나 다른 위치 관련 정보 없이 실내 측위를 위한 모델을 구축 할 수 있도록 하는 새로운 자율 기계학습 (unsupervised learning) 기법을 제안한다. 제안된 자율 학습 기법은 위치 정보가 표시되지 않은 신호 데이터만을 활용하여 기계학습을 통해 데이터의 위치 라벨을 추측하고, 이를 이용하여 실내 측위 모델을 구성 할 수 있다. 이를 위하여 본 논문에서는 은닉마르코브모델 학습 알고리즘을 미미틱 알고리즘의 부분/전체 하이브리드 최적화 구조에 부분최적화 모듈로 통합하는 기법을 제안한다.
앞서 언급되었던 준 지도 학습을 포함한 기계학습 기법들은 부분 최적 해에 빠지는 문제와, 학습된 측위 모델을 실제 실내 지도상에 알맞게 배치하는 문제를 해결하기 위해 일정량의 위치 라벨을 활용할 수 밖에 없었다. 이와는 달리, 본 논문에서 제안한 방법은 효율적인 하이브리드 최적화 기법을 활용하고, 무선 신호전달의 물리 법칙 및 실내 구조도로부터 도출되는 제약조건을 활용하여 부분 최적해 에 빠지는 문제와 학습된 모델을 배치하는 문제를 해결한다. 이러한 전략은 최적화를 위한 탐색 공간의 크기를 크게 줄일 수 있으며, 그 결과 위치 라벨 데이터 없이도 모델 구축을 가능케 한다.
본 논문에서 제안된 기법은 기존의 측위 모델 구축비용 절감 기법들에서 필요로 했던 신호 환경 정보 획득이나, 추가 센서의 사용 및 위치 라벨 부여를 위한 노력을 따로 필요로 하지 않는다. 제안된 기법에서 필요로 하는 위치 정보가 표시되지 않은 신호 데이터는 단순히 무선인터넷 단말기의 사용자가 실내 공간에서 생활할 때에 별도의 추가 노력 없이 얻을 수 있기 때문에 매우 적은 비용으로 수집될 수 있다. 즉 제안된 기법은 실내 측위 시스템 구축비용 절감에 효과가 매우 크다 할 수 있다.
본 학위 논문의 주요 기여 점은 다음과 같다. 1) WLAN 기반 실내 위치 인식을 위한 최초의 자율 기계학습 기법 고안, 2) 다양한 WLAN 핑거프린트 기반 측위 기법에서 활용될 수 있는 범용 학습 데이터 생성기법 고안, 4) 또 다른 구축비용 절감 연구에서 쓰일 수 있는 몇몇 자동화 및 최적화 테크닉 제안, 5) 각 모듈이 더욱 고도화된 기법으로 대체 될 수 있는 실내 측위를 위한 자율 학습 프레임워크 제안.
