Judicaël Ribault
email: judicael.ribault@u-bordeaux1.fr

Gregory Zacharewicz
email: gregory.zacharewicz@u-bordeaux1.fr

TIME-BASED ORCHESTRATION OF WORKFLOW, INTEROPERABILITY WITH G-DEVS/HLA

Keywords: Workflow, Taverna, Interoperability, Discrete event simulation, G-DEVS, HLA 1

Enterprises information systems (EIS) take benefits of latest advanced of web services and internet of things to improve information retrieving and gathering for decision making. Furthermore, EIS should permit a more comprehensive information routing in the company within an electronic workflow in order to save time, cost and to reduce production impact on the environment. Such software has to interact frequently with real world data acquired by different sensors. Nevertheless this combination of software and hardware devices frequently faces interoperability problems. Also, testing and validating the EIS is not trivial without testing in real condition that can lead to deploy the large system. Authors assumed that testing and validating part of the system behaviour can be anticipated progressively by simulation, permitting then more progressive and confident system integration. This paper proposes to introduce a new workflow demonstration platform to combine simulation world with real world interacting with sensor, human interfacing and web service calls. In detail, this paper proposes to combine the Taverna Workflow tool, which handles and triggers web services call proposed by a platform server, to other software components. This combination has revealed one drawback of major workflows orchestrators; they do not provide time management facilities to handle synchronization during parallel execution of interdependent workflows. To overcome that limitation a clock ordering solution has been added by reusing G-DEVS/HLA to synchronize workflows running in parallel. The imbrication of G-DEVS M&S with Taverna workflow is now operating thanks to HLA. This work is validated by demonstrating the interoperability and the complementarity of these approaches on a logistic platform study case.

INTRODUCTION

The effectiveness of enterprise information system (EIS) depends not depend anymore only on the internal P r e P r i n t interconnectivity of its inner software components, but more and more on its ability to exchange data, so to collaborate, with every day new tools developed and updated in the environing digital world. This requirement led to the development of the concept called interoperability that intends to improve collaborations between EIS companies. No doubt, in such context where more and more networked enterprises are developed; enterprise interoperability is seen as one of the most wanted feature in the development of an EIS. Also, data treatment calls actions of both human processing and automatic treatments. The sequencing of these actions should be controlled or orchestrated by a high level application that can decide the human resource and/or component to solicit. The sequence of actions is commonly entitled Workflow (WF) and its administration Workflow management. This field is studied and standardized by the Workflow Management Coalition (WfMC) [WfMC, 1999] [WfMC, 2005].

Several research-works have been launched since the 90's in the field of WF. Workflow was first designed to formalize and improve enterprise business process. A production workflow is a set of linked steps required for developing a product until it is put on the market [START_REF] Weske | Business Process Management Archi-tectures[END_REF]. The workflow steps are based on observing a number of steps that were originally manually enchained then formalizing them to be computer assisted. The research on the WF initiated by the Workflow Management Coalition [WfMC, 1999] [WFMC, 2005] and used for instance in [START_REF] Zacharewicz | G-DEVS/HLA Environment for Distributed Simulations of Workflows[END_REF] was a premise to current WF modelling (e.g. with Business Process Model and Notation (BPMN) [OMG, 2011]). It has permitted for instance the development of Build Time models used for setting Enterprise Resource Planning (ERP) systems.

Deploying such WF is a critical task for the companies that continue to rely on their EIS during the setting. Moreover the proper functioning is difficult to achieve because the installing team doesn't have vision or access to the whole system (EIS environment) during settings, so the final global behaviour is difficult to predict. Executing the WF on part of the real system, while simulating some critical parts that will then be deployed, can be a good option to test the WF behaviour and reduce risk and cost. However, most WF tools and service orchestration are limited in the handling of time management. But without time consideration, executing a parallel simulation with disjunction and junction gateway between tasks is difficult. Distributed simulation has a long time experience in this field and can be an answer for this problem. Few approaches combine efficiently Modelling and Simulation (M&S) and real executions in the WF domain.

Main reasons are: slowing-down due to synchronization of the simulation engine, that is usually constrained by pessimistic causality [Chandy and Misra, 1979] between real and simulated time, and interoperability barriers that are faced between different hardware and software [Chen and Doumeingts, 2003].

Recent improvements in web-based development propose new facilities to connect applications in a more convenient way. For instance, web services can solve part of the interoperability question. WF can be used as an interoperability P r e P r i n t layer between services, and especially Web Services (WS). This paper proposes to use web services and WF for interoperability between simulation and real-world application. Web services enable the integration of applications or data from heterogeneous sources (i.e. Mash-up). Nevertheless the synchronisation is not solved; this work proposes an additional component from the High Level Architecture standard named Run Time Infrastructure (RTI) reused from the G-DEVS/HLA works. In the end, this paper proposes to apply the use of WF Web services and simulation to the transport domain application through the PRODIGE project to validate the approach.

Section 2 describes the necessary background needed to understand how WFs of services and simulation can drive real application. Section 3 presents the scientific contribution while section 4 put it into practice in a real application framework.

BACKGROUND

In this section, we first present the enterprise interoperability concept. Then we briefly present the HLA standard for interoperability of simulation and how WF can be used for experimentation. We recall the DEVS formalism and G-DEVS. Finally we introduce the Taverna WF management system to orchestrate the experimentation.

Enterprise interoperability

Enterprise Interoperability [Chen and Doumeingts, 2003] refers to the interaction ability between enterprise systems.

The interoperability is considered as significant if the interactions can take place at least at the three different levels: data, services and process, with a semantic defined in a given business context.

Interoperability extends beyond the boundaries of any single system, and involves at least two entities. Consequently establishing interoperability implies relating two systems together and removing incompatibilities. Concepts related to enterprise interoperability are classified into three main dimensions as described in [Chen and Doumeingts, 2003]:



The integrated approach demands all partners to have the same description of information.

 The unified approach asks partners to prepare the data to exchange in order for it to be compliant with a Meta model but local description can be kept.

 The third approach is federated. Here, interoperability must be accommodated on-the-fly between partners without considering a pre-existing Meta model.

The goal of these approaches is to tackle interoperability problems through the identification of barriers (incompatibilities) which prevent interoperability. The first kind of barrier concerns the nonexistence of commonly recognized paradigms and data structure, for that, clarification is required to propose a sound paradigm. The second P r e P r i n t

requirement is the synchronization of data. The order of exchanged data is important, ignoring this can lead to misunderstanding and malfunction of the model. Finally the enterprise modelling must take into account the confidential management of data. In this privacy context, concurrent enterprises must define data sharing strategies. The interoperability can be considered between concurrent enterprises in that context, a strategy of data sharing/not sharing between these must be defined. In the presented work the interoperability is focused between WF simulation and service calls. In the simulation domain, the HLA is established as the interoperability reference.

Simulation interoperability with HLA

The High Level Architecture (HLA) [IEEE, 2000] [IEEE, 2003] is a software architecture specification that defines how to create a global software execution composed of distributed simulations and software applications. This standard was originally introduced by the Defense Modelling and Simulation Office (DMSO) of the US Department Of Defence (DOD). The original goal was the reuse and interoperability of military applications, simulations and sensors.

HLA concepts

In HLA, every participating application is called federate. A federate interacts with other federates within a HLA federation, which is in fact a group of federates. The HLA set of definitions brought about the creation of the standard 1.3 in 1996, which then evolved to HLA 1516 in 2000 [IEEE, 2000] and finally to 1516 Evolved [IEEE, 2010].

The interface specification of HLA describes how to communicate within the federation through the implementation of HLA specification: the Run Time Infrastructure (RTI). Federates interact using the proposed services by the RTI. They can notably "Publish" to inform on the intention to send information to the federation and "Subscribe" to reflect information created and updated by other federates. The information exchanged in HLA is represented in the form of classical object-oriented programming. The two kinds of object exchanged in HLA are Object Class and Interaction

Class. The first kind is persistent during run time, the other one is just transmitted between two federates. These objects are implemented with XML format. More details on RTI services and information distributed in HLA are presented in [IEEE, 2000] and [IEEE, 2010]. In order to respect the temporal causality relations in the execution of distributed computerized applications; HLA proposes to use classical conservative or optimistic synchronization mechanisms [START_REF] Fujimoto | Parallel and Distributed Simulation System[END_REF]. In HLA 1516 Evolved [IEEE, 2010] the service approach is demanded as core feature. Nevertheless no software addresses completely that goal at the moment [Tu et al.,12].

