Triangulate example for iBeacons

Question

I am looking into the possibility to use multiple iBeacons to do a 'rough' indoor position location. The application is a kind of 'museum' setting, and it would be easier to be able to form a grid with locations for the different objects then individual beacons (although that might not be impossible too).

Are there examples, experiences, with using multiple beacons to triangulate into some kind of location, or some logic to help me on the way to write it myself?

Answer 1

I have been making some experiments to get a precise position using three beacons.

Results of trilateration

Unluckily, the results were very disappointing in terms of quality. There were mainly two issues:

1. In non-controlled environments, where you can find metals, and other objects that affect the signal, the received signal strength of the beacons changes so often that it seems impossible to get error range below 5 meters.
2. Depending on the way that the user is handling the receiver device, the readings can change a lot as well. If the user puts his/her hand over the bluetooth antenna, then the algorithm will have low signals as input, and thus the beacons will supposed to be very far from the device. See this image to see the precise location of the Bluetooth antenna.

Possible solutions

After talking with an Apple engineer who actively discouraged me to go down this way, the option I feel more inclined to use right now is brute force. Try to set up a beacon every X meters (X being the maximum error tolerated in the system) so we can track on this beacons grid the position of a given device by calculating which beacon on the grid is the closest to the device and assuming that the device is on the same position.

Trilateration algorithm

However, for the sake of completeness, I share below the core function of the trilateration algorithm. It's based on the 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 - a.x*a.x - a.y*a.y + b.x*b.x + b.y*b.y;
    Z = dB*dB - dC*dC - b.x*b.x - b.y*b.y + c.x*c.x + c.y*c.y;

    x = (W*(c.y-b.y) - Z*(b.y-a.y)) / (2 * ((b.x-a.x)*(c.y-b.y) - (c.x-b.x)*(b.y-a.y)));
    y = (W - 2*x*(b.x-a.x)) / (2*(b.y-a.y));
    //y2 is a second measure of y to mitigate errors
    y2 = (Z - 2*x*(c.x-b.x)) / (2*(c.y-b.y));

    y = (y + y2) / 2;
    return CGPointMake(x, y);
}

Answer 2

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;
}

1. Calculate the centre of gravity for a triangle (3 beacons)
2. calculate the shortest distance / nearest beacon
3. Calculate the distance between the beacon and the centre of gravity
4. Convert the shortest distance to co-ordinate units which is just a constant, he used to predict accuracy. You can test with varing the constant
5. calculate the distance delta
6. add the delta with the nearest beacon x,y.

After testing it, I found it accurate to 5 meters.

Please comment me your testing, if we can refine it.

Answer 3

The thing that really helped me was this project on Code.Google.com: https://code.google.com/p/wsnlocalizationscala/ it contains lots of code, several trilateration algorithms, all written in C#. It's a big library, but not really meant to be used "out-of-the-box".

Answer 4

We are also trying to find the best way to precisely locate someone into a room using iBeacons. The thing is that the beacon signal power is not constant, and it is affected by other 2.4 Ghz signals, metal objects etc, so to achieve maximum precision it is necessary to calibrate each beacon individually, and once it has been set in the desired position. (and make some field test to see signal fluctuations when other Bluetooth devices are present). We have also some iBeacons from Estimote (the same of the Konrad Dzwinel's video), and they have already developed some tech demo of what can be done with the iBeacons. Within their App it is possible to see a Radar in which iBeacons are shown. Sometimes is pretty accurate, but sometimes it is not, (and seems phone movement is not being considered to calculate positions). Check the Demo in the video we made here: http://goo.gl/98hiza

Although in theory 3 iBeacons should be enough to achieve a good precision, maybe in real world situations more beacons are needed to ensure the precision you are looking for.

Answer 5

For those who need @Javier Chávarri trilateration function for Android devices (for saving some 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 6

If you're anything like me and don't like maths you might want to do a quick search for "indoor positioning sdk". There's lots of companies offering indoor positioning as a service.

Shameless plug: I work for indoo.rs and can recommend this service. It also includes routing and such on top of "just" indoor positioning.