Fairness and Throughput Guarantees with Maximal Scheduling in Multi-hop Wireless Networks

Saswati  Sarkar; Prasanna  Chaporkar; Koushik  Kar

4th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks

Research Article

Fairness and Throughput Guarantees with Maximal Scheduling in Multi-hop Wireless Networks

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.1109/WIOPT.2006.1666477,
    author={Saswati  Sarkar and Prasanna  Chaporkar and Koushik  Kar},
    title={Fairness and Throughput Guarantees with Maximal Scheduling in Multi-hop Wireless Networks},
    proceedings={4th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks},
    publisher={IEEE},
    proceedings_a={WIOPT},
    year={2006},
    month={8},
    keywords={},
    doi={10.1109/WIOPT.2006.1666477}
}

Saswati Sarkar
Prasanna Chaporkar
Koushik Kar
Year: 2006
Fairness and Throughput Guarantees with Maximal Scheduling in Multi-hop Wireless Networks
WIOPT
IEEE
DOI: 10.1109/WIOPT.2006.1666477

Saswati Sarkar¹^,*, Prasanna Chaporkar²^,*, Koushik Kar³^,*

1: University of Pennsylvania, Philadelphia, PA, USA
2: INRIA Paris, France
3: Rensselaer Polytechnic Institute, Troy, NY, USA

*Contact email: swati@seas.upenn.edu, Prasanna.Chaporkar@ens.fr, koushik@ecse.rpi.edu

Abstract

We investigate the fairness and throughput properties of a simple distributed scheduling policy, maximal scheduling, in the context of a general ad-hoc wireless network. We design a fully distributed algorithm that combines a token generation scheme with maximal scheduling policy so as to attain max-min fair rates within the feasible region of maximal scheduling. We next present throughput guarantees of maximal scheduling that quantify the performance loss of each session due to the use of local information based scheduling. We show that the performance loss for each session depends on the maximum “interference degree” in its neighborhood. We also demonstrate that the performance penalties can not be localized any further.

Published: 2006-08-07
Publisher: IEEE

: http://dx.doi.org/10.1109/WIOPT.2006.1666477