臺灣博碩士論文加值系統

無線感測器(Wireless Sensor)是現存無線網路技術中，應用很廣泛的裝置。加上近年來無線通訊的發展快速，造成無線感測網路(Wireless Sensor Network，WSN)變成很熱門的研究。在這些研究當中，探討使用感測器來做室內定位(Indoor Localization)是很常見的。目前，無線感測網路定位方法主要分成兩大類：Range-based與Range-free定位法。Range-based定位主要是需要使用測距技術(例如ToA、TDoA、AoA、RSS)來當作測量節點之間距離的工具，經由測量的資訊得到待定位點的位置；Range-free定位則是不需要測距技術僅使用參考節點來估算待定位點的位置。但是室內環境存在著許多干擾因素，很容易使得定位結果不精確。為了解決室內定位遭遇到的問題，有些演算法使用RF-mapping的方式，避免室內環境因素造成定位誤差的影響。但是，使用RF-mapping的技術，如果需要定位結果精確，則必須要較多的參考點資料，這樣做的缺點是會引起預建的時間增加與運算量的大增。因此，本論文提出基於基因演算法(Genetic Algorithms，GA)的定位演算法來估算未知節點的位置以及利用預先建立pattern的方法避免因為環境因素所造成的影響。另外，提出的演算法不需要太多參考節點的資訊來預建pattern。

Wireless Sensor is a device that is been wildly used in today''s wireless network technique. In recent years, with the rapid development of wireless communications, the WSN become a popular research topic. And using Wireless Sensor in Indoor localization is quite common in the study. At present, localization Wireless Sensor Network has divided into two categories: Range-based and Range-free localization algorithms. The Range-based algorithms must use several range techniques such as ToA, TDoA, AoA and RSS to measure distance between unknown node and neighbor node. The Range-free algorithms don''t need any range techniques but use reference node to estimate the location of unknown node. But there are many interference factors in indoor environment that causes location result inaccurate. In order to solve this problem, some algorithms use RF-mapping technique to avoid indoor interference. However, if we want an accuracy result, the RF-mapping technique would need a large number of reference node information, and it would increase the computation and the establish times. Therefore, we propose a GA based localization algorithm using pre-establish pattern to avoid the effect that caused by the environment as well as to estimate position of unknown node. In addition, the propose algorithm doesn''t need a lot of reference node information to establish pattern.

摘要I
ABSTRACTIII
表目錄VII
圖目錄VIII
第一章 緒論1
1.1：前言 1
1.2：章節架構3
第二章 定位相關研究背景4
2.1：測距方法4
2.1.1 ToA定位方法4
2.1.2 TDoA定位方法 5
2.1.3 AoA定位方法6
2.1.4 RSS定位方法6
2.2：無線訊號模型7
2.3：相關定位文獻9
第三章 基因演算法18
3.1：基因演算法簡介18
3.1.1 基因演算法基本流程18
3.1.2 基因演算法理論20
3.2：基因演算法運算子22
3.2.1 初始化(Initialization)22
3.2.2 編碼與解碼(Encoding and Decoded)22
3.2.3 適應函數(Fitness function)24
3.2.4 選擇/複製(Select/Reproduction)24
3.2.5 交配(Crossover)26
3.2.6 突變(Mutation)28
3.2.7 終止條件(Termination) 29
3.2.8 基因演算法的特色29
第四章 提出演算法之架構31
4.1 描述31
4.2 提出方法與流程33
4.3 基因演算法修改35
第五章 模擬結果39
5.1 環境參數設定40
5.2 模擬比較42
5.2.1 誤差比較42
5.2.2 鄰居錨節點數量與誤差關係51
5.2.3 參考節點密度與誤差關係52
第六章 結論與未來研究方向53
6.1 結論53
6.2 未來方向54
參考文獻55
表1：Path Loss Exponents for Different Environment8
表2：Path Loss Exponents and Standard Deviation Measured in Different Buildings[3]8
表3：節點對應適應函數值36
表4：設定參數40
圖1：ToA定位法示意圖5
圖2：TDoA定位法則示意圖6
圖3：AoA定位法則示意圖6
圖4：DV-Hop示意圖10
圖5：CDV-Hop示意圖12
圖6：Ecolocation示意圖14
圖7：建立以訊號強度為依據的條件矩陣M14
圖8：格點示意圖15
圖9：建立以距離為依據的限制矩陣C15
圖10：Ecolocation定位流程圖17
圖11：基因演算法基本流程19
圖12：各編碼方法23
圖13：輪盤法25
圖14：單點交配27
圖15：多點交配27
圖16：均一交配28
圖17：突變28
圖18：訊號衰減理想曲線31
圖19：RSS波動圖[11]32
圖20：提出的定位演算法流程圖34
圖21：加上限制範圍示意圖37
圖22：有無限制範圍比較37
圖23：場景設置41
圖24：設定待測節點位置42
圖25：未知節點1的定位情形43
圖26：未知節點2的定位情形44
圖27：未知節點3的定位情形45
圖28：未知節點4的定位情形46
圖29：未知節點5的定位情形47
圖30：未知節點6的定位情形48
圖31：未知節點7的定位情形49
圖32：錨節點數量與誤差關係51
圖33：參考節點密度與誤差關係52

