Queue-based random access in wireless networks
N Niek Bouman · TU/e Research Portal · 2013
A wireless network may be abstractly viewed as a collection of users that all want to transmit or receive data.The network can be modeled by a set of nodes in space, representing the users, interconnected by a number of directed links, indicating a possible transmission from one user to another.Links in the model thus denote a potential wireless data transmission from a transmitting node to a receiving node and have no direct physical interpretation.In this thesis we assume that every transmitter has exactly one intended receiver, and we consider only the links that correspond to these intended transmissions.We further assume that every receiver needs to receive data from only one transmitter.These assumptions are not particularly crucial, and results can be generalized to other scenarios.Every transmitting node has a buffer, or queue, of data packets waiting to be transmitted.If this buffer is empty for a certain node, and if that node is not transmitting any From the interference model we can construct the set Ω ⊆ {0, 1} N of all feasible joint activity states such that any transmission is successful if the state of the system is in Ω for the entire transmission period.When interference is modeled by a conflict graph, every feasible activity state corresponds to a set of vertices in the conflict graph such that none of the vertices share an edge, i.e., an independent set of this graph.The set Ω then consists of all independent sets of the conflict graph.Hence the stationary probability to reside in a certain state increases exponentially with its weight, N i=1 w(L * i )u i .If w(•) is an increasing function with w(l) → ∞ when l → ∞, it then follows that, after the initial convergence period, the system resides in a state with maximum weight or close to maximum weight with high probability at any point in time when the, fixed, number of packets in the system is 'large enough'.Assuming that, when queue lengths vary, the distribution of the activity process is approximately given by (1.4), with) at time t , we then see that the queue-based CSMA algorithm essentially approximates the extension of the MaxWeight algorithm that uses w(L i (t )) for the weight of link i , see Section 1.2.1, when 'a large number' of packets are present in the system [79,80].As this is sufficient for an algorithm to be throughput-optimal [38], it hints at the fact that the queue-based CSMA algorithm is throughput-optimal.Crucial in the above reasoning is the so-called time-scale separation assumption, the assumption that the distribution of the activity process is given by (1.4).This assumption seems reasonable when the time required for the weights w(L i (t )) to substantially change is much longer than the time the activity process needs to converge to its stationary distribution in case the queue lengths are fixed.To achieve this, sufficiently cautious activity functions are considered in the literature to prove throughput-optimality of queue-based CSMA algorithms without assuming the time-scale separation.The algorithm is shown to be throughput-optimal in [82] for f (l) = r (l)/(1 + r (l)) and g (l) = 1/(1 + r (l)), with r (l) = log(l + 1), and the result is generalized to a broad class of cautious activity functions in [47].The algorithm in [47,82] is not completely distributed as it requires the nodes to exchange some information about global system parameters.In particular, the maximum queue length is assumed to be known.This is resolved in [89] by introducing a learning mechanism.For time-varying transmission rates, throughout-optimality can be obtained by extending the above model [109].For more aggressive activity functions, i.e., faster-growing functions, the weight of each link will change rapidly, invalidating the time-scale separation assumption.In fact, [46] shows that the queue-based CSMA algorithm may fail to be throughput-optimal for more aggressive activity functions.Finding the exact characterization of the stability region, depending on the structure of the network and the activity functions, is still an open problem.For algorithms in which links only activate with a fixed rate when packets are present in the buffer of that link, i.e., for [102] derives necessary and sufficient stability conditions for full conflict graphs, and shows that an exact characterization of the stability region is difficult for all other topologies in this case. MotivationThe stability results described in Section 1.3 provide an important first-order indication of the performance of the system.Unfortunately, simulation experiments demonstrate that such throughput-optimal CSMA algorithms can induce excessive delays, which has triggered a strong interest in developing approaches for improving the delay performance [47,54,71,76,79,87].These delay issues are reminiscent of unfairness and starvation phenomena associated with concurrency control in shared-resource systems.To gain a fundamental understanding of the poor delay performance of the