# Wireless Localization Method Based on AHP-WKNN and Amendatory AKF

Authors: Su Pan; Sheng Hua; Duowei Pan; Xixia Sun
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

In this paper, we propose an AHP-WKNN method for indoor localization which combines the Analytic Hierarchy Process (AHP) technique and the WeightedK-nearest Neighbor (WKNN) algorithm. AHP serves to assign weights when WKNN is employed to select fingerprints for indoor positioning. The AHP technique can reasonably enlarge the influence that the received signal strength (RSS) gap between reference points has on the weights, achieving better performance in positioning. This paper also modifies the adaptive Kalman filter (AKF) noise reduction method by correcting the output based on the error between the RSS measurement and the expected output. The modified AKF can track the changes of RSS more effectively and achieve better performance of noise reduction. The simulation result shows that the proposed AHP-WKNN method and the modified AKF can improve positioning accuracy effectively.


---

## Body

## 1. Introduction

The demand for high-precision positioning and navigation in the indoor scenario is increasing along with the popularization of the Internet of things. The WLAN-based indoor positioning can fully make use of the widely deployed Access Points (AP) to achieve high positioning performance [1, 2]. So far, the localization based on WLAN has two main methods—the triangulation method and fingerprinting localization. The triangulation method uses the distances between the test point and three known APs to estimate the location of the test point. The distance here is estimated by measuring the received signal strength (RSS) of the APs. This method relies heavily on the accurate signal path loss model. There are a lot of factors that may affect the signal path. The signal path loss model varies under different environments, and building an accurate and suitable model can be very difficult. Therefore, it is very hard to apply the triangulation method based on indoor localization in reality. Recently, the indoor positioning system based on WLAN, which uses fingerprint (formed by the coordinates of the reference points (RPs) and the APs’ signal strength received at RPs) as the recognition method, has become a research hotspot [3, 4]. It involves two phases named the offline phase and the online phase. In the offline phase, the main task is to build a fingerprint database, which preserves the mapping between the RSS space and the location space. The location space is made up of all RPs’ position coordinates, and the RSS space is made up of the AP’s signal strength measured at RPs. The location of each RP corresponds to a group of RSS measured from APs. In the online phase, the user terminal senses the RSS and further matches it with the RSS space in the database; then, a suitable fingerprint matching method is applied to compute the user’s position. The suitable fingerprint matching method is the Weighted K-nearest Neighbor (WKNN) algorithm, a machine learning-based algorithm. The localization process of the extant WKNN is to first measure the Euclidean distances between the RSS measured at the test points and the RSS of each RP in the fingerprint database. Then, the process sorts those Euclidean distances in ascending order. The first k coordinates of the RPs with the smallest Euclidean distances are chosen. Different weights are then assigned to those k coordinates. The weights are inversely proportional to the Euclidean distance of the RPs. Finally, the position of the test point is the weighted mean of the coordinates of k RPs.However, the WKNN mentioned above is not optimal. In most precise positioning scenarios, the RPs are deployed with high density. The differences between the assortedk Euclidean distances are not big enough. The weights assigned to the k RPs in the existing papers [5–9] are thereby almost the same, and the weighted sum of the location coordinates is almost equal to the average of the location coordinates. Our simulation results show that this method leads to inaccurate location results. As a result, it is necessary to properly enlarge the effect that the differences between these selected k Euclidean distances have on the localization process. Therefore, this paper proposes an AHP-WKNN method which adopts the Analytic Hierarchy Process (AHP) technique [10–14] to assign weights to the k RPs. In this method, we choose the optimal position estimation of the test point as the target layer, the RSS value measured at all APs as the criterion layer, and the first k RPs’ coordinates as the scheme layer. We then set the relative importance of elements in the positioning subjectively and determine whether this setting is consistent with mathematical logic by the consistency check. The weights of the k RPs’ coordinates in the scheme layer can then be calculated through solving the judgment matrix. It is obvious that the AHP technique adds the subjective components in the objective mathematics framework; thus, it properly enhances the effect that RSS difference of k RPs has on weights and achieves a better effect on localization compared to the existing methods.The second problem of indoor localization is that the noise in the measurement of the RSS will lower the accuracy of WKNN. The existing works [15, 16] use the adaptive Kalman filter (AKF) to reduce the noise. AKF includes three phases: prediction, correction, and noise covariance estimation. In the prediction phase, AKF utilizes the estimation of the real RSS vector at the previous moment X^t−1 to calculate the prior RSS vector estimation X^t∣t−1 at the current moment. During the correction phase, based on the current measurement of RSS Zt, Z^t expectation of X^t∣t−1 (the expected output of AKF at the current moment), and the Kalman gain matrix, AKF gives the current estimation of real RSS X^t (the output of AKF); after that, AKF updates the covariance matrix of the noise and uses the result for the next iteration.However, the estimation errors that exist during the iteration process are transitive, and the transition of these errors will affect the number of iterations that AKF needs to achieve the convergence state and the accuracy of the output result. Therefore, the AKF method in works [15, 16] is not effective enough. From the iteration process of AKF, we can see that X^t∣t−1 is determined by the output X^t−1 at moment t−1. If εt (the error between Zt and Z^t) at moment t is too large, then X^t−1 is inaccurate. X^t−1 should be corrected to prevent errors from passing to the next iterations. Based on the analysis above, an amendatory AKF method is proposed in this paper. We set a judgment rule for εt. If ε^t (the covariance of εt) exceeds the judgment rule, X^t∣t−1 is inaccurate. We will adjust X^t−1 and recalculate X^t∣t−1 [17]. Compared to the AKF in works [15, 16], one comparison and one amendment are added to each iteration in the proposed algorithm, and the noise reduction effect of the amendatory AKF is higher than that of the AKF in [15, 16], which leads to better performance of WKNN-based localization.The main contributions of this paper are as follows. (i) This paper proposes an AHP-WKNN algorithm. The AHP technique is used to enhance the effect that the RSS difference between the test points and RPs has on the positioning process by assigning weights for different RP coordinates and thus improves the localization accuracy for the current WKNN algorithms. (ii) By setting a judgment rule to the errorεt between the expected outputs and measurements, this paper conducts an amendment to the prior estimation of real RSS vectors. Thus, it improves the accuracy of the output of the AKF method and thereby improves the accuracy of the WKNN algorithm.


