On-line algorithm for optimizing throughput performance of wireless LANs

Abstract

Throughput improvement of the wireless LANs has been a constant area of research. Most of the work in this area focuses on designing throughput optimal schemes for fully connected networks (no hidden nodes). The schemes are optimal in a sense that they maximize the sum throughput subject to giving equal channel access opportunity to each user. But, we demonstrate that the optimal schemes proposed in the literature, though perform optimally in fully connected network, achieve significantly lesser throughput even than that of standard IEEE 802.11 in a network with hidden nodes. This motivates designing schemes that provide near optimal performance even when hidden nodes are present. This problem is particularly challenging as mathematical models for networks with hidden nodes do not exist. Here, we consider the weighted fair throughput allocation policy that maximizes system throughput while guaranteeing that every user achieves a throughput that is proportional to their weights. We prove the optimality of the proposed scheme in a fully connected network. However, the specialty of the algorithm, as observed in the simulation study, is that it can provide the optimal throughput even in networks with hidden terminals. Unlike existing techniques, which use the mathematical model to derive invariant features, we attempt to maximize the throughput directly using stochastic approximation techniques, and hence does not require the estimation of any system parameters which can result in inaccurate predictions. Simulations show that our proposed policies perform better than the standard IEEE 802.11 protocol without or with hidden nodes present. Moreover, our proposed schemes outperform existing schemes when the network is not fully connected.

Keywords

Stochastic approximation optimization wireless LANs resource allocation on-line algorithms

1. Introduction

IEEE 802.11 has emerged as one of the most popular access mechanisms for wireless local area networks (WLANs). Since its inception, significant effort has been made for improving the throughput of IEEE 802.11 [5,7,8,14,15]. Improving the throughput in WLANs is paramount in order to satisfy the ever increasing demand.

In this paper, we demonstrate that most of the proposed protocols though perform optimally for connected network (no hidden terminals), their throughput is lesser even than that of standard IEEE 802.11 in presence of hidden terminals. The protocols are optimal in the sense that they maximize sum throughput subject to giving fair channel access to each user. This motivates a need of designing schemes that not only perform well in connected networks, but also achieve near optimal throughput when hidden terminals are present. Our aim is to develop schemes to this end.

At the heart of the IEEE 802.11 lies the Distributed Co-ordination Function (DCF) based on CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance). DCF mechanism defines the channel contention mechanism and collision resolution scheme. Currently, DCF employs exponential backoff in which users cooperatively reduce their access probability upon collision. In [4], mathematical modeling of the CSMA/CA protocol is carried out to quantify the throughput performance of the protocol. In [4], the author has shown that the throughput offered by the IEEE 802.11 protocol with standard parameter values is much less than the best possible and degrades significantly with increasing number of users. Another key finding of [4] is: To design an optimal scheme that maximizes the system throughput while providing equal transmission opportunities to each station, it is sufficient to choose a single backoff window appropriately for each terminal, and one need not consider the exponential backoff. This implies that it suffices to consider p-persistent CSMA rather than the classical exponential backoff. Most of the proposals aimed at maximizing the throughput of IEEE 802.11 DCF propose algorithms to tune the access probability of p-persistent CSMA adaptively by statistical estimations of the parameters. For example, [5,9] estimate the number of users based on the number of busy slots observed in the system, and then choose appropriate access probability based on the obtained estimate. Key observation used in computing the optimal access probability based on the estimated number of users is that the product of the number of users and the optimal access probability is approximately constant. In the recently proposed IdleSense algorithm [14], the authors show that the number of idle slots remain constant when the access probability is optimally chosen. Thus, here the optimal access probability is obtained based on the estimated number of idle slots by each user.

Fig. 1.

Comparison of throughput of standard 802.11 protocol and IdleSense protocol without and with hidden nodes. The simulation was performed in ns-3 with nodes placed randomly and the results averaged over 20 iterations. The simulation parameters are given in Table 1. Hidden nodes are created by appropriately choosing the radius over which the nodes are distributed.

The work described above uses analysis similar to that in [4], which holds only under fully connected network in which every node can perform carrier sensing on the transmissions of every other node. This model fails in the presence of hidden nodes. Node i is hidden from node j if i is outside the sensing range of j, and as a result i cannot perform carrier sensing on j’s transmissions. Hence, it is not clear how the proposed schemes that are optimal in fully connected network would perform in presence of hidden nodes. To better understand the performance of the existing schemes in the presence of hidden nodes, we perform the following simulation in ns-3. We set parameters so that the transmission and sensing ranges are 16 and 24 units, respectively. Hence, a node can potentially decode (sense, resp.) transmissions from the nodes at distance less than or equal to 16 (24, resp.) units from it. We consider two types of network configurations, first without hidden nodes and second with hidden nodes. In the first case, nodes are placed uniformly on the edge of the disc with radius 8 units centered at the access point. In the second case, we place nodes uniformly at random in a disc of radius 16 units centered at the access point. Note that the maximum distance between the nodes is 32 units while the sensing radius is only 24 units, and hence there is a non-zero probability of having hidden node pairs. In Fig. 1, we compare the throughput of IdleSense protocol with that of standard IEEE 802.11 DCF with and without hidden nodes. These results are obtained after averaging over the 100 random topologies in each case. Specifically, after placing the nodes randomly, we verify whether hidden node pair exists, and average over such topologies. We choose IdleSense for comparison because it is the most recent protocol and has been shown to outperform the other existing schemes. From Fig. 1, it can be seen that while IdleSense performs significantly better than the standard IEEE 802.11 DCF in the fully connected network, but the protocol performs much worse when the hidden nodes exist. The reason for the failure of the IdleSense like algorithms in the presence of hidden nodes can be understood as follows. These algorithms are based on the mathematical model in [4] that govern the system. However when hidden nodes exist, the mathematical model does not hold. For example the target number of idle slots, while known for a fully connected network, may be different for networks with different hidden nodes configurations. Hence it is not possible to design the system with any particular value of the target idle slots in presence of hidden nodes. These observations motivate the need for schemes that not only perform optimally in fully connected network but also provide near optimal throughput in networks with hidden nodes.

Table 1

Parameters used in the simulation (based on OFDM PHY with 20 MHz channel spacing [16])

Bit Rate	54 Mbps
Packet Payload	8000 bits
${CW}_{min}$	8
${CW}_{max}$	1024
ns3::YansWifiPhy::EnergyDetectionThreshold	−70 dBm
ns3::YansWifiPhy::CcaMode1Threshold	−70 dBm

Before proceeding further, the most important question that needs answering is the following: Do we really need to consider WLANs with hidden nodes? The question is important because mechanisms do exist to potentially eliminate hidden nodes. For example, use of RTS/CTS exchange in IEEE 802.11 based MAC eliminates hidden nodes. But this approach has its own limitations mainly because RTS and CTS messages are transmitted at the lowest rate while data can be transmitted at a much higher rate. For example, in IEEE 802.11a/g the maximum date rate is 56 Mbps while the RTS and CTS messages are typically transmitted at 6 Mbps [16]. Thus, overhead due to RTS/CTS exchange is significant even though these control messages have much smaller length than that of data packets. This affects throughput performance of WLAN adversely (see e.g. [18,30]). Hence, IEEE 802.11 standards recommend use of RTS/CTS exchange only for large data packets. This is accomplished by choosing system parameter called RTS threshold. If the length of data packet is above RTS threshold, only then RTS/CTS exchange is used. By default, RTS threshold is set to the largest possible value, which is 2347 octets [16]. Thus, the default setting ensures that the RTS/CTS exchange is not used. Since, default settings are rarely changed during the installation in practice, it is reasonable to consider WLAN operation in basic access mode, i.e., without RTS/CTS exchange.

Another approach to mitigate the hidden nodes is by choosing the sensing radius to be two times the transmission radius. Intuitively, since all the nodes have to be in the transmission range of access point, with this setting, they have to be in the sensing range of each other. Though this intuition may hold in open spaces, it may fail in spaces with obstacles, e.g. offices, universities. This is because obstacles may cause strong shadowing between nodes. Note that if the path between node i and node j is shadowed due to obstruction, then even though the receiver would be capable of decoding the data from both the nodes, the nodes will not be able to sense each other’s transmissions. Thus, this approach does not guarantee elimination of hidden nodes. This shows that hidden nodes cannot be fully eliminated with current approaches. Hence, it is not sufficient to only consider fully connected WLANs, rather we must consider WLANs with hidden nodes.

Now, lets understand challenges in designing throughput optimal schemes for WLANs with hidden nodes. First note that quantifying the throughput performance of IEEE 802.11 DCF in presence of hidden nodes has remained an open problem for over a decade [31]. To best of our knowledge, mathematical models for such networks are not available except for very restrictive special cases. In absence of general mathematical models, obtaining provably throughput optimal schemes remained illusive. It is worth remembering that the existing model for the fully connected network fails to provide any meaningful insight for the networks with hidden terminals. In view of these difficulties, it is not clear how one should design schemes that provide near optimal performance even in presence of hidden nodes. In our approach, we do not base the design of optimal scheme on any underlying model, rather we base it on the following simple observation: If the channel access probability is “small”, then the medium is underutilized resulting in low system throughput; on the other hand, if the channel access probability is “large”, then the system throughput is again low on account of excessive collisions. This intuitively implies that the system throughput as a function of the access probability is bell-shaped (technically quasi-concave). Thus, we can employ standard gradient ascent techniques to obtain the optimal access probability. Now, we just need to verify that the system throughput is indeed a quasi-concave function of the access probability. We prove the required for the fully connected networks, which proves the optimality of our approach in this case. However, in absence of a mathematical model for networks with hidden terminals, we verify the quasi-concavity using extensive simulations in ns-3. Of course, validation through simulations does not prove that our proposed scheme is optimal when hidden terminals are present, but it at least states that in the numerous random topologies that we investigated, our scheme is throughput optimal.

