LOCALI: Calibration-Free Systematic Localization Approach for Indoor Positioning

Soojung Hur

and

Yongwan Park

Department of Information and Communication Engineering, Yeungnam University, Gyeongsan 38541, Korea

Author to whom correspondence should be addressed.

Sensors2017,17(6), 1213;https://doi.org/10.3390/s17061213

Submission received: 15 March 2017 /Revised: 20 May 2017 /Accepted: 22 May 2017 /Published: 25 May 2017

(This article belongs to the Special IssueSensors and Sensing in Indoor Localization, Tracking, Navigation and Activity Monitoring)

Downloadkeyboard_arrow_down

Browse Figures

Versions Notes

Abstract

Recent advancements in indoor positioning systems are based on infrastructure-free solutions, aimed at improving the location accuracy in complex indoor environments without the use of specialized resources. A popular infrastructure-free solution for indoor positioning is a calibration-based positioning, commonly known as fingerprinting. Fingerprinting solutions require extensive and error-free surveys of environments to build radio-map databases, which play a key role in position estimation. Fingerprinting also requires random updates of the database, when there are significant changes in the environment or a decrease in the accuracy. The calibration of the fingerprinting database is a time-consuming and laborious effort that prevents the extensive adoption of this technique. In this paper, we present a systematic LOCALIzation approach, “LOCALI”, for indoor positioning, which does not require a calibration database and extensive updates. The LOCALI exploits the floor plan/wall map of the environment to estimate the target position by generating radio maps by integrating path-losses over certain trajectories in complex indoor environments, where triangulation using time information or the received signal strength level is highly erroneous due to the fading effects caused by multi-path propagation or absorption by environmental elements or varying antenna alignment. Experimental results demonstrate that by using the map information and environmental parameters, a significant level of accuracy in indoor positioning can be achieved. Moreover, this process requires considerably lesser effort compared to the calibration-based techniques.

Keywords:

indoor positioning;IPS;ILBS;calibration free;localization;fingerprinting

1. Introduction

After the successful implementation and deployment of outdoor location based services (OLBS) using global positioning systems (GPSs), indoor positioning systems (IPS) are now popular. GPS signals from the satellites are prone to multi-path effects in indoor environments (the so-called GPS-denied environments) and are unable to provide a certain level of accuracy in location estimation. This drawback renders the GPS unsuccessful for indoor positioning. Indoor location-based services (ILBS) are expected to play an important role in a diverse range of services. The ILBS enables a user to track devices/users in an indoor environment. In recent years, several solutions have been proposed for the ILBS, providing different levels of accuracy, commonly known as "application specific accuracy levels". IPS solutions are categorized mainly into infrastructure-based and infrastructure-free. Infrastructure-based solutions require the pre-installation of special-purpose hardware infrastructure (e.g., Radio-frequency identification (RFID), Radio Sensors, Bluetooth, Ultra Wide Band(UWB), etc.) [1,2,3,4,5] and some of them provide a high level of accuracy. However, these solutions are less attractive due to deployment costs, whereas the infrastructure-free solutions are more attractive due to low costs and ready-to-deploy characteristics. Infrastructure-less solutions commonly utilize the existing Wi-Fi infrastructure [6] or Light-emitting diode (LED). lights [7] or imaging scene structure [8,9] or other resources that are already available in the environment to estimate the target position. As Wi-Fi infrastructures are commonly available in most public-service and private corporate buildings, most of the proposed ILBS solutions exploit Wi-Fi signals for indoor positioning. We can divide these solutions into two major approaches, i.e., calibration-based and calibration-free, also known as database-based/map-free and database-free/map-based solutions, respectively. The indoor environment is a hybrid owing to the co-existence of line-of-sight (LOS) and non-line-of-sight (NLOS) cases. This complexity in the indoor environment restricts the use of trilateration or triangulation techniques for positioning. The time of arrival (TOA) or time difference of arrival (TDOA) [10,11] suffers from multi-path propagation error and also from other issues such as time synchronization problems and short-range timing accuracies, respectively, whereas the angle of arrival (AOA) requires complex hardware for angle calculation. The received signal strength indicator (RSSI) value is a solution for avoiding the time synchronization but is affected by fading due to several reasons e.g., multi-path propagation or absorption for example by humans or varying antenna alignment. The fingerprinting technique offers a good balance between effort and accuracy for many use cases, currently available, for such complex indoor environments, addressing the fading error issue for Wi-Fi-based IPS. It is a calibration-based approach for enabling IPBS in GPS-denied environments; however, it also suffers from the challenging issue of tedious and time-consuming random database calibrations, which restrict its wide adoption. Several solutions have been suggested for reducing the construction and update time of the database [12]. Updates are required, if there are significant changes in the environment. In this work, we present a calibration-free positioning technique, which leverages the map information and provides a robust and efficient method for estimating indoor positioning, without a calibration database. We use the map information to estimate the propagation model for the LOS and NLOS, and construct an RSSI map for each access point (AP), as shown inFigure 1. Using these RSSI heat maps, we then estimate the target location using an overlap technique that employs a much simpler algorithm than the other techniques for position estimation (e.g., trilateration, triangulation and multilateration). Our approach is a step toward a simple and robust technique for calculating the path loss (by absorption and reflection) of the Wi-Fi signals through complex indoor environments for the construction of RSSI maps. Furthermore, it estimates the target location using the RSSI list received at the target location, as a system input, without trilateration or triangulation techniques. In this work, we briefly describe the advantages of our approach, which promotes adaptable, easy, and ready-to-be-deployed indoor location-bases services. Most of the proposed solutions estimate the location by iteration through all of the possible locations, whereas the LOCALI estimates the location directly using the map overlap technique. We use the words sender, transmitter, and AP alternatively in this manuscript.

InSection 2, we discuss some of the problems and challenges in the existing technologies. InSection 3, the proposed approach is discussed;Section 4 discusses the experimental details and results.Section 5 concludes the study.

