Asymptotic connectivity in wireless ad hoc networks using directional antennas

ABSTRACT

Connectivity is a crucial issue in wireless ad hoc networks (WANETs). Gupta and Kumar have shown that in WANETs using omnidirectional antennas, the critical transmission range to achieve asymptotic connectivity is O(√logn/n) if n nodes are uniformly and independently distributed in a disk of unit area. In this paper, we investigate the connectivity problem when directional antennas are used. We first assume that each node in the network randomly beamforms in one beam direction. We find that there also exists a critical transmission range for a WANET to achieve asymptotic connectivity, which corresponds to a critical transmission power (CTP). Since CTP is dependent on the directional antenna pattern, the number of beams, and the propagation environment, we then formulate a non-linear programming problem to minimize the CTP. We show that when directional antennas use the optimal antenna pattern, the CTP in a WANET using directional antennas at both transmitter and receiver is smaller than that when either transmitter or receiver uses directional antenna and is further smaller than that when only omnidirectional antennas are used. Moreover, we revisit the connectivity problem assuming that two neighboring nodes using directional antennas can be guaranteed to beamform to each other to carry out the transmission. A smaller critical transmission range than that in the previous case is found, which implies smaller CTP.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: Ian F. Akyildiz , Xudong Wang , Weilin Wang, Wireless mesh networks: a survey, Computer Networks and ISDN Systems, v.47 n.4, p.445-487, 15 March 2005 [doi>10.1016/j.comnet.2004.12.001]
• 3: Romit Roy Choudhury , Nitin H. Vaidya, Deafness: A MAC Problem in Ad Hoc Networks when using Directional Antennas, Proceedings of the 12th IEEE International Conference on Network Protocols, p.283-292, October 05-08, 2004
• 4: Romit Roy Choudhury , Xue Yang , Ram Ramanathan , Nitin H. Vaidya, Using directional antennas for medium access control in ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570653]
• 5: H. Gossain, C. M. Cordeiro, D. Cavalcanti, and D. P. Agrawal, "The deafness problems and solutions in wireless ad hoc networks using directional antennas," in IEEE Workshop on Wireless Ad Hoc and Sensor Networks, Dallas, Texas, Nov. 2004.
• 6: Y. Ko, V. Shankarkumar, and N. Vaidya, "Medium access control protocols using directional antennas in ad hoc networks," in Proc. IEEE INFOCOM'00, Tel Aviv, Israel, Mar. 2000.
• 7: Vinay Kolar , Sameer Tilak , Nael B. Abu-Ghazaleh, Avoiding Head of Line Blocking in Directional Antenna, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks, p.385-392, November 16-18, 2004 [doi>10.1109/LCN.2004.30]
• 8: Thanasis Korakis , Gentian Jakllari , Leandros Tassiulas, A MAC protocol for full exploitation of directional antennas in ad-hoc wireless 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.778428]
• 9: P. Li, H. Zhai, and Y. Fang, "A directional MAC protocol for ad hoc networks," in Proc. IEEE Military Communications Conf. (Milcom'06), Washington, DC, Oct. 2006.
• 10: P. Li, H. Zhai, and Y. Fang, "Sdmac: Selectively directional mac protocol for wireless mobile ad hoc networks," ACM Wireless Networks, Oct. 31, 2007, Online.
• 11: A. Nasipuri, S. Ye, and R. Hiromoto, "A mac protocol for mobile ad hoc networks using directional antennas," in Proc. IEEE Wireless Communications and Networking Conf. (WCNC), Chicago, IL, Sep. 2000, vol. 3.
• 12: Mineo Takai , Jay Martin , Rajive Bagrodia , Aifeng Ren, Directional virtual carrier sensing for directional antennas in mobile ad hoc networks, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513823]
• 13: K.-K. Yap, W.-L. Yeow, M. Motani, and C.-K. Tham, "Simple directional antennas: Improving performance in wireless multihop networks," in Proc. IEEE INFOCOM'06, Barcelona, Spain, Apr. 2006.
• 14: P. Gupta and P. Kumar, "Critical power for asymptotic connectivity in wireless networks," Stochastic Analysis, Control, Optimization and Applications , A Volume in Honor of W. H. Fleming, pp. 547-566, 1998.
• 15: Pan Li , Chi Zhang , Yuguang Fang, Asymptotic Connectivity in Wireless Networks Using Directional Antennas, Proceedings of the 27th International Conference on Distributed Computing Systems, p.43, June 25-27, 2007 [doi>10.1109/ICDCS.2007.85]
• 16: Tatiana K. Madsen , Frank H. Fitzek , Ramjee Prasad , Gerrit Schulte, Connectivity Probability of Wireless Ad Hoc Networks: Definition, Evaluation, Comparison, Wireless Personal Communications: An International Journal, v.35 n.1-2, p.135-151, October 2005 [doi>10.1007/s11277-005-8745-7]
• 17: O. Dousse, F. Baccelli, and P. Thiran, "Impact of interferences on connectivity in ad hoc networks," in Proc. IEEE INFOCOM'03, San Francisco, CA, Apr. 2003.
• 18: P. Wan and C. Yi, "Asymptotic critical transmission ranges for connectivity in wireless ad hoc networks with bernoulli nodes," in Proc. IEEE WCNC, New Orleans, LA, Mar. 2005.
• 19: C. Yi, P. Wan, X. Li, and O. Frieder, "Asymptotic distribution of the number of isolated nodes in wireless ad hoc networks with bernoulli nodes," IEEE Trans. Commun., vol. 54, no. 3, pp. 510-517, Mar. 2006.
• 20: Paul Balister , Béla Bollobas , Amites Sarkar , Santosh Kumar, Reliable density estimates for coverage and connectivity in thin strips of finite length, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287863]
• 21: E. Kranakis, D. Krizanc, and E. Williams, "Directional versus omnidirectional antennas for energy consumption and k-connectivity of networks of sensors," in Proc. OPODIS, Grenoble, France, Dec. 2004.
• 22: Josep Díaz , Vishal Sanwalani , Maria Serna , Paul G. Spirakis, The chromatic and clique numbers of random scaled sector graphs, Theoretical Computer Science, v.349 n.1, p.40-51, 12 December 2005 [doi>10.1016/j.tcs.2005.09.050]
• 23: C. Bettstetter, C. Hartmann, and C. Moser, "How does randomized beamforming improve the connectivity of ad hoc networks?," in Proc. IEEE Int. Conf. Communications (ICC), Seoul, Korea, May 2005.
• 24: Su Yi , Yong Pei , Shivkumar Kalyanaraman, On the capacity improvement of ad hoc wireless networks using directional antennas, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778429]
• 25: Joseph C. Liberti , Theodore S. Rappaport, Smart Antennas for Wireless Communications: IS-95 and Third Generation CDMA Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1999
• 26: Ramakrishnan Janaswamy, Radiowave Propagation and Smart Antennas for Wireless Communications, Kluwer Academic Publishers, Norwell, MA, 2001
• 27: Ram Ramanathan, On the performance of ad hoc networks with beamforming antennas, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501426.501430]
• 28: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 29: E. Sevick, P. Monson, and J. Ottino, "Clustering and percolation in assemblies of anisotropic particles: Perturbation theory and monte carlo simulation," Phys. Rev. A, vol. 38, no. 10, pp. 5376-5383, Nov. 1988.
• 30: M. D. Penrose, "On a continuum percolation model," Adv. Appl. Probabil. , vol. 23, no. 3, pp. 536-556, 1991.
• 31: M. D. Penrose, "The longest edge of the random minimal spanning tree," Ann. Appl. Probabil., vol. 7, no. 2, pp. 340-361, 1997.
• 32: R. Meester and R. Roy, Continuum Percolation, Cambridge, U.K.: Cambridge Univ. Press, 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies; Modeling techniques

  E. Data
  E.4 CODING AND INFORMATION THEORY

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
asymptotic connectivity, critical transmission power, critical transmission range, directional antenna, wireless ad hoc networks