text:
Francesco Pantisano
email: fpantisa@ee.oulu.fi

Mehdi Bennis
email: bennis@ee.oulu.fi

Walid Saad

Mérouane Debbah
email: merouane.debbah@supelec.fr

Matti Latva-Aho

Improving Macrocell-Small Cell

Keywords:

published or not. The documents may come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

The use of underlaid small cell base stations (SBSs) has been proposed in the upcoming wireless standards, such as Long-Term Evolution Advanced [START_REF] Gpp | Requirements for further advancements for E-UTRA (LTE-Advanced)[END_REF], so as to increase the spectral efficiency and improve the indoor coverage [START_REF] Sesia | LTE -the UMTS long term evolution[END_REF]. SBSs are low-cost, low-power, base stations that can be deployed either outdoor by the operator (e.g., picocells, microcells, or metrocells) or indoor by end users (e.g., femtocells) so as to boost the capacity of wireless systems by reducing the distance between users and their serving stations. Since, in an underlay spectrum access, the SBSs opportunistically reuse the macrocell spectrum, the interference has been identified as the main limiting factor for the macrocellsmall cell coexistence [START_REF] Lopez-Perez | Enhanced intercell interference coordination challenges in heterogeneous networks[END_REF], [START_REF] Lopez-Perez | OFDMA femtocells: A roadmap on interference avoidance[END_REF]. In this context, two major interference components are identified: the interference brought from the SBSs to the macrocell users (MUEs), and the interference among different SBSs, which are respectively referred to as cross-tier and co-tier interference. While co-tier interference is a major challenge in all SBS deployments, cross-tier interference is particularly sever in outdoor small cell deployment, such as operator-deployed picocells [START_REF] Quek | Small Cell Networks: Deployment, PHY Techniques, and Resource Management[END_REF]. Moreover, as the SBSs can only access the spectral resources which are under-utilized by the macrocell tier, the small cells are not provided any guarantees in terms of transmission opportunities or quality of service (QoS) requirements. Hence, developing efficient interference management and spectrum access policies is of utmost importance for achieving the performance foreseen for small cell deployments [START_REF] Gpp | Service requirements for Home Node B (HNB) and Home eNode B (HeNB)[END_REF].

Recently, significant research efforts have been dedicated to the study of macrocell-small cell coexistence, by relying on the SBSs' self-organization capabilities. Notably, dynamic spectrum access [START_REF] Lopez-Perez | Enhanced intercell interference coordination challenges in heterogeneous networks[END_REF], [START_REF] Guvenc | A hybrid frequency assignment for femtocells and coverage area analysis for co-channel operation[END_REF], [START_REF] Huang | Revenue management for cognitive spectrum underlay networks: An interference elasticity perspective[END_REF], [START_REF] Guruacharya | Hierarchical competition in femtocell-based cellular networks[END_REF], [START_REF] Bharucha | Dynamic resource partitioning for downlink femto-to-macro-cell interference avoidance[END_REF], interference coordination [START_REF] Lopez-Perez | Enhanced intercell interference coordination challenges in heterogeneous networks[END_REF], [START_REF] Guvenc | Capacity and fairness analysis of heterogeneous networks with range expansion and interference coordination[END_REF], [START_REF] Mukherjee | Effects of range expansion and interference coordination on capacity and fairness in heterogeneous networks[END_REF] and power control [START_REF] Huang | Distributed interference compensation for wireless networks[END_REF], [START_REF] Chandrasekhar | Power control in two-tier femtocell networks[END_REF], [START_REF] Torregoza | Joint power control, base station assignment, and channel assignment in cognitive femtocell networks[END_REF], [START_REF] Li | Downlink power control in co-channel macrocell femtocell overlay[END_REF] have been proposed for managing interference by exploiting frequency carriers or time slots that are under-utilized in the macrocell tier. In this context, interference alignment (IA) has been proposed as a linear coding technique that can virtually guarantee interference-free transmissions by exploiting the spatial directions of the multiple-input multiple-output (MIMO) interference channel, referred to as degrees of freedom, hereinafter [START_REF] Jafar | Degrees of freedom region of the MIMO X channel[END_REF], [START_REF] Suh | Downlink interference alignment[END_REF], [START_REF] Gou | Degrees of freedom of the K user MIMO interference channel[END_REF]. As IA techniques only use half of the available transmission opportunities, the opportunistic exploitation of the spatial degrees, proposed in the IA concept, has been recently extended to incorporate the frequency dimension. By doing so, one can improve the transmission rates of the small cells by exploring new transmission opportunities (i.e., degrees of freedom) in both the frequency and space domains [START_REF] Perlaza | From spectrum pooling to space pooling: Opportunistic interference alignment in mimo cognitive networks[END_REF], [START_REF] Amir | Opportunistic interference alignment for multiuser cognitive radio[END_REF], [START_REF] Peters | Cooperative algorithms for MIMO interference channels[END_REF]. It thus becomes possible for the small cells to enable interference-free communications by leveraging the spatial and frequency precoding. Moreover, the opportunistic IA solution can be combined with other interference management techniques, such as successive interference cancellation [START_REF] Yang | On design of asymmetric interference alignment and cancelation scheme in MIMO X network[END_REF] or zero forcing equalization [START_REF] Pantisano | Interference alignment for cooperative femtocell networks: A game-theoretic approach[END_REF]. In order to perform opportunistic IA, the complete knowledge of the full channel state information (CSI) is required and the transmitters are required to cooperate for the joint design of the precoding matrices. However, IA techniques are limited by the fact that IA solutions only exist for certain problem dimensions, which are given by the number of antennas and the degrees of freedom [START_REF] Gou | Degrees of freedom of the K user MIMO interference channel[END_REF], [START_REF] Gomadam | Approaching the capacity of wireless networks through distributed interference alignment[END_REF]. Hence, in practice, an IA scheme one can only suppress a limited number of interfering signals, since the number of antennas (especially at the receiver side) is limited. Moreover, using half of the spatial degrees of freedom further reduces the already scarce transmission opportunities of underlaid small cell networks [START_REF] Gou | Degrees of freedom of the K user MIMO interference channel[END_REF].

To overcome these IA limitations, the concept of interference draining (ID) [START_REF] Zhou | A novel interference draining scheme for cognitive radio based on interference alignment[END_REF] has been recently introduced with the purpose of reusing the degrees of freedom unused by the macrocell, while controlling the interference brought to the macrocell tier. In essence, ID is an extension of the IA solution to the case of shared spectrum deployments. Some of the conditions on the mutual alignment of the interfering signals are relaxed, and a margin of interfering power is allowed at each receiver. In addition, such an approach has full reuse of the degrees of freedom in both space and frequency domains, provided that the interference constraints are verified. In [START_REF] Zhou | A novel interference draining scheme for cognitive radio based on interference alignment[END_REF], an opportunistic technique for interference-limited networks is presented to enable the interference draining in the space and time domain and increase the number of secondary users in the system. In [START_REF] Zhou | On dimension scarcity for user admission in MIMO interference aligned networks[END_REF], the extension of IA to the time domain is combined with a partial alignment technique for data rate enhancement of secondary networks. Note that both interference draining and interference alignment involve operations which are jointly performed by mutual interferers, which, however, are uncoordinated. Therefore, it is clear that there is a need for novel cooperative strategies at the SBS level aimed at a dynamic reuse of the macrocell spatial and frequency resources, as recently suggested in [START_REF] Caire | Special issue on heterogeneous networks[END_REF], [START_REF] Guvenc | Capacity and fairness analysis of heterogeneous networks with range expansion and interference coordination[END_REF], [START_REF] Zhu | A practical and efficient algorithm for distributed interference alignment based on cognitive radio[END_REF], [START_REF] Duan | Contract-based cooperative spectrum sharing[END_REF], [START_REF] Perlaza | From spectrum pooling to space pooling: Opportunistic interference alignment in mimo cognitive networks[END_REF], [START_REF] Barbarossa | Decentralized interference management in femtocells: A game-theoretic approach[END_REF].

The main scope of this paper is to jointly address the co-tier and the cross-tier interference management in the downlink of an underlay macrocell-small cell network. Due to the highly dynamic changes in the small cell tier (e.g., SBSs turning on/off, dynamic user arrivals), the optimization of macro base station (MBS) transmissions accounting for the bursty interference generated by the SBSs is a very complex task. In this respect, we first show that, when the MBS performs an independent and interference-unaware power allocation [32, Section 7.1.1], the achievable downlink data rates are strongly affected by the small cell interference. This effect becomes more acute when the MBS transmits several signal streams over the channels degrees of freedom, and for large small cell tiers. Hence, we propose that the SBSs entirely manage the co-tier and cross-tier interference by cooperatively using an interference draining technique. Unlike existing work which addresses static cooperation among the secondary nodes, i.e., implicit cooperation among mutual interferers [START_REF] Jafar | Degrees of freedom region of the MIMO X channel[END_REF], [START_REF] Zhou | A novel interference draining scheme for cognitive radio based on interference alignment[END_REF], [START_REF] Zhou | On dimension scarcity for user admission in MIMO interference aligned networks[END_REF], our proposed approach allows the SBSs to autonomously decide on when to cooperate and with whom, based on their self-organizing capabilities. One of the key advantages of the proposed solution is that, by opportunistically reusing the channel degrees of freedom, the small cells suppress the mutual interference, while still satisfying a minimum QoS requirement at the nearby MUEs. Note that the proposed approach does not require direct coordination from the MBS, which, in turn, can optimize its spectrum access and power allocation independently of underlaid small cell transmissions.

In a second phase, we investigate the benefits of low-overhead cooperation among MUEs and SBSs.

