# Interference Management Algorithm Based on Coalitional Game for Energy-Harvesting Small Cells.

1. IntroductionThe two-layer cellular heterogeneous network consisting of small cells and macro base stations [1] can improve the quality of service in the hotspot area and make up the blind spot area not covered by the macro base station, which has become the research hotspot of 5G. Although the introduction of small cells can expand the coverage area of the network and increase the total capacity of the system, the intensive deployment of small cells in cellular heterogeneous networks also brings some new problems and challenges. For example, spectral multiplexing may result in cross-tier and co-tier interference in the cellular heterogeneous network [2]. In addition, dense deployment of small cells will also increase the burden of power supply, so we can consider the energy harvesting technology [3] for power supply to facilitate the deployment of small cells to promote the sustainable development of cellular heterogeneous networks.

The interference management of small cell network can be broadly divided into two types of non-cooperation and cooperation. The main consideration of the non-cooperative interference management scheme is to enhance the performance of each small cell through the power control and resource allocation of small cells. In [4], an adaptive graph coloring method is proposed to allocate resources among the femtocells to achieve the purpose of interference management to ensure the fairness of users. In [5], a non-cooperative interference coordination game (ICG) is proposed. The ICG is divided into two games: resource block allocation (RBAG) and power allocation (PAG). RBAG is used to allocate RB resources to avoid interference, and then PAG is used to reduce interference and increase the system efficiency. In the non-cooperative scenario, small cells ignore the adverse effect of the co-tier interference to other small cells, only concerned about their own performance. However, the cooperative interference management scheme can not only reduce the co-tier interference, but also enhance the performance of the small cell network. In [6], the problem of traffic offloading is modeled as a local cooperative game and a distributed iterative learning algorithm is proposed to find the optimal Nash equilibrium point. In [7], the authors present a double auction method based on overlapping coalition game to solve the buyer's multiple needs and economic efficiency and other issues. In [8], the problem of spectrum sharing and interference management in ultra-dense C-RANS is modeled as a local coalition game. To obtain a stable partition, the authors also propose a distributed coalition formation algorithm. Besides, in some existing works, there are some ideas using the clustering techniques that are similar to the coalitional game. In [9], a hierarchical resource allocation approach is presented to mitigate the interference. Firstly, the SAPs are divided into a number of disjoint clusters, and sub-channel allocation is performed in clusters. Then a distributed learning mechanism is proposed to solve the interference between clusters. Finally, the system performance is enhanced by a power adaptive regulation mode. In [10], the authors present a game based on interference separation clustering, which divides small base stations into multiple groups and effectively reduces inter-cluster interference by coordination. From [9] and [10], we can see that there are still some differences between the clustering techniques and the coalitional game. In clustering techniques, the interference between the small base stations forming the cluster is more serious, and each cluster is used as an independent allocation unit for sub-channel allocation to reduce the interference. However, in the coalitional game, there is no interference in the coalition because the SBSs in the same coalition will adopt time sharing to carry out cooperative transmission. We need to find out the partition of coalition that can make the total rate of the system maximum.

Energy harvesting technology is a feasible and effective solution to the energy problem of small cells. The small base stations can collect the renewable energy from the environment for power supply. In [11], the authors propose an optimal cooperative mechanism for energy harvesting in 5G networks to maximize users' throughput under the constraints of data rates and energy harvesting efficiency. In [12], a downlink power control algorithm on account of stochastic game is presented. The energy collected from the environment by the small base stations satisfies random distribution, while the macro base stations still use the traditional energy source. The transmission rate of the small base station is maximized under the condition that the SNR of the macro user is ensured. In [13], a heuristic algorithm of joint power control and sleep-wake mechanism is proposed. Considering energy causality and battery capacity, the capacity of the network is maximized by using the renewable energy collected by the small cells. However, the algorithms in [12] and [13] both consider the optimization of the personal utility of the small cells, while ignoring the impact of the mutual interference between the small cells on the total performance of the system. In this paper, we combine the cooperative game problem with energy harvesting technology in the small cell network for the first time, and study the problem of interference management of small cells based on coalitional game with the aim of maximizing overall system utility.

According to the downlink energy-harvesting small cell network, the problem of cooperative interference management of small cells is established as a coalitional game model with transfer utility (TU). The small cells in the same coalition will adopt time sharing to carry out cooperative transmission. Based on the pre-defined utility function and transfer criteria, each small cell can play a game with others in order to achieve the maximum total system utility. The small cells start from the initial state of non-cooperation and eventually converge to a stable coalition structure. The main contributions of this paper are summarized as follows:

1) We set up a game model of coalition formation to maximize the total utility value of the system. In order to obtain the maximum system utility, the small cells can form the coalition through cooperation, and determine the time sharing strategy of the coalition according to the collected energy of each small cell. To lower the co-tier interference, the spectrum resource will be shared by the small cells in the same coalition according to the coalition's time sharing strategy.

2) We present a distributed coalition formation algorithm to solve the coalitional game model of energy-harvesting small cells and find the coalition structure and time sharing strategy which can make the total utility value of the system maximum. In the proposed algorithm, we first set up the transfer criteria of the small cells. Only when the three conditions are fulfilled simultaneously, such as increasing the personal utility, improving the utility of the new coalition after the transfer and improving the total utility of the system, can the small cells transfer between the coalitions. Each small cell forms the initialized coalition structure in a non-cooperative way, and then determines whether to join or leave the coalition in accordance with the transfer criteria. Finally, when all the small cells are no longer transferred, we can get a stable coalition structure, the optimal time sharing strategy and power allocation for small cells.

3) The performance of the proposed algorithm is analyzed. The algorithm starts from an initial coalition structure, and finally converges to a stable coalition structure with reasonable complexity. At the same time, the total utility value of the corresponding system is also the largest.

The rest part is organized as follows: Section 2 describes the system model of this paper. Section 3 builds a coalition formation game model of energy-harvesting small cells. Section 4 proposes a distributed coalition formation algorithm, and analyzes the performance of it. The experimental results and analysis are given in Section 5. Section 6 is a summary of this paper.

2. System Model

A downlink cellular heterogeneous network is shown in Fig. 1. This network is composed of a macro base station (MBS) and N small cell base stations (SBSs). Each user accesses the small cell base station in a closed manner. Let N = {1,..., N} denote all SBSs. It is assumed that each SBS i [member of] N serves one user [12], and let SUE i represents the user served by the SBS i [member of] N. The MBS uses the traditional power supply, and the SBSs harvest energy for power supply from renewable environmental resources, such as wind and solar energy. The energy collected by each SBS per unit time obeys a certain distribution. Let [E.sub.i] denote the energy collected per second by SBS i [member of] N.

In a non-cooperative scenario, each SBS i [member of] N always occupies the total transmission time on one sub-channel while transmitting data, so that each SUE is subject to the interference from other SBSs using the same sub-channel during transmission. Let [g.sub.i, j] denote the channel gain between SBS i and SUE j served by SBS j and [p.sub.i, j] denote the downlink transmission power from SBS i to SUE . The rate in non-cooperative case is thus defined as follows [14]:

[R.sub.i] = [log.sup.2](1 + [[p.sub.i,i][g.sub.i,i]]/[[[sigma].sup.2] + [I.sup.S.sub.i] + [I.sup.M.sub.i]]) (1)

where [[sigma].sup.2] is the variance of white Gaussian, [I.sup.M.sub.i] denotes the cross-tier interference between MBS and SUE i, and [I.sup.S.sub.i] represents the total co-tier interference received by SUE i, which can be defined as follows:

[I.sub.S] = [summation over (j[member of]N, j[not equal to]i)] [p.sub.j,i][g.sub.j,i] (2)

In addition, in this paper, because the energy collected by SBS i per unit time is [E.sub.i], the downlink transmission power [p.sub.i,i] of SBS i is equal to [E.sub.i].

Therefore, in the area where the SBSs are densely deployed, if the non-cooperative mode is used, the SBSs will have serious co-tier interference, thus affecting the rate of the SBSs [15]. Since the MBS and the SUEs are far apart and there is also wall-through loss between them, the downlink cross-tier interference is much smaller than co-tier interference between SBSs. In order to decrease the co-tier interference, this paper proposes a method of interference management based on the cooperation of SBSs and forming coalitions.

3. Construction of Coalition Formation Game Model

3.1 Mathematical Modeling

We can define a non-overlapping coalition as [S.sub.k] [16], where [S.sub.k] [??] N and is a non-empty subset that satisfies [mathematical expression not reproducible]. For any two coalitions [S.sub.k] and [S.sub.m] in the small cell network, we have [S.sub.k] [intersection] [S.sub.m] = [empty set] , k [not equal to] m . Assuming that N SBSs form a total of K coalitions, then the K coalitions form a coalition structure. The coalition structure can be denoted as CS, which is defined as a set CS = {[S.sub.1],..., [S.sub.K]}.

In the small cell network, the SBS is used as a player to participate in the coalitional game. When a coalition [S.sub.k] is formed, we can use a certain time sharing strategy [mathematical expression not reproducible] to carry out the cooperative transmission in the coalition. The energy collected by the SBSs in the coalition [S.sub.k] per unit time is defined as the energy harvesting strategy of the coalition, that is [mathematical expression not reproducible]. Since the coalition structure CS is an optimized variable in this paper, the total number of coalitions is a constantly changing value, and we can use |CS| instead of K to denote the number of coalitions within the coalition structure CS . Let [E.sub.CS] be a set of all energy harvesting strategies in the coalition structure CS, which is defined as [mathematical expression not reproducible]. The coalition's energy harvesting strategy [E.sub.CS] is known in this paper. The time sharing strategy [mathematical expression not reproducible] in the coalition is related to the energy harvesting strategy [mathematical expression not reproducible] of the coalition.

The time sharing strategy of coalition Sk can be defined as follows:

[mathematical expression not reproducible]

where [[alpha].sub.i] is the proportion of the transmission time of SBS i in the total transmission time of coalition [S.sub.k] and the size of [[alpha].sub.i] depends on how much energy the SBS collects. The more energy [E.sub.i], the greater the proportion of the transmission time of the SBS i in the total transmission time within the coalition, and vice versa. Therefore, [[alpha].sub.i] should be set to satisfy:

[mathematical expression not reproducible] (4)

[[alpha].sub.i] [member of] (0, 1], [for all]i [member of] [S.sub.k] (5)

