Priority-Based Resource Allocation For Downlink OFDMA .

276H. WANG ET AL.size 256 (subcarriers) in fixed WiMAX, OFDMAemploys a larger FFT space (2048 and 4096 subcarriers)which are further grouped into subchannels. Thesubchannels are assigned to different users and mayemploy different modulation and coding schemes toexploit frequency diversity as well as time diversity [12].There are two approaches of allocating subcarriers toform a subchannel in OFDMA: distributed subcarrierpermutation and adjacent subcarrier permutation. Thetwo approaches are shown in Figure 1. In distributedsubcarrier permutation, a subchannel is formed withdifferent subcarriers randomly distributed across thechannel spectrum. This approach maximizes thefrequency diversity and averages inter-cell interference.It is suitable for mobile environment where channelcharacteristics change fast. Both partial usage ofsubchannels (PUSC) and full usage of subchannels(FUSC) schemes employ distributed subcarrierpermutation. In adjacent subcarrier permutation, asubchannel is formed by grouping adjacent subcarriers.This approach creates a ‘loading gain’ and is easy to usewith beam-forming adaptive antenna system (AAS). It issuitable for stationary or nomadic environment wherechannel characteristics change slowly. The AMC schemeemploys adjacent subcarrier permutation.In this paper, we assume that subscriber stations arestationary or nomadic users with slowly varying channelconditions. Therefore, adjacent subcarrier permutationstrategy is employed to support AMC. In OFDMA, radioresource is partitioned in both frequency domain andtime domain, which results in a hybrid frequency-timedomain resource allocation. It provides an addeddimension of flexibility in terms of higher granularitycompared to OFDM/TDM systems.W e c o n s i d e r t h e d o wn l i n k s c e n a r i o o f a ninfrastructure-based OFDMA system with Us subcarriersand K users. At the physical layer, the time axis isdivided into frames with fixed length, each of whichconsists of a downlink (DL) and an uplink (UL) subframeto support TDD operation. In each DL subframe, thereare Ut time slots available for downlink transmissions,each of which may contain one or several OFDMsymbols. To reduce the resource addressing space,channel coherence in frequency and time is exploited bygrouping Is adjacent subcarriers and It time slots to forma basic resource unit (BRU) for resource allocation. ABRU is the minimum resource allocation unit as shown inFigure 2. The size of a BRU is adjusted so that thechannel experiences flat fading in both frequency andtime domain. Thus in each DL subframe, there are S Us/Is subchannels in frequency domain and N Ut/It slotsin time domain, which corresponds to a total of S * NBRUs available in frequency-time domain for DLtransmissions. Each BRU can be assigned to differentusers and be independently bit and power loaded. Inprinciple, adaptive power allocation in each BRU canimprove the system performance. However, some studiesshow that performance improvements are only marginalCopyright 2008 SciRes.Figure 2. Frequency-time domain redio resource allocationin OFDMA systems.over a wide range of SNRs due to the statistical effects[1]. Therefore, we assume that the total transmissionpower is equally distributed among all subchannels.We further assume that in each frame the base station(BS) has perfect knowledge of channel state information(CSI) for each subchannel of each user. This can beobtained by piggybacking such information in eachuplink packet, which is suitable for slowly varyingchannels. Based on CSI, adaptive modulation and codingscheme is employed to adjust the transmission modedynamically according to the time-varying channelconditions. Multiple transmission modes are available,with each mode representing a pair of specificmodulation format and a forward error correcting code.The transmission mode is determined by theinstantaneous signal-to-noise ratio (SNR). To utilize thePHY layer resources more efficiently, fragmentation atthe MAC layer is enabled. A separate queue with a finitequeue length of L MAC protocol data units (PDUs) ismaintained for each connection at the base station. Weassume that the MAC PDUs are of fixed size, each ofwhich contains d information bits.3. Resource Allocation ModelThe resource allocation at the BS involves the allocationof subchannels, time slots, and modulation order andcoding rate assignment. It is executed at the beginning ofevery frame to properly allocate radio resources to thedemanding users according to their queue status, CSI,and QoS requirements.The real-time traffic is delay-sensitive and has strictdelay requirement. The non-real-time traffic can toleratelonger delays, but requires a minimum throughput. Wepropose a novel priority-based packet schedulingalgorithm to support both RT and NRT multimediatraffic with high spectral efficiency and good QoSsatisfaction. The basic idea behind the proposedalgorithm is that the transmission is scheduled on aI. J. Communications, Network and System Sciences, 2008, 3, 207-283

