In this article, 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 problem, 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. Besides, we consider a variant of CIRCLE, CIRCLE-NB, and propose an approximation algorithm to address it. We conduct both simulation experiments and field experiments to verify our theoretical findings. The results show that our algorithm can outperform comparison algorithms by 83.35 percent.
Bibliographical noteFunding Information:
This work was supported in part by the National Key R&D Program of China under Grant No. 2018YFB1004704, in part by the Postgraduate Research & Practice Innovation Program of Jiangsu Province KYCX18_0044, in part by the National Natural Science Foundation of China under Grants 61872178, 61502229, 61373130, 61672276, 61472184, 61629302, 61832005, 61872173, 61872082, and 61321491, in part by the Natural Science Foundation of Jiangsu Province under Grant No. BK20181251, in part by the open research fund of Key Lab of Broadband Wireless Communication and Sensor Network Technology (Nanjing University of Posts and Telecommunications), Ministry of Education, in part by the Key Research and Development Project of Jiangsu Province under Grant No. BE2015154, and BE2016120, in part by the Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing University, in part by the Jiangsu High-level Innovation and Entrepreneurship (Shuangchuang) Program, in part by the Fundamental Research Funds for the Central Universities under Grant 021014380079, in part by the Joint Research Fund for Overseas Chinese Scholars and Scholars in Hong Kong and Macao Young Scholars under Grant F030307, and the Guangdong Leading Talent Program No. 2016LJ06D658, and in part by the Jiangsu Innovation and Entrepreneurship (Shuangchuang) Program.
- approximation algorithm
- directional charging
- wireless power transfer