在Wireless sensor networks (WSNs)環境中，監控區域的感測覆蓋面積會影響回傳到sink的監控資料精確度，如何將sensors佈置於特定欲監測區域內，並維持高效率的監測效能是個重要的議題。在網路佈建議題方面，sensors必須以低成本、高覆蓋的方式佈建在特定的監控區域裡。傳統最簡單的方式是隨機將sensors佈建在監控區域中，然而以隨機佈建會造成sensor佈建不均的問題。有鑑於此，我們首先研發了有效率的克障機器人佈點（OFRD），藉由所提出之感測點佈建策略、蛇行狀移動機制及障礙物與邊界處理規則，使機器人能夠快速且花費最少的sensors數量佈點於監測區域，並有效地避開障礙物。在網路修復議題方面，由於sensor電量的限制，並且常被佈置於戶外去監控環境資訊，因此在執行一段時間後會因電量消耗殆盡，而導致無法正常運作，此時其所負責的區域若沒其他sensor感測的話，將會使網路出現空洞。因此，本論文提出了一有效率的網路修復演算法（TRR），藉由機器人在行走過程中留下其行走的軌跡，使WSN中的sensors皆能追蹤機器人的位置資訊，並能以較短路徑發送修復封包以通知機器人進行毀損修復，使機器人能以動態、快速、省電及有效率的方式往修復區移動。此外，Home演算法提供機器人在進行修復的過程中，以剩餘電量來安排較佳行走路徑，來達到回Home充電及補充新的sensors的目的，使WSNs的覆蓋範圍得以更有效地維護。除了網路佈建與修復議題外，本論文更探討了如何在已佈建的WSNs下進行廣播。傳統的方式是以封包泛流的方式，將需求封包由sink廣播給所有監控區域的sensor，雖然方法簡單，但會造成大量的封包碰撞與頻寬浪費，進而影響資料收集的精確度。有鑑於此，我們提出一個有效率克服障礙物的廣播演算法（OFZBP），藉由動態的座標系統，讓每個sensor知道自己與sink之間的相對位置，並透過適當的封包傳送排程協定，以減少代傳點的數目與克服未知的障礙物，進而節省sensor電量與網路頻寬耗費、以及提高封包到達率。實驗結果顯示了本論文所提出的克障礙物網路佈建、修復以及廣播演算法，能夠成功克服障礙物，並比現存的其他演算法有較佳的效能。

In wireless sensor networks(WSNs), coverage of the monitoring area represents the quality of service (QoS) related to the surveillance. Node deployment and failure recovery are the key issues in providing the WSN with full coverage. In the deployment issue, sensor nodes should be efficiently deployed in a predetermined region in a low cost and high coverage quality manner. Random deployment is the simplest way for deploying sensor nodes but may cause the unbalanced deployment and therefore increase the hardware cost and create coverage holes. This thesis initially presents an efficient obstacle-free robot deployment algorithm, called OFRD, which involves the design of node placement policy, snake-like movement policy, obstacle handling rules, and boundary rules. By applying the proposed OFRD, the robot rapidly deploys near-minimal number of sensor nodes to achieve full sensing coverage even though there exist unpredicted obstacles.
Another important issue for maintaining a high quality of surveillance service is the failure recovery. Since sensor nodes are battery powered and placed at the outdoor environment, they might be failure due to energy exhaustion or environmental influence, and hence result in the WSN coverage-loss. In literature, a number of study developed robot deployment algorithms that aim at achieving full coverage while the number of deployed sensor nodes can be minimized. After completing the deployment task, the robot still patrols the monitoring region for maintaining full coverage. However, the efficiency of existing repairing algorithms can be further improved in terms of time and energy consumption required for the robot to execute the repairing task. Moreover, existing repairing algorithms did not consider the existence of obstacles and the constraint of limited energy of the robot. This thesis presents novel tracking mechanism and robot repairing algorithm for maintaining the coverage quality of the given WSN. Without the support of location information, the tracking mechanism leaves robot’s footmark on those sensors that are nearby the failure region to learn better routes for sending repairing requests to the robot. Upon receiving several repairing request messages, the robot applies the proposed repairing algorithm to establish an optimal route that passes through all failure regions with minimal overhead in terms of the required time and power consumption. In addition, the proposed repairing algorithm also considers the remaining energy of the robot so that the robot can be back to home for recharging energy and overcome the unpredicted obstacles.
In addition to the network deployment and repairing issues, this thesis further considers the broadcasting issue for a given WSN that has been deployed by the robot. Broadcasting is an essential operation for sink node to deliver a request message to a region of sensor nodes. Blind flooding is the most simple way and can overcome obstacles but consumes power and bandwidth resources and raises the packet collision and contention problems. An efficient obstacle-free broadcasting protocol, namely OFZBP, is proposed by utilizing the location information of sensors to reduce the number of forwarding nodes and overcome the unpredictable obstacles. By applying the proposed OFZBP, each zone manager determines whether it would subsequently forward the request or not, according to the received zone ID of sink node and neighboring obstacle information. As a result, the proposed OFZBP reduces the packet collisions and increases the packet success rate in the broadcasting operation even through the existence of unpredictable obstacles. 
Performance evaluation of the proposed obstacle-free deployment, repairing and broadcasting algorithms overcome the unpredicted obstacles and outperform the existing related work.

