A new model for packet scheduling in multihop wireless networks

By Haiyun Luo, Songwu Lu, Vaduvur Bharghavan. ACM/IEEE International Conference on Mobile Computing and Networking, 2000

379 citations recorded by the source corpus.

The goal of packet scheduling disciplines is to achieve fair and maximum allocation of channel bandwidth. However, these two criteria can potentially be in conflict in a generic-topology multihop wireless network where a single logical channel is shared among multiple contending flows and spatial reuse of the channel bandwidth is possible. In this paper, we propose a new model for packet scheduling that addresses this conflict. The main results of this paper are the following: (a) a two-tier service model that provides a minimum “fair” allocation of the channel bandwidth for each packet flow and additionally maximizes spatial reuse of bandwidth, (b) an ideal centralized packet scheduling algorithm that realizes the above service model, and (c) a practical distributed backoff-based channel contention mechanism that approximates the ideal service within the framework of the CSMA/CA protocol.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/1330d25611af320e0cc0a205a62b4ea2ce643378

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

What is the right model for wireless channel interference? (2006, background): “As mentioned earlier, in works like [12], [14], [19], the authors assume a fixed communication range and a fixed interference range.”
Localized algorithm for aggregate fairness in wireless sensor networks (2006, background): “Fairness at the MAC layer is studied in [20, 29, 30, 21, 22].”
On max-min fairness and scheduling in wireless ad-hoc networks: analytical framework and implementation (2001, background): “Luo et al [4] have proposed a two phases scheduling scheme to achieve fairness in ad-hoc networks.”
Handbook of Wireless Networks and Mobile Computing (2002, methodology): “In [13], optimal graph labelings for odd cycles with constraints c1, c2 are given.”
Modeling Per-Flow Throughput and Capturing Starvation in CSMA Multi-Hop Wireless Networks (2006, methodology): “Several forms of fairness have been proposed: weighted fairness [14], [23], max-min fairness [15], [29] and proportional fairness [18], [22]; these objectives have been implemented either using TDMA or random access.”
Mitigating congestion in wireless sensor networks (2004, background): “Achieving fairness in multi-hop wireless networks is difficult and often comes at the cost of reduced aggregate throughput [12, 15].”
Optimal routing, link scheduling and power control in multihop wireless networks (2003, background): “For example, h( P avg) might equal the average power incident at a given point in space, or be equal to the total average power emanating from a closed boundary surrounding the network.”
Utilization and fairness in spectrum assignment for opportunistic spectrum access (2006, methodology): “Contention based schemes invoke a random access protocol like ALOHA and CSMA, where users contend in time to share a common channel [ 14 ], [10], [17].”
Distributed fair scheduling in a wireless LAN (2000, background): “There has been some work on achieving fairness in wireless networks (e.g., [3], [12], [ 16 ], [17], [27], [26]).”