Sahar Hoteit

Stefano Secci

Rami Langar

Guy Pujolle

Raouf Boutaba
email: rboutaba@uwaterloo.ca

A Bankruptcy Game Approach for Resource Allocation in Cooperative Femtocell Networks

Keywords: femtocell networks, resource allocation, nucleolus, Shapley value, bankruptcy game

Femtocells have recently appeared as a viable solution to enable broadband connectivity in mobile cellular networks. Instead of redimensioning macrocells at the base station level, the modular installation of short-range access points can grant multiple benefits, provided that interference is efficiently managed. In the case where femtocells use different frequency bands than macrocells (i.e., split-spectrum approach), interference between femtocells is the major issue. In particular, congestion cases in which femtocell demands exceed the available bandwidth pose an important challenge. If, as expected, the femtocell service is going to be separately billed by legacy wire-line Internet Service Providers, strategic interference management and resource allocation mechanisms are needed to avoid performance degradation during congestion cases. In this paper, we model the resource allocation in cooperative femtocell networks as a bankruptcy game. We identify possible solutions from cooperative game theory, namely the Shapley value and the Nucleolus, and show through extensive simulations of realistic scenarios that they outperform two state-of-the-art schemes, namely Centralized-Dynamic Frequency Planning, C-DFP, and Frequency-ALOHA, F-ALOHA. In particular, the Nucleolus solution offers best performance overall in terms of throughput and fairness, at a lower time complexity.

I. INTRODUCTION

Femtocells have recently appeared as a viable solution to enable broadband connectivity in mobile access networks. Instead of redimensioning macrocells at the base station level, the modular installation of short-range and small mobile access points can grant multiple benefits. Strategically, femtocells are an attractive solution because they are easy to install, inexpensive, and with already present hardware components.

There are however technical challenges with femtocells deployment. The major issue remains, nevertheless, interference management. Interferences can occur with the macrocells as well as with neighboring femtocells, especially in suburban and urban environments. Under certain assumptions, crosslayer interference with the macrocell is manageable, while co-layer interference among femtocells requires collaboration among neighboring cells. In this context, we can often refer to as collaborative femtocell networks since coordination or cooperation mechanisms are needed between independent and opportunistic femtocells to manage reciprocal interferences and resource allocation. The independence of femtocells resides in the fact that the installation of a femtocell for residential or enterprise usages is expected to be subject to separate billing, while the opportunistic behaviour can be motivated by the attempt of each femtocell to satisfy its users, by acquiring the maximum number of resources. Therefore, inter-femto resource allocation needs to be managed via collaborative approaches that have as motivation the performance improvement for all the participating femtocells.

In this paper, we envision a strategic resource allocation among independent subscribers in collaborative femtocell networks. This is especially needed in urban environments, with a high density of femtocells, and where femtocells have different levels of interference and resource demands, and the overall demand exceeds the available bandwidth. The motivation behind our approach is that femtocell's interference level and demands volume, femtocell subscriber independence from other subscribers, as well as opportunistic behaviour of those femtocells, should be taken into account when allocating resources to users. We model such situations using cooperative game theory, which guarantees that interference management and resource allocation solutions are strategically and rationally justified. Results show that our approach grants important improvements in throughput and fairness.

The paper is organized as follows. Section II presents an overview of related works. In Section III, we analytically introduce the context of our work and formulate the problem as a bankruptcy game. Section IV describes the proposed approach, followed by a presentation of simulation results in Section V. Finally, Section VI concludes this paper.

II. RELATED WORK

