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.
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.
Three second (third in the second half of the project) year students of computer science:
- Adam Bar
- Michał Nowakowski
- Remigiusz Modrzejewski
Professor supervising the project was Tomasz Dziubich.
Other works and literature
Some others works on similar matter we’ve found include:
- Two New Algorithms for Indoor Wireless Positioning System by Xiaodong Jia, Yufei Wang and Chris Rizos
- A Novel Positioning System for Static Location Estimation Employing WLAN Indoor Enviroment by Reetu Singh, Matteo Gandetto, Marco Guainazzo, Daniele Angiati and Carlo S. Ragazzoni
- An indoors wireless positioning system based on wireless local area network infrastructure by Y. Wang, X. Jia and H.K. Lee
- Several more found on the Satellite Navigation and Positioning Lab website
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.
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.
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.