## 2. System Model

The fingerprint-based indoor localization system includes the offline phase and the online phase. During the offline phase, the RSS from AP is collected at the known RPs to form the fingerprint database. One fingerprint includes the coordinate of one RP and a series of RSS from APs measured at this RP. Therefore, there are two spaces in the fingerprint database mapping to each other, and these two spaces are the location space and the RSS space, respectively. Assuming there areM APs and N RPs, then the fingerprint database is expressed as follows:
(1)FP=LRSS=LRSS1TRSS2T⋯RSSMT,where the location space L∈ℝN×1 is made by N position coordinate vectors of RPs. RSS∈ℝN×M is the RSS space, including M RSS vectors. RSSi∈ℝ1×N records the observed RSS values from the ith AP as
(2)RSSi=rssi1⋯rssij⋯rssiN,where rssij represents the RSS from the ith AP measured at the jth RP (i=1,⋯,M, j=1,⋯N). ·T represents the matrix transpose.In the online phase, the user terminal compares the RSS measured at the test point with the RSS in the fingerprint database built in the offline phase and then choosesk RPs by considering the minimum Euclidean distance between the RSSs of these RPs and the RSS of the test point. Based on those k chosen RPs’ coordinates and their weights, the optimal position of the test point could be expressed as
(3)P^=∑i=1kβipi,where P^ is the optimal position estimation of the test point, pi is the coordinates of the ith RP, k is the number of the chosen RPs, and βi is the weight assigned by the algorithm for the ith RP.


## 3. AHP-WKNN

### 3.1. Localization Procedure of Extant WKNN

Assume that the RSS of theith AP measured at the test point is zi, i=1,⋯,M, and M is the number of the APs. Then, the Euclidean distance between the RSS of the test point and the RSS of the jth RP in the fingerprint database is
(4)disj=∑i=1Mzi−rssij2,where j=1,⋯N, N is the number of RPs. Those Euclidean distances are sorted in ascending order, and the first k coordinates of the RPs with the smallest Euclidean distances are chosen to estimate the position of the test point. Apparently, the coordinate with a smaller Euclidean distance has a larger weight, and the coordinate with a larger Euclidean distance has a smaller weight. In [5], the weight is equal to the normalized Euclidean distance and can be expressed as the following equation:
(5)wi=disi−1∑i=1kdisi−1.Assuming that the coordinate of the ith RP is xi,yi, i=1,⋯k, the position estimated by WKNN is
(6)x^=∑i=1kwixi,y^=∑i=1kwiyi,where x^i,y^i is the coordinate of the test point’s estimated position.


### 3.2. Problem Statement

From Section3.1, it is easy to see that the coordinate of the test point is the weighted mean of selected k RP coordinates. The weights are related to the RSS differences between the test point and the RPs. Since the differences of those Euclidean distances are not big enough, the differences of weights given by (5) are almost the same. According to our simulation, it is necessary to properly enhance the effect that the RSS difference has on the weights to improve the accuracy of the WKNN algorithm.


### 3.3. Hierarchical Model of AHP

We propose to use the AHP technique to realize this goal. Based on their functions on the positioning, factors involved in the indoor localization process are separated into a target layer, criterion layer, and scheme layer [10]. The judgment matrix is formed subjectively based on the relative importance of factors. Then, the consistency check is applied to determine the mathematical rationality of the judgment matrix. The weight of factors in positioning is obtained through matrix calculation. This method can subjectively enhance the influence that RSS differences have on their weights within an objective mathematical framework. The main steps are shown as follows:
(1)
Constructing the hierarchical structure model: calculating the optimal position of the test point is the target layer. Here, we set 4 APs and select 3 nearest RPs to participate in the localization process. Then, the 4 RSS measured at the four APs (RSS1, RSS2, RSS3, and RSS4) constitute the criterion layer, and the coordinates of three RPs are the scheme layer. The system structure model is shown in Figure1(2)
Constructing the judgment matrix: here, we denoteCk as the kth judgment matrix in the scheme layer. When the scheme layer is making decisions based on the RSS received from the kth AP, the element cijk (k=1,2,3,4, i,j=1,2,3) in Ck represents the degree of relative importance between the coordinate of RPi and the coordinate of RPj. We then denote B as the judgment matrix for the criterion layer. When RSSi and RSSj are used to make decisions by the target layer, the element bij (i,j=1,2,3) in B represents the degree of relative importance between RSSi and RSSj. The degree of relative importance is represented by integers from 1 to 9, and their reciprocal values are represented by one over 1 to 9. The possible values of the elements in the judgment matrix are shown in Table 1Figure 1
AHP model for optimal position estimation.Table 1
Possible values of the elements in the judgment matrix.
ValuesMeaning1The two elements are equally important3When comparing two elements, the former one is slightly more important5When comparing two elements, the former one is more important7When comparing two elements, the former one is particularly more important9When comparing two elements, the former one is significantly more important2, 4, 6, 8Represents the median of adjacent values mentioned aboveReciprocalWhen comparing elementi to element j, if the importance ratio between them is aij, then the ratio between j and i is 1/ajiBased on Table1, since the four APs have the same contribution, all elements in B of the criterion layer are set subjectively to 1. The judgment matrix B of the criterion layer is shown in Table 2.Table 2
Judgement matrixB of the criterion layer.
RSS1RSS2RSS3RSS4RSS11111RSS21111RSS31111RSS41111Since the four APs have the same contribution,Ck is the same for different k, which means C1=C2=C3=C4. The weights of RP’s coordinates in the positioning process are inversely proportional to the Euclidean distance between the RP and the test point. Hence, coordinate 1 is more important than coordinate 2 (with the middle Euclidean distance), and coordinate 2 is more important than coordinate 3 (with the largest Euclidean distance). Based on the analysis above, the effect that the RSS difference has on weights should be enhanced. Therefore, the judgment matrix for Ck of the scheme layer is set subjectively in Table 3.
(3)
Determining whether the elements in the judgment matrix are mathematically reasonable through the consistency check: assuming the weight of elementi to element l is ail and the weight of element l to element j is alj, then the weight of element i to element j should be aij=ail∗alj. If that is the case, we say the matrix is mathematically consistent. Mathematically, for the matrix that satisfies aij=1/aji, λmax=n is the necessary requirement for aij=ail∗alj. Here, λmax is the largest eigenvalue for the judgment matrix and n is the dimension of the judgment matrix [10–12]. However, since the elements in the judgment matrix are set subjectively, it is likely that λmax≠n. We thus use CI=λmax−n/n−1 to measure how close λmax is to n, which means we are examining the consistency degree of the matrix. The degree can vary with n. Table 4 gives the average degree of consistency of RI for different n. We use the ratio CR=CI/RI to check the consistency of the judgment matrix. CR reflects the range of the matrix’s consistency. If CR<0.10, the judgment matrix can be adopted; if CR≥0.10, the judgment matrix is not reasonable, and it needs to be kept adjusted until CR<0.10.(4)
Since the final goal is to get the weight of each RP’s coordinate (the bottom layer) for the target layer (the top layer), we then compute the weight of each element for the upper layer. Because the values of the judgment matrix in this layer reflect the relative importance of the elements in the current layer when making decisions against the upper layer, we can use the normalized vectorWk′ of the eigenvector Wk, which corresponds to the largest eigenvalue λmaxk of the judgment matrix in the current layer to represent the weight vector for the judgment matrix. The ith value wki′ of Wk′ represents the ith attribute’s weight in the current layer for the kth attribute in the upper layer. For example, the weight vector of the judgment matrix Ck is calculated as follows:(i)
CalculatingCk’s largest eigenvalue λmaxk’s corresponding eigenvector Wk, where λmaxk and Wk satisfy the following:(7)CkWk=λmaxkWk.(ii)
Normalizing theith value wki of Wk to get Wk′’s ith valuewki′:(8)wki′=wki∑j=1nwkj.Table 3
Judgement matrixCk of the scheme layer.
Coordinate 1Coordinate 2Coordinate 3Coordinate 1135Coordinate 21/313Coordinate 31/51/31Table 4
Possible values ofRI.
Dimensions123456789RI000.520.891.121.241.361.411.46wki′represents the weight of the ith RP’s coordinate in the scheme layer for the RSS from the kth AP in the criterion layer, where k=1,2,3,4, i=1,2,3. The judgment matrices Ck of the scheme layer are the same for k=1,2,3,4, so the corresponding weight vectors Wk′ are the same. Since there is only one attribute in the target layer, the judgment matrix B of the criterion layer only has one weight vector WB′, and its kth value wbk represents the weight of the RSS of the kth AP in the criterion layer for the target layer.
(5)
Based onWB′ and Wk′, we calculate the weights of three RPs’ coordinates in the scheme layer to realize localization. Each weight of the 3 RPs’ coordinates for the target layer could be expressed as(9)wi=∑k=14wbkwki′,where k=1,2,3,4 and i=1,2,3. Those three weights then can be used in (6) to estimate the optimal position of the test point.


