# Linear Regression Algorithm against Device Diversity for the WLAN Indoor Localization System

Authors: Liye Zhang; Xiaoliang Meng; Chao Fang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Recent years have witnessed a growing interest in using WLAN fingerprint-based methods for the indoor localization system because of their cost-effectiveness and availability compared to other localization systems. In this system, the received signal strength (RSS) values are measured as the fingerprint from the access points (AP) at each reference point (RP) in the offline phase. However, signal strength variations across diverse devices become a major problem in this system, especially in the crowdsourcing-based localization system. In this paper, the device diversity problem and the adverse effects caused by this problem are analyzed firstly. Then, the intrinsic relationship between different RSS values collected by different devices is mined by the linear regression (LR) algorithm. Based on the analysis, the LR algorithm is proposed to create a unique radio map in the offline phase and precisely estimate the user’s location in the online phase. After applying the LR algorithm in the crowdsourcing systems, the device diversity problem is solved effectively. Finally, we verify the LR algorithm using the theoretical study of the probability of error detection. Experimental results in a typical office building show that the proposed method results in a higher reliability and localization accuracy.


---

## Body

## 1. Introduction

In recent years, people’s daily life is becoming more and more convenient owing to the development of “5G”, smart cities, and Internet of Things [1, 2], and the network connectivity and spectrum efficiency of Internet of Things are greatly improved by “5G” [3]. As a major part of smart cities, location-based services (LBS) are attracting an enormous amount of attention [4, 5]. Furthermore, the explosive growth of intelligent mobile devices has promoted the research of LBS technology [6]. The typical LBSs mainly involve human navigation in unfamiliar environment, robot path planning and guidance, health care inside modern hospitals, location-based enhanced sensing, entity and storage tracking, and management. We can see from all these services that the reliable, accurate, and real-time localization technologies are required to locate the users’ position at the beginning of LBS [7].In outdoor environments, the Global Navigation Satellite System (GNSS) is the most prominent positioning technology and provides precise positioning. It has made a great success and brought great convenience to people’s lives [8]. However, due to line-of-sight (LOS) limitations, satellite signal receiving devices cannot be used indoors and in areas where satellites are blocked by tall buildings. Various solutions have been proposed as alternatives to GPS for indoor environments [9].Since the RADAR system is proposed in [10], the RSS fingerprint-based WLAN localization method has attracted the attention of many researchers due to its cost-effectiveness and availability [11, 12]. After years of research and evolution, thousands of access points (APs) have already been deployed in indoor environments, such as campuses, hospitals, airports, and shopping malls, which provide great opportunities for the development of indoor location estimation services. The RSS fingerprint-based WLAN localization system can reuse the existing WLAN infrastructures in indoor environments, which significantly reduces the cost.Typically, The RSS fingerprint-based WLAN indoor localization system contains two phases: the offline phase and the online phase [10]. In the offline phase, a number of reference points (RPs) are set in the indoor area, and researchers collect RSS values from the existing access points (APs) at all RP throughout. A radio map is then constructed using the collected RSS values and its corresponding geographic coordinates. In the online phase, users’ locations can be estimated by comparing the RSS value at their current location and those in the radio map [13, 14].A conclusion can be drawn from the structure of the fingerprinting localization systems that RSS values are the foundation of realizing positioning. In most of the existing experimental systems, researchers build the radio map using a mobile device in the offline phase, and the user’s location is computed using the same device in the online phase. However, in the actual localization system, this assumption is generally invalid, and the mobile devices used by different users are different in both the offline phase and the online phase. In the offline phase, aiming to reduce the labor and time costs of radio map construction, the crowdsourcing method has been proposed in the indoor localization domain, which brings a variety of distinct mobile devices [12, 14, 15]. In the online phase, the mobile devices which are used to localize the users may be different from the mobile devices used in the establishment of the radio map. The device diversity problem has been deeply studied in the last decade. The research results show that the main cause of such problem is the difference in hardware performance, which makes the differences between the RSS values collected by different devices may exceed 25 dB [16–18]. As a result, because of the adverse impact of the device diversity problem, the positioning accuracy of the crowdsourcing system is greatly reduced.Although the establishment of a radio map for each device can obtain the highest positioning accuracy, this method is not practicable obviously as a result of numerous devices. In [19, 20], the linear regression algorithm (LR) is proposed to eliminate the device diversity for the crowdsourcing WLAN indoor localization system. However, the descriptions and simulations of the LR algorithm in [19, 20] are very simple. Therefore, in this paper, we discuss the proposed method in detail and get the complete simulation results. More importantly, the formula of error detection probability of the proposed LR algorithm is derived. The problem of device diversity and the adverse effects caused by this problem are analyzed at the beginning. Then, the LR method is applied to deal with the discussed problem. The device diversity will be diminished greatly with respect to the proposed algorithm. The advantages of this method include the following points: the system has a low computational complexity, does not need any training period, and can be finished automatically without user’s intervention.The main contributions of this paper are as follows.(1)
The linear relationship between the RSS data collected by different devices is proved. We obtain the RSS points by comparing the RSS vectors collected by different devices, and the slope and the intercept of the straight line determined by any two points are calculated. Since all the slopes and intercepts are equal, all the RSS points are on the same line. Therefore, the relationship of RSS data collected by different devices is linear(2)
The fast least trimmed squares (FAST-LTS) algorithm is proposed to eliminate the device diversity problem. Since the relationship between RSS values collected by different devices is linear, using the linear regression algorithm, all the RSS values can be mapped into the same signal space. Because the outliers appear in the collected RSS values frequently and seriously affect the performance of the linear least squares (LLS) algorithm, the FAST-LTS algorithm is used in this paper. Simulation results verify the effectiveness of the proposed algorithm, and all the RSS data are mapped into the same signal space(3)
We derived the probability of error detection of all fingerprints in the radio map. By deducing the formula, we can obtain that the probability of error detection is greater when the two fingerprints are closer. Hence, these fingerprints in the set of candidate nearest neighbor fingerprints contribute most of the error and need to be dealt with carefullyThe rest of the paper is organized as follows. The related works are discussed in Section2. In Section 3, we state that the problem statement on indoor localization and the linear relationship between the RSS data collected by different devices is proved. The linear regression method is proposed to solve the device diversity problem in Section 4. Section 5 analyzes the probability of error detection in the indoor localization system. The simulation and experimental results are presented in Section 6. Finally, Section 7 concludes the paper.


