计算机科学

计算机科学 ›› 2025, Vol. 52 ›› Issue (10): 336-347.doi: 10.11896/jsjkx.240800113

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

面向异构移动可充电设备的最大返岗时间最小化无线充电调度

徐佳, 刘婧怡, 徐力杰, 刘林峰   

  1. 南京邮电大学江苏省大数据安全与智能处理重点实验室 南京 210023
  • 收稿日期:2024-08-21 修回日期:2024-11-10 出版日期:2025-10-15 发布日期:2025-10-14
  • 通讯作者: 徐佳(xujia@njupt.edu.cn)
  • 基金资助:
    国家自然科学基金(62372249,62072254,62272237) This work was supported by the

Wireless Charging Scheduling with Minimized Maximum Return-to-Work Time for Heterogeneous Mobile Rechargeable Devices

XU Jia, LIU Jingyi, XU Lijie, LIU Linfeng   

  1. Jiangsu Key Laboratory of Big Data Security and Intelligent Processing,Nanjing University of Posts and Telecommunications,Nanjing 210023,China
  • Received:2024-08-21 Revised:2024-11-10 Online:2025-10-15 Published:2025-10-14
  • About author:XU Jia,born in 1980,Ph.D,professor,Ph.D supervisor,is a senior member of CCF(No.18435S).His main research interests include crowdsourcing,edge computing and wireless rechargeable sensor networks.
  • Supported by:
    National Natural Science Foundation of China(62372249,62072254,62272237).

PDF (PC)

2

摘要： 随着无线可充电设备的广泛应用,无线功率传输技术成为提高设备续航能力的关键技术。然而,目前大部分研究工作聚焦于优化充电效率、充电成本等充电本身的性能,任务驱动的充电调度的研究尚不充分;另外,大部分充电系统假设充电器或可充电设备是同构的;进一步地,现有工作对移动可充电设备的充电调度问题关注较少。针对实际情况中可充电设备的异构性,提出了异构无线充电模型,形式化了异构无线可充电传感网中的移动可充电设备最大返岗时间最小化问题。首先,在忽略设备移动时间和移动能耗的前提下,研究了简化的最大返岗时间最小化问题,并提出了一个近似算法。为解决具有更大难度的最大返岗时间最小化问题,基于该近似算法的思想,提出了一个启发式算法。大量模拟实验和实物实验的结果表明,所提出的算法相对于其他算法有显著优势,可以减少最多38.78%的设备最大返岗时间。

关键词: 无线可充电传感网, 移动可充电设备, 充电调度, 异构无线充电, 启发式算法

Abstract: With the widespread application of wireless rechargeable devices,wireless power transfer technology has become a key enabler for enhancing device battery life.However,most existing research focuses on optimizing charging efficiency,charging costs,and other charging-related performance metrics.Task-driven charging scheduling has received limited attention.In addition,the majority of charging systems assume homogeneity either in chargers or rechargeable devices,and there is a lack of focus on charging scheduling for mobile rechargeable devices.Considering the heterogeneity of rechargeable devices in real-world scena-rios,this paper proposes a heterogeneous wireless charging model and formalizes the problem of minimizing the maximum return-to-work time of mobile rechargeable devices in heterogeneous wireless rechargeable sensor networks.Initially,it studies the simplified problem of minimizing the maximum return-to-work time under the assumption of ignoring device movement time and energy consumption,and proposes an approximation algorithm.To address the more challenging problem of minimizing the maximum return-to-work time,this paper proposes a heuristic algorithm based on the idea of this approximate algorithm for this problem.The results of extensive simulation and field experiments demonstrate that the proposed algorithm has significant advantages over other algorithms.The proposed algorithm can reduce at most 38.78% maximum return-to-work time of devices comparing with the benchmark algorithms.

Key words: Wireless rechargeable sensor network,Mobile rechargeable devices,Charging scheduling,Heterogeneous wireless charging,Heuristic algorithm

中图分类号: 

  • TP393
[1]ULLO S L,SINHA G R.Advances in smart environment monitoring systems using IoT and sensors[J].Sensors,2020,20(11):3113.
[2]BILAL M,KANG S G.An authentication protocol for futuresensor networks[J].Sensors,2017,17(5):979.
[3]FEINBERG S,WILLIAMS R,HAGLER G S W,et al.Long-term evaluation of air sensor technology under ambient conditions in Denver,Colorado[J].AtmosphericMeasurement Techniques,2018,11(8):4605-4615.
[4]PASTOR-APARICIO A,SEGURA-GARCIA J,LOPEZ-BALLESTER J,et al.Psychoacoustic annoyance implementation with wireless acoustic sensor networks for monitoring in smart cities[J].IEEE Internet of Things Journal,2019,7(1):128-136.
[5]MARRIWALA N,RATHEE P.An approach to increase thewireless sensor network lifetime[C]//2012 World Congress on Information and Communication Technologies.Piscataway,NJ:IEEE,2012:495-499.
[6]ZHOU P,WANG C,YANG Y.Self-sustainable sensor networks with multi-source energy harvesting and wireless charging[C]//IEEE INFOCOM 2019－IEEE Conference on Computer Communications.Piscataway,NJ:IEEE,2019:1828-1836.
[7]KURS A,KARALIS A,MOFFATT R,et al.Wireless power transfer via strongly coupled magnetic resonances[J].Science,2007,317(5834):83-86.
[8]WU T,YANG P,DAI H.Charging on the Move:SchedulingStatic Chargers with Tunable Power for Mobile Devices[C]//2021 IEEE/ACM 29th International Symposium on Quality of Service(IWQOS).Piscataway,NJ:IEEE,2021:1-10.
[9]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).Piscataway,NJ:IEEE,2021:685-695.
[10]WANG X,DAI H,HUANG H,et al.Robust scheduling for wireless charger networks[C]//IEEE INFOCOM 2019－IEEE Conference on Computer Communications.Piscataway,NJ:IEEE,2019:2323-2331.
[11]YANG P,WU T,DAI H,et al.MORE:Multi-node mobile charging scheduling for deadline constraints[J].ACM Transactions on Sensor Networks,2020,17(1):1-21.
[12]ZHANG J,GAO H,CHEN Q,et al.Task-oriented EnergyScheduling in Wireless Rechargeable Sensor Networks[J].ACM Transactions on Sensor Networks,2023,19(4):1-32.
[13]WU T,YANG P,DAI H,et al.Collaborated tasks-driven mobile charging and scheduling:A near optimal result[C]//IEEE INFOCOM 2019－IEEE Conference on Computer Communications.Piscataway,NJ:IEEE,2019:1810-1818.
[14]XUX L,CHEN C,HUANGFU X J,et al.Wireless charging scheduling algorithm of single mobile vehicle with limited energy[J].Computer Science,2018,45(3):110-116.
[15]KURS A,MOFFATT R,SOLJAČIC′ M.Simultaneous mid-range power transfer to multiple devices[J].Applied Physics Letters,2010,96(4):044102.
[16]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,2023,22(8):4563-4577.
[17]WU S,XU L,DAI H,et al.Optimizing Comprehensive Cost of Charger Deployment in Multi-hop Wireless Charging[J].ACM Transactions on Sensor Networks,2023,19(4):1-24.
[18]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,2021,22(3):1827-1839.
[19]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.
[20]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.
[21]GHARBI A,HAOUARI M.An approximate decomposition algorithm for scheduling on parallel machines with heads and tails[J].Computers & Operations Research,2007,34(3):868-883.
[22]Powercast[EB/OL].[2024-05-18].http://www.powercastco.com.
[23]WU S,DAI H,LIU L,et al.Cooperative scheduling for directional wireless charging with spatial occupation[J].IEEE Transactions on Mobile Computing,2024,23(1):286-301.
[24]KOULAMAS C,KYPARISIS G J.Makespan minimization onuniform parallel machines with release times[J].European Journal of Operational Research,2004,157(1):262-266.
[25]LI Y,CHEN Y,CHEN C S,et al.Charging while moving:Deploying wireless chargers for powering wearable devices[J].IEEE Transactions on Vehicular Technology,2018,67(12):11575-11586.
[26]CHEN L,LIN S,HUANG H,et al.Charging path optimization in mobile networks[J].IEEE/ACM Transactions on Networking,2022,30(5):2262-2273.
[27]LIU T,WU B,XU W,et al.RLC:A reinforcement learning-based charging algorithm for mobile devices[J].ACM Transactions on Sensor Networks,2021,17(4):1-23.
[28]LIN C,YANG Z,DAI H,et al.Minimizing charging delay for directional charging[J].IEEE/ACM Transactions on Networking,2021,29(6):2478-2493.
[29]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.
[30]SUN Y,LIN C,YANG W,et al.Charging dynamic sensorsthrough online learning[C]//IEEE INFOCOM 2023-IEEE Conference on Computer Communications.Piscataway,NJ:IEEE,2023:1-10.
[31]DING X,GUO J,WANG Y,et al.Task-driven charger placement and power allocation for wireless sensor networks[J].Ad Hoc Networks,2021,119:102556.
[32]PRIYADARSHANI S,TOMAR A,JANA P K.An efficientpartial charging scheme using multiple mobile chargers in wireless rechargeable sensor networks[J].Ad Hoc Networks,2021,113:102407.
[33]LIN C,GUO C,DENG J,et al.3DCS:A 3-D dynamic collaborative scheduling scheme for wireless rechargeable sensor networks with heterogeneous chargers[C]//2018 IEEE 38th International Conference on Distributed Computing Systems(ICDCS).Piscataway,NJ:IEEE,2018:311-320.
[34]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.Piscataway,NJ:IEEE,2022:1838-1847.
[35]CHEN L,LIN S,HUANG H.Charge me if youcan:Charging path optimization and scheduling in mobile networks[C]//Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing.ACM,2016:101-110.
[36]QI N,HUANG Z,ZHOU F,et al.A task-driven sequentialoverlapping coalition formation game for resource allocation in heterogeneous UAV networks[J].IEEE Transactions on Mobile Computing,2023,22(8):4439-4455.
[37]AL-SHAYEA A M,SALEH M,ALATEFI M,et al.Scheduling two identical parallel machines subjected to release times,delivery times and unavailability constraints[J].Processes,2020,8(9):1025.
[38]SCHUTTEN J M J,LEUSSINK R A M.Parallel machinescheduling with release dates,due dates and family setup times[J].International Journal of Production Economics,1996,46:119-125.
[39]LIU P,LU X.Online Scheduling on Two Parallel Machines with Release Times and Delivery Times[C]//International Confe-rence on Combinatorial Optimization and Applications.Berlin:Springer,2013:96-105.
[40]LI K,YANG S.Heuristic algorithms for scheduling on uniform parallel machines with heads and tails[J].Journal of Systems Engineering and Electronics,2011,22(3):462-467.
[41]DAI H,WANG X,LIU A X,et al.Optimizing wireless charger placement for directional charging[C]//IEEE INFOCOM 2017-IEEE Conference on Computer Communications.Piscataway,NJ:IEEE,2017:1-9.
[42]WANG Z,TAO J,XU Y,et al.Toward the Minimal Wait-forDelay for Rechargeable WSNs with Multiple Mobile Chargers[J].ACM Transactions on Sensor Networks,2023,19(4):1-24.
[43]Clearpath Robotics Dingo[EB/OL].[2024-05-18].https://clearpathrobotics.com/.
[44]KOULAMAS C,KYPARISIS G J.Scheduling on uniform parallel machines to minimize maximum lateness[J].Operations Research Letters,2000,26(4):175-179.
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
本系统由北京玛格泰克科技发展有限公司设计开发