Melhem El Helou

Marc Ibrahim
email: marc.ibrahim@usj.edu.lb

Samer Lahoud
email: samer.lahoud@irisa.fr

Kinda Khawam
email: kinda.khawam@prism.uvsq.fr

Dany Mezher
email: dany.mezher@usj.edu.lb

Member, IEEE Bernard Cousin
email: bernard.cousin@irisa.fr

Member, IEEE Melhem El Helou
email: melhem.helou@usj.edu.lb

A Network-assisted Approach for RAT Selection in Heterogeneous Cellular Networks

Keywords: Radio access technology selection, semi-Markov decision process, reinforcement learning, heterogeneous cellular networks. I

come

L'archive ouverte

To cope with this huge demand for capacity, next-generation networks rely on densely deployed base stations with hierarchical cell structures [START_REF] Cicconetti | 5G Radio Network Architecture[END_REF] (i.e., macro, micro, pico and femto cells). A cost-effective solution is to use existing radio access technologies (RATs). Upcoming 5G networks are thus being devised with the vision of heterogeneity [START_REF] Cicconetti | 5G Radio Network Architecture[END_REF]. Various RATs, including 3GPP and IEEE families, are being integrated and jointly managed. Deciding to which one mobiles connect is known as the RAT selection problem.

When intelligence is pushed to the network edge, rational users select their RAT in a way to selfishly maximize their utility. However, as users have no information on network load conditions, their decisions may be in no one long-term interest, causing performance degradation. Moreover, delegating decisions to the network optimizes overall performance, but at the cost of increased network complexity, signaling and processing load.

A real challenge is to design a RAT selection method that jointly enhances network performance and user experience, while signaling and processing burden remains reduced. We propose, in this paper, a network-assisted approach. The network provides information for the mobiles to make appropriate RAT selections. More precisely, mobile users select their RAT depending on their individual needs and preferences, as well as on the cost and QoS parameters signaled by the network. By appropriately tuning network information, user decisions are globally expected to meet operator objectives, avoiding undesirable network states. Thus, our approach enables selfoptimization, a key feature of self-organizing networks [START_REF]Telecommunication Management; Self-Organizing Networks (SON) Policy Network Resource Model (NRM) Integration Reference Point (IRP); Requirements[END_REF].

Our network-assisted approach has the particularity to involve two inter-dependent decision-making processes. The first one, on the network side, consists in deriving appropriate network information, so as to guide user decisions in a way to satisfy operator interests. The second one, where individual users combine their needs and preferences with the signaled network information, consists in selecting the RAT to be associated with, in a way to maximize user utility. Since, in their turn, user individual decisions influence the upcoming network information, the two decision makings are regarded to be inter-dependent. Thus, RAT selections dynamically involve operator objectives, and user needs and preferences.

To maximize long-term network performance, network information should depend not only on present load conditions, but also on expected future demands. In this paper, deriving network information is formulated as a Semi-Markov Decision Process (SMDP) [START_REF] Puterman | Markov Decision Processes[END_REF]. The aim is to dynamically meet operator objectives, while mobiles maximize their own utility. Also, when network parameters are not perfectly known, a reinforcement learning approach is introduced to derive what to signal to mobiles. The network learns user needs, preferences and decision-making algorithms through interacting with them.

II. RELATED WORK

A key driver for heterogeneous cellular networks is to enable traffic class-aware optimal coverage, capacity, and reliability with low cost and energy consumption. To maximize user experience, mobiles select their serving RAT depending on user needs and preferences. As user experience does not only depend on their own decisions, but also on the decisions of other mobiles, game theory is used as a theoretical framework to model user interactions in [START_REF] Aryafar | RAT Selection Games in HetNets[END_REF]- [START_REF] Kumar | User-Network Association in a WLAN-UMTS Hybrid Cell: Global & Individual Optimality[END_REF]. Players (i.e., the individual users) try to reach a mutually agreeable solution, or equivalently a set of strategies they unlikely want to change. However, the convergence time to the equilibrium assignment seems to be long [START_REF] Khawam | Individual vs. Global Radio Resource Management in a Hybrid Broadband Network[END_REF]. In [START_REF] Nguyen-Vuong | Multicriteria Optimization of Access Selection to Improve the Quality of Experience in Heterogeneous Wireless Access Networks[END_REF]- [START_REF] Zhang | Handover Decision Using Fuzzy MADM in Heterogeneous Networks[END_REF], multi-criteria decision-making methods, including Simple Additive Weighting (SAW), Multiplicative Exponent Weighting (MEW), Grey Relational Analysis (GRA) and Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) are presented. They capture the heterogeneity of decision parameters (e.g., QoS, cost, energy and security parameters). Users with widely varying requirements gather their QoS information (e.g., peak throughput when connected alone to a cell), calculate decision metrics, and select their RAT accordingly. In [START_REF] Chamodrakas | A Utility-Based Fuzzy TOPSIS Method for Energy Efficient Network Selection in Heterogeneous Wireless Networks[END_REF], [START_REF] Zhang | Handover Decision Using Fuzzy MADM in Heterogeneous Networks[END_REF], [START_REF] Falowo | RAT Selection for Multiple Calls in Heterogeneous Wireless Networks Using Modified TOPSIS Group Decision-Making Technique[END_REF], fuzzy logic is also used to deal with the imprecise information of some criteria and user preferences.

Since decisions are delegated to mobile users, network operations remain reduced. Furthermore, decisions can easily involve user needs and preferences, and various mobile-terminalrelated parameters. However, as mobiles do not cooperate, their decisions potentially lead to performance inefficiency. To overcome this limitation, we introduce in this paper a network-assisted approach. The network provides cost and QoS parameters to assist mobile users in their decisions. This decisional information reflects network load conditions and other potential operator concerns. For instance, by signaling appropriate network information, mobiles are globally pushed to some base stations, while others are switched to sleep mode to save energy. RAT selections are then expected to meet operator objectives, while mobiles individually maximize their utility.

