Jean-Marc Kelif
email: jeanmarc.kelif@orange.com

Stephane Senecal
email: stephane.senecal@orange.com

Marceau Coupechoux
email: marceau.coupechoux@telecom-paristech.fr

Impact of Small Cells Location on Performance and QoS of Heterogeneous Cellular Networks

Keywords: heterogeneous networks, small cells, location, performance, quality of service, throughput and coverage analysis

We propose an analysis of the impact of the deployment of small base stations in a wireless network constituted of macro base stations. This analysis is particularly focused on the influence of the position and the transmitting power of small base stations on the performance of the network. In this aim, we consider an analytical model for heterogeneous cellular networks, composed of macro cells and small cells. The network model framework developed allows to derive closed form formulas for the Signal to Interference plus Noise Ratio (SINR) received by a mobile, whatever its location. Moreover, the proposed analytical model is validated by numerical simulations and it is shown that it is a good approximation of the SINR. Performance and quality of service (QoS) in terms of throughput and coverage can therefore be analyzed in a simple way. It makes it possible to analyze the deployment of small cells in an existing macro cells network.

I. INTRODUCTION

One of the great challenges for wireless telecommunication operators is to answer to the exploding traffic demand, and particularly to deploy high data rates services. For the outdoor situations, a new solution known as Small Cell Networks (SCN) recently came out. Indeed, by increasing the number of cells in a given zone, a higher number of users may theoretically be served. However, a scalability problem appears: when the number of cells in a given zone increases, interference increases as well and may become a bottleneck for the performance. Moreover, when the density of transmitters increases, the increasing density of user equipments (UE) do not allow to cope with interference by using techniques based on the reuse of frequency or on spatial diversity [START_REF] Kaiser | Spatial Transmit Diversity Techniques for Broadband OFDM Systems[END_REF]. A major limitation for the use of SCN is thus the intercell interference from other small cells or from macro cells, which can be of significant amount and thus renders the network unoperable. Another interest of SCN consists in the possibility to increase the coverage and the capacity of a wireless macro cell network. This paper presents an analytical evaluation of the impact of the deployment of small cells on a network composed of macro cells. We particularly focus on performance and quality of service (QoS) in terms of throughput and coverage. Moreover, we analyze the impact of the transmitting power of small base stations. An important issue is linked to the interference induced by adding small base stations in an existing network of macro cells. Indeed, the interferences induced may have an impact on the throughput and the coverage. This requires the analysis of the Signal to Interference plus Noise Ratio (SINR). The fluid model we propose in this paper is an analytical approach which allows to easily determine SINR and performance, specifically for heterogeneous networks. Recently, articles [START_REF] Badic | Energy Efficient Radio Access Architectures for Green Radio: Large versus Small Cell Size Deployment[END_REF], [START_REF] Le Treust | Coverage games in small cells networks[END_REF] and [START_REF] Sheu | Adaptive Channel Preemption Model for Small-Cell Embedded Large-Cellular Networks[END_REF] proposed an analysis of wireless networks with small cells deployment. In reference [START_REF] Badic | Energy Efficient Radio Access Architectures for Green Radio: Large versus Small Cell Size Deployment[END_REF], the impact of reducing the cell size on the energy performance is studied. In reference [START_REF] Le Treust | Coverage games in small cells networks[END_REF], a small cell network is analyzed with cooperative power control. It shows that the system performance can be improved. In reference [START_REF] Sheu | Adaptive Channel Preemption Model for Small-Cell Embedded Large-Cellular Networks[END_REF], authors propose an analysis of the channel allocation in a network composed of small cells and macro cells. The impact of decreasing the transmitting power of the macro base stations is addressed in [START_REF] Kelif | Impact of Transmitting Power on Femto Cells Performance and Coverage in Heterogeneous Wireless Networks[END_REF], when femto base stations are deployed in an indoor environment. In [START_REF] Kelif | Impact of Transmitting Power on Femto Cells Performance and Coverage in Heterogeneous Wireless Networks[END_REF], femto base stations serve only indoor users, and macro base stations serve only outdoor users. As a consequence, femto base stations have not the possibility to serve outdoor users even if macro base stations are overloaded. Also, recent references concerning heterogeneous mobile communication networks deployment mainly address the problems and challenges of intercell interference coordination and management techniques, as shown in [START_REF] Damnjanovic | A Survey on 3GPP Heterogeneous Networks[END_REF] and [START_REF] Lopez-Perez | Enhanced Intercell Interference Coordination Challenges in Heterogeneous Networks[END_REF] for instance. The work presented in this paper deals specifically with the problem of performance and QoS estimation for heterogeneous cellular networks. This paper focuses on the SINR and throughput achievable in a given zone, in an outdoor environment composed of both small and macro cells. The users are connected to the best server base station, i.e. the one which allows the user to receive the best SINR. We first focus our study on the critical impact of the location of small base stations on the performance of the network. We then analyze the impact of the small base stations transmit power on the SINR, and the achieved throughput and coverage. In this paper, we develop an analytical fluid model for heterogeneous wireless networks, i.e. composed of two types of base stations: macro base stations (MBS) and small base stations (SBS). This model is partly based on the analytical fluid model for wireless networks proposed and validated in [START_REF] Kelif | Spatial Outage Probability for Cellular Networks[END_REF], and also through comparisons with a simulation tool developed and used at France Telecom/Orange. This model was originally developed for homogeneous networks, i.e. composed of only one type of base stations. We focus on the performance for a heterogeneous cellular network in terms of throughput, considering a LTE system with a 10MHz bandwidth (see [START_REF]3GPP TSG-RAN1#48[END_REF] and [START_REF]3GPP TSG-RAN1 WG1, LTE Downlink Performance[END_REF] for more details). The paper is thus organized as follows. In section II, we present the system model. We particularly establish the expression of the SINR via the analytical fluid model in the case of a heterogeneous network composed of macro base stations and small base stations. In section III, the scenarios and the results are described. This section analyzes the impact of the transmitting power on the throughput achieved by a mobile connected to its serving base station, when interference is induced by both small cells and macro cells. Section IV concludes the paper.

II. SYSTEM MODEL

We consider a wireless network composed of M macro cells, S small cells and U user equipments. We focus our analysis on the downlink, in the context of an OFDMA based wireless network (e.g. WiMax, LTE). Let us consider:

• M = {1, . . . , M } the set of MBS, uniformly and regularly distributed over the two-dimensional plane.

• S = {1, . . . , S} the set of SBS, uniformly and regularly distributed over the two-dimensional plane. • J sub-bands j ∈ J = {1, . . . , J} where we denote W the bandwidth of each sub-band. • Each sub-band consists in a fixed number s of subcarriers. • P (k) ij (u) the transmitted power assigned by base station k to sub-carrier i in sub-band j towards user u.

• g (k) ij (u) the propagation gain between transmitter k and user u in sub-carrier i in sub-band j. We assume that time is divided into slots. Each slot consists in a given sequence of OFDMA symbols. Since the time is slotted, transmissions within each cell do not interfere one with each other. We assume that there is no interference between sub-carriers. The total amount of power received by an UE u connected to a BS k 0 , on sub-carrier i of sub-channel j is given by the sum of : useful signal

P (k0) ij (u)g (k0) ij (u), interference due to the other transmitters k∈S∪M,k =k0 P (k) ij (u)g k ij (u)
and thermal noise N th . We consider the SINR γ ij (u) defined by:

γ ij (u) = P (k0) ij (u)g (k0) ij (u) k∈S∪M,k =k0 P (k) ij (u)g k ij (u) + N th (1)
as the criterion of radio quality. To compute the total interfering power received by an UE, we consider the fluid model network approach [START_REF] Kelif | Spatial Outage Probability for Cellular Networks[END_REF], and extend it to networks composed of MBS and SBS. As we investigate the performance issue of heterogeneous network, we consider a worst case scenario where all the subcarriers are allocated to UEs. Consequently, each sub-carrier i of the sub-band j of any station is used and interfers with the ones of other stations.

A. Analytical fluid model for homogeneous networks

The fluid model core idea consists in replacing a given fixed finite number of transmitters by an equivalent continuous density of transmitters. A similar concept was proposed in references [START_REF] Jacquet | Geometry of information propagation in massively dense ad hoc networks[END_REF] and [START_REF] Toumpis | Packetostatics Deployment of Massively Dense Sensor Networks as an Electrostatics Problem[END_REF]. These works however do not provide a simple analytical formula for the SINR and focus only on massively dense networks. Our approach deals with general networks where the inter-nodes distance may be high as it is the case for realistic mobile communication networks. The network considered is characterized by a density of interfering base stations ρ B , i.e. which use the same frequency bandwidth. The fluid model network approach, cf. [START_REF] Kelif | Spatial Outage Probability for Cellular Networks[END_REF] and [START_REF] Kelif | On the Dimensioning of Cellular OFDMA Networks[END_REF], gives a closed-form formula of the interference factor1 as a function of the location of an UE. We remind hereafter the main results of this model as described in [START_REF] Kelif | Spatial Outage Probability for Cellular Networks[END_REF] and [START_REF] Kelif | On the Dimensioning of Cellular OFDMA Networks[END_REF] (this last reference includes an extension to OFDMA). Let us consider a path gain g t,u = Kr -η , where K is a constant, P t the transmitted power, r is the distance between a transmitter t and a receiver u, and η > 2 is the path loss exponent. For an UE at a distance r from its serving base station, we can express the sum of interfering powers I(r) as:

I(r) = 2πP t Kρ B η -2 (2R c -r) 2-η (2)
where 2R c is the inter-site distance between BS. Formula ( 2) holds for all distance values between BS, and remains valid even when this distance reaches several kilometers.

B. Fluid model for heterogeneous networks

We now consider a network composed of macro cells and small cells. This network is not homogeneous since the joint distribution of macro and small cells is not homogeneous. Moreover, the transmitting powers of MBS are different than the transmitting powers of SBS. The basic idea of the model is to consider that the network is composed of two types of transmitters, each one being spatially distributed according to a given distribution, which share the same bandwidth: a spatial distribution of M macro cells of mean radius R m and a spatial distribution of S small cells of mean radius R s . Let consider P (k) ij as a constant for all i, j, k for each type of transmitter, denoted P s for a SBS and P m for a MBS. We can drop the sub-indices and analyze the interference between sub-carriers.

1) UE connected to a MBS: We can express [START_REF] Kaiser | Spatial Transmit Diversity Techniques for Broadband OFDM Systems[END_REF], for an UE connected to a macro base station denoted m 0 (i.e k 0 =m 0 ) as:

