the energy efficiency guarantees that users form a cluster only if energy
efficiency increases.

#####  3.3.2 Cluster Formation Algorithm

The problem of finding optimal coalitions is NP-complete because it requires
evaluating all possible partitions of the set of users $U$ in the network.
Obviously, the existing base stations with limited computational resources are
not able to handle an NP-complete problem involving a few tens of users.
Hence, we adapt the simple merge and split algorithm to solve the coalition
formation problem with low complexity [152, 153]. Although merge and split is
a trivial method for dynamic cluster formation, it was shown to be a good
alternative when computational overhead is of concern [153]. The merge and
split rules are defined as follows: $(i)$ merge any set
$\left\\{S_{a_{1}},..,S_{a_{k}}\right\\}$ into a unique coalition (i.e.,
cluster), if
$\sum_{i=1}^{k}\nu(S_{a_{i}})<\nu\left(\cup_{i=1}^{k}{S_{a_{i}}}\right)$;
$(ii)$ if the previous inequality does not hold for a coalition that can be
described as $\cup_{i=1}^{k}S_{a_{i}}$, then split it into its components.
Refer to [152] for the proof of convergence and $D_{hp}$-stablity of this
approach.

#####  3.3.3 Payoff Allocation

The payoff of a cluster member is defined as the amount of throughput which it
receives from the total cluster throughput. Formally, let $G\in S$ be a
cluster of size $|G|$, and $\bar{x}=\\{x_{1},\dots,x_{|G|}\\}$ the payoff
vector of members of $G$. A payoff vector is called cost efficient if
$\sum_{i\in G}x_{i}=\nu\left(G\right)$ [154]. Of course, we are only
interested in cost efficient payoff vectors.

Here, we chose to compare three mechanisms proposed in the literature, namely
Equal Share (ES), Weighted Share (WS) [154], and Shapley [152]. These
mechanisms allow us to illustrate how payoff allocation can impact clustering
decisions made by the users.

Equal Share (ES). Here, the clustering gain is equally divided among members.
The cost efficient payoff distribution used under equal share is formally
expressed as follows:

$\displaystyle x_{i}=\frac{\nu(G)-\sum_{j\in
G}\nu(\\{j\\})}{|G|}+\nu(\\{i\\}),\quad i\in G.$ (3.22)

Weighted Share (WS). Here, the payoff distribution is computed based on
positive weights $\omega_{i}$:

$\displaystyle x_{i}\\!=\\!\frac{\omega_{i}}{\sum\limits_{j\in
G}\omega_{j}}\cdot[\nu(G)\\!-\\!\sum_{j\in
G}\nu(\\{j\\})]\\!+\\!\nu(\\{i\\}),\,i\in G.$ (3.23)

Shapely Share (SS). This is an alternative payoff distribution method that
accounts for marginal contribution of each cluster member. The “Shapley value”
is known to maintain good fairness while considering the contribution of the
users in the cluster [152]. The Shapley value of user $i$ in cluster G is
computed as follows:

$\displaystyle x_{i}\\!=\\!\\!\\!\\!\\!\sum\limits_{S\subseteq
G\setminus\\{i\\}}\\!\\!\\!\\!\\!\\!\frac{|S|!\left(|G|-|S|-1\right)!}{|G|!}\left[\nu\left(S\cup\\{i\\}\right)-\nu\left(S\right)\right].$
(3.24)

As shown in [12], the clustering gain is mainly due to the presence of good
users, whereas the channel state probability distribution of a cluster does
not dramatically improve with the addition of a poor user (see Figure 2 in
[12]). Hence, ES may not strongly motivate good users to cluster with poor
users. In contrast, by adjusting $\omega_{i}$ in Eq. (3.23), we can make sure
that users with better channel quality receive enough incentive to cluster.
Specifically, in our numerical simulation, we use values of $\omega_{i}$ equal
to the user’s throughput achieved without clustering. Note that WS better
motivates good users to join clusters but it may not achieve a fair payoff
distribution (as SS) and tuning $\omega_{i}$ for a complete fair payoff
distribution can be challenging in real implementation. Using Shapley value,
we do not need $\omega_{i}$ because Shapley value is designed in such a way
that it distributes the payoffs based on the marginal contribution of each
user. Moreover, Shapley value ensures that all clustered users receive at
least what they would have received without clustering. Therefore we do not
need to add $\nu\\{i\\}$ in Eq. (3.24).

We assume that the overhead due to cluster formation is negligible in
comparison to the time users spend in the cluster. Nonetheless, both discovery
and WiFi connection setup procedures consume time and energy for a few
seconds. Thus, our proposal is not suitable for high speed mobile scenarios.

So far we investigated our proposal analytically, however, the question
remains: Is it possible to implement a network-controlled opportunistic D2D
system in real world with LTE-A and WiFi? We answer this question in the next
section and in chapters 4 and 5.

####  3.4 Performance Evaluation

In this section, we perform numerical and packet simulations to benchmark our
proposed D2D schemes (CL(WRR) and CL(MR)) against Round Robin (RR) and
Proportional Fair (PF) [63] schedulers in an FDD LTE-A SISO system, whose
capacity is $80.64$ Mbps achieved by using a $20$ MHz band and neglecting LTE
overheads (which would reduce the capacity to $\sim 75$ Mbps). The MCS values
in this manuscript are adopted from [155]. For the sake of tractability, in
the analysis we assume that mobile users belong to one of three predefined SNR
classes, which correspond to poor, average, and good mean SNR. The designated
SNR for different classes are chosen in a manner that the mean achievable
rates for poor, average, and good users are $20\%$, $50\%$, and $80\%$ of the
maximum transmission rate achievable in the system, respectively. With the
thresholds and MCS values adapted from [155], the designated SNR values are
$7$ dB, $16$ dB, and $23$ dB, respectively for poor, average, and good users.
Note also that using non-homogeneous channel qualities allows us to evaluate
the long-term system fairness under different (opportunistic) scheduling
mechanisms. The numerical simulations are based on the results obtained using
Mathematica software from the model presented in Sections 3.2 and 3.3. Each
experiment is repeated $2000$ times. The packet simulations are obtained from
our home-grown simulator that reproduces PHY, MAC (i.e., resource allocation
and scheduling) and IP operation. The duration of packet simulations is $60$ s
which is repeated with $25$ different seeds. The values of power related
parameters are derived from [148, 149]. The results reported here include
average, $25^{th}$ and $75^{th}$ percentiles of the achieved performance
figures. The payoff allocation method is Equal Share Eq. (3.22) unless
otherwise specified.

#####  3.4.1 Performance of Static Clusters

This subsection provides the evaluation of throughput, fairness, and energy
efficiency achievable using D2D clustering schemes. For the sake of clarity,
we consider a static scenario, formed by users with heterogeneous average SNR
(see Figure 3.2). In this scenario, clusters C$1$, C$2$, C$3$, and C$4$ have
$2$, $4$, $6$, and $8$ users, respectively. In each experiment, the SNR class
of each user is chosen as poor, average, or good with the same probability.
Although the number of users might be higher in a reality, this scenario is
intended as a toy example that sheds light on potentials of the proposed
schemes.

Figure 3.2: Evaluation topology for static clusters.

Figure 3.3 illustrates the average user performance under different
schedulers. Figure 3.3(a) shows that users receive the lowest throughput under
RR because they are scheduled irrespective of their channel quality. Instead,
PF has remarkably better performance in terms of throughput, due to its
opportunistic nature. Nevertheless, both RR and PF are significantly
outperformed by D2D-clustering schemes in terms of throughput and energy
efficiency. Interestingly, D2D-clustering schemes result in better energy
efficiency than PF, although the users should maintain the WiFi interface
active, in addition to the cellular interface. This stems from the higher
throughput gain achieved by D2D-clusters and the insignificance of WiFi power
consumption in comparison with LTE. Since in D2D cluster users with better
channel quality are more active than those with poor channel quality, we
illustrate the per-SNR class user throughput and user energy efficiency in
Figures 3.3(b) and 3.3(c). In terms of throughput, all classes of users enjoy
higher throughput than RR and PF. D2D-clustering schemes also outperform RR
and PF in terms of energy efficiency with the exception of CL(WRR) in which
the good users can obtain higher energy efficiency under PF scheduler. Recall
than in this scenario the clusters are fixed and users do not decide on the
cluster formation. Therefore, the good users may be forced to form a cluster
with low throughput gain which leads to lower energy efficiency. This
observation highlights the importance of cluster formation strategies that
were discussed in Section 3.3. Between D2D clustering schemes, CL(MR) has
higher throughput and energy efficiency performance due to the adoption of a
more aggressive opportunistic cluster selection scheme.

(a) Throughput and energy efficiency

(b) Throughput

(c) Energy efficiency

Figure 3.3: Average per-user and per-class throughput and energy efficiency
performance.

(a) Per-cluster throughput

(b) Aggregate cell throughput

(c) Jain’s fairness indexes

Figure 3.4: Per-cluster and aggregate performance.

Figure 3.4(a) shows the impact of cluster sizes on the throughput of each
cluster. For comparison, we also report the aggregate throughput achieved by
cluster members if they were scheduled according to RR or PF. Therefore,
results with RR and PF scale linearly with the cluster size. Similarly,
CL(WRR) shows linearity, while the high variability of results for CL(MR) does
not allow us to confirm or reject the hypothesis that CL(MR) scales linearly.
This behavior is due to the fact that CL(MR), differently from CL(WRR), does
not guarantee a minimum airtime to any cluster, so that clusters not including
good users will receive little throughput.

Figure 3.4(b) sheds light on the aggregate throughput performance. The figure
reports results for three sub-scenarios with varying SNR class distribution.
SC1 with the $60$% poor, $30$% average and $10$% good users represents a cell
with more low quality channel users. In SC2 there is equal distribution of
different SNR classes (i.e., $33.\overline{3}$%). Finally, SC3 represents a
cell with more high channel quality users where there are $10$% poor, $30$%
average and $60$% good users. The figure also reports the upper bound for the
downlink throughput. The aggregate throughput of RR and PF is outperformed by
CL(WRR) and CL(MR). CL(MR) practically hits the upper bound, while the worst
case for CL(WRR), i.e., when the number of poor users is predominant,
outperforms RR and PF under their best performance.

So far, CL(MR) outperforms all other schedulers. However, considering
fairness, CL(MR) is always the most unfair, especially when more poor users
are present, while CL(WRR) performs like PF in terms of fairness, see Figure
3.4(c).

#####  3.4.2 Packet Simulation with Static Clusters

In the previous subsection, the network performance was studied in a saturated
network (i.e., fully backlogged assumption). In order to better analyze the
impact of clustering, we evaluate the same scenario (see Figure 3.2) in a non-
saturated network (i.e., $50$ Mbps) using our home-grown LTE simulator
developed with the Mathematica software tools. Here, in addition to throughput
and fairness we focus on the delay in the LTE cell and the load offered to the
WiFi network, which provides us with better insight on the practicality of our
scheme. The average SNR of users is selected randomly with a uniform
distribution between $7$ dB to $23$ dB. The instantaneous channel quality of
the users follows a Rayleigh distribution. Users have heterogenous Poisson
packet arrivals with the total load of $50$ Mbps that allows us to validate
the benefits of our D2D-assisted scheme when the network load is below
saturation.

(a) Delay CDF of delivered packets.

(b) Packet delivery ratio of the schedulers.

(c) WiFi Direct load per user.

Figure 3.5: Delay CDF, packet delivery ratio, and per-user WiFi Direct loads.

Figure 3.5(a) shows the delay CDF of the delivered packets. Here, we only
account for the packet delivery time from the eNB to the UE, whereas the time
to receive the ACK is not counted. The figure shows that our proposed schemes
maintain a $1$ ms delay with $90\%$ probability while RR and PF require $10$
ms to reach this threshold. The delay performance of a scheme is mainly
affected by the achievable throughput and its prioritizing policy. If the
achievable throughput is low, the packet waiting time increases which results
in higher delays. On the other hand, a scheme that highly prioritizes a
certain class of users (e.g., best instantaneous channel quality) can
potentially increase the queue size of the other classes of users. The latter
is the reason why CL(MR) yeilds higher delay than CL(WRR). D2D-clustering
schemes can guarantee delays lower than $10$ ms with $97\%$ probability or
higher, leaving at least $40$ ms of delay budget for WiFi transmissions. Note
that the WiFi delay budget is enough to support real time applications such as
video conferencing.

In Figure 3.5(b), we can observe that CL(WRR) outperforms other schemes in
terms of successful packet delivery ratio. The outstanding results of CL(WRR)
are because of the throughput gain from D2D-clustering and fair resource
allocations which avoids starvation of low priority users. On the other hand,
CL(MR) and PF have comparable performance, although CL(MR) can potentially
achieve higher throughput than PF. CL(MR) cannot outperform PF because of its
greedy behavior in prioritizing high channel quality users.

Figure 3.5(c) illustrates the load offered to the WiFi network under CL(WRR)
and CL(MR). This figure confirms that WiFi Direct is not a bottleneck in our
proposed architecture. The figure also shows that the maximum load offered to
C1 (users 1 and 2), C2 (users 3 to 6), C3 (users 7 to 12), and C4 (users 13 to
20) are less than $4$ Mbps, $12$ Mbps, $20$ Mbps, and $31$ Mbps, respectively,
i.e., no more than 4 Mbps per user, on average. The load variation for
different users depends on the channel quality. For instance, users $12$ and
$15$ relay more traffic because they have higher average SNR w.r.t. the other
users. In all cases, the traffic to be handled by each cluster is well below
typical WiFi capacities.

To summarize the results reported for static cluster evaluation scenarios, we
have observed that the clustering proposal not only increases the throughput
and the energy efficiency, but it can also increase the fairness level. In
particular, CL(WRR) achieves similar throughput and energy efficiency results
as CL(MR), but it is much fairer. Therefore, the advantage of using CL(WRR) is
sixfold: $(i)$ it offers the possibility to gain a high throughput with
respect to legacy RR and PF schedulers; $(ii)$ it allows each cluster to
exploit the clustering gain proportionally to its size; $(iii)$ it provides
nearly perfect fairness among users; $(iv)$ average energy efficiency is
increased with respect to RR and PF; $(v)$ it has the best delay performance
compared with other schemes; $(vi)$ it has much higher packet delivery ratio
(almost $100\%$). Since numerical and packet simulations showed that CL(MR)
may lead to poor fairness and packet delivery ratio, we will focus on the
CL(WRR) in the rest of the evaluation.

(a) Aggregate throughput

(b) Average per-user efficiency

(c) Fairness

Figure 3.6: Throughput, efficiency and fairness under different scheduling
mechanisms.

#####  3.4.3 Performance of Dynamic Clusters

In order to evaluate our proposal in a more realistic setup, we simulate a
network with variable number of users (from $1$ to $100$) with varying SNR,
randomly placed in a circular-shaped cell with $500$ m diameter. The SNR class
of a user is selected at random with a probability distribution that changes
according to the distance from the base station. In particular, the cell area
is divided into three areas. In the area close to the base station, the
probability of finding good users is higher than the area far from the base
station. The users move with an average pedestrian speed between $0$ and $5$
km/h. The maximum diameter of a cluster $d_{\text{m}}$ is $100$ m.

