A regression model-based method for indoor positioning with compound location fingerprints

ABSTRACT

This paper proposed and evaluated an estimation method for indoor positioning. The method combines location fingerprinting and dead reckoning differently from the conventional combinations. It uses compound location fingerprints, which are composed of radio fingerprints at multiple points of time, that is, at multiple positions, and displacements between them estimated by dead reckoning. To avoid errors accumulated from dead reckoning, the method uses short-range dead reckoning. The method was evaluated using 16 Bluetooth beacons installed in a student room with the dimensions of 11 × 5 m with furniture inside. The Received Signal Strength Indicator (RSSI) values of the beacons were collected at 30 measuring points, which were points at the intersections on a 1 × 1 m grid with no obstacles. A compound location fingerprint is composed of RSSI vectors at two points and a displacement vector between them. Random Forests (RF) was used to build regression models to estimate positions from location fingerprints. The root mean square error of position estimation was 0.87 m using 16 Bluetooth beacons. This error is lower than that received with a single-point baseline model, where a feature vector is composed of only RSSI values at one location. The results suggest that the proposed method is effective for indoor positioning.

KEYWORDS:

• Indoor positioning
• integrated estimation
• radio fingerprinting
• dead reckoning
• machine learning
• non-linear regression

1. Introduction

To localize a position in an indoor environment, wireless-based methods and dead reckoning methods are widely used (Liu et al. 2007; Pei et al. 2016; Kjærgaard 2007). Trilateration methods estimate the position on the basis of the signal strength from wireless beacons or transmitters (Liu et al. 2006). Triangulation methods take into account the angle of signals as well as the signal’s strength (Liu et al. 2010; Shan and Yum 2007). Both methods are affected by multipath propagation, especially in indoor environments. Errors in position estimation with both methods can be large in indoor environments, although very short pulses using ultra-wideband technology can reduce the errors. Complex multipath and non-line-of-sight propagation are still a problem indoors (Xiao et al. 2015).

Fingerprinting methods are also used for indoor position estimation (Kjærgaard 2007). They are based on a radio fingerprint, or a feature vector, which is composed of the strength of the signals from multiple transmitters. Multipath propagation attenuates or intensifies signal strength indoors in a complicated manner. Fingerprinting methods can utilize the local increase and decrease in signal strength as features, and their estimation errors are regarded as relatively small. However, these methods have been used mainly for area estimation or for finding a reference point.

Dead reckoning methods are used to estimate a relative position from a reference point (Jimenez et al. 2009). Dead reckoning estimates a relative offset, that is, a displacement vector, usually on the basis of the double integration of acceleration and accumulates position estimation errors. Therefore, the errors become larger as integration time progresses.

Combinations of fingerprinting and dead reckoning are often used to locate a reference point by fingerprinting and then to measure the displacement by dead reckoning (Chang et al. 2015; Seitz et al. 2010). They are useful but do not solve the accumulation of estimation errors caused by dead reckoning. Therefore, they generally need other mechanisms to compensate for the accumulation.

In this paper, we propose a method that combines fingerprinting and dead reckoning differently from the conventional methods of combination. The proposed method estimates a position on the basis of compound location fingerprints, which are combinations of radio signals, or fingerprints, at multiple points of time (or positions), and the displacements between them.

A short moving distance between near times (points) can suppress the accumulated estimation errors caused by dead reckoning. Using fingerprints at multiple times (points) can increase the size of the feature vectors without increasing the number of transmitters. We believe that dead reckoning and fingerprinting can complement each other in this combination and thus improve the estimation accuracy.

2. Proposed method

Fingerprinting in the proposed method is based on a combination of fingerprints of radio wave strength at multiple times and the displacement vectors between them.

The proposed method can be divided into three steps: (1) collecting data, (2) building a regression model, and (3) estimating a position. Steps (1) and (2) are preparations for step (3). The first two steps are also called the “offline training phase,” and step (3) is also called the “online position determination phase.”

Assume that beacons $B_l\left(1\le l\le L\right)$ are installed in a target area where L is the total number of beacons.

2.1. Step for collecting data

The data collection step is the same as the measurement in conventional fingerprinting methods. A data collector measures the Received Signal Strength Indicators (RSSIs) from all beacons at all points in a measurement point set $C=\left\{c_i|1\le i\le N\right\}$, where $c_i$ are known and true coordinates and $N$ is the number of measurement points. In this paper, we focus on a simple coordinate system, that is, a two-dimensional plane, although the proposed method can easily be applied to a three-dimensional space.

Let $r_{i,k}$ ($1\le i\le N,1\le k\le K$) denote an RSSI vector, that is, a conventional fingerprint, on the k-th measurement at coordinates $c_i$, where measurement is repeated K times at each location.

An RSSI vector set $R_i$ at $c_i$ is expressed as

