Connectivity-Constrained Placement of Wireless Chargers

Nan Yu; Haipeng Dai; Guihai Chen; Alex X. Liu; Bingchuan Tian; Tian He

doi:10.1109/tmc.2019.2954306

Connectivity-Constrained Placement of Wireless Chargers

Nan Yu, Haipeng Dai, Guihai Chen, Alex X. Liu, Bingchuan Tian, Tian He

Center for Transportation Studies

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

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.

Original language	English (US)
Article number	8906152
Pages (from-to)	909-927
Number of pages	19
Journal	IEEE Transactions on Mobile Computing
Volume	20
Issue number	3
DOIs	https://doi.org/10.1109/tmc.2019.2954306
State	Published - Mar 1 2021

Bibliographical note

Funding 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.

Publisher Copyright:
© 2002-2012 IEEE.

Keywords

Connectivity
approximation algorithm
directional charging
wireless power transfer

Publisher link

10.1109/tmc.2019.2954306

Find It

Find It at U of M Libraries

Cite this

@article{1bfa0364b562423db2fa87c1ce9167df,

title = "Connectivity-Constrained Placement of Wireless Chargers",

abstract = "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. ",

keywords = "Connectivity, approximation algorithm, directional charging, wireless power transfer",

author = "Nan Yu and Haipeng Dai and Guihai Chen and Liu, {Alex X.} and Bingchuan Tian and Tian He",

note = "Funding 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. Publisher Copyright: {\textcopyright} 2002-2012 IEEE.",

year = "2021",

month = mar,

day = "1",

doi = "10.1109/tmc.2019.2954306",

language = "English (US)",

volume = "20",

pages = "909--927",

journal = "IEEE Transactions on Mobile Computing",

issn = "1536-1233",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - Connectivity-Constrained Placement of Wireless Chargers

AU - Yu, Nan

AU - Dai, Haipeng

AU - Chen, Guihai

AU - Liu, Alex X.

AU - Tian, Bingchuan

AU - He, Tian

N1 - Funding 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. Publisher Copyright: © 2002-2012 IEEE.

PY - 2021/3/1

Y1 - 2021/3/1

N2 - 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.

AB - 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.

KW - Connectivity

KW - approximation algorithm

KW - directional charging

KW - wireless power transfer

UR - http://www.scopus.com/inward/record.url?scp=85075359437&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075359437&partnerID=8YFLogxK

U2 - 10.1109/tmc.2019.2954306

DO - 10.1109/tmc.2019.2954306

M3 - Article

AN - SCOPUS:85075359437

SN - 1536-1233

VL - 20

SP - 909

EP - 927

JO - IEEE Transactions on Mobile Computing

JF - IEEE Transactions on Mobile Computing

IS - 3

M1 - 8906152

ER -

Connectivity-Constrained Placement of Wireless Chargers

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this