PRIORITY-BASED RESOURCE ALLOCATION FOR DOWNLINK OFDMASYSTEMS SUPPORTING RT AND NRT TRAFFICSpacket-bypacket basis. Specifically, at each schedulinginterval, if a PDU was scheduled for transmission on aspecific subchannel, it is assigned a priority value basedon the instantaneous channel condition (PHY layer issue),as well as the QoS constraint (MAC layer issue). Thenwe can formulate the scheduling problem into amathematical optimization problem with the objective tomaximize the total achievable priority values.We apply an extended EXP algorithm as our priorityfunction for both RT and NRT traffics. The EXP rulewas proposed to provide QoS guarantees over a sharedwireless link in terms of the average packet delay for RTtraffic and a minimum throughput for NRT traffic [15].For RT traffic, if the ith PDU from the kth connectionis scheduled for transmission on subchannel n, its priorityvalue is calculated as:P (k,i,n ) ak µk,n (t ) a W (t ) aW exp k k,i 1 aWµ k (t ) (1)where aW 1 akWk ,1 (t ) ,and ak log δ k Tk , max Wk ,i (t ) isk kthe ith PDU delay of connection k at time t, Tk,max is themaximum allowable delay of connection k, δk is themaximum outage probability of connection k, µk,n(t) is theinstantaneous channel rate with respect to the signal-tonoise ratio and a predetermined target error probability ifsubchannel n is assigned to connection k at time t, andµ k (t ) is the exponential moving average (EMA) channelrate of connection k with a smoothing factor tc, calculatedas: µ k (t ) 1 1 1 µ k (t 1) µ k (t )tc tc(2)where µk (t ) nN 1 ck , n µk , n (t ) is the total channel rateof connection k at time t. If subchannel n is assigned toconnection k, ck,n 1, otherwise ck,n 0.For NRT traffic, the extended EXP algorithm is usedin conjunction with a token bucket control to guarantee aminimum throughput [15]. We associate each NRTqueue with a virtual token bucket. Tokens in each bucketarrive at a constant rate rk,req, which is the requiredminimum throughput of connection k. Let us define Vk,i(t)to be the virtual waiting time of the ith PDU fromconnection k:Vk , i (t ) max {0, Qk (t ) (i 1) d }k NRTrk , req(3)where Qk(t) is the number of tokens associated withconnection k at time t, and d is the fixed size of a MACPDU. Note that we do not need to actually maintain thevirtual waiting time, as the arrival rates of tokens areCopyright 2008 SciRes.277constant. Then, the calculation of the priority for a NRTPDU is similar to Exp.(1), with Wk,i(t) being replaced byVk,i(t). After a PDU is scheduled for transmission, thenumber of tokens in the corresponding token queue isreduced by the actual amount of data transmitted.Let u(k,i,n) be defined as a binary random variableindicating subchannel allocation. That is, u(k,i,n) 1means that the ith PDU from connection k is allocated fortransmission on subchannel n, and u(k,i,n) 0 otherwise.Also let us define m(k,i,n) be the number of time slotsoccupied on subchannel n if the ith PDU from connectionk is scheduled for transmission on subchannel n,calculated as: d m(k,i, n ) (4) µk,n (t ) where [x] denotes the smallest integer larger than x.Then, the scheduling problem can be mathematicallyformulated as follows:KLSarg max u(k,i, n ) P(k,i, n )u ( k,i,n )(5)k 1 i 1 n 1Subject to:KL u(k,i, n) m(k,i, n ) N n(6)k 1 i 1S u(k,i, n) 1 k,i(7)u(k,i,n ) {0,1} k,i,n(8)n 1where S denotes the total number of subchannels, Ndenotes the total number of time slots, K denotes the totalnumber of connections, and L denotes the maximumqueue size.The first constraint ensures that the allocatedbandwidth does not exceed the total available bandwidthin terms of time slots on each subchannel. The secondconstraint says that a PDU can only be transmitted viaone subchannel. The instantaneous channel conditionsand the QoS related parameters are embodied into thepriority function P(k,i,n) with the objective ofmaximizing the total achievable priority values, thusimproving the spectral efficiency while maintaining QoSguarantees.The above optimization problem can be solved bydetermining the values of binary variable u(k,i,n) throughstandard linear integer programming (LIP)1. The solutionto the problem provides an optimal resource allocation.1The optimal solution of the LIP problem formulated in this paper isobtained by using the General Algebraic Modeling System(GAMS).I. J. Communications, Network and System Sciences, 2008, 3, 207-283

