5 minutes

How To Determine Location If You have A Roof Over Your Head

Indoor Location

Currently, there are many examples and ready-made solutions for outdoor positioning, but how does an app determine your exact position indoors? For example, an indoor positioning system inside a hospital can help patients find the right wing or navigate to the next procedure. Not to mention such modern mazes as airports, supermarkets, amusement parks, etc. Also, different interactive game apps are getting increasingly popular.

Presented by Apple at WWDC 2014, the technology of indoor location aroused great interest. However, it was just a video presentation without a more detailed description of the equipment or at least some demo code. So we suggest looking closer at indoor positioning technologies and challenges behind them.

Indoor location tracking via iBeacon

Indoor positioning has been given a significant push with new BLET 4.0 technologies, namely iBeacon. In general, iBeacon technology allows us to monitor and evaluate the distance between a Bluetooth-enabled cell phone/mobile device and iBeacon tags. More specifically, for tags identification 3 values are used: UDID, a major value and a minor value. Distance is then roughly estimated for each tag: very close, close, far (like in the hot&cold kids’ game) and get rssi. Using these tags, the technology e can "roughly" estimate user's location in the area of this label.

What if we need to get a more accurate position? Can the exact value of the distance to the mark be determined using rssi? Turns out, if you find the exact distance to the three labels and know their coordinates, the exact location can be calculated. Theoretically, you can calculate the distance using rssi:

Where n is signal propagation constant or exponent, d is the distance from sender and A is the received signal strength at 1 meter distance.

But in practice, there are many problems with measuring rssi value, as we’ve discovered by way of trial and error. This value may be significantly affected by physical barriers like low frequency barrier or a humid environment. Our investigations have proven such resulting deviations can be twice or three times the distance value. A possible solution to account for the environmental parameters is to make measurement calibrations and to eliminate rssi fluctuations using all sorts of filtering.

Kalman filtering

We used Kalman filter for rssi filtration. The Kalman filter uses a dynamic model of the system (law of motion) and a large number of consecutive measurements to create the optimal estimation of the state. The filter algorithm consists of two phases that occur repeatedly: prediction and correction. The first phase is the calculation of a predicted state in the next moment. At the second phase, this prediction is corrected using the measurements values.

All equations are provided in a matrix form, but in the case of one variable the matrix degenerates into scalar values.

So in our case, the algorithm is reduced to this form

Here the index k denotes the actual value and the index k-1 previous.

To apply a filter, you have to specify the variables that determines the dynamics of the system and measurements of F, B and H:

F- a variable that describes the dynamics of the system
B- a variable that describes the external force on the system
H- a matrix that describes the connection between measurements and system status.

And more options:

R- measurement error
Q- noise process (process variance)

Code implementation:

Show code

	#import 

@interface PYKalmanFilter : NSObject

// factor of real value to previous real value
@property (nonatomic) CGFloat f;

// measurement noise
@property (nonatomic) CGFloat q;

// factor of measured value to real value
@property (nonatomic) CGFloat h;

// environment noise
@property (nonatomic) CGFloat r;

// current state
@property (nonatomic) CGFloat currentState;


//initial
-(PYKalmanFilter *)initKlamanFilterWithF:(CGFloat)f withQ:(CGFloat)q withH:(CGFloat)h withR:(CGFloat)r;

-(void)setStartState:(CGFloat)state withCovariance:(CGFloat)covariance;

//data update
-(void)correctWithData:(CGFloat)data;

@end


#import "PYKalmanFilter.h"

@interface PYKalmanFilter()

// predicted state
@property (nonatomic) CGFloat x0;

// predicted covariance
@property (nonatomic) CGFloat p0;

// current covariance
@property (nonatomic) CGFloat covariance;

@end


@implementation PYKalmanFilter

-(PYKalmanFilter *)initKlamanFilterWithF:(CGFloat)f withQ:(CGFloat)q withH:(CGFloat)h withR:(CGFloat)r
{
    self = [super init];
    
    if (self) {
        self.f = f;
        self.q = q;
        self.h = h;
        self.r = r;
    }
    return self;
}

-(void)setStartState:(CGFloat)state withCovariance:(CGFloat)covariance
{
    self.currentState = state;
    self.covariance = covariance;
}

-(void)correctWithData:(CGFloat)data
{
    //prediction equations
    self.x0 = self.f*self.currentState;
    self.p0 = self.f*self.covariance*self.f + self.q;
    
    //update equations (measurements)
    CGFloat k = self.h*self.p0/(self.h*self.p0*self.h + self.r);
    self.currentState = self.x0 + k*(data - self.h*self.x0);
    self.covariance = (1 - k*self.h)*self.p0;
    NSLog(@"");
}
@end

Even after calibration and determining of the additional filtering options, the filtering results were not satisfactory. Deviations from the actual distance value were within the range of 0.5-1.5 m. Such large error is primarily the result of the fact that the Kalman algorithm uses a system with a given equation of motion but we are dealing with chaotic motion. Secondly, this is due to complexity of calibration and system settings.

To put it in a nutshell...

We’ve made a thorough investigation of how the iBeacon technology can be used for indoor positioning in trilateration. As it turns out, iBeacon tags’ aspirations to become the next best thing for outdoor positioning remains just that: aspirations. iBeacons alone cannot determine the exact indoor location due to environmental factors (everything from signal interference to humidity levels).

As much as we wanted it to work, the precision of iBeacon tags could not be improved with any filtering. The Kalman filter we applied offers a perfect filtration system tool, but for unchaotic motion only.

Today, this technology can be used for coarse positioning or as an auxiliary parameter to calculate displacements and location using GPS. We are still keeping our eyes peeled for other technologies.

And what did you expect of iBeacons? Can indoor positioning technologies help you solve specific problems in your industry, leveraring our mobile app development services? Please comment below.