text: The (maximum receiver-centric) interference of a geometric graph (von (2005)) is studied. It is shown that, with high probability, the following results hold for a set, V, of n points independently and uniformly distributed in the unit d-cube, for constant dimension d: (1) there exists a connected graph with vertex set V that has interference O((log n)^ 1 3 ); (2) no connected graph with vertex set V has interference o((log n)^ 1 4 ); and (3) the minimum spanning tree of @math has interference Theta(( n)^ 1 2 ).
  @cite_0: 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 (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 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.
  @cite_5: We consider interference minimization in wireless ad-hoc networks. This is formulated as assigning a suitable transmission radius to each of the given points in the plane, so as to minimize the maximum number of transmission ranges overlapping any point. Using ideas from computational geometry and @e-net theory, we attain an O(@D) bound for the maximum interference where @D is the interference of a uniform-radius ad-hoc network. This generalizes a result given in [P. von Rickenbach, S. Schmid, R. Wattenhofer, A. Zollinger, A robust interference model for wireless ad-hoc networks, in: Proc. 5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Denver, Colorado, USA, April 2005] for the special case of highway model (i.e., one-dimensional problem) to the two-dimensional case. We show how a distributed algorithm can achieve a slightly weaker bound. We also give a method based on quad-tree decomposition and bucketing that has another provable interference bound in terms of the ratio of the minimum distance to the radius of a uniform-radius ad-hoc network.
  @cite_3: 
summary: Several authors have shown that the interference of a point set is related to the (logarithm of) the ratio between the longest and shortest distance defined by the point set. In particular, different versions of the following theorem have been proven by Halld 'orsson and Tokuyama @cite_5 ; Khabbazian, Durocher, and Haghnegahdar @cite_0 ; and Maheshwari, Smid, and Zeh @cite_3 : At least two of the proofs of log proceed by showing that @math . A strengthening of this theorem is that the numerator in the definition of @math can be replaced with the length of the longest edge in @math @cite_0 @cite_3 .