The basic idea of our approach was first presented in [START_REF] Helou | A Hybrid Approach for Radio Access Technology Selection in Heterogeneous Wireless Networks[END_REF], where heuristic policies are introduced to dynamically tune network information as a function of the load conditions. In the present contribution, deriving network information is formulated as a Semi-Markov Decision Process. We first define network states, actions, state dynamics and rewards. An optimal policy (i.e., network information to signal in each state) is then derived through the Policy Iteration algorithm. As a matter of fact, transitions between network states depend not only on network actions, user arrival and departure rates, but also on user needs, preferences and decison-making algorithms. When all these parameters can not be easily obtained in constantly varying networks, an optimal policy is constructed through learning. Among the different existing reinforcement learning (RL) algorithms, we select the Q-learning method for its simplicity.

Furthermore, SMDP and Q-learning have been widely employed in RAT selection. In [START_REF] Zhu | Cross-Layer Handoff Design in MIMO-Enabled WLANs for Communication-Based Train Control (CBTC) Systems[END_REF]- [START_REF]SMDP Approach for JRRM Analysis in Heterogeneous Networks[END_REF], RAT selection is modeled as a semi-Markov decision process. Network elements gather information about individual users, particularly their QoS needs and radio conditions. They decide on user serving cells in a way to maximize long-term network reward, without aligning with user preferences. However, network complexity, processing, and signaling load are drastically increased. Moreover, in [START_REF] Tabrizi | Dynamic Handoff Decision in Heterogeneous Wireless Systems: Q-learning Approach[END_REF]- [START_REF]Learning-Based Cell Selection Method for Femtocell Networks[END_REF], mobiles learn selection decisions through trial-and-error interaction with their dynamic environment. Yet, because of the non-cooperative behavior of mobile users, their performance may be degraded. In this paper, SMDP and Q-learning are used in a network-assisted approach. They enable the network to derive information for the mobiles to make decisions.

The rest of this paper is organized as follows: The network model is presented in section III. Section IV explains our hybrid decision framework. The SMDP and the Policy Iteration algorithm are introduced in section V. Section VI describes the Q-learning algorithm. Performance results are analyzed in section VII. Section VIII concludes the paper.

III. NETWORK MODEL

A. Network Topology

Consider a heterogeneous cellular network composed of two OFDM(A)-based radio access technologies. Let x 1 and x 2 designate the two serving RATs within the network. Although our method adapts to different deployment scenarios, we focus on a realistic and cost effective one where the two RATs base stations are co-localized. The modulation and coding scheme, that can be assigned to a user connected to RAT x, differs depending on its radio conditions in the cell, more precisely on its signal-to-noise ratio denoted by SN R x . As the number of possible modulation and coding schemes is limited, we decompose the cell into N x Z zones with homogeneous radio characteristics [START_REF] Ibrahim | Network-Centric Joint Radio Resource Policy in Heterogeneous WiMAX-UMTS Networks for Streaming and Elastic traffic[END_REF]- [START_REF]SMDP Approach for JRRM Analysis in Heterogeneous Networks[END_REF]. Users in zone Z x k , k = 1, ..., N x Z , are assumed to have a signal-to-noise ratio between δ x k and δ x k-1 , and then to use mod x (k) with cod x (k) as modulation and coding scheme:

       none if SN R x (k) < δ x N x Z , (mod x N x Z , cod x N x Z ) if δ x N x Z ≤ SN R x (k) < δ x N x Z -1 , ... (mod x 1 , cod x 1 ) if δ x 1 ≤ SN R x (k) < δ x 0 = ∞. (1)
where

δ x N x Z
is the minimum signal-to-noise ratio, that allows transmission at the lowest throughput, given a target error probability.

1) Cell Decomposition: Because of fading effects, radio conditions are time-varying. User signal-to-noise ratio can take all possible values, leading to different modulation and coding schemes. However, as RAT selections are made for a sufficiently long period of time (e.g., session duration, user dwell time in the cell), users are distributed over logical zones depending on their average radio conditions, rather than on their instantaneous ones.

Another approach is found in [START_REF] Ibrahim | Network-Centric Joint Radio Resource Policy in Heterogeneous WiMAX-UMTS Networks for Streaming and Elastic traffic[END_REF], where an analytical radio model, that accounts for interference, path loss, and Rayleigh fading, is used. It has been demonstrated that users need to be situated at r k ∈ [R x k-1 , R x k [ from their base stations, so as to have a signal-to-noise ratio between δ x k and δ x k-1 , with at least a high probability P th . This means that the cell may be divided into concentric rings, as illustrated in Fig. 1, and mobiles in ring Z x k will use mod x (k) with cod x (k) as modulation and coding scheme, with at least a high probability P th . Further, to define the different rings, the distances R x k have been analytically derived, mainly as a function of δ x k , P th , and radio model parameters.

Ring N Z Ring k Ring 1 x Fig. 1. RAT x cell divided into N x Z concentric rings
In what follows, and for the sake of simplicity, users in a same zone are assumed to have the same average signal-tonoise ratios.

B. Network Resources

The radio resource is divided into time-frequency resource units (RUs). Users in zone Z k can transmit up to b x (k) bits per resource unit, when connected to RAT x:

b x (k) = N x s •N x f •log 2 [sz(mod x (k))]•R(cod x (k))•(1-BLER) (2
) where N x s and N x f respectively denote the number of OFDM symbols and subcarriers per RU, sz(mod x (k)) the constellation size of mod x (k), R(cod x (k)) the coding rate of cod x (k) and BLER the block error rate obtained as a function of the user signal-to-noise ratio.

In the time dimension, resources are organized into frames of length T x . When RAT x allocates N res resource units per frame to a user in zone Z k , its average throughput d is given by:

d = N res • b x (k) T x (3)

C. Traffic Model

Users belong to N C traffic classes. In our work, we focus on both streaming (c = 1) and elastic (c = 2) traffic classes. Class c arrivals, in zone Z k , follow a Poisson process of rate Λ(k, c). We assume that streaming sessions have an average long-term throughput of R av . Yet, to improve their content quality, they can benefit from throughputs up to R max . Their duration is considered to be exponentially distributed with a mean of 1/µ 1 .

Moreover, elastic sessions adapt to resource availability. Their needs are expressed as comfort throughput denoted by R c , and their size is assumed to be exponentially distributed with a mean of L bytes. However, in addition to their size, their service rate µ 2 also depends on their average throughputs.

IV. HYBRID DECISION FRAMEWORK

A. Network Information

Periodically or upon user request, network information is sent to all mobiles using the logical communication channel (i.e., radio enabler) proposed by the IEEE 1900.4 standard [START_REF]IEEE Standard for Architectural Building Blocks Enabling Network-Device Distributed Decision Making for Optimized Radio Resource Usage in Heterogeneous Wireless Access Networks[END_REF]. This logical channel allows information exchange between the Network Reconfiguration Manager (NRM), on the network side, and the Terminal Reconfiguration Manager (TRM), on the mobile-terminal side (Fig. 2). The purpose is to improve resource utilization and user experience in heterogeneous cellular networks. In our work, by appropriately tuning network information, user decisions are globally expected to meet operator objectives, avoiding undesirable network states. Mobiles make final decisions regarding selection of their most appropriate RAT. As a matter of fact, based on their needs and preferences, as well as on the signaled network information, mobile users choose their RAT in a way to selfishly maximize their utility.

For RAT x, the network broadcasts QoS parameters, denoted by d min (x) and d max (x), and the cost to pay per amount of traffic, denoted by cost(x) [START_REF] Helou | A Hybrid Approach for Radio Access Technology Selection in Heterogeneous Wireless Networks[END_REF]. Mobiles are actually guaranteed an average minimum throughput, namely d min (x), and have priority to be allocated up to an average maximum throughput, namely d max (x). As d min (x) and d max (x) are derived for a generic user with the most robust modulation and coding scheme, individual users need to deduce their own QoS parameters. For that, mobiles in zone Z k multiply the QoS parameters, signaled by the network, with their modulation and coding gain, denoted by g(k).

B. RAT Selection

Using the satisfaction-based multi-criteria decision-making method we have introduced in [START_REF] Helou | Satisfactionbased Radio Access Technology Selection in Heterogeneous Wireless Networks[END_REF], mobiles compute a utility function for each of the serving RATs, and select the one with the highest score. This utility depends on user radio conditions, needs and preferences (i.e., traffic class, throughput demand, QoS-maximizing or cost-minimizing preferences), as well as on the cost and QoS information sent by the network.

In our work, when cost(x) is maintained fixed, d min (x) and d max (x) are dynamically tuned trying to globally control user decisions. Let N x I be the number of possible (d min (x), d max (x)) couples, that may be signaled to incite mobile users to join RAT x. In the next section, selecting the (d min (x), d max (x)) couple to be broadcasted, for each RAT x, is formulated as a Semi-Markov Decision Process (SMDP). The goal is to dynamically optimize the long-term discounted network reward, while mobiles maximize their own utility.

V. SEMI-MARKOV DECISION PROCESS

At each user arrival or departure, signaled network information may have to vary. In this section, the SMDP is used to dynamically decide of the QoS parameters in a way that optimizes the long-term network reward. We first start by defining network states, actions, state dynamics and rewards. Next, using the Policy Iteration algorithm, we compute the optimal solution.

A. Network States

We define a state of RAT x to be the (

N Z × N C × N x I )- tuple n x (t) for {k = 1, ..., N Z , c = 1, ..., N C , i = 1, ..., N x I }: n x (t) = (n x (k, c, i, t)),
where n x (k, c, i, t) is a stochastic process representing the number of class c users in zone Z k , that have the i th (d min (x), d max (x)) couple, at time t. In the remaining, we omit t as we assume stationarity.

To protect ongoing sessions, an admission control policy is applied: new arrivals may join RAT x, with the i th (d min (x), d max (x)) couple, to the extent that RAT x available resources are enough to meet their d min , while not compromising the QoS guarantees of ongoing ones. Consequently, the set of admissible states in RAT x is:

N x a = n x ∈ N N Z ×N C ×N x I | N Z k=1 N C c=1 N x I i=1 n x (k, c, i) • N x min (i) ≤ N x total (4)
where N x min (i) is the number of RUs necessary to guarantee the d min of the i th QoS parameters couple, and N x total is the total number of RUs used for data transmission in RAT x.

Let the (

N Z × N C × N x1 I + N Z × N C × N x2 I )-tuple s = (n x1 , n x2
) be the state of the heterogeneous network, defined as the concatenation of RAT x 1 and RAT x 2 substates. The state space S of the network is then defined as:

S = {s = (n x1 , n x2 ) | n x1 ∈ N x1 a , n x1 ∈ N x2 a }

B. Network Actions

In each state, an action is taken by the network: QoS incentives to join serving RATs are derived. An action a is the quadruple defined by a = (d min (x), d max (x)), x ∈ {x 1 , x 2 }, where d min (x) and d max (x) represent the QoS parameters of RAT x, for the most robust modulation and coding scheme. Based on their needs (e.g., traffic class, throughput demand) and preferences, as well as on their modulation and coding scheme (i.e., geographical position), users act differently upon these actions. Refer to appendix A for more details.

Obviously, N x1 I • N x2 I actions are possible. However, given a state s = (n x1 , n x2 ), not all actions are feasible. We then denote by A the set of all possible actions, and by A(s) ⊂ A the subset of feasible actions in state s.

When both RATs provide no QoS incentives (i.e.,

d min (x 1 ) = d max (x 1 ) = d min (x 2 ) = d max (x 2 ) = 0)
, action a is blocking and new arrivals are rejected.

C. State Dynamics

As the network does not completely control individual decisions, transitions between network states do not only depend on network actions, user arrival and departure rates, but also on user needs and preferences. The decision-making on the mobile side, using a multi-criteria decision-making method, then has a probabilistic impact on the transition rates.

Let p x (k, c, a) represent the probability that class c users in zone Z k select RAT x, when action a is adopted. As action a may be blocking, p x1 (k, c, a) + p x2 (k, c, a), ∀k, c, is not necessarily equal to one: it can be either zero or one. Transition rates T (s, s , a) between states s = (n x1 , n x2 ) and s are then expressed as:

           Λ(k, c) p x1 (k, c, a) if s = (n x1 + e x1 (k, c, i), n x2 ) Λ(k, c) p x2 (k, c, a) if s = (n x1 , n x2 + e x2 (k, c, i)) n x1 (k, c, i) µ x1 c (s) if s = (n x1 -e x1 (k, c, i), n x2 ) n x2 (k, c, i) µ x2 c (s) if s = (n x1 , n x2 -e x2 (k, c, i)) 0 Otherwise (5) where e x (k, c, i) is defined as a (N Z × N C × N x I )
-tuple containing all zeros except for the (k, c, i) th element, that is equal to one, and new arrivals join RAT x with the i th QoS parameters couple proposed by action a. Hence, for example, when a class c user in zone Z k joins RAT x 1 , with the i th QoS parameters couple, the network moves to state s = (n x1 + e x1 (k, c, i), n x2 ).

The state dynamics can equivalently be characterized by the state transition probabilities p(s, s , a) of the embedded chain:

p(s, s , a) = T (s, s , a) • τ (s, a) (6)
where τ (s, a) is the expected sojourn time for each state-action pair, defined as follows:

x k c [Λ(k, c)p x (k, c, a) + i n x (k, c, i)µ x c (s)] -1 (7)

D. Network Reward

To formulate optimization objectives, let r(s, a) denote the permanence reward earned by the network in state s, when action a is adopted. Unlike the impulsive reward, received upon transitions, the permanence reward represents the benefit and penalty continuously received by the network whilst in state s (i.e., it is actually defined on a per unit time basis). In our work, we express r(s, a) as the sum of a network utility N (s, a) and a blocking term B(s, a):

r(s, a) = N (s, a) + B(s, a) (8)
The network utility is given by:

N (s, a) = x k c i n x (k, c, i)d x (k, c, i) (9)
where d x (k, c, i) represents the average throughput of class c users in zone Z k , that have joined RAT x with the i th (d min (x), d max (x)) couple. In fact, mobiles are first provided with their minimum guaranteed throughput given by d min •g(k). Then, fair time scheduling is used to provide them with up to their maximum throughput given by d max • g(k).

Remaining resources may afterwards be equitably shared (i.e., after receiving their maximum throughput, all mobiles have the same priority leading to fair time scheduling). Furthermore, the blocking term reflects the penalty of rejecting future arrivals. B(s, a) is thus proportional to the arrival rates in blocking states, and is expressed as follows:

B(s, a) = -b • k c Λ(k, c)(1 - x p x (k, c, a)) ( 10
)
where b is the cost per unit time inflicted on the network for blocking a new arrival.

E. Uniformization

In our work, we make use of the Policy Iteration algorithm to solve the SMDP problem (i.e., to determine the action the network takes in each state). A stage of uniformization is thus required. The continuous-time Markov chain is transformed to its discrete equivalent.

Time is first discretized into intervals of constant duration τ , that is smaller than the expected sojourn time in any state: 0 ≤ τ < τ (s, a), ∀s ∈ S.

Transition probabilities are then modified as follows: where p(s, s , a) represents the probability that the network moves from state s to s within τ , when action a is adopted. Moreover, the reward is also modified as follows: r(s, a) = r(s, a)τ , where r(s, a) is the reward earned for a time τ .

F. Policy Iteration Algorithm

A policy π is a mapping from S to A. π(s) represents the action to take in state s. Let H π (s) = s, s 1 , s 2 , ..., s n , ... be a trajectory of the Markov chain, when policy π is adopted. The long-term discounted reward dr(H π (s)) of state s is the discounted sum of the rewards earned on that trajectory (that starts from s), and is expressed as follows: r(s, π(s)) + ψr(s 1 , π(s 1 )) + ... + ψ n r(s n , π(s n )) + ... where ψ is the discounting factor (0 < ψ < 1). In our work, we set the value function of state s, denoted by V π (s), as the expected value of dr(H π (s)) over all possible trajectories.

Our goal is to find an optimal policy π opt , that maximizes the expected long-term discounted reward of each state:

V πopt (s) ≥ V π (s), ∀s, π
We therefore use the following Policy Iteration algorithm:

• Step 0 (Initialization): We choose an arbitrary stationary policy π. • Step 1 (Value Determination): Given the current policy π, we solve the following system of linear equations to calculate the discounted value function V π of all states:

V π (s) = r(s, π(s)) + ψ s ∈S p(s, s , π(s))V π (s )
• Step 2 (Policy Improvement): When any improvement is possible, we update the current policy π. For each s ∈ S, we find:

π(s) = arg max a∈A(s) r(s, a) + ψ s ∈S p(s, s , a)V π (s )
• Step 3 (Convergence test): If π = π, the algorithm is stopped with π opt = π. Otherwise, we go to step 1.

VI. REINFORCEMENT LEARNING

In the previous section, knowing r(s, a) and p(s, s , a), an optimal policy π opt is solved through the Policy Iteration algorithm. The transition probability function p(s, s , a) depends on user arrival and departure rates, needs, preferences, and decision-making algorithms. However, when p(s, s , a) may not be easily obtained, reinforcement learning (RL) turns out to be a good fit to derive network information. The network does not estimate user behavior, but rather learns what action to take by trial-and-error. Among the different existing RL algorithms, we select Q-learning [START_REF] Watkins | Technical Note: Q-Learning[END_REF] for its simplicity. Although originally used to solve Markov decision processes, Q-learning may be applied with slight modifications to semi-Markov decision processes [START_REF] Ryan | Hierarchical Reinforcement Learning: A Hybrid Approach[END_REF].

A. SMDP Q-learning Algorithm

The network interacts with its environment over a sequence of discrete time-steps (t, t + 1, t + 2, ...), trying to learn what QoS parameters to signal. These time-steps refer to time intervals of fixed duration τ . The quality function of stateaction pair (s, π(s)), denoted by Q π (s, π(s)), is defined as the expected long-term discounted reward of state s, using policy π. Our aim is to find an optimal policy π opt , that maximizes the quality function of each state s, also referred to as its Q-value:

π opt (s) = arg max a∈A(s) Q π (s, a), ∀s, π
Without knowledge of p(s, s , a), the network, also referred to as the agent, iteratively learns optimal Q-values. At discrete time-steps, when the network state has changed, the network action terminates. QoS parameters to be signaled may have to vary. Unlike in Markov decision processes, where all actions are assumed to take constant time to complete, actions in our work can span several time-steps. They are said to be temporally-abstract. At time-step t, when state-action pair (s, a) is visited (i.e., when the network in state s selects and performs action a), the network earns reward R, and ends in state s at t + k. The Q-value of state-action pair (s, a) is then updated as follows:

Q(s, a) ← Q(s, a) + ρ R + ψ k max a ∈A {Q(s , a )} -Q(s, a) (12
) where ρ is the learning rate (0 < ρ < 1), that determines to what extent the learned Q-value will override the old one. When ρ = 0, the network does not learn. When ρ = 1, the network considers only the most recent Q-value. R is the discounted accumulation of all single-step rewards r τ , received while executing action a for a time τ , and is given by:

R = k-1 i=0 ψ i r τ
Moreover, it has been proved that, while the number of visits of each state-action-pair is sufficiently large, and ρ is reduced to zero over time, Q(s, a) is guaranteed to converge to Q πopt (s, a) [START_REF] Watkins | Technical Note: Q-Learning[END_REF].

B. Exploration and Exploitation

At decision epochs, the network decides, randomly or based on previously learned Q-values, what QoS parameters to signal. To receive high reward, the network may prefer actions it has tried in the past and found effective. This is known as the exploitation mode. Yet, to discover effective ones, the network needs to try actions it has not selected before. It may then randomly select one of the possible actions, aiming to enhance its future decisions. This is known as the exploration mode. Since Q-learning is an online iterative learning algorithm, exploration and exploitation should be simultaneously performed. The agent must discover a variety of actions, and progressively favor effective ones. However, to estimate reliable Q-values, actions need to be sufficiently tested.

In our work, we adopt an -greedy exploration-exploitation policy. At decision epochs, the network in state s explores with probability (s), and exploits stored Q-values with probability 1-(s). To enhance long-term network performance, exploring is never stopped, but rather reduced over time. We define β(s, a) to be the number of visits of state-action pair (s, a) up to current time-step, and choose (s) to be as follows:

(s) = 1 ln( a∈A β(s, a) + 3) (13)
(s) then belongs to [0, 1], and has a logarithmic decay. Furthermore, for Q(s, a) to converge to optimal Q-values, we set ρ to be a state-action pair varying over time:

ρ(s, a) = 1 β(s, a) + 3
Algorithm 1 describes our SMDP Q-learning algorithm for deriving network information. We summarize below the main steps. Q-values are first set to zero. The network state is randomly initialized. Once in state s, depending on (s), exploration or exploitation is executed. In exploration mode, the network randomly selects and performs action a. However, in exploitation mode, it opts for the action with the maximum Q-value: a = max a Q(s, a). After, at each time-step, the network state is observed. While the network is in state s, action a is maintained, and the discounted accumulation of single-step rewards R is updated. Yet, if it is in state s (i.e., the network state has changed), action a is terminated, and Q(s, a) is updated according to equation 12. This is repeated until the end of the learning period. For illustration, we consider a heterogeneous cellular network composed of mobile WiMAX and LTE, respectively designated by W and L. For simplicity, users are of two types: those with good radio conditions (or cell-center users that belong to zone 1) and those with bad radio conditions (or cell-edge users that belong to zone 2). Their peak throughputs, when connected alone to mobile WiMAX and LTE cells, are depicted in Table I. Further, class c arrivals are assumed to be uniformly distributed over the two zones, and to follow a Poisson process of rate Λ c = Λ (i.e., Λ(k, c) = Λ/N Z , ∀k, c). Moreover, for streaming sessions, we suppose that R av = 1 Mb/s, R max = 1.5 Mb/s, and 1/µ 1 = 45 s. For elastic sessions, we consider that L = 5 Mbytes, and R C is fixed to either 1.25 or 0.75 Mb/s, depending on the QoS-maximizing or cost-minimizing preferences of mobile users. For network information, we assume that cost(W ) = 4, cost(L) = 6, N W I = N L I = 3, I W = {(0, 0), (0.5, 1), (1, 1.5)} Mb/s, and I L = {(0, 0), (0.75, 1.25), (1.5, 2)} Mb/s.

Initialize • Q-values: Q(s, a) ← 0,

RAT

The probabilities p x (k, c, a) are calculated according to the satisfaction-based multi-criteria decision-making method, we have introduced in [START_REF] Helou | Satisfactionbased Radio Access Technology Selection in Heterogeneous Wireless Networks[END_REF]. They mainly depend on user preferences, traffic classes and throughput demands. Note that half of the users are ready to pay for better performances.

For comparison purposes, we also investigate the staircase tuning policy [START_REF] Helou | A Hybrid Approach for Radio Access Technology Selection in Heterogeneous Wireless Networks[END_REF]. Load factors are defined as the ratios of the number of guaranteed allocated RUs to the total number of RUs. The highest QoS parameters are first signaled. Next, when a RAT load factor exceeds S 1 threshold, QoS parameters are reduced following a step function (cf. Fig. 3). However, if S 2 is reached, QoS incentives are no longer provided. QoS parameters to signal in RAT x, depending on the load factor φ x , are reported in table II.

Low-load

Load factor S 1 S 2

QoS parameters parameters Fig. 3. QoS parameters reduction using the staircase policy Before we discuss performance results, we remind in table III some notations, useful for the following.

A. Staircase Policy

Using the staircase policy, we study the impact of S 1 and S 2 thresholds on network performance. Figures 4 and5 QoS parameters respectively show the network throughput, defined as the sum of user throughputs, and the blocking probability, as a function of the cell arrival rate Λ, for different threshold values. For fixed S 1 , the higher S 2 the more mobiles are admitted. Yet, higher S 2 thresholds limit user throughputs to their guaranteed ones. Besides, for fixed S 2 , the lower S 1 the less mobiles benefit from the largest QoS guarantees, but much more are admitted with reduced QoS parameters. Therefore, the average number of simultaneous sessions increases. Obviously, the more mobiles are admitted for a fixed cell arrival rate (i.e., the lower S 1 or the higher S 2 ), the lower the blocking probability. Also, the network throughput augments. Typically, streaming sessions have limited throughput demands, and hence the more mobiles are admitted the larger the network throughput will potentially be.

φ x < S 1 S 1 ≤ φ x ≤ S 2 φ x >

B. Optimal Policy

The optimal policy, solved through the Policy Iteration algorithm, and the staircase policy are compared. Using the optimal policy, we study the impact of the blocking cost b, and the discount factor ψ on network performance.

1) Impact of the blocking cost: We start by inspecting the impact of the blocking cost b on network performance. So as to enlarge the number of states involved in the value function, the discount factor ψ is fixed at 0.99.

Figure 6 illustrates the average reward as a function of the cell arrival rate Λ, for different blocking costs. When b is zero, the reward function is reduced to the network utility representing the sum of user throughputs. Otherwise, it also includes a penalty term, that is proportional to the blocking cost b and to the cell arrival rate. At low arrival rate, no blocking occurs leading to similar rewards regardless of b. The reward function, reduced to the network throughput, then increases with the cell arrival rate. Yet, as the latter increases further, or equivalently, when the average number of simultaneous sessions augments, network resources are always nearly exhausted, and not enough are left to cope with future arrivals. Therefore, the blocking probability (i.e., the long-term fraction of time spent in blocking states) also increases. Moreover, and since the penalty term is proportional to the cell arrival rate, the reward function received by the network whilst in a blocking state is as reduced as the arrival rate is increased. For all these reasons, the average reward decreases more when the cell arrival rate increases, except for b equals zero. In fact, when b is null, the average reward stagnates at high arrival rate. It represents the longterm sum of user throughputs. Otherwise, the average reward obviously decreases with increasing blocking costs. We further note that the optimal policy always outperforms the staircase one. However, when S 1 and S 2 are respectively set to 0.3 and 0.95, the staircase policy provides higher network reward in comparison with the case when S 1 = 0.35 and S 2 = 0.85, denoted as Staircase policy (2). Besides, the impact of the penalty term on the reward function, and thereafter on the optimal policy, strongly depends on the blocking cost b. On the one hand, the higher b the more the network avoids blocking actions, even if at the expense of the network utility. On the other hand, the lower b, the more the network tries to maximize its throughput, even if leading to more blocking states. We, respectively, depict in figures 7 and 8 the network throughput and the percentage in number of blocking states, as a function of the cell arrival rate. The optimal policy is illustrated for different values of b. Particularly, when b is zero, the network throughput, but also the percentage of blocking states, are maximized. The blocking cost b may therefore be tuned to control optimization objectives. Further, when S 1 = 0.3 and S 2 = 0.95, the staircase policy achieves a higher throughput in comparison with when S 1 and S 2 are respectively set to 0.35 and 0.85. As a matter of fact, when these thresholds are carefully chosen, the staircase policy provides quite similar performances as the optimal one (b = 50). They both effectively avoid blocking actions and guide user decisions. In the remaining, we only consider the case where S 1 = 0.3 and S 2 = 0.95. It is worth noting that for a given b, when the cell arrival rate is different, the state dynamics and penalty terms are also different. This may lead to dissimilar optimal policies. Thus, and as shown in Fig. 8, the percentage in number of blocking states first increases with the cell arrival rate. Then, when the latter increases further, for b different from zero, this percentage decreases as the penalty term becomes relatively very significant. Moreover, the blocking probability P b depends not only on the number of blocking states, but mostly on the stationary distribution achieved by the different policies (i.e., on the long-term fraction of time spent in the different states). In the following, to efficiently analyze the impact of the blocking cost on P b , we separately consider streaming and elastic sessions.

The service time of elastic sessions depends both on their size assumed to be exponentially distributed with a mean of 5 Mbytes, and on their perceived throughputs. As shown before, the lower b, the higher the network throughput leading to lower average service times. When the optimal policy is adopted (i.e., the actions are fixed to the optimal ones), the SMDP may be reduced to a Markov chain, where departure rates increase with decreasing blocking costs. As a result, for a given cell arrival rate, the lower b, the lower the long-term number of simultaneous sessions. This also means that, although the lower b the higher the percentage of blocking states, the longterm fraction of time spent in these states is reduced as b is low. Accordingly, the lower b, the lower P b for elastic sessions as illustrated in Fig. 9.

Nevertheless, the service time of streaming sessions exclusively depends on their duration, considered to be exponentially distributed with a mean of 45 s. Thereby, maximizing the network throughput will not reduce their average service times. Consequently, as the number of blocking states increases with decreasing b, the blocking probability for streaming sessions also increases (cf. Fig. 10). The long-term fraction of time spent in blocking states will actually be higher. Here again, for both traffic classes, the performance of the staircase policy, with carefully chosen S 1 and S 2 thresholds, is comparable to the optimal solution (b = 50). 2) Impact of the discount factor: In this paragraph, we investigate the impact of the discount factor ψ on network performance. When the blocking cost b is set to zero, the network reward is reduced to the sum of user throughputs.

Figures 11 and12 respectively illustrate the network throughput and the blocking probability as a function of the cell arrival rate, for different ψ values. Recall that the higher ψ, the larger the number of states involved in the value function. Also, next states contribute more to the expected long-term network reward as ψ gets higher.

The discount factor ψ can thus be tuned to control the optimization scope. Typically, higher ψ values imply more long-run optimization, leading to higher throughput and lower blocking probability. Further, we note that the network throughput at low arrival rate and the blocking probability at high arrival rate are obviously quite similar, regardless of the discount factor.

Figures 13 and14 compare the optimal policy with the staircase one. On the one hand, we notice that, at low arrival rate (typically below 1), the staircase policy outperforms the optimal one with ψ = 0.3 and ψ = 0.8. This means that the intuitive and low-complexity staircase policy efficiently guides user decisions at low arrival rate. Yet, to maximize network performance, the number of states that are involved in the value function should be large enough. This can be seen with ψ = 0.99. On the other hand, when the cell arrival rate increases, taking into account next states becomes more relevant. In fact, when the network is expected to approach its saturation, deriving QoS parameters considering future arrivals enhances longterm network performance. Also, reducing QoS parameters in all serving RATs, following the staircase policy, proves to provide close performance to the optimal solution (cf. Fig. 13 and14).

