無線可充電感測網路中多車輛之請求式充電排程策略

Multi-Vehicle On-Demand Charging Scheduling Schemes for Wireless Rechargeable Sensor Networks

陳佳興(Jia-Sing Chen)

指導教授 ： 陳秋媛

國立交通大學/理學院/應用數學系暨研究所/碩士(2020年)

摘要

傳統無線感測網路因為壽命有限，限制了它們的應用。最近，隨著無線電力傳輸與可充電鋰電池技術上的突破， 無線可充電感測網路已經被提出。在無線可充電感測網路中，無線充電車輛(簡記為WCV)被用於補充電量至壽命緊迫(亦即電量即將耗盡)的傳感器。經驗告知，週期式充電方案經常導致大量傳感器失效(亦即電量耗盡)，因此充電效益低。基於以上，我們考慮請求式充電方案。 此外，我們考慮了兩個現實世界的限制。我們將第一個限制稱為傳感器剩餘電量限制(簡記為R1)。我們將第二個限制稱為車輛電量限制(簡記為R2)。限制R1 是由於在無線充電車輛(WCV)行駛過程中，傳感器仍然持續消耗電量，而限制R2 則是基於每台無線充電車輛(WCV)自身的電量原本就是有限的。我們的首要目標是最小化耗盡電力的傳感器數量， 我們的次要目標是最小化無線充電車輛(WCV)的平均移動距離。我們提出了兩個演算法，分別稱為mmDC與msNDC，前者用於多充電站的情境，而後者則是用於單一充電站。在mmDC演算法中，我們引進"延遲充電"的概念。 就我們所知，我們是第一個考慮請求式充電方案，並且同時納入R1限制、R2限制，以及多充電站。我們藉由模擬比較mmDC 和msNDC，並將msNDC 與三種最新的充電排程演算法做比較，分別是NMV [14]、mTS [16]、以及Appro [36]，在長寬比為 1:1、2:1 以及 4:1 的矩形感測區域上(簡記為ROI)。 實驗數據顯示，mmDC的效益優於msNDC，並且在 2:1 以及 4:1 的ROI上，效益更為顯著提升，這顯示"多充電站搭配延遲充電" 是請求式充電方案的一種有效技術。 此外，實驗數據也顯示，msNDC 可以減少耗盡電力的傳感器數量達至少27.8% 並且降低無線充電車輛(WCV)的平均移動距離達至少22.8%。

關鍵字

無線可充電感測網路 ； 充電排程 ； 請求式能源補充 ； 無線充電車輛 ； 車輛路徑問題

並列摘要

The limited lifetime of the traditional wireless sensor networks restricts their applications. Recently, with the breakthrough in wireless power transfer and rechargeable lithium battery technology, wireless rechargeable sensor networks (WRSNs) have been proposed. In a WRSN, wireless charging vehicles (WCVs) are used to wirelessly replenish the energy of life-critical nodes. It has been observed that periodic charging schemes usually result in a large number of failed nodes and therefore have low charging performance. We therefore consider on-demand charging scheme. In addition, we consider two real world restrictions. We call the first restriction the node residual energy restriction and denote it as R1. We call the second restriction the vehicle energy capacity restriction and denote it as R2. R1 is due to the fact that a sensor node continues to consume energy when WCVs travel, while R2 is due to the fact that each WCV is with a limited energy capacity. Our first objective is to minimize the number of dead nodes and our second objective is to minimize the average of moving distance of WCVs. Two algorithms, mmDC and msNDC, are proposed; the former is for the multiple depots scenario and the latter, single depot. We also introduce the concept of "delay charging" in mmDC. To the best of our knowledge, we are the first to consider on-demand charging with both restrictions R1 and R2 and with multiple depots. We conduct simulations to compare mmDC and msNDC and compare msNDC with three state-of-the-art algorithms, namely NMV [14], mTS [16], and Appro [36], on rectangular regions of interest (ROIs) with varying length-to-width ratio 1:1, 2:1, and 4:1. Simulation results show that mmDC outperforms msNDC, and the improvement is significant in 2:1 and 4:1 ROIs, meaning that "multiple depots along with delay charging" is a promising technique for on-demand charging. Simulation results also show that msNDC reduces the number of dead nodes by at least 27.8% and reduces the average moving distance of WCVs by at least 22.8%.

並列關鍵字

Wireless rechargeable sensor network ； charging scheduling ； on-demand energy replenish ； wireless charging vehicle ； vehicle routing problem

參考文獻

[1] Implementing K-Means in Octave/Matlab (http://aqibsaeed.github.io/2016-06-24-k-means/), 2016 (accessed May 13, 2020).

[2] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless sensor networks: a survey. Computer networks, 38(4):393{422, 2002.

[3] R.-H. Cheng, C. Xu, and T.-K. Wu. A genetic approach to solve the emergent charging scheduling problem using multiple charging vehicles for wireless rechargeable sensor networks. Energies, 12(2):287, 2019.

[4] Y. Feng, L. Guo, X. Fu, and N. Liu. Efficient mobile energy replenishment scheme based on hybrid mode for wireless rechargeable sensor networks. IEEE Sensors Journal, 19(21):10131{10143, 2019.

[5] Y. Feng, N. Liu, F. Wang, Q. Qian, and X. Li. Starvation avoidance mobile energy replenishment for wireless rechargeable sensor networks. In 2016 IEEE International Conference on Communications (ICC), pages 1{6. IEEE, 2016.