# Research on WiFi Location Fingerprint Positioning Algorithm Based on DPC-FCM Clustering

Authors: Yaqin Wu; Zhenzhu Jia; Yangping Dai; Wenying Wang
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Aiming at the cost factors and difficulty of wireless positioning technology deployment, as well as the mismatch of similar fingerprints in RSS (received signal strength) indoor fingerprint positioning, the WiFi location fingerprint positioning algorithm based on DPC-FCM clustering is adopted. In this method, the fuzzyC-means (FCM) clustering is used instead of the traditional hard clustering algorithm, which can not only reasonably estimate the RSS feature of the cluster center, avoiding the error of the hard clustering algorithm, but also increase the difference between the reference points. Meanwhile, it can also reduce the complexity of feature matching. Aiming at the problem that the FCM algorithm is easily affected by the initial value and tends to converge to the local extreme value, the density peaks clustering (DPC) algorithm that can accurately characterize the initial center of the cluster is used to make up for the shortcomings of the FCM algorithm and improve the positioning accuracy. Experimental test results show that the positioning algorithm based on DPC-FCM clustering is more accurate than the positioning algorithm based on traditional clustering.


---

## Body

## 1. Introduction

As the Internet of Things (IOT) is widely applied in daily life, we have an increasing demand for indoor positioning, such as large multistorey shopping malls, large stadiums, and underground parking lots. In a complex indoor environment, satellite signals will be blocked by some obstacles such as walls. GPS and China’s Beidou navigation satellite system [1] cannot meet people’s needs for daily positioning in the indoor environment. Experts and scholars have conducted in-depth research on this issue and have proposed many positioning technologies for indoor complex environments, including RFID [2], ultrasonic, Bluetooth, infrared, WiFi [3], two-dimensional code positioning, visual positioning, and magnetic positioning [4]. With the popularization of WiFi technology, its low cost, high transmission speed, wide coverage, and easy deployment have quickly become the research focus of experts and scholars in the field of daily indoor positioning technology [5]. After comprehensive comparison of various WiFi-based indoor positioning technologies that are currently widely used, it could be found that the RSS-based location fingerprint positioning [6] method has the advantages of high positioning accuracy, which is not easily affected by indoor environmental factors, high stability, and low cost. It is a very key research method in the current wireless indoor positioning technology [7].The RSS-based fingerprint positioning method is to use the reference points at different locations to be affected by environmental obstructions, non-line-of-sight, etc., resulting in different RSS signal values of the collected receivable points. By using handheld terminal equipment to collect these signals, a database of the correspondence between the position of the reference point and the value of the RSS signal can be constructed [8]. However, because the neighboring nodes have a similar propagation environment, it is easy to lead to the problem of fingerprint mismatch due to similar position data during positioning. Moreover, in the fingerprint matching process, it is necessary to calculate the similarity between the node to be located and all the RSS signal values in the fingerprint database. The amount of calculation is huge, which increases the complexity of the algorithm and reduces the accuracy and real-time of positioning. Dong et al. proposes using the RSS sequence similarity of the auxiliary nodes adjacent to the coordinates to improve the difference between fingerprints [9], and Yan et al. proposes the use of machine learning algorithms to train the relationship between the position and the fingerprint of the reference point. These methods can increase the difference between similar nodes and will also reduce the real-time performance of online positioning and increase the algorithm complexity [10].A large number of experts and scholars have proposed to use clustering algorithms for data points to achieve presparseness of fingerprint databases. This method can greatly reduce the amount of positioning calculations, reduce the complexity of positioning algorithms, and also reduce the uncertainty of clusters and improve positioning accuracy. Liu et al. used theK-means++ algorithm to cluster the collected fingerprint data and store it in the fingerprint database [11]. In order to achieve better division of the fingerprint database and improve the positioning accuracy, many experts and scholars have proposed the idea of secondary division. For example, Li et al. proposed a WiFi positioning algorithm based on K-means and random forest clustering algorithm. Firstly, the fingerprint data is segmented for the first time by K-means algorithm. Then, based on the results of the first segmentation, the fingerprint data is segmented for the second time by random forest algorithm, thus improving the positioning accuracy [12]. K-means is widely used in indoor fingerprint positioning due to its simplicity and low complexity. However, indoor wireless signals are unstable, and the use of hard clustering algorithm to divide RSS fingerprints may cause deviation. Leon et al. proposed an idea of using soft clustering instead of hard clustering, divided the fingerprint database by FCM clustering algorithm, and estimated the RSS data characteristics of the clustering center according to the membership of all fingerprint data, so as to avoid the deviation caused by hard clustering [13]. Yang et al. proposed a kernel-based FCM fingerprint location method, which reduces the sensitivity of clustering to noise and outliers, improves the robustness of the positioning system, and verifies that it is more accurate than K-means and improve the positioning accuracy [14]. Zhang et al. proposed a random forest indoor positioning method based on density peak clustering. Based on the DPC clustering center, the RSS data was selected for fingerprint samples, the random forest model was trained through the fingerprint database, and the grid search and cross-validation technology were combined to find the best excellent RF positioning model [15]. At present, there are many researches on the application of clustering algorithms in fingerprint positioning methods at home and abroad. Most of them are based on fusion clustering and other machine learning algorithms to achieve positioning, which can achieve high positioning accuracy. However it will also increase the complexity of the algorithm and positioning system. The problem of fingerprint mismatch in RSS indoor fingerprint positioning has not been well resolved.Therefore, for online positioning to estimate the position of the point to be located, it is necessary to traverse the entire fingerprint database and the similar fingerprint mismatch problem is likely to occur in RSS indoor fingerprint positioning. In this paper, a positioning method based on the DPC-FCM clustering algorithm is proposed. Position information is added to the RSS feature to improve the difference between similar fingerprints. In the offline database building stage, the fingerprint database is divided into multiple subcategories by fuzzy clustering method. In the online positioning stage, the fingerprint data collected by the node to be located is matched with the class center of the clustering results in the above offline process, which is used to determine the nearest class center point, and then continue to find the fingerprint point closest to the point to be located in this class. As a result, the position of the point to be located is estimated.


