A RSSI/PDR-Based Probabilistic Position Selection Algorithm with NLOS Identification for Indoor Localisation

Abstract

In recent years, location-based services have been receiving increasing attention because of their great development prospects. Researchers from all over the world have proposed many solutions for indoor positioning over the past several years. However, owing to the dynamic and complex nature of indoor environments, accurately and efficiently localising targets in indoor environments remains a challenging problem. In this paper, we propose a novel indoor positioning algorithm based on the received signal strength indication and pedestrian dead reckoning. In order to enhance the accuracy and reliability of our proposed probabilistic position selection algorithm in mixed line-of-sight (LOS) and non-line-of-sight (NLOS) environments, a low-complexity identification approach is proposed to identify the change in the channel situation between NLOS and LOS. Numerical experiment results indicate that our proposed algorithm has a higher accuracy and is less impacted by NLOS errors than other conventional methods in mixed LOS and NLOS indoor environments.

1. Introduction

With the development of science and technology, location-based services are becoming more and more important in people’s everyday lives. The Global Positioning System (GPS) has been widely used in people’s daily life and can greatly meet the needs of outdoor localisation. Although GPS is the best positioning solution in the outdoor environment, in the indoor environment, GPS positioning cannot provide enough positioning accuracy owing to signal occlusion [1]. Therefore, the development of a precise and reliable indoor localisation system has become a top priority. The indoor environment is more complicated and has more interference than outdoors. However, the accuracy requirements of indoor localisation are much higher than that for outdoor localisation. In the outdoor environment, 10 m of positioning accuracy is sufficient to meet most needs (though it should be 5 m) and even less than 1 m in the indoor environment.

The currently available indoor location systems, such as Wi-Fi [2,3], Radiofrequency Identification (RFID) [4,5,6], Ultra-WideBand (UWB) [7,8,9,10,11], Bluetooth [12,13,14], and Ultrasound [15,16], have achieved great progress in terms of transferring data within a short range, but when it comes to the indoor environment, these systems have various problems, including high cost, high power consumption, low accuracy, and low precision. The advent of Bluetooth Low Energy (BLE) provided opportunities to overcome the above problems. BLE has been designed to provide features such as a low cost and a low power consumption [17]. In the actual system deployment, the cost of the BLE location system is approximately ¥20 (the price of the BLE beacon)/50 m² (the coverage area of the BLE beacon). The BLE beacons can be deployed on the ceiling in the indoor environment by using simple equipment such as magnets and double-sided adhesives. By measuring the received signal strength indication (RSSI) of BLE beacons, the mobile position can be estimated. Compared with the WiFi-based fingerprint positioning algorithm, the BLE-based system is easier to maintain.

Various solutions for localisation and tracking problems are presented in the literature, proposing different localisation algorithms generally categorised as range-measuring algorithms and range-free algorithms. By comparing the signals from users with those of a radio map, fingerprinting [18,19,20,21,22] has been proposed to estimate the users’ location. However, the establishment of a radio map is time-consuming and laborious, and it cannot meet the requirements of a dynamic indoor environment. Another approach is the RSSI-based trilateration [23,24,25]. According to the measurement of three RSSIs, the users’ position can be estimated. However, due to the NLOS factors in the indoor environment, the accuracy of the estimated distance decreases dramatically. To overcome these challenges, researchers have developed machine learning algorithms [26,27] to locate the users’ position in the indoor environment. However, as with fingerprinting, a major drawback of these methods is their inability to adapt to a new environment owing to the use of a pre-established database and they also cannot perform reliably in an environment where continuous changes are expected to take place. An iterative maximum likelihood estimation (MLE) [28] was developed by Li et al., who were first to show a way to consider signal attenuation from walls and incorporate the results into the position estimation. However, it requires building information modelling (BIM) to carry out the iterative process [29]. Thus, this algorithm does not provide a direct improvement of position accuracy from the signal itself. Park et al. presented a new probabilistic local search (PLS) algorithm [29] using BLE network technology. The results of PLS indicate that PLS outperforms other conventional methods when the signal interference is high and performs comparably when the signal interference is minimal. However, the RSSI data in the NLOS conditions are not discussed properly in their work. If the NLOS interference is serious and the number of BLE beacons in the LOS condition is less than 3, the position uncertainty of the target will be caused by the evaluation process. In this paper, we refer to the particle generation and evaluation process in [29], and to solve the problem of position uncertainty, we develop the particle selection and NLOS identification process and improve the evaluation process of [29].

