臺灣博碩士論文加值系統

雖然現在利用訊號強度所做的室內定位系統，其準確度約為兩米左右，但是直接將絕對座標轉換成房間資訊，卻常常造成錯誤。而從事室內定位的專家普遍都有一個共識，就是室內定位系統的準確度必須至少達到房間程度。

本研究結合空間限制的模型Lock Maker與機率模型particle filter，來提昇定位系統在提供房間定位的準確度。藉由particle在不同區域間的分佈情形來更新、給予移動時的空間限制；另外也利用長時間對感測器模型的觀察，協助判斷被追蹤的人是否進入房間，來輔助更新空間限制並適時導引particle移動。

實驗結果顯示，我們所提出的方法在提供房間定位上確實比Walking Area、Collision Detection的方法要值得信賴。雖然會造成2秒左右的進房延遲，但我們覺得這延遲仍在容忍的範圍內，且當定位訊號較穩定時，延遲的情形也可以儘可能的降低。

We discover that it is easy to provide incorrect room-level information which is transformed from the absolute position, although the accuracy of the current RSSI location system is about two meters. Indoor localization researchers have a consensus that systems at least need to provide room-level accuracy. Thus, we propose a spatial constraint model, called Lock Maker and combine it into particle filter to provide better room-level location estimation. In Lock Maker, Space Model constructs the map organization by recording the connection between different regions. Then, Spatial Constraint gives limitations to particles while they
are moving. At the same time, we update limitations by observing the weight of particles distribute over different areas. Region-level Sensor Model uses a longer duration of location information to help change limitations in Spatial Constraints and guide particles to a more suitable position than current.

In our experiments, we compare Lock Maker with Walking Area approach, and Collision Detection Algorithm. The result shows that Lock Maker is more reliable to provide room-level information. Although this approach causes some delay, but we think that the delay is still tolerable to users.

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xi
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv
Chapter 1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Research Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
Chapter 2 Related Work 5
2.1 Wi-Fi Based RSSI Location System . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Deterministic Method . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Probabilistic Method . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Location System Using Spatial Information . . . . . . . . . . . . . . . . .13
2.2.1 Using Spatial Information Directly . . . . . . . . . . . . . . . . . . . 14
2.2.2 Using Spatial Information Indirectly . . . . . . . . . . . . . . . . . . 14
2.2.3 Other Systems provide Room-level Location Information . . . . . . . . . .15
Chapter 3 Room-level Localization 17
3.1 Particle Filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17
3.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20
3.3 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Chapter 4 System Design and Implementation 25
4.1 The Main Idea of Lock Maker . . . . . . . . . . . . . . . . . . . . . . . .25
4.2 The Main Idea of Region-level Sensor Model . . . . . . . . . . . . . . . . 28
4.3 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . .29
4.3.1 Sensor Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.3.2 Motion Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3.3 Space Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31
4.3.4 Spatial Constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.3.5 Region-level Sensor Model . . . . . . . . . . . . . . . . . . . . . . . .42
Chapter 5 Experiment 47
5.1 Introduction of Compared Methodologies . . . . . . . . . . . . . . . . . . 47
5.1.1 Walking Area . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.1.2 Collision Detection Algorithm . . . . . . . . . . . . . . . . . . . . . .48
5.2 Preliminary Experiment . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.2.1 The Sample Rate of the Sensor . . . . . . . . . . . . . . . . . . . . . .51
5.2.2 The Standard Deviation of Sensor Model in the Experiment Radio Map . . . 52
5.2.3 The Error Ratio of the Sensor Model in the Experiment Radio Map . . . . .53
5.2.4 The Parameters of Region-level Sensor Model . . . . . . . . . . . . . . .56
5.3 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3.1 The Enter Depth of R324 is 1.5 meter . . . . . . . . . . . . . . . . . . 60
5.3.2 The Enter Depth of R324 is 3 meter . . . . . . . . . . . . . . . . . . . 60
Chapter 6 Conclusion 73
6.1 Summary of Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .73
6.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74
6.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .75
Bibliography 76
Chapter A Appendix 81
A.1 How to Measure the Distance to Lock . . . . . . . . . . . . . . . . . . . .81
A.2 How to Measure the Distance to Lock: A Faster Method . . . . . . . . . . . 84
A.3 The Implementation of Collision Detection Algorithm . . . . . . . . . . . .87