Another interesting question that we address is: How crucial exponential backoff is in presence of hidden terminals? Note that in a fully connected network, the exponential backoff has shown to be unnecessary, and optimizing attempt probability of a p-persistent scheme suffices in order to maximize the system throughput [4,5]. In this paper, we demonstrate that the exponential backoff based schemes can provide a higher throughput than that under any p-persistent scheme. Thus, p-persistent schemes may not be throughput optimal, rather exponential backoff based schemes must be considered when hidden nodes exist.

Our key contributions in detail are as follows:

First, we consider a weighted fair throughput allocation while maximizing the system throughput. A weighted fair throughput allocation implies that the throughput allocated to a node is proportional to the weight assigned to the node. Note that this is a generalized version of the system throughput maximization. When all weights are equal, weighted throughput maximization reduces to the system throughput maximization. We propose Weighted Fair Throughput Optimal p-Persistent CSMA (wTOP-CSMA) that is an on-line mechanism for tuning access probability of p-persistent CSMA. The tuning mechanism uses techniques from stochastic approximation theory [20] that provides a weighted fair distribution of throughput in a connected network. In this algorithm every user achieves a throughput that is proportional to its weight. This algorithm does not require the users to know the weights used by the other users. Thus, every user could dynamically change their weights and the system would still adapt.

We also propose Throughput Optimal RandomReset-CSMA (TORA-CSMA) that uses standard exponential backoff on transmission failure, but after successful transmission goes to zeroth backoff stage with probability (w.p.) $p_{0}$ and to any of the remaining m backoff stages w.p. $(1 - p_{0}) / m$ . Again, TORA-CSMA uses stochastic approximation technique for on-line tuning of the parameter $p_{0}$ .

We show that both wTOP-CSMA and TORA-CSMA maximize system throughput while providing fairness, i.e. equal throughput to all users, in the connected network.

We also show that if the throughput is a quasi-concave function of the access probability in network with hidden nodes, then wTOP-CSMA maximizes the system throughput among all p-persistent CSMA schemes even when hidden nodes are present.

More interestingly, we show that TORA-CSMA provides better throughput than that of wTOP-CSMA in presence of hidden terminals. This demonstrates the merit of exponential backoff when network is not fully connected. Thus, p-persistent CSMA may not be a good choice for networks with hidden terminals.

The rest of the paper is organized as follows. Section 2 explains the system model that is considered in this paper. Section 3 provides the wTOP-CSMA policy and a proof of its optimality in the absence of hidden nodes. Section 4 describes an exponential backoff based policy that guarantees optimal throughput allocation in a fully connected network when all nodes have equal weights. Section 6 discusses about the performance of the proposed policies in the presence of hidden nodes and conditions under which the policies are optimal. Section 5 presents a discussion on the algorithms. Section 7 presents the simulations results from ns-3 simulations. Section 8 lists the existing literature on the performance improvement of the 802.11 protocol and compares the results with our work. Section 9 provides conclusion.

2. System model

We consider a system with N nodes, and denote $N = {1, \dots, N}$ . We consider the saturated case, i.e., all nodes always have a packet for transmission to a central Access Point (AP). Furthermore, when a node $t \in N$ transmits, a subset $T_{t} \subseteq N$ of the nodes and AP receives the information. We assume that $t \in T_{t}$ . Note that t is a hidden node for nodes in $N ∖ T_{t}$ . We assume that all transmissions by AP can be received by all nodes. If $T_{t}$ is same as the set $N$ for every node t, then the network is called a fully connected network. A node cannot receive and transmit simultaneously.

For the channel access mechanism, we assume the following. Any node $t \in N$ waits for $CW$ slots before attempting a transmission. A slot can be either an idle slot of a pre-determined duration or a busy slot with some node transmitting. An idle slot for transmitter t is a slot in which no transmission is received by t. The duration of the idle slot is typically fixed by the standards, e.g., the IEEE 802.11 with the OFDM PHY on 20 MHz channel has an idle slot duration of 9 µs. A busy slot for t is the duration for which it senses the channel to be busy followed by an idle duration of DIFS (Distributed Inter-Frame Space). Typically, DIFS is also defined by the standards, e.g., the IEEE 802.11 with the above PHY has DIFS equal to 34 µs. It is assumed that all users transmits the packet using the same fixed rate R.

A transmission by t to AP is successful if for the entire duration of transmission there is no other transmission by a node in $N ∖ {t}$ , i.e. the packet loss is only due to collisions.1

¹
Though, we have not considered packet loss due to channel errors, such can be incorporated in our framework in a straightforward fashion provided that the channel errors are independent and identically distributed over all transmissions.

After a successful transmission, AP transmits an Acknowledgement (ACK) after a duration of SIFS (Short InterFrame Space). According to IEEE 802.11 standard with the specified PHY SIFS is 16 µs. If ACK is not received for DIFS duration after transmission (say by t), then t concludes that the transmission failed due to collision and performs a contention resolution algorithm. The contention resolution algorithm specifies how

CW

should be chosen for the next transmission. Here, we consider three classes of contention resolution algorithms, namely, (1) standard exponential backoff, (2) p-persistent, and (3) RandomReset. Next, we briefly describe each of these.

Standard exponential backoff mechanism refers to that used in IEEE 802.11. Here, after i successive transmission failures, $CW$ is chosen uniformly at random from the interval $[0, {CW}_{i} - 1]$ where ${CW}_{i} = min {2^{i} \times {CW}_{min}, {CW}_{max}}$ . While, after a successful transmission, $CW$ is chosen uniformly at random from the interval $[0, {CW}_{min} - 1]$ . Here, ${CW}_{min}$ and ${CW}_{max}$ are the pre-defined system parameters. The states in which $CW$ is chosen from different intervals are referred to as backoff stages. Thus, the scheme has $m + 1$ ( $= {log}_{2} ({CW}_{max} / {CW}_{min})$ ) backoff stages. Typically, backoff stages are enumerated from 0 to m with stage i choosing $CW$ uniformly at random from $[0, {CW}_{i} - 1]$ .

In p-persistent schemes, $CW$ is chosen as a geometrically distributed random variable with mean $1 / p$ independent of success or failure of the previous transmission. Here, p is the system parameter. Typically, p is called the attempt probability, and the access mechanism is called p-persistent CSMA.

In this paper, we propose RandomReset scheme. Broadly this scheme performs exponential backoff on transmission failures, but unlike standard exponential backoff scheme, on successful transmission, it does not return to backoff stage 0 with probability (w.p.) 1. Instead it probabilistically chooses a backoff stage.

In this paper, we consider both p-persistent and RandomReset mechanisms and show that their parameters p and $p_{0}$ , respectively, can be tuned for optimal performance. The performance metric that is primarily considered in the paper is system throughput, which is defined as the effective number of bits transferred to AP per unit time. But, it is also important to consider notions of fairness. Hence, we consider throughput optimization subject to fairness as defined below.

Definition 1.

A channel access scheme is said to be throughput optimal if it maximizes the system throughput while ensuring that each node has the same attempt probability.

In this paper we also consider weighted fair throughput optimal schemes in which each node is pre-assigned with a weight indicating the priority of the user. A weighted fair throughput optimal scheme is defined as follows.

Definition 2.

A channel access scheme is said to be weighted fair throughput optimal if it maximizes the system throughput while ensuring that the throughput obtained by each node is proportional to its weight.

In the following sections, we describe the proposed wTOP-CSMA and TORA-CSMA, and prove their throughput optimality in a fully connected network.

3. A Weighted Fair Throughput Optimal policy in a fully connected network

Here, we describe the Weighted Fair Throughput Optimal p-persistent CSMA algorithm (wTOP-CSMA). We show that a weighted fair throughput allocation can be achieved by tuning a single variable. We then present an on-line algorithm to tune the variable to obtain optimal performance.

3.1. Problem formulation

Let each user $t \in N$ be assigned a fixed weight $w_{t}$ and denote $W = [w_{1}, \dots, w_{N}]$ . The problem of obtaining a weighted fair throughput optimal policy can be formulated as an optimization problem. Let each station use a p-persistent CSMA. Let $p = [p_{1}, \dots, p_{N}]$ be the vector of attempt probabilities with $p_{t}$ being the attempt probability of station t. Let $S_{t} (p)$ be the throughput obtained by station t when the attempt probabilities are p. Let $S (p)$ be the system throughput. Then the weighted fairness problem can be formulated by (1), $\begin{array}{rcl} max_{p \in {[0, 1]}^{N}} C \\ (1) & s.t. \frac{S_{t} (p)}{w_{t}} = C, 1 ⩽ t ⩽ N . \end{array}$ Since system throughput maximization means maximization of $S (p) = \sum_{t = 1}^{N} S_{t} (p) = \sum_{t = 1}^{N} w_{t} C$ which is same as maximizing C, this problem can be seen to maximize the system throughput. Here C is a constant which can be termed as the normalized throughput given to every station.

This problem is a constrained optimization problem over an N-dimensional space. In an adaptive setting this would require tuning of N variables. We show in the subsequent theorem that this problem can be reduced to a one-dimensional problem with a single control variable.

The idea of a weighted fair throughput allocation has been discussed in [28] and [21]. These works, while providing a weighted throughput allocation fail to provide an optimal throughput. In our work we consider a system throughput maximization problem under the constraint of a weighted throughput allocation.

From the system definition it is possible to see that the throughput obtained by station t is given by $\begin{matrix} (2) & S_{t} (p) = \frac{p_{t}}{1 - p_{t}} \frac{E_{P} P_{I}}{P_{I} σ + P_{T} P_{I} (T_{s} - T_{c}) + (1 - P_{I}) T_{c}} . \end{matrix}$

Here $E_{P}$ is the expected packet length, $P_{I} = \prod_{i = 1}^{N} (1 - p_{i})$ is the probability of an idle slot, $P_{T} P_{I}$ (with $P_{T} = \sum_{i = 1}^{N} \frac{p_{i}}{1 - p_{i}}$ ) is the probability that in a slot exactly one user transmits and $1 - P_{I} - P_{T} P_{I}$ is the probability that more than one user transmits in the slot. σ is the duration of an idle slot, $T_{s}$ is the duration of a slot with a successful transmission and $T_{c}$ is the duration of the slot with a failed transmission. In our model $T_{s} = (L_{H} + E_{P}) / R + T_{SIFS} + L_{ACK} / R + T_{DIFS}$ and $T_{c} = (L_{H} + E_{P}) / R + T_{DIFS}$ , where $L_{H}$ is the length of the header of the MAC packet and $L_{ACK}$ is the length of the ACK packet. $T_{SIFS}$ , is termed the short inter-frame space, is the duration after which the receiver responds with an ACK packet. $T_{DIFS}$ is the distributed interframe space which is the duration for which a contending user must sense the channel to be idle to identify the end of a transmission.

Lemma 1.
In a fully connected network using the p-persistent channel access scheme, if the attempt probability of station i is $p_{i}$ and that of station j is $p_{j} = \frac{w p_{i}}{1 + (w - 1) p_{i}}$ then j’s throughput equals w times i’s throughput.
Remark.
Note that the relation between the throughput of i and j is independent of the attempt probability of the other stations in the system.
Proof of Lemma 1.
In the throughput equation for station t given by (2) it can be seen that the values of $P_{I}$ and $P_{T}$ is the same for all stations. Therefore $S_{j} (p) / S_{i} (p)$ is given by $\frac{p_{j}}{1 - p_{j}} \frac{1 - p_{i}}{p_{i}}$ . Equating this term to w, the value of $p_{j}$ in terms of $p_{i}$ can be found which gives the required equation. □

If every station uses $p_{t} = w_{t} p / [1 + (w_{t} - 1) p]$ , then the system throughput is given by $\begin{array}{rcl} S (p, W) = \frac{E_{P} P_{T} P_{I}}{P_{I} σ + P_{T} P_{I} (T_{s} - T_{c}) + (1 - P_{I}) T_{c}}, \\ (3) & where P_{I} = \prod_{i = 1}^{N} \frac{1 - p}{1 + (w_{i} - 1) p}, P_{T} = \sum_{i = 1}^{N} \frac{w_{i} p}{1 - p} . \end{array}$

In the next theorem we show that the optimization problem in (1) can be reduced to $\begin{matrix} (4) & max_{p \in [0, 1]} S (p, W) . \end{matrix}$
Theorem 1.
The optimization problem in ( 1 ) can be reduced to an unconstrained maximization over a single variable give in ( 4 ) .
Proof.
From Lemma 1 it is seen that, for some arbitrary p, if the attempt probability of station t is $p_{t} = \frac{w_{t} p}{1 + (w_{t} - 1) p}$ $\forall t \in N$ then station t obtains a throughput $\frac{w_{t}}{\sum_{i = 1}^{N} w_{i}} S$ , where S is the system throughput. The attempt probabilities $p_{t}$ must necessarily satisfy this equation for obtaining a weighted fairness. Hence the optimization problem reduces to (4). Here the system throughput $S (p, W)$ is given by (3). Thus the N-dimensional optimization problem is reduced to a single variable problem. □

From the above theorem it is seen that to obtain the weighted fair throughput optimal policy it is sufficient to tune a single variable. We shall use an adaptive algorithm to tune the variable. Before presenting the algorithm, we explain the intuition that led to the design of the algorithm. Consider a fully connected network with N nodes. For this discussion we will assume that ever user is assigned a weight of 1. Bianchi has shown that the there exists a unique access probability (say $p^{⋆}$ ) for which the throughput is maximized [4]. Moreover, intuitively, it is clear that the throughput as a function of the access probability, denoted by $S (p, W)$ is monotone increasing for $p < p^{⋆}$ and monotone decreasing for $p > p^{⋆}$ . This is because for small p the medium is under-utilized, while for large p excessive collisions occur. Thus, it appears that the optimal access probability can be obtained using some kind of gradient algorithm, where gradient is $\partial S (p, W) / \partial p$ . But, to calculate the gradient, we need value of $S (p, W)$ for a given p. The throughput, in principle, can be computed at AP, and then AP can communicate the next value of p, computed using gradient ascent, to the nodes in ACK messages. A key challenge in the aforementioned policy is that the exact value of the throughput can be obtained only through measurements for a long time as the underlying system is probabilistic. Throughput measurement for a small duration can only yield noisy estimates. Waiting for a long duration affects the convergence time of the algorithm. Hence, we need techniques from stochastic approximation theory to circumvent the above problem. Specifically, we use Kiefer–Wolfowitz algorithm that we succinctly describe next.
3.2. Kiefer–Wolfowitz algorithm

In [17], Kiefer and Wolfowitz have given an algorithm to obtain the maximum of a regression function using its stochastic estimates. Consider a function $S (p)$ , and let the objective be to find the value of p that maximizes $S (\cdot)$ . However, the value of $S (p)$ is not known, but only a noisy estimate of it, namely $y (p)$ such that $E [y | p] = S (p)$ , is known. Here $E [\cdot]$ is the expectation operator. Consider two sequences ${a_{k}, k ⩾ 1}$ and ${b_{k}, k ⩾ 1}$ satisfying $b_{k} \to 0$ , $\sum_{k} a_{k} = \infty$ , $\sum_{k} a_{k} b_{k} < \infty$ , $\sum_{k} {(a_{k} / b_{k})}^{2} < \infty$ , and the following recursive updates for p: $\begin{matrix} (5) & p_{k + 1} = p_{k} + a_{k} \frac{y_{2 k} - y_{2 k - 1}}{b_{k}}, \end{matrix}$ where $y_{2 k}$ and $y_{2 k - 1}$ are noisy estimates of the function S at $p_{k} + b_{k}$ and $p_{k} - b_{k}$ , respectively. Specifically $E [y_{2 k}] = S (p_{k} + b_{k})$ and $E [y_{2 k - 1}] = S (p_{k} - b_{k})$ . Then, the recursive scheme of updating p given by (5) converges stochastically to the optimal value $p^{⋆}$ at which S is a maximum provided $S (p)$ satisfies the following regularity conditions:

$S (p)$ is a strictly quasi-concave function, i.e., there exists a $p = p^{⋆}$ such that $S (p)$ is strictly increasing for $p < p^{⋆}$ and $S (p)$ is strictly decreasing for $p > p^{⋆}$ .

There exists β and B such that $| p_{1} - p^{⋆} | + | p_{2} - p^{⋆} | < β$ implies $| S (p_{1}) - S (p_{2}) | < B | p_{1} - p_{2} |$ .

There exists ρ and R such that $| p_{1} - p_{2} | < ρ$ implies $| S (p_{1}) - S (p_{2}) | < R$ .

For every $δ > 0$ there exists a positive $π (δ)$ such that $| p - p^{⋆} | > δ$ implies $\begin{matrix} inf_{0 < ϵ < \frac{δ}{2}} \frac{| S (p + ϵ) - S (p - ϵ) |}{ϵ} > π (δ) . \end{matrix}$

The working of the algorithm can be understood by comparing it with the gradient ascent algorithm given as follows $\begin{matrix} p_{k + 1} = p_{k} + α_{k} \nabla S (p_{k}), \end{matrix}$ where $α_{k}$ is the step size. This algorithm cannot be directly applied in our case, since we do not know $S (p_{k})$ and hence $\nabla S (p_{k})$ . Hence, we wish to estimate the gradient through measurements. To obtain an estimate of the gradient at $p_{k}$ , we estimate the slope of the line passing through points $(p_{k} - b_{k}, S (p_{k} - b_{k}))$ and $(p_{k} + b_{k}, S (p_{k} + b_{k}))$ by measuring $S (p_{k} - b_{k})$ and $S (p_{k} + b_{k})$ . But, because of the stochastic nature of the system, $S (p_{k} - b_{k})$ and $S (p_{k} + b_{k})$ cannot be accurately obtained, rather only their noisy estimates $y_{2 k - 1}$ and $y_{2 k}$ , respectively, are obtained. Hence, the term $(y_{2 k} - y_{2 k - 1}) / b_{k}$ gives only the stochastic gradient of the function $S (\cdot)$ around $p_{k}$ . Now, to get close approximation of the gradient, one may take many measurements and use their average. This is achieved by choosing $a_{k} / b_{k} \to 0$ as $k \to \infty$ (ensured by $\sum_{k} {(a_{k} / b_{k})}^{2} < \infty$ ), which ensures that adjustments in $p_{k}$ are much smaller than the gradient range $b_{k}$ as long as regularity conditions 2, 3 and 4 are met. Now, by choosing $b_{k} \to 0$ as $k \to \infty$ , the algorithm ensures that the evaluated gradient approaches the actual gradient. Thus, the algorithm converges to $p^{⋆}$ without knowing the exact form of $S (\cdot)$ whenever noisy estimates of the function can be obtained. Next, we present adaptation of the Kiefer–Wolfowitz algorithm to our case.

Algorithm 1.

wTOP-CSMA algorithm to track the optimal value of the control variable p

3.3. wTOP-CSMA algorithm

To obtain a weighted fair optimal p-persistent scheme, we need to tune the control variable p. Each node can then use this control variable and the node’s weight to arrive at the attempt probability that the node should use. Tuning p can be done using the pseudo code presented in Algorithm 1. We term this algorithm wTOP-CSMA since this algorithm achieves a weighted fair throughput optimal system using the p-persistent scheme. Next, we explain Algorithm 1 in detail.

