無線感測網路(Wireless Sensor Network, WSN)主要被運用於區域資料的蒐集，透過資料的蒐集可以使得操作者對於其區域有更深的了解並根據資料做出更好的決策。WSN雖然可以針對一整片區域進行資料的蒐集，但是對於某些任務來說，必須要更準確的了解每個感測器所處於的位置，因此必須要對感測器做定位的動作以增加資料的可用性，而定位的準確性與所需花費的成本也為其最關鍵的問題。
就目前定位計算的分類大致可以分為兩類: Statistics-based與AI-based。Statistics- based的方法計算較為簡單，但限制較多且定位的結果較不準確，如Kalman filter。而AI-based則反之，雖然計算較為複雜，但卻有限制少與高準確率的優點，如PSO、Neural Network。在AI的演算法中，我們主要評估不同Neural Network定位方法間彼此的差異性，根據定位方法的不同，NN的輸入也將有所差異，這樣的差異也將使得效能有所分別。文中除了比較NN定位方法間的差異外，我們還納入了PSO-based定位方法以評估不同AI間的區別。
對於WSN而言，除了要有好的效能外，成本也是非常重要的部分，若是沒有將成本與效能做一個平衡，將使得WSN壽命減少亦或參考資料價值不足。
為此，我們以不增加額外成本的前提下提出了一個運用NN-based的定位方法，新方法運用Online的訓練方式使得訓練出來的網路模型與拓墣呈正相關，在訓練時我們所納入的訓練組為拓墣全部可能出現的情形，亦即全拓墣式的訓練組，Online的訓練方式與全拓墣式的訓練組將使得我們所訓練出來的網路模型與拓墣是完全相關。為了使效能更加增進，我們提出了結合RSSI與hop count兩種測距使得測距可以更加精準，而在網路模型輸入的部分，我們也將其做倒數的處理使其具有權重，結合兩種測距以及權重的概念將使得我們可以在不增加成本的前提下，擁有更佳的效能。

Wireless Sensor Network is used mainly in regional data collection, through data collection can make the operator to understand the area and make the better decisions based on the information. Although it can collect the data of the area, but for the certain tasks, it must understands the location of each sensor, therefore, the sensors must be located to increase the availability of information, the accuracy of location and the cost are the most critical issues.
The classification of the current location calculation can be divided into two categories: Statistics-based and AI-based. The calculation of statistics-based method is simple, but it is more restrictive and inaccurate location, such as Kalman filter. The AI-based is contrary, although the calculation is more complex, but the limits are few and the accuracy is high, such as PSO and Neural Network. In the AI algorithms, we evaluate mainly the different location methods of Neural Network, according to the different location methods, input of Neural Network will be different, there will cause the performance difference. The paper in addition to compare the different between Neural Network location methods, we also included a PSO-based location method to evaluate the different between different AI.
For WSN, in addition to have a good performance, cost is also a very important part, if there is no balance of cost and performance, it will cause the reference value of location is not enough and life reduced of WSN.
We premise a location method of NN-based without additional cost, new method uses online training method to cause the trained network model correlated with the topology, we included all possible scenarios in topology to our training data, this mean the topology will be training data, online training method and topology training data will make our trained network model is completely relevant with topology. In order to improve the performance, we propose the estimate distance that combine two kinds estimate distance of RSSI and hop count to make more accurate, in the input part of network model, we also do the inverse cause the inputs have weight, combining two estimate distance and the concept of weight will cause the method have the better performance without addition cost.

第一章、緒論	1
1.1、前言	1
1.2、章節架構	4
第二章、相關研究背景	5
2.1、無線感測網路簡介	5
2.2、無線定位系統	9
2.3、無線測距技術	12
2.4、運用Statistics-based定位	17
2.4.1、Kalman filter定位	17
2.5、運用AI-based定位	22
2.5.1、PSO-based定位	22
2.5.2、NN-based定位	28
第三章、現有AI-based定位之評估	43
3.1、AI-based定位之研究動機	43
3.2、現有AI-based定位之評估	45
第四章、我們提出的新方法	49
4.1、新方法的研究動機	49
4.2、新方法的運作過程	53
4.3、新方法的成本與效能評估	60
4.3.1、模擬參數	60
4.3.2、總節點數變化與定位誤差之評估	64
4.3.3、錨節點百分比與定位誤差之評估	66
4.3.4、RSSI取樣次數與定位誤差之評估	67
4.3.5、RSSI標準差與定位誤差之評估	69
4.3.6、稀疏節點的定位成功率	70
4.3.7、RSSI樣本為10之評估	72
4.3.8、成本評估	75
4.3.9、綜合評比	79
第五章、結論	81
第六章、參考文獻	85


圖目錄
圖1. 感測器基本元件	6
圖2. 三點定位機制	10
圖3. 多點定位機制	10
圖4. 三角定位機制	11
圖5. 卡爾曼濾波器流程	18
圖6. 卡爾曼濾波器模型	19
圖7. 均數0、變異數5的高斯隨機變數分布圖	20
圖8. PSO定位方法MODE2	28
圖9. NEURAL NETWORK網路模型	30
圖10.  SUBBEACON搜尋方式	40
圖11. VN與SUBBEACON關係圖	47
圖12. 新方法測距修正	56
圖13. 新方法之訓練組產生演算法	59
圖14. 總節點數變化與定位誤差之評估	64
圖15. 錨節點百分比與定位誤差之評估	66
圖16. RSSI取樣次數與定位誤差之評估	67
圖17. RSSI標準差與定位誤差之評估	69
圖18. 稀疏節點的定位成功率	70
圖19. 總節點數變化與定位誤差之評估(RSSI樣本為10)	74
圖20. 錨節點百分比與定位誤差之評估(RSSI樣本為10)	74
圖21. RSSI標準差與定位誤差之評估(RSSI樣本為10)	74
圖22. 稀疏節點的定位成功率(RSSI樣本為10)	74
圖23. 節點至SINK所需經過的平均HOP COUNT	75


表目錄
表1. COMPARISON OF LOCALIZATION ERRORS (CM)	44
表2. 拓樸模擬參數	61
表3. PSO參數設定	61
表4. DANA ET AL.參數設定	62
表5. BP、VNBP 參數設定	62
表6. 新方法的參數設定	63
表7. 成本評估	76
表8. 定位方法綜合評比	80

[1] R. E. Kalman, “A New Approach to Linear Filtering and Prediction Problems,” Transaction of the ASME-Journal of Basic Engineering, 1960, pp. 35-45.
[2] A. Dana, A. K. Zadeh and B. Hekmat, “Localization in Ad-Hoc networks,” Proceedings of the IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, May 2007.
[3] P.-J. Chuang and C.-P. Wu, “An Effective PSO-based Node Localization Scheme for Wireless Sensor Networks,” Proceedings of the 9th International Conference on Parallel and Distributed Computing, Applications and Technologies, Dec. 2008, pp. 187-194. 
[4] S. K. Chenna, Y. K. Jain, H. Kapoor, R. S. Bapi, N. Yadaiah, A. Negi, V. Seshagiri Rao and B. L. Deekshatulu. “State estimation and tracking problems: A comparison between Kalman filter and recurrent neural networks,” In International Conference on Neural Information Processing, 2004, pp. 275--281.
[5] A. Shareef, Y. F. Zhu, M. Musavi and B. Shen, “Comparison of MLP neural network and kalman filter for localization in wireless sensor networks,” Proceedings of the 19th IASTED International Conference on Parallel and Distributed Computing and Systems, 2007, pp. 323--330. ACTA Press.
[6] J. Kennedy and R. Eberhart, “Particle swarm optimization,” Proc. IEEE International Conf. on Neural Networks (Perth, Australia), IEEE Service Center, 1995, Piscataway, NJ.
[7] R. C. Eberhart, J. Kennedy, “A new optimizer using particle swarm theory,” Proc. Sixth International Symposium on Micro Machine and Human Science, IEEE Service Center, 1995, Piscataway, NJ, 39-43.
[8] Q. Huang, J. Cukier, H. Kobayashi, B. Liu and J. Zhang, “Fast authenticated key establishment protocols for self-organizing sensor networks,” In 2nd ACM international conference on Wireless Sensor Networks and Applications, 2003.
[9] E. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numeriche Mathematics, 1959, vol 1, pp. 269-271.
[10] R. Liu, K. Sun and J. Shen, “BP Localization Algorithm Based on Virtual Nodes in Wireless Sensor Network,” Wireless Communications Networking and Mobile Computing (WiCOM) 6th International Conference on, 2010. 
[11] D. A. Tran, T. Nguyen, “Localization In Wireless Sensor Networks Based on Support Vector Machines,” Parallel and Distributed Systems, IEEE Transactions on, 2008, vol 19, issue 7, pp 981 - 994. 
[12] A. Shareef, Y. Zhu and M. Musavi, “Localization using neural networks in wireless sensor networks,” Proceedings of the 1st international conference on MOBILe Wireless MiddleWARE, Operating Systems, and Applications. ICST, 2007, pp. 1-7.
[13] M. S. Rahman, Y. Park and K. D. Kim, “Localization of Wireless Sensor Network using artificial neural network,” International Symposium on Communications and Information Technology, 2009, pp. 639 - 642.  
[14] M. Yin, J. Shu, L. Liu and H. F. Zhang, “The Influence of Beacon on DV-HOP in Wireless Sensor Networks,” GCCW’06 Fifth International Conference on Grid and Cooperative Computing Workshops, 2006, pp. 459-462.
[15] J. Schmid, M. Volker, T. Gadeke, P. Weber, W. Stork and K. D. Muller-Glaser, “An approach to infrastructure-independent person localization with an IEEE 802.15.4 WSN,” Indoor Positioning and Indoor Navigation (IPIN), 2010 International Conference on.
[16] R. Luo, W. L. Hsu, O. Chen and S. K. Huang, “Mobile Sensor Node Localization and Path Planning for Ubiquitous Service,” Proceedings of the IEEE International Conference on Mechatronics and Automation, August 2009, Changchun, China.
[17] N. Kitakoga, T. Ohtsuki, “A Localization Algorithm for Nonuniform
Propagation Environments in Sensor Networks,” Proceedings of 18th Internatonal Conference on Computer Communications and Networks, 2009.
[18] R. Luo, W. L. Hsu, O. Chen and S. K. Huang, “Localization based on magnetic and RSS data fusion with covariance intersection for mobile sensor network,” IEEE/ASME international conference on Advanced intelligent mechatronics, Sept. 2007, pp. 1 - 6.
[19] G. Mao, B. D. O. Anderson and B. Fidan, “Online calibration of path loss exponent in wireless sensor networks,” IEEE, GLOBECOM '06, Global Telecommunications Conference, Dec. 2006, pp. 1 - 6.
[20] T. Stoyanova, F. Kerasiotis, K. Efstathiou and G. Papadopoulos, “Modeling of the RSS Uncertainty for RSS-Based Outdoor Localization and Tracking Applications in Wireless Sensor Networks,” Fourth International Conference on Sensor Technologies and Applications, July 2010, pp. 45-50.
[21] X. Bao, F. Bao, S. Zhang and L. Liu, “An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks,” 6th International Conference on Wireless Communications Networking and Mobile Computing (WiCOM),Sept. 2010, pp.1-4.
[22] K. Liu, X. Yan and F. Hu, “A modified DV-Hop localization algorithm for wireless sensor networks,” IEEE International Conference on Intelligent Computing and Intelligent Systems, Nov. 2009, vol 3, pp. 511.
[23] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “A Survey on Sensor Networks,” in Proc. IEEE Communications Magazine, Aug. 2002, Vol. 40, No. 8, pp. 102-113.
[24] Q. Jiang, D. Manivannan, “Routing protocols for sensor networks,” IEEE Consumer Communications and Networking Conference, Jan. 2004, pp.93-98.
[25] S. Capkun, M. Hamdi and J. P. Hubaux, “GPS-free positioning in mobile ad-hoc networks,” 34th IEEE Hawaii Int. Conf. Systems Science, Jan. 2001.
[26] J. Hightower and G. Borriello, “Location systems for ubiquitous computing,” IEEE Computer, Aug. 2001, Vol. 34, pp. 57–66.
[27] K. F. Ssu, C. H. Ou and H. C. Jiau, “Localization with mobile anchor points in wireless sensor networks,” IEEE Trans. on Vehicular Technology, May 2005, Vol. 54, pp. 1186–1197.
[28] A. Boukerch, H. A. B. F. Oliveira, E. F. Nakamura and A. A. F. Loureiro, “Localization systems for wireless sensor networks,” IEEE Wireless Communications, Dec. 2007, Vol.14, No.6, pp. 6-12.
[29] V. Ramadurai, M.L. Sichitiu, “Localization in wireless sensor networks: a probabilistic approach,” in Proceedings of ICWN, June 2003..
[30] N. Patwari, J. N. Ash, S. Kyperountas, A. O. Hero III, R. L. Moses and N. S. Correal, “Locating the nodes: cooperative localization in wireless sensor networks,” IEEE Signal Processing Magazine, Jul. 2005, Vol. 22, No. 4, pp.54-69.
[31] S. Gezici, Z. Tian, G. B. Giannakis, H. Kobayashi, A. F. Molisch, H, V. Poor and Z. Sahinoglu, “ Localization via ultra-wideband radios: a look at positioning aspects for future sensor networks,” IEEE Signal Processing Magazine, July 2005, Vol. 22, pp. 70-84.
[32] T. S. Rappaport, “Wireless Communications: Principles and Practice,” Prentice Hall Inc., 2nd edition, 2001.
[33] CC2420: 2.4 GHz IEEE 802.15.4 / Zigbee RF Transceiver, Chipcon
AS SmartRFR CC2420 Preliminary Datasheet (rev 1.0), 2003-11-17.
[34] A. Awad, T. Frunzke and F. Dressler, “Adaptive Distance Estimation and Localization in WSN using RSSI Measures,” 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools, Aug. 2007, pp. 471-478.
[35] M. N. Borenovic, A. M. Neskovic, “Comparative analysis of RSSI, SNR and Noise level parameters applicability for WLAN positioning purposes,” IEEE EUROCON '09, May 2009, pp. 1895-1900.