Nothing Special   »   [go: up one dir, main page]
Next Article in Journal
Semantic-Enhanced Multi-Dimensional Markov Chains on Semantic Trajectories for Predicting Future Locations
Previous Article in Journal
Assessment of Fringe Pattern Decomposition with a Cross-Correlation Index for Phase Retrieval in Fringe Projection 3D Measurements
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Sensors
Volume 18
Issue 10
10.3390/s18103579
sensors-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Voronoi Diagram and Crowdsourcing-Based Radio Map Interpolation for GRNN Fingerprinting Localization Using WLAN

by
Yongliang Sun
1,*,
Yu He
2,
Weixiao Meng
3 and
Xinggan Zhang
4
1
School of Computer Science and Technology, Nanjing Tech University, Nanjing 211816, China
2
College of Electronic and Optical Engineering & College of Microelectronics, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
3
School of Electronics and Information Engineering, Harbin Institute of Technology, Harbin 150001, China
4
School of Electronic Science and Engineering, Nanjing University, Nanjing 210023, China
*
Author to whom correspondence should be addressed.
Sensors 2018, 18(10), 3579; https://doi.org/10.3390/s18103579
Submission received: 19 September 2018 / Revised: 14 October 2018 / Accepted: 17 October 2018 / Published: 22 October 2018
(This article belongs to the Section Sensor Networks)
Browse Figures
Figure 1
<p>Diagram of the proposed fingerprinting localization system.</p> "> Figure 2
<p>The basic structure of GRNN.</p> "> Figure 3
<p>Experimental floor plan.</p> "> Figure 4
<p>Experimental scenario of WLAN fingerprinting localization: (<b>a</b>) TP-LINK TL-WR845N AP; (<b>b</b>) 2-D code sticker on the ground; (<b>c</b>) Meizu M2 smartphone on a tripod.</p> "> Figure 5
<p>The partitioning result of the experimental environment using the Voronoi diagram.</p> "> Figure 6
<p>The locations of CPs, RPs, and IPs in the experimental environment.</p> "> Figure 7
<p>Localization results of one trajectory computed by the KNN and GRNN algorithms.</p> "> Figure 8
<p>Cumulative probabilities of localization errors computed by different fingerprinting algorithms using the fused radio map.</p> ">
Versions Notes

Abstract

:
In the last decade, fingerprinting localization using wireless local area network (WLAN) has been paid lots of attention. However, this method needs to establish a database called radio map in the off-line stage, which is a labor-intensive and time-consuming process. To save the radio map establishment cost and improve localization performance, in this paper, we first propose a Voronoi diagram and crowdsourcing-based radio map interpolation method. The interpolation method optimizes propagation model parameters for each Voronoi cell using the received signal strength (RSS) and location coordinates of crowdsourcing points and estimates the RSS samples of interpolation points with the optimized propagation model parameters to establish a new radio map. Then a general regression neural network (GRNN) is employed to fuse the new and original radio maps established through interpolation and manual operation, respectively, and also used as a fingerprinting localization algorithm to compute localization coordinates. The experimental results demonstrate that our proposed GRNN fingerprinting localization system with the fused radio map is able to considerably improve the localization performance.

1. Introduction

With the rapid development of information technology, especially the emergence of electronic maps, location-based service (LBS) has been one of current research hot-spots and has been applied to various aspects of people’s daily life, bringing great convenience to people [1]. As a core technology of LBS, localization technology has attracted more and more concerns. Meanwhile, the increasing demands for LBS have prompted the vigorous development of localization technology [2,3]. In outdoor environments, global navigation satellite system (GNSS) plays a vital role in high precision localization, navigation, timing and so on [4]. To offer satisfactory LBS in indoor environments, such as airports, museums, shopping malls, and underground car parks, many technologies have been applied to indoor localization like infrared, ultrasound, ZigBee, ultra-wide band (UWB), radio frequency identification (RFID), inertial sensors, and wireless local area network (WLAN) [2,5,6,7]. Considering the establishment cost and localization performance, WLAN fingerprinting localization has been favored among the existing indoor localization techniques.
The basic WLAN fingerprinting localization method consists of two stages: the off-line and on-line stages [8]. In the off-line stage, several specific locations called reference points (PRs) in the target region are selected. The location coordinates are recorded and received signal strength (RSS) samples are measured at each RP by professional technicians, and then these data are compiled into a database, namely radio map. In the on-line stage, when an RSS sample is measured by a user’s mobile device, localization results can be computed by a fingerprinting localization algorithm. The fingerprinting localization algorithms can be generally categorized into two classes: similarity measurement-based and machine learning-based algorithms. The similarity measurement-based algorithms, for example, K nearest neighbors (KNN) and weighted KNN (WKNN) [9], first measure the similarities between the RSS samples of RPs in the radio map and measured RSS sample in the on-line stage and then estimate the location coordinates of the user with the location coordinates of RPs. Machine learning-based fingerprinting algorithms, such as fuzzy logic, multi-layer perceptron (MLP), and support vector regression (SVR) [8,9,10], calculate localization results with a nonlinear function, which is trained in the off-line stage with the radio map. In this paper, we utilize a general regression neural network (GRNN) to fuse different radio maps and also use it as the fingerprinting algorithm because of its superior performance for function approximation.
However, one disadvantage of the fingerprinting localization method is that the process of establishing the radio map is labor-intensive and time-consuming [11]. Furthermore, the changes of building structure and furniture as well as human movement may cause RSS variations. Consequently, the established radio map needs to be updated at intervals, but the burden of updating the radio map continuously with the professional technicians’ manual operation is difficult to bear. A concept called crowdsourcing has been proposed and then applied to radio map establishment, in which common users, namely crowdsourcing participants, take mobile devices that are able to sense and compute, as well as collectively share, the measured location-labeled RSS data in a participatory manner [12]. Therefore, crowdsourcing has been considered as a solution to the radio map establishment and update of WLAN fingerprinting localization for saving the labor and time cost. The establishment of radio maps through crowdsourcing usually needs a large number of RSS data collected by crowdsourcing participants to calculate an accurate localization result [13].
In this paper, we also apply crowdsourcing to radio map establishment. In the target region, we select a few locations as crowdsourcing points (CPs) and attach two-dimensional (2-D) code stickers at these CPs on the ground. These 2-D code stickers are near the toilet, elevator, and exits, where it is convenient for the crowdsourcing participants to obtain the location coordinates of CPs through scanning these 2-D code stickers. Thus, the crowdsourcing participants are able to collect the RSS data and location coordinates of these CPs and then upload these location-labeled RSS data to a localization server for radio map establishment through interpolation. Using a Voronoi diagram, the target region can be partitioned into Voronoi cells according to the locations of CPs and the propagation model parameters are optimized with crowdsourcing data in each cell so that more accurate RSS data can be estimated. In this way, the proposed Voronoi diagram and crowdsourcing-based radio map interpolation method reduces the labor and time cost for radio map establishment greatly compared with the traditional radio map establishment method using manual operation. To the best of our knowledge, little literature has combined Voronoi diagram and crowdsourcing for radio map establishment.
In this paper, we propose a Voronoi diagram and crowdsourcing-based radio map interpolation method for GRNN fingerprinting localization using WLAN to offer accurate localization results for users in indoor environments. Although the disadvantage of this work is that it is based on a basic fingerprinting localization system with an original radio map, it not only needs no extensive time and labor cost to establish a new radio map, but also achieves a comparable localization performance. The main contributions of this paper can be summarized as follows:
  • We propose an interpolation method for radio map establishment based on a Voronoi diagram and crowdsourcing. The method first partitions the target region into Voronoi cells according to the locations of CPs using a Voronoi diagram. The propagation model parameters in each Voronoi cell are optimized with the RSS data and location coordinates of CPs. Then the RSS data of selected interpolation points (IPs) in each Voronoi cell are estimated with the optimized propagation model parameters and are calibrated according to the RSS data of CPs. So a new radio map can be established through the proposed interpolation method.
  • We propose a GRNN-based fingerprinting localization algorithm, which fuses the two radio maps, consisting of the RSS data and location coordinates of the RPs and IPs, respectively. Then a nonlinear function between the RSS data and location coordinates is approximated by the GRNN using the fused radio map. In the on-line stage, the nonlinear function is used to compute the localization coordinates.
  • We verify the proposed localization system with the RSS data and location coordinates collected from a real indoor environment. The experimental results show that our proposed Voronoi diagram and crowdsourcing-based radio map interpolation method for GRNN fingerprinting localization system is effective in saving radio map establishment cost and improving localization performance.
The remainder of this paper is organized as follows: Section 2 introduces related works including radio map establishment methods and fingerprinting localization algorithms. In Section 3, we first describe the overview of the proposed WLAN fingerprinting localization system, then we discuss the key components of the proposed fingerprinting localization system, which are Voronoi diagram-based region partition, propagation model optimization for interpolation, RSS calibration and GRNN fingerprinting algorithm. Section 4 presents the experimental setup, results, and analyses. Finally, the conclusions and future work are given in Section 5.

2. Related Works

2.1. Radio Map Establishment Methods

One of the key components of WLAN fingerprinting localization is to establish the radio map, so people have paid great attention on it. Currently, most of the research on radio map establishment is based on crowdsourcing. P. Bolliger [14] first proposed that location-labeled RSS data could be collected using an electronic map. Then crowdsourcing-based radio map establishment methods using electronic maps were also presented in Ref. [15,16]. C. Wu et al. [17] measured RSS data and trajectories of crowdsourcing participants and matched these RSS data with trajectories using multidimensional scaling for radio map establishment. Additionally, P. Mirowski et al. [18] proposed that crowdsourcing participants could obtain location coordinates for RSS data through scanning the 2-D code labels deployed in the experimental region. In Ref. [19], location information could be measured near building entrances and windows using global positioning system (GPS) and then used to label the collected RSS data. S. Jung and D. Han [20] proposed a radio map establishment and maintenance system using cowdsourced RSS data collected from numerous mobile devices. The system exploited an unsupervised learning algorithm to establish an initial radio map. Then the radio map was adapted according to the RSS variations through crowdsourcing. L. Ma et al. [21] obtained location information of RSS data using crowdsourcing pedestrian dead reckoning (PDR) trajectories for radio map establishment. They transformed the locations in PDR trajectories from relative ones to absolute ones through trajectory matching using Hough transform and Harris corner detection. N. Yu et al. [22] exploited crowdsourcing RSS data to identify the indoor doors that were regarded as reference locations. Then the representative fingerprints were extracted and linked to their corresponding physical locations with the reference locations and RSS similarities. In this way, a radio map could be established.
In addition to the above-mentioned crowdsourcing method for radio map establishment, other radio map establishment methods have also been proposed. J. Yin et al. [23] reconstructed a radio map by using real-time RSS data at RPs. They took real-time RSS values at each time point into account and utilized the dependency between the estimated locations and RPs. H. Wang et al. [24] proposed a dynamic radio map establishment method for WLAN fingerprinting localization. In the off-line stage, the relationship between RSS data of calibration points and RPs was established by an MLP. In the on-line stage, the real-time RSS values at RPs were predicted based on the RSS data collected at calibration points. C. Zhou and Y. Gu presented a joint method of indoor localization and radio map establishment in Ref. [25]. They exploited the inherent spatial correlation of RSS measurements to reduce the calibrating RSS data and perform localization without a full radio map. The accumulation of localization information could be jointly used to establish the radio map. In Ref. [26], H. Zhao et al. considered the comprehensive features of RSS data by adopting universal Kriging method and region partitioning. Naive Bayes classifier and WKNN were used to work with the interpolated radio map. M. Lee and D. Han [27] proposed an interpolation method based on a Voronoi diagram. The method refined the propagation model of each cell for RSS estimation considering the signal fading caused by walls. Compared with their method, through using crowdsourcing, we partition the experimental environment according to the locations of CPs. The estimated RSS data can be updated according to the RSS variations in the indoor environment and the Voronoi cells can be easily adapted according to the locations of CPs.

2.2. Fingerprinting Localization Algorithms

Fingerprinting localization algorithm is essential to WLAN fingerprinting localization. Besides the fingerprinting algorithms referred to above, like the similarity measurement-based algorithms KNN and WKNN, fingerprinting algorithms based on cosine similarity [28] and Pearson correlation coefficient [29] also measure the similarities between the RSS samples stored in the radio map and those collected in the on-line stage. Then these algorithms compute localization results according to selected RP location coordinates whose RSS samples are similar to those collected in the on-line stage. The drawbacks of the similarity measurement-based algorithms are not only the localization performance can be influenced by the RP density and distribution, but also the algorithms suffer high computation complexity if the radio map has a large number of RPs. Regarding the machine learning-based fingerprinting algorithms, machine learning algorithms like radial basis function (RBF) neural network [30] and adaptive neuro-fuzzy inference system (ANFIS) [31] could also be used as fingerprinting algorithms. In the off-line stage, these fingerprinting algorithms are trained with the radio map to approximate to a nonlinear function between RSS data and location coordinates. In the on-line stage, when a mobile device measures an RSS sample, the RSS sample is inputted into the trained nonlinear function and then location coordinates of the mobile device can be estimated with the nonlinear function.
In recent years, many advanced fingerprinting localization algorithms have been proposed. J. Talvitie et al. [32] proposed an RSS-based indoor localization method using RSS images and compressed spectral analysis. The method was able to considerably reduce the size of the radio map only by storing the most significant coefficients from discrete cosine transformed images. An efficient and accurate localization method called Tilejunction was proposed in Ref. [33]. The method mapped the user RSS data of each access point (AP) to a convex hull termed signal “tile”. Then it used a linear programming method to locate the user at the junction of the tiles. X. Wang et al. [34] presented a deep learning-based indoor fingerprinting localization system using channel state information. In the off-line stage, deep learning was utilized to train all the weights of a deep network. In the on-line stage, a probabilistic method was used to compute the location. K. Chen et al. [35] presented a fingerprinting method called Slide that could achieve automatic mapping from the RSS data to the locations on a line. The method also acquired the locations after each WLAN channel scanning to mitigate the misalignment problem. In Ref. [36], an indoor localization system using WLAN named HybLoc was proposed. The system utilized Gaussian mixture model-based soft clustering and random decision forest for localization.
In short, fingerprinting localization can be formulated as a regression problem that is to predict location coordinates with RSS data using an approximated nonlinear function. Because GRNN has a superior regression performance and appropriate noise attenuation performance, which is usually used for function approximation [37], we apply a GRNN as the fingerprinting algorithm in this paper to compute localization coordinates.

3. Proposed Localization System

3.1. System Overview

As the basic fingerprinting localization system, our proposed localization system can also be generally divided into two stages: the off-line stage and on-line stage, which is shown in Figure 1. We apply crowdsourcing to the fingerprinting localization system so that the established radio map through interpolation method can be updated continuously according to the RSS variations in the indoor environment.
In the off-line stage, we also establish a radio map with the RSS data and location coordinates of RPs in the indoor environment, which we consider the original radio map. We select a few extra locations as the CPs and attach 2-D code stickers with location information printed on them, so that the crowdsourcing participants can scan and obtain the location coordinates to label the RSS data measured at these CPs. We exploit the Voronoi diagram to partition the indoor environment into small Voronoi cells. In each Voronoi cell, there is only one CP and the RSS data and location coordinates of the CP are used for optimizing propagation model parameters. We compute the mean value of each propagation model parameter for interpolation. After the locations of IPs are determined around the CP and RPs in the Voronoi cell, the RSS values of different APs are estimated for the IPs with the optimized propagation model parameters and then calibrated with the RSS data of the CP. When the computation and calibration of RSS data at all the IPs are finished, a new radio map is established through interpolation. Then, we utilize a GRNN to fuse the two radio maps and approximate to a nonlinear function F : ℝ J → ℝ 2 between the RSS data and location coordinates. We take the off-line RSS data R S S i = { R S S i , 1 , R S S i , 2 , ⋯ , R S S i , J } , i ∈ { 1 , 2 , ⋯ , I } as the inputs of the GRNN and the corresponding location coordinates L i = ( x i , y i ) , i ∈ { 1 , 2 , ⋯ , I } as its outputs, where I and J denote the numbers of training samples and deployed APs, respectively.
In the on-line stage, when the user takes a mobile device and measures an on-line RSS sample r s s = { r s s 1 , r s s 2 , ⋯ , r s s J } , the on-line RSS sample is inputted into the GRNN. Then localization coordinates   l ^   = ( x ^ , y ^ ) can be computed by   l ^   = F ( r s s ) . This stage of the proposed localization system is the same as the basic fingerprinting localization system.

3.2. Voronoi Diagram-Based Region Partition

A Voronoi diagram is also known as a Thiessen polygon or Dirichlet tessellation, which offers an effective solution for partitioning a plane into a few regions [38]. It has been used in various fields like local coverage optimization of wireless sensor network [39], interferometric synthetic aperture radar (InSAR) fine registration [40], and optimal allocation of dynamic reactive power sources [41]. The general idea of the Voronoi diagram is to partition the plane into regions according to the locations of a set of sites. Each region is called a Voronoi cell and usually there is one site in each Voronoi cell. Any other points in the cell is closer to the corresponding site in the same cell than to other sites. Based on Delaunay triangulation, the perpendicular bisectors for each Delaunay line can be determined, which can intersect at an endpoint called Voronoi vertex. The line segments between Voronoi vertexes are the Voronoi edges and the convex polygon region surrounded by the Voronoi edges is the Voronoi cell.
We take the CPs as the sites and let ξ = { c ( 1 ) , c ( 2 ) , ⋯ , c ( K ) } denote the set of CP locations in the experimental environment ℝ 2 , where c ( k ) = ( x CP ( k ) , y CP ( k ) ) , k ∈ { 1 , 2 , ⋯ K } , and r ( l ) = ( x IP ( l ) , y IP ( l ) ) denote the location coordinate vector of l th IP. The l th IP in the experimental environment whose distance to k th CP c ( k ) are less than or equal to the distances to other CPs c ( i ) , i ≠ k , is in the k th Voronoi cell V k , then the k th Voronoi cell V k can be denoted as follows:
V k = { r ( l ) ∈ ℝ 2 | d ( k , l ) ≤ d ( i , l ) , ∀ c ( i ) ∈ ξ , i ≠ k }  
where, d ( k , l ) and d ( i , l ) denote the Euclidean distances between k th CP and l th IP and between i th CP and l th IP, respectively, which can be calculated by:
d ( k , l ) = ( x CP ( k ) − x IP ( l ) ) 2 + ( y CP ( k ) − y IP ( l ) ) 2  
d ( i , l ) = ( x CP ( i ) − x IP ( l ) ) 2 + ( y CP ( i ) − y IP ( l ) ) 2  