## 2. Research on Location Fingerprint positioning algorithm Based on Clustering

### 2.1. Location Fingerprint Positioning

Fingerprint positioning can be divided into two stages, offline training and online positioning. In the offline phase, the RSS fingerprint information and coordinates of the preset reference point are recorded to establish a reference point fingerprint library. The RSS is received in the online phase, and the coordinates of the most matching reference point are found in the reference point fingerprint library to estimate the position of the node to be positioned. The positioning principle is shown in the Figure1. Assuming that S beacon points (BP) and M reference points are set in the environment to be located, the BP broadcasts the beacon in a certain period, and all the RSS data received by the reference point from the BP forms the fingerprint of the point. Since indoor positioning generally includes complex nonline-of-sight propagation and multipath interference, it will cause large deviations in the positions matched by similar fingerprints. Therefore, the reference point fingerprint library construction includes the coordinates of the reference point Xm=(xm,ym) and RSS fingerprint, as shown in
(1)xm,ymRm,1,⋯,Rm,s,⋯,Rm,S,m∈1,M,s∈1,S,where (Rm,1,Rm,2…,Rm,s,…,Rm,S) are RSS collections received at the mth reference point.Figure 1
Schematic diagram of indoor positioning based on location fingerprints.


### 2.2. FCM Clustering Algorithm

