Queue-Aware Resource Allocation For Downlink OFDMA Cognitive Radio Networks

3spectrum sharing under the spectrum underlay paradigm isconsidered.Closely related to this work is [6] where optimal power allocation for a single user under continuous rate assumption foran OFDM-based cognitive radio is handled. Our current paperconsiders a more general multi-user scenario with max-minrate sharing among secondary users for a downlink OFDMAbased cognitive radio network with discrete subcarrier rateassignments.In [7], an efficient dynamic frequency hopping strategyfor multi-cell IEEE 802.22 is proposed and evaluated. Theproposed strategy provides a conflict-free channel allocationfor 802.22-based multi-cell cognitive radio networks. In addition, it shows how out-of-band spectrum sensing can be donesuch that interruption of data transmission required by in-bandspectrum sensing can be avoided. In [19], the limitation of thecurrent MAC of the IEEE 802.22 standard with the hiddenincumbent problem is described and solved. A distributedsensing approach is proposed in [4] and a sensing approachbased on the cyclostationary properties of primary signalsis presented in [18]. In [20], the performance gains due tospectrum agility, where secondary users can track availablechannels, are compared to the case with no agility wheresecondary users keep sensing and accessing a fixed channel.In [10], a physical layer implementation for an OFDMAbased cognitive radio was proposed and its performance isinvestigated.Resource allocation in traditional OFDMA-based wirelessnetworks has been an active research topic. For the downlinkcase, there are several important resource allocation problems.The first one is to minimize the total transmission power whileproviding certain required transmission rates for different users[11], [12]. The second problem optimizes a given function ofthe transmission rates of the different users under a total powerconstraint at the base station [13]-[17]. These problems arereferred to respectively as margin adaptive and rate adaptivein the literature [13]. In [11], the authors propose an iterativealgorithm to solve the margin adaptive problem that may notbe suitable for highly dynamic wireless systems requiringfast solutions. In contrast, [12] proposes fast but suboptimalalgorithms where the number of subcarriers allocated to eachuser is first calculated and then the subcarrier allocation forall the users is performed.The OFDMA resource allocation problem investigated inthis paper is fundamentally different from existing work inthe literature in the following respects. First, except for [6]which is a single user, continuous rate allocation problem,there are extra power constraints given by the vector T as aresult of distributed spectrum sensing which are not present inthe existing literature. This new set of power constraints limitsthe transmit power on each allocated subchannel and rendersmany techniques unapplicable.For example, in [12] and [21] a multi-step allocation approach is proposed that first computes the number of channelsthat should be allocated to each user. This computation isbased on the average channel gain of each user and implicitlyassumes that other than for differing subchannel gains, allsubchannels are equally good, while this is clearly not thecase in the cognitive setting as some subchannels may havestringent transmit power constraints while others are free ofany primary user.In Section V-A, we will adapt a common multi-step approach (see for example [14]) to the problem at hand and findby numerical computations that the adapted method can havepoor performance in a cognitive setting, thus motivating thestudy of new methods.In addition, we explicitly consider buffer dynamics dueto finite bursty traffic patterns. While buffer dynamics havebeen considered before (e.g., [23]) we believe this to be thefirst setting in which max-min fairness and buffer dynamicsare jointly considered. By considering buffer dynamics, theproposed algorithms in this paper can avoid allocating toomuch radio resources to lightly loaded queues as done inmuch existing work. In addition, we allocate resources overmultiple time slots which improves the granularity of the radioresources allocation.III. S YSTEM M ODEL AND P ROBLEM F ORMULATIONWe consider an OFDMA downlink resource allocationproblem with M subchannels, N secondary users and onesecondary base station (referred to as the base station in thefollowing). Any one of z̄ transmissions modes (correspondingto a particular choice of coding and modulation schemes) canbe used on any subchannel where scheme z results in rateRz on a subchannel, i.e., Rz packets can be transmitted inone time slot over the subchannel. Without loss of generality,0 R1 R2 . . . Rz̄ and we denote R1 as the lowestrate transmission mode. Finally, to employ scheme z on asubchannel requires that the Signal to Noise Ratio (SNR) onthe subchannel be at least above a threshold γz to providesome desired block error rate.The base station has a maximum transmit power budget ofP̄max in every time slot and in the absence of primary users,can allocate Pany portion Pj of this power budget to subchannelj, provided j Pj P̄max .Due to distributed sensing, a vector T of power constraintsP̄j on each subchannel is available at the base station at thebeginning of a frame t (for ease of notation we omit the indext in the following), i.e., the base station must further limitPj P̄j to protect primary users where T {P̄j } (recall thatsince we focus on the downlink case only the base station cantransmit). P̄j is a function, among other things, of the criticalinterference threshold ω. In the case that there is no primaryuser on subchannel j, then P̄j as there is no primary toprotect, though the sum power constraint will provide a limitto Pj .We let gij denote the channel gain from the base stationto secondary user i over subchannel j at the beginning ofthe frame under consideration, and fij (z) be the minimumpower required to transmit from the base station to user i onsubchannel j using transmission mode z. fij (z) is a functionof the corresponding channel gain gij , the SNR thresholdγz , the noise power at the receiver and the interference fromprimary users, if any, on subchannel j.We assume that packets to be transmitted are buffered atthe base station and we denote by qi the number of packets

4waiting for transmission to secondary user i at the beginning ofthe frame. Given the backlog information, whenever possiblethe radio resources should be allocated to each user in sucha way that the corresponding allocated aggregate (over allsubchannels) rate is just sufficient to support the currentbacklog. A user that receives enough resources in the currentframe to take care of its backlog (i.e., the base station cantransmit all the queued packets of this user in the currentframe) is said to be satisfied while one that is not is saidto be highly backlogged.We are interested in finding the joint subchannel, rate, andpower allocation for all N secondary users which maximizesthe minimum aggregated rate among highly backlogged secondary users and hence provide some form of fairness amongthese users. While there many different notions of fairnessthat can be used, here max-min resource allocation is selectedbecause in a system with fixed users, no user should be treateddifferently based on its relative position to the base station.Recall that the frame length is L and for efficiency reasons theresource allocation is performed over 1 F L consecutivetime slots and repeated k L/F times to fill the frame.A resource allocation is then specified by the set of binaryvariablesS {sijzf {0, 1} i 1, . . . , N ; j 1, . . . , M ;z 1, . . . , z̄; f 1, . . . , F },(2)where sijzf 1 iff subchannel j is allocated to user i with rateRz in time slot f of the block. The set S {0, 1}N M z̄ Fof feasible resource allocations is given by those S S forwhichz̄N XXsijzf 1, j, f(3)i 1 z 1fij (z)sijzf P̄j ,z̄M XN XX i, j, z, ffij (z)sijzf P̄max ,(4) f(5)i 1 j 1 z 1Eq. (3) implies that a given subchannel and time slot cannotbe allocated to more than one pair (i, z). Eq. (4) ensures thatthe choice of coding and modulation schemes does not requirea transmission power that would harm a primary user, if any.Finally, eq. (5) is the per time slot constraint on the totaltransmit power of the base station.Given the set of feasible resource allocations S, we wish todetermine an allocation S S which optimizes the utility ofthe secondary network. In the absence of queue information,or equivalently if all users are infinitely backlogged (i.e., nousers can be satisfied in a frame), the utility that we considerin this paper is max-min which provides fairness in the sensethat this optimizes the smallest rate of any user. Specifically,given an allocation S, secondary user i is provided over theframe with the ratexi (S) : (L/F )Fz̄ XM XXj 1 z 1 f 1Rz sijzf(6)over the duration of the frame and the optimal network utilityunder the assumption of infinite backlogs is thenλ opt max min xi (S).S Si(7)To formulate the problem with queue backlogs (so as toavoid over-allocating resources) is somewhat less straightforward. Specifically, consider a user i who has the smallest backlog qi a at the beginning of the frame under consideration.Then it would seem that a resource allocation that does notresult in an over-allocated rate xi a would limit the (maxmin) network utility to at most qi a which is not desirable.We would like to satisfy as many users with small backlogsas possible and make sure that those with large backlogsreceive a fair share of the resources. We aim at allocatingeach highly backlogged user a rate which is at least as muchas any satisfied users and is max-min over all unsatisfied ones.Hence, we define a max-min utility over only the unsatisfiedusers. We first define the setΩ(S) : {i xi (S) qi }(8)of users for which the allocation S satisfies their queue andΩ(S) is the complement of Ω(S) and thus the set of users thathave not had their queues satisfied. The optimal utility of thesecondary network is then defined byλopt : max min xi (S),S S i Ω(S)(9)where we follow the usual mathematical convention that themin over an empty set is . Thus, an optimal resource allocation will satisfy each user’s queue if possible. If not, overproviding a satisfied user’s queue will not provide additionalutility.The problem formulated in (9) and (3) – (5) is a verylarge non-linear problem with integer variables due to thedependency of Ω in S. It is very general and captures several important resource allocation problems. For a traditionalOFDMA resource allocation problem, constraints (4) shouldbe removed while the case for which all users are infinitelybacklogged is obtained by setting qi since then (9)degenerates to (7) as no user has its queue satisfied.Finally, while the optimization given by (7) and (3) – (5)can be formulated as a linear integer program and thus solvedby an IP solver, this is not the case for the optimizationgiven by (9) and (3) – (5) as the set of users over which theminimization is performed depends on the choice of allocationS S.Clearly, one cannot hope to solve problem (9) and (3) – (5)exactly and fast enough (i.e., at the beginning of each frame).However, it is important to obtain exact (benchmark) resultsfor practical scenarios (i.e., of reasonable size) so that one cani) better understand the importance of some of the parameters;ii) validate the (fast) heuristics that will be developed. Thusin Section IV, an iterative solution to numerically solve theoptimization problem is presented since no commercial solvercan directly solve a non-linear integer program.Note: It may be tempting to try to solve these two problems byselecting F 1 and relaxing the sijzf to real numbers in theinterval [0, 1]. While the corresponding relaxed solution could

