The routing capabilities of an interconnection network are strictly related to its bandwidth and latency characteristics, which are in turn quantifiable through the graph-theoretic concepts of expansion and diameter. This paper studies expansion and diameter of a family of subgraphs of the random geometric graph, which closely model the topology induced by the device discovery phase of Bluetooth-based ad hoc networks. The main feature modeled by any such graph, denoted as BT (r(n), c(n)), is the small number c(n) of links that each of the n devices (vertices) may establish with those located within its communi- cation range r(n). First, tight bounds are proved on the expansion of BT (r(n), c(n)) for the whole set of functions r(n) and c(n) for which connectivity has been established in previous works. Then, by leveraging on the expansion result, tight (up to a logarithmic additive term) upper and lower bounds on the diameter of BT (r(n), c(n)) are derived.
On the Expansion and Diameter of Bluetooth-like Topologies
PETTARIN, ALBERTO;PIETRACAPRINA, ANDREA ALBERTO;PUCCI, GEPPINO
2009
Abstract
The routing capabilities of an interconnection network are strictly related to its bandwidth and latency characteristics, which are in turn quantifiable through the graph-theoretic concepts of expansion and diameter. This paper studies expansion and diameter of a family of subgraphs of the random geometric graph, which closely model the topology induced by the device discovery phase of Bluetooth-based ad hoc networks. The main feature modeled by any such graph, denoted as BT (r(n), c(n)), is the small number c(n) of links that each of the n devices (vertices) may establish with those located within its communi- cation range r(n). First, tight bounds are proved on the expansion of BT (r(n), c(n)) for the whole set of functions r(n) and c(n) for which connectivity has been established in previous works. Then, by leveraging on the expansion result, tight (up to a logarithmic additive term) upper and lower bounds on the diameter of BT (r(n), c(n)) are derived.File | Dimensione | Formato | |
---|---|---|---|
ESA09.pdf
accesso aperto
Tipologia:
Preprint (submitted version)
Licenza:
Accesso libero
Dimensione
184.89 kB
Formato
Adobe PDF
|
184.89 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.