TY - GEN

T1 - Scheduling efficiency of distributed greedy scheduling algorithms in wireless networks

AU - Wu, Xinzhou

AU - Srikant, Rayadurgam

PY - 2006/12/1

Y1 - 2006/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=39049142523&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=39049142523&partnerID=8YFLogxK

U2 - 10.1109/INFOCOM.2006.176

DO - 10.1109/INFOCOM.2006.176

M3 - Conference contribution

AN - SCOPUS:39049142523

SN - 1424402212

SN - 9781424402212

T3 - Proceedings - IEEE INFOCOM

BT - Proceedings - INFOCOM 2006

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

Y2 - 23 April 2006 through 29 April 2006

ER -