C. Learning-based Policy

In what follows, the learning-based policy (ψ = 0.99), the optimal policy (b = 0, ψ = 0.99) and the staircase policy are compared. Using the Q-learning algorithm, the agent interacts with its environment over a sequence of T = 100000 and T = 250000 time-steps, of fixed duration τ = 0.5 s. Performance metrics are then averaged over 20 learning periods.

Figures 15 and16 respectively show the network throughput and the blocking probability, as a function of the cell arrival rate. The optimal solution, solved using the Policy Iteration algorithm, provides an upper bound on the network throughput. It also brings the lowest blocking probability, and consequently the best network performance. However, the optimal policy suffers from high computational complexity. For a fixed discount factor, the Policy Iteration algorithm is shown to run in at most

N 2 s (Na-1) 1-ψ • log( N 2 s 1-ψ ) iterations,
where N s is the number of states, N a the number of actions, and ψ the fixed discount factor [START_REF] Ye | The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate[END_REF]. Moreover, and as discussed before, the staircase policy provides very close performance to the optimal solution despite its low complexity. Yet, a practical challenge is to efficiently set S 1 and S 2 values. When our heuristic requires no knowledge on network parameters, its performance strongly depends on the choice of the tuning thresholds.

Furthermore, unlike the optimal and the heuristic solutions, the learning-based one needs no parameterization. Theoretically, after an infinite learning period, our Q-learning algorithm converges to the optimal solution. In our work, we stop learning after a realistic duration of T = 100000 and T = 250000 time-steps. Better performances are obviously observed when T = 250000, in comparison with when T = 100000. Yet, when learning periods are voluntary limited, both the optimal and the heuristic policies outperform the learning-based ones.

