Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes

Please download to get full document.

View again

of 9
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Internet & Web

Published:

Views: 0 | Pages: 9

Extension: PDF | Download: 0

Share
Related documents
Description
Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes Reuven Cohen Guy Grebla Department of Computer Science Technion Israel Institute of Technology Haifa 32000, Israel Abstract LTE-advanced
Transcript
Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes Reuven Cohen Guy Grebla Department of Computer Science Technion Israel Institute of Technology Haifa 32000, Israel Abstract LTE-advanced and other 4G cellular standards allow relay nodes (RNs) to be deployed as a substitute for base stations (BSs). Unlike a BS, an RN is not directly connected to the backbone. Rather, each RN is associated with a donor BS, to which it is connected through the OFDMA wireless link. A very important task in the operation of a wireless network is packet scheduling. In a network with RNs, such scheduling decisions must be made in each cell not only for the BS, but also for the RNs. Because the scheduler in a network with RNs must take into account the transmission resources of the BS and the RNs, it needs to find a feasible schedule that does not exceed the resources of a multi-dimensional resource pool. This makes the scheduling problem computationally harder than in a network without RNs. In this paper we define and study for the first time the packet-level scheduling problem for a network with RNs. This problem is shown to be not only NP-hard, but also very hard to approximate. To solve it, we propose an approximation with a performance guarantee, and a simple water-filling heuristic. Using simulations, we evaluate our new algorithms and show that they perform very well. I. INTRODUCTION The advent of sophisticated mobile devices and new applications has made spectral optimization crucial for wireless networks. New 4G technologies, such as LTE Advanced [2], employ OFDMA in their physical layer and use new concepts such as MIMO, CoMP and Relay Nodes (RNs) [3], [14], [15] to increase the throughput. Deploying long-range wireless networks with good coverage is a complex task, one that introduces a tradeoff between cost and performance. One example of this trade-off is the desire to decrease the size of the cells in order to increase the network bandwidth available to every user. But decreasing cell size by adding more base stations (BSs) increases installation costs substantially, because the most expensive factor in the installation of a new BS is connecting it to the optical backbone. To overcome this barrier, 4G cellular standards allow RNs to be deployed as a substitute for BSs. Unlike a BS, an RN is not directly connected to the backbone /14/$ IEEE Fig. 1. Example of a network with RNs and their donor BSs Rather, each RN is associated with a donor BS, to which it is connected through the OFDMA wireless link (see Figure 1). Each user equipment (UE) receives its data packets either directly from the BS, or indirectly over the BS RN UE route. The performance benefits from the deployment of RNs are three-fold: (a) increased network density; (b) increased network coverage; (c) increased network roll-out speed. An important task in the operation of a wireless network is packet scheduling. This task comprises all real-time decisions that must be made by the BS before transmitting data on the downlink channel: which data packets to transmit during the next OFDMA subframe, which modulation and coding scheme (MCS) to use for each packet, whether to transmit a packet directly to the UE or via an RN, and so on. In a network with RNs, such scheduling decisions must be made for the RNs as well. In this paper we propose the first packet-level scheduling algorithm for such networks. This algorithm has two important advantages compared to the user-level scheduling algorithms proposed in [15], [20], [23]. First, it allows different packets of the same user to have different priority. Second, it allows different packets of the same user to be transmitted using different MCSs. Adding RNs to the network makes the scheduling problem computationally harder. Without RNs, the BS needs to decide which packets to transmit and which MCS to use for each transmitted packet. Each transmission of a packet using some MCS requires a certain amount of bandwidth in the next subframe and is associated with a certain utility function. The goal is to maximize the total profit without exceeding the total bandwidth. Therefore, without RNs, the scheduling problem is equivalent to the known NP-hard Multiple-Choice Knapsack Problem (MCKP) [11], to which excellent approximations, heuristics and dynamic programming algorithms exist. In a network with RNs, the scheduler must also take into account the bandwidth available to each RN. Thus, each packet transmission now has a 2-dimensional size: the first dimension indicates the bandwidth resources required for the BS RN transmission and the second indicates the bandwidth resources required for the RN UE transmission. Thus, the scheduler must find a feasible schedule that does not exceed the resources of a multi-dimensional resource pool, whose number of dimensions depends on the number of RNs. This makes the scheduling problem in a network with RNs more similar to an extension of MCKP into multiple dimensions, a problem known as d-dimensional Multiple-Choice Knapsack (d-mckp), which is computationally harder than MCKP. In order to solve this problem for a network with RNs, we transform it into a less general case of d-mckp called sparse d-mckp, and propose efficient algorithms to solve this new problem. One of our algorithms is proven to have a performance guarantee, and can also be optimal for realistic input size. For ease of presentation, we explain the main concepts of our proposed algorithms for a BS with one omnidirectional antenna, although in many cellular networks that employ RNs the BS uses multiple directional antennas (also known as sectors). For such multi-sector networks, the algorithms proposed in this paper can be invoked independently for each sector, in which case the BS in each sector would also run an independent scheduler, for its directional antenna and for each RN in its sector. If this option is chosen, no changes are required to the proposed algorithms. The rest of the paper is organized as follows. In Section II we discuss related work. In Section III we present our scheduling network. In Section IV, we define the new OFDMA Scheduling with Relays and Dynamic MCS Selection problem, which is the core of this paper. We show that it is NP-hard and equivalent to a special case of d-mckp. In Section V we present efficient algorithms for solving this new problem. Section VI presents an extensive simulation study and Section VII concludes the paper. II. RELATED WORK Our paper is the first to propose packet-level scheduling algorithms for an OFDMA/LTE network with relay nodes (RNs). We therefore classify the papers described in this section into two groups. The first includes papers that propose packet-level scheduling for an OFDMA/LTE network without RNs. The second includes papers that address scheduling related issues in a network with RNs. Papers belonging to the first group are [4], [7], [19]. In [4], the authors study the process of determining the cells that provide service to each mobile station. The potential benefit of global cell selection versus local SNRbased decision is studied. It is shown that the general case of the problem is hard to approximate. However, two algorithms are proposed and are shown to have a performance guarantee under a practical assumption. The authors of [19] also study the cell selection problem and focuses on heterogeneous systems. A new cell selection strategy is proposed to improve the efficiency. In [7], two basic handover schemes for inter-cell interference coordination are considered, and a handover decision algorithm for improving cell edge throughput is proposed. It is shown that the proposed algorithm obtains a higher cell edge throughput compared to that obtained by the legacy SINR-based decision algorithm. Papers in the second group include [15], [20], and [23]. In these papers, user-level admission control algorithms are proposed for OFDMA networks with relays. In [15], the authors consider a cell with RNs, and assume that there is no direct wireless link between the BS and the UEs. The UEs are either delay sensitive or non-delay sensitive, and algorithms that select one of four possible transmission strategies for each UE are presented. In [20], an algorithm for maximizing the total cell throughput while stabilizing user queues is proposed. In [23], two algorithms for utilizing spatial reuse are developed and are shown to improve the throughput. All these papers address the problem of deciding the transmission rates of the BS and RNs to each user. However, we distinguish between this userlevel admission control problem, and our packet-level RN scheduling problem, mainly because in our model different packets of the same user might have different priority. Another important difference is that we allow different packets of the same user to be transmitted using different MCS, while in above-mentioned works the same MCS is determined for each user. In [14] and [18] relay strategies are compared. In [14], the downlink performance for Layer-3 and Layer-1 relays is investigated. System-level simulations are used to demonstrate the impact of several relay conditions. In [18], the performance of several emerging half-duplex relay strategies in interference-limited cellular systems is analyzed. The performance of each strategy as a function of location, sectoring, and frequency reuse are compared with localized base station coordination. 2 RN2 RN1 BS RN1 RN3 RN2 F1 F2 F3 F0 RN1 BS RN3 F1 F2 BS transmits to UEs and to RNs RNs only listen All RNs transmit concurrently to their UEs F1 +F2 BS transmits to UEs and to RNs RNs only listen BS transmits to UEs RNs transmit to UEs Fig. 2. RN2 BS RN3 The frequency reuse model considered in this paper III. NETWORK MODEL A. Inband vs. Outband Relaying We consider a cell with a BS at its center and R RNs, as shown in Figure 2 for R = 3 (frequency reuse aspects of this figure are discussed later on). A 10-ms LTE frame is divided into 10 1-ms subframes 1. Each subframe contains a pool of scheduled blocks, to be assigned by the BS to waiting packets. The exact number of scheduled blocks in every subframe depends on the system bandwidth; it is 100, for example, in an LTE 20MHz system. Each RN is connected to its BS by an OFDMA wireless link, using either inband or outband relaying. In outband relaying, BS and RN transmissions use different subbands. Therefore, they can transmit simultaneously in each subframe, with no interference (Figure 3(a)). In inband relaying, however, the transmissions from the BS to the RNs or to the UEs are performed over the same subbands as those from the RNs to the UEs. Thus, simultaneous transmissions by the BS and RNs are not possible unless sufficient isolation in time or in space is ensured. Figure 3(b) assumes such isolation: in every two consecutive subframes, one is dedicated for transmissions from the BS and one for transmissions by the BS and RNs to UEs (isolation in time). The BS and the RNs can transmit together in every second subframe only if they are located far enough from each other (isolation in space). Otherwise, only the RNs can transmit in every second subframe. B. Our Scheduling Model In an LTE network with RNs, one may distinguish between distributed and centralized scheduling. In distributed scheduling, each transmission entity, namely, a BS or an RN, autonomously decides what to transmit in every subframe. In centralized scheduling, all transmission decisions for the BS and the RNs are performed by the BS. In this paper we focus on centralized scheduling, 1 We are trying to abstract the problem in the most generic way. Therefore, we skip some of the LTE physical layer details that are not directly relevant to the description of the problem and algorithms. 1ms subframe (a) one LTE subframe 1ms subframe 1ms subframe (b) two LTE subframes for outband relaying for inband relaying Fig. 3. An abstract structure of the LTE subframe (F1 and F2 are two orthogonal OFDMA subbands) because it has an important advantage over distributed scheduling [10]: the scheduler has a global view of the network resources and can optimize their usage. For instance, if an RN is overloaded, the BS can decide to transmit to some UEs directly, even if these UEs have better SINR with the busy RN than with the BS. In the considered model, the BS receives periodic Channel Quality Indications (CQI) from the UEs and RNs. Using these reports, the BS is able to estimate the SINR for transmissions from the BS to each UE or RN. The BS also receives CQI reports on the SINR between each UE and its RN. These reports are either transmitted directly by every UE to the BS, or forwarded by the RNs to the BS over an RN BS control channel. The BS uses this information to make the following decisions: (a) which packet to transmit; (b) whether to transmit the packet directly or through an RN; (c) if the packet is not transmitted directly, through which RN to forward it; (d) which MCS (Modulation and Coding Scheme) to use for each transmission. The scheduler determines how many scheduled blocks to allocate to every packet according to the chosen MCS. Some MCSs are more efficient, i.e., require fewer scheduled blocks, but are less robust to transmission errors. Other MCSs are less efficient but more robust. Since there are several pools of scheduled blocks that the scheduler uses, a more formal discussion will require the following definitions: Definition 1: A scheduling area is a set of scheduled blocks to be assigned for transmission by the same transmission entity (a BS or an RN). In the outband relaying model, the scheduler needs to make a scheduling decision every 1ms subframe for 1 BS scheduling area and R RN scheduling areas (Figure 3(a)). Thus, the scheduler has to allocate resources from R + 1 scheduling areas (pools) every 1ms. In the inband relaying model, the scheduler needs to make a scheduling decision every 2ms for two consecutive 1ms subframes (Figure 3(b)). In the first 1ms subframe, the scheduler allocates resources only from the BS scheduling area. In the second 1ms subframe, the scheduler allocates resources from the BS scheduling area and R 3 RN scheduling areas. Thus, in the inband relaying model, the scheduler has to make decisions for R+2 scheduling areas every 2ms. Definition 2: A transmission instance of a packet is a triple [packet, path, MCSs], where path is either BS UE or BS RN i UE, and MCSs is a list that indicates the MCS to be used for the transmission of the packet over each link along the path (1 link if the path is BS UE; 2 links if it is BS RN i UE). Each transmission instance requires allocation of scheduled blocks from the corresponding scheduling area(s). We adopt the profit-based scheduling model proposed in [9]. Thus, each transmission instance of a data packet at time t is associated with a profit and a cost. The profit depends on the following parameters: (a) how important it is to the application that the packet be delivered at t; (b) the probability that this packet will be successfully received by the UE. This probability can be computed by the BS by taking into account (i) the SINR on each wireless link (BS UE or BS RN i and RN i UE); (ii) the length of the packet; and (iii) the MCS used for transmitting this packet [5], [13]. We now give examples of concrete profit values whose aim is to optimize either the throughput, energy, delay, or fairness. p packets - This profit value is defined as the packet transmission success probability. As a result, the sum of all profit values equals the expected number of successfully received packets, i.e., packet-level throughput. p throughput - This profit value is defined as p packets multiplied by the length of the packet. As a result, the sum of all profit values of all transmitted packets equals the expected number of successfully received bits, i.e., bit-level throughput. p energy - This profit value is defined as p throughput divided by the transmission energy cost. As a result, the sum of all profit values of all transmitted packets equals the expected number of bits transmitted per energy unit, namely, the transmission energy utilization. p delay - For each packet, this profit value indicates the probability that this packet will be delivered on time if it is transmitted during the next subframe. As a result, pdelay is the expected number of packets scheduled in a given subframe and are likely to be delivered on time. p pf - For each user, the most urgent packet destined for this user is assigned a profit value of log(p throughput ). The profit for all remaining packets is set to zero. It is shown in [12] that an allocation that maximizes log R u, where R u is the rate of user u, is proportional fair. As a result, a proportional fair allocation is one that maximizes p pf. The success probability for transmitting a given packet varies from one scheduling area to another. Thus, the profit of a packet might also dynamically change. While the profit of a packet is a scalar, the cost is a vector that has one or more dimensions: one for each link over which the packet is scheduled. The cost on each link is equal to the number of scheduled blocks required for transmitting the packet in the scheduling area associated with this link. It depends on the length of the packet and the MCS, and it is what makes the scheduling problem for a BS with RNs intractable. C. Frequency Reuse Models In addition to the decision whether to use inband or outband relaying, the frequency reuse model must also be decided upon. In order to describe our algorithms in a specific context, we focus on a specific model. However, these algorithms are easily adaptable to other frequency reuse models as well 2. The considered model is shown in Figure 2 and is relevant for outband relaying. Here, bandwidth is partitioned into N +1 subbands: F0, F1, F2 and F3 (N = 3 in this figure). The BS in every cell uses subband F0 (i.e., the BSs work using frequency reuse 1), while all the RNs in every cell use either F1, F2 or F3. This guarantees that close RNs in neighboring cells use different subbands. This combination of reuse-1 by the BSs and reuse 1/3 by the RNs can be viewed as an implementation of FFR (Fractional Frequency Reuse), which is very common in networks with no RNs [16]. Since outband relaying is considered for this model, the BSs and RNs use different orthogonal subbands. Thus, the BSs transmit using high power, and they can reach the cell-edge UEs with no interference from/to their RNs. We emphasize that this paper does not claim that the considered frequency reuse model is the best for an LTE network with RNs. The decision about which model to use depends on many factors and regulations that are beyond the scope of this paper. IV. THE SCHEDULING PROBLEM This section is divided into two subsections. In the first subsection, we define the scheduling problem in OFDMA networks with RNs and show hardness results. In the second subsection, we define a new theoretical problem called sparse d-mckp and show that it is equivalent to our OFDMA scheduling problem. A. Preliminaries Throughout the section, the following lemma will be used in order to reduce the number of transmission instances the scheduler considers for each data packet. Lemma 1: If the scheduler is configured to use only links with an SINR 0dBm, then: (a) a packet can be transmitted either directly or through the RN with which 2 In the extended version of this paper [8] we present two models. The one considered here is called there model-1, and the one not considered here is called model-2. The latter is relevant for inband relaying. 4 the user has the best SINR, and not through any other RN; (b) each packet can be associated with at most (M 2 + M) transmission instances, where M is the number of MCSs. (SINR 0dBm is chosen because transmission success probability for SINR no greater than 0dBm is very l
Recommended
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x