臺灣博碩士論文加值系統

本論文提出一個以無線網路之接收訊號強度來進行室內定位的方法，所提出的方法是以高斯混合模型(Gaussian Mixture Models)來計算出使用者在某個位置的最大機率。首先，我們先將單一無線網路基地台(Access Point, AP)接收大量的訊號強度值加以實驗與分析，利用高斯機率分佈及高斯混合模型來模型化(Modeling)其訊號，以最大相似度(Maximum Likelihood)的方法並用Expectation Maximization(EM)演算法比較其實際接收之訊號與訊號模型之相似度，經由實驗我們得到95﹪以上之相似度。接下來，我們並以上述之方法，利用三維(3D- Gaussian)的高斯機率分佈來實驗與分析出多個APs的狀態。我們所提出的系統有以下兩個狀態：(1) 學習狀態：對於接收訊號強度進行機率分析，以建立機率分佈圖。(2) 估測狀態：根據所在位置之接收訊號強度，估算出使用者之位置並顯示於機率分佈圖中。
實驗證實估算使用者最大可能位置之機率當AP=3，GMM=5，Grid size=50x50 cm2，Training time=500秒時可獲得100﹪正確率的結果。因此我們可以利用實驗來證明，本論文中使用之高斯混合模型的方法其特性優於k-NN與Gaussian兩種。

Location positioning techniques are getting important in mobile computing. A novel approach for the location determination by WLAN signal strength is proposed in this paper. Our method receives the RSSI signal strength from wireless access point. The probability distribution of RSSI is statistically modeled by Gaussian mixture models. The modeling is achieved by expectation maximization. By the assumption of signal independence among access points, the computation of Gaussian mixture in three dimensions is greatly reduced. The signal model and the signal we real received is compared and more than 95% correctness is obtained. User location is determined by maximum likelihood.

中文摘要 i
英文摘要 ii
誌謝 iii
目 錄 iv
圖目錄 vi
第一章 導論 1
1.1 研究動機 1
1.2 研究目的 2
1.3 系統架構 2
1.4 論文架構 6
第二章 文獻探討 8
第三章 機率式位置定位方法 12
第四章 訊號強化與雜訊去除 16
第五章 以高斯機率分佈模型來分析接收訊號強度 20
第六章 以高斯混合模型與EM演算法來分析接收訊號強度 26
6.1背景 26
6.2高斯混合模型（Gaussian Mixture Modeling） 28
6.3 EM 演算法 32
第七章 實驗方法與結果 37
7.1實驗方法 37
7.2以Cell-based之實驗分析 37
7.3以Grid-based實驗分析之環境 41
7.4以Grid-based利用k-NN方法之實驗分析 45
7.5以Grid-based利用GMM方法之實驗分析 51
7.6使用k-NN、Gaussian及GMM方法之效能比較 57
第八章 結論與未來工作 65
8.1 結論 65
8.2 未來工作 66
參考文獻 67
附錄一 利用k個最近鄰居（k-NN）的方法估算位置 70

[1]Young Jae Kim, “Location aware computing,” Computer Science and Engineering Department University of Texas at Arlington.
[2]A. Harter and A. Hopper, “A distributed location system for the active office,” IEEE Network, volume. 8, no. 1, pp.62-70, January/February 1994.
[3]A. Harter, A. Hopper, P. Steggles, A. Ward, and P. Webster, “The anatomy of a context-aware application,” Proc. 5th Annual Int’l Conference on Mobile Computing and Network, pp.59-68, August 1999.
[4]M. Addlesee, R. Curwen, S. Hodges, J. Newman, P. Steggles, A. Ward, and A. Hopper, “Implementing a sentient computing system,” IEEE Computer, volume. 34, no. 8, pp.31-34, August 2001.
[5]Partners, Alumni, “House_n Living Laboratory Introduction,” Department of Architecture research group at the Massachusetts Institute of Technology, [Online]. Available: http://architecture.mit.edu/house_n/.
[6]N. Priyantha, A. Chakraborty, and H. Balakrishnan, “The Cricket location support system,” Proc. of the Sixth Annual ACM International Conference on Mobile Computing and Networking (MOBICOM), pp.32-43, August 2000.
[7]Nissanka B. Priyantha, Allen K. L. Miu, Hari Balakrishnan, and Seth Teller, “The Cricket compass for context aware mobile applications,” ACM Special Interest Group on Mobility of Systems, Users, Data and Computing, pp.1-14, 2001.
[8]L. M. Ni, , Y. Liu, Y. C. Lau, and A. P. Patil, “Landmarc: indoor location sensing using active RFID,” First IEEE International Conference on Pervasive Computing and Communications (PerCom'03) , March 2003.
[9]J. Krumm , S. Harris, B. Brumitt, M. Hale, and S. Shafer. “Multi-camera multi-person tracking for easy living,” Proceedings of 3rd IEEE International Workshop on Visual Surveillance, IEEE Press, Piscataway, NJ, pp.3-10, 2000.
[10]P. Bahl and V. N. Padmanabhan, “Radar: an in-building RF-based user location and tracking system,” In Proceedings of the IEEE Infocom 2000, Tel-Aviv, Israel, volume. 2, pp.776-784, March 2000.
[11]P. Bahl, V. N. Padmanabhan, and A. Balachandran, “Enhancements to the RADAR user location and tracking system,” Microsoft Research Technical Report: MSR-TR-00-12 , February 2000.
[12]Moustafa A. Youssef, Ashok Agrawala, and A. Udaya Shankar, “WLAN location determination via clustering and probability distributions,” IEEE International Conference on Pervasive Computing and Communications (PerCom) 2003, Fort Worth, Texas, March 2003.
[13]Moustafa A. Youssef, Ashok Agrawala, “ Handling samples correlation in the Horus system,” IEEE Infocom 2003, Hong Kong, March 2004.
[14]Moustafa A. Youssef, Ashok Agrawala, A. Udaya Shankar, and Sam H. Noh “A probabilistic clustering-based indoor location determination system,” CS-TR 4350, Department of Computer Science, University of Maryland, College Park, March 2002.
[15]A. Smailagic, J. Small, and D. P. Siewiorek, “Determining user location for context aware computing through the use of a wireless LAN infrastructure,” Technical Report: Project Aura Report, Carnegie Mellon University, December 2000.
[16]G. McLachlan, and T. Krishnan. The EM algorithm and extensions, John Wiley & Sons, New York, 1997.
[17]C. M. Bishop. Neural networks for pattern recognition, Oxford University Press, 1995.
[18]W. Lara, “Universal location framework: a reference implementation, ” Emerging Platforms Lab,Intel Research and Development, November 2002.
[19]N. Deshpande,G. Borriello, “Location-aware computing:creating innovative and profitable applications and services,” Emerging Platforms Lab, Intel Research and Development, August 2002.
[20]J. Krumm,J. Platt, “Minimizing calibration effort for an indoor 802.11 device location measurement system,” Technical Report:MSR-TR-2003-82, Microsoft Research, November 2003.
[21]A. Balachandran, “Wireless research API,” University of California, San Diego. [Online].Available:http://ramp.ucsd.edu/pawn/wrapi/.
[22]Microsoft Corporation (2002), “802.11 wireless LAN objects,” [Online].Available: http://msdn.microsoft.com.
[23]T. Seidl, H. P. Kriegel, “Optimal multi-mtep k-nearest neighbor search,” Proc. ACM SIGMOD, 1998.