Partial Interference and Its Performance Impact on Wireless Multiple Access Networks

In a wireless network, all stations communicate with each other through wireless links. A fundamental difference between a wireless network and its wired counterpart is that wireless links may interfere with each other, resulting in performance degradation. Therefore in the study of wireless networks, one important performance measure is the capacity of the network when the effects of interlink interference are considered.

In establishing the capacity of a wireless network, we have to predict whether the wireless links interfere with each other. Two most common interference models in the wireless networking literature, namely, for example, protocol model and physical model [1], were proposed to predict whether transmissions in a wireless network are successful. In these interference models, one key assumption is that interference is a binary phenomenon, that is, either the links mutually interfere with each other to result in total loss of throughput of a target link, or there is no link throughput degradation at all. In other words, these models exclude the possibility that interfering links can be active simultaneously and still realize their capacity partially. However, recent empirical studies [2‐6] have shown that these binary interference models are not valid in practice. Instead, measurement results have confirmed that there is a nonbinary transitional region [2, 4] (also known as the gray zone in some literature [3]) for the successful packet reception rate (PRR) of a wireless link which changes from zero, that is, 100% lossy, to almost 100%, that is, perfectly reliable, as its signal-to-interference-plus-noise ratio (SINR) increases. These studies have indicated that the range of the transitional regional (in SINR) can exceed 10dB for various types of practical networks including IEEE 802.11a wireless mesh [3, 7] and other low-power multihop sensor networks [2, 4]. More importantly, measurement studies on large-scale wireless mesh testbeds [8, 9] found that a significant number of links in those testbeds were indeed operating at the SINR transitional region, that is, with intermediate level of PRR between zero and 100%. In this paper, we call this phenomenon partial interference. From the physical layer implementation perspective, the partial interference phenomenon can be viewed as a consequence/manifestation of the probabilistic nature of signal decoding in the receiver, its interaction with the well-known capture effect [10, 11], and the specific implementation of the frame reception and capture algorithms in individual chipsets [12].

While the phenomenon of partial interference in wireless networks has been widely observed as mentioned above, its incorporation in the performance modeling of such networks is still in its infancy. Most of the efforts in this direction so far ([2, 7, 12, 13]) have been limited to the characterization of the nonbinary transitional region in the PRR-versus-SINR curve based on measurement data [7, 12, 13] or some analytical means [2, 14]. However, once the PRR-versus-SINR curve is obtained, they only resort to simulations to evaluate the effects of partial interference on the system performance.

While the phenomenon of partial interference in wireless networks has been widely observed as mentioned above, its incorporation in the performance modeling of such networks is still in its infancy. Most of the efforts in this direction so far ([2, 7, 12, 13]) have been limited to the characterization of the nonbinary transitional region in the PRR-versus-SINR curve based on measurement data [7, 12, 13] or some analytical means [2, 14]. However, once the PRR-versus-SINR curve is obtained, they only resort to simulations to evaluate the effects of partial interference on the system performance.

To quantify the impact of interference on multiple access networks, we propose an analytical framework to characterize partial interference for two representative types of multiple access wireless networks, namely, the IEEE 802.11 Wireless LANs and the classical slotted ALOHA networks. For IEEE 802.11 Wireless LANs, we extend the single-channel Markov model in [15] to take into account the unsaturated traffic conditions, the SINR attained at the receivers, and the modulation scheme employed. These modifications result in a partial interference region, which cannot be captured by the binary interference models used in previous works. We also find out the stability (admissible) region of IEEE 802.11 networks with two interfering, potentially unsaturated links numerically. For slotted ALOHA networks, we extend the model in [16] to derive the exact stability region of slotted ALOHA with two links while considering partial interference. We show that as the link separation increases, the stability region obtained expands gradually under partial interference, as in the case of 802.11.

Despite the simplicity of slotted ALOHA, characterizing its exact stability region with unsaturated links is extremely difficult and has remained to be a key open problem for decades when there are more than two, potentially unsaturated links in the system [16‐23]. However, by extending the FRASA (Feedback Retransmission Approximation for Slotted ALOHA) approach [24] to model the partial interference effects, we obtain a closed-form approximation for the exact stability region for any number of links.

