On the θ-coverage and connectivity of large random networks

ABSTRACT

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 θ-coverage is found for wireless networks modeled as n points uniformly distributed in a unit square, with every node connecting to its φn nearest neighbors. A network is called θ-covered if every node, except those near the boundary, can find one of its φn nearest neighbors in any sector of angle θ. For all θ ∈ (0, 2π), if φn = (1 + δ) log 2π/2π-θ n, it is shown that the probability of θ-coverage goes to one as n goes to infinity, for any δ > 0; on the other hand, if φn = (1 - δ) log 2π/2π-θ n, the probability of θ-coverage goes to zero. This sharp characterization of θ-coverage is used to show, via further geometric arguments, that the network will be connected with probability approaching one if φn = (1 + δ) log2 n. Connections between these results and the performance analysis of wireless networks, especially for routing and topology control algorithms, are discussed.

REFERENCES

• 1: [1] L. Kleinrock and J. A. Silvester, "Optimum transmission radii for packet radio networks or why six is a magic number," in Proc. IEEE Nat. Telecommun. Conf., Dec. 1978, pp. 4.3.1-4.3.5.
• 2: [2] H. Takagi and L. Kleinrock, "Optimal transmission ranges for randomly distributed packet radio terminals," IEEE Trans. Commun., vol. 32, pp. 246-257, 1984.
• 3: [3] T. Hou and V. Li, "Transmission range control in multihop packet radio networks," IEEE Trans. Commun., vol. 34, pp. 38-44, 1986.
• 4: [4] R. Mathar and J. Mattfeldt, "Analyzing routing strategy NFP in multihop packet radio network on a line," IEEE Trans. Commun., vol. 43, pp. 977-988, 1995.
• 5: [5] E. N. Gilbert, "Random plane networks," J. SIAM, vol. 9, pp. 533-543, Dec. 1961.
• 6: [6] M. D. Penrose, "The longest edge of the random minimal spanning tree," Ann. Prob., vol. 7, no. 2, pp. 340-361, 1997.
• 7: [7] P. Gupta and P. R. 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. McEneany, G. Yin, and Q. Zhang, Eds. Boston, MA: Birkhauser, 1998, pp. 657-566.
• 8: Feng Xue , P. R. Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks, v.10 n.2, p.169-181, March 2004 [doi>10.1023/B:WINE.0000013081.09837.c0]
• 9: Peng-Jun Wan , Chih-Wei Yi, Asymptotic critical transmission radius and critical neighbor number for k-connectivity in wireless ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989461]
• 10: [10] A. Balister, B. Bollobas, A. Sarkar, and M. Walters, "Connectivity of random k-nearest neighbor graphs," Advances in Applied Probability, vol. 37, no. 1, pp. 1-24, 2005.
• 11: [11] R. Wattenhofer, L. Li, P. Bahl, and Y. M. Wang, "Distributed topology control for power efficient operation in multi-hop wireless ad hoc networks," in Proc. IEEE INFOCOM 2001, Apr. 2001, pp. 1388-1397.
• 12: Li Li , Joseph Y. Halpern , Paramvir Bahl , Yi-Min Wang , Roger Wattenhofer, Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.264-273, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384043]
• 13: [13] X.-Y. Li, "Topology control in wireless ad hoc networks," in Ad Hoc Networking, S. Basagni, M. Conti, S. Giordano, and I. Stojmenovic, Eds. Piscataway, NJ: IEEE Press, 2003.
• 14: Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564602]
• 15: [15] A. Yao, "On constructing minimum spanning trees in k-dimensional spaces and related problems," SIAM J. Comput., vol. 11, no. 4, pp. 721-736, 1982.
• 16: [16] X.-Y. Li, P.-J. Wan, and Y. Wang, "Power efficient and sparse spanner for wireless ad hoc networks," in Proc. IEEE Int. Conf. Comput. Commun. Netw. (ICCCN'01), 2001, pp. 564-567.
• 17: [17] P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Trans. Inf. Theory, vol. 46, pp. 388-404, Mar. 2000.
• 18: [18] L.-L. Xie and P. R. Kumar, "A network information theory for wireless communication: Scaling laws and optimal operation," IEEE Trans. Inf. Theory, vol. 50, pp. 748-767, 2004.
• 19: [19] M. Franceschetti, O. Dousse, D. Tse, and P. Thira, "Closing the gap in the capacity of random wireless networks," in Proc. IEEE Int. Symp. Inf. Theory (ISIT 2004), Chicago, IL, 27 Jun.-2 Jul. 2004, p. 438.
• 20: [20] M. Penrose, Random Geometric Graphs. Cambridge, U.K.: Cambridge University Press, 2003.
• 21: [21] H. Kesten, Percolation Theory for Mathematicians. Boston, MA: Birkhauser, 1982.
• 22: [22] R. Meester and R. Roy, Continuum Percolation. Cambridge, U.K.: Cambridge University Press, 1996.
• 23: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 24: [24] B. Bollobas, Random Graphs, second ed. Cambridge, U.K.: Cambridge University Press, 2001.
• 25: [25] G. Finn, "Routing and Addressing Problems in Large Metropolitan-Scale Internetworks," Inst. for Scientific Information, Tech. Rep. ISI Res. Rep. ISU/RR-87-180, 1987.
• 26: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 27: [27] R. Jain, A. Puri, and R. Sengupta, "Geographical routing using partial information for wireless ad hoc networks," IEEE Pers. Commun., pp. 48-57, Feb. 2001.
• 28: Fabian Kuhn , Roger Wattenhofer , Aaron Zollinger, Worst-Case optimal and average-case efficient geometric ad-hoc routing, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778447]
• 29: Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, The lit K-neigh protocol for symmetric topology control in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778433]
• 30: Santosh Kumar , Ten H. Lai , József Balogh, On k-coverage in a mostly sleeping sensor network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023735]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology; Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Design studies; Modeling techniques

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

General Terms:
Algorithms, Design, Performance

Keywords:
ad hoc networks, connectivity, coverage, random geometric graphs, sensor networks, topology control, transmission power control, wireless networks