Resource allocation in OFDMA femtocell networks has been considered in recent research works. The general objective of these works is the computation of efficient allocation of time-frequency resource slots, while accounting for crosslayer interference (between macrocell and femtocell users) and co-layer interference (between femtocells' users) [START_REF] Lopez-Perez | OFDMA femtocells: A roadmap on interference avoidance[END_REF]. In the following, we discuss a selection of relevant approaches proposed to solve these types of interferences.

Authors in [START_REF] Lopez-Perez | OFDMA femtocells: A roadmap on interference avoidance[END_REF] present an overview of possible approaches to manage cross-layer and co-layer interferences. Two main directions are outlined: shared spectrum and split-spectrum schemes. In the first, co-channel assignment mitigates the capacity problems of both femtocells and macrocells thanks to the use of larger spectrum, but cross-layer interference needs to be managed. In the second scheme, an orthogonal channel assignment eliminates cross-layer interference by dividing the spectrum into two independent fragments, one used by the macrocells and the other by the femtocells. For both cases of shared spectrum and split-spectrum, the authors in [START_REF] Lopez-Perez | OFDMA femtocells: A roadmap on interference avoidance[END_REF] outline the requirements of centralized approaches, called C-DFP (Centralized-Dynamic Frequency Planning), in which a subchannel broker receives demands and interference information from the femtocells and/or the macrocells, so as to compute the best resource allocation considering a tradeoff between optimality and computational complexity. In [START_REF] Chandrasekhar | Spectrum allocation in tiered cellular networks[END_REF], the authors show that with a dynamic spectrum splitting among femtocell and macrocell, the area spectral efficiency can be optimized. In their framework, within the femtocell layer an adapted version of ALOHA (for the time-frequency domain, called Frequency ALOHA, F-ALOHA), is proposed to schedule the femtocell access to the co-tier shared spectrum in a distributed fashion. However, the pseudo-random characteristic of this method can generate irrational resource allocations, because not strategically computed. A hybrid centralized/distributed approach is proposed in [START_REF] Hatoum | FCRA: Femtocell Cluster-based Resource Allocation Scheme for OFDMA Networks[END_REF], in which the authors exploit cooperation among neighboring femtocells and improve resource allocation and throughput satisfaction. First, femtocells are grouped in a distributed fashion into disjoint clusters with respect to interference maps. Then, within each cluster, resource allocation is centralized at a cluster-head that periodically optimizes the throughput satisfaction.

Recently, there has been significant interest in applying game theory to the analysis of collaborative communication networks, with the aim to identify rational strategic solutions for multiple decision-maker situations. Indeed, as opposed to mono-decision maker problems which can be solved with centralized approaches, game-theoretic approaches adopt a multi-agent perspective to account for different objective functions and/or counter objections to rationally non justified solutions [START_REF] Owen | Game Theory[END_REF]. Besides, game-theoretic approaches differ from distributed ones by setting a common rule for shared information between different agents. When the collaboration among network agents does not imply binding agreements and need just coordination, non-cooperative game theory can identify strategic solutions as a function of various types of game equilibria [START_REF] Basar | Dynamic Noncooperative Game Theory[END_REF]. When binding agreements are required to motivate cooperation, cooperative game theory allows solutions with the desirable properties of efficiency and rationality [START_REF] Myerson | Game Theory, Analysis of Conflict[END_REF].

In this paper, rather than partitioning the femtocell network topology in disjoint clusters as in [START_REF] Hatoum | FCRA: Femtocell Cluster-based Resource Allocation Scheme for OFDMA Networks[END_REF], we allow femtocells negotiate resources in multiple femtocell groups, where groups are locally detected as function of interferer femtocell neighbors. We believe that, in dense urban environments, joint online scheduling among groups of femtocells as [START_REF] Pantisano | Interference Avoidance via Resource Scheduling in TDD Underlay Femtocells[END_REF] may be counterproductive in terms of signaling overhead. Hence, we target a solution in which the resource allocation is periodically pre-computed based on changing femtocell resource demands and interference maps. In particular, we consider dense environment situations in which the overall demand is quite often higher than the available bandwidth on the shared media, which mathematically corresponds to a bankruptcy game situation [START_REF] Aumann | Game Theoretic Analysis of a Bankruptcy Problem from the Talmud[END_REF]. We investigate two solution concepts: the well-known Shapley value [START_REF] Shapley | A value for n-person games[END_REF] ; and the lessknown Nucleolus [START_REF] Schmeidler | The Nucleolus of a Characteristic Function Game[END_REF], which shows additional interesting properties in bankruptcy situations.

III. CONTEXT AND PROBLEM FORMULATION

We consider a network composed of a macrocell with several femtocell access points (FAPs) that represent residential or enterprise networks. As in [START_REF] Lopez-Perez | OFDMA femtocells: A roadmap on interference avoidance[END_REF] and [START_REF] Chandrasekhar | Spectrum allocation in tiered cellular networks[END_REF], we assume an orthogonal channel assignment that eliminates the cross-layer interference. The femtocells and the macrocell are assumed to operate using the OFDMA technology (e.g., WiMAX or LTE) whose frame structure can be viewed as time-frequency slots, also called tiles. A certain number of users is attached to each femtocell; user demands represent the required bandwidth, expressed in number of required tiles. As already mentioned, in urban dense environment, we expect that the sum of demands of the femtocells often exceeds the available resources. Therefore, our objective is to find, for such congestion situations, a strategic resource allocation that satisfies throughput expectations while controlling the interference between femto-femto users. In the following, we first present the corresponding optimization problem, then, we highlight possible alternative solutions and finally describe the properties of bankruptcy games along with possible solutions.

A. Notations

Let F be the set of femtocells in the network, d i the demand of F i ∈ F, and x i the number of allocated resources to the femtocell F i . Also, let I i be the interference set of F i , which corresponds to the set of femtocells composed of F i and the femtocells causing interference to F i . It is worth noting that interference is not symmetric since it depends on user positions. For example, consider the situation depicted in Fig. 1, with six femtocells where arrow's direction indicates the femtocell whose users suffer from a neighboring femtocell interference. The corresponding interference relationships are reported in Table I.

B. Related centralized optimization problem

For the sake of comparison with common approaches for resource allocation between non-independent femtocell networks, let us show how the resource allocation problem could be formulated as a centralized mono decision-maker optimization problem, i.e., as the C-DFP approaches mentioned in Section II. If femtocells are not independent, a centralized node may solve the problem as:

objective f (d i , x i ) subject to 0 ≤ x i ≤ d i , ∀F i ∈ F j|Fj ∈Ii x j ≤ E, ∀I i x i ∈ Z + , ∀F i ∈ F
where E is the number of tiles in an OFDMA frame (also referred to in the following as 'estate'). The objective typically depends on the demand and the allocated resources; a common objective is the minimization of the maximum gap between the number of allocated and required tiles in each FAP (i.e., the worst case is optimized). Therefore f

(d i , x i ) = min max i ( d i -x i d i
) as proposed in [START_REF] Hatoum | FCRA: Femtocell Cluster-based Resource Allocation Scheme for OFDMA Networks[END_REF]. The constraints are integrity constraints, on the allocated tiles to individual femtocells and to femtocells belonging to same interference sets. Later, we compare game-theoretic approaches to this C-DFP solution highlighting the interest in strategic approaches and stressing the tradeoffs between them.

C. Possible distributed approaches

For each interference set, we have therefore a situation in which a group of femtocells can either: (i) randomly access the spectrum hoping that collision will not occur (e.g., as in F-ALOHA [START_REF] Chandrasekhar | Spectrum allocation in tiered cellular networks[END_REF] ); or (ii) self-organize to define an online joint scheduling (as in [START_REF] Pantisano | Interference Avoidance via Resource Scheduling in TDD Underlay Femtocells[END_REF]); or (iii) divide the available spectrum proportionally. Clearly, (i) excludes any form of coordination and would favor opportunistic wealth-aversive behaviors (e.g., setting a minimum waiting time upon collision in F-ALOHA) that other femtocells can not control. Approaches like (ii) risk to generate enormous signaling for large interference sets (likely in urban dense environments). Under (iii), inefficiency can arise whether many demands are less than the proportional share, and a weighted proportional share would favor cheating demands (higher claims than what is really needed). The path forward is therefore towards cooperative approaches that dissuade malicious behaviors in setting demands, under an adequate binding agreement fixing common rules on shared information and allocation scheme, i.e., our algorithm to compute the allocation, and possibly also the implementation of node blacklisting mechanisms. Before detailing the proposed algorithmic approach, let us introduce the bankruptcy game that can model interactions among femtocells.

D. Bankruptcy game modeling

In urban environments, a dense deployment of femtocells is expected, so that situations in which the overall resource tile claim (i.e., sum of the demands) surpasses the number of available tiles (E) in the shared spectrum are likely. Assuming that femtocells belonging to the same interference set, share information about respective demands, the interaction can be modeled as a cooperative game. The choice of the game characteristic function, representing the profit attributed to each coalition of players in a canonical coalitional game, is an important tiebreak. We stay under the assumption that a coalition S of femtocells, within the same given interference set I i , group apart so as to decide among them how to share the spectrum. In the most pragmatic case, they will be able to share what the other femtocells have left after getting what they claimed. That is, E -i∈N \S d i , where N ≡ I i . In order to avoid secessions, the utility or characteristic function of the game should be superadditive [START_REF] Owen | Game Theory[END_REF], that is, the best coalition should be the grand coalition grouping all femtocells in the same interference set. Such a characteristic function corresponds, in fact, to what is known as 'bankruptcy game' precisely defined hereafter.

Definition III.1. A bankruptcy game [START_REF] Aumann | Game Theoretic Analysis of a Bankruptcy Problem from the Talmud[END_REF] is defined as G(N , v) where N represents the claimants of the bankruptcy situation and v is the characteristic function given in (1) that associates to each coalition its worth defined as the part of the estate not

Femtocell

Interferers

F 1 {F 2 , F 3 } F 2 {F 1 , F 4 } F 3 {F 1 } F 4 {F 2 , F 5 } F 5 {F 4 , F 6 } F 6 {F 4 }

TABLE II INTERFERENCE SETS

Steps

Femtocell sets

1 {F 1 , F 2 , F 3 } 2 {F 1 , F 2 , F 4 } 3 {F 4 , F 5 , F 6 } 4 {F 2 , F 4 , F 5 } 5 {F 1 , F 3 } 6 {F 4 , F 6 }
claimed by its complement. E ≥ 0 is an estate that has to be divided among the members of N and d ∈ R

|N |
+ is the claim vector such that: E < i∈N d i . This function has been proven to be superadditive [START_REF] Owen | Game Theory[END_REF]. Moreover, it satisfies the supermodularity property [START_REF] Shapley | A value for n-person games[END_REF] [START_REF] Driessen | Cooperative Games, Solutions and Applications[END_REF], stronger than the superadditivity, which means that the marginal utility of increasing a player's strategy rises with the increase in other player strategies.

v(S) = max(0, E - i∈N \S d i ) , ∀S ⊆ N \{∅} (1)

E. Possible imputation schemes

Solutions to cooperative games are essentially qualified with respect to the satisfaction of rationality constraints, desirable properties and existence conditions.

As already mentioned, a commonly adopted solution for cooperative games in networking is the Shapley value, because it shows desirable properties in terms of null player, symmetry, individual fairness, and additivity [START_REF] Shapley | A value for n-person games[END_REF]. It is computed by averaging the marginal contributions of each femtocell in the network in each strategic situation i.e., (players' permutation). Nevertheless, the Shapley value is not consistent [START_REF] Aumann | Game Theoretic Analysis of a Bankruptcy Problem from the Talmud[END_REF], in the following sense.

Definition III.2. An allocation x = (x 1 , x 2 , ...., x N ) is consistent if ∀i = j the division of x i + x j , prescribed for claims d i and d j , is (x i ; x j ). This means that no player or group of players can gain more by unilaterally deviating from a consistent solution since it will always obtain the same profit. For cooperative femtocell networks, this discourages clustering-like solutions inside an interference set. Another appealing solution concept, the Nucleolus, the unique consistent solution in bankruptcy games. The Nucleolus is the imputation that minimizes the worst inequity. It is computed by minimizing the largest excess, expressed as: e(x, S) = v(S) -j∈S x j , ∀S ⊂ N . This excess measures the amount by which the coalition S falls short of its potential v(S) in the allocation x; the Nucleolus corresponds to the lexicographic minimum imputation of all possible excess vectors.

IV. AN ALGORITHMIC GAME APPROACH

The game-theoretic approach we propose is composed of two main phases: an Interference Set Detection phase and a Bankruptcy Game Iteration phase. Formally, it represents a binding agreement between cooperating femtocell subscribers.

A. Interference Set Detection

Upon each significant change in demands or in network topology, each femtocell determines the set of interferer femtocells that cause interference to its users based on the minimum required Signal to Interference plus Noise Ratio (SINR) 1Femtocells are able to share their interference set with other femtocells in the network 2 . Next, the list of interference sets are sorted, firstly with respect to their cardinality, and secondly with respect to the overall demands, both in a decreasing fashion; i.e., first the largest sets with highest overall demands.

B. Bankruptcy Game Iteration

In the second phase, resources are eventually allocated, proceeding with solving a bankruptcy game for each interference set, following the order in the sorted list from the first phase. The rational behind such an agreement is that we first solve the most critical bankruptcy situations. Strategically, in this way we do not penalize femtocells that interfere less compared to femtocells that interfere more, as well as femtocells that claim a little compared to femtocells that claim a lot. Since a femtocell can belong to many interference sets, if it has already participated to a game in a previous game iteration, it is excluded from the next game iteration in which it appears. This corresponds in iterating a game differing in that:

• N includes only the unallocated femtocells in the set;

• the estate E is decreased by the amount already allocated to the set's femtocells. The definition of tiles assignment algorithm in OFDMA frame is out of the scope of this paper.

C. An illustrative example

We consider a femtocell network composed of six FAPs as shown in Fig. 1, where the interference relationships are represented by the arrows in the graph and reported in Table I.

To each femtocell, we associate a value representing the demand of attached users (expressed in number of tiles). The OFDMA frame is composed of E = 100 tiles. The interference set list is presented in Table II; the first step includes the players of a bankruptcy game G(N , v) where N = {F 1 , F 2 , F 3 }, and the coalitional payoffs are given in Table III; v(N ) = E = 100 since no femtocell has participated to any previous game. Table IV reports the Shapley values (rounded) as well as the detail on each femtocell's marginal contributions (columns). For the Nucleolus, one starts at an arbitrary point such that x 1 +x 2 +x 3 = 100, e.g., (50, 30, 20), as in the step-1 part of Table V. Then, one minimizes the largest excess, corresponding to coalition F 3 in our case; but, this coalition can claim that every other coalition is doing better than it is. So, one tries to improve this coalition by making x 3 larger or, equivalently, x 1 + x 2 smaller since x 3 = 100 -x 1 -x 2 (feasibility property); but, decreasing the excess of F 3 , the excess of F 1 ∪ F 2 increases at the same rate and these excesses then meet at -30, when x 3 = 30. Clearly, no allocation x can make the excess smaller than -30 since at least one of the coalitions F 3 or F 1 ∪ F 2 can have at least an We move now to the second step. In this situation we have three femtocells, F 1 , F 2 and F 4 , and among them F 1 and F 2 have already taken their required resources; the remaining resources, not assigned to F 1 and F 2 , are assigned to F 4 .

∅ 0 F 1 0 F 2 0 F 3 0 F 1 ∪ F 2 40 F 1 ∪ F 3 30 F 2 ∪ F 3 10 F 1 ∪F 2 ∪F 3 100 TABLE IV SHAPLEY VALUE COMPUTATION Permutation F 1 F 2 F 3 F 1 ,F 2 ,F 3 0 40 60 F 1 ,F 3 ,F 2 0 70 30 F 2 ,F 1 ,F 3 40 0 60 F 2 ,F 3 ,F 1 90 0 10 F 3 ,F 1 ,F 2 30 70 0 F 3 ,F 2 ,
F 1 -x 1 -50 -38 -35 F 2 -x 2 -30 -32 -35 F 3 -x 3 -20 -30 -30 F 1 ∪ F 2 40-x 1 -x 2 -40 -30 -30 F 1 ∪ F 3 30-x 1 -x 3 -40 -38 -35 F 2 ∪ F 3 10-x 2 -x 3 -40 -52 -55 Step 3: Coalition e(x, S) (40, 34) (25, 49)
Then, at the third step, the total estate to distribute among femtocells is not 100 tiles any longer since F 4 has already participated to a game and obtained its resources; thus the new game is formed of two players, F 5 and F 6 , and the total payoff v(N ) is then equal to E -x 4 = 100 -26 = 74 tiles (i.e. the tiles not assigned to F 4 ), as reported in Table VI. The Shapley value computation for this second game is illustrated in Table VII. Moreover, for the Nucleolus, we obtain the step-3 part of Table V. The algorithm stops at this point since all femtocells have received their resources. As it can be noticed, the Nucleolus smoothes the maximum and the minimum allocation, preventing from extremely low and extremely high allocations for femtocells that interfere a lot and interfere a little, respectively.

V. PERFORMANCE EVALUATION

In this section, we evaluate the performance of the proposed game-theoretic approaches (i.e., Shapley value and Nucleolus). C-DFP and F-ALOHA schemes, presented in Section II, are used as benchmarks. We simulated realistic scenarios with a dense network size of 200 FAPs where, for each simulation, FAPs are randomly distributed in a 400m×400m area. We considered two interference level scenarios, a low-level one and a high-level one, based on two SINR thresholds, 10 and 25 dB, to show the impact of the interference degree on the performance metrics. Based on the SINR, the path loss model given in the A1 scenario for indoor small office and residential of WINNER for the frequency range 2-6 GHz [START_REF] Ii | Winner II Channel models[END_REF] where the path loss depends upon the number of floors and traversed walls, and with static user positions; each femtocell determines the set of its interferer femtocells depending on the received signal strength. Users are uniformly distributed within the femtocells with a maximum number of four users per femtocell. Each user uniformly generates its traffic demand that can be directly translated to a certain number of tiles, with a maximum value of 25 tiles per user. As in [START_REF] Chandrasekhar | Spectrum allocation in tiered cellular networks[END_REF], the analysis is achieved using a typical OFDMA frame (downlink LTE frame) consisting of E = 100 tiles. We note that the strategy adopted to serve the associated users to each femtocell is out of the scope of this paper, because it does not affect the outcome of the resource allocation (which is supposed to be run on a longer time-scale). We will focus on the comparison among the different strategies based on the offered throughput, the allocation fairness and the computation time.

A. Throughput analysis Fig. 2 reports the mean normalized throughput (i.e., mean ratio of the number of allocated tiles to the total demand; in the following referred to as throughput) for the two considered datasets. The game-theoretic approaches outperform the other schemes, for both interference levels. We can here appreciate how much the strategic constraints contribute in avoiding low throughputs. In particular, we can assess that:

• At low throughputs, F-ALOHA and C-DFP offer very low performance, especially in high interference level; around 3% of the femtocells obtain null throughput, and about 30% obtain a throughput less than 30%, while these numbers are roughly halved with game-theoretic approaches.

• The median throughput is always higher for the Nucleolus; e.g., in the high interference case, 55% for the Nucleolus, 47% for the Shapley value, 45% for F-ALOHA and 41% for C-DFP, and the gap between the Nucleolus and the other methods decreases at lower interference level. • At high throughputs, F-ALOHA shows a small benefit over the Nucleolus, but in all cases the median throughput of the Nucleolus is still the highest among all approaches. • Among the game-theoretic approaches, the Nucleolus persistently outperforms the Shapley value, with relevant differences at medium-low throughputs. All in all, the Nucleolus seems the most appropriate approach with respect to the offered throughput, especially in high femtocell density and high interference environments as, e.g., in urban environments with a dense deployment of femtocells. Moreover, the C-DFP approach appears as the most inadequate one, and the F-ALOHA offers low throughputs to a significant portion of femtocells.

B. Fairness analysis

We evaluate the fairness of the solutions using three aspects.

(i) with respect to the Jain's fairness index [START_REF] Jain | A Quantitative measure of fairness and discrimination for resource allocation in Shared Computer Systems[END_REF], defined as:

F I = N i=1 (x i /d i ) 2 / N N i=1 (x i /d i ) 2 (2)
reported in Table VIII. It is easy to notice that game-theoretic approaches give the highest fairness, thanks to the strategic constraints that avoid penalizing femtocells presenting low interference degree and those with lower demands.

(ii) Fig. 3 further investigates how femtocell interference degree is taken into account, illustrating the mean normalized throughput as a function of the interference degree, for high interference. We can notice clearly that the Nucleolus always outperforms the other methods. It seems appropriate to conclude that the interference degree is taken into account in a significantly different way with the Nucleolus, showing an interesting fairness performance certainly, especially desirable for urban dense environments.

C. Computation time analysis

Last but not least, it is important to assess if the overall good performance of game-theoretic approaches come at the expense of a higher time complexity. Fig. 4 reports boxplots (i.e., quartile boxes plus maximum, minimum and outliers) of the computation time for the C-DFP, Shapley value and Nucleolus for the high interference level. It is easy to notice that C-DFP has quite high computation times, on the order of dozens of seconds. A stronger dependence on the interference set size (higher for high interference levels) appears for the Shapley value, which is not surprising since the number of marginal contributions equals the factorial of the interference set size. In turn, the Nucleolus does not show any important dependence neither on the network size nor on the interference level, with a median computation time of roughly 2s for very dense high-interference environments.

VI. CONCLUSION

On the way toward fixed-mobile convergence, modern telecommunication networks are introducing novel technologies that better meet user requirements in terms of experienced quality. Femtocell offload is a promising direction to enable broadband access via legacy mobile handsets. Since femtocells are expected to be commercialized as an added-value service subject to separate billing, strategic self-organization among femtocells is needed to cooperatively manage interference and resource allocation. In this paper, we have investigated novel approaches based on the theory of cooperative games motivated by the fact that such approaches allow accounting for strategic interactions among independent and opportunistic femtocells, and by the intuition that they shall offer better performance in urban dense environments.

In particular, we presented a game-theoretic approach for strategic resource allocation in cooperative femtocell OFDMA networks. Upon detection of interference maps, the proposed approach iterates bankruptcy games from the largest interference set with highest demand to the lower sets. We motivated the adoption of solutions from coalitional game theory, the Nucleolus and the Shapley value, highlighting how their properties can help meeting performance goals. Through extensive simulations using realistic datasets, we compared the gametheoretic approaches to state-of-the-art proposals. With respect to throughput, fairness and computation time the proposed approaches outperform the others. In particular, the Nucleolus solution is strictly superior to all the others. The Nucleolus approach represents therefore a promising approach for resource allocation in future femtocell network deployments. As further work, we plan to investigate how the cooperative interaction among independent femtocell can motivate the definition and the deployment of novel future services such as inter-femtocell roaming for urban environments, depending on femtocell user mobility habits and by taking into account cheating behaviors of femtocell users.

Fig. 1 .

 1 Fig. 1. Example 6-femtocell network

  of -30. Hence, x 3 = 30 is the first component of the Nucleolus. Proceeding in the same manner, one finally obtains the Nucleolus allocation (35, 35, 30) in which no femtocell interference with the others.

Fig. 2 .

 2 Fig. 2. Throughput Cumulative Distribution Function (CDF) for the two datasets.

TABLE I INTERFERENCE RELATIONSHIPS

 IRELATIONSHIPS

In LTE networks, user feedback reports can include interferer femtocell identifiers (Physical Cell Identity)[13].

In LTE networks, this can be aggregated at, or relayed by, Home-enhanced Node B (i.e., femtocell) gateways (i.e., HeNB-GW)[14].


Silvio Traversaro

Francesco Nori

Andrea Del Prete

and Robotics). 1

Inertial parameters identification and joint torques estimation with proximal force/torque sensing

Silvio Traversaro 1 , Andrea Del Prete 2 , Serena Ivaldi 3 and Francesco Nori 1 Abstract-Classically robot force control passes through joint torques measurement or estimation. Within this context, classical torque sensing technologies rely on current sensing on motor windings and on torsion sensing on motor shaft. An alternative approach was recently proposed in [START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing. Theory and implementation on the humanoid robot iCub[END_REF] and combines wholebody distributed 6-axis force/torque (F/T) sensors, gyroscopes, accelerometers and tactile sensors (i.e. artificial skin). A further advantage of this method is that it simultaneously estimates (internal) joint torques and (external) contact forces with no need of joint redesign. As a drawback, the method relies on a model of the robot dynamics, as it consists on reordering the classical recursive Newton-Euler algorithm (RNEA). In this paper we consider the problem of the parametric identification of the robot dynamic model from embedded F/T sensors. We extend recent results on parametric identification [START_REF] Ayusawa | Identifiability and identification of inertial parameters using the underactuated base-link dynamics for legged multibody systems[END_REF] by considering an arbitrary reordering of the classical RNEA. The theoretical framework is validated on the iCub humanoid, which is equipped with both 6-axis F/T sensors and joint torque sensors. We estimated the system inertial parameters using only one F/T sensor. We used the obtained parameters to estimate the joint torques (as proposed in [START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing. Theory and implementation on the humanoid robot iCub[END_REF]) and compared the results with direct joint torque measurements, used in this context only as a ground truth.

I. INTRODUCTION

A fundamental problem in controlling torque-actuated robots is the accurate modeling of their dynamics. Depending on the performed task (e.g. control, simulation, contact detection) we can distinguish two possible approaches [START_REF] Hollerbach | Model Identification[END_REF]: in structural modeling the interest is on identifying the real inertial parameters of the robot, while in predictive modeling the interest is only on replicating the input-output behavior of the system, the input and output being some measured quantities. In structural modeling the usual approach is to excite the robot with trajectories chosen so as to be the optimal for identifying the identifiable (i.e. base) parameters [START_REF] Armstrong | Dynamics for Robot Control: Friction Modeling and Ensuring Excitation During Parameter Identification[END_REF]. In predictive modeling, the only concern is to accurately model the input-output response of the dynamical system. This has a significant implication: the interest is not in estimating the "real" parameters, but in getting parameters capable of generalizing predictions across the whole work space. Interestingly, within this context different regression techniques can be adopted, ranging from parametric [START_REF] Hollerbach | Model Identification[END_REF], semi-parametric [START_REF] Nguyen-Tuong | Using model knowledge for learning inverse dynamics[END_REF] and machine learning approaches [START_REF] Fumagalli | From Motor to Interaction Learning in robotics[END_REF]. A common task that falls within the predictive modeling category is learning inverse dynamics: inputs are positions, velocities and accelerations while outputs are joint torques.

In this paper we tackle a problem that lies in between structural and predictive modeling. We aim to relax the modeling assumptions in the procedure proposed in [START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing. Theory and implementation on the humanoid robot iCub[END_REF] to estimate joint torques from embedded 6-axis force/torque (F/T) sensors. This estimation procedure allows us to implement torque control on robots without joint torque sensing. Since most (humanoid) robots are not equipped with joint torque sensors, but have 6-axis F/T sensors, this approach opens the possibility to implement inverse-dynamics control on these "old-generation" robots. Moreover, this is interesting also for new-generation robots, which could be easily equipped with 6-axis F/T sensors, without going through the hassle of redesigning the joints to include torque sensing.

The main drawback of this method is that it relies on the inertial parameters to estimate the joint torques. The goal of this paper is to understand if and to what extent this knowledge is necessary and if we can partially retrieve it through identification procedures similar to the one proposed in [START_REF] Hollerbach | Model Identification[END_REF]. The major technical obstacle lies in the following consideration. We can use F/T measurements to estimate certain inertial parameters (known in literature as base parameters): what is the relationship between these parameters and the ones used in [START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing. Theory and implementation on the humanoid robot iCub[END_REF] to estimate (internal) joint torques and (external) contact forces? In this framework non-parametric techniques have limited appeal and therefore we pursue a parametric approach.

The structure of the paper is as follows. Section II introduces the notation. Section III presents the relationship between the base parameters and the torque estimation scheme presented in [START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing. Theory and implementation on the humanoid robot iCub[END_REF]; we show that the base parameters are sufficient for estimating internal joint torques and external wrenches from F/T measurements. Section IV proposes an on-line identification scheme to learn the base parameters and uses them to properly estimate joint torques. Section V presents a validation of the proposed methodology on the iCub platform, equipped with both F/T and joint torque sensing, the latter being used only as a ground truth for comparison.

II. NOTATION

In this paper we use the spatial vector algebra 1 as defined in [START_REF]Rigid body dynamics algorithms[END_REF]. However, we extend the notation used in [START_REF]Rigid body dynamics algorithms[END_REF] to define the concepts of topology, serialization and base link. While the topology is an intrinsic property of the structure, the serialization and the base link are arbitrary choices that affect computations. The serialization defines an order for links and joints. The base link instead induces a spanning tree that defines the directions in which forces and accelerations are propagated for computations. In the following, to simplify the notation we consider only properly connected trees with one-degree-of-freedom joints.

1) Topology: a robot is composed by N B links, which constitute the link set L, and N J = N B -1 joints, represented as unordered pairs of links contained in the joint set J.

2) Serialization: a serialization is a sequence of links and a sequence of joints, which we define as two bijections 2 :

L : 0, 1, . . . , N B -1 → L J : 1, 2, . . . , N J → J
3) Spanning tree: a spanning tree is uniquely defined by its root b ∈ L, which we call "base link" of the spanning tree. Given a spanning tree, any link l ∈ L has a unique parent λ b (l), and by abuse of notation, any joint j ∈ J has a unique parent link λ b (j) and child link µ b (j). We also define ν b (j) as the set of the links belonging to the subtree starting at joint j.

4) Spatial vectors: as in [START_REF]Rigid body dynamics algorithms[END_REF] we denote by M 6 the spatial motion vector space, i.e. the space of linear and angular velocities. Sometimes it will be useful to distinguish between the linear and the angular components of a vector v ∈ M 6 by denoting v = ω l v l . Similarly, an acceleration a is decomposed in its linear and angular components as follows ωl a l . As in [START_REF]Rigid body dynamics algorithms[END_REF] we denote by F 6 the spatial force vector space, i.e. the space of force and torques.

5) Vector transformations: the front superscript indicates the frame of reference in which a spatial vector is expressed, e.g. a f is the spatial force vector f ∈ F 6 expressed in the frame of reference a. To simplify the notation, superscripts are omitted when referred to the reference frame associated to link on which the force is acting (i.e. the spatial force vector f l ∈ F 6 acting on link l is indicated f l instead of l f l when expressed in the link l reference frame. With b X * a we denote the matrix that transforms a spatial force vector from the reference frame a to the reference frame b, i.e. b f = b X * a a f . 6) Symmetric matrix serialization: in the paper we will make use of the vech operator [START_REF] Henderson | Vec and vech operators for matrices, with some uses in jacobians and multivariate statistics[END_REF], which turns a symmetrical matrix into a vector:

vech     I xx I xy I xz I xy I yy I yz I xz I yz I zz     = [ Ixx Ixy Ixz Iyy Iyz Izz ] .
(1) 1 A brief tutorial is available in [START_REF] Featherstone | A Beginner's Guide to 6-D Vectors (Part 1)[END_REF]. 2 We chose to use two different numbering styles for links and joints to follow [START_REF]Rigid body dynamics algorithms[END_REF].

The operator ω• is defined such that ω • vech(I) = Iω:

ω• =   ω x ω y ω z 0 0 0 0 ω x 0 ω y ω z 0 0 0 ω x 0 ω y ω z   (2)

A. Floating base dynamics

We here consider the formulation of floating base dynamics as presented in [START_REF]Rigid body dynamics algorithms[END_REF]. We slightly modify the notation by including in the front subscripts a J and/or a b whenever a certain quantity depends on the choice of the joint serialization and/or on the choice of the base link. The subscript, as usual, is used to represent the fact that a certain quantity is associated with a link l ∈ L (including the base b) or with a joint j ∈ J. In classical floating base representations the spatial force at the base is assumed to be equal to zero, f b = 0, but we drop this assumption in the computations that will follow in the next sections.

b I c b,J F b b,J F b b,J H a b q + b p c b,J C = f b τ + l∈L b X * l b,J J l f x l ( 3

III. EXTERNAL CONTACT WRENCH AND INTERNAL TORQUE ESTIMATION

In this section we review the approach proposed in [START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing. Theory and implementation on the humanoid robot iCub[END_REF] to simultaneously estimate (internal) torques and (external) contact wrenches by exploiting embedded whole-body distributed F/T sensors, accelerometers, gyroscopes and tactile sensors. As represented in Fig. 1, the procedure consists in cutting the floating-base tree at the level of the (embedded) F/T sensors obtaining multiple subtrees. Each subtree can be considered as an independent articulated rigid body chain subject to the differential equation (3). Among the multiple forces acting on the subtree, we can distinguish those measured by the F/T sensors (green arrows in Fig. 1) and other unknown forces (red arrows) typically due to external contacts. By assuming one unknown force per subtree we can estimate it together with the joint torques. The procedure originally described in [START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing. Theory and implementation on the humanoid robot iCub[END_REF] consists in sensing the contact with the artificial skin and using this information to define the base β on the contact link. With this assumption (3) can be rearranged as follows:

f β τ = l∈L β X * l β,J J l f x l - β I c β,J F β β,J F β β,J H a β q + β p c β,J C
and computations efficiently performed with a classical recursive Newton-Euler algorithm rearranged according to the new base, therefore the name reordered recursive Newton-Euler algorithm (rRNEA) . Position, velocities and accelerations can be either measured or estimated from the available accelerometers, gyroscopes and joint encoders.

A. Estimation of floating base dynamics

It is well known [START_REF] Iwasaki | Identification of the inertial parameters of a humanoid robot using grounded sole link[END_REF] that the right-hand side of (3) can be rearranged linearly with respect to a vector of dynamic parameters φ. In the following, we use the front subscripts L and/or b to denote quantities that depend on the choice of the link serialization and/or on the choice of the base link. Replacing the right-hand side of equation ( 3) with its linear parametrization we have:

b,L Y n b,L Y c L φ = f b τ + l∈L b X * l J l f x l , (4)
with

φ L = φ L(0) φ L(1) . . . φ L(N B -1) ∈ R 10N B , φ l = m l m l c l vech(I O l ) ∈ R 10 ,
and:

m l mass of link l m l c l first moment of mass of link l I O l
3D rotational inertia matrix of link l

Remark: in literature, the inertia matrix is often expressed w.r.t. the center of mass of the link (written as I C [START_REF]Rigid body dynamics algorithms[END_REF]).

However, we express it w.r.t. a different reference framefixed to link l but not located at the center of mass -because otherwise the dynamic equations would not be linear in the inertial parameters.

1) Identifiable subspaces: The parametric representation of the robot dynamics (4) has been widely used to get an estimation of the dynamic parameters φ from available measurements, denoted hereafter y. Typical approaches assume null external forces (f x l = 0) and exploit either torque [3] (y = τ ) or base force [START_REF] Ayusawa | Identifiability and identification of inertial parameters using the underactuated base-link dynamics for legged multibody systems[END_REF] (y = f b ) measurements. With these assumptions, rows in (4) can be rearranged as Yφ = y and an estimation of φ can be obtained by considering repeated measurements y 1 , . . . , y N and the associated values of the regression matrix Y 1 , . . . , Y N , related as follows:

    Y 1 Y 2 . . . Y N     φ =     y 1 y 2 . . . y N     . (5)
In practice, it is well known that the matrix that multiplies φ is rank deficient regardless of the number of measured samples N . More specifically, the following null space can be defined:

N Y = {φ ∈ R 10N B : Y( b R w , v b , a b , q, q, q)φ = 0, ∀ b R w ∈ SO(3), v b , a b ∈ M 6 , q, q, q ∈ R N J }. (6)
In general the space N Y is non-empty as a consequence of fact that the columns of Y are linearly dependent for any choice of the robot position, velocity and acceleration. Only certain linear combinations of the elements of φ influence the measurements and these combinations can be obtained as φ = Bπ, being B a matrix whose columns are an orthonormal base of the so called identifiable subspace

I Y = N ⊥ Y .
It is then possible to reformulate (5) as:

    Y 1 B Y 2 B . . . Y N B     π =     y 1 y 2 . . . y N     → G N π = g N , (7)
with obvious definition for the matrix G N and the vector g N . Classically, equation ( 7) has been used for the estimation of the base parameters associated with a certain measurement y. More recently, it has been questioned whether the estimated base parameters can be used to predict other dynamic quantities different from the measurement y itself. Within this context, in [START_REF] Ayusawa | Identifiability and identification of inertial parameters using the underactuated base-link dynamics for legged multibody systems[END_REF] it was shown that base parameters associated with forces at base (y = f b ) can be used to predict joint torques τ . The result is obtained by showing that the identifiable subspace associated to b,L Y c is a subset of the one associated with b,L Y n . In the present paper we consider the problem of understanding if the base parameters associated with forces at base (y = f b ) can be used to implement the rRNEA described in Section III. Since the procedure consists in redefining the base b at the contact link, all we have to understand is the relationship between b,L Y n and β,L Y n for arbitrary choices of the base β.

B. Base parameterization of the regressor structure

In this section we discuss the structure of the matrices b,L Y n and b,L Y c in detail. With respect to previous literature we explicitly take into account how the choice of b, L and J influences the matrix structure. The reason for this new formulation lies in the fact that in the following sections we will try to understand how the identifiable subspaces associated to b,L Y n and b,L Y c change with the choice of the base b. First, we consider the dynamic equation of the generic link l ∈ L:

l f B l = I l a l + v l × * I l v l = l A B l φ l , (8)
having defined:

l A B l = 0 -(a l + ω l × v l )× ωl • +ω l × ω l • a l + ω l × v l ωl × + (ω l ×)(ω l ×) 0
and:

f B l
net spatial force acting on body l I l spatial inertia of body l a l spatial acceleration of body l v l spatial velocity of body l

In equation ( 8) we have not explicitly indicated the gravitational spatial force l f g l associated with the gravitational acceleration a g . Its contribution on the link l ∈ L can be expressed as follows:

l f g l = I l a g = l A g φ l , (9)
where:

l A g = 0 -l ag× 0 l ag 0 0 .
The net spatial force on link l ∈ L including gravity is therefore obtained by summing ( 8) and ( 9):

l f l = l f B l + l f g l = l A B l φ l + l A g φ l = A l φ l (10)
The explicit expression for b,L Y n can be derived as in [START_REF] Atkeson | Estimation of inertial parameters of manipulator loads and links[END_REF] and takes the following form:

b,L Y n = b X * L(0) A L(0) b X * L(1) A L(1) . . . . . . b X * L(N B -1) A L(N B -1) . ( 11
)
Given the joint serialization J , the generic joint j ∈ J is associated with a certain number of rows of the matrix b,L Y c . The number of rows is determined by the number of degrees of freedom. The rows associated to j ∈ J are denoted by b,L Y j c and can be computed as follows:

b,L Y j c = µ b (j) S λ b (j),µ b (j) σ L b (j, L(0)) µ b (j) X * L(0) A L(0) . . . . . . σ L b (j, L(N B -1)) µ b (j) X * L(N B -1) A L(N B -1) , ( 12
)
where σ L b (j, i) = 1 if L(i) ∈ ν b (j), 0 otherwise and S l,ι is the joint's motion subspace spatial vector defined such that v l = S l,ι ql,ι + v ι . If position, velocity and acceleration of each link of the rigid body tree are available (e.g., computed by the forward step of the RNEA), then one can calculate the dynamics regressor Y using ( 8), [START_REF] Atkeson | Estimation of inertial parameters of manipulator loads and links[END_REF] and [START_REF] Birkhoff | Lattice theory[END_REF].

IV. INERTIAL PARAMETER IDENTIFICATION AND TORQUE ESTIMATION

The rRNEA described in Section III for estimating simultaneously (internal) torques τ and (external) force f β redefines the base link according to the link on which the external force is acting. It is therefore of interest to understand the relationship between b,L Y n , b,L Y c and β,L Y n , β,L Y c for arbitrary choices of the base link β.

A. Estimation regressors identifiability

In order to simplify the notation we will indicate b,L Y n with Y b,n and similarly b,L Y c with Y b,c . In this section we prove the major theoretical result of the present paper. In practice we demonstrate that the inertial parameters used in the procedure in Section III are a subset of the base parameters associated with the regressors associated to the embedded F/T sensors. Let's call this base b and denote the associated identifiable subspace by I Y b,n . The rRNEA in Section III redefines a new base link on the link on which the unknown external wrench is acting, denoted by β. The associated base parameters are therefore identified by I Y β,n ; similarly, the inertial parameters to compute internal torques are identified by I Y β,c . What we will show in Proposition 1 is that:

I Y β,n = I Y b,n and I Y β,c ⊆ I Y b,n .
To reach this conclusion we first need another property:

Lemma 1: given two different choices b and β of the base link in a kinematic tree we have:

I Y b,n = I Y β,n . (13)
Proof: From (11) it can be easily concluded that:

Y β,n = β X *
b Y b,n and the (13) easily follows from the observation that the rigid transformation β X * b is always full rank and invertible.

Proposition 1: given two different choices b and β of the base link in a kinematic tree the induced identifiable subspaces satisfy the following properties: 14) and therefore conclude our proof.

I Y β,n = I Y b,n , I Y β,c ⊆ I Y b,n . (14
Proposition 1 mathematically proves that exactly the same inertial parameters estimated from the F/T sensor measurements can be used to estimate joint torques and external wrenches with the procedure outlined in Section III. In particular, with the F/T sensor measurements we can estimate the inertial parameters in I Y b,n being b the rigid link hosting the F/T sensor. The rRNEA redefines the base at β (contact location) and requires the inertial parameters in I Y β,c ⊆ I Y b,n to estimate the joint torques. Similarly it requires the inertial parameters in I Y β,n = I Y b,n to estimate the external wrench.

V. EXPERIMENTAL SETUP AND TESTS

In this section we present the results obtained on the iCub humanoid robot. Section V-A presents the software and Section V-B presents the experiments.

A. Software

At the best of our knowledge, no free software library is available for calculating dynamics regressors for floatingbase systems. The only two software of which we are aware are Symoro+ [START_REF] Khalil | Symoro+: a system for the symbolic modelling of robots[END_REF], which is not freely available 4 , and SymPy-Botics [START_REF] Sousa | Sagerobotics: open source framework for symbolic computation of robot models[END_REF], which is limited to chain structures. Anyway, none of them provide the torque estimation regressor used in this work. For this reason we developed the necessary algorithms and added them to the C++ iDynTree library 5 , which is freely available under the GNU GPL license. Experiments were conducted on three joints (pitch and yaw in the shoulder and elbow) 6 of the iCub left arm (see Fig. 2). These joints are equipped with joint level torque sensors. Additionally a single F/T sensor is positioned in the middle of the upper arm as represented in Fig. 2.

B. Validation

In the experiment, data from the F/T sensor were used to estimate the associated base parameters. Thanks to the theoretical results in the sections, these parameters coincides with the one used by the method in the rRNEA to obtain an estimation of the joint torques. These estimations have been compared with direct joint torque measurements, used in this framework as a ground truth. Results are presented in Fig. 3 where we reported in blue direct joint torque measurements, in red predictions using CAD parameters and in green predictions from the estimation in [START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing. Theory and implementation on the humanoid robot iCub[END_REF] supplied with the on-line estimation of the base parameters (presented in Fig. 4). At the beginning of the simulation estimated parameters are clearly not sufficiently well estimated to predict with sufficient accuracy the joint torques. This condition holds true until the arm starts moving (vertical solid black line in both Fig. 3 and Fig. 4).

During the testing trajectories, the end-effector randomly moved in Cartesian space, without any interaction with the environment. Literature on suitable choices of the exciting trajectories is extensive, but such an implementation is out of the scope of the present paper. This simpler choice is also motivated by two factors: first, we need to avoid selfcollision of the robot in a simple way; second, we need to generate trajectories similar to those produced during standard operation of the humanoid robot and our goal is to on-line estimate the parameters during standard operations. Joint velocities and accelerations have been estimated using an adaptive-window fitting algorithm [START_REF] Janabi-Sharifi | Discrete-time adaptive windowing for velocity estimation[END_REF].

VI. CONCLUSION

In this paper we presented some theoretical and numerical advances with respect to the problem of estimating joint torques from proximal force and torque (F/T) sensors. This estimation problem was originally proposed in [START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing. Theory and implementation on the humanoid robot iCub[END_REF] and it is based on the idea of exploiting the simple Newton-Euler recursion step to propagate force and torque information across a kinematic structure. The estimation relies on the knowledge of the system inertial parameters. In this paper we address the problem of estimating these parameters directly from the F/T sensor. It is in particular shown that the parameters identifiable from the F/T sensor (the so called base parameters) coincide with those used by the joint torque estimation procedure. This result has been obtained by extending some previous findings [START_REF] Ayusawa | Identifiability and identification of inertial parameters using the underactuated base-link dynamics for legged multibody systems[END_REF].

Validation of the proposed theoretical framework has been conducted on the iCub humanoid robot, which is equipped with both F/T sensors and joint torque sensing. On-line estimation of the base inertial parameters have been performed by means of F/T sensor measurements only. The estimated base parameters have been used to compute joint torques from F/T measurements as in [START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing. Theory and implementation on the humanoid robot iCub[END_REF]. Comparison with direct joint torque measurement (used in this context as ground truth) shows the efficacy of the proposed estimation procedure.

  ) where:a b spatial acceleration of the floating base f b spatial force at floating base q joint positions, depends on J but front subscript is omitted b I c composite rigid body inertia of the tree b p c spatial bias force of the composite tree τ joint torques, depends on J but front subscript is omitted f x l the external wrench acting on link l b,J F b joint Jacobian of the tree spatial momentum b,J H joint inertia matrix b,J C the bias torques considering Coriolis, centrifugal and gravitational effects b,J J l the Jacobian for link l

Fig. 1 .

 1 Fig. 1. The left picture shows the position of F/T sensors on the iCub humanoid. The right picture shows the induced iCub partitioning. Each obtained subpart can be considered an independent floating-base structure subject to an external wrench which coincides with the one measured by the F/T sensor (green arrow). Red arrows represent possible location for the unknown external wrenches.

  ) Proof: For any choice of the base, let us first observe that Y = Y n Y c implies: N Y = N Yn ∩ N Yc , and therefore: N ⊥ Y = N ⊥ Yn + N ⊥ Yc , which can be rewritten as I Y = I Yn + I Yc , using the definition (6) and the usual definition of the operator '+' on vector spaces 3 . The equation above implies that I Yn ⊆ I Y and I Yc ⊆ I Y . Recently it has been shown [2] that I Y = I Yn and therefore we can also conclude I Yc ⊆ I Yn . Now using the Lemma 1 we can consider two different choices b and β of the base link and conclude: I Y b,c ⊆ I Y b,n = I Y β,n ⊇ I Y β,c . The last equations clearly include both inclusions in (

Fig. 2 .

 2 Fig. 2. CAD drawing of the seven degree-of-freedom iCub arm used in the experiments. Three out of the four joints (two in the shoulder and one in the elbow) are sensorized with joint level torque sensors. These joints are the one considered in the proposed experiments.

Fig. 3 .

 3 Fig.3. Joint level torques (left part) and errors (right part): measured (black), estimated with CAD parameters (red) and estimated with the procedure in[START_REF] Fumagalli | Force feedback exploiting tactile and proximal force/torque sensing. Theory and implementation on the humanoid robot iCub[END_REF] supplied with identified parameters (green). The vertical gray line indicate the movement onset.

Fig. 4 .

 4 Fig. 4. The picture shows the time behavior of the base parameters estimation. The estimation is executed on-line in an iterative fashion. The onset of the movement (vertical solid black line) determines the instant at which the data from the F/T sensor become informative for the estimation problem. Convergence is quite fast and mirrors the behavior of the torques estimation in Fig. 3.

The proof is a simple linear algebra exercise. More in general, it can be proven[START_REF] Birkhoff | Lattice theory[END_REF] that vector subspaces with the operators '+', ∩ and ⊥ (the orthogonal complementary space) form an orthocomplemented lattice on which the above property corresponds to the De Morgan law.

There is however a recent partial porting on python: https://github.com/symoro/symoro

http://wiki.icub.org/wiki/IDynTree

http://wiki.icub.org/wiki/ICub joints

*This paper was supported by the FP7 EU projects CoDyCo (No. 600716 ICT 2011.2.