Line-of-Sight Networks.pdf.pdf' (201.03 kB)

Download file# Line-of-Sight Networks

journal contribution

posted on 2007-03-01, 00:00 authored by Alan FriezeAlan Frieze, Jon Kleinberg, Ramamoorthi RaviRamamoorthi Ravi, Warren DebanyRandom geometric graphs have been one of the fundamental
models for reasoning about wireless networks: one places n
points at random in a region of the plane (typically a square
or circle), and then connects pairs of points by an edge if
they are within a fixed distance of one another. In addition
to giving rise to a range of basic theoretical questions, this
class of random graphs has been a central analytical tool in
the wireless networking community.
For many of the primary applications of wireless networks, however, the underlying environment has a large
number of obstacles, and communication can only take place
among nodes when they are close in space and when they
have line-of-sight access to one another — consider, for example, urban settings or large indoor environments. In such
domains, the standard model of random geometric graphs is
not a good approximation of the true constraints, since it is
not designed to capture the line-of-sight restrictions.
Here we propose a random-graph model component, as well an approximation question, in which we
seek to connect a set of given nodes in such an environment
by adding a small set of additional “relay” nodes.
both range limitations and line-of-sight constraints, and
we prove asymptotically tight results for k-connectivity.
Specifically, we consider points placed randomly on a grid
(or torus), such that each node can see up to a fixed
distance along the row and column it belongs to. (We
think of the rows and columns as “streets” and“avenues”
among a regularly spaced array of obstructions.) Further,
we show that when the probability of node placement is a
constant factor larger than the threshold for connectivity,
near-shortest paths between pairs of nodes can be found,
with high probability, by an algorithm using only local
information. In addition to analyzing connectivity and
k-connectivity, we also study the emergence of a giant