More Web Proxy on the site http://driver.im/

research-article

Public Access

Fast Charging Scheduling under the Nonlinear Superposition Model with Adjustable Phases

Authors:

Sanglu LuAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 15, Issue 4

Article No.: 48, Pages 1 - 23

https://doi.org/10.1145/3356342

Published: 20 September 2019 Publication History

All formats PDF

Abstract

Wireless energy transfer has been widely studied in recent decades, with existing works mainly focused on maximizing network lifetime, optimizing charging efficiency, and optimizing charging quality. All these works use a charging model with the linear superposition, which may not be the most accurate. We apply a nonlinear superposition model, and we consider the Fast Charging Scheduling problem (FCS): Given multiple chargers and a group of sensors, how can the chargers be optimally scheduled over the time dimension so that the total charging time is minimized and each sensor has at least energy E? We prove that FCS is NP-complete and propose a 2-approximation algorithm to solve it in one-dimensional (1D) line. In a 2D plane, we first consider a special case of FCS, where the initial phases of all chargers are the same, and propose an algorithm to solve it, which has a bound. Then we propose an algorithm to solve FCS in a general 2D plane. Unlike other algorithms, our algorithm does not need to calculate the combined energy of every possible combination of chargers in advance, which greatly reduces the complexity. Extensive simulations demonstrate that the performance of our algorithm performs almost as good as the optimal algorithm.

References

[1]

A. Alphonsa and G. Ravi. 2016. Earthquake early warning system by IOT using Wireless sensor networks. In Proceedings of the International Conference onWireless Communications, Signal Processing and Networking (WiSPNET’16). IEEE, 1201--1205.

[2]

Haipeng Dai, Yunhuai Liu, Guihai Chen, Xiaobing Wu, and Tian He. 2014. SCAPE: Safe charging with adjustable power. In Proceedings of the 2014 IEEE 34th International Conference onDistributed Computing Systems (ICDCS’14). IEEE, 439--448.

[3]

Haipeng Dai, Yunhuai Liu, Alex X. Liu, Lingtao Kong, Guihai Chen, and Tian He. 2016. Radiation constrained wireless charger placement. In Proceedings of the 35th Annual IEEE International Conference on Computer Communications (INFOCOM’16). IEEE, 1--9.

Digital Library

[4]

Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, and Mohammad R. Salavatipour. 2008. Combination can be hard: Approximability of the unique coverage problem. SIAM J. Comput. 38, 4 (2008), 1464--1483.

Digital Library

[5]

Chen Deng-Peng. 2009. Method and apparatus for optical wireless charging. US Patent 7,514,899.

[6]

Zhi Ang Eu, Winston K. G. Seah, and Hwee-Pink Tan. 2008. A study of MAC schemes for wireless sensor networks powered by ambient energy harvesting. In Proceedings of the 4th Annual International Conference on Wireless Internet. ICST, 78.

Digital Library

[7]

Xenofon Fafoutis and Nicola Dragoni. 2011. ODMAC: An on-demand MAC protocol for energy harvesting-wireless sensor networks. In Proceedings of the 8th ACM Symposium on Performance Evaluation of Wireless ad Hoc, Sensor, and Ubiquitous Networks. ACM, 49--56.

Digital Library

[8]

Arnaud Fréville. 2004. The multidimensional 0--1 knapsack problem: An overview. Eur. J. Operat. Res. 155, 1 (2004), 1--21.

[9]

Om P. Gandhi, L. Lloyd Morgan, Alvaro Augusto de Salles, Yueh-Ying Han, Ronald B. Herberman, and Devra Lee Davis. 2012. Exposure limits: The underestimation of absorbed cell phone radiation, especially in children. Electromagn. Biol. Med. 31, 1 (2012), 34--51.

[10]

Yuan Gao, Cong Wang, and Yuanyuan Yang. 2015. Joint wireless charging and sensor activity management in wireless rechargeable sensor networks. In 2015 44th International Conference on Parallel Processing (ICPP’15). IEEE, 789--798.

Digital Library

[11]

Jorge L. Garcia, Annamarie Burke, B. Juan, Charles B. Swope, and Joseph Patino. 1999. Wireless battery charging system having adaptive parameter sensing. US Patent 5,963,012.

[12]

Peng Guo, Xuefeng Liu, Shaojie Tang, and Jiannong Cao. 2016. Concurrently wireless charging sensor networks with efficient scheduling. IEEE Trans. Mobile Comput. 16, 9 (2016), 2450--2463.

Digital Library

[13]

Shibo He, Jiming Chen, Fachang Jiang, David K. Y. Yau, Guoliang Xing, and Youxian Sun. 2013. Energy provisioning in wireless rechargeable sensor networks. IEEE Trans. Mobile Comput. 12, 10 (2013), 1931--1942.

Digital Library

[14]

Jason Hsu, Sadaf Zahedi, Aman Kansal, Mani Srivastava, and Vijay Raghunathan. 2006. Adaptive duty cycling for energy harvesting systems. In Proceedings of the 2006 International Symposium on Low Power Electronics and Design. ACM, 180--185.

Digital Library

[15]

S Jegadeesan and GKD Prasanna Venkatesan. 2016. Distant biometry in cattle farm using wireless sensor networks. In Proceedings of the International Conference on Communication and Electronics Systems (ICCES’16). IEEE, 1--5.

[16]

Xiaofan Jiang, Joseph Polastre, and David Culler. 2005. Perpetual environmentally powered sensor networks. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks. IEEE Press, 65.

Digital Library

[17]

Aman Kansal, Jason Hsu, Sadaf Zahedi, and Mani B. Srivastava. 2007. Power management in energy harvesting sensor networks. ACM Trans. Embed. Comput. Syst. 6, 4 (2007), 32.

Digital Library

[18]

Zi Li, Yang Peng, Daji Qiao, and Wensheng Zhang. 2014. Joint charging and rate allocation for utility maximization in sustainable sensor networks. In Proceedings of the 2014 11th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON’14). IEEE, 459--467.

[19]

Peng Lin, Chunming Qiao, and Xin Wang. 2004. Medium access control with a dynamic duty cycle for sensor networks. In Proceedings of the 2004 IEEE Wireless Communications and Networking Conference, Vol. 3. IEEE, 1534--1539.

[20]

Zhi Ma, Jie Wu, Sheng Zhang, and Sanglu Lu. 2018a. Fast interference-aware scheduling of multiple wireless chargers. In Proceedings of the 2018 IEEE 15th International Conference on Mobile Ad Hoc and Sensor Systems (MASS’18). IEEE, 344--352.

[21]

Zhi Ma, Jie Wu, Sheng Zhang, and Sanglu Lu. 2018b. Prolonging WSN lifetime with an actual charging model. In Proceedings of the 2018 IEEE Wireless Communications and Networking Conference (WCNC’18). IEEE, 1--6.

Digital Library

[22]

Silvano Martello, David Pisinger, and Paolo Toth. 2000. New trends in exact algorithms for the 0--1 knapsack problem. Eur. J. Operat. Res. 123, 2 (2000), 325--332.

[23]

M. Yousof Naderi, Kaushik R. Chowdhury, and Stefano Basagni. 2015. Wireless sensor networks with RF energy harvesting: Energy models and analysis. In Proceedings of the 2015 IEEE Wireless Communications and Networking Conference (WCNC’15). IEEE, 1494--1499.

[24]

M. Yousof Naderi, Kaushik R. Chowdhury, Stefano Basagni, Wendi Heinzelman, Swades De, and Soumya Jana. 2014a. Experimental study of concurrent data and wireless energy transfer for sensor networks. In Proceedings of the 2014 IEEE Global Communications Conference (GLOBECOM’14). IEEE, 2543--2549.

[25]

M. Yousof Naderi, Prusayon Nintanavongsa, and Kaushik R. Chowdhury. 2014b. RF-MAC: A medium access control protocol for re-chargeable sensor networks powered by wireless energy harvesting. IEEE Trans. Wireless Commun. 13, 7 (2014), 3926--3937.

[26]

Yuki Nishikawa, Takuya Sasamura, Yoichi Ishizuka, Satoshi Sugimoto, Shohei Iwasaki, Hongyan Wang, Tomoyuki Fujishima, Takafumi Fujimoto, Koichiro Yamashita, Takahisa Suzuki, et al. 2018. Design of stable wireless sensor network for slope monitoring. In Proceedings of the 2018 IEEE Topical Conference on Wireless Sensors and Sensor Networks (WiSNet’18). IEEE, 8--11.

[27]

Dusit Niyato, Ekram Hossain, Mohammad M. Rashid, and Vijay K. Bhargava. 2007. Wireless sensor networks with energy harvesting technologies: A game-theoretic approach to optimal energy management. IEEE Wireless Commun. 14, 4 (2007), 90--96.

Digital Library

[28]

Adam B. Noel, Abderrazak Abdaoui, Tarek Elfouly, Mohamed Hossam Ahmed, Ahmed Badawy, and Mohamed S. Shehata. 2017. Structural health monitoring using wireless sensor networks: A comprehensive survey. IEEE Communications Surveys 8 Tutorials 19, 3 (2017), 1403--1423.

[29]

Yawei Pang, Zaixin Lu, Miao Pan, and Wei Wayne Li. 2014. Charging coverage for energy replenishment in wireless sensor networks. In Proceedings of the 2014 IEEE 11th International Conference on Networking, Sensing and Control (ICNSC’14). IEEE, 251--254.

[30]

Joseph A. Paradiso. 2006. Systems for human-powered mobile computing. In Proceedings of the 2006 43rd ACM/IEEE Design Automation Conference. IEEE, 645--650.

Digital Library

[31]

Chulsung Park and Pai H. Chou. 2006. Ambimax: Autonomous energy harvesting platform for multi-supply wireless sensor nodes. In 2006 3rd Annual IEEE Communications Society on Sensor and ad Hoc Communications and Networks, Vol. 1. IEEE, 168--177.

[32]

Yang Peng, Zi Li, Wensheng Zhang, and Daji Qiao. 2010. Prolonging sensor network lifetime through wireless charging. In Proceeedings of the 2010 IEEE 31st Real-time Systems Symposium (RTSS’10). IEEE, 129--139.

Digital Library

[33]

Vijay Raghunathan, Aman Kansal, Jason Hsu, Jonathan Friedman, and Mani Srivastava. 2005. Design considerations for solar energy harvesting wireless embedded systems. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks. IEEE Press, 64.

Digital Library

[34]

Fahira Sangare, Yong Xiao, Dusit Niyato, and Zhu Han. 2017. Mobile charging in wireless-powered sensor networks: Optimal scheduling and experimental implementation. IEEE Trans. Vehic. Technol. 66, 8 (2017), 7400--7410.

[35]

Winston K. G. Seah, Zhi Ang Eu, and Hwee-Pink Tan. 2009. Wireless sensor networks powered by ambient energy harvesting (WSN-HEAP)-Survey and challenges. In Proceedings of the 2009 1st International Conference on Wireless Communication, Vehicular Technology, Information Theory and Aerospace 8 Electronic Systems Technology. IEEE, 1--5.

[36]

Nathan S. Shenck and Joseph A. Paradiso. 2001. Energy scavenging with shoe-mounted piezoelectrics. IEEE Micro 3 (2001), 30--42.

Digital Library

[37]

Farhan Simjee and Pai H. Chou. 2006. Everlast: long-life, supercapacitor-operated wireless sensor node. In Proceedings of the 2006 International Symposium on Low Power Electronics and Design. ACM, 197--202.

[38]

Sujesha Sudevalayam and Purushottam Kulkarni. 2010. Energy harvesting sensor nodes: Survey and implications. IEEE Commun. Surv. Tutor. 13, 3 (2010), 443--461.

[39]

Bin Tong, Zi Li, Guiling Wang, and Wensheng Zhang. 2010. How wireless power charging technology affects sensor network deployment and routing. In Proceedings of the 2010 IEEE 30th International Conference on Distributed Computing Systems. IEEE, 438--447.

Digital Library

[40]

Wei Ye, John Heidemann, and Deborah Estrin. 2004. Medium access control with coordinated adaptive sleeping for wireless sensor networks. IEEE/ACM Trans. Netw. 12, 3 (2004), 493--506.

Digital Library

[41]

Sheng Zhang, Zhuzhong Qian, Jie Wu, Fanyu Kong, and Sanglu Lu. 2018. Wireless charger placement and power allocation for maximizing charging quality. IEEE Trans. Mobile Comput. 17, 6 (2018), 1483--1496.

[42]

Sheng Zhang, Jie Wu, and Sanglu Lu. 2015. Collaborative mobile charging. IEEE Trans. Comput. 3, 64 (2015), 654--667.

Digital Library

Cited By

Xue JWu DPeng JXu WLiu T(2025)Charger Placement With Wave InterferenceIEEE Transactions on Mobile Computing10.1109/TMC.2024.346040324:1(261-275)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TMC.2024.3460403
Liu TMa YRen MYang JPeng JYang JWu D(2024)Concurrent Charging With Wave Interference for Multiple ChargersIEEE/ACM Transactions on Networking10.1109/TNET.2024.336132132:3(2525-2538)Online publication date: Jun-2024
https://doi.org/10.1109/TNET.2024.3361321
Liu YLi DDai HMa XBoano C(2024)Understanding Concurrent Radiative Wireless Power Transfer in the IoT: Out of Myth, into RealityIEEE Wireless Communications10.1109/MWC.022.220059231:3(398-405)Online publication date: Jun-2024
https://doi.org/10.1109/MWC.022.2200592
Show More Cited By

Index Terms

Fast Charging Scheduling under the Nonlinear Superposition Model with Adjustable Phases
1. Networks
  1. Network types
    1. Wireless access networks
      1. Wireless local area networks

Recommendations

Radiation Constrained Scheduling of Wireless Charging Tasks
Mobihoc '17: Proceedings of the 18th ACM International Symposium on Mobile Ad Hoc Networking and Computing

This paper studies the problem of Radiation cOnstrained scheduling of wireless Charging tasKs (ROCK), that is, given wireless charging tasks with required charging energy and charging deadline for rechargeable devices, scheduling the power of wireless ...
Efficient design of an operation profile for wireless charging electric tram systems
Highlights
- This study introduces the innovative wireless charging electric tram system.
- A ...
Abstract
Recently, electric trams have been used as an eco-friendly mode of transport in urban areas. Of the various types of electric trams, this study deals with wireless charging electric trams. A wireless charging electric tram can draw ...
Joint optimization of collaborative interactive charging and charging lane placement for cyclic electric vehicles
Abstract
Electric vehicle (EV) usually has limited battery capacity, which has to be charged frequently during service time. Although lots of work on deployment of charging lanes can support charging in-motion EVs, it cannot guarantee that every EV can be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 15, Issue 4

November 2019

373 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/3352582

Editor:
Yunhao Liu
Tsinghua University, China

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 20 September 2019

Accepted: 01 July 2019

Revised: 01 July 2019

Received: 01 January 2019

Published in TOSN Volume 15, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
465
Total Downloads

Downloads (Last 12 months)125
Downloads (Last 6 weeks)15

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xue JWu DPeng JXu WLiu T(2025)Charger Placement With Wave InterferenceIEEE Transactions on Mobile Computing10.1109/TMC.2024.346040324:1(261-275)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TMC.2024.3460403
Liu TMa YRen MYang JPeng JYang JWu D(2024)Concurrent Charging With Wave Interference for Multiple ChargersIEEE/ACM Transactions on Networking10.1109/TNET.2024.336132132:3(2525-2538)Online publication date: Jun-2024
https://doi.org/10.1109/TNET.2024.3361321
Liu YLi DDai HMa XBoano C(2024)Understanding Concurrent Radiative Wireless Power Transfer in the IoT: Out of Myth, into RealityIEEE Wireless Communications10.1109/MWC.022.220059231:3(398-405)Online publication date: Jun-2024
https://doi.org/10.1109/MWC.022.2200592
Zhang YWang MShi HZhang J(2023)Data Cooperative Transmission and Resource Allocation Algorithm in Aviation CommunicationProceedings of the 8th International Conference on Cyber Security and Information Engineering10.1145/3617184.3630128(177-182)Online publication date: 22-Sep-2023
https://dl.acm.org/doi/10.1145/3617184.3630128
Ma YWu DRen MPeng JYang JLiu T(2023)Concurrent Charging with Wave InterferenceIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10228965(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10228965
Liang YLu YShi M(2023)Towards perpetual sensor networks via Overlapped Mobile ChargingComputer Communications10.1016/j.comcom.2023.03.020204(1-10)Online publication date: Apr-2023
https://doi.org/10.1016/j.comcom.2023.03.020
Ma CWu BPoslad SSelviah D(2022)Wi-Fi RTT Ranging Performance Characterization and Positioning System DesignIEEE Transactions on Mobile Computing10.1109/TMC.2020.301256321:2(740-756)Online publication date: 6-Jan-2022
https://dl.acm.org/doi/10.1109/TMC.2020.3012563
Lin CYang ZRen JWang LZhong WWu GZhang Q(2022)Are You Really Charging Me?2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS54860.2022.00075(724-734)Online publication date: Jul-2022
https://doi.org/10.1109/ICDCS54860.2022.00075
Liang YZhang SGe J(2022)Joint optimization of collaborative interactive charging and charging lane placement for cyclic electric vehiclesComputer Communications10.1016/j.comcom.2022.04.014190:C(166-177)Online publication date: 15-Jun-2022
https://dl.acm.org/doi/10.1016/j.comcom.2022.04.014

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents