Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

A Distributed Algorithm for Maximal Throughput and Optimal Fairness in Wireless Networks with a General Interference Model

Libin Jiang and Jean Walrand

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2008-38
April 15, 2008

http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-38.pdf

In multi-hop wireless networks, earlier research on joint scheduling and congestion control has suggested that MAC-layer scheduling is the bottleneck. Distributed scheduling for maximal throughput is difficult since the conflicting relationship between different links is complex. Existing works on maximal-throughput scheduling usually assumes synchronized time slots, and in each slot, a maximal-weighted "independent set" needs to be found or approximated. However, this is hard to implement in distributed networks. On the other hand, a distributed greedy protocol similar to IEEE 802.11 can only achieve a fraction of the throughput region. In this paper, we introduce an adaptive CSMA algorithm, which can achieve the maximal throughput distributedly under some assumptions. The intuitive idea is that each link should adjust its aggressiveness of transmission based on its backlog. Furthermore, we combine the algorithm with end-to-end flow control to achieve fairness among competing flows. The effectiveness of the algorithm is verified by simulations.


BibTeX citation:

@techreport{Jiang:EECS-2008-38,
    Author = {Jiang, Libin and Walrand, Jean},
    Title = {A Distributed Algorithm for Maximal Throughput and Optimal Fairness in Wireless Networks with a General Interference Model},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2008},
    Month = {Apr},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-38.html},
    Number = {UCB/EECS-2008-38},
    Abstract = {In multi-hop wireless networks, earlier research on joint scheduling and congestion control has suggested that MAC-layer scheduling is the bottleneck. Distributed scheduling for maximal throughput is difficult since the conflicting relationship between different links is complex. Existing works on maximal-throughput scheduling usually assumes synchronized time slots, and in each slot, a maximal-weighted "independent set" needs to be found or approximated. However, this is hard to implement in distributed networks. On the other hand, a distributed greedy protocol similar to IEEE 802.11 can only achieve a fraction of the throughput region. In this paper, we introduce an adaptive CSMA algorithm, which can achieve the maximal throughput distributedly under some assumptions. The intuitive idea is that each link should adjust its aggressiveness of transmission based on its backlog. Furthermore, we combine the algorithm with end-to-end flow control to achieve fairness among competing flows. The effectiveness of the algorithm is verified by simulations.}
}

EndNote citation:

%0 Report
%A Jiang, Libin
%A Walrand, Jean
%T A Distributed Algorithm for Maximal Throughput and Optimal Fairness in Wireless Networks with a General Interference Model
%I EECS Department, University of California, Berkeley
%D 2008
%8 April 15
%@ UCB/EECS-2008-38
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-38.html
%F Jiang:EECS-2008-38