Indoor Mobile Position Monitoring Model with iBeacon/Raspberry Pi 3 ― Enhancement of Two-Circles-Oriented Trilateration (TCOT) and Measurement Results

In the previous post, Raspberry Pi terminals (hereinafter also referred to as terminals) placed in a grid pattern (in a square grid) measured the signal strengths (RSSI) of iBeacons (hereinafter also referred to as beacons) , and calculated the beacon positions by a method called "Two-Circles-Oriented Trilateration."

In this post, this "Two-Circles-Oriented Trilateration" will be extended to allow terminals to be placed freely, not just limited in square grids for improving cost performance (cost per measurement precision), and to arrange terminals according to conditions of facilities and locations for system installation.

Overview of The Previous Two-Circles-Oriented Trilateration

The Two-Circles-Oriented Trilateration (hereinafter referred to as the old version) in the previous article calculated the distances (radii) between the terminals and the beacon based on the measured RSSI values of the beacon (B in the Figure 1), where
the terminals were arranged in a square grid (A to I in Figure 1). The distance (= radius) between the beacons was calculated. Trilateration ordinarily fails if the three circles in question do not overlap; however, this positioning model can assume the position of the beacon (B) by calculating the x coordinate using circle C1 and circle C2 (E and F respectively in the figure), and the y coordinate using circle C1 and circle C3 (E and B respectively in the figure).

Figure 1: Two-Circles-Oriented Trilateration (Old Version) Overview

For more information on Two-Circles-Oriented Trilateration, please read the previous article.

Enhancement of Two-Circles-Oriented Trilateration (TCOT)

One of the problems with the old version was that the terminals always had to be arranged in a square grid, and it was assumed that each terminal involved in positioning existed horizontally and vertically. This leads to maintenance and cost issues.
Therefore, we tried to enhance the previous Two-Circles-Oriented Trilateration so that the arrangement of terminals would be more flexible. Hereinafter, this enhanced version may be called TCOT.

TCOT Overview

This section describes TCOT. Figure 2 below shows one terminal always stays in the center of each square in Figure 1. Suppose the terminals that detect the beacon (B) at the shortest distance are E (circle C1), K (circle C2), B (circle C3) out of the thirteen terminals (A to M) in the order of detecting the beacon (B) from the shortest distance.

Now, please take a closer look at the circles C1 and C2 (Two-Circles Orientation). The previous model with a square grid without having a terminal in each square calculated only the x-axis (the horizontal axis) based on the circles C1 and C2. This new method does not expect the circles C1 and C2 to be placed vertically, so it is still too early to determine the x-axis at this point.
Instead, the blue area where the circles C1 and C2 intersect is used as a candidate for the beacon position. The circle C3 and its radius then locate the beacon within the blue area. Since the circle C3 does not reach the light blue area, the point closest to the circle C3 in the light blue area is determined as the position of the beacon.
The general idea of TCOT is that the circles C1 and C2 determine the candidate area, and then the circle C3 determines the final coordinate from that area.

Figure 2: The enhanced version of Two-Circles-Oriented Trilateration (TCOT)

Grid type

The terminal layout is called a grid or grid type.

Figure 3: Grid type


"Square + center type" aims to improve positioning accuracy while suppressing the increase in terminals. For example, if the 16m "Square type" does not provide satisfactory positioning accuracy, changing to an 8m grid would become costly and difficult to maintain. Instead, adding a terminal to the center of each square will improve the positioning accuracy.

The "Triangle" grid is used according to the shape of the location for system installation.

TCOT supports the "Square + center type" and the "Triangle type", but it is not limited to one grid type and is designed so that terminals can be arranged freely.
The Triangle type will not be covered in this post.
Before presenting the measurement results of TCOT, here is the overview of the system structure for the test we conducted this time.

System Structure Overview

product name explanation
iBeacon Aplix MyBeacon® Pro MB004Ac-DR2: 50 units (including fixed beacons for calibration)
Raspberry Pi Zero W/WH (receiver) Small computers: 13 units as receiving terminals for signals emitted by iBeacon. See node.js.
SQLite 3 Database.  See node.js.
Python 3/sym.py Based on the information recorded in the database by the development platform Raspberry Pi, we have developed a program that executes Two-Circles-Oriented Trilateration (TCOT).
node.js
  • Development platform. Develop a program that receives signals from iBeacon, processes them, and stores them into the database. This is a resident program on each Raspberry Pi and runs the above processes upon request from clients such as PCs.
  • Develop a program for plotting the position information of Raspberry Pi's and beacons with plotly. This is a resident program on the server and run the above process upon request from Web clients such as PCs.
plotly.js See node.js.
Fabric A tool for running commands from clients such as PCs against multiple Raspberry Pi terminals (thirteen in this test) all at once.

Measurement Test Results

Photo 1: Measurement test site

This time, we conducted measurement tests on the above-mentioned grid types, targeting the "Square type" and the "Square + center type", with grid widths set to 4m, 8m, 16m, and 32m* respectively.
The old version of Two-Circles-Oriented Trilateration was applied to the "Square type", and the TCOT of Two-Circles-Oriented Trilateration was applied to the "Square + center type".
The old version measured 41 beaconss, and TCOT measured 37 beacons. The reason why the number is different between the old version and TCOT is that TCOT required four additional beacons (fixed beacons) for calibration.

The two figures below show the results with numerical and graphical representations of the values ​​related to the errors between the actual coordinates of the beacon and the measured coordinates.

The actual position coordinate of each beacon and the measured coordinate error (distance error) are calculated by the following formula:

Distance error = | actual_x --estimated_x | + | actual_y --estimated_y |

actual_x and actual y are the actual coordinates of the beacon, and estimated_x and estimated_y are the coordinates calculated by the system. A value of 0 indicates that the actual and measured coordinates exactly match. The error of each beacon is calculated, and the average value(Error Ave), the maximum value (Error Max) , and the error rate are shown. The minimum value is approximately 0 for both the old version and TCOT, so it is omitted.

The error rate (Error rate) is obtained by the following formula:

Error rate = Error Ave / (Grid distance * 2)

This value is calculated by dividing the average value of the error by the grid distance (horizontal + vertical). The smaller this number is, the more accurately the beacon position is calculated compared to the grid distance.

Figure 4: Distance errors of the old version: Square + center type with 9 terminals

*The data for the 32m grid was generated from the 16m grid data.  The coordinates were calculated using only the data from five terminals except for the terminals B, D, E, F, and H.

Please note that the figure above uses the old version of Two-Circles-Oriented Trilateration.

The error rate decreases (improves) as the grid width increases, but increases (worsens) on the 32m grid. This suggests that when the distance between the beacon signal and the terminal is about 30m, the RSSI, which is originally low in accuracy, deteriorates further in this test environment.

Figure 5: Distance errors of TCOT: Square + center type with 13 terminals


* The data for the 32m grid was generated from the 16m grid data.  The coordinates were calculated using only the data from five terminals except for the terminals B, D, E, F, H, J, K, L, and M.

Please note that the figure above uses an enhanced version of TCOT for Two-Circles-Oriented Trilateration.

The measurement accuracy is improved by the Square + center type with TCOT (ver01) positioning than by the Square type with the old version.

The figure below is a graph comparing the old version and TCOT (ver01 in the figure). 

The red line shows the improvement rate. You can see that TCOT (ver01) is improved by 15% to 30% or more compared to the old version.

Individual Plot

The following table contains plot result files of the beacon positioning data generated by TCOT mentioned above. Unlike the conventional trilateration, TCOT calculates the position coordinates even if the three circles do not intersect, and the following plot files are visual representations of the TCOT results.

Two-Circles-Oriented Trilateration version
(TCOT ver.)
Grid type
(Grid type)
Grid size
(Grid size)
Download
(Download)
Old version (Old) Square 4m x 4m 4mGrid_R9I_old.pdf
Old version (Old) Square 8m x 8m 8mGrid_R9I_old.pdf
Old version (Old) Square 16m x 16m 16mGrid_R9I_old.pdf
Old version (Old) Square 32m x 32m 32mGrid_R9I_old.pdf
TCOT (ver01) Square + center 4m x 4m 4mGrid_R13c_ver01.pdf
TCOT (ver01) Square + center 8m x 8m 8mGrid_R13c_ver01.pdf
TCOT (ver01) Square + center 16m x 16m 16mGrid_R4Ir_ver01.pdf
TCOT (ver01) Square + center 32m x 32m 32mGrid_R5c_ver01.pdf

Batch Plot of All Beacons (Added on 2020/7/27)

Unlike the individual plots above, the following batch plots show the actual positions of all beacons and the estimated positions calculated by TCOT. TCOT has features including the individual plot and the batch plot of all beacons.

Legend: In the representation● -> ●,  the source of the arrow () indicates the actual beacon position, the target of the arrow () indicates the estimated position. () indicates the fixed beacon for calibration.

TPC_IPS (Protoype)

We have been developing an indoor positioning prototype called TPC_IPS to automate the above tests. TPC_IPS is roughly divided into two modules: FetchB and TCOT.

Fetch B

FetchB is placed on the application server and lets Raspberry Pi terminals (receivers, RPs) to scan beacon signals, and stores the data including UUIDs and RSSI values acquired by the RPs into the database.

FetchB is capable of running commands against many RPs in one go.

TCOT

TCOT calls up FetchB to extract the beacon information stored in the database, calculates coordinates based on the above-mentioned Two-Circles-Oriented trilateration, and eventually outputs or plots the result coordinates of each beacon.

TPC_IPS's TCOT module is described in the following video.




(Tsuchiya)



IPS Related Blog Posts

  1. Indoor Mobile Position Monitoring Model with iBeacon/Raspberry Pi 1  ―  Overview*
  2. Indoor Mobile Position Monitoring Model with iBeacon/Raspberry Pi 2   ―  RSSI/Distance Calibration and Trilateration*
  3. Indoor Mobile Position Monitoring Model with iBeacon/Raspberry Pi 3 ― Enhancement of Two-Circles-Oriented Trilateration (TCOT) and Measurement Results*
  4. Estimate the approximate position of the beacon with a small number of receivers in a large area such as Tokyo Dome(Google translate)
  5. Improving IPS Positioning Accuracy with Machine Learning
  6. TIPS for making IPS testbeds(Google translate)
  7. IPS Application Templates for FileMaker ― QuickIPS ―*

TPC's IPS Products

No comments:

Post a Comment