## 3.1. Localization Procedure of Extant WKNN

Assume that the RSS of theith AP measured at the test point is zi, i=1,⋯,M, and M is the number of the APs. Then, the Euclidean distance between the RSS of the test point and the RSS of the jth RP in the fingerprint database is
(4)disj=∑i=1Mzi−rssij2,where j=1,⋯N, N is the number of RPs. Those Euclidean distances are sorted in ascending order, and the first k coordinates of the RPs with the smallest Euclidean distances are chosen to estimate the position of the test point. Apparently, the coordinate with a smaller Euclidean distance has a larger weight, and the coordinate with a larger Euclidean distance has a smaller weight. In [5], the weight is equal to the normalized Euclidean distance and can be expressed as the following equation:
(5)wi=disi−1∑i=1kdisi−1.Assuming that the coordinate of the ith RP is xi,yi, i=1,⋯k, the position estimated by WKNN is
(6)x^=∑i=1kwixi,y^=∑i=1kwiyi,where x^i,y^i is the coordinate of the test point’s estimated position.


## 3.2. Problem Statement

From Section3.1, it is easy to see that the coordinate of the test point is the weighted mean of selected k RP coordinates. The weights are related to the RSS differences between the test point and the RPs. Since the differences of those Euclidean distances are not big enough, the differences of weights given by (5) are almost the same. According to our simulation, it is necessary to properly enhance the effect that the RSS difference has on the weights to improve the accuracy of the WKNN algorithm.


## 3.3. Hierarchical Model of AHP

We propose to use the AHP technique to realize this goal. Based on their functions on the positioning, factors involved in the indoor localization process are separated into a target layer, criterion layer, and scheme layer [10]. The judgment matrix is formed subjectively based on the relative importance of factors. Then, the consistency check is applied to determine the mathematical rationality of the judgment matrix. The weight of factors in positioning is obtained through matrix calculation. This method can subjectively enhance the influence that RSS differences have on their weights within an objective mathematical framework. The main steps are shown as follows:
(1)
Constructing the hierarchical structure model: calculating the optimal position of the test point is the target layer. Here, we set 4 APs and select 3 nearest RPs to participate in the localization process. Then, the 4 RSS measured at the four APs (RSS1, RSS2, RSS3, and RSS4) constitute the criterion layer, and the coordinates of three RPs are the scheme layer. The system structure model is shown in Figure1(2)
Constructing the judgment matrix: here, we denoteCk as the kth judgment matrix in the scheme layer. When the scheme layer is making decisions based on the RSS received from the kth AP, the element cijk (k=1,2,3,4, i,j=1,2,3) in Ck represents the degree of relative importance between the coordinate of RPi and the coordinate of RPj. We then denote B as the judgment matrix for the criterion layer. When RSSi and RSSj are used to make decisions by the target layer, the element bij (i,j=1,2,3) in B represents the degree of relative importance between RSSi and RSSj. The degree of relative importance is represented by integers from 1 to 9, and their reciprocal values are represented by one over 1 to 9. The possible values of the elements in the judgment matrix are shown in Table 1Figure 1
AHP model for optimal position estimation.Table 1
Possible values of the elements in the judgment matrix.
ValuesMeaning1The two elements are equally important3When comparing two elements, the former one is slightly more important5When comparing two elements, the former one is more important7When comparing two elements, the former one is particularly more important9When comparing two elements, the former one is significantly more important2, 4, 6, 8Represents the median of adjacent values mentioned aboveReciprocalWhen comparing elementi to element j, if the importance ratio between them is aij, then the ratio between j and i is 1/ajiBased on Table1, since the four APs have the same contribution, all elements in B of the criterion layer are set subjectively to 1. The judgment matrix B of the criterion layer is shown in Table 2.Table 2
Judgement matrixB of the criterion layer.
RSS1RSS2RSS3RSS4RSS11111RSS21111RSS31111RSS41111Since the four APs have the same contribution,Ck is the same for different k, which means C1=C2=C3=C4. The weights of RP’s coordinates in the positioning process are inversely proportional to the Euclidean distance between the RP and the test point. Hence, coordinate 1 is more important than coordinate 2 (with the middle Euclidean distance), and coordinate 2 is more important than coordinate 3 (with the largest Euclidean distance). Based on the analysis above, the effect that the RSS difference has on weights should be enhanced. Therefore, the judgment matrix for Ck of the scheme layer is set subjectively in Table 3.
(3)
Determining whether the elements in the judgment matrix are mathematically reasonable through the consistency check: assuming the weight of elementi to element l is ail and the weight of element l to element j is alj, then the weight of element i to element j should be aij=ail∗alj. If that is the case, we say the matrix is mathematically consistent. Mathematically, for the matrix that satisfies aij=1/aji, λmax=n is the necessary requirement for aij=ail∗alj. Here, λmax is the largest eigenvalue for the judgment matrix and n is the dimension of the judgment matrix [10–12]. However, since the elements in the judgment matrix are set subjectively, it is likely that λmax≠n. We thus use CI=λmax−n/n−1 to measure how close λmax is to n, which means we are examining the consistency degree of the matrix. The degree can vary with n. Table 4 gives the average degree of consistency of RI for different n. We use the ratio CR=CI/RI to check the consistency of the judgment matrix. CR reflects the range of the matrix’s consistency. If CR<0.10, the judgment matrix can be adopted; if CR≥0.10, the judgment matrix is not reasonable, and it needs to be kept adjusted until CR<0.10.(4)
Since the final goal is to get the weight of each RP’s coordinate (the bottom layer) for the target layer (the top layer), we then compute the weight of each element for the upper layer. Because the values of the judgment matrix in this layer reflect the relative importance of the elements in the current layer when making decisions against the upper layer, we can use the normalized vectorWk′ of the eigenvector Wk, which corresponds to the largest eigenvalue λmaxk of the judgment matrix in the current layer to represent the weight vector for the judgment matrix. The ith value wki′ of Wk′ represents the ith attribute’s weight in the current layer for the kth attribute in the upper layer. For example, the weight vector of the judgment matrix Ck is calculated as follows:(i)
CalculatingCk’s largest eigenvalue λmaxk’s corresponding eigenvector Wk, where λmaxk and Wk satisfy the following:(7)CkWk=λmaxkWk.(ii)
Normalizing theith value wki of Wk to get Wk′’s ith valuewki′:(8)wki′=wki∑j=1nwkj.Table 3
Judgement matrixCk of the scheme layer.
Coordinate 1Coordinate 2Coordinate 3Coordinate 1135Coordinate 21/313Coordinate 31/51/31Table 4
Possible values ofRI.
Dimensions123456789RI000.520.891.121.241.361.411.46wki′represents the weight of the ith RP’s coordinate in the scheme layer for the RSS from the kth AP in the criterion layer, where k=1,2,3,4, i=1,2,3. The judgment matrices Ck of the scheme layer are the same for k=1,2,3,4, so the corresponding weight vectors Wk′ are the same. Since there is only one attribute in the target layer, the judgment matrix B of the criterion layer only has one weight vector WB′, and its kth value wbk represents the weight of the RSS of the kth AP in the criterion layer for the target layer.
(5)
Based onWB′ and Wk′, we calculate the weights of three RPs’ coordinates in the scheme layer to realize localization. Each weight of the 3 RPs’ coordinates for the target layer could be expressed as(9)wi=∑k=14wbkwki′,where k=1,2,3,4 and i=1,2,3. Those three weights then can be used in (6) to estimate the optimal position of the test point.


