Catherine Dubois

Michalis Famelis

Martin Gogolla

Leonel Nobrega

Ileana Ober

Martina Seidl

Markus Völter

Research Questions for Validation and Verification in the Context of Model-Based Engineering

In model-based engineering (MBE), the abstraction power of models is used to deal with the ever increasing complexity of modern software systems. As models play a central role in MBE-based development processes, for the adoption of MBE in practical projects it becomes indispensable to introduce rigorous methods for ensuring the correctness of the models. Consequently, much effort has been spent on developing and applying validation and verification (V&V) techniques for models. However, there are still many open challenges. In this paper, we shortly review the status quo of V&V techniques in MBE and derive a catalogue of open questions whose answers would contribute to successfully putting MBE into practice.

Introduction

This paper is based on the discussions of a working group (whose members are mainly the authors of this paper) of the 2013 Dagstuhl seminar number 13182 on Meta-Modeling Model-Based Engineering Tools. The working group addressed a panel of important issues with validation and verification (V&V) of models and model transformations whose correctness is crucial for the successful realization of model-based engineering (MBE) projects.

Overall, models help to clarify and plan the development of software. Furthermore, they allow the use of methods to ensure quality and discover errors in conceptual designs. However, with the extensive use of models during the software development process, there is the danger of introducing defects into the models. For detecting or avoiding such defects, techniques of validation and verification (V&V) for models help.

Besides models, model transformations (MTs) are at the heart of model-based engineering. Different kinds of MTs underlie the engineering activities and their associated tools. They can be used for example to refine models, to generate code, etc. This variety of purposes of MTs emphasizes the need for effective and dedicated V&V techniques for animating, testing, and proving them.

In a model-based development process, V&V techniques help to better understand models and to assess model properties which are stated implicitly in the model. V&V serves to inspect models and to explore modeling alternatives. Model validation answers the question 'Are we building the right product?' whereas model verification answers 'Are we building the product right?', similar as V&V does for code. Validation is mainly an activity done by the developer demonstrating model properties to the client, whereas in verification the developer uncovers properties relevant within the development process. Verification is closely related to testing and covers automatic and semi-automatic (static) analysis techniques like theorem proving and model-checking.

In this paper, we shortly review the status quo of V&V techniques in MBE and derive research questions whose answers will push the whole field forward. The methodology behind this paper is as follows. First, we started to list objectives, methods, tools, use cases and then highlighted difficulties, bottlenecks and pitfalls. On this basis, we derived some key research questions. This paper sums up these discussions and lists the different research questions. 8The main conclusion of our analysis of the actual situation is that specific V&V methods for models and MTs are required. Although numerous tools exist to verify and validate hardware and software, they do not apply straightforwardly to models and MTs. In [START_REF] Clarke | Model checking: algorithmic verification and debugging[END_REF], E. M. Clarke, E. A. Emerson and J. Sifakis mentioned abstraction techniques as one of the promising paths for the future advances in the field of verification. The use of V&V techniques in the context of MBE follows the direction of abstraction. However V&V for models is concerned by a more complete abstraction mechanism that covers the entire system, whereas in [START_REF] Clarke | Model checking: algorithmic verification and debugging[END_REF], abstraction is considered mostly at mathematical level and targets formal semantics.

The rest of the paper is organized as follows: In Section 2, we reflect on the situation and describe some challenges. Subsequently, the research questions which emerged are listed in Section 3. We conclude in Section 4.

Status and Challenges

In this section we describe the main observations regarding the state of theory and practice that informed the discussions of our working group and list proposed solutions found in the literature. The observations are organized thematically, based on the main areas in which V&V and MBE intersect.

Gap Existing between Models and V&V Formalisms

In the context of model-based development, V&V faces new challenges. The origin of most of them stays in the gap existing between the (mostly high-level) specification mechanisms, used at design time both for specifying the model and the properties that are subject to V&V, and the underlying V&V engines that use low-level formalisms.

The gap between the two specification mechanisms can be (at least partially) filled by using model transformations and traceability mechanisms [START_REF] Galvão | Survey of traceability approaches in modeldriven engineering[END_REF], which are definitely needed in this context. Yet it is only part of the answer as behavioral semantics often leads to non-bijective correspondences between design time and runtime artifacts.

The V&V frameworks, which are typically using back-end tools using specific formalisms need to be complemented with mechanisms allowing the user to interact with the back-end tools through their own modeling languages. They do offer the right environment to reason about the system under modeling. In this context we can mention existing initiatives that go on this direction. In [START_REF] Bergmann | Change-driven model transformations -change (in) the rule to rule the change[END_REF] a high-level change-driven transformation language is proposed in order to capture changes, even those that concern low level transformations (as it may be in the case of some feedback (e.g. counter-examples) produced by V&V tools. Supporting the user during the error diagnosis phases can be done e.g. by allowing customizable simulation trace visualization [START_REF] El Arbi Aboussoror | Seeing Errors: Model Driven Simulation Trace Visualization[END_REF].

In the same spirit of hiding the technicalities related to the V&V engine, we can mention here the issue of (semi-)automatically managing the V&V machine configuration. Although not necessarily a research challenge, this is a typical functionality required in order to improve the accessibility to V&V tools.

Need to Refine Existing Methodologies

V&V tools have the potential of helping the user during model development, by allowing early V&V, similar to debugging facilities offered by programming development environments. Most of the generic methodologies identify some possible points where V&V could be used. In a realistic setting, the model-based development methodology should be refined in order to better identify which V&V activities are meaningful at the various phases of design, in order to take full advantage of the existing V&V engines. Such a methodology would most likely vary depending on the nature of the project and on the application domain, but one can expect that methodology definitions can be capitalized within the same business domain.

Importance of Snapshots

In the context of V&V, it is important to be able to clearly and completely describe a dynamic model configuration (often called model snapshot, or global state of the system) -in terms of existing objects, values of their respective attributes, existing links, active states in the state machine (if any), content of the input queue, etc. Such a snapshot could correspond to the state of the dynamic model before an error or otherwise identified as meaningful. A particular case of model snapshot is the one specifying the model instantiation, arising in the context of describing the initial state of a model execution. Each commercial tool that offers model simulation functionalities uses some (more or less documented) mechanism for describing model instantiation, however this snapshot description does not cover arbitrary snapshots.

There are some approaches that tackle the idea of model snapshot, such as for instance, the USE tool [START_REF] Gogolla | USE: A UML-Based Specification Environment for Validating UML and OCL[END_REF] which allows the user to generate/verify UML model snapshots. Yet, no modelling tool uses such elaborate techniques.

Properties

V&V focuses on verifying some properties with different objectives. Properties to be verified differ according to the nature of models (e.g. static or dynamic) and to the stage in the development process (e.g. specification or code generation time). Furthermore there are also limitations and synergies depending on the applied V&V techniques (static analysis, testing, model checking, runtime verification, formal proof). However there is no one-to-one association between properties and techniques, the latter being for the most part complementary.

More generally, we can distinguish structural properties (composition of models, consistency, redundancy), behavioral properties (ensure liveness of a model or safety properties) and also quantitative properties (such as Worst Case Execution Time (WCET) or schedulability). Properties are related with models but also to model transformations. Here the classification is different, it is discussed in more detail in the next subsection. We can also distinguish between static and dynamic properties and in both categories refine into language inherent, model specific, generic or user-defined properties.

We can find in the literature many approaches and tools to verify models. However it is quite confusing and it is difficult to draw a classification allowing the answer to the following question: What kind of property to verify on which model at what stage with what kind of technique? Some partial answers exist, e.g. using feature models [START_REF] Gabmeyer | A Classification of Model Checking-Based Verification Approaches for Software Models[END_REF] or ontologies [START_REF] Kezadri | First steps toward a verification and validation ontology[END_REF].

Model Transformations

Model transformations (MTs) are an integral part of model-based software engineering. MTs are used for a broad variety of purposes, ranging from applications as diverse as maintaining inter-model consistency to defining the translational semantics of a domain-specific language. This ubiquity of model transformations emphasizes the need for effective V&V techniques, that focus specifically on MTs. This is especially true in contexts of use where MTs are critical, such as code generation. At the same time, V&V for MTs differs from traditional program verification, since MTs are defined at a higher level of abstraction than programs, thus creating opportunities for more effective application of formal techniques. These factors have generated considerable interest in the research community, with special-interest events such as the VOLT workshop ("Verification Of ModeL Transformations") being organized since 2012.

An important challenge in studying the verification of MTs is to understand how verifying MTs is different from traditional program verification. There has been some work mapping the challenges that are specific to MTs; for example, [START_REF] Benoit Baudry | Model transformation testing challenges[END_REF][START_REF] Benoit Baudry | Barriers to systematic model transformation testing[END_REF] discuss the challenges of testing MTs, whereas [START_REF] Stevens | Generative and transformational techniques in software engineering ii[END_REF] focuses specifically on bidirectional transformations.

In the same vein, it is necessary to understand how to best reuse existing verification tools, techniques and methods. For example, in [START_REF] Amrani | A Tridimensional Approach for Studying the Formal Verification of Model Transformations[END_REF], the autors propose a tri-dimensional approach that takes into account (a) the kind of transformation involved, (b) the properties of interest, and (c) the available verification techniques. The purpose is to identify what verification method is most appropriate based on the transformation and desired properties. Similarly, [START_REF] Gabmeyer | A Classification of Model Checking-Based Verification Approaches for Software Models[END_REF] classifies approaches for verifying transformations based on five criteria: (a) verification goal (e.g. consistency, correctness), (b) representation of the domain, (c) representation used for the verification task, (d) specification language used, and (e) verification technique (theorem proving, static analysis, model checking).

In general, the correctness of MTs is of paramount importance and is generally the ultimate goal of verification of MTs. Correctness is tightly related with specification. The Tracts methodology [START_REF] Vallecillo | Formal specification and testing of model transformations[END_REF] proposes a generalization of model transformation contract, based on the idea of duck typing MTs with OCL constraints, while also supporting test-case generation. Another approach is to reuse transformation primitives in order to build correct-by-construction transformations, typically with a trade-off in expressive power, such as the case of DSLTrans [START_REF] Barroca | DSLTrans: A Turing Incomplete Transformation Language[END_REF].

Finally, the identification of properties that are meaningful when verifying MTs is also important. Confluence and termination have been studied extensively for transformations based on graph rewriting [START_REF] Ehrig | Fundamentals of algebraic graph transformation[END_REF][START_REF] Jochen | Definition and validation of model transformations[END_REF]. In [START_REF] Amrani | A Tridimensional Approach for Studying the Formal Verification of Model Transformations[END_REF], a more thorough categorization of properties is proposed, marking the distinction between properties related to transformations themselves (e.g. determinism) and properties related to the result of applying the transformation (e.g. conformance of the output). For each of these major categories, several minor sub-categories are identified.

Informal vs. Formal vs. Incomplete Modeling

Starting from informal use case sketches, which can be connected to formal model elements by trace links, there is need during V&V to concentrate on particular model parts and to switch on or off particular model inherent elements (in class diagrams, e.g., multiplicities, or aggregation and composition restrictions). Furthermore we may desire to explicitly configure constraints by negating, deactivating or activating them (in class diagrams, e.g., class invariants and operation pre-and postconditions; in state charts, e.g., state invariants and transition preand postconditions). Such configuration options must be offered with different types of granularity: (a) all model elements may be relaxed, (b) only a manual model element selection can be considered for relaxation, or (c) a semi-automatic element selection for relaxation may be offered (such a semi-automatic selection might depend on a user-determined, editable criteria catalogue). In the ultimate vision one might consider sliders on the user interface of the modeling tool which allows the developer to gradually go from a strict, formal model through various intermediate levels to a totally relaxed and informal model. However, if formal test cases and test scenarios are desired, then a minimal frame for test case construction must be preserved. Such a minimal frame could consist, e.g., for class diagrams of central classes and associations and for state charts of central states and transitions, with all model elements in the minimal version without any implicit or explicit constraints. Thus, there will be a tradeoff between switching off or ignoring certain model elements (like constraints or classes) and the degree of formality: if more model elements are switched off, the model will become more informal and will accept more scenarios; however, this procedure only works to a certain degree, because one can only formulate scenarios if at least a minimum selection of formal model elements is present; for a completely informal model no formal scenario can be formulated. Thus, ignoring certain model elements or constraints and the degree of formality are closely linked.

In order to handle incomplete and partial models wrt V&V, these model configuration options must be recorded along with the various V&V test scenarios, test cases and their results with respect to the configured model. Test cases and test scenarios must be invoked repeatedly with different configuration options and test results must be recorded in a systematic way. It must be possible to query test results in order to retrieve the proper configuration settings. The mechanisms for playing around with model relaxation can also be employed to allow for model alternatives. Model relaxations and model alternatives will span up a graph of model versions. These model versions must be connected to a graph of proper model test cases and model scenarios.

Comparison and Benchmarking

In the V&V research area, not only theoretical results are important, but also the tools which implement novel approaches in order to benefit from these results. Expressive benchmarks are necessary to evaluate the maturity of the tools as well as compare the power of novel approaches to established techniques. At dedicated workshops like the Comparison and Versioning of Software Models [START_REF] Oliver | Comparison and versioning of software models[END_REF] the benchmarking issue has been a specially discussed topic which is one approach to obtain commonly accepted benchmarks. Often community-organized competitions and evaluations are a valuable source for the benchmarks which serve as basis for evaluations in scientific publications illustrating the benefits of their contributions. Examples of such events are the SAT solving competition [START_REF] Järvisalo | The International SAT Solver Competitions[END_REF] or the Transformation Tool Contest (TTC) [START_REF] Van Grop Christian | Transformation tool contest[END_REF].

For the community the advantages of a centrally organized competition are manifold. First of all, evaluations are performed in an environment equal to all participants, thus allowing a fair comparison of the different tools. Second, the benchmarks are not selected by the tool developers, but by some impartial experts and covers the whole spectrum of interesting test cases. Third, a clear documentation of the outcome is provided such that the experiments performed in the context of a competition are repeatable. By this means the state-of-the-art of a research field becomes publicly available, it becomes clear where progress has been made and where more work has to be done. Ideally, new research questions are derived from the results which might then be handed over to the community in order to get solutions. These research questions may be documented in terms of benchmarks which cannot be handled by current tools. Often, such benchmarks are provided from industry and allow the researchers to show that a new approach improved the state-of-the-art.

To the best of our knowledge, recently there are no community-organized evaluations and competitions for V&V approaches in the field of MBE (TTC goes in that direction), although such events would be extremely beneficial with respect to the same arguments discussed above. Their absence is somehow surprising as the research community is rather large playing a major role in all leading modeling conferences. However, there are several reasons which might explain why no V&V competitions for MBE-approaches are organized at the moment. In the following, we elaborate on three urgent problems, which have to be overcome for structured V&V research.

(i) No common standards. Many approaches use their own metamodel in order to focus on the language element relevant for their purposes as for example UML is too large to be completely implemented.

(ii) No community platform. In order to collect and document interesting benchmarks which are required for organizing a successful competition, the community needs a forum to gather relevant data as it is for example done with the TPTP repository.

(iii) Metrics for improvements. In automatic theorem proving the improvements are mostly measured by runtime reduction or by compactness of proofs. For V&V approaches it is not so easy to measure progress in tools: the size of encodings or the execution time could be compared as well as the size of the error traces. However, MBE tools are also confronted with other requirements like usability and this is much harder to evaluate.

Domain-Specific Languages

Most verification tools have quite specific, sometimes archaic and hard to use input languages that are optimized for the semantic paradigm used by the tool. These languages are often alien to standard developers and hence, verification tools are often not used. On the other hand, developers could benefit from easyto-use verification techniques; even in non safety-critical domains, verification can be an additional means of quality assurance, even when it is not required by industry standards. Development approaches based on domain-specific languages (DSLs) are becoming more and more mainstream, through code generation this approach leads to improved productivity. Models expressed with DSLs also have the potential of simplifying analysis and verification, because of the higher degree of domain semantics they express. There seems to be a potential to exploit the two approaches synergistically: from the high-level models, we can automate the generation of the input to the verification tools. transformation contract? How do we infer a transformation contract from a model transformation? Informal vs. Formal vs. Incomplete Modeling: How do we leverage informal assumptions found in sketches for exploratory V&V? Are informal sketches close enough to V&V at all? What are appropriate relaxation mechanisms for different degrees of formality? How do we handle incomplete or partial models wrt V&V? How do we deactivate and activate model units? How do we handle the exploration of model properties and alternatives? Comparison and Benchmarking: How do we compare existing V&V tools employed for modeling wrt functionality, coverage, scalability, expressiveness, executing system (i.e., for models at runtime)? Which criteria are appropriate for comparison? Can the broad and diverse spectrum of V&V machines (like B, Coq, HOL/Isabelle, SAT, SMT, CSP solvers, Relational logic and enumerative techniques) be globally compared in a fair way at all? Domain-Specific Languages: How can DSLs be defined so that they are close to the domain concepts on the one hand, but still allow the generation of meaningful input files for verification tools? How do we express the properties to be verified at the domain level in a user-friendly way? Can the property specifications be integrated with the same DSL and/or model used for describing the to-be-verified system without creating self-fulfilling prophecies? How can we lift the result of a verification (e.g. an example program execution that demonstrates the failure) back to the domain level and express it in terms of the DSL-level input? Can incremental language extensions help with making programs expressed in general-purpose languages more checkable? For example, the semantics of a specific extension construct may enable the generation of very rich inputs to the verification tool, which otherwise may have to be specified manually (program annotations or properties)?

Conclusion

On this paper we present some observations and list the research questions that emerged from them. This list of research questions spans a wide area of themes where MBE and V&V intersect: specification and feedback and its impact on stakeholder collaboration, development process, design-time vs runtime, properties, model transformations, informal vs formal vs incomplete modeling, comparison and benchmarking, and domain-specific languages.

Our hope is that the set of observations and questions presented here will spark further discussions and thus aid the community focus research on those areas where the synergy of MBE and V&V can yield the greatest benefits.

We are aware that for some of them proposals already exist. Because of lack of space, we are not able to reference them all, and so we cannot reach exhaustiveness.

In this section we list the research questions that emerged from the discussions of our working group. The purpose of the list is to document the important issues that, we believe, research in the intersection of MBE and V&V must address.

Gap Existing between


Dat Sy

Le

Michel Gadonna

Monique Thual
email: monique.thual@univ-rennes1.fr

Lionel Quetel

Jean-Francois Riboulet

Vincent Metzger

Douglas Parker

Alain Philippe

Sebastien Claudot

Reliable Expanded Beam Connector Compliant with Single-mode Fiber Transmission at 10 Gbit/s

Keywords:

A new microlens design brings together benefits of physical contact and expanded beam technologies resulting in a reliable single-mode fiber connection requiring low maintenance for 10 Gbit/s networks as the Fiber-To-The-Home.

OCIS codes: (060.

Introduction

Fiber-To-The-Home (FTTH) and Fiber-To-The-Antenna (FTTA) deployment is becoming a reality with the recent flow-rate increased demands by full High Definition Television (HDTV), the fourth generation of mobile phone (4G) and Web Office. Whether one or several network topologies exist, all converge to have at least one connection at the server location side (OLT -Optical Line Termination) and/or one connection at the end-user location side (ONU -Optical Network Unit). Network designers are more likely to use single-mode fiber (SMF) for complying with higher data rates of about 10 Gbit/s and powerful laser sources (as the $/W ratio is continually decreasing) for covering a larger number of end-users with only one laser source associated with several passive couplers.

But typical SMF connectors have performance dramatically degraded by contaminants and laser power [START_REF] Kokkinos | SC/APC Fiber Optic Connectors Connected and Disconnected under High Optical Power[END_REF]. So what will be the time and money allocated by the service provider for the maintenance of such connectors?

This article proposes to use a microlens design minimizing the number of interfaces to combine the benefits of butt-joint and expanded beam lens technology all together into a mechanical footprint compliant with telecom standards. Modeling, manufacturing and testing at the wavelength of 1550 nm are presented here and lead to a new SMF connector tolerant to contamination, with a high laser damage threshold and reliable for 10 Gbit/s optical transmission data rate.

Principle and theoretical concepts of the proposed solution

The principle of the proposed solution consists of introducing a microlens at a single-mode fiber (SMF) end to expand its mode field diameter [START_REF] Thual | Contribution to research on Micro-Lensed Fibers for Modes Coupling[END_REF]. For that purpose a graded index fiber (GIF) section is spliced at the SMF end (see Fig. 1a). Thanks to the parabolic refractive index transverse profile, the propagation of the Gaussian beam is periodic in GIF. The index profile is considered to be a perfect parabolic curve conforming to the relationship: n(r) 2 =n0 2 (1-2r 2 /a 2 ), n0 is the central refractive index,  is the relative index difference between n0 and nc (the refractive index of the GIF cladding) defined as = (n0 2 -nc 2 )/(2n0 2 ), r the radial position in relation to the optical axis and a the core radius of the GIF. The numerical aperture (NA) is (n0 2

-nc 2 ) ½ = nc (2) ½ .
Using the GIF index profile and the core diameter we observe the propagation of the Gaussian beam in the microlens. This characterizes the Gaussian beam diameter (2), the Gaussian beam waist (20), where the phase front is plane, and the working distance zw, which is the distance between the beam waist location and the GIF end as shown in Fig. 1a. First we perform an analytical calculation based on the Kogelnik method [START_REF] Kogelnik | Coupling and conversion coefficients for optical modes[END_REF] and then a second kind of simulation based on BPM (beam propagation method [START_REF] Feit | Light propagation in graded-index optical fibers[END_REF]). This allows us to take into account the beam truncation by the GIF cladding during the beam propagation in this GIF segment.

The beam waist and working distance depend on the GIF segment length as can be seen in Fig. 1b. The beam diameter in the GIF segment initially increases to its maximum 2max at LGIopt before converging to its input beam diameter at 2LGIopt. The value of LGIopt depends on the GI refractive index profile and its core diameter. Defining the GIF parameter as g = (2) 1/2 /a, the optimal GIF length is given by LGIopt=/(2g) [START_REF] Thual | Contribution to research on Micro-Lensed Fibers for Modes Coupling[END_REF]. The GIF fiber is cleaved at the optimal distance LGIopt from the GIF/SMF splice. In this configuration, as the phase front is plane at the fiber end, the working distance, zw, is zero and the beam waist (20) is equal to the maximum beam diameter (2max). Since the fiber diameter remains 125 µm over the length of the microlens, it is suitable to be inserted in a standard connector ferule.

The computation of beam propagation inside the GIF section is also performed by a BPM analysis by solving the scalar Helmholtz equation ( 2 +k 2 )U(x,y,z)=0, where k=2πn(r)/λ is the spatially dependent propagation constant at wavelength λ, U(x,y,z) = A(x,y,z)exp(ikcz) is the complex scalar wave amplitude with A(x,y,z) the slowly varying beam amplitude and kc=2πnc/λ the propagation constant in cladding. In the simulation, the input beam amplitude profile is Gaussian. The field is sampled on an N×N grid along x and y axes. The core index of GI sections is slightly varied as a function of radius r by the grid. Assuming the weakly guiding conditions, the field propagation along z-axis is simulated by a split-step Fourier BPM with a step of dz [START_REF] Van Roey | Beam-propagation method: analysis and assessment[END_REF]. Fig. 1c shows the coupling efficiency of two optical fibers with a beam waist of 55 µm with respect to lateral offset misalignment for different cases of axial (0 and 200 µm) and tilt misalignment (from 0° to 0.5°). Because of this large beam waist, no increased loss is observed for a gap between fiber ends from 0 up to 200 µm (dash or blue curve) compared to the ideal coupling (solid or red curve). Since the fibers ends will be put in contact in connectors, the gap will be less than one µm, so, no increased loss from axial misalignment will be observed. In the same way, the offset has little impact on signal losses. A 2 µm offset leads to less than 0.1 dB excess loss. However, the coupling losses increase rapidly with an increasingly misaligned angular offset. For 55 µm beam waist, a 0.5 degree tilt misalignment leads to 2 dB excess loss (curve with triangle or cyan marks). The larger the fiber beam waist output, the more tolerant to axial and lateral misalignment are the coupling and the more critical is the angular positioning tolerances. A tradeoff can be found between the gap and lateral offset tolerances on one hand and the tilt tolerances on the other hand.

Results and characterizations

To produce the large beam waist connection, each ferule connector contains a GIF section with a length of LGI spliced to a SMF, so the total length of two GIF sections is 2×LGI. First we measure the insertion loss with a GIF length of 2×LGI spliced in between two SMFs. The measurement shows a minimum loss of about 0.4 dB around the calculated LGIopt (the filled round or green curve, Fig. 2a). It gives idea projection of the expected insertion loss when the two connectors are mated and correctly coupled.

Then, we fabricate SMF-GIF microlens fibers (SMF-GIF) with GIF length, LGI, varying around LGIopt±30 µm in order to measure the beam waist by the far-field method. The measurements show the change of beam waist with the length of GIF section as can be seen in Fig. 2a. We measure a maximum beam waist of about 55 µm for a given GIF length equal to the calculated LGIopt. The maximum beam waist corresponds to the minimum insertion loss (0.4dB).

So by measuring the insertion losses and the beam waist, we confirm the optimal length of GIF section, LGIopt, as the theoretical calculation. Therefore, the SMF-GIF with the GIF section length of LGIopt is prepared for use as the connector expanded beam lens. The measurements of fiber-to-fiber coupling losses for several SMF-GIF pairs with LGI equal to LGIopt and LGIopt±10µm have been performed. The coupling losses for bare SMF-GIF fibers are about 0.5 dB. It increases to about 0.9 dB for SMF-GIF LC/PC connectors. This can be explained by the imperfect alignment of the two connectors. Referring to the calculation, for 55 µm beam waist the coupling loss is 0.4 dB if two beams are tilted at 0.2 degree. Misalignments could arise from ferule positioning or SMF-GIF fiber ends. Optical return losses of the connectors are also measured by an optical coherence-domain reflectometer with a high sensitivity (100 dB) and high spatial resolution (50 µm). The reflection at the SMF/GIF splice is about 70 dB and at the surface of the connector with air gap is about 30 dB. Several pairs of SMF-GIF LC/PC connectors with 55 µm beam waist are put in a test platform for FTTH applications. To test the connector efficiency in XG-PON2, the 10 Gbit/s non-return-to-zero optical signal at the wavelength of 1550 nm is used. It is encoded with a pseudo-random bit sequence (PRBS) of 2 31 -1 pattern length. Fig. 2b shows an example of the bit-error-rate (BER) measurement of the connectors compared to the back-to-back (B2B) case. No penalty is observed. We have demonstrated the use of large mode LC/PC connectors at 10 Gbit/s in FTTH systems. The connectors could be suitable for higher bit-rates.

The robustness of the SMF-GIF interface of the LC/PC connectors has been evaluated in the presence of three contaminants: oil (0.03 ml droplet), water (0.03 ml droplet), and dust particles (Fig. 2c). On this figure, the relative coupling loss is considered referred to the preliminary coupling loss of a connection without contaminant for three fiber types: SMF, SMF-GIF, and multi-mode fiber (MMF). These measurements show that the SMF-GIF version has a better behavior than the SMF and similar to the MMF in the presence of contamination. The physical contact (PC) technology is able to exclude the liquid from the interface due to the high pressure of the spring loading which leads to low optical loss with water contamination. With solid particle contamination, it is a matter of statistical particle distribution over the core area; when the remaining area for passing light becomes smaller, the coupling losses increase accordingly. More, the larger beam waist increases the damage threshold to 1 W against 0.04 W for standard angled physical contact (APC) SMF connectors as the power before failure is proportional to the beam area or the square of the beam waist.

Discussion and conclusions

This study clearly identifies the actual limits of the optical connection technology to cope with future fiber optics application requiring SMF. The study shows the capability of enlarging the light beam at the connection interface without increasing the number of Fresnel reflective interfaces. The simulation based on a GIF with 125 µm cladding shows the capability to increase 25 times the area correlated by the first production batches and measurements. The robust performance during testing confirms that the GIF combined with micro-welded/fused and cutting technology allows manufacturing of a single-mode PC expanded beam (EB) fiber optic interface as rugged as for conventional multimode PC fiber optic interconnection. The technology is thus called "expanded beam physical contact". This approach utilizes the best features of PC and EB technology. As it is, the design can already be adapted to several existing network connectivity platforms such as SC, LC, MPO contacts and connectors.

Acknowledgement

Fig. 1 .

 1 Fig. 1. (a) Principle of the SMF-GIF microlens, (b) calculation of beam waist and working distance based on the analytical method and BPM method, and (c) calculation of 55 µm beam waist coupling losses for different angular misalignments and axial gap related to lateral offset.

Fig. 2 .

 2 Fig. 2. (a) measurement of insertion losses, and beam waist of SMF-GIF LC/PC connectors, (b) BER measurement of the SMF-GIF LC/PC connector in FTTH systems at 10 Gbit/s, and (c) coupling losses measurement with 3 contaminants (oil, water, dust) relative to without contaminant of SMF-GIF LC/PC connectors compared with MMF and SMF (10 times for each).

This work is financed by French government R&D funding.


Hany Kamal
email: hany.kamal@telecom-paristech.fr

Marceau Coupechoux

Philippe Godlewski

Jean-Marc Kelif

Optimal, Heuristic and Q-learning based DSA Policies for Cellular Networks with Coordinated Access Band †

Keywords: Cellular systems, Dynamic Spectrum Access, Markov Desicion Process, Q learning. -

Due to the increasing demands for higher data rate applications, also due to the actual spectrum crowd situation, DSA (Dynamic Spectrum Access) turned into an active research topic. In this paper, we analyze DSA in cellular networks context, where a CAB (Coordinated Access Band) is shared between RANs (Radio Access Networks). We propose an SMDP (Semi Markov Decision Process) approach to derive the optimal DSA policies in terms of operator reward. In order to overcome the limitations induced by optimal policy implementation, we also propose two simple, though sub-optimal, DSA algorithms: a Q-learning (QL) based algorithm and a heuristic algorithm. The achieved reward using the latter is shown to be very close to the optimal case and thus to significantly exceed the reward obtained with FSA (Fixed Spectrum Access). The rewards achieved using the QL-based algorithm are shown to exceed those obtained using FSA. Higher rewards and better spectrum utilization with DSA optimal and heuristic methods are however obtained at the price of a reduced average user throughput.

INTRODUCTION

Wireless networks are facing increasing demand for high data rate applications, and hence their demand for spectral resource increases. Researchers have started working on DSA algorithms as a solution to the spectrum scarcity problem encouraged by the rapid progress in SDR (Software Defined Radio) systems that enable the required reconfigurability for DSA and cognitive radio equipments.

In [START_REF] Buddhikot | Understanding Dynamic Spectrum Allocation: Models, Taxonomy and Challenges[END_REF], the spectrum management models are divided into four main axis: command and control, exclusive-use, primary/secondary usage, and commons. The exclusiveuse model includes a dynamic mode, where spectrum is owned by a single operator at any given point in space or time; owner and usage of the spectrum can however dynamically change. This model is thus particularly adapted to cellular networks. In this context, the IEEE P1900.4 working group has detailed three use cases [START_REF] Buljore | IEEE P1900.4 Standard: Reconfiguration of Multi-Radio Systems[END_REF] [3] with increasing levels of reconfigurability and joint management of resources. In this paper, we focus on the first one and consider a single operator with several RANs, able to dynamically distribute its frequency bands between its RANs.

Several papers are dealing with DSA for cellular networks. For example, in [START_REF] Buddhikot | DIMSUMNet: New Directions in Wireless Networking Using Coordinated Dynamic Spectrum Access[END_REF], authors propose a coordinated DSA system where a pool of resources (CAB or Coordinated Access Band) is shared and controlled by a regional spectrum broker. In [START_REF] Thilakawardana | Darwinian Approach for Dynamic Spectrum Allocation in Next Generation Systems[END_REF], authors made use of the genetic algorithm to analyze the DSA in WCDMA networks. In [START_REF] Sankaranarayanan | A Bandwidth Sharing Approach to Improve Licensed Spectrum Utilization[END_REF], authors propose a MAC protocol enabling ad-hoc secondary users to utilize the unused resources of a GSM system.

It is however difficult to separate technical from pricing aspects when DSA is considered, especially for cellular operators who pay very high prices for the license. The wide interest in DSA is indeed mainly driven by the -Received 9 November 2009 Prepared using ettauth.cls [Version: 2007/01/05 v1.00] Revised Accepted expected benefits resulting from sharing the spectrum [START_REF] Chapin | Cognitive Radios for Dynamic Spectrum Access-The Path to Market Success for Dynamic Spectrum Access Technology[END_REF]. Reference [START_REF] Acharya | A Price Based Dynamic Spectrum Allocation Scheme[END_REF] analyzes a network model where the service providers base stations are sharing a common amount of spectrum. A distributed DSA algorithm is proposed where each user maximizes its utility (bit rate) minus the payment for the spectrum. In [START_REF] Vanbien | A Cell Based Dynamic Spectrum Management Scheme with Interference Mitigation for Cognitive Networks[END_REF], authors have considered a spectrum market, where they propose a Rubinstein-Stahl method for the spectrum trading.

In this paper, we present an approach based on SMDP to analyze DSA in a cellular context. We analyze a network model, where different RANs are sharing a CAB, inspired by the idea of resource sharing proposed in [START_REF] Buddhikot | DIMSUMNet: New Directions in Wireless Networking Using Coordinated Dynamic Spectrum Access[END_REF] and by the single operator use case presented in [START_REF] Filin | Dynamic Spectrum Assignment and Access Scenarios, System Architecture, Functional Architecture and Procedures for IEEE P1900.4 Management System[END_REF]. We take into account the spectrum price, and maximizing the operator revenue is our main concern.

MDP approach has been used to solve several optimization problems in telecommunication networks. In the context of cognitive radio, reference [START_REF] Geirhofer | Cognitive Medium Access: A Protocol for Enhancing Coexistence in WLAN Bands[END_REF] proposes a cognitive medium access protocol that maximizes the throughput while limiting the interference affecting the primary user. The authors formulated the problem within the framework of constrained MDP. In [START_REF] Zhao | Decentralized Cognitive MAC for Opportunistic Spectrum Access in Ad Hoc Networks: A POMDP Framework[END_REF], a POMDP (Partially Observable MDP) framework is proposed to optimize the performance of the secondary users while limiting the interference perceived by the primary users. These references however focus on the primary/secondary usage model.

In [START_REF] Coupechoux | SMDP Approach for JRRM Analysis in Heterogeneous Networks[END_REF], the SMDP framework is used in a JRRM (Joint Radio Resource Managment) context in order to take an optimal CAC (Call Admission Control) decision, whether to accept a new coming call or to reject it. The reward function in [START_REF] Coupechoux | SMDP Approach for JRRM Analysis in Heterogeneous Networks[END_REF] presents the end-user throughput. Different from [START_REF] Coupechoux | SMDP Approach for JRRM Analysis in Heterogeneous Networks[END_REF], SMDP is used in this paper to find the optimal spectrum bands allocations. The reward function in this paper takes into account both user satisfaction and spectrum price.

The paper is organised as follows: section 2 presents the network model in terms of system model, traffic model and the principle of DSA operation. The SMDP approach is presented in section 3. In section 4, we propose a suboptimal DSA heuristic easier to implement for an operator than optimal policies. Section 5 proposes an alternative solution based on Q-learning. The performances of the three approaches (optimal DSA, heuristic DSA and QL based DSA) are compared to the FSA case in section 6. Conclusion is given in section 7.

NETWORK MODEL

System model

We intend to study cell-by-cell DSA between two access networks. RANs are supposed to be homogeneous in propagation and in traffic, and the operator is assumed to deploy classical frequency reuse schemes (i.e., reuse 1 or reuse 3). Based on these assumptions, all cells of a RAN statistically behave the same way, we can thus focus on a single cell per RAN.

The system is thus made of two cells of two different RANs (in this paper, terms cell and RAN will be used indifferently). RANs do not have their own spectrum bands but rather have to dynamically access to a CAB. The CAB is sub-divided into m max elementary spectrum bands (blocks) that can be used indifferently by any RAN. As traffic grows, a RAN can lease a new elementary band (one block) and as it decreases, the RAN can leave it free for the common pool (section 3.3). We assume that the average data rate accessible by users in a RAN is proportional to the bandwidth allocated to the RAN and is equally divided among all users of the RAN (section 2.2). The model is shown in Fig. 1. Parameters n i , i = 1, 2 are the number of active users in RAN1 and RAN2. Parameter m i is the current number of elementary bands leased by RAN i from the CAB.

Both RANs are operated by a single operator responsible for attributing or freeing elementary bands to each RAN. On the one hand, revenue is assumed to be proportional to the satisfaction of the users. On the other hand, it is supposed that spectrum cost follows the law of supply and demand: as free spectrum diminishes, spectrum cost increases (section 3.2). We are interested in the optimal policy that assigns bandwidth to the RANs. Our model could be coherent with multi-carrier HSPA (High Speed Packet Access) systems. According to 3GPP release 8, an evolution of the HSPA systems will indeed allow the aggregation of 5 MHz carriers [START_REF]3GPP[END_REF].

Our model could also be coherent with SOFDMA (Scalable Orthogonal Frequency Division Multiple Access) cellular networks (i.e. WiMAX, 3GPP-LTE), where the bandwidth of the system is scalable [14]. In these systems the operator has indeed an additional flexibility in resource allocation through the possibility of scaling the bandwidth.

Traffic

We consider a bursty packet traffic, such as web browsing or file downloading on the downlink: a user alternates between packet calls (several packets are transferred in a very short time) and reading times (there is no transfer). In this paper, we focus on the packet call level and so we neglect the details of the packet level.

We assume Poisson arrivals of user downlink packet calls with rate λ 1 in RAN1 and λ 2 in RAN2 (see Fig. 1). Traffic is supposed to be elastic: the packet call size is exponentially distributed with mean X ON bits in both RANs and so the service rate depends on the available RAN throughput. We assume a throughput fair scheduling between users of a given RAN. For RAN i let D i be the cell data rate (in bits/s) accessible with an elementary spectrum band. Then, the service rates can be written as:

µ i = m i D i X ON . (1)
An illustration of the traffic model is shown in Fig.

Dynamic spectrum access

In the considered system model, the core issue for the operator of the RANs lies in the trade-off to be found between spectrum cost and revenues obtained from users: more spectrum per RAN means a higher lease cost for the operator but also higher throughputs for users that are encouraged to pay more for the service. As the CAB size is limited and as spectrum cost increases with increasing demand, there is a strong interaction between RANs.

In this paper, a DSA policy is a strategy that dynamically attributes spectrum bands to each RAN from the CAB. We assume that a DSA decision is taken at each new event, i.e., a new packet call arrival or a packet call departure in any RAN (see Fig. 2). A DSA decision is supposed to increase the number of spectrum bands for a RAN by a single block, to decrease by a single block this number, or to keep constant the spectrum of a RAN. We thus do not allow too abrupt changes in resource allocation.

We further assume that at least one spectrum block is always available to each RAN, so that starvation is not possible. We are now interested in the optimal DSA policies in terms of operator revenue.

OPTIMAL DSA POLICIES

In order to achieve this goal, we rely on the SMDP framework. We first define the SMDP and the reward function, then use uniformization to obtain an MDP and rely on the policy iteration algorithm to find the optimal DSA policy.

State space

The system state is given by all four-tuple

(n 1 , m 1 , n 2 , m 2 ) with constraints n 1 ≤ n max 1 , n 2 ≤ n max 2 and m 1 + m 2 ≤ m max .
The limitation imposed to the number of active users is equivalent to setting a minimum throughput per RAN. Let S be the state space.

Reward function

The reward function is based on the revenue expected by the operator. The higher the satisfaction of users, the higher the operator revenue; the higher the amount of bandwidth leased by RAN, the higher the cost to lease this spectrum band. We define a comfort service rate µ com . The revenue obtained from a given customer in RAN i increases with its satisfaction: where K u is a constant in euros per unit of satisfaction. Satisfaction, defined in [START_REF] Enderlé | User Satisfaction Models and Scheduling Algorithms for Packet-Switched Services in UMTS[END_REF], is an increasing function of the user data rate and is without unit. As the scheduling is fair in throughput, each user gets a data rate proportional to µ i /n i in RAN i. Thus the total revenue obtained by the operator in state s

φ i (n i , m i ) = K u (1 -exp(-µ i /n i µ com )),
= (n 1 , m 1 , n 2 , m 2 ) is g 1 (s) = n 1 φ 1 (n 1 , m 1 ) + n 2 φ 2 (n 2 , m 2 ).
We assume that the spectrum price is increasing when the amount of free spectrum decreases and we define it as:

g 2 (s) = K B (m 1 + m 2 ) exp - m max -m 1 -m 2 m com ,
where m com is a constant that controls the variation of the price and K B is a constant in euros per MHz (it is the equivalent spectrum price per cell). If m com is high, the exponential function is close to 1 whatever the state. If m com is small, there is a high discount when the CAB is free. Note that the price paid by the operator for a given elementary band varies with the occupation of the CAB. The global reward function per time unit can thus be written in state s:

g(s) = g 1 (s) -g 2 (s). (2)
Note that g(s) is defined per time unit because the longer the spectrum is used, the more the operator pays. In the same way, for a given throughput, the longer a user is using the bandwidth, the more he has to pay.

Action space

In each state, the operator is allowed to increase, decrease or leave unchanged the spectrum of each RAN. As shown in Fig. 2

ν s (a) = 1 {n1<n max 1 } λ 1 + 1 {n2<n max 2 } λ 2 +1 {n1>0} µ 1 + 1 {n2>0} µ 2 .
Transition probabilities are given by:

p s,s (a) =            λ i /ν s (a) if (n i = n i + 1)
and (∀j

m j = m j + a j ), µ i /ν s (a) if (n i = n i -1)
and (∀j m j = m j + a j ), 0 otherwise.

(3)

Uniformization

A step of uniformization is now needed in order to transform the continuous time Markov chain into an equivalent discrete time Markov chain [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF]. This is done by choosing a sufficiently small transition step 1/ν (∀s, a, ν s (a) ≤ ν) and allowing self transitions from a state to itself. Transition probabilities are modified in the following way:

ps,s (a) = p s,s (a)ν s (a)/ν if s = s , 1 -s =s ps,s (a) otherwise. (4)
A DSA policy R associates to each system state s, an action R(s) from the action space of s.

Policy iteration

We are interested in finding the optimal policy R * of the continuous-time average cost problem described above.

For that, we apply the policy iteration algorithm to the auxiliary discrete-time average cost problem obtained after uniformization (see [START_REF] Bertsekas | Dynamic Programming and Optimal Control[END_REF], vol.2, p.315). The iterative algorithm is now succinctly described, it iteratively solves Bellman equations in a synchronous manner.

Algorithm 1 Policy Iteration 1: Initialization: Let R be an arbitrary stationary policy.

2: Value-determination: For the current policy R, we solve the system of linear equations whose unknowns are the variables

{J R , h R (s)}: h R (1) = 0 and h R (s) = g(s) -J R + s ∈S
ps,s (R(s))h R (s ).

3: Policy improvement: For each s ∈ S, we find:

R (s) = arg max a∈A(s) {g(s) -J R + s ∈S
ps,s (a)h R (s ) .

4: Convergence test: If R = R, the algorithm is stopped, otherwise, we go to step 2 with R := R .

The SMDP approach has the advantage of providing optimal policies and an upper bound on the achievable reward. The policy iteration algorithm takes into account not only RANs loads, the number of active users and RANs interactions but also the whole dynamics of the system. Optimal policies are thus strongly dependent on the system parameters and simple examples cannot be easily generalized when the number of system states increases. In the next section, we propose a sub-optimal DSA heuristic that overcomes these limitations for an operator, while still providing a high reward.

HEURISTIC DSA

DSA policies implementation

In order to implement optimal policies, an operator would have to run the policy iteration algorithm for all possible system parameter sets and store results to be dynamically used according to the context. Running policy iteration on a real-time basis seems indeed difficult, especially when the number of system states increases (for example if many cells or users are considered). The proposed DSA heuristic intends to ease DSA implementation for an operator. With this heuristic, massive storage of data is not needed and computations can be done on the fly.

Proposed DSA heuristic

Optimal DSA policies decisions are taken at each new event (a packet call arrival or departure) and thus depend not only on the arrival rates (λ 1 , λ 2 ) but also on the variations of the number of users (n 1 , n 2 ). In order to obtain a simple heuristic, we focus only on the arrival rates and neglect the variations of (n 1 , n 2 ).

Let us now consider that (m 1 , m 2 ) is fixed for a given couple (λ 1 , λ 2 ). In this case, each of the RANs can be considered as a M/M/1/n max i system. The service rate µ i is indeed constant (see Eq. 1) and in every state n i , the departure rate is µ i = n i × µ i /n i because of the throughput fairness scheduling assumption.

With these assumptions, the average heuristic reward for the operator, g H , can be easily computed for all possible combinations of alloacted bands (m 1 , m 2 ), along with the corresponding λ i values. The average reward is the sum of the rewards obtained from the two RANs. For a given (λ 1 , λ 2 , m 1 , m 2 ):

g H (λ 1 , λ 2 , m 1 , m 2 ) = 2 i=1 n max i ni=0 π ni (λ i )n i φ i (n i , m i ) -g 2 (n 1 , m 1 , n 2 , m 2 ), (5)
where the π ni (λ i ), i ∈ {1, 2}, n i ∈ {0, ..., n max i } are the steady state probabilities of a M/M/1/n max i with arrival rate λ i and service rate µ i . We use this result for the proposed DSA heuristic:

Algorithm 2 Heuristic DSA 1: Estimate arrival rates λ 1 and λ 2 . 2: for all (m 1 , m 2 ) do 3:

Compute the average reward g H according to Eq. 5. 4: end for 5: Allocate bandwidth according to the tuple (m 1 , m 2 ) that maximizes the average reward g H .

Eq. 5 can be instantaneously computed for realistic values of the n max i and can be easily extended to several cells. Note that this proposed heuristic algorithm still need the knowledge of several system parameters, like λ 1 , λ 2 , µ 1 , µ 2 and X ON , which can not be always easily obtained by the operator. We now propose an alternative solution based on Q-learning in order to overcome this limitation.

Q-LEARNING BASED DSA

Reinforcement learning

Reinforcement learning (RL) is a simulation-based dynammic programming technique used to solve complex MDPs (Markov Decision Problems) without the need of knowing the transition probabilities. RL is concerned about learning how to take an action that maximizes a specific metric, typically long-term rewards. The algorithm trains an agent to take the appropriate action in response to the environment reactions. The agent learns by analyzing its actions through the evaluation of the received rewards (for each action it takes). In RL, the agent / environment interactions are usually modeled by an MDP (Markov Decision Process) [START_REF] Tadepalli | Model-based average reward reinforcement learning[END_REF], [START_REF] Glorennec | Reinforcement Learning: an Overview[END_REF]. In this paper, we are going to use the Q-learning technique that solves a MDP using the value-iteration method.

Q-learning for continuous average-cost problem

In Q-learning, the agent learns the action-value function with the target of determining a policy that maximizes long-term rewards. The value function is a function (known as Q function) that gives the expected long-term reward obtained by applying a certain policy. The Q function represents an evaluation of each action, taken by the agent, and associates it with the environment-state at the moment of executing this action. Most approaches to RL, including QL, are developed to optimize discrete discounted-reward problems. The original QL algorithm presented by Watkins [START_REF] Watkins | Learning from Delayed Rewards[END_REF], was based on discounted reward value iteration [START_REF] Gosavi | Reinforcement learning for long-run average cost[END_REF]. Discounted optimization is motivated by domains in which reward is money that earns interest in each time step [START_REF] Tadepalli | Model-based average reward reinforcement learning[END_REF].

In case of average cost problems, QL does not apply immediately. Setting the discount factor to 1 in the Qlearning algorithm would be equivalent to base the method on the average cost value iteration, which is known to be unstable. Using a high discount factor would cause the learning convergence to be too slow. Authors of [START_REF] Abounadi | Learning algorithms for Markov decision processes with average cost[END_REF] and [START_REF] Tadepalli | Model-based average reward reinforcement learning[END_REF] have proposed RL algorithms that solve the average cost problem. They are however designed for discrete-time models. An interesting solution for both average cost and continuous-time problems can be found in [START_REF] Gosavi | Reinforcement learning for long-run average cost[END_REF].

Gosavi algorithm

In this section we give the details of the Gosavi algorithm [START_REF] Gosavi | Reinforcement learning for long-run average cost[END_REF] that we used to implement a QL-based DSA for our average-reward continuous-time problem.

Q factors update:

Like in the traditional Q-learning algorithm, the agent in state s t takes an action a t ; this causes the system to move to state s t+1 ; reward r t is observed and the value of the action is denoted Q(s t , a t ). The Q function (or the Q-factor) is updated each time there is a state transition. The action is then taken at the instant of a new event. The Q function is updated formally, according to [START_REF] Gosavi | Reinforcement learning for long-run average cost[END_REF], as follows:

Q(s t , a t ) = (1 -α)Q(s t , a t ) + α r t -α ρ δ t (6) + α arg max a∈A(s) {Q(s t+1 , a)} ,
where α is a learning factor, ρ is the estimated averagereward, and r t denotes the reward obtained upon spending a period δ t in state s t . Fig. 3, gives an illustration of the Q-factor updating principle, along with the instants where the actions are executed, as implemented in our simulator. The algorithm's main idea is a relative value iteration update. At every state-transition instant, the agent updates the old Q-factor according to the new information. When the system visits a state, the agent selects the action with the highest rewards, this is represented in the term arg max a∈A(s) {Q(s t+1 , a)} in Eq. 6

Although average-reward value iteration is numerically unstable, Gosavi's algorithm uses a relative value-iteration method. The relative value iteration method differs by substracting some value (δ t ρr t ) from the Q-factor.

-Prepared using ettauth.cls Euro. Trans. Telecomms. 00: 1-10 (2007) DOI: 10.1002/ett 5.3.2. Exploration-exploitation policy: In this paper, we use a p-greedy method to explore and exploite: with a probability p, the agent chooses a random action among the given set of authorized actions, and with a probability 1 -p, the agent exploits the Q-factors.

Learning factors:

In case the agent chooses to exploit the Q-factors, he updates the estimated averagereward ρ, using a decreasing (and a second) learning factor β. The parameter ρ is updated as follows:

• The estimated total reward C is updated as:

C ← (1 -β)C + β r t . (7)
• The estimated total time T is updated as:

T ← (1 -β)T + β δ t . (8)
• Parameter ρ is updated as:

ρ = C/T. (9)
The Gosavi algorithm is thus a two time-scales QL algorithm, the average cost is approximated on one time scale and the Q-factor on the other [START_REF] Gosavi | Reinforcement learning for long-run average cost[END_REF].

Two learning factors on two time scales are used. Both of them decrease as the algorithm runs. The learning factor α depends on the number of times the state-action pair was tried until that decision epoch. The learning factor β depends on the number of decision epochs in which the Q-factors have been exploited.

In order to compare this approach to other DSA policies, we first launch the algorithm during a learning phase during which we use the exploration-exploitation policy and two decreasing learning factors (α and β). By the end of the learning phase, the QL algorithm provides us with the output policy. We then calculate analytically the average reward knowing the policy provided by the QL algorithm. The details of the algorithm are given in Algorithm 3.

PERFORMANCE EVALUATION

In this section, we compare the results obtained with optimal DSA policies, the proposed heuristic, the QLbased DSA and FSA in terms of operator reward, CAB utilization, and average user throughput.

Algorithm 3 Q-learning based DSA 1: Initialize the following parameters:

• the initial state: s t = (0, 0, 1, 1).

• Q-factors: Q(s, a) = 0, ∀s ∈ S and a ∈ A(s).

• the estimated total cost: C = 0.

• the estimated average reward: ρ is set to average reward obtained with the heuristic DSA. • the number of times Q is exploited: k = 0.

• the number of visits to the state-action pair (s, a): N v (s, a) = 0, ∀s ∈ S and a ∈ A(s).

2: repeat 3:

Exploration-exploitation policy: draw uniform random variable X on [0, 1].

4:

if X < p (exploration) then 5:

Choose action a t at random 6:

else 7:
Choose action a t that maximizes Q(s t , a) on the set of actions in state s t .

8:

Update learning factors α = 1/(1 + N v (s, a)) and β = 1/(1 + k).

9:

Update Q(s t , a t ) according to Eq. 6.

10:

Update the estimated average reward ρ according to Eq. 7, 8 and 9.

11:

k ← k + 1.
12:

end if

13: N v (s t , a t ) ← N v (s t , a t ) + 1.
14:

s t ← s t+1 .
15:

t ← t + 1. 16: until End of the learning period

Parameters

The CAB is assumed to have a size of 6 MHz, the elementary band (m i = 1) has a size of 1 MHz, and m com = 4 MHz. For the sake of simplicity, we assume that both RANs have the same characteristics: the average cell data rates D i are considered to be 1250 Kbps, X ON = 3 Mbits, λ 1 = λ 2 = λ, and n max We can notice that the (m 1 , m 2 ) values that give the maximum reward are: (1,1), [START_REF] Buljore | IEEE P1900.4 Standard: Reconfiguration of Multi-Radio Systems[END_REF][START_REF] Buljore | IEEE P1900.4 Standard: Reconfiguration of Multi-Radio Systems[END_REF], and [START_REF] Filin | Dynamic Spectrum Assignment and Access Scenarios, System Architecture, Functional Architecture and Procedures for IEEE P1900.4 Management System[END_REF][START_REF] Filin | Dynamic Spectrum Assignment and Access Scenarios, System Architecture, Functional Architecture and Procedures for IEEE P1900.4 Management System[END_REF] depending on the arrival rate λ. The maximum reward can then be obtained by dynamically allocating symmetric numbers of elementary bands to the RANs according to the cell load. This result was expected since in this simulation λ 1 = λ 2 . Threshold values for λ are given on Fig. 4.

Convergence of the QL-based DSA

We illustrate in this section the convergence of the QLbased DSA algorithm through a study on the estimated average reward ρ. Fig. 5 represents the convergence of the estimated average reward ρ as a function of the number of events for two different arrival rates, λ = 0.2 and λ = 1.5 s -1 .

We can notice that the value of ρ fluctuates at the beginning of the learning phase and starts to stabilize after a certain duration (i.e., number of events). The duration required for ρ to stabilize is the period equivalent to about 200 thousands events in our examples. Note that the Qlearning algorithm theoretically converges to the optimal policy after an infinite duration. In our simulations, we stop learning after a realistic duration (200 thousands events) and exploit the obtained policy. 6.4. Operator reward, CAB utilization, user throughput Fig. 6 compares operator rewards obtained respectively with optimal DSA policy, the proposed heuristic, the QLbased DSA and FSA. By definition, FSA allocates m i = 3 elementary bands to each RAN whatever the system state.

It can be seen that optimal policies provide significant increases of the reward for low to intermediate values of λ (for example +229% at λ = 0.5 s -1 ). At high load, FSA and optimal DSA policy converge as expected. Both the proposed heuristic and the QL-based DSA provide the optimal reward at low load and converges also to FSA at high load: only for intermediate values of λ, there is a small degradation of the reward (for example, -21% at λ = 0.7 s -1 for the heuristic method). Fig 7 gives a comparision of the reward gains, in percentage, for the proposed DSA methods with respect to the rewards obtained using FSA.

We can notice that, the three proposed methods achieve gain in terms of rewards over FSA for arrival rate values λ < 2 s -1 . All the proposed DSA methods give rewards that converge to the same reward values as FSA for arrival rates λ > 2 s -1 .

These results can be explained by a better utilization of the sepctrum. CAB utilization is illustrated in Fig. 8 as a function of the arrival rate λ. Optimal DSA policy smoothly increases the CAB utilization as arrival rate increases. The proposed heuristic follows this trend with a step function. QL-based DSA, although a bit less efficient, has a similar behavior. It is worth mentioning the DSA gain in terms of spectral resource usage with respect to FSA. To explain the difference between the heuristic DSA and the QL-based method, it is worth mentioning that the heuristic method needs to know all the networks parameters such as, λ, X ON and D i , unlike the case of the QL-based algorithm. The fact that QL-based DSA is below the optimal DSA in terms of performance is explained by the fact that the learning phase is voluntary limited to a realistic duration.

Operator reward and better spectrum utilization with the three proposed approaches are however obtained at the price of a degradation of the average user throughput. The observed variations of the heuristic DSA between λ = 0.5 and 1.5 s -1 can be explained by the changes of resource allocation at threshold values 0.73 and 1.44 s -1 (see Fig. 4).

The achieved average user throughput with FSA is however much higher, especially at low loads. According to the traffic assumptions (see section 2.2), a single user is indeed allowed to take advantage of the whole bandwidth allocated to a RAN. At low loads, FSA allocates 3 MHz to each RAN, while DSA methods allocates only 1 MHz leading to lower user throughputs. Our assumptions represent thus a worst case scenario; a terminal or service limitation in maximum data rate would reduce the advantage of FSA at low loads.

CONCLUSION

In this paper, we have studied DSA in cellular networks context. We have used the SMDP framework to derive optimal DSA policies in terms of the operator reward. We have proposed two methods to defeat the generalization difficulty of the optimal policies over realistic systems: a simple heuristic DSA method and a QL-based DSA algorithm. The achieved reward using the heuristic DSA gives a very close reward to the optimal obtained by SMDP and thus significantly exceeds the reward obtained with FSA. The obtained reward using the QL-based has shown its gain over reward achieved using FSA. Although less gain is achieved using QL-based DSA, however the algorithm does not need to know the networks parameters. Operator revenue increases but better spectrum utilization is obtained at the price of a user throughput degradation.

Figure 1 .

 1 Figure 1. System model: two RANs access to a CAB according to their needs.

2 .

 2 Arrows on the time axis represent Poisson arrivals of new packet calls and grey rectangles their duration. Packet calls are made of several packets that together represent X ON bits. time Arrival rate = λ (RAN1) or λ (RAN2)

Figure 2 .

 2 Figure 2. Assumed traffic model.

-

  Prepared using ettauth.cls Euro. Trans. Telecomms. 00: 1-10 (2007) DOI: 10.1002/ett

-

  Prepared using ettauth.cls Euro. Trans. Telecomms. 00: 1-10 (2007) DOI: 10.1002/ett

-

  Prepared using ettauth.cls Euro. Trans. Telecomms. 00: 1-10 (2007) DOI: 10.1002/ett

Figure 3 .

 3 Figure 3. Illustration of the Q-value updating principle in our system-model context.

1 = n max 2 = 8 .-

 128 The pricing constants are fixed as follows: K u = 100 euros, K B = 1 euro, and µ com = 0.167 s -1 (which corresponds to a comfort throughput of 500 Kbps).Concerning the QL-based DSA algorithm, the agent keeps learning (and updating the Q-factors) for 200 thousands events, and the results are averaged over 20 iterations. Prepared using ettauth.cls Euro. Trans. Telecomms. 00: 1-10 (2007) DOI: 10.1002/ett 6.2. Arrival rate thresholds for heuristic DSA For the considered parameter set, Fig.4shows the average reward g H (see Eq. 5) as a function of the arrival rate λ for different combinations of the allocated bands.

Figure 4 .

 4 Figure 4. Operator reward obtained for different allocated bands combinations and load thresholds for heuristic DSA.

Figure 5 .

 5 Figure 5. Convergence of the estimated average reward ρ for Qlearning based DSA.

-Figure 6 .Figure 7 .

 67 Figure 6. Operator reward obtained with optimal DSA, heuristic DSA, QL-based DSA, and FSA.

Figure 8 .

 8 Figure 8. CAB utilization with optimal DSA, heuristic DSA, QLbased DSA, and FSA.

Fig. 9

 9 Fig.9illustrates the average user throughput as a function of the RANs load λ. Optimal DSA policy, the proposed heuristic and the QL-based DSA show again similar results.The observed variations of the heuristic DSA between λ = 0.5 and 1.5 s -1 can be explained by the changes of resource allocation at threshold values 0.73 and 1.44 s -1 (see Fig.4).The achieved average user throughput with FSA is however much higher, especially at low loads. According to the traffic assumptions (see section 2.2), a single user is indeed allowed to take advantage of the whole bandwidth allocated to a RAN. At low loads, FSA allocates 3 MHz to each RAN, while DSA methods allocates only 1 MHz leading to lower user throughputs. Our assumptions represent thus a worst case scenario; a terminal or service limitation in maximum data rate would reduce the advantage of FSA at low loads.

-Figure 9 .

 9 Figure 9. Average user throughput with optimal DSA, heuristic DSA, QL-based DSA, and FSA.

Table 1 .

 1 , a decision epoch occurs at each packet call arrival, or departure. As state transitions occur only at the arrival or the departure of a single user, we assume that the band assigned to a single RAN can be increased or decreased by a single elementary band. This leads to nine possible actions of the form a = (a 1 , a 2 ), a i ∈ {0, -1, +1} given in Tab. 1.The effective action space depends on the state. If m i = 1 the spectrum band of RAN i cannot decrease. If the CAB is blocked, i.e., if m 1 + m 2 = m max , no band can increase. List of possible actions Let p s,s (a) be the probability that at the next decision epoch (i.e., at the next transition), the system will be in state s= (n 1 , m 1 , n 2 , m 2 ) if a is chosen in state s = (n 1 , m 1 , n 2 , m 2 ). Let 1/ν s (a) be the expected time until next decision epoch if action a is chosen in state s:

	Action	a vector	action index
	Band1 constant and Band2 constant	(0, 0)	1
	Band1 constant and Band2 increases	(0, +1)	2
	Band1 constant and Band2 decreases	(0, -1)	3
	Band1 increases and Band2 constant	(+1, 0)	4
	Band1 increases and Band2 increases	(+1, +1)	5
	Band1 increases and Band2 decreases	(+1, -1)	6
	Band1 decreases and Band2 constant	(-1, 0)	7
	Band1 decreases and Band2 increases	(-1, +1)	8
	Band1 decreases and Band2 decreases (-1, -1)	9
	3.4. Transition probabilities

ACKNOWLEDGEMENT

This work is part of the French program Systematic/URC funded by Paris Region and the national authorities.