CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
Random 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 incorporating 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 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.
- Computer Systems
- Radio Communications