Pedestrian dead reckoning (PDR) is a widely-adopted localisation technique using an Inertial Measurement Unit module or handheld devices like smartphones [30]. The basic principle is to add up small movements from a known starting point to estimate the trajectory of the pedestrian. The major disadvantage of PDR is the high error propagation due to the relative movement changes. The variations in the step length and the direction of each step add up and lead to very approximate position detection after a few steps. Therefore, a recalibration of the user position is required at regular intervals [30,31,32]. To decrease the drift of PDR, it must be combined with other signals such as GPS [33], WiFi [34,35], BLE [36], and so on. In [37], the Indoor Positioning Systems (IPS), which can be applied to mass market applications, has been surveyed and the hybrid systems are reviewed focusing on the current solutions available in the literature that can be applied to mass market applications. A hybrid range-free-based algorithm for the micro-localization of visitors in large public buildings is presented in [38]. The algorithm combines information from cheap BLE beacons and NFC passive tags, sensors built into the mobile phone (accelerometer, compass, and gyroscope) and data from BIM. In [39], a hybrid real-time indoor localization architecture was proposed. The positioning algorithm fuses the first model based real-time PDR and proximity BLE beacons and does not require any training or calibration phase. The adoption of a heel strike detection technique to carry out step detection and the use of the inverted pendulum model to estimate step length on smartphones have been validated through a stereo-photogrammetric system. In [40], a hybrid-tracking system based on a particle filter is proposed and it combines the PDR estimates, the floor plan information, and the connectivity with a number of pre-deployed wireless sensor nodes. In [41], a similar system is implemented but using a Kalman filter to combine PDR estimates, GPS readings when available, and activity-based map matching.

In order to reduce the negative impact of NLOS and improve the localization accuracy, the signals in the NLOS conditions need to be first identified and then mitigated. NLOS identification and mitigation techniques developed to date have been primarily investigated for UWB signals [42,43,44,45,46]. However, with much narrower bandwidths, typical BLE devices can only report RSSI data rather than these detailed features. As such, how to identify and mitigate LOS/NLOS conditions with this single, rather poor measurement is one of the challenges of this work. In [47], two classifiers based on machine learning Least Square Support Vector Machine Classifier and Gaussian Processes Classifier and one other based on hypothesis testing (Hypothesis Testing Classifier) are used to identify the NLOS conditions. However, the costly training phase is a great limitation when designed for implementation on mobile devices.

This paper proposes an RSSI/PDR-based probabilistic position selection algorithm (PPSA) in a sustainable indoor computing environment. To reduce the negative influence in NLOS conditions, we present a method of NLOS identification that leverages RSSI measurements and PDR data, which greatly improves the potential for RSSI-based localisation.

The rest of this paper is organised as follows. Section 2 introduces the architecture of the proposed indoor localisation system. Section 3 introduces the details of the proposed NLOS identification method and the proposed localisation algorithm. Section 4 analyses the results of the experimental implementation of the proposed localisation algorithm. Finally, the conclusions of the study are presented in Section 5.

2. Architecture of the Proposed Indoor Localisation System

In this paper, our system involves general localisation data from BLE devices deployed in an indoor environment and using them to process the data and estimate the user’s location using our proposed algorithm in order to improve the provided positioning accuracy. Here, we present details of the localisation system. Figure 1a shows the architecture of the BLE indoor positioning system and Figure 1b shows the BLE beacons and the smartphone used in this paper. To build this positioning system, we deployed 32 BLE beacon on the ceiling and the distance between every two beacons is about 6 m. An assumption in the indoor localisation system is that there are at least a few beacons that generate the signals in LOS. For this to be guaranteed in an indoor environment, the deployment of beacons needs to be such that no areas exist where none of the beacons is in near proximity.

In the BLE positioning system, the data format during the time the iteration is set as $[rss{i}_1,rss{i}_2,\cdot \cdot \cdot ,rss{i}_m,{\delta }_1,{\delta }_2,\cdot \cdot \cdot ,{\delta }_m,positionID,\overline{\alpha },{\sigma }_{\alpha },v]$, where $rss{i}_1,rss{i}_2,\cdot \cdot \cdot ,rss{i}_m$ represent the RSSI data received from the BLE beacons; ${\delta }_1,{\delta }_2,\cdot \cdot \cdot ,{\delta }_m$ represent the NLOS identification results of m propagation paths; positionID represents the map information which is stored in the database, and different positionIDs represent different places, such as corridor, room 907, room 908. This can be obtained by the NLOS identification result; the target should have the same positionID with the largest number of beacons in LOS. The parameters $\overline{\alpha }$, ${\sigma }_{\alpha }^{}$, and v are the expectation, the standard deviation of the heading angles, and the current speed, respectively, which are determined by the PDR data collected by smartphone during the time slot. In this paper, the reception frequencies of PDR and BLE data are 1000 times/s and 10 times/s, respectively, and the time period of the iteration is set to 1 s.

To enhance the robustness of the estimation, the positioning process of the proposed system includes initial positioning and normal positioning in two stages. The details of these two steps are described in the following sub-sections.

2.1. The Initial Positioning

The initial positioning refers to the first positioning. In this subsection, we present an overview of the initial positioning. It consists of three main modules: a signal receiving and processing module, an NLOS identification module, and a localisation module. Figure 2 shows the process of the initial positioning.

First, the localisation data are gathered and processed by positioning equipment to prepare for the next step. The NLOS identification module then processes the data gathered from the previous step and identifies the propagation condition between every BLE localisation device and the positioning equipment. In the initial positioning, we analyse the results of the NLOS identification and take the coordinates of the BLE localisation device in the best propagation condition as the centre of particle generation. The results of the initial positioning are calculated by our proposed PPSA.

2.2. The Normal Positioning

The normal positioning refers to the positioning process after the initial positioning. In this subsection, we discuss the process applied in the normal positioning step in detail. As with the initial positioning, this step also consists of three main modules: a signal receiving and processing module, an NLOS identification module, and a localisation module. Figure 3 shows the process of the normal positioning.

As shown in the figure, the coordinate of the initial positioning result is used as the centre of particle generation in the first execution of the normal positioning and then we generate random particles using the previous position as the centre. After the NLOS identification, the information on the propagation condition between the BLE beacons and target is acquired to input the localisation module along with PDR data and map information. We obtain the localisation result when all the above steps are completed and take it as the centre of the particle generation of the next iteration.

3. BLE and PDR-Based Probabilistic Position Selection Algorithm

The proposed PPSA is described in this section and can be referred to in the system diagram shown in Figure 4. As shown in the figure, the algorithm consists of three main parts: the generation of random particles, particle selection, and the process of evaluating the particles. The details of these four parts are described in the following.

3.1. Generation of Random Particles

The PPSA algorithm iteratively generates randomly generated particles. The coordinate of the initial positioning result is used as the centre of the particle generation in the first execution of the normal positioning and then we generate random particles using the previous position as the centre. The generation of random particles at each update interval should cover the distance range that a pedestrian can move during that interval. The radius of randomly generated particles needs to be larger than the current walking speed of a pedestrian to provide an additional buffer for the position estimation. The current speed v can be directly obtained by the PDR of the smartphone and the radius must be set larger than $\mathrm{v}\Delta \mathrm{t}$. It is determined to be $1.5\mathrm{v}\Delta \mathrm{t}$ in this paper, where $\Delta \mathrm{t}=1\mathrm{s}$.

3.2. NLOS Identification

To cope with adverse signal interference from changing the indoor layout and its negative impacts on localisation accuracy, an NLOS identification method was devised. Our proposed NLOS identification method combines RSSI and PDR data to detect the propagation conditions between every beacon node and pedestrian. Similar to [47], we set a threshold to classify the beacons in the LOS and NLOS conditions. In order to design them for implementation on mobile devices, the location prediction process is achieved based on PDR and the resource consumption of this method is quite low.

We assume ${[X_{k-1},Y_{k-1}]}^T$ is the coordinate of the last positioning result at the (k−1)th time slot, $v_k$ and ${\alpha }_k$ represent the velocity and heading angle at the kth time slot which are measured by the PDR, respectively. Thus, we can predict the positioning result at the kth time slot. It can be expressed as

