臺灣博碩士論文加值系統

本論文旨在改善在跨設備的場景下，以接收訊號強度(Received Signal Strength; RSS)作為量測訊號的Wi-Fi定位和同步定位與地圖建構(Simultaneous Localization and Mapping; SLAM)之精準度。跨設備之Wi-Fi定位面臨的主要挑戰在於每個設備間的RSS量測值有所差異。過往研究多使用一次線性方程式描述此差異。然而，該方程式並不能完整詮釋設備間的差異。因此，本論文提出使用線性回歸之殘差量化一Wi-Fi地圖經由線性跨設備轉換後所新增的不確定性。實驗發現該殘差與跨設備定位之誤差間具高度相關性。本論文因此提出一整合來自不同設備之地圖的方法，依據跨設備回歸殘差調整個別地圖的權重，以改善該組地圖對於任意新設備的定位精度。

由於Wi-Fi地圖之建構過程曠日廢時，過往研究提出Wi-Fi SLAM的方法企圖省去人工標註量測訊號正確位置的步驟。然而由於現有之Wi-Fi SLAM方法需對一非線性最佳化問題求解，其結果成敗取決於起始估測的好壞。由於Wi-Fi RSS不具備角度資訊，而未知角度是SLAM目標函數的一個主要非線性來源，本論文提出使用訊號強度之空間梯度(Signal Strength Gradient; SSG)推估Wi-Fi設備操作者的行走軌跡線段間之角度關係。經由推導與模擬實驗證實，兩相交線段間的角度差可由其SSG間的餘玹相關性近似，藉此即可由Wi-Fi RSS取得角度估測。實驗證實使用該角度估測進行純角度同步定位與地圖建構(Bearings-Only SLAM)可快速取得對整個地圖的精確角度起始估測。

This thesis aims at improving the accuracy and reliability of cross-device Wi-Fi localization and Wi-Fi simultaneous localization and mapping (SLAM) using received signal strength (RSS) measurements. The main challenge in cross-device Wi-Fi localization, where different devices are used during training and testing, is that RSS measurements are device-specific. An extensive body of existing work has been using a linear function to map measurements between devices. However, past research has also found that such linear model is only a crude approximation, as RSS measurements are affected by many complex factors that are difficult to model. Instead of attempting to model each and every one of such factors, a dissimilarity measure is proposed to quantify the differences between devices unexplained by the linear mapping using the regression misfit. Experiments show that the amount of regression misfit is strongly related to cross-device localization performance and as such, the dissimilarity measure is used to weight maps from different devices in cross-device map fusion to improve localization accuracy.

As building any Wi-Fi map involves a labor-intensive training phase to provide location labels for all RSS measurements, Wi-Fi SLAM has been proposed in the literature to automate the process. However, existing Wi-Fi SLAM approaches involves optimizing a nonlinear cost function, which requires good initialization to approach a globally optimal solution. Finding a good solution is made more difficult because Wi-Fi RSS measurements does not provide orientation information, which is a major source of nonlinearity in SLAM problems. The thesis thus proposes an orientation constraint for Wi-Fi SLAM using the signal strength gradient (SSG) over trajectory segments. The cosine similarity between the SSGs over a pair of nearby segments is shown to approximate their relative orientations. This finding is used to create orientation constraints between near-parallel trajectory segments, transforming Wi-Fi SLAM into a bearing-only SLAM problem. Experiments show that the approach provides a fast and accurate orientation initialization for Wi-Fi SLAM. As SSGs are invariant to linear transforms in RSS space, the orientation constraints could also be used for cross-device Wi-Fi SLAM.

