Braess’s Paradox in Wireless Networks: The Danger of Improved Technology

Michael Dinitz and Merav Parter

Abstract: When comparing new wireless technologies, it is common to consider the effect that they have on the capacity of the network (defined as the maximum number of simultaneously satisfiable links).  For example, it has been shown that giving receivers the ability to do interference cancellation, or allowing transmitters to use power control, never decreases the capacity and can in certain cases increase it by Omega(log (Delta Pmax)), where Delta is the ratio of the longest link length to the smallest transmitter-receiver distance and Pmax is the maximum transmission power.  But there is no reason to expect the optimal capacity to be realized in practice, particularly since maximizing the capacity is known to be NP-hard.  In reality, we would expect links to behave as self-interested agents, and thus when introducing a new technology it makes more sense to compare the values reached at game-theoretic equilibria than the optimum values.
In this paper we initiate this line of work by comparing various notions of equilibria (particularly Nash equilibria and no-regret behavior) when using a supposedly “better” technology.  We show a version of Braess’s Paradox for all of them: in certain networks, upgrading technology can actually make the equilibria \emph{worse}, despite an increase in the capacity.  We construct instances where this decrease is a constant factor for power control, interference cancellation, and improvements in the SINR threshold beta, and is Omega(log Delta) when power control is combined with interference cancellation.  However, we show that these examples are basically tight: the decrease is at most O(1)for power control, interference cancellation, and improved beta, and is at most
O(log Delta) when power control is combined with interference cancellation.
Guest: Michael Dinitz
Host: Yvonne-Anne Pignolet

Wireless Connectivity and Capacity

Magnus M. Halldorsson, Pradipta Mitra


Given $n$ wireless transceivers located in a plane, a fundamental problem in wireless communications is to construct a strongly connected digraph on them such that the constituent links can be scheduled in fewest possible time slots, assuming the SINR model of interference.
In this paper, we provide an algorithm that connects an arbitrary point set in $O(\log n)$ slots, improving on the previous best bound of $O(\log^2 n)$ due to Moscibroda. This is complemented with a super-constant lower bound on our approach to connectivity. An important feature is that the algorithms allow for bi-directional (half-duplex) communication.
One implication of this result is an improved bound of $\Omega(1/\log n)$ on the worst-case capacity of wireless networks, matching the best bound known for the extensively studied average-case.
We explore the utility of oblivious power assignments, and show that essentially all such assignments result in a worst case bound of $\Omega(n)$ slots for connectivity. This rules out a recent claim of a $O(\log n)$ bound using oblivious power. On the other hand, using our result we show that $O(\min(\log \Delta, \log n \cdot (\log n + \log \log \Delta)))$ slots suffice, where $\Delta$ is the ratio between the largest and the smallest links in a minimum spanning tree of the points.
Our results extend to the related problem of minimum latency aggregation scheduling, where we show that aggregation scheduling with $O(\log n)$ latency is possible, improving upon the previous best known latency of $O(\log^3 n)$. We also initiate the study of network design problems in the SINR model beyond strong connectivity, obtaining similar bounds for biconnected and $k$-edge connected structures.

Guest: Magnus M. Halldorsson

Host: Merav Parter