近年來無線感測器網路（Wireless Sensor Networks, WSNs）被廣泛地運用在現實生活中，路由(Routing)問題一直是無線感測器網路中學者們討論的熱門議題，為了兼顧體積小、成本低且結構簡單等特性，如何有效且迅速地將無線感測器節點（Wireless Sensor Node）偵測到的資料回傳給資料收集節點（Sink Node）即為其中之一。先前的研究中，大多數是使用地理路由（Geographic Routing）來解決這個問題，但是使用地理路由必須知道自己的位置資訊，也需要知道一步鄰居（One Hop）和目的地節點的地理位置資訊，一般是使用全球衛星定位系統（Global Positioning System, GPS）來獲得，但是使用全球衛星定位系統會增加成本及耗電量，使得無線感測器網路的生命週期縮短。所以本文探討在隨機分佈無線感測器節點的網路中，不使用全球衛星定位系統，而是由資料收集節點開始去建立虛擬座標系統（Virtual Coordinate System, VCS），藉由虛擬座標系統找到位於場景中四個邊界極值的節點當作虛擬錨點，虛擬錨點再與資料蒐集節點建立最短路徑，以便代傳資料，進而建立一個低耗能、延長整體網路生命週期、有效率的傳輸以及可容錯的路由機制。

In recent years, wireless sensor networks are widely used in many areas.  How to collect information efficiently and deliver to base station reliably among the hot topics in wireless sensor networks.  Most of the previous studies used the Geographic routing to resolve this problem.  Sensors have to know not only their location information, but also one hop neighbor and destination location information.  Generally, the Global Positioning System (GPS) provides location and time information, but it will increase the cost, power consumption, and reduce the lifetime of wireless sensor network.  In this paper, we propose a Virtual Coordinate System (VCS) start from sink to replace GPS.  With the VCS, WSNs can find the four extreme nodes in the scene boundary as virtual anchor nodes.  Then, a shortest path between virtual anchor nodes and sink for transfer data in the random distribution wireless sensor network is created. In this approach, establish a low-power, extend the network lifetime, efficient and fault-tolerant routing mechanism.

目錄	III
圖目錄	V
表目錄	VII
第一章　緒論	1
1-1研究背景	2
1-2研究動機	5
1-3研究目的	7
1-4論文架構	8
第二章　相關技術與研究	9
2-1 LEACH	13
2-2 TTDD	16
2-3 Anchor Node Based Sink Location Dissemination Scheme for Geographic Routing	18
第三章　虛擬錨點座標路由機制	21
3-1網路環境與假設	22
3-2建立虛擬座標及尋找虛擬錨點階段	25
3-3建立虛擬錨點與資料收集節點路徑	33
3-4建立資料傳送路徑	37
3-5解決空洞問題	38
3-6尋找替代的虛擬錨點或路徑節點	40
3-7虛擬錨點座標路由機制之特性	44
第四章　模擬比較與分析	45
4-1模擬環境	46
4-2模擬結果與分析比較	47
第五章　結論與未來研究方向	53
5-1結論	53
5-2未來研究方向	54
參考文獻	55
附錄-英文論文	63

圖目錄
圖2-1：泛播式架構示意圖	10
圖2-2：鏈結式架構示意圖	11
圖2-3：叢集式架構示意圖	11
圖2-4：樹狀式架構示意圖	12
圖2-1-1：LEACH的叢集架構示意圖	13
圖2-2-1：TTDD網格架構示意圖	16
圖2-3-1：Anchor Node Based Sink Location Dissemination Scheme for Geographic Routing架構示意圖	19
圖3-1-1：無線感測器節點的傳輸範圍	23
圖3-1-2：無線感測器節點的優先權示意圖	23
圖3-2-1：無線感測器節點朝優先權1發送信標封包	26
圖3-2-2：比對錨點之程式碼	28
圖3-2-3：A在優先權1找不到其他無線感測器節點	28
圖3-2-4：A切換到優先權2尋找到無線感測器節點D和E	29
圖3-2-5：無線感測器節點優先權組切換狀態	30
圖3-2-6：建立虛擬座標及尋找虛擬錨點階段的流程圖	32
圖3-3-1：無線感測器網路中錨點座標示意圖	33
圖3-3-2：執行完建立虛擬錨點與資料收集節點路徑示意圖	35
圖3-3-3：建立虛擬錨點與資料收集節點路徑的流程圖	36
圖3-5-1：建立資料傳送路徑及解決空洞問題的流程圖	39
圖3-6-1：低電量之無線感測器節點發送低電量訊息示意圖	41
圖3-6-2：朝第一相鄰節點發送尋找新錨點示意圖	42
圖3-6-3：尋找替代的虛擬錨點或路徑節點流程圖	43
圖4-2-1：網路中控制訊息封包數量和時間的關係圖	47
圖4-2-2：無線感測器節點的能量消耗和時間關係圖	49
圖4-2-3：單位時間內事件發生數傳送到資料收集節點的比較圖	51