In summary, this paper has made the following contributions.

In [1], two interference models, called the protocol model and the physical model, were introduced. The protocol model states that a transmission is successful if the corresponding receiver is located inside the transmission range of the transmitter, and all other active transmitters are located outside the interference range of the receiver. In the physical model, the transmissions from other transmitters are considered as noise, and a transmission is successful if the SINR attained at the receiver exceeds a certain threshold. Based on these models, the capacities of a multihop wireless network under random and optimal node placement were derived.

In [5], the authors measured the interference among links in a single-channel, static 802.11 multihop wireless network. They measured the interference between pairs of links by the link interference ratio and observed that this ratio exhibited a continuum between 0 and 1. In [6], two interfering links were set up in a wireless network with multiple partially overlapped channels to measure TCP and UDP throughputs of an individual link. It was found that the throughputs increased smoothly when the separation between the links increased. The throughputs increased more rapidly as the channel separation between the links increased. Such nonbinary transitional region in the link throughput (or PRR equivalently) as the receiver SINR varies has also been observed by numerous measurement studies including [2‐4]. These experimental results all confirmed that the binary assumption in the protocol or physical interference models are not valid in practice.

There has been some analytical work on finding the relationship between the SINR attained at a receiver and the throughput (or PRR equivalently) achieved by the corresponding wireless link. In [14], a methodology for estimating the packet error rate in the affected wireless network due to the interference from the interfering wireless network was presented. The throughput of the affected wireless network was found to increase continuously with the SINR attained at the corresponding receiver, which increased with the separation between the networks. Similarly, [2] derived expressions for the PRR as a function of distance, radio channel parameters, and the modulation/encoding scheme used by the radio. However, they did not provide analytical model on how the PRR function would impact the performance of the corresponding networks.

In [25], the throughput achieved by an M-link IEEE 802.11 network under physical layer capture was derived. While their analysis can be viewed as another case study of the effects of the partial interference over 802.11 networks, their approach only works for the case where all of the links are always saturated, that is, with infinite backlog at the transmitter side. In contrast, the approach proposed in Section 5 of this paper can handle unsaturated links and has provided explicit numerical solutions for the stability region of the 2-link case.

The study of the stability region of -user infinite-buffer slotted ALOHA was initiated by the study in [17] decades before and is still an ongoing research. The authors in [17] obtained the exact stability region when under the collision channel (i.e., binary interference) model. References [18, 19] used stochastic dominance and derived the same result as in [17] for the case of .

For general , there were attempts to find the exact stability region, but there was only limited success. Reference [21] established the boundary of the stability region, but it involves stationary joint queue statistics, which still do not have closed form to date. Instead, many researchers focused on finding bounds on the stability region for general . Reference [17] obtained separate sufficient and necessary conditions for stability. References [18, 19] derived tighter bounds on the stability region by using stochastic dominance in different ways. Reference [22] introduced instability rank and used it to improve the bounds on the stability region. However, the bounds in [18, 22] are not always applicable. Also, the bounds obtained may not be piecewise linear.

With the advances in multiuser detection, researchers also studied this problem with the multipacket reception (MPR) model. Reference [23] studied this problem in the infinite-user, single-buffer, and symmetric MPR case. Reference [16] considered the problem with finite users and infinite buffer. They obtained the boundary for the asymmetric MPR case with two users, and also the inner bound on the stability region for general .

As an illustration to the methodology in [14], assume the underlying modulation scheme used is binary phase shift keying (BPSK). The distance between the transmitter and the receiver and that between the interferer and the receiver are and meters, respectively. The transmission power of the transmitter and the interferer are and watts, respectively.

Assuming that the interfering signal can be modeled as additive white Gaussian noise (AWGN) and the background noise can be ignored, we use the two-ray ground reflection model

