| 摘要: | 雖然無線感測網絡已經發展了很多年，但它仍然是一個非常前瞻性的技術，是因為人類希望世界實現一個全自動的環境，因此無線感測網絡技術是替代人力必需技術之一。此外，一些待開發的區域很難直接由人類到達，如火山、海底與外太空等。這意味著人們必須在待開發的區域周圍放置許多感測器，因此人們能夠遠端操控這些感測器來進行收集、分析或管理的業務。然而，無線感測網絡的網絡壽命必須基於電池電量，使得感測器總有一天會能量耗盡。因此，無線感測網絡的能源效率成為了一個不可或缺的課題。然而，任何省電機制仍然不能被視為一個永續的解決方案。因此，無線可充電感測器網絡被提出，主要透過充電器的佈署來提供感測器所需的能量。當充電器的數量變得更多時，佈署成本將增加，但是可以避免整個無線感測網絡崩潰。換句話說，它們具有權衡關係，他們之間存在許多指標可能影響充電器佈署的最終策略，例如距離，傳輸半徑，感測器的功率需求等。這意味著充電器佈署問題非常複雜，可能無法在指數時間內獲得結果。目前，現有的充電器佈署方法採用基於貪婪的演算法，這些解決方案容易陷入區域最佳解，這意味著這個議題仍然存在改善空間。
在本研究中，我們將充電器佈署問題分為兩種類型的問題：固定式充電器放置問題和移動式的自動充電車輛路徑選擇問題。在固定式充電器放置問題中，我們首先提出了一種更有效的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. |