表目錄
表3-2-1：ANS封包	25
表3-2-2：最後紀錄封包（Final_Coor）	31
表3-3-1：路徑連結封包（Path_Link）	34
表3-5-1：救援封包（Rescue）	38
表3-6-1：低電量訊息（Low_Energy Message）	41
表3-6-2：尋找新錨點（New_Anch Message）	42

[1]	I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "Wireless sensor networks: a survey," Computer Networks, vol. 38, pp. 393-422, January 2002.
[2]	J. N. Al-Karaki and A. E. Kamal, "Routing techniques in wireless sensor networks: a survey," IEEE Wireless Communications, vol. 11, pp. 6-28, December 2004.
[3]	B. P. Crow, I. Widjaja, L. G. Kim, and P. T. Sakai, "IEEE 802.11 Wireless Local Area Networks," IEEE Communications Magazine, vol. 35, pp. 116-126, September 1997.
[4]	A. Ghosh, D. R. Wolter, J. G. Andrews, and R. Chen, "Broadband wireless access with WiMax/802.16: current performance benchmarks and future potential," IEEE Communications Magazine, vol. 43, pp. 129-136, February 2005.
[5]	"Adjustments to standard delay WiMax certification," IT Professional, vol. 8, pp. 11-15, February 2006.
[6]	A. Ghosh, R. Ratasuk, B. Mondal, N. Mangalvedhe, and T. Thomas, "LTE-advanced: next-generation wireless broadband technology [Invited Paper]," IEEE Wireless Communications, vol. 17, pp. 10-22, June 2010.
[7]	P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot, "Optimized link state routing protocol for ad hoc networks," Proceedings of IEEE International Multi Topic Conference, 2001. INMIC., pp. 62-68, December, 2001.
[8]	J. M. Kahn, R. H. Katz, and K. S. J. Pister, "Next century challenges: mobile networking for “Smart Dust”," Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, Seattle, Washington, United States, pp. 271-278, August, 1999.
[9]	I. F. Akyildiz, S. Weilian, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Communications Magazine, vol. 40, pp. 102-114, August 2002.
[10]	C.-Y. Chang, L.-L. Hung, Y.-C. Chen, and M.-H. Li, "On-supporting energy balanced k-barrier coverage in wireless sensor networks," Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing: Connecting the World Wirelessly, Leipzig, Germany, pp. 274-278, 2009.
[11]	Y.-L. Wen and C.-N. Huang, "A WSN-based Low-Power Self-health Management System," CCL Technical Journal, pp. 97-102, February 2010.
[12]	L. Dan, K. D. Wong, H. Yu Hen, and A. M. Sayeed, "Detection, classification, and tracking of targets," IEEE Signal Processing Magazine, vol. 19, pp. 17-29, March 2002.
[13]	C. Meesookho, S. Narayanan, and C. S. Raghavendra, "Collaborative classification applications in sensor networks," Proceedings of Sensor Array and Multichannel Signal Processing Workshop Proceedings, 2002., pp. 370-374, Aguest, 2002.
[14]	T. Arampatzis, J. Lygeros, and S. Manesis, "A Survey of Applications of Wireless Sensors and Wireless Sensor Networks," Proceedings of IEEE International Symposium on Intelligent Control & 13th Mediterranean Conference on Control and Automation, 2005., pp. 719-724, June, 2005.
[15]	F. Zhao and L. Guibas, Wireless Sensor Networks: An Information Processing Approach: Morgan Kaufmann, 2004.
[16]	P. Liu, X. Zhang, S. Tian, Z. Zhao, and P. Sun, "A Novel Virtual Anchor Node-Based Localization Algorithm for Wireless Sensor Networks," Proceedings of the Sixth International Conference on Networking, p. 9, 2007.
[17]	Y. Fucai, C. Younghwan, K. Sang-Ha, and L. Euisin, "Anchor Node Based Sink Location Dissemination Scheme for Geographic Routing," Proceedings of IEEE Vehicular Technology Conference, 2008. VTC., pp. 2451-2455, May, 2008.
[18]	Y. Fucai, C. Younghwan, P. Soochang, L. Euisin, T. Ye, J. Minsuk, and K. Sang-Ha, "Anchor Node Based Virtual Modeling of Holes in Wireless Sensor Networks," Proceedings of IEEE International Conference onCommunications, 2008. ICC., pp. 3120-3124, May, 2008.
[19]	B. M. Shankarananda and A. Saxena, "Energy efficient localized routing algorithm for Wireless Sensor Networks," Proceedings of 3rd International Conference on Electronics Computer Technology, 2011. ICECT., pp. 72-75, April, 2011.
[20]	C. Intanagonwiwat, R. Govindan, and D. Estrin, "Directed diffusion: a scalable and robust communication paradigm for sensor networks," Proceedings of the 6th annual international conference on Mobile computing and networking, Boston, Massachusetts, United States, pp. 56-67, 2000.
[21]	Y. Jae Duck, K. Kyung Tae, J. Bo Yle, and Y. Hee Yong, "An Energy Efficient Chain-Based Clustering Routing Protocol for Wireless Sensor Networks," Proceedings of International Conference on Advanced Information Networking and Applications Workshops, 2009. WAINA., pp. 383-388, May, 2009.
[22]	L. Chiu-Kuo, L. Jian-Da, and L. Chih-Shiuan, "Steiner Points Routing Protocol for Wireless Sensor Networks," Proceedings of 5th International Conference on Future Information Technology, 2010. FutureTech., pp. 1-5, May, 2010.
[23]	F. Dressler, A. Awad, and M. Gerla, "Inter-Domain Routing and Data Replication in Virtual Coordinate Based Networks," Proceedings of IEEE International Conference on Communications, 2010. ICC., pp. 1-5, May, 2010.
[24]	H. Luo, F. Ye, J. Cheng, S. Lu, and L. Zhang, "TTDD: two-tier data dissemination in large-scale wireless sensor networks," Wirel. Netw., vol. 11, pp. 161-175, 2005.
[25]	J. J. Lotf, M. N. Bonab, and S. Khorsandi, "A Novel cluster-based routing protocol with extending lifetime for wireless sensor networks," Proceedings of 5th Wireless and Optical Communications Networks, 2008. WOCN., pp. 1-5, May, 2008.
[26]	L. Xin, W. Quanyu, and J. Xuliang, "An energy-efficient routing protocol for wireless sensor networks," Proceedings of 7th World Congress on Intelligent Control and Automation, 2008. WCICA., pp. 1728-1733, June, 2008.
[27]	Y. Zhenhua, L. Yu, and C. Yuanli, "Design of an Energy-Efficient Distributed Multi-level Clustering Algorithm for Wireless Sensor Networks," Proceedings of 4th International Conference onWireless Communications, Networking and Mobile Computing, 2008. WiCOM., pp. 1-4, October 2008.
[28]	W. B. Heinzelman, A. P. Chandrakasan, and H. Balakrishnan, "An application-specific protocol architecture for wireless microsensor networks," IEEE Transactions on Wireless Communications, vol. 1, pp. 660-670, 2002.
[29]	T. Yaling and Z. Yongbing, "Hierarchical flow balancing protocol for data aggregation in wireless sensor networks," Proceedings of Computing, Communications and Applications Conference, 2012., pp. 7-12, 11-13 Jan. 2012, 2012.
[30]	A. H. Mohajerzadeh, M. H. Yaghmaee, Z. Eskandari, and H. Deldari, "Energy efficient and congestion aware routing algorithms for Wireless Sensor Networks connected as Hypercube," Proceedings of International Symposium on Telecommunications, 2008. IST., pp. 324-329, Aguest, 2008.
[31]	L. Chiu-Kuo, L. Chih-Hsuan, and L. Jian-Da, "Steiner trees grid routing protocol in wireless sensor networks," Proceedings of IEEE International Conference on Wireless Communications, Networking and Information Security, 2010. WCNIS., pp. 473-477, June, 2010.
[32]	R. Cohen, I. Nudelman, and G. Polevoy, "On the admission of dependent flows in powerful sensor networks," Proceedings of 31th Annual IEEE International Conference on Computer Communications, 2012. INFOCOM., pp. 2336-2344, March, 2012.
[33]	T.-W. Kuo and M.-J. Tsai, "On the construction of data aggregation tree with minimum energy cost in wireless sensor networks: NP-completeness and approximation algorithms," Proceedings of 31th Annual IEEE International Conference on Computer Communications, 2012. INFOCOM., pp. 2591-2595, March, 2012.