The first part of the algorithm is implemented at AP. The working of the algorithm can be understood as follows. From (5) it can be seen that for adaptively varying p we need $y_{2 k}$ and $y_{2 k + 1}$ . In our problem $y (p)$ corresponds to the estimate of the throughput when the attempt probability is p. Specifically $y_{2 k}$ is the estimated throughput when the attempt probability is $p_{k} + b_{k}$ and $y_{2 k + 1}$ is the estimated throughput when the attempt probability is $p_{k} - b_{k}$ . The estimate of the throughput $y (p_{k} \pm b_{k})$ can be obtained by measuring the bits transferred per second to the access point when the nodes use the attempt probability as $p_{k} \pm b_{k}$ (respectively). Hence the access point measures the throughput for a short duration (UPDATE_PERIOD in the algorithm) and then updates the attempt probability. Next we explain the steps of the algorithm for better clarity.

The algorithm has one parameter: UPDATE_PERIOD duration (denoted henceforth as Δ for brevity), and it starts by initializing variables $k = 2$ , $p = p_{val} + b_{k}$ and $p_{val} = 0.5$ . For p and $p_{val}$ any initial values between 0 and 1 is possible. The time is divided into frames of duration $2 Δ$ , and each frame is subdivided into segments of duration Δ. The variables k and $p_{val}$ are updated once at the end of each frame, while variable p is updated once at the end of each segment. In the first segment $p = p_{val} + b_{k}$ , while in the second segment $p = p_{val} - b_{k}$ . AP transmits the value of p in ACK messages. Since all the nodes can hear ACKs transmitted by AP, they can update their access probability using the value provided by AP and using their weight. Thus a node with weight $w_{t}$ on receiving the value of p in the ACK message sets the attempt probability to $p_{t} = w_{t} p / [1 + (w_{t} - 1) p]$ . The node then uses this updated attempt probability ( $p_{t}$ ) to access the channel. AP estimates throughput in each of the segments separately, where the throughput in the first (second, resp.) is denoted by $S_{plus}$ ( $S_{minus}$ , resp.). Here $S_{plus}$ and $S_{minus}$ indicate the terms $y_{2 k}$ and $y_{2 k - 1}$ in (5). $(S_{plus} - S_{minus}) / b_{k}$ is the stochastic gradient of the throughput function around the point $p_{val}$ . Using the stochastic gradient of the throughput around $p_{val}$ , $p_{val}$ is updated towards the direction of gradient. This update is the same as that in (5). We use $a_{k} = 1 / k$ and $b_{k} = 1 / k^{1 / 3}$ .

3.4. Performance guarantees of wTOP-CSMA

It can be seen that the wTOP-CSMA converges to the optimal transmission probability provided that the throughput function satisfies the regularity conditions. In the following theorem, we show that the throughput function indeed satisfies the regularity conditions. First, let us define $T_{s}^{⋆}$ and $T_{c}^{⋆}$ as the expected duration of a successful transmission and the expected duration of a failed transmission, respectively measured in units of slot durations (i.e. $T_{s}^{⋆} = T_{s} / σ$ and $T_{c}^{⋆} = T_{c} / σ$ ).

Theorem 2.
In a fully connected network, the throughput function of Weighted Fair TOP-CSMA $S (p, W)$ given by ( 3 ) is a quasi-concave function of p and satisfies the regularity conditions required by the Kiefer–Wolfowitz algorithm.
Proof.
To show that $S (p, W)$ is quasi-concave function of p we will show that there exists a $p^{⋆}$ such that $S (p, W)$ is non-decreasing for $p < p^{⋆}$ and non-increasing for $p > p^{⋆}$ . $S (p, W)$ can be re-written as $\begin{matrix} (6) & S (p, W) = \frac{E_{P}}{σ (T_{s}^{⋆} - T_{c}^{⋆} + C (p, W))}, \end{matrix}$ where $\begin{matrix} (7) & C (p, W) = \frac{T_{c}^{⋆}}{P_{T} P_{I}} - \frac{T_{c}^{⋆} - 1}{P_{T}}, \end{matrix}$ where $P_{I} = \prod_{i \in N} (1 - p_{i})$ , $P_{T} = \frac{p}{1 - p} \sum_{i \in N} w_{i}$ and $p_{i} = w_{i} p / [1 + (w_{i} - 1) p]$ , $\forall i \in N$ .

By differentiating (6) with respect to p, we obtain $\begin{array}{rcl} \frac{\partial S (p, W)}{\partial p} = - \frac{σ}{E_{P}} S^{2} (p, W) \frac{\partial C (p, W)}{\partial p}, where \\ \frac{\partial C (p, W)}{\partial p} = - \frac{T_{c}^{⋆}}{P_{T}^{2} P_{I}^{2}} (P_{T} \frac{\partial P_{I}}{\partial p} + P_{I} \frac{\partial P_{T}}{\partial p}) \\ + \frac{T_{c}^{⋆} - 1}{P_{T}^{2}} \frac{\partial P_{t}}{\partial p} . \end{array}$ Note that $\begin{matrix} \frac{\partial P_{I}}{\partial p} = - P_{I} \sum_{i \in N} \frac{1}{1 - p_{i}} \frac{\partial p_{i}}{\partial p}, \frac{\partial P_{T}}{\partial p} = \frac{1}{{(1 - p)}^{2}} \sum_{i \in N} w_{i} . \end{matrix}$ Thus $\partial C (p, W) / \partial p$ can be written as $\begin{array}{rcl} \frac{\partial C (p, W)}{\partial p} = - \frac{\sum_{i \in N} w_{i}}{{(1 - p)}^{2} P_{I} P_{T}^{2}} f (p, W), where \\ f (p, W) = T_{c}^{⋆} (1 - p \sum_{i \in N} \frac{1 - p}{1 - p_{i}} \frac{d p_{i}}{d p}) - (T_{c}^{⋆} - 1) P_{I} . \end{array}$

It is clear that $\partial S (p, W) / \partial p$ and $f (p, W)$ have the same signs. By substituting for $1 - p_{i}$ and $d p_{i} / d p$ it can be seen that $\begin{matrix} f (p, W) = T_{c}^{⋆} (1 - \sum_{i \in N} p_{i} - P_{I}) + P_{I} . \end{matrix}$ Also, $\begin{array}{l} \frac{\partial f (p, W)}{\partial p} = & - T_{c}^{⋆} \sum_{i \in N} \frac{\partial p_{i}}{\partial p} (1 - \frac{P_{I}}{1 - p_{i}}) \\ - \sum_{i \in N} \frac{\partial p_{i}}{\partial p} \frac{P_{I}}{1 - p_{i}} . \end{array}$ Since $\partial p_{i} / \partial p > 0$ and $0 ⩽ P_{I} / (1 - p_{i}) ⩽ 1$ , $\partial f (p, W) / \partial p < 0$ . Thus $f (p, W)$ is a monotonically decreasing function of p with $f (0, W) = 1$ and $f (1, W) = - (N - 1) T_{c}^{⋆}$ . Therefore, there exists a unique $p^{⋆} \in {p : 0 < p < 1}$ such that $f (p^{⋆}, W) = 0$ . This is the maxima of the function $S (p, W)$ . Furthermore, $f (p) > 0$ for $p < p^{⋆}$ and $f (p, W) > 0$ for $p > p^{⋆}$ . Thus, $\partial S (p, W) / \partial p > 0$ for $p < p^{⋆}$ implying that $S (p, W)$ increases monotonically for $p < p^{⋆}$ . Similarly, $\partial S (p, W) / \partial p < 0$ for $p > p^{⋆}$ implying that $S (p, W)$ decreases monotonically for $p > p^{⋆}$ . Hence, $S (p, W)$ is a strictly quasi-concave function in the range $0 < p < 1$ .

Furthermore, since $S (p, W)$ , $C (p, W)$ and $f (p, W)$ are differentiable and bounded functions of p, it follows that $\partial S (p, W) / \partial p$ is also a continuous and bounded function of p for $0 < p < 1$ . Thus, the other regularity conditions are also satisfied. □

Figure 3 shows the bell shaped nature of the curve as proved in the above theorem. Note that $\begin{matrix} (8) & p^{⋆} \approx \frac{1}{N \sqrt{T_{c}^{⋆} / 2}} \end{matrix}$ that is obtained in [4] is an approximate solution to $\partial S (p, W) / \partial p = 0$ when weights of all users are 1.
4. A throughput optimal exponential backoff policy in a fully connected network

In a fully connected network, it has been shown that the exponential backoff based scheme can be replaced with a p-persistent CSMA scheme without affecting the performance; this is, however, not obvious in a network with hidden nodes. As seen from the simulations later, in a network with hidden nodes, it is possible that the optimal p-persistent scheme can perform worse even than the standard 802.11 protocol. This shows that an exponential backoff based scheme may have an advantage when hidden nodes exist. Hence, in this section we design an exponential backoff based scheme that can be tuned to achieve optimal performance in a fully connected network. We use this scheme instead of standard IEEE 802.11 DCF to better understand the merit of the exponential backoff based schemes in presence of hidden terminals. Since, our main motivation is only to assess the need of exponential backoff based schemes in networks with hidden terminals, for simplicity, we only consider throughput optimal schemes, i.e. we assume that all nodes have the same weight.

First, let us formalize our notion of the exponential backoff based schemes:

Definition 3.
An access mechanism is said to be exponential backoff based if (1) the contention window size lies in ${2^{i} {CW}_{min} : i = 0, \dots, m}$ for some predefined parameters ${CW}_{min}$ and m, and (2) the contention window size is doubled on a transmission failure except when the contention window size is at the predefined maximum value, in which case it is kept the same.

Note that the exponential backoff based schemes are defined in terms of their actions on transmission failures only, and their actions on transmission successes are not specified. Thus, designing an optimal backoff based scheme amounts to optimally choosing a backoff stage for a terminal when its transmission is successful. We consider the following generic class of the exponential back-off based schemes in which each node uses a reset distribution denoted by $q = [q_{0}, q_{1}, \dots, q_{m}]$ . After a successful transmission, a node chooses contention window size $2^{i} {CW}_{min}$ w.p. $q_{i}$ .
Remark.
Observe that the class we consider is not the class of all exponential back-off based schemes. One example of the exponential back-off based scheme that lies outside the class that we consider is the following: Each node maintains reset distribution ${\tilde{q}}_{j}$ for $j = 0, \dots, m$ , and chooses back-off stage i w.p. ${\tilde{q}}_{j i}$ on transmission success given that the node’s current back-off stage is i. However, it suffices to consider this generic class as schemes in this class can achieve the same performance as any exponential backoff based scheme with the appropriate choice of q. This is because of the following observation: In exponential backoff based schemes, the throughput of the system is determined by the node’s attempt probability which is given by a fixed point solution [4]. Hence the performance of the system is defined by the attempt probability of the exponential backoff scheme for a given number of nodes. It is intuitive that the smallest (largest, resp.) attempt probability is achieved if the user chooses stage m (0, resp.) after every successful transmission. Further, by using an appropriate probability distribution of choosing the backoff stage on a success any attempt probabilities in this range can be achieved. Thus, the class of exponential backoff policies that we consider can achieve the same range of attempt probability as that by the entire class of the exponential backoff based policies, and hence the same throughput values.

Now, to obtain optimal exponential back-off scheme, we need to obtain appropriate reset distribution q. Thus, we need to tune m parameters. It is well known that convergence rate of on-line tuning schemes decreases rapidly as the number of variables to be tuned increases. In our key contribution of the section, we show that it suffices to tune only two parameters. To this end, let us define RandomReset schemes.
Definition 4.
A $RandomReset (j; p_{0})$ is an exponential backoff policy with parameters $j \in {0, \dots, m - 1}$ and $p_{0} \in [0, 1]$ . The scheme chooses contention window $2^{j} \times {CW}_{min}$ w.p. $p_{0}$ and contention window $2^{i} \times {CW}_{min}$ w.p. $(1 - p_{0}) / (m - j)$ for every $i \in {j + 1, \dots, m}$ .

We term $p_{0}$ as the reset probability. We show that the optimal policy lies in the domain of RandomReset schemes. Designing optimal RandomReset policy requires tuning of two variables, namely, the backoff stage j and the reset probability $p_{0}$ . To design on-line algorithm for optimal tuning of RandomReset scheme, we use the following technique: We fix j and tune $p_{0}$ for $RandomReset (j; p_{0})$ using Kiefer–Wolfowitz algorithm. This step is the same as that in wTOP-CSMA (see Algorithm 1) except here updates are applied to the reset probability $p_{0}$ instead of attempt probability p. Now, if the value of $p_{0}$ drops below a fixed threshold $δ_{l}$ (≈ 0), then we reset j to $j + 1$ and $p_{0}$ to 0.5, except at boundary $j = m - 1$ . On the other hand, if $p_{0}$ rises above a fixed threshold $δ_{h}$ (≈ 1), then we reset j to $j - 1$ and $p_{0}$ to 0.5, except at boundary $j = 0$ . Even after reseting the parameters, we continue using Kiefer–Wolfowitz algorithm to tune $p_{0}$ . Intuition behind the reset operation is as follows: Fix j. If the maximum throughput is achieved in the range $0 < p_{0} < 1$ , then it implies that the throughput is optimal. However, if it is achieved at $p_{0} = 0$ ( $p_{0} = 1$ , resp.), then it implies that a better throughput can be achieved by increasing (decreasing, resp.) the backoff stage to decrease (increase, resp.) the attempt probability further. Hence by increasing or decreasing j appropriately the system can be tuned until the optimal throughput is achieved. We term this algorithm the Throughput Optimal RandomReset CSMA algorithm (TORA-CSMA algorithm). Algorithm 2 gives the pseudo code for TORA-CSMA. Next, we establish optimality of TORA-CSMA.
Theorem 3.
In a fully connected network, TORA-CSMA is optimal amongst the class of exponential backoff policies.
Remark.
Though we claim the optimality of TORA-CSMA only in the class of exponential back-off schemes, a more general result is true. Specifically, it can be shown that there exist $N_{l}$ and $N_{h}$ such that for every $N \in {N_{l}, N_{l} + 1, \dots, N_{h}}$ TORA-CSMA is throughput optimal in the class of all policies. The bounds $N_{l}$ and $N_{h}$ on the number of users in the system appears as the attempt probability under exponential back-off policies is bounded below and above by $τ_{l} > 0$ and $τ_{h} < 1$ , respectively. This is because ${CW}_{min}$ and m are fixed. Since for optimal throughput the attempt probability should vary as $Θ (1 / N)$ with N (see (8)), exponential back-off policies cannot be optimal for every N. Nonetheless, the range of N for which TORA-CSMA is optimal among all policies is significant.

Two key steps in the proof of Theorem 3 are: (1) We prove that the throughput function of the $RandomReset (j; p_{0})$ policy is a quasi-concave function of $p_{0}$ for a fixed j. (2) We show that the RandomReset policy for j varying from 0 to $m - 1$ can achieve the same attempt probability as that achieved by any general class of exponential based backoff schemes. The detailed proof is presented in the Appendix.

Algorithm 2.
TORA-CSMA algorithm to track the optimal value of j and $p_{0}$
5. Discussion on the algorithms

In this section, we discuss advantages and limitations of the proposed algorithms. The wTOP-CSMA and TORA-CSMA algorithms are optimal in a fully connected network. The key feature of these algorithms that separates them from the existing proposals is that these do not depend upon any underlying model, rather they act directly on the gradient of the throughput function. This feature makes them more robust towards scenarios in which proposed mathematical models do not hold.

Note that both the algorithms are centralized. While most of the existing algorithms are distributed algorithms, in our opinion, for infrastructure based WLANs implementation of the centralized algorithms would not pose many problems. Furthermore, having the intelligence in a centralized controller would facilitate easy modifications for performance improvements. Indeed, with the advent of IEEE 802.11e standard [16], the process of shifting responsibility of smart, socially optimal decision making to the centralized controller has already begun. Moreover, in a dynamic scenario in which users arrive and depart, the distributed algorithm may not converge to the socially optimal point as the users already in the system will have to compete with the new arrivals that tend to have very different initial values of control parameters.

Now, our algorithms require that the parameters be passed in ACK packets. Though under TORA-CSMA it is sufficient for a node to process its own ACK, under wTOP-CSMA a node has to process all the ACK packets which is not desirable. However, wTOP-CSMA can be modified to use beacon frames to send the parameters.

Comparing the two algorithms, it can be seen that using a p-persistent CSMA provides the benefit of being able to achieve weighted fairness in a straightforward fashion. This is not easy in TORA-CSMA, since the throughput relation to the reset parameter $p_{0}$ is through a fixed-point solution and a closed form expression does not exist. In a fully connected network the wTOP-CSMA algorithm would suffice in providing an optimal throughput. However, it is not completely clear if this observation is true in a network with hidden nodes. As seen through simulations later, in a network with hidden nodes an exponential backoff scheme could provide better throughput. This shows that the exponential backoff schemes may not be eliminated all together.

Note that we have not considered channel errors in our model. Here, we describe how these can be incorporated in our analysis. We consider connected network and p-persistent CSMA. Let us first consider the impact of channel errors. We assume that the channel errors are i.i.d. across the transmissions from a user and independent across the transmissions of differ users. Let $q_{t}$ denote the probability that a packet transmitted by t is delivered correctly to the AP. Let ${\tilde{S}}_{t} (p)$ denote the throughput achieved by t for p-persistent CSMA with attempt probability vector p in the system with unreliable channel. Now, from (2), it follows that $\begin{matrix} (9) & {\tilde{S}}_{t} (p) = q_{t} S_{t} (p) . \end{matrix}$ This is because in p-persistent CSMA the attempt probability is not affected by the success or the failure of the transmission. Thus, all the slot durations remain unaltered, resulting into the above relation. Now, let us first consider the problem of designing throughput optimal policy (see Definition 1). Here, $p_{t} = p$ for every t. Thus, we need to maximize $S_{t} (p) \sum_{t} q_{t}$ . Since $\sum_{t} q_{t}$ is a constant, it follows, using similar arguments as that in the proof of Theorem 2, that the function $S_{t} (p) \sum_{t} q_{t}$ is a quasi-concave function of p and satisfies the regularity conditions required by the Kiefer–Wolfowitz algorithm. Thus, our approach yields the throughput optimal policy in the unreliable channel case as well. Note that the AP or users need not even know the channel error probabilities.

Now, let us consider the issue of designing weighted fair throughput optimal schemes (see Definition 2) in presence of channel errors. Note that we need, for every i, j, ${\tilde{S}}_{i} (p) / w_{i} = {\tilde{S}}_{j} (p) / w_{j}$ . From (9) it follows that we need $S_{i} (p) / {\tilde{w}}_{i} = S_{j} (p) / {\tilde{w}}_{j}$ , where ${\tilde{w}}_{t} = w_{t} / q_{t}$ . Thus, we have the same problem as the one discussed in Section 3.1. However, in this setting, a user t must know $q_{t}$ to set its attempt probability. One way to know $q_{t}$ is to determine it from the channel condition, transmit power and transmission rate used. Other way is to estimate it based on the feedback received from the AP. This is also challenging if AP cannot differentiate between packet loss due to collision and channel error. However, many of the recent approaches propose a method to differentiate between the channel errors and collision in WiFi networks (see e.g. [6,10]). If the channel errors can be detected, then $q_{t}$ can be estimated and our scheme can be used to achieve the optimum performance.

