簡易檢索 / 詳目顯示

回結果列表
研究生： 張恩碩
Chang, En-Shou
論文名稱： 實現合作式定位演算法於室內無線感測器網路
Implementations of Collaborative Localization Algorithms for Indoor Wireless Sensor Networks
指導教授： 劉光浩
Liu, Kuang-Hao
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電腦與通信工程研究所
Institute of Computer & Communication Engineering
論文出版年： 2010
畢業學年度： 98
語文別： 中文
論文頁數： 64
中文關鍵詞： 合作式定位 、室內定位 、最大似然估計 、多維尺度 、ZigBee 、無線感測器
外文關鍵詞： Collaborative Localization, Indoor Localization, Maximum-Likelihood Estimation, Multi-Dimensional Scaling, ZigBee, Wireless Sensor Networks
相關次數： 點閱：113  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 近年來，無線網絡的定位偵測可視為最具吸引力的議題。但要獲得精確的位置信息卻是相當具有挑戰性，尤其是在室內環境，因室內無線傳輸通道的條件非常惡劣，如非視線(Non-Line-of-Sight, NLOS)傳播與電磁干擾。而定位方式除了傳統定位法(依賴於固定的參考節點)之外，近年來許多文獻提出合作式定位的概念，它是以相鄰節點間的直接合作通訊為基礎，以提高位置量測的精確度。

    在本論文中，我們研究於現實環境中，實作現有的合作式室內定位技術。在多種合作式定位演算法，以測量節點的訊號強度(Received Signal Strength Indicator, RSSI)為基礎，我們選擇其中三種經典且廣泛採用的演算法：最大似然估計(Maximum-Likelihood Estimation, MLE)、分佈式加權多維尺度(distributed weighted Multi-Dimensional Scaling, dwMDS)，及MLE結合dwMDS的演算法，稱MDS-MLE。前兩者從測量偏差結果估計未知節點參數，作為最具代表性的類型，而將MLE與dwMDS結合已從理論上驗證能進一步減少估計誤差。

    我們選用較適合定位的Zigbee無線感測器當作實作裝置，在實作中，我們考慮不同的室內佈建場景，包括無礙空間和障礙空間有著不同障礙介質。利用量測的連線品質指標(Link Quality Index, LQI)可估計點感測器之間的距離，建置距離矩陣後可估計感測器間的相對位置。

    根據模擬和實作結果，我們評比在不同的傳播條件下合作定位演算法的效能。比較它們之間的均方根誤差(Root Mean Square Errors, RMSE)，發現MDS-MLE的性能優於其他演算法，尤其是在參考節點數目較少時。從座標定位圖與RMSE測量結果發現環境影響因素的不可避免性與障礙物介質嚴重影響定位精確度，本研究顯示合作式定位演算法對提升室內定位精確度有明顯助益，但定位精確度仍受限二維定位的不足與感測器的佈建方式，如何整合三維定位技術與有效配置感測器值得更進一步研究。

    In recent years, location awareness has been deemed as the most attractive feature of wireless networks. However, acquiring precise position information is challenging, particularly in indoor environments with harsh transmission conditions such as non-line-of-sight (NLOS) and interference. Different from traditional localization methods where each node only communicates with the reference points, the notion of cooperative localization has recently been proposed that improves the measurement accuracy by utilizing the communications between neighboring nodes. Several research work for performance evaluations of cooperative localization has been reported in the literature, based on simulated propagation environments.

    In this thesis, we study the practical performance of existing indoor localization techniques by real-life implementations. Among various cooperative localization algorithms based on measured Received Signal Strength Indicator (RSSI), we choose three of them: Maximum-Likelihood Estimation (MLE), distributed weighted Multi-Dimensional Scaling (dwMDS), and MLE combined with dwMDS, known as MDS-MLE. The former two serve as the most representative forms in estimating the unknown parameters from biased measurement results, and their combination has been theoretically proven to achieve better accuracy than the use of individual one.

    Our implementation is based on Zigbee wireless sensor networks that have been widely deployed for numerous sensing and monitoring applications. In our implementation, we consider different deployment scenarios, including free-space and obstructive fields with different obstacle materials. Using the measured Link Quality Index (LQI), the distance between blind sensor motes can be estimated and their locations are collaboratively determined.

    Based on the simulation and implementation results, we assess the performance of cooperative localization algorithms in different propagation conditions. By comparing their Root Mean Square Errors (RMSE), it has been shown that MDS-MLE outperforms the others, particularly when the number of reference nodes is small. Moreover, the obstacle materials heavily affect the accuracy of the localization algorithms. Our study suggests that even with a small number of reference points, the accuracy of indoor positioning can be improved by cooperative localization methods. However, the obstacle materials heavily affect the positioning accuracy. Therefore, properly determining the location of the reference nodes should be more important than increasing their numbers.

    書名頁 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i 中文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii 英文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv 誌謝 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi 目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 表目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 圖目錄 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii 一、序論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 研究動機 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 研究目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 室內定位的挑戰性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 論文架構 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 二、室內定位相關研究工作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 室內定位技術 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.1 紅外線技術 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.2 超音波技術 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.3 Wi-Fi技術 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.4 超寬頻技術 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.5 藍芽技術 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.6 RFID . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 室內定位系統 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.1 Active Badge系統 . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Cricket系統 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.3 SpotON系統 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.4 RADAR系統 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 ZigBee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3.1 ZigBee協定堆疊 . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3.2 ZigBee特色與優點 . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.3 ZigBee與短距無線技術比較 . . . . . . . . . . . . . . . . . . . . 11 2.4 無線傳感器網路之量測方法概述 . . . . . . . . . . . . . . . . . . . . . . 13 2.4.1 Time of Arrival . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.4.2 Time Difference of Arrival . . . . . . . . . . . . . . . . . . . . . 13 2.4.3 Angle of Arrival . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.4 Received Signal Strength Indicator . . . . . . . . . . . . . . . . 14 2.5 常用定位演算法之概述 . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5.1 三角定位法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5.2 分佈式演算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5.3 集中式演算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5.4 演算法以Range-based或Range-free分類 . . . . . . . . . . . . . . 17 2.6 合作式定位演算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.6.1 Maximum Likelihood Estimator . . . . . . . . . . . . . . . . . 18 2.6.2 Multi-Dimensional Scaling . . . . . . . . . . . . . . . . . . . . . 19 三、合作式定位演算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 RSSI之錯誤估計 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 合作式定位演算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.1 MLE演算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.2 Classical Multi-dimensional Scaling演算法 . . . . . . . . . . . . 22 3.2.3 Distributed Weighted MDS演算法 . . . . . . . . . . . . . . . . . 24 3.2.4 MDS-MLE演算法 . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3 室內定位之模擬 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3.1 模擬環境之場景 . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3.2 Flow Chart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3.3 室內定位模擬結果分析 . . . . . . . . . . . . . . . . . . . . . . . 30 3.3.4 室內定位模擬結果討論 . . . . . . . . . . . . . . . . . . . . . . . 40 四、室內定位之實作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.1 簡介ZigBee-based Sensor Networks . . . . . . . . . . . . . . . . . . . . 41 4.1.1 ZigBee模組與Jennic程式 . . . . . . . . . . . . . . . . . . . . . . 41 4.1.2 Pathloss模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.2 實作結果分析與討論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2.1 實作結果分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2.2 實作結果討論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 五、結論與未來展望 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.1 主要貢獻 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.2 結論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.3 未來工作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 參考文獻 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

    [1] R. Want, A. Hopper, V. Falcao, and J. Gibbons, 「The active badge location system,」 ACM Transactions on Information Systems (TOIS), vol. 10, no. 1, p. 102, 1992.
    [2] A. Harter, A. Hopper, P. Steggles, A. Ward, and P. Webster, 「The anatomy of a context-aware application,」 Wireless Networks, vol. 8, no. 2, pp. 187–197, 2002.
    [3] N. Priyantha, A. Chakraborty, and H. Balakrishnan, 「The cricket location-support system,」 in Proc. the 6th Annual International Conference on Mobile Computing and Networking, 2000.
    [4] N. Priyantha, The cricket indoor location system. PhD thesis, MIT, June 2005.
    [5] V. Padmanabhan and V. Bahl, 「RADAR: An in-building RF-based user location and tracking system,」 in Proc. IEEE INFOCOM, Mar. 2000.
    [6] P. Bahl, V. Padmanabhan, and A. Balachandran, 「Enhancements to the RADAR user location and tracking system,」 Microsoft Research, 2000.
    [7] M. Youssef, A. Agrawala, and A. Udaya Shankar, 「WLAN location determination via clustering and probability distributions,」 in Proc. The First IEEE International Conference on Pervasive Computing and Communications (PerCom 2003), 2003.
    [8] M. Youssef and A. Agrawala, 「Handling samples correlation in the horus system,」in Proc. INFOCOM, 2004.
    [9] J. Hightower, R. Want, and G. Borriello, 「SpotON: An indoor 3D location sensing technology based on RF signal strength,」 University of Washington CSE Technical Report, Feb. 2000.
    [10] H. Ramazanali, Characterization and evaluation of ZigBee modules. PhD thesis, Link¨opings Universitet, 2006.
    [11] D. Torrieri, U. Countermeasures, and C. Center, 「Statistical theory of passive location systems,」 IEEE transactions on Aerospace and Electronic Systems, pp. 183–198, 1984.
    [12] A. Nasipuri and K. Li, 「A directionality based location discovery scheme for wireless sensor networks,」in Proc. The 1st ACM International Workshop on Wireless Sensor Networks and Applications, pp. 105–111, ACM, 2002.
    [13] D. Niculescu and B. Nath, 「DV based positioning in ad hoc networks,」 Telecommunication Systems, vol. 22, no. 1, pp. 267–280, 2003.
    [14] Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz, 「Localization from mere connectivity,」 in Proc. The 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing, pp. 201–212, 2003.
    [15] N. Patwari, J. Ash, S. Kyperountas, A. Hero III, R. Moses, and N. Correal, 「Locating the nodes: cooperative localization in wireless sensor networks,」 IEEE Signal Processing Magazine, vol. 22, no. 4, pp. 54–69, 2005.
    [16] S. Simic and S. Sastry, 「Distributed localization in wireless ad hoc networks,」Tech. Rep. UCB/ERL M02/26, UC Berkeley, Dec. 2001.
    [17] D. Niculescu and B. Nath, 「Ad hoc positioning system (APS),」 in Proc. IEEE Globecom'01, pp. 2926–2931, Nov. 2001.
    [18] C. Savarese, J. Rabaey, and K. Langendoen, 「Robust positioning algorithms for distributed ad-hoc wireless sensor networks,」 in Proc. USENIX Technical Annual Conference, Monterey, CA, 2002.
    [19] N. Patwari, A. Hero III, M. Perkins, N. Correal, and R. O』dea, 「Relative location estimation in wireless sensor networks,」 IEEE Trans. Signal Processing, vol. 51, no. 8, pp. 2137–2148, 2003.
    [20] L. Doherty, K. Pister, and L. El Ghaoui, 「Convex position estimation in wireless sensor networks,」 in Proc. IEEE INFOCOM, 2001.
    [21] N. Bulusu, J. Heidemann, and D. Estrin, 「GPS-less low-cost outdoor localization for very small devices,」IEEE Personal Communications Magazine, pp. 29–35, Oct. 2000.
    [22] T. He, C. Huang, B. Blum, J. Stankovic, and T. Abdelzaher, 「Range-free localization schemes for large scale sensor networks,」 in Proc. The 9th Annual International Conference on Mobile Computing and Networking, 2003.
    [23] R. Nagpal, H. Shrobe, and J. Bachrach, 「Organizing a global coordinate system from local information on an ad hoc sensor network,」 in Proc. The 2nd International Conference on Information Processing in Sensor Networks, 2003.
    [24] J. Kruskal and M. Wish, Multidimensional scaling. Sage Publications, Inc, 1978.
    [25] M. Cox and T. Cox, 「Multidimensional scaling,」 Handbook of Data Visualization, pp. 315–347, 2008.
    [26] J. Costa, N. Patwari, and A. Hero III, 「Distributed weighted-multidimensional scaling for node localization in sensor networks,」 ACM Transactions on Sensor Networks (TOSN), vol. 2, pp. 39–64, Feb. 2006.
    [27] V. Nhat, D. Vo, S. Challa, and S. Lee, 「Nonmetric MDS for sensor localization,」in Proc. International Symposium on Wireless Pervasive Computing, 2008.
    [28] L. Xiao, R. Li, and J. Luo, 「Sensor localization based on nonmetric multidimensional scaling,」 in Proc. The International Conference on Sensing, Computing and Automation, pp. 1–6, 2006.
    [29] N. Patwari, Location estimation in wireless sensor networks. PhD thesis, University of Michigan, 2005.
    [30] X. Ji and H. Zha, 「Sensor positioning in wireless ad-hoc sensor networks using multidimensional scaling,」 in Proc. IEEE INFOCOM, 2004.
    [31] W. Heiser and J. De Leeuw, 「How to use SMACOF-I,」 Research Report, Leiden, Leiden University: Department of Data Theory., 1977.
    [32] X. Li, 「Collaborative localization with received-signal strength in wireless sensor networks,」 IEEE Trans. on Veh. Technol., vol. 56, no. 6, pp. 3807–3817, 2007.
    [33] S. Agarwal, J. Wills, L. Cayton, G. Lanckriet, D. Kriegman, and S. Belongie, 「Generalized non-metric multidimensional scaling,」 in Proc. The Twelfth International Conference on Arti cial Intelligence and Statistics, 2007.
    [34] F. Chan, H. So, and W. Ma, 「A novel subspace approach for cooperative localization in wireless sensor networks using range measurements,」 IEEE Trans. Signal Processing, vol. 57, no. 1, pp. 260–269, 2009.
    [35] R. Ouyang, A. Wong, C. Lea, and V. Zhang, 「Received signal strength-based wireless localization via semidefinite programming,」 in Proc. IEEE Globecom'09, pp. 4637–4642, 2009.

    無法下載圖示 校內：立即公開
    校外：不公開
    電子論文尚未授權公開，紙本請查館藏目錄
    QR CODE