P m (u)g (m0) ij (u) m∈M,m =m0 P m (u)g (m) ij (u) + s∈S P s (u)g (s) ij (u) + N th (3)
Without any loss of generality, we consider that the SBS s 0 is located inside the coverage zone of the MBS denoted m 0 (see figure 1). We can rewrite (3), using the path gain g s,u = K s r -η (for SBS) and g m,u = K m r -η (for MBS) as:

γ(r m0 ) = r -η m0 m =m0 r -η m + KsPs KmPm (r -η s0 + s =s0 r -η s ) + N th

KmPm

(4) where r k is the distance between the UE and the transmitter k. Using the fluid model, we consider a density ρ s of SBS and ρ m of MBS. The mean distance between SBS (resp. MBS) is 2R s (resp. 2R m ). Denoting K = KsPs KmPm , we can express the SINR (4) as:

γ(r m0 ) = r -η m0 I m0 s + I m0 m + N th KmPm ( 5
)
where

I m0 m = 2πρ m η -2 (2R m -r m0 ) 2-η (6)
I m0 s = K 2πρ s η -2 (2R s -r s0 ) 2-η + Kr -η s0 ( 7
)
We denote γ 0 (r s0 ) the SINR of the UE connected to a SBS when there is no MBS and γ 0 (r m0 ) the SINR of the UE connected to a MBS when there is no SBS. Considering that the thermal noise N th is negligible, these SINRs can be expressed as (using fluid model, cf. [START_REF] Kelif | Spatial Outage Probability for Cellular Networks[END_REF]):

γ 0 (r s0 ) = (η -2)r -η s0 2πρ s (2R s -r s0 ) 2-η (8)
γ 0 (r m0 ) = (η -2)r -η m0 2πρ m (2R m -r m0 ) 2-η (9)
Using these expressions, we can rewrite (5) as:

γ(r m0 ) = γ 0 (r m0 ) 1 + Ω m (1 + γ 0 (r s0 )) (10)
where

Ω m = K s P s K m P m . ρ s ρ m . (2R s -r s0 ) 2-η (2R m -r m0 ) 2-η (11)
2) UE connected to a SBS: Following a similar way, we express (1), for an UE connected to a SBS denoted s 0 (i.e k 0 =s 0 ) as:

γ(r s0 ) = r -η s0 I s0 s + I s0 m + N th KsPs ( 12
)
I s0 m = 1 K 2πρ m η -2 (2R m -r m0 ) 2-η + 1 K r -η m0 (13)
I s0 s = 2πρ s η -2 (2R s -r s0 ) 2-η (14)
In a similar way, we can express [START_REF] Toumpis | Packetostatics Deployment of Massively Dense Sensor Networks as an Electrostatics Problem[END_REF] as:

γ(r s0 ) = γ 0 (r s0 ) 1 + Ω s (1 + γ 0 (r m0 )) (15)
using ( 8) and [START_REF]3GPP TSG-RAN1#48[END_REF] where

Ω s = K m P m K s P s . ρ m ρ s . (2R m -r m0 ) 2-η (2R s -r s0 ) 2-η (16)
3) Interest of the fluid model formula: The classical way to compute SINR is to consider the distances between the UE and each bas station (MBS and SBS). This approach results in an untractable formula which we need to approximate or to simulate. Our solution reduces the computational burden and also comes up with simple and interpretable analytical formulas (10) (15).

4) Heterogeneity of the network:

The closed form formula [START_REF]3GPP TSG-RAN1 WG1, LTE Downlink Performance[END_REF] and (15) of the SINRs are very interesting for many reasons. Indeed, they show that to calculate the SINR of an UE in a heterogeneous network, we can in a first step consider independently the SINR in a "sub-network" only composed of MBS and the SINR in a "sub-network" only composed of SBS. In a second step, we can consider the term Ω m (or Ω s ) which characterizes the impact of heterogeneity of the network. This term expresses that this impact depends on the characteristics of the system: the ratio of the density of each type of BS and their transmitting powers, the propagation parameters, the relative location of the UE to each type of transmitters. In the case of an UE connected to a SBS (resp. MBS), we notice that when Ω s → 0 (resp. Ω m → 0), γ(r s0 ) → γ 0 (r s0 ) (resp. γ(r m0 ) → γ 0 (r m0 )). This case may happen for different configurations, for example when the density ρ s of SBS becomes very high compared to ρ m , or when the ratio of the transmitting powers of MBS and SBS Pm Ps is very low. It means that the impact of the MBS becomes negligible, as if the network was only composed of SBS. Moreover, this term allows to quantify the relative impact of MBS and SBS on the SINR. Expressions [START_REF]3GPP TSG-RAN1 WG1, LTE Downlink Performance[END_REF] and ( 15) are also useful to perform an analysis of heterogeneous small-macro cell networks. These expressions represent non-trivial extensions of formula derived for a standard homogeneous network. Indeed, these analytical expressions allow to calculate in a simple way the SINR of a mobile connected to a SBS whatever its location is. They particularly enable an analysis of the impact of transmitting SBS power on performance and QoS of UEs connected to SBS.

5) Impact of SBS location:

The distances r s0 and r m0 can be expressed according to the distance d between macro and small base stations (see figure 1):

r 2 m0 = r 2 s0 + d 2 -2drcosθ,
where θ is the angle between d and r m0 . Therefore, this expression makes it possible to analyze the impact of the distance between SBS and MBS.

Remark: Let us notice that the analysis which allows to establish expressions [START_REF]3GPP TSG-RAN1 WG1, LTE Downlink Performance[END_REF] and (15) focuses on OFDMA based systems, such as WiMax and LTE, is still available for CDMA or HSPA systems.

C. Validation of the fluid model for heterogeneous networks

In this section, we propose a validation of the fluid model for the heterogeneous network presented in the last section. In this perspective, we will compare the cumulative density function (CDF) of the SINR obtained by using fluid expressions established in section II-B to those obtained numerically by simulations. Our simulator assumes a hexagonal network constituted of macro base stations. There are several rings of cells surrounding a central cell. Moreover, a small base station is located in each macro cell. The distance between the SBS and the MBS is 0.7 R m , the transmitting power are respectiveley 26 dBm (SBS) and 43 dBm (MBS). We assume a uniform distribution of UE. Figure 2 shows that the CDF calculated by using the fluid model for heterogeneous networks are very closed to the ones obtained by simulations.

D. Throughput calculation

The reachable throughput D u of an UE u can be calculated from Shannon expression. Considering a bandwidth W , we have:

D u = W log 2 (1 + γ u ) (17)
We can thus write the throughput of an UE connected to a MBS, as (using ( 10)):

D(r m0 ) = W log 2 1 + γ 0 (r m0 ) 1 + Ω m (1 + γ 0 (r s0 )) (18)
and, in a similar way, we can write the throughput of an UE connected to a SBS, as (using (15)):

D(r s0 ) = W log 2 1 + γ 0 (r s0 ) 1 + Ω s (1 + γ 0 (r m0 )) (19)
Expressions ( 18) and ( 19) enable to calculate the theoretical maximum achievable throughputs.

Remarks: Let notice that the mapping between the received SINR and the achieved throughput are established by the mean of link curves in the case of realistic network systems. The network fluid model was validated by comparisons with curves generated by 3GPP system simulator for both the case of homogeneous network and the specific case of an heterogeneous network.

III. SCENARIO AND RESULTS

We present the results obtained from the heterogeneous fluid model applied to the analysis of a macro cell network in which small cells are added. We focus on a scenario where the macro cells and small cells share the same bandwidth. Therefore, a macro cell is interfered by small cells and by the other macro cells. Our aim is to determine the interest of adding small cells in an existing MBS network, in terms of performance (SINR and throughput) and coverage, when they share the same frequency band as the macro cell network. We also analyze the impact of transmitting power and deployment of SBS. The MBS locations and features are fixed and represent constraints for the problem addressed in the paper. We aim to determine the performance in terms of throughput reached by an UE connected to the best server.

A. Assumptions

Various parameters may have an impact on the SINR, the throughput and the coverage of BSs. We present hereinafter the parameters we chose in our analysis:

• downlink OFDM LTE, carrier frequency 2.6 GHz, channel bandwidth 10MHz,

• the SBS transmitting power: we set the value of 31 dBm, for most of the experiments, • the MBS transmitting power: we set it at 43 dBm, as in a realistic transmission environment, • the pathloss parameter : η = 3.5,

• the mean distance d between MBS and SBS,

• the location of the UE from its serving base station. To illustrate the previously mentioned approach, we consider a heterogeneous network composed of macro cells and small cells. Macro cells are homogeneously placed on the network area. Small cells too. Different cases are considered corresponding to different mean distances d between MBS and SBS. The figure 3 depicts the specific case where small base stations are located at the edge of macro cells (i.e. d = R m ). The mean distance between two MBS 2R m is equal to the mean distance between two SBS 2R s (1000 meters). SBS are added in the macro cell network in the aim to increase the performance (in terms of throughput and capacity) and the coverage of the system. Therefore, we consider that a mobile is connected to the BS which offers the best signal. This is a classical connection criterion of a mobile to its serving BS, for wireless networks. The cumulative density functions (CDF) of the SINR and throughput characterize the outage probability and the performance distribution. Therefore, it is interesting to establish these CDF curves to analyze the QoS and the performance of the system. Indeed, these analyses allow to guarantee these QoS and performance results for various application types run under the network.

B. Impact of the SBS location on the SINR distribution

Firstly, we analyze the distribution of the best SINR received by an UE. At each location of the zone covered by a MBS, the SINR received from the MBS is compared to the one received from the SBS, and the station with the best SINR is chosen. The best SINR is calculated according to expression [START_REF]3GPP TSG-RAN1 WG1, LTE Downlink Performance[END_REF] or (15). Figure 4 depicts the cumulative density function (CDF) of the best SINR offered to the UE, for different distances d from the MBS, and without small cells. These curves show that when the small cells are deployed at a distance d=0.7R m or d=R m , the CDF of the SINR is improved compared to the case without SBS. However, when SBS are located at distance d=0.3R m , the CDF of the SINR is slighly deteriorated. Therefore, since the coverage of a BS is an increasing function of the SINR, adding SBS does not always improve the coverage of a BS. For the same reason, the reachable QoS, in terms of throughput and outage probability, may also increase or decrease by adding a SBS, according to its location. These results can be explained as follows. A small cell allows to locally improve the SINR of an UE. However, it also induces more interferences on macro cells signals received by UEs (see expression (4)). To understand this phenomenon, let us consider an UE connected to a MBS. When SBS are too close to MBS (in figure 4, this case happens for d=0.3R m ), these interferences have a relatively high level and, as a consequence, an UE connected to a macro BS has a lower SINR than without SBS. When SBS are far enough from MBS (in figure 4, this case happens for d=0.7R m ), these interferences are relatively low and do not have a high impact on the SINR of the UE. For instance, from figure 4 we can deduce that the presence of a small cell (SC) at the edge of the zone covered by a MBS increases the number of mobiles which reach a SINR of 10 dB by 25% (the CDF values switch from 0.6 to 0.5).

C. Impact on SINR distribution in the zone covered by SBS

This previous result is interesting since it allows to analyze the global impact of adding SBS on a MBS network. However, it cannot allow to analyze the local impact of SBS since the whole area covered by the MBS and SBS is taken into account, and not only the area covered by the SBS. Therefore, it seems interesting to analyze also the specific zone covered by added SBS. In this aim, for a heterogeneous network composed of MBS and SBS, we establish the CDF of the SINR of UEs located in the zone covered by a SBS, considering this last one as the best serving BS. Then, we compare it to the CDF of the SINR of UEs located at the same place, by considering a network only composed of MBS, i.e. when the SBS are not added (see figure 5). The figure 5 is drawn for a location of SBS at a distance d = 0.9R m from the MBS. The CDF are calculated by using expression (9) of the SINR (i.e. network without SBS, black curve) and expression (15) (i.e. network with MBS and SBS, red dotted curve). Figure 5 shows that adding SBS results in a very high improvement of the SINR, in the local zone it covers. Indeed, we first establish that, without SBS, the SINR range is between -4 and 5 dB in that zone. With SBS, the SINR range is between -4 and 30 dB. Therefore, the coverage of the system is improved. For the same reason, the reachable QoS of UEs covered by SBS, in terms of throughput and outage probability, is also highly improved by adding a SBS. For example, for a SINR of -2.5dB, the outage reaches about 35% without SBS (i.e. UE connected to MBS) and decreases until 10% with SBS. Moreover, the maximum reachable SINR is about 5 dB (without SBS) and about 30 dB (with SBS). The analysis developed allows to quantify precisely the improvement in terms of QoS, performance and coverage by adding SBS in a macro cell network.

D. Impact of the SBS transmit power

We investigate the impact of the SBS transmit power P s as we determined in expression of Ω m (16) that only the ratio Ps Pm plays a role on the SINR (and thus the throughput) as expressed in ( 18) and ( 19). Moreover the transmitting power P m of MBS is fixed as a network constraint. Figure 6 shows the CDF of the throughput in the case of a deployment of SBS at the edge of macro cells, for transmitting powers P s of SBS of 0 dBm and 20 dBm and in the case without small cells P s = -Inf dBm. It can be observed that, until an outage probability of 10 %, the CDF of the throughput is not impacted by the transmitting power of small cells. For higher values, we observe an increase of the outage probability when the transmitting power decreases. These curves also mean that the throughput performance of the system is improved when the transmitting power of small cells increases. For example, a probability of 50% is observed to reach 25 Mbits/s with P s = 20 dBm, 20 Mbits/s with P s = 0 dBm and 18 Mbits/s without small cells.

IV. CONCLUSION

In this paper, we analyzed and quantified in a simple way, the impact of adding small base stations in a network composed of macro base stations on the performance and the quality of service of the system. We considered an analytical approach for modeling networks composed of macro and small base stations. This approach allows to establish closed form expressions for the SINR of a user at any distance from its best server, which can be either a macro base station or a small base station. These expressions particularly enable to calculate in a simple way the performance and user QoS, and to analyze the coverage of heterogeneous networks. We analyzed the critical impact of small base stations locations. We showed that adding small base stations can locally improve the SINR, especially when they are located at the edges of the macro cells. In this case, the outage neither increases nor decreases. However, when the small cells are too close of the macro BS, the performance globally decreases. The analysis will be improved, in future works, by considering the shadowing impact.

Fig. 1 .

 1 Fig. 1. Model of small-macro location.

Fig. 2 .

 2 Fig. 2. CDF of the SINR for a UE connected to a MBS (left) and to a small cell (right) d = 0.7Rm.

Fig. 3 .

 3 Fig. 3. Instance of scenario deployment for d = Rm.

Fig. 4 .

 4 Fig. 4. CDF of the best SINR for different distances between MBS and SBS, and without small cell SC (black curve).

Fig. 5 .

 5 Fig. 5. CDF of the SINR in the zone covered by SBS, in the presence of SBS (red dotted line) and without SBS in the same zone (black continuous line).

Fig. 6 .

 6 Fig. 6. CDF of the mean throughput.

The interference factor is defined as the ratio between the power coming from the serving BS and the sum of other BS powers received by an UE, considering all BS transmit with power Pt.

ACKNOWLEDGMENT

The authors thank William Diego for his contribution to the work presented in this paper. This work was performed for the EU FP7 HARP project and France ANR NetLearn project.


Mikaël Touati

Rachid Elazouzi

Marceau Coupechoux

Eitan Altman

Jean-Marc Kélif

J M Kelif

R El-Azouzi

Core stable algorithms for coalition games

published or not. The documents may come

INTRODUCTION

Game theorists have been interested in looking at the stability of the structures resulting from the coalition formation process and have shown the importance of the concept in real-life applications 1 . The stability exhibits the respect of the individual preferences and incentives. An unstable structure would result in deviations [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF]. Coalition and matching games open the way through an important number of interesting applications, notably in wireless networks where much work remain to be done in the decentralized decision taking paradigm. These game-theoretic tools allow for more tractability in the formulations and a reduced complexity. Nevertheless, some of the commonly used assumptions (substitutability, responsive preferences, see [START_REF] Roth | Two-Sided Matching A Study In Game-Theoritic Modeling and Analysis[END_REF]) limit the modeling to the cases without complementarities or peer effects. Recent theoretical works [START_REF] Pycia | Stability and Preference Alignment in Matching and Coalition Formation[END_REF] (and references therein) overcame this difficulties and have paved the way through a suitable modeling of systems with complementarities and peer effects. As examples of such systems in wireless networks we have WiFi and its related anomaly, Device-2-Device with multi-hop relaying, virtual MIMO exploiting multi-users diversity, etc.

RELATED WORKS

