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


系統識別號 U0002-2906201317185300
中文論文名稱 無線感測網路具克服障礙物之多機器人合作佈建演算法
英文論文名稱 A Cooperative Deployment Algorithm for Wireless Sensor Networks with Obstacles
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 101
學期 2
出版年 102
研究生中文姓名 鄧振亞
研究生英文姓名 Cheng-Ya Teng
學號 600410087
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2013-06-01
論文頁數 60頁
口試委員 指導教授-張志勇
委員-張志勇
委員-游國忠
委員-趙志明
中文關鍵字 感測器  機器人  合作佈建 
英文關鍵字 Sensor  Robot  Cooperative deployment 
學科別分類 學科別應用科學資訊工程
中文摘要 在無線感測網路的環境中,感測器的佈建將決定監控效能及硬體成本,如何佈建最少的感測器並達到全區覆蓋,一直是無線感測網路中最重要的問題之一。由於機器人佈建通常較為規則,相較於隨機佈建而言,其可利用較少的感測器便能達到全區覆蓋的目的。在文獻中,現存的機器人佈建演算法通常都只針對單一機器人克服障礙之佈建方式進行討論,較少考慮多台機器人合作佈建的議題。為達到快速完成佈建的目的,本論文將提出利用多台機器人合作佈建之演算法以提升全區佈建的效率。
英文摘要 In wireless sensor networks (WSNs), sensor deployment is an important issue which intends to deploy sensors in a given monitoring region in a way of low hardware cost and high coverage quality. In literature, some robot deployment algorithms have been proposed. Their performances are mainly determined by the obstacle-resistance capability which refers to how well the robot can overcome the Dead-End problem and deploy minimal number of sensors for achieving full coverage even though the environment contains multiple obstacles. Moreover, most of the existing robot deployment mechanisms consider only single robot for executing the deployment task. This thesis presents a multi-robot cooperative deployment algorithm for multiple robots to cooperate with each other aiming at deploying minimal number of sensors while achieving the full coverage purpose even though the given monitoring region contains unknown obstacles.
論文目次 目錄
圖目錄 V
表目錄 VII
第一章、 簡介 1
第二章、 國內外相關研究 4
第三章、 網路環境與問題描述 10
3-1 System Model 10
3-2 Problem Formulation 10
第四章、 Basic deployment 16
4-1 Moving Direction Rule 16
4-2 Horizontal and Vertical Movement Rules 17
第五章、 Single Robot DePloyment 21
5-1 Basic Idea 21
5-2 單機器人佈建演算法之設計 23
5-2.1 Normal State 24
5-2.2 Narrow Lane State 24
5-2.3 Dead-End State 25
5-2.4 Go-Back State 26
第六章、 Multiple Robots deployment 28
第七章、 實驗分析及模擬 33
7-1 佈建完成時間 34
7-2 感測範圍覆蓋率 36
7-3 合作佈建之路徑總長公平性 37
7-4 MRDFD性能模擬 39
7-4.1 機器人感測覆蓋率 39
7-4.2 機器人佈建完成時間 39
7-4.3 協助其他機器人所需行走之路徑 40
7-4.4 機器人總路徑公平性 41
7-4.5 機器人在不同分佈下的影響 42
7-4.6 機器人在不同障礙物大小的影響 46
7-5 實際場景比較 47
第八章、 結論 49
參考文獻 50
附錄-英文論文 53

圖目錄
圖一:機器人佈點問題 5
圖二:[15]研究機制問題 6
圖三:DFD改善的問題 7
圖四:DFD無法支援多機器人 8
圖五:最佳佈建 15
圖六:Basic Movement Rule 17
圖七:Basic Deployment 20
圖八:單一機器人佈建演算法 23
圖九:單機器人佈建演算法之狀態轉換圖 27
圖十:前來協助的機器人,可透過感測器中的GoBack point前往尚未佈建之區域 29
圖十一:說明 MRDFD 機器人演算法的例子 31
圖十二:MRDFD演算法之狀態轉換圖 32
圖十三:實驗場景圖 34
圖十四:各演算法進行佈建所花費的時間 35
圖十五:合作佈建BTD與MRDFD之佈建完成時間比較 36
圖十六:比較感測覆蓋率 37
圖十七:比較最大總路徑與公平性 38
圖十八:機器人在不同場景之感測覆蓋率 39
圖十九:機器人在不同場景佈建完成時間 40
圖二十:機器人支援其他機器人所行走的路徑 41
圖二十一:機器人在不同場景下佈建完成之公平性 42
圖二十二:機器人的分佈位置 43
圖二十三:機器人在不同分佈位置下所受的影響 45
圖二十四:機器人在不同場景中,完成佈建之時間 46
圖二十五:MRDFD與BTD的實際佈建過程 48

