感測器部署問題是一個非常重要的研究議題於無線感測網路之中。一般而言，感測器通常是採用飛機或直升機灑落的方式來部署於場景。然而此種部署方式並無法確保感測器一定可以精準的落在我們所期待的位置上。如此一來，不可避免的將需要透過撒落大量的感測器來確保感測網路可以達到我們所需要的覆蓋程度。為了減少佈建感測網路所需之感測器數量，有學者提出可以透過移動機器人來協助搬運、部署感測器。藉由移動機器人將感測器放置在適當的位置，將可以有效地減少部署感測網路所需之感測器數量。過往研究在探討此問題時，主要是在探討如何規劃出較短的行走路徑來完成感測網路之佈建。然而我們發現過往所提出的方法，在路徑規劃長度上仍有改進的空間。因此在本研究當中，我們將提出一個新的部署路徑規劃演算法來解決上述之感測器部署問題。

The sensor deployment problem is an important issue in Wireless Sensor Networks (WSNs). Sensors are usually deployed by aircraft/helicopter airdrop. To achieve coverage requirement, a greater number of sensors may be needed. Therefore, researchers have proposed to use a mobile robot to relocate the redundant sensors. This problem is also called the carrier-based sensor deployment problem. Most research of this problem focuses on how to plan a shorter traveling path for the mobile robot to relocate the redundant sensors. However, we find that the length of the traveling path planned by the existing algorithms can be further reduced. In this study, we will focus on how to shorten the length of traveling path for the mobile robot to relocate the redundant sensors in WSNs.

目錄
圖目錄IV
表目錄V
第一章　簡介和相關研究1
第二章　環境假設以及問題定義6
2.1網路環境6
2.2問題定義6
第三章　方法概述8
3.1冗餘傳感器和未覆蓋區域的配對機制9
3.2局部配對路徑的連接機制12
3.3移動路徑長度的減少機制13
第四章　實驗模擬14
4.1	實驗1：未覆蓋區域所需要之感測器數量的變化14
4.2	實驗2：機器人之攜帶量上限的變化16
4.3	實驗3：包含未覆蓋區域之網格的百分比變化18
4.4	實驗4：未覆蓋區域之覆蓋率的成長19
第五章　結論22
參考文獻23
附錄-英文論文25

圖目錄
圖1. VORONOI DIAGRAM示意圖2
圖2. 吸引力、排斥力和合力的示意圖2
圖3. 擁有冗餘感測器之區域和未覆蓋區域的WSN示意圖8
圖4. 網格G(0,3)搜尋冗餘感測器的步驟11
圖5. 執行配對機制後的結果11
圖6. 執行連接機制後的結果11
圖7. 移動路徑長度減少機制的示例13
圖8. 移動路徑長度比較(未覆蓋區域所需之感測器數量不同)16
圖9. 比較未覆蓋區域所需之不同數量的感測器的改進率(移動路徑長度)16
圖10. 移動路徑長度比較(機器人的攜帶量不同)17
圖11. 比較機器人不同攜帶量的改進率(移動路徑長度)17
圖12. 移動路徑長度比較(未覆蓋區域之網格的百分比變化)19
圖13. 比較不同比例之未覆蓋區域網格的改進率(移動路徑長度)19
圖14. 移動路徑長度比較(未覆蓋區域之覆蓋率的成長)20
圖15. 比較未覆蓋區域之覆蓋率的成長的改進率(移動路徑長度)21

表目錄
表1. 符號表7
表2. 圖5中的3條TRAVELING PATHS12
表3. 實驗1的模擬參數15
表4. 實驗2的模擬參數17
表5. 實驗3的模擬參數18
表6. 實驗4的模擬參數20

參考文獻
[1]M.A. Batalin, G.S. Sukhatme, “Coverage, exploration, and deployment by a mobile robot and communication network,” Telecommun. Syst., vol. 26, pp. 181-196, 2004.
[2]R. Falcon, X. Li, A. Nayak, “Carrier-based focused coverage formation in wireless sensor and robot networks,” IEEE Trans. Autom. Control, vol. 56, no. 10, pp. 2406-2417, 2011.
[3]G. Fletcher, X. Li, A. Nayak, I. Stojmenovic, “Back-tracking based sensor deployment by a robot team,” Proc. IEEE SECON’10, pp. 385-393, 2010.
[4]G. Fletcher, X. Li, A. Nayak, I. Stojmenovic, “Placing sensors for area coverage in a complex environment by a team of robots,” ACM Trans. Sens. Netw., vol. 11, no. 1, pp. 3:1-3:22, 2014.
[5]S. He, X. Gong, J. Zhang, J. Chen, Y. Sun, “Curve-based deployment for barrier coverage in wireless sensor networks,” IEEE Tans. Wirel. Commun., vol. 13, no. 2, pp. 724-735, 2014.
[6]X. Liu, “A deployment strategy for multiple types of requirements in wireless sensor networks,” IEEE Trans. Cyb., vol. 45, no. 10, pp. 2364-2376, 2015.
[7]P. Lopez-Iturri, L. Azpilicueta, J.J. Astrain, E. Aguirre, E. Salinero, J. Villadangos, F. Falcone, “Implementation of wireless sensor network architecture for interactive shopping carts to enable context-aware commercial areas,” IEEE Sens. J., vol. 16, no. 13, pp. 5416-5425, 2016.
[8]R. Soua, L. Saidane, P. Minet, “Sensors deployment enhancement by a mobile robot in wireless sensor networks,” Proc. IEEE ICN’10, pp. 121-126, 2010.
[9]G. Wang, G. Cao and T.F.L. Porta, "Movement-assisted sensor deployment," IEEE Trans. Mobile Comput., vol. 5, no. 6, pp. 640-652, 2006.
[10]X. Yu, W. Huang J. Lan and X. Qian, “A novel virtual force approach for node deployment in wireless sensor network,” Proc. IEEE DCOSS’12, pp. 359-363, 2012.
[11]Y. Zou, K. Chakrabarty, “Sensor Deployment and Target Localization in Distributed Sensor Networks,” ACM Trans. Embed. Comput. Syst., vol. 3, no. 1, pp. 61-91, 2004.