Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

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

REFERENCES

• 1: N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, (second edition) 2000.
• 2: Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513811]
• 3: C. Bettstetter. On the connectivity of ad hoc networks. The Computer Journal, Special Issue on Mobile and Pervasive Computing, vol. 47, no. 4, pp. 432--447, 2004.
• 4: B. Bollobás. Random Graphs (2nd edition). Cambridge University Press, 2001.
• 5: B. Bollobás and V. Klee. Diameters of random bipartite graphs. Combinatorica 4 (1984) 7--19
• 6: Marek Chrobak , Joseph (Seffi) Naor , Mark B. Novick, Using Bounded Degree Spanning Trees in the Design of Efficient Algorihtms on Claw-Free Graphs, Proceedings of the Workshop on Algorithms and Data Structures, p.147-162, August 17-19, 1989
• 7: J. Deuschel and A. Pisztora, Surface order large deviations for high-density percolation. Probability Theory and Related Fields 104 (1996) 467--482.
• 8: Alon Efrat , Sariel Har-Peled, Guarding Galleries and Terrains, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science: Foundations of Information Technology in the Era of Networking and Mobile Computing, p.181-192, August 25-30, 2002
• 9: A. Efrat, S. Har-Peled, J. S. B. Mitchell. Approximation Algorithms for Two Optimal Location Problems in Sensor Networks. Broadnets 2005.
• 10: Alan M. Frieze , Michael Molloy, Splitting an expander graph, Journal of Algorithms, v.33 n.1, p.166-172, Oct. 1999 [doi>10.1006/jagm.1999.1023]
• 11: Ashish Goel , Sanatan Rai , Bhaskar Krishnamachari, Sharp thresholds For monotone properties in random geometric graphs, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007441]
• 12: G. Grimmett. Percolation. Springer-Verlag, 1989.
• 13: P. Gupta and P. Kumar. Critical power for asymptotic connectivity in wireless networks. in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming. (W.M. McEneaney, G. Yin, and Q. Zhang, Eds.) Birkhauser, Boston, 1998.
• 14: P. Gupta and P. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, vol. 46, no. 2, March 2000, pp. 388--404. Also: A correction to the proof of a lemma in 'The capacity of wireless networks.' IEEE Transactions on Information Theory, vol. 49, no. 11, November 2000, p. 3117.
• 15: G. Kalai and J. Matousek. Guarding galleries where every point sees a large area. Israel Journal of Math., 101:125--139, 1997.
• 16: Philip Klein , R. Ravi, A nearly best-possible approximation algorithm for node-weighted Steiner trees, Journal of Algorithms, v.19 n.1, p.104-115, July 1995 [doi>10.1006/jagm.1995.1029]
• 17: M. Mauve, J. Widmer, H. Hartenstein. A Survey on Position-Based Routing in Mobile Ad Hoc Networks. IEEE Network, Nov/Dec 2001.
• 18: Mobile Ad-hoc Networks (MANET) Charter, http://www.ietf.org/html.charters/manet-charter.html
• 19: Mathew D. Penrose, On k-connectivity for a geometric random graph, Random Structures & Algorithms, v.15 n.2, p.145-164, Sept.1999 [doi>10.1002/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G]
• 20: M. D. Penrose. Random Geometric Graphs, vol. 5 of Oxford Studies in Probability. Oxford University Press, 2003.
• 21: Gabriel Robins , Alexander Zelikovsky, Improved Steiner tree approximation in graphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.770-779, January 09-11, 2000, San Francisco, California, United States
• 22: E. Royer and C.-K. Toh. A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Personal Communications, 1999.
• 23: P. Valtr. Guarding galleries where no point sees a small area. Israel Journal of Mathematics, vol. 104, pp. 1--16, 1998.