Positioning Method

Hola Mostafa, I will prepare a detailed answer for you but I just wanted to point you to a talk we posted on YouTube that may provide you with some answers. The quality of the video is not great but hopefully you'll get a bit of a better sense of what we are doing: http://www.youtube.com/watch?v=TDZ3l2HsvOQ&feature=PlayList&p=EAE766D5E6252965&index=0

If I haven't posted my detailed answer in a couple of days please bug me again... cheers!

Hello Jorge,
I am just reminding you with my question as you requested.

Here is the summary:

1. Feature extraction:

The fingerprint, which consists of a list of MAC addresses with their corresponding received signal strength (RSS), is stored as it is received from the client device, however, different devices report the RSS in different units. E.g., Macs report a number between ~10 to 100% while Linux clients report the measure in negative dBm. Thus, before the RSS is used, we translate the number into a relative measure from 0 to 1 where 1 is the strongest signal while 0 is for any unseen MAC. Thus, the weakest signal in the fingerprint usually receives a value close to 0, but never 0. For example the following fingerprint:

MAC address 1: -37dBm
MAC address 2: -25dBm
MAC address 3: -80dBm
MAC address 4: -45dBm

Would become:

MAC address 1: a
MAC address 2: 1.0
MAC address 3: b
MAC address 4: c

in our feature space, where 1.0 > a > c > b > 0.0. The specific values of a, b & c depend on your transform, which can be linear, inverse, log, etc... We try linear and inverse and combine the results.

2. Distance measure

In any machine learning algorithm you need a measure of distance. We use euclidian distance on the feature space described above. Thus, for example, the distance between the following two hypothetical fingerprints:

FINGERPRINT 1
MAC address 1: 0.8
MAC address 2: 1.0
MAC address 3: 0.1
MAC address 4: 0.5

FINGERPRINT 2
MAC address 2: 0.4
MAC address 4: 1.0
MAC address 5: 0.1

would be:

MAC address 1: 0.8 - 0.0 = 0.8^2 = 0.64
MAC address 2: 1.0 - 0.4 = 0.6^2 = 0.36
MAC address 3: 0.1 - 0.0 = 0.1^2 = 0.01
MAC address 4: 0.5 - 1.0 = -0.5^2 = 0.25
MAC address 5: 0.0 - 0.1 = -0.1^2 = 0.01
TOTAL = 1.27

This difference, defined in arbitrary units, describes how far in the feature space one fingerprint is from another. Please note that this distance has nothing to do with the real physical space.

2. Calibration or Collection Mode (Training data)

The server can handle an online calibration or collection mode where fingerprints can be added to the database with their relevant location information (e.g., floor id & x/y coordinates). Every new point collected automatically becomes part of the model used online to determine the location (no offline training). To add these points, we use a GUI that can display any floorplan in the database through a drop-down menu. Once the floorplan of the location where we are is displayed, we check a collection mode checkbox and do a double click wherever we are standing on the floorplan. This collects the WiFi fingerprint and x/y coordinates and sends both to the server for storage.

3. Which floor? (Testing)

If you request your position to the server, you need to send the WiFi fingerprint of the location you want to know the position for. Once the server receives your fingerprint it selects a set of calibration fingerprints to work with, however, if none of the calibration fingerprints stored on the server contain any of the MAC addresses you submitted with your fingerprint, the server will return an error because it has no other way to tell where you are. In order to obtain a position estimate, the server has to have at least one calibration fingerprint that contains at least one of the MAC addresses in the fingerprint you submitted.

If a group of calibration fingerprints with at least one of the MAC addresses you submitted is found, this group will be used to determine the floor. All the fingerprints in the group cast a vote to help determine the floor that the submitted fingerprint belongs to. Consider for example the following calibration fingerprints containing at least one of the MAC addresses submitted by a sample client request:

Calibration Fingerprint 1 was taken on floor 4
Calibration Fingerprint 2 was taken on floor 3
Calibration Fingerprint 3 was taken on floor 3
Calibration Fingerprint 4 was taken on floor 3
Calibration Fingerprint 5 was taken on floor 2

The algorithm will then assume that the client's fingerprint comes from floor 3 (for a fairer vote, each fingerprint's vote should be divided the total number of calibration fingerprints available on that floor, otherwise, the floors with the most number of calibration fingerprints will tend to overpower those with fewer)

4. Coordinate Regresion (Testing)

Once the floor has been determined, the server will retrieve all calibration fingerprints available for that floor and use them to determine the position of the submitted fingerprint. Each one of the calibration fingerprints will have an associated x/y coordinate pair. We can arrange all components of the feature space for each fingerprint in a matrix A and the x/y coordinate pairs in a matrix B. Then, we can approximate a regression matrix C that allows us to go from A to B:

AC = B

This regression matrix C is then applied to the submitted fingerprint in order to find the required coordinate. In practice, it is hard to find a C that simultaneously solves the x and y coordinates, so we treat them as independent problems and solve instead:

ACx = Bx
ACy = By

where Bx/By are linear vectors with the x/y coordinates of the calibration fingerprints, and Cx/Cy are the independent regression matrices that will be used to obtain the required coordinate.

Hope this helps!

Thanks Jorge :)

Sorry Jorge , I want to ask can I download the source code of WIPS?

Thanks

yes, definitely... it is all open source and you can license it under a GPL or MIT license. Just be aware that the code is a bit messy and the database only includes data from the University of Toronto.

If you make any changes to the code, please consider contributing them back. This site has a bunch of good tools to facilitate including your potential contributions and if you need help you can always ask another question.

Basic info provided, further details may be explained through additional questions

I closed this question, if you need anything else, feel free to create another question

I forgot to mention: the distance measure is used to weight the floor votes, so closer fingerprints have more influence in the final estimate than those further appart.

Thanks Jorge :)