臺灣博碩士論文加值系統

目前常見的定位演算法是以訊號強度為特徵的指紋辨識系統,能
夠在障礙物和人的影響下進行定位。然而,每次定位估計都是獨立分
開的,因此它容易造成連續定位誤差過大的情況出現,為了解決這問
題,藉由考慮地圖的資訊和人的歷史行為來輔助定位。從地圖資訊,
我們利用自動的方式找到空間的骨架,從骨架可以知道自由空間的分
佈與任兩點實際的最短距離。根據不同的場景需求,基於骨架佈署參
考點演算法透過限制參考點之間的距離來簡化原始骨架。我們將人的
歷史行為路徑依照骨架轉換成相對應的軌跡,我們提出基於軌跡的序
列模式探勘求出人的行為模式,再以最近的行為路徑,基於模式匹配
的軌跡預測被提出來預測下一刻位置。然後機率以貝氏定理的方式結
合當下訊號強度特徵跟預測位置的相似度被計算,將機率作為加權最
近鄰居法的權重來估計位置。實驗結果顯示我們的演算法相比其他組
合演算法的定位誤差更小,因此我們提出的演算法被證明能夠有效地
改善傳統的定位系統。

Recently, the common positioning algorithm is the fingerprint identification
system which is characterized by the signal intensity, and can be
positioned under the influence of obstacles and people. However, each positioning
estimation is independent. As a result, it is easy to make continuous
positioning error large. In order to solve this problem, we consider the map
information and human historical behavior to assist positioning. From the
map information, we use the automatic way to find the skeleton of space.
According to the skeleton, we can know the structure of free space and the
shortest distance between any two points. Based on requirements of different
scenes, skeleton-based reference point deployment algorithm simplifies the
original skeleton by limiting the distance between reference points. Through
the skeleton, we convert the human historical trajectory into skeleton-based
trajectory. We propose trajectory-based sequential pattern mining algorithm
to obtain the human behavior patterns. pattern matching based trajectory
prediction is proposed to predict the next position. By using Bayes’ theorem
to combine current signal strength and the similarity of predicted positions,
the probability is computed. The probability is regarded as the weight of
the weighted nearest neighbor to estimate the position. Experimental results
show that our algorithm has smaller positioning errors than algorithms
of other combination. Therefore, our proposed algorithm has proved to be
effective in improving the traditional positioning system.

Chinese Abstract i
English Abstract ii
Acknowledgement iii
Contents iv
List of Figures vi
List of Tables viii
1 Introduction 1
2 Problem Fomulation and System Model 4
2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Proposed Skeleton-based Reference Point Deployment and Pattern
Matching Prediction 7
3.1 Skeleton-based Reference Point Deployment and Trajectorybased
sequential pattern mining . . . . . . . . . . . . . . . . . 7
3.1.1 GVD Skeleton Extraction . . . . . . . . . . . . . . . . . 7
3.1.2 Skeleton-based RP Deployment . . . . . . . . . . . . . 8
3.1.3 Trajectory Preprocessing . . . . . . . . . . . . . . . . . 9
3.1.4 Trajectory-based sequential pattern mining (TSPM) . 11
3.2 Pattern Matching based Trajectory Prediction . . . . . . . . . 14
3.3 Bayesian-based Weighted KNN . . . . . . . . . . . . . . . . . . 15
iv
4 Performance Evaluation 17
4.1 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.2 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . 25
5 Conclusion 30
Bibliography 31

[1] A. El-Rabbany, Introduction to GPS, Global Positioning System. Artech House,
2002.
[2] J. Kemper and H. Linde, “Challenges of Passive Infrared Indoor Localization,” in
Proc. Workshop on Positioning, Navigation and Communication, March 2008, pp.
63–70.
[3] Z. Jianyong, L. Haiyong, C. Zili, and L. Zhaohui, “Rssi based bluetooth low energy
indoor positioning,” in 2014 International Conference on Indoor Positioning and
Indoor Navigation (IPIN), Oct 2014, pp. 526–533.
[4] K. Yu and Y. J. Guo, “Statistical nlos identification based on aoa, toa, and signal
strength,” IEEE Transactions on Vehicular Technology, vol. 58, no. 1, pp. 274–286,
Jan 2009.
[5] S. Y. Jung, S. Hann, and C. S. Park, “Tdoa-based optical wireless indoor localization
using led ceiling lamps,” IEEE Transactions on Consumer Electronics, vol. 57, no. 4,
pp. 1592–1597, November 2011.
[6] D. Niculescu and B. Nath, “Ad Hoc Positioning System (APS) Using AOA,” in Proc.
Conference on Computer Communications (INFOCOM 2003), vol. 3, mar.-apr. 2003,
pp. 1734–1743.
[7] P. Bahl and V. Padmanabhan, “RADAR: an In-building RF-based User Location
and Tracking System,” in Proc. IEEE INFOCOM, vol. 2, 2000, pp. 775–784 vol.2.
[8] M. Youssef and A. Agrawala, “The Horus WLAN Location Determination System,” in
Proc. ACM Conference on Mobile Systems, Applications, and Services, ser. MobiSys
’05, 2005, pp. 205–218.
[9] A. Kokkinis, M. Raspopoulos, L. Kanaris, A. Liotta, and S. Stavrou, “Map-aided
fingerprint-based indoor positioning,” in 2013 IEEE 24th Annual International Symposium
on Personal, Indoor, and Mobile Radio Communications (PIMRC), Sept
2013, pp. 270–274.
[10] Z. Liang, M. Ioannidis, and I. Chatzis, “Geometric and topological analysis of threedimensional
porous media: pore space partitioning based on morphological skeletonization,”
Journal of colloid and interface science, vol. 221, no. 1, pp. 13–24, 2000.
[11] C. J. Chiu, K. T. Feng, and P. H. Tseng, “Spatial skeleton-enhanced location tracking
for indoor localization,” in 2017 IEEE Wireless Communications and Networking
Conference (WCNC), March 2017, pp. 1–6.
[12] T. Laursen, N. B. Pedersen, J. J. Nielsen, and T. K. Madsen, “Hidden markov model
based mobility learning fo improving indoor tracking of mobile users,” in 2012 9th
Workshop on Positioning, Navigation and Communication, March 2012, pp. 100–104.
[13] M. Chen, X. Yu, and Y. Liu, “Mining moving patterns for predicting next location,”
Information Systems, vol. 54, no. Supplement C, pp. 156 – 168, 2015. [Online].
Available: http://www.sciencedirect.com/science/article/pii/S0306437915001295
[14] E. Cho, S. A. Myers, and J. Leskovec, “Friendship and mobility: User movement
in location-based social networks,” in Proceedings of the 17th ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining, ser. KDD ’11.
New York, NY, USA: ACM, 2011, pp. 1082–1090. [Online]. Available: http://
doi.acm.org/10.1145/2020408.2020579
[15] N. T. An and T. M. Phuong, “A gaussian mixture model for mobile location prediction,”
in The 9th International Conference on Advanced Communication Technology,
vol. 2, Feb 2007, pp. 914–919.
[16] R. Srikant and R. Agrawal, Mining sequential patterns: Generalizations and performance
improvements. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996, pp. 1–
17.
[17] M. Ozer, I. Keles, H. Toroslu, P. Karagoz, and H. Davulcu, “Predicting the location
and time of mobile phone users by using sequential pattern mining techniques,” The
Computer Journal, vol. 59, no. 6, pp. 908–922, 2016. [Online]. Available: + http://
dx.doi.org/10.1093/comjnl/bxv075
[18] F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi, “Trajectory pattern mining,”
in Proceedings of the 13th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, ser. KDD ’07. New York, NY, USA: ACM, 2007, pp.
330–339. [Online]. Available: http://doi.acm.org/10.1145/1281192.1281230
[19] G. Yavaş, D. Katsaros, Özgür Ulusoy, and Y. Manolopoulos, “A data mining
approach for location prediction in mobile environments,” Data & Knowledge
Engineering, vol. 54, no. 2, pp. 121 – 146, 2005. [Online]. Available: http://
www.sciencedirect.com/science/article/pii/S0169023X04001545
[20] I. Keles, M. Ozer, I. H. Toroslu, and P. Karagoz, Location Prediction of Mobile
Phone Users Using Apriori-Based Sequence Mining with Multiple Support Thresholds.
Cham: Springer International Publishing, 2015, pp. 179–193. [Online]. Available:
https://doi.org/10.1007/978-3-319-17876-9_12
[21] J. J.-C. Ying, W.-C. Lee, T.-C. Weng, and V. S. Tseng, “Semantic trajectory mining
for location prediction,” in Proceedings of the 19th ACM SIGSPATIAL International
Conference on Advances in Geographic Information Systems, ser. GIS ’11. New
York, NY, USA: ACM, 2011, pp. 34–43. [Online]. Available: http://doi.acm.org/
10.1145/2093973.2093980