Figure 3.6 illustrates the performance metrics for different user population
sizes. In the figure, we report results achieved with RR, PF, CL(WRR) with
equal share, namely CL(WRR)-ES, CL(WRR) with weighted share, namely
CL(WRR)-WS, and CL(WRR) with Shapley share, namely, CL(WRR)-SS. Additionally,
we report results for PF when $n\geq 1$ users are scheduled per frame (PF $n$
in the figure). We report this comparison since user-based schedulers allocate
multiple users per frame, and it is indeed common to schedule tens of users
per scheduling interval, even when opportunistic schedulers are adopted.
However, RR and CL(WRR) are not affected by the number of users scheduled per
frame, due to the assumption that user’s channels are independent and
stationary (and so are the channels of cluster heads).

In Figure 3.6(a), we can observe that the clustering gain rises with the
number of users in the system, and as soon as about $30$ users are present,
CL(WRR) achieves the highest aggregate network throughput, which approaches
the upper bound with a reasonable cell population size of $100$ users. Since
CL(WRR) variants only redistribute the intra-cluster resources, they do not
differ over the aggregate network throughput. The throughput of PF reduces
significantly as the number of scheduled users per frame increases. However,
all PF curves converge, for high number of users, to a value well below the
throughput of CL(WRR). In Figure 3.6(b), we can observe that the energy
efficiency of CL(WRR) is the best. Overall, the energy efficiency decreases
with the number of users, due to the fact that each additional user incurs a
minimum cost due to activating the network interfaces, while the cell capacity
is upper bounded. However, e.g., with $70$ users, the efficiency of CL(WRR) is
higher than RR and PF $5$ by $\sim\\!\\!101\%$ and $\sim\\!\\!13\%$,
respectively. Recall that in Subsection 3.4.1 we observed that good users may
obtain lower energy efficiency than PF. Here, the cluster formation is only
allowed if all cluster members can achieve higher energy efficiency than what
they would achieve under PF. This reduces the throughput gain of D2D schemes.
As regards fairness, Figure 3.6(c) shows that CL(WRR)-ES provides the highest
fairness level followed by CL(WRR)-SS, while CL(WRR)-WS achieves results
comparable to the best results achieved by PF. The ES method exhibits better
fairness because of equal resource distribution. The SS method outperforms WS
because SS distributes the resource based on the contribution of each user to
the total revenue. The fairness improvement due to clustering with respect to
RR and PF $5$ or PF $10$, which are realistic figures for PF performance, is
remarkable.

We also investigate the impact of payoff distribution methods using our LTE
packet simulator, the results indicates that payoff distribution methods
behave very similarly in non-saturated scenarios because users receive the
requested resources. As the load approaches the saturation level, the WS
results in higher throughput and delay variations compared to ES and SS.
Considering the insignificant impact of payoff distribution method in non-
saturated networks, we can use simple payoff distribution methods such as ES
instead of SS that adds on to the practicality of D2D-clustering.

####  3.5 Summary

In this chapter, we have analyzed network-controlled opportunistic D2D
clustering from a theoretical point of view. We first provide a model for
throughput and power consumption of D2D-enabled clusters in LTE-A networks.
Next, we have used coalitional game theory technique to devise revenue
distribution schemes that encourage mobile users to form clusters. The
numerical simulations illustrated that using simple schedulers and game theory
techniques, our proposed architecture significantly outperforms legacy
schedulers in terms of throughput, delay, energy efficiency, and fairness.

###  Chapter 4 A ProSe-Compliant Opportunistic D2D Protocol

####  4.1 Introduction

3GPP is actively studying the feasibility and the architecture of ProSe (i.e.,
D2D communications) for both inband and outband D2D techniques. The latest
draft of the standard includes the provisional D2D network elements and their
expected functionalities. However, there is no concrete signaling and protocol
architecture as of today. Despite the unavailability of the standardization
for D2D communications, possible design could be mapped through the ongoing
feasibility studies and technical reports that deal with D2D (see in
particular [156, 7, 8]). In this chapter, we propose a network-controlled
protocol and position it with respect to the existing architecture of LTE-A
and WiFi Direct. Specifically, this chapter shows how to adapt LTE and WiFi
Direct to support our proposed D2D clustering scheme with minimal
modification. We show how clusters form in WiFi Direct, register to LTE,
obtain LTE connectivity and how the corresponding protocol stack for such a
system looks like. In addition, other important procedures such as feedbacks,
scheduling, security, etc., are elaborated.

####  4.2 A D2D Protocol for WiFi Direct in LTE Cells

This section elaborates on the details of our proposed protocol for D2D
communications using WiFi Direct in LTE network. Here, we refer to clusters as
groups in the cluster formation procedure in order to have the coherent
terminology with WiFi Direct specifications.

Figure 4.1: WiFi Direct group formation procedure. Figure 4.2: Group ownership
transfer in WiFi Direct between UE 1 and UE 2.

#####  4.2.1 Cluster Formation (WiFi Direct)

In our proposal, the first step is to form a cluster among User Equipments
which are willing to use D2D communications. The cluster formation procedure
is mostly coherent with that defined in WiFi Direct specifications [96]. The
major changes to the existing specifications are: $(i)$ the users/cluster
heads also announce their preferred payoff distribution method in the Probe
Requests; $(ii)$ the group ownership is transferable; and $(iii)$ the cluster
head receives the LTE ID from its client and shares this information in the
form of a forwarding table that contains the LTE and WiFi Direct IDs of all
members. Figure 4.1 illustrates the required steps for cluster formation
between two UEs. We briefly explain each step in the following.

Search and discovery. The UE either actively searches to join another UE/group
by sending Probe Request over the social channels (i.e, WiFi channels 1, 6 and
11) [96] or it listens to the social channels for the Probe Requests sent by
other UEs/groups. We propose to include a two-bit field to the Probe Request
in order to express information regarding the desired payoff method of the
UE/group. Upon reception of a desired Probe Request, the UE/ Group Owner (GO)
responds with a Probe Response message which initiates the 3-way group
ownership negotiation.

Group ownership negotiation. In this phase, the negotiating parties exchange
their Intent value and the UE with the highest Intent becomes the GO. In WiFi
Direct specification, Intent value is a number from $0$ to $15$ which shows
the UE’s willingness to be GO. In our proposal, the Intent value is the
average LTE Channel Quality Indicator (CQI) of the UE. The Intent value of an
existing GO, is the average of the Intent values of its group members. Hence,
both parties are able to compute an ex-ante revenue prior to group formation.
The negotiating parties can leverage the computed revenue to decide whether to
terminate or complete the connection setup.

Security setup and IP address allocation: Next, the GO initiates the WiFi
security setup using  Wireless Protected Setup (WPS). After the security setup
is complete, GO assigns IP address to clients following the DHCP protocol.

D2D specific messages. Our proposed D2D operation requires two additional
steps: $(i)$ each group client sends an LTE ID Notification message to the GO,
which contains its LTE identity (e.g., SAE-Temporary Mobile Subscriber
Identity (S-TMSI)); and $(ii)$ the GO broadcasts the WiFi-LTE ID Association
Table to all group clients.111In our proposal, two LTE IDs must be shared
among cluster members: $(i)$ the S-TMSI which is used in the registration
phase; and $(ii)$ Cell Radio Network Temporary Identifier (C-RNTI) which is
allocated to the UE after it is connected to the eNB.  This message includes
the LTE and WiFi Direct IDs of all cluster members. This message can also
include WiFi Direct group settings such as power saving parameters, useful to
quickly switch the GO when needed. Therefore, any group client can immediately
become the GO without tearing down the group.

LTE-WiFi mapping. Next, each group client sends an LTE ID Notification message
to the GO that contains its LTE identity. Finally the GO broadcasts the WiFi-
LTE ID Association Table that includes LTE and WiFi Direct IDs of all cluster
members.222In our proposal, the cluster members should share their S-TMSI and
C-RNTI with other cluster members. This message can also include other group
settings that are useful to quickly switch the GO when needed.

GO transfer. In WiFi Direct, the group ownership cannot be transferred.
However, our proposal requires the GO to change dynamically. A GO transfer
occurs when the eNB detects that another cluster member has a better cellular
channel quality than the current GO (for details, see CSI reporting and
Cluster head selection in Section 4.2.6). We define two messages to enable GO
transfer in WiFi Direct, as shown in Figure 4.2. First, the GO sends the Group
Information Transfer message to the provisioned GO. This message contains the
updated list of members and their power saving parameters. Second, the GO
sends the GO Modification broadcast message. Each group client should
individually acknowledge this message before the GO transfer is completed.

#####  4.2.2 Cluster Registration in LTE

Figure 4.3: Cluster registration procedure in LTE.

Once a cluster is formed over WiFi Direct, it should register at the LTE
network. Cluster registration procedure is shown in Figure 4.3, which reports
the required D2D-enabling modifications in red. This procedure consists of two
phases: $(i)$ cluster notification; and $(ii)$ cluster verification.

Cluster notification. The cluster formation over WiFi Direct is reported to
the eNB via Cluster RRC Connection Management message with Request Cause set
to connection initiation. This message also contains information such as
Identity of the members and their desired payoff allocation method (see Table
4.1). The eNB responds to the cluster notification with the RRC Connection
Setup message. Next, the cluster head sends the RRC Connection Setup Complete
to finish the RRC setup.

Table 4.1: Contents of Cluster RRC Connection Management Information Elements
---
|
Cluster Identity | To be assigned by eNB
Cluster Head Identity | S-TMSI
Cluster Clients’ Identities | S-TMSI of Client#1
(for initiation, all members should be included. Otherwise, only departing/arriving member(s) are listed.) | S-TMSI of Client#2
|  ⋮
Request Cause | CHOICE
|
| Connection Initiation
| Arrival
| Departure
Dedicated NAS Information (Attach Request)

Cluster verification. Once the RRC connection is established, the eNB sends a
Security Mode Command message to each cluster member via the cluster head. We
propose to include the Intent value (i.e., average CQI) of each cluster member
in this message. Since the eNB is aware of real CQI, each member can verify
the correctness of the values reported by others. If an anomaly is detected
the member can send a negative response and leave the group. The clients send
their response to the cluster head over WiFi and the cluster head forwards the
responses to the eNB. By forcing the security verification to pass through the
cluster head, the eNB ensures that all cluster clients are already members of
the cluster over WiFi. This step is very important in terms of security
because it ensures that any misreported value is detected.

#####  4.2.3 Bearer Establishment

After cluster registration, the cluster head should initiate the cluster
bearer establishment procedure. The difference between cluster bearer and UE
bearer is in resource provisioning. The allocated resources for a cluster
bearer are equivalent to the aggregate of resources allocated to all cluster
members. LTE standard defines two types of bearers, namely default and
dedicated, to support services with different QoS. The default bearer is
established once a UE attaches to the network and it remains until the UE
leaves the network. On the other hand, the dedicated bearer is established for
services with specific QoS requirement and it remains active for the life time
of the service. For brevity, we suffice to elaborate on the default bearer
establishment. The procedure of dedicated bear establishment requires minor
changes in the address field in order to accommodate all cluster members. The
procedure for default bearer establishment is depicted in Figure 4.4, and it
consists of three steps: $(i)$ bearer request, $(ii)$ bearer request response,
and $(iii)$ bearer request confirmation.

Figure 4.4: Signaling required for default cluster bearer establishment.

Bearer request. After cluster registration is completed, the eNB sends the
Attach Request to the Mobility Management Entity (MME). The MME determines the
International Mobile Subscriber Identity (IMSI) of each cluster member from
the information provided in EPS Mobile Identity fields of the Attach Request.
In case the IMSI of a member cannot be identified, the MME explicitly asks for
it. Next, the MME sends a Create Session Request to the Serving Gateway (S-GW)
which contains information such as IMSI of the cluster members and requested
Packet Data Network (PDN) connectivity. The S-GW updates its EPS Bearer table
and forwards the Create Session Request message to the PDN Gateway (P-GW). The
P-GW updates its EPS Bearer Context Table and generates a charging profile for
every member which does not have one yet.

Bearer request response. The P-GW responds to the S-GW request with Create
Session Response message. In this message the address (assigned by P-GW) and
QoS parameters (assigned by Policy and Charging Rules Function (PCRF)
333Here, the QoS parameters refer to both per-UE QoS parameter such as
Aggregate Maximum Bit Rate (AMBR) and per-bearer QoS parameters such as QoS
Class Identifier (QCI), Allocation and Retention Priority (ARP), and Maximum
Bit Rate (MBR).) fields are extended to accommodate all cluster members.
Naturally, QoS parameter of the cluster bearer is equivalent to the aggregate
of members’ QoS. Next, the S-GW forwards the Create Session Response message
to the MME which triggers the Initial Context Setup Request sent from the MME
to the eNB. This message provides the eNB with settings such as the IP address
and the QoS parameters of each cluster members. Again, the IP address and QoS
parameters fields of the Initial Context Setup Request message is extended to
accommodate all cluster members. Note that this reduces the signaling overhead
compared to standard LTE operation because the network does not need to send
this information to each UE separately. Finally, the eNB extracts the Attach
Accept message from the Initial Context Setup Request and sends it to the
cluster head in an RRC Connection Reconfiguration message.

Bearer request confirmation. The cluster head updates the cluster clients with
information received from the eNB. It also sends two messages to the eNB in
response to RRC Connection Reconfiguration message. An RRC Connection
Reconfiguration Complete message which is basically an acknowledgment to the
RRC Connection Reconfiguration and an Uplink Information Transfer message in
order to complete the NAS attach process. Upon reception of RRC Connection
Reconfiguration Complete, the eNB sends the initial context Setup Response to
the MME. This message acknowledges that the E-UTRAN Radio Access Bearer
(E-RAB) is successfully setup for the default bearer. It also provides an IP
address for communication between the eNB and S-GW for downlink data transfer.
After the eNB received the Uplink Information Transfer message, it sends the
Attach Complete message to the MME. The Attach Complete and Active Default EPS
Bearer Context Accept messages trigger the MME to send the Modify Bearer
Request to S-GW. This message mainly serves as an acknowledgement. Finally,
the S-GW completes the process by sending Modify Bearer Respond to the MME.

As concerns IP addressing, in LTE, each active UE has at least one default
bearer and each default bearer has a unique IP address. Therefore, if a
cluster member had bearer(s) before cluster formation, the P-GW keeps the
existing IP address(es) associated to the default bearer(s). Once the cluster
bearer is activated, the P-GW automatically terminates the old default
bearer(s).

#####  4.2.4 Mobility

In our proposal, UEs may join or leave at any time. In this section, we
elaborate the procedures for departure/arrival.