## 2. Background and Related Works

To handle the device diversity problem, the establishment of a radio map for each device can obtain the highest positioning accuracy. However, this method is not practicable obviously as a result of numerous devices [21]. Therefore, various solutions have been proposed as the alternations.The device diversity problem was first discussed in [21]. Haeberlen et al. collected RSS values using different mobile devices at the same time and location in the test area, and they repeated this process at different locations. Then, the linear relationship between different RSS values collected by different mobile devices was inferred and used to eliminate the differences caused by different mobile devices. However, when an unknown device was used to find the current location, how to calculate the linear regression coefficients of the device had not been solved. In addition, although the authors in [21] had found the solution to overcome the device diversity problem, the solution was not applied to any localization systems.Since collecting labeled RSS values for each mobile devices is a labor-intensive and time-consuming process, a semisupervised method is proposed in [17] to solve the device diversity problem using a small number of labeled RSS values. To solve the device diversity problem, multiple devices are treated as multiple learning tasks in this paper.A latent feature space and a regression function are learned at the beginning, and then the signal spaces of all devices are mapped to the latent feature space by the regression function. Accordingly, the differences between different devices have been significantly reduced, and the positioning accuracy has been greatly improved.In [18], Tsui proposed an unsupervised learning algorithm to solve the problem in the WiFi localization system. In this paper, the Pearson product-moment correlation coefficient is used to label the RSS readings roughly collected by an unknown device at the beginning in the online phase. Then, different algorithms, such as regression algorithm and expectation maximization algorithm, are applied to train the transformation function. In [22], another solution using unsupervised learning algorithm is proposed to overcome the device diversity problem. In this paper, the probabilistic model is built to calculate the RSS values, and kernel estimation with a wide kernel width is used to reduce the difference in probability estimates. Although these methods reported some gain in localization accuracy, the unsupervised learning algorithm could not take the desired effect when the set APs detected by different devices are different.Kjærgaard et al. utilized hyperbolic location fingerprinting (HLF) to solve the device diversity problem [23, 24]. In the training phase, the radio map is built by the signal strength ratio between two APs instead of an absolute RSS value from a single AP. Since the signal strength ratio is more stable than the absolute RSS value, the localization accuracy is significantly improved. However, the ratio term of the linear transformation function is not the only factor to be considered. If this offset component is significant in the linear relation or the set of the APs detected by different devices is different, this method is expected to fail.In [25–27], three different of signal strength methods are proposed to reduce the impact of device diversity. In [25], Dong et al. used the different between all possible AP pairs, called DIFF, to build the radio map. In this radio map, the cost of the DIFF method is On2 and may increase dramatically when the number of the AP increases. In [26], the signal strength difference (SSD) method approach subtracts the RSS value of an anchor AP from the other RSS values in the fingerprint. Therefore, each fingerprint contains only n−1 RSS differences, and the dimension of SSD method is On. As a result, the DIFF method achieves higher localization accuracy than the SSD method. Laoudias proposed the mean differential fingerprint (MDF) method in [27] which uses the mean RSS value to calculate the RSS differences to create the RSS fingerprint. The MDF method maintains the advantages of DIFF and SSD, which can achieve the high positioning accuracy as DIFF, while keeping the computational overhead similar to SSD.In [28, 29], convolutional neural networks (CNN) are used to eliminate the device diversity problem. Cai et al. [28] proposed a device-free indoor localization system based on channel state information (CSI) in IEEE 802.11n through CNN, and the space diversity, time diversity, and frequency diversity of CSI are combined to design the more abundant localization features. In [29], the database is constructed using the magnetic pattern (MP) in the offline phase, and the location is calculated using the CNN algorithm in the online phase to eliminate the device diversity problem. Although this is a magnetic positioning system, it can give us a lot of inspiration.In [30–33], the LR method is used to mine the internal relationship between data and eliminate the differences between data through linear regression. In [30], an automatic device transparent RSS-based indoor localization system has been proposed, and the linear least squares (LLS) algorithm is applied in this system. Combining the offset component and ratio term makes the LLS algorithm a complete algorithm. Moreover, the algorithm complexity of LLS is much lower than the other algorithms discussed above. Li et al. [31] presented a prototype model of a multiple-surveyor-multiple-client system in the crowdsourcing localization system. The linear regression model is applied to calibrate across participating training devices, and a geometric distribution is used to obtain a conditional likelihood that the client observes invisible access points in the training phase. Ye et al. [32] proposed a device calibration algorithm to fuse samples from different devices to obtain grid fingerprints and a two-step online positioning algorithm to localize user’s position. In [33], the FAST-LTS algorithm is proposed to deal with large data sets. Due to the FAST-LTS algorithm, the LTS estimator becomes available as a tool for analyzing large data sets and to detect outliers or deviating substructures. This algorithm provides us with a very good idea to deal with the problem of device diversity. Therefore, we propose a FAST-LTS algorithm to eliminate the device diversity problem in [19, 20], which achieves good results. In this paper, we further improve this algorithm.


## 3. Problem Formulation

