Technological advances, coupled with the flexibility and mobility of wireless systems, are the driving force behind the Anyone, Anywhere, Anytime paradigm of networking. At the same time, we see a convergence of the telephone, cable and data networks into a unified network that supports multimedia and real-time applications like voice and video in addition to data. Medium access control protocols define rules for orderly access to the shared medium and play a crucial role in the efficient and fair sharing of scarce wireless bandwidth. The nature of the wireless channel brings new issues like location-dependent carrier sensing, time varying channel and burst errors. Low power requirements and half duplex operation of the wireless systems add to the challenge. Wireless MAC protocols have been heavily researched and a plethora of protocols have been proposed. Protocols have been devised for different types of architectures, different applications and different media. This survey discusses the challenges in the design of wireless MAC protocols, classifies them based on architecture and mode of operation, and describes their relative performance and application domains in which they are best deployed. lhe ability to communicate with anyone on the planet from anywhere on the planet has been mankind's dream for a long time. Wireless is the only medium that can enable such untethered communication. With the recent advances in VLSI and wireless technologies, it is now possible to build high-speed wireless systems that are cheap as well as easy to install and operate. However, the wireless medium is a broad cast medium, and therefore multiple devices can access the medium at the same time. Multiple simultaneous transmis sions can result in garbled data, making communication impossible. A medium access control (MAC) protocol moder ates access to the shared medium by defining rules that allow these devices to communicate with each other in an orderly and efficient manner. MAC protocols therefore play a crucial role in enabling this paradigm by ensuring efficient and fair sharing of the scare wireless bandwidth. Wireless MAC proto cols have been studied extensively since the 1970s. The initial protocols were developed for data and satellite communica tions. We are now witnessing a convergence of the telephone, cable and data networks into a single unified network that supports multimedia and real-time applications like voice and video in addition to data. The multimedia applications require delay and jitter guarantees from the network. This demand of the network is known as the Quality of Service (QoS) guaran tee. These requirements have led to novel and complex MAC protocols that can support multimedia traffic. This article surveys the various MAC protocols that have been proposed in the literature and compares them based on architecture (MAC co-ordination, duplexing), performance (throughput, delay, stability, contention resolution algorithms and fairness) and multimedia support (scheduling, access pri orities). We confine our study to systems that span relatively small areas. The article is organized as follows. First we con trast different wireless network architectures. We then bring out the issues unique to wireless MAC protocols. The perfor mance metrics used to compare different MAC protocols are discussed later. We then present a classification of the proto cols. We will present the different classes of proposed MAC protocols and compare the pros and cons of the proposed protocols. A wireless network is comprised of devices with wireless adapters communicating with each other using radio waves. These wireless devices are called nodes in this dissertation. The signal transmitted can be received only within a certain distance from the sender, which is called the range of the node. A base station (BS) is a special node in the network that is not mobile and is located in a central location. Wireless networks differ in the duplexing mechanism and the network architecture. The duplexing mechanism refers to how the data transmis sion and the data reception channels are multiplexed. They can be multiplexed in different time slots or different fre quency channels. Time division duplex (TDD) refers to multiplexing of the transmission and reception in different time periods in the same frequency band. Using different frequency bands for uplink and downlink is called the fre quency division duplex (FDD) mode of operation. In FDD it is feasible for the node to transmit and receive data at the same time; this is not possible in TDD. Based on the network architecture, wireless networks can be logically divided into two classes: distributed and central ized. Distributed Wireless Networks -Distributed wireless net works, also called ad hoc networks, are wireless terminals communicating with one another with no pre-existing infra structure in place; therefore, they are also called infra structure-less networks. A typical ad hoc network is illustrated in Fig. 1a . Wireless terminals have a wireless interface (RF or infrared) and exchange information between one another in a distributed manner. An ad hoc network has no central admin istration, thus ensuring that the network does not collapse when one of the terminals is powered down or moves away. In a distributed network all data transmission and reception has to be in the same frequency band since there are no special nodes to translate the transmission from one frequency band to another. Therefore all ad hoc networks operate in TDD mode. Centralized Wireless Networks -Centralized wireless net works, also known as last-hop networks, are extensions to wire line networks with wireless in the last section of the net work. These networks have a base station that acts as the interface between wireless and wire line networks. In central ized networks the downlink transmissions (from base station to wireless nodes) are broadcast and can be heard by all the devices on the network. The up link (from wireless terminals to the BS) is shared by all the nodes and is therefore a multi ple access channel. The existence of a central node like a BS gives a great degree of flexibility in the design of MAC proto cols. The BS can control the uplink transmissions by allowing access according to QoS requirements. The system architec ture of a centralized network is shown in Fig. lb . A central ized network can operate both in TDD mode or FDD mode. The wireless channel is said to be slotted if transmission attempts can take place at discrete instants in time. A slotted system requires network-wide time synchronization, which is easy to achieve in centralized networks by using the BS as a time reference. Such synchronization is difficult in distributed networks. A slot is the basic time unit in a slotted system. It is usually large enough to carry the smallest packet, perhaps a few bytes together with packet overhead such as headers and guard band. The unique properties of the wireless medium make the design of MAC protocols very different from, and more chal- Ad-hoc network Last hop network • FIGURE 1. System architecture altematives: dis tributed and cen tral ized wireless networks. lenging than, wire line networks. The unique properties of wireless systems and their medium are: Half-Duplex Operation: In wireless systems it is very diffi cult to receive data when the transmitter is sending data. This is because when a node is transmitting data, a large fraction of the signal energy leaks into the receive path. This is referred to as self-interference The transmitted and received power levels can differ by orders of magnitude. The leakage signal typically has much higher power than the received sig nal, which makes it impossible to detect a received signal while transmitting data. Hence, collision detection is not pos sible while sending data and so Ethernet-like protocols cannot be used. Due to the half-duplex mode of operation, the uplink and downlink need to be multiplexed in time (TDD) or fre quency (FDD). As collisions cannot be detected by the sender, all proposed protocols attempt to decrease the proba bility of a collision using collision avoidance principles. Time Varying Channel: Radio signals propagate according to three mechanisms: reflection, diffraction, and scattering. The signal received by a node is a superposition of time-shift ed and attenuated versions of the transmitted signal. As a result, the received signal power varies as a function of time. This phenomenon is called multip ath propaga tion. The rate of variation of the channel is determined by the coherence time of the channel. Coherence time is defined as time within which the received signal strength changes by 3 dB [1] . When the received signal strength drops below a certain threshold, the node is said to be in fa de. Handshaking is a widely used strategy to mitigate time-varying link quality. When two nodes want to communicate with each other, they exchange small messages that test the wireless channel between them. A suc cessful handshake indicates a good communication link between the two nodes. Burst Channel Errors: As a consequence of the time-vary ing channel and varying signal strength, errors are more likely in wireless transmissions. In wireline networks, the bit error rates are typically less than 10-6 and as a result the probability of a packet error is small. In contrast, wireless channels may have bit-error rates as high as 10-3 or higher, resulting in a much higher probability of packet errors. In wire line networks these errors are usually due to random noise. In contrast, the errors on a wireless link occur in long bursts when the node is in fade. Packet loss due to burst errors can be minimized by using one or more of the following three techniques: • Smaller packets. • Forward error correcting codes. • Retransmission methods. A widely used strategy is to use link-layer retransmissions. Therefore, most protocols have immediate acknowledgments (ACK) to detect packet errors. If an ACK is not received at the end of a transmission, the packet is retransmitted. Location-Dependent Carrier Sensing: It is well known that in free space, signal strength decays with the square of the  o ,,><, : • FIGURE 2. Loca tion-depen den t sensing: hidden nodes, exposed nodes, and capture. path length [1] . As a result carrier sensing is a function of the position of the receiver relative to the transmitter. In the wire less medium, because of multipath propagation, signal strength decays according to a power law with distance. Only nodes within a specific radius of the transmitter can detect the carrier on the channel. This location-dependent carrier sens ing results in three types of nodes in protocols that use carrier sensing. • Hidden Nodes: A hidden node is one that is within the range of the intended destination but out of range of the sender [2] . Consider the case shown in Fig. 2 . Node A is transmitting to node B. Node C cannot hear the trans mission from A. During this transmission when C senses the channel, it falsely thinks that the channel is idle. If node C starts a transmission, it interferes with the data reception at B. In this case node C is a hidden node to node A. Hence, hidden nodes can cause collisions on data transmission. • Exposed Nodes: Exposed nodes are complementary to hidden nodes. An exposed node is one that is within the range of the sender but out of range of the destination [2]. In Fig. 2 , consider the case that node B is attempting to transmit to A. Node C can hear the transmission from B. When it senses the channel, it thinks that the channel is busy. However, any transmission by node C does not reach node A, and hence does not interfere with data reception at node A. In theory, C can therefore have a parallel conversation with another terminal out of range of B and in range of C. In this case, node C is an exposed node to node B. If the exposed nodes are not minimized, the bandwidth is underutilized. • Capture: Capture is said to occur when a receiver can cleanly receive a transmission from one of two simultane ous transmissions, both within its range [2]. In Fig. 2 , when nodes A and D transmit simultaneously to B, the signal strength received from D is much higher than that from A, and D's transmission can be decoded without errors in the presence of transmission from A. Capture can improve protocol performance, but it results in unfair sharing of bandwidth with preference given to nodes closer to the BS. Wireless MAC protocols need to ensure fairness under such conditions. Capture models are discussed in [3] [4] [5] . Given the wide range of protocols that have been proposed, it is necessary to understand the metrics that are used to com pare the MAC protocols. Delay, throughput, fairness, support for multimedia, and stability are the widely used metrics to compare MAC protocols. Robustness against fading and bat tery power consumption are additional metrics used to com pare wireless MAC protocols. Following is a brief discussion of these metrics: • Delay: Delay is defined as the average time spent by a packet in the MAC queue, i.e., from the instant it is enqueued till its transmission is complete. Delay is a function of protocol and traffic characteristics. There fore, when comparing protocols, it is necessary to com pare them based on the same traffic parameters. • Throughput: Throughput is the fraction of the channel capacity used for data transmission. A MAC protocol's objective is to maximize the throughput while minimizing the access delay. If the average message size is P bits, the average time to transfer a single packet is T secs, and C bls is the capacity of the channel, then the throughput 11 is given by 11 = PITC • Fairness: A MAC protocol is fair if it does not exhibit preference to any single node when multiple nodes are trying to access the channel. This results in fair sharing of the bandwidth [6] . This definition can be biased when traffic with different priorities is handled. When multi media traffic is supported, fairness is defined as being able to distribute bandwidth in proportion to their allo cation. • Stability: Due to overhead in the protocol, the system may be able to handle sustained source loads that are much smaller than the maximum transmission capacity of the channel. A stable system can handle instantaneous loads that are greater than the maximum sustained load when the long-term offered load is less than the maxi mum. • Robustness against Channel Fading: The wireless chan nel is time-varying and error-prone. Channel fading can make the link between two nodes unusable for short periods of time. Such link failures should not result in unstable behavior. • Power Consumption: Most wireless devices have limited battery power. Hence, it is important for MAC protocols to conserve power and provide some power saving fea tures. • Support for Multimedia: With the convergence of voice, video, and data networks, it is now necessary for MAC protocols to support multimedia traffic. Protocols require mechanisms to treat packets from various applications based on their delay constraints. Two common methods are access priorities and scheduling. Access priorities provide differentiated service by allowing certain nodes to get access to the network services with a higher proba bility than others. Scheduling can give delay and jitter guarantees. Figure 3 shows a classification of wireless MAC protocols. Wireless MAC protocols can be broadly classified into two categories, distributed and centralized, according to the type of network architecture for which they are designed. Protocols can be further classified based on the mode of operation into random access protocols, guaranteed access protocols, and hybrid access protocols. In a random access protocol, nodes contend for access to the medium. When only one node makes a transmission attempt, the packet is delivered success fully. When multiple nodes make a transmission attempt, a collision results. Nodes resolve the collisions in an orderly manner according to rules defined by the contention resolu tion algorithm (CRA). ALOHA was the first protocol pro posed for packet radio networks [7, 8] , and it is a classic example of a random access protocol. The protocol operates as follows: A node that has data to send transmits it. If the transmission collides with another transmission, it retries after a random period. The maximum throughput of this protocol is 18 percent. If the medium is slotted and transmission attempts are made at the beginning of the slot, the vulnerable period of a transmission is halved, doubling the efficiency of the system [9] . This slotted version of ALOHA is called S-ALOHA. In a guaranteed access protocol, nodes access the medium in an orderly manner, usually in a round-robin fashion. There are two ways to implement these protocols. One is to use a master-slave configuration, where the master polls each node and the node sends data in response to the poll. These proto cols are called polling protocols. The second is to operate in a distributed manner by exchanging tokens. Only the station with the token can transmit data. Each station, after transmit ting data, passes the token to the next station. These protocols are called token-passing protocols. Hybrid access protocols blend the best qualities of the above two protocols to derive more efficient MAC protocols. Most hybrid access protocols are based on request-grant mechanisms. Each node sends a request to the base station indicating how much time or bandwidth is required to send the data currently resident in its buffer. The request is sent using a random access protocol. The base station then allo cates an upstream time slot for the actual data transmission and sends a grant to the node indicating that time slot. Depending on the intelligence at the BS, the hybrid access protocols can be further classified into Random Reservation Access (RRA) protocols and Demand Assignment (DA) pro tocols. In an RRA protocol, the BS has implicit rules for reserving upstream bandwidth. An example of a rule is: A suc cessful request results in a periodic reservation of an upstream slot. On the other hand, in a DA protocol the BS controls upstream data transmissions according to their QoS require ments. It collects all the requests from the nodes and uses scheduling algorithms to make bandwidth allocations. Even though wireless MAC protocols handle issues very differently from wireline networks, some of the principles in hybrid access protocols are similar to the principles in the protocols developed for hybrid-fiber coax systems [10] . Hybrid access protocols and polling protocols by their mode of operation require a central node. Therefore they fall into the category of centralized MAC protocols. Random access protocols can operate in either architecture. Token passing protocols could be used as distributed protocols but are not because of robustness considerations. Due to the time varying nature of the wireless channel, token loss would be common and token recovery is a huge overhead. As a result, all proposed distributed MAC protocols are random access protocols. • FIGURE 3. Cla ssifica tion of wireless MAC protocols. With the exception of ALOHA, all distributed MAC proto cols are based on principles of carrier sensing and collision avoidance. Carrier sensing refers to listening to the physical medium to detect any ongoing transmissions. Recall that loca tion-dependent carrier sensing results in hidden and exposed nodes. Such nodes play a dominant role in CSMA protocols. Collisions that occur at the destination node are not necessar ily heard by the sender, so the destination needs to relay feed back to the sender. Consider the example in Fig. 2 when nodes A and C transmit simultaneously to B. This results in a collision at B but not at either A or C. Therefore B has to transmit this collision information back to A and C. However, because wireless transceivers operate in half-duplex mode, nodes cannot listen while transmitting and the feedback infor mation has to be sent using out of band signals or the node has to stop and listen for feedback. As a result most distribut ed MAC protocols use collision avoidance techniques wherein mechanisms are built into the protocol to minimize the proba bility of a collision. There are two mechanisms that can be used: the already mentioned out-of-band approach and the handshaking approach. These two approaches are described below. Collision Avoidance with Out-of-Band Signaling -Busy tone multiple access (BTMA) [11] is an example of a protocol that uses an out-of-band busy tone signal to prevent hidden nodes. Any node that hears an ongoing transmission transmits a busy tone; any node that hears a busy tone does not initiate a transmission. Thus, all nodes in a 2R radius of the transmit ting node are inhibited from transmitting, where R is the range of the transmitting node. Although this solution elimi nates hidden nodes, it increases the number of exposed nodes. In receiver in itia ted -busy ton e multip le access (RI-BTMA) [12] , a node transmits a busy tone only after it decodes the transmission and identifies itself as the intended receiver. As a result, only the nodes within radius R of the receiving node are inhibited. In RI -BTMA the destination has to decode and match the destination address to detect a collision. As a result it takes a long time to initiate the busy tone. Therefore, the packet transmission is vulnerable to collision for a duration much longer than the round trip. This results in a higher probability of collision and hence lower throughput. RI BTMA does not completely eliminate hidden nodes but mini mizes exposed nodes. Collision Avoidance with Control Handshaking -Multi ple access with collision avoidance (MACA) [13] uses a three way handshake as a solution to the hidden node problem. A node that has data to send transmits a short Request to Send (R TS) packet. All stations within one hop of the sending node hear the R TS and defer their transmissions. The destination responds with a Clear to Send message (CTS). All nodes with in one hop of the destination node hear the CTS and also defer their transmissions. On receiving the CTS the transmit ting node assumes that the channel is acquired and initiates the data transmission. This handshaking mechanism does not completely solve the hidden terminal problem, but it does prevent it to a large extent. Enhancements to RTS-CTS con trol handshaking and more complete single-channel solutions can be found in [2, 14, 15] . In these techniques there is a tradeoff between the overhead of handshaking and the num ber of hidden nodes eliminated. The basic operation of any CSMA protocol is as follows: A node that has data to transmit senses the channel for a certain duration before transmitting. If the channel is busy, the node waits a random period and tries to transmit at a later time. If the channel is idle, the node makes an attempt to acquire the channel. Successful acquisition is followed by transmission of the data packet. If the acquisition attempt results in a colli sion, the colliding nodes try to resolve the collision in an orderly manner. Each packet transmission is then acknowl edged by the destination station. Two recently proposed CSMA protocols are discussed here. Fig. 4 . When a node (sender) has data to transmit, it picks a random wait period. This wait peri od is decremented when the channel is idle. When this period expires, the node tries to acquire the channel by sending a R TS packet. The receiving node (destination) responds with a CTS packet indicating that it is ready to receive the data. The sender then completes the packet transmission. If this packet is received without errors, the destination node responds with an ACK. If an ACK is not received, the packet is assumed to be lost and retransmitted. If the R TS fails, the node attempts to resolve the collision by doubling the wait period. This con tention resolution method is called binary exponential backoff (BEB). To give preference to a station trying to send an ACK, different waiting intervals are specified. A node needs to sense the channel idle for a Dis tributed In ter-Frame Sp ace (DIFS) interval before making an RTS attempt and a Sh ort In ter-Frame Sp ace (SIFS) interval before sending an ACK packet. Since the SIFS interval is shorter than the DIFS interval, the station sending an ACK attempts transmission before a station attempting to send data and hence takes priority. In addition to the physical channel sensing, virtual carrier sensing is achieved by using time fields in the packets, which indicate to other nodes the duration of the current transmission. This time field is called the Network Alloca tion Vector (NA V) field, which indicates the duration of the current trans mission. All nodes that hear the R TS or CTS message back off NAVamount of time before sensing the chan nel again. A detailed description of the protocol can be found in [17, 16] . Performance and stability of the protocol are discussed in [18] [19] [20] . Improvements to DFWMAC are proposed in [21] .
A good summary of wireless MAC protocols, including polling ones, can be found in REF .
Wireless medium access control protocols
IEEE Communications Surveys & Tutorials
IEEE Communications Surveys & Tutorials
Computer Science