Generalizing our analysis for exponential backoff based scheme in presence of channel errors in not straightforward unless the channel errors can be detected. This is because for the given value of $p_{0}$ , attempt probabilities of various users will be different. However, when packet loss can be detected, then we can modify TORA-CSMA as follows to achieve throughput optimality. We use $RandomReset (j; p_{0})$ when the user’s transmission do not collide; otherwise we increase the backoff stage. This guarantees that each user has the same attempt probability. Thus, again the system throughput equals throughput of a user multiplied by $\sum_{t} q_{t}$ . Hence, TORA-CSMA maximizes the system throughput. Next, we discuss the performance of the proposed algorithms in presence of the hidden nodes.

6. Performance of the policies in the presence of hidden nodes

In a fully connected network a number of different algorithms have been proposed for throughput improvement. All these suggestions arrive at the required transmission probability that provides optimal throughput. If the number of stations in the system is known, then this transmission probability can be directly computed. However, this reasoning cannot be extended to the case of hidden nodes. This is because even if the number of stations are known beforehand, the number of possible configurations in which these stations could exist is large (exponential in N). Here, configurations refer to various possibilities for $T_{t}$ for each t. It is required for the system to find out the exact configuration to perform optimization and arrive at a suitable transmission probability. This is clearly impractical, and hence the existing solutions cannot be used in such a scenario. For example, in the IdleSense protocol the target number of idle slots is a fixed constant. However, this target value changes in the presence of hidden nodes based on how many hidden node pairs exists. Hence, it is not possible to fix a target value of the idle slots a-priori.

Analysis of hidden nodes has been an open problem for over a decade. There has been different attempts at providing a mathematical model to analyze hidden nodes [31]. However such attempts perform a simplification or consider restricted conditions. Obtaining an analytical model for hidden nodes is a complicated task owing to various reasons. One main hurdle is that in the presence of hidden nodes the system can no longer be modelled using an embedded Markov Chain. The renewal equation used by Bianchi is no longer applicable. Hence in [31] a fixed width slot model is studied for a system with two nodes hidden from each other. In this work this model is shown for a system with two nodes. However, this model becomes intractable even for small number of nodes (greater than 2).

The lack of a mathematical model acts as an obstruction in the design of adaptive algorithms. Algorithms that perform optimally in a fully connected network cannot be shown to perform optimally (or even better than standard 802.11) when hidden nodes are introduced. In our work, while we do not eliminate this problem due to hidden nodes we show through extensive simulation that our algorithm can perform better than standard 802.11 even when hidden nodes exist. The reason for this can be explained intuitively as follows. The two optimal policies defined in Sections 3 and 4, namely, wTOP-CSMA and TORA-CSMA, are defined to track the actual throughput. Specifically, these algorithms attempt to maximize the throughput directly using a stochastic approximation technique by taking a short term measurement of the actual throughput obtained from the system, and then dynamically tune the system parameters to increase the throughput. The major advantage of these algorithms are that they have no binding on the mathematical model, but depend only on how the throughput varies as a function of the control variable. As long as the throughput is a differentiable quasi-concave function of the control variable, the Kiefer–Wolfowitz algorithm can obtain its optimal value. Unfortunately, it is not possible to prove analytically (even with a reasonable degree of approximation) that the function is differentiable and quasi-concave in presence of hidden terminals. Though a mathematical model does not exist when hidden nodes exist, it can be expected that the throughput is still a quasi-concave function of the attempt probability. This is because for a small access probability, the throughput is small as the medium is under-utilized while for a large access probability, again the throughput is small because of excessive collisions. Thus, the throughput should increase until certain value of the access probability and decrease for the higher values, thereby yielding quasi-concavity. Further in extreme situations where the throughput is not quasi-concave, the system would still tune the probability to one of the local maxima. Hence it can be expected that the wTOP-CSMA and the TORA-CSMA algorithm perform better than standard 802.11. We show this through simulations in ns3. Also through simulation we obtain the plot of the throughput as a function of the attempt probability. For the numerous random topologies that we simulated it was observed that the throughput is a quasi-concave function of the control variable. Thus except for extreme cases, the proposed algorithms would perform reasonably well even when hidden nodes exists.

7. Simulation results

The IdleSense, wTOP-CSMA and TORA-CSMA algorithms are implemented in Network Simulator 3 (ns3) and their performance was compared without and with hidden nodes. The parameters used in the simulations are given in Table 1. The last two parameters, namely ns3::YansWifiPhy::EnergyDetectionThreshold and ns3::YansWifiPhy::CcaMode1Threshold ensure that nodes placed at a distance greater than 24 m do not sense the transmissions of each other. Such nodes behave as hidden nodes.

In the simulation of wTOP-CSMA and TORA-CSMA, the UPDATE_PERIOD was defined to be 250 ms. The IdleSense algorithm was implemented with a target average idle slots of 3.1 idle slots per transmission [14].

7.1. Performance of wTOP-CSMA in a fully connected network

The simulation of wTOP-CSMA was carried out in a fully connected network by assigning weight to each node. The results of the simulation are shown for 10 nodes in Table 2. As can be seen the normalized throughput obtained by every node is the same. Also a total throughput of 22 Mbps is obtained.

Table 2
Simulation results of wTOP-CSMA algorithm

Node Weight Throughput (Mbps) Normalized Throughput (Throughput/Weight)

1 1 1.06624 1.06624

2 1 1.06069 1.06069

3 1 1.0603 1.0603

4 2 2.17046 1.08523

5 2 2.19471 1.09736

6 2 2.11976 1.05988

7 3 3.18249 1.06083

8 3 3.18581 1.06194

9 3 3.18676 1.06225

10 3 3.19088 1.06363

Total Throughput = 22.4181 Mbps

Node	Weight	Throughput (Mbps)	Normalized Throughput (Throughput/Weight)
1	1	1.06624	1.06624
2	1	1.06069	1.06069
3	1	1.0603	1.0603
4	2	2.17046	1.08523
5	2	2.19471	1.09736
6	2	2.11976	1.05988
7	3	3.18249	1.06083
8	3	3.18581	1.06194
9	3	3.18676	1.06225
10	3	3.19088	1.06363
Total Throughput = 22.4181 Mbps

In the subsequent part, for comparison it is assumed that all users have equal weights.

Fig. 2.

Comparison of throughput of standard 802.11 protocol, IdleSense and TOP-CSMA and TORA-CSMA policies in fully connected network.

Fig. 3.

Throughput of the p-persistent CSMA versus the attempt probability.

Fig. 4.

Throughput of the RandomReset-CSMA policy versus $p_{0}$ , for $j = 0$ .

7.2. Comparison of performance of wTOP-CSMA, TORA-CSMA and IdleSense in a fully connected network

In Fig. 2 the throughput plots of the IEEE 802.11, IdleSense, TOP-CSMA and TORA-CSMA as a function of the number of stations are shown. It is observed that TOP-CSMA and TORA-CSMA perform much better than the Standard 802.11 protocol. Also the throughputs obtained are as good as that obtained using IdleSense. However one advantage of the TORA-CSMA over the TOP-CSMA can be seen by comparing Figs 3 and 4. The RandomReset-CSMA exhibits a more flat characteristics about the maxima while the p-persistent CSMA has a sharper fall from the maxima. This indicates that if the control variable oscillates around the optimal the throughput variations would be lesser for TORA-CSMA than that for TOP-CSMA.

7.3. Performance in the presence of hidden nodes

We generate the networks with hidden nodes as follows: The nodes are created by randomly placing them in a disc of suitable radius with the Access Point at the center. The radius of the disc determines whether hidden nodes exist. Also, larger the radius more is the probability of hidden nodes. For the parameters that we configured in NS3 hidden nodes occur when the distance between the nodes is more than 24 m. Hence we consider the radius to be 16 m or 20 m for creating situations with hidden nodes scenarios. Scenario with radius 16 m (20 m, resp.) is referred to as case 1 (case 2, resp.) in the following discussion.

7.3.1. Quasi-concavity of throughput

For using the Kiefer–Wolfowitz algorithm it was required that the throughput is a quasi-concave function of the control variable. For a network with hidden nodes, since this cannot be shown analytically, we present evidence of it through simulations. We verify the required by placing nodes randomly in a radius of 16 m or 20 m which creates a hidden node scenario. Subsequently, we compute the throughput for various values of the control variables in the generated network. In Fig. 5, the variation of the throughput of a p-persistent CSMA as a function of p is shown, and in Fig. 6, the throughput of the RandomReset CSMA as a function of $p_{0}$ is shown. It can be seen that the throughput is indeed a quasi-concave function of the control variable. This characteristic has been noticed for a number of iterations of the simulation with different seeds for the random number generator. This indicates that Algorithms 1 and 2 can be applied to obtain the optimal throughput.

Fig. 5.

Throughput of the p-persistent CSMA versus the attempt probability in the presence of hidden nodes.

Fig. 6.

Throughput of the RandomReset-CSMA policy versus $p_{0}$ in the presence of hidden nodes.

7.3.2. Throughput comparison

The comparison of the performance of IEEE 802.11, TOP-CSMA and TORA-CSMA, averaged over 100 random topologies, is shown in Fig. 7 and in Fig. 8 for the two scenarios. One key observation is that, unlike in the fully connected network, TORA-CSMA performs better than the wTOP-CSMA in the network with hidden nodes. However as discussed in Section 4, the TORA-CSMA algorithm may not be the optimal exponential backoff algorithm. The results show evidence that exponential backoff algorithm perform better than an optimal p-persistent channel access scheme when hidden nodes exist.

Fig. 7.

Comparison of throughput of standard 802.11 protocol, TOP-CSMA and TORA-CSMA policies with nodes distributed in a disc of radius 16 m.

Fig. 8.

Comparison of throughput of standard 802.11 protocol, TOP-CSMA and TORA-CSMA with nodes distributed in a disc of radius 20 m.

Table 3

Comparison of average idle slots and throughput obtained for 40 users with and without hidden nodes by different schemes (hidden nodes case 1 and case 2 refers to two runs of the simulation in ns3)

	IdleSense algorithm

	Avg Idle Slots	Throughput (Mbps)
