Summary: We investigate the problem of path selection in radio networks for a given static set of \(n\) sites in two- and three-dimensional space. For static point-to-point communication we define measures for congestion, dilation, and energy consumption that take interferences among communication links into account.
We show that energy-optimal path selection for radio networks can be computed in polynomial time. Then we introduce the diversity \(g(V)\) of a set \(V \subseteq \mathbb {R}^d\) for any constant \(d\). It can be used to upper bound the number of interfering edges. For real-world applications it can be regarded as \(\Theta(\log n)\). A main result is that a \(c\)-spanner construction as a communication network allows one to approximate the congestion-optimal path system by a factor of \(O(g(V)^2)\).
Furthermore, we show that there are vertex sets where only one of the performance parameters congestion, dilation, and energy can be optimized at a time. We show trade-offs lower bounding congestion \(\times\) dilation and dilation \(\times\) energy. The trade-off between congestion and dilation increases with switching from two-dimensional to three-dimensional space. For congestion and energy the situation is even worse. It is only possible to find a reasonable approximation for either congestion or energy minimization, while the other parameter is at least a polynomial factor worse than in the optimal network.