3.3. Propagation Model Optimization for Interpolation

As we know, because wireless signal attenuates with the increasing propagation distance, RSS data measured in indoor environments are spatially related. When we partition the indoor experimental environment into several Voronoi cells according to the locations of CPs, the RSS data collected in the same Voronoi cell usually have the similar RSS characteristics. This is because the wireless links between the APs and locations in the same Voronoi cell could be influenced by the same factors, such as the building structure, furniture, and presence of humans.
Thus, we optimize propagation model parameters with the known location-labeled RSS data of the CP and calculate the RSS data with the optimized propagation model parameters for the IPs in the same Voronoi cell. In this paper, we adopt a common propagation model [42] to estimate the RSS data for the IPs. The propagation model is denoted as follows:
P Total = P AP − P Dev = 20 log 10 f + N log 10 d − X  
where, P Total denotes the total path loss between an AP and mobile device, P AP denotes the power transmitted by the AP that can be derived from AP configurations, P Dev denotes the received power that can be derived from the RSS data measured by the mobile device, f denotes the frequency, d denotes the distance between the AP and mobile device, and both N and X denote the propagation model parameters that are usually set equal to 30 and 28 at a frequency of 2.4 GHz in office environments, respectively. These two parameters, N and X , are the propagation model parameters we need to optimize with the crowdsourcing data in each Voronoi cell.
We let P AP ( j ) and P Dev ( j , k ) denote the transmitted power of j th AP and received power at k th CP by the device from j th AP, respectively, d ( j , k ) denote the distance between j th AP and k th CP, and N ( j , k ) and X ( j , k ) denote the propagation model parameters between j th AP and k th CP. Then the total path loss between j th AP and k th CP can be computed by P Total ( j , k ) = P AP ( j ) − P Dev ( j , k ) and we can have (5) as follows:
P Total ( j , k ) = 20 log 10 f + N ( j , k ) log 10 d ( j , k ) − X ( j , k )  
The distance d ( j , k ) between j th AP and k th CP can be estimated with the propagation model denoted by:
d ( j , k ) = 10 P Total ( j , k ) − 20 log 10 f + X ( j , k ) N ( j , k )  
Because the location coordinates of the APs and CPs are known, the real distance between each AP and CP can be computed. We let a ( j ) = ( x AP ( j ) , y AP ( j ) ) and c ( k ) = ( x CP ( k ) , y CP ( k ) ) denote the known location coordinates of j th AP and k th CP, respectively, so the real distance d Real ( j , k ) between j th AP and k th CP can be calculated by (2) or (3). Then the absolute value of the distance difference between the estimated and real distances is calculated by:
| Δ d ( j , k ) | = | d ( j , k ) − d Real ( j , k ) |  
The propagation model parameters N ( j , k ) and X ( j , k ) are optimized to minimize | Δ d ( j , k ) | calculated by (7). The process of searching the optimized parameters N ^ ( j , k ) and X ^ ( j , k ) can be formulated as an unconstrained nonlinear programming problem denoted by:
( N ^ ( j , k ) , X ^ ( j , k ) ) = arg min ( N ( j , k ) , X ( j , k ) ) | 10 P Total ( j , k ) − 20 log 10 f + X ( j , k ) N ( j , k ) − d Real ( j , k ) |  
In this paper, the initial values of the propagation model parameters N ( j , k ) and X ( j , k ) are set equal to 30 and 28, respectively. We adopt Nelder-Mead simplex algorithm [43] for the parameter optimization. In each Voronoi cell, multiple RSS samples collected from different APs are used to optimize the two propagation model parameters. So multiple optimized parameters can be obtained. We calculate the mean values of the two parameters and utilize the mean values to predict the RSS data at IPs.

3.4. RSS Calibration and GRNN Fingerprinting Localization Algorithm

3.4.1. RSS Calibration

Due to the blockage of walls, doors, furniture and so on, the wireless signals from some APs at some locations may be so weak that they cannot be detected by mobile devices, which causes the corresponding RSS values are unavailable and equal to 0 in the mobile devices. When we estimated RSS values with the optimized propagation model parameters, few estimated RSS values at the IPs are 0. Thus, we need to calibrate the estimated RSS data according to the RSS data of CPs measured in the real environment. For example, if all the RSS values from j th AP at k th CP are 0, which means j th AP cannot be detected by the mobile device at k th CP, then we need to calibrate the j th vector of the RSS samples estimated with the optimized propagation model parameters in k th Voronoi cell. We find such RSS vector using the mean value of the RSS vector rss ¯ j , k of k th CP from j th AP, which can be computed by:
r ¯ s ¯ s ¯ j , k = ∑ i = 1 I r s s i , j , k  
where, I denotes the number of RSS values from j th AP measured at k th CP. If the RSS mean value rss ¯ j , k is equal to 0, then we can calibrate the RSS values estimated with the optimized propagation model parameters of j th AP in k th Voronoi cell and set them equal to 0. So these estimated RSS samples can be more similar with the ones measured in the real environment.

3.4.2. GRNN Fingerprinting Localization Algorithm

