Optimal Deployment for Roadside Wireless Charger with Bounded Detouring Cost

Wireless energy transfer technologies have played an important role in the development of Internet of Things (IoTs). Most of previous studies focus on scheduling mobile chargers efficiently for rechargeable sensor nodes. In this paper, we consider optimizing the deployment for Wireless Charging Stations (WCSs) in urban area. We respect the users detouring cost, when they need move to the candidate WCSs. Given a number of WCSs and users trajectories, we aim at optimizing the WCSs deployment to maximize the number of users for recharging with guaranteed probability. We convert our deployment problem into the weighted maximum coverage problem, which has been proved to be NP-hard. We have also proved that our objective function is a maximum submodular set function. Then a simple but efficient greedy algorithm could be applied with guaranteed approximation ratio (1-1/e). Finally, we evaluate the performance of our algorithm by comparing with two effective algorithms, and the impacts of different parameters on our algorithm. The evaluation results show that our algorithm improves the number of covered users with 30% comparing with two aforementioned algorithms.