Prepared for Prof. Javed I. Khan
Department of Computer Science, Kent State University
Date: November 2003
As wireless ad hoc networking becomes more ubiquitous,
omnidirectional antennas currently in use may limit throughput due to
1) collisions, 2) waiting for the network to become free of traffic,
and 3) the hidden and exposed terminal problems. In addition to
decreased throughput, battery life (and associated LAN lifetime) will
be reduced. Directional antennas and some associated algorithms can
reduce these problems. Some well researched and some interesting
alternative solutions to these problems are described.
As wireless ad hoc networks become more popular, interference from neighboring nodes becomes a more severe problem, reducing available bandwidth and throughput to all nodes. Directional antennas have recently been investigated for increasing the throughput of ad hoc wireless networks. Directional antennas can be grouped into several categories, each of which has it’s own benefits and set of problems.
Classic Problems of Wireless Networking
The two classic problems of wireless networking are the hidden terminal problem and the exposed terminal problem. Each research area should solve these problems as part of their solution to directional antenna improvements to wireless ad hoc networking. Each research paper discussed below which solved the hidden and exposed terminal problem is discussed below in the Research section.
Fig 1: Hidden and Exposed Terminal Problem
Hidden Terminal Problem – Nodes 1 and 3 are in range of node 2, but nodes 1 and 3 are not in range with each other. Node 3 is communicating with node 2 at the time that node 1, the hidden terminal, initiates a communication with node 2(node 1 cannot detect that node 2 is receiving data from node 3) which disrupts the ongoing communication from node 3.
Exposed Terminal Problem – Node 0 and 1 are communicating, as are node 3 and 4. Node 2, the exposed terminal, cannot initiate or receive a communication with any other node until all nodes in its range (node 1 and 3) are quiescent.
Switched beam vs electronically steerable (beamforming) (fixed beam width vs variable min beam width)
Switched Beam – A directional antenna array which can only be directed in a fixed number of directions, usually in 0 to 30 deg increments. This may be accomplished by switching to different physical antennas or antenna combinations. An advantage to switched beam is simplicity and reduced time to determine direction as well as being less sensitive to node movement.
Electronically Steerable (Beamforming) – A directional antenna array which can be directed in any direction by applying signals to each antenna at different phase angles to each other so that the sum of the signals in all directions is the sum of all radiated power from all antennas. For example, with two antennas, the sum in some directions is a null while in other directions is twice the power of each antenna. By applying power in phase to the two antennas, the total radiation is perpendicular to the line of the antennas, while applying the power to the two antennas 90 deg out of phase makes the total radiation parallel to the line of the antennas. Power can be applied at any phase angle to obtain beams in any direction. An advantage to electronically steering antennas is that the power level may be reduced since the lobe is directed at the sending and receiving nodes by the receiving and sending nodes respectively saving battery power and prolonging LAN lifetime. A disadvantage is that determining the angle which to steer the beam is complex and expensive.
Fig 2a Antenna power applied in phase Fig 2b Antenna power applied 90 deg out of phase
Single beam vs multiple simultaneous beams (and if simultaneous, then on both send and receive or only one)
Single Beam – Only one beam sector is active at one time. An advantage is simplicity.
Multi Beams – More than one sector is active at one time. An advantage is increased throughput.
Fig 3a Single Beam Fig 3b Multi Beam
Separate data and control channels vs same data and control channel (single channel vs multi channel)
Separate Data and Control Channel – Control channel assigned to a separate single frequency while the data channel remains channel hopping. An advantage is used in one of the research papers discussed below in the Research section is that a separate channel may be used to explicitly indicate that the data channel is busy, reducing collisions from hidden terminals or from non hidden terminals which happen to be ready to transmit at the same time.
Same Data and Control Channel – Both data and control share the same frequency hopping scheme. An advantage is simplicity. An advantage is simplicity.
RTS/CTS, omnidirectional vs directional (multicast vs unicast)
RTS and CTS (request to send and clear to send) may be either directional or omnidirectional or in combination (i.e.: RTS directional and CTS omnidirectional or RTS omnidirectional and CTS directional). An advantage of omnidirectionally sending RTS and CTS is simplicity and the use of RTS and CTS signals to determine direction. An advantage of directionally sending RTS and CTS is lack of interference with other nodes. In one research paper discussed below in the Research section, the RTS is sent omnidirectionally to assist the receiving node to determine direction and the CTS is sent directionally because the direction of the sending node was determined when it received the RTS, reducing interference while CTS is being sent.
Synchronized vs asynchronous
Synchronized – The clocks of all nodes are synchronized, either using a master clock such as that associated with GPS or by radio signal from a designated master. Nodes are time driven. An advantage as pointed out in one paper discussed in the Research section below is that by using explicit busy signals during the signaling time, nodes hearing the busy signal will be quiescent during the data transmit time, resulting in increased throughput when data channels are heavily loaded.
Asynchronous – The clocks of nodes are not synchronized, each node is event driven. An advantage is simplicity.
Listening for busy channel vs explicit busy tone
Listening – A node wanting to communicate can listen to determine that the channel is not busy before transmitting. An advantage is simplicity.
Explicit Busy Tone – Two nodes wanting to communicate can each transmit a busy tone to all nodes within range so that all nodes will know that there exists a node within its range that is using the channel. An advantage as pointed out in one paper discussed in the Research section below (and discussed in Synchronized above) is that by using explicit busy signals during the signaling time, nodes hearing the busy signal will be quiescent during the data transmit time, resulting in increased throughput when data channels are heavily loaded.
Constant energy beam vs constant overall energy (sink energy to beams not used, or reduce power to one beam vs putting all of the omnidirectional power into one beam)
Constant Energy Beam – Each sector in a switched beam receives the same amount of power. If the antenna array is transmitting omnidirectionally, each sector receives power p. While transmitting in one direction, the single sector receives power p. This can be done by either terminating antennas not being used in a dummy load (sinking the power), or reducing the power applied from the transmitter to the one sector. An advantage is simplicity. A disadvantage, for the dummy terminated antennas, is wasted power and decreased battery life.
Constant Overall Energy – If an antenna array is transmitting omnidirectionally with power p, then switches to directionally transmitting in one sector, all of the transmitter power may be switched to the one sector, so that the sector receives np in an n sector array. An advantage is increased range. A disadvantage is increased interference with other communicating nodes.
Table 1: A comparison of approaches taken by research groups
|Solves Hidden & Exposed Terminal||Beam Switching vs Beamforming||Single vs Multiple Beams||Separate vs Same Data and Control Channels||RTS/CTS Multicast vs Unicast||Synchronous vs Asynchronous Clocks||Listening for Busy vs Explicit Busy Tone||Constant Energy Beam vs Constant Overall Energy|
|Busy Tone Based Protocol ||Solves both with Busy Tone||Beam Switched||Single (Multiple proposed but not explored)||Separate Channels for Transmit Busy, Receive Busy and Spread Spectrum data||RTS Multicast, CTS Unicast||Asynchronous||Explicit||Constant Energy Beam|
|Power Efficient Broadcast Routing ||Not considered in this paper||Both||Both are investigated||Same Channel||Not discussed in this paper||Implicitly Asynchronous||Listening||Constant Energy Beam (and other energy reduction techniques)|
|Energy Efficient Communications  (energy reduced by shortest time routing alg)||Mentioned briefly, not completely solved||Beam Switched||Single Beam||Implicitly Same Channel||Not discussed in this paper||Implicitly Asynchronous||Implicitly Listening||N/A, variable energy, min required to reach destination|
|Modestly Directional Communications ||Solves both reducing exponential backoff using synchronous||Beam Switched||Multiple Beams||Same Channel (control and data are time multiplexed)||N/A, synchronous used in lieu of RTS/CTS||Synchronous||N/A, DSUMA protocol for contention solution||Constant Energy Beam|
|Performance Comparison of Smart Antenna Techniques ||Not considered in this paper||Both, comparison of these two is the subject of this paper||Single Beam||Same Channel||RTS/CTS Unicast briefly mentioned||Implicitly Asynchronous||Not discussed, implied send RTS when ready||Constant Energy Beam|
|Space Division Multiple Access ||Solves hidden terminal only||Both, comparison of these two is addressed in this paper||Multiple Beams||Same Channel||RTS/CTS Multicast||Asynchronous||Active listening – explicitly sends RTR (ready to receive)||Implicit Constant Energy Beam|
|Comparison of Omnidirectional and Directional MAC Protocols ||Both, compares MAC protocols’ solution to these problems||Beam Switched||Single Beam||Both, compares protocols||Both, compares protocols||Asynchronous for all protocols compared||Both, compares protocols||Constant Energy Beam|
|Link Establishment with Smart Antennas ||Solves both when using RTS/CTS||Beamforming||Single Beam||Implicitly Same Channel||Unicast RTS, compares Unicast and Multicast CTS||Asynchronous||Listening||Constant Overall Energy to increase range and reduce hops|
A Busy Tone Based Protocol
Unlike the research in most papers reviewed, the approach taken to avoiding collisions with directional antennas in  is to use a Dual Busy Tone Multiple Access (DBTMA) protocol. This protocol uses RTS and CTS to turn on busy tones until the transmissions are complete. A node not involved with the connection hears the busy tone, and defers its receive and transmit until the connection is terminated. There are multiple channels used with a single frequency for each, one for control, one for Busy Tone Transmit (BTT), one for Busy Tone Receive (BTR), and spread spectrum for data. The busy tones prevent nodes within range from transmitting while the connection is active, reserving the channel for the active nodes in both directions.
When a node has data to transmit, it determines if the BTR signal is present on the BTR channel, if not, the intended receiver is not busy receiving data from a hidden source, then sends the RTS frame to the receiver. When the receiver receives the RTS frame, it senses for BTT on the BTT channel to make sure that the data that it is about to receive will not collide with a nearby ongoing data transmission. If BTT is not no the BTT channel, the receiver replies with a CTS frame and turns on BTT until the data transmission is complete. When the transmitting node receives the CTS, it begins sending data and turns on BTT until it completes sending data.
The antenna used is beam switched directional antenna. RTS is transmitted omnidirectionally. The receiving node uses the receipt of the RTS to determine the direction of the transmitting node and replies with the CTS using the appropriate sector.
The authors propose to use directional busy tones in order to enable simultaneous data transmissions, however the do not explore this idea in this paper.
Using a mesh topology in their simulation, the authors found that the throughput nearly doubled using directional antennas on both the transmit and receive nodes as compared to omnidirectional antennas on either the transmit or receive or both nodes.
Power Efficient Broadcast Routing
The investigation focus in  is to reduce total transmit power when the directional antenna beamwidth becomes very small. The power reduction is applied to different classes of antennas. The authors investigate the asymptotic convergence of routing algorithm trees. The authors also present a dynamic programming solution to optimize beam assignments a switched beam antenna system.
Power reduction by beam angle reduction with a single beam adaptive array is explored. The beam angle can be any arbitrary width as long as it is not less than the minimum beamwidth. Beam power is then adjusted so that any child in the routing tree is covered with the minimum amount of power needed to reach the child. If no child exists, then that node is assigned zero power. With a multi beam antenna, the problem of finding the minimum power for beams is presented as a dynamic programming solution.
The results show that a minimum weight spanning tree produced the most energy savings when the angular span of the beam was in the range of 0 to 30 deg
Energy Efficient Communications
In , all nodes are assumed to use a single directional antenna. First, the shortest cost routes are calculated. Then the total time each link is in use to transmit the data in that link is calculated. Next, nodes transmissions are scheduled to minimize the total time it takes for all possible transmitter receiver pairs to exchange data. The calculations are performed as max weight matching in a graph. The algorithm is adapted to a distributed topology.
Simulations are performed showing that the power savings are proportional to the antenna gain and an additional savings of 10% to 45% is saved by the routing algorithm. Power savings are also proportional to beam width. Some rather liberal assumptions are made, such as assuming the power in secondary lobes are negligible and the antenna efficiency is 100%, then the results can be seen to reduce power but by lesser amounts than shown.
Modestly Directional Communication
In , the authors investigate the effect of directional antennas on network capacity by allowing more simultaneous transmissions to occur on multihop networks. They propose using a Directional Synchronous Unscheduled Multiple Access (DSUMA) protocol, avoiding some of the pitfalls associated with asynchronous networks. The authors introduce the concepts of muteness (similar to the effects of the exposed terminal problem) and deafness (similar to the effects of the hidden terminal problem) to describe problems associated with asynchronous networks.
By requiring a time structure so that transmissions are performed at known begin and end times, nodes know when another node can respond rather than randomly discovering this information as in an asynchronous model. Since transmissions complete during the designated time slot, exponential backoff needed in asynchronous networks is avoided, making for a much more efficient congestion avoidance scenario. Since there is a time structure, the system clocks of nodes must be synchronized, which can be by GPS or radio signals. Since any node may be rotated, the MAC is provided with a compass input to reorient the directional antenna table to the new orientation of the node.
All signaling in the DSUMA protocol occur omnidirectionally. In the DSUMA protocol, there are three phases: a reduction phase, a promotion phase and a second reduction phase. In each reduction phase, there are a number of contention slots immediately followed by echo slots. Nodes not in contention, when hearing a signal in a contention slot, will relay the signal in an echo slot on all sectors of its antenna, allowing nodes to detect the presence of hidden terminals and eliminates muteness and deafness. Any contending node hearing a signal in an echo slot will discontinue contending for the channel until the transmission on that channel is complete. This process is repeated until each contention echo slot pair is satisfied. After the last contention echo slit pair is complete, any node which is still a contender obtains access to the channel. All contenders who won the channel transmit in the direction in which they won the channel. All non winners that hear the signal, as well as the winners, broadcast a signal in the echo slot. Nodes that still have data to send and did not hear a signal in either the promotion or echo slot get promoted to contender status. Then the second round of reduction follows.
A 10 x 10 wraparound array of nodes was used for simulation. It was found that increasing the number of sectors per node antenna enabled more simultaneous winners. At very low node densities, there was about 30 – 50% increase in the average number of winners, while at higher densities (using 16 sector antennas) the gain as about 10 times. It is interesting to note that, contrary to intuition, higher densities produce more winners of channel access. It was also found that the probability of collision decreased dramatically as the number of contention slots per phase increased, and the number of antenna sectors per node had virtually no effect on the probability of collision.
Performance Comparison of Smart Antenna Techniques
In , the authors compare switched beam antennas with beamforming. Beamforming algorithms steer the main lobe of a beam in the direction of the user and steer nulls in the direction of the interfering signal. Even though beamforming requires a training sequence (overhead), bit error rate is reduced, collisions are detected without having to perform elaborate error detection, training is embedded in the RTS/CTS, and enormous gains in throughput were obtained by creating of spatial channels at the nodes using smart antennas.
Space Division Multiple Access
In , the authors used directional antennas proposed a MAC layer protocol that uses Space Division Multiple Access, directional reception to receive more than one packet from transmitters in different sectors. Their results showed very large improvements in throughput using this simultaneous reception of data. This was done asynchronously so the protocol is simple and easily deployed on a range of nodes. Parallelism is only used in reception, not in transmission. However, the cost is high, so should be considered for critical applications such as Future Combat System, critical surveillance mission or disaster relief missions.
A Comparison of Omnidirectional and Directional MAC Protocols
The authors in  compare 4 omnidirectional and 4 directional MAC protocols. The protocols compared are 802.11, MAC/DA1, MAC/DA2, MAC/DA2ACK, MACA, MACAW, FAMA, DBTMA, DBTMA/DA. Each protocol is analyzed for effectiveness of spatial reuse of MAC protocols. The protocols with the most effective spatial reuse were MAC/DA1 and DBTMA/DA, both of which are directional protocols.
Simulation MATLAB & OPNET
In , the author, while investigating signaling mechanisms forming extended links using the network layer, used both MATLAB and OPENT for simulations. Methods for implementing phased array antennas including circular arrays allowing beamforming and null steering to be simulated in OPNET were developed. During this process, an interface was developed that allowed libraries developed in MATLAB to be directly used in OPNET.
Many researchers use beam switching antennas for their simplicity. However, the authors in  found advantages to beamforming antenna algorithms. Many researchers use asynchronous systems for their simplicity; however the authors in  found advantage for a synchronous system. Many researchers use implicit busy discovery and its associated exponential backoff for access control, however, in , the authors found an advantage to using explicit busy signals.
There are many researchers who found that a reduction in energy use could be achieved when compared to omnidirectional antennas.
Almost all research compared a particular version of antenna steering, MAC protocol, etc for directional antennas to omnidirectional antennas. Each found a gain in power reduction, throughput, reduced collisions, etc. Research needs to be done to directly compare the results where others found advantage when comparing to omnidirectional antennas to each other using directional antennas. This was done in  on a small scale, however, to find which protocols perform better will require direct comparison of many protocols using directional antennas.
Research Papers for More Information on This Topic.
 Zhuochuan Huang, Chien-Chung Shen, Chavalit Srisathapornphat, and Chaiporn Jaikaeo. . “A Busy-Tone Based Directional MAC Protocol For Ad Hoc Networks” In Proceedings of IEEE MILCOM, Anaheim, California, October 7-10 2002. http://alfalfa.cis.udel.edu:8080/refs/papers/huang02busytone.pdf
 Intae Kang and Radha Poovendran, “Power-Efficient Broadcast Routing in Adhoc Networks Using Directional Antennas: Technology Dependence and Convergence Issues” UWEETR-2003-0015, UWEE Technical Report Series https://www.ee.washington.edu/techsite/papers/documents/UWEETR-2003-0015.pdf
 Akis Spyropoulos (University of Southern California), Cauligi Raghavendra (University of Southern California) “Energy Efficient Communications in Ad Hoc Networks Using Directional Antennas”, INFOCOM 2002 http://www.ieee-infocom.org/2002/papers/289.pdf
 Kevin Grace, John Stine and Robert Durst, “An Approach For Modestly Directional Communications In Mobile Ad Hoc Networks”, In Proceedings of 12th International Conference on Computer Communications and Networks (ICCCN 2003), Dallas, Texas, October 20--22 2003.
 Rajesh Radhakrishnan, Dhananjay Lal, James Caffery Jr., and Dharma P. Agrawal, “Performance Comparison of Smart Antenna Techniques for Spatial Multiplexing in Wireless Ad Hoc Networks” in Proceedings of the Fifth International Symposium on Wireless Personal Multimedia Communications, pp 614-619, Oct. 2002. http://www.ececs.uc.edu/~dlal/sat_wahn.pdf
 Dhananjay Lal, Rishi Toshniwal, Rajesh Radhakrishnan, Dharma P. Agrawal and James Caffery, Jr., “A Novel MAC Layer Protocol for Space Division Multiple Access in Wireless Ad Hoc Networks” Proceedings of IEEE Conference on Computer Communications and Networks (ICCCN ) 2002, pp 421-428, 2002. http://www.ececs.uc.edu/~dlal/ic3n.pdf
 Zhuochuan Huang, and Chien-Chung Shen, “A Comparison Study of Omnidirectional and Directional MAC Protocols for Ad Hoc Networks” In Proceedings of IEEE GLOBECOM 2002, Taipei, Taiwan, Nov. 17-21 2002. http://alfalfa.cis.udel.edu:8080/refs/papers/huang02comparison.pdf
 Vikram Dham, “Link Establishment in Ad Hoc Networks Using Smart Antennas”, Thesis submitted to the Faculty of the Virginia Polytechnic Institute and State University in partial fulfillment of the requirements for the degree of Master of Science in Electrical Engineering Jan. 15, 2003 http://scholar.lib.vt.edu/theses/available/etd-05072003-180228/unrestricted/etd.pdf
 Chao-Kai Wen, Yeong-Cheng Wang, and Jiunn-Tsair Chen, “An Adaptive Spatio-Temporal Coding Scheme for Indoor Wireless Communication” 2003, IEEE Journal On Selected Areas In Communications, Vol. 21, No. 2, February 2003,
 G. J. Foschini and M. J. Gans, “On limits of wireless communications in a fading environment when using multiple antennas”, in Wireless Personal Communication. Norwell, MA: Kluwer, 1998, pp. 311–335. http://www1.bell-labs.com/project/blast/wpc-v6n3.pdf
 V. Tarokh, N. Seshadri, and A. R. Calderbank, “Space–time codes for high-data rate wireless communication: Performance criterion and code construction” IEEE Trans. Inform. Theory, vol. 44, pp. 744–765, Mar. 1998. http://www.mast.queensu.ca/~math800/papers/TrkhSsdCldb_IT98.pdf
 A. Paulraj and G. B. Papadias, “Space–time processing for wireless communications” IEEE Signal Processing Mag., vol. 14, pp. 49–83, Nov. 1997.
 G. J. Foschini, “Layered space–time architecture for wireless communication in a fading environment when using multielement antennas” Bell Labs Tech. J., pp. 41–59, Autumn 1996.
 Thushara D. Abhayapala 1 , Rodney A. Kennedy, and Jaunty T.Y. Ho “On capacity of multi-antenna wireless channels: Effects of antenna separation and spatial correlation” 3rd AusCTW, Canberra, Australia, Feb. 4–5, 2002 http://www.rsise.anu.edu.au/~thush/publications/capacity.pdf
 R. Ertel, P. Cardieri, K. W. Sowerby, T. R. Rapport, and J. H. Reed, “Overview of spatial channel models for antenna array communication systems” IEEE Personal Commun., vol. 5, pp. 10–22, Feb. 1998. http://bwrc.eecs.berkeley.edu/Classes/EE225C/Papers/Ertel_98.pdf
 Zhuochuan Huang, Chien-Chung Shen, Chavalit Srisathapornphat, and Chaiporn Jaikaeo. “Topology Control for Ad hoc Networks with Directional Antennas” In Proceedings of 11th International Conference on Computer Communications and Networks (ICCCN 2002), Miami, Florida, October 14--16 2002 http://alfalfa.cis.udel.edu:8080/refs/papers/huang02topology.pdf
 Chaiporn Jaikaeo, and Chien-Chung Shen. “Multicast Communication in Ad hoc Networks with Directional Antennas” In Proceedings of 12th International Conference on Computer Communications and Networks (ICCCN 2003), Dallas, Texas, October 20--22 2003. http://alfalfa.cis.udel.edu:8080/refs/papers/jaikaeo03multicast.pdf
 S. Bandyopadhyay, K. Hasuike, S. Horisawa, S. Tawara, “An Adaptive MAC Protocol for Wireless Ad Hoc Community Network (WACNet) Using Electronically Steerable Passive Array Radiator Antenna” in Proc. of the IEEE GLOBECOM2001, 2001 http://www.gta.ufrj.br/~myrna/art28.ZIP
Univ of Deleware, Newark, NJ http://www.cis.udel.edu/~degas/
Univ of Washington, Seattle, WA https://www.ee.washington.edu/research/wit/comm-network/Comun.htm
Univ of Southern Calif, LA http://www.usc.edu/dept/engineering/eleceng/Adv_Network_Tech/
MITRE Corp http://www.mitre.org/
Univ of Cincinnati, OH http://www.ececs.uc.edu/~wsrl/wireless_links.htm
VPI, Blacksburg, VA http://antenna.ece.vt.edu/
Lucent Technologies, Bell Labs, Crawford Hill, NJ & Holmdel, NJ http://www.bell-labs.com/research/
ATR Adaptive Communications Research Lab, Kyoto, Japan http://www.acr.atr.co.jp/acr/top-e.html
Other Relavant Groups
Center for Wireless Communication links to wireless research groups: http://cwc.ucsd.edu/resources.html