近年來，隨著無線感測網路技術的快速發展和物聯網應用的普及，無線感測裝置的充電技術也愈來愈受到重視。如何設計合適的充電機制來提供感測器運作之電量，以延長無線感測網路的生命週期已成為現今最熱門研究主題之一。然而，現存大多數的充電機制，其基本概念是由一台具移動力的充電車，分別移動至每個感測器的可充電範圍內，再逐一地對各個感測器進行充電，導致充電車在執行充電任務時所需移動的充電路徑長度，將隨著感測器數量增多而有顯著的增加，進而造成充電車需要花費大量的時間與電量在充電的移動過程中。另一方面，現存的充電機制大多設計讓充電車移動至感測器充電範圍內的某定點後，停留在該定點並執行充電任務，待感測器充電完成後，充電車才繼續移動前往下一個目標感測器之充電範圍內的定點停留，並執行充電任務，換句話說，充電車的移動過程會是走走停停的狀態，無法維持等速移動，導致充電車必須花費更多的電量來執行充電任務，因此也降低了充電效率。有鑑於此，本論文提出兩種不同的充電技術，分別為Recharging Path Construction (RPC) 技術與Coverage Aware Energy Replenish Mechanism (CAERM) 技術，用以改善現存充電機制的效能。首先，本論文所提出之 RPC 技術，其探討充電車在等速移動下，同步進行充電工作時，如何規劃最佳的充電路徑，進而讓充電車的移動方式更有效率。接著，本論文所提出之 CAERM 技術，其將感測器之充電優先權納入考量，針對不同位置之感測器，分析其覆蓋面積對於整體感測的貢獻度，並協助充電車動態規劃其充電路徑，以進一步改善充電效率。實驗結果顯示，本論文所提出的兩種充電技術，可有效的解決現存充電機制所產生的問題，大幅提昇充電車執行充電任務的效能。

Energy recharging has received much attention in recent years. Several recharging mechanisms were proposed for achieving perpetual lifetime of a given Wireless Sensor Network (WSN). However, most of them require a mobile recharger to visit each sensor and then perform the recharging task, which increases the length of the recharging path. Another common weakness of these works is the requirement for the mobile recharger to stop at the location of each sensor. As a result, it is impossible for recharger to move with a constant speed, leading to inefficient movement. To improve the recharging efficiency, this thesis proposes two energy recharging path planning schemes, including Recharging Path Construction (RPC) mechanism and Coverage Aware Energy Replenish Mechanism (CAERM). The RPG mechanism enables the mobile recharger to recharge all sensors using a constant speed, aiming to minimize the length of recharging path and improve the recharging efficiency while achieving the requirement of perpetual network lifetime of a given WSN. Finally, the CAERM dynamically adjusts the recharging path according to the recharging requests of sensors, aiming to minimize the coverage loss for a given WSN. Theoretical analyses and performance evaluations show that the proposed mechanisms can significantly improve the performance of existing energy recharging techniques.

Contents
List of Figures	VI
List of Tables	VIII
Chapter 1: Introduction	1
Chapter 2: Related Works	5
2.1 Energy Replenishment by the Environmental Energy Resources	5
2.2 Energy Replenishment by Mobile Rechargers	7
Chapter 3: The Recharging Path Construction Mechanism	12
3.1 Network Environment	12
3.2 Problem Formulation	14
3.3 Sensor Recharging Model	16
3.4. The Recharging Path Construction Algorithm	18
3.4.1 Initial Recharging Path Construction Phase	19
3.4.2 Partitioning Phase	23
3.4.3 Inner-Group Path Reduction Phase	25
3.4.4 Inter-Group Path Reduction Phase	29
3.4.5 The Proposed RPC Algorithm	33
Chapter 4: The Coverage Aware Energy Replenish Mechanism 	36
4.1 Network Environment	36
4.2 Problem Formulation	39
4.3 The proposed CAERM Algorithm	44
4.3.1 Coverage Contribution Evaluation Phase	46
4.3.2 Path Construction Phase	66
4.3.3 Recharging Phase	68
Chapter 5: Performance Evaluation	70
5.1 Simulation Environment	72
5.2 Performance Study	74
Chapter 6: Conclusion	87
References		89