The FCM algorithm is a fuzzy clustering algorithm, also known as soft clustering [16], and FCM is the most widely used of many soft clustering methods. Its basic idea is as follows: according to the sample points having different membership degrees for different categories, the membership degrees of all sample points can be set, so that the sample points can be classified according to the size of the membership value. The FCM algorithm is described as follows:
(1)
First, determine the number of clustersq according to the total sample data set X (the data set contains m data) and then initialize the power exponent and the membership matrix U0=uik0. The general initialization membership matrix Uc0is a uniform random number on 0,1. The clustering center point V1 in the first step of iteration can be calculated by(2)vil=∑k=1nuikl−1mxk∑k=1nuikl−1m,i=1,2,⋯,q(2)
The membership matrixUl can be modified by the following equation (3), and then, the objective function Jl can be calculated by(3)uikl=1∑j=1qdikl/djkl2/m−1i=1,2,⋯,q;k=1,2⋯,n(4)JlUl,Vl=∑k=1n∑i=1quiklmdikl2,wheredikl=xk−vil(3)
The condition for terminating the iteration ismaxuikl−uikl−1<εu (εu represents the termination tolerance of membership), skip to step 2 if this condition is not metThe data set performs multiple iterations of the above steps to reach the minimum value of the objective function. At this time, the various cluster centersV and the membership matrix U are calculated to be the final result of the data set.The time complexity of FCM isOncd2i [17], where n is the number of data points,c is the number of clusters,d is the dimension, andi is the number of iterations.


### 2.3. DPC Algorithm

The DPC algorithm is simple and efficient. It can quickly find the density peak points of arbitrary shape data sets. Its basic idea is to find the cluster center, surrounded by adjacent points with low local density, and the data points with relatively large distance from any data points with higher density are regarded as ideal center points [18]. Therefore, in order to be able to determine the cluster center, it is necessary to calculate for each data point: the shortest distance δi between the local density ρi of the data point i and the point j with a higher local density [19].Since the cluster shape of the sample fingerprint database in this paper does not show a spherical distribution, the Gaussian kernel of formula (5) is used to calculate the sample density ρi,
(5)ρi=∑jϵIse−dij/dc2,(6)δi=minj:ρj>ρidij,where ρi is the local density of the ith data point. δiis the shortest distance between data point i and local density point j. After we get the ρi and δi from formulas (5) and (6), the data amount γwhich takes into account the ρ and δ of each data point is obtained by
(7)δi=minj:ρj>ρidij.In formula (7), γi is the comprehensive consideration value of the ith data point. The larger the value of data points γ, the more likely this point is to be selected as the cluster center point. So as long as it is arranged in descending orderγi=1N, the cluster center can be selected.The calculation of time complexity of DPC mainly depends on three aspects: first, calculate the distance time between two points; second, calculation of local densityγi of point i; and third, the time to calculate the distance δi of each point i. The time complexity of each part is O(n2), so the approximate time complexity of DPC is O(n2).


### 2.4. DPC-FCM Fusion Clustering Algorithm

In this paper, the FCM algorithm and a positioning method based on fusion clustering is proposed. The characteristics of DPC global search to determine the cluster center is used by this method and thus determines that the initial clustering center of the FCM clustering algorithm replaces the initial clustering center point randomly determined by the FCM algorithm itself, which can solve the problem that the FCM clustering algorithm is easily affected by randomness. The influence of the determined initial value leads to the problem of local merit, and the FCM algorithm is optimized. According to the fusion of DPC and FCM clustering algorithm to classify the reference points, the membership degree of the cluster center and the final cluster center of the data points in the cluster can be obtained, and then, the RSS feature of the cluster center is estimated according to the membership degree. Therefore, it also avoids the bias produced by the hard clustering algorithm. In the online stage, the RSS of the point to be located is first matched with the RSS feature of the cluster center and then matched with the RSS feature of the reference point in the class, so that the coordinate position of the node to be located can be estimated.The fused clustering algorithm can be divided into two stages to execute. The first stage is to calculate each fingerprint data pointρi and δi value. The larger the value of γ, the more likely the fingerprint point is to be selected as the cluster center point, so the initial cluster center of the clustering algorithm can be determined. The second stage is to execute the basic FCM clustering algorithm to complete the clustering.The detailed steps of the fusion clustering algorithm are as follows:The first stage: DPC algorithm is executed on all the data in the fingerprint database, so that the initial cluster center point of the fingerprint database can be determined.Input: sample fingerprint data setX.Output: cluster center pointqik.Step 1: the distance between all fingerprint points is calculated in the fingerprint database.Step 2: truncation distancedc is calculated.Step 3: the local densityρi of all fingerprint points in the fingerprint database and the distance δi from the nearest point of the fingerprint point when the local density is the same as the local density of the point itself are calculated.Step 4: comprehensive data valueγγi=ρiδi is calculated, and the decision diagram of all data in fingerprint database is drawn. Because the larger the γ value of data fingerprint point, the more likely it is to be selected as the initial clustering center, so qi(k) can be obtained.The second stage: standard FCM clustering algorithm is executed on fingerprint database.Input: fingerprint data setX, cluster center qik (obtained in the first stage), fuzzy index α, and iteration termination condition ε.Output: the final cluster centerC and membership matrix U of all fingerprint data.Step 1: let the number of iterationsk=1, the sample data set X, the initial cluster center determined in the first stage qii=1N and the termination condition of the iteration ε>0 are input.Step 2: according toqi(k), the membership degree uij of each fingerprint data point is calculated.Step 3: the cluster center matrixqik+1,I=1,⋯,q of the fingerprint database is updated according to the degree of membership uij.Step 4: the algorithm is terminated ifmax∣uijk−uijk−1∣≤ε. Otherwise, step 2 is executed.Step 5: the fingerprint database is iterated for many times, and the above steps are executed until the termination condition is met, and the clustering result of the final fingerprint database is obtained.Therefore, the process of the indoor fingerprint positioning method based on fusion clustering proposed in this paper is shown in Figure2.Figure 2
The flow chart of fingerprint location based on FCM-DPC clustering algorithm.


## 2.1. Location Fingerprint Positioning

Fingerprint positioning can be divided into two stages, offline training and online positioning. In the offline phase, the RSS fingerprint information and coordinates of the preset reference point are recorded to establish a reference point fingerprint library. The RSS is received in the online phase, and the coordinates of the most matching reference point are found in the reference point fingerprint library to estimate the position of the node to be positioned. The positioning principle is shown in the Figure1. Assuming that S beacon points (BP) and M reference points are set in the environment to be located, the BP broadcasts the beacon in a certain period, and all the RSS data received by the reference point from the BP forms the fingerprint of the point. Since indoor positioning generally includes complex nonline-of-sight propagation and multipath interference, it will cause large deviations in the positions matched by similar fingerprints. Therefore, the reference point fingerprint library construction includes the coordinates of the reference point Xm=(xm,ym) and RSS fingerprint, as shown in
(1)xm,ymRm,1,⋯,Rm,s,⋯,Rm,S,m∈1,M,s∈1,S,where (Rm,1,Rm,2…,Rm,s,…,Rm,S) are RSS collections received at the mth reference point.Figure 1
Schematic diagram of indoor positioning based on location fingerprints.


## 2.2. FCM Clustering Algorithm

The FCM algorithm is a fuzzy clustering algorithm, also known as soft clustering [16], and FCM is the most widely used of many soft clustering methods. Its basic idea is as follows: according to the sample points having different membership degrees for different categories, the membership degrees of all sample points can be set, so that the sample points can be classified according to the size of the membership value. The FCM algorithm is described as follows:
(1)
First, determine the number of clustersq according to the total sample data set X (the data set contains m data) and then initialize the power exponent and the membership matrix U0=uik0. The general initialization membership matrix Uc0is a uniform random number on 0,1. The clustering center point V1 in the first step of iteration can be calculated by(2)vil=∑k=1nuikl−1mxk∑k=1nuikl−1m,i=1,2,⋯,q(2)
The membership matrixUl can be modified by the following equation (3), and then, the objective function Jl can be calculated by(3)uikl=1∑j=1qdikl/djkl2/m−1i=1,2,⋯,q;k=1,2⋯,n(4)JlUl,Vl=∑k=1n∑i=1quiklmdikl2,wheredikl=xk−vil(3)
The condition for terminating the iteration ismaxuikl−uikl−1<εu (εu represents the termination tolerance of membership), skip to step 2 if this condition is not metThe data set performs multiple iterations of the above steps to reach the minimum value of the objective function. At this time, the various cluster centersV and the membership matrix U are calculated to be the final result of the data set.The time complexity of FCM isOncd2i [17], where n is the number of data points,c is the number of clusters,d is the dimension, andi is the number of iterations.


## 2.3. DPC Algorithm

The DPC algorithm is simple and efficient. It can quickly find the density peak points of arbitrary shape data sets. Its basic idea is to find the cluster center, surrounded by adjacent points with low local density, and the data points with relatively large distance from any data points with higher density are regarded as ideal center points [18]. Therefore, in order to be able to determine the cluster center, it is necessary to calculate for each data point: the shortest distance δi between the local density ρi of the data point i and the point j with a higher local density [19].Since the cluster shape of the sample fingerprint database in this paper does not show a spherical distribution, the Gaussian kernel of formula (5) is used to calculate the sample density ρi,
(5)ρi=∑jϵIse−dij/dc2,(6)δi=minj:ρj>ρidij,where ρi is the local density of the ith data point. δiis the shortest distance between data point i and local density point j. After we get the ρi and δi from formulas (5) and (6), the data amount γwhich takes into account the ρ and δ of each data point is obtained by
(7)δi=minj:ρj>ρidij.In formula (7), γi is the comprehensive consideration value of the ith data point. The larger the value of data points γ, the more likely this point is to be selected as the cluster center point. So as long as it is arranged in descending orderγi=1N, the cluster center can be selected.The calculation of time complexity of DPC mainly depends on three aspects: first, calculate the distance time between two points; second, calculation of local densityγi of point i; and third, the time to calculate the distance δi of each point i. The time complexity of each part is O(n2), so the approximate time complexity of DPC is O(n2).


## 2.4. DPC-FCM Fusion Clustering Algorithm

In this paper, the FCM algorithm and a positioning method based on fusion clustering is proposed. The characteristics of DPC global search to determine the cluster center is used by this method and thus determines that the initial clustering center of the FCM clustering algorithm replaces the initial clustering center point randomly determined by the FCM algorithm itself, which can solve the problem that the FCM clustering algorithm is easily affected by randomness. The influence of the determined initial value leads to the problem of local merit, and the FCM algorithm is optimized. According to the fusion of DPC and FCM clustering algorithm to classify the reference points, the membership degree of the cluster center and the final cluster center of the data points in the cluster can be obtained, and then, the RSS feature of the cluster center is estimated according to the membership degree. Therefore, it also avoids the bias produced by the hard clustering algorithm. In the online stage, the RSS of the point to be located is first matched with the RSS feature of the cluster center and then matched with the RSS feature of the reference point in the class, so that the coordinate position of the node to be located can be estimated.The fused clustering algorithm can be divided into two stages to execute. The first stage is to calculate each fingerprint data pointρi and δi value. The larger the value of γ, the more likely the fingerprint point is to be selected as the cluster center point, so the initial cluster center of the clustering algorithm can be determined. The second stage is to execute the basic FCM clustering algorithm to complete the clustering.The detailed steps of the fusion clustering algorithm are as follows:The first stage: DPC algorithm is executed on all the data in the fingerprint database, so that the initial cluster center point of the fingerprint database can be determined.Input: sample fingerprint data setX.Output: cluster center pointqik.Step 1: the distance between all fingerprint points is calculated in the fingerprint database.Step 2: truncation distancedc is calculated.Step 3: the local densityρi of all fingerprint points in the fingerprint database and the distance δi from the nearest point of the fingerprint point when the local density is the same as the local density of the point itself are calculated.Step 4: comprehensive data valueγγi=ρiδi is calculated, and the decision diagram of all data in fingerprint database is drawn. Because the larger the γ value of data fingerprint point, the more likely it is to be selected as the initial clustering center, so qi(k) can be obtained.The second stage: standard FCM clustering algorithm is executed on fingerprint database.Input: fingerprint data setX, cluster center qik (obtained in the first stage), fuzzy index α, and iteration termination condition ε.Output: the final cluster centerC and membership matrix U of all fingerprint data.Step 1: let the number of iterationsk=1, the sample data set X, the initial cluster center determined in the first stage qii=1N and the termination condition of the iteration ε>0 are input.Step 2: according toqi(k), the membership degree uij of each fingerprint data point is calculated.Step 3: the cluster center matrixqik+1,I=1,⋯,q of the fingerprint database is updated according to the degree of membership uij.Step 4: the algorithm is terminated ifmax∣uijk−uijk−1∣≤ε. Otherwise, step 2 is executed.Step 5: the fingerprint database is iterated for many times, and the above steps are executed until the termination condition is met, and the clustering result of the final fingerprint database is obtained.Therefore, the process of the indoor fingerprint positioning method based on fusion clustering proposed in this paper is shown in Figure2.Figure 2
The flow chart of fingerprint location based on FCM-DPC clustering algorithm.


## 3. Experiment and Analysis

### 3.1. Build a Fingerprint Database

The actual location scene of this paper is selected as the 8th floor of Yifu Experimental Building, as shown in Figure3. Two wireless routers and a data acquisition device are selected, and the model of this device is Huawei mobile phone P30. During signal acquisition, samples are collected from near to far at 1 m intervals, and five pieces of RSS fingerprint data are collected from east, south, west, and north at each reference point to get the average value. This can effectively reduce the influence of wireless signal fluctuation, thus establishing a high-quality fingerprint database.Figure 3
Experimental environment.


### 3.2. Database Partition Using Fusion Clustering

The DPC algorithm is used in this paper firstly which is one of fusion algorithm to process all sample points in fingerprint database, and calculatesρi value and δi value of all data points xi, respectively. Then, according to ρ value and δ value, the initial clustering center can be selected, and noise points can also be filtered, as shown in Figure 4.Figure 4
Calculate theρ and δ values of each fingerprint point.Theρ and δ of all fingerprint data points are calculated and plotted, as shown in Figure 4. The cluster center is the one whose ρ value and δ value are far away from the coordinate axis at the same time. The points near δ axis can be judged as abnormal points, while the points near ρ axis can be classified as ordinary points.In order to determine the cluster center more quickly and accurately, it is necessary to consider a quantityγ that combines ρ and δ. The larger its value, the more likely it is to be selected as the cluster center. Then, γi=1N is arranged in descending order, and the first few fingerprint data points are intercepted as the initial clustering centers, as shown in Figure 5.Figure 5
Sorting theγ value of each fingerprint point in descending order.It can be seen from Figure5 that the first five points of fingerprint data are taken as initial clustering centers in FCM clustering algorithm. At the same time, the best clustering number k=5 can be determined, and then, the FCM algorithm can be used to cluster the fingerprint database, thus completing the division of the fingerprint database.


### 3.3. Indoor Positioning Error Analysis

After the fingerprint database is divided, the target location coordinates need to be estimated, which is also the ultimate goal of indoor positioning. The positioning algorithm based on fusion clustering in this paper is used to perform positioning test analysis on part of the test sample points, and the error of each positioning point is shown in Figure6.Figure 6
Positioning errors of some test sample points.It can be seen from Figure6 that the localization error of some test sample points using the fusion clustering positioning algorithm of this paper is always within 2.5 m, which meets the accuracy requirements of indoor positioning.In order to better verify that the indoor fingerprint positioning algorithm based on fusion clustering in this paper can effectively improve the positioning accuracy,K-means clustering, FCM clustering, DPC clustering, and fusion DPC and FCM clustering algorithms are used for positioning. The error analysis is shown in Table 1.Table 1
The positioning effect based on 4 different clustering algorithms.
AlgorithmMaximum error (m)Minimum error (m)Average error (m)K-means4.771.252.37FCM3.891.151.83DPC3.541.171.74DPC-FCM2.360.851.31Table1 shows that among the four clustering algorithms, compared with the positioning algorithms based on K-means, FCM, and DPC clustering, the average error of the positioning algorithm based on DPC-FCM clustering is the smallest 1.31, which can achieve the best. Therefore, in this paper, the localization function is realized by the clustering algorithm of DPC and FCM.


