1.

INTRODUCTION

With the rise of smartphone, Location Based Service (LBS) plays an important role in daily living, such as emergency rescue, personalized information delivery, shopping navigation and logistics industry¹. Mobile users desire for more adequate personal location information under certain circumstance. For instance, it can be a real-time shopping guide in an entertainment center or shopping mall².

The wireless localization systems can be deployed for outdoor and indoor environment based on various key technologies, including satellites, Wi-Fi, RFID, bluetooth and cellular³. Mature outdoor real-time positioning application includes GPS, BeiDou, Galileo and GLONASS, which provides location services for users anywhere on the earth⁴.

However, compared to maturely developed outdoor localization, research on indoor localization is still in a nascent phase, and several systems widely employed in outdoor environment can’t meet the accuracy requirements of indoor localization. Localization system based on Wi-Fi, due to its low cost and convenience, is considered to be the most potential to realize LBS in indoor environment⁵. Wi-Fi-based indoor localization techniques can be divided into two categories: range-based (arrival-based) and fingerprint-based. The basic idea of range-based technology is to obtain and calculate the distance of the transmitter and the receiver, the time of arrival (TOA), the angle of arrival (AOA) and the time difference of arrival (TDOA) are three typical methods⁶. However, these methods require strict time synchronization, which will cost much in equipment configuration. Therefore, on some occasions requiring low-cost and low-complexity, fingerprint-based localization technology is more suitable⁷.

However, in the complex indoor environment, there exists multiple access points (APs), and it costs much time to realize localization using fingerprint-based algorithm⁸. To shorten the positioning time and reduce the complexity of whole process, Li et al. proposed an AP selecting strategy based on variation, and it effectively reduces the scale of fingerprint database⁹. While Guo et al. focused on the online positioning stage and proposed improved K-means (K-means++) algorithm¹⁰. By partitioning the whole positioning zone, the procedure of matching algorithm was simplified. Inspired by these algorithms, a clustering algorithm based on Self-Organization Map (SOM) is proposed. By realizing partition localization, the complexity of online positioning is lowered. Meanwhile, an improved Weighted K-Nearest Neighbor (WKNN) algorithm is proposed to increase the positioning accuracy.

The rest of this paper is organized as follows. Section 2 describes new localization model in detail. Section 3 presents the experiment results and analysis. Finally, Section 4 draws conclusion and outlines future work.

2.

LOCALIZATION MODEL

2.1

SOM algorithm

Traditional WKNN algorithm compares the characteristic distance between reference point (RP) and test point (TP) to find optimal nearest RPs^11-12. However, it usually traverses the whole fingerprint database and costs much time. In order to lower the complexity of positioning, we choose clustering algorithm based on Self-Organization Map (SOM), which provides precise classification and effectively reduce the positioning time. The flow of SOM is depicted as Figure 1. Assuming that a set of Received Signal Strength (RSS) for one access point (AP) is R = {r₁,r₂,…,r_m}, where m is the number of AP. The training and testing data are firstly normalized by

Figure 1.

The flow of SOM.

where max(R) and min(R) represents the maximum and minimum value of the RSS in R respectively, and ave(R) represents the average of the RSS values in R. Next the node (clustering center) information is initialized. The node number can be set as 2-5 usually, and the initial clustering center can be randomly generated with the area of RPs. On finishing initializing the clustering system, the Euclidean distance D between RP and each clustering center is calculated by

where and represents the RSS of RP and clustering center. With regard to the nearest center, it is defined as “excited node (EN)”, while others are defined as “inhibited node (IN)”. Reasonably, the EN are supposed to be more approaching to the RP, while the IN should be more remote to the RP. In other words, the RP belongs to the cluster whose node is excited. Depending on whether the node is excited or inhibited, the RSS of each node is updated, which is described by

where represents RSS of node after updating and k represents the learning rate. Here, an adaptive learning rate is adopted. It gradually reduces as the iteration lasts, which is described by

where t represents the iteration times. Once the iteration meets the end condition, the clustering produces are accomplished. The fingerprint database is divided into several parts, which can be represented by the clustering center of corresponding cluster.

2.2

Improved WKNN algorithm

WKNN algorithm is the most commonly applied algorithm in indoor positioning^13-14. To further improve the positioning accuracy, an improved WKNN algorithm (AG-WKNN) is proposed. The weight of each RP is calculated and obtained by Gaussian distribution function. The flow of this algorithm is presented in Algorithm 1.

Algorithm 1: AG-WKNN

Specifically, the Gaussian distribution function can be described by

where a, b, c can be set according to different systems. w_k is the normalized f_k, which is depicted by

On this point, the estimated position of TPs can be obtained and the process of positioning is accomplished.

3.

THE EXPERIMENT RESULTS AND ANALYSIS

In order to verify the performance of proposed scheme, experiments were conducted on the sixth floor of Physics Building in Central South University, Changsha city, Hunan province, China. The layout of the environment is shown in Figure 2.

Figure 2.

Layout of the environment.

The environment includes a rectangular area, an east-west corridor and a south-north corridor which cover 15m×9m, 55m×2m and 30m×2m respectively. 73 RPs are 2.4m far from their neighbor and are shown in yellow. 215 TPs are chosen randomly in the area and are shown in blue.

In clustering algorithm, the value of k (the number of node) has great influence on region division. The smaller the number of clusters, the smaller the differentiation will be. However, if the number of clusters is too large, the complexity of subsequent localization will increase. In order to find the optimal k, the experimental range is set as 2-5. Figure 3 shows the clustering results of 73 RPs for this environment, with different categories represented in different colors.

Figure 3.

Clustering results under different k: (a) k = 2, (b) k = 3, (c) k = 4, (d) k = 5.

As shown in Figure 2, when k = 2 or k = 3, there are hardly any distinctions in the region of east-west corridor. When k = 5, the number of clusters is a bit of large, which may increase the complexity of positioning. Therefore, k is set to 4 in this paper.

In order to verify the performance of the proposed SOM algorithm, traditional WKNN algorithm is firstly adopted. The localization results are shown in Table 1.

Table 1.

Performance of SOM algorithm.

Table 1 shows the localization results improve after clustering. Specifically, the mean error has an improvement of 5.4% and the time of positioning reduce by 45.7%, which indicates that the proposed

SOM algorithm can effectively lower the positioning error and shorten the positioning time.

To further improve the accuracy, AG-WKNN is conducted in the environment. In equation (5), a and c are set to 1 in this paper. The value of b determines the weight w directly, and impacts on positioning accuracy. l_k represents the k – th distance between RP and TP, b can be set near the first distance l₁, which is depicted by

where n is the coefficient. In order to find the optimal n, different values are tested, and the results are shown in Figure 4. Figure 4 shows that the positioning error goes up first, and declines later on as n increases. Specially, the positioning error minimizes as n equals to 1.03, and the minimum value goes to 1.18m.

Figure 4.

The relationship between n and positioning

Table 2 lists the performance using the proposed algorithm. The mean error and max error both reduce. Furthermore, the mean error has a reduction of 5.4% and 9.2%. Figure 5 shows the cumulative distribution errors using proposed algorithm. The positioning accuracy improves when using SOM and AG-WKNN algorithm.

Figure 5.

Cumulative distribution errors of proposed error. algorithm.

Table 2.

The performance using the proposed algorithm.

To make our results more convincing, the proposed algorithm is compared with existed algorithms. Zhong et al. proposed K-means algorithm based on neighborhood density¹⁵. Guo et al. proposed a hybrid algorithm, in which used K-means++ algorithm¹⁰. The performance of these algorithms is shown in Table 3.

Table 3.

The comparison of proposed and existed algorithms.

Table 3 shows the clustering time of three algorithms is nearly the same, but the mean error of the proposed algorithm outperforms the other two algorithms, with improvement of 34.8% and 30.6%. In conclusion, the results indicate that the proposed algorithm performs well and it will have a good prospect in real positioning scenarios.

4.

CONCLUSION

In this paper, clustering algorithm based on SOM and improved WKNN algorithm, called AG-WKNN, are proposed to increase the positioning accuracy and cut down the positioning time. The experiment results show that the positioning error and time both decline after using the proposed algorithm, and the experiments also show that the proposed algorithm has higher accuracy than existed algorithm. Better clustering algorithm is still desirable to enhance the indoor localization system and this is the future work.