跳到主要內容

臺灣博碩士論文加值系統

(44.200.86.95) 您好!臺灣時間:2024/05/28 08:28
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:林洋科
研究生(外文):Yang-Ke Lin
論文名稱:室內幾何定位演算法之效能評估與改善
論文名稱(外文):Performance Analysis and Improvement of Geometric Location Estimation Algorithms for Indoor Environments
指導教授:邱奕世
指導教授(外文):Yih-Shyh Chiou
學位類別:碩士
校院名稱:中原大學
系所名稱:通訊工程碩士學位學程
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2019
畢業學年度:107
語文別:中文
論文頁數:99
中文關鍵詞:室內定位系統 (IPS)卡爾曼濾波 (KF)定位追蹤三角定位無線通信
外文關鍵詞:indoor positioning systemKalman filterlocation trackingtrilaterationwireless
相關次數:
  • 被引用被引用:1
  • 點閱點閱:180
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著無線感測網路以及物聯網技術的蓬勃發展,使得以定位為基礎的適地性服務 (LBS,Location-Based Service) 越來越受到廣泛的關注,因而帶動了定位技術的發展。定位技術依環境可分為戶外以及室內的定位系統,戶外環境定位技術的發展已經十分成熟,例如全球定位系統 (GPS,Global Positioning System),但因為GPS的訊號無法穿透大部分的建築物,所以無法適用於室內環境。隨著室內環境定位應用需求的增加,已有各式各樣的應用於生活中出現,例如大眾運輸、商業宣傳以及緊急救援等等。常用於室內定位系統的機制有紅外線、超音波、藍芽以及Wi-Fi等技術。定位系統依照定位機制取得資料的方式,可分成 Time of Arrival (TOA)、 Angle of Arrival (AOA)、 Time Difference of Arrival (TDOA) 以及 Received Signal Strength (RSS) 等技術。目前有許多不同的定位方法,本論文探討以及評估數種三角幾何定位演算法之效能。此篇論文是模擬在室內環境中接收到 Wi-Fi 的訊號強度,並將訊號強度依照電波傳遞模型轉換成距離,接著再依照傳遞距離以及三角定位的演算法計算移動端的位置。使用電波傳遞模型的三角定位方法會造成有些估測位置不合理的情形,為了減緩不合理的估測結果,本論文使用卡爾曼濾波 (KF, Kalman Filter) 的追蹤演算法提高定位的準確度,使估測的位置可以更接近真實移動的路徑,進而改善定位的準確度。
Due to the rapid development of wireless sensor network and internet of things (IoT) technologies, the applications of location-based services (LBSs) are becoming more and more popular, and they have led to the development of localization technologies. According to the environments, positioning systems can be divided into outdoor and indoor localization technologies. The developments of outdoor environmental localization technologies have been very mature, such as global positioning system (GPS). However, the GPS signals can not penetrate most buildings. As a result, it is not suitable for indoor environments. In addition, many localization technologies have been used for indoor positioning systems, such as ultrasonic, infrared, Bluetooth, Wi-Fi, and so on. In terms of the localization mechanisms, the positioning systems can be divided into the time of arrival (TOA), angle of arrival (AOA), time difference of arrival (TDOA), and received signal strengths (RSSs). This thesis evaluates the performances of several kinds of geometric location estimation algorithms. In terms of the Wi-Fi signals in an indoor environment, the trilateration approaches based on the signal propagation model and the collection of RSSs are considered as distance functions to determine user’s location. The localization approach using empirical path loss model related to the environment will cause some unreasonable estimated location. In order to mitigate the unreasonable results, this thesis uses Kalman filter (KF) tracking approach to improve the accuracy of estimated locations. And then, the estimated locations are closer to the real walking path.
目錄

摘要 I
Abstract II
致謝 IV
目錄 V
圖目錄 VII
表目錄 XI
縮寫字 XIV
第一章 緒論 1
1.1 研究背景 1
1.2 研究目的與動機 1
1.3 論文架構 2
第二章 相關文獻探討 3
2.1 三角定位法 (Trilateration) 3
2.1.1 Original (ORG) 3
2.1.2 Centroid Intersection Average (CIAV) 4
2.1.3 Lines Intersection Average (LIAV) 5
2.1.4 Least Square (LS) 8
2.2 卡爾曼濾波 (Kalman Filter) 演算法 10
第三章 定位演算法開發與設計 13
3.1 定位流程 13
3.2 幾何輔助定位演算法 14
3.2.1 Original Displacement Rotation (ODR) 15
3.2.2 Centroid Intersection Select (CIS) 19
3.2.3 Centroid Intersection K-Nearest Neighbor (CIKNN) 23
第四章 研究成果分析與討論 24
4.1 定位的時間複雜度以及準確度 24
4.2 模擬定位路徑 40
4.3 平均 RSSI 之定位效能比較 62
4.4 主觀效能評估 70
第五章 結論以及未來展望 72
附錄 74
A.1 變異量以及定位座標分布狀況 74
A.2 CIKNN 之模擬結果 76
參考文獻 82
論文發表 84

圖目錄

Fig. 2-1. 在理想狀況下,三個圓中會有一個共同之交點 3
Fig. 2-2. APs 依照特定幾何擺放位置方式估測未知位置 P 的座標 4
Fig. 2-3. 將 、 以及 的座標平均計算未知位置 P 的座標 5
Fig. 2-4. (a) 為 、 以及 交於一點的情況, (b) 出現二圓無交點的情況,導致 、 以及 無法交於一點。綜上述兩種情況決定統一平均直線方程式產生的交點估測未知位置 P 7
Fig. 2-5. (a) 調整半徑之方法:當二圓的圓心距離大於二半徑相加時,定位演算可依據方程式 (11) 以及 (12) 找到交點 8
Fig. 2-5. (b) 調整半徑之方法:當二圓的圓心距離小於二半徑相加時,定位演算可依據方程式 (13) 以及 (14) 找到交點 8
Fig. 2-6. 將三個圓之半徑以及 APs 座標代入矩陣後即可估測未知位置 P 的 x 軸以及 y 軸的座標 10
Fig. 2-7. APs 位置的 GDOP 環境產生精準度偏差的情形 10
Fig. 2-8. KF定位追蹤示意圖 12
Fig. 3-1. 模擬使用 RSSI 進行室內定位後加入KF之流程圖 14
Fig. 3-2. 模擬使用 RSSI (AVG) 進行室內定位之流程圖 14
Fig. 3-3. ODR 定位演算法的位移以及旋轉的幾何運算迭代流程 16
Fig. 3-4. 為了容易理解 ODR 定位時的旋轉方向,我們假定圖中的點皆為 AP2,箭頭則為 AP2 將旋轉之方向 17
Fig. 3-5. 連續的 ODR 定位流程圖 19
Fig. 3-6. CIAV 定位演算法在 APs 圍成之三角形區塊外造成誤差的狀況 20
Fig. 3-7. 在 、 以及 中選擇一個做為 P 21
Fig. 3-8. 連續的 CIS 定位流程圖 22
Fig. 3-9. 計算交點間的距離,以最短距離的 K 個交點平均即為 P 23
Fig. 4-1. 計算時間複雜度時使用四種 APs 之擺放位置以及 1 圈的路徑 24
Fig. 4-2. 時間複雜度趨勢圖 25
Fig. 4-3. 模擬 PAOUT 路徑所使用的四種 APs 擺放位置及路徑 26
Fig. 4-4. (a) PAOUT 路徑中, APs 採 Bottom 擺設的準確度趨勢圖 27
Fig. 4-4. (b) PAOUT 路徑中, APs 採 Top 擺設的準確度趨勢圖 28
Fig. 4-4. (c) PAOUT 路徑中, APs 採 Left 擺設的準確度趨勢圖 29
Fig. 4-4. (d) PAOUT 路徑中, APs 採 Right 擺設的準確度趨勢圖 30
Fig. 4-5. (a) CIAV 定位演算法:在正方形路徑上移動 20 圈,由左上至右下分別是變異量 (Var) = 1 到 12 的路徑 (路徑以及 APs 擺設: PAOUT & Bottom) 31
Fig. 4-5. (b) LIAV 定位演算法:在正方形路徑上移動 20 圈,由左上至右下分別是 Var = 1 到 12 的路徑 (路徑以及 APs 擺設: PAOUT & Bottom) 32
Fig. 4-5. (c) LS 定位演算法:在正方形路徑上移動 20 圈,由左上至右下分別是 Var = 1 到 12 的路徑 (路徑以及 APs 擺設: PAOUT & Bottom) 32
Fig. 4-5. (d) ODR 定位演算法:在正方形路徑上移動 20 圈,由左上至右下分別是 Var = 1 到 12 的路徑 (路徑以及 APs 擺設: PAOUT & Bottom) 33
Fig. 4-5. (e) CIS定位演算法:在正方形路徑上移動 20 圈,由左上至右下分別是 Var = 1 到 12 的路徑 (路徑以及 APs 擺設: PAOUT & Bottom) 33
Fig. 4-5. (f) CIAV 定位演算法:在正方形路徑上移動 60 圈,由左上至右下分別是 Var = 1 到 12 的路徑 (路徑以及 APs 擺設: PAIN & Bottom) 34
Fig. 4-5. (g) LIAV 定位演算法:在正方形路徑上移動 60 圈,由左上至右下分別是 Var = 1 到 12 的路徑 (路徑以及 APs 擺設: PAIN & Bottom) 34
Fig. 4-5. (h) LS 定位演算法:在正方形路徑上移動 60 圈,由左上至右下分別是 Var = 1 到 12 的路徑 (路徑以及 APs 擺設: PAIN & Bottom) 35
Fig. 4-5. (i) ODR 定位演算法:在正方形路徑上移動 60 圈,由左上至右下分別是 Var = 1 到 12 的路徑 (路徑以及 APs 擺設: PAIN & Bottom) 35
Fig. 4-5. (j) CIS 定位演算法:在正方形路徑上移動 60 圈,由左上至右下分別是 Var = 1 到 12 的路徑 (路徑以及 APs 擺設: PAIN & Bottom) 36
Fig. 4-6. 使用 Bottom 以及 Left 兩種 APs 擺放位置模擬 PAIN 環境的路徑圖 38
Fig. 4-7. 共 50 次,行走 20 公尺之速度 40
Fig. 4-8. 模擬定位路徑以及 APs 擺設位置 41
Fig. 4-9. (a) 模擬定位路徑 PAOUT- RRD: RSSI → trilateration (RT) 42
Fig. 4-9. (b) 模擬定位路徑 PAOUT- RRD: RSSI (AVG) → trilateration (RAT) 42
Fig. 4-9. (c) 模擬定位路徑 PAOUT- RRD: RSSI → trilateration → KF (RTKF) 43
Fig. 4-9. (d) 模擬定位路徑 PAOUT- RRD: RSSI (AVG) → trilateration → KF (RATKF) 43
Fig. 4-10. 模擬定位路徑 PAOUT- RRD 的 CDF 45
Fig. 4-11. (a) 模擬定位路徑 PAIN- RRD: RT 46
Fig. 4-11. (b) 模擬定位路徑 PAIN- RRD: RAT 47
Fig. 4-11. (c) 模擬定位路徑 PAIN- RRD: RTKF 47
Fig. 4-11. (d) 模擬定位路徑 PAIN- RRD: RATKF 48
Fig. 4-12. 模擬定位路徑 PAIN- RRD 的 CDF 49
Fig. 4-13. 量測地點為中原大學篤信 4 樓走廊,藍點為量測的點 50
Fig. 4-14. (a) 1 到 14 公尺各個方位的 boxplot 51
Fig. 4-14. (b) 1 到 8 公尺各個方位的 PDF 52
Fig. 4-14. (c) 9 到 14 公尺各個方位的 PDF 53
Fig. 4-15. 四個方位平均 (AVG) 之 RSSI 以及 path loss 54
Fig. 4-16. (a) 模擬定位路徑 PAOUT- MRD: RT 55
Fig. 4-16. (b) 模擬定位路徑 PAOUT- MRD: RAT 55
Fig. 4-16. (c) 模擬定位路徑 PAOUT- MRD: RTKF 56
Fig. 4-16. (d) 模擬定位路徑 PAOUT- MRD: RATKF 56
Fig. 4-17. 模擬定位路徑 PAOUT- MRD 的 CDF 57
Fig. 4-18. (a) 模擬定位路徑 PAIN- MRD: RT 59
Fig. 4-18. (b) 模擬定位路徑 PAIN- MRD: RAT 59
Fig. 4-18. (c) 模擬定位路徑 PAIN- MRD: RTKF 60
Fig. 4-18. (d) 模擬定位路徑 PAIN- MRD: RATKF 60
Fig. 4-19. 模擬定位路徑 PAIN- MRD 的 CDF 61
Fig. 4-20. 模擬定位路徑以及 APs 擺設位置 63
Fig. A-1. APs 擺設以及定位點 74
Fig. A-2. 時間複雜度趨勢圖 77
Fig. A-3. 模擬 PAOUT 路徑中, APs 採 Bottom 以及 Left 擺設的準確度趨勢圖 78
Fig. A-4. (a) CIKNN 定位演算法:在正方形路徑上移動 20 圈,由左上至右下分別是變異量 (Var) = 1 到 12 的路徑 (路徑以及 APs 擺設: PAOUT & Bottom) 79
Fig. A-4. (b) CIKNN 定位演算法:在正方形路徑上移動 60 圈,由左上至右下分別是 Var = 1 到 12 的路徑 (路徑以及 APs 擺設: PAIN & Bottom) 80
Fig. A-5. 模擬 PAIN 路徑中, APs 採 Bottom 以及 Left 擺設的準確度趨勢圖 80

表目錄

Table. 4-1 計算時間複雜度的 APs 擺放位置 25
Table. 4-2 模擬 PAOUT定位路徑的 APs 擺放位置 26
Table. 4-3 (a) APs 擺設方式為 Bottom 以及模擬路徑為 PAOUT 的環境下,不同定位演算法的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位: meter) 37
Table. 4-3 (b) APs 擺設方式為 Left 以及模擬路徑為 PAOUT 的環境下,不同定位演算法的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位: meter) 37
Table. 4-4 (a) APs 擺設方式為 Bottom 以及模擬路徑為 PAIN 的環境下,不同定位演算法的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位: meter) 39
Table. 4-4 (b) APs 擺設方式為 Left 以及模擬路徑為 PAIN 的環境下,不同定位演算法的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位: meter) 39
Table. 4-5 模擬 PAOUT- RRD 定位路徑的變異數 44
Table. 4-6 在模擬路徑為 PAOUT- RRD 環境下,不同定位演算法分別依 RT、 RAT、 RTKF 以及 RATKF 機制定位後的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位:meter) 45
Table. 4-7 模擬 PAOUT- RRD 定位路徑的變異數 48
Table. 4-8 在模擬路徑為 PAIN 環境下,不同定位演算法分別依 RT、 RAT、 RTKF 以及 RATKF 機制定位後的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位:meter) 49
Table. 4-9 量測之 RSSI 值數據 50
Table. 4-10 模擬 PAOUT- MRD 定位路徑的變異數 57
Table. 4-11 在模擬路徑為 PAOUT- MRD 環境下,不同定位演算法分別依 RT、 RAT、 RTKF 以及 RATKF 機制定位後的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位: meter) 58
Table. 4-12 模擬 PAIN- MRD 定位路徑的變異數 61
Table. 4-13 在模擬路徑為 PAIN- MRD 環境下,不同定位演算法分別依 RT、 RAT、 RTKF 以及 RATKF 機制定位後的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位:meter) 62
Table. 4-14 (a) 不同定位演算法在模擬路徑為 PAOUT 以及 RSSI 變異數 = 4.53 dB 的環境下, RAT 機制的取樣平均筆數與定位誤差的關係比較 (單位: meter) 63
Table. 4-14 (b) 不同定位演算法在模擬路徑為 PAOUT 以及 RSSI 變異數 = 2 dB 的環境下, RAT 機制的取樣平均筆數與定位誤差的關係比較 (單位: meter) 64
Table. 4-15 (a) 不同定位演算法在模擬路徑為 PAOUT 以及 RSSI 變異數分別為 4.53 dB 以及 2 dB 的環境下, RAT 機制的取樣平均筆數與累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位: meter) 65
Table. 4-15 (b) 不同定位演算法在模擬路徑為 PAOUT 以及 RSSI 變異數分別為 4.53 dB 以及 2 dB 的環境下, RATKF 機制的取樣平均筆數與累積分布函數 (CDF) 達50% 以及 90% 的定位誤差比較 (單位: meter) 66
Table. 4-16 (a) 不同定位演算法在模擬路徑為 PAIN 以及 RSSI 變異數分別為 4.53 dB 以及 2 dB 的環境下, RAT 機制的取樣平均筆數與累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位: meter) 68
Table. 4-16 (b) 不同定位演算法在模擬路徑為 PAIN 以及 RSSI 變異數分別為 4.53 dB 以及 2 dB 的環境下, RATKF 機制的取樣平均筆數與累積分布函數 (CDF) 達50% 以及 90% 的定位誤差比較 (單位: meter) 69
Table. 4-17 主觀效能評估比較- PAOUT 70
Table. 4-18 主觀效能評估比較- PAIN 71
Table. A-1 不同的變異數之 PDF 75
Table. A-2 (a) APs 擺設方式為 Bottom 以及模擬路徑為 PAOUT 的環境下,不同定位演算法的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位: meter) 78
Table. A-2 (b) APs 擺設方式為 Left 以及模擬路徑為 PAOUT 的環境下,不同定位演算法的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位: meter) 79
Table. A-3 (a) APs 擺設方式為 Bottom 以及模擬路徑為 PAIN 的環境下,不同定位演算法的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位: meter) 81
Table. A-3 (b) APs 擺設方式為 Left 以及模擬路徑為 PAIN 的環境下,不同定位演算法的累積分布函數 (CDF) 達 50% 以及 90% 的定位誤差比較 (單位: meter) 81
[1]陳家彥,「利用 BLE 進行室內定位技術之研究」,銘傳大學資訊傳播工程學系碩士班碩士學位論文,民國105年8月。
[2]I. Sharp and K. Yu, “Enhanced least-squares positioning algorithm for indoor positioning,” IEEE Trans. Mobile Comput., vol. 12, no. 8, pp. 1640–1650, August 2013.
[3]C.-H. Huang, L.-H. Lee, C. C. Ho, L.-L. Wu, and Z.-H. Lai, “Real-time RFID indoor positioning system based on Kalman-filter drift removal and heron-bilateration location estimation,” IEEE Trans. Instrum. Meas., vol. 64, no. 3, pp. 728–739, March 2015.
[4]S. He and S.-H. G. Chan, “INTRI: Contour-based trilateration for indoor fingerprint-based localization,” IEEE Trans. Mobile Comput., vol. 16, no. 6, pp. 1676–1690, June 2017.
[5]X. Cheng, H. Shu, Q. Liang, and D. H.-C. Du, “Silent positioning in underwater acoustic sensor networks,” IEEE Trans. Veh. Technol., vol. 57, no. 3, pp. 1756–1766, May 2008
[6]S. Sadowski and P. Spachos, “RSSI-based indoor localization with the internet of things,” IEEE Access., vol. 6, pp. 30149–30161, June 2018.
[7]Z. Abu-Shaban, X. Zhou, T. D. Abhayapala, “A novel TOA-based mobile localization technique under mixed LOS/NLOS conditions for cellular networks,” IEEE Trans. Veh. Technol., vol. 65, no. 11, pp. 8841–8853, Nov. 2016.
[8]L. Yao, Z. Dai, S. Yang, and H. Ding, “A quadratic centroid algorithm for wireless sensor network localization,” in Proc. CCC., July 2017, pp. 9041–9045.
[9]C.-L. Wang, Y.-S. Chiou, and Y.-S. Dai, “An adaptive location estimator based on kalman filtering for wireless sensor networks,” in Proc. IEEE VTC., April 2007, pp. 864–868.
[10]V. G. Ashok, Y. Gongjun, S. Olariu, and A. Gupta, “Privacy aware localization in VANET,” , in Proc. IEEE MASS., Nov. 2010, pp. 739–744.
[11]W. Dargie and C. Poellabauer, Fundamentals of wireless sensor networks: theory and practice. Chichester, U.K.: John Wiley & Sons, pp.253–254, 2010.
[12]A. El-Rabbany, Introduction to GPS: the global positioning system. Norwood, Mass.: Artech House, pp. 39–41, 2002.
[13]C.-L. Wang and Y.-S. Chiou, “An adaptive positioning scheme based on radio propagation modeling for indoor WLANs,” in Proc. IEEE VTC., vol. 6, May 2006, pp. 2676 –2680.
[14]C.-L. Wang, Y.-S. Chiou, and F. Tsai, “Reduced-complexity tracking scheme based on adaptive weighting for location estimation,” IET Commun., vol. 7, no. 7, pp. 673–684, May 2013.
[15]Y.-S. Chiou and F. Tsai , “A reduced-complexity data-fusion algorithm using belief propagation for location tracking in heterogeneous observations,” IEEE Trans. Cybern., vol. 44, no. 6, pp. 922–935, June 2014.
[16]Y.-S. Chiou, C.-L. Wang, and S.C. Yeh, “Reduced-complexity scheme using alpha-beta filtering for location tracking,” IET Commun., vol. 5, no. 13, pp. 1806–1813, Sept. 2011.
[17]P. Bahl and V.N. Padmanabhan, “RADAR: an in-building RF-based user location and tracking system,” in Proc. IEEE INFOCOM., vol. 2, March 2000, pp. 775–784.
[18]Y. Zhuang, Z. Syed, Y. Li, and N. El-Sheimy, “Evaluation of two wifi positioning systems based on autonomous crowdsourcing of handheld devices for indoor navigation,” IEEE Trans. Mobile Comput., vol. 15, no. 8, pp. 1982–1995, August 2016.
[19]M. H. Dridi, “Tracking individual targets in high density crowd scenes analysis of a video recording in Hajj 2009,” CUS., vol.3, no.1, pp.35–53, March 2015.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