無線感測網路主要是利用許多感測節點散佈於環境中，並利用無線傳輸的方式依據每個不同的需求因而產生不同動作。感測節點可以感測資料亦或是傳送資料給資料收集點，由於感測節點再隨機散佈的情形下，大都需要仰賴硬體設備或接收到的封包訊息，來決定感測節點的位置資訊，需要花費額外的時間與成本，而估算的節點位置可能會產生與實際位置相差很大的情況。因此，感測節點的定位問題在無線感測網路中，是一項值得探討的議題。
本篇論文提出一個在無線感測網路的定位機制。我們利用一個移動的參考節點搭載了GPS, 透過所提出的移動方式、廣播方式；並提出環境中未知感測節點的接收方式、透過訊號強度的變換計算距離的方式 (Received signal strength indicator, RSSI)。利用一個移動的參考節點，來涵蓋整個網路環境，進而降低整個需求成本、提升定位的準確度。

Wireless sensor network applications are based on monitoring or managing the sensing area by using the location information with sensor nodes. These sensor nodes are random deployed, so they have to be aware to their location before starting their tasks.
Most sensor nodes need hardware support or receive packets with location information to estimate their location, and needs lots of time or costs. It may have a huge error. In this thesis we present a localization mechanism in wireless sensor networks. This mechanism can cooperate with node localization algorithm and mobile reference node moving direction scheme. We use a mobile reference node with GPS to move to the whole environment, and we use RSSI and trilateration to estimate unknown nodes’ location. We can obtain more unknown nodes location by mobile reference node moving. It decreases the energy consumption and average location error.

目錄
第一章 緒論	1
1-1 研究背景	2
1-2 研究動機	3
1-3 研究目的	4
1-4 論文架構	5
第二章 相關技術背景	6
2-1 全球定位系統(Global Positioning System)	6
2-1-1 GPS系統	7
2-1-2 GPS的定位原理	8
2-1-3 GPS的應用	9
2-2 相關的定位距離測量技術	11
2-2-1 DV-HOP	12
2-2-2 APIT	13
2-2-3 TOA	16
2-2-4 TDOA	17
2-2-5 AOA	18
2-2-6 RSSI	20
2-3 相關定位方法敘述	21
2-3-1 Perpendicular Intersection: locating wireless sensors with mobile beacon (PI)	22
2-3-2 Location systems for ubiquitous computing (TRL)	23
2-3-3 Localization of wireless sensor networks with a mobile beacon (BI)	24
2-3-4 Localization with a Mobile Beacon Based on Geometric Constraints in Wireless Sensor Networks (MBBGC)	26
第三章 以移動參考節點為基礎透過RSSI強度和網格編號定位機制	28
3-1 虛擬網格化初始環境設定階段	31
3-2 移動參考節點廣播演算法(Mobile Reference node Broadcast Algorithm)	34
3-3 未知感測點定位演算法(Sensor node Localization Algorithm)	42
3-4 移動參考節點移動方向演算法(Mobile node moving direction Algorithm)	49
第四章 實驗與模擬	63
4-1 模擬環境	63
4-2 定位誤差率模擬結果的比較與分析	64
4-3 移動參考節點電能消耗模擬結果的比較與分析	68
4-4 未知感測節點模擬結果的比較與分析	70
第五章 結論與未來研究方向	72
5-1 結論	72
5-2 未來研究方向	73
參考文獻	74
附錄 中文投稿格式	78
附錄 英文投稿格式	88