一、中文部份
[1]林豐澤，演化式計算上篇：演化式演算法的三種理論模式，智慧科技與應用統計學報，pp.1-26，2003。
[2]曾煜棋、潘孟鉉、林致宇，無線區域及個人網路：隨意及感測器網路之技術與應用，加樺國際，2006。
二、英文部份
[1]A. El Moutia, K. Makki, “Time and Power Based Positioning Scheme for Indoor Location Aware Services, ”5th IEEE Consumer Communications and Networking Conference, pp.868-872, 2008.
[2]C.-H. Yang, “Indoor Localization for Wireless Sensor Networks, ” Thesis for Master of Science, Graduate Institute of communication Engineering College of Electrical Engineering and Computer Science National Taiwan University, 2007.
[3]D. Niculescu and B. Nath, “DV Based Positioning in Ad Hoc Networks, ” Jour. of Telecommunication System, pp.267-280, 2003.
[4]David E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Publishing company, Inc., 1989.
[5]H.Lim, L.-C. Kung, Jennifer C. Hou, and H. Luo, “Zero-Configuration, Robust Indoor Localization: Theory and Experimentation,” 25th IEEE International Conference on Computer Communications, pp.1-12, 2006.
[6]J.B. Andersen, T.S. Rappaport, S. Yoshida, “Propagation measurements and models for wireless communications channels,” IEEE Communications Magazine, pp.42-49, Jan. 1995.
[7]J.H. Juang, T.K. Weng, P.V. Cuong, C.Y. Hsu, Y.H. Lee, S.H. Su, “Experimental assessment of wireless sensor network localization techniques, ” 10th International Conference on Control, Automation, Robotics and Vision, pp.335-340, 2008.
[8]K. Whitehouse, C. Karlof, D. Culler, “A practical evaluation of radio signal strength for ranging-based localization, ” ACM SIGMOBILE Mobile Computing and Communications, pp.41-52, 2007.
[9]K. Yedavalli, B. Krishnamachari, S. Ravula, B. Srinivasan, “Ecolocation: a sequence based technique for RF localization in wireless sensor networks,“ Information Processing in Sensor Networks, pp.285-292, 2005.
[10]M. Ciurana, F. Barcelo-Arroyo, F. Izquierdo, “A Ranging Method with IEEE 802.11 Data Frames for Indoor Localization, ”IEEE Wireless Communications and Networking Conference, pp.2092-2096, 2007.
[11]M. Emery, M.K. Denko, “IEEE 802.11 WLAN Based Real-Time Location Tracking in Indoor and Outdoor Environments, ”Canadian Conference on Electrical and Computer Engineering, pp.1062-1065, 2007.
[12]M. Garcia, C. Martinez, J. Tomas, J. Lloret, “Wireless Sensors Self-Location in an Indoor WLAN Environment, ”International Conference on Sensor Technologies and Applications, pp.146-151, 2007.
[13]M. Negnevitsky, Artificial Intelligence：A Guide To Intelligent Systems 2/E, Addison-Wesley Publishing company, Inc., 2004.
[14]P. Bahl and V. N. Padmanabhan, “RADAR: an in-building RF-based user location and tracking system,” IEEE Computer and Communications Societies, IEEE Volume 2, pp.775-784 vol.2, 2000.
[15]P. Enge, and P. Misra, “Special issue on GPS: The global positioning systems,” Proceedings of the IEEE, No. 1, pp.3-172, 1999.
[16]Q. Zhang, J. Wang, C. Jin; J. Ye, C. Ma, W. Zhang, “Genetic Algorithm Based Wireless Sensor Network Localization, ” Fourth International Conference on Natural Computation, pp.608-613, 2008.
[17]S. Ali, P. Nobles, “A Novel Indoor Location Sensing Mechanism for IEEE 802.11 b/g Wireless LAN, ”4th Workshop on Positioning, Navigation and Communication, pp.9-15, 2007.
[18]T.K. Sarkar, Ji Zhong, K. Kyungjung, A. Medouri, M. Salazar-Palma, “A survey of various propagation models for mobile communication,“ IEEE Antennas and Propagation Magazine, pp.51-82, 2003.
[19]T.S. Rappaport, Wireless Communications principles and practice, Prentice-Hall, Inc., New Jersey, 2002.
[20]W.-W. Ji and Z. Liu, “An Improvement of DV-Hop Algorithm in Wireless Sensor Networks, ” International Conference on Wireless Communications, Networking and Mobile Computing, pp.1-4, Sept. 2006.