High-Performance Wireless Networking: Algorithms and Protocols

SCOPE: Distributed Packet Scheduling in Multihop Wireless Networks

Design Issues: In a shared-medium, multihop wireless network, since wireless transmissions are local broadcast, the nodes within the spatial transmission range of an ongoing conversation are typically restrained not to transmit in order to avoid collisions. Hence,
  • Location-dependent Contention exists among contending flows in a spatial locality.
  • Location-dependent Channel Reuse of bandwidth is possible: for a given flow, other flows may transmit simultaneously if they are out of the transmission range (typically two hops) of the current flow and are not interfering with each other.
  • Network Dynamics: node mobility, channel errors, new contending flows joining in and old flows dying out.
Compared with wireline fair queueing, contention is not only in the time domain, but also in space domain. The schedulers have to coordinate their scheduling among neighboring nodes, to avoid collision, and achieve channel spatial reuse.

Design Goals: Multihop wireless fair queueing is inherently a global computation problem, since location-dependent contention, together with the notion of fairness, creates global coupling effects in the entire connected topology. To realize fair queueing in an ad hoc wireless network is particularly challenging due to the fact that there is no centralized management or any infrastructure support. Thus, the solution for fair queueing in ad hoc wireless networks must:
  • Be fully distributed, and it involves only local computations by using local information only.
  • Exhibit desired global behavior, e.g., fairness property.
  • Be scalable to potentially large number of nodes and dense networks. Besides, the solution should equally scale well in the presence of frequent node mobility and failures.
  • Be efficient. The fair queueing discipline needs to perform a judicious selection of simultaneous transmissions in order to increase wireless channel spatial reuse.
  • Be coordinated among interacting nodes. Fair queueing in ad hoc wireless networks has to be coordinated among neighbors that have contending flows, and this coordination should be conducted in both the time domain and the spatial domain.
Our Approaches:
  • Distributed fair queueing via approximating a centralized model (Desired global property -> Centralized model -> Localized algorithms to approximate the centralized model):
    • WFQ with lookahead window to enable channel spatial reuse;
    • Adaptive solution to the dynamic graph coloring problem;
    • Backoff-based distributed implementation within CSMA/CA
  • Self-coordinating approach to distributed fair queuing (Desired global property -> Mapping to local property -> Localized model -> Localized algorithms to realize the local model):
    • Maximizing local minimum;
    • Table-driven distributed implementation
People: Journal Publications: Conference Publications: Posters:
WiNG