在無線感測網路的環境中，感測器的佈建將決定監控效能及硬體成本，如何佈建最少的感測器並達到全區覆蓋，一直是無線感測網路中最重要的問題之一。由於機器人佈建通常較為規則，相較於隨機佈建而言，其可利用較少的感測器便能達到全區覆蓋的目的。在文獻中，現存的機器人佈建演算法通常都只針對單一機器人克服障礙之佈建方式進行討論，較少考慮多台機器人合作佈建的議題。為達到快速完成佈建的目的，本論文將提出利用多台機器人合作佈建之演算法以提升全區佈建的效率。

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.