to represent the path loss, where and are the gain of transmitter and receiver antenna, respectively, and are the height of transmitter and receiver antenna, respectively, and . The path loss exponent is 4 in this model. We let and . Then, according to [26], the bit error rate (BER) is given by

where is the SINR attained at the receiver and is given by

Define the packet-level normalized throughput to be the ratio of the successful packet reception rate at the receiver when to the maximum packet reception rate of the link when . As such, is actually the probability of a packet to be received without error when the SINR is . Suppose that all packets consist of bits and bit errors are identically, independently distributed within each packet. We have

In general, depends on the BER, which, in turn, is a function of the SINR at the receiver as well as the specific modulation scheme being used. While we use BPSK as an example here, the actual expression for under other modulation schemes can be readily derived as shown in [2, Table ].

Figure 1 shows a plot of such packet-level normalized throughput against distance between the interferer and the receiver for dBm, meters, ranging from 400 to 700 meters, and  bits (= 1500 bytes). Observe from the figure the nonbinary transitional region of as the separation between the interferer and the receiver increases. Such "partial interference" region is also consistent with the findings of many empirical studies discussed in Section 1.

In Figure 1, we also plot the variation of throughput against distance between the interferer and the receiver if the physical model is used. The SINR threshold for the binary-interference model is set by assuming that when , the packet error rate is , that is,

We observe that if the value we assign to is too large (or the threshold distance is too large), we underestimate the throughput that the links can achieve. On the other hand, if is too small (or the threshold distance is too small), we introduce excessive interference into the network. In other words, it is difficult to use a single threshold to describe accurately the relationship between interference and throughput of each link in a network.

In this section, we demonstrate that there is a gain in system capacity when the effect of partial interference is considered. We consider one variation of the Manhattan network [27], that is, a network consisting of a rectangular grid extending to infinity in both dimensions. The horizontal and vertical separations between neighboring stations are denoted by and , respectively.

Under infinite transmitter backlog, the packet-level capacity of each link, that is, the maximum packet reception rate without interference, is denoted by . We assume that differential binary phase shift keying (DBPSK) is employed and a packet consists of bits. We use the two-ray ground reflection model (1) as in previous section to model the path loss. To apply the physical model, we let the SINR threshold be the case that the packet error rate is , that is, , where is the bit error rate of DBPSK [26]. We let and , therefore the SINR requirement is . Assuming that there is no interferer, this SINR requirement is met when the length of a link is smaller than 493 meters.

We use a Cartesian coordinate plane to represent the modified Manhattan network. One station is placed at every point with integral coordinates in the network. Suppose that we schedule flows in the modified Manhattan network from the South to the North using the pattern shown in Figure 2 and its shifted versions. In Figure 2, an arrow is used to represent an active link, where the tail and the head of an arrow denote the transmitter and the receiver of the link, respectively.

We use the capacity across unit cut as the performance metric, where is the ratio of the horizontal separation to the vertical separation. It is a measure on how much traffic we can send through a cut in a network on average while physically packing the links towards each other. Consider the SINR attained at the receiver marked with the blue circle, which has the position assigned as the origin in the Cartesian coordinate plane. We assume that all stations transmit with power , and each station has a background noise power of . The SINR is defined by , where is the received power from the intended transmitter and is the power received from all interferers. The packet-level capacity achieved by each link, that is, the successful packet reception rate at the receiver, is under our partial interference model. On the other hand, under the physical interference model, if and otherwise. A cut in the network is an infinitely long horizontal line. Let be the set of all active transmitters such that intersects the link used by . We divide into segments , , where

and is the Euclidean norm. Then the length of the cut occupied by an active transmitter is the length of , and the capacity across unit cut is therefore , where is the fraction of time that a link is active.

In the following we assume that meters,  dBm, and  dBm. For the schedule in Figure 2, the signal power is . All transmitters in Figure 2 are located at positions , where and are integers. The interference power is

Considering the physical model, if the schedule is allowed to be active, we need , as listed in Table 1 and depicted in Figure 3 by the blue dashed line. The value of is obtained from . Each active transmitter occupies a cut of length , and each link is active for one quarter of a cycle. Therefore, for , the maximum capacity across unit cut under the physical model is bits per second per kilometer.

