In this paper, we study the connectivity problem for wireless networks under the physical signal to interference plus noise ratio (SINR) model. Given a set of radio transmitters distributed in some area, we seek to build a directed strongly connected communication graph, and compute an edge coloring of this graph such that the transmitter-receiver pairs in each color class can communicate simultaneously. Depending on the interference model, more or fewer colors, corresponding to the number of frequencies or time slots, are necessary. We consider the interference model that compares the received power of a signal at a receiver to the sum of the strength of other signals plus ambient noise. The strength of a signal is assumed to fade polynomially with the distance from the sender, depending on the so-called path-loss exponent α. We show that, when all transmitters use the same power, the number of colors needed is constant in one-dimensional grids if α>1 as well as in two-dimensional grids if α>2. For smaller path-loss exponents and two-dimensional grids we prove upper and lower bounds in the order of O(logn) and Ω(lognloglogn) for α=2 and Θ(n2 α-1) for α<2, respectively. If nodes are distributed uniformly at random on the interval [0,1], a regular coloring of O(logn) colors guarantees connectivity, while Ω(loglogn) colors are required for any coloring. © 2011 Elsevier B.V. All rights reserved.

Avin, C., Lotker, Z., Pasquale, F., Pignolet, Y. (2012). A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model. THEORETICAL COMPUTER SCIENCE, 453, 2-13 [10.1016/j.tcs.2011.12.066].

A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model

PASQUALE, FRANCESCO;
2012-01-01

Abstract

In this paper, we study the connectivity problem for wireless networks under the physical signal to interference plus noise ratio (SINR) model. Given a set of radio transmitters distributed in some area, we seek to build a directed strongly connected communication graph, and compute an edge coloring of this graph such that the transmitter-receiver pairs in each color class can communicate simultaneously. Depending on the interference model, more or fewer colors, corresponding to the number of frequencies or time slots, are necessary. We consider the interference model that compares the received power of a signal at a receiver to the sum of the strength of other signals plus ambient noise. The strength of a signal is assumed to fade polynomially with the distance from the sender, depending on the so-called path-loss exponent α. We show that, when all transmitters use the same power, the number of colors needed is constant in one-dimensional grids if α>1 as well as in two-dimensional grids if α>2. For smaller path-loss exponents and two-dimensional grids we prove upper and lower bounds in the order of O(logn) and Ω(lognloglogn) for α=2 and Θ(n2 α-1) for α<2, respectively. If nodes are distributed uniformly at random on the interval [0,1], a regular coloring of O(logn) colors guarantees connectivity, while Ω(loglogn) colors are required for any coloring. © 2011 Elsevier B.V. All rights reserved.
2012
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - INFORMATICA
English
Connectivity; Network capacity; Physical model; Signal to interference and noise ratio (SINR); Unit disk graphs; Theoretical Computer Science; Computer Science (all)
Avin, C., Lotker, Z., Pasquale, F., Pignolet, Y. (2012). A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model. THEORETICAL COMPUTER SCIENCE, 453, 2-13 [10.1016/j.tcs.2011.12.066].
Avin, C; Lotker, Z; Pasquale, F; Pignolet, Y
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
alpp_TCS12.pdf

solo utenti autorizzati

Licenza: Copyright dell'editore
Dimensione 547.53 kB
Formato Adobe PDF
547.53 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/184078
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact