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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2906201210060400
中文論文名稱 應用於無線感測網路未知區域之機器人佈建機制
英文論文名稱 Robot-Based Deployment Mechanism for Wireless Sensor Networks in Unknown Region
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 100
學期 2
出版年 101
研究生中文姓名 吳宥樺
研究生英文姓名 You-Hua Wu
學號 699411392
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2012-05-22
論文頁數 90頁
口試委員 指導教授-顏淑惠
委員-顏淑惠
委員-王英宏
委員-陳振炎
委員-廖弘源
委員-徐嘉連
中文關鍵字 克障  感測器佈建  全區覆蓋  無線感測網路 
英文關鍵字 obstacle-free  sensor deployment  full coverage  wireless sensor networks 
學科別分類 學科別應用科學資訊工程
中文摘要 在無線感測網路(Wireless Sensor Networks, WSNs)中,要如何利用機器人在未知的區域場景中進行佈建機制是個重要的議題之一。以ORRD(Obstacle-Free Robot Deployment Mechanism, ORRD)演算法為基礎,本文所提出的佈建機制在不失全區覆蓋(Full Coverage)的前提下,利用最少數量的感測器(Sensor),克服了未知區域場景下可能帶有障礙物的狀況,並且適用於多個機器人協同合作。機器人可利用全球衛星定位系統裝置(Global Positioning System Device, GPS Device)來得知其本身所在之位置資訊,加上雷射範圍探測器(Scanning Laser Range-Finder)偵測障礙物與邊界,並利用超音波得知與障礙物之間的距離。此外,我們延伸討論至多個機器人的場景,機器人採取獨立且非同步的移動方式。當機器人相遇,彼此會透過判斷式來更新其本身網路拓樸矩陣之資訊,達到協同合作之概念。實驗結果將證明本文所提之方法會在執行時間效率上優於傳統之作法。
英文摘要 Robot deployment in unknown region is one of the most important issues in wireless sensor networks (WSNs). Based on the Obstacle-Free Robot Deployment Mechanism (ORRD), we propose a new deployment mechanism. This mechanism attempts to use the least number of sensors to guarantee full coverage and avoid physical obstacles in unknown region. In addition, it also supports multiple robots cooperation method. Robots use Global Positioning System device (GPS devices) to know their position, and attach scanning laser range-finder to detect obstacles and boundaries of the ROI. We extend the mechanism to support multiple robots that move independently and asynchronously. When robots meet each other, they will determine how to update their network topology matrix to ensure cooperation. The simulation results show that the mechanism is more efficient in execution time than traditional mechanism.
論文目次 目錄 III
圖目錄 V
表目錄 VIII
第一章 緒論 1
1-1 研究背景 2
1-2 研究動機 4
1-3 研究目的 6
1-4 論文架構 7
第二章 相關背景與研究 8
2-1 Least Recently Visited Algorithm (LRV) 9
2-2 Obstacle-Free and Power Efficient Deployment Algorithm (OFPE) 11
2-3 Obstacle-Free Robot Deployment Mechanism (ORRD) 14
2-4 Back-Tracking Deployment (BTD) 20
第三章 應用於無線感測網路未知區域之機器人佈建機制 24
3-1 網路環境設定 25
3-2 感測器放置方式 26
3-3 機器人佈建機制 28
3-3-1 單一機器人 31
3-3-2 多個機器人 40
3-3-3 佈建流程圖 58
第四章 模擬與分析 61
4-1 模擬環境 62
4-2 模擬結果分析與比較 64
第五章 結論與未來研究方向 75
5-1 結論 75
5-2 未來研究方向 76
參考文獻 77
附錄–英文論文 83

