Transmission scheduling in ad hoc networks with directional antennas

ABSTRACT

Directional antennas can adaptively select radio signals of interest in specific directions, while filtering out unwanted interference from other directions. Although a couple of medium access protocols based on random access schemes have been proposed for networks with directional antennas, they suffer from high probability of collisions because of their dependence on omnidirectional mode for the transmission or reception of control packets in order to establish directional links. We propose a distributed receiver-oriented multiple access (ROMA) channel access scheduling protocol for ad hoc networks with directional antennas, each of which can form multiple beams and commence several simultaneous communication sessions. Unlike random access schemes that use on-demand handshakes or signal scanning to resolve communication targets, ROMA determines a number of links for activation in every time slot using only two-hop topology information. It is shown that significant improvements on network throughput and delay can be achieved by exploiting the multi-beam forming capability of directional antennas in both transmission and reception. The performance of ROMA is studied by simulations, and compared with a well-know static scheduling scheme that is based on global topology information.

REFERENCES

• 1: Lichun Bao , J. J. Garcia-Luna-Aceves, A new approach to channel access scheduling for Ad Hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.210-221, July 2001, Rome, Italy [doi>10.1145/381677.381698]
• 2: I. Chlamtac and A. Lerner. Fair algorithms for maximal link activation in multihop radio networks. IEEE Transactions on Communications, 35(7):739--46, Jul. 1987.
• 3: I. Cidon , M. Sidi, Distributed Assignment Algorithms for Multihop Packet Radio Networks, IEEE Transactions on Computers, v.38 n.10, p.1353-1361, October 1989 [doi>10.1109/12.35830]
• 4: M. Cooper and M. Goldburg. Intelligent Antennas: Spatial Division Multiple Access. Annual Review of Communications, pages 999--1002, 1996.
• 5: A. Ephremides and T.V. Truong. Scheduling broadcasts in multihop radio networks. IEEE Transactions on Communications, 38(4):456--60, Apr. 1990.
• 6: S. Even, O. Goldreich, S. Moran, and P. Tong. On the NP-completeness of certain network testing problems. Networks, 14(1):1--24, Mar. 1984.
• 7: Y.B. Ko, V. Shankarkumar, and N.H. Vaidya. Medium access control protocols using directional antennas in ad hoc networks. In Proceedings of IEEE Conference on Computer Communications (INFOCOM), volume 1(3), pages 13--21, Tel Aviv, Israel, Mar. 26-30 2000.
• 8: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 9: A. Nasipuri, S. Ye, J. You, and R.E. Hiromoto. A MAC Protocol for Mobile Ad Hoc Networks Using Directional Antennas. In Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), Chicago, IL, Sep. 23-28 2000.
• 10: S.L. Preston, D.V. Thiel, T.A. Smith, S.G. O'Keefe, and J.W. Lu. Base-station tracking in mobile communications using a switched parasitic antenna array. IEEE Transactions on Antennas and Propagation, 46(6):841--4, Jun. 1998.
• 11: S. Ramanathan, A unified framework and algorithm for channel assignment in wireless networks, Wireless Networks, v.5 n.2, p.81-94, March 1999 [doi>10.1023/A:1019126406181]
• 12: 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]
• 13: R. Ramaswami and K.K. Parhi. Distributed scheduling of broadcasts in a radio network. In Proceedings of IEEE Conference on Computer Communications (INFOCOM), volume 2, pages 497--504, Ottawa, Ont., Canada, Apr. 23-27 1989. IEEE Comput. Soc. Press.
• 14: J. Razavilar, F. Rashid-Farrokhi, and K.J.R. Liu. Software radio architecture with smart antennas: a tutorial on algorithms and complexity. IEEE Journal on Selected Areas in Communications, pages 662--76, Apr. 1999.
• 15: 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]
• 16: V. Voipio and P. Vainikainen. Narrowbeam cylindrical antenna array with sparse antenna spacing. In 48th IEEE Vehicular Technology Conference, volume 1, pages 465--9, Ottawa, Ont., Canada, May 18-21 1998.
• 17: J. Ward and Jr. Compton, R.T. High throughput slotted ALOHA packet radio networks with adaptive arrays. IEEE Transactions on Communications, 41(3):460--70, Mar. 1993.
• 18: J.H. Winters. Smart antennas for wireless systems. IEEE Personal Communications, 5(1):23--7, Feb. 1998.
• 19: J. Zander. Slotted ALOHA multihop packet radio networks with directional antennas. Electronics Letters, 26(25):2098--100, Dec. 6 1990.
• 20: C. Zhu and M.S. Corson. A five-phase reservation protocol (FPRP) for mobile ad hoc networks. In Proceedings of IEEE Conference on Computer Communications (INFOCOM), volume 1, pages 322--31, San Francisco, CA, USA, Mar. 29-Apr. 2 1998.

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

General Terms:
Algorithms

Keywords:
ad hoc networks, channel access scheduling, directional antenna, multi-beam adaptive array (MBAA)