HLA Implementation Components

An HLA federation is composed of federates and a Run time Infrastructure (RTI) [IEEE, 2000].

P r e P r i n t

A federate is a HLA-compliant program, the code of that federate keeps its original features but must be extended by other functions to communicate with other members of the federation. These functions, contained in the HLA-specified class code FederateAmbassador, make the information received resulting from the federation interpretable by a local process. Therefore, the federate program code must inherit the FederateAmbassador class code, complete the abstract methods defined in this class, to be able to receive information from the RTI.

The RTI supplies services required by distributed executions, it routes messages exchanged between federates and is composed of two parts. The "Local RTI Components code" (LRC, e.g. in Figure 1) supplies external features to the federate to use RTI call back services such as handling objects and time management. The implementation is the class

RTIAmbassador, which transforms the data coming from the federate in an intelligible format for the federation. The federate program calls the functions of RTIAmbassador in order to send data to the federation or to ask information to the RTI. Each LRC contains two queues, a FIFO queue and a time stamp queue to store data before delivering to the federate.

Finally, the "Central RTI Component" (CRC, e.g. in Figure 1) manages the federation notably by using the information supplied by the FOM [IEEE, 2003] to define Objects and Interactions classes participating in the federation.

Object class contains object-oriented data shared in the federation that persists during the run time, Interaction class data are just sent and received.

Figure 1. HLA implementation components

A federate can, through the services proposed by the RTI, "Publish" and "Subscribe" to a class of shared data.

"Publish" allows to diffuse the creation of object instances and the update of the attributes of these instances. "Subscribe"

is the intention of a federate to reflect attributes of certain classes published by other federates.

DEVS and G-DEVS M&S

Discrete EVent Specification (DEVS) was introduced by [START_REF] Zeigler | Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems[END_REF]. This Moore based language describes a dynamic system with a discrete event approach using some typical concepts. In particular it represents a state lifetime.

Central

P r e P r i n t

When a lifetime is elapsed an internal transition occurs that changes the state of the model. The model also takes into account the elapsed time while firing an external state transition triggered by an event received from outside the considered model.

The behavioural models are encapsulated in atomic models that are completed with input and output ports. Then, these models can be composed with others by connecting inputs and outputs. The composed models are called coupled models.

Generalized DEVS (G-DEVS) emerged with the drawback that most classical discrete event abstraction formalisms (e.g. DEVS) face: they approximate observed input-output signals as piecewise constant trajectories. G-DEVS defines abstractions of signals with piecewise polynomial trajectories [START_REF] Giambiasi | GDEVS A Generalized Discrete Event Specification for Accurate Modeling of Dynamic Systems[END_REF]. Thus, G-DEVS defines the coefficient-event as a list of values representing the polynomial coefficients that approximate the input-output trajectory.

Therefore, an initial DEVS model is a zero order G-DEVS model (the input-output trajectories are piecewise constants).

In fact G-DEVS was the pioneer DEVS extension proposing a multi value event.

G-DEVS keeps the concept of the coupled model introduced in DEVS [START_REF] Zeigler | Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems[END_REF]. Each basic model of a coupled model interacts with the others to produce a global behaviour. The basic models are either atomic or coupled models that are already stored in the library. The model coupling is done with a hierarchical approach (due to the closure under coupling of G-DEVS, models can be defined in a hierarchical way).

On the simulation side, G-DEVS models employ an abstract simulator [START_REF] Zeigler | Theory of modeling and simulation: Integrating discrete event and continuous complex dynamic systems[END_REF] P r e P r i n t

Workflow

Workflow was first designed to improve the business process. A production workflow is a set of steps required for developing a product until it is put on the market [START_REF] Weske | Business Process Management Archi-tectures[END_REF]. The workflow steps are based on observing a number of steps that are usually repeated manually and formalizing them. Workflows can be useful in Modeling and Simulation (M&S) for several reasons. The first one is that they allow building a blueprint of the simulation experiment, ensuring its replayability. The second one is that they allow building a simulation experiment independent from the simulation environment [START_REF] Ribault | Using workflows and web services to manage simulation studies (WIP)[END_REF]. The Workflow Management Coalition (WMC) standard group (WMC 2009) proposes a WF reference model in which the WF is in the centre and interacts with other surrounding applications or WF components.

Several surveys have compared different workflow management systems. In [START_REF] Ewa | Workflows and e-Science: An overview of workflow system features and capabilities[END_REF], the authors analyzed and classified the functionality of workflow system based on the needs of scientists who use them. In [START_REF] Yu | A taxonomy of workflow management systems for grid computing[END_REF], the authors focused on the features to access distributed resources. In [START_REF] Curcin | Scientific workflow systems can one size fit all? Biomedical Engineering Conference[END_REF], four of the most popular scientific systems were reviewed. We can abstract from the literature that:

 Kepler [Altintas et al., 2004;Lud¨ ascher et al., 2006] is a scientific workflow system with a graphical interface to create, execute and share workflows. Inputs and outputs are typed, which allows to validate semantically the workflow prior to execution. Kepler uses an archive format for sharing workflows, and a repository. Kepler can invoke a web service through a dedicated actor, and broadcast the response through its output port.

 Triana [Churches et al., 2006] is a problem solving environment with a graphical interface to create and execute workflows. Workflows are data-driven, and special elements enable branching, parallelism and looping. Triana uses scripts to control sub-workflows and it can invoke web services.

 Taverna [START_REF] Hull | Taverna: a tool for building and running workflows of services[END_REF]] is a workflow management system dedicated to the integration of services.

Taverna has a graphical interface for the creation, execution and sharing of workflows. Taverna is interfaced with the myExperiment service [START_REF] Goble | myExperiment: social networking for workflow-using e-scientists[END_REF] to share workflows.

 Worms [START_REF] Stefan | Worms-a framework to support workflows in m&s[END_REF] is a flexible and extensible workflow system dedicated to M&S. It is plug-inbased which offers the possibility to extend its features. Worms also comes with its own workflow repository.

In [START_REF] P R E P R I N T Missier Tan | Building scientific workflow with taverna and bpel: A comparative study in cagrid[END_REF], the authors compare the service discovery, service composition, workflow execution, and workflow result analysis between BPEL and a workflow management system (Taverna) in the use of scientific workflows. They determine that Taverna provides a more compact set of primitives than BPEL and a functional P r e P r i n t

programming model that eases data flow modelling.

We decided to use Taverna to demonstrate the feasibility of our methodology because Taverna eases the interoperability with other services.

Taverna

Taverna [START_REF] Hull | Taverna: a tool for building and running workflows of services[END_REF]] is an application that facilitates the use and integration of a number of tools and databases available on the web, in particular Web services. It allows users who are not necessarily programmers to design, execute, and share WFs. These WFs can integrate many different resources in a single experiment.

Taverna WF can contain services including:

 A service capable of running Java code directly within Taverna.

 A service to run a remote application via the REST protocol.

 A service to run a remote application via the SOAP/WSDL protocol.

A Taverna service can take inputs and produce outputs. The value of an entry can be part of the WF (hardcoded) or a parameter to provide information during the execution of the WF. Taverna offers the possibility to automatically format the input and output based on the type of parameters required by the service.

WFs are particularly suited to automate experiments, but all necessary parameters cannot always be specified in advance. In these cases, it is desirable to interact with users for decision making. Taverna offers several graphical interfaces for interacting with the user.

A Taverna WF can also contain nested WFs in a hierarchical manner. In this way, a set of simple WFs easily allows to design more complex WFs. These WFs can then be shared, reused, and adapted to new needs.

CONTRIBUTION

We propose to use WF of services as the interoperability layer among several services. In addition, we propose to integrate the G-DEVS/HLA engine as a specific WF engine. G-DEVS is a formalism based on a state machine automaton. WFs differ from state machines as state machine can be cyclic graphs while WFs are usually acyclic. WF proceeds down different branches until done. Thus, using G-DEVS coupled to another WF engine to process a WF could benefit from the DEVS formalism while keeping the top to bottom behaviour of the main WF manager. Interoperability between WF engines and applications are done using web services.

Workflow Orchestration Architecture

The Figure 2: Workflow global orchestration architecture.Figure 2 presents the proposed orchestration architecture that P r e P r i n t

G-DEVS/HLA Workflow Model

In previous work [START_REF] Zacharewicz | G-DEVS/HLA Environment for Distributed Simulations of Workflows[END_REF], several G-DEVS models have been already coupled thanks to a HLA connection. The idea was to establish distributed simulation for G-DEVS Models but also to open G-DEVS to interoperability with other software components.

In the PRODIGE platform project [START_REF] Zacharewicz | Distributed platform for advanced freight transportation systems[END_REF] the main components of a transport and logistic system that interact in a WF have been specified using G-DEVS models. The goal was to study the hardware and human behaviour and to test their dialog with the platform. For instance smartphone behaviour has been formalized. The behaviour of the smartphone was to take into account hardware delay due to 3G or Edge bandwidth during communication between the platform and users. In addition the driver responsiveness with its environment and the truck movement were also simulated. In this approach the simulation synchronization was given by an HLA RTI.

In [START_REF] Tu | Building a high-level architecture federated interoperable framework from legacy information systems[END_REF], the Portico RTI has been used to facilitate the connection between RTI and the calls to web services. This RTI has been reused in our work.

We propose the use of the GDEVS/HLA interoperability with other software components and propose to couple it with the Taverna tool. The Figure 3 focuses on the proposed WF simulation architecture (regarding Figure 2 it zooms on Taverna, RTI and G-DEVS). The HLA RTI becomes the information scheduler and the clock leader of the simulation.

More details are provided in the next section.

Figure 3 Workflow Simulation main components view

G-DEVS/HLA, Clock and Message Sorting

In this paper the functional interoperability with web service dealers is mainly assumed by the Taverna engine that calls the services and links the different applications. Taverna allows defining a sequence of service calls. Nevertheless this tool (as most service WF builder/runner) does not allow defining the time constraints (that exists in real situation) in the sequence and does not provide time synchronization for the simulation of services calls in a defined sequence. For instance, the access to a data base too early or too late can be a problem, i.e. with obsolete values or too recent values.

This problem can arise when parallel process is executed. To address this issue, two options have been considered.

On the one hand, using a Run Time Infrastructure tool (RTI) to build an HLA federation as used in [Al-Zoubi and Wainer, 2010a]. This option requires the use of a systematic and direct connection of all components to the RTI. This set-P r e P r i n t up, with RTI as a mediator of all messages exchanged, can be interesting from the interoperability point of view can cause overheads and slow down the communication like discussed earlier in [Al-Zoubi and Wainer, 2010b].

On the other hand, the idea proposed in this research is to use the Taverna WF interoperability facility as the main interoperability layer between services (including applications and simulations). It is executing the main scenario script.

In addition we propose to use a G-DEVS/HLA to be the time based message scheduler for the WF scenario. In that case the use of the RTI is not systematic; it is only solicited when the WF is communicating with a simulated component. On demand, the RTI and the GDEVS model are playing the behaviour of the simulated component with time spent achieving an action in order to reproduce real time reaction delay. [START_REF] Zacharewicz | Distributed platform for advanced freight transportation systems[END_REF] and [START_REF] Tu | Building a high-level architecture federated interoperable framework from legacy information systems[END_REF] already uses G-DEVS models and HLA RTI simulators to simulate the behaviour of several components by mixing HLA and web services in a previous study. The distributed simulation principle of [START_REF] Tu | Building a high-level architecture federated interoperable framework from legacy information systems[END_REF] is based on the original pessimistic algorithm described in [Chandy and Misra, 1979], but adding recent advances on lookahead described in [START_REF] Zacharewicz | G-DEVS/HLA Environment for Distributed Simulations of Workflows[END_REF]. The RTI is defining the ordering of the actions regarding their occurrence time. It stores the information before releasing them regarding the scenario definition played in Taverna. It can be also considered as the script clock and blocker/releaser of the simulation. Regarding time synchronisation, the GDEVS/HLA models are already prepared since [START_REF] Zacharewicz | G-DEVS/HLA Environment for Distributed Simulations of Workflows[END_REF] to inform the RTI about their Lower Bound on Time Stamps (LBTS) [IEEE, 2000] to compute the Lookahead (minimal treatment delay) and unblock the simulation. Taverna was not defined for that. The idea has been to define minimum treatment duration in each workflow step to be communicated to the RTI. Thanks to this information taken by the RTI as the Taverna LBTS, the distributed simulation can be run without deadlocks.

In detail, this paper proposes that the RTI collects simulation messages, sorts them and triggers the services call right in time to the applications or forwarding the message to the G-DEVS models that simulate the behaviour of the WF components according to defined scenario, i.e. a timed sequence of service calls. This model can receive messages both from the server as a service answer or from a G-DEVS model that sends an output message as a simulation result of a local behaviour. The messages received from the server are service answers. They possess time stamp information to be used by the RTI to add the message at the right place in the queue. Then depending on the execution state of the global clock it will sort the message and direct it to the proper receiver. The RTI status can be treating a message or be available. In the first case, the approach is inspired from the conservative algorithm of [Chandy and Misra, 1979]. It is based on the G-DEVS/HLA algorithm, proposed in [START_REF] Zacharewicz | G-DEVS/HLA Environment for Distributed Simulations of Workflows[END_REF], in particular if a message arrives late. The message temporary blocks the simulation and will not be ignored. Then simulation is unblocked when it passes to process the next message, it shows the interest of providing an accurate value of LBTS to the RTI. The receiver can be a web server trough Taverna. In that case it prepares an output message. This output message is addressed to Taverna that P r e P r i n t transforms it to service call and then triggers the web service server. If the message is addressed to a G-DEVS model to trigger component behaviour, the message is sent through the RTI to the appropriate G-DEVS component using the coupled model structure. In the second case (no input event to be treated) the RTI is waiting inputs.

GDEVS/HLA Taverna Interoperability

The interoperability between G-DEVS model and web applications, ensured by Taverna WF plus the HLA RTI, is concretely tested in this section. The Figure 4 The sequence is expressed as follow:

1. The Taverna WF model 1 instantiate and ask the GDEVS clock model to be woken-up at 8:45.

2. The Taverna WF model 2 instantiate and ask the GDEVS clock model to be wock-up at 8:30.

3. The clock model wake-up the Taverna WF model 2; time = 8:30.

4. The Taverna WF model 2 invokes the "setResources" service on the application and then ask the GDEVS clock to be woken-up at 10:00

5. The clock model wake-up the Taverna WF model 1; time = 8:45.

6. The Taverna WF model 1 invokes the "getResources" service on the application and then ask the GDEVS clock to be woken-up at 10:15 P r e P r i n t This interoperability provided by Taverna and HLA allowed us to schedule independent WF running in parallel. In the next section, we experiment interoperability in a real case study through the PRODIGE project.

EXPERIMENTATION

The contribution presented in section 3 is applied to the product transportation use case through the PRODIGE Project.

We will present the PRODIGE Project, the use case scenario and finally the experimentation framework.

PRODIGE Project context

The PRODIGE project aims to prepare the future of physical products transportation, placing the reflection at the organizational level that controls the flow of merchandises in order to provide a technical and organizational solution helping the reduction of the travelled distance, optimization of the tours and transported volumes and taking into account new issues related to sustainable development.

The base of the work, proposed in this paper, starts from a transportation Web application released in the project. This P r e P r i n t

platform is composed of a server where several truck users are remotely contacted to display their positions thanks to GPS and GSM communication. The server is offers an algorithm to optimize truck routing. It exposes its methods through the use of SOAP Web services in order to promote interoperability (set a tour, view the results, etc.). The idea is to test the function of the PRODIGE platform regarding a sequence of dynamic calls. For this purpose, a simulation tool making the WF alive is required in order not to launch all the trucks on the roads for each test.

A scenario in PRODIGE can have several objectives:

 Quantitative: calculating and comparing several variables such as the number of kilometres travelled by products or the amount of CO2 emissions produced for a set of deliveries  Qualitative: following the different steps of the delivery of a product (e.g. respect of delivery times, compliance with cold chain, etc.)

 Analytics: observing a special non understood case, difficult or impossible to reproduce with the real system, mainly for scientific purposes.

In this objective, demonstration scenarios are added, to explain PRODIGE to public audience and to follow graphically the movement of vehicles depending on the scenario chosen.

Use case scenario

The PRODIGE platform is easy to setup (a server connected to internet to provide SOAP services), but it's very expensive to rent a truck and a driver. We decided to simulate the driver/truck and setup a real PRODIGE platform. We propose a simple scenario case to illustrate the simulation of truck, driver, and smartphone regarding the global system.

Earlier in the day, the driver connects to the PRODIGE platform and retrieves information about the tour he was assigned. He leaves the deposit and drive to the first client. He loads the goods then leads to the second client where he will unload the goods. Finally, he returns to the depot at the end of the tour. For each step described above, there is some communication with the PRODIGE platform to ensure traceability and reactivity of the PRODIGE platform. To test this scenario, we need to setup the PRODIGE platform and drive a truck across 2 destinations. The behaviour of the driver/truck can be formalized in a WF which would pass itself for a real truck to the PRODIGE platform. To send GPS tracking data to the PRODIGE server, the WF uses Google Map1 services to get the direction from a place to another.

Then, we can get GPS coordinates of every little part of the road. The WF, like the real application embedded in a truck, sends a couple of GPS coordinates every 30 seconds to the PRODIGE platform and information about load and unload.

P r e P r i n t

At this point, we have a basic scenario involving only one truck and executing in real-time. This means that a delivery from Bordeaux to Paris will take 5 hours.

Authors introduce the main contribution of the paper by using the G-DEVS "clock" model presented in section 3; we can synchronize the logistic WF with virtual time. That means a delivery from Bordeaux to Paris will take few minutes.

Every 30 seconds in virtual time, the WF sends GPS coordinates (which include timestamp) to the PRODIGE platform.

The PRODIGE platform can then display the tour exactly as if it had taken 5 hours thanks to the timestamp embedded with the GPS coordinates, e.g. departure from Bordeaux at 8:00 AM and arrival in Paris at 1:00PM.

From now on, we can create an advanced scenario involving several drivers/trucks. Each driver/truck is represented by a new WF instance, which keeps the WF very simple. WFs instances run in parallel and are synchronized thanks to the G-DEVS clock model. This use case demonstrates the benefits from mixing WF and simulation and how WF of services like Taverna can handle interoperability between application services and simulation.

We created several data input sets as well as several WFs to simulate different situations to experiment the PRODIGE solution before putting it on the market. Packages must be picked up and delivered regarding the two following situations:

 The delivery time windows are wide enough for it to be feasible with a single truck.

 The delivery time windows overlap and several trucks are needed to make the delivery on time.

Those two situations are done using the same generic WFs. We built another WF to take into account hazards such as traffic jams or a breakdown. Indeed, in those cases the WF must take into account specific decision that could involve creating new delivery.

Experimentation Framework

We have implemented the architecture and concept described in the previous sections. At simulation time, during transition due to message treatment by the G-DEVS models, an output message from Taverna is frequently generated in order to give the order to refresh the positioning of the trucks and product to the server P r e P r i n t according to the roadmap and geographical information extracted from Google maps. During the setting of the simulation the pace can be tuned in order to accelerate the simulation execution. Also, at any simulation time the execution can be stopped to show a particular case. P r e P r i n t

  that defines the simulation semantics of the formalism. The architecture of the simulator is derived from the hierarchical model structure. Processors involved in a hierarchical simulation are: Simulators, which implement the simulation of atomic models; Coordinators, which implement the routing of messages between coupled models; and the Root Coordinator, which implement global simulation management. The simulation runs by sending different kind of messages between components. The specificity of G-DEVS model simulation is that the definition of an event is a list of coefficient values as opposed to a unique value in DEVS. Zacharewicz et al. proposed in [Zacharewicz et al., 2008], an environment, named DEVS Model Editor (LSIS_DME), to create G-DEVS models that are HLA compliant and simulating them in a distributed fashion. In LSIS_DME, a G-DEVS model structure can be split into federate component models in order to build a HLA federation (i.e. a distributed G-DEVS coupled model). The environment maps DEVS Local Coordinator and Simulators into HLA federates and it maps Root Coordinator into RTI. Thus, the "global distributed" model (i.e. the federation) is composed of federates intercommunicating.

  is based on the WF architecture introduced by the WfMC [WfMC 99] and [WFMC 05] . We detail in the following the specific architecture tailored to "timed" WF.

Figure 2 :

 2 Figure 2: Workflow global orchestration architecture. We propose to use Taverna and G-DEVS/HLA as the process definition formalism to express WFs. Taverna WF represents the main WF that organizes all tasks and enables interoperability between services. Taverna WF process definition will be executed by the Taverna Engine (Interface 1). G-DEVS model will be executed by the G-DEVS Engine (Interface 1') as another WF enactment services. Communication between both engines (Interface 4) will be garanteed by HLA/RTI. Taverna interprets G-DEVS WF events through HLA based Interface 4 and enables the interoperability with other services using RESTful or SOAP/WSDL Web services protocols through Interface 3 and with users through the use of the Taverna Desktop through Interface 2.

  presents the sequence diagram among 2 Taverna WFs, a generic G-DEVS model entitled "Clock", used to represent a basic time dependent behavioural model; the HLA communication and an application. Taverna WFs represent 2 experimentations executed in parallel to test the application. The G-DEVS model represents the clock scheduling and is waiting for 2 Taverna instances ("nb=2").

Figure 4

 4 Figure 4 Interoperability sequence diagram.

  Figure 5 represents the solution framework. The virtual experiment is defined using Taverna WF and G-DEVS simulation. The Taverna WF mimics the behaviour of managers, clients and drivers while the G-DEVS simulation act as a WF scheduler. Communication between Taverna and G-DEVS are done through HLA RTI. The Taverna WF communicates with the PRODIGE application and Google Maps through Web service. The real experiment needs people to manage the PRODIGE application (manager, clients) and drive the trucks (drivers). Communication between people and PRODIGE is done using a light web application (manager, client) or a mobile application on smart device (driver).

Figure 5

 5 Figure 5 PRODIGE and simulation framework architecture.The Taverna WF plays the role of each actor (manager, clients, and drivers) and interacts with the PRODIGE platform.Several WF instances are executed in parallel for each driver involved. The WF retrieves the information needed on the PRODIGE platform, on Google Maps and using G-DEVS clock model to mimic the behaviour of a real truck. The result of the execution of this WF is directly visible in the PRODIGE web application on which you can view the current path of a truck making its tour in the Bordeaux area (France), as shown on Figure6.

Figure

  Figure 6 PRODIGE Web application.

http://maps.google.com


Pierre Aboussouan

Olivier Alibart

Daniel B Ostrowsky

Pascal Baldi

Sébastien Tanzilli

Near-perfect two-photon interference at a telecom wavelength using picosecond regime separated sources

Keywords: numbers: 03.67.-a, 03.67.Bg, 03.67.Dd, 42.50.Ex, 42.50.Dv Quantum Communication, Two-photon interference, Guided-wave Optics

We report on a two-photon interference experiment in a quantum relay configuration for long distance quantum communication at a telecom wavelength. In contrast to already reported regimes, namely femtosecond and CW, we propose for the first time to employ the picosecond regime which allows achieving a near-perfect visibility two-photon interference using only standard telecom components and detectors. Our experiment is based on two photons at 1550 nm emitted by two separate PPLN waveguides. We show a net interference visibility of 99% which clearly proves the very high potential of our experimental scheme to achieve quantum networking applications in real conditions.

In this paper, we demonstrate that the picosecond regime of operation associated with a guided-wave scheme should have important repercussions for quantum relay implementations, essential for improving both the working distances and the efficiency of quantum cryptography and networking systems [START_REF] Gisin | [END_REF]2].

At the end of the 70's, physicists started to develop entanglement based quantum experiments for testing the completeness of quantum theory [3]. They soon realized that quantum physics could be strongly related to information theory, and introduced the notion of quantum bits (qubits) as superpositions of |0 and |1 states associated with any two dimensional quantum system observable. Currently, single and pairs of entangled qubits are seen as resources for quantum information and communication protocols, among which quantum key distribution is seen as a major application [START_REF] Gisin | [END_REF]. The experimental potential of quantum communication, i.e. dealing with qubits encoded on photons, relies on the ability to generate, distribute, and manipulate qubits. In this context, teleportation of single qubits [4] and entanglement swapping between pairs of qubits [5][6][7][8] are practical examples.

Photon coalescence lies at the very heart of these quantum operations and is seen as a first step towards achieving both teleportation and entanglement swapping. This effect has been extensively studied both theoretically [9,10] and experimentally, initially based on two photons coming from a single downconversion source and therefore sharing both a common past and clock [11]. However, experiments involving truly independent photons represent an important challenge in quantum communication since this is the key to achieving longer quantum links by means of quantum relays based on teleportation or entanglement swapping schemes [2,[6][7][8]12]. Such achievements appear to be much more difficult since a perfect synchronization between the related sources is necessary to prevent from any kind of distinguishability. Unfortunately, beyond the fundamental interest of these previous demonstrations, the reported interference visibilities remain far from the near 100% needed for practical implementations [13]. For these experiments, the reduced visibilities are always associated with partial distinguishability due to the operating regimes, namely femtosecond or CW, placing highly stringent constraints on both the employed material and components.

