現今Wireless sensor networks (WSNs)已廣泛地應用在環境偵測與軍事作戰監控系統，如何將大量的sensor nodes佈置於特定欲監測區域內，並維持高效率的監測效能是個重要的議題。本論文研發一機器人在WSNs佈點、修復及回Home的演算法，我們所研發的佈點演算法使機器人能快速且花費最少的sensors nodes數量佈點於欲監測區域，並有效地避開障礙物，且機器人在行走過程中留下其行走的軌跡，使WSN中的sensor nodes皆能追蹤機器人的位置資訊，並能以較短路徑發送修復封包以通知機器人進行毀損修復，使機器人能以動態、快速、省電及有效率的方式往修復區移動。此外，Home演算法提供機器人在進行修復的過程中，能以剩餘電量來安排較佳行走路徑，以達到回Home充電及補充新的sensors的目的，使WSNs的覆蓋範圍得以更有效地維護。實驗顯示本論文所提出的演算法可以使網路中的sensor nodes有效掌握機器人的移動軌跡，並利用此資訊提供機器人一個動態且快速的巡邏及修復演算法。

Node deployment and failure recovery are important issues in Wireless sensor networks (WSNs). This paper presents efficient robot deployment, repair, and home algorithms, namely ODRH.  With the development of node placement policy, snake-like movement policy, and obstacle handling rules, the robot rapidly deploys sensor nodes to achieve full sensing coverage by using minimal number of sensor nodes even though there exists unpredicted obstacles. The robot leaves a footmark while it moves around the networks. An x-correction mechanism is employed for neighboring sensors of failure node to learn a better route for sending repair request to the robot with low overhead in control packet and power consumption. On receiving several failure notifications, the robot establishes an optimal route that uses shortest path to pass through and repair all failure regions with minimal overhead in time and power consumption. In addition, the route construction for redeployment also considers back to home for robot to recharge energy or supply new sensors. Protocols developed in this paper efficiently take minimal time and consume minimal energy to deploy sensors and recover failure regions. Performance results reveal that the developed protocols can efficiently obtain the trace of robot movement. By exploiting the footmark information, the robot can dynamically and rapidly patrol the sensing region and repair the failure region.

目錄
第一章、緒論 1
第二章、環境與基本概念 5
2.1、Network Environment 5
2.2、Basic Concepts 5
第三章、克服障礙物之機器人佈點技術 14
3.1、Simple Snake-Like Robot Deployment 14
3.2、Obstacle-Free Snake-Like Robot Deployment 16
3.2.1、Obstacle Handling Algorithm 17
3.2.2、Boundary Handling Algorithm 23
3.3、Information Maintainence 36
第四章、節省電量之毀損修復技術 44
4.1、No Obstacle Environment 44
4.2、Obstacle Environment 47
第五章、效能評估 52
5.1、Simulation Model 52
5.2、Performance Study of ODR 54
5.3、Comparative Study 59
第六章、結論 67
參考文獻 68

圖目錄
圖(一)：機器人佈點的規則與蛇行狀佈點法 7
圖(二)：機器人修復所有待修復的sensor nodes的方法 9
圖(三)：Sensor nodes追蹤robot路徑過長的情形 10
圖(四)：以機器人所剩餘的電量來看Home存在的重要性 12
圖(五)：簡單的蛇行狀佈點容易有空洞或區域沒有佈點的情形 17
圖(六)：簡易蛇行狀佈法產生的空洞有內凹的情形 17
圖(七)：東南西北四個方向因障礙物或邊界與機器人行走方向垂直而產生空洞的情形 29
圖(八)：機器人行走方向與障礙物邊界方向同向所產生的邊界空洞問題 34
圖(九)：X-correction mechanism 41
圖(十)：利用X-correction packet來修正sensor nodes追蹤機器人路徑過於彎曲且長的情形 43
圖(十一)：Repair algorithm considering the energy of robot 46
圖(十二)：Algorithm of probe packet 48
圖(十三)：在Obstacle environment中，Repair Phase的執行方法 51
圖(十四)：Snapshots of the deployment of ODR mechanism 57
圖(十五)：The control packet overhead of various counter value correction mechanisms 61
圖(十六)：The average track distance from failure sensors to robotby applying various correction mechanisms 62
圖(十七)：The average track distance of failure sensors to robot byapplying X-correction mechanism in varying distance 63
圖(十八)：Comparison of ODR and CED in delay time 64
圖(十九)：Comparison of ODR and CED in repair efficiency 65
圖(二十)：Comparison of ODR and CED in coverage ratio 66

表目錄
Table I：Snake-like Deployment 15
Table II：為了克服障礙物的Check Directions 19
Table III：Check Direction 2的細節 23
Table IV：Prefer Direction 2的細節 23
Table V：Obstacle-Free Snake-Like Movement Rule 23
Table VI：Simulation parameters 52
Table VII：Deployment time of ODR and CED in different environment 59
Table VIII：Comparison of the number of sensors deployed by applying ODR and CED schemes in different environment 59

[1] M. A. Batalin and G. S. Sukhatme, “Efficient Exploration without Localization,” in IEEE International Conference on Robotics and Automation (ICRA), Taipei, Taiwan, May 2003, pp. 2714–2719. 
[2] 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, 1997,  Vol. 9, No. 2-3, pp. 323-336.
[3] P. Pirjanian, “Behavior coordination mechanisms-state-of-the-eart,” Technic Report, Institute for Robotics and Intelligent Systems, University of Southern California, October 1999, IRIS-99-375.
[4] M. A. Batalin and G. S. Sukhatme, “Coverage, Exploration and Deployment by a Mobile Robot and Communication Network,” in Proceedings of the International Workshop on Information Processing in Sensor Network (IPSN), Palo Alto, Apr 2003, pp. 376-391.
[5] M. A. Batalin, G. S. Sukhatme and M. Hattig, “Mobile Robot Navigation using a Sensor Network,” in Proceedings of the IEEE International Conference on Robotics & Automation (ICRA), New Orleans, LA, April 2004, pp. 636-642.
[6] Y. Zou and K. Chakrabarty, “Sensor deployment and Target Localization in Distributed Sensor Networks,” in ACM Tranactions on Embedded Computing Systems (TECS), New York, February, vol. 3, pp.61-91.
[7] Y. C. Wang, C. C. Hu, and Y. C. Tseng, “Efficient Deployment Algorithms for Ensuring Coverage and Connectivity of Wireless Sensor Networks,” in Wireless Internet Conf. (WICON), 2005.
[8] Q. Huang, C. Lu, and G. C. Roman, “Reliable Mobicast via Face-Aware Routing,” in Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), March 2004
[9] B. Karp and H. T. Kung, “GPSR:Greedy Perimeter Stateless Routing for Wireless Networks,” in Proceedings of International Conference on Mobile Computing and  Networking (MobiCom), Boston, Massachusetts, August 2000, pp. 243-254.
[10] S. Ganeriwal, A. Kansal and M. B. Srivastava, “Self Aware Actuation for Fault Repair in Sensor Neworks,” in IEEE International Conference on Robotics and Automation (ICRA), April 2004.
[11] G. T. Sibley, M.H. Rahimi, G. S. Sukhatme, “Robomote: A Tiny Mobile Robot Platform for Large-Scale Sensor Networks,” in IEEE International Conference on Robotics and Automation (ICRA), Washington DC, May 2002, pp. 1143-1148.
[12] 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.