(1) $R_i=\left\{r_{i,k}|1\le k\le K\right\}$(1)

and the total set R(C) of RSSI vectors at the points in a measurement point set C is also represented as follows:

(2) $R\left(C\right)=\left\{r_{i,k}|c_i\in C,1\le k\le K\right\}=U_{C_i\in C}{R}_i$(2)

2.2 Step for building regression model

In the step for building a regression model, a non-linear regression model is built whose explanatory variable and objective variable are respectively a compound location fingerprint vector and a position.

A compound location fingerprint $g_{i,k,j,m}$ is composed of an RSSI vector $r_{i,k}\in R_i$ $\left(1\le k\le K\right)$, an RSSI vector $r_{j,m}\in R_j\left(1\le K\right)$, and a displacement $d_{i,j}=c_i-c_j$ between coordinate $c_i$ and coordinate $c_j$.

A compound fingerprint $g_{i,k,j,m}$ and a compound fingerprint set $G_{i,j}$ are respectively expressed by

(3) $g_{i,k,j,m}=[r_{i,k};r_{j,m};d_{i,j}]$(3)

and

(4) $G_{i,j}=\{g_{i,k,j,m}1\le k\le K,1m\le K\}$(4)

where $\left[a;b;c\right]$ concatenates vectors $a$, $b$, and $c$ into one vector.

A compound fingerprint set $G\left(C\right)$, which is made of RSSI vectors and displacements at points in a measurement point set $C$, is represented as follows:

(5) $G\left(C\right)=\left\{g_{i,k,j,m}|c_i\in C,c_j\in C,1\le k\le K,1m\le K\right\}=U_{C_i{C}_j\in C}{G}_{i,j}$(5)

A regression model M built with a data set G is represented by

$M\left[G\right]$

The model inputs a compound location fingerprint $f$ and outputs an estimated position $\hat{p}$. This is expressed as follows:

(6) $\hat{p}=M\left[G\right]\left(f\right)$(6)

2.3 Step for estimating position

In this step, a position is estimated on the basis of the built regression model with a measured compound location fingerprint. A user measures RSSIs at times $t_q$ and $t_r$. A displacement vector between time $t_q$ and $t_r$ is also estimated with dead reckoning. Figure 1 describes the relationship between the compound location fingerprints and their elements.

Figure 1. Compound location fingerprint in estimation.

Let $s_l\left(t\right)$ be an RSSI from beacon $B_l$ and $S\left(t\right)=\left(s_1\left(t\right),s_2\left(t\right),\dots ,s_L\left(t\right)\right)$ be a signal strength vector at time $t$.

A displacement vector $D\left(t_r,t_q\right)$ from time $t_q$ to time $t_r$ is estimated with dead reckoning. If $\left(t_r-t_q\right)$ is small, $D\left(t_r,t_q\right)\approx P\left(t_r\right)-P\left(t_q\right)$, where $P\left(t\right)$ is a position vector, that is, coordinates at time $t$, although $P\left(t_r\right)$ and $P\left(t_q\right)$ are unknown. The goal of the proposed method is to estimate $\hat{P}\left(t_r\right)$ precisely.

Compound location fingerprint $F\left(t_r,t_q\right)$is composed of $S\left(t_r\right),S\left(t_q\right),$ and $D\left(t_r,t_q\right)$, which is expressed as follows:

(7) $F\left(t_r,t_q\right)=\left[S\left(t_r\right);S\left(t_q\right);D\left(t_r,t_q\right)\right]$(7)

A compound location fingerprint $F\left(t_r,t_q\right)$ is used to estimate a position at time $t_r$, that is $\hat{P}\left(t_r\right)$, on the basis of the model built in the step for building a regression model. In other words, $\hat{P}\left(t_r\right)=M\left[G\right]\left(F\left(t_r,t_q\right)\right)$. Figure 2 illustrates an example of a compound location fingerprint.

Figure 2. Composition of compound location fingerprint.

3. Experiment

An experiment was conducted to evaluate the proposed method. We measured the RSSIs from beacons at multiple points and prepared the training data and validation data. We then built a regression model on the basis of the training data and estimated the position on the basis of the regression model with the validation data.

The goal of the experiment was to compare the proposed method with a baseline method that uses a regression model based on simple fingerprints at one measurement, that is, $R_i\left(1\le i\le N\right)$.

3.1. Experimental environment and devices

The proposed method was evaluated in a student room with the dimensions of 11 × 5 m and with many pieces of furniture and windows. The room was located in a reinforced concrete building. The origin of the coordinate system was set to one corner of the room. The shorter and the longer sides of the floor of the room were, respectively, the X and Y axis shown in Figure 3.

Figure 3. Layout of target room.

