### Abstract

We consider the problem of distributed scheduling in wireless networks subject to simple collision constraints. In a network depletion problem with an initial traffic load and no further arrivals, we define the scheduling efficiency to be the ratio between the number of time slots required to deplete the network under an optimal centralized scheduling scheme and a distributed greedy scheduling scheme. In a network with stochastic arrivals, we define the scheduling efficiency to be the largest number (fraction) such that its throughput is at least equal to the efficiency multiplied by the throughput of a centralized policy. For 802.11-like scheduling constraints which ensure that there is no collision during the reception of a data packet or its ack, we prove a lower bound on the efficiency of a distributed scheduling algorithm. While the tightness of the lower bound is still open for networks with stochastic arrivals, we also prove an upper bound for the network depletion problem which shows that the efficiency can only be larger than the lower bound by a factor of two. The upper bound is established by deriving a new result on the ratio of the chromatic number to the number of colors required to color the nodes of a contention graph using a greedy coloring algorithm. Our results are not asymptotic in the number of nodes in the network, i.e, they hold for networks of any size. For a collision constraint which only avoids collision of the data packet, we also provide a lower bound on the achievable capacity region.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - INFOCOM 2006 |

Subtitle of host publication | 25th IEEE International Conference on Computer Communications |

DOIs | |

State | Published - Dec 1 2006 |

Event | INFOCOM 2006: 25th IEEE International Conference on Computer Communications - Barcelona, Spain Duration: Apr 23 2006 → Apr 29 2006 |

### Publication series

Name | Proceedings - IEEE INFOCOM |
---|---|

ISSN (Print) | 0743-166X |

### Other

Other | INFOCOM 2006: 25th IEEE International Conference on Computer Communications |
---|---|

Country | Spain |

City | Barcelona |

Period | 4/23/06 → 4/29/06 |

### Fingerprint

### ASJC Scopus subject areas

- Computer Science(all)
- Electrical and Electronic Engineering

### Cite this

*Proceedings - INFOCOM 2006: 25th IEEE International Conference on Computer Communications*[4146829] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFOCOM.2006.176