Arrival. Figure 4.5 depicts the procedure followed by a new arrival. In the
event of a new arrival, the cluster head sends a Cluster RRC Connection
Management to the eNB with the Request Cause set to arrival (see Table 4.1).
In this event, differently from cluster registration (see Section 4.2.2), the
cluster head only sends the S-TMSI of the new UE. After the eNB receives the
notification of new arrival, it sends a Security Mode Command to the cluster
head to verify the new member. After the verification phase, the eNB sends the
Cluster Bearer Resource Modification Request message, see Table 4.2, to the
MME. The MME replaces the S-TMSI identity in the Cluster Bearer Resource
Modification Request message with IMSI and forwards the message to the S-GW.
The S-GW updates the EPS Bearer Table and sends the Cluster Bearer Resource
Modification Request message to the P-GW. This initiates the standard LTE
bearer modification process as described in [157]. For the sake of brevity, we
will not explain the rest of the signaling messages because they follow the
standard LTE-defined procedure.

Figure 4.5: Signaling messages required for a new arrival.

Departure. The signaling procedure for a departure is very similar to that of
an arrival. The only procedural difference between arrival and departure is
that the eNB does not need to send the Security Mode Command in case of
departure. Moreover, according to WiFi Direct specifications, the members
should send a de-authentication message to the cluster head before departure.
The de-authentication message triggers the cluster head to initiate the
departure procedure. Nevertheless, if a UE sends an RRC Connection Request
message after it joined a cluster, the eNB assumes that the UE does not belong
to a cluster anymore.444Our proposal does not permit UEs to have user bearer
and cluster bearer simultaneously. In this case, the eNB initiates the
departure procedure without receiving the departure notification message from
the cluster head. If a UE is reported as a new arrival of a cluster (i.e.,
$C_{a}$) while it is listed as a member of another cluster (i.e., $C_{b}$),
the eNB initiates the departure procedure for $C_{a}$ and an arrival procedure
for $C_{b}$.

Table 4.2: Contents of Cluster Bearer Resource Modification Request
Information Elements
---
|
Identity of Departing/Arriving Member(s) | S-TMSI(s)
Request Cause | CHOICE
|
| Arrival
| Departure

#####  4.2.5 Data Plan Operation

Figure 4.6: Data flow between cluster client $i$ and the eNB.

Figure 4.6 illustrates the adaptation of LTE and WiFi Direct data protocol
stacks to our proposal. We choose to bridge, at the cluster head, the WiFi
Direct MAC and LTE at Packet Data Convergence Protocol (PDCP) layer for three
reasons: $(i)$ LTE packets are ciphered and integrity-protected in the PDCP
layer using keys which are only known to the client and the eNB. Therefore,
other UEs cannot decipher the LTE packets traversing the WiFi network; $(ii)$
the cluster head can further process PDCP Packet Data Unit (PDU)s in RLC layer
for concatenation/segmentation according to its LTE physical link quality; and
$(iii)$ the WiFi Direct MAC provides a robust and secure transmission service,
and natively allows to send frames to be relayed at MAC layer. Note that the
resulting LTE and WiFi Direct data transfer operations are decoupled. Indeed,
the cluster head uses the legacy ACK/NACK to secure all the handled LTE
traffic, so that ARQ/HARQ operations are managed at the cluster head only, as
if the exchanged LTE PDUs were all belonging to the cluster head. Similarly,
the normal ACK and retransmission mechanisms are used by the WiFi Direct
interface to transfer LTE PDUs in a legacy 802.11 payload.

Uplink. As concerns uplink transmission requests, the clients send their
Scheduling Request (SR) or Buffer Status Report (BSR) to the cluster head to
be forwarded to the eNB. The eNB uses Downlink Control Information (DCI) to
inform UEs regarding their downlink and uplink resource allocation. Since the
cluster head is the only member which is listening to the LTE channel, it
receives the DCI and updates the clients with the scheduling decision made by
the eNB, using an 802.11 management frame with the same subtype value used by
the UEs to encapsulate SR and BSR messages in the WiFi Direct frame. As
concerns data packets, the scheduled cluster clients encapsulate the LTE PDCP
PDUs in WiFi frames and send them to the cluster head. The cluster head
extracts the PDCP PDUs and forwards them to the eNB in the designated slot.
The cluster head transmits the packets to the eNB with the client’s C-RNTI
address in order to simplify the identification of the real source of the
packets for the eNB. Since LTE data packets are ciphered and integrity
protected, there are no security concerns and threats in operating LTE relay
over WiFi Direct as described in this chapter.

Downlink. The eNB transmits the packets using the client’s C-RNTI address but
it selects the MCS according to the cluster head’s channel quality. Since the
cluster head is aware of scheduling plan for its clients, it listens to the
downlink channel to receive the packets belonging to all cluster members.
Next, the cluster head encapsulates the PDCP PDUs in regular WiFi data frames
that include the source and destination MAC addresses of cluster head and
client, and the default MAC address of the eNB.

#####  4.2.6 Adaptation of LTE Procedures

So far we have defined the required messaging to support our proposed
architecture in LTE and WiFi Direct. Here, we elaborate on the adaptation of
our proposal to other important operations.

######  4.2.6.1 CSI reporting

In LTE, UEs send CSI reports to the eNB for scheduling purposes. In our
proposal, the cluster head sends the CSI reports of all cluster members to the
eNB. This creates some flexibility which does not exist in the standard LTE
operations. For example, the cluster clients can report the CSI over all sub-
bands to the cluster head over WiFi. Then the cluster head filters these
reports and sends the list of top candidates on each sub-band to the eNB.
Alternatively, the cluster head reports the n highest CQI to the eNB. The
value of $n$ imposes a trade-off between opportunistic gain and spectral
efficiency. Note that such a high resolution CQI report would not be possible
in normal LTE operations.

######  4.2.6.2 Cluster head selection

The eNB selects the cluster head among the cluster members based on the
reported CSIs. We propose to add an extra field to the DCI so that the eNB can
transmit the C-RNTI of the new cluster head to the current cluster head, which
can trigger the GO transfer procedure. The cluster head selection interval is
implementation-specific and it is constrained by the delay of LTE network and
group ownership transfer in WiFi Direct. This interval introduces a trade-off
between signaling overhead and opportunistic gain. On one hand the
opportunistic gain is maximized when the cluster head is selected on a per-
frame basis (shortest possible interval). On the other hand, per-frame cluster
head selection requires higher signaling overhead.

######  4.2.6.3 Label Switching

The relay UE experiences high computational overhead due to LTE frame
processing. Hence, we propose label switching at LTE PDCP layer instead of IP
routing which is the current solution in 3GPP. As mentioned earlier, the
byproduct of this design choice is the elimination of relay-related security
concerns.

######  4.2.6.4 Scheduling

The existing LTE scheduler can be adapted to support our proposal with a minor
modification. In LTE, the eNB selects the physical layer parameters based on
the CSI of the scheduled UE. However, our proposal requires the eNB to select
physical layer parameters according to the CSI of the cluster head so that the
cluster head can decode the packets and forward them to the corresponding
clients. Note that the eNB still uses the C-RNTI of the client in the DCI so
that the cluster head is aware of its transceiving schedule in uplink and
downlink. This also eliminates the need for an uplink intra-cluster scheduler
in the cluster head.

######  4.2.6.5 Security

As mentioned earlier, our proposal does not introduce any new security threats
to the existing LTE architecture because the LTE packets are ciphered and
integrity-protected before forwarding. We also propose to send Security Mode
Command through the cluster head, so that the cluster head cannot exploit a
UE’s resources that is not present in the cluster. The only possible attack is
a malicious cluster head that drops packets of its clients. The eNB can detect
such behavior by tracking communication failures of each cluster head and act
accordingly.

######  4.2.6.6 Policy control and charging

Since the cluster head is in charge of the LTE transmissions for all cluster
clients, it is important to make sure that the cluster head is not billed for
the clients’ traffic. The policy control and charging of LTE is done via
Policy and Charging Enforcement Function (PCEF) which charges the UEs based on
their IP address. Since each cluster member is given a separate IP address,
our proposal does not introduce any problem in billing. It is also important
to ensure that members do not utilize each other resources. Since the eNB
schedules the members individually, utilizing the other cluster members’
resources is not a concern. In case a malicious cluster head transmits its own
packets on a slot allocated to another member, the eNB discards the cluster
head data because it cannot be deciphered.

####  4.3 Summary

In this chapter, we proposed a practical protocol for supporting D2D
communications in cellular networks using WiFi Direct and LTE. This protocol,
to the best of our knowledge, is the first of its kind. Specifically, we
detailed how D2D communications can be supported over LTE network with minor
modifications to the standard procedures without any infrastructural changes.
We first adapted the WiFi Direct group formation procedure to support dynamic
cluster formation and LTE specific message exchange. Then, we introduced the
necessary signaling messages for cluster registration and bearer setup in LTE.
We showed that most of the required pieces are in place and we only need to
amend some of existing messages to support D2D clustering. Finally, we
discussed the impact of D2D clusters on LTE operations such as billing and
security. Our studies revealed that all native LTE operation work with D2D
clusters. Moreover, D2D clustering does not impose any security threat which
does not already exist in legacy LTE systems.

###  Chapter 5 Experimental Evaluation

####  5.1 Introduction

Analytical studies on D2D communications demonstrate very promising results,
but there is no experimental evidence that validates these results to date.
Moreover, the 3GPP study is mostly focused on the description of the
architecture and procedure for D2D communications. As of today, their proposed
architecture of ProSe remain unevaluated. The lack of experimental studies is
mostly due to tedious process of prototyping complex cellular architecture and
expensive equipments that are associated with it. Nevertheless, thanks to the
advent of SDR, the experimental studies for D2D communications are now made
possible. In this chapter, we elaborate on the development procedure of
outband D2D communications using a National Instrument’s SDR platform. Next,
we leverage this platform to answer questions such as: How is the cross-
platform (LTE to WiFi) communication? What is the delay and the computational
overhead? How large is the throughput gain in presence of real channel
dynamics?

####  5.2 SDR-based Testbed for Outband D2D Communications

In this section, we describe the hardware, the software, and the architecture
of our testbed. Our testbed design is utterly beneficial because it is based
on an SDR platform that uses Field Programmable Gate Array (FPGA) modules for
high-speed Digital Signal Processing (DSP) prototyping. Moreover, it exploits
the real-time controllers which ensures quick protocol prototyping. As today’s
cellular networks are moving toward functional virtualization and new
architecture, SDR platforms certainly stand out among the prototyping
alternative in today’s market.

#####  5.2.1 Software and Hardware

Hardware. The hardware used in this testbed is NI PXI 1082
chassis111http://sine.ni.com/nips/cds/view/p/lang/en/nid/207346 that contains:
$(i)$ NI PXIe 8135 Real-Time
controller222http://sine.ni.com/nips/cds/view/p/lang/en/nid/210545 operating
on an Intel Core-i7-3610QE CPU. This controller is used to execute LabVIEW
Real-Time which runs MAC layer algorithm and physical layer control
algorithms. LabVIEW Real-time communicates with the FPGA through dedicated
direct memory access FIFOs; $(ii)$ The Physical layer is programmed using
LabVIEW FPGA and runs on NI FlexRIO modules333http://www.ni.com/flexrio/ that
are equipped with Xilinx Kintex 7 or Virtex 5 FPGAs; $(iii)$ NI 5791 FlexRIO
Adaptor Module (FAM) is used as an RF transceiver operating with a $200$ MHz
bandwidth the in frequency range $200$ MHz to $4.4$ GHz. This is used for
Digital to Analog Conversion (DAC), Analog to Digital Conversion (ADC), up-
converting base-band to band-pass, and down-converting band-pass to base-band.
Figure 5.1 illustrates all these components.

Figure 5.1: Illustration of the hardwares used for the testbed.

Software. We found LabVIEW444http://www.ni.com/labview/ as a suitable tool to
prototype an outband D2D platform. On one hand, LabVIEW FPGA allows for quick
implementation of computationally intensive Physical layer (PHY) operations
(e.g., Fast Fourier Transform (FFT), inverse Fast Fourier Transform (iFFT),
encoding, and decoding) in Xilinx FPGA and meets the stringent nano-second
time scale requirement of the digital communication systems. Moreover, it
provides the necessary means for high speed communication with CPU and Radio
Frequency (RF) hardware. On the other hand, LabVIEW Real-Time is suitable for
implementing MAC layer operations with micro-second resolution. LabVIEW Real-
Time runs on a general purpose CPU and communicates with LabVIEW FPGA over
high-speed PCIe backplane.

#####  5.2.2 Architecture of eNB

The eNB consists of a Real-Time controller and a FlexRIO module used for Over
The Air (OTA) LTE transmission. Figure 5.2 shows the important blocks of the
eNB. Real-Time controller runs MAC layer services such as scheduling, D2D
services, and Transport Block (TB) generation for Control CHannel (CCH) and
shared channel Shared CHannel (SCH). FPGA executes PHY operations such as
convolutional coding, interleaving for CCH traffic and scrambling for SCH
traffic. Finally, the base-band signal is up-converted in the FAM module and
transmitted to the UE OTA. The current testbed only supports OFDMA in downlink
and the uplink transmissions is performed over ethernet. However, in future we
intend to extend this testbed to support OFDMA uplink transmission.

Figure 5.2: Architecture of the eNB.

#####  5.2.3 Architecture of UE

As eNB only requires one interface, UE’s architecture is thus more complex
since it comprises two interfaces: $(i)$ an LTE OFDMA downlink receiver for
communicating with the eNB; and $(ii)$ a WiFi transceiver to establish the
outband D2D link with other UEs.

OFDMA receiver. Following the design of the transmitter, the DSP operations
are implemented in the FPGA. Real-Time controller is only used for processing
the received payload and MAC layer D2D operations. These operations mainly
consist in filtering the relay packets and transmitting them to the WiFi
interface for relaying. Figure 5.3 shows the location of different logical
blocks in the system.

Figure 5.3: Architecture of UE’s LTE interface.

WiFi transceiver. The majority of the WiFi framework [158] is implemented in
FPGA. In addition, the transceiver is implemented within the same FPGA. We
implemented the D2D state-machine and its corresponding logic in the Real-Time
controller. The controller is also in charge of feeding data to the FPGA
transmission processing chain and reading the decoded data from FPGA reception
processing chain. Figure 5.4 shows the structure of the WiFi framework.

Figure 5.4: Architecture of UE’s WiFi interface.

Communication. We observe in Figure 5.5 that UEs receive downlink
transmissions over the OFDMA receiver and send the uplink messages over an
ethernet link. The WiFi (i.e., D2D) transmission uses an OFDM transceiver.

Figure 5.5: Architecture of the testbed.

#####  5.2.4 Shadow UEs

