Name
Abstract | ||
|---|---|---|
This paper considers the problem of Heterogeneous wIreless charger Placement with Obstacles (HIPO), i.e., given a number of heterogeneous rechargeable devices distributed on a 2D plane where obstacles of arbitrary shapes exist, deploying heterogeneous chargers with a given cardinality of each type, i.e., determining their positions and orientations, the combination of which we name as strategies, on the plane such that the rechargeable devices achieve maximized charging utility. After presenting our practical directional charging model, we first propose to use a piecewise constant function to approximate the nonlinear charging power, and divide the whole area into multi-feasible geometric areas in which a certain type of chargers have constant approximated charging power. Next, we propose the Practical Dominating Coverage Set extraction algorithm to reduce the unlimited solution space to a limited one by exacting a finite set of candidate strategies for all multi-feasible geometric areas. Finally, we prove the problem falls in the realm of maximizing a monotone submodular function subject to a partition matroid constraint, which allows a greedy algorithm to solve with approximation ratio of 1/2- epsilon. We conduct both simulations and field experiments to evaluate the performance of our algorithm and other five comparison algorithms. The results show that our algorithm outperforms the comparison algorithms by at least 33.49% on average. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1145/3225058.3225079 | PROCEEDINGS OF THE 47TH INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING |
Keywords | Field | DocType |
Charger placement, Heterogeneity, Obstacles | Matroid,Mathematical optimization,Finite set,Computer science,Constant function,Submodular set function,Cardinality,Greedy algorithm,Monotone polygon,Piecewise,Distributed computing | Conference |
ISSN | Citations | PageRank |
0190-3918 | 3 | 0.40 |
References | Authors | |
12 | 7 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiaoyu Wang | 1 | 167 | 59.60 |
| Dai Haipeng | 2 | 419 | 55.44 |
| Weijun Wang | 3 | 15 | 3.27 |
| Jiaqi Zheng | 4 | 34 | 4.54 |
| guihai chen | 5 | 3537 | 317.28 |
| Wanchun Dou | 6 | 878 | 96.01 |
| xiaobing wu | 7 | 396 | 22.25 |