Carrier-sense multiple access collision avoidance networks have often been analyzed using a stylized model that is fully characterized by a vector of back-off rates and a conflict graph. Furthermore, for any achievable throughput vector @math , the existence of a unique vector @math of back-off rates that achieves this throughput vector was proven. Although this unique vector can in principle be computed iteratively, the required time complexity grows exponentially in the network size, making this only feasible for small networks. In this paper, we present an explicit formula for the unique vector of back-off rates @math needed to achieve any achievable throughput vector @math provided that the network has a chordal conflict graph. This class of networks contains a number of special cases of interest such as (inhomogeneous) line networks and networks with an acyclic conflict graph. Moreover, these back-off rates are such that the back-off rate of a node only depends on its own target throughput and the target throughput of its neighbors and can be determined in a distributed manner. We further indicate that back-off rates of this form cannot be obtained in general for networks with non-chordal conflict graphs. For general conflict graphs, we nevertheless show how to adapt the back-off rates when a node is added to the network when its interfering nodes form a clique in the conflict graph. Finally, we introduce a distributed chordal approximation algorithm for general conflict graphs, which is shown (using numerical examples) to be more accurate than the Bethe approximation.
In @cite_10 the fairness of large CSMA CA networks was studied and for regular networks (lines and grids) conditions on when the unfairness propagates within the network were presented. The cause of unfairness in CSMA CA networks was further analyzed in @cite_1 , where the equality of the receiving and sensing ranges was identified as an important cause. Fairness in CSMA CA line networks was also studied in @cite_20 , where an explicit formula was presented to achieve fairness in a line network consisting of @math nodes, where each node interferes with the next and previous @math nodes. The existence of a unique vector of back-off rates to achieve any achievable throughput vector was established in @cite_26 , which also discusses several iterative algorithms to compute this vector.
@cite_1 @cite_26 @cite_10 @cite_20
2130986870 2003813460 2162938499 2158564748
In this paper, we consider the throughput modelling and fairness provisioning in CSMA CA based ad-hoc networks. The main contributions are: firstly, a throughput model based on Markovian analysis is proposed for the CSMA CA network with a general topology. Simulation investigations are presented to verify its performance. Secondly, fairness issues in CSMA CA networks are discussed based on the throughput model. The origin of unfairness is explained and the trade-off between throughput and fairness is illustrated. Thirdly, throughput approximations based on local topology information are proposed and their performances are investigated. Fourthly, three different fairness metrics are presented and their distributed implementations, based on the throughput approximation, are proposed. We characterize the fairness of decentralized medium access control protocols based on CSMA CA, in large multi-hop wireless networks. In particular, we show that the widely observed unfairness of these protocols in small network topologies does not always persist in large topologies. In regular networks, this unfairness is essentially due to the unfair advantage of nodes at the border of the network, which have a restricted neighborhood and thus a higher probability to access the communication channel. In large 1D lattice networks these border effects do not propagate inside the network, and nodes sufficiently far away from the border have equal access to the channel; as a result the protocol is long-term fair. In 2D lattice networks, we observe a phase transition. If the access intensity of the protocol is small, the border effects remain local and the protocol behaves similarly as in one-dimensional networks. However, if the access intensity of the protocol is large enough, the border effects persist independently of the size of the network and the protocol is strongly unfair. In irregular networks, the topology is inherently unfair. This unfairness increases with the access intensity of the protocol, but in a much smoother way than in regular two-dimensional networks. Finally, in situations where the protocol is long-term fair, we provide a characterization of its short-term fairness. CSMA CA, the contention mechanism of the IEEE 802.11 DCF medium access protocol, has recently been found vulnerable to selfish backoff attacks consisting in nonstandard configuration of the constituent backoff scheme. Such attacks can greatly increase a selfish station's bandwidth share at the expense of honest stations applying a standard configuration. The paper investigates the distribution of bandwidth among anonymous network stations, some of which are selfish. A station's obtained bandwidth share is regarded as a payoff in a noncooperative CSMA CA game. Regardless of the IEEE 802.11 parameter setting, the payoff function is found similar to a multiplayer Prisoners' Dilemma; moreover, the number (though not the identities) of selfish stations can be inferred by observation of successful transmission attempts. Further, a repeated CSMA CA game is defined, where a station can toggle between standard and nonstandard backoff configurations with a view of maximizing a long-term utility. It is argued that a desirable station strategy should yield a fair, Pareto efficient, and subgame perfect Nash equilibrium. One such strategy, called CRISP, is described and evaluated. Random-access networks may exhibit severe unfairness in throughput, in the sense that some nodes receive consistently higher throughput than others. Recent studies show that this unfairness is due to local differences in the neighborhood structure: nodes with fewer neighbors receive better access. We study the unfairness in saturated linear networks, and adapt the random-access CSMA protocol to remove the unfairness completely, by choosing the activation rates of nodes as a specific function of the number of neighbors. We then investigate the consequences of this choice of activation rates on the network-average saturated throughput, and we show that these rates perform well in non-saturated settings.