Gabriel Hermosillo

Lionel Seinturier

Laurence Duchien

Using Complex Event Processing for Dynamic Business Process Adaptation

Keywords: Complex Event Processing, BPEL, process adaptation, QoS

As the amount of data generated by today's pervasive environments increases exponentially, there is a stronger need to decipher the important information that is hidden among it. By using complex event processing, we can obtain the information that really matters to our organization and use it to improve our processes. However, even when this information is retrieved, business processes remain static and cannot be changed dynamically to adapt to the actual scenario, diminishing the advantages that can be achieved. In this paper we present CEVICHE, a framework that combines the strengths of complex event processing and dynamic business process adaptation, which allows to respond to the needs of today's rapidly changing environments. We use a simple car rental scenario to show how CEVICHE could be used to maintain the quality of service of a business process by adapting it according to the situation.

I. INTRODUCTION

Given the dynamicity of today's business environments, there is a need to continuously adapt the business processes in order to respond to the changes in those environments and keep a competitive level. One of the main concerns for on-line applications is to keep a high Quality of Service (QoS), for which they need to keep a constant monitoring of their processes. By using Complex Event Processing (CEP) we can facilitate the solution of this problem by gathering information about the different steps of the processes in order to determine whether a situation of low QoS is approaching. CEP is an emerging technology which allows to find real-time relationships between different events using elements such as timing, causality, and membership in a stream of data in order to extract relevant information [START_REF] Luckham | The Power of Events: An Introduction to Complex Event Processing in Distributed Enterprise Systems[END_REF].

CEP can be used, for example, to prevent the theft of merchandise from stores by creating relationships between the amount, kind, and movement of the products inside the store and sending an alert when a suspicious situation is detected [START_REF] Huber | Minimizing Product Shrinkage across the Supply Chain using Radio Frequency Identification: a Case Study on a Major Australian Retailer[END_REF]. However, there are some occasions in which it is not enough just to be able to obtain this information from simple raw data. For example, when monitoring the QoS, we could alert the administrator when the process is not responding as expected, but an optimal response would be to automatically adapt the business process according to the new context in order to continue in an optimal way, and this is why we developed CEVICHE (Complex EVent processIng for Context-adaptive processes in pervasive and Heterogeneous Environments).

The purpose of CEVICHE is to create context-aware business processes that are able to adapt dynamically in order to respond to different scenarios. CEVICHE relies on BPEL, since it is the most common orchestration language, it is an OASIS standard and it is an execution language and not a modeling language (like BPMN), and in CEVICHE the adaptation of the business process happens at runtime during the execution [START_REF]OASIS Standard. Web Services Business Process Execution Language Version 2.0[END_REF]. The decisions of how to respond to a specific scenario are done by collecting data from different sources and transforming it into useful information, using CEP. By using an aspect-oriented approach, we can define alternative processes that can be woven into the business process at runtime, allowing the business process to adapt in a dynamic way.

In this paper we use an on-line car rental application to show how CEP, and specially CEVICHE, can be used to maintain a high QoS by monitoring the business process and adapting it accordingly to respond to the context information gathered by the system.

The objectives in this paper are:

• To show why dynamic adaptation is needed in today's business processes.

• To integrate CEP into business processes to help in the decision making task.

• To provide a framework that facilitates such integration by giving the users a unique entry point to create dynamically adaptable business processes. The rest of this paper is organized as follows. In Section II, we use a scenario to illustrate the motivation and challenges of our proposal. Section III presents a background of the different domains used in this paper. Section IV explains the CEVICHE framework and its architecture. In Section V, we discuss our proposal and present some validations. Section VI presents some of the related work. Finally, section VII concludes and discusses some future work.

II. MOTIVATION AND CHALLENGES

In this section we present our motivation by using a small car rental scenario in which we want to monitor the QoS.

After that we present the challenges that we face when using static business processes.

A. Motivation

To show how CEP and CEVICHE can be used to maintain a high QoS we present an on-line car rental service. In this service, the client goes through a process of eleven steps to get a car, as shown in Fig. 1. The client starts the process by providing a valid license number, then selects the characteristics of the car to rent and finally pays and receives a confirmation from the system. Whenever the application is getting a considerable amount of traffic, that could decrease the response time of the servers, the owners of the on-line application want to avoid the invocation of some optional tasks of the business process. This will help to maintain the QoS and allow the user to complete the car rental process in fewer steps and to spend less time waiting for the application to respond.

The optional tasks that could be excluded from the business process of this scenario, without altering the main objective, are: the color select (step c) and the satisfaction survey (step j). To skip them, an additional path from the preceding activity to the next will have to be set. Then, the process will have to be redeployed and the application restarted, for the changes to be considered.

In this scenario, the QoS is considered with two parameters: service performance and service availability. The performance of a web service can be measured by considering the time it takes to respond to a user query, while the service availability can be simply measured by the existence or not of a response from the service.

B. Challenges

When we want to monitor the business process and adapt it accordingly to respond to current situation, we face several challenges that make it difficult to accomplish.

Challenge 1: The first challenge we have in this scenario is the lack of specification in the BPEL standard to monitor the business processes, thus leaving each BPEL engine implementation to decide whether or not to include a monitoring interface [START_REF]OASIS Standard. Web Services Business Process Execution Language Version 2.0[END_REF]. But even when the BPEL engine used provides a monitoring interface, it does not necessarily mean that it will provide the precise information that we want to monitor.

Challenge 2: As our next challenge, we face that even when we could monitor the business process, the identification of a situation that needs the process to be adapted (like a low QoS), will add a lot of unnecessary code to the core business process definition, and in some cases will be impossible to specify using only BPEL.

Challenge 3: The last challenge that we face when using BPEL engines is that the process definitions are static, which means that we cannot adapt the business process without redeploying it, thus generating a downtime of the system and losing all the information of the current transactions. The only changes possible at runtime are the bindings to partner links, but they have to be previously defined at deploy-time and we cannot add new partner links at runtime [START_REF] Juric | Business Process Execution Language for Web Services BPEL and BPEL4WS 2nd Edition[END_REF].

III. BACKGROUND

In this section, we present a brief introduction to the four main domains addressed in this paper: complex event processing, business process execution language, quality of service and aspect oriented programming.

A. Complex Event Processing

CEP is an emerging technology for finding relationships between series of simple and independent events from different sources, using previously defined rules [START_REF] Luckham | The Power of Events: An Introduction to Complex Event Processing in Distributed Enterprise Systems[END_REF]. The CEP technology can be used, among a lot of other things, to enrich the enterprise's existing processes, by introducing rules that will allow the capture of relevant information from the different steps of their business process [START_REF] Ku | A Novel Complex Event Mining Network for Monitoring RFID-Enable Application[END_REF].

For example, let us consider the scenario of a retail store that keeps a record of its inventory in an existing Enterprise Resource Planning (ERP) system and wants to keep a live monitoring of its stocks in order to prevent shortage. To achieve this, the store installs a CEP engine that will monitor the products movements through their life cycle in the store process by receiving and analyzing all the events generated by every change in the state. Since the objective is to monitor inventory, the CEP engine will only keep the events related to changes in the inventory and forget about the rest. By creating the necessary CEP rules, the configuration is set to specify the lowest acceptable stock of product that the store can have to avoid a shortage, e.g., a 10% for normal products and a 5% for some low-demand products. Whenever a product reaches a minimum, the CEP engine alerts the managers so they can make a supply order.

In addition to that, CEP can also be used to predict unexpected situations. To complement the previous example, we can say that because of a global pandemic alert, hand sanitizers are very popular and are selling a lot more than usual. Given this demand, the store will run out of hand sanitizer before they can resupply it, even with the minimum stock alert. By adding some specialized CEP rules to analyze the frequency of sells of each product during the last 4 or 5 hours, the engine could polarize these values to know in advance (if the sells rates are kept) that it will need to resupply before the expected time, which will allow them to react in time even before it reaches the minimum level.

B. Business Process Execution Language

The Business Process Execution Language (BPEL) is an XML-based language for composing services, created by IBM, BEA Systems and Microsoft in 2002, and later approved as an OASIS Standard as WS-BPEL 2.0 [START_REF]OASIS Standard. Web Services Business Process Execution Language Version 2.0[END_REF]. There are two types of service composition: orchestration (execution) and choreography (control). BPEL is an orchestration language, which means that it focuses on the flow of control and data among the different services of the business process, rather than on the specification of peerto-peer collaboration.

BPEL uses web services as a way to communicate with the different parties involved in the business process. It has two types of activities: primitive and structured. The former refers to atomic or single activities while the latter refers to composite activities (a combination of several activities). Some instructions like invoke, receive or assign refer to the primitive activities, while sequence and flow are part of the structured activities and refer to the order in which the activities will execute.

In order to interact with the different parties of the business process (called partners), we need to define a partner link, which specifies the roles of the partner and the caller. We also need to define the different input and output variables that we will use to send information to and receive information from the service. Finally, BPEL also provides some facilities for transaction and exception handling.

C. QoS in Web Services

The goal of the Web Services effort is to achieve interoperability between applications by using Web standards. Web Services use a loosely coupled integration model to allow flexible integration of heterogeneous systems in a variety of domains including business-to-consumer, businessto-business and enterprise application integration [START_REF]OASIS Standard. Web Services Business Process Execution Language Version 2.0[END_REF]. Web services are the most popular technology to implement the service-oriented architecture and they use open Internetbased standards, like the Simple Object Access Protocol (SOAP) for data transmission, the Web Services Description Language (WSDL) for defining services, and BPEL for orchestrating services [START_REF] Papazoglou | Service-oriented computing: State of the art and research challenges[END_REF].

When these web services are used as part of a whole process, the QoS of the process depends on the QoS of the web services composing it. But, in order to use the services provided through the Internet by the different organizations, the users of those services need to know what to expect from them, in terms of QoS, so that they can offer a decent QoS to their own users.

