Keywords

1 Introduction

A global indoor positioning system (GIPS) is a positioning system that can provide indoor positioning services in most buildings in villages and cities globally. The goals of wide availability and high resolution should be accomplished for a positioning system to be a GIPS. While the global positioning system (GPS) has been dominantly used outdoors since its completion in the early 1990s, no GIPS with such a wide availability and high resolution has yet appeared.

Various signals such as cell-tower signals, radio frequency (RF), Wi-Fi, Bluetooth, magnetic fields, and ultra-sounds can be used for indoor positioning. Among these signals, the Wi-Fi signal is one of the best candidates to construct a GIPS because of its widespread availability of Wi-Fi hot spots all over the world. However, the wide availability of Wi-Fi signals does not guarantee a high resolution of Wi-Fi-based positioning systems. A radio map, which is a collection of fingerprints along with their collected location information, should be constructed at each building to provide WLAN-based positioning service. Here, the fingerprint is the WLAN signal characteristics represented by a set of signal strength and access point ID pairs.

However, constructing precise radio maps covering most buildings in cities globally requires tremendous time and effort. Consequently, reducing calibration efforts to construct radio maps has long been a critical issue in this research area [1]. Google has been collecting indoor floor plans and radio maps by crowdsourcing since the end of 2011 [2]. Thousands of floor plans have been collected, but until now, they have been mainly from large-scale buildings such as airport terminals, shopping malls, and exhibition centers. However precise positioning services are not yet available in most buildings because of lack of radio maps which require manual calibration efforts.

In fact, constructing a GIPS that integrates indoor maps, radio maps, and positioning algorithms is a large, complex project. This study introduces methods and tools to construct a GIPS by using Wi-Fi signals. The key idea is to realize a GIPS by collecting indoor and radio maps from volunteers who are interested in developing or deploying indoor positioning systems for their buildings. A GIPS provides methods and tools to support the volunteers, and the indoor and radio maps collected from the volunteers while they are developing their indoor positioning systems are shared by the users and applications of the GIPS.

The reason we employ a crowdsourcing approach is that it is the only way to collect indoor maps and construct radio maps globally at a very low cost in a short period of time. We developed an unsupervised learning-based radio map construction method to construct radio maps with crowdsourced fingerprints. However, all the radio maps for the GIPS need not be constructed this way. We also developed tools and web interfaces to collect radio maps from volunteers on the Internet. This radio map collection strategy inevitably results in diverse types of radio maps because collected radio maps may be constructed in various ways.

The GIPS has to deal with such various types of radio maps. It is known that one positioning algorithm cannot always outperform other positioning algorithms for all types of radio maps. The GIPS should be equipped with multiple positioning algorithms to cope with the diversity of radio map types. It switches from one positioning algorithm to another depending on the types of radio maps for better positioning performance. Mapping radio maps into appropriate positioning algorithms is an essential function of the GIPS. In this study, we propose a method to map radio maps into positioning algorithms. The diversity of radio maps cannot be handled only by the mapping of radio maps and positioning algorithms, because most existing positioning algorithms are not suitable, especially for radio maps constructed with crowdsourced fingerprints. This study also proposes a new probabilistic positioning algorithm adapted for radio maps constructed with crowdsourced fingerprints.

Using the methods and tools needed for the GIPS, an experimental GIPS, KAist Indoor LOcating System (KAILOS) was developed. KAILOS allows anyone to contribute indoor and radio maps of buildings by using its methods and tools. In return, it provides indoor positioning and navigation services for the buildings. KAILOS has a long way to go to cover most of the buildings in villages and cities globally. Nevertheless, it was used very effectively for developing indoor positioning and navigation systems in some confined areas such as COEX mall, Seoul, and the KAIST Daejeon campus. In addition, it has been shown that the unsupervised leaning-based radio map construction method and the proposed probabilistic positioning algorithm can be effectively used in reducing the cost of radio map construction and improving the accuracy of positioning in crowdsourced radio maps.

This chapter is organized as follow: Sect. 14.2 introduces a positioning technology stack; Sect. 14.3 describes the methods, techniques, and tools to construct a GIPS; Sect. 14.4 describes an experimental GIPS, KAILOS; Sect. 14.5 describes the performance evaluation of radio map construction methods and the proposed probabilistic positioning algorithm and introduces examples of using KAILOS; finally, we draw our conclusion in Sect. 14.6.

2 Location Technology Stack

A positioning technology stack is a layered structure of technical and environmental elements required to implement positioning systems and services. Signals, maps, positioning systems, and location-based applications are the major components constituting a positioning technology stack. Figure 14.1 shows the layered architecture of such technical and environmental elements in the positioning technology stack. As illustrated in the figure, there is only a slight difference between outdoor and indoor positioning environments from the technology point of view.

Fig. 14.1
figure 1

Positioning technology stack

Full size image

Signal environments are the fundamental basis of a positioning service. Without the presence of appropriate signals, positioning service is not possible in both indoor and outdoor environments. GPS signals are mainly used outdoors, whereas 3G, 4G, Wi-Fi, Bluetooth signals, and magnetic fields can be used indoors. From an availability point of view, 3G, 4G, and Wi-Fi signals can be used for the GIPS because they are available in most buildings in cities. However, from an accuracy point of view, there is no other way but to use Wi-Fi signals incorporated with fingerprint-based positioning techniques [3]. Thus, radio maps, which are collections of fingerprints with their collected locations, should be constructed for most of the buildings globally.

Map environments are another fundamental basis of positioning systems and services. Without a map, the positioning service can hardly be provided to users. In addition, many advanced positioning techniques, such as map matching and automatic radio map construction, are developed on models constructed on a map. Partitioning and drawing road networks for an area are typical examples of the modeling. A more complex modeling can be done with a state machine such as a Hidden Markov Model (HMM). We leave the details to Sect. 14.3.1.

Various location-based applications, such as navigation systems, can be developed using positioning systems. Although the positioning systems can be integrated with the applications, a positioning service platform is usually placed between the positioning systems and the applications. Hence, the positioning service platform layer is placed on top of the positioning system layer. Lastly, the location-based applications layer is placed on the top of the stack. The details of each layer of the positioning technology stacks are described in the following sections.

3 Methods and Tools to Construct a GIPS

3.1 Deployment Process of Indoor Positioning System

Prior to describing the construction of a GIPS, we describe the process of installing an indoor positioning system in a building. The techniques and tools for a GIPS will be explained along the process of installing an indoor positioning system. Various activities should be performed to deploy a fingerprint-based indoor positioning system in a building. Indoor maps should be prepared, and a model of the area is required for radio map construction and more advanced techniques. Radio maps are then constructed for the modeled indoor area by using one of the radio map construction methods. Once the construction of a radio map is completed, an indoor positioning system is installed on top of the radio maps. Testing and evaluation must be performed to ensure the quality of the deployed indoor positioning systems. In this section, we describe the detailed activities required at each step along with the methods and tools provided by the GIPS for these activities.

3.2 Indoor Map Registration and Modeling

3.2.1 Indoor Map Drawing and Registration

An indoor map is the basis for developing a fingerprint-based indoor positioning system. The collection of fingerprints, installation of positioning systems, and provision of positioning services can hardly be performed without an indoor map. However, indoor maps of a majority of the buildings in cities are not yet available. Crowdsourcing seems to be the only possible way to address this problem. To support the crowdsourcing of indoor maps, the GIPS provides tools and interfaces to collect indoor maps from volunteers all over the world. Building registration should be the first step in the collection process. This is done by drawing a polygon on a Google outdoor map. The GIPS highlights the specified building by changing the color of the polygon. Floor map registration is performed after the building registration. The GIPS also provides interfaces for volunteers to register points of interests (POIs), such as room numbers and store names, on the registered indoor map for users to locate their destinations.

Many positioning techniques were developed using various kinds of indoor maps. However, if an indoor map is specified in an image file format, it lacks information needed for some advanced positioning techniques. In addition, to use an advanced learning-based method to label the locations of crowdsourced unlabeled fingerprints, indoor areas need to be modeled with a state machine such as an HMM. We describe the details of modeling in the next section.

3.2.2 Modeling of Indoor Areas

To collect fingerprints, simplify the movement of a user, or represent the characteristics of signals in relation to locations, modeling of the indoor area is required. Partitioning is a basic modeling technique to collect fingerprints in an area. Fingerprints are collected at each partitioned area. Road networks are usually used to support the optimization of map-matching filters. A state machine is often used to represent the characteristics of signals observed in an indoor area [4]. An HMM, which is a variation of the state machine, is used to model the movement of users and signal characteristics in an indoor area. The transition and observation probabilities of the HMM match well to the movement of users and signal characteristics observed at each location, respectively [5].

Supporting partitioning and road network modeling in the GIPS is rather simple and straightforward. It is only necessary to provide tools to draw road networks on indoor maps. Unlike the modeling of road networks, HMM modeling involves a rather complex process. The first requirement for HMM modeling is to partition each floor into parts. The GIPS automatically divides an indoor map into parts after the specification of walls and doors. Because each partition of an indoor area is mapped onto a state of the HMM, the partitions may be considered as the states of the HMM.

3.3 Radio Map Construction

Radio map construction is usually performed on the models just described. In fact, radio map construction is one of the key features distinguishing the GIPS from other ordinary indoor positioning systems. It aims to support all kinds of radio map construction methods, including a novel unsupervised learning-based location labeling method (ULM) for crowdsourced fingerprints collected without location information. The ULM is expected to greatly reduce the time and effort needed to construct radio maps [6]. In this section, we present the existing radio map construction methods and ULM for the GIPS.

