Denis Efimov

Shifang Li

Yiran Hu

Steven Muldoon

Hossein Javaherian

Vladimir O Nikiforov

Nikiforov V O Are With

Javaherian H Are

Application of Interval Observers to Estimation and Control of Air-Fuel Ratio in a Direct Injection Engine

come

I. INTRODUCTION

One of the main constraints for engine development and certification is constituted by the requirements on vehicle emission. The fuel-to-air ratio (FAR) regulation is a related engine control problems. FAR control performance can strongly impact key vehicle attributes such as emissions, fuel economy, and drivability. The FAR is regulated at stoichiometric value such that the exhaust gas can be efficiently converted by a three-way-catalyst converter. Thus in the most operating modes of the engine, the primary objective of the on-board FAR control system is to maintain the fuel injection in stoichiometric proportion to the ingested air flow. Variations in the air flow are affected by the driver, they serve as an exogenous disturbance to the FAR regulation system. In some direct injection engines, the fuel is injected via a common rail line directly into the combustion chamber of each cylinder, which leads to an increased fuel efficiency and improved emission level [START_REF] Zhao | Advanced Direct Injection Combustion Engine Technologies and Development: Gasoline and Gas Engines[END_REF].

Due to its importance, the problem of FAR regulation for spark ignition engines has attracted significant attention during the last few decades [START_REF] Cook | Control, computing and communications: Technologies for the twenty-first century model T[END_REF]. Adaptive control theory [START_REF] Ault | Adaptive air-fuel ratio control of a spark ignition engine[END_REF], [START_REF] Franceschi | An adaptive delay-compensated pid air fuel ratio controller[END_REF], [START_REF] Powell | Observer-based air fuel ratio control[END_REF], [START_REF] Turin | Model-reference adaptive a/f-ratio control in an si engine based on kalman-filtering techniques[END_REF], [START_REF] Yildiz | Adaptive air fuel ratio control for internal combustion engines[END_REF], robust and H ∞ control approaches [START_REF] Brandstetter | Robust air-fuel ratio control for combustion engines[END_REF], [START_REF] Mianzo | Transient air-fuel ratio H∞ preview control of a drive-by-wire internal combustion engine[END_REF], gain scheduling [START_REF] Di Gaeta | Model-based control of the air fuel ratio for gasoline direct injection engines via advanced cosimulation: An approach to reduce the development cycle of engine control systems[END_REF], fuzzy control systems theory [START_REF] Ghaffari | Adaptive fuzzy control for air-fuel ratio of automobile spark ignition engine[END_REF], observer based controllers [START_REF] Chang | Air-fuel ratio control in spark-ignition engines using estimation theory[END_REF], neural network techniques [START_REF] Huang | Neural sliding mode control of engine torque[END_REF], [START_REF] Zhai | Rbf based feedforward feedback control for airfuel ratio of si engines[END_REF], supervisory controls [START_REF] Efimov | Switching control of air-fuel ratio in spark ignition engines[END_REF], [START_REF] Efimov | Supervisory control of air-fuel ratio in spark ignition engines[END_REF], [START_REF] Kolyubin | Twochannel adaptive hybrid control of the air-to-fuel ratio and torque of automobile engines[END_REF], model predictive controllers [START_REF] Muske | A model-based si engine air fuel ratio controller[END_REF] and learning methods [START_REF] Rupp | Iterative tuning of internal model controllers with application to air/fuel ratio control[END_REF], [START_REF] Efimov | Iterative learning airfuel ratio control with adaptation in spark ignition engines[END_REF] are successfully tested in this particular application. However, the complexity of the problem (taking into account the variety of engines and their operating conditions) and growing demands on FAR regulation quality in the presence of a significant modeling uncertainty require new solutions. Additional important constraints for implementation are a small number of tuning parameters and clear design guidelines.

In order to deal with the FAR dynamics uncertainty/complexity, an appealing approach is to represent its model in a Linear Parameter-Varying (LPV) form:

ẋ = A(θ(t))x + B(θ(t))u, (1)
y = C(θ(t))x,
where x ∈ R n , u ∈ R m , y ∈ R p are the system state, input and output respectively, θ ∈ R q is the vector of scheduling parameters (θ : R + → Θ where Θ ⊂ R q is a given set, the instant value θ(t) can be available for measurements or not), A, B and C are matrix functions of corresponding dimensions. The main advantage is that a partial linearity of LPV models allows plenty of methods developed for linear systems to be applied [START_REF] Mohammadpour | Control of Linear Parameter Varying Systems with Applications[END_REF].

If the value of θ(t) is not measured (it means the presence of uncertainties, unknown parameters or/and disturbances), then design of a control law or an observer for (1) is complicated [START_REF] Mohammadpour | Control of Linear Parameter Varying Systems with Applications[END_REF]. Indeed, if θ(t) is available for measurements, then the following observer can be synthesized:

ẋ = A(θ(t))x + B(θ(t))u + L(θ(t))[y -C(θ(t))x],
where x ∈ R n is the estimate of x and L is the observer gain [START_REF] Mohammadpour | Control of Linear Parameter Varying Systems with Applications[END_REF]. This scheme is an extension of Luenberger approach for LPV systems, x(t) should converge to x(t) asymptotically or in a finite time. On the other hand, if θ(t) is not available for measurements, then such an observer is not realizable since the instant values of the matrix functions A, B and C are unknown. Therefore, in such a case another estimation problem can be posed: an observer has to be designed, which is robust with respect to θ(t) ∈ Θ, then x(t) may converge not to the exact value of x(t), but to some vicinity of x(t), with the size of the vicinity proportional to the size of Θ.

The interval observers provide a solution in this case. An interval observer is a dynamical system that, using inputoutput information and the bounds of the model uncertainties, evaluates the set of admissible values (interval) for the state x(t) at each instant of time. In other words, a system ż = g(z, y, u), x = h(z, y, u), x = h(z, y, u), where g, h, h are some known functions (dependent on Θ) and z ∈ R k with k ≥ n, is called an interval observer if the relations

x(t) ≤ x(t) ≤ x(t)
are satisfied for all t > 0 provided that x(0) ≤ x(0) ≤ x(0) (in this definition the relation x(t) ≤ x(t) is understood elementwise, i.e. x i (t) ≤ x i (t) for all 1 ≤ i ≤ n).

The variables x(t) and x(t) are called lower and upper bounds of x(t) respectively. The value x(t) -x(t) is the estimated interval width, which is proportional to the size of the system uncertainty, i.e. the set Θ dimensions. Such an observer may generate an estimate on the state value x(t) (the mean value of the interval x(t) = 0.5[x(t) + x(t)], for example) and also it evaluates its own error of estimation since it is guaranteed that x(t) ∈ [x(t), x(t)] for all t ≥ 0. Thus an interval observer gives more information than a conventional pointwise observer. The interval observers have been proposed recently in the seminal work [START_REF] Gouzé | Interval observers for uncertain biological systems[END_REF], next many extensions have been proposed for continuous-time systems [START_REF] Mazenc | Interval observers for linear time-invariant systems with disturbances[END_REF], [START_REF] Combastel | Stable interval observers in BBC for linear systems with time-varying input bounds[END_REF], [START_REF] Raïssi | Interval state estimation for a class of nonlinear systems[END_REF] and discrete-time systems [START_REF] Mazenc | Interval observers for discretetime systems[END_REF], [START_REF] Efimov | Interval observers for time-varying discrete-time systems[END_REF]. As we can conclude from these references, the interval observers constitute a new and actively developing area of research.

In this work the interval observer methodology is applied for estimation and control of a LPV model of a direct injection engine. The model of FAR dynamics is presented in Section 2. An interval observer is given in Section 3. In Section 4 it is explained how using interval observers it is possible to evaluate the set Θ. A control algorithm is designed based on the obtained interval observer in Section 5. The performance of the synthesized control is evaluated by simulations and implementation experiments.

II. LPV MODEL OF FAR DYNAMICS

A simplified LPV mean-valued model for FAR dynamics can be selected for a direct injection engine in the following form [START_REF] Cook | Control, computing and communications: Technologies for the twenty-first century model T[END_REF], [START_REF] Di Gaeta | Model-based control of the air fuel ratio for gasoline direct injection engines via advanced cosimulation: An approach to reduce the development cycle of engine control systems[END_REF]:

τ λ (t) λ(t) + λ(t) = λ EM (t), (2)
λ EM (t) = 1 AF stoich ṁac (t) ṁfi (t) , ṁac (t) = g(t)η(t), ṁfi (t) = N (t) 30 m f i (t),
where λ(t) is the air-to-fuel ratio estimate available for direct measurements after catalytic converter and λ EM (t) is the regulated variable, which represents the FAR in the cylinders (in this case an uncertain time-varying coefficient τ λ (t) corresponds to parameters of the exhaust manifold and lambda-sensor); ṁac (t) is the intake air flow in the cylinders, which is proportional to time-varying signals g(t) (uncertain) and η(t) (it is a function of measured variables, like the engine rotation velocity N (t), pressures and temperatures in intake and exhaust manifolds, positions of cam phasers, etc.); AF stoch = 14.681 is a known constant; ṁfi (t) is the injected fuel flow and m f i (t) is the mass of injected fuel, which is the control input in the system. In fact, there is also a delay in the measurements of λ(t), which corresponds to the air transportation in the exhaust manifold, and which has been skipped in this model since for its compensation a separately developed predictor is used (its choice is not critical and it is not presented here for brevity of presentation, the predictor is based on the model ( 2) with average values of uncertain parameters). Recall, in (2) the signals λ, m f i , N and η are measured, the parameters τ λ and g are time-varying (their nominal or mean values τ * λ , g * are also given). The variable τ λ represents the exhaust manifold and lambda-sensor dynamics uncertainty (it may also be used for the exhaust manifold delay modeling), in this case τ * λ corresponds to some identified parameter of the sensor. The variable g is introduced in order to take into account the approximation and modeling errors appeared in η(t), thus g * = 1.

