Abstract
As the penetration of wireless networks increase, number of neighboring networks contending for the limited unlicensed spectrum band increases. This interference between neighboring networks leads to large systems of locally interacting networks. We investigate whether the shortterm fairness of this system of networks degrades with the system size and density if transmitters employ random spectrum access with carrier sensing (CSMA). Our results suggest that (a) shortterm fair capacity, which is the throughput region that can be achieved within the acceptable limits of shortterm fairness, reduces as the number of contending neighboring networks, i.e., degree of the conflict graph, increases for random regular conflict graphs where each vertex has the same number of neighbors, (b) shortterm fair capacity weakly depends on the network size for a random regular conflict graph but a stronger dependence is observed for a grid deployment. We demonstrate the implications of this study on a citywide WiFi network deployment scenario by relating the shortterm fairness to the density of deployment. We also present related results from the statistical physics literature on longrange correlations in large systems and point out the relation between these results and shortterm fairness of CSMA systems.
1 Introduction
Popularity of wireless access technologies manifests itself in the form of ever increasing penetration of wireless local area networks. For example, it is estimated that household penetration of WiFi networks is 61% in the USA, 73% in the UK, and 80% in South Korea as of 2011 [1].
This trend has a number of profound implications, particularly for densely populated urban areas. First, as more WiFi networks that are in close physical proximity share a common spectrum, the amount of spectrum per network drops due to interference. This effect cannot be controlled in unlicensed bands, but its extent may be bounded by estimating the maximum number of neighboring networks that is possible in view of the limited WiFi transmission range.
Second, and more subtly, dense deployment of WiFi networks leads to large systems of weakly interacting networks. That is, while each network contends with its immediate neighbors to access the spectrum, it also interacts obliviously with further away networks through intermediaries that form chains of neighbors. In that case, whether or not the performance of individual networks depend on the size of the alluded system is of critical importance: Because while this latter effect cannot be controlled either, in contrast to the former effect, the system size cannot easily be estimated and tends to be very large in metropolitan areas. Hence, if performance of individual networks indeed degrades persistently with the aggregate system size, then the resulting operating regime would essentially be practically unacceptable under dense deployment of such networks.
The objective of this article is to investigate key parameters that delineate practically relevant regimes of dense spectrum usage. Our focus is on delaysensitive applications and random spectrum access with carrier sensing (CSMA). Specifically, we seek succinct conditions that predict excessive dependence between channel access delay and system size. Our ultimate interest is in understanding the relationship among throughputs, access delays, and system size; and thereby in identifying throughput levels that entail admissible access delay regardless of the system size.
Using a Markov model, it was recently shown that randomized CSMA is throughputoptimal. That is, if a collection of pernetwork throughputs in a given system topology can be attained by some transmission scheduling algorithm, then it can also be attained by a randomized CSMA algorithm that operates with appropriate parameters [2,3]. Such feasible throughputs are coined the throughput region for that system topology. It was also observed that in certain parts of the throughput region CSMA displays shortterm unfairness [4]: Namely, theoretically computed throughputs emerge as time averages only if such averages are computed over longtime intervals. Over shorttime intervals, however, one constellation of networks in the system tends to enjoy virtually unobstructed channel access whereas the remaining networks starve. Hence, in the short term, channel access is unfair among constituent networks of the system. Although different constellations take effect in the long term interval, this operational regime leads to high temporal variation in access delay. When it exists, this variation becomes more pronounced with increasing system size [5].
This phenomenon is related to the mixing time of the underlying system dynamics, and in turn to the concept of phase transitions. In statistical physics, phase transition refers to the existence of multiple equilibrium distributions in a graphical model of infinite size. In a finite, prelimit graphical model, a phase transition typically manifests itself in the form of a unique equilibrium distribution that has multimodal nature. That is, most of the probability measure is concentrated around several quasistable states. Transitions between such states become rare as the system size increases, leading to multiple distinct equilibrium distributions in the limit.
Alternatively, such shortterm behavior is suggested by existence of longrange dependence in a graphical system model. In more specific terms, if states of distant nodes in the graph are strongly correlated (either negatively or positively), then such correlation is indicative of the constellations that take effect over shorttime horizons.
Our main contributions are as follows:
• We claim that the shortterm fairness among the interacting wireless transmitters is affected by the degree of the conflict graph of these transmitters if the conflict graph is a random regular graph where each vertex has the same number of neighbors. A denser deployment results in an increase in the number of contending neighbors of a network and our results suggest that the practically useful portion of the throughput region reduces as the number of neighboring networks increases.
• We demonstrate the implications of our study on a practical citywide WiFi deployment scenario. Our results indicate that shortterm fairness has to be sacrificed to improve coverage in such a system. To improve coverage, the density of the deployment has to be increased which causes the nodal degree of the system to increase. This in turn reduces shortterm fairness.
• We discuss if there is a reduction in the performance of interacting networks as the system size increases. Our results suggest that there is a weak dependence on the system size if the density of deployment is kept unchanged and the deployment has a random regular conflict graph. On the other hand, the performance of networks with a grid conflict graph may severely degrade with system size if all networks operate at high throughputs.
• We highlight the results from the statistical physics and theoretical computer science literatures on the longrange dependence in physical systems and identify a relationship between CSMA systems and physical systems. Despite the discrepancies between the physical models and the practical networking scenarios, we point out similarities between the shortterm fair capacity region and the phase transition thresholds of the physical models.
The remainder of this article is organized as follows: Section 2. surveys related work and Section 3. describes the system model. We explain the shortterm fairness metrics that we use in Section 4. A mathematical analysis of the shortterm fairness of the tree topology is given in Section 5. Section 6. presents a simulationbased analysis of the tree, grid, and random topologies. Section 7. illustrates the tradeoff between shortterm fair capacity and coverage for a practical WiFi deployment scenario. Several observations on the relationship between the phase transitions of the hardcore model and the CSMA network are presented in Section 8. A summary and discussion of results are given in Section 9.
2 Related work
The studies that investigate the fairness of a CSMA system can roughly be categorized into two classes: First class of studies deal with the fairness of fixed rate CSMA systems where each transmitter attempts to access the channel at the same rate. Second class of studies investigates the fairness of CSMA systems where the transmitters adapt their channel access rates according to recently proposed distributed CSMA algorithms.
For fixedrate CSMA systems, unfairness in the longterm average throughputs of transmitters has been investigated. Starvation of an intermediate node in a multihop system topology was first noted in [6]. A fundamental cause of the longterm unfairness of CSMA was shown to be the selforganization of transmission patterns [7]. Unfairness in a large CSMA system caused by the unfair advantage of border nodes at high access rates was analyzed in [8]. To eliminate border effects, channel access rates which equalize throughputs are proposed for linear networks and 2 × N grids [9,10]. Determination of channel access rates which achieves target throughputs is investigated in [11].
Despite these studies that investigate longterm fairness of a fixed rate CSMA system, there are not many studies that deal with the shortterm fairness problem. Shortterm fairness of longterm fair grid and line topologies were analyzed briefly in [8]. For a given topology, a method of analysis is proposed using the Markov chain of independent sets [12] but this analysis requires enumeration of all independent sets which is computationally difficult.
Recently, adaptive CSMA algorithms that can achieve throughput optimality have been proposed [2,3,13,14]. These algorithms solve the longterm fairness problem of CSMA systems by adapting the channel access rate of nodes according to their demands. In these algorithms, nodes in an unfair position will increase their channel access probability as their queue lengths grow. This mechanism balances the average throughputs of transmitters in the long run.
However, throughput allocation among transmitters may be unfair in the short term even when the average throughput distribution is fair in the long run. Shortterm unfairness becomes more apparent as throughputs increase and, as a result, variation in the channel access delay of transmitters increases. Degradation in the shortterm fairness as the throughput optimality is achieved is investigated in [4]. Several bounds for delay are proposed [5,1518] and methods for minimizing the delay are devised [1921]. To reduce delay, appropriate selection of the rate adaptation function is also investigated [2224].
In this study, we investigate the shortterm fairness of a fixed rate CSMA system and investigate the effect of system size, density, and topology on the shortterm fairness. Previous studies on fixedrate CSMA systems are often limited to linear and grid topologies. We study here also random regular topologies that demonstrate very different shortterm fairness characteristics from the grid topology. Besides, to the best of the authors’ knowledge, the relationship between the degree of a network and its shortterm fairness has not been shown before. We demonstrate that this relationship may result in a tradeoff between the coverage and the shortterm fairness of a WiFibased access network.
3 System model and studied topologies
3.1 System model
We study a system of transmitters distributed over an area. The interference relationships between these transmitters are modeled using a conflict graph in which each node represents a transmitter and two nodes are connected with a link if their corresponding transmitters interfere with each other. We consider two transmitters as interfering if they are in the carrier sensing range of each other. From now on, we use the terms node, transmitter, and access point interchangeably throughout the article.
We study the idealized CSMA model which is analyzed in [2,6,25]. In this model, it is assumed that carrier sensing is instantaneous and always successful, which leads to a zerocollision system. Since interfering transmitters cannot be in transmission concurrently in the idealized CSMA model, the set of transmitting nodes at a given time forms an independent set of the conflict graph.
We assume that all transmitters in the system are saturated, that is, transmitters always have data to transmit. Each transmitter in the CSMA system probes the channel at random times according to a Poisson point process and starts transmission when it finds the channel idle. The mean waiting time between two consecutive probing instants, 1/λ, determines the aggressiveness of a transmitter where λ is defined as the probing rate. The lengths of transmissions are exponentially distributed with mean 1.
3.2 Studied conflict graph topologies
In this study, we analyze three different conflict graph topologies: tree, grid, and random regular topologies. In urban areas, independently distributed WiFi networks can be expected to form a fairly random conflict graph. However, in a large campus or corporate network, transmitters may be placed in a more structured manner which may result in a grid conflict graph topology. Although not common in practice, tree topology is suitable for mathematical analysis and it has been commonly used in deriving bounds in the statistical physics literature.
We study a tree in which every node except leaf nodes have b children as shown in Figure 1a. The degree of nodes in the tree is d = b + 1 except the leaf nodes and the root node. The height of the tree and the number of nodes in the tree are denoted by h and n, respectively. The grid topology we simulated is an N × N grid with d = 4 as shown in Figure 1b. We also generated connected random regular topologies, where each node has a degree of d, using the software developed by Viger [26]. A random regular topology with d = 3 can be seen in Figure 1c. Shortterm fairness analysis of irregular random topologies appears difficult because they typically fail to achieve longterm fairness when all nodes have the same access rate due to the inhomogeneity of the topology. Since longterm fairness is a prerequisite for evaluating the shortterm fairness, we limited our study to random regular graph topologies where longterm fairness is always achieved since each node has the same degree.
Figure 1. Studied topologies. (a) The tree topology that we study. Each node has b children except leaf nodes. (b) The N × N grid. (c) A sample regular random topology with a degree of 3.
We have also investigated the conflict graph of a mesh deployment of WiFi access points. To cover an area with access points, it has been shown that a mesh deployment provides better coverage than a totally random deployment [27]. In such a deployment, number of conflicting neighbors of an access point is determined by the density of deployment. When the access points interfere with their nearest neighbors, the conflict graph becomes the grid topology described above. As the density increases, the conflict graph becomes a higherdegree graph. We investigate the effect of the density of deployment on shortterm fairness and coverage in Section 7.
4 Shortterm fairness metrics
4.1 Shortterm fairness horizon
Shortterm fairness horizon is defined as the minimum time required for the transmitters to achieve a fair share of the network [28]. To measure the shortterm fairness horizon, network is monitored for a predetermined window duration. If the throughput distribution over the window is not sufficiently fair, the window size is increased. The minimum window size which attains a fair throughput distribution is defined as the shortterm fairness horizon. To calculate the shortterm fairness horizon, a measure of longterm fairness is needed to determine the point after which the network is considered fair. The most widely used and intuitive longterm fairness measure is the Jain’s fairness index [29]. We consider the network longterm fair when a Jain’s fairness index of 0.95 is achieved. It should be noted that the measured throughputs in simulations are noisy. The particular simulation technique that we use is explained in Section 6.1.
Shortterm fairness horizon is originally measured in time units. However, if the probing rates of transmitters are too low, the network converges to equilibrium very slowly. This behavior results in artificially large values for the shortterm fairness horizon at low probing rates. Instead of measuring time until fairness, counting the average number of transmissions per transmitter leads to a healthier comparison between different scenarios. This metric normalizes the effect of probing rate allowing a better comparison of the fairness performances at different probing rates. For that reason, we consider the number of transmissions per transmitter required to achieve fairness as the shortterm fairness horizon in this study.
4.2 Shortterm fair capacity region
For a given conflict graph, throughput of a node refers to the fraction of time that the node transmits, and the throughput region of the conflict graph refers to the collection of achievable pernode throughputs. In this study, we are mainly interested in how much of the throughput region can be achieved within the acceptable limits of shortterm fairness. We define this subset of the throughput region as shortterm fair capacity region. In order to quantify the shortterm fair capacity, a shortterm fairness horizon threshold has to be determined such that the network is considered shortterm unfair when the shortterm fairness horizon is beyond this threshold. In a study which is focused on developing a fair MAC protocol [30], the authors observed that it takes 80–140 packets per user for the IEEE 802.11 standard to become fair. Considering this result, we select 100 transmissions per node as a threshold for shortterm fairness. We also used 50 transmissions per node as another threshold which corresponds to a stricter fairness requirement. However, these choices are not restrictive; the behavior of the capacity region does not significantly change with the selection of the threshold as it will be demonstrated in Section 6.
4.3 Successive transmission probability
Another metric that can be used for measuring shortterm fairness is to calculate the probability of a node making a successive transmission before any of its neighbors has a chance to transmit. If this probability is high, it indicates that a node captures the channel for a long time and its neighbors starve during this period.
For a random access protocol, a successive transmission probability of
Successive transmission probability is a local measure of shortterm fairness which can be computed using the statistics of a single node and its neighbors. Shortterm fairness horizon, however, is a global metric which requires states of all nodes have to be taken into account. For that reason, successive transmission probability appears to be a more tractable metric for mathematical analysis. We present an analysis of the shortterm fairness of the tree conflict graph using this metric in the next section.
5 Mathematical analysis for a tree
In this section, we develop an approximate fairness model for a tree conflict graph using the successive transmission probability as the fairness metric.
We are interested in determining the probability that a node starts transmission before
its neighbors after finishing its transmission. In order to evaluate the successive
transmission probability of a node, we refer to Kelly’s work
[31] which gives the conditional probability of a node being in transmission when its
parent is not transmitting as a function of probing rate. For the tree topology, let
p be the probability of the child being idle given that its parent is idle. The value
of this probability typically depends on the node, but for large trees nodes that
are far from the leaves tend to have similar values due to symmetry. Kelly’s analysis
identifies a common value in the limit of an infinite tree, which serves as a convenient
approximation for large finite trees. Namely, it is shown that p is the positive solution of
To illustrate our approach let us consider a special case of a tree with d = 2 which is an infinite line topology. Let Nodes −2 to 2 be adjacent nodes in this
line as shown in Figure
2. Each node probes the channel at rate λ. Let Node 0 be at the end of its transmission. At this point, its neighbors (Nodes
−1 and 1) are idle; and, Nodes −2 and 2 are idle with probability p. Node 0 has a higher chance of capturing the channel: Even if Node −1 or 1 probe
the channel before Node 0, they may find the channel busy because Nodes −2 and 2 may
be transmitting. Node 0 will probe the channel after a duration exponentially distributed
with rate λ. Nodes −1 and 1 will also probe the channel after exponentially distributed durations
with λ but they may find the channel busy because Nodes −2 and 2 may be in transmission
with probability
Figure 2. States of nodes in a line topology. Node 0 is transmitting, Nodes −1 and 1 are therefore idle and Nodes −2 and 2 are active with probability p.
If we generalize this formula to a tree with a degree d, we get
where p is the positive solution of
For d > 3, we cannot obtain p in closed form which prohibits obtaining a direct relationship between probing rate,
λ, and successive transmission probability, P_{s}. However, it is possible to establish a relationship between throughput and successive
transmission probability since
where 0 < T < 0.5.
At very low probing rates, the successive transmission probability of a node is independent of the global topology where it is solely determined by the degree of a node. Since all nodes have the same probing rate, the probability of a node to perform a successive transmission before its neighbor is given by
At very high probing rates, however, successive transmission probability of a node converges to 1, i.e.,
T = 0.5 is the maximum achievable throughput by all nodes in the network because it is not possible for more than half of the nodes in the tree to be active concurrently. In this case, once a node has a chance to transmit, it tends to transmit repeatedly at successive probing instants, severely degrading shortterm fairness.
The assumption of
6 Simulation study
We now study the effects of several network attributes on shortterm fairness. We investigate three different conflict graph topologies: tree, grid, and random regular.
6.1 Simulation method
In this section, we use the shortterm fairness horizon as the fairness metric. We also measure the successive transmission probability for the tree topology in order to evaluate the accuracy of proposed analysis.
We measure the shortterm fairness horizon in our simulations using the following procedure: we keep a throughput counter for each node; this counter records the total throughput that the node has gained until the current time in the simulation. Using these throughput values, we repeatedly check for the Jain’s index of the network as the simulation continues. If the network achieves a Jain’s index of 0.95, we record the number of completed transmissions per node until that moment as the shortterm fairness horizon. At this moment, we reset the counters and again wait for the network to reach a fairness index of 0.95. We sample the shortterm fairness horizon 50 times by repeating this procedure and take the average of these values.
In order to measure the shortterm fairness horizon, the network has to achieve a fairness index of 0.95 in the long run; that is, it must be longterm fair. To establish longterm fairness, probing rates of nodes have to be adjusted such that all nodes have the same longterm throughput. However, computing the probing rates that result in a fair equilibrium distribution is nontrivial [9]. Although there is a closed form expression for probing rates which equalizes throughputs for the tree topology [31], there is no such expression for N × N grids and random topologies.
In the simulations of grid and random topologies, we assign the same probing rate to each node and assume that they can achieve a fairness index of 0.95 in the longrun. This assumption is valid for our simulations because all simulations achieved a fairness index of 0.95. Simulating large random topologies is also of help because the effect of locally unfair throughput distributions can be balanced in a large network.
In the tree topology, leaf nodes have an important advantage over the internal nodes; they have a single neighbor whereas internal nodes have d neighbors. For that reason, leaf nodes face less competition and they can gain higher throughputs than internal nodes. Since the leaf nodes form a large portion of nodes in the tree, the probing rates of leaf nodes have to be adjusted such that they have the same throughput with internal nodes. Using the analysis in [31], we select the probing rates such that the throughput distribution is longterm fair.
6.2 Tree topology
Figure 3a depicts the shortterm fairness horizon for tree topologies with different values of d as a function of λ. At the same probing rate, shortterm fairness horizon of higher degree topologies is shorter than lower degree topologies. However, nodes in the higherdegree networks need to probe the channel at a higher rate than the nodes in the lowerdegree networks in order to achieve the same throughput. For that reason, comparing the performance of topologies with different degrees at the same probing rate is not fair.
Figure 3. Shortterm fairness horizon of the tree topology with different degrees; (a) as the probing rate increases (b)as the average throughput increases. Shortterm fairness thresholds of Th = 50 and 100 transmissions per node are also shown as horizontal dashed lines.
The relationship between fairness and throughput is more relevant for our purposes than the relationship between fairness and probing rate because we are interested in characterizing a practically useful throughput region. Figure 3b shows how shortterm fairness horizon changes as a function of throughput. At low throughputs, shortterm fairness horizon does not depend on d. As the throughput increases, there is a sharp increase in the shortterm fairness horizon. The maximum value of the throughput where shortterm fairness can be satisfied decreases as d increases. The reason behind this behavior is that the nodes are more dependent on each other in densely connected networks at high throughputs. When the average throughput in the network is low, transmission of a node is rarely prevented by its neighbors. So, nodes behave almost independently and shortterm fairness does not depend on the global properties of the system such as the degree. As the probing rates increase, dependence between nodes increases. A node frequently finds the channel busy since at least one of its neighbors is already transmitting. This phenomenon is more apparent in higher degree networks because nodes are more densely connected. So, the nodes in higherdegree topologies starve for a long time at high probing rates that are required for achieving high throughputs.
This relationship between the fairness and the degree of the tree demonstrates an important limitation of random access networks working at high throughput. A centralized scheduler can provide a throughput of 0.5 to all nodes in the tree independent of the degree by alternating transmissions between nodes at even and odd distances to the root node. Since the transmissions are alternated between nodes at each time step, shortterm fairness of this scheduler is optimum. On the other hand, fairness of the CSMA network significantly depends on the degree and average throughput of the network.
Since shortterm fairness is significantly affected by the degree and throughput, it is natural to ask how much of the throughput region can be achieved within the acceptable limits of shortterm fairness. We have previously defined this practically useful throughput limit as the shortterm fair capacity region. The shortterm fairness thresholds of 50 and 100 transmissions are depicted as horizontal lines in Figure 3b. Throughputs corresponding to these thresholds are computed using interpolation and plotted in Figure 4 where the shortterm fair capacity of a tree network under CSMA is plotted as d increases. In this plot, degrees omitted from Figure 3b are also included to give a better picture of the shortterm fair capacity region. For d = 2, the network can achieve a throughput of 0.44 in a shortterm fair manner for a threshold of 100. However, for d = 18, the maximum throughput which can be obtained under shortterm constraints drops to 0.22.
Figure 4. Shortterm fair capacity of the tree topology as the degree increases.
Figure 5 presents simulation results for trees with different heights but with the same number of children, b = 3, i.e., d = 4 for internal nodes. The tree with h = 1 has a very good fairness performance since it consists of only four nodes. For very small networks consisting of a few nodes, the number of nearby nodes which influence the state of a node is very small. As extra nodes are added to the neighborhood of a node, the number of transmitters affecting the state of the transmitter increases. This increase results in a decrease in shortterm fairness. However, as the network grows beyond the neighborhood, the influence of the newly added nodes declines gradually. For that reason, shortterm fairness becomes almost independent of the network size for sufficiently large topologies, i.e., shortterm fairness does not degrade further once the network size becomes sufficiently large.
Figure 5. Shortterm fairness horizon of the tree topology as the height of the tree increases. Internal nodes in all trees have d = 4.
6.2.1 Successive transmission probability
We now present the mean number of successive transmissions of a node and compare the results with the analysis given in Section 5. We collected transmission statistics of each node during the simulations presented in the previous part. Statistics of only internal nodes are used because leaf nodes have only a single neighbor resulting in different transmission statistics from internal nodes.
We compare fairness performances of tree topologies with different degrees using this new metric. Figure 6 plots the mean number of successive transmissions of a node as the throughput increases along with the mean number of transmissions computed using the proposed fairness model using a binomial assumption. The proposed model gives a closedform relationship between the successive transmission probability and throughput as given by (4). The successive transmission probability is computed using the assumption that probability of the secondary neighbors of a node being idle is independent of the number of its previous transmissions. Since this assumption gets closer to reality as d increases, the model is very accurate especially for higher degree trees. At a very low throughput, the successive transmission probability of a node is lower for a higher degree graph as given by (5). However, as the throughput increases, the higher degree graphs show worse shortterm fairness because of the increased dependence between nodes.
Figure 6. Mean number of successive transmissions as the average throughput increases. Dashed lines plot the results of the proposed model
Figure 6 is very similar to Figure 3b which shows that both metrics, shortterm fairness horizon and number of successive transmissions, characterize the shortterm fairness behavior in a similar manner. Since behaviors of both metrics resemble, we do not present the successive transmission probability statistics in the rest of this article.
6.3 Grid topology
We now examine the shortterm fairness properties of the grid topology. Since the degree of the grid topology is fixed at 4 for internal nodes, the only parameter that we investigate is the network size. We simulated the grid topology for n = 50 × 50,100 × 100, and 150 × 150.
Figure 7 shows how shortterm fairness of the grid topology changes as the average throughput in the network increases. It may not be possible to operate the CSMA protocol under reasonable shortterm fairness requirements above an average throughput of 0.35 because the shortterm fairness horizon reaches extremely high values. At such high throughputs, shortterm fairness of the grid topology also depends on the network size. At a throughput of 0.35, shortterm fairness horizon of the 100 × 100 grid network is twice of the horizon of the 50 × 50 grid. At this throughput, shortterm fairness horizon of all simulated topologies is larger than 1,000 transmissions which can be considered unacceptable for practical purposes.
Figure 7. Shortterm fairness horizon of the grid topology for three different dimensions.
Grid topology exhibits undesirable shortterm fairness properties mainly because it has two maximal independent sets which correspond to the blacks and whites of the checkerboard pattern. The throughput distribution of the network favors either of these maximal independent sets at high probing rates. Since these maximal independent sets have no elements in common, transition from one to the other occurs rarely at high probing rates resulting in long starvation periods for some nodes.
6.4 Random topology
We now investigate the shortterm fairness properties of randomly generated contention graph topologies. For each d, ten random topologies each having 5,000 nodes are generated as described in Section 3.2. Shortterm fairness horizon of these topologies are computed for increasing throughputs and averaged to obtain a shortterm fairness horizon plot for each d.
Figure 8 shows how shortterm fairness horizon changes as the throughput increases. It is very similar to the tree topology: at low throughputs, shortterm fairness horizon weakly depends on d but highdegree topologies have substantially larger shortterm fairness horizon than lowdegree topologies at higher throughputs. Shortterm fairness thresholds of 50 and 100 are also depicted as horizontal dashed lines. Throughputs obtained at these thresholds are plotted in Figure 9 where we observe that shortterm fair capacity degrades as network degree increases. The reduction in the shortterm fair capacity as the degree increases is more apparent in the random topology than the tree topology as will be compared later.
Figure 8. Average shortterm fairness horizon of randomly generated topologies with different degrees as the average throughput increases. Shortterm fairness thresholds of Th = 50 and 100 transmissions per node are also shown as horizontal dashed lines.
Figure 9. Shortterm fair capacity of the randomly generated topologies as the degree increases with shortterm fairness thresholds of Th=50 and 100.
Figure 10 plots how shortterm fairness horizon changes with the size of the random network. The plot is obtained by simulating randomly generated topologies with d = 4, 6, and 10 for n = 1,000, n = 5,000, and 20,000. It is observed that the shortterm fairness of the random topology does not depend significantly on n for large networks.
Figure 10. Average shortterm fairness horizons for the randomly generated topologies with different network sizes.
These results imply that the performance of a system of randomly placed networks does not degrade with the system size if the number of neighbors is kept fixed. However, as the density, along with d, increases, a performance reduction in the shortterm fairness is observed.
6.5 Comparison of different topologies
Figure 11 compares fairness performances of tree, grid, and random topologies all with d = 4. At low throughputs, shortterm fairness is marginally affected by the network topology because nodes do not interact strongly with each other. However, as the throughput increases, nodes interact strongly and topological structure becomes more important. Among the topologies we consider, tree topology has the best shortterm fairness performance mainly because interdependency between nodes in the tree topology is lower than any other topology: tree can be separated into two independent parts by removing a single node. Low interdependency results in good shortterm fairness performance because network does not spend too much time around some transmission patterns.
Figure 11. Shortterm fairness horizons for the tree, grid and random topologies as the throughput increases. All three topologies have d = 4.
In contrast to the tree topology, grid topology exhibits high dependency between nodes which results in a poor fairness performance. The active nodes of the grid topology tend to be in one of the two maximal independent sets so that nodes which do not belong to the active transmission pattern wait for a long time to become active. Random topology lies between the tree and the grid topologies in terms of shortterm fairness.
Figure 12 plots the shortterm fair capacities of the tree and random topologies as d increases. A tree with d = 2 is a line topology; similarly, a connected random topology with d = 2 is also a line topology. So, both topologies have the same capacity at d = 2. As d increases, the difference between these two topologies increases. At d = 18, shortterm fair capacity of the random topology is 53% of the tree topology.
Figure 12. Shortterm fair capacities for tree and random topologies as the degree increases with shortterm fairness threshold Th = 50.
This comparison demonstrates that although the network degree is the main determining factor for the shortterm fairness, it is not the sole influencing factor. Other characteristics such as the structure of independent sets and network topology may also affect the shortterm fairness performance. Also, it should be noted that we here present averages taken over a large number of topologies; however, shortterm fairness of each individual topology may not monotonically degrade with d.
7 Practical implications on the deployment of WiFi networks
Municipal wireless networks become increasingly widespread to provide wireless connectivity for cities. For example, Oklahoma City provides wireless coverage for a 555squaremile area using 1,100 mesh nodes and 900 mobile nodes. As well as municipalities, private companies are also interested in providing urban wireless coverage. For instance, Google provides citywide WiFi access for Mountain View, California.
Our findings may have some implications on the performance of such citywide networks regarding their deployment density. Densely deploying WiFi access points may be required to provide a better coverage of the mobile users. On the other hand, as the density of deployment increases, the number of interfering neighbors of an access point increases, which in turn increases the nodal density of the system. Our analysis indicates that nodal degree of the system inversely affects the shortterm fairness of a system of wireless networks. For that reason, there may be a tradeoff between the shortterm fairness of the system and the deployment density to some extent.
To investigate this relationship, we simulated a 10km × 10km area covered by WiFi access points. Previous studies showed that a regular deployment such as the mesh deployment provides better coverage than a totally random deployment [27]. We here investigate the relationship between the density of deployment and shortterm fairness performance of networks.
The transmission range of each access point is selected to be 250 m and carrier sensing range of access points is selected to be 550 m which are the default values for ns2 network simulator. We simulated for internodal distances between 200 and 900 m. For each internodal distance, we formed the conflict graph by linking the access point with their neighbors within their carrier sensing ranges. Two sample conflict graphs corresponding to different deployment scenarios for l = 300 and l = 450 m are depicted in Figure 13. As the internodal degree reduces, the number of interfering neighbors of an access point increases, in turn increasing the degree of the conflict graph. We assumed that the access points have similar traffic requirements and each of them independently probes the channel at the same rate according to a Poisson point process. Similar to previous simulations, we measured the shortterm fairness horizon of each topology corresponding to a given internodal distance.
Figure 13. A 5km × 5km area is covered by WiFi access points which are located in a mesh pattern where(a)l = 300 m and (b) l = 450 m. The interference relationship between nodes are denoted by lines between interfering nodes.
Shortterm fairness of the network against the throughput of individual access points for different internodal distances are plotted in Figure 14. As the deployment density increases, the shortterm fairness horizon starts to increase rapidly at lower throughputs. For l > 550, there is no interaction between nodes. This low interference results in desirable shortterm fairness performance: there is no degradation in shortterm fairness with increasing throughput. For denser deployments, however, shortterm fairness horizon starts to degrade rapidly as throughputs increase.
Figure 14. Shortterm fairness horizon of the simulated WiFi deployment for different internodal distances. Higher density of deployment results in higher shortterm fairness horizon at the same throughput.
Although a larger internodal distance gives a good shortterm fairness performance, coverage ratio decreases as the internodal distance increases. Figure 15 presents the coverage of access points as the internodal distance increases. In this plot, coverage is calculated by assuming that an access point can cover a circular area with a radius of its transmission range and total coverage is the union of these circular areas. Although the shortterm fairness is very good, it is only possible to cover almost half of the area with an internodal distance of 600 m. From this plot, it can be said that a sacrifice from shortterm fairness is needed to achieve a significant coverage of the area.
Figure 15. Coverage of the simulated WiFi deployment for different internodal distances.
The results imply that there is a tradeoff between the shortterm fairness of the network and its coverage. Improving coverage may come at the expense of reducing shortterm fairness which should be considered in designing WiFi networks along with other factors such as cost, connectivity, etc.
8 Analogy with the hardcore model
The idealized CSMA network model closely resembles a simple model of a material which is called as the hardcore model [32]. In this model, particles of the material can be found at the vertices of a lattice graph under the condition that two particles cannot be found at neighboring nodes. This model is equivalent to the ideal CSMA network where two neighboring nodes cannot be active at the same time. So, finding a particle at a given vertex is equivalent to finding a node transmitting in a CSMA network. Recently, the underlying dynamics of the hardcore model has been used to analyze the performance of ideal CSMA [3,14,19].
The equivalent of the probing rate in the CSMA network is the fugacity in the hardcore model. As the probing rate of a node increases in the CSMA network, the probability of finding it active increases. Similarly, probability of finding a particle at a given vertex is increased as the fugacity increases. The difference between the idealized CSMA model and the hardcore model is that the individual transmitters in the CSMA model can have different probing rates. In contrast, the fugacity in the hardcore model is a systemwide parameter. So, the equivalent of the hardcore gas model with a given fugacity is a CSMA network where the probing rate of all nodes is equal to the fugacity.
There is substantial literature in statistical physics, and more recently in theoretical computer science, on characterization of conditions under which longterm correlations arise in the hardcore model. On the one hand, this literature is relevant to our purposes due to the alluded relationship between longrange dependence in spatial models and shortterm fairness. On the other hand, explicit characterization of these conditions is known to be difficult, and has been achieved only for special graph topologies such as regular trees, which have limited relevance to spatial systems of interacting WiFi networks that may arise in practice. In addition, conventional approach is to characterize such conditions in terms of parameters coined “fugacities” that may roughly be associated with backoff timers in WiFi transmitters. In contrast, since we are interested in identifying the practically useful portion of the throughput region, our goal here is to obtain conditions that are in terms of throughputs.
Since longrange correlations in a CSMA network causes transmission patterns to persist over long time scales, we here investigate if conditions creating longrange correlations have a relationship with the shortterm fairness of a CSMA network. We explain two conditions from the literature which corresponds to two different intensities of long range correlations and present simulation results which demonstrate the possible relation between these conditions and the shortterm fair capacity.
The first condition which is indicative of longrange correlations in the model is the existence of multiple equilibrium distributions. The second condition which indicates a stronger correlation is the reconstruction condition under which longrange correlations enable the reconstruction of the state of the root node using the states of leaf nodes in the tree as the length of the tree approaches to infinity.
8.1 Uniqueness of a Gibbs measure
Gibbs measure is the equilibrium distribution of a large number of locally interacting particles [33]. Since the interactions between particles are local, Gibbs measure has the Markov property where each node is conditionally independent of the rest of the network given the states of its neighbors. It is known that there exists at least one Gibbs measure satisfying the local conditional distributions. However, the system may also admit multiple measures in an infinite graph under some conditions which is called as phase transition.
The hardcore model on the infinite square lattice, for example, may admit multiple equilibrium distributions. For small λ, there is a unique Gibbs measure on the square lattice. However, it is possible to find two equilibrium distributions for large λ, namely μ_{white }and μ_{black}. μ_{white} corresponds to the case where the whites of the checkerboard pattern have a higher probability than the blacks of the checkerboard pattern. μ_{black }corresponds to the opposite case where the blacks are favored over whites.
A phase transition typically manifests itself in the form of a unique equilibrium distribution that has multimodal nature in a finite graph. That is, most of the probability measure is concentrated around several quasistable states. Transitions between such states become rare as the system size increases, leading to multiple distinct equilibrium distributions in the limit.
Dobrushin [34] showed that when the fugacity is below a certain critical threshold, i.e., λ < λ_{c}, a system has a unique measure. However, determination of this threshold is a difficult problem even for regular topologies. Kelly [31] has obtained the uniqueness threshold for the tree topology with degree d:
Previous literature was interested in determining threshold fugacities but they did
not consider the stationary probabilities, that is, throughputs that correspond to
these thresholds. The uniqueness threshold for the tree topology corresponds to the
case where the stationary probability of a node being active is
8.2 Reconstruction threshold
A stronger condition that is indicative of longrange correlations between nodes is called the reconstruction condition. Reconstruction problem is interested in characterizing the conditions under which the state of the root can be reconstructed using the states of the leaf nodes as the height of the tree approaches to infinity. Reconstruction property is a stronger condition than having multiple equilibrium distributions.
Exact reconstruction threshold for the tree topology is not known but, recently, it is shown that the hardcore model on the tree has nonreconstruction if [35]:
8.3 Shortterm fairness and mixing time
The described conditions occur as a result of increased correlation between the particles in the material. Similarly, shortterm fairness of a CSMA network reduces mainly because states of nodes become increasingly correlated which causes some nodes to starve for a long time reducing shortterm fairness.
Shortterm fairness is thought to be estimated by the mixing time of the underlying system dynamics [5] where mixing time is defined as the time required for the underlying Markov chain to converge to its equilibrium distribution. Convergence to equilibrium slows down if the network sticks to some transmission patterns during the convergence process. For that reason, slow mixing is considered to be an indicator of shortterm unfairness.
Previous studies on the mixing time of the hardcore model investigate the conditions of fast mixing. A recent study shows that the fast mixing region extends beyond the uniqueness region and reaches to the reconstruction region for the tree topology [36]. Because of this relationship, we investigate here whether these two thresholds have any implications in determining the region beyond which shortterm fairness of the CSMA network starts to deteriorate.
8.4 Simulations
The described uniqueness and reconstruction thresholds are for the tree topology and are in terms of fugacities. We obtain throughputs obtained at these fugacities by performing simulations and compare the results against the shortterm fair horizon for the tree topology.
Figure 16 plots the shortterm fairness horizon of the tree topologies for d = 4,10, and 18, along with the throughputs corresponding to the uniqueness threshold and the nonreconstruction bound. For d = 4, the uniqueness threshold and the nonreconstruction bound are close to each other corresponding to the point where shortterm fairness starts to increase rapidly. However, for larger d, the uniqueness threshold underestimates this point of increase while the nonreconstruction bound consistently locates the point where the horizon starts to increase rapidly.
Figure 16. The uniqueness threshold, nonreconstruction bound, and the shortterm fairness horizon for tree topologies with (a) d = 4 (b) d = 10 (c) d = 18.
These simulations demonstrate a possible analogy between the phase transitions of the hardcore model and shortterm fairness of the CSMA network. In light of the recent research, results showing that the fast mixing threshold of the tree topology extends to the reconstruction threshold [36], this line of study suggests further research especially for other topologies.
9 Conclusions
This article was aimed at characterizing the performance of a system of networks employing CSMA protocol under a shortterm fairness constraint. Our main findings can be summarized as follows: (1) Shortterm fairness significantly depends on the degree of the network: highdegree topologies have less shortterm fair capacity than lowdegree topologies. (2) Shortterm fairness does not depend on network size for reasonably large fixed degree random networks.
Conflict graph topology is an important factor affecting the shortterm fair capacity. The grid topology is inherently unfair at high throughputs. When the WiFi transmitters form a grid conflict graph the network may become severely unfair at high throughputs. However, in random conflict graphs, such behavior is not observed so that randomly placed transmitters are unlikely to experience this degradation in shortterm fairness.
Dependence of shortterm fairness on the degree of the network has implications for deployment of large area WiFi networks. Deploying a dense network improves coverage; however, it reduces shortterm fair capacity by increasing the average degree.
We have also presented simulation results which suggest a correlation between the phase transitions of the hardcore model from statistical physics literature to the shortterm fairness of the CSMA network. Our results suggest that the reconstruction threshold can be used as a good indicator of the shortterm fair capacity region for the tree topology which is in accordance with the recent results on the mixing time.
Our study focuses on fixedrate CSMA systems where the nodes do not adaptively change their probing rates. Whether a similar shortterm unfairness phenomenon will be observed in adaptive CSMA systems is a subject of future study. We conjecture that the shortterm unfairness problem may also be observed in adaptive CSMA systems at high loads because the nodes need to probe the channel very frequently resembling a fixed rate system at high loads. Similarly, the extent of shortterm unfairness in CSMAbased MAC protocols, such as the 802.11 protocol, has to be investigated.
In addition to further analysis of adaptive CSMA, methods to resolve the shortterm fairness problems have to be devised. As our results show, only a portion of the capacity region can be achieved under shortterm fairness constraints, so a sacrifice from throughput may be needed to alleviate the shortterm unfairness problem in a distributed fashion.
Competing interests
The authors declare that they have no competing interests.
References

K Thota, Broadband and WiFi households global forecast 2012. Technical report, Strategy Analytics 2012 (www), . strategyanalytics.com/default.aspx?mod=pressreleaseviewer&a0=5193 webcite.

L Jiang, J Walrand, A distributed CSMA algorithm for throughput and utility maximization in wireless networks. 46th Annual Allerton Conference on Communication, Control, and Computing ((Monticello, 2008)

S Rajagopalan, D Shah, J Shin, Network adiabatic theorem: an efficient randomized protocol for contention resolution. SIGMETRICS ’09 ((New York, NY, USA (ACM), 2009)

J Liu, Y Yi, A Proutiere, M Chiang, HV Poor, Towards utilityoptimal random access without message passing. Wirel. Commun. Mob. Comput 10, 115–128 (2010). Publisher Full Text

L Jiang, M Leconte, J Ni, R Srikant, J Walrand, Fast mixing of parallel Glauber dynamics and lowdelay CSMA scheduling. IEEE INFOCOM ((Shanghai, 2011)

X Wang, K Kar, Throughput modelling and fairness issues in CSMA/CA based adhoc networks. IEEE INFOCOM ((Miami, 2005)

M Durvy, O Dousse, P Thiran, Selforganization properties of CSMA/CA systems and their consequences on fairness. IEEE Trans. Inf. Theory 55(3), 931–943 (2009)

M Durvy, O Dousse, P Thiran, On the fairness of large CSMA networks. IEEE J. Sel. Areas Commun 27(7), 1093–1104 (2009)

PM van de Ven, SC Borst, D Denteneer, AJ Janssen, JS van Leeuwaarden, Equalizing throughputs in randomaccess networks. SIGMETRICS Perform. Eval. Rev 38, 39–41 (2010). Publisher Full Text

P van de Ven, J van Leeuwaarden, D Denteneer, A Janssen, Spatial fairness in linear randomaccess networks. Perform. Eval 69(3–4), 121–134 (2012)

P van de Ven, A Janssen, J van Leeuwaarden, S Borst, Achieving target throughputs in randomaccess networks. Perform. Eval 68(11), 1103–1117 (2011). Publisher Full Text

CH Kai, SC Liew, Temporal starvation in CSMA wireless networks. IEEE International Conference on Communications (ICC) ((Kyoto, 2011)

S Rajagopalan, D Shah, Distributed algorithm and reversible network. 42nd Annual Conference on Information Sciences and Systems ((Princeton, 2008)

L Jiang, D Shah, J Shin, J Walrand, Distributed random access algorithm: scheduling and congestion control. IEEE Trans. Inf. Theory 56(12), 6182–6207 (2010)

N Bouman, S Borst, J van Leeuwaarden, Achievable delay performance in CSMA networks. 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton) ((Monticello, 2011)

D Shah, D Tse, J Tsitsiklis, Hardness of low delay network scheduling. IEEE Trans. Inf. Theory 57(12), 7810–7817 (2011)

L Jiang, J Ni, R Srikant, J Walrand, Performance bounds of distributed CSMA scheduling. Information Theory and Applications Workshop (ITA) ((San Diego, 2010)

V Subramanian, M Alanyali, Delay performance of CSMA in networks with bounded degree conflict graphs. IEEE International Symposium on Information Theory ((St. Petersburg, 2011)

M Lotfinezhad, P Marbach, Throughputoptimal random access with orderoptimal delay. IEEE INFOCOM ((Shanghai, 2011)

D Shah, J Shin, Delay optimal queuebased CSMA. SIGMETRICS Perform. Eval. Rev 38, 373–374 (2010). Publisher Full Text

J Ni, B Tan, R Srikant, QCSMA: queuelength based CSMA/CA algorithms for achieving maximum throughput and low delay in wireless networks. IEEE INFOCOM ((San Diego, 2010)

J Ghaderi, R Srikant, On the design of efficient CSMA algorithms for wireless networks. 49th IEEE Conference on Decision and Control (CDC) ((Atlanta, 2010)

N Bouman, SC Borst, JS van Leeuwaarden, Delay performance of backlog based random access. SIGMETRICS Perform. Eval. Rev 39(2), 32–34 (2011). Publisher Full Text

N Bouman, S Borst, J van Leeuwaarden, A Proutiere, Backlogbased random access in wireless networks: fluid limits and delay issues. 23rd International Teletraffic Congress (ITC) ((San Francisco, 2011)

R Boorstyn, A Kershenbaum, B Maglaris, V Sahin, Throughput analysis in multihop CSMA packet radio networks. IEEE Trans. Commun 35(3), 267–274 (1987)

F Viger, M Latapy, Efficient and simple generation of random simple connected graphs with prescribed degree sequence. Computing and Combinatorics, Volume 3595 of Lecture Notes in Computer Science, ed. by Wang L (Springer, Berlin, 2005)

J Robinson, E Knightly, A performance study of deployment factors in wireless mesh networks. IEEE INFOCOM ((Anchorage, 2007)

CE Koksal, H Kassab, H Balakrishnan, An analysis of shortterm fairness in wireless media access protocols (poster session). ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems ((New York, 2000)

R Jain, D Chiu, W Hawe, A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. ArXiv Computer Science (eprints)

C Cetinkaya, F Orsun, Cooperative medium access protocol for dense wireless networks. The Third Annual Mediterranean Ad Hoc Networking Workshop  Med Hoc Net ((Bodrum, 2004)

FP Kelly, Stochastic models of computer communication systems. J. R. Stat. Soc. Ser. B (Methodological) 47(3), 379–395 (1985)

J van den Berg, JE Steif, Percolation and the hardcore lattice gas model. Stoch. Process. Appl 49(2), 179–197 (1994). Publisher Full Text

HO Georgii, Gibbs Measures and Phase Transitions (Walter de Gruyter & Co, Berlin, 1988)

RL Dobrushin, The problem of uniqueness of a Gibbsian random field and the problem of phase transitions. Funct. Anal. Appl 2, 302–312 (1968)

N Bhatnagar, A Sly, P Tetali, Reconstruction threshold for the hardcore model. in Approximation, Randomization, and Combinatorial Optimization, ed. by Serna M, Shaltiel R, Jansen K, Rolim J. Algorithms and Techniques, Volume 6302 of Lecture Notes in Computer Science (Springer, Berlin, 2010)

R Restrepo, D Stefankovic, JC Vera, E Vigoda, L Yang, Phase transition for glauber dynamics for independent sets on regular trees. 22nd Annual ACMSIAM Symposium on Discrete Algorithms ((San Francisco, 2011)