Much work has been devoted to super-additive coalition games (where the grand-coalition forms [START_REF] Rapoportand | Theories of Coalition Formation[END_REF]) and to the stabilization of structures by payoff distribution. Nevertheless, real-word problems may not verify the super-additivity assumption. More recently, researchers have been interested in the set of structures maximizing the social welfare in case of non-super-additive coalition games. This problem is called optimal coalition structure generation and is known to be an NP-hard problem with exponential complexity even for suboptimal solution. Three classes are to be distinguished: dynamic programming, anytime property and heuristics. We have an interest in the first two classes. Dynamic programming has been used in [START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF][START_REF] Rahwan | An improved dynamic programming algorithm for coalition structure generation[END_REF]. The worst case complexity is O(3 n ). On the opposite, any-time algorithms can be stopped at any-time to provide a sub-optimal result. The coalition structure graph representation 2 is used in [START_REF] Sandholm | Coalition structure generation with worst case guarantees[END_REF] for coalition formation. The results are guaranteed to be within a bound from the optimum. Despite of improvements (see [START_REF] Keinanen | Algorithms for coalitional games[END_REF] and references therein), the complexity remains O(n n ). Our compatibility graph is an alternative graph representation with coalitions as vertices and structures as maximal cliques. In [START_REF] Gale | College Admissions and the Stability of Marriage[END_REF], Gale and Shapley show the non-emptiness of the core of the stable marriage and the college admission problems with preferences over individuals. The Deferred Acceptance Algorithm (DAA) is introduced. In [3], Roth et a.l. survey the existing results related to matching games and develop the theoretical results to provide insights in the understanding of the matching markets. The core stable structures (no subset of players have an incentive to deviate and form a coalition with each others) is shown to be non-empty under some simplifying assumptions (e.g. responsive preferences). In [START_REF] Cechlarova | Stability in coalition formation games[END_REF], Cechlarova et a.l. propose two extensions of the preferences over individuals to sets and propose an algorithm close to Gale's top-trading cycles to find a strict core partition. In [START_REF] Echenique | A solution to matching with preferences over colleagues[END_REF], Echenique et a.l. show a fixed-point-based algorithm to compute the set of core stable (if non-empty) many-to-one matchings in the case of preferences over colleagues. In [START_REF] Pycia | Stability and Preference Alignment in Matching and Coalition Formation[END_REF], Pycia analytically tackles the problem of coalition formation and matchings with complementarities and peer effects. Among many other results, he shows that the pairwise aligned preferences and the Nash bargaining based allocation rules guarantee non-emptiness of the set of core stable structures in all states of nature.

CONTRIBUTIONS

2 The coalition structure graph is defined as the graph G = (S, E), where the set of vertices is the set of coalition structures and the set of edges is defined such that it exists an edge e = (S, S ) between vertices S and S if S can be obtained from S by merging two coalitions of S or by splitting a coalition of S into two disjoint ones. By definition, the graph is of size B(N ) (Bell number).

The first algorithm is a centralized algorithm enumerating the set of core stable structures. It performs on a graph called the compatibility graph and does not require a tiebreaking rule (indifference between payoffs). The second algorithm is a decentralized algorithm finding a many-to-one core stable matching. It is a modified DAA that uses the pairwise alignment of the preferences over groups to reduce the preferences of the proposers over individuals.

POTENTIAL COALITION GAMES AND VIDEO CACHING

Potentials coalition games

Let Γ = (N , v, {ui}i∈N } define a coalition game in characteristic form. The set N denotes the set of players of cardinality N , {ui}i∈N denotes the set of their individual utilities and v : N → R is the characteristic function of the game. We define the set of coalitions C. The potential function Φ is an ordinal coalition potential for the game Γ if for every player i ∈ N ,

ui(C) > ui(C ) iff Φ(C) > Φ(C ), for every C, C ∈ C (1)
where ui(C) is player i's utility of the payoff it receives when taking part in the coalition C. A coalition game in characteristic form with set of players N admitting an ordinal potential Φ is called an ordinal coalition potential game in characteristic form and denoted,

Γ = (N , v, {ui}i∈N , Φ) (2)

An application: the video caching

As an example consider a video caching matching market between a content creator P and a service provider S. The content creator P has a set L of L videos. The service provider S has a set R of R caching servers. The caching servers may differ in the Quality of Service (QoS) for the cached content. This differentiation is taken to be due to the hierarchical location of the servers in the caching tree. We define T the set of T QoS of the servers. The content creator's videos are stored in its own servers. They can also be duplicated in a subset of the service provider's servers. We define the set of coalitions as,

C = {{r} ∪ J, r ∈ R, J ⊆ L, |J| ≤ qr} ∪ {l ∈ L}
i.e. the set of subsets of videos and a single server. We furthermore require the quotas qr of any server r ∈ R to be valued in {2, . . . , L -1}3 . These quotas give for each server the maximum number of videos that can be cached. We assume that the service provider can compute the impact of caching over the number of views of the videos in the coalition as the following fixed point equations,

n l (C) = n l (1)γr + l ∈C∩L a ll n l (C)
where a ll is an impact factor of l over l and γr ∈ T is QoS gain obtained by caching in the server r. We define the characteristic function v : C → R of a coalition as,

v(C) = l∈C∩L n l (C)α
where α is the constant monetary income generated by a view of a video. We now assume v(C) is shared among the players in C via a Nash bargaining (null threats) with concave individual utilities u l (x l ) = x α P l for the content creator's videos and ur(xr) = x αr r for the service provider's server r.The servers' bargaining powers increase in their factor of quality. We obtain that the individual payoffs increase in χC = v(C) |C∩L|α P +αr which is called the fear-of-ruin. In this case the fear-of-ruin is the potential Φ of the matching game between P's videos and S's servers. The game Γ = (N = L ∪ R, v, {ui}, χ) is an ordinal coalition potential game.

AN ANYTIME ENUMERATIVE CLIQUES-BASED ALGORITHM

In this section we introduce an anytime cliques-based algorithm for enumerating the core stable coalition structures in the case of an ordinal coalition potential game Γ with a set of coalitions C. The algorithm has been constructed over the game-theoritic sequential description of convergence to a stable structure provided in [START_REF] Pycia | Stability and Preference Alignment in Matching and Coalition Formation[END_REF].

Define the coalitions weighted-vertices undirected graph (G, Φ) such that the graph G = (V, E) is the complement of the intersection graph of the coalitions in C. The set of vertices V is in bijection α with the set of coalitions C but for the sake of simplicity and clarity we will further identify a coalition Ci ∈ C with the vertex vi ∈ V of the graph. Let V ⊂ V be a subset of the nodes, we denote G = (V , E(V )) the subgraph induced by V . Each vertex vi ∈ V is weighted by the value Φ(Ci) and the set of edges E is defined by the adjacency matrix A = (aij) (i,j)∈C 2 such that:

aij = 1 if Ci = Cj and Ci ∩ Cj = {∅} 0 if Ci = Cj or Ci ∩ Cj = {∅} A clique σ of the graph G = (V, E) is a complete subgraph of G.
In case the clique σ may not be included in a superior sized clique σ without loosing the completeness property, σ is said to be maximal. If σ is the clique with the highest cardinality (in terms of number of vertices |σ|) the clique is maximum. For the sake of clarity and simplicity, we will further identify a clique σ with the set of its coalitions given by V(σ). Any two coalitions C1 and C2 will be called compatible if they have no common players, i.e. C1 ∩ C2 = ∅.

In other words, if the nodes v1 and v2 are adjacent. More generally, the coalitions of C ⊂ C are compatible if the set of their nodes form a clique in the graph G. Denote G k the subgraph induced by the set of nodes of k th highest weight. As an example, G1 is the subgraph induced by the nodes with maximum weights, i.e. the subgraph such that any node in G1 is a coalition giving each player its most preferred achievable share in the game.

The algorithm iteratively builds a forest (i.e. a set of disconnected trees) such that each tree is rooted by one of the maximal clique obtained at initialization and each vertex in each tree is a stable structure. A vertex that is not a leaf is a subgame stable structure (this is the anytime property of the algorithm) and a leaf is a stable structure for the game. The set of leaves is the output of the algorithm. To go into further details, the algorithm starts by defining an initial set of structures, obtained by looking for the set Σ1 of maximal cliques in the subgraph G1 (line 3). Each clique S ∈ Σ1 is the root of a tree of stable structures (line 3). Starting from S, we look in G\G1 for the set C max S of highest valued coalitions that are compatible with S (line 11). If C max S is empty, the remaining players are left unmatched. Otherwise let Σ S be the set of maximal cliques in C max S (line 14). A child of S in the structure tree is a structure S ∪ S where S ∈ Σ S (line 15). Every time a structure is visited, it is tagged by a binary variable such that it will not be visited again (line 8). Furthermore, in case this structure becomes a parent, then the algorithm gets rid of it (line 13) to only hold the children (tagged as non-visited, line 16). The algorithm goes on iterating as long as it exists non-visited structures (line 6). We have the following propositions.

Proposition 1

The algorithm converges in a finite number of iterations.

Proposition 2

The algorithm outputs stable structures.

Proposition 3 The algorithm outputs the set of stable structures.

A DECENTRALIZED ALGORITHM: BACKWARD DEFERRED ACCEPTANCE

