Application of Half Spaces in Bounding Wireless Internet Signals for use in Indoor Positioning

Abstract

The problem of outdoor positioning has been largely solved via the use of GPS. This thesis addresses the problem of determining position in areas where GPS is unavailable. No clear solution exists for indoor localization and all approximation methods offer unique drawbacks. To mitigate the drawbacks, robust systems combine multiple complementary approaches. In this thesis, fusion of wireless internet access points and inertial sensors was used to allow indoor positioning without the need for prior information regarding surroundings. Implementation of the algorithm involved development of three separate systems. The first system simply combines inertial sensors on the Android Nexus 7 to form a step counter capable of providing marginally accurate initial measurements. Having achieved reliable initial measurements, the second system receives signal strength from nearby wireless internet access points, augmenting the sensor data in order to generate half-planes. The half-planes partition the available space and bound the possible region in which each access point can exist. Lastly, the third system addresses the tendency of the step counter to lose accuracy over time by using the recently established positions of the access points to correct flawed values. The resulting process forms a simple feedback loop. A primary contribution of this thesis is an algorithm for determining access point position. Testing shows that in certain applications access points relatively near the user's path of travel can be positioned with high accuracy. Additionally, the nature of the design means that the geometric algorithm has a tendency to achieve maximum performance in environments containing many twists and turns while suffering from a lack of useful data on straight paths. In contrast, winding areas confound the step counter which performs better when used in long straight stretches of constant movement. When combined, these trends complement one another and result in a robust final product.