A 3D Fingerprinting Positioning Method Based on Cellular Networks

Abstract

A new 3D fingerprinting positioning scheme based on cellular networks is proposed by using implicit information of the location around geographic environments. Compared with original fingerprint positioning scheme, singular measurement is processed at the beginning of the proposed scheme. The main improvement of our proposed scheme is to employ cell matching degree and choose the best reasonable fingerprint according to the correlation of its surrounding points. Additionally, in order to improve searching efficiency, a new searching window is introduced. Finally, compared with the maximum likelihood method and the weighted K nearest neighbors method, the promising numerical results are also presented.

1. Introduction

The location-based service (LBS) in indoor environments has recently received unprecedented attention, since it is closely related to human lives. According to industry statistics, 70% of voice services and 80% of data services occur in indoor environments. Indoor location technologies based on wireless sensor network (WSN) increase enormously, for instance, wireless fidelity (Wi-Fi) and radio frequency identification (RFID) [1].

Much work has been done in the indoor location field. For example, Brunato and Battiti [2] proposed localization algorithms based on statistical learning theory. Mumtaz et al. [3] developed a downlink location based on adaptive beamforming algorithm, which profits from available positioning information. Alsehly et al. [4] presented a novel WIFI based indoor positioning method to save time and cost. Lee et al. [5] presented a localization method based on sound sources in underground parking lots and the least-squares method (LSM). T. Kim and E.-J. Kim [6] used SSID of virtual AP which contains the location information to allow users to detect their locations by scanning the WLAN signals. Liu and Yang [7] combined scene analysis and the feature of trilateration and gave a WIFI based positioning scheme. Navarro-Alvarez et al. [8] presented a new adaptive method to calculate the path loss exponent which could contribute to the precise estimation of the distance. Alsalih et al. [9] proposed two RFID localization schemes, which used received signal strength index (RSSI) and the transmission power control from the reader side.

Excluding accurate and mature for these technologies, compared with cellular location technology, they need to install extra infrastructures such as access points (APs) and bring extra costs. Additionally, a more realistic challenge is that users can not use the indoor location services, since their mobile terminals do not have corresponding modules. In order to solve these problems, radio frequency pattern matching (RFPM) method is proposed in 3GPP RAN4 due to its advantages [10, 11]. First of all, it does not bring any extra equipment to existing cellular networks. Secondly, it is not sensitive to the channel states and can be designed to obtain better results in the environment with significant multipath by using specific algorithms.

A typical localization method based on fingerprint matching is generally divided into two phases: an offline training phase (offline) and an online positioning phase (online). As shown in Figure 1, in the offline training phase, a pattern database can be constructed to store radio measurement vectors between network side and the center of every separated grid in advance [12, 13]. In that way, the radio condition mapping is created. In the online stage, when network side receives a positioning request coming from user equipment (UE), the position of UE can be acquired by matching available UE measurements with the corresponding data of every separated grid. According to the certain algorithm criteria, the most appropriate grid is selected as estimated position of target UE. Therefore, in the condition that the pattern database is created, it is necessary to find a good matching algorithm.

Figure 1

Fingerprinting positioning principle.

Recently, several fingerprint matching algorithms have been used for UE localization. In [14], a fingerprint positioning method is proposed, which puts the average of K nearest neighbors similar to MR data in the feature database as estimated position. In [15], a matching algorithm based on maximum likelihood is proposed to suit the situation where the measurement values are relatively independent, and measurement errors satisfy the Gaussian distribution. A new position estimation method is obtained from support vector machine (SVM) in [16].

In this paper, we propose a new fingerprinting scheme, which makes full use of the implicit measurement information of environment and space. Then, the promising test results are also presented, compared with the traditional RFPM localization method in indoor environments.

This paper is organized as follows. In next section, some traditional RFPM algorithms are given, including the maximum likelihood method and the K nearest neighbors method. Section 3 describes a new scheme called fingerprint correlation localization (FCL), with enhanced nearest neighbor localization (ENNL) algorithm. In Section 4, the test results based on the real cellular localization data are given. Finally, conclusions are drawn in the last section.

