  The interference at a wireless node s can be modelled by the number of
wireless nodes whose transmission ranges cover s. Given a set of positions for
wireless nodes, the interference minimization problem is to assign a
transmission radius (equivalently, a power level) to each node such that the
resulting communication graph is connected, while minimizing the maximum
interference. We consider the model introduced by von Rickenback et al. (2005),
in which each transmission range is represented by a ball and edges in the
communication graph are symmetric. The problem is NP-complete in two dimensions
(Buchin 2008) and no polynomial-time approximation algorithm is known.
Furthermore, even in one dimension (the highway model), the problem's
complexity is unknown and the maximum interference of a set of n wireless nodes
can be as high as Theta(sqrt(n)) (von Rickenback et al. 2005). In this paper we
show how to solve the problem efficiently in settings typical for wireless ad
hoc networks. In particular, we show that if node positions are represented by
a set P of n points selected uniformly and independently at random over a
d-dimensional rectangular region, for any fixed d, then the topology given by
the closure of the Euclidean minimum spanning tree of P has maximum
interference O(log n) with high probability. We extend this bound to a general
class of communication graphs over a broad set of probability distributions.
Next we present a local algorithm that constructs a graph from this class; this
is the first local algorithm to provide an upper bound on the expected maximum
interference. Finally, we discuss an empirical evaluation of our algorithm with
a suite of simulation results.
