Show simple item record

dc.contributor.authorKabbani, Abdul
Salonidis, Theodoros
Knightly, Edward
dc.creatorKabbani, Abdul
Salonidis, Theodoros
Knightly, Edward
dc.date.accessioned 2007-10-31T00:48:52Z
dc.date.available 2007-10-31T00:48:52Z
dc.date.issued 2007
dc.date.submitted 2006-08-14
dc.identifier.citation A. Kabbani, T. Salonidis and E. Knightly, "Distributed Low-Complexity Maximum-Throughput Scheduling for Wireless Backhaul Networks," IEEE INFOCOM, 2007.
dc.identifier.urihttps://hdl.handle.net/1911/19996
dc.description Tech Report
dc.description.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.
dc.language.iso eng
dc.subjectWireless networks
Scheduling
Graph Theory
Distributed MAC protocols
dc.title Distributed Low-Complexity Maximum-Throughput Scheduling for Wireless Backhaul Networks
dc.type Report
dc.citation.bibtexName techreport
dc.citation.journalTitle IEEE INFOCOM
dc.date.modified 2006-08-14
dc.contributor.orgCenter for Multimedia Communications (http://cmc.rice.edu/)
dc.subject.keywordWireless networks
Scheduling
Graph Theory
Distributed MAC protocols
dc.relation.projecthttp://ece.rice.edu/~thsalon
dc.type.dcmi Text
dc.type.dcmi Text
dc.identifier.doihttp://dx.doi.org/10.1109/INFCOM.2007.239


Files in this item

Thumbnail

This item appears in the following Collection(s)

  • ECE Publications [1289]
    Publications by Rice University Electrical and Computer Engineering faculty and graduate students

Show simple item record