# Coalitional Game Theory for Cooperative Interference Management in Femtocell Networks

Authors: Yuanyuan Shi; Gang Zhu; Siyu Lin; Jianwen Ding; Shengfeng Xu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Dense deployment of femtocells can cause serious intra-tier interference in femtocell networks. In this paper, a new cooperative interference management approach which allows the femtocell user equipment (FUE) to merge into cooperative groups, that is, coalitions, for the uplink transmissions in a femtocell network is proposed, so as to reduce the intra-tier interference and improve the system performance. Taking into account the power cost for cooperation, we claim that all the FUEs are impossible to merge together, and we formulate the proposed cooperative problem as a coalitional game in partition form with an externality due to the interference between the formed coalitions. To get the solution, a novel distributed coalition formation algorithm that takes advantage of the characteristics of femtocell network and allows the FUEs to interact and individually decide on which coalitions to participate in is proposed. Furthermore, we analyze the convergence and stability of the proposed algorithm. Simulations are conducted to illustrate the behavior and the performance of the proposed coalition formation algorithm among FUEs. Results show that the proposed algorithm can improve the system performance with much lower complexity than some previously proposed coalition formation algorithms.


---

## Body

## 1. Introduction

Femtocell networks have recently emerged as a key structure that shows promise in satisfying the demand for ubiquitous wireless access and higher data rates and have attracted a great attention from both academia [1] and standardization bodies such as 3GPP [2]. The basic idea of the femtocell network is to deploy plug-and-play, low power, low cost femtocell access points (FAPs) underlaying existing communication infrastructures [3, 4]. FAPs can be installed by the users or the service operators inside a home or an office and are able to connect to existing backhaul technologies through a local broadband connection [5, 6]. Subsequently, femtocells can offload traffic from the existing wireless systems (e.g., macrocell networks) and can significantly improve the spectrum efficiency and system capacity.Nevertheless, when FAPs are deployed in a very dense manner, if interference management and resource allocation are not properly designed, the intra-tier (i.e., femtocell to femtocell) interference can be very serious, consequently affecting the achievable data rate of each FUE and the overall system performance. A lot of recent work has studied the interference problem in the femtocell network. The current solutions can be divided into two categories: noncooperative and cooperative strategies. Noncooperative approaches include power control [7, 8], interference alignment [9], interference cancelation [10], interference avoidance [11], and fractional frequency reuse [12]. In [11], the authors point out that, based on combining frequency handover and power control, the outage probability can be reduced by an interference avoidance technique for noncooperative femtocells. In [13], a two-tier femtocell network is studied by using stochastic geometric theorem, and the success probability is derived for each tier when applying disjoint and joint spectrum allocation, respectively. Cognitive femtocells perceiving the locations of scheduled macrocell users are studied in [14], and an effective macro/femto throughput tradeoff is derived. In noncooperative schemes, each femtocell just pays attention to its own quality of service (QoS) and neglects overall system performance (e.g., sum-rate of the femtocell network) which is of great importance in large scale system deployment. Furthermore, most noncooperative interference management approaches such as fractional frequency reuse and power control need a centralized controller for allocating the resource in the networks, increasing the complexity of the network structure.To overcome this issue, cooperative methods based on the formation of the cooperative groups (i.e., coalitions) among the nodes in the femtocell network are proposed in [15–19]. The basic idea of coalition is based on the coalitional game theory [20], which aims at improving the whole utility of the game. In [15], downlink intra-tier interference is mitigated by using a game-theoretic approach. Reference [16] introduces a cooperative resource allocation algorithm for the downlink transmission system, without consideration of cost. Reference [19] proposes a cooperative model for downlink interference reduction using a cooperative game. The current schemes just focus on the downlink scenarios where FAPs can form coalitions by exchanging scheduling information through interface X2. However, such cooperative methods are not suitable for uplink scenarios, because there is no such interface for providing direct communication between any two FUEs. Besides, the current coalition formation algorithms neglect the characteristics of the networks. In fact, in a femtocell network, intra-tier interference in the uplink is often dominated by one or two FUEs located near the femtocell boundaries closest to FAP serving the desired signal. FUEs that suffered from the mutual interference have an incentive to mitigate the most serious interference with their closest interfering sources.In this paper, by applying the coalitional game theory, we propose a new approach to mitigate the interference in the uplink transmissions in the context of femtocell networks. Specifically, to mitigate uplink intra-tier interference and improve the system performance, the neighboring FUEs which are active on the same channel, have an incentive to cooperate with each other by forming coalitions. The FUEs in the same coalition exchange some useful information in a device-to-device (D2D) mode. Based on the success of information exchange, the FUEs within one coalition share the whole transmission time, and thus the intra-tier interference is avoided in that coalition. Furthermore, we model this cooperation problem as a coalitional game in partition form with an externality in terms of the interference among disjoint coalitions. To get the solution, we propose a new algorithm for coalition formation which takes advantage of the characteristics of the femtocell network. In summary, the main contributions of this paper are the following.(i)
We propose a new cooperative interference management approach for uplink transmissions in the femtocell network, aiming to improve the aggregate system utility.(ii)
Taking into account the power cost for coalition formation, we show that it is impossible for all the FUEs to merge together by forming one coalition and we formulate the proposed approach as a coalitional game in partition form with an externality due to the interference among the formed disjoint coalitions.(iii)
To obtain the solution of the coalitional game, we propose a new distributed coalition formation algorithm which takes advantage of the characteristics of the femtocell network to reduce the computational complexity and through which the FUEs can self-organize to reach a convergent and stable coalition structure.The rest of this paper is organized as follows: Section2 presents the system model and the proposed cooperative approach for interference management. Section 3 formulates the proposed cooperation problem as a coalitional game in partition form with an externality and proposes a novel algorithm to solve the cooperation problem. Simulation results and analysis are presented in Section 4. Finally, we conclude the paper in Section 5.


## 2. System Model

Consider the uplink transmission scenario in a femtocell network with several FAPs deployed within the range of a macrocell base station (MBS). Adjacent FAPs are connected by X2 interface, and each FAP is connected to the cellular operator network via fiber backhauls. Each FAP serves several FUEs, and we assume the FUEs belonging to the same FAP are originally assigned orthogonal channels, and thus there is no interference among the FUEs which communicate with the same FAP. LetN={1,2,…,N} denote the set of the active FUEs in the considered network which occupy the same channel k in the femtocell networks, and FAP is identified by the same label as its corresponding FUE in N. Let Pimax be the maximum transmit power of FUE i on channel k. As shown in Figure 1(a), in the traditional noncooperative scenario, each FUE i∈N transmits its own signal on its originally assigned channel k during its whole transmission time; hence, the concurrent transmission of FUEs belonging to different FAPs can generate mutual interference which constrains the transmission data rate. The intra-tier interference suffered by FAP i∈N on channel k is given by (1)Iik=∑j∈N,j≠iPjkgj,ik,where gj,ik is the channel gain between FUE j∈N and FAP i on channel k and Pjk is the uplink transmit power of FUE j∈N on channel k.Figure 1
System model illustration. (a) The left part presents a noncooperative approach. Each FUE transmits signals independently and intra-tier interference is caused; (b) the right part presents a cooperative approach. To mitigate the intra-tier interference, FUEs form coalitions dynamically. This paper aims to study this coalition formation problem.
(a)
Noncooperation
(b)
CooperationLetB and N0 be the bandwidth of channel k and the noise power spectral density of additive white Gaussian noise (AWGN), respectively. Then, the achievable transmission data rate of FUE i offered by FAP i in terms of bps/Hz is (2)Rik=log21+Pikgi,ikIik+N0B.In such a noncooperative case, each FUE only cares about its own quality of service, ignoring the intra-tier interference it generates. The intra-tier interference can significantly reduce the transmission data rate and degrade the system throughput. And hence, the intra-tier interference in femtocell networks becomes a serious problem, especially in the case that the FAPs are deployed in a dense manner.To coordinate the intra-tier interference due to neighboring simultaneous transmissions on the same channel and improve the system performance in terms of the achievable transmission data rate, we propose a new approach in which the FUEs transmitting on the same channel in neighboring femtocells can cooperate with each other to reduce the mutual interference and improve the system performance. In detail, depending on the received signal strength indication (RSSI) measurements feedback from their corresponding FAPs [21], each FUE periodically detects nearby interfering FUEs to identify which might cooperatively provide higher system performance. Each FUE and its potential partners negotiate with each other, tending to form a cooperative group, that is, coalition, denoted by S, and S∈N. In addition, cooperative FUEs communicate in a device-to-device (D2D) mode to exchange their scheduling information, time-sharing information, synchronization information, and SINR. Based on the success of the information exchange, each FUE in S can know the actions of the other FUEs and decide how to operate cooperation in a time-sharing manner. Moreover, we assume that the synchronization can be operated well in a coalition. In consequence, the cooperative time-sharing manner ensures that neighboring cooperative FUEs operating on the same channel in the same coalition will not transmit on the same time slot. Therefore, the intra-tier interference is avoided in a coalition. However, due to the independent scheduling among different coalitions, there is still mutual interference among different coalitions. Figure 1 illustrates the cooperative scenario (i.e., Figure 1(b)) compared to the traditional noncooperative paradigm (i.e., Figure 1(a)).In this context, we note that forming coalitions is accompanied by penalty in terms of power cost for exchanging information. DenotePScost by the average power cost for forming coalition S. On the assumption that there is no interference among the links for information exchange, we can define PScost as (3)PScost=∑i∈SPi,jS,where Pi,jS is the minimum transmit power needed by FUE i∈S for broadcasting its individual information to its corresponding farthest partner jS∈S to decide the ways of cooperation and Pi,jS=β0σ2/gi,jS with β0 the target average SNR for information exchange, σ2 the noise variance, and gi,jS the channel gain between FUEs i and jS. We assume that, during information exchange, no transmission errors occur. Meanwhile, for any coalition S, we define the average transmit power constraint as PSmax. In consequence, the actual average power constraint for data transmission is formulated as (4)PStran=PSmax-PScost+,where a+≜max(a,0). Equation (3) shows that the power cost for the formation of any coalition S has relations not only with the location of the FUEs but also with the size of the coalition. Therefore, whenever the distance between the FUEs increases or the coalition size increases, a higher power cost is incurred. Equation (4) indicates that if the power cost for forming coalition S exceeds the maximum transmit power assigned for S, the forming of coalition S fails.LetTS and αik be the transmission time within coalition S and the time fraction shared by FUE i∈S on channel k, respectively. TS represents the time-sharing strategy of FUEs in S and TS={αik}i∈S with αik∈(0,1], ∑i∈S‍αik=1. When cooperating, the average power in terms of Joule/s used for data transmission at the coalition level is (5)P-Stran=∑i∈SPikαikTSTS=∑i∈SPikαik,where PikαikTS is the energy spent by FUE i in terms of Joule for transmitting its own data to its corresponding FAP i on channel k. P-Stran should be no more than PStran. Taking into account P-Stran and PStran, the achievable transmission data rate of FUE i∈S offered by FAP i∈S can be expressed as (6)Ri∈Sk=αiklog2⁡1+Pikgi,ikIN∖S,ik+N0B,where IN∖S,ik=∑j∈N∖S‍Pjkgj,ik is the total interference suffered by FAP i from the other FUEs in S, that is, the interference among disjoint coalitions. As a result, for any FUE i, its achievable transmission data rate in terms of bps/Hz depends not only on its assigned time fraction which is closely related to the size of its coalition, but also on the interference from other coalitions.In this paper, we aim at maximizing the aggregate system utility in terms of the sum of achievable transmission data rate of each link in the femtocell network by the proposed approach while taking account of the power cost. However, (6) shows that the achievable transmission data rate depends not only on the size of S but also on the actions of the FUEs in N∖S. In consequence, to get the maximum total utility, we need to find the optimal coalition structure that the FUEs can form. Although the problem of how coalitions should be formed to get the maximum utility is complex to solve, in this paper, we can capture the characteristics of the femtocell network to figure out the solution.


## 3. Coalition Formation

In this section, we formulate the problem of the proposed cooperative scheme as a coalitional game in partition form and explore a new algorithm for coalition formation in the femtocell networks. First, we introduce the problem formulation for the proposed cooperative approach.


### 3.1. Coalition Formation Concepts

Based on the coalitional game theory, a coalitional game involves a set of players, who seek to form cooperative groups, that is, coalitions, in order to improve their performance or gains [20]. In our paper, we can model the FUEs in N as the players, and all these players aim to reduce the system interference and improve the aggregate system utility (i.e., the sum of achievable transmission data rate of each uplink in the femtocell network) by dynamically forming coalitions.Theorem 1.
The proposed approach is a coalitional game in partition form with an externality.Proof.
Coalitional game in partition form [22] means that the value of any coalition (i.e., the utility that a coalition can obtain) strongly depends on how the players outside that coalition are organized. In our paper, due to the power cost for coalition formation, it is impossible for all the FUEs to form a single coalition. Given any coalition S⊂N, we define the value of S, denoted by υ(S), as the sum of the data rates of each FUE in S. According to (6), υ(S) is given by (7)υS=∑i∈SRi∈Sk=∑i∈Sαiklog2⁡1+Pikgi,ikIN∖S,ik+N0B.Hence, υ(S) is affected by IN∖S,ik. And thus, we claim that the partition form of the proposed approach stems from the fact that the value of one coalition is affected by the interference from the other coalitions. Actually, the interference suffered by one coalition depends on the time-sharing strategies of the FUEs that are not within that coalition and the way they organize themselves into their own coalitions.Letτ be a coalition structure or a partition of N. One partition represents which coalitions the FUEs form. Let B be the set of all partitions. For a partition τ∈B, we have ∪S∈τS=N and S~∪S^=∅, for all S~,S^∈τ, S~≠S^. For example, given a coalitional game with three players, τ∈B can be one of the following coalition structures: {{1},{2},{3}}, {{1,2},{3}}, {{1},{2,3}}, {{1,3},{2}}, and {{1,2,3}}.Given a partitionτ of N and the time-sharing strategy set of τ, denoted by Tτ=∪S∈τTS, according to Theorem 1, we can rewrite υ(S) as υ(S,τ,Tτ).As discussed in the previous section, active FUEs occupying the same channel have a strong incentive to cooperate to reduce the intra-tier interference and improve their performance by using advanced techniques such as D2D and dynamic coalition formation. Due to the proposed time-sharing scheme within each coalition, there is no interference among FUEs in the same coalition. We define the payoff of FUEi∈S as its achievable transmission data rate in terms of bps/Hz, which is given by (8)υiS,τ,Tτ=αiklog2⁡1+Pikgi,ikIN∖S,ikS,τ,Tτ+N0B,where IN∖S,ik(S,τ,Tτ) is the interference suffered by FUE i in coalition S, and IN∖S,ik(S,τ,Tτ) depends on the partition τ and the time-sharing strategy set of τ.The aggregate system utility can be defined as(9)υτ,Tτ=∑S∈τ∑i∈SυiS,τ,Tτ=∑S∈τ∑i∈Sαiklog21+Pikgi,ikIN∖S,ikS,τ,Tτ+N0B.The goal of the paper is to maximize the aggregate system utility by finding the optimal partitionτ∈B and its corresponding time-sharing strategy set Tτ while taking account of the constraints in terms of transmit power. Hence, the optimization problem can be formulated mathematically as(10a)max⁡υτ,Tτ(10b)s.t.PStran=PSmax-PScost+,∀S∈τ(10c)0≤P-Stran≤PStran,∀S∈τ(10d)∑i∈Sαik=1,∀k,∀S∈τ(10e)αik∈0,1,∀i∈S,∀k,∀S∈τ(10f)Pi,jS=β0σ2gi,jS,∀i,jS∈S,jS≠i,∀S∈τ,where (10a) is the goal of the proposed cooperative approach, (10b) represents the power cost constraint for forming a coalition, (10c) represents the power constraint for the data transmission in a coalition, (10d) and (10e) are the time-sharing strategy constraints for each coalition, and finally (10f) is the SNR condition for forming a coalition.


### 3.2. Coalition Formation Algorithm

To solve the above coalition formation problem, there are several methods, such as the exhaustive search method [23], the merge and split method [20], the recursive core method [15], and the merge-only method [19]. Reference [23] shows finding the optimal partition for solving an optimization problem such as in (10a), (10b), (10c), (10d), (10e), and (10f) by a centralized entity through exhaustive search is an NP-complete problem. This is because the size of the partition set is equal to the Bell number, and it grows exponentially with the number of FUEs. Thus, the exhaustive search method is impossible in practice. Although the merge-split process is the most general approach to coalition formation [20], there exist games for which the merge-split process is unstable [19]. The recursive core method is just practical on the condition that the core exists [15]. Besides, in the merge-only method [19], any two coalitions can decide whether or not to merge with each other and once they decide to merge into a bigger coalition, they can not split away. However, in the merging process between two coalitions, after one of the two coalitions is fixed, the selection of the other coalition is random. Once the fixed-one’s merging with its randomly selected partner can bring more profits, they merge together, and they will no longer split. This randomness ignores other possible partners of that fixed coalition which may bring more benefits.In a nutshell, to obtain the optimal solution of (10a), (10b), (10c), (10d), (10e), and (10f) is very difficult, and the practical methods in the existing literatures are partly based on some assumptions to simulate the behaviors of the players in a distributed manner. In this paper, we propose a new distributed algorithm called RSSI-based coalition formation algorithm which takes advantage of the RSSI availability of the nodes in the femtocell networks. In practice, intra-tier interference in the uplink is often dominated by one or two FUEs located near the femtocell boundaries closest to FAP serving the desired signal. FUEs in the femtocell network have an incentive to mitigate the most serious interference with their closest interfering sources. Thus, unlike the random selection of the partner, once each FUE gets the global RSSI measurements feedback from its corresponding FAP, the mutual interfering FUEs with the most serious interference tend to cooperate with each other first.For simplicity, we introduce two assumptions which allow us to constrain the number of possible partitions.(1)
Equality assumption: all the FUEs in the same coalition share the whole transmission time equally [16].(2)
Status quo assumption: FUEs maintain their status quo as other FUEs are forming coalitions.Given a partitionτ of N and any coalition S∈τ, while the first assumption models the behavior of the FUEs in S, the second assumption indicates the behavior of the FUEs in τ∖S. From an individual perspective, it is reasonable to make the assumption that the FUEs can reach an agreement on the equal time-sharing strategy in a coalition, and in this paper we mainly focus on the dynamic coalition formation by using the proposed RSSI-based coalition formation algorithm. This proposed algorithm is absolutely suitable for other time-sharing strategies.For the RSSI-based coalition formation method, we have the following algorithm.(1)
The partition is initialized to be all singletons. A singleton is a coalition with only one FUE as its member.(2)
Through RSSI measurements, each FUE detects nearby active FUEs on the same channel and sorts the interfering FUEs from the stronger to the weaker. Moreover, all the FUEs record the interference information (i.e., the location of all the nodes and the interference level of all the links) of the femtocell networks.(3)
At any given time, all the FUEs search for the link with the most serious interference. The coalitions associated with the link with the most serious interference negotiate with each other to check if a merger is possible and thus a new partition. During the negotiation, the power cost and the aggregate system utility in the newly formed partition are calculated by (10a), (10b), (10c), (10d), (10e), and (10f). Moreover, whatever the result of the negotiation between the two concerned coalitions is, the other coalitions maintain their status quo.(4)
Based on the calculated aggregate system utility, if the aggregate utility in the newly formed partition is greater than that in the previous partition, the new partition is retained and then the negotiation process is iterated for another pair of coalitions corresponding to the most serious interfering link in the new partition from step(3). Otherwise, we revert to the previous partition.At any timet, given a partition τt, there are three possibilities for the merging negotiation between the coalitions associated with the newfound link with the most serious interference in step (3) according to the above status quo assumption. Compared with the singleton, we define the nonsingleton in τt as the cooperative coalition. First, if one node of the newfound most serious interfering link belongs to any one current cooperative coalition, the negotiation is conducted between the other FUE and this cooperative coalition. Second, if both nodes of the newfound most serious interfering link belong to different current cooperative coalitions, the negotiation is not conducted. Third, if both nodes of the newfound most serious interfering link do not belong to any current cooperative coalitions, FUEs associated with this newfound link negotiate with each other to check if a new merger is possible. Let N={1,2,…,N} be a set of active FUEs on the same frequency channel, and take N=10 as an example to illustrate these three possibilities. At time t, given τt={S1,S2,…,S7} with S1={2,5}, S2={3,9,7}, S3={1}, S4={4}, S5={6}, S6={8}, and S7={10}, there exist three possibilities.(1)
If the newfound most serious interfering link is FUE1-FAP2, the negotiation will be conducted betweenS1 and S3 to decide whether or not to merge into a potential bigger coalition {2,5,1} due to the fact that FUE2 is in the current cooperative coalition S1, thus forming a new partition τt+1, and τt+1={{2,5,1},{3,9,7},{4},{6},{8},{10}}.(2)
If the newfound most serious interfering link is FUE2-FAP3, new merger will not be performed due to the fact that FUE2 and FUE3 are in the current cooperative coalitionsS1 and S2, respectively, and thus τt+1←τt.(3)
If the newfound most serious interfering link is FUE6-FAP8, it is noted that{6} and {8} are singletons. Because {6} and {8} have nothing to do with any current cooperative coalition, they negotiate with each other to merge into a potential bigger coalition {6,8}, thus forming a new partition τt+1, and τt+1={{2,5},{3,9,7},{6,8},{1},{4},{10}}.Using the proposed method, we can get the final solutionτ∗, that is, the final agreed partition by negotiations, and the FUEs in the same coalition then transmit their signals with the equal time-sharing strategy based on the final partition.


