Abstract | ||
---|---|---|
This paper considers the problem of practical
<underline>H</underline>
eterogeneous w
<underline>I</underline>
reless charger
<underline>P</underline>
lacement with
<underline>O</underline>
bstacles (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
<italic>strategies</italic>
, 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
<inline-formula><tex-math notation="LaTeX">$\frac{1}{2} - \epsilon$</tex-math></inline-formula>
. We conduct experiments to evaluate the performance. Results show that our algorithm outperforms the comparison algorithms by at least 33.49 percent on average. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1109/TMC.2019.2916384 | IEEE Transactions on Mobile Computing |
Keywords | DocType | Volume |
Wireless sensor networks,Wireless communication,Approximation algorithms,Partitioning algorithms,Mobile computing,Shape,Sensors | Journal | 19 |
Issue | ISSN | Citations |
8 | 1536-1233 | 4 |
PageRank | References | Authors |
0.39 | 0 | 8 |
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 |
Nan Yu | 5 | 13 | 2.53 |
guihai chen | 6 | 3537 | 317.28 |
Wanchun Dou | 7 | 878 | 96.01 |
xiaobing wu | 8 | 396 | 22.25 |