For the RSS fingerprint-based localization method, the localization accuracy greatly depends on the mapping relation between the fingerprint and its corresponding coordinates stored in the radio map. In the offline phase, the localization area is divided into a discrete grid withn RPs and m APs, which are deployed in this area. We collect RSS values from the APs at each RP, and a fingerprint radio map is constructed that holds the RSS for m APs and n RPs. The system diagram of the RSS fingerprint-based WLAN indoor localization system is shown in Figure 1. In traditional WLAN positioning methods, hundreds of fingerprints are collected over time for each RP. After RSS preprocessing, a 1×m vector xi=xi1,xi2,⋯,xim is generated at each RP, where xik is the received signal strength measured by the training device at the i-th RP from the k-th AP. The i-th fingerprint xi,ci is the combination of the RSS measurement xi and the coordinate ci=ci1,ci2 of RP Si. All the fingerprints are tabulated into the radio map that can be represented in Figure 1.Figure 1
Typical WLAN indoor localization system.In the online phase, the user collects the RSS valuey=yj1,yj2,⋯,yjm at an unknown position Sj by a mobile device, and then the user’s position could be estimated by comparing y with the radio map. Usually, if y is similar to the fingerprint xi in the radio map, we reason that user’s location Sj must be close to Si.In the actual localization system, the mobile devices used by different users are distinct from each other. Since the WLAN signal receivers with different performance are equipped with the different mobile devices, so the different mobile devices may have different signal sensing capacities and yield different RSS values. To illustrate, we used five different mobile devices to collect RSS values from a single AP at a particular location and plotted the histogram in Figure2. Due to the large fluctuation of the RSS value in the indoor environment, if only 2-3 RSS is collected on one RP, the accurate RSS distribution cannot be obtained. Therefore, we collected 100 RSS values in each RP. As shown in Figure 2, the RSS values collected by different devices can be quite different even at the same location. This directly results in erroneous location estimations if we use one device’s data for training and another device’s data for locating.Figure 2
RSS values collected by five different devices at the same time and location from the same APs..We defineX and Y as the signal space for the radio map X built by the training device and the online RSS values collected by the localization device, respectively. Let the fingerprint x∗ in the radio map X is the nearest neighbor online RSS value y. Because of the different signal receiving capability of the different mobile devices, the RSS values collected at the close physical locations are obvious different. Hence, one of the key challenges arises: how to process these RSS values collected by different devices to make the x∗ in closer to y. Mathematically,
(1)Y≈FX.By learningF, the radio map X build by the training device could be used to localize any other devices.Next, we will explore the relationship between different RSS values collected by different mobile devices. The signal processing diagram of the mobile device is shown in Figure3.Figure 3
Signal processing diagram of the mobile device.We suppose that the transmit power of the AP isPt, and the receiving power of the mobile device is
(2)P=Pt+PL+Gt+Gr+α,where P is the receiving power of the antenna, PL is the path loss at distance d form AP, Gt is the transmit antenna gain, Gr is the receiving antenna gain, and α is the power amplifier magnification.Assume thatxA=P1A,P2A,⋯,PmA and xB=P1B,P2B,⋯,PmB represent the RSS vectors collected by two distinct devices A and B at the same location and the same time. In order to obtain the mapping function in Eq. (1), we compare xA and xB and get m points whose coordinates are PiA,PiB,i=1,2,⋯,m, and the RSS value collected by devices A and B from the i-th AP are
(3)PiA=Pti+PLi+Gti+GrA+αA,(4)PiB=Pti+PLi+Gti+GrB+αB,where the subscript i represents the i-th AP, and the superscripts A and B represent the device A and the device B, respectively.Figure4 shows three points determined by matrix xA and xB, any two points can determine a straight line, and then we get 3 lines in this figure. Suppose the slopes of the 3 lines are a12, a13, and a23, and the intercept of the 3 lines are b12, b13, b23, if a12=a13=a23 and b12=b13=b23, all the 3 points are in the same line; that is, there is a linear relationship between xA and xB. Therefore, if the slopes and intercepts of the lines determined by any two of the n data points are equal, it can be determined that all the n data points are on the same line, which means the relationship between xA and xB is linear. In this paper, using this method, the relationship between xA and xB can be proved.Figure 4
Schematic diagram of relation between data points.The linear equation determined by two pointsPiA,PiB and PjA,PjB is
(5)PB=aijPA+bij.The slope and intercept of the equation are(6)aij=PiB−PjBPiA−PjA,(7)bij=PiAPjB−PjAPiBPiA−PjA.Substituting the values of Eq. (3) and Eq. (4) into Eq. (6) and Eq. (7), then we can get
(8)aij=1,(9)bij=GrB+αB−GrA−αA.As can be seen from Eq. (8) and Eq. (9), in the ideal case, the slope and intercept of the line determined by two points PiA,PiB and PjA,PjB are only related to the antenna gains and amplification factor of the device A and device B. Therefore, the m points determined by the vectors xA and xB are on the same line.
(10)xB=axA+b,where the linear equation coefficients are a=aij and b=bij.Assume that the RSS vectorsxA and xB are collected at the same location and at different times. In an ideal case, the transmitting power of the AP, the working status of the mobile terminal, and the path loss remain constant; therefore, the linear relationship between xA and xB is same as Eq. (10).In practice, the instability of the AP transmit power and the complexity of the indoor electromagnetic environment make the RSS values collected by the mobile device unstable at different times.(11)PiA=PtiA+PLiA+Gti+GrA+αA+ξmA,(12)PiB=PtiB+PLiB+Gti+GrB+αB+ξmB,(13)PjA=PtjA+PLjA+Gtj+GrA+αA+ξmA,(14)PjB=PtjB+PLjB+Gtj+GrB+αB+ξmB,where PtiB=PtiA+δPti, PLiB=PLiA+δPLi, PtjB=PtjA+δPtj, and PLjB=PLjA+δPLj.Substituting the values of Eq. (11), Eq. (12), Eq. (13), and Eq. (14) into Eq. (6),
(15)aij=PiB−PjBPiA−PjA=PtiB+PLiB+Gti+GrB+αB+ξmB−PtjB−PLjB−Gtj−GrB−αB−ξmB/PtiA+PLiA+Gti+GrA+αA+ξmA−PtjA−PLjA−Gtj−GrA−αA−ξmA=PtiB+PLiB+Gti−PtjB−PLjB−GtjPtiA+PLiA+Gti−PtjA−PLjA−Gtj=PtiA+δPti+PLiA+δPLi+Gti−PtjA−δPtj−PLjA−δPLj−Gtj/PtiA+PLiA+Gti−PtjA−PLjA−Gtj=PtiA+PLiA+Gti−PtjA−PLjA−Gtj+δPti+δPLi−δPtj−δPLj/PtiA+PLiA+Gti−PtjA−PLjA−Gtj.When the indoor environment approaches an ideal environment, which means the difference of AP transmitting power at different timesδPt→0, and the difference of path loss at different times δPL→0, then
(16)limδPt→0δPL→0aij=1.Similarly, we can get(17)limδPt→0δPL→0bij=GrB+αB−GrA−αA.As a result, the linear relationship betweenxA and xB can be proved by Eq. (16) and Eq. (17).In an actual indoor environment, the working status of the AP is unstable, and the electromagnetic environment in the room is very complicated. Therefore, the differenceδPt of the transmission power of the AP and the difference δPL of the path loss are not equal to 0, and as the result, the linear equation coefficients are
(18)aij=1+δa,(19)bij=GrB+αB−GrA−αA+δb,where δa=δij/PiA−PjA is the error of slope, and δb=PiAδAPj−PjAδAPi/PiA−PjA is the error of intercept, δij=δAPi−δAPj, δAPi=δPti+δPLi, and δAPj=δPtj+δPLj.Figure5 shows the slope and intercept of Eq. (18) and Eq. (19). Considering the noise, we can see from Eq. (18), Eq. (19), and Figure 5 that the slope and intercept of the straight line are centered on the ideal slope and intercept and fluctuate within an error range. Therefore, the relationship between RSS data vectors xA and xB is approximately linear.Figure 5
The slope and intercept between RSS values collected by different devices. (a) Slope diagram. (b) Intercept diagram.
(a)(b)In Figure6, the comparison results of RSS values collected by five distinct devices are plotted. In this figure, each point represents the RSS values collected by two distinct devices at the same RP from the same AP. For example, the top left subplot in Figure 6 represents the RSS values collected by Lenovo laptop and Huawei mobile device. Figure 6 verifies the results of Eq. (18), Eq. (19), and Figure 5, and the linear correlation can be drawn by the RSS values collected by Lenovo laptop and other devices.Figure 6
Linear correlation between RSS values for different devices.As a result, we apply the linear regression method (LR) as the mapping function in this paper. The LR model is defined by specifying how the signal space of localization deviceX is mapped into Y in the signal space of the training device. Based on the LR method, a unique radio map in the offline phase could be built and improve the localization accuracy in the RSS-based crowdsourcing localization system.


## 4. Linear Regression Algorithm against Device Diversity for the Crowdsourcing Fingerprint Indoor Localization System

In this section, a preprocessing procedure is used to stabilize the acquisition of RSS values at the beginning. Then, the RSS values collected by an unknown device are labeled automatically with a rough location estimation using a correlation ratio computed from the Pearson product-moment correlation coefficient. Finally, the linear regression algorithm (LR) is proposed as the mapping function to solve the device diversity problem, and the fast least trimmed squares (FAST-LTS) is applied for the LR method to provide a more robust performance.


### 4.1. Preprocessing of RSS Values

The first step in our work is to mitigate the RSS fluctuations caused by the complexity of the indoor environment. Typically, when building the radio map, we measure a large number of RSS values at each RP to eliminate the noise. LetRSSli=rss1,rss2,⋯,rssp be the set of RSS values collected at location l from the i-th AP. When the RSS values are collected to build the radio map or estimate the current location, the length of all RSS must be the same. However, for some reasons, some APs cannot work properly. To ensure that the RSS measurements are the same length, we use a value of −110 dBm to fill the missing RSS value, and we denote it as an outlier. These outliers could affect the linear regression process and produce erroneous location estimations, as shown in Figure 7.Figure 7
Preprocessing of RSS values using trimmed average. (a) Traditional average. (b) Trimmed average.
(a)(b)Figure7(a) plots the linear regression function of the RSS values for two different devices, where the traditional average is used for estimation. The uncertainty in the RSS samples can be seen clearly in this figure. To achieve higher positioning accuracy, the original RSS measurements should be preprocessed prior to the localization process. Average, mode, and median are the common data preprocessing methods in mathematics. Because the average takes all the RSS values into consideration and uses the data more efficiently, so we average the RSS values to overcome the RSS fluctuations. However, the average is susceptible to the outliers of -110 dBm. The existence of outliers could seriously affect the accuracy of the average and produce erroneous location estimations. Hence, the truncated average is used in our work to stabilize the collected RSS samples:
(20)xli=∑j=1prssjIrssj≠−110dBm∑j=1pIrssj≠−110dBm,where I· is an indicator function.There is also a special case when calculating the truncated average. Consider a situation that only one sample reports valid readingrssi=αdBm when all the other RSS values are -110 dBm, the result of Eq. (20) is xli=αdBm. Therefore, when applying Eq. (20), we first calculate the ratio t of the normal RSS value in the collected vector and set a threshold tth, and then we can get the truncated average
(21)xli=xli,ift>tth−110dBm,ift≤tth.


### 4.2. Rough Location Estimation