2. Traditional RFPM Localization Methods

Available fingerprint matching algorithms can be divided into two categories: probabilistic algorithms and deterministic algorithms. Probabilistic algorithms create a mathematic model and get an estimated position based on maximum likelihood estimation [15] or naive Bayesian statistical learning theory [1, 2]. Deterministic algorithms select the most similar position by calculating the similarity of measurement parameters between the target UE and the fingerprint. The most famous deterministic algorithm is K nearest neighbors method proposed by Microsoft Corporation [14].

2.1. ML Positioning Scheme

The probability density distribution of measurements can be obtained by measuring the identical point repeatedly. Then, the estimated position is the coordinate of fingerprint, which maximizes the likelihood function and achieves the maximum probability.

In [15], the basic model for a UE positioning can be expressed as

$$\begin{array}{cc}& F=h\left(l\right)+v,\end{array}$$

(1)

where l is the three-dimensional coordinates of UE, F is measurement vector, and v is a zero-mean Gaussian error vector.

Assume that all the measurement variables are mutually independent and the measurement error satisfies the Gaussian distribution. Its probability density is defined by

$$\begin{array}{cc}& f\left(F;l\right)=\frac{\mathrm{1}}{{\left(\mathrm{2}\pi \right)}^{m/\mathrm{2}}*{{\displaystyle \prod }}_j{\delta }_{i,j}}\exp \left(-{\displaystyle \sum }_j\frac{{\left(F-h\left(l\right)\right)}^{\mathrm{2}}}{\mathrm{2}{\delta }_{i,j}^{\mathrm{2}}}\right).\end{array}$$

(2)

When F is given, l can be calculated. Since the exponential function is monotonically increasing, the maximum value of (2) can be obtained as the following:

$$\begin{array}{cc}& \underset{i}{\min }\hspace{0.17em}lik\left(l\right)={\displaystyle \sum }_j\frac{{\left(r_j-h_j\left(l\right)\right)}^{\mathrm{2}}}{\mathrm{2}{\delta }_{i,j}^{\mathrm{2}}}.\end{array}$$

(3)

The ML positioning method assumes that measurement variables are mutually independent, and the measurement error satisfies the Gaussian distribution. Therefore, it can achieve relatively high accuracy under this assumption.

2.2. K Nearest Neighbors Positioning Scheme

In the online stage, using the strength of signal, the K nearest neighbors positioning method calculates the Euclidean distance between the measurement vector and the fingerprint of each grid [14] as

$$\begin{array}{cc}& D\left(F,F\left(l_i\right)\right)=\parallel F-F\left(l_i\right)\parallel ,\end{array}$$

(4)

where $l_i=(\text{id},x_i,y_i,z_i)\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le i\le n)$ indicates the three-dimensional coordinate of grid $l_i$ , F is the measurement vector, and $F(l_i)$ is the fingerprint on $l_i$ . The points of the first K smallest distance errors are chosen. And their positions generates a probable set

$$\begin{array}{cc}& \left\{l\left(\mathrm{1}\right),l\left(\mathrm{2}\right),\dots ,l\left(K\right)\right\}.\end{array}$$

(5)

The output estimation position is the average of $l(\mathrm{1}),\dots ,l(K)$ in (5).

The variable K has a significant impact on its positioning accuracy. If K equals 1, the algorithm is equivalent to the nearest neighbor method, which could be affected by measurement error easily. When K is a big number, points that are not close to the real location would be included. Then, the accuracy will decrease dramatically [17, 18]. Therefore, mostly, the best K is a small constant (from 2 to 4).

Better positioning accuracy can be achieved by averaging the coordinate of K nearest neighbor positions in the database. It also improves the positioning accuracy by using the weighted average technique. The more the fingerprint point is approximate to the needed positioning point in signal space, the higher weight value is assigned. Then, the K nearest neighbors' method is modified by

