目標物覆蓋(Target Coverage)在無線感測網路(Wireless Sensor Networks, WSNs)中是個很重要的研究議題。然而，在過去的研究中，大都假設目標物間相互連結。本論文所考慮的目標物(Target Points)乃分散於許多不連續區域中。為使目標物的資訊可在時限內傳達至收集站(Sink Node)，行動資料蒐集裝置(Data Mule)必須設法以移動性來達成網路的連通及目標物資訊的收集等目的。本論文提出了Time-Constrained Target Points Patrolling (TCTP) Algorithm，使分處於各地的Data Mule以分散式的方式，在目標物之間建置出一有效率的巡邏路徑，進行感測及資料蒐集的任務，並使這個路徑中每個目標物具有相近的資訊更新時間週期，並考慮Data Mule的電量限制與充電問題。此外，本論文亦針對具不同權重的目標物提出Weight-TCTP(W-TCTP) Algorithm，使Data Mule對於重要性較高的目標物，給予其較高的感測與收集頻率，提高其資料更新之速度。
除了收集目標物的路徑建外，本論文亦針對Data Mule如何在初始階段快速到達目標物進行深入研究。本論文考慮一行動感測網路之派遣問題，每個目標物依重要性不同的監控品質(Quality of Monitoring, QoM)需求，但由於行動感測器在一開始隨機散佈於環境中，使行動感測器之間並無法利用通訊能力協調所要前往的目標物，這使得行動感測器的派遣面臨極大的挑戰。本論文考慮目標物分散在各區域且不連續，為了對這些不連結的目標物進行監控，本論文發展一有效率的Mobile Sensor Dispatching Mechanism (MDM)，可使隨機散佈於環境中的行動感測器以最少的移動成本迅速的覆蓋目標物，且滿足目標物之QoM需求。此外，本論文還提出了Learning Dispatching Mechanism (L-MDM) ，使行動感測器在執行派遣工作的同時，利用與其他感測器短暫交會的機會，分享其移動經驗，使行動感測器透過可學習機制，以更高的效率覆蓋目標物且滿足目標物的QoM需求。

Target coverage problem has been widely discussed in Wireless Sensor Networks (WSNs). Different from the traditional target coverage problem, this paper considers the scenario that the target points are distributed over several disconnected areas. To collect the target information within a given time period, data mules should move and visit all target points for data collection in a disconnected network. Since the time interval (also referred to visiting interval) for consecutively visiting to each target point reflects the monitoring quality of this target point, the goal of this research is to minimize the maximal visiting interval for each target point. Given a number of data mules, this thesis initially proposes a Time-Constrained Target Points Patrolling (TCTP) algorithm which aims at constructing an efficient patrolling path for all data mules to visit each target point with a minimal visiting interval. Then a Weighted-TCTP (W-TCTP) algorithm is further proposed to cope with the weighted target problem where some targets might have higher weights and should have higher data update frequencies. In addition, this thesis consider the energy constraint of data mules and additionally proposes a RW-TCTP algorithm that treats energy recharge station as a weighted target and arranges all data mules visiting the recharge station before exhausting their energies. Simulation results reveal that the proposed TCTP and RW-TCTP mechanisms outperform the existing work in terms of visiting interval.
In addition to the path construction problem, this thesis also considers the dispatching problem. In the considered environment, each target point gi is assigned with a Quality of Monitoring (QoM) value QoMi which representing the number of data mules required for monitoring the target. The given mobile sensors are randomly distributed in the monitoring region and thus they can not communicate with each other. As a result, the key challenge of the dispatching problem is that each mobile sensor should locally construct a visiting path passing thourhg all targets such that all targets can rapaidly satisfy their own QoMs with a minimal movement cost of mobile sensors. To cope with the dispatching problem, this thesis  presents two efficient Mobile Sensor Dispatching Mechanisms (MDM) which aims to minimize the movement cost of mobile sensor while the QoM demand of each target is rapaidly satisfied. Experimental study shows that the proposed dispatching mechanism has a better performance than existing work in terms of movement cost of mobile sensors.

