在Wireless sensor networks (WSNs)環境中，監控區域的感測覆蓋面積會影響回傳到sink的監控資料精確度，如何將sensors佈置於特定欲監測區域內，並維持高效率的監測效能是個重要的議題。在網路佈建議題方面，sensors必須以低成本、高覆蓋的方式佈建在特定的監控區域裡。傳統最簡單的方式是隨機將sensors佈建在監控區域中，然而以隨機佈建會造成sensor佈建不均的問題。有鑑於此，本論文首先研發了有效率的克障機器人佈點（ORRD），藉由所提出之感測點佈建策略、蛇行狀移動機制及障礙物與邊界處理規則，使機器人能夠快速且花費最少的sensors數量佈點於監測區域，並有效地避開障礙物。接著，本論文另外提出了一機器人佈點演算法(OFPD)，同時考量避障礙物以及機器人移動時所產生的偏差問題，進行自我位置調整。透過機器人以螺旋形的移動機制以及遭遇障礙物時的規則處理，進行佈點的動作，進而減少機器人移動時所消耗的電量並達到完整覆蓋整個監控區域之目的。上述所提出的兩種機器人佈點演算法，雖然可以適用於絕大部分的網路環境，然而，當障礙物的形狀極度不規則時，
仍然有可能產生空洞及死路的問題，導致整個監控環境無法被完全覆蓋。此外，ORRD及OFPD皆未對機器人行走的路徑進行最佳化的動作，導致機器人在進行佈點的同時，可能會產生多繞路的問題。因此，本論文最終提出了一有效率的機器人佈點演算法(DFD)，以少量的記憶成本讓機器人幾乎可以克服任何複雜的障礙物並最佳化佈點路徑，將適量的感應器佈建於監控區中，同時達到縮短佈建時間、節省硬題成本及全區覆蓋等目的。實驗顯示，本論文所提出的演算法具有高佈點率、低電力成本，且可以在複雜的監測區域中達到全區覆蓋，並比現存的其他機器人佈點演算法有較佳的效能。

In wireless sensor networks(WSNs), coverage of the monitoring area represents the quality of service (QoS) related to the surveillance. Node deployment is one of the most important issues in providing the WSN with full coverage. 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 ORRD, which involves the designs of node placement policy, snake-like movement policy, obstacle handling rules, and boundary rules. By applying the proposed ORRD, the robot rapidly deploys near-minimal number of sensor nodes to achieve full sensing coverage even though unpredicted obstacles exit. Afterward, this thesis proposes an obstacle-free and power efficient-robot deployment algorithm, called OFPD which applies a spiral movement rule to overcome unpredicted obstacles, correct bias movement, and employ full-coverage deployment. By applying the OFPD, the number of deployed sensors can be significantly reduced and the purposes of full coverage and energy saving are likely achieved. In addition, the OFPD also takes into consideration the bias movement problem which is generally occurred in most commercial robots. Though the proposed ORRD and OFPD algorithms can deal with most irregular obstacles, however, the coverage hole, dead-end and long route length problem might be occurred in some other cases due to the obstacle shapes. Eventually, this thesis further proposes a dead-end free deployment algorithm, called DFD, which consists of Movement, Deployment and Dead-End handling rules. The Movement and Deployment rules ask robot to efficiently deploy a minimal number of sensors for achieving full coverage while the Dead-End handling rule overcomes the Dead-End problem and likely achieves full sensing coverage. Performance evaluations depict that the proposed obstacle-free deployment algorithms overcome the unpredicted obstacles and outperform the existing related work.

Contents
Contents…...IV
List of Figures...VI
List of Tables...XI
Chapter 1. Introduction...1
Chapter 2. Related Work...4
Chapter 3. The Obstacle-Resistant Robot Deployment (ORRD) Algorithm...7
3.1 Network Environment and Basic Concept...7
3.2 Legal Movement Pattern...9
3.3 Simple Serpentine Robot Deployment...10
3.4 Obstacle-Resistant Serpentine Robot Deployment...11
3.4.1 The Impact of Obstacles...11
3.4.2 Obstacle Handling Rules...12
3.5 Boundary Problem and Its Handling Rules...17
3.5.1 Boundary Rule for S-Class boundary problem...19
3.5.2 Boundary rule for C-Class boundary problem...20
3.5.3 Putting Obstacle and Boundary Handling Rules Together...23
3.6 Analysis and Deployment Efficiency...24
3.6.1 Without the Obstacle Environment...25
3.6.2 With the Obstacle Environment...28
3.7 Performance Study...30
3.8 Summary...46
Chapter 4. The Obstacle-Free and Power-Efficient Deployment (OFPD) Algorithm...47
4.1 Network Environment and Basic Concept...47
4.2 Robot Deployment Algorithm...50
4.2.1 Node Placement Policy...50
4.2.2 Spiral Movement Policy...51
4.3 Obstacle Handling...53
4.3.1 Obstacle Surrounding Movement Policy...54
4.3.2 Switching from Obstacle to Steady State...57
4.3.3 Layer Information and Energy Conservation...61
4.3.4 Algorithm Termination...62
4.3.5 Robot Deployment Algorithm...63
4.4 Performance Study...65
4.5 Summary...71
Chapter 5. The Dead-End Free Deployment (DFD) Algorithm...72
5.1 Network Environment and Problem Formulation...72
5.2 Optimal Deployment Mechanism without Considering Obstacle...74
5.2.1 Basic Movement Rule...74
5.2.2 Basic Deployment Rule...76
5.3 Dead-End Free Deployment (DFD) Algorithm...78
5.3.1 Basic Concept...78
5.3.2 The DFD Algorithm...80
5.4 Analysis of Deployment Trajectories...88
5.5 Performance Study ...92
5.6 Summary...96
Chapter 6. Conclusions...97
References...99

