移动无线可充电传感器网络中的充电路径优化

doi:10.11959/j.issn.2096-3750.2023.00364

摘要/Abstract

摘要：

无线能量传输技术能够有效缓解无线传感器网络中传感器节点的能量供给瓶颈问题，延长网络寿命甚至实现网络的永久可持续性运转。已有工作大多针对静态无线传感器网络（传感器节点位置固定）研究静态充电器的部署问题或是移动充电器的充电路径优化问题，而忽略了传感器节点移动的场景。因此，针对动态无线传感器网络（传感器节点可以移动），设计并优化了移动充电器在网络中的充电路径，使得在有限的时间内最大化移动充电器的充电效用，即充电器在有限的时间内遇到尽可能多的传感器节点并为它们充电。注意，移动充电器在移动的过程中可以选择停下来，为其当前位置充电范围内所遇到的多个节点同时进行无线充电。首先证明该问题是一个 APX-hard 问题。其次，基于离散化构造的有向无环图，提出一种基于回溯思想的分层剪枝算法，该算法以贪婪算法的解作为基准，逐层剪枝，从而得到固定时隙划分下的最优充电路径。仿真结果表明，所提算法能够有效地提升充电效用。

关键词: 移动无线网络, 移动充电器调度, 分层剪枝算法

Abstract:

The wireless power transfer technique is promising in solving the energy bottleneck of sensor nodes in wireless sensor networks, which can thus prolong the network lifetime or even maintain sustainable network operations.Most existing works focused on optimizing the static chargers’ deployment or mobile chargers’ charging path for static sensor nodes with fixed sensor node positions, ignoring the scenario with mobile sensor nodes.Thus, design and optimize the charging path of a mobile charger was studied for dynamic wireless sensor networks with mobile sensor nodes, to maximize the charging utility within a finite time horizon, that is, the charger can encounter as more sensor nodes as possible in a limited time and charge them.Notice that the mobile charger may stop to simultaneously charge multiple nodes within its charging range during its charging tour.The proposed charging path optimization problem was proven to be an APX-hard problem.Then, based on the constructed directed acyclic graph using discretization method, a layer-wise pruning algorithm based on the backtracking method was proposed.The proposed algorithm took the solution generated by the greedy algorithm as the benchmark and searched the optimal charging path under a fixed time division by layer-wise pruning.Simulation results show that the proposed algorithm can effectively improve the charging utility .

Key words: mobile wireless network, mobile charger scheduling, layer-wise pruning algorithm

中图分类号:

TP393

牛权龙, 贾日恒, 李明禄. 移动无线可充电传感器网络中的充电路径优化[J]. 物联网学报, 2023, 7(4): 110-122.

Quanlong NIU, Riheng JIA, Minglu LI. Charging path optimization in mobile wireless rechargeable sensor networks[J]. Chinese Journal on Internet of Things, 2023, 7(4): 110-122.

图/表 6

图1

图2

图3

图4

图5

图6

参考文献 50

[1]	KURS A , KARALIS A , MOFFATT R ,et al. Wireless power transfer via strongly coupled magnetic resonances[J]. Science, 2007,317(5834): 83-86.
[2]	SHINOHARA N . Trends in wireless power transfer:WPT technology for energy harvesting,mllimeter-wave/THz rectennas,MIMO-WPT,and advances in near-field WPT applications[J]. IEEE Microwave Magazine, 2021,22(1): 46-59.
[3]	XIE L G , SHI Y , HOU Y T ,et al. Wireless power transfer and applications to sensor networks[J]. IEEE Wireless Communications, 2013,20(4): 140-145.
[4]	HUANG J , ZHOU Y D , NING Z L ,et al. Wireless power transfer and energy harvesting:current status and future prospects[J]. IEEE Wireless Communications, 2019,26(4): 163-169.
[5]	YANG Y Y , WANG C . Wireless rechargeable sensor networks[M]. Cham: Springer International Publishing, 2015.
[6]	HE S B , CHEN J M , JIANG F C ,et al. Energy provisioning in wireless rechargeable sensor networks[J]. IEEE Transactions on Mobile Computing, 2013,12(10): 1931-1942.
[7]	WANG C , LI J , YE F ,et al. A mobile data gathering framework for wireless rechargeable sensor networks with vehicle movement costs and capacity constraints[J]. IEEE Transactions on Computers, 2016,65(8): 2411-2427.
[8]	孙鸿广 . 可充电传感器网络中充电节点的部署规划研究[D]. 南京:南京邮电大学, 2021.
	SUN H G . Research on the deployment planning of charging nodes in rechargeable sensor networks[D]. Nanjing:Nanjing University of Posts and Telecommunications, 2021.
[9]	ZHANG S , QIAN Z Z , KONG F Y ,et al. P3:Joint optimization of charger placement and power allocation for wireless power transfer[C]// Proceedings of 2015 IEEE Conference on Computer Communications (INFOCOM). Piscataway:IEEE Press, 2015: 2344-2352.
[10]	WANG Z , DUAN L J , ZHANG R . Adaptively directional wireless power transfer for large-scale sensor networks[J]. IEEE Journal on Selected Areas in Communications, 2016,34(5): 1785-1800.
[11]	DAI H P , WANG X Y , LIU A X ,et al. Wireless charger placement for directional charging[J]. IEEE/ACM Transactions on Networking, 2018,26(4): 1865-1878.
[12]	DAI H P , SUN K , LIU A X ,et al. Charging task scheduling for direc tional wireless charger networks[J]. IEEE Transactions on Mobile Computing, 2021,20(11): 3163-3180.
[13]	YU N , DAI H P , CHEN G H ,et al. Connectivity-constrained placement of wireless chargers[J]. IEEE Transactions on Mobile Computing, 2021,20(3): 909-927.
[14]	DAI H P , WU C F , WANG X Y ,et al. Placing wireless chargers with limited mobility[C]// Proceedings of IEEE INFOCOM 2020 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2020: 2056-2065.
[15]	WANG X Y , DAI H P , WANG W J ,et al. Practical heterogeneous wireless charger placement with obstacles[J]. IEEE Transactions on Mobile Computing, 2020,19(8): 1910-1927.
[16]	DAI H P , LIU Y H , CHEN G H ,et al. Safe charging for wireless power transfer[C]// Proceedings of IEEE INFOCOM 2014 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2014: 1105-1113.
[17]	DAI H P , LIU Y H , YU N ,et al. Radiation constrained wireless charger placement[J]. IEEE/ACM Transactions on Networking, 2021,29(1): 48-64.
[18]	GUO P , LIU X F , TANG S J ,et al. Concurrently wireless charging sensor networks with efficient scheduling[J]. IEEE Transactions on Mobile Computing, 2017,16(9): 2450-2463.
[19]	SUN Y , LIN C , DAI H P ,et al. Recycling wasted energy for mobile charging[C]// Proceedings of 2021 IEEE 29th International Conference on Network Protocols (ICNP). Piscataway:IEEE Press, 2021: 1-11.
[20]	LIN C , HAO S B , DAI H P ,et al. Maximizing charging efficiency with Fresnel zones[J]. IEEE Transactions on Mobile Computing, 2022,PP(99): 1-17.
[21]	YANG W , LIN C , DAI H P ,et al. Robust wireless rechargeable sensor networks[J]. IEEE/ACM Transactions on Networking, 2023,31(3): 949-964.
[22]	SUN Y , LIN C , DAI H P ,et al. Trading off charging and sensing for stochastic events monitoring in WRSNs[J]. IEEE/ACM Transactions on Networking, 2022,30(2): 557-571.
[23]	LIN C , GUO C Y , DAI H P ,et al. Near optimal charging scheduling for 3-D wireless rechargeable sensor networks with energy constraints[C]// Proceedings of 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS). Piscataway:IEEE Press, 2019: 624-633.
[24]	YANG P L , WU T , DAI H P ,et al. MORE:multi-node mobile charging scheduling for deadline constraints[J]. ACM Transactions on Sensor Networks, 2020,17(1): 1-21.
[25]	WU T , YANG P L , DAI H P ,et al. Joint sensor selection and energy allocation for tasks-driven mobile charging in wireless rechargeable sensor networks[J]. IEEE Internet of Things Journal, 2020,7(12): 11505-11523.
[26]	SHI Y , XIE L G , HOU Y T ,et al. On renewable sensor networks with wireless energy transfer[C]// 2011 Proceedings IEEE INFOCOM. Piscataway:IEEE Press, 2011: 1350-1358.
[27]	HE L , KONG L H , GU Y ,et al. Evaluating the on-demand mobile charging in wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2015,14(9): 1861-1875.
[28]	CHEN L , LIN S , HUANG H . Charge me if you can:charging path optimization and scheduling in mobile networks[C]// Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York:ACM Press, 2016: 101-110.
[29]	LIANG W F , XU Z C , XU W Z ,et al. Approximation algorithms for charging reward maximization in rechargeable sensor networks via a mobile charger[J]. IEEE/ACM Transactions on Networking, 2017,25(5): 3161-3174.
[30]	WU T , YANG P L , DAI H P ,et al. Collaborated tasks-driven mobile charging and scheduling:a near optimal result[C]// Proceedings of IEEE INFOCOM 2019 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2019: 1810-1818.
[31]	DAI H P , MA Q F , WU X B ,et al. CHASE:Charging and scheduling scheme for stochastic event capture in wireless rechargeable sensor networks[J]. IEEE Transactions on Mobile Computing, 2020,19(1): 44-59.
[32]	MA Y , LIANG W F , XU W Z . Charging utility maximization in wireless rechargeable sensor networks by charging multiple sensors simultaneously[J]. IEEE/ACM Transactions on Networking, 2018,26(4): 1591-1604.
[33]	LIU J X , PENG J , XU W Z ,et al. Maximizing sensor lifetime via multi-node partial-charging on sensors[J]. IEEE Transactions on Mobile Computing, 2022,PP(99): 1-14.
[34]	LIN C , GAO F , DAI H P ,et al. Maximizing charging utility with obstacles through Fresnel diffraction model[C]// Proceedings of IEEE INFOCOM 2020 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2020: 2046-2055.
[35]	FU L K , CHENG P , GU Y ,et al. Minimizing charging delay in wireless rechargeable sensor networks[C]// 2013 Proceedings IEEE INFOCOM. Piscataway:IEEE Press, 2013: 2922-2930.
[36]	FU L K , CHENG P , GU Y ,et al. Optimal charging in wireless rechargeable sensor networks[J]. IEEE Transactions on Vehicular Technology, 2016,65(1): 278-291.
[37]	LIN C , ZHOU Y H , MA F L ,et al. Minimizing charging delay for directional charging in wireless rechargeable sensor networks[C]// Proceedings of IEEE INFOCOM 2019 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2019: 1819-1827.
[38]	ZHOU P Z , WANG C , YANG Y Y . Leveraging target k-coverage in wireless rechargeable sensor networks[C]// Proceedings of 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS). Piscataway:IEEE Press, 2017: 1291-1300.
[39]	ZHANG S , QIAN Z Z , WU J ,et al. Optimizing itinerary selection and charging association for mobile chargers[J]. IEEE Transactions on Mobile Computing, 2017,16(10): 2833-2846.
[40]	WANG C , LI J , YANG Y Y ,et al. Combining solar energy harvesting with wireless charging for hybrid wireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2018,17(3): 560-576.
[41]	ZHOU P Z , WANG C , YANG Y Y . Self-sustainable sensor networks with multi-source energy harvesting and wireless charging[C]// Proceedings of IEEE INFOCOM 2019 - IEEE Conference on Computer Communications. Piscataway:IEEE Press, 2019: 1828-1836.
[42]	陈肖依 . 可充电传感网中基于成本最小化的能量空洞缓解移动充电策略[D]. 南京:南京邮电大学, 2022.
	CHEN X Y . A mobile charging strategy based on cost minimization for energy hole mitigation in wireless rechargeable sensor networks[D]. Nanjing:Nanjing University of Posts and Telecommunications, 2022.
