目標物覆蓋(Target Coverage)問題在無線感測網路中一直受到廣泛的討論，本論文考慮監控場景中存在許多我們所感興趣的位置(Points of Interest ( POIs ))，其分散於不連續的區域中，若以固定式感測器佈建整個網路，將佈建數量龐大的感測器，造成佈建成本昂貴，而收集資料時亦造成耗電量不均以及感測器不亦充電的問題。因此，本論文以具移動性之行動資料蒐集裝置(Data Mule)來達成網路的連通及目標物監控或資訊收集等目的。本論文首先提出了Time-Constrained Weighted Targets Patrolling (TCWTP) Algorithm，使分處於各地的Mobile Data Mules以分散式的方式，在POIs之間建置出有效率的巡邏路徑，進行感測及資料蒐集的任務。不同於以往的研究，本論文考慮所有POIs具有不同的權重值，Data Mule對於重要性較高的POIs，將給予其較高的感測與拜訪頻率，以提高其資料更新之速度‧此外，本論文亦針對Mobile Spatial Coverage的議題，考慮監控場景中存在許多不具感測與通訊能力的目標物(POIs)，並解決前述目標物監控所遭遇的硬體成本、目標物監控品質以及Data mules電量等三大挑戰。

This thesis first considers the weighted target patrolling problem which asks a set of mobile data mules (DMs) to efficiently patrol a set of given weighted targets. A patrolling algorithm, called Time-Constrained Weighted Target Patrolling (TCWTP), is presented aiming to construct an efficient patrolling route for a number of given data mules such that  targets with higher weights have higher visiting frequency and the overall visiting frequency is stable. Performance study demonstrates that the proposed algorithm outperforms existing approaches in terms of patrolling delay and quality of monitoring.

目錄
圖目錄	V
表目錄	VII
第一章 Introduction	1
第二章 Related Work	5
第三章 TCWTP Algorithm	9
3.1 Network Environment and Problem Formulations	10
3.1.1 Network Model	10
3.1.2 Problem Formulations	11
3.2 Basic Concept	14
3.3 TCWTP Algorithm	18
3.3.1 Paths Construction Phase	18
3.3.2 Position Initialization	23
3.3.3 Speed Control Phase : Target Base Policy	32
3.4 Performance Study	38
3.4.1 Simulation Model	38
3.4.2 Performance Study	39
第四章 Data Mule Recharging Mechanism	51
4.1 Network Model and Problem formulations	52
4.1.1 Network Model	52
4.1.2 Problem Formulations	54
4.2 Basic Concept and Challenges	61
4.3 Algorithm	67
4.3.1 Location Initialization Phase	68
4.3.2 Path Construction Phase	69
4.3.3 System Stable Phase	69
4.3.4 Monitoring and Data Collection Phase	75
4.3.5 Data Mule State Diagram	83
4.4 Performance Study	87
4.4.1 Simulation Model	87
4.4.2 Performance Study	88
第五章 Conclusions	91
References	92
附錄—英文論文	96

圖目錄
圖(3.1) 網路環境	11
圖(3.2) Data Collection Network Environment	14
圖(3.3)(a) Weighted patrolling route H1	15
圖(3.3)(b) Weighted patrolling route H2	15
圖(3.4) Ideal Schedule for each target node	16
圖(3.5) Target Base Policy - Speed Control	17
圖(3.6) TCWTP Algorithm	18
圖(3.7) TCWTP Path Construction Algorithm	23
圖(3.8)(a) 迴路權重值(wiH)相等	25
圖(3.8)(b) 迴路長度( |Hi| )相等	25
圖(3.9) Initialization - Breaking Point	31
圖(3.10)(a) Respective frequency of target	33
圖(3.10)(b) Unstable frequency	34
圖(3.10)(c) Stable frequency	34
圖(3.11) 巡邏路徑切分速度調整路段	35
圖(3.12) Speed Control Phase	37
圖(3.13) 行動感測網路中目標物覆蓋演算法之AVI比較	40
圖(3.14) 行動感測網路中目標物每次被拜訪之AVI	41
圖(3.15)(a) 尚未進行速度控制機制在VIP數及權重值大小不同時之AVI比較	42
圖(3.15)(b) 速度控制機制在VIP數及權重值大小不同時之AVI比較	43
圖(3.16) 行動感測網路中目標物覆蓋演算法之SD比較	44
圖(3.17) 行動感測網路中目標物覆蓋演算法之SD比較	45
圖(3.18) 六大監控場景	46
圖(3.19) 六大監控場景所需的DMs個數比較	47
圖(3.20) 路徑毀損對目標物監控品質影響之比較	49
圖(3.21) POI被DMs拜訪之公平性比較	50
圖(4.1) 網路環境	53
圖(4.2) 所建置之資料回傳與充電路徑	61
圖(4.3) 目標物g3上DM電量狀態	65
圖(4.4) 目標物g4上DM電量狀態	65
圖(4.5) DM m4充電門檻值之電量示意圖	78
圖(4.6) DM電量狀態圖	83
圖(4.7) Energy Efficient Recharging Algorithm	86
圖(4.8) 充電機制中DMs的平均剩餘電量之觀察	89
圖(4.9) DM充電之成本效益	90

