Ismail Ktata

Fakhreddine Ghaffari

Bertrand Granado

Mohamed Abid

Prediction Performance Method for Dynamic Task Scheduling, case study: the OLLAF Architecture

Keywords: Dynamically Reconfigurable Architecture, OLLAF, uncertainty variation, predictive scheduling

Actual dynamic applications, executed on real-time systems, have the tendency to be built on dynamically reconfigurable hardware devices. These applications require high performance and flexibility towards user and environment needs. To perform these application requirements, efficient mechanisms to manage hardware device must exist. In this paper we target OLLAF as a dynamically reconfigurable architecture which is designed to support complex and flexible applications. In order to deal with all of the dynamic aspects of such systems, we describe a predictive scheduling allowing an early estimation of our application dynamicity. A vision system of a mobile robot and an application of 3D synthesis images were served to validate the presented scheduling approach.

I. Introduction

Embedded systems are presented around us in automobiles, robots, planes, satellites, industrial control systems, etc. They offer enormous opportunities for novel functionalities but, at the same time, system complexity is increasing and the actual methods and tools are immature, or

have not yet been adapted to. In addition, the today applications have a dynamic behavior which is managed only in software as actual hardware targets are still static. To overcome these problems, designers tend to use dynamically reconfigurable architectures (DRA) that are well suited to deal with the dynamism of applications and allow better compromise between cost, flexibility and performance [START_REF] Noguera | Multitasking on reconfigurable architectures: Microarchitecture support and dynamic scheduling[END_REF]. Such architectures increase the complexity of the applications design. This complexity could be abstracted at run time by providing an operating system that abstracts the lower level of the system [START_REF] Garcia | OLLAF: a Fine Grained Dynamically Reconfigurable Architecture for OS Support[END_REF]. This operating system has to be able to respond rapidly to events. In this paper, we are interested in the scheduling of applications that could be executed on dynamically reconfigurable architectures and in particular in predictive scheduling. The reason why prediction is becoming an important objective is the recent focus on large systems that can be dynamic and where uncertainty in terms of execution time or resource usage can be very important.

The remaining of the paper is organized as follows. In Section II we introduce a brief review about the context and problematic revealed. Several works dealing with scheduling approaches for flexible and dynamic systems are detailed in Section III. The new proposed approach of predictable scheduling technique is described in Section IV. In Section V we present an example of our method applied to a vision system of a mobile robot. Finally, conclusion and future works are given in Section VI.

II. Problem Definition

Our goal is an efficient management of dynamically reconfigurable architectures; more precisely, as case study, we target the OLLAF architecture. OLLAF, as presented in [START_REF] Garcia | OLLAF: a Fine Grained Dynamically Reconfigurable Architecture for OS Support[END_REF], is an original FGDRA specifically designed to enhance the efficiency of OS services necessary to manage such architecture. From the global view (figure 1), OLLAF has a reconfigurable logic core organized in columns. Each column can be reconfigured separately and offer the same set of services. A task uses an integer number of columns and can be moved from one column to another without any change on the configuration data [START_REF] Garcia | OLLAF: a Fine Grained Dynamically Reconfigurable Architecture for OS Support[END_REF]. Each column provides a hardware configuration manager (HCM) and a local cache memory (LCM). Configurations have to be placed in advance in the local cache memory. In the first prototype, those memories can store 3 configurations and 3 contexts. The associated service running on the micro-processor will thus need to take into account and prefetch task configuration on the columns where it might most probably be placed. The reconfigurable logic core uses a double memory plan. With this topology, the context of a task can be shifted in while the previous task is still running and shifted out while the next one is already running. The effective task switching overhead is then taken down to one clock cycle. In [START_REF] Garcia | OLLAF: a Fine Grained Dynamically Reconfigurable Architecture for OS Support[END_REF], authors showed some cases studies which demonstrate that the OLLAF architecture can perform a greater efficiency than the one performed using a traditional commercial FPGA. Our intervention is then to make a dynamic and predictable scheduling to better manage a dynamic real time application executed on such architecture. Being able to predict in most cases the future task that will run in a particular column will permit to take even better advantage of the context and configuration management scheme proposed in OLLAF. Uncertainty in scheduling may arise from many sources [START_REF] Davenport | A Survey of Techniques for Scheduling with Uncertainty[END_REF]. In our research, we will consider three cases:

-Tasks execution time uncertainty: Variability in the execution time requirement of real time tasks is common in actual real time systems. For real time tasks, meeting deadlines is important. Traditional scheduling algorithms schedule real time tasks assuming that each task requires the worst case execution time (WCET). This is a pessimistic approach since tasks are rarely executed via their WCET [START_REF] Singh | Co-Scheduling Variable Execution Time Requirement Real-Time Tasks and Non Real-Time Tasks[END_REF].

-Dynamical creation of multiple instances of a task: As hardware resources are limited in embedded systems, redundant copies are considered only for software tasks [START_REF] Girault | A scheduling heuristics for distributed real-time embedded systems tolerant to processor and communication media failures[END_REF]. With its hierarchical memories, OLLAF architecture has overcome this problem.

-Resources failure:

The goal in architectural reconfiguration is to modify the hardware topology by reallocating resources. In some situations, some resources become unavailable either due to a fault or due to reallocation to a higher priority task, or due to a shutdown in order to minimize the power usage. There is a need to predict such failure so that the system could react and failure does not disrupt the application process.

III. Related Work

To realize an efficient predictive schedule of an application, an operating system needs to know the behavior of this application, in particular the part where the dynamicity can be efficiently exploited on a DRA.

The different items of a scheduling problem are the tasks, the constraints, the resources and the objective function. Tasks execution must be programmed to optimize a specific objective with the consideration of several criteria. Many resolution strategies have been proposed in literature [START_REF] Brucker | Complex Scheduling[END_REF]. Usually these methods assume that execution times can be modeled with deterministic values. They use predictive schedule that gives an explicit idea of what should be done. Unfortunately, in real environments, the probability of a precomputed schedule to be executed exactly as planned is low [START_REF] Billaut | Multicriteria Scheduling: Theory, Models and Algorithms[END_REF]. This is because of, not only variations, but also because of a lot of data that are only previsions or estimations. It is then necessary to deal with uncertainty or flexibility in the process data. Hence, a significant reformulation of the problem and the solving methods are needed in order to facilitate the incorporation of this uncertainty and imprecision in scheduling [START_REF] González | Comparative Study of Meta-heuristics for Solving Flow Shop Scheduling Problem Under Fuzziness[END_REF]. In general, there are two main approaches dealing with uncertainty in a scheduling environment according to phases in which uncertainties are taken into account [START_REF] Davenport | A Survey of Techniques for Scheduling with Uncertainty[END_REF]. Proactive scheduling approach aims to build a robust baseline schedule that is protected as much as possible against disruptions during schedule execution. It takes into account uncertainties only in design phase (off-line). Hence, it constructs predictive schedule based on statistical and estimated values for all parameters, thus implicitly assuming that this schedule will be executed exactly as planned. However, this could become infeasible during the execution due to the dynamic environment, where unexpected events continually occur [START_REF] Davenport | A Survey of Techniques for Scheduling with Uncertainty[END_REF]. Instead of anticipating future uncertainties, reactive scheduling takes decisions in real-time when some unexpected events occur. A reference deterministic scheduling, determined off-line, is sometimes used and re-optimized. In general, reactive methods may be more appropriate for high degrees of uncertainty, or when information about the uncertainty is not available. A combination of the advantages of both precedent approaches is called proactive-reactive scheduling. This hybrid method implies a combination of a proactive strategy for generating a protected baseline schedule with a reactive strategy to resolve the schedule infeasibilities caused by the disturbances that occur during schedule execution.

Hence, this scheduling/rescheduling method permits to take into account uncertainties all over the execution process and ensures better performance [START_REF] Aytug | Executing production schedules in the face of uncertainties: A review and some future directions[END_REF] [START_REF] Herroelen | Project scheduling under uncertainty: Survey and research potentials[END_REF]. For rescheduling, the literature provided two main strategies: schedule repair and complete rescheduling. The first strategy is most used as it takes less time and preserves the system stability [START_REF] Vieira | Rescheduling manufacturing systems: a framework of strategies, policies and methods[END_REF].

In our case, we are dealing with hardware tasks scheduling for real time applications. We are concerned with soft realtime systems, such as telecommunication and multimedia, where the goal is typically to meet some Quality of Service (QoS) requirements. When developing the real time systems, it is often required to predict tasks properties of the application, especially the timing property [START_REF] Ganssle | Really Real-Time Systems[END_REF]. Usually, scheduling algorithms are based on the worst-case execution time (WCET) of a task. They assume that the WCET is known a priori. Unfortunately, in general, the worst-case input is not known and depends on some factors such as input data and available resources [START_REF] Wilhelm | The worst case execution time problem overview of methods and survey of tools[END_REF]. In general, scheduling algorithms focus on offline WCET estimation to use it at runtime. However, those investigations on WCET estimation are not optimal because, in most cases, real time tasks are not executing via their worst case execution times. Therefore, the improvements of efficient execution time analysis are still limited and the resources utilization is extremely high [START_REF] Hu | A Novel Gain Time Reclaiming Framework Integrating WCET Analysis for Object-Oriented Real-Time Systems[END_REF]. Instead of scheduling based on the worst case execution time as an upper boundary time elapsed for a task to execute, we prefer to get advantage of that characteristic and attribute, for each task, a dynamic online estimated value of execution time. The predictive algorithm will permit to schedule the different hardware tasks (T i ) and allocate its needed cells of the hardware DRA based on online estimated values.

IV. Proposed Approach

As we mentioned in section III, to realize a predictive scheduling we must exhibit the dynamic characteristics of an application. We consider three cases of dynamicity in applications:

(a) The number of tasks is not fixed. It may change from iteration to another.

(b) The tasks execution time may change too.

(c) The number of needed resources for tasks execution is variable. In addition, the number of available resources may decrease after a failure occurs.

For these cases, the goal is to develop a robust scheduling method that is little sensible to data uncertainties and variations between theory and practice.

Our first work in [START_REF] Ktata | Novel Approach for Modeling Very Dynamic and Flexible Real Time Application[END_REF] was to define a new model to represent dynamic applications features we considered. This model will be the input of the scheduler. At design time, the scheduler is able to distinct between two parts of the application: permanent branches (containing tasks that will be executed during the whole application runtime) and hazardous ones. Obviously, scheduler can take into account all dynamic features of the application presented in the model. Permanent tasks will be sorted respecting their precedence constraints (topological order). Its configuration data will be prefetched, as much as possible, on the columns making a maximum use of the whole of the architecture. This is to ensure minimizing the number of configuration data transfers and tasks relocation, and thus the time of saving and restoring process. From the model, the prediction service can identify tasks whose execution time is variable as well as hazardous tasks with possible multiple instances. At the design time, the execution times will be defined as WCET values and dynamic features will not be taken in the first period.

At run-time, there are three dynamic online features:

-Firstly, the graph precedence which is already presented by the graph but it can be modified as some nodes (i.e. tasks) may not be executed in some period. -Secondly, the new changed parameters of some tasks.

This includes execution time and instance number. -Finally, the resource availability which may change from one period to another depending on the tasks requirements and the fact that a resources failure may occur or not. After a task s execution and for uncertain parameters, the prediction technique will compute predicted values to be taken for the next execution. Tasks are executed at the earliest possible time. For many tasks activated at the same time, priority will be assigned according to Least Laxity First (LLF) policy. The LLF permits a dynamic priority assumption depending on the laxity which depends on the execution time (L= (D-R)-C); where D is the deadline, R is the ready time and C is the execution time. If there is equality between some tasks, task which has maximum execution time will have priority to be launched before the others.

The scheduler will proceed taking into account those features. It has to prefetch configurations data of new activated tasks in the columns that are available for executing and to find the possible way to integrate them in the current schedule without effect on performance. This schedule must rely on rapid algorithms based on a simple scheduling technique so that it can perform online execution with no overhead. In addition, on the reconfigurable device, resource failure may occur which will affect the resource availability. Thus, for some tasks, execution may occur or not depending on the available resources compared with needed ones. A variable, which is initialized as the total number of resources, will indicate the amount of remaining resources. From the ready list, LLF algorithm determines the tasks that can be executed on the reconfigurable device. Tasks with the higher priorities will be placed first until the area of device is fully occupied. If there are not enough hardware resources available, the Last Recently Used (LRU) strategy is used to select which tasks configuration data will be removed. Therefore, for a ready task, scheduler will compare its needed resources with the variable reflecting the available ones. If availability is satisfied, the configuration will be fetched on target resources. Otherwise, last recently executed tasks will free their columns until the needed resources will be satisfied. In the case that all executed resources have released their resources and the available resources still cannot fit the needed ones, the tasks in question will be delayed and scheduler goes to the next one. During run-time, and for dynamic parameters, historic values are stored and prediction is made for the next task s period. The choice will depend on the applications requirements and the accuracy of estimating methods. Prediction tested methods will be presented in next section.

V. Experimental Results

To validate our approach, we should make use of dynamic applications presenting uncertainty information. In [START_REF] Verdier | Using High-Level RTOS Models for HW/SW Embedded Architecture Exploration: Case Study on Mobile Robotic Vision[END_REF] and [START_REF] Loukil | Self adaptive reconfigurable system based on middleware cross layer adaptation model[END_REF] two image processing applications are represented. First one is a visual system embedded in a mobile robot, while the other is 3D synthesis images. In the first application, robot moves around and learns its environment to identify keypoints in the landscape. The keypoints correspond to the image filtered by difference of Gaussians. This application is dynamic in the sense that the number of keypoints is not known a priori and depends on the visual scene and on the robot movement if it is slow or fast or if it is stopped. For the application of 3D synthesis images, an object can be generated using various polygons number and different shade algorithm (Gouraud, flat, Phong) so with different visual qualities. For instance, in the application of 3D synthesis images, an object can be generated using various polygons number and different shade algorithm (Gouraud, flat, Phong) so with different visual qualities. Figure 2 shows time execution model based on off-line measures for the 3D application using flat shading method. In this section we will more focus on the vision system of a mobile robot as we dispose more experimental data of it. An experiment has been done with a pure software version of this application executed on a single microprocessor. As a consequent, we can divide application tasks in three groups:

-Intensive data-flow computation tasks that execute in a constant time, -Tasks whose execution number is correlated with the number of interest points, -Tasks with unpredictable execution time (depending on the images features). The figure 3 shows our proposed model for the robotic vision application. We can notice the presence of permanent branch (squared nodes) which represents permanent tasks that will be executed in all cases or modes (exp: T1, T14, T19). Tasks with unpredictable execution time are indicated by the asterisk (exp: T9, T11, T20). Another dynamic feature of tasks which execution number depends on the number of keypoints is indicated by the use of resource factor n (exp: T9, T10, T30).

For the prediction techniques of uncertain tasks features, we have studied the task of keypoints search. The provided measured execution times on representative samples are presented in the figure 4. As we can see, the values distribution is random. The elapsed time of keypoints search in an image depends on the number of keypoints that this image contains. So the execution time is correlated to the founded number of keypoints. For the fact this number is also random variable as shown in figure 5. The figure 5 shows the number of founded keypoints in the corresponding image over a sequence of more than 5000 images. where t i is a runtime instant and i={0,..n}.

Tested methods make statistical measurement based on a specific amount of previous succeeded instances of the same task that have been obtained by on-line monitoring. We do not use the whole historic as this need more memory size and is not useful in the prediction of such random values. The first method (a) uses the mean value of the three last real execution times. After making some successive estimations, the predicted values become almost constant and do not follow the graph evolution. The second method (b) uses the mean of the three last values multiplied by different weights. Weights are determined experimentally based on tested data to minimize estimation error. As in nonparametric regression techniques, the higher weights are assigned to the values closed to the actual parameter and lower weights to those more distant. The last two methods are more pessimistic and make overestimation of previous values: one (c) takes the maximum of the last three real values and the other (d) takes the last value increased by 5%. We use estimation error rate as a metric to compare those methods. Firstly, we notice that all methods lead, for the twenty tested images, to an overestimation of the execution time. The higher error rate is for the techniques (a) and (c). For (d), and even with a 1% increase of the last measure value, the error is still greater than the one of (b). Hence, the least obtained error percentage is the one related to the method using weighted average of last values (b). It provides a good prediction for the task execution time distribution. The mean error between estimated and simulated results is about 0.4% for low and medium frequency scales and about 2.45% for high frequency scale. Those results show that the technique based on a weighted average of the execution time values works with an accuracy of almost 98%. Even for keypoints number estimation (figure 5); the mean estimation error of the same technique is 0.406% for the whole 5000 images.

Figure 6 shows the error rate functions of the prediction of the keypoints number corresponding to figure 5. The presented function corresponds to the prediction method which uses the maximum value of last measures. The errors were calculated of over 1000 successive images. The mean error (indicated by a horizon line) is -6.5%. This technique presents significant advantage with a relative acceptable mean overestimation of 6.5% and less than 21% of the whole predicted values were underestimated. The purpose is that prediction be almost near real values and guarantee better compromise between requested QoS and efficient resources management. For this visual system application the latter estimation can assist the prediction engine for better scheduling analysis of real-time tasks and so better exploitation of the DRA like OLLAF.

VI. Conclusion

In this work, we aim at performing predictive scheduling of hardware tasks on OLLAF as a FGDRA. The proposed approach takes into account the hardware tasks uncertain characteristics, the available resources in the target device and the quality of service of the application. We have presented the scheduling method with the use of a prediction method enabling better adaptation of the architecture to the environment variations. To validate the proposed scheduling method, we have used a case of an image-processing application of a visual system embedded in a mobile robot. Such application shows dynamically variable characteristics that are unpredictable without an entire a priori knowledge on the environment. We have demonstrated that with our modeling we can realize an efficient predictive scheduling on a robot vision application with a mean error of 6.5%. Future works will consist in integrating our scheduling approach among the services of an RTOS taking into account the new possibilities offered by OLLAF. We plan also to employ preemptive scheduling policies by using the mechanisms of migration and reallocation of tasks configuration and context data proposed by OLLAF.

Figure 1 .

 1 Figure 1. Global view of OLLAF architecture

Figure 2 .

 2 Figure 2. Texe/triangle_nb variation for flat shading

Figure 3 .

 3 Figure 3. Our proposed model for the robotic vision application

Figure 4 .Figure 5 .

 45 Figure 4. Execution time measurement of search task

Figure 6 .

 6 Figure 6. Prediction error function of the number of detected keypoints


Ismail Ktata

Fakhreddine Ghaffari

Bertrand Granado

Mohamed Abid

Novel Approach for Modeling Very Dynamic and Flexible Real Time Applications

Keywords: Dynamically Reconfigurable Architecture, uncertainty, scheduling, modeling methodologies, DFG

Modeling techniques are used to solve a variety of practical problems related to processing and scheduling in several domains like manufacturing and embedded systems. In such flexible and dynamic environments, there are complex constraints and a variety of unexpected disruptions. Hence, scheduling remains a complex and time-consuming process and the need for accurate models for optimizing this process is increasing. This paper deals with dynamically reconfigurable architectures which are designed to support complex and flexible applications. It focuses on defining a solution approach for modeling such applications where there is significant uncertainty in the duration, resource requirements and number of tasks to be executed.

I. Introduction

Today, integrated silicon applications are more and more complex. Moreover, in spite of its performance, ASICs development is still long and very expensive, and provides inefficient solutions for many applications which are composed of several heterogeneous tasks with different characteristics. In addition, the growing complexity of realtime applications today presents important challenges, in great part due to their dynamic behavior and uncertainties which could happen at runtime [START_REF] Steiger | Operating systems for reconfigurable embedded platforms: online scheduling of realtime tasks[END_REF]. To overcome these problems, designers tend to use dynamically reconfigurable architectures (DRA). The development of the latter opens new horizons in the field of architecture design. Indeed, the DRAs are well suited to deal with the dynamism of new applications and allow better compromise between cost, flexibility and performance [START_REF] Noguera | Multitasking on reconfigurable architectures: Microarchitecture support and dynamic scheduling[END_REF]. In particular, fine grained dynamically reconfigurable architectures (FGDRA), as a kind of DRAs, can be adapted to any application more optimally than coarse grain DRAs. This feature makes them today an interesting solution when it comes to handle computational tasks in a highly constrained context. However, this type of architecture makes the applications design very complex [START_REF] Mtibaa | An efficient list scheduling algorithm for time placement problem[END_REF], especially with the lack of suitable and efficient tools. This complexity could be abstracted at some level in two ways: at design time by providing design tools and at run time by providing an operating system that abstracts the lower level of the system [START_REF] Garcia | OLLAF: a Fine Grained Dynamically Reconfigurable Architecture for OS Support[END_REF]. Moreover, such architecture requires the presence of an appropriate operating system that could manage new tasks at run time and under different constraints. This operating system, and to effectively manage dynamic applications, has to be able to respond rapidly to events. This can be achieved by providing a suitable scheduling approach and dedicated services like hardware preemption that decreases configurations and contexts transfer times. To realize an efficient schedule of an application, this operating system needs to know the behavior of this application, in particular the part where the dynamicity can be exploited on a DRA.

In this paper, we are interested in the modeling of applications that could be executed on dynamically reconfigurable architecture. This kind of applications is characterized, in addition to its real-time constraints, by several types of flexibility. The purpose is to improve the performance of the modeling techniques which facilitates the job to design an efficient scheduling approach.

The remainder of this paper is structured as follows: in Section 2, brief review is given about the context and the related work on modeling techniques used in different domains. Section 3 describes our new technique modeling applications targeted to DRA. The Section 4 reports a description of the proposed modeling method and comparisons with other models, while the last Section draws conclusions.

II. Context and problem definition

Today, embedded systems are more and more used in several domains: automobiles, robots, planes, satellites, boats, industrial control systems, etc. An important feature of these systems is to be reactive. A reactive system is a system that continuously reacts to its environment at a rate imposed by this environment itself. It receives inputs from the environment, responds to these stimuli by making a number of operations and produces the outputs used by the environment, known as reactions. Dynamically reconfigurable architectures are an interesting solution for this type of applications. Due to that emerging range of applications with dynamic behavior, dynamic scheduling for reconfigurable system-on-chip (RSoC) platforms has become an important field of research [START_REF] Noguera | Multitasking on reconfigurable architectures: Microarchitecture support and dynamic scheduling[END_REF].

A. Problematics

This paper deals with the constraint-based scheduling for real-time applications executed on FGDRA. In particular, we focus on two major problems:

The modeling of the application that should exhibit its dynamical aspects and must allow the expression of its constraints, in particular real-time constraints. The run-time performance of the scheduling algorithm that must be reasonable in term of overhead for a typical application.

The different components of a scheduling problem are the tasks, the potential constraints, the resources and the objective function. Tasks execution must be programmed to optimize a specific objective with the consideration of several criteria. Many resolution strategies have been proposed in literature [START_REF] Brucker | Complex Scheduling[END_REF]. Usually these methods assume that processing times can be modeled with deterministic values. They use predictive schedule that gives an explicit idea of what should be done. Unfortunately, in real environments, the probability of a precomputed schedule to be executed exactly as planned is low [START_REF] Billaut | Multicriteria Scheduling: Theory, Models and Algorithms[END_REF]. This is because of not only variations, but also because of a lot of data that are only previsions or estimations. It is then necessary to deal with uncertainty or flexibility in the process data. Hence, for an effective resolution, we need to make a significant reformulation of the problem and the solving methods in order to facilitate the incorporation of this uncertainty and imprecision in scheduling [START_REF] González | Comparative Study of Meta-heuristics for Solving Flow Shop Scheduling Problem Under Fuzziness[END_REF]. Uncertainty in scheduling may arise from many sources [START_REF] Davenport | A Survey of Techniques for Scheduling with Uncertainty[END_REF]:

