Paper Info
Title
Distributed Low-Complexity Maximum-Throughput Scheduling For Wireless Backhaul Networks
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 even if global topology information is available, the problem of computing the optimal link transmission set at each slot is NP-complete. For the logical tree structures induced by 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 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 perslot 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.
Year
DOI
Venue
2007
10.1109/INFCOM.2007.239
INFOCOM 2007, VOLS 1-5
Keywords
Field
DocType
scheduling,computational complexity,wireless application protocol,network topology,tree structure,np complete problem,throughput,minimisation,tree data structures,scheduling algorithm,wireless network,computer networks,wireless networks
Wireless network,Wireless,Job shop scheduling,Scheduling (computing),Computer science,Computer network,Maximum throughput scheduling,Tree structure,Throughput,Distributed computing,Computational complexity theory
Conference
ISSN
Citations 
PageRank 
0743-166X
22
1.02
References 
Authors
10
3
Name
Order
Citations
PageRank
Abdul Kader Kabbani1221.02
Theodoros Salonidis2124793.31
Edward W. Knightly34763371.38