### 3.3. Properties of the Proposed Coalition Formation Algorithm

We now investigate the properties of the proposed coalition formation algorithm from the perspective of its convergence and the stability of its final partition.Proposition 2.
Starting from the initial partition, the convergence of the proposed RSSI-based coalition formation algorithm is guaranteed.Proof.
In femtocell networks, given the set of the active FUEs on the same channel, the total number of partitions is finite. In particular, when taking the power cost for coalition formation into consideration, the growth of the coalition size or the increase in the distance between the FUEs in the coalition can increase the power cost, leading to the failure of a new coalition. In consequence, the FUEs have a strong incentive to cooperate with their closest partners, further reducing the potential number of the partitions. As each iteration aims to mitigate the current most serious interference and cause a new partition with a higher system utility than all the old ones, the proposed algorithm prevents the FUEs from forming a partition that has previously appeared. Consequently, the proposed algorithm is essentially a continual process of approaching the optimal solution, and given the finite number of the partitions, our algorithm is guaranteed to reach a final partition.Proposition 3.
The final partitionτ∗ resulting from the RSSI-based coalition formation algorithm is stable.Proof.
If the final partitionτ∗ is not stable, then there is at least one FUE that can deviate from its current coalition and join (or form) another coalition, changing the current partition τ∗ into a new coalitional structure τ′. Denote FUEdev as this FUE, and there are two cases. (1)
IfFUEdev belongs to a singleton of the final partition τ∗, its deviation means that FUEdev has an incentive to join another coalition to improve the system utility, which contradicts with the fact that τ∗ is the final partition resulting from the convergence of the proposed algorithm.(2)
IfFUEdev belongs to a cooperative coalition of the final partition τ∗, its deviation means that FUEdev has an incentive to leave its cooperative coalition to form a singleton or join another coalition, which contradicts with the status quo assumption.
Consequently, the final partitionτ∗ is stable.


## 3.1. Coalition Formation Concepts

Based on the coalitional game theory, a coalitional game involves a set of players, who seek to form cooperative groups, that is, coalitions, in order to improve their performance or gains [20]. In our paper, we can model the FUEs in N as the players, and all these players aim to reduce the system interference and improve the aggregate system utility (i.e., the sum of achievable transmission data rate of each uplink in the femtocell network) by dynamically forming coalitions.Theorem 1.
The proposed approach is a coalitional game in partition form with an externality.Proof.
Coalitional game in partition form [22] means that the value of any coalition (i.e., the utility that a coalition can obtain) strongly depends on how the players outside that coalition are organized. In our paper, due to the power cost for coalition formation, it is impossible for all the FUEs to form a single coalition. Given any coalition S⊂N, we define the value of S, denoted by υ(S), as the sum of the data rates of each FUE in S. According to (6), υ(S) is given by (7)υS=∑i∈SRi∈Sk=∑i∈Sαiklog2⁡1+Pikgi,ikIN∖S,ik+N0B.Hence, υ(S) is affected by IN∖S,ik. And thus, we claim that the partition form of the proposed approach stems from the fact that the value of one coalition is affected by the interference from the other coalitions. Actually, the interference suffered by one coalition depends on the time-sharing strategies of the FUEs that are not within that coalition and the way they organize themselves into their own coalitions.Letτ be a coalition structure or a partition of N. One partition represents which coalitions the FUEs form. Let B be the set of all partitions. For a partition τ∈B, we have ∪S∈τS=N and S~∪S^=∅, for all S~,S^∈τ, S~≠S^. For example, given a coalitional game with three players, τ∈B can be one of the following coalition structures: {{1},{2},{3}}, {{1,2},{3}}, {{1},{2,3}}, {{1,3},{2}}, and {{1,2,3}}.Given a partitionτ of N and the time-sharing strategy set of τ, denoted by Tτ=∪S∈τTS, according to Theorem 1, we can rewrite υ(S) as υ(S,τ,Tτ).As discussed in the previous section, active FUEs occupying the same channel have a strong incentive to cooperate to reduce the intra-tier interference and improve their performance by using advanced techniques such as D2D and dynamic coalition formation. Due to the proposed time-sharing scheme within each coalition, there is no interference among FUEs in the same coalition. We define the payoff of FUEi∈S as its achievable transmission data rate in terms of bps/Hz, which is given by (8)υiS,τ,Tτ=αiklog2⁡1+Pikgi,ikIN∖S,ikS,τ,Tτ+N0B,where IN∖S,ik(S,τ,Tτ) is the interference suffered by FUE i in coalition S, and IN∖S,ik(S,τ,Tτ) depends on the partition τ and the time-sharing strategy set of τ.The aggregate system utility can be defined as(9)υτ,Tτ=∑S∈τ∑i∈SυiS,τ,Tτ=∑S∈τ∑i∈Sαiklog21+Pikgi,ikIN∖S,ikS,τ,Tτ+N0B.The goal of the paper is to maximize the aggregate system utility by finding the optimal partitionτ∈B and its corresponding time-sharing strategy set Tτ while taking account of the constraints in terms of transmit power. Hence, the optimization problem can be formulated mathematically as(10a)max⁡υτ,Tτ(10b)s.t.PStran=PSmax-PScost+,∀S∈τ(10c)0≤P-Stran≤PStran,∀S∈τ(10d)∑i∈Sαik=1,∀k,∀S∈τ(10e)αik∈0,1,∀i∈S,∀k,∀S∈τ(10f)Pi,jS=β0σ2gi,jS,∀i,jS∈S,jS≠i,∀S∈τ,where (10a) is the goal of the proposed cooperative approach, (10b) represents the power cost constraint for forming a coalition, (10c) represents the power constraint for the data transmission in a coalition, (10d) and (10e) are the time-sharing strategy constraints for each coalition, and finally (10f) is the SNR condition for forming a coalition.


## 3.2. Coalition Formation Algorithm

To solve the above coalition formation problem, there are several methods, such as the exhaustive search method [23], the merge and split method [20], the recursive core method [15], and the merge-only method [19]. Reference [23] shows finding the optimal partition for solving an optimization problem such as in (10a), (10b), (10c), (10d), (10e), and (10f) by a centralized entity through exhaustive search is an NP-complete problem. This is because the size of the partition set is equal to the Bell number, and it grows exponentially with the number of FUEs. Thus, the exhaustive search method is impossible in practice. Although the merge-split process is the most general approach to coalition formation [20], there exist games for which the merge-split process is unstable [19]. The recursive core method is just practical on the condition that the core exists [15]. Besides, in the merge-only method [19], any two coalitions can decide whether or not to merge with each other and once they decide to merge into a bigger coalition, they can not split away. However, in the merging process between two coalitions, after one of the two coalitions is fixed, the selection of the other coalition is random. Once the fixed-one’s merging with its randomly selected partner can bring more profits, they merge together, and they will no longer split. This randomness ignores other possible partners of that fixed coalition which may bring more benefits.In a nutshell, to obtain the optimal solution of (10a), (10b), (10c), (10d), (10e), and (10f) is very difficult, and the practical methods in the existing literatures are partly based on some assumptions to simulate the behaviors of the players in a distributed manner. In this paper, we propose a new distributed algorithm called RSSI-based coalition formation algorithm which takes advantage of the RSSI availability of the nodes in the femtocell networks. In practice, intra-tier interference in the uplink is often dominated by one or two FUEs located near the femtocell boundaries closest to FAP serving the desired signal. FUEs in the femtocell network have an incentive to mitigate the most serious interference with their closest interfering sources. Thus, unlike the random selection of the partner, once each FUE gets the global RSSI measurements feedback from its corresponding FAP, the mutual interfering FUEs with the most serious interference tend to cooperate with each other first.For simplicity, we introduce two assumptions which allow us to constrain the number of possible partitions.(1)
Equality assumption: all the FUEs in the same coalition share the whole transmission time equally [16].(2)
Status quo assumption: FUEs maintain their status quo as other FUEs are forming coalitions.Given a partitionτ of N and any coalition S∈τ, while the first assumption models the behavior of the FUEs in S, the second assumption indicates the behavior of the FUEs in τ∖S. From an individual perspective, it is reasonable to make the assumption that the FUEs can reach an agreement on the equal time-sharing strategy in a coalition, and in this paper we mainly focus on the dynamic coalition formation by using the proposed RSSI-based coalition formation algorithm. This proposed algorithm is absolutely suitable for other time-sharing strategies.For the RSSI-based coalition formation method, we have the following algorithm.(1)
The partition is initialized to be all singletons. A singleton is a coalition with only one FUE as its member.(2)
Through RSSI measurements, each FUE detects nearby active FUEs on the same channel and sorts the interfering FUEs from the stronger to the weaker. Moreover, all the FUEs record the interference information (i.e., the location of all the nodes and the interference level of all the links) of the femtocell networks.(3)
At any given time, all the FUEs search for the link with the most serious interference. The coalitions associated with the link with the most serious interference negotiate with each other to check if a merger is possible and thus a new partition. During the negotiation, the power cost and the aggregate system utility in the newly formed partition are calculated by (10a), (10b), (10c), (10d), (10e), and (10f). Moreover, whatever the result of the negotiation between the two concerned coalitions is, the other coalitions maintain their status quo.(4)
Based on the calculated aggregate system utility, if the aggregate utility in the newly formed partition is greater than that in the previous partition, the new partition is retained and then the negotiation process is iterated for another pair of coalitions corresponding to the most serious interfering link in the new partition from step(3). Otherwise, we revert to the previous partition.At any timet, given a partition τt, there are three possibilities for the merging negotiation between the coalitions associated with the newfound link with the most serious interference in step (3) according to the above status quo assumption. Compared with the singleton, we define the nonsingleton in τt as the cooperative coalition. First, if one node of the newfound most serious interfering link belongs to any one current cooperative coalition, the negotiation is conducted between the other FUE and this cooperative coalition. Second, if both nodes of the newfound most serious interfering link belong to different current cooperative coalitions, the negotiation is not conducted. Third, if both nodes of the newfound most serious interfering link do not belong to any current cooperative coalitions, FUEs associated with this newfound link negotiate with each other to check if a new merger is possible. Let N={1,2,…,N} be a set of active FUEs on the same frequency channel, and take N=10 as an example to illustrate these three possibilities. At time t, given τt={S1,S2,…,S7} with S1={2,5}, S2={3,9,7}, S3={1}, S4={4}, S5={6}, S6={8}, and S7={10}, there exist three possibilities.(1)
If the newfound most serious interfering link is FUE1-FAP2, the negotiation will be conducted betweenS1 and S3 to decide whether or not to merge into a potential bigger coalition {2,5,1} due to the fact that FUE2 is in the current cooperative coalition S1, thus forming a new partition τt+1, and τt+1={{2,5,1},{3,9,7},{4},{6},{8},{10}}.(2)
If the newfound most serious interfering link is FUE2-FAP3, new merger will not be performed due to the fact that FUE2 and FUE3 are in the current cooperative coalitionsS1 and S2, respectively, and thus τt+1←τt.(3)
If the newfound most serious interfering link is FUE6-FAP8, it is noted that{6} and {8} are singletons. Because {6} and {8} have nothing to do with any current cooperative coalition, they negotiate with each other to merge into a potential bigger coalition {6,8}, thus forming a new partition τt+1, and τt+1={{2,5},{3,9,7},{6,8},{1},{4},{10}}.Using the proposed method, we can get the final solutionτ∗, that is, the final agreed partition by negotiations, and the FUEs in the same coalition then transmit their signals with the equal time-sharing strategy based on the final partition.


## 3.3. Properties of the Proposed Coalition Formation Algorithm

We now investigate the properties of the proposed coalition formation algorithm from the perspective of its convergence and the stability of its final partition.Proposition 2.
Starting from the initial partition, the convergence of the proposed RSSI-based coalition formation algorithm is guaranteed.Proof.
In femtocell networks, given the set of the active FUEs on the same channel, the total number of partitions is finite. In particular, when taking the power cost for coalition formation into consideration, the growth of the coalition size or the increase in the distance between the FUEs in the coalition can increase the power cost, leading to the failure of a new coalition. In consequence, the FUEs have a strong incentive to cooperate with their closest partners, further reducing the potential number of the partitions. As each iteration aims to mitigate the current most serious interference and cause a new partition with a higher system utility than all the old ones, the proposed algorithm prevents the FUEs from forming a partition that has previously appeared. Consequently, the proposed algorithm is essentially a continual process of approaching the optimal solution, and given the finite number of the partitions, our algorithm is guaranteed to reach a final partition.Proposition 3.
The final partitionτ∗ resulting from the RSSI-based coalition formation algorithm is stable.Proof.
If the final partitionτ∗ is not stable, then there is at least one FUE that can deviate from its current coalition and join (or form) another coalition, changing the current partition τ∗ into a new coalitional structure τ′. Denote FUEdev as this FUE, and there are two cases. (1)
IfFUEdev belongs to a singleton of the final partition τ∗, its deviation means that FUEdev has an incentive to join another coalition to improve the system utility, which contradicts with the fact that τ∗ is the final partition resulting from the convergence of the proposed algorithm.(2)
IfFUEdev belongs to a cooperative coalition of the final partition τ∗, its deviation means that FUEdev has an incentive to leave its cooperative coalition to form a singleton or join another coalition, which contradicts with the status quo assumption.
Consequently, the final partitionτ∗ is stable.


## 4. Simulation Results and Analysis

For simulations, we consider a single hexagonal macrocell with a radius ofl=100m within which N active FAPs on the same channel are randomly deployed. Each FAP n∈N with a radius of 20 m serves only one FUE by a closed access policy. The maximum transmit power at each FUE is 20 dBm. Transmissions are affected by distance dependent path loss shadowing according to the 3GPP specifications [6]. Moreover, a wall loss attenuation of 12 dB is considered. The maximum transmit power per coalition is 20 dBm and the minimum required SNR at the FUEs for the success of information exchange in the same coalition is 6 dB. 10000 independent simulation rounds with randomly located nodes (i.e., FAPs and FUEs) are conducted for different sizes of femtocell networks.Figure2 shows a snapshot of a femtocell network with the final partition resulting from the proposed coalition formation algorithm with N=8 FAPs that are randomly deployed in the network. In this figure, it is clear that any FUE has an incentive to cooperate with its neighboring interfering FUEs to reduce the interference. However, the size of the coalition is limited because of the consideration of the power cost. In detail, FUE3, FUE4, FUE5, and FUE6 have an incentive to merge into a coalition due to their dense deployments which cause serious interference. Furthermore, while FUE2 and FUE7 form a cooperative cooperation, FUE1 and FUE8 have to remain to be singletons due to their spatial separation which may make costs outweigh the benefits. As a result, the final partition is {{3,4,5,6},{2,7},{1},{8}}.Figure 2
A snapshot of a femtocell network with the final partition.N=8 and l=100m. Red dots and red stars represent the FUEs and FAPs in the femtocell network, respectively. The MBS is represented by a green square.To show how the coalition formation performs by the proposed method, Figure3 illustrates the variation of the aggregate system utility with respect to the separation distance between two FAPs, both of which serve their corresponding FUEs. The distance between the two FAPs is varied from 5 to 80 meters. The FUE is randomly located within the range of its corresponding FAP. By comparing our approach with noncooperative approach and grand coalition (i.e., a coalition containing all the players) approach in terms of the aggregate system utility, Figure 3 shows that the RSSI-based coalition formation method performs better than both noncooperative approach and grand coalition approach. In detail, when the FAPs are near each other, in this case, within 30 meters, the grand coalition method outperforms the noncooperation in terms of the aggregate system utility. Nevertheless, the performance of the singletons improves with increasing the distance of separation. This is due to the fact that the nearer two links cause more interference to each other and they have an incentive to cooperate with each other to reduce the interference. Conversely, when the FAPs are far apart, the interference becomes not serious and even negligible; hence there is no gain in forming a coalition by sharing the transmission time. Moreover, it is interesting to note that the aggregate utility of the grand coalition remains almost the same at around 18.5 bps/Hz. This is because the cooperation of the two FUEs eliminates the system interference and υ({1,2})=α1klog2(1+P1kg1,1k/N0B)+α2klog2(1+P2kg2,2k/N0B). In a nutshell, merging is profitable only when the FAPs are close enough to each other, and the RSSI-based coalition formation method can serve better performance than noncooperative method and grand coalition method.Figure 3
Aggregate system utility versus the distance between two FAPs, for a femtocell network havingN=2 FAPs.Figure4 shows a comparison of the aggregate system utility of both cooperative approach and noncooperative approach as a function of the number of FUEs. Furthermore, to compare different coalition formation algorithms, three algorithms are taken into consideration, such as the centralized optimal solution by exhaustive search method, the merge-only algorithm, and the proposed RSSI-based coalition formation algorithm. Note that since the computational complexity for exhaustive search, which determines the optimal partition of a set, increases exponentially with the number of FUEs, we present the results for up to seven FUEs in the network. The results show that both the proposed algorithm and the merge-only algorithm achieve a near-optimal performance when the number of FUEs N is small. This figure also shows that the cooperative approach outperforms the noncooperative approach. In detail, the proposed algorithm has a relatively small performance gain compared to the noncooperative case for small networks, in the case that N≤6. As the number of FUEs increases, the proposed coalition formation algorithm improves the performance in terms of the aggregate system utility significantly. This is due to the fact that, as N increases, cooperation becomes desirable since interference can be suppressed among nearby interfering FUEs by forming coalitions. Moreover, we also observe that with increasing the number of the FUEs the rate of the improvement of the utility is smaller, both for the noncooperative method and the proposed coalition formation method. This is because of the increased interference from the dense FUEs.Figure 4
Aggregate system utility versus the number of FUEs.In Figure5, we plot the average payoff of each link versus the number of FUEs from 2 to 20 in the case of noncooperative approach, centralized optimal solution, merge-only method, and the proposed algorithm, respectively. Results show that when the number of FUEs increases, the average payoff decreases due to the increased intra-tier interference. However, the proposed algorithm can achieve a near-optimal performance when the number of FUEs N is small and outperforms noncooperative schemes.Figure 5
Average payoff of each link versus the number of FUEs.Figure6 provides a comparison of the simulation time of exhaustive search method, merge-only algorithm, and our algorithm as a function of the achievable aggregate system utility. The results demonstrate that though the optimal solution can be obtained by exhaustive search, its simulation time increases exponentially with the number of FUEs, and we just consider the case for up to seven FUEs in the network. In Figure 4, the curves indicate that the results of the merge-only algorithm and our algorithm appear to be the same. However, Figure 6 shows that the time complexity of the RSSI-based coalition formation algorithm is much lower than that of the merge-only method.Figure 6
Simulation time versus the aggregate system utility.Figure7 shows the average number of nonsingletons and the average size of the maximum coalition (i.e., the coalition with the largest number of players relative to the other coalitions for a given partition) resulting from the proposed coalition formation algorithm as a function of the number of FUEs. Figure 7 illustrates that as N increases both the average number of nonsingletons and the average size of the maximum coalition increase. This is because, for large N, the FUEs are more inclined to cooperate with their neighboring FUEs to suppress the interference. However, while the average number of nonsingletons increases linearly, the improvement of the average size of the maximum coalition slows with the number of FUEs varying from 3 to 20. This is due to the fact that the power cost for information exchange increases with an increase in the size of the coalition. For any coalition, once the power cost exceeds its maximum transmit power, that coalition can not be formed.Figure 7
Average number of nonsingletons and average size of the maximum coalition versus the number of FUEs.


## 5. Conclusion

In this paper, we have proposed a new cooperative approach for the interference management in the context of femtocell networks. In the new proposed approach, each FUE has an incentive to cooperate with its closest interfering partners by forming coalitions to mitigate the intra-tier interference. Taking into account the power cost for cooperation, we have formulated the cooperation problem as a coalitional game in partition form with an externality due to the interference among disjoint coalitions. To form coalitions, we have introduced a new distributed coalition formation algorithm, that is, RSSI-based coalition formation algorithm, which takes advantage of the behaviours of the nodes in the femtocell networks. We have presented the analysis of the convergence and the stability of the final partition of the proposed algorithm, respectively. Simulation results have shown that the proposed cooperative algorithm has much lower time complexity, when compared with other cooperative case, and the size of the coalitions is unlikely very big due to the consideration of the power cost.



---

*Source: 767649-2015-06-15.xml*