We now show that a modified version of the Gale and Shapley's Deferred Acceptance Algorithm (DAA) in its collegeadmission form with servers' preferences over groups of videos and videos' preferences over individual servers is a core stable matching mechanism for the many-to-one matching games with complementarities, peer effects and pairwise alignment of the preferences (see Algorithm 2).

The Backward Deferred Acceptance Algorithm (BDAA) is similar to the DAA in many aspects. It involves two sets of players that have to be matched. Every player from one side has a set of unacceptable players from the other side. In our case, a server and a video are always acceptable. As in DAA, the algorithm proceeds by proposals and corresponding acceptances or rejections. The main difference resides in the notion of counter-proposals, introduced to tackle the problem of complementarities.

To go into more details: Knowing the mutual impact factors of the videos and their own QoS gains, the servers compute all the possible coalitions they can form and the corresponding payoff vectors. They can thus build their preference lists over groups (Steps 1b). Then, every server r transmits to each of its acceptable videos the maximum achievable payoff it can achieve in the coalitions it can form with r (Step 1.c). Every video l can thus build its reduced list of preferences over individual servers: l prefers ri to rj if the maximum achievable throughput with ri is strictly greater than its maximum achievable throughput with rj (Step 1.d). BDDA then proceeds by rounds during which videos make proposals, servers make counter-proposals and videos accept or reject (from Step 2.a to Step 2.h). L(r) is the list of all videos that have proposed at least once to server r. L * (r) is a dynamic list that is reinitialized to L(r) at the beginning of every new round (Step 2.b). In each round of the algorithm, every unengaged video proposes to its most preferred server for which it has not yet proposed (Step 2.a). Every server receiving proposals adds the proposing players to its cumulated list of proposers and reinitializes its dynamic list (Step 2.b). Using P # (r) it then searches for its most preferred coalition involving only videos from the dynamic list and emits a counter-proposal to these videos. This counter-proposal contains the payoff the videos can achieve in this coalition (Step 2.c). Each video compares the counter-proposals it just received with the best achievable payoffs obtained with the servers it has not proposed to yet (Step 2.d). If one of these best achievable payoffs is strictly greater than the best counter-proposal, the video rejects the counter-proposals and continues proposing (Step 2.d, Step 2.h). Otherwise, the video accepts its most preferred counter-proposal (Step 2.d). Given a counter-proposal, if all the videos accept it, then they are engaged to the server (Step 2.e). If at least one video does not agree, then the Algorithm 2: Backward Deferred Acceptance Data: For each server: The set of acceptable videos. For each video: The set of acceptable servers. Result: A core stable structure S 1 begin 2

Step 1: Initialization; Step 1.b: Every server r computes possible coalitions with its acceptable videos, the respective videos' payoffs and emits its preference list P # (r);

5

Step 1.c: Every server r transmits to its acceptable users the highest payoff they can achieve in coalitions involving r; 6

Step 1.d: Every video l emits its reduced list of preference P (l); Step 2 (BDAA); Step 2.a, Videos proposals: According to P (v), every unengaged video v proposes to its most preferred acceptable server for which it has not yet proposed; 9

Step 2.b, Lists update: Every server r updates its list with the set of its proposers: L(r) ←-L(r) ∪ {proposers} and L * (r) ←-L(r); 10

Step 2.c, Counter-proposals: Every server r computes the set of coalitions with users in the dynamic list L * (r) and counter-proposes to the videos of their most preferred coalition according to P # (r); Step 2.e: If all videos of the most preferred coalition accept the counter-proposal of an server r, all these videos and r are marked engaged;

13

Step 2.f: Every unengaged server r updates its dynamic list by removing videos both having rejected the counter-proposal and being engaged to another server: L * (r) ←-L * (r)\{engaged rejecters}; 14

Step 2.g: Go to Step 2.c while there are unengaged servers with L * (r) = ∅; 15

Step 2.h: Go to Step 2.a while there are unengaged videos that can propose. server is unengaged (Step 2.e), it updates its dynamic list by removing the videos both having rejected its counterproposal (Step 2.f) and being engaged with an other server. The counter-proposals continues up to the point when no unengaged server can emit any counter-proposal (Step 2.g). The current round ends and the algorithm enters a new round (Step 2.h). The algorithm stops when no more videos are rejected (Step 2.h). A stable matching is obtained.

Proposition 4 In a many-to-one matching game with complementarities, peer effects and pairwise alignment of the preferences, the Backward Deferred Acceptance Algorithm (BDAA) is a core stable matching mechanism.

Assume R servers and L videos . At each round, the number of counter-propositions by servers is at most R. From the pairwise alignment of the preferences, at each step there is at least one server whose counter-proposal has been accepted. Since the algorithm stops if no more videos are rejected or all rejected videos have already proposed to all their available servers, then in at most L 2 -2L + 1, every non-engaged mobiles have proposed to all servers. Hence the complexity of our algorithm is O(n 3 ) where n = max(R, L).

CONCLUSION

We have shown two new algorithms for finding core stable structures. The first algorithm is a centralized anytime enumerative one and the second is a decentralized deferred acceptance based one. We need to go further in the analysis of the complexity of the enumerative algorithm and search for the requirements over the coalitions compatibility graph to make it fall in classes of graphs with low complexity in the maximal cliques enumeration.

Algorithm 1 : 2 Step 1 ( 3 S 5 Step 2 (

 121352 Cliques-based algorithm for finding the set of stable structures Data: Coalitions compatibility weighted graph (G, Φ) Result: The set of stable structures S 1 begin Initialize); := Σ1 (Σ1 set of maximal cliques in G1); 4 p(S) = 0 (vector of size |S|, the structures in S have not been visited yet); Form the forest); 6 while ∃S ∈ S s.t. p(S) = 0 do 7 take S s.t. p(S) = 0; 8 p(S) = 1; 9 if W ⊂ S or F ⊂ S (if the structure includes one or both of the set of players, no coalition can be added) then 10 break; 11 if C max S = ∅ (C max S set of maximum valued coalitions compatible with S) then 12 break; 13 S := S\S; 14 for S ∈ Σ S (Σ S set of maximal cliques in C max S ) do 15 S := S ∪ {S ∪ S} (complete the structures by the child S ∪ S); 16 p(S ∪ S) = 0;

3

  Step 1.a: All servers and videos are marked unengaged. L(f ) = L * (f ) = ∅, ∀f ; 4

7

 7

8

 8

11

  Step 2.d, Acceptance/Rejections: Based on these counter-proposals and the best achievable payoffs offered by the servers in Step 1.c to which they have not yet proposed, videoss accept or reject the counter-proposals; 12

See the regularity conditions over the set of coalitions for the non-emptiness of the set of core stable structures in all states of nature in[START_REF] Pycia | Stability and Preference Alignment in Matching and Coalition Formation[END_REF].

 [START_REF] Gale | College Admissions and the Stability of Marriage[END_REF]J.-M. Kelif and M. Coupechoux are partly supported by the french ANR project NETLEARN ANR-13-INFR-004


Elisabetta Bevacqua
email: bevacqua@enib.fr

Céline Jost
email: jost@enib.fr

Alexis Nédélec
email: nedelec@enib.fr

Pierre De Loor
email: deloor@enib.fr

Gestural coupling between humans and virtual characters in an artistic context of imitation

Keywords:

We present a human-agent interaction based on a theatrical mirroring game. The user and the agent imitate each other's body movements and introduce, from time to time, changes by proposing a new movement. The agent responses are linked to the game scenario but also to the user's behavior, which makes each game session unique.

Context

This demonstration has been realized within the collaborative French project called Ingredible. The fundamental goal of this project is to reproduce the mutual influence that is intrinsic to human-human interaction for a human-virtual agent interaction. The Ingredible project focuses, especially, on the gestural behavior and gestural expressive quality shown by both the virtual agent and the user while interacting. This type of interactions contains some spontaneous and emergent behaviors which are hard to tackle for virtual characters because the evolution of the interaction is shared between the protagonists. A first attempt was proposed by [START_REF] Pugliese | A Framework for Motion Based Bodily Enaction with Virtual Characters[END_REF] but this work does not show the evolution of the decision relative to the quality of the interaction. Previous works on human-human interaction have studied the dynamical evolution of communication. In "Alive Communication" [START_REF] Fogel | Alive communication[END_REF], Fogel and Garvey showed that, while interacting, people coordinate their behaviors and mutually influence their actions and intentions. Ordinary variability, that is slight modifications in the behavior due, for example, to personal style, emerges naturally without braking the bounds of the interaction. From time to time, extraordinary variability (called innovation) can appear, obliging interactants to make an effort to integrate the novelty in order to keep the communication going. This theory highlights the dynamical evolution of human-human interactions, the mutual influence and the capability to resist and to adapt to changes. Regular and unexpected behaviors appear naturally and previous works showed that reproducing the equilibrium between them in human-agent interactions is fundamental to improve agent believability and user's engagement [START_REF] Bevacqua | Effects of Coupling in Human-Virtual Agent Body Interaction[END_REF]. Within the Ingredible project we aim to reproduce this evolving equilibrium between regularity and surprise, that we call coupling [START_REF] De Loor | Utilisation de la notion de couplage pour la modélisation d'agents virtuels interactifs socialement présents[END_REF]. This demonstration shows our last progress in this direction.

