多节点部分充电模型下的充电调度优化

doi:10.3778/j.issn.1002-8331.2111-0410

摘要/Abstract

摘要： 在无线可充电传感器网络中，针对移动充电车采用多节点部分充电模型在充电调度过程中往复行驶，导致充电时间增加的问题进行了研究。提出一种新颖的多节点部分充电模型，从全局优化移动充电车在每个充电位置的充电时间，保证每个能量临界的传感器被充满电。同时提出AlgMinTime算法进行路径规划，确定移动充电车的充电环路以及对应位置的充电时间，使得环路上总充电调度时间最小化。最终通过仿真实验评估所提出算法的性能。实验结果表明，所提算法的充电调度平均环路时间相较于SOTA算法缩短9.8%。

关键词: 无线传感器网络, 多节点充电, 部分充电, 充电调度, 路径规划

Abstract: In the wireless rechargeable sensor network, the mobile charger adopts the multi-node partial charging model to reciprocate during the charging scheduling process, which leads to the increase of the charging duration. For this reason, this paper proposes a novel multi-node partial charging model, which globally optimizes the charging duration of the charger at each charging position, ensuring that each energy-critical sensor is fully charged. Meanwhile, the AlgMinTime algorithm is designed for path planning to determine the charging tour of the charger and the charging duration corresponding to the charging position, such that the total charging scheduling duration in the tour is minimized. Finally, the performance of the proposed algorithm is evaluated through simulation experiments. Experimental results show that the average tour duration of charging scheduling by the proposed algorithm is 9.8% shorter than that of the SOTA algorithm.

Key words: wireless sensor network, multi-node charging, partial charging, charging scheduling, path planning

刘景祥, 徐文政. 多节点部分充电模型下的充电调度优化[J]. 计算机工程与应用, 2023, 59(6): 251-257.

LIU Jingxiang, XU Wenzheng. Optimization of Charging Scheduling Under Multi-Node Partial Charging Model[J]. Computer Engineering and Applications, 2023, 59(6): 251-257.

参考文献

[1] BOUBRIMA A，BECHKIT W，RIVANO H.Optimal WSN deployment models for air pollution monitoring[J].IEEE Transactions on Wireless Communications，2017，16（5）：2723-2735.
[2] MOUSSA N，ALAOUI A，CHAUDET C.A novel approach of WSN routing protocols comparison for forest fire detection[J].Wireless Networks，2018，26（3）：1857-1867.
[3] GUO Z，PENG J，XU W，et al.Minimizing redundant sensing data transmissions in energy-harvesting sensor networks via exploring spatial data correlations[J].IEEE Internet of Things Journal，2021，8（1）：512-527.
[4] SAMPLE A P，YEAGER D J，POWLEDGE P S，et al.Design of an RFID-based battery-free programmable sensing platform[J].IEEE Transactions on Instrumentation and Measurement，2008，57（11）：2608-2615.
[5] 水九生，王然.一种按需多节点优先级充电调度算法[J].电子科技，2021，34（8）：43-49.
SHUI J S，WANG R.An on-demand multi-node priority charging scheduling algorithm[J].Electronic Science and Technology，2021，34（8）：43-49.
[6] 王茜，崔志华，王丽芳.无线可充电传感器网络中的充电路径优化[J].小型微型计算机系统，2021，42（10）：2167-2172.
WANG Q，CUI Z H，WANG L F.Charging path optimization in wireless rechargeable sensor network[J].Journal of Chinese Computer Systems，2021，42（10）：2167-2172.
[7] 张娜，赵传信，陈思光，等.无线可充电传感器网络混合移动充电调度研究[J].传感技术学报，2021，34（9）：1237-1249.
ZHANG N，ZHAO C X，CHEN S G，et al.Research on hybrid mobile charging scheduling in wireless rechargeable sensor networks[J].Chinese Journal of Sensors and Actuators，2021，34（9）：1237-1249.
[8] WANG N，WU J，DAI H.Bundle charging：wireless charging energy minimization in dense wireless sensor networks[C]//2019 IEEE 39th International Conference on Distributed Computing Systems，2019：810-820.
[9] XU W，LIANG W，JIA X，et al.Maximizing sensor lifetime with the minimal service cost of a mobile charger in wireless sensor networks[J].IEEE Transactions on Mobile Computing（TMC），2018，17（11）：2564-2577.
[10] LIU T，WU B，ZHANG S，et al.An effective multi-node charging scheme for wireless rechargeable sensor networks[C]//IEEE INFOCOM 2020-IEEE Conference on Computer Communications，2020：2026-2035.
[11] YANG P，WU T，DAI H，et al.MORE：multi-node mobile charging scheduling for deadline constraints[J].ACM Transactions on Sensor Networks（TOSN），2020，17（1）：1-21.
[12] SHAH R C，RABAEY J M.Energy aware routing for low energy ad hoc sensor networks[C]//2002 IEEE Wireless Communications and Networking Conference Record，2002：350-355.
[13] LI J，MOHAPATRA P.Analytical modeling and mitigation techniques for the energy hole problem in sensor networks[J].Pervasive and Mobile Computing，2007，3（3）：233-254.
[14] VAIDYA P M.Speeding-up linear programming using fast matrix multiplication[C]//30th Annual Symposium on Foundations of Computer Science，1989：332-337.
[15] CHRISTOFIDES N.Worst-case analysis of a new heuristic for the travelling salesman problem[R].Carnegie Mellon University Pittsburgh Pa Management Sciences Research Group，1976.
[16] XU W，LIANG W，JIA X，et al.Minimizing the maximum charging delay of multiple mobile chargers under the multi-node energy charging scheme[J].IEEE Transactions on Mobile Computing（TMC），2021，20（5）：1846-1861.
[17] OSSIA Whitepaper.Cota versus other wireless power technologies[EB/OL].[2022-01-24].https：//www.ossia.com/resources-library/.