IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.17.NO.6.JUNE 2018 1483 Wireless Charger Placement and Power Allocation for Maximizing Charging Quality Sheng Zhang Member,IEEE,Zhuzhong Qian,Member,IEEE, Jie Wu,Fellow,IEEE,Fanyu Kong,and Sanglu Lu,Member,IEEE Abstract-Wireless power transfer is a promising technology used to extend the lifetime of,and thus enhance the usability of, energy-hungry battery-powered devices.It enables energy to be wirelessly transmitted from power chargers to energy-receiving devices.Existing studies have mainly focused on maximizing network lifetime,optimizing charging efficiency,minimizing charging delay,etc.In this paper,we consider wireless charging service provision in a two-dimensional target area and focus on optimizing charging quality,where the power of each charger is adjustable.We first consider the charger Placement and Power allocation Problem with Stationary rechargeable devices(SP):Given a set of stationary devices and a set of candidate locations for placing chargers,find a charger placement and a corresponding power allocation to maximize the charging quality,subject to a power budget We prove that SP3 is NP-complete,and propose an approximation algorithm.We also show how to deal with mobile devices(MP). cost-constrained power reconfiguration(CRP),and optimization with more candidate locations.Extensive simulation results show that,the proposed algorithms perform very closely to the optimum(the gap is no more than 4.5,4.4,and 5.0 percent of OPT in SP3, MP3,and CRP,respectively),and outperforms the baseline algorithms Index Terms-Wireless power transfer,charger placement,power allocation,submodularity,approximation algorithm ◆ 1 INTRODUCTION VER the past few years,wireless portable devices monitoring [8];more than 30 types of popular phones greatly improved the quality of our lives.Due to the are beginning to embrace wireless charging [9];and even limited battery capacity of these devices,they can only vehicles [10]and unmanned planes [11]are now supporting remain operational for a limited amount of time before con- wireless charging.It is predicted that the wireless charging necting wired chargers.To extend the lifetime of these bat- market will be worth $13.78 billion by 2020 [12]. tery-powered devices,solutions from different perspectives Existing studies regarding this issue have mainly focused have been proposed,including energy harvesting [1],[21, on maximizing the lifetime of the underlying network [13] [31,energy conservation [41,[51,battery replacement [61,etc. optimizing the efficiency of charging scheduling [14], However,energy harvesting remains limited in practice energy provisioning [151,collaboration between charg- due to its partial predictability and the large size of harvest- ers [161,minimizing total charging delay [17],minimizing ing panels;energy conservation cannot compensate for maximum radiation point [18],etc. depletion;battery replacement is costly and impractical. In contrast to existing works,we consider how to effi- Wireless power transfer provides a promising alternative ciently provide wireless charging service [221.Suppose a that has attracted significant attention from both academia service provider decides to offer a wireless power charg- and industry.Kurs et al.experimentally demonstrated that ing service in a two-dimensional (2-D)target area,e.g.,a energy can be efficiently transmitted between magnetically campus or park.Based on historical data analysis and mar- resonant objects without any interconnecting conductors [7]. ket investigation,it could predict the location or trajectory This technology has led to the development of several com- information of potential customers (i.e.,devices)and then mercial products,e.g,Intel developed the wireless identi- preselect a certain number of candidate locations for plac- fication and sensing platform (WISP)for battery-free ing wireless power chargers (chargers for short in the sequel),the power of which is adjustable.Given a power budget,the provider wants to maximize its revenue, .S.Zhang,Z.Z.Qian,and S.L.Lu are with the State Key Laboratory for Novel Software Technology,Nanjing UIniversity,Nanjing 210023,China. which is proportional to the charging quality defined later E-mail:(sheng,qzz,sanglu@nju.edu.cn. in the paper.In order to maximize the charging quality,a J.Wu is with the Center for Networked Computing,Temple University, limited number of chargers with appropriate power levels Philadelphia,PA 19122.E-mail:jiewu@temple.edu. F.Y.Kong is with Ant Financial,Hangzhou,Zhejiang 310013,China. must be strategically placed at a subset of the candidate E-mail:njukongfy@gmail.com. locations. Manuscript received 2 July 2015;revised 15 Sept.2017;accepted 2 Nov.2017. In this paper,we consider the charger Placement and Date of publication 8 Nov.2017;date of current version 3 May 2018. Power allocation Problem with Stationary devices (SP): (Corresponding author:Sheng Zhang.) Given a set of stationary devices and a set of candidate locations For information on obtaining reprints of this article,please send e-mail to: reprints@ieee.org,and reference the Digital Object Identifier below. for placing chargers,how to find a charger placement and a cor- Digital Object Identifier no.10.1109TMC.2017.2771425 responding power allocation to maximize the charging quality
Wireless Charger Placement and Power Allocation for Maximizing Charging Quality Sheng Zhang , Member, IEEE, Zhuzhong Qian , Member, IEEE, Jie Wu, Fellow, IEEE, Fanyu Kong, and Sanglu Lu, Member, IEEE Abstract—Wireless power transfer is a promising technology used to extend the lifetime of, and thus enhance the usability of, energy-hungry battery-powered devices. It enables energy to be wirelessly transmitted from power chargers to energy-receiving devices. Existing studies have mainly focused on maximizing network lifetime, optimizing charging efficiency, minimizing charging delay, etc. In this paper, we consider wireless charging service provision in a two-dimensional target area and focus on optimizing charging quality, where the power of each charger is adjustable. We first consider the charger Placement and Power allocation Problem with Stationary rechargeable devices (SP3): Given a set of stationary devices and a set of candidate locations for placing chargers, find a charger placement and a corresponding power allocation to maximize the charging quality, subject to a power budget. We prove that SP3 is NP-complete, and propose an approximation algorithm. We also show how to deal with mobile devices (MP3), cost-constrained power reconfiguration (CRP), and optimization with more candidate locations. Extensive simulation results show that, the proposed algorithms perform very closely to the optimum (the gap is no more than 4.5, 4.4, and 5.0 percent of OPT in SP3, MP3, and CRP, respectively), and outperforms the baseline algorithms. Index Terms—Wireless power transfer, charger placement, power allocation, submodularity, approximation algorithm Ç 1 INTRODUCTION OVER the past few years, wireless portable devices greatly improved the quality of our lives. Due to the limited battery capacity of these devices, they can only remain operational for a limited amount of time before connecting wired chargers. To extend the lifetime of these battery-powered devices, solutions from different perspectives have been proposed, including energy harvesting [1], [2], [3], energy conservation [4], [5], battery replacement [6], etc. However, energy harvesting remains limited in practice due to its partial predictability and the large size of harvesting panels; energy conservation cannot compensate for depletion; battery replacement is costly and impractical. Wireless power transfer provides a promising alternative that has attracted significant attention from both academia and industry. Kurs et al. experimentally demonstrated that energy can be efficiently transmitted between magnetically resonant objects without any interconnecting conductors [7]. This technology has led to the development of several commercial products, e.g., Intel developed the wireless identi- fication and sensing platform (WISP) for battery-free monitoring [8]; more than 30 types of popular phones are beginning to embrace wireless charging [9]; and even vehicles [10] and unmanned planes [11] are now supporting wireless charging. It is predicted that the wireless charging market will be worth $13.78 billion by 2020 [12]. Existing studies regarding this issue have mainly focused on maximizing the lifetime of the underlying network [13], optimizing the efficiency of charging scheduling [14], energy provisioning [15], collaboration between chargers [16], minimizing total charging delay [17], minimizing maximum radiation point [18], etc. In contrast to existing works, we consider how to effi- ciently provide wireless charging service [22]. Suppose a service provider decides to offer a wireless power charging service in a two-dimensional (2-D) target area, e.g., a campus or park. Based on historical data analysis and market investigation, it could predict the location or trajectory information of potential customers (i.e., devices) and then preselect a certain number of candidate locations for placing wireless power chargers (chargers for short in the sequel), the power of which is adjustable. Given a power budget, the provider wants to maximize its revenue, which is proportional to the charging quality defined later in the paper. In order to maximize the charging quality, a limited number of chargers with appropriate power levels must be strategically placed at a subset of the candidate locations. In this paper, we consider the charger Placement and Power allocation Problem with Stationary devices (SP3): Given a set of stationary devices and a set of candidate locations for placing chargers, how to find a charger placement and a corresponding power allocation to maximize the charging quality, S. Zhang, Z.Z. Qian, and S.L. Lu are with the State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China. E-mail: {sheng, qzz, sanglu}@nju.edu.cn. J. Wu is with the Center for Networked Computing, Temple University, Philadelphia, PA 19122. E-mail: jiewu@temple.edu. F.Y. Kong is with Ant Financial, Hangzhou, Zhejiang 310013, China. E-mail: njukongfy@gmail.com. Manuscript received 2 July 2015; revised 15 Sept. 2017; accepted 2 Nov. 2017. Date of publication 8 Nov. 2017; date of current version 3 May 2018. (Corresponding author: Sheng Zhang.) For information on obtaining reprints of this article, please send e-mail to: reprints@ieee.org, and reference the Digital Object Identifier below. Digital Object Identifier no. 10.1109/TMC.2017.2771425 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 6, JUNE 2018 1483 1536-1233 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information
1484 IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.6,JUNE 2018 TABLE 1 Comparison of Near-Field WPT Standards Standards Charging Efficiency Distance Communication Power Key Supporters Technology Frequency Frequency Wireless Power Magnetic High Short 100 to 205 khz 100 to 205 khz HTC,Nokia,Sony, Consortium (Qi)[19 Induction Verizon Wireless Power Matters Magnetic High Short 277 to 357 khz 277 to 357 khz AT&T,Duracell, Alliance (Powermat)[20] Induction Starbucks Alliance for Wireless Magnetic Medium Medium 2.4 GHz 6.78 Mhz Witricity,Intel Power (WiPower)[21] Resonance subject to a power budget.We prove that SP3 is NP-complete 2 BACKGROUND AND RELATED WORK by reduction from the set cover problem [23].To design an 2.1 Wireless Power Transfer:A Primer approximation algorithm for Sp3,we first consider two special cases of SP3.The algorithms for these special cases The limited battery capacity of mobile devices has created help us design the final algorithm,namely,TCA,for Sp3, a demand for more convenient and accessible ways to with an approximation factor of where e is the base charge them.Previous solutions including harvesting of the natural logarithm,and L is the maximum power energy from environment [2],[3]and energy conserva- level. tion [4],[5]are either unstable or not able to compensate We provide three extensions of Sp3.First,we extend Sp3 for energy depletion.Wireless power transfer (WPT)is to MP3 where rechargeable devices are mobile.We leverage then proposed as a promising technology to fulfill the discrete time modeling to represent the trajectory of each needs of mobile devices. device,and then we tailor the algorithm for Sp3 to MP3 Nikola Tesla conducted the first experiment in wireless Second,mobile devices may leave or enter the target area, power transfer as early as the 1890s:an incandescent light which makes the current charger placement and power bulb was successfully powered using a coil receiver that allocation not optimal in terms of charging quality.We may was in resonance with a nearby magnifying transmitter [241. need to compute a new charger placement and power allo- Recently,Kurs et al.experimentally demonstrated that cation.However,switching from one power allocation to energy can be efficiently transmitted between magnetically another incurs some reconfiguration cost.We thus study resonant objects without any interconnecting conductors, the cost-constrained reconfiguration problem (CRP),and e.g.,powering a 60 W light bulb,which is two meters away, design an approximation algorithm of factorwhere with approximately 40 percent efficiency [71.Today,exam- B is the power budge and F is the reconfiguration cost ples of wireless charging systems include rechargeable threshold.Third,we show how to deal with the case in toothbrushes,biomedical implants,Tesla motors,etc. which chargers are allowed to be placed at any location In general,WPT techniques mainly fall into two catego- within the target area,and evaluate how the overall charg- ries,non-radiative (near-field)and radiative (far-field).In ing quality evolves as the number of candidate locations near-field WPT techniques,there are three main standards, listed in Table 1.The Qi open standard [19]was released by increases. Simulation results show that,the proposed algorithms Wireless Power Consortium in 2009.Since then,over 900 perform very closely to the optimum (the gap is no more Qi-compliant devices have become available.Powermat [20] than 4.5,4.4,and 5.0 percent of OPT in SP3,MP3,and CRP, and WiPower [21]are released in 2012 by Power Matters respectively),and outperforms the baseline algorithms. Alliance and Alliance for Wireless Power,respectively.We The contributions of this paper are three-fold: see from Table 1 that,Qi and Powermat are similar in terms of distance and frequency,while WiPower allows a medium To the best of our knowledge,we are the first to charging distance.In far-field WPT techniques,power is study the joint optimization of charger placement transferred by beams of electromagnetic radiation.These and power allocation problem.We present a for- techniques can transport energy over longer distances but mal problem statement and prove that it is NP- must be aimed at the receiver.Examples include WISP [8] complete. and WiPoT [25]. We propose an approximation algorithm,i.e.,TCA, For near-filed WPT standards,the power frequency is for Sp3.Based on TCA,we provide solutions for usually very small compared with today's WLAN or cellu- mobile devices,cost-constrained reconfiguration,lar frequencies.For far-field standards,currently,there no and more candidate locations. special frequency band for them.Hence,the time division Evaluations are conducted to confirm the effective- dulplex WPT(TDD-WPT)[26]was proposed to enable the ness and advantages of the proposed algorithms. coexistence of WPT and wireless communication.Many The rest of the paper is organized as follows.We discuss existing works [13],[271,[28]on charging scheduling also background and related work in Section 2.We introduce the assume that wireless communication and charging can Sp3 problem in Section 3.We present our solutions to Sps in coexist without any interfere.For example,energy charging Section 4.We provide several extensions in Section 5.Before is carried out in the 903-927 MHz band while communica- we conclude the paper in Section 7,we evaluate our design in tion uses the 2.4 GHz band in [13]. Section 6. For more details,please refer to [29]
subject to a power budget. We prove that SP3 is NP-complete by reduction from the set cover problem [23]. To design an approximation algorithm for SP3, we first consider two special cases of SP3. The algorithms for these special cases help us design the final algorithm, namely, TCA, for SP3, with an approximation factor of 11=e 2L , where e is the base of the natural logarithm, and L is the maximum power level. We provide three extensions of SP3. First, we extend SP3 to MP3 where rechargeable devices are mobile. We leverage discrete time modeling to represent the trajectory of each device, and then we tailor the algorithm for SP3 to MP3. Second, mobile devices may leave or enter the target area, which makes the current charger placement and power allocation not optimal in terms of charging quality. We may need to compute a new charger placement and power allocation. However, switching from one power allocation to another incurs some reconfiguration cost. We thus study the cost-constrained reconfiguration problem (CRP), and design an approximation algorithm of factor ð11=eÞF 4BL , where B is the power budge and F is the reconfiguration cost threshold. Third, we show how to deal with the case in which chargers are allowed to be placed at any location within the target area, and evaluate how the overall charging quality evolves as the number of candidate locations increases. Simulation results show that, the proposed algorithms perform very closely to the optimum (the gap is no more than 4.5, 4.4, and 5.0 percent of OPT in SP3, MP3, and CRP, respectively), and outperforms the baseline algorithms. The contributions of this paper are three-fold: To the best of our knowledge, we are the first to study the joint optimization of charger placement and power allocation problem. We present a formal problem statement and prove that it is NPcomplete. We propose an approximation algorithm, i.e., TCA, for SP3. Based on TCA, we provide solutions for mobile devices, cost-constrained reconfiguration, and more candidate locations. Evaluations are conducted to confirm the effectiveness and advantages of the proposed algorithms. The rest of the paper is organized as follows. We discuss background and related work in Section 2. We introduce the SP3 problem in Section 3. We present our solutions to SP3 in Section 4. We provide several extensions in Section 5. Before we conclude the paper in Section 7, we evaluate our design in Section 6. 2 BACKGROUND AND RELATED WORK 2.1 Wireless Power Transfer: A Primer The limited battery capacity of mobile devices has created a demand for more convenient and accessible ways to charge them. Previous solutions including harvesting energy from environment [2], [3] and energy conservation [4], [5] are either unstable or not able to compensate for energy depletion. Wireless power transfer (WPT) is then proposed as a promising technology to fulfill the needs of mobile devices. Nikola Tesla conducted the first experiment in wireless power transfer as early as the 1890s: an incandescent light bulb was successfully powered using a coil receiver that was in resonance with a nearby magnifying transmitter [24]. Recently, Kurs et al. experimentally demonstrated that energy can be efficiently transmitted between magnetically resonant objects without any interconnecting conductors, e.g., powering a 60 W light bulb, which is two meters away, with approximately 40 percent efficiency [7]. Today, examples of wireless charging systems include rechargeable toothbrushes, biomedical implants, Tesla motors, etc. In general, WPT techniques mainly fall into two categories, non-radiative (near-field) and radiative (far-field). In near-field WPT techniques, there are three main standards, listed in Table 1. The Qi open standard [19] was released by Wireless Power Consortium in 2009. Since then, over 900 Qi-compliant devices have become available. Powermat [20] and WiPower [21] are released in 2012 by Power Matters Alliance and Alliance for Wireless Power, respectively. We see from Table 1 that, Qi and Powermat are similar in terms of distance and frequency, while WiPower allows a medium charging distance. In far-field WPT techniques, power is transferred by beams of electromagnetic radiation. These techniques can transport energy over longer distances but must be aimed at the receiver. Examples include WISP [8] and WiPoT [25]. For near-filed WPT standards, the power frequency is usually very small compared with today’s WLAN or cellular frequencies. For far-field standards, currently, there no special frequency band for them. Hence, the time division dulplex WPT (TDD-WPT) [26] was proposed to enable the coexistence of WPT and wireless communication. Many existing works [13], [27], [28] on charging scheduling also assume that wireless communication and charging can coexist without any interfere. For example, energy charging is carried out in the 903-927 MHz band while communication uses the 2.4 GHz band in [13]. For more details, please refer to [29]. TABLE 1 Comparison of Near-Field WPT Standards Standards Charging Technology Efficiency Distance Communication Frequency Power Frequency Key Supporters Wireless Power Consortium (Qi) [19] Magnetic Induction High Short 100 to 205 khz 100 to 205 khz HTC, Nokia, Sony, Verizon Wireless Power Matters Alliance (Powermat) [20] Magnetic Induction High Short 277 to 357 khz 277 to 357 khz AT&T, Duracell, Starbucks Alliance for Wireless Power (WiPower) [21] Magnetic Resonance Medium Medium 2.4 GHz 6.78 Mhz Witricity, Intel 1484 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 6, JUNE 2018
ZHANG ET AL.:WIRELESS CHARGER PLACEMENT AND POWER ALLOCATION FOR MAXIMIZING CHARGING QUALITY 1485 drones [11],etc.The location (x[sil,ysi])of a device sj can be localized using existing techniques(e.g.,[381)or GPS and is reported to the wireless charging service provider via long- distance communications.Based on historical data analyses, market investigation,and urban planning,the service pro- vider could preselect a certain number of candidate locations for placing chargers.These locations are denoted by a set C={c1,c2,...,cN).The coordinate of ci is (x[ca],yfci]).With- Fig.1.Example of chargers,devices,and power levels.The maximum out causing confusion,we also use ci to denote the charger cover distance of a power level is indicated by the radius of a dashed placed at candidate location c. circle. The distance function d(,)gives the Euclidean distance between two objects (chargers or devices),e.g.,the distance 2.2 Related Work between charger ci and device sj is There is a number of studies that inspire our work.We can classify them into two broad types according to whether the d(ci,sj)=V([ci]-x[sjl)2+(ylci]-yls;l)2 (1) wireless charger is stationary or mobile. When the wireless chargers are static,a charger place- Fig.1 shows an example of chargers,devices,and power ment framework is proposed in [15]to ensure that each levels.There are four candidate locations,i.e.,C= device receives sufficient energy for continuous operation. (c,c2,ca,ca},and three devices,i.e.,S={s1,s2,83}. The joint optimization of charger placement and power allo- For wireless chargers,we assume that the power of each cation is considered in [22].How to obtain the maximum charger is adjustable [181.Each charger can be operated at L electromagnetic radiation point in a given plane is studied different power levels.Denote the power of charger c by p; in [181.The performance of multi-device simultaneous without loss of generality,we define charging is investigated in [301. For mobile wireless chargers,existing studies have consid- p=h·Pmin (2) ered various decision variables and objectives.To maximize network lifetime,charging sequence and packet routing are where h{1,2,...,L}is the power level of charger c,and optimized in [131,[311,while charger velocity is optimized pmin is the constant gap between two adjacent power levels. in [32].To maximize the ratio of the charger's vacation time Note that,this kind of discretization is for simplicity.As (i.e.,time spent at the home service station)over the cycle long as the number of allowable power levels of each char- time,travelling path and stop schedules are optimized in 141 ger is finite,the proposed algorithms are still feasible. [33].To maximize energy usage effectiveness,collaboration We assume an omnidirectional charging model which is between mobile chargers is optimized in [161,[341.To mini- widely adopted in existing studies [15],[17],[18],[32].In mize the total charging delay,stop locations and durations this model,the receiving power at rechargeable devices is are optimized in [17].NDN-based energy monitoring and determined by the transmission power of a charger and the reporting protocols are designed in [28]with a special focus distance between a device and a charger.According to the on scheduling mobile chargers for multiple concurrent emer- profiling experiments in [151,the power p(ci,sj)received by gencies.To simultaneously minimize charger travel distance device s;from charger ci can be captured by the follow and charging delay,synchronized charging sequences based model on multiple nested tours are optimized in [35].Given heterog- api enous charging frequencies of sensors,how to schedule multi- d(c,s）≤D(h) p(Ci;sj) 99+ (3) ple charging rounds to minimize total moving distance of 0 dc,s）>D(h), mobile chargers is studied in [361.Given a set of candidate charging itineraries,how to select itineraries and determine a where a and B are known constants determined by hard- corresponding charging association to minimize the amount ware of chargers and devices and the environment,and of overhead energy is considered in [37].Different from them, D(hi)is the maximum cover distance of a charger with our work jointly determines charger placement and power power level hi.We further assume that,a charger can trans- allocation to improve the charging quality,subject to a budget fer energy to multiple devices simultaneously without sig- constraint. nificantly reducing the received power at each device [301. When a device is far away from a charger,the device PROBLEM receives negligible power that cannot be rectified to useful electrical energy.The threshold of this negligible power is In this section,we first introduce the wireless charging model denoted by pBy lettingp we have (Section 3.1),then we present the problem(Section 3.2). a·hi·pmim 3.1 Wireless Charging Model D(hi) -B. (4) Pth We consider wireless charging service provision using sta- tionary chargers in this paper.The two-dimensional target That is,given constants a,B,and pth,the maximum cov- area under consideration contains a set of M stationary erage radius D(hi)of a charger ci is determined by its power rechargeable devices S={s1,s2,...,s}.These devices level hi.In Fig.1,when we place a charger ci with a power could be RFIDs [81,sensors [13],phones [9],vehicles [101,level h being 1,its maximum coverage radius is D(1),and
2.2 Related Work There is a number of studies that inspire our work. We can classify them into two broad types according to whether the wireless charger is stationary or mobile. When the wireless chargers are static, a charger placement framework is proposed in [15] to ensure that each device receives sufficient energy for continuous operation. The joint optimization of charger placement and power allocation is considered in [22]. How to obtain the maximum electromagnetic radiation point in a given plane is studied in [18]. The performance of multi-device simultaneous charging is investigated in [30]. For mobile wireless chargers, existing studies have considered various decision variables and objectives. To maximize network lifetime, charging sequence and packet routing are optimized in [13], [31], while charger velocity is optimized in [32]. To maximize the ratio of the charger’s vacation time (i.e., time spent at the home service station) over the cycle time, travelling path and stop schedules are optimized in [14], [33]. To maximize energy usage effectiveness, collaboration between mobile chargers is optimized in [16], [34]. To minimize the total charging delay, stop locations and durations are optimized in [17]. NDN-based energy monitoring and reporting protocols are designed in [28] with a special focus on scheduling mobile chargers for multiple concurrent emergencies. To simultaneously minimize charger travel distance and charging delay, synchronized charging sequences based on multiple nested tours are optimized in [35]. Given heterogenous charging frequencies of sensors, how to schedule multiple charging rounds to minimize total moving distance of mobile chargers is studied in [36]. Given a set of candidate charging itineraries, how to select itineraries and determine a corresponding charging association to minimize the amount of overhead energy is considered in [37]. Different from them, our work jointly determines charger placement and power allocation to improve the charging quality, subject to a budget constraint. 3 PROBLEM In this section, we first introduce the wireless charging model (Section 3.1), then we present the problem (Section 3.2). 3.1 Wireless Charging Model We consider wireless charging service provision using stationary chargers in this paper. The two-dimensional target area under consideration contains a set of M stationary rechargeable devices S¼fs1; s2; ... ; sMg. These devices could be RFIDs [8], sensors [13], phones [9], vehicles [10], drones [11], etc. The location ðx½sj; y½sjÞ of a device sj can be localized using existing techniques (e.g., [38]) or GPS and is reported to the wireless charging service provider via longdistance communications. Based on historical data analyses, market investigation, and urban planning, the service provider could preselect a certain number of candidate locations for placing chargers. These locations are denoted by a set C¼fc1; c2; ... ; cN g. The coordinate of ci is ðx½ci; y½ciÞ. Without causing confusion, we also use ci to denote the charger placed at candidate location ci. The distance function dð; Þ gives the Euclidean distance between two objects (chargers or devices), e.g., the distance between charger ci and device sj is dðci; sjÞ ¼ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ðx½ci x½sjÞ2 þ ðy½ci y½sjÞ2 q : (1) Fig. 1 shows an example of chargers, devices, and power levels. There are four candidate locations, i.e., C ¼ fc1; c2; c3; c4g, and three devices, i.e., S¼fs1; s2; s3g. For wireless chargers, we assume that the power of each charger is adjustable [18]. Each charger can be operated at L different power levels. Denote the power of charger c by p; without loss of generality, we define p ¼ h pmin; (2) where h 2 f1; 2; ... ; Lg is the power level of charger c, and pmin is the constant gap between two adjacent power levels. Note that, this kind of discretization is for simplicity. As long as the number of allowable power levels of each charger is finite, the proposed algorithms are still feasible. We assume an omnidirectional charging model which is widely adopted in existing studies [15], [17], [18], [32]. In this model, the receiving power at rechargeable devices is determined by the transmission power of a charger and the distance between a device and a charger. According to the profiling experiments in [15], the power pðci; sjÞ received by device sj from charger ci can be captured by the follow model pðci; sjÞ ¼ api ðdðci;sjÞþbÞ 2 dðci; sjÞ DðhiÞ 0 dðci; sjÞ > DðhiÞ; ( (3) where a and b are known constants determined by hardware of chargers and devices and the environment, and DðhiÞ is the maximum cover distance of a charger with power level hi. We further assume that, a charger can transfer energy to multiple devices simultaneously without significantly reducing the received power at each device [30]. When a device is far away from a charger, the device receives negligible power that cannot be rectified to useful electrical energy. The threshold of this negligible power is denoted by pth. By letting api ðDðhiÞþbÞ 2 ¼ pth, we have DðhiÞ ¼ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi a hi pmin pth s b: (4) That is, given constants a, b, and pth, the maximum coverage radius DðhiÞ of a charger ci is determined by its power level hi. In Fig. 1, when we place a charger c1 with a power level h1 being 1, its maximum coverage radius is Dð1Þ, and Fig. 1. Example of chargers, devices, and power levels. The maximum cover distance of a power level is indicated by the radius of a dashed circle. ZHANG ET AL.: WIRELESS CHARGER PLACEMENT AND POWER ALLOCATION FOR MAXIMIZING CHARGING QUALITY 1485
1486 IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.6,JUNE 2018 thus c cannot transfer power to s1,which is more than D(1) does there exist a sub-collection of y of size y that covers distance away from c1. all elements ofu? Denote by R a charger placement,where R is a subset of Given an instance of the decision version of the SC C,and denote by a vector H=(h,h2,...,hN)a power allo- problem,we construct an instance of the Sp3 problem as cation.As we know,the power received by one device from follows.We let L=1,i.e.,every charger can only be multiple chargers is additive [15].Therefore,given a char- operated at the fixed power pmin.For each element ej in ger placement R and a power allocation H,the total power U,we construct a device s;in Sp3.We assume that all PRH(sj)received by device sj is devices have the same maximum power consumption rate,i.e.,P=P2=...,=Pim =P.For each ViV,we pR(sj)=>p(ci,sj). (5) add a candidate location c;to Sp3.For each element e;in GER Vi,we move si into the coverage of ci.We also make sure that,as long as a device sj is within the coverage of a For example,in Fig.1,if we set R={c1,cs}and H= location ci,p(ci,sj)>P;this can be achieved by setting (2,0,2,0);we have pRH(s1)=p(c1,s1)+p(c2,s1),PR.H(s2)= Pmin to a sufficiently large value. p(c1,s2),and pRH(s3)=p(c2,s3). Combining these together,we get the following spe- 3.2 Problem Formulation cial case of the decision version of the Sp3 problem: Given a candidate location set C of size k,and a device The energy consumption rate of a device may fluctuate over time.Similar to [15],we define the average energy con- set S of size m,does there exist a charger placement R of sumption rate of a device as follows.Taking a sensor for sizeJ,such that Q((1,1,....1))z mP? It is not hard to see that the construction can be finished example,denote the energy consumption rate for sensing/ logging and sleeping by pa and p.,respectively.Assuming in polynomial time;thus,we reduce solving the NP- the cycle is T and the time duration for sensing/logging is complete SC problem to solving a special case of the Sp3 problem,implying that Sp3 is NP-hard.It is easy to verify Ta,then the average energy consumption rate of this sensor that SP3 is in NP;the theorem follows immediately. ▣ is P=aTT-T).If the total power received by the sensor is no less than P,then it can sustain its operations over time 4 SOLUTION and the over-received energy would be useless. Based on this,we now give the definition of charging 4.1 Sketch quality.Denote the average energy consumption rate of sj It is nontrivial to directly find an efficient algorithm for Sp3 by P.The charging quality ORH(sj)with respect to R and Therefore,we first look at two special cases (Sp3fu and Hon device sjis SP3fn defined below)of SP3 to reveal the problem structure and find key insights that help us design an efficient QRH(sj)=minpRH(sj),Pi}, @ approximation,namely,TCA for Sp3. Spfu.In this case,we assume that every charger can only where pr.H(sj)is the total power received by device sj. work at a fixed power level and all chargers have the same We define our objective function as follows: power level.In other words,h=h2=...=hN =h,and Definition 1 (Charging Quality).Given a charger placement PI =p2 =...=pN =h.pmin.Hence,we only need to deter- R and a power allocation H,the charging quality,denoted as mine charger placement and do not need to determine Q(R,H),is defined as the sum of the charging qualities of over power allocation:the objective function Q(R,H)degener- all devices with respect to R and H,i.e.,Q(R,H)= ates into Q(R).For convenience,denote the power of each ∑1QRHs charger by p in SP fu.Formally, The Sp3 problem studied in this paper is: Problem 2(SP3 with fixed and uniform power levels, SP3fu).Given a set C of candidate locations,a set S of devices, Problem 1 (Charger Placement and Power Allocation a power budget B,and a fixed power p,Sp is to find a charger Problem with Stationary Devices,SP3).Given a set C of placement R to maximize O(R),subject to the budget candidate locations,a set S of devices,and a power budget B, Sp3 is to find a charger placement R and a porer allocation H constraint,ie,lR≤Lg. to maximize Q(R,H),subject to the power budget constraint, For SpSfu,we design an approximation algorithm shown ie,∑c,eRh≤B. in Algorithm 1 based on the good properties of Q(R). Spfn.In this case,we assume that every charger can only By reducing the NP-complete Set Cover problem(SC)[23] work at a fixed power level,but different chargers work at to Sp3,we have the following theorem. different power levels.Similarly,we have Theorem 1.Sp3 is NP-complete. Problem 3(SP3 with fixed and non-uniform power Proof.The decision version of the SC problem is as follows: levels,SP3fn).Given a set C of candidate locations,a set S of Given a universeu=fe1,e2,...,em}of m elements and an devices,a power budget B,and a fixed power level hi for each integer y,a collection of subsets of u,V=V1,V2,....V}, location ci,Sp3 is to find a charger placement R to maximize Q(R),subject to the budget constraint,i.e.p B. 1.If the sensor is equipped with a battery of capacity w,for simplic- 器里no器e toupby the For Spfn,we design an approximation algorithm shown in Algorithm 2 based on the insights acquired from solving sor is larger than P,the over-received energy is also useless. the first special case SPfu
thus c1 cannot transfer power to s1, which is more than Dð1Þ distance away from c1. Denote by R a charger placement, where R is a subset of C, and denote by a vector H ¼ ðh1; h2; ... ; hN Þ a power allocation. As we know, the power received by one device from multiple chargers is additive [15]. Therefore, given a charger placement R and a power allocation H, the total power pR;HðsjÞ received by device sj is pR;HðsjÞ ¼ X ci2R pðci; sjÞ: (5) For example, in Fig. 1, if we set R¼fc1; c3g and H ¼ ð2; 0; 2; 0Þ; we have pR;Hðs1Þ ¼ pðc1; s1Þ þ pðc2; s1Þ, pR;Hðs2Þ ¼ pðc1; s2Þ, and pR;Hðs3Þ ¼ pðc2; s3Þ. 3.2 Problem Formulation The energy consumption rate of a device may fluctuate over time. Similar to [15], we define the average energy consumption rate of a device as follows. Taking a sensor for example, denote the energy consumption rate for sensing/ logging and sleeping by pa and ps, respectively. Assuming the cycle is T and the time duration for sensing/logging is Ta, then the average energy consumption rate of this sensor is P ¼ paTaþpsðTTaÞ T . If the total power received by the sensor is no less than P, then it can sustain its operations over time and the over-received energy would be useless.1 Based on this, we now give the definition of charging quality. Denote the average energy consumption rate of sj by Pj. The charging quality QR;HðsjÞ with respect to R and H on device sj is QR;HðsjÞ ¼ minfpR;HðsjÞ; Pjg; (6) where pR;HðsjÞ is the total power received by device sj. We define our objective function as follows: Definition 1 (Charging Quality). Given a charger placement R and a power allocation H, the charging quality, denoted as QðR; HÞ, is defined as the sum of the charging qualities of over all devices with respect to P R and H, i.e., QðR; HÞ ¼ M j¼1 QR;HðsjÞ. The SP3 problem studied in this paper is: Problem 1 (Charger Placement and Power Allocation Problem with Stationary Devices, SP3). Given a set C of candidate locations, a set S of devices, and a power budget B, SP3 is to find a charger placement R and a power allocation H to maximize QðR; HÞ, subject to the power budget constraint, i.e., P ci2R pi B. By reducing the NP-complete Set Cover problem (SC) [23] to SP3, we have the following theorem. Theorem 1. SP3 is NP-complete. Proof. The decision version of the SC problem is as follows: Given a universe U¼fe1; e2; ... ; emg of m elements and an integer y, a collection of subsets of U, V ¼ fV1; V2; ... ; Vkg, does there exist a sub-collection of V of size y that covers all elements of U? Given an instance of the decision version of the SC problem, we construct an instance of the SP3 problem as follows. We let L ¼ 1, i.e., every charger can only be operated at the fixed power pmin. For each element ej in U, we construct a device sj in SP3. We assume that all devices have the same maximum power consumption rate, i.e., P1 ¼ P2 ¼ ... ; ¼ Pm ¼ P. For each Vi 2 V, we add a candidate location ci to SP3. For each element ej in Vi, we move sj into the coverage of ci. We also make sure that, as long as a device sj is within the coverage of a location ci, pðci; sjÞ P; this can be achieved by setting pmin to a sufficiently large value. Combining these together, we get the following special case of the decision version of the SP3 problem: Given a candidate location set C of size k, and a device set S of size m, does there exist a charger placement R of size b B pminc, such that QðR;ð1; 1; ... ; 1ÞÞ mP? It is not hard to see that the construction can be finished in polynomial time; thus, we reduce solving the NPcomplete SC problem to solving a special case of the SP3 problem, implying that SP3 is NP-hard. It is easy to verify that SP3 is in NP; the theorem follows immediately. tu 4 SOLUTION 4.1 Sketch It is nontrivial to directly find an efficient algorithm for SP3. Therefore, we first look at two special cases (SP3fu and SP3fn defined below) of SP3 to reveal the problem structure and find key insights that help us design an efficient approximation, namely, TCA for SP3. SP3fu. In this case, we assume that every charger can only work at a fixed power level and all chargers have the same power level. In other words, h1 ¼ h2 ¼ ... ¼ hN ¼ h, and p1 ¼ p2 ¼ ... ¼ pN ¼ h pmin. Hence, we only need to determine charger placement and do not need to determine power allocation: the objective function QðR; HÞ degenerates into QðRÞ. For convenience, denote the power of each charger by p in SP3fu. Formally, Problem 2 (SP3 with fixed and uniform power levels, SP3fu). Given a set C of candidate locations, a set S of devices, a power budget B, and a fixed power p, SP3 is to find a charger placement R to maximize QðRÞ, subject to the budget constraint, i.e., jRj bB pc. For SP3fu, we design an approximation algorithm shown in Algorithm 1 based on the good properties of QðRÞ. SP3fn. In this case, we assume that every charger can only work at a fixed power level, but different chargers work at different power levels. Similarly, we have Problem 3 (SP3 with fixed and non-uniform power levels, SP3fn). Given a set C of candidate locations, a set S of devices, a power budget B, and a fixed power level hi for each location ci, SP3 is to find a charger placement R to maximize QðRÞ, subject to the budget constraint, i.e., P ci2R pi B. For SP3fn, we design an approximation algorithm shown in Algorithm 2 based on the insights acquired from solving the first special case SP3fu. 1. If the sensor is equipped with a battery of capacity w, for simplicity, we can define the average energy consumption rate as P ¼ paTaþpsðTTaÞþw T . In this case, if the total power received by the sensor is larger than P, the over-received energy is also useless. 1486 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 6, JUNE 2018
ZHANG ET AL.:WIRELESS CHARGER PLACEMENT AND POWER ALLOCATION FOR MAXIMIZING CHARGING QUALITY 1487 Finally,we design TCA for Sp3 based on the insights If p(c,sj)<Pi-pR'(sj),then acquired from solving the second special case SP3fn. Q(Rute))(sj)-QR(sj)=p(c.sj)=Q(R'uep)(sj)-QR(sj). 4.2 Details 4.2.1 Solving SPfu If Pj-PR'(sj)<p(c,sj)<Pj-PR(sj),then To solve Sp3fu,we first prove that the objective function Q(RUe)(sj)-QR(sj)=p(c,sj) Q(R)of Sp3fu has three tractable properties:nonnegativity, monotonicity,and submodularity,which enable us to pro- >Pj-PR(sj)=Q(R'uen)(sj)-QR'(sj). pose a(1-1/e)-approximation algorithm. If乃-pR(s)≤p(c,s),then Definition 2 (Nonnegativity,Monotonicity,and Sub- modularity).Given a non-empty finite set u,and a function Q(RUIe)(sj)-QR(sj)=P;-pR(sj) f defined on the power set u ofu with real values,f is called ≥乃-Pr(s)=Q(r'uG(s)-QR(s: nonnegative if The theorem follows immediately. ▣ f(A)≥0，HAC These properties enable us to propose an approximation f is called monotone if algorithm of factor (1-1/e)shown in Algorithm 1 [39], f(A)≤f(A),A≤A'C [401.Since power levels are fixed in SPfu,we only have to determine the charger placement R.In Algorithm 1,R is f is called submodular if initialized to 0;in each iteration,we add the location that maximizes the marginal gain of the objective function into f(AULe))-f(A)>f(A'ule))-f(A'),VACA'cu. R.Here,the marginal gain means the additional charging quality from selecting an additional location,i.e.,in each We have the following theorem: iteration,we select the location cEC\R that maximize the Theorem 2.Q(R)in spfu is nonnegative,monotone,and following formula: submodular. Q(RUIC])-Q(R). (70 Proof.Q(R)is nonnegative according to Definition 1.For There are at most N iterations in Algorithm 1;in each all R C R'CC,we have iteration,we need to check at most N locations to find the location that maximizes the marginal gain.It takes O(MN) time to compute Q(R),thus,the time complexity of Algo- rithm 1 is O(MN3). implying that,Q(R)is monotone.For all R CR'CC,we need to prove Algorithm 1.Greedy Algorithm(GA)for SP3fu Input:C,S,B,and the uniform power levelp Q(RUIc})-Q(R)>Q(R'U(C})-Q(R'). Output:R 1:R-0 It is sufficient to show that for any sje S,we have 2:whileR<do 3: Qrue(s)-Qr(s）≥Qrue(s)-QR(s) select ccR that maximizes Q(RUfc})-Q(R) 4: R-RUfc} Based on Egs.(5)and(6),we prove the above inequality 5:end while 6:return R in three non-overlapping cases: ·B≤pR(s:since pe(s)≥Pr(s,we have 4.2.2 Solving SPfn Q(Rue(s）-QR(s)=0=QRue(s）-QR(s We now study the case where the power levels of chargers ·pR(s)<乃<pr(s:in this case,QRuc(s)- are fixed but not necessarily the same.To solve SP3fn,an intui- Qg'(sj)=0,and we have tive method is to use the same greedy idea as in Algorithm 1. However,we show in Fig.2a that,this method may perform Q(RUe)(sj)-QR(sj) very poorly.In Fig.2a,there are N=L+1 candidate =minPj-pR(sj),P(RUe))(sj)-PR(sj)} locations and M=L+1 devices;h h2 =...hN-1=1, min{Pj-PR(sj),p(c,sj)} and hN=L;the radii of dashed circles indicate the maximum coverage distance of each charger;p(c1,s1)= ≥0=Que(s)-QR(s》 p(c2,s2)=...=p(CN-1,SN-1)=p(CN,SN)-E,where e satis- fies 0<e<p(cN,SN).Given a power budget B=L.Pmin, ·prr(sj)≤P:in this case,we have using Eq.(7),as cN leads to the maximum marginal gain, cN would be picked and achieves a charging quality of Q(RUKen(sj)-QR(sj)=min{Pj-PR(sj),p(c,sj)}, p(cI,s1)+e.However,the optimal solution that picks ci, Q(R'ue)(sj)-QR'(sj)=min{Pj-PR'(sj),p(c,sj)} c2,...,and cN-1 achieves a charging quality of L.p(c1,s1). When e is approaching zero,this method could only achieve
Finally, we design TCA for SP3 based on the insights acquired from solving the second special case SP3fn. 4.2 Details 4.2.1 Solving SP3fu To solve SP3fu, we first prove that the objective function QðRÞ of SP3fu has three tractable properties: nonnegativity, monotonicity, and submodularity, which enable us to propose a ð1 1=eÞ-approximation algorithm. Definition 2 (Nonnegativity, Monotonicity, and Submodularity). Given a non-empty finite set U, and a function f defined on the power set 2U of U with real values, f is called nonnegative if fðAÞ 0; 8A U; f is called monotone if fðAÞ fðA0 Þ; 8A A0 U; f is called submodular if fðA [ fegÞ fðAÞ fðA0 [ fegÞ fðA0 Þ; 8A A0 U: We have the following theorem: Theorem 2. QðRÞ in SP3fu is nonnegative, monotone, and submodular. Proof. QðRÞ is nonnegative according to Definition 1. For all RR0 C, we have QðRÞ ¼ X M j¼1 QRðsjÞ X M j¼1 QR0ðsjÞ ¼ QðR0 Þ; implying that, QðRÞ is monotone. For all RR0 C, we need to prove QðR [ fcgÞ QðRÞ QðR0 [ fcgÞ QðR0 Þ: It is sufficient to show that for any sj 2 S, we have QðR[fcgÞðsjÞ QRðsjÞ QðR0 [fcgÞðsjÞ QR0ðsjÞ: Based on Eqs. (5) and (6), we prove the above inequality in three non-overlapping cases: Pj pRðsjÞ: since pR0ðsjÞ pRðsjÞ, we have QðR[fcgÞðsjÞ QRðsjÞ ¼ 0 ¼ QðR0 [fcgÞðsjÞ QR0ðsjÞ: pRðsjÞ < Pj < pR0ðsjÞ: in this case, QðR0 [fcgÞðsjÞ QR0ðsjÞ ¼ 0, and we have QðR[fcgÞðsjÞ QRðsjÞ ¼ minfPj pRðsjÞ; pðR[fcgÞðsjÞ pRðsjÞg ¼ minfPj pRðsjÞ; pðc; sjÞg 0 ¼ QðR0 [fcgÞðsjÞ QR0ðsjÞ: pR0ðsjÞ Pj: in this case, we have QðR[fcgÞðsjÞ QRðsjÞ ¼ minfPj pRðsjÞ; pðc; sjÞg; QðR0 [fcgÞðsjÞ QR0ðsjÞ ¼ minfPj pR0ðsjÞ; pðc; sjÞg: If pðc; sjÞ Pj pR0ðsjÞ, then QðR[fcgÞðsjÞ QRðsjÞ ¼ pðc; sjÞ ¼ QðR0 [fcgÞðsjÞ QR0ðsjÞ: If Pj pR0ðsjÞ < pðc; sjÞ < Pj pRðsjÞ, then QðR[fcgÞðsjÞ QRðsjÞ ¼ pðc; sjÞ > Pj pR0ðsjÞ ¼ QðR0 [fcgÞðsjÞ QR0ðsjÞ: If Pj pRðsjÞ pðc; sjÞ, then QðR[fcgÞðsjÞ QRðsjÞ ¼ Pj pRðsjÞ Pj pR0ðsjÞ ¼ QðR0 [fcgÞðsjÞ QR0ðsjÞ: The theorem follows immediately. tu These properties enable us to propose an approximation algorithm of factor ð1 1=eÞ shown in Algorithm 1 [39], [40]. Since power levels are fixed in SP3fu, we only have to determine the charger placement R. In Algorithm 1, R is initialized to ;; in each iteration, we add the location that maximizes the marginal gain of the objective function into R. Here, the marginal gain means the additional charging quality from selecting an additional location, i.e., in each iteration, we select the location c 2CnR that maximize the following formula: QðR [ fcgÞ QðRÞ: (7) There are at most N iterations in Algorithm 1; in each iteration, we need to check at most N locations to find the location that maximizes the marginal gain. It takes OðMNÞ time to compute QðRÞ, thus, the time complexity of Algorithm 1 is OðMN3Þ. Algorithm 1. Greedy Algorithm (GA) for SP3fu Input: C, S, B, and the uniform power level p Output: R 1: R ; 2: while jRj < bB pc do 3: select c 2CnR that maximizes QðR [ fcgÞ QðRÞ 4: R R[fcg 5: end while 6: return R 4.2.2 Solving SP3fn We now study the case where the power levels of chargers are fixed but not necessarily the same. To solve SP3fn, an intuitive method is to use the same greedy idea as in Algorithm 1. However, we show in Fig. 2a that, this method may perform very poorly. In Fig. 2a, there are N ¼ L þ 1 candidate locations and M ¼ L þ 1 devices; h1 ¼ h2 ¼¼ hN1 ¼ 1, and hN ¼ L; the radii of dashed circles indicate the maximum coverage distance of each charger; pðc1; s1Þ ¼ pðc2; s2Þ ¼ ... ¼ pðcN1; sN1Þ ¼ pðcN ; sN Þ , where satis- fies 0 <<pðcN ; sN Þ. Given a power budget B ¼ L pmin, using Eq. (7), as cN leads to the maximum marginal gain, cN would be picked and achieves a charging quality of pðc1; s1Þ þ . However, the optimal solution that picks c1, c2; ... ; and cN1 achieves a charging quality of L pðc1; s1Þ. When is approaching zero, this method could only achieve ZHANG ET AL.: WIRELESS CHARGER PLACEMENT AND POWER ALLOCATION FOR MAXIMIZING CHARGING QUALITY 1487