Name
Abstract | ||
|---|---|---|
We study the problem of assigning transmission ranges to radio stations in the plane such that any pair of stations can communicate within a bounded number of hops h and the cost of the network is minimized. We consider two settings of the problem: collinear station locations and arbitrary locations. For the case of collinear stations, we introduce the pioneer polynomial-time exact algorithm for any \(\alpha \ge 1\) and constant h, and thus conclude that the 1D version of the problem, where h is a constant, is in \(\mathcal {P}\). Furthermore, we provide a 3 / 2-approximation algorithm for the case where h is an arbitrary number and \(\alpha =1\), improving the previously best known approximation ratio of 2. For the case of stations placed arbitrarily in the plane and \(\alpha =1\), we first present a \((1.5+ \varepsilon )\)-approximation algorithm for a case where a deviation of one hop (\(h+1\) hops in total) is acceptable. Then, we show a \((3+\varepsilon )\)-approximation algorithm that complies with the exact hop bound. To achieve that, we introduce the following two auxiliary problems, which are of independent interest. The first is the bounded-hop multi-sink range problem, for which we present a PTAS which can be applied to compute a \((1+\varepsilon )\)-approximation for the bounded diameter minimum spanning tree, for any \(\varepsilon >0\). The second auxiliary problem is the bounded-hop dual-sink pruning problem, for which we show a polynomial-time algorithm. To conclude, we consider the initial bounded-hop all-to-all range assignment problem and show that a combined application of the aforementioned problems yields the \((3+\varepsilon )\)-approximation ratio for this problem, which improves the previously best known approximation ratio of \(4(9^{h-2})/(\root h \of {2}-1)\). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s00453-017-0370-9 | Algorithmica |
Keywords | DocType | Volume |
Computational geometry,Approximation algorithms,Wireless networks | Journal | 80 |
Issue | ISSN | Citations |
11 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paz Carmi | 1 | 321 | 43.14 |
| Lilach Chaitman-Yerushalmi | 2 | 16 | 4.72 |
| Ohad Trabelsi | 3 | 8 | 4.46 |