Region-based massive positioning method using Bluetooth low energy

2.1 Path loss model of Bluetooth low energy (BLE)

Most of the trilateration techniques using BLE beacons directly convert the RSSI received from each scanner into a distance. The relative distance estimation method through RSSI uses the Friis formula, which expresses the attenuation according to the distance of radio waves in free space [21]-[24]. The attenuation signal strength PL(d) according to each distance is derived as follows:

In the above, d is the relative distance, λ is the signal's wavelength, and BLE follows the ISM band of 2.4 GHz. Equation (1) is a free space propagation model, and derives a log-distance path loss model that can be applied as an actual model according to the propagation characteristics. This path loss model calculates $$ \overline{\text{PL}}\left(d\right)$$, the average received RSSI according to the distance, as follows:

Here, d₀ refers to the far-field reference distance, and $$ \overline{\mathrm{P}\mathrm{L}}\left(d_0\right)$$ uses the path loss index n as the path loss at the reference distance. In real space, a loss owing to a shading effect occurs owing to structures such as surrounding walls, and thus the loss must be additionally considered. The log-normal model, which is the final path loss, can be derived as follows:

X_σ of the log-normal model means a Gaussian probability distribution with a standard deviation σ. It can obtain the relative position from the beacon scanner through this calculation process.

2.2 Device-based localization

RSSI-based positioning techniques are largely divided into mobile-based localization (MBL) and device-based localization (DBL) [4][25]. MBL estimates a user's location in a reference space using a mobile device such as a smartphone and anchor nodes. In most LBSs, MBL is often applied, but it is challenging to apply in industrial sites where an integrated positioning service needs to be operated, owing to the variety of devices and cost of individual terminals. Conversely, DBL is a method of estimating the user's location by analyzing the signal of the user's beacon with a central server through the scanner built into the infrastructure. A DBL-applied integrated positioning system has a low construction cost, but the server load increases as the number of people providing LBS increases. Therefore, it is necessary to consider the server's load to apply it to the recently enlarged conventions and smart systems.

3.1 Overview of the proposed positioning method

In this paper, we propose a region-based massive positioning method using BLE to build a low-cost, large-scale positioning system that can be directly applied to industrial sites. Unlike the general LBS operating environment, industrial zones have broad and complex spatial characteristics. These characteristics increase the cost of building a positioning system. In addition, a structure that changes according to the work schedule of the field makes it challenging to apply the existing mainstream fingerprint determination system. To solve this problem, in this study, DBL centered on the BLE beacon is used instead of the relatively expensive MBL to reduce the construction cost. In this DBL, as the load on the server increases as the number of service personnel increases, ROE stacking is applied to determine the existence of the target locally, so as to minimize this effect. Figure 1 shows the distributed processing method as proposed in a service space through scanners and servers.

Figure 1:

Structural diagram of the proposed positioning method scanner and server

As the proposed method applies the DBL approach, it consists of a user's terminal, multiple scanners in the reference space as shown in Figure 1, and the central server for location analysis. The scanner collects the MAC and RSSI signals of nearby beacons. It is possible to filter only the beacon(s) for positioning as preset through the beacon list. The proposed method analyzes the noise as a standard deviation using Equation (3) of the RSSI received to design the pass loss model. The standard deviation is reflected in the RSSI obtained in real-time, and the RSSI is converted into a distance through a pass loss model like in the conventional trilateration. We arranged Equation (3) as a distance-measured RSSI, which is derived as follows:

In the above, RSSI stands for the RSSI collected in real-time, and X_σ stands for the analyzed noise. By sending this to the server, the ROEs of all scanners are synthesized to obtain the final location information. Through this, the load of the server part can be distributed, and the amount of computation can be minimized.

3.2 Generating region of existing

Trilateration, a representative positioning algorithm, estimates through the intersection of circles with three or more anchor nodes whose positions are known based on the calculated distance. This method is widely used, because it is intuitive and easy to implement. However, it is not easy to apply in an environment where the signal deviation is significant, such as in a BLE environment, because there is a case where the circles do not intersect. To solve this problem, the proposed algorithm estimates the location through the ROE. The ROE, like a fingerprint, divides the reference space into grids at regular intervals to store the possibility of the existence of an object. Figure 2 schematically illustrates the form and concept of the ROE.

Figure 2:

Example of structure and concept of region of existing (ROE)

The ROE is a matrix composed of real numbers mapped to a grid, with a circle with an estimated distance R centered on each scanner. In the case of Figure 2, the four quadrants are expressed as centered on the sensor. The ROE proposed in the natural environment is generated by substituting the coordinates of each scanner for the entire reference space. The area of the circle indicating the estimated position is determined based on the BLE propagation model. This ROE is generated individually for each scanner and sent to the server, as shown in Figure 1. The distance R, which is the circle's radius, can be calculated through Equation (4) with the measured RSSI. To generate the ROE, each scanner must have its coordinates checked in advance, and from these coordinates, it can accurately generate the grid. Equation (5) gives the equation of the circle projected on each ROE, as follows:

Here, x_i and y_i denote coordinates in the reference space of the scanner. As BLE has a significant standard deviation of the signal strength, the circle centered on R has a donut-shaped area, rather than a line. This phenomenon occurs more in a space where multiple fading is severe. We applied the log-normal path loss model of Equation (3) to apply these propagation characteristics to the ROE, and in this case, it defined the probability distribution to follow a Gaussian distribution.

Figure 3 shows the Gaussian probability distribution, which means the probability at 1 σ. As the propagation characteristics of the environment in which the actual positioning system is constructed change according to the shape and material of each structure, a statistical analysis of the space is required. In the proposed algorithm, the circle is set as an area of 1 σ that can contain a majority signal of 68.2%. In this case, the upper and lower boundaries can be derived as Equations (6) and (7) through the standard deviation based on the measured RSSI, as follows:

Figure 3:

Gaussian probability distribution and probability according to standard deviation

The ROE can be composed of a straightforward binary matrix, because it denotes the space where an object is likely to exist on the grid. However, in a BLE environment, the closer the distance, the higher the reliability of the path loss model. Therefore, when there are many anchor nodes, the result may be biased to a location other than the location of the beacon. Thus, to reduce this bias, the collected RSSI was normalized to min-max, and the number to be input to the ROE grid was set. Equation (8) can be used to derive the value of the RSS ROE, as follows:

Here, min is the minimum of the collected RSSI, and max is the maximum of the collected RSSI. For each point of the ROE, the RSSI normalized to the inside of the boundary is input, and 0 is inputted to the outside and transmitted to the server. By processing this process in each distributed scanner, the load on the server is minimized.

3.3 Stacking region of existing and positioning

The ROEs generated by each scanner are transmitted and consolidated. As the normalized ROE has a value closer to 1 as the region with the highest probability of existence, the region with the highest probability of existence can be found by overlapping the ROE of the same beacon in all scanners. As this method consists of a simple matrix addition without calculations such as inverse matrix calculation or distance calculation between data, stable operation is possible even when positioning many people.

In most wireless communications, including those based on BLE, it is difficult to determine the actual difference in the RSSI at 1 m or less [15]. We set the grid to generate ROE as 1 m × 1 m. As a result, the location estimation through the initial grid can be very unstable. In addition, regions having a relatively large ROE may have a form in which they are scattered rather than continuous. It is an essential consideration, as a problem related to the reliability of the positioning system. We estimate the location by changing to a broader grid through ROE pooling.

Figure 4 is a conceptual diagram of the max pooling for ROE pooling. As the information of each grid refers to the possibility of existing in the corresponding space, it is downsampled by applying max pooling to maximize the likelihood. The user can adjust the size of the grid from 1 × 1 to 5 × 5 according to the setting of the environment initially. After that, the maximum position is detected based on the pooled ROE to estimate the position of the object. In this way, improved accuracy can be obtained.

Figure 4:

Conceptual diagram of the proposed ROE pooling

4.1 Experimental environment

In this study, to prove the validity of the proposed method, we collected and tested the RSSIs at each location of the BLE equipment in a natural environment. As shown in Figure 5(a), we measured the experiment at intervals of 1 m in a space of 5.0 m × 12.0 m in Room 604 of the KMOU Research Complex. Figure 5(b) shows the locations of the installed four scanners and 55 reference points at 1-m intervals. We set the height of the scanner to 1.8 m in consideration of the general AP installation location, and we put the beacon to 1.0 m in a review of the height of the human hand. For the experiment, the sensor of the scanner was CHIPSEN's BoT-nLE521. We measured the RSSI of the beacon 100 times per one reference point (RP) through four scanners. In addition, we simultaneously collected beacon data five times during one measurement, for stable measurement. In general, scanners are often installed in locations other than the RP. However, the proposed method required an experiment for generating a path loss model in the offline stage. Therefore, the actual path loss model was derived through scanner 1 in Figure 5(b) in this experiment.

Figure 5:

Experiment environment (a) Measurement configuration, (b) received signal strength indicator (RSSI) collection position

4.2 Analysis of path loss model and region of existing generation

The proposed method uses model-based distance estimation. Therefore, to generate the ROE, we needed to know the log-distance path loss model from Equation (2). This study selected the path coefficient 1.665 through curve fitting to determine the path loss model for the ROE. Figure 6 is a graph comparing the actual measured RSSI of scanner 1 and the RSSI of the path loss model. The x-axis represents the distance from the scanner, and the y-axis represents the RSSI. In Figure 6, the blue line is the measured RSSI, and the orange line is the estimated model. The log-distance path loss model derived through this is as follows:

Figure 6:

Curve fitting path loss model

In the above, d₀ is the far-field reference distance of the BLE environment, and d₀ is obtained as follows:

Here, D is the length of the antenna, generally 1/2 of the wavelength, and λ is the wavelength of BLE. As the frequency of BLE is 2.4 GHz, wavelength is 0.125 m, and length of the antenna is 0.06 m, d₀ is 0.0576 m. As the far-field had the same waveform, the reference distance of the path loss model was more than 0.06 m. Therefore, in this study, the far-field reference distance was calculated as 1 m for the convenience of calculation [26]. Figure 7 shows the generation of the ROE through the proposed method when the RSSI is -76.5 dBm.

Figure 7:

Generate ROE (a) Binary ROE, (b) RSS ROE

In Figure 7, the red dot at the (10, 11) position is the position of scanner 1, and the black dot at the (15, 15) position is the beacon's position. The yellow part formed around the scanner's position is the grid value of the ROE, and is composed of the binary ROE and RSS ROE of Equation (8). It can be seen that the actual number is changed through the legend on the right. We can estimate the exact position through the ROE in Figure 7(b).

4.3 Positioning experimental results

The ROEs collected from the scanner were stacked through the server, and the position was estimated by performing matrix sum. The grid with the highest value among the grid values of the stacking ROE was the position we estimated. Figure 8 shows the stacking ROE when the beacon position was (15,15). It is a heat map of the ROE that stacks the ROEs generated by each scanner. The red dots are the positions of the scanners, and the black dots are the positions of the measured beacons. Figure 8(a) is the stacking binary ROE, and Figure 8(b) is the stacking normalization ROE. At this time, the yellow pixel of the red bounding box is the portion having the highest value in the heat map, and is the location of the BLE beacon as estimated through the ROE. Here, the number of yellow pixels is 18 for the stacking binary ROE, and four for the stacking normalization ROE. This phenomenon, in which the remaining 14 pixels in Figure 8(b) have a smaller grid value owing to the normalization weight, solved the bias.

Figure 8:

Stacking ROE (a) Stacked binary ROE, (b) Stacked RSS ROE

Figure 9 confirms the performance change of the mean error distance and error rate according to the grid size to find the optimal ROE pooling size. The X-axis is the result of ROE pooling according to the grid size, and the left Y-axis is the mean error distance corresponding to the line graph. The right Y-axis corresponds to the bar graph as the error rate. The mean error distance was obtained through the location of the BLE beacon and Euclidean distance by getting the midpoint of the result of the stacking ROE. The error rate was set to True if the coordinates of the BLE beacon were included in the ROE result, and set to False if not, to obtain the ratio of the number of True. Looking at the results of applying ROE pooling, the mean error distance increased gradually and sharply from 5.34 m and 4.8 m to 5.76 m and 5.56 m in a 5 m × 5 m grid for the binary and RSS ROE, respectively. Also, if the error rate was checked, the performance was significantly improved from 92.18 % and 88.95 % to 97.98 % and 96.27 % in a 4 m × 4 m grid, respectively. Therefore, the optimal grid size for ROE pooling was 4 m × 4 m.

Figure 9:

Comparison mean error distance and accuracy according to grid size

Figure 10 shows the error distance in the case of 4 m × 4 m ROE pooling using a cumulative distribution function (CDF). The X-axis is error distance, and the Y-axis is the CDF. The mean error distances were 5.34 m and 4.8 m, respectively. The mean error distance of trilateration using the same path loss model was 5.20 m, which did not show a significant performance difference of 0.14 m from the binary ROE. Still, the normalization ROE showed a performance difference of 0.4 m.

Figure 10:

Cumulative distribution function of the error distance

Figure 11 shows the results of Figure 8 when 4 m × 4 m ROE pooling is performed. Similarly, the yellow pixel in the red bounding box is the location where the location of the BLE beacon is most likely to exist. Through the 4 m × 4 m grid ROE pooling, we increased the probability of including the location of the BLE beacon. The number of pixels in Figure 11(a) is five, and the number in Figure 11(b) is two. As a result of ROE pooling, the accuracy values were 97.98% and 96.27% for the binary and RSS ROE, respectively, showing excellent performance.

Figure 11:

4 m × 4 m ROE Pooling results (a) Stacking binary ROE (b) Stacking RSS ROE

Table 1 shows the error distance and accuracy of the test results in the experimental space through this method. As the grid size increased, the error distance increased by 0.33 m from 4.47 m to 4.8 m. Through the proposed method, it is possible to check the existence of Bluetooth low energy (BLE) beacons in the grid with high accuracy, and massive positioning through simple calculations is also possible.

Table 1:

Comparison of mean error distance and accuracy according to the algorithm

Author Contributions

Conceptualization, S. H. Lee; Methodology, S. B. Jeong; Soft-ware, S. B. Jeong and Y. J. Shin; Data curation S. B. Jeong and S. H. Lee; Writing-Original Draft Preparation, S. B. Jeong; Writing-Review & Editing, J. H. Seong and D. H. Seo; Supervision, D. H. Seo.