After the RSS calibration, the estimated RSS data, along with the location coordinates of all the IPs, can be compiled into a new radio map. Because GRNN does not need iterative training like the MLP trained by back propagation (BP) algorithm and it has a superior regression performance to MLP or RBF network [44], we use a GRNN to fuse the new radio map established through interpolation and the original radio map that consists of the location-labeled RSS data of RPs and then to approximate a nonlinear function between RSS data and location coordinates. A basic GRNN structure is shown in Figure 2. The GRNN consists of four layers that are the input layer, pattern layer, summation layer, and output layer. In addition, after we obtain the nonlinear function F using the GRNN, the localization coordinates can be calculated in the on-line stage.
As shown in Figure 2, we let ζ = { x i , y i , i = 1 , 2 , ⋯ , I } denote the training data set, x = { x 1 , x 2 , ⋯ , x M } denote the input vector, and   y ^   = { y ^ 1 , y ^ 2 , ⋯ , y ^ N } denote the desired output vector, which can be the fused radio map, an on-line RSS sample measured by a mobile device, and localization coordinates in this paper, respectively. In the input layer, the number of neurons is the same as the number of inputs of the GRNN and all the neurons in the input layer are connected with the neurons in the pattern layer. In the pattern layer, a Gaussian function is used and denoted by:
{ g i = exp [ − D i 2 2 σ 2 ] D i 2 = ( x − x i ) T ( x − x i )  
where, σ denotes a smoothing parameter that can be obtained through cross validation in the off-line stage and D i 2 denotes the squared distance between x and x i .
In the summation layer, there are two kinds of neurons. One kind of neuron calculates the weighted sum S W n , n = 1 , 2 , ⋯ , N of the outputs in the pattern layer; the other kind of neuron calculates the sum S of the pattern layer outputs. So we can compute the n th element of the desired output vector as follows:
{ y ^ n = S W n S S W n = ∑ i = 1 I y i , n g i S = ∑ i = 1 I g i  
where, y ^ n and y i , n , n = 1 , 2 , ⋯ , N denote n th elements of the output vectors y ^ and y i , respectively. Thus, when a user measures an RSS sample and inputs it into the GRNN in the on-line stage, the localization coordinates can be computed.

4. Experimental Setup, Results, and Analyses

4.1. Experimental Setup

In this paper, we collected all the experimental data from a real office environment. The experimental environment was a rectangular region with dimensions of 51.6 m × 20.4 m, as shown in Figure 3. A total of 7 TP-LINK TL-WR845N (TP-LINK Co., Ltd., Shenzhen, China) APs were mounted in the experimental environment at a height of 2.2 m to offer wireless communication service, as shown in Figure 4a. Because the office rooms might not be free to enter for the crowdsourcing participants to collect RSS data, we selected 10 specific locations as CPs only in the corridor, which were marked with the blue points in Figure 3. We labeled the 10 CPs with 2-D code stickers on the ground of the corridor, as shown in Figure 4b, so that the crowdsourcing participants could scan the 2-D codes on the stickers and obtain the location coordinates of the CPs. Because we assumed that the crowdsourcing participants collected the RSS data and location coordinates of the CPs in a voluntary manner, the time for the crowdsourcing participants to collect these data must be less than one minute [45], and only 60 RSS samples were collected at each CP. We selected 92 RPs in the corridor and Room 620, and then collected 120 RSS samples at each RP. To test the proposed fingerprinting localization system, a trajectory consisting of 90 testing points (TPs) with 0.6 m gaps were selected from the end of the corridor near the elevator to Room 620 in order to simulate a person walking along the trajectory in the experimental environment. A total of 5400 RSS samples were collected along the trajectory to test the system. All the RSS data were measured by a Meizu M2 (Meizu Technology Co., Ltd., Zhuhai, China) smartphone that was placed on a tripod at a height of 1.2 m, as shown in Figure 4c. This smartphone was installed with our self-developed Android application software, the sampling rate of which was 1 RSS sample per second.

4.2. Experimental Results and Analyses

As mentioned above, we selected 10 CPs in the experimental environment, so the experimental environment is partitioned into 10 regions with a Voronoi diagram according to the locations of the CPs, with each region being a Voronoi cell. The partitioning result is shown in Figure 5, below. Because all of the CPs are in the corridor, most of the Voronoi cells in the straight corridor can be the standard rectangles, and it is easy for us to select the locations of IPs. In each Voronoi cell, we exploit the RSS data and location coordinates of CP to optimize the propagation model parameters between the CP and each AP.
Then we select 128 specific locations in the experimental environment as IPs and estimate RSS data for these IPs. These IPs are around the RPs and CPs, and the locations of the CPs, RPs, and IP are shown in Figure 6. Specifically, the 128 IPs are distributed in the corridor and Room 620 like the RPs. We estimate the RSS data of different APs for these IPs with the optimized propagation model parameters in each Voronoi cell. Due to the influence of the experimental environment, before we compile these estimated RSS data into a new radio map for localization, we need to calibrate the estimated RSS data for IPs with the RSS data of the CP in the same Voronoi cell that can be collected in the real environment by crowdsourcing participants.
We first take one trajectory as an example, the localization results with the fused radio map computed by the traditional KNN and proposed GRNN algorithms are shown in Figure 7. In the experiment, we select the 7 nearest RPs for the KNN to compute localization coordinates and utilize 4-fold cross validation for the GRNN to optimize the smoothing parameter σ in the off-line stage. The mean errors of the localization results computed by the KNN and GRNN are 3.57 m and 2.63 m, respectively. As shown in Figure 7, the localization results computed by the GRNN algorithm are more continuous than those computed by the KNN algorithm. Although the localization results of the KNN algorithm are near to the true trajectory in the middle segment of the corridor, the localization results of the KNN algorithm deviate from the real locations of TPs greatly in the region near Room 620. Some of these localization results even reach to the toilet and the stairs.
We also compute the localization results using all the RSS data at TPs and the fused radio map, and then compare the localization performance of the fingerprinting algorithms KNN, WKNN, MLP, and our proposed GRNN. We set the same parameters for the KNN, WKNN, and GRNN as in the simple trajectory experiment. Regarding the MLP we utilize, it is trained by the BP algorithm in the off-line stage. The numbers of neurons in the input layer, hidden layer, and output layer of the MLP are 7, 40, and 2, respectively. The number of iterative epochs is set to be equal to 10,000. Meanwhile, Sigmoid function and linear function are selected as the activation functions for the hidden layer and output layer of the MLP, respectively.
The localization results are listed in Table 1. The mean errors of localization results computed by the fingerprinting algorithms KNN, WKNN, MLP and GRNN with the fused radio map are 3.29 m, 3.27 m, 3.75 m and 2.78 m, respectively. The cumulative probabilities of the KNN, WKNN, MLP and GRNN within a localization error of 3 m are 64.3%, 64.1%, 42.0% and 66.4%, respectively. The cumulative probabilities of the KNN, WKNN, MLP and GRNN within a localization error of 4 m are 74.3%, 74.7%, 58.2% and 80.4%, respectively. We also test the KNN algorithm using the original radio map that only consists of the RSS data and location coordinates of RPs. The mean error of the KNN using the original radio map is 4.20 m. Obviously, the localization results using the fused radio map are more accurate than those computed using the original radio map. The cumulative probability curves of the KNN, WKNN, MLP and GRNN fingerprinting algorithms are shown in Figure 8. In Figure 8, the cumulative probabilities of the GRNN algorithm within a localization error of 2 m are a little lower than those of the KNN and WKNN algorithms, but larger localization errors are computed by the KNN and WKNN. Generally, the proposed GRNN fingerprinting algorithm outperforms the other three fingerprinting algorithms.

5. Conclusions and Future Work

In this paper, we propose a WLAN fingerprinting localization system, which is not only able to save labor and time cost for radio map establishment, but also achieves a comparable localization performance. In the off-line stage, we exploit the Voronoi diagram and crowdsourcing to establish a new radio map through interpolation. We first partition the experimental environment into Voronoi cells using the Voronoi diagram according to the locations of CPs, and then optimize the propagation model parameters with the CP data, so that the estimated RSS data using optimized propagation model parameters after RSS calibration will be more similar to the RSS data measured in the real environment. Because the radio map is established based on crowdsourcing data collected by crowdsourcing participants, it can be easily updated according to the RSS variations in the indoor environment. Owing to the superior performance of GRNN for function approximation, we use a GRNN as a fingerprinting algorithm to fuse the new radio map established through interpolation and the original radio map and to approximate to a nonlinear function between RSS data and location coordinates. Then localization coordinates can be computed using the nonlinear function in the on-line stage. The experimental results show that our proposed fingerprinting localization system can reduce the mean error of localization results to 2.78 m with the crowdsourcing data collected at only a few CPs, which proves the effectiveness of the proposed system. We expect that the proposed system could offer a valuable reference for WLAN fingerprinting localization and promote the theoretical research and practical application of WLAN fingerprinting localization to some degree.
In the future, we intend to continue the work on radio map interpolation to reduce labor and time cost for radio map establishment. We might also focus on the crowdsourcing-based localization performance improvement against device diversity, multi-signal fingerprinting localization, and high-accuracy fingerprinting localization based on deep learning.

Author Contributions

Conceptualization, Y.S.; methodology, Y.S.; software, Y.S. and Y.H.; validation, Y.S. and Y.H.; formal analysis, Y.S. and Y.H.; investigation, Y.H. and Y.S.; supervision, W.M. and X.Z.; writing—original draft preparation, Y.S. and Y.H.; writing—review and editing, W.M. and Y.S.; funding acquisition, Y.S.

Funding

This work was partially supported by the Natural Science Foundation of the Jiangsu Higher Education Institutions of China under Grant No. 16KJB510014, the Natural Science Foundation of Jiangsu Province under Grant No. BK20171023, and the National Natural Science Foundation of China under Grant No. 61701223.

Acknowledgments

The authors of this paper would like to gratefully thank all the referees for the constructive and insightful comments.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Liu, J.; Chen, R.; Pei, L.; Guinness, R.; Kuusniemi, H. A hybrid smartphone indoor positioning solution for mobile LBS. Sensors 2012, 12, 17208–17233. [Google Scholar] [CrossRef] [PubMed]
  2. Liu, H.; Darabi, H.; Banerjee, P.; Liu, J. Survey of wireless indoor positioning techniques and systems. IEEE Trans. Syst. Man Cybern. C 2007, 37, 1067–1080. [Google Scholar] [CrossRef]
  3. He, S.; Chan, S.-H.G. Wi-Fi fingerprint-based indoor positioning: Recent advances and comparisons. IEEE Commun. Surv. Tutor. 2016, 18, 466–490. [Google Scholar] [CrossRef]
  4. Zou, D.Y.; Meng, W.X.; Han, S.; He, K.; Zhang, Z.Z. Towardubiq-uitous LBS: Multi-radio localization and seamless positioning. IEEE Wirel. Commun. 2016, 23, 107–113. [Google Scholar] [CrossRef]
  5. Sun, Y.L.; Zhang, X.Z.; Wang, X.C.; Zhang, X.G. Device-free wireless localization using artificial neural networks in wireless sensor networks. Wirel. Commun. Mob. Comput. 2018, 2018, 4201367. [Google Scholar] [CrossRef]
  6. Deng, Z.A.; Si, W.J.; Qu, Z.Y.; Liu, X.; Na, Z.Y. Heading estimation fusing inertial sensors and landmarks for indoor navigation using a smartphone in the pocket. EURASIP J. Wirel. Commun. Netw. 2017, 2017, 160. [Google Scholar] [CrossRef]
  7. Zhou, M.; Tang, Y.X.; Tian, Z.S.; Geng, X.L. Semi-supervised learning for indoor hybrid fingerprint database calibration with low effort. IEEE Access 2017, 5, 4388–4400. [Google Scholar] [CrossRef]
  8. Teuber, A.; Eissfeller, B.; Pany, T. A two-stage fuzzy logic approach for wireless LAN indoor positioning. In Proceedings of the 2006 IEEE/ION Position, Location and Navigation Symposium, San Diego, CA, USA, 25–27 April 2006; pp. 730–738. [Google Scholar]
  9. Sun, Y.L.; Xu, Y.B. Error estimation method for matrix correlation-based Wi-Fi indoor localization. KSII Trans. Internet Inf. Syst. 2013, 7, 2657–2675. [Google Scholar]
  10. Lin, T.-N.; Fang, S.-H.; Tseng, W.-H.; Lee, C.-W.; Hsieh, J.-W. A group-discrimination-based access point selection for WLAN fingerprinting localization. IEEE Trans. Veh. Technol. 2014, 63, 3967–3976. [Google Scholar] [CrossRef]
  11. Wen, Y.T.; Tian, X.H.; Wang, X.B.; Lu, S.W. Fundamental limits of RSS fingerprinting based indoor localization. In Proceedings of the IEEE INFOCOM, Hong Kong, China, 26 April–1 May 2015; pp. 2479–2487. [Google Scholar]
  12. Wang, B.; Chen, Q.; Yang, L.T.; Chao, H.-C. Indoor smartphone localization via fingerprint crowdsourcing: Challenges and approaches. IEEE Wirel. Commun. 2016, 23, 82–89. [Google Scholar] [CrossRef]
  13. Sun, Y.L.; Meng, W.X.; Li, C.; Zhao, N.; Zhao, K.L.; Zhang, N.T. Human localization using multi-source heterogeneous data in indoor environments. IEEE Access 2017, 5, 812–822. [Google Scholar] [CrossRef]
  14. Bolliger, P. Redpin-adaptive, zero-configuration indoor localization through user collaboration. In Proceedings of the MELT, San Francisco, CA, USA, 19 September 2008; pp. 55–60. [Google Scholar]
  15. Park, J.-G.; Charrow, B.; Curtis, D. Growing an organic indoor location system. In Proceedings of the ACM MobiSys, San Francisco, CA, USA, 15–18 June 2010; pp. 271–284. [Google Scholar]
  16. Rai, A.; Chintalapudi, K.K.; Padmanabhan, V.N.; Sen, R. Zee: Zero-effort crowdsourcing for indoor localization. In Proceedings of the ACM MobiCom, Istanbul, Turkey, 22–26 August 2012; pp. 1–12. [Google Scholar]
  17. Wu, C.S.; Yang, Z.; Liu, Y.H. Smartphones based crowdsourcing for indoor localization. IEEE Trans. Mob. Comput. 2015, 14, 444–457. [Google Scholar] [CrossRef]
  18. Mirowski, P.; Tin, K.H.; Saehoon, Y.; Macdonald, M. SignalSLAM: Simultaneous localization and mapping with mixed WiFi, bluetooth, LTE and magnetic signals. In Proceedings of the Indoor Positioning and Indoor Navigation (IPIN), Montbéliard, France, 28–31 October 2013; pp. 1–10. [Google Scholar]
  19. Chintalapudi, K.K.; Iyer, A.P.; Padmanabhan, V.N. Indoor localization without the pain. In Proceedings of the ACM MobiCom, Chicago, IL, USA, 20–24 September 2010; pp. 173–184. [Google Scholar]
  20. Jung, S.-H.; Han, D. Automated construction and maintenance of Wi-Fi radio maps for crowdsourcing-based indoor positioning systems. IEEE Access 2017, 6, 1764–1777. [Google Scholar] [CrossRef]
  21. Ma, L.; Fan, Y.Y.; Xu, Y.B.; Cui, Y. Pedestrian dead reckoning trajectory matching method for radio map crowdsourcing building in WiFi indoor positioning system. In Proceedings of the IEEE ICC—International Conference on Communications, Paris, France, 21–25 May 2017; pp. 1–5. [Google Scholar]
  22. Yu, N.; Xiao, C.; Wu, Y.; Feng, R. A radio-map automatic construction algorithm based on crowdsourcing. Sensors 2016, 16, 504. [Google Scholar] [CrossRef] [PubMed]
  23. Yin, J.; Yang, Q.; Ni, M. Learning adaptive temporal radio maps for signal-strength-based location estimation. IEEE Trans. Mob. Comput. 2008, 7, 869–883. [Google Scholar] [CrossRef]
  24. Wang, H.M.; Ma, L.; Xu, Y.B.; Deng, Z.A. Dynamic radio map construction for WLAN indoor location. In Proceedings of the Intelligent Human-Machine Systems and Cybernetics (IHMSC), Hangzhou, China, 26–27 August 2011; pp. 162–165. [Google Scholar]
  25. Zhou, C.F.; Gu, Y. Joint indoor localization and radio map generation based on stochastic variational Bayesian inference for FWIPS. In Proceedings of the 8th International Conference on Indoor Positioning and Indoor Navigation (IPIN), Sapporo, Japan, 18–21 September 2017; pp. 1–10. [Google Scholar]
  26. Zhao, H.L.; Huang, B.Q.; Jia, B. Applying kriging interpolation for WiFi fingerprinting based indoor positioning systems. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), Doha, Qatar, 3–7 April 2016; pp. 1–6. [Google Scholar]
  27. Lee, M.; Han, D. Voronoi tessellation based interpolation method for Wi-Fi radio map construction. IEEE Commun. Lett. 2012, 16, 404–407. [Google Scholar] [CrossRef]
  28. Han, S.; Zhao, C.; Meng, W.X.; Li, C. Cosine similarity based fingerprinting algorithm in WLAN indoor positioning against device diversity. In Proceedings of the IEEE International Conference on Communications (ICC), London, UK, 8–12 June 2015; pp. 2710–2714. [Google Scholar]
  29. Sun, Y.L.; Xu, Y.B.; Li, C.; Ma, L. Kalman/map filtering-aided fast normalized cross correlation-based Wi-Fi fingerprinting location sensing. Sensors 2013, 13, 15513–15531. [Google Scholar] [CrossRef] [PubMed]
  30. Laoudias, C.; Kemppi, P.; Panayiotou, C.G. Localization using radial basis function networks and signal strength fingerprints in WLAN. In Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM), Honolulu, HI, USA, 30 November–4 December 2009; pp. 1–6. [Google Scholar]
  31. Meng, W.X.; Wang, J.W.; Peng, L.; Xu, Y.B. ANFIS-based wireless LAN indoor positioning algorithm. In Proceedings of the Wireless Communications, Networking and Mobile Computing (WiCOM), Beijing, China, 24–26 September 2009; pp. 1–4. [Google Scholar]
  32. Talvitie, J.; Renfors, M.; Lohan, E.S. Novel indoor positioning mechanism via spectral compression. IEEE Commun. Lett. 2016, 20, 352–355. [Google Scholar] [CrossRef]
  33. He, S.; Chan, S.-H.G. Tilejunction: Mitigating signal noise for fingerprint-based indoor localization. IEEE Trans. Mob. Comput. 2016, 15, 1554–1568. [Google Scholar] [CrossRef]
  34. Wang, X.Y.; Gao, L.J.; Mao, S.W.; Pandey, S. CSI-based fingerprinting for indoor localization: A deep learning approach. IEEE Trans. Veh. Technol. 2017, 66, 763–776. [Google Scholar] [CrossRef]
  35. Chen, K.Y.; Wang, C.; Yin, Z.M.; Jiang, H.B.; Tan, G. Slide: Towards fast and accurate mobile fingerprinting for Wi-Fi indoor positioning systems. IEEE Sens. J. 2018, 18, 1213–1223. [Google Scholar] [CrossRef]
  36. Akram, B.A.; Akbar, A.H.; Shafiq, O. HybLoc: Hybrid indoor Wi-Fi localization using soft clustering-based random decision forest ensembles. IEEE Access 2018, 6, 38251–38272. [Google Scholar] [CrossRef]
  37. Specht, D.F. A general regression neural network. IEEE Trans. Neural Netw. 1991, 2, 568–576. [Google Scholar] [CrossRef] [PubMed]
  38. Aurenhammer, F. Voronoi diagrams—A survey of a fundamental geometric data structure. ACM Comput. Surv. 1991, 23, 345–450. [Google Scholar] [CrossRef]
  39. Zhang, G.L.; You, S.; Ren, J.J.; Li, D.M.; Wang, L. Local coverage optimization strategy based on voronoi for directional sensor networks. Sensors 2016, 6, 2183. [Google Scholar] [CrossRef] [PubMed]
  40. Fang, D.S.; Lv, X.L.; Yun, Y.; Li, F.F. An InSAR fine registration algorithm using uniform tie points based on Voronoi diagram. IEEE Geosci. Remote Sens. Lett. 2017, 14, 1403–1407. [Google Scholar] [CrossRef]
  41. Huang, H.W.; Sun, K.; Qi, J.J.; Ning, J.X. Optimal allocation of dynamic var sources using the Voronoi diagram method integrating linear programing. IEEE Trans. Power Syst. 2017, 32, 4644–4655. [Google Scholar] [CrossRef]
  42. Rao, T.R.; Balachander, D. RF propagation investigations at915/2400MHz in indoor corridor environments for wireless sensor communications. Prog. Electromagn. Res. B 2013, 47, 359–381. [Google Scholar] [CrossRef]
  43. Nelder, J.A.; Mead, R. A Simplex method for function minimization. Comput. J. 1965, 7, 308–313. [Google Scholar] [CrossRef]
  44. Tomandl, D.; Schober, A. A modified general regression neural network (MGRNN) with new, efficient training algorithms as a robust ‘black box’-tool for data analysis. Neural Netw. 2001, 14, 1023–1034. [Google Scholar] [CrossRef]
  45. Yang, S.; Dessai, P.; Verma, M.; Gerla, M. FreeLoc: Calibration-free crowdsourced indoor localization. In Proceedings of the IEEE INFOCOM, Turin, Italy, 14–19 April 2013; pp. 2481–2489. [Google Scholar]