2. Existing Systems

In most of the proposed indoor positioning techniques, target localization is based on the signal propagation time or the received signal strength (RSS) information from multiple transmitters, i.e., Wi-Fi APs. Trilateration and triangulation, which use the propagation time information, undergo an unacceptable accuracy limitation due to certain constraints; the TOA requires a high level of precision in the time synchronization, at both the sender and receiver sides. This becomes more critical, when synchronization is done for the very short ranges of an indoor environment. Specialized directional antennas are required to accurately assess the AOA of the RF signals. The TDOA is used to avoid the time synchronization problem, but it has multi-path propagation delay errors inside the building due to walls or obstructions. Instead of using the vulnerable time information, most studies use the RSSI, a metric that is most commonly used in IPS as a substitute for the time information, with respect to the distance between the sender and receiver. However, the RSSI also suffers from fading due to multi-path, absorption by soft objects and varying antenna alignment in a multi-modal environment [13], and it is almost impossible for the RSSI level to be circular with respect to the distance from the transmitter to the receiver. Hence, we cannot use trilateration directly to estimate the position of the target. Fingerprinting is a calibration-based solution for such trilateration and triangulation problems. In this study, we place emphasis on the fingerprinting technique using the RSSI of the Wi-Fi network [14,15], whereas fingerprinting can also be carried out using other kinds of signal or field strength (e.g., geo-magnetism) [16]. Fingerprinting has two phases: the pre-deployment offline survey training phase and the online location estimation phase. It requires a comprehensive survey of the environment to construct an RSSI database at a certain degree of spatial granularity. This training point granularity is significant with respect to the level of accuracy required from the fingerprinting technique. It is time-consuming to record the RSSI level at each grid point of the environment; it becomes more challenging, when the device orientation, the types of devices used in the survey, and the averaging of the RSSI level due to the time varying characteristics of the RSSI are to be considered. Of late, extensive research efforts have been made to reduce this laboriously time-consuming fingerprinting training phase and several solutions have been proposed [12].

2.1. Interpolation-Based Systems

Some of the solutions attempt to reduce the survey time using interpolation techniques with a modified path-loss model at sparse reference points. In [17], the author combines the fingerprint prediction model with a calibration procedure and proposed a new hybrid model that provides a comparable location accuracy using a few RSSI samples to that of the traditional fingerprinting approach. Triangular interpolation and extrapolation (TIX) [18] uses only online Wi-Fi RSS values measured at each AP to obtain a linear mapping between RSS decay and distance, which further helps in estimating client location using the TIX algorithm. Similarly, a signal-distance map (SDM) [19] works on the same principle, whereas the mapping of distance between APs and RSS measurements is obtained by singular value decomposition (SVD).

2.2. Crowdsourcing-Based Systems

Systems employ active user inputs or crowdsourcing [20,21,22,23,24,25,26] to build a radio-map database online instead of using the conventional time-consuming task of building a training database through a survey. The Organic indoor Localization OIL [22] incorporates the active user input after training phase to extend the converge and accuracy of fingerprinting based localization at particular areas called varonoi regions. EZ [23] does not require prior map and transmitter location information and resolves the environment, devices and distance parameters by running a genetic algorithm on RSS information reported by a background service running on user mobiles. Walkie-Markie [24] also relaxes the prior information of indoor RF infrastructure and tries to generate maps of the environment using crowd-sourcing. The Wifi-mark estimation in the Walkie-Markie requires a sufficient number of users reporting the trajectory information on at least two sides of an AP, which is nearly impractical from the user’s point of view and the building architecture, with corners and long continuous hallways in which traversal to the other side is not usually possible.

2.3. Sensors-Based Systems

Recent research developments in ILBS technology use data from a wide range of sensors, i.e., inertial sensors, accelerometers, gyroscopes, magnetic sensors, etc. to improve indoor positioning and mapping [27] using data fusion techniques [28,29,30,31]. WILL (Wireless Indoor Localization) and unLoc trace user movements with an inertial sensor to generate a map of the environment [32,33].

2.4. Model-Based Systems

A model-based indoor positioning algorithm is presented in [34] to address the absorption effects of crowded scenarios on Wi-Fi signals through an indoor canyon environment and crowed sensing is achieved by using a mobile camera with the assistance of deep Convolutional Neural Network (CNN). A similar approach of location estimation using the merging of multiple heat-maps is discussed in the Probability Maps Technique [35]. The probability map technique uses RF packet transmission to asses RSSI Value of a transmitter mobile node at multiple receivers. This technique differs from our proposed technique in such a manner that it uses probability distribution for distance calculation and uses a triangular density function and geometric correction technique in the localization procedure. An online path-loss parameter estimation approach is discussed in [36] and a variant of particle filter (RBPF-AGB) is used for position estimation of target node. In [37], the author has proposed handling LOS and NLOS cases separately using the corresponding path loss model to enhance indoor WiFi positioning accuracy.

Although most of the proposed systems avoid a pre-offline survey process, the crowd-sourcing activity requires considerable time for active or inactive user participation; additional sensors are needed to construct the database, or the environment map adds more complexity in calibration steps. As per our knowledge, the map and AP information are inevitable for location accuracy because the indoor architecture shapes radio propagation; therefore, to achieve a simple IPS and a certain level of accuracy, the map information should be considered. Triangular interpolation and extrapolation (TIX) [18] provides a 4–5 m accuracy without map information, whereas the signal-distance map (SDM) [19] working on the same principle improves the accuracy and is dependent on the location and number of APs in the environment.

3. Proposed Approach

As the indoor architecture of the environment shapes the RSSI heat map, the map information cannot be ignored. Maps are easily available in legally approved buildings. The map used in our approach is simple and can be constructed using a measuring tape and a simple bitmap drawing application such as “Microsoft Paint” (Microsoft Inc., Redmond, WA, USA). The other options include the use of automated maps generated from the 2D simultaneous localization and mapping (SLAM) [38]. Our approach consists of the following tasks: generation of a pixel map from the floor plan of the target site, where indoor positioning is required, the generation of an RSSI map from the pixel map using LOS and NLOS models for each AP, and finally, the estimation of the user location by applying the Overlap technique on generated RSSI maps of APs listed in RSSI vectors received at the target location. To complete the entire estimation task, we require three types of information: the bitmap (

M \times N

pixels) of building floor plane (at reasonable resolution, i.e., not very high to avoid image processing computation and not very low to preserve that environment architecture, e.g., 10 pixels/m), i.e., Equation (1); the list of “k” Wi-Fi APs installed, location on the map, and the Media Access Control(MAC) address.

V_{A P} = \{A P_{1}, A P_{2}, . . . A P_{n} . . ., A P_{k}\}

, where

A P_{n} = 〈M A C_{n}, x_{n}, y_{n}〉, n = 1, 2, 3 . . . k, x = 1, 2, . . ., M

and

y = 1, 2, . . ., N

; the received RSSI list

S_{R S S I} = = \{S_{1}, S_{2}, . . . . . ., S_{n},\}

, where

S_{i} = 〈M A C_{i}, l〉

and

n = 1, 2, 3 . . .

at the target location which includes the Mac address “

M A C_{i}

” and the RSSI level “l” of each AP in the range. For convenience, we have considered onlyx andy coordinates to address common average floor height buildings where thez-axis has no significant impact on RSSI calculation; however, in the case of high roof buildings, e.g., shopping malls, airports, etc., and the floor plan remains the same from floor to ceiling, the mounting height (z coordinate) of AP must be considered in RSSI estimation, as RSSI estimation depends on Euclidean distance from source to receiver. Otherwise, the proposed approach requires a 3D model of the environment, which is not commonly available, although it can be built easily using 3D modeling tools. We have described each task as follows.

3.1. Pixel Map Tracing

As mentioned earlier, the key component of our approach is the pixel map. In our experiment, we have created pixel maps from the floor plans of the subject buildings. This task includes the tracing of a picture and can be easily done using any image drawing tool. First, we resize the floor plan image to a resolution of 10 pixel/m. Then, we trace each concrete wall with white colored (RGB 255,255,255) lines and the wooden partitions with gray colored (RGB 128,128,128) lines on a black background (RGB 0, 0, 0). For simplicity, we consider only two types of walls; the color value is an adjustment factor for the wall attenuation factor (WAF) [13]. The adjustment factor must be carefully selected with respect to the thickness and material of the walls or obstructions. Finally, we obtain a gray-scale image map, Equation (1), with the information of the wall sizes, types, orientation, and location.Figure 2 shows the inputs and output of this pixel map generation task:

B (M, N) = [\begin{matrix} p x (1, 1) & p x (1, 2) & \dots & p x (1, N) \\ p x (2, 1) & ⋱ & ⋮ \\ ⋮ & p x (i, j) & ⋮ \\ p x (M, 1) & \dots & \dots & p x (M, N) \end{matrix}]

(1)

where

0 \leq p x_{(i, j)} \leq 255, i = 1, 2, 3, . . ., M

and

j = 1, 2, 3, . . ., N .

3.2. RSSI Map Generation

The second important task is to generate the RSSI Map of each selected AP for location estimation. To build an RSSI radio-map, we first divide the map into a grid of equal square blocks of 10 pixels/m. Next, we select a pixel vector from the center of a block (let (p,q)) to the AP (let (x,y)) using an improfile function that returns the intensity values of pixels along a straight line, i.e.,

V ((p, q), (x, y)) = i m p r o f i l e ((p, q), (x, y)) = \{p x (p, q), p x (p \pm 1, q \pm 1), . . . . . . . ., p x (x, y)\},

where

p x (p, q)

returns intensity values of pixels at location

(p, q), p = δ

2 δ

3 δ

, ...,M,

q = δ

2 δ

3 δ

, ...,N and

d e l t a

is the size of grid spacing, as shown inFigure 3a-(right). We call this pixel vector a profile vector. This profile vector enables us to differentiate between the LOS and NLOS scenarios, in order to determine the type and number of walls or obstructions in the path, and the length of the path as well. If all of the pixels in the profile vector are black, it indicates an LOS case; otherwise, it is NLOS. The white pixels in the profile vector indicate the number of walls in the path from the center of the block to the AP. Equation (2) describes the calculation of the path loss weight (PLW) from the profile vector by finding the peaks values in the pixel array of the profile vector usingGetPeakValues() that return local maxima and their count in given vectors. Next, the product of the PLW and WAF calculates the effective path loss (EPL), Equation (3), for NLOS radio signal propagation, where PLW represents the adjustment factor for walls in paths. The number of pixels in the profile vector is the absolute distance between the center of the reference block and the AP; however, to avoid diagonal error, we measure the Euclidean distance from the center of the block to the AP, as in Equation (4). Using this information and the RSSI prediction model, Equation (5), we calculate the RSSI for a particular block of the LOS or NLOS case.

P L W = \frac{\sum G e t P e a k V a l u e s (V ((p, q), (x, y)))}{255},

(2)

E P L = P L W \times W A F,

(3)

d_{((p, q), (x, y))} = \sqrt{{(p - x)}^{2} + {(q - y)}^{2}},

(4)

f (p, q) = p_{0} + 10 \times r \times l o g (\frac{d_{((p, q), (x, y))}}{10}) + E P L,

(5)

where WAF = 3.5,

p_{0}

= −30 dB and

r = \{\begin{matrix} 1, & P L W = 0, \\ 1.6, & P L W > 0, \end{matrix}

M (A P_{k}) = [\begin{matrix} f (δ, δ) & f (δ, 2 δ) & \dots & f (δ, n) \\ f (2 δ, δ) & ⋱ & ⋮ \\ ⋮ \\ f (m, δ) & \dots & \dots & f (m, n) \end{matrix}]

(6)

where

m = M / δ, n = N / δ

. To generate the RSSI path loss map, we repeat this process for all blocks and we get a

M (m, n)

matrix Equation (6) of the RSSI map of current AP. Algorithm 1 shows implementation details of Map Generation task.

Similarly, we generate an RSSI Map for each AP and store them in a list, i.e.,

E_{M} = \{M_{S_{1}}, M_{S_{2}}, M_{S_{3}}, . . ., M_{S_{i}}, . . ., M_{S_{k}}\}

, where

i = 1, 2, 3 . . . k

, and each

M_{S_{i}}

is a tuple of

〈m a c_{i}, M_{i}, l o c_{i}〉 = 〈M a c A d d r e s s, E s t i m a t e d r a d i o m a p, L o c a t i o n o f A P o n b i t m a p〉

. The RSSI map of each AP is tagged with its MAC address for later reference in position estimation procedure. A mesh plot of an estimated RSSI Map is shown inFigure 1.

RSSI Estimation Model

The location accuracy of our approach is completely dependent on the correctness of the RSSI map, whereas the correctness of the RSSI map depends on the accuracy of the RSSI prediction model selected for each point on the map. We have analyzed multiple RSSI path loss models and their accuracy with the respect to LOS and NLOS cases and selected soft partition and the concrete wall attenuation factor model [13,39].Figure 4 depicts the estimated and the real RSSI levels received, with respect to the distance, for the selected models. During the assessment of the RSSI path loss using the wall-map approach, we found that a couple of corrections were required in the estimation, as described in the following sections.

Correction I

Pixel line errors occur when the inclination angle of the profile vector with any wall in the map is very small, i.e., multiple pixels overlap over the wall, as shown inFigure 3c-(left). As the pixels in the profile vector indicate free space and the thickness of the obstruction, due to this overlap, an error is caused and the RSSI map appears more like a petal shape around the walls, as displayed inFigure 3b-(right). To mitigate the affect of the pixel line error, we count the peaks’ values in the path vector. The output of correction I is shown inFigure 3c-(right).

Correction II

To improve the RSSI map generation accuracy using the procedure described above, we compare our map with a real RSSI heat map, calculated manually by site survey, while recording the RSSI information at each crossing point, 1 m in the horizontal and vertical direction of the grid, as depicted inFigure 3d-(left). We found that the original heat map shows a corner diversion due to the dominant path [40], whereas in our RSSI map estimation, only the direct path was used. To incorporate such effects and to retain a low calculation complexity, we add two triangular paths to avoid the direct path error to a certain extent, as shown inFigure 3d-(right). Finally, we select a path with a minimum path loss, calculated by following each of the three paths. This correction is more useful if the building walking paths are rectangular and aligned with the map’sx- andy-axis.

Algorithm 1 Generate RSSI Map

1:: procedureGenRSSIMap
2:: INPUT:
3:: $M a p \leftarrow Path of Map file . bmp$
4:: $A P L o c \leftarrow Location of AP on Map (x, y)$
5:: $D e l t a \leftarrow Grid Block width δ$
6:: OUTPUT:
7:: $R S S I M a p \leftarrow RSSI Map of AP at location APLoc$
8:: BODY:
9:: $H e i g h t \leftarrow Height of Map$
10:: $W i d t h \leftarrow Width of Map$
11:: $G P o i n t \leftarrow Get_Grid_Points (Delta, Width, Height)$
12:: loop: Estimate RSSI for each point ’px’ in ’GPoint’
13:: $Vp 0 \leftarrow GetProfileVector (map, [{px}_{x}, {APLoc}_{x}], [{px}_{y}, {APLoc}_{y}])$
14:: if $lengthof (V p 0) = Delta$ then
15:: ${P e a k V a l u e s}_{V p 0} \leftarrow f i n d p e a k s (V p 0)$
16:: if $V p 0 i s n o t s t a r t i n g a t w a l l$ then
17:: $x 1 \leftarrow [{px}_{x}, {px}_{x}, {APLoc}_{x}]$
18:: $y 1 \leftarrow [{px}_{x}, {APLoc}_{y}, {APLoc}_{y}]$
19:: $V p 1 \leftarrow G e t P r o f i l e V e c t o r (m a p, x 1, y 1)$
20:: ${P e a k V a l u e s}_{V p 1} = f i n d p e a k s (V p 1)$
21:: $x 2 \leftarrow [{px}_{y}, {APLoc}_{x}, {APLoc}_{x}]$
22:: $y 2 \leftarrow [{px}_{y}, {px}_{y}, {APLoc}_{y}]$
23:: $V p 2 \leftarrow G e t P r o f i l e V e c t o r (m a p, x 2, y 2)$
24:: ${P e a k V a l u e s}_{V p 2} \leftarrow f i n d p e a k s (V p 2)$
25:: $P L W \leftarrow min (\sum ({P e a k V a l u e s}_{V p 0}), \sum ({P e a k V a l u e s}_{V p 1}), \sum ({P e a k V a l u e s}_{V p 3})$
26:: else $C a l c u l a t e d i r e c t p a t h$
27:: $P L W \leftarrow \sum ({P e a k V a l u e s}_{V p 0})$
28:: else
29:: $P L W \leftarrow 0$
30:: $p 0 \leftarrow - 30$
31:: $E P L \leftarrow 0$
32:: $W A F \leftarrow 3.5$
33:: $r \leftarrow 1;$
34:: if $PLW > 0$ then
35:: $r \leftarrow 1.6;$
36:: $E P L \leftarrow P L W / 255 \times W A F;$
37:: $d i \leftarrow \sqrt{(} {({px}_{x} - {APLoc}_{x})}^{2} + {({px}_{y} - {APLoc}_{y})}^{2})$
38:: $e s t R S S I \leftarrow (p 0 - 10 \times r \times l o g (d i / 10) - E P L)$
39:: $R S S I M a p ({px}_{x}, {px}_{y}) \leftarrow e s t R S S I$
40:: gotoloop.

3.3. User Location Estimation

The LOCALI location estimation is also an easy and interesting process. As an indoor environment is nonlinear, we cannot estimate the location using trilateration. This nonlinearity causes non-circular RSSI regions around the transmitter, and it is not possible to obtain an accurate estimation using the time or RSSI information directly. To estimate the user location, we propose a four-step procedure that includes selection, thresholding, intersection, and centroid finding.

Selection of APs for location estimation; for simplicity, we select the top three APs in the list with the strongest RSSI level.
For each AP, we generate a binary map by applying the threshold value of the RSSI level received from a particular AP on the corresponding RSSI Map. Let us assume that we have received a list $Z = (- 56, m a c_{A}), (- 70, m a c_{B}), (- 65, m a c_{C})$ . Each RSSI Map is an $m \times n$ matrix of RSSI levels and we mark a value of “1”, if the block has a 3 dB-difference value with the RSSI level received at the target, else it is “0”. This process gives us a binary map, as inFigure 5c. The same process applies for the remaining two selected APs, for the assessment of the RSSI map.
We now have three binary maps that depict the expected region around each AP, where a target can be located. Next, we perform a simple intersection operation between the three binary maps and obtain the common region for these maps; this gives us a region, where all the points have the same values, for the three selected APs, from the received RSSI list “Z”, at the target location.
Finally, the centroid of the common area gives us the estimated location of the target. The step-by-step implementation details of this task are listed in Algorithm 2.

Algorithm 2 Estimate Target Location

1:: procedureGetTargetLoc
2:: INPUT:
3:: $R S S I M a p s \leftarrow List of Maps “ E_{M} ”$
4:: $S_{R S S I} \leftarrow List of RSSI Values < (RSSI Level, MAC) > Received by Target$
5:: OUTPUT:
6:: $T a r g e t L o c \leftarrow (t_{x}, t_{y}) Location of Target$
7:: BODY:
8:: $A P L i s t \leftarrow Get Top Three APs with Highest RSSI Level from S_{R S S I}$
9:: $O R M a p \leftarrow RSSIMaps [0] \times 0$
10:: loop: Threshold RSSIMap for each AP in APList
11:: $map \leftarrow G e t R S S I M a p O f (A P . M A C, RSSIMaps)$
12:: $l e v e l \leftarrow A P . R S S I L e v e l$
13:: $t h M a p \leftarrow (m a p - l e v e l)$
14:: $b i n M a p \leftarrow (a b s (t h M a p) < 3)$
15:: $O R M a p \leftarrow ORMap | (b i n M a p)$
16:: gotoloop.
17:: $c o m R e g i o n \leftarrow G e t R e g i o n (O R M a p,^{'} C e n t r o i d^{'})$
18:: $T a r g e t L o c \leftarrow c o m R e g i o n . C e n t r o i d$

4. Experiment Setup

We have selected two types of environments for the experimentation and verification of our proposed approach: a hallway environment of 2160 m

^{2}

and an atrium building 1215 m

^{2}

, at the Yeungnam University, the 2nd floor of an IT Building and the 1st floor of an RIC Building, respectively.Figure 2a andFigure 4a show the floor plans of both the sites, respectively. The setting up of the LOCALI-based ILBS is a two-step process: the first is the creation of a map file server by calculating the RSSI map of each Wi-Fi AP permanently installed at the site. Next is the location estimation, using the overlap algorithm. The server is a simple Personal Computer (PC) with Intel Corei3 Processor and 8-GB RAM, running MATLAB (16a, MathWorks, Inc., Natek, MA, USA). We performed all the experiments in the hallway of an IT Building for calculating the parameters, “r” and “WAF”, and used the RIC Building for testing. The IT Building contains 21 APs and only 12 are selected, whereas, from the RIC Building, only seven are selected to participate in the position. To estimate the RSSI map for each selected AP, we selected a grid with

d e l t a

= 5 instead of

d e l t a

= 10, for radio-maps with slightly high resolution. To measure the positioning accuracy of the proposed technique, 54 reference points 1 m apart from each other are selected in the IT Building and 98 reference points are selected in a rectangular path around the opening between different floors of the RIC Building. Android and Apple-based hand-held devices are used for the RSSI calculation and as the target devices at each reference point marked on floor.

5. Results and Discussion

To estimate the position on each reference point on the map, instead of generating binary maps in the thresholding process, we consider absolute values at each grid point of the map, after subtracting the corresponding RSSI level received at the target for a particular AP. This gives us a mesh grid with a circular valley showing the expected location of the target around each AP, as shown inFigure 6a–c. Subsequently, we add all three of the maps and determine the deepest location in the combination map, as depicted inFigure 6d,e. This deepest location indicates the estimated location of the target. The difference between ground truth and estimated location are calculated by Euclidean distance between corresponding points on the bitmap.

InTable 1, we have compared our approach with some other similar or slightly similar model-based approaches. As the table shows, our approach is more practical and adoptable in nature, as it does not requires any active user input and special purpose hardware resources. The automatic assessment of LOS and NLOS and obstacle count (walls) is special to our approach, whereas some techniques employ a single model for LOS/NLOS cases. In addition, our technique does not use interpolation and gives more precise changes between LOS and NOLS cases. Active user input in [34] and hardware requirements of [35] make them less practical techniques due to limited mobile resources and user point of view. Moreover,Table 2 presents statistics regarding the time and memory consumption in our setup. The results demonstrate that our proposed technique sets up the IPS without a time-consuming effort and is ready to use within a few minutes. No significant resources in terms of the memory are required. The results inFigure 7 show the percentage of 2 m position accuracy achieved by the system, without the application of any optimization technique.

In the proposed technique, there are several aspects for improving the accuracy of the RSSI map estimation that are critical and need further exploration; e.g., the selection of the AP for position estimation, the location estimation procedure, and the optimization methods for enhancing the location accuracy. In this work, for simplicity, we selected three APs with the strongest RSSI levels as the target locations. The architecture of the environment around an AP also affects the RSSI levels because it is observed that the Wi-Fi signals add up to a stronger RSSI at the closed-end of the hallway. This effect causes certain nonlinear behavior in the real-time RSSI value for the LOS environment, compared to the estimated RSSI value and results as an error in position estimation at the close ends. Furthermore, the APs closer to the wall show stronger signals on opposite sides due to reflection of rays towards free space and cause free-space outliers, as highlighted inFigure 7. These effects are observed in closed-end corridors and atrium buildings, respectively. As our approach currently does not cover the reflection effect, this limitation can be overcome by placement of the APs at the center of rooms and closer to the ceiling. Moreover, it is observed that the user direction causes an almost 10-dB difference in the measurement at close proximity about three to six meters from transmitters in indoor environments, which is an error of almost 2 m.

6. Conclusions

In this study, we have presented a simple and effortless indoor positioning system that does not require any time-consuming calibration survey of the environment. The proposed technique exploits the floor plan information of the environment to build RSSI based path loss maps of a transmitting source more accurately, and these maps further help in estimating position of the targets in the environment by employing a map overlap technique. Results show that the proposed technique has achieved a reasonable accuracy without using any complex procedures and optimization techniques. Moreover, our next focus is to study how to incorporate dynamic changes in RSSI due to changes in environment over time, which will help in calculating more accurate path loss maps. In addition, fusion of inertial sensing data is planned to add more reliable tracking capabilities to the system. Increasing the accuracy of model-based path loss maps will minimize the outliers count, and, ultimately, a high accuracy in position estimation will be achieved while retaining a simple and affordable approach.

Acknowledgments

This work was supported by the ICT R&D program of the MSIP/IITP (Ministry of Science, ICT and Future Planing/Institute for Information and Communication Technology Promotion) (2017-0-00543, Development of Precise Positioning Technology for the Enhancement of Pedestrian’s Position/Spatial Cognition and Sports Competition Analysis), the 2017 Yeungnam University Research Grant and National Research Foundation (NRF)-2014R1A1A2055988.

Author Contributions

Muhammad Usman Ali and Yongwan Park conceived and developed the idea of database-less indoor positioning. Muhammad Usman Ali and Soojung Hur designed the procedures and processes to be carried out during experiments; Muhammad Usman Ali performed the experiments; Muhammad Usman Ali and Yongwan Park analyzed the data and results; and Muhammad Usman Ali wrote the paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

Ni, M.L.; Liu, Y.; Lau, Y.C.; Patil, A.P. LANDMARC: Indoor location sensing using active RFID.Wirel. Netw.2004,10, 701–710. [Google Scholar] [CrossRef]
Bahl, P.; Padmanabhan, V.N. RADAR: An in-building RF-based user location and tracking system. In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies, Tel Aviv, Israel, 26–30 March 2000. [Google Scholar]
Feldmann, S.; Kyamakya, K.; Zapater, A.; Lue, Z. An Indoor Bluetooth-Based Positioning System: Concept, Implementation and Experimental Evaluation. In Proceedings of the International Conference onWireless Networks, Las Vegas, NV, USA, 23–26 June 2003. [Google Scholar]
LaMarca, A.; Chawathe, Y.; Consolvo, S.; Hightower, J.; Smith, I. Place lab: Device positioning using radio beacons in the wild. In Proceedings of the International Conference on Pervasive Computing, Munich, Germany, 8–13 May 2005. [Google Scholar]
Mahfouz, M.R.; Zhang, C.; Merkl, B.C.; Kuhn, M.J.; Fathy, A.E. Investigation of high-accuracy indoor 3-D positioning using UWB technology.IEEE Trans. Microw. Theory Tech.2008,56, 1316–1330. [Google Scholar] [CrossRef]
Liu, H.; Darabi, H.; Banerjee, P.; Liu, J. Survey of wireless indoor positioning techniques and systems.IEEE Trans. Syst. Man Cybern. Part C2007,37, 1067–1080. [Google Scholar] [CrossRef]
Yoshino, M.; Haruyama, S.; Nakagawa, M. High-accuracy positioning system using visible LED lights and image sensor. In Proceedings of the 2008 IEEE Radio and Wireless Symposium, Orlando, FL, USA, 22–24 January 2008. [Google Scholar]
Se, S.; Lowe, D.G.; Little, J.J. Vision-based global localization and mapping for mobile robots.IEEE Trans. Robot.2005,21, 364–375. [Google Scholar] [CrossRef]
Mulloni, A.; Wagner, D.; Barakonyi, I. Indoor positioning and navigation with camera phones.IEEE Pervasive Comput.2009,8, 22–31. [Google Scholar] [CrossRef]
Chan, Y.T.; Ho, K.C. A simple and efficient estimator for hyperbolic location.IEEE Trans. Signal Process.1994,42, 1905–1915. [Google Scholar] [CrossRef]
A Python Implementation of Chan’s TDoA Algorithm for Ultrasonic Positioning and Tracking. Stock, V2-Lab Rotterdam. Available online:https://trac.v2.nl/export/6400/andres/Documentation/TDOA/Ultrasonic_Tracking.pdf (accessed on 15 March 2017).
Hossain, A.K.M.M.; Soh, W.-S. A survey of calibration-free indoor positioning systems.Comput. Commun.2015,66, 1–13. [Google Scholar] [CrossRef]
Seidel, S.Y.; Rappaport, T.S. 914 MHz path loss prediction models for indoor wireless communications in multifloored buildings.IEEE Trans. Antennas Propag.1992,40, 207–217. [Google Scholar] [CrossRef]
Husen, M.N.; Lee, S. Indoor Location Sensing with Invariant Wi-Fi Received Signal Strength Fingerprinting.Sensors2016,16, 1898. [Google Scholar] [CrossRef] [PubMed]
Kaemarungsi, K.; Krishnamurthy, P. Modeling of indoor positioning systems based on location fingerprinting. In Proceedings of the Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, Hong Kong, China, 7–11 March 2004. [Google Scholar]
Chung, J.; Donahoe, M.; Schmandt, C.; Razavai, P. Indoor location sensing using geo-magnetism. In Proceedings of the 9th International Conference on Mobile Systems, Applications, and Services, Bethesda, ML, USA, 28 June–1 July 2011. [Google Scholar]
Narzullaev, A.; Park, Y. Novel calibration algorithm for received signal strength based indoor real-time locating systems.AEU-Int. J. Electron. Commun.2013,67, 637–644. [Google Scholar] [CrossRef]
Gwon, Y.; Jain, R. Error characteristics and calibration-free techniques for wireless lan-based location estimation. In Proceedings of the 2nd ACM MobiWac, Philadelphia, PA, USA, 1 October 2004; pp. 2–9. [Google Scholar]
Lim, H.; Kung, L.-C.; Hou, J.C.; Luo, H. Zero-configuration indoor localization over IEEE 802.11 wireless infrastructure.Wirel. Netw.2010,16, 405–420. [Google Scholar] [CrossRef]
Yang, S.; Dessai, P.; Verma, M. FreeLoc: Calibration-free crowdsourced indoor localization. In Proceedings of the IEEE INFOCOM, Turin, Italy, 14–19 April 2013. [Google Scholar]
Chang, Q.; Li, Q.; Shi, Z.; Chen, W.; Wang, W. Scalable Indoor Localization via Mobile Crowdsourcing and Gaussian Process.Sensors2016,16, 381. [Google Scholar] [CrossRef] [PubMed]
Park, J.-G.; Charrow, B.; Curtis, D. Growing an organic indoor location system. In Proceedings of the 8th International Conference on Mobile Systems, Applications, and Services, San Francisco, CA, USA, 15–18 June 2010. [Google Scholar]
Chintalapudi, K.; Iyer, A.P.; Padmanabhan, V.N. Indoor localization without the pain. In Proceedings of the 16th Annual International Conference on Mobile Computing and Networking, Chicago, IL, USA, 20–24 September 2010. [Google Scholar]
Shen, G.; Zhuo, C.; Zhang, P. Walkie-Markie: Indoor pathway mapping made easy. In Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation, Lombard, IL, USA, 2–5 April 2013. [Google Scholar]
Rai, A.; Chintalapudi, K.K.; Padmanabhan, V.N.; Sen, R. Zee: Zero-effort crowdsourcing for indoor localization. In Proceedings of the 18th Annual International Conference on Mobile Computing and Networking, Istanbul, Turkey, 22–26 August 2012. [Google Scholar]
Zhou, B.; Li, Q.; Mao, Q. ALIMC: Activity landmark-based indoor mapping via crowdsourcing.IEEE Trans. Intell. Transp. Syst.2015,16, 2774–2785. [Google Scholar] [CrossRef]
Khoshelham, K.; Zlatanova, S. Sensors for Indoor Mapping and Navigation.Sensors2016,16, 655. [Google Scholar] [CrossRef] [PubMed]
Chen, Z.; Zou, H.; Jiang, H. Fusion of WiFi, smartphone sensors and landmarks using the Kalman filter for indoor localization.Sensors2015,15, 715–732. [Google Scholar] [CrossRef] [PubMed]
Hilsenbeck, S.; Bobko, D.; Schroth, G. Graph-based data fusion of pedometer and WiFi measurements for mobile indoor positioning. In Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing, Seattle, WA, USA, 13–17 September 2014. [Google Scholar]
Li, W.W.-L.; Iltis, R.A.; Win, M.Z. A smartphone localization algorithm using RSSI and inertial sensor measurement fusion. In Proceedings of the 2013 IEEE Global Communications Conference (GLOBECOM), Atlanta, GA, USA, 9–13 December 2013. [Google Scholar]
Deng, Z.-A.; Hu, Y.; Yu, J. Extended Kalman filter for real time indoor localization by fusing WiFi and smartphone inertial sensors.Micromachines2015,6, 523–543. [Google Scholar] [CrossRef]
Wu, C.; Yang, Z.; Liu, Y. WILL: Wireless indoor localization without site survey.IEEE Trans. Parallel Distrib. Syst.2013,24, 839–848. [Google Scholar]
Wang, H.; Sen, S.; Elgohary, A. No need to war-drive: Unsupervised indoor localization. In Proceedings of the 10th International Conference on Mobile Systems, Applications, and Services, Lake District, UK, 25–29 June 2012. [Google Scholar]
Jiao, J.; Li, F.; Deng, Z. A Smartphone Camera-Based Indoor Positioning Algorithm of Crowded Scenarios with the Assistance of Deep CNN.Sensors2017,17, 704. [Google Scholar] [CrossRef] [PubMed]
Knauth, S.; Ortega, A.A.B.; Dastageeri, H.; Griese, T.; Tran, Y.Towards Smart Watch Position Estimation Employing RSSI based Probability Maps; HFU: Furtwagen, Germany, 2014. [Google Scholar]
Bruno, L.; Addesso, P.; Restaino, R. Indoor positioning in wireless local area networks with online path-loss parameter estimation.Sci. World J.2014,2014, 986714. [Google Scholar] [CrossRef] [PubMed]
Bose, A.; Chuan, H.F. A practical path loss model for indoor WiFi positioning enhancement. In Proceedings of the 6th International Conference on the Information, Communications & Signal Processing, Singapore, 10–13 December 2007. [Google Scholar]
Santos, J.M.; Portugal, D.; Rocha, R.P. An evaluation of 2D SLAM techniques available in robot operating system. In Proceedings of the 2013 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR), Linkoping, Sweden, 21–26 October 2013. [Google Scholar]
Series, P.Propagation Data and Prediction Methods for the Planning of Indoor Radio Communication Systems and the Radio Local Area Networks in the Frequency Range 900 MHz to 100 GHz; ICU: Genève, Switzerland, 2012. [Google Scholar]
Wang, H.; Lenz, H.; Szabo, A. Enhancing the map usage for indoor location-aware systems. In Proceedings of the International Conference on Human-Computer Interaction, Beijing, China, 22–27 July 2007. [Google Scholar]

Figure 1. Site wall-map and the corresponding estimated radio-map, clearly showing the change in received signal strength indicator(RSSI) with respect to line-of-sight and non-line-of-sight cases; (a) site wall-map and (b) RSSI radio-map of an Access Point.

Figure 2. Input: (a) detailed floor plan of the Regional Innovation Center (RIC Building) and (b) corresponding output: Wall-map obtained from the pixel map tracing process.

Figure 3. Details of 2nd the task: Generation of the path loss radio-map for an AP and corrections made to improve the estimation of RSSI at particular point on the map. (a) Left: IT Building’s traced wall-map; Right: Vector from each grid point to an AP (for clarity, we used a 20 pixel/m resolution) (b) Left: Two types of profile vectors from an LOS Point and an NLOS point; Right: Flower-shaped radio map obtained without any correction; (c) Left: Pixel overlap of the profile vector with the wall; Right: Radio-map after the 1st correction (d) Left: Two rectangular paths, one direct from AP to the estimation point; Right: Radio-map after the 2nd correction and; (e) Left: Reference points to measure the actual RSSI map; Right: Real RSSI map of the environment obtained after linear interpolation.

Figure 4. (a) reference points to measure actual RSSI level received by a handheld device inside an office environment (IT Building) and (b) real and estimated RSSI with respect to distance for both LOS AP and NLOS AP cases.

Figure 5. Details of the 3rd task for target location estimation: (a) location of the selected APs with the strongest RSSI received by the target/user, on the map; (b) radio-map of each selected AP; (c) binary map obtained after applying the threshold value, depicting the expected region around an AP, where the target is located; and (d) intersection of the binary maps and location, considering the centroid of the common region.

Figure 6. Slightly different approach from the binary map for reducing the thresholding calculation: (a) expected target location of the lowest valley with respect to AP, A; (b) expected target location of the lowest valley with respect to AP, B; and (c) for AP, C; (d,e) combination of the RSSI valleys and deepest region of the expected target location.

Figure 7. (a) ground truth reference points of the RSSI received from user “circles” from one end of the corridor to the other and localization points of the user “Xs” estimated by the system, along a straight path of the IT Building; and (b) actual reference points of the user and estimated localized points around the open area of the RIC Building hallway; (c,d) median accuracy in meters and percentage less than 2 m accuracy with respect to number of scans taken at a reference point for the IT and RIC Buildings, respectively.

Table 1. Comparison with related techniques.

	Proposed	CBIPA [34]	Probability	Online	PPLM [37]
Props.	Technique		Maps [35]	PLPE [36]
LOS/NLOS Assessment	Automatic	No	No	No	Manual
Obstacle count	Yes	No	No	No	No
Coverage	Both	Both	LOS	LOS	Case Level
(LOS/NLOS)					(LOS or NLOS)
Positioning	Map	Turbo RSSI	Map	Particle	Trilateration
Algorithm	Overlapping	model	Overlapping	Filter
Active User Input	No	Yes	No	No	Yes
Interpolation	No	No	No	Yes	No
Special H/W Requirement	No	Yes(Camera)	Yes	No	No

Camera-Based Indoor Positioning Algorithm (CBIPA), Practical Path Loss Model (PPLM), Path Loss Parameter Estimation (PLPE), Line-of-sight (LOS), Non-line-of-sight (NLOS), Received Signal Strength Indicator (RSSI).

Table 2. Statistics of the change in the time and memory required on the disk for map generation with respect to the area and number of Access Points.

Building Type	Area (m²)	AP Count	delta (δ)	Time (s)	Maps File Size (Kb)
Hallway	20 × 54	21	5	1001	630
			10	267	172
Artium	27 × 45	07	5	360	240
			10	103	60

© 2017 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Ali, M.U.; Hur, S.; Park, Y. LOCALI: Calibration-Free Systematic Localization Approach for Indoor Positioning.Sensors2017,17, 1213. https://doi.org/10.3390/s17061213

AMA Style

Ali MU, Hur S, Park Y. LOCALI: Calibration-Free Systematic Localization Approach for Indoor Positioning.Sensors. 2017; 17(6):1213. https://doi.org/10.3390/s17061213

Chicago/Turabian Style

Ali, Muhammad Usman, Soojung Hur, and Yongwan Park. 2017. "LOCALI: Calibration-Free Systematic Localization Approach for Indoor Positioning"Sensors 17, no. 6: 1213. https://doi.org/10.3390/s17061213

APA Style

Ali, M. U., Hur, S., & Park, Y. (2017). LOCALI: Calibration-Free Systematic Localization Approach for Indoor Positioning.Sensors,17(6), 1213. https://doi.org/10.3390/s17061213

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further detailshere.

Article Metrics

Article Access Statistics

For more information on the journal statistics, clickhere.

Multiple requests from the same IP address are counted as one view.

Movatterモバイル変換

Article Menu

LOCALI: Calibration-Free Systematic Localization Approach for Indoor Positioning

Abstract

1. Introduction

2. Existing Systems

2.1. Interpolation-Based Systems

2.2. Crowdsourcing-Based Systems

2.3. Sensors-Based Systems

2.4. Model-Based Systems

3. Proposed Approach

3.1. Pixel Map Tracing

3.2. RSSI Map Generation

RSSI Estimation Model

Correction I

Correction II

3.3. User Location Estimation

4. Experiment Setup

5. Results and Discussion

6. Conclusions

Acknowledgments

Author Contributions

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI