计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (6): 355-364.doi: 10.11896/jsjkx.240400186

• 计算机网络 • 上一篇    下一篇

无线可充电传感器网络中异构感知的限时移动充电调度

李德强, 任新一, 徐佳   

  1. 南京邮电大学先进网络与经济实验室 南京 210023
  • 收稿日期:2024-04-28 修回日期:2024-08-14 出版日期:2025-06-15 发布日期:2025-06-11
  • 通讯作者: 徐佳(xujia@njupt.edu.cn)
  • 作者简介:(lideqiang@njupt.edu.cn)
  • 基金资助:
    国家自然科学基金(62372249,62272237,62302236,62171217,62272244,62372250);江苏省自然科学基金(BK20230350);南京邮电大学引进人才科研启动基金(NY222014)

Time-constrained Mobile Charging Scheduling for Heterogeneous Sensing in Wireless Rechargeable Sensor Networks

LI Deqiang, REN Xinyi, XU Jia   

  1. Advanced Network and Economic Lab,Nanjing University of Posts and Telecommunications,Nanjing 210023,China
  • Received:2024-04-28 Revised:2024-08-14 Online:2025-06-15 Published:2025-06-11
  • About author:LI Deqiang,born in 1990,Ph.D,lecturer,is a member of CCF(No.O0276M).His main research interests include wireless charging scheduling,optimization algorithm and data mining.
    XU Jia,born in 1980,Ph.D,professor,Ph.D supervisor,is a senior member of CCF(No.18435S).His main research interests include crowd intelligence sensing,wireless rechargeable network,edge computing and blockchain.
  • Supported by:
    National Natural Science Foundation of China(62372249,62272237,62302236,62171217,62272244,62372250),Natural Science Foundation of Jiangsu Province(BK20230350) and Nanjing University of Posts and Telecommunication Introdued Talent Research Startup Fund(NY222014).

PDF (PC)

105

摘要： 无线传感器网络被广泛应用于军事监视、灾害预测、危险环境勘探等领域。然而,无线传感器的寿命有限,需要频繁更换电池才能维持正常工作,这带来了昂贵的维护成本和极大的不便。近年来,随着无线电力传输技术的发展,无线可充电传感器网络应运而生,为研究提供了新的思路。尽管如此,大多数相关工作仅考虑充电电量对调度的制约,未能体现现实情况下传感器质量不同与紧急任务中时间的重要性。将时间和电量同时作为约束,研究无线可充电传感器网络中异构感知的充电调度问题。首先,以最大化传感器的监控效用为目标,形式化了无线可充电传感器网络中针对异构感知的有限时间下的充电调度问题,并证明了该问题的NP困难性;然后,通过对充电时间离散化,将问题转化为子模最大化问题,并提出了针对转化后问题的近似算法;最后,通过大量的仿真实验验证了该算法的有效性。结果表明所提出的算法可以显著提高监控效用,且有理论支撑该效果与最优值之间的近似比,例如与传统NJNP算法相比,其将监控效用最多提高了279.79%。

关键词: 无线可充电传感器网络, 移动充电, 充电时间离散化, 子模函数, 近似算法

Abstract: Wireless Sensor Networks(WSNs) are widely deployed in various applications,including military surveillance,disaster prediction,and hazardous environment exploration.However,the limited lifespan of wireless sensors necessitates frequent battery replacements,leading to high maintenance costs and significant inconvenience.In recent years,with the advent of wireless power transmission technology,wireless rechargeable sensor networks(WRSNs) have been developed to address these issues,providing new avenues for research.Nonetheless,existing studies typically prioritize charging capacities,underestimating the urgency and heterogeneity of sensors in emergency scheduling.Formally,this paper treats the scheduling task as a constrained optimization problem with the aim to maximizing the monitoring utility for heterogeneous sensors,which has been proven to be NP-hard.Therefore,it converts the problem to sub-modular maximization through the discretization of charging time.This naturally leads to develop approximate algorithms based on a greedy strategy,with theoretical backing for the approximation ratio to the optimal value.Extensive experiments demonstrate that the proposed algorithms can significantly enhance monitoring utility,with the highest improvement reaching 279.79% compared to the classical NJNP algorithm.