Sensors 18 03579 g001 550
Figure 1. Diagram of the proposed fingerprinting localization system.
Figure 1. Diagram of the proposed fingerprinting localization system.
Sensors 18 03579 g001
Sensors 18 03579 g002 550
Figure 2. The basic structure of GRNN.
Figure 2. The basic structure of GRNN.
Sensors 18 03579 g002
Sensors 18 03579 g003 550
Figure 3. Experimental floor plan.
Figure 3. Experimental floor plan.
Sensors 18 03579 g003
Sensors 18 03579 g004 550
Figure 4. Experimental scenario of WLAN fingerprinting localization: (a) TP-LINK TL-WR845N AP; (b) 2-D code sticker on the ground; (c) Meizu M2 smartphone on a tripod.
Figure 4. Experimental scenario of WLAN fingerprinting localization: (a) TP-LINK TL-WR845N AP; (b) 2-D code sticker on the ground; (c) Meizu M2 smartphone on a tripod.
Sensors 18 03579 g004
Sensors 18 03579 g005 550
Figure 5. The partitioning result of the experimental environment using the Voronoi diagram.
Figure 5. The partitioning result of the experimental environment using the Voronoi diagram.
Sensors 18 03579 g005
Sensors 18 03579 g006 550
Figure 6. The locations of CPs, RPs, and IPs in the experimental environment.
Figure 6. The locations of CPs, RPs, and IPs in the experimental environment.
Sensors 18 03579 g006
Sensors 18 03579 g007 550
Figure 7. Localization results of one trajectory computed by the KNN and GRNN algorithms.
Figure 7. Localization results of one trajectory computed by the KNN and GRNN algorithms.
Sensors 18 03579 g007
Sensors 18 03579 g008 550
Figure 8. Cumulative probabilities of localization errors computed by different fingerprinting algorithms using the fused radio map.
Figure 8. Cumulative probabilities of localization errors computed by different fingerprinting algorithms using the fused radio map.
Sensors 18 03579 g008
Table
Table 1. Localization results of different fingerprinting algorithms using the fused radio map.
Table 1. Localization results of different fingerprinting algorithms using the fused radio map.
AlgorithmMean Error (m)Cumulative Probability (%)
Within 3 m ErrorWithin 4 m Error
KNN3.2964.374.3
WKNN3.2764.174.7
MLP3.7542.058.2
GRNN2.7866.480.4