List of Figures
Figure 1:The scenario of the considered WSNs 14
Figure 2:An example of executing the RPC 22
Figure 3:An example of two partitions for path P_(I)^RPC 24
Figure 4:The recharging segment of sensor s_i 26
Figure 5:An example of executing Inner-Group Path Reduction Phase 27
Figure 6:New recharging path of a partition 30
Figure 7:The reduction path of each partition 30
Figure 8:An example of four tasks performed in each round 38
Figure 9:The scenario that the mobile charger has finished the last round and checks the recharging requests in current queue Q in this round 47
Figure 10:Coverage contribution evaluation 53
Figure 11:Coverage benefit of sensor s_8^Q 55
Figure 12:Architecture of the proposed algorithm CAERM 69
Figure 13:The recharging segments of a sensor 71
Figure 14:An example that applies the exhausted search to obtain the near optimal mechanism 72
Figure 15:Three scenarios considered in the experiments 74
Figure 16:The comparison of four recharging mechanisms in terms of path length using different deployment scenarios 76
Figure 17:Impact of number of sensors on the energy consumption by applying the four compared algorithms 78
Figure 18:Comparison of the four algorithms in terms of recharging time efficiency in three scenarios 79
Figure 19:The recharging paths by applying three clustering mechanisms. Three scenarios are considered 82
Figure 20:Example of recharging path reduction by applying the second clustering mechanism 83
Figure 21:The comparison of path length of the four algorithms by varying the recharging radius ranging from 5 to 9 distance units 84
Figure 22:The comparison of the four mechanisms in terms of recharging path length by varying the speed of recharger from 1 to 4 85

List of Tables
Table 1:The comparison between the existing algorithms and the proposed RPC 10
Table 2:The Recharging Path Construction (RPC) Algorithm 33
Table 3:Determine strategies: The SU and MU strategies 63
Table 4:Simple Recharging Coverage Benefit (S-RCB) Algorithm 64
Table 5:Chain-Effect Recharging Coverage Benefit Algorithm 66

References

