skip to main content
10.5555/1283383.1283487acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

Line-of-sight networks

Published: 07 January 2007 Publication History

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]
C. 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 and Computing (MobiHoc '02), pages 80--91, June 2002.
[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]
M. Chrobak, J. Naor, and M. Novick. Using bounded degree spanning trees in the design of efficient algorithms on claw-free graphs. In Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science Vol 382, pages 147--162.
[7]
J. Deuschel and A. Pisztora, Surface order large deviations for high-density percolation. Probability Theory and Related Fields 104 (1996) 467--482.
[8]
A. Efrat, S. Har-Peled. Locating Guards in Art Galleries. 2nd IFIP International Conference on Theoretical Computer Science 2002, 181--192.
[9]
A. Efrat, S. Har-Peled, J. S. B. Mitchell. Approximation Algorithms for Two Optimal Location Problems in Sensor Networks. Broadnets 2005.
[10]
A. M. Frieze and M. Molloy, Splitting an expander graph, Journal of Algorithms 33 (1999) 166--172.
[11]
A. Goel, S. Rai, and B. Krishnamachari. Sharp thresholds for monotone properties in random geometric graphs. ACM Symposium on Theory of Computing, 2004.
[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 N. Klein, R. Ravi: A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees. J. Algorithms 19(1): 104--115 (1995)
[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]
M. D. Penrose. On k-connectivity for a geometric random graph. Random Structures and Algorithms, vol. 15, no. 2, pp. 145--164, 1999.
[20]
M. D. Penrose. Random Geometric Graphs, vol. 5 of Oxford Studies in Probability. Oxford University Press, 2003.
[21]
G. Robins and A. Zelikovsky. Improved Steiner Tree Approximation in Graphs. In Proc. 10th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 770--779, 2000.
[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.

Cited By

View all
  • (2013)Connectivity in obstructed wireless networksProceedings of the fourteenth ACM international symposium on Mobile ad hoc networking and computing10.1145/2491288.2491306(157-166)Online publication date: 29-Jul-2013
  • (2012)Modeling and connectivity analysis in obstructed wireless ad hoc networksProceedings of the 15th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems10.1145/2387238.2387273(195-202)Online publication date: 21-Oct-2012
  • (2009)Line-of-sight networksCombinatorics, Probability and Computing10.1017/S096354830800933418:1-2(145-163)Online publication date: 1-Mar-2009
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
January 2007
1322 pages
ISBN:9780898716245
  • Conference Chair:
  • Harold Gabow

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

  • Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;
Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2013)Connectivity in obstructed wireless networksProceedings of the fourteenth ACM international symposium on Mobile ad hoc networking and computing10.1145/2491288.2491306(157-166)Online publication date: 29-Jul-2013
  • (2012)Modeling and connectivity analysis in obstructed wireless ad hoc networksProceedings of the 15th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems10.1145/2387238.2387273(195-202)Online publication date: 21-Oct-2012
  • (2009)Line-of-sight networksCombinatorics, Probability and Computing10.1017/S096354830800933418:1-2(145-163)Online publication date: 1-Mar-2009
  • (2009)Line-of-sight percolationCombinatorics, Probability and Computing10.1017/S096354830800931018:1-2(83-106)Online publication date: 1-Mar-2009
  • (2007)Communication problems in random line-of-sight ad-hoc radio networksProceedings of the 4th international conference on Stochastic Algorithms: foundations and applications10.5555/2392533.2392542(70-81)Online publication date: 13-Sep-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media