Share and Cite

MDPI and ACS Style

Sun, Y.; He, Y.; Meng, W.; Zhang, X. Voronoi Diagram and Crowdsourcing-Based Radio Map Interpolation for GRNN Fingerprinting Localization Using WLAN. Sensors 2018, 18, 3579. https://doi.org/10.3390/s18103579

AMA Style

Sun Y, He Y, Meng W, Zhang X. Voronoi Diagram and Crowdsourcing-Based Radio Map Interpolation for GRNN Fingerprinting Localization Using WLAN. Sensors. 2018; 18(10):3579. https://doi.org/10.3390/s18103579

Chicago/Turabian Style

Sun, Yongliang, Yu He, Weixiao Meng, and Xinggan Zhang. 2018. "Voronoi Diagram and Crowdsourcing-Based Radio Map Interpolation for GRNN Fingerprinting Localization Using WLAN" Sensors 18, no. 10: 3579. https://doi.org/10.3390/s18103579

APA Style

Sun, Y., He, Y., Meng, W., & Zhang, X. (2018). Voronoi Diagram and Crowdsourcing-Based Radio Map Interpolation for GRNN Fingerprinting Localization Using WLAN. Sensors, 18(10), 3579. https://doi.org/10.3390/s18103579

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

Article Metrics

Back to TopTop