[1]	Srbinovska, M.; Gavrovski, C.; Dimcev, V.; Krkoleva, A.; Borozan, V. Environmental Parameters Monitoring in Precision Agriculture Using Wireless Sensor Networks. J. Clean. Prod. 2015, 88, 297–307. 
[2]	Bhuiyan, M.Z.A.; Wang, G.; Cao, J.; Wu, J. Deploying Wireless Sensor Networks with Fault Tolerance for Structural Health Monitoring. IEEE Trans. Comput. 2015, 64, 382–395. 
[3]	Ehsan, S.; Bradford, K.; Brugger, M. Design and Analysis of Delay-Tolerant Sensor Networks for Monitoring and Tracking Free-Roaming Animals. IEEE Trans. Wirel. Commun. 2012, 11, 1220–1227. 
[4]	Vaidya, T.; Swami, P.; Rindhe, S.; Kulkarni, S.; Patil, S. Avalanche Monitoring & Early Alert System Using Wireless Sensor Network. Int. J. Adv. Res. Comput. Sci. Electron. Eng. 2013, 2, 38–41. 
[5]	Keung, G.Y.; Li, B.; Zhang, Q. The Intrusion Detection in Mobile Sensor Network. IEEE/ACM Trans. Netw. 2012, 20, 1152–1161. 
[6]	Abo-Zahhad, M.; Ahmed, S.M.; Sabor, N.; Sasaki, S. Mobile Sink-Based Adaptive Immune Energy-Efficient Clustering Protocol for Improving the Lifetime and Stability Period of Wireless Sensor Networks. IEEE Sens. J. 2015, 15, 4576–4586. 
[7]	Le, T.N.; Pegatoquet, A.; Berder, O.; Sentieys, O. Energy-Efficient Power Manager and MAC Protocol for Multi-Hop Wireless Sensor Networks Powered by Periodic Energy Harvesting Sources. IEEE Sens. J. 2015, 15, 7208–7220. 
[8]	Kiani, F.; Amiri, E.; Zamani, M.; Khodadadi, T.; A. Manaf, A. Efficient Intelligent Energy Routing Protocol in Wireless Sensor Networks. Int. J. Distrib. Sens. Netw. 2015, 2015, 1–13. 
[9]	Steinfeld, L.; Ritt, M.; Silveira, F.; Carro, L. Optimum Design of a Banked Memory with Power Management for Wireless Sensor Networks. Springer Wirel. Netw. 2015, 21, 81–94. 
[10]	Taneja, J.; Jeong, J.; Culler, D. Design, Modeling, and Capacity Planning for Micro-Solar Power Sensor Networks. In Proceedings of the 2008 International Conference on Information Processing in Sensor Networks, St. Louis, MO, USA, 22–24 April 2008. 
[11]	Tan, Y.K.; Panda, S.K. Self-Autonomous Wireless Sensor Nodes with Wind Energy Harvesting for Remote Sensing of Wind-Driven Wildfire Spread. IEEE Trans. Instrum. Meas. 2011, 60, 1367–1377
[12]	Sodano, H.A.; Simmers, G.E.; Dereux, R.; Inman, D.J. Recharging Batteries Using Energy Harvested from Thermal Gradients. J. Intell. Mater. Syst. Struct. 2007, 18, 3–10. 
[13]	He, S.; Chen, J.; Jiang, F.; Yau, D.K. Y.; Xing, G.; Sun, Y. Energy Provisioning in Wireless Rechargeable Sensor Networks. IEEE Trans. Mob. Comput. 2013, 12, 1931–1942. 
[14]	Lu, S.; Wu, J.; Zhang, S. Collaborative Mobile Charging for Sensor Networks. In Proceedings of the 2012 International Conference on Mobile Ad-Hoc and Sensor Systems (MASS), Las Vegas, NV, USA, 8–11 October 2012. 
[15]	Peng, Y.; Li, Z.; Zhang, W.; Qiao, D. Prolonging Sensor Network Lifetime Through Wireless Charging. In Proceedings of the 31st IEEE Real-Time Systems Symposium (RTSS), San Diego, CA, USA, 30 November–3 December 2010. 
[16]	Xie, L.; Shi, Y.; Hou, Y.T.; Sherali, H.D. Making Sensor Networks Immortal: An Energy-Renewal Approach with Wireless Power Transfer. IEEE/ACM Trans. Netw. 2012, 20, 1748–1761. 
[17]	De Lurgio, P.; Djurcic, Z. A Prototype of Wireless Power and Data Acquisition System for Large Detectors. Nucl. Instrum. Methods Phys. Res. Sect. A Accel. Spectrom. Detect. Assoc. Equip. 2015, 785, 99–104. 
[18]	Shi, Y.; Xie, L.; Hou, Y.T.; Sherali, H.D. On Renewable Sensor Networks with Wireless Energy Transfer. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), Shanghai, China, 10–15 April 2011. 
[19]	Li, J.; Zhao, M.; Yang, Y. OWER-MDG: A Novel Energy Replenishment and Data Gathering Mechanism in Wireless Rechargeable Sensor Networks. In Proceedings of the IEEE Global Communications Conference (GLOBECOM), Anaheim, CA, USA, 3–7 December 2012. 
[20]	Ganeriwal, S.; Kansal, A.; Srivastava, M.B. Self-Aware Actuation for Fault Repair in Sensor Networks. In Proceedings of IEEE International Conference on Robotics and Automation (ICRA), New Orleans, LA, USA, 26 April–1 May 2004.