|
Title:
|
Distributed Low-Complexity Maximum-Throughput Scheduling for Wireless Backhaul Networks |
|
Author:
|
Kabbani, Abdul; Salonidis, Theodoros; Knightly, Edward
|
|
Type:
|
Tech Report |
|
Keywords:
|
Wireless networks; Scheduling; Graph Theory; Distributed MAC protocols |
|
Citation:
|
A. Kabbani, T. Salonidis and E. Knightly, "Distributed Low-Complexity Maximum-Throughput Scheduling for Wireless Backhaul Networks," IEEE INFOCOM, 2006. |
|
Abstract:
|
We introduce a low-complexity distributed slotted MAC protocol
that can support all feasible arrival rates in a wireless backhaul
network (WBN). For arbitrary wireless networks, such a maximum
throughput protocol has been notoriously hard to realize because
(i) even if global topology information is available, the problem
of computing the optimal link transmission set at each slot is
NP-complete (ii) no bounds exist on the number of steps required
for such a computation (per-slot overhead). For the logical tree
structures induced by the WBN traffic matrices, we first introduce
a centralized algorithm that solves the optimal scheduling problem
in a number of steps at most linear in the number of nodes in the
network. This is achieved by discovering and exploiting a novel
set of graph-theoretical properties of the WBN contention graph.
Guided by the centralized algorithm, we design a distributed
protocol where, at the beginning of each slot, nodes coordinate
and incrementally compute the optimal link transmission set. We
then introduce an algorithm to compute the minimum number of steps
to complete this computation, thus minimizing the per-slot
overhead. Using both analysis and simulations, we show that in
practice our protocol yields low overhead when implemented over
existing wireless technologies and significantly outperforms
existing suboptimal distributed slotted scheduling mechanisms. |
|
Date Published:
|
2006-08-01 |