Without hidden nodes	3.27849	21.5732
With hidden nodes-I	3.29951	12.4798
With hidden nodes-II	3.36866	0.497839

	wTOP-CSMA algorithm

	Avg Idle Slots	Throughput (Mbps)
Without hidden nodes	4.86102	22.0138
With hidden nodes-I	9.97689	17.1832
With hidden nodes-II	25.127	10.455

From the simulation another inference that can be made is the reason for the failure of algorithms like IdleSense. In Table 3 the idle slots obtained by the IdleSense algorithm and the wTOP-CSMA algorithm is shown for a typical network topology. The first row shows the results when no hidden nodes are present while the second and third row show the results when hidden nodes are introduced. In each case IdleSense algorithm achieves a target average Idle slots per transmission value close to 3.1 as desired. However, from the results of wTOP-CSMA it can be seen that the target idle slots achieved is different for different scenarios. While it is close to 3 (4.8) when no hidden nodes exist, in the presence of hidden nodes it varies as 9 and 25. This shows that based on the configuration of the hidden nodes, the optimal idle slot per transmission value would vary. Hence it is not possible to choose a particular value when using the IdleSense algorithm. However, since our algorithm does not depend on system parameters, it still manages to track the optimal and achieve a relatively higher throughput.

7.4. Dynamic scenarios and convergence analysis

Another factor to be considered in the implementation of an adaptive protocol is the speed of convergence of the protocol, and the effectiveness of the protocol in changing conditions. In this case, the changes refer to the change in the number of active nodes N. We study the performance of wTOP-CSMA algorithm when N changes at predefined time instants. In Fig. 9, the variations in throughput as a function of time is shown (the number of users is indicated along the right y-axis). Note that the throughput does not change very much even as N changes when no hidden nodes exists. From Fig. 10, it can also be seen that the system quickly adapts to changes and converges to the optimal probability value. Thus, the algorithm suggested can handle dynamic conditions by modifying the control variable on-line as the number of users vary.

Fig. 9.

Variation of throughput as the number of stations vary.

Fig. 10.

Variation of p as the number of stations vary.

8. Literature survey

There has been a number of attempts at designing algorithms that improve the throughput of IEEE 802.11. The key issue is the degradation of the throughput with increasing number of nodes. In this section we review the existing work on throughput improvement of IEEE 802.11.

One of the first studies of the standard 802.11 was done in [4] where the author provides a mathematical model to analyze the throughput of 802.11. The same author in [5] also suggests an adaptive algorithm to improve the throughput of the protocol. The improvement is based on the idea that the optimal attempt probability is a function of number of users and hence by estimating the number of users the attempt probability can be chosen appropriately. However, the estimate of the number of users require the current value of the attempt probability and there is no way to ensure that every station uses the same attempt probability. For newly arriving stations the attempt probability being used is not known and hence it may cause unfairness to new users. Further, the optimal access probability depends on $T_{c}^{*}$ which may vary based on the average packet length, the PHY layer used and the transmission rates.

In [8,9] the authors again reduce the standard 802.11 to a p-persistent CSMA, and attempt to dynamically vary the attempt probability. The idea in this work is to keep the expected collision duration and the expected idle duration equal by tuning the attempt probability. To achieve this it is required to estimate the number of active stations which is done by measuring the average number of idle slots in a transmission time. However, this method does not work when hidden nodes are present as a proper estimate of the collision probability and average idle slots is no longer possible. The Asymptotic Optimal Backoff Mechanism defined in [7] is an extension of the work in [8,9] where the optimal transmission probability is found by attempting to keep the slot utilization level at an optimum value called the Asymptotic Contention limit. This slot utilization level is achieved only asymptotically. Further this measure of the slot utilization cannot be done in the presence of hidden nodes.

In [27], the authors suggest a slow Contention Window decrease rather than an immediate reset. This improves the throughput since the stations are less aggressive on success. However there is no guarantee of optimality of this protocol and as seen from the results presented in their work though there is an improvement over the standard 802.11 the throughput still degrades as a function of number of users.

In [15], a dynamic optimization is provided which estimates the approximate number of users and sets a contention window based on the range in which the number lies. This also uses a centralized AP based approach for optimization but requires an estimate of the number of users. The optimal contention window is transmitted in the beacon frame with which every station updates the ${CW}_{min}$ value.

Another improvement is the Idle Sense protocol given in [14]. IdleSense tunes the attempt probability so that the expected number of idle slots between transmissions remains a constant. Apart from throughput improvement the authors discuss about other factors like short term fairness and time fairness of the protocol. The short term fairness in the protocol is obtained as a result of reducing the binary backoff to a single p-persistent model. Further time fairness is an extension of the p-persistent CSMA model to provide a transmission probability that depends on the rate of transmission. Both these techniques can be extended to any p-persistent CSMA system including our system. However, as shown in our work the simple p-persistent CSMA cannot perform optimally in the presence of hidden nodes and hence a binary backoff is preferred. Furthermore in the Idle Sense protocol the optimal number of idle slots depends again on $T_{c}^{*}$ and varies based on the expected packet lengths and the PHY parameters. The optimal number of idle slots cannot be found out analytically in the presence of hidden nodes as there is no mathematical model defined. Further the optimal number of idle slots is expected to depend on the percentage of hidden nodes and cannot be dynamically found.

In a recent work in [26] the authors suggest an improved backoff algorithm that looks at the history of channel utilization and uses a backoff that is non-binary. That is the algorithm attempts to increase the backoff window by α rather than a fixed value of 2. Like [27], though the protocol does perform better than IEEE 802.11, it does not perform optimally.

The idea of a weighted fair throughput allocation, discussed in our work, has also been dealt with in other works. In [28] the authors arrive at the condition required for achieving weighted fair throughput allocation. Also the contention window to be used by each user for obtaining an optimum throughput is found. However the value of the optimal contention window depends on the number of users in each class. Thus every user in the network must be aware of the number of priority classes and number of users in each class. In [12] the authors consider only two classes of users. The contention window is arrived at numerically and hence requires an offline calculation based on the number of users in each class. In [21], the authors suggest a modification to the algorithm to support weighted fairness. In this work while the throughput allocation is proportional to the weight of the user, it is not optimal. While it is shown that different attempt probabilities provide different throughput, no algorithm to achieve the optimal throughput is suggested. Unlike these works, our algorithm requires no knowledge of the number of users in different classes. The user is free to choose a weight independent of the other users and still obtain the optimal weighted fair allocation of the bandwidth.

Recently in [23,29] the authors propose an algorithm to achieve α-fairness for a general value of α. Here, every user chooses an attempt probability that maximizes a certain utility function given the attempt probabilities of others. This process is done iteratively until the attempt probabilities converge. While the proposed algorithm provides good results, it also has some limitations. The algorithm requires that every user knows the attempt probability of every other user. This information can be obtained by message passing or through estimation. In a message passing technique, the number of messages passed for every iteration of the algorithm is of the order of the number of users in the system. Estimation, on the other hand, requires every user to process all packets in the network which is not desirable from a power consumption viewpoint. Also, the algorithm assumes that packet transmissions complete within a single slot. This assumption models a slotted Aloha kind of systems, and is far from an IEEE 802.11 based system in which packet transmission spans over multiple slots and CSMA is used. Other notions of fairness are also considered, e.g. [2] considers time fairness, [3,13] considers proportional fairness and [19] explores equivalence between these two fairness notions.

Game theoretic approach for rate adaptation and/or channel selection with utility being users’ throughput is consider in [11,24]. However, the price of anarchy is shown to significant [11]. Thus approach to find an efficient Nash equilibrium is required.

In [1,22], authors consider not saturated case and obtain throughput expression under some assumptions on the arrival process. The authors here do not propose the optimal scheme.

Another area of related study is the modeling of hidden nodes and the performance measurements in the presence of hidden nodes. Very few work exists that attempt to model the hidden nodes scenario and predict the system performance. One of the recent works in [24,25,31] show that existing modeling techniques would not work in the presence of hidden nodes and new approaches are required. In [31], the authors suggest a fixed slot technique and are able to model the system only when there are two nodes present. For a more general setup the system becomes too complicated to analyze mathematically. In [25], authors model the system as a continuous time Markov chain and using certain approximation obtain throughput expression for a given topology. Here, authors’ experiment demonstrate that the throughput is an quasi-concave function of the attempt probability. In [24], the game theoretic approach is proposed. The schemes proposed here may not be optimal.

9. Conclusion

In this work, we have a suggested a simple modification to the CSMA/CA protocol of the 802.11 standard. Unlike previous work, here the throughput is directly maximized by tuning a single control variable using stochastic maximization technique, specifically using the Kiefer–Wolfowitz algorithm. Two policies are suggested – one in which the control variable is the attempt probability of the p-Persistent CSMA and another in which the control variable is the probability of returning to the lowest backoff stage on success. The modified algorithms wTOP-CSMA and TORA-CSMA are shown to perform significantly better even in the presence of the hidden nodes. It is seen that a binary backoff method works much better in the presence of hidden nodes as compared to the optimal p-Persistent CSMA. Further the wTOP-CSMA can also guarantee weighted fairness in a fully connected network.

Footnotes

Proof of Theorem 3

First, we define some terms that are used in the proof. Let $\hat{τ} (q)$ denote the attempt probability of nodes, which are using exponential back-off scheme with the reset distribution q. For obtaining the attempt probability, we use the following assumption: the conditional probability of collision is independent of the backoff stage of the users. Note that the same assumption is used by Bianchi in his seminal paper [4]. Let ${\hat{τ}}_{c} (q)$ denote the attempt probability for reset distribution q and the conditional collision probability c. Similarly, let $τ (j; p_{0})$ and $τ_{c} (j; p_{0})$ denote the attempt probability and the attempt probability given the conditional collision probability c, respectively, under the $RandomReset (j; p_{0})$ policy. From the Markov Chain analysis of the system (similar to that in [4]), the term ${\hat{τ}}_{c} (q)$ is given by $\begin{array}{rcl} {\hat{τ}}_{c} (q) = \frac{κ_{0}}{\sum_{j = 0}^{m - 1} q_{j} α_{j} (c)}, where \\ (10) & α_{j} (c) = (1 - c) \sum_{i = j}^{m - 1} 2^{i} c^{i - j} + 2^{m} c^{m - j} . \end{array}$ Here $κ_{j} = 1 / (2^{j - 1} \times {CW}_{min})$ for $j = 0, \dots, m$ . The conditional probability of collision is then given by $\begin{matrix} (11) & c = 1 - {(1 - {\hat{τ}}_{c} (q))}^{N - 1} . \end{matrix}$ The term $\hat{τ} (q)$ is then obtained as a fixed point solution of (10) and (11). The fixed point is unique [4]. Also, note from (10), the attempt probability given the conditional attempt probability c for $RandomReset (j, p_{0})$ is given as $\begin{matrix} (12) & τ_{c} (j; p_{0}) = \frac{κ_{0}}{p_{0} α_{j} (c) + \frac{1 - p_{0}}{m - j} \sum_{i = j + 1}^{m} α_{i} (c)} . \end{matrix}$

Following lemma, proves the uniform continuity of $\hat{τ} (\cdot)$ .

The monotonicity property can be understood from Fig. 11. From the plot it can be seen that since $τ_{c} (p_{0}; 0)$ is a monotonically increasing function of $p_{0}$ the curve for $τ_{c} (p_{0}; 0)$ for a higher value of $p_{0}$ lies above a curve corresponding to a lower value of $p_{0}$ . Also the fixed point is the intersection of this curve with the curve for the plot of c as a function of $τ_{c}$ . From the plot it can be seen that the as $p_{0}$ increases intersection point shifts towards the top right indicating a higher attempt probability and a higher conditional collision probability.

In the following lemma, we first establish some structural properties of the term in $α_{j} (c)$ in (10).

Now, we establish monotonicity of the attempt probability under RandomReset policy.

Next, we show that the $RandomReset (j; p_{0})$ achieves the entire range of attempt probabilities that can be achieved using the class of exponential back-off policies.

Now we prove that the throughput obtained by a $RandomReset (j; p_{0})$ policy (denoted by $\tilde{S} (j, p_{0})$ ) is a quasi-concave function of the reset probability $p_{0}$ for a fixed j. Note that $\tilde{S} (j, p_{0}) = S (τ (j; p_{0}), 1)$ , where $1$ is a N-dimensional unit vector.

The quasi-concavity can also be seen in Fig. 4.

Thus the TORA-CSMA algorithm which uses the Kiefer–Wolfowitz stochastic maximization technique converges to the optimal value of $p_{0}$ that maximizes the system throughput.

References

[1]

Alazemi,

Margolis,

Choi,

Vijaykumar and

Roy, Stochastic modelling and analysis of 802.11 DCF with heterogeneous non-saturated nodes, Computer Communications 30(18) (2007), 3652–3661.

[2]

Babu,

Jacob and

Brijith, A novel scheme for achieving time based fairness in IEEE 802.11 multirate wireless LANs, in: IEEE ICN’05, 2005.

[3]

Banchs,

Serrano and

Oliver, Proportional fair throughput allocation in multirate IEEE 802.11e wireless LANs, Computer Networks 13(5) (2007), 649–662.

[4]

Bianchi, Performance analysis of the IEEE 802.11 distributed coordination function, IEEE Journal on Selected Areas in Communications 18(3) (2000), 535–547.

[5]

Bianchi,

Fratta and

Oliveri, Performance evaluation and enhancement of the CSMA/CA MAC protocol for 802.11 wireless LANs, in: Seventh IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC’96, October 1996, Vol. 2, pp. 392–396.

[6]

Biaz and

Wu, Loss differentiated rate adaptation in wireless networks, in: IEEE WCNC’08, 2008.

[7]

Bononi,

Conti and

Gregori, Runtime optimization of IEEE 802.11 wireless LANs performance, IEEE Transactions on Parallel and Distributed Systems 15(1) (2004), 66–80.

[8]

Calì,

Conti and

Gregori, IEEE 802.11 protocol: Design and performance evaluation of an adaptive backoff mechanism, IEEE Journal on Selected Areas in Communications 18(9) (2000), 1774–1786.

[9]

Calì,

Conti and

Gregori, Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit, IEEE/ACM Transactions on Networking 8(6) (2000), 785–799.

10.

[10]

Cardoso and

Rezende, Accurate hidden Markov modeling of packet losses in indoor 802.11 networks, IEEE Communications Letters 13(6) (2009), 417–419.

11.

[11]

Chaporkar,

Proutiere and

Radunovic, Rate adaptation games in wireless LANs: Nash equilibrium and price of anarchy, in: IEEE INFOCOM’10, 2010.

12.

[12]

R.-G.

Cheng,

C.-J.

Chang,

C.-Y.

Shih and

Y.-S.

Chen, A new scheme to achieve weighted fairness for WLAN supporting multimedia services, IEEE Transactions on Wireless Communications 5(5) (2006), 1095–1102.

13.

[13]

Daneshgaran,

Laddomada,

Mesiti and

Mondin, On the throughput allocation for proportional fairness in multirate IEEE 802.11 DCF, in: IEEE CCNC’09, 2009.

14.

[14]

Heusse,

Rousseau,

Guillier and

Duda, Idle Sense: An optimal access method for high throughput and fairness in rate diverse wireless LANs, in: SIGCOMM’05: Proceedings of the 2005 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, New York, NY, USA, 2005, pp. 121–132.

15.

[15]

Hui,

Xing,

Hewu,

Zhang and

S.C.

Yuan, Dynamic optimization of IEEE 802.11 CSMA/CA based on the number of competing stations, in: 2004 IEEE International Conference on Communications, June 2004, Vol. 1, pp. 191–195.

16.

[16]IEEE 802.11, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications, IEEE, March 2007.

17.

[17]

Kiefer and

Wolfowitz, Stochastic estimation of the maximum of a regression function, The Annals of Mathematical Statistics 23(3) (1952), 462–466.

18.

[18]

Kim,

Verma,

Choi and

Qiao, Collision-aware adaptation in multi-rate WLANs: Design and implementation, Computer Networks 54(17) (2010), 3011–3030.

19.

[19]

Krishnan and

Chaporkar, Equivalence between proportional fairness and time-based fairness in multi-rate wireless LANs, in: IEEE INFOCOM’10, 2010.

20.

[20]

Kushner and

Yin, Stochastic Approximation Algorithms and Applications, Applications of Mathematics, Springer-Verlag Telos, 1997.

21.

[21]

J.-S.

Liu, Achieving weighted fairness in IEEE 802.11-based WLANs: Models and analysis, WTOC 7(6) (2008), 605–615.

22.

[22]

Malone,

Duffy and

Leith, Modeling the 802.11 distributed coordination function in nonsaturated heterogeneous conditions, IEEE/ACM Transactions on Networking 15(1) (2007), 159–172.

23.

[23]

Mohsenian-Rad,

Huang,

Chiang and

Wong, Utility-optimal random access: Reduced complexity, fast convergence, and robust performance, IEEE Transactions on Wireless Communications 8(2) (2009), 898–911.

24.

[24]

Najafabadi and

Constantinou, A game theoretic model for wireless medium access control in the presence of hidden terminals, in: IEEE PIMRC’13, London, UK, September 2013, pp. 1731–1736.

25.

[25]

Nardelli and

Knightly, Closed-form throughput expressions for CSMA networks with collisions and hidden terminals, in: IEEE INFOCOM’12, Orlando, FL, March 2012.

26.

[26]

Nasir and

Albalt, Improved backoff algorithm for IEEE 802.11 networks, in: International Conference on Networking, Sensing and Control, ICNSC’09, March 2009, pp. 1–6.

27.

[27]

Qiang,

Aad,

Barakat and

Turletti, Modeling and analysis of slow CW decrease IEEE 802.11 WLAN, in: 14th IEEE Proceedings on Personal, Indoor and Mobile Radio Communications, PIMRC 2003, September 2003, Vol. 2, pp. 1717–1721.

28.

[28]

Qiao and

Shin, Achieving efficient channel utilization and weighted fairness for data communications in IEEE 802.11 WLAN under the DCF, in: Tenth IEEE International Workshop on Quality of Service, 2002, pp. 227–236.

29.

[29]

Rad,

Huang,

Chiang and

Wong, Utility-optimal random access without message passing, IEEE Transactions on Wireless Communications 8(3) (2009), 1073–1079.

30.

[30]

Tan,

Fang,

Zhang,

Chen,

Shi,

Zhang and

Zhang, Fine-grained channel access in wireless LAN, in: ACM SIGCOMM, 2010.

31.

[31]

Tsertou and

Laurenson, Revisiting the hidden terminal problem in a CSMA/CA wireless network, IEEE Transactions on Mobile Computing 7(7) (2008), 817–831.

On-line algorithm for optimizing throughput performance of wireless LANs

Abstract

Keywords

1. Introduction

1 Though, we have not considered packet loss due to channel errors, such can be incorporated in our framework in a straightforward fashion provided that the channel errors are independent and identically distributed over all transmissions.

3.1. Problem formulation

3.4. Performance guarantees of wTOP-CSMA

6. Performance of the policies in the presence of hidden nodes

7. Simulation results

7.1. Performance of wTOP-CSMA in a fully connected network

7.3. Performance in the presence of hidden nodes

7.3.1. Quasi-concavity of throughput

9. Conclusion

Footnotes

Proof of Theorem 3

References

¹
Though, we have not considered packet loss due to channel errors, such can be incorporated in our framework in a straightforward fashion provided that the channel errors are independent and identically distributed over all transmissions.