Selective AP Probing for Indoor Positioning in a Large and AP-Dense Environment

Abstract

As massive number of mobile devices have been widely distributed, importance of Location-based service (LBS) has been increasing for decades. Locating a target on a map, Automotive navigation, location-based social networking, augmented reality (AR), virtual reality (VR), location-aware advertising and promotion, assistive healthcare service are examples of LBSs. Therefore, locating a person or an object is crucial to provide a LBS. Global Navigation Satellite System (GNSS), widely known as Global Positioning System (GPS) can be used outdoors to locate and track a location of a target. On the other hand, GNSS cannot be used to locate a target indoors due to severe signal attenuation, reflection and refraction due to complex structure of a building. In order to locate a target which resides in an indoor site, indoor positioning techniques have been studied and proposed using alternative wireless communication technologies. Thanks to the low cost and power consumption, wide communication range, and high data rate, Wi-Fi is one of the most widely used wireless communication technologies. Among various positioning techniques and methods, a received signal strength (RSS) fingerprint-based scene analysis has been used frequently due to its practicality. Wi-Fi RSS fingerprint-based indoor positioning system collects RSS values from APs, compose a fingerprint, a vector of AP-RSS pairs, and store it into a database, a radiomap with its corresponding coordinates in the offine phase. And it estimates a target's location by comparing a fingerprint composed in the online phase with those in the radiomap. To measure an RSS, a client broadcasts a probe request frame (PRRQ) and nearby APs listening to it responds with probe response frames (PRRPs) according to the probing procedure defined in the IEEE 802.11 standard. The client measures a signal strength of a received PRRP and composes a fingerprint. In this dissertation, we show that the standard probing procedure causes severe contention between Wi-Fi devices with actual data consisting of 1,734 AP. This leads to saturation on the wireless channel and missing RSS values in a fingerprint, and thus degradation of positioning accuracy. We name such a phenomenon a missing AP. This is because the medium access protocol of IEEE 802.11, carrier sense multiple access with collision avoidance (CSMA/CA) is a probabilistic approach to avoid collision. Such approach effectively coordinates medium access of each device when there exist a moderate number of devices. However, as the number of devices increases, probability of devices attempting frame transmission at the same time increases and CSMA/CA will not be effective. This dissertation proposes Selective AP Probing (SelAP) scheme, which reduces the contention by selectively probing APs via unicast and thus solves the missing access point (AP) problem and also presents criteria to select such target APs to be probed. Through the performance evaluation, it is shown that the proposed scheme reduces the positioning error by up to 55 percent. Furthermore, we show that only a small number of APs contribute a positive effect to positioning accuracy and the others does a negative effect. In addition, SelAP reduces control and management traffic for indoor positioning and thus avoids the throughput degradation problem during the probing stage.