计算机科学技术学报 ›› 2022,Vol. 37 ›› Issue (4): 869-887.doi: 10.1007/s11390-022-1993-0

所属专题: Computer Networks and Distributed Computing

• • 上一篇    下一篇

无线传感器网络的能量有效的最小移动充电设备覆盖研究

  

  • 收稿日期:2021-10-25 修回日期:2022-05-30 接受日期:2022-06-22 出版日期:2022-07-25 发布日期:2022-07-25

Energy-Efficient Minimum Mobile Charger Coverage for Wireless Sensor Networks

Abdalaziz Sawwan and Jie Wu, Fellow, IEEE        

  1. Department of Computer and Information Sciences, Temple University, Philadelphia 19122, U.S.A.
  • Received:2021-10-25 Revised:2022-05-30 Accepted:2022-06-22 Online:2022-07-25 Published:2022-07-25
  • Contact: Abdalaziz Sawwan E-mail:abdalaziz.sawwan@temple.edu
  • About author:Abdalaziz Sawwan is a second-year Ph.D. student in computer and information sciences at Temple University, Philadelphia. Sawwan received his Bachelor's degree in electrical engineering from the University of Jordan, Amman in 2020. His current research interests include mobile charging and wireless networks, routing protocols, and age of information.
  • Supported by:
    This work was supported in part by the National Science Foundation of USA under Grant Nos. 2128378, CNS 2107014, CNS 1824440, CNS 1828363, CNS 1757533, CNS 1629746, and CNS 1651947.

因为需要持续不断地给电池供电型传感器充电,所以维持无线传感器网络(WSN)的运转是个具有挑战性的问题。可以覆盖到网络中固定传感器,并能有效地无线地传输能量的可移动充电设备器(MC),有望解决这一挑战。保证所有的传感器正常工作,并且在满足传感器充电频率和充电设备的调度的前提下所需要的MC最少,是一个优化问题。在高维空间里,该优化问题为NP问题。而如果考虑一维空间是一条线还是一个环时,传感器具有同构充电频率这一特殊场景则有一个可解算法。本文旨在寻找在可解空间和不可解空间间的微妙的界限。具体而言,我们学习了在线性空间中,频率为1秒和2秒 (生命周期为1和0:5时间单位)的异构传感器,猜想其NP困难,提出了一个新的暴力破解算法,并给出了能提供1:5近似解决方案的线性贪婪算法。然后,我们介绍了使用最少MC的能源优化问题,并给出最优解决方案。我们通过充分的仿真验证了本文提出MC数量最小化算法的有效性。

关键词: 协同充电, 线性网络, 能源优化, 移动充电设备, 无线充电, 无线传感器网络

Abstract: Sustaining an operational wireless sensor network (WSN) is challenging due to the persistent need of the battery-powered sensors to be charged from time to time. The procedure of exploiting mobile chargers (MCs) that traverse to the fixed sensors of the network and wirelessly transfer energy in an efficient matter has been considered widely as a promising way to tackle this challenge. An optimization problem, called the mobile charger coverage problem, arises naturally to keep all of the sensors alive with an objective of determining both the minimum number of MCs required meeting the sensor recharge frequency and the schedule of these MCs. It is shown that this optimization problem becomes NP-hard in high-dimensional spaces. Moreover, the special case of the homogeneous recharge frequency of the sensors has already been proven to have a tractable algorithm if we consider whether the 1-dimensional space is a line or a ring. In this work, we seek to find a delicate border between the tractable and the intractable problem space. Specifically, we study the special case of heterogeneous sensors that take frequencies of 1's and 2's (lifetime of 1 and 0.5 time units) on a line, conjecture the special case's NP-hardness, propose a novel brute-force optimal algorithm, and present a linear-time greedy algorithm that gives a 1.5-approximation solution for the problem. Afterwards, we introduce the energy optimization problem of the MCs with the minimized number and solve it optimally. Comprehensive simulation is conducted to verify the efficiency of using our proposed algorithms that minimize the number of MCs.

Key words: cooperative charging, linear network, energy optimization, mobile charger, wireless charging, wireless sensor network

[1] Sawwan A, Wu J. Mobile charger coverage problem for specific heterogeneous wireless sensor networks. In Proc. the 18th IEEE Int. Conference on Mobile Ad Hoc and Smart System, Oct. 2021, pp.62-70. DOI: 10.1109/MASS52906.2021.00017.

