Minimizing interference in ad hoc networks with bounded communication radius

We consider a topology control problem in which we are given a set of sensors in R ^d and we would like to assign a communication radius to each of them so that they generate a connected network and have low receiver-based interference (defined as the largest in-degree of the network). We show that any radii assignment that generates a connected network can be modified so that interference is (asymptotically) unaffected and no sensor is assigned communication radius larger than R _min, where R _min is the smallest possible radius needed to obtain strong connectivity. Combining this result with the previous network construction methods (see Halldórsson and Tokuyama (2008) [7] and von Rickenbach et al. (2009) [11]), we obtain a way to construct a connected network of low interference and bounded radii. Since the radius of a sensor is only affected by neighboring sensors, this construction can be done in a distributed fashion.