IntroductionDesign Issues and Solution SpaceNetwork ModelDesign IssuesLocation-dependent contention and spatial reuseConflict between fairness and maximizing channel utilizationSolution spaceThe Packet Scheduling ModelThe fluid model and the flow contention graphAchieving a minimum fair share through fair queueingApproximating the maximum independent setSlot queues and packet queuesAnalytical Properties of the Packetized AlgorithmFairness and throughput in the basic channelSpatial reuseA Distributed ImplementationTwo Design IssuesDistributed nature of packet scheduling in multihop wireless networksInformation propagation in a broadcast mediumA backoff-based distributed algorithmAlgorithm descriptionImplementation of the global fairness modelImplementation of the local fairness modelSimulationsDiscussions and Related WorkFurther IssuesRelated WorkConclusionTo appear in ACM Journal of Mobile Networks and Applications (MONET) Vol. 9, No. 3, June 2004 1A Packet Scheduling Approach to QoS Support in MultihopWireless NetworksHaiyun Luo∗, Songwu Lu∗, Vaduvur Bharghavan†, Jerry Cheng∗, Gary Zhong†∗Computer Science Dept.†Coordinated Science LaboratoryUniversity of California University of IllinoisLos Angeles, CA 90095 Urbana, IL 61801{hluo,slu,chengje,gzhong}@cs.ucla.edu [email protected] packet-level quality of service (QoS) is criticalto support both rate-sensitive and delay-sensitive applica-tions in the bandwidth-constrained, shared-channel, mul-tihop wireless networks. Packet scheduling has been avery popular paradigm to ensure minimum throughput andbounded delay access for packet flows. This work describesa packet scheduling approach to QoS provisioning in mul-tihop wireless networks. Besides minimum throughput anddelay bounds for each flow, our scheduling disciplines seekto achieve fair and maximum allocation of the shared wirelesschannel bandwidth. However, these two criteria can poten-tially be in conflict in a generic-topology multihop wirelessnetwork where a single logical channel is shared among mul-tiple contending flows and spatial reuse of the channel band-width is possible. In this paper, we propose a new schedul-ing model that addresses this conflict. The main results ofthis paper are the following: (a) a two-tier service modelthat provides a minimum “fair” allocation of the channelbandwidth for each packet flow and additionally maximizesspatial reuse of bandwidth, (b) an ideal centralized packetscheduling algorithm that realizes the above service model,and (c) a practical distributed backoff-based channel con-tention mechanism that approximates the ideal service withinthe framework of the CSMA/CA protocol.KeywordsWireless Scheduling, Fair Queueing, Ad-hoc networks,Wireless MAC1 IntroductionIn recent years, researchers have developed numerous re-source management algorithms and protocols for wirelessmobile networking environments [1, 2, 3, 4, 5, 6], e.g.,QoS oriented MAC layer design, packet scheduling, mobilitymanagement, admission control and resource reservation toname a few. The end goal of all these proposals is to deviseeffective management schemes for capacity-constrained andhighly dynamic wireless networks in order to support com-munication intensive applications with QoS that are compa-rable to their wireline counterparts. In many of these pro-posed designs, fair distribution of bandwidth and maximiza-tion of resource utilization have been identified as two impor-tant design goals, notably for scheduling disciplines [2, 3, 7].Fairness is critical to ensure that well-behaved users are notpenalized because of the excessive resource demands of ag-gressive users. Maximizing resource utilization is criticalto effectively support communication-intensive applications,e.g., web browsing, video conferencing and remote trans-fer of large files, which can easily stress the bandwidth-constrained wireless channel.Achieving both fairness and maximization of channel uti-lization in packet scheduling is particularly challenging in ashared-medium multihop wireless network. Since wirelesstransmissions are locally broadcast in the shared physicalchannel, location-dependent contention exists among flowsin a neighborhood [8]. How to ensure fair channel alloca-tion among spatially contending packet flows through packetscheduling has not been addressed in related literature. Be-sides, the multihop nature of a shared-channel wireless net-work makes spatial channel reuse possible [2, 4]. How tomaximize channel reuse, and hence the aggregate networkcapacity, poses another challenge. Unfortunately, the twogoals of ensuring fairness and maximizing resource utiliza-tion have inherent conflicts in shared-medium multihop wire-less networks, as we will illustrate in this paper. Two extremeapproaches for resolving this conflict are to either maximizethe aggregate channel utilization without any fairness consid-erations (potentially starving some packet flows), or enforcestrict notions of fairness across all flows in the network at thecost of possibly significant reductions in the aggregate chan-nel utilization.In this paper, we investigate a model for packet schedulingthat arbitrates these two design criteria in order to resolvethe inherent conflict between them. The main results of thispaper are the following: (a) a two-tier service model that pro-vides a minimum “fair” allocation of the channel bandwidthfor each packet flow and additionally maximizes spatial reuseof bandwidth, (b) an ideal centralized packet scheduling al-gorithm that realizes the above service model, and (c) a prac-tical distributed backoff-based channel contention mecha-nism that approximates the ideal service within the frame-work of the CSMA/CA protocol. We evaluate our approachthrough simulations and simple analysis.The organization for the rest of the paper is as follows. Sec-tion 2 explores the design issues and the solution space.Section 3 proposes a channel sharing model and a central-ized packetized algorithm that achieves the proposed modelwithin analytically provable performance bounds. Section4 presents a distributed backoff-based channel contentionmechanism that has the same long-term expected behaviorfor channel sharing as the proposed model. Section 5 evalu-ates the proposed mechanism through simulations. Section 6discusses related work, and Section 7 concludes the paper.2 Design Issues and Solution Space2.1 Network ModelOur network model is based on the ad hoc mode