## 4. Amendatory AKF Method to Reduce Noise

We apply the amendatory AKF method to remove the noise in RSS. Generally, the estimation errors in the AKF iterations are transitive, and the accumulation of these errors will affect the number of iterations that AKF needs to achieve the convergence state as well as the accuracy of the output result. Therefore, we set judgment rules to reduce accumulation of these errors and make the output of AKF closer to the real value.The AKF method utilizes the output obtained from the previous moment to adjust the current filtering parameters and adapts the statistical characteristics of the signals and noise. The AKF method has two basic assumptions. (1) The RSS vector at momentt can be expressed by the RSS vector at moment t−1, and the measured RSS vector at moment t can be expressed by the real RSS vector. (2) These expressions and measurements can be described by the linear algorithm.We denote the real RSS vector and the measured RSS vector received fromM APs at moment t as Xt and Zt, respectively. They can be expressed as
(10)Xt=FXt−1+Nt,Nt~N0,Qt,(11)Zt=HXt+Vt,Vt~N0,Rt,where Xt−1 is the real RSS vector at moment t−1. F is the state transition matrix. H is the measurement matrix, mapping the real vector to the observation space, which means it expresses the unmeasurable real value as the measurable value. Since there is only noise between the real value and the measured value and the only difference between measurements at different moments is the different random value of noise, an M-order identity matrix is used to represent F and H. The vector Nt is the process noise vector distributed with zero mean and the process covariance matrix Qt. The vector Vt is the observation noise vector distributed with zero mean and the measurement covariance matrix Rt.The AKF method includes three phases: prediction, correction, and noise covariance estimation. In the prediction phase, AKF calculates the prior RSS vector estimationX^t∣t−1 at moment t based on the real RSS vector estimation X^t−1 at moment t−1 and the prior estimation error covariance matrix Pt∣t−1 at the same time.
(12)X^t∣t−1=FX^t−1,(13)Pt∣t−1=FPt−1FT+Qt,where Pt−1=covXt−1−X^t−1. Pt−1 is the posterior estimation error’s covariance matrix at moment t−1. It reflects the accuracy of the output at moment t−1. Since the real RSS vector at any moment is not available, the initial value P0 of Pt−1 is difficult to obtain. Generally, when P0 is not a zero matrix, it will not affect the convergence of AKF [18]. Therefore, an M-order identity matrix is used to represent P0. The initial value of X^t−1 will be the measured value at the first time.During the update phase, we first calculate the expected measured RSS vectorZ^t at moment t, and then, we calculate the Kalman gain matrix Kt. Finally, we calculate the posterior RSS vector estimation X^t at moment t, which is the system output at moment t, and we update the posterior estimation error’s covariance matrix Pt at the same time:
(14)Z^t=HX^t∣t−1,(15)Kt=Pt∣t−1HTHPt∣t−1HT+Rt−1,(16)X^t=X^t∣t−1+KtZt−Z^t,(17)Pt=Pt∣t−1−KtHPt∣t−1.Finally, we updateQt and Rt for the next iteration:
(18)εt=Zt−Z^t,(19)Qt=1−dtQt−1+dtKtεtεtTKtT+Pt−FPtFT,(20)Rt1−dtRt−1+dtεtεtT−HPtHT,where εt is the error between Zt and Z^t. εt reflects the degree of the error between the expected output and measurement value. b is the forgetting factor in dt=1−b/1−bt+1. b is used to lower the influence that the output at the prior moment (old data) has on the input data (new data) which is needed for new iteration at moment t. As the number of iterations increases, the estimation error’s covariance matrix will become smaller and closer to the zero matrix. From Equations (15) and (16), we could see that Kt→0 when Pt∣t−1→0, and Kt will no longer work in the noise reduction process [19]. In another word, the old data will saturate AKF. Data saturation will cause new data to be ineffective in the iteration process. Therefore, in order to reduce the impact of old data, we introduce the forgetting factor b to fasten the convergence of AKF. The range for b is from 0.95 to 0.995, and we set it to be 0.975.εt reflects the degree that Z^t, the expected output at moment t, is away from the measurement value Zt. When the model parameters are not accurate or Zt fluctuates greatly (due to the existence of noise or the fluctuation of APs’ signals), εt will be large, and the output accuracy obtained by Equation (16) will be low. In order to improve the output accuracy, we should make a judgment rule based on εt. If ε^t (the covariance of εt) is greater than a threshold, X^t−1 should be amended, and X^t∣t−1 should be recalculated based on amendatory X^t−1. The process is shown in Figure 2.Figure 2
The proposed amendment process.Based on the analysis above, we set the judgment rules and amendment criterion to reduceεt, making the output of AKF closer to the real value. The amendment condition is based on the condition that the error between the expected value and the measurement is greater than a threshold. Define
(21)rt=Rt1,1,(22)gatet=μrt,where Rt1,1 is the element of the first row and first column of Rt and gatet is the threshold at moment t. The range of coefficient μ is 0.5~0.9, and it is used to balance the influence that the measurement value and expected output have on the AKF output. It is also used to increase trust in the measurement value. Since the AKF model is a simulation of the real environment, the coefficient cannot be exact; thus, the output relies on the measurement value. Therefore, increasing trust in the measurement value will make the output closer to the real value. In this paper, μ=0.8.Ifε^t≥gatet, it indicates that X^t−1 is inaccurate and should be adjusted as
(23)X^t−1′=X^t−1+ctεt,(24)ct=μrtRt1,1,where ε^t is the covariance of εt. X^t−1′ is used for the next iteration.We use Equations (12), (13), (14), (15), (16), (17), (18), (19), (20), (21), (22), (23), and (24) to reduce the noise in RSS at the test point. The noise-reduced RSS will then be applied in AHP-WKNN.