Here, we propose that the MUEs alleviate the interference produced by the SBSs by adjusting the MBS' power allocation and focusing the transmission only on the degrees of freedom experiencing the best channel and interference conditions. In other words, we propose that an interference-limited MUE can deliberately release those degrees of freedom, if this allows for a reduction of the interference over the degrees of freedom which remain in its use. This approach, which is akin to the modified water-filling policy [START_REF] Krikidis | Space alignment for cognitive transmission in MIMO uplink channels[END_REF], creates new transmission opportunities for the nearby SBSs.

We formulate the problem of macrocell-small cell coexistence as a coalitional game in which the SBSs and the MUEs are the players. By deciding to cooperate, the players increase their own utility in terms of achievable data rate, while accounting for both co-tier and cross-tier interference constraints.

We show that, due to the mutual interference, the utility achieved by any player is affected by the cooperative behavior of the other players in the network. As a result, the proposed small cell coalitional game is in partition form, which is a class of coalitional games significantly different than classical characteristic form games, widely studied in wireless networks [START_REF] Duan | Contract-based cooperative spectrum sharing[END_REF], [START_REF] Barbarossa | Decentralized interference management in femtocells: A game-theoretic approach[END_REF]. We solve the considered game through the concept of a recursive core [START_REF] Kóczy | A recursive core for partition function form games[END_REF], a key solution concept for coalitional games in partition form.

In summary, our key contributions are the following:

• We design a framework in which the small cells are underlaid to a macrocell network and reuse the macrocell degrees of freedom in the space and frequency domains.

• We propose a small cell interference mitigation solution based on ID, in which the SBSs autonomously manage the interference brought to the other cooperative SBSs and the MUEs in their vicinity.

• The proposed cooperative approach takes advantage of the different nature of co-tier and cross-tier interferences. On the one hand, underlaid SBSs are mostly limited by resource availability and co-tier interference. Hence, it is beneficial to mitigate the interference while keeping the small cell transmissions confined in a limited frequency band different from the one used by the nearby MUEs. On the other hand, the cooperative SBSs' transmissions are required to satisfy the QoS requirements of the MUEs in proximity.

• We model a small cell cooperative behavior using a game theoretical approach, by formulating a coalitional game in which MUEs and SBSs are the players. The benefits from cooperation are quantified in terms of improved achievable data rates.

• By leveraging the solution of modified water-filling power allocation, we propose a protocol for implicit cross-tier cooperation which does not involve direct coordination between the macrocell and the small cell tiers. The proposed protocol enables the MUEs to capitalize on the release of some degrees of freedom with the reduction of the received interference.

• We present a distributed coalition formation algorithm through which MUEs and SBSs take autonomous decisions on the selection of a cooperative strategy and reach a stable solution.

The rest of this paper is organized as follows. In Section II, we describe the considered system model and analyze the limitations of the non-cooperative approach. In Section III we describe the cooperative behavior of MUEs and SBSs for mutual interference management. In Section IV we model the cooperative framework as a coalitional game, discuss its properties and provide a distributed algorithm for performing coalition formation. Numerical results are discussed in Section V and finally conclusions are drawn in Section VI. frequency subchannel, over which d n signal streams are modulated and transmitted 1 . As a result, for each time instant, the discrete received signal at the MUE n is given by:

Notations

y n = H 0n V n s n + k∈K Φn H kn V k s k + z n , (1)
where 2 . In such a setting, we consider that the MBS optimizes its transmissions by neglecting the existence of the small cell tier, and thus, it does not account for the interference generated by the SBSs. In turn, the SBSs are required to adapt their transmission schemes to the current macrocell spectrum allocation so as to control the interference brought to the nearby MUEs and the 1 Nevertheless, the proposed solution can accommodate multiple subchannel allocation schemes in the macrocell tier, without loss of generality.

K Φn = {k ∈ K : Φ k ∩ Φ n = ∅}
other SUEs. Through this assumption, which is common in non-cooperative networks [START_REF] Barbarossa | Decentralized interference management in femtocells: A game-theoretic approach[END_REF], [START_REF] Amir | Opportunistic interference alignment for multiuser cognitive radio[END_REF], [START_REF] Wu | Mimo active interference alignment for underlay cognitive radio[END_REF], the macrocell tier can optimize its own transmissions while remaining oblivious of the underlaid small cell transmissions, which allows for higher scalability of the small cell tier. Accordingly, the MBS performs a classical water-filling power allocation over the set of antennas A k as in [START_REF] Tse | Fundamentals of Wireless Communications[END_REF]Section 7.1.1], based the knowledge of the channel realizations H 0n . Finally, the data rate at MUE n is computed by transforming the MIMO channel to d n parallel channels, in which one signal stream is transmitted, and can be expressed as [START_REF] Nosrat-Makouei | User admission in mimo interference alignment networks[END_REF]:

R n = dn d=1 log 1 + γ n d /d n e d (V † n H † 0n G n H 0n V n ) -1 + I K n e † d , (2)
where

γ n d = P n d σ 2 , γ k d = P k d σ 2 , e d is the d-th column of 1 dn and G n = (1 An -b n b † n )
denotes the matrix of the projection into the nullspace of the interference subspace of MUE n, which is identified by the non-unique basis b n . In addition,

I K n = k∈K Φn γ k d d k Q n H kn V k V † k H † kn Q †
n denotes the covariance of the interference brought to MUE n by the co-channel SBSs and [Q n ] dn×An is the respective post-processing matrix at the MUE's side.

From the small cell perspective, spectrum access is carried out in an uncoordinated fashion at each SBS. This implies that, in order to transmit a signal s k ∈ C d k ×1 , an SBS k selects a set Φ k of frequency subchannels, which are potentially affected by both co-tier and cross-tier interference. In this context, a traditional frequency modulation technique (e.g., OFDM) requires |Φ k | = d k subchannels for the signal transmissions. Moreover, using such scheme, each SBS needs to perform additional operations for interference management (e.g., power control [START_REF] Kwanghun | Optimization of femtocell network configuration under interference constraints[END_REF] or bandwidth partitioning [START_REF] Bharucha | Dynamic resource partitioning for downlink femto-to-macro-cell interference avoidance[END_REF]). In contrast, a spatial coding technique (e.g., interference draining or alignment) allows multiple streams to be transmitted With these considerations in mind, for a transmission from an SBS k to one of its SUEs i ∈ L k , the discrete-time received signal at the SUE i, at a given time instant, is given by:

y i = H ki V k s k + j∈K Φ k , j =k H ji V j s j + n∈N Φ k H 0i V n s n + n i , (3)
where [H ki , H ji ] A k ×B respectively denote the complex matrices of the MIMO channels coefficients between SBS k and SUE i, and the interfering link between SBS j and SUE i, over the used subchannel 3 .

K Φ k = {j ∈ K, j = k : Φ j ∩ Φ k = ∅}, N Φ k = {n ∈ N : Φ n ∩ Φ k = ∅}
s j ∈ C d k ×1 denotes the d k -dimensional signals transmitted by SBS j ∈ K Φ k .
Finally, the last summation in (3) represents the interference from the MBS transmitting to its MUE n, in which [H 0i ] An×B is the matrix of the MIMO interference channel between the MBS 0 and the SUE i. With this considerations in mind, we express the rate achieved at each SUE i ∈ L k as [START_REF] Nosrat-Makouei | User admission in mimo interference alignment networks[END_REF]:

R i = d k d=1 log 1 + γ k d /d k e d (V † k H † ki G i H ki V k ) -1 + I K i + I i N e † d , (4)
where

[Q i ] d i ×A i is the post-processing matrix at the SUE i, γ k d = P k d σ , e d is the d-th column of 1 d k and G i = (1 A k -b i b † i )
denotes the matrix of the projection into the nullspace of the interference subspace of SUE i, which is identified by the non-unique basis b i . We let

I K i = j∈K Φ k γ j d d j Q i H ji V j V † j H † ji Q † i and I N i = n∈N Φ k γ n d dn Q i H 0i V n V † n H † 0i Q † i denote

III. PROPOSED COOPERATIVE INTERFERENCE MANAGEMENT FRAMEWORK

In this section, we propose two novel cooperative mechanisms of cooperation that enable SBSs to maximize their transmission rate with a constraint on the interference brought to the macrocell tier. We initially propose an interference management scheme which relies on the small cell's self-organization capabilities. Subsequently, we extend the model by including partial cooperation from the MUE side, which, however, requires a limited feedback from the SBSs. 3 In case of |Φ k | > 1, each of the matrices [H ki , Hji] corresponds to one of the used frequency subchannel in Φ k . Here, we omit the subchannel index for the sake of a simplified notation.

A. Cooperative spatial coding techniques for small cell transmissions

According to the underlay spectrum access, small cell transmissions take place on the macrocell spectrum, while satisfying the QoS requirements of the macrocell tier. One way to let the MBS and all the SBSs simultaneously transmit on the same spectral resources is to require that, at each receiver (MUE or SUE) the interfering signal lies on a subspace which is orthogonal to the received useful signal.

In this respect, an IA scheme enables the transmitters to achieve high multiplexing gain (or degrees of freedom) by adequately choosing the processing matrices Q n and V k . By doing so,

Q n H kn V k = 0 and rank(Q n H 0n V n ) = d n
have to be verified by all the MUEs n and the SBSs k [START_REF] Tresch | Performance of interference alignment in clustered wireless ad hoc networks[END_REF]. The problem of constructing those processing matrices in large multi-tier networks is challenging and the complexity increases when one cannot rely on the coordination between MUEs or SBSs. In fact, this latter case has three important implications. First, the MBS precoding matrix V n remains fixed regardless of the SBSs' operations. Second, the interference at the MUE's side is generally treated as noise. Finally, due to the contention over the available transmission opportunities, the small cells are limited by the co-tier interference.

In order to apply an IA based solution and benefit from complete interference suppression, the knowledge of the cross channel information H kn is required at each SBS (e.g., it can be acquired assuming channel reciprocity [START_REF] Wu | Mimo active interference alignment for underlay cognitive radio[END_REF] or through CSI information exchange [START_REF] Pantisano | Interference alignment for cooperative femtocell networks: A game-theoretic approach[END_REF]). Furthermore, by considering that the channel coefficients in H kn are identically and independently distributed, the existence of a solution for the IA problem only depends on the dimensions of the problem (d n , A n , d k , A k , B) as discussed in [START_REF] Tresch | On spectrum sharing with underlaid femtocell networks[END_REF], [START_REF] Yetis | On feasibility of interference alignment in MIMO interference networks[END_REF]. For example, to let small cell underlaid transmissions fall in the nullspace of the MUEs signal space, the following condition on the number of antennas must be satisfied [START_REF] Nosrat-Makouei | User admission in mimo interference alignment networks[END_REF]:

A k ≥ n∈N Φ k d n + j∈K Φ k , j =k d j + d k .
(5)

As an example, if each MUE and SUE received one signal stream (i.e., representing one degree of freedom) respectively, the necessary number of transmitting antennas to suppress two interferers would be greater than or equal to three. When condition ( 5) is verified, the small cell deployment reuses the macrocell spatial degrees of freedom and the interference is avoided without modifying the operations at the MUE. This case, known a zero-touch, is of particular interest for heterogeneous networks as discussed in [START_REF] Sesia | LTE -the UMTS long term evolution[END_REF]. It can be noted that (5) incurs a limitation on the efficiency of the IA, meaning that the solution exists only for certain properties of the signal (i.e., the number of streams) and the number of antennas equipped at each transmission link. Therefore, when condition (5) is not satisfied, the SBSs can no longer resolve the interference in the spatial domain only. However, each SBS can schedule its transmissions in the spatial and frequency domains, by choosing a spatial precoding strategy and a frequency subchannel. Clearly, by adding the frequency dimension to the problem, the achievable rate depends on the frequency resource management and the scheduling policy at each SBS. We assume that each SBS k constructs the set Φ k by measuring the transmission activity over the macrocell spectrum and selecting the frequency subchannels with the least level of energy. Clearly, due to the nature of the underlay spectrum access, the SBSs compete for the transmission opportunities in space and frequency domains, while, on the other side, the MUEs remain oblivious of the underlaid small cells, and hence non-cooperative.

Although (3) includes both co-tier and cross-tier interference contributions, the downlink achievable rate is sensibly limited by the small cell-to-small cell interference, notably when the small cells are densely deployed. To overcome this limitation, we propose an approach using which interfering SBSs decide whether to join cooperative groups, i.e., coalitions, and jointly design their precoders so as to reduce the mutual interference. When condition ( 5) is verified for all the coalition members, the precoding matrices represent the IA concept solution, which can be obtained through the minimization of the interference leakage, for example [START_REF] Gomadam | Approaching the capacity of wireless networks through distributed interference alignment[END_REF]. Otherwise, when the macrocell rates decrease due to the small cell transmissions, we propose an interference draining scheme, which generalizes the concept of timebased approach in [START_REF] Zhou | A novel interference draining scheme for cognitive radio based on interference alignment[END_REF] to the case of frequency underlaid transmissions. Accordingly, two cooperative SBSs align their transmissions on mutually orthogonal interference subspaces, while maintaining a strong SIR at the MUEs in proximity. Figure 1 illustrates the considered scenario compared to the traditional transmission paradigm. The conditions for the interference draining can be summarized as follows:

∃Γ S ⊂ C B×d k , V k , V j ∈ Γ, span[Q i H ki V k s k ] ⊥ span[Q i H ji V j s j ], ∀k, j ∈ S, while H 0n V n s n H kn V k s k ≥ δ, ∀k ∈ S, (6)
where Γ S is the interference draining space of coalition S and MUE n. Note that, the first condition guarantees that the co-tier interfering components within a coalition S are mutually orthogonal to the useful signal at the respective receivers. The second condition, instead, addresses the interference experienced at the MUEs discovered by the SBSs in S and ensures that a target requirement δ of signal to interference (SIR) ratio is met. In other words, the precoders V k , k ∈ S have to verify that the interference brought to the MUEs by the underlay transmissions of the SBSs in S does not excessively deteriorate the MUEs' performance. As an alternative to δ, the impact of the cross-tier interference can also be evaluated by accommodating other metrics, such as the interference constraints [START_REF] Guler | Interference alignment for cooperative MIMO femtocell networks[END_REF], [START_REF] Kwanghun | Optimization of femtocell network configuration under interference constraints[END_REF] or the interference temperature [START_REF] Xing | Dynamic spectrum access with qos and interference temperature constraints[END_REF]. It can be noted that the case of H kn V k s k = 0 represents the IA solution, since it provides the interference suppression at MUE n, through the precoding at SBS k.

Here, we extend this concept to a coalition S of SBSs, by minimizing the interference leakage caused by the co-channel small cell transmissions, through the precoding matrices V k , k ∈ S. As a result, the problem that we are solving is analogous to construct the precoders so as to solve arg min

V k ,k∈S H kn V k s k F .
We illustrate an example of the proposed interference draining scheme by considering a coalition of two SBSs willing to solve the mutual interference, while respecting the QoS requirements of a nearby MUE. We foresee the following steps:

1) During the uplink, the cooperative SBSs j, k estimate the channels H nk , H nj .

2) The cooperative SBSs compute the matrices H kn , H jn via channel inversion (assuming channel reciprocity).

3) In the downlink, the SBS k, closest to MUE n, estimates the subspace spanned by H 0n V n s n transmissions.

4) At this point, SBSs j and k jointly compute the precoding matrices V j , V k in the interference draining subspace Γ k , i.e., that are either in the nullspace of H kn ,H jn , or that verify that the projections of H 0n V n s n on H kn V k s k and H jn V j s j are greater than δ.

As a result, the interference from members of the same coalition can be suppressed within a coalition S, yielding the following signal at SUE i ∈ L k serviced by SBS k ∈ S:

R c i = d k d=1 log 1 + γ k d /d k e d (V † k H † ki P i H ki V k ) -1 + j∈KΦ k \S γ j d dj Q i H ji V j V † j H † ji Q † i + n∈NΦ k γ n d dn Q i H 0i V n V † n H † 0i Q † i e † d , (7)
where SBS k modulates the d k signal streams over |Φ k | < d k frequency subchannels, through cooperative interference draining among the SBSs in S. Also note how, in [START_REF] Guvenc | A hybrid frequency assignment for femtocells and coverage area analysis for co-channel operation[END_REF], the residual interference is only imputable to the transmissions from the MBS and the SBSs outside the coalition S.

B. Implicit coordination scheme for MUEs and SBSs

From the small cell perspective, the underlay spectrum access implies that the performance of the MUEs operating over the same spectrum should ideally remain unaffected by transmissions in the other tiers, or at least, that the cross-tier interference remains at a tolerable level. However, it is hard to verify these conditions in absence of coordination among the macrocell and the small cell tiers [START_REF] Wu | Mimo active interference alignment for underlay cognitive radio[END_REF], [START_REF] Pantisano | Cooperative interference alignment in femtocell networks[END_REF], [START_REF] Kwanghun | Optimization of femtocell network configuration under interference constraints[END_REF], [START_REF] Barbarossa | Decentralized interference management in femtocells: A game-theoretic approach[END_REF].

In a conventional small cell deployment, the rate optimization of the macrocell transmission links is performed by the MBS without accounting on the underlaid small cell transmissions. As a matter of fact, interference-aware rate optimization is a very challenging task in macrocell-small cell networks, mainly because the MBS cannot directly estimate or measure the interference produced by an SBS to an MUE. For example, in order to implement an interference-aware power allocation in the macrocell tier, each SUE is required to measure the interference received from the nearby SBSs, compute the SIR, and convey this information to the MBS. However, It must be stressed that macrocell operations are expected to remain independent of the underlaid small cell deployments. In turn, the small cells are expected to leverage on their self-organizing nature so as to perform the spectrum access and manage the interference. In line with these considerations, we propose that the MBS performs an autonomous power allocation such as the one proposed in [32, Section 7.1.1] which does not account for the interference brought by the SBSs, and is only aimed at maximizing the macrocell achievable rate based on the channel realizations. In practice, this means that upon the knowledge of H 0n , the MBS assigns to the set of signal streams (each one uniquely identified by a frequency subchannel and a spatial direction) a vector {P n * d } ⊂ R dn×1 . Although the water-filling policy maximizes the achievable rate based on the instantaneous channel condition of each signal stream, it is insensitive of the interference suffered at the MUE. As a result, it could be more rewarding for the MUE to receive the signal streams over the degrees of freedom which are experiencing the best channel conditions and are least affected by the interference. This concept idea, which is also referred to as modified water-filling [START_REF] Krikidis | Space alignment for cognitive transmission in MIMO uplink channels[END_REF], gives the macrocell tier the flexibility to focus on the degrees of freedom which are more robust to the cross-tier interference. In other words, when a macrocell user is victim of nearby SBSs' transmissions, it can require the MBS to adjust the power allocation and produce a new transmit power vector

{P n * d } ⊂ R d * n ×1
, which focuses on the least interfered degrees of freedom d * n , while leaving the remaining degrees of freedom unutilized. Although, the procedure described above appears like an under-utilization of the available resources (i.e., the degrees of freedom), we propose to apply it only when the modified water-filling can compensate the smaller number of degree of freedoms with a higher achievable rate due to the decreased interference.

At the same time, in the small cell tier, the newly released resources represent additional transmission opportunities, which can be seized in order to adequately increase the number of degrees of freedom and relieve the congestion during the underlay spectrum access.

