在可充電無線感測網路(Wireless Re-chargeable Sensor Networks, WRSNs)中，無線充電器(Wireless Charger)使用無線充電技術適時補充網路中感測節點的電力，讓所有感測節點持續運作，而使WRSN具有永續性(sustainability)。由於無線充電器價格昂貴，因此如何以較少的充電器覆蓋所有感測節點以達成WRSN的永續性成為一個非常重要的議題。本論文提出GPSCD (Genetic Particle Swarm Charger Deployment)演算法，嘗試最佳化WRSN充電器的佈置。利用基因演算法(Genetic Algorithm, GA)將粒子群充電器佈置(Particle Swarm Charger Deployment, PSCD)演算法的參數編碼為染色體。PSCD演算法是一個粒子群充最佳化(Particle Swarm Optimization, PSO)演算法，它將充電器視為粒子，透過記住區域最佳值的PSO粒子個體記憶及記住全域最佳值的PSO群體記憶調整充電器的位置及天線方向，找尋充電效益最好的方式，以最小數量的充電器滿足所有感測器的充電需求。PSCD演算法找出的最小充電器數量就是GA演算法染色體的適應值。依據每個染色體的適應值，GA演算法即可透過基因的複製、交配和突變找出適應值最佳的染色體，達成利用最少數量的充電器滿足所有感測器的充電需求。我們使用Powercast P2110-EVAL-02無線充電器設備進行充電效益實驗，用以求得充電器對感測節點在不同距離、不同角度的充電效率數據，並進行模擬實驗以比較GPSCD演算法與兩個啟發式貪婪演算法，即Greedy Cone Covering (GCC)演算法與Adaptive Cone Covering (ACC)演算法的效能。實驗結果顯示GPSCD確實能以較少的充電器滿足所有感測節點充電需求，而使WRSN具有永續性。;In Wireless Rechargeable Sensor Networks (WRSNs), wireless chargers can recharge batteries of sensor nodes so that they can operate sustainably to provide WRSNs with the property of sustainability. Since wireless chargers are costly, how to apply as few as possible chargers to cover all sensor nodes and fulfill their charging demands for making WRSNs sustainable is thus an important problem. This paper proposes the GPSCD (Genetic Particle Swarm Charger Deployment) algorithm trying to optimize WRSN charger deployment. We use the genetic algorithm (GA) to encode the parameters of the particle swarm charger deployment (PSCD), which is an algorithm based on the particle swarm optimization (PSO). PSCD estimates a charger’s charging efficiency according to the distance and angle between the charger and sensor nodes and then utilizes PSO individual memory of the local optimum and PSO group memory of global optimum to adjust locations and antenna orientations of chargers. In this way, PSCD algorithm tries to use the minimum number of chargers to fulfill the demands of all sensor nodes. The number of chargers derived by the PSCD algorithm is the fitness value of the GA chromosome. Based on the fitness value of every chromosome, GA can then find out, through chromosome duplication, crossover, and mutation, the chromosome with the highest fitness value to reach the goal of using the minimum number of chargers to fulfill the charging demands of all sensor nodes. We perform experiments by using Powercast P2110-EVAL-02 wireless chargers to obtain charging efficiency for different distances and angles between chargers and sensor nodes. Based on the charging efficiency data, we simulate GPSCD and two related heuristic greedy algorithms, namely the Greedy Cone Covering (GCC) algorithm and the Adaptive Cone Covering (ACC) algorithm. The simulation results show that GPSCD indeed outperforms the other two algorithms in sense that it uses fewer chargers to fulfill the charging requirements of all sensor nodes to make WRSNs sustainable.