$$\begin{array}{cc}& \bar{l}\left(k\right)={\displaystyle \sum }_{i=\mathrm{1}}^{K}w\left(\frac{\mathrm{1}}{\left(\epsilon +D_i\right)}\right)l\left(i\right),\end{array}$$

(6)

where ε is an infinitesimal number in order to avoid denominator which is zero and $D_i$ is the distance between the fingerprint point and the needed positioning point.

Through the analysis, compared with the algorithms that focus on complex environmental characteristics, the K nearest neighbors positioning scheme pays more attention to the similarity between the measurement signal features and the fingerprint in database.

3. Fingerprint Correlation Localization Scheme

UE can be located more rapidly and more accurately if the environmental and space information is used properly. In this section, the modified fingerprint correlation localizationscheme and the corresponding mathematical model are presented, including flowchart and specific implementations. In order to improve searching efficiency, a new searching window is introduced.

3.1. Fingerprint Correlation Localization Scheme

Compared with original fingerprint positioning scheme, the singular measurement process, the cell matching degree, and the correlation with surrounding points are introduced in the modified scheme. Figure 2(a) is the overview of the flowchart of our scheme, and Figure 2(b) is the flowchart of original scheme.

Figure 2

(a) Proposed algorithm flowchart. (b) Original scheme.

The construction of pattern database is as follows. For each layer of 3D buildings, it is divided into many areas whose shapes may be rectangular, which is denoted as

$$\begin{array}{cc}& L=\left\{l_{\mathrm{1}},l_{\mathrm{2}},\dots ,l_n\right\},\end{array}$$

(7)

where $l_i=(\text{id},x_i,y_i,z_i)\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le i\le n)$ indicates the three-dimensional coordinate of grid $l_i$ .

Pattern database $FM=\{l_i,F(l_i),{\delta }_i^{\mathrm{2}}\hspace{0.17em}|\hspace{0.17em}i=\mathrm{1,2},\dots ,n\}$ can be constructed by collecting signal characteristics of every divided grid. Signal intensity vector is given as

$$\begin{array}{cc}& F\left(l_i\right)=\left(r_{i,\mathrm{1}},r_{i,j},\dots ,r_{i,M}\right),\end{array}$$

(8)

where ${\delta }_i^{\mathrm{2}}$ is the signal intensity variance of every grid, $r_{i,j}$ is the received signal intensity value of the jth cell at the grid $l_i$ , and M is the received total number of cells at the grid $l_i$ .

3.2. Processing Singular Measurements

Based on the pattern database, we handle singular measurement at first. UE sends a positioning request to the network side and reports the measurement report (MR). When the network interface obtains the MR, it judges the number of received signal code power (RSCP), which is given as $\text{RSC}{\text{P}}_{\text{num}}$ . At this step, there are two cases:

• (i)

if $\text{RSC}{\text{P}}_{\text{num}}=\mathrm{1}$ , according to trajectory characteristics, the estimated position of the terminal is adopted by historical steady positions. Firstly, we determine whether the trend of the first three historical positions is stable or not. If it is stable, let $\text{Lo}{\text{c}}_j=\text{Lo}{\text{c}}_{j-\mathrm{1}}$ . Otherwise let $\text{Lo}{\text{c}}_j$ equal the average of the first three historical positions;

(ii)

if $\text{RSC}{\text{P}}_{\text{num}}\ne \mathrm{1}$ , it reports MR and processes the localization request.

3.3. Enhanced Nearest Neighbor Localization Algorithm

For the reported MR, the measurement vector F is defined as

$$\begin{array}{cc}& F=\left(r_{\mathrm{1}},r_{\mathrm{2}},\dots ,r_m\right),\end{array}$$

(9)

where $r_k$ is signal intensity value of every cell and m is the received total number of cells.

Then, we calculate the cell matching degree between the measurement vector F and each fingerprint $F(l_i)$ of fingerprint database $FM$ ,

$$\begin{array}{cc}& {\eta }_i=\frac{N_{\text{same}}}{N_{\text{total}}}\times \mathrm{100}\%,\end{array}$$

(10)

where ${\eta }_i$ represents cell matching degree, $N_{\text{same}}$ is the number of the same cell between F and $F(l_i)$ , and $N_{\text{total}}$ is the total cell number of F.

According to our numerical experiments, the indicator of cell matching degree ${\eta }_i$ has a serious impact on the localization result. Due to some measurement errors, the cell-ID number of measurement vector does not always equal ${\max }_i\mathrm{\hspace{0.17em}\hspace{0.17em}}{\eta }_i$ . Therefore, the fingerprints need to be added in the candidate set, when the same cell-ID number $N_{\text{same}}$ is in certain range of the value (multiply $N_{\text{Total}}$ by ${\max }_i\mathrm{\hspace{0.17em}\hspace{0.17em}}{\eta }_i$ ).

Then, the candidate fingerprint set, which has senior cell matching degree with measurement vector, is obtained and denoted by

$$\begin{array}{cc}& C=\left\{F\left(l_p\right)\right\},\hspace{1em}p\in \left\{\mathrm{1,2},\dots ,n\right\},\end{array}$$

(11)

where n is point number of candidate fingerprint set.

Calculate the Euclidean distance between F and each grid of C as follows:

$$\begin{array}{cc}& D\left(F,F\left(l_p\right)\right)=\parallel F-F\left(l_p\right)\parallel ,\end{array}$$

(12)

where F and $F(l_p)$ are defined by (9) and (11), respectively. Afterwards, identify several potential grid fingerprints, which are relatively close to F (their Euclidean distances are small).

Finally, the best grid fingerprint is determined from these potential fingerprints.

At first, the smallest point $l_p$ is selected as the estimated position of UE. In order to confirm the reasonableness of the estimated point $l_p$ , it needs to consider the correlation of the point and its surrounding points. Then, calculate the Euclidean distance between F and surrounding points of $l_p$ . If those points do not deviate from the estimated point $l_p$ too much, we regard $l_p$ as a reasonable estimation. Otherwise, choose the point whose Euclidean distance is second-smallest as the estimated point and repeat the above process.

3.4. Searching Window

From the above analysis, the matching process costs much time when the fingerprint database is huge. In order to improve searching efficiency, we restrict searching data in a range of the coarse estimation point. The coarse estimation point can be obtained as follows. When the call-ID of the next MR is similar to an MR of the previous set, we regard the previous estimated point as the coarse estimation point of the current point and search the fingerprint points around that coarse estimation point.

4. Real Test Experiments

In order to test the effect of our modified method, we collect the real data of macrocell in a supermarket and compare it with the ML method and KNN method for those real data.

4.1. Test Scenario

In a real cellular network environment, since UE is distributed widely, the cost of acquiring large-scale drive test data is too high in a wide area. Then, it is not impracticable to construct a fingerprint database from drive test data. A practicable method of constructing a fingerprint database is generated by ray tracking techniques [19], and our pattern database is provided by Huawei Technologies Co., Ltd., in 2013.

The fingerprint database is constructed in an area of 2000 m * 2000 m, Chengdu, China. That test scenario is divided into four layers, and the height of each floor is 7 m. The size of vertical grid is 5 m * 5 m. The total number of grids is 272306. The grid fingerprint has ten cells.

They collect the real measurement data including RSCP and the position of UE in a supermarket. The supermarket is a building with four floors, and its area is 173.95 m * 53.82 m. The total number of measurement reports is 148482. And each measurement report receives the signals from seven cells.

4.2. Real Test Results

In the phase of processing singular measurements, since RSCP of the measurement report only comes from one cell-ID, the position of UE cannot be determined. To overcome this phenomenon, its historical tracking information is added to determine the position of UE. The positioning performance compared with original method is shown in Figure 3 and Table 1.

Table 1

Error statistics (m).

Err.	Singular number	67th percentile	90th percentile
Original method	4456	50.86	93.74
Revised method	4456	30.38	70.04

Figure 3

Horizontal positioning error.