[summation over (i[member of][S.sub.k][[alpha].sub.i] = 1 (6)

Thus, in the same coalition, the same sub-channel can be shared by multiple SBSs, that is, we are able to separate the downlink transmission from each SBS to its SUE in time. Within a certain time in the same coalition, there will be only one SBS occupying the resources, which can effectively reduce the interference within the coalition [S.ub.k]. However, SUEs are still affected by the co-tier interference from the downlink transmission of other coalition's SBSs due to the interference between the different coalitions, although they are not subject to interference from other SBSs in the same coalition.

While the cooperation between SBSs can bring effective performance gain, but also bring a certain coordination costs. SBSs through information exchange to conduct negotiate cooperation and form coalitions. The interactive information includes location information, SINR, time sharing strategy, synchronization timing information and so on, which is the overhead of forming the coalition. Meanwhile, the information exchange will inevitably lead to power loss, we will focus on the power consumed by the information exchange in order to form the coalition. In coalition [S.sub.k], each SBS i [member of][S.sub.k] broadcasts its own signals to interchange with other SBSs in the same coalition. We must ensure that each SBS can transmit information to the SBS that is farthest from it in the same coalition. Assuming that there is no errors in the entire information exchange process. The power cost of forming a coalition [S.sub.k] is given by:

[mathematical expression not reproducible] (7)

where [p.sub.i,j*], is the power consumed by the SBS i [member of] [S.sub.k] when SBS i [member of] [S.sub.k] broadcasts its own signals to SBS j * [member of] [S.sub.k] that is farthest from it and SBS j * [member of] [S.sub.k] just reaches the requirement of SNR threshold. Let [[gamma].sub.0] denote the SNR threshold of SBS j * [member of] [S.sub.k]. We assume that the noise power at the receiving end of the SBS is the same as that of the user, and define [p.sub.i, j*], as follows [17]:

[p.sub.i, j*] = [[[gamma].sub.0][[sigma].sup.2]]/[g.sub.i, j*] (8)

It can be seen from (7) and (8) that the power cost of forming the coalition is related to the distribution of the SBSs in the coalition. With the distribution more extensive, the corresponding power cost will increase. In addition, the power cost is also associated with the size of the number of members within the coalition. The larger the size of the coalition, the greater the power cost. We define the maximal power cost that the coalition can tolerate as [P.sup.lim.sub.S] [ 18] and the power cost of forming a coalition [S.sub.k] as [mathematical expression not reproducible]. If [mathematical expression not reproducible] satisfies [mathematical expression not reproducible], the coalition is not allowed to form, whereas [mathematical expression not reproducible] allows the formation of the coalition.

From above discussion, we can conclude that in the case of SBSs cooperating with each other, if the coalitional cooperation method is adopted, the reachable rate of SUE i served by each SBS i [member of] [S.sub.k] is given by:

[mathematical expression not reproducible] (9)

where [I.sup.MO.sub.I] represents the cross-tier interference between MBS and SUE i, [[GAMMA].sub.CS] denotes a collection of time sharing strategies for all coalitions under the coalition structure CS and can be defined as [mathematical expression not reproducible], and [I.sub.i]([S.sub.k], CS, [[GAMMA].sub.CS]) denotes the total co-tier interference received by the SUE i in the coalition [S.sub.k] from SBSs in other coalitions, as

[I.sub.i]([S.sub.k], CS, [[GAMMA].sub.CS]) = [summation over (j[member of]CS\[S.sub.k], j[not equal to]i])] [p.sub.j,i][g.sub.j,i] (10)

Assume that the total transmission time in coalition [S.sub.k] is 1 second, so the transmission time of SBS i [member of] [S.sub.k] is [[alpha].sub.i] second. The initial transmit power of each SBS i [member of] [S.sub.k] is [p.sub.i,i] = [E.sub.i]/[[alpha].sub.i] since the energy [E.sub.i] is used up within [[alpha].sub.i] [member of] (0, 1] second, and the actual transmit power is the initial transmit power minus the power cost [p.sub.i, j*] of each SBS i [member of] [S.sub.k]. Thus, the reachable rate of SUE i served by each SBS i [member of] [S.sub.k] is given by:

[mathematical expression not reproducible] (11)

3.2 Establishment of Optimization Problem

We use the coalition formation game with TU to model the cooperation problem of the small cell network. All the SBSs in N are regarded as the players of the game. We define the coalition formation game with transfer utility as G = (N, v) where N represents all players, that is, a collection of SBSs, and v denotes the utility value for each coalition. The utility value of the coalition [S.sub.k] can be expressed as the sum of the reachable rates of all SBSs in [S.sub.k] , which can be given by:

[mathematical expression not reproducible] (12)

where v([empty set], CS, [[GAMMA].sub.CS]) = 0.

In this model, intra-coalition interference is negligible and the performance of SBSs participating in the game is influenced by other coalitions. Hence, the utility value of any coalition [S.sub.k] [member of] CS lies not only on the SBSs in the coalition [S.sub.k] , but also on the coalition structure CS, time sharing strategy [[GAMMA].sub.CS] and energy harvesting strategy [E.sub.CS].

The utility value of SBS i [member of] [S.sub.k] in the coalition [S.sub.k] , which is defined as its reachable transmission rate in the coalition [S.sub.k], can be defined as follows:

[x.sub.i]([S.sub.k],CS, [[GAMMA].sub.CS]) = [[alpha].sub.i][log.sub.2](1 + [([E.sub.i]/[[alpha].sub.i] - [P.sub.i,j*])[g.sub.i,i]]/[[[sigma].sup.2] + [I.sup.MO.sub.i] + [I.sub.i](S.sub.k, CS, [[GAMMA].sub.CS])]) (13)

According to (12), the utility value of the coalition [S.sub.k] [member of] CS is:

[mathematical expression not reproducible] (14)

where u ([S.sub.k], CS, [[GAMMA].sub.CS]) is:

[mathematical expression not reproducible] (15)

The total system utility value of the coalition formation game G = (N, v) under the coalition structure CS, time sharing strategy [[GAMMA].sub.CS] and energy harvesting strategy [E.sub.CS] is superposed by the utility values of all coalitions, and is also equal to the sum rate of all the SBSs in N , which can be defined as follows:

[mathematical expression not reproducible] (16)

The optimization goal of this paper is to find the coalition structure and time sharing strategy which could make the total utility value of the system maximum under certain constraints, that is, the optimal solution of coalition formation game G= (N,v). The optimization model is established as follows:

max v(CS, [[GAMMA].sub.CS]) (17a)

[mathematical expression not reproducible] (17b)

[[alpha].sub.i] = [E.sub.i]/[summation over (j[member of][S.sub.k])][E.sub.j] [member of] (0, 1], [for all]i [member of] [S.sub.k], [for all][S.sub.k] [member of] CS (17c)

[summation over (j[member of][S.sub.k])][[alpha].sub.i] = 1, [for all][S.sub.k] [member of] CS (17d)

[p.sub.i,j*] = [[gamma].sub.0][[sigma].sup.2]/[g.sub.i,j*], [for all]i, J* [member of] [S.sub.k], j* [not equal to]i, [for all][S.sub.k] [member of] CS (17e)

[E.sub.i]/[[alpha].sub.i] [greater than or equal to] [p.sub.i,j*], [for all]i, j* [member of] [S.sub.k], j* [not equal to] i, [for all][S.sub.k] [member of] CS (17f)

where (17a) indicates that the optimization goal of this paper is the biggest utility value of the system and the coalition structure CS and time sharing strategy [[GAMMA].sub.CS] that make the total system utility maximum. (17b) indicates that the power cost required to form the coalition cannot be greater than the maximum power cost [P.sup.lim.sub.S] that the coalition can tolerate. (17c) and (17d) represent the formation of a time sharing strategy within a coalition and the constraints that the strategy needs to satisfy. (17e) represents the minimum value of the required transmit power for the SBS i [member of] [S.sub.k] when SBS i broadcasts the information to the SBS j * [member of] [S.sub.k] that is farthest from it and SBS j* just satisfies the SNR threshold requirement, and (17f) indicates that the average transmission power of the SBS i [member of] [S.sub.k] is not less than the minimum value of the required transmission power.

4. Distributed coalition Formation Algorithm

According to the mathematical model established in the previous section, we can see that the solution of the optimization model is a stable coalition structure CS (.) that makes the total utility value of the system maximum. At the same time, in the iterative process of the algorithm, the members of the coalition are constantly changing, so the time sharing strategy of the coalition is also changing. When the algorithm finally converges to the stable coalition structure CS*, the corresponding optimal time sharing strategy [[GAMMA].sub.CS]* will be obtained. It can be seen that the average transmit power [E.sub.i]/[[alpha].sub.i] of each SBS i [member of] [S.sub.k] is constantly changing in the iterative process of the algorithm, and it is not fixed, and will eventually achieve an optimal power distribution.

At the beginning, the SBSs transmit resources in a non-cooperative way. When the SBS finds that cooperation with another SBS can enhance its own utility value and the system's total utility value, it will choose to form a coalition with that SBS. Each SBS will determine whether or not to join or leave a coalition in accordance with such criteria, in order to obtain the utility value gain. Finally, when all SBSs can no longer able to obtain an increase in system utility by moving from one coalition to another, the coalition structure is stable.

4.1 Transfer Criteria

In order to be able to compare the two kinds of coalition structure, we must set the appropriate judgment criteria. There are two kinds of judgment criteria: individual utility criterion and coalition utility criterion. The individual utility criterion is that when the two coalition structures are compared in the game, only the utility of the individual is improved, and the coalition utility criterion is considered to improve the coalition utility. In the algorithm proposed in this paper, to compare the two kinds of coalition structure, we should consider the improvement of the two kinds of utility and can make use of the distributed method to increase the total utility of the system.

We assume that there is a coalition structure CS = {[S.sub.1],..., [S.sub.a], [S.sub.b],... [S.sub.K]}. If SBS i [member of] [S.sub.a] is to move from the coalition [S.sub.a] to [S.sub.b], meanwhile, the coalition structure changes from CS = {[S.sub.1],..., [S.sub.a], [S.sub.1],... [S.sub.K]} to CS' = {CS\{[S.sub.a], [S.sub.b]}}[union]{{i}}[union]{[S.sub.b] [union] {i}}, the following transfer criteria [??] must be met:

[mathematical expression not reproducible] (18)

The transfer criteria [??] state that the SBS must meet three criteria to transfer from one coalition to another, namely:

1) The individual utility value of the SBS after the transfer to another coalition must be greater than that before the transfer;

2) After the addition of the SBS to another coalition, the utility value of the newly formed coalition could not be less than that of the original coalition;

3) The total utility value of the system under the newly formed coalition structure after the transfer of the SBS must be larger than that of the original system.

In addition to the above transfer criteria, another rule needs to be satisfied in order to determine whether the SBS joins other coalitions. We can define a history set H(i) for the SBS i , which contains all the coalitions that the SBS i has joined. After the SBS i satisfies the transfer criteria, it is also necessary to ensure that the coalition to join is not in the history set H(i) in order to transfer successfully. To ensure convergence of the algorithm, when SBS i has successfully transferred to another coalition, we should add the coalition into the history set H(i), so that any SBS could not be repeated to join the same coalition.

4.2 Coalition Formation Algorithm

As shown in Algorithm 1, this paper presents a new distributed coalition formation algorithm combined with energy harvesting of the small cells. Firstly, all the SBSs in N collect energy from the environment, and form an initialized coalition structure in a non-cooperative manner. Then, the SBSs will find all existing coalitions and determine whether to join or leave the coalition according to the transfer criteria and history set. After the completion of each transfer, the overall system utility will be improved, while the coalition structure will be changed. The change of the membership in the coalition will cause the coalition's time sharing strategy to change, so the transmission time of the SBS in the coalition changes accordingly, and the transmitting power of the SBS also changes accordingly. Finally, when all the SBSs are no longer transferred, a stable coalition structure is formed, and the optimal time sharing strategy and power allocation for the SBSs are also obtained. Once the coalition structure is stable, the SBSs in the same coalition will use a certain time sharing mode to carry out cooperative transmission.

Algorithm 1. Distributed algorithm for coalition formation based on energy-harvesting small cells 1: Initial State: CS = {{1}, {2},...,{N}} 2: for all SBS i e N do 3: [E.sub.i] [member of] (0, [E.sup.max]] 4: H(i) = [empty set] 5: end for 6: while CS' [not equal to] CS* do 7: for all SBS i [member of] N do 8: Each SBS finds the existing coalitions and collects relevant information 9: Compute the power cost [mathematical expression not reproducible] required to join each coalition for SBS i , each SBS sorts all the possible coalitions which fulfill [mathematical expression not reproducible] 10: if it satisfies transfer criteria [??] in (18) after SBS i switches to these possible coalitions which are not in the history set H(i) then 11: Record these coalitions and the total system utilities v(CS', [[GAMMA].sub.CS]') after SBS i joins these coalitions 12: end if 13: SBS i chooses the coalition which ensures the maximum total system utility to join 14: Update the history set H(i) by putting the new coalition into it and the coalitional structure to CS 15: end for 16: end while 17: The cooperative transmission between SBSs is carried out by using the time sharing strategy in each coalition [S.sub.k]

Through the proposed algorithm, we learn that, each time the SBS is transferred, it can not only increase the individual utility value of each SBS and the total utility value of the system, but also do no harm to the individual utility of other SBSs in the newly formed coalition.

4.3 Performance Analysis of the Algorithm

Theorem 1: The coalition formation game G = (N, v) of small cells based on energy harvesting finally reaches convergence.

Proof: First, since the number of all SBSs is given, only a finite number of non-overlapping coalitions are possible, and the number of coalition structures is limited. The proof of the finite number of coalitions is as follows:

We will divide N SBSs into K (|CS| = K ) non-empty coalitions. A partition corresponds to a coalition structure. The number of possible coalition structures can be expressed as [19]:

[mathematical expression not reproducible] (19)

where S(N,1) = 1, S(N, N) = 1 and S(N, K) = 0, [for all]K > N or K < 1.

Since the range of K is [1, N], we can use the Bell number to represent the number of all possible coalition structures:

B( N) = [N.summation over (K=1)] S(N, K) (20)

According to the knowledge of probability theory, the probability of dividing N SBSs into K coalitions, that is, the probability of |CS| = K is defined as follows:

P(|CS| = K) = S(N, K)/B(N) (21)

Thus, the average number of coalitions within the coalition structure CS is:

[mathematical expression not reproducible] (22)

According to the relational expression S (N +1, K) = S (N, K - 1) + KS (N, K) [20], we can get that

[mathematical expression not reproducible] (23)

From (22) and (23), we can have

|[bar.CS]| = [B(N+1)]/B(N) - 1 (24)

According to (24), the number of coalitions is limited, and the number of coalitions that meet the transfer criteria in (18) is also finite, so the number of coalition structures is bound to be limited. In addition, the algorithm proposed in this paper also introduces the history set H(i) to prevent the phenomenon of dead cycle. In the algorithm of this paper, we will find a coalition structure that makes the total system utility maximum in a limited number of coalition structures, so the result must be convergent. In summary, the coalition formation game will eventually converge to a certain coalition structure.

Proposition 1: In the case of the given transfer criteria [??], the coalition structure CS* formed by the distributed coalition formation algorithm based on energy harvesting is stable.

Proof: The proposition can be proved by the reduction to absurdity. Assuming that the coalition structure CS (.) formed by the distributed coalition formation algorithm based on energy harvesting is ultimately unstable, there must be some SBSs which can turn the existing coalition structure CS (.) into another coalition structure CS by leaving or joining a coalition, for the improvement of the total system utility. But this is contradictory to the conclusion in Theorem 1 that the algorithm proposed in this paper will converge at the end.

Therefore, the coalition structure CS*must be stable.

Proposition 2: The complexity of the proposed algorithm is O(|[bar.CS]|) , which is more reasonable.

Proof: The complexity of the proposed algorithm is mainly related to the number of coalitions under the coalition structure CS . The worst case is when the N SBSs are in a non-cooperative state, at this time the number of coalitions up to N and the complexity is approximately O(N). When the SBSs began to form coalitions, the number of coalitions will decline, so the complexity of the proposed algorithm will be reduced. According to (24), the average number of coalitions in the proposed algorithm is |[bar.CS]| = B(N + 1)/B(N) - 1 < N, thus the complexity of the algorithm can be approximately expressed as O(|[bar.CS]|) < O(N). In addition, under the constraint of transfer criteria [??], history set and maximum power cost [P.sup.lim.sub.S], the number of iterations of the proposed algorithm is also limited. Therefore, the complexity of the proposed algorithm is not too high, and more reasonable.

5. Simulations and Analysis of Algorithm

This section considers a downlink transmission scenario consisting of one MBS and N SBSs. The simulation parameters are shown in Table 1. N SBSs are randomly deployed in a circle of radius R with the MBS as the center. The energy harvested by the SBS from the surrounding environment per unit time obeys the uniform distribution in the range (0, [E.sup.max]], and the coverage radius of the SBS is 20m. In the simulation scenario of this paper, we neglect the impact of the wall loss on the signal transmission. The path loss model is given by [18]:

PL(dB) = 18.7 x [log.sub.10](d) + 46.8 + 20 x [log.sub.10] (2.7 / 5) (25)

Fig. 2.1 maps an initial network topology. The downlink cellular heterogeneous network is composed of one MBS and N = 8 SBSs. All the SBSs form an initialized coalition structure in a non-cooperative manner. Fig. 2.2 shows a stable coalition structure obtained by the proposed algorithm. As can be seen from the figure, there are five coalitions. The Coalition1 contains only SBS2, the Coalition2 contains only SBS1 and the Coalition3 contains only SBS4. These three SBSs are far away from other SBSs, so they are less disturbed by the interference and do not form the coalition with other SBSs. The Coalition4 is composed of SBS3, SBS5 and SBS6. Due to the relatively dense deployment of SBS3, SBS5 and SBS6, their formation of the coalition is more conducive to reducing interference and improving system performance. Similarly, SBS7 and SBS8 also constitute Coalition5. According to Fig. 2.1 and Fig. 2.2, we can see that the proposed algorithm can converge to a stable coalition structure.

Fig. 3 depicts the relationship between the number of iterations required to achieve convergence and the total utility of the system when the radius of the randomly distributed region of the SBSs is 200m. The proposed algorithm can converge quickly as shown in Fig. 3. We denote N as the number of randomly distributed SBSs in the network. After several simulations to get the average value, the proposed algorithm needs to iterate about 2.22 times to achieve convergence when the number of SBSs is N = 10, iterate about 7.03 times when N = 20 and 11.31 times when N = 30 . It is indicated that that when the number of SBSs is more, the iterations required to form a stable coalition structure between SBSs is more and the complexity of the algorithm is higher. Because of the increase in the number of SBSs, each SBS needs to negotiate with more coalitions and use the transfer criteria to determine whether to join or leave a coalition, thus increasing the difficulty of the implementation of the algorithm. In addition, we can also find that with the increase of the times of iterations, the total utility of the system increases gradually, and it will not change after reaching a stable value. This trend reflects the whole process of coalitional game. First, each SBS plays game with other SBSs to seek the coalition structure that makes the total utility of the system bigger. Eventually, the game converges to a stable coalition structure that makes the total utility value of the system maximum.

Fig. 4 illustrates the relationship between the number of SBSs and the total system utility value under different radius of the distribution area in the proposed algorithm and non-cooperative algorithm. It can be seen that the algorithm in this paper is superior to the non-cooperative algorithm when the distribution area radius R = 100m and R = 200m . This is because in the case of non-cooperation, the SBSs will pay more attention to the improvement of their own utility without considering the serious interference to other SBSs when their own utility is improved. In this condition, the overall performance of the small cell network will be greatly affected, resulting in the reduction of the total utility value of the system. In this paper, the method based on coalitional cooperation is to form the coalitions between the SBSs through negotiation and game. The proposed algorithm improves the overall utility value of the system while ensuring the utility of the SBS itself, and pays more attention to the improvement of the overall performance, which is superior to the non-cooperative mode. Besides, it can be seen from the Fig. 4, with the growth of the quantity of SBSs, the difference between the proposed algorithm and non-cooperative algorithm is more and more obvious. In the case of the SBSs' distribution range is R = 100m, the performance gain of the proposed algorithm is 28.30% compared to the non-cooperative algorithm when N = 20 , and the performance gain is 42.24% when N = 50. When the SBS numbers are growing, co-tier interference of the small cell network will become more and more serious, so the SBSs are more willing to lower the mutual interference and enhance the overall performance of the network by forming coalitions. Thus, with the increase of SBSs, the performance gain of the proposed algorithm is more obvious. However, when the number of SBSs grows continuously, the upward trend of the overall system utility will slow down. This is because, a large number of SBSs will lead to the formation of more coalitions, and the interference between the coalitions still exists, which will affect the performance of the overall system.

Fig. 5 illustrates the relationship between total system utility value and distribution range of the SBSs under two different cases of the proposed algorithm and non-cooperative algorithm. It suggests that the performance of the algorithm based on coalitional game in this paper is still superior to non-cooperative algorithm. In addition, with the expansion of distribution range, the total system utility rises gradually. When the number of SBSs is constant, expanding the distribution range of SBSs can increase the distance between SBSs, thus effectively reducing the co-tier interference between the SBSs. Hence, the total utility of the system increases with the increase of the distribution range, both in this paper and non-cooperative algorithm. We can also see that the total utility of this algorithm is more and more close to that of the non-cooperative algorithm when the distribution range of the SBSs expands to a certain extent. This is because when the distribution range of the SBSs is wider, the interference between each other becomes weaker and the demand of forming coalitions is reduced. So the formation of the coalition is gradually reduced, this condition is getting closer and closer to non-cooperative situations.

Fig. 6 describes the complexity of the proposed algorithm. It can be seen that the algorithm's complexity is concerned with the quantity of SBSs and the distribution range of the SBSs. As the quantity of SBSs grows, the times of iterations required for convergence are increased. And when the number of SBSs is the same, the iterations required for the algorithm are more if the distribution range is smaller. This shows that when the distribution of SBSs in a region is relatively intensive, the probability of forming coalitions will increase, and the number of negotiation between SBSs will also increase, so the algorithm needs to be run more times to obtain a stable coalition structure.

6. Conclusion

In this paper, we study the interference management problem of energy-harvesting small cell network, and use the coalitional game model with transfer utility to solve this problem. First of all, we develop the time sharing strategy in the same coalition according to the size of the energy collected by the SBSs. At the same time, we define the utility function of the SBS, which is related to the structure of the coalition, the time sharing strategy and the energy harvesting strategy. Then we establish the optimization problem to maximize the total utility value of the system. To overcome this problem, we propose a distributed coalition formation algorithm, and determine the transfer criteria of the SBSs. Only after satisfying the three conditions specified in the transfer criteria can the SBSs join or leave the coalitions. Finally, we analyze the performance of the algorithm. It is proved that the algorithm converges to a stable coalition structure with reasonable complexity, and the corresponding total utility of the system is the largest. Experimental results indicate that the proposed algorithm converges quickly, and the system utility of the algorithm is superior to that of the non-cooperative algorithm when the SBSs are deployed intensively.

References

[1] S. Sun, K. Adachi, P. H. Tan and Y. Zhou, "Heterogeneous network: An evolutionary path to 5G," in Proc. of 21st Asia-Pacific Conference on Communications (APCC), pp. 174-178, October 14-16, 2015. Article (CrossRef Link)

[2] H. S. Dhillon, R. K. Ganti, F. Baccelli and J. G. Andrews, "Modeling and analysis of K-tier downlink heterogeneous cellular networks," IEEE Journal on Selected Areas in Communications, vol. 30, no. 3, pp. 550-560, April, 2012. Article (CrossRef Link)

[3] Y. Mao, Y. Luo, J. Zhang and K. B. Letaief, "Energy harvesting small cell networks: feasibility, deployment, and operation," IEEE Communications Magazine, vol. 53, no. 6, pp. 94-101, June, 2015. Article (CrossRef Link)

[4] A. R. Elsherif, W. P. Chen, A. Ito and Z Ding, "Adaptive resource allocation for interference management in small cell networks," IEEE Transactions on Communications, vol. 63, no. 6, pp. 2107-2125, June, 2015. Article (CrossRef Link)

[5] L. Liang, G. Feng, "A game-theoretic framework for interference coordination in OFDMA relay networks," IEEE Transactions on Vehicular Technology, vol. 61, no. 1, pp. 321-332, Jan., 2012. Article (CrossRef Link)

[6] H. Shao, Y. Sun, H. Zhao, W. Zhong and Y. Xu, "Locally cooperative traffic-offloading in multi-mode small cell networks via potential games," Transactions on Emerging Telecommunications Technologies, vol. 27, no. 7, pp. 968-981, July, 2016. Article (CrossRef Link)

[7] Y. Sun, Q. Wu, J. Wang, Y Xu and A. Anpalagan, "VERACITY: Overlapping coalition formation based double auction for heterogeneous demand and spectrum reusability," IEEE Journal on Selected Areas in Communications, vol. 34, no. 10, pp. 2690-2705, October, 2016. Article (CrossRef Link)

[8] Y. Sun, J. Wang, F. Sun and Z. Zhang, "Local altruistic coalition formation game for spectrum sharing and interference management in hyper-dense cloud-RANs," IET Communications, vol. 10, no. 15, pp. 1914-1921, October, 2016. Article (CrossRef Link)

[9] J. Qiu, G. Ding, Q. Wu and et al, "Hierarchical Resource Allocation Framework for Hyper-Dense Small Cell Networks," IEEE Access, vol. 4, no. 99, pp. 8657-8669, December, 2016. Article (CrossRef Link)

[10] J. Qiu, Q. Wu, Y. Xu, Y. Sun, and D. Wu, "Demand-aware resource allocation for ultra-dense small cell networks: an interference-separation clustering-based solution," Transactions on Emerging Telecommunications Technologies, vol. 27, no. 8, pp. 1071-1086, May, 2016. Article (CrossRef Link)

[11] H. Gao, W. Ejaz and M. Jo, "Cooperative wireless energy harvesting and spectrum sharing in 5G networks," IEEE Access, vol. 4, pp. 3647-3658, July, 2016. Article (CrossRef Link)

[12] T. K. Thuc, E. Hossain and H. Tabassum, "Downlink power control in two-tier cellular networks with energy-harvesting small cells as stochastic games," IEEE Transactions on Communications, vol. 63, no. 12, pp. 5267-5282, December, 2015. Article (CrossRef Link)