It is easy to see, that for x(t) = λ(t), u(t) = m -1 f i (t) and θ(t) = [τ λ (t) g(t) N (t)] T the system (2) can be rewritten as a first order LPV model [START_REF] Zhao | Advanced Direct Injection Combustion Engine Technologies and Development: Gasoline and Gas Engines[END_REF], in this case the vector of scheduling parameters θ(t) is not available for measurements (only N (t) is measured). It is required to design m f i providing boundedness of the regulation error |λ EM (t) -1| ≤ ∆ for some ∆ > 0 and all t ≥ 0.

In addition, a database is used with all necessary measured signals for a Chevrolet Equinox with a 2.4L direct injection engine, all simulation below are performed based on this database.

III. INTERVAL OBSERVER FOR FAR VARIABLE IN CHEVROLET EQUINOX

For the interval observer design we will assume that the admissible intervals for the values of uncertain time-varying parameters τ λ and g are given:

τ λ ≤ τ λ (t) ≤ τλ , g ≤ g(t) ≤ ḡ ∀t ≥ 0, (3)
where τ λ , τλ , g and ḡ are known positive constants. Due to the system structure it is possible to design two interval estimators for the variable λ EM (t), one is dependent only on the measured output information, another is based on the input signals only (and intervals of uncertainty defined in (3)).

For the interval observer from the "output", we calculate derivative λ(t) of λ(t) using differentiator from [START_REF] Perruquetti | Finite-time observers: Application to secure communication[END_REF] or from [START_REF] Efimov | A hybrid robust non-homogeneous finitetime differentiator[END_REF]:

ż1 (t) = -α |z 1 (t) -λ(t)|sign[z 1 (t) -λ(t)] + z 2 (t), ż2 (t) = -βsign[z 1 (t) -λ(t)] -χsign[z 2 (t)] -z 2 (t), (4) λ(t) = z 2 (t),
where z 1 , z 2 ∈ R are the states of the differentiator, β > α > χ > 0 are the parameters to be tuned. Then the admissible interval [λ o EM (t), λo EM (t)] of the value λ EM (t) can be calculated as follows:

λ o EM (t) = λ(t) + π[ λ(t), τλ , τ λ ], λo EM (t) = λ(t) + π[ λ(t), τ λ , τλ ], where π(λ, a, ā) = āλ, if λ ≥ 0, aλ, if λ < 0.
For the interval observer from the "input", we calculate the interval of admissible values [ ṁac (t), mac (t)] for the variable ṁac (t):

ṁac (t) = gη(t), ṁac (t) = ḡη(t),
where we used the fact that η takes only positive values. Next, the FAR channel dynamics can be rewritten as follows:

λ EM (t) = 1 d(t) ṁfi (t) , d(t) = AF stoich ṁac (t) . (5)
Thus ( 5) is a static system with measured input ṁfi (t) and known interval bounds for the parameter d(t):

d(t) = AF stoich ṁac (t) , d(t) = AF stoich ṁac (t) .
Then the following interval estimates can be computed ( ṁfi (t) takes also only positive values):

λ EM (t) ∈ [λ EM (t), λEM (t)], (6)
λ EM (t) = max{λ o EM (t), λ i EM (t)}, λEM (t) = min{ λo EM (t), λi EM (t)}, λ i EM (t) = [d(t) ṁfi (t)] -1 , λi EM (t) = [d(t) ṁfi (t)] -1 .
Therefore, [λ o EM (t), λo EM (t)] is the interval estimate for λ EM (t) obtained from the "output", and [λ i EM (t), λi EM (t)] is the interval estimate derived from the "input". These interval estimates depend on known bounding variables for unknown time-varying parameters τ λ , g and measured signals. The precision of the obtained interval estimates is proportional to the accuracy of differentiation and the initial uncertainty imposed on the system (parameters τ λ , τλ , g and ḡ).

The results of simulation are given in Fig. 1, the timevarying parameters τ λ (t) and g(t) are modeled as stochastic signals with uniform distributions in the selected limits [τ λ , τλ ] and [g, ḡ]. As we can see from this simulation, the estimates λ EM (t), λEM (t) (the blue and magenta lines) correctly envelop λ EM (t) (the cyan line). The time axes is represented in events (in all figures in the paper).

IV. VALIDATION OF MODELS USING INTERVAL

OBSERVERS

Previously we have assumed that for all time-varying parameters an interval of admissible values is given: where 0 < τ λ ≤ τλ , 0 < g ≤ ḡ are some constants, which define the admissible deviations of the model parameter from the nominal values. The variables τ λ , g are not measured (they were introduced in order to model approximation errors or uncertain processes), and as it has been noticed, accuracy of the interval estimation is proportional to the model uncertainty, which is represented by the intervals [τ λ , τλ ] and [g, ḡ]. Therefore, a good identification of the values τ λ , τλ , g, ḡ is very important for application of interval observers. In this section we will show how the values of constants τ λ , τλ , g, ḡ can be calculated off-line using datasets of measurements (on which the model was approximated).

τ λ ∈ [τ λ , τλ ], g ∈ [g, ḡ],
The idea is to calculate the interval estimates λ(t), λ(t) of the measured variable λ(t) using the output of the interval observer (6), then we may adjust τ λ , τλ , g, ḡ such that λ(t) ∈ [λ(t), λ(t)] for all t ≥ 0 (for all recorded samples used for the model approximation and validation), which will be an explicit indication that intervals for τ λ , g have been selected properly.

Using the values of λ EM (t), λEM (t) (which are dependent on τ λ , τλ , g, ḡ) we may calculate the interval estimates for the measured output λ applying the following interval framer:

λ(t) = λEM (t) τ λ - λ(t) τλ , λ(t) = λ EM (t) τλ - λ(t) τ λ .
The values τ λ , τλ , g, ḡ can be tuned using the trial and error method. Initially, the intervals [τ λ , τλ ] and [g, ḡ] are selected big enough guaranteeing that λ(t) ∈ [λ(t), λ(t)] for the given dataset. Next, the width of intervals [τ λ , τλ ] and [g, ḡ] is iteratively decreased while the inclusion λ(t) ∈ [λ(t), λ(t)] is preserved. For example, in Fig. 2 the results obtained on the dataset for the case of 5% deviations from the nominal values are shown (τ λ = 0.95τ * λ , τλ = 1.05τ * λ , g = 0.95 and ḡ = 1.05). The time-varying parameters τ λ (t) and g(t) are modeled as stochastic signals (uniform distributions) with the values in [τ λ , τλ ] and [g, ḡ]. As we can conclude the interval estimates λ(t), λ(t) (the red lines) nicely envelop the signal λ(t) (the magenta line), the estimate λEM (t) = 0.5[ λEM (t) + λ EM (t)] is also shown (the blue line). This technique gives us an evaluation of the parameter uncertainty acceptable for the model representation.

V. FAR CONTROL By design of the control m f i it is required to ensure the relation λ EM (t) = 1 with the maximal admissible deviation from this value 25%, i.e. ∆ = 0.25.

A. Control design

As an auxiliary control strategy let us calculate the values of ṁfi (t) that ensures realization of the control goal λ EM (t) = 1. From ( 5), we derive the following constraints to guarantee:

d(t) ṁfi (t) = 1, d(t) ṁfi (t) = 1, then λ i EM (t) = λi EM (t) = 1
, and since λ i EM (t) ≤ λ EM (t) ≤ λi EM (t) for all t ≥ 0 then the control goal has to be achieved. The common control value that minimizes the error for both equations can be found by the formula (a least square solution):

ṁ0 f i (t) = d(t) + d(t) 2d(t) d(t) . (7)
The control ( 7) can be used in the "normal" situation, when λ EM (t), λEM (t) do not exceed the admissible 25% deviations from 1. If it is not the case, simple correction controls can be used:

ṁfi (t) = λ * EM /d(t), ṁfi (t) = λ * EM / d(t), (8)
where λ * EM , λ * EM ∈ [1 -∆, 1 + ∆] are design parameters. The control ṁfi (t) guarantees that λi EM (t) = λ * EM , and it can be used if λ EM (t) > 1 + ∆ in order to return the trajectory back in the desired domain. The control ṁfi (t) similarly ensures λ i EM (t) = λ * EM , it can be activated if λEM (t) < 1 -∆. Finally, combining [START_REF] Yildiz | Adaptive air fuel ratio control for internal combustion engines[END_REF] and ( 8) we obtain the feedforward control algorithm for FAR channel:

m f f f i (t) = 30 N (t)      ṁfi (t) if λEM (t) < 1 -∆, ṁfi (t) if λ EM (t) > 1 + ∆, ṁ0 f i (t) otherwise. (9)
Lemma 1. For the model (2) with the control (9), if the relations (3) are satisfied for some known positive constants τ λ , τλ , g and ḡ, then

λ EM (t) ∈ min 1 -∆ g , 1 λ * EM , g λ * EM ḡ , max 1 + ∆ g , ḡ λ * EM g , 1 λ * EM for all t ≥ 0, where ∆ g = ḡ-g g+ḡ . Proof. Note that λ EM (t, ṁfi (t)) = g(t)η(t) AF stoich 1 ṁfi (t) ,
then for the control ( 7) we obtain

λ 0 EM (t) = λ EM (t, ṁ0 f i (t)) = g(t)η(t) AF stoich 2d(t) d(t) d(t) + d(t) = 2g(t) g + ḡ ,
and, consequently,

λ 0 EM (t) ∈ [ 2g g+ḡ , 2ḡ g+ḡ ] = [1-∆ g , 1+∆ g ]. For the controls (8) we get λ * EM (t) = λ EM (t, ṁfi (t)) = g(t) λ * EM g , λ * EM (t) = λ EM (t, ṁfi (t)) = g(t) λ * EM ḡ , then λ * EM (t) ∈ [ 1 λ * EM , ḡ λ * EM g ] and λ * EM (t) ∈ [ g λ * EM ḡ , 1 λ * EM ].
Since the values of λ EM (t) with the control (9) are in the set {λ 0 EM (t), λ * EM (t), λ * EM (t)}, then the required interval estimate follows.

Corollary 1. Under the conditions of Lemma 1, if ḡ g ≤ 1+∆ 1-∆ , then there exist λ * EM ∈ [ ḡ (1+∆)g , 1 1-∆ ] and λ * EM ∈ [ 1 1+∆ , g (1-∆)ḡ ] such that λ EM (t) ∈ [1 -∆, 1 + ∆] for all t ≥ 0.
Proof. The claim follows by a direct substitution.

For feedback regulation, an estimate of the regulated variable value is needed, and for this purpose we will use

λEM (t) = 0.5[ λo EM (t) + λ o EM (t)] = λ(t) + τ * λ λ(t
m f i (t) = sat[m f f f i (t) + m f b f i (t)], (10)
where sat[•] is a saturation function, which ensures that the control lies in the admissible bounds.

B. Results of simulation

The results of simulation are shown in Fig. 3, the timevarying parameters τ λ (t) and g(t) are modeled as stochastic signals in the required limits (±5% of deviation, in this case the conditions of Lemma 1 and Corollary 1 are satisfied). In Fig. 3 the variable λ(t) (blue line) and its reference value (yellow line) are plotted. As we can conclude, the regulation error is rather small, that confirms the obtained theoretical results in Lemma 1 and Corollary 1. An example of the interval observer (6) estimates is given in Fig. 1. Thus the proposed interval observer based control demonstrated sufficient robustness and accuracy in the simulations.

C. Results of implementation

The plots of signals obtained during an US06 cycle (this test cycle includes sufficiently different driving conditions) for Chevrolet Equinox (2.4L direct injection engine) are shown in figures 4-6 (throttle position control has been generated by ECM in this case). As we can conclude from these results, in Fig. 5 the variable λ(t) lies in the limits of 25% deviation from the desired value 1 during the complete cycle, and almost everywhere the more advantageous limits in 10% of deviation are guaranteed. The estimates of the regulated variable λ EM (t) given in Fig. 6 are almost all time in the correct limits (blue line is the estimate λEM (t), red and green lines are λ EM (t) and λEM (t) respectively). Thus the developed FAR control algorithm based on interval observer has acceptable performance in the presence of diverse engine operating modes, which can be seen analyzing Fig. 4, where the engine rotation speed N (t) is presented. In addition, it is worth to stress that in the tests only feedforward control has been used, the feedback control has been switched off (i.e. k i = 0 for all i = 1, . . . , 5), the reason for that is to show advantages and workability of the interval observer based scheme.

VI. CONCLUSION

Interval observers constitute a new method for state estimation of significantly uncertain systems. These observers provide an estimate on the state and compute bounds on estimation error simultaneously, i.e. at each instant of time they evaluate the interval of admissible values of state (that is a counterpart of the Kalman filtering in deterministic setting). Width of the estimated interval is proportional to the current size of uncertainty in the system description. An important area of applications for interval observers deals with LPV systems (especially in the case with unmeasured vector of scheduling parameters). A simple LPV model of spark ignition engine is analyzed in the paper. An interval

Figure 1 .

 1 Figure1. The results of simulation of the interval observer[START_REF] Turin | Model-reference adaptive a/f-ratio control in an si engine based on kalman-filtering techniques[END_REF]

Figure 2 .

 2 Figure 2. The signals λ (magenta), λEM (blue) and λ, λ (red)

Figure 4 .

 4 Figure 4. N (t) in implementation

Figure 5 .

 5 Figure 5. AFR in implementation

Figure 6 .

 6 Figure 6. Estimates of λ EM in implementation

  ). is an estimate of the derivative of e(t) calculated by differentiator (4), the coefficients k i , i = 1, . . . , 5 and powers 0 < p 1 ≤ 1, p 2 ≤ 1, 1 ≤ p 3 have to be adjusted using the trial and error method. The terms proportional to k 1 and k 5 are responsible for proportional Figure3. AFR λ regulation in simulation regulation in local and global scale correspondingly, if p 1 < 1 and p 3 > 1 then a fixed-time rate of convergence can be guaranteed[START_REF] Polyakov | Nonlinear feedback design for fixed-time stabilization of linear control systems[END_REF] (it is better to use different powers, p 1 ≤ 1 for local regulation and p 3 ≥ 1 for global setting; in the conventional PID p 1 = p 3 = 1 then k 1 = k 5 can be selected). The coefficients k 2 and k 3 correspond to integral and derivative actions in PID, the power p 2 < 1 may ensure a finite-time rate of static error compensation. The sliding mode term proportional to k 4 serves for cancellation of matched uncertainties.The final expression of the control is:

	1.15
	1.1
	1.05
	1
	0.95
	0.9
	0.85
	0.8	0	1	2	3	4	5	6	7	8	9	10
												x 10 4
												Let us stress that the estimates λ i EM (t), λi EM (t), which are
												dependent on the control signals, were used for calculation
												of m f i . Then the following nonlinear PID, based on the estimates λo EM (t), λ o EM (t), can be used for the feedback: m f b f i (t) = k 1 e(t) p1 + k 2 e(s) p2 ds + k 3 ê(t) ˆt 0 +k 4 sign[e(t)] + k 5 e(t) p3 ,
												where e(t)

p = |e(t)| p sign[e(t)], e(t) = 1 -λEM (t) is the regulation error, ê(t)

ACKNOWLEDGMENTS

The financial support for this research project was provided by General Motors Company and is gratefully acknowledged by the lead author and Prof. Nikiforov of University ITMO, Russia.

Federation (Grant 074-U01) and the Ministry of Education and Science of Russian Federation (Project 14.Z50.31.0031).


Tommaso Caselli Trentorise

Carlo Strapparava

Laure Vieu
email: vieu@irit.fr

Guido Vetere
email: gvetere@it.ibm.com

Aligning an Italian WordNet with a Lexicographic Dictionary: Coping with limited data

This work describes the evaluations of two approaches, Lexical Matching and Sense Similarity, for word sense alignment between MultiWordNet and a lexicographic dictionary, Senso Comune De Mauro, when having few sense descriptions (MultiWordNet) and no structure over senses (Senso Comune De Mauro). The results obtained from the merging of the two approaches are satisfying, with F1 values of 0.47 for verbs and 0.64 for nouns. Lexical Match P R F1 Acc. Verb SYN -no threshold 0.41 0.29 0.34 0.864 Verb SYN -≥ 0.1 0.42 0.26 0.32 0.874 Verb SYN -≥ 0.2 0.54 0.11 0.18 0.901 Verb SYN -max score 0.59 0.19 0.29 0.

Introduction

This work is situated in the field of word sense alignment, a research area which has seen an increasing interest in recent years and which is a key requirement for achieving semantic interoperability between different lexical-semantic resources [START_REF] Matuschek | [END_REF]. Our goal is to automatically import high-quality glosses in Italian in MultiWordNet [START_REF] Pianta | MultiWordNet: developing an aligned multilingual database[END_REF] (MWN) by aligning its synsets to the entries of a lexicographic dictionary, namely the Senso Comune De Mauro (SCDM), thus providing Italian with a more complete and robust version of MWN. For SCDM, the linking of the entries with MWN plays a double role. On the one hand, it will introduce lexical-semantic relations, thus facilitating its use for NLP tasks in Italian, and, on the other hand, it will make SCDM a structurally and semantically interoperable resource for Italian, to which other lexical-semantic resources (both in Italian, such as PAROLE-SIMPLE-CLIPS [START_REF] Ruimy | A computational semantic lexicon of italian: SIMPLE[END_REF], and in English, such as VerbNet (Kipper [START_REF] Schuler | Verbnet: a broadcoverage, comprehensive verb lexicon[END_REF], among others), sense annotated corpora (e.g. the MultiSemCor corpus [START_REF] Bentivogli | Exploiting parallel texts in the creation of multilingual semantically annotated resources: the MultiSemCor Corpus[END_REF]), and Web-based encyclopedia (e.g. Wikipedia) can be connected.

At this stage of development we focused on the alignment of verbs and nouns. The remaining of this paper is organized as follows. Section 2 will state the task and describe the characteristics of the two lexica. In Section 3 some related works and the perculiarities of our work are discussed. The approaches we have adopted are described in Section 4. The evaluation is carried out in Section 5, including an error analysis. Finally, in Section 6 conclusions and future works are reported.

Problem Description and Resources

Following [START_REF] Matuschek | [END_REF], word sense alignment (WSA) can be formally defined as a list of pairs of senses from two lexical-semantic resources. A pair of aligned senses denotes the same meaning.

For instance, taken the two senses of the word "day" "amount of hours of work done in one day and "the recurring hours established by contract or usage for work" (taken from translated SCDM and MWN, respectively), they must be aligned as they are clearly equivalent.

MultiWordNet

MWN is a computational multilingual lexicon perfectly aligned to Princeton WN 1.6. As in WN, concepts are organized in synonym sets (synsets) which are hierarchically connected by means of hypernym relations (is a). Additional semantic relations such as meronymy, troponymy, nearest synonym and others are encoded as well. The Italian section of MWN is composed of 38,653 synsets, with 4,985 synsets for verbs and 28,517 synsets for nouns. Each synset is accompanied by a gloss describing its meaning and, when present, one or more examples of use. Only 3,177 glosses (8,21%) are in Italian and, in particular, 402 for verbs and 2,481 for nouns.

Senso Comune De Mauro

The SCDM lexicon is part of a larger research initiative, Senso Comune1 [START_REF] Oltramari | Senso Comune: A collaborative knowledge resource for italian[END_REF]).

Senso Comune aims at building an open knowledge base for the Italian language, designed as a crowd-sourced initiative that stands on the solid ground of an ontological formalization and wellestablished lexical resources. The lexicon entries have been obtained from the De Mauro GRADIT dictionary and consists in the 2,071 most frequent Italian words, for a total of 11,939 fundamental senses. As for verbs we have 3,827 senses, corresponding to 643 lemmas, with an average polysemy of 5.9 senses per lemma. As for nouns we have 4,586 senses, corresponding to 1,111 lemmas with an average polysemy of 4.12 senses per lemma. In SCDM, word senses are encoded following lexicographic principles and are associated with lexicographic examples of usage.

Senso Comune comprises three modules: i.) a top level module for basic ontological concepts; ii.) a lexical module for linguistic and lexicographic structures; and iii.) a frame module for modeling the predicative structure of verbs and nouns. The top level ontology is inspired by DOLCE (Descriptive Ontology for Linguistic and Cognitive Engineering) [START_REF] Masolo | Wonderweb deliverable D17: the wonderweb library of foundational ontologies[END_REF]. All nominal entries have been manually classified according to the ontological concepts and an ontological classification of verb entries will start in the near future. With respect to MWN, word senses are not hierarchically structured and no semantic relation is encoded. Senses of polysemous entries have a flat representation, one following the other.

Related Works

Previous works in word sense alignment can be divided into two main groups: a.) approaches and frameworks which aim at linking lexica based on different models to WN synsets [START_REF] Rigau | Disambiguating bilingual nominal entries against WordNet[END_REF]; [START_REF] Navigli | Meaningful clustering of senses helps boost word sense disambiguation performance[END_REF]; [START_REF] Roventini | Mapping concrete entities from PAROLE-SIMPLE-CLIPS to ItalWordNet: Methodology and results[END_REF] or language resources, such as Wikipedia [START_REF] Ruiz-Casado | Automatic assignment of Wikipedia encyclopedic entries to WordNet synsets[END_REF]; [START_REF] Mihalcea | Using Wikipedia for automatic word sense disambiguation[END_REF]; [START_REF] Niemann | The peoples web meets linguistic knowledge: Automatic sense alignment of Wikipedia and WordNet[END_REF]), and b.) approaches towards the merging of different language resources [START_REF] Gurevych | Uby -a large-scale unified lexical-semantic resource based on LMF[END_REF]; [START_REF] Navigli | BabelNet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network[END_REF]). Our work clearly fits into the first group. While different methods are employed (similaritybased approaches vs. graph-based approaches), common elements of these works are: i.) the extensive use of lexical knowledge based on the sense descriptions such as the WN glosses or an article first paragraph as in the case of Wikipedia; and ii.) the extension of the basic sense descriptions with additional information such as hypernyms for WN entries, domains labels or categories for dictionaries or Wikipedia entries so as to expand the set of available information, thus improving the quality of the alignments.

As for our task, the most similar work is [START_REF] Navigli | Meaningful clustering of senses helps boost word sense disambiguation performance[END_REF] where entries from a lexicographic dictionary, namely the Oxford English Dictionary (OED), are mapped to WN. The author adopts and compares two methods: a.) a pure lexical matching function based on the notion of lexical overlap [START_REF] Lesk | Automatic sense disambiguation using machine readable dictionaries: how to tell a pine code from an ice cream cone[END_REF] of the lemmas in the sense descriptions; and b.) a semantic matching based on a knowledge-based WSD system, Structural Semantic Interconnections (SSI), built upon WN and enriched with collocation information representing semantic relatedness between sense pairs. In this latter approach, first each sense description in WN and in the OED is disambiguated by means of SSI with respect to the WN sense inventory, thus obtaining a semantic description as a bag of concepts. Then, two senses are matched if a relation edge is identified between the concepts in the description of each sense in the two lexica. Both approaches are evaluated with respect to a manually created gold standard. The author reports an overall F1 measure of 73.84% for lexical matching, and of 83.11% for semantic matching.

With respect to the SCDM, the OED has some advantages, namely i.) the distinction between core senses and subsenses for polysemous entries; ii.) the presence of hypernyms explicitly signalled; and iii.) domain labels associated with word senses. Such kind of information is not present in the SCDM where senses are presented as a flat list and no enrichment of the sense descriptions with additional information is available, except for the ontological tagging of nouns. Moreover, the low number of MWN glosses in Italian prevents a straightforward application of state-ofthe-art methods for sense alignment. MWN sense descriptions must be built up from other sources. Thus, the main issue we are facing is related to data sparseness, that is how to tackle sense alignment when we have few descriptions in Italian (MWN side) and few meta-data and no structure over senses (SCDM side).

The automatic alignment of senses has been conducted by applying two approaches for constructing the sense representations of the resources and evaluation.

Lexical Match

In the first approach, Lexical Match, for each word w and for each sense s in the given resources R ∈ {MWN, SCDM} we constructed a sense descriptions d R (s) as a bag of words in Italian. Provided the different characteristics of the two resources, two different types of bag of words have been built. As for the SCDM, the bag of words is represented by the lexical items in the textual definition of s w , automatically lemmatized and partof-speech analyzed with the TextPro tool suite [START_REF] Pianta | TextPro Tool Suite[END_REF] with standard stopword removal. On the other hand, for each synset, S, and for each part of speech in analysis, the sense description of each MWN synset was built by optionally exploiting:

• the set of synset words in a synset excluding w;

• the set of direct hypernyms of s in the taxonomy hierarchy in MWN;

• the set of synset words in MWN standing in the relation of nearest synonyms with s;

• the set of synset words in MWN composing the manually disambiguated glosses of s from the "Princeton Annotated Gloss Corpus"2 . To extract the corresponding Italian synset(s), we have ported MWN to WN 30;

• the set of synset words in MWN composing the gloss of s in Italian (when available);

• for verbs, the set of synset words in MWN standing in the relations of entailment/is entailed, causes/is caused with s;

• for nouns, the set of synset words in MWN standing in the relations of part of /has part, has member/is member with s.

The alignment of senses is based on the notion of lexical overlap. We used Text::Similarity v.0.09 module3 , and in particular the method Text::Similarity::Overlaps, to obtain the overlap value between two bags of words of s w . Text similarity is based on counting the number of overlapping tokens between the two strings, normalized by the length of the strings.

One of the well known limitation of the Lexical Match approach is the so called "lexical gap" problem [START_REF] Meyer | What psycholinguists know about chemistry: Aligning Wiktionary and WordNet for increased domain coverage[END_REF], i.e. a reduced number of overlapping words. To overcome this limit, we have exploited a newly developed multilingual resource, BabelNet [START_REF] Navigli | BabelNet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network[END_REF], which has been obtained by merging together WN synsets and Wikipedia pages with an accuracy of 83%. It contains 4,683,031 nominal glosses (2,985,243 of which are in English). In BabelNet English WN 3.0 synsets have been aligned to their corresponding Wikipedia pages and then extended to other languages, including Italian, by exploiting Wikipedia language links and WN mappings. As for our task, we have retained only those BabelNet entries which have a corresponding synset word in MWN. In this way, we have extended the bag of words representation of nominal entries for MWN synsets by adding the Italian Wikipedia glosses from BabelNet.

Sense Similarity

In the second approach, Sense Similarity, the basis for sense alignment is the Personalized Page Rank (PPR) algorithm [START_REF] Eneko | Personalizing PageRank for Word Sense Disambiguation[END_REF] relying on a lexical-semantic knowledge base model as a graph G = (V, E) as available in the UKB tool suite4 . As knowledge base we have used WN 3.0 extended with the "Princeton Annotated Gloss Corpus". Each vertex v of the graph is a synset, and the edges represent semantic relations between synsets (e.g. hyperonymy, hyponymy, etc.). The PPR algorithm ranks the vertices in a graph according to their importance within the set and assigns stronger initial probabilities to certain kinds of vertices in the graph. The result of the PPR algorithm is a vector whose elements denotes the probability for the corresponding vertex that a jumper ends on that vertex if randomly following the edges of the graph.

To obtain the PPR vector for a sense s of the SCDM, we have translated the Italian textual definitions in English by means of a state-of-theart Machine Translation system5 , automatically lemmatized and part-of-speech analyzed with the TextPro tool suite, remove standard stopwords and applied the UKB tool suite. The PPR vector is a thus semantic representation overall the entire WN synsets of the textual definition of s in SCDM.

As for the MWN synsets, we have exploited its conversion to WN 3.0. Instead of building the PPR vector by means of the lexical items, we have passed to the UKB tool suite the WN synset id, thus assuming that the MWN synset is already disambiguated. Given two PPR vectors, namely ppr mwn and ppr scdm for the MWN synset w syn and for the SCDM sense w scdm , we calculated their cosine similarity. On the basis of the similarity score, the sense pair is considered as aligned or not.

Experiments and Evaluation

Gold Standards

To evaluate the reliability of the two approaches with respect to our data, we developed two different gold standards, one for verbs and one for nouns.

The verb gold standard is composed by 44 lemmas selected according to corpus frequency (highly frequent lemmas in the La Repubblica Corpus [START_REF] Baroni | Introducing the "la Repubblica" corpus: A large, annotated, TEI(XML)-compliant corpus of newspaper italian[END_REF]) and patterns in terms of semantic and syntactic features6 . It is composed by 350 aligned sense pairs obtained by manually mapping the MWN synsets to their corresponding senses in the SCDM lexicon. These verbs corresponds to 279 synsets and 424 senses in the SCDM. Overall, 211 of the 279 MWN synsets have a corresponding sense in the SCDM (i.e. SCDM covers 84.22% of the MWN senses in the data set), while 235 out of 424 SCDM senses have a correspondence in MWN (i.e MWN covers 49.76% of the SCDM senses). Average degree of polysemy for MWN entries is 6.34, while for the SCDM is 9.63.

The noun gold standard is composed by 46 lemmas selected according to frequency and polysemy with respect to the fundamental senses in the SCDM (each lemma must have at least two fundamental senses in the SCDM). On the basis of the manual alignment, we have obtained 166 aligned sense pairs. The noun lemmas correspond to 229 synsets and 216 senses in the SCDM. Overall, 134 of the 229 MWN synsets have a corresponding sense in the SCDM (i.e. SCDM covers 53.71% of the MWN senses in the data set), while 123 out of 216 SCDM senses have a correspondence in MWN (i.e MWN covers 62.03% of the SCDM senses). Average degree of polysemy for MWN entries is 4.97, while for the SCDM is 4.69. The difference in terms of coverage with respect to the verbs is clearly due to two aspects, namely i.) the restrictions of the SCDM entries to the fundamental senses; ii.) the higher coverage in terms of nouns synsets of MWN with respect to the verbal ones.

Though small, the size of the gold standards is representative of the two lexica. In particular, the 279 verbs synsets yield 3,319 possible sense pairs, i.e. 11.8 SCDM senses per synset on average. As for nouns, the 229 nominal synsets yield 1,414 sense pairs, i.e. 6.13 SCDM senses on average.

Results

The evaluation has been performed by computing Precision (the ratio of the correct alignment with respect to all proposed alignments), Recall (the ratio of extracted correct alignment with respect to the alignments in the gold standard), F-measure (the harmonic mean of Precision and Recall calculated as 2P R/P + R) and Accuracy (the precentage of the correctly identifed alignments and non alignments). As baseline, we have implemented a random match algorithm, rand, which for the same word w in SCDM and in MWN assigns a random SCDM sense to each synset with w as synset word, returning a one-to-one alignment. The selection of the correct alignments has been obtained by applying two types of thresholds with respect to all proposed alignments (the "no threshold" row in the tables): i.) a simple cut-off at specified values (0.1; 0.2); ii.) the selection of the maximum score (either lesk measure or cosine; row "max score" in the tables) between each synset S and the proposed aligned senses of the SCDM. As for the maximum score threshold, we have retained as good alignments also instances of a tie, thus allowing the possibility of having one MWN synset aligned to more than one SCDM sense.

Table 1: Results for automatic alignment based on Lexical Match for SYN and SREL sense representations.

Lexical Match Results

We have analyzed different combinations of the sense representation of a synset. We developed two basic representations: SYN, which is composed by the set of synset words excluding the target word w to be aligned, all of its direct hypernyms, the set of synset words in MWN standing in the relation of nearest synonyms and the synset words obtained from the "Princeton Annotated Gloss Corpus"; and SREL, which contains all the items of SYN plus the the synset words included in the selected set of semantic relations. The results are reported in Table 1. As the figures show, all synset configurations outperform the baseline rand for both parts of speech in analysis. However, it is interesting to observe that the alignment of noun senses performs much better than that for verbs in both sense representations and with all filtering methods. On the basis of the alignment method (i.e. lexical overlap) such a difference in performance provides interesting data on the two resources in analysis. A manual exploration of the data in the configurations both for verbs and nouns has highlighted that, on the one hand, we suffer from data sparseness on the SCDM side as no extension of the sense description of the glosses is possible, and, on the other hand, that senses are described in ways that are semantically equivalent but with different lexical items.

As for verbs the Recall with no filtering (no threshold) has extremely low levels, ranging from 0.32 for SREL to 0.29 for SYN. The SREL sense representation outperforms SYN when no filtering is applied only in terms of Recall (+0.03), thus signaling that the additional semantic relations play a very limited role in the description of verb senses without providing real additional information to match data in the SCDM glosses. Furthermore, the difference in performance of the SREL configuration is not statistically significant with respect to the SYN configuration (p > 0.05).

The situation looks different for nouns where, although low, the no threshold Recall values range between 0.60 (SREL) to 0.59 (for SYN). As for the two basic configurations, SYN and SREL, the results show that SYN is more accurate and that the impact of additional semantic relations, though it slightly improves the Recall, is not statistically signiticant (p > 0.05).

Both for verbs and nouns we decided to select the SYN basic configuration as the best sense representation because it has a simpler bag-of-words and better Precision. To improve the results, we have extended this basic representation with the lexical items in the corresponding glosses of Ba-belNet (+BABEL) (only for nouns) and the lexical items of the MWN Italian glosses (+IT) (for verbs and nouns)7 . The results are illustrated in Table 2.

In both cases, the extension of the basic sense representations with additional data is positive, namely for Recall. Notice that for verbs the presence of Italian MWN glosses improves the alignment results (for the no-threshold filter, F1=0.37 vs. F=0.35 for SREL and F1=0.34 for SYN) as they introduce information which better represents the sense definition than the synset words in the bag of words representations and overcomes missing information in the WN 3.0 annotated glosses. For instance, consider the following example for the verb "rendere" [to make]. In example 1a) the two senses are aligned with a very low lexical overlap score as there is only one word in com- The positive effect of the original Italian data for verbs points out a further issue for our task, namely that the derivation of sense representations of MWN synsets by means of synset words (including the sense annotated glosses of WN 3.0) is not as powerful as having at disposal original glosses.

Similarly, for nouns we register an improvement in Recall at a low or null cost for Precision for all filtering methods, with the exclusion of the no threshold filtering. Precision for SYN+BABEL+IT with maximum score filtering is lowered with respect to the extension with the BabelNet data only (P=0.66 for SYN+BABEL+IT vs. P=0.69 for SYN+BABEL)8 . To better clarify these results, consider the following example for the noun "palla" [ball]. In the example 2a) the two senses are not aligned as there are no matching words, while in 2b) the extension by means of the BabelNet data provides a sufficient number of matching items for aligning the two senses. As for the previous example, the lexical items of the sense descriptions are reported in Italian, matching words are in bold. Concerning the filtering of the proposed alignments, the maximum score filter provides the best results for Precision at a low cost in terms of Recall, with F1 scores for verbs ranging from 0.34 (SYN+IT) to 0.29 (SYN), and from 0.55 (SYN+BABEL) to 0.52 (SYN and SREL) for nouns. It is interesting to point out a further difference in performance between verbs and nouns. In particular, for verbs we can observe that the filtering based on maximum score has lower F1 values with respect to the no threshold baseline in all sense descriptions. As for nouns, on the contrary, both the two basic sense descriptions, SYN and SREL, and the SYN+BABEL configuration have comparable F1 values between the no threshold and the maximum score data. Nevertheless, the filtering based on the maximum score improves the quality of the proposed alignment by removing lots of false positives both for verbs and nouns (for verbs P=0.59 for SYN, P=0.60 for SREL, and P=0.63 for SYN+IT; for nouns, P=0.69 for SYN, SREL, and SYN+BABEL, P=0.66 for SYN+BABEL+IT) without impacting on the number of good instances retrieved (for verbs R=0.19 for SYN, R=0.20 for SREL, and R=0.23 for SYN+IT; for nouns R=0.42 for SYN and SREL, R=0.44 for SYN+BABEL; R=0.45 for SYN+BABEL+IT).

Similarity Measure Results

The results for the Similarity Measure obtained from the Personalized Page Rank algorithm on the basis of the vectors described in Section 4.2 are illustrated in Table 3. Similarly to the Lexical Match, the Personalized Page Rank approach outperforms the baseline rand. Overall, the differences in performance with the Lexical Match results are not immediate. In general, as the Recall values for no threshold filtering show, almost all aligned sense pairs of the gold are retrieved, outperforming the Lexical Match. Clearly, this difference is strictly related to the different nature of the sense descriptions, i.e. a semantic representation based on a lexical knowledge graph, which is able to catch semantically related items out of the scope for the Lexical Match approach.

By observing the figures for verbs, we notice that the simple cut-off thresholds provide better results with respect to the maximum score. The best F1 score (F1=0.32) is obtained when setting the cosine similarity to 0.1, though Precision is less than 0.50 (namely, 0.47). When compared with threshold value of 0.1 of the Lexical Match, the Personalized Page Rank method yields the best Precision (P=0.47 vs. P=0.42 for Verb SYN, P=0.38 for Verb SYN+IT, and P=0.40 for Verb SREL). Similar observations can be done when the threshold is set to 0.2. In this latter case, Personalized Page Rank yields the best Precision score for verbs with respect to all other filtering methods and the Lexical Match results obtained with maximum score (P=0.66 vs. P=0.59 for Verb SYN, P=0.63 for Verb SYN+IT, and P=0.60 for Verb SREL).

The analysis for nouns is more complex. Apparently, the Personalized Page Rank approach has lower F1 scores with respect to all Lexical Match sense configurations and filtering methods, including the no threshold score of the basic sense descriptions (respectively, F1=0.55 for SYN, F1=0.54 for SREL, F1=0.21 for Personalized Page Rank). However, when maximizing Precision for the Personalized Page Rank (threshold 0.2), the algorithm provides better performances (F1=0.33) with respect to Lexical Match on the same filtering method, minimizing the drop of Recall (R=0.21; +0.09 with respect to SYN+BABEL with same threshold; + 0.08 with respect to SREL; +0.05 with respect to SYN, respectively).

The better performance of the simple cut-off thresholds with respect to the maximum score is due to the fact that aligning senses by means of semantic similarity provides a larger set of alignments and facilitates the identification of multiple alignments, i.e. one-to-many.

Merging Lexical Match and Sense Similarity

As The combination of the best results yields the best performance for both parts of speech compared to the stand-alone approaches. In particular, for verbs we obtain an F1=0.47, with an improvement of 0.18 points with respect to SYN and of 21 points with respect to Personalized Page Rank with threshold 0.2. Similar improvements can be observed for nouns, where SYN+BABEL+ppr02 has an F1=0.64, with an improvement of 9 points with respect to SYN+BABEL and of 31 points with respect to Personalized Page Rank with threshold 0.2. In both cases the performance gains originate from the higher precision of the Personalized Page Rank approach which minimizes the data sparseness of the SCDM lexicon.

Conclusion and Future Work

This paper focuses on the automatic alignment of senses from two different resources when few data are available. In particular, the lack of Italian glosses in MWN and the absence of any kind of structured information in the SCDM dictionary posed a serious issue for the application of stateof-the-art techniques for sense alignment.

We experimented with two different approaches: Lexical Match and Sense Similarity obtained from Personalized Page Rank. In all cases, when filtering the data we are facing low scores for Recall which point out issues namely related to data sparseness in our lexica. By comparing the results of the two approaches, we can observe that: i.) the Personalized Page Rank yields the best Precision with respect to Lexical Match; ii.) Lexical Match, with a simple sense description configuration (i.e. the SYN configurations for verbs and nouns), is still a powerful approach for this kind of tasks; the exploitation of additional semantically related items (e.g. SREL for verbs) or additional sense descriptors (e.g. SYN+BABEL for nouns), though good in principle, has a limited contribution to solve the "lexical gap" problem in our case and points out differences in the way word senses are encoded in the two lexica; and iii.) Personal-ized Page Rank vectors and Lexical Match appears to qualify as complementary methods for achieving reliable sense alignments, namely when dealing with few data. Our approach provides satisfying results both for verb and noun sense alignment, with an overall F1=0.47 for verbs and an F1=0.64 for nouns. The better results for nouns are strictly related to the definitions of the senses which mainly relies on synonym words and hypernyms. On the other hand, verbs tend to have more abstract definitions and the contribution of additional semantic relations (i.e. the SREL configuration) is poor.

Future work will concentrate on two aspects by exploiting the sense alignment results. The aligned sense pairs will be used for sense clustering as a strategy to reduce the sense descriptions in MWN and in SCDM. Existing clustering of WN senses (e.g. [START_REF] Navigli | Meaningful clustering of senses helps boost word sense disambiguation performance[END_REF]) will be used as a starting point and for subsequent evaluation. Furthermore, we aim at importing the ontological classes of SCDM in MWN. This aspect will be useful for the identification of possible taxonomical errors in the MWN hierarchy and boostrap better sense alignments.

Table 3 :

 3 Results for automatic alignment based on Similarity Score.

Table 4 :

 4 Results for automatic alignment merging the best results from Lexical Match and Sense Similarity.

	the two approaches are different in nature both
	with respect to the creation of the sense descrip-
	tions (simple bag of words vs. semantic represen-
	tation) and to the methods with which the align-
	ment pairs are extracted and computed, we have
	developed a further set of experiments by merging
	together the results obtained from the best sense
	descriptions and best filtering methods for Lexical
	Match and Semantic Similarity. As parameters for
	the identification of the best results we have taken
	into account the Precision and F1 values. Exclud-
	ing the presence of Italian data from the sense de-
	scriptions of the Lexical Match approach due to
	their sparseness, we selected the SYN sense de-
	scription filtered with maximum score for verbs
	(P=0.59, F1=0.29) and the SYN+BABEL sense
	description filtered with maximum score for nouns
	(P=0.69; F1=0.55). As for the Personalized Page
	Rank approach, we have selected both for verbs
	and nouns the cut-off threshold at 0.2. The results
	are reported in Table 4.

http://www.sensocomune.it

See http://wordnet.princeton.edu/ glosstag.shtml

http://www.d.umn.edu/ ˜tpederse/ text-similarity.html

See http://ixa2.si.ehu.es/ukb/

We use Google Translate API.

A subset of these verbs have been taken from[START_REF] Jezek | Capturing coercions in texts: a first annotation exercise[END_REF]

The Italian MWN glosses for the items in the Golds are present for 24% senses of verbs and 30% senses of nouns, respectively

Excluding the BabelNet data and running the alignment only with the Italian glosses, SYN+IT, with maximum score filtering, gives F1=0.52 which is the same as SYN and SREL, and lower that SYN+BABEL.


Bartłomiej Błaszczyszyn
email: bartek.blaszczyszyn@ens.fr

Anastasios Giovanidis
email: anastasios.giovanidis@telecom-paristech.fr

Optimal Geographic Caching In Cellular Networks

Keywords: wireless cache, Poisson cellular network, SINR kcoverage, hit probability, content popularity, optimization

In this work we consider the problem of an optimal geographic placement of content in wireless cellular networks modelled by Poisson point processes. Specifically, for the typical user requesting some particular content and whose popularity follows a given law (e.g. Zipf), we calculate the probability of finding the content cached in one of the base stations. Wireless coverage follows the usual signal-to-interference-and noise ratio (SINR) model, or some variants of it. We formulate and solve the problem of an optimal randomized content placement policy, to maximize the user's hit probability. The result dictates that it is not always optimal to follow the standard policy "cache the most popular content, everywhere". In fact, our numerical results regarding three different coverage scenarios, show that the optimal policy significantly increases the chances of hit under high-coverage regime, i.e., when the probabilities of coverage by more than just one station are high enough.

I. INTRODUCTION

Today's cellular networks provide additionally to traditional telephony and messaging services, a considerable amount of multimedia content. Multimedia traffic demand is expected to show exponential increase in the years to come. Recent suggestions to densify the network via multi-tier heterogeneous equipment or to apply cooperation techniques [START_REF] Baccelli | Coverage by pairwise base station cooperation under adaptive geometric policies[END_REF], will locally improve wireless throughput but will eventually push the network's backhaul and its available bandwidth to its limit.

Considering the fact that the great volume of traffic consists of multiple demands for the same content by various users, a solution to relieve the overloaded network is to cache popular content at intermediate nodes. In the case of cellular networks, this practically translates in adding physical memory at the central base station (BS) and the smaller scale (pico, nano, etc.) stations. Wired architectures consider caching on routers of the core network. All these ideas follow the novel concept of Information Centric Networks (see [START_REF] Xylomenos | A survey of Information-Centric Networking[END_REF] and also [START_REF] Rossini | A dive into the caching performance of content centric networking[END_REF]), which challenges the existing host-centric Internet architecture and puts the emphasis on the content itself.

There are several benefits from doing so: (a) The most evident is the reduction of backhaul traffic load. (b) Another one is the reduction of multimedia (audio/video) playback latencies. When the content is cached at a node close to the user, it is delivered with less delay than fetching it from the core network. (c) Caching can give the opportunity to adapt the multimedia quality to the actual end-users' channel, and consequently improve Quality-of-Experience [START_REF] Poularakis | Video delivery over heterogeneous cellular networks: Optimizing cost and performance[END_REF].

In the literature there are already considerable works dealing with the problem of cellular caching. Among these, the paper by Shanmugam et al [START_REF] Shanmugam | FemtoCaching: Wireless content delivery through distributed caching helpers[END_REF] treats the problem of optimal association of content to wireless caches, given BS-user topology. Bastug et al in [START_REF] Bastug | Cache-enabled Small Cell Networks: Modeling and Tradeoffs[END_REF] provide stochastic geometry results on the user outage probability and average delay experienced. The optimal storage allocation related to user mobility is addressed by Poularakis and Tassiulas in [START_REF] Poularakis | Exploiting user mobility for wireless content delivery[END_REF]. Further benefits and challenges from the application of caching in 5G networks are presented in the work by Wang et al [START_REF] Wang | Cache in the Air: Exploiting content caching and delivery techniques for 5G systems[END_REF]. In all the above, it is common to consider a fixed content library and a popularity distribution which is known a priori and follows the Zipf distribution. The latter was proposed and verified to well approximate the hit distribution of Internet content by Newman [START_REF] Newman | Power laws, Pareto distributions and Zipf's law[END_REF].

The great difference of caching in cellular networks as compared to wired ones, is that there can appear planar regions with overlapping coverage by more than one BS [START_REF] Keeler | SINR-based k-coverage probability in cellular networks with arbitrary shadowing[END_REF]. When a user finds him/herself in such areas, he/she can choose service by any of the covering stations. Such observation has indeed been taken into consideration in the works of [START_REF] Shanmugam | FemtoCaching: Wireless content delivery through distributed caching helpers[END_REF], [START_REF] Poularakis | Video delivery over heterogeneous cellular networks: Optimizing cost and performance[END_REF], [START_REF] Poularakis | Exploiting user mobility for wireless content delivery[END_REF], but the discrete problem formulations suggested fail to give solutions with global validity, because they are based on a priori known BS-user topologies. A novel related work is [START_REF] Altman | Distributed Storage in the Plane[END_REF].

In our work we will revisit the problem of optimal content placement in cellular caches by assuming a known distribution of the coverage number, i.e. the number of BSs simultaneously covering a user. We will see different expressions for this distribution based on different coverage models, like the SINR model in [START_REF] Keeler | SINR-based k-coverage probability in cellular networks with arbitrary shadowing[END_REF] where the network topology was modelled by a Poisson point process. As a main result, we will provide the optimal probabilistic placement policy, which guarantees maximal total hit probability for random network topologies. To achieve optimality, the policy exploits multi-coverage regions and delivers considerable performance improvement compared to the standard "cache the most popular content, everywhere" strategy. We argue that the latter is not optimal in general networks but only either for an isolated cache [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] or when there is no coverage overlap in the network.

The model under study is presented in Section II, where the probabilistic caching policy is introduced and three coverage model examples are given. In Section III we state and solve the content placement optimization problem. Evaluation of the optimal strategy for three different coverage models is presented in Section IV. We conclude the paper in Section V.

II. MODEL UNDER STUDY

We consider a cellular network where the positions of Base Stations (BSs) coincide with the atoms from the realization of a two dimensional (2D) Poisson Point Process (PPP) Φ = {x i }. The PPP is homogeneous and has intensity λ > 0. The performance of the network is evaluated at the Cartesian origin (0, 0), which we denote as the typical user o. Due to the Slivnyak-Mecke theorem and the stationarity and isotropy of the PPP, the results for the typical user apply to any user randomly located on the 2D plane [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF].

A. Network Coverage Number

In cellular networks a user at a random location may be covered by more than one BS, or may not be covered at all. A user may also be covered by multiple networks. The so called coverage number N is a random variable (r.v.) [START_REF] Keeler | SINR-based k-coverage probability in cellular networks with arbitrary shadowing[END_REF] that depends on the features of the communications scheme and the network parameters. It has a mass function

p m := P [N = m] , m = 0, 1, . . . (1)
The maximum number of covering BSs is M ∈ N + ∪ {∞}, where we let the coverage number be unlimited in the general case. Later in the section, we will give specific expressions for the p m , which depend on the network evaluated. Obviously, it holds

M m=0 p m = 1. (2)
Specific coverage models are presented in Section IV-A.

B. Content and its Popularity

Each user has a request for a specific content (say video file) that he/she wants to receive. In our model the set (library) of available content is finite. It is denoted by C := {c 1 , c 2 , . . . , c J }, where an element c j is an entire file. The cardinality of the set is J. We consider that all content has the same size, normalised to 1. Cases of unequal size will not be treated in this work, but we can always assume that each file can be divided into chunks of equal size, so the same analysis can still be applied. Furthermore, each content is related to its popularity, which we assume known a priori. We order the content by popularity: c 1 is the most popular content, c 2 the second most popular and so on. The popularity follows a distribution {a j }. To be consistent with the above ordering, a 1 ≥ a 2 ≥ . . . ≥ a J . Without losing in generality, we will often consider that the distribution has a Zipf probability mass function and consequently the probability that a user (hence the typical one) will ask for content c j is equal to

a j = A -1 j -γ . (3)
Here, γ is the Zipf exponent, often (but not necessarily) chosen as γ < 1, so that a 1 /a 2 = 2 γ < 2. It holds

J j=1 a j = 1, (4)
and this explains the normalisation factor A := J j=1 j -γ .

C. Content Placement to Caches

We assume that a cache memory of size K ≥ 1 is installed and available on each BS. The memory inventory of BS x i ∈ Φ is denoted by Ξ (i) , which is a subset of C, with the number of elements not larger than K; i.e., |Ξ (i) | ≤ K for all i.

We consider a probabilistic model, where the content is independently, placed in the cache memories of different BSs, according to the same distribution. In other words, Ξ (i) are Fig. 1. A realization of the probabilistic placement policy for the case of J = 9 contents and K = 4 memory slots. We first draw uniformly a random number (0.42). The vertical line at this point intersects with each of the 4 memory intervals at a specific content. We conclude from the figure that the subset {c 1 , c 2 , c 4 , c 7 } will be cached. assumed independent identically distributed (random) subsets of C. Denote by

b j := P c j ∈ Ξ (i)
the probability that the content c j is stored at a given base station. (The model is homogeneous, hence the values of b j are common for all BSs x i ; and the superscript • (i) can be omitted when considering a generic base station.)

As we shall see, the probability that a typical user finds the content he/she is looking for in the inventory of a base station covering him/her (which is the performance metric we want to maximize) depends on the distribution of the (random) set Ξ only through the one-set-coverage probabilities b j , j = 1, . . . , J. And these probabilities do not define the distribution of the random set Ξ -hence the content placement policyuniquely.

When looking for the optimal values b j , j = 1, . . . , J, we shall consider the following constraints

J j=1 b j ≤ K, (5)
0 ≤ b j ≤ 1, ∀j. (6)
The second condition is obvious (b j is a probability). Regarding the first one we have the following result.

Fact 1. Assuming (6), the condition ( 5) is necessary and sufficient for the existence of a distribution of Ξ satisfying |Ξ| ≤ K almost surely, i.e. existence of a random content placement policy requiring no more than K slots of memory at each base station.

Proof: The necessity follows from the observation that the right-hand side of ( 5) is equal to the expected number of content items in the base station inventory. Indeed

E   J j=1 1(c j ∈ Ξ)   = J j=1 P (c j ∈ Ξ) = J j=1 b j .
We prove the sufficiency by constructing (in what follows) some particular content placement policy satisfying |Ξ| ≤ K.

The following policy having one-set-coverage probabilities b j satisfying ( 5) and ( 6) respects the cache size constraint K.

Probabilistic placement policy: Given the cache memory of size K ≥ 1, and the values b j , j = 1, . . . , J satisfying ( 5) and ( 6), we divide it into K continuous memory intervals of unit length and place them one under the other, as shown in the example considered on Fig. 1 (the example assumes equality in ( 5)). The J contents of the library are picked one after the other without replacement and their values b j fill the memory.

If not enough space is available in one unitary memory slot, the content fills the slot underneath. In order to randomly choose a set of contents, we pick uniformly a number within [0, 1] and draw a vertical line which intersects the memory space covered by no more than K distinct contents, (It intersects exactly K contents if the equality is observed in [START_REF] Shanmugam | FemtoCaching: Wireless content delivery through distributed caching helpers[END_REF].) The contents are distinct because b j ∈ [0, 1]. Moreover, the probability of appearance of content j in a memory of size K is exactly equal to b j .

III. OPTIMAL CONTENT PLACEMENT -PROBLEM STATEMENT AND SOLUTION

The performance metric of interest is the total hit probability, i.e. the probability that the typical user will find the content he/she is asking for in one of the BSs he/she is covered from. This is 1-minus the probability that the user does not find its content. This happens when the user is covered by m = 0 BSs (i.e. no coverage), or by some number m > 0 but the content has not been saved in the cache memory space of any of these BSs. The performance metric is equal to

f (b 1 , . . . , b J ) := 1 - J j=1 a j ∞ m=0 p m (1 -b j ) m . (7)
To better understand the above expression, m is the number of BSs that the user is covered by. The probability (1 -b j ) m is the probability that none of the cache memory slots of these stations contains the desired content. Hence, the expression in [START_REF] Poularakis | Exploiting user mobility for wireless content delivery[END_REF] is the probability that the content requested by the user should be fetched from the backhaul network.

We can control the hit probability, by varying the content placement probabilities b j . In the following we will find the optimal vector (b 1 , . . . , b J ), that maximises the objective function f in [START_REF] Poularakis | Exploiting user mobility for wireless content delivery[END_REF]. The constraint set of our problem is

F 1 := {(b 1 , . . . , b J )| b 1 + . . . + b J ≤ K, & b j ∈ [0, 1] , ∀j} (8)
The parameters that influence the objective function but cannot be used as actions are (a) the size of memory K, (b) the probability of content popularity a j , j = 1, . . . , J and (c) the probability of coverage by m BSs p m , m = 0, 1, . . .. Altogether, we summarize the optimisation problem below, which we call GCP (Geographic Caching Problem) and in the following we will try to find its solution.

max f (b 1 , . . . , b J ) [GCP] s.t. (b 1 , . . . , b J ) ∈ F 1 .
We first give two Lemmas that facilitate the solution.

Lemma 1. The objective function of [GCP] has the following two properties:

• P.1: It is separable w.r.t. b 1 , . . . , b J .

• P.2: It is increasing and concave in b j , ∀j. Consequently, it is a concave function of (b 1 , . . . , b J ).

Proof: P.1 results by rewriting the objective function after replacing ( 4

), 1 = J j=1 a j . Then f (b) = J j=1 g (a j , b j , p) = J j=1 a j (1 - M m=0 p m (1 -b j ) m
). P.2 becomes trivial due to the separability property. We only need to show that the first derivative of g(b j ) is ≥ 0 and the second ≤ 0, ∀b j . Lemma 2. At the optimal solution, the sum constraint inequality ( 5) is active, i.e. the optimal solution satisfies b

* 1 + . . . + b * J = K. ( 9
)
Proof: Suppose that the inequality is inactive, i.e. strictly < K for the optimal solution. But then, for any l ≤ J, we can increase b * l → b * l + , so that the constraint is satisfied with equality. Substituting in the objective function b * l + instead of b * l the value of the function will increase, because f is increasing over b l , by P.2. Hence the primal optimal solution cannot leave the constraint inactive and ( 9) is true.

Since the objective function is concave by P.2 and the constraint set is linear (affine inequalities), the optimisation problem can be solved as a convex program. We will make use of the Lagrangian relaxation method (see [START_REF] Boyd | Convex Optimization[END_REF]). Let us relate the dual price µ ≥ 0 to the sum constraint inequality [START_REF] Shanmugam | FemtoCaching: Wireless content delivery through distributed caching helpers[END_REF]. The Lagrangian function is

L (b 1 , . . . , b J , µ) = J j=1 a j 1 - ∞ m=0 p m (1 -b j ) m + + µ   K - J j=1 b j   , (10)
and the remaining constraint set is F 2 := {b j ∈ [0, 1] , ∀j = 1, . . . , J}. We can systematically find the optimal primal (b * j ) and dual (µ * ) variables by solving a min-max problem. Additionally, in our case where we deal with a convex program, the optimal value of the min-max problem (f * ) is equal to the optimal value of the original problem [GCP] with objective function f , that is

f * := max F1 f (b 1 , . . . , b J ) = min µ≥0 max F2 L (b 1 , . . . , b J , µ) . = f (b * 1 , . . . , b * J ) . (11)
We then say that the duality gap between the original [GCP] problem and the min-max problem is zero. Theorem 1. The optimal primary variables, that maximise the [GCP] objective, given the optimal dual variable µ * is b

* j = b j (µ * ) with the expression b j (µ * ) = 1, if a j p 1 > µ * ω (µ * ), if a j p 1 ≤ µ * ≤ a j E [N ] 0, if a j E [N ] < µ * . (12)
In the above, E [N ] = ∞ m=1 mp m and ω (µ * ) is the solution over b j of the equation

a j M m=1 p m m(1 -b j ) m-1 = µ * . ( 13
)
The optimal dual variable µ * satisfies the equality b

1 (µ * ) + . . . + b J (µ * ) = K. (14)
Proof: Sketch. Given any dual price µ ≥ 0, we first solve the relaxed primary problem max F2 L (b 1 , . . . , b J , µ) over the b j s as shown in [START_REF] Altman | Distributed Storage in the Plane[END_REF]. From Lemma 1 and the affinity of the relaxed constraint, the primal problem is separable in J subproblems, each one having as constraint b j ∈ [0, 1]. The solution for each µ, hence also for µ * is given in [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] and [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF]. We further need to minimize the function q (µ) = max F2 L (b 1 , . . . , b J , µ) over µ. The standard way to do this is by use of a subgradient method. However, in our problem we need not proceed this way due to Lemma 2, which states that the optimal primal solution satisfies the relaxed constraint with equality. To find µ * , we thus have to replace the solution [START_REF] Martina | A unified approach to the performance analysis of caching systems[END_REF] in the equation J j=1 b j (µ) = K and solve over µ. The solution is unique since we can prove that the sum of b j s is a decreasing function in µ within an interval that is guaranteed to contain the solution.

Algorithm. The solution is found numerically as follows. We start by an interval of µ that contains the optimal solution, i.e. µ (0) ∈ µ (0,min) , µ (0,max) = [a K p 1 , a 1 E [N ]]. Then we use the bisection method, according to which J j=1 b j µ (l+1) is evaluated for l = 0, 1, . . . at the dual price µ (l+1) := µ (l,min) + (µ (l,max) -µ (l,min) )/2. If the value of the sum is < K then the search continues to the left interval and µ (l+1,max) := µ (l+1) , else if the sum is > K, the search continues to the right interval and µ (l+1,min) := µ (l+1) . The algorithm stops when the change in µ for some step l is smaller than a chosen > 0. The difficulty in the implementation lies in the fact that we need to solve also the polynomial equalities of the form [START_REF] Baccelli | Stochastic Geometry and Wireless Networks[END_REF], which do not give a closed form solution when M is large. We also solve these over b j by use of the bisection method.

To provide some intuition, we consider in what follows a simple example assuming J = 2, K = 1.

Example 1 (2CP). Consider the case of one-slot cache memory K = 1 and the content library of size J = 2 with a 1 +a 2 = 1 and maximum M = 2 BSs covering a user. We call this problem the [2CP]. It has the following explicit solution. The optimal pair (b

* 1 , b * 2 ) that solves the [2CP] problem is b * 2 = 1 -b * 1 where b * 1 = 2a1(p1+p2)-p1 2p2 , if 0 ≤ a 1 ≤ 1 - p1 2(p1+p2) . 1, otherwise (15)
IV. PERFORMANCE EVALUATION

We will now evaluate the performance of the placement policy given in Theorem 1 for some three different coverage models, which we present first.

A. Coverage Models

We overview three specific network models that give different expressions to the coverage number probability p m .

1) SINR Model: The quality of coverage at the origin is described by the SINR o (from now on SINR). SINR(x i ) is the SINR at the reception, when user o is connected to BS x i ∈ Φ and is defined as

SINR(x i ) := S i / (r i ) W + I -S i / (r i ) . (16)
In the above, S i is the shadowing experienced between the typical user and the BS at x i . The constant W is the noise power, I = xi∈Φ S i / (r i ) is the total received power from the network, r i = |x i | is the distance of x i from o, and (r) = (Br) β is the path-loss function, with constants B > 0, β > 2. We say that the typical user is covered when SINR(x i ) > T , where T is a predefined positive threshold.

The coverage number N (T ) indicates how many BSs cover the typical user simultaneously and is the r.v.

N (T ) = xi∈Φ 1[SINR(x i ) > T ]. (17)
For the coverage of a user who can choose to be served by different BSs in some realization of Φ, we make use of a basic result from [13, Proposition 6.2], analysed further in [START_REF] Keeler | SINR-based k-coverage probability in cellular networks with arbitrary shadowing[END_REF]. It is shown that if m stations cover a user at SINR level T , then the following inequality holds

M = 1 T ⇔ m < 1 + 1/T. (18)
For example, when T ≥ 1 then necessarily m < 1 + 1 T < 2 which implies that m ∈ {0, 1} and M = 1. Similarly, when 1 > T ≥ 1/2, m ∈ {0, 1, 2} and M = 2, etc. Based on this model, the authors in [START_REF] Keeler | SINR-based k-coverage probability in cellular networks with arbitrary shadowing[END_REF] have given explicit expressions for the probability that the typical user is covered by exactly m BSs in the SINR model without frequency reuse. For general shadowing, they have calculated the probability p SINR m In the interference limited network (W = 0) some results regarding the Poisson-Dirichlet model can be used to calculate equivalently the above coverage probabilities, cf [START_REF] Keeler | SINR in wireless networks and the two-parameter Poisson-Dirichlet process[END_REF]Prop,[START_REF] Bastug | Cache-enabled Small Cell Networks: Modeling and Tradeoffs[END_REF].

:= P [N (T ) = m] (19)
2) Boolean Model: For the noise-limited case, where the interference is small compared to noise, we can use the Boolean model to calculate the probability of coverage by m BSs. This is a germ-grain model, where the atoms of the PPP are the germs. Centered on each atom is a grain, i.e. a 2D sphere B (x i , R b ) which describes the area of coverage. R b is a fixed radius that can be expressed by communications quantities. Specifically, if we only consider path-loss and no fading,

2 β

 2 I n,β (W a -β/2 )J n,β T 1-(n-1)T for 0 < T < 1/(n -1) and S n (T ) = 0 otherwise, with a = λπE[S ]/B 2 , λ is the intensity of base stations andI n,β (x) = 2 n ∞ 0 u 2n-1 e -u 2 -u β xΓ(1-2/β) -β/2 du β n-1 (C (β)) n (n -1)!(20)whereC (β) = 2π β sin(2π/β) = Γ(1 -2/β)Γ(1 + 2/β). η i ) dv 1 . . . dv n-1 (22) where η i := (1 -v i ) n-1 k=i+1 v k .The software developed for MATLAB is available in[START_REF] Keeler | SINR-based k-coverage probability in cellular networks[END_REF] to get the numerical values of p SINR m .

the received signal at the boundary should be larger than the threshold, in order to guarantee coverage, i.e. 3) Overlaid 2-Network Model: Very often in practice, it occurs that 2 (or more) networks of the same provider operate in parallel over an area, using different infrastructure (nodes) and orthogonal resources (bandwidth). It is typical, for example, for operators to have one network of base stations for 3G/4G technology and numerous WiFi hotspots within a city. Given that a user may chose between the two to connect to the Internet with his/her cellphone (and assuming for simplicity mathematically independent models of these two networks), the coverage number at the typical user is distributed as the convolution of the coverage probability vectors of the two individual networks p (1) = p

p (1) n p

(2)

B. Performance of the Content Placement Policies

In this section we show the performance benefits of our scheme compared to a standard policy, the one that places in the cache memory of size K, always K Most Popular Contents

1) Simple Scenario [2CP]:

We start by the solution of the [2CP] provided in Example 1. In the simulated example, we assume p 0 = 0.05 to be the probability that the typical user is not covered by any BS. Hence p 1 + p 2 = 0.95. A general picture of the way the optimal caching policy (b * 1 , b * 2 ) varies w.r.t. the coverage ratio p 1 /p 2 and for different values of the popularity a 1 , is given in Fig. 2(a). Here, the ratio p 1 /p 2 varies from 10 -2 → 10 2 and we find for each value the optimal b * 1 , given a 1 = {0.5, 0.6, 0.7, 0.8, 0.9}. We can deduce from the figure, that when each location is covered with high probability by 2 BSs, it is optimal to cache with probability b * 1 ≈ a 1 . When each location is covered with high probability by a single BS, it is optimal to cache with [MPC], i.e. b * 1 ≈ 1. In Fig. 2 2 ) and for different values of a 1 . We compare the solution to the value of the objective function under the [MPC], which is always equal to f (M P C) = a 1 (1p 0 ), irrespective of the values of p 1 , p 2 . From the figure we can observe a considerable performance improvement in the total hit probability, which is especially large when a 1 /a 2 is small (comparable popularities) and when p 1 /p 2 is small. 2) Boolean, SINR and Overlaid 2-Network Coverage: We further evaluate the general problem [GCP] for the three coverage models suggested in Section II. We consider a content library of size J = 25 and cache memories of size K = 5. Since in all three models coverage depends on the threshold ratio T , we use the latter as the variable on the x-axis. In all cases, increasing the service threshold T reduces the probability of coverage by m > 0 BSs, and consequently increases p 0 . Another important aspect is the relation of T with the transmission rate R. These two are related through the Shannon formula R = B W 1 2 log 2 (1 + T ), where the transmission bandwidth is considered here equal to B W = 5 MHz for typical applications.

In Fig. 3(a) we evaluate the total hit probability under the Boolean model, for which the values of p B m are calculated as in (23). We choose M = 10. The evaluation spans the threshold values T = 10 -2 → 2 • 10 3 . Compared to [MPC], we observe considerable gains in hit probability until T ≤ 10, which corresponds to rate service of R ≤ 8650 Kbits/sec. Given that 8000 Kbits/sec is a very high video quality from YouTube [START_REF] Youtube | Advanced encoding settings[END_REF], our approach can realistically improve the backhaul cellular network traffic under this model. In Fig. 3(b) the same performance evaluation is done for the SINR model, where the probability of coverage is found in closed form in [START_REF] Keeler | SINR-based k-coverage probability in cellular networks with arbitrary shadowing[END_REF]. We use the software developed for MATLAB and available in [START_REF] Keeler | SINR-based k-coverage probability in cellular networks[END_REF] to get the numerical values of p SINR m . These are used as input to solve the [GCP]. We chose to evaluate the interference-limited case, i.e. W = 0, thus we consider SIR. For numerical integration reasons, the minimum threshold is taken to be 5 • 10 -2 , which from (18) refers to at most 25 BSs covering a planar point. The maximum threshold value is 2 because due to (18) at most 1 BS can cover a planar point when T ≥ 1. From the figure we see that the benefits are not very important and appear until T ≤ 0.2, or equivalently R ≤ 650 Kbits/sec. This rate refers to audio files rather than video files, given that the a high quality encoded audio file has a rate of 512 Kbits/sec. The main reason for the poor performance is the generally low probability of coverage by more than one BS (around 20% at best). We conclude that in the SINR model without frequency reuse, it is optimal to use [GCP] for low bit rate content (audio) and [MPC] for high bit rate content (video).

Finally, Fig. 3(c) illustrates the performance gains when the [GCP] is applied to the case of coverage by 2 independent overlaid networks (2NET). The coverage probability p 2N ET m is given in (24). For both vectors of the convolution, we use the same numerical values from p SINR m as calculated in the single SINR network above. Due to the convolution, the coverage probability for m > 1 is now increased, since most planar areas will be covered by at least two BSs. In such case the [GCP] policy has impressive benefits in the entire domain of T , compared to the [MPC]. More than any other, this case emphasises the great potentials of optimal geographic caching of content.

V. CONCLUSIONS

In this work, we have revisited the problem of optimal content placement in caches within a cellular network. We exploited the fact that certain areas are covered by multiple BSs. An optimal policy is derived which suggests that when multi-coverage areas are significant, it is not optimal to cache the most popular contents everywhere. The total hit probability of the policy is evaluated in plots for three different coverage models (Boolean, SINR, Overlaid 2-Network) and the results are highly in favour of our approach.