If we allow partial interference, the active transmitters can be packed more closely. When decreases, more spatial reuse is allowed. The increase in the density of active transmitters outweighs the degradation in capacity, so there is an increase in the capacity across unit cut. However, if decreases further, interference will be the dominant factor in determining the capacity across unit cut. Therefore, the capacity across unit cut drops, and there exists for the optimal performance under partial interference. This behavior is depicted by the blue solid line in Figure 3. The optimal value of under partial interference is , and the capacity across unit cut is bits per second per kilometer. There is a percentage increase of 66.82% in the capacity across unit cut when the effect of partial interference is considered. Similar results are shown in Table 1 and Figure 3 for meters. The percentage increase is larger when the links are longer, but the capacity achieved by each link reduces. We can view as the carrier sensing range in the modified Manhattan network with the scheduling pattern in Figure 2, as it is the smallest horizontal separation allowed by the physical model. We observe that if the length of the links increases, the carrier sensing range needs to be increased in a larger proportion. Also, this carrier sensing range is much larger than double of the length of the links, which is the usual convention used in defining the relationship between carrier sensing range and transmission range.

In this section, we study partial interference in 802.11 networks, the prevalent wireless random access networks. We present an analytical framework to characterize partial interference in a single-channel wireless network under unsaturated traffic conditions, which uses 802.11b with basic access scheme and DBPSK. We show that there is a partial interference region, in which the throughput of each link increases continuously with the separation between the links in the network. As a first attempt to relate the capacity-finding problem in wireless random access networks to the stability region of such networks, we derive the admissible (stability) region of an 802.11 network with two potentially unsaturated links numerically.

In order to obtain insights in the stability region of general 802.11 networks, in this section, we study the stability of slotted ALOHA, which is a simpler random access protocol, under the assumptions of finite links and infinite buffer.

Theorems 2 and 3 cover all cases with zero or one nonempty nonpersistent link in an M-link system, respectively. However, if there are at least two nonempty unsaturated links, the stationary joint queue statistics must be involved in calculating the boundary. Unless we are able to compute the stationary joint queue statistics in closed-form, we are unable to solve the capacity-finding problem, even assuming one of the simplest random access protocol, that is, slotted ALOHA. In fact, the characterization of the exact stability region of a general M-link slotted ALOHA system with nonpersistent links has remained to be a key open problem for decades when [16‐23] even under the simplified binary interference model.

To overcome the problem caused by the stationary joint queue statistics, we have introduced the FRASA (Feedback Retransmission Approximation for Slotted Aloha) model in [24] to obtain a closed-form approximation for the stability region of a general M-link slotted ALOHA system under binary interference (i.e., simple collision channel) assumptions. We refer the readers to [24, 31] for a detailed description of the FRASA approach. In the following subsection, we extend the model and analysis in [24] to cover the partial interference case. We remark that our results here automatically apply to the binary interference case if we allow to be either zero or one only by comparing the corresponding SINR, that is, , against a predefined threshold , as illustrated in (32) and (33).

In this paper, we have introduced the notion of partial interference in wireless multiple access systems and illustrated the potential gain in system capacity when the effect of partial interference is taken into account. In particular, we characterize the stability region of IEEE 802.11 networks under partial interference with two potentially unsaturated links numerically. We also derive the stability region of slotted ALOHA networks under partial interference with two links analytically and obtain a partial characterization of the boundary of the stability region for the case of more than two, potentially unsaturated links in a slotted ALOHA system. By extending the FRASA model, we provide a closed-form approximation for the stability region for general M-link slotted ALOHA system under partial interference effects. Our analyses demonstrate that partial interference considerations can result in not only significant quantitative differences in the predicted system capacity but also fundamental qualitative changes in the shape of the stability region of the systems. This highlights the need of capturing the partial interference effects instead of adopting the conventional, overly simplified binary interference models while analyzing wireless MAC protocols.