無線感測網路已廣泛應用於環境監控、軍事及醫療監控。根據其不同的應用與場景，在研究上急待解決的問題包括覆蓋、繞徑、定位等研究議題。位置資訊的利用在過去許多國內外的研究中一直被高度重視，位置資訊的取得與否，將影響演算法發展的難易度及效率。本論文以位置資訊的獲得程度將研究主題區分為兩大部份：(1) 在精確位置資訊的條件下，探討克障繞徑以及時間覆蓋的議題。(2) 在不精確的位置資訊的環境下，開發克障且電量平衡的繞徑協定。
在第一部份的研究主題上，本論文假設每個感測器均具有精準的位置資訊，並據此提出一新的繞徑演算法，稱為WRGP。其改善了環境中障礙物對Greedy Forwarding Routing所造成的不良影響。在運作之初，WRGP會先找出包圍障礙物四周的節點，我們稱這些節點為Border Node。隨後，位於障礙物凹洞區的節點便開始進行權重值更動的工作，利用權重值的更動，這些Border Nodes便能夠建立一禁閉區以防止封包進入凹洞區。最後，WRGP選出一些具有特殊地位的Border Nodes成為Effective Border Nodes，這些Effective Border Nodes主要用於建立一條自身至Sink的最佳封包傳送路徑。本論文所提出的WRGP不儘降低了網路初始化的通訊成本，也可利用Effective Border Nodes來導引封包至最佳的傳送路徑。此外，本論文亦提出一繞徑協定，稱為M-WRGP，以克服環境中具有多障礙物並提昇繞徑效能。
除了繞徑的議題外，我們提出了一稱為EBHMM的演算法以解決覆蓋問題。空間上的完全覆蓋其達成的條件必需要有足夠的移動式感測器以填補網路中的空洞。當網路中的感測器數量不足以填滿空洞時，移動式感測器以搬移空洞的方式將可達到時間上的覆蓋。但是若只有固定少數的感測器參與空洞搬移，則很容易造成網路節點電量不均的情況發生。在這個研究議題上，本論文以節點數不足的環境為假設場景，發展一電量平衡的空洞搬移技術，以達到時間上的完全覆蓋，並使網路生命期得以延長。
在第二個部份中，我們考慮感測節點具有不精確之位置資訊，在這種艱困的環境下，本論文的議題再度回到繞徑協定上。在傳統的繞徑協定中，尋找一條最短的傳送路徑以減少封包傳遞的時間為共同的目標。但是由於封包經常在此路徑上傳送，因此此路徑上的節點便較其他節點消耗更多的電量。另一方面，不精確的位置資訊以及障礙物的存在將導致某些繞徑協定效能降低。為解決此問題，本論文提出了一繞徑演算法，稱為JLR。JLR結合了電量平衡以及克障的功能，運作在不精確位置資訊的環境下。首先，JLR以裝載方向性天線的機器人進行定位。之後，感測器再建立緊鄰障礙物的禁閉區以防止封包進入凹洞區。

Wireless sensor networks (WSNs) have been widely applied on applications such as environment monitoring, military, and remote medical system. In the past few years, research issues including coverage, routing and localization have received much attention and required more efforts to improve the performance of existing work. The location information is a critical factor that it determines the difficulty of the algorithm design and significantly impacts their performance. Based on the different levels of obtained location information, the research issues proposed in this thesis can be categorized into two parts: (1) The issues of obstacle-resist routing protocol and temporal coverage with accurate location information; (2) The obstacle-resist and energy-balanced routing protocol with inaccurate location information. 
In the first part, this thesis proposes a novel mechanism, called WRGP, which removes the impact of obstacles on the greedy forwarding routing. The proposed WRGP initially identifies the border nodes that surround the obstacle. The border nodes in the concave region of the obstacle then initiate the weight assigning process aiming at establishing a forbidden region to prevent the packets from entering the concave region. Finally the WRGP identifies some border nodes to act as the effective border nodes for constructing the optimal routes from themselves to the sink node. The proposed WRGP reduces the control overheads and guides the packets moving along the shortest path from the encountered effective border node to the sink node. In addition, the M-WRGP is further developed to cope with the multi-obstacle problem.
In addition to the routing issue, the coverage problem is one of the most important issues in WSNs and has been widely discussed in last decade. However, the spatial full-coverage only can be achieved when the surplus mobile sensors contribute a larger coverage area than the hole size. When there is no surplus mobile sensor to cover the hole, the mobile sensor moving the hole from one location to another can achieve the purpose of temporal full-coverage. However, if only some mobile sensors participate in the hole-movement task, the WSN will be energy-unbalanced. This thesis further considers a mobile WSN that contains holes but no redundant mobile sensor exists to heal the hole. To achieve the temporal full-coverage purpose, a distributed hole-movement mechanism is proposed aiming to balance the energy consumptions of mobile sensors.
The second part of this thesis focuses on the routing issue based on the network environment where each sensor has inaccurate location information. Constructing a best route is a common goal of existing researches on the routing issue. In a WSN, the best route is the shortest path that minimizes the end-to-end delay from source to destination. However, the sensor nodes that participate in the best route might consume more energy to deliver the packet than other sensor nodes. On the other hand, the inaccurate location information and the existence of obstacles can significantly drop the performances of existing routing protocols. This thesis proposes a novel algorithm, called JLR, which takes both the energy balancing and obstacle resistance issues into consideration under the network environment where all sensors have inaccurate location information. Initially, a robot localization approach based on the directional-antenna system is proposed to offer the inaccurate location information to each sensor node. Afterward, the sensor nodes that are nearby the obstacles cooperatively establish the forbidden regions to prevent the packet from entering the concave regions. Compared with the well known GPSR routing protocol, the JLR expects to improve the performance in terms of packet delivery ratio and network lifetime.