As a matter of fact, small cells which incorporate self-organization capabilities are capable of exploiting the unused spatial dimension of the primary link and achieve a throughput improvement, while alleviating the interference on the degrees of freedom currently used by the MUEs. It can be noted that the modified water-filling still requires the MUEs to measure the level of received interference power and to feed it back to the MBS but the mechanism of exploitation of the macrocellular degrees of freedom occurs without involving direct communication between the MUE and the neighboring SBSs.

Finally, the achievable rate for MUE n using the modified water-filling policy becomes:

R c n = d * n d=1 log 1 + γ n * d /d * n e d (V † n H † 0n G n H 0n V n ) -1 + k∈K Φn γ k d d k Q n H kn V k V † k H † kn Q † n e † d , (8)
where d * n and γ n * d = P n * d σ 2 respectively denote the number of degrees of freedom selected by the modified water-filling policy and the respective signal-to-noise ratio over the d-th stream. Note that, according to such a policy, the rate in (8) is achieved over d * n ≤ d n degrees of freedom, using transmit power levels P n * d ≥ P n d .

C. Small cell Frequency Reuse

In order to assess the efficiency of the proposed solution, we provide a comparison with a case in which small cells adopt a frequency reuse scheme. In this case, each SBS senses the macrocell spectrum and modulates its d k -dimensional signal over |Φ k | = d k distinct frequency subchannels (e.g., using an OFDM modulation technique). Clearly, under this approach, the degrees of freedom can only be achieved in the frequency domain, due to the absence of spatial coding. In addition, while the frequency reuse had the advantage of a simpler implementation, since the spectrum access only requires a preliminary sensing phase, it is instead more sensitive to the received interference. The notion of frequency reuse can be seen as complementary to the IA scheme. In fact, the former allows several transmissions to coexist in the frequency domain while underutilizing the opportunities in the spatial domain. Conversely, the latter exploits the geometrical properties of the received signal to allow the coexistence in the spatial domain, while the frequency dimension is ignored. Intuitively, the interference draining solution, which combines both aspects, can extend the range of operability of the above methods, and thus improve the small cell and macrocell coexistence to further extents. This novel concept has the benefit of solely relying on self-organization capabilities at the small cells, namely in the area of spectrum sensing and dynamic frequency subchannel occupation, which represent the technology requirements of nextgeneration cellular networks.

IV. MACROCELL-SMALL CELL COEXISTENCE AS A COALITIONAL GAME

In this section, we analytically model the small cell cooperation framework as a coalitional game in which the MUEs and the SBSs are the players. We introduce some coalitional game concepts and present the solution concept of the recursive core which show the existence of stable coalitions in the networks. Finally, we provide a distributed algorithm which converges to a stable partition.

Let Ψ = N ∪ K denote the set of the players and in the proposed game and S ⊆ Ψ a coalition in the network, i.e., a set of players which are the decision makers seeking to cooperate. Then, the macrocellsmall cell cooperation can be understood as a coalitional game in which, the SUEs form coalitions so as to coordinate the spectrum access and efficiently use the available degrees of freedom in the space and frequency domains, while the MUEs join the existing coalitions to alleviate the received interference.

The overall benefit achieved by a coalition is represented by the coalitional value v(S, Π Ψ ), which quantifies the worth of a coalition and is defined as a vector of the individual payoffs of the players in coalition S. Further, we recognize that the individual payoff x i that each player i in coalition S receives is indeed the achievable transmit rate of each SUE and MUE as per R c i and R c n in ( 7) and ( 8), respectively. According to the coalitional game theory terminology, the game under analysis belongs to the category of coalitional game in partition form with non transferable utility (NTU) [START_REF] Saad | Coalition game theory for communication networks: A tutorial[END_REF], [START_REF] Mackenzie | Game Theory for Wireless Engineers[END_REF]. The NTU property is implied by the nature of the transmit rate, which is an individual performance metric that cannot be exchanged among MUEs or SUEs. With respect to the partition form, it must be noted that the value of any coalition S strongly depends on how the players outside S have organized themselves, thus, it is affected by the formation of other distinct coalitions in the network. In other words, the performance achieved by each player (SUE or MUE) depends on the partition of the network Π Ψ (Π Ψ is a partition of Ψ). When a coalition is formed, the members jointly remodel their transmit signals in both space and frequency domain, and, to the players outside the coalition, this is seen as a change in the shape of the interference. Therefore, in the proposed model, the rate achieved by the members of any coalition S ⊆ Ψ that forms in the network depends on the cooperative or non-cooperative strategy choice at the SBSs and MUEs in Ψ \ S. Now, given two payoff vectors x, y ∈ R |Ψ| , we write x > S y if x i ≥ y i for all i ∈ S ⊂ Ψ and for at least one j ∈ S x j > y j . We also define an outcome as couple (x, Π Ψ ), where x is a payoff vector resulting from a partition Π Ψ . Finally, let Ω(Ψ, v) denote the set of all the possible outcomes of Ψ.

A. Recursive core

In order to solve the proposed coalition formation game in partition form, we will use the concept of a recursive core as introduced in [START_REF] Kóczy | A recursive core for partition function form games[END_REF] which is one of the key solution concepts for coalitional games in partition form. In essence, the recursive core is a suitable outcome of a coalition formation process that accounts for externalities across coalitions, which, in the considered game, are represented by the mutual interference between coalitions of SBSs. In order to explain the recursive core we introduce the concept of the residual game [START_REF] Kóczy | A recursive core for partition function form games[END_REF]. We use the concept of residual game to model how the rest of the network organizes itself after a coalition S has formed. Clearly, one of the main attractive properties of a residual game is the possibility of dividing any coalitional game in partition form into a number of residual games which, involving a smaller number of players, are easier to solve. Indeed, a residual game is still in partition form and it can be solved as an independent game, regardless of how it was generated. The solution of a residual game (R, v) is known as the residual core which is defined as the set of possible game outcomes, i.e., partitions of R that can be formed.

Through the concept of residual games, it is possible to analyze the cooperative behavior in large networks in a computationally easier way as the residual games are defined over a smaller set of players than the original game. Hence, the recursive core solution can be found by recursively playing residual games, which yields the following definition [START_REF] Kóczy | A recursive core for partition function form games[END_REF]Definition 2]:

Definition 2:
The recursive core of a coalitional game (Ψ, v) is inductively defined in four main steps:

1) Trivial Partition. In a network with only one player Ψ={i}, the recursive core is clearly composed by the only outcome with the trivial partition composed by the single player i: C({i} , v) = (v(i), i).

2) Inductive Assumption. As an inductive step, we assume that the residual games (R, v) with at most K -1 players have been defined and each one is associated to a residual core C(R, v).

Thus, proceeding recursively, we define the assumption A(R, v) about the game (R, v) as follows:

A(R, v) = C(R, v), if C(R, v) = ∅ ; A(R, v) = Ω(R, v), otherwise.
In other words, an assumption defines a preference on how to partition a residual game R, and it coincides with the residual core, if already defined, or with the set of any possible partition of R.

3) Dominance. We now introduce the mechanisms of selection among the possible partitions. An outcome (x, Π Ψ ) is dominated via a coalition S if for at least one (y Ψ\S , Π Ψ\S ) ∈ A(Ψ \ S, v) there exists an outcome ((y S , y Ψ\S ), Π S ∪ Π Ψ\S ) ∈ Ω(Ψ, v) such that (y S , y Ψ\S ) > S x. 4) Core Generation. Finally, the recursive core of a game of |Ψ| players is the set of undominated outcomes and we denote it by C(Ψ, v).

One can notice that a stable network partition will emerge according the concept of dominance in step 3) of Definition 2. The concept of dominance inherently captures the fact that the value of each coalition depends on the belonging partition. Hence, it can be expressed in the following way. Given a current partition Π Ψ and the associated payoff vector x, an undominated coalition S represents a deviation from Π Ψ such that the resulting outcome ((y S , y Ψ\S ), Π S ∪ Π Ψ\S ) is more rewarding for the players of S. It appears clear now that by simultaneously playing reduced games, the players organize themselves in the coalitions which guarantee the highest payoff, which is uniquely determined by the belonging partition. Thus, finally, the recursive core can be interpreted as the set of those undominated partitions.

We now analyze the stability of the recursive core solution and provide some instructions in order to guarantee it. As the players of the game under analysis are MUE and SUE which face different operation as described in Section III, the stability of the partition in the recursive core has to verify diverse conditions. With respect to the small cell tier, it can be observed that the dominant interferers SBSs are the most eligible to join a SBSs coalition. Their respective transmit rates are limited by the received signals overlapping in the frequency and spatial dimension, thus, through cooperation they would jointly construct the precoders in order to suppress the mutual interference. As a result, as long the coalitions are constructed while iteratively suppressing the interference among dominant interferers, the members will not abandon it and the coalition value will be non decreasing at each iteration. At the MUE side, when a cooperative strategy is adopted the MUE is associated with the coalition exploiting its unused degrees of freedom, although there is no direct interaction with the observed MUE and the SBSs in the coalition. Naturally, as an MUE may release its degrees of freedom only upon a feasible reduction of the received interference, the transmit rate achieved by MUE n in coalition S over the degrees of freedom d * n has to verify the condition: R c n ≥ R n .

B. Proposed Algorithm and Distributed Implementation

In the following we provide a distributed algorithm which converges to the recursive core and reflects the above considerations on how stable coalition form.

To reach a partition in the recursive core, the players in Ψ use Algorithm 1. In this algorithm, which includes the operations at both the SBS and the MUE sides, we devise three phases: Interferer discovery, small cell coalition formation, and coalition-level cooperative transmission. Initially, the network is partitioned by |Ψ| singleton coalitions (i.e., non-cooperating mobile users). During the phase of interference discovery, the MBS periodically requests Received Signal Strength Indicators (RSSIs) measurements from its MUEs to identify the presence of small cells which might cooperatively provide higher throughput. Then, based on the RSSIs, the interfering SBSs are ordered from the stronger to the weaker. Moreover, during the uplink (UL) macrocell transmissions, each SBS estimates the subspace spanned by H nk V n of any MUE n in proximity. This operation is accompanied by the assumption of reciprocity of channel H nk , to allow SBS k to estimate the interference produced at the MUE n. In the successive phase of coalition formation, each SBS selects the first interfering SBS from the ordered Algorithm 1 Distributed coalition formation algorithm for interference draining in small cell networks

