Nothing Special   »   [go: up one dir, main page]

Next Article in Journal
Fault-Tolerant Model Predictive Control Algorithm for Path Tracking of Autonomous Vehicle
Next Article in Special Issue
Toward Accurate Position Estimation Using Learning to Prediction Algorithm in Indoor Navigation
Previous Article in Journal
Encapsulation of Electrically Conductive Apparel Fabrics: Effects on Performance
Previous Article in Special Issue
A Method of Multiple Dynamic Objects Identification and Localization Based on Laser and RFID
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Letter

An RSSI Classification and Tracing Algorithm to Improve Trilateration-Based Positioning

1
School of Computer Information and Engineering, Changzhou Institute of Technology, Changzhou 21300, China
2
Department of Land Surveying and Geo-Informatics, The Hong Kong Polytechnic University, Hong Kong
*
Author to whom correspondence should be addressed.
Sensors 2020, 20(15), 4244; https://doi.org/10.3390/s20154244
Submission received: 22 June 2020 / Revised: 28 July 2020 / Accepted: 29 July 2020 / Published: 30 July 2020
(This article belongs to the Special Issue Indoor Positioning and Navigation)

Abstract

:
Received signal strength indicator (RSSI)-based positioning is suitable for large-scale applications due to its advantages of low cost and high accuracy. However, it suffers from low stability because RSSI is easily blocked and easily interfered with by objects and environmental effects. Therefore, this paper proposed a tri-partition RSSI classification and its tracing algorithm as an RSSI filter. The proposed filter shows an available feature, where small test RSSI samples gain a low deviation of less than 1 dBm from a large RSSI sample collected about 10 min, and the sub-classification RSSIs conform to normal distribution when the minimum sample count is greater than 20. The proposed filter also offers several advantages compared to the mean filter, including lower variance range with an overall range of around 1 dBm, 25.9% decreased sample variance, and 65% probability of mitigating RSSI left-skewness. We experimentally confirmed the proposed filter worked in the path-loss exponent fitting and location computing, and a 4.45-fold improvement in positioning stability based on the sample standard variance, and positioning accuracy improved by 20.5% with an overall error of less than 1.46 m.

1. Introduction

With widespread Wi-Fi, Bluetooth (iBeacon), and smart mobile terminal deployment, received signal strength indicator (RSSI)-based indoor positioning technology has attracted research attention due to its advantages of low complexity, low cost and high accuracy [1,2]. However, the received signal strength (RSS) is easily blocked and easily interfered with by objects and environmental effects. These influences usually increase RSSI variance; thus, RSSIs vary sharply over time even when the actual signal strength remains constant. The variation reduces accuracy and stability for an RSSI-based indoor positioning system (IPS) [3,4,5]. Many assisted and combined technologies were proposed to achieve higher accuracy, e.g., pedestrian dead reckoning (PDR), computer vision, space-scenario, and artificial intelligence techniques [1,4]. However, fundamentally, dealing with RSSI is a crucial step during the whole IPS process.
RSSI is environment-dependent. Therefore, it is significant to filter the raw RSSIs before substituting them into the positioning process. Many RSSI purification technologies such as the Gaussian filter [6], Kalman filter [7], and particle filter [8,9] are typically designed to mitigate either the linear or non-linear noise through smoothing. Still, they may not effectively deal with the ever-changing dynamics of the indoor environment [10] and have left-skewed distributions [11]. The mean filter [12] is widely accepted because it has similar accuracy and anti-interference performance, but has less burden in filtering computation [13,14]. Besides smoothing, RSSI screening is another effective filtering method, e.g., by selecting the max N RSSIs (N = 13 is optimal) [13], and the least variance RSSIs over time [15]. Importantly, RSSI classification is also an effective filtering method, especially in combination with clustering algorithms for RSSI filtering and singular RSSI tracing [16,17].
RSSI-based IPS is generally divided into two categories: trilateration-based IPS and fingerprint-based IPS [10,18,19]. The fingerprint-based IPS [20,21,22] gets more concern in terms of the number of references retrieved, where the number is 1,910,000 vs. 30,000 from Google Scholar. It also gains positive effect by using unsupervised machine-learning algorithms to reduce the data dimensionality, and fingerprint matching calculations required [23]. Meanwhile, the trilateration-based positioning system is widely applied in outdoor environments [24,25]. However, it faces challenges in indoor environments, achieving 3–5 m accuracy without assistive technology and device, and lower stability [3]. The trilateration-based IPS positioning is easy to understand and easy to construct. Usually, RSSI-based trilateration IPS is undertaken in two main steps: distance mapping and position computation [10]. The distance between the unknown position sensor and the known position sensor anchor is obtained by some RSSI propagation model [26]; its accuracy depends on signal transmission anchor, path-loss exponent in the RSSI propagation model, and RSSI sampling, etc. [10,13]. Based on this, the unknown location is obtained by trilateration methods such as least square and maximum likelihood [4,10].
This paper will propose a new filtering technique to play a role in the propagation parameter fitting and the RSSI sampling purification, to improve RSSI-based IPS accuracy and stability, particularly for trilateration-based positioning, considering that accuracy and stability are equally important. The overall accuracy may diminish due to energy consumption [27,28], and stability may significantly influence the user experience and application promotion.
The main contributions of this study are as follows:
(1)
We propose a tri-partition classification of RSSIs, considering that the interference effects are finite and unambiguous, increasing and decreasing while the interference sources are multiple and fuzzy. And we also propose a clustering algorithm to trace the tri-partition classification quantitatively and seek the partition distribution centers, helping to reveal the interference and judge whether the sun-classification conforms to normal distribution.
(2)
We take the proposed algorithm as an RSSI filter and discuss its work mechanism. And we infer that it is feasible by analyzing the features in terms of sample count and deviation and advantages compared to the mean filter.
(3)
We verify that the proposed filter works in path-loss exponent fitting and location computing, and analyze the improvement of IPS it yields.
The remainder of this paper is arranged as follows. In Section 2, we review RSSI-based trilateration positioning technologies and RSSI filters. We detail the proposed RSSI filter based on an RSSI classification and tracing algorithm in Section 3. In Section 4, we analyze the filtering performance, including features adapted to real-time IPS and advantages over the mean filter. Section 5 introduces a test to examine the positioning performance using the proposed filter and compares its performance with the mean filter. Finally, in Section 6, we summarize and conclude the paper.

2. Literature Review

2.1. Received Signal Strength Indicator (RSSI)-Based Trilateration Indoor Positioning System (IPS)

Trilateration-based positioning technology is easily understood and widely used in the positioning of pedestrians and robots and things [1,2,3]. In the method we should know the position of the anchors (reference nodes) as (x1, y1), (x2, y2), …, (xn, yn), and their distances from the target node, which is calculated by the RSSI-distance mapping, d1, d2, …, d3. If we assume the target node’s coordinates as (x, y), then the essential geometric functions as follows. When the anchors are more than 4, the least square and maximum likelihood [4,10] are used to calculate the target node’s optimal coordinates.
{ ( x 1 x ) 2 + ( y 1 y ) 2 = d 1 2 ( x 2 x ) 2 + ( y 2 y ) 2 = d 2 2 ( x n x ) 2 + ( y n y ) 2 = d n 2
The positioning complexity is partly to know the anchor points’ location in advance, especially when anchors change and a lot of update work required. The difficulty is that RSSI-based trilateration techniques depend on an accurate estimation of distance by RSSI-distance mapping. RSSI is a function of distance and is generally affected by the environment and any changes therein. Usually, researchers use the following simplified propagation model to measure RSSI (Formula 1) and map RSSI to distance (Formula 2) [26,29,30]:
ρ = α 10 β log ( d )
d = 10 ( ( ρ α ) / ( 10 β ) )
where d is the distance from the current position to some beacon, ρ is the RSSI at the current position, α is the RSSI at some referenced distance (usually 1 m), β is the path-loss exponent, and the parameters α and β are obtained to adapt to different sensors and environments; the path-loss exponent β generally has a value in the range of 1.6–1.8 in an indoor environment [26,31,32]. More importantly, it is necessary to fit the path-loss exponent according to the actual environment in which RSSIs are collected [33,34]. These parameters should be calculated again when a target node moves across the boundary of two different environments [34], even be constantly updated if necessary [35]. Furthermore, the piecewise fitting and min–max method are proposed for local adaption to the real environment, 4 m and 8 m are the breakpoints, and the curvatures of different sections are noticeably different [15,34,36].
Accuracy is the most crucial performance metric of the positioning system. It is related to devices and its effective coverage. Wi-Fi and iBeacon belong to high-frequency signals, but the RSSI performance received is also different due to the difference in transmitting power and antenna angle. For example, iBeacon, particularly the loss of packets, is serious for the interval beyond 10 m [10,15,36]. The deployment density is also computing- and maintenance-cost related. When the anchors’ density is 0.27 nodes/m2, localization estimation error can be decreased to 1.5–2 m [37]. However, increasing the number of anchor nodes does not result in higher average accuracy, and with more than 50 anchors, the average accuracy declines [26]. Meanwhile, paper [38] proposes a sensor deployment method based on wireless sensor network topology optimization, and [39] suggests a novel technique related to pedestrian density, gaining an accuracy of 1.8–3.9 m.
Considering the overall accuracy may diminish due to energy consumption [27,28], that accuracy and stability are equally important, and stability may significantly influence the user experience and application promotion. This paper’s core contribution is to adopt the same positioning method without increasing the calculation amount of positioning, which reflects the function advantages of proposed classification and filtering in this paper.

2.2. RSSI Filtering Technologies

Raw RSSIs measurement is related to the parameter fitting and distance mapping process, and play a decisive role for IPS performance [33]. Compared with the mean filter [11], Kalman filter [7], particle filter [8,9], least-squares estimator [40,41], and maximum-likelihood estimator [42] have advantages in terms of accuracy but are computationally expensive. They use a moment before estimation and the current observations to update the state variables’ estimate, while the mean filter just takes the average. Thus, the mean filter is widely recommended because it has similar accuracy and anti-interference performance [11]. Considering their relatively small computational overheads and the fact they can be used in a real-time context, the rolling mean filter, exponential moving mean filer, and moving median filter have been discussed [12]. However, these filters are typically intended to mitigate these influences by smoothing and could suffer from left-skewed distributions caused by RSSI multipath propagation [15].
RSSI screening is another effective filtering method based on analyzing the spatial resolution of the signal strength and RSSI signal characteristics under different scenarios. Gaussian filter [6] selects the high RSSI probability RSSIs and takes the average value as filter results, lowers the influence of the small probability and interference over the measurement. An algorithm using the maximum RSSI average has been proposed and suggests that N = 13 is optimal [13]. Relative to selecting the maximum, [15] selected the least variance RSSIs over time, arguing that the normal variances are not dramatic. Based on dichotomy, Study [16] and [17] propose an RSSI classification to distinguish singular RSSIs from normal path-loss RSSIs. Paper [17] proposes a k-means clustering algorithm tracing the rating.
Applying artificial intelligence (including statistical inference methods) for RSSI processing is a new trend, e.g., using a k-means clustering algorithm for singular RSS tracing [22] and filtering, and RSSI fingerprint matching [23,24]. Moreover, support vector machine (SVM) [43], artificial neural network (ANN) [44,45] and deep learning [46] have been proposed to aid RSSI purification and high positioning accuracy. However, in indoor environments, all of the above algorithms still face challenges of spatial ambiguity, RSSI instability, and RSSI’s short collecting time per location [47,48].
This paper will propose a three-classification and tracking method to explore its distribution center instead of the mean center based on the classification idea and unsupervised learning algorithm. More importantly, we will discuss the filtering performance under the conditions of small samples and small sampling time.

3. RSSI Classification and Tracing

3.1. Tri-Partition RSSI Classification

Environmental conditions, scenario changes, anchor deployment, transmission power, and interferences between anchor nodes can affect the RSSI values. Furthermore, it is challenging to determine antenna gains [10]. However, the actual effects can be summarized as increasing and decreasing, so unlike the dichotomy, we propose a tri-partition of RSSIs, as shown in Figure 1. We classify RSSI samples into three collections:
  • The decreased collection (DC) represents singular weakened RSSIs such as blocked and reflected signals.
  • The normal collection (NC) represents normal path-loss and fading RSSIs.
  • The increased collection (IC) represents singular enhanced RSSIs caused by transmitting equipment such as antenna gained power or transmitting power mutation.
The tri-partition can help with the quantitative analysis of the RSSI. Tracing the item count of sub-classification can reveal that the subsequent positioning is dependable or not, where NC RSSIs do not conform to normal distribution means more significant errors. Thus, it helps select different path-loss parameters to adapt to the environment.

3.2. RSSI Tracing Algorithm

We propose an RSSI tracing algorithm based on k-means clustering to determine the partition and its distribution center. The proposed algorithm considers the RSSI sample (R) to be a one-dimensional collection. It uses the absolute value of RSSI and sub-classification center subtraction as the clustering factor, takes the maximum RSSI as the initial center of the IC, the minimum RSSI as the initial center of the DC, the mean RSSI as the initial center of the NC, and then defines the assistant function MIN(R) to obtain the minimum RSSI from R, the function MAX(R) to obtain the maximum RSSI from R, and the function AVERAGE(R) to obtain the mean value from R. The algorithm steps are as follows Algorithm 1:
Algorithm 1. Sub-Classification Tracing.
Input: R = {RSSI1, RSSI2, …, RSSIn}//the collected RSSI samples
Output: NC, IC, DC
Define://initial the center of IC, NC, and DC
    IV = MAX(R), NV = AVERAGE(R), and DV = MIN(R)
    ICT = ϕ, NCT = ϕ, and DCT = ϕ  //temporal collections
    TD = ID = ND = DD = 0.0    //temporal values.
Classify:
For each (RSSIi ∈ R){
//calculate its distance to IV, NV, and DV
ID = abs (IV- RSSIi)
       ND = abs (NV- RSSIi)
       DD = abs (DV- RSSIi)
       //select the minimum distance
       TD = MIN ({ID, ND, DD})
       //add RSSIi to sub-classification
       If (TD= =ID)
       IC = IC + { RSSIi }
       Else if (TD= =ND)
    NC = NC+{ RSSIi }
    Else
    DC = DC + { RSSIi }
    }
Judge:
   //judge the change of sub-classification
   If (ICT = = NCT = = DCT = = ϕ){
       ICT = IC
       NCT = NC
       DCT = DC
       }
GOTO (Reset)
//if convergence, exit
   If (ICT = = IC and NCT = = NC and DCT = = DC)
   GOTO (Exit)
   Else {
       ICT = IC
       NCT = NC
       DCT = DC
       }
Reset: //reset the sub-classification center
IV = AVERAGE (IC)
    NV = AVERAGE (NC)
    DV = AVERAGE (DC)
    GOTO (Classify)
Exit:  //deal with ϕ
   If (NC = = ϕ) {
    TD = (ID + DD)/2
    NC+ = {TD}
    }
EXIT(-)
where NC equals ϕ in the Algorithm (1) means that sample R has a polarization distribution, and partition NC is affected by substantial RSSI deviation from reality. When we set the mean value as a new RSSI, the whole count will increase by one each time.

3.3. Apply to Trilateration-Based Positioning

Trilateration-based IPS includes many steps [10,13], here we divide these steps into two stages: offline and online. The offline stage aims to adapt the path-loss exponent, including anchor deployment, RSSI collecting, raw RSSI measurement, and path-loss exponent fitting (may fit as needed during the online stage [15,34]). The online stage aims to optimize positioning, including real-time RSSI collecting, raw RSSI measurement, distance mapping, coordinate calculation, and positioning optimization and correction. This paper adopts the proposed tracing algorithm as an RSSI filter to re-establish the raw RSSI measurement for the path-loss exponent fitting (offline) and distance calculating (online) steps, as shown in Figure 2.
Figure 2 shows the application mechanism that focuses on the sample count and the partition item count. The minimum sample count is related to real-time positioning, as RSSI’s shortest collecting time per location usually less than 1 s. The partition item size is related to influences when the tri-partition counts conform to a normal distribution, indicating that the filtering result is reliable. For the filtering process, the partition center is the filtering result. Next, we will discuss the minimum sample and performance to reveal the availability of the proposed filter.

4. Feasibility and Performance as an RSSI Filter

To examine the proposed filter’s feasibility and performance advantages, we collected a large RSSI sample (named Sample ALL) over approximately 10 min using iBeacon as the signal sender. And we defined six type sample groups, named Sample X (X = 10, 20, 30, 40, 50, 60). Each sample group had 10 sample arrays, and each array had the same count RSSIs. The sample array data structure is as follows:
Test Sample = {Arrayi,j, I = 10, 20, …, 60, j = 1, 2, …, 10}
where i represents different groups, and j represents different arrays in the current group. For example, Array30,1 represents that the collection is in group 30, and the collection’s item count is 30.
In preparation, we cut the sample ALL into each test sample sequentially and continuously according to the sample type, and then filter each test sample and the sample ALL. Figure 3 shows the filtering results, where each node represents a filtering result of some Test Sample. For each type of sample, ten filtering tests are conducted in sequence, with a total of 60 filtering times. Figure 3 also shows Sample 10 has the max deviation from the Sample ALL, and with the sample count is larger than 20, the gap range gradually stabilized.

4.1. Features of the Proposed Filter

4.1.1. Low Deviation

RSSI fluctuation is an inherent issue for wireless signals, hence reducing the variance range for each sample count is essential to improve the accuracy and stability [49,50]. Using the sample ALL as the comparative standard, we measured the deviation and variance of each test sample, which is as shown in Table 1. It summarizes the deviations from all samples, and together with Figure 3 shows that the proposed filter achieves lower variance. Sample 10 and Sample 20 have the highest variation with a maximum deviation range of less than 2.5 dBm and the mean deviation range of less than 1.44 dBm. When the test sample count was greater than 20, the maximum deviation range was less than 1.64 dBm, and the mean variation was below 0.92 dBm. As experiments have confirmed that a change of 1 dBm represents 0.08 m at some distance [13], therefore, the filter obtained a significantly lower fluctuation, and the test sample gains a similar performance to the sample. ALL, especially when the sample size is more significant than 20.

4.1.2. Minimum Sample Count

While RSSIs are Gaussian distribution and random, the time of sampling can affect the collected RSSI count and positioning quality [10,51]. Most current IPSs and RSSI analyses take a long-time interval for sample collecting, such as 1–3 or 3–6 min, but it is a gap from second-level real-time requirements.
By counting the items of each sample, as shown in Table 2, the Sample 10 had an item count of 103 when the expected count was 100, and sample 20 s item count was 201 when the expected count was 200, indicating that the NC in Sample 10 and Sample 20 generated ϕ during filtering. Further calculating the sub-classification distribution rate, as shown in Figure 4, the tri-partition collection items conform to the normal distribution when the sample count is over 20. Therefore, the proposed filter obtained a minimum sample count of 20 suitable for the positioning process.
In summary, the proposed filter has such features; the small test sample gains a similar performance to the larger sample ALL, and the sun-classification conforms to normal distribution when the sample count is larger than 20. Therefore, the proposed filter adapts to real-time positioning, for it has a lower deviation, and the minimum sample count is 20.

4.2. Advantages over the Mean Filter

Using the same RSSI test sample from the upper section, Figure 5 shows the filtering results comparison by the proposed filter and the mean filter, respectively, where each node represents a filtering result of some test sample. For each type of sample, 10 filtering tests are conducted in sequence, with a total of 120 filtering computations. Based on the filtering performance, we discuss the advantages associated with reductions in variance below.

4.2.1. Reducing Variance over Time

The comparisons use variance range and sample variance (SV, calculated using the sample standard deviation function in EXCEL) to measure the proposed and mean filters’ performance. As Figure 5 shows the filtering result, Table 3 shows the variance comparisons in detail. The proposed filter achieves a smaller maximum variance range than the mean filter, and a lower SV when the sample count is greater than 10.
Overall, the average maximum variance for the proposed filter was 2.31 dBm, while for the mean filter, this was 2.97 dBm. The average minimum deviation for the proposed filter was 0.37 dBm, while the mean filter was 0.39 dBm. The average variance for the proposed filter was 1.08 dBm, while the mean filter was 1.34 dBm, and the average SV for the proposed filter was 1.38 dBm, while the mean filter was 1.73 dBm. Thus, the proposed filter resulted in a lower and more stable variance.

4.2.2. Reducing Left-Skewness

Traditional RSSI filtering commonly produces left-skewed distributions [11,26,50], i.e., the returned value is lower than the actual value. Table 4 shows that the proposed filter mitigates this problem, achieving a 65% superior performance in terms of skewness reduction. The left 35% which did not mitigate skewness; they had an average of 96.7% deviation at less than one dBm and an average of 78.9% deviation at less than 0.5 dBm, so the proposed filter successfully reduced skewness.
In summary, the proposed filter shows feasibility because it has significant low variance and a minimum sample of 20 properties and mitigating advantages over the mean filter which is vastly used.

5. Positioning Improvement

5.1. Experiment Design

Figure 6 shows the 4 × 4 m testbed used to investigate the proposed filter’s positioning performance. The experiment selects (1,1), (1,3), and (3,3) as test points, deploys four iBeacon (SEEKCY s1u) sensors as RSS senders at the grid corners and selects an android mobile phone (MI max2) as the RSS receiver. To seek reliable positioning performance under real-time, we set the minimum sample count of 30 each time. The experimental steps are as follows.
  • Fit RSSI propagation model factors,
    • collect RSSI samples at each fixed distance (1 m, 2 m, …, 10 m),
    • filter each sample using the proposed and mean filters, and
    • fit the propagation model according to Formula (2).
  • For each positioning process,
    • filter RSSI samples using the proposed and mean filters,
    • perform traditional trilateral positioning, and
    • compare the positioning results.
  • Repeat step (2) for the next test process.

5.2. Experiment Results

5.2.1. Propagation Factors

Using MATLAB Fitting Tools and a similar fitting process in paper [14,15], Table 5 shows the that α and β are distinctly different. It is foreseeable that the distance mapping process will still make a difference using the factors.
The α is as RSSI sample filtering result at 1 m, and the b is as the fitting result of collected RSSI samples at each fixed distance from 1 m to 10 m, by the proposed filter and the mean filter. Considering studies have confirmed that many packets may mass lose when the measured distance exceeds 10 m [36,52].

5.2.2. Positioning Results

Table 6 shows a total of 24 positioning coordinates. Figure 7 shows the positioning results and the relative positions of these test points. The proposed filter achieves a significantly compact location distribution at each test point, whereas the mean filter has a relatively loose distribution, with point (3,1) exhibiting the highest accuracy.

5.3. Improvement Analysis

5.3.1. Accuracy

Figure 8 shows the calculated positioning errors in sequence. Based on the accuracy changes at each test point, errors by the proposed filter change little, while the errors by the mean filter change significantly. Unfortunately, despite the proposed filter gains in the overall improvement, it does not improve every positioning, and about 58% have higher accuracy compared to the mean filter.
In detail, Table 7 shows the comparison of the proposed filter and the mean filter in accuracy promotion. For each test point, the proposed filter achieves smaller maximum and average errors than the mean filter, and the positioning accuracy is improved by approximately 20% for each test point. The overall average error is 1.46 and 1.84 m for the proposed and mean filters, respectively, and the overall average accuracy improvement is 20.5%. Still, it can be concluded that even if the error by the proposed filter is larger, the difference between the errors by the mean filter is still small, this phenomenon is consistent with the mitigation performance analysis in chapter 4.

5.3.2. Stability

Using sample standard deviation (SSD) to measure positioning stability, the SSD will be calculated by the following formula:
  S S D = S T D E V ( R ) / A V E R A G E ( R )
where STDEV (–) is the sample standard deviation function in EXCEL, and AVERAGE (–) is the mean function in EXCEL; R is the positioning error of each test point.
Table 8 shows that the proposed filter achieves smaller SV and closer average positions for each test point than the mean filter. The positioning stability is 6.45, 5.82, and 1.08-fold better for test points (1,1), (1,3), and (3,3), respectively, for the proposed filter compared with the mean filter. The overall average stability is improved 4.45-fold.
In summary, the proposed filter achieved a 20.5% improvement in positioning accuracy, with an overall error of less than 1.46 m and a 65% probability of higher accuracy. Significantly, the proposed filter gained a 4.45-fold improvement in positioning stability.

6. Conclusions

Considering RSSI is easily blocked and affected by things and the environment, RSSI-based IPS faces the challenge of an unfortunate application effect. To improve the accuracy and stability, particularly for trilateration-based positioning, we propose a tri-partition RSSI classification as the decreased RSSIs, normal RSSIs, and increased RSSIs, and proposed a novel RSSI tracing algorithm based on k-means clustering as an RSSI filter.
The proposed filter adapts to the real-time IPS, for it shows a characteristic achieving a lower variance (<1 dBm) when the minimum sample size is greater than 20. In contrast, traditional RSSI variation can exceed 10 dBm [26]. The proposed filter offers several advantages compared to the mean filter, including lower variance range and sample variance, and 65% probability to mitigate RSSI left-skewness. Thus, the proposed filter is feasible in real-time positioning.
We design a trilateration-based positioning test within a room. The RSSI propagation model fitting achieves a difference path-loss exponent where 4.613 by the proposed filter while 2.326 by the mean filter. Based on this, the positioning results confirm a 20.5% improvement in positioning accuracy and 4.45-fold improvement in stability for the proposed filter compared to the mean filter. Thus, the proposed filter significantly outperforms traditional mean filtering, providing an excellent option for large-scale IPS improvement.

Author Contributions

Y.S. conceived the main concept of the algorithm, designed the system and the experiments and wrote the paper. W.S. and X.L. contributed analysis tools, offered professional instructions and supervised the whole experimental process. X.X. conducted the experiments, analyzed the experimental data and wrote part of the paper. All authors have read and agreed to the published version of the manuscript.

Funding

This work was supported in part by the National Natural Science Foundation of China (Grant No. 41571382, No. 41901323), in part by the Natural Science Foundation of the Jiangsu Higher Education Institutions of China (Grant No. 15KJB170006, No.16KJB 520003, No. 17KJD520001), in part by Jiangsu industry-university-institute collaboration project (Grant No. BY2019021), in part by Jiangsu Collaborative Innovation Center for Cultural Creativity (Grant No.XYN1702, No.XYN1703), in part by Taizhou Science and technology support program of China (Grant No. TS201621), in part by Changzhou Science and technology support program of China (Grant No. CE20172023), in part by Collaborative Innovation Center of Changzhou Institute of Technology for Digital Information Technology, in part by Excellent Scientific and Technological Innovation Team of Changzhou Institute of Technology, and in part by Natural Science Foundation of Changzhou Institute of Technology (Grant No.YN1726).

Acknowledgments

The authors would like to thank the editor and the anonymous reviewers who provided insightful comments on improving this article, thank The Hong Kong Polytechnic University for providing the opportunity of a visiting scholar, and thank student Jiaxin Li, Wenlong Zhou, Zhongqi Cui for data collecting.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Ali, W.H.; Kareem, A.A.; Jasim, M. Survey on Wireless Indoor Positioning Systems. CUESJ 2019, 3, 42–47. [Google Scholar] [CrossRef] [Green Version]
  2. Lee1, K.; Nam1, Y.; Min, S.D. An indoor localization solution using Bluetooth RSSI and multiple sensors on a smartphone. Multimed. Tools Appl. 2018, 77, 12635–12654. [Google Scholar] [CrossRef]
  3. Oguntala, G.; Abd-Alhameed, R.A.; Jones, S.; Noras, J.; Patwary, M.; Rodriguez, J. Indoor location identification technologies for real-time IoT-based applications: An inclusive survey. Comput. Sci. Rev. 2018, 30, 55–79. [Google Scholar] [CrossRef]
  4. Brena, R.F.; García-Vázquez, J.P.; Galván-Tejada, C.E.; Muñoz-Rodriguez, D.; Vargas-Rosales, C.; Fangmeyer, J. Evolution of Indoor Positioning Technologies. Surv. J. Sens. 2017, 2017, 2630413. [Google Scholar] [CrossRef]
  5. Huang, H.; Gartner, G.; Krisp, J.M.; Raubal, M.; Van de Weghe, N. Location based services: Ongoing evolution and research agenda. J. Locat. Based Serv. 2018, 12, 63–93. [Google Scholar] [CrossRef]
  6. Ito, K.; Xiong, K. Gaussian filters for nonlinear filtering problems. IEEE Trans. Autom. Control 2020, 45, 910–927. [Google Scholar] [CrossRef] [Green Version]
  7. Sung, Y. RSSI-Based Distance Estimation Framework Using a Kalman Filter for Sustainable Indoor Computing Environments. Sustainability 2016, 8, 1136. [Google Scholar] [CrossRef] [Green Version]
  8. Chao, C.H.; Chu, C.Y.; Wu, A.Y. Location-Constrained Particle Filter human positioning and tracking system. In Proceedings of the 2008 IEEE Workshop on Signal Processing Systems, Washington, DC, USA, 8–10 October 2008; pp. 73–76. [Google Scholar]
  9. Liu, H.H.; Chen, W.C.; Hsu, P.C. Comparison of NVA and RLOWESS Algorithms in Indoor Positioning System. In Proceedings of the 2019 20th Asia-Pacific Network Operations and Management Symposium (APNOMS), Matsue, Japan, 18–20 September 2019; pp. 1–4. [Google Scholar]
  10. Shojaifar, A. Evaluation and Improvement of the RSSI-Based Localization Algorithm Received Signal Strength Indication (RSSI); Blekinge Institute of Technology: Karlskrona, Sweden, 2015. [Google Scholar]
  11. Luo, J.; Zhan, X. Characterization of Smart Phone Received Signal Strength Indication for WLAN Indoor Positioning Accuracy Improvement. J. Netw. 2014, 9, 739. [Google Scholar] [CrossRef]
  12. Koledoye, M.A.; De Martini, D.; Rigoni, S.; Facchinetti, T. A Comparison of RSSI Filtering Techniques for Range-based Localization. In Proceedings of the 2018 IEEE 23rd International Conference on Emerging Technologies and Factory Automation (ETFA), Turin, Italy, 4–7 September 2018; pp. 761–767. [Google Scholar]
  13. Xue, W.; Qiu, W.; Hua, X.; Yu, K. Improved Wi-Fi RSSI Measurement for Indoor Localization. IEEE Sens. J. 2017, 17, 2224–2230. [Google Scholar] [CrossRef]
  14. Shi, Y.; Long, Y.; Lu, F.; Xu, Z.; Xiao, X.; Shi, S. Indoor RSSI Trilateral Algorithm Considering Piecewise and Space-Scene. In Proceedings of the 2017 IEEE International Conference on Smart Cloud, New York, NY, USA, 3–5 November 2017; pp. 278–282. [Google Scholar]
  15. Kaemarungsi, K.; Krishnamurthy, P. Properties of indoor received signal strength for WLAN location fingerprinting. In Proceedings of the First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, MOBIQUITOUS 2004, Boston, MA, USA, 26 August 2004; pp. 14–23. [Google Scholar]
  16. Wang, B.; Gan, X.; Liu, X.; Yu, B.; Jia, R.; Huang, L.; Jia, H. A Novel Weighted KNN Algorithm Based on RSS Similarity and Position Distance for Wi-Fi Fingerprint Positioning. IEEE Access 2020, 8, 30591–30602. [Google Scholar] [CrossRef]
  17. Subedi, S.; Gang, H.S.; Ko, N.Y.; Hwang, S.S.; Pyun, J.Y. Improving Indoor Fingerprinting Positioning with Affinity Propagation Clustering and Weighted Centroid Fingerprint. IEEE Access 2019, 7, 31738–31750. [Google Scholar] [CrossRef]
  18. Liu, H.H.; Lo, W.H.; Tseng, C.C.; Shin, H.Y. A WiFi-based weighted screening method for indoor positioning systems. Wirel. Pers. Commun. 2014, 79, 611–627. [Google Scholar] [CrossRef]
  19. Suroso, D.J.; Cherntanomwong, P.; Sooraksa, P.; Takada, J.-I. Location fingerprint technique using fuzzy C-means clustering algorithm for indoor localization. In Proceedings of the TENCON 2011-2011 IEEE Region 10 Conference, Bali, Indonesia, 21–24 November 2011; pp. 88–92. [Google Scholar]
  20. Yunfei, C.; Taihang, D.; Chundong, J.; Ling, Q.I.; Sun, S. Optimal processing of singular values of K-means clustering algorithm in indoor location. Sci. Technol. Eng. 2018, 18, 95–99. [Google Scholar]
  21. Chandrawanshi, V.S.; Tripathi, R.K.; Pachauri, R. An Intelligent Energy Efficient Clustering Technique for Multiple Base Stations Positioning in a Wireless Sensor Network. J. Intell. Fuzzy Syst. 2019, 36, 2409–2418. [Google Scholar] [CrossRef]
  22. Zhang, W.; Hua, X.; Yu, K.; Qiu, W.; Zhang, S.; He, X. A novel WiFi indoor positioning strategy based on weighted squared Euclidean distance and local principal gradient direction. Sens. Rev. 2019, 39, 99–106. [Google Scholar] [CrossRef]
  23. Zhang, C.; Zhang, F.; Zhao, L. Research and Optimization of BLE Fingerprint Indoor Positioning Algorithm Based on Fusion Clustering. In Proceedings of the 2019 IEEE International Conference on Artificial Intelligence and Computer Applications (ICAICA), Dalian, China, 29–31 March 2019; pp. 95–100. [Google Scholar]
  24. Honkavirta, V.; Perala, T.; Ali-Loytty, S.; Piché, R. A Compartive Survey of WLAN Location Fingerprinting Methods. In Proceedings of the 2009 6th Workshop on Positioning, Navigation and Communication, Hannover, Germany, 19 March 2009. [Google Scholar]
  25. Teoman, E.; Ovatman, T. Trilateration in Indoor Positioning with an Uncertain Reference Point. In Proceedings of the 2019 IEEE 16th International Conference on Networking, Sensing and Control (ICNSC), Banff, AB, Canada, 9–11 May 2019; pp. 397–402. [Google Scholar]
  26. Heurtefeux, K.; Valois, F. Is rssi a good choice for localization in wireless sensor network? In Proceedings of the 2012 IEEE 26th International Conference on Advanced Information Networking and Applications, Fukuoka, Japan, 26–29 March 2012; pp. 732–739. [Google Scholar]
  27. Huang, K.; He, K.; Du, X. A Hybrid Method to Improve the BLE-Based Indoor Positioning in a Dense Bluetooth Environment. Sensors 2019, 19, 424. [Google Scholar] [CrossRef] [Green Version]
  28. He, S.; Chan, S.H.G. Wi-Fi Fingerprint-Based Indoor Positioning: Recent Advances and Comparisons. IEEE Commun. Surv. Tutor. 2015, 18, 466–490. [Google Scholar] [CrossRef]
  29. Zhang, W.; Dong, Y.; Wang, X. Indoor Positioning methods using Rfid and Block clustering. Comput. Eng. Appl. 2016, 52, 112–117. [Google Scholar]
  30. Yang, G.L.; Kong, Y.P.; Zhong, Z.M.; Zhang, Y.L. Multimode-fingerprint matching based indoor positioning System Design and Implementation. Comput. Eng. Des. 2013, 34, 1896–1900. [Google Scholar]
  31. Mehra, R.; Singh, A. Real Time RSSI Error Reduction in Distance Estimation Using RLS Algorithm. In Proceedings of the IEEE 3rd International Advance Computing Conference, IACC 2013, Ghaziabad, India, 22–23 February 2013; pp. 661–665. [Google Scholar]
  32. Zhenghua, Z.; Lei, D.; Jiawen, L.; Xu, T. Research of optimizing weighted centroid distance correction localization algorithm based on RSSI. In Proceedings of the 2013 IEEE 11th International Conference on Electronic Measurement & Instruments, Harbin, China, 16–19 August 2013; pp. 552–556. [Google Scholar]
  33. Zhou, C.; Yuan, J.; Liu, H.; Qiu, J. Bluetooth Indoor Positioning Based on RSSI and Kalman Filter. Wirel. Pers. Commun. 2017, 96, 4115–4130. [Google Scholar] [CrossRef]
  34. Chen, Y.; Pan, Q.; Liang, Y.; Hu, Z. AWCL: Adaptive weighted centroid target localization algorithm based on RSSI in WSN. In Proceedings of the 2010 3rd International Conference on Computer Science and Information Technology, Chengdu, China, 9–11 July 2010; pp. 331–336. [Google Scholar]
  35. Golestani, A.; Petreska, N.; Wilfert, D.; Zimmer, C. Improving the Precision of RSSI-based Low- Energy Localization Using Path Loss Exponent Estimation. In Proceedings of the 2014 11th Workshop on Positioning, Navigation and Communication (WPNC), Dresden, Germany, 12–13 March 2014. [Google Scholar]
  36. Yong, S.H.I. Research on Indoor-Positioning Methods and Technologies Considering Indoor Space-Scene. Ph.D. Thesis, Nanjing Normal University, Nanjing, China, December 2016. [Google Scholar]
  37. Sugano, M.; Kawazoe, T.; Ohta, Y.; Murata, M. Indoor localization system using RSSI measurement of wireless sensor network based on ZigBee standard. Wirel. Opt. Commun. 2006, 538, 1–6. [Google Scholar]
  38. Zhou, H.; Hu, J.; Wu, H.; Guo, C. Indoor positioning research based on wireless sensor network topology optimization. In Proceedings of the 2019 Chinese Automation Congress (CAC), Hangzhou, China, 22–24 November 2019; pp. 3951–3957. [Google Scholar]
  39. Chen, F. Global Optimization Placement of Bluetooth Nodes Based on Indoor Maps. Master’s Thesis, Nanjing Normal University, Nanjing, China, June 2017. [Google Scholar]
  40. Li, X.R. RSS-based location estimation with unknown path-loss model. IEEE Trans. Wirel. Commun. 2006, 5, 3626–3633. [Google Scholar] [CrossRef]
  41. Lin, L.X.; So, H.C.; Chan, Y.T. Accurate and simple source localization using differential received signal strength. Digit. Signal Process. 2013, 23, 736–743. [Google Scholar] [CrossRef] [Green Version]
  42. Coluccia, A.; Ricciato, F. Maximum likelihood trajectory estimation of a mobile node from RSS measurements. In Proceedings of the 2012 9th Annual Conference on Wireless On-Demand Network Systems and Services (WONS), Courmayeur, Italy, 9–11 January 2012; pp. 151–158. [Google Scholar]
  43. Brunato, M.; Battiti, R. Statistical learning theory for location fingerprinting in wireless LANs. Comput. Netw. 2005, 47, 825–845. [Google Scholar] [CrossRef] [Green Version]
  44. Chen, H.; Zhang, Y.; Li, W.; Tao, X.; Zhang, P. ConFi: Convolutional neural networks based indoor Wi-Fi localization using channel state information. IEEE Access 2017, 5, 18066–18074. [Google Scholar] [CrossRef]
  45. Cui, X.; Yang, J.; Li, J.; Wu, C. Improved Genetic Algorithm to Optimize the Wi-Fi Indoor Positioning Based on Artificial Neural Network. IEEE Access 2020, 8, 74914–74921. [Google Scholar] [CrossRef]
  46. Wu, L.; Chen, C.-H.; Zhang, Q. A Mobile Positioning Method Based on Deep Learning Techniques. Electronics 2019, 8, 59. [Google Scholar] [CrossRef] [Green Version]
  47. Hoang, M.T.; Yuen, B.; Dong, X.; Lu, T.; Westendorp, R.; Reddy, K. Recurrent Neural Networks for Accurate RSSI Indoor Localization. IEEE Internet Things J. 2019, 6, 10639–10651. [Google Scholar] [CrossRef] [Green Version]
  48. Hoang, M.T.; Zhu, Y.; Yuen, B.; Reese, T.; Dong, X.; Lu, T.; Westendorp, R.; Xie, M. A soft range limited K-nearest neighbours algorithm for indoor localization enhancement. IEEE Sens. J. 2018, 18, 10208–10216. [Google Scholar] [CrossRef] [Green Version]
  49. Neishaboori, A.; Harras, K. Energy saving strategies in WiFi indoor localization. Proc. Acm Mswim 2013, 399–404. [Google Scholar] [CrossRef]
  50. Li, Y.; He, Z.; Li, Y.; Xu, H.; Pei, L.; Zhang, Y. Towards Location Enhanced IoT: Characterization of LoRa Signal for Wide Area Localization. In Proceedings of the 2018 Ubiquitous Positioning, Indoor Navigation and Location-Based Services (UPINLBS), Wuhan, China, 22–23 March 2018. [Google Scholar]
  51. Xu, Y. Autonomous Indoor Localization Using Unsupervised Wi-Fi Fingerprinting; Kassel University Press: Kassel, Germany, 2016. [Google Scholar]
  52. Jayakanth, K.; AbdelGhani, K.; Somaya, A.M.; Al-Ali, A. Indoor positioning and wayfnding systems: A survey. Hum.Cent. Comput. Inf. Sci. 2020, 10, 1–41. [Google Scholar]
Figure 1. Received signal strength indicator (RSSI) classification based on the view of influence effects.
Figure 1. Received signal strength indicator (RSSI) classification based on the view of influence effects.
Sensors 20 04244 g001
Figure 2. Application mechanism of the proposed filter for the indoor positioning system (IPS).
Figure 2. Application mechanism of the proposed filter for the indoor positioning system (IPS).
Sensors 20 04244 g002
Figure 3. Filtering results of each test sample in sample group and the sample ALL.
Figure 3. Filtering results of each test sample in sample group and the sample ALL.
Sensors 20 04244 g003
Figure 4. Distribution of tri-partition for sample groups.
Figure 4. Distribution of tri-partition for sample groups.
Sensors 20 04244 g004
Figure 5. Filtering performance comparisons of each type sample by the proposed filter and the mean filter, respectively.
Figure 5. Filtering performance comparisons of each type sample by the proposed filter and the mean filter, respectively.
Sensors 20 04244 g005
Figure 6. Testbed diagram and selected test points.
Figure 6. Testbed diagram and selected test points.
Sensors 20 04244 g006
Figure 7. Positioning results distributions at point (1,1), point (1,3) and point (3,1).
Figure 7. Positioning results distributions at point (1,1), point (1,3) and point (3,1).
Sensors 20 04244 g007
Figure 8. Positioning error comparison with the proposed filter and the mean filter at point (1,1), point (1,3) and point (3,1).
Figure 8. Positioning error comparison with the proposed filter and the mean filter at point (1,1), point (1,3) and point (3,1).
Sensors 20 04244 g008
Table 1. Low deviation feature of each sample group compared to sample ALL.
Table 1. Low deviation feature of each sample group compared to sample ALL.
Sample TypeMax Positive Deviation (dBm)Max Negative Deviation (dBm)Mean Absolute Deviation (dBm)
Sample 101.992.511.44
Sample 202.221.5720.89
Sample 301.361.170.83
Sample 401.640.870.70
Sample 501.531.560.92
Sample 601.361.170.83
Table 2. Items count and rate statistics for sample groups. DC, NC, IC represnts the RSSI count of the decreased, normal, and increased collection.
Table 2. Items count and rate statistics for sample groups. DC, NC, IC represnts the RSSI count of the decreased, normal, and increased collection.
Sample TypeItems CountDC RateNC RateIC Rate
Sample 1010328%32%38%
Sample 2020121%60%19%
Sample 3030026%51%23%
Sample 4040025%55%20%
Sample 5050025%50%25%
Sample 6060019%57%23%
Table 3. Comparison between the mean and proposed filters in terms of variance range and sample variance over time. SV = sample variance.
Table 3. Comparison between the mean and proposed filters in terms of variance range and sample variance over time. SV = sample variance.
Sample TypeMean FilterProposed Filter
Max RangeMin RangeAverage RangeSVMax RangeMin RangeAverage RangeSV
Sample 103.21.01.962.283.91.962.252.68
Sample 203.460.151.692.283.080.031.111.54
Sample 302.230.060.661.031.770.010.690.95
Sample 401.620.10.760.961.320.070.670.82
Sample 501.960.30.821.031.250.010.650.83
Sample 605.350.712.122.772.530.131.121.44
Table 4. Skewness reductions by comparisons among filters.
Table 4. Skewness reductions by comparisons among filters.
Sample TypeMitigating Others Less 1 dbmOthers Less0.5 dbm
Sample 1070%100%66.7%
Sample 2050%100%80%
Sample 3070%100%100%
Sample 4070%100%66.7%
Sample 5080%100%100%
Sample 6050%80%60%
Table 5. The simplified RSSI propagation model fitting.
Table 5. The simplified RSSI propagation model fitting.
FilterFiltered RSSI at 1 m (α)Fitted Path-Loss Parameter (β)
The proposed filter–80.14 dBm4.613
The mean filter–83.82 dBm2.326
Table 6. Positioning results coordinates at point (1,1), point (1,3) and point (3,1).
Table 6. Positioning results coordinates at point (1,1), point (1,3) and point (3,1).
Test PointPositioning Results Using
the Mean Filter
Positioning Results Using
the Proposed Filter
Coordinate xCoordinate yCoordinate xCoordinate y
(1,1)2.82 1.02 2.69 1.79
2.56 0.77 2.56 1.63
4.38 2.83 2.51 1.66
2.63 0.87 2.74 1.82
(1,3)2.84 2.25 2.87 2.25
4.19 2.46 2.97 2.25
2.80 2.21 2.89 2.27
4.38 2.10 3.06 2.09
(3,1)2.48 0.80 2.56 1.18
2.54 0.51 2.55 1.15
2.54 0.56 2.54 1.14
2.42 1.01 2.49 1.22
Table 7. Positioning errors and average accuracy promotion.
Table 7. Positioning errors and average accuracy promotion.
Test PointPositioning Errors Using
the Mean Filter
Positioning Errors Using
the Proposed Filter
Average Accuracy Promotion
MaximumMinimumAverageMaximumMinimumAverage
(1,1)3.841.572.221.921.641.7819.8%
(1,3)3.51.972.682.252.012.121.6%
(3,1)0.670.560.610.550.480.5116.0%
Table 8. Positioning stability and increase for the proposed filter vs. the mean filter. SSD represents the sample stand deviation and calculated by the Formula (5).
Table 8. Positioning stability and increase for the proposed filter vs. the mean filter. SSD represents the sample stand deviation and calculated by the Formula (5).
Test PointPositioning Stability Using
the Mean Filter
Positioning Stability Using
the Proposed Filter
SSD Promote
STDEV(R)AVERAGE(R)SSDSTDEV(R)AVERAGE(R)SSD(–fold)
(1,1)1.0892.2150.4910.1361.7750.0776.45
(1,3)0.812.6750.3030.1092.10.0525.82
(3,1)0.050.610.0810.0370.50.051.08

Share and Cite

MDPI and ACS Style

Shi, Y.; Shi, W.; Liu, X.; Xiao, X. An RSSI Classification and Tracing Algorithm to Improve Trilateration-Based Positioning. Sensors 2020, 20, 4244. https://doi.org/10.3390/s20154244

AMA Style

Shi Y, Shi W, Liu X, Xiao X. An RSSI Classification and Tracing Algorithm to Improve Trilateration-Based Positioning. Sensors. 2020; 20(15):4244. https://doi.org/10.3390/s20154244

Chicago/Turabian Style

Shi, Yong, Wenzhong Shi, Xintao Liu, and Xianjian Xiao. 2020. "An RSSI Classification and Tracing Algorithm to Improve Trilateration-Based Positioning" Sensors 20, no. 15: 4244. https://doi.org/10.3390/s20154244

APA Style

Shi, Y., Shi, W., Liu, X., & Xiao, X. (2020). An RSSI Classification and Tracing Algorithm to Improve Trilateration-Based Positioning. Sensors, 20(15), 4244. https://doi.org/10.3390/s20154244

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop