Tools to determine exact location when using ibeacons

Question

We are working with a Retail client who would like to know if using multiple iBeacons throughout the store would help track a customer's exact location when they are inside the store (of course when they have the client's App installed).

I would like to know what software tools are already available for this purpose?

What is clear is that at the basic level the location of a device can be determined based on it's relative distance from multiple (at least 2) iBeacons. If so, aren't there tools that help with this?

Thanks

Answer 1

Obviously this is unlikely to work well due to the inconsistency of the RSSI value (bluetooth signal). However, this is the direction you may want to take it (adapted from lots of stackoverflow research):

Filter RSSI

I use a rolling filter with this whenever the beacons are ranged, using a kFilteringFactor of 0.1:

rollingRssi = (beacon.rssi * kFilteringFactor) + (rollingRssi * (1.0 - kFilteringFactor));

And I use this to get a rolling Accuracy value (in meters). (Thanks David!)

- (double)calculateAccuracyWithRSSI:(double)rssi {
    //formula adapted from David Young's Radius Networks Android iBeacon Code
    if (rssi == 0) {
        return -1.0; // if we cannot determine accuracy, return -1.
    }


    double txPower = -70;
    double ratio = rssi*1.0/txPower;
    if (ratio < 1.0) {
        return pow(ratio,10);
    }
    else {
        double accuracy =  (0.89976) * pow(ratio,7.7095) + 0.111;
        return accuracy;
    }
}

Calculate XY with Trilateration (Beacons 1, 2, and 3 are Beacon subclasses with pre-set X and Y values for location and distance is calculated as above).

float xa = beacon1.locationX;
float ya = beacon1.locationY;
float xb = beacon2.locationX;
float yb = beacon2.locationY;
float xc = beacon3.locationX;
float yc = beacon3.locationY;
float ra = beacon1.filteredDistance;
float rb = beacon2.filteredDistance;
float rc = beacon3.filteredDistance;

float S = (pow(xc, 2.) - pow(xb, 2.) + pow(yc, 2.) - pow(yb, 2.) + pow(rb, 2.) - pow(rc, 2.)) / 2.0;
float T = (pow(xa, 2.) - pow(xb, 2.) + pow(ya, 2.) - pow(yb, 2.) + pow(rb, 2.) - pow(ra, 2.)) / 2.0;
float y = ((T * (xb - xc)) - (S * (xb - xa))) / (((ya - yb) * (xb - xc)) - ((yc - yb) * (xb - xa)));
float x = ((y * (ya - yb)) - T) / (xb - xa);

CGPoint point = CGPointMake(x, y);
return point;

Answer 2

The easiest way to get an exact location is to put one iBeacons at each point you care about, then have an iBeacon-aware app compare the "accuracy" field (which actually gives you a rough distance estimate i meters), and assume the user is at the iBeacon point with the lowest "accuracy" reading. Clearly, this approach will require a large number of iBeacons to give a precise location over a large floorplan.

Lots of folks have proposed triangulation-like strategies for using only a few iBeacons. This is much more complex, and there is no pre-built software to do this. While I have read a lot about people wanting or trying to do this, I have not heard any reports of folks pulling it off yet.

If you want to try this yourself, then you should realize that you are undertaking a bit of a science project, and there may be a great deal of time and effort needed to make it happen with unknown results.

Answer 3

Exact location is something that is unlikely to be achievable, but something within some tolerance values is certainly possible. I've not done extensive testing of this yet, but in a small 3x4m area, with three Beacons, you can get good positioning in ideal situations, the problem is that we don't normally have ideal situations!

The hard part is getting an accurate distance from the receiver to the iBeacon, RSSI (the received signal strength) is the only information we have, to turn this into a distance we use a measurement based on known signal strengths at various distances from the transmitter e.g. Qiu, T, Zhou, Y, Xia, F, Jin, N, & Feng, L 2012. This bit works well (and is already implemented with an average accuracy in the iOS SDK), but unfortunately environmental conditions such as humidity and other objects (such as people) getting between the receiver and transmitter degrade the signal unpredictably.

You can read my initial research presentation on SlideShare, which covers some basic environmental effects and shows the effect on the accuracy of measurement, it also references articles that explain how RSSI is turned into distance, and some approaches to overcome the environmental factors. However in a retail situation the top tip, is to position the iBeacons on the ceiling as this reduces the number of Human obstructions.

Trilateration is basically the same whatever you do, I've been using Gema Megantara's version. To improve the positioning further a technique will be needed that takes environmental conditions into account e.g. Hyo-Sung & Wonpil 2009.

Answer 4

The solution is a technique called trilateration. There is a decent wiki article on it.

If you assume that all the beacons and the receiver are on the same plane you can ignore the Z dimension and it simplifies to circles.

The math is still kind of messy. You'd have to do some matrix math on the positions of the beacons to shift one beacon to the origin and put a second beacon on the x axis, and then apply the inverse of your matrix to the result to convert it back to "real" coordinates.

The big problem is that the "accuracy" (aka distance) value is anything but accurate. Even in a wide open space with no interference, the distance signals vary quite a bit. Add any interference (like from your body holding the phone even) and it gets worse. Add walls, furniture, metal surfaces, other people, etc, and it gets really wonky.

I have it on my list of things to do to write trilateration code, measure out a grid in my yard (when the weather warms up), take a tape measure, and do some testing.

Answer 5

The problem with all of this is that the RSSI signal you get back is extremely volatile. If you simply take the raw RSSI you will get very unreliable answers. You need to somehow process the data you get back before you run it through any triangulations, and that means either 1)averaging, or 2)filtering (or both). If you don't, you may get "IMMEDIATE" proximity response even though you are in fringe areas.

Answer 6

