臺灣博碩士論文加值系統

在定位服務裡，系統的反應時間是一個關鍵點，對於即時性的應用來說，更是如此。在大型網路下（如無線城市），以樣本比對法為基礎的定位系統，如此的需求更為明顯。此類定位法的運作是仰賴目前物體收集到的訊號強度特徵與事先在訓練階段建立的以訊號強度為樣本的資料庫做比對來達到定位的目的。在這篇論文中，我們提出一個以群簇法為基礎的樣本比對定位架構來加快定位的程序。藉著將擁有類似的訊號特徵樣本的訓練點群聚在一起，我們會展示如何降低定位所需的比較複雜度來加速整個定位的流程。為了解決訊號飄移的問題，我們更提出了幾個有效的分群法。在許多廣泛的模擬的結果下，我們可以發現：平均來說，在不影響定位準確度的情況下，我們提出的系統相較於原來的樣本比對法的比較複雜度上可減少至少90%。

In location-based services, the response time of location
determination is critical, especially in real-time applications. This is especially true for pattern-matching localization methods, which rely on comparing an object's current signal strength pattern against a pre-established location database of signal strength patterns collected at the training phase, when the sensing field is large (such as a wireless city). In this work, we propose a cluster-based localization framework to speed up the positioning process for pattern-matching localization schemes. Through grouping training locations with similar signal strength
patterns, we show how to reduce the associated comparison cost so as to accelerate the pattern-matching process. To deal with signal fluctuations, several clustering strategies are proposed. Extensive simulation studies are conducted. Experimental results show that more than 90% computation cost can be reduced in average without degrading the positioning accuracy.

中文摘要i
Abstract ii
誌謝iii
Contents iv
List of Figures 1
1 Introduction 2
2 RelatedWorks 5
3 The Cluster-Based Pattern-Matching Localization Framework 8
3.1 The Training Phase . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 The Positioning Phase . . . . . . . . .. .. . 10
4 Clustering Algorithms 11
4.1 k-means Algorithm . . . . . . . . . . .. 11
4.2 Clustering Techniques Allowing Overlaps . .. . 13
4.2.1 Multi-Nearest-Neighbor Strategy . . . . .13
4.2.2 Voronoi-based Strategy . . . . . . . . . . . 14
4.2.3 Probability-based Strategy . . . . . . . . . 16
5 Simulations 20
5.1 Simulation Model . . . . . . . . . . .. . . 20
5.2 Impact of Clustering on the Average Positioning Error . 22
5.3 Sensitive Performance Study for Clustering Strategies. 23
5.4 Performance Comparison of Clustering Strategies . 25
5.5 Performance Study of Total Comparison Cost . . .. 25
6 Conclusion 27
Bibliography 28

[1] P. Enge and P. Misra, “Special Issue on Global Positioning System,” Proc. IEEE, vol. 87,
no. 1, pp. 3–15, 1999.
[2] R. Want1, A. Hopper, V. Falc˜ao, and J. Gibbons, “The Active Badge Location System,”
ACM Trans. on Information Systems (TOIS), vol. 10, no. 1, pp. 91–102, 1992.
[3] N. B. Priyantha, A. Chakraborty, and H. Balakrishnan, “The Cricket Location-support
System,” in IEEE/ACM MOBICOM. ACM Press New York, NY, USA, 2000, pp. 32–43.
[4] P. Bahl and V. N. Padmanabhan, “RADAR: An In-Building RF-based User Location and
Tracking System,” in IEEE INFOCOM, 2000, pp. 775–784.
[5] T. Roos, P.Myllym¨aki, H. Tirri, P.Misikangas, and J. Siev¨anen, “A ProbabilisticApproach
to WLAN User Location Estimation,” Int’l Journal of Wireless Information Networks,
vol. 9, no. 3, pp. 155–164, 2002.
[6] R. Battiti, T. L. Nhat, and A. Villani, “Location-aware Computing: A Neural Network
Model for Determining Location in Wireless LANs,” University of Trento, Department of
Information and Communication Technology, Tech. Rep. DIT-5, 2002.
[7] M. Brunato and R. Battiti, “Statistical Learning Theory for Location Fingerprinting in
Wireless LANs,” Computer Networks, vol. 47, no. 6, 2005.
[8] V. Seshadri, G. V. Z´aruba, and M. Huber, “A Bayesian Sampling Approach to In-door
Localization of Wireless Devices using Received Signal Strength Indication,” in IEEE
PERCOM, 2005, pp. 75– 84.
[9] J. Letchner, D. Fox, and A. LaMarca, “Large-Scale Localization from Wireless Signal
Strength,” in Proc. of the Nat’l Conf. on Artificial Intelligence (AAAI), 2005, pp. 15–20.
[10] Y.-C. Cheng, Y. Chawathe, A. LaMarca, and J. Krumm, “Accuracy Characterization for
Metropolitan-scaleWi-Fi Localization,” in ACM MOBISYS, vol. 5, 2005, pp. 233–245.
[11] A. LaMarca, J. Hightower, I. Smith, and S. Consolvo, “Self-Mapping in 802.11 Location
Systems,” in Proc. 7th Int’l Conf. on Ubiquitous Computing (UBICOMP). Springer,
2005, pp. 87–104.
[12] A. Haeberlen, E. Flannery, A.M. Ladd, A. Rudys, D. S.Wallach, and L. E. Kavraki, “Practical
Robust Localization over Large-scale 802.11 Wwireless Networks,” in IEEE/ACM
MOBICOM, 2004.
[13] X. Chai and Q. Yang, “Reducing the Calibration Effort for Location Estimation Using
Unlabeled Samples,” in IEEE PERCOM, 2005, pp. 95–104.
[14] J. J. Pan, J. T. Kwok, Q. Yang, and Y. Chen, “Multidimensional Vector Regression for
Accurate and Low-Cost Location Estimation in Pervasive Computing,” IEEE Trans. on
Knowledge and Data Engineering, vol. 18, no. 9, pp. 1181–1193, 2006.
[15] P. Krishnan, A. S. Krishnakumar, W.-H. Ju, C. Mallows, and S. Ganu, “A System for
LEASE: Location Estimation Assisted by Stationary Emitters for Indoor RFWireless Networks,”
in IEEE INFOCOM, vol. 2, 2004, pp. 1001–1011.
[16] J. MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations,”
in Proc. 5th Berkeley Symposium on Mathematical Statistics and Probability, vol. 1,
1967, pp. 281–297.
[17] M. Youssef and A. Agrawala, “On the Optimality of WLAN Location Determination Systems,”
in Comm. Networks and Dist. Syst. Modeling and Simulation Conf., 2004.
[18] A. Agiwal, P. Khandpur, and H. Saran, “LOCATOR: Location Estimation System for
Wireless LANs,” in ACM WMASH, 2004, pp. 102–109.
[19] M. A. Youssef, A. Agrawala, and A. U. Shankar, “WLAN Location Determination via
Clustering and Probability Distributions,” in IEEE PERCOM, 2003, pp. 143–150.
[20] R. Xu and D. W. II, “Survey of Clustering Algorithms,” IEEE Trans. on Neural Networks,
vol. 16, no. 3, pp. 645–678, 2005.
[21] F. Aurenhammer, “Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure,”
ACM Computing Surveys (CSUR), vol. 23, no. 3, pp. 345–405, 1991.
[22] T. S. Rappaport, Wireless Communications. Principles and Practice, 1996.