The Ingredible project framework

To reach our goal we propose a framework composed of five modules: the Capture module retrieves data from tracking devices and generates a unified 15joints skeleton. Skeletons are sent to the Analysis module which tries to recognize the current gesture and its expressivity. The Decision module determines the agent's response depending on the user's behavior and the interaction scenario. The Synthesis module computes the final skeleton animation that is displayed by the Rendering module, implemented in Unity3D. The Ingredible project is still an ongoing project, and this demonstration focuses mainly on the Analysis and Decision modules. The Analysis module collects, in a continuous flow, data from devices enabling skeletal tracking of a single person. The recognition process is based on skeleton analysis and motion features computation. Skeleton joints are used to compute features which are stored in a reference database. A Principal Component Analysis (PCA) is computed to select the most important features, useful in discriminating gestures. During real-time recognition, using distance measures, real-time selected features are compared to the reference database to find the most similar gesture. More details can be found in [START_REF] Jost | Real-time gesture recognition based on motion quality analysis[END_REF]. The objective of the Decision module, shown in Fig. 1(a), is to generate an appropriate action of the virtual agent according to the user's non verbal behavior. An action can be an animation to play, a joint to move, or an expressivity to change (for example, moving faster). The decision is based on the level of coupling between the human and the virtual agent, which shows mutual influence, engagement, and willing to keep on interacting together. A high level of coupling indicates that, both human and virtual agent, are engaged in the interaction, while a low level of coupling results in a bad feeling about the interaction. Analyzing this coupling, the main objective is to maintain the interaction. According to Fogel [START_REF] Fogel | Alive communication[END_REF], three strategies are possible: (i) to maintain the current coupling level (co-regulation) if everything is going well, (ii) to induce a small variation of coupling level (ordinary variability) for example to avoid human's boredom, or (iii) to change dramatically the coupling level (innovation) for example to reengage the human. To take such a decision, the Decision module refers to a scenario which describes its expectations (what human is supposed to do), and its goals (what virtual agent is supposed to do). The satisfaction of expectations implies that the level of coupling increases, otherwise it decreases. The first implementation of this module is scenario-dependent and rule-based. A scenario is written in XML and describes actions which can be done by the virtual agent, a sequence of possible events and associated expectations. Rules, also written in XML, describe relations between the level of coupling and the goal to reach. This is only a first attempt to reproduce the mutual influence of human-human interaction. Our next objective is to make the decision module more generic to decrease the importance of a predefined scripted scenario. Moreover, a learning process will be added to automatically define the rules which conducted to the best experience between the human and the virtual agent.

Theatrical mirroring game scenario

As explained in section 1, the Ingredible project focuses on gestural behavior, particularly in the artistic domain. For such a reason, we collaborate with a theater company to define scenarios in which the whole interaction is based solely on body movements (neither speech nor facial expressions). The mirroring game is a good example of the researched interactions: two players imitate each other's movements and introduce, from time to time, changes by proposing a new movement or by modifying the expressivity, that is the manner in which the movement is performed. A very interesting characteristic of this game is that at any moment both players can be the leader and the follower, for example a person can control the movement of left hand while the other is leading that of the right hand. If the game is correctly realized, it is impossible for an external observer to guess who is in control of which part of the body and just the players can feel it. They are strongly aware of how their behavior is both influenced and influential. To play successfully this type of game, coupling between the players is fundamental; for such a reason, the mirroring game is the scenario we chose in this demonstration. It evolves as follows: the virtual agent performs idle movements in its virtual environment, patiently waiting for a user who would like to play with it. When the user appears in front of the agent and the Kinect tracks him, to establish the interaction, the agent and the user must communicate. Since neither verbal behavior nor facial expressions are allowed, both interactants have nothing but gestures to express themselves. So the agent greets the user waving its hand (or greets back if the user waves his hand first). From this moment, to start the game, both virtual and human players can express their intention to play by performing a bow. It does not matter who bows first, what is important is that, by bowing, both show that they agree to play the game together. Fig. 1(b) shows the demo set-up. During the game the agent expects that the user imitates its gestures and their expressivity and that from time to time the user proposes something new. So, when the Analysis module informs the Decision module about the user's behavior, this module compares the input data with the agent expectations and updates the level of coupling. In this scenario, there is just one expectation: "the human and the virtual agent are doing the same thing". To measure this coupling, human position and features are compared to virtual agent position and features. The coupling is inversely proportional to the resulting distance. For example, if the human and the virtual agent are doing the same thing, distance is minimum, therefore the coupling is maximum. In this context, the virtual agent has two possible goals: to imitate human (goal 1) or to introduce new movement (goal 2). In relation to "Alive Communication" theory, we consider that co-regulation is goal 1, that ordinary variability is goal 2, and that innovation is stopping the game. During the game, virtual agent alternates these goals according to rules until the end of the game. In this first implementation, rules are minimalist and describe the relation between coupling and goals: At any moment, both the agent and the user can stop the game showing a specific gesture. The agent could stop the game for several reasons, for example if the game has lasted long enough or if the user is not a "good" player and the coupling level remains low (the user rarely follows new movement propositions, that is he rarely adapts his behavior to that shown by the agent). When the interaction is over, the virtual character greets the human player and goes back to its idle motion waiting again for a new player.

Fig. 1 .

 1 Fig. 1. (a) Decision module architecture. (b) Theatrical mirroring game.

  if state == goal1 then if coupling == too low then stop the game else if coupling == high then state ← goal2 else coregulation end if else if state == goal2 then if coupling == too low then state ← goal1 else coregulation end if end if

Acknowledgments. This work was funded by the ANR INGREDIBLE project: ANR-12-CORD-001 (http://www.ingredible.fr).


Anke Brock
email: anke.brock@irit.fr

Samuel Lebaz
email: samuel.lebaz@unimes.fr

Bernard Oriola
email: bernard.oriola@irit.fr

Delphine Picard
email: delphine.picard@univ-tlse2.fr

Christophe Jouffrais
email: christophe.jouffrais@irit.fr

Philippe Truillet
email: philippe.truillet@irit.fr

Kin'touch: understanding how visually impaired people explore tactile maps

Keywords: visual impairment, depth cameras, kinect, multi-touch, fusion, finger tracking, haptic exploration, tactile maps ACM Classification K.4.2. [Computers and Society]: Social Issues -Assistive Technologies for Persons with Disabilities, H.5.2. [Information Interfaces and Presentation]: User Interfaces, I.4.9. [Image Processing and Computer Vision]: Applications, J.4 [Social and Behavioral Sciences]: Psychology

information in an accessible format. They are, for example, used to present maps in geography (figure 1) or geometric figures in mathematics. Interactive maps are produced by placing a raised-line map on top of a touch-screen which facilitates the communication of additional audio information (e.g. street names) [START_REF] Brock | Usage of multimodal maps for blind people: why and how[END_REF].

A precise description of strategies used by visually impaired subjects while exploring maps would enable progress in three important areas: [START_REF] Brock | Usage of multimodal maps for blind people: why and how[END_REF] the design of the map -the exploration description may help to identify and solve specific problems with the map itself (e.g., ambiguous lines or symbols); (2) the design of the interaction techniques -exploration strategies may highlight preferences for interacting with the map (e.g., role of the different digits); (3) the inference of guidelines on how to teach map exploration.

Several studies in experimental psychology have investigated haptic exploration strategies of tactile pictures in visually impaired and sighted subjects [START_REF] Heller | Picture and pattern perception in the sighted and blind: The advantage of the late blind[END_REF][START_REF] Wijntjes | The influence of picture size on recognition and exploratory behaviour in raised line drawing perception[END_REF]. The observed exploration strategies included the use of only one finger (index), or that of multiple fingers. When exploration is bimanual, subjects may use one hand as a stationery reference point or move both hands simultaneously. The precise nature of these exploratory modes and their relations to performance level remain obscure [START_REF] Thinus-Blanc | Representation of space in blind persons: Vision as a spatial sense?[END_REF] and need further investigation. Furthermore, the study of exploration strategies in psychology usually relies on video observation, which is time-consuming.

Our project was to design a system to better capture the users' hand motions on a tactile map. This system was designed to speed up the analysis of exploration strategies by automatically tracking and identifying the fingers used to explore the surface. To date, many projects have focused on finger tracking. The majority were based on automatic recognition in video, tracking either bare hands [START_REF] Do-Lenh | Multi-finger interactions with papers on augmented tabletops[END_REF] or markers [START_REF] Marquardt | What Caused that Touch? Expressive Interaction with a Surface through Fiduciary-Tagged Gloves[END_REF]. More recently depth sensors have been used [START_REF] Harrison | OmniTouch: Wearable Multitouch Interaction Everywhere[END_REF][START_REF] Wilson | Using a Depth Camera as a Touch Sensor[END_REF]. Other projects used optical multi-touch surfaces for finger tracking and identification [START_REF] Dang | Hand distinction for multi-touch tabletop interaction[END_REF]. To our knowledge no prior project investigated the automatic analysis of exploration strategies of tactile images by visually impaired people.

Concept

Our interactive map prototype [START_REF] Brock | Usage of multimodal maps for blind people: why and how[END_REF] uses a 3M projected capacitive multi-touch screen M2256PW. This device was selected as its technology is compatible with placing a map on its surface (unlike an optical table). It is possible to obtain coordinates of ten or more simultaneous finger positions on the screen with a precision of 0.28 mm. However it has two important limitations. Firstly, it can only track the position of fingers that actually touch the surface. The goal is to also track fingers above the surface so that all finger movements are monitored. Secondly, the multi-touch table cannot identify which hand (left or right) and which finger (i.e. the thumb, index, etc.) caused the touch. A new identifier is created for each touch event, even if the same finger made two successive touches. Furthermore, it is not possible to determine whether the touch event is provoked by a finger or another body part, such as the palm of the hand. These unexpected touch events are considered as false positives.

To overcome these limitations, we relied on the rationale proposed by Wilson [START_REF] Wilson | Using a Depth Camera as a Touch Sensor[END_REF]: First of all, it is possible to use the Kinect [START_REF]Kinect for windows[END_REF] to detect finger positions; secondly, fingers are detected even if the surface is not flat (i.e. the relief of the tactile map does not disrupt ; and finally, it is possible to get information about body parts above the surface. However the precision of the Kinect as a depth sensor is inferior to the precision of a touch surface [START_REF] Wilson | Using a Depth Camera as a Touch Sensor[END_REF]. Therefore we decided to merge finger detections from the Kinect with touch events from the multi-touch screen. The aim was to get precise information regarding hands and fingers involved during a complex exploration of a tactile map.

Prototype

Hardware and software architecture Our prototype (figure 2) consisted of a multi-touch screen in horizontal position, a tactile map, a Kinect camera fixed above the touchscreen at 70 cm height and turned in the direction of the touch screen, and a computer connected to touch screen and Kinect.

The software consisted of two applications: one for detecting finger positions on the touch screen and a second for finger tracking in the Kinect image. The data was sent via the ivy middleware [START_REF] Buisson | Ivy : un bus logiciel au service du développement de prototypes de systèmes interactifs[END_REF] to a log file. Each touch event contained a timestamp and x and y coordinates. The Kinect output contained the name of the finger (thumb, etc.) and corresponding hand (right or left), x and y coordinates of the finger and a timestamp. A third application called "fusion" (used for offline processing) read this data and created another output file that contained the name of the fingers and corresponding hand, x and y coordinates of the fingers, whether the fingers were in touch, and a timestamp.

Finger tracking algorithms

As the Kinect possesses two cameras (depth and RGB), it was easy to implement and compare two different algorithms within the same setup. Both algorithms use OpenCV functions [9] and OpenNI middleware [10].

VARIANT 1: USING DEPTH CAMERA This algorithm uses the depth image (figure 3). The calibration phase consisted of two steps. First, a depth mask was created to segregate objects (i.e. hands and digits) from the background (i.e. the tactile map). Second, the user held their hand horizontally with the fingers spread. Angles between fingers were automatically measured. They were then used as additional constraints on finger identification. After calibration the noise was reduced and the image was converted into a binary image. Contours were detected as lists of points. Each contour was reduced to the minimum number of points needed to form the outline of the hand. Vertexes of the contour represented fingertips. Fingers were identified using previous finger positions and angles between fingers.

VARIANT 2: USING RGB CAMERA The second algorithm identified fingers in the RGB image by using color markers (figure 4); two colors applied to alternating fingers were sufficient. The image was then transformed into HSV colors to eliminate any problems caused by lighting. During calibration the experimenter would click on the two colors in the image which enabled the algorithm to identify fingers by color tracking as well as angles and last finger positions. Although it required additional preparation before the experiment (adjusting color markers took 5 minutes), this algorithm was more stable for finger detection.

Fusion

The aim of the fusion was to combine and correlate touch data obtained from the multi-touch surface (touch events) with the data from the tracking algorithm (finger detections). For each touch event, the algorithm searched for the closest finger detection.

Multi-touch table and tactile map

Finger detections that had not been matched to touch events were considered as fingers above the surface. Touch events that did not correspond to finger detections were considered as false positives.

Temporal accuracy is important for fusion. Touch events were produced at 100 Hz; finger detections and fusion output at 10 Hz. As for spatial accuracy, the precision of finger detections was about 1.4 mm/pixel. This was precise enough to determine the average positions of the fingertips. The precision of touch events was 0.28 mm. Coordinates were transformed from the Kinect frame (640 x 480 pixels) to the multitouch frame (1680 x 1050 pixels) for the fusion. The average position error after conversion was about 5.6 mm or 20 pixels. Although this accuracy seemed quite low, we validated during the preliminary tests that it was sufficient to match positions of the same finger from the multi-touch screen and the Kinect.

In brief, the fusion assigned the name of the finger to touch events, added position information about fingers not in touch with the surface, and eliminated false positive touch events. We implemented an offline fusion process as there was no need to analyze exploration strategies at runtime. The application read log files, executed the fusion process, and produced an output file with the results. As the output file format was the same for both variants of the finger tracking algorithm, the fusion process worked with either one.

Case studies

We did preliminary tests with both algorithms and offline fusion. Two aspects were important to us:

(1) Although it has been proven that cameras can be used for finger tracking in touch sensors [START_REF] Harrison | OmniTouch: Wearable Multitouch Interaction Everywhere[END_REF][START_REF] Wilson | Using a Depth Camera as a Touch Sensor[END_REF], we wanted to check that those algorithms were adapted to finger tracking during exploration of a tactile image.

(2) We wanted to get concrete fusion results (i.e. success rate of the fusion, usage of different fingers, etc.) in order to decide if this approach could be used for analyzing haptic exploration strategies.

The test subject group consisted of three blindfolded (2 female, 1 male) and three legally blind (1 female, 2 male) participants. Participants possessed different levels of expertise in tactile map exploration based on the assumption that this factor impacts on exploration strategies. Two of the blind participants had significant expertise in map reading, whereas the third blind and the blindfolded participants had little expertise. We prepared a simple tactile map that contained six streets, six buildings, six points of interests and a river. For each test, participants were asked to explore the map in the way they normally do, or in the way that feels natural.

Using depth camera

The depth camera based algorithm proved efficient with most of the subjects: fingers were successfully detected and identified. Obviously, occluded fingers were not detected. Yet, the occlusion of some fingers did not hinder the correct identification of the remaining fingers (figure 5). Reappearing fingers were identified within one video frame. However the algorithm failed with one blind subject with good expertise in map reading. As a part of his exploration strategy, he frequently closed his fingers so they were no longer sufficiently separated (figure 6). Hence, the algorithm is globally working, but does not support every user's exploration strategies.

Using RGB camera

Color markers were placed on the fingers before map exploration. We observed that detection was stable for all users and that their choice of exploration strategy did not interfere with the algorithm. It proved efficient when the fingers were spread out as well as when they were closed. It did not depend on the number of fingers involved. Occlusion of certain fingers did not hinder the correct identification of remaining fingers. Reappearing fingers were identified within one video frame. The only negative was that wearing a watch led to reflections that were sometimes detected as color markers.

Fusion

Based on these preliminary results, we selected the RGB-image based algorithm for continued evaluation of the complete fusion process. One example of case study is the map exploration by a blindfolded user with little experience: after fusion, 98% of the detected fingers were identified (name of finger and hand). For each finger it was possible to determine whether it touched the surface or not. 95% of the detections were identified as touches which means that most of the time the subject was using all of his fingers. Both hands were used almost equally. His left ring finger was the finger having the most contact with the map (19%), whereas it is not typically used for map exploration by an experienced visually impaired subject. The thumbs were least used with only 3.4% of touches. The fusion successfully removed false positives (mainly contacts of the palm in the lower part of the map). These results suggest that it is possible to analyze the output data after fusion to decipher users' exploration strategies.

Discussion + future work

We presented a novel approach for finger tracking during exploration of a tactile drawing. The prototype included a raised-line map on top of a multi-touch table and a Kinect camera observing hands and fingers. We implemented and compared two algorithms for finger tracking, one using a RGB image and one using a depth image. The depth image algorithm presented errors when fingers were closed. On the contrary, no specific preparation was necessary. The RGB image algorithm was very stable and compatible with different users' exploration strategies. It would be portable for cameras with higher resolution and thus higher coordinate precision. However, users needed to wear color markers which demanded additional preparation time (less than 5 min). Also, the markers on the fingers might hinder natural exploration movements. Hence, we recommend using very little markers (e.g. nail polish). Preliminary tests showed that it was possible to merge video and touch inputs. The fusion identified hand and finger positions for 98% of all detections with accuracy of 5.6 mm (0.28 mm for touch events) and a 10 Hz frequency. It also determined whether fingers were touching the surface or not. Adventitious touches from other body parts were removed quickly and easily.

We are currently working on an advanced prototype. Among other things, we want to investigate the combined usage of both cameras in order to improve the finger detection algorithm. We are also working on visualizing the fusion results. We suggest that drawing finger traces and matching them to the map content can be helpful for analyzing exploration strategies from both a spatial and temporal perspective. Figure 7 shows which map regions are explored the most often by the right index finger of a visually impaired user. In addition to this spatial analysis of the exploration, we also visualized finger traces over different periods of Thanks to this prototype, we will be able to decipher haptic behavior that lead to successful exploration of a tactile map. The first step will be the automatic classification of output data according to different haptic exploration strategies [see 12]. The next step will be a series of experiments with visually impaired users. We hypothesize that both the type of strategy and the interaction method used for map exploration have an effect on cognitive mapping.

To conclude, we have shown that it was possible to combine multi-touch and Kinect sensing to better capture the users' hand motions on a surface. We applied this system to a map exploration program for visually impaired users. Beyond the exploration of tactile maps, our combined system offers an interesting and novel apparatus for learning about how visually impaired users read a variety of pictures with their sense of touch. In addition to providing future guidelines for teaching efficient picture reading to visually impaired people and for designing interaction techniques, our system might also be used as a training device itself. It might assist visually impaired people in learning how to scan pictures successfully through providing online corrective feedback during the manual exploration (e.g., an auditory feedback could help users to modulate their finger movements to optimal trajectories, velocity and pressure parameters).

Figure 1 :

 1 Figure 1: Exploring a tactile map

Figure 2 :

 2 Figure 2: Prototype for Kinect and multi-touch fusion

Figure 4 :

 4 Figure 4: using RGB camera

Figure 3 :

 3 Figure 3: using depth camera

Figure 5 :

 5 Figure 5: detection is working even when some fingers are occluded

Figure 6 :

 6 Figure 6: when fingers are closed separation of fingers in the depth image is not possible

Figure 7 :

 7 Figure 7: spatial and temporal visualization of movements made by the right index (see colored traces) during map exploration matched to the map content. Colors indicated the successive production of movements (1 red, 2 green, and 3 blue).

Acknowledgements

We thank Céline Ménard for her strong involvement in this project, as well as the users who participated in the preliminary tests.


Anke Brock

Philippe Truillet

Bernard Oriola

Christophe Jouffrais

Usage of Multimodal Maps for Blind People: Why and How

Keywords: ACM Classification: H.5.2 User Interfaces; H5.m. Information interfaces and presentation (e.g., HCI): Miscellaneous Multitouch, multimodal, haptics, map, blind, visual impairment, accessibility

Multimodal interactive maps are a solution for providing the blind with access to geographic information. Current projects use a tactile map set down on a monotouch display with additional sound output. In our current project we investigated the usage of multitouch displays for this purpose. In this paper, we outline our requirements concerning the appropriate multitouch tactile device and we present a first prototype. We conclude with future working propositions.

INTRODUCTION

Navigating in a familiar environment is not always obvious for a blind person. In an unknown environment, it becomes especially complicated. Therefore this issue presents a social challenge as well as an important research area. The major problem is a lack of information concerning the environment which leads to deficits in orientation and mobility. These problems often mean that the visually impaired travel less, which influences their personal and professional life and can lead to exclusion from society. Many websites offer the possibility of calculating an itinerary for free. Often, this information is presented in the form of a visual map and a corresponding roadmap. The roadmap is accessible using a screen reader (technical aid for the blind for accessing the screen content), but sequential access to information in the roadmap is limited to the important steps of an itinerary and does not help to understand the environment, which is necessary to enable a flexible and autonomous navigation (e.g. a change of itinerary in case of roadwork). Visual maps are very useful for spatial knowledge but are inaccessible. Although human tactile capacities differ from visual capacities (e.g. tactile spatial discrimination is less precise, tactile information is mainly perceived serially and not in parallel, etc.), tactile maps are used to represent geographic information for the blind. As stated by Jacobson [START_REF] Jacobson | Navigating maps with little or no sight: An audio-tactile approach[END_REF] these maps have numerous limitations, for example they are static. A solution to improve accessibility to spatial knowledge might be offered by multimodal interactive maps, by using a tactile map that is placed on a touch device. The device reacts to touch events and associates a sound output to the elements on the map targeted by the user, indicating for instance a street name. Projects like ABAplans [1] or MVI [START_REF] Campin | SVG Maps for People with Visual Impairment[END_REF] use monotouch displays. However monotouch displays present important limitations concerning usage of interaction technologies and presentation of information. For example, information can only be obtained by simple touch events and not gestural interaction. Gestural interaction on multitouch displays would enable new possibilities, for example indicating the distance between two points on the map, zooming, etc. For this reason our project investigates the usage of multitouch displays for multimodal interactive maps.

MULTITOUCH DISPLAYS

We have identified the following requirements:  Technology: it is crucial that the touch screen is usable with a tactile map placed on its surface.  Accuracy: it must be possible to identify the exact position of a finger. As presented by Power [START_REF] Power | On the Accuracy of Tactile Displays[END_REF], inaccuracy of finger position can lead to errors in the sound output of interactive maps. Accuracy is thus an important aspect.  Number of inputs: Most blind seem to explore tactile maps with both hands and all 10 fingers. Tactile device should therefore provide real multitouch characteristics and if possible react to 10 inputs in parallel.  Size: As explained by Tatham [START_REF] Tatham | The design of tactile maps: theoretical and practical considerations[END_REF] tactile maps should not exceed a certain size (two handspans, 450 mm). Thus it is not necessary to use a large scale touch table. On the other hand it is difficult to present tactile maps in a very small size. Therefore we propose that touch displays should at least have A4 format. Evaluations of different maps with our user group show that they prefer maps in format A3.  Orientation: usually, maps are presented in horizontal orientation. Thus a device should provide the possibility to be posed in this way.  Programmable interface: the device should provide access to touch events and/or gestural events.

The function of a multitouch device for a multimodal interactive map for the blind is not graphical rendering but responding to touch events. Therefore there is no requirement concerning the visual quality of the display.

In order to find an adapted technology we have made several tests with touch interfaces relying on different technologies.

Resistive displays react to touch events even if the contact is established using other objects (for example a pen) or through a paper. However, most resistive displays provide only monotouch input. Stantum [START_REF] Stantum | Unlimited Multitouch -Home[END_REF] touch display offers multitouch possibilities and has been available as a development kit, but unfortunately this device is now only sold in small sizes for mobile phones. Another technology that we have tested is the projected capacitance as in the Apple Ipad and 3M™ Multi-touch Display M2256PW. Both systems work with a tactile map placed on the surface. However the size of the Ipad is too small for our map project. Finally we tested Immersion touch table ILight that based on the technology of Diffused Illumination. This technology uses projectors and sensors placed below the surface of the display. When placing a paper on the surface, the finger position cannot be recognized and thus this technology is not fitting our project.

A first test with a tactile display using a grid of infrared light was not successful. Other technologies that might work but that we could not test yet include "frustrated total internal reflection", optical "out-of plane" (sensor above the surface) and "surface acoustic wave".

FIRST PROTOTYPE

A high-fidelity prototype has been realized using the Stantum touch screen [START_REF] Stantum | Unlimited Multitouch -Home[END_REF]. The touch device is connected to the computer via a USB port and a VGA port. The computer needs a sound card for Text-to-Speech (TTS) output. A tactile map is placed on the touch device.

The prototype is composed of four modules connected by the ivy middleware [START_REF] Buisson | Ivy : un bus logiciel au service du développement de prototypes de systèmes interactifs[END_REF]. A driver adapted to our requirements reacts to touch events on the display and sends them to another software module which has access to the map in SVG format. It receives these messages and uses the touch position in order to determine the element of the map that has been touched. It then sends a message with the element's ID on the ivy bus. A third module, MIM (Multimodal Interactive Map) receives messages of both modules. It reacts only to "touchdown" events as the sound output should only be triggered when the user explicitly presses on the map and not when he explores the map by following the embossment with his fingers ("touch move"). MIM then sends a message with the text output to the TTS module via ivy. Finally, the TTS module converts the string into a sound output. The user explores the map following the embossed streets and borders with his fingers. When he wants to get information on an element, he makes a press and hears associated information (e.g. street name, name of a park or river). The application can easily be extended to add further output elements.

RESULTS AND FUTURE WORK

Preliminary results show that the users appreciate having a multimodal interactive map and that usage is pertinent for acquiring spatial knowledge. However the current implementation is too sensitive. "Touch down" events are even triggered when the user slightly moves his fingers on the display. As most blind users put all 10 fingers on the display in parallel, too many sound outputs (one for each finger) are produced. Thus, the next step will be to implement specific interactions techniques (e.g. double click) in order to distinguish between exploration movements and touch events. Another possibility would be to react to the number of fingers on the display and to provide sound output depending on this parameter (e.g. indicate an element's name for one finger and distances for two fingers, etc.). Other problems are related to technical limitations. For instance, it would be helpful to get the touch pressure as a parameter, which is unfortunately not provided by most touch displays. The choice of touch displays is limited. It will be interesting to further examine other technologies and, specifically if they address the requirements presented in this paper. Anyway, the concept of multimodal interactive maps is promising. Due to the relatively low cost of tactile devices, it seems possible that, in near future, blind users have their own multimodal map system at home.

ACKNOWLEDGMENTS

Many thanks to Stéphane Chatty for letting us use the Stantum device during this project.