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 identification 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 efficiently 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, 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 1−1/e2L, 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 SP 3 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 MP 3. 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 (1−1/e)F4BL, 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 NP-complete.

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 SP 3 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.