表目錄
表(3.1) 模擬參數	38
表(4.1) 問題描述之符號定義	55
表(4.2) 模擬參數	87

[1]	C. Liu, K. Wu, Y. Xiao, and B. Sun, “Random Coverage with Guaranteed Connectivity: Joint Scheduling for Wireless Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 6, June 2006, pp. 562–575. 
[2]	Z. Yun, X. Bai, D. Xuan, T. H. Lai, and W. Jia, “Optimal Deployment Patterns for Full Coverage and k-Connectivity (k ≤ 6) Wireless Sensor Networks,” IEEE/ACM Transactions on Networking, vol. 18, no. 3, June 2010, pp. 934–947.
[3]	J. He and H. Shi, “Finding barriers with minimum number of sensors in wireless sensor networks,” The 2010 IEEE International Conference on Communications (IEEE ICC), South Africa, May 2010. 
[4]	G. Yang and D. Qiao, “Multi-Round Sensor Deployment for Guaranteed Barrier Coverage,” The 2010 IEEE Conference on Computer Communications (IEEE INFOCOM), San Diego, March 2010.
[5]	M. Cardei, J. Wu, M. Lu, and M. O. Pervaiz, “Maximum Network Lifetime in Wireless Sensor Networks with Adjustable Sensing Ranges,” IEEE International Conference on Wireless and Mobile Computing, Networking and Communications (IEEE WiMob), August 2005.
[6]	M. Cardei, M. T. Thai, Y. Li, and W. Wu, “Energy-Efficient Target Coverage in Wireless Sensor Networks,” IEEE Computer and Communications Societies (IEEE INFOCOM), March 2005.
[7]	K. Chakrabarty, S. Iyengar, H. Qi, and E. Cho, “Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks,” IEEE Transactions on Computers, vol. 51, no. 12, December 2002, pp. 1448–1453.
[8]	B. Liu, P. Brass, O. Dousse, P. Nain and D. Towsley, “Mobility Improves Coverage of Sensor Networks,” ACM international symposium on Mobile ad hoc networking and computing (ACM MobiHoc), USA, May 2005.
[9]	C. Y. Chang, S. W. Chang and S. Y. Hsu, “A Decentralized Hole-Shape Regulation Technique for Enhancing Patrol and Deployment Tasks in Mobile WSNs,” The 2007 IEEE/ACM International Conference on Mobile Adhoc and Sensor Systems (IEEE/ACM MASS), Italy, October 2007.
[10]	J. Du, Y. Li, H. Liu and K. Sha, “On Sweep Coverage with Minimum Mobile Sensors,” The 2010 IEEE International Conference on Parallel and Distributed Systems (IEEE ICPADS), Shanghai China, December 2010. 
[11]	M. Li, W. Cheng, K. Liu, Y. He, X. Y. Li and X. Liao, “Sweep Coverage with Mobile Sensors,” The IEEE Transactions on Mobile Computing, vol. 10, no. 11, November 2011. 
[12]	C. Y. Chang, C. Y. Lin, C. Y. Hsieh and Y. J. Ho, “Patrolling Mechanisms for Disconnected Targets in Wireless Mobile Data Mules Networks,” The 2011 IEEE International Conference on Parallel Processing (IEEE ICPP), Taiwan, September 2011.
[13]	E. Ekici, Y. Gu and D. Bozdag, “Mobility-Based Communication in Wireless Sensor Networks,” The 2006 IEEE Communications Magazine, pp. 56-62, August 2006. 
[14]	M. Zhao and Y. Yang, “A Framework for Mobile Data Gathering with Load Balanced Clustering and MIMO Uploading,” The 2011 IEEE Conference on Computer Communications (IEEE INFOCOM), Shanghai, China, April 2011. 
[15]	G. Xing, M. Li, T. Wang, W. J and J. Huang, “Rendezvous Algorithms for Wireless Sensor Networks with a Mobile Base Station,” The 2011 IEEE Transactions on Mobile Computing, May 2011.
[16]	M. Zhao, M. Ma and Y. Yang, “Mobile Data Gathering with Space-Division Multiple Access in Wireless Sensor Networks,” The 2008 IEEE Conference on Computer Communications (IEEE INFOCOM), USA, April 2008.
[17]	M. Zhao, Y. Yang, “Data Gathering in Wireless Sensor Networks with Multiple Mobile Collectors and SDMA Technique Sensor Networks,” The 2010 IEEE Wireless Communications and Networking Conference(IEEE WCNC), Sydney, Australia, April 2010. 
[18]	R. Sugihara and R. K. Gupta, “Optimal Speed Control of Mobile Node for Data Collection in Sensor Networks,” The IEEE Transactions on Mobile Computing, vol. 9, no. 1,   January 2010, pp.127-139.
[19]	M. Padberg and G. Rinaldi, “A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems,” SIAM Review, vol. 33, no. 1, pp. 60–100, 1991.