Here, we demonstrate for the first time why the picosecond regime provides an efficient trade-off permitting the attainment of a near-perfect two-photon interference visibility, while using standard components available from the telecommunications industry. We realized a guided-wave optics experiment based on two periodically poled lithium niobate (PPLN) waveguides emitting photons around 1550 nm and report the highest two-photon interference visibility, i.e. of 99%, ever demonstrated in a quantum relay configuration. This emphasizes why guided-wave technology and the use of the picosecond regime should lead to realistic quantum relay schemes. In the following, we shall first introduce the quantum relay principle and discuss why the picosecond regime is a valuable trade-off. We then focus on our picosecond regime demonstration. Finally, we detail a comparative study of performance with similar reported experiments.

When considering long distance quantum communications, the preferred qubit carriers are photons at 1550 nm allowing the users, namely Alice and Bob, to use optical fibers for distribution purpose. However, even if telecom fibers show propagation losses as low as 0.2 dB/km at 1550 nm, ultimately, dark counts in the detectors limit both the signal-to-noise ratio (SNR) and the maximum achievable distance. The quantum relay function, based on quantum state teleportation, allows partially overcoming this problem [2]. Teleportation success is indeed validated by the emission of an electrical signal which is eventually used as a trigger for Alice and Bob's detectors. It therefore reduces the overall channel noise by turning on the detectors only when the probability of having a pair of qubits available at Alice and Bob locations is high.

A basic scheme of a quantum communication link in the entanglement swapping relay configuration is shown in FIG. 1. In this figure, two properly synchronized sources (EPR) produce two photon pairs, one at each source. Sending the two inner photons that share no common past to the BS projects them onto an entangled state thanks to a Bell state measurement stage (BSM). Using a dedicated detection, entanglement can be swapped from these photons to the outer ones making Alice and Bob connected by entanglement, as if they had received each one photon from an entangled pair directly. In terms of SNR, we see in FIG. 1 that Alice and Bob photons have actually travelled only one half of the total distance, the other half being covered by the two inner photons which give rise to a heralding signal when entanglement swapping is succesful. Thus, two-photon interference is a means to entangle independent photons and to connect two remote locations by such a quantum operation. Note that for quantum networking applications, it has been demonstrated theoretically in Ref. [13] that a two-photon interference net visibility of at least 95% is required for practical implementations using currently available photon pair sources and multimode quantum memories.

FIG. 1: Schematics of a quantum relay involving two pairs of entangled photons emitted synchronously. After separation of the pairs, the two inner photons are sent onto a BS where a joint-measurement, or Bell state measurement (BSM) which is based on two-photon interference, is performed. This results in projecting these two photons onto an entangled state, and, accordingly, the outer ones onto the same state. The two inner photons detection is used as a heralding signal of a successful entanglement swapping. The filtering stages in each sources is necessary to prevent any distinguishability.

Theoretically, the photons can come from any type of source, provided they are identical before the BS (preselection) or before the detectors (post-selection). In any case, synchronizing the two EPR sources is of great importance to prevent any kind of distinguishability.