## 5. The Complete Algorithm

The module of the proposed algorithm is shown in Figure3. First, the amendatory AKF is used to reduce the noise of the RSS in the test point. AHP is then applied to assign weights for the chosen k RPs’ coordinates, and WKNN is used to estimate the optimal position.Pseudocode 1: The pseudocode of the proposed algorithm.
Input: measured RSS matrix Z at test point and fingerprint database FP.Output: the optimal position estimation P^1. Initializing the amendatory AKF and AHP, and setting the first column ofZ as the initial value for the X^t−1 in amendatory AKF;2.t⟵1;3.N⟵ the number of iterations of the amendatory AKF;4.whilet≤Ndo:5. setting the thresholdgatet based on Equations (21) and (22)6. reducing noises ofZt in the tth column of Z based on Equations (12), (14) and (16) and getting the output X^t;7. calculating the covarianceε^t of Equation (18);8. comparingε^t with gatet. If ε^t≥gatet, fix X^t−1 to get X^t−1′ based on Equations (23) and (24), and use X^t−1′ for the next iteration. Otherwise, use X^t−1 instead;9. updating Equation (13), (17), (19) and (20);t⟵t+1;11.end while12. Calculating the Euclidean distances betweenX∧′ and each fingerprint in the database. Sorting these distances and choose k nearest fingerprints’ coordinates;13. Based onX∧′ and k fingerprints, using AHP to build hierarchical model and judgment matrices;14. Examining the consistency of each judgment matrix and determining the weight vector of each judgment matrix based on Equation (7) and (8);15. Getting the weights ofk fingerprints’ coordinates that are needed to realize localization based on Equation (9);16. Based on thek coordinates and their corresponding weights, using Equation (6) to estimate the optimal position P^;17.returnP^.Figure 3
Module of the proposed algorithm.


## 6. Simulation Result Analysis

We simulate a30‐meter∗30‐meter room with 4 APs in its corners. 957 RPs are set in the room with a one-meter interval between them unless otherwise stated. The static propagation model [20] and the RSS measured at each RP are shown as follows:
(25)PLd0=GtGrλ24πd02,(26)lossij=PLd0+10disijd0,(27)rssij=PAP−lossij−noise,where lossij represents the path loss from the ith AP to the jth RP and disij represents the distance between the ith AP and the jth RP (i=1,2,3,4, j=1,⋯,957). PLd0 is the received power with distance d0, where d0 is 2 meters. Gt and Gr are the gain of the transmitting antenna and receiving antenna, respectively. Gt=Gr=1 in the paper. λ is the wavelength, and λ=c/f, where c is the velocity of light in vacuum and f is the 2.4 GHz of the carrier. n is the channel fading factor with range 2 to 5, and n=2 in this paper. rssij represents the RSS from the ith AP measured at the jth RP. PAP represents the transmit power of AP. PAP=30dBm without specific indication in this paper. noise is the white Gaussian noise with a mean of 0 and a variance of 0.1. A stationary test point is randomly set in the simulated room, and the signal strength received at the test point also follows the static propagation model [20] described by Equations (25), (26), and (27).We employ two methods to evaluate the accuracy of the localization: (1) the root-mean-square error (RMSE) expressed in Equation (28) between the estimated position and the actual position of the test point:
(28)RMSE=x−x∧2+y−y∧2,where x,y and x^,y^ are the coordinates of the test point’s actual position and estimated position, respectively, and (2) the probability of positioning error to assess the accuracy.The comparison of the noise reduction performance achieved by the standard KF, the existing AKF, and the amendatory AKF is shown in Figure4.Figure 4
Performance comparison of noise reduction by standard KF, existing AKF, and amendatory AKF.From Figure4, it can be seen that the result of the standard KF is not convergent. The existing AKF is better than the standard KF, but its output RSS fluctuates greatly and can be far away from the measured RSS. The amendatory AKF we proposed has outputs with stable fluctuation of RSS during the iteration process. The reasons are as follows: the standard KF is too simple to adapt the statistical characteristics of signals and noise during the noise reduction process. The existing AKF introduces the forgetting factor and noise covariance estimation into the standard KF. Using the output of the previous moment, the standard KF amends the current filtering parameters, and thus, it can adapt the statistical characteristics of signals and noise. However, when the RSS measured at the test point fluctuates, the existing AKF cannot adjust the filtering parameters in time. The amendatory AKF adds one comparison and one amendment process during every iteration. Thus, it can better track the change of RSS and achieve better performance of noise reduction.Figure5 reflects the effects that different noise reduction algorithms have on localization. The abscissa is the allowable positioning error (x), and its unit is meter; the ordinate is the probability that the error between the estimated position of the test point and the real position is smaller than x, i.e., Perror≤x.Figure 5
Performance comparison of localization by existing AKF and amendatory AKF.From Figure5, we can see that after using the amendatory AKF method to reduce noise at the test point, the positioning accuracy is better than that of having no noise reduction. When using the existing AKF, however, the positioning result fluctuates. Table 5 shows the comparison result of the RMSE generated by the existing AKF and amendatory AKF and without reducing noise, respectively.Table 5
RMSE comparison of the existing AKF and amendatory AKF and without noise reduction.
RMSENoisy0.746797Existing AKF0.706257Amendatory AKF0.599461Figure6 shows the influence that the intervals between RPs have on the positioning results.Figure 6
Influence of intervals between RPs on localization performance.It is straightforward that the average RMSEs are inversely proportional to the distance between RPs. From the point of view of machine learning, the smaller the distance is, the more fingerprints and information there are. Thus, when there is more training data for WKNN, the positioning accuracy is higher. We compare the RMSE between different algorithms, including WKNN, KNN (using the average coordinates of theK nearest neighbors to locate the test point), and NN (using the coordinate of the nearest neighbors to locate the test point). As can be seen from Figure 6, the average RMSE of the proposed algorithm is generally lower than that of the extant WKNN under different RP distances. The AHP technique reasonably expands the weight of the first RP during the positioning process, so that the difference between the weights of the k RPs is more obvious. The AHP technique adds the subjective components in the objective mathematics framework; thus, it properly enhances the effect that RSS difference of k RPs has on weights and helps to achieve a better effect on localization.Figure7 demonstrates the influence of different μ on the positioning results of the proposed algorithm.Figure 7
Influence ofμ on localization performance.It can be concluded from Figure7 that the proposed algorithm has a better positioning performance when μ is around 0.8. As μ is used to balance the influence that the measurement value and expected output have on the AKF output, relatively higher value of μ means that the output of AKF relies more on measurements.Figure8 shows the influence of different transmit powers of APs on the localization performance of the proposed algorithm.Figure 8
Influence of AP transmit power on localization.From Figure8, we can see that the transmit powers of different APs have little influence on the positioning performance. This is because the factor that determines the positioning accuracy is the differences of the RSS between fingerprints. The fingerprints and their weights are chosen based on this difference. However, this difference is not affected by the transmit power. Thus, there is no point to adjust transmit power for positioning accuracy.


## 7. Conclusions

This paper proposes an AHP-WKNN method for indoor localization in which the AHP technique is designed to assign weights for selecting RPs to locate the position of the test point. We can subjectively enhance the effect that the differences between RSS have on the weights during positioning by employing AHP. To deal with the noises that exist in the indoor positioning system, this paper proposes an amendatory AKF method to reduce the noise, which introduces one comparison and one amendment in each iteration. The simulation results suggest that compared to the original AKF, the amendatory AKF can better fulfill the requirements of noise reduction at the test point, and the AHP-WKNN method thus can help achieve a higher positioning accuracy.



---

*Source: 8859731-2021-05-24.xml*