Bounded-Hop Communication Networks Academic Article

•
• Overview
•
• Research
•
• Additional Document Info
•
• View All
•

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)$$.

publication date

• January 1, 2018