Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Radio resource allocation in emerging broadband wireless access networks : some analytical models and.. Rashid, Mohammad Mamunur 2010-04-14

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
24-ubc_2010_spring_rashid_mohammadmamunur.pdf [ 1.06MB ]
Metadata
JSON: 24-1.0065882.json
JSON-LD: 24-1.0065882-ld.json
RDF/XML (Pretty): 24-1.0065882-rdf.xml
RDF/JSON: 24-1.0065882-rdf.json
Turtle: 24-1.0065882-turtle.txt
N-Triples: 24-1.0065882-rdf-ntriples.txt
Original Record: 24-1.0065882-source.json
Full Text
24-1.0065882-fulltext.txt
Citation
24-1.0065882.ris

Full Text

Radio Resource Allocation in Emerging BroadbandWireless Access Networks: Some Analytical Models andTheir ApplicationsbyMohammad Mamunur RashidM.Sc. in Electrical & Computer Engineering, University of Manitoba, 2004B.Sc. in Computer Science & Engineering, Bangladesh University of Engineering &Technology, 2000A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFDoctor of PhilosophyinTHE FACULTY OF GRADUATE STUDIES(Electrical and Computer Engineering)The University Of British Columbia(Vancouver)April 2010c⃝Mohammad Mamunur Rashid, 2010AbstractNew generation wireless networks are designed not only to carry voice but also to supportdata-intensive and multimedia applications. Broadband wireless networks offer high band-width necessary to support these applications. However, without proper resource allocationschemes, increasedbandwidthisnotsufficienttomeetdiverseapplicationqualityofservice(QoS) requirements. In designing or deploying a resource allocation scheme, it is crucialto understand the inter-relationship of the resource allocation scheme and important systemparameters with resulting QoS performance. Analytical models provide an opportunity toderive these relationships in an accurate and readily verifiable way.In this thesis, we develop novel analytical models for radio resource allocation schemesin emerging broadband wireless access networks. These models are then adopted for in-depth analysis of QoS performance of the modeled schemes and in devising new solutionsbased on the models to either improve upon or complement those schemes. Our work pri-marily deals with Medium Access Control layer; however, in most of our contributions,we also consider cross-layer issues. First, we develop a queueing model for a downlinkpacket scheduling policy in IEEE 802.16e mobile broadband systems and propose a re-sourceallocationframeworkbasedonthismodel. Comparedtoexistingschemes, proposedframeworkoffersasimpleyetmoreeffectivewaytoprovideQoStoaheterogeneousmixofiiapplications. Second, we develop a cross-layer model for a prominent multiuser schedulingscheme in multi-antenna-based broadband cellular systems. It captures cross-layer effectsof important parameters of the multi-antenna physical layer. The model output is shownto have important applications in QoS provisioning. Next, we perform queueing analysisof controlled channel access mechanism in IEEE 802.11e-based Wireless Local Area Net-works. Using the insight gained, we propose a novel channel access scheduling mechanismthat achieves very robust performance in meeting QoS guarantees. Finally, we focus on apromising new technology called Cognitive Radio (CR), which can greatly improve spec-trum utilization in next generation broadband systems. We develop a queueing model toanalyze the performance of an opportunistic spectrum access mechanism in CR networks.The model has important applications including cross-layer analysis and admission controlin CR-based broadband networks.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvStatement of Co-Authorship . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Scope, Motivation and Objective of the Thesis . . . . . . . . . . . . . . . 41.2 Background and Literature Review . . . . . . . . . . . . . . . . . . . . . . 71.2.1 IEEE 802.16e Mobile WiMAX Systems . . . . . . . . . . . . . . . 71.2.2 Multiuser MIMO for Cellular Broadband Access . . . . . . . . . . 131.2.3 IEEE 802.11e based WLANs . . . . . . . . . . . . . . . . . . . . 161.2.4 Cognitive Radio for Broadband Wireless Access . . . . . . . . . . 20iv1.3 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.4 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 A Model-Based Downlink Resource Allocation Scheme for IEEE 802.16eMobile WiMAX Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.2 IEEE 802.16e and Its QoS Architecture . . . . . . . . . . . . . . . . . . . 382.2.1 Overview of IEEE 802.16e Air Interface . . . . . . . . . . . . . . 382.2.2 MAC Layer and QoS Framework . . . . . . . . . . . . . . . . . . 402.3 System Model and Related Assumptions . . . . . . . . . . . . . . . . . . . 422.4 A Queue-Length-Based Packet Scheduling Policy and Its Queueing Analysis 442.4.1 Queueing Analytical Model for the Packet Scheduling Policy . . . 462.5 Model-Based and Channel-Aware Downlink Resource Allocation . . . . . . 552.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602.6.1 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . 602.6.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . 622.7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772.9 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793 Cross-Layer Analysis of Downlink V-BLAST MIMO Transmission Exploit-ing Multiuser Diversity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 843.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 843.2 System Model and Assumptions . . . . . . . . . . . . . . . . . . . . . . . 873.2.1 MIMO Transmission Model and Receiver Architecture . . . . . . . 88v3.2.2 Modeling the MIMO Channel . . . . . . . . . . . . . . . . . . . . 903.2.3 Multiuser Diversity Scheme . . . . . . . . . . . . . . . . . . . . . 913.3 Queueing Model and Analysis . . . . . . . . . . . . . . . . . . . . . . . . 923.3.1 Formulation as a Quasi-Birth-and-Death Process . . . . . . . . . . 963.3.2 Matrix-Analytic Solution for Steady State Distributions . . . . . . . 1003.3.3 Derivation of Performance Measures . . . . . . . . . . . . . . . . . 1003.4 Numerical Results and Discussions . . . . . . . . . . . . . . . . . . . . . . 1033.4.1 Effect of Number of Transmit and Receive Antennas . . . . . . . . 1053.4.2 Effect of Transmit Antenna Correlation . . . . . . . . . . . . . . . 1073.4.3 Effect of Doppler Spread . . . . . . . . . . . . . . . . . . . . . . . 1113.4.4 Effect of Buffer Size, Traffic Intensity, and Number of Users . . . . 1123.4.5 Validation of the Queueing Model . . . . . . . . . . . . . . . . . . 1153.5 Application of the Queueing Model . . . . . . . . . . . . . . . . . . . . . . 1163.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1183.7 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1194 ControlledChannelAccessSchedulingforGuaranteedQoSin802.11e-BasedWLANs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1234.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1234.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1254.2.1 Overview of HCCA . . . . . . . . . . . . . . . . . . . . . . . . . . 1254.2.2 Reference HCCA Scheduler Design . . . . . . . . . . . . . . . . . 1264.3 Queueing Model and Analysis for the Reference HCCA Scheduler . . . . . 1274.3.1 Formulation of the Queueing Model . . . . . . . . . . . . . . . . . 1284.3.2 Markov Chain Analysis . . . . . . . . . . . . . . . . . . . . . . . . 130vi4.3.3 Matrix-Analytic Solution for Steady State Distributions . . . . . . . 1344.3.4 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . 1344.4 The Prediction and Optimization-Based HCCA (PRO-HCCA) Scheduler . . 1394.4.1 Accounting for Different Delay Bounds . . . . . . . . . . . . . . . 1404.4.2 Predicting VBR Traffic Intensities . . . . . . . . . . . . . . . . . . 1424.4.3 Optimizing TXOP Allocation . . . . . . . . . . . . . . . . . . . . . 1454.5 Performance Evaluation of the PRO-HCCA Scheduler . . . . . . . . . . . . 1474.5.1 Simulation Setup and Parameters . . . . . . . . . . . . . . . . . . . 1474.5.2 Simulation Results and Discussions . . . . . . . . . . . . . . . . . 1494.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1534.7 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1545 OpportunisticSpectrumSchedulingforMultiuserCognitiveRadio: AQueue-ing Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1575.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1575.2 The System Model and Assumptions . . . . . . . . . . . . . . . . . . . . . 1615.2.1 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1615.2.2 Primary User Activity . . . . . . . . . . . . . . . . . . . . . . . . . 1635.2.3 Channel Model and Adaptive Modulation . . . . . . . . . . . . . . 1645.2.4 Opportunistic Spectrum Scheduling . . . . . . . . . . . . . . . . . 1655.3 Formulation of the Queueing Model . . . . . . . . . . . . . . . . . . . . . 1665.3.1 Packet Arrival Process . . . . . . . . . . . . . . . . . . . . . . . . 1665.3.2 Joint System State Considering Primary User Activity, ChannelState, and Opportunistic Scheduling . . . . . . . . . . . . . . . . . 1675.3.3 Quasi-Birth-and-Death Process Formulation and Analysis . . . . . 170vii5.3.4 Matrix-Analytic Solution for Steady State Distributions . . . . . . . 1755.3.5 Derivation of Performance Measures . . . . . . . . . . . . . . . . . 1755.4 Numerical Results and Discussions . . . . . . . . . . . . . . . . . . . . . . 1775.4.1 Primary User Activity Level . . . . . . . . . . . . . . . . . . . . . 1785.4.2 Number of Channels Available for CR Users . . . . . . . . . . . . 1795.4.3 Channel Fading . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1805.4.4 Number of Admitted CR Users . . . . . . . . . . . . . . . . . . . . 1825.4.5 Queueing Model Validation . . . . . . . . . . . . . . . . . . . . . . 1845.5 Application of the Queueing Model . . . . . . . . . . . . . . . . . . . . . . 1855.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1865.7 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1886 Conclusions and Future Research Directions . . . . . . . . . . . . . . . . . . 1926.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1926.2 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1956.2.1 Models for End-to-End QoS in Multihop Wireless Broadband Net-works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1966.2.2 Cross-Layer Models for Various Multiuser MIMO Systems . . . . 1976.2.3 Analyzing Effects of CQI Feedback Issues . . . . . . . . . . . . . . 1976.2.4 Enhanced Queueing and Game Theoretical Models for SpectrumSharing in CR-based Wireless Broadband Systems . . . . . . . . . 1986.3 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199viiiList of TablesTable 2.1 System parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . 64Table 2.2 Modulation and coding schemes (MCS) used in the simulation . . . . 64Table 3.1 Throughputandpacketlossperformancefordifferentnumberoftrans-mit and receive antennas (fd = 15 Hz, γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1]) . . . . . . . . . . . . . . . . . . . . . . . . . 105Table 4.1 Packet overhead and MAC parameters . . . . . . . . . . . . . . . . . 148Table 4.2 Properties and QoS requirements of the scheduled streams . . . . . . 148Table 4.3 Summary of the results . . . . . . . . . . . . . . . . . . . . . . . . . 152Table 5.1 Effect of channel fading on the packet loss rate of CR users. . . . . . 181ixList of FiguresFigure 2.1 IEEE 802.16e frame structure . . . . . . . . . . . . . . . . . . . . . 39Figure 2.2 A simplified view of the system model . . . . . . . . . . . . . . . . 42Figure 2.3 CDF of packet delay for various values of model parameter x . . . . 61Figure 2.4 Model parameter x vs. packet loss rate . . . . . . . . . . . . . . . . 61Figure 2.5 System-wide packet loss rate for non-real-time services . . . . . . . 66Figure 2.6 Number of supported non-real-time service flows vs. their arrivalintensities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67Figure 2.7 System-wide packet delay violation probability for real-time services 69Figure 2.8 System-wide packet loss rate for real-time services . . . . . . . . . 69Figure 2.9 Number of supported service flows (real-time video streams) vs.their bit rates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71Figure 2.10 Numberofsupportednon-real-timeandreal-timeserviceflowscom-peting simultaneously . . . . . . . . . . . . . . . . . . . . . . . . . 72Figure 3.1 Packet delay distribution for different number of transmit and re-ceive antennas (fd = 15 Hz, γ0 = 10 dB, 5 users, Q = 50, α =[0.4,0.4,0.1,0.1]) . . . . . . . . . . . . . . . . . . . . . . . . . . . 105xFigure 3.2 Packet delay distribution for different transmit antenna correlation(fd = 15 Hz, t = 2, r = 2, γ0 = 10 dB, 5 users, Q = 50, α =[0.4,0.4,0.1,0.1]) . . . . . . . . . . . . . . . . . . . . . . . . . . . 108Figure 3.3 Effect of Tx antenna correlation on packet loss rate (fd = 15 Hz,t = 2, r = 2, γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1]) . 108Figure 3.4 Average throughput for different levels of antenna correlation (fd =15 Hz, t = 2, r = 2, γ0 = 10 dB, 5 users, Q = 50, α =[0.4,0.4,0.1,0.1]) . . . . . . . . . . . . . . . . . . . . . . . . . . . 109Figure 3.5 Packet delay distribution for various Doppler spread (t = 2, r = 2,ρ = 0.1, γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1]) . . . . 110Figure 3.6 Packet loss rate for various fading rates (t = 2, r = 2, ρ = 0.1,γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1]) . . . . . . . . 110Figure 3.7 Average throughput for various fading rates (t = 2, r = 2, ρ = 0.1,γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1]) . . . . . . . . 111Figure 3.8 Delay distribution for different buffer size and traffic arrival profiles(AP) (fd = 15 Hz, t = 2, r = 2, ρ = 0.1, γ0 = 10 dB, 5 users) . . . . 113Figure 3.9 Effect of the number of users on packet delay distribution (fd = 15Hz, Q = 50, t = 2, r = 2, γ0 = 10 dB, ρ = 0.1, Arrival profile =AP1 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113Figure 3.10 MAC layer throughput for different number of users (fd = 15 Hz,Q = 50, t = 2, r = 2, γ0 = 10 dB, ρ = 0.1, Arrival profile = AP1 ) . 114Figure 3.11 Effectof thenumber ofcompeting userson packetlossrate (fd = 15Hz, Q = 50, t = 2, r = 2, γ0 = 10 dB, ρ = 0.1, Arrival profile =AP1 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114xiFigure 4.1 Timing diagram for the reference HCCA scheduler showing differ-ent timing periods and their relationships within a beacon intervalhaving two SI periods. . . . . . . . . . . . . . . . . . . . . . . . . . 127Figure 4.2 Cumulative distribution function of access delay (ms) derived fromthe analytical model. . . . . . . . . . . . . . . . . . . . . . . . . . . 137Figure 4.3 Cumulativedistributionfunction(derivedfromtheanalyticalmodel)of queue length at the end of a TXOP. . . . . . . . . . . . . . . . . . 137Figure 4.4 Cumulative distribution function of delay (ms) experienced by pack-ets generated from the interactive video stream. . . . . . . . . . . . . 149Figure 4.5 Cumulative distribution function of delay (ms) experienced by pack-ets generated from the non-interactive video stream. . . . . . . . . . 150Figure 4.6 Cumulative distribution function of delay (ms) experienced by pack-ets generated from the VBR VoIP stream. . . . . . . . . . . . . . . . 151Figure 5.1 Infrastructure-basedcognitiveradionetworkarchitecture(CR=Cog-nitive radio; PU = Primary user; BS = Base station). . . . . . . . . . 162Figure 5.2 Effect of primary user activity level on packet delay distribution ofCR users. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179Figure 5.3 Effect of primary user activity level on packet loss rate of CR users. . 180Figure 5.4 Effect of number of cognitive channels on packet delay distributionof CR users. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181Figure 5.5 Effect of number of cognitive channels on packet loss rate of CR users.182Figure 5.6 Effect of channel fading on the packet delay distribution of CR users 183Figure 5.7 Packet delay distribution for different number of CR users in thecognitive radio network. . . . . . . . . . . . . . . . . . . . . . . . . 184xiiFigure 5.8 Packet loss rate for different number of CR users in the cognitiveradio network. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185xiiiAcknowledgmentsManythanksgotoallthosewhowereinstrumentalinthedevelopmentofthisthesis. First, Imust thank my supervisor, Professor Vijay K. Bhargava for his great guidance, support andencouragement throughout my academic studies and this research. Second, I would like tothank Professor Ekram Hossain for all his invaluable suggestions and helpful advice. I amgrateful to my past and present colleagues in the Information Theory and Systems (ITS)laboratory for providing me with their genuine and friendly support during the course ofmy PhD research. I would also like to acknowledge with gratitude the support from theUniversity of British Columbia in the form of Graduate Fellowship and a number of otherscholarships.Great appreciation goes to my family, specially to my parents for their unconditionalloveandforalwaysbeingbehindme. Iamprofoundlyindebtedtomylovingwife, ZakiRe-zoana, for her continued encouragement, support and sacrifice, that have been instrumentalin the successful accomplishment of this endeavor.xivTo My Parents...xvStatement of Co-AuthorshipI am the primary researcher and author for all the research contributions made in this the-sis. I identified the research problems, conducted literature review and performed researchto address those problems. Mathematical analysis and formulation of the problems anddevelopment of novel schemes were totally carried out by me. I wrote the computer pro-grams for analyzing the mathematical models and for simulating performances of proposedschemes. I also prepared the associated manuscripts for publication. Prof. Ekram Hossainis a co-author for contributions in Chapters 3, 4 and 5. He provided some important feed-backs during the identification and formulation of the research problems addressed in thosechapters. In Chapter 3, he provided some input during the derivation of a small part of themathematical formulation. He also checked the mathematical derivations for correctnessand provided some editorial corrections for the associated manuscripts. Dr. Md. J. Hos-sain is a co-author for the contribution in Chapter 5. I consulted him during identificationof the research problem. He also provided some technical feedbacks that helped in im-proving a part of the mathematical model developed in that chapter. My supervisor Prof.Vijay Bhargava is a co-author for contributions made in Chapters 2, 3, 4 and 5. I consultedhim during the identification and formulation of the research problems. He also providededitorial feedbacks during my preparation of the manuscripts for publication.xviChapter 1IntroductionWith the explosive growth of Internet and widespread deployment of multimedia appli-cations, the role of wireless networks has altered significantly. Current wireless com-munications networks are designed not only to carry voice but also to support data andmultimedia applications. Broadband wireless access networks such as WiFi (Wireless Fi-delity), WiMAX (Worldwide Interoperability for Microwave Access), beyond 3G (ThirdGeneration) systems offer high bandwidth necessary to support these new applications andservices. However, these multimedia and other data-intensive applications come with theirown stringent Quality of Service (QoS) requirements for their smooth operation. For ex-ample, live video streams need to meet certain latency requirements to avoid choppy videosequences at the viewers’ ends; VoIP communications need to fulfil certain latency andpacket loss requirement for the involved parties to continue a meaningful conversation.Fulfilling these QoS requirements still remain challenging in broadband wireless systemsdespite the fact that they are able to offer much higher bandwidth and data rate than those intraditional wireless systems. Many research problems remain open–especially in the area1of radio resource allocation. Studying the relevant issues and challenges and developingsolutions to these open problems are therefore very crucial for successful deployment ofthese emerging broadband wireless systems.Asbroadbandwirelesscommunicationsisarecentphenomenon,systemsofferingbroad-band wireless access are still undergoing very active research and development stage. IEEE802.11 standard [1] was finalized for Wireless Local Area Networks (WLAN), which even-tually have become the most successful and widely deployed broadband wireless accessnetworks across the globe. The technology for IEEE 802.11 WLANs, also referred asWiFi, is aimed at providing broadband access in the range of 100 meters–typically cover-ing university campuses, hospitals, home and business complexes. Although WiFi technol-ogy supports a very limited mobility, it has been mainly targeted towards fixed broadbnadaccess within a small geographic area. For mobile users, the cellular technologies beforethe introduction of third generation (3G) cellular systems were designed mainly to carryvoice. By offering the capability to simultaneously carry voice and data services, 3G cel-lular systems have significantly altered mobile wireless access. Personal mobile phonescould now be used not only for regular phone conversations but also for accessing email,browsing internet and accessing other data services. However, the data transmission speedoffered by this technology was still not enough to offer true broadband quality. 3G+ cameinto picture as a natural evolution of 3G networks to offer mobile broadband services withmuch faster speed than 3G using High Speed Packet Access (HSPA) technology. Recently,Multiple Input Multiple Output (MIMO) technology has dramatically increased the datarate and throughput of 3G+ systems by employing multiple transmit and/or receive anten-nas. Although 3G+ is a significant advance towards realizing wireless broadband access,the technology still remains relatively costly and suffers from a number of limitations in2terms of QoS support and spectral efficiency. WiMAX is another emerging technologythat has revolutionalized broadband wireless access. Compared to 3G/3G+, it offers sim-pler, faster and more cost-effective broadband access. Using mostly cellular architecture,WiMAX can offer such access in the range of few kilometers, typically capable of coveringlarge metropolitan, suburban, or rural areas. The technology is IP-based, comes with QoSsupport and high spectral efficiency. Although the initial IEEE standard 802.16 [2] wasfinalized by IEEE in 2001, WiMAX networks are at the early stage of deployment. In spiteof all these advancements, underutilization of radio spectrum remains a critical issue be-cause of the static allotment of spectrum among wireless service providers. Cognitive radio(CR) technology [3] has been introduced to implement a new dynamic spectrum sharingparadigm that can dramatically improve spectrum utilization across different broadbandaccess networks. With this technology, valuable spectrums that might remain unused oth-erwise (such as TV-bands during off-peak hours), can also be harnessed to enhance theperformance, capacity and coverage of broadband wireless networks. A new IEEE stan-dard, named IEEE 802.22 [4], is now in development that aims to offer cognitive radiosupport for broadband wireless access.The abundance of raw bandwidth that these networks offer by using new transmissiontechnologies, however, itself is not sufficient to support the QoS requirements of the newapplications. In these multiuser systems, applications and services associated with dif-ferent user-ends compete for a common pool of radio resource to meet a diverse set ofQoS requirements. The improvement in the raw data rate can be easily squandered if thisshared resource is poorly managed and inefficiently allocated among competing users. Be-sides, the diversity in QoS requirements of different applications necessitates QoS-awareresource allocation schemes. The resource allocation schemes determine how the available3radio resource will be allocated to competing users or services over time. A common de-sign goal for these schemes is to improve utilization of the broadband quality bandwidthby increasing the number of users that can be supported by the system while fulfilling QoSpledges.1.1 Scope, Motivation and Objective of the ThesisA common thread in this thesis is the development of novel analytical models for radio re-source allocation techniques in a number of emerging broadband wireless access networks.These models are then adopted to achieve two main objectives: in-depth analysis of QoSperformance of the modeled radio resource allocation techniques and devising new solu-tions based on these models to either improve upon existing schemes or to complement theoperations of those schemes.In designing or deploying a resource allocation scheme, it is crucial to understand theintricate inter–relationship among different system parameters, the dynamics of the re-source allocation scheme and resulting system performance. Analytical models providethe opportunity to derive these relationships in an accurate and readily verifiable way.These models also allow the system engineers to analyze their choice of design param-eters quickly and efficiently without first developing comprehensive simulation programsthat might take considerably long time to develop and may be extremely costly as well.The models offer excellent opportunity for optimizing the parameter selection so that thosesystem parameters can be selected that can optimize some performance measures given re-source constraints and QoS requirements. For example, some service providers may wantto ensure that audio/video over their networks are served within some delay constraints andat the same time wants to maximize the number of users to optimize their revenue poten-4tial. The analytical models can also greatly assist system engineers in capacity planning fortheir wireless networks by offering time-efficient means for gauging the QoS effects of thenumber of admitted users in the system. In summary, such analytical models offer moreaccurate, timely and efficient analysis compared to detailed simulation studies for resourceallocation schemes and can greatly expedite the design and optimization of these systems.This remains the primary motivation for our work.The analytical models, however, need to be designed carefully to consider a numberof important factors. For example, the analysis of physical layer performance such as bit-error-rate (BER) itself may not provide meaningful QoS information at user ends becausemany MAC layer factors such as scheduling and admission control affect the performanceexperiencedbyusers. Ontheotherhand, performancemodelofaschedulingalgorithmthatruns in the MAC layer will be much more accurate and realistic if important physical layerparameters such as channel fading are considered. Although many cross-layer analysishave been done in literature, the researchers vary widely on what to consider as cross-layer.Many researchers have limited their cross-layer analysis to the rate and power adaptationin the wireless links in response to varying channel conditions. However, such analysisfails to cover important MAC layer dynamics and are not truly cross-layer in nature. Otherimportant factors to consider in developing the analytical models include realistic trafficmodeling and proper selection of performance measures to analyze. Most of the existingMAC layer-specific or cross-layer analytical models for the wireless systems that we con-sider in this thesis have assumed unrealistic traffic models and/or buffer dynamics (e.g.infinite buffer space), and have derived performance measures that are often inadequate asQoS measure for many multimedia services. Besides, application of these analytical mod-els have not been well-addressed in these works. These limitations in the existing works5have also motivated us to better address these factors in this thesis.The scope of this thesis encompasses resource allocation techniques in a number ofemergingbroadbandwirelesstechnologies: IEEE802.16eWiMAX,IEEE802.11eWLAN,3G+ MIMO cellular and CR networks. We mainly focus on the Medium Access Control(MAC) layer because it is responsible for coordinating communication access over theshared wireless medium and hence, plays the pivotal role in resource allocation techniques.Therefore, our work primarily deals with MAC layer techniques such as channel accessscheduling, packet scheduling and admission control. In most of our contributions, we alsoconsider cross-layer effects of important physical layer parameters on these MAC layertechniques. However, wedonotmodelorproposepowerandrateallocationtechniquesthatare usually performed at the physical layer. Instead, in the cross-layer models or schemesproposed in this thesis, we consider certain rate allocation mechanisms implemented in thephysical layer and aim to incorporate their effects in the modeling.The broad objectives of this thesis are to investigate QoS performance of certain re-source allocation techniques in emerging broadband wireless systems through analyticalmodeling and to derive improved or complementary solutions using outputs from these an-alytical models. In the following, we list very briefly the specific objectives of this thesis:1. To develop an analytical model for a downlink packet scheduling policy in IEEE802.16emobileWiMAXsystems, andtodesignanoveldownlinkresourceallocationscheme based on this analytical model. In designing the proposed scheme, we try toachieve better QoS performance than existing downlink resource allocation schemesfor mobile WiMAX systems.2. To develop an analytical model of a prominent multiuser scheduling scheme forMIMO downlink transmissions in 3G+ cellular systems (e.g. HSDPA) employing6spatial multiplexing and then to show the application of the model in a number ofsystem engineering purposes that include cross-layer analysis and QoS provisioning.3. To analyze the performance of the resource allocation mechanism for guaranteedQoS provisioning in the IEEE 802.11e WLAN standard through a queueing analyti-cal model and then to apply the insight gained from the model in designing a betterchannel access scheduling scheme.4. To analyze opportunistic spectrum access scheduling in cognitive radio based broad-band wireless systems through a queueing analytical model and to show how thismodel can be applied for cross-layer analysis and model-based admission control inCR-based broadband wireless access systems1.2 Background and Literature ReviewIn this thesis, we address the resource allocation problem with special emphasis on QoSprovisioninginanumberofemergingbroadbandwirelessnetworks. Thissectionsoverviewsthe underlying standards and/or technologies and provides a literature review of relatedworks on resource allocation and QoS provisioning in these broadband systems.1.2.1 IEEE 802.16e Mobile WiMAX SystemsThefirstIEEEstandardforWiMAXsystemswascompletedinOctober2001andpublsihedin April 2002. This initial standard, also known as IEEE 802.16-2001 [2], was proposedfor fixed wireless broadband access over a Wireless Metropolitan Area Network (WMAN).The core IEEE 802.16 standard defined the physical layer (PHY) for the 10-66GHz rangeof (licensed) spectrum. With single carrier quadrature amplitude modulation (QAM) in7the PHY layer, the core IEEE 802.16 system is referred to as WirelessMAN-SC. Non-line-of-sight (NLOS) operation is infeasible in this frequency range. IEEE 802.16a thenextended the PHY layer specification to support the 2-11GHz band of licensed and unli-censed spectrum. The standard also removed the requirement for LOS operation. To takeinto account the effects multipath in a NLOS environment, orthogonal frequency divisionmultiplexing (OFDM) was added to the specification as modulation scheme. The releaseof 802.16-2004 [5] superseded the earlier 802.16 documents for fixed wireless broadbandaccess. The IEEE 802.16e standard was introduced in 2005 as an amendment to IEEE802.16-2004 to address user mobility. As such, it is also known as the standard for mobileWiMAXsystems. SimilartothecoreIEEE802.16standard, theIEEE802.16eonlydefinesthe architecture, air interface, MAC protocol specifications and a QoS infrastructure.The Architecture and Air InterfaceThe IEEE 802.16 standard specifies two modes for sharing the wireless medium: point-to-multipoint (PMP) and mesh (optional). With PMP, the base station (BS) serves a set ofstations (SSs) within the same antenna sector in a broadcast manner. Transmissions fromSSs are directed to and centrally coordinated by the BS. On the other hand, in mesh mode,traffic can be routed through other SSs and can occur directly among SSs. In this thesis,we focus mainly on the PMP mode. In IEEE 802.16e, the architectures remain similar;however, an SS in the network is now refereed as a mobile station (MS) to account forpotential user mobility.The IEEE 802.16e air interface uses Orthogonal Frequency-Division Multiple Access(OFDMA)asitscoretechnology. Thecommunicationovertheairinterfaceisframe-based,whereaframeisconstitutedfromanumberofOFDMAslotsthatserveasthebasicresource8allocation units. Each OFDMA slot combines a certain number of OFDMA symbols allo-cated in the time domain and subcarriers grouped in subchannels in the frequency domain.How many symbols and subchannels will be used to form an OFDMA slot depends onthe subchannelization mechanism, which can be either diversity-based or contiguous. WithOFDMA-TDD, an IEEE 802.16e frame is further divided into a downlink (DL)-subframeand an uplink (UL)-subframe. Control information for all connections scheduled in the DLand UL subframes is carried by DL- and UL-submaps that are broadcast as part of a DL-submap. The DL-and UL-MAPs are composed of smaller elements known as informationelements (IEs). Each IE describes an MS’s allocation and provides information, such asthe Modulation and Coding Scheme (MCS), resource size, location of the allocation in theframe.MAC Layer Specification and QoS InfrastructureMAC layer in an IEEE 802.16e systems performs several important functions includingresource allocation, link adaptation, error recovery, network entry, mobility managementas well as security and authentication. The MAC layer of WiMAX systems is connection-oriented, where a transport connection serves as a context for data communications overa service flow between the BS and an MS. For QoS management, the concept of serviceflow was introduced, which defines the QoS parameters for a unidirectional flow of pack-ets. A service flow is created and its QoS parameters are defined through Dynamic ServiceAddition (DSA) messages that are exchanged between the BS and the MS associated withthe service flow. The service flow and its QoS parameters can subsequently be updatedthrough Dynamic Service Change (DSC) messages. Upon admission into the system, anactive service flow is associated with a transport connection–identified by a unique connec-9tion ID (CID). For applications needing bidirectional communication, two service flowsand correspondingly, two transport connections are created–one for each direction.Another concept relevant to QoS support in WiMAX systems is scheduling service,which essentially refers to the data handling mechanism associated with a connection. TheIEEE 802.16 restricted all service flows, both in downlink and uplink, to four schedulingservices: Unsolicited Grant Services (UGS), Real-time Polling Services (rtPS), Non-real-time Polling Services (nrtPS) and Best Effort (BE). UGS is designed to support real-timeapplications (with strict delay requirements) that generate fixed-size data packets at peri-odic intervals. Uplink grants are granted by the BS regardless of the current estimation ofbacklog; hence, UGS connections use the unsolicited granting bandwidth-request mecha-nism(i.e.,UGSconnectionsneverrequestbandwidth). rtPSisdesignedtosupportreal-timeapplications (with less stringent delay requirements) that generate variable-size data pack-ets at periodic intervals, such as MPEG video and VoIP with silence suppression. UnlikeUGS and rtPS, nrtPS and BE are designed for applications that do not have any specificdelay requirement. The main difference between the two is that nrtPS connections are re-served a minimum amount of bandwidth (by means of the minimum reserved traffic rateparameter), which can boost performance of bandwidth-intensive applications (e.g. FTP).IEEE 802.16e introduced major changes to the definition and scope of scheduling ser-vices (section 6.3.5 of IEEE 802.16e-2005 [6]). Although the underlying concept remainssimilar, association of service flows in the downlink need not confine to a mandatory listof scheduling services. The standard suggests but does not mandate a number of QoS pa-rameters that would provide scheduling service for different types of applications such asreal-time and non real-time VBR video, VoIP. In essence, incorporating a flexible interpre-tation of scheduling services, IEEE 802.16e allows scheduling services of a service flow to10bedefinedbyits statedQoSparameters. Besidesthe parametersalreadydefinedin thestan-dard, these QoS parameters can also include vendor defined parameters. In the uplink, thescheduling services are renamed as scheduling types and every service flow in the uplinkneeds to define its scheduling type from a set of five predefined types: UGS, rtPS, nrtPS,Extended Real-time Polling Service (ertPS) and BE. The scheduling type determines thebandwidth request/grant mechanism for uplink connections.Resource Allocation SchemesOverall, from the resourc allocation perspective, the IEEE 802.16e defines the necessaryinfrastructure, signaling and messaging mechanism, but leaves open the designs of the re-source allocation schemes. Previous work on resource allocation on WiMAX systems hasevolvedovertimeasthestandardizationactivitieshavematured. Previousworkonresourceallocation on WiMAX systems has evolved over time as the standardization activities havematured. For the basic 802.16 standard, which was introduced with single-carrier PHY,the resource allocation problem, however, is very similar to that in TDMA-based cellularsystems. This also applies to OFDM PHY, as with IEEE 802.16d, where all subcarriers areallocated as a whole to a particular MS during a frame either in the uplink or the down-link direction. Many of the earlier resource allocation solutions were proposed assumingtime division multipexing without focusing on any specific PHY. They are often packetscheduling schemes based on traditional time-domain radio resource scheduling solutionsand are customized to make compatible with the scheduling service classes defined in the802.16 standard. Some of these schemes are designed for specific traffic types such asvideo, VoIP and targets the relevant service classes. For delay sensitive applications thatuse rtPS scheduling service, EDF and Modified Largest Weighted Delay First (MLWDF)11were evaluated in previous research. Classical wired network schedulers such as WeightedRound Robin (WRR), WFQ and their variants were also proposed and evaluated for bothdelay-sensitive rtPS and throughput-guaranteed nrtPS applications. Wongthavarawat andGanz [7] proposed a hierarchical scheduling scheme where EDF and WFQ are used forintra-calss scheduling of rtPS and nrtPS connections respectively, and a simple prioritybased scheme is adopted for allocating resource among different service classes. Othernotable solutions include a hierarchical scheme proposed by Wang and Dittman in [8], across-layer scheme proposed by Liu et al. [9], a joint queueing and optimization basedscheme by Niyato and Hossain [10] and a fuzzy logic based approach proposed by Chen etal. [11]Resource allocation schemes specifically proposed for OFDMA-based WiMAX sys-tems, however, follow two main avenues of research. The first avenue of research con-siders subcarrier/subchannel assignment along with rate and power adaptation across usersmainly to improve system level performance such as capacity and throughput. These solu-tions have basic similarity with those for OFDMA resource allocation problem in general.Examples of such solutions are [12, 13, 14, 15] and their main limitation is that the goalis to improve system performance but not necessarily to provide specific QoS to applica-tions and service. The second category of solutions involve frame-by-frame schedulingof OFDMA subchannels or slots among admitted service flows or connections. Yahiyaet al. [16] proposed a cross-layer scheduling mechanism that assigns priorities to UGS,rtPS and nrtPS connections for each available subchannel. In [17], Mehrjoo et al. pro-posed a queue- and channel-aware schedular, called opportunistic stable queue schedulingfor WiMAX downlink. The scheduler, however, aimed to improve overall throughput andpacket dropping probability experienced by MSs in the system. In [18], Ali et al. proposed12a cross-layer scheme where the scheduling priorities of different connections are calcu-lated using channel quality, service class and QoS requirements of the connections. Wanet al. took a similar approach in [19], but resorted to priority-based scheduling to avoidcomplexity of an optimized solution.1.2.2 Multiuser MIMO for Cellular Broadband AccessAfter MIMO technology was introduced, extensive research has been done by many re-searchers to devise schemes to reach its promised capacity. In traditional single-user pointto point MIMO systems, the extra spatial degree of freedom offered by multiple antennasis utilized by advanced transmission schemes such as Space-Time Block Coding (STBC)and advanced receiver techniques to boost signal quality at the receiver and better combatchannel errors. In such systems, the MIMO technology can be viewed primarily as a wayto boost the physical layer performance. Although the MAC layer and upper layer pro-tocols can benefit from this increased physical layer performance without being aware ofthe available MIMO capability, the true potential of MIMO cannot be be realized this way.More recent advances in MIMO, therefore, have been more focused on multiuser MIMO,which essentially takes a coordinated design approach between the MAC layer shcedul-ing/resource allocation and the availability of a MIMO physical layer [20] . Informationtheoreticresultsinthisfieldhaveshownthatsuchcoordinateddesignapproachisnecessaryfor optimal system performance [21]. In fact, an uncoordinated approach can cause severeperformance degradation as can be seen when both layers attempt to extract diversity (e.g.use of channel-hardening [22] single-user space-time codes at the PHY combined withmultiuser diversity scheduling at the MAC). Multiuser MIMO provides lot of advantagessuch as providing multiuser diversity in addition to antenna diversity and user multiplexing13in addition to stream multiplexing. Multiuser MIMO, however, introduces its own set ofproblems–especially in resource allocation.Resource Allocation in Multiuser MIMO SystemsResource allocation problems arise in multiuser MIMO systems in both downlink and up-link. In the downlink, which is often referred as MIMO broadcast channel (BC), the objec-tive is often to reach as close as possible to the information-theoretic capacity limit of theMIMO BC. A concept known as dirty paper coding (DPC) has been shown to make reach-ing this limit possible–at least in theory [23]. Despite significant theoretical interest, thistype of scheme is impractical because of its sheer extremely complex and need for codesthat are incompatible with existing communication systems and protocols [24].A simpler and popular scheme is called spatial multiplexing, which is a suboptimalscheme where BS equipped with multiple antennas sends parallel data streams across itstransmit antennas. Each user’s data is encoded independently of the others, allowing theuse of traditional modulation and coding schemes. One of the most prominent spatialmultiplexing systems is known as Vertical-Bell Labs Layered Space-Time (V-BLAST) sys-tem[25,26], whichwasproposedbyBellLaboratoriesasanextremelyefficientschemeforhigh capacity communications in wireless environments. Spatial multiplexing, however,requires the interference produced by the transmitter to be mitigated or balanced amongall of the users in order to meet their QoS requirements [24]. To this end, a number of re-ceiverarchitectures, suchasthezero-forcing(ZF)receiver, theminimummeansquareerror(MMSE) receiver and the successive interference canceller (SIC), have been investigated todecode the spatially multiplexed signals over the multiuser MIMO downlink [27]. With aZF receiver, the basic idea is to drive inter-user interference to zero and the design offers an14attractive low-complexity solution. Moreover, ZF receivers in conjunction with multiuserdiversity have been shown to scale identically to optimal DPC strategy when number ofusers approaches infinity [28, 29]. However, the assumption of infinite user population forsuch optimal performance is not applicable in practical MIMO systems.Developing scheduling strategies to best exploit multiuser diversity in multiuser MIMOsystems with finite number of users and evaluating the capacity limit achieved by thosestrategies remain an active area of research. To this end, Shao et. al. proposed opportunis-tic beamforming where resources are allocated to only one user who has the best equivalentchannel created by the multiple antennas and beamforming. In [30], a random beamform-ing technique was proposed, where the best single user is selected in communication basedon the limited feedback information from the users. In [31] the authors studied multiuserdiversity gain by selecting a single user or selecting multiple users simultaneously commu-nicating in downlink.In the multiuser MIMO uplink, the resource allocation is a multiple access problem,which is often referred as space-division multiple access (SDMA). A nearly optimal trans-mission strategy would be to group a number of users with SDMA within each group andto implement orthogonal multiple access between the groups [32]. Combination of theseuser subsets can vary over time and in a SDMA/TDMA system a challenge is to determinehow users belonging to same subset have to be time-multiplexed as well. There have beennumerous proposals [33, 34, 35] mainly on how to select suitably small user subset for si-multaneous transmission (multi-user scheduling) in system potentially with a large numberof users. Similar to downlink, multiuser diversity is also considered in user selection inuplink scheduling in multiuser MIMO systems [36].15Cross-layer Performance Analysis of Multiuser MIMO SystemsPerformance analysis of resource allocation in multiuser MIMO systems has been an ac-tive area of research. Heath Jr. et al. in [31] have presented simulation analysis on variousways to exploit the multiuser diversity in multiuser MIMO systems and their effects on thespectral efficiency of the system. Airy et al., on the other hand, have presented analyticalmodels in [37] to compare two opportunistic scheduling techniques in this context. Othernotable works on this topic are [38, 39, 40, 41, 42, 43]. In most of the research works,however, the focus has been mainly on the capacity, throughput and/or outage probabilityachievable at the physical layer. The performance measures are the raw bit rate achievablefrom the system and the average delays experienced by fixed sized files served from differ-ent users. Developing a truly cross-layer analytical model that captures the layered aspectof the system design, derives more comprehensive performance measures such as packetdelay statistics, packet throughput and loss rate, and relates these performance to importantphysical layer, link layer and traffic parameters has not been addresses in the literature.One of our contributions is on such cross-layer modeling.1.2.3 IEEE 802.11e based WLANsAfter its introduction in 1999, the IEEE 802.11 standard became the de facto standardfor the deployment of WLANs. In subsequent years, it has gone through a number ofamendments to address limitations and to incorporate new features and capabilities such asQoS support. In this thesis, we focus mainly on QoS aspects of these networks, which areaddressed in the IEEE 802.11e [44] amendment. In this subsection, we therefore start withthe basic IEEE 802.11 standard and then gravitate towards the IEEE 802.11e standard.16The Architecture and Air InterfaceA basic service set (BSS) is the fundamental building block of the architecture. It is com-prisedofagroupofwirelessstations(STAs)encompassingageographicalareacalledBasicService Area (BSA). BSA is a similar concept to a cell in a cellular wireless network. Ac-cording to IEEE 802.11 standard, a WLAN can be configured in two modes, either as aninfrastructure network or an ad-hoc network. In infrastructure networking, all STAs areconnected directly to an Access Point (AP) which is connected to a wired network. Com-munication between devices inside a BSS goes through the AP. An AP can also work as anintegration point between multiple BSSs, thus forming an extended service set (ESS). Inthis situation, an AP connects to a distribution system (DS) that integrates multiple BSSs.The DS can be thought of as a backbone network and it could even be wired. In an ad-hocmode, there is no AP and STAs can form a network “on the fly”. The STAs communicatedirectlywitheachother. Thenetworktopologychangesdynamicallyasmobilenodescomein and out of the network.For the physical layer, three different alternatives were proposed: infrared PHY (neverimplemented widely), frequency hopping spread spectrum (FHSS) PHY and direct se-quence spread spectrum (DSSS) PHY. The PHY specification, however, was supersededby three revisions namely 802.11b, 802.11g and 802.11a. The 802.11b uses DSSS in thePHY and offers a maximum data rate of 11 Mbps in the unlicensed 2.4GHz radio band.On the other hand, 802.11g and 802.11a both use OFDM in the PHY and support upto 54Mbps data rate in the unlicensed radio band of 2.4 GHz and 5 GHz respectively.The IEEE 802.11e standard developed by 802.11 Task Group E proposes to enable themuch needed QoS support , which is absent in the basic 802.11 standard. The BSS is nowcalled QBSS with QoS access point (QAP) and QoS stations (QSTAs).17MAC Layer Specification and FunctionalitiesThe IEEE 802.11 standard specifies two MAC protocols: Distributed Coordination Func-tion (DCF) and the optional Point Coordination Function (PCF). An interval between twosuccessivebeaconframesconsistsofanoptionalContentionFreePeriod(CFP)followedbya Contention Period (CP). CFP occurs only if PCF is enabled. DCF is a distributed accesscontrol protocol based on the carrier sensing multiple access with collision avoidance (CS-MA/CA). The centrally-coordinated access mechanism of the IEEE 802.11 MAC, calledthe PCF, adopts a poll-and-response protocol to control the access to the shared wirelessmedium and eliminate contention among wireless stations.The IEEE 802.11e introduces QoS support through the introduction of Hybrid Coordi-nation Function (HCF). HCF offers channel access through two MAC schemes: EnhancedDistributed Channel Access (EDCA) for prioritized QoS and HCF Controlled Channel Ac-cess(HCCA)forparameterizedQoSprovisioning. OnemainfeatureofHCFistointroducefour access category (AC) queues and eight traffic stream (TS) queues at MAC layer. An-other main feature of the HCF is the concept of transmission opportunity (TXOP), the timeinterval permitted for a particular STA to transmit packets. During the TXOP, there canbe a series of frames transmitted by an STA separated by short interframe space (SIFS).EDCA is aimed at service differentiation which is achieved by using different IFS sizesand allocating different CW sizes for different ACs. HCCA improves over the Point Co-ordination Function (PCF) of legacy 802.11 MAC. Similar to PCF, HCCA is a pollingbased mechanism where the access to the medium is arbitrated centrally. However, it re-solves the limitation of PCF by eliminating the unpredictability of beacon delays arisingfrom incompatible cooperation between Contention Period (CP) and Contention Free Pe-riod (CFP) [45].18Resource Allocation Schemes for IEEE 802.11e WLANsA few research efforts have addressed the scheduler and admission controller design in thecontext of IEEE 802.11e WLANs. The scheduler design is relevant to HCCA and is notnecessary for EDCA, which itself is designed to schedule medium access for competingtraffic.Ni et al. proposed a fair scheduling algorithm named fair HCF (FHCF) in [46]. AQAP scheduler estimates the queue length for each QSTA before the next SI. Based onthese estimated queue lengths, the QAP adapts the computation of TXOPs accordingly.A node scheduler then redistribute the unused time among its different traffic streams.For EDCA, schemes proposed in [47, 48] are examples of measurement-based admis-sion control schemes. In [47], a threshold-based admission controller for EDCA has beenproposed. The QSTAs monitor the wireless link for traffic conditions and take individ-ual admission/rejection decisions based on the measured relative occupied bandwidth oraverage collision rates. Although the scheme is simple to implement, setting the properthreshold values or optimizing them is very difficult. Xiao and Li [48] have proposed amechanism, what they call global parameter control, to achieve performance protection forvideo and audio applications from data services. Measurement based schemes, however,suffer from performance oscillations. Among model based schemes for EDCA, Pong andMoors in [49] propose an admission controller for EDCA using a Markov Chain Analy-sis. In [50], Gao and Cai propose an admission control scheme called Physical-Rate-BasedAdmission Control (PRBAC) for HCCA. The idea is to consider the variance of physicalrates of the wireless channels due to background noise, pathloss, multipath effects insteadof a fixed physical rate when admitting new flows. The scheme works for CBR trafficand have the same limitations with VBR traffic as those with the reference admission con-19troller. In the admission control scheme proposed for VBR traffic in [51], the key idea isto introduce a new variable, effective TXOP (Te), to replace TXOP. Te is defined as thenecessary TXOPs which can statistically guarantee that the packet loss probability is lessthan a threshold.1.2.4 Cognitive Radio for Broadband Wireless AccessCognitive radio is a recent development which aims to achieve high spectrum efficiency–very essential for broadband wireless access, given the scarcity and high cost of availableradio spectrum. Massive underutilization of radio spectrum is well documented under tra-ditional static spectrum allocation policy [52, 53] and is a major hurdle in achieving wide-spread deployment of broadband wireless access. Cognitive radio shifts the spectrum allo-cation paradigm from static to dynamic by allowing unlicensed secondary users (SUs) toopportunistically access frequency bands originally licensed to some primary users (PUs).A CR network is thus formed by a number of SUs that use sophisticated spectrum sensingand dynamic access techniques to utilize resource holes from PU networks. Research inter-est in CR technology has grown tremendously off late and a reasonable number of ensuingresearch efforts have dealt with resource allocation issues and performance analysis of CRsystems.Opportunistic Spectrum Access and Performance ModelingIn a CR network, the availability of radio spectrum for CR users depends mainly on theactivity of primary users. On the other hand, since wireless channel quality of CR users istime-varying in nature, communication resource available to CR users is highly dynamic.How the secondary users can access the opportunistically available spectrum most effec-tively in such dynamic scenarios with minimal interference to the primary users is a chal-20lenging problem. The access schemes not only have implications for interference to pri-mary users, but also can drastically affect the QoS experienced by applications runningat the secondary user ends. The primary users have the preemptive right to reoccupy thespectrum opportunistically accessed by secondary users and therefore, can reoccupy thechannels accessed by secondary user anytime; such preemptions would mean potentialthroughput degradation, increased packet loss and connection dropping. The opportunisticspectrum access in CR networks, therefore, demands careful design considerations and hasreceived considerable attention from wireless communications researchers. For a detailedsurevey on the spectrum access solutions for CR networks, we refer to [54]. Since MAClayer controls access to the available spectrum, designing MAC schemes adapted for op-portunistic spectrum access has also been investigated in CR literature. A number of MACprotocols for CR networks have been proposed in literature. An in-depth survey of theMAC schemes for CR networks can be found in [55].Besidesspectrumaccessschemesdesign,performancemodelingofCRnetworksisalsoa very active area of research. In most of the cases, however, the focus of the performanceanalysis has been on the capacity, throughput and/or outage probability achievable at thephysical layer (PHY). In [56], Devroye et al. presented an information theoretic analysisto derive the capacity regions of a cognitive radio channel. Information theoretic limit ofthroughput in cognitive networks was also analyzed in [57] and [58] assuming differentcooperative behaviors between primary and CR users. Game theoretic models have alsobeen used to analyze CR networks. Ji and Liu provided a review of theses game theoreticmodels in [59]. These models are useful to analyze achievable payoffs and associatedfairness of service among CR users resulting from different spectrum sharing policies inCR networks.21For CR networks, cross-layer performance modeling is especially important becauseof networking functionalities in these networks directly depend on the properties of thespectrum band in use and the activity of primary users in those bands. The MAC layerprotocols in a CR network should be able to adapt to this very dynamic availability of thecommunication resources. An adaptive MAC layer, which efficiently uses communicationresources given the QoS requirements, is an important component for an adaptive wire-less access system based on CR technology. Among the notable research works done onsuch cross-layer modeling, Simeone et al. [60] studied MAC layer throughput for a CRuser over a cognitive link given a certain throughput at the primary user end. The systemmodel, however, is very simplistic with a single CR user opportunistically sharing the cog-nitive link with a single primary user. The queueing model assumes infinite transmissionqueues and does not study delay or packet loss performance measures. In [61], an M/G/1queueing model was used to analyze the transmission performance of multiple CR users onan aggregate basis considering both PHY and MAC layer parameters. Analytical modelswere developed in [62] for cognitive MAC protocols with dedicated control channel andwith embedded control channel. Call-level QoS performance (e.g., blocking performance)for CR users was analyzed in [63] based on a G/M/N queueing model. In a similar spirit,call-level performances for both primary users and CR users were analyzed in [64] using atwo-dimensional Markov chain. A cross-layer design methodology for CR networks basedon fuzzy logic was presented in [65].1.3 Thesis OutlineIn chapter 2, we address the resource allocation problem in the downlink of a mobileWiMAX system and propose a novel mode-based resource allocation framework to meet22QoS guarantees for both real-time and non-real-time applications. At first, we developa queueing model to link important performance measures of downlink service flows toa set of tunable parameters. We show how these parameters could be set to appropriatevalues to meet the QoS performances sought by the admitted service flows. We then intro-duce a resource allocation scheme that uses these parameter values for scheduling packetsamong these service flows. Inside the proposed queue- and channel-aware scheme, thequeue-length-based packet scheduler is complemented by a cross-layer OFDMA slot al-location mechanism that adapts to channel conditions at the destination mobile stations(MSs). Compared to existing schemes, our model-based approach offers a simple yet moreeffective way to provide QoS to a heterogenous mix of applications. It also offers greaterflexibility to service providers by allowing probabilistic delay guarantees to time-criticalmultimedia applications. Besides, unlike many existing schemes, our proposed solutionis designed to be compatible with the updated definition of some key resource allocationconcepts in IEEE 802.16e. The cross-layer aspect of the scheme ensures efficient resourceutilization in presence of link adaptations due to mobility and channel fading. We alsopresent our simulation results to show performance benefits of the proposed scheme in pro-viding QoS support for both real-time and non-real-time applications in mobile WiMAXsystems.In chapter 3, we develop a queuing analytic model for cross-layer analysis of a down-link resource allocation scheme that exploits multiuser diversity in a V-BLAST MIMO-based cellular broadband system. The queuing model is developed considering the systemdynamics resulting from the prominent resource allocation scheme, fading in the MIMOchannel, and the traffic arrival process. The transmit antenna correlation in the base stationand the possibility of bursty traffic arrival are also factored into the model. The queuing23model is then shown to have important applications in the QoS provisioning frameworkfor a V-BLAST MIMO system as the model output can be used in admission control, QoSnegotiation and setting proper values for QoS relevant parameters.In chapter 4, we formulate an analytical model of the controlled channel access mech-anism, also called HCCA, of 802.11e based WLANs considering VBR traffic applications.The model enables us to derive important performance measures in terms of the parametersusedinthereferenceschedulerandadmissioncontroller. Italsoshowstheunderlyingcauseof the critical weakness of the reference scheduler in providing QoS for VBR applications.Using the insights gained from the model, we then develop a novel channel access sched-uler for IEEE 802.11e WLANs. By simulation analysis, we then show that the proposedscheme, referred as PRO-HCCA scheduler, achieves very robust and stable performance inmeeting the QoS guarantees for different type of VBR traffic applicationsIn chapter 5, we develop a queueing analytical model to study the performance of op-portunistic spectrum access by CR users in a dynamic spectrum access network. For re-source allocation, a channel-quality-based opportunistic scheduling scheme is considered.In formulating the analytical model, we performed stochastic modeling of primary users’activity and CR users’ channel quality variation over time. The proposed model is shownto have important applications including cross-layer analysis and design for system engi-neering, and model-based admission control in CR based broadband systems.In chapter 6, we summarize our contributions, conclude the thesis and highlight poten-tial future research directions.241.4 Bibliography[1] IEEE 802.11, “Part 11: Wireless LAN Medium Access Control (MAC) and PhysicalLayer (PHY) Specifications,” Aug. 1999.[2] IEEE 802.16-2001, “IEEE Standard for Local and Metropolitan Area Networks – Part16: Air Interface for Fixed Broadband Wireless Access Systems,” Apr. 2002.[3] J. Mitola and G. Q. Maguire,“Cognitive radio: Making Software Radios More Per-sonal,” IEEE Personal Communications, vol. 6, no. 4, pp. 13-18, Aug. 1999.[4] http://www.ieee802.org/22/, retrieved Dec. 2009.[5] IEEE 802.16-2004, “IEEE standard for Local and Metropolitan Area Networks – Part16: Air Interface for Fixed Broadband Wireless Access Systems,” Oct. 2004.[6] IEEE 802.16e-2005, “IEEE Standard for Local and Metropolitan Networks – Part 16:Air Interface for Fixed and Mobile Broadband Wireless Access Systems, Amendment2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Op-eration in Licensed Bands and Corrigendum 1,” Feb. 2006.[7] K. Wongthavarawat and A. Ganz, “Packet Scheduling for QoS Support in IEEE 802.16Broadband Wireless Access Systems,” International Journal of Communication Sys-tems, vol. 16, no. 1, pp. 81-96, Feb. 2003.[8] H. Wang and L. Dittmann, “Adaptive Radio Resource Allocation in Hierarchical QoSScheduling for IEEE 802.16 Systems,” Proc. IEEE Global Telecommunications Con-ference, pp. 4769-4774, Washington, D.C., Nov. 2007.25[9] Q. Liu, X. Wang, and G. B. Giannakis, “A Cross-Layer Scheduling Algorithm withQoS Support in Wireless Networks,” IEEE Transactions on Vehicular Technology,vol. 55, no. 3, pp. 839-847, May 2006.[10] D. Niyato and E. Hossain, “A Queuing-Theoretic and Optimization-Based Model forRadio Resource Management in IEEE 802.16 Broadband Wireless Networks,” IEEETransactions on Computers, vol. 55, no. 11, pp. 1473-1488, Nov. 2006.[11] C-L. Chen, J-W. Lee, C.-Y. Wu, and Y.-H. Kuo, “Fairness and QoS Guarantees ofWiMAX OFDMA Scheduling with Fuzzy Controls,” EURASIP Journal on WirelessCommunications and Networking, vol. 2009, Article ID 512507, 14 pages, Jan. 2009.[12] A. Biagioni, R. Fantacci, D. Marabissi, and D. Tarchi, “Adaptive Subcarrier Alloca-tion Schemes for Wireless OFDMA Systems in Wimax Networks,” IEEE Journal onSelected Areas in Communications, vol. 27, no. 2, pp. 217-225, Feb. 2009.[13] G. Miao and N. Himayat, “Low Complexity Utility Based Resource Allocation for802.16 OFDMA Systems,” Proc. IEEE Wireless Communications and NetworkingConference, pp. 1465-1470, Las Vegas, NV, Mar.-Apr. 2008.[14] V. Singh and V. Sharma, “Efficient and Fair Scheduling of Uplink and Downlink inIEEE 802.16 OFDMA Networks,” Proc. IEEE Wireless Communication and Network-ing Conference, vol. 2, pp. 984-990, Las Vegas, NV, Apr. 2006.[15] C. Tarhini and T. Chahed, “AMC-Aware QoS Proposal for OFDMA-Based IEEE802.16 WiMAX Systems,” Proc. IEEE Global Telecommunications Conference,pp. 4780-4784, Washington, D.C., Nov. 2007.26[16] T.A. Yahiya, A.-L. Beylot, and G. Pujolle, “Cross-Layer Multiservice Schedulingfor Mobile WiMAX Systems,” Proc. IEEE Wireless Communications and NetworkingConference, pp. 1531-1535, Las Vegas, NV, Mar.-Apr. 2008.[17] M.Mehrjoo, X.Shen, andK.S.Naik, “AJointChannelandQueue-AwareSchedulingfor IEEE 802.16 Wireless Metropolitan Area Networks,” Proc. IEEE Wireless Commu-nications and Networking Conference, Hong Kong, pp. 1549-1553, Mar. 2007.[18] N.A. Ali, M. Hayajneh, and H. Hassanein, “Cross Layer Scheduling Algorithm forIEEE 802.16,” Proc. IEEE International Conference on Communications, pp. 3858-3862, Beijing, China, May 2008.[19] L. Wan, W. Ma and Z. Guo, “A Cross-Layer Packet Scheduling and Subchannel Al-location Scheme in 802.16e OFDMA System,” Proc. IEEE Wireless Communicationsand Networking Conference, pp. 1865-1870, Hong Kong, Mar. 2007.[20] D. Gesbert, M. Kountouris, R. W. Heath, Jr., C.-B. Chae, and T. Salzer, “Shiftingthe MIMO Paradigm: From Single User to Multiuser Communications,” IEEE SignalProcessing Magazine, vol. 24, no. 5, pp. 36-46, Oct. 2007[21] A. El Gamal and T.M. Cover, “Multiple user information theory,” Proc. IEEE, vol.68, no. 12, pp. 1466–1483, Dec. 1980.[22] B. Hochwald, T. Marzetta, and V. Tarokh, “Multi-Antenna Channel Hardening andItsImplicationsforRateFeedbackAndscheduling,” IEEE Transactions on InformationTheory, vol. 50, no. 9, pp. 18931909, Sept. 2004.[23] M. Costa, “Writing on Dirty Paper,” IEEE Transactions on Information Theory, vol.29, no. 3, pp. 439441, 1983.27[24] Q. H. Spencer and A. L. Swindlehurst, “A Hybrid Approach to Spatial Multiplexingin Multiuser MIMO Downlinks,” EURASIP Journal on Wireless Communications andNetworking, vol. 2004, no. 2, pp. 236247, Dec. 2004.[25] G. D. Golden, G. J. Foschini, R. A. Valenzuela, and P. W. Wolniansky, “DetectionAlgorithm and Initial Laboratory Results using the V-BLAST Space-Time Communi-cation Architecture,” Electronics Letters, vol. 35, no. 1, pp. 14–15, 1999.[26] G. J. Foschini, G. D. Golden, P. W. Wolniansky, and R. A. Valenzuela, “Simpli-fied Processing for Wireless Communication at High Spectral Efficiency EmployingMulti-Element Arrays,” IEEE Journal on Seleced Areas in Communications, vol. 17,no. 11,pp. 1841–1852, 1999.[27] C.–J. Chen and L.–C. Wang, “Performance Analysis of Scheduling in MultiuserMIMO Systems with Zero-Forcing Receivers,” IEEE Journal on Selected Areas inCommunications, vol. 25, no. 7, pp. 1435–1445, Sept. 2007.[28] D. P. Palomar, M. A. Lagunas, and J. M. Cioffi, “Optimum Linear Joint Transmit-Receive Processing for MIMO Channels with QoS Constraints,” IEEE Transactionson Signal Processing, vol. 52, no. 5, pp. 1179–1197, 2004.[29] D. P. Palomar and M. A. Lagunas, “Joint Transmit-Receive Space-Time Equalizationin Spatially Correlated MIMO Channels: A Beamforming Approach,” IEEE Journalon Selected Areas in Communications, vol. 21, no. 5, pp. 730-743, 2003.[30] J.Chung, C.S.Hwang, K. Kim, andY.K.Kim, “ARandomBeamformingTechniquein MIMO Systems Exploiting Multiuser Diversity,” IEEE Journal on Selected Areas inCommunications, vol. 21, pp. 848–855, Jun. 2003.28[31] R. W. Heath, Jr., M. Airy, and A. J. Paulraj, “Multiuser diversity for MIMO wirelesssystems with linear receivers,” in Proc. Asilomar Conference on Signals, Systems andComputers, Pacific Grove, CA, Oct. 2001.[32] D. Tse and P. Viswanath, Fundamentals of Wireless Communication, Cambridge Uni-versity Press, New York, 2005.[33] R. Zhang, “Scheduling for Maximum Capacity in SDMA/TDMA Networks,” Proc.IEEE International Conference on Acoustics, Speech, Signal Processing, vol. 3, pp.2141–2144, Orlando, FL, USA, May 2002.[34] S. Serbetli and A. Yener, “Time Slotted Multiuser MIMO Systems: Beamforming andScheduling Strategies,” EURASIP Journal on Wireless Communications and Networks,Special Issue on Multiuser MIMO Networks, pp. 286-296, Dec. 2004.[35] H. Yin and H. Liu, “Performance of Space-Division Multiple Access (SDMA) WithScheduling,” IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 611–618, Oct. 2003.[36] W. Ajib and D. Haccoun, “An Overview Of Scheduling Algorithms in MIMO-BasedFourth-Generation Wireless Systems,” IEEE Network, vol. 19, no. 5, pp. 43–48, Sept.–Oct. 2005[37] M.Airy, S.Shakkottai, andR.W.Heath, Jr., “Limitingqueuingmodelsforschedulingin multi-user mimo wireless systems,” in Proc. IASTED Conference on Communica-tions, Internet & Information Technology, Scottsdale, USA, Nov. 2003.29[38] C.-J. Chen, and L.-C. Wang, “A Unified Capacity Analysis for Wireless SystemsWith Joint Multiuser Scheduling and Antenna Diversity in Nakagami Fading Chan-nels,” IEEE Transactions on Communications, vol. 54, no. 3, pp. 469–478, Mar. 2006[39] C. K. Sung, S. H. Moon, J. Choe-i, and I. Lee, “Performance Analysis of MultiuserMIMO Systems with Zero Forcing Receivers,” Proc. IEEE Vehicular Technology Con-ference, Dublin, Ireland, Apr. 2007[40] C. Pietsch, S. Sand, W. G. Teich, J. Lindner, “Modeling and Performance EvaluationOf Multiuser MIMO Systems Using Real-Valued Matrices,” IEEE Journal on SelectedAreas in Communications, vol. 21, no. 5, pp. 744–753, Jun. 2003[41] X. Zhang; Z. Lv, and W. Wang, “Performance Analysis of Multiuser Diversity inMIMO Systems with Antenna Selection,” IEEE Transactions on Wireless Communi-cations, vol. 7, no. 1, pp. 15–21, Jan. 2008[42] M. Torabi, W. Ajib, and D. Haccoun, “Performance Analysis of Multiuser MIMOSystems with Scheduling and Antenna Selection,” Proc. IEEE Vehicular TechnologyConference, Singapore, May 2008.[43] G. Dimic and N. D. Sidiropoulos, “On Downlink Beamforming With Greedy UserSelection: Performance Analysis and A Simple New Algorithm,” IEEE Transactionson Signal Processing, vol. 53, no. 10, pp. 3857–3868, Oct. 2005.[44] IEEE 802.11e-2005, “Part 11: Wireless LAN Medium Access Control (MAC) andPhysical Layer (PHY) Specifications Amendment 8: Medium Access Control (MAC)Quality of Service Enhancements,” Nov. 2005.30[45] Q. Ni, L. Romdhani, and T. Turletti, “Survey of QoS enhancements for IEEE 802.11wireless LAN,” Wiley Journal of Wireless Communications and Mobile Computing,vol. 4, no. 5, pp. 547-566, 2004.[46] P. Ansel, Q. Ni, and T. Turletti, “FHCF: A Simple and Efficient Scheduling Schemefor IEEE 802.11e,” Springer/Kluwer Journal on Mobile Networks and Applications,vol. 11, no. 3, pp. 391–403, 2006.[47] D. Gu and J. Zhang, “A New Measurement-Based Admission Control Method forIEEE802.11WirelessLocalAreaNetworks,” Proc.IEEEPersonal, IndoorandMobileRadio Communications Symposium, Beijing, China,Sept. 2003.[48] Y. Xiao and H. Li, “Voice and Video Transmissions With Global Data Parameter Con-trolforTheIEEE802.11eEnhanceDistributedChannelAccess,”IEEETransactionsonParallel and Distributed Systems, vol. 15, no. 11, pp. 1041–1053, Nov. 2004.[49] D. Pong and T. Moors, “Call Admission Control for IEEE 802.11 Contention AccessMechanism,” Proc. IEEE Global Communications Conference, San Francisco, CA,Dec. 2003.[50] D. Gao and J. Cai, “Admission Control With Physical Rate Measurement for IEEE802.11e Controlled Channel Access,” IEEE Communications Letters, vol. 9, no. 8, pp.694–696, Aug. 2005.[51] W.F. Fan, D.Y. Gao, D.H.K. Tsang, and B. Bensaou, “Admission Control for VariableBit Rate Traffic in IEEE 802.11e WLANs,” Proc. IEEE LANMAN’04, Apr. 2004.[52] Federal Communications Commission, “Spectrum Policy Task Force,” Rep. ETDocket no. 02-135, Nov. 2002.31[53] R. W. Broderson, A. Wolisz, D. Cabric, S. M. Mishra, and D. Willkomm, “CORVUS:A cognitive radio approach for usage of virtual unlicensed spectrum,” white papersubmitted at the University of Berkeley, CA, Jul. 2004.[54] I. F. Akyildiz, Won-Yeol Lee, M. C. Vuran, and S. Mohanty, “A Survey on SpectrumManagement in Cognitive Radio Networks,” IEEE Communications Magazine, Vol.46, Issue 4, pp. 40–48, Apr. 2008.[55] D. Niyato and E. Hossain, “Medium Access Control Protocols for Dynamic SpectrumAccess in Cognitive Radio Networks: A Survey,” invited chapter in Cognitive RadioNetworks, (Eds. Y. Xiao and F. Hu), Auerbach Publications, CRC Press, 2008.[56] N. Devroye, P. Mitran and V. Tarokh, “Achievable Rates in Cognitive Radio,” IEEETransactions on Information Theory, vol. 52, no. 5, pp. 1813–1827, May 2006.[57] S. A. Jafar and S. Srinivasa, “Capacity Limits Of Cognitive Radio With Distributedand Dynamic Spectral Activity,” IEEE Journal on Selected Areas in Communications,vol. 25, no. 3, pp. 529–537, Apr. 2007.[58] S. Srinivasa and S. A. Jafar, “The Throughput Potential Of Cognitive Radio: A Theo-retical Perspective,” IEEE Communications Magazine, vol. 45, pp. 73–79, May 2007.[59] Z. Ji and K. J. R. Liu, “Dynamic Spectrum Sharing: A Game Theoretical Overview,”IEEE Communications Magazine, vol. 45, no. 5, pp. 88–94, May 2007.[60] O. Simeone, Y.Bar-Ness and U. Spagnolini, “Stable Throughput of CognitiveRadioswith and Without Relaying Capability,” IEEE Transactions on Communications, vol.55, no. 12, pp. 2351–2360, Dec. 2007.32[61] S. Shankar, “Squeezing The Most out of Cognitive Radio: A Joint MAC/PHY Per-spective,” Proc. IEEE ICASSP’07, Honolulu, Hawaii, USA, Apr. 2007.[62] L.-C. Wang, Y.-C. Lu, C.-W. Wang, and D. S. L. Wei, “Latency Analysis for Dy-namic Spectrum Access in Cognitive Radio: Dedicated or Embedded Control Chan-nel?,” Proc. Personal, Indoor and Mobile Radio Communications Symposium , Athens,Greece, Sept. 2007.[63] S. Keshavamurthy and K. Chandra, “Multiplexing Analysis for Dynamic SpectrumAccess,” Proc. IEEE , Washington, DC, USA, Oct. 2006.[64] S. Tang and B. L. Mark, “Performance Analysis of a Wireless Network with Oppor-tunistic Spectrum Sharing,” Proc. IEEE Global Communications Conference, Wash-ington, DC, USA, Nov. 2007.[65] N. Baldo and M. Zorzi, “Fuzzy Logic for Cross-Layer Optimization in CognitiveRadio Networks,” IEEE Communications Magazine, vol. 46, no. 4, pp. 64-71, Apr.2008.33Chapter 2A Model-Based Downlink ResourceAllocation Scheme for IEEE 802.16eMobile WiMAX Systems12.1 IntroductionWiMAX is an emerging broadband wireless technology that holds the promise of dramat-ically expanding the reach of broadband Internet services while eliminating huge deploy-ment costs associated with last-mile wired connections to client ends. The technology,first standardized in the IEEE 802.16 standard [1], can offer broadband quality data ratenecessary to support wide range of multimedia applications and services that are currentlygenerating perhaps the major portion of traffic carried over the Internet. After its introduc-tion, the IEEE 802.16 standard has gone through several amendments and enhancements.1A version of this chapter has been submitted for publication. Rashid, M.M. and Bhargava, V.K. (2009)A Model-Based Downlink Resource Allocation Scheme for IEEE 802.16e Mobile WiMAX Systems.34The initial IEEE 802.16 standard was designed for fixed broadband services. WiMAX thenventured into the mobile broadband service though the introduction of IEEE 802.16e [2],which has introduced many advanced features to better handle user mobility. Among them,the OFDMA-based air interface offers better robustness against multipath fading experi-enced by mobile users and enables efficient resource multiplexing in a multiuser system.From its onset, the IEEE 802.16 standard came with a Quality of Service (QoS) sup-port framework. This is especially important for WiMAX systems as they are expectedto support wide range of multimedia applications such as Voice over IP (VoIP), streamingvideo, network gaming that require certain levels of QoS for their smooth operation. Be-sides, WiMAX service providers would also like to offer different levels of QoS supportto their clients according to their subscriptions. With IEEE 802.16e, the basic QoS frame-work remains intact, but new resource allocation issues have emerged with OFDMA at theair interface and for the need to support QoS in presence of user mobility. The standard,however, only defines the QoS infrastructure and the basic signaling mechanisms to sup-port QoS, but leaves open the designs of necessary resource management functionalitiessuch as packet scheduling, OFDMA resource allocation and admission control. The IEEE802.16e standard also adds a number of amendments to the specifications of QoS classesand their associated scheduling services, especially for downlink transmissions.In this chapter, we focus on a resource allocation framework that comprises of packetscheduling and OFDMA resource allocation with the goal of QoS provisioning in IEEE802.16e systems. We design the framework to deal with various types of QoS-constrainedmultimedia and data applications. Most of these applications generate variable-bit-rate(VBR) traffic and require their diverse QoS requirements to be met in presence of othercompeting VBR as well as constant-bit-rate (CBR) applications. Due to their dynamic traf-35fic characteristics, VBR applications are more challenging to provide QoS for than theirCBR counterpart. Hence, we aim to provide a framework that is primarily designed forQoS support of VBR applications, but can also be configured with ease to handle CBRapplications. The QoS framework in IEEE 802.16e provides QoS on a per-service-flowbasis, where a service flow defines a unidirectional flow of packets usually generated by asingle application or service. The signaling mechanism allows to specify traffic parametersas well as QoS requirements of individual service flows seeking admission into the system.Each admitted service flow is then assigned to a transport connection and is allocated re-source inside WiMAX frames, which are comprised of a limited number of OFDMA slots.In our proposed resource allocation framework, a joint packet scheduling and OFDMAslot allocation scheme determines how many packets have to be scheduled for each back-logged connection during a frame time and how the available OFDMA slots need to beallocated to each connection for transmitting those scheduled packets. The objective is tomeet QoS guarantees for the admitted service flows and the constraint is the limited num-ber of OFDMA slots that are available in the WiMAX frames. How many slots should beallocated in a frame to different connections also depends on the link quality of the destina-tion mobile station (MS) and the signaling overhead involved in transmitting the allocationinformation. Therefore, a cross-layer adaptive resource allocation scheme is desirable andpursued.More specifically, we propose a model-based resource allocation framework that buildson the queueing model of a simple queue-length-based packet scheduling policy. First, wedevelop the queueing model that links important performance measures of a particular ser-vice flow to the value of a model parameter associated with its connection. Each downlinkconnection transporting a QoS-constrained service flow is associated with a model param-36eter. We then propose a method that utilizes this queueing model to set appropriate valuesfor these model parameters, given the QoS requirements and arrival statistics of the ad-mitted service flows. Finally, we propose the resource allocation scheme that adopts thesemodelparametervaluesalongwiththesignalingoverheadandchannelqualityfeedbacksinscheduling packets and allocating OFDMA slots to these QoS connections in the downlink.Compared to existing WiMAX resource allocation schemes, which we overview insection 2.7, our model-based approach has several advantages. Instead of complexitiesinvolved with installing separate scheduling schemes within the same resource allocationframework for real-time and non-real-time traffic, the model-based approach offers an effi-cient unified way to handle both types of traffics and their diverse QoS requirements. Manyof the existing schemes for IEEE 802.16e continue to assume that a number of predeter-mined service classes are mandatory and aims to provide intra-class or inter-class downlinkresource allocation to provide QoS specific to those service classes. Some researchers haveproposed hierarchical designs that combine both intra- and inter-class resource allocation;the inter-class component is usually priority-based that might cause applications belong-ing to a lower- priority service class to lack enough resource to fulfil QoS requirements.Besides, the hierarchical solutions can significantly increase implementation complexityof the resource allocation module. We note that the IEEE 802.16e standard no longer hasprovisions for mandatory service classes for the downlink and offers much more flexiblespecifications of traffic and QoS parameters. Therefore, the existing solutions might be in-compatible and inefficient for IEEE 802.16e mobile WiMAX systems. We, in contrast, de-sign our proposed scheme according to the flexible interpretation of service classes in IEEE802.16e. The scheme also offers flexibility to service providers by allowing different prob-abilistic guarantees to be made for delay experienced by packets belonging to connections37serving different customer classes (e.g. platinum, gold, silver). Besides, the cross-layerdesign of the resource allocation scheme ensures robustness and efficient resource utiliza-tion in presence of user mobility and channel fading. In addition, our proposed schemeis designed to meet QoS of individual applications and is more comprehensive than someexisting resource allocation schemes that focus mainly on improving overall system per-formance of OFDMA-based WiMAX systems.The rest of the chapter is organized as follows. In section 2.2, we provide a briefoverview of IEEE 802.16e standard focusing mainly on the air interface and QoS archi-tecture. We discuss the system model and assumptions in section 2.3. We introduce aqueue-length-based scheduling policy and its queueing analytical model in section 2.4,which forms the basis of our proposed resource allocation scheme. We describe our pro-posed resource allocation scheme in section 2.5. Next, we present and discuss performanceevaluation results of our proposed scheme in section 4.5. A brief summary of related workis provided in Section 2.7. Section 6 concludes the chapter.2.2 IEEE 802.16e and Its QoS Architecture2.2.1 Overview of IEEE 802.16e Air InterfaceThe IEEE 802.16e air interface is OFDMA-based, where OFDMA symbols are allocated inthe time domain and subcarriers grouped in subchannels are alocated in the frequency do-main. Combination of certain number of symbols and subchannels constitutes an OFDMAslot. How many symbols and subchannels will be used to form an OFDMA slot dependson the subchannelization mechanism, which can be either diversity-based or contiguous.Among the subchannelization schemes, Partial Usage of Subchannels (PUSC) and Full38PREAMBLEDL-MAPDL-MAPUL-MAPDL-Subframe UL-SubframeTransmit transition gapFrequency(Logical Subchannels)Time(Symbols)AllocationIEOFDMA SlotFigure 2.1: IEEE 802.16e frame structureUsage of Subchannels (FUSC) are diversity-based and Adaptive Modulation and Coding(AMC) is contiguous subchanelization. In PUSC, which is mandatory for both downlinkand uplink, logical subchannels are formed from randomly chosen subcarriers across theOFDM spectrum. A slot is constructed using two OFDMA symbols across one subchannelin PUSC and using one symbol across two subchannels in FUSC. On the other hand, AMCforms subchannels by grouping contiguous subcarriers and offers the opportunity for utiliz-ing multiuser diversity. In general, AMC is desired for limited mobility or fixed WiMAXsystems and PUSC/FUSC is recommended for mobile WiMAX.Frame StructureThe IEEE 802.16e OFDMA air interface communication is frame-based. With OFDMA-TDD, an IEEE 802.16e frame is divided into a downlink (DL)-subframe and an uplink(UL)-subframe. The DL-subframe consists of a preamble followed by DL- and UL-MAPsrespectivelyasshowninFig.2.1. TheDL-andUL-MAPsarebroadcastMACmanagementmessages that specify the control information for all connections scheduled in the DL andUL subframes. The MAP is received and parsed by all MSs so that they can determine39the parameters associated with their allocations. The minimum unit of allocation is a slotand each MS’s allocation is assigned an integral number of slots. The number of slots orresource size needed for an MS’s allocation depends on its modulation and coding scheme(MCS) and the number of bits in the packets scheduled for transmission. The DL-andUL-MAPs are composed of smaller elements known as information elements (IEs). EachIE describes an MS’s allocation and provides information such as the MCS, resource size,location of the allocation in the frame. A separate IE is usually required for each individualallocation in the frame.2.2.2 MAC Layer and QoS FrameworkThe MAC layer of WiMAX systems is connection-oriented. For QoS management, theconcept of service flow was introduced, which defines the QoS parameters for a unidirec-tional flow of packets. A service flow is created and its QoS parameters are defined throughDynamicServiceAddition(DSA)messagesthatareexchangedbetweentheBSandtheMSassociated with the service flow. The service flow and its QoS parameters can subsequentlybe updated through Dynamic Service Change (DSC) messages. Creation of a service flowmay be initiated by an MS or the BS using a DSA-REQ message, which includes the pa-rameters for the service flow. The MS-initiated service flow requests have to go through anadmission control process. Upon admission into the system, an active service flow is asso-ciated with a transport connection–identified by a unique connection ID (CID). In essence,a transport connection serves as a context for data communications between the BS and anMS, whereas the associated service flow defines the connection’s QoS requirements. Forapplications needing bidirectional communication, two service flows and correspondingly,two transport connections are created–one for each direction. In the rest of the chapter, the40terms “service flow” and “connection” will be used interchangeably.Another concept relevant to QoS support in WiMAX systems is scheduling service,which essentially refers to the data handling mechanism associated with a connection. TheIEEE 802.16 restricted all service flows, both in downlink and uplink, to four schedulingservices: Unsolicited Grant Services (UGS), Real-time Polling Services (rtPS), Non-real-time Polling Services (nrtPS) and Best Effort (BE). Each of these scheduling services ex-cept BE has a mandatory set of QoS parameters; therefore, any service flow must declarethe scheduling service that it wants to be handled with and as such must define the QoSparameters for that scheduling service.IEEE 802.16e introduced major changes to the definition and scope of scheduling ser-vices (section 6.3.5 of IEEE 802.16e-2005 [2]). Although the underlying concept remainssimilar, association of service flows in the downlink need not confine to a mandatory listof scheduling services. The standard suggests but does not mandate a number of QoS pa-rameters that would provide scheduling service for different types of applications such asreal-time and non real-time VBR video, VoIP. In essence, incorporating a flexible interpre-tation of scheduling services, IEEE 802.16e allows scheduling services of a service flow tobedefinedbyits statedQoSparameters. Besidesthe parametersalreadydefinedin thestan-dard, these QoS parameters can also include vendor defined parameters. In the uplink, thescheduling services are renamed as scheduling types and every service flow in the uplinkneeds to define its scheduling type from a set of five predefined types: UGS, rtPS, nrtPS,Extended Real-time Polling Service (ertPS) and BE. The scheduling type determines thebandwidth request/grant mechanism for uplink connections.41Packet schedulerOFDMA slot allocatorMS2MS1WiMAX BSDownlink connection queuesMSmFigure 2.2: A simplified view of the system model2.3 System Model and Related AssumptionsWe consider a single cell in an IEEE 802.16e mobile WiMAX system operating in point-to-multipoint (PMP) mode, where a single BS communicates with a number of MSs locatedwithin a geographic area. We assume that TDD is used for multiplexing uplink and down-link connections. In this chapter, we focus on the resource allocation for admitted serviceflows in the system. Therefore, we do not propose any design for the admission controlprocess, but assume that the service flows considered in the resource allocation processhave successfully gone through such process. After being admitted, each of the serviceflows destined from the BS to an MS is assigned a downlink connection. Fig. 2.2 presentsa simplified overview of the system model in consideration. We assume that a separatequeue is maintained at the BS for each downlink connection and the packets belonging to42a downlink connection are served on an FCFS basis. The packets may arrive in variableintervals and may have variable packet size. Allocation decisions regarding the numberof packets and the necessary number of slots to communicate these packets from eachconnection are made by the BS at the beginning of each frame. The packet scheduler isresponsible for determining the number of packets to be scheduled from each downlinkconnection and can use the information from OFDMA slot allocator on available numberof OFDMA slots in the physical layer (PHY). On the other hand, the OFDMA slot alloca-tor, in coordination with the packet scheduler, determines how many slots will be allocatedto the scheduled connections and in which order the connections will be allocated the slots.The DL-MAP is then constructed to indicate which connection is assigned which slots inthe DL-subframe.WealsoassumePUSCsubchannelizationinthedownlink,thereforeforaparticularMS,all the subchannels offer similar fading dynamics. The MCS chosen by the BS to transmitto an MS depends on the channel quality information (CQI) feedback sent by the MS.A link adaptation process selects MCS levels for different MSs to maintain a target errorperformance in response to change in channel fading conditions. We assume that channelquality remains static over the length of a frame, so the MCS choice for a particular MSdoes not change within a frame time. The chosen MCS has the effect in the slot allocationschemeasitwillbeusedincalculatinghowmanyslotsneedtobeallocatedfortransmittinga certain number of packets from the BS to the MS.ComparedtoIEEE802.16oritsIEEE802.16damendment(laternamed802.16-2004[3]),theIEEE802.16estandardhasanupdatedscopeforschedulingservicesindefiningQoSre-quirement of service flows. The scheduling service of a service flow is no longer limited tofour predefined classes namely UGS, rtPS, nrtPS, and BE. IEEE 802.16 and 802.16d also43specified a mandatory list of QoS parameters for each of these four scheduling services.IEEE 802.16e does not have such mandatory lists of QoS parameters; instead, the schedul-ing service for a service flow is now defined through its specified traffic characteristics andQoS parameters. Unlike many of the related works, we conform to these updates and donot assume four mandatory scheduling services. We also assume that three important QoSmeasures can be included in the scheduling service specification for a service flow: delay,packet loss rate and throughput. The maximum latency and minimum reserved traffic rateparameters defined in the standard can be used to specify delay and throughput require-ments respectively. For delay performance, we allow tolerable delay limit to be specifiedprobabilistically. Many service providers offer a number of QoS classes (e.g. platinum,gold, silver) and corresponding pricing policies for their customers; such providers canuse probabilistic delay guarantees to differentiate the levels of service offered to customersbelonging to different QoS classes. Therefore, we assume that the delay requirement ofa service flow is specified by a maximum packet delay and a probability that the packetsbelonging to the service flow will be transmitted within this target delay. This probabilitymeasure and the packet loss rate are assumed to be specified through vendor specific QoSparameters, which the standard allows the vendors to define for QoS measures not coveredby the predefined QoS parameters in the standard.2.4 A Queue-Length-Based Packet Scheduling Policy andIts Queueing AnalysisA queue-length-based packet scheduling policy serves as the key to determining a set oftunableparametersinourproposedresourceallocationscheme. Inthissection, wedescribethe scheduling policy and its queueing model that is used to calculate these parameters for44admitted service flows. Note that the packet scheduling policy described and analyzed inthis section is not directly adopted in our proposed resource allocation scheme describedlater; rather, its queueing model is used to determine important parameters affecting thepacket scheduler’s operation in that scheme.In this packet scheduling policy, the BS evaluates the number of packets in each back-logged downlink connection queue at the beginning of a frame and decides to schedulesome fraction of the backlog at each queue in the current frame. More specifically, ifqueue-length of connection i at the beginning of frame n is denoted by q(n)i , then the num-ber of packets, w(n)i that will be scheduled for the connection in the current frame is givenbyw(n)i =⌈xiq(n)i⌉, if 0 < q(n)i ≤L0, if q(n)i = 0,(2.1)where L is the maximum limit on the queue size in number of packets and xi (0 < xi < 1)is a model parameter associated with connection i. The ceiling function in this expressionis needed to convert any fractional values for the number of packets to the nearest integerand also to make sure that each non-empty queue gets to transmit at least one packet duringeach frame so that a queue does not remain without service for an extended period of timedue to low traffic intensity.The value of xi for connection i is determined through a queueing analytical modelwhen the associated service flow is admitted and its QoS parameters are known to theBS. The following subsection is devoted to formulating the queueing analytical model thatrelates the value of xi with the QoS performance of connection i, given its traffic arrivalstatistics. If there are m admitted connections that have QoS requirements to fulfil, theanalytical model will enable us to find the values for a set of m such model parameters.45Note that, if a service flow does not put forward any QoS requirement, it will be treatedas BE traffic. Connections associated with BE traffic will be treated differently than thosewith QoS traffic and will not need association with a model parameter.2.4.1 Queueing Analytical Model for the Packet Scheduling PolicyWe develop the queueing analytical model from the perspective of the queue associatedwith a tagged downlink QoS connection. Without loss of generality, in the analysis, we canomit the CID of the tagged connection. Therefore, the model parameter for the connectionwill be denoted simply by x, and other parameters specific to the tagged connection willbe used without any index referring to the CID. In developing the model, we considerthe packet arrival process of the service flow associated with the connection and assume agiven value for parameter x. The idea is to map the dynamics of this downlink queue toa discrete-time Markov chain (DTMC) and then solve the Markov chain for performancemeasures. The output of the queueing model will be the values for a set of performancemeasures given a particular value of x.Packet Arrival ProcessWe model the packet arrival process to the downlink queue by a Markov Modulated Pois-son process (MMPP), where the rate of arrivals varies depending on the current state of afinite-state Markov chain. MMPP has been extensively used by many researchers to modelwide range of multimedia and IP traffic because of its ability to effectively model importantproperties of these traffic applications [4]. For example, it can closely match the observedautocovariance function and the marginal distribution associated with the packet arrivalprocess. Besides, it offers excellent modeling for long-range dependence, burstiness andself-similar behavior observed in multimedia traffic [5]. Along with these desirable prop-46erties, it offers analytical tractability in modeling complex system dynamics.In this chapter, we resort to a discrete-time analysis and therefore, we use a discrete-time equivalent of the MMPP arrival process, also known as d-MMPP. In general, aN-stated-MMPP is described by the transition probability matrix of a N-state Markov chain and adiagonal matrix containing the arrival rates associated with the various states of the Markovchain [6]:S =1−∑i̸=1s1i s12 ... s1Ns21 1−∑i̸=2s2i ··· s2N... ... ... ...sN1 sN2 ··· 1− ∑i̸=NsNi, δ = diag(r1,r2,···,rN).Now, assuming that the maximum number of packets that can arrive during a singletime slot is M, we can form M transition probability matrices:U(h) = β(h)S, where 0≤h≤M, β(h) = diag(e−r1rh1/h!,e−r2rh2/h!,···,e−rNrhN/h!).Here, matrix U(h) corresponds to state transitions that happen after a batch of h packetsarrives during a time slot. The value of M is chosen such thatmax1≤l≤N∞∑i=M+1e−rlril/i! < ϵ, (2.2)where the value of ϵ is chosen to be very small to limit modeling error.Assuming that matrix S is time-independent, the steady state probability vector ψ of47the arrival process can be found fromψ =ψS; ψ1 = 1, (2.3)where 1 is a column matrix of ones with appropriate dimension The mean packet arrivalrate λ can be found fromλ =ψδ1. (2.4)Although the MMPP arrival process is typically used to model VBR multimedia applica-tions, modeling CBR traffic with MMPP is also possible by appropriate selection of statespace and transition probability matrix. For example, a CBR application that periodicallygenerates a packet after every t time slots can be modeled by U = 0(t−1)×1 It−11 01×(t−1),β(0) = diag(11×(t−1),0) and β(1) = diag(01×(t−1),1). Here, 0(t−1)×1 and 01×(t−1) are col-umn and row vectors of zeros respectively with dimension t−1. Similarly, 11×(t−1) is arow vector of ones with dimension t−1 and It−1 is an identity matrix of dimension t−1.Also, VoIP applications with silence suppression are often modeled by an Interrupted Pois-son Process (IPP), which is essentially a 2-state MMPP characterized by an arrival rate of0 associated with one of the states.Markov Chain AnalysisFor this discrete-time analysis, we assume that the time slot is equal to the frame durationof the IEEE 802.16e WiMAX system. Note that a time slot in the context of the discrete-time queueing model in this analysis is different from an OFDMA slot in the WiMAXframe. To avoid further confusion, from hereon we will use the term frame to mean boththe WiMAX frame and the time slot of the discrete-time queueing model. We proceed by48defining a process with state spaceX(n) ,{(q(n),a(n))|0≤q(n)≤L;a(n) = 1,2,···,N},where q(n) is the number of packets in the queue and a(n) is the state of the arrival processat the beginning of frame n. Assuming the transition among the states occur at frameboundaries and as the state variables assume discrete values only, it can be proven that theprocess X(n) is a DTMC. We write the transition probability matrix P of the DTMC in thefollowing form:P =A0→0 A0→1 ··· A0→LA1→0 A1→1 ··· A1→L... ... ··· ...AL→0 AL→1 ··· AL→L.Here, block submatrices Ak→l (0 ≤ k ≤ L,0 ≤ l ≤ L) denote transition probabilitiesassociated with the events when queue length of the connection changes from k in frame nto l in frame n + 1. These block submatrices can be derived as follows:A0→l =U(l), 0≤l≤M0, M < l≤L(2.5)Ak→l =U(l−k+⌈kx⌉), if l≤M + k−⌈kx⌉0, otherwisefor 0 < k < l < L(2.6)Ak→l =U(l−k+⌈kx⌉), if k−⌈kx⌉≤l≤min(M + k−⌈kx⌉,k−1)0, otherwisefor 0 < l < k < L(2.7)49Ak→L =M∑h=L−k+⌈kx⌉U(h), if k≥L−M +⌈kx⌉0, otherwisefor 1 < k < L(2.8)Ak→k =U(⌈kx⌉), if ⌈kx⌉≤M0, if ⌈kx⌉> Mfor 1 < k < L(2.9)AL→L =M∑h=⌈Lx⌉U(h), if ⌈Lx⌉≤M0, if ⌈Lx⌉> M,(2.10)where0denotes a zero matrix with appropriate dimensions.Once the block submatrices are derived, we can find the steady state probability vectorπ for the Markov chain by solving the set of linear equations given byπ =πP; π1 = 1.By reblocking the entries inπ according to the associated queue lengths, we can write thesteady state probability vector as π , [π0,π1,π2,···,πL], where πh stands for steadystate vector associated with a queue length of h (0≤h≤L).Derivation of Performance MeasuresIn this subsection, we will derive a number of performance measures using the steady stateprobability vector achieved from the Markov chain analysis. These measures include delay,packet loss rate and throughput—three important performance measures that often consti-tute the QoSrequirements of most multimedia and data intensiveapplications. In analyzingthe delay performance, many researchers limit their analysis to computing average delayonly. In contrast, we derive delay distribution because it offers a more meaningful perfor-50mance measure, especially for delay-sensitive multimedia applications. Individual packetsbelonging to these applications need to be delivered within a delay limit to maintain QoS;computing the average delay of these packets is, therefore, not very useful. The delay dis-tribution of these packets, on the other hand, provides adequate information to determinehow well the packets are served within the delay limit.Delay Distribution We use an absorbing Markov chain to find the delay distribution for apacket in the tagged queue. In order to construct the state space of this Markov chain, wetag an arbitrary packet in the queue and consider the number of packets that are in front ofit waiting to be served and the number of packets waiting behind it in the queue. The chaininitializes from one of the possible states corresponding to the tagged packet’s arrival atthe corresponding queue and gets absorbed when the tagged packet reaches the top of thequeue regardless of the number of packets waiting behind it. Let the state space Θ of thisMarkov chain be defined as follows:Θ ,{(u,v,w)|0≤u≤L−1;0≤v≤L−u−1;1≤w≤N},where u and v are the number of packets waiting in front and behind the tagged packet re-spectively and w is the MMPP state of the arrival process. Absorption of the chain occurswhenever any of the states in{(0,v,w)|0≤v ≤L−1;1≤w ≤N}is reached. Let usdenote the transition probability matrix of the absorbing Markov chain by Q and reblock itwith block submatricesB(i1,j1)→(i2,j2) that contain transition probabilities from states rep-resenting i1 (0≤i1≤L−1) packets in front and j1 (0≤j1≤L−i1−1) packets behindto states representing i2 (0≤i2 ≤L−1) packets in front and j2 (0≤j2 ≤L−i2−1)packets behind the tagged packet. We now find these block submatrices of the absorbing51chain as follows:B(0,j1)→(i2,j2) =I, if j1 = j2,i2 = 00, otherwisefor 0≤j1≤L−1,0≤i2≤L−1,0≤j2≤L−i2−1(2.11)B(i1,j1)→(i2,j2) =U(j2−j1), if i2 = i1−⌈(i1 + j1 + 1)x⌉,j2≤j1 + M0, otherwisefor 1≤i1≤L−1,0≤i2≤L−1,0≤j1≤L−i1−1,0≤j2 < L−i2−1(2.12)B(i1,j1)→(i2,L−i2−1) =M∑h=L−i2−j1−1U(h), if i2 = i1−⌈(i1 + j1 + 1)x⌉,j1≥L−M−i2−10, otherwisefor 1≤i1≤L−1,0≤i2≤L−1,0≤j1≤L−i1−1(2.13)where I and 0 denote identity matrix and zero matrix respectively of appropriate dimen-sions.We then determine the initial probability vector for this absorbing Markov chain as thenext step for finding the delay distribution. To this end, we first consider the probabilityvector associated with the number of packets in front and behind as seen by an arrivingpacket. Note that, the arriving packet might see packets behind because packet arrival mayoccur in bursts in a given frame and the arriving packet can be at any of the positions inthat burst. Let us denote the probability vector byξ(0). By reblocking the vector in termsof packets seen in front by the arriving packet, we can write it in an expanded form asξ(0) ,[ξ(0)0 ,ξ(0)1 ,···,ξ(0)L+M−1], where,ξ(0)i (0≤i≤L+M−1) is the probability vectorassociated with i packets in front as seen by the arriving packet. We can further reblock52the probability vectorξ(0)i asξ(0)i ,[ξ(0)(i,0),···,ξ(0)(i,min(M−1,L+M−i−1))]on the basis of thenumber of packets behind the arriving packet that sees i packets in front of itself. Theseprobability vectors can be derived as follows:ξ(0)(i,j) =1(1−α0)(j+1)π0 +∑y:1≤y≤L,y=⌈yx⌉πyU(j+1),i = 0,0≤j≤M−111−α0min(M−j−1,i)∑h=01j+h+1∑y:i−h<y≤L,y−⌈yx⌉=i−hπyU(j+h+1), 1≤i≤L,0≤j≤M−111−α0M−j−1∑h=i−L+11j+h+1∑y:i−h<y≤L,y−⌈yx⌉=i−hπyU(j+h+1),L + 1≤i≤L + M−1,0≤j≤L + M−i−1,(2.14)where α0 denotes the probability associated with no packet arrivals during a frame and canbe derived from α0 =ψβ(0)1.Note that the packets which find their destination queues full upon arrival are not admit-ted into the system. The probability po that a buffer overflow event will occur upon arrivalof a packet can be found from:po =M−1∑i=0ξ(0)L+i1+M−1∑i=1M−1∑j=iξ(0)(L−i,j)1. (2.15)Since we consider the delay experienced by the admitted packets only, the initial proba-bilityvectorω(0) ,[ω(0)(0,0),···ω(0)(0,L−1),···,ω(0)(i,j)···,ω(0)(L−1,0)]oftheabsorbingMarkov53chain is derived from the above probability vector as follows:ω(0)(i,j) =ξ(0)(i;j)1−po, if 0≤j≤min(M−1,L−i−1)0, otherwisefor 0≤i≤L−1,0≤j≤L−i−1,(2.16)which is due to the fact that packets that cannot enter the queue due to overflow are notconsidered in the state space of the absorbing Markov chain. After d frames, the stateprobability vector of the absorbing chain can be written asω(d) =ω(0)Qd, (2.17)where Qd is derived by multiplying the transition probability matrix Q of the absorbingMarkov chain with itself d times. The cumulative distribution function (CDF) of packetdelayDin frame times, not including the arrival frame, is given by:FD(d) = Pr(D≤d) =L−1∑j=0ω(d)(0,j)1. (2.18)Packet Loss Rate and Average Throughput A packet loss occurs at the downlink queuewhen a packet finds the queue full upon arrival. The packet loss rate, ploss at the queue canbe written asploss =M−1∑i=0ξ(0)L+i1. (2.19)Note that packets lost at the receiver side due to reception errors are not considered in theabove expression. Assuming no error recovery protocol is used, the average throughput η54in packets per frame time can then be calculated as:η = λ(1−ploss)(1−PER), (2.20)where PER is the average packet error rate.Queue Length Distribution and Average Delay The marginal probability distribution ofqueue lengthLcan be written as:fL(l) = Pr(L= l) =πl1,1≤l≤L. (2.21)Subsequently, the average queue length ¯Land average delay ¯Dcan be found as¯L=L∑l=1lπl1, ¯D=¯Lλ, (2.22)where the calculation of average delay follows from Little’s law.2.5 Model-Based and Channel-Aware DownlinkResource AllocationIn this section, we describe our proposed resource allocation scheme that utilizes the out-put from the analytical model developed in the preceding section. When a new downlinkservice flow, represented by connection i is admitted into the system, its QoS requirementsare evaluated and the value of the model parameter xi is computed. The outline of thecomputation procedure is listed in Algorithm 1 . The range of values of xi is 0 < xi < 1,but searching over the entire range will be infeasible. Therefore, a step-size is selected and55Algorithm 1 Compute model parameter xi for connection iInput: Ti: Pkt. Arrival statistics for connection i; ∆ : Step size;Q(i)req: QoS requirementfor connection iOutput: Model parameter xi1: xi←02: repeat3: xi←xi + ∆4: Q(i)out⇐QueuingModel (xi,Ti)5: until Q(i)out meets QoS requirementsQ(i)req of connection ithe value of xi is incremented by this step size in iterations. In the simulation experiments,for example, we choose a step size of 0.05; however, vendors’ choice for its value couldbe flexible depending on the available computational resource. During each iteration, theupdated value of xi is fed into the queueing model along with the queue-length informationand the parameters of the packet arrival process. Increasing the value of model parameterxi will allow more packets to be transmitted on average from the queue associated withconnection i and hence, improve its QoS performance. The process continues until the setof performance measures, denoted byQ(i)out in Algorithm 1, calculated from the output ofthe queueing model satisfies the QoS requirement of connection i.The value of the model parameter xi is used in our resource allocation scheme to de-termine the minimum number of packets that need to be scheduled from connection i ateach frame time. However, the actual number of packets that are scheduled is determinedthrough a number of steps in the allocation procedure listed in Algorithm 2, which alsoshows how the available OFDMA slots are allocated once the number of packets to bescheduled for each admitted downlik service flows is determinedAtthebeginningofeachframe, someimportantinformationbecomeavailabletothere-source allocation module at the BS: the backlog at the queues of the downlink connections56Algorithm2Schedulepackets, allocateslotsfordownlinkconnectionsinthecurrentframe1: Nrem←# of slots in the DL-subframe−slots allocated to DL-subframe overhead;2: m ←# of downlink QoS connections; [h1,···,hm] ←CIDs of downlink QoS con-nections;3: for i←1···m do4: Khi ←0; // initialize slots allocated for each QoS connections to 05: θhi ←byte per slot with MCS selected for hi;6: Mhi ←θhi×backlog (bytes) at connection hi; //MetricMassociated with hi7: end for8: Sort QoS connections according to their M values in descending order. Let[c1,c2,···,cm] be the sorted list and [qc1,qc2,···,qcm] be the corresponding queue-lengths9: G⇐∅; // list of scheduled connections10: repeat11: for i←1···m do12: p←⌈xci×qci⌉; //#ofpacketsselectedbasedonqueue-length&modelparameterxci13: b←number of bytes in top p packets in the queue of ci;14: a←⌈ bθci⌉; // # of slots necessary to transmit p packets over connection ci15: if ci /∈Gthen16: a←a+IE overhead (slots); //IE added if not previously added for connectionci17: end if18: ifNrem≥a then19: Nrem←Nrem−a;20: if ci /∈Gthen21: G ⇐G∪{ci}; // ci added to list of scheduled connections22: end if23: qci ←qci−p; // queue length of ci updated24: Kci ←Kci + a; // update slots allocated to ci25: end if26: end for27: until (Nrem = 0)or(nonewallocationorallocationupdatehappenedinthisiteration)28: Allocate Nrem among BE connections57and the channel quality feedbacks for different subchannels at different MSs. At first, thelist of active downlink QoS connections is sorted in descending order based on a metricM.The value ofMfor a connection is calculated by multiplying the amount of backlog (inbytes) in its queue with the number of bytes that a single OFDMA slot will be able to trans-mit on the connection in the current frame. MCS selected for a connection is dependent onthe CQI and will in turn determine the number of bytes an OFDMA slot can carry for theconnection in the current frame. The metric affects the ordering of the connections whileallocating available OFDMA slots. Note that such ordering becomes important when thereare not enough OFDMA slots available to accommodate the minimum number of packets(as determined by model parameters) from all the backlogged downlink connections. Iftwo connections have the same amount of backlog, then the connection that can transmitmore bytes per slot will be given preference for the remaining slots. This cross-layer adap-tive ordering is designed to improve resource utilization as the connection with the betterchannel quality will likely need less number of slots to clear the same amount of backlog.On the other hand, we also want connections with large backlogs to have better opportunityto transmit their packets. Therefore, among two connections with the same MCS level, theconnection with larger backlog will be given preference in the ordering.The scheduler then goes over the sorted list to determine how many packets to scheduleinthecurrentframeforeachconnection. LetusassumethatconnectionwithCIDc1 istheatthetopofthesortedlist. Inthefirstiteration, itstartsbyselectingthetop⌈xc1×qc1⌉packetsfor connection c1, where qc1 is the number of backlogged packets in the connection’s queueand xc1 is the associated model parameter. The number of slots necessary to transmitthose packets is then calculated. If a new IE needs to be created in the DL-submap tocarry the allocation information, the necessary overhead is added while calculating the58number of slots required. The other factor in this calculation is the transmission rate whichcorrespondstotheselectedMCSforthedestinationMSofconnectionc1. IfthereisenoughspaceleftintheDL-subframetoaccommodatethecalculatednumberofslots,thesepacketsare marked as selected for transmission in the current frame. The amount of available spaceis also updated by deducting the number of slots selected for the connection. The nextconnection in the sorted list is then considered and the above process is applied to choosetheminimumnumberofpacketsandcorrespondingnumberofrequiredOFDMAslots. Thefirst iteration continues until all the connections in the list [c1,c2,···cm] are considered forthe above step or all the DL-subframe space is used up.After the first iteration, if more space is left in the DL-subframe and some QoS con-nections in [c1,c2,···cm] still have backlogged packets not selected yet for transmissionin the current frame, the allocation module enters into more iterations. The aim of thesesubsequent iterations is to avoid wasting any empty space in the DL-subframe. In theseiterations, the initial sorted order of connections is maintained, but the packets are selectedby considering backlog containing those packets that have not been selected in previousrounds of iterations. The process is repeated until it is determined that further iterationswill not allocate any more space to the QoS connections. The allocation module then con-siders BE connections if more space is left in the DL-subframe.The selected packets for each connection are then scheduled to transmit in the currentDL-subframe. A single IE with the allocation information is constructed in the DL-MAPfor each scheduled connection, and slots allocated to the connection are chosen to be con-tiguous.592.6 ResultsInthissection, wereportnumericalandsimulationresultsforourproposedqueueingmodeland the model-based resource allocation scheme. For the queueing model, we tag an arbi-trary downlink service flow and analyze the sensitivity of the model outputs to the modelparameter associated with its connection. From these results, we discuss how the appro-priate value of the model parameter can be chosen for the connection so that the QoSrequirement of the service flow can be met. The simulation results are then presented toshow the performance of the proposed model-based resource allocation scheme in meetingQoS requirements of both real-time and non-real-time service flows.2.6.1 Numerical ResultsTo derive the numerical results, we coded in Matlab the steps involved in the queueingmodel developed in section 2.4. For the packet arrival process, we use a 3-state MMPPmodel with the following parameters:P =0.0005 0.9751 0.02440.2438 0.7245 0.03170.1463 0.0024 0.8513; δ = diag(0.62,2.75,4.95).The maximum capacity of the downlink queue was set to 25 packets. Since numericalresults are derived for a single connection, its model parameter is referred simply by x,without any subscript.Fig. 2.3 shows the CDF of delay experienced by the packets transmitted over the taggedservice flow for various values of model parameter x. As the value of x is increased, thedelay CDF improves, albeit by different amount at different ranges of values of x. In the601 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1600.10.20.30.40.50.60.70.80.91d(frames)Pr.(packetdelay≤d) x=0.25x=0.2x=0.15x=0.1 x=0.05Figure 2.3: CDF of packet delay for various values of model parameter x0.05 0.1 0.15 0.2 0.25 0.300.050.10.150.20.250.30.35ModelparameterxPacketlossratetargetpacketlossrate=0.01Figure 2.4: Model parameter x vs. packet loss ratefigure, the improvement is quite substantial as we increase x from 0.05 to 0.1 and then to0.15. The gain then starts to level off when we increase x further. Although this trendshould remain similar in general, the exact effects are likely to vary for different rangesof values for x, depending on the packet arrival statistics. Now let us assume that thetagged service flow has been provided a probabilistic guarantee that with 95% probabilityits packets will be served within 50 ms. Assuming a frame duration of 5 ms, we can see61from the figure that x = 0.05 will not be sufficient to meet this guarantee. If we onlyconsider the values of x having an interval ∆ = 0.05, it is apparent that the delay guaranteecould be met with x = 0.1. As we will see in the next paragraph, other QoS constraints,however, might demand the value of x to be raised further.In Fig. 2.4, we show the effect of parameter x on the packet loss rate experienced by thetagged service flow. The interval ∆ associated with the values of x is again set to 0.05. Theeffect ofxon packet loss rate seems very pronounced when the value ofxis changed insidethe range 0.05 to 0.15. With x higher than 0.2, the probability of buffer overflow becomesnegligible. Now if we assume that the service flow has been guaranteed a maximum packetloss rate of 1%, this obligation clearly cannot be met with x = 0.1 or x = 0.15, whichincur a packet loss rate of 9.44% and 2.49% respectively. With x = 0.2, the packet lossrate comes down to 0.5%, which is below the allowed packet loss rate. Although x = 0.1was sufficient to meet the delay guarantee mentioned in the previous paragraph, x = 0.2 isrequired instead if this packet loss target needs to be met at the same time.2.6.2 Simulation ResultsWe have also performed extensive simulations to evaluate the performance of the proposedresourceallocationframework. Tothisend,wehavedevelopedaMATLAB-basedWiMAXSystem Level Simulator (SLS) that includes a resource allocation module implementingour proposed scheme. We have also implemented Earliest Deadline First (EDF), WeightedDeficit Round Robin (WDRR) and a hierarchical scheme in our SLS, which allows to se-lectively run these schemes to compare the performance of these schemes with that of ourproposed scheme. The EDF is a well known scheme designed for providing QoS for delay-sensitive multimedia applications in many wired and wireless systems including WiMAX.62At each scheduling instant, priority is given to packets that have earlier deadlines. WDRRisamodifiedversionofDeficitRoundRobin(DRR)[7],whichessentiallyisaO(1)approx-imation of Weighted Fair Queueing (WFQ) [8]. In [9], WFQ was proposed and evaluatedfor intra-class scheduling of throughput guaranteed nrtPS connections. However, due to theframe-based transmissions in mobile WiMAX systems, where multiple connections can bescheduledwithinaframetime, WFQdoesnotperformsignificantlybetterthanround-robinbased schemes [10]. The high complexity involved in implementing WFQ is thus no longerjustified; rather DRR becomes a better alternative due its low-complexity. DRR was alsoselected by Cicconetti et al. in [11] for downlink scheduling . The WDRR scheme pro-posed by Lakkakorpi et al. in [12] further modifies the standard DRR to allow dynamicadjustment of the quantum parameter for each connection according to the connection’schannel quality. The authors also found that, in a mobile WiMAX system, the channel-adaptive design of WDRR offers better performance over the standard DRR. We thereforecompare our proposed scheme to WDRR instead of the standard DRR.Simulation Setup and ParametersWe have simulated a single IEEE 802.16e WiMAX cell with PMP architecture, in which asingle BS communicates with multiple MSs. The MSs are assumed to be distributed uni-formlyacrossthecell. Tomodelthelinkadaptationsduetomobilityandchannelvariations,we have used the results reported in [13] from the Mobile WiMAX link-level simulationscarried out at Intel’s Wireless Standards and Technology Laboratory. The IEEE 802.16elink-level simulator assumed the following mix of mobility profiles [14] for the MSs servedby the network: 60% ITU Pedestrian B 3 Km/h, 30% ITU Vehicular A 60 km/h and 10%ITU Vehicular A 120 km/h. It also assumed a 2×2 MIMO model in the DL with two trans-63Table 2.1: System parametersParameters ValuePHY OFDMADuplexing method TDDFrame duration 5 msBandwidth 10 MHZDL:UL ratio 26:21Number of DL subchannels 30Number of DL symbols per slot 2Number of Symbols in DL-subframe 26DL subchannelization scheme PUSCNumber of antennas (TX:RX) 2:2FFT size 1024Compressed MAP enabledMAP MCS QPSK (1/2)HARQ scheme disabledQueue size limit (in packets) 50Fragmentation/packing OFFMobility model 60% ITU PB3, 30% VA30, 10% VA120Table 2.2: Modulation and coding schemes (MCS) used in the simulationLevel Bytes per slot(without SMX/with SMX MCS (without SMX/with SMX)1/- QPSK 1/12 1/-2/- QPSK 1/8 1.5/-3/- QPSK 1/4 3/-4/12 QPSK 1/2 6/125/13 QPSK 3/4 9/186/14 16-QAM 1/2 12/247/15 16-QAM 3/4 18 /368/16 64-QAM 1/2 18/369/17 64-QAM 2/3 24/4810/18 64-QAM 3/4 27/5411/19 64-QAM 5/6 30/6064mit antennas at the BS and two receive antennas at each MS. The assumed MCS levels andtheir corresponding per-slot data capacities are listed in Table 2.2. MCS levels 1, 2 and 3employ QPSK 1/2 with repetition 6, 4 and 2 respectively. MIMO mode for MCS levels4 to 11 is space-time block coding (STBC), whereas MCS levels 12 to 19 adopt spatialmultiplexing (SMX). We select the MCS level for each MS during each WiMAX frame ac-cordingtothereportedMCSdistribtioninFig. 3(for1.4kmBS-BSseparation)of[13]. Welist selected values for important simulation parameters involving the OFDMA-based airinterface in Table 2.1, other physical layer specific parameters were chosen in accordancewith [13]. We simulated 11000 WiMAX frames for each of the simulation experiments andtook average from several runs to smooth out the results.QoS Support for Non-Real-Time Service FlowsNon-real-time applications can tolerate delays, but demand a limited level of packet loss.Our first set of simulations is aimed at evaluating the effectiveness of our proposed schemein providing QoS for such applications. We use a non-real-time application modeled by thefollowing set of MMPP parameters:S = 0.975 0.0250.05 0.95, δ = diag (0.5,2.0).These MMPP parameters can be derived considering a peak rate of 2 packets/frame, min-imum rate of 0.5 packets/frame and mean rate of 1 packets/frame, which are equivalentto 747 Kbps, 187 Kbps and 373 Kbps respectively, considering the following packet sizedistribution: truncated pareto with shape paramter a =1.1, minimum packet size of 81bytes and maximum packet size of 1500 bytes. The truncated pareto distribution is often6510 15 20 25 30 35 40 45 5000.10.20.30.40.50.60.7Number of non−real−time service flowsMean packet loss rate  ProposedWDRRFigure 2.5: System-wide packet loss rate for non-real-time servicesused to model size of the packets carried by Internet data traffic. For evaluating WiMAXMAC layer performance, same parameter values as above were also used in [10] to modelpacket size distribution of non-real-time data traffic. The packet loss performance results inFig. 2.5 are obtained for a homogenous traffic scenario where each of the MSs is associatedwith a downlink service flow transporting traffic modeled by above listed parameters. Themaximum tolerated packet loss rate for each of the service flows is set to 1%. QoS for non-real-time services are also often sought in terms of required throughput and our scheme iscapable of handling such requirement too. However, we note that, for a given PER andthe offered load on a service flow, throughput and packet loss rate measures of the serviceflow can be calculated directly from each other. We, therefore, consider packet loss rateonly in our simulation analysis. The results for WDRR are also shown for comparison. Wecan clearly see that, compared to WDRR, our proposed scheme significantly improves thesystem-wide packet loss performance. The packet loss rates drawn in Fig. 2.5, however, isaveraged over all connections. Nevertheless, the results show that the proposed scheme’spro-active management of backlogs at the connection queues is very effective in reducing660.75 1 1.25 1.5 1.75 251015202530354045Arrival Intensity, ρNumberofsupportedserviceflows  ProposedWDRRFigure 2.6: Number of supported non-real-time service flows vs. their arrival intensi-tiesunwanted packet losses.In Fig. 2.6, we show the number of service flows that can be supported without violat-ing the target packet loss rate of 1% for any of the service flows. To show how differentlevels of traffic load affect the performance, we plot the capacity values against intensity ofthe packet arrival process. We use the same traffic parameters as described in the previousparagraph, except that the rate matrix is now specified as δ = ρ×diag (0.5,2.0), where ρis the intensity parameter. We vary the value of ρ by 0.25 from 0.75 to 2.0, which translatesto an average data rate of 280 Kbps to 747 Kbps. We can see that our proposed schemesignificantly outperforms WDRR in a wide range of arrival intensities. Unlike WDRR, ourproposed scheme is queue-aware and therefore, better adapts to backlog buildups at theconnection queues. Thanks to the model-based approach, our scheme also has the advan-tage of having the precise information on the minimum amount of backlog that needs tobe transmitted from each backlogged QoS connection during every frame. The proposedscheme can, therefore, make more-informed scheduling decisions and is more successful67in avoiding under-allocation of resources to the scheduled connections. These factors con-tribute positively to the performance benefit of our proposed scheme over WDRR in termsof the number of supported non-real-time service flows in the downlink.QoS Support for Real-Time Service FlowsIn the next set of simulations, we evaluate how effectively our model-based resource al-location scheme can meet QoS guarantees for real-time multimedia applications such asstreaming video, audio/video conferencing, VoIP. These delay-sensitive applications needtheir packets to be transmitted within a certain delay limit and can tolerate only a very lim-ited amount of packet losses. In our analysis, we assume a homogeneous traffic scenario,where each MS is associated with a real-time service flow characterized by identical trafficparameters. We use the following 3-state MMPP model mapped to the real traffic trace ofa VBR MPEG-4 coded live video stream:P =0.9475 0.0525 00.1042 0.0750 0.82080 0.8333 0.1667; δ = diag(0.58,1.37,4.65).The parameters associated with the three states of this MMPP model were derived bymatching the arrival and frame size statistics of I, P and B frames in the traffic trace [15].To avoid confusion, we will refer to the video frames as packets in our analysis. The aver-age bit rate of the VBR video stream is 256 Kbps. For each of these connections, packetdelay limit is set to 50 ms with 95% probability level and the maximum allowable packetloss rate is set to 1%.Fig. 2.7 compares our proposed scheme with EDF in terms of system-wide packet de-6810 15 20 25 30 35 40 45 5000.10.20.30.40.50.60.70.80.91Number of real−time service flowsSystem−wide packet delay violation probability(delay limit = 50ms)   ProposedEDFFigure 2.7: System-wide packet delay violation probability for real-time services20 25 30 35 40 45 50 55 6000.10.20.30.40.50.60.7Number of real−time service flowsMean packet loss rate  ProposedEDFFigure 2.8: System-wide packet loss rate for real-time services69lay violation probabilities with various number of service flows in the system. To find thesystem-wide delay violation probability, we compute the delay experienced by each trans-mitted packet and then determine how many of these packets have failed to transmit withinthe guaranteed delay limit. We then divide the number of packets exceeding delay limitby the total number of transmitted packets. The figure clearly shows that the delay viola-tion probability with EDF starts to rise much earlier than that with our proposed scheme.With increasing number of service flows, the limited number of slots in the DL-subframegradually raises the earliest deadline that the EDF can serve during a frame time. Afterthe number of service flows increases to a certain value, the earliest deadline the EDF canserve during a frame time crosses the maximum packet delay limit of all the backloggedconnections. This can explain the sharp rise of packet delay violation probability with EDFwhen the number of service flows in Fig. 2.7 increases beyond 27. Our proposed scheme,on the other hand, pro-actively manages the backlogs at the connection queues and is tar-geted towards meeting the packet delay guarantees in contrast to EDF’s goal of minimizingoverall packet delay in the system. It can thereby achieve a lower system-wide packet delayviolation probability for more number of service flows, as evident in Fig. 2.7. The delayviolation probability starts to rise when the number of service flows is more than 36; therate of this increase, however, declines considerably with more than 45 service flows. Notethat we consider the delay experienced by admitted packets only. Therefore, this gradualdecline means the packet loss rate is also on the rise with more than 45 service flows, asthe scheme is working to keep delay violation probability of admitted packets in check.In Fig. 2.8, we compare the packet loss performances achieved by EDF and our pro-posed scheme. Until the number of service flows in the system reaches 28, the system widepacket loss rates of both EDF and our proposed scheme remain insignificant. The packet70192 256 320 384 448 5121520253035404550Video rate (Kbps)Number of supported service flows  ProposedEDFFigure 2.9: Number of supported service flows (real-time video streams) vs. their bitratesloss rate with EDF then starts rising pretty rapidly. With our proposed scheme, on the otherhand, we can increase the number of service flows to 45 without incurring any significantpacket loss. Note that, the model parameters used in our resource allocation scheme werederived to keep packet loss rate at individual service flows within 1%. The packet lossrates drawn in Fig. 2.8, however, is averaged across all the real-time service flows in thedownlink. Nevertheless, the results show that our scheme is more effective in preventingunwanted packet losses by better controlling the backlog buildups at the connection queuesassociated with the service flows.Although the results presented in Figs. 2.7-2.8 clearly shows that our proposed schemeachieves significant improvement of both delay and packet loss performances across thesystem, we further investigate how the individual service flows are affected. Fig. 2.9 showshow many service flows can be served without violating the delay and packet loss guaran-tees for any of the service flows. We vary the bit rate of the video connection associated710 5 10 15 20 25 30 35 4005101520253035Number of real−time service flowsNumber of non−real−time service flows  ProposedHierarchicalFigure 2.10: Number of supported non-real-time and real-time service flows compet-ing simultaneouslywith each downlink service flow. To vary the bit rate, we modify the video frame sizesby multiplying them by a common factor; I,P and B frames are equally affected. For eachservice flow, the maximum packet delay is guaranteed to be 50 ms with 95% probabilitylevel and maximum allowable packet loss rate is set to 1%. We compare the performancesof the proposed scheme and the EDF. As can be seen, our proposed scheme can serve moreservice flows with the specified QoS support. The performance advantage of our schemeremains superior on a wide range of offered loads on the video connections. The resultsshowthat, withourproposedscheme,theWiMAXBScanadmitsignificantlymorenumberof MSs that are seeking service for real-time applications.QoS Support for a Heterogenous Traffic MixThe above results are indicative of the performance benefits of our proposed scheme inproviding QoS for both real-time and non-real-time services. We further our analysis toheterogeneous traffic scenarios where both real-time and non-real-time applications are72supported simultaneously in the system. To this end, we attach real-time traffic serviceflows with downlink connections to a given number of MSs and configure the rest of theMSs in the system as the receiving ends of non-real-time service flows. We attach one ser-vice flow only to each MS. We vary the number of real-time service flows in the system anddetermine how many non-real-time service flows can be supported simultaneously withoutviolating the QoS requirements of any of the real-time or non-real-time service flows. Thetraffic stream for the real-time service flows are generated from the same MMPP modelas was used in the previous set of set of simulations. The bit rate of the real-time videostream was set to 256 Kbps. For the non-real-time traffic, we adopt the 2-MMPP modelused before and set its intensity parameter ρ = 1. We compare the performance of ourproposed scheme with a hierarchical resource allocation scheme. The design of the hier-archical scheme is similar to [9], which assigned higher priority to rtPS class over nrtPSclass and proposed EDF and WFQ for the intra-class scheduling for these service classesrespectively. Accordingly, the hierarchical scheme implemented in our simulation assignshigher priority to real-time service flows over non-real-time service flows. Given the ben-efits of WDRR over WFQ as discussed earlier, the scheme implements WDRR instead ofWFQ for allocating resource among non-real-time service flows, whereas EDF is retainedfor resource allocation among real-time service flows.Fig. 2.10 presents the number of non-real-time service flows that can be supportedsimultaneously with different number of real-time service flows. The QoS requirementfor the non-real-time service flows is set to a maximum packet loss rate of 1%, whereasthe real-time service flows are guaranteed a maximum packet delay of 50 ms with 95%probability and a maximum packet loss rate of 1%. We can see that, compared to thehierarchical scheme, our proposed scheme can provide QoS for more number of service73flows when both real-time and non-real-time applications are competing for service. Withthe hierarchical scheme, the queues attached to non-real-time traffic are serviced only afterthe queues of real-time traffic are exhausted. As a result, some non-real-time traffic queuesmight not receive adequate resource to meet their QoS or might even starve while the real-time traffic queues are allocated more than enough resource. Our proposed scheme, on theother hand, does not need such priority-based mechanism to protect the QoS of real-timeservice flows; individual service flows are allocated resource according to their QoS needsregardless of their service classes. The benefit of such isolation of service compared toa priority-based hierarchical scheme is evident in the results plotted in Fig. 2.10. Thesefindings confirm that our proposed scheme not only excels in providing QoS for individualapplication types but also better protects their QoS from each other in a heterogeneoustraffic scenario.2.7 Related WorkPrevious work on resource allocation on WiMAX systems has evolved over time as thestandardization activities have matured. In the uplink, the resource allocation problem isoften jointly addressed with bandwidth request/grant mechanisms as a WiMAX BS doesnot have direct access to queues located at individual MSs. In this work, we focus on down-link resource allocation problem, and for a survey on uplink resource allocation schemes,we refer readers to [16].For the basic 802.16 standard, which was introduced with single-carrier PHY, the re-source allocation problem, however, is very similar to that in TDMA-based cellular sys-tems. This also applies to OFDM PHY, as with IEEE 802.16d, where all subcarriers areallocated as a whole to a particular MS during a frame either in the uplink or the downlink74direction. Many of the earlier resource allocation solutions were proposed assuming timedivision multipexing without focusing on any specific PHY. They are often packet schedul-ing schemes based on traditional time-domain radio resource scheduling solutions and arecustomized to make compatible with the scheduling service classes defined in the 802.16standard. Some of these schemes are designed for specific traffic types such as video,VoIP and targets the relevant service classes. For delay sensitive applications that usertPS scheduling service, EDF and Modified Largest Weighted Delay First (MLWDF) [17]were evaluated in previous research. Classical wired network schedulers such as WeightedRound Robin (WRR), WFQ and their variants were also proposed and evaluated for bothdelay-sensitive rtPS and throughput-guaranteed nrtPS applications. Wongthavarawat andGanz [9] proposed a hierarchical scheduling scheme where EDF and WFQ are used forintra-calss scheduling of rtPS and nrtPS connections respectively, and a simple prioritybased scheme is adopted for allocating resource among different service classes. The solu-tion proposed by Wang and Dittman in [18] is another example of hierarchical schedulingscheme. Among other solutions, Niyato and Hossain [20] proposed a scheduling mech-anism that distributes the available bandwidth of the WiMAX channel to the connectionsbelongingtodifferentserviceclassesbyusingajointqueueing andoptimizationmodel; theaim was to maximize the utility which is dependent on the average throughput and delayperformance achieved by connections belonging to different QoS classes. In [19], Liu et al.proposedacross-layerschedulingschemethatassignsafixedamountofbandwidthtoUGSconnections and then uses a priority function to determine the connection to be scheduledfor the remaining bandwidth in a frame. The priority function for each connection is cal-culated using the channel quality, service status and QoS requirments. Only one non-UGSconnection is scheduled in a frame, which might result in inefficient resource usage. Lera75et al. proposed a schemer that tweaked the WF2Q+ algorithm in [21] to work for per-classqueues rather than per-flow queues that WF2Q is originally designed for. Chen et al. in [22]introduced a fuzzy logic based scheduling algorithm to provide intra-class QoS guaranteeswhile maintaining intra- and inter-class fairness. The online computation requirement withthe scheme, however, could be prohibitively high.Resource allocation schemes specifically proposed for OFDMA-based WiMAX sys-tems, however, follow two main avenues of research. The first avenue of research con-siders subcarrier/subchannel assignment along with rate and power adaptation across usersmainly to improve system level performance such as capacity and throughput. These solu-tions have basic similarity with those for OFDMA resource allocation problem in general.Examples of such solutions are [23, 24, 25, 26] and their main limitation is that the goalis to improve system performance but not necessarily to provide specific QoS to applica-tions and service. The second category of solutions involve frame-by-frame schedulingof OFDMA subchannels or slots among admitted service flows or connections. Yahiya etal. [27] proposed a cross-layer scheduling mechanism that assigns priorities to UGS, rtPSand nrtPS connections for each available subchannel. The scheme, however, has the lim-itation of assuming an AWGN channel model and of possible starvation of applicationsthat have low traffic intensity. Performance results only showed average system throughputand packet loss probability achieved for different number of users. In [28], Mehrjoo et al.proposed a queue- and channel-aware schedular, called opportunistic stable queue schedul-ing for WiMAX downlink. The scheduler, however, aimed to improve overall throughputand packet dropping probability experienced by MSs in the system and did not providemechanism to meet QoS guarantees for individual connections. In [29], Ali et al. proposeda cross-layer scheme where the scheduling priorities of different connections are calcu-76lated using channel quality, service class and QoS requirements of the connections. Theoptimization-based solution is likely to suffer from very high implementation complexity.The average delay and throughput performances achieved by different service classes overtime were presented, but how well QoS guarantees for individual connections could be metwas not shown in the simulation results. Wan et al. took a similar approach in [30], butresorted to priority-based scheduling to avoid complexity of an optimized solution. Aver-age system throughput, average rtPS packet loss rate and average nrtPS packet delay werepresented against different channel SNR. Effectiveness in meeting QoS guarantees for in-dividual connections was not presented.2.8 ConclusionIn this chapter, we have proposed a novel resource allocation framework for downlinkservice flows in IEEE 802.16e mobile WiMAX systems. At first, we have developed aqueueing analytical model that relates important performance measures of an admitted ser-vice flow to its packet arrival statistics and a parameter in the packet scheduling scheme.Referring to this parameter as the model parameter for the service flow, we have demon-strated how the output from the queueing model can be utilized to set the appropriate valuefor this model parameter. This value of the model parameter essentially allows to computethe minimum number of packets that need to be scheduled from the queue of the serviceflow in order to meet its QoS requirement. Each admitted service flow is associated with amodel parameter. Next, we have proposed a cross-layer adaptive and queue-aware resourceallocation scheme that utilizes these parameter values along with the channel quality andbacklog information to schedule packets and allocate OFDMA slots among downlink QoSconnections. The proposed model-based approach offers simplicity of design for the on-77line component, flexibility to the service providers in defining QoS parameters and bettercompatibility to the IEEE 802.16e standard. Instead of complexities involved with in-stalling separate scheduling schemes within the same resource allocation framework forreal-time and non-real-time traffic, our model-based approach offers an efficient unifiedway to handle both types of traffics and their diverse QoS requirements. We have runsimulation experiments to evaluate the performance of our proposed scheme in providingQoS for VBR real-time and non-real-time multimedia and data services. Compared to EDFscheduling, which is specialized for allocating resource to delay-sensitive applications, ourproposed scheme significantly reduces delay violation probability and packet loss rate forreal-time services. As a result, the number of real-time service flows that can be supportedby the system is also improved considerably. For non-real-time services, our proposedscheme achieves much better packet loss rate performance and can support significantlymore service flows compared to throughput conscious WDRR scheduling. We have alsoshown that, even without priority-based or complex hierarchical approach, our proposedscheme can successfully protect QoS of individual service flows in a heterogenous trafficscenario involving both real-time and non-real-time services.782.9 Bibliography[1] IEEE Std. 802.16-2001, “IEEE Standard for Local and Metropolitan Area Networks –Part 16: Air Interface for Fixed Broadband Wireless Access Systems,” Apr. 2002.[2] IEEE 802.16e-2005, “IEEE Standard for Local and Metropolitan Networks – Part 16:Air Interface for Fixed and Mobile Broadband Wireless Access Systems, Amendment2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Op-eration in Licensed Bands and Corrigendum 1,” Feb. 2006.[3] IEEE 802.16-2004, “IEEE standard for Local and Metropolitan Area Networks – Part16: Air Interface for Fixed Broadband Wireless Access Systems,” Oct. 2004.[4] H. Kobayashi and B. L. Mark, System Modeling and Analysis: Foundations of SystemPerformance Evaluation, Prentice Hall, 2008.[5] P. Salvador, A. Pacheco, and R. Valadas, “Multiscale Fitting Procedure using MarkovModulated Poisson processes,” Telecommunications Systems, vol. 23, no. 1-2, pp. 123-148, Jun. 2003.[6] D.P. Heyman and D. Lucantoni,“Modeling Multiple IP Traffic Streams with Rate Lim-its,” IEEE/ACM Transactions on Networking, vol. 11, no. 6, pp. 948-958, Dec. 2003.[7] M. Shreedhar and G. Varghese, “Efficient Fair Queuing Using Deficit Round Robin,”IEEE/ACM Transactions on Networking, Vol.4, No.3, pp. 375-385, June 1996.[8] A. Demers, S. Keshav, and S. Shenker, “Analysis and Simulation of a Fair QueueingAlgorithm,” Proc. ACM SIGCOMM, Austin, TX, pp. 1-12, Sep. 1989.79[9] K. Wongthavarawat and A. Ganz, “Packet Scheduling for QoS Support in IEEE 802.16Broadband Wireless Access Systems,” International Journal of Communication Sys-tems, vol. 16, no. 1, pp. 81-96, Feb. 2003.[10] O.Gusak, N.Oliver, andK.Sohraby, “PerformanceEvaluationofthe802.16MediumAccess Control Layer,” Lecture Notes on Computer Science, vol. 3280/2004, pp. 228-237, Oct. 2004.[11] C. Cicconetti, A. Erta, L. Lenzini, and E. Mingozzi, “Performance Evaluation of theIEEE802.16MACforQoSSupport,” IEEE Transactionson Mobile Computing, vol.6,no. 1, pp. 26-38, Jan. 2007.[12] J. Lakkakorpi, A. Sayenko, and J. Moilanen, “Comparison of Different SchedulingAlgorithms for WiMAX Base Station: Deficit Round-Robin vs. Proportional Fair vs.Weighted Deficit Round-Robin,” Proc. IEEE Wireless Communications and Network-ing Conference, pp. 1991-1996, Las Vegas, NV, Mar. 2008.[13] R. Srinivasan, S. Timiri, A. Davydov, and A. Papathanassiou, “Downlink spectralefficiency of Mobile WiMax,” Proc. IEEE Vehicular Technology Conference, Dublin,Ireland, Apr. 2007.[14] ITU-R Task Group 8/1 “Guidelines for Evaluation of Radio Transmission Technolo-gies for IMT-2000,” Recommendation ITUR M.1225, 1999.[15] G. Dan, V. Fodor, and G. Karlsson, “On the Effects of The Packet Size Distributionon FEC Performance,” Computer Networks, vol. 50, no. 8, pp. 1104-1129, Jun. 2006.80[16] N. A. Ali, P. Dhrona, and H. Hassanein, “A Performance Study of Uplink schedulingAlgorithms in Point-to-Multipoint WiMAX Networks,” Computer Communications,vol. 32, no. 3, pp. 511-521, Feb. 2009.[17] M. Andrews, K. Kumaran, K. Ramanan, A. Stolyar, P. Whiting, and R. Vijayakumar,“Providing Quality of Service over a Shared Wireless Link,” IEEE CommunicationMagazine, vol. 39, no. 2, pp. 150-154, Feb. 2001.[18] H. Wang and L. Dittmann, “Adaptive Radio Resource Allocation in Hierarchical QoSScheduling for IEEE 802.16 Systems,” Proc. IEEE Global Telecommunications Con-ference, pp. 4769-4774, Washington, D.C., Nov. 2007.[19] Q. Liu, X. Wang, and G. B. Giannakis, “A Cross-Layer Scheduling Algorithm withQoS Support in Wireless Networks,” IEEE Transactions on Vehicular Technology,vol. 55, no. 3, pp. 839-847, May 2006.[20] D. Niyato and E. Hossain, “A Queuing-Theoretic and Optimization-Based Model forRadio Resource Management in IEEE 802.16 Broadband Wireless Networks,” IEEETransactions on Computers, vol. 55, no. 11, pp. 1473-1488, Nov. 2006.[21] A. Lera, A. Molinaro, and S. Pizzi, “Channel-Aware Scheduling for QoS and FairnessProvisioning in IEEE 802.16/WiMAX Broadband Wireless Access Systems,” IEEENetwork, vol. 21, no. 5, pp. 34-41, Sept.-Oct. 2007.[22] C-L. Chen, J-W. Lee, C.-Y. Wu, and Y.-H. Kuo, “Fairness and QoS Guarantees ofWiMAX OFDMA Scheduling with Fuzzy Controls,” EURASIP Journal on WirelessCommunications and Networking, vol. 2009, Article ID 512507, 14 pages, Jan. 2009.81[23] A. Biagioni, R. Fantacci, D. Marabissi, and D. Tarchi, “Adaptive Subcarrier Alloca-tion Schemes for Wireless OFDMA Systems in Wimax Networks,” IEEE Journal onSelected Areas in Communications, vol. 27, no. 2, pp. 217-225, Feb. 2009.[24] G. Miao and N. Himayat, “Low Complexity Utility Based Resource Allocation for802.16 OFDMA Systems,” Proc. IEEE Wireless Communications and NetworkingConference, pp. 1465-1470, Las Vegas, NV, Mar.-Apr. 2008.[25] V. Singh and V. Sharma, “Efficient and Fair Scheduling of Uplink and Downlink inIEEE 802.16 OFDMA Networks,” Proc. IEEE Wireless Communication and Network-ing Conference, vol. 2, pp. 984-990, Las Vegas, NV, Apr. 2006.[26] C. Tarhini and T. Chahed, “AMC-Aware QoS Proposal for OFDMA-Based IEEE802.16 WiMAX Systems,” Proc. IEEE Global Telecommunications Conference,pp. 4780-4784, Washington, D.C., Nov. 2007.[27] T.A. Yahiya, A.-L. Beylot, and G. Pujolle, “Cross-Layer Multiservice Schedulingfor Mobile WiMAX Systems,” Proc. IEEE Wireless Communications and NetworkingConference, pp. 1531-1535, Las Vegas, NV, Mar.-Apr. 2008.[28] M.Mehrjoo, X.Shen, andK.S.Naik, “AJointChannelandQueue-AwareSchedulingfor IEEE 802.16 Wireless Metropolitan Area Networks,” Proc. IEEE Wireless Commu-nications and Networking Conference, Hong Kong, pp. 1549-1553, Mar. 2007.[29] N.A. Ali, M. Hayajneh, and H. Hassanein, “Cross Layer Scheduling Algorithm forIEEE 802.16,” Proc. IEEE International Conference on Communications, pp. 3858-3862, Beijing, China, May 2008.82[30] L. Wan, W. Ma and Z. Guo, “A Cross-Layer Packet Scheduling and Subchannel Al-location Scheme in 802.16e OFDMA System,” Proc. IEEE Wireless Communicationsand Networking Conference, pp. 1865-1870, Hong Kong, Mar. 2007.83Chapter 3Cross-Layer Analysis of DownlinkV-BLAST MIMO TransmissionExploiting Multiuser Diversity13.1 IntroductionEver increasing demand for high data rate transmission over wireless systems has openedmany new avenues of research in wireless communication. Multiple Input Multiple Out-put (MIMO) wireless technology is receiving profound attention in this respect becauseit can enhance spectral efficiency significantly in rich scattering wireless environment [1].Besides increased data rate, a major goal of future wireless systems design is to provideproper Quality of Service (QoS) in terms of performance measures such as delay, packetloss, packet throughput to both data and time intensive applications that are increasingly1A version of this chapter has been published. Rashid, M.M., Hossain, E. and Bhargava V.K. (2009)Cross-Layer Analysis of Downlink V-BLAST MIMO Transmission Exploiting Multiuser Diversity. IEEETrans. on Wireless Commun. 8(9):4568–4579.84beingdeployedonwirelesssystems. Althoughimprovingphysicallayerdatarateisamajorstep toward this objective, this will often not be enough. This is especially true for mul-tiuser systems where many users have to compete for the limited available radio resource.A cross-layer design approach is a more viable approach that would take into considerationboth physical and Medium Access Control (MAC) layer aspects of the communication aswell as the traffic characteristics and QoS requirement of the applications. Studying thecross-layer effects on the QoS experienced by the users in such systems is an importantstep towards this objective.Among many signal processing techniques available for MIMO wireless systems, V-BLAST[2]is wellknownforitsabilitytoofferexcellentperformance-complexitytradeoff.The V-BLAST aims to achieve MIMO potential by employing spatial multiplexing, whichcan theoretically offer a nearly linear increase in system capacity with increasing numberof transmit antennas–provided thatthe number of receive antennas is greater than or equalto the number of transmit antennas. In a multiuser scenario, how well this improved ca-pacity can be utilized also depends on how transmissions are scheduled among the users.Exploiting multiuser diversity in the scheduling process has been shown to achieve optimalsystem throughput for Single Input Single Output (SISO) systems [3]. Multiuser diversitycan also be exploited to the efficient utilization of the increased system capacity in MIMOsystems [4]. In fact, simple zero-forcing (ZF) receivers in conjunction with multiuser di-versity have been shown to achieve a large portion of MIMO downlink capacity [5, 6, 7].By considering the linear ZF receiver with the V-BLAST transmission model, the MIMOchannel can be decoupled into parallel independent subchannels. The transmit antennashave a one-to-one association with these subchannels, which can now transmit indepen-dentstreamsorsubstreams[4]. Inamultiuserscenario, multiuserdiversitycanbeexploited85further by utilizing this extra dimension to opportunistically assign different transmit an-tennas to different users over time. The independent stream scheduler proposed by HeathJr. et al. in [4] is designed based on this idea. As a generalization of the throughput op-timal scheduling for multiuser diversity in SISO systems, it is expected to offer excellentthroughput performance for the multiuser MIMO systems considered in this chapter.Inthischapter, weconsiderthe independent stream scheduler inthedownlinktoexploitmultiuser diversity in a V-BLAST MIMO wireless system and develop a queuing analyticmodel to determine the cross-layer effects on important QoS measures. We model theindependent subchannels associated with each of the transmit antennas by a Finite StateMarkov chain (FSMC) and consider Adaptive Modulation and Coding (AMC) employedin the physical layer to achieve a predefined packet error rate. From the queuing model, wederive important performance measures at the MAC layer. From the model output, theseperformance measures can be related to the physical layer parameters and traffic arrivalstatistics. Example applications of the queuing model are also outlined which include amodel based admission control scheme.Although many related research efforts have dealt with performance analysis (e.g. [8,9, 5, 10, 11]) and performance enhancement (e.g. [12, 13, 14, 15]) of multiuser MIMOsystems, their focus in most cases has been on the capacity, throughput and/or outage prob-abilityachievableatthephysicallayer. We, incontrast, proposeaveryelaboratecross-layeranalytical model to relate the physical layer parameters with the MAC layer performancemeasures in presence of multiuser diversity exploited in the resource scheduling process.As in multiuser SISO systems, multiuser diversity has been shown to have a great potentialin improving system performance in multiuser MIMO systems as well. Heath Jr. et al.in [4] have presented simulation analysis on various ways to exploit the multiuser diver-86sity in multiuser MIMO systems and their effects on the spectral efficiency of the system.Airy et al., on the other hand, have presented analytical models in [16] to compare twoopportunistic scheduling techniques in this context. The performance measures are the rawbit rate achievable from the system and the average delays experienced by fixed sized filesserved from different users. The results from these two research works have motivated usto choose the particular scheduling scheme assumed in our chapter. However, unlike theauthors in these works, we develop a cross-layer analytical model that captures the layeredaspect of the system design, derives more comprehensive performance measures such aspacket delay statistics, packet throughput and loss rate, and relates these performance toimportant physical layer and traffic parameters for better system design. Our work alsoconsiders more realistic traffic model that captures the potential burstiness in the arrivalprocess.The rest of the chapter is organized as follows. In section 5.2, we describe the MIMOsystem model and multiuser diversity scheme that we are considering in this chapter, anddiscuss relevant assumptions. We formulate the queuing model and derive important per-formance measures from the model in section 3.3. In section 5.4, we present some se-lected numerical results derived from the queuing model. Some example applications ofthe model are presented in section 5.5. Section 6 concludes the chapter with some futureresearch directions.3.2 System Model and AssumptionsWe consider a MIMO wireless system comprising of a number of users covered by a singlebase station. The model presented in this chapter focuses on downlink scheduling. There-fore, the transmission buffers for the users are assumed to be located at the MAC layer in87the base station. We consider limited space in these transmission buffers and assume thatdownlinktrafficarriveatthesetransmissionbuffersfollowingsomestochastictrafficarrivalprocess. The MIMO system consists of V-BLAST transmission model with a ZF detectorat the receiver side.Similar to the MAC layer model used in [17], packets arrive from the higher layers tothe MAC layer where they are grouped into MAC layer frames. The system is assumedto be time slotted with the slot size equal to the duration of a frame transmission. Thisduration, Tf is fixed although the size (in bits) of a frame might vary from frame to framedue to the AMC used to adaptively adjust the transmission rate at different transmit an-tennas. Considering a slowly varying fading environment, we assume that the channelremains static over a frame duration.Assuming a fixed packet size, the number of packetstransmitted in a frame duration will vary accordingly. The MIMO transmission model al-lows independent streams to be transmitted through different transmit antennas, which arelocated at the base station for downlink transmission. The V-BLAST MIMO transmissionmodel and the receiver architecture are briefly described in the next subsection.3.2.1 MIMO Transmission Model and Receiver ArchitectureWe consider V-BLAST transmission model withttransmit antennas andr receive antennas(r ≥ t). If s = [s1,s2,···,st]T is the vector of symbols transmitted from the t transmitantennas during a symbol time and H is the t×r channel matrix at that time instant, thenthe received signal vectorv = [v1,v2,···,vr]T can be expressed asv = sH+w, (3.1)88where w = [w1,w2,···,wr]T is the noise vector. We assume that the elements of thisnoise vector are zero mean i.i.d Gaussian random variables with variance equal to N0.For the detection of the symbol vector from the V-BLAST transmitter, several detec-tion algorithms including minimum mean square error (MMSE), successive interferencecancellation (SIC) and ZF have been proposed for the MIMO receiver [2]. Choice of a re-ceiver algorithm, in general, is a tradeoff between performance and implementation cost/-complexity. ZF is simple and offers low cost implementation, but is known to suffer fromthe effect of noise enhancement. MMSE is more complex than ZF, but offers better noisesuppression. In contrast, with much higher complexity, SIC-based receiver could poten-tially achieve the full capacity gain of the MIMO system [5, 18]. However, in a multiuserscheduling system, multiuser diversity can offer a natural way to mitigate the drawbackof poor noise performance by ZF; in fact, it has been shown that the combination of mul-tiuser diversity with zero forcing can lead to a low-cost and effective way for achieving alarge portion of MIMO downlink capacity [5, 6, 7]. Besides these, the fact that the post-detection SNR distribution for ZF receiver is known allows for nice analytical tractabilityfor our cross-layer queueing analysis.In ZF detection, the receiver, which is assumed to have the perfect knowledge of thechannel, multiplies the signal vector received during a symbol time by the pseudo-inverseH† of the channel matrix at that time instant. Assuming a transmission power of Es pertransmit antenna, the post-detection SNR associated with the ith transmit antenna i.e. thepost-detection SNR at the ith subchannel can be expressed as [19]γi = EsN0[H∗H]−1ii= γ0[H∗H]−1ii,i = 1,2,···,t, (3.2)89where H∗ is the Hermitian transpose of H and γ0 = Es/N0. Due to this MIMO systemmodel, t independent streams can be fed into t transmit antennas. However, a single datastream can be divided into t independent substreams for transmission as well.3.2.2 Modeling the MIMO ChannelWe assume a point-to-point Rayleigh flat fading channel with transmit antenna correlation,but without any receive antenna correlation. In cellular mobile systems, in general thereare several local scatterers around the receiver or hand set. Due to the effect of theselocal scatterers, fading of the received signals are more likely to be uncorrelated across thereceiver antennas. However, at the base stations trasmit antennas are often mounted on topof high buildings or towers. Local scatterers are not usually present around these transmitantennas and therefore, the signal fading across these antennas tends to be correlated. Withthisassumption, theprobabilitydensityfunction(pdf)ofthepost-detectionSNRassociatedwith the ith subchannel can be shown to be Gamma distributed as follows due to [19]:f(γi) = γr−ti(γ0/σ2i )r−t+1Γ(r−t + 1) exp(− γiγ0/σ2i), (3.3)where σ2i is the ith diagonal entry of the inverse of the transmit correlation matrix.We assume that the post detection SNR of each subchannel is quantized into a numberof discrete values which are fed back to the transmitter to adjust the modulation level.These discrete values essentially represent the subchannel states. If Z + 2 thresholds{ϕ0,ϕ1,···,ϕZ+1} are used to quantize a subchannel, the subchannel will have Z + 1statesC={0,1,···,Z}and it will be in state j when the post-detection SNR is within therange (ϕj,ϕj+1]. Here it is assumed that the SNR thresholds satisfy the following inequal-ity: 0 = ϕ0≤...≤ϕj ≤...≤ϕZ+1 =∞.90Assuming correlated block fading, we model the variation in each subchannel overtime using an FSMC, which is a well accepted channel model for slowly varying environ-ment [20]. For a given doppler spread, the transition probabilities between the states of theFSMC can be found from the post-detection SNR distribution following few steps as de-scribed, for example, in [17]. In the transmitter, for each of the transmit antennas, AMC isapplied to map a unique transmission rate to each of the states of the associated subchannel.When the subchannel is in statej, ζj packets can be transmitted per frame time through thissubchannel using transmission mode j. These transmission modes are selected such that aprescribed average packet error rate PER can be maintained at each subchannel state.3.2.3 Multiuser Diversity SchemeThe objective of downlink multiuser diversity systems is to maximize long run average sys-tem throughput. The opportunistic scheduling scheme proposed in [3] for SISO systemshas been shown to achieve this objective by assigning the time slot in consideration to theuser that has the best channel quality at that time instant. Heath Jr. et al. in [4] have pro-posed generalization of this scheme for MIMO systems where the MIMO channel can bemodeled as a series of parallel SISO equivalent channels. The scheduler is called indepen-dent stream scheduler which assigns each transmit antenna at each time slot independentlyto the user who has the highest state in the subchannel associated with the transmit antenna.If more than one users exhibit the highest state for that subchannel, then one of those usersis picked up randomly to be assigned to that transmit antenna. As a result, a single usermay be assigned zero, one or more than one transmit antennas at any time instant.Note that optimality results similar to [3] is not possible for MIMO multiuser diversitysystems due to the dependence of throughput not only on the received SNR but also on91the subspace structure of the channel matrix and the receiver [4]. The independent streamscheduler considered in this chapter is thus not a provably optimal MIMO multiuser di-versity scheme. However, as a generalization of the throughput optimal SISO multiuserdiversity scheme, it is expected to offer excellent throughput performance for the multiuserMIMO systems considered in this chapter.3.3 Queueing Model and AnalysisWe consider a system where all the users have the same number of receive antennas andhave similar channel fading characteristics. These assumptions of a homogeneous systemallow us to model the system from the perspective of a tagged user. Without loss of gener-ality, the following analysis is done considering user 1 as the tagged user and therefore, theuser number index for user 1 is omitted. Also note that the time slot duration in the discretetime queuing model is equal to a MAC layer frame transmission time, Tf.We assume that packets arrive in the buffer following a Batch Bernoulli arrival process.We also assume that packets arriving during time interval n−1 cannot be served untiltime interval n at the earliest. This arrival process can be described by a vector α =[α0,α1,···,αN], where N is the maximum batch size, the maximum number of packetsthat can arrive during a time slot. In our model, α0 is the probability that no packets arrivesand αi(1≤i≤N) is the probability that i packets arrive in a time slot. The average arrivalrate λ can be calculated as follows:λ =N∑i=1iαi. (3.4)The assumed Batch Bernoulli arrival model is very general which can capture different92level of burstiness in the traffic arrival process. The waiting packets in the queue are servedinafirst-comefirst-servedmanner. Besides,packettransmissionsinatimeslotareassumedto finish before arriving packets enter the queue.As we have seen in previous section, due to the MIMO transmission model and thedetection scheme we consider, the allocation of a transmit antenna to a user is equivalentto allocating the associated subchannel to that user. In the following, the term subcannel,when used, should be interpreted as such. Let the random variable m(i)n ∈{1,0}repre-sent whether ith subchannel is assigned to the tagged user or not at time slot n due to themultiuser diversity scheme. Let m(i)n = 1 denote that the ith subchannel is assigned to thetagged user at time slot n. Similarly c(i)n ∈C denotes the state of the ith subchannel attime slot n at tagged user’s end. Therefore, for the ith subchannel, the joint state indicatingwhether it is assigned to the tagged user and its state at time slot n at tagged user’s end,is a vector denoted as (m(i)n ,c(i)n ). We can write the state transition matrix for vector states(m(i)n ,c(i)n ) as follows:M(i) = M(i)0→0 M(i)0→1M(i)1→0 M(i)1→1, (3.5)where M(i)k→l is the Z×Z matrix whose elements are defined as follows:M(i)k→l(f,g) = Pr (m(i)n+1 = l,c(i)n+1 = g|m(i)n = k,c(i)n = f). (3.6)The probability in (3.6) can be expressed asPr(m(i)n+1,c(i)n+1|m(i)n ,c(i)n ) = Pr(m(i)n+1|c(i)n+1,m(i)n ,cin)×Pr(c(i)n+1|c(i)n ), (3.7)where we have used the fact that Pr(c(i)n+1|m(i)n ,c(i)n ) = Pr(c(i)n+1|c(i)n ). Also, Pr(c(i)n+1|c(i)n )93can be determined from the transition probability matrix of the FSMC associated with thesubchannel as Pr(c(i)n+1 = g|c(i)n = f) is the probability that the ith subchannel transits fromstate f to g. In addition, Pr(m(i)n+1|c(i)n+1,m(i)n ,c(i)n ) can be written as :Pr(m(i)n+1|c(i)n+1,m(i)n ,c(i)n ) = Pr(m(i)n+1,m(i)n |c(i)n+1,c(i)n )Pr(m(i)n |c(i)n ), (3.8)where we used the fact that Pr(m(i)n |c(i)n+1,c(i)n ) = Pr(m(i)n |c(i)n ). We show the computa-tion process for these probabilities in the following. Since m(i)n+1 can be either 0 or 1, wecan write Pr(m(i)n+1 = 0|c(i)n+1,m(i)n ,c(i)n ) = 1−Pr(m(i)n+1 = 1|c(i)n+1,m(i)n ,c(i)n ). Therefore,showing the derivations for m(i)n+1 = 1 will be sufficient.Let us express the state of subchannel i at user h(1 ≤ h ≤ S) at time slot n as c(i,h)n ,where S is the total number of users in the system. Now, to find the denominator of theright side expression in (3.8), we can writePr(m(i)n = 1|c(i)n = f) =Z∑c(i;2)n =0···Z∑c(i;S)n =0Pr(m(i)n = 1,c(i,2)n ,···,c(i,S)n |c(i)n = f), (3.9)in which the inner probability expression of the right side can be derived as follows:Pr(m(i)n = 1,c(i,2)n ,···,c(i,S)n |c(i)n = f) =0, if∃h(2≤h≤S) s.t. c(i,h)n > f1uS∏h=2Pr(c(i,h)n ), otherwise,(3.10)where u is the number of users that have the same state as that of the tagged user (user1) on subchanne i at time slot n. Probabilities Pr(c(i)n ) can be found from steady stateprobabilities of FSMC for subchannel i. We can also derive Pr(m(i)n = 0|c(i)n = f) as94Pr(m(i)n = 0|c(i)n = f) = 1−Pr(m(i)n = 1|c(i)n = f).Now, let us derive the numerator of the right side expression of (3.8) for m(i)n+1 = 1. Wecan rewrite the expression asPr(m(i)n+1 = 1,m(i)n |c(i)n+1,c(i)n )=Z∑c(i;2)n+1=0···Z∑c(i;S)n+1 =0Z∑c(i;2)n =0···Z∑c(i;S)n =0Pr(m(i)n+1 = 1,m(i)n ,c(i,2)n+1,···,c(i,S)n+1,c(i,2)n ,···,c(i,S)n |c(i)n+1,c(i)n ),(3.11)in which the inner probability expression in the right side can be derived as follows forPr(m(i)n+1 = 1,m(i)n = 1|c(i)n+1 = g,c(i)n = f) at the left side:Pr(m(i)n+1 = 1,m(i)n = 1,c(i,2)n+1,···,c(i,S)n+1,c(i,2)n ,···,c(i,S)n |c(i)n+1 = g,c(i)n = f)=0, if∃h(2≤h≤S) s.t. (c(i,h)n > f or c(i,h)n+1 > g)1uvS∏h=2Pr(c(i)n+1,c(i)n ), otherwise, (3.12)where v is the number of users that have same state for subchannel i as that of the taggeduser (user 1) at time slot n + 1. The probabilities Pr(c(i)n+1,c(i)n ) can be derived fromthe FSMC of subchannel i as Pr(c(i)n+1,c(i)n ) = Pr(c(i)n+1|c(i)n )×Pr(c(i)n ). Similarly, forPr(m(i)n+1 = 1,m(i)n = 0|c(i)n+1 = g,c(i)n = f) at the left side of (3.11), we can derive theinner probability expression in the right side asPr(m(i)n+1 = 1,m(i)n = 0,c(i,2)n+1,···,c(i,S)n+1,c(i,2)n ,···,c(i,S)n |c(i)n+1 = g,c(i)n = f)=0, if (∃h(2≤h≤S) s.t. c(i,h)n+1 > g) or (∀h(2≤h≤S) c(i,h)n < f)1vS∏h=2Pr(c(i)n+1,c(i)n ), if ∃h(2≤h≤S) s.t. c(i,h)n > fu−1uvS∏h=2Pr(c(i)n+1,c(i)n ), otherwise(3.13)95Now considering all the transmit antennas or the associated subchannels, the process de-fined by state spaceWn , {(m(1)n ,c(1)n ,···,m(t)n ,c(t)n )|∀i∈{1,2,···t}m(i)n ∈{0,1},c(i)n ∈C}is a discrete-time Markov Chain (DTMC), whose transition matrixW can be written asW = M(1)⊗M(2)⊗···⊗M(t). Its steady state probability distributionφcan be foundfrom solving the set of linear equations: φW = φ and φ1 = 1, where 1 stands for acolumn matrix containing 1 only in each entry.3.3.1 Formulation as a Quasi-Birth-and-Death ProcessAssuming a finite buffer size ofQ, let us define a processPn ,{(xn,an)|0≤xn≤Q,0≤an ≤ L}, where state variable xn is the number of packets at the tagged user’s queue atthe beginning of time slot n, state variable an is the maximum number of packets that canbe transmitted from that queue at time slot n and L = tζZ. Assuming that state transitionoccurs only at the slot boundaries and noting the fact that the state variables are designedto assume discrete values only, we can model the system processPn using a DTMC. Toderive the transition probability matrix of the DTMC, we consider the system dynamics asit evolves over one frame to the next frame. With an infinite buffer space (Q = ∞), thestate transition probability matrix for the DTMC describing the system can be written asP =A(0)0 A(0)1+ ··· ··· A0N+A(1)1− A(1)0 A(1)1+ ··· ··· A(1)N+... ... ...A(L−N+1)(L−N+1)− A(L−N+1)(L−N)− ··· ··· ··· ··· A(L−N+1)1− A0(L−N+1)A(L−N+1)1+ ··· A(L−N+1)(N−1)+ AN+... ... ... ... ... ...A(L)L− A(L)(L−1)− ··· ··· ··· ··· ··· ··· ··· A(L)1− A0(L) A1+ ··· ··· AN+AL− ··· ... ··· ··· ··· ··· ··· ··· A1− A0 A1+··· ··· AN+... ... ... ...AL− ··· ··· ··· ··· ··· ··· A(L−N+1)− A(L−N)− ··· ··· ··· ··· A1− A0 A1+ ··· A(N−1)+ AN+... ... ... ... ... ... ...AL− A(L−1)− ··· ··· ··· ··· ··· ··· ··· A1− A0 A1+ ··· AN+... ... ....(3.14)96By constructing blocks of submatrices as shown in (3.14), we can obtain a quasi-birth-and-death (QBD) process with a transition matrix as follows:Pinf =B EC D G0G2 G1 G0G2 G1 G0... ... .... (3.15)However, we are interested in finding performance measures for systems with finite bufferspace, which is more realistic. Setting K =⌊Q/L⌋, we can write the transition matrix inthe following form:P =0123...K−1KB EC D G0G2 G1 G0G2 G1 G0... ... ...G2 G1 G′0G′2 G′1. (3.16)The next step in the model involves deriving the submatrices inside P. We proceed byconsidering a process defined by the state spaceVn , {an|0 ≤ an ≤ L}. Now let bkdenote the set of states from state space Wn resulting in an = k, where 0 ≤ k ≤ L.WithWh→h′ denoting the transition probability from state h to h′, where both h and h′ areelements of state spaceWn, we can construct the transition probability matrix V for state97spaceVn asVi→j =∑h∈bi∑h′∈bjφhWh→h′∑h∈biφh , where Vi→j denotes the transition probability fromstate i to state j.Now, let us define a number of (L + 1)×(L + 1) matrices as followsU(g) =εg+1V, 0≤g≤L,where εg+1 is a row vector of size L + 1, in which all the elements are 0 except a 1 atposition g + 1. With these matrices defined, we can derive the inner submatrices of P in(3.14) as follows:A(0)0 = α0V; A(0)d+ = αdV,1≤d≤N (3.17)A(e)d− =α0L∑j=eU(j), d = ee−d−1∑j=0αjU(j+d) + αe−dL∑j=eU(j),e−N ≤d≤e−1N∑j=0αjU(j+d), 1≤d < e−N,for 1≤e≤L−1(3.18)A(e)d+ =d+e−1∑j=dαjU(j−d) + αd+eL∑j=eU(j),1≤d≤N,1≤e≤L−1 (3.19)A(e)0 =e−1∑j=0αjU(j) + αeL∑j=eU(j), 1≤e≤NN∑j=0αjU(j), N < e≤L(3.20)98Ad− =N∑j=0αjU(j+d),1≤d≤L (3.21)Ad+ =N∑j=dαjU(j−d),1≤d≤N (3.22)A0 =N∑j=0αjU(j) (3.23)G′0 =[G0 0L2×K′L](3.24)G′1 =A0 A1+ ··· AN+A1− A0 A1+ ··· AN+... ... ...A(L−N+K′)− ··· ··· ··· A′(N−1)+... ... ...AL− ··· ··· ··· ··· A′(K′−1)+... ... ...AL− ··· ··· ··· A′1+AL− ··· ··· A′0(3.25)99A′k+ = U(0)αk +N∑j=k+1αj [U(j−k) +U(0)],1≤k≤N−1 (3.26)G′2 = G20K′L×L2, (3.27)where K′ = Q−⌊Q/L⌋.3.3.2 Matrix-Analytic Solution for Steady State DistributionsWith the system described by a QBD type Markov chain whose block matrices are derivedin the previous subsection, we can now apply matrix-analytic method [21] to find its steadystate distributions. From these steady state probability distributions, we can derive thesteady state probability vectorsπ = [π0,π1,π2,···,πQ] for queue lengths in the buffer.For the detailed procedure to calculateπ, we refer readers to [21].3.3.3 Derivation of Performance MeasuresAfter obtaining the state vector, we can determine the performance measures of interest.We are mainly interested in the following four important performance measures: queuelengthdistribution,packetlossrate,averagethroughput,andthedistributionofaccessdelayfor packets belonging to the target queue. We denote by access delay the time betweenthe moment a packet arrives at the queue and the moment the packet gets access into themedium for transmission. All these performance measures are assumed to be obtainable atthe MAC layer.100Queue Length DistributionThe marginal probability p(ℓ) of finding ℓ packets in the queue at an arbitrary time instantcan be written as:p(ℓ) =πℓ1,1≤ℓ≤Q. (3.28)Delay DistributionThe delay distribution for a packet belonging to the tagged user queue is derived by con-sidering an absorbing Markov chain. The chain initializes from the state when a packetarrives the corresponding queue and gets absorbed in the states associated with the trans-mission of the packet. Note that, in this case, there is no arrival in that particular queuewhile the process moves towards the absorbing state. Therefore, the transition matrix Pabsof the chain can be constructed by setting α0 = 1 and αi = 0 (1 ≤ i ≤ N). Thenext step for finding the delay distribution is to determine the initial probability vector forthis absorbing Markov chain. To this end, we first consider the probability vector asso-ciated with the number of packets including the arriving packet and the packets waitingahead of it in the queue for service as seen by the arriving packet. This probability vectorξ(0) =[ξ(0)0 ,ξ(0)1 ,···,ξ(0)Q+N]can be derived as:101ξ(0)h =0, h = 011−α0[h∑i=1i∑j=1L∑k=0αii πh−j+kU(k) + N∑i=h+1h∑j=1L∑k=0αii πh−j+kU(k)],1≤h≤N11−α0[N∑i=1i∑j=1L∑k=0αii πh−j+kU(k)], N < h≤Q−L + 111−α0[N∑i=1i∑j=1Q−h+j∑k=0αii πh−j+kU(k)], Q−L + 1 < h≤Q11−α0[N∑i=h−Qi∑j=h−QQ−h+j∑k=0αii πh−j+kU(k)], Q < h≤Q + N(3.29)Note that the packets which find their destination queues full upon arrival are not admit-ted into the system. The probability that an arriving packet finds the corresponding queuefull can be written aspfull =N∑i=1ξ(0)Q+i. (3.30)Since we consider the delay experienced by the admitted packets only and since an ar-riving packet seeing a full queue will be dropped, the initial probability vector ω(0) =[ω(0)0 ,ω(0)1 ,···,ω(0)Q]of the absorbing Markov chain is derived from the above probabilityvectors as follows:ω(0)i = ξ(0)i1−pfull,0≤i≤Q. (3.31)102After d time slots the state vector of the absorbing chain isω(d) =ω(0)P<d>abs (3.32)whereP<d>abs is the transition matrix derived by multiplyingPabs with itself d times.We can then write the cumulative distribution function (cdf) of the packet delay D asFD(d) =ω(d)0 1 (3.33)Packet Loss Rate and Average ThroughputA packet loss occurs when a packet finds the queue full upon arrival or when a packet isreceived in error in the receiver. Assuming that no error recovery protocol (e.g., ARQ) isused, the packet loss rate, ploss can be found as follows:ploss = 1−(1−pfull)(1−PER). (3.34)Once the packet loss rate is derived as above, the average throughput η in packets pertime slot can be calculated as follows:η = λ(1−ploss). (3.35)3.4 Numerical Results and DiscussionsThe main objective of the analytical model developed in this chapter is to facilitate a bettercross-layer system design. Two types of system parameters can be involved in the design103process. The operating environment such as fading conditions may determine the valuesfor a number of system parameters. On the other hand, some system parameters such asnumber of admitted users can be tunable to obtain different levels of performance from thesystem. To this end, we run the model to obtain numerical results relating the obtainableQoS measures to different values of system parameters, both pre-determined and tunable,for the MIMO system in consideration. Since our primary interest lies in the cross-layeraspects of the system design, the performance measures of interest were mainly relevantto the MAC layer whereas the system parameters were mainly chosen from the physicallayer. For the sake of completeness, we also consider traffic model parameters as well asthe number of users in the system in our analysis.Since we assume a homogeneous system, we tag one of the users in the system andevaluate the performance measures from its perspective. The frame duration, packet sizeand target packet error rate are assumed to be Tf = 2 ms, Lp = 1080 bits, and PER = 1%respectively. We assume a four-state FSMC model for the subchannels associated with thetransmit antennas. In addition, the following parameter values are assumed in general, butare changed when their individual effects are evaluated. Number of transmit and receiveantennas are assumed to be t = 2 and r = 2 respectively. The average transmit SNR ateach transmit antenna, transmit antenna correlation coefficient and Doppler spread are setto γ0 = 10 dB, ρ = 0.1 and fd = 15 Hz respectively. A mix of five homogeneous usersin the system with a packet arrival probability given byα= [0.4,0.4,0.1,0.1] and a buffersize of Q = 50 packets are assumed. The values of other important parameters are listed inthe relevant subsections below. We used MATLAB to code and execute the different stepsin the development of the queuing model. The numerical results are discussed below.1040 20 40 60 80 100 120 140 16000.10.20.30.40.50.60.70.80.91d(time slots)Pr(delay≤d) t=1,r=4t=2,r=2t=2,r=3t=2,r=4t=4,r=4Figure 3.1: Packet delay distribution for different number of transmit and receive an-tennas (fd = 15 Hz, γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1])Table 3.1: Throughput and packet loss performance for different number of trans-mit and receive antennas (fd = 15 Hz, γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1])Rx Antennas Tx Antennas Avg. Throughput Packet Loss (%)(pkts/slot)4 1 0.5 43.934 2 0.879 0.954 4 0.89 0.113 2 0.883 1.452 2 0.79 5.933.4.1 Effect of Number of Transmit and Receive AntennasThe number of transmit antennas directly affects the multiplexing gain from a V-BLASTMIMO system. On the other hand, the number of transmit and receive antennas both affecttheachievablediversityinaV-BLASTsystem. Boththemultiplexingandreceiverdiversitygain are likely to effect how fast a user device can transmit or receive data. We vary the105number of transmit antennas in the base station and the number of received antennas at theuser end to see the effect of the number of transmit and receive antennas on MAC layerperformance measures.Fig. 3.1 shows the effect on the delay distribution when the number of transmit andreceive antennas are varied. The effect on packet loss rate and throughput is shown in Ta-ble 3.1. We observe that the delay performance improves significantly when we increasethe number of transmit antennas from one to two keeping the number of receive antennasfixed at four. With only a single transmit antenna at the base station, the downlink queue ofa particular user shows poor packet loss rate and throughput performance as well. This ob-servation suggests that the probability of the transmit antenna being assigned to the taggeduser is much less than sufficient to clear the backlogs created in the queue. Two transmitantennas, at the base station means the user will have access to data transfer when any ofthese antennas is assigned to it. This greatly improves the downlink queue’s chance of get-ting access to transmission at a given time slot. The packet loss rate drops sharply to only0.95%withtwotransmitantennas, whichindicatesthattheaccessprobabilityisalmostsuf-ficient to clear the backlog at the downlink queue. The improvement in the throughput anddelay performance can be similarly explained. Although increasing the number of transmitantennas from two to four shows better performance, the improvement is less pronounced.Similar observations can be made for throughput and packet loss rate experienced by theuser. This simply indicates that the QoS improvement in the MAC is not linear with theincreasing number of transmit antennas.We also vary the number of receive antennas keeping the number of transmit anten-nas fixed at two. We see a moderate level of performance improvement in terms of delay,packet loss rate and throughput when the number of receive antennas are increased from106two to three. The performance gain can be seen to diminish significantly when the numberof receive antennas is increased from three to four. We can conclude that increase in per-formance by the addition of further receive antennas is markedly less for each additionalantenna.For a given system setup and for specific system parameter values, the above observa-tions imply that going beyond a certain number of transmit or receive antennas may notbe beneficial from the QoS perspective. Moreover, antennas are expensive to deploy andincreasing their numbers can come with a steep price tag. The queuing model thus offers anobjective way to find a tradeoff between the cost associated with the increased number an-tennas and the improvement achievable in the MAC layer performance for a given systemsetup.3.4.2 Effect of Transmit Antenna CorrelationFrom (3.3), we see that the transmit antenna correlation coefficients are factored into thereceived SNR from the independent subchannels associated with the transmit antennas.Transmit antenna correlation reduces available multiplexing gain; in equation (3.3) the ef-fect is reflected in the reduction of received SNR at the subchannel associated with eachtransmit antenna. On the other hand, the independent stream scheduler is designed to allo-cate the antennas based on the received SNR levels. Therefore, it should be interesting tosee how the performance measures are affected by the transmit antenna correlation whenpaired with the scheduling scheme. In Figs. 3.2, 3.3, and 3.4, we consider two transmitantennas at the base station and vary their correlation to see the effect on packet delaydistribution, loss rate, and throughput respectively. We can see that increasing transmitantenna correlation negatively affects all three performance measures. The performance1070 20 40 60 80 100 120 140 16000.10.20.30.40.50.60.70.80.91d(slots)Pr(delay≤d)ρ=0.75ρ=0.1ρ=0.25 ρ=0.5Figure 3.2: Packet delay distribution for different transmit antenna correlation (fd =15 Hz, t = 2, r = 2, γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1])0 0.15 0.3 0.45 0.6 0.75 0.90102030405060708090ρPacketlossrate(%)Figure 3.3: Effect of Tx antenna correlation on packet loss rate (fd = 15 Hz, t = 2,r = 2, γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1])1080 0.15 0.3 0.45 0.6 0.75 0.90.10.20.30.40.50.60.70.80.9ρAveragethroughput(packets/slot)Figure 3.4: Average throughput for different levels of antenna correlation (fd = 15Hz, t = 2, r = 2, γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1])degradation, however, is not linear with the antenna correlation. We see in the figures thatthe rate at which the performances degrade also increases with increased correlation. Infact, the effect remains rather subdued until certain level of transmit correlation is presentand then picks up very fast. This is consistent with how the average received SNR at re-ceiver changes with varying transmit antenna correlation. When the correlation co-efficientreaches near 1.0, the high correlation causes extreme loss in received SNR resulting in avery poor transmission rates at all the subchannels. Consequently, packets take long timeto transmit and create large backlogs in the queues. As a result, very high delay and packetsloss rates are observed along with a severe throughput degradation.1090 20 40 60 80 100 120 14000.10.20.30.40.50.60.70.80.91d(slots)Pr(delay≤d)fd =5Hzfd=15Hzfd =45Hzfd =25Hzfd =35HzFigure 3.5: Packet delay distribution for various Doppler spread (t = 2, r = 2, ρ =0.1, γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1])10 20 30 40 50024681012fd (Hz)Packetlossrate(%)Figure 3.6: Packet loss rate for various fading rates (t = 2, r = 2, ρ = 0.1, γ0 = 10dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1])11010 20 30 40 500.780.80.820.840.860.880.9fd (Hz)Averagethroughput(packets/slot)Figure 3.7: Average throughput for various fading rates (t = 2, r = 2, ρ = 0.1,γ0 = 10 dB, 5 users, Q = 50,α= [0.4,0.4,0.1,0.1])3.4.3 Effect of Doppler SpreadDoppler spread has been shown to have significant performance implications in single an-tenna wireless systems exploiting multiuser diversity. Therefore, it is imperative to ex-amine this relationship in the MIMO system in our consideration. The Doppler spread isprimarily governed by the relative motion of the base station and the user mobile device.Fig. 3.5 shows that the delay distribution improves when the Doppler spread increases. Ahigher Doppler spread means less correlation over time in the subchannel associated witha particular transmit antenna. As a result, the state of the subchannel at any particular userwill change more rapidly over time. This phenomenon in conjunction with the schedulingscheme will make it less likely that a particular user can monopolize the subchannel fora long time. Our tagged user will thus have more probability of access to the subchannel.The same conclusion can be drawn for other subchannels as well. Consequently, the tagged111user will have more opportunities to reduce the backlog in its queue. A reduced backlog inthe queue implies less delay for the incoming packets. Moreover, with the less probabilityof queue size reaching the buffer limit, the packet loss rate drops and subsequently, theaverage throughput is also improved (see Figs. 3.6-3.7)3.4.4 Effect of Buffer Size, Traffic Intensity, and Number of UsersThe queuing model also allows us to investigate quantitatively the effects of buffer size,traffic characteristics as well as the number of users on the system performance. ThreedifferenttrafficarrivalpatternsAP1, AP2, andAP3werecharacterizedbythepacketarrivalprobability vectors as below:αAP1 = [0.7,0.3]αAP2 = [0.3,0.7]αAP3 = [0.3,0.5,0.2]AP1 represents an arrival pattern that has very low packet arrival probability and is non-bursty in nature. AP2 is also non-bursty, but has higher packet arrival probability in a giventime. On the other hand, although AP3 has the same packet arrival probability as that ofAP2, it introduces burstiness into the traffic.Fig. 3.8 shows the delay distribution curves for different values of buffer size and thesetraffic arrival profiles. For a given traffic profile, we should see increased packet delaywhen a larger buffer size is chosen because the backlogs in the queues can grow larger. ForAP2 and AP3, we can easily observe this behavior. For AP1, however, the effect of buffersize is observed to be very insignificant. The packet arrival probability in AP1 is very low,and therefore, the backlog tends to remain short even with a large buffer space. On the1120 10 20 30 40 50 60 70 80 90 10000.10.20.30.40.50.60.70.80.91d(slots)Pr(delay≤d)  Q=25, AP1Q=50, AP1Q=25, AP3Q=50, AP2Q=25, AP2Q=50, AP3Figure 3.8: Delay distribution for different buffer size and traffic arrival profiles (AP)(fd = 15 Hz, t = 2, r = 2, ρ = 0.1, γ0 = 10 dB, 5 users)0 20 40 60 80 100 120 140 16000.10.20.30.40.50.60.70.80.91d(slots)Pr(delay≤d)  8 users4 users12 users—– Analysiso SimulationFigure 3.9: Effect of the number of users on packet delay distribution (fd = 15 Hz,Q = 50, t = 2, r = 2, γ0 = 10 dB, ρ = 0.1, Arrival profile = AP1 )1132 4 6 8 10 12 14 16 18 200.20.210.220.230.240.250.260.270.280.29Number of usersAveragethroughput(packets/slot)Figure 3.10: MAC layer throughput for different number of users (fd = 15 Hz, Q =50, t = 2, r = 2, γ0 = 10 dB, ρ = 0.1, Arrival profile = AP1 )2 4 6 8 10 12 14 16 18 200510152025Number of usersPacketlossrate(%)  AnalysisSimulationFigure 3.11: Effect of the number of competing users on packet loss rate (fd = 15Hz, Q = 50, t = 2, r = 2, γ0 = 10 dB, ρ = 0.1, Arrival profile = AP1 )114other hand, with a fixed buffer size, traffic profile AP1 shows the best delay performanceamong the three traffic profiles. As expected, the delay increases with higher packet arrivalprobabilities associated with AP2 and AP3. However, if we compare the delay distributioncurves for AP2 and AP3, it also becomes apparent how burstiness in case of AP3 con-tributes to the increased packet delay. Bursty packet arrivals can give rise to sudden risein queue length, which can take time to clear. Consequently, delay performance is morelikely to suffer.We also investigate the effect of the number of users in the V-BLAST system in con-sideration. We consider four receive antennas and four transmit antennas with no antennacorrelation. Fig. 3.9 shows how the number of users affects the delay distribution. Asexpected, more users in the system create more competition, and therefore, longer packetdelays are experienced. Similar observations can be made for the throughput and packetloss rate performance (see Figs. 3.10-3.11).3.4.5 Validation of the Queueing ModelWe also developed a discrete-event simulator to validate the correctness of the proposedqueueing model. At each of the downlink queue that is simulated for each admitted user inthe system, packets are generated following a Batch Bernouli distribution. The V-BLASTMIMO downlink to each of these users is simulated by t (t is the number of transmit an-tennas at the base station) parallel subchannels, each of which is modeled by an FSMCparameterized by a transition probability matrix. All the parameter values related to thetraffic arrival process and FSMC channel model are chosen to be identical to the valuesused for the corresponding numerical analysis. In each time slot, the state for each sub-channel is randomly generated according to the FSMC transition probability matrix. The115simulated independent stream scheduler thenconsidersthesesubchannelstatesforallusersto determine which transmit antenna will be assigned to which user in the current time slot.Once the user selection and antenna assignment are done, the total number of packetsthat will be transmitted from the downlink queue associated with each user is determinedthrough the same AMC scheme as assumed in the queueing model. We keep the statisticson the number of packets that arrived, dropped and transmitted at each of the downlinkqueue over the entire simulation time. We also record the arrival and departure times ofeach of the transmitted packets at all the downlink queues. We simulate 100000 time slotsfor each simulation run. We present two representative sets of simulation results along withanalytical results in Fig. 3.9 and Fig. 3.11, where the delay statistics and packet loss rateperformances achieved from simulation and analytical model are compared for a taggeduser (user 1). As can be seen, the simulation and numerical results match very closely,thereby validating the correctness of our proposed queueing model.3.5 Application of the Queueing ModelThe queuing model developed in this chapter can be used for system engineering throughcross-layer design in a multiuser V-BLAST MIMO system. Some of the example applica-tions are as follows:• The model essentially draws a relationship between different system specific param-eters mainly at the physical layer and the obtainable QoS at the MAC layer. It thuscan give the operating points for these system parameters to achieve a specific QoSlevel. Resource limitations or operating environments can put constraints on the val-ues of these parameters. For example, with the given parameter values used to findthe relationship between the delay distribution and the number of transmit/receive116antennas in Fig. 3.1, two transmit and two receive antennas are sufficient to keep thepacket delay within a target delay bound of 80 ms with a 90% probability. There-fore, the model gives a design guideline on the number of antennas that should bedeployed under given resource constraints.• The model allows to gauge beforehand the level of QoS the system can entertain fora new incoming request given the resource constraints and operating environments.Therefore, the model output can also be used by base stations in QoS negotiation fornew connections or service flows. The QoS negotiation usually involves a counteroffer on the level of service that the base station can offer when a new service flowputs forward its desired QoS level when seeking entry into the system. The basestation can make use of the output from the queuing model to furnish counter offers.• The queuing model can be utilized in a model based admission controller design aswell. When a user wants to establish a new request for an application or service, theadmission controller can use the queuing model to determine whether the requiredQoS of the new and existing applications or services can be met given the numberof users with active connection already in the system. If the QoS of the requestedand existing applications or services cannot be met, the connection request may berefused or can be accepted otherwise. For example, in Fig. 3.11, with the given pa-rameter values used to find the relationship between packet loss rate and the numberof users in the system, only 14 users can be served with a target packet loss rate of5%. If the system is already serving 14 active users at some point in time, the admis-sion controller could refuse admission of a connection from a new user on the basisof the achievable packet loss rate measure determined by the queuing model output.1173.6 ConclusionsWe have developed a queuing analytic model for cross-layer analysis of downlink resourceallocation in a V-BLAST MIMO system exploiting multiuser diversity. The MIMO chan-nel in the V-BLAST system is decomposed into subchannels associated with the transmitantennas and the users are then allocated the transmit antennas opportunistically based onthe received SNR on the associated subchannels. The queuing model is developed consid-ering the system dynamics resulting from the scheduling mechanism, fading in the MIMOchannel, and the traffic arrival process. The transmit antenna correlation in the base stationand the possibility of bursty traffic arrival are also factored into the model. After devel-oping the queuing model, we elaborate the steps to compute important QoS performancemeasures including the delay distribution, throughput, and packet loss performance at theMAC layer. We also present selected numerical results that show cross-layer effects ofthe physical layer parameters as well as the effects of the traffic arrival statistics and thenumber of users in the system on the MAC layer performance. The queuing model hasimportant applications in the QoS provisioning framework for a V-BLAST MIMO systemas the model output can be used in admission control, QoS negotiation and setting propervalues for QoS relevant parameters.1183.7 Bibliography[1] G. Foschini and M. J. Gans, “On Limits of Wireless Communication in a Fading Envi-ronment when using Multiple Antenna Arrays,” Proc. Wireless Personal Communica-tion, vol. 6, pp. 311-335, Mar. 1998[2] P. W. Wolniansky, G. J. Foschini, G. D. Golden, and R. A. Vlenzuela, “V-BLAST: AnArchitecture for Realizing Very High Data Rates Over the Rich-Scattering WirelessChannel,” Proc. URSI International Symposium on Signals, Systems, and Electronics,Pisa, Italy, Sept. 1998.[3] D. N. C. Tse, “Optimal Power Allocation over Parallel Gaussian Broadcast Chan-nels,” Proc. IEEE International Symposium on Information Theory, Ulm, Germany,Jul. 1997.[4] R. W. Heath, Jr., M. Airy, and A. J. Paulraj, “Multiuser Diversity for MIMO WirelessSystems with Linear Receivers,” Proc. Asilomar Conference on Signals, Systems andComputers, Pacific Grove, CA, Oct. 2001.[5] C.-J. Chen and L.-C. Wang, “Performance Analysis of Scheduling in Multiuser MIMOSystems with Zero-Forcing Receivers,” IEEE Journal on Selected Areas in Communi-cations, vol. 25, no. 7, pp. 1435-1445, Sept. 2007.[6] T. Yoo and A. Goldsmith, “On The Optimality Of Multiantenna Broadcast SchedulingUsing Zero-Forcing Beamforming,” IEEE Journals on Selected Areas in Communica-tions, vol. 24, no. 3, pp. 528-541, Mar. 2006.119[7] M. Airy, R. W. Heath and S. Shakkottai, ‘Multi-User Diversity For The Multiple An-tenna Broadcast Channel With Linear Receivers: Asymptotic Analysis,” Proc. Asilo-mar Conference on Signals, Systems, amd Computers, pp. 886-890, Nov. 2004.[8] W. Rhee and J. M. Cioffi, “On the Capacity of Multiuser Wireless Channels with Mul-tiple Antennas,” IEEE Transactions on Information Theory, vol. 49, no. 10, pp. 2580-2595, Oct. 2003.[9] C.-J. Chen and L.-C. Wang, “A Unified Capacity Analysis for Wireless Systems withJoint Antenna and Multiuser Diversity in Nakagami Fading Channels,” Proc. IEEEInternational Conference on Communications, Paris, France, Jun. 2004.[10] L.B.LeandE.Hossain,“OnthePerformanceofSpatialMultiplexingMIMOCellularSystems with Adaptive Modulation and Scheduling,” Proc. IEEE Wireless Communi-cations and Networking Conference, Atlanta, USA, Mar. 2004.[11] E. S. Lo, P. W. C. Chan, V. K. N. Lau, R. S. Cheng, K. B. Letaief, R. D. Murch, andW. H. Mow, “Adaptive Resource Allocation and Capacity Comparison of DownlinkMultiuser MIMO-MC-CDMA and MIMO-OFDMA,” IEEE Transactions on WirelessCommunications, vol. 6, no. 3, pp. 1083-1093, Mar. 2007.[12] K. K. Wong, R. D. Murch, and K. B. Letaief, “Performance Enhancement of Mul-tiuser MIMO Wireless Communication Systems,” IEEE Transactions on Communica-tions, vol. 50, no. 12, pp. 1960-1970, Dec. 2002.[13] P. Tejera, W. Utschick, G. Bauch, and J. A. Nossek, “Subchannel Allocation in Mul-tiuser Multiple-Input-Multiple-Output Systems,” IEEE Transactions on InformationTheory, vol. 52, no. 10, Oct. 2006.120[14] O.-S. Shin and K. B. Lee, “Antenna-Assisted Round Robin Scheduling for MIMOCellular Systems,” IEEE Communications Letters, vol. 7, no. 3, pp. 109-111, Mar.2003.[15] G. Aniba and S. Aissa, “Adaptive Scheduling for MIMO Wireless Networks: Cross-Layer Approach and Application to HSDPA,” IEEE Transactions on Wireless Commu-nications, vol. 6, no. 1, pp. 259-268, Jan. 2007.[16] M. Airy, S. Shakkottai, and R. W. Heath, Jr., “Limiting Queuing Models for Schedul-ing in Multi-User MIMO Wireless Systems,” Proc. IASTED Conference on Communi-cations, Internet & Information Technology, Scottsdale, USA, Nov. 2003.[17] Q. Liu, S. Zhou, and G. B. Giannakis, “Queuing with Adaptive Modulation and Cod-ing Over Wireless Link: Cross-Layer Analysis and Design,” IEEE Transactions onWireless Communications, vol. 4, no. 3, pp. 1142- 1153, May 2005.[18] G. J. Foschini, D. Chizhik, M. Gans, C. Papadias and R. A. Valenzuela, “Analysis andperformance of some basic spacetime architectures,” IEEE Journals on Selected Areasoin Communications., vol. 21, pp. 303-320, Apr. 2003.[19] D. Gore, R. W. Heath, Jr., and A. J. Paulraj, “On Performance of the Zero ForcingReceiver in Presence of Transmit Correlation,” Proc. IEEE International Symposiumon Information Theory, Lausanne, Switzerland, Jul. 2002.[20] H. S. Wang and N. Moayeri, “Finite-State Markov Channel-A Useful Model forRadio Communication Channels,” IEEE Transactions on Vehicular Technology, vol.44, pp. 163-171, Feb. 1995.121[21] M. F. Neuts, Matrix geometric Solutions in Stochastic Models: An Algorithmic Ap-proach. Baltimore, MD: John Hopkins Univ. Press, 1981.122Chapter 4Controlled Channel Access Schedulingfor Guaranteed QoS in 802.11e-BasedWLANs14.1 IntroductionWireless Local Area Network (WLAN) technology offers a simple, cost effective, andflexible solution to ubiquitous wireless access in homes, offices, campuses, hospitals etc.With the surging popularity of WLANs, multimedia applications such as voice, streamingaudio/video, network gaming, teleconferencing are going to be widely deployed and sup-ported in WLANs. These applications require certain Quality of Service (QoS) support fortheir smooth operation. However, the current WLAN technology standardized in the IEEE802.11 standard lacks this QoS support. The IEEE 802.11e standard [1] aims to offer this1A version of this chapter has been published. Rashid, M.M., Hossain, E. and Bhargava V.K. (2008) Con-trolled Channel Access Scheduling for Guaranteed QoS in 802.11e-Based WLANs. IEEE Trans. WirelessCommun., 7(4):1287–1297123QoS support to the 802.11-based WLANs. The 802.11e introduces the Hybrid Coordina-tion Function (HCF) that offers two medium access control (MAC) mechanisms, namely,Enhanced Distributed Channel Access (EDCA) for prioritized QoS and HCF ControlledChannel Access (HCCA) for parameterized/guaranteed QoS.Most of the multimedia applications require hard QoS requirements that could only beprovided through the HCCA mechanism instead of EDCA which is able to only provide a“soft” or “relative” QoS. HCCA is a polling based mechanism in which the Hybrid Con-troller (HC) collocated with Access Point (AP) grants the transmission opportunities tothe contending traffic streams generated from these applications. However, the HC has toproperly schedule the granting of the transmission opportunities in order to provide theseapplications with their pledged QoS. Moreover, the HC should not grant admission to thosetraffic streams for which it cannot provide the required QoS. The standard provides a refer-ence scheduler design along with the design of an admission controller unit to complementthe HCCA scheme. Many multimedia applications such as real-time multimedia stream-ing, videoconferencing, and network gaming produce Variable Bit Rate (VBR) traffic. Thepackets are generated in variable intervals with fluctuating packet sizes. This type of trafficposes significant challenge to the HCCA scheduler due to their time-varying nature. Al-though the transmission opportunities could be granted according to the expected bit rateand required service intervals, the traffic might be generated at much higher or lower ratesat times.In this chapter, first, we develop a queueing model to analyze the performance of thereference scheduler in HCCA that captures the traffic dynamics from a VBR multimediasource. We model the system as a vacation queue with general arrival and service pro-cesses. Then matrix-analytic method [2] is applied to solve the queueing model and derive124the performance measures of interest including the access delay statistics. Although EDCAhas been the focus of a number of analytical studies (e.g. [3, 4, 5]), there has been no ana-lytical framework proposed in the literature so far for HCCA. The analytical model in thischapter reveals some interesting performance behaviors that point out the problems withthe reference HCCA scheduler. Then, based on the insights obtained from the performanceanalysis, we design the prediction and optimization-based HCCA (PRO-HCCA) schedulerwhich can solve these performance problems and enable HCCA to meet the desired QoSguarantees.The rest of the chapter is organized as follows. Section II provides background on theIEEE 802.11e standard and the HCCA mechanism along with the reference HCCA sched-uler design. We develop and analyze a queueing model for the HCCA reference schedulerin Section III. Section IV presents the proposed PRO-HCCA scheduling algorithm and itsimplementationaspectsinaIEEE802.11enetwork. Theperformanceevaluationresultsforthe PRO-HCCA scheduler in a simulated IEEE 802.11e WLAN are presented in Section V.Section VI states the conclusions.4.2 Background4.2.1 Overview of HCCAThe HCCA mechanism, which improves over the Point Coordination Function (PCF) oflegacy 802.11 MAC, is a polling based mechanism where the access to the medium isarbitrated centrally. However, it resolves the limitation of PCF by eliminating the unpre-dictability of beacon delays arising from incompatible cooperation between ContentionPeriod (CP) and Contention Free Period (CFP) [6]. Note that, since PCF is unable to guar-125anteethetransmissiontimesofthepolledstations,itisnotaviablesolutionforQoSsupportin 802.11-based WLANs.IEEE 802.11e introduces the concept of Traffic Stream (TS) which can be thought ofas a set of data units (MSDU) that has to be delivered conforming to a correspondingTraffic Specification (TSPEC). A TSPEC characterizes the traffic streams and its QoS re-quirements. A TSPEC negotiation takes place between a QoS Station (QSTA) and theHC collocated with the QoS Access Point (QAP) before a TS can be served through theHCCA. The TSPEC parameters which are considered during the negotiation include nomi-nal MSDU size in octets, mean data rate in bps, Maximum Service Interval (MaxSI) whichis the maximum interval in micro seconds (µs) between two successive polls for the stream,minimum PHY rate in bps, and delay bound in µs. Once the TSPEC negotiation is suc-cessful, the TS is admitted and offered transmission opportunities (TXOPs) by the HC ineach polling cycle. The length of the TXOPs offered to the stream is decided through ascheduling scheme. The periods in which the HC has the exclusive control of the chan-nel for data transmission are called Controlled Access Periods (CAPs). The HC polls theQSTAs during these CAPs and offers TXOPs to the admitted streams.4.2.2 Reference HCCA Scheduler DesignThe scheduler first determines a Scheduled Service Interval (SI), which is the time intervalused by the QAP to periodically poll each non-AP QSTA that has one or more streamsadmitted by the admission controller. The SI is calculated as a number which is smallerthan all the MaxSIs of the admitted streams and a submultiple of the beacon interval. Anyadmitted stream will be able to get a TXOP at the end of each SI. The idea is to provideeven the most QoS constrained stream with at least one TXOP within its MaxSI time limit.126Figure 4.1: TimingdiagramforthereferenceHCCAschedulershowingdifferenttim-ing periods and their relationships within a beacon interval having two SI peri-ods.The scheduler then determines the TXOP duration needed for each stream by consideringthe number of packets that may arrive within an SI. The TXOP for an admitted TS i in aQSTA is calculated as follows:TXOPi = max(Gi×SiR + X, ZR + X) (4.1)where Gi is the number of MSDUs arrived in the QSTA at mean data rate λi during theSI and can be calculated from Gi = ⌈SI×λiSi ⌉, Si is the nominal MSDU size, R is thephysical transmission rate, Z is the maximum allowable size of MSDU, and X denotes theoverhead (which includes inter-frame spaces, acknowledgements and polling frames) intime unit. Fig. 4.1 shows the channel timing diagram encompassing a beacon period in anHCCA enabled 802.11e WLAN with the reference HCCA scheduler in operation, where kin the figure is number of scheduled stream.4.3 Queueing Model and Analysis for the ReferenceHCCA SchedulerIn this section, we develop and analyze a queueing model for the IEEE 802.11e HCCAwhen coupled with the reference HCCA scheduler. We analyze the QoS performance of127the admitted traffic streams which would enable us to see the effectiveness of the HCCAreference scheduler in providing guaranteed QoS in a IEEE 802.11e WLAN. We assumethat each stream is queued in a buffer that can accommodate a limited number of packets.4.3.1 Formulation of the Queueing ModelThe QAP maintains separate queues for the downlink traffic streams, whereas each of theQSTAs maintains separate queues for its uplink traffic streams. Through the schedulingoperation, each of these TS queues are assigned a TXOP in each SI. The HC polls thequeues during these TXOPs when queued packets are transmitted to their destinations.From the perspective of any of these queues, the HC acts like a server that serves the queuefor a preassigned TXOP time with the service rate proportional to the channel data rateand then goes for a vacation before serving it again. The duration of the vacation is the SIperiod calculated during the scheduling process. In the analysis, without loss of generality,we focus on a particular VBR traffic stream and consider its queue as the target queue.Pleas note that we develop a discrete-time queueing model and therefore, assume thattime is slotted with a pre-defined slot duration. In rest of the analysis, the time-relatedparameters such as TXOP, SI should thus be interpreted in terms of this slot duration.Arrival and Service ProcessesIn order to model packet arrivals into the target queue, we consider the VBR nature ofthe traffic source. Unlike a CBR source, packets are generated from a VBR source atrandom intervals. However, the distribution of these packet inter-arrival times dependson the characteristics and parameters associated with the traffic source (video, audio etc.).To generalize the arrival process, we use a discrete phase-type distribution [2] to modelthe inter-arrival times. The phase-type distribution for inter-arrival time is represented by128(α,U,M1), where M1 is the number of transient phases of the absorbing Markov chaindescribing the distribution, α is the initial probability vector of order M1, and U is thetransition matrix among the transient phases. The mean inter-arrival time is 1λ=α(IM1 −U)−1eM1, where λ is the rate of packet arrival, Ij represents an identity matrix of orderj, and ej is a column vector of order j containing only 1s. The column vector for thetransitions to absorption phase is eU = eM1−UeM1.To model the service process, we follow a similar approach. The variable-length pack-ets generated from a VBR source when added with fixed length headers form variablelength MAC layer frames. Once the opportunity to transmit arrives, a MAC frame is trans-mitted at the channel using a fixed data rate. We assume that rate adaptation algorithmssuch as auto rate fall back [7] are not implemented. The 802.11e protocol requires thatthere be a SIFS time gap between the reception of a poll or acknowledgement (ACK) andthe start of the next packet transmission. Therefore, a SIFS period and an ACK durationof TACK have to be added to the packet transmission time. Let us denote the length ofa packet as LP. For a typical video transmission over UDP, the MAC layer header con-sists of RTP, UDP, IP, MAC protocol headers, whose lengths are denoted by LRTP, LUDP,LIP, LMAC, respectively. Moreover, a PLCP header transmission time TPLCP is added bythe physical layer. Therefore, the total transmission time of the packet can be written asTtotal = LP+LlayerR +TPLCP +SIFS+TACK, whereLlayer = LRTP +LUDP +LIP +LMACand R is the channel data rate. Assuming that the header size, channel data rate, the SIFS,PLCP, and ACK durations are fixed, the transmission time is a random variable whichvaries with the length of the packet.The distribution of the transmission time of a packet (i.e., service time) is modeledas a phase-type distribution. It is represented by (β,S,M2), where M2 is the number of129transient phases of the absorbing Markov chain describing the distribution,β is the initialprobability vector of order M2, and S is the transition matrix among the transient phases.The column vector for the transitions to absorption phase is eS = eM2−SeM2.Mapping into a Vacation Queue ModelFrom the perspective of the target queue, the system can be modeled as a time-limitedPh/Ph/1 vacation queueing system, where “Ph” stands for phase-type distribution, the timelimit is the TXOP duration and the vacation period is the SI period. T Note that in therest of our analysis, we use the term “server” as an abstraction of HC with a service rateproportional to the channel data rate and the term “service completion” of a packet as theend of transmission of the packet in the channel.Although the server has the maximum limit of TXOP allowed to serve the queue inone round, it can leave the queue before TXOP if the queue becomes empty. In suchscenarios, the HC will poll the next TS in its polling list. The duration of the vacation isthe SI period and the system is of multiple vacation types. We represent the deterministicvacation period SI by a phase-type distribution (δ,V,SI), whereδ = [1,0,0,···,0| {z }SI] andV = 0 ISI−10 0. The phase-type distributions for the inter-arrival and the serviceprocesses can be fitted from their known distributions or the traces of inter-arrival timesand the lengths of the incoming packets.4.3.2 Markov Chain AnalysisWe analyze the Markov chain describing the queueing model above by adopting a matrix-analytic method [8]. Letθj(i) denote the ith column of Ij andθ′j(i) denote the transpose130of θj(i). Let e (when used without a subscript) represent a column vector of appropriateorder (equal to the number of columns of the matrix that it is multiplied with) consisting ofonly 1s,Hk represent 0 Ik−10 0, and⊗denote the Kronecker product.The discrete-time Markov chain (DTMC) describing the model has state space Ψ =ΨV ∪ΨS, where ΨV is the state space of the system when the server is in vacation andΨS is the state space when the server is serving the target queue. The state space ΨV andΨS can further be described by considering the number of packets in the queue, the timeelapsed in the current visit of the server, the phase of the arrival process, and the phase ofthe service when the server is serving or the phase of the vacation when the server is invacation i.e. serving other queues. We can writeΨV ={(xn,an,vn)|0≤xn≤q,1≤an≤M1,1≤vn≤SI}ΨS ={(xn,yn,an,sn)|0≤xn≤q,1≤yn≤TXOP,1≤an≤M1,1≤sn≤M2},where xn is the number of packets in the queue, q is the buffer size in number of packets,yn is the time elapsed during the current visit of the server and sn is the phase of the serviceif the server is serving the queue, an is the phase of the arrival process, vn is the phase ofthe vacation if the server is in vacation at time n.LetPdenote the transition matrix of the DTMC. Since more than one arrival or servicecompletion cannot take place in a single time slot, it is straightforward to see that thetransition matrix P will have the following structure of a quasi-birth-and-death (QBD)131processP =B0 B1B2 A1 A0A2 A1 A0... ... ...A2 A1 A0A2 A1q. (4.2)By considering the possible state transitions when the queue is empty, the block matri-cesB0 andB1 can be written asB0 = U⊗(V+ eVδ) (4.3)B1 =[(eUα)⊗V θ′txop(1)⊗(eUα)⊗(eVδ)](4.4)BlockmatrixB2 representstransitionsinwhichnumberofpacketsinthequeuechangesfrom 1 to 0. The server goes for vacation if the queue becomes empty regardless of the timespent in the current visit. We, therefore, can writeB2 = 0etxop⊗U⊗δ⊗eS. (4.5)On the other hand, block matrixA2 contains the transitions corresponding to the reduc-tion in the number of packets in the queue by 1. If the time spent in the current visit to thequeue has reached the TXOP allocated for the queue, the server leaves the queue for other132queues i.e. the server enters another vacation period. Consequently,A2 = 0 0θtxop(txop)⊗U⊗δ⊗eS Htxop⊗U⊗(eSβ). (4.6)Whennoservicecompletionorarrivaloccursinatimeslot,thenumberofpacketsinthequeue will not change. However, the phase of service may change for the packet currentlyin service (if the server is currently serving the queue) or the phase of server in vacationmay change (if the server is in vacation). In addition, the server will go to vacation if TXOPtime has already elapsed in the current visit. Block matrixA1 contains these transitions andthus can be written asA1 = U⊗V θ′txop(1)⊗U⊗(eVβ)Asv1 Ass1 (4.7)where Asv1 = θtxop(txop)⊗(U⊗δ⊗eM2 + (eUα)⊗δ⊗eS) and Ass1 = Htxop⊗(U⊗S+ (eUα)⊗(eSβ)).The boundary block matrix A1q can be found out by replacing U by U + eUαin A1.This is because when the buffer is full, a new packet arrival will not increase the bufferlength (i.e. the new packet will be dropped).Since there cannot be more than one arrival or service completion within a time slot,the number of packets in the queue can only increase if there is a new arrival and no servicecompletion in the time slot. Considering the possible transitions, we can writeA0 asA0 =(eUα)⊗V θ′txop(1)⊗(eUα)⊗(eVβ)Asv0 Htxop⊗(eUα)⊗S (4.8)133where Asv0 =θtxop(txop)⊗(eUα)⊗δ⊗eM2.4.3.3 Matrix-Analytic Solution for Steady State DistributionsWith the system described by a QBD type chain whose block matrices are derived in theprevious subsection, we can now apply matrix-analytic method [2] to find its steady statedistributions. Thedistributionsarerepresentedbyasteadystatevectorπ = [π0,π1,π1,···,πq],which satisfiesπP = π and ∑qi=0πie = 1. We can use the boundary and the normaliza-tion conditions to find the vectorsπ0,π1,···,πq. For the detailed procedure to calculateπ, please see [2].4.3.4 Performance MeasuresTheperformancemeasuresincludingqueuelengthdistributionattheendofaTXOP,packetlossrate, anddistributionofaccessdelayforthepacketsfromtheVBRtrafficsourcecanbedetermined based on the state vector. We assume that the steady state vectorπi,0≤i≤qis partitioned as [πvi,πsi,1,πsi,2,···,πsi,txop].Queue Length DistributionThe objective of the reference scheduler for HCCA is to leave a queue empty at the end ofevery visit to the queue. Therefore, it is interesting to find out the distribution of the queuelength at the end of a TXOP to see how successful the scheduler is to meet this objective.The marginal probability of finding l packets in the queue at the end of a TXOP can bewritten as fLtxop(ltxop) = πl,txope, 0≤ltxop ≤q, where fLtxop(ltxop) is the pmf of queuelength at the end of a TXOP.134Packet Loss RateWhen a packet arrives at the queue which has reached its limit, the newly arrived packetwill be lost in two scenarios. In the first scenario, the server is in vacation. In the secondscenario, the server is serving the queue but no service completion occurs with the newarrival. Therefore, packet loss rate Ploss can be written as follows:Ploss = 1λ[(πvq((eUα)⊗V))e+(πsq,txop((eUα)⊗δ⊗eM2))e+(txop−1∑i=1πsq,i((eUα)⊗S))e].(4.9)Access Delay DistributionAccess delay is the time between the moment a packet arrives at a station and the momentthe packet gets access into the medium for transmission. The access delay distribution fora packet from the target stream is derived by considering an absorbing Markov chain. Thechain initializes from the state when the packet arrives at the corresponding queue and getsabsorbed when the packet reaches the head of the queue. Note that, in this case, there isno arrival in that particular queue while the process moves towards the absorbing state.Therefore, the transition matrix Pabs of the chain can be constructed by setting U = 1and eUα = 0. The next step for finding the delay distribution is to determine the initialprobability vector for this absorbing Markov chain. This vectorγ = [γ0,γ1,γ2,···,γq]can be found by considering the steady state vector of the system as seen by an arrivingpacket and then summing up the probabilities due to the phases of any new arrival. We canpartitionvectorγi,0≤i≤q asγi = [γvi,γsi,1,γsi,2,···,γsi,TXOP], whichcanbecomputedas follows:135γv0 = 1λ[πv0((eUα)⊗(V + eVδ))+TXOP∑y=1πs1,y((eUα)⊗(eSβ))](eM1⊗ISI)(4.10)γvi =1λ[πvi((eUα)⊗V) +πsi,TXOP((eUα)⊗δ⊗eM2) +πsi+1,TXOP((˜Uα)⊗δ⊗S)](eM1⊗ISI)(4.11)γsi,1 = 1λ[πvi((eUα)⊗(eVβ))](eM1⊗IM2) (4.12)γsi,y = 1λ[πsi,y((eUα)⊗S)+πsi+1,y−1((eUα)⊗(eSβ))](eM2⊗ISI). (4.13)After d time slots the state vector of the absorbing chain is γ(d) = γPdabs. Assumingthat γ(d) can be partitioned as γ(d) = [γ(d)0 ,γ(d)1 ,γ(d)2 ,···], we can write the CumulativeDistribution Function (CDF) of the access delay D asFD(d) = Pr{D≤d}=γ(d)0 e. (4.14)Figs. 4.2 and 4.3 show typical numerical results obtained from the analytical modelusing real VBR traffic traces. We consider a video traffic stream admitted in a QSTA of a802.11e WLAN. The real traffic trace was collected using VIC videoconferencing tool [9]and H.261 coding in QCIF format. The mean sending rate, average packet size, and mean1360 100 200 300 400 500 600 700 800 900 100000.10.20.30.40.50.60.70.80.91d(ms)Pr(accessdelay≤d)Figure 4.2: Cumulative distribution function of access delay (ms) derived from theanalytical model.0 5 10 15 20 25 30 35 40 450.10.20.30.40.50.60.70.80.91l (packets)Pr.(queuelength≤l)Figure 4.3: Cumulative distribution function (derived from the analytical model) ofqueue length at the end of a TXOP.137packet inter-arrival time computed from the trace are 200 kbps, 687 bytes, and 26 ms,respectively. The maximum service interval, delay bound, and mean data rate in the QoSspecification are set to be 50 ms, 100 ms, and 20 kbps, respectively. The physical layer con-forms to the 802.11a standard. We selected 36 Mbps as the PHY data rate (802.11a offersdata rates: 6, 9, 12, 18, 24, 36, 48, or 54 Mbps). For the analysis, we assume that the SI pe-riod after considering the maximum service intervals needed by the admitted traffic streamsis 50 ms. The TXOP duration is then calculated by using (4.1). We collect the inter-arrivaland the packet size information from the VBR traffic trace. The individual packet sizesare then converted to corresponding transmission times (i.e. service times) considering thedifferent header sizes and the physical layer transmission rate. The inter-arrival and servicetimes are then fitted to discrete phase-type distributions using the PhFit [10] program. Wethen run our analysis using Matlab.The CDF of access delay for the VBR video traffic is plotted in Fig. 4.2. It showsthat the access delay fails to remain under the delay requirement (100 ms) for 50% of thepackets. Moreover, there remains a significant chance of some packets’ suffering excessivedelays (over 500 ms).The observations suggest that a large number of packets remain in the queue for aduration much longer than the MaxSI time interval. In an ideal scenario, the queue of theVBR stream should become empty at the end of TXOPs, because the scheduler is designedto allocate enough TXOP to transmit all the packets within the scheduled SI. However,Fig. 4.3 shows for the VBR stream the probability that the queue is empty at the end ofthe TXOPs is rather very low (about 15% only). The packets remaining in the queue aftera TXOP must have to wait another one or more scheduled SIs. This accumulated backlogmight further add to the delay of the packets arriving during the next SIs in addition to the138delays caused by the insufficient TXOPs. The backlog eases up when packets arrive at arate lower than the expected rate for some period of time. However, a significant numberof packets eventually end up experiencing high access delays due to the queue buildup.Now let us assume that a similar stream is generated from the same traffic trace andis simultaneously admitted through another QSTA. The stream, however, demands a lessstricter access delay bound of 300 ms and a maximum service interval of 150 ms. Dueto the presence of lower MaxSI values of other admitted streams the SI period remains50 ms. Obviously, the plot of the CDF of access delay will be the same as in Fig. 4.2.However, it also means that percentage of packets failing to meet the access delay boundhas reduced from 50% to 40%; the former is the percentage of packets failing to meetthe deadline for the same stream with a stricter delay bound of 100 ms. This observationcan be explained if we consider that the reference scheduler treats the admitted streamssimilarly by serving them with similar urgencies in equal intervals. Consequently, streamswith stricter delay bounds are penalized more when backlogs buildup at the end of TXOPsand higher percentage of their packets fail to meet the delay requirement.4.4 The Prediction and Optimization-Based HCCA(PRO-HCCA) SchedulerThe PRO-HCCA scheduler avoids the reference scheduler’s problem of unduely penalizingthe more delay constrained packets. This is due to the fact that the reference schedulertreats the streams having different delay requirements with equal priority. Therefore, inthe PRO-HCCA scheduler we introduce an accounting mechanism to treat packets fromdifferent streams according to their urgencies for service. Another idea here is to minimizethe backlog that contributes to unwanted delay at the end of TXOPs. This is achieved in139PRO-HCCA scheduler by using a proper prediction mechanism to account for the dynamicintensity of VBR traffic and then finding an optimal allocation of available transmissiontime among the competing traffic streams. The optimal allocation strives to strike a balancebetween the urgencies of services for different traffic streams and the available mediumtime. To further reduce unnecessary backlogs in the queues, we take into consideration thefact that after certain queuing delay a packet would become useless and should be dropped.4.4.1 Accounting for Different Delay BoundsIn the design of PRO-HCCA scheduler, we keep the computation of SI similar to that inthe reference scheduler. This interval is fixed for a given traffic mix until a new streamis admitted or one or more of the existing streams finish transmission. Having a dynamicserviceintervalislikelytoresultinsignificantcomplexityintheschedulingprocesswithoutofferingbenefitswhencomparedtoanoptimization-basedfixedserviceintervalscheduling.For each admitted TS i, the QAP will maintain a partition list PLi with entry j contain-ing the amount of traffic backlogged for time period between (j−1)∗SI and j∗SI, where0 < j≤⌈DiSI⌉and Di is the delay bound of the stream. We refer to this backlogged trafficrecorded in the jth entry of the list as the jth partition of the corresponding TS queue anddenote it by PLij. The index j literally represents the degree of urgency for service. Thislist will be updated at each scheduling instant. A pseudo code for the updating procedureis provided in Algorithm 1, where N is the number of admitted streams, QLi is the queuelength (in bits) of TS i, X is overhead in time units, and 0 in the superscript stands for theprevious value of the variable.Let us consider the traffic amount in the (j−1)th partition at the previous schedulinginstant. When the current scheduling instant arrives, this traffic amount has been either140Algorithm 1: Updating the partition list PL1. for i := 1 to N2. for j :=⌈DiSI⌉downto 33. PLij := PL0i(j−1)−(t0i(j−1)−X)∗R4. endfor5. PLi2 := AR0i ∗SI−(t0i1−X)∗R6. if i is a downlink stream7. PLi1 := QLi−⌈DiSI⌉∑j=2PLij8. else PLi1 := PRi∗SI9. endif10. endforfully or partially transmitted. The transmitted traffic amount can be determined from thetransmission time ti(j−1) that was computed for the partition in the optimization process(described in Subsection 4.4.3) during the previous scheduling instant. The rest of thetraffic in the partition has been backlogged for another SI period. Therefore, this remainingamount of traffic should be set as the value of PLij in the current scheduling instant. Thisupdate method is applied to all the partitions except partition 1 and 2. Therefore, we choose3 as the end value of the loop in line 2 of the pseudo code listed in Algorithm 1. Theupdating method for PLi1 is different because this is the amount of traffic that has arrivedonly after the last scheduling instant. On the other hand, since PLi1 may contain thepredicted amount of traffic instead of the actual amount, it cannot be used to calculate thenew value of PLi2.Regarding the calculation of PLi1, the uplink streams have to be considered differentlythan the downlink streams. The traffic queue of an uplink stream is located at the QSTA141where the stream is attached. Since the queue is not at the QAP, the scheduler does notknow the amount of traffic that has arrived to that traffic queue during the last SI period.The scheduler, therefore, has to predict this amount for an uplink TS i by multiplying apredicted traffic intensity PRi with the value of SI. On the other hand, the instantaneousqueue lengths of downlink streams are known to the scheduler since the downlink queuesare collocated with the scheduler at the QAP. The value of PLi1 of a downlink stream is,therefore, easily obtainable by considering its queue length and the rest of the partitions ofits queue.To update PLi2, the actual amount of TS i traffic that arrived during the SI period pre-ceding the previous scheduling instant has to be considered. This amount can be calculatedfrom traffic arrival intensity ARi of TS i during that SI period. For downlink streams, thecalculation is straightforward. In subsection 4.4.2 we will discuss how ARi can be calcu-lated for uplink streams. To get the updated value of PLi2, the amount of traffic that hasbeen transmitted by the transmission time allocated for partition 1 of TS i during the lastSI period is deducted from the amount of traffic that arrived during the SI period precedingthe previous scheduling instant.4.4.2 Predicting VBR Traffic IntensitiesFrom the previous subsection, we can see that the first entry in the PL list of an uplinkstream cannot be determined like the other entries in the list. To determine this entry thescheduler has to know the amount of traffic that has arrived within the SI period sincethe start of the last service to the corresponding TS. The downlink traffic volumes can bedetermined from the downlink queues, which are collocated with the QAP. However, sincethe arrivals occur at the QSTAs, the actual information on the newly arrived uplink traffic142volume is not available to the QAP when it makes the scheduling decision. Due to thepotentially VBR nature of the traffic, the QAP needs to make predictions. The predictedtraffic intensities will be used to estimate the amount of newly arrived traffic for each TS.The prediction mechanism should meet some requirements. Due to the limited memoryand computational power available in the WLAN routers, the scheme has to be simple.On the other hand, it should be able to deal with the short term and long term correlationbetweentrafficintensitiesovertime. ItiswellknownthatVBRvideoandaudiotrafficshowthisproperty. Theleastmeansquare(LMS)predictorisasimplepredictionmechanismandhas been shown to predict VBR traffic reasonably well [11].However, the performance of the LMS filter largely depends on the eigenvalue spreadof the input data. A large spread in the eigenvalue badly affects the performance of theLMS predictor. As a result, the LMS predictor can perform poorly if the time series showsstrong correlation property. This limitation can be largely overcome by using transformdomain LMS predictors [12]. Wavelet domain LMS prediction could be an ideal choicedue to its simplicity and its ability to smooth out the effect of large correlation among theinput data.Wavelet transform is a powerful signal processing technique. The idea behind wavelettransform-basedpredictoristodecomposetheoriginaldataseriesintoadifferentseriesthatwill offer better stability and convergence. As shown in [12], the eigenvalue spread of theinputdataisreducedsubstantiallywhentheyaredecomposedusingwavelettransform. Thediscrete transform gives a wavelet co-efficient vector of the same length as that of the inputvector. The wavelet transform-based LMS predictor can be described by the following set143of equations [12]:z(n) = DWT(x(n−1),x(n−2),···,x(n−K))ˆx(n) = ww(n)·z(n)e(n) = x(n)−ˆx(n)ww(n + 1) = ww(n) + 2µe(n)Γ−1z (n)z(n)(4.15)where DWT stands for Discrete Wavelet Transform, ww(n) is the filter co-efficient vec-tor, ˆx(n) is the predicted and x(n) is the real signal value at the nth time step, K isthe order of the prediction, Γz is the input correlation matrix in the DWT domain. Thecondition of convergence is 0 < µ < 1. Considering a self-orthogonalizing WLMS,the Γz matrix can be approximated following the methods proposed in [13] as ˆΓz(n) =diag(ˆζn,1, ˆζn,2,···, ˆζn,K), in which ˆζn,m = φˆζn−1,m +(1−φ)z2m(n), 1≤m≤K whereφ is an adjustable parameter (0≤φ≤1) that can be adjusted for better convergence.To predict the traffic intensity over the next SI period, the PRO-HCCA scheduler entityin the QAP keeps record of the K observations in the recent past over the last K SIs foreach admitted stream i. Here, K is the order of the WLMS predictor. By substitutingthese K past observations into the variables x(n−1) to x(n−K) of the WLMS predictorequations, the predicted traffic intensity PRi can be calculated as ˆx(n).For the adaptation step of the predictor, the actual intensity of traffic that have arrivedduring the last SI has to be computed. The IEEE 802.11e specification allows that after aQSTA is done with its transmission opportunity in a scheduling interval, the QSTA informsthe QAP about the queue length information of the TSs attached to itself. This informationusually is piggybacked with the last packet transmitted within that transmission opportu-nity. Let the queue length of a TS i attached to a particular QSTA at this time instant be144denoted as QLtxopi (in bits). If QL0txopi denotes this value at the end of TXOP during theprevious SI then the QAP can calculate the actual intensity ARi of traffic arrival for TS ias follows:ARi = QLtxopi−QL0txopi + (TXOPi−X)∗RSI . (4.16)This value of ARi is then used as x(n) in the above mentioned WLMS equations.4.4.3 Optimizing TXOP AllocationAt each scheduling instant that will occur after each SI interval, the QAP has to distribute(in the form of TXOPs) a constrained amount of medium time Tavail (0 ≤ Tavail ≤ SI)among the admitted traffic streams. We formulate this allocation as an optimization prob-lem. Thanks to the accounting and prediction mechanism described in Subsections 4.4.1and 4.4.2, respectively, the scheduler entity inside the QAP has a picture on the urgenciesof service for different portions of the TS queues. We propose to use a utility function totake into account these urgencies and to formulate an optimization model accordingly. Theutility received from transmitting data belonging to partition PLij for a single time unit (inslot time) is Uij = 1⌈DiSI ⌉−j+1.The constraint on the available medium time for HCCA within each scheduling intervalis described by two parameters. The first parameter ρhcca is the fraction of medium timeallocated for HCCA. If T and TCP denote the beacon interval and the time used by EDCAtraffic within a beacon interval, respectively, then ρhcca = T−TCPT . The second parameteris the 802.11e dot11CAPlimit, which is set during the WLAN setup. Therefore, Tavail =max(ρhcca∗SI,dot11CAPlimit).The output from the optimization procedure will be the transmission times allocated fordifferent partitions of the TS queues. For TS queue i, let us denote by tij the transmission145time allocated for the jth partition. The optimization model can be described mathemati-cally as follows:maximizetijΩ =N∑i=1⌈DiSI⌉∑j=1Uij.tijs.t. :N∑i=1⌈DiSI⌉∑j=1tij ≤Tavail0≤tij ≤(PLijR + X),i = 1,2,···,N;j = 1,2,···,⌈DiSI⌉(4.17)A closer inspection into the formulation of the optimization reveals that it can bemapped into the classical fractional Knapsack problem [14] which can be solved efficientlywith a greedy algorithm in an online fashion. From different TSs, we can combine thosetransmission time units which have the same utility. Since we only have discrete valuesfor utility, there will be a discrete set of transmission time units. Let us denote the set asG = [g1,g2,···,gp], where p is the number of distinct values of per transmission timeunit utilities at the scheduling instant. The scheduler at the QAP maintains the informationabout which TSs are contributing how much to the value of each element in the set. Foreach element, an entire amount or a fraction will be selected by the solution [14] of thefractional Knapsack problem.Ifgh (1≤h≤p) is selected as a whole, then from each TS the entire amount contribut-ing to gh is selected for service. When a fraction is selected, the amounts for different TSsare selected in proportion to their contributions to gh. The outcome of the procedure will146be the tij values which are the variables in the optimization problem. Note that, for a givenTS, the transmission times will be allocated such that partition j+1 will be able to transmitcompletely before partition j gets the opportunity to transmit. This is simply due to the factthat transmitting a data unit from partition j +1 will yield higher utility than transmitting adata unit from partition j and that the optimization is aimed at maximizing the total utility.With the tij values determined as above, the TXOPs for the TSs are calculated as follows:TXOPi =⌈DiSI⌉∑jtij,i = 1,2,···,N (4.18)Once the TXOP values for the admitted streams have been calculated as above during thescheduling instant, the QAP broadcasts these allocations to the QSTAs.4.5 Performance Evaluation of the PRO-HCCAScheduler4.5.1 Simulation Setup and ParametersWe simulate IEEE 802.11e HCCA using a discrete-event simulator written in Parsec [15].We code the reference scheduler and the proposed PRO-HCCA scheduler in the simulator.Simulations can be run with either of the scheduler enabled. In the WLMS predictor, weuse Daubechie-4 as the mother wavelet to perform wavelet transforms. The physical layerof the WLAN conforms to 802.11a specification with a physical rate of 36 Mbps. The PHYand MAC parameters are listed in Table 4.1.The WLAN topology consists of 3 QSTAs each generating a traffic stream. The mixof the streams consists of VBR VoIP and video streams. Two types of video streams are147Table 4.1: Packet overhead and MAC parametersParameter ValueRTP header size 12 bytesUDP header size 8 bytesIP header size 20 bytesMAC header size 36 bytesPLCP header size 3 bytesSIFS interval 16 µsecACK size 14 bytesPHY data rate 36 MbpsMinimum data rate 6 MbpsSlot time 9 µsecBeacon period 500 msIFQ Length 50Table 4.2: Properties and QoS requirements of the scheduled streamsTS No. Type TSPEC Parameters Attached QSTANominal MSDU Size Mean Data Rate MaxSI Delay Bound1 Interactive video 1000 bytes 210 kbps 50 ms 100 ms 12 Non-Interactive video 920 bytes 180 kbps 100 ms 200 ms 23 VoIP 160 bytes 22.4 kbps 25 ms 50 ms 3used: interactive and non-interactive. QSTA 1 generates the interactive video whose traffictrace is collected from the lecture room cam trace (high quality MPEG-4) available at [16].A non-interactive or streaming video stream is generated from real traffic trace and is at-tached to QSTA 2. The stream is generated from the medium quality MPEG-4 trace of themovie Mr. Bean. This trace is also collected from [16]. A VBR VoIP stream with silencesuppression is simulated and attached to QSTA 3. The stream has exponentially distributedON and OFF state times with the average state duration of 352 ms and 650 ms, respec-tively. Table 4.2 summarizes the properties and QoS requirements of the streams used inthe simulation. The amount of time simulated is 300 seconds.1480 20 40 60 80 100 120 140 16000.10.20.30.40.50.60.70.80.91d(ms)Pr(delay≤d)  PRO−HCCA SchedulerReference HCCA SchedulerFigure 4.4: Cumulative distribution function of delay (ms) experienced by packetsgenerated from the interactive video stream.4.5.2 Simulation Results and DiscussionsFig. 4.4 shows the CDF of the delays experienced by packets belonging to the interactivevideo stream. The packet delay includes the access delay and the transmission time of thepacket itself. We can observe that the reference scheduler performs very badly in termsof meeting the delay bound. Only 43% of the packets could be served within the pledgeddelay bound. On the other hand, the PRO-HCCA scheduler clearly shows its ability tomeet the delay guarantee. All the packets generated by the stream are served within theguaranteed delay although the interactive video requires a very stringent delay bound of100 ms. Table 4.3 also shows that this delay performance is achieved with no packet lossat all. Note that the PRO-HCCA is designed to drop any packet that fails to meet the delaybound. The reference scheduler does not have such provisioning. Even with this extrapassage for packet dropping, the PRO-HCCA scheduler achieves 0% packet loss, which is1490 10 20 30 40 50 60 70 80 90 100 110 12000.10.20.30.40.50.60.70.80.91d(ms)Pr(delay≤d)  PRO−HCCA SchedulerReference HCCA SchedulerFigure 4.5: Cumulative distribution function of delay (ms) experienced by packetsgenerated from the non-interactive video stream.quite remarkable. On the other hand, the reference scheduler drops a significant percentage(almost 19%) of packets.Fig.4.5showstheCDFofdelaysexperiencedbypacketsbelongingtothenon-interactiveor streaming video traffic. Compared to the interactive video stream, this stream has bet-ter delay tolerance with a delay bound of 200 ms. The figure shows that the referencescheduler still performs very badly. Although the percentage of packets meeting the delaybound improves to nearly 65% because of the less strict delay bound, the performance isstill unacceptable. In contrast, the proposed PRO-HCCA scheduler excels in performancein terms of meeting the delay bound. The figure clearly shows that 100% of the packetsbelonging to the stream are served with latencies comfortably within the delay guarantee.For the reference scheduler, the packet drop rate (2.5%) for the non-interactive stream isnot as bad as it is with the interactive video stream. This improvement can be attributed tothe lower intensity of the traffic arrival (since the video is of a medium quality) and also1500 25 50 75 100 125 150 175 200 22500.10.20.30.40.50.60.70.80.91d(ms)Pr(delay≤d)  PRO−HCCA SchedulerReference HCCA SchedulerFigure 4.6: Cumulative distribution function of delay (ms) experienced by packetsgenerated from the VBR VoIP stream.to the less strict delay bound. On the other hand, the PRO-HCCA scheduler maintains 0%packet loss with the stream as well.Finally, the CDF of packet delays for the VoIP stream is shown in Fig. 4.6. Althoughthis stream has the most stringent delay bound of 50 ms, with the PRO-HCCA scheduler,all the packets of the stream are served within this delay bound. As is evident from thefigure, the reference scheduler performs the worst in terms of meeting delay guarantees forthe stream out of the three streams served. This also confirms that the reference schedulerpenalizes more the streams with stricter delay bounds. On the other hand, the PRO-HCCAscheduler treats the streams fairly and can provide delay guarantees irrespective of thestrictness of the delay bound. As shown in Table 4.3, the reference scheduler does notdrop packet for the considered VBR VoIP stream because of the very low traffic arrivalintensity of the stream. The proposed PRO-HCCA scheduler also exhibits no packet lossfor the stream. The packet loss performance of the reference scheduler is highly sensitive151Table 4.3: Summary of the resultsStream Packets served within delay bound Packet lossType Reference HCCA PRO-HCCA Reference HCCA Scheduler PRO-HCCA SchedulerScheduler Scheduler Scheduler SchedulerInteractive video 43% 100% 19% 0%Non-Interactive video 65% 100% 2.5% 0%VBR VoIP 17% 100% 0% 0%to the traffic intensity of the relevant stream, whereas the PRO-HCCA scheduler showsstable performance irrespective of the traffic intensity. A summary of the numerical resultsis listed in Table 4.3.Overall, the simulation results show the effectiveness of the PRO-HCCA scheduler inadapting to various multimedia traffic scenarios while delivering necessary QoS require-ments. Although the results are shown for a WLAN with three QSTAs, the performance ofPRO-HCCA is expected to show its effectiveness in much larger sized WLAN deployment.Due to the low computational complexity of the prediction mechanism used for the sched-uler, the QAP will be able to handle the VBR traffic prediction with acceptable accuracyfor a reasonable number of traffic streams. The optimization module is designed to achievethe maximum utilization of the available medium time and bandwidth. If the number ofscheduled streams grows, the delays experienced by the streams are expected to grow to-wards their delay bounds. However, since the packets needing the most urgent service areserviced with the most priority, the delay guarantees will be met as much as possible withthe available resource constraint. Moreover, the PRO-HCCA scheduler is designed to notschedule the packets that have already missed their deadlines. Therefore, meeting delayguarantees will enjoy higher priority over packet loss if the available medium time cannotaccommodate the instantaneousness demand. Multimedia applications typically can toler-ate some level of packet loss. By continuing to meet the delay guarantees at the expense of152some packet loss could be the worst case scenario if the number of streams and their aggre-gate QoS demand exceeds the available resource in the system. However, we assume thatthe HCCA admission controller will complement the operation of the scheduler to restrictthe number of admitted streams so that aggregate QoS demand remains within the availableresource in the WLAN system. We conjecture that the PRO-HCCA scheduler will be ableto meet the QoS guarantees of increased number of multimedia streams from increasednumber of WLAN stations so long as the admission controller can effectively regulate theadmission of traffic streams based on the QoS demands and the system capacity.4.6 ConclusionsWe have formulated an analytical model for the controlled channel access mechanism (alsocalled HCCA) in IEEE 802.11e based WLANs considering VBR traffic applications. Themodelenablesustoderiveimportantperformancemeasuresintermsoftheparametersusedin the reference scheduler. The results obtained from the analytical model have shown thatthe QoS guarantees for VBR traffic cannot be met without dynamically adapting the trans-mission opportunities to variable traffic intensities and to urgencies for service of compet-ing connections. Using the insights gained into the cause of the problems in the referencescheduler, we have developed a novel HCCA scheduler for IEEE 802.11e WLANs. Theproposed scheduler adapts dynamically with dynamic traffic intensities that may arise frommultimedia applications. The proposed PRO-HCCA scheduler utilizes simple but smartprediction mechanism along with an efficient online optimization process. The urgency ofservice for different parts of the backlogged queues is considered in the optimization step.Simulation experiments have shown that the PRO-HCCA scheduler achieves very robustand stable performance in meeting QoS guarantees for various VBR traffic applications.1534.7 Bibliography[1] IEEE Std. 802.11e-2005, Part 11: Wireless LAN Medium Access Control (MAC) andPhysical Layer (PHY) Specifications Amendment 8: Medium Access Control (MAC)Quality of Service Enhancements, Nov. 2005.[2] M. F. Neuts, Matrix Geometric Solutions in Stochastic Models - An Algorithmic Ap-proach, John Hopkins Univ. Press, Baltimore, MD, 1981.[3] Z.-N. Kong, D. H. K. Tsang, B. Bensaou, and D. Gao, “Performance Analysis of IEEE802.11e Contention-based Channel Access,” IEEE Journal on Selected Areas in Com-munications, vol. 22, no. 10, pp. 2095- 2106, Dec. 2004.[4] Z. Tao and S. Panwar, “An Analytical Model for the IEEE 802.11e Enhanced Dis-tributed Coordination Function,” Proc. IEEE International Conference on Communi-cations, pp. 4111 - 4117, Paris, France, Jun. 2004.[5] O. Tickoo and B. Sikdar, “Queueing Analysis and Delay Mitigation in IEEE 802.11Random Access MAC Based Wireless Networks,” Proc. IEEE Infocom 2004, Anchor-age, AK, USA, Mar. 2004.[6] S.Mangold,S.Choi,G.Hiertz,O.Klein,B.Walke,“AnalysisofIEEE802.11eforQoSSupport in Wireless LANs,” IEEE Wireless Communications, vol. 10, no. 6, pp. 40-50,Dec. 2003.[7] G. Holland, N. Vaidya, and P. Bahl, “A Rate-Adaptive MAC Protocol for Multi-HopWireless Networks,” Proc. ACM/IEEE MOBICOM’01, Rome, Italy, pp. 236–250, Jul.2001.154[8] A. S. Alfa, “Vacation Models in Discrete Time,” Queueing Systems, vol. 44, no. 1,pp. 5-30, May 2003.[9] S. McCanne and V. Jacobson, “VIC: A Flexible Framework for Packet Video,” Proc.ACM Multimedia’95, S. Francisco, California, Nov. 1995.[10] A. Horv´ath and M. Telek, “Phfit: A General Phase-Type Fitting Tool,” Proc. 12thPerformance TOOLS, Lecture Notes in Computer Science, vol. 2324, London, UK,Apr. 2002.[11] T. S. Randhawa and R. H. S. Ardy, “Estimation and Prediction of VBR Traffic inHigh-Speed Networks using LMS Filters,” Proc. IEEE International Conference onCommunications, Atlanta, GA, USA, June 1998.[12] B. Farhang-Boroujeny, Adaptive Filters: Theory and Applications, New York: Wiley,1998.[13] J. C. Lee and C. K. Un, “Performance of Transform-Domain LMS Adaptive DigitalFilters,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-34, pp. 499-510,1986.[14] T. Cormen, C. Leisorson, R. Rivest, and C. Stein, Introduction to Algorithms, Secondedition, Cambridge: MIT Press, 2001.[15] R. Bagrodia, R. Meyer, M. Takai, Y. Chen, X. Zeng, J. Martin, and H. Y. Song,“PARSEC: A Parallel Simulation Environment for Complex Systems,” IEEE Com-puter, vol. 31, no. 10, pp. 77-85, Oct. 1998.155[16] MPEG-4 and H.263 Video Traces for Network Performance Evaluation,http://www.tkn.tu-berlin.de/research/trace/trace.html, Oct. 2006.156Chapter 5Opportunistic Spectrum Scheduling forMultiuser Cognitive Radio: A QueueingAnalysis15.1 IntroductionWidespread deployment of broadband wireless access systems have dramatically increasedthe demand for radio spectrum. This is expected because such systems require certainamount of bandwidth to offer broadband quality data rates. However, radio spectrum is oneof the most scarce and valuable resources for wireless communications. As the availableradiospectrumislimited,improvingitsutilizationhasgainedrenewedinterestwiththepro-liferation of broadband wireless technologies. New insights into the use of radio spectrumhave challenged the traditional static spectrum allocation policy. Actual measurements1A version of this chapter has been published. Rashid, M.M., Hossain, M.J., Hossain, E. and BhargavaV.K. (2009) Opportunistic Spectrum Scheduling for Multiuser Cognitive Radio: A Queueing Analysis. IEEETrans. on Wireless Commun. 8(10):5259–5269.157have shown that most of the allocated spectrum is largely underutilized [1]. Similar viewson the underutilization of allocated spectrum were reported by the Spectrum-Policy TaskForce appointed by Federal Communications Commissions (FCC) [2]. Spectral efficiencycan be increased significantly by giving opportunistic access of the frequency bands to un-licensed users. Cognitive radio (CR) has been proposed as a way to improve spectrum effi-ciency by exploiting the unused spectrum in dynamically changing environments [3]. TheCR technology is based on an innovative radio design philosophy which involves smartlysensing the swaths of radio spectrum and then determining the transmission characteristics(e.g., symbol rate, power, bandwidth) for cognitive radio users (CR users) based on theperceived behavior of the primary users (i.e., users who are licensed for the spectrum inconsideration).Although opportunistic spectrum access would allow CR users to identify and accessavailable spectrum resources, one of the main concerns is to utilize the available spectrumresources efficiently. As such CR users’ quality-of-service (QoS) requirements are metwithout violating the priority right of primary users. In a CR network, the availability ofradio spectrum for CR users depends mainly on the activity of primary users. On the otherhand, since wireless channel quality of CR users is time-varying in nature, communicationresource available to CR users is highly dynamic. The medium access control (MAC) layerprotocols in a CR network should be able to adapt to the availability of the communicationresources. An adaptive MAC layer, which efficiently uses communication resources giventhe QoS requirements, is an important component for an adaptive wireless access systembased on CR technology. In order to design smart radio resource management schemes forthis adaptive system, the system engineers have to determine how important system andoperating parameters affect important performance measures relevant to the design. These158parameters are most likely to encompass different layers of the protocol stack. Therefore,a cross-layer analytical model will be very useful for efficient design, analysis, and opti-mization of resource management schemes such as scheduling and admission control.Research interest on CR technology has grown tremendously off late and a reasonablenumber of ensuing research efforts have dealt with performance analysis of CR systems. Inmost of the cases, the focus of the performance analysis has been on the capacity, through-put and/or outage probability achievable at the physical layer (PHY). In [4], Devroye etal. presented an information theoretic analysis to derive the capacity regions of a cogni-tive radio channel. Information theoretic limit of throughput in cognitive networks wasalso analyzed in [5] and [6] assuming different cooperative behaviors between primary andCR users. Game theoretic models have also been used to analyze CR networks. Ji andLiu provided a review of theses game theoretic models in [7]. These models are usefulto analyze achievable payoffs and associated fairness of service among CR users result-ing from different spectrum sharing policies in CR networks. The problem of efficientspectrum sensing and spectrum access in CR networks was addressed in [8]-[10]. While[11] and [12] studied the spectrum access problem in a single-user scenario, [13] and [10]considered a multi-user scenario. A framework for medium access control (MAC) protocoladaptationinadynamicspectrumaccessscenariowasproposedin[14]. Simeoneetal.[15]studied MAC layer throughput for a CR user over a cognitive link given a certain through-put at the primary user end. The system model, however, is very simplistic with a single CRuser opportunistically sharing the cognitive link with a single primary user. The queueingmodel assumes infinite transmission queues and does not study delay or packet loss perfor-mance measures. In [16], an M/G/1 queueing model was used to analyze the transmissionperformance of multiple CR users on an aggregate basis considering both PHY and MAC159layer parameters. Analytical models were developed in [17] for cognitive MAC protocolswith dedicated control channel and with embedded control channel. Call-level QoS perfor-mance (e.g., blocking performance) for CR users was analyzed in [18] based on a G/M/Nqueueing model. In a similar spirit, call-level performances for both primary users and CRusers were analyzed in [19] using a two-dimensional Markov chain. A survey of the MACschemes for CR networks can be found in [20]. A cross-layer design methodology for CRnetworks based on fuzzy logic was presented in [21].Differentfromtheaboveworks, wedevelopacross-layer(MAClayerandPHY)queue-ing model that considers multiple CR users competing for spectrum opportunities, and ex-ploitation of multiuser diversity for allocating spectrum opportunities among the CR users.We consider a spectrum overlay scenario in an infrastructure-based dynamic spectrum ac-cess environment where the CR controller or the cognitive radio base station (BS) allocatesthe available spectrum opportunities among CR users. The cognitive radio BS uses an op-portunistic scheduling scheme based on channel quality to allocate the spectrum resourcesamong CR users, because such a scheduling scheme offers throughput gain with increasednumber of users in a wireless system [22]. For the queueing analysis, we model the activityof primary users in a channel as a two state Markov chain and the channel fading in thelink between the cognitive radio BS and a CR user as a finite-state Markov chain (FSMC).The model also considers realistic traffic model that captures the potential burstiness in thearrival process. The queueing analysis enables use to relate the packet-level QoS perfor-mancemeasuresattheMAClayerwithanumberofimportantsystemandPHYparameters.Therefore, this will facilitate cross-layer (MAC layer and PHY) design of CR networks.Also, the analysis facilitates the design of a model-based admission controller in order toprovidetherequiredQoSfortheCRusers. Selectednumericalresultsarepresentedtoshow160the effect of important system and traffic parameters on the performance measures of inter-est including the delay distribution, packet loss rate, and throughput. The matrix-analyticmethod used in this chapter has a nice algorithmic approach, which is much more elegantthan traditional queueing analysis methods that usually involve complex Laplace-StieltjesTransforms (LST). Being free from LST, our method allows to numerically compute thedelay and queue length distributions with much greater ease.The rest of the chapter is organized as follows. In Section 5.2, we describe the systemmodel which includes details of primary users’ activity level modeling, wireless channelmodeling, and the spectrum scheduling scheme. We develop the queueing analytic modelin Section 5.3 and present some selected numerical results in Section 5.4. Example appli-cations of the model are presented in Section 5.5. Section 6 concludes the chapter.5.2 The System Model and Assumptions5.2.1 Network ModelWe consider an infrastructure-based CR system consisting a cognitive radio BS and multi-ple CR users which opportunistically utilize the spectrum licensed to some primary users(Fig. 5.1). The cognitive radio BS controls transmissions to/from the CR users in its cov-erage area. For downlink transmission, the packet queues for the CR users will be locatedat the cognitive radio BS. In case of uplink transmission, the location of the packet queueswill be at the CR users. The analytical model presented later in the chapter will be validfor both the cases.Following the cross-layer model in [23], we assume that packets arriving from thehigher layers are buffered and scheduled at the MAC layer and then transmitted on air161CR BSCR userPU BSPU BS CR userCR userCR userCR userFigure 5.1: Infrastructure-based cognitive radio network architecture (CR = Cogni-tive radio; PU = Primary user; BS = Base station).one or more at a time inside physical layer frames. The system is assumed to be timeslotted with the slot size fixed to the duration (Tf) of a frame transmission. Adaptive mod-ulation and coding (AMC) is used to adjust the PHY transmission mode for each radiochannel between a CR user and the cognitive radio BS. Therefore, the size (in bits) of aframe might vary from frame to frame due to AMC and the number of channels assignedto the user. Assuming a fixed packet size, the number of packets transmitted in a frameduration will vary accordingly. Note that in the rest of the chapter, the term time slot willbe used synonymously for the frame duration Tf.Let the total bandwidth available for communication be WT[Hz] which is licensed to agroup of primary users. We assume that the total bandwidth is divided into M channels.Portions of the spectrum i.e., channels licensed to the primary users may remain unused162and thus be available to the CR users. The spectrum sensing technique implemented inthe cognitive radio BS will enable it to discover these spectrum opportunities at each timeslot n2. We assume that if a channel is not used by primary users at the beginning ofa time slot n, it remains unoccupied by primary users during that slot and the cognitiveradio BS can assign this channel to a CR user under its coverage. The availability ofspectrum opportunities for CR users will vary over time depending on the activity leveland pattern of the usage by the primary users. The wireless channel quality of CR users isalso time-varying in nature. Since in a given time slot, a number of CR users may demandfor the spectrum resource, a scheduling method will be required to allocate the spectrumopportunities among CR users.5.2.2 Primary User ActivityWe assume that the channel occupancy by primary users for ith (1≤i≤M) channel is atwo-state time-homogenous first-order Markov Process, and the process is independent andidentical from one channel to another. Similar channel occupancy model was used in [11].LetO denote the Markov process representing the channel occupancy by primary users andPO denote its transition probability matrix. In this chapter, we refer PO as the occupancymatrix and define it as follows:PO = 1−p0→1 p0→1p1→0 1−p1→0 (5.1)where p0→1 denotes the probability that the channel is occupied in time n and will bereleased in the next time slot n + 1. Similarly, p1→0 denotes the probability that an unoc-2Spectrum sensing can be performed through separate sensing devices installed by the cognitive radioservice provider [24].163cupied channel will be occupied by a primary user in the next time slot. The activity factorof primary users in a given channel can be defined as the probability that the channel willbe occupied in a given time slot. This probability can be obtained by finding the steadystate probabilities of the state transition matrix in (5.1). We assume that theses transitionprobabilities are known at the cognitive radio BS. We also assume a perfect channel sens-ing scheme in the CR network in consideration, and therefore, ignore any channel sensingerror when estimating primary user activity.5.2.3 Channel Model and Adaptive ModulationThe power gain for channel fading of CR user j at channel i, γi,j is assumed to be slowlyvarying with Gamma distribution which corresponds to the Nakagami-m distribution [25]for fading amplitude variation. The channel fading process can be modeled as an FSMC[26], for which, γi,j maps to a channel state in setC = {0,1,...,Z}with a total of Z +1 states. In a time slot, let the state of channel i for CR user j be k if σk ≤ γi,j <σk+1. The power gain thresholds satisfy the following inequality: 0 = σ0 ≤ ... ≤ σk ≤... ≤ σZ+1 = ∞. A set of AMC schemes are chosen as transmission modes accordingto a one-to-one relationship with these channel states. The following relationship betweenpacket transmission rates and transmission modes is also assumed: ξk = bk,1 ≤k ≤Z,where ξk denotes the number of packets that can be transmitted during a time slot whentransmission mode k (which corresponds to channel state k) is selected, b is an integerwhich depends on time slot duration and modulation parameters. Channel state 0 simplyrepresents that there will be no transmission in the channel when the fading SNR remainsbelow σ1. The thresholds σk (1≤k≤Z) can be obtained to meet the average packet errorrate (PER) target for for each of these transmission modes [23]. For a given Doppler shift,164the transition probabilities between the channel states of the FSMC can be obtained as in[26]. Note that, in our model, a channel can change from one frame to the next, and thedynamics of such changes is captured through the FSMC channel model. A session, on theother hand, usually contains many frame times and therefore, signal strength of a channelcan change many times during a session. The assumption made in our model only restrictsa channel state to remain unchanged over a frame time, which is usually in the range offew milliseconds. However, we allow the possibility that a channel can change many timesduring a session, which is usually in the order of many seconds.5.2.4 Opportunistic Spectrum SchedulingFor wireless networks, opportunistic scheduling, which exploits multiuser diversity, hasbeen proved to maximize system throughput [27]. Due to the inherent gain from multiuserdiversity, we also assume an opportunistic spectrum scheduling scheme. In this scheme,an empty channel is assigned to a CR user for whom the highest transmission rate can besupported in that channel. The spectrum scheduling scheme can be summarized as follows:• At time slotn, the cognitive radio BS identifies the set of unoccupied channels,L(n).• From the listL(n), a channel is picked up and the channel state for each CR useris checked for this channel. It is assigned to the CR user with the highest channelstate. If there are more than one CR users with the highest state, a user is selectedrandomly. The channel is assigned to this user and removed from the list.• This procedure is repeated until all the channels inL(n) are assigned to the CR usersAccording to the above spectrum scheduling scheme, a CR user may be allocated morethan one channel in a given time slot. Also, multiple CR users could be allocated spectrum165opportunities in the same time slot. For this, we assume that a hybrid FDMA/TDMAmechanism is employed at the cognitive radio BS.Note that the channel fading information for the CR users need to be made availableat the scheduler through some Channel Quality Information (CQI) feedback mechanismimplemented at the BS. The main cost of such feedback is the extra uplink radio resourcenecessary to carry the CQI. How to minimize the amount of radio resources necessary forthe CQI feedback method is itself a very active research area and in our analysis, we do notassume any particular scheme to obtain channel fading information. For the system modelanalyzed in our chapter, the possible CQI (i.e. SNR) values are divided into a predefinednumber of channel states; therefore, for a particular channel, a user can report the channelstate instead of reporting the exact SNR. As a result, a CR user can forgo sending CQI tothe cognitive radio BS for a channel when channel fading in the current frame does notdiffer from that in the previous frame to warrant a transition in channel states. Therefore,we conjecture that the cost of getting the channel fading information would be reasonablylow. Sincetheremaynotbeanycommoncontrolchannelavailableforperiodicfeedbackofchannel state information from the CR users to the cognitive radio BS, a predictive schemecan be used [28].5.3 Formulation of the Queueing Model5.3.1 Packet Arrival ProcessAssuming a homogenous system, we develop the queueing model from the perspective ofa tagged CR user. We assume that packet arrivals for a CR user follow a Batch Bernoulliprocess which can be described by a vector α = [α0,α1,···,αN], where N is the maxi-166mum number of packets that can arrive during a time slot. Here, α0 is the probability of nopacket arrival and αi (1 ≤i≤N) is the probability that i packets arrive in a time slot.The average arrival rate λ (in packets/slot) can be calculated as λ =N∑i=1iαi.The assumed Batch Bernoulli arrival model is very general which can capture differentlevel of burstiness in the traffic arrival process. We also assume that packets arriving duringtime slot n−1 cannot be served until time slot n at the earliest. The packets in the queueare served in a first-come first-served manner and packet transmissions in a time slot areassumed to finish before arriving packets enter the queue.5.3.2 Joint System State Considering Primary User Activity, ChannelState, and Opportunistic SchedulingLet random variable m(i)n ∈{1,0}represent whether ith channel is assigned to the taggeduser (CR user 1) or not at time slot n. We assume that m(i)n = 1 denotes that CR user 1 isassigned to ith channel at time slot n. Similarly c(i)n ∈C denotes the channel state of ithchannel at time slot n. Therefore, the joint state for the ith channel at time slot n can bedenoted as (m(i)n ,c(i)n ). The corresponding state transition probability matrixM(i) can bedetermined as follows:M(i) = M(i)0→0 M(i)0→1M(i)1→0 M(i)1→1 (5.2)whereM(i)k→l is a (Z +1)×(Z +1) matrix whose element at row y and column z denotedhere byM(i)k→l(y,z) is defined asM(i)k→l(y,z) = Pr (m(i)n+1 = l,c(i)n+1 = z|m(i)n = k,c(i)n =y). These probabilitiescan be obtained using similarequations as (3.6)-(3.13) of Chapter3.For brevity, we do not include the details of the procedure here. Also note that thesetransition probabilities are calculated for a specific number of users inside the network.167When any CR user moves in and out of the CR network, these transition probabilities canbe recalculated with the updated number of CR users in the system.However, assignment of a given channel to a CR user does not guarantee that the userwill be able to access the channel since it can be occupied by a primary user. Therefore,we introduce another random variable o(i)n ∈{1,0}to denote the occupancy state of ithchannelbyprimaryusersattimeslotn. Specifically,o(i)n = 0meansithchannelisoccupiedby primary users and o(i)n = 1 represents that the channel is available to the CR user attime slot n. In the previous section, we have also introduced the occupancy matrix PO todescribe the Markov process assumed for channel occupancy by primary users. Therefore,for ith channel, the joint state considering the spectrum scheduling scheme and primaryuser activity can be denoted asΦ(i) ,{(o(i)n ,m(i)n ,c(i)n )|0≤o(i)n ≤1,0≤m(i)n ≤1,0≤c(i)n ≤Z}.The transition probabilities among the states inΦ(i) can be expressed using matrixH(i) as:H(i) = PO ⊗M(i), where ⊗ represents the Kronecker product.Letusnowdefineanewstatevariablesn(M)calculatedas: sn(M) = ∑1≤i≤Mo(i)n m(i)n c(i)nand construct a state space Θ(M) ,{sn(M)|0 ≤ sn(M) ≤ MZ}. Next, we describe aprocedure to calculate the transition probability matrixS(M) for state spaceΘ(M).Let us consider channels 1 and 2 first and start by constructing a joint state spaceΩ(2) ,{(o(1)n ,m(1)n ,c(1)n ,o(2)n ,m(2)n ,c(2)n )|0≤o(1)n ,o(2)n ≤1;0≤m(1)n ,m(2)n ≤1;0≤c(1)n ,c(2)n ≤Z}.Thetransitionprobabilitiesamongthesestatescanberepresentedbymatrixℜ(2) as:ℜ(2) =H(1)⊗H(2).168The steady state probability vectorτ(2) for the state spaceΩ(2) can be derived by solv-ing the following set of linear equations: τ(2)ℜ(2) = τ(2) and τ(2)1 = 1, where 1 standsfor a column matrix containing 1 only in each entry.With sn(2) = o(1)n m(1)n c(1)n + o(2)n m(2)n c(2)n , let yt (yt⊂Ω(2)) denote the set of states thatresult in sn(2) = t, where 0 ≤ t ≤ 2Z. Withℜ(2)h→h′ denoting the transition probabilityfrom state h to h′, where both h and h′ are elements of state space Ω(2), we can constructthe transition probability matrixS(2) for state spaceϕ(2) as follows:Sk→k′(2) =∑h∈yk∑h′∈yk′τ(2)h ℜ(2)h→h′∑h∈ykτ(2)h(5.3)whereSk→k′(2)denotesthetransitionprobabilityfromstatek tostatek′,where0≤k,k′≤2Z.We now describe a generalized procedure to recursively calculate transition probabilitymatrix S(M) for M ≥3. We combine state variables o(M)n ,m(M)n , and c(M)n for channel Mwith state variable sn(M−1) to construct the joint state spaceΩ(M) ,{(sn(M−1),o(M)n ,m(M)n ,c(M)n )|0≤o(i)n ≤1;0≤m(i)n ≤1;0≤c(i)n ≤Z},whose transition probability matrix ℜ(M) can be derived, assuming S(M −1) has beencalculated in the previous iteration of the recursion, asℜ(M) = S(M−1)⊗H(M).From definition of sn(M), we can also write sn(M) = sn(M−1) + o(M)n m(M)n c(M)n .Therefore, the transition probability matrixS(M) for M channels can be derived similarlyas was done for the two channel case by grouping states having same sn(M) values fromstate spaceΩ(M).169Now, let rn(M) denote the sum rate (in packets/time slot) available to the tagged CRuser due to M channels at time slot n. Since at any time slot n, the number of packetsthat can be transmitted over a single channel is bcn when the channel’s state is cn, it isstraightforward to show that rn(M) = bsn(M). For the sake of clarity in mathematicalexpressions, we will omit the index M from sn(M) andS(M) in the rest of the analysis.5.3.3 Quasi-Birth-and-Death Process Formulation and AnalysisThesystemcanbeviewedasatime-slottedsystemwheretransitionsamongthestatesoccurat the slot boundaries. In addition, the state variables assume discrete values only. There-fore, we can model the system using a discrete-time Markov chain (DTMC). To derive thetransition probability matrix of the DTMC, we consider the system dynamics as it evolvesfrom one time slot to the next time slot. With a finite buffer size of Q packets, the statespace of the system can be written as follows:Ψ ,{(xn,sn)|0≤xn≤Q;0≤sn≤MZ},where xn is the queue length in number of packets at time slot n.Once the transition probabilities in (5.2) are calculated, assuming an infinite bufferspace (Q = ∞) and setting L = bMZ, the state transition matrix for the DTMC can be170written asP =A(0)0 A(0)1+ ··· ··· A0N+A(1)1− A(1)0 A(1)1+ ··· ··· A(1)N+... ... ...A(L−N+1)(L−N+1)− A(L−N+1)(L−N)− ··· ··· ··· ··· A(L−N+1)1− A0 A(L−N+1)1+ ··· A(L−N+1)(N−1)+ AN+... ... ... ... ... ...A(L)L− A(L)(L−1)− ··· ··· ··· ··· ··· ··· ··· A(L)1− A0 A1+ ··· ··· AN+AL− ··· ... ··· ··· ··· ··· ··· ··· A1− A0 A1+ ··· ··· AN+... ... ... ...AL− ··· ··· ··· ··· ··· ··· A(L−N+1)− A(L−N)− ··· ··· ··· ··· A1− A0 A1+ ··· A(N−1)+ AN+... ... ... ... ... ... ...AL− A(L−1)− ··· ··· ··· ··· ··· ··· ··· A1− A0 A1+ ··· AN+... ... ....(5.4)By constructing blocks of submatrices as shown in (3.14), we can obtain a quasi-birth-and-death (QBD) process with a transition matrix of following form:Pinf =B EC D G0G2 G1 G0G2 G1 G0... ... .... (5.5)However, we are interested in finding performance measures for systems with finite bufferspace, which is more realistic. Assuming a finite buffer size of Q and setting K =⌊Q/L⌋,we can write the transition matrix in the following form:171P =0123...K−1KB EC D G0G2 G1 G0G2 G1 G0... ... ...G2 G1 G′0G′2 G′1. (5.6)To proceed further, let us define a set of matricesU(k)(0≤k≤MZ) as follows:U(k)i,j =Si,j if i = k0, if i̸= kwhere 0≤i,j≤MZ.With these matrices defined, we can derive the inner submatrices of P in (3.14) asfollows:A(0)0 = α0S; A(0)d+ = αdS,1≤d≤N (5.7)A(e)d− =α0 ∑⌈e/b⌉≤j≤MZU(j), if d = e∑0≤j≤e−d−1;(j+d) mod b=0αjU(j+db ) + αe−d ∑⌈e/b⌉≤j≤MZU(j), if e−N ≤d≤e−1∑0≤j≤N;(j+d) mod b=0αjU(j+db ), if 1≤d < e−N,for 1≤e≤L−1.(5.8)172A(e)d+ =∑d≤j≤d+e−1;(j−d) mod b=0αjU(j−db ) + αd+e∑⌈e/b⌉≤j≤MZU(j),1≤d≤N,1≤e≤L−1 (5.9)A(e)0 =∑0≤j≤e−1;j mod b=0αjU(jb) + αe ∑⌈e/b⌉≤j≤MZU(j), if 1≤e≤N∑0≤j≤N;j mod b=0αjU(jb), if N < e≤L(5.10)Ad− =∑0≤j≤N;(j+d) mod b=0αjU(j+db ), if 1≤d < L−N∑0≤j≤L−d;(j+d) mod b=0αjU(j+db ), if L−N ≤d < L(5.11)Ad− =∑0≤j≤N;(j+d) mod b=0αjU(j+db ),1≤d≤L (5.12)Ad+ = ∑d≤j≤N;(j−d) mod b=0αjU(j−db ),1≤d≤N(5.13)173A0 =∑0≤j≤N;j mod b=0αjU(jb); G′0 =[G0 0LMZ×K′MZ](5.14)G′1 =A0 A1+ ··· AN+A1− A0 A1+ ··· AN+... ... ...A(L−N+K′)− ··· ··· ··· A′(N−1)+... ... ...AL− ··· ··· ··· ··· A′(K′−1)+... ... ...AL− ··· ··· ··· A′1+AL− ··· ··· A′0(5.15)A′0 =∑0≤j≤N∑0≤h≤j;h mod b=0αjU(hb) (5.16)A′k+ =∑k≤j≤N∑0≤h≤j−k;h mod b=0αjU(hb),1≤k≤N−1 (5.17)174G′2 = G20K′MZ×LMZ, (5.18)where K′ = Q−⌊Q/L⌋.5.3.4 Matrix-Analytic Solution for Steady State DistributionsWith the system described by a QBD type Markov chain whose block matrices are derivedin the previous subsection, we can now apply matrix-analytic method [29] to find its steadystate probability vectorπ. For the detailed procedure to calculateπ, we refer the readersto [29]. By blocking the entries in π according to the associated queue lengths, we canwrite the steady state probability vector asπ, [π0,π1,π2,···,πQ], whereπi stands forsteady state probability vector associated with a queue length of i (0≤i≤Q).5.3.5 Derivation of Performance MeasuresAfter obtaining the steady state probability vector for queue length, we can determine anumber of performance measures of interest at the MAC layer. We are mainly interested inthe following three important performance measures: packet loss rate, average throughput,and the distribution of access delay for packets in the tagged queue. We denote by accessdelaythetimebetweenthemomentapacketarrivesatthequeueandthemomentthepacketgets access into the medium for transmission.Delay DistributionThe delay distribution for a packet in the tagged user queue is derived by considering anabsorbing Markov chain. The chain initializes from the state when a packet arrives at the175corresponding queue and gets absorbed in the states associated with the transmission of thepacket. Note that, in this case, there is no arrival in that particular queue while the processmoves towards the absorbing state. Therefore, the transition matrix Pabs of the chain canbe constructed by setting α0 = 1 and αi = 0 (1≤i≤N). The next step for finding thedelay distribution is to determine the initial probability vector for this absorbing Markovchain. To this end, we first consider the probability vector associated with the number ofpackets including the arriving packet, and the packets ahead of it as seen by the arrivingpacket. This probability vectorξ(0) =[ξ(0)0 ,ξ(0)1 ,···,ξ(0)Q+N]can be derived as:ξ(0)h =0, if h = 011−α0[h∑i=1i∑j=1MZ∑k=0αii πh−j+bkU(k) + N∑i=h+1h∑j=1MZ∑k=0αii πh−j+bkU(k)], if 1≤h≤N11−α0[N∑i=1i∑j=1MZ∑k=0αii πh−j+bkU(k)], if N < h≤Q−L + 111−α0 N∑i=1i∑j=1∑0≤k≤Q−h+j;k mod b=0αii πh−j+kU(kb), if Q−L + 1 < h≤Q11−α0 N∑i=h−Qi∑j=h−Q∑0≤k≤Q−h+j;k mod b=0αii πh−j+kU(kb), if Q < h≤Q + N(5.19)Note that the packets which find their destination queues full upon arrival are not admit-ted into the system. The probability that an arriving packet finds the corresponding queuefull can be written as: pfull =N∑i=1ξ(0)Q+i.Since we consider the delay experienced by the admitted packets only, the initial prob-176ability vectorω(0) ,[ω(0)0 ,ω(0)1 ,···,ω(0)Q]of the absorbing Markov chain is derived fromthe above probability vectors as follows:ω(0)i = ξ(0)i1−pfull,0≤i≤Q (5.20)which is due to the fact that an arriving packet seeing a full queue will be dropped andconsequently, will not be considered in the delay calculation. After d time slots the statevectoroftheabsorbingchainisω(d) =ω(0)Pdabs,wherePdabs isthetransitionmatrixderivedbymultiplyingPabs withitselfdtimes. Thecumulativedistributionfunction(cdf)ofpacketdelay D is given by: FD(d) =ω(d)0 1.Packet Loss Rate and Average ThroughputA packet loss occurs when a packet finds the queue full upon arrival or when a packet isreceived in error in the receiver. Assuming that no error recovery protocol is used, thepacket loss rate, ploss can be found as: ploss = 1−(1−pfull)(1−PER). The averagethroughput η in packets per time slot can then be calculated as: η = λ(1−ploss).5.4 Numerical Results and DiscussionsUsing the queueing analytical model, the MAC layer QoS performance measures for atagged CR user are obtained considering PHY as well as some other system parameters(e.g., primary users’ activity level, number of radio channels, number of CR users). Unlessotherwisespecifiedinthefollowingsubsections,wealsoassumetheparametervalueslistedbelow:• Duration of a time slot, Tf = 2ms, packet size, Lp = 1080 bits177• Doppler spread, fd = 15 Hz, average SNR = 15 dB, Nakagami fading parameter,m = 1.1• Number of channels, M = 12, number of CR users = 10, buffer size, Q = 30 packets• Packet arrival probability vector, α = [0.0,0.3,0.4,0.3], primary user activity factor,θ = 0.5Each of the channels are modeled by an FSMC derived for targetPER = 1%; all the chan-nels are assumed to be homogeneous in terms of their fading characteristics. We use MAT-LAB to code and execute the different steps in the development of the queueing model.5.4.1 Primary User Activity LevelWe capture the activity level of primary users by occupancy matrix derived from two pa-rameters: θ and the average occupancy duration t of primary users on a given channel. Forexample, with an activity factor θ = 0.6 and average occupancy duration of t = 5 timeslots, the occupancy matrixPo will be 0.8 0.20.3 0.7.Fig. 5.2 shows the effect of primary user activity level on packet delay distribution ofthe CR user. As expected, the delay performance deteriorates when the primary users’activity factor or the average occupancy duration increases. The effect of the average oc-cupancy duration, however, is not very prominent in the figure when θ = 0.4 and becomesmuch more significant with θ = 0.8 than with θ = 0.6. Therefore, the average occupancyduration tends to affect the delay performance more when the activity factor is higher.Fig. 5.3 shows the relationship between packet loss rate at the CR user end and the activitylevel of the primary users. The packet loss rate increases rapidly with increasing value of1780 15 30 45 60 75 90 105 12000.10.20.30.40.50.60.70.80.91d (time slots)prob.(delay≤d)  θ = 0.4, t = 3 slotsθ = 0.4, t = 6 slotsθ = 0.6, t = 3 slotsθ = 0.6, t = 6 slotsθ = 0.8, t = 3 slotsθ = 0.8, t = 6 slotsFigure 5.2: Effect of primary user activity level on packet delay distribution of CRusers.θ. There is also a positive correlation between packet loss rate and the average occupancytime. However, the effect is much less significant than that of the activity factor.5.4.2 Number of Channels Available for CR UsersFigs. 5.4-5.5 show the delay and packet loss performances, respectively, with varying num-ber of available channels. As expected, given the primary users’ activity level and othersystem parameters remain unchanged, both delay and packet loss performance improvewith increasing number of channels. The effect on packet loss rate, however, diminishesgradually once the number of channels becomes high enough to provide adequate radioresource to serve the waiting packets without causing any buffer overflow.1790.1 0.2 0.3 0.4 0.5 0.6 0.7 0.810−210−1100activity factor θpacketlossrate  t = 3 slotst = 6 slotst = 9 slotsFigure 5.3: Effect of primary user activity level on packet loss rate of CR users.5.4.3 Channel FadingThe analytical model enables use to demonstrate the effect of channel fading on MAClayer performance. Fig. 5.6 and Table 5.1 show how the delay distribution and packet lossrate vary with Doppler spread and average SNR. At higher Doppler spread, the channelstate for a CR user will change more rapidly over time. This phenomenon in conjunctionwith the scheduling scheme will make it less likely that a particular user can monopolizethe channel for a long time. The tagged user will thus have more probability of access tothe channel. Consequently, it will have more opportunities to reduce its queue backlog.A reduced backlog implies smaller delay for the incoming packets. Moreover, with theless probability of queue size reaching the buffer limit, the packet loss rate drops, andsubsequently, the average throughput improves.1800 25 50 75 100 125 150 175 20000.10.20.30.40.50.60.70.80.91d (time slots)prob.(delay≤d)  Number of channels = 4Number of channels = 8Number of channels = 12Figure 5.4: Effect of number of cognitive channels on packet delay distribution of CRusers.Table 5.1: Effect of channel fading on the packet loss rate of CR users.Doppler spread Average SNR Packet loss rate15 Hz 10 dB 12.3%15 Hz 15 dB 4.7%30 Hz 10 dB 9%30 Hz 15 dB 1.9%The effect of the Doppler spread in the CR network, however, is less profound thanits expected effect in a traditional (i.e. not cognitive) cellular network that uses multiuserdiversity for opportunistic scheduling. This observation can be explained as follows. Theprimary user occupancy in a channel that is currently assigned to a CR user makes thechannel unavailable to the CR user for some time slots. As a result, the correlation in1814 6 8 10 12 14 16 18 2010−210−1100Number of cognitive channelsPacket loss rateFigure 5.5: Effect of number of cognitive channels on packet loss rate of CR users.the channel fading diminishes by the time the channel is assigned back to the same CRuser. The fading correlation remains effective for the CR user as long as the channel isnot reoccupied by some primary user. The average SNR of the homogenous channels hasmore direct effect on the delay and packet loss performances, both of which improve withincreasing SNR.5.4.4 Number of Admitted CR UsersThe queueing model also allows us to investigate quantitatively the effects of the numberof admitted users in the CR network on the QoS experienced by our tagged user. Fig. 5.7shows how the delay distribution varies with different number of users admitted to the sys-1820 10 20 30 40 50 60 70 8000.10.20.30.40.50.60.70.80.91d (time slot)prob.(delay≤d)  SNR = 10 dB, fd = 15 HzSNR = 15 dB, fd = 15 HzSNR = 15 dB, fd = 30 HzFigure 5.6: Effect of channel fading on the packet delay distribution of CR userstem, given the system and traffic parameters stated earlier in the section. As expected, moreusers in the system create more competition, and therefore, longer packet delays are expe-rienced. Similar observations can be made for the packet loss rate as shown in Fig. 5.8.Such relationships, however, can be drawn using our model for different values of systemparameters such as primary user occupancy, number of available CR channels, channel fad-ing, the characteristics of the packet arrival process of the applications requesting service.This can be very useful in deciding how many users could be supported for a given systemcondition and traffic parameters.1830 10 20 30 40 50 60 70 80 90 100 110 120 130 14000.10.20.30.40.50.60.70.80.91d (time slots)prob.(delay≤d)  Number of CR users = 4Number of CR users = 8Number of CR users = 12Number of CR users = 16SimulationFigure 5.7: PacketdelaydistributionfordifferentnumberofCRusersinthecognitiveradio network.5.4.5 Queueing Model ValidationTo validate our analytical model, we developed a discrete-event simulator using Matlab. Ateach time slot, the availability and channel state for each cognitive channel are generatedrandomly according to a channel occupancy matrix and FSMC transition probability ma-trix respectively. These matrices and the parameters for packet arrival process at each userqueue are selected to be same as those used in obtaining the numerical results. The AMCscheme used to link channel states with the maximum number of packet transmission overa channel during a time slot is also selected to be identical to the one adopted in the ana-lytical model. For the purpose of comparison, we have included two representative sets of1844 6 8 10 12 14 16 18 2010−310−210−1100number of userspacket loss rate  Analysis      SimulationFigure 5.8: Packet loss rate for different number of CR users in the cognitive radionetwork.simulation results in Fig. 5.7 and 5.8 beside the analytical results for a tagged user. Clearly,the presented simulation results match very closely with the corresponding analytical find-ings. We are, therefore, very confident about the validity of the analytical model presentedin this chapter.5.5 Application of the Queueing ModelThe queueing model has important applications for system engineering in CR networks.Two example applications of the model are as follows:• The model allows to gauge beforehand the level of QoS the system can entertain for anewincoming connection giventhe resource constraints and operating environments.185Therefore, the model output can also be used by the cognitive radio BS in QoS nego-tiation for new connections arriving from the CR users. The QoS negotiation usuallyinvolves a counter offer by the BS in response to the QoS level demanded by an in-coming connection request. The BS can make use of the output from the queueingmodel to furnish the counter offer.• The queueing model can be utilized in a model-based admission controller design.When a CR user wants to establish a new connection for an application or service,the admission controller at the BS can be assisted by the output from the queueingmodel to make an admission decision. The model output can determine whether therequired QoS of the new and existing users can be met given the number of activeusers in the system. If the QoS of the requested and existing users cannot be met, theconnection request may be refused, or can be accepted otherwise. For example, inFig. 5.8, with the given parameter values used to find the relationship between packetlossrateandthenumberofusersinthesystem, only10CRuserscanbeservedwithatarget packet loss rate of 5%. If the system is already serving 10 active users at somepoint in time, the admission controller could refuse admission of a new connectionon the basis of the achievable packet loss rate determined by the queueing model.5.6 ConclusionsIn this chapter, we have developed a queueing analytic framework to study the performanceof opportunistic spectrum access by CR users in a dynamic spectrum access network. Wehave derived important QoS measures by modeling primary users’ activity as a two stateMarkov chain and CR users’ channel quality variation as a finite state Markov chain. Inorder to allocate available spectrum opportunities among the CR users, a channel-quality-186based opportunistic scheduling scheme has been considered. The proposed framework hasimportant applications including cross-layer analysis and design for system engineering,and model-based admission control in CR-based broadband wireless access networks. Anumber of practical issues could be considered in extending the model presented in thischapter. Examples of such issues include more practical modeling of primary user activity,considering heterogeneous channel characteristics across users, and modeling for differentmultiuser diversity and channel access scheduling schemes.1875.7 Bibliography[1] R. W. Broderson, A. Wolisz, D. Cabric, S. M. Mishra, and D. Willkomm, “CORVUS:A cognitive radio approach for usage of virtual unlicensed spectrum,” white papersubmitted at the University of Berkeley, CA, Jul. 2004.[2] Federal Communications Commission, “Spectrum Policy Task Force,” Rep. ETDocket no. 02-135, Nov. 2002.[3] J. Mitola, “The software radio architecture,” IEEE Communications Magazine, vol.33, pp. 26-38, May 1995.[4] N. Devroye, P. Mitran and V. Tarokh, “Achievable rates in cognitive radio,” IEEETransactions on Information Theory, vol. 52, no. 5, pp. 1813-1827, May 2006.[5] S. A. Jafar and S. Srinivasa, “Capacity Limits of Cognitive Radio with Distributedand Dynamic Spectral Activity,” IEEE Journal on Selected Areas in Communications,vol. 25, no. 3, pp. 529-537, Apr. 2007.[6] S. Srinivasa and S. A. Jafar, “The Throughput Potential of Cognitive Radio: A Theo-retical Perspective,” IEEE Communications Magazine, vol. 45, pp. 73-79, May 2007.[7] Z. Ji and K. J. R. Liu, “Dynamic Spectrum Sharing: A Game Theoretical Overview,”IEEE Communications Magazine, vol. 45, no. 5, pp. 88-94, May 2007.[8] W.-Y. Lee and I. F. Akyildiz, “Optimal Spectrum Sensing Framework for CognitiveRadio,” IEEE Transactions on Wireless Communications, vol. 7, no. 10, pp. 3845-3857, Oct. 2008.188[9] H. Jiang, L. Lai, R. Fan, and H. V. Poor, “Optimal Selection of Channel Sensing Orderin Cognitive Radio,” IEEE Transactions on Wireless Communications, vol. 8, no. 1,pp. 297–307, Jan. 2009.[10] L. B. Le and E. Hossain, “OSA-MAC: A Multi-Channel MAC Protocol for Oppor-tunistic Spectrum Access in Cognitive Wireless Networks,” Proc. IEEE Wireless Com-munications and Networking Conference, Las Vegas, Nevada, USA, Apr. 2008.[11] Q.Zhao, L.Tong, A. Swami, and Y.Chen, “DecentralizedCognitiveMACfor Oppor-tunistic Spectrum Access in Ad Hoc Networks: A POMDP Framework,” IEEE Journalon Selected Areas in Communications, vol. 25, no. 3, pp. 589-600, Apr. 2007.[12] J. Jia, Q. Zhang, and X. Shen, “HC-MAC: A Hardware-Constrained Cognitive MACfor Efficeint Spectrum Management,” IEEE Journal on Selected Areas in Communica-tions, vol. 26, no. 1, pp. 106-117, Jan. 2008.[13] H. Su and X. Zhang, “Cross-Layer Based Opportunistic MAC Protocols for QoSProvisioning over Cognitive Radio Wireless Networks,” IEEE Journal Selected Areasin Communications, vol. 26, no. 1, pp. 118-129, Jan. 2008.[14] C. Doerr, M. Neufeld, J. Fifield, T. Weingart, D. C. Sicker, and D. Grunwald, “Mul-tiMAC: An Adaptive MAC Framework for Dynamic Radio Networking,” Proc. IEEEInternational Dynamic Spectrum Access Networks, Baltimore, MD, USA, Nov. 2005.[15] O. Simeone, Y.Bar-Ness and U. Spagnolini, “Stable Throughput of CognitiveRadioswith and Without Relaying Capability,” IEEE Transactions on Communications, vol.55, no. 12, pp. 2351-2360, Dec. 2007.189[16] S. Shankar, “Squeezing The Most out of Cognitive Radio: A Joint MAC/PHY Per-spective,” Proc. IEEE ICASSP’07, Honolulu, Hawaii, USA, Apr. 2007.[17] L.-C. Wang, Y.-C. Lu, C.-W. Wang, and D. S. L. Wei, “Latency Analysis for Dy-namic Spectrum Access in Cognitive Radio: Dedicated or Embedded Control Chan-nel?,” Proc. Personal, Indoor and Mobile Radio Communications Symposium , Athens,Greece, Sept. 2007.[18] S. Keshavamurthy and K. Chandra, “Multiplexing Analysis for Dynamic SpectrumAccess,” Proc. IEEE , Washington, DC, USA, Oct. 2006.[19] S. Tang and B. L. Mark, “Performance Analysis of a Wireless Network with Oppor-tunistic Spectrum Sharing,” Proc. IEEE Global Communications Conference, Wash-ington, DC, USA, Nov. 2007.[20] D. Niyato and E. Hossain, “Medium Access Control Protocols for Dynamic SpectrumAccess in Cognitive Radio Networks: A Survey,” invited chapter in Cognitive RadioNetworks, (Eds. Y. Xiao and F. Hu), Auerbach Publications, CRC Press, 2008.[21] N. Baldo and M. Zorzi, “Fuzzy Logic for Cross-Layer Optimization in CognitiveRadio Networks,” IEEE Communications Magazine, vol. 46, no. 4, pp. 64-71, Apr.2008.[22] X. Liu, E.K.P. Chong, and N.B. Shroff, “A Framework for Opportunistic Schedulingin Wireless Networks,” Computer Networks, vol. 41, no. 4, pp. 451474, Mar. 2003.[23] Q. Liu, S. Zhou, and G. B. Giannakis, “Queuing with Adaptive Modulation andCoding over Wireless Link: Cross-Layer Analysis and Design,” IEEE Transactions onWireless Communications, vol. 4 , pp. 1142-1153, May 2005.190[24] Z. Han and H. Jiang, “Replacement of Spectrum Sensing and Avoidance of HiddenTerminal for Cognitive Radio,” Proc. IEEE Wireless Communications and NetworkingConference, Las vegas, NV, USA, Mar.-Apr. 2008.[25] M. Nakagami, “The m-Distribution–A General Formula of Intensity Distribution ofRapid Fading,” Statistical Methods in Radio Wave Propagation, Oxford, UK: Perga-mon, pp. 3-36, 1960.[26] H. S. Wang and N. Moayeri, “Finite-State Markovchannel-A Useful Model for RadioCommunication Channels,” IEEE Transactions on Vehicular Technology, vol. 44, pp.163-171, Feb. 1995.[27] R. Knopp and P. A. Humblet “INformation Capacity and Power Control in Single-Cell Multiuser Communications,” Proc. IEEE International Conference on Communi-cations, Seattle, WA, USA, Jun. 1995.[28] T. Issariyakul and E. Hossain, “ORCA-MRT: An Optimization-Based Approach forFair Scheduling in Multi-Rate Tdma Wireless Networks,” IEEE Transactions on Wire-less Communications, vol. 4, no. 6, pp. 2823-2835, Nov. 2005.[29] M. F. Neuts, “Matrix Geometric Solutions in Stochastic Models–An AlgorithmicApproach,” John Hopkins Univ. Press, Baltimore, MD, 1981.191Chapter 6Conclusions and Future ResearchDirections6.1 ConclusionsIn this thesis, we have developed a number of useful analytical models for resource al-location schemes in emerging broadband wireless access networks. The models not onlyprovide insight into the intricate relationship between the system as well as traffic param-eters and the achievable QoS at user ends, but also provide framework for new resourceallocation solutions for these networks. In particular, we have made following four majorcontributions in this thesis.First, we have proposed a novel model-based resource allocation framework for down-link service flows in IEEE 802.16e mobile WiMAX systems. At first, we have developeda queueing analytical model that relates important performance measures of an admittedservice flow to its packet arrival statistics and a parameter in the packet scheduling scheme.Referring to this parameter as the model parameter for the service flow, we have demon-192strated how the output from the queueing model can be utilized to set the appropriate valuefor this model parameter. This value of the model parameter essentially allows to computethe minimum number of packets that need to be scheduled from the queue of the serviceflow in order to meet its QoS requirement. Each admitted service flow is associated with amodel parameter. Next, we have proposed a cross-layer adaptive and queue-aware resourceallocation scheme that utilizes these parameter values along with the channel quality andbacklog information to schedule packets and allocate OFDMA slots among downlink QoSconnections. The proposed model-based approach offers simplicity of design for the on-line component, flexibility to the service providers in defining QoS parameters and bettercompatibility to the IEEE 802.16e standard. Instead of complexities involved with in-stalling separate scheduling schemes within the same resource allocation framework forreal-time and non-real-time traffic, our model-based approach offers an efficient unifiedway to handle both types of traffics and their diverse QoS requirements. We have runsimulation experiments to evaluate the performance of our proposed scheme in providingQoS for VBR real-time and non-real-time multimedia and data services. Compared to EDFscheduling, which is specialized for allocating resource to delay-sensitive applications, ourproposed scheme significantly reduces delay violation probability and packet loss rate forreal-time services. As a result, the number of real-time service flows that can be supportedby the system is also improved considerably. For non-real-time services, our proposedscheme achieves much better packet loss rate performance and can support significantlymore service flows compared to throughput conscious WDRR scheduling. We have alsoshown that, even without priority-based or complex hierarchical approach, our proposedscheme can successfully protect QoS of individual service flows in a heterogenous trafficscenario involving both real-time and non-real-time services. The work has been submitted193for publication [1].Second, we have developed a queuing analytic model for cross-layer analysis of down-linktransmissionsinaV-BLASTMIMOsystemexploitingmultiuserdiversity. TheMIMOchannel in the V-BLAST system is decomposed into subchannels associated with the trans-mit antennas and the users are then allocated the transmit antennas opportunistically basedon the received SNR on the associated subchannels. The queuing model is developedconsidering the system dynamics resulting from the scheduling mechanism, fading in theMIMO channel, and the traffic arrival process. The transmit antenna correlation in the basestation and the possibility of bursty traffic arrival are also factored into the model. Afterdeveloping the queuing model, we elaborate the steps to compute important QoS perfor-mance measures including the delay distribution, throughput, and packet loss performanceat the MAC layer. We also present selected numerical results that show cross-layer effectsof the physical layer parameters as well as the effects of the traffic arrival statistics and thenumber of users in the system on the MAC layer performance. The queuing model hasimportant applications in the QoS provisioning framework for a V-BLAST MIMO systemas the model output can be used in admission control, QoS negotiation and setting propervalues for QoS relevant parameters. This work has been published in [2].Third, we have formulated an analytical model for the controlled channel access mech-anism (also called HCCA) in IEEE 802.11e based WLANs considering VBR traffic ap-plications. The model enables us to derive important performance measures in terms ofthe parameters used in the reference scheduler. The results obtained from the analyticalmodel have shown that the QoS guarantees for VBR traffic cannot be met without adaptingthe transmission opportunities properly. Using the insights gained into the cause of theproblems in the reference scheduler, we have developed a novel HCCA scheduler for IEEE194802.11e WLANs. The proposed scheduler adapts dynamically with dynamic traffic inten-sities that may arise from multimedia applications. The proposed PRO-HCCA schedulerutilizes simple but smart prediction mechanism along with an efficient online optimizationprocess. Simulation experiments have shown that the PRO-HCCA scheduler achieves ex-tremely robust and stable performance in meeting the QoS guarantees for VBR traffic. Forrelated publications to this work, please refer to [3, 4, 5].Inthefinalcontributionofthisthesis, weexpandedouranalyticalmodeling tocognitiveradiotechnologythathasthepotentialtosignificantlyincreasespectrumutilizationinwire-less broadband access networks. The cross-layer analytic model captures dynamic resourceavailability due to opportunistic access of radio spectrum by cognitive users in presence ofprimary users activity in the spectrum. It allows to relate channel characteristics, trafficparameters and other important system parameters with the achievable QoS performancefor cognitive users. Later, we show a number of application of the model including cross-layer system engineering and model-based admission control. For publications related tothis work, please refer to [6, 7].6.2 Future ResearchThe analytical models and resource allocation solutions developed in this thesis not onlyhave far reaching important applications for system designers of emerging broadband wire-less services, but also open up interesting possibilities of future research. In the following,we list some important future research directions that can follow from this thesis.1956.2.1 Models for End-to-End QoS in Multihop Wireless BroadbandNetworksIn this thesis, we focused on single-hop wireless broadband systems; a natural extensionwould be to consider multihop architectures. An interesting future research will be toextend our analytical models to wireless mesh networks [8], which can form broadbandwireless access with radio nodes organized in a mesh topology. Such networks can be builtwith various broadband wireless technology including 802.11, 802.16, cellular or combi-nations of more than one type. Another very widespread scenario of multihop broadbnadwireless access networks would be where WMAN will be used to bring broadband serviceto a premise where WLAN will be the technology used for distributing the access acrossthe premise. In such systems, a multihop modeling for end-to-end QoS will be required.One idea would be to use tandem queue modeling in which output process from the queuerepresenting one hop is modeled as the input process to the queue representing the next hopin the route connecting the communicating nodes [9]. Besides providing important inputsin designing resource allocation schemes for these multihop systems, these models canbe useful in assessing the performance and selecting paramer values of the interoperationmodules in heterogeneous systems. Besides, the models can be utilized to design novelmodel–based schemes to map QoS parameters between one part of the multihop networkto the other part that implementing a different broadband wireless technology. The ultimategoal will be devise better resource managment schemes for providing end-to-end QoS inmultihop broadband wireless access networks.1966.2.2 Cross-Layer Models for Various Multiuser MIMO SystemsIn Chapter 3, we analyzed a multiuser V-BLAST MIMO system with the assumption ofa zero-forcing receiver, that offered several benefits in terms of performance in multiuserschduling as well as in our analytical modeling. As an extension to this work, we planto consider other receiver schemes such as MMSE and SIC-based detection in our cross-layer analytical model. One of the challenges will be the fact that there is no closed-form expression available for post detection SNR for these receiver schemes. We willinvestigate how we can address this issue in our modeling. In the transmitter side, it willalso be interesting to explore the effect of power control instead of adaptive modulation andcoding. This is because power control is more widely employed in many practical wirelesssystems. Aside from these, we plan to explore other multiuser scheduling and antennaassignment schemes than the independent stream scheduler assumed in the analysis donein Chapter 3. Besides the V-BLAST system considered in our work, there is opportunityfor analyzing other multiuser MIMO systems employing various transmitter and receivertechniques. Therefore, the work presented in this thesis on V-BLAST MIMO systems mayserve as a good starting point for many exciting avenues for future research.6.2.3 Analyzing Effects of CQI Feedback IssuesIn this thesis, we have assumed perfect CQI and zero feedback delay in the queueing mod-els. Suchassumptionshaveverylimitedimpactin slowfadingand/orslowmobilityscenar-ios. However, the effects of imperfect CQI and feedback delay may become pronounced inhigh mobility or fast fading scenarios [10] and need to be considered in the model. To min-imize potential negative effects, many feedback mechanism and link adaptation schemeshave been developed [11]. An exciting future research will be to analyze the cross-layer197effects of imperfect CQI and delayed feedback on these schemes and to use the findings toimprove their designs as well as to develop better schemes. Another interesting researchissue to consider would be to analyze the effects of CQI feedback overhead on potentialthroughput degradation in different broadband wireless access networks and to utilize thefindings to design low-overhead CQI feedback mechanisms.6.2.4 Enhanced Queueing and Game Theoretical Models forSpectrum Sharing in CR-based Wireless Broadband SystemsSharing of spectrum resources by primary user networks with cognitive users is often dic-tated by perceived utility from such sharing. From a cognitive users’ perspective, the morespectrum that it can opportunistically access, the more it has the potential to improve theQoS of its applications. However, for primary user networks, although allowing more ac-cess might mean more potential revenue (if cognitive access is given for a price), increasedinterference to primary users might lead to user dissatisfaction and lost revenue. In suchsituations, where the primary user network and cognitive users are not likely to be centrallycontrolled by a single entity, game theoretic models can be useful to devise new spectrumsharing strategies. In devising these strategies, the queueing model developed in this thesiscould be useful at the CR network end as the derivation of perceived utility can utilize themodel output on performance measures. In this thesis, however, we developed the queue-ing model from the perspective of cognitive users only. Another avenue of research wouldbe to develop queuing models from PU network perspective, where the effect of spectrumsharing with secondary users can be analyzed given certain access behaviour of cognitiveusers. These models, in turn, can be used in game theoretic analysis.1986.3 Bibliography[1] M. M. Rashid and V. K. Bhargava, “A Model-Based Downlink Resource AllocationScheme for IEEE 802.16e Mobile WiMAX,” Submitted to IEEE Transactions on Ve-hicular Technology, Nov. 2009.[2] M. M. Rashid, E. Hossain, and V. K. Bhargava, “Cross-Layer Analysis of DownlinkV-BLAST MIMO Transmission Exploiting Multiuser Diversity,” IEEE Transactionson Wireless Communications, vol. 8, no. 9, pp. 4568–4579, Sep. 2009.[3] M. M. Rashid, E. Hossain, and V. K. Bhargava, “Controlled Channel Access Schedul-ing for Guaranteed QoS in 802.11e-Based WLANs,” IEEE Transactions on WirelessCommunications, vol. 7, no. 4, pp. 1287-1297, Apr. 2008.[4] M. M. Rashid, E. Hossain, and V. K. Bhargava, “HCCA Scheduler Design for Guaran-teed QoS in 802.11e Based WLANs,” Proc. IEEE International Wireless Communica-tions and Networking Conference, Hong Kong, Mar. 2007.[5] M. M. Rashid, E. Hossain, and V. K. Bhargava, “Queueing Analysis of 802.11e HCCAwith Variable Bit Rate Traffic,” Proc. IEEE International Conference on Communica-tions, Istanbul, Turkey, Jun. 2006.[6] M. M. Rashid, J. Hossain, E. Hossain, and V. K. Bhargava, “Opportunistic SpectrumScheduling for Multiuser Cognitive Radio: A Queueing Analysis,” IEEE Transactionson Wireless Communications, vol. 8, no. 10, pp. 5259-5269, Oct. 2009.[7] M. M. Rashid, J. Hossain, E. Hossain, and V. K. Bhargava, “Opportunistic Spec-trum Access in Cognitive Radio Networks: A Queueing Analytic Model and Admis-199sion Controller Design,” Proc. International Global Telecommunications Conference,Washington, DC, USA, Nov. 2007.[8] I. Akyildiz and X.Wang, “A Survey on Wireless Mesh Networks,” IEEE Communica-tions Magazine, vol. 43, no. 9, pp. s23-s30, Sep. 2005.[9] L. Le and E. Hossain, “Tandem Queue Models with Applications to QoS Routing inMultihop Wireless Networks,” IEEE Transactions on Mobile Computing, vol. 7, no. 8,pp. 1025–1040, Aug. 2008.[10] D. Tse and P. Viswanath, Fundamental of Wireless Communications, Cambridge Uni-versity Press, 2005.[11] D. J. Love, R. W. Heath, V. K. N. Lau, D. Gesbert, B.D. Rao, and M. Andrews, “AnOverview of Limited Feedback in Wireless Communication Systems,” IEEE Journalon Selected Areas in Communications, vol. 26, no. 8, pp. 1341-1365, Oct. 2008200

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0065882/manifest

Comment

Related Items