Bounded-Hop Communication Networks Academic Article uri icon


  • 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)\).

publication date

  • September 8, 2017