Placing Wireless Chargers With Multiple Antennas
Haipeng Dai, Yikang Zhang, Weijun Wang, Rong Gu, Yuben Qu, Chi Lin, Lijie Xu, Jiaqi Zheng, Wanchun Dou, Guihai Chen
Abstract
Charger placement is an important problem in improving the quality of service in wireless rechargeable sensor networks. This paper studies the problem of <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">W</u> ireless Ch <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</u> rger Placeme <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</u> t with Multiple (Directional) Antennas (WANDA). The problem is described as follows: given a set of wireless chargers equipped with multiple directional antennas and a set of wireless rechargeable sensors, determine the chargers' positions and orientations to maximize the overall charging utility. According to the relative positional relationship between the antennas, the problem is classified into Relative Orientation Fixed (WANDA-ROF) and Relative Orientation Unfixed (WANDA-ROU) situations. To address WANDA, we present a piecewise constant function to approximate the nonlinearity of charging power and propose an area discretization technique to reduce the infinite solution space to a limited one without performance loss. Then, we prove the monotonic submodularity of WANDA, and present a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\frac{1}{2}-\epsilon$</tex-math></inline-formula> approximation algorithm for the ROF situation and a <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\frac{1}{2}-\epsilon$</tex-math></inline-formula> approximation algorithm for the ROU situation, all run in polynomial time. Finally, we conduct extensive simulation and experiments to show that our algorithms outperform comparison algorithms by at least 16% for ROF situation and 12% for ROU situation.