Sixteen Bluetooth beacons were placed in the room, as shown in Figure 3. The beacons were installed on the ceiling and on the walls. We attached 12 beacons to the ceiling and the remaining 4 on the walls between the ceiling and the floor. We used 16 MyBeacons whose specifications are shown in Table 1.

Table 1. Specifications of MyBeacon.

Name	MyBeacon
Bluetooth Version	Bluetooth 4.1 Smart
Frequency Band	2.4 GHz
Advertising Interval	100 ms
Output Power	−63 dBm
Power Supply	3V (AA battery × 2)

Measurement was performed with a Huawei P10 with the operating system Android 7.0. The specifications of the device are shown in Table 2. The device was mounted at a height of 1.35 m on a stand with casters so that it would be easy to change the location of the device. Figure 4 shows the measurement tool. We developed a measurement application program to measure Bluetooth RSSIs.

Table 2. Specifications of HUAWEI P10.

Name	HUAWEI P10
OS	Android 7.0 (Nougat)
Android SDK Version	25
Bluetooth Version	Bluetooth 4.2

Figure 4. Measurement tool.

3.2. Experimental procedure

In the step for collecting data, we measured the RSSI values of the Bluetooth beacons 10 times at 30 measuring points, which were points of intersections on a 1 × 1 m grid with no obstacles, as shown in Figure 3. The measuring point set is referred to as $C1$. The total number of valid pieces of data in the collected data set $R\left(C1\right)$ was 300. We divided $R\left(C1\right)$ into two parts, training data set $R_t$ and validation data set $R_v$, before composing the compound location fingerprints to avoid the compound fingerprints to contain the same fingerprint elements, which could affect the results. The compound fingerprints for training $G_t$ were composed of fingerprint elements in $R_t$ and those for validation $G_v$ were composed of fingerprint elements in $R_v$.

In the step for building a regression model, Random Forests (RF) (Breiman 2001; Breiman et al. 2001) was used to build regression models as it was effective for position estimation in previous experiments (Takayama et al. 2018). In particular, the proposed method with the RF outperformed the baseline method with the RF and the Support Vector Regression (SVR) method (Cortes and Vapnik 1995). We built the regression models using various numbers of beacons. Beacon bNN in Figure 3 represents a beacon with the identifier number NN. Beacons from b01 to bMM are used where the number of beacons is MM. For example, when the number of beacons is 3, three beacons b01, b02, and b03 are used.

In the step for estimating a position, calculated displacements were used on the basis of the collected data in the evaluation in this paper. These displacements were used to compose compound location fingerprints in the validation data set.

3.3. Evaluation criterion

We evaluated two methods with respect to the estimation distance error and accuracy.

A Root Mean Squared Error (RMSE) is used for estimation distance error. The RMSE is a standard deviation of prediction errors, or the residuals.

Let $p$, $\hat{p}$, $\left|\hat{p}-p\right|$, and $\epsilon$ be, respectively, a true position, an estimated position, a distance between $p$ and $\hat{p}$, and a permissible tolerance of error distance. If $\left|\hat{p}-p\right|\le \epsilon$, $\hat{p}$ is a correct estimate. The accuracy of estimation is the ratio of the number of correct estimates to the number of total estimates.

4. Results

4.1. Basic evaluation

We first evaluated the proposed method on the basis of regression models by 10-fold cross-validation, referred to as Model C1 $\left(=M\left[G_t\left(C1\right)\right]\right)$, built with a training data set $G_t\left(C1\right)$ that consists of compound location fingerprint vectors composed of 90% of a data set $R\left(C1\right)$ on the 1 × 1 m grid. The remaining 10% of the $R\left(C1\right)$ were used to create the validation data set $G_v\left(C1\right)$, where the total number of compound location fingerprints in each fold is 900 (= 30 × 30) in $G_v\left(C1\right)$ and 72,900 (= 270 × 270) in $G_t\left(C1\right)$. In comparison, conventional fingerprints of baseline method are 30 in $R_v\left(C1\right)$ and 270 in $R_t\left(C1\right)$ in each fold.

Figure 5 shows the RMSEs at the intersections ($C1$) of the 1 × 1 m grid: the baseline method, referred to as $B\left(C1\right)=B[R_t\left(C1\right)]\left(R_v\left(C1\right)\right)$, the proposed method, referred to as $P\left(C1\right)=P[G_t\left(C1\right)]\left(G_v\left(C1\right)\right)$. The RMSE of the position estimation in the proposed method with the RF using 16 beacons was 0.87 m. The RMSE of the position estimation of the baseline method using 16 beacons was 1.01 m. The RMSE in the proposed method is smaller than that in the baseline model.

Figure 5. RMSE using model with C1.

Figure 6 shows the cumulative accuracy of the two methods $B\left(C1\right)$ and $P\left(C1\right)$ with different numbers of beacons. Figure 6 shows that at a tolerance distance of 0.5 m using 16 beacons, the cumulative accuracy of the proposed method was 40.9%, which was better than that of the baseline method by 14.9 percentage points (pp). Similarly, the cumulative accuracy of the proposed method using six beacons was 33.8%, which was better than that of the baseline method by 16.2 pp.