圖目錄
圖2.1 GPS接收器透過衛星定位	9
圖2.2 DV-Hop 範例圖	12
圖2.3 APIT概要示意圖	14
圖2.4 APIT感測器節點知道區域交集方法示意圖	14
圖2.5 感測器節點在三角形內範例圖	15
圖2.6 感測器節點在三角形外範例圖	15
圖2.7 TOA概要示意圖	17
圖2.8 TDOA概要示意圖	18
圖2.9 AOA概要示意圖	19
圖2.10 三點定位法的概要示意圖	20
圖2.11 Perpendicular Intersection方法示意圖	22
圖2.12 Perpendicular Intersection移動方式	23
圖2.13 TRL 參考節點部屬示意圖	24
圖2.14 BI 移動節點移動示意圖	25
圖2.15 未知感測節點接收方式	25
圖2.16 未知感測節點接收到的訊號位置	26
圖2.17 接收到移動節點訊號之間的相交位置	27
圖3.1 Grid-based Mobile Sensor Node Localization Mechanism	30
圖3.2 Mobile reference node 與 Sink的初始位置	32
圖3.3 k值為奇數的情況，t為False	33
圖3.4 k值為偶數的情況，t為True	34
圖3.5 單一虛擬正方形的廣播方式	35
圖3.6 Mobile reference node broadcast Algorithm	38
圖3.7 Pseudo Code (Mobile reference node broadcast algorithm)	39
圖3.8 以5 * 7 為例，並用實線圓圈標出特殊的網格位置	41
圖3.9 特殊網格廣播方式	42
圖3.10 Sensor node localization Algorithm	43
圖3.11 Pseudo Code (Sensor node localization algorithm)	44
圖3.12 特殊區域(One edge situation (1))	46
圖3.13 特殊區域(One edge situation (2))	47
圖3.14 特殊區域(Two edges situation)	47
圖3.15 特殊區域(No edge situation)	48
圖3.16 Mobile reference node moving direction scheme	50
圖3.17 Mobile reference node moving direction for even algorithm	50
圖3.18 Pseudo Code (Mobile reference node moving direction for even algorithm)	51
圖3.19 Mobile reference node moving direction for odd algorithm	51
圖3.20 Pseudo Code (Mobile reference node moving direction for odd algorithm)	52
圖3.21 環境大小(p * k)為4 * 4	55
圖3.22 環境大小(p * k)為6 * 6	56
圖3.23 環境大小(p * k)為5 * 4	57
圖3.24 環境大小(p * k)為3 * 4	57
圖3.25 環境大小(p * k)為5 * 5	59
圖3.26 環境大小(p * k)為7 * 7	59
圖3.27 環境大小(p * k)為5 * 5	60
圖3.28 環境大小(p * k)為7 * 7	60
圖3.29 環境大小(p * k)為4 * 5	61
圖3.30 環境大小(p * k)為6 * 5	62
圖4.1 各未知感測節點的位置誤差	67
圖4.2 平均定位誤差率	68
圖4.3 移動節點電源消耗	69
圖4.4 未知感測節點平均電能消耗	71
 
表目錄
表3.1 開始訊號所包含的內容	36
表3.2 未知感測節點回傳封包	45
表4.1 參數設定	64
表4.2 環境大小與節點個數	65

[1] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and Cayirci E., “A survey on sensor networks, ” IEEE Communications Magazine, Volume 40, Issue 8, pp. 102-114, Aug 2002.
[2] R. Min, M. Bhardwaj, Cho Seong-Hwan, E. Shih, A. Sinha, A. Wang, and A. Chandrakasan, “Low-power wireless sensor networks,” Proceedings of the Fourteenth International Conference on VLSI Design, pp. 205-210, Jan. 2001.
[3] 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 Mag., Volume 22, Issue 4, pp. 54-69, July 2005.
[4] K. F. Ssu, C. H. Ou, and H. C. Jiau, “Localization with mobile anchor points in wireless sensor networks,” IEEE Transactions on Vehicular Technology, Volume 54, Issue 3, pp. 1187-1197, May 2005.
[5] Smart Dust: Autonomous sensing and communication in a cubic millimeter, http://robotics.eecs.berkeley.edu/~pister/SmartDust/
[6] Li Dan, K.D. Wong, Yu Hen Hu, and A.M. Sayeed, “Detection, classification, and tracking of targets,” IEEE Signal Processing Magazine, Volume 19, Issue 2, pp.17-19, Mar. 2002.
[7] Th. Arampatzis, J. Lygeros, and S. Manesis, “A Survey of Applications of Wireless Sensors and Wireless Sensor Networks,” Proceedings of the IEEE International Symposium on Mediterrean Conference on Control and Automation Intelligent Control, pp. 719-724, June 2005.
[8] W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, “An application-specific protocol architecture for wireless microsensor networks,” IEEE Transactions on Wireless Communications, Volume 1, Issue 4, pp. 660-670, Oct. 2002.
[9] Ahmed El-Rabbany, “Introduction to GPS: the Global Positioning System,” Boston: Artech House, 2002. 
[10] Global Positioning System (GPS) : http://zh.wikipedia.org/wiki/GPS
[11] T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. F. Abdelzaher, “Range-free localization schemes for large scale sensor networks,” ACM Transactions on Embedded Computing System, Volume 4, Issue 4, pp. 877–906, Nov. 2005.
[12] D. Niculescu, and B. Nath, “DV-based positioning in ad hoc networks,” Kluwer J. Telecommunications System, Volume 22, Issue 1, pp. 267–280, Jan. 2003.
[13] L. Cong, and W. Zhuang, “Hybrid TDOA/AOA mobile user location for wideband CDMA cellular systems,” IEEE Transactions on Wireless Communications, Volume 1, Issue 3, pp. 439–447, Jul. 2002.
[14] R. Yamasaki, A. Ogino, T. Tamaki, T. Uta, N. Matsuzawa, and T. Kato, “TDOA location system for IEEE 802.11b WLAN,” Proceedings of the IEEE Wireless Communications and Networking Conference, Volume 4, pp. 2338-2343, Mar. 2005.
[15] K. D. Frampton, “Acoustic self-localization in a distributed sensor network,” IEEE Sensors Journal, Volume 6, Issue 1, pp.166-172, Feb. 2006.
[16] F. Dai, and J. Wu, “Efficient broadcasting in ad hoc wireless networks using directional antennas,” IEEE Transactions on Parallel and Distributed Systems, Volume 17, Issue 4, pp. 335-347,Apr. 2006.
[17] D. Niculescu , and Badri Nath, “ Ad hoc positioning system, ” Proceedings of the IEEE Societies INFOCOM：Twenty-Second Annual Joint Conference of the IEEE Computer and Communications,” Volume 3, pp. 1734-1743, Jul. 2003.
[18] J. Hightower, G. Borriello, and R. Want, “SpotON: An indoor 3D location sensing technology based on RF signal strength,” University of Washington, Seattle, Univ. Washington, Tech. Rep. UW CSE 00-02-02, Feb. 2000.
[19] T. S. Rappaport, Wireless Communications: Principles and Practice. Englewood Cliffs, 1999.
[20] P. Angelini, F. Frati, and L. Grilli, “An algorithm to construct greedy drawings of triangulations,” Journal of Graph Algorithms and Applications, Volume 14, Issue 1, page 19-51, Jan. 2010.
[21] J. Sun, J. Yu, L. Zhu, D. Wu, and Y. Cao, “Construction of Generalized Ricci Flow Based Virtual Coordinates for Wireless Sensors Network,” IEEE Sensors Journal, Volume 12, Issue 6, pp.2109-2112, Jan. 2012.
[22] Zhongwen Guo, Ying Guo, Feng Hong, Zongke Jin, Yuan He, Yuan Feng, and Yunhao Liu, “Perpendicular Intersection: Locating Wireless Sensors With Mobile Beacon,” IEEE Transactions on Vehicular Technology,  Volume 59 ,  Issue 7, pp. 3501–3509, Sep. 2010.
[23] J. Hightower, and G. Borriello, “Location systems for ubiquitous computing,” Computer, Sponsored by IEEE Computer Society, Volume 34 ,  Issue 8, pp. 57–66, Aug. 2001.
[24] M.L. Sichitiu, and V. Ramadurai, “Localization of wireless sensor networks with a mobile beacon,” Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor Systems, pp. 174–183, Oct. 2004.
[25] Sangho Lee, Eunchan Kim, Chungsan Kim, and Kiseon Kim, “Localization with a mobile beacon based on geometric constraints in wireless sensor networks,” IEEE Transactions on Wireless Communications, Volume 8, Issue 12, pp. 5801–5805, Dec. 2009.