The One-Sender-Multiple-Receiver Technique and DownlinkPacket Scheduling in Wireless LANsZhenghao Zhang, Steven Bronson, Jin Xie and Hu WeiComputer Science DepartmentFlorida State University Tallahassee, FL 32306, USAAbstractIn this paper, we study the One-Sender-Multiple-Receiver (OSMR) transmission technique, which allowsa sender to send to multiple receivers on the same fre-quency simultaneously by utilizing multiple antennas atthe sender. OSMR has the potential to significantly im-prove the downlink performance of wireless LANs, be-cause with OSMR, the Access Point (AP) can send dis-tinct packets to multiple computers at the same time. Tostudy the practicability of OSMR in the indoor environ-ments typical to wireless LANs, we implemented a proto-type OSMR transmitter/receiver with GNU Software De-fined Radio and conducted experiments in a universitybuilding. To the best of our knowledge, this is the firstimplementation and experimentation of OSMR. Our re-sults are positive and show that the wireless channels al-low OSMR for a significant percentage of the time. Wealso note that with OSMR, packet scheduling is neededat the AP to determine when a packet should be sentand whether it should sent together with other packetsusing OSMR. We focus on the problem of maximizingnetwork throughout, and propose a simple algorithm andprove that it has a performance ratio of11+√2comparedto the optimal algorithm. We evaluated OSMR and ouralgorithm with packet traces collected from 802.11a net-works, and the results show that our algorithm signifi-cantly improves the network throughput. Our algorithmis simple and is suitable for the implementations in APswith inexpensive processors.1 IntroductionWireless Local Area Networks (LAN) offer conve-nient access to the Internet. However, wireless LANs arestill much slower than wired LANs. For example, themaximum data rate of 802.11g and 802.11a networks is54Mps, while the maximum data rate of a typical Ether-net LAN is 100Mps. In addition, measurement studiesshow that the typical throughput of an 802.11 network isonly about half of the maximum data rate [19], while thetypical throughput of an Ethernet can be much closer toits maximum data rate. As new applications such as In-ternet TV are demanding more and more bandwidth, im-proving the performance of wireless LANs has attractedmuch attention in both the academia and the industry.In this paper, we study the One-Sender-Multiple-Receiver (OSMR) technique, which allows one senderto send to multiple receivers simultaneously by utilizingmultiple antennas at the sender [12]. OSMR could sig-nificantly improve the downlink performance of wirelessLANs, where the downlink refers to the link from the Ac-cess Point (AP) to the computers, because when the APis the sender, it can send distinct packets to multiple com-puters simultaneously. Most of the existing research re-lated to OSMR focus on theoretical signal processing andoften assume simplified network models, e.g., the avail-ability of a feedback channel for channel state update,homogeneous and constant traffic load among users, etc[15, 18]. To the best of our knowledge, OSMR has notbeen implemented and tested for wireless LANs, wherethere is no feedback channel and traffic loads of usersare heterogeneous and random. To find out the practi-cability of OSMR, we implemented a prototype OSMRtransmitter/receiver with GNU Software Defined Radio(SDR) that allows one sender to send to two receivers si-multaneously. An OSMR transmission depends on thechannel states of the receivers because it requires thesender to process the signals according to the channelstates. The critical questions related to the practicabilityof OSMR include (1) how likely are two receivers com-patible, where two receivers being compatible means thattheir channel states allow the sender to use OSMR, and(2) whether the channel fluctuation speed is slow enoughsuch that the measured channel state remains valid untilthe sender finishes sending, and whether the compatibil-ity relations of receivers are stable enough to allow in-telligent packet scheduling. Fortunately, our experimentsreveal that two receivers are usually compatible for a sig-nificant percentage of the time. Also, although the com-patibility relations vary as the channels fluctuate, in theindoor environment, the channel fluctuation is typicallyslow. Overall, our results are positive and show that thetypical wireless LAN environments allow packet trans-missions with OSMR. In addition, OSMR does not re-quire much change to the receiver hardware and OSMR-capable nodes and OSMR-incapable nodes can co-existin the same LAN.To take full advantage of OSMR, a packet schedulingalgorithm is needed at the AP. The AP runs this algorithmto decide which packet(s) to send to optimize the perfor-mance, e.g., maximizing the throughput. We formalizethe problem of maximizing network throughput as find-ing a c-matching in a graph, and propose an algorithmwith a performance ratio of11+√2compared to the op-timal algorithm. We evaluated our algorithm based ontraffic traces collected from 802.11a networks, and theresults show that it significantly improves the downlinkthroughout.The rest of the paper is organized as follows. Sec-tion 2 discusses the related works. Section 3 describesour implementation of OSMR. Section 4 describes ourOSMR experiments. Section 5 discusses application is-sues of OSMR and the backward compatibility with ex-isting 802.11 networks. Section 6 describes our packetscheduling algorithm. Section 7 evaluates the packetscheduling algorithms. Section 8 concludes the paper.2 Related WorksIn this section we discuss related works.2.1 Wireless Transmission TechniquesMultiple-Input Multiple-Output (MIMO) and802.11n. In an 802.11n LAN, to achieve a higherspeed than existing wireless LANs, nodes use MIMOto communicate with the AP [16]. However, althoughmultiple antennas are used, the transmission in 802.11nis still one-to-one. One the other hand, OSMR allowssimultaneous transmissions between one sender andmultiple receivers, which will help achieving an overallhigher efficiency. For example, in a wireless LAN, often,some nodes have very strong channels while others haveweak channels. Suppose node A has a weak channel, andthe AP cannot further increase the data rate to A due tothe constraint of transmission power. Suppose there isa node B that has a strong channel. Instead of sendingonly to A, the AP may allocate a very small amount