Contents  I
List of Figures  III
List of Tables  VIII
1. Introduction  1
1.1 Literature Review of Network Deployment Algorithms  2
1.2 Literature Review of Failure Recovery Algorithms  4
1.3 Literature Review of Broadcasting Algorithms  6
2. Backgrounds and Basic Concepts  9
2.1 Backgrounds of Sensor Technology  9
2.2 Basic Concepts of Obstacle-Free Robot Deployment Algorithms  12
2.3 Basic Concepts of Obstacle-Free Robot Repairing Algorithms  14
2.4 Basic Concepts of Obstacle-Free Broadcasting Protocol 19
3. Obstacle-Free Deployment Algorithms for Wireless Sensor Networks  22
3.1 Network Environment and Problem Statement  22
3.2 Preliminaries  24
3.3 Simple Snake-like Deployment  25
3.4 Obstacle-Free Snake-like Deployment  26
3.4.1 Obstacle Handling Mechanisms  27
3.4.2 Boundary Handling Mechanisms  32
3.5 Analysis of Deployment Efficiency  39
3.6 Performance Study  42
4. Energy Efficient Robot Repairing Algorithms for Maintaining Coverage Quality in Wireless Sensor Networks  54
4.1 Network Environment and Problem Formulation  54
4.2 Tracking Mechanism  57
4.3 Power-Conservation Repairing Mechanism  64
4.4 Performance Study  70
5. An Obstacle-Free Zone-based Broadcasting Protocol for Wireless Sensor Networks  81
5.1 The Existing Broadcasting Protocols  81
5.2 Network Environment and Problem Statement  87
5.3 Notations and Preliminaries  91
5.4 Challenges of Overcoming Unknown Obstacle  95
5.5 The Obstacle-Free Broadcasting Protocol (OFZBP)   97
5.6 Simulation Results and Comparison  112
6. Conclusions  121
References  123 