USA Federal Communication Commission (FCC) releases the regulatory requirements for typical region. Positioning errors of FCC emergency positioning are less than 50 m with 67% and 150 m with 95% in the terminal-dependent case and less than 100 m with 67% and 300 m with 95% in the network-dependent case [20]. Therefore, we obtain the cumulative distribution function for all the MR positioning errors and compare positioning accuracy at 67% and 90% probability. The positioning probability is defined by the ratio of the number of the positioning error being less than the distance and the total number of MR measurements.

From Figure 3 and Table 1, we find that the revised method with processing singular measurements improves 20 m horizontal positioning errors at 90% positioning probability, compared with the original localization method.

In the positioning phase, as discussed in Section 3, an appropriate threshold of cell matching degree needs to be chosen. The threshold cannot be too large or too small. In order to pick up an appropriate threshold, we test the algorithm when the threshold of cell matching degree is chosen from 60%, 70%, 80%, and 90% to 100%, and their localization errors and cost of execution time are presented by Figures 4 and 5 and Tables 2 and 3.

Table 2

Error statistics (m).

Err.	Total number	60th percentile	70th percentile	80th percentile	90th percentile	100th percentile
Hor.	148482	32.24	22.02	21.10	27.38	43.04
Ver.	148482	7	0	0	7	7

Table 3

Time statistics (minute).

	Total number	60th percentile	70th percentile	80th percentile	90th percentile	100th percentile
CPU time	148482	40.87	29.24	22.75	18.89	17.49

Figure 4

Estimated error at 67% positioning probability.

Figure 5

Estimated error with 67% positioning probability.

From Figures 4 and 5, we find that the positioning accuracy seems better when the threshold is chosen from 70% to 80%, and the positioning time is decreasing monotonically in threshold variable. Therefore, we choose 75% as the threshold of cell matching degree.

Based on the above discussions, we compare the revised positioning method with the maximum likelihood positioning method (ML) and the K nearest neighbors positioning method (KNN), and their numerical results are presented in Figures 6 and 7 and Tables 4 and 5. Figure 6 is their numerical curves of horizontal positioning accuracy. Figure 7 is their numerical curves of vertical positioning accuracy. From Tables 4 and 5, compared with the ML positioning method and the KNN positioning method, we find that our revised positioning method (ENNL) improves the horizontal positioning accuracy from 70.8 m (ML) and 51 m (KNN) to 21 m (ENNL) at the 67% positioning probability and the vertical average positioning error from 7 m (ML) and 5.9 m (KNN) to 2 m (ENNL), respectively. The vertical error especially of our revised positioning scheme achieves 0 m at 67% positioning probability, which can distinguish the floor of the test building significantly compared with other methods, since the floor height of the test building is 7 m. It meets the FCC requirement and implements 3D indoor localization well [20].

Table 4

Horizontal error statistics (m).

Algorithm	Total number	67th percentile	90th percentile	Average error	Standard deviation	Max error	Min error
ML	148482	70.8	114.6	63.55	52.96	146.60	0
WKNN	148482	51.0	91.2	52.24	43.53	144.94	0
ENNL	148482	21.1	60.4	21.11	28.95	144.09	0

Table 5

Vertical error statistics (m).

Algorithm	Total number	67th percentile	90th percentile	Average error	Standard deviation	Max error	Min error
ML	148482	7	21	7.01	7.93	21	0
WKNN	148482	6	14.5	5.90	5.79	21	0
ENNL	148482	0	7	2.00	4.85	21	0

Figure 6

Horizontal positioning accuracy.

Figure 7

Vertical positioning accuracy.

5. Conclusions

In this paper, the principle of fingerprinting positioning and a novel positioning method in indoor environments with cellular networks have been presented. The detailed description of ML and KNN and the revised positioning scheme are given. Besides, we test and compare those positioning methods in a real indoor environment based on cellular network. From the test results, the horizontal accuracy is 21 m at 67% positioning probability of the revised positioning method without any extra equipment and satisfies the FCC requirement, that is, horizontal positioning accuracy 50 m at 67% positioning probability [20].