# A Game-Theoretical Approach for Spectrum Efficiency Improvement in Cloud-RAN

Authors: Zhuofu Zhou; Jun Peng; Xiaoyong Zhang; Kaiyang Liu; Fu Jiang
Journal: Mobile Information Systems
 (2016)

---

## Abstract

As tremendous mobile devices access to the Internet in the future, the cells which can provide high data rate and more capacity are expected to be deployed. Specifically, in the next generation of mobile communication 5G, cloud computing is supposed to be applied to radio access network. In cloud radio access network (Cloud-RAN), the traditional base station is divided into two parts, that is, remote radio heads (RRHs) and base band units (BBUs). RRHs are geographically distributed and densely deployed, so as to achieve high data rate and low latency. However, the ultradense deployment inevitably deteriorates spectrum efficiency due to the severer intercell interference among RRHs. In this paper, the downlink spectrum efficiency can be improved through the cooperative transmission based on forming the coalitions of RRHs. We formulate the problem as a coalition formation game in partition form. In the process of coalition formation, each RRH can join or leave one coalition to maximize its own individual utility while taking into account the coalition utility at the same time. Moreover, the convergence and stability of the resulting coalition structure are studied. The numeric simulation result demonstrates that the proposed approach based on coalition formation game is superior to the noncooperative method in terms of the aggregate coalition utility.


---

## Body

## 1. Introduction

It is estimated that mobile data traffic will grow 1000 times from 2010 to 2020, as more and more devices which are capable of accessing to the Internet emerge with the development of mobile Internet and Internet of Things (IoTs) [1, 2]. According to the above researches, future networks should be able to accommodate enough pieces of user equipment (UEs) and provide high wireless data rate services while keeping the quality of service (QoS).However, the spectrum resource is extremely scarce, so improving the capacity or data rate by exploiting more bandwidth is not an efficient or feasible method under the circumstance of large-scale access. In order to cater the demand of high capacity and meanwhile guarantee the spectrum efficiency, the heterogeneous networks (HetNets) appear to be the key technology to handle the above challenges [3]. In HetNets, a number of different small cells, such as LTE, WiMax, and Wi-Fi, are deployed densely within the area covered by a macrocell. Due to the characteristics of low power and small coverage of these small cells, the low latency and high rate can be guaranteed. On the other hand, because of the population fluctuating drastically in residential and business areas over the time, the workload of the network also varies following the pattern of the movement of population, which is called tidal effect. The current scheduling mode of the traditional base stations (BSs) is not efficient for solving this problem, since BSs can only accommodate a fixed amount of connectivity for UEs within their coverage. That is to say that the BSs meeting the capacity demand during the day will turn to idle at night, which leads to huge waste of energy or other resources, and vice versa.In order to make the scheduling of resource more flexible and efficient, cloud radio access network (Cloud-RAN) is proposed as a new paradigm to solve the spectrum scarcity challenge faced by the network infrastructures of future mobile communication, which are required to handle an exponentially increasing demand for data services [4, 5]. The most attractive feature of Cloud-RAN is that the BS is broken up into three components: the remote radio heads (RRHs) for the basic transmission and reception functionalities for radio signal, the base band units (BBUs) aimed at processing computationally intensive task, and the fronthaul link for connecting RRHs and BBUs. Different from the traditional hardware management architecture, all BBUs are collected to form a centralized BBU pool in a cloud data center. By this way, similar to servers cluster in cloud computing, the visualization technology and centralized signal processing can be exploited in the BBU pool for dynamic and flexible resource allocation.Although large-scale geographically distributed RRHs can achieve the elasticity and convenience in resource scheduling, it drastically reduces spectrum efficiency caused by the severe intercell interference among RRHs. Orthogonal Frequency Division Multiple Access (OFDMA) can be an effective mechanism to decrease the mutual interference among the UEs within the same RRH, while the interference of the same carrier frequency generated by other RRHs may become worse. Therefore, how to mitigate the intercell interference effectively among the RRHs for higher spectrum efficiency is a key challenge.There are great achievements focused on improving spectrum efficiency in recent years. A graph based clustering scheme was proposed in [6], in which the femtocells and macrocell reuse portion of the whole system bandwidth. Dai et al. [7] proposed a novel OFDM based transmission scheme called TFT-OFDM, whereby the training information exists in both time and frequency domains. In [8], compared with the proposed known Massive MIMO scheme, a novel Network-MIMO TDD architecture requiring an order of magnitude fewer antennas per active use per cell was proposed to achieve high spectral efficiency. A new transmission system, Cloud Transmission for terrestrial broadcasting, was proposed in [9], in which the spectrum utilization can be greatly enhanced by making all terrestrial RF channels in a city/market available for broadcast service. Although lots of proposed researches, like the above literatures, have made great progress in spectrum efficiency. However, they just focused on the micro details while ignoring the scenarios of the cooperation and competition among the access points or UEs in the densely deployed network.Game theory provides a tool framework for analyzing optimization problems with multiple conflicting objectives and has been widely used for improving spectrum efficiency or managing interference [10]. Due to the selfish characteristic of the player in the game, every player tries to meet its communication demand as much as possible. However, the disordered competition among the players may result in the decline of performance of the global system. Therefore, the resource share scheme based on cooperative game can stimulate the collaboration among the players, thus optimizing resource utilization and network performance [11].The cooperative methods based on coalition formation game are regarded as a novel paradigm, which is applied to wireless communication networks [12]. In [13], game based cooperative approaches have better performance than the noncooperative ways which is illustrated by using the interference channel model. In [14], a number of femtocells in user equipment cooperate to merge into a group and improve their uplink spectrum efficiency by sharing spectral resources and suppressing intratier interference using interference alignment. Pantisano et al. [15] presented a novel model where a number of femtocells cooperate to improve their performance by sharing spectral resources, minimizing the number of collisions and maximizing the spatial reuse. The interference management problem in [16] was formulated as a coalition formation game in partition form with negative externalities, and an algorithm named RECORD based on the concept of recursive core was utilized. In [17], the authors proposed a distributed algorithm where the femtocell access point makes the decision to cooperate or not according to the trade-off between the cooperation gains and the energy consumption. The problem of cooperative interference management in an OFDMA two-tier small cell network was studied [18], and a decentralized algorithm was proposed to allow small cell base stations to interact and self-organize into a stable overlapping coalition structure. However, these works just focused on eliminating the mutual interference without considering turning the interference into the additional gain in a coalition. Moreover, in the mentioned works, the information exchange among access points in the process of coalition formation is necessary, which consumes more power for the broadcasting.In this paper, we consider that the coalition formation algorithm is performed in the cloud BBU pool. Within the novel architecture of Cloud-RAN, the RRH is just responsible for transmitting or receiving the data of the UEs in its coverage, so the information exchange among the RRHs can be achieved through the centralized process, which greatly decreases the latency and power consumption. Moreover, the interference can be treated as the additional gain in a coalition by transmitting the same data to the scheduled UE. To show the difference from the existing works, the main contribution of our paper is summarized as follows:(i)
We proposed a novel approach based on coalition formation game to improve the spectrum efficiency within the framework of Cloud-RAN, so as to effectively suppress the mutual interference in the ultradense network.
(ii)
A hybrid multiple access mode is introduced for the coalition to achieve the cooperative transmission among the RRHs. TDMA is adopted within a coalition. Each scheduled UE in this coalition is allocated the duration in a time frame. In each duration, the remaining RRHs in this coalition can transmit the same data simultaneously. Hence, for the scheduled UE in its duration, the mutual interference from neighboring RRHs in a coalition can be turned into the additional gain. Furthermore, FDMA is exploited for each RRH; thus the users served by the same RRH only suffer from cochannel interference generated by the RRHs in other coalitions.
(iii)
The proposed coalition formation game based algorithm focuses on maximizing the spectrum efficiency of the individual RRH by cooperating with the others. Moreover, the proposed algorithm guarantees the increase of the coalition payoff per iteration at the same time. The simulation results demonstrate that proposed method yields a better spectrum efficiency performance than the noncooperative way. In addition, a history variable is introduced to solve the repetitive iteration problems, so the rate of convergence can be improved.The rest of this paper is organized as follows. Section2 presents the system model. Section 3 mainly discusses the approach based on the coalition formation game, and the convergence and stability of the final coalition structure are also studied. The numeric simulation and evaluation are given in Section 4. Finally, we draw a conclusion and discuss our future work in Section 5.


## 2. System Model

As shown in Figure1, we consider the coalition formation scenario in Cloud-RAN. A large number of RRHs are densely deployed within the coverage served by the macro base station (MBS). Each RRH serves just a few UEs within its much smaller coverage. The data of UEs received by RRHs is transmitted to the cloud BBU pool through the optical fiber fronthaul link with low latency [19]. However, if RRHs work in a noncooperative manner, UEs will suffer from low spectrum efficiency due to the severer interference generated by other RRHs. To deal with this problem, a cooperative approach to reducing the mutual interference based on coalition formation game is proposed as follows.Figure 1
Coalition formation model in cloud radio access network.We consider the downlink transmission scenario in Cloud-RAN where each RRH works in OFDMA mode. In this way, the UEs within the same RRH can transmit simultaneously on the same subcarriers without suffering from the interference. However, under the coverage of MBS, the signals transmitted on the same frequency subchannel from the neighboring RRHs interfere with each UE. To reduce the interference, a cooperative method among several RRHs by forming a coalition is exploited. Within the coalition of RRHs, Time Division Multiple Access (TDMA) is introduced. So a hybrid multiple access mode adopting both OFDMA and TDMA is considered. As shown in Figure2, we show the difference between the noncooperative transmission and the cooperative transmission in a coalition. Without loss of generality, we consider a network deployed with two RRHs, that is, RRH 1 and RRH 2. For simplicity, only one user end is served by its corresponding RRH. In Figure 2(a), in noncooperative transmission scheme, we can see that RRH 2 interferes with UE 1 served by the corresponding RRH 1; meanwhile RRH 1 interferes with UE 2 as well in a time frame. In Figure 2(b), the cooperative transmission scheme is depicted. At first, RRH 1 and RRH 2 constitute a coalition, and then a coalition-level scheduler in BBU pool is introduced to allocate the time slot in the time frame for each UE within this coalition. Meanwhile, the time guard interval (TGI) is also introduced to eliminate intersymbol interference between the two neighboring time slots, and generally they can be neglected due to the low overhead. As shown in Figure 2(b), during time slot 1, UE 1 is at the active status where two RRHs can transmit signal simultaneously. So the interference from RRH 2 is turned into additional gain, and the interference can be eliminated and thus the spectrum efficiency can be increased in time slot 1. Consequently, the same results can be achieved for UE 2 in time slot 2.Figure 2
The difference between the noncooperative transmission and the cooperative transmission in a coalition.
(a)
Noncooperative transmission scheme
(b)
Cooperative transmission scheme in a coalition with two RRHsWe consider that there areN RRHs denoted by N
=
{
1,2
,
…
,
N
} which are deployed within the coverage of MBS. We assume that each RRH i
∈
N serves M UEs with M orthogonal subcarriers denoted by M
=
{
f
1
,
f
2
,
…
,
f
M
}. In the noncooperative communication scheme, each UE is just served by only one RRH on a certain subchannel. Due to the orthogonality among the subchannels, the interchannel interference does not exist. However, the severer interference caused by the neighboring RRHs working on the same frequency band signals will limit the spectrum efficiency of the downlink. Therefore, the received signal to interference plus noise ratio (SINR) of UE served by RRH i
∈
N on subchannel f
k
∈
M
i can be defined as(1)
S
I
N
R
i
k
=
p
i
k
g
0
,
i
k
I
0
+
B
i
k
N
0
+
I
i
,
N
k
,where p
i
k denotes the transmit power of RRH i on subchannel f
k and g
0
,
i
k is the channel gain from RRH i to its UE on subchannel f
k. I
0 is the interference from the MBS. Let B
i
k and N
0 denote the bandwidth of UE served by RRH i over subchannel f
k and noise power spectral density of additive white Gaussian noise (AWGN), respectively. We denote the intercell interference which is suffered by the UE served by RRH i on subchannel f
k by(2)
I
i
,
N
k
=
∑
j
∈
N
,
j
≠
i
p
j
k
g
i
,
j
k
,where p
j
k is the transmit power of RRH j
∈
N over subchannel f
k and g
i
,
j
k denotes the channel gain from RRH j to the UE receiver served by RRH i over subchannel f
k.According to the Shannon formula, the downlink spectrum efficiency of the UE served by RRHi over subchannel f
k can be defined as(3)
R
i
k
=
log
2
⁡
1
+
p
i
k
g
0
,
i
k
I
0
+
B
i
k
N
0
+
I
i
,
N
k
.In such noncooperative scenario, we can find that, from the formula (3), each UE on subchannel f
k suffers severe intercell cochannel interference from remaining N
-
1 RRHs, since the limited spectrum resource is shared among them, and the white noise and the interference from the MBS are also taken into account.


## 3. Coalition Formation

In order to minimize the mutual interference for high spectrum efficiency, it is necessary for a set of RRHs to transmit signals cooperatively to improve their performance. Therefore, we formulate the problem of cooperation among RRHs as a coalition formation game in partition form. Given a number of RRHs, the various different coalitions can be formed in terms of the coalition size and profit or utility of the RRHs within the coalition. Hence, it is necessary to setup some criterions for each RRH to decide whether to join or to split from a coalition. There are two main criterions: (i)stability, only when every RRH in the coalition has no incentive to leave the federation for more individual profit can the coalition keep stable and (ii)fairness, each RRH is selfish and expected to obtain as more profits as possible when it chooses to join or leave a coalition. So the fair profit allocation scheme is essential to maintain the coalition stability.


### 3.1. The Concept of Coalition Formation

The problem of RRHs cooperation is mathematically modeled as a coalition formation game withtransferable utility [20]. The proposed algorithm is based on thehedonic game [21], where each player (referred to as RRH in this paper) is selfish and its payoff is completely determined by the identity of other members within the coalition.As defined in Section2, the set of RRHs N
=
{
1,2
,
…
,
N
} is given. Let S
⊆
N denote the coalition of RRHs. We define π
N as the coalition structure or partition where π
N
=
{
S
1
,
S
2
,
…
,
S
l
}. For any one coalition structure, π
N, we have ∪
S
∈
π
N
=
N and S
i
∩
S
j
=
ϕ for i
≠
j. Once a coalition is formed, a coalition-level scheduler will work according to the hybrid multiple access mode which is depicted in Figure 2. For any RRH in a coalition, the corresponding UE served by this RRH on some subcarrier is scheduled according to the TDMA rule. In Figure 2(b), one time slot is allocated to one UE. And, in this time slot, the remaining RRHs in the same coalition can simultaneously serve this UE. Therefore, for one UE in its time slot, the received power can be improved and thus the mutual interference among RRHs in a coalition can be eliminated. In this way, the UEs just suffer from the interference caused by the RRHs in other coalitions.For any RRHi in coalition S
l
∈
π
N, the received power and interference of the UE over subchannel f
k
∈
M can be expressed, respectively, as follows:(4)
P
i
k
=
p
i
k
g
0
,
i
k
+
∑
n
∈
S
l
,
n
≠
i
p
n
k
g
i
,
n
k
,
(5)
I
i
,
N
∖
S
l
k
=
∑
j
∈
N
∖
S
l
p
j
k
g
i
,
j
k
.According to the explanation of Figure2(b), during the time slot of the UE served by RRH i, ∑
n
∈
S
l
,
n
≠
i
p
n
k
g
i
,
n
k denotes the additional gain from the remaining RRHs in coalition S
l. I
i
,
N
∖
S
l
kis the interference from the remaining coalitions in coalition structure π
N.Consequently, for one coalition of RRHsS
l
∈
π
N, the total sum-rate achieved can be given by function R
(
S
l
,
π
N
) defined as follows:(6)
R
S
l
,
π
N
=
∑
i
∈
S
l
∑
k
∈
M
α
i
k
log
2
⁡
1
+
P
i
k
I
0
+
B
i
k
N
0
+
I
i
,
N
∖
S
l
k
,where α
i
k denotes the fraction of the time frame duration during which RRH i transmits signal over subchannel f
k. What is more, for any RRH i in coalition S
l
∈
π
N and given a subchannel f
k
∈
M, we have ∑
i
∈
S
l
α
i
k
=
1 and α
i
k
≥
0. If the RRH is in singleton, α
i
k is equal to 1, which means that the UE occupies subchannel f
k for all its duration.Accordingly, we define coalition valuev
(
S
l
,
π
N
) based on (6) as follows:(7)
v
S
l
,
π
N
=
R
S
l
,
π
N
M
,where M is the cardinality of the orthogonal subcarriers set M, that is, the number of the subcarriers within each RRH. For reducing the complexity, we assumed that each RRH provides the same number of subcarries in Section 2. In (7), we consider the average performance of each RRH. For empty set ϕ, we have v
(
ϕ
,
π
N
)
=
0.Each RRH makes its own decision to join or leave a coalition based on its payoff. During the coalition formation, each RRH is selfish and expected to get more payoff as much as possible while keeping the stability and fairness criterions. Therefore, based on the coalition value acquired from (7), a fair payoff allocation mechanism for individual player should be considered.The egalitarian fair method is the most common way where each player shares the equal extra value generated by the cooperation among the members in the formed coalition. The value of RRHi among coalition S
l is defined as(8)
x
i
S
l
,
π
N
=
1
S
l
v
S
l
,
π
N
-
∑
j
∈
S
l
v
j
,
π
N
+
v
i
,
π
N
.However, such method is not fair enough, since the channel gain from the RRH to its UEs differs from each other. The RRH with better channel gain is reluctant to cooperate with the RRH with bad channel condition. In the process of coalition formation, the player who creates more extra value should be allocated more payoff. Consequently, based on the egalitarian criterions, the weight according to the player’s noncooperative utility is taken into consideration. Finally, the payoff of RRHi in coalition S
l can be calculated by the following equation:(9)
x
i
S
l
,
π
N
=
ω
i
v
S
l
,
π
N
-
∑
j
∈
S
l
v
j
,
π
N
+
v
i
,
π
N
,where ∑
i
∈
S
ω
i
=
1 and within coalition ω
i
/
ω
j
=
v
i
/
v
(
{
j
}
).


### 3.2. The Condition to Form Coalition

In the procedure of coalition formation, atomic step is that the individual RRH splits from one coalition to another one for the higher payoff. In order to express this action specifically in mathematical method, some definitions for comparing two different coalitions are presented at first.Definition 1.
Consider two different coalitionsS
1, S
2
⊆
N and S
1
≠
S
2, which both include RRH i
∈
N. Apreference relation
≻
i is defined as a complete, reflexive, and transitive binary relation over the set of all coalitions that RRH i can form [22]. Therefore, S
1
≻
i
S
2 indicates that RRH i prefers to stay at coalition S
1 rather than coalition S
2.In our RRHs, for cooperation problem which is modeled as the coalition formation game, we aimed at increasing the coalition value while considering allocating fairly higher payoff to the members of the coalition at the same time. For any RRHi
∈
N, the abovepreference relation is equivalent to the following inequation:(10)
S
1
≻
i
S
2
⟺
x
i
S
1
,
π
N
∗
>
x
i
S
2
,
π
N
,where (10) denotes that RRH i splits from coalition S
2 to join coalition S
1 for more individual payoff, which results in the change of the coalition structure from π
N to π
N
∗.Based on the concept ofpreference relation given above, the three conditions for changing the current coalition structure are studied. Briefly speaking, (i) the value of the newly formed coalition should be greater than the sum of the individual utility of all the members who belong to the newly formed coalition, working in noncooperative manner. (ii) The value of the newly formed coalition should be greater than the value of the coalition in last state which does not incorporate the player desired to join. (iii) The payoff allocated to the every member within the newly formed coalition is supposed to be higher than the payoff allocated in old coalition. Then, the more specific mathematical expressions are presented in subsequent parts.Condition 1.
The motivation for each RRH to cooperate with others whereby forming a coalition is to mitigate the mutual interference and increase the spectrum efficiency further. Therefore, the total value produced by forming a coalition is expected to exceed the summation of the value created by each RRH within the coalition without cooperation among them. Specifically, for any RRHi
∈
N that tends to join some coalition S
l
∈
π
N excluding i, hence,Condition
1 should be satisfied firstly, and it can be written as(11)
v
S
l
∪
i
,
π
N
∗
>
∑
j
∈
S
l
∪
i
v
j
,
π
N
∗
,where π
N
∗ denotes the changed coalition structure after RRH i is incorporated into coalition S
l.Condition 2.
Condition
1 is only the prerequisite to form a new coalition, and two sufficient conditions are given inConditions  2 and 3, respectively.Condition
2 is a new coalition that can be formed only when the coalition value gets increased after incorporating the new RRH, which is designed for higher system efficiency. Thus, based on (11),Condition
2 can be expressed mathematically as follows:(12)
v
S
l
∪
i
,
π
N
∗
>
v
S
l
,
π
N
.Condition 3.
Based on the two conditions above, after allocating coalition value to all members within it, the last condition is that each player’s payoff in newly formed coalition should be greater than its payoff in its old coalition. Consequently, for any RRHj
∈
S
l
∪
{
i
} and j
≠
i,Condition
3 is written as follows:(13)
x
j
S
l
∪
i
,
π
N
∗
>
x
j
S
l
,
π
N
,where for case j
=
i,Condition
3 meets inequation constrain (10).


### 3.3. The Algorithm of Coalition Formation

According to the definition elaborated in Algorithm1, to solve the cooperation problem for RRHs, we propose a novel and efficient algorithm which is based on thehedonic shift rule [14]: given coalition structure π
N
=
{
S
1
,
S
2
,
…
,
S
l
} defined on RRHs set N and preference relation ≻
i, for any RRH i
∈
N that decides to leave its current coalition S
c to join another one S
∈
π
N
∪
ϕ if and only if S
∪
{
i
}
≻
i
S
c, that is, RRH i can benefit more from being one of the members of coalition S than staying at coalition S
c. Based on the characteristic of the hedonic game described in Section 3.1, we can conclude that, on one hand, every player is selfish enough, since it just tries to join the coalition where it can obtain more payoff without considering the decrease at the value of the coalition to which it ever belonged. On the other hand, the coalition only incorporates the potential player which can improve the coalition value.Algorithm 1:The proposed RRHs cooperation algorithm.
Stage 1: Initialization
The network is partitioned byπ
N
=
{
{
1
}
,
{
2
}
,
…
,
{
N
}
} at the
beginning time. For eachi
∈
N, to initialize the variable h
(
i
) as
the empty set.
Stage 2: Coalition Formation
do
for
each RRH i  in  N
for
each  S  in  π
N
if  S
∪
i
≻
i
S
c  then
(a) If the (11) in Condition1, (12) in Condition2,
(13) in Condition3and S
∉
h
(
i
) are satisfied
at the same time, then record the coalitionS.
end if
if all recorded S is not a empty set then
(a) After traversing all the possible coalitions inπ
N,
the optimumS
o is found.
(b) RRHi decides to perform the hedonic shift rule
from current coalitionS
c to the optimal one S
o.
(1) RRH i updates the history variable h
(
i
) by
adding the old coalitionS
c to the h
(
i
).
(2) RRH i leaves its current coalition S
c and
joins the new coalitionS
o.
(3) π
N is updated,
π
N
=
(
π
N
∖
{
S
o
,
S
c
}
)
∪
{
S
c
∖
{
i
}
,
S
o
∪
{
i
}
}.
end if
end for
end for
untilthe coalition structure is stable.
Stage 3: Cooperative Transmission
All the RRHs transmit signals cooperatively, which is
controlled by a coalition-level scheduler in a hybrid multiple
access mode.With the three conditions defined above, the cloud BBU pool can perform the proposed algorithm where RRHs are partitioned into different coalitions, considering both the individual value and coalition value. The corresponding algorithm is proposed in Algorithm1.In proposed Algorithm1, we define a history variable h
(
i
) which is designed for RRH i recording the coalitions that it ever joined when the algorithm is performing the transfer from one coalition to another. By introducing h
(
i
), the coalition formation algorithm must converge to a stable structure. The advantage of our algorithm is that both the payoff of the individual RRH and the aggregate coalition value are considered simultaneously when an external RRH is desired to merge into the coalition, which is achieved by the three conditions expressed mathematically in (11), (12), and (13). Due to the superiority of parallel and centralized computing in cloud BBU pool, the proposed algorithm can be implemented more easily, comparing with the traditional distributed algorithm where one FAP negotiates with the others to form the coalition by broadcasting their information.Proposition 2.
From the initial coalition structureπ
N
=
{
{
1
}
,
{
2
}
,
…
,
{
N
}
}, the proposed algorithm always converges to final structure π
N
f.Proof.
The evolution process of coalition structure can be described as a discrete sequence. Specifically, for any RRHi
∈
N, each hedonic shift action can turn current coalition structure π
N
c into next stage π
N
c
+
1.According to the proposed algorithm, for RRHi
∈
N, after traversing all the current coalitions, there are two cases; that is, one is that no feasible coalition is recorded and another is that at least one coalition is recorded as the chosen optimal coalition to join. For the first case, the coalition structure maintains the current status; thus, the number of revisited structures is limited. For the second case, the number of the coalition structures is also finite, and according to [23], it is no more than the Bell number, that is, the number of the set partitions. Consequently, in both of the two cases, the proposed algorithm always terminates and converges to final coalition structure π
N
f.Proposition 3.
Any stable coalition structureπ
N
f formed in the end is Nash-stable.Proof.
This proposition can be proved by the contradiction. We assume that the final coalition structureπ
N
f is not Nash-stable. Hence, there exist RRH i
∈
N and coalition S
∈
π
N
f so that S
∪
{
i
}
≻
i
S
c for S
c
∈
π
N
f. Then, RRH i will perform a hedonic shift action and therefore π
N
f will also change. Consequently, this contradicts the assumption that π
N
f is the final structure of the proposed algorithm.