List of Figures
2.1	The environment architecture of WSNs.  10
2.2	Different versions of Mica motes.  11
2.3	Basic components of sensor node.  11
2.4	The robot deployment and movement policies involving the design of obstacle handling mechanism.  13
2.5	The route constructed based on the trajectory path of the robot is rugged and inefficient. The proposed X-correction mechanism enables the robot timely correcting the footmarks to help sensor learn a better route from itself to the robot.  15
2.6	The comparison of the constructed paths by applying the greedy algorithm and the proposed repairing algorithm. The proposed repairing algorithm constructs a shortest path marked by the solid line.  16
2.7	The challenge of developing a repairing algorithm in considering the robot’s remaining energy. The developed repairing algorithm constructs a route that prevents the robot from energy exhaustion.  17
2.8	The proposed repairing algorithm constructs an efficient path even though there exists an unpredicted obstacle.  18
2.9	ZBP[15] selects managers which lie on the blue region participate the broadcast process.  20
2.10	The OFZBP overcomes the unpredicted obstacles and achieves higher success rate of receiving the packets.  20
3.1	A basic requirement for an optimal deployment and the proposed snake-like movement mechanism.  22
3.2	Applying simple snake-like deployment results holes due to the existence of obstacles and boundary.  23
3.3	Six types of basic movements and their usages.  24
3.4	(a) Applying the simple snake-like deployment scheme results an inner-concave sensing hole. (b) The proposed obstacle-free snake-like deployment mechanism can overcome the obstacle and achieves full coverage.  29
3.5	The boundary problem: the robot should make decision whether or not a sensor should be deployed at the boundary.  32
3.6	Two cases in the S-Class boundary problem.  34
3.7	Eight cases in the C-Class boundary problem.  34
3.8	An example of overcoming the C-class boundary problem by applying the BRules.  37
3.9	In analysis, a hexagon region is used to represent the sensing area of one sensor.  39
3.10	The monitoring region contains a rectangle obstacle with size W’*L’.  41
3.11	Obstacles with various shapes are considered in the simulation environment in the X-correction mechanism.  43
3.12	Screenshots of the deployment by applying OFRD mechanism.  44
3.13	The OFRD reduces the number of deployed sensors and maintains near-full coverage in different environments.  45
3.14	The OFRD deploys a constant number of deployed sensors even though the five-shape obstacles are rotated with 45°, 90°, 180°, and 270° degrees in the environment.  46
3.15	OFRD achieves high Deployment Efficiency in the environments containing various shapes of obstacles.  47
3.16	The average deployment time and coverage percentage by applying the OFRD and CED in the environment containing multiple obstacles with different shapes.  49
3.17	OFRD achieves high Energy Efficiency in the environment with multiple different shapes of obstacles.  51
3.18	The frequency of six movement types applied by the robot which executes OFRD in different environments.  52
3.19	The frequencies of each rule applied by the robot which executes OFRD in different environments.  53
4.1	The robot leaves a footmark on each sensor. It assigns each deployed sensor with coordinates and thus the VC system of the WSN is constructed.  58
4.2	The basic concept of X-correction mechanism.  61
4.3	An example for illustrating the X-correction mechanism.  62
4.4	An example that illustrates the benefit obtained by applying the X-correction mechanism.  64
4.5	Robot Repairing algorithm that considers the remaining energy of the robot but does not considers the existence of obstacles.  66
4.6	Algorithm for constructing a repairing path by initiating a probe packet along the previously constructed optimal path to cope with the obstacle problem.  68
4.7	An example for illustrating the path construction algorithm with the consideration of obstacle.  70
4.8	Obstacles with various shapes are considered in the simulation environment.  71
4.9	The control overhead of three mechanisms for correcting the counter values.  72
4.10	The average length of tracking path from request initiators to the robot by applying the three correction mechanisms.  73
4.11	The average length of tracking path by varying the threshold value of movement distance.  74
4.12	Comparison of TRR and CED in terms of recovery delay in the environment that contains multiple obstacles with different shapes.  75
4.13	Comparison of TRR and CED in terms of recovery delay in the environment that contains one obstacle with different sizes.  76
4.14	Comparison of TRR and CED in terms of the repairing efficiency in the environment that contains multiple obstacles with different shapes.  77
4.15	Comparison of TRR and CED in terms of the repairing efficiency in the environment that contains multiple obstacles with different sizes.  77
4.16	Comparison of TRR and CED in terms of the coverage ratio in the environment of containing multiple obstacles with different shapes.  78
4.17	Comparison of TRR and CED in terms of the coverage ratio in the environment of containing multiple obstacles with different sizes.  79
4.18	Comparison of TRR and CED in terms of the variation of repair efficiency when the home location is changed.  80
5.1	Collision caused by node-level flat flooding.  82
5.2	Coordinate system of CBM[26].  82
5.3	The scenarios of inter- and intra- zone-level flooding.  83
5.4	ZBP partitions the WSN into six regions, A1, …, A6, according to the six direction of source cell S where the sink node is located.  84
5.5	ZBP further partitions each region Ai into bands with width three. In sub-region Ai, manager of cell location on Sub-Axis Si executes the packet broadcasting. All managers in this sub-region will receive packet without collision.  85
5.6	Type-1 collision and it’s the delay scheduling.  86
5.7	Type-2 collision and it’s the delay scheduling.  86
5.8	Some examples of unknown obstacles. These obstacles block packet transmission, resulting managers in region X without receiving any packet sent from sink node S.  90
5.9	The x-axis and y-axis of region Ai are Xi and X(i+1) mod 6, respectively.  92
5.10	Transmission delay of manager MA、MB、MC、MD、ME and MF scheduled to avoid collision.  99
5.11	The Forwarding Broadcast Packet is transmitted by the packet forwarding direction.  99
5.12	The three gray zones are promising forwarding zones of R and the three white zones are non-promising forwarding zones of R.  103
5.13	Show that the timestamp that the manager received the broadcast packet.  107
5.14	Show that the managers MC, MD, and ME received the AP packet and rebroadcast the packet at the same time, causing the packet collision at the managers MF and MG.  108
5.15	The managers nearby the obstacle can successfully receive the query packet by AP packet transmission, but the further managers in the region X can not receive the query packet if the manager such as MI does not continuously transmit the packet after receiving the AP packet.  110
5.16	A complete example to run the aforementioned four rules.  111
5.17	Obstacles with various shapes are considered in the simulation environment.  112
5.18	The OFZBP can efficiently overcome multiple obstacles and achieve 100% packet success rate.  114
5.19	The OFZBP can overcome all kinds of multiple obstacles and achieve high packet success rate.  115
5.20	The comparison of four mechanisms in terms of Overhead Index in the environment that contains multiple middle-sized obstacles.  116
5.21	Percentage of sensor nodes that rebroadcast messages in the environment that contains different shapes of obstacles with various sizes.  117
5.22	The number of collisions associated with the number of sensor nodes under the mixed kind of different-sized obstacles environment.  118
5.23	The comparison of power consumption among OFZBP, ZBP, CBM, and Flooding in the environment with multiple different shapes of obstacles.  119
5.24	The frequencies of each rule applied by the OFZBP in different environments.  120 