Initial State at the SBS:

The network is partitioned by Π Ψ = N ∪ K with non-cooperative SBSs and MUEs.

Proposed Coalition Formation Algorithm

Phase I -Interferers Discovery 1) Based on the collected RSSIs, each SBS k discovers the interfering SBSs j, and forms an interferers list sorted by the level of interference brought to the SUEs i ∈ L k .

2) During the UL, each SBS k estimates the subspace spanned by H nk Vn from MUEs transmissions and identifies an interference draining subspace Γ k .

Phase II -Small Cell Coalition Formation

for all SBS j in the list do 1) SBS k computes a precoding matrix V k ∈ Γ k which guarantees the first draining condition in [START_REF] Gpp | Service requirements for Home Node B (HNB) and Home eNode B (HeNB)[END_REF] for all the SUEs l ∈ L j .

2) Each SBS k computes the projection of s k on the signal subspace of each of the detected MUEs n, and computes the respective SIR.

if V k verifies the second condition in (6) then

3) SBS k sequentially engages in pairwise negotiations with SBS j in the list to join coalition S.

4) Each SBS evaluates the average rate R c i of its SUE i as in (4). else 5) Current SBS j is discarded and the following SBS in the interferers list is assessed.

end if

6) The payoff is updated, accounting for the newly adopted strategy. list and computes the precoding matrix V k which verifies the first condition in [START_REF] Gpp | Service requirements for Home Node B (HNB) and Home eNode B (HeNB)[END_REF]. If also the second condition in ( 6) is verified for all the MUEs detected by the negotiating SBSs, SBS k sends a request for cooperation to its counterpart. If both SBSs mutually approve the cooperation request, they form a coalition S, and their transmissions will lay in the interference draining space Γ S . Once a coalition has formed, the member SBSs exchange information for properly model the matrices Q k , V k which realize the draining of the interference, and the channel state indicators H ji , H ki , via the X2 interface 4 .

For the MUEs, we assume that no direct cooperation with the small cell tier occurs, however, each MUE can estimate the SIR of each of the d n received signal streams. Therefore, when the SIR level at the generic stream d is lower than the average threshold δ dn , and the modified water-filling policy over the remaining degrees of freedom guarantees a higher rate, then the d-th degree of freedom is released by allocating the power over the remaining stream. As the SBSs are able to detect the dimensions of the MUE signal subspace, the newly released degrees of freedom have a beneficial impact in finding a solution which respects the QoS requirements as per [START_REF] Gpp | Service requirements for Home Node B (HNB) and Home eNode B (HeNB)[END_REF]. Further, this results in a more efficient interference management of the SBSs which, in return, spread the transmit power over a larger number of streams, and flatten the interference over a larger set of degrees of freedom.

Next, we prove the following property for our algorithm: Property 1: Using Algorithm 1, coalitions of SBSs merge together by Pareto dominance, and, thus, the resulting network partition Π Ψ is stable and lies in the recursive core C(Ψ, v) of the game.

Proof. Each distributed decision taken by an SBS defines the shape of a coalition in the network, hence, the shape of the overall network partition. Therefore, Algorithm 1 can be seen as a sequence of steps through which the SBSs sequentially transform the composition of the network partition. For example, let us assume that the network at a given step t is partitioned by Π . Note that, as each SBS gradually selects the partners among its mutual interferers without affecting the other orthogonally allocated SBSs in the network, the value of other coalitions remains unchanged. Therefore, given any two successive algorithm steps t and u, t < u, we have that

Π (t) Ψ is Pareto dominated by Π (u) Ψ . As a result, v(Π (t) Ψ ) = S∈Π (t) Ψ v(S, Π (t) Ψ ) < v(Π (u) Ψ ) = T ∈Π (u) Ψ v(T, Π (u) Ψ ).
The above sequence resulting from the proposed algorithm ensures that the overall network utility sequentially increases by Pareto dominance. Thus, at each iteration of Algorithm 1, the sum of values of the coalitions in the network increases without decreasing the payoffs of the individual SBSs. We show that as the number of possible steps of the algorithm is finite and given by the number of possible partitions of Ψ (Bell number [START_REF] Mackenzie | Game Theory for Wireless Engineers[END_REF]), Algorithm 1 converges to a final partition.

When an SBS cannot find any other deviation which is profitable by Pareto dominance, it has reached the highest payoff and then induced an undominated coalition which lies in the recursive core of the game. Clearly, the players have no incentive to deviate from the current partition, because any other possible strategy would lead to an inferior payoff. The partition in the recursive core is therefore stable since, once formed, it will not change into any other partition provided that the players are always able to modify their strategy at any time.

Therefore, the recursive core is reached by considering that only the payoff-maximizing coalitions are formed, through the concept of dominance in Definition 2. Clearly, this algorithm is distributed since the SBSs and MUEs take individual decisions to join or leave a coalition, while, ultimately reaching a stable partition, i.e., a partition where players have no incentive to leave the belonging coalition. Those stable coalitions are in the recursive core at the end of the second stage of the algorithm. Finally, once the coalitions have formed, the members of each coalition proceed to perform the interference draining operations described in Section III-A.

V. NUMERICAL RESULTS

For system-level simulations, we consider a single macrocell with a radius of 650 m within which K SUEs and MUEs, we assume that power control fully compensates for the path loss. Further simulation parameters are included in Table 1. To leverage channel variations and user positions, statistical results are averaged on a large number of simulation rounds (Monte Carlo simulations).

In Figure 2, we show the average payoff per SUE as a function of the number of MUEs in the network N, for different strategies and MIMO antenna set sizes A k × B = {2, 4} × {2, 4}. Figure 2 shows that a cooperative strategy whose solution is based on the joint interference draining leads to gains almost proportional to B. Nevertheless, as the density of MUEs grows, the average rates start decreasing as the mechanism of interference suppression approaches the maximum number of signals which can be suppressed. For instance, Figure 2 shows that the average payoff per SUE with a 4x2 MIMO antenna set resulting from the coalition formation can achieve an additional 51% gain with respect to the non-cooperative case, in a network with K = 200 SBSs and N = 120 MUEs. Therefore, we demonstrated how cooperation is beneficial to the SUEs in highly populated areas where the density of interferers (i.e., potential coalitional partners) is high.

In Figure 3, we evaluate the performance of the proposed coalition formation game model by plotting the average payoff achieved per MUE during the whole transmission time scale as a function of the number of SBSs K. We compare the performance of the proposed algorithm to that of the noncooperative case, for different number of signal streams per MUE d n = 1 -4. It can be noted that the MUE achievable rate is affected by the cross-tier interference in a way which is proportional to Proposed cooperative approach with MWF Non-cooperative approach with WF -d n =4

Non-cooperative approach with WF -d n =3

Non-cooperative approach with WF -d n =2

Non-cooperative approach with WF -d n =1 the portion of spectrum occupied. As the number of SBSs further grows, the interference brought at the MUE side justifies a cooperative approach with modified water-filling power allocation, as it grants a larger achievable rate. Hence, the MUEs will successively release the available degrees of freedom while perceiving a reduction on the received interference. For example, Figure 3 shows that by releasing 2 degrees of freedom, an MUE can gain up to 33% with respect than the non-cooperative case in a network with K = 320 SBSs and N = 150 MUEs.

In Figure 4, we observe the average number of coalitions in the network and the average size of the SBS coalitions in the recursive core for a given QoS target of δ = 12 dB at each MUE. Figure 4 shows that, for small networks, K < 40 SBSs, the SBSs have low incentive to cooperate, and, thus, the recursive core is mainly populated by singleton coalitions. Conversely, for larger network sizes (40 < K < 160 SBSs), the SBSs start to prefer a cooperative strategy, as witnessed by the increase in the average size of the coalitions. The coalition formation becomes even more preferable when the SBSs can exploit the frequency dimension as it extends the limitation of condition [START_REF] Quek | Small Cell Networks: Deployment, PHY Techniques, and Resource Management[END_REF]. Indeed, by doing so, nearby SBSs can drain the mutual interference on signal subspaces, which are mutually orthogonal among the coalition members and still respect the QoS requirement δ at the MUE close to any of the coalition members. Further, for K > 160 SBSs, also note how the IA based approach cannot accommodate new coalition members as the solution reaches a saturation point, while the interference Average coalition size under the IA+ID approach Average number of coalitions under the IA approach Average number of coalitions under the IA+ID approach Average number of coalitions under the IA approach Average number of coalitions under the IA+ID approach Average coalition size under the IA approach draining allows for additional gains reaching up to an average coalition size of 3 for a network with K = 280 SBSs, with respect to the 1.8 of the IA based approach.

Figure 5 shows the efficiency of the proposed solution in terms of percentage of interference in the desired signal signal subspace versus the number of SBSs in the network. In this figure, we show that through cooperative operations it is possible to redirect the interference over signal subspaces which are mutually orthogonal among coalition members. In a non-cooperative approach, the interference is randomly distributed over the spectrum channels and the spatial directions, so the ascendant behavior in Figure 5 is a consequence of the number of transmissions which linearly grows with K. Conversely, through the proposed approach with interference draining it is possible to control the addressed interference subspace and this allows for additional interference reduction of 17% with respect to the non-cooperative case. As the number of SBS gets larger (160 < K < 200), the spectrum becomes congested and the interference starts to occupy all the signal subspaces (i.d., the degrees of freedom) in the network, with a consequent impact decrease on the achievable gains. Finally, note how the benefit of the proposed cooperative approach grows in case of a higher tolerance of the MUEs' to the received interference.

In Figure 6, we compute the cumulative distribution function of spectral efficiency of the proposed approach for different number of antennas A k ×B = 4×4, 4×2, 2×2, in a network with N = 250 MUEs Proposed cooperative approach with IA and ID (δ = 12 dB) Proposed cooperative approach with IA and ID (δ = 8 dB) Proposed cooperative approach with IA Non-cooperative approach with unitary frequency reuse and K = 250 SBSs. This figure shows that through spatial reuse it is possible to significantly reduce the co-tier interference and achieve high spectral efficiencies. In detail, we compared a solution which is only based on the interference alignment with one that performs the interference draining in the spatial and frequency domains. It can be noted that the proposed interference draining solution results in a further improvement of 15% of the average spectral efficiency per small cell transmission, with respect to the IA solution. This is motivated by the fact that, when only an IA based solution is available, the coalition formation process reaches its saturation for smaller network sizes. Therefore, through under an IA based approach it is possible to form coalitions and solve less interfering links than under an interference draining approach.

Figure 7 shows the average spectral efficiency per small cell link as a function of the maximum transmit power P k max at each SBS, for different studied approaches, in a network with N = 150 SBSs. For low levels of transmit power P k max < 6 dBm, the performance of the ID and IA based approaches are similar, as the interference among SBS is limited. As the level of transmit power increases (6 < P k max < 16 dBm), the mechanisms of interference avoidance outperform the traditional non-cooperative frequency reuse scheme. Furthermore, it can be observed that the ID based approach allows for a more effective interference management, for higher transmit power levels, when the received interference is CDF of the spectral efficiency with IA + ID Proposed cooperative approach -MIMO 4x4 Proposed cooperative approach -MIMO 4x2 Proposed cooperative approach -MIMO 2x2 Non-cooperative approach with unitary frequency reuse -MIMO 2x2 generally the main factor of low SIRs. In fact, we observe that cooperative SBSs using an ID based approach can gain up to 35% and 89% with respect to an IA based approach and a non-cooperative case, respectively. Finally, for P k max > 16 dBm, the average spectral efficiency gains eventually decrease, being limited by the co-tier interference. In a nutshell, Figure 7 demonstrates that the proposed coalitional game model using interference draining has a significant advantage over the non-cooperative case, which increases with the MUEs' toleration to the cross-tier interference.

VI. CONCLUSIONS

In this paper, we have introduced a cooperative framework for interference mitigation in both the small cell and the macrocell tiers. We have formulated the problem as a coalitional game in partition form and proposed a distributed coalition formation algorithm that enables SBSs to independently select the most rewarding strategy, while accounting for a limitation on the interference brought to the close MUEs. We have shown that the proposed algorithm reaches a stable partition, which lie in the recursive core of the studied game. Within every formed coalition, we have proposed an interference draining scheme, which is a suitable solution for enabling multiple underlay transmissions over the same spectrum. Results have shown that the performance of underlay small cells is ultimately limited by the received interference, therefore, the proposed cooperative strategy among interfering small cells brings significant gains, in terms of average achievable rate per small cell, reaching up to 37%, relative to the non-cooperative case, for a network with 150 MUEs and 200 SBSs.

:

  In the rest of the paper, The log refers to log 2 . Bold uppercase letters (e.g., [A] a×b ) denote matrices with a rows and b columns, bold lowercase letters (e.g., a) denote column vectors and normal letters (e.g., a) denote scalars. The identity matrix is denoted by 1. The operator • F denotes the Frobenius norm. C represents the set of complex numbers and (•) † denotes the Hermitian transpose operator. II. SYSTEM MODEL Consider the downlink of a single macrocell wireless network in which K SBSs are underlaid to a tier of N MUEs. Both the MBS and the SBSs use an orthogonal frequency division multiple access (OFDMA) technique over the shared macrocell spectrum. The macrocell bandwidth is divided into non-overlapping frequency subchannels, denoted by the set Φ, and each subchannel represents the unitary spectral resource which can be assigned to each signal stream. Let K = {1, ..., K} and N = {1, ..., N} denote the sets of the SBSs and the MUEs, respectively. Every SBS k ∈ K services L k small cell users (SUEs), denoted by L k = {1, ..., L k }, over |Φ k | subchannels, in which Φ k ⊂ Φ denotes the set of such selected subchannels. Similarly, the MBS allocates a set of subchannels Φ n to each MUE n, and thus, due to the unitary frequency reuse, k∈K Φ k ∪ n∈N Φ n ⊆ Φ. The MBS and SBSs are respectively equipped with A n and A k transmitting antennas, while the MUEs and SUEs are both equipped with B receiving antennas. The MBS and each of the SBSs respectively utilize the linear precoding matrices V n ∈ C B×dn and V k ∈ C B×d k to transmit d n ≤ A n and d k ≤ A k streams to the corresponding receivers. For the sake of simplicity, we consider that each MUE n is assigned |Φ n | = 1

  over the same interference-free subchannel, thus it requires |Φ k | < d k subchannels for transmitting d k signal streams. As a result, we consider that 1 ≤ |Φ k | ≤ d k for each SBS k, as it captures two important features. First, spatial coding transmission techniques increase the spectrum efficiency of an OFDM scheme by enabling d k -dimensional signal transmissions over |Φ k | ≤ d k subchannels. Second, the co-channel interference is avoided through cooperative linear precoding at the transmitter side.

  respectively denote the subsets of SBSs and MUEs whose transmissions are interfering with SUE i over the bandwidth Φ k .

  the covariances of the interfering transmissions from the SBSs and the MBS, respectively.It can be noted that the performance of the MUEs and SUEs are limited by different factors. While the former are solely limited by the cross-tier interference, the latter face the challenges of the availability of degrees of freedom and the contention with the other uncoordinated SBSs over the transmission opportunities, which incurs severe co-tier interference.

Fig. 1 .

 1 Fig. 1. A concept model of the proposed solution compared to the traditional non-cooperative approach.

Definition 1 :

 1 Consider a network Ψ in which a subset of players S has already organized themselves in a certain partition. A residual game (R, v) is a coalitional game in partition form defined on a set of players R = Ψ \ S.

7 )

 7 Each SBS joins the SBS which ensures the maximum payoff.end forOutcome of this phase: Convergence to a stable partition Π Ψ in the recursive core.Phase III -Coalition-level CoMP transmissions1) Within each coalition, cooperative interference draining operations as described in Section III-A are initiated.Initial State at the MUE:Each MUE n controls the SIR over each of the dn signal streams.if the interference on the d-th signal leads to a SIR smaller than δ dn then MUE n executes the modified water-filling algorithm and updates the rate R c n . if R c n ≥ Rn then The d-th degree of freedom is released, and the payoff update to R c n .

  that an SBS k ∈ S ⊂ Π (t) Ψ deviates to another coalition T ⊂ Π (t+1) Ψ , which Pareto dominates S. In other words, if x and y are the payoffs vectors of coalitions S and T , respectively, x k < y k and x j ≤ y j for all j ∈ T ⊂ Π (t+1) Ψ

  SBSs and N MUEs are randomly distributed. Each SBS k ∈ K serves L k = 1 SUE scheduled over |Φ k | subchannel, adopting a closed access policy. We set the maximum transmit power per transmission at the MBS and the SBSs to P n max = 40 dBm, P k max = 20 dBm, respectively. Transmissions are affected by distance dependent path loss shadowing according to the 3GPP specifications [46]. Moreover, a wall loss attenuation of 12 dB affects SBS-to-MUE transmissions. The considered macrocell has 200 available subchannels, each one having a bandwidth of 180 KHz. The MBS and each SBS dedicate |Φ n | = 1 and |Φ k | ≤ 4 subchannels to the transmission of each MUE and SUE, respectively. For both

Fig. 2 .

 2 Fig. 2. Average individual payoff per SUE as a function of the number of MUEs, for the different studied approaches and MIMO antenna sets. δ = 12 dB, K = 200.

  SBS (K)Average downlink data rate per MUE[Kbps]

Fig. 3 .

 3 Fig. 3. Average individual payoff per MUE as a function of the number of MUEs, for the different studied approaches and MIMO antenna sets. δ = 12 dB, N = 150.

Fig. 4 .

 4 Fig. 4. Average coalition size as function of the number of SBSs, for different QoS requirements at the MUEs, expressed by δ = 12 dB and δ = 8 dB in the ID+IA and IA approaches respectively. N = 200.

  (K) Interference in the desired subspaces[%]

Fig. 5 .

 5 Fig. 5. Average percentage of interference in the desired signal subspace under different approaches versus the total number of SBSs. δ = 12dB.

Fig. 6 .

 6 Fig. 6. Cumulative distribution function of the spectral efficiency per SBS for different studied approaches and MIMO antenna sets. δ = 12 dB. N = 200, K = 200.

Fig. 7 .

 7 Fig. 7. Average spectral efficiency per SBS link vs maximum transmit power limits, for the different studied approaches. δ = 12 dB. N = 200, K = 250 A k = 4, B = 2.

  denotes the subset of the SBSs which are interfering with the macrocell transmission over Φ n . [H 0n ] An×B and [H kn ] A k ×B are complex matrices corresponding to

	the MIMO channels coefficients between the MBS denoted by the subscript 0 and MUE n, and the
	interfering link between SBS k and MUE n, respectively. s n ∈ C dn×1 represents the d n -dimensional
	signal transmitted to the MUE n. In addition, d n denotes the degrees of freedom of the transmitter-
	receiver pair (i.e., the number of transmitted signal streams), for the transmitted message. Similarly,
	s k ∈ C d k ×1 is the d k -dimensional signal pertaining to SBS k ∈ K Φn (that is interfering). Further, z n
	represents the noise vector at MUE n which is considered as a zero mean circularly symmetric additive
	white Gaussian noise (AWGN) vector with variance σ 2 . Both transmitted signals s n and s k are limited
	by the respective power constraints P n max and P k max over their signal components: dn d P n d ≤ P n max ,
	d k d P k d ≤ P k max , where P n d , P k d are the power of the d-th signal stream from the MBS to MUE n or from
	SBS k to each of its SUEs

TABLE I TABLE 1 -

 I1 SMALL CELL SYSTEM PARAMETERS

	Macrocell radius		650m		Number of antennas at the MUE, SUE	B = 2
	Small cell radius		15-25m		Max TX power at MBS (SBS): P n max (P k max )	40 dBm (20 dBm)
	Carrier frequency		2.0 GHz		Forbidden drop radius (SBS)	0.2m
	Number of SBSs		1 -360			Total Bandwidth	40 MHz
	Number of SUEs per small cell (L k )	1			Subcarrier Bandwidth	180 kHz
	Number of MUEs per macrocell	1-200			Thermal Noise Density	-174 dBm/Hz
	Minimum required SIR at each MUE: δ	8-12 dB		Path Loss Model [dB] (outdoor)	15.3 + 37.6 log 10 (d[m])
	SBS antenna gain		0 dBi		External wall penetration loss	12dB
	Forbidden drop radius (macro)	50m		Lognormal shadowing st. deviation	10 dB
	Number of antennas at the MBS (SBS)	An = {2, 4} (A k = {2, 4})	Shadowing correlation between SBSs	0
		1800
		1600
	Average downlink data rate per SUE [Kbps]	600 800 1000 1200 1400
			Proposed cooperative approach -MIMO 4x4
		400	Proposed cooperative approach -MIMO 4x2
			Proposed cooperative approach -MIMO 2x2
			Non-cooperative approach -MIMO 2x2 -Unitary frequency reuse
		1 200	30	60	90	120	150
				Number of MUEs (N)

Clearly, P n d = 0 (P k d = 0) if the MBS (SBS k) is not transmitting on the d-th degree of freedom of the wireless channel.

Nevertheless, the data exchange among neighboring SBSs can also occur via wireless link or through the wired backhaul.

Finnish foundation for technology and innovation promotion, the Nokia Foundation, the Riitta and Jorma J. Takanen Foundation, Elektrobit and Nokia Siemens Networks for supporting this work.


Philippe Biane
email: biane@univ-mlv.fr

POLYNOMIALS ASSOCIATED WITH FINITE MARKOV CHAINS

Given a finite Markov chain, we investigate the first minors of the transition matrix of a lifting of this Markov chain to covering trees. In a simple case we exhibit a nice factorisation of these minors, and we conjecture that it holds more generally.

Introduction

The famous matrix-tree theorem of Kirchhoff gives a combinatorial formula for the invariant measure of a finite Markov chain in terms of covering trees of the state space of the chain. One can provide a probabilistic interpretation of Kirchhoff's formula by lifting the Markov chain to the set covering trees of its state space, see e.g. [START_REF] Anantharam | A proof of the Markov chain tree theorem[END_REF] or [START_REF] Lyons | Probability on trees and networks[END_REF], §4.4. This yields a new Markov chain, whose transition matrix can be constructed from the transition matrix of the original Markov chain. In this paper, we investigate the first minors of this new matrix, which are polynomials in the entries of the original transition matrix. We will see that in a simple case, that of a Markov chain evolving on a ring, these polynomials exhibit a remarkable factorisation. We expect that such factorisations hold in a much more general context. This paper is organized as follows: we start in section 2 by recalling some general facts about finite Markov chains and their invariant measure. In section 3 we describe how to lift the Markov chain to its set of covering trees. In section 4 we introduce a polynomial associated to the Markov chain, and show that in the case of a Markov chain with three states it has a nice factorisation. We generalize this observation to the case of Markov chains on a ring in section 5, which contains the main result of the paper.

I would like to thank Jim Pitman for pointing out reference [START_REF] Lyons | Probability on trees and networks[END_REF] to me.

Finite Markov chains and invariant measures

We start by recalling some well known facts about finite Markov chains.

2.1. Transition matrix. We consider a continuous time Markov chain M on a finite set X. Let Q = (q ij ) i,j∈X be its matrix of transition rates: q ij ≥ 0 if i = j ∈ X and j q ij = 0 for all i.

2.2. Invariant measure. An invariant measure for M (more exactly, for Q) is a nonzero vector µ(i), i ∈ X, with nonnegative entries such that i µ(i)q ij = 0 for all j ∈ X. An invariant measure always exists, it is unique up to a multiplicative constant if the chain is irreducible.

q ij = l∈p -1 (j)
r kl then p(N ) is a Markov chain on X with transition rates q ij . Furthermore, if ν is an invariant measure for R, then µ defined as

(2.2) µ(i) = k∈p -1 (i) ν(k)
is an invariant measure for Q.

Oriented graph and covering trees.

To the matrix Q is associated a graph (X, E) with X as vertex set, and E as edge set, such that there is an edge from i to j if and only if q ij > 0. This graph is oriented, has no multiple edges, and no loops (edges which begin and end at the same vertex). Let i ∈ X, a covering tree of (X, E), rooted at i is an oriented subgraph of (X, E) which is a tree and such that, for every j ∈ X, there is a unique path from j to i in the graph (paths are oriented). The Markov chain is irreducible if and only if for all i, j ∈ X there exists a path from i to j in the graph (X, E). If this is the case then for every vertex i ∈ X there exists a covering tree rooted at i. Figure 1 shows an oriented graph, together with a covering tree rooted at the shaded vertex (beware that a Markov chain corresponding to this graph is not irreducible).

2.5. Kirchhoff 's matrix tree theorem. We assume that the Markov chain is irreducible. For i ∈ X let Q (i) be the matrix obtained from Q by deleting row and column i and let µ(i) = det(-Q (i) ), then it is well known, and easy to see that µ is an invariant measure for Q. Indeed, if Q (ij) is obtained by deleting row i and column j, then det(-

Q (ij) ) = det(-Q (ii) ) = det(-Q (i)
), since the sum of each line is 0, and det(-Q) = i q ij det(-Q (ij) ) = 0 for all j, by expanding the determinant along columns. That µ has positive entries follows from irreducibility and Kirchhoff's formula:

(2.3) µ(i) = t∈Ti π(t) j i
The tree s j i

The tree t where the sum is over the set T i of oriented covering trees of X, rooted at i, and π(t) is the product of the q kl over all oriented edges (k, l) of the tree t. See [START_REF] Lyons | Probability on trees and networks[END_REF], §4. More generally, if {i 1 , . . . , i k } ⊂ X, then Kirchhoff's formula also applies to the determinant of the matrix obtained from Q by deleting columns and rows indexed by i 1 , . . . , i k . This determinant is equal, up to a sign, to the sum over oriented covering forests, rooted at i 1 , . . . , i k , of the product over edges of the forest.

Lifting the Markov chain to its covering trees

3.1. The lift. Notations are as in the preceding section furthermore we assume that Q is irreducible. The set of oriented covering rooted trees of (X,

E) is T = ∪ i∈X T i .
Let the map p : T → X assign to each tree t its root (i.e. p maps T i to i). There exists an irreducible Markov chain on T whose image by p is a Markov chain on X with transition rates Q, and the vector (π(t)) t∈T is an invariant measure for this Markov chain. In particular by (2.2) the invariant measure π projects by p to the invariant measure µ and this construction provides a probabilistic interpretation of Kirchhoff's formula (2.3). This Markov chain can be described by its transition rates r st , s, t ∈ T . Let s be a covering tree of X, rooted at i, and let j ∈ X be such that q ij > 0. There is a unique edge of s coming out of j. Take out this edge from s and then add the edge (i, j). One obtains a new oriented tree t, rooted at j (see Figure 2 for an example). One puts then r st = q ij . For all pairs s = t which are not obtained by this construction, one puts r st = 0. This defines a unique matrix of transition rates (r st ) s,t∈T .

It is clear that these transitions define a Markov chain which projects onto M by the map p.

Theorem 3.1. The Markov chain with transition rates R is irreducible, and the vector π is an invariant measure for this Markov chain.

The proof can be found in [START_REF] Anantharam | A proof of the Markov chain tree theorem[END_REF].

3.2. An example. Let X = {1, 2, 3} and Q =   λ a w u µ b c v ν   with λ = -a -w, µ = -b -u, ν = -c -v.
We assume that a, b, c, u, v, w > 0. The graph (X, E) looks as follows:

1 3 2 w c v b u a
Each covering rooted tree t can be indexed by the monomial π(t). There are nine such covering trees: first cu, uv, bc rooted at 1, then av, ac, vw rooted at 2, and finally uw, bw, ab rooted at 3. With this ordering of T , the transition matrix for the lifted Markov chain is

R =                 λ 0 0 0 a 0 w 0 0 0 λ 0 a 0 0 w 0 0 0 0 λ 0 a 0 0 w 0 0 u 0 µ 0 0 0 0 b u 0 0 0 µ 0 0 0 b 0 u 0 0 0 µ 0 b 0 c 0 0 0 0 v ν 0 0 0 0 c 0 0 v 0 ν 0 0 0 c v 0 0 0 0 ν                
Figure 3 shows the oriented graph. We have shown, for each vertex, its projection onto X (namely 1, 2, or 3) and for each oriented edge, its weight (a, b, c, u, v or w). The polynomial. We consider, as in the previous sections, an irreducible Markov chain on a finite set X with transition matrix Q and its canoncial lift to T , with transition matrix R. For t ∈ T , consider the matrix R (t) obtained from R by taking out row and column t, and let ρ(t) = det(-R (t) ), then ρ is an invariant measure for R, and gives a generating function for covering trees of the graph T . If we fix the graph (X, E), then ρ(t) is a polynomial in the variables q ij , where we keep only the pairs (i, j) forming an edge in E. Since π and ρ are invariant measures of the lifted Markov chain, they are proportional so that there exists there exists a function, Ψ(q ij ), independent of t, such that for all t ∈ T ,

