Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Downlink packet scheduling for IEEE 802.16 point-to-multipoint fixed broadband wireless access systems Zhang, Yonghong 2006

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-ubc_2006-0730.pdf [ 3.91MB ]
Metadata
JSON: 831-1.0065426.json
JSON-LD: 831-1.0065426-ld.json
RDF/XML (Pretty): 831-1.0065426-rdf.xml
RDF/JSON: 831-1.0065426-rdf.json
Turtle: 831-1.0065426-turtle.txt
N-Triples: 831-1.0065426-rdf-ntriples.txt
Original Record: 831-1.0065426-source.json
Full Text
831-1.0065426-fulltext.txt
Citation
831-1.0065426.ris

Full Text

DOWNLINK PACKET SCHEDULING FOR IEEE 802.16 POINT-TO-MULTIPOINT FIXED BROADBAND WIRELESS ACCESS SYSTEMS by Yonghong Zhang B . E n g , X i ' a n Jiaotong Universi ty, C h i n a 1994 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F A P P L I E D S C I E N C E in T H E F A C U L T Y O F G R A D U A T E S T U D I E S (Electr ical and Computer Engineer ing) T H E UNIVERSITY OF BRITISH COLUMBIA August 2006 © Yonghong Zhang, 2006 Abstract The release o f the I E E E 802.16 standard has stimulated commerc ia l interest in dep loy ing f ixed broadband wireless access networks. A l though the fixed wireless environment is general ly less harsh than the mobi le environment, the expectations for rel iabi l i ty and performance are also higher. In suburban neighbourhoods, w ind-b lown fol iage is one o f the main factors that contribute to fading on fixed wireless channels. It seems l ike ly that fading events associated w i th the onset o f w ind w i l l occur s imultaneously on mult ip le l inks wi th in a given ce l l . Th is has important impl icat ions for both system performance and radio resource management. In this thesis, we consider the impact o f such fading on a s ingle-cel l point- to-mult ipoint sys-tem based on the I E E E 802.16 standard. U s i n g an improved R icean K- factor mode l that combines elements o f previously d isclosed models, we show that the performance o f the system is degraded when the fading events on mult ip le l inks are correlated. Further, we propose two channel-state-dependent downl ink schedulers that exploi t mult i -user diversity for use wi th T D M A mode I E E E 802.16 point-to-mult ipoint systems. The first is intended for use w i th real-t ime traffic wh i le the second is intended for use wi th a mixture o f real-t ime, min imum-rate ensured, and best effort traf-fic. We propose the use o f fair degradation for real-t ime traffic and fair resource al locat ion for delay-tolerant traffic in order to maintain quality o f service (QoS) and mitigate w ind- induced fad-ing dur ing heavy w ind condit ions. U s i n g the new concepts o f flexible t ime and urgent t ime, our proposed schedulers are able to max im ize system throughput wh i le meet ing users' different levels o f Q o S requirements. S imulat ion results show that the proposed schedulers outperform exist ing schedul ing schemes, especial ly dur ing fading events associated wi th w ind b low ing through fol iage. i i Table of Contents Abstract 1 1 Table of Contents i H List of Tables v i List of Figures v u List of Abbreviations I X Acknowledgements • X l Dedication x " 1 Introduction 1 1.1 Background • 1 1.2 Scope 2 1.3 Related Past Work and Their Limitations 2 1.4 Research Approach 5 1.5 Objectives 5 1.6 Thesis Overview 6 References 7 2 Impact of Wind-Induced Fading on the Performance of Point-to-Multipoint Fixed Wireless Access Systems 10 2.1 Introduction 1 0 iii 2.2 Effect o f W i n d - B l o w n Fol iage on Propagation 12 2.2.1 Effect o f W i n d - B l o w n Fol iage on Indiv idual L i n k s 12 2.2.2 Pre l iminary Observations o f the Corre lat ion on Mu l t i p le L i n k s 13 2.2.3 K-Fac to r M o d e l for F i xed Wire less Access Systems 15 2.3 Simulat ion Mode l s and Parameters 16 2.4 Simulat ion Results 19 2.4.1 The Influence o f Wind- Induced Fad ing on the Performance o f Systems wi th Different Terrain Type 19 2.4.2 The Influence o f Fade M a r g i n on System Performance 20 2.5 Conc lus ions 22 References 23 3 Opportunistic QoS Enhanced Scheduler for Real-time Traffic in Fixed Wireless Com-munication Systems 25 3.1 Introduction 25 3.2 Opportunist ic Q o S Enhanced Scheduler 27 3.2.1 The Schedul ing Ru le 28 3.2.2 Proact ive Packet D iscard ing M e c h a n i s m 30 3.2.3 Fa i r Degradat ion 31 3.3 Implementat ion o f O Q E S 32 3.3.1 F lex ib le T ime Cfc 32 3.3.2 Relat ive Rate Funct ion U% and (3 32 3.3.3 Urgency Funct ion gkij) and a 33 3.3.4 Adjustment Factor 7 • 33 3.4 Performance Measures 33 3.4.1 Effect ive Throughput 34 3.4.2 No rma l i zed Packet De lay 34 3.4.3 V io la t ion Factor 34 3.4.4 Fairness Index 34 3.5 Simulat ion Results 35 3.5.1 S imulat ion Envi ronment 35 iv 3.5.2 Performance under Dif ferent System L o a d 38 3.5.3 Performance Evaluat ion under Wind- Induced Fad ing 42 3.5.4 Performance o f O Q E S wi th Dif ferent Parameters 45 3.6 Conc lus ions 50 References 51 4 Multi-Service Opportunistic QoS Enhanced Scheduler for the Downlink of IEEE 802.16 Point-to-Multipoint Systems 54 4.1 Introduction 54 4.2 I E E E 802.16 Supported Services and The i r Q o S Requirements 56 4.2.1 U G S 56 4.2.2 r tPS 56 4.2.3 nr tPS 56 4.2.4 B E 57 4.2.5 Down l i nk Q o S Requirements for The Services 57 4.3 The Mu l t i -Se rv i ce Opportunist ic Q o S Enhanced Scheduler ( M - O Q E S ) 58 4.3.1 Relat ive Rate Funct ion U 59 4.3.2 Urgency Function F . . ._• 59 4.3.3 The M - O Q E S A lgo r i t hm 62 4.3.4 Implementat ion 64 4.4 S imula t ion 64 4.4.1 S imula t ion Envi ronment 65 4.4.2 Evaluat ion o f the Performance 67 4.4.3 Evaluat ion o f Short Term Fairness 69 4.5 Conc lus ions 71 References 72 5 Conclusions and Future Work 74 5.1 Conc lus ions 74 5.2 Future Work 75 v List of Tables 2.1 Parameters o f the simulated ce l l 17 2.2 Numer i ca l values o f path loss model parameters [17] 17 2.3 S N R requirement for modulat ion and coding schemes 19 3.1 S imula t ion models and parameters 36 3.2 S N R Requirement for modulat ion and cod ing schemes 36 4.1 Q o S requirements and mandatory Q o S service flow parameter to be considered by the downl ink scheduler 57 4.2 Parameters o f t h e M - O Q E S algori thm 64 4.3 Simulated traffic and their Q o S requirements 66 v i List of Figures 2.1 Preliminary observations of simultaneous fading on fixed wireless channels 14 2.2 System throughput under different terrain type and weather conditions 20 2.3 System throughput with respect to fade margin 21 3.1 System throughput with respect to system load 38 3.2 Effective throughput with respect to system load 39 3.3 Normalized Packet Delay with respect to system load 40 3.4 Violation Factor with respect to system load 40 3.5 Fairness index with respect to system load. . 41 3.6 System throughput under different weather conditions. 43 3.7 Violation factor under different weather conditions 43 3.8 Fairness index of the system under different weather conditions 44 3.9 Percentage of satisfied user in the system under different weather conditions. . . . 44 3.10 System throughput with respect to adjustment factor 7 46 3.11 Fairness index with respect to adjustment factor 7 46 3.12 System throughput with respect to parameter a 48 3.13 Violation factor with respect to parameter a 48 3.14 System throughput with respect to parameter /? 49 3.15 Violation factor with respect to parameter (3 49 4.1 System architecture of the M-OQES scheduling algorithm 58 4.2 Example urgent function for rtPS service (FrtPS{t) = 1, t > Trt; ae 1 / ' , t < Trt). . 60 4.3 Example urgent function for BE service (FBE(c/C) = ^eclc) 61 vii 4.4 Examp le urgent funct ion. The m in imum reserved rate part o f the urgent funct ion for nr tPS service ( F n r t P S ' M R T R { s / S ) = 1, s/S < Tnrt; (3esls,s/S > Tnrt). . . . 62 4.5 System throughput o f the simulated system when using different schedul ing schemes. 67 4.6 M a x i m u m , mean, and m i n i m u m receiv ing ratio o f v ideo users o f the simulated sys-tem when using different schedul ing schemes 68 4.7 M a x i m u m , mean, and m in imum throughput o f the nrtPS users o f the simulated system when using different schedul ing schemes 68 4.8 M a x i m u m , mean, and m i n i m u m throughput o f B E users o f the simulated system when us ing different schedul ing schemes 69 4.9 Short term fairness o f the M - O Q E S schedul ing algor i thm 70 v i i i List A M C B E B S E D F E X P F B W A H O L M a x R R M L M - O Q E S M R T R nrtPS O Q E S P C S P F P M P Q o S R R R R M rtPS S N R SS of Abbreviations Adapt ive Modu la t ion and C o d i n g Best Effort Base Station Earl iest Deadl ine First Exponent ia l Ru le F i xed Broadband Wireless Access Head o f L i n e (refers to the first packet o f a queue) M a x i m u m Rate Reward M a x i m u m Latency Mu l t i - serv ice Opportunist ic Q o S Enhanced Scheduler M i n i m u m Reserved Traff ic Rate N o n - R e a l - T i m e Po l l i ng Service Opportunist ic Q o S Enhanced Scheduler Personal Communicat ions Services Proport ional Fai r Po in t - to-Mul t ipo in t Qual i ty o f Service R o u n d R o b i n Rad io Resource Management Rea l -T ime Po l l i ng Service Signal to No ise Rat io Subscriber Station ix T D M A T ime D i v i s i o n Mu l t i p le Access T J Tolerated Jitter T P Traff ic Pr ior i ty U G S Unso l i c i ted Grant Service Acknowledgements I offer my enduring gratitude to the faculty, staff and m y fe l low students at U B C , a l l o f whom have inspired me to continue my work in this f ie ld. I owe part icular thanks to m y supervisor, Prof . D a v i d G . M i c h e l s o n , who init iated this research topic and has spent a lot o f t ime on useful discussions. Thanks to the Natura l Sciences and Engineer ing Research C o u n c i l ( N S E R C ) o f Canada for awarding me a Post Graduate Scholarship ( P G S ) as w e l l as Prof. M i c h e l s o n for prov id ing me wi th addit ional f inancial support. Together, they have prov ided me wi th the f inancial means to engage in and complete this work. Spec ia l thanks are owed to my husband, who has supported me throughout m y years o f education. Y O N G H O N G Z H A N G THE UNIVERSITY OF BRITISH COL UMBIA August 2006 x i To my parents and my family. xu Chapter 1 Introduction The thesis is concerned wi th characterization o f the f ixed wireless propagation channel and ex-ploitat ion o f this understanding to design packet schedul ing schemes that w i l l funct ion we l l in the presence o f channel impairments. Our goals are: (1) to provide more effective qual i ty o f service (QoS) prov is ion ing mechanisms and (2) to max imize system throughput for point- to-mult ipoint ( P M P ) f ixed broadband wireless access systems ( F B W A ) . In particular, we propose packet schedul-ing schemes for the downl ink o f the I E E E 802.16 F B W A systems that cou ld help mitigate fading associated wi th w i n d b lown fol iage as is often encountered in typ ica l f ixed wireless systems. 1.1 Background The I E E E 802.16 standard is a set o f specif ications for broadband wireless metropol i tan access networks ( M A N s ) . Such networks provide h igh speed data communicat ion through f ixed wireless connections over a wide area at low cost. They can be deployed in locations such as the countryside or new residences where neither cable nor twisted pair have been laid out. They can also be deployed in exist ing neighbourhoods by competit ive carriers so they can provide service without leasing l ines f rom incumbent carriers. Furthermore, such networks a l low carriers to provide portable service. A l though the f ixed wireless environment is general ly less harsh than the mobi le environment, they are expected to provide wire l ine performance. Thus, the expectations for rel iabi l i ty and performance are also higher. For f ixed wireless systems deployed in suburban neighbourhoods, w ind -b lown fol iage is 1 one o f the main factors that cause the channel to fade. Appropr ia te diversity and cod ing schemes, in concert w i th suitable radio resource management ( R R M ) schemes, a l low the system to provide a satisfactory Q o S wi th the smallest fade margin even in the face o f severe propagation impairments. The I E E E 802.16 Work ing Group has deliberately left the R R M schemes unspecif ied in an effort to encourage innovative designs. Th is gives us great opportunit ies to exploi t the characteristics o f the propagation channel in designing appropriate schemes that provide better Q o S prov is ion ing wh i le max im iz i ng system throughput. 1.2 Scope Rad io resource management is concerned wi th the efficient ut i l izat ion o f the scarce spectrum re-sources so as to support a wide range o f services wi th user satisfactory Q o S and max im ize system capacity in gain ing higher revenue for service providers. There are a lot o f aspects involved in R R M . Connect ion admiss ion control checks whether a new connect ion request shal l be accepted, packet schedul ing decides the time and sequence for packet t ransmission, and load control manages situations when system load exceeds a certain threshold. Other R R M strategies inc lud ing subchan-nel assignment, power contro l , etc. In this thesis, instead o f t ry ing to devise wi th a complete set o f R R M schemes that are able to solve the entire problem, we w i l l concentrate on packet schedul ing due to its key role in assuring Q o S for indiv idual users. 1.3 Related Past Work and Their Limitations Un l i ke the mobi le communicat ion systems, in the absence o f mot ion o f the user terminal itself, fading on fixed and stationary wireless l inks is general ly the result o f movement o f scatterers in the environment. The role o f w ind gusts and environmental disturbances in causing fading events on non- l ine-of-s ight fixed and stationary wireless channels has been we l l established dur ing the past several years by several researchers based upon both laboratory and field measurements [1-10] . The first-order statistics o f such fading has been characterized by previous researchers and were accounted for dur ing the propagation model ing activit ies o f the I E E E 802.16 Work ing Group on Broadband Wife less Access [11,12]. However, the results do not a l low the nature, frequency, and duration o f such events to be predicted f rom knowledge o f phys ica l and environmental parameters 2 o f the deployment area. Such information is crucia l for the effective design and simulat ion o f f ixed wireless systems. Because w ind events are often felt over large areas, many l inks in a given ce l l may be affected simultaneously (albeit to vary ing degrees depending on the amount and type o f fol iage along each path). Such correlat ion between fading events cou ld have signif icant impact on the capacity and performance o f the system. However , none o f the previous study has considered the impact o f such correlat ion. Bo th t ime-vary ing fading channel and the correlat ion between fading events on mult ip le l inks are obstacles for prov id ing Q o S to users. The packet schedul ing scheme in the med ium access control layer, wh i ch arbitrates among mult ip le users in accessing to the shared wireless channel, is one o f the key components in eff iciently u t i l iz ing the resources wi th Q o S prov is ion ing for ind iv idual users. The real-t ime schedul ing problem was intensively studied in the 1980's for the sharing o f computer processors or other shared resources such as the communicat ion channel, o f wh ich the goal is to process each job in a t imely manner (e.g., del iver the packet wi th in certain deadlines). The earliest deadline first ( E D F ) [13] or earlier due date po l icy has been considered opt imal in so lv-ing real t ime schedul ing problems. For non-real-t ime data communicat ions, such as file transfer, however, the ma in concern is no longer guaranteeing the del ivery o f each packet before its expira-t ion, but rather, is to fair ly distribute the l imi ted resources to each user, so that users can receive relat ively same level o f service. The general ized processor sharing ( G P S ) [14] a lgor i thm is one o f such schedul ing schemes that can guarantee such fairness in an error-free environment. Cons ider ing the unique characteristics o f the wireless channel , the above ment ioned wi re-less system schedul ing rules are not readi ly appl icable to wireless systems. A fami ly o f wireless schedul ing schemes is adapted f rom its wire l ine counterpart consider ing the impairments o f the wireless channel wh i ch is main ly modeled as either good or bad using the Gi lber t -E l l io t t model . Examples o f past efforts to develop schedulers suitable for wireless non-real-t ime appl icat ions are described in [15] and the references therein. Some studies have extended the wire l ine version E D F to the wireless scenario [16-18] for real-t ime appl icat ions. Instead o f treating the variat ion o f wireless channel as impairments, mult i -user diversity [19] considers the t ime-vary ing property o f wireless channel as an opportunity. It exploits the channel 3 condit ions o f mult ip le users, and opportunist ical ly selects the user w i th better channel qual i ty for transmission under certain constrains, such as fairness or t imel iness. M a n y studies have proposed to exploi t mult i -user diversity for non-real-t ime appl icat ions. Dif ferent types o f fairness have been considered, inc lud ing service t ime fairness [20,21] and proport ional fairness [22]. For real-t ime appl icat ions, on the other hand, on ly a few studies have exploi ted the t ime-vary ing property o f the channel to max im ize system throughput for delay-sensit ive traffic [23-25] . However, these schedulers judge the urgency o f a packet only on packet delay, wh i ch cou ld make long packets that need signif icant amount o f t ime for transmission at disadvantages in meet ing their deadlines. Meanwh i l e , the above mentioned opportunistic schedulers do not provide any mechanism for preventing the transmission o f packets that w i l l have expired before they are del ivered, wh ich cou ld result in bandwidth wast ing. A l though some schedulers consider d iscarding expired packets, they are intended for use wi th specif ic traffic, such as v ideo [26]. Furthermore, none o f the mult i -user diversity scheduler for real-t ime traffic has considered fair degradation among users when the system cannot satisfy every user's requirement. W h e n the system is overloaded, not every packet o f the real t ime users is able to meet its delay requirement. A s a result, i f fair degradation among real-t ime users was not considered, and since users can only tolerant certain amount o f packet dropping, some o f the users cou ld experience unbearable service. In terms o f a mixture o f real-t ime and delay-tolerant traffic, most studies have treated the two types o f traffic separately. Usua l ly , only after taking care o f the needs o f al l real-t ime flows do most o f the algori thms consider the delay-tolerant traffic. Th is approach is fine for wi re l ine systems where the channel condi t ion rarely changes. For wireless systems, however, because the channel qual i ty for each flow is not f ixed, explo i t ing mult i -user diversity to max im ize system throughput is better achieved by examin ing al l flows al l at once rather than look ing at each traffic type in sequence. Very few studies have considered schedul ing both real-t ime and non-real-t ime flows together. In [27], the exponential rule [23] and proport ional fair rule [22] combined algor i thm seeks to max im ize system throughput for both delay sensitive traffic and best effort traffic. A n adaptive factor is introduced to adjust the resource distr ibution between delay sensitive traffic and best effort traffic. However , same as the exist ing opportunistic real-t ime schedulers, the combined algor i thm does not provide any packet d iscarding mechanism and long packets cannot be guaranteed to meet their deadlines. 4 1.4 Research Approach To design a packet schedul ing scheme that is appropriate for P M P F B W A systems that are v u l -nerable to wind- induced fading, it is important to understand the characteristics o f the propagation channel dur ing the w indy state. Based on previous studies on the effect o f w ind b low ing through fol iage on ind iv idual l inks, compared to the ca lm state when there is no w ind , the propagation channel under heavy or gusty w ind exhibits R icean distr ibution [3,9] w i th lower K- factor [9,10] wh i ch result in deeper fading [8] and higher signal f luctuation [5,7] . A l though deeper fading cou ld cause h igh packet error ratio, the higher f luctuation also introduces opportunities. In a t ime-slotted system where only one user can transmit dur ing any time instant, we can use the technique o f mult i -user diversity to schedule the user for transmission only when its l ink presents its peak channel quality. U s i n g mult i -user diversity not on ly avoids any transmission at users' deep fades, but also poss ib ly results in higher overal l system throughput w i th adaptive modulat ion and cod ing, because the higher fluctuation dur ing w indy state indicates higher peak values for affected users. Therefore, it is appropriate to use mult i -user diversity in the schedul ing design for mit igat ing the wind- induced fading on the l ink level . Meanwh i l e , for real-t ime applications that have tight delay constraints, schedul ing based on expiry t ime has been considered opt imal in wire l ine systems where channel capacity rarely changes. In wireless systems, however, because the qual i ty o f user's channel changes over t ime, it may be more benef ic ial to consider user's instantaneous channel quali ty a long w i th packets ' expiry t ime for schedul ing decisions. A s a result, w ise ly using the techniques o f mult i -user diversity consider ing packet 's expiry t ime in the schedul ing design for real-t ime appl icat ions is a suitable approach. 1.5 Objectives In this thesis, we main ly focus on the design o f packet schedul ing scheme that exploits mult i -user diversity for the downl ink o f T D M A mode I E E E 802.16 P M P F B W A systems. Ou r objectives are to: 1. Determine fundamental l imitat ions (in the sense that we account only for signal to noise ratio ( S N R ) ) on the impact o f wind- induced fading on the performance o f a s ingle-cel l P M P F B W A 5 system. 2. Des ign a downl ink packet schedul ing scheme located at the base station for real-t ime traffic for the T D M A mode I E E E 802.16 P M P F B W A systems that (1) exploits mult i -user diversity for max im iz ing system throughput, (2) provides Q o S prov is ion ing, (3) proact ively discards packet that are to be dropped in order to prevent system resources f rom being wasted, and (4) ensures fair degradation among users for better performance under overloaded system status caused by w i n d -induced fading. 3. Des ign a downl ink packet schedul ing scheme located at the base station for the T D M A mode I E E E 802.16 P M P F B M A systems that both provides Q o S for a l l level o f services supported by the standard and max imizes system throughput consider ing the characteristics o f the propagation channel o f the f ixed wireless systems. 1.6 Thesis Overview Th is thesis is written in the manuscript-based format according to guidel ines specif ied by the Facul ty o f Graduate Studies o f the Univers i ty o f Br i t i sh Co lumb ia . In Chapter 2, we assess the effect o f w ind-b lown fol iage on both ind iv idual l inks and m u l -t iple l inks. B y proposing a complete K-factor model for F B W A systems descr ib ing the w ind effect, we are able to assess the system performance changes under different weather condit ions. In Chapter 3, by introducing the concept o f f lexible t ime and urgent t ime per iod, we propose an opportunist ic Q o S enhanced scheduler ( O Q E S ) wh i ch tries to max im ize system throughput by explo i t ing the t ime-vary ing channel by apply ing mult i -user diversity as we l l as a "meets de lay" requirement. To avoid wast ing bandwidth, a s imple proactive packet d iscarding mechanism has been introduced to discard packets that w i l l have expired before they are del ivered. Fa i r degradation mechanism is also proposed in coping w i th the capacity degradation prob lem caused by w i n d -induced fading. In Chapter 4, we extend the work o f Chapter 3 to support the mult i -services o f I E E E 802.16 by def ining different urgency functions according to the requirements o f ind iv idual services. In Chapter 5, we summarize the contributions o f our work and offer recommendat ions for future work. 6 References [1] P. B . Papazian, G . A . Huf fo rd , R. J . Acha tz , and R. Ho f fman , "S tudy o f the loca l mult ipoint distr ibution service radio channel , " IEEE Transactions on Broadcasting, vo l . 43 , no. 2, pp. 175-184, 1997. [2] D. A . J . Pearce, A . G . Burr , and T. C . Tozer, " M o d e l l i n g and predict ing the fading performance o f f ixed radio l inks through vegetation," in Proc. of National Conference on Antennas and Propagation, 1999, pp. 263 -266 . [3] A . Ka j iwa ra , " L M D S radio channel obstructed by fol iage," in Proc. of IEEE International Conference on Communications, vo l . 3, 2000, pp. 1583-1587. [4] J . C . R. D a l B e l l o , G . L . Siqueira, and H . L. Ber ton i , "Theoret ica l analysis and measurement results o f vegetation effects on path loss for mobi le cel lu lar communicat ion systems," IEEE Transactions on Vehicular Technology, vo l . 49 , no. 4 , pp. 1285-1293 , 2000. [5] S. Perras and L. Bouchard , "Fad ing characteristics o f R F signals due to fol iage in frequency bands f rom 2 to 60 G H z , " in Proc. of IEEE 5th International Symposium on Wireless Personal Multimedia Communications (WPMC 2002), vo l . 1, 2002, pp. 2 6 7 - 2 7 1 . [6] A . Domazetov ic , L . J . Greenstein, N . B . Mandayam, and I. Seskar, "Es t imat ing the Dopp le r spectrum o f a short-range fixed wireless channel , " IEEE Communications Letters, vo l . 7, no. 5, pp. 2 2 7 - 2 2 9 , 2 0 0 3 . [7] P. L e d l , P. Pechac, and M . Mazanek , "T ime-ser ies predict ion o f attenuation caused by trees for fixed wireless access systems operating in mi l l imeter waveband," in Proc. of Antennas and Propagation. (ICAP 2003), vo l . 2, 2003, pp. 646-649 . [8] E . R. Pelet, J . E . Salt, and G . Wel ls , "Ef fec t o f w ind on fol iage obstructed l ine-of-sight channel at 2.5 G H z , " IEEE Transactions on Broadcasting, vo l . 50, no. 3, pp. 2 2 4 - 2 3 2 , 2004. [9] M . H . Hash im and S. Stavrou, " W i n d influence on radio waves propagating through vegetation at 1.8 G H z , " Antennas and Wireless Propagation Letters, vo l . 4 , pp. 143 - 146, 2005. 7 [10] D . Crosby, V. S. Abhayawardhana, I. J . Wasse l l , M . G . B r o w n , and M . P. Sel lars, " T i m e var iabi l i ty o f the fol iated f ixed wireless access channel at 3.5 G H z , " in Proc. of IEEE 61st Vehicular Technology Conference. (VTC 2005-Spring) , vo l . 1, 2005, pp. 106-110. [11] V . E rceg et a l , "Channe l models for f ixed wireless appl icat ions," IEEE 802.16 Working Group, 2003. [12] L . J . Greenstein, S. Ghassemzadeh, V. Erceg , and D. G . M i c h e l s o n , " R i c e a n K-factors in narrowband f ixed wireless channels: Theory, experiments, and statistical models , " in Proc. of International Symposium on Wireless Personal Multimedia Communications. (WPMC99), 1999. [13] S. S. Panwar, D. Towsley, and J . K . Wol f , "Op t ima l schedul ing pol ic ies for a class o f queues wi th customer deadlines to the beginning o f service," Journal of the ACM (JACM), vo l . 35, no. 4, pp. 832 -844 , 1988. [14] A . K . Parekh and R. G . Gal lager, " A general ized processor sharing approach to f low control in integrated services networks: The single-node case," IEEE/ACM Transactions on Networking, vo l . l , n o . 3, pp. 344 -357 , 1993. [15] H . Fattah and C . Leung , " A n overview o f schedul ing algori thms in wireless mul t imedia net-works , " IEEE Wireless Communications, vo l . 9, no. 5, pp. 7 6 - 8 3 , 2002. [16] S. Shakkottai and R. Srikant, "Schedu l ing real-t ime traffic w i th deadlines over a wireless chan-ne l , " Wireless Networks, vo l . 8, pp. 13-26, 2002. [17] P. Y . K o n g and K . H . Teh, "Per formance o f proactive earliest due date packet schedul ing in wireless networks," IEEE Transactions on Vehicular Technology, vo l . 53, no. 4, pp. 1224— 1234, 2004. [18] M . A d a m o u , S. Khanna , I. Lee , I. Sh in , and S. Z h o u , "Fa i r real-t ime traffic schedul ing over a wireless L A N , " in Proc. of the 22nd IEEE Real-Time Systems Symposium, 2001, pp. 279 -288 . [19] R. K n o p p and P. A . Humblet , " Informat ion capacity and power control in s ingle-cel l mu l t i -user communicat ions," in Proc. of IEEE International Conference on Communications, vo l . 1, 1995, pp. 331 -335 . [20] X . L i u , E . K . P. C h o n g , and N . B . Shroff, "Opportunist ic t ransmission schedul ing wi th resource-sharing constraints in wireless networks," IEEE Journal on Selected Areas in Com-munications, vo l . 19, no. 10, pp. 2053-2064 , 2001. [21] Y . L i u , S. G r u h l , and E. W. Kn igh t ly , " W C F Q : A n opportunist ic wireless scheduler w i th sta-t ist ical fairness bounds," IEEE Transactions on Wireless Communications, vo l . 2, no. 5, pp. 1017 -1028 ,2003 . [22] A . Ja la l i , R. Padovani , and R. Pankaj , "Da ta throughput o f C D M A - H D R a h igh eff ic iency-high data rate personal communicat ion wireless system," in Proc. of IEEE 51st Vehicular Technology Conference. (VTC 2000-Spring), vo l . 3, 2000, pp. 1854 - 1858. [23] S. Shakkottai and A . L . Stolyar, "Schedu l ing for mult ip le flows sharing a t ime-vary ing chan-nel : The exponential rule," American Mathematical Society Translations, vo l . 207, 2002. [24] M . Andrews et a l . , " C D M A data Q o S schedul ing on the forward l ink wi th variable channel condi t ions," B e l l Laborator ies, Tech. Rep. , Apr . 2000. [25] P. L i u , R. Berry , and M . L . H o n i g , "Delay-sensi t ive packet schedul ing in wireless networks," in Proc. of IEEE Wireless Communications and Networking. (WCNC 2003), vo l . 3, 2003, pp. 1627-1632. [26] J . Tang, L . Zhang , and C . - K . Siew, " A n opportunistic v ideo schedul ing algor i thm over shared wireless downl ink , " Computer Communications, vo l . 29 , pp. 1917-1926, 2005. [27] R. Jong-Hun , J . M . Ho l t zman , and K . D o n g Ku", "Per formance analysis o f the adaptive E X P / P F channel scheduler in an A M C / T D M system," IEEE Communications Letters, vo l . 8, no. 8, pp. 4 9 7 ^ 9 9 , 2004. 9 Chapter 2 Impact of Wind-Induced Fading on the Performance of Point-to-Multipoint Fixed Wireless Access Systems 2.1 Introduction In recent years, the introduction o f the I E E E 802.16 standard for f ixed broadband wireless access has st imulated interest in the nature o f propagation on non-l ine-of-sight l inks in macroce l l suburban environments. In the absence o f mot ion o f the user terminal itself, fading on f ixed and stationary wireless l inks is general ly the result o f movement o f scatterers in the environment, such as the movement o f people, w i ld l i fe , or vehicles in the v ic in i ty o f the path. However , the dominant source o f such fading in suburban macrocel l environments is w ind-b lown fol iage. The effect o f w ind-b lown fol iage on radiowave propagation over f ixed wireless l inks has been studied by several research groups dur ing the past decade based upon both laboratory and f ie ld measurements [1-10]. The first-order statistics o f such fading have been characterized by previous researchers and were accounted for dur ing the propagation model ing activit ies o f the I E E E 802.16 Work ing Group on Broadband Wireless Access [11,12]. 'The material in this chapter is mainly based on Yonghong Zhang and David G. Michelson, "Impact of Wind-Induced Fading on the Capacity of Point-to-Multipoint Fixed Wireless Access Systems," Proc. of International Wireless Commu-nications and Mobile Computing Conference (IWCMC 2006), Vancouver, Canada, July 2006. 10 Previous studies have we l l established the not ion that fade depth increases as w ind speed increases, wh i ch translates to a lower R icean K-factor. Several K- factor models have been proposed in the literature. E a c h describes part o f the phenomenon. In [12], Greenstein et. al. have related K- factor to the parameters o f subscriber station (SS) antenna and distance to the base station (BS) . However , the model is a statistical descript ion based upon data col lected over a long per iod o f t ime and the manner in wh i ch K- factor changes wi th w ind speed is not captured. Hash im and Stavrou [8] proposed a K-factor model that accounts for w ind speed, and Crosby et. al. [9] expressed K-factor w i th respect to excess path loss and w ind speed using a different approach. A l l have focused on l ink level performance. In order for us to assess the effects o f w ind-b lown fol iage on system throughput, it is necessary to combine and extend these models. Meanwh i l e , because w ind events are often felt over large areas, many l inks in a given ce l l may be affected simultaneously (albeit to vary ing degrees depending on the amount and type o f fol iage along each path). Such correlat ion between fading events cou ld have signif icant impact on the capacity and performance o f the system. The tendency o f some l inks to be h igh ly susceptible to such fading may not be obvious i f the system is instal led in ca lm weather. Thus , it 's quite possible for the system operator to be unpleasantly surprised by unexpected degradation in system performance dur ing periods o f severe fading during periods o f h igh winds. A l though the effect o f w ind b low ing through fol iage on a single l ink have been wel l -s tudied and several K- factor models that describe such effect have been proposed, the not ion that fading events on different l inks wi th in a ce l l may be correlated, a complete K-factor mode l that fu l ly de-scribe the effect, and the impact o f this phenomenon on performance o f the system have apparently not been previously explored. Accord ing ly , this paper presents pre l iminary observations o f such fading events, proposes a complete K- factor model , and provides an assessment o f the effect o f such fading on the performance o f f ixed broadband wireless access ( F B W A ) systems. In Sect ion 2.2, pre-v ious work concerning the effect o f w ind b low ing through fol iage on wireless s ignal propagation is reviewed and a complete K-factor model is proposed. In Sect ion 2.3, the s imulat ion models and pa-rameters are described. In Sect ion 2.4, s imulat ion results are presented. In Sect ion 2.5, conclusions are drawn. 11 2.2 Effect of Wind-Blown Foliage on Propagation 2.2.1 Effect of Wind-Blown Foliage on Individual Links The presence o f fol iage along a path signif icantly affects the propagation o f radio waves [13], whether the fol iage is in the form o f a single tree, a row o f trees, a f ie ld o f crops, or a forest. W h e n the w ind b lows through such fol iage, the movement o f the swaying leaves and branches introduces an addit ional level o f complex i ty in the received s ignal , wh i ch results in deeper fading and higher power variat ion. The severity o f these effects, however, is quite dependent upon carrier frequency, the direct ion and veloci ty o f w ind , tree species, fol iage density, and the structure o f the leaves and branches. Du r ing the past several years, researchers have studied the effect o f w ind b low ing through fol iage based upon both laboratory and f ie ld measurements. Through the study o f data col lected in and around Nor thg lenn, Co lo rado and San Jose, Ca l i fo rn ia at 28.8 G H z and 30.3 G H z , Papazian et al.[\] found out that w ind b low ing through trees can cause signal attenuation and signal variabil i ty. However , the best fit R icean distr ibution predicted deeper fades than were actually observed. Results based upon experiments conducted by Hash im and Stavrou [8] at 1.8 G H z and f ie ld measurements performed by Crosby et al [9] at 3.5 G H z and N a z and Falconer [10] at 29.5 G H z conf i rmed that the received signal resembles R icean distr ibution regardless o f the w ind speed. A n empir ica l mode l that relates the R icean K- factor to w ind speed at 1.8 G H z has been proposed in [8]. Pelet et al [7] studied the fading characteristics o f a 6 - M H z - w i d e channel centred at 2.545 G H z through measurements on f ixed wireless paths b locked wi th a few trees. Deep fading was observed, especial ly when the w ind is h igh or gusty. They also not iced that the fades are largely flat across the band but wi th some frequency selective fading. B e l l o et al. [3] observed this fade induced by w ind through their studies o f propagation in an urban forested park area. Ka j iwa ra [2] reported the attenuation characteristics o f swaying fol iage in w ind by experiments performed at 5 G H z and 29.5 G H z . The studies in [4,6] showed that the received signal variations increase wi th the increase o f w ind speed. To summar ize, here are some o f the observed effects caused by w ind b low ing through fo-liage: • Deep fading. W i n d can cause signif icant fading. Based on the study o f [7], w ind imp ing ing 12 on the trees at velocit ies as low as 15 km/h can cause fades o f 15 d B wi th slopes o f up to 50 dB/second at 2.4 G H z . • R icean distr ibution. The fading channel o f propagation through vegetation is observed to be R icean fading [2,8], independent o f the presence o f w ind . The probabi l i ty density funct ion o f a R icean distr ibution is given by [14] where p2 is the variance, Io(-) is the modi f ied Bessel funct ion o f the first k ind and zero-order, and K is the R icean K-factor defined as the ratio o f the " f i x e d " component power and the "scatter" component power. • R icean K-factor. K- factor is observed to decrease as w ind speed increases. • F lat fading. The fading dur ing w ind events has a signif icant flat fading component, e.g., one 15dB fade had an average fade o f lOdB across the band and excess fading o f 5dB at some frequencies [7]. • Seasonal dependence. Because leaves are present in summer but fa l l o f f in winter, the effects are more severe in summer than in winter [9]. 2.2.2 Preliminary Observations of the Correlation on Multiple Links W h i l e the first-order statistics o f fading on f ixed wireless l inks have been characterized by previous workers, several key questions o f great interest to system planners and deployment teams remain largely unanswered: D o al l l inks in a given ce l l exhibit the same range o f channel behaviour, or are some more fragile than others? To what degree are fading events on different l inks correlated wi th each other, and wi th meteorological events such as w ind gusts? What are the impl icat ions o f correlat ion between fading events for radio resource management schemes? Pre l iminary observations col lected in a typical suburban macroce l l environment in the 2 G H z P C S band suggest answers to some o f these questions. Three l inks ranging in length f rom 600 meters to 1.4 k m were moni tored for a 48-hour per iod. The terrain in the study area is flat w i th stands o f tall trees dispersed throughout the neighbourhood. A l l three l inks fal l w i th in a 60-degree sector. None have a l ine-of-sight to the base station. The shortest l ink is relatively free o f (2.1) 13 48; hours Figure 2.1 : Pre l iminary observations o f simultaneous fading on f ixed wireless channels. obstructions. The middle l ink is obstructed by a large stand o f trees in the distance. The longest l ink is obstructed by a large stand o f trees in the immediate v ic in i ty o f the remote terminal. Traces o f received signal strength over t ime are presented in F i g . 2.1. Several trends are apparent: 1. Du r ing the observation per iod, three major events lasting several hours were observed. The fading events were fair ly wel l -def ined and tended to last for tens o f minutes to hours. The onset o f each fading event tended to be fair ly s low and usual ly took at least several minutes. This is l ike ly favourable f rom a radio resource management perspective because it impl ies that the system has considerable t ime to adapt to changing channel condit ions. 2. Some o f these l inks are obv ious ly much more robust than others. Path 1, wh i ch is the least obstructed, experiences shorter and less intense fading events than Path 2. It is clear that Path 3 is 14 by far the worst. Th is raises an obvious question: H o w easy wou ld it be to improve the performance o f Path 3 s imply by shif t ing the locat ion o f the remote terminal? 3. W h e n fading events occur, they tend to do so on a l l three l inks simultaneously. Th is has serious impl icat ions for systems that use adaptive modulat ion schemes to deal w i th changes in channel characteristics. It impl ies that total system capacity w i l l be severely affected by the onset o f fading and that one cannot necessari ly assume that, on average, the number o f good and bad l inks at a given t ime w i l l be equal. 2.2.3 K-Factor Model for Fixed Wireless Access Systems Based on the former d iscussion, we notice the signif icance o f the changing o f R icean K- factor induced by w i n d over fol iage. A s we ment ioned, al l o f the exist ing K-factor models have captured part o f the picture w e l l and none o f them has considered the correlat ion between mul t ip le l inks. To provide system planners wi th a complete propagation and channel mode l that accurately describe the environment for the purpose o f simulat ions and design, it is necessary for us to propose a more complete K- factor model . Based on the exist ing K-factor models, the observations o f the correlat ion on mul t ip le l inks, and our understanding o f the wind- induced fading on propagation channel o f the f ixed wireless systems, we bu i ld our K- factor model based on the fo l lowing hypotheses, • Hypothesis 1: L i n k s wi th h igh shadow fading have a higher probabi l i ty o f exper iencing a greater range o f K-factors. • Hypothesis 2: L i n k s wi th a h igh fol iage index have a higher probabi l i ty o f exper iencing a greater range o f K-factors. • Hypothesis 3: L i n k s wi th a longer range have a higher probabi l i ty o f exper iencing a greater range o f K-factors. • Hypothesis 4: The changing o f K-factors on different l inks are correlated. • Hypothesis 5: Fad ing on different l inks is uncorrelated. Ou r mode l ( in l inear units) is presented as fo l lows, 15 K = FsFhFbK0<Psa°ea"vt (2.2) where Fs is the seasonal factor, Fh is the receive antenna height factor, Fb is the beamwidth factor, d is the distance between the base station (BS) and the SS in ki lometers, s is the shadowing effect or excess path loss wh ich fo l lows lognormal distr ibution, v is the average w ind speed, t is the vegetation factor descr ib ing the degree o f the w ind effect, KQ, 7, a s , and a v are a l l data-derived constants. Parameters Fs, F^, KQ, and d1 have the same meaning as in Greenstein's model . The exponential term is taken f rom Hash im 's model to introduce the w ind effect, an extra vegetation factor t has been added along wi th w ind speed to differentiate locations wi th and without trees in the immediate v ic in i ty o f the S S . Not ice that because we have introduced shadowing effect s in the path loss mode l into our K- factor mode l , path loss model and K- factor mode l are no longer two separate models. Such a relat ionship is based on the results presented in [9], 2.3 Simulation Models and Parameters To evaluate the impact o f w ind b low ing through fol iage on system throughput, we have simulated the performance o f the downl ink o f a single ce l l o f a T D M A mode 802.16 S C a system using M A T -L A B . Inter-cell interference is not considered. The B S is at the centre o f the ce l l w i th three 120° direct ional antennas on the tower and SSs use 30° direct ional antennas. The SSs are either un i -fo rmly distributed in the ce l l for ce l l performance or un i formly distributed at the edge o f the ce l l for ce l l edge performance. The m a x i m u m frequency o f the Dopp ler effect is un i formly distributed between 2 H z to 3 H z . Refer to Table 2.1 for detailed s imulat ion models and parameters. Note that our simulat ions account only for the effect o f S N R on throughput and do not account for other M A C and Network layer effects. We use Erceg 's suburban model as the s imulat ion path loss model . A l l three terrain types, wh i ch are h i l l y wi th moderate-to-heavy tree density (terrain type A ) , h i l l y w i th l ight tree density or flat w i th moderate-to-heavy tree density (terrain type B ) , and flat w i th l ight tree density (terrain type C ) , have been considered. The decibel path loss is given by [17] PL = m + s 16 (2.3) Table 2.1: Parameters o f the simulated ce l l C e l l radius 3 k m Frequency 2.4 G H z Bandwid th 3.5 M H z Phys ica l layer overhead 10% Fade margin 10 d B Base station antenna height and gain 40 m, 15 d B Subscriber station antenna height and gain 2.5 m, 16 d B Path loss model Erceg 's suburban model [17] Fade channel R icean channel Use r terminal noise figure 5 d B Equivalent noise power in channel B W -103.8 d B m Table 2.2: Numer i ca values o f path loss mode l parameters [17] Model Parameters Terrain Category A (H i 1 ly/Moderate-to-Heavy Tree Density) Terrain Category B (Hilly/Light Tree Density or Flat/Moderate-to-Heavy Tree Density) Terrain Category C (Flat/Light Tree Density) a 4.6 4.0 3.6 b 0.0075 0.0065 0.0050 c 12.6 17.1 20.0 where m gives the median value o f the path loss for a given distance d f rom the B S and s describes the shadowing effect. Med ian path loss m and shadowing effect s is defined by the fo l low ing equations, m = 20 l o g 1 0 ( 4 7 r d 0 / A ) + 1 0 7 l o g 1 0 ( d / d n ) (2.4) s = ya (2.5) where do is a given c lose- in reference distance," A is the Wavelength in m, y is a zero-mean Gauss ian variable o f unit standard deviat ion, a is the standard deviat ion o f s, and 7 is the path-loss exponent w i th 7 = (a — bhb + c/hf,) where is the height o f the B S in m, and a, b, c are the constants dependent on the terrain category as described in Table 2.2 [17]. To further differentiate the three types based on tree density, we use a vegetation index to describe the fract ion o f the area covered by trees. The vegetation indices for terrain type A , terrain type B , and terrain type C are 0.9, 0.5, and 0.1, respectively. We use the model described in Sect ion 2.2.3 as the K- factor mode l . The parameters are taken f rom [8 ,9 , 12, 17]. The seasonal factor Fs is set to be 1 representing summer wi th leaves 17 in order to show the biggest effect, height factor is calculated by ( f o / 3 ) 0 , 4 6 wi th h = 2 . 5m , beamwidth factor Fb is set by ( 6 / 1 7 ) - ° - 6 2 w i th b = 30, K0 = 10, 7 = - 0 . 5 , as = - 0 . 4 5 , and av = —0.75. Shadowing effect s is lognormal distributed wi th standard deviat ion to be 10.6 d B for terrain type A , 9.6 for terrain type B , and 8.2 for terrain type C . W i n d speed v is set to 0 m/s for ca lm weather, 2 m/s for low winds, and 6 m/s for h igh winds. The vegetation factor t is 1 for locations covered by trees and 0 for locations without trees. The user channel is generated using the M A T L A B code presented by B a u m in Append ix B o f [11]. The channel coefficients are generated by the method o f f i l tered noise wi th the specif ied distr ibution and spectral power density. A set o f complex zero-mean Gauss ian distributed numbers is generated wi th a variance o f 0.5 for the real and imaginary part, result ing in an average power o f 1. Th is y ie lds a normal ized Ray le igh distr ibution for the magnitude o f the complex coefficients. Fo r R icean distr ibut ion, the power o f the complex Gaussian part a is calculated by a2 = P/(K + 1) and the power o f the constant part m is determined by | m | 2 = PKj(K +1), where K is the R icean K-factor. The power spectral density funct ion is given by In order to get a set o f channel coefficients wi th the power spectral density funct ion denned above, we correlate the or ig inal coefficients w i th a filter whose ampli tude frequency response is \H(f)\ = \/S(f). A c c o r d i n g to Nyqu is t theorem, the coefficients are sampled at a frequency o f 2 / m , because there are no frequency components higher than fm. A n d f inal ly, the total power o f the filter is normal ized to 1. The B S communicates wi th the SS using the rates adapted to the user channel condit ions. The transmission between the B S and the SS is assumed to be error-free. Table 2.3 gives the S N R requirement for each modulat ion and coding scheme. The SSs share the communicat ion channel in a round robin fashion. I f the B S transmits packets to a SS whose received S N R is lower than the lowest requirement, i.e., 6.4 d B , the transmitt ing packets are considered to be lost. A l l SSs are assumed to be back logged at a l l t imes. Each s imulat ion lasts for 5 minutes, i.e., 30,000 t ime slots, w h i c h is suff iciently long to avoid any specif ic scenarios. 1 - 1 . 7 2 ( / / / m ) 2 + 0 . 7 8 5 ( / / / m ) 4 , \f/fm\ < 1 0 , \f/fm\ > 1 18 Table 2.3: S N R requirement for modulat ion and coding schemes Modu la t ion C o d i n g Rate Receiver S N R (dB) B P S K 1/2 6.4 Q P S K 1/2 9.4 Q P S K 3/4 11.2 1 6 - Q A M 1/2 16.4 1 6 - Q A M 3/4 18.2 6 4 - Q A M 2/3 22.7 6 4 - Q A M 3/4 24.4 2.4 Simulation Results 2.4.1 The Influence of Wind-Induced Fading on the Performance of Systems with Different Terrain Type To simulate the wind- induced fading on system performance, we simulated the system throughput for the three terrain types. To further study the effect on the performance o f both the ce l l and the ce l l edge, simulat ions have been performed for each case under ca lm weather, low w ind weather, and high w ind weather for al l three terrain types. F i g . 2.2 shows the system throughput as a funct ion o f vegetation index under different weather condit ions for both ce l l performance and cel l edge performance. W e can see f rom F i g . 2.2 that under ca lm weather when there is no w ind , the system through-put is almost the same under a l l three terrain type for both ce l l performance and ce l l edge perfor-mance. Under w indy weather condit ions, however, the system throughput goes down signif icant ly wi th the increase o f vegetation index. For example, under heavy w ind weather, the throughput difference o f ce l l edge users between 0.1 vegetation coverage and 0.9 vegetation coverage is over 10%. Furthermore, when a system is changing f rom ca lm weather condi t ion to w indy weather condi t ions, the system throughput also changes wi th the change o f w ind speed. For terrain type A , for example, the system throughput o f the ce l l edge degraded by 4 % when changing f rom ca lm weather to low w ind weather, and 7% when changing f rom low w ind to heavy w ind weather. The degree o f system throughput degradation is quite dependent on vegetation index, and the higher the 19 9.0 8.5 -8.0 -5- 7.5 -| 7.0 3 tx "f1 6.5 o H 6.0 5.5 5.0 4.5 • • a - + — o — Cell - Calm -Cell - Low wind — i - - Cell - Heavy wind -— o — Edge - Calm • Edge - Low wind - + - Edge - Heavy wind _ o — - — — + 0.1 (type C) 0.5 (type B) Vegetation Index 0.9 (type A) Figure 2.2: System throughput under different terrain type and weather condit ions. vegetation index, the greater the effect o f the w ind on throughput degradation. In our s imulat ion, the difference between the cel l performance under ca lm weather and heavy winds is less than 1% for terrain type C , but 6% for terrain type A . We also notice that ce l l edge users are more vulnerable to wind- induced fading than ce l l users. The performance degradation o f the ce l l edge is 11% for terrain type A , but only 6% for ce l l users. Th is is expected because ce l l edge users usual ly have a relatively lower received signal level than the average user. W i th greater w ind- induced fading at greater distances, the received signal o f ce l l edge users can easi ly be led to the non-transferable condit ions, i.e., lower than the lowest S N R requirement for transmission. 2.4.2 The Influence of Fade Margin on System Performance Fade margin, by wh ich a received signal level may be reduced without causing system performance to fal l be low a specif ied threshold value, is an important design parameter that provides for sufficient system gain to accommodate expected fading. A higher fade margin corresponds to a higher system cost, but offers greater protection against channel fading such as the wind- induced fading. In order to see how system performs wi th different fade margins, we simulate the system throughput o f 20 Fade margin Figure 2.3: System throughput wi th respect to fade margin. terrain type A for both the ce l l and the ce l l edge under different weather condit ions wi th respect to fade margin as shown in F i g . 2.3. Here, fade margin is the amount above the lowest received signal level requirement (6.4 dB) for the ce l l edge users. A s expected, system throughput increases wi th the increase o f fade margin both for ce l l users and cel l edge users. A n d also, w i th the increase o f fade margin, the throughput difference between ca lm weather and heavy w ind weather becomes smal ler and smaller. For ce l l users, for example, when the fade margin increases f rom 5 d B to 15 d B , and then to 30 d B , the performance difference between the two weather condit ions decreases f rom 7%, to 5%, and then to less than 1%. Th is suggest that w i th a h igh enough fade margin, the effect o f w ind- induced fading on system performance can be el iminated. Compared to ce l l users, ce l l edge users require a much higher fade margin in order to el iminate the w ind effect to the same degree, e.g., to make the throughput degradation to be less than 5%, we need a fade margin o f 15 d B for ce l l users, but 25 d B for ce l l edge users. Th is is not surprising because ce l l edge users experience higher path loss than ce l l users, to be immune f rom channel fading, a higher gain is required. 21 2.5 Conclusions W i n d b low ing through fol iage can lead to periods o f severe fading on mult ip le l inks wi th in point-to-mult i -point wireless communicat ions systems. V i r tua l ly a l l previous studies o f w ind- induced fading considered only ind iv idual wireless l inks. However, our pre l iminary observations indicate that the fading events on different l inks wi th in a ce l l may occur more or less simultaneously, albeit to vary ing degrees. We have proposed a K- factor model that describes wind- induced fading consider ing the correlat ion between fading events on mult ip le l inks in f ixed wireless systems to introduce the envi -ronmental changes to the propagation channel. Th is a l lows us to access the effects o f w ind-b lown fol iage on system throughput o f F B W A systems. Our s imulat ion results, wh i ch account only for the effect o f S N R on system throughput, show that w i th increases in one or both of: (1) the percentage o f areas covered by fol iage and (2) w ind speed increases, the system throughput decreases. For areas wi th high tree densities, when mov ing f rom the ca lm weather to heavy w ind condi t ion, the system throughput degradation cou ld be over 10% at the ce l l edge. Ou r s imulat ion results also show that wi th a high enough fade margin, the effect caused by w ind -b lown fol iage can be el iminated. O n the other hand, because a higher fade margin corresponds a much higher system cost, designing efficient radio resource management schemes may be more appropriate in mit igat ing such fading for some systems. However , few, i f any, exist ing radio resource management schemes account for the manner in wh i ch channel characteristics are affected by fading due to gusts o f w ind b low ing through fol iage. Development and evaluation o f schemes that account for this w i l l require that the proposed K- factor model o f such channel behaviour be refined based on extensive measurement data. 22 References [1] P. B . Papazian, G . A . Huf fo rd , R. J. Acha tz , and R. Ho f fman , "S tudy o f the loca l mult ipoint distr ibution service radio channel , " IEEE Transactions on Broadcasting, vo l . 43 , no. 2, pp. 175-184, 1997. [2] A . Ka j iwa ra , " L M D S radio channel obstructed by fo l iage," in Proc. of IEEE International Conference on Communications, vo l . 3, 2000, pp. 1583-1587. [3] J . C . R. D a l B e l l o , G . L . Siqueira, and H . L. Ber ton i , "Theoret ica l analysis and measurement results o f vegetation effects on path loss for mobi le cel lu lar communicat ion systems," IEEE Transactions on Vehicular Technology, vo l . 49, no. 4, pp. 1285-1293, 2000. [4] S. Perras and L. Bouchard , "Fad ing characteristics o f R F signals due to fol iage in frequency bands f rom 2 to 60 G H z , " in Proc. of IEEE 5th International Symposium on Wireless Personal Multimedia Communications (WPMC 2002), vo l . 1, 2002, pp. 2 6 7 - 2 7 1 . [5] A . Domazetov ic , L . J . Greenstein, N . B . M a n d a y a m , and I. Seskar, "Es t imat ing the Doppler spectrum o f a short-range f ixed wireless channel , " IEEE Communications Letters, vo l . 7, no. 5, p p . 2 2 7 - 2 2 9 , 2003. [6] P. L e d l , P. Pechac, and M . Mazanek , "T ime-ser ies predict ion o f attenuation caused by trees for f ixed wireless access systems operating in mi l l imeter waveband," in Proc. of Antennas and Propagation. (ICAP 2003), vo l . 2, 2003, pp. 646-649 . [7] E . R. Pelet, J . E . Salt, and G . Wel ls , "Ef fec t o f w ind on fol iage obstructed l ine-of-sight channel at 2.5 G H z , " IEEE Transactions on Broadcasting, vo l . 50, no. 3, pp. 2 2 4 - 2 3 2 , 2004. [8] M . H . H a s h i m and S. Stavrou, " W i n d influence on radio waves propagating through vegetation at 1.8 G H z , " Antennas and Wireless Propagation Letters, vo l . 4, pp. 143 - 146, 2005. [9] D . Crosby, V. S. Abhayawardhana, I. J . Wasse l l , M . G . B r o w n , and M . P. Sel lars, " T i m e var iabi l i ty o f the fol iated f ixed wireless access channel at 3.5 G H z , " in Proc. of IEEE 61st Vehicular Technology Conference. (VTC 2005-Spring), vo l . 1, 2005, pp. 106-110. 23 [10] N . N a z and D . D . Falconer, "Tempora l variations characterization for f ixed wireless at 29.5 G H z , " in Proc. of IEEE 51st Vehicular Technology Conference. (VTC 2000-Spring), vo l . 3, 2000 ,pp . 2178-2182 . [11] V. E rceg et a l , "Channe l models for f ixed wireless appl icat ions," IEEE 802.16 Working Group, 2003. [12] L . J . Greenstein, S. Ghassemzadeh, V. Erceg , and D. G . M i c h e l s o n , " R i c e a n K-factors in narrowband f ixed wireless channels: Theory, experiments, and statistical models , " in Proc. of International Symposium on Wireless Personal Multimedia Communications. (WPMC99), 1999. [13] M . O . A l - N u a i m i and R. B . L. Stephens, "Measurements and predict ion model opt imisat ion for signal attenuation in vegetation media at centimetre wave frequencies," in Proc. of IEE Microwaves, Antennas and Propagation, vo l . 145, no. 3, 1998, pp. 201 -206 . [14] M . Ab ramow i t z and I. Stegun, Handbook of Mathematical Functions. N e w York : Dover , 1964. [15] H . Taub and D. L . Sch i l l i ng , Principles of Communications Systems. N e w York : M c G r a w -H i l l , 1971. [16] C . G . Gunther, " C o m m e n t on 'estimate o f channel capacity in rayle igh fading environment ' , " IEEE Transactions on Vehicular Technology, vo l . 45 , no. 2, pp. 4 0 1 - 4 0 3 , 1996. [17] V . Erceg , L . J . Greenstein, S. Y . Tjandra, S. R. Parkoff, A . Gupta , B . K u l i c , A . A . Jul ius, and R. B i a n c h i , " A n empir ica l ly based path loss model for wireless channels in suburban environments," IEEE Journal on Selected Areas in Communications, vo l . 7, no. 7, pp. 1205 -1211,1999. [18] M . E . Crove l la and A . Bestavros, "Se l f -s imi lar i ty in wor ld w ide web traffic: Ev idence and possible causes," IEEE/ACM Transactions on-Networking, vo l . 5, no. 6, pp. 835 -846 , 1997. 24 Chapter 3 Opportunistic QoS Enhanced Scheduler for Real-time Traffic in Fixed Wireless Communication Systems 3.1 Introduction F ixed wireless systems, such as the ones that comply to the I E E E 802.16 standard, are expected to prov ide a broad range o f services, each wi th high qual i ty-of-service (QoS) , to users. A l t hough the f ixed environment is generally less harsh than the mobi le environment, the expectations for re l iab i l -ity and performance are also higher. Un l i ke their wi re l ine counterparts, wireless systems must cope wi th t ime-vary ing, location-dependent, and relatively expensive communicat ion channels. Th is re-quires the al locat ion o f resources to be efficient in order to provide users wi th satisfactory services. Furthermore, real-t ime appl icat ions, such as voice, v ideo/audio streaming, require data to be sent w i th in a short per iod o f t ime, wh i ch introduces an addit ional level o f dif f iculty in channel al locat ion and packet schedul ing. In the suburban neighbourhoods, w ind b lown fol iage is one o f the main factors that cause fading on f ixed wireless channels. Wh i l e signal strength tends to remain relatively constant when 1 A version of this chapter will be submitted for publication. The material in this chapter is largely based on Yonghong Zhang and David G. Michelson, "Opportunistic QoS Enhanced Scheduler for Real-time Traffic in Wireless Communica-tion Systems", accepted for presentation at IEEE Vehicular Technology Conference (VTC 2006-fall), Montreal, Canada, Sept. 2006. 25 there is no w ind , the onset o f w ind and movement o f leaves and branches causes the signal to fluctuate at rates between 0.1 and 10 H z . The statistics tend to fo l low a R icean distr ibution wi th K- factor somewhat proport ional to the amount o f vegetation in the v ic in i ty o f the user terminal and inversely proport ional to the w ind speed [1,2]. A l though deeper fading cou ld cause higher packet error ratio, the higher f luctuation also introduces opportunit ies. In a t ime-slotted system where only one user can transmit dur ing any t ime instant, schedul ing the user for t ransmission only around his/her peak channel qual i ty not only avoids any transmission dur ing users ' deep fades, but also possib ly results in higher overal l system throughput when using appropriate adaptive modulat ion and cod ing schemes because the higher f luctuation dur ing w indy condi t ion indicates higher peak values for affected users. Such approach is not new and is termed mult i -user diversity. First introduced by K n o p p and Humble t [3], mult i -user diversity al lows only the user w i th the best channel to transmit at any t ime so as to improve overal l system throughput. The investi-gat ion for up l ink transmissions in a single ce l l has showed that this scheme can increase the total capacity dramatical ly. The M a x R a t e rule, wh i ch schedules packet to the user w i th the best reported channel quality, has been adopted by 3 G P R However, these schemes are proposed for delay-tolerant appl icat ions and do not consider any fairness between users. The Proport ional Fa i r (PF) packet scheduler [4], on the other hand, tries to provide greater fairness than the above schemes and a better throughput than R o u n d R o b i n ( R R ) , although it may not provide a good overal l system throughput. The scheduler proposed in [5] is throughput opt imal under the constraint o f t ime sharing between users so as to provide long-term fairness. A l l the above ment ioned mult i -user diversity schedulers are appropriate for data traffic where fairness is prov ided between users either in the t ime or resource usage domain. O n l y a few studies have exploi ted the t ime-vary ing nature o f the channel to max im ize system throughput for delay-sensit ive traffic. The exponential rule ( E X P ) [6] schedules packets main ly based on the chan-nel quali ty and packet delay, and its superiority over the M a x R a t e rule, modi f ied largest weighted delay first ( M - L W D F ) rule [7] and P F has been conf i rmed by an evaluation o f a mixture o f real-t ime and non-real-t ime data performed in [8]. The U ' R rule [9] is intended for delay-sensit ive packet schedul ing and is composed o f the M a x R a t e rule and the user ut i l i ty funct ion, wh i ch is a decreasing funct ion o f packet delay. However, these opportunistic schedulers al l judge the urgency o f a packet based on packet 26 delay. L o n g packets that need a signif icant amount o f t ime for transmission are at a disadvantage in meeting their deadlines. Meanwh i l e , they d id not provide any mechanism for preventing the transmission o f packets that w i l l have expired before they are del ivered, wh i ch results in wasted bandwidth. A l though some schedulers have considered discarding expired packets, they are pro-posed for specif ic traffic, such as v ideo [10]. Furthermore, none o f the proposed opportunistic schedulers for real-t ime traffic has cons id-ered fair degradation among users when the system cannot satisfy every user's requirement. W h e n heavy w ind felt over a large area, the performance o f the affected system cou ld be degraded [11], such that it wou ld lead a fu l ly loaded system to the overloaded status. In such cases, not every packet o f the real t ime users is able to meet its delay requirement. I f we do not consider fair degradation among real-t ime users, since they can only tolerant certain amount o f packet dropping or delay, some o f the users cou ld experience unbearable service when the system is overloaded. A l though the study in [ 12] considered fair degradation in a wireless L A N system, its computat ional complex-ity is very h igh, and it does not consider mult i -user diversity to max im ize system throughput. In this chapter, we propose a new scheduler wh i ch we refer to as an opportunist ic Q o S enhanced scheduler ( O Q E S ) for real-t ime traffic. It: (1) exploits mult i -user diversity for max im i z i ng system throughput, (2) provides a better mechanism for meeting deadlines, (3) proact ively discards packet that are go ing to be dropped in order to prevent system resources f rom being wasted, and (4) ensures fair degradation among users for better performance when the system is overloaded. We organize the remainder o f this chapter as fo l lows. Sect ion 3.2 describes the proposed scheduler. Sect ion 3.3 explains the selection o f parameters for implementat ion. Sect ion 3.4 in -troduces performance measures. In Sect ion 3.5, we expla in s imulat ion environment and give the simulat ion results o f the performance o f O Q E S . In Sect ion 3.6, we draw conclusions. 3.2 Opportunistic QoS Enhanced Scheduler Rea l t ime appl icat ions such as video or audio streaming require that each o f its packets be sent w i th in a specif ic t ime frame. Otherwise, the packet cou ld be dropped and the user wou ld probably be left unsatisf ied. O n the other hand, the fact that wireless communicat ion channel changes over t ime makes 27 it desirable to exploi t the mult i -user diversity property o f the channel to use the scarce wireless resources more efficiently. Moreover , wi th the help o f the buffering abi l i ty at the receivers, some o f the real-t ime appl icat ions, such as audio/v ideo streaming, can now tolerate longer delays than before, and the requirement for j i tter is also loosened, wh ich leaves room for max im i z i ng system throughput. 3.2.1 The Scheduling Rule Cons ider the downl ink o f a packet-switched wireless communicat ion system, wh i ch is t ime-slotted wi th N t ime slot. There is a base station communicat ing wi th K users randomly located in the cel l . Each user has an established connect ion wi th the base station denoted as session k, and k € { 1 , 2 , K } . The base station maintains one queue for each user session, whose packets are to be scheduled wi th in t ime slots. A t t ime slot n, the arr iv ing t ime o f the head o f l ine ( H O L ) packet o f the queue for user session k is denoted by h\. Packet i o f user session k arrives at t ime slot a\, and the last bit o f the packet leaves the base station at t ime slot b\. The transmission channel o f the users changes over t ime. Ei ther the base station or the user tracks the channel signal to noise ratio ( S N R ) and feed back the channel qual i ty to the other party. The base station schedules packets to the users using the data rate that adapted to the channel quality. The data rate for user session k at t ime slot n is denoted by rj?. The goal o f the targeted scheduler is to successful ly transmit packet w i th in required t ime wi th highest possible data rate, so as to meet higher system throughput and in return serve more users. Theorem 3.2.1. LetU — {U\,U2,---UN) be the scheduleduser vector ofthe system, Un represents the users whose HOL packets or part of the packets being transmitted at time slot n, and n £ { 1 , T V } . Suppose error free transmission, the scheduler that satisfies \fk,\/i,al+dk>b% (3.1) will achieve maximum throughput when Vn,\/k,k G Un,rl = m&x(rft ,rft+1 k hnk+dk (3.2) 28 Proof. Suppose the number of packets arrived for user k is M\., the number of packets successfully sent out to user k is m ^ , the length of the ith packet of user k is l\, and the time spent is t\, the throughput of the system is1 Z^ fc=i l-,i=i lk EK v^ mfc ,i k=\ 2^i=i Lk where the numerator represents the total number of bits sent and the denominator denotes the time spent. Satisfying (3.1), each packet is sent between (a\, blk]. Without losing generality, assume for any packet, TV > b\. Then all arrived packets are successfully sent, and the total bits sent by the base station is a fixed number denoted by L, which is the sum of the length of all arrived packets. The throughput of the system can be written as Z^fc=l L-,%=\ lk Suppose user fc's ith packet is sent out at time slot n, the rate used is then r£, and conse-quently, t\ = l\/r^. Based on (3.2), r£ is the maximum possible rate that packet i can achieve, thus t\ is the minimum possible time that the system spent to send the packet out. Since each of the term inside the summation is a minimum, the denominator of (3.3) will reach its minimum. The numerator being fixed, the system throughput described in (3.3) will reach its maximum. • In practice, the conditions in theorem 3.2.1 are quite difficult to achieve. Because it is either difficult to predict future channel conditions or the expense of predicting channel quality is high, we cannot easily get the maximum achievable rate within the required time frame. What we can do, however, is to wait for a high quality channel state until the packet has to be sent out to meet its deadline. We refer to the waiting period as flexible time, and the period that the packet has to be transmitted as urgent time. The strategy can be expressed as a x g m a x £ / ? / f c n ( r ) (3.4) where a rg max/c refers to the user whose ( T ) is the maximum among all users. U% and / £ ( T ) are the relative rate and urgency value of user k at time slot n. T, the number of time slots left to 'A packet is said to be fragmented before transmission when it cannot be sent within the remaining time in the current time slot. The remaining bits of the packet stay in the queue and the packet length is updated. Here, each fragmented packet is counted as one packet. 29 reach the user's H O L packet's deadline, can be expressed as r = dk - lk/(fkT) - (n - hi) where Ik is the remaining length of H O L packet for user k, r"k is the average rate of user k in a past window, and T is the length of one time slot. The relative rate Uk is the rate relative to the maximum rate Rknax that user k has reached in a past window. It is denned by ( /? rj? = RTax,f3 > 1 U%={ • (3-5) [ 1 r l ^ R ^ The urgency value fk(r) describes how urgent the H O L packet of session k is, in other words, it shows how close the H O L packet is to its deadline. When the H O L packet is within the flexible time denoted by ck, i.e., r > dk — Ck, the urgency value is a positive constant, i.e., a; while when it is in the urgent period, i.e., r < dk — ck, the urgency value is higher than a , and the less time left (smaller r ) , the higher the urgency value to show its urgency, which is described by the urgency function gk(r). The urgency value is denned by { a r > dk — Ck OL + 9k{r) T < dk Ck L e m m a 3.2.2. Assume one time slot is long enough for transmitting multiple packets, and for all packets 3i,ri = Rrx,hnk<i<hnk+ck, the scheduling rule that is given by (3.4) will achieve maximum throughput. Proof. Since one time slot is long enough to transmit all packets whose designated users reach their maximum rate, and for any packet, RJ^ax exists during flexible time, all packets wi l l be scheduled at their corresponding users' maximum rate within flexible time. Based on Theorem.3.2.1, it wi l l reach maximum throughput. • 3.2.2 Proactive Packet Discarding Mechanism Some packets are very big and cannot be successfully transmitted within one time slot. If the packet misses its deadline at the end of transmission, the whole packet could be discarded. For real-time 30 appl icat ions, such as v ideo conference, the packet is o f no use after its deadline. S imp ly schedul ing every packet regardless o f its status could result in wasted bandwidth, wh ich should be avoided. For these types o f traffic, we propose a s imple packet discarding mechanism wh ich discards packets when T , the t ime left for meeting deadline, is equal to or smal ler than 0. 3.2.3 Fair Degradation E v e n wi th perfect admiss ion control , it is sti l l possible for a system to go into the overloaded state. For example, when strong w ind come across a large area o f a fu l ly loaded f ixed broadband wi re-less access system, the system cou ld be overloaded because o f the degraded system capacity [11]. W h e n a system is overloaded, it is not possible for every real-t ime packet to be scheduled on t ime. However, i f we manage to control each user's packet delay v io la t ion ratio w i th in a certain degree denoted by 8k, i.e., the highest ratio that user k can tolerate for packet delay v io la t ion, al l users cou ld be able to remain in the system wi th satisfying Q o S . We use a v io lat ion bucket s imi lar to the leaky bucket approach to achieve fair degradation due to its s impl ic i ty and the abi l i ty to achieve short-term fairness [13]. Each user has a v io lat ion bucket to ho ld the expired packets. The leaking rate is fk8k, and the size o f the bucket is rk8ko-k, where ak is the t ime that user k can tolerate for delay requirement v io lat ion. I f the bucket is fu l l , no more packets shal l miss their deadlines. W h e n the bucket is nearly fu l l , and the corresponding user is in the urgent t ime per iod, the user shal l get higher transmission opportunity over others. We use an exponential term to express how fu l l a user's v io lat ion bucket is where s£ denotes the number o f the bits in the bucket at t ime slot n, and 7 is a non-negetive number named adjustment factor. W h e n the bucket is nearly empty, the exponential term is close to 1, wh i le when the bucket is close to fu l l , the exponential term becomes much bigger to close to e7. Wi th the fair degradation mechanism, the t ime value funct ion equation (3.4) now is defined by ' a T > dk - Cfc U + 9k{T)Jk r < d k - c k fk(r) 31 3.3 Implementation of OQES To successful ly use O Q E S , several parameters need to be specif ied careful ly. 3.3.1 Flexible Time ck It is important to set an appropriate f lexible t ime. I f ck is too long, the room left for urgent t ime w i l l be too smal l to send the packet by its deadl ine; on the other hand, i f is too short, there w i l l be no room to wait for the m a x i m u m possible rate. To the extreme, when ck = 0 for a l l users, the urgency value o f the algor i thm becomes Earl iest Deadl ine First ( E D F ) rule, wh ich schedules user whose H O L packet has the earliest approaching deadline. The setting o f f lexible t ime depends on the type o f appl icat ion, e.g., for audio/v ideo stream-ing, wh i ch has buffer at the receiver, ck can be longer; whi le for constant rate traffic, e.g., voice appl icat ions that connected to the publ ic switched telephone network ( P S T N ) , ck should be very smal l . F lex ib le t ime should also be a funct ion o f the H O L packet length and system load. The longer the H O L packet, the more t ime it needs for transmission, and therefore the less flexible t ime should be a l lowed. W h e n the system is heavi ly loaded, there are higher chances for mul t ip le users to go to the urgent t ime per iod at the same t ime, wh i ch makes channel compet i t ion more intense for these users and results in longer wai t ing t ime. In such case, a longer ck is necessary in ensuring packets meeting their deadlines. O n the other hand, it is relatively easy for a user in urgent t ime per iod to qu ick ly gain the transmission opportunity in a low- loaded system, where ck cou ld be shorter. 3.3.2 Relative Rate Function [/£ and (3 In pract ice, the condit ions in L e m m a 3.2.2 may not always be satisfied. For example, the delay requirement may be too short to a l low m a x i m u m rate to be reached; there cou ld be times when no user reach its m a x i m u m rate; or mult ip le users reach their m a x i m u m rate at the same t ime, yet one t ime slot is not long enough to send a l l their H O L packets out. To deal wi th such imperfectness, we use the P F rule as the second condi t ion for setting relative rate. Thus equation (3.5) becomes 32 \ l+rnk/rk r%^Rrx Not ice that for L e m m a 3.2.2 to st i l l ho ld , parameter j3 should be b ig enough, so that the P F rule part wou ld not take over the relative max rate part. General ly , ft can be set to be the ratio o f the m a x i m u m rate to the m in imum rate o f the system. 3.3.3 Urgency Function gk(r) and a A s ment ioned, gk(r) is a posit ive decreasing funct ion, wh i ch should have much higher value for smal ler r. The value o f gk normal ly should increase exponential ly w i th the decrease o f r. Th is is to a l low users wi th more urgent packets to grab the channel qu ick ly regardless o f its data rate. Bes ides , users w i th higher pr ior i ty should have higher values than users wi th lower priority. Parameter a is the urgency value for users at their f lexible t ime. It shal l be a smal l posit ive number setting wi th respect to gk(l), the m a x i m u m value o f <7fc(r). For example, i f we set gk(r) = V7"2' fffe(l) w i u be 1 , and we can set a to be 0.1. In such case, the urgency value o f users at f lexible t ime is only 9 % o f that o f the users almost reaching their deadlines. We w i l l discuss the select ion o f the value o f a in details in later sections. 3.3.4 Adjustment Factor 7 Parameter 7 adjusts the level o f fair degradation. A higher 7 w i l l result in higher fairness, but less system throughput, because in order to give higher transmission chances to users wi th h igh packet delay v io la t ion ratio, users at better channel condit ions may have to give up their t ransmission op-portunity. O n the other hand, a lower 7 can lead to higher system throughput w i th worse fairness. Consequent ly, there is a tradeoff between system throughput and fairness. Deta i led discussion re-garding the select ion o f the value o f 7 w i l l be presented in later sections. 3.4 Performance Measures To evaluate the effectiveness o f a scheduler, both system throughput and packet delay should be con-sidered. Speci f ica l ly , for real-t ime traffic, delay requirement v io la t ion and fair degradation should 33 also be evaluated. 3.4.1 Effective Throughput Since for real-t ime traffic, packet cou ld be dropped when it violates the delay requirement, besides total throughput, we also consider effective throughput, wh ich do not account for dropped packets. 3.4.2 Normalized Packet Delay In terms o f packet delay, because different types o f users have different requirements, we consider the delay in respective o f its requirement, wh i ch is defined by [14] where qlk is the packet delay o f zth packet for user k, and M is the total number o f transmitted packets. A value o f less or equal to 1 means that on average the system meets packet delay deadlines. 3.4.3 Violation Factor In order to measure the degree o f v io la t ion, we define v io la t ion factor VF as 1 K k=i [ 0 v k < 5 k where vk denotes the percentage o f packets that violate the delay requirement for user k. The v io la t ion factor reflects how users are satisfied wi th the service. A n acceptable system should have a VF close to 0. 3.4.4 Fairness Index Fairness for real-t ime traffic has a different meaning than it does for data traffic. In the case o f data traffic fairness is measured wi th respect to user received throughput or resources. Because sat isfying delay requirement is more important than the throughput it receives, fairness for real-t ime traffic measures the ratio o f packets that miss their delay requirements. We use the ratio o f 34 the actual packet delay v io lat ion over the highest tolerable packet delay v io lat ion as the fairness measurement for the real-t ime user wh i ch is determined by s " (3.6) 1 v k < 5 k -In order to measure fairness o f the system, we use the fairness index denned in [15], wh ich is (s£i 0 A fairness value o f 1 indicates that the system is fair to a l l users, wh i le 0 means it is total ly biased 3.5 Simulation Results 3.5.1 Simulation Environment To evaluate the effectiveness o f O Q E S , we simulated the performance o f the downl ink o f one sector o f an I E E E 802.16 F B W A system [16] us ing M A T L A B . For compar ison, we also evaluated E X P , U ' R due to their suitabil i ty for delay sensitive traffic, and E D F , the opt imal solut ion for real-t ime traffic in wire l ine systems. The base station o f the s imulat ion system is at the centre o f the ce l l wi th three 120° d irec-t ional antennas on the tower. User terminals are equipped wi th 30° direct ional antennas, and are un i formly distributed throughout the ce l l . The path loss model is Erceg 's suburban model for ter-rain type A as described in [17]. The fast fading channel fo l lows a R icean distr ibution wi th fading characteristics as described in [18]. The max imum frequency o f the Dopp le r spectrum, as denned in the s imulat ion code suppl ied by I E E E 802.16, is un i fo rmly distributed between 2 and 3 H z . Refer to Table 3.1 for a l ist o f the s imulat ion parameters. The base station communicates wi th the users using the rates adapted to the user channel condit ions. The transmission between the base station and the user is assumed to be error-free. Table 3.2 gives the S N R requirement for each modulat ion and cod ing scheme. W h e n a user's received S N R is lower than the lowest requirement, i.e. 6.4 d B , no transmission w i l l be scheduled for the user. In terms o f user traffic, we consider vo ice, v ideo, and web browsing. The voice traffic is s imulated by the O N - O F F mode l [19]. The packet stream is modeled by arrivals at f ixed intervals 35 Table 3.1: S imulat ion models and parameters C e l l radius 3 k m Frequency 2.4 G H z Bandwid th 7 M H z Phys ica l and med ium access control layer overhead 18% Base station transmission power 1 0 W Base station antenna height and gain 40 m, 15 d B Use r terminal antenna height and gain 2.5 m, 1 7 d B Path loss model Erceg 's suburban mode l [17] M e a n o f locat ion variabi l i ty 2.3 d B Standard deviat ion o f locat ion var iabi l i ty 10.6 d B Fade channel R icean channel User terminal noise figure 5 d B Equivalent noise power in channel B W -100.5 d B m Table 3.2: S N R Requirement for modulat ion and cod ing schemes Modu la t i on Cod ing Rate Receiver S N R (dB) B P S K 1/2 6.4 Q P S K 1/2 9.4 Q P S K 3/4 11.2 1 6 - Q A M 1/2 16.4 1 6 - Q A M 3/4 18.2 6 4 - Q A M 2/3 22.7 6 4 - Q A M 3/4 24.4 36 o f 16 ms dur ing talk spurts ( O N time) and no arrivals dur ing si lences ( O F F time). O N t ime is exponent ial ly distributed wi th mean 352 ms, and O F F time is exponent ial ly distributed wi th mean 650 ms. The dig i ta l ized voice data is 64 K b p s , and each packet is 128 bytes long. V ideo traffic is s imulated us ing the s imple I P B composite model introduced in [20]. W e simulate the frames o f Star Wars. One frame is generated every 40 ms. The mean length o f the packet is 9750 bytes, and is synthesized by combin ing three sel f s imi lar processes in a way s imi lar to the Group o f Pictures ( G O P ) structure. The sel f s imi lar processes adopted above are generated using the algor i thm given in [21]. For web-browsing traffic, we use the traffic model described in [22]. A l l users are act ively browsing the Internet. Fo l l ow ing each active browsing per iod, there's a reading t ime wh ich is geometr ical ly distributed wi th a mean o f 3 seconds. Dur ing the active t ime, there are Npc packet cal l requests wi th packets in each packet ca l l . Npc is geometr ical ly distributed wi th a mean o f 5, and is also geometr ical ly distributed wi th a mean o f 25. The size o f the packets is Pareto distr ibuted, the Pareto shape factor a is 1.1, and the m in imum packet size is 40 bytes. The packet interarrival t ime is geometr ical ly distributed wi th a mean o f 3.9 ms. The ratio o f vo ice, v ideo and web traffic is 15%, 4 6 % , and 3 9 % , respectively. The delay requirement is 100 ms for voice users, 200 ms for v ideo users, and 2 s for web-browsing users. De layed packets o f voice and video users w i l l be dropped, but stay in system wai t ing to be scheduled for web-browsing users. The v io lat ion al lowance 5 is 0.02, 0.05 and 0.10 for vo ice, v ideo, and web-browsing, respectively. Pr ior i ty is 3, 2 and 1 for vo ice, v ideo and web-browsing users, respectively. In order to test the system under fu l ly loaded condi t ion, we have implemented a s imple admiss ion control scheme. Whenever a new user session asking for admiss ion, the scheme w i l l look at the status o f the system buffer wh ich is the only place to ho ld un-transmitted user packets. I f the buffer is not fu l l , the user w i l l be admitted, otherwise, it w i l l be refused. Simulat ions last for 5 minutes, i.e., 300,000 frame t ime, wh ich is considered to be long enough to avoid any specif ic scenarios. A s for the parameters in O Q E S , we use ck = dk — (1 - log(5fc))Zfc/(rj;T) — qk as flexible t ime wi th q k representing average packet delay for user k. Urgency funct ion ff/c(r) — p t / T 2 , where Pk denote priority, a is set to 0.1, (3 is 4.5, and 7 is 0.3. 37 User Number Figure 3.1: System throughput wi th respect to system load. 3.5.2 Performance under Different System Load We ran simulat ions for each o f the four schedulers w i th 225, 250, 275, 300 and 325 users represent-ing different system loading, where less than 300 users represents moderate system load and over 300 users shows heavy system load. N o admission control is implemented in these simulat ions. F i g . 3.1 shows the system throughput and F i g . 3.2 shows the effective throughput for differ-ent schedulers. We can see clearly that the system throughput for the three opportunist ic schedulers is quite simi lar, al though O Q E S is s l ight ly better than E X P and U ' R for 300 users and 325 users. The system throughput for E D F is s imi lar w i th the opportunistic schedulers when the system load is moderate, but increases much slower when the system load becomes heavier. No t i ce that the throughput increase from 275 users to 300 users is much more signif icant than that f rom 225 users to 250 users or f rom 250 users to 275 users, the reason is that when increasing the user number to 300, a v ideo user has jo ined the system whose data rate is over 80 times o f either voice users or web-browsing users. In terms o f effective throughput, O Q E S performs better than other schedulers no matter how many users there are. W h e n the system load is not heavy, the difference between O Q E S 38 User Number Figure 3.2: Effect ive throughput w i th respect to system load. and other schedulers are not signif icant; wh i le when the load is heavy wi th more than 300 users, the effective throughput o f O Q E S st i l l increases steadily as the number o f user increases, but the effective throughput o f other schedulers drops quick ly , wh ich makes O Q E S outstanding f rom others. The reason that E X P , U ' R , or E D F drops at heavy system load is as fo l lows: when the system is heavi ly loaded, not al l packets can be handled on time due to the l imitat ion o f the system capacity, without a proactive packet d iscarding mechanism, part o f the system bandwidth has been wasted for transmitt ing delayed packets for v ideo and voice users. No rma l i zed packet delay is shown in F i g . 3.3. W h e n the system load is moderate, a l l sched-ulers provide comparable good service. However, when the system load is heavy, only O Q E S is be low 1, wh i ch means that the other schedulers cannot meet packet delay deadlines in an average sense. In other words, the system using either E X P , U ' R , or E D F cannot support more than 300 users wi th sat isfying Q o S . F i g . 3.4 shows the v io lat ion factors for these schedulers. Under moderate system load, the schedulers perform good wi th VF close to 0. W h e n the system is heavi ly loaded, the average v io la t ion beyond m a x i m u m tolerable al lowance for O Q E S is much less than other schedulers, wh ich indicates that the users in system using O Q E S is much more satisfied than that in system using E X P , 39 275 User Number Figure 3.3: No rma l i zed Packet De lay wi th respect to system load. o > 275 User Number 300 325 Figure 3.4: V io la t ion Factor w i th respect to system load. 40 1.0 0.8 0.6i 0.4 0.2 1.2 0.8 0.6 0.4 0.2 225 250 275 User Number 300 325 Figure 3.5: Fairness index wi th respect to system load. U ' R , or E D F . Fairness is shown in F i g . 3.5. Fairness decreases wi th the increases o f the system load. Du r ing moderate system load, a l l algori thms except for U ' R are fair to most o f the users wi th fairness index to be more than 0.9. O Q E S and E X P are 100% fair to al l o f their users wi th fairness index to be 1. However, when the system load becomes heavy, on ly O Q E S maintains high fairness to the users. Other schedul ing schemes can no longer maintain good fairness. W h e n the system is moderately loaded, a l l four schedulers perform we l l . However , when the system is heavi ly loaded, the difference between O Q E S and other schedulers becomes signif icant. Th is is because when there are less users in the system, there is extra bandwidth available for trans-mit t ing users data, so the cleverness o f the schedul ing algor i thm wou ld not be obvious. However, when the number o f users in the system reaches 300, almost no bandwidth is left over. In such cases, O Q E S wh ich tries to max im ize system throughput wh i le ensuring meeting the Q o S requirements o f . the users, performs much better than the others. Th is indicates that O Q E S can support more users w i th satisfactory service than other schedulers, wh ich suggests that us ing O Q E S can achieve higher system capacity in terms o f the number o f users a system can support w i th certain Q o S . 41 3.5.3 Performance Evaluation under Wind-Induced Fading Because wind- induced fading is one o f the main factors that contributes to the t ime-vary ing fading channel in f ixed wireless systems, we performed another type o f s imulat ions to determine how the schedulers perform under different weather condit ions. We considered three types o f weather condit ions: i.e., ca lm weather, low w ind , and heavy w ind wi th w ind speeds o f 0 m/s, 2 m/s, and 6 m/s, respectively. The K-factor model uses the model proposed in Chapter 2, where seasonal factor Fs is 1, height factor Fh is calculated by ( / i / 3 ) 0 4 6 w i th h = 2 . 5m , beamwidth factor Ft, is set by ( 6 / 1 7 ) " 0 - 6 2 w i th b = 30, K0 = 10, 7 = - 0 . 5 , as = - 0 . 4 5 , and av = - 0 . 7 5 . Shadowing effect s is lognormal distributed wi th standard deviat ion to be 10.6 d B . Vegetation factor t is 1 for locations covered by trees and 0 for no-tree locations. The area that covered by trees in the ce l l is assumed to be 90%. Because when system is l ight ly or moderately loaded, the system has extra bandwidth to handle the capacity shortage, the influence is usual ly only obvious when the system is heavi ly loaded, we simulated the system w i th a nearly fu l l load to evaluate how serious is the weather (wind) changes to the performance o f the system using different schedulers. F i g . 3.6 through F i g . 3.9 show the system throughput, v io lat ion factor, fairness index, and percentage o f satisfied user, wh i ch shows the percentage o f users whose overal l packet delay v io la -t ion is smaller than 8k-W h e n the system encounters ca lm weather, the system performs we l l us ing either O Q E S , E X P , U ' R , or E D F . The difference between the system throughput among the schedulers is not b ig , w i th on ly 6 % separating the best scheduler ( O Q E S ) and the worst scheduler ( E D F ) . The v io la t ion factor is low for a l l schedulers, wh i ch indicates a h igh percentage o f satisfied users as shown in F i g . 3.9 o f over 9 0 % for al l schedulers. W h e n the system encounters w indy condit ions, however, the performance o f the schedulers diverges. The performance o f the opportunistic schedulers only goes down sl ightly, wh i le E D F suffers signif icant degradation. For the system that uses E D F , the system throughput goes down by nearly 12%, the v io lat ion factor becomes extremely h igh at over 9, the fairness index drops over 3 0 % , and almost none o f the users are satisfied wi th service. Th is suggests that schedulers explo i t ing mult i -user diversity are more appropriate than those that implement the E D F fami ly o f schedulers when one carries real-t ime traffic in fixed wireless systems where wind- induced fading is the main channel impairment. 42 11.5 10.5 2 J 3 H 9.5 9.0 8.5 —o—O Q E S Exp - + - U R EDF Calm Low wind Heavy wind Figure 3.6: System throughput under different weather condit ions. 2.0 1.5 o > 0.5 0.0 Calm Low wind — o — O Q E S Exp - + - UR • - • - • E D F Heavy wind Figure 3.7: V io la t ion factor under different weather condit ions. 43 Calm Low wind Heavy wind Figure 3.8: Fairness index o f the system under different weather condit ions. 110 100 90 £ 80 1 70 £ 60 S 50 « c 40 £ 30 20 10 0 Calm Low wind Heavy wind Figure 3.9: Percentage o f satisfied user in the system under different weather condit ions. 44 A l s o notice that for both O Q E S and U ' R , when the system moves f rom ca lm to w indy cond i -t ions, except for a sl ight drop in throughput for less than 2 % , their v io lat ion factor and percentage o f satisfied user almost stays unchanged. Moreover , the fairness index o f O Q E S even goes up by over 10%, wh i ch indicates better fairness among users under w indy weather condit ions. Th is suggests that in F B W A systems, using appropriate schedulers, such as O Q E S , can mit igate w ind- induced fading to a large extent. 3.5.4 Performance of O Q E S with Different Parameters To show the influence o f the parameters in O Q E S to system performance, we simulated the system at a near fu l l load condi t ion wi th different parameters. The rules o f selecting appropriate values o f these parameters are also explained. Adjustment Factor 7 A s ment ioned in Sect ion 3.3.4, the select ion o f adjustment factor is a tradeoff between system throughput and fairness. To illustrate how adjustment factor influence the system performance, we have presented the system throughput in F i g . 3.10 and fairness index in F i g . 3.11 wi th different adjustment factor 7. We can see clearly from the figure that as 7 increases, the system throughput decreases, the deceasing is quite s low unt i l 7 reaches 0.32. O n the other hand, as 7 increases, the system fairness index increases. However, when 7 reaches 1, the system fairness begins to decrease wi th the increase o f 7. The reason for the decrease o f the fairness index wi th large 7 is as fo l lows: when 7 is b ig , the system concentrates so much on ensuring fairness that system throughput sacrif ices largely, and because the system is fu l ly loaded, the packets have to wait longer to be transmitted, wh i ch leads more users end up wi th higher than tolerable packet delay v io lat ion ratio. A c c o r d i n g to our fairness def ini t ion in (3.6) and (3.7), the more users receive higher than tolerable packet delay v io la t ion ratio (vk > 5k), the less fair the system is. Apparent ly , a reasonable range for 7 is between 0.032 and 0.32, w i th wh i ch both system throughput and fairness index are fair ly good. Not ice that the dependency o f the select ion o f the value o f 7 on parameters a and/or j3 is quite smal l . 45 9.6 9.41 9.2 a 9 0 n. 8.8 00 J2 H 8.4 8.2 8.0 o a = 0.1, (3= 10 -°— a = 0.1,P= 100 +• -a= l,p= 10 - • - a = l,p= 100 0 0.01 0.032 0.1 Y 0.32 3.2 Figure 3.10: System throughput wi th respect to adjustment factor 7. F igure 3.11: Fairness index wi th respect to adjustment factor 7. 46 Parameter a We show system throughput and v io lat ion factor as a funct ion o f parameter a in F i g . 3.12 and F i g . 3.13. F i g . 3.12 shows that system throughput increases wi th the increase o f a, and the increase becomes negl ig ib le when a is bigger than 3.2. However, wi th the increase o f a, v io lat ion factor increases, too, wh ich indicates that the overal l Q o S provided by the system has decreased. O n the other hand, very smal l a (e.g. smal ler than 0.32) also leads to higher v io la t ion factor. Therefore, an appropriate a shal l not be too b ig or too smal l . The selection o f a is also dependent on the value o f f3 and 7. For example, when (3 is 10 and 7 is 0.1, a good range o f a is between 1 and 3.2, w i th wh i ch v io lat ion factor reaches m in imum and system throughput is relatively good. W h i l e when (3 = 10 and 7 = 0.32, a higher range (1 < a < 10) is preferred. Bas ica l ly , w i th smal ler 7, a shal l be smal ler; and wi th smal ler (3, a shal l be bigger. However , because o f the smal l difference between performance, we can s imply set a to a reasonable range regardless o f the values o f (3 or 7. A reasonable range o f the value for a is between 0.32 and 3.2. Parameter (3 System throughput and v io lat ion factor as a funct ion o f (3 is shown in F i g . 3.14 and F i g . 3.15, respectively. We can see f rom the figure that system throughput increases w i th the increase o f [3. However , it does not mean that we should use a (3 as b ig as possible. H igher (3 c lear ly leads to higher v io lat ion factor, wh ich should be avoided. The value o f (3 between 3.2 and 10 yie lds the best result for both system throughput and v io lat ion factor. L i k e the selection o f the value o f parameter a, al though there are some dependencies o f the select ion o f (3 on adjustment factor 7 and parameter a, because the performance difference is not b ig , we can s imply set (3 to any value between 3.2 and 10. Parameter Selection Rules A s we showed in the above discussion, there are some dependencies on the select ion o f the values o f parameters a, (3, and 7. However, because the system performance is not very sensitive to the 47 Figure 3.12: System throughput wi th respect to parameter a. 0.045 0.040 0.035 0.030 0.025' 0.020 0.015 -o—p= 10, Y = 0 . 1 •a-- - p= 1 0 0 , 7 = 0 . 1 , +- - p= 1 0 , 7 = 0 . 3 2 -«- P= 1 0 0 , 7 = 0 . 3 2 _ _ +-0.1 0.32 3.2 10 32 Figure 3.13: V io la t ion factor w i th respect to parameter a. 48 CX = 0.1,Y=0.32 ° cc = 1,7=0.32 +• - a = 0.1,7=0.1 »- a = 1,7=0.1 100 Figure 3.14: System throughput w i th respect to parameter (3. 0.045 0.0151 1 L - — 1 1 3.2 10 32 100 P Figure 3.15: V io la t ion factor wi th respect to parameter [3. 49 values o f parameter a and (3, but sensitive to adjustment factor 7, we can first select 7 regardless o f the values o f a and (3, and then p ick the best value for a and ft based on the value o f 7. For example, say we set 7 to be 0.32, wi th wh ich both system throughput and fairness index are close to their best values. A n d then we set j3 = 10, w i th wh i ch both system throughput and v io lat ion factor are acceptable. W i t h 7 = 0.32 and (3 = 10, it is easy for us to set a to 3.2 based on F i g . 3.12 and F i g . 3.13, at wh i ch point the system throughput is close to the highest and the v io lat ion factor reaches the lowest. 3.6 Conc lus ions W e have shown that the Opportunist ic Q o S Enhanced Scheduler ( O Q E S ) introduced in this chapter offers better performance than E X P , U ' R , and E D F for real-t ime traffic. Th is is ma in ly because O Q E S tries to schedule packets w i th their best channel qual i ty dur ing their flexible time, wh i le concentrating on meeting deadlines dur ing packets' urgent time. The proactive packet discarding mechanism also plays a posit ive rule on the efficient usage o f the resource. Mu l t i -user diversity is an appropriate technique in designing schedul ing schemes for f ixed wireless systems wh ich are vulnerable to wind- induced fading. O Q E S , wh i ch exploi ts mult i -user diversity, is proved to be performed better than other schedulers in such systems because it both pro-vides fair degradation among real-t ime users and tries to max im ize system throughput in re l iev ing the degraded system capacity under such unfavoured condit ions. 50 References [1] M . H . Hash im and S. Stavrou, " W i n d influence on radio waves propagating through vegetation at 1.8 G H z , " Antennas and Wireless Propagation Letters, vo l . 4, pp. 143 - 146, 2005. [2] D. Crosby, V . S. Abhayawardhana, I. J . Wasse l l , M . G . B r o w n , and M . P. Sel lars, " T i m e var iabi l i ty o f the fol iated f ixed wireless access channel at 3.5 G H z , " in Proc. of IEEE 61st Vehicular Technology Conference. (VTC 2005-Spring), vo l . 1, 2005, pp. 106-110. [3] R. K n o p p and P. A . Humblet , " Informat ion capacity and power control in s ingle-cel l mul t i -user communicat ions," in Proc. of IEEE International Conference on Communications, vo l . 1, 1995, pp. 331 -335 . [4] A . Ja la l i , R. Padovani , and R. Panka j , "Da ta Throughput o f C D M A - H D R a H i g h Ef f ic iency-H i g h Data Rate Personal Commun ica t ion Wireless System," in Proc. of IEEE 51st Vehicular Technology Conference. (VTC 2000-Spring), vo l . 3, 2000, pp. 1854 - 1858. [5] X . L i u , E . K . P. C h o n g , and N . B . Shroff, "Opportunist ic transmission schedul ing wi th resource-sharing constraints in wireless networks," IEEE Journal on Selected Areas in Com-munications, vo l . 19, no. 10, pp. 2053-2064 , 2001. [6] S. Shakkottai and A . L . Stolyar, "Schedu l ing for mul t ip le flows sharing a t ime-vary ing chan-nel : The exponential rule," American Mathematical Society Translations, vo l . 207, 2002. [7] M . Andrews , K . Kumaran , K . Ramanan, A . Stolyar, P. Wh i t i ng , and R. V i jayakumar , " P r o v i d -ing qual i ty o f service over a shared wireless l ink," IEEE Communications Magazine, vo l . 39, no. 2, pp. 150-154, 2001. [8] S. Shakkottai and A . L. Stolyar, "Schedu l ing algori thms for a mixture o f real-t ime and non-real-t ime data in H D R , " in Proc. of 17th International Teletraffic Congress. (ITC), 2001, pp. 793 -804 . [9] P. L i u , R. Berry, and M . L . H o n i g , "Delay-sensi t ive packet schedul ing in wireless networks," in Proc. of IEEE Wireless Communications and Networking. (WCNC 2003), vo l . 3, 2003, pp. 1627-1632. 51 [10] J . Tang, L . Zhang, and C . - K . Siew, " A n opportunistic v ideo schedul ing algor i thm over shared wireless downl ink , " Computer Communications, vo l . 29, pp. 1917-1926, 2005. [11] Y . Zhang and D. G . M i che l son , " Impact o f wind- induced fading on the capacity o f point-to-mul t ipoint f ixed wireless access systems," in Proc. of ACM International Wireless Communi-cations and Mobile Computing Conference, 2006. [12] M . A d a m o u , S. Khanna , I. Lee , I. Sh in , and S. Z h o u , " F a i r real-t ime traffic schedul ing over a wireless L A N , " in Proc. of the 22nd IEEE Real-Time Systems Symposium, 2001, pp. 279 -288 . [13] A . K . Parekh and R. G . Gal lager, " A general ized processor sharing approach to f low control in integrated services networks: The single-node case," IEEE/ACM Transactions on Networking, vo l . 1, no. 3, pp. 344 -357 , 1993. [14] K . B . Johnsson and D . C . C o x , " A n adaptive cross-layer scheduler for improved Q o S support o f mult ic lass data services on wireless systems," IEEE Journal on Selected Areas in Commu-nications, vo l . 23, no. 2, pp. 334 - 343, 2005. [15] R. Ja in, D. C h i u , and W. Hawe , " A quantitative measure o f fairness and d iscr iminat ion for resource al locat ion in shared computer systems," DEC (Digital Equipment Corporation) Re-search Report TR-301, 1984. [16] " I E E E Standard for L o c a l and Metropol i tan A r e a Networks , Part 16: A i r Interface for F i x e d Broadband Wireless Access Systems," IEEE, 2004. [17] V . Erceg et a l . , " A n empir ica l ly based path loss mode l for wireless channels in suburban en-vironments," IEEE Journal on Selected Areas in Communications, vo l . 7, no. 7, pp. 1205 -1211,1999. [18] L . J . Greenstein, S. Ghassemzadeh, V. Erceg , and D. G . M i c h e l s o n , " R i c e a n K-factors in narrowband f ixed wireless channels: Theory, experiments, and statistical models , " Proc. of In-ternational Symposium on Wireless Personal Multimedia Communications. (WPMC99), 1999. [19] H . Heffes and D . Lucanton i , " A M a r k o v modulated characterization o f packet ized vo ice and data traffic and related statistical mult ip lexer performance," IEEE Journal on Selected Areas in Communications, vo l . 4, no. 6, pp. 856-868 , 1986. [20] N . A n s a r i , L . H a i , Y . Q . Sh i , and Z . H o n g , " O n model ing M P E G v ideo traffics," IEEE Trans-actions on Broadcasting, vo l . 48, no. 4, pp. 337 -347 , 2002. [21] M . W. Garrett and W. Wi l l inger , " A n a l y s i s , model ing and generation o f sel f -s imi lar V B R v ideo traffic," in Proc. of ACM Conference on Communications Architectures, Protocols and Applications, 1994, pp. 269 -280 . [22] T R 101 112 V3 .2 .0 , "Un ive rsa l mobi le te lecommunicat ion systems ( U M T S ) : selection proce-dures for the choice o f radio transmission technologies o f the U M T S , " European Telecommu-nication Standards Institute (ETSI), pp. 3 3 - 3 7 , 1998-04. 53 Chapter 4 Multi-Service Opportunistic QoS Enhanced Scheduler for the Downlink of IEEE 802.16 Point-to-Multipoint Systems 4.1 Introduction U n l i k e wire l ine systems, I E E E 802.16 broadband wireless metropol i tan access networks ( M A N s ) must funct ion effectively in the face o f t ime-vary ing fading channels o f l imi ted bandwidth. A c -cordingly, effective management o f scarce radio resources is required in order to max im ize system throughput and/or Q o S . The packet scheduler sitt ing at the med ium access control ( M A C ) layer arbitrates among the mult ip le users that seek access to the shared med ium and plays a key role in achiev ing these goals. The real-t ime schedul ing prob lem has been intensively studied for many years in conjunc-t ion wi th appl icat ions as diverse as sharing o f computer processor cycles or t ime slots on c o m m u -nicat ions channels. For real t ime data communicat ions, the objective is to guarantee the del ivery o f ' A version of this chapter has been submitted for publication. Yonghong Zhang and David G. Michelson, "Multi-service Opportunistic QoS Enhanced Scheduler for the Downlink of IEEE 802.16 Point-to-Multipoint Systems," submit-ted to IEEE Wireless Communications Magazine. 54 each packet before its expirat ion. In such cases, the earliest deadline first ( E D F ) or earlier due date po l icy has been considered opt imal . For non real t ime data communicat ions, such as f i le transfer, however, the objective is to fair ly distribute the l imi ted resource to each user, so that users can re-ceive relatively same level o f service. The general ized processor sharing ( G P S ) algor i thm is one o f the schedul ing schemes that can guarantee such fairness in an error-free environment. A l t hough these simple schedulers funct ion we l l when the channel is error-free, they are less effective when appl ied to t ime-vary ing fading channels. Examples o f past efforts to develop sched-ulers suitable for wireless appl icat ions are described in [1] and the references therein. Instead o f treating the t ime-vary ing nature o f the wireless channel as impairments, mult iuser diversity exploits the t ime-vary ing property o f the wireless channel by schedul ing transmissions to a part icular user only dur ing instants o f m in ima l fading [2]. The Proport ional Fa i r (PF) rule [3] and the scheduler proposed in [4] are examples o f scheduler algorithms that focus on fairness. The exponential rule ( E X P ) [5] and our own opportunistic Q o S enhanced scheduler ( O Q E S ) [6], on the other hand, are suitable for real-t ime traffic associated wi th t ime constraints. W h e n designing a schedul ing scheme suitable for use wi th the I E E E 802.16 standard, an-other issue needs to be considered. The standard provides different level o f services for a variety o f users ' needs. Some require that each o f their packets are del ivered wi th in a l imi ted t ime, some require guaranteed m in imum traffic rates, whi le others do not care about the ind iv idual behaviour o f the packet, as long as they can receive reasonable service at low cost. These diverse and often contradictory requirements add another level o f complex i ty to the design o f schedul ing schemes. A few studies (e.g., [7]) have focused on upl ink schedul ing for I E E E 802.16 systems, yet to the best o f our knowledge, none that seek to max im ize system throughput wh i le ensuring Q o S on the system downl ink has been introduced. The exist ing mult i -service schedul ing schemes that are suit-able for the downl ink are main ly designed for wireless A T M systems (e.g., [8]) and are not readi ly portable to the I E E E 802.16 system. Moreover , they are not able to exploi t the mult iuser diversity property o f the wireless system. A n E X P and P F rule combined algor i thm [9] has recently been proposed. It seeks to max im ize system throughput for both delay sensitive traffic and best-effort services. However , no mechanism has been provided to ensure m i n i m u m data rate. In this chapter, we propose a mult i -service opportunistic Q o S enhanced scheduler ( M -O Q E S ) that schedules mul t ip le service f lows from the base station (BS) to the subscriber stations 55 (SS) . It seeks to satisfy a l l levels o f Q o S requirements denned by the I E E E 802.16 wh i le t ry ing to max im ize the overal l system throughput. In Sect ion II, we review I E E E 802.16 supported ser-vices and their Q o S requirements. In Sect ion III, we describe our mul t i -serv ice opportunistic Q o S enhanced scheduler ( M - O Q E S ) . In Sect ion IV, we present s imulat ion results. In Sect ion V , we summarize the ma in contributiobs o f this work. 4.2 IEEE 802.16 Supported Services and Their QoS Requirements Four services are provided in I E E E 802.16. They are Unso l i c i ted Grant Service ( U G S ) , Real- t ime Po l l i ng Serv ice (r tPS), Non-real - t ime Po l l i ng Service (nrtPS), and Best Effort ( B E ) . 4.2.1 U G S Real- t ime data streams consist ing o f fixed-size data packets issued at per iodic intervals are to be sup-ported by U G S . Examp le appl icat ions include T l / E l and Vo ice over IP without si lence suppression. Because the fixed length packets o f such traffic arrive at the B S per iodical ly , and the appl icat ion at the SS requires the receipt o f these packets at tight t ime intervals, the task o f the downl ink scheduler at the B S is to transmit the packet at fixed interval w i th little or no variat ion so that the M a x i m u m Latency ( M L ) and Tolerated Jitter (TJ) requirements can be satisfied. 4.2.2 rtPS The r tPS is designed to support real-t ime data streams consist ing o f var iable-s ized data packets that are issued at per iodic intervals, such as video streaming or v ideo conference. Such appl icat ions require each packet arrives the SS wi th in a l imi ted t ime. For example, for v ideo conference, the tolerable delay f rom the B S to the SS is roughly between 40 ms to 90 ms. W i th the improvement o f the buffer abi l i ty at receiver, delay variance (jitter) is not as important as in U G S . The main Q o S service f low parameter shal l be considered for r tPS in downl ink schedul ing is M L . 4.2.3 nrtPS Delay-tolerant data streams such as F T P can be supported by nr tPS. Such streams usual ly consist o f var iable-s ized data packets for wh ich a m in imum data rate is required. The mandatory Q o S service 56 Table 4 .1 : Q o S requirements and mandatory Q o S service flow parameter to be considered by the downl ink scheduler Service type Q o S requirements Relevant service flow parameters U G S Per iod ic transmission M a x i m u m Latency ( M L ) , Tolerated Jitter (TJ) r tPS Wi th in certain delay M a x i m u m Latency ( M L ) nr tPS Ma in ta in m in imum data rate. Fa i r share o f the remaining resource. M i n i m u m Reserved Traff ic Rate ( M R T R ) B E H igher pr ior i ty flow gets lower delay. Fairness among same priori ty flows. Traff ic Pr ior i ty (TP) flow parameters that shall be considered by the B S downl ink scheduler is M i n i m u m Reserved Traff ic Rate ( M R T R ) , and Traff ic Pr ior i ty (TP) , wh i ch specifies the prior i ty among identical flows. 4.2.4 B E Data streams without any m in imum service level requirement can be supported by the B E service, wh ich can be handled on a space-available basis. A s there is no m i n i m u m requirement, the only Q o S service flow parameter need to be taken into considerat ion is TP. 4.2.5 Downlink QoS Requirements for The Services The I E E E 802.16 standard does not specify how resources shal l be al located among same pr ior i ty B E flows after the Q o S requirements o f the U G S , r tPS, and nrtPS flows have been satisfied. A reasonable rule is to ensure fairness, so that such flows can receive the same level o f service. Another issue the standard does not stress is how nrtPS flows should be treated after their M R T R have been met. A Poss ib le solut ion is to share the system resources wi th the B E flows w i th some fair share. Table 4.1 summarizes the Q o S requirements and the mandatory Q o S service flow parameters that need to be considered by the downl ink schedul ing scheme. 57 UGS Incoming packets " Flow 1 Flow 2 Flow n Flow 1 Flow 2 S-H OJ Flow m o 1/3 o Flow 1 H Flow 2 Flow p HPS nrtPS Fixed-size frame B E Flow 1 Flow 2. Flow q . Figure 4.1: System architecture o f the M - O Q E S schedul ing algor i thm. 4.3 The Multi-Service Opportunistic QoS Enhanced Scheduler (M-OQES) M - O Q E S is designed for the T D M A / T D D based M A C protocol in the I E E E 802.16 standard and the system architecture can be found in F i g . 4 .1 . Throughout the chapter, we assume that an ap-propriate ca l l admiss ion control scheme has been implemented. The terms SS and user are used interchangeably. To satisfy the Q o S requirements as summarized in table 4.1 wh i le t ry ing to max im ize system throughput, it is necessary to consider the characteristics o f the wireless channel. The signal strength received by wireless users changes randomly over t ime. Th is is not only true for mov ing users, but also true for stationary or fixed users due to the movement o f the scatterers around them, inc lud ing mov ing vehicles and w ind b lown fol iage. Schedul ing packets without consider ing the corresponding user's channel qual i ty cou ld lead to low channel ut i l izat ion. To max im ize system throughput, it is beneficial to exploit mult iuser diversity and try to allocate 58 resource to the user w i th the best channel quali ty at each time. However , only consider ing system performance wou ld both sacrif ice users wi th strict t ime constraints (e.g., real-t ime appl icat ions) and at un-favourable locations (e.g., at the ce l l edge). In order to compensate for such users, we use an urgency term along wi th the channel qual i ty condi t ion as the under l in ing schedul ing rule. No t i ce that because the tight t ime constraints o f the U G S f lows, we schedule the U G S f lows in fixed intervals before apply ing the fo l lowing schedul ing value rule. In other words, U G S f lows have higher prior i ty over other services, and are scheduled per iodica l ly regardless o f their channel condit ions. We use the schedul ing value v — UF to represent the schedul ing opportunity o f each flow. A t each schedul ing decis ion t ime, the f low w i th the max imum v gets the transmission opportunity for its head o f l ine ( H O L ) packet. The term U represents the relative achievable rate o f a flow's corresponding user, and term F specifies the urgency o f the flow. 4.3.1 Relative Rate Function U The relative speed o f the user is composed o f two parts. The first part is cal led the max imum rate reward ( M a x R R ) . On l y when a user reaches the m a x i m u m rate he/she ever reached in a past w indow, can the user receive the reward A; otherwise, the reward is 0. The second part is s imi lar to the P F rule, i.e., the ratio o f the user's current rate to their average rate. The goal o f the M a x R R is to encourage users to transmit at their highest possible rate. The P F rule becomes the decis ion rule when the M a x R R o f mul t ip le users are the same at t imes when none user reaches its m a x i m u m rate or mul t ip le users reach their max imum rate simultaneously . Because the relative m a x i m u m rate is the main determining factor, the value o f the reward A should be larger than the m a x i m u m possible value o f the P F term. 4.3.2 Urgency Function F A s the name suggests, the flow urgency term F describes how urgent the H O L packet o f the flow is. For different services, urgency has different meanings. For r tPS traffic, because every packet need to be transmitted wi th in the flow's M L , F r t P S measures how close the H O L packet is to its deadline. The closer it is, the higher the urgency. I f the deadline is far ahead, the value is set to its m i n i m u m , wh ich is 1, meaning that the packet is at 59 1 Trt Time left (t) Figure 4.2: Examp le urgent funct ion for r tPS service (Frtps(t) = l,t> Trt; ae1^, t < Trt). the normal state; wh i le i f the wait t ime has past a certain threshold, say Trt, the f low goes into the urgent state, and the closer we are to the deadline, the higher the value o f the urgency parameter. The closeness to the H O L packet 's deadline is measured by frame time left, t, wh i ch is the difference o f the f low's M L and its age, wh i ch is the summary o f the t ime the packet spent in the B S and the estimated transmission t ime. A n example funct ion o f FrtPS for r tPS service is shown in F i g . 4.2. I f frame t ime left t is smal ler than zero, there is a h igh change that the packet w i l l miss its deadline. In order to avoid the waste o f bandwidth by sending expired packets, we drop such packets proact ively in the B S . Fo r B E , because the main issue is to ensure fairness among users, urgency term FBE shows i f the flow has received its fair share. We use a credit l ike approach to moni tor the gap between a flow's fair share and the actual service it gets. W h e n a flow i gets the transmission opportunity for its H O L packet s ized L bytes, a l l other flows that have packets wai t ing for t ransmission w i l l receive credits equal to the fair share it shal l gets i f the L bytes had been shared fair ly among a l l these flows. A t the same t ime, flow i w i l l get negative credits equal to the total credits the other flows receive. In such case, we say flow i has spent L credits. For example, suppose there are 3 users in the system sharing the resources wi th a fair share o f (2,1,1). If user 1 spend 4 credits, i.e., transmit a packet 60 Y 1 -oo 0 1 Credit factor (c/C) Figure 4.3: Examp le urgent funct ion for B E service (FBE(c/C) = 7 e c / c ) . s ized 4, then the credits o f user 1 is -2 because the system offered 4 and user 1 on ly entit led o f 2 whi le borrowed the remaining 2 f rom the other users. The credits o f user 2 and 3 are both 1 since that is the share they should have received. Af ter user 3 spend 8 credits, the credits for the users are 2, 3, and -5 , respectively. We use the ratio o f user's credit c to a constant C to evaluate B E users' urgency. For the previous example, the credit factor for each f low becomes 0.02, 0.03, and -0.05 wi th a C o f 100. The higher the ratio, the more credits the f low have, and the more urgent the flow should be. A n example funct ion o f FBE for B E service is shown in F i g . 4.3. W h e n consider ing pr ior i ty o f the flow, the credit factor becomes p * c/C, where p is the T P o f the f low. For nr tPS, urgency term F n r t P S shows how far away is the flow to its M R T R and its fair share. We use token bucket to maintain the m in imum reserved rate and the credit mechanism in -troduced above to control its fair share. The token bucket is a container o f size S that holds the transferable token for a flow wi th each token represents one bit. A s time goes by, token is gener-ated at the M R T R as the flow specif ied ( in bits per second). W h e n the H O L packet is transmitted, the same amount o f the token is taken out o f the bucket. I f the generated token reaches a certain percentage o f the container, i.e., Tnrt, we say the flow is under-served, and put it to the urgent sta-tus, w h i c h translate to a F n r t P S value bigger than 1. W e use token factor to measure the urgency 61 1 L 0 Tnrt Token factor (s/S) 1 Figure 4.4: Examp le urgent funct ion. The m in imum reserved rate part o f the urgent funct ion for nr tPS service (FnrtPS'MRTR(s/S) = l,s/S < Tnrt; / 3 e s / s , s/S > Tnrt). through the ful lness o f the token bucket, i.e., s/S, where s is the nmber o f the token the flow has. The ful ler the bucket, the more urgent the flow. A n example funct ion o f the m i n i m u m reserved rate part o f the urgency funct ion FnrtpS'MRTR f o r service is shown in F i g . 4.4. W h e n the token in the bucket is not enough for the current H O L packet, the packet is st i l l a l lowed to be sent, the over-taken token is spent as credits, and the number o f the token is set to zero. A flow wi th negative credit and non urgent token factor is in the over-served state, and is temporari ly degraded as B E traffic. The urgency value o f a nrtPS flow takes into consideration o f both the rate reservation part and the fair share part, and the value is the greater one o f the two. 4.3.3 The M - O Q E S Algorithm Here, we describe our schedul ing algor i thm in detail. Du r ing each frame preparation t ime: 1) . I f a U G S flow reaches its sending t ime (e.g., the associated t imer times out), get the H O L packet o f the flow and go to step 5. Otherwise, continue to step 2. 2) . Calculate the schedul ing value v = UF for each r tPS flow, select the flow wi th the biggest v. I f the flow's H O L packet is in urgent state or the flow receives the M a x R R , get the H O L 62 packet o f the flow and go to step 5. Otherwise, mark the user as M A X R T and continue to step 3. 3) Calculate the schedul ing value v for each nrtPS flow whose credit is none negative or token factor is urgent (s/S > Tnrt), select the flow wi th the biggest v. I f the flow's H O L packet is in the urgent state or the flow receives the M a x R R , get the flow's H O L packet and go to step 5. Otherwise, mark the user as M A X N R T and continue to step 4. 4) Calculate the schedul ing value v for each B E flow and the degraded nrtPS flow, select the flow wi th the biggest v and mark it as MAXQE- Select the flow wi th the biggest v among M A X R T , M A X N R T , and MAX BE, and get the flow's H O L packet. Cont inue to step 5. 5) I f the packet can be fu l ly packed into the frame, do so. Otherwise, fragment the packet into two parts in such a way that the first part can just f i l l the frame. Pack the first part in the frame, leave the remain ing packet in the buffer. I f the frame is fu l l , f in ish. Otherwise, go to step 1. The basic idea o f the above algor i thm is to try to schedule flows at their m a x i m u m rate when there is no flow in urgent to meet Q o S requirement. For r tPS flows, since their packets need to be sent wi th in the M L , i f they could not get chances to send before they go to the urgent state, they w i l l grab the channel for transmission no matter what the channel qual i ty is, because the urgency factor goes up very fast. In that case, however, their channel state may be at bad condi t ions, and they may need more resources to send the same amount o f data out. A l though nrtPS and B E flows a l low some flexibility in their Q o S requirements, when they are far of f their normal token factor or fair share, they w i l l also qu ick ly get the transmission opportunity regardless o f their channel condit ions. We want to avoid such cases as much as possible to improve the overal l system throughput. Ideally, i f the corresponding user channel changes fast enough so that the relative m a x i m u m rate can be reached before each packet goes into the urgent state, the system performance w i l l be max im ized . Such condi t ion cou ld be reached when implement ing mult ip le antennas at the B S in the way as introduced in [2]. The computat ional complex i ty o f the M - O Q E S algor i thm is related to the number o f flows for each type o f services in the system. In the best case, the t imer o f one o f the U G S f lows times out wh ich indicates that it is t ime to send its H O L packet out, the schedul ing scheme does not need to do any calculat ions to make the decis ion. O n the other hand, when none o f the U G S flows meets its sending t ime and neither r tPS nor nr tPS flows satisfies the selection criteria in step 2 and step 3, the schedul ing algor i thm goes unti l step 4 to make the decis ion. In such worst scenarios, the 63 Table 4.2: Parameters o f the M - O Q E S algor i thm Parameter Scope Meaning Setting rules or guides Example value System The value of FrtPS(x), and FBE(x), when x = 1 a > B > 7 > 1 When using the urgent functions in Fig. 4.2, Fig. 4.3, and Fig. 4.4, we can set a = 6 * e, 3 = 4 * e, 7 = 3 * e A System Value of the maximum rate reward (MaxRR) Bigger than the max/min rate ratio in the system Tdt&max j T(Xt(ijnin Trt Flow The threshold of rtPS flows going to the urgent status A function of the HOL packet length and the flow's maximum tolerable packet loss ratio Estimated packet transmission time * (-log10(maximum tolerable packet loss ratio)) Tnrt Flow The threshold ofnrtPS flows going to the urgent status Set with S. 0 < Tnrt < 1, the bigger the value, the more rate variance, and the bigger the system throughput Typical value is between 0.2 and 0.7 C Flow The max tolerable credit loss for nrtPS and B E flows Tolerable amount of lacking service If a flow can stand 1 second of no service, then C = 1 * WQK with a rate of 100 kbps s Flow Size of the token bucket for nrtPS flows Set with Tnrt. The bigger the token bucket, the more variant of the receiving rate is allowed, and the bigger the system throughput If a flow's rate is 1 Mbps, and the rate variation within 2 seconds is tolerable, then 5 = 2* 1Mbps computat ional complex i ty is 0 ( l o g ( n ) ) (n is the number o f flows) wh i ch is the same as the P F rule. 4.3.4 Implementation Setting appropriate parameters is very important in successful ly implement ing the M - O Q E S algo-r i thm. A summary o f the parameters, their meanings, setting rules, and example values are shown in table 4.2. 4.4 S imu la t ion The simulat ion was performed on the downl ink o f one sector o f the I E E E 802.16 system using M A T L A B . We conducted two types o f simulat ions in order to evaluate the effectiveness o f the proposed scheduler. One was used to measure the overal l performance o f M - O Q E S compar ing wi th other exist ing comparable schedulers. The other was used to determine how we l l fairness between 64 nrtPS and B E servies is achieved. 4.4.1 Simulation Environment Because U G S traffic is scheduled before other type o f services, it has no cross effect w i th the schedul ing schemes for other services. Without losing accuracy, in our s imulat ion, we on ly evalu-ated the schedul ing scheme designed for r tPS, nr tPS, and B E traffic. rtPS service is evaluated us ing v ideo traffic that simulated us ing the s imple I P B composite mode l introduced in [10]. The movie Star Wars was simulated wi th an average data rate o f 1 M b p s . There is one packet (frame) generated in every 40 ms, wh ich is synthesized by combin ing o f three sel f -s imi lar processes in a way s imi lar to the Group o f Pictures ( G O P ) structure. The sel f -s imi lar processes adopted above are generated using the algor i thm given in [11]. The delay requirement is 100 ms, and the m a x i m u m tolerable delay v io lat ion is 2%. In terms o f nr tPS and B E services, in order to evaluate the m in imum rate guarantee for nrtPS service and fairness among users, we generated continuous f lows to simulate F T P for nr tPS service and W W W for B E service. Fo r both cases, one packet is generated every 4 ms. The ratio o f r tPS f lows, nr tPS f lows, and B E f lows is 1:2:2. Table 4.3 summarizes the traffic and their Q o S requirements for both types o f simulat ions. The base station o f the simulated system is located at the centre o f the ce l l wi th three 120° direct ional antennas. SSs use omnidirect ional antennas, and are un i formly distributed in the ce l l . Path loss model uses Erceg 's suburban model terrain type A described in [12] and fast fading channel uses R i c i a n distr ibution. The system uses mult ip le antennas as described in [2] to generate faster fading in the channel in order to enhance the performance o f mult iuser diversity. The m a x i m u m Dopp le r frequency is un i formly distributed between 10 and 20 H z . The base station communicates wi th the users using the rates adapted to the user channel condit ions so that the bit error rate Q o S required by each services can be met. The transmission between the base station and the user is assumed to be error-free. W h e n a user's received signal to noise ratio ( S N R ) is lower than the lowest requirement, no transmission w i l l be scheduled for the user. A l l s imulat ions last for 2 minutes, i.e., 120,000 frames, wh ich is considered to be long enough to avoid any specif ic scenarios. 65 Table 4.3: Simulated traffic and their Q o S requirements Frame dimension 240 * 252 M a x frame 26955 bytes V ideo M e a n rate 1 M b p s De lay requirement 100 ms M a x i m u m delay v io lat ion 0.02 Fa i r share among F T P 1 Generat ion rate (Type 1) 300 kbps Packet size (Type 1) 150 bytes F T P M i n i m u m required traffic rate (Type 1) 250 kbps Generat ion rate (Type 2) 1 M b p s Packet size (Type 2) 500 bytes M i n i m u m required traffic rate (Type 2) 500 kbps Fa i r share among W W W 1 Generat ion rate (Type 1) 300 kbps W W W Packet size (Type 1) 150 bytes Generat ion rate (Type 2) 1 M b p s Packet size (Type 2) 500 bytes Fai r share between F T P and W W W (Type 1) 1:2 Fa i r share between F T P and W W W (Type 2) 2:3 66 120 Throughput Effective Throughput Figure 4.5: System throughput o f the simulated system when using different schedul ing schemes. 4.4.2 Evaluation of the Performance To evaluate the effectiveness o f M - O Q E S , we selected some exist ing schedulers as a compar ison. We use E D F for the r tPS service, and R R for the nrtPS and B E services as a baseline in v iew o f the algor i thms' popularity. To be fair, the E D F / R R algor i thm is used in conjunct ion wi th adaptive modulat ion and coding. We also selected the E X P / P F [9] rule for compar ison. The E X P rule is suitable for the r tPS service, and the P F rule is a good match for B E service. For the nrtPS service, however, there is no suitable rule, so w e use two versions o f the E X P / P F rule. E X P / P F - 1 uses E X P for the nrtPS service, and E X P / P F - 2 uses P F for the nrtPS service. We ran the s imulat ion wi th 200 users for each targeted algor i thm. F i g . 4.5 through F i g . 4.8 show the system throughput; mean, max imum and m in imum receiv ing ratio for v ideo users, and mean, m a x i m u m , m i n i m u m throughput for F T P users and W W W users. It is obvious that the system throughput o f M - O Q E S is better than the others. The improve-ment is roughly 10% over E X P / P F - 1 , E X P / P F - 2 , and 17% over A M C - E D F / R R . The difference between throughput and effective throughput, wh ich is the throughput subtracting dropped bits, is not signif icant, although A M C - E D F / R R and O Q E S - M is better than the two E X P / P F schedulers. 67 100 A M C - E D F / R R EXP/PF-1 EXP/PF-2 M - O Q E S Figure 4.6: M a x i m u m , mean, and m in imum receiv ing ratio o f v ideo users o f the simulated system when us ing different schedul ing schemes. 400 A M C - E D F / R R EXP/PF-1 EXP/PF-2 M - O Q E S Figure 4.7: M a x i m u m , mean, and m in imum throughput o f the nrtPS users o f the simulated system when using different schedul ing schemes. 68 9 | I A M C - E D F / R R EXP/PF-1 EXP/PF-2 M - O Q E S Figure 4.8: M a x i m u m , mean, and m in imum throughput o f B E users o f the s imulated system when using different schedul ing schemes. A l l four schedul ing schemes are able to del iver most o f the real-t ime v ideo packet w i th in required t ime constrain wh i le keeping the dropping ratio be low 2 % . A M C - E D F / R R and M - O Q E S are better than the two E X P / P F algorithms wi th the packet receiv ing ratio at 100%. A M C - E D F / R R and E X P / P F - 2 are fai led at maintain ing the M R T R at 250 kbps for F T P users, and users under the E X P / P F - 2 rule are receiv ing quite different data rates because o f their different channel condi t ions, wi th the m a x i m u m rate at 300 kbps and the m i n i m u m at 0.26 kbps. Bo th E X P / P F - 1 and M - O Q E S are able to maintain the M R T R , however, the E X P / P F - 1 rule has del ivered every packet o f the F T P f low no matter how starving the W W W users are. In terms o f W W W users, both A M C - E D F / R R and O Q E S - M are able to achieve fairness among users, wh i le both versions o f the E X P / P F rule favour some users over others, wh i ch results in a best vs. worst data ratio o f 34 for E X P / P F - 1 and 1154 for E X P / P F - 2 . 4.4.3 Evaluation of Short Term Fairness To il lustrate how fairness is achieved among nrtPS and B E services, we d id another type o f s imu-lations wi th seven users wi th the mean S N R o f 13.8 d B , 31.4 d B , 18.0 d B , 22.7 d B , 12.2 d B , 21.6 350 300 Q. XI 250 200 60 3 O J 3 50 100 50 69 0.2 0.0 1 • nrtPS 1 - nrtPS 2 - B E 1 •• B E 2 - nrtPS added - B E added 10 20 30 40 50 60 70 80 90 100 110 120 Time (second) Figure 4.9: Short term fairness o f the M - O Q E S schedul ing algor i thm. d B , and 27.6 d B , respectively. Use r 1 is a real-t ime video user who requires r tPS service, and users 2 through 7 are F T P or W W W users that consume nrtPS and B E services. The simulated traffic and Q o S requirement o f each f low can be found in table 4.3. A t the start, there were only 5 users in the system, inc lud ing 1 v ideo user, 2 F T P users, and 2 W W W users. Af ter 40 seconds, another F T P user jo ined the system, and later at 80 second, an extra W W W user was added. F i g . 4.9 shows the time-series consumed bandwidth averaged over 10 seconds for each user. A n d because the v ideo user does not need to share any resources wi th the F T P and W W W users, we d id not include the throughput o f the v ideo user in the f igure. Throughout the simulated 120 seconds, each packet o f the v ideo user has been del ivered on t ime. F r o m F i g . 4.9, we can see that throughout the s imulat ion per iod, the rates received by F T P users are quite similar, and so are those for the W W W users. Th is shows the bandwidth has been fair ly shared among the same service consumers. 70 In the first 40 seconds, after sat isfying the Q o S requirements o f the v ideo user and the M R T R (500 kbps) o f the F T P users, the remaining resources is shared among the F T P and W W W users wi th a fair share o f (2,3). Thus , apart f rom the m in imum rate, each F T P user received a data rate totaled at 860 kbps wi th a fair share o f 360 kbps, and each W W W user got the fair share o f about 540 kbps. Apparent ly , the received fair share o f F T P and W W W users do fo l low the specif ied fair share, wh i ch is 360:540 or 2:3. W h e n the F T P user jo ined at 40 second, the four exist ing users' data rate dropped accordingly. The data rates for the W W W users then became 390 kbps, and 760 kbps for F T P users, inc lud ing the newly jo ined one. A n d then at 80 second, another W W W user jo ined the system. A g a i n , the exist ing F T P and W W W users' data rate dropped accord ing to their M R T R and fair share. W i th 7 users in the system, the fair share unit became 120 kbps, and the data rate for F T P and W W W user are 740 kbps and 360 kbps, respectively. Note that the overal l system throughput grew each t ime new users added in , f rom 3.8 M b p s at the beginning, to 4.06 M b p s after one F T P user jo ined, and to 4.3 M b p s f inal ly (the video user has a data rate o f roughly 1 Mbps ) . The reason for the increase in system throughput is ma in ly due to the effect o f mult iuser diversity. 4.5 Conclusions We have introduced a new downl ink scheduler for I E E E 802.16 point- to-mult ipoint broadband wi re-less access systems. It aims to provide good performance for mult ip le services by achieving an effective compromise between max im iz ing throughput and max im iz i ng Q o S . It does so by com-b in ing convent ional mult iuser diversity wi th an urgency funct ion whose value increases qu ick ly when meet ing a specif ied Q o S requirement becomes urgent. S imulat ion results conf i rm that our mul t i -serv ice opportunistic Q o S enhanced scheduler ( M - O Q E S ) algor i thm outperforms exist ing mult i -service schedul ing schemes. Moreover , the M - O Q E S algor i thm is easy to implement and the computat ional complex i ty is comparable to the w ide ly adopted P F rule. 71 References [1] H . Fattah and C . Leung , " A n overview o f schedul ing algori thms in wireless mul t imedia net-works , " IEEE Wireless Communications, vo l . 9, no. 5, pp. 7 6 - 8 3 , 2002. [2] P. V iswanath , D . N . C . Tse, and R. La ro ia , "Opportunist ic beamforming us ing dumb antennas," IEEE Transactions on Information Theory, vo l . 48, no. 6, pp. 1277 - 1294, 2002. [3] A . Ja la l i , R. Padovani , and R. Panka j , "Da ta Throughput o f C D M A - H D R a H i g h Ef f ic iency-H i g h Data Rate Personal Commun ica t ion Wireless System," in Proc. of IEEE 51st Vehicular Technology Conference. (VTC 2000-Spring), vo l . 3, 2000, pp. 1854 - 1858. [4] X . L i u , E . K . Chong , and N . B . Shroff, "Oppor tunis t ic transmission schedul ing wi th resource-sharing constraints in wireless networks," IEEE Journal on Selected Areas in Communications, vo l . 19, no. 10, pp. 2 0 5 3 - 2 0 6 4 , 2 0 0 1 . [5] S. Shakkottai and A . L . Stolyar, "Schedu l ing for mult ip le flows sharing a t ime-vary ing chan-nel : The exponential rule," American Mathematical Society Translations, vo l . 207, 2002. [6] Y . Zhang and D . G . M i c h e l s o n , "Opportunist ic Q o S enhanced scheduler for real-t ime traffic in wireless communicat ion systems," accepted for presentation at the IEEE 64st Vehicular Technology Conference, Mont rea l , Canada, Sep. 25-28, 2006. [7] K . Wongthavarawat and A . Ganz , "Packet schedul ing for Q o S support in I E E E 802.16 broad-band wireless access systems," International Journal of Communication Systems, vo l . 16, no. l , p p . 8 1 - 9 6 , 2003. [8] J . F. F r igon , V. C . M . Leung , and H . Chan B u n Chan , " D y n a m i c reservation T D M A protocol for wireless A T M networks," IEEE Journal on Selected Areas in Communications, vo l . 19, no. 2, pp. 3 7 0 - 3 8 3 , 2 0 0 1 . [9] R. Jong-Hun , J . M . Ho l t zman, and K . D o n g K u , "Per formance analysis o f the adaptive E X P / P F channel scheduler in an A M C / T D M system," IEEE Communications Letters, vo l . 8, no. 8, pp. 4 9 7 - 4 9 9 , 2004. 72 [10] N . A n s a r i , L . H a i , Y . Q . Sh i , and Z . H o n g , " O n mode l ing M P E G v ideo traffics," IEEE Trans-actions on Broadcasting, vo l . 48, no. 4, pp. 337 -347 , 2002. [11] M . W. Garrett and W. Wi l l inger , " A n a l y s i s , model ing and generation o f sel f -s imi lar V B R v ideo traffic," in Proc. of ACM conference on Communications architectures, protocols and applications, 1994, pp. 269 -280 . [12] V. Erceg et a l . , " A n empir ica l ly based path loss model for wireless channels in suburban en-vironments," IEEE Journal on Selected Areas in Communications, vo l . 7, no. 7, pp. 1205 -1211, 1999. 73 Chapter 5 Conclusions and Future Work 5.1 Conclusions In this thesis, we have considered the impact o f w ind-b lown fol iage on the performance o f f ixed broadband wireless access ( F B W A ) systems. U s i n g an improved R icean K- factor mode l that c o m -bines elements o f prev iously d isc losed models, we have shown how the performance o f the system is degraded when the fading events on mult ip le l inks are correlated. Further, we have proposed two channel-state-dependent downl ink schedulers that exploit mult i -user diversity for use wi th T D M A mode I E E E 802.16 point-to-mult ipoint systems. Our specif ic contributions are as fo l lows: • We have assessed the impact o f wind- induced fading on the performance o f a s ingle-cel l point- to-mult ipoint system. B y combin ing elements o f prev iously d isc losed K- factor models in a manner that accounts for w ind speed, subscriber station antenna characteristics, and the distance f rom the base station to the subscriber, and mak ing use o f a pathloss mode l for subur-ban environments that has been adopted by I E E E 802.16, and by account ing for the m i n i m u m signal-to-noise ratio required by different modulat ion schemes, we have been able to assess the fundamental l imits on system performance under different w ind condit ions for different terrain types. Ou r s imulat ion results show that when w ind increases f rom n i l to heavy, system performance at the edge o f a ce l l wi th heavy fol iage may degrade by over 10%. However, our simulat ions account for the effect o f S N R on throughput only and do not account for other M A C and Network layers effects. Ma jo r portions o f this work were presented at the Proceed-74 ings of International Wireless Communications and Mobile Computing Conference (IWCMC 2006). • We have proposed an opportunistic Q o S enhanced scheduler ( O Q E S ) for real-t ime traffic for F B W A systems. B y introducing the concepts o f flexible t ime and urgent t ime, O Q E S is able to max imize system throughput over a t ime-vary ing channel by apply ing both mul t i -user diversity and a "meets de lay" requirement. To avoid wast ing bandwidth, we have also introduced a s imple mechanism that proact ively discard packets that w i l l have expired before they are del ivered. Cons ider ing the nature o f the propagation channel impairments caused by w ind b lown fol iage, we have proposed the use o f fair degradation to keep user packet delay v io la t ion ratio w i th in a tolerable range. Simulat ion results show that O Q E S outperforms exist ing schedulers for real-t ime traffic especial ly under w indy weather condit ions. M a j o r port ions o f this work w i l l be presented at the IEEE Vehicular Technology Conference (VTC 2006-Fall). A fu l l journa l manuscript is been prepared. • We have proposed a mult i -service opportunistic Q o S enhanced scheduler ( M - O Q E S ) for the downl ink o f the I E E E 802.16 P M P F B W A system. It seeks to max im ize the overal l sys-tem throughput by explo i t ing mult i -user diversity for mult ip le service users simultaneously whi le ensuring different levels o f Q o S requirements defined by the I E E E 802.16 standard by def ining different urgency functions for each service. S imulat ion results conf i rm that the M -O Q E S algor i thm outperforms exist ing mult i -service schedul ing schemes. Th is work has been submitted to IEEE Wireless Communication Magazine for review and possib le publ icat ion. 5.2 Future Work The fo l low ing summarizes some possible topics for future study: • In Chapter 2, we assessed the impact o f w ind- induced fading on the performance o f an ideal -ized s ingle-cel l P M P system in wh i ch signal-to-noise ratio is the only cri teria for determining system throughput. In order to assess the impact on realist ic systems, it w i l l l i ke ly be nec-essary to incorporate both upper layer protocols and adaptive modulat ion schemes in more real ist ic ways. 75 In Chapter 2, we proposed a K- factor model that combines elements o f previously d isc losed models and our pre l iminary observations o f w ind- induced fading on mult ip le l inks. W h i l e this mode l has signif icantly improved our abi l i ty to assess system-wide throughput, our un-derstanding o f the effect is st i l l incomplete. It w i l l be necessary to col lect measurement data f rom real systems to refine the mode l and its parameters. The schedulers proposed in Chapter 3 and Chapter 4 are designed for I E E E 802.16 systems that operate in T D M A mode, where only one user can transmit at any instant o f t ime. In O F D M A systems, however, mult ip le users can share the channel by using different sub-carriers. A s a result, the packet schedul ing opt imizat ion prob lem extends f rom the t ime domain to both the t ime and frequency domains, wh i ch adds an extra level o f complex i ty to the problem. Thus, a possible future research topic is to extend this work f rom T D M A systems to O F D M A systems. 76 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            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:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0065426/manifest

Comment

Related Items