On the θ-coverage and connectivity of large random networks

被引:11
作者
Xue, Feng [1 ]
Kumar, P. R.
机构
[1] Intel Corp, Technol Lab, Santa Clara, CA 95052 USA
[2] Univ Illinois, Dept Elect & Comp Engn, Chicago, IL 60680 USA
[3] Univ Illinois, Coordinated Sci Lab, Chicago, IL 60680 USA
关键词
ad hoc networks; connectivity; coverage; random geometric graphs; sensor networks; topology control; transmission power control; wireless networks;
D O I
10.1109/TIT.2006.874384
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Wireless planar networks have been used to model wireless networks in a tradition that dates back to 1961 to the work of E. N. Gilbert. Indeed, the study of connected components in wireless networks was the motivation for his pioneering work that spawned the modern field of continuum percolation theory. Given that node locations in wireless networks are not known, random planar modeling can be used to provide preliminary assessments of important quantities such as range, number of neighbors, power consumption, and connectivity, and issues such as spatial reuse and capacity. In this paper, the problem of connectivity based on nearest neighbors is addressed. The exact threshold function for theta-coverage is found for wireless networks modeled as n points uniformly distributed in a unit square, with every node connecting to its 0, nearest neighbors. A network is called theta-covered if every node, except those near the boundary, can find one of its On nearest neighbors in any sector of angle theta. For all theta is an element of (0, 2 pi), if phi n = (1 + delta) log 2 pi/2 pi-0 n, it is shown that the probability of theta-coverage goes to one as goes to infinity, for any delta > 0; on the other hand, if phi(n) = (1 - delta) log 2 pi/2 pi-0 n, the probability of theta-coverage goes to zero. This sharp characterization of theta-coverage is used to show, via further geometric arguments, that the network will be connected with probability approaching one if phi(n) = (1 + delta.) log(2) n. Connections between these results and the performance analysis of wireless networks, especially for routing and topology control algorithms, are discussed.
引用
收藏
页码:2289 / 2299
页数:11
相关论文
共 30 条
  • [1] [Anonymous], 1982, PERCOLATION THEORY M
  • [2] [Anonymous], P IEEE NAT TEL C DEC
  • [3] Connectivity of random k-nearest-neighbour graphs
    Balister, P
    Bollobás, B
    Sarkar, A
    Walters, M
    [J]. ADVANCES IN APPLIED PROBABILITY, 2005, 37 (01) : 1 - 24
  • [4] BLOUGH D, 2003, P 4 ACM INT S MOB AD
  • [5] Bollobas B., 2001, Random Graphs, V21
  • [6] Finn G. G, 1987, ISURR87180 ISI
  • [7] Franceschetti M, 2004, 2004 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, PROCEEDINGS, P438
  • [8] RANDOM PLANE NETWORKS
    GILBERT, EN
    [J]. JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1961, 9 (04): : 533 - 543
  • [9] The capacity of wireless networks
    Gupta, P
    Kumar, PR
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2000, 46 (02) : 388 - 404
  • [10] GUPTA P, 1998, STOCHASTIC ANAL CONT, P657