表目錄
表一:模擬參數 33
參考文獻 [1] M. A. Batalin and G. S. Sukhatme, “Efficient Exploration without Localization,” IEEE ICRA, pp. 2714–2719, Taipei, Taiwan, Sep. 2003.
[2] M. J. Mataric, “Behavior-Based Control: Examples from Navigation, Learning, and Group Behavior,” Journal of Experimental and Theoretical Artificial Intelligence, vol. 9, no. 2–3, pp. 323–336, 1997.
[3] P. Pirjanian, “Behavior coordination mechanisms-state-of-the-eart,” Tech. Rep. IRIS-99-375, Institute for Robotics and Intelligent Systems, University of Southern California, Oct. 1999.
[4] M. A. Batalin and G. S. Sukhatme, “Coverage, Exploration and Deployment by a Mobile Robot and Communication Network,” ACM IPSN, pp. 376–391, California, USA, Apr. 2003.
[5] M. A. Batalin, G. S. Sukhatme and M. Hattig, “Mobile Robot Navigation using a sensor Network,” IEEE ICRA, pp. 636–641, LA, USA, May 2004.
[6] G. Fletcher, X. Li, A. Nayak, and I. Stojmenovic, “Back-Tracking based Sensor Deployment by a Robot Team,” IEEE SECON, pp. 1–9, Boston, USA, Jun. 2010.
[7] G. Wang, G. Cao, and T. L. Porta, “Movement-Assisted Sensor Deployment,” IEEE Transactions on Mobile Computing, vol. 5, no. 6, pp. 640–652, Jun. 2006.
[8] G. Wang, G. Cao, T. L. Porta, and W. Zhang, “Sensor Relocation in Mobile Sensor Networks,” IEEE INFOCOM, pp. 2302–2312, Florida, USA, Mar. 2005.
[9] J. Hwang, D. H. C. Du, and E. Kusmierek, “Energy Efficient Organization of Mobile Sensor Networks,” ACM ICPPW, pp. 84–91, Quebec, Canada, Aug. 2004.
[10] Z. Yun, X. Bai, D. Xuan, W. Jia, and W. Zhao, “Pattern Mutation in Wireless Sensor Deployment,” IEEE/ACM Transactions on Networking, vol. 20, no. 6, pp. 1964–1977, Dec. 2012.
[11] L. Liu and H. Ma, "On Coverage of Wireless Sensor Networks for Rolling Terrains," IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 1, pp. 118–125, Jan. 2012.
[12] X. Li, D. K. Hunter, and S. Zuyev, "Coverage Properties of the Target Area in Wireless Sensor Networks," IEEE Transactions on Information Theory, vol. 58, no. 1, pp. 430–437, Jan. 2012.
[13] 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, Jul. 2009.
[14] 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, Jul. 2009.
[15] E. Gonzalez, O. Alvarez, Y. Diaz, C. Parra, and C. Bustacara, “BSA: A Complete Coverage Algorithm,” IEEE ICRA, pp. 2040–2044, Apr. 2005.
[16] C. Y. Chang, C. T. Chang, C. Y. Hsieh, C. C. Chen, and Y. C. Chen, “A Dead-End Free Deployment Algorithm for Wireless Sensor Networks with Obstacles,” ACM IWCMC, pp. 84-88, Caen, France, Jun. 2010.
[17] R. K. Jain, D. M. W. Chiu, and W. R. Hawe, “A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems,” DEC Research Report TR-301, Sep. 1984.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2018-07-01公開。
  • 同意授權瀏覽/列印電子全文服務,於2018-07-01起公開。


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