近年來，定位一直是多項應用科技所渴望的技術。由於監測環境大小不一，不可避免地需要佈置多個感測器節點，並將訊息以路由的方式漸漸傳到資料蒐集的位置，無線感測器網路對於上述的要求是一項非常好的選擇。然而過去的無線感測器網路定位系統多半需要事先裝設位置已知的節點當作參考點來定出其他待測節點的位置，而此類系統架設往往過於麻煩，在很多情況下使用者並不會想要去使用。例如該定位系統需要時常換不同場地，如果已知參考點的部署過於複雜，使用者每次使用時會因為花很長一段時間去佈置並且紀錄各個參考點的位置而覺得並不人性化。因此，最理想的無線感測器網路定位系統是可以讓使用者任意放置感測器節點，該系統就能自行計算出節點間的相對位置，再進一步地定出其他待定位目標。
此論文提供一種能讓使用者隨機佈置感測器節點，不需要事先佈置任何位置已知的位置參考點，且這些節點會自行將它們自己的相對位置定出來。除此之外，此篇論文僅僅使用收到的訊號強度指標 (Received Signal Strength Indicator，簡稱RSSI)當作輸入訊號，節點本身並沒有任何事先已知的絕對座標或是相對座標。
此篇論文設計的中心概念：距離越遠的節點訊號越弱，距離越近的節點訊號越強。由於訊號強度和距離的關係式並不是固定的，因此並無法藉由訊號強度直接反算出距離來，但可以肯定的是藉由上述距離越遠則訊號越弱的概念，可以讓節點彼此測試和不同節點間的訊號強弱關係，藉此判定出不同節點之間的遠近關係。最後由遠近的相對關係可以完成整張不同節點的位置相對關係圖。此論文將會詳細介紹演算法和最後實驗的結果。

In the past few years, localization technology has gained more and more attentions. Wireless sensor network is one of best solutions since nodes can be easily distributed around monitored environment and relay the required sensors information. Most methods require a pre-built infrastructure with anchor nodes, whose positions are known, to locate the blind nodes (unanchored nodes). These kinds of methods would take user much time to construct the system. For example, if user wants to move the locating system from one place to another, user should re-build all the anchor nodes due to the different environment. The most ideal method is to let user randomly distribute all the nodes and they will be located automatically.
In this thesis, a relative-localization identification of random deployed non-anchored nodes will be presented. Based on relative RSSI information, the system can identify which sensor nodes are placed in locations that are planned on the map. The method can let user put any nodes anywhere (random distributed), and the nodes will locate themselves without knowing the coordinate (absolute or relative) beforehand.
The main idea of this paper is: “Further nodes would get weaker signal strength, and vice versa.” Because the relationship between RSSI value and distance is not always fixed, the RSSI can not be transformed to distance directly. Nevertheless, we still can use the RSSI value to know which node is closer and which is further by the idea mentioned above. The distance relationship can draw the map which includes the relative locations of all the nodes. The algorithm and experimental verification of this method will all be detailed in this paper.

謝誌 ...........................................i
中文簡介 .........................................iii
Abstract ..........................................iv
目錄 ...........................................v
圖目錄 ........................................viii

第一章、 無線感測器網路緒論 .........................1
1.1. 無線感測器網路簡介 .........................1
1.2. 各章節介紹 ..................................4

第二章、 研究背景與動機 .........................5
2.1. 無線感測器網路概論 .........................5
2.2. 研究動機 ..................................7
2.3. 無線感測器網路相關定位方法 ................8
2.3.1. 所使用的實體測量方式： ................9
2.3.2. 各種定位技術： ........................10

第三章、 系統程式與硬體 ........................17
3.1. 系統架構 .................................17
3.2. 內部程式相關 .................................19
3.2.1. 網路封包格式 ........................19
3.2.2. 各種節點內部程式 ........................21
3.2.3. 頻寬分配方式──以時間來分配頻寬 ..... 24
3.3. 使用到的硬體介紹： ........................25
3.4. 使用到的軟體介紹： ........................28
第四章、 單次快速定位法與使用者修正 ...............31
4.1. 實驗架設 .................................31
4.2. 單次快速定位法 ........................32
4.2.1. 方法 .................................32
4.2.2. 虛擬距離 .................................35
4.2.3. 整體執行結果 ........................35
4.3. 使用者已知節點輪廓概況而未知每個節點詳細位置.37
4.4. 誤差探討 .................................40
4.5. 定位法改善和修正結果 ...............45
4.5.1. 定位法改善 .................................45
4.5.2. 修正結果討論 ........................47
4.6. 小結 .................................48

第五章、 以粒子過濾為概念設計的定位方式 ......49
5.1. 傳統粒子過濾(Particle filter)簡介 ......49
5.2. 此篇定位條件和傳統粒子過濾的相同相異點以及可取之處 ..........................................53
5.3. 以粒子過濾為概念設計的方法 ...............54
5.4. 實驗結果 .................................72
5.4.1. 六點定位(一) ........................72
5.4.2. 六點定位(二) ........................73
5.4.3. 局部數據錯誤所造成的影響 ...............74
5.4.4. 在不同隔間分佈節點(一) ...............75
5.4.5. 在不同隔間分佈節點(二) ...............77
5.5. 使用者已知節點輪廓概況而未知每個節點詳細位置..80
5.5.1. 修改部分 ..................................80
5.5.2. 在不同隔間分佈節點(一) ................81
5.5.3. 在不同隔間分佈節點(二) ................82
5.6. 多次疊代穩定度測試 .........................84
5.7. 小結 ..................................86

第六章、結論與未來展望 .........................87
6.1. 結論： ..................................87
6.2. 未來展望 ..................................89

參考文獻 ...........................................90
附錄 ...........................................95

[1] Kahn, J.M., R.H. Katz, and K.S.J. Pister, 『Mobile Networking for Smart Dust』, ACM/IEEE Intl. Conf. on Mobile Computing and Networking (MobiCom 99). Seattle, WA, Pages:271-278. 1999.

[2] Rabaey, J.; Ammer, J,; da Silva,J.L., Jr.; Patal, 『PicoRadion: Ad-hoc wireless networking of ubiquitous low-energy sensor/monitor nodes』, VLSI, 2000. Proceedings. IEEE Computer Society Workshop, Pages.9-12. December, 2000.

[3] Levis, P. and Culler, 『A tiny virtual machine for sensor networks』, Proc. of the 10th Inter. Conference on Architectual Support for Programming Languages and Operating Systems (ASPLOS-X), Vol. 37, 30, 36, Issue 10, 5, 5, Pages.85-95. December, 2002.

[4] Madden, S.R., Franklin, M. J., Hellerstein, J. M., and Hong, 『TinyDB: an acquisitional query processing system for sensor networks』, ACM Trans. Database Syst. 30, 1(Mar. 2005), Pages.122-173. 2005.

[5] ZigBee全球網, 『ZigBee前景撲溯迷離，巨頭熱情仍不減』, (http://www.51zigbee.com/Article/ShowArticle.asp?ArticleID=282)

[6] Kate Greene, 『A wireless-sensor network to report pollution and traffic comes to Cambridge, MA.』, Technology Review, Published by MIT. April, 2007.
(http://www.technologyreview.com/communications/18533/?a=f)

[7] Darko Muˇsicki, Member, IEEE, Regina Kaune, and Wolfgang Koch, Senior Member, IEEE, 『Mobile Emitter Geolocation and Tracking Using TDOA and FDOA Measurements』, IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 58, NO. 3, Pages: 1863 - 1874 . MARCH 2010

[8] Nikolas Kantas, Sumeetpal S. Singh, Arnaud Doucet, 『DISTRIBUTED SELF LOCALISATION OF SENSOR NETWORKS USING PARTICLE METHODS』, Nonlinear Statistical Signal Processing Workshop, 2006 IEEE, Pages: 164 – 167. 13-15 September. 2006

[9] Guerrero, E. ; Xiong, H.G. ; Gao, Q., 『A Range-Free Localization Algorithm for Wireless Sensor Networks Based on Unmanned Aerial Vehicles』, Networked Digital Technologies, 2009. NDT ''09. First International Conference, IEEE, Pages:267-273, 28-31 July 2009 .

[10] Ali Ozer Ercan, Abbas El Gamal, Leonidas J. Guibas , 『Object Tracking in the Presence of Occlusions via a Camera Network』, ACM: Association for Computing Machinery, Pages: 509 -518, 2007

[11] Huang Lee; Dong, H.; Aghajan, H.,『Robot-Assisted Localization Techniques for Wireless Image Sensor Networks』, Sensor and Ad Hoc Communications and Networks, 2006. SECON ''06. 2006 3rd Annual IEEE Communications Society on Volume 1, Pages:383 – 392, 28 Sept. 2006



[12] Ying-Hong Wang, Chien-Min Lee, Wei-Ting Chen, and Chieh-Hsin Kuo, 『Location Estimation with Mobile Nodes in Wireless Sensor Networks』, Springer-Verlag Berlin Heidelberg, Ubiquitous Intelligence and Computing , Volume 4611/2007 . Pages:720-729. 2007.

[13] McGillem, C.D., Rappaport, T.S., 『A Beacon Navigation Method for Autonomous Vehicles』Vehicular Technology, IEEE Transactions on Volume 38, Issue_3, Pages:132 – 139. Aug. 1989.

[14] UBEC Corp,『U-Force Module Application Note AN-2400-12』

[15] M. Chen and M. L. Fowler, 『Geometry-adaptive data compression
for TDOA/FDOA location [wireless sensor network applications]』 IEEE Int. Conf. Acoust., Speech Signal Process, Philadelphia, PA, Vol. 4, Pages: iv/1069 - iv/1072. March 2005.

[16] H. Wei, C. Xia, and S. Ye, 『Motion detection using Rao test in dual satellite geolocation system』 in 8th Int. Conf. Signal Process., Beijing, Vol 4,
China, Nov. 2006.

[17] G. Yao, Z. Liu, and Y. Xu, 『TDOA/FDOA joint estimation in a correlated noise environment』 in IEEE Int. Symp. Microwave, Antenna,
Propagation EMC Technol. Wireless Commun., Beijing, China, Vol. 1, Pages: 831 - 834 Aug. 2005.


[18] Wei Zhuang, Guangming Song， Jindong Tan， Aiguo Song, 『Localization for Hybrid Sensor Networks in Unknown Environments Using Received Signal Strength Indicator』, Proceedings of the 2008 IEEE International Conference on Information and Automation, Zhangjiajie, China, Pages: 567 - 572 , June 20 -23, 2008

[19] Jang-Ping Sheu, Jian-Ming Li, Chih-Shun Hsu, 『A Distributed Location Estimating Algorithm for Wireless Sensor Networks』, IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing, Volume: 1. 2006

[20] Stefano Tennina , Marco Di Renzo , Fabio Graziosi , Fortunato Santucci, 『Locating ZigBee Nodes Using the TI ’s CC2431 Location Engine: A Testbed Platform and New Solutions for Positioning Estimation of WSNs in Dynamic Indoor Environments』, Co-Located with the fourteenth annual intenational conference on mobile computing and networking, Pages: 37-42. 2008.

[21] Santiago Mazuelas, Alfonso Bahillo, Ruben M. Lorenzo, Patricia Fernandez, Francisco A. Lago, Eduardo Garcia, Juan Blas, and Evaristo J. Abril, 『Robust Indoor Positioning Provided by Real-Time RSSI Values in Unmodified WLAN Networks』, IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, VOL. 3, NO. 5 , Pages: 821 – 831. OCTOBER 2009



[22] Boon-Giin Lee, Young-Sook Lee and Wan-Young Chung,『3D Map Visualization for Real Time RSSI Indoor Location Tracking System on PDA』, Third International Conference on Convergence and Hybrid Information Technology, Pages: 375 - 381. 2008.

[23] Neal Patwari, Alfred O. Hero, III, Matt Perkins, Neiyer S. Correal, and Robert J. O’Dea,『Relative Location Estimation in Wireless Sensor Networks』, IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 51, NO. 8., AUGUST 2003

[24] Chia-Hung Chang and Wanjinn Liao,『Revisiting Relative Location Estimation in Wireless Sensor Networks』, Communications, 2009. ICC ''09. IEEE International Conference on ,14-18 , Pages: 1 – 5, June 2009

[25] Mohammad Shaifur Rahman, Youngil Park, and Ki-Doo Kim,『Relative Location Estimation of Vehicles in Parking Management System』, Advanced Communication Technology, 2009. ICACT 2009. 11th International Conference on 15-18, Pages: 729 – 732, Feb. 2009

[26] Ahmed, N; Rutten, M; Bessell, T; Kanhere, S; Gordon, N; Jha, S,『Detection and Tracking Using Wireless Sensor Networks』, Mobile Computing, IEEE , Pages: 1 - 1, 2010