skip to main content
10.1145/1164717.1164755acmconferencesArticle/Chapter ViewAbstractPublication PagesmswimConference Proceedingsconference-collections
Article

Analytical study of connectivity in wireless multihop networks utilizing beamforming

Published:07 October 2006Publication History

ABSTRACT

In previous work, the effects of randomized beamforming, i.e., the strategy of every node in a wireless multihop network directing its antenna in a randomly chosen direction, on connectivity are studied by simulation. In this paper, we study some such effects analytically under similar but slightly simplified modeling assumptions. We begin by generalizing the notion of the threshold range for k-connectivity from the traditional Boolean network model to networks with arbitrary link attenuations. Then, for a network of uniformly distributed nodes with randomized beamforming, we derive analytically and evaluate numerically the degree distribution of a random node. Based on this, we apply a commonly used approximation to the probability that such a network is k-connected.We find that because the randomness caused by this strategy in the link attenuations shifts the network topology from being strictly a geometric random graph towards being a pure random graph, the k-connectivity probability of a network applying randomized beamforming can be approximated more accurately than that of a network with omnidirectional antennas. This added randomness also manifests itself as the increased variance of the node degree and the threshold attenuation range for k-connectivity. The main conclusion from our findings is that randomized beamforming cannot be said to strictly improve -- nor to degrade -- the connectivity of random wireless multihop networks.

References

  1. C. A. Balanis. Antenna theory. John Wiley & Sons, Inc., New York (NY), second edition, 1997.Google ScholarGoogle Scholar
  2. C. Bettstetter. On the connectivity of ad hoc networks. The Computer Journal, Special Issue on Mobile and Pervasive Computing, 47(4):432--447, 2004.Google ScholarGoogle Scholar
  3. C. Bettstetter, C. Hartmann, and C. Moser. How does randomized beamforming improve the connectivity of ad hoc networks? In Proceedings of IEEE International Conference on Communications (ICC), volume 5, pages 3380--3385, May 2005.Google ScholarGoogle ScholarCross RefCross Ref
  4. P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388--404, Mar. 2000. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. R. Hekmat and P. V. Mieghem. Study of connectivity in wireless ad hoc network with an improved radio model. In Proceedings of the 2nd Workshop on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt'04), Mar. 2004.Google ScholarGoogle Scholar
  6. H. Koskinen. A simulation-based method for predicting connectivity in wireless multihop networks. Telecommunication Systems, 26(2-4):321--338, June 2004.Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. P. Lassila, E. Hyytiä, and H. Koskinen. Challenges in Ad Hoc Networking: Fourth Annual Mediterranean Ad Hoc Networking Workshop, June 21-24, 2005, Île de Porquerolles, France, volume 197 of IFIP International Federation for Information Processing, chapter Connectivity properties of Random Waypoint mobility model for ad hoc networks, pages 159--168. Springer, Boston, Jan. 2006.Google ScholarGoogle Scholar
  8. M. D. Penrose. The longest edge of the random minimal spanning tree. Annals of Applied Probability, 7(2):340--361, 1997.Google ScholarGoogle ScholarCross RefCross Ref
  9. A. Spyropoulos and C. Raghavendra. Asympotic capacity bounds for ad-hoc networks revisited: the directional and smart antenna cases. In Proceedings of IEEE Global Telecommunications Conference (GLOBECOM), volume 3, pages 1216--1220, Dec. 2003.Google ScholarGoogle ScholarCross RefCross Ref
  10. A. Spyropoulos and C. Raghavendra. Capacity bounds for ad-hoc networks using directional antennas. In Proceedings of IEEE International Conference on Communications (ICC), volume 1, pages 348--352, May 2003.Google ScholarGoogle ScholarCross RefCross Ref
  11. R. Vilzmann, C. Bettstetter, D. Medina, and C. Hartmann. Hop distances and flooding in wireless multihop networks with randomized beamforming. In MSWiM '05: Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, pages 20--27, New York, NY, USA, 2005. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. S. Yi, Y. Pei, and S. Kalyanaraman. On the capacity improvement of ad hoc wireless networks using directional antennas. In MobiHoc '03: Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, pages 108--116, New York, NY, USA, 2003. ACM Press. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Analytical study of connectivity in wireless multihop networks utilizing beamforming

                Recommendations

                Comments

                Login options

                Check if you have access through your login credentials or your institution to get full access on this article.

                Sign in
                • Published in

                  cover image ACM Conferences
                  MSWiM '06: Proceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems
                  October 2006
                  406 pages
                  ISBN:1595934774
                  DOI:10.1145/1164717

                  Copyright © 2006 ACM

                  Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

                  Publisher

                  Association for Computing Machinery

                  New York, NY, United States

                  Publication History

                  • Published: 7 October 2006

                  Permissions

                  Request permissions about this article.

                  Request Permissions

                  Check for updates

                  Qualifiers

                  • Article

                  Acceptance Rates

                  MSWiM '06 Paper Acceptance Rate39of160submissions,24%Overall Acceptance Rate398of1,577submissions,25%

                PDF Format

                View or Download as a PDF file.

                PDF

                eReader

                View online with eReader.

                eReader