## 3.1. The Concept of Coalition Formation

The problem of RRHs cooperation is mathematically modeled as a coalition formation game withtransferable utility [20]. The proposed algorithm is based on thehedonic game [21], where each player (referred to as RRH in this paper) is selfish and its payoff is completely determined by the identity of other members within the coalition.As defined in Section2, the set of RRHs N
=
{
1,2
,
…
,
N
} is given. Let S
⊆
N denote the coalition of RRHs. We define π
N as the coalition structure or partition where π
N
=
{
S
1
,
S
2
,
…
,
S
l
}. For any one coalition structure, π
N, we have ∪
S
∈
π
N
=
N and S
i
∩
S
j
=
ϕ for i
≠
j. Once a coalition is formed, a coalition-level scheduler will work according to the hybrid multiple access mode which is depicted in Figure 2. For any RRH in a coalition, the corresponding UE served by this RRH on some subcarrier is scheduled according to the TDMA rule. In Figure 2(b), one time slot is allocated to one UE. And, in this time slot, the remaining RRHs in the same coalition can simultaneously serve this UE. Therefore, for one UE in its time slot, the received power can be improved and thus the mutual interference among RRHs in a coalition can be eliminated. In this way, the UEs just suffer from the interference caused by the RRHs in other coalitions.For any RRHi in coalition S
l
∈
π
N, the received power and interference of the UE over subchannel f
k
∈
M can be expressed, respectively, as follows:(4)
P
i
k
=
p
i
k
g
0
,
i
k
+
∑
n
∈
S
l
,
n
≠
i
p
n
k
g
i
,
n
k
,
(5)
I
i
,
N
∖
S
l
k
=
∑
j
∈
N
∖
S
l
p
j
k
g
i
,
j
k
.According to the explanation of Figure2(b), during the time slot of the UE served by RRH i, ∑
n
∈
S
l
,
n
≠
i
p
n
k
g
i
,
n
k denotes the additional gain from the remaining RRHs in coalition S
l. I
i
,
N
∖
S
l
kis the interference from the remaining coalitions in coalition structure π
N.Consequently, for one coalition of RRHsS
l
∈
π
N, the total sum-rate achieved can be given by function R
(
S
l
,
π
N
) defined as follows:(6)
R
S
l
,
π
N
=
∑
i
∈
S
l
∑
k
∈
M
α
i
k
log
2
⁡
1
+
P
i
k
I
0
+
B
i
k
N
0
+
I
i
,
N
∖
S
l
k
,where α
i
k denotes the fraction of the time frame duration during which RRH i transmits signal over subchannel f
k. What is more, for any RRH i in coalition S
l
∈
π
N and given a subchannel f
k
∈
M, we have ∑
i
∈
S
l
α
i
k
=
1 and α
i
k
≥
0. If the RRH is in singleton, α
i
k is equal to 1, which means that the UE occupies subchannel f
k for all its duration.Accordingly, we define coalition valuev
(
S
l
,
π
N
) based on (6) as follows:(7)
v
S
l
,
π
N
=
R
S
l
,
π
N
M
,where M is the cardinality of the orthogonal subcarriers set M, that is, the number of the subcarriers within each RRH. For reducing the complexity, we assumed that each RRH provides the same number of subcarries in Section 2. In (7), we consider the average performance of each RRH. For empty set ϕ, we have v
(
ϕ
,
π
N
)
=
0.Each RRH makes its own decision to join or leave a coalition based on its payoff. During the coalition formation, each RRH is selfish and expected to get more payoff as much as possible while keeping the stability and fairness criterions. Therefore, based on the coalition value acquired from (7), a fair payoff allocation mechanism for individual player should be considered.The egalitarian fair method is the most common way where each player shares the equal extra value generated by the cooperation among the members in the formed coalition. The value of RRHi among coalition S
l is defined as(8)
x
i
S
l
,
π
N
=
1
S
l
v
S
l
,
π
N
-
∑
j
∈
S
l
v
j
,
π
N
+
v
i
,
π
N
.However, such method is not fair enough, since the channel gain from the RRH to its UEs differs from each other. The RRH with better channel gain is reluctant to cooperate with the RRH with bad channel condition. In the process of coalition formation, the player who creates more extra value should be allocated more payoff. Consequently, based on the egalitarian criterions, the weight according to the player’s noncooperative utility is taken into consideration. Finally, the payoff of RRHi in coalition S
l can be calculated by the following equation:(9)
x
i
S
l
,
π
N
=
ω
i
v
S
l
,
π
N
-
∑
j
∈
S
l
v
j
,
π
N
+
v
i
,
π
N
,where ∑
i
∈
S
ω
i
=
1 and within coalition ω
i
/
ω
j
=
v
i
/
v
(
{
j
}
).


## 3.2. The Condition to Form Coalition

In the procedure of coalition formation, atomic step is that the individual RRH splits from one coalition to another one for the higher payoff. In order to express this action specifically in mathematical method, some definitions for comparing two different coalitions are presented at first.Definition 1.
Consider two different coalitionsS
1, S
2
⊆
N and S
1
≠
S
2, which both include RRH i
∈
N. Apreference relation
≻
i is defined as a complete, reflexive, and transitive binary relation over the set of all coalitions that RRH i can form [22]. Therefore, S
1
≻
i
S
2 indicates that RRH i prefers to stay at coalition S
1 rather than coalition S
2.In our RRHs, for cooperation problem which is modeled as the coalition formation game, we aimed at increasing the coalition value while considering allocating fairly higher payoff to the members of the coalition at the same time. For any RRHi
∈
N, the abovepreference relation is equivalent to the following inequation:(10)
S
1
≻
i
S
2
⟺
x
i
S
1
,
π
N
∗
>
x
i
S
2
,
π
N
,where (10) denotes that RRH i splits from coalition S
2 to join coalition S
1 for more individual payoff, which results in the change of the coalition structure from π
N to π
N
∗.Based on the concept ofpreference relation given above, the three conditions for changing the current coalition structure are studied. Briefly speaking, (i) the value of the newly formed coalition should be greater than the sum of the individual utility of all the members who belong to the newly formed coalition, working in noncooperative manner. (ii) The value of the newly formed coalition should be greater than the value of the coalition in last state which does not incorporate the player desired to join. (iii) The payoff allocated to the every member within the newly formed coalition is supposed to be higher than the payoff allocated in old coalition. Then, the more specific mathematical expressions are presented in subsequent parts.Condition 1.
The motivation for each RRH to cooperate with others whereby forming a coalition is to mitigate the mutual interference and increase the spectrum efficiency further. Therefore, the total value produced by forming a coalition is expected to exceed the summation of the value created by each RRH within the coalition without cooperation among them. Specifically, for any RRHi
∈
N that tends to join some coalition S
l
∈
π
N excluding i, hence,Condition
1 should be satisfied firstly, and it can be written as(11)
v
S
l
∪
i
,
π
N
∗
>
∑
j
∈
S
l
∪
i
v
j
,
π
N
∗
,where π
N
∗ denotes the changed coalition structure after RRH i is incorporated into coalition S
l.Condition 2.
Condition
1 is only the prerequisite to form a new coalition, and two sufficient conditions are given inConditions  2 and 3, respectively.Condition
2 is a new coalition that can be formed only when the coalition value gets increased after incorporating the new RRH, which is designed for higher system efficiency. Thus, based on (11),Condition
2 can be expressed mathematically as follows:(12)
v
S
l
∪
i
,
π
N
∗
>
v
S
l
,
π
N
.Condition 3.
Based on the two conditions above, after allocating coalition value to all members within it, the last condition is that each player’s payoff in newly formed coalition should be greater than its payoff in its old coalition. Consequently, for any RRHj
∈
S
l
∪
{
i
} and j
≠
i,Condition
3 is written as follows:(13)
x
j
S
l
∪
i
,
π
N
∗
>
x
j
S
l
,
π
N
,where for case j
=
i,Condition
3 meets inequation constrain (10).


## 3.3. The Algorithm of Coalition Formation

