Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

A Distributed CSMA Algorithm for Throughput and Utility Maximization in Wireless Networks

Libin Jiang and Jean Walrand

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2009-124
August 23, 2009

http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-124.pdf

In multi-hop wireless networks, designing distributed scheduling algorithms to achieve the maximal throughput is a challenging problem because of the complex interference constraints among different links. Traditional maximal-weight scheduling (MWS), although throughput-optimal, is difficult to implement in distributed networks. On the other hand, a distributed greedy protocol similar to IEEE 802.11 does not guarantee the maximal throughput. In this paper, we introduce an adaptive CSMA scheduling algorithm that can achieve the maximal throughput distributively. Some of the major advantages of the algorithm are that it applies to a very general interference model and that it is simple, distributed and asynchronous. Furthermore, the algorithm is combined with end-to-end flow control to achieve the optimal utility and fairness of competing flows. Simulations verify the effectiveness of the algorithm. Also, the adaptive CSMA scheduling is a modular MAC-layer algorithm that can be combined with various protocols in the transport layer and network layer. Finally, the paper explores some implementation issues in the setting of 802.11 networks.


BibTeX citation:

@techreport{Jiang:EECS-2009-124,
    Author = {Jiang, Libin and Walrand, Jean},
    Title = {A Distributed CSMA Algorithm for Throughput and Utility Maximization in Wireless Networks},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2009},
    Month = {Aug},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-124.html},
    Number = {UCB/EECS-2009-124},
    Abstract = {In multi-hop wireless networks, designing distributed scheduling algorithms to achieve the maximal throughput is a challenging problem because of the complex interference constraints among different links. Traditional maximal-weight scheduling (MWS), although throughput-optimal, is difficult to implement in distributed networks. On the other hand, a distributed greedy protocol similar to IEEE 802.11 does not guarantee the maximal throughput. In this paper, we introduce an adaptive CSMA scheduling algorithm that can achieve the maximal throughput distributively. Some of the major advantages of the algorithm are that it applies to a very general interference model and that it is simple, distributed and asynchronous. Furthermore, the algorithm is combined with end-to-end flow control to achieve the optimal utility and fairness of competing flows. Simulations verify the effectiveness of the algorithm. Also, the adaptive CSMA scheduling is a modular MAC-layer algorithm that can be combined with various protocols in the transport layer and network layer. Finally, the paper explores some implementation issues in the setting of 802.11 networks.}
}

EndNote citation:

%0 Report
%A Jiang, Libin
%A Walrand, Jean
%T A Distributed CSMA Algorithm for Throughput and Utility Maximization in Wireless Networks
%I EECS Department, University of California, Berkeley
%D 2009
%8 August 23
%@ UCB/EECS-2009-124
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-124.html
%F Jiang:EECS-2009-124