[13] C. Y. Chang, K. L. Ho, W. Liao and D. S. Shiu, "Capacity maximization of energy-harvesting small cells with dynamic sleep mode operation in heterogeneous networks," in Proc. of IEEE International Conference on Communications (ICC), pp. 2690-2694, June 10-14, 2014. Article (CrossRef Link)

[14] Z. Zhang, L. Song, Z. Han and W. Saad, "Coalitional games with overlapping coalitions for interference management in small cell networks," IEEE Transactions on Wireless Communications, vol. 13, no. 5, pp. 2659-2669, May, 2014. Article (CrossRef Link)

[15] T. Q. S. Quek, D. L. R. Guillaume, I. Gven and M. Kountouris, Small cell networks: deploymenS, PHY techniques, and resource management, Cambridge University Press, 2013. Article (CrossRef Link)

[16] W. Saad, Z. Han, M. Debbah and A Hjorungnes, "Coalitional games theory for communication networks," IEEE Signal Processing Magazine, vol. 26, no. 5, pp. 77-97, September, 2009. Article (CrossRef Link)

[17] Y. Shi, G. Zhu, S. Lin and S. Xu, "RSSI-based dynamic coalition formation for cooperative interference management in femtocell networks," in Proc. of International Wireless Communications & Mobile Computing Conference (IWCMC 2015), pp. 1400-1405, August 24-28, 2015. Article (CrossRef Link)

[18] Z. Zhang, L. Song, Z. Han and W. Saad, "Overlapping coalition formation games for cooperative interference management in small cell networks," in Proc. of IEEE Wireless Communications and Networking Conference (WCNC), pp. 643-648, April 7-10, 2013. Article (CrossRef Link)

[19] Z. Y. Xiong, Z. H. Xu, L. Zhang and S. P. Xiao, "Cluster analysis for the synthesis of subarrayed monopulse antennas," IEEE Transactions on Antennas & Propagation, vol. 62, no. 4, pp. 1738-1749, April, 2014. Article (CrossRef Link)

[20] A. J. Dobsona, "A note on stirling numbers of the second kind," Journal of Combinatorial Theory, vol. 5, no. 2, pp. 212-214, 1968. Article (CrossRef Link)

Jiamin Chen was born in Jiangsu Province, China, in 1993. She received the B.E. degree in Communication Engineering from Nanjing University of Posts and Telecommunications, Nanjing, in 2015. She is now pursuing master's degree in the Department of Telecommunication and Information Engineering, Nanjing University of Posts and Telecommunications. Her research interests include resource allocation in heterogeneous cellular networks, mobile communication and wireless technology.

Qi Zhu (corresponding author) was born in Suzhou, Jiangsu, China, in 1965. She received the M.S. degree in radio engineering from Nanjing University of Posts and Telecommunications in 1989. Now she is a professor in the Department of Telecommunication and Information Engineering, Nanjing University of Posts and Telecommunications, Jiangsu, China. Her research interests focus on technology of next generation communication, broadband wireless access, OFDM, channel and source coding, dynamic allocation of radio resources.

Su Zhao received a Bachelor of engineering degree in radio engineering from Nanjing University of Posts and Telecommunications in 1986, and received a master's degree in communication and information systems engineering from Beijing University of Posts and Telecommunications in 2005. Now she is associate professor of Nanjing University of Posts and Telecommunications and associate dean of the School of Communication and Information Engineering. Her research interests focus on multiple access technology, modulation and demodulation technology, MIMO technology, wireless resource dynamic allocation technology and mobile network optimization technology.

Jiamin Chen (1), Qi Zhu (1) and Su Zhao (1,2)

(1) The Key Wireless Laboratory of Jiangsu Province, School of Telecommunication and Information Engineering, Nanjing University of Posts and Telecommunications Nanjing 210003, Jiangsu - P. R. China

[e-mail: 1015010329@njupt.edu.cn; zhuqi@njupt.edu.cn]

(2) National Mobile Communications Research Laboratory, Southeast University Nanjing 210000, Jiangsu - P. R. China

[e-mail: zhaos@njupt.edu.cn]

(*) Corresponding author: Qi Zhu

Received February 17, 2017; revised May 4, 2017; accepted May 28, 2017; published September 30, 2017

This research has been supported by National Natural Science Foundation of China (No.61571234, No.61631020), National Basic Research Program of China (973 program: 2013CB329005) and the open research fund of National Mobile Communications Research Laboratory, Southeast University (No.2015D10).

doi.org/10.3837/tiis.2017.09.003

Table 1. Simulation parameters Simulation parameters Value Coverage radius of macrocell R 50-300m Coverage radius of small cell r 20m Channel bandwidth B 180kHz Number of SUE served by each small cell 1 Noise power [[sigma].sup.2] -104dBm SNR threshold [[gamma].sub.0] 6dB Maximum power cost that the coalition 100dBm tolerates [P.sup.lim.sub.S] Peak value of energy collected by SBS 0.1J per unit time [E.sup.max]

Printer friendly Cite/link Email Feedback | |

Author: | Chen, Jiamin; Zhu, Qi; Zhao, Su |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Sep 1, 2017 |

Words: | 7963 |

Previous Article: | A Secure and Efficient Cloud Resource Allocation Scheme with Trust Evaluation Mechanism Based on Combinatorial Double Auction. |

Next Article: | An Efficient Downlink MAC Protocol for Multi-User MIMO WLANs. |

Topics: |