5be used to create a schedule, this schedule is not guaranteedto meet the required power constraints in each time slot, butonly on average over the entire schedule. Thus, there is noassurance of protecting the primary users in each time slot.Moreover, in the case of the problem given by (9) and (3) –(5), this does not change the non-linear nature of the problemdue to the utility in (9).ofλ maxS {sijzf }min {xi (S) µ(λnew , qi )} (12)isubject toz̄N XXsijzf 1,fij (z)sijzf P̄j ,IV. I TERATIVE S OLUTION U SING A N I NTEGER P ROGRAMS OLVER j, f(13)i 1 z 1 i, j, z, fz̄M XN XXfij (z)sijzf P̄max ,Fz̄ XM XXRz sijzf qi ,(14) f(15)i 1 j 1 z 1 i s.t. qi λnewj 1 z 1 f 1In this section, we show how the problem given by (9) and(3) – (5) can be solved exactly by solving a sequence of linearIP problems.We start by considering a modification to the objectivefunction in (9) asλ̄opt : max min [xi (S) µ(xi (S), qi )] ,S Si(10)where µ(x, q) is a function which is defined asµ(x, q) : 0,Λ,if x qif x q(11)where Λ is a sufficiently large number.This transformation can be interpreted as follows. For asecondary user i such that xi (S) qi , µ(xi (S), qi ) is largeenough that this secondary user will not be a bottleneck forthe min operation. Therefore, the min in the objective functionis only applied to secondary users with queue backlogs thatare not met and the optimal resource allocation for (9) and (3)– (5) is the same as that for (10) and (3) – (5).This transformation allows us to remove the dependency inS of the set over which the minimum is taken. However theproblem is still not suitable for a linear IP solver. We nowdiscuss how to obtain the optimal solution from an iterativeprocedure that invokes a linear integer program solver. Thisprocedure works by solving a modified problem where eachuser is required to have either a rate λnew or its queue satisfied.λnew is then iteratively increased until it reaches a maximumthat we denote λ .SolveCognitiveRAInit: λnew 0: λold 11) WHILE λnew 6 λolda) Use a linear IP solver to find the optimal solution(16)b) Update: λold λnewc) Update: λnew λ END WHILEWe now show that this iterative procedure will find theoptimal solution for our resource allocation problem.Proposition 1: The algorithm SolveCognitiveRA converges to an optimal solution of the resource allocation problem formulated in (10) and (3) – (5).Proof: Since µ(λ, q) is non-decreasing in λ, at every iteration, λ , the optimal value of the objective, is non-decreasing.Since the number of subchannels and the maximum rate oneach subchannel are both finite, the algorithm must convergeto some value λ′ .Now, we show that the converged value λ′ is an optimalsolution for the problem formulated in (9) and (3) – (5).Let λopt be the optimal objective value of (9) and (3) – (5).Also, suppose that the algorithm converges to λ′ λopt . This′means that substituting either λnew λ or λnew λopt into(12)–(16) yields a feasible solution. However, since λopt λ′is the optimal solution, there is an allocation such that anysecondary user i with qi λ′ will receive a rate at leastequal to its queue backlog while other secondary users (i.e.,those with qi λ′ ) can be supported at rates strictly largerthan λ′ . This is a contradiction because the solution in the lastiteration of the algorithm provides rates of at most λ′ for asecondary user i with qi λ′ . Hence, the iterative algorithmmust converge to the optimal solution.V. H EURISTICSIn this section, we consider two heuristics for the resourceallocation problem. The first is an adaptation of the multi-stepdecoupling heuristic of [14]. While the approach works wellin the absence of primary users, the adaptation to the cognitivecase does not work well in the presence of a large number ofprimary users in spite of adding an additional step. Thus, wealso consider a second heuristic which does not decouple theallocation in sub-problems. This heuristic is called selectivegreedy.A. Multi-Step ApproachThe multi-step heuristic has four steps. The first three areadapted from the three proposed in [14] and the last one is

