Interference-Aware Mode Selection and Resource Allocation for Device-To-Device (D2D) communications in LTE-Advanced Networks

(1)

Department of Information Engineering

Master of Science in Computer Engineering

Master’s Thesis

Interference-Aware Mode Selection and Resource Allocation

for Device-To-Device (D2D) communications in

LTE-Advanced Networks

Candidate: Advisors:

Andrea Rossali Ing. Giovanni Stea Prof. Enzo Mingozzi Ing. Antonio Virdis

(2)

(3)

Abstract

The recent socio-technological trend in proximity-based applications and services, and the increasing market interest in short-range communications have triggered the re-search and standardization communities to explore the potential of device-to-device (D2D) communications in LTE-Advanced networks (LTE Release 12). D2D com-munications imply that wireless devices in proximity of each other communicate in a peer-to-peer fashion without the aid of the base station. This new type of com-munication holds the promise of three types of gains: High bit-rates, low delays and reduced power consumption from both the users (transmitting at lower powers) and the infrastructure (offloading transmissions to users). In addition, if reuse of the same frequency resources by the D2D devices is enabled, lower use of both uplink and downlink resources is expected. New challenges are also introduced (such as interfer-ence management) and effective and efficient solutions have to be developed to deal with them. In this work, we present a comprehensive framework for D2D transmis-sions. The latter consists of two interrelated building blocks: an Interference-Aware Mode Selection algorithm, which decides whether pairs of UE should communicate via the infrastructure or directly, based on their mutual interference and channel quality in both directions; a Resource Allocation algorithm, that manages the uplink and downlink frames by scheduling mutually non interfering D2D pairs in shared re-sources, so as to minimize the number of allocated frequencies. Simulation results show that the proposed solution enhances both system and end-users performance: more specifically, at low loads we achieve the same throughput with a lower resource (hence power) consumption, and, at higher loads, we move further to the right the saturation limit.

(4)

(5)

7 Performance Evaluation 76 7.1 Simulation Overview . . . 76 7.2 Scenarios . . . 77 7.3 Users deployment . . . 77 7.4 Preliminary Results . . . 78 7.5 First Scenario . . . 84 7.5.1 Simulation parameters . . . 84 7.5.2 Results . . . 84 7.6 Second Scenario . . . 91 7.6.1 Preliminary assumptions . . . 91 7.6.2 Simulation parameters . . . 92 7.6.3 Results . . . 92 8 Conclusions 101 References 102 Acknowledgements 104

(8)

List of Tables

2.1 Cellular technologies comparison . . . 18

2.2 Cell bandwidths supported by LTE . . . 21

7.1 Preliminary scenario simulation parameters . . . 78

7.2 First simulation parameters . . . 84

(9)

List of Figures

2.1 High Level View of the LTE Architecture . . . 20

2.2 The Resource Grid . . . 21

2.3 OFDMA symbols in frequency−time domain . . . 22

2.4 SC-FDMA symbols in frequency−time domain . . . 23

2.5 The Air Interface’s protocol stack . . . 24

2.6 MAC Layer . . . 26

2.7 Operation of multiple hybrid ARQ processes in conjunction with a stop-and-wait retransmission scheme . . . 27

2.8 4-bit CQI Table . . . 30

3.1 Data Path in a standard LTE communication . . . 33

3.2 Data Path in a D2D LTE communication . . . 33

3.3 Control Path in a D2D LTE communication . . . 34

3.4 Interference problem in sharing Uplink resources . . . 35

3.5 Channel Estimation Between two D2D UEs . . . 36

3.6 Control and Data Channels between eNodeB and D2D UEs . . . 37

3.7 Single-Cell scenario . . . 39

3.8 Multi-Cell scenario . . . 40

5.1 Resource partitioning in uplink channel . . . 48

5.2 Various simultaneous uplink communications . . . 55

5.3 Conflict Graph associated to figure 5.2 . . . 56

6.1 CQI needed for D2D communication . . . 66

6.2 Control and Data signaling for D2D . . . 67

6.3 Signaling for a Retransmission . . . 68

(10)

6.5 Conflict Graph Builder connections . . . 70

6.6 Statistics Manager connections . . . 71

6.7 Mode selection and UE adjustment . . . 72

6.8 Retransmission of INFRA PDU during D2D mode . . . 73

6.9 RLC issues during path changes . . . 74

6.10 Flowchart for the First-Fit algorithm . . . 75

7.1 Average Served blocks for Uplink and Downlink . . . 79

7.2 MAC Uplink Throughput for 60 users . . . 80

7.5 CDF of MOS for 60 users . . . 82

(11)

(12)

List of Acronyms

3GPP 3rd Generation Partnership Project AMC Adaptive Modulation and Coding BSR Buffer Status Report

CQI Channel Quality Indicator

D2D CQI Channel Quality Indicator for the Device-To-Device Link D2D Device to Device

eNodeB Evolved Node B

HARQ Hybrid Automatic Repeat Request ISI Inter Symbol Interference

LTE-A LTE Advance LTE Long Term Evolution MAC Medium Access Control MOS Mean Opinion Score

OFDMA Orthogonal Frequency Division Multiple Access PDCCH Physical Downlink Control Channel

PDCP Packet Data Convergence Protocol PGW Packet Data Network Gateway PUCCH Physical Uplink Control Channel RB Resource Block

RLC Radio Link Control

(13)

SGW Serving Gateway SR Scheduling Request SRS Sound Reference Signal TTI Transmission Time Interval UE User Equipment

(14)

Chapter 1 Introduction

In this chapter is defined Device to Device (D2D) communication and the reasons that drives the research on this topic.

1.1 Device-To-Device Communication

The recent socio-technological trend in proximity-based applications and services, and the increasing market interest in short-range communications have triggered the research and standardization communities to explore the potential of device-to-device (D2D) communications. Indeed, proximity-based services, associated requirements, and possible technology enablers are currently being studied by 3GPP. Direct D2D communications, sometimes called direct-mode communications, imply that wireless devices in proximity of each other communicate in a peer-to-peer fashion without the user plane involvement of a cellular infrastructure. D2D communications tech-nology is a promising add-on component to LTE-Advanced systems for enhancing spectrum utilization, increasing the cellular capacity, improving the user through-put, and extending the battery lifetime of UEs. Some example applications of D2D communications are multimedia downloading, video streaming, online gaming, VoIP, and peer-to-peer (P2P) file sharing. Recently, wireless local-area network (WLAN) technologies (e.g. based on the IEEE 802.11 standards) and wireless personal-area network (WPAN) technologies (e.g. Bluetooth,Ultra Wideband [UWB] technologies) have been increasingly used because they provide Internet access and local services with low cost and fast access through the license exempt bands (e.g. industrial, scien-tific and medical [ISM] radio bands). However, communications on a licensed band of

(15)

a cellular network can be better in terms of interference avoidance under a controlled environment. Moreover, the local services through the above mentioned techniques require users to manually pair the peers or connect to the access points. Therefore, D2D communications could be more convenient for users because the base stations (BSs) can handle the pairing and provide better user experiences. Although D2D communications provide several benefits for local-area services in cellular networks, the extensive use of D2D communications can cause harmful interference to cellular users when sharing the same resources and also may not satisfy the quality-of-service (QoS) requirements of D2D and cellular users. D2D communication can take place on uplink or downlink resources and between two devices inside the same cell or bewteen two devices belonging to different, but adjacent, cells.

1.2 Thesis contributions

Provide D2D communication as an underlay to LTE-A networks introduces new chal-lenges. The main ones are:

• How and when switch between D2D and INFRA mode?

• How to manage the resources to permit D2D communications?

In this thesis we propose two algorithms to give an answer to the above questions . The first problem is called “Mode Selection”, i.e. the problem of decide the best communication path between two communicating devices. We formulated an opti-mized solution that, despite is complexity, can be adopted since the problem have to be resolved at relatively long time-scales. The second problem is called “Resource Allocation”, i.e. the problem of decide how to assign the LTE-A spectrum resources. Here an heuristic approach has been designed since the algorithm have to be executed once per Transmission Time Interval (TTI), i.e. every 1 ms. The main features of our solution are the following:

(16)

• Mode Selection take into account both channel quality, interference and desired rate of every communication.

• Resource Allocation take into account the decision made by the Mode Selection and permits resource sharing between non-conflicting UEs.

The contributions proposed in this Thesis are valid given the following assumptions: • Only LTE FDD is taken into account

• Only the Uplink channel is used for D2D communication

• A D2D communication is feasible only between two devices under the control of the same eNodeB

Both Mode Selection and Resource Allocation can be extended to enable D2D com-munication between two devices belonging to different, but adjacent (in terms of cell location), eNodeBs.

1.3 Overview of the Results

For evaluate our solutions we have built two scenarios:

• The First one compares the performance of our Resource Allocation algorithm to a standard Max C/I scheduler.

• The Second one compares the performance of our Mode Selection with a Ran-dom Mode Selection.

The following metrics are observed: • CDF for the Throughput • CDF for the VoIP MOS

(17)

• Average served Blocks for uplink and Downlink

The results shows that our Resource Allocation algorithm can give the same or even better performance compared to a standard scheduler with a lower cell resources load. Results for the Mode Selection shows that even at relatively low cell load our solution leads to better QoS for the communications.

1.4 Organization of this Thesis

The remainder of this Thesis is organized as follows. A brief overview of the LTE technology is given in chapter 2. In chapter 3 is presented the Device-To-Device communication and the most significant researches done about it (State of the art). In chapter 4 a brief description of the OMNeT++ network simulation framework and of the SimuLTE framework is given. In chapter 5 our solution for Mode Selection and Resource Allocation are presented. In chapter 6 the challenges of implementing the D2D communication on a packet-level simulator are presented. In chapter 7 performance evaluation of the proposed solutions are presented. Finally chapter 8 concludes the Thesis.

(18)

Chapter 2 LTE: the Long Term Evolution

In this chapter is described briefly the LTE technology. Special attention is given on the aspects to support D2D communication.

2.1 Why LTE?

For many years voice calls dominated the traffic in mobile telecommunications net-works. The growth of web oriented services (Video streaming, VoIP )and the evo-lution of the cellular equipment have increased dramatically the need of data for a mobile user. New mobile telecommunication technologies, as LTE, have to satisfy new types of traffic demand. In table 2.1 is reported a comparison between older cellular technologies and LTE.

Peak rate Typical user rate downlink Typical user rate uplink

3G 384 kbps ∼200 kbps 64 kbps

3G HSPA 7 Mbps 1-2 Mbps 64-884 kbps

3G HSPA+ 42 Mbps 2-10 Mbps 0.5-4.5 Mbps

LTE 150 Mbps 10-20 Mbps 5-10 Mbps

LTE-A ∼1 Gbps ∼30-100 Mbps ∼10-60 Mbps

(19)

2.2 System Architecture

In figure 2.1 is reported the LTE system architecture. The fundamentals elements of the system are:

• The EPC (Evolved Packet Core) distributes all types of information to the user, voice as well as data, using the packet switching technologies that have traditionally been used for data alone. Voice calls are transported using voice over IP.

• The E-UTRAN (represented by a grey dotted rectangle) handles the EPC’s radio communications with the mobile. It is composed by:

– eNodeB (enhanced Node B) – Mobile equipment (UE in figure)

• The PDNs represent the Packet Data Networks in the outside world such as the internet, private corporate networks or the IP multimedia subsystem. In 2.1 are also specified the connection interfaces between the network elements:

• The X2 interface used for connects the eNodeB with themselves, which is mainly used for signalling and packet forwarding during handover. X2 is optional. • The S1 interface for connect the eNodeBs to the EPC

• the SGi interface for connect the EPC with the PDN

Usually, the S1 and X2 interfaces are not direct physical connections: instead, the information is routed across an underlying IP based transport network.

(20)

Figure 2.1: High Level View of the LTE Architecture

2.3 Radio Resource and Transmission Techniques

transmission techniques used in Long Term Evolution (LTE) are the Orthogonal Frequency Division Multiple Access (OFDMA) for the Downlink (see 2.3.2)and Single Carrier Frequency Division Multiple Access (SC-FDMA) for the Uplink transmissions (see 2.3.3).

2.3.1 The time-frequency Resource Grid

The resource allocation of LTE is based upon the Resource Block element (RB). The RB is the smallest amount of radio resource that can be allocated for an UE. In Figure 2.2 is reported the resource grid, on a time-frequency plane, for the OFDMA where the RB is highlighted by a thick solid black rectangle. The smallest square of information is called the Resource Element and correspond to a single symbol in the OFDMA space. The RB is composed of 12 sub-carriers (frequency) x Nsymbol

(21)

Nsymbol = 7 ) or a total of 72 RE using extended cyclic prefix (i.e. Nsymbol = 6) in a

time-slot of Tslot = 0.5ms. In frequency the number of RBs available depend on the

Figure 2.2: The Resource Grid

total bandwidth of the LTE system. In Table 2.2 are reported the Cell bandwidths supported by LTE.

Table 2.2: Cell bandwidths supported by LTE

Total bandwidth N. of RBs N. of sub-carriers Occupied bandwidth

1.4 MHz 6 72 1.08 MHz 3 MHz 15 180 2.7 MHz 5 MHz 25 300 4.5 MHz 10 MHz 50 600 9 MHz 15 MHz 75 900 13.5 MHz 20 MHz 100 1200 18 MHz

(22)

Figure 2.3: OFDMA symbols in frequency−time domain

2.3.2 Orthogonal Frequency Division Multiple Access

The OFDMA is a powerful way to reduce the Inter Symbol Interference (ISI). Instead of sending the information as a single stream, an OFDMA transmitter divides the information into several parallel sub-streams, and sends each sub-stream on a different frequency known as a sub-carrier. If the total data rate stays the same, then the data rate on each sub-carrier is less than before, so the symbol duration is longer. This reduces the amount of Inter Symbol Interference (ISI), and reduces the error rate.In figure 2.3 is reported the frequency−time plot for the OFDMA transmission of 4 symbols.

2.3.3 Single-Carrier Frequency Division Multiple Access

The OFDMA is powerful technique for the Downlink transmission but is unsuitable for the LTE Downlink. During Uplink communication the UE device is the trans-mitter and the eNodeB is the receiver. This means that it must be used a commu-nication technique suited for a “cheap transmission module” (here cheap is referred to the transmitter module compared to the eNodeB one). The OFDMA amplitude

(23)

Figure 2.4: SC-FDMA symbols in frequency−time domain

of the transmitted signal varies widely leading to distortion in the frequency-domain (Any distortion of the time-domain waveform will distort the frequency-domain power spectrum as well). This, plus the non-linear amplifiers present on the UE device, makes OFDMA unsuitable for Uplink transmission. So an SC-FDMA technique is used instead. In figure 2.4 is reported the frequency−time plot for the SC-FDMA transmission of 4 symbols . In the SC-FDMA a symbol is composed by 12 sub-carriers (180KHz = 12 · 15KHz,the size of one Resource Block in frequency domain) modulated with the same data but it last for much shorter time compared to the duration symbol of OFDMA. This means that there’s the need to deal with shorter symbols (more ISI etc . . . ) but we must consider that eNodeB reception module (antennas,demodulators,amplifiers,. . . ) is way more sophisticated than the UE one.

(24)

2.4 User plane Protocols

2.4.1 Air Interface Transport Protocol

Figure 2.5: The Air Interface’s protocol stack

In Figure 2.5 is reported the air interface’s protocol stack. Starting at the bottom, the air interface physical layer contains the digital and analogue signal processing functions that the mobile and base station use to send and receive information. The physical layer is responsible for low level operation like modulation, demodulation etc . . . . Transmission technique for uplink and downlink have been covered in 2.3.2 and 2.3.3. The next three protocols make up the data link layer, layer 2 of the OSI model: • The Medium Access Control (MAC) protocol [5] carries out low-level control of the physical layer, particularly by scheduling data transmissions between the mobile and the base station (see 2.4.2).

• The Radio Link Control (RLC) protocol [6] maintains the data link between the two devices, for example by ensuring reliable delivery for data streams that need to arrive correctly (error-free transmission and data reordering). It is also responsible for segmentation and reassembly of upper layer packet in order to adapt them to the size which can actually be transmitted over the radio interface.

(25)

• Finally, the Packet Data Convergence Protocol (PDCP) [7] carries out higher-level transport functions that are related to header compression, security (in-tegrity protection and cyphering) and support for reordering and retransmission during handover.

The information flows from a layer to another are grouped into three distinct types of channel:

• Logical Channels carry data for the user plane and signalling messages for the control plane.

• Transport Channels carry data, signalling messages and broadcast informations. • Physical Channels carry all the information in the channels above in a format

suitable for the Physical Layer.

They differ on the information carried and the “position covering” in the Air Inter-face Architecture. Each channel is composed by different sub-channels each with a different purpose.

2.4.2 Medium Access Control Protocol (MAC)

The MAC layer is the lowest sub-layer in the Layer 2 architecture of the LTE radio protocol stack. The MAC layer therefore performs multiplexing and demultiplexing between logical channels and transport channels: the MAC layer in the transmitting side constructs MAC PDUs, known as Transport Blocks (TBs), from MAC SDUs received from the upper layer, and the MAC layer in the receiving side recovers MAC SDUs from MAC PDUs received through transport channels. In Figure 2.6 is reported an overview of the MAC architecture. The most important module inside the layer are the HARQ, the Controller and RAC module.

(26)

Figure 2.6: MAC Layer

The HARQ entity is responsible for the transmit and receive HARQ operations i.e. transmission and retransmission of RBs through ACK/NACK signalling. A more detailed explanation is given in Subsection 2.4.3. The Controller major task is to schedule data or users (for the eNodeB uplink side of MAC) following a determined scheduling policy. More details are given in 2.5. The RAC is responsible for control-ling the Random Access Channel (RACH) procedure. This procedure is used when a UE is not allocated with uplink radio resource but has data to transmit, or when the UE is not time-synchronized in the uplink direction.

2.4.3 Hybrid Automatic Repeat Request

The Hybrid Automatic Repeat Request (HARQ) is an error management technique based upon CRC check and ACK/NACK signalling. Briefly the steps done by the HARQ process are the followings:

1. The Transmitter add CRC to DATA 2. The transmitter sends the DATA+CRC

(27)

3. The Receiver receives and check DATA+CRC

4. If the check fails (NACK) the Transmitter have to send data again

5. This time the Receiver combines the data from the first transmission and re-transmission to increase the likelihood of a CRC pass

This scheme performs better than a non-hybrid ARQ technique, in which the first transmission was discarded. Normally, hybrid ARQ uses a re-transmission technique called stop-and-wait, in which the transmitter waits for an acknowledgement before sending new data or a re-transmission. This simplifies the design but put some limitations in system performance. In LTE a more performance-wise solution was chosen: for both the eNodeB and the UEs the system shares the data from a single MAC Buffer amongst 8 HARQ processes. Thank to this one process can then transmit while the others are waiting for acknowledgements as we can see in Figure 2.7. To limit the resulting time delays, a hybrid ARQ process is usually configured so that it gives up after a few unsuccessful attempts to transfer a block of data.

Figure 2.7: Operation of multiple hybrid ARQ processes in conjunction with a stop-and-wait retransmission scheme

(28)

2.5 Scheduling

The scheduling in LTE is done in the UE device for the uplink and in the eNodeB for both the uplink and the downlink. This process is done on a TTI (i.e. 1ms) basis so scheduling decisions must be taken in a very short time. The scheduler in the eNodeB distributes the available radio resources among the UEs inside a cell, and among the radio bearers of each UE. In principle, the eNodeB allocates downlink or uplink radio resources to each UE based respectively on the downlink data buffered in the eNodeB (scheduling for downlink transmissions) and on Buffer Status Reports (BSRs) received from the UE (scheduling for uplink transmissions). The scheduling is also channel-dependent so channel-state-reports are needed by the eNodeB to obtain the amount of data that can be delivered to an UE. This is done by CQI reporting for downlink and through Sounding Reference Signals (SRS) in uplink. On the UE side the scheduling is done between the different outgoing data streams (radio bearers for uplink transmissions) when an uplink Grant is received.

2.5.1 BSR report and eNodeB scheduling for Uplink

trans-mission

Buffer Status Reports (BSRs) from the UE to the eNodeB are used to assist the eN-odeB’s allocation of uplink radio resources. The basic assumption underlying schedul-ing in LTE is that radio resources are only allocated for transmission to or from a UE if data is available to be sent or received. In the downlink direction, the scheduler in the eNodeB is obviously aware of the amount of data to be delivered to each UE; however, in the uplink direction, because the scheduling decisions are performed in the eNodeB and the buffer for the data is located in the UE, BSRs have to be sent from the UE to the eNodeB to indicate the amount of data in the UE that needs to be transmitted. A BSR can be triggered, by an UE, in the following situations:

(29)

• whenever data arrives for a logical channel which has a higher priority than the logical channels whose buffers previously contained data (this is known as a Regular BSR);

• whenever data becomes available for any logical channel when there was previ-ously no data available for transmission (a Regular BSR);

• whenever a retxBSR timer expires and there is data available for transmission (a Regular BSR);

• whenever a periodicBSR timer 17 expires (a Periodic BSR);

• whenever spare space in a MAC PDU can accommodate a BSR (a Padding BSR).

The eNodeB, trough the BSR reports, is aware of the data in the UE buffer’s and take scheduling decisions upon that information. As for the downlink scheduling, various scheduling policies can be applied:

• MAX C/I • PF

• DRR

2.5.2 CQI and SRS

For the downlink data transmissions in LTE, the eNodeB typically selects the mod-ulation scheme and code rate depending on a prediction of the downlink channel conditions. An important input to this selection process is the Channel Quality In-dicator (CQI) feedback transmitted by the User Equipment (UE) in the uplink. CQI feedback is an indication of the data rate which can be supported by the channel,

(30)

taking into account the Signal-to-Interference-plus-Noise Ratio (SINR) and the char-acteristics of the UE’s receiver. In general, in response to the CQI feedback the eNodeB can select between QPSK, 16QAM and 64QAM schemes and a wide range of code rates. In figure 2.8 are reported the CQI values and the associated modulation schemes and others parameters.

Figure 2.8: 4-bit CQI Table

For the LTE uplink transmissions, the link adaptation process is similar to that for the downlink, with the selection of modulation and coding schemes also being un-der the control of the eNodeB. An identical channel coding structure is used for the uplink, while the modulation scheme may be selected between QPSK, 16QAM and, for the highest category of UE, also 64QAM. The main difference from the downlink is that instead of basing the link adaptation on CQI feedback, the eNodeB can di-rectly make its own estimate of the supportable uplink data rate by channel sounding, for example using the Sounding Reference Signals (SRSs). A final important aspect of link adaptation is its use in conjunction with multi-userscheduling in time and frequency, which enables the radio transmission resources to be shared efficiently

(31)

be-tween users as the channel capacity to individual users varies. The CQI can therefore be used not only to adapt the modulation and coding rate to the channel conditions, but also for the optimization of time/frequency selective scheduling and for inter-cell interference management.

(32)

Chapter 3 D2D Communication

In this chapter various aspect related to the D2D communication on LTE-Advanced networks are investigated. In 3.2 the interference problem due to resource sharing is explained. In 3.3 is reported a possible method for estimate the channel quality for the D2D link. In 3.4 are identified the possible Control and Data Channels involved in a D2D communication. In 3.5 the Single-Cell and Multi-Cell scenario are presented, highlighting the challenges that have to be faced. At last in 3.6 an overview of the State of the Art is given.

3.1 3GPP on D2D Communication

D2D communications commonly refer to the technologies that enable devices to com-municate directly without an infrastructure of access points or base stations, and the involvement of wireless operators. In this work we investigate the requirements, feasibility and possible benefits of supporting D2D communications in LTE/LTE-A Network. As specified by 3rd Generation Partnership Project (3GPP) on TR 22.803 [1] two UE satisfying some proximity criteria, under continuous network control and under 3GPP network coverage can communicate with each other for various purposes:

• Commercial/Social use • Network Offloading • Public Safety

In 3.1 is represented a Single-Cell scenario where UE1 and UE2 communicates with each other. Standard data-path(solid blue lines) involves the eNodeB and the Serving

(33)

Gateway (SGW) or Packet Data Network Gateway (PGW).

Figure 3.1: Data Path in a standard LTE communication

If UEs are in proximity with each other they may be able to communicate in Direct-Mode (D2D Communication). In this case Data-Path (i.e., the path used by LTE data channels) (solid blue line) involves only the two UEs as we can see in figure 3.2 (No involvement of eNodeB and SGW/PGW).

Figure 3.2: Data Path in a D2D LTE communication

The Control-Path (i.e., the path used by LTE control channels) is quite the same as for INFRA mode. In Figure 3.3 the control path for a D2D communication is represented by the solid black arrows. In dashed black arrow is represented the possibility to establish an additional control channel between the two UEs directly (not present in the INFRA mode).

(34)

Figure 3.3: Control Path in a D2D LTE communication

3.2 The Interference Problem in D2D

Communi-cations

Sharing Radio resources with Cell UEs leads to a new type of Intra-Cell Interference that was absent in presence of standard Cell Communication. In [3] the authors consider the impact of Interference in sharing Downlink/Uplink resources between D2D and Cell users. Results show that reusing Uplink resources is a better solution due to underutilization of Uplink channel (in LTE FDD) and better overall SNR values (especially when the D2D users are far away from the eNodeB). So using and sharing Uplink resources is the better choice for D2D Communication and will be one of the assumptions for our work. Figure 3.4 illustrates the possible interference in sharing the same Uplink resources at the same time.

(35)

Figure 3.4: Interference problem in sharing Uplink resources

D2DA Tx and D2DA Rx forms a D2D Pair where D2DA Tx is the transmitter and D2DA Rx the receiver. D2DB Tx and D2DB Rx forms another D2D pair that shares the same Uplink resources of D2DA Tx, D2DA Rx and CellUE. CellUE rapresents a Cellular User. During the Uplink period D2DA Rx is exposed to the interference of the CellUE and D2DB Tx. Also, D2DA Tx creates interference on the eNodeB and on D2DB Rx. Similar interference consideration can be made for D2DB Tx, D2DB Rx and CellUE. In (figure) authors try to limit the impact of interference by re-allocating Uplink resources in a proper way: they assign the same resources between the CellUE and a D2D Pair with the minimun channel gain between them.

3.3 Channel Estimation in D2D Communication

For feasible communication between two UEs it is fundamental to estimate the chan-nel between the two devices. In [2] authors describe a method for chanchan-nel estimation between UEs. The method is reported here: Hypothesis:

(36)

• UE1/UE2 can perform CQI estimation from the received SRS transmitted by its D2D peer

Process:

• eNodeB send a special CQI D2D report request to UE1 and UE2 • UE1 and UE2 send to each other a SRS

• UE1 and UE2 calculate CQI based on received SRS

• UE1 and UE2 send calculated CQI to eNodeB through PUCCH A graphical representation is reported in 3.5.

(37)

3.4 Control and Data Channels

In 3.6 a data transmission procedure is reported identifying the possible Control and Data Channels between the eNodeB and D2D UEs: control channels are represented by solid black arrows while data channels are represented by solid cyan arrows.

Figure 3.6: Control and Data Channels between eNodeB and D2D UEs • PUCCH (SR, CQI) and PUSCH (BSR) directed to the eNodeB are used like

in Standard Cell Communication.

• PUCCH (ACK NACK) directed to the D2D Tx are used like in Standard Cell Communication except for the destination.

• PUSCH (data) directed to the D2D Rx are used like in Standard Cell Com-munication except for the destination.

• PDCCH (UL grant) is used by the eNodeB like in standard Cell communication except for the destination that now is the D2D Rx (not the eNodeB).

(38)

3.5 Single-Cell and Multi-Cell D2D

Communica-tion

A communication between two D2D users can take place:

• Between two devices belonging to the same cell: Intra-Cell communication. • Between two devices belonging to different, but adjacent, cells: Inter-Cell

com-munication.

In 3.7 is reported a Single-Cell scenario i.e. a scenario where only Intra-Cell D2D communications take place. In blue is reported the Intra-Cell communication Link that can take place on Downlink or Uplink channel. In red is reported an INFRA communication between two users belonging to the same cell. The Link Selection can be performed between the red and blue link only. Here the scheduling decision are taken entirely by the scheduler on the cell A. In 3.8 is reported a Multi-Cell scenario. It is reported only the new communication possibility: an Inter-Cell D2D communication. The old communication possibilities seen in Figure 3.7 are obviously valid in this scenario too (they are not reported for sake of simplicity). Here only two cells are represented (cell A and cell B) but a transmitter that resides in the A cell can have a D2D communication with a receiver in any of the neighbouring cells. In order to take Link Selection and Scheduling decisions there’s the need of some kind of coordination between the cells involved in the Inter-Cell D2D communication. From the Scheduling point of view since the resource allocation is done for the transmitters, only the scheduler on the cell A is aware of the transmission. There’s the need of a mechanism to reduce the interference on the receiver side (that resides on the B cell) i.e. a mechanism to prevent the scheduler of the B cell to allocate the same resources to potentially interfering transmitters.

(39)

(40)

(41)

3.6 State of the Art

In literature various aspects of the D2D communication are investigated but the ma-jority of them is focused on the Interference and Power control. Here are present some of the most relevant contributions. In [8] the authors propose two MINLP problem for allocation of Uplink and Downlink resources. They introduce the limitation that the same RBs assigned to an INFRA communication can be allocated at most to one D2D communication. Only quality of channel is taken into account: no cell load and no rate constraints are considered. In [9] the authors present both a mode selection (Link Selection) and resource allocation scheme. The mode selection is however based only on channel quality experienced by two communicating UEs so omitting any con-sideration about the available resources. None are meant for running in a TTI (since link selection cannot be performed at a TTI time-scale). Only a single-cell scenario and reuse of Uplink resources are concerned. In [4] the authors propose an MINLP problem for resource allocation and a greedy heuristics for solve the problem at a TTI Timescale. One of the major limitations of the work is to enable resource sharing between one INFRA communication and at most one D2D communication. Nothing is said about how Link Selection is made and Inter-Cell communication is not taken into account. In [10] the authors propose an Interference-Aware graph based resource sharing algorithm with some limitations:

• Each communication link ,INFRA or D2D, can be allocated at most one RB through every scheduling process

• Only a single-cell scenario is concerned

• No hint on how Link Selection is made is given

(42)

In [11] the authors face the problem of packets overscheduling for D2D UEs using channel-aware schedulers. Considering the dynamic channel conditions in D2D con-nections the PF metric will generally be fairly high. This means that the scheduler will choose more likely to schedule a D2D User over an INFRA one. They however focus only on packet scheduling leaving others problems such as Link Selection, Conflict-Aware scheduling or Inter-Cell communication untreated. In [12] the authors present a method and apparatus for enabling scheduling and control of direct link communi-cation in a cellular communicommuni-cation system. The examples of allocommuni-cation, reported from the point of view of the WRTU (wireless transmit/receive unit), treats only the Tx and Rx moments during a D2D communications using LTE FDD DL/UL bands (half and full duplex) and an LTE TDD spectrum. No references about the packet schedul-ing at the eNodeB, no Link Selection etc. . . In [13] the authors propose a method for selecting the appropriate D2D mode (dedicated DL/UL or reusing DL/UL) at the UE level or eNodeB level through channel probing. No mention about Packet Scheduling, interference management and Link Selection. In [14] a QoS-Aware mode selection and Uplink resource allocation scheme is proposed. They not only consider the quality aspects of channel, but also take into account QoS constraints. However there is no mention about the execution period of the proposed algorithms and none is said about the possibility of an Inter-Cell D2D communication.

(43)

Chapter 4 OMNet++ simulator

4.1 Overview of the the OMNet++ simulator

OMNeT++ is an object-oriented modular discrete event network simulation frame-work. OMNeT++ itself is not a simulator of anything concrete, but rather provides infrastructure and tools for writing simulations. One of the fundamental ingredi-ents of this infrastructure is a component architecture for simulation models. Models are assembled from reusable components termed modules. Well-written modules are truly reusable, and can be combined in various ways like LEGO blocks. Modules can be connected with each other via gates (other systems would call them ports), and combined to form compound modules. The depth of module nesting is not limited. Modules communicate through message passing, where messages may carry arbitrary data structures. Modules can pass messages along predefined paths via gates and connections, or directly to their destination; the latter is useful for wireless simu-lations, for example. Modules may have parameters that can be used to customize module behaviour and/or to parametrize the model’s topology. Modules at the lowest level of the module hierarchy are called simple modules, and they encapsulate model behaviour. Simple modules are programmed in C++, and make use of the simulation library.

4.1.1 Discrete event simulation

A discrete event system is a system where state changes (events) happen at discrete instances in time, and events take zero time to happen. It is assumed that nothing (i.e. nothing interesting) happens between two consecutive events, that is, no state

(44)

change takes place in the system between the events. This is in contrast to continuous systems where state changes are continuous. Systems that can be viewed as discrete event systems can be modeled using discrete event simulation, DES. For example, computer networks are usually viewed as discrete event systems. Some of the events are:

• start of a packet transmission • end of a packet transmission

• expiry of a retransmission time-out

This implies that between two events such as start of a packet transmission and end of a packet transmission, nothing interesting happens. That is, the packet’s state remains being transmitted (Note that the definition of “interesting” events and states always depends on the intent and purposes of the modeller). Discrete event simulation maintains the set of future events in a data structure often called FES (Future Event Set) or FEL (Future Event List). A pseudo-code for the execution of a DES is reported in Listing 4.1.

Listing 4.1: Pseudo-code for DES

i n i t i a l i z e −− t h i s i n c l u d e s b u i l d i n g t h e model and i n s e r t i n g i n i t i a l e v e n t s t o FES

while (FES not empty and s i m u l a t i o n not y e t c o m p l e t e ) {

r e t r i e v e f i r s t e v e n t from FES t := timestamp o f t h i s e v e n t p r o c e s s e v e n t

( p r o c e s s i n g may i n s e r t new e v e n t s i n FES or delete e x i s t i n g o n e s )

}

(45)

The implementation of the FES is a crucial factor in the performance of a discrete event simulator. In OMNeT++, the FES is implemented with binary heap, the most widely used data structure for this purpose

4.2 Modeling concepts

An OMNeT++ model consists of modules that communicate with message passing. The active modules are termed simple modules; they are written in C++, using the simulation class library. Simple modules can be grouped into compound modules and so forth. The whole model, called network in OMNeT++, is itself a compound module. Messages can be sent either via connections that span modules or directly to other modules. Modules communicate with messages that may contain arbitrary data, in addition to usual attributes such as a timestamp. Simple modules typically send messages via gates, but it is also possible to send them directly to their destination modules. Gates are the input and output interfaces of modules: messages are sent through output gates and arrive through input gates. An input gate and output gate can be linked by a connection. Modules can have parameters. Parameters can be assigned in either the NED files or the configuration file omnetpp.ini. Parameters can be used to customize simple module behavior, and to parameterize the model topology. An OMNeT++ model consists of the following parts:

• NED language topology description(s) (.ned files) that describe the module structure with parameters, gates, etc.

• Message definitions (.msg files). You can define various message types and add data fields to them. OMNeT++ will translate message definitions into full-fledged C++ classes.

(46)

4.3 The SimuLTE

TM

framework

SimuLTETMis a framework for the OMNet++ simulator that enables complex system level performance evaluation of LTE and LTE-Advanced networks (3GPP Release 8 and beyond). In this work the Framework is used as a starting point to add D2D capabilities to both the eNodeB and the UEs. A more detailed explanations of the customization made to support D2D communication are reported in Chapter 6 .

(47)

Chapter 5 The Link Selection and Resource

Allocation problem

The purpose of this document is to describe pairing algorithms, i.e. decision algo-rithms that state on which link a communication should take place, whether the D2D or the IM one, given that the two endpoints are in the same cell. Call D the set of flows that may (or may not) take place using D2D, selected by means that are outside the scope of this document (e.g., topological proximity, estimated through a positioning algorithm). In other words, D is a set of possible ordered UE pairs: note that, for UEs i and j, (i, j) and (j, i) are two distinct such pairs, since the decision on whether to use the d2d or the infrastructure link must be made in both directions independently. We assume that the other UEs (those which cannot communicate through the direct link, whether because they have endpoints outside the cell or for technological reasons) are being scheduled as usual by the eNB, hence they will not be part of our decision algorithms, but they will eat up some of the UL/DL resources nonetheless. The Mode Selection algorithm is supposed to run at relatively long timescales, called periods (e.g., no less than tens or hundreds of TTIs). For the pairs of endpoints in D, we assume that we know the average rate achievable by pair i on link l ∈ {U L, DL, D2D}, called RL_i , measured in whatever meaningful way (e.g., by averaging the reported or estimated CQIs in the last period). Let ML are the avail-able RBs in both the uplink and the downlink directions, taking into account the fact that either direction might include flows which are outside the scope of this decision problem (i.e., uplink flows whose destination is outside the cell and/or downlink flows whose source is outside the cell). Ai is the required rate to be carried in

(48)

communi-cation i , measured in whatever meaningful way (e.g., inferred from the applicommuni-cation QCI and/or by averaging the sending rate in the past period). The pairing can be given as the optimum of a mathematical programming models. Several such models can be formulated, depending on two orthogonal choices:

• whether D2D flows resources are mutually exclusive or shared, i.e., whether it is possible or not to allocate two D2D flows on the same RBs (given favourable interference conditions).

• what is the objective of the optimization, i.e., whether we want to maximize the overall throughput (i.e., the sum of the D2D throughput and the IM through-put), minimize the eNodeB transmit power, or maximize the minimum normal-ized throughput (thus ensuring fairness), or combinations of the above.

All the formulated problems are based on the assumption that D2D communications take place in the UL channel as depicted in (figure). The solutions to the above models state whether each communication will be allocated on the D2D or the IM link, and what percentage of the links will be occupied by each communication. We distinguish the models based on the style of resource partitioning (i.e., mutually exclusive vs. shared), since this makes the biggest difference, and we begin with mutually exclusive resources, since this paves the way to understanding what happens with shared resources.

(49)

5.1 Link Selection

5.2 Resource allocation

In LTE/LTE-A networks the resource allocation is done per TTI basis applying what-ever scheduling policy is specified (MaxC/I, PF, DRR, etc . . . ). Allocation for D2D communication can be performed following two assumptions:

1. The D2D communications are treated as standard INFRA communications so the allocation is done in a mutually exclusive way (as 3GPP Standard two users cannot share entirely or partially the same resources)

2. The D2D communication can share the same resources (partially or entirely) with others communications: INFRA or D2D

For 1 there is no differences between D2D and INFRA communication. Once a policy scheduling is selected and flows are ordered the allocation is done in the LTE standard way because every communication is on mutually exclusive resources. This lead to a minimum interference allocation. For 2 there is a huge difference between D2D and INFRA communications. Here the allocator must support shared resource allocation between communications.

5.3 Models assuming mutually exclusive resources

The following problem maximizes the overall throughput (i.e., the sum of the d2d throughput and the IM throughput) subject to capacity constraints, given that D2D flows take place on mutually exclusive resources. We call this problem maximum

(50)

throughput (MT) problem. MaxX i∈D xD2D_i R_iD2D+ xU L_i R_iU L (5.1) subject to X k∈D xU L_i RU L_i /RDL_i (5.2) X k∈D (xD2D_i + xU L_i ) ≤ MU L (5.3) xD2D_i R_iD2D+ xU L_i R_iU L≤ Ai ∀i ∈ D (5.4) xD2D_i ≤ min{MU L, Ai/RD2Di }di ∀i ∈ D (5.5) xU L_i ≤ min{MU L_{, A} i/RU Li }(1 − di) ∀i ∈ D (5.6) di ∈ {0, 1}∀i ∈ D, xD2Di , x U L i ∈ R +_{∀i ∈ D}

In (5.1), di is a binary variable that is equal to 1 if the D2D link is used for

communication i, and 0 if the usual UL/DL handshake in infrastructure mode is used instead. M is the number of RBs given to communication i using link L. Our aim is to maximize the overall throughput, given both the uplink and the downlink may be cluttered by other transmissions. Constraint (5.2) concerns downlink transmissions: for a link assignment to be feasible, we cannot send in the uplink more traffic than we can carry in the downlink. Constraint (5.3) concerns uplink transmissions: both D2D and uplink IM transmissions must be fitted in the uplink frame. Constraint (5.4) states that the amount of resources given to communication i must be such that its required rate is satisfied (we remark that this is a maximization problem, hence this constraint will be active whenever possible). Constraints (5.5) and (5.6), finally, state that either the D2D or the infrastructure link is used for a communication. Constraint (vi) states that , which is a number of RBs, is a real-valued variable. This is somewhat counter-intuitive, but it stems from the fact that we are concerned with

(51)

average rates, hence we are deciding the fraction of resources that are going to be assigned to a communication in the long term, which may not be an integer number of RBs. The above problem can be easily transformed into others, simply by modifying the objective function and/or few constraints. The first variant is a minimum energy (mE) problem. Note, in fact, that the eNB does not consume power for D2D flows, whereas it does for IM flows that include a downlink leg. All it takes is to modify the following:

• The objective function becomes , i.e. minimize the number of RBs to be used in the downlink

• Constraint (5.3) becomes redundant (if the solution exceeds the right hand side of (i) there is simply no way to make a schedule)

• Constraint (5.4) must be reversed, since we are now facing a minimization prob-lem (otherwise the solver would just nullify each UL assignment).

A second variant is a maximum fairness (MF) problem. We want a solution to satisfy the same percentage of the requested rate. Ideally, it should be , i.e. every UE should receive 100% of the required rate. If, however, there is not enough space to do so (in either or both directions), the level of satisfaction should be the same for all the requests. This can be achieved by modifying the above problem as follows:

• The objective function becomes minP

i∈D

xU L

i RU Li /RDLi i.e. minimize the number

of RBs to be used in the downlink

• Constraint (5.2) becomes redundant (if the solution exceeds the right hand side of (5.2) there is simply no way to make a schedule).

• Constraint (5.4) must be reversed, since we are now facing a minimization prob-lem (otherwise the solver would just nullify each UL assignment).

(52)

A second variant is a maximum fairness (MF) problem. We want a solution to satisfy the same percentage α · Ai of the requested rate. Ideally, it should be α = 1

, i.e. every UE should receive 100% of the required rate. If, however, there is not enough space to do so (in either or both directions), the level of satisfaction α should be the same for all the requests. This can be achieved by modifying the above problem as follows:

• The objective function becomes Max α , where α ∈ R+

• Constraint (5.4) becomes xD2D

i RD2Di + xU Li RiU L ≥ α · Ai . Again, the direction

is reversed with respect to (5.1), since variables xL

i are not in the objective

function anymore.

• A constraint α ≤ 1 must be added, since UE requests should not be exceeded anyway.

Now, the three versions of (5.1) can be used for different purposes, and even combined to produce improved solutions. For instance, a maximum fairness-minimum energy (MFmE) problem may be setup, whose objective function is:

Max α − 1/K · 1/MDL_· P i∈D ·RU L i /RDLi

Where K is a large constant (e.g., 1000), and the constraints are those of the MF formulation. With the MFmE formulation, either of the following cases may happen: • some solutions exist such that α = 1 . In this case the second term in the

objective function will locate the minimum-energy one among these.

• There is no way to satisfy all the requests, hence α < 1 at the optimum. In this case, the trade-off between minimum throughput and energy is determined by K : a minimum throughput reduction can only be traded for a K-fold saving of downlink resources. It is thus clear that, for a suitably large K , increasing the minimum throughput will have priority over decreasing the energy consumption.

(53)

Problems such as (5.1) (including its variants) are Mixed Integer-linear Problems (MIPs) (binary variables being, in fact, integer). These problems are known to be NP-hard in general, unless some structure can be found that allows a polynomial solution algorithm. These are solved by branching on the binary variables, and may be fast, despite NP-hardness, if the size of the problem is small enough. Now, the number of variables and constraints of problem(s) (5.1) is O(|D|) . Since the number of D2D-capable pairs could be expected to be in the order of a few tens at most, this biases us to think that the problem may be solvable in reasonable times (i.e., split-second) using general-purpose solvers. This implies that the above problems could be solved periodically, at the minimum period allowed by the computational burden, the coherence time of the various constants (e.g., the average rates on each link and the amount of available resources in the UL/DL), and the technological constraints (e.g., the signaling latency required for a pair to switch to/from the D2D channel from/to the infrastructure one). When the computational burden represents the bottleneck, a heuristic can be devised to solve the MT problem

5.3.1 A greedy heuristic for the MT problem

We explain the greedy heuristic at a high level. We sort the pairs by decreasing Max{RU

i L, RDi 2D} , and loop through the sorted list allocating resources. When a

pair i is selected, variable diis set to the link yielding the highest rate (ties are broken

in favor of the D2D link), and the amount of resources required to match its rate is carved out of the UL and/or DL frames. The loop has three exit points, namely:

1. The UL frame is full. In this case, there is nothing more to do, and the maximum-throughput allocation has been achieved, because we ran through a list sorted by decreasing rate.

(54)

achieved, and it is equal to P

i∈D

Ai . In order to save power, we might use any

leftover space in the UL frame, if any, to clear some more space in the DL frame, by switching some pairs to the D2D link.

3. The DL frame is full and both the former two conditions are false. In this case, we sort the unscheduled pairs by decreasing D2D rate, RD2D_i , and we assign them to the D2D link until the UL frame is full or all pairs have been scheduled The above heuristic is O(|D|·log |D|) , due to the required sorting, hence can certainly be computed at the same timescales at which eNB scheduling is performed. Moreover, the only case in which it may not be optimal is when the DL frame is the bottleneck.

5.4 Models assuming shared resources

Sharing uplink resources may improve the overall throughput (more UEs served si-multaneously). Now problem 5.1 assumes that no frequency reuse is possible under D2D flows: in other words, flows i and j can only take place using different RBs. If, instead, we want to reuse frequencies (which may be possible, given that two remote D2D-UE pairs would hardly interfere at all with each other), then we must modify the above problem as follows:

• We construct a conflict graph of D2D flows. By doing this, we are assuming that only D2D flows are subject to frequency reuse, and that the portion of uplink frame reserved for IM flows is not to be shared.

• We schedule D2D flows in a portion of the UL frame, reusing RBs whenever two flows do not interfere with each other in the conflict graph.

A Conflict Graph is a graphical representation used for show the possible conflict between two entities. In this case a D2D-Pair forms a vertex and an edge between

(55)

entities (i.e., between D2D-Pair) represents a conflict. In 5.2 is reported, as an exam-ple, a scenario where all the D2D Flows are active at the same time (for simplicity only unidirectional links are reported).

Figure 5.2: Various simultaneous uplink communications

In 5.3 the associated conflict graph (one of the possible conflict graphs for the Pair in the scenario) is reported. A conflict between a Pair i and a D2D-Pair j is depicted by an edge connecting the vertices i and j. The presence of an edge between one or more vertices means that conflicting D2D Flows must be serialized.

(56)

Figure 5.3: Conflict Graph associated to figure 5.2

The modified version of problem 5.16 maximizes the overall throughput (i.e., the sum of the D2D throughput and the IM throughput) subject to capacity constraints, given that frequency reuse for D2D flows is possible.

MaxX i∈D xD2D_i RD2D_i + xU L_i RU L_i (5.7) subject to X i∈D xU L_i RU L_i /RDL_i ≤ MDL _(5.8) X i∈D (xD2D_i + nD2D) ≤ MU L (5.9) xD2D_i RD2D_i + xU L_i RU L_i ≤ Ai ∀i ∈ D (5.10) xD2D_i ≤ min{MU L_{, A} i/RiD2D}di ∀i ∈ D (5.11) xU L_i ≤ min{MU L, Ai/RU Li }(1 − di) ∀i ∈ D (5.12) πi+ xD2Di ≤ πj+ MU L· [oij + (1 − di) + (1 − dj)] ∀ (i, j) ∈ CG (5.13) πj+ xD2Dj ≤ πi+ MU L· [(1 − oij) + (1 − di) + (1 − dj)] ∀ (i, j) ∈ CG (5.14) πi+ xD2Di ≤ nD2D+ MU L· (1 − di) ∀i ∈ D (5.15) di ∈ {0, 1}∀i ∈ D, oij ∈ {0, 1}∀ (i, j) ∈ CG, xD2Di , x U L i , πi ∈ R+∀i ∈ D

(57)

We use a variable πi to denote where in the frame the transmission of link i starts.

That variable is continuous for the same reasons explained above. Moreover:

• Constraint (5.8) mirrors the one of problem (5.1), assuming that nD2D _{is the}

number of RBs reserved for D2D flows.

• Constraints (5.13),(5.14) and (5.15) define the sequencing of conflicting trans-missions i and j in the frame, assuming that i and j are D2D transtrans-missions. If they are not, all the three constraints are automatically verified, since MU L

is a large enough constant. Otherwise, whether (5.13) or (5.14) are active is determined by the oij variable, which thus provides the sequence.

Obviously, the same variants of problem (5.7) (MF, mE, MFmE) may be formulated as for problem (5.1). In order to distinguish the two versions, then, we will postpone the tags MER (Mutually Exclusive Resources) and SR (Shared Resources) when re-ferring to them, i.e., we will refer to (5.7) as MT-SR, etc.. As far as computations are concerned, we observe that the shared-resource versions of these problems are generally more complex. In fact, all the MIPs in this case have O(|D| + |E|) variables and constraints, where E is the set of edges in the conflict graph. The latter heavily depends on the position of the UE pairs, and it is always O|E| ≤ (|D| − 1)/2. There-fore, we can expect SR problems to be harder than MER ones, all else being equal. It is also inherently difficult to find good heuristics, given the interplay between the link decision (i.e., whether are to be set to zero or one) and the serialization decision. We terminate this section by observing that the pairing algorithm transforms the CG, which is by definition an undirected graph, into a directed acyclic one. In fact, assigning serialization decision oij implies defining the direction of the edge between

i and j, and serialization inequalities (5.13),(5.14) and (5.15) ensure that no loops occur.For this reason, we will call the directed conflict graph. Directed acyclic graphs can often be explored in polynomial time, which can be used to find heuristics for

(58)

their scheduling at the TTI level, as detailed in the next sub-section.

5.4.1 Packet Scheduling at the TTI timescale

The above algorithms are meant to define the link where communications take place and the percentage of resources that each of them should be allocated, so that the allocation achieves some pre-determined objective. They are meant to work at rela-tively long time-scales (i.e., tens or hundreds of TTIs at the very least), henceforth referred to as a period. It may happen that the pairing algorithms are given an input which they find to be unschedulable: for instance, the amount of required rate may simply be infeasible given the available space in the frames and the channel quality of each pair. In this case, decisions have to be made as to what course of action should be taken, and − in case − packet scheduling at the TTI timescale may play a role. Either of two things may happen:

• a certain number of pair is denied communication, hence a schedulable subset is only taken into consideration by the per TTI scheduler

• all pairs are reduced their rate with respect to their requirements (e.g., with MFmE problems). In this case, some other mechanism (e.g., selective discard, throttling, RED, proportional fair scheduling) should be employed to limit the rate of each pair, lest queue overload coupled with opportunistic scheduling at the TTI timescale thwarts fairness at the period timescale.

Assuming the above mechanisms are in place, scheduling at the TTI level is quite simple under the MER hypothesis, less so under the SR hypothesis. For MER, any traditional scheduling algorithm (e.g., MaxC/I, PF, RR, etc.) can be used in the presence of D2D flows, since D2D flows need not be distinguished from IM ones. Of course, prioritized versions of the above can easily be devised (e.g., a prioritized MaxC/I, giving priority to D2D flows, whose CQIs may be expected to be lower

(59)

than uplink CQIs of IM flows, or vice versa). For SR problems, instead, we need a TTI-level packet scheduler that enforces multiplexing of non-conflicting D2D flows on the same RBs, since this is the hypothesis under which the long-term planning has been approved (hence allocating resources in mutual exclusion would jeopardize stability). Therefore, traditional scheduling algorithms (which intrinsically assume mutual exclusion) cannot be used, hence ad-hoc ones have to be proposed. Hereafter, we present two TTI-level scheduling algorithms to share the uplink frame. The first one tries to achieve the maximum throughput by scheduling D2D and IM flows si-multaneously 1 _{. The second one schedules D2D flows in isolation, on either a fixed}

or a minimum amount of RBs. We denote as BD2D and BIM the set of backlogged

D2D and IM flows, respectively, at the TTI we are considering, and with DCGr the

restriction of the directed conflict graph to flows in BD2D . We use Qi to denote the

backlog, and Oij is the constant that sets whether D2D communication i precedes j

or vice-versa (obtained as a solution of the pairing problem).

1_{Note that, for TTI-level scheduling, IM communications also include those whose sink is not}

in the same cell (which were not considered in the pairing problem). In fact, although the pairing decision is not relevant for these, they have to be scheduled as well in the UL frame.

(60)

D2D/IM maximum-throughput scheduler The scheduling problem can be formulated as follows:

Max X i∈BD2D bi· CQIiD2D− pi + X i∈BU L bi· CQIiIM− pi (5.16) subject to X i∈BIM bi+ nD2D ≤ M (5.17) bi· CQIiX ≤ Qi+ pi ∀i ∈ BX, X ∈ {D2D, IM } (5.18) pi ≤ CQIiX − 1 ∀i ∈ BX, X ∈ {D2D, IM } (5.19) πi+ bi ≤ πj ∀i, j ∈ DCGr|Oij = 0 (5.20) πi+ bi ≤ nD2D ∀i ∈ BD2D (5.21) πi ∈ Z+∀i ∈ BD2D bi ∈ Z+∀i ∈ BX, X ∈ {D2D, IM } nD2D _{∈ Z}+

Where bi is the number of RBs given to a communication i, and πi is the start RB for

D2D communication i. Problem (5.16) attempts to maximize the amount of backlog cleared (minus the padding pi ), given the sequencing. We observe that sequencing

has to be enforced - as per constraint (5.19) - since it has already been decided during the pairing phase. Problem (5.16) is a MIP with O(|BD2D| + |BIM|) integer variables

and O(|BD2D| + |BIM| + |CGr|) constraints. Some performance evaluation is needed

to verify whether solving it is feasible at the TTI timescale. A simple improvement would be to check first whether sharing is really needed at all for D2D flows, and to solve (5.16) only if it is. In fact, if there is no need for sharing, any algorithm that clears all the backlogs will achieve the maximum throughput. The check is the

(61)

following: Max X i∈BD2D d Qi CQID2D i e + X i∈BIM d Qi CQIU L i e ≤ MU L _(5.22)

If (5.22) holds, then there is no need for sharing, since the available space is enough to have all d2d flows on mutually exclusive resources. Hence any algorithm will be able to fit all the flows in the available space (e.g., by sorting them according to any ordering and giving them enough RBs to empty their queues). If, instead (5.22) does not hold, we solve (5.16) optimally. It is also fairly easy to compute a necessary condition for all the backlog to be cleared at the given TTI. In fact, we can assign to each edge i,j in the DCG a weight equal to d Qi

CQID2D i

e, and solve the longest path problem (LPP) in polynomial time. The LPP problem is the dual of the (more famous) shortest path problem, and is solved using the same algorithm and negative edge weights. The LPP is the longest sequence that has to be enforced among d2d RBs if we want all the queues to be drained, hence it is a lower bound on nD2D (there is, in fact, no guarantee that the longest sequence will not need to be augmented by some other transmission). Call MLP P the length of the LPP. It is then straightforward to show that:

MLP P + X i∈BIM d Qi CQIU L i e ≤ MU L _(5.23)

Is a necessary condition for all the queues to be emptied (though, unfortunately, not sufficient). We terminate by observing that variants of the objective function can be envisaged, e.g., proportional fairness or any kind of priority obtained by combining waiting time, channel conditions and historical rate. All these variants are trivially implemented by multiplying the number of RBs bi in the objective function for a

(62)

D2D Maximum-Throughput Scheduler

In this case, we assume that the eNB schedules IM flows in isolation (using whatever strategy, e.g., MaxC/I). The problem below schedules d2d flows using either a fixed or a minimum number of RBs. A fixed-resources problem can be solved if:

• Resources are reserved statically for d2d flows

• IM flows are scheduled first, hence having priority over d2d, hence d2d flows are scheduled on the leftover RBs

On the other hand, a minimum-resources problem is to be solved if d2d flows have priority over IM, hence we schedule them first, while trying to leave as much room as possible for IM flows. c The minimum-resources problem can be formulated as follows: Max X i∈BD2D bi· CQIiD2D− pi + nD2D/2 (5.24) subject to nD2D≤ MU L _(5.25) bi· CQIiD2D≤ Qi+ pi ∀i ∈ BD2D (5.26) pi ≤ CQIiD2D− 1 ∀i ∈ BD2D (5.27) πi+ bi ≤ πj ∀i, j ∈ DCGr|Oij = 0 (5.28) πi+ bi ≤ nD2D ∀i ∈ BD2D (5.29) πi ∈ Z+ ∀i ∈ BD2D bi ∈ Z+ ∀i ∈ BD2D nD2D_{∈ Z}+

Where D2D flow i starts from RB πi . Problem (5.24) attempts to maximize the

Interference-Aware Mode Selection and Resource Allocation for Device-To-Device (D2D) communications in LTE-Advanced Networks

Department of Information Engineering

Master of Science in Computer Engineering

Interference-Aware Mode Selection and Resource Allocation

for Device-To-Device (D2D) communications in

LTE-Advanced Networks

Abstract

Table of Contents

List of Tables

List of Figures

List of Acronyms

Chapter 1

Introduction

1.1

Device-To-Device Communication

1.2

Thesis contributions

1.3

Overview of the Results

1.4

Organization of this Thesis

Chapter 2

LTE: the Long Term Evolution

2.1

Why LTE?

2.2

System Architecture

2.3

Radio Resource and Transmission Techniques

2.3.1

The time-frequency Resource Grid

2.3.2

Orthogonal Frequency Division Multiple Access

2.3.3

Single-Carrier Frequency Division Multiple Access

2.4

User plane Protocols

2.4.1

Air Interface Transport Protocol

2.4.2

Medium Access Control Protocol (MAC)

2.4.3

Hybrid Automatic Repeat Request

2.5

Scheduling

2.5.1

BSR report and eNodeB scheduling for Uplink

trans-mission

2.5.2

CQI and SRS

Chapter 3

D2D Communication

3.1

3GPP on D2D Communication

3.2

The Interference Problem in D2D

Communi-cations

3.3

Channel Estimation in D2D Communication

3.4

Control and Data Channels

3.5

Single-Cell and Multi-Cell D2D

Communica-tion

3.6

State of the Art

Chapter 4

OMNet++ simulator

4.1

Overview of the the OMNet++ simulator

4.1.1

Discrete event simulation

4.2

Modeling concepts

4.3

The SimuLTE

framework

Chapter 5

The Link Selection and Resource

Allocation problem