淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1907200511075300
中文論文名稱 在無線感測網路中發展可克服障礙物之網路佈建及毀損修復之機器人演算法
英文論文名稱 Obstacle-Free Robot Deployment and Repair Algorithms for Wireless Sensor Networks
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 93
學期 2
出版年 94
研究生中文姓名 謝珍琪
研究生英文姓名 Chen-Chi Hsieh
學號 692190985
學位類別 碩士
語文別 中文
口試日期 2005-06-24
論文頁數 69頁
口試委員 指導教授-張志勇
委員-曾煜棋
委員-簡榮宏
委員-許健平
中文關鍵字 網路佈建  網路修復  無線感測網路  機器人  克服障礙物 
英文關鍵字 Deployment  Repair  Sensor Networks  Robot  Obstacle-Free 
學科別分類 學科別應用科學資訊工程
中文摘要 現今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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2008-07-21公開。
  • 同意授權瀏覽/列印電子全文服務,於2008-07-21起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信