目前已有許多透過無線感測網路應用於野生動物棲息地的監控、惡意敵軍的偵測和生態氣候的觀察，一般而言會利用隨機撒佈大量的靜態感測節點在特定的感測區域，並且利用一個偵測機率去決定目標物是否出現，最後將感測到的資料數據回報給決策中心，由決策中心進行決策。但是此方法容易因靜態感測節點分佈不均，導致整個無線感測網路通訊不佳，同時回收的感測資料也易造成決策中心進行錯誤的判斷。另外，距離決策中心較近的靜態感測節點由於一直在進行資料轉送的工作，形成熱點問題，易耗損該靜態感測節點的電量，使得無線感測網路的生命週期縮短，造成感測工作中斷。
因此，本篇論文利用動態感測節點取代靜態感測節點來進行感測工作，一個感測節點路徑規劃的品質，可以以監測範圍中，偵測機率最低的地點為標準，即此監控範圍最弱的地點，若一路徑規劃能提升此最弱地點的偵測機率，則代表此路徑規劃的品質較好。在此篇論文中，我們提出了一個利用動態感測節點進行感測資料蒐集的方法稱為關鍵式選擇感測位置路徑規劃機制 (Critical Sensing Location Path planning，CSLP)，利用動態感測節點有效率地蒐集感測資料，提升監控範圍中最弱地點的偵測機率，同時規劃動態感測節點在感測區域中的行走路徑，並且也考慮了在無障礙物情況下，利用多個動態感測節點負責分擔感測工作，期望每一個動態感測節點所負責的路徑長度是近似相等的，並達到動態感測節點之間負載的平衡。
我們將在模擬實驗中展現關鍵式選擇感測位置路徑規劃機制無論障礙物是否存在，皆能有較佳的偵測機率，並且能夠有效地規劃動態感測節點的行經路線，達到負載平衡。

Wireless sensor networks have been used for a variety of purposes such as wildlife habitats monitoring, malicious enemy detection, and climate observation. Conventionally, stationary sensors are used to carry out sensing tasks. However, stationary sensors could lead to many problems such as communication overhead and coverage holes.
This thesis investigates the problem of detecting a target or event using mobile sensors in a region with or without obstacles. The goal is to maximize the worst-case detection probability over the monitored region and reduce patrolling length of mobile sensors. An approach, namely critical sensing location path planning (CSLP), is developed to guide mobile sensors in order to collect data in an efficient way. CSLP directs mobile sensors to take measurements at carefully selected locations and reduces the patrolling path by solving a Travelling Salesman Problem. The proposed method can be used for cases either in the presence or absence of obstacles. Moreover, the thesis considers load balance problem if multiple mobile sensors are used. A method based on K-means clustering algorithm is developed to balance patrolling load for each sensor.
The performance of CSLP is shown by simulations for regions with and without obstacles. The results show that CSLP is an effective solution for the proposed mobile sensing architecture in terms of detection probability and patrolling path length of mobile sensors. In addition, the performance of the K-means clustering based balance algorithm is compared to one based on a minMax clustering algorithm. Simulation results show that the former outperforms the later in balancing patrolling length for each sensor.

[1] D. Estrin; L. Girod; G. Pottie; M. Srivastava, “Instrumenting the world with wireless sensor networks” in Proc. IEEE International Conf. Acoustics, Speech, and Signal Processing, ICASSP’01, vol. 4, Salt Lake City, Utah, USA, May 2001, pp. 2033-2036.
[2] Y. Zou; K. Chakrabarty, “Sensor deployment and target localization based on virtual forces” in Proc. IEEE International Conf. Infocom’03, vol. 2, San Francisco, California, USA, Mar. 2003, pp. 1293-1303.
[3] G. Wang, G. Cao, and T. L. Porta, “Movement-assisted sensor deployment,” IEEE Trans. Mobile Computing, vol. 5, no. 6, pp. 640-652, Jun. 2006.
[4] S. Chellappan, X. Bai, B. Ma, D. Xuan, and C. Xu, “Mobility limited flip-based sensor networks deployment,” IEEE Trans. Parallel and Distributed Systems, vol. 18, no. 2, pp. 199-211, Feb. 2007.
[5] M. Ma and Y. Yang “Adaptive triangular deployment algorithm for unattended mobile sensor networks,” IEEE Trans. Computers, vol. 56, no. 7, pp. 946-958, Jul. 2007.
[6] Y. -C. Wang, C.-C Hu, and Y.-C. Tseng, “Efficient placement and dispatch of sensors in a wireless sensor network,” IEEE Trans. Mobile Computing, vol. 7, no. 2, pp. 262-274, Feb. 2008.
[7] S. Yang, M. Li, and J. Wu, “Scan-based movement-assisted sensor deployment methods in wireless sensor networks,” IEEE Trans. Parallel and Distributed Systems, vol. 18, no. 8, pp. 1108-1120, Aug. 2007.
[8] P. Juang; H. Oki; Y. Wang; M. Martonosi; L. Peh; D. Rubenstein, “Energy- efficient computing for wildlife tracking design tradeoffs and early experiences with zebranet” in Proc. International Conf. Architectural Support for Programming Languages and Operating Systems, ASPLOS’02, vol. 37, San Jose Fairmont, San Jose, CA, Oct. 2002, pp. 96-107.
[9] T. Small and Z. J. Hass, “The shared wireless infestation model - a new ad hoc networking paradigm,” in Proc. ACM International Symp. Mobile Ad Hoc Networking and Computing, MobiHoc’03, Annapolis, Maryland, USA, Jun. 2003, pp. 233-244.
[10] R. Shah; S. Roy; S. Jain; and W. Brunette, “Data MULEs: Modeling a three-tier architecture for sparse sensor networks” in Proc. IEEE International Workshop Sensor Network Protocols and Applications, SNPA’03, Anchorage, Alaska, May 2003, pp. 30-41.
[11] D. Jea; A. Somasundara; M. Srivastava, “Multiple controlled mobile elements (data mules) for data collection in sensor networks” in Proc. IEEE International Conf. Distributed Computing in Sensor Systems, DCOSS’05, vol. 3560, Marina del Rey, CA, USA, Jun. 2005, pp. 244-257.
[12] E. Saad; M. Awadalla; R. Darwish, “A data gathering algorithm for a mobile sink in large-scale sensor networks” in Proc. IEEE International Conf. Wireless and Mobile Communications, ICWMC’08, Athens, Greece, Jul. 2008, pp. 207 - 213.
[13] G. Xing, T. Wang, W. Jia, and M. Li, “Rendezvous design algorithms for wireless sensor networks with a mobile base station” in Proc. ACM International Symp. Mobile Ad Hoc Networking and Computing, MobiHoc’08, New York, USA, May 2008.
[14] D. Bote; K. Sivalingam; P. Agrawal, “Data gathering in ultra wide band based wireless sensor networks using a mobile node” in Proc. IEEE International Conf. Broadband Communications, Networks and Systems, BROADNETS’07, Raleigh, North Carolina, USA, Sep. 2007, pp. 346-355.
[15] S. Gao, H. Zhang, and S. K. Das, “Efficient data collection in wireless sensor networks with path-constrained mobile sinks,” IEEE Trans. Mobile Computing, vol. 10, no. 4, pp. 592-608, Apr. 2011.
[16] J. Luo; J. P. Hubaux, “Joint mobility and routing for lifetime elongation in wireless sensor networks” in Proc. IEEE Infocom, vol. 3, Miami, USA, 13~17 Mar. 2005, pp. 1735-1746.
[17] A. A. Somasundara, A. Ramamoorthy, and M. B. Srivastava, “Mobile element scheduling with dynamic deadlines,” IEEE Trans. Mobile Computing, vol. 6, no. 4, pp. 395-410, Apr. 2007.
[18] W. Wang, V. Srinivasan, and K. C. Chua, “Extending the lifetime of wireless sensor networks through mobile relays,” IEEE/ACM Trans. Networking, vol. 16, no. 5, pp. 1108-1120, Oct. 2008.
[19] B. Yuan, M. Orlowska, and S. Sadiq, “On the optimal robot routing problem in wireless sensor networks,” IEEE Trans. Knowledge and Data Engineering, vol. 19, no. 9, pp. 1252-1261, Sep. 2007.
[20] Y.-C. Wang, W.-C. Peng, and Y.-C. Tseng, “Energy-balanced dispatch of mobile sensors in a hybrid wireless sensor network,” IEEE Trans. Parallel and Distributed Systems, vol. 21, no. 12, pp.1836-1850, Dec. 2010.
[21] T.-L. Chin, “Sensor deployment for collaborative target detection in the presence of obstacles” in Proc. IEEE Global Telecommunications Conf. GLOBECOM'09, Honolulu, HI, 30 Nov. ~ 4 Dec. 2009, pp. 1-5.
[22] M. Hata, “Empirical formula for propagation loss in land mobile radio service,” IEEE Trans. Vehicular Technology, vol. 29, no. 3, pp. 317–325, Aug. 1980.
[23] D. L. Applegate, R. E. Bixby, V. Chv tal, and W. J. Cook, The Traveling Salesman Problem : A Computational Study, Princeton: Princeton University Press, 2006.
[24] P. Brito, P. Bertrand, G. Cucumel, and F. de Carvalho, Selected Contributions in Data Analysis and Classification, New York: Springer, 2007.