After completing the preprocessing of RSS data, we use the linear regression method as the mapping function.(22)y=aixi+bi1,where xi is the i-th fingerprint in the radio map collected by the training device, y is the RSS values measured in the online phase by localization device, and ai,bi are the coefficients in the mapping function.Based on the mapping function in Eq.(22), the RSS values collected by different devices can be transformed to the same signal space. Accordingly, the device diversity problem can be solved. However, the RSS values collected in the online phase are unlabeled and cannot be processed using the linear regression algorithm. Therefore, the correlation ratio computed from the Pearson product-moment correlation coefficient is proposed to roughly label the RSS values collected in the online phase as [18].
(23)ry,xi=∑k=1myk−y¯xik−x¯i∑k=1myk−y¯2∑k=1mxik−x¯i2,where m is the number of APs, yk and xik are the RSS values measured from the k-th AP, y¯=1/m∑k=1myk is the average of the RSS values from the tracking device, and x¯i=1/m∑k=1mxik represents the mean of the RSS values measured by the training device in the i-th fingerprint. The range of the Pearson correlation ratio is −1,1, where 1 indicates the highest positive linear correlation between RSS values and the fingerprints with a negative r should be excluded.When we get the online RSS valuesy, the Pearson correlation ratio r between y and all fingerprints xi in X can be computed using Eq. (23). By setting a correlation coefficient threshold rth, we can obtain the set of nearest neighbor fingerprints in the radio map X for y.
(24)A=xi∈X∣ry,xi>rth,0≤rth≤1.The fingerprints inA have the strongest linear correlation with the online RSS values, the online RSS values can be labeled roughly, and the linear regression mapping function can be obtained more accurately.


### 4.3. Linear Regression Algorithm against Device Diversity Problem

In Eq. (22), the important parameters, ai and bi, need to be computed first. Because the linear least squares (LLS) algorithm is more sensitive to the outliers, we use the fast least trimmed squares (FAST-LTS) algorithm to compute the parameters in Eq. (22).Assume that the amount of the nearest neighbors inA is c, the FAST-LTS solution for linear regression with intercept is given by
(25)minai,bi∑i=1hdi2,where h=intc+2/2, di=y−aixi+bi1, and • is norm 2 of a vector, di2 are the ordered squared residuals: d12≤d22≤⋯≤di2≤⋯≤dc2.Given theh-subset Hold of all nearest neighbors, the C−step is used to compute ai and bi as follows [33]:
(1)
Computeaold and bold≔ least squares regression estimator based on Hold(2)
Compute the residualsdoldi for i=1,⋯,c(3)
Sort the absolute values of these residuals,∣dold1∣≤∣dold2∣≤⋯≤∣doldc∣(4)
Arrange the absolute values of the residuals in ascending order, letHnew be a subset consisting of the nearest neighbors corresponding to the first h absolute values of the residuals in the sequence(5)
Computeanew and bnew≔ least squares regression estimator based on HnewRepeatingC−step with numerous Hold, a lot of regression coefficients will be gotten. The approximate solution is the coefficient corresponding to the least ∑i=1hdi2. Using the parameters ai and bi, x can be transformed to the signal space of the online data y:
(26)xi′=aixi+bi1,where xi′∈Y. Since both xi′ and y belong to the same signal space, the KNN algorithm based on the RSS Euclidean distance can be used to estimate the user’s location.


## 4.1. Preprocessing of RSS Values

The first step in our work is to mitigate the RSS fluctuations caused by the complexity of the indoor environment. Typically, when building the radio map, we measure a large number of RSS values at each RP to eliminate the noise. LetRSSli=rss1,rss2,⋯,rssp be the set of RSS values collected at location l from the i-th AP. When the RSS values are collected to build the radio map or estimate the current location, the length of all RSS must be the same. However, for some reasons, some APs cannot work properly. To ensure that the RSS measurements are the same length, we use a value of −110 dBm to fill the missing RSS value, and we denote it as an outlier. These outliers could affect the linear regression process and produce erroneous location estimations, as shown in Figure 7.Figure 7
Preprocessing of RSS values using trimmed average. (a) Traditional average. (b) Trimmed average.
(a)(b)Figure7(a) plots the linear regression function of the RSS values for two different devices, where the traditional average is used for estimation. The uncertainty in the RSS samples can be seen clearly in this figure. To achieve higher positioning accuracy, the original RSS measurements should be preprocessed prior to the localization process. Average, mode, and median are the common data preprocessing methods in mathematics. Because the average takes all the RSS values into consideration and uses the data more efficiently, so we average the RSS values to overcome the RSS fluctuations. However, the average is susceptible to the outliers of -110 dBm. The existence of outliers could seriously affect the accuracy of the average and produce erroneous location estimations. Hence, the truncated average is used in our work to stabilize the collected RSS samples:
(20)xli=∑j=1prssjIrssj≠−110dBm∑j=1pIrssj≠−110dBm,where I· is an indicator function.There is also a special case when calculating the truncated average. Consider a situation that only one sample reports valid readingrssi=αdBm when all the other RSS values are -110 dBm, the result of Eq. (20) is xli=αdBm. Therefore, when applying Eq. (20), we first calculate the ratio t of the normal RSS value in the collected vector and set a threshold tth, and then we can get the truncated average
(21)xli=xli,ift>tth−110dBm,ift≤tth.


## 4.2. Rough Location Estimation

