IntroductionRelated WorkMedium Access DiversityChannel ProbingData TransmissionOverviewPacket Concatenation (PAC)Incorporation with IEEE 802.11 MACIncorporation with IEEE 802.11 PHYOther PAC IssuesMAD SchedulingBasic Scheduling ModelApproximation Algorithmsk-Set Round RobinRevenue Based SchedulingPerformance AnalysisOptimal Number of Receivers to Query (k)Derivation of p.d.f. of MAD Transmission RateDerivation of Expected Goodput per Data TransmissionOptimal Value of kNetwork ThroughputPerformance EvaluationImpact of Traffic DensityImpact of D Impact of Number of FlowsImpact of Channel Coherence TimeNetwork Performance with Different TopologiesStar Topology with Variable DRandom TopologyConclusionREFERENCES -9ptExploiting Medium Access Diversityin Rate Adaptive Wireless LANs∗Zhengrong Ji, Yi Yang, Junlan Zhou, Mineo Takai, and Rajive BagrodiaComputer Science DepartmentUniversity of California Los AngelesLos Angeles, CA 90095{jizr, yangyi, zjl, mineo, rajive}@cs.ucla.eduABSTRACTRecent years h ave seen the growing popularity of multi-ratewireless network devices (e.g., 802.11a cards) that can ex-ploit variations in channel conditions and improve overallnetwork throughput. Concurrently, rate adaptation schemeshave been developed that selectively increase data trans-missions on a link when it offers good channel q uality. Inthis paper, we propose a Medium Access Diversity (MAD )scheme that leverages the benefits of rate adaptation schemesby aggressively exploiting multiuser diversity. The basicmechanism of MAD is to obtain instantaneous channel con-dition information from multiple receivers and selectivelytransmit data to a receiver that improves the overall through-put of the network, while maintaining temporal fairnessamong multiple data flows. We identify and address thechallenges in the design and implementation of MAD’s threephases: channel probing, data transmission, and receiverscheduling. We also use analytical models to examine thetradeoff between network performance improvement and over-head of channel probing, and derive an asymptotic perfor-mance bound for the receiver scheduling algorithms used byMAD. Results from the analysis and the extensive simula-tions demonstrate that, on average, MAD can improve theoverall throughput of IEEE 802.11 wireless LANs by 50% ascompared with the best existing rate adaptation scheme.Categories and Subject DescriptorsC.2.1 [Computer-Communication Networks]: NetworkArchitecture and Design—Wi reless Communication; C.2.2[Computer-Communication Networks]: Network Pro-tocols∗This research is funded in part by the National ScienceFoundation under NRT grant ANI− 0335302 WHYNET:Scalable Testbed for Next Generation Mobile Wireless Net-working Technologies, and the DARPA NMS program un-der contract N 66001−00−1−8937 MAYA: Next GenerationPerformance Prediction Tools f or Global Networks.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.MobiCom’04, Sept. 26-Oct. 1, 2004, Philadelphia, Pennsylvania, USA.Copyright 2004 ACM 1-58113-868-7/04/0009 ...$5.00.General TermsDesign, PerformanceKeywordsMedium Access, Multiuser Diversity, Scheduling, WirelessLAN1. INTRODUCTIONThe availability and low cost of 802.11 wireless networkingproducts have encouraged a rapid growth in the deploymentof wireless Local Area Networks (LANs). They can extendaccess to wired intranets such as campus networks, as wellas support broadband access to the Internet — particularyat “hot spots”. As t he use of powerful portable comput-ing devices (laptops, PDAs) with wireless LAN connectivitybecomes common, the ability of wireless LANs to cater tolarge number of users having applications with high band-width requirements is increasingly important. The increas-ing app etite for bandwidth in wireless LANs has in turnspurred extensive research efforts to provide high data ratesat the physical (PHY) layer. However, the highest feasiblerate is ultimately bounded by the channel signal to n oise ra-tio, which is time-varying due to both slow and fast fadingin mobile environments. This has encouraged the develop-ment of multi-rate adaptors, where the PHY layer data ratecan effectively resp ond to wide variations in channel con-ditions; the difference between t he lowest and highest datarates is expected t o widen even further with emerging PHYlayer tech nologies. This is evident by comparison of IEEE802.11a [12 ] with legacy 802.11 standard [11]: the lowestdata rate increased by a factor of 6 while the highest rateincreased by a factor of 27. The number of distinct datarates supported by PHY is increasing as well and the trendin next generation PHY technologies such as MIMO andAdaptive-Bit-Loading OFDM [8 ] is to provide wider, almostcontinuous range of data rates that can be tailored to thegiven channel quality.The multi-rate support at the PHY layer offers primitivesfor upper layers to respond in an agile manner to fluctu-ations in channel conditions and optimize channel utiliza-tion. Recent research efforts on rate adaptation schemesat the Medium Access Control (MAC) layer have focusedon dynamic rate switching mechanisms by either sender’sinference [15] or receiver’s feedback [9] of the current chan-nel conditions. Sadeghi et al. [23] shows that the successof rate adaptation depend s not only on th e ability to findthe highest feasible data rate for the given channel, butalso on the ability to optimize the link utilization undertime-varying channel conditions. Thus, the existing rate-adaptation schemes merely respond to th e quality of a givenchannel by selectively increasing the transmission rates whenthe channel condition is favorable.In contrast, this p aper proposes a scheme called MediumAccess Diversity (MAD), to actively exploit time and spacevarying channels at the MAC layer. In a wireless LAN envi-ronment, t he instantaneous channel conditions from a senderto multiple receivers are time varying and are not correlateddue to mobility, interference and other factors. This effectis referred to as multiuser diversity in the context of cellu-lar networks [16] but is observable in mobile wireless envi-ronments in