@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix skos: . vivo:departmentOrSchool "Applied Science, Faculty of"@en, "Non UBC"@en, "Electrical and Computer Engineering, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:identifierCitation "EURASIP Journal on Wireless Communications and Networking. 2015 Dec 22;2015(1):263"@en ; ns0:rightsCopyright "Hajipour et al."@en ; dcterms:creator "Hajipour, Javad"@en, "Mohamed, Amr"@en, "M. Leung, Victor C"@en ; dcterms:issued "2016-08-19T02:01:53"@en, "2015-12-22"@en ; dcterms:description "In this paper, we study resource allocation in buffer-aided relay-assisted OFDMA networks. We consider utility-based stochastic optimization framework where there are constraints to be met either instantaneously or in average sense. Using the well-known Lyapunov drift-plus-penalty policy, we extract the instantaneous problem that needs to be solved in each slot to control the data admission and allocate the time slots, power, and subchannels. We propose the parameters that should be taken into account in utilizing the drift-plus-penalty policy in relay-assisted cellular networks, for providing fair data admission and satisfying the average power constraints. We introduce a low-complexity strategy for power and subchannel allocation and propose distributed and centralized algorithms to utilize it. Specifically, the proposed efficient dynamic distributed resource allocation (EDDRA) scheme is suitable for use in practice as it imposes less overhead on the system and splits the resource allocation tasks among the base station (BS) and the relays. Extensive simulation results show the effectiveness of the proposed parameters in meeting the objective and the constraints of the studied problem. We also show that the proposed EDDRA scheme has close performance to the proposed centralized one and outperforms an existing centralized scheme."@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/58883?expand=metadata"@en ; skos:note "Hajipour et al. EURASIP Journal onWireless Communications andNetworking (2015) 2015:263 DOI 10.1186/s13638-015-0481-4RESEARCH Open AccessUtility-based efficient dynamic distributedresource allocation in buffer-aidedrelay-assisted OFDMA networksJavad Hajipour1*, Amr Mohamed2 and Victor C. M. Leung1AbstractIn this paper, we study resource allocation in buffer-aided relay-assisted OFDMA networks. We consider utility-basedstochastic optimization framework where there are constraints to be met either instantaneously or in average sense.Using the well-known Lyapunov drift-plus-penalty policy, we extract the instantaneous problem that needs to besolved in each slot to control the data admission and allocate the time slots, power, and subchannels. We propose theparameters that should be taken into account in utilizing the drift-plus-penalty policy in relay-assisted cellularnetworks, for providing fair data admission and satisfying the average power constraints. We introduce alow-complexity strategy for power and subchannel allocation and propose distributed and centralized algorithms toutilize it. Specifically, the proposed efficient dynamic distributed resource allocation (EDDRA) scheme is suitable foruse in practice as it imposes less overhead on the system and splits the resource allocation tasks among the basestation (BS) and the relays. Extensive simulation results show the effectiveness of the proposed parameters in meetingthe objective and the constraints of the studied problem. We also show that the proposed EDDRA scheme has closeperformance to the proposed centralized one and outperforms an existing centralized scheme.Keywords: OFDMA, Regenerative buffering relays, Distributed resource allocation, Low complexity1 IntroductionRelay-assisted orthogonal frequency division multipleaccess (OFDMA) networks are the promising solutionsfor providing high-speed data services in wide cover-age areas and therefore, they have been accepted in thestandardization bodies such as IEEE 802.16 [1] and longterm evolution-advanced (LTE-A) [2] for providing wire-less access to the customers. Resource allocation is animportant factor in utilizing the capacities of these net-works; while the combination of OFDMA and relayingtechniques results in high benefits and opportunities, italso brings challenges and issues that need to be addressedfor exploiting those opportunities [3]. There have beenextensive works in this area in the recent years. In [4], theauthors aimed at utilizing cross layer optimization frame-work for resource allocation in cooperative decode-and-forward (DF) relaying networks. For that, they introduced*Correspondence: hajipour@ece.ubc.ca1ECE Department, The University of British Columbia, Vancouver, CanadaFull list of author information is available at the end of the articlevirtual links and nodes to embed the cooperation mech-anism into the optimization framework. They assumedhalf-duplex relaying and also considered spatial reuse ofthe spectrum among the links with lower mutual inter-ference on each other. Using dual method, then, theymaximized the balanced end-to-end throughput. On theother hand, [5] considered reusing the OFDMA resourcesonly among the different access links (from the relays totheir users) and also suggested adaptive segmentation ofthe frame for transmissions on the base station (BS)-to-relay links and relay-to-user links. To optimize these, theauthors proposed linear-programming-based and greedyalgorithms which led to significant improvements in thesystem capacity. However, the proposed algorithms in[4, 5] were centralized which impose high computationalburden on the BS and high signaling overhead for report-ing channel state information (CSI) of the links. To alle-viate these drawbacks, several other works have studieddistributed resource allocation [6–9]. In [6], cross layerscheduling in an OFDMA amplify-and-forward (AF) relay© 2015 Hajipour et al. Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, andreproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to theCreative Commons license, and indicate if changes were made.Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 2 of 21network was studied to maximize the received goodputfor the relayed users, taking into account the effects ofimperfect CSI at the transmitter. Based on dual decom-position, a distributed algorithm was proposed for powerand subcarrier allocation. Similarly, [7] proposed a dis-tributed algorithm for power and subchannel allocationbased on dual decomposition, with the difference that theauthors studied multiple-input multiple-output (MIMO)transmissions in a system with the possibility to dynam-ically select full-duplex or half-duplex, and AF or DFrelaying. Pan et al. [8] investigated distributed power allo-cation algorithms in the presence of cognitive relays, basedon convex optimization. They considered the cases withand without fairness considerations, with and withoutlow signal-to-noise ratio (SNR) limitation on the BS-to-relay links, assuming fixed subcarrier allocations. More-over, they proposed a distributed scheme for joint powerand subcarrier allocation. In contrast with the aboveworks, [9] proposed a low-complexity semi-distributedalgorithm for power and subcarrier allocation, by con-sidering complete/limited information about the CSI ofthe relay-to-user links at the relays/BS and assigning thesubcarriers based on them. More other works studied fre-quency reuse schemes to improve the system capacity[10–12].The common assumption in most of the literature inthis area is that the relays do not have buffer to storepackets for later transmission. Therefore, they have toforward their received data immediately in the followingtransmission interval. Recently it has been shown that theuse of buffers in relays can improve the system capacity[13–15]. This is achieved as a result of more flexibilityin transmissions from relays. In other words, bufferingcapability in relays enables them to postpone the dataforwarding for a user if its channel is not good and usethe wireless resources for the links with higher quality ofchannel.Even though using buffers helps in compensating for theeffect of channels in wireless networks, it also brings newchallenges. In general, for better utilization of buffers, it isneeded to take into account the queue dynamics in them.In this regard, different problems arising in different partsof these networks have been addressed in the literature.Yang et al. [16] studied adaptive media playout for videostreaming, taking into account the queue dynamics in thereceiver. By monitoring the queue size and its variation,a model was developed for buffer underflow probabilityestimation which was exploited to smoothly control frameseparations of video traffic. In [17], a novel framework wasproposed for online source rate control, where a bufferoverflow probability (BOP) estimator monitors the queuesizes and its variation at the BS, and sends feedback aboutthe estimated BOP to the video source to control its bitrate.With the introduction of buffers in relays, several worksalso studied the challenges that arise for resource allo-cation in these networks. In [18], the authors studiedresource allocation in a system with quasi full-duplex(quasi-FD) relays, where each relay is able to simultane-ously receive and transmit on orthogonal channels. Theyconsidered symmetric traffic for the users and proposedcentralized algorithms for joint routing and subchannelallocation, to provide load balance among the cell nodesand fairness among the users. Compared with that, [19]studied a system with half-duplex (HD) relays where eachrelay can only receive in the first half of the frame andtransmit in the second half. Then, using queue-lengthcoupling across subframes, the authors proposed cen-tralized joint routing and subchannel allocation for eachsubframe and studied the system’s performance underboth symmetric and asymmetric data traffic. In [20], theauthors considered quasi-FD relaying and formulated aconvex optimization problem for joint power and sub-channel allocation. Assuming a single power constraintfor the whole system, a distributed resource allocationframework was proposed based on dual decomposition.On the contrary, [21] considered HD relays with individ-ual peak and average power constraints for the BS andrelays, and studied joint optimization for subframe, sub-channel, and power allocation in LTE-A systems, whereeach subframe can either be used for transmissions onthe BS-to-relays and BS-to-users links or the BS-to-usersand relays-to-users links. Using utility-based stochasticnetwork optimization [22, Chapter 5], and dual decompo-sition, optimal solution was provided for data admissioninto the network, and an iterative distributed algorithmwas proposed for reaching the optimal resource alloca-tion. In Table 1, we have classified the most relevantreferences cited above, based on the usage of buffer andcentralized or distributed approach of resource allocationalgorithms.The work in [21] is a pioneer in utilizing the Lya-punov drift-plus-penalty framework [22, Chapter 5] fordata admission and resource allocation in OFDMA relaynetworks. However, it does not take into account someconstraints and challenges that arise in practice in suchnetworks. In particular, the proposed iterative algorithmto get the optimal solution incurs very low convergencerate due to the separate power constraints for the BSTable 1 Classification of the most relevant resource allocationreferencesRelaying without bufferingCentralized [4, 5]Distributed [6–9]Relaying with bufferingCentralized [18, 19]Distributed [20, 21]Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 3 of 21and relays. This is not suitable for the practical sce-narios where the scheduling is performed in the unitsof millisecond. Also, it does not take into account theconstraint that might be imposed on the buffer capac-ity in relays. Other than that, in the drift-plus-penaltyframework, the average of a variable is defined overinfinite time horizon, which requires some considera-tions for achieving the desired objectives and satisfy-ing the constraints in practical systems. To the best ofour knowledge, none of the existing works on OFDMArelay networks has studied resource allocation with theabovementioned constraints altogether. This paper aimsat addressing these issues and filling the gaps highlightedabove.In summary, we study low-complexity utility-basedresource allocation in buffer-aided relay-assisted OFDMAnetworks, with HD relays, based on stochastic optimiza-tion framework presented in [22, Chapter 5]. We considerthe network utility as a function of average data admis-sion of the users and aim at maximizing it subject tothe long term and instantaneous constraints. Note thatin our previous work [20], data admission was not stud-ied. Also, the resource allocation problem only had asingle power constraint for the whole system, and therewas no constraint on the transmission rates of the sub-channels (like finite data availability and limited buffercapacity). Therefore, it was possible to convert it to aconvex optimization problem and use dual decompo-sition for power and subchannel allocation. However,in the current work, we consider several practical con-straints which necessitate a new solution approach. Inaddition to those constraints, the contributions of ourcurrent paper can be classified into two categories: onecategory is the identification of important factors thatshould be taken into account in the instantaneous prob-lem formulation. The other one is the design of low-complexity algorithms for solving the resource allocationsubproblem. Specifically, the main contributions are asfollows:• We identify the factors that need to be taken intoaccount for adapting the Lyapunov drift-plus-penaltypolicy for relay-based cellular networks. In particular,we propose to consider an importance parameter foraverage power constraint, to satisfy that constraint ina reasonable time period for practical scenarios. Also,we propose to add extra weight for the BS-to-relaysand relays-to-users links, in the cases that the fairnessis also an objective in the utility-based data admissioncontrol.• We aim at low-complexity algorithms for time slot,subchannel, and power allocations and highlight thechallenges even in such algorithms due to the lack ofa priori knowledge about the subchannel sets andtotal power usage of the BS and relays in each timeslot. Then, we propose a low-complexity strategy forbreaking the ties and making the correlationstractable, which can be used in both centralized anddistributed resource allocation implementations.• We focus on distributed mechanism for resourceallocation and propose low-complexity algorithms fordeciding about the type of time slot, subchannel setsof the nodes, and subchannel and power allocationsto the links of the nodes. Based on that, we alsopresent a low-complexity centralized mechanismwhich needs more signaling overhead and can beused as a baseline.• We take into account practical constraints such asHD relaying operation, average and peak powerconstraint for each of the BS and relays, as well aslimits on data availability and buffer capacity.• Using extensive simulations, we demonstrate theeffectiveness of the introduced parameters and alsoevaluate the performance of the proposed algorithms.We observe that the distributed scheme has veryclose performance to the centralized one andoutperforms an existing centralized scheme proposedin [19]. Also, we show that our proposed algorithmshave similar or even better performance comparedwith the iterative algorithm proposed in [21] forreaching the optimal solution.The rest of the paper is organized as follows. Section 2describes the system model and the stochastic problemformulations. In Section 3, we state the subproblems andchallenges as well as the proposed parameters and algo-rithms. Numerical results are provided in Section 4, withthe conclusion finally presented in Section 5.2 PreliminariesIn this section, we present the system model and thestochastic problem formulation. Then, we present thetransformed version of the problem and introduce thevirtual queues which make it possible to exploit the Lya-punov drift-plus-penalty policy in the next section. Here-after, for easiness, we will use the term “drift-plus-penalty”instead of “Lyapunov drift-plus-penalty”.2.1 SystemmodelWe consider the downlink of a single cell relay-assistedOFDMA network, as shown in Fig. 1. It is assumed thateach user is connected to either the BS or one of therelays, meaning that it receives service from only oneof them. This is decided at the beginning of users’ con-nection to the network and through handshaking proce-dures between the BS, relays, and users about the signalstrengths that users can receive from the BS and relays.Users, relays, and subchannels are indexed, respectively,Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 4 of 21Fig. 1 System model for buffer-aided relay-assisted networkby k ∈ K = {1, . . . ,K}, m ∈ M = {1, . . . ,M} and n ∈N = {1, . . . ,N}. Table 2 presents the key notations usedthroughout this paper. We use the term “serving node” orsimply “node” to refer to any of the BS or relays and showthe set of all nodes by B = {0, 1, . . . ,M}, where m = 0indicates the BS. Also, we useKm to denote the set of usersthat have a direct link to node m ∈ B. On the other hand,m(k) is used to refer to the node directly serving user k.We assume that time is divided into the units of slot,where each time slot can be either type A or type B. Intype A slots, the BS transmits to users directly connectedto it, or to the relays; in type B slots, the BS and relays cantransmit only to the users connected to them and there-fore, there is no transmission from the BS to relays. Thistransmission format is based on LTE-A with type 1 relayswhere the BS-to-relays transmissions and relays-to-userstransmissions use the same bandwidth but over differenttime slots, to prevent the interference between transmitand receive antennas.We assume that the MAC layers of the BS and relaysare equipped with buffers, where the BS has one for eachuser but every relay has one for each of the users con-nected to it. We denote the set of the users that have abuffer in node m ∈ B by Qm; therefore, we have Q0 = Kand Qm = Km,∀m ∈ M. These notations are defined tomake the formulations and algorithms shorter. The dataadmitted into a BS buffer are queued until transmissionto the corresponding direct user, or to the correspondingbuffer in the relay serving the user. Similarly, data arrivedat the relays’ buffers are queued until transmission to theirusers.Note that in the following, when we use the term “thelink of user k from nodem”, we mean “the link that servesthe queue of user k in node m”, which might be a directlink between the BS and a user, a feeder link between theBS and a relay or an access link between a relay and a userconnected to it. We use emkn(t) for the link of user k fromnode m to denote the channel gain-to-noise ratio at thereceiver side on subchannel n in time slot t. It is assumedthat the channel conditions of the links vary over time andfrequency, but remain constant during one time slot andover one subchannel. In the following, when we removethe (t) argument from the variables, we imply them ina general transmission incident. We assume that the BSand relays useM-ary QAMmodulation for their transmis-sions; therefore, the achievable transmission rate on thelink of user k from node m on subchannel n in time slot tcan be computed as follows [23]:rmkn(t) = B log2(1 + pmn (t)emkn(t)k), (1)where B is the bandwidth of a subchannel. k is the SNRgap due to the limited number of coding and modula-tion schemes and is related to the bit error rate of userk (BERk), through equation k = − ln(5BERk)1.5 [23]. pmn (t)denotes the power allocated by node m on subchannel nin time slot t. We indicate the total power used by nodem in time slot t as Pm(t) = ∑Nn=1 pmn (t). Using (1), thetotal transmission rate on the link of user k from nodem can be written as rmk (t) =∑Nn=1 xmkn(t)rmkn(t), wherexmkn(t) ∈ {0, 1} denotes the subchannel allocation indicatorwhich will be one if subchannel n is used for transmissionon the link of user k from node m in time slot t, and zerootherwise. Note that for any n, in type A time slot, xmknshould be set to zero for m ∈ M, k ∈ Km and in type Btime slot, x0kn should be set to zero for k ∈ K −K0.In each time slot, a resource allocation policy deter-mines the type of time slot, subchannel, and power allo-cations for the different links of the system. Based on that,the BS and relays transmit data from their queues, and atthe end, the queue sizes are updated as follows:Qmk (t + 1) = min[Lmk , max[Qmk (t) − Trmk (t), 0]+ amk (t)],∀m ∈ B, k ∈ Qm(2)Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 5 of 21Table 2 Notation SummaryNotation DescriptionN ,N Set and total number of subchannels, respectivelyM,M Set and total number of relays, respectivelyK, K Set and total number of users, respectivelyB Set of all the serving nodes, including the BS and relaysKm Set of users connected to nodemQm Set of users that have a buffer in nodemm(k) Serving node of user kT Duration of a time slotB Bandwidth of a subchannelk SNR gap for user kemkn(t), xmkn(t)Channel gain-to-noise ratio and subchannel allocationindicator of subchannel n in time slot t, respectively, for thelink of user k from nodemrmkn(t), r˜mkn(t)Achievable transmission rate and estimated achievabletransmission rate on subchannel n in time slot t,respectively, for the link of user k from nodemrmk (t) Total transmission rate on the link of user k from node min time slot tpmn (t) Power used by nodem on subchannel n in time slot tPm(t), Pˆm , PavmTotal power to be used in time slot t, peak powerconstraint and average power constraint, respectively, fornodemLmk ,Qmk (t) Capacity of MAC layer buffer of user k in node m and thequeue size in it in time slot t, respectivelyamk (t) Size of data arrived at the MAC layer buffer of user k innodem in time slot taˆ Upper bound of data admission into a buffer in the MAClayer of the BSJk , Yk(t), Ak(t) Capacity, queue size and the arrived data size in time slott, respectively, in the top layer buffer of user k in the BSU (.), V Utility function and the value coefficient for it, respectivelyγk(t),Gk(t) Auxiliary variable corresponding to data admission of userk and its corresponding virtual queue size, respectively, intime slot tZm(t), I Virtual power queue size of node m in time slot t and theimportance factor, respectively, corresponding to averagepower constraintsρmk ,We Indicator variable for the link of user k fromnodem and theextra weight, respectively, for providing fair data admissionN˜m , Nˆm Estimation of node m for its number of subchannels andthe upper bound considered by the BS on the number ofsubchannels for nodem, respectivelyDmn ,Dm Average demand of relaym on subchannel n and averagetotal demand of nodem, respectivelyD0an ,D0a Average demand of the BS on subchannel n and averagetotal demand of the BS, respectively, for type A time slotD0bn ,D0b Average demand of the BS on subchannel n and averagetotal demand of the BS, respectively, for type B time slotDA ,DB Total demand for type A and type B time slots, respectivelywhere T is time slot duration, and Lmk and Qmk (t), respec-tively, denote the buffer capacity of user k in node mand the size of data queued in it in time slot t. Dataarrival process amk (t) into a relay buffer is in fact thedeparture process from the BS, and therefore, we haveamk (t) = min[Q0k(t),Tr0k(t)],∀m ∈ M, k ∈ Km. Onthe other hand, the arrival processes in the BS buffersare managed through a data admission control policyin the MAC layer, which decides to admit data or notto admit from the queues of the top layer buffers inthe BS; this will be clarified in Section 3.2 and through(10). The size of the queues in top layer are updated asfollows:Yk(t + 1) = min[Jk , max[Yk(t) − a0k(t), 0]+ Ak(t)] , ∀k ∈ K(3)where Jk and Yk(t), respectively, denote the buffer capac-ity of user k in the top layer of the BS and the size ofdata queued in it in time slot t. Ak(t) is the amount ofdata arrived in time slot t for user k, according to anexogenous stochastic process, which is assumed to bestationary and ergodic. We assume that due to the pro-cessing limitations, an upper bound of aˆ is imposed onthe amount of data admitted into the MAC layer buffers,and therefore, we have a0k(t) ≤ aˆ,∀k, t. Note that inthe above, no specific assumptions have been consid-ered for queueing mechanisms other than the ordinaryfirst-in-first-out (FIFO) operation and the layer-basedarchitecture of data management, which has been con-sidered in [24] and [21] as well. In this paper, for sim-plicity, we have only considered the top layer and MAClayer in the BS and the MAC layer in the relays. How-ever, the discussions can be easily extended to the caseswhere the queueing in different layers are also taken intoaccount.2.2 Stochastic problem formulationWe note that in a realistic scenario, the BS buffers arenot infinitely backlogged and are fed by stochastic dataarrivals. This makes it necessary to take into accountthe queue dynamics, in the design of resource alloca-tion algorithms, in addition to the randomness causedby the wireless channels. Therefore, the average perfor-mance metrics become important for network opera-tors, and especially, the average throughput and averagepower constraints are the issues that need to be man-aged. In the following, we will explain these in moredetail.We define the time average expectation of a stochas-tic variable v(t) as v = limτ→∞ 1τ∑τ−1t=0 E[v(t)], accordingto [22, Chapter 4]. Considering the abovementioned, weaim at controlling the data traffic and resource allocation,Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 6 of 21by addressing the following stochastic optimizationproblem:maxa0,x,pK∑k=0U (a0k) , (4a)s.t. C1 : Pm ≤ Pavm , ∀m ∈ B, (4b)C2 : rmk (t)T ≤ Qmk (t), ∀m ∈ B, k ∈ Qm, (4c)C3 : r0k(t)T ≤ (Lmk − Qmk (t)), ∀m ∈ M, k ∈ Km, (4d)C4 : rmkn(t) ≤ Bsˆ, ∀m ∈ B, k ∈ Qm,∀n, (4e)C5 : a0k(t) ≤ min[aˆ,Yk(t)], ∀k ∈ K, (4f)C6 : a0k(t) ≤(L0k − Q0k(t)) ∀k ∈ K, (4g)C7 : Pm(t) ≤ Pˆm, ∀m ∈ B, (4h)C8 :∑m∈B∑k∈Qmxmkn(t) ≤ 1, ∀n ∈ N , (4i)C9 : {xmkn(t)} comply to the transmission rules ofeither type A or type B slot (4j)where U(.) is the utility function and C1 is to limit theaverage power consumption of each node.C2 shows that afinite amount of data can be transmitted from each queueand C3 is to prevent the incidents of more transmissionsto relay buffers than they can accommodate. C4 indicatesthe limit on the availability of modulation schemes, wheresˆ is the spectral efficiency of the highest order modulationin the system; considering it helps in controlling the powerallocation and preventing overflows from relays’ buffers(This will be explained clearly in Section 3). C5 and C6,respectively, show the limit on the data admission fromthe top layer buffers of the BS and the limit on the availablebuffer space in the MAC layer of the BS. C7 indicates themaximum instantaneous power, Pˆm, that node m can usefor transmissions, C8 shows that each subchannel can beallocated to only one link, and C9 is to use the feasiblevalues for subchannel allocation variables {xmkn}.The utility function in (4a) makes it possible to controlthe data admission for the users based on the objectiveof the network operator. For example for maximizing thetotal throughput, U(z) = z can be used or for providingproportional fairness, U(z) = log(z) can be considered[22, Chapter 5]. We assume that U(z) is a concave andcontinuous function of z.Note that the problem (4) has two types of constraints.While C1 needs to be satisfied in long term, C2 − C9state the constraints that must be met in each time slot.In particular, Pavm is different from Pˆm, as the former canbe set to limit the power consumption costs or the circuitheating but the latter is imposed by the system hardware(such as power amplifiers’ linear operation characteristicsor maximum available instantaneous power) and is largerthan Pavm .2.3 Transformed problem and virtual queuesWe note that the objective in problem (4) is a function oftime average of users’ data admission rate. In order to uti-lize the drift-plus-penalty policy, it is needed to have theobjective function as a time average expression. Similar to[22, Chapter 5], we define auxiliary variables 0 ≤ γk(t) ≤aˆ, k = 1, . . . ,K , corresponding to each a0k(t), k = 1, . . . ,K .Then, the problem (4) can be transformed into the follow-ing equivalent problem, in which the objective is the timeaverage of a function:maxa0,x,p,γK∑k=0U(γk), (5a)s.t. C1 − C9, (5b)C10 : γ k ≤ a0k ,∀k ∈ K, (5c)C11 : 0 ≤ γk ≤ aˆ (5d)We also define the virtual power queues Zm(t) and vir-tual auxiliary queuesGk(t), respectively, corresponding tothe constraints C1 and C10, with the following updatingequations:Zm(t + 1) = max[Zm(t) + Pm(t) − Pavm , 0] , ∀m ∈ B(6a)Gk(t + 1) = max[Gk(t) + γk(t) − a0k(t), 0] , ∀k ∈ K(6b)Based on the abovementioned, we are able now to definethe instantaneous problem (with the objective and con-straints stated in terms of the instantaneous values of thevariables) and study the algorithms for solving it, whichwill be presented in the next section.3 Cross layer traffic control and resourceallocationIn this section, we first describe the instantaneous prob-lem to be addressed in each time slot and propose someparameters that need to be included in it to make it suit-able for relay-assisted cellular networks. Then, we presentthe data admission subproblem and discuss the factorsinfluencing it. After that, we highlight the issues in solv-ing the resource allocation subproblem and propose alow-complexity strategy to address them. Then, we pro-vide a low-complexity distributed scheme which uses theproposed strategy through four steps to decide about theallocation of time slots, power and subchannels. Finally,we present a low-complexity centralized algorithm anddescribe its required steps.Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 7 of 213.1 Instantaneous problemTo address the problem (5), based on the drift-plus-penalty policy [22, Chapter 5], we define the “instanta-neous” problem in time slot t as follows:maxa0,x,p,γVK∑k=0U(γk) +K∑k=0Gk(t)[a0k(t) − γk(t)]+ IM∑m=0Zm(t)[Pavm − Pm(t)]+M∑m=0∑k∈Qm(Qmk (t) + ρmk We)[rmk (t)T − amk (t)], (7a)s.t. C2 − C9,C11 (7b)where V > 0 is the value that can be given to the objec-tive (5a), and by that, we can trade off higher utility tolarger queue sizes [22]. This will be clarified later. I >0, ρmk ∈ {0, 1} and We > 0 are the parameters that wepropose in this paper, to adapt the drift-plus-penalty pol-icy to relay-assisted cellular networks. I is the importancefactor that we give to average power constraint, throughwhich we can prevent the continuous growth of the virtualpower queues and consequently, we can meet the averagepower constraints in shorter time. We is an extra positiveweight, that can be given to the feeder links from the BSto relays and the access links from relays to users, in thecases that the fair admission of users’ data is of our con-cern. ρmk is the indicator variable to specify the cases toapplyWe; in particular, it is set to zero unless when the fairdata admission is desired and the corresponding queue(either in the BS or in a relay) belongs to an indirect user,i.e., k ∈ K − K0,m ∈ B. Proposition of I, ρmk and We isone of the main contributions of our paper and will be dis-cussed later. Based on the above, we can see that the workin [21] is in fact a special case of our work, in which I = 1,ρmk = 0,We = 0 and no limitations on buffer capacities ormodulation schemes are considered.It is observed from (7a) that, using the drift-plus-penalty policy, the instantaneous objective in each timeslot includes four terms: the first term corresponds to thelong term objective (5a) and the rest correspond to serv-ing the actual queues and stabilizing the virtual queues (tomeet the constraints C1 and C10).We note that due to thelimited buffer capacities, the actual queues of the systemare always stable. However, using drift-plus-penalty policyprovides a useful framework for channel- and queue-aware resource allocation which takes into account boththe channel states and the data availability in the sys-tem’s actual queues. It also makes it possible to stabilizethe virtual queues {Gk(t)} and {Zm(t)}. It is shown in[22, Chapter 5] that solving the instantaneous problemobtained from drift-plus-penalty policy in the case of infi-nite buffer capacities (i.e., when the constraints C3 and C6are not imposed) provides a utility (4a) that has a gap ofDV from its optimal value, where D is a constant related tosum of the squared data arrivals and squared transmissionrates. If the solution algorithm for instantaneous prob-lem (7) also leads to an approximate value of the objectivefunction (7a) within distance C from its optimal value(e.g., due to a suboptimal solution), then the aforemen-tioned gap will be D+CV . Therefore, there is anO(1/V ) gapbetween the optimal utility of the stochastic problem andthe utility obtained from solving the instantaneous prob-lem, which can be arbitrarily reduced by choosing a largeV. However, this will lead to larger queue sizes and delaysdue to the fact that the upper bound on the queue sizes hasan O(V ) expression. Recently, [25] has shown that in thecase of finite buffer capacity of β , the utility obtained fromdrift-plus-penalty policy is within O(1/V ) +O(e−β) of itsoptimal value. Note that [25] assumes that each node isallowed to transmit to the next hop even if it does not haveenough buffer space, in which case the received packet isdropped. However, this is not allowed in the system con-sidered in our paper, due to the constraint C3, as it willwaste the (expensive) frequency resources. This makesthe mathematical analysis of the drift-plus-penalty policydifficult in our system model and can be investigated infuture works.It is worth mentioning that considering V, I, ρmk , andWe in (7a) facilitates reaching our goals for system util-ity and constraints in different scenarios; neglecting themis in fact like setting them based on a fixed scenario (i.e.,V = I = 1 and We = 0) which would lower the use-fulness of the drift-plus-penalty policy. Note that V and Ican be tuned easily by considering the range of values forweighted rates in (7a), affected by packet sizes and trans-mission rates. On the other hand, ρmk can be easily set asstated above, when fairness is an objective; then, We canbe tuned by increasing its value from zero towards the val-ues in the range of queue sizes in relays, depending onhow much we trade off between data admission for thedirect and indirect users. These will get clearer in the nextsection, when we discuss their effects.Similar to [22], by rearranging the terms in the instanta-neous problem, it can be divided into three instantaneousSubproblems (SPs) which will be presented in the nextsubsections.3.2 Traffic control and data admissionThe first subproblem of (7) is related to the auxiliaryvariables as follows:SP1 (auxiliary variable subproblem) :maxγK∑k=1(VU(γk(t)) − Gk(t)γk(t)), (8a)s.t. 0 ≤ γk(t) ≤ aˆ,∀k ∈ K (8b)Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 8 of 21SP1 is a simple convex optimization problem and there-fore, the BS can solve it easily. As an example, for theproportional fairness, i.e., when U(γk) = log(γk), aftertaking the derivatives, the BS can determine the optimalauxiliary variables in time slot t through 1γk(t) =Gk(t)V =⇒γk(t) = min(aˆ, VGk(t)),∀k. After computing the solution,the BS can update the corresponding virtual queue sizesbased on (6b).The second subproblem of (7) is related to the flow con-trol and data admission into the users’ buffers in the MAClayer of the BS, as follows:SP2 (flow control subproblem) :maxa0K∑k=1(Gk(t) − Q0k(t))a0k(t), (9a)s.t. 0 ≤ a0k(t) ≤ aˆ,∀k ∈ K, (9b)a0k(t) ≤ min[Yk(t), L0k − Q0k(t)],∀k ∈ K (9c)which is a linear problem; by solving it, the BS can deter-mine the optimal data admissions in time slot t as:a0k(t) ={min[Yk(t), min[aˆ, L0k − Q0k(t)]],Q0k(t)≤Gk(t)0 , otherwise(10)Based on the above, for deciding about data admis-sion for user k, the BS needs the information about itstop layer queue size Yk(t), MAC layer queue size Q0k(t),auxiliary variable’s virtual queue size Gk(t), maximumadmissible data size aˆ, and the MAC layer’s buffer capac-ity L0k . All of these information are accessible to the BSas the related buffers and queues are implemented inthe BS. aˆ and L0k are fixed parameters; Yk(t), Q0k(t) andGk(t) are in fact the input variables to the data admissionprocedure in the MAC layer of the BS and the decisionabout the size of admitted data is the output. This isclarified in Fig. 2. After determining data admissions andtransmissions (discussed later), the BS can use (2) and (3)to update the affected queue sizes. It is worth mention-ing that the data admission procedure presented aboveis based on [22, Chapter 5], and its inclusion here is forcompleteness of the discussions presented later.Note that based on (10), whenever the size of an actualqueue at the BS, Q0k(t), is larger than the virtual queueGk(t), no data is admitted into the corresponding BSbuffer. This can happen for several time slots, in buffer-aided relay-assisted cellular networks, due to the admis-sion of a large packet and low service rate of the queueof an indirect user at the BS (which is caused by thedifferential backlog terms described in the next subsec-tion). Consequently, even using a utility function withfairness property and large value for parameter V doesnot necessarily lead to fair data admission, and therefore,more considerations are needed in resource allocation forserving the queues. This is the motivation for proposingρmk and the extra weight We (explained clearly later, inRemark 1), which help to improve the fair data admissionfor indirect users.3.3 Resource allocation challengesBy substituting (1) in (7a) and removing the constantterms, the last and most important subproblem, whichis to decide about the time slot, subchannel and powerallocations, can be stated asSP3 (resource allocation subproblem) :maxp,xN∑n=1M∑m=0⎛⎝ ∑k∈QmBTwmk (t) log2(1 + pmn (t)emkn(t)k)− IZm(t)pmn (t)⎞⎠ , (11a)s.t.C2 − C4,C7 − C9 (11b)Fig. 2 The diagram of the inputs and output of data admission procedureHajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 9 of 21where w0k(t) = Q0k(t), k ∈ K0 (weights for the direct linksfrom the BS to its users; recall that ρ0k is always equal to 0for these links), wmk (t) = Qmk (t) + ρmk We,m ∈ M, k ∈ Km(weights for the access links from relays to their users),and w0k(t) = Q0k(t) − Qm(k)k (t) + ρ0kWe,∀k ∈ Q0 − K0(weights for the feeder links of indirect users from the BSto relays). The differential backlog term Q0k(t) − Qm(k)k (t)in the weight of a feeder link is resulted by switching thesums and considering the fact that for the buffers of therelays, the arrivals are upper bounded by the transmis-sion rates from the BS to relays, i.e., amk (t) ≤ r0k(t),∀m ∈M, k ∈ Qm. As explained in the previous subsection, andlater in Remark 1, these differential backlog terms lead tounfair data admission for indirect users, and their effectcan be reduced by using ρmk We terms.We note that SP3 is a mixed integer and nonlinearprogramming and needs an exhaustive search to find itsoptimum solution. One common approach for these typesof problems is to relax the subchannel allocation variablesxmkn whenever this relaxation converts the problem intoa convex one. Then, using the dual decomposition, opti-mal solution can be found, if the duality gap is zero. Thisapproach was used in our previous work in [20], based onwhich we proposed a dynamic distributed resource allo-cation. However, in the current paper, due to the finitedata and limited buffer capacity constraints, i.e., C2 andC3, the resulted problem after relaxation of xmkn variableswill be non-convex. In addition, we note that in [20], therewas only one power constraint for the whole systemwhichmade it possible to have high convergence speed for theproposed algorithm. In amore realistic system like the onewe consider in the current paper, the BS and relays haveseparate power constraints. Therefore, even if we removethe constraints C2,C3 and relax xmkn variables to make itconvex, a dual-based iterative algorithm will need manyiterations and a long time to converge. This is not suit-able for use in practical scenarios where each time slotis in the order of a millisecond, and the resource allo-cation decision needs to be made in a small fraction oftime.Due to the abovementioned, we aim at low-complexitysuboptimal algorithms which can be easily implementedin practical systems. For this purpose, we consider equalpower allocation on subchannels and allocate them in agreedy way, based on the queue sizes and achievable trans-mission rates of the links. This is not only for makingthe resource allocation practical, but it is also reasonable,because when adaptive transmission rates are used (as inour system by (1)), optimal power allocation results inmarginal gains [26].However, even considering equal power distribution onsubchannels and computing the achievable transmissionrates of the links is not trivial here, due to the followingtwo issues:a) Unknown number of subchannels for each node. Fordeciding about the allocation of subchannels, weneed to know the achievable transmission rates of thelinks on the subchannels, and for that we need toknow the power allocations on the subchannels.However, before subchannel allocation, it is not clearhow many subchannels will be allocated to the BSand relays, and consequently, it is not known on howmany subchannels their total powers will bedistributed equally.b) Unknown total powers to be used by each node. Thetotal powers used by each of the BS and relays needto satisfy the average and peak power constraints.This is controlled in SP3 by constraint C7 and theobjective function which is the sum of increasing anddecreasing functions of power. Based on that, thetotal power used by each node can vary in each timeslot between zero and its peak value, depending onthe subchannel allocations and the size of thecorresponding virtual power queue. Therefore, evenif we make an assumption on the number ofsubchannels to be used by each node, it is not clearthat how much total power will be distributed equallyon them.To address the above issues, we propose a low-complexity suboptimal strategy, as shown in subchanneland power allocation strategy (SPAS), which breaks theinterdependence between power allocation and subchan-nel assignment. At the beginning, SPAS assumes thatSubchannel and power allocation strategy (SPAS)• Assume the number of subchannels that node m willuse for its transmissions, N˜m, will be proportional tothe number of its queues.• Assume that each node m will use its peak power(which will be equally distributed on its subchannels,i.e., it will use PˆmN˜m for transmission on each of itssubchannels).• Estimate the achievable transmission rates of thelinks of the nodes based on their channel conditionsand the abovementioned assumption for powers.• Determine the type of time slot and allocate thesubchannels to the system links, based on theestimated achievable transmission rates and actualqueue sizes.• Adjust the total power that node m should use, byconsidering the size of its actual data queues andvirtual power queue; then, distribute it equally on thesubchannels assigned in the previous step to the linksof node m.Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 10 of 21the number of subchannels that each node will use forits transmissions will be proportional to its number ofqueues, and the total power each node will distribute onits subchannels will be its peak power. Based on that,SPAS estimates the transmission rates of the links to beused in making a decision about the type of time slot andsubchannel allocation. At the end, it adjusts the total pow-ers, considering the size of actual and virtual queues. Thedetails for these are presented in the next subsections.Note that SPAS in fact provides a plan which can be uti-lized for designing the resource allocation algorithms ina centralized or distributed way. In the following, we willpresent the distributed implementation, as it is of moreinterest to the research and industrial bodies; later, we willdescribe the centralized resource allocation which can beused as a baseline for the proposed distributed one.3.4 Efficient dynamic distributed resource allocationIn this subsection, we propose the EDDRAmethod whichperforms resource allocation in each time slot, throughfour steps. In the first step, every node reports estimatesof its subchannel demands to the BS and based on them,the BS decides about the type of time slot. In the sec-ond step, the BS determines and reports the subchannelsets that each of the BS and relays can use. Then, in thethird and fourth steps, in a distributed way, each node firstassigns the subchannels to its users and then adjusts thetotal power it can distribute over its subchannels.Step 1) Slot Type Determination (STD). At the end ofeach time slot, first, the BS needs to specify the type ofthe next slot. For this, relays report an estimate of theiraverage demand for each subchannel to the BS. Thesedemands are computed based on the assumptions on thenumber of subchannels they can get and the total powerthey can use. Then, the BS uses the reported demandsfrom the relays as well as its own demands to estimate thesystem’s total demands for type A and type B slots, andbased on that, it decides about the type of the next timeslot. This is outlined in STD algorithm and the details aredescribed in the following.Based on SP3, we define the estimated average demandof nodem ∈ M on subchannel n asDmn =1|Km|∑k∈Kmwmk r˜mkn,∀m ∈ M,∀n ∈ N (12)where r˜mkn = log2(1 + PˆmemknN˜mk)is the estimated transmis-sion rate of the link of user k from nodem on subchanneln. It is computed in node m, m ∈ M, assuming thatthe number of subchannels it will get, N˜m, is proportionalto the ratio of its number of queues (|Km|) and the totalnumber of queues that can be considered for service intype B slot(∑m∈B |Km| = K); i.e.,N˜m = N |Km|K ,∀m ∈ B, (13)Since the BS knows the number of queues in each relay,it can easily estimate their total demands as in line 2 ofSTD algorithm. For itself, the BS needs to compute sepa-rate demands for type A and type B slots. Noting that intype B slots, it can only transmit to its direct users whilesharing subchannels with relays, its average demands arecomputed similar to relays and based on the weights andrates of the links of direct users (assuming the transmis-sion power on each subchannel equal to Pˆ0N˜0 , N˜0 = N|K0|K ),i.e., D0bn = 1|K0|∑k∈K0 w0k log2(1 + Pˆ0e0knN˜0k).Algorithm 1 Slot Type Determination (STD)1: Each relaym∈M reports to the BS, its estimatedaverage demands on all subchannels, i.e., Dmn ,∀n ∈ N .2: The BS estimates the total demand of each relaym asDm = |Km|∑Nn=1 Dmn ,m ∈ M3: The BS estimates its own demand for type A slot asD0a = K∑Nn=1 D0an4: The BS estimates its own demand for type B slot asD0b = |K0|∑Nn=1 D0bn5: The BS estimates the total demand for type A slot asDA = D0a, and for type B slot as DB = D0b+∑Mm=1 Dm6: if DA > DB7: The BS sets the type of slot to A8: else9: The BS sets the type of slot to B10: end ifOn the other hand, we note that in a type A slot,only the BS can transmit and all the queues in the BS(including those of indirect users) can be served usingall the subchannels; thus, its total demand is computedbased on the weights and rates of all of its links andassuming Pˆ0N power on each subchannel, i.e., D0an = 1K∑k∈K w0k log2(1 + Pˆ0e0knNk).Note that for computing the demands in the BS, it needsto know the queue sizes of the relays as well (to be usedin the weights of the feeder links from the BS to relays).For this purpose, relays also report the information abouttheir modified queue sizes, to the BS. Considering the factthat in each time slot, at most N different queues can beserved, the maximum number of modified queue sizes inHajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 11 of 21relays is min(K − |K0|,N)). Therefore, in EDDRA, thetotal overhead of signaling about the demands and themodified queue sizes is of O(min(K − |K0|,N) +MN).Remark 1. Here, we explain the reason for using ρmk Wein the weights of the links of indirect users from the BSand relays. Without that, due to the low powers of relaysand low transmission rates, their demands would not becomparable to the demands of the BS for direct users,unless the queues in relays grew large. On the other hand,for the links serving the queues of indirect users in theBS, we would have w0k = Q0k − Qm(k)k ,∀k ∈ K − K0. Asa result, these would not have enough impact on comput-ing the average demands for indirect users and providingservice for them (in the cases that the queue sizes ofan indirect user in the BS and relay have the same size,Q0k = Qm(k)k , the impact would be zero). Consequently,the queues of indirect users in the BS would usually havelarger sizes than the queues of direct users, and there-fore, data admission for them would be less. This woulddegrade the usefulness of drift-plus-penalty for cellularnetworks, because fairness is usually one of the main con-cerns in these networks. To prevent that, ρmk should beset to 1 for the feeder and access links and We should beapplied as mentioned in subsection 3.1. This will compen-sate for the effect of low power of relays on the demandsof access links and the effect of differential-backlog-based weights on the demands of feeder links. Similareffect holds also in the subchannel sets determinationand subchannel allocation steps which will be describedlater.Step 2) Subchannel Sets Determination (SSD). Wenote that in a type B slot, due to sharing subchannelsamong all the nodes, the resource allocation for the linksof different nodes are tied together which is reflectedin (11). In this step, the goal is to break this tie and specifythe subchannel sets to be used for transmissions from theBS and relays. This allows to have the resource allocationin a distributed manner at each node.For the above purpose, when the slot is decided to betype A, the BS notifies the relays about it and they knowthey have no transmissions. In the case of a type B slot, theBS determines the subchannel sets of the relays and noti-fies them to transmit on them. SSD algorithm shows thewhole procedure in detail. Since in type B slots, the BS canonly transmit to the direct users, line 5 of the algorithmdefines its demands based on the estimations for type Bslot, explained before. Line 6 sets Nˆm, as the upper boundfor the number of the subchannels that each node can get,and the next lines assign the subchannels to the nodes thathave not reached their limit on the number of subchannelsand have higher average demands on the subchannels.Algorithm 2 Subchannel Sets Determination (SSD)1: if the slot type is A2: The BS determines subchannel sets asN0 = N andNm = ∅,m ∈ M3: else4: The BS specifies subchannel sets, based on the relays’demands as well as its own, as follows5: Set D0n = D0bn6: Set Nˆm =⌈N |Km|∑Nn=1 Dmn∑Mm=0∑Nn=1 |Km|Dmn⌉,∀m ∈ B7: InitializeN ′ = N ,B′ = B,Nm = ∅,∀m ∈ B′8: whileN ′ = ∅ and B′ = ∅9: find (m∗, n∗) = arg maxm∈B′,n∈N ′Dmn10: Nm∗ = Nm∗ ∪ {n∗}11: N ′ = N ′ − {n∗}12: if |Nm∗ | = Nˆm∗13: B′ = B′ −m∗14: end if15: end while16: end if17: The BS notifies relays about their subchannel setsNote that setting the limit Nˆm for the size of the sub-channel set of node m is to prevent node m from gettingsubchannels more than it needs. For example, a relaymight have only one user with high average demands onthe subchannels while another relay with several usersmight have a little lower average demands on the subchan-nels. In such a case, without considering the total numberof users and the limit for subchannel set sizes, the relaywith a single user would overshadow the other relay in allthe iterations of subchannel assignments through line 9.The computational complexity of the SSD algorithmis of O((M + 1)N2), which is obtained by ignoring theinsignificant computations and considering the number ofiterations needed for performing line 9.Step 3) Subchannel Allocation (SA). After determin-ing the subchannel sets, the resource allocation sub-problem (11) can be further decomposed into separatesubsubproblems, as follows:SSP (resource allocation subsubproblems) :maxp,x∑n∈Nm∑k∈Qm(BTxmkn(t)wmk (t) log2(1 + pmn (t)emkn(t)))−∑n∈NmIZm(t)pmn (t),∀m ∈ B, (14a)s.t.C2 − C4,C7 − C8 (14b)where each node knows its set of subchannels and candecide individually about allocating them to its own links,considering the related subset of the constraints C2−C4,Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 12 of 21C7 − C8. For this purpose, following the SPAS strat-egy, we propose to have subchannel allocations by eachnode based on using Pˆm|Nm| (i.e., assuming Zm(t) = 0)for computing the achievable transmission rates. Thenin the power adjustment step, considering the real valueof Zm(t), each node can decide about the total power itshould use and distribute it on its subchannels.Algorithm 3 Subchannel Allocation (SA) in the BS1: if slot type is A, setQ′ = Q0 , otherwise, setQ′ = K02: Initialize q0k = Q0k , r0kn = B log2(1 + Pˆ0e0kn|N0|k), k ∈Q′, n ∈ N0.3: whileN0 = ∅ and( ∑k∈Q′q0k > 0)4: Compute w0k = q0k , k ∈ K05: Compute w0k =(q0k − Qm(k)k), k ∈ Q′ −K06: if Q0k > BTsˆ,w0k = w0k + ρ0kWe, k ∈ Q′7: if Lm(k)k − qm(k)k < BTsˆ,w0k = −1, k ∈ Q′ −K08: Compute D0kn = w0kr0kn, k ∈ Q′, n ∈ N09: Find (k∗, n∗) = arg maxk∈Q′,n∈N0D0kn10: x0k∗n∗ = 111: N0 = N0 − {n∗}12: if k∗ ∈ Q′ −K0, then qm(k∗)k∗ = qm(k∗)k∗+min (q0k∗ ,Tr0k∗n∗)13: q0k∗ = max(q0k∗ − Tr0k∗n∗ , 0)14: end whileNoting that the BS has more constraints than the othernodes (the constraint C3 is only enforced on the feederlinks from the BS, which is to prevent transmitting data tothe relays more than their empty buffer spaces), we pro-vide the subchannel allocation by the BS and then explainits use for relays. SA algorithm shows the details in allo-cating the subchannels by the BS. The procedure is donein an iterative way with |N0| iterations. In each itera-tion, the weights of the links and the resulted demandsare computed, and the pair of subchannel and queue withthe highest corresponding demand is selected. Then, theselected subchannel is assigned to the link serving theselected queue and the size of the affected queues areupdated virtually. Since the actual queue sizes, Qmk , areonly updated at the end of transmission intervals, we haveused qmk variables to prevent ambiguity about the updatingduring the algorithm iterations. Note that these updatesare done to meet the constraints C2 and C3. Line 6 isfor applying the extra weight We, described before. How-ever, before adding it, by comparing the queue size withBTsˆ, we make sure that there are enough data such thatthey can utilize the subchannel completely if it is allocated.Line 7 is to meet the constraint C3 and prevent overflow,by giving a negative weight in case the remaining emptyspace in a relay buffer is less than the possible maximumtransmission size on a subchannel. If a feeder link getsnegative weight, then it will not be considered for sub-channel allocation and this will prevent transmitting datato the corresponding relay buffer.Remark 2. Note that the rate computations in SA arebased on the assumption of equal distribution of peakpowers on the subchannel sets. This way, we will be surethat when in Step 4, the total power is adjusted (whichcertainly will be equal or less than the peak power), thetransmission rate for each link will be less than the amountconsidered in SA algorithm, and therefore, the constraintsC2 and C3 will not be violated.In type B time slots, in parallel to the BS, any relayalso uses the SA algorithm with the difference that all thesuperscripts/subscript 0 are replaced by the correspond-ing m. Note that in this case we have Q′ = Km andQ′ − Km = ∅. Hence, the lines 5, 7, 12 are not executedwhen SA algorithm is used by relays. Based on the above-mentioned, the subchannel allocation task in EDDRA issplit among the serving nodes, where the computationalcomplexity of the SA algorithm in any node m ∈ B is ofO(|Nm|2|Qm|).Step 4) Total Power Adjustment (TPA). After assign-ing the subchannels to the links, the BS and relays decideabout the total power that they can distribute on their sub-channels to meet the constraints C4,C7. For this, basedon SSP in (14), each nodem solves the following problem,which we refer to as the total power adjustment, to findthe total power, Pm, that it can use.TPA (total power adjustment problems) :maxPm∑n∈Nm(BTwmk(n)(t) log2(1 + Pm(t)emk(n)n(t)|Nm|k))−IZm(t)Pm(t),∀m ∈ B (15a)s.t. 0 ≤ Pm(t) ≤ Pˆm (15b)In the above, k(n) indicates the index of the user, to thequeue of which the subchannel n has been allocated. TheTPA problem is a convex problemwith one variable. Thus,the optimal value, P∗m, can be found easily by using an iter-ative one-dimensional search such as the Golden Sectionmethod [27, Appendix C.3], which has the computationalcomplexity ofO(log(1/1)), where 1 is the desired relativeerror bound.Remark 3. As explained before, the constraint C1 isenforced over time through the virtual queues, {Zm},Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 13 of 21defined for that purpose. In fact, based on (6a), having anonzero Zm means that in the past time slots, there havebeen the events of transmission with the total power, Pm,larger than the average power limit, Pavm . Therefore, in TPAproblem, Zm applies a kind of negative feedback to useless power than Pˆm. The proposed importance factor I isin fact for amplifying this negative feedback to adjust thetotal power use in a short period of time. Without it, thesecond term in the objective (15a) would not be compara-ble to the first one over a large period of time slots, beforeZm becomes big enough to impact the objective value.This is due to the fact that the values of the power vari-ables are very small (in the order of 1–10 watts) comparedto the values of queue sizes multiplied by transmissionrates (in the order of tens of megabits).After finding P∗m as described above, each node com-putes the power on its subchannels, considering equalpower distribution and noting that the rate on each sub-channel can not be larger than Bsˆ (due to the limitedspectral efficiency of modulation schemes in practice); i.e.,pmn = min(P∗m|Nm| ,(2sˆ − 1)k(n)emk(n)n),∀m ∈ B, n ∈ Nm(16)The reason for considering the term with sˆ in (16) is toprevent using the power more than needed for maintain-ing the desired bit error rate. It is obtained based on (1)and C4.After the above steps, based on the variables xmkn and pmn ,each node notifies its users about the subchannel alloca-tions and the assigned transmission rates. Then, it trans-mits to them and updates its actual and virtual queuesusing (2) and (6).Remark 4. As discussed in subsection 3.3, the resourceallocation subproblem (11) is not a convex optimiza-tion problem; therefore, the existence of global optimal isunknown. The algorithms proposed in the STD, SSD, SA,and TPA steps provide a suboptimal solution which havelow overhead and low computational complexity, and, asshown in Section 4 (Figs. 5, 6, 7, 8, 9, and 10), lead to betterperformance compared with an existing suboptimal algo-rithm. Moreover, to the best of our knowledge, even whenthe constraints C3 and C6 are not imposed (i.e., assum-ing infinite buffer capacities), there is not a clear methodto compute mathematically the distance of our proposedscheme from the optimal solution of the correspondingconvex optimization problem, as it is heuristic. However,as shown in Section 4 (Figs. 13, 14, 15, and 16), depend-ing on the value ofV in this case, our proposed algorithmscan lead to higher or slightly lower system utility (at thecost of higher queue sizes) compared with an existingalgorithm which uses subgradient method to reach theoptimal solution.Remark 5. Note that the Steps 1 to 4 are executed onlyonce in each time slot. Also, STD, SSD, and SA algorithmshave a fixed number of iterations/operations after whichthey terminate, and there is no need to analyze their con-vergence. On the other hand, as stated in Step 4, TPAproblem is a single-variable convex optimization problemand therefore, any one-dimensional search is guaranteedto terminate when reaching the specified tolerance of 1.3.5 Efficient dynamic centralized resource allocation(EDCRA)In this subsection, we briefly describe the EDCRAmethod, in which the BS performs all the procedures forresource allocation. In a centralized scheme, the BS needsto get notified about the channel states of all the links inthe system over all the subchannels1. For this purpose,since the indirect users do not have connection to the BS,the relays report to the BS about the channel conditions ofthe access links (which already have been reported by theindirect users to their serving relays). This imposes a sig-naling overhead of O((K − |K0|)N) from relays to the BS.Considering the fact that in practice the number of usersis remarkably more than the number of the relays, the sig-naling overhead in EDCRA is a lot more compared withEDDRA2 (which is of O(min(K − |K0|,N) +MN)).Having all the information about the channel states andthe queue sizes, the BS performs STD procedure and ifthe slot type is set to A, it uses the SA algorithm as inEDDRA. However, if the slot type is set to B, the BS doesnot need to run SSD algorithm. Instead, considering theset of all the subchannels, it uses SA algorithm as fol-lows. The queues in relays are assumed to be located inthe BS, and their corresponding access links are assumedas direct links starting from the BS to the indirect users;however, the weights and channel rates are considered thesame as those of actual access links. Then, SA algorithmis exploited to decide about the subchannel allocation tothe different links in the system, which incurs the compu-tational complexity of O(N2(∑m∈B |Km|)) = O(N2K).After that, based on the corresponding subchannel allo-cations for all the nodes, i.e., {xmkn}, the BS specifies thepowers to be used by each node by performing the totalpower adjustments for them. Finally, the BS informs all therelays about the subchannels and powers they can use.Remark 6. Wenote that the algorithms proposed in thissection do not consider any strict quality of service (QoS)requirement such as packet delay thresholds for the users.Therefore, they are mostly suitable for the data admissionand resource allocation in the case of best effort services.However, the heuristics used here can provide insightsHajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 14 of 21for future works to design data admission and resourceallocation algorithms in the presence of the services withstrict QoS requirements.4 Performance evaluation and discussionTo evaluate the performance of the proposed algorithms,we have conducted extensive simulations for a systemwithM=6 relays, which are located in the distance of 2/3 ofthe cell radius from the BS and in an equal angular dis-tance from each other. The simulation parameters areas in Table 3, unless otherwise specified. For the linksfrom the BS to relays, channels are assumed line-of-sight(LOS)-based and therefore, Rician channel model, with κfactor equal to 6 dB, is considered; for the links betweenthe BS/relays and users, channels are assumed non-LOS(NLOS)-based and therefore, Rayleigh channel model isused [28]. For computing the path loss of the links, wehave considered the COST231 Hata urban propagationmodel which uses the following equation [29]:PL = (44.9 − 6.55 log10(htx)) log10( d1000)+ 45.5+ (35.46 − 1.1hrx) log10(fc) − 13.82 log10(htx)+ 0.7hrx + 3,(17)where PL is the path loss in dB, htx is the transmit-ter antenna height in meters, hrx is the receiver antennaheight in meters, fc is the carrier frequency in MHz, andd is the distance between the transmitter and receiverin meters. The above model for path loss has been con-sidered in [29] for urban Macrocell environment, wherethe distance between the BS of the adjacent cells is largerthan 1 km. Due to the fact that using relays in cellularnetworks makes it possible to have a large coverage areafor a single cell, served through the BS and relays, weTable 3 Simulation parametersParameter name SettingCell radius 1000mBS antenna height 15mRelay antenna height 10mUser antenna height 1.5mCarrier frequency 2500 MHzSubhannel bandwidth 180 KHzTime slot duration 1msNoise power spectral density –174 dBm/HzBER requirement 10−6Traffic model PoissonPacket size 5 KBitshave assumed the network environment as urban macro-cell and have used the above equation. We acknowledgethe fact that, in reality, the channel behaviors in cellularnetworks might be different from the models consideredin our simulations. However, considering the fact that thesame models have been used in simulating the behav-ior of the baseline algorithms existing in the literature,the relative performance improvements of our proposedalgorithms, presented later, are expected to hold.For utility function, we have considered U(z) = log(z)to provide proportional fairness. Due to the large packetsizes which resulted in large queue sizes, based on theobservations from simulation results, we have chosenV tobe 107. This gives high value for utility function in (7a) tobe comparable to the terms related to the weighted trans-mission rates. The buffer capacities at the BS and relaysare considered equal to 100 and 10 packet sizes, respec-tively. The highest order for modulation is assumed to be64QAMwhich has the spectral efficiency of 6 bits/sec/Hz.In the following, we first consider a special scenario withthe settings as follows. The data arrival rate of each useris 100 packets per second, or equivalently 500 kbps. Thepeak power of the BS is equal to Pˆ0 = 34 dBm and thepeak power of the relays are equal to Pˆm = 25 dBm,m ∈ M. The average power constraint of the nodes arehalf of their peak power constraints, i.e., 31 dBm= 1259mW for BS and 22 dBm= 158 mW for relays. The num-ber of subchannels is considered equal to N = 7. Thereare 12 users in the system, 6 of them connected directly tothe BS and the rest connected to relays, one user per relay.The distances of the direct users from the BS and the indi-rect users from the corresponding relays are 300 m. Notethat this special scenario, with the mentioned settings, isto provide an example to show the necessity of consid-ering the importance parameter I in practical scenarios.The values of the different parameters are selected specif-ically for simulation purpose. However, in practice, thesevalues are possible. For instance, the indirect users’ loca-tion are considered 300 m from relays to simulate the casethat those users are close to the cell edge, and the directusers location is selected 300 m from the BS to simulatean average location between the BS and relays. On theother hand, the number of subchannels is selected equal toseven to have, on average, one subchannel for each of theserving nodes (the BS and six relays). Even though sevensubchannels might not correspond to an explicit standardbandwidth, it can happen in practical systems. For exam-ple, the operators might allocate the system resourcesseparately for different classes of users and reserve spe-cific number of subchannels for each class of users, usingthe number of serving nodes as a rule of thumb.Figure 3 shows the average power consumed by eachnode, over 20,000 time slots, with different values forimportance factor I, and Fig. 4 depicts the virtual queueHajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 15 of 21Fig. 3 Effect of parameter I on average power consumption of the BSand relays; N = 7, |K0| = 6, |Km| = 1,m ∈ Msize corresponding to the average power constraint of theBS during the mentioned period. It is observed that with-out considering a suitable I (e.g., when I = 1 or I = 103),the average power consumption of the BS is about 2000mW, which is far beyond the constraint of 1259 mW, andthe size of virtual power queue of the BS grows constantlyover this period. This happens due to the fact that in (15a),the value of the second term is very small compared withthe value of the first one and as a result, it does not havemuch effect on the optimization objective; therefore, theonly thing that limits the total power usage is the peakpower or the maximum spectral efficiency. The conse-quence of this is the steady use of the peak power of theBS in each time slot, which incurs the steady growth of itsvirtual power queue size according to (6a). Without a suit-able I, this would continue for a long time, until the size ofthe virtual queue has grown so large that the second termin (15a) is comparable to the first one. However, as statedin Remark 3, using a suitably large I (e.g., I = 106 in thisscenario) amplifies the effect of the virtual power queuesizes in (15a) and prevents continuous use of the peakpowers. Therefore, as shown in Fig. 4, the virtual powerqueue of the BS gets bounded after about 300 time slotsand, as displayed in Fig. 3, the average power consumptionof the BS over the simulation period is about the speci-fied constraint. It is worth mentioning that due to fewertransmissions from the relays, compared with the BS, theirvirtual power queues did not grow large and remained sta-ble in all the above values for I and had similar graphsas that of the BS in the case of I = 106. Because of thissimilarity, their graphs were omitted.To investigate the overall performance of the proposedalgorithms in general scenarios, we consider a systemwith25 users, which are uniformly distributed in the cell areaand are connected to the node from which they receivehigher signal strength. The simulations are conducted forFig. 4 Effect of parameter I on virtual power queue size of the BS over time; N = 7, |K0| = 6, |Km| = 1,m ∈ MHajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 16 of 21100 runs, each over 10,000 time slots, to generate differ-ent realizations of users’ locations. All the users have thedata arrival rate of 20 packets per second or equivalently100 kbps, and the buffer capacity in the BS and relays are,respectively, 100 and 10 packets per user. There are 14subchannels in the system, the BS’s peak power is 37 dBm,relays’ peak powers are 28 dBm, and the average powerconstraints are half of the peak powers. As a baseline, wehave adapted the low-complexity centralized algorithmproposed in [19] to our system model, which we refer toas fixed half-duplex relaying (FHDR) in the figures. WithFHDR, the type of the time slots are fixed such that theodd-numbered time slots are used for the transmissionsfrom the BS and the even-numbered slots for the trans-missions only from the relays. The subchannel allocationsin even-numbered slots are based on considering a mini-mum of N/M subchannels for each relay and assigningthem based on the Hungarian algorithm. For FHDR, theaverage power limit of each node is equally distributedover all the subchannels, considering the maximum spec-tral efficiency constraint. Also, we have implemented thedata traffic control procedure in the FHDR to compare itsutility with that of the proposed schemes.We note that due to limited buffer capacities, all thequeues are stable and their sizes are less than the corre-sponding buffer capacities. Therefore, in the following, wedo not present any results about them and instead studythe overflow performance. Figure 5 displays the cumula-tive distribution function (CDF) of the system utility. Itis observed that all the algorithms have the same util-ity of data admissions. This indicates that all of themlead to similar amount of transmissions from the BS,and therefore, similar queue sizes in it which allow sim-ilar data admissions. However, as shown in Fig. 6, theFig. 5 CDF of system utility at the data arrival rate of 20 packets/sFig. 6 CDF of system average overflow at the data arrival rate of 20packets/stotal overflow from the buffers of relays is zero with theproposed EDCRA and EDDRA schemes whereas FHDRhas the incidents of overflow. This is due to the fact thatFHDR does not take into account the limited buffer capac-ities of the relays when deciding about the subchannelallocations. On the contrary, in the case of insufficient freespace in a relay buffer, the proposed schemes do not allo-cate any subchannel to the corresponding link from theBS and this way, they prevent data transmissions to thatbuffer.We have also presented the system average through-put, received by the users, in Fig. 7. It is observed thatthe EDCRA and EDDRA result in higher throughput thanFig. 7 CDF of system average throughput at the data arrival rate of 20packets/sHajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 17 of 21the FHDR, which is a sign of efficient utilization of systemresources (i.e., time slot, subchannel and power) by theproposed schemes. This happens due to several reasons.In FHDR, the transmission power of the subchannels areconstant; the time intervals for the transmissions from theBS and relays are fixed and are done in the odd-numberedand even-numbered time slots, respectively. Also, FHDRconsiders a fixed minimum number of subchannels foreach node in each time slot, which reduces the flexi-bility in allocating the subchannels. On the other hand,EDCRA and EDDRA decide about the type of the timeslots and the subchannel allocations in an adaptive wayand based on the demands of the different nodes, wherethe demands are based on achievable transmission ratesand the actual queue sizes. Moreover, after subchannelallocations, EDCRA and EDDRA adjust the power usageon the subchannels depending on the virtual power queuesizes, peak power, and the maximum spectral efficiencyconstraints, which allow them to utilize the flexibility inpower allocation.Next, in the same system, we investigate the effect ofincrease in the data arrival rate on the performance of theproposed algorithms. Figures 8, 9, and 10 show, respec-tively, the system utility, system average overflow, andsystem average throughput versus data arrival rate. It isobserved that as the data arrival rates increase, the util-ities of the EDDRA and EDCRA also increase; but afterthe arrival rate of 60 packets/s, this increase is not much.This is firstly due to the fact that the utility function isa concave function which has diminishing returns as thearrival rates increase. The other reason is the fact thatthe system capacity is saturated in high packet arrivalrates, leading to lower increase in throughput as shownFig. 8 Effect of increase in the packet arrival rate on the system utilityFig. 9 Effect of increase in the packet arrival rate on the averageoverflow from the buffers of relaysin Fig. 10; therefore, the queues can not be served muchand this prevents more admission of data into the system.Similar effect is observed about FHDR; however, since itdoes not determine the type of time slot based on thedemands and does not use the subchannel and powerresources efficiently, it leads to higher queue sizes in theBS and consequently, lower data admissions in high packetarrival rates. Due to this and the overflows from the relays’buffers, it also results in lower throughput.Note that the performance of the EDCRA is a little bet-ter than that of EDDRA. This is due to the fact that inEDCRA, the BS has information about the channel statesFig. 10 Effect of increase in the packet arrival rate on the systemaverage throughputHajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 18 of 21of all the links and performs subchannel allocation basedon the individual demands of the relays’ queues and itsown queues; but in EDDRA, the BS determines the sub-channel sets of the nodes based on their average demandsand then each set of subchannels is only used to serve theset of the queues of the corresponding node. However, thedegradation in the performance of EDDRA is not signifi-cant. The reason for this is the fact that there are usuallyseveral users for each node, with different channel con-ditions, that make it possible for each node to utilize itsset of subchannels efficiently. Also considering an upperbound for the number of subchannels each node can getprevents wasting the resources. These observations showthat using EDDRA, the system can allocate resources effi-ciently with less computations at the BS, low signalingoverhead, and without remarkable reduction in the systemperformance.Next, in order to show the effectiveness of the parame-ters ρmk and We proposed in this paper, we show the dataadmissions for direct and indirect users. It is observed inFig. 11 that as the packet arrival rates of the users increase,the data admissions for direct users increase but less dataare admitted for indirect ones. As explained in Remark 1,this is due to the fact that the queues of indirect usersat the BS get low weights and grow large, which resultin lower data admissions for them. To prevent that, ρmkcan be set to one to apply an extra weight of We in theweights of the links from the BS to relays and the linksfrom the relays to users, to increase the service provision-ing for their corresponding queues and consequently leadto more data admissions into the corresponding buffersin the BS. Figure 12 shows this in the case of arrivalrates equal to 140 packets per second for every user. Itis observed that giving higher weights can increase theFig. 11 Effect of increase in the packet arrival rate on the amount ofdata admitted for direct and indirect usersFig. 12 Effect of parameterWe on providing fair data admissions fordirect and indirect users at the arrival rate of 140 packets/s for everyuserdata admissions for indirect users; this comes at the costof large drops in the data admissions of direct users. It isdue to the fact that adding the extra weights results in theincrease of subchannel allocations to the queues of indi-rect users in the BS and relays. Since the BS has higherpower than relays, the less subchannel allocation to thedirect users means that their queues loose higher trans-mission rates than those for the queues in relays. As aresult, the queues of direct users in the BS grow quickerand limit the data admissions.Finally, we consider a scenario in which there is nolimit on the transmission rates and buffer capacities (i.e.,C2−C4 andC6 are removed from problem (4)), and actualqueues need to be stabilized (i.e., remain bounded). In thiscase, as shown in [21], the resource allocation subprob-lem can be formulated as a convex optimization problemand therefore, a global optimal exists. In [21], the JFRPalgorithm is proposed which uses subgradient-based iter-ations to get close to the optimal solution for resourceallocation. To compare our proposed schemes with JFRP,we have run simulations for EDDRA and EDCRA withthe settings considered in [21], over 10,000 time slots. Theresults are shown in Figs. 13, 14, 15, and 16, in whichthe graphs of JFRP are imported from the correspondingfigures in [21].In Figs. 13 and 14, the system utility and total queue sizeare shown versus mean data arrival rate, when V = 60.It is observed that EDCRA and EDDRA have almost thesame or even higher utility than JFRP, which is a sign ofmore data admissions to the network. On the other hand,the proposed schemes lead to larger queue sizes in most ofthe arrival rates. Figures 15 and 16 show the system utilityHajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 19 of 21Fig. 13 Effect of increase in the data arrival rate on the system utilityin the settings of [21]and total queue size versus V. It is observed that whenV < 70, the proposed schemes outperform JFRP in termsof system utility, even though they result in larger queuesizes in almost all the values of V. It is stated in [21] thatthe lower utility of the JFRP in smaller values of param-eter V is because the power is under-utilized. Also, wenote that even though the JFRP algorithm tries to get asolution close to the optimal one, it leads to a suboptimalsolution which can be due to the approximations throughthe iterations of subgradient method. Moreover, note thatin these results, according to the settings of [21], infinitebuffer capacities were assumed for the BS and relays, andtherefore, instead of overflow, we have shown the resultsFig. 14 Effect of increase in the data arrival rate on the system sumqueue size in the settings of [21]Fig. 15 Effect of value parameter V on the system utility in the settingsof [21]for queue sizes. It is observed that all the algorithms keepthe queues stable which means that in long term, the datareception rates at the users are equal to the data admis-sion rates into their buffers at the BS; thus, in this scenario,the system utility performance also indicates the through-put performance. However, in the scenarios with limitedbuffer capacities, JFRP can result in overflows and lowerthroughput similar to FHDR in Figs. 6, 7, 9, and 10. Alsobased on the Figs. 3, 4, 11, and 12, we note that since JFRPdoes not consider the parameters I, ρmk and We, it canlead to unsatisfactory performance for the average powerV5 10 20 30 40 50 60 70 80 90System Sum Queue Size [KBits]0.20.40.6EDCRAEDDRAJFRPFig. 16 Effect of value parameter V on the system sum queue size inthe settings of [21]Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 20 of 21constraints and the fair data admission for the users in thesettings of practical systems.In order to compare the computational complexitiesof JFRP and the proposed algorithms, we first note thatthe subgradient method requires number of iterations inthe order of O(1/22) to reach the 2 error bound [30].Also we note that in each iteration, the dual variablesused for updating the primal ones are not optimal. Thiscan lead to ties in computing the subchannel allocationindicators during the iterations. Depending on the meth-ods and approximations used for breaking the ties, JFRPmight require even more iterations. This prohibits dis-tributed implementation of JFRP, due to the messagingoverheads imposed for updating the dual and primal vari-ables in every iteration. Also, it is very expensive in termsof time it consumes, considering the fact that the itera-tions should be done for each time slot which is in theorder of millisecond in practical systems. Consideringthe abovementioned and the main computations in eachiteration, the overall computational complexity of JFRPalgorithm is at least in the order of O(KN/22). On theother hand, the EDDRA algorithm requires only one-timemessaging from relays to the BS (about their queue sizesand demands) and one-time messaging from the BS torelays (about subchannel sets), and the rest of the pro-cessing is done locally in each node. Furthermore, theoverall computational complexity of EDDRA is clear andis of O(KN2 + (M + 1) log(1/1)) which is split amongthe serving nodes. Similarly, EDCRA requires one-timemessaging from relays to the BS (about the users’ chan-nel conditions) and one-time messaging from the BS torelays (about the subchannel and power allocations). It hasclear overall computational complexity, too, which is ofO(KN2 + (M + 1) log(1/1)). Based on the discussions inthis section as well as the previous ones, EDDRA is moresuitable for implementation in practice while EDCRA andJFRP provide good baselines for comparison purposes.5 ConclusionsIn this paper, we have studied data admission control andresource allocation in buffer-aided relay-assisted OFDMAnetworks. We have formulated time slot, subchannel,power allocation as a utility-based stochastic optimizationproblem, taking into account several practical constraints.Using the Lyapunov drift-plus-penalty policy, we havetransformed the problem into instantaneous subproblemswhile introducing several parameters related to cellularnetworks. For practical considerations, we have proposedlow-complexity strategy for the allocation of power andsubchannels and have provided distributed and central-ized schemes to utilize it. In particular, the proposedEDDRA policy is attractive for use in practice due to itslow complexity as well as low signaling overhead. Numer-ical results confirm the effectiveness of the proposedparameters and also show that the proposed algorithmslead to significant improvement in data admission andthroughput of the system.Endnotes1In a centralized implementation, the BS has informationabout all the queue sizes, due to the fact that it has thehistory of the transmissions from all the queues.2In the above discussions, we excluded the signalingoverhead of channel state feedbacks from the receiverside of any link to the transmitter side, due to the factthat it is the same in EDDRA and EDCRA.Competing interestsThe authors declare that they have no competing interests.AcknowledgementsThis work was supported by the Canadian Natural Sciences and EngineeringResearch Council through grants RGPIN-2014-06119 and RGPAS-462031-2014,and the National Natural Science Foundation of China through Grant No.61271182. The work of Amr Mohamed was supported by NPRP 5-782-2-322from the Qatar National Research Fund (a member of Qatar Foundation). Thestatements made herein are solely the responsibility of the authors.Author details1ECE Department, The University of British Columbia, Vancouver, Canada. 2CSEDepartment, Qatar University, Doha, Qatar.Received: 13 May 2015 Accepted: 12 November 2015References1. IEEE Std 802.16j-2009, Part 16: Air interface for broadband wireless accesssystems-amendment 1: Multihop relay specification. (IEEE, New York, USA,2009)2. 3GPP TR 36.814 V9.0.0, Evolved universal terrestrial radio access (E-UTRA);further advancements for E-UTRA physical layer aspects. (3GPP, Valbonne,France, 2010). http://www.3gpp.org/dynareport/36814.htm3. M Salem, A Adinoyi, H Yanikomeroglu, D Falconer, Opportunities andchallenges in OFDMA-based cellular relay networks: a radio resourcemanagement perspective. IEEE Trans. Veh. Technol. 59, 2496–2510 (2010)4. SJ Kim, X Wang, M Madihian, Optimal resource allocation in multi-hopOFDMA wireless networks with cooperative relay. IEEE Trans. Wirel.Commun. 7, 1833–1838 (2008)5. K Sundaresan, S Rangarajan, in Proc. IEEE International Conference onComputer Communications. Adaptive resource scheduling in wirelessOFDMA relay networks (IEEE, New York, USA, 2012), pp. 1080–10886. DWK Ng, R Schober, Cross-layer scheduling for OFDMAamplify-and-forward relay networks. IEEE Trans. Veh. Technol. 59,1443–1458 (2009)7. DWK Ng, ES Lo, R Schober, Dynamic resource allocation in MIMO-OFDMAsystems with full-duplex and hybrid relaying. IEEE Trans. Commun. 60,1291–1304 (2012)8. Y Pan, A Nix, M Beach, Distributed resource allocation for OFDMA-basedrelay networks. IEEE Trans. Veh. Technol. 60, 919–931 (2011)9. S Zhang, XG Xia, in Proc. IEEEWireless Communications and NetworkingConference. A high-efficiency semi-distributed resource allocation inOFDMA-based wireless relay networks (IEEE, New York, USA, 2013),pp. 3277–328110. O Oyman, Opportunistic scheduling and spectrum reuse in relay-basedcellular networks. IEEE Trans. Wirel. Commun. 9, 1074–1085 (2010)11. J Liang, H Yin, H Chen, Z Li, S Liu, in Proc. IEEE Vehicular TechnologyConference. A novel dynamic full frequency reuse scheme in OFDMAcellular relay networks (IEEE, New York, USA, 2011), pp. 1–512. H Mei, J Bigham, P Jiang, E Bodanese, Distributed dynamic frequencyallocation in fractional frequency reused relay based cellular networks.IEEE Trans. Commun. 61, 1327–1336 (2013)Hajipour et al. EURASIP Journal onWireless Communications and Networking (2015) 2015:263 Page 21 of 2113. N Zlatanov, R Schober, P Popovski, in Proc. IEEE Global TelecommunicationsConference. Throughput and diversity gain of buffer-aided relaying,(2011), pp. 1–614. T Riihonen, R Wichman, S Werner, Evaluation of OFDM(A) relayingprotocols: capacity analysis in infrastructure framework. IEEE Trans. Veh.Technol. 61, 360–374 (2011)15. N Zlatanov, A Ikhlef, T Islam, R Schober, Buffer-aided cooperativecommunications: opportunities and challenges. IEEE Commun. Mag. 52,146–153 (2014)16. J Yang, H Hu, H Xi, L Hanzo, Online buffer fullness estimation aidedadaptive media playout for video streaming. IEEE Trans. Multimed. 13,1141–1153 (2011)17. J Yang, Y Ran, S Chen, W Li, L Hanzo, Online source rate control foradaptive video streaming over HSPA and LTE-style variable bitratedownlink channels. To appear in IEEE Trans. Veh. Technol., 1–1 (2015)18. M Salem, A Adinoyi, M Rahman, H Yanikomeroglu, D Falconer, Y Kim,Fairness-aware radio resource management in downlink OFDMA cellularrelay networks. IEEE Trans. Wirel. Commun. 9, 1628–1639 (2010)19. M Salem, A Adinoyi, H Yanikomeroglu, D Falconer, Fair resource allocationtoward ubiquitous coverage in OFDMA-based cellular relay networkswith asymmetric traffic. IEEE Trans. Veh. Technol. 60, 2280–2292 (2011)20. J Hajipour, A Mohamed, VCM Leung, in Proc. International Conference onWireless andMobile Communications. Dynamic distributed resourceallocation in relay assisted OFDMA networks (IARIA, 2012). www.thinkmind.org21. H Ju, B Liang, J Li, X Yang, Dynamic joint resource optimization forLTE-Advanced relay networks. IEEE Trans. Wirel. Commun. 12, 5668–5678(2013)22. MJ Neely, Stochastic Network Optimization with Application toCommunication and Queueing Systems. (Morgan & Claypool, San Rafael,2010)23. X Qiu, K Chawla, On the performance of adaptive modulation in cellularsystems. IEEE Trans. Commun. 47, 884–895 (1999)24. 3GPP TS 36.300 V13.0.0 (2015-06). Evolved universal terrestrial radioaccess (E-UTRA) and evolved universal terrestrial radio access network(E-UTRAN); overall description; stage 2. (3GPP, Valbonne, France). http://www.3gpp.org/dynareport/36300.htm25. S Supittayapornpong, MJ Neely, in Proc. IEEE International Conference onComputer Communications. Achieving utility-delay-reliability tradeoff instochastic network optimization with finite buffers (IEEE, New York, USA,2015), pp. 1–926. H Hu, H Yanikomeroglu, DD Falconer, S Periyalwar, in Proc. IEEE GlobalTelecommunications Conference. Range extension without capacitypenalty in cellular networks with digital fixed relays (IEEE, New York, USA,2004), pp. 3053–305727. DP Bertsekas, Nonlinear Programming, 2nd edn. (Athena Scientific,Nashua, 1999)28. MC Jeruchim, P Balaban, KS Shanmugan, Simulation of CommunicationSystems: Modeling, Methodology and Techniques, 2nd edn. (KluwerAcademic, Dordrecht, 2000)29. 3GPP TR 25.996 V7.0.0 (2007-06), Spatial channel model for multiple inputmultiple output (MIMO) simulations. (3GPP, Valbonne, France). http://www.3gpp.org/DynaReport/25996.htm30. L Vandenberghe, EE236C. Class lecture, topic: optimization methods forlarge-scale systems: subgradient method. http://www.seas.ucla.edu/~vandenbe/236C/lectures/sgmethod.pdfSubmit your manuscript to a journal and benefi t from:7 Convenient online submission7 Rigorous peer review7 Immediate publication on acceptance7 Open access: articles freely available online7 High visibility within the fi eld7 Retaining the copyright to your article Submit your next manuscript at 7 springeropen.com"@en ; edm:hasType "Article"@en ; edm:isShownAt "10.14288/1.0308651"@en ; dcterms:language "eng"@en ; ns0:peerReviewStatus "Reviewed"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "Springer International Publishing"@en ; ns0:publisherDOI "10.1186/s13638-015-0481-4"@en ; dcterms:rights "Attribution 4.0 International (CC BY 4.0)"@en ; ns0:rightsURI "http://creativecommons.org/licenses/by/4.0/"@en ; ns0:scholarLevel "Faculty"@en ; dcterms:subject "OFDMA"@en, "Regenerative buffering relays"@en, "Distributed resource allocation"@en, "Low complexity"@en ; dcterms:title "Utility-based efficient dynamic distributed resource allocation in buffer-aided relay-assisted OFDMA networks"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/58883"@en .