According to the definition elaborated in Algorithm1, to solve the cooperation problem for RRHs, we propose a novel and efficient algorithm which is based on thehedonic shift rule [14]: given coalition structure π
N
=
{
S
1
,
S
2
,
…
,
S
l
} defined on RRHs set N and preference relation ≻
i, for any RRH i
∈
N that decides to leave its current coalition S
c to join another one S
∈
π
N
∪
ϕ if and only if S
∪
{
i
}
≻
i
S
c, that is, RRH i can benefit more from being one of the members of coalition S than staying at coalition S
c. Based on the characteristic of the hedonic game described in Section 3.1, we can conclude that, on one hand, every player is selfish enough, since it just tries to join the coalition where it can obtain more payoff without considering the decrease at the value of the coalition to which it ever belonged. On the other hand, the coalition only incorporates the potential player which can improve the coalition value.Algorithm 1:The proposed RRHs cooperation algorithm.
Stage 1: Initialization
The network is partitioned byπ
N
=
{
{
1
}
,
{
2
}
,
…
,
{
N
}
} at the
beginning time. For eachi
∈
N, to initialize the variable h
(
i
) as
the empty set.
Stage 2: Coalition Formation
do
for
each RRH i  in  N
for
each  S  in  π
N
if  S
∪
i
≻
i
S
c  then
(a) If the (11) in Condition1, (12) in Condition2,
(13) in Condition3and S
∉
h
(
i
) are satisfied
at the same time, then record the coalitionS.
end if
if all recorded S is not a empty set then
(a) After traversing all the possible coalitions inπ
N,
the optimumS
o is found.
(b) RRHi decides to perform the hedonic shift rule
from current coalitionS
c to the optimal one S
o.
(1) RRH i updates the history variable h
(
i
) by
adding the old coalitionS
c to the h
(
i
).
(2) RRH i leaves its current coalition S
c and
joins the new coalitionS
o.
(3) π
N is updated,
π
N
=
(
π
N
∖
{
S
o
,
S
c
}
)
∪
{
S
c
∖
{
i
}
,
S
o
∪
{
i
}
}.
end if
end for
end for
untilthe coalition structure is stable.
Stage 3: Cooperative Transmission
All the RRHs transmit signals cooperatively, which is
controlled by a coalition-level scheduler in a hybrid multiple
access mode.With the three conditions defined above, the cloud BBU pool can perform the proposed algorithm where RRHs are partitioned into different coalitions, considering both the individual value and coalition value. The corresponding algorithm is proposed in Algorithm1.In proposed Algorithm1, we define a history variable h
(
i
) which is designed for RRH i recording the coalitions that it ever joined when the algorithm is performing the transfer from one coalition to another. By introducing h
(
i
), the coalition formation algorithm must converge to a stable structure. The advantage of our algorithm is that both the payoff of the individual RRH and the aggregate coalition value are considered simultaneously when an external RRH is desired to merge into the coalition, which is achieved by the three conditions expressed mathematically in (11), (12), and (13). Due to the superiority of parallel and centralized computing in cloud BBU pool, the proposed algorithm can be implemented more easily, comparing with the traditional distributed algorithm where one FAP negotiates with the others to form the coalition by broadcasting their information.Proposition 2.
From the initial coalition structureπ
N
=
{
{
1
}
,
{
2
}
,
…
,
{
N
}
}, the proposed algorithm always converges to final structure π
N
f.Proof.
The evolution process of coalition structure can be described as a discrete sequence. Specifically, for any RRHi
∈
N, each hedonic shift action can turn current coalition structure π
N
c into next stage π
N
c
+
1.According to the proposed algorithm, for RRHi
∈
N, after traversing all the current coalitions, there are two cases; that is, one is that no feasible coalition is recorded and another is that at least one coalition is recorded as the chosen optimal coalition to join. For the first case, the coalition structure maintains the current status; thus, the number of revisited structures is limited. For the second case, the number of the coalition structures is also finite, and according to [23], it is no more than the Bell number, that is, the number of the set partitions. Consequently, in both of the two cases, the proposed algorithm always terminates and converges to final coalition structure π
N
f.Proposition 3.
Any stable coalition structureπ
N
f formed in the end is Nash-stable.Proof.
This proposition can be proved by the contradiction. We assume that the final coalition structureπ
N
f is not Nash-stable. Hence, there exist RRH i
∈
N and coalition S
∈
π
N
f so that S
∪
{
i
}
≻
i
S
c for S
c
∈
π
N
f. Then, RRH i will perform a hedonic shift action and therefore π
N
f will also change. Consequently, this contradicts the assumption that π
N
f is the final structure of the proposed algorithm.


## 4. Simulation and Analysis