圖目錄
圖 2.1 LRV演算法範例 9
圖 2.2.1 螺旋型移動 11
圖 2.2.2 OFPE演算法克服障礙物之範例 12
圖 2.2.3 OFPE演算法缺點 13
圖 2.3.1 SLD演算法範例 15
圖 2.3.2 SLD演算法造成空洞問題範例 16
圖 2.3.3 ORRD演算法佈建完成範例 18
圖 2.3.4 ORRD演算法缺點 19
圖 2.4.1 BTD演算法執行後退機制範例 21
圖 2.4.2 BTD演算法機器人佈建完成行走路徑 22
圖 2.4.3 BTD演算法多個機器人場景範例 23
圖 3.1 對於sensor si、sj、sk之最佳佈建方式 26
圖 3.2 機器人運作機制流程圖 30
圖 3.3(a) 佈建演算法 32
圖 3.3(b) 佈建演算法範例對應矩陣 33
圖 3.4 遭遇障礙物範例 34
圖 3.5(a) 死路情況範例一 35
圖 3.5(b) 死路情況矩陣範例一 35
圖 3.6(a) 死路情況範例二 36
圖 3.6(b) 死路情況矩陣範例二 36
圖 3.7 後退運算路徑 38
圖 3.8 單一機器人全區覆蓋 39
圖 3.9 粉紅色機器人遇到其他機器人所佈建之感測器情況情況 42
圖 3.10(a) 粉紅色機器人發送訊息交換封包 43
圖 3.10(b) 粉紅色機器人發送訊息交換封包矩陣範例 43
圖 3.11(a) 粉紅色機器人佈建完成 44
圖 3.11(b) 粉紅色機器人後退至編號6感測器矩陣範例 45
圖 3.12 白色機器人遇到其他機器人所佈建之感測器情況情況 46
圖 3.13 白色機器人與粉紅色機器人佈建完成 46
圖 3.14 機器人相遇更新網路拓樸矩陣之判斷式 50
圖 3.15 白色機器人與粉紅色機器人相遇場景範例一 51
圖 3.16(a) 機器人相遇場景範例一之粉紅色機器人矩陣更新前 52
圖 3.16(b) 機器人相遇場景範例一之粉紅色機器人矩陣更新後 52
圖 3.17(a) 機器人相遇場景範例一之白色機器人矩陣更新前 53
圖 3.17(b) 機器人相遇場景範例一之白色機器人矩陣更新後 53
圖 3.18 白色機器人與粉紅色機器人相遇場景範例二 54
圖 3.19(a) 機器人相遇場景範例二之粉紅色機器人矩陣更新前 54
圖 3.19(b) 機器人相遇場景範例二之粉紅色機器人矩陣更新後 55
圖 3.20(a) 機器人相遇場景範例二之白色機器人矩陣更新前 55
圖 3.20(b) 機器人相遇場景範例二之白色機器人矩陣更新後 56
圖 3.21 機器人相遇場景範例之全區覆蓋 57
圖 3.22 機器人佈建階段流程圖 60
圖 4.1 模擬環境圖 63
圖 4.2 單一機器人在不同區域環境下覆蓋率比較 64
圖 4.3 多個機器人在不同區域環境下覆蓋率比較 65
圖 4.4 單一機器人至多個機器人在(a)區域環境下覆蓋率比較 66
圖 4.5 單一機器人至多個機器人在(c)區域環境下覆蓋率比較 67
圖 4.6 單一機器人至多個機器人在(e)區域環境下覆蓋率比較 68
圖 4.7 單一機器人至多個機器人在(a)區域環境下佈建效率比較 69
圖 4.8 單一機器人至多個機器人在(c)區域環境下佈建效率比較 70
圖 4.9 單一機器人至多個機器人在(e)區域環境下佈建效率比較 70
圖 4.10 單一機器人在不同區域環境下網路中訊息封包量比較 71
圖 4.11 多個機器人在不同區域環境下網路中訊息封包量比較 73

表目錄
表2.3.1、SLD演算法佈建優先權表 14
表2.3.2、克服障礙物之機器人移動方向規則表 17
表2.3.3、ORRD演算法規則表 17
表3.1、ACK格式表 41
表3.2、機器人相遇更新其本身網路拓樸矩陣表 49

參考文獻 [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] J.L. Hill and D.E. Culler, “Mica: A Wireless Platform for Deeply Embedded Network,” IEEE Micro, vol. 22, no. 6, pp.12 – 24, November 2002.
[3] I. Mahgoub and M. Ilyas, “Sensor Network Protocols,” 2006.
[4] J. M. Kahn, R. H. Katz and K. S. J. Pister, “Next Century Challenges: Mobile Networking for Smart Dust,” in Proc. the 5th annual ACM/IEEE international conference on Mobile computing and networking, August 1999.
[5] T. Arampatzis, J. Lygeros and S. Manesis, “A Survey of Applications of Wireless Sensors and Wireless Sensor Networks,” in Proc. IEEE International Symposium on Mediterrean Conference on Control and Automation Intelligent Control, pp.719 – 724, June 2005.
[6] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, “Wireless Sensor Networks: A Survey,” Journal of Computer Networks, vol. 38, no. 4, pp. 393 – 422, March 2002.
[7] N. Tamboli and M. Younis, “Coverage-Aware Connectivity Restoration in Mobile Sensor Networks,” in Proc. IEEE International Conference on Communications (ICC), pp. 1–5, June 2009.
[8] T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan and K. K. Saluja, “Sensor Deployment Strategy for Target Detection,” in Proc. the 1st ACM international workshop on Wireless sensor networks and applications, pp. 42 – 48, September 2002.
[9] G. S. Gaba, K. Singh and B.S. Dhaliwal, “Sensor Node Deployment using Bacterial Foraging Optimization,” in Proc. Recent Trends in Information Systems (ReTIS), pp. 73–76, December 2011.
[10] S .Xiong, Y. Lei, H. Shen, C. Wang and W. Lu, “Efficient Algorithms for Sensor Deployment and Routing in Sensor Networks for Network-structured Environment Monitoring,” in Proc. IEEE INFOCOM, pp. 1008 – 1016, March 2012.
[11] S. S. Dhillon and K. Chakrabarty, “Sensor Placement for Effective Coverage and Surveillance in Distributed Sensor Networks,” in Proc. IEEE Wireless Communications and Networking Conference, vol. 3, pp. 1609 – 1614, March 2003.
[12] K. B. Khajeh, M. A. J. Jamali and H. M. Manie, “ACDS: Adaptive Topology Construction for R-random Sensor Deployment in Wireless Sensor Networks,” in Proc. 12th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD), pp. 139 – 144, July 2011.
[13] N. Ahmed, S. S. Kanhere and S. Jha, “The Holes Problem in Wireless Sensor Networks: A Survey,” ACM SIGMOBILE Mobile Computing and Communications Review, vol. 9, no. 2, pp. 4 – 18, April 2005.
[14] N. Tamboli and M.Younis, “Coverage-Aware Connectivity Restoration in Mobile Sensor Networks,” in Proc. IEEE International Conference on Communications (ICC), pp. 1–5, June 2009.
[15] N. Bartolini, T. Calamoneri, T. LaPorta and S. Silvestri, “Mobile Sensor Deployment in Unknown Fields,” in Proc. IEEE INFOCOM, pp. 1 – 5, March 2010.
[16] M. A. Batalin and G. S. Sukhatme, “Efficient Exploration without Localization,” in Proc. IEEE International Conference on Robotics and Automation (ICRA), vol.2, pp.2714 – 2719, September 2003.
[17] S. Ganeriwal, A. Kansal and M. B. Srivastava, “Self Aware Actuation for Fault Repair in Sensor Networks,” in Proc. IEEE International Conference on Robotics and Automation (ICRA), vol. 5, pp.5244 – 5249, April 2004.
[18] R. Soua, L. Saidane and P. Minet, “Sensors Deployment Enhancement by a Mobile Robot in Wireless Sensor Networks,” in Proc. the 9th International Conference on Networks (ICN), pp. 121 – 126, April 2010.
[19] Y. Mei, Y. H. Lu, Lee, C. S. Lee and Y. Hu, “Energy-Efficient Mobile Robot Exploration,” in Proc. IEEE International Conference on Robotics and Automation (ICRA), pp. 505 – 511, May 2006.
[20] M. A. Batalin and G. S. Sukhatme, “Efficient Exploration Without Localization,” in Proc. IEEE International Conference on Robotics and Automation (ICRA), vol. 2, pp.2714 – 2719, May 2003.
[21] M. A. Batalin and G. S. Sukhatme, “Coverage, Exploration and Deployment by a Mobile Robot and Communication Network,” Journal of Telecommunication Systems, vol.26, pp.181 – 196, June 2004.
[22] C. Y. Chang, J. P. Sheu, Y. C. Chen and S. W. Chang, “An 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.
[23] 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.
[24] C. Y. Chang, H. R. Chang, C. C. Hsieh and C. T. Chang, “OFRD: Obstacle-Free Robot Deployment Algorithms for Wireless Sensor Networks,” in Proc. IEEE Wireless Communications and Networking Conference (WCNC), pp. 4371 – 4376, March 2007.
[25] G. Fletcher, X. Li, A. Nayak and I. Stojmenovic, “Back-Tracking based Sensor Deployment by a Robot Team,” in Proc. the 7th Annual IEEE Communications Society Conference on Sensor Mesh and Ad Hoc Communications and Networks (SECON), pp. 1 – 9, June 2010.
[26] Y. C. Wang, C. C. Hu and Y. C. Tseng, “Efficient Deployment Algorithms for Ensuring Coverage and Connectivity of Wireless Sensor Networks,” in Proc. the 1st IEEE International Conference on Wireless Internet, pp. 114 – 121, July 2005.
[27] J. H. Jung, S. Park and S. L. Kim, “Multi-Robot Path Finding with Wireless Multihop Communications,” IEEE Communications Magazine, vol. 48, no. 7, pp. 126 – 132, July 2010.
[28] “RF Transceiver,” http://wiki.dzsc.com/info/7375.html
[29] “RF Transceiver,”
http://www.2cm.com.tw/windowofplayers_content.asp?sn=1202020008
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2012-07-03公開。
  • 同意授權瀏覽/列印電子全文服務,於2017-07-03起公開。


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