List of Figures
3.1A basic requirement for an optimal deployment and the proposed serpentine movement mechanism. (a) The optimal deployment of the three nearby sensors A, B, and C. (b) The serpentine movement deployment...7
3.2The deployment by applying the obstacle handling mechanism...8
3.3Six types of basic movements and their usages. (a) Six legal patterns for basic movement. (b) A scenario of applying six types of basic movement to overcome obstacles...9
3.4Applying simple serpentine deployment results several holes due to the existence of obstacles and boundary...12
3.5Examples of simple serpentine and obstacle-resistant serpentine deployment mechanisms. (a) Applying the simple serpentine deployment scheme results an inner-concave sensing hole. (b) The proposed obstacle-resistant serpentine deployment mechanism can overcome the obstacle and achieves full coverage...15
3.6The boundary problem: the robot should make a decision on whether or not a sensor should be deployed at the boundary...17
3.7Two cases in the S-Class boundary problem...19
3.8Eight cases in the C-Class boundary problem...19
3.9An example of overcoming the C-class boundary problem by applying the BRules. (a) An example of the C-Class boundary problem. The robot applies BRule2 to achieve the full-coverage deployment. (b) Boundary for Rule2 (The robot moves toward Check Direction 2 by about   and then turns to Check Direction 1 or Prefer Direction 1 whose moving distance is not enough  )...22
3.10Three ways of regular deployment and their effective coverage regions. (a) Triangle deployment. (b) Square deployment. (c)Hexagon deployment...25
3.11The effective coverage region of hexagon deployment can be treated as a rectangle region which has the same area size as the hexagon region shown in Figure 3.10(c)...26
3.12An example of irregular monitoring area considered in the optimality analysis for ORRD mechanism...27
3.13The irregular monitoring region containing irregular obstacles is considered for optimality analysis by the ORRD mechanism...28
3.14The shapes of regular obstacles considered in the simulation...31
3.15The generation of an irregular obstacle. (a) An example of an irregular obstacle with nine unit squares. (b) Six possible arcs that replace the boundaries of an irregular obstacle. (b) Six possible arcs that replace the boundaries of an irregular obstacle. (d) The final version of the generated irregular obstacle with nine unit squares...33
3.16Screenshots of the deployment by applying OFRD mechanism. (a) The screenshot of the development by applying OFRD in an environment without obstacle. (b) The screenshot of the development by applying OFRD in an environment containing a C-shape obstacle...34
3.17The comparison of coverage percentage in the environment that contains a regular obstacle with various shapes...35
3.18The ORRD 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...36
3.19The impact of irregular obstacles on the number of deployment sensors...37
3.20The comparison of the ORRD, CED and LRV in terms of the deployment efficiency...38
3.21The average deployment time after applying the ORRD, CED and LRV in the environment containing multiple regular obstacles with different shapes...39
3.22The comparison of the ORRD, CED and LRV in terms of energy efficiency within a specific time period...41
3.23The frequencies of six movement types applied by the robot that executes the ORRD in different environments...43
3.24The applied frequency of each rule proposed in the ORRD in an environment containing a regular obstacle with various shapes...43
3.25The applied frequency of each rule proposed in the ORRD in environments containing one or two irregular obstacles of sizes six, nine or twelve unit squares...44
3.26The applied frequencies of Brules 1 and 2 for the environment containing irregular obstacles...45
3.27Coverage hole existed in U-Shape obstacle environment...46
3.28Dead-end problem occurred in the ORRD algorithm...46
4.1Sensor placement and spiral movement policies...48
4.2Basic deployment concept when the robot encounters an obstacle...50
4.3An optimal deployment of sensors si, sj, and sk...51
4.4Movement trajectory of the robot. (a) Spiral movement. (b) Six cardinal directions...52
4.5Obstacle surrounding movement policy...55
4.6An example wherein the robot applies obstacle surrounding movement policy to overcome obstacles. (a) The robot applies obstacle surrounding movement policy in obstacle state. (b) The robot treats the sensors with obstacle state as virtual obstacles, and switches from steady and obstacle state to overcome obstacles...56
4.7The robot uses an ultrasonic sensor or a laser sensor to detect the distance of the farthest point of the obstacle-boundary and the robot. The robot treats an irregular boundary as a regular boundary B1...56
4.8An example that illustrates the details of the obstacle surrounding movement policy. (a) Example of the boundary problem wherein the robot needs to deploy a sensor at the boundary of an obstacle. (b) A case wherein the robot deploys sensors to surround the obstacle...57
4.9The robot determines a location for deploying its next sensor from candidate locations D and D’ as it switches from obstacle to steady state...58
4.10The execution of Algorithm Termination...62
4.11Considered monitoring areas that might contain obstacles. (a) Scenario 1: Rectangular area. (b) Scenario 2: Circular area. (c) Scenario 3: U-shaped obstacle existing in the rectangular area. (d) Scenario 4: X-shaped obstacle existing in the rectangular area. (e) Scenario 5: Multiple obstacles existing in the rectangular area...65
4.12Average number of deployed sensors in different monitoring areas...67
4.13The relationship between the number of sensors and the coverage percentages in different scenarios. (a) Scenario 1: Rectangular area. (b) Scenario 2: Circular area. (c) Scenario 3: U-shaped obstacle. (d) Scenario 4: X-shaped obstacle. (e) Scenario 5: Multiple obstacles...68
4.14Average moving distance in various scenarios...69
4.15The power consumption of robot movements and communications. (a) Power consumption in robot movements. (b) Power consumption in communications...70
4.16Coverage hole existed in complex obstacle environment...71
4.17Redundant robot movement path in the proposed OFPD algorithm...71
5.1The robot deployment problem(a) ORRD could encounter coverage-hole problem. (b) ORRD could encounter Dead-End problem. (c) In OFPD, many of robot movement routes for achieving full coverage is redundant...73
5.2The priorities of movement directions...75
5.3An example that illustrates the deployment trajectory by applying the proposed movement rule. (a) The robot moves in a spiral way, from outside to inside, if it initially locates at the left-top corner. (b) The movement trajectory of the robot in case that it is not initially located at the boundary region...76
5.4Basic Deployment Rule. (a) Basic requirement for optimal deployment. (b) The movement of H mode. (c) The straight movement of V mode consists of two patterns....77
5.5A scenario that the robot stays in a Narrow-Lane state...79
5.6The state diagram of DFD Algorithm...80
5.7An example to explains that the robot should record the locations of turns in stack...82
5.8Stack Reduction Procedure. (a) The comparison of stack status with and without applying the Stack-Reduction Rule. (b) The coverage holes neighboring to the entrance point of a Narrow Lane will be covered when the robot visit it again...86
5.9A WSN deployed by applying the DFD and BSA algorithms...89
5.10The obstacle is treated as a rectangle region to simplify the deployment efficiency analysis. (a) The irregular obstacle. (b) The corresponding regular obstacle...90
5.11The experimental environments. (a) Square-shape monitoring region. (a) Square-shape monitoring region. (c) X-shape obstacle. (d) C-shape obstacle. (e) Complex obstacles. (f) Exhibition center...92
5.12The comparison of the proposed DFD with the other three existing mechanisms in terms of coverage ratio...93
5.13The DEI of the four compared mechanisms in different scenarios...94
5.14Energy consumption of DFD and BSA for handling each Dead-End problem...95
5.15Memory cost of DFD and BSA mechanisms for handling a Dead-End problem...95

List of Tables
3.1Simple Serpentine Deployment...11
3.2Check Directions for overcoming the obstacle...14
3.3Obstacle-Resistant Serpentine Movement Rule...14
3.4Simulation parameters...30
3.5Comparisons between ORRD, CED and LRV schemes in terms of the number of deployed sensor nodes in the environment containing a regular obstacle with various shapes....35
3.6Energy consumption of the ORRD, CED and LRV...40
4.1Simulation parameters...66
5.1Simulation parameters...92

References

[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]Q. Huang, C. Lu and G. C. Roman, “Spatiotemporal Multicast in Sensor Networks,” The 1st ACM international conference on Embedded networked snensor system, pp. 205–217, USA, Oct. 2003
[6]T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan and K. K. Saluja, “Sensor Deployment Strategy for Target Detection,” The 1st ACM international workshop on Wireless sensor networks and applications, pp. 42–48, USA, Sep. 2002.
[7]S. S. Dhillon and K. Chakrabarty, “Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks,” The 2003 annual IEEE Wireless Communications and Networking Conference, vol. 3, pp. 1609–1614, USA, Mar. 2003.
[8]P. Cheng, C. N. Chuah, and X. Liu, “Energy-Aware Node Placement in Wireless Sensor Networks,” The 47th annual IEEE Global Telecommunications Conference, vol. 5, pp. 3210–3214, USA, Nov. 2004.
[9]W. Li and C. G. Cassandras, “A Minimum-Power Wireless Sensor Network Self-Deployment Scheme,” The 2005 annual IEEE Wireless Communications and Networking Conference,  vol. 3, pp. 1897–1902, USA, Mar. 2005.
[10]T. L. Wong, T. Tsuchiya, and T. Kikuno, “A Self-Organizing Technique for Sensor Placement in Wireless Micro-Sensor Networks,” The 18th IEEE Internation Conference on Advanced Information Networking and Applications, vol. 1, pp. 78–83, Japan, Mar. 2004.
[11]G. Wang, G. Cao, and T. L. Porta, “A Bidding Protocol for Deploying Mobile Sensors,” The 11th IEEE International Conference on Network Protocols, pp. 315–324, USA, Nov. 2003.
[12]G. Wang, G. Cao, and T. L. Porta, “Proxy-Based Sensor Deployment for Mobile Sensor Networks,” The 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems, pp. 493–502, USA, Oct. 2004.
[13]G. Wang, G. Cao, and T. L. Porta, “Movement-Assisted Sensor Deployment,” IEEE INFOCOM 2004. 23rd annual Joint Conference of the IEEE Computer and Communication Societies, vol. 4, pp. 2469–2479, HongKong, Mar. 2004.
[14]G. Wang, G. Cao, T. L. Porta, and W. Zhang, “Sensor Relocation in Mobile Sensor Networks,” IEEE INFOCOM 2005. 24rd Annual Joint Conference of the IEEE Computer and Communication Societies, USA, Mar. 2005.
[15]S. Ganeriwal, A. Kansal and M. B. Srivastava, “Self Aware Actuation for Fault Repair in Sensor Networks,” IEEE International Conference on Robotics and Automation, vol. 5, pp. 5244–5249, Spain, Apr. 2004.
[16]A. Sekhar, B. S. Manoj, and C. S. R. Murthy, “Dynamic Coverage Maintenance Algorithms for Sensor Networks with Limited Mobility,” The 3rd IEEE International Conference on Pervasive Computing and Communications, pp. 51–60, USA, Mar. 2005.
[17]A. Ghosh, “Estimating Coverage Holes and Enhancing Coverage in Mixed Sensor Networks,” The 29th IEEE Conference on Local Computer Networks, pp. 68–76, USA, Nov. 2004.
[18]Y. C. Wang ,C. C. Hu, “Efficient Placement and Dispatch of Sensors in a Wireless Sensor Network,” IEEE Transactions on Mobile Computing, vol. 7, no. 2, pp. 262–274, Feb. 2008.
[19]M. A. Batalin and G. S. Sukhatme, “Efficient Exploration Without Localization,” IEEE International Conference on Robotics and Automation, vol. 2, pp. 2714–2719, Taiwan, Sep. 2003.
[20]M. A. Batalin and G. S. Sukhatme, “Coverage, Exploration and Deployment by a Mobile Robot and Communication Network,” The International Workshop on Information Processing in Sensor Networks, pp. 376–391, Palo Alto, Apr. 2003.
[21]M. A. Batalin and G. S. Sukhatme, “Sensor Coverage using Mobile Robots and Stationary Nodes,” The SPIE Conference on Scalability and Traffic Control in IP Networks II (Diaster Recovery Networks), pp. 269–276, USA, Aug. 2002.
[22]Y. Chiun Wang, C. C. Hu, and Y. C. Tseng, “Efficient Deployment Algorithms for Ensuring Coverage and Connectivity of Wireless Sensor Networks,” The 1st IEEE International Conference on Wireless Internet, Hungary, July 2005.
[23]Y. Mei,  Y. H. Lu,  C. S. G. Lee,  Y. C. Hu, “Energy-Efficient Mobile Robot Exploration,” IEEE International Conference on Robotics and Automation, May 2006.
[24]C. Y. Chang, C. T. Chang, Y. C. Chen and H. R. Chang, “Obstacle-Resistant Deployment Algorithms for Wireless Sensor Networks,” IEEE Transactions on Vehicular Technology, vol. 58, no. 6, pp. 2925–2941, July 2009.
[25]C. Y. Chang, J. P. Sheu, and Y. C. Chen, “Obstacle-Free and Power Efficient Deployment Algorithm for Wireless Sensor Networks,” IEEE Transactions on Systems, Man, and Cybernetics–Part A: Systems and Humans, vol. 39, no. 4, pp. 795-806. July 2009.
[26]E. Gonzilez, M. Alarcon, P. Aristiziibal, and C. Parra, “BSA: A Coverage Algorithm,” The 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, Nevada, Oct. 2003.
[27]M. A. Batalin and G. S. Sukhatme, “The Design and Analysis of an Efficient Local Algorithm for Coverage and Exploration Based on Sensor Network Deployment,” IEEE Transactions on Robotics, vol. 23, no. 4, August 2007.
[28]S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. Srivastava, “Coverage Problems in Wireless Ad-Hoc Sensor Networks,” IEEE Conference on Computer Communications, pp. 1380–1387, USA, Apr. 2001.
[29]B. Carbunar, A. Grama, J. Vitek, and O. Carbunar, “Coverage Preserving Redundancy Elimination in Sensor Networks,” The 1st Annual IEEE Communications Society Conference on IEEE SECON, USA, pp. 377–386, Oct. 2004.
[30]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.
[31]G. T. Sibley, M. H. Rahimi and G. S. Sukhatme, “Robomote: A Tiny Mobile obot Platform for Large-Scale Sensor Networks," Proceedings of the 2002 IEEE International Conference on Robotics and Automation (ICRA), Washington, USA, May 2002, pp. 1143-114.