Triangulation Example for iBeacons

Question

I am exploring the possibility of using multiple iBeacons to perform a "rough" internal position of a location. The application is a kind of “museum” setting, and it would be easier to be able to create a grid with locations for different objects, and then separate beacons (although this may also be impossible).

Are there any examples, experiments, using several beacons to triangulate to some place or some kind of logic to help me on the way to writing it?

Answer 1

I did some experiments to get an accurate position using three beacons.

Trilateration Results

Unfortunately, the results were very disappointing in terms of quality. Basically there were two questions:

• In uncontrolled environments where you can find metals and other objects that affect the signal, the received signal level of the beacons changes so often that it seems impossible to get an error range below 5 meters.
• Depending on how the user processes the receiver, the readings can also vary greatly. If the user puts his hand on the bluetooth antenna, then the algorithm will have low signals as input signals, and therefore the beacons will be very far from the device. See this image to see the exact location of the Bluetooth antenna.

Possible solutions

After talking with an Apple engineer who was actively discouraging me from taking this path, the option that I think is more likely to be used right now is brute force. Try to adjust the beacon every X meters (X is the maximum error made in the system), so we can track the position of this device on this grid of beacons, calculating which beacon on the grid is closest to the device, and assuming that the device is in the same position.

trilateration algorithm

However, for completeness, I share the main function of the trilateration algorithm. It is based on paragraph 3 (“Three distances known”) of this article .

- (CGPoint)getCoordinateWithBeaconA:(CGPoint)a beaconB:(CGPoint)b beaconC:(CGPoint)c distanceA:(CGFloat)dA distanceB:(CGFloat)dB distanceC:(CGFloat)dC { CGFloat W, Z, x, y, y2; W = dA*dA - dB*dB - ax*ax - ay*ay + bx*bx + by*by; Z = dB*dB - dC*dC - bx*bx - by*by + cx*cx + cy*cy; x = (W*(cy-by) - Z*(by-ay)) / (2 * ((bx-ax)*(cy-by) - (cx-bx)*(by-ay))); y = (W - 2*x*(bx-ax)) / (2*(by-ay)); //y2 is a second measure of y to mitigate errors y2 = (Z - 2*x*(cx-bx)) / (2*(cy-by)); y = (y + y2) / 2; return CGPointMake(x, y); } 

Answer 2

I learned this. The term you want is trilateration. (In triangulation, you have angles of 3 known points. In trilateration, you have a distance from 3 known points). If you are Google, you should find several articles, including one on the Wiki. It involves solving a set of three simultaneous equations. The documents I saw were for three-dimensional trilateration - 2D is simpler because you can simply refuse the Z-term.

I found abstract math. I have not yet found the time to draw a general algorithm in a specific code, but I plan to solve it at some point.

Please note that your results will be VERY rude, especially in all but an empty room. The signals are weak enough that a person, a statue, or something that blocks visibility will significantly increase your distance reading. Perhaps you may have places in the building where constructive intervention (mainly from walls) makes some places more accurate than they actually are.

Answer 3

Here is an open source Java library that will do trilateration / multilateration: https://github.com/lemmingapex/Trilateration

It uses the popular nonlinear least squares optimizer, the Levenberg-Marquardt algorithm, from Apache Commons Math.

 double[][] positions = new double[][] { { 5.0, -6.0 }, { 13.0, -15.0 }, { 21.0, -3.0 }, { 12.42, -21.2 } }; double[] distances = new double[] { 8.06, 13.97, 23.32, 15.31 }; NonLinearLeastSquaresSolver solver = new NonLinearLeastSquaresSolver(new TrilaterationFunction(positions, distances), new LevenbergMarquardtOptimizer()); Optimum optimum = solver.solve(); // the answer double[] calculatedPosition = optimum.getPoint().toArray(); // error and geometry information RealVector standardDeviation = optimum.getSigma(0); RealMatrix covarianceMatrix = optimum.getCovariances(0); 

Most scientific examples, such as wikipedia , engage in exactly three circles and suggest accurate information. These circumstances make it possible to obtain simpler formulations of problems with exact answers and are usually not suitable for practical situations.

A problem in R ² or R ^{3 is} Euclidean space with distances that contain a measurement error, a region of interest (ellipse) or volume (ellipsoid) of a point. If a point estimate is needed instead of an area, you must use the area centroid or volume centroid. R ² requires at least 3 non-degenerate points and distances to obtain a single region; and thus, the space R ³ requires at least 4 non-degenerate points and distances to obtain a single domain.

Answer 4

Accurate internal positioning with iBeacon will be difficult for the following reasons:

• As stated in earlier comments, the iBeacon signal fluctuates greatly. The reason includes the multipath effect, the obstacles of a dynamic object between the phone and iBeacon when a person is moving, other 2.4 GHz interference, etc. Therefore, ideally, you do not want to trust 1 single packet information and instead perform some averaging for several packets from the same beacon. This requires that the distance between the phones and the beacons does not change too much between the several packages. For common BLE packages (such as StickNFind beacons), you can easily set the beacon speed to 10 Hz. However, for iBeacon it will be difficult because
• The frequency of the iBeacon beacon probably cannot be higher than 1 Hz. I will be glad if someone can point to a source that says otherwise, but all the information that I have seen so far confirms this statement. It really makes sense, since most iBeacons will run on battery power, and high frequency will significantly affect battery life. Given that the average speed of people moving is 5.3km (~ 1.5 m / s), so even if you just use a modest 3 beacon package for averaging, it will be difficult for you to get an accuracy of ~ 5 m.

On the other hand, if you can increase the frequency of the iBeacon to more than 10 Hz (which, I doubt it is possible), then you can get an accuracy of 5 m or more using the appropriate processing method. Firstly, trivial solutions based on the inverse square of the law , like trilateration, often do not work well, because in practice the distance / RSSI ratio for different beacons often leaves the Sqare Law on Reverse for reason 1 above. But while RSSI is relatively stable for a specific beacon at any particular place (which usually happens), you can use an approach called fingerprinting to achieve higher accuracy. The common method used for fingerprinting is kNN ( k-Nearest Neighbor ).

Update 2014-04-24

Some iBeacons can broadcast more than 1 Hz, for example, Estimote uses 5 Hz by default. However, according to this link : “This is a limitation of Apple. IOS returns beacon updates every second, no matter how often the device’s ads.” There is another comment (probably from Estimote): "Our beacons can be broadcast much faster, and can improve results and measurements." Therefore, it is unclear whether a higher frequency of iBeacon is useful.

Answer 5

If you're something like me and don't like math, you might need a quick search for "internal sdk positioning." There are many companies offering internal positioning as a service.

Shameless plugin: I work for indoo.rs and can recommend this service. It also includes routing and one on top of "only" internal positioning.

Answer 6

For those who need @Javier Chávarri trilateration function for Android devices (to save time):

 public static Location getLocationWithTrilateration(Location beaconA, Location beaconB, Location beaconC, double distanceA, double distanceB, double distanceC){ double bAlat = beaconA.getLatitude(); double bAlong = beaconA.getLongitude(); double bBlat = beaconB.getLatitude(); double bBlong = beaconB.getLongitude(); double bClat = beaconC.getLatitude(); double bClong = beaconC.getLongitude(); double W, Z, foundBeaconLat, foundBeaconLong, foundBeaconLongFilter; W = distanceA * distanceA - distanceB * distanceB - bAlat * bAlat - bAlong * bAlong + bBlat * bBlat + bBlong * bBlong; Z = distanceB * distanceB - distanceC * distanceC - bBlat * bBlat - bBlong * bBlong + bClat * bClat + bClong * bClong; foundBeaconLat = (W * (bClong - bBlong) - Z * (bBlong - bAlong)) / (2 * ((bBlat - bAlat) * (bClong - bBlong) - (bClat - bBlat) * (bBlong - bAlong))); foundBeaconLong = (W - 2 * foundBeaconLat * (bBlat - bAlat)) / (2 * (bBlong - bAlong)); //`foundBeaconLongFilter` is a second measure of `foundBeaconLong` to mitigate errors foundBeaconLongFilter = (Z - 2 * foundBeaconLat * (bClat - bBlat)) / (2 * (bClong - bBlong)); foundBeaconLong = (foundBeaconLong + foundBeaconLongFilter) / 2; Location foundLocation = new Location("Location"); foundLocation.setLatitude(foundBeaconLat); foundLocation.setLongitude(foundBeaconLong); return foundLocation; } 

Answer 7

My architect / manager, who wrote the following algorithm,

 public static Location getLocationWithCenterOfGravity(Location beaconA, Location beaconB, Location beaconC, double distanceA, double distanceB, double distanceC) { //Every meter there are approx 4.5 points double METERS_IN_COORDINATE_UNITS_RATIO = 4.5; //http://stackoverflow.com/a/524770/663941 //Find Center of Gravity double cogX = (beaconA.getLatitude() + beaconB.getLatitude() + beaconC.getLatitude()) / 3; double cogY = (beaconA.getLongitude() + beaconB.getLongitude() + beaconC.getLongitude()) / 3; Location cog = new Location("Cog"); cog.setLatitude(cogX); cog.setLongitude(cogY); //Nearest Beacon Location nearestBeacon; double shortestDistanceInMeters; if (distanceA < distanceB && distanceA < distanceC) { nearestBeacon = beaconA; shortestDistanceInMeters = distanceA; } else if (distanceB < distanceC) { nearestBeacon = beaconB; shortestDistanceInMeters = distanceB; } else { nearestBeacon = beaconC; shortestDistanceInMeters = distanceC; } //http://www.mathplanet.com/education/algebra-2/conic-sections/distance-between-two-points-and-the-midpoint //Distance between nearest beacon and COG double distanceToCog = Math.sqrt(Math.pow(cog.getLatitude() - nearestBeacon.getLatitude(),2) + Math.pow(cog.getLongitude() - nearestBeacon.getLongitude(),2)); //Convert shortest distance in meters into coordinates units. double shortestDistanceInCoordinationUnits = shortestDistanceInMeters * METERS_IN_COORDINATE_UNITS_RATIO; //http://math.stackexchange.com/questions/46527/coordinates-of-point-on-a-line-defined-by-two-other-points-with-a-known-distance?rq=1 //On the line between Nearest Beacon and COG find shortestDistance point apart from Nearest Beacon double t = shortestDistanceInCoordinationUnits/distanceToCog; Location pointsDiff = new Location("PointsDiff"); pointsDiff.setLatitude(cog.getLatitude() - nearestBeacon.getLatitude()); pointsDiff.setLongitude(cog.getLongitude() - nearestBeacon.getLongitude()); Location tTimesDiff = new Location("tTimesDiff"); tTimesDiff.setLatitude( pointsDiff.getLatitude() * t ); tTimesDiff.setLongitude(pointsDiff.getLongitude() * t); //Add t times diff with nearestBeacon to find coordinates at a distance from nearest beacon in line to COG. Location userLocation = new Location("UserLocation"); userLocation.setLatitude(nearestBeacon.getLatitude() + tTimesDiff.getLatitude()); userLocation.setLongitude(nearestBeacon.getLongitude() + tTimesDiff.getLongitude()); return userLocation; } 

• Calculate the center of gravity for a triangle (3 beacons)
• calculate shortest distance / nearest beacon
• Calculate the distance between the beacon and the center of gravity
• The conversion of the shortest distance to the coordinates of units that are only a constant, he used to predict accuracy. You can test with a constant change
• calculate distance delta li>
• add a delta with the nearest beacon x, y.

After testing, I found it accurate to 5 meters.

Comment on my testing if we clarify it.

Answer 8

I implemented a very simple Fingerprint algorithm for android 4.4, tested in a relative "bad" environment:

• about 10 wifi ap nearby.
• several other bluetooth signals nearby.

the accuracy seems 5-8 meters and depends on how I posted this 3rd Ibeacon TV company. The algorithm is pretty simple, and I think you can implement it yourself, steps:

• load the internal card.
• with a map for the entire pending positioning point.
• record all the data in the sample, the data should include: map coordinates, position signals and their RSSI.

therefore, when you start positioning, this is just the reverse side of the steps.

Answer 9

We are also trying to find the best way to accurately find someone in the room using iBeacons. The fact is that the power of the beacon radio signal is not constant, and it is affected by other 2.4 GHz signals, metal objects, etc. Therefore, to achieve maximum accuracy, it is necessary to calibrate each beacon separately and as soon as it is installed in desired position (and conduct field tests to see signal fluctuations when other Bluetooth devices are present). We also have some iBeacons from Estimote (the same from Konrad Dzwinel's video), and they have already developed a technical demo of what can be done with iBeacons. In their application, you can see the radar, which displays iBeacons. Sometimes it’s pretty accurate, but sometimes it’s not (and it seems that the phone’s movement is not considered to calculate positions). Check out the demo in the video we made here: http://goo.gl/98hiza

Although in theory 3 iBeacons should be sufficient to achieve good accuracy, perhaps in real situations more beacons are needed to ensure the accuracy you are looking for.

Answer 10

What really helped me was the Code.Google.com project: https://code.google.com/p/wsnlocalizationscala/ contains a lot of code, several trilateration algorithms, everything is written in C #. This is a large library, but was not really intended to be used out of the box.

Answer 11

I found the Vishnu Prahbu solution very useful. I ported it to C # if someone needs it.

 public static PointF GetLocationWithCenterOfGravity(PointF a, PointF b, PointF c, float dA, float dB, float dC) { //http://stackoverflow.com/questions/20332856/triangulate-example-for-ibeacons var METERS_IN_COORDINATE_UNITS_RATIO = 1.0f; //http://stackoverflow.com/a/524770/663941 //Find Center of Gravity var cogX = (aX + bX + cX) / 3; var cogY = (aY + bY + cY) / 3; var cog = new PointF(cogX,cogY); //Nearest Beacon PointF nearestBeacon; float shortestDistanceInMeters; if (dA < dB && dA < dC) { nearestBeacon = a; shortestDistanceInMeters = dA; } else if (dB < dC) { nearestBeacon = b; shortestDistanceInMeters = dB; } else { nearestBeacon = c; shortestDistanceInMeters = dC; } //http://www.mathplanet.com/education/algebra-2/conic-sections/distance-between-two-points-and-the-midpoint //Distance between nearest beacon and COG var distanceToCog = (float)(Math.Sqrt(Math.Pow(cog.X - nearestBeacon.X, 2) + Math.Pow(cog.Y - nearestBeacon.Y, 2))); //Convert shortest distance in meters into coordinates units. var shortestDistanceInCoordinationUnits = shortestDistanceInMeters * METERS_IN_COORDINATE_UNITS_RATIO; //http://math.stackexchange.com/questions/46527/coordinates-of-point-on-a-line-defined-by-two-other-points-with-a-known-distance?rq=1 //On the line between Nearest Beacon and COG find shortestDistance point apart from Nearest Beacon var t = shortestDistanceInCoordinationUnits / distanceToCog; var pointsDiff = new PointF(cog.X - nearestBeacon.X, cog.Y - nearestBeacon.Y); var tTimesDiff = new PointF(pointsDiff.X * t, pointsDiff.Y * t); //Add t times diff with nearestBeacon to find coordinates at a distance from nearest beacon in line to COG. var userLocation = new PointF(nearestBeacon.X + tTimesDiff.X, nearestBeacon.Y + tTimesDiff.Y); return userLocation; } 

Answer 12

Alternative equation

 - (CGPoint)getCoordinateWithBeaconA:(CGPoint)a beaconB:(CGPoint)b beaconC:(CGPoint)c distanceA:(CGFloat)dA distanceB:(CGFloat)dB distanceC:(CGFloat)dC { CGFloat x, y; x = ( ( (pow(dA,2)-pow(dB,2)) + (pow(cx,2)-pow(ax,2)) + (pow(by,2)-pow(ay,2)) ) * (2*cy-2*by) - ( (pow(dB,2)-pow(dC,2)) + (pow(cx,2)-pow(cx,2)) + (pow(cy,2)-pow(by,2)) ) *(2*by-2*ay) ) / ( (2*bx-2*cx)*(2*by-2*ay)-(2*ax-2*bx)*(2*cy-2*by) ); y = ( (pow(dA,2)-pow(dB,2)) + (pow(cx,2)-pow(ax,2)) + (pow(by,2)-pow(ay,2)) + x*(2*ax-2*bx)) / (2*by-2*ay); return CGPointMake(x, y); }