Figure 6. Cumulative accuracy using model with C1.

The results of the basic evaluation show that the proposed method using compound location fingerprints improved the RMSE and the accuracy compared to the baseline method using the RSSI vectors at one point.

4.2. Accuracy at unknown points

We also evaluated estimation accuracy at unknown points in the proposed method on the basis of regression models by 10-fold cross-validation. We built regression models based on a data set collected at the intersections on a 2 × 2 m grid (10 times at 12 measurement points). The intersection points are referred to as $C2$, as shown in Figure 3. We then validated an in-between data set whose locations are at the intersections of the 1 × 1 m grid but not at the intersections of the 2 × 2 m one. The location points are referred to as $CX$. In other words, $CX=C1-C2$. The in-between points can be considered to be unknown locations whose data are not used in model building. Training data set $G_t\left(C2\right)$ was a data set composed of 90% of $G\left(C2\right)$ (10 times at 12 measurement points), that is, $\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{o}\mathrm{f}{G}_t\left(C2\right)$ is 11,664 (= 108 × 108). The regression models are referred to as Model $\mathrm{C}2\left(=M\left[G_t\left(C2\right)\right]\right)$. The validation data set included $G_v\left(C2\right)$ and in-between data set $G_v\left(CX\right)$. The number of compound location fingerprints in $G\left(CX\right)$ was 32,400 (= 180 × 180). Each fold in 10–fold cross validation has a validation set whose size is 468, that is, 144 (= 12 × 12) in $G_v\left(C2\right)$ and 324 (= 18 × 18) in $G_v\left(CX\right)$. In comparison, each hold in baseline method has a training set whose size is 108 in $R_t\left(C2\right)$ and a validation set whose size is 12 in $R_v\left(C2\right)$ and 18 in $R_v\left(C1\right)$.

The RMSEs for Model $\mathrm{C}2$ are shown in Figure 7. The RMSE of the position estimation of the proposed method with the RF using 16 beacons was 1.55 m. This error is smaller than that in the baseline model. The RMSE of the position estimation of the baseline method using 16 beacons was 1.70 m.

Figure 7. RMSE using model with C2.

Figure 8 shows the cumulative accuracy for Model $C2$. Let $Q\left(D_t,D_v,w,t\right)$ be the cumulative accuracy for the model built with training data set $D_t$, validation data set $D_v$, the number of beacons $w$ and w is a tolerance distance $t$ in meters. At a tolerance distance of 0.8 m using 16 beacons, $Q\left(G_t\left(C2\right),G_v\left(CX\right),16,0.8\right)$ was 29.3%, which was better than that of the baseline method by 3.8 pp. Similarly, at a tolerance distance of 1.0 m using six beacons, $Q\left(G_t\left(C2\right),G_v\left(CX\right),6,1.0\right)$ was 33.8%, which was better than that of the baseline method by 4.4 pp.

Figure 8. Cumulative accuracy using model with C2.

The evaluation of the RMSE at the unknown points showed that the RMSE at in-between points of the proposed method with the RF was better than that of the baseline method using models built on more data. This suggests that the proposed method with the RF is effective for precisely estimating a position.

5. Conclusions

We proposed a method for estimating position that is based on non-linear regression models with a unique combination of fingerprinting and dead reckoning. The evaluation results showed that the proposed method was better than the baseline method based on a single fingerprint, suggesting that it can be effective in indoor environments.

Additional information

Notes on contributors

Tomofumi Takayama

Tomofumi Takayama received his B.E., and M.E. degrees from Chiba University, Japan, in 2016, and 2018, respectively. He is now with Hewlett-Packard Japan, Ltd.

Takeshi Umezawa

Takeshi Umezawa received his B.E., M.E., and PhD degrees in Computer Science from Keio University, Yokohama, Japan in 1999, 2001, and 2007, respectively. He joined National Institute of Information and Communications Technology (NICT), Japan, in 2006. He is now with Chiba University as an Assistant Professor.

Nobuyoshi Komuro

Nobuyoshi Komuro received the B.E., M.E., and PhD degrees in Information Science from Ibaraki University, Japan, in 2000, 2002, and 2005, respectively. He is now with Chiba University as an Associate Professor with the Institute of Management and Information Technologies. He was with Rutgers University as a visiting scholar from May 2012 to Apr. 2013.

Noritaka Osawa

Noritaka Osawa received his B.S., M.S., and PhD degrees in information science from the University of Tokyo in 1983, 1985, and 1988, respectively. After working for a software company, the University of Electro-communications, and the National Institute of Multimedia Education, he is now with Chiba University as a professor.