Name
Abstract | ||
|---|---|---|
The problem of computing a connected network with minimum interference is a fundamental problem in wireless sensor networks. Several models of interference have been studied in the literature. The most common one is the receiver-centric, in which the interference of a node pis defined as the number of other nodes whose transmission range covers p. In this paper, we study the problem of assigning a transmission range to each sensor, such that the resulting network is strongly connected and the total interference of the network is minimized.For the one-dimensional case, we show how to solve the problem optimally in O(n(3)) time. For the two-dimensional case, we show that the problem is NP-complete and give a polynomial-time 2-approximation algorithm for the problem. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1016/j.tcs.2021.08.003 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
Computational geometry, Wireless sensor networks, Interference, NP-hardness, Approximation algorithms | Journal | 889 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Karim Abu-Affash | 1 | 37 | 7.94 |
| Paz Carmi | 2 | 321 | 43.14 |
| Matthew J. Katz | 3 | 130 | 12.41 |