WLAN indoor positioning system is the most widely used one for locating targets because there have been already many installed access points. The major approaches in this system make use of fingerprints each of which is a vector composed of a location and received signal strength at the location. Among fingerprintingbased positioning algorithms, Viterbi algorithm based on Hidden Markov Model has showed better performance. However the fingerprinting-based approaches including Viterbi algorithm require large number of sample fingerprints at each location for constructing signal distribution and it results in heavy cost of collecting huge number of fingerprints. Although there have been various studies to reduce the cost, they have showed the
tradeoff between localization accuracy and reduced cost. This thesis proposes an extended Viterbi algorithm that is workable with the radio map constructed from few fingerprints at each location. At the same time, the algorithm can calculate moving distance without additional sensors so that transition probability can be calculated
dynamically. The algorithm is derived from conditional probability into the extended form of Viterbi algorithm for reflecting a trajectory of a target and provides an estimated location by averaging K-best probable locations. Experiments were conducted to compare the proposed algorithm with others including original Viterbi algorithm. According to the experiments, the proposed algorithm showed about 20% better positioning accuracy than Viterbi algorithm in the condition where the radio map is constructed from few fingerprints. It also represents about 10% better positioning accuracy in the conditions where fingerprints at each location are enough. It implies that cost of collecting large number of fingerprints can be reduced without loss of accuracy.
무선 랜 통신에 기반한 실내 측위는 이미 도처에 설치된 무선 통신기들(Access point)을
사용하며 추가적인 제반 시설을 설치할 필요는 없기 때문에 오늘날 가장 널리 사용되는 실내
측위 시스템이다. 무선 랜 기반의 실내 측위는 신호 지문(Fingerprint)을 활용한 방식이 주로 사용되는데, 이 때 신호 지문은 어느 한 지점의 위치 좌표와 해당 위치에서의 수집된 신호 세기 정보를 의미한다. 비터비(Viterbi) 알고리즘이 신호 지문 기반 실내 위치 인식에서 가장 좋은 성능을 보이고 있음에도 불구하고, 해당 알고리즘을 사용하기 위해서는 각 위치 별로 여러 번의 신호 지문을 수집하여 신호 분포를 확보해야 한다는 부담감과, 전이 확률(Transition probability)를 계산하기 위하여 이동 궤적을 확보해야 한다는 부담을 가지고 있다. 본 논문은, 이러한 비용적인 부담을 줄이면서도 비터비 알고리즘의 정확성을 확보할 수 있는 확장된 비터비 알고리즘을 제안한다. 본 알고리즘은 충분히 신호 지문을 수집하지 않은 곳에서도 동작할 수 있도록 확장되었고, 동시에 추가적인 감지기(Sensors) 없이도 이동 거리를 추정하고 이를 바탕으로 전이 확률을 동적으로 계산할 수 있도록 하였다. 실험을 통해 제안한 알고리즘은 신호 본래의 비터비 알고리즘 보다 개선된 성능을 보임을 확인할 수 있었고, 비단 비터비 알고리즘 뿐만 아니라 다른 실내 측위 알고리즘과 비교하였을 때에도 나은 성능을 보임을 확인할 수 있었다. 제안한 알고리즘은, 적은 수의 신호 지문으로도 높은 정확도를 유지할 수 있다는 점에서 장점이 있으며, 이를 통해 앞으로 실내 위치 인식과 관련된 서비스를 제공하고자 하는 단체에서 적은 부담으로도 양질의 위치 서비스를 제공할 수 있으리라 기대된다.