Key words: Wireless rechargeable sensor network, Mobile charging, Discretization of charging time, Submodular function, Approximation algorithm

中图分类号: 

  • TP393
[1]LU X,WANG P,NIYATO D,et al.Wireless Charging Technologies:Fundamentals,Standards,and Network Applications[J].IEEE Communications Surveys & Tutorials,2015,18(2):1413-1452.
[2]SUN G,LIU Y,WANG A,et al.Sidelobe Control by Node Selection Algorithm Based on Virtual Linear Array for Collaborative Beamforming in WSNs[J].Wireless Personal Communications,2016,90:1443-1462.
[3]ANASTASI G,CONTI M,DI FRANCESCO M,et al.Energy conservation in wireless sensor networks:A survey[J].Ad hoc networks,2009,7(3):537-568.
[4]KANSAL A,HSU J,ZAHEDI S,et al.Power management in energy harvesting sensor networks[J].ACM Transactions on Embedded Computing Systems(TECS),2007,6(4):32.
[5]REN X,LIANG W,XU W.Use of a Mobile Sink for Maximizing Data Collection in Energy Harvesting Sensor Networks[C]//2013 42nd International Conference on Parallel Proces-sing.IEEE,2013:439-448.
[6]AZIZ S A,WANG X,HAWBANI A,et al.Wireless Rechargeable Sensor Networks:Energy Provisioning Technologies,Charging Scheduling Schemes,and Challenges[J].IEEE Transactions on Sustainable Computing,2025(99):1-20.
[7]CHING T W,WONG Y S.Review of wireless charging techno-logies for electric vehicles[C]//2013 5th International Confe-rence on Power Electronics Systems and Applications(PESA).IEEE,2013:1-4.
[8]XU J,HU S,WU S,et al.Cooperative Charging as Service:Scheduling for Mobile Wireless Rechargeable Sensor Networks[C]//2021 IEEE 41st International Conference on Distributed Computing Systems(ICDCS).IEEE,2021:685-695.
[9]HE S,CHEN J,JIANG F,et al.Energy provisioning in wireless rechargeable sensor networks[J].IEEE transactions on mobile computing,2012,12(10):1931-1942.
[10]LIU H,HUANG X,TAN L,et al.Dynamic wireless charging for inspection robots based on decentralized energy pickup structure[J].IEEE Transactions on Industrial Informatics,2017,14(4):1786-1797.
[11]JIN Y,XU J,WU S,et al.Bus Network Assisted Drone Scheduling for Sustainable Charging of Wireless Rechargeable Sensor Network[J].Journal of Systems Architecture,2021,116:102059.
[12]JIN Y,XU J,WU S,et al.Enabling the Wireless Charging via Bus Network:Route Scheduling for Electric Vehicles[J].IEEE Transactions on Intelligent Transportation Systems,2020,22(3):1827-1839.
[13]WU S,DAI H,XU L,et al.Comprehensive Cost Optimization for Charger Deployment in Multi-hop Wireless Charging[J].IEEE Transactions on Mobile Computing,2022,22(8):4563-4577.
[14]FU L,CHENG P,GU Y,et al.Optimal charging in wireless rechargeable sensor networks[J].IEEE Transactions on Vehicular Technology,2015,65(1):278-291.
[15]ZHANG S,WU J,LU S.Collaborative mobile charging[J].IEEE Transactions on Computers,2014,64(3):654-667.
[16]LIANG W,XU Z,XU W,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.
[17]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,2018,17(11):2564-2577.
[18]XU W,LIANG W,JIA X,et al.An effective multi-node charging scheme for wireless rechargeable sensor networks[C]//IEEE INFOCOM 2020-IEEE Conference on Computer Communications.IEEE,2020:2026-2035.
[19]LIN C,HAO S,DAI H,et al.Maximizing charging efficiency with Fresnel zones[J].IEEE Transactions on Mobile Computing,2022,23(1):612-629.
[20]YANG W,LIN C,DAI H,et al.Robust wireless rechargeable sensor networks[J].IEEE/ACM Transactions on Networking,2022,31(3):949-964.
[21]LIU J,PENG J,XU W,et al.Maximizing sensor lifetime viamulti-node partial-charging on sensors[J].IEEE Transactions on Mobile Computing,2023,22(11):6571-6584.
[22]HUANG S,SHA C,ZHU X,et al.Charging Scheduling Method for Wireless Rechargeable Sensor Networks Based on Energy Consumption Rate Prediction for Nodes[J].Sensors,2024,24(18):5931.
[23]CHEN J Y,YI C Y,WANG R,et al.Optimization of Data Collection and Charging in Industrial Wireless Rechargeable Sensor Networks[J].Journal of Chinese Computer Systems.2024,45(7):1686-1694.
[24]XU W,LIANG W,KAN H,et al.Minimizing the longest charge delay of multiple mobile chargers for wireless rechargeable sensor networks by charging multiple sensors simultaneously[C]//2019 IEEE 39th International Conference on Distributed Computing Systems(ICDCS).IEEE,2019:881-890.
[25]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,2020,20(5):1846-1861.
[26]LATA S,MEHFUZ S,UROOJ S,et al.Fuzzy clustering algorithm for enhancing reliability and network lifetime of wireless sensor networks[J].IEEE Access,2020,8:66013-66024.
[27]WU S,DAI H,LIU L,et al.Cooperative scheduling for direc-tional wireless charging with spatial occupation[J].IEEE Transactions on Mobile Computing,2024,23(1):286-301.
[28]JIA R,WU J,LU J,et al.Energy saving in heterogeneous wireless rechargeable sensor networks[C]//IEEE INFOCOM 2022-IEEE Conference on Computer Communications.IEEE,2022:1838-1847.
[29]JIA R,WU J,WANG X,et al.Energy cost minimization in wireless rechargeable sensor networks[J].IEEE/ACM Transactions on Networking,2023,31(5):2345-2360.
[30]SUN Y,LIN C,DAI H,et al.Trading off charging and sensing for stochastic events monitoring in WRSNs[J].IEEE/ACM Transactions on Networking,2021,30(2):557-571.
[31]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.
[32]REN Y,LIU A,MAO X,et al.An intelligent charging scheme maximizing the utility for rechargeable network in smart city[J].Pervasive and Mobile Computing,2021,77:101457.
[33]YE X,LIANG W.Charging utility maximization in wireless rechargeable sensor networks[J].Wireless Networks,2017,23:2069-2081.
[34]WU T,YANG P,DAI H,et al.Charging Oriented Sensor Placement and Flexible Scheduling in Rechargeable WSNs[C]//IEEE INFOCOM 2019-IEEE Conference on Computer Communications.IEEE,2019:73-81.
[35]WU T,YANG P,DAI H,et al.Optimal Charging Oriented Sensor Placement and Flexible Scheduling in Rechargeable WSNs[J].ACM Transactions on Sensor Networks(TOSN),2022,18(3):1-27.
[36]MA Y,LIANG W,XU W.Charging utility maximization inwireless rechargeable sensor networks by charging multiple sensors simultaneously[J].IEEE/ACM Transactions on Networking,2018,26(4):1591-1604.
[37]XU W,LIANG W,KAN H,et al.Minimizing the longest charge delay of multiple mobile chargers for wireless rechargeable sensor networks by charging multiple sensors simultaneously[C]//2019 IEEE 39th International Conference on Distributed Computing Systems(ICDCS).IEEE,2019:881-890.
[38]ZHANG H,VOROBEYCHIK Y.Submodular optimization with routing constraints[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2016:819-825.
[39]LIN C,HAO S,DAI H,et al.Maximizing Charging EfficiencyWith Fresnel Zones[J].IEEE Transactions on Mobile Computing,2024,23(1):612-629.
[40] DANDE B,CHANG C Y,WU S J,et al.WLARS:Workload-Aware Recharge Scheduling Mechanism for Improving Surveillance Quality in Wireless Rechargeable Sensor Networks[J].IEEE Sensors Journal,2023,23(11):12237-12250.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发