VIII. CONCLUSION

In this paper, we have addressed the radio access technology selection in heterogeneous cellular networks. We have proposed a network-assisted approach, aiming to jointly enhance network performance and user experience. As a matter of fact, the network provides information for the mobiles to make decisions regarding selection of their most appropriate RAT. Deriving network information was formulated as a semi-Markov decision process, and optimal policies were solved through the Policy Iteration algorithm. However, a heavy computational load was required to find optimal solutions. Further, as network parameters may not be easily obtained, we have introduced a RL-based algorithm to determine what to signal to mobiles. Although our learning-based algorithm requires no prior parameterization, it does not react fast to sudden parameter changes. Moreover, we have investigated the staircase policy, and proved its efficiency for implementation in practice. When tuning thresholds are pertinently chosen, our heuristic achieves close performance to the optimal solution.

APPENDIX USER DECISION-MAKING

We consider a mobile user, in zone Z k , that needs to join one of the serving RATs. For RAT x, the network broadcasts the three parameters d min (x), d max (x), and cost(x). From the user point of view, these parameters are the values of the decision criteria, used to evalute available RATs. As d min (x) and d max (x) are derived for the most robust modulation and coding scheme, the mobile has first to determine its perceived QoS parameters, as signaled by the network: d min (x) • g(k) and d max (x)•g(k). Second, using the satisfaction-based multicriteria decision-making method we have introduced in [START_REF] Helou | Satisfactionbased Radio Access Technology Selection in Heterogeneous Wireless Networks[END_REF], the mobile computes a utility function for each of the available RATs, and selects the one with the highest score.

The utility function of a class c user, for RAT x, is defined as follows: β + ( d (x).g(k)

Rav

) )

where d = {d min , d max }. R av represents session needs: an average throughput demand. α and β are two positive constants that determine the shape of the sigmoid function. Also, when elastic sessions (c = E) adapt to resource availability, requiring no QoS guarantees, d min (x) is completely ignored (i.e., w E dmax = 0). Moreover, their throughput normalizing function for d max has a concave shape. dE max (x) increases slowly as the throughput exceeds the comfort throughput demand R c of the user (i.e., the average throughput beyond which, user satisfaction exceeds 63% of maximum satisfaction). dE max (x) = 1 -exp(-

d max (x).g(k) R c ) (15)
However, the cost normalizing function is modeled as a Z-shaped function for both traffic classes. cost

where λ c represents the cost tolerance parameter, a positive constant that determines the shape of the Z-shaped function.

Depending on user preferences (e.g., QoS-maximizing or cost-minimizing preferences), and needs (i.e., traffic class), the cost tolerance parameter λ and the weights of the decision criteria are reported in table IV

Fig. 2 .

 2 Fig. 2. Hybrid IEEE 1900.4 network architecture

  s , a) = p(s, s , a) τ τ (s,a) for s = s p(s, s , a) = 1s =s p(s, s , a) Otherwise (11)

Fig. 4 .

 4 Fig. 4. Staircase policies: network throughput

Fig. 5 .

 5 Fig. 5. Staircase policies: blocking probability

Fig. 6 .

 6 Fig. 6. Impact of b on network reward

Fig. 7 .

 7 Fig. 7. Impact of b on network throughput

Fig. 8 .

 8 Fig. 8. Impact of b on the percentage of blocking states

Fig. 9 .

 9 Fig. 9. Impact of b on blocking probability for elastic sessions

Fig. 10 .

 10 Fig. 10. Impact of b on blocking probability for streaming sessions

Fig. 11 .Fig. 12 .

 1112 Fig. 11. Impact of ψ on network throughput

Fig. 13 .Fig. 14 .

 1314 Fig. 13. Optimal vs. staircase policies: network throughput

Fig. 15 .Fig. 16 .

 1516 Fig. 15. RL-based vs. optimal vs. staircase policies: network throughput

U

  c (x) = w c dmin • dc min (x) + w c dmax • dc max (x) + w c cost • cost c (x)where dc min (x), dc max (x), and cost c (x) are respectively the normalized values of d min (x), d max (x), and cost(x). w c dmin , w c dmax , and w c cost are the weights of the decision criteria, reflecting user preferences. The normalizing functions depend on user traffic class c, and throughput demands. As streaming sessions (c = S) are usually characterized by a minimum, an average and a maximum bandwidth requirement, their throughput normalizing function is modeled as an sigmoid function: d S (x) = 1 -exp( -α( d (x).g(k) Rav ) 2

c

  (x) then decreases rapidly with the cost.cost c (x) = exp(-cost(x) 2 λ c ), c ∈ {S, E}

TABLE I PEAK

 I THROUGHPUTS IN MOBILE WIMAX AND LTE

  .

	Preferences Traffic class λ	w dmin w dmax w cost
	QoS-max	Streaming	60 14/30 7/30	0.3
	QoS-max	Elastic	60	0	0.7	0.3
	Cost-min	Streaming	25	0.2	0.1	0.7
	Cost-min	Elastic	25	0	0.3	0.7

Currently, he is at the head of a research group on Advanced Networking. He is member of IRISA (a CNRS-University joint research laboratory located at Rennes in France). He has co-authored 150+ papers published in international journals and conferences.

His research interests include next generation Internet, green networking, all-optical networks, wireless networks, dependable networking, high speed networks, traffic engineering, multicast routing, network QoS management, network security and multimedia distributed applications.


Conclusion and Future Work

In its actual state, Xefee offers a practical GUI front-end for the TEI/Epidoc encoding of ancient Egyptian inscriptions, facilitating the marking up of texts and prosopographical information. The next step is the full encoding of a sub-collection of the corpus (Late Period texts) by a small group of scholars and PhD students with full Egyptological proficiencies. The TEI/Epidoc files created using Xefee will then be poured into a web application (built upon a native XML database). Being a pilot project for digital epigraphy, the Karnak Cachette text corpus may offer a discussion basis for a better standardization of practice in the Egyptological field. The ODD customization may also be discussed and enhanced within the community.

As a prototype of what can be done to articulate a relational database to a structured text encoding in the perimeter of a given project, Xefee may be also adapted to other epigraphical projects from other fields. It will be distributed as an open-source project in the near future.

IFAO-SCA

The Karnak Cachette project

Current goals

The project aims at developing the tools to encode, search and publish electronically the hieroglyphic texts inscribed on the objects from the Cachette, enabling different types of full-text searches and queries (especially those dealing with titles and prosopographical data).

The version 3 of the database will comprise an electronic epigraphic edition of the corpus of texts with detailed prosopographical data.

The current efforts are focussed on :

• the development and finalization of a user-friendly tool for the encoding, analysis and online publication of the hieroglyphic texts inscribed on the objects from the Karnak Cachette;

• the implementation of TEI/Epidoc standards in ancient Egyptian Epigraphy to serve as a basis for building bridges between text-edition projects within Egyptology.

The texts of the Karnak Cachette often occur in compact sequences of personal names and titles, giving parts of genealogy information (e.g. born to the mistress of the house, sistrum player of Amun-Ra, Di-se-Amunet). The XML marking up can then be quite dense. A preview pane renders the encoded strings with different border styles or highlighting patterns.

At the end of the editing process, the user can generate the XML/TEI file via the «create xml» button. Xefee picks up in the MySQL database all the required pieces of information and places them between the appropriate XML tags. This creates all the sections of a TEI/Epidoc file, from the headers with the publication and bibliographic metadata to the div elements dealing with the encoded transliterations, translations, apparatus criticus and epigraphical commentary.

Version 2 of the scientific database, including all the objects from the Karnak Cachette.

http://www.ifao.egnet.net/bases/cachette/

The ancient Egyptian to present genealogical filiations also required the building of peculiar tools to handle this very important aspect of the text content. A tab of the GUI is dedicated to the creation of the mentioned person's identities.

Another tab provides a tabular window which offers a practical way to manage the familial relationships and generate the <listRelation/> element of the <particDesc/> set of elements in the <teiHeader/>.

ENS DE LYON

pane XML/TEI export tab

The import module directly converts any hieroglyphic transliteration using Egyptological transcription standards to a basic TEI/Epidoc markup.

The text edition tab offers buttons, combo-boxes and other controls in order to facilitate the marking up of the texts with tags relating to epigraphy (<lb/>, <cb/>, <gap/>, <sic/>, <supplied/> elements), onomastics (<persName/> element and <rs/> elements with specific @type such as "deity", "dei-tyEpithet", "toponym") and prosopography (<rs/> elements with specific @type such as "person", "title", "filiationMark").

The general information tab displays the descriptive data recorded in versions 1 and 2 of the database.

general information tab

  Between 1903 and 1907, the French archaeologist discovered thousands of hidden stone statues, stelae and other objects that were buried in a large pit inside the temple of Amum at Karnak (known as the "Cachette" of Karnak). This ensemble constitutes an extraordinary source of information on the Egyptian clergy and the evolution of local cults. The objects as well as the related documentation now being widely dispersed, and in the absence of a comprehensive inventory of the find, it was decided to create an online inventory and a tool to search this rich corpus. The first version of the online database was launched in 2006. It provided a general description of each object, a label, date of discovery, its various inventory numbers, and a bibliography. Version 2 went online in 2012. It gives access to the complete photographic documentation (more than 8 000 photographs). The database is regularly updated. See: http://www.ifao.egnet.net/bases/cachette/