臺灣博碩士論文加值系統

雖然無線感測網絡已經發展了很多年，但它仍然是一個非常前瞻性的技術，是因為人類希望世界實現一個全自動的環境，因此無線感測網絡技術是替代人力必需技術之一。此外，一些待開發的區域很難直接由人類到達，如火山、海底與外太空等。這意味著人們必須在待開發的區域周圍放置許多感測器，因此人們能夠遠端操控這些感測器來進行收集、分析或管理的業務。然而，無線感測網絡的網絡壽命必須基於電池電量，使得感測器總有一天會能量耗盡。因此，無線感測網絡的能源效率成為了一個不可或缺的課題。然而，任何省電機制仍然不能被視為一個永續的解決方案。因此，無線可充電感測器網絡被提出，主要透過充電器的佈署來提供感測器所需的能量。當充電器的數量變得更多時，佈署成本將增加，但是可以避免整個無線感測網絡崩潰。換句話說，它們具有權衡關係，他們之間存在許多指標可能影響充電器佈署的最終策略，例如距離，傳輸半徑，感測器的功率需求等。這意味著充電器佈署問題非常複雜，可能無法在指數時間內獲得結果。目前，現有的充電器佈署方法採用基於貪婪的演算法，這些解決方案容易陷入區域最佳解，這意味著這個議題仍然存在改善空間。
在本研究中，我們將充電器佈署問題分為兩種類型的問題：固定式充電器放置問題和移動式的自動充電車輛路徑選擇問題。在固定式充電器放置問題中，我們首先提出了一種更有效的FoI之定義方式，使得我們能夠花費更低的成本即可獲得更好的充電器候選位置，基於此方法，我們進一步設計了四個超啟發式算法來解決區域最佳解問題，由於超啟發式算法必須花費更多的計算成本來避開落入區域最佳、更好的解之搜尋以及適應函數的計算，因此我們還設計了一個能夠有效減少超啟發式算法解空間的框架，最後為了提供更靈活的佈署方式，我們將充電器結合自走車，並且將充電路徑的選擇問題映射到旅行銷售員問題，進而對此問題設計了四種超啟發式算法的應用方式，最後，我們根據此問題定義的相應特性，設計一個框架來找出感測器能量耗盡的數量與充電路徑的權衡，模擬結果表明，該方法可以實現最佳的性價比。

Although wireless sensor networks have developed over many years, they are still a very forward-looking technology because humans hope for a “global village”; hence wireless sensor network technologies are necessary for replace manpower and improve communication. In addition, some areas of interest are difficult to reach or hazardous to the human body. It means that the people must place many sensors in these areas of interest so that they can collect, analyze or manage these sensors remotely. However, the network lifetime of wireless sensor networks is based on their battery power so that the sensors will be run out of power eventually. Therefore, ensuring the energy efficiency of wireless sensor networks has become an indispensable issue. Nevertheless, since no energy efficiency mechanisms can be regarded as a sustainable solution, the wireless rechargeable sensor network has been proposed, with the chargers deployed to provide needed power for the sensors. Deployment cost will increase when the number of the chargers increases, but it can help the whole wireless sensor network avoid being crashed. In other words, they have the trade-off relationship; as well, many metrics may impact the final policy for chargers deployment such as distance, transmission radius, power requirement of the sensors, and so on. It means that the chargers deployment problem is very complex and may not obtain the results in exponential time. Currently, the existing methods of charger deployment adopt a greedy-based operation so that the solutions will fall into the local optimum more easily, signifying that this topic still has some room for improvement.
In this thesis, we divide the charger deployment problem into two types: the fixed chargers placement problem and the mobile autonomous charging vehicle path selection problem. In the fixed chargers placement problem, we first propose a more efficient way for initiating the field of interest (FoI) to find the better candidate positions of chargers with lower computation costs. Based on that, we further designed the application of four metaheuristic algorithms to solve the local optimum problem. Since we know that metaheuristic algorithms always require more computation costs for escaping local optimum, to obtain better solution searching and fitness function calculating, we designed a framework to solve these problems via effectively reducing the solution space. In order to provide more flexible planning, we combined the charger and self-propelled vehicle, and then mapped the mobile chargers path selection problem into the travelling salesman problem (TSP). We also designed the application of four metaheuristic algorithms and enhanced them for finding the higher fitness value between the charging path and number of dead sensors. The simulation results show that the proposed method can achieve the best price–performance ratio.

摘要 i
ABSTRACT ii
誌謝 iv
List of figures vii
List of tables ix
Explanation of symbols x
Chapter 1. Introduction 1
1.1 Introduction of Wireless Sensor Network 1
1.2 Introduction of Wireless Rechargeable sensor network 2
1.3 Motivation 2
Chapter 2. Related Works 4
2.1 Wireless Rechargeable Sensor Network 4
2.1.1 Magnetic Induction 4
2.1.2 Magnetic Resonance 4
2.1.3 Laser light sensor 5
2.1.4 Micro-wave conversion 5
2.2 Wireless Charring Planning 6
2.3 Movable-Charger-Based Algorithm 6
2.4 Metaheuristic Algorithm 7
2.4.1 Simulated Annealing Algorithm 7
2.4.2 Tabu search algorithm 8
2.4.3 Genetic Algorithm 8
2.4.4 Ant colony optimization Algorithm 9
Chapter 3. Problem Definition 10
3.1 Network model 10
3.1.1 Projection of charger position 10
3.1.2 Coordinate of Overlapping Coverage 11
3.2 Wireless Charging model 14
3.3 Linear programing model 15
3.4 Proof the bounded 16
Chapter 4. Proposed Mechanism 19
4.1Matahuristic Algorithm 19
4.1.1 SA- Based Charging Algorithm 20
4.1.2 TS- Based Charging Algorithm 24
4.1.3 GA- Based Charging Algorithm 29
4.1.4 ACO- Based Charging Algorithm 33
4.2 Layoff Algorithm 38
4.2.1 LSA- Based Charging Algorithm 41
4.2.2 LTS- Based Charging Algorithm 45
4.2.3 LGA- Based Charging Algorithm 49
4.2.4 Layoff ACO- Based Charging Algorithm (LACOBC) 53
Chapter 5. Simulation 58
5.1 Simulation settings 58
5.2 Deployment of chargers 58
5.3 Comparison of number of chargers 61
5.4 Comparison of computation time 64
5.5 Comparison of Energy efficiency 67
5.6 Comparison of convergence rate 70
5.7 Summary of fixed chargers placement 72
Chapter 6. Problem Definition for Mobile Charging 74
6.1 Network model 75
Chapter 7. Proposed Mechanism for Mobile Charging 78
7.1 SA-Based Mobile Charging Algorithm 79
7.2 TS- Based Mobile Charging Algorithm 81
7. 3 GA- Based Mobile Charging Algorithm 83
7. 4 ACO- Based Mobile Charging Algorithm 86
7. 5 Mobile Layoff Algorithm 89
Chapter 8. Simulations of Mobile Charging 93
8.1 Simulation settings 93
8.2 Path planning of chargers 93
8.3 Comparison of dead sensors 96
8.4 Comparison of computation time 98
8.5 Comparison of path length 100
8.6 Comparison of convergence rate 102
8.7 Summary of mobile chargers placement 104
Chapter 9 Conclusion 106
Reference 108

