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

doi:10.11959/j.issn.2096-3750.2023.00364

Abstract

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

CLC Number:

TP393

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.

Figures/Tables 6

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

Charging path optimization in mobile wireless rechargeable sensor networks

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 50

Related Articles 15

Metrics

Recommended 0

[1]	Yanjue LI, Wenxuan HAN, Hailong ZHU, Changchuan YIN. A hybrid traffic scheduling mechanism applied to large scale time-sensitive networking [J]. Chinese Journal on Internet of Things, 2023, 7(4): 72-87.
[2]	Yang ZHOU, Honglong CHEN, Lei ZHANG. An algorithm for joint optimization of dynamic routing and scheduling in time-sensitive networking [J]. Chinese Journal on Internet of Things, 2023, 7(4): 52-62.
[3]	Min FAN, Siyuan SHAO, Chao HE, Xiang WANG, Haiming WANG. Next-generation mmWave WLAN: vision and key enabling technologies [J]. Chinese Journal on Internet of Things, 2023, 7(3): 1-14.
[4]	Guanglei GENG, Bo GAO, Ke XIONG, Pingyi FAN, Yang LU, Yuwei WANG. A survey of federated learning for 6G networks [J]. Chinese Journal on Internet of Things, 2023, 7(2): 50-66.
[5]	Chao HU, Bangyan LU, Yanbing YANG, Zhe CHEN, Lei ZHANG, Liangyin CHEN. Human activity recognition system based on low-cost IoT chip ESP32 [J]. Chinese Journal on Internet of Things, 2023, 7(2): 133-142.
[6]	Zhihong WANG, Supeng LENG, Kai XIONG. Multi-agent resource allocation strategy for UAV swarm-based cooperative sensing [J]. Chinese Journal on Internet of Things, 2023, 7(1): 18-26.
[7]	Nongyu WEI, Zilong JIANG, Fangjiong CHEN. AODV protocol for acoustic-radio integrated network based on location information and energy balance [J]. Chinese Journal on Internet of Things, 2023, 7(1): 27-36.
[8]	Cenhuishan LIAO, Junyan CHEN, Guanping LIANG, Xiaolan XIE, Xiaoye LU. Quality of service optimization algorithm based on deep reinforcement learning in software defined network [J]. Chinese Journal on Internet of Things, 2023, 7(1): 73-82.
[9]	Bei TANG, Qian WANG, Siguang CHEN. Radio frequency energy harvesting-combined collaborative energy-saving computation offloading mechanism [J]. Chinese Journal on Internet of Things, 2023, 7(1): 83-92.
[10]	Yao LIU, Yueyuan HE, Hongjing ZHOU, Chaoliang LI, Chuang LI. Partial computation offloading method based on joint resource allocation for mobile edge computing [J]. Chinese Journal on Internet of Things, 2023, 7(1): 140-148.
[11]	Wenxuan HAN, Hailong ZHU, Xinxin HE, Yanjue LI, Changchuan YIN. A TSN traffic scheduling algorithm combined with enqueue shaping [J]. Chinese Journal on Internet of Things, 2022, 6(4): 117-127.
[12]	Huanhuan ZHANG, Anfu ZHOU, Huadong MA. Reinforcement learning-based real-time video streaming control and on-device training research [J]. Chinese Journal on Internet of Things, 2022, 6(4): 1-13.
[13]	Yingyun GUO, Bo GAO, Zhifei ZHANG, Yu ZHANG, Ke XIONG. An incentive mechanism with bandwidth allocation for federated learning [J]. Chinese Journal on Internet of Things, 2022, 6(4): 82-92.
[14]	Fangyuan XING, Shibo HE, Mingyang SUN, Jiming CHEN. Carbon emission monitoring based on internet of things with cloud-tube-edge-end structure [J]. Chinese Journal on Internet of Things, 2022, 6(4): 53-64.
[15]	Jin QI, Wei WANG, Mengxi CHEN, Bin XU, Zhenjiang DONG, Yanfei SUN. Concept, architecture and key technologies of industrial internet [J]. Chinese Journal on Internet of Things, 2022, 6(2): 38-49.