ACKNOWLEDGEMENTS ii
摘要 iii
ABSTRACT iv
List of Figures vii
List of Tables viii
Chapter 1. Introduction 1
Chapter 2. Current Approaches of Indoor Localization and Mapping 3
2.1. Positioning Techniques 3
2.2. Positioning Sensors 4
2.3. Wi-Fi as a Positioning Sensor 4
Chapter 3. Cross-Device Wi-Fi Map Fusion with Gaussian Processes 6
3.1. Introduction 6
3.2. Related Work 7
3.3. Background 10
3.3.1. Wi-Fi Localization Using Gaussian Processes 10
3.3.2. The Regression Misfit in Cross-Device Localization 11
3.4. Using the Regression Misfit in Cross-Device Map Fusion 14
3.5. Linear Regression for Sparse Training Sets Using GP-WTLS 17
3.5.1. Linear Adaptation of GP Hyperparameters 18
3.5.2. Generating Pseudo-Samples Using GPs 19
3.5.3. Linear Regression with Pseudo-Samples 20
3.6. Experimental Results 21
3.6.1. Experiment Setup 22
3.6.2. Effect of Regression Misfit on Discrete Multi-Orientation Training Sets 23
3.6.3. Comparison of Linear Fitting Algorithms 25
3.6.4. Comparison of Map Fusion Algorithms 25
3.6.5. Unsupervised Adaptation And Map Fusion 31
3.7. Discussion 32
3.8. Summary 35
Chapter 4. Orientation Constraints for Wi-Fi SLAM using Signal Strength Gradients 37
4.1. Introduction 37
4.2. Related Work 38
4.2.1. Wi-Fi SLAM using RSS Measurements 38
4.2.2. Pose Graph SLAM using Orientation Constraints 40
4.2.3. Robust Pose Graph SLAM 40
4.3. SSG Orientation Constraint 41
4.3.1. Estimating Orientation from SSGs 41
4.3.2. Trajectory Segmentation and SSG Estimation 43
4.3.3. Generating Orientation Constraints for Wi-Fi SLAM 46
4.3.4. Outlier Rejection of Orientation Constraints 47
4.4. Experimental Results 48
4.4.1. Approximation of Segment Orientation using Cosine Similarity 48
4.4.2. Bearing-Only Wi-Fi SLAM Performance 49
4.5. Summary 54
Chapter 5. Conclusions and Future Work 55
Bibliography 57

