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 "TwoCirclesOriented Trilateration."
In this post, this "TwoCirclesOriented 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 TwoCirclesOriented Trilateration
The TwoCirclesOriented 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).
For more information on TwoCirclesOriented Trilateration, please read the previous article.
Enhancement of TwoCirclesOriented 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 TwoCirclesOriented 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 (TwoCircles Orientation). The previous model with a square grid without having a terminal in each square calculated only the xaxis (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 xaxis 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.
Grid type
The terminal layout is called a grid or 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 MB004AcDR2: 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 TwoCirclesOriented Trilateration (TCOT). 
node.js 

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 abovementioned 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 TwoCirclesOriented Trilateration was applied to the "Square type", and the TCOT of TwoCirclesOriented 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 actual position coordinate of each beacon and the measured coordinate error (distance error) are calculated by the following formula:
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:
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.
*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 TwoCirclesOriented 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.
* 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 TwoCirclesOriented 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.
TwoCirclesOriented 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.
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 abovementioned TwoCirclesOriented 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
 Indoor Mobile Position Monitoring Model with iBeacon/Raspberry Pi 1 ― Overview*
 Indoor Mobile Position Monitoring Model with iBeacon/Raspberry Pi 2 ― RSSI/Distance Calibration and Trilateration*
 Indoor Mobile Position Monitoring Model with iBeacon/Raspberry Pi 3 ― Enhancement of TwoCirclesOriented Trilateration (TCOT) and Measurement Results*
 Estimate the approximate position of the beacon with a small number of receivers in a large area such as Tokyo Dome(Google translate)
 Improving IPS Positioning Accuracy with Machine Learning
 TIPS for making IPS testbeds(Google translate)

IPS Application Templates for FileMaker ― QuickIPS ―*
No comments:
Post a Comment