Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Quality of service provisioning for multimedia transmissions in packet-switched wireless communication.. Hui, Chen 2010

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

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
[if-you-see-this-DO-NOT-CLICK]
ubc_2010_fall_chen_hui.pdf [ 1000.63kB ]
Metadata
JSON: 1.0064780.json
JSON-LD: 1.0064780+ld.json
RDF/XML (Pretty): 1.0064780.xml
RDF/JSON: 1.0064780+rdf.json
Turtle: 1.0064780+rdf-turtle.txt
N-Triples: 1.0064780+rdf-ntriples.txt
Original Record: 1.0064780 +original-record.json
Full Text
1.0064780.txt
Citation
1.0064780.ris

Full Text

Quality of Service Provisioning for Multimedia Transmissionsin Packet-Switched Wireless Communication SystemsbyHui ChenB.Sc., Nanjing University, Nanjing, China, 1999M.Sc., Nanjing University, Nanjing, China, 2002A THESIS SUBMITTED IN PARTIAL FULFILMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinTHE FACULTY OF GRADUATE STUDIES(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)August, 2010c Hui Chen, 2010iiAbstractThis thesis covers several research problems in the area of multimedia transmissions over wirelesscommunication systems. The objective is to enhance the quality of service (QoS) provisioningfor multimedia transmissions over wireless communication systems. Recent advances in signalprocessing techniques have enabled wireless networks to have multi-packet reception (MPR)capability at the physical layer, where it is possible to receive more than one packet whenconcurrent transmissions occur. In this thesis, a multi-reservation, multiple access (MRMA)scheme for wireless multimedia networks, based on an MPR channel model, is proposed todifierentiate the QoS provisioning for multimedia tra–c and best efiort tra–c on MPR-enabledchannels. Another advance in recent wireless technologies is the cross-layer optimization overwireless links. In this thesis, a cross-layer QoS provisioning method is proposed. Speciflcally, thedata frame drop ratio (FDR) in the medium access control layer and the bit error rate (BER) inthe physical layer are jointly optimized to provide a better data frame loss ratio (FLR) seen bythe higher layers. In this thesis, a cross-layer enhanced scheduling (CEPS) method is proposedfor providing QoS optimization for multimedia tra–c in multi-code code-division multiple access(MC-CDMA) systems. CEPS also provides  exible fairness provisioning among difierent tra–c ows. Then, the cross-layer QoS FLR in the MC-CDMA systems is further optimized byaccounting for not only the predesigned QoS requirements, the historical QoS experienced,Abstract iiiand the current bufier status, but also the statistical tra–c models of difierent tra–c  ows.Results show that the system performance and the QoS provisioning can be greatly improvedby the cross-layer QoS consideration and the proposed optimizations. The thesis also adoptsthe cross-layer QoS consideration in adaptive modulation and coding (AMC)-enabled wirelesssystems. A QoS-based cross-layer scheduling scheme (QoS-CLS) is proposed for AMC-basedsystems. It can guarantee the QoS provisioning for multimedia tra–c  ows and/or share theQoS among difierent tra–c  ows by making scheduling and coding/modulation decisions basedon the bufier status, tra–c status, channel status, and other information for difierent tra–c ows. Results show that QoS-CLS can greatly enhance the system performance.ivContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiContents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivCo-Authorship Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Quality of Service of Multimedia Transmissions . . . . . . . . . . . . . . . . . . . 21.2 Multiple Access with Multi-Packet Receptions . . . . . . . . . . . . . . . . . . . . 51.3 Scheduling Algorithm for Multi-Code CDMA . . . . . . . . . . . . . . . . . . . . 61.4 Cross-Layer Optimization of Quality of Service . . . . . . . . . . . . . . . . . . . 81.5 Opportunistic Scheduling and Adaptive Modulation and Coding . . . . . . . . . 101.6 Summary of Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.7 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17Contents vBibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 A Novel Multiple Access Scheme over MPR Channels for Wireless Multime-dia Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.2 MPR Channel Model and Tra–c Models . . . . . . . . . . . . . . . . . . . . . . . 352.2.1 MPR Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.2.2 Tra–c Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.3 Multi-Reservation Multiple Access Scheme . . . . . . . . . . . . . . . . . . . . . . 382.3.1 Frame Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382.3.2 Basic Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392.3.3 Random Access Scheme for MPR Channel . . . . . . . . . . . . . . . . . . 402.3.4 Slot Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412.3.5 QoS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 432.3.6 Preventing Lost and Endless Reservations . . . . . . . . . . . . . . . . . . 452.3.7 Other Enhancements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.4 Analytical Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462.5 Results and Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663 CEPS for Multimedia Tra–c over MC-CDMA Networks . . . . . . . . . . . . 693.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 713.2 Multicode CDMA System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72Contents vi3.3 System Model and Principle of CEPS . . . . . . . . . . . . . . . . . . . . . . . . 743.3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 753.3.2 Basic Concept of the Cross-Layer Enhancement . . . . . . . . . . . . . . . 783.3.3 Fairness Requirement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803.3.4 Objective Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 833.4 The Proposed CEPS Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853.4.1 Basic Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853.4.2 Stage 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 873.4.3 Stage 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 883.4.4 Stage 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 893.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 903.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1084 Cross-Layer Optimization for Multimedia Transport over MC-CDMA Net-works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1124.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1144.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1164.2.1 Multicode CDMA System . . . . . . . . . . . . . . . . . . . . . . . . . . . 1164.2.2 MMPP Tra–c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1174.3 System Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1184.3.1 Maximum Number of Simultaneous Transmissions . . . . . . . . . . . . . 1194.3.2 Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120Contents vii4.3.3 Slot Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1224.4 Tra–c Adaptive Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1234.4.1 Queue Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1244.4.2 The Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1274.4.3 QoS Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1304.4.4 Limitation and Approximation . . . . . . . . . . . . . . . . . . . . . . . . 1324.5 Results and Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1344.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1445 A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissionswith AMC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1485.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1505.2 System Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1535.3 Basic System Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1575.4 Markov Decision Process for Scheduling and AMC Mode Selection . . . . . . . . 1625.4.1 State Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1625.4.2 Decision Epochs and Actions . . . . . . . . . . . . . . . . . . . . . . . . . 1635.4.3 State Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1635.4.4 Policy, Performance Criterion and Cost Function . . . . . . . . . . . . . . 1635.4.5 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1645.4.6 Linear Programming Solution to The MDP . . . . . . . . . . . . . . . . . 1655.5 Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166Contents viii5.5.1 Reduced Bufier State Space . . . . . . . . . . . . . . . . . . . . . . . . . . 1665.5.2 Decomposition of The Optimization . . . . . . . . . . . . . . . . . . . . . 1685.6 Results and Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1695.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1846 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1896.1 Summary of Work Accomplished . . . . . . . . . . . . . . . . . . . . . . . . . . . 1896.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197A Calculations for State Transition Probabilities for MRMA . . . . . . . . . . . 197A.1 Calculation of The Transition Probability T1 . . . . . . . . . . . . . . . . . . . . 197A.2 Calculation of The Transition Probability T2 . . . . . . . . . . . . . . . . . . . . 198B List of Publications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200ixList of Tables1.1 ITU-T Recommendations for Multimedia QoS Target . . . . . . . . . . . . . . . 182.1 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.1 Parameters for The System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 973.2 Typical QoS Parameters Setting (Setting 1) for Difierent Tra–c Classes in ThisChapter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 983.3 Another QoS Parameters Setting (Setting 2) for Difierent Tra–c Classes in ThisChapter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 995.1 Parameters for Modulation and Coding Pairs in AMC . . . . . . . . . . . . . . . 1755.2 List of Important Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175xList of Figures2.1 Frame structure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592.2 AveragenumberofslotsneededfordifierentinitialnumbersofUTstosuccessfullysend requests when the permission probability varies from 0.05 to 1. . . . . . . . 592.3 State transition graphs at the frame boundary and within a frame. . . . . . . . . 602.4 Comparison of analytical and simulation results for voice. . . . . . . . . . . . . . 612.5 Comparison of voice packet loss ratio for MRMA and FPLS. . . . . . . . . . . . 612.6 Comparison of video packet loss ratio for MRMA and FPLS. . . . . . . . . . . . 622.7 Packet loss ratio in a voice/video system with 100 voice UTs and difierent numberof video UTs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622.8 Packet loss ratio in a voice/video system with 15 video UTs and difierent numberof voice UTs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632.9 Packet loss ratio in a multimedia system with 90 voice UTs and 10 video UTs(SNR=10). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632.10 Throughput in a multimedia system with 90 voice UTs and 10 video UTs. . . . . 642.11 Average data access delay in a multimedia system with 90 voice UTs and 10video UTs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64List of Figures xi2.12 Packet loss ratio with 90 voice UTs, 10 video UTs and 90 or 150 data UTs withdifierent q (SNR=10). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653.1 Flow chart of the proposed CEPS algorithm. . . . . . . . . . . . . . . . . . . . . 1003.2 Packet loss ratio for difierent tra–c classes when there are 30 video users, 50data users and variable number of voice users. . . . . . . . . . . . . . . . . . . . . 1013.3 Mean packet delay for difierent tra–c classes when there are 30 video users, 50data users and variable number of voice users. . . . . . . . . . . . . . . . . . . . . 1013.4 Maximum packet delay for difierent tra–c classes when there are 30 video users,50 data users and variable number of voice users. . . . . . . . . . . . . . . . . . . 1023.5 Throughput for difierent tra–c classes when there are 30 video users, 50 datausers and variable number of voice users. . . . . . . . . . . . . . . . . . . . . . . . 1023.6 Packet loss ratio for difierent tra–c classes when there are 100 voice users, 50data users and variable number of video users. . . . . . . . . . . . . . . . . . . . 1033.7 Mean packet delay for difierent tra–c classes when there are 100 voice users, 50data users and variable number of video users. . . . . . . . . . . . . . . . . . . . 1033.8 Throughput for difierent tra–c classes when there are 100 voice users, 50 datausers and variable number of video users. . . . . . . . . . . . . . . . . . . . . . . 1043.9 Packet loss ratio for difierent tra–c classes with 100 voice users, 30 video usersand 50 data users. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1043.10 Mean packet delay for difierent tra–c classes with 100 voice users, 30 video usersand 50 data users. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105List of Figures xii3.11 Throughput for difierent tra–c classes with 100 voice users, 30 video users and50 data users. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1053.12 Weighted excess PLR of difierent tra–c classes with 100 voice users, 50 datausers and variable number of video users. . . . . . . . . . . . . . . . . . . . . . . 1063.13 Weighted excess PLR of difierent tra–c classes with 30 video users, 50 data usersand variable number of voice users. . . . . . . . . . . . . . . . . . . . . . . . . . . 1063.14 Weighted excess PLR of difierent tra–c classes with 100 voice users, 50 datausers, variable number of video users and QoS parameters in Table 3.3. . . . . . 1073.15 Weighted excess PLR of difierent tra–c classes with 30 video users, 50 data users,variable number of voice users and QoS parameters in Table 3.3. . . . . . . . . . 1074.1 Data frame loss ratios vs. data frame generation rates for difierent flxed u0. . . . 1404.2 Throughput vs. data frame generation rates for difierent flxed u0. . . . . . . . . 1404.3 Packet access delay vs. data frame generation rates for difierent flxed u0. . . . . 1414.4 Data frame loss ratios vs. data frame generation rates for difierent schemes on u0.1414.5 Throughput vs. data frame generation rates for difierent schemes on u0. . . . . . 1424.6 Data frame loss ratios vs. number of tra–c  ows for difierent schemes on u0. . . 1424.7 Throughput vs. number of tra–c  ows for difierent schemes on u0. . . . . . . . . 1435.1 FLR comparison for single tra–c  ow. . . . . . . . . . . . . . . . . . . . . . . . 1785.2 Throughput comparison for single tra–c  ow. . . . . . . . . . . . . . . . . . . . . 1785.3 FLR comparison for the type 1 tra–c  ow in a system with FLR guarantee forthe type 1 tra–c  ow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179List of Figures xiii5.4 FLR comparison for the type 2 tra–c  ow in a system with FLR guarantee forthe type 1 tra–c  ow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1805.5 Throughput comparison for the system with FLR guarantee for the type 1 tra–c ow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1815.6 FLR comparison for the system with FLR sharing. . . . . . . . . . . . . . . . . . 1825.7 Throughput comparison for the system with FLR sharing. . . . . . . . . . . . . . 183xivAcknowledgementsI would like to express my deep gratitude to my research supervisor Dr. Victor C.M. Leungand Dr. Henry C.B. Chan for all these years of guidance and help throughout my PhD researchwork. Their great efiorts in teaching and research provided me with valuable support and goodideas. Without their guidance, this thesis would not be possible.I also want to thank all the members of my supervisory committee for their comments andtime, Dr. Vikram Krishnamurthy and Dr. Jane Wang.Thanks to Dr. Fei (Richard) Yu, Dr. Min Chen, Dr. Zhanping (Walter) Yin, Dr. Qixiang(Kevin) Pang, Dr. Zhibing (Harry) Chen, Dr. Ki-Dong Lee, Dr. Syed Hussain Ali, Jie Zhang,Ying Wai (Ray) Lam, Yangwen Liang, Haoming Li, with whom I have the great opportunityto collaborate during the past years.Special thanks to my wife Jie Zhang and my parents Yuanfang and Hongzhang for all theirsupport during these years.xvCo-Authorship StatementI am the flrst author and principal contributor of all manuscript chapters. All chapters areco-authored with Dr. Henry C.B. Chan and Dr. Victor C.M. Leung, who supervise the presentthesis research. Chapter 2 is also co-authored with Dr. Richard F. Yu, who helped to reviewthe journal paper draft and provided positive feedback on the a couple of detailed design in theprotocol. Chapter 3 is also co-authored with Jie Zhang, who helped in contributing to parts ofthe simulation modeling.1Chapter 1IntroductionThe Internet has grown dramatically in the last decade and many interesting multimedia ap-plications have emerged in business, social, entertainment, personal management, and otherflelds. People’s lifestyles have changed greatly and communication services are becoming es-pecially important, since they serve as the fundamental element for accessing Internet-basedmultimedia applications. In such an environment, packet-switched wireless communication sys-tems have attracted great interest from both service providers and subscribers, since the wirelesstechnologies can allow users to reach communication services from anywhere, without needingphysical attachments to immobilized equipment. While wireless technologies provide great con-venience and  exibility, wireless communication systems are still faced with the challenge toprovide competitive communication services over a limited amount of radio spectrum resourcesfor users to enjoy the plethora of multimedia applications via shared transmission media. Onone hand, service providers need to control the channel access to distribute the total bandwidthamong users wisely and e–ciently so that users will enjoy a good quality of service (QoS) whensubscribing to difierent types of multimedia services. On the other hand, service providers alsoneed to maximize the system utilization with limited spectrum resources, to support as manyusers as possible who subscribe to bandwidth-consuming multimedia applications.This thesis focuses on multimedia transmissions over wireless links. Note that transmis-Chapter 1. Introduction 2sions over wireless links are usually considered as the bottleneck of wireless communicationsystems, because of the limited wireless spectrum resources. As a result, QoS provisioning onwireless links is essential for the end-to-end QoS for difierent applications running on top ofwireless communication systems. The objective of this thesis is to provide  exible and guaran-teed QoS for multimedia transmissions, while enhancing the capacity of wireless links. Whilenumerous wireless technologies have been proposed to achieve higher data rates over wirelesslinks, the ability to manipulate and coordinate the transmissions on the data link layer mustalso be considered to achieve the desired QoS, especially for bandwidth-consuming multime-dia transmissions. This thesis focuses on the protocol design of wireless links and cross-layeroptimizations for wireless channels to provide efiective and e–cient guaranteed or difierenti-ated QoS for difierent transmissions. Speciflcally, a multiple access protocol is proposed forwireless channels with multi-packet reception (MPR) capabilities, so that the QoS of voice,video, and data transmissions can be difierentiated. Also, a cross-layer QoS consideration isproposed and applied to the scheduling and the transmission parameter optimizations in code-division multiple access (CDMA) networks and to wireless channels with adaptive modulationand coding (AMC) capabilities. Thus, the QoS of difierent transmissions can be guaranteed ordifierentiated, according to their QoS requirements, while the channel utilization is optimized.1.1 Quality of Service of Multimedia TransmissionsTraditional circuit-switched voice or best efiort data transmissions require only simple coordi-nations and a small efiort for QoS provisioning. Nevertheless, the tra–c  ows of Internet-basedmultimedia applications require more bandwidth and have complicated and diverse QoS re-Chapter 1. Introduction 3quirements. Wireless communication systems often classify transmissions into difierent typesto provide better service. For example, in the Third Generation Partnership Project (3GPP),tra–c  ows for difierent applications are classifled into four groups, according to the tra–ccharacteristics and the QoS requirements [1]. The conversational class represents applications,such as real-time voice communications, which have very strict delay and jitter requirements.The streaming class represents applications or services like playback video, which have lessstringent delay requirements but still need to have very little jitter. The interactive class repre-sents services like web browsing, which have almost no delay requirements, though the contentmust be delivered error-free and the tra–c has a speciflc request/response pattern. The back-ground class represents best efiort data services such as email and telemetry, which have QoSrequirements that are similar to those of the interactive class, but without a speciflc tra–cpattern. Some other systems, such as the Institute of Electrical and Electronics Engineers(IEEE) 802.11e wireless local area networks (WLANs) [2], also have their own deflnitions oftra–c classes or types to enable the system to serve difierent transmissions with difierent QoSrequirements more easily. In [3], International Telecommunication Union{Telecommunicationstandardization sector (ITU-T) proposed the end-user multimedia QoS categories. It also pro-vided the key QoS parameters for multimedia QoS and the recommended target values fordifierent categories as shown in Table 1.1. While the tra–c classiflcations in difierent systemsare based on the end-to-end QoS requirements of speciflc applications, QoS provisioning onwireless links for difierent classes of tra–c  ows is especially critical for wireless communicationsystems and has been widely studied. One of the major difierences between wired and wirelesscommunication systems is that wireless links are generally less reliable than wired links. ITU-Talso provided a relationship between the end-to-end QoS and the QoS for a speciflc networkChapter 1. Introduction 4section (say the wireless link) in [4].Transmissions over wireless links are coordinated by schemes involving the physical layerand the medium access control layer (MAC, a sub-layer of the data link layer). Packets arrivingfrom the upper layer are divided and encapsulated into data frames before being transmittedover wireless links. For multimedia transmissions, packet delivery can be time-sensitive andif a data frame is missing its transmission deadline, the packet should be dropped to preservevaluable network resources. For tra–c that is not delay-sensitive, even though data framescan wait for a long time before they are transmitted, new data frames may arrive continuouslycausing the bufier to over ow and some data frames to be dropped. The fraction of droppeddata frames is referred to as the frame drop ratio (FDR), and is one of the most importantQoS parameters for the MAC layer. In this thesis, the packet-drop ratio (PDR) is sometimesused for the QoS parameter on the MAC layer. It has the same deflnition as FDR and is morerelevant to the higher layers. The average data frame delay, or the packet delay, is anotherimportant QoS parameter for the MAC layer. The efiective data link layer throughput can alsobe used to measure the performance of the system. In any case, the QoS parameter for thephysical layer is the bit error ratio (BER), or the signal-to-interference-plus-noise ratio (SINR).These parameters can be used to measure the error probability of transmitting one bit or onesymbol. In this thesis, all of these QoS parameters and their relationships to difierent wirelesslinks are considered, in proposing new transmission schemes to improve QoS provisioning overwireless links.Chapter 1. Introduction 51.2 Multiple Access with Multi-Packet ReceptionsIn wireless communication systems, the MAC protocol allows several user terminals connectedto the same wireless link to transmit over the link and share its capacity. It runs on top ofthe physical layer multiplexing technologies and deals with issues such as addressing, assigningmultiplex channels to difierent users, and avoiding collisions. Conventional multiple accessprotocols, such as ALOHA [5] and carrier sense multiple access (CSMA) [6], are aimed to servebest efiort communications such as best efiort data transmissions. Thus, the focus is on efiectivechannel throughput rather than the QoS of speciflc tra–c  ows. Nevertheless, as more and moremultimedia transmissions appear in wireless communication systems, QoS provisioning at theMAC layer becomes increasingly important. There is a large body of work that addresses thisissue. Packet reservation multiple access (PRMA) [7{10], the collision resolution and dynamicallocation (CRDA) MAC protocol [11] and other work [12{14] combine random access andreservation techniques to provide better QoS for multimedia tra–c. All these schemes are basedon the single packet reception model, where errors always happen if more than one transmissionsoccur simultaneously on the channel. Many new physical layer techniques have been developedrecently to enable the MPR capability of wireless links. With these advanced techniques, one ormore user terminals can proceed with data transmissions simultaneously without interferencebetween each other that might otherwise cause serious transmission errors. Such physicallayer techniques include CDMA [15{18], multi-input-multi-output (MIMO) [19], orthogonalfrequency-division multiple access (OFDMA) [20], among others. Compared to single packetreception wireless channels, MPR channels allow simultaneous low-data-rate transmission fromseveral users, to greatly decrease the access delay from the low-data-rate users. Also, sinceChapter 1. Introduction 6collisions can be avoided in the MPR channel, it ofiers beneflts for contention-based multipleaccess.Conventional multiple access protocols are not flt for wireless communication systems withthe new MPR techniques. Consequently, developing e–cient multiple access protocols for fullyexploiting the MPR capability of the wireless links while providing e–cient QoS for difierentmultimedia transmissions becomes a new challenge. [21] and [22] proposed two MAC protocolsfor the MPR channel, where the state of the tra–c load is estimated and a set of users isscheduled to access the channel to maximize the channel utilization. [23, 24] analyzed theperformance of the traditional ALOHA protocol on the MPR channel. [16] and [17] employedboth time-division multiple access (TDMA) and CDMA in the same wireless link. [18] adoptedthe packet reservation multiple access protocol in CDMA networks, and [25] and [26] proposedefiective scheduling algorithms for CDMA networks to enhance the QoS of multimedia tra–c.One important contribution of this thesis is the proposal of a new MAC scheme, multi-reservation multiple access (MRMA) [27], for wireless channels with MPR capability.1.3 Scheduling Algorithm for Multi-Code CDMAOne of the typical wireless technologies with the MPR capability is the multi-code CDMA (MC-CDMA) [30]. As the MC-CDMA can  exibly provide diverse transmission rates to a variety ofdevices over a shared wireless channel, it has been extensively studied in both academic andindustry research [31{36]. It has been adopted as the Universal Mobile TelecommunicationsSystem (UMTS) [37] and high-speed downlink packet access (HSDPA) [38, 39] standard and willcontinue to be used in many current and future wireless communication systems [40, 41]. Al-Chapter 1. Introduction 7though the MC-CDMA can support simultaneous multimedia transmissions, it faces challengesin providing multimedia tra–c with the required QoS. This goal is accomplished by multipleaccess protocols, or scheduling algorithms, that fairly and e–ciently provide the required QoSfor all tra–c  ows (the FDR or PDR and packet delay).In infra-structured wireless communication systems, a base station or an access point usuallyserves as the central controller for all wireless user terminals within its coverage area. WhileMAC schemes provide coordination for uplink transmissions among difierent users, the schedul-ing algorithm that runs on the central controller coordinates the down-link transmissions. Insome cases, the scheduling algorithm can also be used for up-link transmissions as a complementto MAC schemes, as long as all of the transmission information can be obtained by the cen-tral controller and the central controller can notify user terminals about scheduling decisions.The scheduling algorithm determines the service sequences for difierent transmissions so thatspeciflc QoS provisioning can be achieved. Conventional scheduling algorithms for best efiortdata service include round-robin [42, 43], fair queuing (max-min fair) [44], proportionally fairscheduling [45], and maximum throughput [46], etc.In CDMA networks (and many other MPR systems), apart from ordering the transmis-sions of difierent  ows, scheduling algorithms also have radio resource management functionsfor controlling the interference between users so that the physical layer QoS requirements canbe satisfled. In most multiple access control protocols for CDMA networks, the radio re-source management function and the transmission ordering function are independent of eachother. Speciflcally, the radio resource management function aims to support QoS by keepingthe physical layer BER (or SINR) below (or above) a certain threshold. The transmission or-dering function seeks to serve the tra–c  ows fairly or with priority, while maximizing the linkChapter 1. Introduction 8throughput or minimizing the data frame drops [47{49].Compared to the common CDMA, where a scheduled user always sends transmissions ata constant rate, the MC-CDMA system enables scheduled users to transmit at multiple ratesusing multiple codes. Thus, the scheduling algorithm must not only determine which users cantransmit, but also determine the rate of transmission. Various scheduling algorithms have beenproposed for MC-CDMA [25, 26, 50]. To support multimedia tra–c, sophisticated schedulingalgorithms are used in wireless communication systems to guarantee the physical layer QoS(SINR or BER) and to provide difierentiated MAC layer QoS FDR for difierent tra–c  ows.As a complement to the MAC scheme, the scheduling algorithm is another key elementin QoS provisioning in the MC-CDMA and other wireless communication systems. Anotherimportant contribution of this thesis is in the proposal for a new scheduling scheme for theMC-CDMA, called cross-layer enhanced scheduling (CEPS) [51, 52].1.4 Cross-Layer Optimization of Quality of ServiceIn the traditional network infrastructure, communication tasks are divided into sub-tasks andhandled in separated layersindependently. The layeredarchitecture makesthe networkplanningand implementation easier and more e–cient. Nevertheless, while numerous wireless technolo-gies have been proposed recently, the cross layer technologies are suggested to enhance thewireless link capacity by sharing the knowledge among difierent layers and applying adaptationtechniques [55{59].Previous work on multiple access or scheduling algorithms has usually been aimed to sepa-rately meet the physical layer QoS requirement, in terms of SINR or BER, and the data linkChapter 1. Introduction 9layer QoS requirements, in terms of FDR (or PDR) and delay. The physical layer parameter,BER, and the MAC layer (or the data link layer) parameter, FDR, have similar efiects on thesystem, in terms of the QoS seen at the higher layer. This is due to the fact that data frameswith uncorrectable bit errors are also dropped. In fact, given the data frame structure, BERcan be further translated into the frame-error rate (FER), the fraction of data frames that arelost due to channel errors. We deflne the FLR as the fraction of total data frames that are lostdue to both data frame transmission errors (represented by the FER) and missed transmissiondeadlines or bufier over ow (represented by the FDR). Similarly, if the data link layer has are-transmission capacity and can re-transmit an error data frame, the re-transmission will leadto more data frame drops, since the chance of data frames missing the deadline or the chanceof bufier over ow is increased. In such cases, BER will afiect the FDR directly, and FLR willbe equal to FDR.In MC-CDMA networks, since scheduling algorithms afiect both frame error rate (FER)(by radio resource management) and FDR (by transmission ordering), these physical and MAClayer QoS parameters should be considered jointly; i.e., to optimize the overall FLR, insteadof FER (or BER) and FDR separately. We present a simple example to illustrate the cross-layer QoS issue, as studied in this thesis. Consider the case where one slot is available inthe current TDMA frame, which can be used to transmit multiple data frames (e.g., usingCDMA), and when two, three, or four data frames are transmitted simultaneously in the slot,the corresponding FER are 0, 0:2, and 0:6, respectively. At the MAC layer, four data framesmust be transmitted in the frame; otherwise, they will be dropped because of the delay violation.From the view of the physical layer, transmitting two data frames in the slot is better, so asto keep the FER reasonably low, where the FLR is 2=4 = 0:5 and the throughput is 2 (dataChapter 1. Introduction 10frames). On the other hand, from the view of the MAC layer, transmitting all four data framesis better, as the FLR is 0:6 and the throughput is 4 £ (1 ¡ 0:6) = 1:6 (data frames). Fromthe view of the cross-layer consideration, transmitting three data frames and dropping one isbetter for achieving the best FLR of 0:4 (i.e., (3 £ 0:2 + 1)=4), where the throughput is alsomaximized at 2:4 (i.e., 4£(1¡0:4)). From this simple example, it can be seen that the cross-layer optimization of the FLR results in a better performance, by accounting for the MAClayer queue statuses or the delay requirements. Moreover, the optimization of FLR actuallyoptimizes the channel throughput as well. This cross-layer QoS consideration can also be usedwith other wireless transmission technologies.The cross-layer QoS consideration can be used in scheduling algorithms and other trans-mission parameter optimizations to enhance the QoS provisioning of the wireless link. TheCEPS, proposed in this thesis, is employed to enhance the QoS provisioning and system ca-pacity. Also, a cross-layer optimization of the maximum number of simultaneous transmissionsin MC-CDMA networks is proposed in this thesis, based on the cross-layer QoS consideration[60].1.5 Opportunistic Scheduling and Adaptive Modulation andCodingTo further study the cross-layer QoS consideration in scheduling algorithms for multimediatransmissions over wireless communication systems, we studied the wireless communicationsystems with AMC, where the QoS provisioning of multimedia transmissions is also a challenge.A notable feature of wireless communication, in contrast to wired communication, is thatChapter 1. Introduction 11every user may have a difierent channel status while sharing the same wireless channel. Thechannel status is determined by the fading of the signal through the paths between antennasof the sender and receiver. This is also afiected by the interference received by the receiver’santenna. Intraditionalwirelesscommunicationsystemssuchas802.11eandUMTS,thephysicallayer QoS BER is guaranteed. If the BER cannot be guaranteed even with the maximumtransmission power, the scheduling algorithm can temporarily block the user’s transmissionand give channel access to some other users with better channel statuses.In recent years, advances in wireless communications have enabled the same transmissionover a wireless link to use difierent transmission rates, based on difierent channel statuses. Thebetter the channel status, the higher the transmission rate, which can be achieved while thephysical layer QoS is guaranteed. A typical example of such technology is AMC. In AMC,based on the channel status, the system can choose difierent coding (forward error coding) andmodulation schemes. While some coding and modulation pairs result in very low transmissionrates, they can tolerate a relatively poor physical layer channel status, and other coding andmodulation pairs can achieve very high transmission rates but require very good channel sta-tuses. The system uses training sequences to detect the channel status before making decisionsabout the coding and modulation schemes. AMC is already widely used in today’s wirelesscommunication systems. Because of its capability to maximize system e–ciency over the vary-ing wireless channels, it has been adopted at the physical layer in several important standards,including 3GPP [38, 69], 3GPP2 [70, 71], HIPERLAN/2 [72], IEEE 802.11a [73, 74], IEEE802.15.3 [75], and IEEE 802.16 [76], and has been combined with difierent advance technologiessuch as multi-carrier code division multiple access, MIMO, and cooperative networks.Scheduling methods that operate in AMC-based systems can improve the overall channelChapter 1. Introduction 12throughput by selecting the user with the best channel status to transmit. Such a strategy iscalled opportunistic scheduling, or multiuser diversity [77{82]. Nevertheless, the opportunisticscheduling may result in unfairness and QoS degradation problems, particularly for real-timetra–c [83]. Hence, the design of a fair and e–cient scheduling algorithm is strongly needed tosupport multimedia communications over AMC-based systems. Several authors have proposedways for addressing this problem using difierent strategies, with the aim to fairly provision theMAC layer QoS FDR for difierent tra–c  ows, while keeping the physical layer QoS SINR orBER guaranteed [84, 85].This thesis makes a signiflcant contribution in proposing a novel scheduling algorithm forAMC-based systems [86]. The cross-layer consideration, introduced above, is used to optimizethe channel throughput, while guaranteeing the QoS provisioning for difierent tra–c  ows.1.6 Summary of ContributionsThis thesis examines several state-of-the-art research problems in the area of wireless commu-nication systems. The objective is to support multimedia transmissions with QoS provisioningin wireless communication systems. The major contributions of this thesis are divided into fourchapters, as summarized below:† Chapter 2 proposes a novel multiple access scheme over MPR channels, called MRMA.MRMA addresses some new issues of the reservation protocol for the MPR channel, suchas adjusting the random access scheme, designing a new slot allocation mechanism totake advantage of the MPR capability of the channel, preventing lost reservations andinflnite reservations, and accounting for both data frame drops and data frame errors forChapter 1. Introduction 13realistic FLR. A Markov model for analyzing the performance of the proposed MRMAprotocol is proposed in Chapter 2. The proposed Markov model is suitable for analyzingthe access performance of multimedia tra–c as it incorporates bi-state tra–c sources (e.g.,mini-sources for video), in general, and on-ofi voice sources, in particular. The model isalso used to validate the simulation model, which is used to carry out detailed perfor-mance evaluations. Chapter 2 presents simulation and analytical results that quantifythe performance of MRMA for integrated multimedia (voice, video, and data) tra–c.MRMA can achieve very good QoS provisioning and keep the operation simple andstraightforward, which are important aspects for access control in wireless communica-tion systems. MRMA can difierentiate the QoS of voice, video, and best efiort datatra–c  ows, and the PLR and packet access delay of voice and video transmissions canbe guaranteed. Thus, multimedia transmissions can be better supported in a practicalsystem.MRMA is an efiective MAC scheme for wireless channels with MPR capacity, when com-pared to other, conventional MAC schemes. Its speciflc design can e–ciently exploit thecapacity of wireless channels and manipulate channel access wisely. It can be used inpractical systems, such as CDMA networks. Furthermore, many insights can be gainedfor MAC scheme designs in future wireless communications, stemming from the manyinteresting observations made during the design phase.† Chapter 3 proposes the CEPS scheme for scheduling multimedia cross-layer enhancedpacket tra–c over the uplink MC-CDMA networks. In CDMA networks, since schedulingalgorithms afiect both FER and FDR, these physical and MAC layer QoS parametersChapter 1. Introduction 14should be considered jointly, i.e., to optimize the overall FLR, instead of FER and FDR,separately. In CEPS, the scheduling algorithm makes decisions by considering the jointFLR. Also, in CEPS, the total FLR experienced by the system is shared among all tra–c ows according to predesigned weights. By estimating the data frame losses that mayhappen for the current frame and for later frames, according to the current bufier statusof difierent tra–c  ows, CEPS optimizes the sum of the weighted FLR for all tra–c  ows.Also, the historical FLR experienced by difierent tra–c  ows is considered by CEPS inproviding the proportional fairness. Chapter 3 presents both the essential optimizationobjective and the detailed practice steps of the scheduling algorithm.CEPS is a great enhancement of the system performance in terms of channel utiliza-tion and the maximum admissible tra–c  ows, due to its cross-layer QoS consideration.The enhancement can provide the more efiective capacity for the wireless communicationsystem, which is crucial for wireless communication systems with limited wireless radiospectrum resources. CEPS verifles the efiectiveness of the cross-layer QoS consideration.The rest of this thesis is focused on how the cross-layer QoS consideration can be used toimprove the performance of other systems and in other aspects.Compared to other scheduling algorithms, CEPS can give more efiective QoS provisioningfor multimedia transmissions. It can provide QoS guarantee to speciflc multimedia tra–c ows and share the rest of the bandwidth fairly among others. This feature can greatlyimprove the users’ experience when subscribing to multimedia applications over wirelesscommunication systems. CEPS also has a low complexity such that it can easily beapplied to practical MC-CDMA systems for enhancing the system performance.Chapter 1. Introduction 15† Chapter 4 proposes a cross-layer method for optimizing the QoS provisioning of multi-media tra–c in an MC-CMDA system by dynamically adjusting the maximum numberof simultaneous data frame transmissions in every frame. The optimization is based onthe current bufier status and the tra–c status of speciflc tra–c  ows. The problem isformalized as a Markov Decision Process (MDP) and solved by linear programming. Theresult is stored in the system upon new tra–c  ow being admitted and based on old tra–c ows remaining, and applied at the beginning of every frame. Chapter 4 also presentsthe theoretical analysis for the QoS parameter in terms of the FLR, average data framedelay, and channel throughput. The MDP solution is computationally infeasible if thesize of the whole system is too large. Thus, Chapter 4 presents an approximation methodfor the cross-layer optimization. According to the approximation method, only the tra–cstatus is considered in the optimization, and the bufier status is considered statistically.The optimization method proposes maximizing the channel capacity by choosing an ap-propriate number for the maximum number of simultaneous transmissions in one time slot,so that more multimedia transmissions can be admitted into the system. It also veriflesthe efiectiveness of the cross-layer QoS consideration. By using the optimization methodin a practical MC-CDMA system, the whole system is expected to provide better QoSfor multimedia applications, since the capacity is greatly enhanced. With the proposedapproximation method, even very large systems can be optimized with the cross-layerQoS consideration.† Chapter 5 proposed a scheme, called QoS-CLS, to dynamically determine the scheduledtra–c  ow and the modulation and coding pairs used for each transmission time interval.Chapter 1. Introduction 16Instead of optimizing the FDR and BER separately, QoS-CLS optimizes the FLR byconsidering both the physical layer and the MAC layer information. For FLR-sensitivetra–c  ows, the FLR can be guaranteed. For best efiort data tra–c  ows, the FLR ofthe system is distributed according to pre-specifled weights or priorities. To relax thecomputational complexity, Chapter 5 also presents two approximation methods. The flrstmethod divides the bufier states of a speciflc tra–c  ow into a small number of groupsand tracks the bufier states in terms of groups. In the other method, optimization isdecomposed into two parts with each being less computationally complex, compared tothe original optimization.The scheduling in the AMC-based system is of interest to research. A tradeofi existsbetween the channel capacity optimization and the fair QoS provisioning. Both are im-portant for multimedia transmission over wireless communication systems. Compared toother work, QoS-CLS can support these two goals in one optimization while achieving agood balance. It gives a good solution for the scheduling problem for AMC-based sys-tems. First, a good QoS provisioning is implemented, and the FLR and delay of speciflctransmissions can be guaranteed. The other transmission can share the channel fairly sothat the FLR can be achieved proportionally for predesigned weights. Second, while theabove QoS provisioning is achieved, the capacity of the wireless link is also optimized.Thus, the number of transmissions admitted into the system can be maximized. QoS-CLS also verifles the efiectiveness of the application of the cross-layer QoS considerationin AMC-based systems. QoS-CLS can achieve much better channel throughput becauseof its cross-layer QoS consideration. The proposed approximation methods can alleviateChapter 1. Introduction 17the computational burden of optimization in practical systems.1.7 Thesis OrganizationThis thesis is presented in the manuscript-based format, which is one of the two thesis formatsspecifled by the Faculty of Graduate Studies at the University of British Columbia (UBC).Each of the inner chapters (Chapters 2 to 5) is written in the style of a journal manuscript,based on manuscripts that have been published, accepted, submitted, or under preparation forsubmission. Moreover, each chapter has its own bibliography as required for the manuscript-based thesis format. The remainder of the thesis is organized as follows. Chapter 2 introducesthe multiple reservation multiple access scheme proposed for MPR channels. Chapter 3 proposesthe cross-layer enhanced packet scheduling scheme for MC-CDMA systems that schedules dataframes on the basis of historical joint data frame losses and estimated joint data frame lossesin current and future frames. Chapter 4 presents the QoS-based cross-layer scheduling forMC-CDMA systems that optimizes the maximum number of simultaneous transmissions forachieving a better system FLR. Chapter 5 presents the optimization method proposed foradaptivemodulationandthecoding-basedsystem, anditsapproximationmethods. Themethodoptimizes the channel throughout while guaranteeing the FLR for speciflc tra–c  ows andsharing the FLR among other best efiort data tra–c  ows. Chapter 6 summarizes the flndingsof the thesis and discusses possible future research directions.Chapter 1. Introduction 18Table 1.1: ITU-T Recommendations for Multimedia QoS TargetTypicalMedium Applicationdata ratesKey performance parameters and target valuesOne-way Delay Informationdelay variation lossOtherAudio Conversational 4-64 kbit/s < 150 ms < 1 ms < 3% packetvoice preferred loss ratio< 400 ms (PLR)limitAudio Voice 4-32 kbit/s < 1 s for < 1 ms < 3% PLRmessaging playback< 2 srecordAudio High quality 16-128 kbit/s < 10 s << 1 ms < 1% PLRstreamingaudioVideo Videophone 16-384 kbit/s < 150 ms < 1% PLR Lip-preferred synch:< 400 ms limit < 80 msVideo Streaming 16-384 kbit/s < 10 s < 1% PLRBibliography 19Bibliography[1] 3GPP, \Quality of service (QoS) concept and architecture," 3GPP TS23.107, v6.4.0, Mar.2006.[2] IEEE-802.11WG, \IEEE 802.11e standard draft/D8.0: Draft supplement to standard fortelecommunications and information exchange between systems LAN/MAN speciflc re-quirements part 11: MAC enhancements for quality of service (QoS)," Feb. 2004.[3] ITU-T, \ITU-T Recommendation G. 1010: End-user multimedia QoS categories," ITU-TG.1010, Nov. 2001[4] ITU-T, \ITU-T Recommendation Y. 1541: Network performance objectives for IP-basedservices," ITU-T Y.1541, Feb. 2006[5] N. Abramson, \THE ALOHA SYSTEM: Another alternative for computer communica-tions," Proc. of AFIPS Joint Computer Conference, pp. 281-285, 1970.[6] F. Tobagi and L. Kleinrock, \Packet switching in radio channels: Part II{The hiddenterminal problem in carrier sense multiple-access and the busy-tone solution," IEEE Trans.Commun., vol. 23, no. 12, pp. 1417-1433, Dec. 1975.[7] D. J. Goodman, R. A. Valenzuela, K. T. Gayliard, and B. Ramamurthi, \Packet reservationmultiple access for local wireless communications," IEEE Trans. Commun., vol. 37, no. 8,pp. 885-890, Aug. 1989.Bibliography 20[8] S. Elnoubi and A. M. Alsayh, \A packet reservation multiple access (PRMA)-based algo-rithm for multimedia system," IEEE Trans. Veh. Technol., vol. 53, no. 1, pp. 215-222, Jan.2004.[9] S. Nanda, D. J. Goodman and U. Timor, \Performance of PRMA: A packet voice protocolfor cellular systems," IEEE Trans. Veh. Technol., vol. 40, no. 3, pp. 544-598, August 1991.[10] E. D. Re, R. Fantacci, G. Giambene, and W. Sergio, \Performance analysis of an improvedPRMA protocol for low Earth orbit-mobile satellite systems," IEEE Trans. Veh. Technol.,vol. 48, no. 3, pp. 985-1001, May 1999.[11] L. Lenzini, M. Luise and R. Reggiannini, \CRDA: A collision resolution and dynamicallocation MAC protocol to integrate data and voice in wireless networks," IEEE J. Sel.Areas Commun., vol. 19, no. 6, pp. 1153-1163, June 2001.[12] M. J. Karol, Z. Liu and K. Y. Eng, \Distributed queueing request update multiple access(DQRUMA) for wireless packet (ATM) networks," Proc. of IEEE ICC’95, pp. 1224-1231,June 1995.[13] X. Qiu and V. O. K. Li, \Dynamic reservation multiple access (DRMA): A new mul-tiple access scheme for personal communication systems (PCS)," ACM/Kluwer WirelessNetworks, vol. 2, no. 2, pp. 117-128, June 1996.[14] H. C. B. Chan, J. Zhang and H. Chen, \A dynamic reservation protocol for LEO mobilesatellite systems," IEEE J. Sel. Areas Commun., vol. 22, no. 3, pp. 559-573, April 2004.Bibliography 21[15] N. D. Wilson, R. Ganesh, K. Joseph and D. Raychaudhuri, \Packet CDMA versus DynamicTDMAformultipleaccessinanintegratedvoice/dataPCN,"IEEE J. Sel. Areas Commun.,vol. 11, no. 6, pp. 870-884, Aug. 1993.[16] T. Weber, J. Schlee, S. Bahrenburg, P. W. Baier, J. Mayer and C. Euscher, \A hardwarddemonstrator for TD-CDMA," IEEE Trans. Veh. Technol., vol. 51, no. 5, pp. 877-892,Sept. 2002.[17] C. Yeh, \A TCDMA protocol for next generation wireless cellular networks with burstytra–c and diverse QoS requirements," Proc. PIMRC’02, pp. 2142-2147, Sept. 2002.[18] A. E. Brand and A. H. Aghvami, \Performance of a joint CDMA/PRMA protocol formixed voice/data transmission for third generation mobile communication," IEEE J. Sel.Areas Commun., vol. 14, no. 9, pp. 1698-1707, Dec. 1996.[19] J.Salz, \Digitaltransmission overcross-coupled linearchannels," AT&T Technical Journal,vol. 64, no. 6, pp. 1147-1159, July-August 1985.[20] H. Yin and S. Alamouti, \OFDMA: A broadband wireless access technology," Proc. ofIEEE Sarnofi Symposium, 2006, pp. 1-4, March 2006.[21] Z. Qing and L. Tong, \A multiqueue service room MAC protocol for wireless networkswith multipacket reception," IEEE/ACM Trans. Netw., vol. 11, no. 1, pp. 125-137, Feb.2003.[22] Z. Qing and L. Tong, \A dynamic queue protocol for multiaccess wireless networks withmultipacket reception," IEEE Trans. Wireless Commun., vol. 3, no. 6, pp. 2221-2231, Nov.2004.Bibliography 22[23] S. Ghez, S. Verd˜u, and S. C. Schwartz, \Stability properties of slotted ALOHA withmultipacket reception capability," IEEE Trans. Autom. Control, vol. 33, no. 7, pp. 640-649, July 1988.[24] V. Naware, G. Mergen, and L. Tong, \Stability and delay of flnite user slotted ALOHA withmultipacket reception," IEEE Trans. Information Theory, vol. 51, no. 7, pp. 2636-2656,July 2005.[25] V.HuangandW.Zhuang, \QoS-orientiedpacketschedulingforwirelessmultimediaCDMAcommunications," IEEE Trans. Mobile Comput., vol. 3, pp. 73-85, Jan.-Mar. 2004.[26] I. F. Akyildiz, D. A. Levine, and I. Joe, \A slotted CDMA protocol with BER schedulingfor wireless multimedia networks," IEEE/ACM Trans. Netw., vol. 7, no. 2, pp. 146-158,April 1999.[27] H. Chen, F. Yu, H. C. B. Chan and V. C. M. Leung, \A novel multiple access scheme overmulti-packet reception channels for wireless multimedia networks," IEEE Transactions onWireless Communications, vol. 6, no. 4, pp. 1501-1511, April 2007.[28] B. Maglaris, D. Anastassiou, P. Sen, G. Karlsson, and J. D. Robbins, \Performance modelsof statistical multiplexing in packet video communications," IEEE Trans. Commun., vol.36, no. 7, pp. 834-844, July 1988.[29] 3GPP, \Physical layer - general description," 3GPP TS25. 201, v3.4.0, June 2002.[30] C. Lin and R. D. Gitlin, \Multi-code CDMA wireless personal communication networks,"Proc. of IEEE Commun., pp. 1060-1064, Jun. 1995.Bibliography 23[31] A. Hamid, R. Hoshyar, and R. Tafazolli, \Joint rate and power adaptation for MC-CDMAover tempo-spectral domain," Proc. IEEE WCNC2008, pp. 969-973, Mar. 2008.[32] Z. Han, G. Su, A. Kwasinski, M. Wu, and K. J. R. Liu, \Multiuser distortion managementof layered video over resource limited downlink multicode-CDMA," IEEE Trans. WirelessCommuni., vol. 5, no. 11, pp. 3056-3067, Nov. 2006.[33] B. S. Thian, Y. Wang, T. T. Tjhung, and L. W. C. Wong, \A hybrid receiver schemefor multiuser multicode CDMA systems in multipath fading channels," IEEE Trans onVehicular Tech., vol. 56, no. 5, pp. 3014-3023, Sept. 2007.[34] C. S. Chang and K. C. Chen, \Medium access protocol design for delay-guaranteed mul-ticode CDMA mutimedia networks," IEEE Trans. Wireless Commun., vol. 2, no. 6, pp.1159-1167, Nov. 2003.[35] Y. Ma, J. Jin and D. Zhang, \Throughput and channel access statistics of generalizedselection multiuser scheduling," IEEE Trans. Wireless Commun., vol. 7, no. 8, pp. 2975-2987, August 2008.[36] C. D. Iskander, \Performance of multicode DS/CDMA with noncoherent M-ary orthogonalmodulation in the presence of timing errors," IEEE Trans. Vehicular Techno., vol. 57, no.6, pp. 3867-3874, Nov. 2008.[37] 3GPP, \Spreading and modulation (FDD)," 3GPP TS25.213, v3.4.0, Dec. 2000.[38] W. Xiao, A. Ghosh, D. Schaefier, and L. Downing, \Voice over IP (VoIP) over Cellular:HRPD-A and HSDPA/HSUPA," Proc. of IEEE VTC2005, pp. 2785-2789, Sept. 2005.Bibliography 24[39] A. Farrokh and V. Krishnamurthy, \Opportunistic scheduling for streaming multimediausers in high-speed downlink packet access (HSDPA)," IEEE Trans. Multimedia, vol. 8,no. 4, pp. 844-855, August 2006.[40] J. Zhou and M. Gurcan, \An improved multicode CDMA transmission method for Ad Hocnetworks," Proc. of IEEE WCNC 2009, pp. 1-6, April 2009.[41] L. Luo, J. Zhang and Z. Shi, \Novel block-interleaved multi-code CDMA system for UWBcommunications," Proc. of IEEE ICUWB 2007, pp. 648-652, Sept. 2007.[42] L. B. Le, E. Hossain, and A. S. Alfa,\Service difierentiation in multirate wireless net-works with weighted round-robin scheduling and ARQ-based error control," IEEE Trans.Commun., vol. 54, no. 2, pp. 208-215, Feb. 2006[43] P. Y. Kong, K. C. Chua and B. Bensaou, \Multicode-DRR: A packet-scheduling algorithmfor delay guarantee in a multicode-CDMA network," IEEE Trans. Wireless Commun., vol.4, no. 6, pp. 2694-2704, Nov. 2005.[44] V. Bharghavan, S. Lu, and T. Nandagopal, \Fair queuing in wireless networks: Issues andapproaches," IEEE Pers. Commun., vol. 6, no. 1, pp. 44-53, Feb. 1999.[45] G. barriac, and J. Holtzman, \Introducing delay sensitivity into the proportional fair algo-rithm for CDMA downlink scheduling," Proc. of IEEE 7th Int’l. Symp. Spread SpectrumTechniques and Apps., vol. 3, pp. 652-656, Sept. 2002.[46] H. Zeng et al., \Packet scheduling algorithm considering both the delay constraint anduser throughput in HSDPA," Proc. of Int’l. Conf. Commun., Circuits and Sys., vol. 1, pp.387-92, May 2005Bibliography 25[47] M. A. Arad and A. Leon-Garcia, \Scheduled CDMA: A hybrid multiple access for wirelessATM networks," Proc. of IEEE Pers., Indoor & mobile Radio Commun. 1996, pp. 913-917,Oct. 1996.[48] O. Gurbuz and H. Owen, \Dynamic resource scheduling strategies for QoS in W-CDMA,"Proc. of IEEE GLOBECOM 1999, pp. 183-187, Dec. 1999.[49] D.Zhao, X.ShenandJ.W.Mark, \RadioresourcemanagementforcellularCDMAsystemssupporting heterogeneous service," IEEE Trans. Mobile Computing, vol. 2, no. 2, pp. 147-160, Apr.-Jun. 2003.[50] P. Y. Kong, K. C. Chua, and B. Bensaou, \A novel scheduling scheme to share droppingratio while guaranteeing a delay bound in a multicode-CDMA network," IEEE/ACM,Trans. Networking, vol. 11, no. 6, pp. 994-1006, Dec. 2003.[51] H. Chen, H. C. B. Chan and V. C. M. Leung, \Cross-layer enhanced real-time packetscheduling over CDMA networks," Proc. of IEEE ICON2006, pp. 1-6, Sept. 2006.[52] H. Chen, H. C. B. Chan, V. C. M. Leung and J. Zhang, \Cross-layer enhanced uplinkpacket scheduling for multimedia tra–c over MC-CDMA networks," IEEE Trans. Veh.Technol., vol. 59, no. 2, pp. 986-992, Feb. 2010.[53] Q. Liu, S. Zhou and G. B. Giannakis, "Queuing with adaptive modulation and coding overwireless links: cross-layer analysis and design," IEEE Trans. Wireless Commun., vol. 4,no. 3, pp. 1142-1153, May 2005.Bibliography 26[54] Q. Liu, S. Zhou and G. B. Giannakis, "Cross-layer combining of adaptive modulation andcoding with truncated ARQ over wireless links," IEEE Trans. Wireless Commun., vol. 3,no. 5, pp. 1746-1755, May 2005.[55] Q. Liu, S. Zhou and G. B. Giannakis, \Cross-layer scheduling with prescribed QoS guar-antee in adaptive wireless networks," IEEE J. Selected Areas Commun., vol. 23, no. 5, pp.1056-1066, May 2005.[56] F. Yu, V. Krishnamurthy and V. C. M. Leung, \Cross-layer optimal connection admissioncontrol for variable bit rate multimedia tra–c in packet wireless CDMA networks," IEEETrans. Signal Processing, vol. 54, no. 2, pp. 542-555, Feb. 2006.[57] L.Alonso, andR.Aqusti, \Automaticrateadaptationandenergy-savingmechanismsbasedon cross-layer information for packet-switched data networks," IEEE Commun. Magaz.,vol. 42, no. 3, pp. S15-S20, Mar. 2004.[58] Y. Li and G. Zhu, \M-gated scheduling and cross-layer design for heterogeneous servicesover wireless networks," IEEE Trans. Vehicular Technol., vol. 58, no. 4, pp. 1983-1997,May 2009.[59] V. Cirvino, V. Tralli and R. Verdone, \Cross-layer radio resource allocation for multicarrierair interfaces in multicell multiuser environments," IEEE Trans. Vehicular Technol., vol.58, no. 4, pp. 1864-1875, May 2009.[60] H. Chen, H. C. B. Chan, and V. C. M. Leung, \Two cross-layer optimization meth-ods for transporting multimedia tra–c over multicode CDMA networks," Proc. of IEEEWCNC’07, pp. 288-293, March 2007.Bibliography 27[61] Q. Liu, S. Zhou and G. B. Giannakis, \Cross-layer combining of adaptive modelation andcoding with truncated ARQ over wireless links," IEEE Trans. Wireless Commun., vol. 3,no. 5, pp. 1746-1755, May 2005.[62] J. Ramis, L. Carrasco, and G. Femenias, \A two-dimensional markov model for cross-layerdesign in AMC/ARQ-based wireless networks," Proc. of IEEE GLOBECOM 2008, pp. 1-6,Nov. 2008.[63] M. Schwartz, Broadband Integrated Networks: Prentice Hall, 1996.[64] J. N. Daigle and J. D. Langford, \Models for analysis of packet-voice communicationsystems," IEEE J. Sel. Areas Commun., vol. 4, no. 6, pp. 847-855, Sep. 1986.[65] P. Skelly, M. Schwartz, and S. Dixit, \A histogram-based model for video tra–c behaviorin an ATM multiplexer," IEEE/ACM Trans. Netw., vol. 1, no. 4, pp. 446-459, Aug. 1993.[66] A. T. Anderson and B. F. Nielsen, \A Markovian approach for modeling packet tra–c withlong-range dependence," IEEE J. Sel. Areas Commun., vol. 16, no. 5, pp. 719-732, Jun.1998.[67] E. P. C. Kao, An introduction to stochastic processes, Duxbury Press, 1996.[68] M. L. Puterman, Markov decision processes: Discrete stochastic dynamic programming,John Wiley & Sons, New York, 1994.[69] 3GPP, \Physical layer aspects of UTRA high speed downlink packet access," 3GPP TR25.848, V4.0.0, 2001.Bibliography 28[70] 3GPP2, \Physical layer standard for CDMA2000 spread spectrum systems," 3GPP2C.S0002-0, v1.0, July 1999.[71] J. Yang, N. Tin and A. K. Khandani, \Adaptive modulation and coding in 3G wirelesssystems," Proc. of IEEE VTC2002, vol. 1, pp. 544-548, Sept. 2002.[72] A. Doufexi, S. Armour, M. Butler, A. Nix, D. Bull, J. McGeehan, and P. Karlsson, \A com-parison of the HIPERLAN/2 and IEEE 802.11a wireless LAN standards," IEEE Commun.Mag., vol. 40, no. 5, pp.172-180, May 2002.[73] IEEE Standard 802.11 Working Group, IEEE 802.11a Physical Layer Speciflcations, July1999.[74] F. Peng, J. Zhang and W. E. Ryan, \Adaptive modulation and coding for IEEE 802.11n,"IEEE Proc. WCNC 2007, March 2007.[75] H. Hu, Y. Zhang and J. Luo, \Distributed antenna systems open architecture for futurewireless communications," Auerbach Publications, CRC Press, May 2007.[76] IEEE Standard 802.16 Working Group, IEEE standard for local and metropolitan areanetworks Part 16: Air Interface for Fixed Broadbandwireless Access Systems, 2002.[77] X. Liu, E. K. P. Chong and N. B. Shrofi, \Opportunistic transmission scheduling withresource-sharing constraints in wireless networks," IEEE J. Selected Areas Commun., vol.19, no. 10, pp. 2053-2064, Oct. 2001.[78] S. S. Kulkarni and C. Rosenberg, \Opportunistic scheduling for wireless systems withmultiple interfaces and multiple constraints," Proc. of the 6th ACM/SIGCOM MSWiM,pp. 11-19, Sep. 2003.Bibliography 29[79] S. S. Kulkarni and C. Rosenberg, \Opportunistic scheduling policies for wireless systemswith short term fairness constraints," Proc. of IEEE GLOBECOM 2003, pp. 533-537, Dec.2003.[80] S. H. Ali and V. C. M. Leung, \Mobility assisted opportunistic scheduling for downlinktransmissions in cellular data networks," Proc. of IEEE WCNC2005, pp. 1213-1218, Mar.2005.[81] T. Bonald, \A score-based opportunistic scheduler for fading radio channels," Proc. ofEuro. Wireless, pp. 2244-2248, Sept. 2004.[82] A. Farrokh and V. Krishnamurthy, \Opportunistic scheduling for streaming users in high-speed downlink packet access (HSDPA)," Proc. of GLOBECOM2004, pp. 4043-4047, Nov.2004.[83] H. Fattah and C. Leung, \An overview of scheduling algorithms in wireless multimedianetworks," IEEE Wireless Communications, vol. 9, no. 5, pp. 76-83, Oct. 2002.[84] A. Golaup, O. Holland, and A. Aghvami, \A packet scheduling algorithm supporting mul-timedia tra–c over the HSDPA link based on early delay notiflcation," Proc. 1st Int’l.Conf. Multimeda Services Access Networks, pp. 78-82, June 2005.[85] B. Al-Manthari, H. Hassanein and N. Nasser, \Packet scheduling in 3.5G high-speed down-link packet access networks: Breadth and depth," IEEE Network, vol. 21, no. 1, pp. 41-46,Jan.-Feb. 2007.Bibliography 30[86] H. Chen, H. C. B. Chan, and V. C. M. Leung, \A cross-layer scheduling scheme forwireless multimedia transmissions with adaptive modulation and coding," Proc. of IEEEBroadnets2008, pp. 249-256, Sep. 2008.[87] A.Jalali, R.Padovani, andR.Pankaj, \DatathroughputofCDMA-HDR:Ahigne–ciency-high data rate personal communication wireless system," Proc. of IEEE VTC2000, pp.1854-1858, May 2000.[88] K. W. Choi, D. G. Jeong and W. S. Jeon, \Packet scheduler for mobile communicationssystems with time-varying capacity region," IEEE Trans. Wireless Commun., vol. 6, no.3, pp. 1034-1045, March 2007.[89] C. Cicconetti, L. Lenzini, E. Mingozzi, and G. Stea, \An e–cient cross layer schedulerfor multimedia tra–c in wireless local area networks with IEEE 802.11e HCCA," ACMSIGMOBILE Mobile Computing and Communications Review, vol. 11, no. 3, pp. 31-46,July 2007.[90] E. Biglieri, G. Caire, and G. Taricco, \Limiting performance of block-fading channels withmultiple antennas," IEEE Trans. Inform. Theory, vol. 47, no. 4, pp. 1273-1289, May 2001.[91] G. L. St˜uber, Principles of Mobile Communication, 2nd ed. Norwell, MA: Kulwer, 2001.[92] Y. L. Guan and L. F. Turner, \Generalized FSMC model for radio channels with correlatedfading," IEE Proc. Commun., vol. 146, no. 2, pp. 133-137, Apr. 1999.[93] V. Hassel, G. E. Oien, and D. Gesbert, \Throughput guarantees for wireless networks withopportunistic scheduling," Proc. of IEEE GLOBECOM, pp. 1-6, 2006.Bibliography 31[94] J. A. Stankovic, M. Spuri, K. Ramamrithan, and G. C. Buttazzo, Deadline Scheduling forReal-Time Systems: EDF and Related Algorithms. Norwell, MA: Kluwer, 1998.[95] S. Lu, T. Nandagopal, and V. Bharghavan, \Design and analysis of an algorithm for fairservice in error-prone wireless channels," Wirel. Netw., vol. 6, no. 4, pp. 323-343, Jul. 2000.32Chapter 2A Novel Multiple Access Schemeover Multi-Packet ReceptionChannels for Wireless MultimediaNetworks 1A challenge for future wireless multimedia networks is to design e–cient multiple access orMAC schemes to support packet-switched multimedia tra–c. Recent research work on wirelesscommunication enables the multiple packet reception capability for wireless channels. As aresult, conventional MAC scheme that assumes an error-free collision channel cannot be usedon the new MPR channels directly. As the MPR channel will be a suitable medium for packettransmissions over many future wireless multimedia networks, in this chapter, we propose a newreservation-based MAC protocol named MRMA for MPR channels. It aims to maximize thechannel throughput while satisfying the access delay bounds of difierent classes of real-time ser-1A version of this chapter has been published. H. Chen, F. Yu, H. C.B. Chan and V. C.M. Leung, \Anovel multiple access scheme over multi-packet reception channels for wireless multimedia networks," IEEETransactions on Wireless Communications, vol. 6, no. 4, pp. 1501-1511, Apr. 2007.Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 33vices such as voice and video. The major contributions of our work are summarized as follows.First, we present the detailed design of MRMA. Since existing reservation protocols cannot beapplied directly to MPR channels, we revisit many protocol features and address some newissues, such as adjusting the random access scheme and designing a new slot allocation mech-anism to take advantage of the fact that concurrent transmissions can be received successfully.Moreover, as transmission errors can occur over an MPR channel in practice, we need to handlenew issues such as lost reservations to ensure the correct operation of the protocol, and accountboth packet drops and packet errors for realistic packet loss ratio (plr) representation. Thesecond contribution is the development of a Markov model for analyzing the performance of theproposed MRMA protocol. Existing Markov models for conventional packet reservation proto-cols cannot be used because of the difierent properties of MPR channels, i.e., the MPR capacityand the error-prone nature. The proposed Markov model is suitable for analysis of access per-formance for multimedia tra–c as it incorporates bi-state tra–c sources (e.g., mini-sources forvideo) in general and on-ofi voice sources in particular. The model is also employed to validatethe simulation model, which is used to carry out detailed performance evaluations. Last butnot least, the chapter presents simulation and analytical results to quantify the performanceof MRMA for integrated multimedia (voice, video and data) tra–c. The results show that theproposed protocol can accommodate a larger number of real-time tra–c  ows while guaran-teeing their plr and delay bounds. Furthermore, the efiectiveness of the service difierentiationmechanism is demonstrated by the fact that the best efiort data tra–c has little and insignif-icant impact on voice and video tra–c. The results lead to some interesting observations andprovide valuable insights into the design of MAC protocols for MPR channels in future wirelessmultimedia networks.Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 34The remaining parts of the chapter are organized as follows. Section 2.1 introduces therelated work for MPR channels. Section 2.2 introduces the MPR channel model and tra–cmodels used in this chapter. Section 2.3 presents the proposed MRMA protocol, which ismodeled analytically in Section 2.4. Simulation and analytical results are presented in Section2.5 and their implications discussed. Finally, Section 2.6 concludes the chapter.2.1 Related WorkThe MAC schemes should be able to maximize the channel throughput, bear the unreliability ofwireless links and at the same time satisfy the QoS requirements, such as constraints on packetdelay and plr, of difierent multimedia services.Traditional MAC schemes for wireless networks such as Aloha, carrier sense multiple access,dynamic TDMA [1] and PRMA [2] have been commonly designed and analyzed assuming anerror free collision channel in which a collision destroys all the packets involved whereas a singlepacket transmission can always be received without error. However, with recent advances inwireless physical layers enabled by sophisticated signal processing techniques, such an assump-tion is no longer valid in many contemporary and future wireless networks, in which it is possibleto correctly receive multiple packets when concurrent transmissions occur. Such an MPR fea-ture exists in CDMA, multi-user detection, multiple-input-multiple-output and spacing-timecoding schemes. These schemes may greatly enhance the system performance and are mostsuitable for supporting multimedia tra–c.Recently, thedevelopmentofMACprotocolsfortheMPRchannelhasattractedconsiderableinterest. The CDMA/PRMA protocol [3] applies packet reservations in CDMA networks, inChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 35which reserved packets and access request packets use the same time slots. Consequently,QoS may not be guaranteed due to possibly unexpected heavy access requests. In the multi-queue service room protocol [4] and dynamic queue protocol [5], the state of the tra–c loadis estimated and a set of users is scheduled to access the channel to maximize the channelutilization. However, although the characteristics of difierent tra–c types (e.g., voice, dataand video) have great impacts on the design of MAC protocols for multimedia tra–c (e.g., see[3, 6, 7]), they have not been considered in [4, 5]. Without using realistic tra–c characteristics,user state estimations may not be accurate in practice, which may degrade the performanceresultspresentedin [4]and [5]. Morerecently, aQoS-orientedMACprotocol with fairpacketlosssharing (FPLS) scheduling [8] has been proposed for wireless CDMA communications. AlthoughBER is controlled by properly arranging simultaneous packet transmissions and packet loss anddelay are controlled by proper packet scheduling, the packet loss and delay caused by the randomaccess process have not been considered in [8]. These issues have a signiflcant impact on theoverall MAC performance.2.2 MPR Channel Model and Tra–c ModelsIn this section, we introduce the MPR channel model as well as voice, video and data tra–cmodels that will be used in later sections to evaluate the system performance.2.2.1 MPR Channel ModelWeconsiderasystemwithabasestation(BS)andmanyuserterminals(UTs)sharingacommonwireless channel, which has MPR capability. We focus on the uplink channel that consists ofChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 36time slots of flxed size, each accommodating the transmission time of one information packetexactly. The MPR capability of the channel is described by the MPR matrix fCi;jg, where theelement Ci;j is the probability that j packets are successfully received given that i packets havebeen sent simultaneously [4, 5, 9]. For data reception over wireless channels, the impairmentscaused by noise and interference can only be considered in a statistical sense. The channelstatistics, including efiects of multi-user interference, mobility and multi-path fading, are usedto construct the MPR matrix. For an example of the MPR model, we consider direct sequence(DS) CDMA employing pseudo-noise spreading codes. With the widely used standard Gaussianapproximation, the bit error rate Be of a packet received with (w ¡1) interfering packets in aCDMA system, where each packet is spread by a randomly generated code with a spreadingfactor of N and perfect power control is employed, is given by [4, 5]:Be(w¡1) = Qˆs3N(w¡1)+3N 2!(2.1)where 1= 2 gives the signal-to-noise ratio (SNR). Suppose that a packet has L bits and ischannel coded to tolerate at most " bit errors, the success probability Ps of a packet receptionis given by:Ps(w¡1) ="Xi=0 Li¶¡Be(w¡1)¢i¡1¡Be(w¡1)¢L¡i (2.2)So we have:Ci;j = ij¶¡Ps(i¡1)¢j¡1¡Ps(i¡1)¢i¡j (2.3)Note that the above mapping is an example for the given modulation and coding scheme.Generally, for any system, there is always a mapping from the SNR to the packet error rate.The MPR model serves as a powerful abstraction of the physical layer to facilitate design andanalysis of the MAC layer. The above is just an example showing how the MPR matrix canChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 37be obtained in practice. Note that in general the MPR matrix is not constant, but changes aschannel statistics vary over time. For example, a channel can alternate between good and badstates, each having a difierent SNR and hence a difierent MPR matrix. A time-varying matrixcan be employed provided that the channel stays constant over a packet transmission time. Forthe channel dynamics over one packet transmission time (for example, the fast-fading efiects),a stationary MPR can be formulated by accounting for the statistics of the channel dynamicsduring the packet transmission.2.2.2 Tra–c ModelsIn this chapter we consider three classes of tra–c: voice, data and video tra–c. To facilitatethe presentation, we assume that each UT hosts exactly one tra–c source. For practical caseswhere one UT can have multiple tra–c sources with difierent classes, the proposed protocol andmodels should have the same performance. The tra–c models for admitted UTs of difierenttra–c classes are given as follows and the tra–c parameters used in this chapter are shown inTable 2.1.For voice tra–c, the popular two-state Markov chain model with a constant bit rate (e.g.,8 Kbps) during the talkspurts and the zero bit rate in the silent gaps is employed [3, 6, 7]. Thedurations of the talkspurts and silent gaps follow the exponential distribution with the expectedvalues of 1=fi = 1s and 1=fl = 1:35s, respectively [3, 6, 7].For data tra–c, the on/ofi model given in [7] is employed where data packets arrive accordingto a Poisson process during the on period and no data packet arrives in the ofi period. Thedurations of the on/ofi periods are independent and follow the Weibull probability distribution(see [7] for details and Table 2.1 for the parameters used).Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 38A video UT is always active while connected. Bit rate variations of the source over time ismodeled by the autoregressive Markov model in [10] with parameters given in Table 2.1. Weassume that the flrst packet in each video frame carries the most important information.2.3 Multi-Reservation Multiple Access Scheme2.3.1 Frame StructureA TDMA-like frame structure is used to exploit time-division statistical multiplexing. Thisframe structure is widely used in third generation (3G) wideband CDMA (WCDMA) systems[11], TD-CDMA systems [12] and beyond 3G/ fourth generation (4G) systems [8, 13]. Figure2.1 shows the frame structure of the uplink channel. A speciflc number (F) of consecutiveslots are grouped into frames. Table 2.1 shows the frame parameters used in this chapter.Note that the frame length (Tf = 0:02s) is chosen such that an active (8kbps) voice UT hasexactly one packet (160 information bits) to send in each frame during a talkspurt. This is acommonly used approach in packet reservation protocols [6, 14]. There are two types of slotsin each frame: reservation slots/mini-slots and information slots. Reservation slots/mini-slotsare used by admitted voice and data UTs to send reservation requests to the BS. To improvee–ciency, a reservation slot is divided into t mini-slots for carrying reservation requests, and anextended guard space after the last mini-slot allows UTs to receive request acknowledgementsfrom the BS before the next slot. The value of t is chosen based on the tradeofi between thesystem e–ciency and the complexity. As an example, we assume t = 3 in this chapter. Asexplained in Section 2.3.4, the numbers of reservation and information slots are dynamicallyvaried while keeping a flxed frame length. Like other packet reservation protocols, a reliable andChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 39well-organized high-speed downlink broadcast channel from the BS to all the UTs is employedto send downlink packets, control messages, and immediate feedbacks on contention results.The allocation of information slots and announcement of reservation slots are broadcast to allUTs via the downlink channel before the beginning of each uplink frame.2.3.2 Basic ProtocolWhen starting a talkspurt, an admitted voice UT flrst contends in the next frame to send areservationrequestviaamini-slottotheBSusingtherandomaccessschemedescribedinSection2.3.3. At the end of the slot, the BS immediately acknowledges the contention result over thedownlink channel. An admitted video UT always maintains its connection with the BS throughsome reserved slots, so that requests via mini-slots are not needed. When a data UT becomesactive, it also needs to send a reservation request to the BS via a mini-slot using the randomaccess method in Section 2.3.3. To provide a best efiort service to data UTs using residualbandwidth, the data UTs do not contend for reservation mini-slots until they learn from theBS’s acknowledgement that the last reservation slot was idle, indicating that voice UTs likelyhave completed their reservation requests. Having received the requests, subject to availabilitythe BS assigns information slots to UTs according to the slot allocation method described inSection 2.3.4. After connecting to the BS, video and data UTs keep the BS informed of theirslot requirements or bufier status by piggybacking this information on the packets transmittedin information slots. This method is commonly used in packet reservation protocols (e.g., see[15]) to enhance the system e–ciency.Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 402.3.3 Random Access Scheme for MPR ChannelThe p-persistent random access scheme, whereby a station accesses a reservation slot with per-mission probability p until successful, is a common approach in reservation protocols [2, 3, 6, 16]for voice and data UTs to convey reservation requests in reservation mini-slots. However, thevalue p must be reestablished for the MPR channel as its unique property is not considered inexisting reservation protocols. In this chapter, we consider three difierent cases of p-persistentrandom access: ideal, flxed and adaptive schemes. Denote S as the expected number of suc-cessful requests. If the number of requesting UTs is m, it is not di–cult to see that:S =mXi=0 mi¶pi(1¡p)m¡iiXj=0j £Ci;j (2.4)Note that in (2.4), the Ci;j values in the MPR matrix are difierent from those used for informa-tion slots, because the length and coding are difierent between request and information packets.We can choose p such that S in (2.4) is maximized if we know the number of requesting UTs,m. We refer to this as the ideal scheme, which gives the best results for comparison purposes,but is impractical as it requires perfect knowledge of m. We also consider two approaches thatare more practical: flxed and adaptive schemes. The flxed scheme assumes a small number ofcontending UTs and employs a flxed permission probability p to maximize the chance of success.Previous studies of packet reservation protocols [3, 17] have suggested that p = 0:3 generallyworks well. For MPR channels, it is found that p = 1 is better since simultaneous transmissionscan be received successfully. However, if there are too many contending UTs, using p = 1will give adverse results. Hence, we also consider a simple adaptive scheme, in which p = 1 isnormally used, but when there are many contending UTs (or collisions), the BS will signal theUTs via the downlink channel to fall back to a lower p in the next frames. The collision efiectsChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 41and noise efiects are inter-related, as re ected in the MPR matrix, and a Kalman fllter may beused to detect the collision rate. For simplicity, a fallback is triggered when –% of the requeststransmitted in one frame fail. If a completely idle reservation slot is found, the BS signals theUTs to use p = 1 again. Generally, the fallback permission probability p and the threshold– must be determined based on the system parameters including channel statistics and tra–cstatistics. For the simulation model in this chapter, we choose the fallback p = 0:3 and – = 90based on the other system parameters. However, these values can be difierent in other systems.2.3.4 Slot AllocationIn MRMA, multiple packets can be assigned to a single slot. Hence, to allocate slots to UTs,we must flrst determine the maximum number of packets that can be accommodated by eachslot based on the plr requirements. We deflne Kvi, Kvo and Kd as the maximum numbers ofvideo, voice and data packets, respectively, that an information slot can support. Let ´vi, ´vo,and ´d be the plr requirements for voice, video and data tra–c, respectively. As an example,consider the case of video tra–c. To satisfy the plr requirement of video, we have:plr =KviXi=0Kvi ¡iKvi £CKvi;i • ´vi (2.5)Note that if there are Kvi packets, with probability CKvi;i, plr = (Kvi ¡i)=Kvi , i.e., (Kvi ¡i)packets are not received, according to the MPR channel model. Summing over all the possiblevalues of i, we can obtain the average plr. Hence, given a plr requirement of ´vi, we can flndKvi, the maximum number of packets that a slot can support based on (2.5). Then, we candetermine the required number of slots to send a certain number of packets. Similarly, therequired number of slots for other tra–c types can also be worked out. As difierent tra–c typesChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 42may be able to endure difierent numbers of bit errors per packet, their MPR matrices C maybe difierent too. Also, difierent tra–c types usually have difierent plr requirements. Thereforethe maximum numbers of packets a slot can accommodate may be difierent for difierent tra–ctypes. It is better that the same type of tra–c should share the same assigned slots wheneverpossible for ease of management and for maximizing the bandwidth utilization. However, ifmore than one slots are not \full" (can hold more packets) after all packets are allocated,packets in these slots should be mixed to further save bandwidth. In this situation, packetsfrom difierent tra–c are allocated in one slot and the maximum number of packets this slot canhold must be limited to fulflll the lowest plr target among the heterogeneous tra–c streams.Based on the slot capacity for each tra–c type determined above and the requests receivedin the current frame, the BS allocates slots in the next frame to the requesting UTs usingthe mechanism described below, and sends the allocation results to the UTs via the downlinkchannel before the start of the new frame. Subject to slot availability, the BS assigns slotsin this order: 1) one slot to every admitted video and voice UT with an ongoing reservation,2) one slot to each new voice request, 3) one slot to each video UT requiring multiple slots,repeated in a round robin fashion until all video requests are fulfllled, 4) one slot to eachdata UT (new or existing), repeated on a round robin basis, 5) remaining slots assigned asreservation slots. If there are not enough slots, the BS will not be able to allocate slots forthe unsatisfled requests and an unsuccessful UT will retry in the next frame if the need forreserved capacity persists. By the flrst two steps, the number of reservation requests requiredto set up reservations is minimized so that the channel utilization is enhanced. The best efiortdata packets are allocated in the step 4), so that they have little and insigniflcant impact tothe voice and video UTs, which are allocated in the flrst three steps. Only the remaining slotsChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 43are assigned as reservation slots, so that the total packet losses are reduced and the channelutilization is further improved.2.3.5 QoSVoice and video tra–c streams are time sensitive but they can tolerate moderate packet losses.For example, voice UTs can tolerate a plr of about 1% [6, 7, 16]. Thus the QoS requirementsfor voice and video tra–c at the MAC layer are expressed in terms of upper bounds for accessdelay and plr. To provide bounded access delay, deflned as the time taken for a tra–c sourceto gain access to the channel to send an information packet, we adopt the policy that voice andvideo packets are discarded from the respective bufiers if they cannot be sent within D frames.As an example, we use D = 1 in this chapter so that voice and video packets must be sent assoon as possible. This assumption is commonly used in packet reservation protocols [3, 16, 17].The requirement on plr bounds can only be satisfled by MAC in conjunction with a connectionadmission control (CAC) scheme. Therefore the MAC design objective is to maximize systemthroughput for specifled plr values, so as to maximize the number of admitted connections.MRMA has two components contributing to the overall plr: plrc due to information packetscorrupted by channel errors, and plra due to unsuccessful reservation requests or unsuccessfulslot allocations. In contrast with existing packet reservation protocols [2, 3, 6, 16, 17], whichgenerally consider only the second type of packet losses above, the MRMA model is morerealistic. Basically, plrc can be controlled using (2.5) by limiting the number of packets assignedto an information slot. On the other hand, plra can be controlled by limiting the number of UTsadmitted into the system using a CAC scheme [3, 8, 14]. Normally we keep plra ¿ plrc, so thatwhen the channel state degrades (causing the MPR matrices to change), the MRMA schemeChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 44can adapt quickly by changing the maximum number of packets assigned to an informationslot in the following frames, while the CAC function can respond more slowly by trying not toterminate any existing connection unless plra increases so greatly that the overall plr cannotmeet the required QoS target. This strategy minimizes the impact on the current tra–c whenthe channel condition is changed. Note that the MPR matrices can be dynamically adjustedbased on results of channel state estimations. For real-time tra–c, the system throughput canbe calculated as the product of the sources’ packet generation rates and the corresponding plrsince plr includes all packet losses at the MAC layer due to reservation failures or transmissionerrors.Data tra–c is sensitive to packet losses but not time delay. In MRMA, a best-efiort serviceis provided to data UTs using the residual bandwidth. New data packets are stored in theirUTs’ bufiers until they are transmitted over an allocated information slot. The data tra–c hasan indirect in uence on voice performance in that allocation of information slots to data UTsreduces the number of reservation slots available for voice requests. To address this issue, wedesign a simple control mechanism as follows. If the BS flnds no reservation mini-slot availablein q consecutive frames, it will stop assigning slots for data tra–c. This ensures that data UTscannot consume all residual slots for an extended time period. Here, the parameter q is used tobalance the QoS of data tra–c and voice tra–c, and also can be adapted dynamically to realizea simple CAC scheme for data tra–c; q can be adjusted gradually to reach a desired operatingpoint. Furthermore, upper/lower bounds of q can also be set based on past statistics. In thischapter, we study the efiect of q by simulations.Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 452.3.6 Preventing Lost and Endless ReservationsAs packets can be lost over the MPR channel due to multi-packet interference, MRMA needsto incorporate mechanisms to guarantee proper protocol operations. If the BS does not receivethe flrst voice packet of a UT with a successful reservation, it must distinguish whether it isa packet loss due to transmission errors or the talk-spurt has ended during the reservationprocess. The BS may wait a little longer, say, 2 or 3 frames, for a voice packet. If the BScannot receive it during this period, the reservation is cancelled. At the end of the talkspurt,the UT piggybacks on the second last voice packet a request to end the reservation. TheBS acknowledges it and wait for the last packet from the UT. If the ending request or theacknowledgement is lost, the UT resends the ending request. If the last packet is lost, the BSterminates the reservation after receiving 2 or 3 blank slots. These mechanisms prevent endlessreservations and premature termination of reservations due to lost packets (i.e., reservationlosses), and minimize the impact of lost packets on system performance. The losses may alsohappen to video packets with piggybacked requests for increasing bit rates. In this case, the BSsimply continues with the UT’s existing reservation (i.e., serve the video UT with the currentrate) until the UT reissues the request.2.3.7 Other EnhancementsThe objective of this chapter is to present the core framework of MRMA while giving the exibility for implementing other advanced services. For example, as mentioned above, whilewe assume that slots are allocated on a round-robin basis, other allocation mechanisms canalso be used without afiecting the basic operation of the protocol. Furthermore, although abest-efiort service is provided for data tra–c, it is also possible to support difierentiated dataChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 46services by provisioning some dedicated slots and using some appropriate scheduling method(e.g., earliest deadline flrst policy or weighted fair queuing) under BS control. In addition, it isalso of interest to study efiective ways to change the system parameters (e.g., q) in an adaptivemanner. In summary, the proposed MRMA framework provides the basis for further researchwork.2.4 Analytical ModelIn this section, we present an analytical model for evaluating the performance of MRMA forbi-state Markov sources in general and on-ofi voice sources in particular. For example, the bi-state Markov model can be applied to video tra–c as mini-sources [10]. Note that the voice andvideo access processes are in fact quite similar. Like a voice source, a video source also needs toaccess the BS when connection is flrst established. Subsequently, the bit rate requirements canbe communicated through piggybacking the new bit rate on information packets. Here, we flrstdescribe the model for on-ofi voice sources. Then we will describe how it can be used for videomini-sources. To facilitate the analysis, we neglect lost reservations, and follow the commonpractice to discretize the tra–c models such that the tra–c sources only change states at theframe boundaries [18, 19]. A UT can be in one of the following three states: 1) Idle (IDL), i.e.,the UT is silent; 2) Connecting (CON), i.e., the UT has started a talk spurt and is trying toconnect to the BS; and 3) Reserved (REV), i.e., the UT has successfully reserved a slot.Consider a group of voice UTs using the MRMA protocol to send packets to a BS over anMPR channel where the MPR matrix remains unchanged. Here, we assume that there are Nvvoice UTs. We describe the system state at any moment as a tuple (NCON, NREV ), whereChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 47NCON, NIDL and NREV are the numbers of CON, IDL and REV UTs, respectively, andNIDL = Nv ¡ NCON ¡ NREV . The states (NCON, NREV ) at the end of the frames form adiscrete time Markov chain.We consider the state transitions in two steps: at the boundary of two frames, and withineach frame after each reservation mini-slot. To do this, we deflne NCON;n as the number ofCON UTs at the beginning of frame n (before all slots), and NCON;n;i as the number of CONUTs at the end of the i-th mini-slot in frame n, where the number of mini-slots is hn. Thenumber of CON UTs at the end of frame n is NCON;n;hn and the number of CON UTs afterall information slots and before all reservation slots is NCON;n;0. The notations for REV UTsare deflned in a similar manner. The above deflnitions will be used in the appendices for thecalculations. Figure 2.3 shows the state transition graphs.At the frame boundary, some IDL UTs may become CON. Note that occasionally, anactive UT may not be able to secure a reservation successfully before it becomes silent again.In such a situation, the UT will go directly to the IDL state from the CON state. Thetransition probability T1 is derived in Appendix A.1. As shown in Figure 2.1, information slotsare grouped at the beginning of a frame. At the beginning of a frame, the number of informationslots k for the frame can be determined by the system state given by the number of REV UTsand the MPR matrix. Subject to availability, each REV UT is assigned an information slot. Atthe end of frame n, a REV UT may become IDL (i.e., the UT has sent the last packet in thetalkspurt). Also, some CON UTs may become REV after successfully sending a reservation.The state transition probability T2 is derived in Appendix A.2.As shown in the appendices, both T1 and T2 can be calculated from the system parametersF, Tf, fi and fl. So, we can get the state transition matrix T from the end of one frame to theChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 48end of the next one as follows:T(NCON;n+1;hn+1;NREV;n+1;hn+1jNCON;n;hn;NREV;n;hn)=XNCON;n+1XNREV;n+1T1(NCON;n+1;NREV;n+1jNCON;n;hn;NREV;n;hn)£T2(NCON;n+1;hn+1;NREV;n+1;hn+1jNCON;n+1;NREV;n+1) (2.6)Basedonthetransitionprobabilities, wecanobtainthestationarystateprobabilities…(NCON;NREV )at the end of a frame, and calculate the plr and the throughput as follows:plr =XNCONXNREV…(NCON;NREV )£(NCON +PLR(NREV ))Nv £ fifi+fl (2.7)· =XNCONXNREV…(NCON;NREV )£(NREV ¡PLR(NREV ))Tf (2.8)where PLR(NREV ) is deflned in (2.9).PLR(NREV )=8>>>>>>>>>>>><>>>>>>>>>>>>:„NREVKvo”£Xi¡CKvo;i£(Kvo ¡i)¢+Xi¡CNREV modKvo;i£(NREV mod Kvo¡i)¢NREV <Kvo£F(NREV ¡Kvo£F)+F£Xi¡CKvo;i£(Kvo ¡i)¢NREV ‚Kvo£F(2.9)Let us explain (2.7) as follows. Obviously, a CON UT will lose one packet at the end of aframe because it cannot get an information slot in the next frame. Also, if NREV ‚ Kvo £F,where there are F slots each assigned to Kvo UTs, NREV ¡Kvo£F UTs should lose one packetChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 49each due to no allocation. If NREV < Kvo£F, there should bebNREV =Kvocslots each with Kvopackets and one slot with (NREV modKvo) UTs (x mod y = remainder of x divided by y). Hence,based on the MPR model, P(CKvo;i£(Kvo¡i)) and P(CNREV modKvo;i£(NREV modKvo¡i))packet losses are expected for a slot with Kvo and NREV modKvo packets, respectively. Notethat in (2.7), the denominator Nv £ fi=(fi + fl) is the expected number of active UTs in aframe, and each active UT will send one packet per frame. Similarly, the throughput can becomputed by (2.8) where the numerator gives the expected number of packets that can be sentsuccessfully in a frame.As mentioned, the above model can also be used for video mini-sources, which model the bitrate increase/decrease processes [10]. In this case, each video mini-source alternates betweenactive and idle states, which are equivalent to the talk-spurt and silent states, respectively, inthe voice model. Assuming that late packets are discarded in a similar manner, the calculationsbasically follow the similar approach although the details may be difierent. The above Markovmodel cannot be used for data tra–c because the data model applies the Weibull distribution,which is not memoryless but gives a more realistic representation of data sources.Unfortunately, it is not feasible to compute the stationary distribution of the Markov chainderived above for a large number of UTs. It is found that numerical computations using themodel can handle up to approximately 50 UTs within a reasonable computation time. Withinthis limit, the analytical model can be used to calculate the results in minutes while it takeshours to obtain the results by simulations. However, when there are many UTs, it becomesinfeasible to use the analytical model because it requires too much memory to store the statesor too much time to compute the results. So we apply the analytical model to a small sizesystem to validate the correctness of our simulation model. Then we use the simulation modelChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 50to obtain further results under difierent conditions. This approach is commonly used in theliterature [18, 19] for performance evaluations of MAC protocols.2.5 Results and DiscussionsTo evaluate the performance of the proposed MRMA protocol, we have implemented a simulatorin C++. We consider the simple CDMA system introduced in Section 2.2 with spreading factorN = 7. An information packet is 511 bits long and encoded with a (511, 229, 38) BCH codefor transmission. A reservation request is 154 bits long and can tolerate 10 bit errors. Unlessotherwise specifled, Table 2.1 shows the simulation parameters for the system and the tra–c.In the simulations, the physical layer is applied statistically and the data link layer is operatedstep by step. The results are generated from the average of a couple of same simulations, whichruns at least 100,000 TDMA frames.We flrst justify the use of the adaptive random access scheme. We flnd by simulations theaverage number of slots required to allow a certain number of contending UTs to get connectedto a BS when difierent permission probabilities p are used. Figure 2.2 shows that when thenumber of contending UTs is not large, p = 1 has the best performance as it uses the leastnumber of slots. So it is justifled to use p = 1 when there are not too many contending UTs.We also observe that setting p … 0:3 can keep the required number of slots at a low level even ifthe channel is heavily utilized. Hence the above results justify the use of the adaptive scheme,i.e., using p = 1 if possible but falling back to p = 0:3 when there are many collisions.Next, we validate the simulation model using the analytical model described in Section 2.4.In this case, a small system with F = 5 and ´vo = 1% is used. Figure 2.4 compares the plr forChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 51voice sources obtained using the analytical and simulation models when SNR = 10db (baselineor good channel condition) and SNR = 6db (bad channel condition). It can be seen that theanalytical and simulation results agree closely with each other. As expected, p = 0:3 results ina higher plr than p = 1 because the number of contending UTs in this system is very small.Furthermore, p = 1 and the adaptive scheme can give a performance that is very close to theideal scheme. As expected, the results show that at the higher SNR, a better performance canbe achieved.Next, we compare the performance of MRMA and FPLS [8] by simulations at SNR = 6dband SNR = 10db. Note that FPLS also works over an MPR channel but it employs a deadline-based scheduling policy instead of hard reservations. Furthermore, it uses a flxed reservationbandwidth and a simple random access method. To ensure a fair comparison, we use the sameframe structure, channel model, and tra–c model in the simulations. We assume that FPLSchooses the number of simultaneous transmitted packets in the same way as MRMA, i.e., tomeet ´vo = ´vi = 1%. For FPLS, we consider that there are 3, 6 or 9 reservation mini-slots perframe and the transmission deadline is one frame time. For video tra–c, we assume that FPLSalso updates the slot requirements through piggybacking instead of reservation slots. Here, wefocus on comparing the plr’s of voice and video in an integrated voice/video system. Figure 2.5and Figure 2.6 show the comparison results for 10 video UTs and variable number of voice UTs.In summary, when there are few UTs and the channel is good (i.e., SNR=10db), both MRMAand FPLS give a similar performance if FPLS uses 3 reservation mini-slots. It is because bothFPLS and MRMA keep the plrc lower than the target plr and the plra is close to zero in thissituation. However, when the channel condition becomes worse (i.e., SNR=6db) or there aremore voice UTs (i.e., the tra–c load is higher), MRMA ofiers lower plr’s because the dynamicChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 52reservation bandwidth enables MRMA to utilize the limited bandwidth for both random accessand tra–c transmission more e–ciently than FPLS could, the adaptive access control furtherimproves the random access, and the frame-based reservation mechanism minimizes the requiredbandwidth for random access. All these factors result in a lower plra for MRMA. Note that theperformance of FPLS also depends very much on the flxed number of reservation mini-slots,which may be di–cult to set to a correct value for dynamic tra–c. Essentially, if with a target1% PLR for voice tra–c, FPLS can support 90 to 115 voice UTs or 130 to 160 UTs for SNR =6db or SNR = 10 db, respectively, while MRMA can support 120 and 170 voice UTs. It is a 4%to 33% or 6% to 30% capacity enhancement. From these two flgures, we can also conclude theMRMA provides a higher throughput than FPLS, based on the discussion of the relationshipbetween tra–c throughput and plr in Section 2.3.5.In the following, we further evaluate the performance of MRMA by simulating systems withmore UTs. Figure 2.7 shows the plr’s of voice and video tra–c in a voice/video joint systemwith ´vo = ´vi = 1%, when the number of video UTs is varied while the number of voice UTsis 100. Figure 2.8 shows the plr’s versus the number of voice UTs for 15 video UTs. Again, itcan be seen that the adaptive scheme can provide a performance close to the ideal scheme. Theresults are similar in the two flgures. Note also that all the curves in Figure 2.7 and 2.8  attenofi at around plr = 0:0004 for SNR = 10db. This is because the plr is ultimately limited by plrc(i.e., channel errors). In the system, based on the target plr of 1%, a slot can support at most6 packets for SNR = 10db. In fact, with 6 packets assigned to each slot, the achievable plrc isaround 0.0004 according to (2.5), corresponding to the minimum plr shown in the flgures. Notethat we cannot support 7 packets per slot because in this case, the plr > 0:01 according to (5).A similar phenomena can also be observed for SNR = 6db. These two flgures also show thatChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 53the numbers of voice and video UTs have a similar in uence on the target plr of both types oftra–c, which suggest that it is possible to satisfy the QoS of both types of tra–c using a jointCAC scheme to limit the numbers of voice and video UTs.We have also simulated a multimedia system with voice, video and data tra–c, where´vo = ´vi = ´d = 1%. Only the results for the adaptive access scheme are shown, as it wasfound that the results for the adaptive access scheme are very close to those of the ideal scheme.Figure 2.9 shows the result for 90 voice UTs and 10 video UTs, when the number of data UTsvaries from 10 to 160. As expected, when the number of data UTs is increased, the plr’s of bothvoice and data tra–c increase while the plr of video tra–c remains almost unchanged. Whenthere are few data UTs, the voice and data plr’s are relatively less sensitive to the change of q.However, when there are more data UTs, the data plr can be decreased by using a larger q at theexpense of increasing the voice plr. Figure 2.10 shows the throughput (i.e., bits transmitted persecond) for video, voice and data tra–c when the number of data UTs is varied. The desirableresult that the video and voice throughput is almost unafiected by the data UTs is apparent.When SNR = 10db, the data throughput is less sensitive to the change in the number of dataUTs and the q value. Figure 2.11 shows the average data access delay when the number of dataUTs is varied. Note that for video and voice tra–c, the access delay is bounded within 0.02s (1frame duration). When SNR = 10db and the number of data UTs is small, the average delayis less afiected by the q value. When SNR = 6db, the delay increases more signiflcantly for thesame number of data UTs.Figure 2.12 shows how the parameter q in uences the plr’s of voice and data tra–c whenSNR = 10db. When there are 90 data UTs, the tra–c load is not heavy, and the parameterq has almost no in uence on the voice tra–c. So the value of q should be made as large asChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 54possible to enhance the performance of data tra–c. When there are 150 data UTs, the tra–cload is heavy. Here, the parameter q in uences not only the performance of the data tra–c,but also the plr of the voice tra–c. It is obvious that the parameter q here should be set to 1 tokeep the voice plr within 1%. Based on this observation, we recommend that when the systemis underloaded, q should be adjusted to a larger value to increase the system e–ciency, andwhen the system is overloaded, q should be set to a smaller value so that the voice tra–c cansatisfy its plr requirement. The flgure also conflrms the idea mentioned in Section 2.3.3 thatq can be dynamically adjusted to provide basic CAC for data tra–c. Essentially, based on thehistorical statistic of the tra–c load, we can estimate an upper bound of q that can guaranteethe QoS of voice tra–c for a certain tra–c load, and also a lower bound of q that can maintaina certain plr for data tra–c. If the upper bound is lower than the lower bound, the system isoverloaded. If not, the parameter q can be adapted gradually between the two bounds.2.6 SummaryWe have proposed a novel MRMA protocol for future wireless multimedia networks with MPRcapability. Based on the channel model and the QoS requirements, the proposed scheme controlsthe number of packets transmitted in each time slot. In addition, service difierentiation isprovided by assigning difierent priorities to difierent tra–c types. System performance hasbeen evaluated by simulations and analysis, and compared with FPLS. Results show that theamount of data tra–c has only a slight and almost no impact, respectively, on the voice andvideo performance, verifying the efiectiveness of service difierentiation. Results also show that,by taking full advantage of the MPR capacity of the channel, MRMA can accommodate aChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 55larger number of real-time tra–c streams compared with FPLS while satisfying their accessdelay bounds and plr objectives.Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 56Table 2.1: Simulation ParametersDeflnition ValueChannelChannel rate after coding 511,000 bpsChannel rate before coding 229,000 bpsSpreading factor 7Base SNR 10dbFrame structureFrame duration 0.02 sSlot per frame 20Packet structurePacket size before coding 229 bitsPayload size 160 bitsOverhead 69 bitsPacket size after coding 511 bitsTolerable errors 38 bitsChannel coding BCH(511,229,38)Packet size for requests 154 bitsTolerable errors for requests 10 bitsVoice Modelcontinued on next pageChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 57Table 2.1: continuedDeflnition ValueAverage length of talkspurt 1.0 sAverage length of silent gap 1.35 sOfiered load while in talkspurt 8 kbpsOfiered load average 3.4 kbpsData ModelDistribution of the on/ofi duration WeibullAverage length of on duration 3.3 sAverage length of ofi duration 22.8 sShape parameter 0.88Number of packets per message 6Ofiered load while in on period 15.8 kbpsOfiered load average 2.0 kbpsData bufier size 200Video ModelPixels per video frame 2,400Video frames per second 30 frame/sAverage bits/pixel 0.421Variation of bits/pixel 1continued on next pageChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 58Table 2.1: continuedDeflnition ValueOfiered load average 30.3 kbpsChapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 59Figure 2.1: Frame structure.0 0.2 0.4 0.6 0.8 1100101102103104105106permission probability paverage number of slots needed 6 initial UTs12 initial UTs18 initial UTs24 initial UTs30 initial UTs36 initial UTsFigure 2.2: Average number of slots needed for difierent initial numbers of UTs to successfullysend requests when the permission probability varies from 0.05 to 1.Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 60Figure 2.3: State transition graphs at the frame boundary and within a frame.Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 6140 42 44 46 48 50 52 5410−410−310−210−1100number of UTspacket loss ratio  p = 1 (Simulation)p = 1, (Analytical)p = 0.3 (Simulation)p = 0.3, (Analytical)ideal p (Simulation)ideal p, (Analytical)Adaptive p (Simulation)SNR=6dbSNR=10dbFigure 2.4: Comparison of analytical and simulation results for voice.80 90 100 110 120 130 140 150 160 17010−410−310−210−1100number of voice UTsvoice packet loss ratioMRMA with ideal pMRMA with adaptive pFPLS with 3 minislotsFPLS with 6 minislotsFPLS with 9 minislotsSNR=6SNR=10Figure 2.5: Comparison of voice packet loss ratio for MRMA and FPLS.Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 6280 90 100 110 120 130 140 150 160 17010−410−310−210−1number of voice UTsvideo packet loss ratioMRMA with ideal pMRMA with adaptive pFPLS with 3 minislotsFPLS with 6 minislotsFPLS with 9 minislotsSNR=6SNR=10Figure 2.6: Comparison of video packet loss ratio for MRMA and FPLS.8 10 12 14 16 18 20 2210−410−310−210−1100number of video UTspacket loss ratiovoice, ideal pvoice, adaptive pvideo, ideal pvideo, adaptive pSNR=6SNR=10Figure 2.7: Packet loss ratio in a voice/video system with 100 voice UTs and difierent numberof video UTs.Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 6320 40 60 80 100 120 140 16010−410−310−210−1100number of voice UTspacket loss ratiovoice, ideal pvoice, adaptive pvideo, ideal pvideo, adaptive pSNR=6SNR=10Figure 2.8: Packet loss ratio in a voice/video system with 15 video UTs and difierent numberof voice UTs.0 20 40 60 80 100 120 140 16010−410−310−210−1100number of data UTspacket loss ratioq = 2, voiceq = 2, videoq = 2, dataq = 5, voiceq = 5, videoq = 5, dataFigure 2.9: Packet loss ratio in a multimedia system with 90 voice UTs and 10 video UTs(SNR=10).Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 640 20 40 60 80 100 120 140 160102103104105number of data UTsthroughput (bits per second)voice, q=2voice, q=5video, q=2video, q=5data, q=2data, q=5SNR=6 and SNR=10SNR=6 and SNR=10SNR=6SNR=10Figure 2.10: Throughput in a multimedia system with 90 voice UTs and 10 video UTs.0 20 40 60 80 100 120 140 16010−210−1100101number of data UTsaverage data access delay (in seconds) q = 2q = 5SNR=6SNR=10Figure 2.11: Average data access delay in a multimedia system with 90 voice UTs and 10video UTs.Chapter 2. A Novel Multiple Access Scheme over MPR Channels for Wireless Multimedia Networks 651 2 3 4 5 6 7 8 9 1010−410−310−210−1100qpacket loss ratiovoice (90 data UTs)voice (150 data UTs)video (90 data UTs)video (150 data UTs)data (90 data UTs)data (150 data UTs)Figure 2.12: Packet loss ratio with 90 voice UTs, 10 video UTs and 90 or 150 data UTs withdifierent q (SNR=10).Bibliography 66Bibliography[1] N. D. Wilson, R. Ganesh, K. Joseph and D. Raychaudhuri, \Packet CDMA versus DynamicTDMAformultipleaccessinanintegratedvoice/dataPCN,"IEEE J. Sel. Areas Commun.,vol. 11, no. 6, pp. 870-884, Aug. 1993.[2] D. J. Goodman, R. A. Valenzuela, K. T. Gayliard, and B. Ramamurthi, \Packet reservationmultiple access for local wireless communications," IEEE Trans. Commun., vol. 37, no. 8,pp. 885-890, Aug. 1989.[3] A. E. Brand and A. H. Aghvami, \Performance of a joint CDMA/PRMA protocol formixed voice/data transmission for third generation mobile communication," IEEE J. Sel.Areas Commun., vol. 14, no. 9, pp. 1698-1707, Dec. 1996.[4] Z. Qing and L. Tong, \A multiqueue service room MAC protocol for wireless networkswith multipacket reception," IEEE/ACM Trans. Netw., vol. 11, no. 1, pp. 125-137, Feb.2003.[5] Z. Qing and L. Tong, \A dynamic queue protocol for multiaccess wireless networks withmultipacket reception," IEEE Trans. Wireless Commun., vol. 3, no. 6, pp. 2221-2231, Nov.2004.[6] S. Elnoubi and A. M. Alsayh, \A packet reservation multiple access (PRMA)-based algo-rithm for multimedia system," IEEE Trans. Veh. Technol., vol. 53, no. 1, pp. 215-222, Jan.2004.Bibliography 67[7] L. Lenzini, M. Luise and R. Reggiannini, \CRDA: A collision resolution and dynamicallocation MAC protocol to integrate data and voice in wireless networks," IEEE J. Sel.Areas Commun., vol. 19, no. 6, pp. 1153-1163, June 2001.[8] V.HuangandW.Zhuang, \QoS-orientiedpacketschedulingforwirelessmultimediaCDMAcommunications," IEEE Trans. Mobile Comput., vol. 3, pp. 73-85, Jan.-Mar. 2004.[9] S. Ghez, S. Verd˜u, and S. C. Schwartz, \Stability properties of slotted ALOHA withmultipacket reception capability," IEEE Trans. Autom. Control, vol. 33, no. 7, pp. 640-649, July 1988.[10] B. Maglaris, D. Anastassiou, P. Sen, G. Karlsson, and J. D. Robbins, \Performance modelsof statistical multiplexing in packet video communications," IEEE Trans. Commun., vol.36, no. 7, pp. 834-844, July 1988.[11] 3GPP, \Physical layer - general description," 3GPP TS25. 201, v3.4.0, June 2002.[12] T. Weber, J. Schlee, S. Bahrenburg, P. W. Baier, J. Mayer and C. Euscher, \A hardwarddemonstrator for TD-CDMA," IEEE Trans. Veh. Technol., vol. 51, no. 5, pp. 877-892,Sept. 2002.[13] C. Yeh, \A TCDMA protocol for next generation wireless cellular networks with burstytra–c and diverse QoS requirements," Proc. PIMRC’02, pp. 2142-2147, Sept. 2002.[14] I. F. Akyildiz, D. A. Levine, and I. Joe, \A slotted CDMA protocol with BER schedulingfor wireless multimedia networks," IEEE/ACM Trans. Netw., vol. 7, no. 2, pp. 146-158,April 1999.Bibliography 68[15] M. J. Karol, Z. Liu and K. Y. Eng, \Distributed queueing request update multiple access(DQRUMA) for wireless packet (ATM) networks," Proc. of IEEE ICC’95, pp. 1224-1231,June 1995.[16] H. C. B. Chan, J. Zhang and H. Chen, \A dynamic reservation protocol for LEO mobilesatellite systems," IEEE J. Sel. Areas Commun., vol. 22, no. 3, pp. 559-573, April 2004.[17] X. Qiu and V. O. K. Li, \Dynamic reservation multiple access (DRMA): A new mul-tiple access scheme for personal communication systems (PCS)," ACM/Kluwer WirelessNetworks, vol. 2, no. 2, pp. 117-128, June 1996.[18] S. Nanda, D. J. Goodman and U. Timor, \Performance of PRMA: A packet voice protocolfor cellular systems," IEEE Trans. Veh. Technol., vol. 40, no. 3, pp. 544-598, August 1991.[19] E. D. Re, R. Fantacci, G. Giambene, and W. Sergio, \Performance analysis of an improvedPRMA protocol for low Earth orbit-mobile satellite systems," IEEE Trans. Veh. Technol.,vol. 48, no. 3, pp. 985-1001, May 1999.69Chapter 3Cross-Layer Enhanced UplinkPacket Scheduling for MultimediaTra–c over MC-CDMA Networks 1We employed an arbitrary slot allocation method in MRMA scheme proposed in Chapter 2.As a result, though the multimedia tra–c has higher priority over the best efiort data traf-flc, the further QoS difierentiation among difierent tra–c  ows is not provided. Such a taskcan be accomplished by a scheduling algorithm that determines how the channel resource isallocated to difierent tra–c  ows. In MC-CDMA, one of the typical MPR enabled system,since scheduling algorithms afiect both PER and PDR, it is desirable to consider these physicaland MAC layer QoS parameters jointly, i.e., to optimize the overall PLR instead of PER andPDR separately. Designing a scheduling algorithm based on the above optimization approachpresents a new set of research challenges. In traditional scheduling algorithms, the PER istypically kept below a threshold. So, given the channel status and the power constraint, it is1A version of this chapter has been published. H. Chen, H. C.B. Chan, V. C.M. Leung, and J. Zhang, \Cross-layer optimization for multimedia transport over multicode CDMA networks," IEEE Transactions on VehicularTechnology, vol. 59, no.2, pp. 986-992, Feb. 2010.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 70not di–cult to determine the channel capacity (i.e., the number of packets that can be trans-mitted in a frame) for scheduling purposes. However, with the above cross-layer optimizationapproach, the channel capacity is also related to the MAC layer tra–c status (i.e., cross-layerinformation) since the PER is not kept below a threshold anymore. It makes the schedulingtask more challenging especially for heterogeneous users where fairness among users has to beaddressed as well. A major contribution of this chapter is to tackle these new challenges forcross-layer scheduling. Speciflcally, we propose a novel scheduling algorithm called cross-layerenhanced packet scheduling (CEPS) for supporting multimedia tra–c over MC-CDMA. CEPSfocuses on the uplink transmissions because the problem is more challenging than the downlinktransmissions. In fact. it is easy to adapt the proposed scheme to schedule the downlink trans-missions. CEPS seeks to jointly optimize PER and PDR through a cross-layer optimizationframework that takes into account both QoS requirements and fairness. Basically, by consid-ering the MAC layer delay requirements and the queue statuses of difierent users, both thetransmission ordering and the interference among transmissions are controlled by the algorithmto minimize the packet losses (and to maximize the throughput) as seen above the data linklayer. Another advantage of CEPS is that it can handle fairness more efiectively and  exibly.Simulation results will be presented to illustrate the beneflts of the proposed algorithm.The remainder of this chapter is organized as follows. Section 3.1 introduces the relatedwork. Section 3.2 describes the MC-CDMA system in which we apply our algorithm. Section 3.3deflnesthesystemmodelandalsopresentsthecross-layerenhancementandfairnessprovisioningmethod, which is the central idea of this chapter. Section 3.4 presents the CEPS algorithm forthe MC-CDMA system. Section 3.5 presents the simulation results to compare the performanceof the proposed algorithm with two other existing algorithms. Section 3.6 concludes the chapter.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 713.1 Related WorkOne of the challenges in future packet-switched wireless networks is to provision multimediatra–c with the required QoS over unreliable wireless links. This goal is accomplished by schedul-ing algorithms that fairly and e–ciently provide the required QoS to all tra–c  ows (referredsimply as  ows in this chapter). Although the cross-layer concept (to optimize the physical layerBER and MAC layer PDR jointly) can be applied to any CDMA networks and other wirelessnetworks with variable rate capability, we study its application in the MC-CDMA [14] networksin this chapter. Due to its ability to support a variety of devices with diverse transmissionrates within a single frequency band, MC-CDMA has been studied widly in both academicand industry research [15{17]. It has also been adopted in the WCDMA [18] and HSDPA [19]standards and is expected to be used in many future wireless communication systems.Many scheduling algorithms [1{5] proposed for CDMA systems attempt to maximize thechannel throughput or minimize the PDR while providing fairness among difierent users. How-ever, they optimize BER at the physical layer and PDR at the link layer separately. Recently,some scheduling algorithms that utilize cross-layer information have also been proposed forwireless networks, especially for systems employing AMC. Opportunistic scheduling algorithms[6{9] can enhance the system throughput. However, they may not be suitable for supportingmultimedia tra–c, as is our objective in this chapter, since they do not provide hard guaranteeson delay and packet loss. In [10], based on the estimation of the efiective bandwidth, every QoS-guaranteed  ow reserves some speciflc bandwidth from the system. The reserved bandwidth isused by other  ows only when there are no more packets in the queue of the QoS-guaranteed ow. However, the algorithm is based on a very conservative admission control with which theChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 72system can satisfy the throughput requirement of all QoS guaranteed  ows when all these usersexperience the worst channel status simultaneously. So, this approach does not fully utilizethe multiplexing gain among QoS guaranteed  ows. Also, the estimation of the efiective band-width greatly depends on having an accurate estimate of the tra–c characteristics, which is notalways achievable. The protocol in [11] jointly considers channel errors in the physical layerand bufier over ows in the MAC layer. However, it does not take full advantage of cross-layeroptimization. In addition, each real-time  ow is served at a constant transmission rate basedon the estimated efiective bandwidth, which may lead to less multiplexing gain. While all theabove proposals considered cross-layer information, they did not consider the MAC layer QoSrequirements while optimizing the physical layer transmission parameters. Hence the total PLRwas not optimized (i.e., the throughput could be further improved). The work in [12] and [13]studied how the MAC layer queue statuses (or retransmission information) and QoS require-ments can be used to optimize the physical layer parameters for AMC so that a signiflcantimprovement in throughput can be achieved. The parameters were optimized in a statisticalmanner according to the system dynamics. However, they did not address scheduling issuesand the approach cannot be used in CDMA systems.3.2 Multicode CDMA SystemIn this chapter, we consider a multi-cell time division MC-CDMA system and focus on the uplinkchannel. To simplify the presentation, we assume that each user has only one  ow. Without lossof generality, consider that the number of time slots in each MAC frame is a flxed number (F),all packets have the same size, and each packet can be transmitted in one time slot using oneChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 73code. To achieve difierent bit rates, a user may transmit multiple packets in each frame usingeither multiple time slots, or multiple codes over a single time slot, or both. Although in currentsystems like IS-95, non-orthogonal codes are commonly used [14], we assume that orthogonalcodes are used for multiple packet transmissions from the same user over one time slot toachieve a higher bit rate, so that the mutual-inference between the concurrent transmissionsof the same user is greatly reduced at the BS due to the same propagation condition on theparallel orthogonal codes [20]. An efiective code generation method is introduced in [14]. Wealso assume that the near-far problem and fading efiects are mitigated by perfect power controland can be neglected (an imperfect power control may lead to less efiectiveness of the proposedscheme). Also, because there are a large number of interfering streams from all adjacent cells,we can apply the Gaussian approximation, i.e., the inter-cell interference can be considered asa part of the total Gaussian noise with normalized variance  2. So, denoting the number ofusers with i packets transmitted in slot t of frame s as Ns;ti , the SINR for a packet in slot t offrame s from a user with i packets in this time slot is [2, 21]:SINRi =32GPl l£Ns;tl ¡i+3G 2B(3.1)In (3.1), G is the processing gain, B is the baseband bandwidth for a single code transmissionand l is the possible number of packets a user may transmit in a time slot. The BER of such apacket is:BERi = Q(qSINRi) (3.2)where Q(:) is the tail function of the Gaussian distribution. In some practical systems, theSINR and BER models may be more complicated than above. Regardless, the BER and SINRChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 74of a packet in a slot can always be determined given the packets scheduled for transmissionsover the same slot and the power constraints on these transmissions.Furthermore, given the channel coding scheme, the PER can be determined from the BER.Generally, for a coding block or a coding cycle that is w bits long and can tolerate v bit errors,the block error probability is:Perror =wXj=v+1(wj )BERij(1¡BERi)w¡j (3.3)The PER is the probability that any block or cycle in a packet is in error. For some systems,the above calculation may not be obtained. But generally, there must be a mapping from theSINR to PER and it can be studied by experiments. We assume that the BS can reliablydetermine if an uplink packet is correctly received, e.g., by performing a cyclic redundancycheck on the received packet. While more sophisticated coding schemes can be applied, amapping always exists between the channel BER and the PER at the link layer given thecoding scheme.Note that in most of the related previous work, the SINR of each user is guaranteed to behigher than a specifled threshold. Based on (3.2) and (3.3), it is equivalent to keeping the PERof each user below a certain threshold.3.3 System Model and Principle of CEPSBefore explaining the proposed algorithm, we flrst deflne the system model, introduce theproposed cross-layer enhancement and study the fairness provision of the proposed schedulingalgorithm.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 753.3.1 System ModelWe consider J classes of multimedia users, where class j (j=1, 2, ..., J) has Kj users. In thesubsequent analysis, we consider three tra–c classes: conversational, streaming, and interac-tive [22], which have difierent QoS requirements. Generally, conversational tra–c has a verystringent delay requirement but it can tolerate moderate packet losses. Streaming tra–c canalso tolerate moderate packet losses but it has less stringent delay requirements, although adelay bound is still desirable. Interactive data tra–c requires a very low packet loss rate but itcan tolerate much higher delays. Each user station has a bufier to store generated packets. Weconsider uplink transmissions only, and assume that all users can inform the BS their bufierstatus via an error-free uplink signaling channel (Note that the modulation and coding schemefor the signaling channel is chosen for high reliability rather than bandwidth e–ciency). At thebeginning of every MAC frame, the BS applies the scheduling algorithm to decide which packetis to be transmitted in which slot in the frame and informs the user stations accordingly via anerror-free downlink signaling channel. This decision is based on the QoS requirements, bufierstates, past statistics and channel states of the users.1. Packet Access Delay and Bufier SizePacket access delayis one of the most important QoS parameters for multimedia tra–c inthe MAC layer of a packet switched wireless network, and is deflned as the time from thearrival of the packet at the station to the transmission of the packet over the air interface.Generally, there is an expiration time associated with each time-sensitive packet such thatthe packet is dropped by the sender if it is not sent before it expires [2, 3]. The expirationtime is determined by the delay/jitter requirements of the real-time application. In thisChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 76chapter, we adopt the common assumption [2, 3] that a packet, which will expire in framen, must be sent before frame n since the scheduling decisions are made at the beginning ofthe frames. If the peak packet rate is Sj and the maximum tolerable packet access delayis Dj for class j users, a bufier with size DjSj at each sending station will ensure that nobufier over ow happens for these users, and that packets are dropped at the station onlydue to the packet access delay exceeding the expiration time.2. Most Urgent Packets and Bufier StatusAs stated above, each packet in the sending bufier has an expiration time (except forbackground tra–c classes). A scheduling algorithm should try its best to transmit eachpacket before it expires. In each frame, some packets will expire if not sent out in thisframe. We name these packets the most urgent packets (MUPs) for the current frame.These packets should be sent out in this frame if possible, or else they would be droppedby the sender. Similarly, we can deflne the 2nd most urgent packets (2UPs), 3rd mosturgent packets (3UPs), etc. To minimize packet drops, 2UPs should be served in eachframe after all MUPs have been served, followed by 3UPs, and so on. The BS knows thebufier status of each user, i.e., the numbers of MUPs, 2UPs, 3UPs, ..., from each user inany given frame.3. Processed Packets, Dropped Packets and PDRWe know that, in each frame, a MUP is dropped at the sending station if it is not sent. Wedeflne the processed packets in a given time period T as the packets sent out or droppedby the sending stations in T. Note that a processed packet may not be a MUP in periodT. A packet that is not so urgent may still be sent in T if capacity is available. The PDRChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 77of class j user i in period T is deflned as:PDRTj;i = DPTj;iPPTj;i (3.4)where DPTj;i and PPTj;i are, respectively, the numbers of dropped and processed packetsat the user station in the period T. During each scheduling instance, the system shouldconsider not only the packet drops that have happened in previous frames, but also thosethat will happen in the next frame due to failure to schedule MUPs for transmissions inthe next frame.4. Error Packets and PERWe deflne the error packets in a given time period T as the packets which are sent inperiod T but not correctly received. The PER experienced by class j user i in period Tis:PERTj;i = EPTj;iPPTj;i ¡DPTj;i (3.5)where EPTj;i is the number of error packets in period T. When the system schedules apacket, to fairly distribute the PLR, it must guess whether the packet will be correctlyreceived. The probability that a packet will be correctly received depends on how manypackets are allocated in the slots from what stations and the power constraints on thesetransmissions. For the system introduced in Section 3.3, it can be derived based on (3.3).After a transmission, we assume that the BS knows for sure if the transmitted packet iscorrectly received or not via some error detection coding such as cyclic redundancy check.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 785. Lost Packets and PLRWe deflne lost packets to include both packets dropped by the transmitter due to delayviolations, and packets sent but not received correctly. So, we deflne the PLR of class juser i in a given period T as:PLRTj;i = LPTj;iPPTj;i =DPTj;i +EPTj;iPPTj;i (3.6)where LPTj;i is the number of lost packets from the user station in the period T. It is alsogiven by:PLRTj;i = 1¡(1¡PDRTj;i)(1¡PERTj;i) = PDRTj;i +PERTj;i ¡PDRTj;i £PERTj;i (3.7)3.3.2 Basic Concept of the Cross-Layer EnhancementTo explain the basic concept of the cross-layer enhancement, we flrst consider only one userin the system and extend to multiple users later. We consider a scheduling algorithm whichprocess packets one by one like the approaches used in [1{3].In most existing algorithms, there is a PER or BER threshold for difierent  ows or users.These scheduling algorithms will not admit more packets if adding one more packet into theframe will lead to the violation of the PER requirements of any user in the frame. This kind ofmechanism is e–cient for transmitting non-urgent packets or non delay sensitive tra–c becausethe throughput is maximized and the PLR of the frame is guaranteed (PER is efiectively PLRhere since no packet drop occurs). However, this approach is not e–cient for transmittingurgent packets or delay sensitive tra–c as it may lead to a greater number of packet dropswhen there are a lot of MUPs or the tra–c source rate is very high. Actually, if there are stillMUPs in the bufier, by degrading the PER requirements of some packets, more packets can beChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 79transmitted in one frame and thus the overall number of packets losses due to errors and dropsin the frame may be reduced. This is the basis of the cross-layer-based scheduling method fordelay sensitive multimedia tra–c proposed in this chapter. We consider two cases of the bufierstatus in a frame.The flrst case is that there are not too many MUPs and all of them can be transmittedin the frame. We denote this case \all MUPs transmitted" (MAT). Note that, adding lowerpriority packets (2UP, 3UP, ...) may increase the total packet losses in the frame because thePER may increase while no packet will be dropped. So the algorithm should try to maximizethe throughout by keeping the PER reasonably low for each packet. In this case, our algorithmworks in the same manner as the existing algorithms, which allows other packets (2UPs, 3UPs,...) to be scheduled if and only if a predeflned PER threshold is not exceeded. Note that,in MAT, PLR for the frame is contributed solely by the PER. We deflne this threshold as thePLR threshold in this chapter since it re ects the capability of a speciflc  ow to tolerate packetlosses.The second case is denoted as MAT, where there are too many MUPs in a frame so thatsome packets must be dropped if the PER is kept below the threshold for every transmittedpacket. In this case, the PLR of the frame cannot be kept below the threshold. So, the algorithmshould try to relax the PER of the frame so that the total PLR for the frame can be minimized.Based on the number of MUPs in the bufier, the scheduling algorithm chooses an appropriatenumber of MUPs to be transmitted in the current frame to reduce the overall PLR (consideringboth packet errors and packet drops) of the current frame. Speciflcally, the scheduling algorithmdecides whether the next MUP in the bufier should be added into the frame by checking theexpected PLR of the current frame. In MAT, Packets other than MUPs (i.e., 2UPs, 3UPs, ...)Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 80will not be transmitted.Since MUPs are always scheduled before other packets, if all MUPs can be scheduled whilekeeping the PER below the threshold, this belongs in the MAT case; otherwise the MAT case.For a multi-user system, the approach is similar. However, unlike a single user system wherewe can just minimize the total PLR of a frame, we now need to consider the PLR requirementsof difierent users, whose  ows may have difierent PLR targets. So, in a multi-user system,we optimize the weighted excess PLR instead of the total PLR of the frame. In this case, theoptimization problem is constrained by the fairness requirements specifled below.3.3.3 Fairness RequirementIn a multi-user system, we deflne `j as the PLR threshold of class j users, similar to the PERthreshold deflned in previous work. We also call these the target PLRs. The target PLR`jshould be satisfled for all class j users in every frame whenever possible. If there are toomany MUPs in one frame (i.e., the MAT case), the target PLR`j may not be satisfled in thatparticular frame for all users, and PLR becomes excessive for some users.Most previous work on fair scheduling aims to fairly distribute the bandwidth among usersor  ows. However, this approach may not be suitable for multimedia  ows that have variablerates and stringent delay requirements. Instead, in this chapter we propose to provide fairscheduling via fair distribution of excess PLR (FDEL) among all  ows, which is similar to theapproaches in [2, 3] where difierent users or  ows share the PDR. We show below that FDELis equivalent to fairly distributing throughput degradations among difierent  ows when there isinsu–cient link capacity, due to channel or tra–c conditions.In this chapter, we deflne the reference period (RP) as a series of frames on which FDELChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 81must try to guarantee the fairness among all  ows. Its length is decided by the system (or thesystem operator). If the length of the RP is one frame, FDEL will distribute the current frame’sexcess PLR for each frame. If the length of RP is n frames, in every frame, FDEL will try todistribute the excess PLR among the previous n¡1 frames and the current fame. The length ofthe RP can also be the whole lifetime of the system (from the start of the system to the currentframe), which means that FDEL will try to distribute the life time excess PLR (the excess PLRfrom the beginning of a  ow to the current frame) of all active  ows. Such a design gives thesystem the  exibility to flt difierent practical scenarios. Given a frame t (t 2 f1;2;3;g), wedenote the RP for the frame t as TRP;t, which represent the RP ending on the current frame.Consider its length is LRP. So TRP;t is from the beginning of frame t¡LRP + 1 to the end offrame t. Then the excess PLR of class j user k during the RP is (PLRTRP;tj;k ¡`j)+. Here (:)+means that if the value of (:) is negative it is converted to zero.When distributing the excessive PLR, FDEL also considers the priorities of difierent  ows.This is accomplished by deflning a fairness weight (FW) for each  ow, which is decided by thesystem (or the system operator) when the  ow is admitted into the system. The FW of  ow kof class j is denoted  j;k.We deflne the fairness factor (FF) FFj;k as the weighted excess PLR of user k of class jduring the RP.FFj;k = (PLRTRP;tj;k ¡`j)+ j;k ;j 2 1:::J;k 2 1;:::;Kj (3.8)In FEDL, fairness is satisfled if:FFj;k = FFi;l;8i;j 2 1:::J;k 2 1:::Kj;l 2 1:::Ki (3.9)Though we deflne FF as the weighted excess PLR, it also re ects the throughput degradationChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 82of each  ow as follows.FFj;k = (PLRTRP;tj;k ¡`j)+ j;k= 1 j((1¡`j)¡(1¡PLRTRP;tj;k ))+= 1 jPPTRP;tj;k((1¡`j)PPTRP;jj;k ¡(LPTRP;jj;k ))+ (3.10)Here (1 ¡ `j)PPTRP;jj;k is the number of packets expected to be transmitted during TRP;tsince there are PPTRP;jj;k packets processed and the  ow can tolerate PLR up to `j. Also,PPTRP;jj;k ¡LPTRP;jj;k is the number of packets successfully transmitted among PPTRP;jj;k packets.Essentially, FF is equivalent to the weighted throughput degradation ratio. Note that FW heredetermines how tra–c  ows can share the excess PLR. So it should not be designed based onthe PLR requirements directly. Instead, it should be determined based on how important thePLR requirements should be satisfled for the tra–c  ows.Equation (3.9) gives the fairness constraint. It can be directly applied to the scheduling ofMUPs-to calculate of FF over the RP ending at the current frame. However, in the case ofMAT, to schedule 2UPs, 3UPs, etc., which do not contribute to the PLRs of the RP ending atthe current frame, we must predict the FF of future frames. For example, 2UPs are scheduledbased on the estimated FF for the RP ending at the next frame, since 2UPs become MUPs inthe next frame.Scheduling with FDEL has some advantages. Because of the rate variations of multimediatra–c, the number of MUPs may vary from frame to frame. So a good scheduling algorithmmust have the ability to adapt to the variations. FDEL, which is equivalent to fairly sharingthe throughput degradation ratio, can automatically provide more bandwidth in one frame tousers with more MUPs to balance the excessive PLR. The fairness constraint (3.9) also providesChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 83the  exibility of distributing excess PLR or throughout degradation among difierent classes ofusers with difierent QoS requirements. Note that efiectively, the FWs  represent the prioritiesof the users. This is because a  ow with a lower weight will have a better chance to transmitthe MUPs and therefore will result in a lower excess PLR and lower throughput degradationratio.3.3.4 Objective FunctionsIn this subsection we formally deflne the objective function of the cross-layer enhancementmethod proposed in this chapter. Since scheduling is performed frame by frame, the objectivefunction is updated every frame. As discussed before, we consider scheduling for two difierentcases of the bufier states in a frame, namely MAT and MAT.The scheduling task is straightforward in the MAT case. The algorithm should maximizethe throughput of the frame while meeting the PLR threshold for each  ow in the currentframe (note that it may not be possible to guaranteed the PLR threshold in the whole RP)and satisfying the FDEL constraint. Assuming that the current frame is frame t, the objectivefunction in this case is:maxPPtj;kfJXj=1KjXk=1PPtj;kg (3.11)s:t: PLRtj;k • `j;(PLRTRP;t+xj;k ¡`j)+ j;k =(PLRTRP;t+xi;l ¡`i)+ i;l ;8i;j 2 1:::J;k 2 1:::Kj;l 2 1:::Ki;x 2f0;1;2;3:::gThe flrst constraint makes sure that the PLR thresholds of all  ows are satisfled. Note thatPLRtj;k is the PLR of the  ow k of class j for the current frame. It is also efiectively the same asChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 84PERtj;k since no packet is dropped in frame t. The second constraint is the fairness constraint.Here TRP;t+x is the RP until the end of frame t+x. Note that as described in the last subsectionwe need to predict FF of the RP ending at frame t+x, in order to fairly schedule 2UPs, 3UPsand so on. CEPS chooses the number of packets from the current  ows as the ones scheduledfor the current frame. It maximizes the throughput by choosing as many packets as possible,while satisfying the above constraints.The other case MAT is that there are too many MUPs in a frame so that the schedulermust determine how many and which of them should be transmitted in the frame. In a singleuser system, we seek to minimize the PLR of the current frame if there are too many MUPsin a frame. Similarly, in a multi-user system, the algorithm aims to ensure that the sum ofFFs (weighted excess PLRs) of all  ows can be minimized for the RPending at the currentframe. It is equivalent to minimizing the sum of all weighted throughout degradation ratios.The objective function in this case is:minPPtj;kfJXj=1KjXk=1(PLRTRP;tj;k ¡`j)+ j;k g (3.12)s:t: (PLRTRP;tj;k ¡`j)+ j;k =(PLRTRP;ti;l ¡`i)+ i;l ;8i;j 2 1:::J;k 2 1:::Kj;l 2 1:::KiThe constraint in (3.12) ensures fairness among all  ows. CEPS also chooses the number ofpackets from current  ows as the ones scheduled for the current frame. The numbers are decidedto minimize the sum of FFs (weighted excess PLRs) for the RP. Note that 2UPs, 3UPs andso on are not scheduled in this case. So we only need to consider the fairness constraints withrespect to the current frame.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 85Using the above objective functions, the overall PLR can be optimized (i.e., instead of op-timizing PER and PDR separately) subject to the FDEL constraint. Efiectively, the algorithmconsiders both the physical layer situation and status of the MAC layer queues.3.4 The Proposed CEPS Algorithm3.4.1 Basic PrinciplesWith the fairness constraint and objective functions provided by (3.11) and (3.12) in the pre-vious section, we discuss how they can be realized in a practical system in this section.Because of the discrete nature of packet-switched systems, it is obvious that the fairnessconstraints in (3.11) and (3.12) cannot hold perfectly. In practical systems, the proposed CEPSalgorithm schedules packets one by one like other algorithms for packet-switched networks [1{3]. Speciflcally, it selects a packet from the  ow with the largest FF (weighted excess PLR) sothat the fairness constraints can be met as much as possible. Note that, to transmit one moreMUP, the FF (weighted excess PLR) will decrease a little bit. In this way, it can try the bestto ensure the FFs of all  ows are as close as possible.At the beginning of every frame, the algorithm does not know whether there are too manyMUPs. While FFs (or predicted FFs) of all  ows determine which packets will be served, thealgorithm simply adds packets as long as the PER of each user is below its PLR threshold.Note that for both MAT and MAT cases, the scheduling does the same thing as above. If allpackets can be scheduled in this way, the work is done. If the PER of any user reaches to itsPLR threshold during the process, the algorithm looks at the bufier to see whether there arestill MUPs not scheduled. If there are no MUPs in the bufier, it can be concluded that theChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 86case is MAT, and the scheduling should stop here as the objective for MAT is already achieved.If there are still MUPs in the bufier, it is MAT and further work need to be done for thecross-layer optimization. For case MAT, the algorithm then schedules packets one by one andsee whether the sum of all weighted excess PLR is decreasing. Scheduling stops when the sumof all FFs (weighted excess PLRs) stops decreasing (and start increasing). In this way, theminimum sum of FFs (weighted excess PLRs) is found.Based on the basic principles given above, we describe the CEPS algorithm in details asfollows. Our focus is to support three types of tra–c: conversational/voice, streaming videoand interactive data. Note that background data tra–c can also be easily supported usingthe residual capacity. In the proposed CEPS algorithm for MC-CDMA networks, scheduling apacket consists of three stages. In the flrst stage, which user should be served next is decidedaccording to the fairness constraint in the objective functions in Section 3.3.4, and one of itspacket is selected out. In the second stage, the selected packet is put into a speciflc slot in theframe, which aims to maximize the residual bandwidth and maximize the multi-code beneflt. Inthe third stage, the algorithm determines whether to end the scheduling by checking the sum ofweighted excess PLR in the case of MAT, which is based on the discussion in the optimizationobjective in (3.12) in Section 3.3.4. Figure 3.1 shows the  ow chart of the proposed CEPSalgorithm. As shown by simulation results presented later, the system performance can begreatly enhanced by CEPS.To facilitate the description, we make some more deflnitions of the system states at thebeginning of a frame and the QoS requirements of difierent tra–c classes here. For user kof tra–c class i, we assume that the numbers of processed and lost packets in the previous sframes are ‰i;k;s and ‡i;k;s, respectively. The numbers of MUPs, 2UPs, 3UPs, , for this user inChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 87the current frame are m(1)i;k, m(2)i;k, m(3)i;k, and so on. The PLR requirement and the FW of a classi user k are `i and  i;k, respectively.3.4.2 Stage 1In stage 1, an appropriate user is chosen to be served next and one of its packet is selected out.It is obvious that MUPs must be served before other packets, as they will be dropped if nottransmitted in the current frame while other packets can wait to be sent out in the next frame.Similarly, 2UPs must be served next, followed by 3UPs, and so on.As we discussed in Section 3.4.1, the algorithm will choose the user with the largest FF(weighted excess PLR) to serve next, among all users with MUPs (or 2UPs if there are noMUPs, 3UPs if there are no 2UPs, and so on) in the bufier. This ensures that the fairnessconstraint is satisfled as much as possible. According to the deflnitions of the FF in (3.8) and(3.10), the algorithm calculates the FFs as follows.1. While scheduling MUPs, the FF of user k in class i is:ˆi;k = 1 i;k0@‡i;k;LRP¡1 +m(1)i;k ¡zi;k +·i;k(zi;k)‰i;k;LRP¡1 +m(1)i;k¡`i1A+(3.13)Here zi;k is the number of scheduled MUPs of the user and ·i;k(zi;k) is the expectednumber of packet errors for the zi;k scheduled packets. The term ‰i;k;LRP¡1 +m(1)i;k is theexpected number of processed packets in TRP;t, and ‡i;k;LRP¡1 +m(1)i;k ¡zi;k +·i;k(zi;k) isthe expected number of lost packets in TRP;t. Essentially, (3.13) gives the FFs at the endof this frame if the scheduling is ended at this point. Note that here ·i;k(zi;k) depends onChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 88all packets which have already been scheduled in this frame, how the packets are put intoslots and also the physical layer channel status.2. While scheduling 2UPs, the predicted FF is:ˆi;k = 1 i;k0@‡i;k;LRP¡1 +m(2)i;k ¡z2i;k +·i;k(m1i;k +z2i;k)‰i;k;LRP¡2 +m(1)i;k +m(2)i;k¡`i1A+(3.14)Here z(2)i;k is the number of 2UPs already scheduled for the user in the current frameand ·i;k(m(1)i;k + z(2)i;k) is the corresponding expected number of packet errors. Note that,m(1)i;k MUPs must have been scheduled. The processed and lost packets in TRP;t+1 are‰i;k;LRP¡2 + m(1)i;k + m(2)i;k and ‡i;k;LRP¡2 + m(2)i;k ¡ z(2)i;k + ·i;k(m(1)i;k + z(2)i;k), respectively.Although there are no packet drops in the frame (since all MUPs have been scheduledalready), we consider the packets that will be dropped in the next frame if the schedulingstop at this point and no further packet scheduling occurs in the next frame.3. The FF is similarly deflned by modifying (3.14) for scheduling 3UPs, 4UPs, ...In stage 1, FFs are used to determine the service sequences. However, they are calculatedin the stage 2 since some information needed for calculation can only be available in stage 2.3.4.3 Stage 2In stage 2, CEPS algorithm puts packet into slots wisely maximize the residual bandwidthafter the target PLRs for all packets scheduled are satisfled so that as many packets with lowerurgency can be transmitted as possible. Of course, a random assignment that does not optimizeanything like in some previous works [2, 3, 21], can also be used here.Since packets from the same user uses orthogonal codes, the algorithm always tries its bestto assign multiple packets from the same user in the same time slot to maximize the systemChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 89performance. CEPS maintains a counter and an array for each user. The counter stores thenumber of packets being selected from the bufier of the user’s terminal and the array recordsthe slot positions of the packets as scheduled for transmissions in the frame. Every time apacket is selected in stage 1, the counter for the corresponding user increases by one. CEPSthen tries to put the packet into some slot with packets from the same user.If after the packet added to the frame, all packets scheduled can still keep their PLR thresh-old, the scheduling process returns to the stage 1 directly. However, if all slots are \fllled up"in the sense that adding one more packet to the slot will lead to the PERs of some packetsto become higher than their corresponding target PLR, the scheduling process goes to stage3 if there are still MUPs in the bufier (case MAT), or the scheduling process ends directly(case MAT). In stage 3, whether or not this new packet is added to the frame is determined bywhether the sum of FFs (weighted excess PLRs) decreases after the addition.Optimal packet coordination is an NP-hard problem. The above process can flnd a relativelygood solution. Note that FFs are needed to assist the operation. Given the transmissionparameters of the packets, the expected PERs can be easily obtained from a table calculatedfrom (3.1), (3.2) and (3.3) (or similar physical layer channel model). The FFs can be determinedfrom (3.13) or (3.14), and then the sum of the FFs (weighted excess PLR) can be calculated.These metrics are also used by stage 1 and stage 3 to make decisions.3.4.4 Stage 3While the capacity of a frame is easy to calculate for traditional scheduling algorithm, it becomesan undetermined one for our cross-layer enhancement. Actually, the capacity depends on whichpackets we choose to send in the frame. So, according to the discussion in Section 3.3.4, CEPSChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 90tries to minimize the sum of FFs (weighted excess PLR) for all users.In stage 3, CEPS determines when to stop the scheduling more packets for transmissionsin the current frame in case MAT. Generally, one more packet can always be scheduled if theframe has not been \fllled up" (as deflned in the previous subsection). If the frame has been\fllled up", a packet can be scheduled only if it is a MUP (in the MAT case) and the sum ofFFs (weighted excess PLR) is decreased by scheduling the packet in some slot in the currentframe. So, stage 3 is only needed when the frame is \fllled up", i.e., only when scheduling a newpacket violates the target PLR of some packets that have already been scheduled. Essentially,CEPS delays the packet scheduling to the next frame if the new packet is not a MUP. Otherwiseit will attempt to schedule the packet and compare the resulting sum of FFs (weighted excessPLRs) with the previous value to see whether the system performance is enhanced. If not, theMUP is not scheduled but dropped instead. The dropping of a MUP indicates that the frameis truly full and then the scheduling algorithm ends.3.5 Performance EvaluationA simulation model was implemented in C++ to evaluate the performance of the proposedCEPS algorithm and to compare it with FPLS [3] and PSDRDG [2]. Note that FPLS was notoriginally designed for MC-CDMA systems. To help it take the advantage of multi-codes, theslot assignment mechanism proposed in Section 3.4.3 is used also with FPLS. Some commonparameters for all simulations are listed in Table 3.1. In the simulations, the physical layer isapplied statistically and the data link layer is operated step by step. The results are generatedfrom the average of a couple of same simulations, which runs at least 100,000 TDMA frames.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 91As mentioned before, three classes of tra–c are considered: conversational/voice tra–c,streaming video tra–c, and interactive data tra–c. For the voice tra–c, each tra–c source isrepresented by the commonly used two-state (on/ofi) Markov model [23]. During the \on" or\talk-spurt" state, packets are generated at a constant rate of one packet per frame. Duringthe \ofi" or \silence gap" state, no packet is generated. The durations of the \on" and \ofi"states are exponentially distributed with mean values of 1.0 s and 1.35 s, respectively. For thevideo tra–c, the tra–c source is modeled by a Markov-Modulated Poisson Process [24] withthe stationary distribution of (0.2, 0.4, 0.3, 0.1). Packets are generated based on a Poissonprocess with the rates of (2, 4, 6, 8) packets per frame in the respective states. The data tra–csource is modeled by the on-ofi model proposed in [23]. Each data tra–c source alternatesbetween \on" and \ofi" states. During the \on" state, messages are generated based on aPoisson distribution with the rate 0.5 messages per frame. Each message consists of 6 packets.No message is generated during the \ofi" state. The durations of the \on" and \ofi" states arevaried based on the Weibull distribution. The shape and scale parameters are 0.88 and 3.10,respectively for the \on" state, and 0.88 and 21.4, respectively for the \ofi" state. The typicalQoS parameters used in this chapter are based partly on [2] and are listed in Table 3.2. Alsothe length of the RP is set to 100 frames.We flrst study the cross-layer performance enhancement achieved by CEPS. To fairly com-pare CEPS with FPLS and PSDRDG, we set the FWs according to the target PLRs. Figures3.2-3.5 show the simulation results with 30 video users, 50 data users and the number of voiceusers varied from 70 to 145. Figure 3.2 shows the PLRs of difierent tra–c classes. When thenumber of voice users is lower than 90, all three algorithms achieve the same PLR for each tra–cclass, because the PLR is dominated by the PER for all three algorithms (i.e., PDR … 0). How-Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 92ever, when the number of voice users increases, Figure 3.2 shows that CEPS achieves a muchlower PLR for each tra–c class, and it can support more than 125 voice users with PLR < 0:01,whereas the other two algorithms can only support about 90 voice users. The results clearlydemonstrate the efiectiveness of the cross-layer enhancement of CEPS in system capacity (about39%). Figure 3.3 compares the mean packet delay for all tra–c classes. Note that the meandelay > 0.01 (half a frame) because a packet must wait on average at least half a frame beforethe start of the frame in which it can be transmitted. Also, the mean delay is always lowerthan the delay bound by at least one frame because a packet must be sent out before it expires(i.e., a packet expiring in frame x must be sent in or before frame x¡1). It can be seen thatfor video and data tra–c, which has a delay bound of more than one frames, CEPS can achievea lower mean delay when the number of voice users is moderate. In the case of voice tra–c,the mean delays for the three algorithms are similar because all packets have to be transmittedwithin one frame or else they will be dropped. Figure 3.4 conflrms that the maximum delayexperienced by each user is lower than the required delay bound. The results also reveal thatfor video tra–c and data tra–c, CEPS can achieve a lower maximum delay when the numberof voice users is small. Figure 3.5 shows the throughput of difierent tra–c classes. It can beseen that when the number of voice users increases, the voice throughput increases while thevideo throughput decreases because some resources are allocated to the additional voice users.When the number of voice users is larger than 85 (i.e., the system is heavily loaded and thereare some packets dropped, see Figure 3.2), CEPS yields a higher throughput for voice and videotra–c than the other two algorithms. The data tra–c throughput for all three algorithms aresimilar. Because of its very low target PLR and smaller FW, data tra–c packets are rarelydropped. Thus the throughput variation (caused by the variation of the PLR) on data tra–cChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 93is too small to be observed. Figures 3.6-3.8, respectively, show the PLR, average access delayand throughput performance of the system with 100 voice users, 50 data users and the numberof video users varying from 21 to 36. In general, the performance is similar to that presentedabove (the capacity of the system is increased by 22%). Similar to the previous scenario, theseflgures show that CEPS can achieve a better performance than the other two algorithms.Next, we show the beneflts of using cross-layer optimization when the channel condition or1 2 varies. Note that1 2 gives the reciprocal of the normalized noise variance (including theinter-cell interference). That means, the larger the value of 1 2, the better the channel conditionis and the larger the SINR is as determined by (3.1). Figures 3.9-3.11 show the performanceof the system with 100 voice users, 30 video users and 50 data users, while 1 2 varies from9dB to 10.4dB. Figure 3.9 shows that as 1 2 increases, the PLRs of all tra–c classes decrease;however, CEPS clearly achieves better PLR performance than the other algorithms for eachtra–c class. Note that there is a sharp decrease of PLR between 1 2 = 9:8dB and 1 2 = 9:9dB.With 1 2 • 9:8dB, a video or voice packet can tolerate at most 8 interfering packets but with1 2 ‚ 9:9dB, this number is increased to 9. Thus, the system capacity is increased signiflcantlyand the PLRs of all tra–c classes decrease dramatically. There is another sharp decrease forthe PSDRDG and the FPLS between 1 2 = 10:2dB and 1 2 = 10:3dB. However, it has almostno impact to CEPS. With 1 2 = 10:2dB, CEPS can already serve all tra–c classes with almostno packet drop. Thus a further increase in system capacity at that point does not benefltCEPS much. Figure 3.10 shows that as 1 2 decreases, the mean packet delay of each tra–c classdecreases also, as expected. As explained previously, the mean delay of voice tra–c for the threealgorithms are similar. For other tra–c classes, for 1 2 from 9dB to 9.8dB, all three algorithmshave almost the same mean packet delay because the system is a bit overloaded such that almostChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 94all packets must wait until the deadline to be sent out. From 9:9dB to 10:2dB, CEPS exhibitsa lower mean packet delay than the other two algorithms because of cross-layer enhancement.Between 10.3dB and 10.4dB, the mean packet delays for the three algorithms are again similarbecause the system capacity is large enough so that almost all packets can be served within oneframe. Figure 3.11 shows the throughput of each tra–c class under difierent channel conditions.It can be seen that CEPS can achieve a higher throughput for video tra–c and voice tra–cthan the other two algorithms especially when 1 2 is small. When 1 2 increases to 10.3dB, thethroughput enhancement disappears because nearly all packets can be transmitted due to verygood channel condition. As explained earlier, the throughput for the data tra–c are almost thesame for the three algorithms because of the very low PLR target.In summary, the above simulation results show the great beneflts of the cross-layer enhance-ment in CEPS. The PLRs of difierent tra–c classes are reduced so that the system can supportmore users. Furthermore, the mean packet delay is reduced and the throughput is increasedunder most conditions. The simulation results also show that CEPS has a better ability to copewith the variations of noise and inter-cell interference. It can meet the target PLR over a widerrange of 1 2 than the other two algorithms.Next, we show the efiectiveness of CEPS in providing fairness. We flrst compare all threealgorithms with the target PLR set according to (i.e., proportional to) the FW. Figure 3.12shows the weighted excess PLR of difierent tra–c classes for the three algorithms when thereare 100 voice users, 50 data users and difierent number of video users. The weighted excessPLRs are all zero when the number of video users is small. However, they go up when thereare more video users. It can be seen that only CEPS can achieve the desirable result of havingapproximately the same weighted excess PLR for all tra–c classes. The other two algorithmsChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 95have difierent weighted excess PLRs for difierent tra–c classes when the number of video usersis not so large, because FPLS or PSDRDG only proportionally distribute the PDR to thedifierent tra–c classes without considerations on the difierent PERs. Figure 3.13 shows theweighted excess PLR when there are 30 video users and 50 data users, and the number ofvoice users is varied between 70 and 160. It shows a similar result to that presented in Figure3.12. Hence, with the proposed cross-layer optimization framework, CEPS can achieve betterfairness. Furthermore, from these two flgures, we can also observe that the weighted excessPLR of CEPS is much lower than those of FPLS and PSDRDG.To further illustrate the  exibility of CEPS, we use a difierent set of QoS parameters forthe three tra–c classes as listed in Table 3.3. In this scenario, the FWs are not set accordingto the target PLRs. Figure 3.14 shows the weighted excess PLR of all tra–c classes whenthere are 100 voice users, 50 data users and difierent number of video users. Note that FPLSalways proportionally distributes the PDR to difierent users with respect to their target PLRsand PSDRDG always proportionally distributes the PDR to difierent users with respect to theirFWs. It can be seen that for FPLS, the weighted excess PLRs for difierent tra–c classes divergesubstantially, while PSDRDG can provide the same weighted excess PLRs for difierent tra–cclasses when the number of video users is large. However, when the number of video users isnot so large, say 28, the target PLR of voice and video tra–c is satisfled while that of datatra–c not; so it weakens the fairness. Compared with these two algorithms, CEPS meets thetarget PLR of difierent tra–c classes while keeping the weighted excess PLRs the same. Figure3.15 shows a similar result with 30 video users, 50 data users and difierent number of voiceusers. It can also be seen that FPLS has diverged weighted excess PLR and PSDRDG cannotmeet the target PLR of all tra–c classes at the same time. Again, CEPS outperform the otherChapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 96algorithms by meeting the two aforementioned requirements.3.6 SummaryIn this chapter, we have presented a cross-layer optimization for scheduling multimedia tra–cin MC-CDMA networks. Based on it, we proposed a novel uplink scheduling algorithm calledCEPS. CEPS can also be applied to downlink transmission with a few revisions. The algorithmhas two new contributions. First, it jointly optimizes link layer PDR and physical layer PER toimprove the overall PLR and hence the system performance. Second, it distributes the excesspacket losses according to predeflned weights so as to maintain fairness more efiectively and exibly. We have performed extensive simulations to compare the performance of the proposedCEPS algorithm with two previously proposed scheduling algorithms that proportionally dis-tribute excess PDR. The simulation results show that the CEPS algorithm can greatly decreasethe PLR experienced by users especially when the tra–c demand is heavy, and support moreusers in the system while meeting a specifled PLR objective. The simulation results also showthat CEPS is also efiective and more  exible in maintaining fairness among difierent users.Note that the superior performance of CEPS is because of its cross-layer design and it does notrelax the fairness target to achieve better system performance.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 97Table 3.1: Parameters for The SystemParameters ValuesProcessing Gain 32Normalized noise variance 0:1Packet size 511 bitsPayload size 229 bitsTolerable bit errors 38 bitsTime slot per frame 20Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 98Table 3.2: Typical QoS Parameters Setting (Setting 1) for Difierent Tra–c Classes in ThisChapter.Parameters ValuesVoice target PLR 10¡2Video target PLR 10¡2Data target PLR 10¡5Voice delay bound in frames 2Video delay bound in frames 20Data delay bound in frames 20Voice FW 1Video FW 1Data FW 0:001Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 99Table 3.3: Another QoS Parameters Setting (Setting 2) for Difierent Tra–c Classes in ThisChapter.Parameters ValuesVoice target PLR 2£10¡2Video target PLR 10¡2Data target PLR 10¡5Voice delay bound in frames 2Video delay bound in frames 20Data delay bound in frames 20Voice FW 1Video FW 2Data FW 0:1Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 100Figure 3.1: Flow chart of the proposed CEPS algorithm.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 10180 100 120 140 160videoNumber of voice users 60 80 100 120 140 16010−310−210−1100 voiceNumber of voice usersPacket loss ratio60 80 100 120 140 16010−610−510−410−3 dataNumber of voice usersPacket loss ratioCEPSFPLSPSDRDGtarget PLRFigure 3.2: Packet loss ratio for difierent tra–c classes when there are 30 video users, 50 datausers and variable number of voice users.80 100 120 140 160Number of voice usersvideo  CEPSFPLSPSDRDG60 80 100 120 140 1600.010.0150.020.0250.030.0350.040.0450.05Number of voice usersMean packet delay (s)voice60 80 100 120 140 16000.050.10.150.20.250.30.350.40.450.5Number of voice usersMean packet delay (s)datadelay boundFigure 3.3: Mean packet delay for difierent tra–c classes when there are 30 video users, 50data users and variable number of voice users.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 10270 80 90 100 110 120 130 140 15000.050.10.150.20.250.30.350.40.450.5Number of voice usersMaximum packet delay (s)  CEPSFPLSPSDRDGvideo and datavoiceFigure 3.4: Maximum packet delay for difierent tra–c classes when there are 30 video users,50 data users and variable number of voice users.70 80 90 100 110 120 130 140 15002004006008001000120014001600Number of voice usersThroughput for each class of traffic (kbps)  CEPSFPLSPSDRDGvideovoicedataFigure 3.5: Throughput for difierent tra–c classes when there are 30 video users, 50 datausers and variable number of voice users.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 10325 30 35 40videoNumber of video users 20 25 30 35 4010−310−210−1100 voiceNumber of video usersPacket loss ratio20 25 30 35 4010−610−510−410−3 dataNumber of video usersPacket loss ratioFPLSPSDRDGCEPStarget PLRFigure 3.6: Packet loss ratio for difierent tra–c classes when there are 100 voice users, 50 datausers and variable number of video users.25 30 35 40videoNumber of video users 20 25 30 35 400.010.0150.020.0250.030.0350.040.0450.05 voiceNumber of video usersMean packet delay (s)20 25 30 35 4000.050.10.150.20.250.30.350.40.450.5 dataNumber of video usersMean packet delay (s)FPLSPSDRDGCEPSdelay boundFigure 3.7: Mean packet delay for difierent tra–c classes when there are 100 voice users, 50data users and variable number of video users.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 10420 22 24 26 28 30 32 34 36020040060080010001200140016001800Number of video usersThroughput for each class of traffic (kbps)  CEPSFPLSPSDRDGvideovoicedataFigure 3.8: Throughput for difierent tra–c classes when there are 100 voice users, 50 datausers and variable number of video users.9.5 10 10.5video1/σ2 (dB) 9 9.5 10 10.510−310−210−1100 voice1/σ2 (dB)Packet loss ratio9 9.5 10 10.510−610−510−410−3 data1/σ2 (dB)Packet loss ratioFPLSPSDRDGCEPStarget PLRFigure 3.9: Packet loss ratio for difierent tra–c classes with 100 voice users, 30 video usersand 50 data users.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 1059.5 10 10.5video1/σ2 (dB) 9 9.5 10 10.50.010.0150.020.0250.030.0350.040.0450.05 voice1/σ2 (dB)Mean packet delay (s)9 9.5 10 10.500.050.10.150.20.250.30.350.40.450.5 data1/σ2 (dB)Mean packet delay (s)FPLSPSDRDGCEPSdelay boundFigure 3.10: Mean packet delay for difierent tra–c classes with 100 voice users, 30 video usersand 50 data users.9 9.5 10 10.5020040060080010001200140016001/σ2 (dB)Throughput for each class of traffic (kbps)  CEPSFPLSPSDRDGdatavoicevideoFigure 3.11: Throughput for difierent tra–c classes with 100 voice users, 30 video users and50 data users.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 10627 28 29 30 31 32 33 34 35 3610−310−210−1100Number of video usersWeighted excess PLR  VideoVoiceDataFPLSPSDRDGCEPSFigure 3.12: Weighted excess PLR of difierent tra–c classes with 100 voice users, 50 datausers and variable number of video users.80 90 100 110 120 130 140 15010−310−210−1100Number of voice usersWeighted excess PLR  VideoVoiceData FPLSPSDRDGCEPSFigure 3.13: Weighted excess PLR of difierent tra–c classes with 30 video users, 50 data usersand variable number of voice users.Chapter 3. CEPS for Multimedia Tra–c over MC-CDMA Networks 10728 30 32 34 36 3810−410−310−210−1100Number of video usersWeighted excess PLR  VideoVoiceDataPSDRDGCEPSFPLSFPLSFigure 3.14: Weighted excess PLR of difierent tra–c classes with 100 voice users, 50 datausers, variable number of video users and QoS parameters in Table 3.3.80 90 100 110 120 130 140 150 160 17010−410−310−210−1100Number of voice usersWeighted excess PLR  VideoVoiceDataPSDRDG CEPSFPLSFPLSFigure 3.15: Weighted excess PLR of difierent tra–c classes with 30 video users, 50 datausers, variable number of voice users and QoS parameters in Table 3.3.Bibliography 108Bibliography[1] I. F. Akyildiz, D. A. Levine, and I. Joe, \A slotted CDMA protocol with BER schedulingfor wireless multimedia networks," IEEE/ACM Trans. Netw., vol. 7, no. 2, pp. 146-158,April 1999.[2] P. Y. Kong, K. C. Chua, and B. Bensaou, \A novel scheduling scheme to share droppingratio while guaranteeing a delay bound in a multicode-CDMA network," IEEE/ACM,Trans. Networking, vol. 11, no. 6, pp. 994-1006, Dec. 2003.[3] V.HuangandW.Zhuang, \QoS-orientiedpacketschedulingforwirelessmultimediaCDMAcommunications," IEEE Trans. Mobile Comput., vol. 3, pp. 73-85, Jan.-Mar. 2004.[4] M. A. Arad and A. Leon-Garcia, \Scheduled CDMA: A hybrid multiple access for wirelessATM networks," Proc. of IEEE Pers., Indoor & mobile Radio Commun. 1996, pp. 913-917,Oct. 1996.[5] O. Gurbuz and H. Owen, \Dynamic resource scheduling strategies for QoS in W-CDMA,"Proc. of IEEE GLOBECOM 1999, pp. 183-187, Dec. 1999.[6] X. Liu, E. K. P. Chong and N. B. Shrofi, \Opportunistic transmission scheduling withresource-sharing constraints in wireless networks," IEEE J. Selected Areas Commun., vol.19, no. 10, pp. 2053-2064, Oct. 2001.[7] S. S. Kulkarni and C. Rosenberg, \Opportunistic scheduling for wireless systems withmultiple interfaces and multiple constraints," Proc. of the 6th ACM/SIGCOM MSWiM,pp. 11-19, Sep. 2003.Bibliography 109[8] S. S. Kulkarni and C. Rosenberg, \Opportunistic scheduling policies for wireless systemswith short term fairness constraints," Proc. of IEEE GLOBECOM 2003, pp. 533-537, Dec.2003.[9] S. H. Ali and V. C. M. Leung, \Mobility assisted opportunistic scheduling for downlinktransmissions in cellular data networks," Proc. of IEEE WCNC2005, pp. 1213-1218, Mar.2005.[10] Q. Liu, S. Zhou and G. B. Giannakis, \Cross-layer scheduling with prescribed QoS guar-antee in adaptive wireless networks," IEEE J. Selected Areas Commun., vol. 23, no. 5, pp.1056-1066, May 2005.[11] D.Zhao, X.ShenandJ.W.Mark, \RadioresourcemanagementforcellularCDMAsystemssupporting heterogeneous service," IEEE Trans. Mobile Computing, vol. 2, no. 2, pp. 147-160, Apr.-Jun. 2003.[12] Q. Liu, S. Zhou and G. B. Giannakis, "Queuing with adaptive modulation and coding overwireless links: cross-layer analysis and design," IEEE Trans. Wireless Commun., vol. 4,no. 3, pp. 1142-1153, May 2005.[13] Q. Liu, S. Zhou and G. B. Giannakis, "Cross-layer combining of adaptive modulation andcoding with truncated ARQ over wireless links," IEEE Trans. Wireless Commun., vol. 3,no. 5, pp. 1746-1755, May 2005.[14] C. Lin and R. D. Gitlin, \Multi-code CDMA wireless personal communication networks,"Proc. of IEEE Commun., pp. 1060-1064, Jun. 1995.Bibliography 110[15] A. Hamid, R. Hoshyar, and R. Tafazolli, \Joint rate and power adaptation for MC-CDMAover tempo-spectral domain," Proc. IEEE WCNC2008, pp. 969-973, Mar. 2008.[16] Z. Han, G. Su, A. Kwasinski, M. Wu, and K. J. R. Liu, \Multiuser distortion managementof layered video over resource limited downlink multicode-CDMA," IEEE Trans. WirelessCommuni., vol. 5, no. 11, pp. 3056-3067, Nov. 2006.[17] B. S. Thian, Y. Wang, T. T. Tjhung, and L. W. C. Wong, \A hybrid receiver schemefor multiuser multicode CDMA systems in multipath fading channels," IEEE Trans onVehicular Tech., vol. 56, no. 5, pp. 3014-3023, Sept. 2007.[18] 3GPP, \Spreading and modulation (FDD)," 3GPP TS25.213, v3.4.0, Dec. 2000.[19] A. Farrokh and V. Krishnamurthy, \Opportunistic scheduling for streaming multimediausers in high-speed downlink packet access (HSDPA)," IEEE Trans. Multimedia, vol. 8,no. 4, pp. 844-855, August 2006.[20] C. S. Chang and K. C. Chen, \Medium access protocol design for delay-guaranteed mul-ticode CDMA mutimedia networks," IEEE Trans. Wireless Commun., vol. 2, no. 6, pp.1159-1167, Nov. 2003.[21] P. Y. Kong, K. C. Chua and B. Bensaou, \Multicode-DRR: A packet-scheduling algorithmfor delay guarantee in a multicode-CDMA network," IEEE Trans. Wireless Commun., vol.4, no. 6, pp. 2694-2704, Nov. 2005.[22] 3GPP, \Quality of service (QoS) concept and architecture," 3GPP TS23.107, v6.4.0, Mar.2006.Bibliography 111[23] L. Lenzini, M. Luise and R. Reggiannini, \CRDA: A collision resolution and dynamicallocation MAC protocol to integrate data and voice in wireless networks," IEEE J. Sel.Areas Commun., vol. 19, no. 6, pp. 1153-1163, June 2001.[24] F. Yu, V. Krishnamurthy and V. C. M. Leung, \Cross-layer optimal connection admissioncontrol for variable bit rate multimedia tra–c in packet wireless CDMA networks," IEEETrans. Signal Processing, vol. 54, no. 2, pp. 542-555, Feb. 2006.112Chapter 4Cross-Layer Optimization forMultimedia Transport overMulticode CDMA Networks 1An important task for contemporary packet-switched networks is to provision the QoS requiredto transport multimedia tra–c streams while e–ciently utilizing the system capacity. As wire-less spectrum can be expensive, it is particularly important to optimize multimedia transportover wireless networks so that more multimedia tra–c can be admitted into the system to en-hance the bandwidth utilization in the presence of a heavy tra–c load. We have proposed aCEPS algorithm in Chapter 3 to optimize the FLR of a MC-CDMA system. The objective ofCEPS is to schedule packets from difierent tra–c  ows by considering a FLR utility functioninstead of handling BER and FDR independently, so that the FLR utility is minimized anddifierent tra–c  ows can share the excess FLR (deflned as the FLR excess to the pre-designedtarget) fairly. CEPS performs the optimization frame by frame by meeting the optimization1A version of this chapter has been published. H. Chen, H. C.B. Chan and V. C.M. Leung, \Two cross-Layeroptimization methods for transporting multimedia tra–c over multicode CDMA networks," in Proc. of IEEEWCNC’07, March 2007Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 113objective while scheduling every single data frame. It does not take the advantage of the tra–cmodel or statistics of multimedia tra–c  ows. As a further enhancement of CEPS, in this chap-ter, we focus on optimizing the resource allocation in a MC-CDMA system by considering thetra–c model/statistics and tra–c dynamics of the system. We propose a cross-layer methodnamed tra–c adaptive scheme to optimize the maximum number of simultaneous data frametransmissions in the system, taking into account the packet arrival rate and the queue status.The problem is formalized as an MDP and solved by linear programming. Also, we providethe analysis of the system performance for the proposed optimization scheme in terms of theFLR, system throughput and packet access delay. To alleviate the computational complexityof the optimized scheme, we also propose an approximate method named rate adaptive scheme.By modeling multimedia tra–c using the Markov-modulated Poisson process (MMPP) tra–cmodel [22], the performance of these two methods is evaluated. We also implement a simu-lation model to validate the theoretical analysis and to compare the proposed schemes withother schemes. The results show that the system performance can be signiflcantly improvedby the cross-layer optimization methods in terms of FLR, throughput and the packet accessdelay, especially when the tra–c load of the system is heavy. Also, the results show that therate adaptive scheme can produce a performance close to the tra–c adaptive scheme, when thesystem tra–c load is heavy, although it is not as good as the latter when the system is lightlyloaded.The remainder of this chapter is organized as follows. Section 4.1 introduces the relatedwork. We describe the MC-CDMA system and the MMPP tra–c model in Section 4.2. InSection 4.3, we present an overview of the system operations on determining the maximumnumber of simultaneous transmissions, scheduling, and slot allocation. Then, we present theChapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 114queue analysis, tra–c adaptive optimization scheme, QoS analysis and rate adaptive scheme inSection 4.4. Section 4.5 gives the results and discussion. Section 4.6 summarizes the chapter.4.1 Related WorkPrevious work on CDMA networks usually aims to separately meet the physical layer QoSrequirement in terms of SINR or BER, and MAC layer QoS requirement in terms of FDR [1{4].Recently, many cross-layer methods have been proposed to improve the system performance ofwireless networks. For example, in [11, 12], based on the channel state awareness and an AMCmethod, the system can choose to serve a user with a better channel condition more often sothat the throughput of the system can be improved. In [13], using AMC, a flxed bandwidthis reserved for every QoS-guaranteed  ow based on the estimated efiective bandwidth and thechannel status, and then the tra–c is scheduled based on both the bufier status and the channelcondition for the speciflc user. In [14], the queue status and the channel status are used todetermine the spreading factor and the optimal number of simultaneous transmissions. In [15],a cross-layer design is proposed for IEEE 802.16/WiMAX networks. Speciflcally, the physicallayer information are used to determine link layer scheduling parameters. In [16], a cross-layerscheduling algorithm is proposed for a radio access network using a multicarrier air interfacein a multicell multiuser context. It considers channel, physical layer and application-relatedinformation to make the scheduling decisions.In general, all of the above-mentioned work [11{16] still deals with QoS at the physical andMAC layers separately. However, these two layers are in fact closely related since: 1) a dataframe is only correctly received when it is neither dropped at the MAC layer (due to deadlineChapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 115violation or queue over ow) nor corrupted by uncorrectable errors at the physical layer, and 2)allowing more simultaneous data frame transmissions in the CDMA channel reduces frame dropsat a given packet arrival rate but increases BER and hence frame corruptions due to heaviermultiple-access-interference (MAI). This means that there is a trade-ofi between minimizingthe MAC layer’s FDR and the physical layer’s BER. The optimal solution should thereforeminimize the total FLR at the MAC layer by jointly optimizing FDR and BER across theMAC and physical layers. Essentially, this aims to minimize the overall PLR experiencedby higher layers. Note that this cross-layer optimization method is particularly importantfor handling time-varying physical channels and variable bit rate multimedia tra–c in futurewireless communication systems. This research issue has gained much interest in recent years.For example, in [17], the queue status is taken into account in determining the SINR boundsfor AMC so that the overall FLR can be optimized. In [18], the upper and lower SINR boundsfor each AMC mode is designed based on the maximum retransmission time of the system.However, both designs are not applicable for CDMA systems and it assumes a Poisson tra–cmodel which is not suitable for multimedia tra–c. [19] proposes a two-dimensional markovchannel mode and an AMC threshold searching algorithm for a system employing AMC andautomatic repeat request. And with the queuing analysis of the system, the link layer packetarrival rate and the physical layer tolerable packet error rate are determined to provide speciflcFLR and delay. However, it requires exhaustive search for the optimization and it does notcount the dynamic of the tra–c  ows.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 1164.2 System Model4.2.1 Multicode CDMA SystemIn this chapter, we consider a multi-cell system employing TDMA and MC-CDMA in eachTDMA time slot. We focus on the uplink common tra–c channel in one radio cell. Withoutloss of generality, the uplink common tra–c channel is divided into TDMA frames of durationTf and each TDMA frame consists of a flxed number (F) of time slots, each with a duration ofTs. And also we assume that perfect signaling channels exist for the mobile stations to conveytheir states (e.g., data rates, queue lengths) at the end of each TDMA frame to the base station,and for the base station to inform the mobile stations the transmission schedule for the nextTDMA frame before it starts. Also, the channel status is also exchanged via the signalingchannel for power control purpose.We consider that randomly chosen pseudo-noise codes with the same spreading gain G areused in the system. For every mobile station, packets from the higher layer are fragmentedand encapsulated into data frames with the same speciflc size so that each data frame can beexactly transmitted in one time slot using one spreading code. To achieve difierent data rate,a mobile station may transmit more than one data frames 1) in more than one time slot withone code, 2) in one time slot with difierent codes, or 3) in more than one time slot with morethan one codes. Note that, the number of data frames transmitted by one mobile station inone time slot is limited by the power constraint on the mobile station. The maximum numberof codes to be used in one time slot is determined by the system to provide adequate physicallayer QoS BER. Essentially, it is the parameter that we hope to adapt to optimize the systemperformance in this chapter.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 117We know that with certain resource allocation schemes, the total tra–c load in a TDMAframe in each cell can be estimated and approximately distributed to each time slot. So theinter-cell interference can be estimated. Following a common practice, we assume that noiseand inter-cell interference follow a Gaussian distribution with the normalized variance ( 2).To facilitate the development of the analytical model, we also consider that all data framesuse non-orthogonal spreading codes even if they are from the same mobile station, like in manycurrent systems (for example, IS95). Furthermore, we assume that the near-far problem and thefading efiects are mitigated by perfect power control and can be neglected (an imperfect powercontrol may lead to inaccurate calculations and less efiectiveness of the proposed optimization).So, ber(u), the BER for a data frame if there are totally u data frames transmitted in the timeslot can be determined as in [1{3]. And given the channel coding scheme, the expected frameerror probability for such a data frame, fer(u), can be calculated based on the SINR too.4.2.2 MMPP Tra–cThe MMPP model has been shown to be efiective in representing many types of multimediatra–c, including voice [23], MPEG video [24] and general data [25]. We apply the MMPPmodel for all the tra–c  ows in the system (note that the Poisson model is a special case of theMMPP model).For simplicity, we consider that each mobile station has only one tra–c  ow. We assumethat there are C classes of MMPP tra–c  ows and Kc tra–c  ows for each class c in the system.A class c (c 2f1;:::;Cg) tra–c  ow has Sc difierent tra–c states and packets arrive followinga Poisson process with a speciflc rate Rc;s in each tra–c state s (s 2 f1;:::;Scg). Transitionsbetween tra–c states are governed by a continuous-time Markov chain (or more generally aChapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 118Markov renewal process). The inflnitesimal generating matrix for the Markov chain is deflnedas¡c =266666666664¡”c;(1;1); c;(1;2);:::; c;(1;Sc) c;(2;1);¡”c;(2;2);:::; c;(2;Sc)::: c;(Sc;1); c;(Sc;2);:::;¡”c;(Sc;Sc)377777777775(4.1)where  c;(i;j) (i;j 2 1:::Sc;i 6= j) is the transition rate from state i to state j for class ctra–c  ows and ”c;(i;i) = Pj6=i  c;(i;j) is the rate that a tra–c  ow leaves the state i. Wecan get the stationary distribution of the tra–c states of class c tra–c  ows as a row vector´c = [´c;1;´c;2;:::;´c;Sc], which must satisfy ´c¡c = 0 [26].As in many related studies, we apply an approximate discrete MMPP tra–c model in ouranalysis and optimization, instead of using the above continuous model directly. Note that, theaverage duration of one tra–c state is very long compared to a TDMA frame duration. So wecan safely assume that the tra–c state changes only occur at the boundaries of TDMA frames.In another word, we assume that the tra–c state remains unchanged during a TDMA frame.4.3 System OperationAt the beginning of a TDMA frame, the system flrst makes some decisions. Normally, it decideshow many simultaneous data frame transmissions at most can be accommodated in one timeslot (i.e., an upper bound for the simultaneous data frame transmissions), how many dataframes from each tra–c  ow should be scheduled, and how the time slots are allocated totransmissions of all scheduled data frames. After making the decisions, all the mobile stationsget informed by the base station via the reliable signaling channel. Then they get the scheduledChapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 119data frames out of the corresponding queue bufiers for the subsequent transmissions. Duringthe TDMA frame, all the scheduled data frames are transmitted via time slots based on theslot allocation decision. At the same time, newly arrived packets enter the respective queuesafter fragmentation and encapsulation. We assume that there is a queue bufier which can holdat most Vc data frames for every class c tra–c  ow. If the newly arrived data frames flnd afull bufier, it is simply dropped. We assume that data frames dropped and transmitted withuncorrectable errors can be handled by the upper layers, i.e., the MAC layer does not performdata frame retransmissions.In general, all the decision factors mentioned above can be optimized to enhance the systemperformance and QoS. In this chapter, as an example, we focus on deciding the maximumnumber of data frames (an upper bound) that can be simultaneously transmitted in each timeslot of a TDMA frame. The other two decision factors are also utilized in the optimization. Inthe following, we brie y discuss how the decisions are made and give examples on the schedulingand slot allocation methods.4.3.1 Maximum Number of Simultaneous TransmissionsGenerally, most CDMA systems aim to keep the physical layer BER below a threshold valueber0. It results a speciflc upper bound u = u0 of the number of data frames simultaneouslytransmitted in one time slot. This upper bound is governed by the levels of noise and inter-cellinterference. For the system introduced here, it is:u0 = argmaxu fber(u) • ber0g (4.2)Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 120This function is commonly used in existing CDMA systems. In this chapter, we propose amoptimization for the upper bound u of the number of simultaneous data frame transmissionsin one time slot. Note that if the aggregative packet arrival rate of all tra–c  ows are veryhigh or the queue bufiers of most users are almost full, it is better to slightly increase u sothat more data frames can be sent out in the current TDMA frame and the FDR can decreasedramatically. Of course the BER as well as the FER for the data frames transmitted in theTDMA frame may be a little higher. However, the proposed optimization may flnd the optimalu to minimize the total FLR (counting both FDR and FER) over time. The details of theoptimization are presented in Section 4.4.4.3.2 SchedulingThe scheduling algorithm is an important element of the system. It decides how to scheduledata frames from each tra–c  ow in a TDMA frame so that the system can provide fairness todifierent tra–c  ows. Here, we describe a scheduling decision as a scheduling decision vector,M = (m1;1;m1;2;:::;m1;K1;m2;1;:::;mC;KC): (4.3)In the vector, mc;k is the number of data frames to be transmitted for class c tra–c  ow k inthe TDMA frame according to the scheduling decision.One major factor for making the scheduling decision is the bufier states of all tra–c  owsat the beginning of the TDMA frame. It can be described as a bufier state vector,N = (n1;1;n1;2;:::;n1;K1;n2;1;:::;nC;KC) (4.4)and nc;k is the number of data frames in the bufier for class c tra–c  ow k. Note that thenumber of data frames scheduled for any tra–c  ow cannot be greater than the number of dataChapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 121frames in its queue, i.e., mc;k • nc;k. Also, it must be aware that there is a bufier size Vc forany class c tra–c  ow, i.e, nc;e • Vc.Another important factor is the tra–c states of all tra–c  ows in the TDMA frame. It canbe described as a tra–c state vector,D = (d1;1;d1;2;:::;d1;K1;d2;1;:::;dC;KC) (4.5)and dc;k is the tra–c state of class c tra–c  ow k in the TDMA frame. With the tra–c state,the system knows the packet arrival rate of all the tra–c  ows.Also, the decision is limited by the maximum number (the upper bound u) of simultaneousdata frame transmissions. Speciflcally, the total number of data frame transmissions in theTDMA frame cannot be greater than uF and we have PCc=1PKck=1 mc;k • uF.Some other factors such as historical bandwidth allocation and historical FLR may also beconsidered for making a scheduling decision.In this chapter, the scheduling function is deflned as a mapping which determines thescheduling decision vector M by the maximum number (upper bound u)of simultaneous dataframes transmissions, the bufier state vector N and the tra–c state vector V. Such a functionis deflned as:› : fu;N;Dg! M (u ‚ 1;N 2 currency1;D 2 ¥;M 2 “) (4.6)Here currency1, ¥ and “ are the spaces of the bufier state vector N, the tra–c state vector D andthe scheduling decision vector M respectively and deflned as: currency1 = fNjnc;k 2 f0:::Kcgg, ¥ =fDjdc;k 2f1:::Scgg, “ = fMjmc;k 2f0:::Kcgg. Note that the above deflnition of schedulingfunction is valid even if some static parameters such as priorities and QoS requirements forChapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 122difierent tra–c  ows are taken into account. Essentially, if any static parameters are appliedin the scheduling, the scheduling deflnition can be presented as:› : fu;N;D;Paramsg! M (u ‚ 1;N 2 currency1;D 2 ¥;M 2 “) (4.7)Here Params represents all static parameters applied. Since all these parameters are staticand do not vary among difierent TDMA frames, the scheduling decision will be determined forany TDMA frame given the bufier states and the tra–c states of all tra–c  ows in the TDMAframe. As a result, Params can be neglected from (4.7) and the deflnition of (4.6) is still valid.For example, if a speciflc tra–c  ow i of class j has a higher priority than all other tra–c ows, it needs to occupy any available slot as long as it still has data frames to transmit. Inthis situation, the scheduling decision is partially determined by whether nj;i > 0. In anotherwords, it is still based on the tra–c states and the bufier states of all tra–c  ows.4.3.3 Slot AllocationGiven u the maximum number of the simultaneous data frame transmissions allowed in one timeslot and M the scheduling decision vector, the system also need to inform the mobile stationsin which time slot their scheduled data frames should be transmitted. If every time slot holdsexactly u transmissions of data frames, the BER of all data frames can be easily determined.However, if there are not so many data frames transmitted in one TDMA frame, the BER ofa data frame is afiected by the number of data frames transmitted in the same time slot. Inother words, it depends on the slot allocation scheme. Here we consider a simple slot allocationscheme, which assigns data frames to every time slot evenly. In this case, any time slot mayhave bzFc or bzFc+1 data frames with probability 1¡ z mod FF and z mod FF , respectively, if thereChapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 123are totally z (0 • z • uF) data frames scheduled in the TDMA frame, i.e., z = Pc;k mc;k.So Efer(z;u), the expected FER of data frames in the TDMA frame can be easily calculated.Note that, other slot allocation methods can also be applied in practice and a similar functionEfer can also be found. In this chapter, we assume that a slot allocation method is providedand Efer(z;u), can be determined. This function is important for evaluating and optimizingthe system performance.4.4 Tra–c Adaptive OptimizationIn this chapter, we focus on the cross-layer optimization of u, the upper bound of the numberof simultaneous data frame transmissions in each time slot of a TDMA frame. The objectiveis to minimize the FLR (i.e., taking into consideration both FER and FDR) of the system sothat the channel throughput is maximized (Note that the throughput is the aggregate packetarrival rate factored by (1-FLR)). To make such an optimization, the system needs to knowthe scheduling function and slot allocation when every speciflc u is given for a TDMA frame.As discussed in Section 4.3.3, any slot allocation scheme can be used as long as the functionEfer(z;u), can be acquired. The optimization of u concerns not the actual slot allocation butthe function Efer(z;u). On the other hand, any scheduling function deflned as (4.6) can be usedfor the optimization. We will also show a speciflc example in Section 4.4.1 which minimizes theFLR of every TDMA frame.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 1244.4.1 Queue AnalysisBefore presenting the optimization of u, we flrst need to analyze the number of data frame lossesof a TDMA frame if the upper bound u of the number of simultaneous data frame transmissionis decided, the bufier state vector N and the tra–c state vector D is known, and the slotallocation and the scheduling decision vector M is given.To facilitate the analysis, we deflne the bufier state vector at the beginning of the TDMAframe t as N(t) and the corresponding number of data frames in the bufier of class c tra–c  owk as nc;k(t). Similarly, we deflne D(t) and M(t) as the tra–c state vector and the schedulingdecision vector for TDMA frame t, and dc;k(t) and mc;k(t) as the corresponding tra–c stateand the number of scheduled data frames of class c tra–c  ow k. The maximum number ofsimultaneous data frame transmissions (the upper bound) for the TDMA frame is deflned asu(t). Also, we assume that a speciflc slot allocation method is always used and Efer(z;u) isthe expected frame error probability for each data frame transmitted in a TDMA frame withtotally z data frames in the TDMA frame and with u applied as the maximum simultaneousdata frame transmissions in one slot.We denote the number of arriving data frames for tra–c  ow k of class c in TDMA framet as Ac;k(t). Here to simplify the presentation, we assume that one packet is always convertedto exactly one date frame after the fragmentation and encapsulation. Note that the followingmodel can also be extended to handle other situations (i.e., the assumption is not mandatory).Since the tra–c state of class c tra–c  ow k is dc;k(t), the packets should arrive according toa Poisson process with rate Rc;dc;k(t)(t) according to the MMPP model introduced in Section4.2.2. It is not di–cult to compute the probability that there are i data frames arriving inChapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 125TDMA frame t for class c tra–c  ow k as:PfAc;k(t) = ig = (Rc;dc;k(t))i £e¡Rc;dc;k(t)i! (4.8)So we can get the conditional probability of the bufier state vector at the beginning of theTDMA frame (t+1) asPfN(t+1)jN(t);D(t);M(t)g =CYc=1KcYk=1Pfnc;k(t+1)jnc;k(t);dc;k(t);mc;k(t)g (4.9)wherePfnc;k(t+1)jnc;k(t);dc;k(t);mc;k(t)g=8>><>>:PfAc;k(t) = nc;k(t+1)¡(nc;k(t)¡mc;k(t))+g if nc;k(t+1) < VcP1i=Vc¡(nc;k(t)¡mc;k(t))+ PfAc;k(t) = ig if nc;k(t+1) = Vc(4.10)Here the value of (x)+ is x or 0 if x is less than 0. Normally, mc;k(t) should be less than nc;k(t)for a good scheduling decision, which means that (nc;k(t) ¡ mc;k(t))+ should always equal tonc;k(t)¡mc;k(t).Note that data frames may be dropped if the queue bufier is full when they arrive. Ifnc;k(t+1) < Vc, no data frames will be dropped and the number of arrived data frames in theTDMA frame t is nc;k(t + 1)¡(nc;k(t)¡mc;k(t))+. So the probability of this case is exactlythe probability that there is such data frames arriving. And if nc;k(t + 1) = Vc, it indicatesthat arrived data frames may be dropped and the number of arrived data frames in the TDMAframe can be any number greater than Vc ¡(nc;k(t)¡mc;k(t))+. The probability of this case isthat there are over Vc ¡(nc;k(t)¡mc;k(t))+ data frames arrived in the TDMA frame.With the above analysis, we can get the expected number of data frames dropped for classChapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 126c tra–c  ow k for TDMA frame t as follows:DRc;k(N(t);D(t);M(t)) =1Xi=0(i+(nc;k(t)¡mc;k(t))+ ¡Vc)+PfAc;k(t) = ig (4.11)Here P(Ac;k(t) = i) is the probability that there are i data frames arrived to the bufier for classc tra–c  ow k in TDMA frame t. And (i+(nc;k(t)¡mc;k(t))+¡Vc)+ data frames are droppedbecause of bufier over ow.On the other hand, if we know how these data frames are allocated into the time slots, wecan also calculate the expected data frame errors for each tra–c  ow. The expected data frameerrors for tra–c  ow k of class c in TDMA frame t is:ERc;k(M(t);u(t)) = mc;k(t)Efer(Xi;jmi;j(t);u(t)) (4.12)So the expected number of data frame losses for class c tra–c  ow k in TDMA frame t isLOc;k(N(t);D(t);M(t);u(t)) = ERc;k(M(t);u(t))+DRc;k(N(t);D(t);M(t)): (4.13)And the expected number of total data frame losses isXcXkLOc;k(N(t);D(t);M(t);u(t)):Note that this number also depends on the function Efer(z;u), which is a static parameter (i.e.,it does not change over time).As we discussed before, to perform the optimization of u, we need to determine the schedul-ing function based on u and the slot allocation method. Here we consider the following schedul-ing function which minimizes the total data frame losses in a TDMA frame:M(t) = arg minM(t)⁄XcXkLOc;k(N(t);D(t);M(t)⁄;u(t)): (4.14)Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 127Note that, this scheduling function is of the same form as (4.6). Other scheduling functionscan also be applied as long as they are of the form (4.6). For example, we can also considerthe priority control or QoS requirement for some tra–c  ows when determining the schedulingfunction.4.4.2 The OptimizationBased on the above analysis, in this section, we present a cross-layer-based optimization mech-anism to determine the maximum number (or the upper bound of the number) of data framestransmitted in one time slot of a TDMA frame to minimize the total FLR of all tra–c  ows.This optimization method is based on such a principle. The more data frame transmissions areallowed in every time slot in a TDMA frame, the higher chance the data frames are transmittedwith errors and the less chances the data frames expire. Especially, a larger upper bound ofthe number of simultaneous transmissions in one time slot for a TDMA frame may decreasethe large FDR experienced when the tra–c  ows are in a \burst" (i.e., there happen to be alot of data frames arrived in a short period). Since the FLR accounts both frame errors andthe frame drops, the minimal FLR can be acquired by choosing an appropriate upper bound ofthe number of data frame transmissions allowed in every time slot.As stated in previous sections, to perform the optimization, there must be a schedulingfunction as (4.6) and Efer(z;u) must be given. Then, the decision of u in every TDMA frameis a function of the bufier state vector N and the tra–c state vector D. Here, as presented inSection 4.3, we assume that the vectors N(t) and D(t) are known by the system at the beginningof TDMA frame t via the signaling channels. We perform the cross-layer optimization using aMDP [27] as explained below.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 128State spaceWe deflne the system state of the MDP at the beginning of the TDMA frame t, G(t), asG(t) = [N(t);D(t)]. So the state space here of the system state is:' = fG(t) = [N(t);D(t)] : N(t) 2 currency1;D(t) 2 ¥g (4.15)ActionsAt the beginning of TDMA frame t, the maximum number of data frame transmissions allowedin one time slot, u(t), is determined. Then, the speciflc scheduling function and slot allocationmethod are applied to determine the packet transmissions in the TDMA frame. This numberu(t) is the action to be determined by the MDP. Its state space is ¢ = fu(t) : u(t) ‚ 1g.State transitionIt is easy to get the state transition probability P(G(t+1) j G(t);u(t)) since the state transitionof D(t) depends only on the MMPP tra–c model for each tra–c  ow and the transition of N(t)depends only on D(t) and the scheduling decision M(t) which is determined by N(t), D(t) andu(t) given a scheduling function deflned as in (4.6). We have:PfG(t+1) j G(t);u(t)g = PfD(t+1) j D(t)g£PfN(t+1) j N(t);D(t);u(t)g (4.16)Here according to (4.1) we have PfD(t+ 1) j D(t)g = QCc=1QKck=1  c;(dc;k(t);dc;k(t+1)). Since thescheduling function is provided, the scheduling decision M(t) is determined given N(t), D(t)and u(t). We can havePfN(t+1) j N(t);D(t);u(t)g =PfN(t+1) j N(t);D(t);M(t);u(t)g=PfN(t+1) j N(t);D(t);M(t)g (4.17)Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 129Note that PfN(t + 1) j N(t);D(t);M(t)g is already calculated according to (4.9) and (4.10).It is not di–cult to see that the constructed markov decision process is a unichain model.CostDepending on the optimization objective, the cost can be deflned in difierent ways. In thischapter, it is deflned as the total data frame losses over time. Given the system state G(t) andthe action u(t), it is not di–cult to get the cost for a TDMA frame as:CT(t) =XcXkLOc;k(N(t);D(t);M(t);u(t)) (4.18)Then the average cost over time is then:limT!11TTXt=0XcXkLOc;k(N(t);D(t);M(t);u(t)): (4.19)The linear programming solutionThe above sections actually deflned difierent components of an MDP. To acquire the minimumaverage cost over time, i.e., to minimize the number of data frame losses over time, we need tochoose an appropriate decision u(t) for each system state G(t). The decision can be stochastic.In other words, for a speciflc system state G(t), the optimal decision may be to choose u(t) = 1with probability p1, u(t) = 2 with probability p2 and so on. Then, to solve the MDP, we getthe following mapping:G(t) !fp1;p2;:::g (4.20)Note that, a deterministic decision (to choose an explicit u(t) for a speciflc G(t)) is a specialcase of the stochastic decision.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 130The MDP described above can be transformed to a linear programming problem as follows:minx(:)XG2'Xu>0x(G;u)c(G;u)s:t:Xu>0x(G;u)¡XG⁄2'Xu>0PfG j G⁄;ugx(G⁄;u) = 0XG2'Xu>0x(G;u) = 1 (4.21)Here c(G;u) is the cost (expected number of data frame losses) for one TDMA frame when thesystemstatefortheTDMAframeisGandthedecisionisu, i.e., c(G;u) = Pc;k LOc;k(N;D;M;u)where G = (N;D) and M = ›(N;D;u).Also, PfG j G⁄;ug is the state transition function deflned in Section 4.4.2, and x(G;u) isthe probability of the case that the system state is G and the maximum number of simultaneoustransmissions is decided as u. Then we can get the decision on u(t) for TDMA frame t as:pfu(t) = i j G(t)g = x(G(t);i)P1j=0 x(G(t);j)(4.22)4.4.3 QoS AnalysisThe above optimization minimizes the number of data frame losses over time by choosing anappropriate value of u for a TDMA frame. By doing so, the FLR of the system can be minimizedsince the expected number of data frames arrived to the system over time is a constant. Notethat it is determined by the tra–c models of the tra–c  ows. Based on the above, we canperform further analysis of the system QoS as follows.From the above optimization, we can get the stationary distribution of the system state Gas:B(g) = PfG = gg =1Xj=0x(g;j) (4.23)Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 131Assume that the bufier state vector and the tra–c state vector corresponding to g is n and d,and the corresponding scheduling decision vector given n, d, u is m according to the schedulingfunction. Then we can determine the expected number of data frame losses of class c tra–c k inone TDMA frame to bePg B(g)LOc;k(n;d;m;u). So, it is not di–cult to get the correspondingFLR –c;k and the average TDMA frame throughput  c;k for class c tra–c  ow k as follows:–c;k =Pg B(g)LOc;k(n;d;m;u)RcTf (4.24) c;k = RcTf ¡XgB(g)LOc;k(n;d;m;u) (4.25)Here Rc is the average data frame arrival rate of class c tra–c  ows. And RcTf is the expectednumber of newly arrived data frames to the bufier queue in one TDMA frame.If a data frame arrives to the bufier in a TDMA frame, there is an expected delay of half of aTDMA frame from the arrival to the beginning of the next TDMA frame. If it is sent out in thenext TDMA frame, there is expectedly another half TDMA frame delay if the aforementionedeven allocation method is used. Actually, every data frames transmitted has these two partsof delays totally one TDMA frame as long as it is not dropped for bufier over ow (no matterwhich TDMA it is sent out). Additionally, if such a data frame is not transmitted in a TDMAframe, it will experience one extra TDMA frame delay. So the expected delay for a data frameof class c tra–c  ow k (if the data frame is not dropped for bufier over ow) can be calculatedas follows.·c;k = Tf + limT!1PTt=0 (nc;k(t)¡mc;k(t))£Tf»c;kRcTTf= »c;kRcTf»c;kRc+Pg B(g)nc;k»c;kRc ¡Pg B(g)mc;k»c;kRc=Pg B(g)nc;k»c;kRc (4.26)Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 132Here nc;k and mc;k are the components of n and m respectively. »c;k equals to 1 ¡ –c;k. Itrepresents the percentage of the data frames of class c tra–c  ow k which are not dropped forbufier over ow. In the flrst line, Tf is the flrst two parts delay discussed above for a data frameand the limitation shows the expected extra delay for one data frame of class c tra–c  ow k.Note that, during a period t = 0 ! T, the number of class c tra–c k data frames arrived inthe bufier is »c;kRcTTf. For a TDMA frame t, nc;k(t)¡mc;k(t) bufiered data frames are nottransmitted in the TDMA frame and experience one extra TDMA frame delay. So the flrstline gives the average delay for data frames not dropped of class c tra–c  ow k. In the laststep, »c;kRcTf is the average data frames arrived in one TDMA frame and Pg B(g)mc;k is theexpected data frames transmitted in one TDMA frame. They must be the same.4.4.4 Limitation and ApproximationThe above optimization provides a set of decisions on u for difierent system states G. Thedecision can be pre-calculated and stored in the system so that the system can apply it at thebeginning of every TDMA frame. However, the linear programming solution of the optimizationmay become computationally infeasible if the state space of the system is very large (e.g., thereare too many tra–c  ows in the system and the bufier size of each tra–c  ow is very large).Some simpliflcation and approximation techniques can be utilized to alleviate the problem. Forexample, for computation purposes, we can assume that all the tra–c  ows share a single bufier.It will produce better performance since less data frames will be dropped due to shared bufierresources. Also, we provide another scheme which apply the same principle as the optimizationabove, as u should increase a little bit during \burst" period. We call it the rate adaptiveoptimization here.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 133As discussed in Section 4.2.2, the duration between updates of the tra–c state for a MMPPtra–c  ow is normally much longer than a TDMA frame. So we assume that the tra–cstates of all tra–c  ows should remain unchanged for a certain period of time. Within thatperiod, the system tries to flnd the best u. based on the tra–c state vector D. Note thatif the tra–c state vector and the value u are known, the scheduling decision vector M(t)for TDMA frame t depends on the bufier state vector N(t) only. So the transition of thebufier state N(t) which should depend on M(t), D(t) and u becomes deterministic. We havePfN(t+1) j N(t)g = PfN(t+1) j N(t);D;Mg which can be calculated according to (4.9) and(4.10). The bufier state vectors N(t) at the beginning of TDMA frame t can form a Markovchain. By solving the Markov chain, we can easily obtain the stationary distribution of N(t)as …(n) = PfN(t) = ng. The best u for the period with the tra–c state vector D can then befound as follows:u⁄ = argminuXnˆ…(n)XcXkLOc;k(n;D;M;u)!: (4.27)When the tra–c state vector changes, the optimal u⁄ should be updated accordingly. Theaforementioned method can be used to reduce computation cost signiflcantly. Compared to thetra–c adaptive scheme, the rate adaptive scheme does not need to formulate the MDP. Althoughthe computation complexity cannot be compared directly, the dimension of the variables isreduced dramatically (from the product of dimensions of the decision state space, tra–c statespace and bufier state space to a single decision variable).Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 1344.5 Results and DiscussionsWe implemented a simulation model to validate the analysis and to study the performanceenhancements of the proposed optimization methods. We also compared our work with thetransmission scheme proposed in [1{4, 28], where packets are scheduled according to theirBER requirements. Furthermore, we compared the two adaptive scheme with the transmissionscheme used in CEPS [20, 21]. We have studied a multicode CDMA system (as described inSection 4.2) with a spreading gain of 7 and a noise level of  2 = 10db. Each TDMA frame is0.02 second long and is divided into two time slots. Each data frame is 511 bits long. It carriesa 160 bits payload and a 69 bits header. The channel code is a (511,229,38) BCH code, whichcan tolerate 38 bit errors. We assume that a packet always has the same length and can beexactly transmitted by one data frame, so that no fragmentation is needed. We also assumethat a bufier queue of size 30 is shared by all tra–c  ows. Note that we use a very small systemhere for studying the performance of the proposed scheme. A bigger system may lead to largercomputation complexity but the proposed scheme should have a similar performance. In thesimulations, the physical layer is applied statistically and the data link layer is operated stepby step. The results are generated from the average of a couple of same simulations, which runsat least 100,000 TDMA frames.We flrst study the basic idea of dynamically adjusting the maximum number of simultaneousdata frame transmissions in a time slot. In this study, we simply assume that packets arrive toa mobile station according to a Poisson process. The BER threshold is equivalent to 1% FER,which leads to an upper bound u = 6 of the number of simultaneous data frame transmissionsin one time slot for the traditional threshold-based scheme. Figure 4.1 shows the simulationChapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 135and analytical results of FLR when the packet arrival rate varies. Furthermore, we try difierentu for the same system and compare their performances. It is clear that the curves for difierentu have difierent shapes because the systems with difierent u have difierent capacities in oneTDMA frame. When the packet arrival rate increases, all these curves are supposed to achievethe limit 1. As we can observe, u = 6 used by the traditional scheme (which conforms to (4.2))achieves the best performance only when the packet arrival rate is between 420 packets/secondand 560 packets/second. When the packet arrival rate is lower than 420 packet/second, u = 5achieves a better performance. When the packet arrival rate is greater than 560 packets/second,u = 7 gives a much better performance than others. Note that, when the packet arrival rateis greater than 560 packets/second, the system is a little bit overloaded because the FLR ofall cases of u are higher than the desired 1% FER. These results support the motivation forthe optimization methods proposed in this chapter. In other words, the maximum number ofsimultaneous data frame transmissions should be changed adaptively based on the tra–c  owstatus.Figure4.2showsthecorrespondingnormalized throughput. Herethenormalized throughputis the percentage of successfully transmitted packets from all packets arrived. It is obvious thatu = 6 gives the best result when the packets arrival rate is lower than 560 packets/secondbut its performance degrade greatly when the packet arrival rate is higher. And u = 7 givesthe best performance among all four cases when the packet arrival rate is higher than 560packets/second. And also, when the packet arrival rate is lower than 420 packets/second, theFLR for every difierent u is far below 1 so that the normalized throughput is very close to 1.Figure 4.3 shows the corresponding packet access delay. It is interesting to see that whileu = 6 shows the best performance in terms of FLR when the packet arrival rate is between 420Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 136packets/second and 560 packets/second arrival rate, the corresponding delay is not the best.Note that, actually this makes sense since the higher service rate, the less delay is experienced.It also reminds us that the performance in terms of FDR should also follow the commonsensethat the higher service rate, the less drops happen. The reason of the lower FLR of u = 6compared with u = 7 and u = 8 during this range of packet arrival rate is that the FLR isdominated by the FER and the FDR is much smaller than FER here. So the efiect on FDR isoverridden by the dominating FER performance.All the above three flgures show that the simulation results match closely with the analyticalresults based on the analytical model in Section 4.4.3. It verifles the correctness of the analyticalmodel as well as validates the simulation programs.Next, we study the proposed optimization methods (i.e., the tra–c adaptive scheme and theapproximated version, the rate adaptive scheme which updates u according to the system tra–cstate vector described in Section 4.4.4) for a system with difierent conflgurations. We comparethem with the scheme proposed in [1{4, 28] (specifled as \BERG" in the flgures. BERG standsfor BER guaranteed), which stops scheduling packets in a slot if the BER will exceed the pre-designed target. We assume that the pre-designed target BER here is equivalent to a 1% FER,and the transmission scheme used in CEPS [20, 21] (specifled as \CEPS" in the flgures). Notethat in CEPS, the data frames are all associated with an expiration time and the data framedrops happens and only happens when data frames expire. So we modify the analytical modelof our scheme a little bit (the bufier transition and the FLR calculation) to realize the samebufiering mechanism.We flrst investigate the performance of the three schemes in the system described above.The aggregative packet arrival rate varies also from 250 packets/second to 750 packets/second.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 137We assume the expiration time of arrived packets is two TDMA frames, which means a dataframe will be dropped if it is not transmitted in the next two TDMA frames upon its arrival.Figure 4.4 shows the performance in terms of the FLR. It can be seen clearly that boththe rate adaptive and tra–c adaptive schemes can provide a better performance than theBERG scheme. When the tra–c load is light, CEPS scheme provides a better performancethan the rate adaptive scheme because it concerns the bufier status while the rate adaptivescheme concerns the tra–c  ow rate. Note that, the tra–c status does not change during eachsimulation in this flgure. So the bufier status is more important than the tra–c status for theoptimization. And the tra–c adaptive can achieve the best performance since it counts both thetra–c status and the bufier status. When the tra–c load is heavy, all these schemes providessimilar performance. It is because when the packet arrival rate is very high, the decisions madeby the tra–c adaptive scheme and CEPS are almost flxed at u = 7 for each frame, which is thesame value used in the rate adaptive scheme. Another interesting observation is that the FLRof the rate adaptive scheme does not vary smoothly with the packet arrival rate. Actually, sincethe packet arrival rate is flxed in each independent simulation, the rate adaptive scheme onlyapplies the best flxed u for each simulation. For the packet arrival rate from 250 packets/secondto 425 packets/second, the best u for the rate adaptive scheme is 5. For the packet arrival ratefrom 450 packets/second to 575 packets/second, the best u for the rate adaptive scheme is 6.When the packet arrival rate is higher than 575, the best u for the rate adaptive scheme is 7.So, as a result, the curve for the rate adaptive scheme has two sharp turns at the packet arrivalrate of 425 packets/second and 575 packets/second. The results also show that the two schemescan outperform the traditional scheme. Figure 4.5 shows the corresponding system throughput.It is easy to see that the two adaptive schemes and the CEPS scheme have similar performance,Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 138which is much better than that of the BERG scheme when the packet arrival rate is higherthan 600 packets/second. When the packet arrival rate is lower than 600 packets/second, allschemes have the similar performance because all of them have very little FLR. Although thedifierences in FLR are quite apparent, the difierences in throughput are very little (all of themcan achieve a throughput very close to the packet arrival rate).Next, we study the performance of the above schemes with variable number of multimediatra–c  ows. We consider a typical VOIP tra–c source, which can be represented by a two-stateMMPP. At the \talk" state, its packet arrival rate is 25 packets/second. At the \silence" state,its packet arrival rate is 0. The average durations of the \talk" and \silence" states are 1 and1.35 seconds respectively.Figure 4.6 shows the FLR of the four schemes when the number of tra–c  ows in the systemvaries from 32 to 64. It can be seen that the rate adaptive and tra–c adaptive schemes performmuch better than the traditional scheme. Speciflcally, if the target FLR is 1%, the traditionalscheme can support about 45 tra–c  ows while the rate adaptive and tra–c adaptive schemecan support about 50 and 55 tra–c  ows respectively (CEPS can support 49 tra–c  ows).Note that, when the number of tra–c  ows increases in the system, the performance of thetwo adaptive schemes becomes much closer. Also, CEPS scheme could provide a better FLRwhen the tra–c load is light, because the packets arrival rate is relatively low so that it ismore important to adapt to the bufier status than to the tra–c status. However, when thetra–c load is high, the tra–c adaptive and rate adaptive schemes perform better for it is moreimportant to concerns the packets coming the next TDMA frame. Actually, for target FLR1%, the tra–c adaptive scheme can obtain a 10% capacity improvement compared to CEPS.Figures 4.7 shows the corresponding simulation results on throughput.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 1394.6 SummaryIn this chapter, we have proposed a tra–c adaptive optimization scheme for multi-code CDMAoperating over a TDMA framework. Using a Markov decision process model, it seeks to deter-mine the maximum number of simultaneous data frame transmissions that can be supported ina time slot of a TDMA frame. To facilitate implementation, we also propose an approximationscheme called the rate adaptive scheme. Both schemes aim to jointly optimize the physicallayer’s BER and the MAC layer’s FDR to minimize the overall FLR. Simulation results showthat these two schemes can improve the FLR and hence the system capacity substantially ascompared to the traditional scheme and a previous work CEPS. While the tra–c adaptive op-timization scheme can give a better performance in general, the computation cost is higher. Inmost cases, the rate adaptive scheme can give a performance close to that of the tra–c adaptiveoptimization scheme, especially when the system tra–c load is heavy.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 140250 300 350 400 450 500 550 600 650 700 75010−710−610−510−410−310−210−1100Packet arrival rate (packets/second)FLR  u=5, modelu=6, modelu=7, modelu=8, modelu=5, simulationu=6, simulationu=7, simulationu=8, simulationFigure 4.1: Data frame loss ratios vs. data frame generation rates for difierent flxed u0.250 300 350 400 450 500 550 600 650 700 7500.650.70.750.80.850.90.9511.05Packet arrival rate (packets/second)Throughput  u=5, modelu=6, modelu=7, modelu=8, modelu=5, simulationu=6, simulationu=7, simulationu=8, simulationFigure 4.2: Throughput vs. data frame generation rates for difierent flxed u0.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 141250 300 350 400 450 500 550 600 650 700 7500.0150.020.0250.030.0350.040.0450.050.0550.06Packet arrival rate (packets/second)Average packet delay (seconds)  u=5, modelu=6, modelu=7, modelu=8, modelu=5, simulationu=6, simulationu=7, simulationu=8, simulationFigure 4.3: Packet access delay vs. data frame generation rates for difierent flxed u0.250 300 350 400 450 500 550 600 650 700 75010−1010−810−610−410−2100Packet arrival rate (packets/second)FLR  BERG, modelrate adaptive, modeltraffic adaptive, modelBERG, simulationCEPS, simulationrate adaptive, simulationtraffic adaptive, simulationFigure 4.4: Data frame loss ratios vs. data frame generation rates for difierent schemes on u0.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 142250 300 350 400 450 500 550 600 650 700 750200250300350400450500550600650700Packet arrival rate (packets/second)Throughput (packets/second)  BERG, modelrate adaptive, modeltraffic adaptive, modelBERG, simulationCEPS, simulationrate adaptive, simulationtraffic adaptive, simulationFigure 4.5: Throughput vs. data frame generation rates for difierent schemes on u0.30 35 40 45 50 55 60 6510−510−410−310−210−1100Number of voice traffic flowsFLR  BERG, modelrate adaptive, modeltraffic adaptive, modelBERG, simulationCEPS, simulationrate adaptive, simulationtraffic adaptive, simulationFigure 4.6: Data frame loss ratios vs. number of tra–c  ows for difierent schemes on u0.Chapter 4. Cross-Layer Optimization for Multimedia Transport over MC-CDMA Networks 14330 35 40 45 50 55 60 65300350400450500550600650Number of voice traffic flowsThroughput (packets/second)  BERG, modelrate adaptive, modeltraffic adaptive, modelBERG, simulationCEPS, simulationrate adaptive, simulationtraffic adaptive, simulationFigure 4.7: Throughput vs. number of tra–c  ows for difierent schemes on u0.Bibliography 144Bibliography[1] P. Y. Kong, K. C. Chua, and B. Bensaou, \A novel scheduling scheme to share droppingratiowhileguaranteeingadelayboundin amulticode-CDMA network," IEEE/ACM, Trans.Networking, vol. 11, no. 6, pp. 994-1006, Dec. 2003.[2] C.S.ChangandK.C.Chen, \Mediumaccessprotocoldesignfordelay-guaranteedmulticodeCDMA mutimedia networks," IEEE Trans. Wireless Commun., vol. 2, no. 6, pp. 1159-1167,Nov. 2003.[3] P. Y. Kong, K. C. Chua and B. Bensaou, \Multicode-DRR: A packet-scheduling algorithmfor delay guarantee in a multicode-CDMA network," IEEE Trans. Wireless Commun., vol.4, no. 6, pp. 2694-2704, Nov. 2005.[4] V. Huang and W. Zhuang, \QoS-orientied packet scheduling for wireless multimedia CDMAcommunications," IEEE Trans. Mobile Comput., vol. 3, pp. 73-85, Jan.-Mar. 2004.[5] J. Zhou and M. Gurcan, \An improved multicode CDMA transmission method for Ad Hocnetworks," Proc. of IEEE WCNC 2009, pp. 1-6, April 2009.[6] L. Luo, J. Zhang and Z. Shi, \Novel block-interleaved multi-code CDMA system for UWBcommunications," Proc. of IEEE ICUWB 2007, pp. 648-652, Sept. 2007.[7] Y. Ma, J. Jin and D. Zhang, \Throughput and channel access statistics of generalizedselection multiuser scheduling," IEEE Trans. Wireless Commun., vol. 7, no. 8, pp. 2975-2987, August 2008.Bibliography 145[8] C. D. Iskander, \Performance of multicode DS/CDMA with noncoherent M-ary orthogonalmodulation in the presence of timing errors," IEEE Trans. Vehicular Techno., vol. 57, no.6, pp. 3867-3874, Nov. 2008.[9] 3GPP, \Spreading and modulation (FDD)," 3GPP TS25.213, v3.4.0, Dec. 2000.[10] A. Farrokh and V. Krishnamurthy, \Opportunistic scheduling for streaming multimediausers in high-speed downlink packet access (HSDPA)," IEEE Trans. Multimedia, vol. 8, no.4, pp. 844-855, August 2006.[11] S. S. Kulkarni and C. Rosenberg, \Opportunistic scheduling for wireless systems withmultiple interfaces and multiple constraints," Proc. of the 6th ACM/SIGCOM MSWiM, pp.11-19, Sep. 2003.[12] S. S. Kulkarni and C. Rosenberg, \Opportunistic scheduling policies for wireless systemswith short term fairness constraints," Proc. of IEEE GLOBECOM 2003, pp. 533-537, Dec.2003.[13] Q. Liu, S. Zhou and G. B. Giannakis, \Cross-layer scheduling with prescribed QoS guar-antee in adaptive wireless networks," IEEE J. Selected Areas Commun., vol. 23, no. 5, pp.1056-1066, May 2005.[14] L.Alonso, andR.Aqusti, \Automaticrateadaptationandenergy-savingmechanismsbasedon cross-layer information for packet-switched data networks," IEEE Commun. Magaz., vol.42, no. 3, pp. S15-S20, Mar. 2004.Bibliography 146[15] Y. Li and G. Zhu, \M-gated scheduling and cross-layer design for heterogeneous servicesover wireless networks," IEEE Trans. Vehicular Technol., vol. 58, no. 4, pp. 1983-1997, May2009.[16] V. Cirvino, V. Tralli and R. Verdone, \Cross-layer radio resource allocation for multicarrierair interfaces in multicell multiuser environments," IEEE Trans. Vehicular Technol., vol. 58,no. 4, pp. 1864-1875, May 2009.[17] Q. Liu, S. Zhou and G. B. Giannakis, "Queuing with adaptive modulation and coding overwireless links: cross-layer analysis and design," IEEE Trans. Wireless Commun., vol. 4, no.3, pp. 1142-1153, May 2005.[18] Q. Liu, S. Zhou and G. B. Giannakis, "Cross-layer combining of adaptive modulation andcoding with truncated ARQ over wireless links," IEEE Trans. Wireless Commun., vol. 3,no. 5, pp. 1746-1755, May 2005.[19] J. Ramis, L. Carrasco, and G. Femenias, \A two-dimensional markov model for cross-layerdesign in AMC/ARQ-based wireless networks," Proc. of IEEE GLOBECOM 2008, pp. 1-6,Nov. 2008.[20] H. Chen, H. C. B. Chan and V. C. M. Leung, \Cross-layer enhanced real-time packetscheduling over CDMA networks," Proc. of IEEE ICON2006, pp. 1-6, Sept. 2006.[21] H. Chen, H. C. B. Chan, V. C. M. Leung and J. Zhang, \Cross-layer enhanced uplink packetscheduling for multimedia tra–c over MC-CDMA networks," IEEE Trans. Veh. Technol.,vol. 59, no. 2, pp. 986-992, Feb. 2010.[22] M. Schwartz, Broadband Integrated Networks: Prentice Hall, 1996.Bibliography 147[23] J. N. Daigle and J. D. Langford, \Models for analysis of packet-voice communicationsystems," IEEE J. Sel. Areas Commun., vol. 4, no. 6, pp. 847-855, Sep. 1986.[24] P. Skelly, M. Schwartz, and S. Dixit, \A histogram-based model for video tra–c behaviorin an ATM multiplexer," IEEE/ACM Trans. Netw., vol. 1, no. 4, pp. 446-459, Aug. 1993.[25] A. T. Anderson and B. F. Nielsen, \A Markovian approach for modeling packet tra–cwith long-range dependence," IEEE J. Sel. Areas Commun., vol. 16, no. 5, pp. 719-732,Jun. 1998.[26] E. P. C. Kao, An introduction to stochastic processes, Duxbury Press, 1996.[27] M. L. Puterman, Markov decision processes: Discrete stochastic dynamic programming,John Wiley & Sons, New York, 1994.[28] I. F. Akyildiz, D. A. Levine, and I. Joe, \A slotted CDMA protocol with BER schedulingfor wireless multimedia networks," IEEE/ACM Trans. Netw., vol. 7, no. 2, pp. 146-158,April 1999.148Chapter 5A Cross-layer Scheduling Scheme forWireless Multimedia Transmissionswith Adaptive Modulation andCoding 1The previous two chapters applied the cross-layer consideration of the QoS in multimedia trans-missions over wireless links in MC-CDMA systems. Note that, though some other systems donot have the multiple packet reception capability, they can also utilize the cross-layer QoS con-sideration to improve the system performance in terms of QoS provisioning, channel throughputand utilization. In this chapter, we propose a novel scheduling algorithm called QoS-CLS forserving real-time multimedia tra–c  ows in wireless networks employing AMC. Unlike otheralgorithms, QoS-CLS is based on the cross-layer consideration of QoS. The modulation andcoding pair (we also call it the AMC mode in this chapter) is not selected based on the physical1A version of this chapter has been published as a conference paper and awarded the best paper of theconference. H. Chen, H. C.B. Chan and V. C.M. Leung, \A cross-layer scheduling scheme for wireless multimediatransmissions with adaptive modulation and coding," Proc. of IEEE Broadnets, Sep. 2008.Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 149layer FER requirements only. Instead, it is selected using cross-layer information to achieve thebest channel throughput while satisfying the FLR requirement, which is a key QoS parameterfor the user application. As a result, the overall channel throughput or system performancecan be greatly enhanced. QoS-CLS also takes into account the dynamics of the channel state,tra–c state and bufier state of the system in order to implement an optimal decision policy.We present results to show that this cross layer consideration of QoS can greatly improve thechannel throughput. Maintaining fairness is another important issue in a multi-user system.QoS-CLS can incorporate difierent deflnitions of fairness. First, for some multimedia tra–cwhich is not only delay sensitive but also FLR sensitive, QoS-CLS can guarantee the FLR ofsuch tra–c  ows by keeping it below some preset thresholds. Second, for tra–c  ows with-out hard FLR guarantee requirements, QoS-CLS adopts the proportional distribution of FLR,which was also used in previous work [24] (Note that [24] did not consider possible cross-layeroptimization between FER and FDR). By analyzing the dynamics of the system, we formulatethe scheduling problem and AMC mode selection as an MDP with the aim of maximizing thechannel throughput. Then, by transforming the MDP to a linear programming optimizationproblem, we can add the required QoS constraints to guarantee the FLR of some speciflc tra–c ows, and/or to proportionally distribute the FLR among other tra–c  ows according to fair-ness requirements. We also provide two approximation methods to reduce the computationalcomplexity of the optimization. To facilitate implementation, the scheduling policy can bepre-calculated and applied later in real-time.The remainder of the chapter is organized as follows. Section 5.1 introduces the relatedwork. Section 5.2 presents the system models used in this chapter. Section 5.3 studies the basicdynamics of the system. Section 5.4 presents the MDP model and the linear programming modelChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 150for QoS-CLS. Section 5.5 proposes two approximation methods for the algorithm to address thecomputational complexity. Section 5.6 presents the numerical results and discussions. Section5.7 concludes the chapter.5.1 Related WorkAMC is widely used in today’s wireless communication systems. Because of its capability tomaximize system e–ciency over the varying mobile channel, AMC has been adopted in thephysical layer of several important standards, including 3GPP [1, 2], 3GPP2 [3, 4], HIPER-LAN/2 [5], IEEE 802.11 [6, 7], IEEE 802.15.3 [8], and IEEE 802.16 [9]. AMC is often applied incombination with difierent advanced transmission methods such as multi-carrier code divisionmultiple access, multiple-input multiple-output, and cooperative transmissions. When schedul-ing user transmissions in AMC-based systems, the overall system throughput can be improvedby selecting the user with the best channel status to transmit; however, such a strategy mayresult in unfairness and QoS degradation problems, particularly for real-time multimedia tra–c[10]. Hence there is a great need to design a fair and e–cient scheduling algorithm to supportmultimedia communications over AMC-based systems.Note that real-time multimedia tra–c is usually delay sensitive [20]. In this chapter, weassume that each multimedia data frame has a certain delivery deadline, and the frame isdropped from the bufier if it cannot be sent when the specifled deadline expires. For other nondelay sensitive tra–c, although the frames do not have any deadline, they may also be droppeddue to bufier over ow. We deflne the fraction of frames dropped at the data link layer as theFDR, which is a key data link layer QoS measure. In this chapter, we consider a system withChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 151data link retransmission capability. In this case, an error frame will always be returned to thebufier for retransmission, if possible. That means, a frame is only dropped due to deadlineexpiration or bufier over ow. In such a system, the total frame error or drop ratio experiencedby the upper layer, which is deflned as FLR, is efiectively equivalent to FDR. We also deflne theFER as the probability that a data frame is transmitted but received with uncorrectable errors.Note that when the FER of the physical channel becomes worse due to poor channel quality,the FDR may also increase because more retransmissions will efiectively reduce the availablebandwidth for normal transmissions thus increasing the chance of bufier over ow or deadlineexpiration. In this chapter the QoS requirement of a multimedia tra–c stream is specifled bythe maximum FLR and maximum delay (i.e., the deadline). Our objective is to design ane–cient scheduling algorithm that satisfles QoS requirements of tra–c  ows while optimizingthe channel throughput.In recent years, many scheduling algorithms have been proposed for AMC-based systems. Inthe proportional fairness [11] and score-based fairness [12], a weight is calculated for each userbased on present or historical statistics of the channel quality and average throughput. By doingso, these algorithms seek to enhance the overall channel utilization while preventing any userfrom hogging the channel. However, these algorithms cannot provide a good service to real-timemultimedia tra–c because they do not consider the delay requirements of tra–c  ows. In themodifled proportional fairness [13, 14], maximum carrier-to-interference ratio with early delaynotiflcation [15] and channel quality-based minimum throughput assurance [16] algorithms, thedelay requirements or current delays experienced by users are used to prioritize the tra–c  owsfor scheduling purposes. However, they cannot precisely control the delay experienced by eachpacket. Moreover, they operate at the expense of sacriflcing system e–ciency. In [17], theChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 152fundamental scheduling algorithm and the advanced scheduling algorithm (ASA) are proposedfor non-real-time and real-time tra–c, respectively. However, ASA cannot efiectively handle asituation that more than one real-time tra–c  ows have urgent packets to be sent out. In [18],a weighted round-robin scheduling algorithm is proposed to distribute the average delay amongdifierent tra–c  ows by studying the queue dynamics. Both [17] and [18] cannot provide preciseQoS guarantee for real-time tra–c  ows. In [19], the required QoS can be guaranteed, but theproposed scheduling method must be used in conjunction with a very conservative admissioncontrol that ensures the system can satisfy the bandwidth requirement of all real-time tra–c ows even when all these users experience the worst channel status simultaneously. Also, itrequires a large scheduling cycle which can be precisely shared proportionally among the tra–c ows.In addition to deciding which tra–c  ow to serve next, the scheduling algorithm in anAMC-based system also needs to determine the AMC mode to be used for transmission of thetra–c  ow. In most systems, an AMC mode is chosen to keep the physical layer FER below therequired threshold of the tra–c  ow without considering the FDR. However, this approach maynot work efiectively if a large number of frames are queued at the link layer, in which case itmay be better to select an AMC mode with a higher transmission rate to clear the outstandingframes as quickly as possible. Although this selection may cause the FER to increase, theFLR may be greatly reduced to give a better overall system performance. Some other workalso investigated ways to improve system performance by jointly considering FER and FDR.In [21] and [22], the upper and lower SINR bounds for each AMC mode are determined bystudying the maximum retransmission time or the queue and channel dynamics of the system,respectively. However, neither of these schemes makes decision based on the current bufierChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 153state. Also, they do not consider the essential scheduling problem|to decide which tra–c  owto serve. In [23], a scheduling algorithm is proposed for multi-code code division multiple accesssystems. The current bufier status is utilized to determine the number of packets from eachuser to be transmitted in one TDMA frame, so as to minimize the overall FLR. However, thedecision depends only on the current bufier state and does not consider the tra–c models orstatistics.5.2 System DescriptionWe consider downlink scheduling in a wireless network employing AMC. The system consists ofa base station at the centralized cell site broadcasting to a number of mobile terminals in the cell.As in HSDPA and code division multiple access | high data rate (CDMA-HDR), we assumethat there is a downlink data channel that is organized in flxed size transmission time intervals(TTI) with length W0. At the beginning of each TTI, the system determines the tra–c  ow tobe served and the AMC mode to be used during the TTI. We also assume that an error-freefeedback channel exists from each mobile terminal to the base station to convey the channel stateinformation (CSI) and acknowledge successful transmissions. To ensure the efiective operationofthesystem, wealsoconsiderthatthesystemisprovidedwithanappropriateadmissioncontrolalgorithm for admitting tra–c  ows and an efiective tra–c policing mechanism to shape thetra–c  ows. Note that the FLR cannot be guaranteed for any tra–c  ow if the system admitstoo many tra–c  ows with FLR guarantee requirements. Also, without an efiective tra–cpolicing mechanism, the system cannot provide efiective fairness among difierent tra–c  ows asone tra–c  ow may generate too much tra–c to seriously afiect the QoS of other tra–c  ows.Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 154We assume that there are J tra–c  ows in the system. We also deflne the tra–c  ow scheduledfor transmission in TTI t as d(t) 2f1;:::;Jg.We assume that there are K possible modulation and coding pairs (AMC modes) in thesystem. For AMC mode i 2f1;:::;Kg, the transmission rate is Ri and at most fii frames canbe transmitted in one TTI. Without loss of generality, we assume that Ri < Rj 8i < j. So wealso have fii < fij. We deflne the AMC mode selected for TTI t as k(t) 2f1;:::;Kg.For contemporary multimedia communications, the MMPP [25] is widely used to modeldifierent kinds of tra–c, such as video, voice and best efiort data. In this chapter, we assumethat tra–c  ow i has Mi difierent states and data packets arrive according to a Poisson processwith a distinct rate Di;j per TTI at each state j. To simplify the analysis, we assume inthis chapter that the size of each packet can be exactly encapsulated into 1 data frame. Bydiscretizing the model with the TTI, we can get the transition matrix 'i = f`i;j;j0g, where`i;j;j0 is the probability that the tra–c state of tra–c  ow i turns to j0 in the next TTI giventhat the tra–c state is j in the current TTI. Also, from the Di;j and 'i, it is easy to get theaverage data frame arrival rate Di for tra–c  ow i. We denote the tra–c state of tra–c  ow iat TTI t as gi(t) 2fDi;1 :::Di;Mig.We consider two difierent bufiering mechanisms in this chapter. Class one (C1) bufieringmechanism is suitable for real-time tra–c  ows. The delay of each frame must be strictlybounded. A flxed initial expiration counter EPi is associated with each frame of tra–c  ow iupon arriving and it will decrease by 1 after each TTI. Tra–c  ow d(t) is selected to transmitits frames by AMC mode k(t) in TTI t. It will transmit fik(t) frames (or all the frames in thebufier, whichever is less). Among them, those frames received with uncorrectable errors arereturned to the bufier for retransmissions. If a frame’s expiration counter is 1 and it is notChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 155sent out or received correctly in the current TTI, it is dropped from the bufier. The expirationcounters of all frames left in the bufiers are decreased by 1 after the TTI. Also, some new framesmay arrive in the bufiers during the TTI. In practice, the bufier size is flnite. So, we assumethat all tra–c  ows are bufiered separately and for tra–c  ow i, at most EBi frames whichhave the same expiration time can be stored in the bufier. There is no speciflc delay guaranteefor the class two (C2) bufiering mechanism. Instead, there is a bufier of size ENi for tra–c  owi. During TTI t, some frames sent out may be returned to the bufier for retransmission becauseof uncorrectable errors. If the bufier is full, new frames will be dropped directly. This class ofbufiering mechanism is suitable for non real-time tra–c or real-time tra–c without a strict delayrequirement. We assume that there are J1 and J2 (J1 +J2 = J) tra–c  ows employing C1 andC2 bufiering mechanisms, respectively. Generally, the bufier state of tra–c  ow i 2 f1:::J1gat the beginning of TTI t is deflned as bi(t) = [bi;1(t);bi;2(t);:::;bi;EPi(t)], where bi;j(t) is thenumber of frames with expiration counter j in the bufier. And the bufier state of tra–c  owi0 2fJ1 +1:::Jg at the beginning of TTI t is described by ni0(t), the number of frames in thebufier. We assume that the bufier states of all tra–c  ows are known by the system.In this chapter, we assume that the channel of each user is a frequency  at fading channel,which remains unchanged in a TTI. It corresponds to a block fading mode, which is suitable forslowly varying wireless channels [26]. For such channels, the channel quality can be describedby a single parameter of received SINR † for each TTI. So, the general Nakagami-m model,which represents a large class of fading channels, is used to model the channel [27]. The receivedSINR † of a tra–c  ow is a random variable with the density functionp†(†) = mm†m¡1„†m¡(m) exp(¡m†„† ) (5.1)Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 156Here „† = Ef†g is the average received SINR, ¡(m) = R10 tm¡1dt is the Gamma function and mis the Nakagami fading parameter (m ‚ 1=2). Since each AMC mode has difierent capabilityto resist noise and interference, we deflne the function fi mapping the SINR † to the FER forAMC mode i, i.e., if the SINR is †, the FER under mode i is fi(†). Generally, the function fi(†)can be found by experiments. In [21], an approximation of the FER in the presence of additivewhite Gaussian noise (AWGN) is proposed asfi(†) =8>><>>:1; if 0 < † < ¶i;‰i exp(¡´i†); if † ‚ ¶i;(5.2)where ‰i, ´i and ¶i are mode-dependent parameters. Table 5.1 provides these parameters forsome popular AMC modes for 1080 bit data frames. Their accuracy has been verifled in [21].To analyze the channel dynamics and apply it in QoS-CLS, the Finite-State Markov Channel(FSMC) [28] model, which has been widely used in recent research on wireless channels, isemployed in this chapter. Generally, the channel state is modeled in L levels. There are aupper bound †i and a lower bound †i¡1 of SINR for level i. So, for each TTI, the channel stateis one of the L levels and it may transit to an adjacent level or remain in the same level inthe next TTI [28]. Deflning the transition probability that the state changes from i to j aftera TTI as  i;j, we can get the transition matrix £ = f i;jg. Also, we deflne the average FERfor level i in AMC mode j as Fj;i. The determination of £ and Fj;i from the Nakagami-mmodel can be found in [22]. We denote the channel state of tra–c  ow i at TTI t as ci(t).Note that, in this chapter, we assume a frequency  at slow fading channel. However, for afrequency selective fast fading channel, as long as the channel statistics can be obtained and aFSMC model can still be formulated with the statistics, the algorithm proposed in this papershould still work. In this chapter, we assume that perfect CSI is available at the mobile terminalChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 157receiver using a training-based estimation method and is conveyed to the base station throughthe feedback channel. The performance of the proposed scheme is related to the accuracy of theCSI estimation. An imperfect CSI estimation may lead to the degradation of the performanceof the proposed scheme.5.3 Basic System DynamicsBased on the description above, we can get the dynamics of the channel state and the tra–cstate from £ and 'i (i 2f1;:::;Jg) easily. The bufier state dynamics is more complicated. Itdepends on not only the bufiering mechanism but also the current channel state, tra–c state,scheduled tra–c  ow and selected AMC mode.We flrst study the bufier dynamics for the C1 bufiering mechanism, i.e., the transitionprobability from bi(t) to bi(t+1) for tra–c  ow i. We assume that the corresponding channelstate ci(t) and the tra–c state gi(t) is known. The system determine that the tra–c  ow d(t)sends its frames and the AMC mode k(t) is applied in TTI t.If d(t) = i, the number of frames transmitted in the TTI from tra–c  ow i is given asfollows:hi(t) = min'fik(t);EPiXj=1bi;j(t)“We consider that ui;j(t) of bi;j(t) frames with expiration counter j from tra–c  ow i are trans-mitted in TTI t. Therefore, we haveui;j(t)=8>>>>>><>>>>>>:0; if 0 • hi(t) •Pj¡1j0=1 bi;j0(t)hi(t)¡Pj¡1j0=1bi;j0(t); if Pj¡1j0=1 bi;j0(t) < hi(t) •Pjj0=1 bi;j0(t)bi;j(t); if Pjj0=1 bi;j0(t) < hi(t)Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 158Note that the transmitted frames with uncorrectable errors will be returned to the bufier.We consider that zi;j(t) of the ui;j(t) transmitted frames are returned to the bufier. Then wemust havezi;j(t) = bi;j¡1(t+1)¡(bi;j(t)¡ui;j(t)) 8j ‚ 2So given bi;j(t), ci(t), d(t) and k(t), the probability that there are bi;j¡1(t+1) frames withexpiration counter j ¡1 in the bufier of tra–c  ow i in TTI t+1 is the probability that thereare zi;j(t) frames errors from the ui;j(t) frame transmissions. So, we have the probabilitywi(t)=Pfbi;1(t+1);:::;bi;EPi¡1(t+1)jbi(t)g=Pfzi;2(t);:::;zi;EPi(t)jbi(t)g=EPiYj=2BN(ui;j(t);zi;j(t);Fk(t);ci(t)) (5.3)whereBN(i;j;p) =8>><>>:¡ij¢pj(1¡p)i¡j; 0•j•i and 0•p• 10; otherwiseis the binomial probability function.Besides the transmitted frames, some new frames will arrive in the bufier of tra–c  ow iwith an initial expiration counter of EPi. So the probability that there are bi;EPi(t+1) frameswith expiration counter EPi in the bufier of tra–c  ow i isqi(t)=Pfbi;EPi(t+1)jgi(t)g=8>><>>:AR(bi;EPi(t+1);Di;gi(t)); bi;EPi(t+1) 6= EBiP1j=EBi AR(j;Di;gi(t)); bi;EPi(t+1) = EBi(5.4)whereAR(i;j) = ji e¡ji!Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 159is the Poisson probability function.Then, we get the bufier dynamics as follows:pbuf1(bi(t+1);bi(t)) :=Pfbi(t+1)jbi(t)g=wi(t)£qi(t) (5.5)We also analyze the frame losses in TTI t for tra–c  ow i given bi(t), ci(t), gi(t), d(t) and k(t).First, Fk(t);ci(t) £ui;1(t) data frames are expected to be dropped because they are transmittedwith errors and do not have a chance to be retransmitted. Second, bi;1(t)¡hi(t) data frameswill be dropped too after the TTI because of the deadline expiration if bi;1(t) > hi(t). Third, jdata frames may be dropped with probability AR(j + EBi;Di;gi(t)) because of too many newframes arriving during the TTI. Taking into account the three cases, the expected number ofdata frame losses for tra–c  ow i in TTI t is·i(bi(t)) = Fk(t);ci(t) £ui;1(t)+(bi;1(t)¡hi(t))+ +1Xj=1j £AR(j +EBi;Di;gi(t)) (5.6)On the other hand, if d(t) 6= i, we have a similar analysis and hi(t) = 0, ui;j(t) = 0. Wehave:w⁄i(t) =8>><>>:1; zi;j(t) = bi;j¡1(t+1)¡(bi;j(t)¡ui;j(t)) = 0 8j0; otherwise(5.7)and the bufier dynamics pbuf1⁄(bi(t + 1);bi(t)) = w⁄i(t) £qi(t) does not depend on k(t). Theexpected frame drops·⁄i (bi(t)) = (bi;1(t)¡hi(t))+ +1Xj=1j £AR(j +EBi;Di;gi(t)) (5.8)Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 160does not depend on k(t) either.Next we consider the bufier dynamics for C2 bufiering mechanism. We want to work outthe transition probability from ni(t) to ni(t+1) for each tra–c  ow i given ci(t), gi(t) d(t) andk(t).If d(t) = i , the number of transmitted data frames of tra–c  ow i in TTI t isli(t) = minffikd(t)(t);ni(t)gWe assume that j of the li(t) data frames are transmitted with uncorrectable errors and pnew data frames arrive at the bufier in TTI t. It is clear that if ni(t+1) < ENij +p = ni(t+1)¡(ni(t)¡li(t))and if ni(t+1) = ENij +p ‚ ni(t+1)¡(ni(t)¡li(t))Notethattheprobabilityofhavingj dataframeerrorsfromli(t)transmissionsisBN(li(t);j;Fk(t);ci(t)).Furthermore, the probability that p data frames arrive during the TTI is AR(p;Di;gi(t)). So,by considering every possible j and p, we can obtainpbuf2(ni(t+1);ni(t)) := Pfni(t+1)jni(t)g=8>>>>>>>>><>>>>>>>>>:minfli(t);vi(t)gXj=0BN(li(t);j;Fkd(t)(t);ci(t))AR(vi(t)¡j;Di;gi(t)); ni(t)¡li(t) • ni(t+1) < ENili(t)Xj=01Xp=vi(t)¡jBN(li(t);j;Fkd(t)(t);ci(t))AR(p;Di;gi(t)); ni(t+1) = ENi0; otherwise(5.9)Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 161wherevi(t) = ni(t+1)¡(ni(t)¡li(t))Note that in this bufiering mechanism frames are only dropped due to bufier over ow (i.e.,j +p > ENi ¡(ni(t)¡li(t))). So, given ni(t), ci(t), gi(t), d(t) and kd(t)(t), (ni(t)¡li(t)+j +p¡ENi)+ data frames are dropped with probabilityBN(li(t);j;Fkd(t)(t);ci(t))AR(p;Di;gi(t))Considering every possibility of j and p, the expected number of data frame losses for tra–c ow i in TTI t is·i(ni(t)) =li(t)Xj=01Xp=0AR(p;Di;gi(t))BN(li(t);j;Fk(t);ci(t))(ni(t)¡li(t)+j +p¡ENi)+ (5.10)Similar to the analysis of the C1 bufiering, if d(t) 6= i, both the bufier dynamics and theexpected frame drops do not depends on k(t) and we have:pbuf2⁄(ni(t+1);ni(t)) := Pfni(t+1)jni(t)g=8>>>>>>><>>>>>>>:AR(ni(t+1)¡ni(t);Di;gi(t)); ni(t) • ni(t+1) < ENi1Xp=ni(t+1)¡ni(t)AR(p;Di;gi(t)); ni(t+1) = ENi0; otherwise(5.11)and·⁄i (ni(t)) =1Xp=0AR(p;Di;gi(t))(ni(t)+p¡ENi)+ (5.12)Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 1625.4 Markov Decision Process for Scheduling and AMC ModeSelectionWith the analysis above, now we construct an MDP to determine the optimal decision policy forscheduling tra–c  ows and selecting the AMC mode. We will show how QoS-CLS maximizesthe channel throughput while supporting FLR guarantee and fair FLR distribution. Followingthe notations in [29], we describe the MDP as follows:5.4.1 State SpaceA system state is deflned as the row vector of channel states, tra–c states and bufier states ofall tra–c  ows sharing the channel. The system state at the beginning of TTI t iss(t) =[c1(t);:::;cJ(t);g1(t);:::;gJ(t);b1;1(t);:::;b1;EP1(t);b2;1(t);:::;bJ1;EPJ1(t);nJ1+1(t);:::;nJ(t)]:The state space S comprises all possible state vectors, where a state vector has a certain tra–cstate, channel state and bufier state for each of J tra–c  ows. So the state space is deflned asS=fs = [c;g;b;n] :c = [c1;:::;cJ] 2f1;2;:::;LgJg = [g1;:::;gJ] 2 ƒJj=1f1;2;:::;Mjgb = [b1;1;:::;bJ1;EPJ1] 2 ƒJj=1f1;2;:::;EBJ1gEPjn = [nJ1+1;:::;nJ] 2 ƒJj=J1+1f1;2;:::;ENjgg (5.13)Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 1635.4.2 Decision Epochs and ActionsThe decision epochs are the beginning of the TTIs. An action for TTI t is described as a(t) =[d(t);kd(t)(t)], i.e., in TTI t, tra–c  ow d(t) is chosen to transmit with AMC mode kd(t)(t). Theaction space is the set of all possible actions, which can be deflned as:A = fa = [d;k] : d 2f1;:::;Jg;k 2f1;:::;Kgg (5.14)5.4.3 State DynamicsSince the probability of state s(t+1) only depends on state s(t) and action a(t) as discussed inSection 5.3, the dynamics of the system state is a MDP, where the state transition probabilitiesare:ps(t)s(t+1)(d(t);kd(t)(t)) = Pfs(t+1)js(t);d(t);k(t)g=pbuf1(bd(t)(t+1);bd(t)(t))Yj=1:::J1;j6=d(t)pbuf1⁄(bj(t+1);bj(t))pbuf2(nd(t)(t+1);nd(t)(t))Yj=J1+1:::J;j6=d(t)pbuf2⁄(nj(t+1);nj(t))JYj=1 cj(t);cj(t+1)`j;gj(t);gj(t+1) (5.15)It is clear that the embedded chain modelled above is a unichain [29].5.4.4 Policy, Performance Criterion and Cost FunctionThe system must decide the action for any TTI based on the system state at the TTI. Fordeterministic decisions, an action a 2 As is chosen for each given state s 2 S according to adecision policy ˆ 2 “ where “ is deflned as“ = fˆ : S ! Ajˆs 2 As;8s 2 SgChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 164To optimize the QoS of the system, we deflne the cost criterion as follows. For any deter-ministic policy ˆ 2 “ and an initial state s(t0), the average cost is¢ˆ(s(t0)) = limT!11TE‰ TXt=0–(s(t);a(t)) (5.16)where Ef¢g denotes the expected value and –(s(t);a(t)) is the expected cost for a TTI given thatthe state at the beginning of the TTI is s(t) and the action is a(t). The aim here is to choose anoptimum policy to minimizes ¢ˆ(s(t0)) for any initial state s(t0). As stated in above section,the aim of CLS-QoS is to optimize the channel throughput subject to certain QoS constraintsor requirements. Note that, given the tra–c source rates of the tra–c  ows, if less frames arelost, the channel throughput will be higher. So here we choose the following cost function tominimize the total data frame losses:–(s(t);a(t)) =8>>>>><>>>>>:·d(t)(bd(t)(t))+Xj=1:::J1;j6=d(t)·⁄j(bj(t))+Xj=J1+1:::J·⁄j(nj(t)) d(t) • J1·d(t)(nd(t)(t))+Xj=1:::J1·⁄j(bj(t))+Xj=J1+1:::J;j6=d(t)·⁄j(nj(t)) d(t) > J1(5.17)5.4.5 ConstraintsTo achieve speciflc QoS requirements, we need to set up constraints to address the FLR guar-antees and proportional distribution requirements. Without loss of generality, we assume thattra–c  ows fl1;fl2;:::;fl‡ need FLR guarantee yfl1, yfl2, ..., yfl‡, and the remaining tra–c  ows»1;»2;:::;»„ need to have their FLR proportionally distributed with weight $»1, $»2, ..., $»„.Then for a C1 tra–c  ow ¿ 2 fl1 :::fl‡, we haver¿ =limT!11TE'·¿(b¿(t))£pfd(t) = ¿g+·⁄¿(b¿(t))£(1¡pfd(t) = ¿g)“•D¿y¿ (5.18)Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 165Also, for any two tra–c  ows ¿1;¿2 2 »1 :::»„, we haver¿1$¿1D¿1 ¡r¿2$¿2D¿2 = 0 (5.19)5.4.6 Linear Programming Solution to The MDPBased on the above discussion, the optimal policy of the MDP can be obtainted by solving thefollowing linear programming.minxsa‚0Xs2SXa2Asxsa–(s;a)subject toXa2Asxsa ¡Xs02SXa2As0xs0aps0s(a) = 0 8s 2 S; (5.20)Xs2SXa2Asxsa = 1; (5.21)Xs2SXa2Asxsa·¿(s;a) • D¿ £y¿; 8¿ 2 fl1 :::fl‡ (5.22)Ps2S;a2As xsa·¿1(s;a)$¿1D¿1 ¡Ps2Sa2As xsa·¿2(s;a)$¿2D¿2 = 0; 8¿1;¿2 2 »1 :::»„ (5.23)Here if tra–c  ow ¿ uses the C1 bufiering mechanism, we have ·¿(s;a) = ¿(b¿), otherwisewe have ·¿(s;a) = ¿(n¿). Note that xsa is the optimization variable, which is the probabilitythat the system state is s and the action is a. Speciflcally, the action a will be chosen withprobability xsa=Pa02As xsa0 when the system state is s.Note that the above optimization objective makes sure that the number of data frame lossesin the system is minimized subject to the QoS constraints. So the throughput of the system isefiectively optimized. Also, constraint (5.22) ensures that the FLR of speciflc tra–c  ows arekept under their required thresholds. Constraint (5.23) ensures that the other tra–c  ows areserved with FLR proportionally distributed.Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 166Since the system cannot distinguish two system states which have the same bufier andchannel states (i.e., even though they have difierent tra–c states), the actions mapped fromsuch two system states should be the same. We can add a constraint (5.24) addresses thispractical requirement. However, the optimization is not linear anymore in this case.xsa=Xa02Asxsa0 = xs0a=Xa02As0xs0a0; if c = c0;b = b0;n = n0: (5.24)5.5 Implementation IssuesDue to the complexity of the MDP, there are implementation challenges for QoS-CLS. In prac-tice, the scheduling decisions must be made quickly in real-time. In QoS-CLS, the schedulingof every TTI can be based on a simple table lookup. When a tra–c  ow arrives or departs,the system updates the look-up table by a precalculated scheduling policy and also preparesscheduling policies for situations where any tra–c  ow departs or another new tra–c  ow ar-rives, which will be used upon next arrival or departure. We also propose two approximatemethods to reduce the complexity of the optimization.5.5.1 Reduced Bufier State SpaceNote that the state space of the MDP for QoS-CLS may become extremely large if some tra–c ows have big bufiers. So we flrst try to reduce the bufier states space of tra–c  ows with C1bufiering mechanism. For a C2 tra–c  ow i (i 2fJ1 +1;:::;Jg), the size of the bufier is ENi.So in the original optimization, the bufier state ni(t) can be any number between 0 to ENi.When ENi is too big, we divide the ENi + 1 states into a small number wi of groups (vi;1 tovi;wi), and we consider each group vi;z to represent a bufier state. As a result, the bufier stateChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 167n0i(t) can be any of the states vi;z (z 2f1;:::;wig). To apply the optimization based on the newbufier state deflnition, we need to have the bufier state transition probability Pfn0i(t+1)jn0i(t)g.To make the illustration simple, we assume that ENi + 1 can be divided by wi and the bufierlengths (ENi +1)=wi £(z ¡1) to (ENi +1)=wi £z ¡1 belong to group vi;z (z 2 f1;:::;wig)(a similar result can also be achieved if the bufier length is grouped in a difierent way). So thebufier state dynamics can be calculated as:Pfn0i(t+1)jn0i(t)g =Xni(t+1)2n0i(t+1)Pfni(t+1)jn0i(t)g=Xni(t+1)2n0i(t+1)Xni(t)2n0i(t)Pfni(t+1)jni(t)g£Pfni(t)jn0i(t)g: (5.25)Note that, when the bufier size ENi is very large, the probabilities that the bufier has a speciflclength x or x + 1 should be very close to each other. So we assume that the probability thatthe bufier is in a state vi;z is fairly distributed inside the group. We will show some results tovalidate this assumption later. As a result, we have:Pfni(t)jn0i(t)g… wiENi +1: (5.26)And the equation (5.25) becomes:Pfn0i(t+1)jn0i(t)g… wiENi +1Xni(t+1)2n0i(t+1)Xni(t)2n0i(t)Pfni(t+1)jni(t)g: (5.27)Note that Pfni(t + 1)jni(t)g has been calculated in equation (5.11). Also, we can get theexpected number of data frame losses for tra–c  ow i in TTI t as:·0i(n0i(t)) =Xni(t)2n0i(t)Pfni(t)jn0i(t)g·i(ni(t)) … wiENi +1Xni(t)2n0i(t)·i(n0i(t)) (5.28)With the above approximation, the state space and the computation complexity for the opti-mization presented in Section 5.4 can be greatly reduced.Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 1685.5.2 Decomposition of The OptimizationAnother approximate method proposed here is to decouple the optimization problem into twosmaller problems and deal with them separately. Note that, given ci(t), gi(t), and bi(t) or ni(t)for every tra–c  ow i, we need to determine both the scheduled tra–c  ow and the selectedAMC mode for the  ow. Instead of optimizing them together, we flrst determine the AMCmode ki(t) for each tra–c  ow i if it needs to transmit data frames in TTI t.When the aggregate tra–c load is not too heavy, the data frame drop rate from each tra–c ow should not be very large. In such a situation, the probability of channel access shouldbe proportionally distributed to every tra–c  ow according to its average tra–c rate. So weassume that the probability of d(t) = i for any t in the optimization is:Pfd(t) = ig = DiPJ1+J2i0=1 Di0: (5.29)As a result, we can get the bufier dynamics for tra–c  ow i as:Pfbi(t+1)jbi(t)g =Pfd(t) = ig£pbuf1(bi(t+1);bi(t))+(1¡Pfd(t) = ig)£pbuf1⁄(bi(t+1);bi(t)) (5.30)And the expected data frame drops is:·0i(n0i(t)) = Pfd(t) = ig£·i(n0i(t))+(1¡Pfd(t) = ig)£·⁄i(n0i(t)) (5.31)Note that, with the above approximation, the bufier dynamics and expected data framedrops for tra–c  ow i do not depend on d(t) any more. So we can follow the same stepsdescribed in Section 5.4 to formulate a MDP for the tra–c  ow i only. It can give a stochasticmapping between the current system state for tra–c  ow i (ci(t), gi(t), bi(t) or ni(t)) andChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 169Pfki(t)jci(t);gi(t);bi(t)g, the probability of ki(t). Note that the dimension of this sub-problemis reduced by a factor of cigiENiƒJj=1cjgjƒJ1j=1EBjƒJj=J1+1ENjrelative to the dimension of the originaloptimization problem.Based on the above result, we can further optimize d(t) using the MDP in Section 5.4.However, the actions are now only the decision for d(t) in every TTI t since we already knowthe probability distribution of ki(t). So the dimension of the sub-problem is 1K of the dimensionof the original problem.5.6 Results and DiscussionsIn this section, we study the performance of the proposed QoS-CLS algorithm. For the channelof each tra–c  ow, we assume that the average SINR of the channel is 15db. The Nakagamiparameter m is 1. The channel is discretized into 5 levels with SINR bounds [¡1;2;5;10;20;1]db. We assume that the AMC modes employed in the system are the same as those listed inTable 5.1. The frame size is 1080 bits and the length of a TTI is 0.02 s. Each TTI can hold[1;2;3;6;9] frames for modes 1 to 5. This setting provides a channel with a transmission rateranging from 54kbps to 486kbps.First, we study a system in which there is only one tra–c  ow. In this case, QoS-CLSoptimizes the channel throughput by only selecting the most appropriate AMC mode for eachTTI. The following system parameters are used in this study. The initial expiration counterfor the C1 bufiering mechanism is 2 and the bufier size for frames with the same deadline is5. The bufier size for the C2 bufiering mechanism is 10. The tra–c  ow has only one tra–cstate, i.e., it follows a Poisson arrival process. As a comparison, we also present the result forChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 170a scheme where the AMC mode is simply chosen to guarantee the FER. Figure 5.1 shows theFLR of difierent tra–c  ows with varied bufiering mechanisms and scheduling schemes. In theflgure, \QoS-CLS" stands for results with the proposed QoS-CLS algorithm, \QoS-CLS, RBS"stands for results with the proposed algorithm and the reduced bufier state approximation, and\FER guaranteed" stands for results with conventional AMC mode selection scheme where thephysical layer FER is kept below the threshold 0.01 (a very close result can be achieved withthe threshold 0.001 and 0.0001 too). It is clear that the FLR achieved by QoS-CLS is muchless than that achieved by the conventional FER guaranteed scheme. Also, we can observe thatthe results for C2 bufiering scheme are much better than those for C1 bufiering scheme, sinceC1 bufiering mechanism drops frames not only where the bufier over ows but also when framedeadlines expire. However, for the FER-guaranteed scheme, when the tra–c load exceeds 1.9frame/TTI, the FLR is very close for both C1 and C2 bufiering schemes. It is because thechannel capacity is flxed and almost fully utilized for every TDMA frame so that the numberof data frames transmitted should be the same for either C1 or C2 scheme, which results in thesame FLR for both C1 and C2 schemes. Another fact we can observe in the flgure is that thereduced bufier state approximation can provide results close to those of the original QoS-CLS.Figure 5.2 compares the channel throughput of QoS-CLS and the FER-guaranteed schemes. Itis clear that with the increase of tra–c load, the gain in throughput of QoS-CLS above that ofthe FER-guaranteed scheme increases. For example, if the FLR target is 0.01, QoS-CLS canachieve a throughput of 1.84 frame/TTI (with a tra–c load of about 1.85) for C1 bufieringand 2.3 frame/TTI (with a tra–c load of about 2.32) for C2 bufiering scheme. At the sametime, the FER-guaranteed scheme can only achieve 1.4 frame/TTI (with a tra–c load of about1.4) for C1 bufiering and 1.59 frame/TTI (with a tra–c load of about 1.6) for C2 bufieringChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 171scheme. This represents a large improvement of 32% and 45% for C1 and C2 bufiering scheme,respectively, relative to the performance of the FER-guaranteed scheme. Note that for thereduced bufier state approximation method, the maximum throughput for C2 bu–ng schemewith a 0.01 FLR target is about 2.23 frame/TTI, which is about 40% better than the maximumthroughput of the FER-guaranteed scheme.Next we consider a system with multiple tra–c  ows sharing the channel. We considertwo types of tra–c  ows here. The flrst type of tra–c  ow is from a voice-over-IP (VoIP)session. The tra–c can be represented by a two-state MMPP with an average arrival rate of0 frame/TTI in state 1 (silent state) and 0.6 frames/TTI in state 2 (talk state). The averagedurations of state 1 and state 2 are 1.5s and 1s, respectively. The average tra–c load of thetra–c  ow is 0.24 frames/TTI. This tra–c  ow employs the C1 bufiering mechanism with aninitial expiration counter of 1 TTI, i.e., a frame must be sent before the next frame arrives. Thebufier size for frames with the same deadline is 6 (then the expected frame loss due to bufierover ow is about 0.0006 when the frame arrival rate is 1 frame/TTI). Also, this tra–c  ow hasa FLR guarantee requirement of FLR1 <0.01. The second type of tra–c  ow is representedby a Poisson process with the frame arrival rate 0.1 frame/TTI. All this type of tra–c  owsshares a bufier with size of 6 under C2 bufiering mechanism. Type 2 tra–c  ows have no FLRguarantee but they need to have their FLR distributed proportionally.To show the efiectiveness of our proposed scheme, we compare QoS-CLS with some existingscheduling schemes. The flrst one we use as a benchmark for comparisons is opportunisticscheduling [30, 31] (denoted as \OS" in the flgures). OS selects the tra–c  ow with the bestchannelcondition to transmit in eachTTI. Another schemechosenfor comparisons isthe earliestdeadline flrst [32] (denoted as \EDF" in the flgures), which takes into account of transmissionChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 172deadlines. EDF schedules type 1 tra–c  ows for transmissions according to the numbers ofhead of line data frames, with those having the most head of line data frames scheduled fortransmissions flrst. Type 2 tra–c  ows are only scheduled after all type 1 tra–c  ows havebeen scheduled, since type 2 data frames do not have transmission deadlines.We flrst set up a system with one type 1 tra–c  ow and a variable number of type 2 tra–c ows. The FLR of the type 1 tra–c  ow needs to be guaranteed to be less than 0:01. Figures5.3 and 5.4 show the FLR for type 1 and type 2 tra–c  ows, respectively, when the number ofthe type 2 tra–c  ows is varied from 8 to 18. In Figure 5.3, results for \QoS-CLS" and \QoS-CLS, DO" show that the FLR of type 1 tra–c  ow can always be kept below 0.01 using thesemechanisms. This demonstrates the correct operation of the proposed scheduling algorithm interms of meeting QoS constraints. The results for OS show a much greater FLR for type 1tra–c  ow since the scheme does not consider the stringent delay requirement and the bufieringmechanism. Also, the EDF scheme achieve the better FLR result for the type 1 tra–c  owthan required because type 1 tra–c  ows always get access to the channel prior to other type 2tra–c  ows. It actually wastes the channel resources and leads to a worse performance for thetype 2 tra–c  ows. We can see clearly in Figure 5.4 that the FLR result of the EDF schemeis the worst one among all schemes. In Figure 5.4, we can also see that the OS scheme canprovide a best performance for type 2 tra–c  ows because a type 2 tra–c  ow can transmit themost data frames in a TTI as long as its channel status is the best. If the target FLR is 1%,QoS-CLS can support 11 type 2 tra–c  ows and EDF can only support 8 type 2 tra–c  ows (a38% capacity improvement). OS cannot achieve a good capacity in this situation at all for itspoor support for real-time tra–c  ows. Also, the flgures show that the approximation methodDO can give similar results for type 1 tra–c  ows as the QoS-CLS scheme. But it producesChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 173a little bit higher FLR for type 2 tra–c  ows compared with the QoS-CLS scheme. Figure5.5 shows the corresponding average channel throughput for one TTI. It can be seen that theQoS-CLS scheme and its approximation scheme can provide a similar channel throughput thatis a little bit better than both those of the OS and EDF schemes.Next, we evaluate the efiectiveness of fair FLR distribution supported by QoS-CLS. We stillconsider a system with two types of tra–c  ows as above. However, in this case the type 1tra–c  ow does not require any FLR guarantee. Instead, the FLR is distributed fairly betweenthe type 1 and type 2 tra–c  ows. The distribution weights of the two tra–c  ows are the same,which means that they should experience the same FLR according to the fairness requirement.We assume that there are one type 1 tra–c  ow and ten type 2 tra–c  ows. The frame arrivalrate for a type 2 tra–c  ow is still 0.1 frames/TTI, but the frame arrival rate of the type 1tra–c  ow in state 2 is varied from 0.5 to 1.5 frames/TTI. Figures 5.6 and 5.7 show the FLRand throughout results. In Figure 5.6, we can see that the FLR of the type 1 and 2 tra–c ows are exactly the same for the QoS-CLS scheme and its approximation method. For theOS scheme, the FLR of type 1 tra–c  ow is very high and the FLR of type 2 tra–c  ows isvery small. For the EDF scheme, the FLR of type 2 tra–c  ows are much higher than thatof the QoS-CLS scheme or its approximation method, while the FLR of type 1 tra–c  ow islower than that of the QoS-CLS scheme when the tra–c load is relatively light, as EDF givesthe type 1 tra–c  ow absolute priority over type 2 tra–c  ows. However, when the tra–c loadbecomes heavy, the QoS-CLS scheme and its approximation method can still achieve a betterFLR than that of EDF for the type 1 tra–c  ow, since the proposed schemes may choose ahigher order AMC mode to transmit more frames per TTI to reduce the overall FLR. Figure 5.7shows the corresponding throughout. Note that the QoS-CLS and its approximation methodChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 174can also provide higher throughput than those of the OS and EDF schemes, when fair FLRdistribution is applied. In summary, the results from Figures 5.1 and 5.7 show that QoS-CLScan enhance the channel throughput as well as providing efiective QoS provisioning.5.7 SummaryIn this chapter, we have proposed a novel scheduling algorithm called QoS-CLS for multimediatransmissions over wireless channels with adaptive modulation and coding. To satisfy user QoSrequirements while maintaining fairness, a cross-layer framework is used for scheduling usertransmissions and selecting the appropriate AMC mode. The scheduling problem is formulatedas a MDP and solved by linear programming. As a result, the optimal scheduling policy can bepre-determined and stored in the system for tra–c scheduling in real-time. Two approximationmethods are also proposed to reduce the computational complexity of the optimization. Resultsshow that QoS-CLS can achieve signiflcant improvements in channel throughput compared tothe opportunistic scheduling algorithm and the earliest deadline flrst scheme. Furthermore, itcan efiectively guarantee QoS (i.e., FLR) and maintain fairness.Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 175Table 5.1: Parameters for Modulation and Coding Pairs in AMC1 2 3 4 5Modulation BPSK QPSK QPSK 16-QAM 64-QAMCoding rate 1/2 1/2 3/4 3/4 3/4Rate 0.50 1.00 1.50 3.00 4.50‰k 274.7229 90.2514 67.6181 53.3987 35.3508´k 7.9932 3.4998 1.6883 0.3756 0.0900¶k (db) -1.5331 1.0942 3.9722 10.2488 15.9784Table 5.2: List of Important SymbolsSymbol DesriptionW0 Length of TTI of the downlink data channelJ Number of tra–c  owK Number of modulation and coding pairsRi Transmission rate for mode ifii Max number of frames per TTI for mode iL Number of channel states£ Channel state transition matrix i;j probability for state to turn from i to j in one TTIcontinued on next pageChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 176Table 5.2: continuedSymbol DesriptionFj;i Average FER for channel state i in AMC mode jMi Number of states for tra–c  ow iDi;j Data frame arrival rate for tra–c  ow i in state j'i Tra–c transition matrix for tra–c i`i;j;j0 Probability for tra–c i to turn from state j to j0C1 Class one bufiering mechanismC2 Class two bufiering mechanismJ1 Number of tra–c  ows for C1J2 Number of tra–c  ows for C2EPi Initial expiration counter for C1 tra–c  ow iEBi Bufier size for data frames with the same deadline for C1 tra–c  ow iENi Bufier size for C2 tra–c  ow id(t) Tra–c  ow scheduled for TTI tk(t) Mode used for TTI tci(t) Channel state of tra–c  ow i at TTI tgi(t) Tra–c state of tra–c  ow i at TTI tbi(t) Bufier state for C1 tra–c  ow i at TTI tbi;j(t) Number of frames with expiration counter j for C1 tra–c  ow icontinued on next pageChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 177Table 5.2: continuedSymbol Desriptionni(t) Bufier state for C2 tra–c  ow i at TTI tChapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 1781.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 310−510−410−310−210−1100FLRTraffic load (frame/TTI)  C1, QoS−CLSC1, FER guaranteedC2, QoS−CLSC2, QoS−CLS, RBSC2, FER guaranteedFigure 5.1: FLR comparison for single tra–c  ow.1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 311.21.41.61.822.22.42.62.83Throughput (frame/TTI)Traffic load (frame/TTI)  C1, QoS−CLSC1, FER guaranteedC2, QoS−CLSC2, QoS−CLS, RBSC2, FER guaranteedFigure 5.2: Throughput comparison for single tra–c  ow.Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 1798 10 12 14 16 1810−310−210−1100FLRNumber of type 2 traffic flows  QoS−CLSQoS−CLS, DOOSEDFFigure 5.3: FLR comparison for the type 1 tra–c  ow in a system with FLR guarantee forthe type 1 tra–c  ow.Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 1808 10 12 14 16 1810−410−310−210−1FLRNumber of type 2 traffic flows  QoS−CLSQoS−CLS, DOOSEDFFigure 5.4: FLR comparison for the type 2 tra–c  ow in a system with FLR guarantee forthe type 1 tra–c  ow.Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 1818 10 12 14 16 180.811.21.41.61.82Throughout (frames/TTI)Number of type 2 traffic flows  QoS−CLSQoS−CLS, DOOSEDFFigure 5.5: Throughput comparison for the system with FLR guarantee for the type 1 tra–c ow.Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 1820.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.510−510−410−310−210−1100FLRFrame arrival rate of state 2 of the type one traffic flow (frames/TTI)  FLR1, QoS−CLSFLR1, QoS−CLS, DOFLR1, OSFLR1, EDFFLR2, QoS−CLSFLR2, QoS−CLS, DOFLR2, OSFLR2, EDFFigure 5.6: FLR comparison for the system with FLR sharing.Chapter 5. A Cross-layer Scheduling Scheme for Wireless Multimedia Transmissions with AMC 1830.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.51.11.151.21.251.31.351.41.451.51.55Throughout (frames/TTI)Frame arrival rate of state 2 of the type one traffic flow (frames/TTI)  QoS−CLSQoS−CLS, DOOSEDFFigure 5.7: Throughput comparison for the system with FLR sharing.Bibliography 184Bibliography[1] 3GPP, \Physical layer aspects of UTRA high speed downlink packet access," 3GPP TR25.848, V4.0.0, 2001.[2] W. Xiao, A. Ghosh, D. Schaefier, and L. Downing, \Voice over IP (VoIP) over Cellular:HRPD-A and HSDPA/HSUPA," Proc. of IEEE VTC2005, pp. 2785-2789, Sept. 2005.[3] 3GPP2, \Physical layer standard for CDMA2000 spread spectrum systems," 3GPP2C.S0002-0, v1.0, July 1999.[4] J. Yang, N. Tin and A. K. Khandani, \Adaptive modulation and coding in 3G wirelesssystems," Proc. of IEEE VTC2002, vol. 1, pp. 544-548, Sept. 2002.[5] A. Doufexi, S. Armour, M. Butler, A. Nix, D. Bull, J. McGeehan, and P. Karlsson, \A com-parison of the HIPERLAN/2 and IEEE 802.11a wireless LAN standards," IEEE Commun.Mag., vol. 40, no. 5, pp.172-180, May 2002.[6] IEEE Standard 802.11 Working Group, IEEE 802.11a Physical Layer Speciflcations, July1999.[7] F. Peng, J. Zhang and W. E. Ryan, \Adaptive modulation and coding for IEEE 802.11n,"IEEE Proc. WCNC 2007, March 2007.[8] H. Hu, Y. Zhang and J. Luo, \Distributed antenna systems open architecture for futurewireless communications," Auerbach Publications, CRC Press, May 2007.[9] IEEE Standard 802.16 Working Group, IEEE standard for local and metropolitan area net-works Part 16: Air Interface for Fixed Broadbandwireless Access Systems, 2002.Bibliography 185[10] H. Fattah and C. Leung, \An overview of scheduling algorithms in wireless multimedianetworks," IEEE Wireless Communications, vol. 9, no. 5, pp. 76-83, Oct. 2002.[11] A.Jalali, R.Padovani, andR.Pankaj, \DatathroughputofCDMA-HDR:Ahigne–ciency-high data rate personal communication wireless system," Proc. of IEEE VTC2000, pp.1854-1858, May 2000.[12] T. Bonald, \A score-based opportunistic scheduler for fading radio channels," Proc. ofEuro. Wireless, pp. 2244-2248, Sept. 2004.[13] G. barriac, and J. Holtzman, \Introducing delay sensitivity into the proportional fair al-gorithm for CDMA downlink scheduling," Proc. of IEEE 7th Int’l. Symp. Spread SpectrumTechniques and Apps., vol. 3, pp. 652-656, Sept. 2002.[14] H. Zeng et al., \Packet scheduling algorithm considering both the delay constraint anduser throughput in HSDPA," Proc. of Int’l. Conf. Commun., Circuits and Sys., vol. 1, pp.387-92, May 2005[15] A. Golaup, O. Holland, and A. Aghvami, \A packet scheduling algorithm supporting mul-timedia tra–c over the HSDPA link based on early delay notiflcation," Proc. 1st Int’l. Conf.Multimeda Services Access Networks, pp. 78-82, June 2005.[16] B. Al-Manthari, H. Hassanein and N. Nasser, \Packet scheduling in 3.5G high-speed down-link packet access networks: Breadth and depth," IEEE Network, vol. 21, no. 1, pp. 41-46,Jan.-Feb. 2007.Bibliography 186[17] K. W. Choi, D. G. Jeong and W. S. Jeon, \Packet scheduler for mobile communicationssystems with time-varying capacity region," IEEE Trans. Wireless Commun., vol. 6, no. 3,pp. 1034-1045, March 2007.[18] L. B. Le, E. Hossain, and A. S. Alfa,\Service difierentiation in multirate wireless net-works with weighted round-robin scheduling and ARQ-based error control," IEEE Trans.Commun., vol. 54, no. 2, pp. 208-215, Feb. 2006[19] Q. Liu, S. Zhou and G. B. Giannakis, \Cross-layer scheduling with prescribed QoS guar-antee in adaptive wireless networks," IEEE J. Selected Areas Commun., vol. 23, no. 5, pp.1056-1066, May 2005.[20] C. Cicconetti, L. Lenzini, E. Mingozzi, and G. Stea, \An e–cient cross layer schedulerfor multimedia tra–c in wireless local area networks with IEEE 802.11e HCCA," ACMSIGMOBILE Mobile Computing and Communications Review, vol. 11, no. 3, pp. 31-46,July 2007.[21] Q. Liu, S. Zhou and G. B. Giannakis, "Cross-layer combining of adaptive modulation andcoding with truncated ARQ over wireless links," IEEE Trans. Wireless Commun., vol. 3,no. 5, pp. 1746-1755, May 2005.[22] Q. Liu, S. Zhou and G. B. Giannakis, "Queuing with adaptive modulation and coding overwireless links: cross-layer analysis and design," IEEE Trans. Wireless Commun., vol. 4, no.3, pp. 1142-1153, May 2005.[23] H. Chen, H. C. B. Chan and V. C. M. Leung, \Cross-layer enhanced real-time packetscheduling over CDMA networks," Proc. of IEEE ICON2006, pp. 1-6, Sept. 2006.Bibliography 187[24] P. Y. Kong, K. C. Chua, and B. Bensaou, \A novel scheduling scheme to share droppingratiowhileguaranteeingadelayboundin amulticode-CDMA network," IEEE/ACM, Trans.Networking, vol. 11, no. 6, pp. 994-1006, Dec. 2003.[25] A. T. Anderson and B. F. Nielsen, \A Markovian approach for modeling packet tra–cwith long-range dependence," IEEE J. Sel. Areas Commun., vol. 16, no. 5, pp. 719-732,Jun. 1998.[26] E. Biglieri, G. Caire, and G. Taricco, \Limiting performance of block-fading channels withmultiple antennas," IEEE Trans. Inform. Theory, vol. 47, no. 4, pp. 1273-1289, May 2001.[27] G. L. St˜uber, Principles of Mobile Communication, 2nd ed. Norwell, MA: Kulwer, 2001.[28] Y. L. Guan and L. F. Turner, \Generalized FSMC model for radio channels with correlatedfading," IEE Proc. Commun., vol. 146, no. 2, pp. 133-137, Apr. 1999.[29] M. L. Puterman, Markov decision processes: Discrete stochastic dynamic programming,John Wiley & Sons, New York, 1994.[30] A. Farrokh and V. Krishnamurthy, \Opportunistic scheduling for streaming users in high-speed downlink packet access (HSDPA)," Proc. of GLOBECOM2004, pp. 4043-4047, Nov.2004.[31] V. Hassel, G. E. Oien, and D. Gesbert, \Throughput guarantees for wireless networks withopportunistic scheduling," Proc. of IEEE GLOBECOM, pp. 1-6, 2006.[32] J. A. Stankovic, M. Spuri, K. Ramamrithan, and G. C. Buttazzo, Deadline Scheduling forReal-Time Systems: EDF and Related Algorithms. Norwell, MA: Kluwer, 1998.Bibliography 188[33] V. Bharghavan, S. Lu, and T. Nandagopal, \Fair queuing in wireless networks: Issues andapproaches," IEEE Pers. Commun., vol. 6, no. 1, pp. 44-53, Feb. 1999.[34] S. Lu, T. Nandagopal, and V. Bharghavan, \Design and analysis of an algorithm for fairservice in error-prone wireless channels," Wirel. Netw., vol. 6, no. 4, pp. 323-343, Jul. 2000.189Chapter 6Conclusions and Future Work6.1 Summary of Work AccomplishedThis thesis has investigated several problems with regards to QoS provisioning in multipleaccess and packet scheduling schemes for multimedia transmissions over wireless communicationsystems. A new, multiple access scheme and several scheduling algorithms have been proposedto provide better QoS for multimedia tra–c in wireless communication environments. A newapproach for cross-layer enhanced QoS provisioning has been proposed and applied in the thesis.Speciflcally, we have addressed the following four major research problems, with the followingcontributions to the fleld:† A New MAC Scheme for Wireless Channels with MPR Capability: In Chapter2, we have proposed an MRMA scheme for MPR channels. The work uses an MPR channelmodel that is widely used in the literature. The proposed scheme accounts for the error-prone characteristic of the MPR channel and the speciflc design guarantees the correctoperation of the reservation. MRMA also provides an adequate slot allocation schemeto provide good QoS for multimedia tra–c  ows. A Markov analysis model has beenproposed, along with the MRMA, to evaluate the performance of the MRMA scheme,as well as to validate the simulation mode implemented in this work. The simulationChapter 6. Conclusions and Future Work 190mode provides detailed performance analysis for MRMA. The results show that MRMAcan provide efiective channel access and good QoS for multimedia tra–c. Compared toanother scheme FPLS, the system capacity of voice tra–c can be increased by 4% to 33%or 6%to 30% for SNR = 6db and SNR = 10db, respectively, in one of our simulationenvironment. Also, the data tra–c has has only a slight and almost no impact to voiceand video tra–c, respectively. The MRMA shows details for the design of MAC schemesfor wireless channels with MPR capacity and is also an efiective MAC scheme with goodQoS provisioning for multimedia transmission over wireless channels with MPR capacity.† Cross-Layer Enhanced Packet Scheduling for MC-CDMA: In Chapter 3 of thethesis, we have proposed a cross-layer enhanced packet scheduling scheme for MC-CDMAnetworks. CEPS makes scheduling decisions by considering the joint FLR, instead ofFDR and BER, separately. Essentially, CEPS assumes that the arrival of future dataframes is not predictable, and decisions are made based on the historical FLR record, thecurrent bufier status, and the QoS requirements of all difierent tra–c  ows. With thisinformation, CEPS optimizes the sum of the weighted FLR of all tra–c  ows so that thechannel throughput is optimized and the QoS is shared with predesigned weights amongall tra–c  ows. We have also implemented a simulation model for CEPS. The resultsshow that CEPS can efiectively enhance the channel throughput, compared to otherscheduling algorithms, and that the QoS is proportionally provisioned to tra–c  ows.Essentially, from the simulation result, CEPS enhanced the system capacity by 22% to39% compared to the other two scheduling algorithms. CEPS shows the efiectiveness ofthe cross-layer QoS consideration and is a practical candidate scheduling algorithm. ItChapter 6. Conclusions and Future Work 191provides  exible and efiective QoS provisioning for multimedia transmission, so that itmay be used in difierent wireless communication systems to enhance the users’ experienceswith multimedia applications.† Cross-Layer Optimization of the Maximum Number of Simultaneous Trans-missions in MC-CDMA: In Chapter 4 of the thesis, we have proposed a cross-layeroptimization for MC-CDMA. By dynamically adapting the maximum number of trans-missions for one slot, the cross-layer optimization minimizes the FLR experienced by thewhole system. During optimization, we assume that a slot allocation scheme is used tominimize the FLR, given the scheduling decision and the maximum number of simul-taneous transmissions for each time slot. Also, we assume that a scheduling algorithmis used for mapping the bufier status and the tra–c status into the scheduling decisionevery frame. These assumptions are valid and other slot allocation and scheduling al-gorithms can also be used for the optimization. According to the tra–c status and thebufier status of all tra–c  ows, the optimization determines the maximum number ofsimultaneous transmissions so that the FLR of the whole system is optimized. We havealso proposed an approximation scheme to address the computational complexity issuefor the optimization. Simulation results have been presented to show the large efiectsof the optimization. Compared to CEPS, the optimization can achieve a 10% capacityimprovement for the system. The optimization verifles the efiectiveness of the cross-layerQoS consideration and could be used to optimize channel capacity and QoS provisioningfor MC-CDMA systems.† QoS-Based Cross-Layer Scheduling for AMC-Based Systems: In Chapter 5 of theChapter 6. Conclusions and Future Work 192thesis, we have proposed a cross-layer scheduling for AMC-based systems. The QoS-CLSmethod optimizes the QoS of difierent tra–c  ows by selecting appropriate modulationand coding pairs and the scheduling decisions. The delay requirement for multimediatra–c is met by a bufiering mechanism. The FLR requirements of multimedia tra–c aresatisfled by the optimization, and for tra–c  ows not requiring the FLR guarantee, theFLR experienced is proportionally distributed according to a predesigned weight for thetra–c type. The optimization is based on the information of the tra–c status, the bufierstatus, and the QoS requirements of all tra–c  ows. Simulation result shows that thesystem capacity is increased by 38% and event more compared by the EDF and OS algo-rithms. To address the computational complexity of the optimization, two approximationmethods are proposed. QoS-CLS provides a good solution for the scheduling problem inAMC-based systems for multimedia transmissions. It can achieve precise QoS provisioningand, at the same time, optimize the channel capacity. It could be a candidate schedulingalgorithm for future wireless communication systems with AMC. Moreover, the schedulingalso verifled the efiectiveness of the cross-layer QoS consideration in AMC-based wirelesscommunication systems.6.2 Future WorkThe work described in this thesis can be the subject of future research, in several aspects, asdescribed below:† Combination of the MRMA and CEPS: We have proposed a multiple access schemeMRMA for MPR channel in Chapter 2. Although a simple, round-robin slot allocationChapter 6. Conclusions and Future Work 193mechanism is used in MRMA, it is also possible to apply other scheduling algorithmsto further provide the QoS difierentiation. Studies of the performance of the MRMAwith an advanced scheduling algorithm would be of interest. We have also proposed aCEPS scheme in Chapter 3 for MC-CDMA systems. When CEPS is applied for the uplinkscheduling, a signaling channel is required for user terminals to notify the base station andfor the base station to inform the scheduling decision and the transmission result. Oneof our future studies is to apply CEPS on MRMA, and to investigate how the signalingfunction could be taken over by the MRMA protocol and how better QoS difierentiationamong difierent tra–c  ows could be provisioned.† Admission Control for Multimedia Tra–c with Cross-Layer QoS Consider-ation: We have applied the cross-layer QoS consideration in Chapters 3, 4, and 5 tooptimize the QoS provisioning and system throughput. In addition, the result can beused to study the performance improvement in the admission control by the cross-layerQoS consideration. The admission control in MPR systems for multimedia tra–c is an-other interesting topic. The cross-layer optimizations proposed in Chapters 3, 4, and 5can further improve the channel capacity. Still, the design of an efiective and e–cientadmission control scheme becomes more complicated to allow the admitted tra–c  owsto meet their QoS requirement while channel utilization is maximized. In our future work,we intend to investigate the design of an admission control scheme with cross-layer QoSconsiderations and optimizations.† Cross-Layer QoS Consideration in Other New Wireless Technologies: Althoughthe cross-layer QoS consideration can be generally applied to any wireless link, someChapter 6. Conclusions and Future Work 194advanced wireless technologies, such as MIMO, multi-carrier CDMA, and OFDMA, aresophisticated and not easily modeled as MC-CDMA or AMC channels. Thus, to apply thecross-layer QoS consideration in such wireless channels for achieving better performanceby adjusting the physical and MAC layer schemes would be a challenging undertaking.In future work, we intend to implement the cross-layer schemes for these sophisticatedchannels to improve system performance.† Better Solutions for Proposed Optimizations: Except for Chapter 3, all of our workon the cross-layer QoS consideration is based on the optimization modeled by MDP. Wehave solved these MDP optimizations with the linear programming method. When thestatespaceoftheoptimizationbecomesverylarge, however, thecomputationalcomplexitybecomes a practical problem. We have proposed several approximation methods to reducethe state space of the optimization in Chapter 5, but still need better ways for solvingthe optimization so that it can be easily implemented in large systems. Reinforcementlearning could be a potential solution for the MDP. In future work, we intend to flnd abetter way to model the optimization problem for the cross-layer QoS consideration andflnd better ways to solve MDP-based optimizations.† Higher Layer QoS: In proposing the cross-layer QoS optimization, we have used anumber of assumptions. Some of these stipulated the speciflc design of higher layers. Forexample, we assumed that every data frame has an expiration deadline on the wirelesslink. This assumption dictates the higher layer design, which may afiect the higher layerQoS. It would be of interest to see how the cross-layer QoS consideration on the wirelesslink can afiect the end-to-end QoS of the wireless communication system. In the future,Chapter 6. Conclusions and Future Work 195we will investigate the relationship between the wireless link QoS and the end-to-end QoSof the wireless communication system, and investigate the impact of the cross-layer QoSconsideration on the higher layer QoS.Bibliography 196Bibliography[1] H. Chen, F. Yu, H. C. B. Chan and V. C. M. Leung, \A novel multiple access scheme overmulti-packet reception channels for wireless multimedia networks," IEEE Transactions onWireless Communications, vol. 6, no. 4, pp. 1501-1511, April 2007.[2] H. Chen, H. C. B. Chan, V. C. M. Leung and J. Zhang, \Cross-layer enhanced uplink packetscheduling for multimedia tra–c over MC-CDMA networks," IEEE Trans. Veh. Technol.,vol. 59, no. 2, pp. 986-992, Feb. 2010.[3] H. Chen, H. C. B. Chan, and V. C. M. Leung, \Two cross-layer optimization methods fortransporting multimedia tra–c over multicode CDMA networks," Proc. of IEEE WCNC’07,pp. 288-293, March 2007.[4] H. Chen, H. C. B. Chan, and V. C. M. Leung, \A cross-layer scheduling scheme for wirelessmultimedia transmissions with adaptive modulation and coding," Proc. of IEEE Broad-nets2008, pp. 249-256, Sep. 2008.197Appendix ACalculations for State TransitionProbabilities for MRMAA.1 Calculation of The Transition Probability T1Section 2.4 discusses the state transitions at the frame boundary between frame n and n + 1.We have:Pst = 1¡efiTf; Pts = 1¡eflTf (A.1)Suppose that there are i CON UTs and j IDL UTs changing their states; we have:j = NCON;n+1 ¡NCON;n;hn +i (A.2)Therefore, the transition probability can be found as (A.3)T1(NCON;n+1;NREV;n+1 j NCON;n;hn;NREV;n;hn) =8>>>>>>>>>>>><>>>>>>>>>>>>:minfNCON;n;hn;Nv¡NCON;n+1¡NREV;n;hngXi=maxf0;NCON;n;hn¡NCON;n+1gB(NCON;n;hn;i;Pts)£ B(NIDL;n;hn;j;Pst)NREV;n+1 = NREV;n;hn0NREV;n+1 6= NREV;n;hn(A.3)Appendix A. Calculations for State Transition Probabilities for MRMA 198whereB(x;y;z) = xy¶zy(1¡z)x¡yNIDL;n;hn = Nv ¡NCON;n;hn ¡NREV;n;hnNote that the number of REV UTs remains unchanged at NREV;n+1 = NREV;n;hn during thistransition. Also, the variables i and j in (A.3) must satisfy the following conditions:0 • i • NCON;n;hn; 0 • j • NIDL;n;hn (A.4)Based on these conditions, the upper and lower limits of i can be determined as shown in (A.3).A.2 Calculation of The Transition Probability T2Here we flrst analyze the transition from REV to IDL. The number of REV UTs changingto IDL at the end of frame n+1 is NCON;n+1 +NREV;n+1 ¡NCON;n+1;hn+1 ¡NREV;n+1;hn+1.Given that there are NREV;n+1 REV UTs at the beginning of frame n+1, the probability thatthere are NCON;n+1 +NREV;n+1¡NCON;n+1;hn+1 ¡NREV;n+1;hn+1 REV UTs changing to IDLin frame n+1 is:B(NREV;n+1;NCON;n+1 +NREV;n+1 ¡NCON;n+1;hn+1¡NREV;n+1;hn+1;Pts) (A.5)Next, we analyze the transition from CON to REV by a recursive method. Such a transitiondepends on the number of mini-slots (i.e., hn+1) in the frame, the permission probability p, theinitial number of CON uses at the beginning of the frame (i.e., NCON;n+1), and the C matrix.In frame n + 1, if there are y CON UTs at the end of the i-th mini-slot, the probability thatAppendix A. Calculations for State Transition Probabilities for MRMA 199there are x CON UTs at the end of the (i+1)-th mini-slot is:P(NCON;n+1;i+1 = x j NCON;n+1;i = y)=yXz=y¡xB(y;z;p)£Cz;y¡x (A.6)Here, z is the number of CON UTs who send reservation requests via the (i+1)-th mini-slot.By considering all the possible values of y, we have:P(NCON;n+1;i+1 = x)=NCON;n+1Xy=xP(NCON;n+1;i = y)yXz=y¡xB(y;z;p)£Cz;y¡x (A.7)Note that the initial condition is:P(NCON;n+1;0 = y) =8>><>>:1; y = NCONn+10; otherwise(A.8)Furthermore, we have:hn+1 = t£‡F ¡dNREV;n+1Kvoe·+(A.9)DenoteP(NCON;n+1;hn+1 j NCON;n+1;NREV;n+1)astheprobabilitythat, ifthereareNCON;n+1CON UTs and NREV;n+1 REV UTs at the beginning of frame n+1, there will be NCON;n+1;hn+1CON UTs at the end of frame n + 1. This probability can be found by running the recursiveequation (A.7) from i = 0 to i = hn+1 based on the initial condition deflned by (A.8).Finally, we can get the transition probability as follows:T2(NCON;n+1;hn+1;NREV;n+1;hn+1jNCON;n+1;NREV;n+1)=B(NREV;n+1;NCON;n+1+NREV;n+1¡NCON;n+1;hn+1¡NREV;n+1;hn+1;Pts)£P(NCON;n+1;hn+1jNCON;n+1;NREV;n+1) (A.10)200Appendix BList of PublicationsJournal Papers† H. Chen, F. Yu, H. C. B. Chan and V. C. M. Leung, \A novel multiple access scheme overmulti-packet reception channels for wireless multimedia networks," IEEE Transactions onWireless Communications, vol. 6, no. 4, pp. 1501-1511, April 2007.† H. Chen, H. C. B. Chan, V. C. M. Leung and J. Zhang, \Cross-layer enhanced uplinkpacket scheduling for multimedia tra–c over MC-CDMA networks," IEEE Trans. Veh.Technol., vol. 59, no. 2, pp. 986-992, Feb. 2010.† H. Chen, H. C. B. Chan, and V. C. M. Leung, \Cross-layer optimization for multimediatransport over multicode CDMA networks," submitted to IEEE Transactions on MobileComputing, Dec. 2009.† H. Chen, H. C. B. Chan, and V. C. M. Leung, \A Cross-layer Scheduling Scheme for Wire-less Multimedia Transmissions with Adaptive Modulation and Coding," in preparationfor journal submission.Conference Papers† H. Chen, F. Yu, H. C. B. Chan and V. C. M. Leung, \A novel multiple access scheme inAppendix B. List of Publications 201wireless multimedia networks with multi-packet reception," in Proc. of ACM WMuNeP2005, pp. 24-31, 2005.† H. Chen, H. C. B. Chan and V. C. M. Leung, \Cross-layer enhanced real-time packetscheduling over CDMA networks," Proc. of IEEE ICON2006, pp. 1-6, Sept. 2006.† H. Chen, H. C. B. Chan, and V. C. M. Leung, \Two cross-layer optimization methodsfor transporting multimedia tra–c over multicode CDMA networks," Proc. of IEEEWCNC’07, pp. 288-293, March 2007.† H. Chen, H. C. B. Chan, and V. C. M. Leung, \A cross-layer scheduling scheme forwireless multimedia transmissions with adaptive modulation and coding," Proc. of IEEEBroadnets2008, pp. 249-256, Sep. 2008.

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 14 44
United States 13 4
Republic of Korea 3 0
India 3 0
Canada 2 0
France 2 0
Thailand 2 0
Iraq 1 0
Uzbekistan 1 0
City Views Downloads
Unknown 14 15
Beijing 7 6
Washington 4 0
Shenzhen 4 35
Ashburn 3 0
Rosemount 3 0
Guangzhou 2 0
Vancouver 2 0
San Francisco 1 0
Nanjing 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

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-0064780/manifest

Comment

Related Items