An Approximation Algorithm for Path Planning of Vehicles for Data Collection in Wireless Rechargeable Sensor Networks

被引:1
作者
Kumar, Rohit [1 ]
Mukherjee, Joy Chandra [1 ]
机构
[1] Indian Inst Technol Bhubaneswar, Sch Elect Sci, Bhubaneswar, Odisha, India
来源
PROCEEDINGS OF THE 24TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING AND NETWORKING, ICDCN 2023 | 2023年
关键词
Approximation algorithms; Data Collection; Wireless rechargeable sensor networks; MOBILE SINKS;
D O I
10.1145/3571306.3571405
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Wireless rechargeable sensor networks (WRSNs) have been extensively used in various event detection and environmental monitoring applications, where it is important to collect environmental data from the sensors. Data may be collected at the base station (BS) through multi-hop communication. But it may cause sensors located near the BS to run out of their energy quickly. In a WRSN, data may also be collected using mobile vehicles that visit different sensors to collect data. However, in a large scale WRSN, travelling to all the sensors for data collection may cause vehicles to run out of their energy in the middle of their journey. In this paper, we formulate an optimization problem that minimizes the average travel distance of the vehicles while collecting data from maximum number of sensors. The problem is proved to be NP-complete. To avoid visiting all the sensors, our scheme selects a subset of sensors as anchor nodes that first collects data from neighboring sensors through one-hop transfer. Then, the anchor nodes are divided among the vehicles. Finally, a convex-hull based 3-approximation algorithm is proposed that finds the travel plan for each vehicle through the anchor nodes only, where the vehicle starts from the BS, collects data from the anchor nodes, while returning back to the BS at the end of its journey. Simulation results show that our scheme outperforms the existing schemes in terms of the average travel distance by vehicles, while collecting data from a large number of sensors.
引用
收藏
页码:207 / 216
页数:10
相关论文
共 23 条
[1]  
Cormen TH., 2009, Introduction to Algorithms, V3
[2]  
Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
[3]   Joint Mobile Data Gathering and Energy Provisioning in Wireless Rechargeable Sensor Networks [J].
Guo, Songtao ;
Wang, Cong ;
Yang, Yuanyuan .
IEEE TRANSACTIONS ON MOBILE COMPUTING, 2014, 13 (12) :2836-2852
[4]   An Optimal Data Gathering Method for Mobile Sinks in WSNs [J].
Ha, Ilkyu ;
Djuraev, Mamurjon ;
Ahn, Byoungchul .
WIRELESS PERSONAL COMMUNICATIONS, 2017, 97 (01) :1401-1417
[5]   A Joint Energy Replenishment and Data Collection Algorithm in Wireless Rechargeable Sensor Networks [J].
Han, Guangjie ;
Yang, Xuan ;
Liu, Li ;
Zhang, Wenbo .
IEEE INTERNET OF THINGS JOURNAL, 2018, 5 (04) :2596-2604
[6]   Employing mobile elements for delay-constrained data gathering in WSNs [J].
Konstantopoulos, Charalampos ;
Vathis, Nikolaos ;
Pantziou, Grammati ;
Gavalas, Damianos .
COMPUTER NETWORKS, 2018, 135 :108-131
[7]   On-demand vehicle-assisted charging in wireless rechargeable sensor networks [J].
Kumar, Rohit ;
Mukherjee, Joy Chandra .
AD HOC NETWORKS, 2021, 112
[8]  
Kumar R, 2020, INT CONF COMMUN SYST, DOI [10.1109/comsnets48256.2020.9027418, 10.1109/COMSNETS48256.2020.9027418]
[9]  
Kurs Andre, 2007, Wireless Power Transfer via Strongly Coupled Magnetic Resonances, V317, P83
[10]   Range extension cooperative MAC to attack energy hole in duty-cycled multi-hop WSNs [J].
Lin, Jian ;
Weitnauer, Mary Ann .
WIRELESS NETWORKS, 2018, 24 (05) :1419-1437