Wireless Sensor networks已被廣泛地應用於軍事戰略、目標追蹤及環境監測等領域。然而，在Sensor network 所佈建的環境中，常由於地形地物(如河流、峽谷) 、佈點不均、感測點毀損及外力訊號干擾等因素，使WSN中形成喪失感測能力甚至阻礙通訊的障礙區。在WSN中傳送的封包將因誤闖障礙區而造成路徑增長、耗費轉送封包之sensor 電量及增長傳送的Delay Time等問題。在本論文中，我們以主動式克服障礙物為目的，研發一Route Guiding Protocol (S-RGP)，主動的以分散式協定將障礙物資訊相對於Sensor Network予以透明化，並依障礙區的各種不同型狀設定網路的禁入區以避免封包（packet）因誤闖障礙區而造成電量消耗、頻寬浪費、delay time增加及傳輸成功率下降等問題，進而提升sensor network 中資料傳輸的效率。此外，我們亦考慮WSN中存在多個障礙物，主動導引封包避開障礙區並依最短路徑傳送至Sink，並針對障礙物可能的變化提出障礙物維護協定。實驗數據顯示，我們所提出的障礙物處理協定能有效在WSN中提供障礙物資訊並提升資料傳遞的效率。

In wireless sensor networks, a geographic region without functionality of sensing and communication can be generally treated as an obstacle, which significantly impacts the performance of existing location-based routing. The existence of an obstacle is due to unbalanced deployment, failure or power exhaustion of sensors, animus interference, or physical obstacles such as mountains or lakes. This thesis proposes a novel algorithm, namely S-RGP and M-RGP, to make existing location-based routing protocols resist obstacles. Applying the proposed S-RGP, border nodes that surround the obstacles will actively establish a forbidden region for concave obstacles and make the obstacle information transparently. Then packets will be guided to overcome the obstacle and to be moved through the shortest path from the encountered border node to the sink node. By integrating and maintaining information of multiple obstacles, the proposed M-RGP also resists multi-obstacles and enables the packets to be moved along the shortest path to the sink node. Simulation results show that the proposed protocol creates low overhead but significantly reduces the average route length and therefore improves the energy consumption and end-to-end delay for a wireless sensor network.

Contents
1、 Introduction 	 1
2、 Related Work	 4
3、 ACTIVE ROUTE GUIDING PROTOCOL	 9
A、S-RGP: Active Route Guiding Protocol for Single Obstacle	 9
B、M-RGP: Active Route Guiding Protocol for Multiple Obstacles 	20
4、 Simulation Study	29
5、 Conclusion	44
6、 References	45
7、Conference version	  A1

List of Figures
1、	Node a applies the Right-Hand Rule may guide the packet to a long routing path 	 5
2、	The major disadvantage of PAGER is that the packet can be guided  to a long routing path 	 6
3、	The S-RGP selects border and corner nodes in the first two phases
		 8
4、	The S-RGP constructs a forbidden region for each concave region  and sensors are enable to guide packets to the shortest path	 8
5、	Cases for determining ni as the border node	12
6、	The example of reducing border nodes by pruning rule 	13
7、	Illustrations of turning angles 	14
8、	An example of forbidden region construction 	16
9、	In the Packets Guiding phase, the S-RGP uses reference point Z and four extremely corner nodes to derive the best route and the packet forwarding direction	20
10、	An example that S-RGP considering single obstacle can not guide the packet transmission to the shortest route 	21
11、	The M-RGP operations for overcoming multiple obstacles 	24
12、	The single-regular obstacle with equal side lengths 	25
13、	A screenshot of S-RGP execution. The border nodes, corner nodes, extremely corner nodes, and forbidden region selected by the S-RGP
		30
14、	The scenario of WSN with single-regular-obstacle and the source sensors are located in the shadow subregions	31
15、	The comparison of S-RGP, flooding, GPSR, and PAGER mechanisms in terms of average hop count with different distribution of source sensor nodes in regions R4, R6, R7, R8 and R9.	32
16、	The comparison of average hop count of flooding, S-RGP, GPSR, and PAGER mechanisms by varying the size of single-regular-obstacle	33
17、	The control overhead of PAGER and S-RGP in different size of single-regular-obstacle 	34
18、	The comparison of PAGER and S-RGP in terms of control overhead by varying different size of concave region of single-regular-obstacle 	35
19、	A single-irregular-obstacle exists in the WSN. The comparison of flooding, S-RGP, GPSR, PAGER mechanisms in terms of average hop count by varying the distribution of source sensor nodes	36
20、	The control overhead of PAGER and S-RGP in different size of single-irregular-obstacle	37
21、	A single-irregular-obstacle exists in the WSN. The comparison of flooding, S-RGP, GPSR, PAGER mechanisms in terms of average hop count by varying the obstacle size	38
22、	The comparison of the Flooding, S-RGP, GPSR, PAGER mechanisms in terms of the remaining energy in the single-irregular-obstacle environment	39
23、	The WSN with multiple regular obstacles	40
24、	Multiple regular obstacles exist in a WSN. The comparison of flooding, M-RGP, GPSR, PAGER mechanisms in terms of average hop count by varying the obstacle size	41
25、	The control overhead of PAGER and M-RGP in different size of multiple-regular-obstacle	42
26、	The average hop count of the compared four mechanisms in different size of multiple-regular-obstacle	43
27、	The WSN contains multiple-irregular-obstacle. The comparison of M-RGP and PAGER in terms of control overhead by varying the size of obstacles	43

 
List of Tables
1、	The notations used to present the details of  M-RGP 	21

REFERENCES
[1]	I. Stojmenovic and X. Lin, “GEDIR: Loop-Free Location Based Routing in Wireless Networks,” Proceedings IASTED International. Conference on Parallel and Distributed Computing and Systems, pp. 1025-1028, Nov. 1999.
[2]	Y. B. Ko and N. H. Vaidya, “Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithm, “ IEEE Workshop on Mobile Computer Systems and Applications(WMCSA 1999), pp. 101-110,  Feb. 1999.
[3]	C. Y. Chang, C. T. Chang, S. C. Tu, “Obstacle-Free Geocasting Protocols for Single/Multi-Destination Short Message Services in Ad Hoc Networks,“ Wireless Networks, vol. 9, no. 2, pp. 143-155, March 2003. 
[4]	B. Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proceedings 6th Annual International Conference on Mobile Computing, pp. 243-254, August 2000.
[5]	L. Zou, M. Lu, and Z. Xiong, “A Distributed Algorithm for the Dead End Problem of Location Based Routing in Sensor Networks,“ IEEE Transactions on Vehicular Technology, vol. 54, no. 4, pp. 1509-1522, July 2005.
[6]	Q. Fang, J. Gao, and L. J. Guibas, ”Locating and Bypassing Routing Holes in Sensor Networks,” Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies(INFOCOM 2004), vol. 4, pp. 2458-2468, March 2004.
[7]	S. Ratnasamy, B. Karp, L. Yin, F. Yu, D. Estrin, R. Govindan, and S. Shenker, “GHT: A Geographic Hash Table for Data-Centric Storage,” Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications(WSNA 2002), Sep. 2002.
[8]	http://webs.cs.berkeley.edu/tos
[9]	H. Sabbineni and K. Chakrabarty, “Location-Aided Flooding: An Energy-Efficient Data Dissemination Protocol for Wireless Sensor Networks,” IEEE Transactions on Computers, vol. 54, no. 1, pp. 36-46, January 2005.