278H. WANG ET AL.However, the computation complexity of the optimalsolution is too high to be applied in practical systems. Toreduce the computational complexity, we propose asuboptimal heuristic algorithm with low complexity inthe next section.4. Proposed Suboptimal SchemeIn the suboptimal algorithm, we allocate radio resourceson a packet-by-packet basis. The general idea is that, ateach scheduling interval, the packet with the highestpriority value from all queues is scheduled fortransmission, and this procedure continues until eitherthere is no radio resource left or there is no packetremaining unscheduled in the queue. A detaileddescription of the proposed scheduling algorithm is listedin pseudocode 1, where Ω ks is the set of subchannels thatare available for data transmission of connection k, tn isthe number of residual time slots on subchannel n, qk isthe current queue size of connection k, and ik is a pointerto the next PDU to be scheduled of connection k.It works as follows: If connection k has pendingtraffic in the queue, the proposed algorithm first preallocates the best subchannel n in terms of theinstantaneous channel quality to connection k from itsavailable subchannel set Ω ks (see Step 14). If there isnot enough capacity left on the best subchannel n toaccommodate one PDU from connection k’s queue,subchannel n will be removed from connection k’savailable subchannel set, and the second bestsubchannel n' will be selected. This procedurecontinues until a best possible subchannel is preallocated to connection k (see Step 13-22). Otherwise,connection k is removed from the scheduling list. Afterthe subchannel pre-allocation process for allconnections is complete, the algorithm calculates thepriority value of the head-of-line (HOL) PDU in eachnonempty queue, and schedule the PDU with thehighest priority value for transmission on subchannel n*(see Step 16 & 24). The scheduled PDU is removedfrom the corresponding queue and the consumed radioresources in terms of time slots are subtracted onsubchannel n* (see Step 25 & 26-30). Then it startsfrom the beginning and continues until either there is noradio resource left or there is no PDU pending in thequeue. A detailed flowchart of the proposed suboptimalalgorithm is given in Appendix I.5. Simulation Results and DiscussionsTo evaluate the performance of the proposed resourceallocation algorithm for downlink OFDMA systemssupporting both RT and NRT multimedia traffic, asystem-level simulation is performed in OPNET.Copyright 2008 SciRes.Algorithm 1 Suboptimal Packet Scheduling Algorithm forDownlink OFDMA Systems1: Set t n N for n ｛initialize t n ｝2:Set ik 1 for3:4:5:6:7:8:9:10:11:12:13:Get qk for k ｛get the queue size of connection k ｝for k 1 to K doif qk 0 thenSet Ω ks ｛1, ,S｝｛initialize Ωks ｝14: k｛initialize ik ｝elseSet Ω ks φ ｛set Ω ks to be null｝end ifend forwhile x, Ω sx φ dofor k 1 to K dowhile Ω ks φ doSelect n arg max n Ω µ k ,n (t ) ｛assign the bestkssubchannel from the available subchannel set｝ d (t ) k ,n 15:if tn µ16:17:18:Calculate P(k,ik,n) in Exp. (1)BREAKelse19:thenΩ ks Ω ks ｛n｝｛remove n from the availablesubchannel set if there is not enough capacity left｝20:CONTINUE21:end if22:end while23: end forSchedule the ik * th PDU of connection k * on subchannel24: *n , where ( k * , ik * , n * ) arg max P ( k , ik , n )25: d t n * t n* ｛update the residual time slots｝ µ k *,n* (t ) 26: if ik * qk thenΩ ks * φ ｛set Ω ks * to be null when all pending PDUs27:of connection k* have been scheduled for transmission｝28: elseik * ik * 1 ｛point to the next pending PDU｝29:30:end if31: end while5.1. System ModelWe consider the downlink of a single-cell OFDMAsystem with TDD operation. The cell radius is 2 km,where subscriber stations are randomly placed in the cellwith uniform distribution. The total bandwidth is set tobe 5 MHz, which is divided into 10 subchannels. The BStransmit power is set to 20W (43 dBm) which is evenlydistributed among all subchannels. The duration of aframe is set to be 1 ms so that the channel quality of eachconnection remains almost constant within a frame, butmay vary from frame to frame. The propagation model isderived from IEEE 802.16 SUI channel model [20]. Pathloss is modeled according to terrain Type A suburbanmacro-cell. Large-scale shadowing is modeled by lognormal distribution with zero mean and standarddeviation of 8 dB. The rms delay spread is 0.5µs, typicalof an urban environment. The effect of small scaleI. J. Communications, Network and System Sciences, 2008, 3, 207-283

