# 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