Bluetooth Low Energy (4.0) alone is not a robust indoor location and mapping technology, it will most likely become part of the fabric of indoor location technologies, in much the same way wi-fi signals are used to add fidelity to GPS signals in cities. Currently iBeacon can really only be used for fairly nebulous nodes indoors, like 'the shoe department' (assuming a large store)

I expect via the 'iBeacon' service (or something alternatively-named), Apple are working on high-resolution indoor location for app developers. You need look no further than their purchase of WifiSLAM, in mid 2013, for evidence. As yet, iBeacon and any other solely BLE technology is not going to give you precise indoor location. (Perhaps if you blanket the store with beacons, and combine a probabilistic model with a physical model, you could do it, but not with any practically-implementable beacon strategy.)

Also of note, is the discussion around Nokia's next-gen BLE HAIP (High-Accuracy Indoor Positioning) version http://conversations.nokia.com/2012/08/23/new-alliance-helps-you-find-needle-in-a-haystack/

Basically accurate indoor positioning doesn't exist in the wild yet, but it's about to...

Answer 7

We did use gimbal's ibeacons for indoor localization in a 6mx11m area. The RSSI fluctuation was a major issue that we handled through particle filtering. The code for the project can be found at https://github.com/ipapapa/IoT-MicroLocation/. The github repository contains the iOS application as well as a java based apache tomcat server. While we did get an accuracy as high as 0.97 meters, it is still very challenging to use beacons for micro-location purposes.Check the paper http://people.engr.ncsu.edu/ipapapa/Files/globecom2015.pdf which has been accepted for publication in IEEE Globecom conference.

Answer 8

To determine the user's position based on surrounding iBeacons, which have to stay at fixed positions, it is possible by signal strength triangulation. Take a look at this thesis about Bluetooth Indoor Positioning ;-)

Answer 9

Certainly if you can measure the exact position(lat/lon) of any individual iBeacon - that could be included in the beacons message. But assuming a stationary location - obviously this only need to be done once. Sort of an independent "calibration" exercise - which could itself be automated.

Answer 10

I have not done the extensive research that I believe went into Phil's above master's thesis, but...

There is another team that has claimed to have figured this out using various AI algorithms . See this linkedin post: https://www.linkedin.com/groups/6510475/6510475-5866674142035607552

As someone who develops beacons ( http://www.getgelo.com ) I can share first hand that pretty much any object will drastically change the consistency and accuracy of the RSSI which is going to make computing an exact position impossible. (Phil, I hope you prove me wrong, I haven't read your thesis yet).

If are the only person in a wide open space that has a grid of beacons then you can likely get this to work, but as soon as you add other people, walls, objects, etc, then you're SOL.

You can approximate location which is what iBeacons do and are pretty bad at, but it's directionless.

You could deploy enough beacons so that essentially wherever you are in a retail location you're standing very close to a beacon and you can have high confidence that you're in aisle 5 about 20 ft done (as opposed to being on the other side of aisle, aisle 6, and 20 ft down). Cost may become an issue here.

There are teams that are combining BLE with Wifi and other technologies to create a more accurate indoor positioning solution.

In short, and this will come as an echo of what's already been posted, BLE is not a good technology to be used solely for extremely accurate positioning.

Answer 11

When discussing positioning, you need to first define your needs more concretely.

Computer/GPS geeks will assume you want accuracy down to the millimeter, if not finer, so they will either provide you with more information then you need - or tell you it can't be done[both viable answers].

However, in the REAL WORLD, most people are looking for accuracy of at most 3 feet[or 1 meter] - and most likely are willing to accept accuracy of within 10 feet[ie visual distance].

iOS already provides you with that level of accuracy - their api gives you the distance as "near, medium, far" - so within 10 feet all you need to check is that the distance is "near" or "medium".

If your needs go beyond that, then you can provide the custom functionality quite easily. You have 32 bits of information[major and minor codes] That is more then enough information to store the lattitude and longitude of each ibeacon IN the beacon itself using Morton Coding, http://www.spatial.maine.edu/~mark.a.plummer/Morton-GEOG664-Plummer.pdf

As long as altitude[height] is not a factor and no beacon will be deployed within 1 meter of another beacon - you can encode each lat/long pair into a single 32 bit integer and store it in the major and minor code.

Using just the major code, you can determine the location of the beacon[and hence the phone] to within 100 meters[conservatively]. This means that many beacons within the same 100 meter radius will have the SAME major code.

Using the minor code, you can determine the location of the beacon to within 1 meter, and the location of the phone to within 10 feet.

The code for this is already written and widely available - just look for code that demonstrates how it is "impossible" to do this, ignore what the comments about it not being possible since their focused on precision to a greater degree then you care about.

**Note: as mentioned in later posts, external factors will affect signal strength - but again this is likely not relevant for your needs. There are 3 'distances' provided by the iphone sdk, "close, near, far".

Far is the problematic one. Assume a beacon with a 150 foot range. Check with an iphone to determine what the 2 close distances are ideally... assume within 5 feet is "close" and 15 feet is "near".

If phone A is near to Beacon B[which has a known location] then you know the person is within 15 feet of point X. If there is a lot of interference, they may be 3 feet away, or they may be 15 feet, but in either case it is "within 15 feet". That's all you need.

By the same token, if you need to know if they are within 5 feet, then you use the "close" measurement.

I firmly believe that 80% of all positioning needs is provided by the current scheme - where it is not then you do your initial implementation with the limitation as a proof of concept and then contact one of the many ibeacon experts to provide the last bit of accuracy.

Answer 12

The above problem can be solved using technology that combines Wi-Fi trilateration and a phone's sensor data. We get 1 meter accuracy in spaces that are properly outfitted when companies integrate our SDK with their app. The accuracy of these methods has improved dramatically over the last year.