List of Tables
3.1	Simple Snake-like Deployment.  25
3.2	Check Directions for overcoming the obstacle.  27
3.3	Obstacle-Free Snake-Like Movement Rule.  29
3.4	Simulation parameters.  42
3.5	Comparisons of OFRD and CED schemes in terms of the number of deployed sensor nodes in different environments.  45
3.6	Deployment time of OFRD and CED in different environments.  48
3.7	Energy consumption of OFRD and CED in different environments.  50
4.1	Simulation parameters.  71
5.1	The direction table of information recorded in the manager of cellular A of the Fig. 5.10.  101
5.2	The threshold δ impacts OFZBP on the success rate and delay time.  113

[1]I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, ”A Survey on Sensor Networks,” IEEE Communications Magazine, vol. 40, no. 8, pp.102-114, August 2002.
[2]I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, ”Wireless Sensor Networks: A Survey,” Computer Networks(Elsevier) Journal, vol. 38, no. 4, pp. 393–422, March 2002.
[3]M. S. Pan, C. H. Tsai and Y. C. Tseng, “Emergency Guiding and Monitoring Applications in Indoor 3D Environments by Wireless Sensor Networks”, International Journal of Sensor Networks, vol. 1, no. 1/2, pp. 2-10, 2006.
[4]W. Liang and Y. Liu, "Online Data Gathering for Maximizing Network Lifetime in Sensor Networks," IEEE Transactions on Mobile Computing, vol. 6, no. 1, pp. 2-11, Jan. 2007. 
[5]B. CARBUNAR, A. GRAMA, J. VITEK and O. CARBUNAR, "Redundancy and Coverage Detection in Sensor Networks," ACM Transactions on Sensor Networks, vol. 2, no. 1, pp. 94-128, February 2006.
[6]H. Gupta, Z. H. Zhou, S. R. Das and Q. Gu, "Connected Sensor Cover: Self-Organization of Sensor Networks for Efficient Query Execution," IEEE/ACM Transactions on Networking, vol. 14, no. 1, pp. 55-67, Feb. 2006. 
[7]N. Heo and P.K. Varshney, "Energy-Efficient Deployment of Intelligent Mobile Sensor Networks," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol. 35, no. 1, pp. 78-92, Jan. 2005. 
[8]S. Chellappan, X. Bai, B. Ma, D. Xuan and C. Xu, "Mobility Limited Flip-Based Sensor Networks Deployment," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 2, pp. 199-211, Feb. 2007.
[9]G. L. Wang, G. H. Cao and T. F. L. Porta, "Movement-assisted sensor deployment," IEEE Transactions on Mobile Computing, vol. 5, no. 6, pp.640-652, June 2006.
[10]G. Wang, G. Cao and T. LaPorta, ”Movement-Assisted Sensor Deployment,” Proceedings of the 23rd annual Joint Conference of the IEEE Computer and Communication Societies (INFOCOM), vol. 4, pp. 2469-2479, HongKong, March 2004.
[11]G. Wang, G. Cao, T. L. Porta and W. Zhang, ”Sensor Relocation in Mobile Sensor Networks,” Proceedings of the 24rd Annual Joint Conference of the IEEE Computer and Communication Societies (INFOCOM), Minmi, Florida, USA, pp.2302-2312, March 2005.
[12]M. A. Batalin and G. S. Sukhatme, “Efficient Exploration without Localization,” International Conference on Robotics and Automation (ICRA), pp. 2714–2719, Taipei, Taiwan, May 2003. 
[13]M. A. Batalin and G. S. Sukhatme, “Coverage, Exploration and Deployment by a Mobile Robot and Communication Network,” Proceedings of the International Workshop on Information Processing in Sensor Networks, pp. 376-391, Palo Alto Research Center (PARC), Palo Alto, Apr 2003.
[14]Y. Zou and K. Chakrabarty, “Sensor deployment and Target Localization in Distributed Sensor Networks,” ACM Transations on Embedded Computing Systems, vol. 3, pp.61-91, 2004.
[15]Y. C. Wang, C. C. Hu and Y. C. Tseng, “Efficient Deployment Algorithms for Ensuring Coverage and Connectivity of Wireless Sensor Networks,” IEEE Wireless Internet Conference (WICON), pp.114-121, 2005.
[16]M. J. Mataric, “Behavior-based Control: Examples from Navigation, Learning, and group behavior,” Journal of Experimental and Theoretical Artificial Intelligence, special issue on Software Architectures for Physical Agents, vol. 9, no. 2-3, pp. 323-336, 1997.
[17]P. Pirjanian, “Behavior Coordination Mechanisms-State-of-The-Eart,” Tech. Rep. IRIS-99-375, Institute for Robotics and Intelligent Systems, University of Southern California, October 1999.
[18]M. A. Batalin, G. S. Sukhatme and M. Hattig, “Mobile Robot Navigation using a Sensor Network,” Proceedings of the IEEE International Conference on Robotics & Automation, New Orleans, LA, April 2004.
[19]J. Hill and D. Culler, “A Wireless Embedded Sensor Architecture for System-level Optimization,” Technical report, Computer Science Department, University of California at Berkeley, 2002.
[20]S. Ganeriwal, A. Kansal and M. B. Srivastava, “Self Aware Actuation for Fault Repair in Sensor Neworks,” IEEE International Conference on Robotics and Automation (ICRA), April 2004.
[21]W. H. Liao, Y. C. Tseng and J. P. Sheu, ”GRID : A Fully Location-Aware Routing Protocol for Mobile Ad Hoc Networks,” The 6th Mobile Computing Workshop, pp. 1-8, March 2000.
[22]Y. C. Tseng, S. Y. Ni, Y. S. Chen and J. P. Sheu, "The Broadcast Storm Problem in a Mobile Ad hoc Network," ACM Wireless Networks, vol. 8, no. 2, pp. 153-167, March 2002.
[23]S. Basagni, D. Bruschi and I. Chlamtac, “A Mobility-Transparent Deterministic Broadcast Mechanism for Ad Hoc Networks,” IEEE/ACM transactions on networking, vol. 7, no. 6, December 1999.
[24]C. Y. Chang and C. T. Chang, "Hierarchical Cellular-Based Management for Mobile Hosts in Wireless Ad Hoc Networks," Computer Communications Journal, vol. 24, pp. 1554-1567, 2001.
[25]S. Basagni, D. Bruschi and I. Chlamtac, “A Mobility-Transparent Deterministic Broadcast Mechanism for Ad Hoc Networks,” IEEE/ACM transactions on networking, vol. 7, no. 6, pp. 799–807, December 1999.
[26]E. M. Royer and C. K. Toh, “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” IEEE Personal Communications, vol. 6, no. 2, pp. 46–55, April 1999.
[27]C. S. Hsu, J. P. Sheu and Y. J. Chang, “Efficient Broadcasting Protocols for Regular Wireless Sensor Networks,” IEEE International Conference on Parallel Processing, pp. 213-220, Oct. 2003.
[28]C. Y. Chang, K. P. Shih and S. C. Lee, “ZBP: A Zone-based Broadcasting Protocol for Wireless Sensor Networks,” Wireless Personal Communications, vol. 33, no. 2, pp. 53-68, June 2005.
[29]C. Y. Chang, C. T. Chang and S. C. Tu, "Obstacle-Free Geocasting Routing Protocol for Ad-Hoc Wireless Networks," ACM/Baltzer Journal of Wireless Networks,vol.9, no. 2, pp.143-155, 2003.
[30]E. Biagioni and K. Bridges, “The Application of Remote Sensor Technology to Assist the Recovery of Rare and Endangered Species,” Special Issue on Distributed Sensor Networks, International Journal of High Performance Computing Applications, vol. 16, no. 3, Aug. 2002.
[31]A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton and J. Zhao, “Habitat Monitoring: Application Driver for Wireless Communications Technology,” Proceeding of 2001 ACM SIGCOMM Workshop on Data Communications in Latin America and the Caribbean, April 2001.
[32]A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler and J. Anderson, “Wireless Sensor Networks for Habitat Monitoring,” ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), Atlanta, GA, Sept. 2002.
[33]S. Chessa and P. Santi, “Crash Faults Identification in Wireless Sensor Networks,” Computer Communications, vol. 25, no. 14, pp. 1273-1282, Sept. 2002.
[34]L. Schwiebert, S. K. S. Gupta and J. Weinmann, “Research Challenges in Wireless Networks of Biomedical Sensors,” Proceeding ACM/IEEE Conference on Mobile Computing and Networking (MobiCom), pp. 151-165, 2001.