目錄	IV
圖目錄	V
表目錄	VIII
第一章 簡介	1
第二章 相關研究	5
第三章 Data Collection Mechanisms (DCM)	9
3.1 Network Environment and Problem Formulations	10
3.2 Basic TCTP (B-TCTP) Algorithm	13
3.3 Weighted TCTP (W-TCTP) Algorithm	15
3.3.1 Path Construction (PC) Phase	15
3.3.2 Patrolling Phase	25
3.4 W-TCTP with Recharge(RW-TCTP) Algorithm	27
3.4.1 RW-TCTP algorithm	27
3.5 Performance Study	31
3.5.1 Simulation Model	32
3.5.2 Performance Study	33
第四章 Mobile Sensor Dispatching Mechanisms (MDM)	45
4.2 Mobile Sensor Dispatching Mechanism (MDM)	51
4.2.1 Basic Dispatching Mechanism (BDM)	54
4.2.2 Pessimistic Dispatching Mechanism (PDM)	56
4.2.3 Revenue- Based Dispatching Mechanism (RDM)	67
4.3 Learning Dispatching Mechanism (L-MDM)	70
4.3.1 Learning Policy	70
4.3.2 Earlier Termination Policy	71
4.3.3 Power Control Policy	71
4.4 Performance Study	73
4.4.1 Simulation Model	73
4.4.2 Performance Study	74
第五章 結論	88
參考資料	         90
附錄—英文論文	92


圖目錄
圖(3.1) Delay-Tolerant Data Collection Network Environment  10
圖(3.2) Hamilton Patrolling Route  14
圖(3.3) Weighted-TCTP Patrolling Route  17
圖(3.4) Weighted-TCTP Patrolling Route (Weighted=x)  19
圖(3.5)(a) W-TCTP by Shortest-Length Policy  22
圖(3.5)(b) W-TCTP by Balancing-Length Policy  22
圖(3.6) W-TCTP Route Construct Algorithm  24
圖(3.7) Euler Circuit Patrolling Route  26
圖(3.8) Recharging Route  28
圖(3.9) RW-TCTP Algorithm  31
圖(3.10) 行動感測網路中目標物覆蓋演算法之SDT比較。  34
圖(3.11) 行動感測網路中目標物每次被拜訪之SDT比較。  35
圖(3.12) 行動感測網路中目標物覆蓋演算法之SD比較。  36
圖(3.13) CHB及TCTP演算法與目標物及DM數量關係之SD比較。  37
圖(3.14) 行動感測網路中目標物覆蓋演算法滿足VIP 權重值之移動成本比較。  39
圖(3.15) Shortest Policy以及Balancing Policy之SDT比較。  40
圖(3.16) Shortest Policy以及Balancing Policy之SD比較。  40
圖(3.17) Shortest Policy以及Balancing Policy在VIP數及權重值大小不同時之SDT比較。  41
圖(3.18) Shortest Policy以及Balancing Policy在VIP數及權重值大小不同時之SD比較。  42
圖(3.19) DM充電機制之能源使用效率比較。  44
圖(4.1) Mobile Sensor Dispatching Network Environment  47
圖(4.2) 行動感測器滿足目標物之QoM。  48
圖(4.3) Terminated Condition  53
圖(4.4) Basic Dispatching Mechanism  55
圖(4.5) BDM Algorithm  56
圖(4.6) Dispatching Fault  57
圖(4.7) (a) Expectant Weighted Value Calculating  60
圖(4.7) (b) Expectant Weighted Value Calculating  60
圖(4.8) eji之選擇  61
圖(4.9) Replaceable Target Node  62
圖(4.10) Cutting Rule  64
圖(4.11) Cutting Rule之運作  65
圖(4.12) PDM Algorithm  66
圖(4.13) Revenue-Based Dispatching Mechanism  68
圖(4.14) RDM Algorithm  69
圖(4.15) 目標物數量及行動感測器平均移動成本模擬。  75
圖(4.16) 目標物QoM值總及行動感測器平均移動成本模擬。  76
圖(4.17) 目標物數量及目標物QoM被滿足之感測器派遣時間模擬。  77
圖(4.18) 行動感測器總數及目標物QoM被滿足之感測器派遣時間模擬。  78
圖(4.19) 目標物QoM值總和及目標物QoM被滿足之感測器派遣時間模擬。  79
圖(4.20) 位於不同位置之目標物QoM被滿足之感測器派遣時間模擬。  80
圖(4.21) 場景中成功停留於不同位置之目標物的行動感測器所拜訪過的目標物個數模擬。  81
圖(4.22) 目標物QoM被滿足之感測器派遣時間及目標物數量及行動感測器數量之效能分析。  82
圖(4.23) 行動感測器花費在派遣工作上的能源成本及目標物數量及行動感測器數量之效能分析。  83
圖(4.24) 最短生命週期及目標物數量及行動感測器數量分析。  84
圖(4.25) MDM效能分析(QSD=5,TSD=50(m))  85
圖(4.26) MDM效能分析(QSD=1,TSD=250(m))  86
圖(4.27) MDM效能分析(QSD= 3,TSD= 150(m))  87



表目錄
表(一) Data Collection Mechanisms模擬參數  32
表(二) Mobile Sensor Dispatching Mechanisms模擬參數  73

[1]M. Cardei, M. T. Thai, Y. Li, and W. Wu, “Energy-Efficient Target Coverage in Wireless Sensor Networks,” in Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM), March 2005.
[2]W. Wang, V. Srinivasan, B. Wang, and K. C. Chua, “Coverage for Target Localization in Wireless Sensor Networks,” IEEE Transactions on Wireless Communications, vol. 7, no. 2, February 2008, pp. 667–676.
[3]Hao Li, Huifang Miao, Li Liu, Lian Li, and Heping Zhang, “Energy Conservation in Wireless Sensor Networks and Connectivity of Graphs,” Theoretical Computer Science, ELSEVIER, vol. 393, no. 1–3, pp. 81–89, March 2008.
[4]B. Y. Liu, P. Brass, O. Dousse, P. Nain, and D. Towsley, “Mobility Improves Coverage of Sensor Networks,” in Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (ACM MobiHOC), pp. 300–308, 2005.
[5]C. Y. Chang, S. W. Chang, S. Y. Hsu, “A Decentralized Hole-Shape Regulation Technique for Enhancing Patrol and Deployment Tasks in Mobile WSNs.” IEEE/ACM Mobile Ad Hoc and Sensor Networks (IEEE/ACM MASS), October 2007.
[6]C. Y. Chang, H. R. Chang, H. J. Liu, and S. W. Chang, “On Providing Temporal Full-Coverage by Applying Energy Efficient Hole-Movement Strategies for Mobile WSNs,” IEEE Wireless Communications and Networking Conference (IEEE WCNC), March 2007.
[7]Weifang Cheng, Mo Li, Kebin Liu, Yunhao Liu, Xiangyang Li, Xiangke Liao1, “Sweep Coverage with Mobile Sensors,” IEEE International Parallel & Distributed Processing Symposium (IEEE IPDPS), 2008.
[8]F.-J. Wu, C.-F. Huang, and Y.-C. Tseng, "Data Gathering by Mobile Mules in a Spatially Separated Wireless Sensor Network", Mobile Data Management, 2009
[9]Ryo Sugihara and Rajesh K. Gupta, “Optimal Speed Control of Mobile Nodeor Data Collection in Sensor Networks”, IEEE Transactions on Mobile Computing , Vol. 9, No. 1, January 2010.
[10]Waleed Alsalih, Hossam Hassanein, and Selim Akl, “Routing to a Mobile Data Collector on a Predefined Trajectory”, IEEE International Communications Conference (IEEE ICC), 2009.
[11]Miao Zhao and Yuanyuan Yang, “Bounded Relay Hop Mobile Data Gathering in Wireless Sensor Networks” IEEE Mobile Ad Hoc and Sensor Networks (IEEE MASS), 2009.
[12]J. Hill and D. Culler, “A Wireless Embedded sensor Architecture for System-level Optimization,” Technical Report, Computer Science Department, University of California at Berkeley, 2002.
[13] Waleed Alsalih, Hossam Hassanein, and Selim Akl, “Routing to a
Mobile Data Collector on a Predefined Trajectory”, IEEE ICC, 2009.
[14] Miao Zhao and Yuanyuan Yang, “Bounded Relay Hop Mobile Data
Gathering in Wireless Sensor Networks” IEEE MASS, 2009.
[15] J. Hill and D. Culler, “A Wireless Embedded sensor Architecture for
System-level Optimization,” Technical Report, Computer Science
Department, University of California at Berkeley, 2002.