Synchronization essentially depends on the pump laser regime employed in the EPR sources and is also strongly related to the filtering stages placed on the path of the emitted paired photons. From the experimental side, this two-fold issue amounts to the need of erasing any temporal distinguishability between the two interfering photons. Here, we have to compare the coherence time, τ coh , of these two photons to the time uncertainty, t uncert within which they are created (i.e. the pulse duration of the pump laser(s)) or are detected (detector's timing jitters), which can be written as:

τ coh ≥ t uncert (1)
Suitable bandpass filters are therefore employed to achieve optimal interference visibilities. Up to now, this issue has been addressed using different approaches based on pulsed or CW lasers (see also Table I for comparison).

On the one hand, the first experiments reported two independent crystals pumped by a single laser operating in the femtosecond regime [5]. The reason for this lies in the fact that this regime allows operating with broadband filters, i.e. on the order of a few nm. However, the large photon bandwidths makes them more prone to chromatic or polarisation dispersions and leads to reported visibilities below 85% when the photons travel in optical fibers. When two independent lasers are used, one has to take into account the synchronization difficulty since the two related laser cavities have to be driven so as to be identical within the pump pulse duration, which is usually on the order of 100 fs [6,7]. Additional efforts have therefore to be provided to actively drive the two laser cavities together using phase-locked loops or atomic clocks and dedicated electronics [14,[START_REF] Cundiff | Selected Topics in Quantum Electronics[END_REF]. Any remaining jitter between the two lasers will have to be compensated by narrowing the filters which implies a substantial reduction of the pair production rate for equivalent powers.

On the other hand, the development of narrowbandwidth fiber Bragg grating (FBG) filters allows using two independent CW lasers stabilized against an atomic transition. Since the CW regime does not provide any reference clock, the timing function is transferred to the coincidence detection after the BS. To ensure a high quality interference, the photons have to show a coherence time longer than the jitter of the employed detectors. Experimentally, entanglement swapping is made possible using a suitable combination of low-jitter detectors (based on superconducting or up-conversion technologies), on the order of 70 ps, associated with ultra-narrow FBG filter bandwidths, on the order of 10 pm [8,16]. In such a situation, one gets rid of the synchronisation but the price to pay is rather high in terms of sensitive fluctuations of the filters central wavelengths, low experimental rates due to the narrow filters coupled to the randomness of entangling photons coincidence detection, and rather high statistical fluctuations due to low count rates. All these features prevent reaching high visibilities.

Between these two extremes, the picosecond regime appears to be an efficient compromise. First, the timing condition (1) is easily met by using FBG filters showing much larger bandwidths than in CW, i.e. on the order of 100 pm [12]. In addition to the FBGs, this also allows taking advantage of off-the-shelf telecommunications components, such as standard InGaAs avalanche photodiodes (APD), optical circulators, and 50/50 couplers. Eventually, synchronizing two picosecond lasers is a much easier task compared to synchronizing two femtosecond lasers. Note that synchronization up to 1 ps can be achieved by simply distributing a common clock by means of a standard telecom pulsed laser between Alice and Bob. All these features should permit the implementation of realistic quantum relays.

As shown in FIG. 2, our experiment is based on two of our PPLN waveguides, known for their high efficiency and easy handling [8,18]. They are pumped by a picosecond laser at 768 nm and both designed to produce identical degenerate paired photons at 1536 nm within a bandwidth of 50 nm (spectrum not represented). The pump laser is first sent to a BS whose outputs are directed towards two PPLN guides. From each source, we select pairs of photons meeting the Fourier transform criterion using narrowband demultiplexers made of two optical circulators and a pair of FBG filters. These are set to reflect energy-matched pairs of wavelength at 1537 nm and 1535 nm, associated with bandwidths of 800 pm and 250 pm, respectively. A slightly wider (800 pm) filter is used on the long wavelength (1537 nm) photons mainly to minimise losses. This filtering solution based on standard telecom components provides a simple way to separate the photons at the output of the waveguides and makes them each available in a single mode fiber [8]. We have estimated the 250 pm filter bandwidths to accomodate the 1.2 ps-width of the laser pulses and any possible jitter due to laser synchronization up to 4 ps. However, as in Refs. [5,12], we used a single laser which is sufficient for a proof-of-principle demonstration. Regarding this, the two lasers in Ref. [6] are not truly independent since they share the same Ti:Sapphire crystal Kerr medium for precise synchronization. To observe the two-photon interference, the four-fold coincidences are detected thanks to four InGaAs-APDs triggered with the laser clock. The evolution of the effective five-fold coincidence rate is given in FIG. 3 in which a remarkable dip is obtained when the delay between the two inner photons is zero.

Using 1 mW of pump power per source, we obtained 4 × 10 3 coincidences per hour per source which corresponds in term of normalized rate to 1.6 × 10 3 pairs•s -1 •pm -1 •mW -1 . When the two photons are made indistinguishable in time (δt) thanks to the adjustment of the retro-reflector (R) and spectral modes, a 93% ± 3% reduction in the raw five-fold coincidence count rate is obtained. Moreover, the net five-fold coincidence count rate, i.e. when the accidental coincidences are subtracted, reaches 99% ± 3%. The width at half the height of the dip is approximately ∆τ =11 ps, which is well in agreement with the coherence time of 14 ps associated to our filtering stages. This interference visibility is extremely close to the maximum value of 99.9% that can be obtained from theory taking into account our filtering bandwidths, as properly outlined in Refs. [10,17,[START_REF] Rarity | Fundamental Problems in Quantum Theory[END_REF]. FIG. 3: Five-fold coincidence rate as a function of the relative delay, δt, between the interfering photons. We clearly observe a dip for δt = 0 that reaches the noise level. The Gaussian fit of the interference pattern shows a net visibility of 99% ± 3%.

We also plotted one of the average single count rates.

Table I presents the results reported in the literature. From the experimental point of view, all the different configurations can be summarized in four key points: (i) the type of nonlinear generators, (ii) the emitted photon wavelengths, (iii) the pumping regime and its associated time uncertainty, (iv) and, finally, the applied filtering bandwidths and their associated coherence times. From a comparison of all the reported configurations, it appears that the combination of the picosecond regime and the single mode properties of the employed telecom components is the most performant scheme. It allows matching efficiently the inequality (1) and obtain-TABLE I: Compared two-photon interference visibilities, source's brightness, and whole experimental coincidence rates, between reported works in continuous wave (CW), picosecond (ps), and femtosecond (fs) regimes. Regarding time uncertainties, note that the first number is always associated with the pulse duration while the ± sign corresponds to the synchronisation jitter if two pulsed lasers are involved. In contrast, the time uncertainty for the CW case is associated with the detector's timing jitters. The coherence time is calculated for Gaussian filters using the standard relation τc = 0.44 λ 2 c∆λ . Here, the net visibility is given after subtraction of the accidentals originiated by the detectors dark counts. a In this column, the figures associated with the pump regimes correspond to the number of employed lasers.

Reference

b The net visibility is given after subtraction of the accidentals initiated by the detectors noise.

ing near-perfect two-photon interference. For practical long distance quantum communication, it is also interesting to compare the rates in terms of effective number of created pairs per second Alice and Bob actually receive. This figure of merit is calculated by normalizing the four-fold coincidence rates with respect to Alice and Bob detectors efficiency. A comparison with similar entanglement swapping configurations at telecom wavelengths indicates that the picosecond regime allows maintaining a high effective pair production rate equivalent to the femtosecond regime but shows a much higher visibility. One should note the two orders of magnitude rate difference for equivalent source technologies and brightness between the CW and picosecond regimes.

The results demonstrated in this experiment are of broad interest since the obtained net visibility is the best value reported to date for competing configurations. According to reference [13], this allows considering for the first time the possibility to use quantum relays in actual quantum cryptography networks. In this context, where two synchronized lasers would be used, we expect results of the same order due to easy picosecond synchronization and well-fitted filter bandwidths.

FIG. 2 :

 2 FIG. 2: Coalescence experiment based on two PPLN waveguides pumped by a single picosecond laser (λp = 768 nm, ∆λp = 0.25 nm, Coherent MIRA 900-D) which provides 1.2 ps duration, Fourier-transform limited, pulses, at a repetition rate of 76 MHz. A very weak part of this beam is sent to a silicon APD (not represented) whose output serves as the laser clock to trigger four InGaAs-APDs (id-Quantique 201). Λ: poling period of the PPLN waveguides; I: isolator; R: retroreflector; C: circulator; &: AND-gate.

The authors would like to thank M. P. de Micheli and S. Tascu for the realization of the PPLN waveguides, G. Sauder for technical support, and A. Beveratos, H. Zbinden, and K. Thyagarajan for fruitful discussions. This work has been supported by the CNRS and the University of Nice -Sophia Antipolis. P. Aboussouan thanks the French "Ministère de l'Enseignement Supérieur et de la Recherche" for its support through a Ph-D grant.


Cheikh A T C Ndiaye

Ndeye Fatou Ngom
email: ndefangom@gmail.com

Niang Oumar
email: niangom@yahoo.fr

Cheikh H T Chérif Ndiaye * -Ndèye

Fatou Ngom
email: fngom@ept.sn

-Oumar Niang

Computational geometry and GIS for digital terrain modeling

Keywords: Géométrie algorithmique, triangulation de delaunay, modélisation urbaine, modélisation numérique de terrain, simulation d'écoulement computational geometry, delaunay triangulation, urban modeling, digital terrain model, flood simulation

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Geographic information Science (GIS) is a multi-disciplinary area with contributions mainly coming from the spatial sciences (geodesy, geography, cartography), computer science (databases, artificial intelligence and computational geometry) and applied science (spatial planning, archeology, geology, civil engineering and biology). Thus, a substantial part of all activities performed by a GIS involves computing with the geometric data (such as location, shape, proximity, and spatial distribution) which calls for efficient methods to store, manipulate, analyze, and display such amounts of data [START_REF] Van-Oosterom P | Geo-information and computational geometry[END_REF]. In the past, the importance of the data geometric aspects was often underestimated and the proposed solutions often suffered from lack of foundations, both from a geometric point of view (e.g the result of an operation defined just as the output of a certain algorithm) and from a computer science perspective [START_REF] Magilo | Application of computational geometry to geographic information system[END_REF]. The needs for a solid theorical background and for high performance reasoning make the field of GIS an interesting source of problems to work on for computational geometers. Computational geometry is about the design and analysis of algorithms for geometric problems. The success of the field as research discipline can on the one hand be explained from the beauty of the problems studied and the solutions obtained, and on the other hand, by the many application domains (computer graphics, geographic information system, vision, path planning, image processing) where geometric algorithms play a fundamental role [START_REF] Mark De Berg | Computational Geometry : Algorithms and application[END_REF].

This paper first reviews issues concerning GIS and computational geometry in order to improve the understanding of the diversity of the possible interactions between computational geometry and GIS and application to terrain modeling and simulation. Indeed, real time hydrological processes simulation relies on spatial distribution representing discretization of representative terrain maps. Triangular network is typically the basis of such discretization. Thus some preprocessing become relevant, before running any simulation on the discretized space, to get a more realistic physical representation taking into account topological, geometrical and morphometric properties. Among other issues to be addressed is the need to get a mesh representation which can enable to enhance the computation of surface flows in hydrologic and digital terrain models. The issues related with GIS and computational geometry is presented. The aim is to improve the understanding of the diversity of the possible interactions of the two fields. Then we project application for urban modeling. This applications includes three main processing stages. The first stage deals with the construction of a geometric terrain representation based on Delaunay Triangulation. In this stage, theorical backgroud for flood simulation based on the Delaunay decomposition is proposed. The second stage copes with the urban area modeling including a step of building modeling process.

Section 2 discusses geographic information systems issues. Section 3 presents computational geometry tools that can be used in GIS. Section 4 introduces techniques and tools to generate digital terrain model based on irregular triangular networks. We propose a method of generating DTM based on Delaunay triangulation and java graphics 3d libraries. Section 5 proposes a coupled hydrological and digital elevation model for flood simulation. Conceptual principles and schematic processing steps are given. Section 6 presents 1. CNRIA '15 an urban model integrating the creation of building which has impact on the water flow. Conclusion and futures works are given in section 7 .

GEOGRAPHY INFORMATION SYSTEM (GIS)

A geographic information system (GIS) can be seen as a system of hardware, software and procedures designed to support the capture, management, analysis, modeling and display of spatially referenced data for solving complex planning and management problems. The main issues adressed are related to geometric primitive, data models and terrain analysis.

1) Geometrics primitives

Terrain modeling never ceased to evolve gradually with the development of representation techniques. Indeed, construction of terrain involves conversion among geometrics primitives such as points, lines, triangular surfaces and parametric curve and surface. The resulting parametric surfaces allows modeling complicated objects. There are two types of curves and surfaces -Interpolating curves and surfaces, including all points of controls in the curve (curve Catmull-Rom and Coons surfaces) [START_REF] Magilo | Application of computational geometry to geographic information system[END_REF].

-Curves and surfaces approximation : that does not necessarily pass by all points of controls but rather close to them (Bezier, B-Splines, β-Splines) [START_REF] Magilo | Application of computational geometry to geographic information system[END_REF].

Illustrations of parametric curves and surfaces are given by Figure 1 and Figure 2.

2) Cubic parametric curves

A cubic parametric curve is defined by,

Q (t) = (x (t) , y (t) , z (t)) , t ∈ R [1] x(t) = a x t 3 + b x t 2 + c x t + d x y(t) = a y t 3 + b y t 2 + c y t + d y z(t) = a z t 3 + b z t 2 + c z t + d z If t belong to [0.0, 1.0], then Q(t) = (x(t), y(t), z(t)) = T.C where C =     a x a y a z b x b y b z c x c y c z d x d y d z     and T = (t 3 , t 2 , t, 1) [2]
The matrix C can be transformed into a matrix M called basic matrix and a column vector G of four geometrics constraints called vector geometry [START_REF] Magilo | Application of computational geometry to geographic information system[END_REF]. 3) Cubic parametric surfaces

Q(t) = (x(t),y(t),z(t))= T.C= T.M.G = (t
        g 1 x g 1 y g 1 z g 2 x g 2 y g 2 z g 3 x g 3 y g 3 z g 4 x g 4 y g 4 z     [3]
The cubic parametric surfaces are generalization of cubic parametric curves. They are defined from a set of control points which is called mesh tiles or patches [START_REF] Wafia Boubguira | Modélisation numérique de terrain : Etude de Synthèse et Application[END_REF]. Parametric surface is defined by the the following equation, t ∈ [0, 1]

Q(t) = S.M.G(t)whereG(t) =     G 1 (t) G 2 (t) G 3 (t) G 4 (t)     [4]
The G i are cubic and are defined as follow

G i (t) = (T.M .P i )withP i = (P i1 , P i2 , P i3 , P i4 ) T As each P ij is a control point of G i (t), then Q(s,t) = S.M.G(t) = S.
    [5]
Figure 2 illustrates an example of Bezier surface computed from a set of control poins. Figure 3 shows the smooth appearance of different representation of the surface. However, real terrain is far having a smooth and polished appearance and the necessary calculation time which appears to be relatively high.

4) Data models and structures

There are basically three ways to store data : raster model, vector model and digital elevation model. The raster representation is a space oriented representation : the domain is [START_REF] Wafia Boubguira | Modélisation numérique de terrain : Etude de Synthèse et Application[END_REF] subdivided in atomic regions similar to the pixels in digital image. Raster model provides direct information about a given location. However, besides their size raster structure has the disadvantage of providing an approximate geometry, whose accuracy is dependent on the resolution of the grid.

In vector model, points are stored with their coordinates according to some reference system, line segments by their two end points, and regions are defined by their bounding line segments. When incidence relations between points, segments, and regions are stored explicitly, we speak of a topological data structure. Raster model are more suitable to support queries by location while vector models are more suitable to support queries by content. Thus, hybrid representations, such as digital elevation model (DEM) , are more generally adopted. DEM includes the raster-based elevation matrix, and the vector-based isoline model and triangulated irregular network (Figure 4). The elevation matrix is a twodimensional array of square cells, each cell storing a height value or elevation. The isoline model is a way to represent and visualize a real-valued function defined over the plane. The triangulated irregular network is a subdivision of the plane in non-uniform triangles. Indeed, in relatively flat areas we can do with a small number of large triangles, while smaller triangles are used in areas with a lot of variation in height.

III. COMPUTATIONAL GEOMETRY IN GIS

Computational geometry occurs in all stages of the GIS data cycle. Geometric algorithms are useful in data correction (after data acquisition and input), in data retrieval (through queries), data analysis (like map overlay and geostatistics), and data visualization (for maps and animations). For instance, line segment intersection by plane sweep solves map overlay, Voronoi diagrams are helpful in neighborhood analysis, Delaunay triangulations are widely used for terrain modeling, and geometric data structures help with efficient spatial indexing in large spatial data sets [START_REF] Van Kreveld | Digital elevation Models : overview and selected TIN algorithms[END_REF]. Such problems are closely related to various well-known GIS operations like map overlay, buffer computation map generalization and spatio-temporal data mining and range searching.

Digital elevation model

Digital elevation modeling deals with generating a model for a terrain in a GIS that is realistic. The model is built on an initial data set which can consist of points with elevations or digitized contour lines with elevations. Generating a terrain that fits with the input data, the high-level information is a problem where several conflicting criteria have to be taken into account. The modeling problem and corresponding algorithms are a continuing direction of future research that has hardly been addressed from the computational geometry perspective [START_REF] Van Kreveld | Digital elevation Models : overview and selected TIN algorithms[END_REF]. However, in the cases of TIN, Delaunay triangulation, which is optimal according the minimum angle, is more widely used.

Delaunay triangulation

From irregularly distributed data, either a regular grid or an irregular triangular network can be formed [START_REF] Li | Digital terrain modeling : principles and methods[END_REF][START_REF] Ngom | Extraction of three dimensional pore space from microtomography images using a geometrical approach[END_REF]. There are three basic requirements for TIN formation : for a given set of data points, the resulting TIN should be unique if the same algorithm is used. The geometric shapes of resultant triangles are optimum (each triangle is nearly equilateral) ; each triangle is formed with nearest neighbor points, that is, the sum of the three edges of the triangle is minimum [START_REF] Li | Digital terrain modeling : principles and methods[END_REF]. In all the possible alternatives, Delaunay triangulation is the one most widely used because it satisfies all three requirements.

A Delaunay triangulation is a set of linked but non overlapping triangles uniquely defined if the points are in general position : no two points are identical, no three points lie on a common line, no four points lie in the same plane and no five points lie in the same sphere. The circumscribing circle of each triangle would not include any other points. As the Delaunay triangulation is a dual diagram of the Voronoi diagram (Figure 6), the Delaunay triangulation network can be formed either directly by algorithm or indirectly through the Voronoi diagram which is much easier in raster mode. The resulting triangulation network is independent of the starting point. Therefore, the selection of a starting point is only for the convenience of algorithm implementation. Delaunay's constraint on the mesh selects for nearly equilateral triangles, which evenly distribute the feature bias. TINs' vertices are derived from the features of the reference image, regardless of those features' positions. If we compare grid-based heightmaps to TINs at various resolutions, we would observe that the grid of the first heightmap grows and shrinks around a point of origin, while the TIN's mesh is anchored to the most important features of the reference image. Thus, TINs consistently represent multiple features of the terrain, while grid heightmaps can only consistently represent a feature if it lies at the grid's point of origin.

COMPUTING THE GEOMETRIC TERRAIN MODEL

Modern acquisition techniques provide huge dataset that permit to represent terrain accurately. However, high representation accuracy is paid in terms of high costs for storage and processing. So there must be a trading between the representation cost and accuracy. In this section we present a method of computing Triangular Irregular Network (TIN).

Computation of the Delaunay triangulation

Delaunay triangulation can be found in either dynamic or static mode. Static triangulation means that the triangulation network that has already been constructed will not be altered by adding new points in the formation process. In contrast, with a dynamic trian-gulation, the network already constructed will be changed if a new point is added, so as to meet the Delaunay circumcircle principle.

Materials

We tested the triangulation with Java using a Window 7 environment. The program has been written in java but can be easily transferred in Java Applet so it can run in the internet. The real time rendering of the digital terrain model require Java 3D library. The Java3D library uses OpenGL or Direct3D operating software library to create the necessary algorithms to set up the 3D virtual universe.

Computation of the DTM based on TIN

The geometric terrain model is based on TIN computed from Delaunay triangulation algorithm.

-Algorithms for computing the Delaunay triangulation

There are mainly four algorithms for computing the Delaunay triangulation : Incremental, Gift Wrap, divide and Conquer and QuickHull [START_REF] Van Kreveld | Digital elevation Models : overview and selected TIN algorithms[END_REF][START_REF] Li | Digital terrain modeling : principles and methods[END_REF]. In this paper, the incremental algorithm and the Quickhull algorithm were used to compute respectively the 2D and 3D Delaunay triangulation. The incremental algorithm work as follow : to insert a new site, we walk across the triangulation, starting from the most recently created triangle, until we find the triangle that contains the new site. This triangle and any adjacent triangles that contain this new site in their circumcircle are eliminated and the resulting empty spot is re-triangulated. The expected time to insert a new site is roughly O(n 1/2 ) where n is the current number of sites [START_REF] Chew | Voronoï diagram and Delaunay triangulation[END_REF]. The Quickhull algorithm finds a point on the hull, then repeatedly looks for the next point until it returns to the start [START_REF] Barber | The Quickhull Algorithm for Convex Hull[END_REF]. The algorithm has O(n log(n)) complexity. The data input is a text file containing points with x, y and z coordinates. The incremental algorithm is less time consuming but is difficult to generalize in 3D. That why we chose the QuickHull algorithm for computing the 3D triangulation. However, there should be noted that by fixing the z coordinate, the QuickHull algorithm can also be used to compute 2D triangulation. The output of the Delaunay triangulations is a set of vertices and faces, printed in files that can be easily rendered.

-Implementation and visualization Even if many implementations of Delaunay triangulation have been proposed, to the best of our knowledge many of them suffer of platform dependencies and none is able to handle dynamic Delaunay triangulation as robust as it should be. In this paper, the implementation has been done in Java so as to have full control of the transformations on the model. To render 3D model using Java3D requires the construction of the Scene Graph to implement its 3D graphical operations. The Scene Graph of our application is divided in two main branches or Branchgroup. The diagram of Figure 7 outlines the position of each Java3d variable within the Scene Graph.

The platform enables the visualization of the digital terrain as set of points or as a triangulated surface that can be associated with weight (Figure 7, Figure 8). As java3D has been used for the implementation, there is also possibility to look the surface from different point view through an interaction with the keyboard or the mouse. Besides, the program can be easily transferred in Java Applet application so it can be run on the internet.

FIRST STEPS TOWARDS FLOOD SIMULATION

Real time flood simulation relies on spatial distribution representing discretization of representative terrain maps. Among other issues to be addressed is the need to get a mesh representation which can enable to enhance the computation of surface flows in hydrologic and digital terrain models. The model described here is based on the model presented by [START_REF] Qu | An integrated hydrologic model for multi-process simulation using semidiscrete finite volume approximation[END_REF] resumed by Figure 9. The processes considered are overland flow, subsurface flow, evaporation and infiltration.

Domain decomposition

DT is a realistic physical representation taking into account topological, geometrical and morphometric properties. Besides, the flux across any edge with its neighbor is always normal to its boundary by definition and thus reduces the computational cost to evaluate flux across the volume boundary. In the model, Delaunay triangulation is used to represent the watershed terrain and incorporate watershed boundaries, the stream network, soil type, geology, elevation contours or other feature particular to the domain. Starting points for the watershed domain start from a set of user defined control points : hydrographic points and critical terrain points (maximum or minimum of local surface, convexity or concavity).

Gouverning Hydorlogical processes equations

The governing equations are local system of ODEs representing multiple hydrological processes (Figure 6) within triangle or element i including

δh/δt = P 0 -I -E 0 -Q oc + Σ 3 j=1 Q s [6]
Where h is the local water depth, Q s is surface flow from element i to its neighbor j, P o , I and E 0 are precipitation, infiltration and evaporation respectively.

-Subsurface flow :

dξ/dt = I -q 0 -ET s i dξ/dt = q 0 + Σ 3 j=1 Q -Q l +Qgc g [7]
where ξ is unsatured moisture storage of element I. ξ is satured moisture storage, q 0 is unsatured zone and satured zone ; I and ET are incoming infiltration and outgoing evapotranspiration at land surface respectively ; Q s is lateral groundwater flow from element I to its neighbor Q l is vertical leakage through and underlying confining bed ; Q gc is discharge/recharge from/to aquifer to/from channel.

One advantage of this study is flexibility in this constitution relationship and there is no intrinsic limitation to other possible forms or hydrological processes.

Urban modeling

In urban modeling, building description is the first step towards the construction of an efficient representation. Building can be modeling under vector form using primitives likes planes and straights lines. Indeed planes describe facades or roofs, while the lines represent the facades or roof edges.

Building construction

In recent years a new standard CityGML was validate in the worldwide by Open-Geospatial Consortium [START_REF] Mehdi Rezoug | MODELISATION ET OPTIMISATION DES INONDATIONS UR-BAINES AVEC UNE APPROCHE MULTICRITERES[END_REF]. The main purpose is to give norm of building in the urban environment. It defines many levels of details that explains how the buildings have to be create. For example, in figure 10, the level of detail 1 (LoD1) represents building with just extruded polygons (flat roofs), Lod 2 corresponds to detailed roofs and vertical facade and flat. Lod3 corresponds to more detailed facade, complex roof, all textured. The LoD 4 offers details with an interior modeling. In the our model, The LOD 2 is used during the process of building modeling. For the construction of building, we use a 3D modeler called Wings3D [START_REF] Strother | Wings3D : users reference manual[END_REF]. The procedure is as follow. initialization : put an image; while image exists do -travel image -get contours of all shape in the image -clean it to eliminate no significant details of contour (smallest things that have no impact on the simulation) -adjust some geometric configurations which can cause mesh damage -do an extrusion to get building's shape in three dimensions end The tests of the algorithm have been made with the 2D perspective views of the figure 12 as input image. In the first step, we search the contours of all parts that delimit the different building. Once finished a removal process begin to eliminate no significant contours like illustrated by Figure 13. In the next step, we do an extrusion to all contours found to get the 3D building's shape. The result is illustrated by Figure 14. In the last step, the numerical terrain computed from Delaunay tringulation and the building contructed from a modeler are put in a single scene.

Conclusion

In this paper we have first reviewed issues concerning computational geometry and GIS. At the state of the art, computational geometry offers rigorous and powerful tools for solving a variety of geometric problems in GIS. However, a number of problems that could be solved with computational geometry tools remain to be solved. We used java application based on the convex hull algorithm to build triangular irregular network for 2D set of points and 3D set of points. Java 3D graphics package was used to render the three dimensional model of TIN. In the last section, we introduce conceptual principles and steps processing for a hydrological model based on Delaunay triangulation terrain decomposition. We also gives first step for urban area modeling.

Futures works will focus on improving the digital terrain model by providing tools for the user to move through the virtual world, to supply elevation datasets, to drape images over the model, to generate statistics and perform simulation of hydrological processes over the model. After that we will superpose our two model (DTM and building) because our final aim is to create an interactive, real-time three-dimensional terrain model that can be rendered with free 3d graphics libraries, which may be used as a base for digital terrain analysis, natural phenomena real time simulation for decision making.

Figure 1 .

 1 Figure 1. Example of parametric curves[START_REF] Wafia Boubguira | Modélisation numérique de terrain : Etude de Synthèse et Application[END_REF]

Figure 2 .Figure 3 .

 23 Figure 2.Bezier surface computed from control points[START_REF] Wafia Boubguira | Modélisation numérique de terrain : Etude de Synthèse et Application[END_REF]

Figure 4 .

 4 Figure 4. An elevation matrix, isoline model, and TIN for the same source data [6]

Figure 5 .

 5 Figure 5. Topographical features classifications[START_REF] Kalbermatten | Multiscale analysis of geomorphological and geological features in high resolution digital elevation model using wavelet transform[END_REF]

Figure 6 .

 6 Figure 6. Set of points (top), Voronoï diagram (right), Delaunay circle (left), Delaunay triangulation of the point

Figure 7 .

 7 Figure 7. scene describing the structure of the program

Figure 8 .

 8 Figure 8. Triangulation of complex contour structure

Figure 9 .

 9 Figure 9. Sample of 3D representation of building. Three representations of the same building in different level of details[23].

Figure 10 .

 10 Figure10. Input image : 2D perspective view of a scene of urban area[START_REF] Insertion-Paysagere | PC6 vue aérienne aménagement lotissement[END_REF]

Figure 11 .

 11 Figure 11. Contours computed from the 2D input image

Figure 12 .

 12 Figure 12. 3D Building reconstruction from the contour image6.2. Towards a model of flood simulationThe processing steps of the model are resumed by Figure9. Spatial discretization of the hydrological model coupled with a digital elevation model of surface is first performed. The governing equations of hydrological model are based on a system of ODE (Equation X, Equation Y) extracted from Saint Venant equations. The hydrological model will be integrated using a semi-discrete finite volume method. The finite volume elements are prisms projected from a Delaunay Triangulation based TIN. The model is designed to simulate hydrological processes such as water movement, water quality and sediment transport in surface and subsurface.

Figure 13 .

 13 Figure 13. Step processing of the hydrological model based on DT domain decomposition

m

  3 , t 2 , t, 1) 11 m 12 m 13 m 14 m 21 m 22 m 23 m 24 m 31 m 32 m 33 m 34 m 41 m 42 m 43 m 44

	
	 
	

  M. P 11 P 12 P 13 P 14 P 21 P 22 P 23 P 24 P 31 P 32 P 33 P 34 P 41 P 42 P 43 P 44

	
	  