The study of QoS for web services is not new, and there have been a good number works discussing how to estimate the QoS of a web service-based workflow [START_REF] Cardoso | Quality of service for workflows and web service processes[END_REF], [START_REF] Jaeger | Qos aggregation for web service composition using workflow patterns[END_REF], [START_REF] Wang | Combining subjective and objective qos factors for personalized web service selection[END_REF], [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF]. Also, in order to measure the QoS of the web services, many metrics have been proposed in the literature [START_REF] Cardoso | Quality of service for workflows and web service processes[END_REF], [START_REF] Moser | Non-intrusive monitoring and service adaptation for ws-bpel[END_REF], [START_REF] Gillmann | Workflow management with service quality guarantees[END_REF], [START_REF] Jaeger | Qos aggregation for web service composition using workflow patterns[END_REF], [START_REF] Patel | A qos oriented framework for adaptive management of web service based workflows[END_REF]. The QoS attributes can be classified as deterministic or non-deterministic. The former means that the attributes are already known before the execution of the service (e.g., price, server location). The latter refers to the attributes that are unknown before the execution (e.g., response time, availability). The monitoring of these attributes can be achieved in two ways: server-side monitoring or client-side monitoring. Since the user of the services does not always have the control of the hosting servers, we will focus on the client-side monitoring for our scenario.

As we mentioned in Section II, our scenario measures the QoS using two parameters: performance and availability. To calculate those values we will use the formulas provided by Oliver et al. in [START_REF] Moser | Non-intrusive monitoring and service adaptation for ws-bpel[END_REF], as shown in Table I.

QoS Attribute Formula

Performance

1 #requests requestT ime i Availability 1 -uptime downtime Table I QOS ATTRIBUTES

D. Aspect Oriented Programming

The domain of Aspect-Oriented Programming (AOP) appeared in 1996 [START_REF] Kiczales | Aspect-Oriented Programming[END_REF], [START_REF] Kiczales | An overview of aspectj[END_REF]. It was pioneered by Gregor Kiczales and his team, then at the Xerox Palo Alto Research Center. While original and innovative, the domain of AOP inherits results from other programming approaches, such as reflection, open implementations, meta-object protocols, and generative programming.