PRIORITY-BASED RESOURCE ALLOCATION FOR DOWNLINK OFDMASYSTEMS SUPPORTING RT AND NRT TRAFFICSTable 1. A summary of system parameters.ParametersSystemCentral frequencyChannel bandwidthNumber of subchannelsLength of OFDM symbolUser distributionBeam patternCell radiusFrame durationBS transmit powerThermal noise densityPropagation modelMaximum MAC PDU sizeValueOFDMA/TDD3500 MHz5 MHz10156.25 µsUniformOmni-directional2 km1 ms20 W–174 dBm/Hz802.16 SUI-5 Channel model256 bytesTable 2. Modulation and Coding Schemes for 802.16 .52344.5Target SNR for1% PER (dB)1.56.48.213.416.221.724.4Table 3. A summary of traffic paramenters.TypeCharacteristicsDistribution ParametersVoIPVoIPVoIPON periodOFF periodPacket sizeInter-arrival timebetween packetsExponentialExponentialConstantMean 1.34 secMean 1.67 sec66 bytesConstant20 msVideo Packet sizeLog-normalVideo Inter-arrival timebetween packetsReadingtimeWebbetween sessionsNumber of packetsWebwithin a packet callInter-arrival timeWebbetween packetsNormalMean 4.9 bytesStd.dev. 10 msMean 33 msStd.dev. 10 msVoIPWebExponentialMean 5 secGeometricMean 25packetsMean 0.0277seck 81.5 bytesα 1.1m 2 M bytesGeometricTruncatedParetoPacket sizeN(9)i 0where N is the total number of paths, δ(·) is the Diracimpulse, βi(t) and τi(t) are the time-variant gain and delayof the ith path, respectively. The channel gains βi(t) arezero mean mutually independent Gaussian stationaryprocesses with an exponentially decaying power profileCopyright 2008 SciRes.and a classical Jake’s spectrum. The thermal noisedensity is assumed to be –174 dBm/Hz.Table 1 summarizes the system parameters used in thesimulation. We assume that all MAC PDUs aretransmitted and received without errors and thetransmission delay is negligible. The modulation orderand coding rate in the AMC scheme is determined by theinstantaneous SNR of each user on each subchannel. Wefollow the AMC table shown in Table 2, which specifiesthe minimum SNR required to meet a target packet errorrate, e.g., 1%.5.2. Traffic ModelIn the simulation, three types of traffic sources aregenerated: Real-time (RT) voice: RT voice traffic is assumed tobe VoIP that periodically generates packets of fixedsize. Assuming that silence suppression is used, VoIPtraffic can be modeled as a two-state Markov ON/OFFsource [17]. Real-time (RT) video: RT video traffic is assumed tobe the videoconference which consists of a VoIPsource and a video source [17]. A video sourceperiodically generates packets of variable size. Non-real-time (NRT) data: NRT data traffic isassumed to be Internet traffic such as web browsingthat requires large bandwidth and generates burstydata of variable size. We apply the Web browsingmodel for the Internet traffic [18].It is assumed that each user has a connection pairconsisting of a RT connection and a NRT connection.VoIP and video traffic is served in RT connection whiledata traffic is served in NRT connection. Eachconnection alternates between the states of idle and busy,which are both exponentially distributed, and is loadedwith corresponding traffic source when the connection isin busy state. A summary of traffic parameters ofdifferent traffic types are listed in Table 3.5.3. Performance Evaluationmultipath fading is modeled by a tapped delay line (TDL)with exponential power delay profile as follows:h(τ , t ) β i (t )δ (τ τ i (t ))279We evaluate and compare the performance of theproposed priority-based scheduling algorithm with otherconventional algorithms in terms of the average packetdelay, the throughput, the outage probabilities, and themodulation efficiency via extensive computer simulations.For delay-sensitive RT traffic, the average packetdelay and the delay outage probability are the mainperformance metrics. The delay constraint for RT trafficis set to be 50ms. For loss-sensitive NRT traffic, theaverage throughput and the throughput outageprobability are the main performance metrics. Theminimum throughput constraint for NRT traffic is set tobe 100 Kbits/sec. The outage probabilities for both RTI. J. Communications, Network and System Sciences, 2008, 3, 207-283

280H. WANG ET AL.and NRT traffic should be less than 3%. In order toevaluate the spectral efficiency, the modulation efficiencyis also considered in the performance evaluation.For comparisons, we include the simulation results oftwo conventional scheduling algorithms proposed forOFDMA systems. The first one is maximum SNR, whereusers are selected for transmission over each subchannelaccording to their CSI. The second one is proportionalfair (PF) [14], where users are selected for transmissionover subchannel n according to the following criteria:in* arg maxiµ i ,n (t )µ i ,n (t )(10)where µ i, n (t ) is the average data rate of the nthsubchannel of user i. To compare the performancebetween OFDM/TDM and OFDMA based systems,simulation results of the EXP rule applied inOFDM/TDM systems are also included. The EXP rule isconsidered to be one of the best scheduling algorithms inOFDM/TDM based systems [15], of which each usertransmits in the assigned time slots over all subchannels.Figure 3 shows the average packet delay of RT trafficversus the number of users for different schedulingalgorithms. When the number of users is below 48, theaverage packet delay of the proposed scheme increasesmarginally and it is well kept below the maximumallowable delay, which is 50 ms in our scenario. Afterthat point, the system is overloaded and the averagepacket delay increases sharply. Similar phenomenon ofthe proposed scheme can be observed for the delayoutage probability shown in Figure 4. However, theaverage packet delay of the PF scheme and the MAXSNR scheme is much larger compared to our proposedscheme, which consequently results in a higher delayoutage probability when the number of users is below 48.Furthermore, it can be seen from Figure 4 that when thenumber of users is above 48, the delay outage probabilityFigure 3. Average packet delay in RT.Copyright 2008 SciRes.Figure 4. Delay outage probability in RT.of the proposed scheme increases rapidly to one, whichmeans that the system is overloaded and almost no RTconnections can maintain the required delay constraint.On the other hand, some RT connections in the PF andMAX-SNR schemes can still maintain the required delayconstraint as the delay outage probabilities in these twoschemes increase steadily with respect to the number ofusers. This is because in the proposed scheme, it not onlytakes the instantaneous channel conditions, but also thedelay requirement into consideration when schedulingpackets. RT connections with larger packet delay areassigned higher priorities in an effort to average out thepacket delay among all RT connections. As a result, eachRT connection will have similar average packet delayregardless of its channel conditions. When the system isoverloaded, congestion occurs and all RT connectionswill experience bandwidth starvation, which results in asharp increase of the average packet delay and the delayoutage probability. However, in the PF and MAX-SNRschemes, the scheduler selects a connection fortransmission only based on instantaneous channelconditions. As a consequence, connections with goodchannel conditions will always experience very shortdelay at the cost of bandwidth starvation for connectionswith poor channel conditions. Therefore, the delayoutage probability in the PF and MAX-SNR schemesincreases much more smoothly compared to the proposedscheme when the number of users is above 48. As for theEXP rule applied in OFDM/TDM systems, the dottedline in Figure 3

In this paper, we propose a novel resource allocation algorithm for downlink OFDMA systems supporting both RT and NRT multimedia traffic. Unlike the conventional approaches, which decompose the resource allocation into two steps: packet scheduling and subcarrier-and-power allocation [4,11], the proposed algorithm tightly