How we calculate a position

IndoorWPSLib tries to provide easy to costumize and extend classes. The location-calculating Algorithm can be spilt into three phases, which can easily be replaced or costumized.

When trying to determine the useres current position, the algorithm has several inputs:
  1. The current measurement(Accesspoints with their signalstrenght), which is provided by the
  2. A List of Calibration-Points, also known as Fingerprints.

A a first step, the algorithm tries to eliminate all irrelevant Fingerprints. It does so by calling the FingerprintLoaders getSimalarFingerprints(). This step could be costumized by implementing your own FingerprintLoader, although this step isn't where the calculation takes place. The getSimalarFingerprints method should only filter the fingerprints very little, it is just a memory saving procedure. In the location calculating algorithm, it is not good to work with hundreds of possible Fingerprints

As a second Step, the algorithm calculates a correlation for each Fingerprint of the possible ones. It does that by calling the correlators correlation(current readingss, calibration readings) method. The Correlator can be changed to adjust to the calculating-method you want. Currently, there are a few Correlators implemented, for more information on each of them, see Correlatos. The lower the correlation is, the nearer the current measurement is to the specified Fingerprint. But keep in mind that the correlation is not equal to the distance, altought one might implement a Correlator providing that fnctionality.

As a last step, the calculateLocation of the locationCalculator is called with the list of the Fingerprints, each providing a correlation value to the current measurement. The LocationCalculator is responsible for calculating a location based on several Fingerprints. The easiest way is to return the Location of the fingerprint with the lowest correlation, whereas more advanced implementations might try to average between the given Fingerprints, weighing their relevance according to the correlation. There are several already implemented LocationCalculators availible, see LocationCalculators for more information on that.

This UML-Sequence Diagram should graphically summarize how a location is calculated.

Correlators

Let's start with an UML-Class diagram of the availible Correlators.

As you can see, every LocationCalculator must implement the Correlator<Fingerprint> interface.
Let's see what each of these LocationCalculators do:
  • FingerprintNullCorrelator
    The simplest Correlator, always returns 0.
  • DistanceOrdererFingerprintCorrelator
    Determmines the correlations according to the difference of the signals and taking in account that stronger signals are better than weak ones. This is at the moment the Correlator which yields the best result, but it's also hard to understand how it exactly works. To simplify things, we tried to seperate each action and created a Decorator-Pattern based solution, where the user can create his own calculating algorithm, just by stacking different parts of functionality. It's a bit like playing with Lego.
  • OverlappingOrderedFingerprintCorrelator
    Another rather old and complex Correlator.
  • AbstractCorrelator
    This class provides some common functionality which is used in the concrete super-classes.
  • AveragingDifferenceCorrelator
    This correlator calculates the average of the signal differences.
  • PenaltyAddingCorrelator
    This correlator tries to take into account that not every Accesspoint is always visible. It adds a penalty to the correlation, calculated by the targetCorrelator, which makes the correlation bigger if an accesspoint is not visible.
  • MacEqualsCountWeighedCorrelator
    This correlator devides the correlation calculated by the targetCorrelator by the count of common accesspoints of the calibrationpoint and the measurement. The idea behind this is that Fingerprints with more common accesspoints should be better than Fingerprints with less.

Here is an example of how you could combine those Correlators.

correlator = new PenaltyAddingCorrelator(new MacEqualsCountWeightedCorrelator(new AveragingDifferenceSumCorrelator()));

This will create a Correlator which calculates the average of the signal-differences, devides them by the count of common accesspoints and, as a last step, adds penalties for the accesspoints that are not present in both reasings(the calibration reading and the current reading)

LocationCalculators

This is an overview of the implemented LocationCalculators:

  • NearestLocationCalculator
    This LocationCalculator just finds the Fingerprint with the smallest correlation and returns that.
  • MaximalFingerprintLocationCalculator
    This locationCalculator works as a filter, it redirects to a targetCalculator, but only with the best n Fingerprints. Usage of such a filter can increase the performance and accuracy of the targetCalcultor.
  • WeighBasedLocationCalculator
    This Algorithm calculates the average position, wheiged by theis relative correlations.
  • HistoryAwareLocationCalculator
    This abstract class provides the functionality of keeping track of the last calculated positions. superclasses may use this information. The real calculation of the current Location is delegated to the targetCalculator.
  • AverageLocationCalculator
    calculates the average position of the last n calculated positions. Can be used to smooth the result and avoid jumping.
  • MedianLocationCalculator
    Simalar to AverageLocationCalculator, but this one calculates the median, which means that if for an unknown reason a high jump in location occures from time to time but mostly its about the same location, the resulting location won't be influenced by these jumping values as they would be in an averaging approach.

None of these Calculators or Correlators is the best solution, which is appropriate for a situation depends on the environement. But they can be mixed to provide together a good result.

This is an exaple of how you could mix these LocationCalculators:

LocationCalculator l = new AverageLocationCalculator(
                new MaximalFingerprintLocationCalculator(
                        new WeightBasedLocationCalculator(), 5));

This is creating a locator which works with the WeightBasedLocationCalculator but only considers the 5 best Fingerprints, wraped in a average-based result smoother.

LocationCalculators_class_diagram.jpg (80.1 KB) Anonymous, 01/19/2011 09:36 AM

sequence_diagram_location_calculation.jpg (35.3 KB) Anonymous, 01/19/2011 09:36 AM

correlator_class_diagram.jpg (79.4 KB) Anonymous, 01/19/2011 09:36 AM