Table of Contents
Table of Contents	I
List of Figures	III
List of Tables	VIII
1. Introduction	1
1.1 ROUTE WITH THE ACCURATE LOCATION INFORMATION	1
1.2 COVERAGE	3
1.3 ROUTE WITH THE INACCURATE LOCATION INFORMATION	6
2. Related Work	9
2.1 ROUTE WITH THE ACCURATE LOCATION INFORMATION	9
2.2 COVERAGE	13
2.3 ROUTE WITH THE INACCURATE LOCATION INFORMATION	15
2.3.1 Obstacle Resistance	15
2.3.2 Energy Balancing	17
2.3.3 JLR	18
3. The Proposed WRGP, EBHMM and JLR	19
3.1 WRGP	19
3.1.1 Network Environment and Problem Statement	19
3.1.2 Basic Concepts of the WRGP	20
3.1.3 The WRGP Protocol	21
3.1.4 Multi-Obstacles	37
3.1.5. Analysis of the WRGP	41
3.1.6 Performance Study of the WRGP	43
3.2 EBHMM	55
3.2.1 Network Environment and Problem Statement	55
3.2.2 The Proposed Temporal Full-Coverage Mechanism	57
3.2.3 Intra-Cell and Inter-Cell Hole-Healing Algorithms	69
3.2.4 Performance Study of the EBHMM	71
3.3 JLR	76
3.3.1 Directional-Antenna Based Localization	77
3.3.2 The JLR Routing Protocol	78
3.3.2.1 Energy Balancing	79
3.3.2.2 Obstacle Resistance	80
3.3.3 Performance Study of the JLR	87
4. Conclusion	92
References	94
附錄—英文論文	98