[1] P. Bahl and V. N. Padmanabhan. Radar: An in-building rf-based user location and tracking system. In Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, volume 2, pages 775-784, Tel Aviv, Israel, March 2000.
[2] P. Bahl, V. N. Padmanabhan, and A. Balachandran. Enhancements to the radar user location and tracking system. Technical report, Microsoft Research, 2000.
[3] F. Bennett, T. Richardson, and A. Harter. Teleporting - making applications mobile. In Proceedings of the IEEE Workshop on Mobile Computing Systems and Applications, pages 82-84, Santa Cruz, California, December 1994. IEEE Computer Society Press.
[4] G. Borriello, A. Liu, T. ORer, C. Palistrant, and R. Sharp. Walrus:wireless acoustic location with room-level resolution using ultrasound. In Proceedings of the 3rd ACM/USENIX International Conference on Mobile Systems Applications, and Services (MobiSys), pages 191-203. Usenix Association, 2005.
[5] P. Castro, P. Chiu, T. Kremenek, and R. Muntz. A probabilistic room location service for wireless networked environments. In Proceedings of the 3rd International Conference on Ubiquitous Computing (UbiComp 2001), number 18-34, Georgia,USA, 2001.
[6] H. Chen, T. Finin, A. Joshi, L. Kagal, F. Perich, and D. Chakraborty. Intelligent agents meet the semantic web in smart spaces. Proceedings of the IEEE Internet Computing, 8(6):69-79, November 2004.
[7] Y.-C. Chen, J.-R. Chiang, H.-h. Chu, P. Huang, and A. W. Tsui. Sensor-assisted wi-fi indoor location system for adapting to environmental dynamics. In Proceedings of the International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems, pages 118-125, Montreal, Quebec, Canada, October 2005.
[8] D. Clarke. Evaluation of active r‾d in the perioperative context. Technical Report tr-20051130-01, Fremont Associates technical report, November 2005.
[9] D. Clarke and A. Park. Active-r‾d system accuracy and its implications for clinical applications. In Proceedings of the 19th IEEE International Symposium on Computer-Based Medical Systems(CBMS), pages 21-26, June 2006.
[10] A. K. Dey, D. Salber, G. D. Abowd, and M. Futakawa. The conference assistant: Combining context-awareness with wearablecomputing. In Proceedings of the Third International Symposium onWearable Computers(ISWC ''99), 1999.
[11] D. Fox, J. Hightower, L. Liao, D. Schulz, and G. Borriello. Bayesian filtering for location estimation. In Proceedings of the Workshop on Location-aware Computing at the IEEE Pervasive Computing, 2003.
[12] D. Fox, J. Hightower, L. Liao, D. Schulz, and G. Borriello. Bayesian filters for location estimation. In Proceedings of the IEEE Pervasive Computing, volume 2, July 2003.
[13] J.-S. Gutmann, W. Burgard, D. Fox, and K. Konolige. An experimental comparison of localization methods. In Proceedings of the Intelligent Robots and Systems on IEEE/RSJ International Conference, volume 2, pages 736-743, Victoria, BC, Canada, October 1998.
[14] Y. Gwon, R. Jain, and T. Kawahara. Robust indoor location estimation of stationary and mobile users. In Proceedings of the Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies(INFOCOM), volume 2, March 2004.
[15] A. Harter and A. Hopper. A distributed location system for the active office. In Proceedings of the Network on IEEE, volume 8, pages 62-70, January 1994.
[16] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher. Range-free localization schemes for large scale sensor networks. In Proceedings of the 9th annual international conference on Mobile computing and networking(MobiCom), pages 81-95, San Diego, CA, USA, 2003. ACM Press.
[17] J. Hightower and G. Borriello. Location systems for ubiquitous computing. IEEE Computer Magazine, 34(8):57-66, August 2001.
[18] J. Hightower and G. Borriello. A survey and taxonomy of location systems for ubiquitous computing. Technical Report UW CSE 01-08-03, University of Washington, Department of Computer Science and Engineering, 2001.
[19] J. Hightower and G. Borriello. Particle ‾lters for location estimation in ubiquitous computing: A case study. In N. Davies, E. Mynatt, and I. Siio, editors, Proceedings of the Sixth International Conference on Ubiquitous Computing, volume 3205, pages 88-106. Springer-Verlag, September 2004.
[20] S. W. Lee, S. Y. Cheng, J. Y. J. Hsu, P. Huang, and C. W. You. Emergency care management with location-aware services. In Proceedings of the First Workshop on Location Based Services for Health Care(Locare''06) at Pervasive Computing Technologies for Healthcare, Innsbruck, Austria, November 2006.
[21] C. Liu, K.Wu, and T. He. Sensor localization with ring overlapping based on comparison of received signal strength indicator. In Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems(MASS), pages 516-518, October 2004.
[22] T. Manesis and N. Avouris. Survey of position location techniques in mobile systems. In M. Tscheligi, R. Bernhaupt, and K. Mihalic, editors, Proceedings of the 7th Conference on Human-Computer Interaction with Mobile Devices and Services(Mobile HCI), pages 291-294, Salzburg, Austria, September 2005. ACM.
[23] S. Y. Seidel and T. S. Rapport. 914 mhz path loss prediction models for indoor wireless communications in multi°oored buildings. In Proceedings of the Antennas and Propagation, IEEE Transactions on, volume 40, pages 207-217, February 1992.
[24] V. Seshadri, G. V. Zaruba, and M. Huber. A bayesian sampling approach to in-door localization of wireless devices using received signal strength indication. In Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, pages 75-84, Washington, DC, USA, 2005. IEEE Computer Society.
[25] J.Wang and X. An. Rf-opt:a range-free online person tracking system. In Proceedings of the First Workshop on Location Based Services for Health Care(Locare''06) at Pervasive Computing Technologies for Healthcare, Innsbruck, Austria, November 2006.
[26] R.Want, A. Hopper, V. Falcao, and J. Gibbons. The active badge location system. In Proceedings of the ACM Transactions on Information Systems, pages 91-102, January 1992.
[27] R.Want, B. N. Schilit, N. I. Adams, R. Gold, K. Petersen, D. Goldberg, and M. Ellis, John R.Weiser. An overview of the parctab ubiquitous computing experiment. In Proceedings of the Personal Communications, IEEE, volume 2, pages 28-43, December 1995.
[28] M.Weiser. Some computer science issues in ubiquitous computing. In Proceedings of the Communications of the ACM, volume 36, pages 75{84, New York, NY, USA, July 1993. ACM Press.
[29] G.Welch and G. Bishop. An introduction to the kalman filter. Technical report, University of North Carolina at Chapel Hill, 1995.
[30] C.Wojek and S. R. Nickel, Kai. Activity recognition and room-level tracking in an o±ce environment. In Proceedings of the IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems(MFI''06), Heidelberg, Germany, September 2006.
[31] M. Youssef and A. Agrawala. The horus wlan location determination system. In Proceedings of the 3rd international conference on Mobile systems, applications, and services(MobiSys ''05), pages 205-218, Seattle, Washington, June 2005. ACM Press.