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)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Þ ¼ 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
1488 IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.6,JUNE 2018 名 8 ●S2 SN SN-1, 时 S3 (a)With Eq.(7),charger cn would be picked,while the optimal (b)With Eg.(8),charger c would be picked; solution is to pick c1,c2,...,and cN-1. while the optimal solution is to pick c2. Fig.2.Directly applying Eq.(7)or Eq.(8)to SPSfn may result in a very poor performance. approximately 1/L of the charging quality returned by the Problem 4 (VSP3).For each candidate location ci,we are given optimal solution. L chargers with exactly different power levels,i.e.,the power Another intuitive method is that,as long as there is levels of these chargers are 1,2,...,and L.We use (ci,hk)to remaining power budget,in each iteration,we add the loca- denote the charger of a constant power level hy that can only be tion crEC\R that maximizes the ratio of the marginal gain placed at ci.Note that there are,in total,N.L chargers.Given to the power cost,i.e., a power budget B,how do we find a charger placement that maximizes the objective function defined below? Q(RUIGz})-Q(R) C红← arg max (8) caeR,∑4 eRute:h≤B Pr Algorithm 3.Two-Choice-Based Alg.(TCA)for SP3 Input:C,S,and B However,we show in Fig.2b that,this method may also Output:R and H perform poorly.In Fig.2b,there are 2 candidate locations 1:-Cx H //the Cartesian product and M=L+1 devices;h=1,and h2=L;p(c1,s1)= 2:21←-0，H1←-0 p(c2,s2)...=p(c2,sM-1)=p(c2,sM)+e,where e satisfies 3:while B≥min()e\zp(hg)+∑h)eP(he)do 0D(hk) 4.2.3 Solving SP Given a charger placement 3',the total power pz(sj) received by device sj is pa(sj)(cisj h).The In this section,we present an approximation algorithm,i.e., charging quality of g'on s;is TCA in Algorithm 3 for the general SP problem. Before formally explaining TCA,we first consider the fol- Qzr(s)=min{pz(s,P乃} (10) lowing variant of SP3,where we can place multiple chargers at one location: The objective function is (=)
approximately 1=L of the charging quality returned by the optimal solution. Another intuitive method is that, as long as there is remaining power budget, in each iteration, we add the location cx 2CnR that maximizes the ratio of the marginal gain to the power cost, i.e., cx arg max cx2CnR; P ci2R[fcxg piB QðR [ fcxgÞ QðRÞ px : (8) However, we show in Fig. 2b that, this method may also perform poorly. In Fig. 2b, there are 2 candidate locations and M ¼ L þ 1 devices; h1 ¼ 1, and h2 ¼ L; pðc1; s1Þ ¼ pðc2; s2Þ¼ pðc2; sM1Þ ¼ pðc2; sMÞ þ , where satisfies 0 DðhkÞ: ( (9) Given a charger placement Z0 , the total power pZ0ðsjÞ received by device sj is pZ0ðsjÞ ¼ P ðci;hkÞ2Z0 pðci; sj; hkÞ. The charging quality of Z0 on sj is QZ0ðsjÞ ¼ minfpZ0ðsjÞ; Pjg: (10) The objective function is QðZ0 Þ ¼ PM j¼1 QZ0ðsjÞ. Fig. 2. Directly applying Eq. (7) or Eq. (8) to SP3fn may result in a very poor performance. 1488 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 6, JUNE 2018
ZHANG ET AL.:WIRELESS CHARGER PLACEMENT AND POWER ALLOCATION FOR MAXIMIZING CHARGING QUALITY 1489 The main idea of TCA is as follows.We first use the two greedy heuristics (i.e.,Eqs.(7)and (8))to solve VSP3,and get two results Z1 and 22,respectively.We then invoke the RDU sub-procedure to transform Z1 and 22 into(R1,H1) and (R2,H2),respectively.We choose the better one of them as the final solution to Sp3. The RDU sub-procedure (Algorithm 4)works as fol- lows (take Z1 for example):Note that there may be more than one charger placed at a candidate location in Z1,we thus retain only one charger for each location in transforming Z Fig.3.There are three candidate locations and two devices.The radii of into R and H,which implies that there may be some unused dashed circles show the maximum cover distances of four different budget for Ri and H1.For each location ci,we set Hlcil to power levels. be the maximum value of hk among all (ci,h)EZ1,i.e., Hi(ci]max(eh)ez hk (line 6 of Algorithm 3).For each Proof.Denote by (R*,H*)the optimal solution to SP3,and location ci,if Hci]>0,we add it into Ri,which is by (R,H)the solution returned by TCA.We want to equivalent to R1={cil(ci,h)EZ1}(lines 2-4 of Algo- prove that, rithm 4).In the following,we try to improve R and H Q(R,H)、1-1/e by utilizing the remaining budget(B-B)(lines 5-8 of Q(R,H) 2L Algorithm 4).In each iteration,we allocate a fixed power Pmin to the location that maximizes the marginal objective Let g*be the optimal solution to VSP3,and let gain,2 that is,we increase the power level of location ci by 1,if its power level is less than L and it maximizes 'arg max Q(Z') z'e{21,22} Q(RU{c},H+1)-Q(R,H). Time Complexity.There are at most NL iterations in where 31 and 32 are the solutions generated by lines 3-7 each while-loop of Algorithm 3;in each iteration,at most and 9-14 of TCA,respectively.According to the results in NL pairs of c and h are checked,and computing Q(3) Section 4.2.2,we know needs O(MNL)time.Therefore,each while-loop takes O(MN3L3)time.For Algorithm 4,lines 2-4 takes O(N) Q(2)≥(1-1/e)/2Q(z*). time;there are B-B iterations in the while-loop;in Notice that,if we restrict the number of chargers that each iteration,at most N locations are checked,and each can be placed at each candidate location to one,the VSP3 check takes O(MN)time.Therefore,the time comple- problem is equivalent to Sp3,i.e.,Sp3 is a special case of xity of Algorithm 4 is O(N+(B-B)MN2).Observ- ing B-B0 do 3 R-RUfcih,B-B'+p(H[ci]) Combining them together,we have 4:end for 5:while B-B'≥Pmin do Q(R,H)=max{Q(Ri,Hi),Q(R2,H2)} 6: select ci that maximizes Q(RU(ci},H+Ii)-Q(R,H) subject to Hc+1≤Z ≥maxQ(3hQ(2,}-Q(2 7: R-R U{ci),Hlci]-H[ci]+1,B-B'+pmin 8:end while ≥q2)≥@n 9:return(R,H) The theorem follows immediately. Approximation Ratio.Theorem 3 gives the performance guarantee of TCA.Later,we will see in the simulations that, 4.3 Example of Running TCA the gap between TCA and the optimal solution is and 2.0 We use the example shown in Fig.3 to explain how TCA percent on average,and 4.5 percent at most. works.There are 3 candidate locations and 2 devices.Fol- Theorem 3.TCA is a factorapproximation algorithm lowing existing works [15],[171,[181,we assume that, for Sp3. Pmin =50,L=4,Pth 0.01,a =0.64,and B =30.Given these parameters,.we have D(1)≈27，D(2)=50,D(3)≈68， and D(4)83.The radii of dashed circles show the maxi- 2.We can further improve lines 5-8 of Algorithm 4 by applying both mum cover distances of four different power levels.We can Egs.(7)and (8),and choosing the better one.However,the improve- compute that,d(c1,s1)=20,d(c1;s2)=70,d(c2:s2)=40, ment would be little.We choose the current form for brevity. and d(c3,s2)=60.The average power consumption rate of
The main idea of TCA is as follows. We first use the two greedy heuristics (i.e., Eqs. (7) and (8)) to solve VSP3, and get two results Z1 and Z2, respectively. We then invoke the RDU sub-procedure to transform Z1 and Z2 into ðR1; H1Þ and ðR2; H2Þ, respectively. We choose the better one of them as the final solution to SP3. The RDU sub-procedure (Algorithm 4) works as follows (take Z1 for example): Note that there may be more than one charger placed at a candidate location in Z1, we thus retain only one charger for each location in transforming Z1 into R1 and H1, which implies that there may be some unused budget for R1 and H1. For each location ci, we set H1½ci to be the maximum value of hk among all ðci; hkÞ2Z1, i.e., H1½ci ¼ maxðci;hkÞ2Z1hk (line 6 of Algorithm 3). For each location ci, if H1½ci > 0, we add it into R1, which is equivalent to R1 ¼ fcijðci; hkÞ2Z1g (lines 2-4 of Algorithm 4). In the following, we try to improve R1 and H1 by utilizing the remaining budget ðB B0 1Þ (lines 5-8 of Algorithm 4). In each iteration, we allocate a fixed power pmin to the location that maximizes the marginal objective gain,2 that is, we increase the power level of location ci by 1, if its power level is less than L and it maximizes QðR [ fcig; H þ IiÞ QðR; HÞ. Time Complexity. There are at most NL iterations in each while-loop of Algorithm 3; in each iteration, at most NL pairs of c and h are checked, and computing QðZÞ needs OðMNLÞ time. Therefore, each while-loop takes OðMN3L3Þ time. For Algorithm 4, lines 2-4 takes OðNÞ time; there are B B0 iterations in the while-loop; in each iteration, at most N locations are checked, and each check takes OðMNÞ time. Therefore, the time complexity of Algorithm 4 is OðN þ ðB B0 ÞMN2Þ. Observing B B0 0 do 3: R R[fcig, B0 B0 þ pðH½ciÞ 4: end for 5: while B B0 pmin do 6: select ci that maximizes QðR [ fcig; H þ IiÞ QðR; HÞ subject to H½ci þ 1 L 7: R R[fcig, H½ci H½ci þ 1, B0 B0 þ pmin 8: end while 9: return ðR; HÞ Approximation Ratio. Theorem 3 gives the performance guarantee of TCA. Later, we will see in the simulations that, the gap between TCA and the optimal solution is and 2.0 percent on average, and 4.5 percent at most. Theorem 3. TCA is a factor 11=e 2L approximation algorithm for SP3. Proof. Denote by ðR ; H Þ the optimal solution to SP3, and by ðR; HÞ the solution returned by TCA. We want to prove that, QðR; HÞ QðR ; H Þ 1 1=e 2L : Let Z be the optimal solution to VSP3, and let Z0 ¼ arg max Z0 2fZ1;Z2g QðZ0 Þ where Z1 and Z2 are the solutions generated by lines 3-7 and 9-14 of TCA, respectively. According to the results in Section 4.2.2, we know QðZ0 Þð1 1=eÞ=2QðZ Þ: Notice that, if we restrict the number of chargers that can be placed at each candidate location to one, the VSP3 problem is equivalent to SP3, i.e., SP3 is a special case of VSP3. From this viewpoint, we have QðZ Þ QðC ; H Þ: In Z1 (resp. Z2), we can place at most L chargers at one location. When transforming Z1 (resp. Z2) into R1 and H1 (resp. R2 and H2), for each location, we retain the charger that has the largest power level, if any. Therefore, we have QðR1; H1Þ QðZ1Þ=L; and QðR2; H2Þ QðZ2Þ=L: Combining them together, we have QðR; HÞ ¼ maxfQðR1; H1Þ; QðR2; H2Þg maxfQðZ1Þ; QðZ2Þg L ¼ QðZ0 Þ L 1 1=e 2L QðZ Þ 1 1=e 2L QðR ; H Þ: The theorem follows immediately. tu 4.3 Example of Running TCA We use the example shown in Fig. 3 to explain how TCA works. There are 3 candidate locations and 2 devices. Following existing works [15], [17], [18], we assume that, pmin ¼ 50, L ¼ 4, pth ¼ 0:01, a ¼ 0:64, and b ¼ 30. Given these parameters, we have Dð1Þ 27, Dð2Þ ¼ 50, Dð3Þ 68, and Dð4Þ 83. The radii of dashed circles show the maximum cover distances of four different power levels. We can compute that, dðc1; s1Þ ¼ 20, dðc1; s2Þ ¼ 70, dðc2; s2Þ ¼ 40, and dðc3; s2Þ ¼ 60. The average power consumption rate of Fig. 3. There are three candidate locations and two devices. The radii of dashed circles show the maximum cover distances of four different power levels. 2. We can further improve lines 5-8 of Algorithm 4 by applying both Eqs. (7) and (8), and choosing the better one. However, the improvement would be little. We choose the current form for brevity. ZHANG ET AL.: WIRELESS CHARGER PLACEMENT AND POWER ALLOCATION FOR MAXIMIZING CHARGING QUALITY 1489
1490 IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.6,JUNE 2018 Denote by E the circle radius in the figure,and obvi- (xy ously,E can be used to control modeling precision.The tra- ANd jectory of sj is represented by a set of tuples,i.e.(). ⊙. The kth tuple (,means that,s;stays with the circle, A whose center and radius are(,)and E,respectively,for .(xy) a time duration of. We now show how to obtain these tuples.Denote by A the starting point of the trajectory.The distance between A and (,y)is E,thus,we have the first circle.Denote by A2 Fig.4.The trajectory of device s;is represented by a series of tuples.The the intersection point of the trajectory and the first circle. kth tuple()indicates that,s stays within the circle,whose center The distance between A2 and (j,y)is also E,thus,we and radius are()and E,respectively,for a time duration of have the second circle;and so on.is set to be the time duration when sj is with its kth circle. s1 or s2 is 0.07,i.e.,P=P2=0.07.Given a power budget Given a placement R and an allocation H,the total power B=500,we now check how TCA works. PRH(sj,)received by a device sj at its kth position is In lines 2-7 of Algorithm 3,we first check which(c,h) denoted by gives the maximal marginal objective gain.For ci,we have Q({(c,1)})=0.0128,Q({(a,2)})=0.0256,Q({(9,3)})= pRH(s,)=∑pc,s) (11) 0.0384,and Q({(c1,4)})=0.064;for c2 and c3,we can com- GiER pute these values in a similar way.Thus,in the first iteration of lines 2-8,we add (c1,4)into 31.It is worth noting that,in Similarly,the charging quality of R and H on sj at its kth the second iteration,Q({(c1,4){(c1,2)))-Q((c1,4)})= position is denoted by min{p(g1,s1,2),-p(g,s1,4)}=0.0188(see Eqs.(9) and (10)).The reader can check that,Z1 would be {(c1,4), QRH(sj,)minpr(sj,),P. (12) (c2,4),(C,2)}. Note that,for each location,we retain only one charger And the charging quality of R and H on s;is defined as the which has the largest power level in Z1.Then we get weighted sum of Q(sj,),i.e., R1 ={c1,c2}and H1=(4,4,0).In lines 5-8 of Algorithm 4, we try to utilize the remaining budget 500-(4+4)x QR.H(sj)= ∑tQRH(s,) (13) 50=100.We find that,the distance between cs and s2 is larger than D(2),thus,there is no need to allocate the remain- ing 100 units of power to ca.Finally we have R=fc1,c2} With the above discrete time-based modeling,we can andH=(4,4,0). formulate a problem similar to Sp3.Fortunately,MP3 also Similarly,after running lines 9-14,we would have has the aforementioned tractable properties as Sp3,based 2={(c1,4),(c1:1),(c2,2),(c2,3)).Through removing dupli- on which we can tailor Algorithm 3 to MP3 and yield an cations,we have R2={c1,c2}and H2 =(4,3,0).After utiliz- approximation algorithm of the same factor as TCA.Note ing the remaining budget,we also have R2=[cI,c2}and that,the discrete time model could be arbitrarily precise H2=(4.4,0). when E is sufficiently small. The final solution is R={c1,c2}and H=(4,4,0),yield- ing an objective of Q(R,H)=0.0902. 5.2 Reconfiguration Mobile devices may leave or enter the target area over time, 5 EXTENSIONS which makes the current charger placement and power allo- In this section,we provide three extensions of Sp3.The first cation not optimal in terms of charging quality.Hence,we is to deal with mobile devices instead of stationary devices may need to switch from one charger placement and power allocation to another one. (Section 5.1).The second is to study the reconfiguration problem when devices leave and enter the target area over First,when should we reconfigure the charger placement and power allocation?It is reasonable to start a reconfigura- time(Section 5.2).And the last is to optimize charging qual- ity with more candidate locations(Section 5.3). tion only when a certain percent of devices leave or enter the target area.For example,when S changes into S,if 5.1 Mobile Rechargeable Devices ss1 we start a reconfiguration.Here,repre- In Sp3,we assume that rechargeable devices are stationary. sents the percentage threshold. However,it is more realistic to consider mobile recharge- Second,how should we maintain smoothness when able devices.We consider MP3 problem in this section switching one solution to another one?By 'smoothness'we where M'denotes mobile. mean that,the received power by a device should not In Fig.4,the trajectory of a device sj is shown in decrease or increase too much when we change one charger dashed lines.Theoretically,we can compute the integral placement and power allocation into another one.Taking over its trajectory to obtain the charging quality given Fig.3 for example,suppose the power budget B is 6.pmin a charger placement and power allocation.However,this and the current power allocation H is(4,2,0).Now a new is too complicated.Instead,we resort to discrete time device s3 emerges and it is within D(2)distance from cs and modeling. within D(3)distance from c2.We have two new power
s1 or s2 is 0.07, i.e., P1 ¼ P2 ¼ 0:07. Given a power budget B ¼ 500, we now check how TCA works. In lines 2-7 of Algorithm 3, we first check which ðc; hÞ gives the maximal marginal objective gain. For c1, we have Qðfðc1; 1ÞgÞ ¼ 0:0128, Qðfðc1; 2ÞgÞ ¼ 0:0256, Qðfðc1; 3ÞgÞ ¼ 0:0384, and Qðfðc1; 4ÞgÞ ¼ 0:064; for c2 and c3, we can compute these values in a similar way. Thus, in the first iteration of lines 2-8, we add ðc1; 4Þ into Z1. It is worth noting that, in the second iteration, Qðfðc1; 4Þg [ fðc1; 2ÞgÞ Qðfðc1; 4ÞgÞ ¼ minfpðc1; s1; 2Þ; P1 pðc1; s1; 4Þg ¼ 0:0188 (see Eqs. (9) and (10)). The reader can check that, Z1 would be fðc1; 4Þ; ðc2; 4Þ;ðc1; 2Þg. Note that, for each location, we retain only one charger which has the largest power level in Z1. Then we get R1 ¼ fc1; c2g and H1 ¼ ð4; 4; 0Þ. In lines 5-8 of Algorithm 4, we try to utilize the remaining budget 500 ð4 þ 4Þ 50 ¼ 100. We find that, the distance between c3 and s2 is larger than Dð2Þ, thus, there is no need to allocate the remaining 100 units of power to c3. Finally we have R1 ¼ fc1; c2g and H1 ¼ ð4; 4; 0Þ. Similarly, after running lines 9-14, we would have Z2 ¼ fðc1; 4Þ;ðc1; 1Þ;ðc2; 2Þ;ðc2; 3Þg. Through removing duplications, we have R2 ¼ fc1; c2g and H2 ¼ ð4; 3; 0Þ. After utilizing the remaining budget, we also have R2 ¼ fc1; c2g and H2 ¼ ð4; 4; 0Þ. The final solution is R¼fc1; c2g and H ¼ ð4; 4; 0Þ, yielding an objective of QðR; HÞ ¼ 0:0902. 5 EXTENSIONS In this section, we provide three extensions of SP3. The first is to deal with mobile devices instead of stationary devices (Section 5.1). The second is to study the reconfiguration problem when devices leave and enter the target area over time (Section 5.2). And the last is to optimize charging quality with more candidate locations (Section 5.3). 5.1 Mobile Rechargeable Devices In SP3, we assume that rechargeable devices are stationary. However, it is more realistic to consider mobile rechargeable devices. We consider MP3 problem in this section where ‘M’ denotes mobile. In Fig. 4, the trajectory of a device sj is shown in dashed lines. Theoretically, we can compute the integral over its trajectory to obtain the charging quality given a charger placement and power allocation. However, this is too complicated. Instead, we resort to discrete time modeling. Denote by E the circle radius in the figure, and obviously, E can be used to control modeling precision. The trajectory of sj is represented by a set of tuples, i.e., ðxk j ; yk j ; tk j Þ. The kth tuple ðxk j ; yk j ; tk j Þ means that, sj stays with the circle, whose center and radius are ðxk j ; yk j Þ and E, respectively, for a time duration of t k j . We now show how to obtain these tuples. Denote by A1 the starting point of the trajectory. The distance between A1 and ðx1 j ; y1 j Þ is E, thus, we have the first circle. Denote by A2 the intersection point of the trajectory and the first circle. The distance between A2 and ðx2 j ; y2 j Þ is also E, thus, we have the second circle; and so on. t k j is set to be the time duration when sj is with its kth circle. Given a placement R and an allocation H, the total power pR;Hðsj; tk j Þ received by a device sj at its kth position is denoted by pR;Hðsj; tk j Þ ¼ X ci2R pðci; sjÞ: (11) Similarly, the charging quality of R and H on sj at its kth position is denoted by QR;Hðsj; tk j Þ ¼ minfpR;Hðsj; tk j Þ; Pjg: (12) And the charging quality of R and H on sj is defined as the weighted sum of QR;Hðsj; tk j Þ, i.e., QR;HðsjÞ ¼ 1 PK i¼1 t i j X K k¼1 t k jQR;Hðsj; tk j Þ: (13) With the above discrete time-based modeling, we can formulate a problem similar to SP3. Fortunately, MP3 also has the aforementioned tractable properties as SP3, based on which we can tailor Algorithm 3 to MP3 and yield an approximation algorithm of the same factor as TCA. Note that, the discrete time model could be arbitrarily precise when E is sufficiently small. 5.2 Reconfiguration Mobile devices may leave or enter the target area over time, which makes the current charger placement and power allocation not optimal in terms of charging quality. Hence, we may need to switch from one charger placement and power allocation to another one. First, when should we reconfigure the charger placement and power allocation? It is reasonable to start a reconfiguration only when a certain percent of devices leave or enter the target area. For example, when S changes into S0 , if jS0 S SS0 TSj jSj d, we start a reconfiguration. Here, d represents the percentage threshold. Second, how should we maintain smoothness when switching one solution to another one? By ‘smoothness’ we mean that, the received power by a device should not decrease or increase too much when we change one charger placement and power allocation into another one. Taking Fig. 3 for example, suppose the power budget B is 6 pmin and the current power allocation H is ð4; 2; 0Þ. Now a new device s3 emerges and it is within Dð2Þ distance from c3 and within Dð3Þ distance from c2. We have two new power Fig. 4. The trajectory of device sj is represented by a series of tuples. The kth tuple ðxk j ; yk j ; tk j Þ indicates that, sj stays within the circle, whose center and radius are ðxk j ; yk j Þ and E, respectively, for a time duration of t k j . 1490 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 6, JUNE 2018
ZHANG ET AL.:WIRELESS CHARGER PLACEMENT AND POWER ALLOCATION FOR MAXIMIZING CHARGING QUALITY 1491 allocations:H=(2,2,2)and H2 =(3,3,0).Although both of them satisfy the budget constraint,the latter one is better from the perspective from smoothness.For s1,pH(si)= o,m,《s）=andm《6)= a4-Pmin o-3-Pmin ornm(问=+《o= 2-Pmin 22+7 and p ()(We see that,for either s orthe a3-Pmin (a)G=1 (b)G=2 (c)G=19 received power fluctuates less when switching from H to H2 than H.Based on this observation,without loss of gen- Fig.5.Improving charging quality through more candidate locations.The erality,the reconfiguration cost from(R,H)to (R',H')can grey circle indicates the final charger placement and power allocation for each G. be defined as ensures that decreasing h does not increase f(H,H');then f(H,H')= h:- (14) we randomly select ci that satisfies hj>h,and increase h i=1 by one,which would definitely reduce f(H,H'). Following similar analyses to that of Algorithm 3,we To keep smoothness,the reconfiguration cost should not know the time complexity of Algorithm 5 is also O(MN3L3). exceed a threshold,denoted by F.More formally, The following gives the performance guarantee of IAA. Problem 5(Cost-constrained Reconfiguration Problem, CRP).Given current device set S,charger placement R,and Theorem 4.IAAis fctorapproximation algoritl for CRP power allocation H,if S evolves into S',find a new charger placement R'and power allocation H'that maximize the charg- Proof.Let us first compare the charging qualities of(R,H) ing quality,subject to f(H,H')OPI,where algorithm for CRP in Algorithm 5. OPT denotes the optimal solution for the new device set S'with respect to F.Combining above formulas Algorithm 5.Iteratively Adjustment Alg.(IAA)for CRP together,we have Input:C,S,B,S',and F Output:R'and H' Q(R,H)≥1-1 )FOPT. 4BL 1:(R.H)=TCA(S) 2:(R,H,)=TCA(S') The theorem follows immediately. 0 3:(R'.H-(Rt.H) 4:while f(H,H)>F do 5.3 Optimization with More Candidate Locations 5: i-arg minisis(R,H)-Q(R,H-Ii) The candidate locations for placing wireless chargers are 6: H'-H'-I fixed in aforementioned problems.In this section,we 7: randomly select jsuch thathj>h remove this constraint and allow chargers to be placed at H-H'+Ij any location within the target area. 9:end while To cope with the infinitive candidate locations,we turn 10:return(R',H') to the discrete space model:for G=1,2,...,we partition the target area into Gx G grids and use these Gx G grid The main idea of Algorithm 5 is as follows:we first centers as the candidate locations;the iteration stops when employ TCA to compute two solutions for S and S,respec- the gap between the charging quality in the Gth iteration tively (lines 1-2);then we iteratively adjust(R',H')in order and the best quality among previous(G-1)iterations is no to make sure f(H,H')hi,to minimize the marginal (60x60).Following existing works [15],[17],[18],we quality loss,i.e,Q(R',H')-Q(R',H'-Ii);here,h>hi assume that,pmin =50,L=2,pth =0.01,a =0.64,and
allocations: H1 ¼ ð2; 2; 2Þ and H2 ¼ ð3; 3; 0Þ. Although both of them satisfy the budget constraint, the latter one is better from the perspective from smoothness. For s1, pHðs1Þ ¼ a4pmin ðdðc1;s1ÞþbÞ 2 , pH1 ðs1Þ ¼ a2pmin ðdðc1;s1ÞþbÞ 2, and pH2 ðs1Þ ¼ a3pmin ðdðc1;s1ÞþbÞ 2. For s2, pHðs2Þ ¼ a4pmin ðdðc1;s2ÞþbÞ 2 þ a2pmin ðdðc2;s2ÞþbÞ 2, pH1 ðs2Þ ¼ a2pmin ðdðc2;s2ÞþbÞ 2, and pH2 ðs2Þ ¼ a3pmin ðdðc2;s2ÞþbÞ 2. We see that, for either s1 or s2, the received power fluctuates less when switching from H to H2 than H1. Based on this observation, without loss of generality, the reconfiguration cost from ðR; HÞ to ðR0 ; H0 Þ can be defined as fðH; H0 Þ ¼ X N i¼1 jhi h0 ij: (14) To keep smoothness, the reconfiguration cost should not exceed a threshold, denoted by F. More formally, Problem 5 (Cost-constrained Reconfiguration Problem, CRP). Given current device set S, charger placement R, and power allocation H, if S evolves into S0 , find a new charger placement R0 and power allocation H0 that maximize the charging quality, subject to fðH; H0 Þ F. Formally, CRP can be formulated as follows: max QðR0 ; H0 Þ (15a) s.t. fðH; H0 Þ F (15b) ðR; HÞ ¼ TCAðSÞ (15c) X ci2R0 pi B (15d) where Eq. (15c) means R and H are computed by TCA (i.e., Algorithm 3). It is not hard to see that CRP is also NPcomplete, since SP3 is a special case of CRP when F is suffi- ciently large. In the following, we design an approximation algorithm for CRP in Algorithm 5. Algorithm 5. Iteratively Adjustment Alg. (IAA) for CRP Input: C, S, B, S0 , and F Output: R0 and H0 1: ðR; HÞ ¼ TCAðSÞ 2: ðRt; HtÞ ¼ TCAðS0 Þ 3: ðR0 ; H0 Þ ðRt; HtÞ 4: while fðH; H0 Þ > F do 5: i arg min1iN;h0 i > hi QðR0 ; H0 Þ QðR0 ; H0 IiÞ 6: H0 H0 Ii 7: randomly select j such that hj > h0 j 8: H0 H0 þ Ij 9: end while 10: return ðR0 ; H0 Þ The main idea of Algorithm 5 is as follows: we first employ TCA to compute two solutions for S and S0 , respectively (lines 1-2); then we iteratively adjust ðR0 ; H0 Þ in order to make sure fðH; H0 Þ F (lines 4-9). In each iteration of the while-loop, we decrease the power level of ci by one, which satisfies 1 i N and h0 i > hi, to minimize the marginal quality loss, i.e., QðR0 ; H0 Þ QðR0 ; H0 IiÞ; here, h0 i > hi ensures that decreasing h0 i does not increase fðH; H0 Þ; then we randomly select cj that satisfies hj > h0 j, and increase h0 j by one, which would definitely reduce fðH; H0 Þ. Following similar analyses to that of Algorithm 3, we know the time complexity of Algorithm 5 is also OðMN3L3Þ. The following gives the performance guarantee of IAA. Theorem 4. IAA is a factor ð11=eÞF 4BL approximation algorithm for CRP. Proof. Let us first compare the charging qualities of ðRt; HtÞ (line 2) and ðR0 ; H0 Þ (line 10). Due to the submodularity of QðR; HÞ and the way we decrease power levels (lines 5- 6), we can guarantee that the charging quality loss due to power levels decrease is no more than 2BF 2B QðRt; HtÞ. Hence, we have QðR0 ; H0 Þ F 2B QðRt; HtÞ: According to Theorem 3, we have QðRt; HtÞ 1 1=e 2L OPT where OPT denotes the optimal solution for the new device set S0 irrespective of reconfiguration cost threshold, i.e., F. Obviously, we have OPT OPT, where OPT denotes the optimal solution for the new device set S0 with respect to F. Combining above formulas together, we have QðR0 ; H0 Þ ð1 1=eÞF 4BL OPT: The theorem follows immediately. tu 5.3 Optimization with More Candidate Locations The candidate locations for placing wireless chargers are fixed in aforementioned problems. In this section, we remove this constraint and allow chargers to be placed at any location within the target area. To cope with the infinitive candidate locations, we turn to the discrete space model: for G ¼ 1; 2; ... ; we partition the target area into G G grids and use these G G grid centers as the candidate locations; the iteration stops when the gap between the charging quality in the Gth iteration and the best quality among previous ðG 1Þ iterations is no more than a threshold. Fig. 5 shows an example. There are 3 devices in the plane (60 60). Following existing works [15], [17], [18], we assume that, pmin ¼ 50, L ¼ 2, pth ¼ 0:01, a ¼ 0:64, and Fig. 5. Improving charging quality through more candidate locations. The grey circle indicates the final charger placement and power allocation for each G. ZHANG ET AL.: WIRELESS CHARGER PLACEMENT AND POWER ALLOCATION FOR MAXIMIZING CHARGING QUALITY 1491
1492 IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.6,JUNE 2018 The second phase is to invoke Algorithm 2 to generate a charger placement. 0 Optimal Algorithm (OPT):All of SP3,MP3,and CRP are NP-complete.We simply use brute force to find the optimal solution.Due to its high time complexity O(MLN),it is only practical for small instances. 10 110 130 number of candidate locations 4,number of devices 6.2 Results of SP3 (a) (b) 6.2.1 Setup We evaluate the performance of TCA on SP3 instances in this section.We assume that wireless devices and candidate locations are randomly distributed over a 1.000 m x 1.000 m two-dimensional square area.The default number of can- didate locations is 20.The minimum power Pmin of a charger is 50.By default,the maximum power level L is 6.The 00 E00 70 800 900 1000 d.power budge aximum power level of a charger default number of devices is 200.Following prior works [151, (c) (d) [171,we set a=0.64 and B=30 in the charging model Fig.6.Evaluation results on small instances of SP3(the default setting is (Eq.(3)).The threshold ph of negligible power is 0.01. N=8,M=50,B=800,L=4,and the side length of the 2-D plane is Therefore,the minimum coverage radius is D(1)= 300m). √/0.64×50/0.01-30≈27m(see Eq.(4),and by default the maximum coverage radius is D(6)=V0.64 x 300/0.01- B=30.Given these parameters,we have D(1)27 and 30109 m.The average power consumption rate of each D(2)=50.The average power consumption rate of each device is uniformly generated between 0.02 and 0.03.The device is 0.02,i.e.,=B2=P=0.02.The grey circle indi- default power budget is 3,000. cates the coverage of a charger.Given a power budget B=100,we now show how the placement and allocation 6.2.2 Results evolves as G increases. When G=1 (Fig.5a),the final placement is (c1}and the As we have mentioned,it is impractical to run OPT using power allocation is H=(2),yielding a charging quality of brute force in general;we thus use the following setting to 0.045.When G=2 (Fig.5b),the final placement is [cs}and generate some small instances for comparing TCA with the power allocation is H=(0,0,2,0),yielding a charging OPT:N=8,M=50,B=800,L=4,and the side length of quality of 0.031.When G=19 (Fig.5c),the final placement the 2-D plane is 300 m.Fig.6 shows the results of different is {c162}and the power allocation is H=(0,0,....2....,0), experiment setups of small instances.We ran each different yielding a charging quality of 0.047,which is also the opti- setup ten times and averaged the results.The max and min mal solution of the example values among ten runs are also provided in the figures. In general,TCA achieves a near optimal solution and 6 PERFORMANCE EVALUATION outperforms the other algorithms.Specifically,the gap between TCA and OPT is 4.5 percent at most and 2.0 percent on In this section,we first introduce baseline algorithms average.This observation validates our theoretical results. (Section 6.1),then we present simulation results and key FLA uses a similar idea as our algorithm,thus,it performs findings (Sections 6.2,6.3,6.4,and 6.5). much better than RAN,which has the worst performance of all the setups.On average,the charging quality RAN 6.1 Baselines achieves is roughly 64.4 percent of that of TCA. We introduce three algorithms for comparison. In Figs.6a and 6d,when the number of candidate loca- Random Algorithm(RAN):It should generate each possi- tions increases or the maximum power level of a candidate ble solution with the same probability.We implement it as location increases,the chance of having a better solution follows.Let b=0 at the beginning.In the ith iteration,we goes up,so the overall charging quality increases.Since a uniformly generate a random integer ri in the range [1,L], charger can transfer power to multiple devices simulta- let b=b+ri;if (B/pmin-b)is no less than L,go to the next neously [30],when the number of energy receiving devices iteration,else let i+be(B/pmin-b).Suppose the index of increases,the total power received by all devices would be the last iteration is k,for k+1 sjN,we let zj be 0.We larger than before,so the charging quality increases as well. then sort xi,2,...,xN randomly to get a random permuta- This is what we noticed in Fig.6b.Fig.6c presents the per- tion (,...,)For each ci,we set Hcil in the random formance of the four algorithms when the power budget is solution. varying.As we can see,when the budget increases,our Fixed Level Algorithm(FLA):It consists of two phases.The objective function increases as expected. first phase is to compute the optimal power level of each For easy understanding,we visualize two charger place- location irrespective of the other locations,i.e., ments and the corresponding allocated power levels gener- ated by TCA for two instances of p3 in Fig.7.In Fig.7a, hi=arg max ∑0Qes (16) there are a total of 9 candidate locations and 50 devices. hief1....! p(hi) TCA picks 6 of them,and the corresponding power levels are 4,3,1,4,1,and 3.As we mentioned in Eq.(4),the
b ¼ 30. Given these parameters, we have Dð1Þ 27 and Dð2Þ ¼ 50. The average power consumption rate of each device is 0.02, i.e., P1 ¼ P2 ¼ P3 ¼ 0:02. The grey circle indicates the coverage of a charger. Given a power budget B ¼ 100, we now show how the placement and allocation evolves as G increases. When G ¼ 1 (Fig. 5a), the final placement is fc1g and the power allocation is H ¼ ð2Þ, yielding a charging quality of 0.045. When G ¼ 2 (Fig. 5b), the final placement is fc3g and the power allocation is H ¼ ð0; 0; 2; 0Þ, yielding a charging quality of 0.031. When G ¼ 19 (Fig. 5c), the final placement is fc162g and the power allocation is H ¼ ð0; 0; ... ; 2; ... ; 0Þ, yielding a charging quality of 0.047, which is also the optimal solution of the example. 6 PERFORMANCE EVALUATION In this section, we first introduce baseline algorithms (Section 6.1), then we present simulation results and key findings (Sections 6.2, 6.3, 6.4, and 6.5). 6.1 Baselines We introduce three algorithms for comparison. Random Algorithm (RAN): It should generate each possible solution with the same probability. We implement it as follows. Let b ¼ 0 at the beginning. In the ith iteration, we uniformly generate a random integer xi in the range ½1; L, let b ¼ b þ xi; if ðB=pmin bÞ is no less than L, go to the next iteration, else let xiþ1 be ðB=pmin bÞ. Suppose the index of the last iteration is k, for k þ 1 j N, we let xj be 0. We then sort x1, x2; ... ; xN randomly to get a random permutation ðx0 1; ... ; x0 N Þ. For each ci, we set H½ci ¼ x0 i in the random solution. Fixed Level Algorithm (FLA): It consists of two phases. The first phase is to compute the optimal power level of each location irrespective of the other locations, i.e., hi ¼ arg max hi2f1;...;Lg PM j¼1 QfcigðsjÞ pðhiÞ : (16) The second phase is to invoke Algorithm 2 to generate a charger placement. Optimal Algorithm (OPT): All of SP3, MP3, and CRP are NP-complete. We simply use brute force to find the optimal solution. Due to its high time complexity OðMLN Þ, it is only practical for small instances. 6.2 Results of SP3 6.2.1 Setup We evaluate the performance of TCA on SP3 instances in this section. We assume that wireless devices and candidate locations are randomly distributed over a 1;000 m 1;000 m two-dimensional square area. The default number of candidate locations is 20. The minimum power pmin of a charger is 50. By default, the maximum power level L is 6. The default number of devices is 200. Following prior works [15], [17], we set a ¼ 0:64 and b ¼ 30 in the charging model (Eq. (3)). The threshold pth of negligible power is 0.01. Therefore, the minimum coverage radius is ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi Dð1Þ ¼ 0:64 50=0:01 p 30 27 m (see Eq. (4)), and by default the maximum coverage radius is Dð6Þ ¼ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 0:64 300=0:01 p 30 109 m. The average power consumption rate of each device is uniformly generated between 0.02 and 0.03. The default power budget is 3,000. 6.2.2 Results As we have mentioned, it is impractical to run OPT using brute force in general; we thus use the following setting to generate some small instances for comparing TCA with OPT: N ¼ 8, M ¼ 50, B ¼ 800, L ¼ 4, and the side length of the 2-D plane is 300 m. Fig. 6 shows the results of different experiment setups of small instances. We ran each different setup ten times and averaged the results. The max and min values among ten runs are also provided in the figures. In general, TCA achieves a near optimal solution and outperforms the other algorithms. Specifically, the gap between TCA and OPT is 4.5 percent at most and 2.0 percent on average. This observation validates our theoretical results. FLA uses a similar idea as our algorithm, thus, it performs much better than RAN, which has the worst performance of all the setups. On average, the charging quality RAN achieves is roughly 64.4 percent of that of TCA. In Figs. 6a and 6d, when the number of candidate locations increases or the maximum power level of a candidate location increases, the chance of having a better solution goes up, so the overall charging quality increases. Since a charger can transfer power to multiple devices simultaneously [30], when the number of energy receiving devices increases, the total power received by all devices would be larger than before, so the charging quality increases as well. This is what we noticed in Fig. 6b. Fig. 6c presents the performance of the four algorithms when the power budget is varying. As we can see, when the budget increases, our objective function increases as expected. For easy understanding, we visualize two charger placements and the corresponding allocated power levels generated by TCA for two instances of P3 in Fig. 7. In Fig. 7a, there are a total of 9 candidate locations and 50 devices. TCA picks 6 of them, and the corresponding power levels are 4, 3, 1, 4, 1, and 3. As we mentioned in Eq. (4), the Fig. 6. Evaluation results on small instances of SP3 (the default setting is N ¼ 8, M ¼ 50, B ¼ 800, L ¼ 4, and the side length of the 2-D plane is 300 m). 1492 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 6, JUNE 2018