For coalition formation simulation, we consider a single circular area covered by MBS with radiusR. There are N RRHs randomly distributed within the coverage of the MBS, and the radius of each RRH is set as 20 m. We assume that each RRH serves M UEs at the same time on the orthogonal subcarriers and each UE occupies 10 MHz bandwidth. Furthermore, it is assumed that each RRH in the same coalition occupies the same duration in a time frame; that is, for any coalition S
∈
π
N and every RRH i
∈
S, α
i
k
=
1
/
S. The transmission power of each RRH to its served UE p
i
k is 30 dBm and the interference from MBS is set as −30 dBm. The transmissions are affected by distance dependent path loss shadowing according to the 3GPP specifications [24], and the path loss is based on the BeFemto model. To lower the variations of the random variables, 2000 rounds simulations are conducted for different numbers of RRHs.To improve the clarity, the values of key simulation parameters are summarized in Table1.Table 1
Simulation parameters.
Parameter
Value
MBS radiusR
50 m
Number of RRHsN
8
RRH radius
20 m
Number of UEsM
2
Duration in a time frameα
i
k
1
/
|
S
|
RRH transmit powerp
i
k
30 dBm
Simulation rounds
2000
⁢Path loss model PL (dB): 18.7 × log10(d) + 46.8 + 20 × log10(2.7/5)In Figure3, we show a snapshot of Cloud-RAN partition resulting from the coalition formation algorithm with N
=
8 RRHs which are randomly deployed within the MBS coverage. With the convergence of the proposed algorithm, all RRHs organize into the resulting coalition structure, as shown in Figure 3. At first, all RRHs work without cooperating with others. Hence, the initial coalition structure can be described as π
N
0
=
{
{
1
}
,
{
2
}
,
…
,
{
8
}
}, where each element in π
N
0 denotes one RRH at the beginning time. Then, in the process of iteration, each individual RRH is looking for other RRHs or coalitions to join for higher payoff. As discussed previously, ultradense network inevitably results in more serious cochannel interference. However, the closer distance also increases the probability of cooperative transmission. Therefore, the proposed coalition formation algorithm is aimed at figuring out that whether the additional gain benefiting from the cooperation is greater than the total noise. Due to the remote distance from others, RRH 4 exists as a singleton coalition. On the other hand, RRH 5 and RRH 6 (or RRH 7 and RRH 8) prefer to form a coalition for higher spectrum efficiency rather than be a singleton, since the severe mutual interference can be suppressed by transmitting cooperatively. In the end, after a finite iteration, as shown in Figure 3, the final coalition structure consisting of two coalitions with two RRHs and four singleton coalitions is acquired, so the final partition can be described as π
N
f
=
{
{
1
}
,
…
,
{
4
}
,
{
5,6
}
,
{
7,8
}
}.Figure 3
A snapshot example of the final coalition structure.Figure4 shows that no matter which method is adopted, the system utility gets higher with the number of the RRHs increasing. Obviously, the coalition formation game based algorithm significantly achieves more payoff than the noncooperative approach because the intercell interference can be suppressed in the same coalition and the higher spectrum efficiency can be obtained due to the additional power via cooperative transmission. Moreover, we can see that the more the number of RRHs is, the better the performance of the proposed algorithm can be, comparing with the noncooperative method. Since it is urgent for RRHs to form a coalition under the circumstance of the ultradensely deployed network. The curves in Figure 4 have similar trend to logarithmic function. With the deployed RRHs increasing, the performance of the whole system can get improved. If the system utility is invariant or decreased, the ultradense deployment network shall not be proposed as one of the potential technologies for future wireless communication. Furthermore, the calculation of the system utility correlates with formula (6) and the path loss model in Table 1. We can see that both two formulas are in the form of logarithm, and all the operations in the proposed algorithm follow the logarithmic characteristics. Consequently, the performance curves in Figure 4 have the similar increasing trend with the logarithm function. Specifically, when the number of RRHs is 20, the system utility in terms of spectrum efficiency can be improved by 11.7% due to the coalitional game based cooperative transmission.Figure 4
System utility versus number of RRHsN.In Figure5, we can see that the average payoff of RRH decreases with the increase of the RRH numbers, which can be easily obtained from Figure 4 according to the characteristic of the logarithmic function. Even though increasing the number of RRHs can improve the system utility as shown in Figure 4, the total mutual interference among RRHs can be also severer. Specifically, the newly deployed RRH will generate the cochannel interference which deteriorates the utility of all the UEs served by other RRHs. Then, comparing with the noncooperative approach, the coalition game based cooperative approach shows indistinctive superiority when the network is sparse. However, with the densification of the deployment for RRHs, the proposed algorithm shows that each RRH can acquire more payoff than the noncooperative method, which indicates that the spectrum efficiency can be improved through the cooperative transmission among RRHs.Figure 5
Average utility versus number of RRHsN.From Figure6, we can see that both average coalition size and average maximum coalition size get larger with the increase of RRHs numbers N. When the network is sparse, the RRH has no incentive to cooperate with other RRHs, since the path loss is large enough and mutual interference can be neglected. As the number of RRH increases, the probability of coalition formation is increased. The reason is that the network densification makes the distance among the RRHs closer, which improves the opportunity for several RRHs to transmit cooperatively. Moreover, the average maximum coalition size increases much faster, while the average coalition size keeps growing slowly. With the densification of the network, the bigger coalition is formed to eliminate the severer interference. Specifically, for the number of RRHs N
=
20, the average coalition size and average maximum coalition size reach to 1.3 and 3.1, respectively. Therefore, the final coalition structure is mainly composed of medium-sized coalitions with the occasional emergence of large coalitions between the RRHs.Figure 6
Coalition size versus number of RRHsN.In Figure7, for both the proposed algorithm and the noncooperative method, the system utility gets increased when the MBS coverage radius becomes larger, since the intercell interference power can be much less due to the path loss resulting from the larger distance among the RRHs within a larger MBS coverage. We can see that the proposed algorithm always creates more system utility than the noncooperative method. However, with the increase of the MBS coverage radius, the performance of the noncooperative approach is gradually close to that of coalitional game based method. Because the total interference power is low enough and the RRHs prefer to work in noncooperative way rather than form a coalition in the case of low dense deployment. Specifically, the proposed coalition formation game based algorithm can show better advantage in dense network. Furthermore, for a given number of RRHs N, the system utility will not increase infinitely when the coverage radius is very large. So the mutual interference can be neglected in a sparse enough network.Figure 7
System utility versus MBS coverage radius (N
=
10).Then, the comparison between the proposed coalition formation algorithm (CFA) and the exhaustive search method in terms of the number of iterations is presented in Table2. According to the Bell number [23], we can see that the exhaustive search method is impractical since the number of the possible coalition structures increases exponentially with the total number of RRHs N. Hence, it is computationally complex for the ultradense network. As for the proposed CFA, the history variable is introduced to avoid joining the same coalition for RRHs. Furthermore, both player’s payoff and coalition’s utility are taken into account, which extremely decreases the iteration time and greatly improves the spectrum efficiency.Table 2
Comparison of the number of iterations.
Algorithms
⁢RRHs
5
10
15
20
The proposed CFA
28
166
431
779
Exhaustive search
52
115975
1.38 × 109
5.17 × 1013Finally, we give the theoretical analysis in terms of the overhead for information exchange when coalition formation algorithm is performed. In existing work [15], the authors proposed a recursive core approach, where each cooperating FAP needs to broadcast its data to all the other members in the coalition. In such a case, the total cost to form a coalition is the sum of power required by each FAP; that is,(14)
P
c
S
=
∑
i
∈
S
P
j
,
i
,where P
j
,
i denotes the power spent by FAP i to reach farthest FAP j in coalition S.Different from the recursive core approach, the proposed algorithm in this paper is achieved by the iterative method. So, the total consumption is determined by the number of the iterations. In conventional network, where the computational ability of FAPs is distributed, the power consumption spent by FAPs to exchange information should be considered. According to the proposed algorithm, at the beginning, there areN atomic coalitions randomly distributed in the network. Hence, it is necessary for given FAPs to exchange information with remaining N
-
1 coalitions. We use P
x to denote the power consumption of each information exchange. Consequently, for the first iteration, the cost can be written as (
N
-
1
)
P
x. It is easy to deduce that, for a network deployed with N FAPs without any coalition formed, the total power consumption is N
(
N
-
1
)
P
x. In practice, from Table 2, we can see that the average number of iterations in simulation is greater than N
(
N
-
1
), which means more power is consumed to converge to a stable coalition structure.In this paper, within the novel architecture of Cloud-RAN, the proposed algorithm is running in the centralized BBU pool where all data of RRHs is stored, and the necessary information for forming a coalition can be exchanged and calculated in the cloud. Therefore, the substantial power consumption in terms of broadcasting at information exchange can be saved according to the above theoretical analysis.


## 5. Conclusion and Future Work

Although the Cloud-RAN with densely deployed RRHs is regarded as an effective way to increase the capacity and to achieve high data rate, the severer mutual interference is introduced. In this paper, we propose a novel and efficient cooperation method based on coalition formation game where RRHs can be self-organized to negotiate with each other for reducing the mutual interference and thus improve the spectrum efficiency. Once a coalition is formed, the hybrid multiple access mode can be implemented by a coalition-level scheduler within it. The proposed algorithm shows a great performance compared to the noncooperative method, since the coalition utility and individual payoff are both considered. Based on the achievement in this paper, more further research such as the search for global optimum coalition structure while considering the algorithm efficiency will be conducted in the future.



---

*Source: 3068732-2016-07-18.xml*