Academic
Publications
Distributed Random Access Algorithm: Scheduling and Congestion Control

Distributed Random Access Algorithm: Scheduling and Congestion Control,10.1109/TIT.2010.2081490,IEEE Transactions on Information Theory,Libin Jiang,De

Distributed Random Access Algorithm: Scheduling and Congestion Control   (Citations: 9)
BibTex | RIS | RefWorks Download
This paper provides proofs of the rate stability, Harris recurrence, and ε-optimality of carrier sense multiple access (CSMA) algorithms where the random access (or backoff) parameter of each node is adjusted dynamically. These algorithms require only local information and they are easy to implement. The setup is a network of wireless nodes with a fixed conflict graph that identifies pairs of nodes whose simultaneous transmissions conflict. The paper studies two algorithms. The first algorithm schedules transmissions to keep up with given arrival rates of packets. The second algorithm controls the arrivals in addition to the scheduling and attempts to maximize the sum of the utilities, in terms of the rates, of the packet flows at different nodes. For the first algorithm, the paper proves rate stability for strictly feasible arrival rates and also Harris recurrence of the queues. For the second algorithm, the paper proves the ε-optimality in terms of the utilities of the allocated rates. Both algorithms are iterative and we study two versions of each of them. In the first version, both operate with strictly local information but have relatively weaker performance guarantees; under the second version, both provide stronger performance guarantees by utilizing the additional information of the number of nodes in the network.
Journal: IEEE Transactions on Information Theory - TIT , vol. 56, no. 12, pp. 6182-6207, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Inspired by and similar to [22], [46], we also adopt the standard methods of stochastic approximation [47], [48] and Markov chain [49], [50]...
    • ...The difference between our proof and [22], [46] is that, our proof studies the saddle points of Lagrangian function, while [22], [46] studies the optimal dual solutions directly...
    • ...The difference between our proof and [22], [46] is that, our proof studies the saddle points of Lagrangian function, while [22], [46] studies the optimal dual solutions directly...
    • ...Therefore, in general, our proof techniques can be applied to primal-dual resource allocation algorithms, while proof techniques in [22], [46] can be applied only to dual resource allocation algorithms...

    Ziyu Shaoet al. Cross-Layer Optimization for Wireless Networks With Deterministic Chan...

    • ...This result has spurred interest among researchers in searching for other distributed throughput-optimal scheduling algorithms [7], [8]...

    Qiao Liet al. Distributed Throughput-optimal Scheduling in Ad Hoc Wireless Networks

    • ...The decentralized queue-length based scheduling algorithm in [14] and its variants have been shown to be throughput-optimal in [12], [13], [19]...
    • ...We consider a Lyapunov function of the form, for .I n order to establish positive Harris recurrence, for any such that , we use multi-step9 Lyapunov and Foster’s drift criteria to establish positive recurrence of a set of the form , for some . From the assumption on the arrival processes, it follows that is a closed petite (small) set (for definition and details see [12], [21])...
    • ...The proofs given in this Appendix are generalizations of proofs in [12] and [13] to multi-state framework...

    Jubin Joseet al. Distributed Rate Allocation for Wireless Networks

    • ...In the same spirit, several powerful algorithms have been devised for adapting the transmission lengths based on backlog information, and been shown to guarantee maximum stability [12], [20]...

    Niek Boumanet al. Backlog-based random access in wireless networks: Fluid limits and del...

    • ...Several authors have proposed clever backlog-based algorithms for adapting activation rates that achieve stability whenever feasible to do so at all [6, 7, 8, 13, 14]...
    • ...As stated in the introduction, there are simple backlogbased algorithms for adapting activation rates that achieve stability whenever feasible at all [6, 7, 8, 13, 14]...

    Peter M. van de Venet al. Equalizing throughputs in random-access networks

Sort by: