## 1 Introduction  
A Media Access Control (MAC) protocol is designed for coordinating access to shared channel(s) among multiple users in order to avoid collisions and achieve efficient use of the medium. It has been shown that the IEEE 802.11 MAC [1], although widely adopted, suffers low throughput performance in the multi-hop wireless network environment [2, 3, 4]. In the IEEE 802.11 MAC, the nodes around a transmitter and the target receiver are regarded as potentially interfering nodes. The virtual carrier sensing mechanism is used to prevent these nodes from initiating their transmissions. However, there are scenarios that some of the neighboring nodes' transmissions will not cause collision with, and will not be interfered by the ongoing transmission, but are still forbidden to transmit. Such nodes are termed \"exposed terminals\" and in such situations the channel spectrum is not efficiently utilized. It has attracted considerable interest to solve or alleviate the exposed terminal problem, since the IEEE 802.11 MAC is becoming the most popular MAC protocol for single- and multi-hop wireless networks. There have been considerable research efforts on this aspect. For example, MAC protocols requiring additional hardware or PHY capacities are shown to be helpful [5; 6]. In addition, there have been proposals on tuning the carrier sensing range [7; 8; 9], controlling the transmit power [10; 11; 12], and modifying the behavior of the IEEE 802.11 MAC [13; 14; 15]. However, these studies are conducted assuming deterministic wireless propagation models, such as the free-space propagation model or the two-ray ground reflection model [16]. In these models, path loss is determined by the distance between the transmitter and receiver deterministically. However, due to obstacles, multi-path propagation, and mobility, randomness such as shadowing or fading exists in most wireless networks and should be considered in MAC protocol design. In a wireless network environment, factors such as reflection, diffraction, and scattering affect the propagation of radio waves. In addition to power attenuation, \"large-scale shadowing\" and \"small-scale fading\" are usually experienced by radio signals. Small-scale fading describes the rapid fluctuation of the signals over a short period of time or distance. On the other hand, large-scale shadowing represents a random effect which occurs over a large number of measurement locations which have the same distance between the transmitter and the receiver, but have different levels of obstacles on the propagation path. It is well-known that the log-normal shadowing propagation model captures this effect. The log-normal shadowing propagation model describes the random variation of the received power around the mean (nominal) value, and the power variation in decibel (dB) follows a normal distribution [16]. Figure 1 illustrates the transmission ranges when the two-ray ground reflection model (left) and the log-normal shadowing propagation model (right) are used. Under the deterministic channel model, transmission range of a node is circular for a given transmit power, as shown in the left figure in Figure 1. Under shadowing channels as in a typical wireless network environment, the transmission range is not circular anymore. As can be observed in the right figure, although Node \(B\) is within the mean  
Figure 1: Transmission ranges for the two-ray ground reflection model (left) and the shadowing model (right). transmission range of the center node (the dotted circle), it may not receive the center node's transmission due to shadowing. On the other hand, although Node \(C\) is out of the mean transmission range of the center node, it can receive the center node's transmission. The free space or two-ray ground reflection channels do not model the actual radio propagation precisely, and such inaccuracy may have a considerable impact on the MAC protocol performance since the set of one-hop neighbors is not deterministic anymore.