After completing the preprocessing of RSS data, we use the linear regression method as the mapping function.(22)y=aixi+bi1,where xi is the i-th fingerprint in the radio map collected by the training device, y is the RSS values measured in the online phase by localization device, and ai,bi are the coefficients in the mapping function.Based on the mapping function in Eq.(22), the RSS values collected by different devices can be transformed to the same signal space. Accordingly, the device diversity problem can be solved. However, the RSS values collected in the online phase are unlabeled and cannot be processed using the linear regression algorithm. Therefore, the correlation ratio computed from the Pearson product-moment correlation coefficient is proposed to roughly label the RSS values collected in the online phase as [18].
(23)ry,xi=∑k=1myk−y¯xik−x¯i∑k=1myk−y¯2∑k=1mxik−x¯i2,where m is the number of APs, yk and xik are the RSS values measured from the k-th AP, y¯=1/m∑k=1myk is the average of the RSS values from the tracking device, and x¯i=1/m∑k=1mxik represents the mean of the RSS values measured by the training device in the i-th fingerprint. The range of the Pearson correlation ratio is −1,1, where 1 indicates the highest positive linear correlation between RSS values and the fingerprints with a negative r should be excluded.When we get the online RSS valuesy, the Pearson correlation ratio r between y and all fingerprints xi in X can be computed using Eq. (23). By setting a correlation coefficient threshold rth, we can obtain the set of nearest neighbor fingerprints in the radio map X for y.
(24)A=xi∈X∣ry,xi>rth,0≤rth≤1.The fingerprints inA have the strongest linear correlation with the online RSS values, the online RSS values can be labeled roughly, and the linear regression mapping function can be obtained more accurately.


## 4.3. Linear Regression Algorithm against Device Diversity Problem

In Eq. (22), the important parameters, ai and bi, need to be computed first. Because the linear least squares (LLS) algorithm is more sensitive to the outliers, we use the fast least trimmed squares (FAST-LTS) algorithm to compute the parameters in Eq. (22).Assume that the amount of the nearest neighbors inA is c, the FAST-LTS solution for linear regression with intercept is given by
(25)minai,bi∑i=1hdi2,where h=intc+2/2, di=y−aixi+bi1, and • is norm 2 of a vector, di2 are the ordered squared residuals: d12≤d22≤⋯≤di2≤⋯≤dc2.Given theh-subset Hold of all nearest neighbors, the C−step is used to compute ai and bi as follows [33]:
(1)
Computeaold and bold≔ least squares regression estimator based on Hold(2)
Compute the residualsdoldi for i=1,⋯,c(3)
Sort the absolute values of these residuals,∣dold1∣≤∣dold2∣≤⋯≤∣doldc∣(4)
Arrange the absolute values of the residuals in ascending order, letHnew be a subset consisting of the nearest neighbors corresponding to the first h absolute values of the residuals in the sequence(5)
Computeanew and bnew≔ least squares regression estimator based on HnewRepeatingC−step with numerous Hold, a lot of regression coefficients will be gotten. The approximate solution is the coefficient corresponding to the least ∑i=1hdi2. Using the parameters ai and bi, x can be transformed to the signal space of the online data y:
(26)xi′=aixi+bi1,where xi′∈Y. Since both xi′ and y belong to the same signal space, the KNN algorithm based on the RSS Euclidean distance can be used to estimate the user’s location.


## 5. Analysis of Probability of Error Detection of the Proposed Algorithm