Agarwal, P., Tipaldi, G. D., Spinello, L., Stachniss, C., & Burgard, W. (2013). Robust map optimization using dynamic covariance scaling. In IEEE International Conference on Robotics and Automation (ICRA), (pp. 62–69).
Bahl, P. & Padmanabhan, V. N. (2000). Radar: An in-building rf-based user location and tracking system. In IEEE International Conference on Computer Communications (INFOCOM), (pp. 775–784).
Bishop, C. M. (2006). Pattern Recognition and Machine Learning (Information Science and Statistics), chapter 3.1. Secaucus, NJ, USA: Springer-Verlag New York, Inc.
Bonilla, E. V., Ming, K., Chai, A., & Williams, C. K. I. (2008). Multi-task gaussian process prediction. Advances in Neural Information Processing Systems (NIPS), 20, 153–160.
Brena, R. F., Garc´ıa-Vazquez, J., Galv ´ an-Tejada, C. E., Rodr ´ ´ıguez, D. M., Rosales, C. V., & Jr., J. F. (2017). Evolution of indoor positioning technologies: A survey. Journal of Sensors, 2017, 2630413:1–2630413:21.
Carlone, L., Aragues, R., Castellanos, J. A., & Bona, B. (2014). A fast and accurate approximation for planar pose graph optimization. International Journal of Robotics Research, 33(7), 965–987.
Chen, C., Chen, Y., Han, Y., Lai, H., Zhang, F., & Liu, K. J. R. (2017). Achieving centimeteraccuracy indoor localization on wifi platforms: A multi-antenna approach. IEEE Internet of Things Journal, 4(1), 122–134.
Chen, L.-H., Wu, E.-K., Jin, M.-H., & Chen, G.-H. (2014). Homogeneous features utilization to address the device heterogeneity problem in fingerprint localization. IEEE Sensors Journal, 14(4), 998–1005.
Cheng, H., y. Luo, H., & Zhao, F. (2012). Device-clustering algorithm in crowdsourcingbased localization. Journal of China Universities of Posts and Telecommunications, 19, 114–121.
Cheng, Y.-C., Chawathe, Y., LaMarca, A., & Krumm, J. (2005). Accuracy characterization for metropolitan-scale wi-fi localization. In International Conference on Mobile Systems, Applications, and Services (MobiSys), (pp. 233–245)., New York, NY, USA.
Deyle, T., Kemp, C. C., & Reynolds, M. S. (2008). Probabilistic UHF RFID tag pose estimation with multiple antennas and a multipath RF propagation model. In IEEE/RSJ
International Conference on Intelligent Robots and Systems (IROS), (pp. 1379–1384).
Dong, F., Chen, Y., Liu, J., Ning, Q., & Piao, S. (2009). A calibration-free localization solution for handling signal strength variance. In International Workshop on Mobile Entity Localization and Tracking in GPS-less Environnments (MELT), volume 5801, (pp. 79–90).
Fearnhead, P. (2005). Exact bayesian curve fitting and signal segmentation. IEEE Transactions on Signal Processing, 53(6), 2160–2166.
Fearnhead, P. & Liu, Z. (2007). On-line inference for multiple changepoint problems. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 69(4), 589–605.
Ferris, B., Fox, D., & Lawrence, N. (2007). Wifi-slam using gaussian process latent variable models. In International Joint Conference on Artificial Intelligence (IJCAI), (pp. 2480–2485).
Ferris, B., Hahnel, D., & Fox, D. (2006). Gaussian processes for signal strength-based location estimation. In Robotics: Science and Systems (RSS).
Figuera, C., Rojo-Alvarez, J. L., Mora-Jim ´ enez, I., Guerrero-Curieses, A., Wilby, M. R., & Ramos-Lopez, J. (2011). Time-space sampling and mobile device calibration for wifi indoor location systems. IEEE Transactions on Mobile Computing, 10(7), 913–926.
Gjengset, J., Xiong, J., McPhillips, G., & Jamieson, K. (2014). Phaser: enabling phased array signal processing on commodity wifi access points. In International Conference on Mobile Computing and Networking (MobiCom), (pp. 153–164).
Gutmann, J., Eade, E., Fong, P., & Munich, M. E. (2012). Vector field SLAM - localization by learning the spatial variation of continuous signals. IEEE Transactions on Robotics, 28(3), 650–667.
Haeberlen, A., Flannery, E., Ladd, A. M., Rudys, A., Wallach, D. S., & Kavraki, L. E. (2004).
Practical robust localization over large-scale 802.11 wireless networks. In International Conference on Mobile Computing and Networking (MobiCom).
Halperin, D., Hu, W., Sheth, A., & Wetherall, D. (2011). Tool release: Gathering 802.11n traces with channel state information. SIGCOMM Computer Communication Review, 41(1),
53–53.
He, S. & Chan, S. G. (2016). Wi-fi fingerprint-based indoor positioning: Recent advances and comparisons. IEEE Communications Surveys and Tutorials, 18(1), 466–490.
Herranz, F., Llamazares, A., Molinos, E. J., Ocana, M., & Sotelo, M. ˜ A. (2016). Wifi SLAM algorithms: an experimental comparison. Robotica, 34(4), 837–858.
Huang, J., Millman, D., Quigley, M., Stavens, D., Thrun, S., & Aggarwal, A. (2011). Efficient, generalized indoor wifi graphslam. In IEEE International Conference on Robotics and Automation (ICRA), (pp. 1038–1043).
Jiang, J., Lin, C., Lin, F., & Huang, S. (2013). ALRD: aoa localization with RSSI differences of directional antennas for wireless sensor networks. International Journal of Distributed Sensor Networks (IJDSN), 9.
Jiang, Y., Pan, X., Lv, K. L. Q., Dick, R. P., & Shang, M. H. L. (2012). Ariel: Automatic wi-fi based room fingerprinting for indoor localization. In ACM International Joint Conference on Pervasive and Ubiquitous Computing (UbiComp).
Kjargaard, M. B. & Munk, C. V. (2008). Hyperbolic location fingerprinting: A calibrationfree solution for handling differences in signal strength (concise contribution). In IEEE International Conference on Pervasive Computing and Communications (PerCom), (pp. 110–116).
Kotaru, M., Joshi, K. R., Bharadia, D., & Katti, S. (2015). Spotfi: Decimeter level localization using wifi. SIGCOMM Computer Communication Review, 45(5), 269–282.
Krystek, M. & Anton, M. (2007). A weighted total least-squares algorithm for fitting a straight line. Measurement Science and Technology, 18(11), 3438.
Kummerle, R., Grisetti, G., Strasdat, H., Konolige, K., & Burgard, W. (2011). G ¨ 2o: A general framework for graph optimization. In IEEE International Conference on Robotics and Automation (ICRA), (pp. 3607–3613).
Kummerle, R., Steder, B., Dornhege, C., Ruhnke, M., Grisetti, G., Stachniss, C., & Kleiner, ¨A. (2009). On measuring the accuracy of SLAM algorithms. Autonomous Robots, 27(4), 387–407.
Laoudias, C., Piche, R., & Panayiotou, C. G. (2013). Device self-calibration in location systems using signal strength histograms. Journal of Location Based Services, 7(3), 165–181.
Laoudias, C., Zeinalipour-Yazti, D., & Panayiotou, C. G. (2013). Crowdsourced indoor localization for diverse devices through radiomap fusion. In International Conference on Indoor Positioning and Indoor Navigation (IPIN).
Latif, Y., Lerma, C. D. C., & Neira, J. (2013). Robust loop closing over time for pose graph SLAM. International Journal of Robotics Research, 32(14), 1611–1626.
Lee, M., Jung, S. H., Lee, S., & Han, D. (2012). Elekspot: A platform for urban place recognition via crowdsourcing. In IEEE/IPSJ International Symposium on Applications and the Internet (SAINT), (pp. 190–195).
Lee, S., Jung, S., & Han, D. (2012). Uncaught signal imputation for accuracy enhancement of wlan-based positioning systems. In ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems, (pp. 80–85)., New York, NY, USA.
Lin, T.-H., Ng, I.-H., Lau, S.-Y., Chen, K.-M., & Huang, P. (2008). A microscopic examination of an rssi-signature-based indoor localization system. In Workshop on Embedded Networked Sensors (HotEmNets).
Lu, F. & Milios, E. E. (1997). Globally consistent range scan alignment for environment mapping. Autonomous Robots, 4(4), 333–349.
Machaj, J., Brida, P., & Piche, R. (2011). Rank based fingerprinting algorithm for indoor positioning. In International Conference on Indoor Positioning and Indoor Navigation (IPIN), (pp. 1–6).
Mahtab Hossain, A., Jin, Y., Soh, W.-S., & Van, H. N. (2013). Ssd: A robust rf location fingerprint addressing mobile devices’ heterogeneity. IEEE Transactions on Mobile Computing, 12(1), 65–77.
Menegatti, E., Zanella, A., Zilli, S., Zorzi, F., & Pagello, E. (2009). Range-only SLAM with a mobile robot and a wireless sensor networks. In IEEE International Conference on Robotics and Automation (ICRA), (pp. 8–14).
Miyagusuku, R., Yamashita, A., & Asama, H. (2016). Improving gaussian processes based mapping of wireless signals using path loss models. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), (pp. 4610–4615).
Niehsen, W. (2002). Information fusion based on fast covariance intersection filtering. In International Conference on Information Fusion.
Olson, E. & Agarwal, P. (2013). Inference on networks of mixtures for robust robot mapping. International Journal of Robotics Research, 32(7), 826–840.
Olson, E., Leonard, J. J., & Teller, S. J. (2006). Fast iterative alignment of pose graphs with poor initial estimates. In IEEE International Conference on Robotics and Automation (ICRA), (pp. 2262–2269).
Pan, J. J., Pan, S. J., Yin, J., Ni, L. M., & Yang, Q. (2012). Tracking mobile users in wireless networks via semi-supervised colocalization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(3), 587–600.
Park, J.-g., Curtis, D., Teller, S. J., & Ledlie, J. (2011). Implications of device diversity for organic localization. In IEEE International Conference on Computer Communications (INFOCOM), (pp. 3182–3190).
Pfingsthorn, M. & Birk, A. (2016). Generalized graph SLAM: solving local and global ambiguities through multimodal and hyperedge constraints. International Journal of Robotics
Research, 35(6), 601–630.
Rasmussen, C. E. & Nickisch, H. (2010). Gaussian processes for machine learning (gpml) toolbox. Journal of Machine Learning Research, 11, 3011–3015.
Ridley, M., Upcroft, B., Ong, L.-L., Kumar, S., & Sukkarieh, S. (2004). Decentralised data fusion with parzen density estimates. In Intelligent Sensors, Sensor Networks and Information Processing Conference, (pp. 161–166).
Rosa, F., Xu, L., Nurmi, J., Pelosi, M., Laoudias, C., & Terrezza, A. (2011). Hand-grip and body-loss impact on rss measurements for localization of mass market devices. In
International Conference on Localization and GNSS (ICL-GNSS), (pp. 58–63).
Schssel, M. (2016). Angle of arrival estimation using wifi and smartphones. In International Conference on Indoor Positioning and Indoor Navigation (IPIN).
Schwaighofer, A., Grigoras, M., Tresp, V., & Hoffmann, C. (2004). GPPS: A gaussian process positioning system for cellular networks. Advances in Neural Information Processing Systems (NIPS), 16, 579–586.
Seco, F., Plagemann, C., Jimenez, A., & Burgard, W. (2010). Improving rfid-based indoor positioning accuracy using gaussian processes. In International Conference on Indoor Navigation and Indoor Positioning (IPIN).
Sunderhauf, N. & Protzel, P. (2012). Towards a robust back-end for pose graph SLAM. In IEEE International Conference on Robotics and Automation (ICRA), (pp. 1254–1261).
Tao, P., Rudys, A., Ladd, A. M., & Wallach, D. S. (2003). Wireless lan location-sensing for security applications. In ACM Workshop on Wireless Security, (pp. 11–20)., New York, NY, USA.
Tsui, A. W., Chuang, Y.-H., & Chu, H.-H. (2009). Unsupervised learning for solving rss hardware variance problem in wifi localization. Mobile Networks and Applications, 14(5), 677–691.
Tzur, A., Amrani, O., & Wool, A. (2015). Direction finding of rogue wi-fi access points using an off-the-shelf MIMO-OFDM receiver. Physical Communication, 17, 149–164.
Wu, Z., hung Li, C., Ng, J. K.-Y., & Leung, K. R. P. H. (2007). Location estimation via support vector regression. IEEE Transactions on Mobile Computing, 6(3), 311–321.
Xiong, H. & Tao, D. (2017). A diversified generative latent variable model for wifi-slam. In AAAI Conference on Artificial Intelligence, (pp. 3841–3847).
Xiong, J. & Jamieson, K. (2013). Arraytrack: A fine-grained indoor location system. In USENIX Symposium on Networked Systems Design and Implementation (NSDI), (pp. 71–84).
Yang, S., Dessai, P., Verma, M., & Gerla, M. (2013). Freeloc: Calibration-free crowdsourced indoor localization. In IEEE International Conference on Computer Communications (INFOCOM).
Zheng, V. W., Pan, S. J., Yang, Q., & Pan, J. J. (2008). Transferring multi-device localization models using latent multi-task learning. In AAAI Conference on Artificial Intelligence, (pp. 1427–1432).