Distributed Random Access Algorithm: Scheduling and Congesion Control

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 ε [epsilon]-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 numberNational Science Foundation (U.S.) (Project CNS 0546590) (Project TF 0728554)United States. Defense Advanced Research Projects Agency. Information Theory for Mobile Ad-Hoc Networks ProgramUnited States. Air Force Office of Scientific Research. Complex Networks ProjectUnited States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (Grant BAA 07-036.18