In this section, we analyzed the probability of error detection in the crowdsourcing indoor localization system. In the offline training phase, the radio mapX consists of n fingerprints that are built by the training device DT. Suppose x1 and x2 are two fingerprints in the radio map X, y is the RSS value collected by the localization device in the online phase. Assume that the fingerprint x1 is the nearest neighbor to the online RSS value y. Based on the linear regression model, the relation between the RSS vector y and the fingerprint x1 can be expressed as
(27)y=a0x1+b01+ε,where a0 and b0 are the real linear regression coefficient between two RSS vectors, and ε is a 1×m noise vector. We suppose that ε is the Gaussian distribution of N0,σε2, and the variance σε2 is unknown.Using the proposed LR method, the online RSS vectory and the radio map X can be transferred to the same signal space
(28)x^1=a1x1+b11,(29)x^2=a2x2+b21.In this paper, the KNN algorithm is used to estimate the location of the online RSS vectory. First of all, the Euclidean distance between the online point y and the fingerprints in the radio map X should be calculated by
(30)d1=y−x∧12,(31)d2=y−x∧22.In the KNN algorithm, we choose the fingerprints with the smallest Euclidean distance as the nearest neighbor ofy. Assume that k=1, if d1>d2, then x1 is the nearest neighbor of y; on the contrary, x2 is the nearest neighbor of y. We have assumed that x1 in the radio map X is the nearest neighbor of y, and an error occurs when the calculation results show that d1<d2. Therefore, we can get the probability of localization error from Eq. (32) as given as
(32)Pe=PNNy=x2∣NNy=x1=Py−x∧22<y−x∧12,where NN· is the nearest neighbor of the online data y.If the nearest neighbor of the online datay estimated by the localization system is correct, then, NNy=x1, the linear regression coefficient could be calculated by Eq. (25),
(33)a1,b1=argmina,by−ax1+b12=argmina,ba0x1+b01+ε−ax1+b12=argmina,ba0−ax1+b0−b1+ε2.Obviously, in Eq. (33), when a=a0 and b=b0, we get the minimizer of Eq. (30), and the linear regression coefficient between y and x1 is
(34)a1=a0,b1=b0.Substituting the values of Eq. (34) into Eq. (33), we can get
(35)d1=y−x∧12=εTε=∑i=1mεi2~χm2,where χm2 is the chi-square distribution with degrees of freedom of m.When a localization error occurs, thenNNy=x2, and the linear regression coefficient between y and x2 becomes
(36)a2,b2=argmina,by−ax2+b12=argmina,ba0x1+b01+ε−ax2+b12=argmina,ba0x1−ax2+b0−b1+ε2.By making use of triangular inequality,(37)a0x1−ax2+b0−b1+ε≤a0x1−ax2+b0−b1+ε.From Eq. (37), b2=b0 is the solution when we get the minimizer of Eq. (36). Therefore, Eq. (36) can be equivalent to
(38)a2=argmina,ba0x1−ax22=argmina,ba0x1−ax2Ta0x1−ax2=argmina,ba02x1Tx1−aa0x1Tx2−aa0x2Tx1+a2x2Tx2.Becausex1 and x2 are m×1 vector, then x1Tx2=x2Tx1; therefore, Eq. (38) can be written as
(39)a2=argmina,ba02x12−2aa0x1Tx2+a2x22.In Eq. (39), a0, x1, and x2 are already known. Let A=a02x12, B=a0x1Tx2, and C=x22, and then Eq. (39) can be expressed as
(40)a2=argmina,bA−2Ba+Ca2.From Eq. (40), we can get the solution of a2 by making the derivative of the quadratic equation equal to 0. Let Δ=A−2Ba+Ca2 and ∂Δ/∂a=0 yields
(41)∂Δ∂a=2Ca−2B=0.Then, we can get(42)a2=BC=a0x1Tx2x22.At last, the linear regression coefficient betweeny and x2 can be calculated by
(43)a2=BC=a0x1Tx2x22,b2=b0.Substituting the linear regression coefficients into Eq. (31), then we can get
(44)d2=y−x^2=a0x1+b01+ε−a0x1Tx2x22x2−b012=a0x1−a2x2+ε2.Using Eq. (35) and (44), the probability of localization error in Eq. (32) can be computed by
(45)Pe=Py−x∧22<y−x∧12=Pa0x1−a2x2+ε2<ε2=Pa02x1Tx1−a0a2x1Tx2+a0x1Tε+a22x2Tx2−a0a2x2Tx1−a2x2Tε+a0εTx1−a2εTx2+εTε<εTε=Pa02x1Tx1−2a0a2x1Tx2+2a0x1Tε−2a2x2Tε+a22x2Tx2<0=P2a0x1T−a2x2Tε<2a0a2x1Tx2−a02x1Tx1−a22x2Tx2=P2a0x1T−a2x2Tε<2a0a2x1Tx2−a02x12−a22x22.For the right side of the inequality in Eq. (45), we set
(46)ξ=2a0a2x1Tx2−a02x12−a22x22=2a0a0x1Tx2x22x1Tx2−a02x12−a0x1Tx2x222x22=a02x1Tx22x22−a02x12=a02x1Tx22−x12x22x22.Using Cauchy-Schwartz inequality,(47)x1Tx22≤x12x22.Therefore,ξ≤0 is in Eq. (46).For the left side of the inequality in Eq. (45), we set η=sTε. In this equation,
(48)sT=2a0x1T−a2x2T=2a0x1T−a0x1Tx2x22x2T=2a0x1TI−x2x2Tx22,where I is the identity matrix.Sinceε∼N0,σε2, then
(49)η∼N0,σ2,where
(50)σ2=σε2sTs=σε22a0x1TI−x2x2Tx222a0x1TI−x2x2Tx22T=4a02σε2x1TI−x2x2Tx22I−x2x2Tx22Tx1=4a02σε2x1TI−2x2x2Tx22+x2x2Tx2x2Tx24x1=4a02σε2x1Tx1−2x1Tx2x2Tx1x22+x1Tx2x2Tx2x2Tx1x24=4a02σε2x12−2x1Tx22x22+x1Tx2x22x2Tx1x24=4a02σε2x12−2x1Tx22x22+x1Tx22x22=4a02σε2x12x22−x1Tx22x22.Using Eq. (46) and Eq. (48), the probability of localization error in Eq. (45) can be rewritten as
(51)Pe=Pη<ξ=∫−∞ξ12πσe−η22σ2dη=Φξσ=Φa02x1Tx22−x12x22/x224a02σε2x12x22−x1Tx22/x22=Φ−a02σεx12x22−x1Tx22x22,where Φ· is the standard normal distribution function.Assume that the actual nearest neighbor of the online datay in the radio map X is x2, when the localization system wrongly detect the fingerprint x1 is the nearest neighbor, the probability of error detection is shown in Eq. (51). Generally, there are n fingerprints in the radio map X. Assume that the fingerprint xi in the radio map X is the nearest neighbor of the online data y. Then, an error occurs when any other fingerprint xj in the radio map X is chosen as the nearest neighbor of y. Therefore, the probability of error detection is
(52)Pei,j=Φ−ai2σεxi2xj2−xiTxj2xj2,i,j=1,2,⋯,n,i≠j.Each of the standard normal distribution functionΦ represents the probability of wrongly detecting the fingerprint xj as the nearest neighbor of the online data y when the actual nearest neighbor is the fingerprint xi. In the radio map X, if the fingerprint is closer to the online data y, it is determined as the nearest neighbor by the localization system with higher probability; so, when an error occurs, the probability of error detection is larger. This is because the fingerprints in the nearest neighbor set A calculated by Eq. (23) have a high probability to be the nearest neighbor; so, these fingerprints in A contribute most of the probability of error detection in Eq. (52) and should be dealt with carefully. Therefore, it is possible to obtain a more accurate nearest neighbor set by using the preprocess of RSS values, so as to realize the linear regression of RSS values more precisely.


## 6. Experimental Results and Analysis

The effectiveness of the proposed LR method is studied and analyzed through experiments and simulations in this section. Figure8 shows the indoor localization experiment system. The localization area is the corridor with 49.4 m in length and 14.1 m in width, which is illustrated with yellow color. In the offline phase, we deployed 27 access points (Linksys WRT54G) with IEEE 802.11b/g mode. As we can see from Figure 9, in the indoor positioning system, the larger the interval between two adjacent reference points in radio map, the lower the final positioning accuracy, but the interval cannot be too small; therefore, the corridor is divided into several grids of 0.5m×0.5m, which means the interval between any two adjacent reference points is 0.5 m, and 823 reference points are set in the corridor. At each RP, 100 RSS values are collected from all APs for each orientation by using a Lenovo laptop, so that 400 samples of RSS reading per RP are collected as the raw RSS readings. Then, the radio map is built based on the RSS values and their corresponding coordinates. In the online phase, four distinct test devices, namely, Huawei, Samsung, Xiaomi, and Coolpad are used to estimate the user’s location and are verified with the proposed LR method. At the same time, the Lenovo laptop is used to obtain the optimal localization result for comparison. In our experiment, we take the RSS values in one direction to test the proposed LR method.Figure 8
Floor plan for indoor localization, where the area colored in yellow is used for testing.Figure 9
Illustration of the reference point distribution in the interesting area for localization.To verify the LR method, several RSS values are collected by the test devices and are used to find the candidate fingerprints in the radio map at the beginning. Based on the candidate fingerprints and the measured data, the linear regression coefficients are calculated. Then, the signal space of the radio map and the online RSS values can be mapped to the same signal space, and we can obtain the accurate localization result.Next, we take (Lenovo, Huawei) pair as an example to illustrate the effectiveness of the LR algorithm. As a comparison, the linear regression coefficients are calculated by the LTS algorithm and LLS algorithm, and the linear regression functions are shown in Figure10. In Figure 10, compare with the result of the LTS algorithm, the linear regression function calculated by the LLS algorithm is closer to the outliers, which result in a large error. The LLS algorithm is more susceptible to the outliers, and this is due to the fact that the LLS algorithm deals with all the measured RSS values equally without any special treatment of the outliers. After getting the linear regression functions, the signal space of the radio map can be mapped to the signal space of the online RSS data.Figure 10
Linear correlation between Huawei and Lenovo.In order to demonstrate the ability of linear regression algorithm more intuitively, the comparison of RSS values before and after using LTS algorithm is illustrated in Figure11. In Figure 11, the distributions of Huawei device and Lenovo device are -62 dBm to -55 dBm and -51 dBm to -41 dBm. Obviously, the minimum and maximum RSS difference between Huawei device and Lenovo device is 4 dBm and 21 dBm, respectively. If the radio map is built by the Lenovo device and the user’s location is estimated by Huawei device, the localization accuracy is considerably low. Using the LTS algorithm, the RSS values collected by Lenovo device are transformed, and the signal distributions of Huawei device and Lenovo device are basically the same. As a result, the localization accuracy can be improved significantly.Figure 11
Comparison of signal distributions.After applying the LTS algorithm, the RSS values in the radio map are transformed, and the KNN algorithm (K=3) is used to estimate the user’s current location. As a comparison, the LLS algorithm and the RSS ratios are also used to solve the device diversity problem. The error between the estimate and the truth locations is expressed by Euclidean distances. The CDF curves of the localization error of all algorithms are displayed in Figure 12. When the devices used to build the radio map and estimate the user’s current location are the same, we can obtain the optimal solution, as the red line shown in Figure 12. As we can see from the rest caves in Figure 12, if the devices used in the offline phase and the online phase are different, the localization accuracy of the crowdsourcing localization system is greatly reduced. In this paper, we do our best to eliminate the device diversity problem, so that the localization accuracy can be as close as possible to the optimal result. As we can see from Figure 12, the localization accuracy has been improved by applying different algorithms. It is clear that the proposed LTS algorithm outperforms the other methods, and the localization accuracy is closest to the optimal solution. Notably, the maximum localization error has been reduced from 10 m to 4.5 m, and the average error is reduced from 3.72 m to 2.31 m.Figure 12
Comparison of the proposed algorithm with other algorithms.In Eq. (24), the correlation coefficient threshold rth is set to choose the nearest neighbor fingerprints in the radio map for the online RSS data. However, if all the correlation ratios calculated by Eq. (23) are less than rth, then A=∅. To be guaranteed A≠∅, we choose 10% of the fingerprints with the highest r to form the candidate nearest neighbor set. The CDF curves of the localization error using different size of A are plotted in Figure 13. As shown in Figure 13, since more fingerprints with low probability to be the nearest neighbors are included in A, the localization accuracy decreases as the candidate set size increases.Figure 13
Localization performance for different numbers of candidate nearest neighbors.The probability of error detection in Eq. (52) for all fingerprints in the radio map is shown in Figure 14. In the simulation, since the variance of the noise has no effect on the trend of the probability distribution, we set σε=10. In addition, we assume that all the RSS values collected in the online phase have an ideal nearest neighbors in the radio map; that is NNy=xi, so we set ai=1 for all i=1,2,⋯,n. Because Pei,j has no physical meaning when i=j, we make Pei,i=0 when drawing Figure 14. From Figure 14, it can be concluded that the probability of error detection of fingerprints closer to the nearest neighbor is higher than others, which means that these fingerprints are more likely to be detected as the nearest neighbors. Thus, the fingerprints in the nearest neighbor set in Eq. (24) contribute the most errors in Eq. (52) and should be chosen more carefully.Figure 14
Probability of error detection.


## 7. Conclusions

In this paper, the linear regression (LR) method is proposed to overcome the device diversity problem for the RSS fingerprint-based WLAN indoor localization system using crowdsourced data. The intuition behind this technique is that the RSS values between different devices have a linear relationship. The Pearson correlation coefficient is used to label the RSS values with rough location estimation at the beginning, and the regression coefficients are calculated by the LTS algorithm. Based on the LR algorithm, the RSS values collected by distinct devices can be shifted into the same signal space, and the device diversity problem can be solved. We did a theoretical study of the probability of error detection, and the proposed algorithm is validated through it. Furthermore, we tested the proposed method in a typical office environment, and the experimental results demonstrate that the proposed method leads to significant improvements in localization accuracy.



---

*Source: 5530396-2021-04-08.xml*