6novel and is called the perturbation step in the following. Thedetails can be found in [22] and we restrict the description inthis paper to the broad concepts.Specifically, in Step 1, we perform power allocation overthe subchannels by sharing P̄max as uniformly as possibleconsidering the power constraints in vector T (i.e., there is nopoint allocating more than P̄j to subchannel j). This resultsin a subchannel being allocated either a power Pj P̄j or thesame power as any subchannel which is not at its limit P̄j .This power allocation is used in each of the F time slots.With the power allocation of Step 1 now fixed, we performsubchannel-time slot pair allocation in Step 2. Specifically,subchannel-time slot pairs are allocated to the secondary userssequentially where in each allocation iteration, a secondaryuser with the smallest rate is allocated one available pairachieving the highest rate subject to the power allocation inStep 1. Ties in the subchannel-time slot pairs are broken infavor of a pair with the highest channel gain.When a secondary user i has received enough resources tosatisfy its queue, i.e., it has received an allocation of at least qipackets, it is removed from the list of non-satisfied secondaryusers, and thus not allocated any more resources. If the “best”subchannel-time slot pair in any allocation iteration does notimprove the rate of the secondary user under consideration,then we cannot improve the utility function and we allocate allremaining available pairs to secondary users whose queues arenot yet fully satisfied in a round robin fashion in preparationfor the next step. Finally, the power allocated to a subchannelin Step 1 is usually larger than the power required to deliverthe assigned rate once it has been allocated to a secondary user.Therefore, after each subchannel-time slot allocation iteration,the residual power on the selected pair is calculated andallocated to the set of remaining subchannels in the time slotas evenly as possible considering the power limits due to T .Given the subchannel allocation solution from Step 2, thereis a potential max-min rate improvement by redoing rate andpower allocation. This is done in Step 3. Specifically, we sequentially increment the transmission mode of the most powerefficient subchannel-time slot pair that would n

Queue-Aware Resource Allocation for Downlink OFDMA Cognitive Radio Networks Patrick Mitran, Member, IEEE, Long Bao Le, Member, IEEE, Catherine Rosenberg, Senior Member, IEEE Abstract—In this paper we consider resource allocation for an OFDMA-based cognitive radio point-to-multipoint network with fixed users.