Line-of-Sight Networks

被引:12
作者
Frieze, Alan [1 ]
Kleinberg, Jon [2 ]
Ravi, R. [3 ]
Debany, Warren [4 ]
机构
[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA
[2] Cornell Univ, Dept Comp Sci, Ithaca, NY 14853 USA
[3] Carnegie Mellon Univ, Tepper Sch Business, Pittsburgh, PA 15213 USA
[4] USAF, Res Lab, RIG, Informat Grid Div, Rome, NY 13441 USA
基金
美国国家科学基金会;
关键词
GUARDING GALLERIES; POINT SEES; CONNECTIVITY;
D O I
10.1017/S0963548308009334
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 mother. 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 analysing 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.
引用
收藏
页码:145 / 163
页数:19
相关论文
共 25 条
[1]  
Alon N., 2004, PROBABILISTIC METHOD
[2]  
[Anonymous], 1999, PERCOLATION
[3]  
[Anonymous], 2003, OXFORD STUDIES PROBA
[4]  
[Anonymous], 1999, SYS CON FDN
[5]  
[Anonymous], MOBILE AD HOC NETWOR
[6]   On the connectivity of Ad hoc networks [J].
Bettstetter, C .
COMPUTER JOURNAL, 2004, 47 (04) :432-447
[7]  
BETTSTETTER C, 2002, P 3 ACM INT S MOB AD, P80, DOI DOI 10.1145/513800.513811
[8]  
BOLLOBAS B, 2000, RANDOM GRAPHS
[9]  
CHROBAK M, LECT NOTES COMPUTER, V382, P147
[10]  
Deuschel JD, 1996, PROBAB THEORY REL, V104, P467, DOI 10.1007/s004400050031