## 3.1. Build a Fingerprint Database

The actual location scene of this paper is selected as the 8th floor of Yifu Experimental Building, as shown in Figure3. Two wireless routers and a data acquisition device are selected, and the model of this device is Huawei mobile phone P30. During signal acquisition, samples are collected from near to far at 1 m intervals, and five pieces of RSS fingerprint data are collected from east, south, west, and north at each reference point to get the average value. This can effectively reduce the influence of wireless signal fluctuation, thus establishing a high-quality fingerprint database.Figure 3
Experimental environment.


## 3.2. Database Partition Using Fusion Clustering

The DPC algorithm is used in this paper firstly which is one of fusion algorithm to process all sample points in fingerprint database, and calculatesρi value and δi value of all data points xi, respectively. Then, according to ρ value and δ value, the initial clustering center can be selected, and noise points can also be filtered, as shown in Figure 4.Figure 4
Calculate theρ and δ values of each fingerprint point.Theρ and δ of all fingerprint data points are calculated and plotted, as shown in Figure 4. The cluster center is the one whose ρ value and δ value are far away from the coordinate axis at the same time. The points near δ axis can be judged as abnormal points, while the points near ρ axis can be classified as ordinary points.In order to determine the cluster center more quickly and accurately, it is necessary to consider a quantityγ that combines ρ and δ. The larger its value, the more likely it is to be selected as the cluster center. Then, γi=1N is arranged in descending order, and the first few fingerprint data points are intercepted as the initial clustering centers, as shown in Figure 5.Figure 5
Sorting theγ value of each fingerprint point in descending order.It can be seen from Figure5 that the first five points of fingerprint data are taken as initial clustering centers in FCM clustering algorithm. At the same time, the best clustering number k=5 can be determined, and then, the FCM algorithm can be used to cluster the fingerprint database, thus completing the division of the fingerprint database.


## 3.3. Indoor Positioning Error Analysis

After the fingerprint database is divided, the target location coordinates need to be estimated, which is also the ultimate goal of indoor positioning. The positioning algorithm based on fusion clustering in this paper is used to perform positioning test analysis on part of the test sample points, and the error of each positioning point is shown in Figure6.Figure 6
Positioning errors of some test sample points.It can be seen from Figure6 that the localization error of some test sample points using the fusion clustering positioning algorithm of this paper is always within 2.5 m, which meets the accuracy requirements of indoor positioning.In order to better verify that the indoor fingerprint positioning algorithm based on fusion clustering in this paper can effectively improve the positioning accuracy,K-means clustering, FCM clustering, DPC clustering, and fusion DPC and FCM clustering algorithms are used for positioning. The error analysis is shown in Table 1.Table 1
The positioning effect based on 4 different clustering algorithms.
AlgorithmMaximum error (m)Minimum error (m)Average error (m)K-means4.771.252.37FCM3.891.151.83DPC3.541.171.74DPC-FCM2.360.851.31Table1 shows that among the four clustering algorithms, compared with the positioning algorithms based on K-means, FCM, and DPC clustering, the average error of the positioning algorithm based on DPC-FCM clustering is the smallest 1.31, which can achieve the best. Therefore, in this paper, the localization function is realized by the clustering algorithm of DPC and FCM.


## 4. Conclusion

In this paper, a WiFi indoor fingerprint positioning method based on the fusion of FCM and DPC algorithms is proposed. The DPC algorithm can accurately describe the initial center of the cluster and remove noise points and can make up for the lack of the FCM clustering algorithm to easily converge to a local level value. Therefore, fusing the DPC and FCM algorithms to cluster the reference points can effectively improve the positioning accuracy and reduce the complexity of small feature matching. The same fingerprint database was used to experiment and analyze the positioning effect of the positioning algorithm based onK-means clustering, FCM clustering, DPC clustering, and fusion of DPC and FCM clustering. The above experimental results show that the method in this paper has better positioning effect.



---

*Source: 8347084-2022-05-11.xml*