$$\{\begin{array}{c}\stackrel{\wedge }{X_k}=X_{k-1}+v_k·\sin {\alpha }_k\\ \stackrel{\wedge }{Y_k}=Y_{k-1}+v_k·\cos {\alpha }_k\end{array}$$

(1)

As shown in the Figure 5, the signals from node A and node B are in the LOS and NLOS conditions, respectively. Assuming that the coordinate of the beacon node we need to identify is ${[x_N,y_N]}^T$, the distance between this node and the predicted position can be calculated by the following formula.

$$\stackrel{\wedge }{d}=\sqrt{{(\stackrel{\wedge }{X_k}-x_n)}^2+{(\stackrel{\wedge }{Y_k}-y_n)}^2}$$

(2)

Since the signal will be faded gradually and the intensity will be decreased with extended propagation distance, the final received signal intensity can be used to estimate the transmitter–receiver distance. Generally, the signal propagation model can be expressed as the intensity which is shown in Equation (3) to estimate the transmitter-receiver distance.

$$\mathrm{RSSI}={\mathrm{RSSI}}_0-10n_p\log (\frac{d}{d_0})+w_{\mathrm{LOS}/\mathrm{NLOS}}$$

(3)

where $\mathrm{RSSI}$ represents the signal intensity received by the BLE beacon at distance $d$; ${\mathrm{RSSI}}_0$ is the received signal intensity at distance $d_0$ (typically 1 m for indoor systems); $n_p$ is path loss factor which can be calculated by the BLE data measured at a different distance to the BLE beacon; in this paper, every set of BLE data had 1000 groups of RSSI data received from the same beacon; and $w_{\mathrm{LOS}/\mathrm{NLOS}}$ represents the deviation in the LOS and NLOS condition, and it can be expressed as

$$\{\begin{array}{c}{w}_{\mathrm{LOS}}\sim N(0,{\sigma }_{\mathrm{LOS}}^2)\\ w_{\mathrm{NLOS}}\sim N({\mu }_{\mathrm{NLOS}},{\sigma }_{\mathrm{NLOS}}^2)\end{array}$$

(4)

In this paper, after the path loss factor $n_p$ is determined according to Equation (3), the parameters ${\mu }_{\mathrm{NLOS}}$, ${\sigma }_{\mathrm{NLOS}}^2$, and ${\sigma }_{\mathrm{LOS}}^2$ can be determined by the RSSI data collected in the NLOS and LOS conditions, respectively.

Assuming that the propagation condition is LOS, we can estimate the RSSI data at ${[{\stackrel{\wedge }{X}}_k,{\stackrel{\wedge }{Y}}_k]}^T$ by using Equations (2) and (3).

$${\stackrel{\wedge }{\mathrm{RSSI}}}_k={\mathrm{RSSI}}_T+w_p$$

(5)

where ${\stackrel{\wedge }{\mathrm{RSSI}}}_k$ represents an estimate of the signal strength at ${[\stackrel{\wedge }{X_k,}\stackrel{\wedge }{Y_k}]}^T$; ${\mathrm{RSSI}}_{\mathrm{T}}$ represents the ideal signal strength without error; $w_p$ represents the error caused by the deviation of the last position and the PDR data and we assume that it obeys $N(0,{\sigma }_p^2)$ where ${\sigma }_p$ is the standard deviation of $w_p$.

Suppose the received signal strength at this time is $R{\mathrm{SSI}}_k$. Due to the complexity of the indoor environment, we can represent it by the following equation.

$${\mathrm{RSSI}}_k={\mathrm{RSSI}}_T+w_{\mathrm{LOS}/\mathrm{NLOS}}$$

(6)

where ${\mathrm{w}}_{\mathrm{LOS}/\mathrm{NLOS}}$ represents the deviation in the LOS and NLOS conditions, respectively.

The difference between the measured and predicted value can be expressed as

$$\delta ={\mathrm{RSSI}}_k-\stackrel{\mathrm{Ù}}{\mathrm{RSSI}}=w_{\mathrm{LOS}/\mathrm{NLOS}}-w_p$$

(7)

In the LOS condition, $\delta \sim N(0,{({\sigma }_{\mathrm{LOS}}+{\sigma }_p)}^2)$.

In the NLOS condition, $\delta \sim N({\mu }_{\mathrm{NLOS}},{({\sigma }_{\mathrm{NLOS}}+{\sigma }_p)}^2)$.

In order to identify the propagation conditions, we need to determine an optimal threshold $T{H}_{best}$.

$$th=T{H}_{best}:r(T{H}_{best})=\underset{th}{\min }r(th)$$

(8)

where $r(th)$ is defined as Equation (9).

$$r(th)={\displaystyle \underset{th}{\overset{+\infty }{\int }}\frac{1}{\sqrt{2\pi {\sigma }_1^2}}}\exp (-\frac{w_1^2}{2{\sigma }_1^2})d{w}_1+{\displaystyle \underset{-\infty }{\overset{th}{\int }}\frac{1}{\sqrt{2\pi {\sigma }_2^2}}\exp (-\frac{{(w_2-{\mu }_{NLOS})}^2}{2{\sigma }_2^2})}d{w}_2$$

(9)

where ${\sigma }_1={\sigma }_{LOS}+{\sigma }_p$, ${\sigma }_2={\sigma }_{NLOS}+{\sigma }_p$.

$$\{\begin{array}{cc}\delta \ge T{H}_{best}& NLOS\\ \delta <T{H}_{best}& LOS\end{array}$$

(10)

3.3. Particle Selection

As shown in Figure 6, in order to reduce the area of the evaluation process and decrease the time complexity of the algorithm, we selected particles in the area A1 determined by using the results of the NLOS identification and map information. N1, N2, N3, and N4 are four pre-installed BLE beacons, point L is the previous position, and the round L represents the range of particle generation.

Through the results of NLOS identification, we can make a preliminary judgment on the current position and identify the location ID. According to the location ID, the particles outside the area can be filtered out. As shown in Figure 6, we selected beacon N2 as the centre of the ring because it has the best propagation conditions. The inside radius and outer radius are express as $d_{low}$ and $d_{high}$, respectively. It is obvious that beacon N2 is in the LOS condition, thus, the current RSSI obeys $N(\mu ,{\sigma }_{LOS}^2)$. According to the 3 sigma principle, the probability of the interval $\left(\mu -3{\sigma }_{LOS},\mu +3{\sigma }_{LOS}\right)$ is 99.73%. Therefore, ${\mathrm{RSSI}}_{low}$ and ${\mathrm{RSSI}}_{high}$ can be represented as

$${\mathrm{RSSI}}_{low}=\mu -3{\sigma }_{LOS}$$

(11)

$${\mathrm{RSSI}}_{high}=\mu +3{\sigma }_{LOS}$$

(12)

where ${\mathrm{RSSI}}_{low}$ and ${\mathrm{RSSI}}_{high}$ represent the lower and upper limit of the RSSI value; $\mu$ is the mean value of the RSSI data received by the smartphone from the beacon in the best propagation condition during this time slot. According to Equation (3), $d_{low}$ and $d_{high}$ can be expressed as

$$d_{low}={10}^{\frac{{\mathrm{RSSI}}_0-{\mathrm{RSSI}}_{low}}{10n_p}}·d_0$$

(13)

$$d_{high}={10}^{\frac{{\mathrm{RSSI}}_0-{\mathrm{RSSI}}_{high}}{10n_p}}·d_0$$

(14)

Therefore, the particles in area A1 are the results of particle selection.

3.4. Evaluation Process of Particles

Upon receiving the RSSI data from the transmitters, the evaluation of each particle takes place. The evaluation process consists of the three following parts.

In the first part, the evaluation process involves the comparison of the collected ground true RSSI with the estimated RSSI. Equation (3) represents the distance propagation model. By using this equation and its parameters, the RSSI can be calculated based on the coordinates of the particles and BLE beacons. Suppose the coordinates of particles after selection are ${[X_i,Y_i]}^T,i=1,2,\dots ,I$ ($I$ represents the number of selected particles), the coordinates of BLE beacons are ${[x_n,y_n]}^T,n=1,2,\dots ,N$ ($N$ represents the number of received BLE beacons). The distance between the particles and BLE beacons can be expressed as

$$dis=\sqrt{{(X_i-x_n)}^2+{(Y_i-y_n)}^2}$$

(15)

The condition of every propagation path is identified by the NLOS identification method. According to Equations (3) and (15), the expected RSSI data transmitted from the BLE beacons can be computed. Equations (16)–(19) describe the first evaluation part for a particle with respect to the BLE beacons.

$$P_{i,j}=\mathrm{normpdf}(RSS{I}_{i,j},\overline{RSS{I}_{i,j}},{\sigma }_{i,j})$$

(16)

$${\sigma }_j=\{\begin{array}{cc}{\sigma }_{LOS}& LOS\\ {\sigma }_{NLOS}& NLOS\end{array}$$

(17)

In Equation (16), normpdf means the normal probability density function; $P_{i,j}$ represents the normal probability density function value of point $i$ for sensor $j$; the first parameter ${\mathrm{RSSI}}_{i,j}$ represents the received ground true RSSI. Meanwhile, the second parameter $\overline{RSS{I}_{i,j}}$ represents the expected RSSI that can be obtained from Equations (3) and (15), and the third parameter ${\sigma }_{i,j}$ represents the standard deviation of RSSI. As mentioned above, the received RSSI data obeys $N(\mu ,{\sigma }_{LOS/NLOS}^2)$ in the LOS and NLOS conditions. Thus, the value can be achieved as a result of NLOS identification.

In order to make the PPSA algorithm applicable in a dynamic environment, the propagation status of each beacon should be estimated by the NLOS identification module. When ${\delta }_{\mathrm{j}}\ge T{H}_{best}$, the propagation path should be discarded. When ${\delta }_{\mathrm{j}}<T{H}_{best}$, the evaluation result of this part can be expressed as

$$P_1^i={\displaystyle {\sum }_{j=1}^n{\mathrm{A}}_j{P}_{i,j}}$$

(18)

where n is the number of particles and ${\mathrm{A}}_j$ represents the normalized weight coefficient of propagation path j.

$${\mathrm{A}}_j=\frac{1/{\delta }_j}{{\displaystyle {\sum }_{j=1}^{n}1/{\delta }_j}}$$

(19)

where ${\delta }_{\mathrm{j}}$ is the NLOS identify value that can be calculated by Equation (7).

In the second part, the heading angle of the PDR data is used to evaluate the particles. Suppose that it obeys the Gaussian distribution $N(\overline{\alpha },{\sigma }_{\alpha }^2)$, where $\overline{\alpha }$ is the expectation of the heading angles, and ${\sigma }_{\alpha }^{}$ is the standard deviation. The parameters $\overline{\alpha }$ and ${\sigma }_{\alpha }^{}$ are determined by the PDR data collected by the smartphone during the time slot.

Suppose the coordinate of the particle $i$ is ${[x_i,y_i]}^T$ and the coordinate of the last position is ${[X_{k-1},Y_{k-1}]}^T$. Thus, the angle $\alpha$ between the connection of particle $i$, the last position, and the north direction is expressed as

$$\{\begin{array}{c}\begin{array}{ccc}\alpha =\arctan [\frac{(y_i-Y_{k-1})}{(x_i-X_{k-1})}]& if& x_i-X_{k-1}>0\end{array}\\ \begin{array}{ccc}\alpha =\arctan [\frac{(y_i-Y_{k-1})}{(x_i-X_{k-1})}]+\pi & if& (x_i-X_{k-1}<0)\&\&(y_i-Y_{k-1}>0)\end{array}\\ \begin{array}{ccc}\alpha =\arctan [\frac{(y_i-Y_{k-1})}{(x_i-X_{k-1})}]-\pi & if& (x_i-X_{k-1}<0)\&\&(y_i-Y_{k-1}<0)\end{array}\\ \begin{array}{ccc}\begin{array}{c}\alpha =\pi /2\\ \alpha =-\pi /2\end{array}& \begin{array}{c}if\\ if\end{array}& \begin{array}{c}(x_i-X_{k-1}=0)\&\&(y_i-Y_{k-1}>0)\\ (x_i-X_{k-1}=0)\&\&(y_i-Y_{k-1}<0)\end{array}\end{array}\end{array}$$

(20)

Equation (21) describes the second evaluation part for a particle based on the heading angle of PDR.

$$P_2^i=normpdf(\alpha ,\overline{\alpha },{\sigma }_{\alpha })$$

(21)

For particle $i$, the final score of the previous three evaluation parts is expressed as

$$re{s}_i=P_1^i+P_2^i$$

(22)

As the evaluation process takes place for all the particles, the algorithm updates the positioning result by selecting the particle that has the highest evaluation score.

$$P_{res}=Max(re{s}_i)$$

(23)

The following chart shows the detailed progress of the PPSA algorithm.

Algorithm 1: PPSA Algorithm

Input: The coordinates of BLE beacons ${[x_n,y_n]}^T,n=1,2,\dots ,N$, the measured RSSI data, the measured PDR data

Output: The positioning result ${[X_k,Y_k]}^T$

Start

1.  Input last positioning result ${[X_{k-1},Y_{k-1}]}^T$

2.  Set the radius of generating particles $r=1.5v\Delta \mathrm{t}$

3.  Generate random particles

4.  NLOS identification and correction

5.  FOR ($i=1$ to the number of particles)

6.   RUN Particles selection

7.   IF particle in the selection area

8.    RUN evaluation process

9.    IF ${\delta }_{\mathrm{j}}<T{H}_{best}$

10.     $P_{i,j}=normpdf(RSS{I}_{i,j},\overline{RSS{I}_{i,j}},{\sigma }_{i,j})$

11.     $P_1^i={\displaystyle {\sum }_{j=1}^n{\mathrm{A}}_j{P}_{i,j}}$

12.   ELSE

13.     Discard the propagation path j

14.   $P_2^i=normpdf(\alpha ,\overline{\alpha },{\sigma }_{\alpha })$

15.   $re{s}_i=P_1^i+P_2^i$

16.   $P_{res}=Max(re{s}_i)$

17.  ELSE

18.    Discard this particle

19.  END IF

20. END FOR

21. Get the positioning result of this time slot ${[X_k,Y_k]}^T$

22. Repeat step 1

END

4. Experimental Results

In this section, the proposed NLOS identification method is evaluated using numerical simulations. The performance of our proposed PPSA algorithm is also evaluated by real-time positioning using a smartphone. Moreover, a comparison of the PPSA algorithm with the trilateration + PDR and MLE + PDR is shown in the latter part of this section.

To evaluate the performance of the PPSA, we deployed 32 BLE beacons (model: CC2640, price: ¥20) on the ceiling of the ninth floor of the Beijing University of Posts and Telecommunications (BUPT) Research Building.

Table 1. The coordinates of the deployed BLE beacons.

Beacon ID	Coordinates	Beacon ID	Coordinates
1	(63.8, 30.5)	17	(76.1, 83.1)
2	(63.8, 38.5)	18	(69.8, 81.2)
3	(63.8, 44.5)	19	(68.8, 76.5)
4	(63.8, 50)	20	(71.9, 76.5)
5	(63.8, 55.6)	21	(68.8, 38.5)
6	(63.8, 59.9)	22	(47.7, 50)
7	(63.8, 63.2)	23	(51.5, 51.4)
8	(55.8, 63.6)	24	(60.2, 49.1)
9	(63.8, 66.6)	25	(47.5, 53.8)
10	(63.8, 71.3)	26	(51.5, 51.4)
11	(68, 71.3)	27	(59.1, 54)
12	(63.8, 76.5)	28	(72.9, 53.6)
13	(63.8, 82)	29	(69.4, 53.6)
14	(63.8, 87.5)	30	(69.4, 49.8)
15	(71.7, 86.8)	31	(72.9, 50.6)
16	(76.1, 87.5)	32	(70.5, 38.6)

shows the coordinates of the deployed BLE beacons. In order to obtain the real-time positioning result and show it on an indoor map, an Android app was developed to collect the real-time RSSI data and calculated the positioning results using the three algorithms. According to the heterogeneity of the transceivers, smartphones with different sensitivities and antenna patterns may measure different RSS in the same conditions. Therefore, we conducted the BLE signal tests on 6 different models of mobile phones. Figure 7 and

Table 2. The ${\sigma }_{LOS}$ and ${\sigma }_{NLOS}$ of different phone models.

Phone Model	${\mathit{\sigma }}_{\mathit{LOS}}$	${\mathit{\sigma }}_{\mathit{N}\mathit{L}\mathit{O}\mathit{S}}$
HUAWEI Mate 9	1.9	4.25
HUAWEI P9	2.02	4.32
HUAWEI Honor 8	1.96	4.19
ZTE A2017	2.16	4.38
ONEPLUS 5T	1.88	3.98
Coolpad 8675-A	2.11	4.32

show the test results for the 6 different phone models. In this paper, we use the Huawei Mate 9 to collect data. Because the deployed BLE beacons are the same model, the transmit power of every beacon is the same. The test results of the 6 models of phone are the mean of the RSSI data and the mean standard deviation measured in 4 different directions of the BLE beacon, and we collected 1000 groups of RSSI data for every direction.

Table 3. The parameter values for evaluating the performance of our proposed methods collected by Huawei Mate 9.

Parameter	Value
Received Power at 1 m	−55 dBm
Path Loss Factor (LOS)	2.7
Mean Speed of PDR	1.2 m/s
Mean Heading Angle of PDR	2.4

shows the parameter values that were collected by the Huawei Mate 9 for evaluating the performance of PPSA.

4.1. Evaluation of Proposed PPSA Algorithm

In this subsection, the performance of our proposed localisation algorithm is evaluated by comparing it with the trilateration + PDR and MLE + PDR methods. Figure 8 shows the developed Android app and test environment with deployed BLE beacons. Figure 9 shows the evaluation procedure. Before starting the evaluation process, the path loss model must be determined. According to the RSSI data measured by Huawei Mate 9 in Figure 7, the path loss factor $n_p$ can be fitted based on Equation (3) by Matlab 2017. As shown in Table 3, the fitting result of the path loss factor $n_p$ is 2.7. Therefore, the path loss model was determined.

In order to exactly evaluate the localisation accuracy of the various positioning algorithms, we need to determine the rule of localisation accuracy. In this paper, the root mean square error (RMSE) evaluation factor is used as the rule of localisation accuracy. In the two-dimensional positioning environment, the RMSE factor can be expressed as

$$\mathrm{RMSE}=\sqrt{E[{(\widehat{x}-x)}^2+{(\widehat{y}-y)}^2]}$$

(24)

where ${[\widehat{x},\widehat{y}]}^T$ denotes the coordinate of the estimated position and ${[x,y]}^T$ denotes the coordinate of the true position. The smaller the value of the RMSE is, the higher the localisation accuracy is.

4.1.1. Experiments in the Test Scenario

The performance of the three methods (PPSA, trilateration + PDR, MLE + PDR) was evaluated; for the PPSA algorithm, Equations (16)–(23) were used to evaluate its performance; and for the trilateration + PDR and MLE + PDR methods, the conventional computing process was applied. In this subsection, we collected 61 sets of RSSI data with the Huawei Mate 9 in different positions, shown in Figure 10, and the distance between each of the two positions is 1.2 m. The experimental evaluations indicate the performance of the positioning algorithms from best to worst are the PPSA, trilateration + PDR, and MLE + PDR. Figure 10 provides a visual depiction of the positioning results. It can be clearly confirmed from Figure 10 that our proposed PPSA algorithm achieves the closest result to the true path compared to the other two methods. For a more detailed assessment of the methods, Figure 11 provides quantitative results from the positioning error analysis and due to space limitations,

Table 4. The localisation errors of the three methods.

No.	True Positions	PPSA	Trilateration + PDR	MLE + PDR
1	(63.8, 32.2)	1.15	1.93	2.43
2	(63.8, 33.4)	0.72	1.41	2.82
3	(63.8, 34.6)	0.69	1.46	2.43
4	(63.8, 35.8)	0.71	2.54	2.03
5	(63.8, 37)	0.53	1.34	1.41
6	(63.8, 38.2)	0.81	0.67	1.62
7	(63.8, 39.4)	1.09	1.84	1.93
8	(63.8, 40.6)	0.59	2.11	2.12
9	(63.8, 41.8)	0.39	1.73	1.77
10	(63.8, 43)	0.76	1.52	1.28
11	(63.8, 44.2)	1.48	1.41	2.18
12	(63.8, 45.4)	1.51	1.78	3.03
13	(63.8, 46.6)	1.39	2.08	1.93
14	(63.8, 47.8)	0.85	1.83	0.95
15	(63.8, 49)	0.77	1.24	1.45
16	(63.8, 50.2)	1.14	1.13	1.68
17	(63.8, 51.4)	0.68	1.64	1.91
18	(63.8, 52.6)	0.25	1.74	1.66
19	(63.8, 53.8)	1.38	2.54	1.98
20	(63.8, 55)	0.85	2.02	2.44
21	(63.8, 56.2)	1.46	2.24	2.27
22	(63.8, 57.4)	1.50	1.89	1.95
23	(63.8, 58.6)	1.15	1.23	2.15
24	(63.8, 59.8)	0.98	1.54	2.51
25	(63.8, 61)	1.31	2.37	2.31

lists the errors of the first 25 points of the three methods from Figure 10. In the error analysis, the estimated positions were compared with the exact positions, the RMSEs were used to evaluate the positioning accuracy of each method. For most of the time slots, the smallest errors were observed in the proposed algorithm, whereas the largest errors were found in both the trilateration + PDR and MLE + PDR methods.

4.1.2. RMSE Changing Compared with the NLOS Rate

In this subsection, we further evaluate the performance of the three methods. In order to control the value of the NLOS rate, we simulated the BLE beacons’ propagation condition of the LOS and NLOS with the parameters in Table 2 based on the 61 sets of data measured previously. Equation (25) shows the definition of the NLOS rate.

$$\mathrm{NLOS}\_rate=\frac{pat{h}_{\mathrm{NLOS}}}{pat{h}_{\mathrm{LOS}}+pat{h}_{\mathrm{NLOS}}}$$

(25)

where $pat{h}_{\mathrm{LOS}}$ and $pat{h}_{\mathrm{NLOS}}$ represent the propagation path from the BLE beacon to the target in LOS and NLOS, respectively. Therefore, we can set the NLOS rate by changing the numbers of BLE beacons in LOS and NLOS. Figure 12 and Figure 13 indicate the results of the experiment by increasing the NLOS probability from 0 to 1 to show the impact of the NLOS rate on the localisation accuracy. We can conclude that the RMSE error of the above three methods have a similar characteristic: it tends to decrease with the increase in the NLOS rate. However, it is obvious that the proposed algorithm has the best localisation accuracy in the environment with the same NLOS rate. Meanwhile, it can be observed that the NLOS error has a significant impact on the localisation performance of both the trilateration + PDR and MLE + PDR methods. However, the proposed method is less affected by the NLOS error. Based on the analysis of these results, the performance of the three positioning algorithms from best to worst are the PPSA, trilateration + PDR, and MLE + PDR methods. Therefore, we can conclude that the proposed method can mitigate the NLOS error effectively.

4.2. Evaluation of Proposed NLOS Identification Method

This subsection reports the performance of our proposed NLOS identification method. Figure 14 shows the design of the NLOS identification evaluation process.

Before we start the evaluation process, the optimal threshold $T{H}_{best}$ needs to be determined. According to Equation (8), if ${\sigma }_{LOS}$, ${\sigma }_{NLOS}$, and ${\sigma }_p$ are known, $T{H}_{best}$ is determined and then the signal propagation state can be identified by our proposed method. Owing to the time interval between the localisation steps being quite short, the errors caused by the PDR are small enough to be ignored. Thus, parameter ${\sigma }_p$ can be ignored. To calculate the optimal threshold, the $T{H}_{best}$, ${\sigma }_{LOS}$, and ${\sigma }_{NLOS}$ must be measured. As shown in Table 2, the standard deviation ${\sigma }_{LOS}$ and ${\sigma }_{NLOS}$ can be acquired, where ${\sigma }_{LOS}=1.9$ and ${\sigma }_{NLOS}=4.25$. To evaluate the proposed NLOS identification method, we collected 160 sets of BLE data at 16 time slots using a Huawei Mate 9 and every set of BLE data had 1000 groups of RSSI data received from the same beacon in the same time slot. To obtain the last position as the input of this method, the proposed localisation algorithm is used to calculate the real-time positioning result at the previous time slot. The NLOS identification result $\delta$ can then be solved according to Equation (7). Figure 15 shows results of the evaluation of the proposed NLOS identification method.

The red and blue points represent the BLE beacons in the NLOS and LOS propagation conditions, respectively. The points above the threshold indicate that the signals received from these BLE beacons are NLOS conditions and the points below the threshold represent the signals under the LOS conditions.

In order to further evaluate the performance of the proposed NLOS identification method, we compared the localisation results when the NLOS identification process is applied and not applied to the localisation algorithm in Figure 16.

5. Conclusions and Future Work

In this paper, we proposed a novel probabilistic position selection algorithm based on the RSSI and PDR. In order to better filter out the particles and mitigate the impact of the NLOS condition on localisation performance, a low-complexity RSSI-based identification approach is proposed to identify the change in the channel situation between NLOS and LOS. This study assessed the developed algorithm in a multitude of simulations. The trilateration + PDR and MLE + PDR were subjected to the same testbeds to serve as a benchmark for comparison with the proposed algorithm. A sample data set was collected within our indoor test environment and used as a base to generate computationally simulated data to better validate the developed algorithm with various site conditions. In order to demonstrate the reliability and robustness of PPSA, the validation tests included different NLOS rates of signal propagation by varying the quality of the BLE signal propagation condition. Through comparison with the trilateration + PDR and MLE + PDR methods, we verified that the proposed algorithm outperforms the other methods in terms of the localisation accuracy and that it can better overcome the NLOS errors. The benefit of the PPSA is the ability to filter the signals in NLOS and further process the positioning estimation by giving more significance to the relatively reliable signals. An underlying assumption in this is that there are at least a few BLE beacons that generate reliable signals. For this to be guaranteed in an indoor environment, the deployment of the BLE beacons needs to be such that no areas exist where none of the beacons is in near proximity; in fact, PPSA is not a concern only for this BLE system, but also for all other systems that use RSSI-based technology. However, there are two limitations of the proposed PPSA. First, in dynamic LOS and NLOS mixed environments, which only rely on BLE beacons and PDR, the proposed RSSI and PDR based PPSA is unable to identify the environmental conditions such as moving people. Second, the use of fusion algorithms increases the computational complexity (o) and reduces the battery life of the smartphones.

To solve the limitations of the PPSA, the present study will be further developed in the following directions: (1) a building information modelling (BIM) will be investigated in conjunction with the proposed algorithm to improve the tracking accuracy; (2) in order to achieve a dynamic judgment of the environment, the smartphone camera will be combined with this system to identify the environmental conditions; and (3) an improved PPSA will be developed to balance the computational complexity and positioning accuracy.