[43]	SHU Y C , YOUSEFI H , CHENG P ,et al. Near-optimal velocity control for mobile charging in wireless rechargeable sensor networks[J]. IEEE Transactions on Mobile Computing, 2016,15(7): 1699-1713.
[44]	LIU T , WU B J , ZHANG S H ,et al. An effective multi-node charging scheme for wireless rechargeable sensor networks[C]// Proceedings of IEEE INFOCOM 2020 - IEEE Conference on Computer Communications. New York:ACM Press, 2020: 2026-2035.
[45]	陈波 . 大型土木结构中无线传感器网络充电节点路径优化策略研究[D]. 武汉:湖北工业大学, 2016.
	CHEN B . Research on path optimization strategy of charging nodes in wireless sensor networks in large civil structures[D]. Wuhan:Hubei University of Technology, 2016.
[46]	TSILIGIRIDES T . Heuristic methods applied to orienteering[J]. Journal of the Operational Research Society, 1984,35(9): 797-809.
[47]	BLUM A , CHAWLA S , KARGER D R ,et al. Approximation algorithms for orienteering and discounted-reward TSP[J]. SIAM Journal on Computing, 2007,37(2): 653-670.
[48]	GUNAWAN A , LAU H C , VANSTEENWEGEN P . Orienteering problem:a survey of recent variants,solution approaches and applications[J]. European Journal of Operational Research, 2016,255(2): 315-332.
[49]	XU W Z , LIANG W F , XU Z C ,et al. Approximation algorithms for the generalized team orienteering problem and its applications[J]. IEEE/ACM Transactions on Networking, 2021,29(1): 176-189.
[50]	KHODADADIAN M , DIVSALAR A , VERBEECK C ,et al. Time dependent orienteering problem with time windows and service time dependent profits[J]. Computers ＆ Operations Research, 2022(143): 105794.