List of Figures
Figure 1. An example of ping-pong effect in [5]. The number in each node represents the weight cost of that node. Node a changes its weight cost twice as shown from (a) to (d).	10
Figure 2. The WRGP constructs an efficient route R1 while PAGER [5] and construct an inefficient route R2.	12
Figure 3. (a) The WRGP selects border nodes in a distributed manner in Phase I. (b) The WRGP determines the effective concave region A in Phase II. (c)The WRGP constructs the Forbidden region in Phase III. (d) In Phase IV, each effective border node derives the best route from itself to the sink node.	20
Figure 4. A failure of the proposed hole-detection rule of study [19] since all intra-angles are smaller than 120o.	22
Figure 5. A network environment with an obstacle.	22
Figure 6. (a) The node s, ni, ni+1 should not play the border role since the small hole did not block the communication of any pair of these three nodes (b) An example that there exists a physical obstacle which blocks the communication of node ni and ni+1. Node s is located nearby the obstacle and therefore should play a border role.	25
Figure 7. (a) The physical obstacle blocks the communication between ni and ni+1 even though their distance is smaller than the communication range. (b) Node s will not serve as a border node since the voronoi neighbors of node s separate obstacle and node s.	26
Figure 8. An example of applying the Self Pruning Rule.	27
Figure 9. An example for illustrating the farthest, critical, and effective border nodes.	31
Figure 10. A special case for identification of cs and cn.	31
Figure 11. An example to illustrate the case operations for the CE packets sent from the critical border node cs.	36
Figure 12. An example to illustrate that S-WRGP results in an inefficient route due to the existence of multiple obstacles.	36
Figure 13. The new obstacle exploitation and the optimal path construction designed in M-WRGP.	38
Figure 14. The monitoring region is partitioned into n hexagonal cells. The communication circle of sensor a intersects with the hexagon H whose edge passing through k+1 hexagonal cells.	41
Figure 15. The shapes of the obstacles in our simulation environment.	44
Figure 16. Comparison of PAGER and S-WRGP in terms of the control overhead in the environment shown in Fig. 15(a).	46
Figure 17. The environments with single obstacle and multiple obstacles used to examine the effect on routing length.	47
Figure 18. Comparison of the accumulated path length between PAGER and S-WRGP under various numbers of the neighboring nodes in Fig. 17(a).	48
Figure 19. Comparison of the path length between PAGER and S-WRGP to the source located in sub-area 9 in Fig. 17(a).	49
Figure 20. Comparison of the accumulated path length between PAGER, S-WRGP and M-WRGP under various numbers of the neighboring nodes in Fig. 17(b).	49
Figure 21. Comparison of PAGER and M-WRGP in terms of accumulated path length. The source location is varied at various sub-areas as shown in Fig. 17(b).	49
Figure 22. Simulation environment that changes the distance of two obstacles for measuring the performance improvement of M-WRGP against the PAGER and S-WRGP in terms of accumulated routing length.	50
Figure 23. Performance comparison of PAGER, S-WRGP and M-WRGP in terms of accumulated path length by varying the distance of two obstacles ranging from 100m to 233m..	51
Figure 24. Five distributions of two obstacles for measuring their impacts on routing path.	52
Figure 25. The impact of obstacle distributions on the route efficiency. The obstacle distributions are shown in Fig. 24. Five distributions of two obstacles are compared. M-WRGP significantly outperforms PAGER and S-WRGP in terms of accumulated path length when the obstacle distributions are (a), (c), and (e).	53
Figure 26. The obstacle distributions with various numbers of obstacles.	53
Figure 27. Performance study of accumulated path length by varying the number of obstacles. The proposed M-WRGP significantly outperforms PAGER and S-WRGP in all cases.	54
Figure 28. The working scenario of M-WRGP.	55
Figure 29. The state diagram of the proposed mechanism applied in each mobile sensor.	57
Figure 30. (a) An example of the partitioned network. The white cell denotes the hole cell. The arrows denote the hole trajectory. (b) Width compression for constructing a Hamiltonian Circuit path.	60
Figure 31. The relationship between coverage disks and hexagonal cell.	62
Figure 32. An example for choosing the best Inter-Cell Hole-Healer.	65
Figure 33. The algorithms of Intra-Cell and Inter-Cell Hole-Healing.	70
Figure 34. The network lifetime of compared three mechanisms in td =1500 and td =2100.	72
Figure 35. The comparison of EBHMM and ADA in terms of the event detection ratio for 10 days starting from the day that the compared temporal full-coverage mechanism is applied.	73
Figure 36. The comparison of EBHMM, ADA and TCSC in terms of average energy difference by varying the number of deployed sensor nodes.	74
Figure 37. The comparison of EBHMM, ADA and TCSC in terms of average energy difference by varying the value of  .	74
Figure 38. The comparison of EBHMM, ADA and TCSC in terms of MCI by varying the number of sensor nodes.	75
Figure 39. The beacon node b with four directional antennas partitions its transmission range into four regions R1, R2, R3 and R4. The gray area in the area that outsides the transmission range but belongs to the bounding box of beacon node b.	78
Figure 40. A monitoring region with forbidden and permitted cells.	79
Figure 41. An example of the destination-location determination of the dead end.	83
Figure 42. An example of the packet delivery from permitted cell to forbidden cell.	85
Figure 43. The state diagram of the proposed JLR.	87
Figure 44.  The comparison of the GPSR, LEBR and JLR in terms of EBI.	88
Figure 45. The comparison of three routing protocols in terms of the packet delivery ratio.	89
Figure 46. The comparison of three routing protocols in terms of EI.	89
Figure 47. The scenarios of three routing protocols in terms of the traffic load.	90

List of Tables
Table 1. The performances of S-WRGP examined in various shapes of the obstacle of	46
Table 2. The Abbreviations of Compared Mechanisms	71
Table 3. Simulation Parameters	71