[2] Beigel R, Wu J, Zheng H. On optimal scheduling of multiple mobile chargers in wireless sensor networks. In Proc. the 1st Int. Workshop on Mobile Sensing, Computing and Communication, Aug. 2014, pp.1-6. DOI: 10.1145/2633675.2633676.

[3] Zheng H, Wu J. Cooperative wireless charging vehicle scheduling. In Proc. the 14th IEEE Int. Conference on Mobile Ad Hoc and Sensor Systems, Oct. 2017, pp.224-232. DOI: 10.1109/MASS.2017.13.

[4] Shu Y, Yousefi H, Cheng P, Chen J, Gu Y J, He T, Shin K G. Near-optimal velocity control for mobile charging in wireless rechargeable sensor networks. IEEE Trans. Mobile Computing, 2015, 15(7): 1699-1713. DOI: 10.1109/TMC.2015.2473163.

[5] Kurs A, Karalis A, Moffatt R, Joannopoulos J D, Fisher P, Soljačić M. Wireless power transfer via strongly coupled magnetic resonances. Science, 2007, 317(5834): 83-86. DOI: 10.1126/science.11432.

[6] Xu W, Liang W, Jia X, Xu Z, Li Z, Liu Y. Maximizing sensor lifetime with the minimal service cost of a mobile charger in wireless sensor networks. IEEE Trans. Mobile Computing, 2018, 17(11): 2564-2577. DOI: 10.1109/TMC.2018.2813376.

[7] Ma Y, Liang W, Xu W. Charging utility maximization in wireless rechargeable sensor networks by charging multiple sensors simultaneously. IEEE/ACM Trans. Networking, 2018, 26(4): 1591-1604. DOI: 10.1109/TNET.2018.2841420.

[8] Wu M, Ye D, Kang J, Zhang H, Yu R. Optimal and cooperative energy replenishment in mobile rechargeable networks. In Proc. the 83rd IEEE Vehicular Technology Conference, May 2016. DOI: 10.1109/VTCSpring.2016.7504382.

[9] Liang W, Xu Z, Xu W, Shi J, Mao G, Das S K. Approximation algorithms for charging reward maximization in rechargeable sensor networks via a mobile charger. IEEE/ACM Trans. Networking, 2017, 25(5): 3161-3174. DOI: 10.1109/TNET.2017.2723605.

[10] Yang P, Wu T, Dai H, Rao X, Wang X, Wan P J, He X. MORE: Multi-node mobile charging scheduling for deadline constraints. ACM Trans. Sensor Networks, 2020, 17(1): Article No. 7. DOI: 10.1145/3410454.

[11] Zhang S, Wu J, Lu S. Collaborative mobile charging. IEEE Trans. Computers, 2014, 64(3): 654-667. DOI: 10.1109/TC.2013.2297926.

[12] Wang N, Wu J, Dai H. Bundle charging: Wireless charging energy minimization in dense wireless sensor networks. In Proc. the 39th IEEE Int. Conference on Distributed Computing Systems, Jul. 2019, pp.810-820. DOI: 10.1109/ICDCS.2019.00085.

[13] He L, Kong L, Gu Y, Pan J, Zhu T. Evaluating the on-demand mobile charging in wireless sensor networks. IEEE Trans. Mobile Computing, 2014, 14(9): 1861-1875. DOI: 10.1109/TMC.2014.2368557.

[14] Xu W, Liang W, Lin X. Approximation algorithms for min-max cycle cover problems. IEEE Trans. Computers, 2013, 64(3): 600-613. DOI: 10.1109/TC.2013.2295609.

[15] Xu W, Liang W, Jia X, Xu Z. Maximizing sensor lifetime in a rechargeable sensor network via partial energy charging on sensors. In Proc. the 13th Annual IEEE Int. Conference on Sensing, Communication, and Networking, Jun. 2016. DOI: 10.1109/SAHCN.2016.7733001.

[16] Banoth S P, Donta P K, Amgoth T. Dynamic mobile charger scheduling with partial charging strategy for WSNs using deep-Q-networks. Neural Computing and Applications, 2021, 33(22): 15267-15279. DOI: 10.1007/s00521-021-06146-9.

[17] Tseng F H, Cho H H, Lai C F. Mobile charger planning for wireless rechargeable sensor network based on ant colony optimization. In Proc. the 11th International Conference on Computer Science and Its Applications and the 14th KIPS International Conference on Ubiquitous Information Technologies and Applications, Dec. 2019, pp.387-394. DOI: 10.1007/978-981-15-9343-7.

[18] Zhang S, Qian Z, Wu J, Kong F, Lu S. Optimizing itinerary selection and charging association for mobile chargers. IEEE Trans. Mobile Computing, 2016, 16(10): 2833-2846. DOI: 10.1109/TMC.2016.2641446.

[19] Sangare F, Xiao Y, Niyato D, Han Z. Mobile charging in wireless-powered sensor networks: Optimal scheduling and experimental implementation. IEEE Trans. Vehicular Technology, 2017, 66(8): 7400-7410. DOI: 10.1109/TVT.2017.2668990.

[20] Lin C, Guo C, Dai H, Wang L, Wu G. Near optimal charging scheduling for 3-D wireless rechargeable sensor networks with energy constraints. In Proc. the 39th IEEE Int. Conference on Distributed Computing Systems, Jul. 2019, pp.624-633. DOI: 10.1109/ICDCS.2019.00068.

[21] Wang C, Li J, Ye F, Yang Y. Multi-vehicle coordination for wireless energy replenishment in sensor networks. In Proc. the 27th IEEE Int. Symp. Parallel and Distributed Processing, May 2013, pp.1101-1111. DOI: 10.1109/IPDPS.2013.22.

[22] Dai H, Wu X, Chen G, Xu L, Lin S. Minimizing the number of mobile chargers for large-scale wireless rechargeable sensor networks. Computer Communications, 2014, 46: 54-65. DOI: 10.1016/j.comcom.2014.03.001.

[23] Madhja A, Nikoletseas S, Raptis T P. Efficient, distributed coordination of multiple mobile chargers in sensor networks. In Proc. the 16th ACM Int. Conference on Modeling, Analysis Simulation of Wireless and Mobile Systems, Nov. 2013, pp.101-108. DOI: 10.1145/2507924.2507938.

[24] Galvin R. Energy consumption effects of speed and acceleration in electric vehicles: Laboratory case studies and implications for drivers and policymakers. Transportation Research Part D: Transport and Environment, 2017, 53: 234-248. DOI: 10.1016/j.trd.2017.04.020.

[1] 王怿, 刘忆雪, 朱舜佳, 高晓沨, 田臣. 无线传感器网络中能量收集中继器部署的近似算法设计[J]. 计算机科学技术学报, 2022, 37(4): 779-796.
[2] Shou-Wan Gao, Peng-Peng Chen, Xu Yang, Qiang Niu. 基于竞争协议的不可靠无线网络多传感器估计[J]. 计算机科学技术学报, 2018, 33(5): 1072-1085.
[3] Yawar Abbas Bangash, Ling-Fang Zeng, Dan Feng. MimiBS:模仿基站以在无线传感器网络中提供地址隐私保护[J]. , 2017, 32(5): 991-1007.
[4] Xiao-Long Zheng and Meng Wan. 无线传感器网络中数据分发方法综述[J]. , 2014, 29(3): 470-486.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 周笛;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] 陈世华;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[3] 冯玉琳;. Recursive Implementation of VLSI Circuits[J]. , 1986, 1(2): 72 -82 .
[4] 刘明业; 洪恩宇;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[5] 王选; 吕之敏; 汤玉海; 向阳;. A High Resolution Chinese Character Generator[J]. , 1986, 1(2): 1 -14 .
[6] C.Y.Chung; 华宣仁;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[7] 孙钟秀; 商陆军;. DMODULA:A Distributed Programming Language[J]. , 1986, 1(2): 25 -31 .
[8] 金兰; 杨元元;. A Modified Version of Chordal Ring[J]. , 1986, 1(3): 15 -32 .
[9] 潘启敬;. A Routing Algorithm with Candidate Shortest Path[J]. , 1986, 1(3): 33 -52 .
[10] 吴恩华;. A Graphics System Distributed across a Local Area Network[J]. , 1986, 1(3): 53 -64 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: