Wireless Positioning System

WPS was an academic research project of mine and two colleagues at Technical University of Gdańsk (Politechnika Gdańska). Its lifespan lasted couple semesters on different courses.

Goal

Assess the feasibility of a wireless fidelity based indoor positioning system. The system should take advantage of preexisting infrastructure and achieve maximal possible accuracy and reliability. Part of the project is implementing a working solution for a HP iPaq PDA.

Authors

Three second (third in the second half of the project) year students of computer science:

Professor supervising the project was Tomasz Dziubich.

Other works and literature

Some others works on similar matter we’ve found include:

Why not triangulation

Most other works concentrate on translating readouts into distances form access points and then calculating the position using simple triangulation. It was the best method (in fact based on distance) to use in GPS and similar projects. But for indoors it simply doesn’t work like that. The most important difference are walls - they both suppress the signal and reverberate it, creating complicated multipath. Furthermore signal propagation is disturbed by all kinds of objects, electronics, furniture and even peoples bodies. All that is combined with relatively high level of background noise. Triangulation is possible in those circumstances but it requires fairly great dose of additional information and great amounts of complicated computations to work with acceptable reliability.

The location algorithm

To acquire best results no information about static objects should be disregarded. We cannot assume that all objects in the field are immovable, but there is no way to take all the possible landscape changes into consideration - they set an upper limit on the accuracy. It also feels clear, that all the available data should be considered as a whole, as many of the elements are correlated. On the other hand, we must consider the case of malfunctioning or removed hardware (with signal much below the normal levels, or absent at all).
Therefore we use an observation history matcher algorithm. First, we impose a set of location points on the area map. Then some signal history in each of those points is collected. When localizing, current readout is confronted against each of those points, with a similarity value as the result. The points are then checked against current observation history and the most probable location is chosen.

The implementation

We have experimented on an implementation for the HP iPaq PDA. It’s WiFi card seems to have medium accuracy - it’s the mid level hardware you would expect the end user to have. Furthermore it doesn’t measure any additional values like SNR, so our initial decision of using only RSSI was strongly reinforced. The program itself is written in C# language using the Compact Framework and OpenNETCF API for accessing the readouts. There are two executables, one for imposing location points on the map and gathering measurements, the second for dipslaying the guessed position. All the data is stored in a single file, which due to CF limitations could only be a XML serialization of the database structure.

Achieved results

Passing the courses with a good grade, of course ;)

Achieved accuracy is decided at the time of gathering data - it’s simply the mean distance between neighboring location points. As intuition says, the better the accuracy, the worse the reliability. We have achieved accuracy similar to that claimed by other works, with reasonable reliability, in environment containing far less APs. Still it was order of magnitude worse than what was needed by the professor. He switched in his projects from WiFi to RFID based solutions.