TY - JOUR

T1 - Minimizing interference in ad hoc networks with bounded communication radius

AU - Korman, Matias

N1 - Funding Information:
✩ A preliminary version of this paper appeared in the proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011). E-mail address: matias.korman@upc.edu. 1 With the support of the Secretary for Universities and Research of the Ministry of Economy and Knowledge of the Government of Catalonia and the European Union.

PY - 2012/10/15

Y1 - 2012/10/15

N2 - 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.

AB - 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.

KW - Ad hoc networks

KW - Algorithms

KW - Bucketing

KW - Interference

KW - Minimum spanning tree

UR - http://www.scopus.com/inward/record.url?scp=84863474894&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863474894&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2012.06.021

DO - 10.1016/j.ipl.2012.06.021

M3 - Article

AN - SCOPUS:84863474894

SN - 0020-0190

VL - 112

SP - 748

EP - 752

JO - Information Processing Letters

JF - Information Processing Letters

IS - 19

ER -