[1] C.-M. Yu, C.-Y. Chen, C.-S. Lu, S.- Y. Kuo, H.-C. Chao, "Acquiring authentic data in unattended wireless sensor networks", Sensors, vol. 10, no. 4, pp. 2770-2792, 2010.
[2] G. Han, J. Jiang, L. Shu, J. Niu, H.-C. Chao, "Management and applications of trust in wireless sensor networks: A survey", J. Comput. Syst., vol. 80, no. 3, pp. 602-617, May 2014.
[3] C.-Y. Chen, H.-C. Chao, "A survey of key distribution in wireless sensor networks", Security and Communication Networks, vol. 7, no. 12, pp. 2495-2508, 2014.
[4] A. M. Nia, M. Mozaffari-Kermani, S. Sur-Kolay, A. Raghunathan, N. K. Jha, "Energy-efficient long-term continuous personal health monitoring", IEEE Trans. Multi-Scale Comput. Syst., vol. 1, no. 2, pp. 85-98, Apr–Jun. 2015.
[5] C. Habib, A. Makhoul, R. Darazi, and C. Salim, “Selfadaptive data collection and fusion for health monitoring based on body sensor networks,” IEEE Trans. Industrial Informatics, 2016.
[6] D. Yang, S. Misra, X. Fang, G. Xue, J. Zhang, "Two-tiered constrained relay node placement in wireless sensor networks: Computational complexity and efficient approximations", IEEE Trans. Mobile Comput., vol. 11, no. 8, pp. 1399-1411, Aug. 2012.
[7] H.-H. Cho, C.-Y. Chen, T. K. Shih, H.-C. Chao, "A Survey on underwater delay/disruption tolerant wireless sensor network routing", IET Wireless Sensor Systems, pp. 1-10, 2014.
[8] H.-H. Cho, T. K. Shih, H.-C. Chao, "A Survey on underwater delay/disruption tolerant wireless sensor network routing", "A Robust Coverage Scheme for UWSNs using the Spline Function" IEEE Sensors Journal, Vol. 16, No. 11, pp. 3995-4002, May 2016.
[9] F.-H. Tseng, H.-H. Cho, L.-D. Chou, and H.-C. Chao, "Efficient Power Conservation Mechanism in Spline Function Defined WSN Terrain", IEEE Sensors Journal, vol. 14, no. 3, pp. 853-864, March 2014.
[10] W. Ouyang, C. W. Yu, C.-C. Tien, C. W. Hao, T. H. Peng, "Wireless charging scheduling algorithms in wireless sensor networks", Journal of Internet Technology, vol. 13, no. 2, pp. 293-306, 2012.
[11] Y.-S. Yen, S. Hong, R.-S. Chang, H.-C. Chao. “An energy efficient and coverage guaranteed wireless sensor network. ” Proc. 2007 IEEE Wireless Communications and Networking Conference, 2923-2928
[12] D.-C. Huang, H.-C. Tseng, D.-J. Deng, H.-C. Chao. “A queue-based prolong lifetime methods for wireless sensor node. ” Proc. Computer Communications 35 (9), 10938106
[13] J. Ren, Y. Zhang, K. Zhang, A. Liu, J. Chen, X. Shen, "Lifetime and energy hole evolution analysis in data-gathering wireless sensor networks", IEEE Trans. Ind. Informat., vol. 12, no. 2, pp. 788-800, 2016 .
[14] S. He, J. Chen, F. Jiang, D. Yau, G. Xing, Y. Sun, "Energy provisioning in wireless rechargeable sensor networks", IEEE Trans. Mobile Comput., vol. 12, no. 10, pp. 1931-1942, 2013.
[15] M. Zhao, J. Li, and Y. Yang, “Joint Mobile Energy Replenishment and Data Gathering in Wireless Rechargeable Sensor Networks, ” Proc. 23rd Intl. Teletraffic Congress, Sept. 68, 2011, San Francisco, USA.
[16] C. Hu, Y. Wang, "Minimizing energy consumption of the mobile charger in a wireless rechargeable sensor network", Journal of Internet Technology, vol. 16, no. 6, pp. 1111-1119, 2015.
[17] J.-H. Liao, J.-R. Jiang, "Wireless charger deployment optimization for wireless rechargeable sensor networks", Proc. IEEE International Conference on Ubi-Media Computing (UMEDIA), 2014.
[18] J.-H. Liao, C.-M. Hong, and J.-R. Jiang, “An Adaptive Algorithm for Charger Deployment Optimization in Wireless Rechargeable Sensor Networks. ” Proc. ICS. 2014.
[19] W.-J. Jian, H.-H. Cho, C.-Y. Chen, H.-C. Chao, T. K. Shih, "Movable-charger-based planning scheme in wireless rechargeable sensor networks", Proc. IEEE International Workshop on MobiWorld, 2015.
[20] O. H. Stielau, G. A. Covic, "Design of loosely coupled inductive power transfer systems", Proc. Int. Conf. Power Syst. Technol., vol. 1, pp. 85-90, 2000.
[21] M. Kiani, M. Ghovanloo, "The circuit theory behind coupled-mode magnetic resonance-based wireless power transmission", IEEE Trans. Circuits Syst.—Part I, vol. 59, no. 8, pp. 1-10, Aug. 2012.
[22] N. N. H. Ching, H. Y. Wong, W. J. Li, P. H. W. Leong, Z. Wen, "A laser-micromachined multi-modal resonating power transducer for wireless sensing systems", Sens. Actuators A Phys., vol. 97, pp. 685-690, Apr. 2002.
[23] N. Shinohara, "Power without wires", IEEE Microw. Mag., vol. 12, no. 7, pp. S64-S73, Dec. 2011.
[24] M. Erol-Kantarci and H. T. Mouftah, "Suresense: Sustainable wireless rechargeable sensor networks for the smart grid", IEEE Wireless Commun., vol. 19, no. 3, pp. 30-36, Jun. 2012.
[25] T.-C. Chiu, Y.-Y. Shih, A.-C. Pang, J.-Y. Jeng, P.-C. Hsiu, "Mobility-Aware Charger Deployment for Wireless Rechargeable Sensor Networks", Proc. 14th Asia-Pacific Network Operations and Management Symp. (APNOMS), pp. 1-7, 2012.
[26] Y. Pang, Y. Zhang, Y. Gu, M. Pan, Z. Han, P. Li, "Efficient data collection for wireless rechargeable sensor clusters in harsh terrains using UAVs", Proc. of IEEE Global Communications Conference (GLOBECOM), pp. 234-239, Dec. 2014.
[27] Y. Tian, P. Cheng, L. He, Y. Gu, and J. Chen, " Optimal Reader Location for Collision-Free Communication in WRSN," Proc. of IEEE Global Communications Conference (GLOBECOM), pp. 234-239, Dec. 2014.
[28] T. Rault, A. Bouabdallah and Y. Challal, "Multi-hop wireless charging optimization in low-power networks", Proc. IEEE Global Commun. Conf., Dec. 2013.
[29] C. Hu and Y. Wang, “Minimizing the number of mobile chargers in a large-scale wireless rechargeable sensor network”, Proc. IEEE Wireless Communications and Networking Conference (WCNC), pp. 1297-1302, 2015.
[30] Shu, Yuanchao, Hamed Yousefi, Peng Cheng, Jiming Chen,Yu Gu, Tian He, Kang G. Shin, "Near-optimal velocity control for mobile charging in wireless rechargeable sensor networks", IEEE Trans. Mobile Comput., vol. 15, no. 7, pp. 1699-1713, Jul. 2016.
[31] C.-W. Tsai, W.-C. Huang, M.-H. Chiang, M.-C. Chiang, C.-S. Yang, "A hyper-heuristic scheduling algorithm for cloud", IEEE Trans. Cloud Comput., vol. 2, no. 2, pp. 236-250, Apr./Jun. 2014.
[32] I. Boussaïd, J. Lepagnot, P. Siarry, "A survey on optimization metaheuristics", Inf. Sci., vol. 237, pp. 82-117, Jul. 2013.
[33] S. P. Brooks, B. J. T. Morgan, "Optimization using simulated annealing", Statistician, vol. 44, no. 2, pp. 241-257, 1995.
[34] F. Glover, "Tabu search-Part I", ORSA J. Comput., vol. 1, no. 3, pp. 190-206, 1989.
[35] F. Glover, "Tabu search-Part II", ORSA J. Comput., vol. 2, no. 1, pp. 4-32, 1990.
[36] J. H. Holland, “Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence,” Ann Arbor, MI, USA: Univ. of Michigan Press, 1975.
[37] S. T. Cheng and C. L. Hsu, "Genetic Optimal Deployment in Wireless Sensor Networks", Journal of Internet Technology, Vol. 6, No. 1, pp. 9-18, 2005.
[38] V. T’kindt, N. Monmarche, F. Tercinet, and D. Laugt, Y. Wang “An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem,” Eur. J. Oper. Res., vol. 142, no. 2, pp. 250–257, 2002.
[39] K. L. Hoffman, M. Padberg, G. Rinaldi, "Traveling salesman problem" Encyclopedia of Operations Research and Management Science, pp. 1573-1578, 2013.
[40] J. Zhang, Z. H. Zhan, Y. Lin, N. Chen, Y. J. Gong, J. H. Zhong, H. Chung, Y. Li, Y. H. Shi, "Evolutionary computation meets machine learning: A survey", IEEE Comput. Intell. Mag., vol. 6, no. 4, pp. 68-75, Nov. 2011.