Mobile and pervasive computing applications require knowledge of the location of objects or persons in indoor environments in order to provide location-based or context-aware services, which have been receiving particular attention these days. Indoor navigation systems, location-based games, and site-specific services are examples of location-based services. In order to enable such location-based services, we need an indoor localization system. Global Positioning System (GPS) is a representative system covering almost the entire surface of the earth. However, in indoors and in urban canyons, the signal is not received or frequently disconnected. Consequently, many indoor localization technologies have been developed based on infrared, ultrasonic, GSM, pressure sensor, RFID, and Wi-Fi. Among these methods, Wi-Fi-based technologies have drawn special attention because the deployment cost can be drastically reduced by utilizing already existing Wi-Fi network infrastructures. There are two approaches for WLAN-based localization: fingerprinting and trilateration. The fingerprint-based approach is more accurate than trilateration, but it requires building a radio map (or a fingerprint database) for the target building. The performance of the fingerprinting-based location systems heavily depends on the radio map, but the raw radio map built by only human efforts is inaccurate and inefficient. However, recent location-based services require not only accurate indoor locations but also computational efficiency. Thus, optimization techniques have been developed such as interpolation, dimensionality reduction, and clustering to maximize accuracy and efficiency of a given raw radio map.
The work of this dissertation is three-fold. First, we propose a new interpolation technique for generating fin-gerprints to improve location accuracy. The technique estimates AP locations and then refines the model for each cell of the target area tessellated by a higher-order Voronoi diag...