The release time of tasks can be variable, even unexpected. New unexpected tasks may occur. Cancellation or modification of existing tasks.

The execution order of tasks on resources can be changed.

Resources may become unavailable. Tasks assignments: if a task could be done on different resources (identical or not), the choice of this resource can be changed. This flexibility is necessary if such a resource becomes unusable or less usable than others. The ability to change execution mode: this mode includes the approval or disapproval of preemption, whenever a task could be resumed or not, the overlap between tasks, changing the range of a job, taking into account whether or not a time of preparation, changing the number of resources needed for a task, etc. We are considering real cases where some variations could occur and some data may change over the forecast. The model has to be few sensible to data uncertainties and variations, and be flexible to be adaptable to the possible disturbances.

B. Scheduling under uncertainty

In general, there are two main approaches dealing with uncertainty in a scheduling environment according to phases in which uncertainties are taken into account [START_REF] Davenport | A Survey of Techniques for Scheduling with Uncertainty[END_REF]:

Proactive scheduling approach aims to build a robust baseline schedule that is protected as much as possible against disruptions during schedule execution. It takes into account uncertainties only in design phase (off-line). Hence, it constructs predictive schedule based on statistical and estimated values for all parameters, thus implicitly assuming that this schedule will be executed exactly as planned. However, this could become infeasible during the execution due to the dynamic environment, where unexpected events continually occur. Therefore, in this case, a reactive approach may be more appropriate. Instead of anticipating future uncertainties, reactive scheduling takes decisions in real-time when some unexpected events occur. A reference deterministic scheduling, determined off-line, is sometimes used and reoptimized. In general, reactive methods may be more appropriate for high degrees of uncertainty, or when information about the uncertainty is not available. A combination of the advantages of both precedent approaches is called proactive-reactive scheduling. This hybrid method implies a combination of a proactive strategy for generating a protected baseline schedule with a reactive strategy to resolve the schedule infeasibilities caused by the disturbances that occur during schedule execution. Hence, this scheduling/rescheduling method permits to take into account uncertainties all over the execution process and ensures better performance [START_REF] Aytug | Executing production schedules in the face of uncertainties: A review and some future directions[END_REF] [START_REF] Herroelen | Project scheduling under uncertainty: Survey and research potentials[END_REF]. For rescheduling, the literature provided two main strategies: schedule repair and complete rescheduling. The first strategy is most used as it takes less time and preserves the system stability [START_REF] Vieira | Rescheduling manufacturing systems: a framework of strategies, policies and methods[END_REF].

Scheduling techniques are quite different depending on the nature of the problem and the type of disturbance considered: resources failure, the duration of the variation and the fact that new tasks can occur, etc. The mainly used methods are dispatching rules, heuristics, metaheuristics and artificial intelligence techniques [START_REF] Ouelhadj | A survey of dynamic scheduling in manufacturing systems[END_REF]. In [START_REF] Peter | Scheduling of design projects with uncertain number of iterations[END_REF] authors considered a scheduling problem where some tasks (called "uncertain tasks") may need to be repeated several times to satisfy the design criteria. They used an optimization methodology based on stochastic dynamic programming. In [START_REF] Lambrechts | Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities[END_REF] and [START_REF] Liu | Genetic Local Search for Resource-Constrained Project Scheduling under Uncertainty[END_REF] scheduling problem with uncertain resource availabilities was encountered. Authors used proactive-reactive strategies and heuristic techniques. Another uncertainty case, which is uncertain tasks duration, had been studied in [START_REF] Turnquist | Allocating time and resources in project management under uncertainty[END_REF] and [START_REF] Beck | Proactive Algorithms for Job Shop Scheduling with Probabilistic Durations[END_REF]. Authors discuss properties of robust schedules, and develop exact and heuristic solution approaches.

C. Scheduling model

To study a system we need models to describe it, including significant system characteristics of geometry, information and dynamism. The latter is a crucial system characteristic as it permits to represent how a system behaves and changes states over time. Moreover, dynamic modeling can cover different domains from the very general to the very specific [START_REF] Fishwick | Handbook of dynamic system modeling[END_REF]. Model types have different presentations, as shown in figure 1: some are text-based using symbols while others have associated diagrams.

Graphical models use a diagram technique with named symbols that represent process and lines that connect the symbols and represent relationships and various other graphical notations to represent constraints (figure 1(a), (b) (d)).

Textual models typically use standardized keywords accompanied by parameters (figure 1(c)). In addition, some models have static form, whereas others have natural dynamics during model execution as in figure 1 (a). The solid circle (a token) moves through the network and represents the executional behavior of the application. In the domain of embedded systems, a large number of modeling languages have been proposed [START_REF] Edwards | Design of Embedded Systems: Formal Models, Validation, and Synthesis[END_REF], [START_REF] Lavagno | Models of computation for embedded system design[END_REF], [START_REF] Jantsch | Modeling Embedded Systems and SoC's: Concurrency and Time in Models of Computation[END_REF], including extensions to finite state machines, data flow graphs, communicating processes, and Petri nets, among others. In this section we present main models of computation for real-time applications reported in the literature.

Finite State Machines

The classical Finite State Machine (FSM) representation is probably the most well-known model used for describing control systems. However, one of the disadvantages of FSMs is the exponential growth of the number of states that have to be explicitly captured in the model as the system complexity increases making the model increasingly difficult to visualize and analyze [START_REF] Cortes | Verification and Scheduling Techniques for Real-Time Embedded Systems[END_REF]. For dynamic systems, the FSM representation is not appropriate because the only way to model such kind of systems is to create all the states that represent the dynamic behavior of the application. It is then unthinkable to use it as the number of states could be prohibitive.

Data-Flow Graph

A data-flow graph (DFG) is a set of compute nodes connected by directed links representing the flow of data. It is very popular for modeling data-dominated systems. It is represented by a directed graph whose nodes describe the processing and the arcs represent the partial order followed by the data. However, the conventional model is inadequate for representing the control unit of systems [START_REF] Cortés | A Survey on Hardware/Software Codesign Representation Models[END_REF]. It provides no information about the ordering of processes. It is therefore inappropriate to model dynamic applications.

Petri Net

Petri net (PN) is a modeling formalism which combines a well-defined mathematical theory with a graphical representation of the dynamic behavior of systems [START_REF] Fishwick | Handbook of dynamic system modeling[END_REF]. Petri Net is a 5-tuple PN = (P, T, F, W, Mo) where: P is a finite set of places which represent the status of the system before or after the execution of a transition. T is a finite set of transitions which represent tasks. F is a set of arcs (flow relation). W: F {1, 2, 3, ... } is a weight function. M 0 is the initial marking. However, though Petri net is well-established for the design of static systems, it lacks support for dynamically modifiable systems [START_REF] Rust | Rammig: "A Petri Net Based Approach for the Design of Dynamically Modifiable Embedded Systems[END_REF]. In fact, the PN structure presents only the static properties of a system while the dynamic one results from PN execution which requires the use of tokens or markings (denoted by dots) associated with places [START_REF] Tavana | Dynamic process modelling using Petri nets with applications to nuclear power plant emergency management[END_REF]. The conventional model suffers from good specification of complex systems like lack of the notion of time which is an essential factor in embedded applications and lack of hierarchical composition [START_REF] Rammig | Modeling of Dynamically Modifiable Embedded Real-Time Systems[END_REF]. Therefore, several formalisms have independently been proposed in different contexts in order to overcome the problems cited above, such as introducing the concepts of hierarchy, time, and valued tokens. Timed PNs are those with places or transitions that have time durations in their activities. Stochastic PNs include the ability to model randomness in a situation, and also allow for time as an element in the PN. Colored PNs allow the user and designer to witness the changes in places and transitions through the application of color-specific tokens, and movement through the system can be represented through the changes in colors [START_REF] Fishwick | Handbook of dynamic system modeling[END_REF].

Most of the methodologies mentioned provide no sufficient support for systems which include variable dynamic features. Dynamic creation of tasks for instance is not supported by most of the systems above mentioned [START_REF] Rammig | Modeling of Dynamically Modifiable Embedded Real-Time Systems[END_REF]. In [START_REF] Rammig | Modeling of Dynamically Modifiable Embedded Real-Time Systems[END_REF], authors proposed an extension of high-level Petri net model [START_REF] Badouel | Reconfigurable Nets, a Class of High Level Petri Nets Supporting Dynamic Changes[END_REF] in order to capture dynamically modifiable embedded systems. They coupled that model with graph transformation techniques and used a double pushout approach which consists of the replacement of a Petri net by another Petri net after firing of transitions. This approach allows modeling dynamic tasks creation but not variable execution time nor variable number of needed resources.

III. Proposed method

Before beginning to describe our modeling method, we define the constraints that typically appear in dynamic systems. In our case, we consider a firm real-time context. In fact, for actually developed applications, especially multimedia and control applications, tardiness or deadline violations results only in degradation of Quality of Service (QoS) without affecting good processing. In this context hardware tasks are characterized by the following parameters:

-Execution time (Ci), -Deadline (Di), -Periodicity (Pi), -Precedence constraints among tasks, -Tasks could be preempted, -Used resources of the DRA.

In real world, all characteristics may change: tasks (the release time, deadline and execution time), as well as the availability of resources. There are several types of changes like uncertainty, unexpected changes and values variation. For our study, we will consider three cases of dynamic scheduling problems for dynamic applications:

(a) The number of tasks is not fixed. It may change from iteration to another.

(b) The tasks execution time may change too. (c) The number of needed resources for tasks execution is variable. In addition, the number of available resources may decrease after a failure occurs.

For those cases, the goal is to develop a robust scheduling method that is little sensible to data uncertainties and variations between theory and practice. In addition, the schedule has to be flexible to be adaptable to the possible disturbances. Therefore, we consider a proactive-reactive approach. The proactive technique (a reference schedule computed offline for the static part) is used to facilitate the execution of the reactive strategy online, so that scheduling decisions have a better quality and produced in a shorter time. To represent all those constraints in the same model and to be adequate for the adopted scheduling approach, our graph will be composed of two forms of nodes. The first type of nodes refers to static tasks which are known in advance and whose execution is permanent during the whole application of the lifecycle execution. The second type is for dynamic tasks which could be executed in a cycle and not in others and with a variable number of needed resources. Therefore, the first step is to separate the two parts of the application (static and dynamic). Then, a priority-based schedule is established offline for static part. Such a schedule serves very important functions. The first is to allocate cells of the hardware DRA to the different hardware tasks. The second is to serve as a basis for planning tasks that may occur during execution. The basic idea is to sort static tasks from the graph and schedule them according to a priority scheme, while respecting their precedence constraints (topological order). Tasks are executed at the earliest possible time. If there is equality between some tasks, task which has maximum execution time will have priority to be launched before the others. At runtime, the objective is to generate a new schedule that deviates from the original schedule as little as possible so that the repair operations will be mostly simple. Therefore, the online scheduler must take into account the next tasks to be performed with their dynamic aspects (different duration, more or less instances to execute, more or less number of needed cells for execution). It has to prefetch configurations context of new tasks in the columns that are available for executing and to find the possible way to integrate them in the current schedule without effect on performance. This schedule repair must rely on rapid algorithms based on a simple scheduling technique so that it can perform online execution with no overhead. It consists in finding a suitable partitioning of N tasks, forming the application, to be executed on M target resources of the hardware devices. In addition, tasks execution order has to meet the real time constraints. This scheduling problem is known to be NP-hard [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-completeness[END_REF] [START_REF] Mann | Optimization problems in system-level synthesis[END_REF]. In this context, heuristics are schedule repair methods which offer fast and reasonably good solution but do not guarantee to find an optimal schedule.

We make use of the example shown in figure 3 in order to illustrate the different definitions corresponding to our model. For this example, the set {T1, T2, T3, T4, T5, T6, T7, T8} represents the static tasks which are always executed in each period and {T9, T10, T11} are dynamic tasks which may be executed in some period but not in others and whose number of resource requirements is variable. Each task is represented with time characteristics: Ci for the execution time and Di for the deadline.

The first dynamic feature considered in this model is tasks with variable execution time. To represent that case, we are inspired by the Program Evaluation and Review Technique (PERT) [START_REF] Chauvet | The PERT Problem with Alternatives: Modelisation and Optimisation[END_REF], which is a network model that allows randomness in activity execution times. For each task, PERT indicates a start date and end time at the earliest and latest. The chart identifies the critical path which determines the minimum duration of the project. Tasks are represented by arcs with an associated number presenting the tasks duration.

Between arcs, we find circles marking events of beginning or end of tasks (figure 2). In this model, we replace the release time feature by the execution time as it would be changed over execution, and we keep the deadline as it will be useful to minimize the makespan (or the length of the schedule). In figure 3, tasks with variable execution time are {T1, T7, T8}. This will be noticed by the use of asterisk. To be executed, hardware tasks need a minimum number of resources. The percentage of this minimal number is indicated in labels over tasks nodes. This case is frequently found on some computer vision applications where a first task is detecting objects and then a particular processing is applied on each detected object. To execute multiple instances of this process, the minimum needed number of resources will be multiplied by the number of instances. In figure 3, task T9 will be executed n times. T9 is represented with circled node and the minimum needed number of resources indicated in the label will be multiplied by n. If the integer number n=0 then task will not occur. The instance number is unexpected from the static phase and decision will be taken online. The number n will depend on the previous executions and the actual input data to be processed (such as keypoints in the robotic vision application). Thus, n will be recalculated, after each period, based on its previous values. For more details, we take an example of execution. In each iteration the scheduler will have two values of n: n p which is a predicted value of n to be used by the scheduler for the next period, and n r which is the real value of n for the executed task. At t=0, let n= n p =0 (no prediction to execute T9). In the first execution, the application needs n= n r =10 instances of T9. So, for the second iteration, the scheduler will predict to execute n= n p =10 instances of T9, while, in the real execution, n= n r =6. For the next execution, n p could be: the maximum of precedent values, the highest values of n, the average of real last values (n= n p =8), or a Gaussian like probability which is a typical realistic distribution, etc. The choice will depend on the application. For the example of a moving robot which need to predict the direction and the presence or absence of obstacles, it will be preferred to take the last real values with different weights. In our model, the number n is represented above the arcs. The arcs represent the dependencies between tasks. For static (permanent) tasks, we represent arcs with solid lines, while unpredictable dependencies are represented by dashed lines. On the reconfigurable device, resource failure may occur which will affect the resource availability. Thus, execution may occur or not depending on the available resources compared with needed ones. A variable, which is initialized as the total number of resources, will indicate the amount of remaining resources. From the ready list, algorithm determines the tasks that can be executed on the reconfigurable device. Tasks with the higher priorities will be placed first until the area of device is fully occupied.

IV. Comparison of models

When we compare with other models (section 2-C), the proposed technique presents several advantages. For unpredicted number of occurring tasks, the data flow graph does not contain information about the number of instances. During execution of the application, every task represented by the nodes of DFG is executed once in each iteration [START_REF] Sinnen | Task Scheduling for Parallel Systems[END_REF]. Only when all nodes have finished their executions, a new iteration can start. So to model this, we need to represent n nodes of the same task, which increases the size of the model (see figure 4(b)). In our model, information about number of instances of a same task to be executed is noted by the circle form of the task and the indicated number above its arc. For PN model, (see figure 4(a)), arcs could be labeled with their weights where a k-weighted arc can be interpreted as the set of k parallel arcs [START_REF] Murata | Petri nets: Properties, Analysis and Applications[END_REF]. But, from its definition (section 2-C), weights are positive integers, so it cannot present a fictive arc with non firing transition representing a task that may not be executed in some iterations. In figure 4(a), if T9 and T10 are not executed, then n should be null, which is impossible from PN definition. In addition, to fire T8 all input places should have at least one token, which will be not possible if T10 or T11 was not executed (fired). Timing information is useful for determining minimum application completion time, latest starting time for an activity which will not delay the system, and so on. We have inspired from the PERT chart to explicitly represent useful time features that are, in our case, execution time and deadline. However, Petri net does not provide any of this type of information. The only important aspect of time is the partial ordering of transitions. For example, it presents variable tasks duration with a set of consequent transitions for each task which will complicate the model (see figure 5). The addition of timing information might provide a powerful new feature for Petri nets but may not be possible in a manner consistent with the basic philosophy of Petri nets Research [START_REF] James | Petri net theory and the modeling of systems[END_REF].

For resource representation, PN models this feature by an added place with a fixed number of tokens. To begin execution, a task removes a token from the resource place and gives it back in the end of its execution. However, this model is inadequate in our case since the number of available resources may change over the execution.

Therefore, the use of conventional modeling methods is not effective in our case. In fact, with PN and DFG model (figure 4), there is no distinction between static tasks and dynamic ones (that may not be executed), nor an explicit notion of time (as variable execution time of some tasks). The main advantage of the proposed method is the possibility to present several dynamic features of real time applications with the minimum of nodes and thus in a simple formalism. Indeed, from the first sight of the model, we can bring out three main characteristics of this model: -The distinction between the static execution (which is presented by the squared nodes) and the dynamic execution i.e. the tasks whose execution and number of instances is uncertain (presented by the circled nodes), -The tasks whose execution time is variable (presented by the asterisk), -The percentage, for each task, of needed resources for its execution. In each iteration, and depending on the available resources, schedule is able to decide which ready tasks could be executed on the device. Those informations will be useful further for the scheduler. We consider a 1D area model as it is a commonly used reconfigurable resource model, but even 2D area model could be considered. In that considered 1D model, tasks can be allocated anywhere along the horizontal device dimension; the vertical dimension is fixed and spans the total height of the hardware task area (see figure 6). Based on the proposed tasks model, statically defined tasks represented by squared nodes, will be scheduled and placed on the reconfigurable device during the proactive phase. Whereas dynamically defined tasks, which are represented by circled nodes, will be scheduled online in a reactive phase. This online decision will take into account the variable parameters and try to fit into the set of already guaranteed tasks, to delay or to reject these new dynamic tasks.

V. Conclusion

This paper presented a particular modeling problem dealing with the implementation of dynamic and flexible applications on dynamically reconfigurable architecture. The purpose is to consider most of the dynamic features supported by the architecture and to present them in an easy and efficient method. For that point we have proposed a model, based on some features of existing modeling techniques, and which is more dedicated to dynamic real time applications. The main advantage of our specification model is the possibility to obtain more exact scheduling characteristics from the representation. Those characteristics include the distinction between static and dynamic occurring tasks, bring out tasks whose execution time may change over the time and determine the number of resources needed for executing hardware tasks. So, we will be able either to take decisions or not. As a reconfigurable architecture, we target OLLAF [START_REF] Garcia | OLLAF: a Fine Grained Dynamically Reconfigurable Architecture for OS Support[END_REF] (Operating system enabled Low LAtency Fgdra), an original FGDRA specifically designed to enhance the efficiency of an RTOS services necessary to manage such architecture. Future works will consist in integrating our scheduling approach among the services of an RTOS taking into account the new possibilities offered by OLLAF.

VI. References

Figure 1 .

 1 Figure 1. Four types of dynamic system models. (a) Petri net. (b) Finite state machine. (c) Ordinary differential equation. (d) Functional block model.

Figure 2 .

 2 Figure 2. PERT graph

Figure 3 .

 3 Figure 3. New model for dynamic application

Figure 4 .

 4 Figure 4. (a) A Petri net representation of the example of figure 3. (b) A DFG representation of the example of figure 3.

Figure 5 .

 5 Figure 5. PN model for variable tasks duration

Figure 6 .

 6 Figure 6. 1D area model of a reconfigurable device

ReCoSoC 2010May 17-19, 2010, Karlsruhe, Germany

May 17-19, 2010, Karlsruhe, Germany ReCoSoC 2010

May 17-19, 2010, Karlsruhe, Germany


Nourhene Maalel

Mounir Kellil

Pierre Roux

Abdelmadjid Bouabdallah
email: bouabdal@hds.utc.fr

Fast Restoration Of Connectivity for Wireless Sensor Networks

Keywords: WSN, fault tolerance, sensor failure

Fast restoration of Connectivity for Wireless Sensor Networks

Nourhene Maalel, Mounir Kellil, Pierre Roux, Abdelmadjid Bouabdallah

Introduction

Because of the unprecedented prospects they offer and the idea of eliminating human intervention, wireless sensor networks (WSNs) have perceived a tremendous attention from the research community in recent years [START_REF] Akyildiz | Wireless Sensor and actor networks: Research Challenges[END_REF]. Upon their deployment, WSN form a network composed of a set of sensor nodes and one or several sink nodes. Sensors role is to make measurement then to relay it as routers from sensor to sensor toward a sink node. We do also consider the presence of specific entity called mobile node which has the ability of processing data and making the appropriate decision. WSNs encounter many challenges [START_REF] Akyildiz | Wireless Sensor and actor networks: Research Challenges[END_REF] such as energy efficiency and limited battery. Our contribution focuses on the issue of sustainable connectivity.

Uneven energy distribution and consumption or accidental failures due to harsh environments may cause sensors to die arbitrarily [START_REF] Wu | Lightweight deploymentaware scheduling for wireless sensor networks[END_REF]. These damaged nodes generate constrained region which provoke the network partitioning and thus hamper the network activity. On the other hand, the data traffic is typically concentrated on the sensor nodes surrounding the sink [START_REF] Jaichandran | Effective strategies and optimal solutions for Hot Spot Problem in wireless sensor networks (WSN)[END_REF][START_REF] Wang | Prolonging the Lifetime of Wireless Sensor Networks via Hotspot Analysis[END_REF]. Consequently, those bottleneck nodes around the sink exhaust their batteries faster than other nodes which lead to the isolation of the sink from the rest of the network. Therefore, the network may get partitioned into disjoint areas (referred to as holes) due to node failure or energy depletion. If the network gets useless when the first holes occur, the remaining resources are wasted. Consequently, maintaining network connectivity is a crucial concern to ensure application operation.

In this paper, we exploit the non-uniform consumption, traffic distribution and deployment of wireless sensors to elaborate an efficient dynamic recovery approach. We present CoMN2 a protocol restoring WSNs Connectivity using a Mobile Node in a Mapped Network. CoMN2 introduces a new concept called Network Mapping which consists in partitioning the network in several regions of increasing criticality. For instance a dense area with low sensing activity will have lower criticality than nodes in a sparse area highly solicited. Through this network mapping, our solution CoMN2 ensures the continuous network activity by swapping nodes from low critical area to high critical ones when required. The swapping is performed using a mobile node which is aware of the sensor status.

Basically, the algorithm is triggered depending on the Zone of the failed node in our mapped network. This solution minimizes the energy consumption by inhibiting the recovery process as long as the damaged node is not vital for the network. Above and beyond that, CoMN2 proceeds to a periodic network mapping update in response to unpredictable network dynamics. CoMN2 design fulfills the following points that we consider as requirements for our context:  In view of the autonomous and unsupervised characteristics of WSN, the network recovery from node failure should be performed in a distributed manner.  The process should be rapid and lightweight to preserve the WSN responsiveness to detected events.  The overheads should be minimized in order to consider the scarce resources of WSNs. The remainder of this paper is organized as follows: the next section gives an overview of the problem statement. The details of the algorithms and analysis are given section 3. Section 4 presents the previous approaches then section 5 provides the simulation results and finally section 6 concludes this paper.

Problem Statement

Maintaining inter-node connectivity is a crucial concern in WSNs. Many applications like disaster management require efficient and highly reliable nodes collaboration to efficiently assess damage and identify safe escape paths which emphasize the impor-tance of this concern. Basically, the failure of a sensor in critical region may create "holes" (Figure 1) and induces a partitioned network, so a reduction of the network operation efficiency. A particular case of this point is the HotSpot problem: Sensor nodes around the sink are extremely solicited to forward the sensed data (from the entire network nodes) toward the sink. In spite of the large deployment of sensors to tolerate possible node failures, we have to face the problem of isolation of the sink node caused by the depletion of the energy of sensor nodes surrounding it. This may result in the failure of the whole network whereas the remaining nodes are perfectly functional.

Fig. 1. Node isolation in the hotspot area

On the other hand, sensor nodes activity may be non-uniform in an hybrid network. For instance, regular traffic is expected for monitoring a given parameter whereas some nodes may be further involved in relaying data toward the sink. This nonuniform activity distribution depletes the battery of some sensors faster than the rest of the network. Nevertheless, some areas are covered by excessive sensors which create redundant sensing region because closest nodes may have similar data [START_REF] Wu | Lightweight deploymentaware scheduling for wireless sensor networks[END_REF]. Table 1 presents the relationship between the number of neighbors and the percentage of redundancy. As shown above, with 11 neighbors, the probability of complete redundancy is almost 92.28%, and the percentage of redundancy area exceeds 99%. Thus, the loss of a sensor in a redundant area does not impact the rest of the network because its neighbors are capable to achieve exactly the same role.

Keeping in mind all these aspects, our problem statement can be formulated as follows: given a set of nodes,  How can we recover from node failure?  When should we replace the damaged node and which nodes are vital for the functioning of the network?  How can we handle unpredictable dynamics of the networks? To deal with the first issue, CoMN2 proposes to recover from node failure by swapping nodes using a mobile node. This solution raises another issue which is the selec-tion of the node to move. This problem is resolved thanks to a new concept proposed in this paper which is the network Mapping. Upon the detection of a damaged node, CoMN2 considers four characteristics:

 The battery level  The number of neighbors  The location of the node (Hotspot area or not)  The activity of the node These issues are summarized in the ZoneAffectationTable which will be presented in the next section. Depending on the value of these parameters, the network is mapped in three zones of increasing rank expressing the criticality of sensors of each zone. This mapping is periodically updated to consider the network dynamism. The detailed CoMN2 algorithm is explained in the next section.

3

CoMN2 Operation

Overview of the mechanism

In the following scenario, we are considering a hybrid WSN with static sensors, along with a sink and a mobile node. The mobile node is resource-rich node equipped with high processing capabilities and longer battery life. We assume that the sensors are randomly scattered over the network and that every node is aware of its location and its remaining energy.

The communication between sensors and the mobile node is performed thanks to the sink. All the control messages as initially sent to the sink which transfers it to the mobile node. We assume that the mobile node notifies the sink of its new position each time it moves.

As mentioned above, the crash of some nodes may stir up the division of the network into disjoint segments and leads to the formation of holes. To avoid this, our solution uses a mobile node carrying out the network restoration by switching a failed node with another from a redundant area (less critical). Furthermore, our solution handles simultaneous sparse node failure by classifying nodes according to their importance through an innovative process called network Mapping (partitioning). This method consists in organizing the network into three zones of increasing rank depending on the criticality of nodes belonging to each area. The detailed mechanism will be presented in the following part.

Network Model

Our idea of mapping (Figure 2) the network emanates from the observation that sensors have no uniform activity in the network as explained in section II. The key plan is to hierarchically divide the sensor field into zones of increasing importance according to the node"s activity.

Fig. 2. Network Mapping

In fact, the more the node is solicited, the faster its energy depletes and consequently it will die first. On the other side, some high density zones are monitored by excessive sensors what means that the failure of a node of that zone does not impact its functioning as stressed in section 3. That"s why we decide to give priority to connectivity in specific zones instead of favoring connectivity of the entire network. We divide the network into three zones of growing rank. Our basic assumption is that the nodes around the sink are the most actives [START_REF] Jaichandran | Effective strategies and optimal solutions for Hot Spot Problem in wireless sensor networks (WSN)[END_REF][START_REF] Wang | Prolonging the Lifetime of Wireless Sensor Networks via Hotspot Analysis[END_REF] and that they belong to the first zone. Since we are considering a heterogeneous network with nodes assigned to diverse applications, some nodes may be very solicited for sensing or reporting operations. In view of their importance, the sensors of these specific zones belong to the first zone too. We define the third zone as the less critical one containing the set of nodes with more than 10 neighbors (section 3). The remaining nodes constitute the second zone. Finally we obtain a network"s cartography based on how critical is each zone. This network cartography will be dynamic: it will be updated contingent on the activity of nodes.

Protocol Operation

Initial affectation of nodes through zones:

The first affectation of nodes through zones exploits their position and their neighborhood repartition. The mobile node will maintain a table referred to thereafter as ZoneAffectationTable containing five parameters {Id, Pos, NN, RZ, Zone} where:  Id is a unique identifier of each node.  Pos designate the local position of the node.

 NN is the number of neighbors.

 RZ is a binary parameter designating risky zones: 1 for risky one/ 0 for no risky. Initially, RZ is set to 0 for all nodes. It will be set to 1 during the update process when the mobile node will notice the high activity of some nodes.  Zone indicates the zone of affection. It can be 1, 2 or 3 with 1 designating the most critical zone. To establish ZoneAffectationTable, each node should send NN and Pos to the sink which will relay it to the mobile node (Figure 3). The whole process is kept local by requiring every node to maintain a list of only its close neighbors: we restrain our list to the 1-hop and 2-hop ones only.

Fig. 3. Initialization phase

After receiving this information from nodes, the mobile node would proceed to the zone affectation depending on the number of neighbors around each node:

Zone = 3 IF NN≥10 (1) 2 Otherwise
Nodes around the sink constitute the special case of the HotSpotArea. They are automatically affected to zone 1.

Update of the network mapping:

CoMN2 pursues a dynamic approach by updating the mapping of the network throughout the exchange of specific messages between nodes. This reorganization involves the refresh of the ZoneAffectationTable (Figure 4) and more precisely of NN and RZ. NN is kept up to date by sending periodic HEARTBEAT messages between neighboring nodes. The absence of HEARTBEAT response from a neighboring node F would mean that F failed then a message is automatically sent to the sink which will notify the mobile node. Upon receiving this notification, the mobile node modifies the value of the corresponding NN in the ZoneAffectationTable. Furthermore, we define Tobs as the time that the sink waits before sending a periodic activity report to the mobile node for analysis. This report aims to determine the most solicited nodes by quantifying the number of operation (including sensing and routing) per node: each sensor is equipped with a counter which is incremented after every action like relaying or sensing data. The result of this counter is periodically sent to the sink. Keeping in mind that this report must characterize the network and is used to identify the most active zones, special attention is paid to well choose Tobs which should be long enough. Once the account is relayed by the sink, the mobile node calculates the average number of operations per node (the mean value) and sets RZ to 1 for the most solicited nodes: with a number of operations greater than the mean value. Thanks to this parameter, a node initially belonging to zone 3 can be classified as zone1 if it"s highly active. Additionally, as soon as a node"s energy drops below a critical level, it sends a DISTRESSMESSAGE containing its ID to the mobile node.

Fig. 4. Update phase

Initiation of the CoMN2 recovery process:

To expound how CoMN2 Algorithm performs, let"s consider these two cases with a first classical one of a single alert message and a second case showing how our proposed algorithm handles simultaneous node failure. Before giving rise to the recovery process upon detecting a failure, the mobile node waits during a period of Thold to check if there is another alert.  Single Alert For the case of single alert, the mobile node should decide whether to initiate the recovery or not. This choice is based on the zone to which the node belongs. Actually, the network mapping aims to avoid restoring connectivity at the cost of additional energy consumption when we can do without this node: The protocol tussles to minimize the movement of the mobile node in order to save its energy. In fact, despite its high battery compared to the sensors, the energy of the mobile node is not unlimited. Execution of restoration is triggered only if the node belongs to zone 1 or 2 which are the most important regions. If the dying node is from zone 3, we suppose that it has a sufficient number of close redundant neighbors to replace it. The mobile node checks at first ZoneAffectationTable to determine the Zone of the node then decide to rescue it or not.  Simultaneous Alert Let"s consider the case of 2 alerts received during Thold from node A in zone 1 and node B in zone 3. The mobile node proceeds to the comparison of the zone of each node using ZoneAffectationTable then decides to rescue the node with the most important zone (which is node A in our example). If all the alerts arise from zone 3, no recovery process is triggered because the failure of these nodes does not impact the efficiency of the network application. The case of simultaneous alerts with the same importance is handled by a FIFO mechanism (First In First Out). The mobile node continues its current task then deals with the second affected node.

Recovery execution:

The recovery solution is based on the swap of nodes and the replacement of the broken ones with the help of the mobile node. For the beginning of the network recovery approach, the mobile node exploits the Network Mapping to find the most suitable node to move. The choice of the best candidate is based on two criteria:

-A minimum change in the network topology. This condition can be achieved by choosing a node from a redundant area (zone3) which will not involve the reorganization of the network.

-The nearest one given the position of the failed node and the actual position of the mobile node in order to minimize the overhead of the recovery process.

The mobile node searches the closer node of zone 3 in the ZoneAffectationTable given the position of the failed node and his current position. This way, the inter-node connectivity is re-established without involving a change of the network topology. Since the spare node reaches the failed node location, it becomes responsible for carrying out its tasks including both routing and the application level. The choice of the optimal path to reach the failed node is out of the scope of this paper.

Related works

How to deal with node failure is a challenging concern that has been widely studied in the past years. For instance, [START_REF] Liang | A fault tolerant and energy efficient routing protocol for urban sensor networks[END_REF] proposed a power extension algorithm consisting on the increase of the transmission power to extend the communication range so that a node can reach further nodes when its next hop fails. This algorithm handles the connectivity aspect but does not provide a solution to ensure the sensing function of the failed node. Another proposed approach in [START_REF] An | Route recovery with one-hop broadcast to bypass compromised nodes in wireless sensor networks[END_REF] uses the neighbor information to construct a new path and take the routing role of the failed nodes. This work assumes that sufficient number of neighbors surround the failed node. Yet, this is not always true because of the random deployment of sensors in some scenarios such as hostile environments and hazardous zones. Many researches investigate the use of mobile nodes [6-8] [14-15] to restore connectivity in mobile networks. In [START_REF] Luo | Joint mobility and routing for lifetime elongation in wireless sensor networks[END_REF], the author suggests to use a mobile base station in order to load balance the charge around the sink by changing the nodes located close to it. Unlike our proposed approach, this algorithm restrains its efficiency on nodes surrounding the sink and involves an extra message overhead to update the location of the mobile base station. Another solution referred to as Coverage Conscious Connectivity Restoration algorithm [START_REF] Tamboli | Coverage-Aware Connectivity Restoration in Mobile Sensor Networks[END_REF] (C3R) relocates one or multiple neighbors of the failed node to recover from the damage. Each neighbor temporarily moves to substitute the failed node what leads to intermittent connectivity. The assumptions in the above work are strict because there is no guarantee to have multiple neighbors available.

Controlled mobility is a framework operating in context aware mobile devices with intelligent ability permitting to determine their future location on the basis of some conditions like battery level or data gathered. Authors in [START_REF] Denkovski | Extension of the WSN Lifetime through Controlled Mobility[END_REF] exploit controlled mobility to propose an algorithm for sensor nodes relocation. The algorithm assumes WSNs with cluster topology and allows relocation of sensor nodes between clusters based on predefined utility function. Despite its interest, this approach arises clustering limitations such cluster head deployment and maintaining coverage in clusters.

Experimental Evaluation

This section describes the simulation experiments to assess the effectiveness of the proposed approach. We compared CoMN2 to a Mobile Sink solution and to a basic topology without restoration.

Baseline approach:

We use two metrics to evaluate the performance of CoMN2: the network lifetime and the failure rate.

-The network lifetime is a generic term depending on the considered scenario. In our case, we define it as the time for the first node to become unable to reach the sink (no route available because of the failed nodes). Our goal is to increase the network lifetime.

-The failure rate indicates the rate of failed nodes. It serves as a measure of the fault tolerance of the network: The higher the failure rate is at the end of the network life, the more fault-tolerant the network is.

A java simulator has been developed to evaluate CoMN2. The simulation experiments involve randomly generated WSN topologies with varying number of nodes from 100 to 800 in a network field with dimensions of 10000mx20000m. The location of the sink is selected randomly. For each topology set-up (network size, protocol) simulation is run 10 times and the average performance is reported. During each run, packets are generated and sent successively. The sending sensors are randomly selected and the path to the sink is created using least-cost routing in terms of number of hops. We assume the energy distribution is uniform in the network: all nodes have initially the same battery level. Nodes" battery-level decrease at each operation until attaining a critical threshold equivalent to 20% of the initial battery level. Once the threshold reached, CoMN2 is activated if the node belongs to zone 1 or 2 and the node is considered as failed.

As explained in section 4, many researches propose solutions with Mobile Sink. Our simulation uses a configuration where the sink moves periodically in the network to load balance the traffic. It chooses a location where nodes in the neighborhood (nodes around the new position of the sink) have a high level of battery available.

Performance comparison

We conduct different experiment by varying the network density. To test the scalability of our approach, we increased progressively the number of nodes for a fixed network field dimension and transmission range. The results are depicted in Figure 5. As can be seen from the figure, our algorithm significantly increases the network lifetime compared to the basic configuration (without restoration) and to the mobile sink for all network sizes. This rise is more significant for dense network which is attributed to the fact that the number of the back-up nodes used to replace the failed nodes in CoMN2 is higher in a dense network. 2 summarizes the increase of the network lifetime for the different configurations. We observe an average increase of more than 11% compared to the Mobile Sink and 40% compared to the network without CoMN2 which assess the effectiveness of our approach.

Table 2. Percentage of the network lifetime increase with CoMN2

Moreover, we tested the performance of CoMN2 in term of fault tolerance. Curves in Figure 6 shows that the fault tolerance is considerably raised thanks to CoMN2: the network tolerates a higher percentage of failed nodes (~35% vs ~10% without CoMN2). This increase is due to the location of the failed nodes which differs as shown in In fact, the curves of failure rate vs. time for a network with and without CoMN2 follow the same slope (Figure 8) in the beginning of the simulation. Nevertheless, CoMN2 maintains nodes around the sink alive by swapping them with nodes far from it which increase the lifetime of the network. However, the hotspot area around the sink remains vulnerable to node failure (highly solicited) which increase its failure rate hence the higher slope of CoMN2 from t=500.

Conclusion & future works

Network mapping based on node resources represents an attractive paradigm in the design of wireless sensor network. In this paper, we presented a distributed and dynamic recovery protocol CoMN2 which handles node failure in WSNs. As it is unknown whether such crash causes a network partitioning or not, we provide a technique based on network mapping deciding if a node should be replaced or not. Simulations show that CoMN2 achieve more than 40% improvement of the network lifetime.

For the future work, we plan to reduce the network recovery delay of our approach by investigating the optimal routing path to follow to join the sink.

CoMN2

Without CoMN2

Fig. 5 .

 5 Fig. 5. Network Lifetime vs. Network size Table2summarizes the increase of the network lifetime for the different configurations. We observe an average increase of more than 11% compared to the Mobile Sink and 40% compared to the network without CoMN2 which assess the effectiveness of our approach.

Fig. 6 .

 6 Fig. 6. Fault tolerance vs. Network Size

Fig- ure 7 .

 7 We notice that unlike CoMN2, failed nodes are scattered around the sink for the first figure which shortens the network lifetime and provokes the hotspot problem.

Fig. 7 .

 7 Fig. 7. Failed node location for the same failure rate

Fig. 8 .

 8 Fig. 8. Failure rate vs. Time

Table 1 . Number of neighbors Vs Percentage of redundancy extracted from [3] Number of neighbors Probability of complete redundancy Percentage of the redundant area

 1

	5	31.22-37.01%	91.62%
	7	64.29-65.21%	96.89%
	9	82.97-83.09%	98.85%
	11	≈ 92.28%	99.57%