The first proposed radio map construction method was point-by-point manual calibration (PMC). The primary goal of this method was to achieve a high accuracy without much regard for the cost. In this method, an indoor area is partitioned into numerous parts, and then dedicated collectors collect Wi-Fi fingerprints point-by-point (see Fig. 14.2a). Because PMC requires considerable time and effort, a walking survey was developed to reduce the cost [4]. In the walking survey, only some points, such as corners and the start and end points of the survey paths, are specified to guide the collectors (see Fig. 14.2b). The fingerprints are collected while the collectors walk along the path carrying collection devices.

Fig. 14.2
figure 2

Radio map construction methods: (a) PMC, (b) walking survey, (c) semi-supervised learning, and (d) unsupervised learning

Full size image

The semi-supervised learning method utilizes references to label the locations of fingerprints (see Fig. 14.2c). The location of access points (APs), Bluetooth signals, or GPS signals are often used for the references [7]. Manifold learning [8–10] and expectation maximization [11] techniques have been developed to construct radio maps by using unlabeled fingerprints with only a few labeled fingerprints. The goal of semi-supervised learning is to further reduce the manual calibration cost, although it still requires some effort to acquire references.

A recent research approach uses inertial sensors such as a three-axis accelerometer, gyroscope, and compass. Microsoft Zee [12], UnLoc [13], WILL [14], LiFS [15], and other methods have tried to incorporate dead-reckoning techniques for labeling the locations of crowdsourced fingerprints by using inertial sensors in smartphones along with the location of stairs, elevators, and other features. These so-called sensor-based methods can further reduce the collection effort. However, the involvement of additional sensors impedes the contribution of fingerprints from numerous smartphones because sensor operation consumes additional power.

The ULM labels the location of crowdsourced fingerprints from numerous smartphones (see Fig. 14.2d). This method is distinguished from the sensor-based methods because it does not require any explicit labeling effort or sensing data for reference. The ULM, which has been implemented in the GIPS for the first time, allows almost all crowdsourced fingerprints to be used for the construction of radio maps.

Figure 14.3 shows an overview of the method. Here, the target area is assumed to have already been modeled with an HMM. It integrates location optimization and global search in a hybrid learning framework to determine an optimized placement of collected fingerprint sequences in an area. When a set of unlabeled fingerprint sequences has been collected in a building, the ULM repeats the local optimization and global search in turn until it finds an optimized placement of the unlabeled fingerprint sequences in the hybrid learning framework.

Fig. 14.3
figure 3

ULM to label the location of crowdsourced fingerprint sequences

Full size image

Because the local optimization often becomes stuck in local optima, the global search provides new inputs to prevent this. When a genetic algorithm is used for learning, the genotype of the leaning should be created by combining access point (AP) locations and path loss exponents, and the phenotype of the learning is represented with a set of fingerprints. The genotype, which is an abstraction of phenotypes, is used for the global search, and the phenotype is used for the local optimization. The search space of the global search can be drastically reduced using the genotype, and the local optimization can be effectively performed using the phenotype. Although the ULM requires some computational time for labeling, it can drastically reduce the manual effort needed to construct radio maps.

3.4 Mapping of Radio Maps and Positioning Algorithms

Once a radio map is constructed, a positioning system equipped with various positioning algorithms can be installed on the radio map to provide a positioning service. Installing a positioning system on top of the constructed radio maps is one of critical steps in deploying an indoor positioning system in a building. If the radio maps are assumed to be collected by crowdsourcing, the types of radio maps for the GIPS would be diverse in terms of collection methods and density of collected fingerprints. A positioning algorithm appropriate to each radio map type should be used to achieve high accuracy.

In general, it is known that probabilistic positioning algorithms such as the Gaussian and histogram methods can achieve a relatively good performance on radio maps with a high fingerprint density, whereas discrete positioning algorithms do better on radio maps with a low fingerprint density. A single positioning algorithm can hardly be expected to achieve a good performance on both low- and high-density radio maps. Hence, the GIPS must be equipped with several positioning algorithms and select the most appropriate one depending on the characteristics of the respective crowdsourced radio maps. In fact, the only major difference between the positioning system for the GIPS and ordinary positioning systems is the diversity of the radio maps to be handled.

In this section, we describe the mapping between radio maps and positioning algorithms for the GIPS. We start this with a brief introduction to existing positioning algorithms.

3.4.1 Positioning Algorithms

