# Research on a Wi-Fi RSSI Calibration Algorithm Based on WOA-BPNN for Indoor Positioning
## 2 Methods and Algorithms
### Algorithms
#### 2.2.2 Region-Adaptive WKNN Algorithm Based on Hierarchical Clustering  
The WKNN algorithm is a further improvement based on the \(K\)-nearest neighbour (KNN) algorithm [22]. Different weighting factors are set according to the Euclidean distance of different fingerprint reference points relative to the current position. Compared with other fingerprint-based positioning algorithms, the WKNN algorithm has better positioning accuracy and stability. However, regardless of whether the WKNN or KNN algorithm is used, when performing the actual positioning, determining the value of K, which is the number of neighbouring reference points, is necessary. The value of \(K\) has an important influence on the positioning result. Thus, we propose an adaptive WKNN method that can utilise the feature of the Euclidean distance and physical coordinates between the real-time position and RSSI of the fingerprint database to adjust the value of \(K\) dynamically during the online positioning process, which can help to improve the positioning stability and obtain the best positioning accuracy.  
The algorithm steps of the region-adaptive WKNN algorithm based on hierarchical clustering are shown in Figure 3, and its process is described as follows:  
* **Step 1:** In the offline phase, a mobile terminal collects the average RSSI data of each Wi-Fi AP at each fingerprint point, match the RSSI of each fingerprint point with the physical two-dimensional coordinates to build an offline location fingerprint database.
* **Step 2:** Calculate the Euclidean distance between two fingerprint points, then merge the two fingerprint points with the smallest Euclidean distance into a new class and recalculate the centre point of the new class. Finally, obtain the RSSI of different area classes and centre points of each class.
* **Step 3:** In the online phase, the mobile terminal collects RSSI values from each Wi-Fi AP at a real-time position to form a set of RSSI data. Calculate the Euclidean distance \(D\) between the RSSI value of the real-time position and the RSSI value of the class \(CLASS\) centre point \(F\) in turn, as shown in Equation (13), then divide the real-time position into the class \(CLASS\) with the smallest Euclidean distance. \[D=\sqrt{\Sigma_{j=1}^{n}\left(rssi_{j}-RSSIi_{Fj}\right)^{2}}\] (13) where \(rssi_{j}\) is RSSI value of the \(j\)th Wi-Fi AP collected from the real-time position, \(RSSIF\) is the RSSI value of the \(j\)th Wi-Fi AP of the \(CLASS\) centre point \(F\) of class, and \(n\) is the number of Wi-Fi APs.
* **Step 4:** Sort the Euclidean distance from each fingerprint point to the real-time position in class \(CLASS\) in ascending order. Find the corresponding two-dimensional coordinates (\(x_{1}\), \(y_{1}\)) of the fingerprint points, calculate the distance \(d_{i}\), the average distance \(\overline{d}\) and the standard deviation \(S\) from the nearest neighbour point to the other fingerprint points, as shown in Equations (14)-(16). \[d_{i}=\sqrt{\left(x_{1}-x_{i}\right)^{2}+\left(y_{1}-y_{i}\right)^{2}}\] (14) \[\overline{d}=\frac{d_{2}+d_{3}+\ldots+d_{n}}{n-1}\] (15) \[S=\sqrt{\frac{\sum_{i=2}^{n}\left(d_{i}-\overline{d}\right)^{2}}{n-1}}\] (16)* **Step 5:** Filter the fingerprint points in class \(C\) further. When \(d_{i}>S\), delete the \(i\)th RSSI, otherwise, when \(d_{i}\leq S\), keep the \(i\)th RSSI. Finally, obtain \(K\) fingerprint points data, \(n\) is the number of Wi-Fi AP.
* **Step 6:** According to the Euclidean distance of the remaining \(K\) fingerprint points, calculate the corresponding weight factor and obtain the estimated two-dimensional coordinates of the real-time position.