These non-SDR UEs (i.e., UE3, UE4, and UE5 in Figure 5.5) are off-the-shelf
android smartphones. We include the shadow UEs in our setup to better capture
the performance of outband D2D in a real-world scenario. We developed an
android application to obtain real-time cellular channel quality on a
millisecond basis. The application then transmits the channel quality values
to an access point, which is connected to the eNB over an ethernet link.
Although the shadows do not receive the actual transmission, the eNB schedules
them and transmits their data as if they were real UEs. Since the MCS-SNR
mapping is constructed to ensure block error rates below $10^{-4}$, we assume
that the shadows receive the transmitted blocks with success probability of
$0.9999$.

#####  5.2.5 Synthetic Fading

We measure the selected KPIs under different scheduling schemes. Due to the
limitation in the number of equipments in our disposal, we should run each
experiment at a separate time instant. In an ideal case, the system can be
connected to high-end multi-channel cellular channel emulators to create the
same channel variation in each experiment. Since we do not have such a device,
we decided to create a repeatable channel variation situation using
refractors.

In order to create repeatable channel variation patterns, we mounted the
refractors plates on a step motor that is controlled by an Arduino
Uno555http://www.arduino.cc/en/Main/ArduinoBoardUno micro-controller. We
generate synthetic channel variation by changing the rotation speed of the
step-motor. Figure 5.6 is the proof of concept of this mechanism. We repeated
an experiment four times and plotted the CDF of the potential MCS (obtained
from channel qualities) for both UEs to ensure stable repetitions of the
channel variation. Indeed, the results show that this approach is suitable to
re-create the same channel environment for different experiments. Note that
the location/frequency is selected such that unpredictable interference is
minimized.

Figure 5.6: CDF of MCS for UE1 and UE2 in each experiment.

####  5.3 Experimental Evaluation

In this section, we experimentally evaluate the performance of outband
D2D-relay and our proposed protocol. We design several experiments to better
demonstrate the system behavior in different scenarios. We first present the
performance of a simple outband D2D-relay setup. The simple setup is then
redesigned to first incorporate channel opportunism and then QoS-awareness. We
also examine the impact of non-collaborative UEs (i.e., shadow UEs). The
duration of each experiment is $300$ seconds, which is sufficiently long to
observe the average system’s performance. In order to provide the reader with
a detailed view of the achieved performance, we show minimum, maximum, 25th
and 75th percentiles in addition to the average values. Unless otherwise
specified, the rotation speed of the refractor is $5$ rpm. Finally, UE2
experiences higher average channel quality than UE1 in all experiments.

#####  5.3.1 Algorithm Implementation

We implement DORE, a channel-opportunistic framework for enhancing network
capacity under QoS constraints. DORE is based on the aforementioned channel
opportunistic design in previous chapters. In addition to channel opportunism,
we add delay consideration to our implemented algorithm for better QoS-
awareness. The delay consideration enables our proposed D2D scheme to serve a
much larger variety of application in particular those with tight delay
requirements. Algorithm 1 is the pseudocode of DORE. In the algorithm, we
first calculate the achievable throughput of the cellular link $T_{lte}^{(i)}$
and the D2D link $T_{d2d}^{(ij)}$. Then Merge and Split algorithm uses the
potential throughput information of the links (throughput is zero if the link
can not be established) for cluster formation. Next, the algorithm compares
the achieved delay $d^{(ij)}$ over the D2D link with the application specific
threshold $d_{th}^{(i)}$ to decide whether it should keep the D2D link active
($\alpha_{d2d}=1$) or it should fall back to cellular link ($\alpha_{d2d}=0$).
It should be noted that we do not use the game theory-based dynamic cluster
formation algorithm in our experimental evaluation because the testbed
consists of only two static UEs.

Algorithm 1 DORE

1:

2:$T_{lte}^{(i)},T_{d2d}^{(ij)},d^{(ij)},d_{th}^{(i)}\quad\forall
i,j\in\\{0,\dots,N\\}$.

3:$\alpha_{d2d}$

4:Initialize: $T_{lte}^{(i)}=T_{d2d}^{(ij)}=T_{gain}^{(ij)}=0$,
$d^{(ij)}=\infty$.

5:for k from 1 to N do

6: Compute the potential $T_{lte}^{(i)}$ and $T_{d2d}^{(ij)}$ based on the
received CSI.

7:end for

8:Merge & Split based on the estimated values for $T_{lte}^{(i)}$ and
$T_{d2d}^{(ij)}$.

9:if $d^{(ij)}\leq d_{th}^{(i)}$ then

10: Use D2D link ($\alpha_{d2d}=1$).

11:else

12: Use cellular link ($\alpha_{d2d}=0$).

13:end if

#####  5.3.2 Selected KPIs

We report several KPIs to examine different aspects of outband D2D-relay and
DORE. The KPIs described below are chosen based on their importance for
understanding the characteristics of a practical D2D system.

Throughput. Throughput is measured as the number of received bits per second.

Delay. We timestamp each packet at the eNB MAC and measure the delay at three
points within the path from the eNB to the D2D receiver. The delay from the
eNB MAC to the relay-UE MAC is referred to as LTE delay. The delay from the
relay’s LTE MAC to WiFi MAC is called the cross-platform delay. WiFi delay is
the time from the relay WiFi MAC to the D2D receiver WiFi MAC. The end-to-end
delay is the sum of all these delays. Note that the cross-platform delay is
affected by our implementation using multiple FPGA card for WiFi and LTE
interfaces.

CPU load. Since the Real-Time controller executes D2D related operations, we
can calculate the extra CPU load due to D2D operations by monitoring the Real-
Time module.

D2D lifetime. We examine our proposed design with slow and fast channel
variations. In each case, we measure the time during which a UE acts as relay,
which we call relay lifetime. This is an important factor in opportunistic D2D
because frequent role switching imposes extra load to the system.

Structural Similarity (SSIM) This is an index of similarity between two images
and it is known to be a better estimation of human eye perception in
comparison to other traditional methods such as peak SNR or mean squared
error. We use this metric for Quality of Experience (QoE) measurements in
video streaming experiments.

#####  5.3.3 Non-opportunistic Outband D2D Relay

We start with the simplest form of outband D2D-relay scenario with two UEs.
Despite the simplicity of this experiment, it provides answers regarding the
delay overhead due to multi-hop communication and achievable throughput gain.

Figure 5.7(a) compares a Legacy scheme (in which both UEs receive traffic only
from the eNB) with an Outband D2D-relay, in which UE1 acts as relay for UE2.
We observe that outband D2D increases the average end-to-end delay (i.e.,
Total in the figure) by $3.3$ ms as compared to the Legacy cellular system.
Looking at different delay components of outband D2D-relay, we can see that
cross-platform delay and WiFi delay are the major contributors to the delay
overhead. It is important to note that extra frame processing results in
higher LTE delays in outband relay mode. While commonly ignored in the
literature, this illustrates that relaying large volumes of traffic comes at a
cost. According to the observation from the delay profile, outband relay could
be potentially suitable for a large variety of non-mission critical
applications. Indeed, outband relay with a total delay of $6.3$ ms meets the
3GPP suggested delay budget of $70$ ms [145]. The motive for opportunistic
D2D-relay is vividly depicted in Figure 5.7(b). The figure shows that UE2
suffers from low channel quality while UE1 experiences a good channel
condition. After outband D2D activation, UE2’s throughput increases
significantly because it receives its traffic through a high channel quality
relay.

(a) Delay at different parts of the path.

(b) Per-UE throughput.

Figure 5.7: Outband UE-Relay: UE1 relays the traffic from the eNB to UE2.

#####  5.3.4 DORE with Delay-tolerant Traffic

Now, we evaluate the performance of opportunistic outband D2D using RR and PF
scheduling algorithms. We test DORE with delay-tolerant traffic to evaluate
the potential throughput gain for such use-cases. In the figures, we label the
legacy schemes as RR and PF. When used for DORE with delay-tolerant traffic,
they are labeled as RR-DT and PF-DT.

Figure 5.8(a) shows the achievable aggregate throughput of RR-DT and PF-DT is
$21$% and $11.2$% higher than RR and PF, respectively. As mentioned,
opportunistic outband D2D leverages the channel diversity between the D2D
users. Since PF harvests part of this opportunism due to its opportunistic
nature, the resulting gain reduces by $9.8$% in comparison to RR.
Nevertheless, the gain remains relevant for a two-user scenario where there
are limited opportunities. We show later in this section that the
opportunistic gain increases with the user population. Delay comparison in
Figure 5.8(b) demonstrates DORE causes higher delays. The additional delay
stems from WiFi and cross-platform transmission and LTE frame processing.

(a) Aggregate throughput.

(b) Delay

Figure 5.8: DORE: the relay UE is chosen according to reported CQI values.

#####  5.3.5 Impact of Fading Speed

(a) Impact of refractor speeds on D2D lifetime.

(b) Impact of threshold on D2D lifetime.

(c) Impact of switching thresholds.

Figure 5.9: Impact of fading speed on the lifetime of D2D UEs.

(a) Per-UE throughput.

(b) End to end delay for D2D UEs.

(c) CPU load.

Figure 5.10: System KPIs in an experiment with two D2D UEs and three shadow
users.

This experiment is designed to show the dynamics of DORE under different
fading scenarios. In particular, the change of role in the D2D connection
(i.e., a UE can be a relay or a D2D receiver). We refer to the period in which
a D2D UE acts as relay as the lifetime. In this experiment, we shed light on
the frequency of these changes and their impact on the system.

Figure 5.9(a) shows the CDF of the lifetime of UEs when the refractor surface
spins at $10$, $20$, $30$, and $40$ rpm. At these rotation speeds, the MCS of
a UE remains the same for $18.86$ ms, $15.38$ ms, $13.51$ ms, and $10.82$ ms,
on average. We can see that the duration of the lifetimes increases as the
fading speed reduces. The results also show that regardless of fading speed,
the lifetime is shorter than $250$ ms more than $50$% of the time. This
emphasizes on the fact that any implementation of opportunistic outband D2D
must be capable of handling the relay dynamics on a millisecond timescale.

In our implementation of DORE, a switch of D2D roles occurs as soon as the
achievable MCS of the D2D receiver becomes higher than the one of the relay
UE. In other words, the MCS difference threshold to switch roles is one MCS
index. Nevertheless, considering the resulting short lifetimes depicted in
Figure 5.9(a), we have decided to introduce and test hysteresis in the
switching to reduce frequent switching. Introducing higher switching threshold
can avoid role changes due to small MCS variations that do not vary much in
terms of bit efficiency. Thus, we increase the MCS difference that triggers
the role switching. Figure 5.9(b) shows that larger thresholds (Th in the
figure) increase lifetimes, as expected. However, this increment comes at the
cost of reduced throughput. Indeed, Figure 5.9(c) illustrates that the
throughput reduces up to $18$% when the switching threshold is $6$ MCS levels.
Our results indicate that small switching thresholds increase D2D lifetime
with limited throughput penalty. Therefore, it is not strictly necessary to
reconfigure D2D links upon any MCS change, which reduces the complexity of the
implementation.

#####  5.3.6 DORE in Presence of Shadows and Delay-tolerant Traffic

Here, we emulate the presence of additional legacy UEs using the shadow UEs
introduced in Section 5.2.4. The shadows do not collaborate in DORE but they
help us to test DORE in presence of non-collaborative UEs. The shadows send
real-time CQI reports to the eNB, and the eNB schedules traffic for them,
although they cannot decode such traffic.

Per-UE throughput results are presented in Figure 5.10(a). We can see that UE1
achieves a $53.2$% throughput gain with DORE (i.e., RR-DT and PF-DT) while UE2
only achieves a mere $1.4$% throughput gain. UE2 achieves lower gain due to
its higher average channel quality. We also reported the aggregate throughput
of each scheme in Figure 5.10(a), marked as Total. DORE results in $10.2$% and
$9$% throughput gain compared to RR and PF. The throughput gains are lower
than those achieved in the previous scenario ($\sim 20$%). This is because in
a scenario with $5$ UEs, the relay UE receives only a fraction of the total
available bandwidth (i.e., $2/5$ of the resources can be relayed if RR-DT is
used). As a result, the opportunistic scheme can only optimize that portion of
the cellular resources.

Figure 5.10(b) depicts the end-to-end delay. The delay behavior of the UEs is
very similar to the delay behaviors observed in Figure 5.7(a). Both UEs
experience additional delay under RR-DT and PF-DT w.r.t. RR and PF because of
the aforementioned cross-platform and WiFi delays. UE1 has a higher delay than
UE2 because it has lower channel quality than UE2 and it acts as the D2D
receiver most of the time. However, the increased delay is quite limited and
can be substantially reduced by using dedicated and integrated hardware rather
than different FPGA cards for LTE and WiFi interfaces.

Figure 5.10(c) compares the CPU load of the eNB and the UEs. The overhead on
the eNB is negligible. The two D2D-enabled UEs experience $4.42\%$ and
$4.45\%$ higher CPU load due to outband D2D operations in WiFi and LTE
interfaces. Note that running the WiFi code in the idle mode on the Real-Time
controller increases the total CPU load by about $3$%. Hence, the overhead due
to outband D2D is marginal.

#####  5.3.7 DORE in Presence of Shadows and Delay-sensitive Traffic

In this experiment, UE1 and UE2 host a real-time gaming application and a VOIP
call with $30$ ms and $80$ ms OTA delay threshold, respectively. To highlight
the impact of DORE’s QoS-awareness, we also show the performance figures when
the delay thresholds are set to infinity (i.e., DORE ignores the delay
constraints). In this scenario, we stressed the WiFi channel (i.e., D2D link)
by introducing extra non-D2D traffic to the network so that the WiFi channel
operates near to the congestion point. Therefore, small changes in the
instantaneous channel quality provoke non-negligible size queues.

Figure 5.11(a) shows the aggregate throughput of DORE with RR and PF but
without QoS constraints (RR-DT and PF-DT in the figure) and with tight
constraints (RR-DS and PF-DS). Both RR-DS and PF-DS achieve slightly lower
throughput ($3\%$) w.r.t RR-DT and PF-DT because the QoS-awareness of DORE
prevents opportunistic relay when delay constraints are violated. However, the
$3\%$ throughput loss is a small price to pay to maintain the QoS requirements
of the time-sensitive applications. Indeed, we observe in Figure 5.11(b) that
DORE can successfully cap the average delay below 30 ms and 80 ms. The
effectiveness of DORE is especially seen when it reduces the packet delay of
the voice traffic from $100$ ms to $23$ ms and $30$ ms. Since DORE delay
control mechanism relies on UE feedbacks, it cannot avoid the delay caused by
dramatic channel variations. As a result, the maximum delay under RR-DS and
PF-DS can be higher than the delay thresholds.

#####  5.3.8 QoE with DORE

Good QoS does not necessarily corresponds to good QoE. Thus, we design a video
streaming scenario using VLC666http://www.videolan.org/vlcto measure the QoE
in terms of SSIM. We use AviSynth to measure SSIM. Both PF and RR demonstrated
similar trend hence we only show the result for PF, for brevity. Again, we
show in Figure 5.12(a) the SSIM of the received video with $30$ ms delay
constraint (i.e., PF-DS) and with an infinite one (i.e., PF-DT). We repeat the
experiment for three different videos with 240p, 360p, and 480p resolutions.
The results indicate that the QoS awareness of DORE results in up to $26\%$
SSIM improvement. The SSIM values degrade with higher resolution videos
because they are more sensitive to channel impairments. We also demonstrate a
snapshot of the received video for 240p and 360p resolutions, in Figure
5.12(b). As expected, tight QoS constraints result in better image quality.

(a) Aggregate throughput.

(b) End to end delay.

Figure 5.11: Impact of QoS-awareness of DORE on system performance.

(a) SSIM between streamed videos.

(b) Snapshots of streamed video at the receiver.

Figure 5.12: QoE performance of DORE.

#####  5.3.9 Opportunistic Relay within Large Relay Groups

In the previous experiments, only two UEs were allowed to collaborate in DORE.
Our observation in Figure 5.10(a) showed that the impact of opportunistic
outband relay with only two users is limited. Since one-to-many communication
is also present in 3GPP ProSe services, we can increase the size of the
outband D2D group in order to achieve higher throughput. This experiment is
designed to illustrate the impact of larger D2D UEs groups. Here, all UEs
report their CQIs to the eNB and we only measure the throughput at the LTE
because the shadows are commercial smartphone, which are unable to decode the
messages of our experimental eNB. Figure 5.13 shows the aggregate system
throughput. Our results confirm that by enlarging the outband D2D group from
$2$ to $5$ UEs, the network throughput increases up to $71.8$%. The result is
critical to confirm the potentials of opportunistic D2D schemes. Indeed, we
are the first to assess the opportunistic gain with multiple UEs relaying
traffic among each other with a real implementation of an eNB scheduler and
real-time CQI acquisition from multiple UEs. The reported results are obtained
under PF scheduling. The achievable gains are even higher with RR, as shown in
prior subsections.

Figure 5.13: Aggregate throughput versus the number of UEs in the same
opportunistic outband D2D group.

####  5.4 Discussion

This chapter provides in-depth intuitions to understand the practicality of
integrating outband D2D communications in cellular networks. Here, we discuss
the feasibility of such integration in order to enlighten some key
requirements for developing an experimental setup as well as for designing
possible use-cases.

Feasibility. The SDR-based implementation of DORE is the proof-of-concept for
the feasibility of outband D2D schemes with more complex and dynamic scenarios
than non-opportunistic and QoS-unaware UE to UE communications.

Implementation. There are several challenging issues to solve for SDR
implementation of a D2D system. Here, we point out the most critical ones. The
relay UE experiences high computational overhead due to LTE frame processing.
Hence, we use label switching at LTE PDCP layer instead of IP routing which is
the current solution in 3GPP. During the course of DORE implementation, we
realized that D2D UEs switch role with high frequency (in order of
milliseconds). Thus, we place DORE at the eNB instead of ProSe Function/Server
to meet timing constraints and to avoid the additional overhead on the
backhaul links.

Choice of platform. To date, there are a few SDR platforms with ‘simultaneous’
LTE and WiFi capability, namely, Open Air Interface, and LabVIEW. We choose
LabVIEW for its modular and graphical programming structure that allows for
quick real-time and FPGA code development without stepping into complex low-
level programming languages. The choice of the NI PXI-based platform over USRP
is due to the real-time capability of the PXI system that speeds up MAC layer
algorithm prototyping and testing.

Capacity. DORE is key for boosting network capacity in one-to-many relay
scenarios. This result is very promising and it may suggest to increase the
size of the relay groups as much as possible. However, in virtue of our
observations on the extra load due to relay operations, it is plausible to
suggest that each relay group should not include more than a handful of users,
which is enough to enhance the network capacity by $70\%$.

QoS. QoS provisioning is a concern in outband D2D due to the use of unlicensed
spectrum. As a result, we designed DORE and the surrounding protocol with
necessary feedback and handlers to enable QoS monitoring in our testbed. The
experiments confirmed that DORE achieves the QoS requirements using a simple
monitoring and feedback scheme.

Use-cases. Our experimental evaluation showed that (opportunistic) outband D2D
schemes have low latency and ameliorate the throughput substantially. Hence,
these schemes suit a large variety of applications including voice calls,
video streaming, real-time gaming, and content sharing.

####  5.5 Summary

We prototyped the first SDR platform for outband D2D communications. We
leveraged Xilinx FPGAs and the NI Real-Time OS to develop realistic
experiments with LTE-like millisecond CQI reporting, scheduling, and high-
speed LTE- WiFi interaction. Our experimental evaluation using several QoS and
QoE metrics confirmed the feasibility and potentials of opportunistic outband
D2D communications. The results revealed that experimental performance figures
are lower than the reported values in the prior analytical studies, although
still notable (up to 20% with just two users). Nevertheless, high throughput
gains are achievable if the number of participating UEs in opportunistic
outband D2D increases (up to 71% with five users). Finally, we are in the
process of providing public access to our D2D SDR implementation so that the
research community can benefit from deeper study of such a system.

## D2D for Network Optimization

###  Chapter 6 D2D Mode Selection

####  6.1 Introduction

There have been extensive research efforts in both academia and industry to
explore D2D techniques [2]. D2D communications have been considered for a
large variety of use-cases such as cellular offloading [159], mobile relaying
[12], and video streaming [160]. These studies indicate the potential
outstanding gain of D2D communications in cellular networks. Indeed, the high
performance gain motivated leading telecommunication companies such as
Qualcomm to perform experimental studies on this paradigm using early stage
prototypes [4]. Standardization bodies such as 3GPP have also joined this
front by considering D2D communications as a public safety feature in the next
release of LTE-A [86]. These efforts from academia, industry, and
standardization bodies confirm that the society regards D2D communications as
a crucial feature for next generation networks. Nevertheless, there is still
no concrete agreement on D2D operational details such as which medium access
control to adopt, or which spectrum allocation schemes, connection setup, and
resource management protocols are to be implemented. As described in Chapter
2, initial proposals for D2D communications aimed at re-using the same
resources that are used for conventional cellular communications (i.e., inband
underlay D2D mode) [74]. The significance of the D2D gain had led to proposals
in which a part of the cellular resources is dedicated only to D2D
communications (i.e., inband overlay D2D mode). Finally, the scarcity and the
high price of cellular spectrum motivated some researchers to explore D2D
communications over the unlicensed band (i.e., outband D2D mode). The use of
resources with these D2D modes is illustrated schematically in Figure 6.1.

Figure 6.1: Schematic representation of overlay inband, underlay inband, and
outband D2D for cellular scenarios.

The majority of the existing studies on D2D communications select one of the
aforementioned modes, then propose a method for resource
allocation/interference management in order to handle the resulting
complications, and finally illustrate the achievable performance improvement
[109, 12, 74, 79, 159]. However, single mode D2D significantly limits the
system performance to the interference profile of the network. Existing multi-
mode D2D systems only focus on inband D2D modes, i.e., fully dependent on
cellular spectrum. Other proposals focus on joint scheduling and mode
selection [108, 161], although they are extremely complex (more complex than
scheduling, which is already proven to be NP-hard for cellular systems such as
LTE [162]) and introduce unnecessarily frequent mode selection decisions.

Interestingly, while some researchers limit D2D communications to cellular
spectrum, the standards have a more liberal view of D2D. In fact, 3GPP defines
D2D as “the communication between two users in proximity using a direct link
between the devices without traversing the eNB(s) or the core network” [86].
We also remark that network-assisted outband D2D is accounted for in 3GPP
ProSe [7]. Although both inband and outband D2D are considered valid options
for ProSe services, there is no indication on how to select between the two.
Hence, given the fast-track emergence of D2D communications in cellular
networks, the need for an adaptive D2D mode selection scheme is beyond
question.

In this chapter, we propose a flexible framework to adaptively select D2D mode
or operating band and technology. In particular, we first discuss the
practical implications of each D2D mode based on the latest standard releases
of LTE-A and WiFi-Direct. This discussion clarifies that there is no superior
D2D mode and the potential of each mode is highly scenario/use-case dependent.
After discussing practical implementation issues of D2D-enabled networks, we
provide analytical insights into the mode selection problem in an innovative
multi-mode multi-band setup, which accounts for both achieved throughput and
energy costs. We call such a novel approach Floating Band D2D, because D2D
transmissions can occur on either inband or outband modes. The problem is
formulated as a non-linear integer programming problem. Given the NP-hardness
of the problem and time-stringent requirements of future cellular networks,
e.g., 5G networks, we propose three practical heuristics with near-optimal
performance and low complexity. Finally, we evaluate the performance of the
proposed heuristics in a multi-cell scenario using a realistic setup designed
based on the ITU-R guidelines for evaluating IMT-Advanced networks [163]. Our
results confirm that the coexistence of D2D modes ameliorates the performance
of the system in terms of the key performance factors such as throughput and
utility (up to one order of magnitude), and near complete fairness.

####  6.2 Pros and Cons of D2D Modes

As mentioned, 3GPP’s definition does not restrain D2D implementations to a
specific technology or spectrum. To date, the available commercialized
technologies that suit D2D communications are either in the family of 3GPP
standards such as LTE-A or in the family of IEEE standards such as WiFi. The
former are suitable candidates for inband D2D and the latter match the
requirements of outband D2D. Indeed, the feasibility of D2D communications
with the aforementioned technologies has recently been theoretically proven
not only by us in [11] but also by other independent studies [164].

We refer to users that communicate with the eNB as cellular users and to those
who communicate with other neighboring users as D2D users. The following
describes the list of D2D modes available are _Underlay inband_ , _Overlay
inband_ , and _Outband_. Note that inband D2D users are allowed to share the
same resource (i.e., simultaneously transmit over the same frequency), while
outband D2D users adopt a WiFi MAC and contend for channel access. The
differences among available D2D modes pose advantages and disadvantages for
each mode, as summarized in Table 6.1. For completeness, we also include
legacy cellular communication in the table. Interestingly, none of the
available D2D modes can simultaneously guarantee features like controlled
interference, spectrum efficiency, and QoS. So, when it comes to electing a
specific mode for implementing D2D in a network, there is no clear winner.

Table 6.1: Pros and cons of each D2D mode |  Underlay |  Overlay |  WiFi | Cellular
---|---|---|---|---
Interference between D2D and cellular users | $\checkmark$ | $\times$ | $\times$ | $\times$
Interference among D2D users | $\checkmark$ | $\checkmark$ | $\times$ | $\times$
Needs dedicated resources for D2D users | $\times$ | $\checkmark$ | $\times$ | $\times$
Controlled interference environment | $\checkmark$ | $\checkmark$ | $\times$ | $\checkmark$
Simultaneous D2D and cellular transmission | $\times$ | $\times$ | $\checkmark$ | $\times$
Increased spectral efficiency | $\checkmark$ | $\checkmark$ | $\checkmark$ | $\times$
Requires additional wireless interface | $\times$ | $\times$ | $\checkmark$ | $\times$
QoS guarantee | $\checkmark$ | $\checkmark$ | $\times$ | $\checkmark$
Energy cost | Eq.(6.3) | Eq.(6.3) | Eq.(6.5) | Eq.(6.2)

Looking at the pros and cons of the available D2D modes, one can observe that
none of the available D2D modes is ideal. So the question remains: Which D2D
mode is the best? Let us look at a few examples to better address this
question. The use of underlay in micro cell scenarios, where users are in
short range, results in intolerable co-channel interference to cellular users.
In such scenarios, overlay and outband modes better facilitate D2D
communications. On the other hand, using overlay in a macro cell with many
cellular users can result in underutilization of network resources if the
number of D2D users is small. Here, underlay and outband potentially perform
better because of the sufficient distance among users. Finally, places with
high occupancy of unlicensed band are not suitable for outband mode, due to
well known congestion problems of contention-based MAC protocols.

One can observe that an eNB may face the above-mentioned scenarios on a daily
basis, e.g. as different groups of users (workers/students, residents,
shoppers, etc.) become dominant at particular times of the day. Thus, an
adaptive scenario-independent D2D-enabled system cannot be tied to a specific
mode or band. Indeed, we propose a multi-band mode selection scheme in order
to facilitate such high level of adaptiveness in real implementations.

####  6.3 System Model

In this section, we describe our reference system, our proposed mode selection
approach, and its practical implications.

#####  6.3.1 System

We consider a hexagonal multi-cell LTE-A network with a reference cell in the
center and its first-tier neighbors as shown in Figure 6.2. The cell consists
of $N$ users labelled as $n\in\mathcal{N}:=\\{1,2,\dots,N\\}$. Downlink and
uplink channels are separated and each one has a fixed bandwidth. Users may
communicate with other users in the cell or with those outside the cell. If a
user wants to communicate with another user in her proximity, she can use D2D
communications. Inband D2D communications use uplink cellular spectrum [86].
It is assumed that each user communicates with (at most) one user at any given
time. Each connection between users $n$ and $m$ is referred to as $(n,m)$,
$\forall n,m\in\mathcal{N}$. For notational convenience, the eNB is addressed
as user $N+1$. Here, we assume that the outband D2D exploits WiFi Direct
technology. With the above, we use four communication modes operating:

  * •

Mode $0$ $\leftrightarrow$ cellular;

  * •

Mode $1$ $\leftrightarrow$ inband underlay D2D;

  * •

Mode $2$ $\leftrightarrow$ inband overlay D2D;

  * •

Mode $3$ $\leftrightarrow$ outband D2D (WiFi).

Our system operates in discrete time units and the eNB is in charge of mode
selection and scheduling. The eNB makes the scheduling decisions on a per-
frame basis. Each frame consists of $s$ subframes. In each subframe, only one
cellular user is scheduled, while the number of concurrent D2D transmissions
is not limited a priori. Therefore, there is no interference among cellular
users (i.e., mode $0$), but underlay users (i.e., mode $1$) interfere with the
cellular and other underlay users (i.e., modes $0$ and $1$). Overlay users
only interfere with each other, while outband D2D users simply contend for the
WiFi channel. A fixed portion of cellular bandwidth is dedicated to overlay
D2D users. This portion is released to cellular and underlay users if there is
no user in overlay mode.

Figure 6.2: Our system model that consists of a cell with its first-tier
neighbors.

#####  6.3.2 Mode Selection and Scheduling

As mentioned, mode selection and scheduling decisions by nature require
decision making schemes with a different time-scale resolution. Thus, we
propose to decouple the mode selection and scheduling problems. The decoupling
is mainly inspired by the fact that D2D connections last more than a few
frames in a real world scenario and scheduling them on a per-frame basis is
unnecessary and possibly inefficient. The inefficiency is due to the high
signaling overhead, which is caused by such a high resolution mode selection
(see Subsection 6.3.3). Moreover, the channel quality of D2D links is
potentially less time variant in comparison to that of the cellular links due
to the short-range nature of D2D communications. The decoupling also
simplifies the integration of D2D communications into current cellular systems
as it minimizes the changes to the scheduler. Although mode selection and
scheduling are decoupled, they are still highly intertwined. On one hand, the
scheduling is affected by the interference, which is unknown before mode
selection. On the other hand, mode selection depends on the set of cellular
users scheduled along with D2D users. Hence, we choose the eNB to perform mode
selection, because it is already in charge of scheduling.

We propose a mechanism in which the eNB handles these decisions in two steps:
$(i)$  _mode selection_ and $(ii)$  _scheduling_. First, in mode selection,
each D2D pair is assigned a mode (modes $1$ to $3$), and the assignment is
repeated at regular mode intervals of length $T$ seconds. The eNB selects D2D
modes with the assumption of a worst-case interference scenario. This approach
helps to reduce the system complexity and to avoid disruptive co-channel
interference. Second, in the scheduling phase, the eNB schedules users and
assigns them a Modulation and Coding Scheme (MCS). Mode selection and
scheduling both rely on the accuracy of CSI data gathered at the eNB, which
can be challenging in terms of signaling overhead and scheduling.

#####  6.3.3 Practical Implications

In a D2D-enabled network, the eNB requires CSI between each pair of users
(i.e., user-to-user CSI) in addition to user-to-eNB CSI in order to perform
MCS assignment and scheduling. However, the existing cellular technologies do
not have the means to obtain user-to-user CSI. Hence, we need a mechanism to
obtain and send this information to the eNB efficiently because the addition
of user-to-user CSI imposes high signaling overhead to the system.

CSI measurement. In LTE, the eNB-to-user CSI is estimated by active
measurements from the received signal strength. However, there is no signaling
message exchange between the users. Therefore, some researchers propose
probing techniques to perform CSI estimation among users [108]. This approach
imposes even higher signaling overhead to the system. In contrast, we propose
an adaptive passive CSI estimation between users as explained in what follows.
In LTE, each user has a unique ID (i.e., C-RNTI [165]) and this ID is included
in the frame header. Thus, the users can detect the ID of the source of
interference at each frame. Alternatively, the user can read C-RNTIs from the
broadcasted scheduling map to identify the interfering user’s ID. The latter
does not require users to sniff and decode other users’ frame headers. The CSI
is then reported to the eNB. The eNB builds an interference table, whose
elements $I_{n,m}\\!\geq\\!0$ represent the interference caused by user $n$ to
user $m$ $\left(\forall
n,m\\!\in\\!\mathcal{N}\\!\cup\\!\\{\\!N\\!+\\!1\\!\\}\right)$. In case two
users do not detect each other for physical/timing reasons, the failure only
causes an interruption on a millisecond scale. Once an interruption occurs,
the user will report it to the eNB which will update the interference matrix.
As for outband D2D, each user reports the last achieved rate over WiFi. In
case of an inaccurate report due to long inactivity period, the users can send
an updated report before the next mode interval.

Signaling overhead. The maximum number of CSI reports in LTE-A (with wideband
CSI reporting [165]) is equal to $N$. This number increases to
$N+2|\mathcal{N}_{d}||\mathcal{N}_{c}|+|\mathcal{N}_{d}|\left(|\mathcal{N}_{d}|-1\right)$
in a D2D-enabled network, where $\mathcal{N}_{c}$ and $\mathcal{N}_{d}$ are
the sets of cellular and D2D users, respectively. For instance, a D2D-enabled
network with $4$ cellular and $6$ D2D users may require up to $88$ CSI
reports, which is almost $9$ times higher than its equivalent in a legacy
system. Fortunately, the CSI feedbacks can be considerably reduced using the
state-of-the-art feedback reduction techniques [166]. Moreover, we will see in
Section 6.6 that the D2D signaling overhead is negligible as compared to the
resulting gain. This overhead is further reduced by our proposal because we
decouple scheduling from mode selection, hence the D2D related CSIs are
obtained less frequently.

####  6.4 Floating Band D2D Framework

In this section we describe our proposed Floating Band D2D framework and
formulate the problem of mode selection at the beginning of each mode interval
$j$, i.e., each $T$ seconds. The utility function in our problem formulation
depends on throughput and energy costs, for which we provide a general model
in which specific schedulers can be plugged in. Note that, although the
general model can be used with specific schedulers to evaluate the performance
of various strategies, the formulation of the problem does not depend on the
scheduler actually implemented, and is not affected by resource allocation
strategies for either cellular or D2D connections.

Throughput and energy costs. The transmitted data $\theta^{i}_{n,m}(j)$ for a
connection $(n,m)$ in mode $i\in\\{0,1,2\\}$ during mode interval $j$ is
formulated as follows:

$\displaystyle\theta^{i}_{n,m}(j)$
$\displaystyle=B^{i}_{n,m}(j)R^{i,\text{CSI}}_{n,m}(j),$ (6.1)

where $B^{i}_{n,m}(j)$ is the number of Resource Blocks (RBs) allocated to
connection $(n,m)$ in mode interval $j$. $R^{i,\text{CSI}}_{n,m}(j)$ is the
number of transmitted bits per RB of connection $(n,m)$ in mode $i$ during
mode interval $j$, computed based on the channel gain between users $n$ and
$m$, and the interference matrix $\bf I$.

The energy consumption of a cellular user $E^{0}_{n,m}(j)$ and the energy
consumption of a D2D pair $E^{i}_{n,m}(j)$ in inband mode $i\in\\{1,2\\}$ are
given by:

$\displaystyle E^{0}_{n,m}(j)$
$\displaystyle=\beta_{lte}+p^{0,\text{TX}}_{n}\cdot t_{B^{0}_{n,m}}(j)\qquad
m=N+1,$ (6.2) $\displaystyle E^{i}_{n,m}(j)$
$\displaystyle=2\left(\beta_{lte}+\beta^{\texttt{WiFi}}_{idle}\right)+\left(p^{i,\text{TX}}_{n}+p^{i,\text{RX}}_{m}\right)t_{B^{i}_{n,m}}(j),$
(6.3)

where $\beta_{lte}$ and $\beta^{\texttt{WiFi}}_{idle}$ are the baseline energy
consumed in a mode interval by an active cellular interface and an idle WiFi
interface, respectively. The WiFi interface is kept idle in inband modes to
speed up WiFi connection setup. Here, $p^{i,\text{TX}}_{n}$ and
$p^{i,\text{RX}}_{m}$ are the energy consumed for transmission and reception
in one subframe, respectively. $t_{B^{i}_{n,m}}(j)$ is the transmission time
associated with $B^{i}_{n,m}(j)$. Here, we do not calculate the energy per RB,
because it is shown that the transmission/reception power mainly depends on
time rather than bandwidth [167].

The expression of transmitted data $\theta^{3}_{n,m}(j)$ and the energy
consumption $E^{3}_{n,m}(j)$ for connection $(n,m)$ under outband mode (i.e.,
mode $3$) in mode interval $j$ is as follows:

$\displaystyle\theta^{3}_{n,m}(j)$ $\displaystyle=T\cdot
R^{3,\text{CSI}}_{n,m}(j),$ (6.4) $\displaystyle E^{3}_{n,m}(j)$
$\displaystyle=2(\beta_{lte}+\beta^{\texttt{WiFi}}_{active})+\left(p^{3,\text{TX}}_{n}+p^{3,\text{RX}}_{m}\right)\theta^{3}_{n,m}(j),$
(6.5)

where $R^{3,\text{CSI}}_{n,m}$ is the WiFi rate and
$\beta^{\texttt{WiFi}}_{active}$ is the baseline WiFi energy consumed by a
user in a mode interval. $p^{3,\text{TX}}_{n}$ and $p^{3,\text{RX}}_{m}$ are
the energy consumed by user $m$ per transmitted/received bit. Note that the
energy consumption as defined here can incorporate both the consumption due to
transmission/reception and packet processing (see [12]). The $\beta_{lte}$ is
due to the dependence of outband users to the eNB signaling.

We define a utility function for connection $(n,m)$ under mode $i$ in mode
interval $j$ as follows:

$U_{n,m}^{i}(j)=\theta^{i}_{n,m}(j)-\alpha E^{i}_{n,m}(j),$ (6.6)

where $\alpha$ is the relative cost of energy. The utility accounts for both
throughput and energy consumption. The value of $\alpha$ determines whether
the system is biased towards higher throughput or lower energy consumption. In
our model, the impact of schedulers is summarized in $B^{i}_{n,m}$ and
$t_{B^{i}_{n,m}}$. Those parameters have to be computed in each mode interval
and for each possible mode selection decision.

Problem Formulation. Let $\mathcal{L}(j)$ be the set of all existing
connections during mode interval, $j$, $\\{Y^{i}_{n,m}(j)\\}$ be the set of
binary decision variables, and $\gamma_{n}$ be the tolerable interference
threshold that allows for a non-zero reception rate by user $n$. We formulate
the problem of mode selection for mode interval $j$ as a binary programming
problem (the dependency on $j$ is omitted for readability):

$\displaystyle\\!\\!\\!\\!\\!\begin{cases}\max\\!\\!&U_{sum}:=\sum_{i=0}^{3}\sum_{(n,m)\in\mathcal{L}}U_{n,m}^{i}Y_{n,m}^{i}\quad\\!\\!\\!\\!\forall(n,m)\in\mathcal{L}\\!\\!\\!\\!\\\
\text{s.t.}&\\!\\!\\!\\!\\!\\!\\!\sum_{i=0}^{3}\sum_{n|(n,m)\in\mathcal{L}}Y_{n,m}^{i}\leq
1\quad\forall m\in\mathcal{N}\\\
&\\!\\!\\!\\!\\!\\!\\!\sum_{i=0}^{3}\sum_{m|(n,m)\in\mathcal{L}}Y_{n,m}^{i}\leq
1\quad\forall n\in\mathcal{N}\\\
&\\!\\!\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}(n,m)\in\mathcal{L}\end{subarray}}Y_{n,m}^{1}I_{n,x}\leq\gamma_{x}\quad\forall
x\in\mathcal{N}_{c}\cup\\{N+1\\}\\\
&\\!\\!\\!\\!\\!\\!\\!\sum_{i\in\\{0,1\\}}\sum_{(x,y)\in\mathcal{L}\setminus\\{(n,m)\\}}Y_{x,y}^{i}Y_{n,m}^{1}I_{x,m}\leq\gamma_{m}\\\
&\\!\\!\\!\\!\\!\\!\\!\sum_{(x,y)\in\mathcal{L}\setminus\\{(n,m)\\}}Y_{x,y}^{2}Y_{n,m}^{2}I_{x,m}\leq\gamma_{m}\quad\\!\\!\\!\forall(n,m)\\!\in\\!\mathcal{L}\\!\\!\\!\\!\end{cases}$
(6.7)

Problem (6.7) maximizes the sum of utilities $U_{sum}$ over all possible
combinations of users and modes. Our assumption on single instantaneous
connectivity is enforced with the first and second constraints (the eNB, which
is labeled as $N+1$, is an exception). The third constraint ensures that the
co-channel interference from underlay users to cellular users and to the eNB
is kept below the threshold. The fourth constraint limits the interference
from cellular and inband underlay users to other inband underlay users. The
interference of overlay transmissions is limited by the fifth constraint.

Complexity. Problem (6.7) is NP-hard and non-linear since it can be reduced to
the longest path problem (e.g., for a weighted directed and possibly
disconnected graph), which is NP-hard [168]. This reduction is obtained when
we consider Problem (6.7) for a single mode $i=3$ (outband), in which the
objective is to activate D2D pairs so as to achieve the maximum utility
possible with the two restrictions on at most one incoming and at most one
outgoing transmission for every user. Problem (6.7) requires the computation
of $\\{U_{n,m}^{i}\\}$, which is based on SINR and its optimal solution can be
achieved by brute force: exploring the consequences of assigning modes $1$,
$2$, or $3$ to any of the $\frac{|\mathcal{N}_{d}|}{2}$ D2D pairs. Hence, the
resulting complexity is $O(N\cdot 3^{\frac{|\mathcal{N}_{d}|}{2}})$, which
grows exponentially with the number of D2D pairs. The optimal solution to the
above maximization problem is computationally expensive and practically
unfeasible in dense networks. However, the non-linear constraints can be
linearized so that the problem can be solved relatively efficiently by
standard approaches, such as Branch & Bound [169]. Nevertheless, we deem such
an approach impractical as the system requires a solution in milliseconds.
Thereby, we propose efficient heuristics in what follows.

####  6.5 Heuristics

The exact solution to Problem (6.7) is computationally expensive and does not
allow for a fast and scalable mode selection. Given the similarity of the
problem to the longest path problem and the knapsack problem, we propose three
practical heuristics. These heuristics explore the achievable utilities of the
users in an iterative manner. Note that these utilities are computed assuming
that the system is fully utilized (i.e., users’ queues are fully backlogged)
so that they do not require the knowledge of the actual user’s offered load.

Algorithm 2 Social

1:

2:$\mathcal{N}_{d,\text{TX}}$: set of D2D transmitters (randomized order).

3:$I_{n,x}$: interference between each pair of users.

4:$Y_{(n,m)}^{i},\forall n\in\mathcal{N}_{d,\text{TX}}$

5:initialize: ${\bf Y}\\!=\\!{\bf Y}_{old}\\!=\\!\emptyset$;
$Y_{(c,N+1)}^{0}\\!=\\!1,\forall c\\!\in\\!\mathcal{N}_{c}$;
$Y_{(n,m)}^{3}\\!=\\!1,\forall n\\!\in\\!\mathcal{N}_{d,\text{TX}}$;
$\text{max}=U_{sum}$

6:while ${\bf Y}\neq{\bf Y}_{old}$ do

7: ${\bf Y}_{old}={\bf Y}$

8: for $n\in\mathcal{N}_{d,\text{TX}}$ do

9: for $j\in\\{1,2,3\\}$ do

10: Calculate: $U_{sum}|n\text{ is in mode }j$

11: if $U_{sum}>\text{max}$ then

12: $\text{max}=U_{sum}$

13: $Y_{(n,m)}^{j}=1$; $Y_{(n,m)}^{k}=0,k\in\\{1,2,3\\}\setminus\\{j\\}$

14: end if

15: end for

16: end for

17:end while

#####  6.5.1 Heuristic 1. Social

The eNB iterates over the set of D2D transmitters $\mathcal{N}_{d,TX}$, and it
selects the mode that maximizes the aggregate utility (lines $7$-$13$ in
Algorithm 2). Note that the mode for user $i$ is selected based on the modes
selected for the precedent users. Initially, all D2D pairs are assigned to
mode $3$ (outband), to minimize the impact on cellular users. For better
fairness [4], the order of users in $\mathcal{N}_{d,TX}$ is randomized at any
mode interval. The mode selection repeats until the algorithm converges to a
decision. We name this heuristic as Social because it decides based on social
welfare. Since the utility of Social cannot decrease with mode selection
decisions, the heuristic always converges.

#####  6.5.2 Heuristic 2. Greedy

The Greedy heuristic is similar to Social. Unlike Social, Greedy selects the
mode which maximizes the user’s individual utility (line $10$ in Algorithm 3).
The drawback of Greedy is that it might not converge. However, we can index
each decision since the algorithm is running in the eNB. Once a duplicate
index (stored in $\mathcal{D}$) is found, the algorithm stops the iteration.

Algorithm 3 Greedy

1:

2:$\mathcal{N}_{d,\text{TX}}$: set of D2D transmitters (randomized order).

3:$I_{n,x}$: interference between each pair of users.

4:$Y_{(n,m)}^{i},\forall n\in\mathcal{N}_{d,\text{TX}}$

5:initialize: ${\bf Y}=\emptyset$; $Y_{(c,N+1)}^{0}=1,\forall
c\\!\in\\!\mathcal{N}_{c}$; $Y_{(n,m)}^{3}=1,\forall
n\\!\in\\!\mathcal{N}_{d,\text{TX}}$; $\text{max}_{i}=U_{(i,m)}$;
$exit\\!=\\!False,\mathcal{D}=\emptyset$

6:while $exit=False$ do

7: for $i\in\mathcal{N}_{d,\text{TX}}$ do

8: for $j\in\\{1,2,3\\}$ do

9: Calculate: $U_{(i,m)}^{j}|i\text{ is in mode }j$

10: if $U_{(i,m)}^{j}>\text{max}_{i}$ then

11: $\text{max}_{i}=U_{(i,m)}^{j}$

12: $Y_{(i,m)}^{j}=1$; $Y_{(i,m)}^{k}=0,k\in\\{1,2,3\\}\setminus\\{j\\}$

13: end if

14: end for

15: end for

16: $dec$ = Index of current $\bf Y$

17: if $dec\in\mathcal{D}$ then

18: exit = True

19: end if

20: Add $dec$ to $\mathcal{D}$

21:end while

#####  6.5.3 Heuristic 3. Ranked

Both Social and Greedy operate on a list of D2D transmitters with a randomized
order. In contrast, Ranked heuristic sorts this list based on the achievable
utility of each user without considering the impact of other users (PHASE 1).
In PHASE 2, the pre-ordered list $\mathcal{N}_{d,\text{TX}}^{(\text{ranked})}$
is evaluated using Greedy, which makes the heuristic greedier than Greedy.
This helps to evaluate the ability of our approach to withstand unfair
conditions. Algorithm 4 illustrates the pseudocode of the heuristic.

Algorithm 4 Ranked

1:

2:$\mathcal{N}_{d,\text{TX}}$: set of D2D transmitters (randomized order).

3:$I_{n,x}$: interference between each pair of users.

4:$Y_{(n,m)}^{i}$

5:initialize: ${\bf Y}=\emptyset$; $Y_{(c,N+1)}^{0}=1,\forall
c\in\mathcal{N}_{c}$; $Y_{(n,m)}^{3}=1,\forall n\in\mathcal{N}_{d,\text{TX}}$

6:

7:PHASE 1: Sorting D2D pairs based on their utility

8:

9:for $i\in\mathcal{N}_{d,\text{TX}}$ do

10: for $j\in\\{1,2,3\\}$ do

11: Calculate $U_{(i,m)}^{j}$

12: end for

13: $\text{mode}_{i}=\arg\max\\{U_{(i,m)}^{j};j\in\\{1,2,3\\}\\}$

14:end for

15:sort the $\mathcal{N}_{d,\text{TX}}$ based on utilities
$U_{(i,m)}^{\text{mode}_{i}}$ & store in
$\mathcal{N}_{d,\text{TX}}^{(\text{ranked})}$.

16:

17:PHASE 2: Executing Greedy heuristic

18:

19:Do Greedy with
$\mathcal{N}_{d,\text{TX}}=\mathcal{N}_{d,\text{TX}}^{(\text{ranked})}$.

#####  6.5.4 Complexity Analysis

Our proposed heuristics compute $N-|\mathcal{N}_{d,\text{TX}}|$ utilities
$\\{U_{n,m}^{i}\\}$ for each mode and for every D2D transmitter in a
sequential manner, i.e.,
$3\left(N|\mathcal{N}_{d,\text{TX}}|-|\mathcal{N}_{d,\text{TX}}|^{2}\right)$
utilities per round of evaluation. In each mode interval, the evaluation cycle
is repeated $r_{i}$ times, $r_{i}\geq 1$, until the algorithm converges to a
decision. Therefore, the complexity of Social and Greedy is
$O\left(3r_{i}N|\mathcal{N}_{d,\text{TX}}|\right)$, $i\in\\{1,2\\}$. Ranked
has an additional sorting procedure before the mode selection in which the
utility of each D2D pair is computed in isolation. Thus, the algorithm only
needs to compute $3|\mathcal{N}_{d,\text{TX}}|$ utilities in PHASE 1, which
can be neglected with respect to the number of utilities to be computed in
PHASE 2. Hence, the complexity of Ranked is
$O\left(3r_{3}N|\mathcal{N}_{d,\text{TX}}|\right)$. Therefore, the three
proposed heuristics have the same complexity, except for a constant factor
$r_{i}$ that we will quantify experimentally later.

####  6.6 Evaluation

In this section, we use numerical simulations to evaluate the performance of
our proposed heuristics. The evaluation scenario consists of a hexagonal
multi-cell network with a reference cell in the middle and its first-tier
neighbors (see Figure 6.2). The results reported in this chapter pertain to
the reference cell, and the neighboring cells model the impact of inter-cell
interference. Error bars in the results are the $95\%$ confidence intervals.
Although our approach can be tested with any scheduler, here we refer to the
Proportional Fair (PF) scheme for scheduling cellular users, since it
represents the state of the art for schedulers used in real implementations
[162, 170]. In addition to our heuristics, we evaluate three benchmark
schemes, namely, Forced-LTE, Forced-WiFi, and Optimal. In Forced-LTE, D2D
users are forced to use legacy cellular communications (i.e., mode $0$). In
Forced-WiFi, D2D users are forced to communicate over WiFi (i.e., mode $3$).
Optimal results are based on the exact solution to Problem (6.7) obtained by
brute force. The benchmarks allow to compare our proposals with the legacy
cellular system, to measure the gain due to extra WiFi bandwidth, and to see
how far the heuristics are from the optimum.

#####  6.6.1 Simulation Setup

User placement follows the uniform distribution. The number of D2D users is on
average $30\%$ of the cell population. The simulation parameters are chosen
according to the evaluation guidelines of ITU-R [163] which are reported in
Table 6.2. In the simulation, we show both the _packet simulation results_
(i.e., performance under finite offered load and in the presence of
probabilistic arrival processes) and the _achievable performance_ (i.e.,
performance at capacity-level utilization, under infinite offered load
conditions). In the later, the transmission queues of the users are always
fully backlogged. Unless otherwise specified, the default values for $\alpha$
and overlay resource portion are those reported in Table 6.2, with an
aggregate D2D and cellular load of $30$ Mbps and $90$ Mbps, respectively.
Since the D2D capacity is higher than the cellular one, due to proximity of
D2D users and availability of outband resources, we deemed fair to impose
higher load to D2D users. Note that the default value of $\alpha$ is selected
based on a rough estimate of the current relative price of bit per Joule (b/J)
in the market.

Besides the values of Table 6.2, we investigate the impact of user density
$N$, overlay resource portion, relative cost of energy $\alpha$, and D2D load
on the system performance. Moreover, we shed light on the convergence time of
our heuristics and their flexibility in different environments.

Table 6.2: The parameters used in the evaluation Parameter | Value
---|---
Cellular
Cellular uplink bandwidth | 20 MHz
Cell radius | 250 m
eNB, cellular user TX power | 44 dBm, 24 dBm
Thermal noise power | -174 dBm/Hz
Mode interval length $T$ | 2 s
Fading, shadowing, pathloss | Reyleigh, 6 dB, UMa [163]
Buffer size | 500 packets
$\beta_{lte}$ | 1288.04 mW
WiFi
WiFi bandwidth | 22 MHz
WiFi effective range | 150 m
WiFi TX power | 20 dBm
$\beta^{\texttt{WiFi}}_{active}$, $\beta^{\texttt{WiFi}}_{idle}$ | 132.86 mW, 77.2 mW
D2D
Underlay max bandwidth | 20 MHz
Overlay resource portion | 30%
D2D maximum distance | 20 m
D2D inband TX power | 10 dBm
Relative cost of energy $\alpha$ | 1 bit/Joule

#####  6.6.2 Simulation Results

(a) Aggregate cell throughput.

(b) Aggregate cell power.

(c) Aggregate cell Utility.

Figure 6.3: The impact of user population on the system performance with fully
backlogged queues (achievable performance).

(a) Fairness among cellular users.

(b) Fairness among D2D users.

(c) Aggregate cell Utility.

Figure 6.4: The impact of user population on the system performance evaluated
through packet simulation.

Impact of the number of users $N$. Figure 6.3 illustrates the impact of $N$ on
achievable system performance. We can observe the achievable throughput in
Figure 6.3(a). The aggregate throughput has a negligible change with $N$ under
Forced-LTE because the distribution of channel qualities in the cell remains
the same for different density of users, and therefore the average aggregated
throughput. The throughput of the rest of schemes increases with $N$ because
there are probabilistically more D2D pairs in a denser cell, hence D2D
throughput is higher. In Forced-WiFi, the throughput grows slowly due to the
contention-based nature of WiFi, in which the MAC overhead increases with the
number of contending users. Since some of the outband D2D pairs do not
interfere with each other (i.e., they are more distant than $150$ m), the
aggregate throughput of Forced-WiFi in our experiments reaches up to $98$
Mbps. More importantly, not only the simple proposed heuristics greatly
outperform Forced-LTE and Forced-WiFi, but they also perform very close to
Optimal (due to the computational complexity of such an ideal scheme, we only
have the results up to $80$ users).

In terms of energy cost, the aggregate cell power increases with $N$, as shown
in Figure 6.3(b), mainly due to the baseline energy consumption of wireless
interfaces. Forced-WiFi has higher energy consumption because outband users
have to maintain two active wireless interfaces instead of one.

Figure 6.3(c) shows that the trend for system utility is similar to that of
throughput because the throughput is the dominant factor with the current
value of $\alpha$. Our results show that, with a reasonable population, say
$100$ users per cell, the aggregate throughput gain over Forced-LTE is
tenfold. This gain comes from both the frequency re-use of inband modes and
additional spectrum provided by the outband mode, as shown in the figure. The
significant contribution of both outband and inband modes to this gain
highlights the importance of Floating Band D2D. Moreover, this gain can easily
compensate for the infrequent D2D CSI feedbacks sent to the eNB (user-to-user
CSI). Note that in LTE-A systems with millisecond feedback reporting, the CSI
contributes to less than $20$% of the total bandwidth.

In Figure 6.4, we can observe the accuracy of our mode selection and its
performance using packet simulation. Figure 6.4(a) shows that cellular users
have comparable throughput performance under all schemes due to PF scheduling.
If the data rate of a cellular user degrades due to co-channel interference,
the PF compensates for it by allocating more resources to that user. In Figure
6.4(b), it is observed that the fairness among D2D users drops under Forced-
LTE and Forced-WiFi. Under Forced-LTE, D2D users are scheduled as cellular
users, hence they achieve similar fairness performance as cellular users (but
not equal because their fairness is computed over a different set and their
load is different). The fairness reduction under Forced-WiFi is due to
topologically uneven distribution of contending outband users. In Figure
6.4(c), we can observe that utilities of all D2D-enabled schemes grow until
$N$ reaches $50$. The reason for this behavior is that the network operates
under saturation up to this point. In fact, one can observe in Figure 6.3(a)
that the achievable throughput with $50$ users or less is below $120$ Mbps
which is equal to the total offered load (i.e., $\\!30\\!+\\!90$) in the
scenario of Figure 6.4(c). For $N\\!>\\!50$, the utility in the packet
simulation is limited by the adopted load.

(a) Aggregate achievable utility.

(b) Average delivery ratio of cellular users.

(c) Average delivery ratio of D2D users.

Figure 6.5: The impact of overlay portion on system performance
$\left(N=50\right)$.

Impact of overlay resource portion. Here, the number of users per cell is
fixed to $50$. Figure 6.5(a) shows that the utilities of multi-band schemes
increase with the overlay bandwidth. This increment is due to throughput
improvement under mode 2. This implies that D2D users tend to receive more
interference from cellular users than from other D2D users, hence, the
spectral efficiency is higher in overlay than underlay. As mentioned, the
overlay portion is given to modes $0$ and $1$ if there are no overlay users.
As a result, the utilities of Forced-LTE and Forced-WiFi remain unchanged
here.

Although the aggregate utilities are improved, we should also investigate the
impact of overlay bandwidth on cellular users. Figure 6.5(b) illustrates that
the delivery ratio of cellular users degrades as the overlay bandwidth grows
because there is less bandwidth at their disposal. Figure 6.5(b) also sheds
light on the differences among multi-band schemes. Cellular users experience
higher packet delivery ratio with Social. Indeed, Social is the only scheme
that aims to maximize the aggregate utility, which includes the utility of
cellular users. Finally, Figure 6.5(c) shows how the delivery ratio of D2D
users approaches $1$ with higher overlay bandwidths, as expected.

(a) D2D delivery ratio.

(b) Cellular delivery ratio.

(c) Aggregate utility.

Figure 6.6: The impact of D2D load on system performance evaluated through
packet simulation ($N=50$).

(a) Aggregate achievable throughput.

(b) Aggregate achievable utility.

Figure 6.7: The impact of $\alpha$ on system throughput and utility
$\left(N=50\right)$.

Impact of D2D load. The impact of D2D load is shown in Figure 6.6 for $N=50$.
The packet delivery ratio for D2D users drops as the load increases, as shown
in Figure 6.6(a). This is the expected behavior of systems in saturation.
However, as we see in Figure 6.6(b), our schemes are designed in such a way
that saturation of D2D users does not impact the cellular users. This shows
that our proposal can be a candidate for distributed D2D mode selection
implementations in which cellular users are protected from mode selection
decisions of D2D users. It is observed in Figure 6.6(c) that system utility
approaches its achievable limit ($220$) when the D2D load is almost $250$ Mbps
(see Fig 6.3(c), $N\\!=\\!50$). In Fig 6.3(a), we observe that the achievable
capacity for $N\\!=\\!50$ is almost $\\!120\\!$ Mbps. Indeed, by multiplying
the packet delivery ratios (see Figs. 6.6(a) and 6.6(b)) with the aggregate
network load ($250\\!$ Mbps for D2D users and $\\!30\\!$ Mbps for cellular
users), we observe that the achieved throughput is almost $120$ Mbps (i.e.,
$250\cdot 0.4+30\cdot 0.6\\!=\\!118$). With similar calculations, one finds
that Forced-WiFi saturates almost at $100$ Mbps.

Impact of energy cost $\alpha$. Recall that with the current relative energy
cost $\alpha$ our system is biased towards throughput. Hence, we investigate
the impact of $\alpha$ in Figure 6.7, for $N=50$. We start with Figure 6.7(a),
in which a $20\%$ throughput reduction is observed at $\alpha=10^{6}$ b/J.
This shows the system’s bias shifts towards energy minimization as $\alpha$
increases. In Figure 6.7(b), the utility reduces as $\alpha$ grows, although
the behavior of the curves is not linear at all. In particular, for very large
values of $\alpha$, our system prefers Forced-LTE (i.e., mode $0$) because it
only powers one interface. Note that D2D users need to keep the second
interface in idle mode to be able to quickly switch among different modes.
Since we disallow multi-band schemes to assign mode $0$ to D2D users, Forced-
LTE might achieve utilities higher than that of Optimal when $\alpha$ is very
large (e.g., with $\alpha=10^{6}$ b/J, which is too unrealistic as of today
and for the near future due to the high cost of electricity).

Convergence. In Table 6.3, we report the convergence of our proposed
heuristics in terms of time and the number of iterations. The heuristics are
tested on Mathematica™ on a machine with a $3.6$ GHz processor and $8$ GB
memory. Greedy and Social have a very similar convergence time. Greedy is
slightly slower than Social due to decision indexing. Interestingly,
notwithstanding its ranking operations, Ranked has a better performance. This
happens because Ranked converges to a decision with less iterations (which is
what we have indicated as factor $r_{i}$ in Section 6.5.4).

Table 6.3: Convergence of the heuristics ($N=100$) | Social | Greedy | Ranked
---|---|---|---
Average convergence time [s] | 1.61 | 1.62 | 1.43
Average number of iterations $r_{i}$ | 2.69 | 2.80 | 1.46

Flexibility. As mentioned, Floating Band D2D is key to flexible D2D
architectures. We emphasize this fact by evaluating our proposal in various
cellular environments, according to ITU-R guidelines [163]. Table 6.4 shows
that, moving from micro-cell to rural macro-cell, the system relies more on
the cellular spectrum as density reduces. As a consequence, the number of
underlay connections increases. For denser environments, we observe that a
significant part of connections is served using outband D2D.

Table 6.4: Percentage of each mode in different environments ($N=100$) | Urban | Urban | Suburban | Rural
---|---|---|---|---
| micro-cell | macro-cell | macro-cell | macro-cell
Inband underlay | 4% | 8% | 29% | 31%
Inband overlay | 63% | 66% | 66% | 67%
Outband | 33% | 26% | 5% | 2 %

####  6.7 Summary

We have shown that the performance of D2D modes is highly scenario-dependent.
Thus, the most convenient mode in one scenario, say in a macro-cell, could be
a poor choice in another, say in a micro-cell. To cope with this issue, we
proposed the Floating Band D2D framework along with practical heuristics
suitable for quick and adaptive mode selection in such a complex setup. Unlike
existing schemes, we allow D2D users to communicate over inband or outband
modes, depending on network load and channel conditions. Our results
demonstrate the impressive potentials of multi-band mode selection.
Remarkably, our simple heuristics result in fair operation and achieve near
optimal performance by dramatically ameliorating network utility, which
accounts for both throughput and energy consumption.

###  Chapter 7 D2D-Assisted Tie Breaking

####  7.1 Introduction

It has been shown that the cellular throughput can be dramatically improved by
using opportunistic schedulers such as MaxRate [25] and Proportional Fair
[171]. The opportunistic schedulers proposed for cellular networks face a
trade off between throughput and fairness when it comes to prioritizing the
users based on their channel qualities [65, 58]. Hence, with the existing
cellular architectures, opportunistic schedulers cannot achieve maximum
throughput and fairness at the same time, unless all mobile users experience
the very same channel quality [172].

In contrast, in this chapter, we show how to evolve the cellular architecture
by leveraging D2D communications to achieve maximum throughput and maximum
fairness. In particular, we explore the possible gain from having D2D
connections within clusters of mobile users, as presented in Part I of this
dissertation.

However, fairness is achieved in the following way. The schedulers select some
of the connections for transmission, and there are situations in which two or
more users are in tie, i.e., they can be scheduled with the same transmission
rate. These ties are usually ignored or broken randomly [173]. In contrast, we
show that a smart tie-breaking strategy allows to compensate for the channel
quality differences experienced by the data connections which are active in
the cellular network.

So far, nobody has investigated the possibility of enhancing fairness of
opportunistic schedulers by utilizing tie-breaking methods. Thus, we are the
first to explore tie-breaking mechanisms for improving the fairness achieved
with a MaxRate scheduler, though other opportunistic schedulers could also be
enhanced with our approach. We select the MaxRate scheduler since it maximizes
system throughput, and we show that improved fairness levels can be achieved
without paying any throughput cost, i.e., we study how to break ties in order
to improve connection fairness while maintaining the maximum cell throughput.

####  7.2 System model

In this section we present our D2D-based opportunistic scheduling system that
can be leveraged to improve both throughput and fairness in the system.

#####  7.2.1 Connections

We consider a cellular network with a set $\mathcal{N}$ of $N$ persistent
connections of users to a base station, using dedicated wireless channels. In
the following, we focus on downlink communications, though the model is
applicable also to synchronized uplink communications. The base station
operates in a synchronous time-slotted way, and its task is to schedule
connections for transmission in every frame $t=0,1,\dots$. We also assume that
the base station has a queue for storing packets to be delivered to each
connection, and queues are never empty (fully backlogged assumption), so that
we can evaluate the behavior of the system in saturation, i.e., under the
worst scheduling operational conditions.

Connection channels are _heterogeneous_ , i.e., not satisfying the i.i.d.
assumption common to many works on cellular networks. The communication
channel for connection $n$ is characterized by stationary Rayleigh fading.
Therefore, the SNR for connection $n$ can be described as a random process
$C_{n}(t)$ with mean $\gamma_{n}$ and CDF given by:

$\displaystyle\vspace{-1mm}F_{n}(z)=1-e^{-\frac{z}{\gamma_{n}}},\quad z\geq
0,\;\gamma_{n}\in\Gamma,\;n\in\mathcal{N};$ (7.1)

where, for the sake of tractability, we have introduced $\Gamma$ as the
discrete set of average values for the SNR of connections.

We assume that the information available at the base station corresponds to
the steady-state distribution of SNR. Note that, for practical systems, in
which measured channel conditions form a discrete set, existing patents [174,
175, 176] propose to keep track of historical observations of the SNR of every
connection in order to provide an estimate of the steady-state distribution of
SNR. We assume that the selection of MCS is perfect (i.e., transmissions are
affected by negligible error rate), so that we ignore retransmissions.
Eventually, we consider a system with no power control, which is typical for
realistic downlink transmission schemes in LTE.

#####  7.2.2 Scheduling of Clusters of Users

In the previous discussion we had implicitly associated every connection with
a single user. However, mobile users may form clusters using cooperative D2D
communications, in which only one of the users, namely the cluster head,
connects at a given frame to the base station and relays traffic for the other
users.

The scheduling algorithm is MaxRate, i.e., the cluster that contains the user
with the highest MCS is scheduled, so we propose to operate clusters in an
opportunistic way: $(i)$ the cluster head can change on a per-frame basis, as
it is opportunistically selected as the cluster member with the highest
current MCS rate; $(ii)$ an entire cluster is scheduled as an individual user
whose MCS is the highest among members; and $(iii)$ the cluster head relays
the downlink packets to the final destination (intra-cluster communications)
on a secondary wireless interface, using D2D communications. Therefore, in
this chapter, a connection $n$ can be a user or a cluster (also indicated as
CLn) composed by $m_{n}$ mobiles, and its instantaneous SNR is the highest SNR
among the mobile users composing the cluster. In particular, the probability
$p_{\text{CL}_{n},k}$ that a scheduled connection $n$ (i.e., cluster CLn)
receives data encoded according to the $k$-th MCS can be computed based on the
SNR and the MCS thresholds used in LTE (see Appendix B).

For simplicity of notation, we omit the “CL” index in the formulas in the
reminder of this chapter, so that expressions like $p_{n,k}$ and $F_{n}(z)$
can be equivalently used for connection $n$ and cluster CLn. Similarly, we
will use the notation “connection $n$” to address either the mobile user $n$
or the cluster CLn, according to the context.

As detailed in Subsections 7.3.3, 7.4.2, and 7.5.1, scheduling clusters
instead of users not only brings advantages in terms of system throughput, but
also in terms of fairness. However, we will mainly focus on inter-cluster
fairness, since the actual per-user fairness depends on the way resources are
shared within a cluster. Accordingly, when we refer to per-user throughput and
fairness, we assume that cluster resources are divided equally between cluster
members. Note that user throughput unfairness due to heterogeneous channel
qualities within the same cluster is smoothed by the adopted cooperative D2D
communications mechanisms.

####  7.3 Maximal Fairness with MaxRate Scheduling

Maximum throughput is achieved in our setting by using MaxRate, which in each
frame transmits data to a connection with the highest instantaneous SNR, i.e.,
the process of selected connection $A(t)$ must satisfy for every $t$ that
$A(t)=n$ implies $R_{n}(t)\geq R_{m}(t)$ for all connections $m=1,\dots,N$.
Therefore, by definition, MaxRate is throughput-optimal, and so is our
proposal.

The objective of this section is to study when it is possible, and how, to
achieve the perfect fairness given that the scheduler be MaxRate. We focus on
fairness in the sense of equalizing the expected time-average throughput
across connections, independently of their average channel quality. The only
degree of freedom that the system offers to play with fairness consists in the
occurrence of ties in the scheduling mechanism, which is frequent in systems
using only few discrete MCS values. This degree of freedom can be exploited by
designing a tie-breaking rule to employ if at least two connections compete
for scheduled with the same highest instantaneous transmission rate. Formally,
we use the following definitions:

######  Definition 1.

(Best set $\cal M$ and best MSC $\kappa$) ${\cal M}(t,\kappa(t))$ is the set
of connections that can be scheduled with the $\kappa$-th MCS in frame $t$,
and $\kappa$ is the best MCS that can be used in the system in frame $t$,
according to the SNR of the connections. We will use $\cal M$ as short for
${\cal M}(t,\kappa(t))$.

######  Definition 2.

(Tie) A tie occurs when, in a given frame $t$, two or more connections can be
scheduled by the MaxRate mechanism with the same MCS $\kappa$, which is the
best possible MCS in the system at that scheduling epoch, that is: $|{\cal
M}(t,\kappa(t))|>1$.

######  Definition 3.

(Tie-breaking) A tie-breaking mechanism is a procedure to select exactly one
connection $i\in{\cal M}(t,\kappa(t))$ to be scheduled when a tie occurs at
time $t$.

In what follows, we first examine the multiple-connection case and show that
it is intractable to solve exactly. Then we study the two-connection case in
detail, for which we provide complete answers. Using the outcome of the
analysis for two-connections case, we develop the fundamental intuition for
tie-breaking. In Section 7.4, inspired by this intuition, we design low
complexity heuristics for the multi-connection case. Subsequently, we show how
clustering can be beneficial in achieving perfect fairness via tie-breaking,
without paying in terms of throughput.

In many of the arguments below we will rely on the fact that the expected
long-term fairness (throughput distribution over an indefinitely long
interval) is equivalent to the expected one-slot fairness (average per-slot
throughput distribution), due to the stationarity channel assumption we made
earlier.

#####  7.3.1 Analysis of the Multiple-Connections Case

Let us denote by $\displaystyle Q_{n,k}:=\sum_{l=1}^{k-1}p_{n,l}$ the
probability that connection $n\in\mathcal{N}$ has an MCS strictly worse than
$k$. Note that $Q_{n,1}=0$. Let $h_{n}\in\\{0,1\\}$ denote whether the current
MCS of connection $n$ is higher than or equal to the current MCS’ of all the
other connections ($h_{n}=1$) or not ($h_{n}=0$). Then, vector
$\boldsymbol{h}:=\left(h_{n}\right)_{n\in\mathcal{N}}$ identifies with
elements $1$ precisely those connections that are allowed to transmit under
MaxRate (only one of them is transmitting at any moment). Note that, by
definition, $\boldsymbol{h}=\boldsymbol{0}$ cannot happen.

We can now define

$\displaystyle R^{\boldsymbol{h}}$
$\displaystyle:=\sum_{k=1}^{K}\left(r_{k}\prod_{n:h_{n}=1}p_{n,k}\prod_{n:h_{n}=0}Q_{n,k}\right),$
(7.2)

which represents the expected (both one-slot and time-average) cumulative
throughput of the system in situation $\boldsymbol{h}$ (i.e., when exactly the
connections specified by $\boldsymbol{h}$ are in a tie situation).
$R^{\boldsymbol{h}}$ is therefore the “tie throughput” to be shared between
connections for which $h_{n}=1$.

The number of $1$’s of $\boldsymbol{h}$ is denoted by $L_{0}(\boldsymbol{h})$
(so-called _zero “norm”_). If $L_{0}(\boldsymbol{h})=1$, then there is a
single connection with highest MCS, so it will be scheduled. If
$L_{0}(\boldsymbol{h})\geq 2$, then there are several connections in a tie,
and the scheduler must decide who to serve. Without loss of generality this
can be done randomly. Then we need to define $L_{0}(\boldsymbol{h})$
parameters $0\leq\alpha_{n}^{\boldsymbol{h}}\leq 1$ for every connection $n$
such that $h_{n}=1$, denoting the probability of serving connection $n$ in
situation $\boldsymbol{h}$.

Let us denote by $\mathcal{H}_{1}:=\\{\boldsymbol{h}:L_{0}(\boldsymbol{h})\geq
1\\}$ the set of all vectors $\boldsymbol{h}\neq\boldsymbol{0}$. Then the
aggregate throughput of the system under MaxRate scheduler is equal to
$\sum_{\boldsymbol{h}\in\mathcal{H}_{1}}R^{\boldsymbol{h}}$, and the perfectly
fair share is thus
$R^{*}:=\sum_{\boldsymbol{h}\in\mathcal{H}_{1}}R^{\boldsymbol{h}}/N$. We
further denote by
$\mathcal{H}_{2}:=\\{\boldsymbol{h}:L_{0}(\boldsymbol{h})\geq 2\\}$ the set of
all vectors representing ties (of at least two connections). Then achieving
perfect fairness means that the following equalities hold:

$\displaystyle
R^{\boldsymbol{e}_{n}}+\sum_{\boldsymbol{h}\in\mathcal{H}_{2}:h_{n}=1}\alpha_{n}^{\boldsymbol{h}}R^{\boldsymbol{h}}$
$\displaystyle=R^{*}$ $\displaystyle\text{ for all }n\in\mathcal{N}$ (7.3)
$\displaystyle\sum_{n\in\mathcal{N}}\alpha_{n}^{\boldsymbol{h}}$
$\displaystyle=1$ $\displaystyle\text{ for all
}\boldsymbol{h}\in\mathcal{H}_{2}$ (7.4)

where $\boldsymbol{e}_{n}$ is the unit vector with $1$ at $n$-th position, and
$0$’s otherwise, representing the situation when connection $n$ is the unique
connection achieving the highest transmission rate.