|Nan Yu||Nanjing University & State Key Laboratory for Novel Software Technology, P.R. China|
|Haipeng Dai||Nanjing University & State Key Laboratory for Novel Software Technology, P.R. China|
|Alex X Liu||Michigan State University, USA|
|Bingchuan Tian||Nanjing University, P.R. China|
In this paper, we first study the problem of Connected wIReless Charger pLacEment (CIRCLE). That is, given a fixed number of directional wireless chargers and candidate positions, determining the placement position and orientation angle for each charger under connectivity constraint for wireless chargers such that the overall charging utility is maximized. To address CIRCLE, we first consider a relaxed version of CIRCLE (CIRCLE-R for short). We prove that CIRCLE-R falls into the realm of maximizing a submodular set function subject to a connectivity constraint, and propose an algorithm whose approximation ratio is at least 1.5 times better than that of the state-of-the-art algorithm. Next, we reduce the solution space for CIRCLE from infinite to finite, and propose an algorithm with a constant approximation ratio to address CIRCLE. We conduct both simulations and field experiments to verify our theoretical findings. The results show that our algorithm can outperform comparison algorithms by 83.35%.