[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, 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, Mar. 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, Aug. 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, Jul. 2005.
[6]	Shigang Chen, Guangbin Fan and Jun-Hong Cui, “Avoid ’Void’ in Geographic Routing for Data Aggregation in Sensor Networks,” International Journal of Ad Hoc and Ubiquitous Computing (IJAHUC), Special Issue on Wireless Sensor Networks, vol. 2, no. 1, pp. 169-178, Nov. 2006.
[7]	S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, “Coverage Problem in Wireless Ad-Hoc Sensor Networks,” IEEE Conference on Computer Communications, vol. 3, pp. 1380-1387, Apr. 2001.
[8]	S. Slijepcevic and M. Potkonjak, “Power Efficient Organization of Wireless Sensor Networks,” IEEE International Conference on Pervasive Computing and Communications, pp. 406-410, Mar. 2005.
[9]	J. Hwang, D. H. C. Du and E. Kusmierek, “Energy Efficient Organization of Mobile Sensor Networks,” IEEE International Conference on Parallel Processing Workshop, pp. 84-91, 2004.
[10]	Y. Zou and K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” ACM Transactions on Embedded Computing Systems, vol. 3, pp. 61-91, 2004.
[11]	X. Shan and J. Tan, “Mobile Sensor Deployment for a Dynamic Cluster-based Target Tracking Sensor Network,” IEEE International Conference on Intelligent Robots and Systems, pp. 1452-1457, Aug. 2005.
[12]	M. Zhang, X. Du, and K. Nygard, “Improving Coverage Performance in Sensor Networks by using Mobile Sensors,” IEEE Military Communications Conference, pp. 17-20, Oct. 2005.
[13]	C. Gui, and P. Mohapatra, “Virtual Patrol: A New Power Conservation Design for Surveillance Using Sensor Networks,” IEEE Information Processing in Sensor Networks, pp. 246-253, Apr. 2005.
[14]	B. Liu, P. Brass, and O. Dousse, “Mobility Improves Coverage of Sensor Networks,” ACM international symposium on Mobile ad hoc networking and computing, pp. 300-308, 2005.
[15]	G. Wang, G. Cao, T. L. Porta, and W. Zhang, “Sensor Relocation in Mobile Sensor Networks,” IEEE IEEE Conference on Computer Communications, vol. 4, pp. 2302-2312, Mar. 2005.
[16]	Z. Jiang, J. Wu, A. Agah, and B. Lu, “Topology Control for Secured Coverage in Wireless Sensor Networks,” Proc. of the 3rd IEEE International Workshop on Wireless and Sensor Networks Security, Oct. 2007.
[17]	C. Y. Chang, H. R. Chang, H. J. Liu, and S. W. Chang, “On Providing Temporal Full-Coverage by Applying Energy Efficient Hole-Movement Strategies for Mobile WSNs,”  IEEE Wireless Communications and Networking Conference, Hong Kong, Mar. 2007.
[18]	P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, “Routing with guaranteed delivery in ad hoc wireless networks,” Proceedings of the 3rd ACM International Workshop on discrete Algorithms and Methods for Mobile Computing and Communications, pages 48–55, Seattle, WA, Aug. 1999.
[19]	Q. Fang, J. Gao, and L. J. Guibas, ”Locating and Bypassing Routing Holes in Sensor Networks,” IEEE Conference on Computer Communications, Mar. 2004.
[20]	C. Y. Chang,  W. C. Ju and Y. C. Chen, “WRGP: Weight Aware Route Guiding  Protocol for  Wireless Sensor Networks with Obstacles,” IEEE International Conference on Communications, May 2008.
[21]	K. Seada, A. Helmy and R. Govindan, “Modeling and analyzing the correctness of geographic face routing under realistic conditions,” Ad Hoc Networks 2007.
[22]	S. Funke, N. Milosavljevi´c, “Guaranteed-delivery Geographic Routing under Uncertain Node Locations,” IEEE Conference on Computer Communications, May 2007.
[23]	Q. Li, J. Aslam, D. Rus, “Online power-aware routing in wireless ad-hoc networks,” The Annual International Conference on Mobile Computing and Networking 2001.
[24]	K. Woo, C. Yu, D. Lee, H. Yon, and B. Lee, “Non-blocking, localized routing algorithm for balanced energy consumption in mobile ad hoc networks,” in Proceedings of the 9th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication System, pp. 117-124, 2001.
[25]	X. Liu, H. Hou, H. Yu, and H.  Hu, “LEBR: A Localized Energy Balancing Routing Algorithm in Wireless Sensor Networks,” International Conference on Communication Technology, pp. 1-4, Nov. 2006.
[26]	A. Galstyan, B. Krishnamachari, S. Pattem, and K. Lerman, “Distributed Online Localization in Sensor Networks Using a Moving Target,” IEEE Information Processing in Sensor Networks, Apr. 2004.
[27]	http://webs.cs.berkeley.edu/tos.