AOP, as a new programming paradigm, introduces notions such as aspect, join point, pointcut and advice code. However, these notions do not replace existing ones, such as class, object, procedure or method. Rather, AOP must be seen as a complement to these existing techniques. Furthermore, these notions are not specific to a programming style (e.g., object-oriented or procedural) or a given syntax (Java, C#, Ada, COBOL, etc.). Aspect-oriented extensions exist for many languages, object-oriented or procedural, and in this case, BPEL.

AOP has been proposed as a technique for improving the separation of concerns in software systems and for adding crosscutting functionalities without changing the business logic of the software. AOP provides specific language mechanisms that make it possible to address concerns, such as

IV. THE CEVICHE FRAMEWORK

In this section we present the CEVICHE framework. We start by giving an overview of the system, then we present the architecture and finally we explain how the process adaptation is realized.

A. Overview

CEVICHE is a framework that intends to facilitate the integration of CEP into existing business processes and to allow these processes to be dynamically adapted to different circumstances. With this framework we want to address mainly four issues: adaptation, dynamicity, integration to business process, and non-dependency to a specific CEP engine.

To address the first issue, adaptation, we use an approach based on AOP [START_REF] Kiczales | Aspect-Oriented Programming[END_REF]. This approach allows the system to add or change services from the current business process and facilitates the task of separating concerns. To do this, AOP needs to know in which part of the business process it needs to perform the adaptation (the pointcut). Using the pointcuts, we can tell the AOP framework what special behavior (the advice code) we want to apply in that part of the business process. Once the advice code is woven, the process is adapted.

By analyzing the current events with CEP and using context information, CEVICHE can automatically decide when and how to adapt the system. This adaptation can be done at runtime, thanks to the advantages of using an aspectoriented approach, thus giving a solution to the dynamicity issue.

To integrate BPEL with AOP, we use the AO4BPEL framework [START_REF] Charfi | Ao4bpel: An aspect-oriented extension to bpel[END_REF], which creates a wrapper around the BPEL interpreter and has the ability to weave the aspects at runtime to the business process. The advantage of using AO4BPEL is that we can change the business process specifications at runtime without the need to redeploy them, avoiding to lose all the ongoing transactions by doing that. In CEVICHE we integrate the AO4BPEL framework with CEP, allowing us to give a solution to the third issue.

Finally, CEVICHE aims to be able to work with any CEP engine available. For that, as part of this framework, we define a language called the Standard Business Process Language (SBPL), which gathers all the information about the processes, contextual environment, business rules, and adaptation conditions. This information is saved in an XML file that CEVICHE translates to the chosen CEP engine using the corresponding translation plug-in of that engine. This approach allows the users to define their business processes only once and deploy them using their preferred CEP engine.

< a s p e c t name= " M o n i t o r i n g A s p e c t " > 2

< p a r t n e r L i n k s > 3 < p a r t n e r L i n k name= " P e r f o r m a n c e M o n i t o r " p a r t n e r L i n k T y p e = " P e r f o r m a n c e L i n k " 4 myRole= " c a l l e r " p a r t n e r R o l e = " m o n i t o r " / > 5 < / p a r t n e r L i n k s > 6 < v a r i a b l e s > 7 < v a r i a b l e name= " a c t i v i t y S t a r t " messageType = " a c t i v i t y S t a r t N a m e " / > 8 < v a r i a b l e name= " a c t i v i t y S t a r t T i m e " messageType = " s t a r t T i m e " / > 9 < v a r i a b l e name= " a c t i v i t y S t o p " messageType = " a c t i v i t y S t o p N a m e " / > 10 < v a r i a b l e name= " a c t i v i t y S t o p T i m e " messageType = " s t o p T i m e " / >

B. CEVICHE Architecture

CEVICHE is composed of three main parts: a user interface to create the SBPL files, a translation framework to manage the plug-ins for each CEP engine, and an aspect manager to deal with the process adaptation. CEVICHE also relies on different technologies to achieve the process adaptation, as shown in Fig. 2.

To configure the system, the user is provided with an interface to capture the different elements needed to adapt the processes, which are then saved to an SBPL file. The SBPL is an extension of BPEL which allows the user to include, in the business process definitions, the adaptation points and conditions in order to create dynamically adaptable business processes. The information in the SBPL file is sent to the translation framework, which separates the data in three parts: the business process (BPEL), the adaptation situations (CEP rules) and the aspects to adapt the process. Since there is no standard to define the CEP rules, the translation framework uses a specialized plug-in to send the adaptation information in the SBPL file in the specific CEP engine's format. This way, whenever the user wants to use another CEP engine, the only thing that needs to be done is to change the plug-in, without rewriting all the specifications of the business processes.

Once the initial setup is ready and all the components have been properly configured, the process starts and the information begins to flow from one component to the other, as seen in Fig. 2. First, the CEP engine subscribes to the different sources of events, here called the events cloud, which will provide the engine with the information it needs to take decisions and create complex events.

The CEP engine will gather all the events, filter the interesting ones according to the business rules and find relations that can generate complex events. When an adaptation situation is detected, the CEP engine notifies the aspect manager, which in turn searches for the corresponding aspect to adapt the business process. Once the aspect is selected, CEVICHE uses the AO4BPEL engine to weave the code into the process, adapting it at runtime.

C. Process adaptation

CEVICHE uses an aspect-oriented approach, which allows the system to add and remove functionality at runtime. When this approach is applied to the business processes, it allows them to be dynamically adapted.

With AO4BPEL we can handle two types of aspect deployments: process-level deployment and instance-level deployment [START_REF] Charfi | Ao4bpel: An aspect-oriented extension to bpel[END_REF]. The former is used when the aspect is needed in all the instances of the business process, while the latter is used when only a specific kind of instances are targeted.

The process can be adapted using three kind of advices: before advice, after advice and around advice. The first one intercepts the call before the joinpoint, executes its task and then lets the process continue the normal flow, including the execution of the joinpoint activity. The after advice gets executed just after the joinpoint activity is completed and the process continues normally afterwards. Finally, the around advice intercepts the call just like the before advice, but it adds functionality before and after the join point activity. Moreover, this advice can be used without executing the joinpoint activity.

An example of an aspect definition can be seen in Fig. 3. In this example we see the use of the special reflexive variable ThisJPActivity (line 20), which refers to the join point (the intercepted activity). This variable can obtain all the information of the join point, in this case the name, so that it can be used by the advice.

We can also have a pool of different services that can replace the original one and we can even have a historical QoS rating for each one, that will allow us to select the best option. This pool of services can even include composite services, which can replace the original one.

V. DISCUSSION AND VALIDATION In this section, we present how we can use CEVICHE to deal with the challenges presented in Section II. In a nutshell, we had three main challenges in our scenario: QoS monitoring, identification of special situations and dynamic adaptation.

Challenge 1: For the monitoring of the QoS, in our car rental scenario, we created an around advice. This advice is deployed at process-level, since we want to monitor all the instances of the business process. In the advice we include four additional activities, two before and two after the joinpoint. The first activity is used to count the number of times the joinpoint activity is called, then it calls the second activity which records the start time of the joinpoint activity. Once the joinpoint activity is executed, the third extra activity is called. This activity measures the duration of the invocation by subtracting the starting time from the current time, thus getting the performance of the activity for that invocation. The final activity is used to count the number of times the joinpoint has been successfully executed to calculate the availability. By using this two metrics (performance and availability) we can monitor the QoS of the business process.

Challenge 2: To identify the special situations where the process needs to be adapted, we created some CEP rules using the formulas presented in Section III-C. Whenever the performance of the car rental process dropped more than 25% or an activity was not available, the CEP engine notified CEVICHE.

Challenge 3: When CEVICHE received the notification about the drop in performance, it automatically deployed the instance-level aspect that skipped the two optional tasks of the car rental scenario: the color select (step c) and the satisfaction survey (step j). When the notification was about an unavailable service, then CEVICHE searched for alternative service from the pool. If an alternative service is found in the service pool, then an aspect deployed at instance-level to change the service. We tried this by turning off the insurance selection service (step f) in the car rental process and CEVICHE automatically changed to an alternative service of another provider. The adaptation of the business process was done dynamically and automatically, without loosing any information from the different instances of the process.

Performance: As it can be expected, the inclusion of aspects to dynamically adapt the process, as well as a CEP engine to discover the adaptation situations, require some additional time and resources. This overhead may vary depending on the number of rules that need to be processed by the CEP engine and the complexity of the aspects that will be woven. However, the overhead induced to the original process is negligible compared to the cost of the whole process, specially when dealing with Internet interactions with partners. The AO4BPEL engine adds only an overhead of 1% of the execution time, and could be even less when the processes are bigger, since the cost is mostly the same for the whole system and does not vary in terms of the number of activities. For the CEP engine, the overhead is also insignificant, taking it less than 1 ms to process each event through the whole set of rules. In this case we used the Esper engine, which is an open source stream event processing engine [START_REF] Espertech | Esper[END_REF]. The efficiency of the CEP engine to process the events is such that it exceeds over 500,000 events per second.

VI. RELATED WORK

CEP and BPEL: As mentioned earlier in this paper, CEP is an emerging technology and the use of it in the business processes is a recent topic of interest and research [START_REF] Barros | Complex events in business processes[END_REF], [START_REF] Hermosillo | A Traceability Service to Facilitate RFID Adoption in the Retail Supply Chain[END_REF]. An analysis of scenarios of composite event patterns comparing BPEL and BPMN is done in [START_REF] Barros | Complex events in business processes[END_REF]. The authors analyze patterns of events that go from conjunction and cardinality to time relations and event consumption possibilities. The conclusion of their study is that neither BPEL nor BPMN are capable of supporting complex event scenarios in their specifications, so there is a need to integrate event pattern descriptions into the process definitions language, but they do not mention the need to adapt the process according to those complex events.

In [START_REF] Hermosillo | A Traceability Service to Facilitate RFID Adoption in the Retail Supply Chain[END_REF], we present a service to add traceability to the RFID tagged products by using Complex Event Processing. When the RFID events are captured, they are transformed into business events that correspond to the business rules defined in the process which allows the users to have a better understanding of the status of their products, i.e., the product's location and the environment it has been exposed to.

Business process adaptation:

The need to adapt a process has been a topic of interest in the recent years and there have been different approaches that offer solutions to it [START_REF] Lins | Adaptive web service composition[END_REF], [START_REF] Sánchez | A flexible architecture to build workflows using aspect-oriented concepts[END_REF], [START_REF] Rahman | An adaptive eca-centric architecture for agile service-based business processes with compliant aspectual .net environment[END_REF], [START_REF] Koning | Vxbpel: Supporting variability for web services in bpel[END_REF]. In [START_REF] Lins | Adaptive web service composition[END_REF], the authors propose to deal with process adaptation by adding a web service repository that will handle the web services to invoke in each case. Whenever an invocation of a web service is done, the call is intercepted and the repository is checked for changes in the process definition, before the invocation of a web service. If there have been some changes, then it examines the available web services in the repository and chooses the one that best suits the criteria, otherwise the invocation is executed as usual.

The authors in [START_REF] Sánchez | A flexible architecture to build workflows using aspect-oriented concepts[END_REF] use an aspect-oriented approach introducing executable models, which are used to represent the cross-cutting concerns. They use open objects, which are representations of the state of the elements in the model, to monitor the invocation of services and adapt the process by weaving the interaction with other models before (activation) and after (deactivation) the call to the service.

Another aspect oriented implementation, using the Spring .NET framework, is presented in [START_REF] Rahman | An adaptive eca-centric architecture for agile service-based business processes with compliant aspectual .net environment[END_REF]. They use a contractbased approach to assign a web service to each instance of an execution call. To achieve adaptation of the process they can change the contract at runtime to assign a new web service for the call. They can also adapt an existing implementation of a web service by using aspects to weave the new behavior.

An adaptation of the BPEL language called VxBPEL is presented in [START_REF] Koning | Vxbpel: Supporting variability for web services in bpel[END_REF]. The authors insist on the need of flexibility and variability in the service-based systems and the lack of them when deploying BPEL processes. They extend the BPEL language to add new elements like Variation Points, which are the places where the process can be adapted and Variants, which define the alternative steps of the process that can be used. VxBPEL also accepts new Variants to be added at runtime, allowing the systems to be adapted without redeploying the process.

BPEL context adaptation: The work that is closer to our proposal is the one presented in [START_REF] Charfi | A plug-in architecture for self-adaptive web service compositions[END_REF]. The authors present a plug-in based architecture for self-adaptive processes that uses AO4BPEL. Their proposal is to have different plugins with a well-defined objective. Each plug-in will have two types of aspects: the monitoring aspects that will check the system to observe when an adaptation is needed and the adaptation aspects that will handle the situations detected by the monitoring aspects. Whenever the conditions of a monitoring aspect are met, it uses AO4BPEL to weave the adaptation aspects into the process at runtime. In our approach we deal with the monitoring part using the rules deployed in the CEP engine, which will detect special situations (by relating simple events) and select the aspects to be used to adapt the process.

An advantage of their work is that the monitoring aspects can be hot-deployed to their BPEL engine while with our approach the changes in the rules might not be considered at runtime, depending on the CEP engine. On the other hand, this difference also shows an advantage for our proposal, since we are not tied to a single engine and we can use any CEP rules already defined for the monitoring process, while in their case we would need to create a new plug-in for each new situation we want to monitor. Also, even if we needed to restart the CEP engine in order to consider the new rules, this would not affect any active running processes, as it would if we restarted the BPEL engine.

VII. CONCLUSIONS AND FUTURE WORK

Process adaptation and Complex Event Processing are two topics that are creating a lot of interest in the research community, however there is still no integration of both domains. In this paper we presented CEVICHE, a framework that intends to facilitate the integration of CEP into existing business processes and to allow these processes to be dynamically adapted to different circumstances. With CEVICHE we addressed four issues: adaptation, dynamicity, integration to business process, and non-dependency to a specific CEP engine. As part of the CEVICHE framework, we proposed the SBPL, an extension of BPEL that allows the user to include the adaptation points and conditions in order to create dynamically adaptable business processes. The SBPL uses special plug-ins to deal with the different languages of the CEP engines, allowing the users to write their process specifications only once and deploy it in the engine they want. Using a simple car rental scenario we showed how CEVICHE can be used to monitor the QoS of a business process and adapt it dynamically to keep a competitive level whenever the QoS dropped, without the need to redeploy the process and without loosing any current transactions.

Thanks to the modular architecture of CEVICHE, it is not strongly linked to any third party technology. Even though, for the moment we use AO4BPEL to deal with dynamic adaptation of business processes, we could change it for any other technology that allows us to do better dynamic adaptation, or even develop our own. This architecture also allows our work to be componentized in the future, facilitating the integration with other technologies and the interaction with the different parts of the architecture. We also plan to work on the definition of a RESTful architecture to leverage on the deployment of CEVICHE components and facilitate the evolution of the architecture by adding or changing components. We are still working with the SBPL in order to have a very vast coverage of the CEP needs, and for the moment we only have some basic support for SQL based CEP engines like Esper.

Figure 1 .

 1 Figure 1. The car rental process

Figure 2 .

 2 Figure 2. The CEVICHE framework

Figure 3 .

 3 Figure 3. The performance monitoring aspect


Keywords: Réseaux radio cognitifs, environnement hostiles, architecture d'accès à internet

Une architecture d'accès à internet basée sur la radio cognitive pour le déploiement des réseaux en cas de catastrophes dans des environnements hostiles Résumé : Dans cet article, nous proposons une architecture d'accès à internet basée sur la radio cognitive pour le déploiement des réseaux en cas de catastrophes dans des environnements hostiles. L'architecture proposée est conçue pour aider les réseaux existants et particulièrement ceux endommagés pour reconstituer leur connectivité et les relier à l'Internet. L'architecture proposée constitue la base pour le développement de protocoles et algorithmes pour les réseaux radio cognitifs déployés dans des environnement hostiles.

Introduction

Natural disasters like earthquake or storms are unpredictable and rather a frequent phenomenon these days. The collapse of communications infrastructure is the usual effect of disaster. In fact, different types of communication networks could be affected by a disaster. For instance, base stations of cellular networks, lack of connectivity between sensors and sink in static WSNs, damage in the existing WLANs etc. Thus, these partially damaged coexistent networks that were previously deployed are now disconnected and all kind of wireless communication cease to work.

In spite of technological advancements, the instantaneous deployment of core telecommunication infrastructure, for e.g. base stations in the case of cellular networks, is not feasible because of planning and cost. Besides, there is a quick need to help rescue teams or NGOs to facilitate organized help and rehabilitation works, which further motivates the need of rapid ad-hoc network infrastructure deployment. The goal of this rapidly deployed ad-hoc network infrastructure is to provide connectivity and Internet access to partially destroyed networks and to help the rescue team members, until the telecommunication infrastructure is repaired. The use of WLANs can be the solution, and that is in fact what in Hiati [START_REF] Goldstein | Engineers help ngos get online after haiti quake[END_REF] engineers did but the achieved communications suffered considerable delays. However, these disaster response networks, which we referred as challenged networks, impose several constraints like intermittent connectivity, delay, high error rates, no end-to-end paths, unreliable links, heterogeneous devices and operating environment, lack of infrastructure, to name a few. In fact, disasters and emergencies are unpredictable, and network deployment should allow rapid and adhoc deployment, and must be specifically designed to cater the needs of challenged environments.

In this paper, we propose a Cognitive Radio Based Internet Access Framework for Disaster Response Network Deployment in Challenged Environments. In fact, cognitive radio is the term first coined by J. Mitola et al. [START_REF] Mitola | Cognitive radio: Making software radios more personal[END_REF] in the year 1999 for efficient spectrum utilization. These cognitive radio devices are capable to change their operating parameters on-the-fly and adapt with respect to the environment [START_REF] Akyildiz | Crahns: Cognitive radio ad hoc networks[END_REF]. By doing so, Cognitive Radio (CR) devices opportunistically exploits the spectrum left unoccupied by Primary Radio (PR) nodes. Moreover, cognitive radio devices operate in an ad-hoc fashion and form cognitive radio ad-hoc networks. In this way, through our proposed framework and by exploiting cognitive radio technology, the goal of providing robust connectivity and Internet access to partially destroyed networks can be easily achieved. In this context, to allow CR devices to restore the connectivity of partially destroyed coexistent network as well as providing Internet accessibility, an architectural framework is required, which in turn provides rapid, cost-effective, and robust connectivity. Recently, [START_REF] Gorcin | Public safety and emergency case communications: Opportunities from the aspect of cognitive radio[END_REF] discussed the use of cognitive radio in public safety systems, while a cognitive agent based approach for post-disaster communication is proposed in [START_REF] Majid | Post-disaster communications: A cognitive agent approach[END_REF], nevertheless, the connectivity of partially destroyed networks and their connectivity to the global Internet is still an unaddressed topic.

In challenged environments, Cognitive Radio Ad-Hoc Networks (CRNs) is a promising technology and capable to federate the communication of coexistent networks temporarily. In fact, several distinguished features of cognitive radio technology make CRN an easy to deploy and flexible solution for challenged environments. These features include for instance the accessibility and flexibility of communication over the whole spectrum band. Another important feature is the multi-radio capability of CRNs which can further be used to control communication overhead. For instance, if one radio is available per device, flooding should be avoided in order to limit communica-tion overhead, what requires the design of different forwarding mechanisms. However, if multi-radios are available, flooding can become a powerful transmission strategy, if access to channels is well done.

Despite the availability of whole communication spectrum band, concentration of all the radio devices over a single spectrum band could lead to contention and collision problems, which further reduces the connectivity to global Internet. Cognitive Radio could help a lot on these, by providing more "communication space" to devices. In addition, the inherent self-organizing capabilities of cognitive radio devices i.e. detect and jump among channels, features provided by the spectrum sensing and allocation, and the ad-hoc deployment can also be interesting for post-disaster situations.

The remainder of this paper is organized as follows: Section 2 discusses the related work. The architecture of the proposed framework is presented in Section 3. Issues and challenges concerning deployment and connectivity of the proposed framework are discussed in Section 4. Section 5 discusses the use of channel selection strategy SURF in conjunction with the proposed architecture. Finally, we conclude in Section 6.

Related Work

Recent work on the deployments of cognitive radio networks in post-disaster situations include [START_REF] Gorcin | Public safety and emergency case communications: Opportunities from the aspect of cognitive radio[END_REF] and [START_REF] Majid | Post-disaster communications: A cognitive agent approach[END_REF]. The authors in [START_REF] Gorcin | Public safety and emergency case communications: Opportunities from the aspect of cognitive radio[END_REF] discussed several opportunities from the aspect of cognitive radio in public safety, however, these discussions remained general without proposing a feasible architecture or framework. A cognitive agent based approach for post-disaster communication is proposed in [START_REF] Majid | Post-disaster communications: A cognitive agent approach[END_REF] but the authors did not explain how the connectivity of partially destroyed networks as well as their connectivity to the global Internet could be achieved. In summary, the problem of restoring connectivity of partially destroyed networks and connecting them to global Internet is still unaddressed.

Another cognitive radio based network architecture DIMSUMnet [START_REF] Buddhikot | Dimsumnet: New directions in wireless networking using coordinated dynamic spectrum access[END_REF] is proposed for the integration of cognitive radio networks into the global Internet. This architecture is specifically designed for cellular networks and based on a centralized regional spectrum broker and does not cater the needs of rapid and ad-hoc network deployments, mostly required in post-disaster situations. Moreover, this architecture requires significant time in planning and deployment, and requires strong coordination with the existing infrastructure, instead of opportunistic, distributed, rapid, and un-coordinated deployments mostly required in challenged environments. Compared to [START_REF] Buddhikot | Dimsumnet: New directions in wireless networking using coordinated dynamic spectrum access[END_REF], our proposed architecture is totally rapid, distributed, cost-effective, suitable for ad-hoc deployment and provides robust connectivity to partially destroyed networks.

In addition, cognitive radio ad-hoc networks has been widely used in several application scenarios including military and mission-critical networks [START_REF] Leschhorn | Military software defined radios-rohde and schwarz status and perspective[END_REF], [START_REF] Younis | Cognitive manet design for mission-critical networks[END_REF], and consumer-based applications [START_REF] Ball | Consumer applications of cognitive radio defined networks[END_REF], [5], [START_REF] Chapin | The path to market success for dynamic spectrum access technology[END_REF]. Cognitive radio technology can also play an important role in E-health applications [START_REF] Phunchongharn | A cognitive radio system for e-health applications in a hospital environment[END_REF], [START_REF] Feng | Providing telemedicine services in an infrastructure-based cognitive radio network[END_REF]. These aforementioned works are not suitable for post-disaster situation and can not be directly implemented in such scenarios. Consequently, there is a need to exploit inherent features of cognitive radio technology and tailor them to be well operated for disaster response networks. Thus, keeping altogether in mind; the adaptive and inherent self-organizing capabilities of cognitive radio devices [START_REF] Haykin | Cognitive radio: Brain-empowered wireless communications[END_REF], their potential applications, and recent advancement in hardware technology [START_REF] Zhang | A reconfigurable radio architecture for cognitive radio in emergency networks[END_REF], make the cognitive radio technology the most suitable radio access technology for challenged environments. In this architecture, we consider partially destroyed networks as primary networks and their nodes as primary nodes. Indeed, our objective is to detect on-going communications of the partially destroyed infrastructures in order to offer them connectivity to other parts of the same infrastructure or even to the Internet. It is clear that interconnecting different type of networks using different technologies can be considered as a challenging task, however, the flexibility and dynamic spectrum management offered by CRN can help to overcome these obstacles. In such kind of situations non-CR devices can be considered as PR nodes, since they are the users of the network with high priority and their communication can not be affected. Non-CR devices need to communicate with the CR devices in order to restore their connectivity to other parts of the network and Internet. If they detect disconnectivity to other non-CR devices, Access Points, sink, base station or Internet, some how the non-CR devices has be have a mechanism to detect the bad performance of their network, then they contact CR devices. Practically, when non-CR devices, need to communicate with CR devices, they first need to detect them. To achieve this goal, CR devices can advertise their presence to non-CR devices. Moreover, CR devices have to overhear the channels in order to know if the data transmitted by a non-CR device is for another non-CR device or for a CR device -to reach the Internet. This architecture can be operated in two scenarios: single-hop and multi-hop. CR devices communicate directly with the cognitive multi-radio mesh routers in single-hop scenario, while in multi-hop scenario, CR devices create multi-hop path to reach to the nearest cognitive multi-radio mesh router.

Architecture

In Fig. 2 we show a practical use case of our framework. In the shown scenario, our architecture acts as a gateway able to federate various existing infrastructures and restore their connectivity to Internet. We now describe individually the functionality of the framework components.

INTERNET COGNITIVE RADIO BASED INTERNET ACCESS FRAMEWORK FOR DISASTER RESPONSE NETWORKS

Cognitive Radio (CR) Devices

Cognitive radio devices which are based on software defined radio can access any cognitive multi-radio mesh router to upload their data to the Internet. These devices can be mobile and are capable to directly communicate with the cognitive multi-radio mesh router in single-hop fashion, they can also create multi-hop network to reach nearest cognitive multi-radio mesh router.

In single-hop scenario, cognitive radio devices are not responsible for their channel selection decision, instead cognitive radio devices will provide feedback to the cognitive multi-radio mesh router about the spectrum occupancy. Cognitive multi-radio mesh router will then make an intelligent decision about channel selection and communicate them to CR devices in order to be used for data transmission.

In the multi-hop scenario, the accessibility of CR devices to the cognitive multiradio mesh router is quite challenging due to lack of any centralized authority. Thus, CR devices are responsible themselves to collect the locally inferred spectrum related INRIA information and make a channel selection decision alone to reach the cognitive multiradio mesh router. Therefore, an intelligent channel selection techniques should be employed that facilitates CR devices in their channel selection decision. In multi-hop scenario, cognitive radio devices should be equipped with spectrum fluctuation monitor to support intelligent spectrum decision (cf. section 3.1.2, fig. 3).

Basically, cognitive radio devices will be deployed in order to achieve two goals. The first one is to relay the data of the heterogeneous networks and/or devices to the Internet and the second one is to provide connectivity to the disjoint networks i.e. non-CR devices. In the latter case, when CRNs deployed with partially destroyed networks to provide connectivity, CR devices will first perform the discovery of the partially destroyed networks i.e. infrastructure discovery and then tune themselves to the appropriate operating frequency of the disjoint network. In this manner, CR device will help the disconnected network to restore their connectivity.

More precisely, when CR devices are deployed in an area, they first perform a neighborhood discovery. Thus, CR devices will discover still alive non-CR devices. In the meantime, non-CR devices will learn the presence of CR devices in the form of new neighbors. Note that this process can be completely transparent to non-CR devices and may not necessitate any reconfiguration. One example is if a non-CR device after the disaster becomes disconnected from the whole network, with the arrival of one or more CR devices, the connectivity of that non-CR device can be re-established.

Spectrum Opportunity DataBase

Cognitive Multi-Radio Mesh Routers (CMRs)

Cognitive multi-radio mesh routers will be deployed in fixed locations. The main responsibility of these cognitive multi-radio mesh routers is to perform inter-communication between cognitive radio devices and internet portal point to facilitate data transfer and connectivity to Global Internet.

These cognitive multi-radio mesh routers can operate in two scenarios: (1) singlehop, and (2) multi-hop. In the single-hop scenario, cognitive multi-radio mesh routers perform channel monitoring, keep track of the spectrum occupancy, generate spectrum opportunity map [START_REF] Yucek | A survey of spectrum sensing algorithms for cognitive radio applications[END_REF] and facilitate cognitive radio devices in their reliable channel selection decision. Therefore, in this context, cognitive multi-radio mesh routers are responsible for channel assignment of the CR devices too. In single-hop scenarios, it may happen that non-CR devices generate concurrent transmissions over the spectrum. Thus, cognitive multi-radio mesh routers have to monitor the spectrum, perform sensing to detect free channels, and implement a scheduling algorithm to regulate the transmissions from CR neighbors to cognitive multi-radio mesh routers in such channels, limiting thus the contention. A simple polling mechanism as the one proposed in the IEEE 802.11 standard can be used here to schedule transmissions between CR's and cognitive multi-radio mesh routers. Single-hop scenario can be further classified into standalone approach and coordinated approach, based on the way spectrum opportunities are generated and distributed, as explained hereafter.

In the multi-hop scenario, cognitive multi-radio mesh routers are responsible for data relaying, as well as they will also implement scheduling algorithm to order the transmissions among their CR neighbors, and to limit contention.

The monitoring of the spectrum and generation of spectrum opportunity map by the cognitive multi-radio mesh routers can be done in two fashions:

• Standalone Approach: In this approach, cognitive multi-radio mesh routers themselves monitor the spectrum fluctuations without any feedback from or coordination with the CR devices. Moreover, cognitive multi-radio mesh routers can coordinate with other cognitive multi-radio mesh routers to share spectrum monitoring related information. In this manner, cognitive multi-radio mesh routers maintain a database of the corresponding geographic area and the designated radio spectrum.

• Coordinated Approach: In this approach, cognitive multi-radio mesh routers generate and maintains spectrum opportunity map by getting the feedback from cognitive radio devices. These cognitive radio devices that are disperse around the vicinity of cognitive multi-radio mesh routers detect radio spectrum activity and sends this information to the nearest cognitive multi-radio mesh routers. This information contains the channel id, channel utilization time, frequency of the channel, etc.

Irrespective of any approach adopted by the cognitive multi-radio mesh routers i.e. standalone or coordinated approach in single-hop context only, the collected information about spectrum occupancy will be first analyzed by Spectrum Fluctuation Monitor, which is then stored in Spectrum Opportunity Database. This database can then be used to make predictions about the spectrum utilization. Fig. 3 shows the function of a Spectrum Fluctuation Monitor maintained over the cognitive multi-radio mesh routers. Then based upon this, an intelligent spectrum decision can be perceived by the cognitive multi-radio mesh routers and will be communicated to the cognitive radio devices to help them select reliable channels (cf. section 5 for more details). Moreover, cognitive multi-radio mesh routers are also responsible to take care of the contention over the medium.

Internet Portal Point

Internet Portal Point are devices that serves as gateways to the Internet. These devices can be stationary or mobile; equipped with powerful communication medium, for e.g. satellite-link. They are responsible for sharing Internet bandwidth to, as well as gathering data from, cognitive multi-radio mesh routers and transfer it to the Internet.

INRIA

Working Principle

Initially the network is deployed having a single internet portal point device. This device should be connected with the global Internet through the satellite link. In the vicinity of this internet portal point, fixed cognitive multi-radio mesh routers are deployed which are directly connected with the internet portal point. Internet portal point shares the Internet connection with these cognitive multi-radio mesh routers. In order to increase the coverage area and provide last-mile connectivity, more cognitive radio devices can be deployed in multi-hop fashion to reach to internet portal point via cognitive multi-radio mesh routers. Then, cognitive radio devices are deployed in such a manner that they co-ordinate with the partially destroyed network nodes and help them to restore their connectivity, provide Internet accessibility or relay their data to the global Internet.

In this manner, the cognitive radio devices first discover the partially destroyed existing infrastructure through spectrum sensing and resource discovery mechanisms, which we will discuss in section 4. Once detected, they forward the data of the partially destroyed network to the nearest cognitive multi-radio mesh router which further relay it to the central internet portal point and finally this data reaches to the global Internet.

Application Scenarios and Advantages

In a post disaster situation, one may have information from the partially destroyed existing infrastructures in order to have insights about the catastrophe area. For e.g., getting connected to a sink node of an smart camera network can play a vital role in rescuing lives in the area (cf. Fig. 4, the 2nd plane).

Another example in a post-disaster situation could be a static sink deployed in a wireless sensor network to collect the sensed information that may lose the connectivity to the Internet. And some how the collected data has to be delivered to a base station that will process it. In order to deliver this data to the base station, Internet connectivity is required. In addition, after the poster disaster situation, it might happen the reachability of humans to the region where the sink is located, might be hard to achieve or not be possible. Self-deploying mobile cognitive radio devices can facilitate this access by providing Internet connectivity to the sink.

An important advantage of the proposed architecture is that cognitive radio devices can be able to access real updates about weather forecast or seismic forecast of the post-disaster area from the natural disaster tracking system [2] and Geographical Information Systems (GIS) [1]. Once they have this information, they can help rescue team members by guiding them towards safe passages and help them to reach to the nearest rescue base stations. Fig. 4 shows different applications of the proposed framework, where it can restore the connectivity of distinct network entities and connect them to Global Internet.

Deployment and Connectivity: Issues and Challenges

We now discuss how the proposed framework address the issues and challenges concerning the deployment and connectivity of the CR devices to restore the connectivity of partially destroyed networks and to connect them to global Internet.

Network Deployment and Connectivity

Depending on the application requirements, the deployment of cognitive radio devices may exhibit different network topologies: (1) single-hop (centralized), and (2) multihop (ad-hoc). Besides, traditional self-deployment techniques [START_REF] Kermarrec Kévin Huguenin | Route in mobile wsn and get self-deployment for free[END_REF] can add extreme value to the deployment of cognitive radio devices. When the cognitive radio devices are deployed in ad-hoc fashion and they create multi-hop network to reach the cognitive multi-radio mesh router, the main issue is regarding their connectivity. In fact, cognitive radio devices must select reliable channels in order to ensure their connectivity. Otherwise, a CR device that intends to upload its data to the Internet may not be able to find relaying CR devices and a delay may occur which is undesirable in post disaster situations. Moreover, without any intelligent channel selection strategy, there will be contention and collisions, which results in packet losses. Thus, to deal with these issue, we propose to use our channel selection strategy SURF [START_REF] Husain Rehmani | Toward reliable contention-aware data dissemination in multi-hop cognitive radio ad hoc networks[END_REF] in conjunction with the proposed framework. SURF provides a good level of connectivity and is well suited for these scenarios (cf. Section 5 for more details).

Infrastructure Discovery

Infrastructure discovery is another important aspect that need to be considered. Primarily because the deployment of the proposed framework depends on the knowledge of network that was operating previously. Insights such as whether the previously deployed network works with Base Stations (BS) or not, in ad-hoc mode or decentralized mode, with a sink, on which frequency, etc can aid the initial deployment and configuration of the proposed framework. Infrastructure discovery means the identification of the existing infrastructure, such as wireless sensor networks' nodes and sink, WiFi access points, GSM base stations, etc. This infrastructure discovery can be done by INRIA using advanced methods that relies on Software Defined Radio (SDR) [START_REF] Yucek | A survey of spectrum sensing algorithms for cognitive radio applications[END_REF] technology which scans the radio spectrum, search for beacons and radio signals, and identify the presence of any radio device.

In order to restore the connectivity of the partially deployed fixed telecommunication infrastructure like GSM base stations, prior knowledge about the deployed infrastructure is required. This will facilitate to analyze how much CR devices should be deployed and in which geographic region they should be deployed. The real challenge is in restoring the connectivity of networks where prior knowledge of the deployed infrastructure is not available. For instance, WLANs, that operates in the ISM band and can be heavily deployed in urban city regions and office buildings. Thanks to the inherent capabilities of cognitive radio devices and methods such as [START_REF] Miller | Service discovery and device identification in cognitive radio networks[END_REF], [START_REF] Damljanovic | Cognitive radio access discovery strategies[END_REF], the service discovery and identification of the available communication technology, such as Bluetooth, WiFi, is now possible. Moreover, these techniques can be also used to identify and distinguish different operating devices including Bluetooth piconets, individual Bluetooth devices, WiFi access points, sensor nodes, PDAs.

Inter-network Coordination

Inter-network coordination means how the cognitive radio devices communicate with distinct network entities. This challenge is addressed in the proposed framework by exploiting the inherent capabilities of CR devices. For instance, during the infrastructure discovery phase, CR devices already aware of distinct network entities and their operating frequency. Thus, to communicate with a distinct network entity, for example, a sensor node, a cognitive radio device will tune itself to the sensor nodes' operating frequency. In this manner, cognitive radio device have to select one channel to communicate with sensors and other channel to communicate with cognitive radio devices or cognitive multi-radio mesh routers.

Channel Selection Strategy SURF for CR Devices and

CMRs

When CR devices wants to upload their data to the Internet, they are required to communicate with the cognitive multi-radio mesh router over a particular channel. Without any intelligent channel selection strategy, concentration of all the cognitive radio devices over a particular channel could lead to contention and collision problems, which further reduces the connectivity to the global Internet. Thus, channel selection plays a vital role in efficient and reliable data relaying to the cognitive multi-radio mesh router and/or between to cognitive radio devices which operates in multi-hop fashion to reach the cognitive multi-radio mesh router.

In scenarios where cognitive multi-radio mesh routers are responsible for channel assignment to CR devices, a channel selection strategy proposed by us [START_REF] Husain Rehmani | Toward reliable contention-aware data dissemination in multi-hop cognitive radio ad hoc networks[END_REF][START_REF] Husain | Channel assortment strategy for reliable communication in multi-hop cognitive radio networks[END_REF] could be executed by the cognitive multi-radio mesh routers. Here, the mode of communication between the cognitive radio devices and cognitive multi-radio mesh routers is single-hop. But, when cognitive radio devices communicate with other cognitive radio devices and create a multi-hop network to reach to cognitive multi-radio mesh routers, the task of relaying data to the cognitive multi-radio mesh routers will be much more challenging. This is due to the diversity in the number of available channels and lack of any centralized authority. Therefore, keeping these challenges in mind, more recently we proposed a channel assortment strategy SURF [START_REF] Husain Rehmani | Toward reliable contention-aware data dissemination in multi-hop cognitive radio ad hoc networks[END_REF][START_REF] Husain | Channel assortment strategy for reliable communication in multi-hop cognitive radio networks[END_REF]. SURF channel assortment is performed in a distributed way and is based only on information locally inferred by CR devices.

Performance Evaluation

To evaluate the feasibility and usability of the framework, we use SURF [START_REF] Husain Rehmani | Toward reliable contention-aware data dissemination in multi-hop cognitive radio ad hoc networks[END_REF], [START_REF] Husain | Channel assortment strategy for reliable communication in multi-hop cognitive radio networks[END_REF] to be implemented by CR devices to relay data towards cognitive multi-radio mesh router. and our strategy (SURF), when channels=5 and channels=15, for varying number of cognitive multi-radio mesh routers.

Simulation Environment

We consider a post-disaster scenario in which the existing infrastructure is partially destroyed but still there are some alive non-CR devices that need Internet connectivity to deliver emergency messages, alerts or wants to deliver their data to the Internet (cf. bottom plane of Fig. 4). In order to restore the connectivity and to help the rescue team members, we deploy an ad-hoc cognitive radio network in which CR devices communicate in multi-hop fashion in order to reach the nearest cognitive multi-radio mesh router. These cognitive mesh routers are deployed randomly and upload this data to the Internet via internet portal point.

First, the channel selection phase starts in which CR devices execute SURF [START_REF] Husain Rehmani | Toward reliable contention-aware data dissemination in multi-hop cognitive radio ad hoc networks[END_REF][START_REF] Husain | Channel assortment strategy for reliable communication in multi-hop cognitive radio networks[END_REF] and select the best channel for transmission and/or overhearing. The message dissemination phase then starts, in which a randomly selected CR device, who received the data from the non-CR device, disseminates the message on the selected channel by setting the TTL. CR neighbor devices that are on the same selected channel will overhear the message, decrease TTL, redo the spectrum sensing, select the best available channel, and disseminate the message to the next-hop neighbors until TTL=0. In this INRIA manner, the message is traversed throughout the network and if at any stage, CR device and cognitive multi-radio mesh router are on the same channel, the message will be delivered to the cognitive multi-radio mesh router.

Reachability of Cognitive Multi-radio Mesh Routers

The data will be delivered to the Internet iff it is received by the one-hop neighbors of the cognitive multi-radio mesh router. The hop-by-hop delivery of this data is more difficult in the presence of PR nodes and multiple channels and it is difficult to guarantee that CR devices will have receivers when they transmit. Thus, in order to check the data is successfully delivered to one-hop neighbors of cognitive multi-radio mesh router, we calculate the average delivery ratio of message reached to one-hop neighbors of CMRs. Fig. 5 compares the average one-hop neighbors delivery ratio for random (RD) and our strategy (SURF), when channels=5 and channels=15, for varying number of cognitive multi-radio mesh routers. Note that in RD strategy, channels are randomly selected to be used by CR devices for transmission and/or overhearing, i.e. without any consideration to the ongoing PR and CR activity over these channels. SURF allows the average delivery ratio of 65% and 80% messages to the one-hop neighbors of cognitive multi-radio mesh routers in the network, compared to 65% and 40% in the RD case, for Ch=5 and Ch=15 respectively. When there is a increase in the number of channels i.e. Ch=15, SURF allows the average delivery ratio of 80% messages to the one-hop neighbors of cognitive multi-radio mesh routers in the network, compared to 40% in the RD case. In fact, this happens since during channel selection SURF considers both the PR nodes and number of CR neighbor receivers. These results show the good level of network connectivity provided by SURF, suitable for reliable data relaying.

Conclusion

In this paper, we have discussed that cognitive radio network can be served as a core technology which enables partially destroyed networks to restore their connectivity. In this regard, we presented a cognitive radio based Internet access framework for disaster response network deployment in challenged environments. This architecture is specially designed to cater the needs of challenged environments. We then highlighted issues and challenges in the deployment of this architecture. We believe that this work can be served as a basis to build new algorithms and protocols that lead us to federate various communication paradigms.

INRIA 3 AnFigure 1 :

 31 Figure 1: An Internet Access Framework for Future Cognitive Radio Networks

Figure 2 :

 2 Figure 2: A cognitive radio based disaster response network restore the connectivity of partially destroyed network to the global Internet.

Figure 3 :

 3 Figure 3: Function of Spectrum Fluctuation Monitor in CMRs.

Figure 4 :

 4 Figure 4: Cognitive radio based internet access framework helps distinct network entities to restore their connectivity to the global Internet.

Figure 5 :

 5 Figure 5: Comparison of average one-hop neighbors delivery ratio for random (RD)

RR n°7285


Dominique Raynaud
email: dominique.raynaud@upmf-grenoble.fr

Why Do Diffusion Data not Fit the Logistic Model? A Note on Network Discreteness, Heterogeneity & Anisotropy

Diffusion of innovations and knowledge is in most cases accounted for by the logistic model. Fieldwork research however constantly report that empirical data utterly deviate from this mathematical function. This chapter scrutinizes network forcing of diffusion process. The departure of empirical data from the logistic function is explained by social network discreteness, heterogeneity and anisotropy. New indices are proposed. Results are illustrated by empirical data from an original study of knowledge diffusion in the medieval academic network.

Compared with other aspects of diffusion research, there have been relatively few studies of how the social or communication structure affects the diffusion and adoption of innovations in a system [27, p. 25].

So speaks Everett M. Rogers, the outstanding promoter of diffusion studies, about the way they are connected to network analysis. In the 1970's, according to a content analysis of 1,084 empirical publications, diffusion networks represented less than one percent of diffusion research. Ten years ago, a book especially dedicated to network analysis has the same diagnosis:

Introduction

Diffusion of innovations is the process by which an innovation is communicated through certain channels over time among the members of a social system [27, p. 5]. Diffusion of knowledge may be defined in the same manner, replacing what should be in the previous definition. Social network analysis is in its early stages of application to diffusion issues.

Only few material coupling a diffusion study with network analysis is available [8, p. 189].

The authors consequently content themselves with classical studies in the field. The fact that different authors interested in the diffusion of innovations vs. network analysis have detected the same lack of research, vouches for a promising fieldwork.

A Brief Historical Sketch

Despite the fact that the first paper explicitly dedicated to network diffusion was written in 1979 by Everett M. Rogers [START_REF] Rogers | Network analysis of the diffusion of innovations[END_REF], the concern is much more ancient. For instance, in the course of his studies on the cholera, in 1884, Etienne-Jules Marey already applied network perspective to diffusion data. He had the insight that the topology of social network determines the form of the diffusion process. Marey says: "Closed institutions: prisons, boarding schools, convents, asylums, etc., usually escape to cholera; but if it gets into, it takes a terrible toll of victims" [20, p. 670]. Cliques (i.e. closed communities) exhibit atypical behaviour: they are resistant to the disease or completely devastated by the epidemic. The "clique effect" was independently rediscovered in 1973 by Mark S. Granovetter [START_REF] Granovetter | The strength of weak ties[END_REF]: "weak ties" favour diffusion, "strong ties" protect the members from a tentative adoption: either they all adopt, or they all reject.

The first book approaching the diffusion of innovations through network analysis came out in 1995 by a student of Rogers: Thomas W. Valente [START_REF] Valente | Network Models of the Diffusion of Innovations[END_REF]. His scope was to compare three classical datasets: the adoption of tetracycline by 130 physicians of the Middle West [START_REF] Coleman | The diffusion of an innovation among physicians[END_REF]; the diffusion of innovations among 692 Brazilian farmers [START_REF] Rogers | Diffusion of Innovation in Brazil, Nigeria, and India[END_REF]; the diffusion of family planning in 24 Korean villages [START_REF] Rogers | Communication Networks: Towards a New Paradigm for search[END_REF]. Held with fifteen years of hindsight, the book appears a little disapointing for seven chapters out of nine are in fact dedicated to apply thresholds and critical mass models to diffusion issues. Network analysis occupies thirty pages [35, p. 31-61], where classical measures of density, centrality and equivalence are processed out on the three datasets.

In the past decades, diffusion process have been simulated either within deterministic or probabilistic models [START_REF] Bailey | The Mathematical Theory of Epidemics[END_REF][START_REF] Kendall | Mathematical Models of the Spread of Infection[END_REF][START_REF] Hägerstrand | A Monte Carlo approach to diffusion[END_REF][START_REF] Cavalli-Sforza | Cultural Transmission and Evolution: A Quantitative Approach[END_REF][START_REF]Simulating Societies: The Computer Simulation of Social Phenomena[END_REF][START_REF]Modelling and Simulation in the Social Sciences from the Philosophy of Science Point of View[END_REF]. Researchers have explored a full range of simulations, including Monte Carlo, Ising, Potts, Krause-Hegselmann and Deffuant models [START_REF] Hägerstrand | A Monte Carlo approach to diffusion[END_REF][START_REF] Doreian | Mapping networks through time[END_REF][START_REF] Skillnäs | Modified innovation diffusion. A way to explain the diffusion of cholera in Linköping in 1866. A study of methods[END_REF][START_REF] Stauffer | Physics and mathematics applications in social science[END_REF][START_REF] Castellano | Statistical physics of social dynamics[END_REF]. However, more often than not, models presuppose the population to be homogeneous. Simulations are implemented on regular bi-dimensional lattices. Modeling rarely assumes the topology in which the diffusion occurs, and it is only in the 2000s that sociologists, economists and physicists addressed the point [START_REF] Cowan | Network Structure and the Diffusion of Knowledge[END_REF][START_REF] Guardiola | Modelling diffusion of innovations in a social network[END_REF][START_REF] Simonsen | Diffusion on complex networks: a way to probe their large-scale topological structures[END_REF][START_REF] Simonsen | Diffusion and networks: a powerful combination[END_REF][START_REF] Iribarren | Information diffusion epidemics in social networks[END_REF][START_REF] Baronchelli | Diffusive dynamics on weighted networks[END_REF]. The network-based approach of diffusion is full of consequences, some of which are still developing.

There is consequently little research on the irregularity of diffusion curves. The state-of-the-art is the following: 1/ Threshold models have relied the γ curve slope to higher or lower individual adoption thresholds [START_REF] Granovetter | Threshold models of collective behavior[END_REF][START_REF] Granovetter | Threshold models of diffusion and collective behavior[END_REF][START_REF] Valente | Social network thresholds in the diffusion of innovations[END_REF]. 2/ Critical mass models have shown that, the more the early majority members have a high centrality index, the faster the critical mass is reached, and the higher is the saturation threshold [START_REF] Oliver | A theory of critical mass, I. Interdependance, group heterogeneity, and the production of collective action[END_REF][START_REF] Valente | Network Models of the Diffusion of Innovations[END_REF]. 3/ In a forthcoming paper, we find, with no supplementary details, that "important consequences of this large variability [of human behaviour] are the slowing down or speed up of information" [18, p. 6].

Diffusion irregularity is not the main concern of papers in statistical physics that closely combine network analysis with diffusion processes. They consider instead: 1/ critical points for avalanches [START_REF] Guardiola | Modelling diffusion of innovations in a social network[END_REF]; 3/ random walks, qua they provide network topology characteristics [START_REF] Simonsen | Diffusion on complex networks: a way to probe their large-scale topological structures[END_REF]; 4/ modularity-based partitioning of graphs [START_REF] Simonsen | Diffusion and networks: a powerful combination[END_REF]; 5/ mean-field theory applications [START_REF] Baronchelli | Diffusive dynamics on weighted networks[END_REF]. An overview of the current research would say that diffusion is basically seen as a means to find network properties. Hence, the literature is still lacking for network-based studies that could answer the long-delayed question of diffusion anomalies.

The Logistic Function

The choice of the mathematical model accounting for diffusion depends on the empirical conditions of spreading. If the empirical process is a step-by-step diffusion through interpersonal contacts, it follows the logistic function, which was first discovered in 1838 by Pierre-François Verhulst-albeit he never used the term [START_REF] Verhulst | Notice sur la loi que la population suit dans son accroissement[END_REF]. In the recent years, there was a propensity to emancipate from his formalism; see [START_REF] Cavalli-Sforza | Cultural Transmission and Evolution: A Quantitative Approach[END_REF]. In the following equation, the term e -γt is the most characteristic of the process:

n t = N 1 + ae -γt (1)
n t represents the cumulative number of individuals having adopted at time t; N the number of susceptible adopters in the given population; a is a parameter setting the number of early adopters; γ the slope of the curve at the inflection point (when γ → 0, the curve is flat).

The bell-shaped first derivative represents the instant number of adopters at time t. The second derivative is swing-shaped. First and second derivatives respond to equations (2) and (3) respectively:

dn dt = γN ae -γt 1 + ae -γt (2)
d 2 n dt 2 = γ 2 N ae -γt (ae -γt -1) (1 + ae -γt ) 3 (3)
This approach provides a natural classification of adopters through diffusionbased concepts. Introducing N in the equations, we find that-whatever be parameters a and γ-early adopters, early majority, late majority and laggards appear at exactly 0.21, 0.5 and 0.79 of the susceptible population. These values are somewhat different from those given in Rogers' influential book [START_REF] Rogers | Diffusion of Innovations[END_REF], and afterwards endlessly repeated in the literature. According to him, early adopters, early majority, Fig. 1: The logistic function and its derivatives late majority and laggards appear respectively at 0.16, 0.5 and 0.84 of the susceptible population.

The reason for such a disagreement is that the classification of adopters is envisaged through common statistical concepts. The logistic first derivative is assimilated to a normal distribution. Rogers' values are in fact those of the mean µ and µσ 2 , µ + σ 2 . Valente is even more explicit:

The logistic function has an inflexion point at 50 % adoption and two second-order inflection points, one each at one standard deviation below and above the mean [35, p. 83].

Standard deviation concept is inappropriate in this context: logistic function is not a Gaussian distribution. There is a simple visual proof for that: respective curves cross several times with each other, as in Fig. 1 (b). As a consequence, the values 0.16, 0.5 and 0.84 must be discarded and replaced by 0.21, 0.5 and 0.79.

Empirical Data

Does the logistic function fit the diffusion data? Compared to fieldwork data, logistic law rather appears as a mathematical ideality. In fact, curves never exhibit so a smooth and regular profile. Let us begin by the fact fieldwork studies constantly report that curves of diffusion are affected by irregularities. One can find in Valente's valuable book [START_REF] Valente | Network Models of the Diffusion of Innovations[END_REF] a report on such irregularities (Fig. 2).

Such anomalies are evidently not accountable within the logistic model. We owe to Rapoport and Yuan the first penetrating remarks. While reaching the conclusion that "actual processes can be approximated by equivalent epidemics in well-mixed populations or by equivalent random social nets," they are nevertheless warning us that this conjecture "does not apply to highly structured populations" [24, p. 344-345]. The gap between the model and the real world lies in the assumption that societies are "well-mixed populations," thus assimilating the adoption of innovation to a random draw. Social network heterogeneity urges to abandon this assumption, which is the basis of all SIR-susceptible/infective/removed-epidemiological models.

During the 2000s, statistical physicists took part in the debate, by criticizing the logistic model as "utterly inaccurate" [START_REF] Newman | The spread of epidemic disease on networks[END_REF]. They have again argued that standard epidemiological models do not take into account that diffusions happen in highly structured, heterogeneous population, whose topology influences the very form of the diffusion [START_REF] Watts | Collective dynamics of small word networks[END_REF][START_REF] Moreno | Epidemic outbreaks in complex heterogeneous networks[END_REF][START_REF] Newman | The spread of epidemic disease on networks[END_REF]. This observation put the answer at hand.

Accounting for Anomalies

Let us extract empirical data from a recent study of knowledge diffusion within the academic network of medieval universities (XIIIth-XIVth centuries). In this special case, the social network is represented by a deterministic articulated k + -regular graph [START_REF] Raynaud | Etudes d'épistémologie et de sociologie des sciences, 2. Pourquoi la perspective a-t-elle été inventée en Italie centrale?[END_REF]. This graph G =( V, E) is particularly fitted for the study of diffusion anomalies, because it is little dense: δ = /(g(g -1)) = 0.069 and little cohesive:

χ =(2 ∑ g i=1 ∑ g j=1 x ij / (v i , v j ) ⇒ (v j , v i ))/(g(g -1)) = 0.047.
In the following sections, these data will be used to illustrate theoretical findings.

The deviation of diffusion curves from the logistic model appears by superimposing the curves that have any vertex of the graph as emitter (Fig. 3). Since the set is heterogeneous, we may decompose it into subsets. Let us for instance isolate all curves whose receptor belongs to component P 7 (Fig. 4).

We are now in position to investigate the main causes why empirical diffusion curves deviate from the logistic function. Let us call, by license, "fast diffusion" any diffusion that converts many vertices in few steps; "slow diffusion" the one that eiher converts few vertices, or requires many steps to convert them all. Analytical concepts presented hereinafter are devised to fit diffusion networks that are always directed graphs and, more often than not, grounded networks-i.e. dependent on the position of vertices in space.

Net Discreteness

Discreteness of social networks results in slowing down/accelerating adoption, hence flattening/straightening the diffusion curve.

The more obvious difference between the logistic function (Fig. 1) and empirical curves (Fig. 3 and4), is that the former is a smooth curve, when the latter is angled. While the logistic function is defined on a continuous (infinite) set, social diffusion happens within discrete (finite) structures. The lower the number of susceptible adopters, the more angled the curve.

There is a simple estimate for network discreteness. Let us call v i the emitter vertex of any given diffusion process. The number of diffusion steps will be equal to the lenght of the longest geodesic d ik originating in v i . Local discreteness ranges from 0 when d ik = ∞, to 1 when d ik = 1, hence:

D i = 1 max (d ik ) D i ∈ [0, 1] (4)
If we need a comparative index, we first calculate the mean discreteness D Gwhere g is the total number of vertices-, then the difference

D i = D i -D G : D i = 1 max (d ik ) - 1 g g ∑ j=1 1 max (d jk ) D i ∈ [-1, +1] (5)
Local discreteness is null if the geodesic on which the vertex stands is as long as the graph mean geodesics. Positive values occur if D i D G , when the region in which the information is going through is less dense than the rest of the graph, thus slowing down the diffusion; negative values otherwise. Discreteness values on the academic network are given in Appendix (columns D i and D i ). The data (ROS, 0.111, -0.048) are to be read as: "All vertices standing on the longest geodesic attached to ROS, i.e. {ROS, KOL, STR, DIJ, AST, GEN, PIS, SIE, PER, TOD, ROM} have discreteness 0.111 or, equivalently, are 0.048 less discrete than the rest of the graph."

Net Heterogeneity

Heterogeneity of social networks results in slowing down/accelerating adoption, hence flattening/straightening the diffusion curve.

Let us consider anew all curves of diffusion (Fig. 4). At t = 2, the curves, which were hitherto undifferentiated, split into five distinct profiles. The message from DIJ is adopted by six new vertices (fast growth); the one from ESZ is adopted by only two new vertices (slow growth). This difference is due to the fact the first message is diffused within two distinct subsets, when the second message never leaves the starting subset, composed of few susceptible adopters. The diffusion growth is as fast as the conversion rate. It is only when the message gets into new components of the network that it can cause mass adoption. Consequently, slow and fast phases are sensitive to articulators.

Network forcing is detectable by visual inspection. Let us consider STR vs. FLO as emitters. Two steps after he has quitted STR, the message propagates at constant rate e i t = 5 (Fig. 5). In the meanwhile, after having been constant until t = 3, FLO message adoption rate decreases to e i t = 0 (Fig. 6). Vertex STR connects immediately to two components, when FLO can join few vertices only. As a result, at t = 5, the message has touched 24 vertices (STR) vs. 12 vertices (FLO). Network properties subtending this contrastive behaviour are: STR articulator status and low transitivity (T = 0.166) vs. FLO confinement and high transitivity (T = 0.5), that is, high vs. low area heterogeneity.

The concept of social heterogeneity has become familiar since the discovery of "structural holes" by Peter Blau [START_REF] Blau | Inequality and Heterogeneity[END_REF]. Several methods exist to detect structural holes and heterogeneity in a graph [START_REF] Fararo | Biased networks and social structure theorems[END_REF][START_REF] Skvoretz | Salience, heterogeneity, and consolidation of parameters: civilizing Blaus primitive theory[END_REF]. We can proceed with by defining local density for vertex v i -thus adapting graph density δ G = L/g(g -1) to a local neighbourhood. Let us first define the neighbourhood as the circle of center v i and radius r = max (d ij ), equal to the Euclidean distance of the remotest vertex v j to which v i is connected (whatever be the direction of the arc). Let i be the outdegree of vertex v i , and k i the number of possible arcs capable of being built in this region. Local heterogeneity is:

H i = 1 - i k i H i ∈ [0, 1] (6)
If we prefer a comparative index, we first calculate the mean heterogeneity H G on the graph, then the difference H i = H i -H G :

H i = 1 - i k i - 1 g g ∑ j=1 1 - j k j
that is equal to :

H i = 1 g g ∑ j=1 j k j - i k i H i ∈ [-1, +1] (7)
This index is null when the region the information is going through is as dense as the whole graph. Positive values occur when H i H G , that is when the local region is more heterogeneous than the rest of the graph, thus slowing down the diffusion; negative values otherwise. See Appendix for academic network values (columns H i and H i ). For example, the data (ROS, 0.000, -0.323) are to be read as: "Vertex ROS has null heterogeneity or, equivalently, is 0.323 less heterogeneous than the rest of the graph."

Net Anisotropy

Anisotropy of social networks results in slowing down/accelerating adoption, hence flattening/straightening the diffusion curve.

Let us isolate curves originating in DIJ and ESZ, two vertices having the greatest difference among component P 7 . A good way to link irregularity of curves with network properties is to represent the message progression within the network by joining all vertices converted at the same time by "isochrones." Fast spreading is associated to even isochrones when slow diffusion is coupled with uneven isochrones. As a result, six to nine steps are needed so that DIJ and ESZ information could cover the same area (Fig. 7 and8). At any first steps, DIJ can distribute the message all around (quasi-isotropy), when ESZ can send information to its western neighbours only (anisotropy). This is a last factor explaining anomalies. As far as I know, network anisotropy has never been defined in network analysis literature. This concept could be derived from other fields of physics, as optics, electricity or magnetism, but in the special case of grounded social networks, there is a more direct method to define the concept of anisotropy. Suppose vertex v i has an outdegree i and let α mn be the angle of two adjacent arcs. The isotropic case arises when every angle is equal to 2π/ i . In order to appreciate anisotropy, we define the deviation of angle α mn from 2π/ i . Vertex local anisotropy will then be the sum of actual deviations divided by the sum of theoretical maximum deviations:

A i = α mn - 2π i + α no - 2π i + ...+ α sm - 2π i 2 ( i -1) 2π i
Since angles α mn , α no ... are supplementary, we may simplify:

A i = 2 max α mn - 2π i 2 ( i -1) 2π i ∴ A i = i max α mn - 2π i 2π( i -1) A i ∈ [0, +1] (8)
The comparative index is obtained as previously, by calculating the mean anisotropy A G on the graph (with g vertices), then the difference A i = A i -A G :

A i = 1 2π     i max α mn - 2π i ( i -1) - 1 g g ∑ j=1 i max α pq - 2π j ( j -1)     A i ∈ [-1, +1] (9)
Local anisotropy is null when the local region has the same degree of isotropy as the rest of the graph. Positive values occur in the case A i A G , when the region the message is going through is less isotropic than the rest of the graph, thus slowing down the diffusion; negative values otherwise. See Appendix for academic network data (columns A i and A i ). The data (ROS, 0.866, +0.388) are to be read as: "Vertex ROS has anisotropy 0.866 or, equivalently, is 0.388 more anisotropic than the rest of the graph."

A Test of DHA Indices

First of all, the definition of D (discreteness), H (heterogeneity) and A (anisotropy) enables us to tell the difference between regular and irregular graphs. In a 2D square lattice, all geodesics are infinite, the term 1/d ik is null and D = 0. Since all vertices are disposed regularly, and have the same outdegree, the term i /k i =+1 everywhere, thus H = 0. Finally, since angles of all adjacent arcs are equal, any term α mn = 2π/ i so that A = 0. We recognize a well known property: a lattice is a perfect infinite, homogeneous and isotropic network.

Social networks utterly differ from this model. Regarding the conditions of spreading in the same graph, DHA indices make it possible to see the regions where the diffusion is speeding up, and where it is slowing down. Let us resume the discussion of the medieval academic network and compare the indices of all vertices (see Appendix). Network mean values are: discreteness D G = 0.159, heterogeneity H G = 0.323, anisotropy A G = 0.478. Because of the problem of sign combination, it is not appropriate to agregate directly DHA indices. General results are nonetheless accessible.

Maximum discreteness occurs for vertices in the graph innermost component {AST, MIL, PAD, VEN, GEN, BOL, PIS, FIR, SIE, RIM, PER} because several directed filters impede information to propagate outside the component, thereby reducing the number of steps of diffusion. Maximum heterogeneity occurs for vertices situated on the borders of the central component {AST, PIS, ROM, CHI, CIV} because those vertices are both in dense regions and in position to be tied to many vertices with which they have no actual relation. Maximum anisotropy occurs for the outermost vertices of the graph (DUB, ROS, ESZ, DJU) because they can send information only inwards the network.

All vertices are now sorted into eight classes, according to the sign of their indices (see Appendix, last column):

---{OXF, CAM, WIE} + --{MON, AVI, GEN, FIR, PAD} -+ -{PRA, ERF, RGB, STR, PAR, VAL, ASC, CHI The behaviour of classes (---) and (+++) is quite obvious. Other classes can either accelerate or slow down the diffusion.

A 3D-plotting (x = D, y = H, z = A) shows the wide dispersion of vertices on both HA axes (Fig. 9), while D seems to have a much more limited impact on how they are spatially distributed (Fig. 10). This limitation is not a general property. It is due to the academic network small diameter, φ = 9. I have plotted in light blue low-valued vertices, for which the corresponding vector has lenght x 0.300 {MAG, ERF, PRA, TOU, VAL, BOL, SIE, PER, TOD, ASC}. Accordingly, the impact of each node on the diffusion shape can be estimated by the Euclidean distance of any vertex v i of coordinates (D i , H i , A i ) to the plane Γ :

ω i = 1 √ 3 |-D i -H i -A i | (11)
As a result, this compounded index (Appendix, column ω i ) tells us how much the network vertex is contributing to the deviation from the logistic curve. When ω i sign is negative (yellow) the diffusion is accelerating, when it is negative (blue) the diffusion is slowing down (Fig. 11).

Conclusion

We are now in position to answer the issue adressed at the beginning of the chapter: Diffusion data do not fit the logistic model because social space is discrete, heterogeneous and anisotropic. Social space is thus an inadequate metaphor that should be outlawed. Any social spreading of innovations and knowledge is networkdependent. The agenda for future research should plan to: 1/ test DHA indices robustness-especially the concept of "net anisotropy" presented in these pages, 2/ focus on how DHA indices could predict the precise shape of a diffusion process occuring in a given social network and, conversely, 3/ deduce, from any empirical data on social diffusion, the DHA indices of the social network in which the diffusion takes place.

Fig. 2 :

 2 Fig. 2: Diffusion curves irregularity.

Fig. 3 :

 3 Fig. 3: Diffusion (any receptor) Fig. 4: Diffusion (receptor ∈ P 7 )

Fig. 5 :

 5 Fig. 5: Fast diffusion from STR Fig. 6: Slow diffusion from FLO

Fig. 7 : 8 :

 78 Fig. 7: Fast diffusion from DIJ Fig. 8: Slow diffusion from ESZ

Fig. 9 :

 9 Fig. 9: DHA dispersion of vertices Fig. 10: D index limited impact

Fig. 11 :

 11 Fig. 11: DHA values

  , CIV} --+ {LIS, SEV, SAL, TOU, ANG, DUB, ROS, ESZ, DJU, REG, PAL} ++-{DIJ, BOL, SIE, PER, ASS, TOD} + -+ {MIL, VEN} -++ {MAG, KOL, BAR, NAP} +++ {AST, PIS, ROM, RIM}