ρ(t) = π(t)Ψ
Actually it is not difficult to see that Ψ(q ij ) is a polynomial. Indeed one has Ψ = ρ(t)/π(t), and π(t) is a monomial so that, by reducing, Ψ = P/m with P a polynomial and m a monomial prime with P . In particular, ρ(t) = π(t)P/m is a polynomial for all t, hence m divides π(t) for all t. But the π(t) have no common divisor, since a variable q kl cannot divide π(t) is t is rooted at k, therefore m = 1. so that Ψ is the product of all symmetric rank two minors of the matrix -Q (a symmetric minor of rank k of a matrix of size n, is the determinant of a submatrix obtained by deleting n -k rows and the n -k columns with the same indices). I have computed the polynomial Ψ for various graphs with 4 vertices and found in many cases that Ψ can be written as a product of symmetric minors of the matrix -Q. I could not compute in the case of |X| = 4 and the graph (X, E) is a complete graph, but by putting some of the variables equal to 1 to make the determinant easier to compute, the results suggest that the formula for Ψ in this case should be

Ψ = m 2 (Q) 3 m 3 (Q) 2
where m k (Q) is the product of all symmetric minors of rank k of -Q.

Based on this small evidence it seems natural to conjecture that for any irreducible graph (X, E) the polynomial Ψ should be a product of symmetric minors of the matrix -Q. Which minors appear, and what are their exponents, should depend on the graph and encode some of its geometry. By symmetry, in the case of a complete graph on n vertices, the result should be a product

n-1 k=1 m v n k k for some exponents v n k .
Guillaume Chapuy [2] has done some further computations for n = 5 and conjectured that v n k = (k -1)(n -1) n-k-1 . One can check that, at least, this gives the correct degree. In general the degree of Ψ is |T | -n, and in the case of a complete graph, |T | = n n-1 , moreover there are n k symmetric minors of rank k, which are polynomials of degree k, and

n-1 k=2 n k k(k -1)(n -1) n-k-1 = n n-1 -n
as follows easily from the binomial formula.

In the following I obtain a result for the case where the graph is a ring: X = {1, 2, . . . , n} and the edges are (i, i ± 1) (where i ± 1 is taken modulo n).

Theorem 4.1. If (X, E) is a ring of size n ≥ 3, then Ψ is the product of the symmetric minors of size n -1:

Ψ = m n-1 (Q)
The proof of Theorem 4.1, which is the main result of this paper, occupies the next section.

Proof of Theorem 4.1

In this section, (X, E) denotes a ring, namely, X = {1, 2, . . . , n} and the edges are (i, i ± 1) (here and in the sequel i ± 1 is always taken modulo n). I will illustrate this with n = 4, as in Figure 4. 5.1. Structure of the graph T . For each pair (i, j) ∈ X 2 there exists a unique covering tree of (X, E), rooted at i, which has no edge between j and j + 1. Let us denote this covering rooted tree by [i, j]. For example, if n = 4 here are the trees denoted by, respectively, [2,[START_REF] Lyons | Probability on trees and networks[END_REF] and [START_REF] Lyons | Probability on trees and networks[END_REF][START_REF] Lyons | Probability on trees and networks[END_REF] (here and in the sequel the roots are shaded):

1 2 3 4 1 2 3 4
It is easy to check that these are all covering rooted trees of (X, E), in particular |T | = n 2 . Let us now describe the structure of the graph on T induced by the lifting of the Markov chain.

First consider the trees indexed by the pairs [i, i]. The trees [i, i] and [i + 1, i + 1] are connected by an edge labelled q i,i+1 e.g.

1 2 3 4 q 34 -→ 1 2 3 4
These trees form an oriented ring in T :

[1,1] [2,2] [3,3] [4,4]
The trees indexed by pairs [i, i -1] are connected by edges labelled q i,i-1 :

1 2 3 4 q 32 -→ 1 2 3 4
They form another oriented ring:

Figure 5. The graph of T for n = 4 [1,4] [2,1] [3,2] [4,3]
There are also edges in the two directions between [i, j] and [i + 1, j], labelled by q i,i+1 and q i+1,i :

1 2 3 4 q 23 -→ ←- q 32 1 2 3 4
These form lines of length n:

[2, 1] [3, 1] [4, 1] [1, 1]
One can represent the graph T by putting two concentric oriented rings of size n, with opposite orientations, and joining the vertices of the rings by sequences of vertices connected by double edges, see Figure 3 for n = 3 and Figure 5 for n = 4: 5.2. The symmetric n -1 minors of -Q. We will use the following lemma. Proof. Let i ∈ Q, then det(-Q (i) ), the symmetric n -1 minor corresponding to i is a polynomial with degree at most one in each variable. More precisely, using Kirchhoff's formula this minor is the generating function of covering trees rooted at i and it can be written as αq i-1,i + β where α and β are polynomials of degree 0 in q i-1,i . Moreover β is a monomial since there exists a unique covering tree of (X, E) rooted at i which does not contain the edge (i -1, i). It follows that any nontrivial factorisation of this polynomial can be written as (5.1)

αq i-1,i + β = (γq i-1,i + δ)η
where γ, δ, η have degree 0 in q i-1,i and ηδ = β. In particular, η is a nontrivial monomial, therefore there exists a variable q kl which divides αq i-1,i + β, and this means that the edge (k, l) belongs to all covering trees rooted at i. Clearly this is not possible, therefore a nontrivial factorisation such as (5.1) does not exist, and the symmetric minor is a prime polynomial. 5.3. A preliminary lemma. Consider the restriction of the graph T to the sets of vertices

G = {[1, n], [2, 1], [3, 1], . . . , [n, 1], [1, 1]}
If we are in the first case then the restriction of the tree to G forms a covering forest of G, rooted at [1, n] and [START_REF] Anantharam | A proof of the Markov chain tree theorem[END_REF][START_REF] Anantharam | A proof of the Markov chain tree theorem[END_REF]. Furthermore any such forest can occur, independently of the trees A and B. It follows that the generating function of trees in case i) is a multiple of the generating function of such covering forests, which is det(-Q (1) ) by Lemma 5.2.

In case ii) the same argument as in i) can be applied, so we conclude again that the generating function of such trees is a multiple of det(-Q (1) ).

Finally in case iii) the edge ([2, 1], [1, n]) cannot belong to the tree, but a similar reasoning, this time with H instead of G, shows that the generating function of such trees is a again multiple of det(-Q (1) ).

From this, summing over all three cases, and all pairs (A, B) we conclude that det(-R ([1,1]) ), the generating function of the set of covering trees of T , rooted at [START_REF] Anantharam | A proof of the Markov chain tree theorem[END_REF][START_REF] Anantharam | A proof of the Markov chain tree theorem[END_REF], is a multiple of det(-Q (1) ). Since det(-R ([1,1]) ) = π([1, 1])Ψ and π([1, 1]) is a monomial which is prime with det(-Q (1) ) it follows that det(-Q (1) ) divides the polynomial Ψ. By symmetry, this is true of all the det(-Q (i) ), for i ∈ X and since these are distinct prime polynomials, we conclude that Ψ is a multiple of m n-1 = i det(-Q (i) ). The degree of the polynomial det(-R ([1,1]) ) is n 2 -1, the degree of m n-1 is n(n -1) and the degree of π([1, 1]) is n -1. It follows that Ψ and m n-1 are proportional.

In order to find the constant of proportionality, we consider the generating function of the covering trees of T , rooted at [n, n]. This generating function is det(-R ([n,n]) ) = π([n, n])Ψ. I claim that the coefficient of the monomial (5.2)

q n-1 n1 n-1 i=1 q n i,i+1
in det(-R ([n,n]) ) is 1. Indeed for each i ≤ n there are exactly n edges in T which are labelled q i,i+1 , and one of the edges labelled q n1 goes out of [n, n] so it cannot belong to a tree rooted at [n, n], therefore there exists at most one covering tree rooted at [n, n] whose product over labelled edges is equal to (5.2). On the other hand, one can check that, taking the graph formed with all these edges, one obtains a covering tree rooted at [n, n], see e.g. Figure 6 for the case of n = 4. It remains now to check that the coefficient of π([n, n]) i det(-Q (i) ) is 1. This follows from the fact that for each i there exists a unique covering tree of X rooted at i, whose labels are all of the form q k,k+1 . Taking the product over these trees one recovers the product (5.2).

This completes the proof of Theorem 4.1.

Final remark.

If we look at formula det(-R ([n,n]) ) = π([n, n])

n i=1 det(-Q (i) )
there is a combinatorial significance for both sides of the equality. The left hand sides is the generating function for covering trees of T rooted a [n, n] whereas the right hand side is the generating function of the n-tuples of rooted covering trees of (X, E) rooted at 1, 2, . . . , n. It would be interesting to tranform our proof of this formula into a bijective proof by exhibiting a bijection between these two sets which respects the weights. This could shed some light on the general case.

Figure 1 . 2 . 3 .

 123 Figure 1. An oriented graph, and a covering rooted tree

Figure 2 .

 2 Figure 2. Lifting a transition between i and j

Figure 3 .

 3 Figure 3. The graph T

4. 2 .Figure 4 .

 24 Figure 4. The ring (X, E) with n = 4

Lemma 5 . 1 .

 51 The symmetric n -1 minors of -Q are prime polynomials.

Figure 6 .

 6 Figure 6. The covering tree for n = 4