Positioning algorithms can be classified into two groups: probabilistic and discrete. Positioning algorithms that estimate locations by searching the nearest fingerprints for an online measurement in discrete radio maps, such as kNN and weighted kNN [16], belong to the discrete positioning algorithm category. On the other hand, positioning algorithms that estimate locations based on the distributions of signal strengths, such as Gaussian, histogram, kernel methods, and Viterbi tracking algorithm, belong to the probabilistic positioning algorithm category.

Figure 14.4 is a rough sketch of the expected accuracy of positioning algorithms with respect to the precision of radio maps and radio map construction methods. As shown in the figure, the accuracy of the positioning algorithms is usually expected to improve with the increment of the precision of radio maps, i.e., the number of fingerprints collected at each measurement point or partitioned area. The radio map construction methods and appropriate positioning algorithms are also illustrated with the cost expectation. The information in the graph should not be taken as a definitive mapping between the radio map models and the positioning algorithms, however, because it is only a rough sketch of their matches.

Fig. 14.4
figure 4

Radio map construction methods and positioning algorithms with respect to cost and accuracy

Full size image

3.4.2 Mapping Radio Maps into Positioning Algorithms

The GIPS classifies the crowdsourced radio maps into four radio map types depending on the fingerprint collection method and number of fingerprints collected at each measurement point. The types of radio maps given their collection method and number n of collected fingerprints at each measurement point or partitioned area are as follows:

  • Regular-highly-dense radio map: PMC and n > 20

  • Regular-dense radio map: PMC and 20 ≥ n > 10

  • Regular-sparse radio map: walking survey and n = 1 or 2

  • Irregular radio map: crowdsourcing (Irregular-dense if n ≥ 15 and Irregular-sparse if n < 15).

Figure 14.5 shows the mapping of radio map types into radio map models and then positioning algorithms. As shown in the mapping, if a radio map is constructed by a PMC, and more than 20 fingerprints have been collected at each measurement point, it is classified as a regular-highly-dense radio map. Any kind of radio map model can be used to represent the characteristics of a regular-highly-dense radio map, and any kind of positioning algorithms can be used for regular-highly-dense radio maps.

Fig. 14.5
figure 5

Mapping of radio map construction methods, radio maps, and positioning algorithms

Full size image

If a radio map is constructed by PMC with 10–20 fingerprints at each measurement point, it is classified as a regular-dense radio map. The discrete and Gaussian radio map models can be used to represent the characteristics of a regular-dense radio map. However the histogram and kernel models are not suitable because of the lack of collected fingerprints.

In contrast, if a radio map is constructed by a walking survey and only one or two fingerprints have been collected at each measurement point, it is classified as a regular-sparse radio map. Only a discrete radio map model can be used to represent the characteristics of a regular-sparse radio map. There is no other option but to use the discrete positioning algorithms, kNN or WkNN for a regular-sparse radio map.

When fingerprints have been collected by crowdsourcing, an irregular radio map is constructed. Irregular radio maps are divided into irregular-dense and irregular-sparse radio maps, depending on the number of fingerprints collected at each partitioned area. The discrete and Gaussian radio map models can be used for an irregular radio map. The positioning algorithms corresponding to the selected radio map models should be used.

3.5 Probabilistic Positioning Algorithm for Radio Maps with Crowdsourced Fingerprints

In the previous section, the diversity of radio maps was assumed to be handled by the GIPS with the mapping of radio maps and positioning algorithms. In reality, however, most of the existing positioning algorithms are not suitable, especially for the radio maps constructed with crowdsourced fingerprints. As a result, the GIPS can hardly be expected to achieve a good performance on radio maps constructed with crowdsourced fingerprints only by the mapping. In this section, we propose a new probabilistic positioning algorithm adapted for radio maps constructed with crowdsourced fingerprints.

The proposed positioning algorithm extends Viterbi tracking algorithm (VA) in the framework of the HMM because the VA is a probabilistic positioning algorithm utilizing historical trajectories of users [17, 18], and probabilistic tracking of dynamic movement of users can be effectively modeled in the HMM. The Extended VA (EVA) can take advantage of the probabilistic framework for tracking the dynamic movement of a user—even when only a few samples have been collected at each measurement point—without incorporation of inertial sensors. These are the common conditions of fingerprints collected from crowdsourcing.

3.5.1 Emission Probability

The modification of the emission probability calculation of the HMM is the first extension of the VA. The emission probability is usually calculated based on received signal strength (RSS) distributions, which require multiple fingerprint samples. An RSS distribution is known to be multimodal and often represented in the form of a histogram, log normal distribution, and Gaussian distribution, or even by a single mean RSS value [19]. The more complex distributions, such as a histogram, require more samples, but it is known that performance improvement is not significant by the choice of the distributions unless samples are enough [20]. We derive emission probabilities by using only mean RSSs that can be obtained from a few samples collected at each location, because not so many samples are assumed to be available at each location.

For the derivation of emission probabilities from a mean RSS of a location, we assume that RSS distribution follows the Gaussian for an AP at a location. Another hidden assumption of Euclidean distance (ED)-based methods is that standard deviations of RSSs are the same for all APs at any locations. If enough samples are provided, the standard deviation is worth being referred to in positioning. Otherwise, it would be better to ignore it because the standard deviation calculated from few samples is usually unreliable.

The assumptions of Gaussian distribution and uniform standard deviation may not hold for real-world RSS distributions. However, by taking these assumptions, EVA inherits the robustness of the ED-based methods despite the lack of training samples.

3.5.2 Dynamic Transition Probability

The second extension of the algorithm is the calculation of dynamic transition probabilities. Transition probabilities can be dynamically calculated based on the moving distance of a user at each time. In order to obtain the moving distance without the incorporation of inertial sensors, we exploit the fact that the change of user positions is reflected in Wi-Fi fingerprint. The moving distance indicated by signal changes can be estimated by the distance between the positions of two successive online fingerprints.

In the distance estimation, we consider the topology of routes induced by inner structures including doors, walls, and other barriers in an indoor area. We also consider the k most probable locations of a fingerprint for a more reliable estimation. Let kL t−1 be the set of the k most probable locations for an online fingerprint o t−1 given at time t−1, and kL t be that for the next fingerprint o t . The moving distance d t−1,t of the two fingerprints is then calculated as the average distance between the pairs of locations in the two sets,

$$ {d}_{t-1,t}=\frac{1}{\left|k{L}_{t-1}\left|\cdot \right|k{L}_t\right|}{\displaystyle \sum_{u\in k{L}_{t-1}}{\displaystyle \sum_{v\in k{L}_t}TD\left(u,v\right)}}, $$
(14.1)

where, TD(u, v) returns the topological distance between two locations u and v.

Given a distance estimate d t−1,t at time t, a transition probability \( P\left({l}_j\Big|{l}_i\right) \) is extended to \( P\left({l}_j\Big|{l}_i,{d}_{t-1,t}\right). \). This probability can be computed using PDF under Gaussian assumption if the standard deviation of estimation errors σ is given as follows:

$$ P\left({l}_j\Big|{l}_i,{d}_{t-1,t}\right)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{\frac{{\left(TD\left({l}_i,{l}_j\right)-{d}_{t-1,t}\right)}^2}{2{\sigma}^2}}. $$

The standard deviation of estimation errors , σ is unknown. In the implementation, from an arbitrary value, σ was adjusted based on the accumulated results of the tracking; the difference between d t−1,t and its corresponding distance in the tracking result was considered as the error of the moving distance estimation. A maximum moving distance of a human was also set in order to remove unrealistic transitions; transitions longer than a maximum distance setting were regarded to have a zero transition probability.

3.5.3 Extension of Viterbi Algorithm

The VA finds a location sequence L seq t = <l o ,…,l t > that maximizes P(L seq t , O seq t ) for a given fingerprint sequence O seq t  = <o 0 , …, o t > observed from time 0 to time t. Here, we extend the probability function to \( P\left({L}_t^{seq},{O}_t^{seq}\Big|{D}_t^{seq}\right) \) in order to reflect dynamic user movements represented by a moving distance vector D seq t  = <d 0,1 ,…, d t−1,t >.

With the extended probability function, the standard dynamic programming technique of VA determines the most probable trajectory of a user by simply replacing emission and transition probabilities with the extended ones. Once the most probable trajectory is found, the end point of the trajectory can be considered as the user position at current time t.

While the basic tracking considers only a single best trajectory, the best k trajectories are considered by the proposed algorithm. It estimates the position of a user by averaging the final locations of the k most probable trajectories. That strategy was known to be effective in decoding a data sequence observed through a noisy channel [21].

3.6 Testing and Evaluation

Testing and evaluation should be performed to measure the positioning accuracy after deploying a positioning system on the radio maps of a building. Thus the GIPS should be equipped with methods and tools for evaluation and testing. For example, it is helpful to visualize the signal distributions of collected fingerprints before testing and evaluation. The areas in which the collection of fingerprints has been incompletely performed can be easily identified through visualization. This visualization is especially important in the GIPS because the collection activity is usually performed by volunteers who cannot easily communicate with the developers or operators of the GIPS.

The GIPS visualizes the signal characteristics of collected fingerprints at a location with a light green circle when only weak Wi-Fi signals are available, a bright green circle for a few strong signals, and a red circle when many strong Wi-Fi signals are available. When an area’s set of fingerprints is incomplete by mistake, the collection of fingerprints should be performed once more at the area.

Once the test results are obtained, any faults and errors should be examined and fixed if possible. For example, floor errors are often detected during testing. The GIPS can mitigate the floor errors to some extent by using the sensing data from a pressure sensor. We do not delve into the details because of space limitations. The volunteers can improve the signal environment by installing additional APs or Bluetooth beacons.

4 KAIST Indoor Locating System

Most of the aforementioned methods, tools, and algorithms have been integrated into an experimental GIPS named KAILOS [22, 23]. KAILOS supports the entire deployment process of an indoor positioning system in a building. KAILOS consists of three parts: KAI-Map, KAI-Pos, and KAI-Navi. Kai-Map includes indoor and radio maps. KAI-Pos, installed on top of KAI-Map, is an indoor positioning system equipped with several positioning algorithms, such as discrete and probabilistic positioning algorithms, from which it selects an appropriate one for the underlying radio map. It provides positioning services for the buildings whose indoor and radio maps have been contributed to KAILOS. KAI-Navi is an indoor/outdoor integrated navigation system. It directs users to the destinations in both indoor and outdoor environments. The following describes the details of the KAILOS components. Figure 14.6 shows the architecture of KAILOS.

Fig. 14.6
figure 6

The architecture of KAILOS

Full size image

4.1 KAI-Map

4.1.1 KAI-Radio Map

KAILOS is equipped with methods and tools to support the PMC, walking survey, and unsupervised-learning-based radio map construction methods. To support the PMC, KAILOS provides tools to plan collection points on indoor maps, and collect Wi-Fi fingerprints on the planned points. The collectors are assumed to collect 10–20 fingerprints on the marked collection points. The match of the marked collection points and the real collection points should be confirmed by the collectors themselves during the collection activity.

KAILOS also supports the walking survey by providing tools to plan survey lines, collect fingerprints, and label the locations of collected fingerprints. In the waking survey, the survey lines should be planned in advance without the specification of collection points. Only the start and end points of survey lines are specified to guide the collectors.

KAILOS also provides tools for the proposed unsupervised learning-based method. The fingerprints are assumed to be collected by collectors who just walk around all the locations of the floor carrying the smartphones after installing the collection tool. Then KAILOS labels the locations of collected fingerprints. The time and effort of collectors can be drastically reduced by the learning-based method.

4.1.2 KAI-Indoor Map

In Sect. 14.3, indoor maps were assumed to be given. In reality, however, most of the indoor maps of buildings are still unavailable. To address this problem, KAILOS provides tools and interfaces to contribute indoor maps. KAILOS assumes that the contributors already have the indoor maps of their buildings in an image file format, and radio maps will be collected by walking survey or crowdsourcing. Figure 14.7 shows the schematic view of the contribution process. As shown in the figure, building registration is the first step of the contribution process. The floor map registration step follows after the registration of a building. POIs are registered and specified on the floor map for users to find or search their destinations. KAILOS supports volunteers by providing interfaces to register POIs for the registered indoor maps.

Fig. 14.7
figure 7

Registration of an indoor map and designing survey lines and road networks

Full size image

KAILOS also provides tools to model indoor areas. Partitioning, designing road networks, and constructing a state machine such as an HMM are typical modeling methods. Currently, KAILOS is equipped with a tool to design road networks. This is because the path finding for indoor navigation cannot be realized without the road networks.

4.2 KAI-Pos

The probabilistic positioning algorithm introduced in Sect. 14.3 is the basis of KAI-Pos. It also incorporates various filters for more accurate positioning. KAI-Pos adopts an adaptive hybrid filter to utilize the dynamics of user movements, and a map-matching filter to utilize the road network model. The effect of the filters was apparent when they were applied for developing indoor positioning systems at the COEX mall, Seoul, Korea in 2010 and 2014.

Though Wi-Fi signals have been mainly used, KAI-Pos incorporates other wireless signals and sensing data from various sensors for more accurate positioning. Bluetooth signals are often used to cover areas in which Wi-Fi signals are not available or only weak signals are available. A pedestrian dead-reckoning PDR using smartphone sensors, such as a three-axis accelerometer and a gyroscope, has been incorporated to compensate for the gap incurred by the time interval of consecutive scans. The time interval of consecutive Wi-Fi scans is known to be approximately 3–4 s. The floor errors can also be mitigated with the incorporation of a barometer sensor. Figure 14.8 shows the architecture of KAI-Pos. In the near future, it will incorporate the additional signals and sensors in a very tightly coupled manner using the so-called sensor-fusion technique [24].

Fig. 14.8
figure 8

Hybrid architecture of KAILOS positioning system

Full size image

4.3 KAI-Navi

KAI-Navi is an indoor/outdoor integrated navigation system. It directs users in both indoor and outdoor environments. KAI-Pos operates indoors, and GPS outdoors, and the estimated current location is displayed on KAI-Indoor Map and Google Maps, respectively. Any outdoor navigation system can be integrated with KAI-Navi if it can provide open APIs to be connected to. Currently, the SK Telecom T-map outdoor navigation system, which is the most popular outdoor navigation system in Korea, is connected with KAI-Navi. The outdoor paths have been connected to indoor paths through special points designated as entrances of buildings. KAI-Navi, named Campus Atlas in Google Play, was deployed on KAIST campus, Daejeon, Korea, accommodating around 40 four- to five-story buildings.

5 Evaluation and Examples

5.1 Performance Evaluation of Radio Map Construction Methods

Experiments were conducted to evaluate the performance of the radio map construction methods in the N5 building, and on the seventh floor, N1 building, KAIST, Daejeon. Four kinds of radio maps were constructed at the experiment buildings by using the PMC, walking survey, semi-supervised learning, and unsupervised learning methods. A Samsung Galaxy S3 was used to collect fingerprints with a sampling rate of 1 Hz. A simple kNN method (k = 3) was used for the localization test in the evaluation. All programs for the evaluation were implemented in Java and run on a 3.40-GHz Intel® Core™ i7 CPU with 8GB of memory.

Approximately 2000 fingerprints were collected on the seventh floor, N1 building, and approximately 4400 fingerprints in the N5 building for each method. Figure 14.9 shows the evaluation results. When 400 fingerprints were collected for the learnings, the walking survey achieved an accuracy of 1.7 m; PMC, 2.3 m; semi-supervised learning, 4.5 m; and unsupervised learning, 5.3 m. The accuracy gradually improved and then the improvement was saturated with the increase in the amount of learning data for all methods. The radio map types also converted from a sparse, to a dense, and then to a highly dense radio map with the increment in the number of fingerprints. When 2000 fingerprints were used, the walking survey achieved an accuracy of 1.2 m; PMC, 1.7 m; semi-supervised learning, 3.2 m; and unsupervised learning, 3.7 m. The walking survey outperformed the PMC in accuracy when the learning data were collected one or more times at every 1 m. This trend continues with the increment of the amount of learning data. This is because the distance between measurement points is reduced with the increase of learning data point. To collect 2000 fingerprints on the seventh floor, N1 building, the walking survey must collect fingerprints at every 4 cm, whereas the PMC was assumed to collect fingerprints at every 3 m just by varying the number of fingerprints collected at each measurement point.

Fig. 14.9
figure 9

Accuracy evaluation of radio map construction methods. (a) Accuracy achieved on the seventh floor, N1 building, KAIST. (b) Accuracy achieved in N5 building, KAIST

Full size image

Similar results were obtained in the N5 building. When 1500 fingerprints were used, the walking survey achieved an accuracy of 1.7 m; PMC, 2.5 m; semi-supervised learning, 3.3 m; and unsupervised learning, 4.7 m. When 4400 fingerprints were used, the walking survey achieved an accuracy of 1.5 m; PMC, 2.1 m; semi-supervised learning, 2.9 m; and unsupervised learning, 4.3 m.

Although the semi-supervised and unsupervised learning methods achieved accuracies slightly worse than the manual calibrations, the results were promising because they were within the accuracy range that can be used by practical positioning systems.

5.2 Performance Evaluation of Proposed Probabilistic Tracking Algorithm

The evaluation of EVA was conducted on the seventh floor, N1, KAIST. As three extensions were proposed, the extensions were applied to VA in stages. First, ED-based emission probabilities, dynamic transition probabilities, and their combination were applied to VA, separately; we denote them by EVA (ED), EVA (dynamic transition), and EVA (ED + dynamic transition), respectively. Then, the three best results of EVA (ED + dynamic transition) were used to evaluate the effect of considering multiple best trajectories on positioning accuracy; this configuration is denoted by 3-EVA. A simple kNN method (k = 3) was also compared in the evaluation. The maximum moving distance was set to 6 m for VA and EVAs in the experiments.

All of the extensions and their combinations were revealed to be effective for accurate positioning. EVA(ED) was more effective than VA, especially when using a few training samples. It provided 11 % improved positioning accuracy against VA when the number of samples was two at a location, whereas the improvement of using 20 samples was 5 %. Using fewer samples results in less-reliable RSS distributions being constructed. Since ED is calculated based on mean RSSs irrespective of RSS distributions, EVA(ED) was less sensitive to the amount of samples.

The improvement made by dynamic transition probabilities was also significant. The strategy of considering multiple trajectories was also revealed to be effective. The improvements of 3-EVA ranged from 8 to 14 % against EVA (ED + dynamic transition), and from 20 to 28 % against VA.

The cost of training to label locations of unlabeled fingerprints is a major hurdle in building a crowdsourcing-based indoor positioning system. It is closely related to the amount of data required for the training. Because the proposed positioning algorithm can achieve high positioning accuracy even if only a few training samples are available at a location, it can be used for practical crowdsourcing-based positioning systems to reduce the cost of constructing radio maps with crowdsourced fingerprints.

5.3 Examples of Using KAILOS

Since the release of KAILOS in the middle of 2014, the indoor positioning systems for subway stations, indoor shopping malls, and buildings on university campuses have been developed on KAILOS. Table 14.1 is the summary of the areas, buildings, and stores in which KAILOS has been used. The indoor positioning systems of COEX and KAIST were released integrated with mycoex 3.0 and Campus Atlas apps in the Google Play store to direct pedestrians to their destinations. The indoor positioning systems for shopping malls and game rooms on KAILOS were developed to issue coupons or game items for the promotion of particular stores, events, and games. The coupons or game items are notified to users when they are detected at specific areas.

Table 14.1 Summary of indoor positioning systems developed using KAILOS
Full size table

In addition, a company started registering indoor maps and constructing radio maps of subway stations on KAILOS to provide an indoor positioning service at subway stations in Seoul. The indoor and radio maps of five subway stations were collected along with their POIs. The collection activity should be conducted at as many as 600 subway stations for the complete installation of the subway indoor positioning system in Seoul. The indoor positioning systems of sea vessels were also developed on KAILOS for the safety of crew members. The working locations of crew members are displayed on a monitoring panel in an upper deck control room, and when someone is working or staying in dangerous working areas, an alarm is activated on the panel to watch the situation.

Among the examples, we describe the details of two examples: the COEX indoor positioning and navigation system deployed at the COEX mall in 2014, and an indoor/outdoor integrated campus navigation system deployed at KAIST in 2015. The KAIST campus, Daejeon, Korea, accommodates around 40 four-, five-, and ten-story buildings in an area of 1 km2 (see Fig. 14.10a). In contrast, the COEX area comprises Asia’s largest underground shopping mall area, three five-star hotels, one 55-story and one 41-story premier office tower, a big department store, a subway station, a city airport terminal, and other buildings (see Fig. 14.10b).

Fig. 14.10
figure 10

The bird’s eye view on KAIST, Daejeon, and the COEX, Seoul. (a) KAIST Campus, Daejeon. (b) COEX mall, Seoul

Full size image

In both cases, a walking survey was used for the collection of fingerprints. It took 5 days for five collectors to collect the fingerprints at the COEX, and 4 days for five collectors at KAIST. The accuracy differed depending on the conditions of the Wi-Fi signal environments. The areas with many strong AP signals usually showed a good accuracy. At the COEX, the accuracy on the first floor with a big open space was worse than that on the B1 floor. This result is similar to that obtained in 2010. The PMC was used to collect fingerprints at that time. Note that only one or two fingerprints were collected at each location by the walking survey, whereas approximately 20 fingerprints were collected by the PMC. On the B1 floor of the COEX (304 × 652 m in size), an accuracy of approximately 3–8 m was achieved by the walking survey. A similar accuracy was achieved by the PMC in 2010. A more detailed description on the PMC can be found in [23].

The man-month (MM) estimation to deploy an indoor positioning system in a building can be reduced to a tenth by using KAILOS. Approximately 20 MM were required for the development of the COEX indoor positioning and navigation system in 2010, whereas only 2 MM were required in 2014. Indoor map drawing, POI registration, modeling of road networks, survey planning, and fingerprint collection activities have been included in the MM estimation. Approximately 3 MM were required for deploying an indoor positioning system at the KAIST campus. The COEX and KAIST examples confirmed the benefits of using KAILOS for maintaining accuracy and reducing the time and effort needed to deploy indoor positioning systems.

6 Conclusion

Wi-Fi zones are still expanding, and the density of Wi-Fi signals is ever increasing globally. Despite the hurdles in implementing GIPS utilizing Wi-Fi signals, the Wi-Fi signals will be mainly used for the GIPS because of already-available Wi-Fi infrastructures.

This study presents the essential methods and tools to develop a GIPS by using Wi-Fi signals. An unsupervised learning-based fingerprint labeling technique was developed to construct radio maps by using crowdsourced fingerprints. It allows us to build the radio maps for most of the buildings in cities and villages at a very low cost. The practical probabilistic positioning algorithm turned out to be applicable for crowdsourced radio maps because it showed relatively good performance on the radio maps with randomly and sparsely collected fingerprints. Finally, the idea of mapping radio maps into positioning algorithms for positioning systems will allow the GIPS to accommodate new positioning algorithms.

However the techniques are applicable only for buildings whose indoor maps are available. Since the indoor maps of most of the building are currently unavailable, it will take some time until we have a complete GIPS. If the radio maps can be constructed for the buildings without indoor maps, we can shorten the time to realize the GIPS. Now, we are planning to develop the crowdsourcing radio map construction techniques for the buildings without indoor maps.