Stéphane Lohier
email: lohier@univ-mlv.fr

Abderrezak Rachedi
email: rachedi@univ-mlv.fr

Erwan Livolant
email: livolant@univ-mlv.fr

Ismail Salhi
email: salhi@univ-mlv.fr

Wireless Sensor Network Simulators Relevance compared to a real IEEE 802.15.4 Testbed

Keywords: Wireless Sensor Networks, IEEE 802.15.4, Network Simulators, Testbed I

The diversity of research topics in Wireless Sensor Networks (WSNs) is attracting more and more researchers from different fields. The common point of all proposed solutions and protocols for WSNs is the evaluation usually done with network simulators. In this paper, we focus on the results relevance of wireless sensor network simulators in different scenarios based on indoor and outdoor environments. We propose a comparative study between 3 usual simulators (NS2, OPNET and QualNet) while using as reference a real testbed based on recent Imote2 sensors. The simulators give different results even in similar environments. NS2 and Qualnet give results close to those of the experimentation in the case of an indoor environment, but in the outdoor environment Opnet gives results closer to the reality. In addition, the impact of different MAC protocols (B-MAC and TKN15.4 MAC) which observe or do not observe the IEEE 802.15.4 standard is illustrated by real experimentations. They show that TKN15.4 protocol gives a better throughput than B-MAC.

INTRODUCTION

The design and the implementation of new protocols or models for wireless sensor networks are mainly based on simulation in order to test and validate the proposed solutions. Simulations are indeed less costly and complex than a real implementation in a testbed, especially if the density of the network and the complexity of the topology used are significant. Moreover, we are able to compare the performances of different protocols/models in different scenarios and through different periods much faster with simulations. When implementing a real WPAN testbed with ZigBee [START_REF] Zigbee | Zigbee Specification[END_REF] devices, we have to take into account the environment type, the terminal location and the MAC sub-layer parameters as they may have an important impact on the different protocols/models performances. To assess the relevance of a specific wireless network simulator, two questions have to be answered: 1) Is the implementation of the lower layers, specially the physical layer, close to the reality? 2) If the implementation is not enough realistic, how can we evaluate the relevance of our results, particularly in the case of a dense multi-hop network, as we know that the transmission model between two nodes does not match a real situation?

Our involvement in such a study is thus due to three observations we made: 1) No work dealing with the latest 802.15.4 [START_REF]Part 15.4: Wireless medium access control (MAC) and physical layer (PHY) specifications for low-rate wireless personal area networks (WPANs)[END_REF] devices ever reported any evaluation of their performance and observance of the IEEE standard. These studies focused on the different MAC 802. This paper thus aims at:

1) Assessing the performances of different MAC layers implemented in the latest 802.15.4 devices based on the CC2420 RF transceiver [START_REF]Datasheet for Chipcon/Texas Instruments CC2420 2.4 GHz IEEE 802.15.4/ZigBee-Ready RF Tranceiver[END_REF] and checking their observance of the IEEE standard. The 802.15.4 devices performances are evaluated both in an indoor and in an outdoor environment. 2) Estimating the relevance of the MAC 802.15.4 layer lately implemented in the different network simulators and comparing it to a real testbed. We will thus be able to provide researchers a guideline to help them choose and tune a 802.15.4 simulator in accordance with a specific environment.

To achieve these goals, we use four different environments: an outdoor free-space and three indoor environments (office, corridor and hall). For the indoor-office environment, we first study a simple transmission without contentions between two nodes, and then transmissions with one to seven emitters in competition to access to the media. The comparisons are made with three major network simulators: NS2 [START_REF]The Network Simulator NS-2[END_REF], OPNET [START_REF]OPNET Modeler[END_REF] and QualNet [START_REF] Qualnet | [END_REF]. For the testbed, two MAC protocols are investigated: B-MAC (Berkeley MAC) [START_REF] Polastre | Versatile low power media access for wireless sensor networks[END_REF] which does not observe the IEEE 802.15.4 standard and TKN15.4 MAC [START_REF] Hauer | [END_REF] which does. B-MAC protocol is a native protocol of many hardware devices like Crossbow sensors (MICAz, TelosB, Imote2). TKN15.4 MAC protocol includes almost the complete functionality described in the 802. 15.4-2006 [2] specification, except for GTS allocation and management, security services, and a few minor services like PAN ID conflict notification. This paper is divided into five sections. In section 2, we sum up the existing works dealing with experimentation results and network simulators. We present an evaluation of B-MAC and TKN15.4 MAC over Imote2 in section 3. Section 4 is dedicated to the comparative study of the major network simulators performances. The fifth section concludes our paper and presents the future works.

II. RELATED WORKS

Many works in literature deal with the performance evaluation of the IEEE 802.15.4 standard. These studies can be divided into three categories. In the first one [START_REF] Petrova | Performance study of IEEE 802.15.4 using measurements and simulations[END_REF][START_REF] Lee | An experiment on performance study of IEEE 802.15.4 wireless networks[END_REF], the results are obtained with real 802.15.4 devices. In the second one [START_REF] Lu | Performance Evaluation of the IEEE 802.15.4 MAC for Low-Rate Low-Power wireless Networks[END_REF][START_REF] Zheng | A comprehensive performance study of IEEE 802.15. 4, Sensor Network Operations[END_REF][START_REF] Koubaa | A Comprehensive Simulation Study of Slotted CSMA/CA for IEEE 802.15.4 Wireless Sensor Networks[END_REF], they are obtained with different simulations. In the third one [START_REF] Ramachandran | Analysis of the contention access period of IEEE 802.15.4 MAC[END_REF][START_REF] Misic | Performance of a Beacon Enabled IEEE 802.15.4 Cluster with Downlink and Uplink Traffic[END_REF][START_REF] Singh | Performance evaluation of an IEEE 802.15.4 sensor network with a star topology[END_REF], the analysis and modelling of the 802.15.4 channel enable the network performances assessment.

The complete study proposed by Petrova et al. [START_REF] Petrova | Performance study of IEEE 802.15.4 using measurements and simulations[END_REF] analyzes the performance of IEEE 802.15.4 through the measurement of the PER (Packet Error Rate) and the RSSI (Received Signal Strength Indicator) both in indoor and outdoor environments with only one emitter and one receiver using the usual CC2420 RF transceiver. The results demonstrate the OQPSK modulation efficiency compared to other schemes included in WiFi or Bluetooth technologies. The results are then used to tune the error model in NS-2 simulator [START_REF]The Network Simulator NS-2[END_REF] for the IEEE 802.15.4 MAC extension [START_REF]Ns2 simulator for 802[END_REF]. The simulations show that in the slotted CSMA-CA mode, the throughput is always lower than 45kbps (for a 250kbps nominal raw bit rate), whatever the offered load and the number of sources (from 1 to 60). The conclusion is that the beaconed mode should only be used when the resulting short channel access time is critical, and the offered load is low. No comparison on the throughput is done between the simulator and the testbed.

In a similar study [START_REF] Lee | An experiment on performance study of IEEE 802.15.4 wireless networks[END_REF], the authors study the performance of the direct and indirect data transmissions using an IEEE 802.15.4 compliant CC2420 transceiver in the CSMA/CA beacon-enabled mode and analyze the effects of the data payload size. This study shows that: (1) the data throughput is significantly reduced in the case of indirect transmissions (from 153kbps to 65 kbps for a 250kbps raw bit rate); (2) when the number of sources increases, both the effective data rate and delivery ratio decrease because of collisions and random backoffs; (3) the data rate increases according to the payload size but it has no significant influence on the delivery ratio.

In [START_REF] Lu | Performance Evaluation of the IEEE 802.15.4 MAC for Low-Rate Low-Power wireless Networks[END_REF], Lu et al. evaluate the performances of 802.15.4 MAC for the beacon-enabled mode, using NS-2 simulations. They found that an extremely low duty cycle operation enables significant energy savings but can lead to an important latency and a low bandwidth. The CSMA-CA algorithm reduces the energy costs but increases the number of collisions at a higher rate and with a larger number of sources. However, the use of GTS (Guaranteed Time Slots) can ensure a low latency but increases the energy costs. Thus, it is difficult to find a tradeoff, which mainly depends on the context and the type of application (real time, high throughput…). In this study, no guideline is proposed to tune the parameters of the simulator. [START_REF] Zheng | A comprehensive performance study of IEEE 802.15. 4, Sensor Network Operations[END_REF] a complete simulation set using the Samsung/CUNY 802.15.4 implementation in an NS-2 simulator [START_REF]Ns2 simulator for 802[END_REF]. This study shows that the 802.15.4 standard suffers from hidden terminal problems because of the absence of any RTS/CTS mechanism. However, for low data rates (up to one packet per second), the performance decrease is minor. The default CSMA-CA backoff period is too short, which leads to frequent repeated collisions. The superframes with low beacon orders (short duration between beacons) can also lower the slotted CSMA-CA backoff efficiency and lead to a high collision probability when the superframes are launched.

Zheng et al. present in

In [START_REF] Koubaa | A Comprehensive Simulation Study of Slotted CSMA/CA for IEEE 802.15.4 Wireless Sensor Networks[END_REF], the authors have developed simulation tools for IEEE 802.15.4 slotted CSMA/CA mechanism using an OPNET simulator [START_REF]OPNET Modeler[END_REF]. The sensor network is composed of a PAN coordinator and 100 nodes randomly spread in a 100m x 100m area. The basic conclusions are that the backoff algorithm is not flexible enough for large-scale sensor networks; the offered load (corresponding to the inter-arrival times of the flows in each node) should be around 50% to offer the best trade-off between throughput and average delay; lower superframe orders (active duration of the superframe) introduce additional overheads and thus limit the throughput.

The performance of the IEEE 802.15.4 contention access period is also analyzed in [START_REF] Ramachandran | Analysis of the contention access period of IEEE 802.15.4 MAC[END_REF] in terms of throughput and energy consumption. For the analysis, the behavior of the nodes and the channel are modeled, using Markov chains. For the lower layers, the authors used the characteristics of the CC2420 transceiver. They show that the standard specified MAC can be accurately modeled as non-persistent CSMA. They also demonstrate that letting the radio in a shutdown state between the different transmissions is a very effective means of reducing the average power consumption for a very wide range of traffic rates. Finally, they propose to initialize the contention window length to 1, in order to significantly improve the throughput and reduce the energy consumption when MAClevel acknowledgements are not used. [START_REF] Misic | Performance of a Beacon Enabled IEEE 802.15.4 Cluster with Downlink and Uplink Traffic[END_REF] the operation of the IEEE 802.15.4 MAC layer in the beacon-enabled mode through discrete time Markov chains. They identify the downlink queue stability at the PAN coordinator as the tightest criterion for the network. Consequently, they assume that the number of nodes and their traffic load should be chosen to avoid the saturation point of the network.

Misic et al. have modeled in

In [START_REF] Singh | Performance evaluation of an IEEE 802.15.4 sensor network with a star topology[END_REF], the authors provide an analytic performance model using Markov chains in order to compute the saturation throughput of the network in a star topology. The model is validated through simulations with NS2 in a network composed of a maximum of 50 nodes. One of the main conclusions is that the aggregated throughput is never higher than 70Kbps, whatever the number of nodes and the total load.

As far as we know, no comparison between WPAN 802.15.4 simulators and real testbed has ever been carried out. The added value of our study is thus to present and analyse a complete set of measurements (throughput, RSSI and loss ratio) with a recent 802.15.4 testbed and then to compare the testbed and the simulators' results in order to point out their divergences and the causes of these divergences.

III. EVALUATION OF MAC LAYERS OVER IMOTE2

A. Context

In this section, we point out the significant impact of the environment on wireless communications. The indoor environment is more common (companies, offices, home, etc). The outdoor environment represents a free-space area without any physical obstacle, such as emergency deployments. It is thus much less frequent, especially in a WPAN context. Nevertheless, many performance simulation studies on WPAN use the free-space or the two-ray ground propagation models, whatever the supposed context. These models are obviously not adapted to an indoor environment. The free-space model does not take into account the floor reflection signals and the two-ray ground model takes these signals into account from a certain distance threshold between the transmitter and the receiver.

For our experiment, we selected four realistic environments. The first one is an outdoor environment corresponding to our campus park without any obstacle (freespace). The three others are indoor and take place in our laboratory building. As the WiFi technology is currently used in all buildings, we kept the existing IEEE 802.11g communication on, in order to get results as close to the reality as possible. When the 802.15.4 sensor wants to send a packet, it selects an available channel. The first indoor environment is the most usual one: it is represented by our laboratory, made up of 15-30m2 offices located along a corridor (figure 1). For this indoor-office environment, we use a simple scenario with a fixed emitter and a mobile receiver in order to evaluate the range and the fading effects across several offices (each office is 3 meter long and is separated from the next one by a concrete wall 30cm thick). The objective here is to characterize and compare the different MAC layers existing for the CC2420 transceiver, another scenario with several emitters creating contention is presented in next section. The second indoor environment is the corridor also shown in figure 1. The goal is to highlight the corridor effect which theoretically allows higher ranges. The third indoor environment is the hall of our building, an open space with a ten meter high ceiling and a length of eighty meter in its longest part. This place is comparable with station or airport halls.

In both scenarios, we used one CBR connection with the maximum rate in order to reach the limit of the channel capacity (1kHz). The selected frame size is set to its maximum value (127 Bytes). The transmitter and receiver nodes are placed at a height of 1m corresponding to a desk height. The distance between them fluctuates between 0 and 65m, which is almost the maximum range except for the corridor. The nodes used in the testbed are the recent MEMSIC (formerly Crossbow) [START_REF]MEMSIC Company[END_REF] Imote2 equipped with CC2420 radio transceiver (see table I). The native MAC protocol in Imote2 sensors (BMAC) does not observe IEEE 802.15.4 standard and many capabilities, such as the beacon-enabled mode, are not implemented. In order to compare BMAC and other protocols in conformity with the standard, we have adapted the TKN-15.4 MAC protocol implementation provided by the TinyOS 15.4 working group [START_REF]TinyOS 15.4 working group[END_REF] to the Imote2 platform. In this study, we only focus on the non-beacon-enabled mode, in order to provide a fair comparison between TKN-15.4 and BMAC. The selected metrics are the throughput, the RSSI (Received Signal Strength Indication) and the packet loss ratio in order to evaluate the performance of the transmission and the quality of the channel.

B. Results

The results related to the average throughput assessed at the receiver according to the different distances between the sender and the receiver are plotted in figures 2 and 3. Both scenarios (outdoor-free-space, indoor-office, indoor-corridor and indoorhall) and the three MAC layers (BMAC, TKN-15.4, and TKN-15.4 with ACK) are represented. Whatever the context, the TKN-15.4 MAC layer gives a better result than BMAC in terms of throughput. The TKN-15.4 enhances the throughput up to 50% compared to BMAC. This result reflects the different implementations of both MAC protocols in terms of buffer management policy and backoff algorithms. Except in the case of BMAC, the throughput reaches 50% of the raw bit rate (250 kbps). In addition, we can compare the throughput provided by the same MAC layer (TKN-15.4) in both acknowledgement-enabled and non-acknowledgement enabled modes. This comparison shows that the acknowledgementenabled mode is more reliable thanks to the retransmission mechanism, whereas the non-acknowledgement-enabled mode provides a 10% higher capacity (see also figure 6 and7).

In the outdoor scenario (line-of-sight), the measured range is about the triple (55m) of that obtained in an office environment (15m). Until this value, the throughput in the outdoor scenario is almost constant. This result demonstrates the robustness of the 802.15.4 channel. In the indoor-office scenario, the throughput becomes null beyond 15m (no more propagation) which correspond to 5 offices. Before this threshold, up to the 4th office, the throughput remains almost constant with weak variations proportional to the RSSI (see figure 4). Let us note that it is mainly the number of walls which limit the range, this one would be higher for longer offices. The range for the indoor-hall scenario (65m) is a little higher than for the outdoor context (55m) thanks to the reflections on the floor and the walls. These effects are much more important in the case of the corridor: the geometry of the places (1.6m between both walls) associated to a line-of-sight propagation favors a wave canalization effect. These reflections produce an important gain and increase the range up to 180m. Let us also note that the corridor effect produces, for a distance of 25m, a weak reduction of the throughput due to the superposition, at this point, of the direct signal (with a 2.4GHz carrier) and the signal reflected on the floor. Figures 4 and5 show the evolution of the RSSI and throughput measured at the receiver according to the distance (only the TKN-15.4 MAC layer without ACK is plotted). In the cases of the outdoor and the indoor-hall scenarios, according to the mathematic formulation of free-space environment, the signal level should decrease according to the distance square. The measured signal level is more versatile than expected, particularly in the hall. It depends on many parameters, such as the characteristics and orientation of the antennas, the ground reflections, the potential background noise, etc. For the corridor, the RSSI remains almost constant between 40m and 160m which confirms the corridor effect due to the importance of the reflections. In the case of the office environment, we expected a significant fluctuation of the signal level because of the number and nature of the dividing walls, the people moving in the area, the interferences with other transmissions, etc. The results show that the signal level decreases starting from the 2nd wall and remains relatively constant up to the 5th wall, which also demonstrates the robustness of the channel. What is the impact of the RSSI fluctuations on the throughput? Figure 4 and 5 show that the throughput remains constant up to a certain threshold (from 15 to 160m, depending on the environment), even if the signal level decreases or fluctuates. The 802.15.4 device thus tries to maintain a high data rate until a certain received power threshold (approximately -40dB).

The fluctuation of the packet loss ratio according to the distance is plotted in figures 6 and 7. The ratio is much higher for the BMAC in both contexts, which explains the differences in the measured throughputs. With the TKN-15.4 protocol, the loss rate remains very weak for ranges that are close to the limit. Even in the indoor-office environment, the rate remains lower than 15% until a 15m distance (4 offices). For the corridor scenario, the corridor effect at 25m is also illustrated in figure 7. Finally, the measured ratios enable us to give some guidelines for an IEEE 802.15.4 network deployment in both indoor and outdoor environments: the router mesh should have a 15-20m diameter in a noisy indoor environment and a 50-60 m diameter in a free-space environment.

IV. COMPARISONS BETWEEN TESTBED AND SIMULATORS

A. NS2

NS-2 [START_REF]The Network Simulator NS-2[END_REF] is currently the most popular network simulator. We used the Free-Space propagation models to simulate the outdoor environment and the Shadowing model with different parameters to simulate the indoor environment. In the latest versions of NS-2, the IEEE 802.15.4 extension developed at the City College of New York is included. Moreover, NS-2 observes the 802.15.4 standard and the frames are always acknowledged. The simulation parameters (frame size, CBR rate, data rate) are the same as those used for the testbed. The transmitted power is tuned in the free-space model in order to obtain a 55m reception range. To be as close to the real testbed as possible, neither the background noise nor the interferences are taken into account in the vicinity of the nodes.

For the Free-Space model, the signal power attenuation is proportional to 1/d 2 :

ܲ = ܲ ௧ ܩ ௧ ܩ ߣ ଶ (4ߨ݀) ଶ ܮ
G t and G r are the antennas gains, λ the wavelength, L the Loss Factor and d the distance between two nodes. We tuned the values of Transmitted Power (P t ) and Capture Threshold (P r ) to obtain the same range as in the real testbed. These reference values are also used for the other propagation models.

For the shadowing model, two important parameters are used to differentiate the environment:

ܲ (݀) ܲ (݀ ) ൨ ௗ = -10ߚ log ൬ ݀ ݀ ൰ + ܺ ௗ
where d 0 is a reference distance, β is the path loss exponent and is usually empirically determined by a field measurement.

For instance, β=2 corresponds to a free-space propagation.

When we set β to a larger value, that means that the number of obstructions is more significant, and the greater the distance, the faster the decrease of the received signal power. The second parameter X dB is a log-normal random variable which reflects the fluctuation of the received power at a certain distance. X dB is thus a Gaussian random variable with zero mean and a standard deviation σ dB which is called the shadowing deviation. σ dB is also obtained by measurement. For example, σ dB =7dB corresponds to an obstructed office environment.

B. Qualnet

In order to carry out an efficient and fair comparison between the simulators, we used the same parameters as in NS-2. The proposed propagation models are close to those proposed in NS-2: free-space and log-normal shadowing (in this model, only the deviation parameter is used). Qualnet also proposes the Rayleigh fading model, which occurs when there is no line of sight between the source and destination.

C. OPNET

The wireless suite of OPNET Modeler [START_REF] Qualnet | [END_REF] integrates 802.15.4 devices (PHY Extended Rate) and offers 5 propagation models intended for outdoor environments (Free-Space, Longley-Rice, Hata, CCIR, Walfisch-Ikegami). OPNET Modeler views all wireless channels as Gaussian channels (uniform noise spectral density) and ignores the fading effect. In addition, OPNET uses a fixed value of the pathloss exponent without considering the diversity of the environments. As for NS-2 and Qualnet the transmitted power is tuned in the freespace model in order to obtain a 55m reception range. In that case, the obtained throughput is close to the reality.

D. Results

For these comparisons, we use three scenarios. Two scenarios (outdoor-free-space and indoor-office) with one fixed emitter and a mobile receiver, like previously. The third is located in an office with one receiver and from 1 to 7 transmitters in order to evaluate the impact of the contention on the global throughput. The transmitters are placed at 1m from the receiver. Each transmitter is located at 10cm from its neighbor.

The testbed results are used as reference to compare the performances of the three simulators, see figures 8, 9 and 10. First, we notice that the throughput obtained with NS-2 simulations is always higher, whatever the model. This is mainly due to the implementation of the 802.15.4 MAC layer. As for all simulators, the free-space model gives a binary response: beyond a certain threshold, no more packets will be received. The shadowing model offers results closer to the reality but the parameters that drive the shadowing propagation are difficult to set. The documentation of NS-2 gives typical values of β and σ (for example: β=2 and σ=4 to 12dB for an outdoor free-space environment; β=4 to 6 and σ=6.8dB for an indoor obstructed environment) but the shadowing model is probabilistic and insofar as these parameters have to be determined by field measurement, it is difficult to reflect the reality. Thus, it is possible to tune the parameters in order to obtain a curve close to the reality (indoor or outdoor) but these configurations cannot be generalized. In figure 8, for β=2 and σ=4, the throughput shows almost the same decrease as for the testbed in the indoor environment. However, according to the model, these parameters correspond to an "in building, line-ofsight" environment.

Concerning Qualnet, the first remark is related to the average values of the throughputs which are lower than those obtained with the testbed or the other simulators (in the indoor and outdoor environments). Once again, the implementation of the MAC layer (backoff algorithm, clear channel assessment, MAC buffers…) has a significant impact on the performance. As for NS-2, the shadowing model gives better results for the indoor environment, despite a lower throughput. The shadowing deviation is tuned in order to obtain a curve close to the reality (σ=4dB) and the configuration is much more precise and effective than for NS.

The free-space model of OPNET gives results close to the reality. With the same power value, the other propagation models give very nearby results and are thus not represented. They are indeed designed for an outdoor environment and thus for transmission powers much higher than those usually used in IEEE 802.15.4 (greater than 100mW) and for antennas with a range much higher than this present in the nodes (greater than 100m). Although OPNET integrates 802.15.4 device and a lot of potential configurations (noise, loss factor, antenna models…), the propagation models proposed by default do not enable to carry out simulations close to the reality in an indoor environment (the HATA model plotted in figure 9 gives a binary response like for the free-space model). It is necessary in this case to add other propagation models, such as the shadowing model. In addition, the beacon-enabled mode is not implemented.

For the scenario with contention (figure 10), the shadowing model proposed in NS2, with optimized parameters (β=2 and σ=4) gives results very close to those obtained with the testbed: the average global throughput increases slightly with the number of sources until a threshold close to 135Kbps. For the other simulators, the increase is much more important (up to 175kbps). This result confirms that for OPNET and Qualnet, the implementation of the radio physical layer is not very realistic; the contentions are minimized which leads to a faster channel access when several sources compete. The 802.15.4 MAC layers implemented in the recent devices based on the CC2420 transceiver can be incomplete compared to the standard. The performances show that up to a certain range threshold, the throughput in both indoor and outdoor contexts is relatively constant, which confirms the robustness of the 802.15.4 channel. The lower layers of the simulators are approximate, do not include realistic propagation models and give a throughput that is not realistic. Finally, despite a difficult tuning of the propagation model parameters, NS-2 gives the results closest to reality in the indoor scenario, while OPNET gives the best results in the outdoor scenario.

  15.4 implementations (B-MAC, TinyOS 15.4 WG, TinyOS ZigBee WG, etc.) but we are not aware of any comparative study between the devices. 2) No work proposed a recent IEEE 802.15.4 comparative study between simulators. 3) No work studies the simulator relevance in comparison with real 802.15.4 testbed.

Figure 1 .

 1 Figure 1. The indoor environment (Paris-Est computing research laboratory)

Figure 2 .Figure 3 .Figure 5 .

 235 Figure 2. Throughput vs Distance (Office and Outdoor)

Figure 6 .Figure 7 .

 67 Figure 6. Packet Loss Ratio vs Distance (Office and Outdoor)

Figure 8 .Figure 9 .Figure 10 .

 8910 Figure 8. Throughput vs Distance Outdoor (Testbed and Simulators)

TABLE I

 I

	.	CC2420 CHARACTERISTICS
	Frequency Band (ISM)	2400.0 -2483.5 MHz
	Data Rate		250 kb/s
	Tx Power		-24 -0 dBm
	Rx Sensitivity		-94 dBm
	Range (line of sight)		~30 m

In our future works, we plan to extend our study to the IEEE 802.15.4 beacon-enabled mode. In addition, improving the lower layers of the network simulators in order to generate results which are closer to the reality is another challenge.


Frédéric Fauberteau
email: frederic.fauberteau@univ-paris-est.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

Manar Qamhieh
email: qamhieh@ece.fr

Partitioned Scheduling of Parallel Real-time Tasks on Multiprocessor Systems

In this paper, we focus on the scheduling of periodic fork-join real-time tasks on multiprocessor systems. Parallel real-time tasks of fork-join model have strict parallel segments with no laxity. We propose a partitioned scheduling algorithm which increases the laxity of the parallel segments and therefore the schedulability of tasksets of this model. A similar algorithm has been proposed in the literature but it produces job migrations. Ours avoid the use of job migrations in order to create a portable algorithm that can be implemented on a standard Linux kernel. Results of extensive simulations are provided in order to analyze the schedulability of the proposed algorithm compared to the previous one.

Introduction

Chip manufacturers are tending to build multiprocessors and multi-core processors as a solution to overcome the physical constrains of the manufacturing process, such as chip's size and heating. Because of that, parallel programming has gained a higher importance although it has been used for many years.

The concept of parallel programming is to write a code that can be executed simultaneously on different processors, and usually these programs are harder to be written than sequential ones, since it is necessary to keep the parallel partitions independent in order to execute them correctly on different processors at the same time. This condition might not be affected by reasons like shortage in processors, which requires the use of partitioning. In real-time systems and as we found in literature [START_REF] Goossens | Gang ftp scheduling of periodic and parallel rigid real-time tasks[END_REF], [START_REF] Kato | Gang edf scheduling of parallel task systems[END_REF], a parallel task can be:

• rigid if the number of processors is assigned externally to the scheduler and can't be changed during execution,

• moldable if the number of processors is assigned by the scheduler and can't be changed during execution, • malleable if the number of processors can be changed by the scheduler during execution. From practical implementation's point of view, there exist certain libraries, APIs and models created specially for parallel programming like POSIX threads [START_REF]Posix threads programming[END_REF] and OpenMP [START_REF]Openmp[END_REF], except those are not designed for real-time systems normally, but in this paper we will work on periodic real-time tasks of fork-join structure, the same structure OpenMP is based on, and which can be seen as a rigid type of real-time parallelism.

The remainder of this paper is organized as follows: in Section 2, we present our task model. Section 3 describes a related work on the same model. Section 4 explains the proposed algorithm followed by the analysis in section 5. and we finish with perspective and the conclusion in sections 6 and 7.

Fork-Join Model

As shown in Figure 1, the fork-join model defines a task as a collection of several segments, both sequential and parallel, and this task always starts by a sequential segment, then it forks into several parallel independent threads (parallel segment) to be joined finally in another sequential segment. It is important to note that all parallel segments in a task shares the same number of processors, and it should be mentioned that tasks of this model have implicit deadline (deadline of a task equals its period ).

Here is an example of the fork-join model:

τ i = ((C 1 i , P 2 i , C 3 i , ..., P si-1 i , C si i ), m i , T i
) where: • s i is the total number of segments (sequential and parallel) and it is an odd number according to definition of the model,

• m i is the number of parallel threads on which parallel segments will be executed. m i > 1 for parallel segments, and equals to 1 for sequential segments. • C s i is the Worst-Case Execution Time (WCET) of sequential segment, where s is an odd number and 1 ≤ s ≤ s i , • P s i is the WCET of parallel segment, where s is an even number and 1 ≤ s ≤ s i , • T i is the period of the task. What we can notice about this model is the fact that by default all parallel segments have to finish their execution before the following sequential segment starts. Therefore these segments have strict laxity and their execution times equal to their deadlines.

Figure 2 shows a fork-join task, which can be represented as well according to the previous definition: (1, 2, 2, 3, 1), 3, 17).

S1 P11 P12 P13 S2 P21 P23 P22 S3 S1 P11 P13' P12 P13" S2 P21 P22 P23' P23" S3 S1 P11 P12 P13 S2 P21 P22 P23 S3 Figure 2.
Example of fork-join task.

Related work

Due to the strict laxity of the parallel segments in the fork-join task model, Lakshmanan et al. in [START_REF] Lakshmanan | Scheduling parallel real-time tasks on multi-core processors[END_REF] propose an algorithm to increase the laxity of the parallel segments by reducing the parallelism in the fork-join model when possible. Their algorithm stretches the main thread to its deadline, as shown in Figure 3. It aims to execute as much parallel segments as possible in the master string thread (the thread that contains the sequential segments and it is also considered as the entry and end point of the program), this master string will be stretched to its deadline so as to be executed on an exclusive processor with 100% processor's utilization. What remains of the parallel segments will be distributed on the available processors using partitioning algorithm called FBB-FFD (stands for Fisher Baruah Baker -First Fit Decreasing) [START_REF] Fisher | The partitioned scheduling of sporadic tasks according to staticpriorities[END_REF].

This algorithm enhances the schedulability of parallel tasks of fork-join structure, by increasing the parallel segments deadline and getting rid of their strict execution time, as shown in the example of Figure 2 and 3, parallel segment P 1,3 has a deadline of 4 time units instead of 2 which was exactly the worst case execution time of that parallel segment, then it has to migrate to the master string so as to fill the master thread. This laxity in the deadline will increase the chances of the parallel segments to be scheduled using FBB-FFD as it will be clarified later in the analysis.

The number of job migrations in this algorithm could be either 0, if the algorithm succeeded in scheduling all the parallel segments into the master string, creating a sequential task that will be executed on one processor. The other possibility for the number of job migrations will be the number of parallel segments in the task, as shown in Figure 3 , both P 1,3 and P 2,3 are used to fill the slack time in the master string, and they both will migrate. Task Stretch Transformation (TST) has a constraint when it comes to practical implementation, that in order to achieve a fully stretched master string, then job migration is inevitable. As shown in the Figure 3, segments P 1,3 and P 2,3 have to start execution on a certain processor then they will migrate to the master string's processor in order to fill it. According to the paper, this can be easily implemented on a specific Linux system called Linux/RK [START_REF] Oikawa | Portable rk: A portable resource kernel for guaranteed and enforced timing behavior[END_REF] (stands for Linux Resource Kernel), which is a real-time extension to the Linux kernel to support the abstractions of a resource kernel. But our idea is to implement this algorithm directly on a standard Linux enhanced with PREEMPT_RT kernel patch.

Segment Stretch Transformation

In order to eliminate the use of job migration, some modifications have to be done on the original pseudocode, which we called Segment Stretch Transformation (SST), the basic idea of TST stayed the same, we will keep trying to avoid the fork-join model by stretching the master string, but now it will be filled only with complete parallel segments with no migration, the following example will better explain the modifications.

We have a task τ 1 = ((1, 2, 2, 3, 1), 3, 17) as shown in Figure 2, which is a typical fork-join task. In Figure 2 we show the result of applying TST on τ 1 . We can notice that segment P 1,3 and P 2,3 have to be executed on 2 processors. But in SST and as shown in Figure 4, the master string is only filled by complete parallel segments. Even though the master string is not fully stretched (there still a 1 unit of time not used before the deadline), the parallel segment P 2,3 will not be used. In TST, the master string has to be filled with all the parallel segments with equal partitions, which will increase the laxity of all the segments equally. But at the same time, it will increase the number of job migrations as well. However, in SST, the master string will be filled initially with the pre-calculated number of parallel strings, then we check if we can add other single parallel strings to the master string (like P 1,3 in Figure 4). The remaining parallel segments of the task with the master string will be scheduled using FBB-FFD partitioning algorithm. The laxity of the master string will increase since we did not fill it completely with parallel segments.

So, from a practical implementation point of view, the SST can be fully implemented on a standard Linux RT kernel with no special extensions or batches added, and by only using an ordinary function like sched_set_affinity(), each segment of the parallel task can be assigned to a specific processor, according to the scheduling results of any partitioning algorithm (e.g. FBB-FFD).

Analysis

In order to provide a practical analysis for these algorithms, we are going to use rtmsim (stands for Real-Time Multiprocessor SIMulator). It is a free simulation software developed at Université Paris-Est Marnela-Vallée, France [START_REF]rtmsim[END_REF]. This simulation software helps analyzing the performance of real-time scheduling algorithms by choosing one of the pre-coded approaches and run in through extensive simulation.

For our extensive simulation analysis, we considered 4 identical processors with taskset utilization varies from 0.025 to 0.975 times the number of processors in steps of 0.025, and for each utilization value we run 10,000 tasksets each of 16 parallel tasks with implicit deadline, which will be scheduled using FBB-FFD partitioning algorithm.

We started the analysis by creating a dataset of parallel tasks of the fork-join model, and by using FBB-FFD directly to schedule this dataset, we got the results shown in Figure 5(a) (the curve with the rectangle points). And as we can see from this result, FBB-FFD failed to schedule the dataset after processors' utilization of 0.1. This can be explained by knowing that FBB-FFD is using the following condition. For each task τ i to be placed on processor k, the following condition has to be true:

d i - τj ∈τ (π k ) RBF * (τ j , d i ) ≥ e i
where τ i is the task to be scheduled on processor k, π k is the set of tasks already placed on processor k and RBF * (τ j , d i ) = e j + According to this condition, if the task to be scheduled has both execution time and deadline of the same value, then it will be executed on an empty processor, considering the condition will fail if the processor already executes other tasks. And since parallel segments in the fork-join model have execution times equal to their deadlines always (Figure 2), then each parallel segment will need to be executed on a processor exclusively.

But by looking at the characteristics of the parallel segments, we can notice that they have offsets which means that they will not arrive all at the same time to be scheduled, and by using a suitable type of partitioning algorithm that can handle offsets we might be able to enhance the results of the simulation. FDD-RTA (First Fit Decreasing-Response Time Analysis) could be a good choice.

A second analysis is performed to compare TST and SST algorithms, by using the same model of extensive simulation described previously, the result of simulation is shown in Figure 5(a), where TST is the curve with the round points and SST is the curve with the square ones. As we can see, both curves are the same with no noticeable difference. There is a slight difference between these 2 algorithms as represented in Figure 5(b). The interesting result we can notice is the incomparability of these 2 algorithms.

Perspective

The temporal constraints of the theoretical real-time systems such as the worst case execution time, the deadline and the period, all these values can be estimated and specified. But when it comes to commercial real-time systems, some interferences and variations affect those constraints, the causes vary from the tasks to exceed their WCET, OS overheads to system interrupts [START_REF] Davis | Robust priority assignment for fixed priority real-time systems[END_REF], those variations made the constraints harder to be controlled and studied.

There exist some mechanisms to compute the variations in the temporal constraints and to analyze the interferences, among those we can mention as example the sensitivity analysis, which "provides useful information for changing the implementation by giving a measure of those computation times that must be reduced to achieve feasibility" [START_REF] Bini | Sensitivity analysis for fixed-priority real-time systems[END_REF]. And task's allowance which is defined as the maximum extra duration that can be granted to a faulty task without compromising the timeliness constraint of the task [START_REF] Bougueroua | Dealing with execution-overruns to improve the temporal robustness of real-time systems scheduled fp and edf[END_REF].

The principal idea of the algorithm TST is to design a full master string, where the processor's utilization is 100%, and there is no laxity which means the worst execution time of the task equals to its deadline. However, in our proposed algorithm SST, we stopped the migration and created a non-full master string by filling it with complete segments, which increased the laxity of the master string as well as the parallel segments, and it is a step forward to build a robust system.

In the future, we aim to provide an algorithm which computes a robust partitioning, in which we maximize the acceptable variations of the temporal constraints, taking into account the variations of possible WCET overruns. As well as maximizing the duration of a task without compromise missing its deadline [START_REF] Fauberteau | A robust partitioned scheduling for real-time multiprocessor systems[END_REF].

Conclusion

In this paper, we presented an algorithm that transforms parallel tasks of fork-join structure in order to increase the laxity of the parallel segments, and eliminate the use of job migration, which makes it possible to be implemented on standard Linux kernel. The analysis of this algorithm is performed by using extensive simulations in order to compare its performance with the original taskset model and TST algorithm. Our next step will be to study the possibility of proposing a robust partitioning algorithm so as to maximize the laxity of the segments and tolerate the execution overruns of the parallel task model.

7

 7

Figure 1 .

 1 Figure 1. Fork-Join structure model.

Figure 3 .

 3 Figure 3. Task Stretch Transformation.

Figure 4 .

 4 Figure 4. Segment Stretch Transformation.


Frédéric Fauberteau
email: frederic.fauberteau@univ-paris-est.fr

Serge Midonnet
email: serge.midonnet@univ-paris-est.fr

Laurent George
email: lgeorge@ieee.org

Laxity-Based Restricted-Migration Scheduling

We focus on the real-time multiprocessor scheduling of periodic tasksets. We propose a new static priority scheduling algorithm based on the restricted-migration approach. Restricted-migration approach is a global scheduling approach for which the number of migrations is bounded just by one migration per job at most. Our algorithm uses the laxity of already admitted jobs to decide the admission of newly arrived jobs. We prove that this algorithm is predictable. We give a feasible interval and we propose a utilization bound for this algorithm. We also compare our algorithm to other global algorithms in terms of schedulability by simulations.

Introduction

One of the most studied model of recurring realtime tasks is the periodic task model of Liu and Layland [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]. In the periodic model, a periodic task is characterized by a Worst Case Execution Time (WCET) and a period. Each job of a recurring task must be completed before its absolute deadline which is equal to its activation time plus the relative deadline of the task. Three levels of constraint on the deadline of tasks are studied in the literature: (i) implicit deadlines for which the deadline of a task is equal to its period, (ii) constrained deadlines for which the deadline of a task is less than or equal to its period and (iii) arbitrary deadlines for which there are no relations between the deadline of a task and its period. A recurring task is also characterized by an offset. The offset of a task corresponds to the time before which the first job of this task is activated. This research focus on the scheduling of periodic tasks with constrained deadlines and offsets.

A priority-driven preemptive scheduler schedules a set of tasks by executing the highest priority active job and by preempting the actual executed job if the processor is not idle. There are three main classes of priority algorithms: (i) static priority algorithms (or fixed tasks priority algorithms), (ii) fixed job priority algorithms and (iii) dynamic priority algorithms. Static priority algorithms assign a priority to each task and each job of a task inherits the priority of this task. A job keeps the same priority during its lifetime (e.g. Rate Monotonic [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF], Deadline Monotonic [START_REF] Leung | On the complexity of fixed-priority scheduling of periodic, real-time tasks[END_REF]). Fixed job priority algorithms assign a priority to each job and it keeps it during its lifetime (e.g. Earliest Deadline First (EDF) [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]). Dynamic priority algorithms update the priority of jobs during their lifetimes (e.g. Least Laxity First [START_REF] Mok | Fundamental design problems of distributed systems for hard-real-time environments[END_REF]). In this paper, we consider static priority scheduling of a set of periodic tasks.

In multiprocessor scheduling, there are two main approaches: (i) partitioned scheduling and (ii) global scheduling. In partitioned scheduling, the tasks are statically assigned to a processor and each job of a task is scheduled on the processor on which this task has been assigned. The interprocessor migrations are not allowed with this approach. In global scheduling, there is no assignment of task and unrestricted migrations of the jobs are allowed. In uniprocessor scheduling, EDF is an optimal algorithm for the implicit deadlines case. With this algorithm, a processor can schedule as many tasks as its capacity enables it (i.e. the sum of the utilization of tasks can be equal to 1). But in the multiprocessor case, EDF is not an optimal priority algorithm for global scheduling. There are global algorithms with dynamic priority which are optimal (e.g. PF [START_REF] Baruah | Proportionate progress: A notion of fairness in resource allocation[END_REF], PD 2 [START_REF] Anderson | Early-release fair scheduling[END_REF]). But these algorithms can lead to many context switches (i.e. preemptions and migrations). Consequently, the scheduling approaches with static priority and fixed job priority are still actively studied.

Global and partitioned scheduling approaches are incomparable in static priority and fixed job priority [START_REF] Baruah | Techniques for multiprocessor global schedulability analysis[END_REF] (i.e. there are tasksets that are schedulable using global algorithms that partitioned algorithms cannot schedule, and vice versa). Although global scheduling does not outperform partitioned scheduling, a global scheduler is more suitable for taking good scheduling decisions. While the scheduling decisions of a partitioned scheduler are taken a priori, a global scheduler decides to assign tasks dynamically and can therefore take into account the state of all the processors. But this behavior can lead to an important number of migrations (e.g. DP-Wrap algorithm produces at most m-1 migrations by time slice [START_REF] Levin | Dp-fair: A simple model for understanding optimal multiprocessor scheduling[END_REF]). The cost of migrations can represent a considerable overhead. Therefore we focus on a third approach for multiprocessor scheduling. This approach is the restricted-migration scheduling approach for which the tasks are allowed to migrate just one time per job at most. For instance, a job of a task τ 2 can not migrate at job of τ 1 arrival time (with τ 1 more priority than τ 2 ).

In this paper, we have proposed a new scheduling algorithm for the restricted-migration approach. This approach is known to have scheduling anomalies associated to WCETs (a scheduling valid when tasks experience their WCET can become non feasible when the execution duration of a task is less than its WCET). Our scheduler makes scheduling decisions by considering the laxity of already assigned jobs. The laxity of a job is the duration between its finish time and its absolute deadline. By taking into account the laxity of the jobs, our algorithm assigns the newly activated jobs to a processor with the guaranty that no already assigned jobs miss their deadline on this processor. We show that our algorithm is predictable and does not lead to scheduling anomalies associated to WCETs. We propose a feasibility condition for our algorithm that we compare to a well known global EDF feasibility condition. We then study by simulations the performances of our scheduling algorithm.

Related work

Baruah and Carpenter have proposed a restrictedmigration with fixed job priority algorithm to schedule periodic tasksets (r-EDF) [START_REF] Baruah | Multiprocessor fixedpriority scheduling with restricted interprocessor migrations[END_REF]. This algorithm has been designed to deal with hard real-time task systems (no deadline miss is allowed). Anderson, Bud and Devi have proposed the EDF-fm algorithm [START_REF] Anderson | An EDFbased restricted-migration scheduling algorithm for multiprocessor soft real-time systems[END_REF]. This algorithm has been designed to schedule soft real-time task systems (some deadlines can be missed). To the best of our knowledge, this scheduling approach has not been very studied in static priority.

For a long time, the laxity is a parameter used for scheduling decisions. One of the well-known example is LLF [START_REF] Mok | Fundamental design problems of distributed systems for hard-real-time environments[END_REF], which gives the highest priority to the task with the lowest value of laxity. But LLF suffers from high context switching overhead and Lee has proposed the scheduling algorithm Earliest Deadline until Zero Laxity (EDZL) [START_REF] Lee | On-line multiprocessor scheduling algorithms for real-time tasks[END_REF]. EDZL is based on EDF but shortcircuits it when a task has no laxity to give the highest priority to this task. Recently, Davis and Burns have proposed a similar algorithm called Fixed Priority until Zero Laxity (FPZL) [START_REF] Davis | Fpzl schedulability analysis[END_REF]. This algorithm uses a fixed task priority instead of EDF.

Remainder

The remainder of this paper is organized as follows: in Section 2, we describe the notations used in this paper. In Section 3, we present our restricted-migration scheduling algorithm. In Section 4, we discuss the predictability of our proposed algorithm. In Section 5, we give a sufficient feasibility condition based on the load(τ ) function. In Section 6, we compare our proposed algorithm with a global and a restrictedmigration scheduler, and finally, we conclude in Section 7.

Terminology

We consider a taskset τ composed of n periodic tasks (i.e. τ = {τ 1 , . . . , τ n }). The tasks are considered in decreasing order of their priorities (i.e. τ 1 is the highest priority task and τ n is the lowest priority task). Each task τ i is characterized by:

• the activation time of its first job (i.e. its offset) denoted O i , • its WCET denoted C i ,

• its relative deadline denoted D i , • its period denoted T i . We denote U i the utilization of the task τ i defined by

U i = Ci Ti .
A periodic task is a recurrence of jobs and the k th job J i,k of the task τ i is characterized by:

• its activation time denoted r i,k and defined by

r i,k = O i + kT i , • its execution requirement denoted e i,k , • its absolute deadline denoted d i,k and defined by d i,k = r i,k + D i . By definition, e i,k = C i .
We denote e i,k (t) the remaining execution time of job J i,k at time t and by definition e i,k = e i,k (r i,k ). To improve readability, we denote J i a job of τ i when we do not refer to a particular job of τ i . J i is characterized by (r i , e i , d i ). The priorities are indexed from 1 to n. We denote hp(J i , π j ) the set of higher priority jobs than J i on the processor π j and lp(J i , π j ) the set of lower priority jobs than J i on the processor π j .

We consider that τ is scheduled on a set Π of m identical processors (i.e. Π = {π i , . . . , π m }). We denote J(π m ) the set of jobs which has been assigned on the processor π m .

Scheduling algorithm

Contrary to LLF, EDZL or FPZL, our algorithm is a pure static-priority algorithm. The priority of a task (and by extension of all the jobs of this task) is decided just one time. The laxity is used to take the scheduling decisions at jobs arrival times.

We now describe the behavior of a restrictedmigration scheduler on a system consisting of m processors. The activated jobs are put in a global queue. When a processor π j becomes idle respectively to the highest priority job J i of the global queue, J i is started on π j . The processor π j is idle respectively to the job J i if either no jobs are executed on π j or a job of lower priority than J i is executed on π j . If J k (k > i) is executed on π j before the activation of J i , J k is preempted and moved to the local queue of π j . J k can be restarted only if π j becomes idle respectively to this job. In Figure 1, we represent an example taskset composed of 3 jobs: J 1 (0, 3, 5), J 2 (2, 4, 8) and J 3 (0, 10, 12). At time 0, J 1 is assigned on the idle processor π 1 and J 3 is assigned on the idle processor π 2 . At time 2, J 2 is activated and the only idle processor respectively to J 2 is π 2 . Then J 2 preempts J 3 and is executed for 4 time on π 2 . Unfortunately, J 3 misses its deadline at time 12 with 2 remaining execution time. We notice that these jobs can be successfully scheduled as shown in Figure 2. Actually, J 2 must be assigned at time 2 on the non-idle processor π 1 . From this observation, we have designed a restrictedmigration scheduling algorithm (r-SP_wl) using the laxity to decide the admission of jobs.

Definition 1 (Laxity). The laxity L j i,k (t) of the job J i,k on the processor π j at time t is the duration between the job ending and its deadline.

L j i,k (t) is defined on the time interval [r i,k , d i,k ].
The laxity of the job J i on the processor π j is defined at time r i by:

L j i (r i ) = d i -e i - Jj ∈hp(Ji,πj ) e j (r i ) (1)
Contrary to the original restricted-migration scheduling algorithm, our algorithm does not use global queue. Only a local queue per processor is needed to maintain the pending preempted jobs. The jobs are assigned on a processor at time of their activations. A job J i,k can be assigned on a processor π j at time r i,k if and only if these 2 conditions are verified:

1) the laxity of the job J i,k on π j is greater than or equal to 0:

L j i,k (r i,k ) ≥ 0 with L j i,k (r i,k
) given by Equation (1), 2) the laxity of the lower priority jobs than J i,k is greater than or equal to 0. The Condition 2) is given by:

∀J l ∈ lp(J i,k , π j ), L j l (r i,k ) -e i,k ≥ 0 (2)
The condition given by Equation (2) insures that no lower priority jobs previously assigned on the processor π j miss their deadlines. Therefore the scenario depicted in Figure 1 can not occur.

Our scheduling algorithm must maintain the values of jobs laxity in order to take scheduling decision at activation time of jobs. A data structure per processor is needed to store these values of laxity. We define the concept of processor laxity. The laxity of the processor π j is defined as the laxity of the job which has the minimum value of laxity on π j . Our algorithm works as follow:

1) when a job J i is activated, the remaining time of all the current running jobs is updated, 2) we consider the processors of Π taken in decreasing order of their laxity. J i is assigned on the first processor π j for which the Conditions 1) and 2) are verified (the processor with the maximum value of processor laxity on which J i can be assigned), 3) a new entry in the structure is added to store its value of laxity computed by Equation (1), 4) the laxity of jobs of lp(J i , π j ) is decreased by e i , 5) when J i finishes at time t, its corresponding entry in the structure is removed. If J i finishes prior to e i execution time, the value of laxity of all lower priority jobs is increased by the remaining execution time e i (t) of J i . Our algorithm runs with a linear time complexity since there are just one activated job per task at most. Likewise the space complexity is also linear for the same reason.

Predictability

In this section, we consider the schedulability of a set J of jobs (i.e. J = {J 1 , . . . , J l }). We consider this set of jobs ordered by decreasing priorities (i.e. J 1 > . . . > J l ). The execution time e i of a job J i is a value in the time interval [e - i , e + i ]. We denote J - i the job characterized by (r i , e - i , d i ) and J + i the job characterized by (r i , e + i , d i ). We denote J (k) the set {J 1 , . . . , J k }. We also denote J

(k) -= {J - 1 , . . . , J - k } and J (k) + = {J + 1 , . . . , J + k }. S(J)
denotes the start time of the lowest priority jobs of the set J. F (J) denotes the ending time of the lowest priority jobs of the set J.

Definition 2 (Predictable algorithm). An scheduling algorithm is predictable if and only if both the start times and ending times are predictable.

The start times are predictable implies S(J

(k) -) ≤ S(J (k) ) ≤ S(J (k) + ) such that 1 ≤ k ≤ l. The ending times are predictable implies F (J (k) -) ≤ F (J (k) ) ≤ F (J (k) + ) such that 1 ≤ k ≤ l.
Ha and Liu have shown that a restricted-migration scheduler is not predictable in static-priority [START_REF] Ha | Validating timing constraints in multiprocessor and distributed real-time systems[END_REF]. In Figure 3, we show the example they presented to illustrate this property. In Figure 3(a) and 3(b), the schedules arise when the execution time of J 2 has the maximum value 6 and the minimum value 2. We would conclude that these jobs always meet their deadlines. Unfortunately, this assumption is false as shown in Figure 3(c). We can then suspect r-SP_wl of being prone to anomalies of WCET reduction. In the example of the Figure 3, we notice that the standard restrictedmigration scheduler take decisions independently of the already allocated jobs. The scenario depicted in the Figure 3(c) can not occur with our algorithm because r-SP_wl does not allow J 3 to be assigned on π 2 . In Figure 4, we represent the schedule obtained from r-SP_wl for the jobs from the previous example. in the global queue until a processor becomes idle, our scheduler assigns J 4 on the processor π 1 at time of its activation (π 1 has the highest processor laxity at time 0). Then, J 3 can not be assigned on π 1 anymore because J 4 has not enough laxity. Our algorithm does not suffer from the anomalies presented by Ha and Liu. However, our algorithm is not predictable as shown in Figure 5. The Figure 5

(a) represents 3 periodic job [e - i , e + i ] D i T i J 1 [2, 3] 3 3 J 2 [2, 2] 4 4 J 3 [2, 2] 4 4 π 2 π 1 J 3 J 2 J 3 J 2 J 1 J 1 J 3 J 2 J 1 J 1 J 1 J 1 J 2 J 3 J 2 J 2 J 1 J 3 J 1 J 3 0 5 10 15 20
(a) e 1 = 3 No deadlines are missed for this scenario. But in Figure 5(b), the job J 1,3 is executed for its minimum execution time. Then at time 8, the processor π 1 becomes idle and J 2 can be assigned on it. J 3 is always assigned on π 2 and is started at time 8. At time 9, J 1 is reactivated but can be assigned neither on π 1 nor π 2 unless the deadline of either J 1 or J 2 be missed.

π 2 π 1 J 3 J 2 J 3 J 2 J 3 J 1 J 2 J 1 J 1 0 5 10 15
In order to avoid these anomalies, we propose an extension for r-SP_wl by adding a second data structure to maintain the laxity values. This second data is used in parallel of the first one and the execution time e i is replaced by the WCET C i in Equation ( 1). If a job finishes prior to C i , the laxity value of the lower priority jobs is not increased in the second structure. Thus, our scheduler maintains "virtual" value of laxity in parallel of the exact values. These virtual values of laxity depend of the WCET of tasks and do not suffer from variations of the execution time.

Proposition 1. The algorithm r-SP_wl is a predictable algorithm.

Proof: It is sufficient to notice that the scheduler makes the assignment decision independently of the actual execution time of jobs but dependently of the WCET of tasks.

Schedulability conditions 5.1. Necessary and sufficient condition

In order to decide if a taskset is schedulable, we propose a necessary and sufficient schedulability condition for r-SP_wl. This condition consists in scheduling the taskset over a feasibility interval.

Definition 3 (Feasibility interval). Let τ be a taskset and Π be a set of processors. A feasibility interval is a finite time interval such that if no deadline is missed in this time interval, then τ is schedulable on Π.

An asynchronous activation scenario for a periodic taskset τ is the set {O 1 , . . . , O n } such that ∃i, 1 ≤ i ≤ n, O i = 0. In [START_REF] Cucu | Feasibility intervals for fixed-priority real-time scheduling on uniform multiprocessors[END_REF], Cucu and Goossens have given a feasibility interval for a taskset with asynchronous activation scenario. This time interval is built from the hypothesis that the scheduling of a taskset with asynchronous scenario is periodic from time S n with the period P . The period P is equal to least common multiple of the task periods of τ . S n is the time from which at least one job of all tasks has been activated. It is recursively defined by:

• S 1 = 0 1 ; • S i = max(O i , O i + Si-1-Oi Ti T i ).
The time interval starts from X 1 . [X 1 , S n ] includes the activations of the jobs which have their deadline after time S n . X 1 is recursively defined by:

• X n = S n ; • X i = O i + Xi+1-Oi Ti T i .
Theorem 1 (Corollary 10 [START_REF] Cucu | Feasibility intervals for fixed-priority real-time scheduling on uniform multiprocessors[END_REF]). For any schedulable taskset τ on m processors, [X 1 , S n +P ] is a feasibility interval.

The schedule produced by our algorithm r-SP_wl must be periodic if we want to use this feasibility interval given by Theorem 1.

Proposition 2. The scheduling of any taskset τ produced by algorithm r-SP_wl is periodic from S n with period P .

Proof: The proof is the same as the one given for the Theorem 9 in [START_REF] Cucu | Feasibility intervals for fixed-priority real-time scheduling on uniform multiprocessors[END_REF].

Proposition 3. The time interval [X 1 , S n + P ] is a feasibility interval to decide the schedulability of a taskset scheduled by r-SP_wl.

Proof: The proof follows from Theorem 1 and Proposition 2.

We must identify the worst case activation scenario to decide the schedulability of a taskset τ on a set of processor Π. Definition 4 (Worst case activation scenario). An activation scenario characterized by {O 1 , . . . , O n } for a taskset τ of n tasks is the worst case activation scenario if and only if τ is schedulable (resp. unschedulable) implies τ is schedulable (resp. unschedulable) for any activation scenario.

In static-priority uniprocessor scheduling, the worst case activation scenario is the synchronous scenario. The synchronous scenario is the scenario for which ∀i ∈ 1 ≤ i ≤ n, O i = 0. In the multiprocessor case, the worst case scenario is not necessarily the synchronous scenario. Proposition 4. The worst case activation scenario for a taskset τ is not necessarily the synchronous scenario.

Proof: We consider the taskset τ consisting of 6 tasks: τ 1 (0, 6, 6, 14), τ 2 (0, 7, 7, 12), τ 3 (0, 1, 11, 16), τ 4 (0, 7, 27, 57), τ 5 (0, 1, 62, 67) and τ 6 (0, 21, 81, 88). This synchronous taskset is schedulable with r-SP_wl since no deadline has been missed during the simulation of this scheduling over the interval [0, 4705008]. However, the taskset obtained from τ with 0 3 = 1 is not schedulable and τ 6 misses its deadline at time 3329384.

Hence all possible scenarios have to be considered to identify the worst case activation scenario. Goossens has shown that just n i=1 Ti P are non-equivalent activation scenarios [START_REF] Goossens | The non-optimality of the monotonic priority assignments for hard real-time offset free systems[END_REF]. To decide the schedulability of a taskset τ on a set of Π processors, all the nonequivalent scenarios must be studied on their time interval [X 1 , S n + P ].

Utilization Bound

The necessary and sufficient schedulability condition for the algorithm r-SP_wl is exponential regarding the number of tasks. In the worst case, periods with different prime number values exponentially increase the least common multiple P . Therefore we propose a utilization bound to decide the schedulability of a taskset τ with this algorithm.

This bound is based on LOAD and is inspired by the bound proposed by Baruah and Fisher [START_REF] Baruah | Global fixed-priority scheduling of arbitrary-deadline sporadic task systems[END_REF]. Definition 5 (DBF). For any time interval of length t, the DBF (τ i , t) of a task τ i bound the execution time of the jobs of τ i which both are activated and have their deadline in this interval.

Baruah, Mok and Rosier have shown that DBF (τ i , t) = max 0, ( t-Di Ti + 1)C i . Definition 6 (LOAD). For any k, the parameter LOAD is defined by:

LOAD(k) = max t>0 k j=1 DBF (τ j , t) t
We consider a taskset τ for which the priorities are assigned by a static-priority algorithm. We consider a scenario where a job of the task τ k misses its deadline. We denote t a the activation time of this job and t d the time of the deadline miss. We notice that:

t d -t a = D k (3)
We consider W (t a ) the execution time of the jobs which have a deadline ≤ t d and are executed over the time interval [t a , t d ). Our algorithm assigns the job τ k on a processor π j because it had sufficiently laxity to be executed. But a higher priority job has been activated prior to t d which implies a deadline miss for job J k . This processor has executed jobs for a duration t d -t a (it has not been idle). The only hypothesis we can do on the other processors is these processors were not idle when jobs have been admitted on π j . If a processor is idle, its minimum laxity value is considered as infinite and a job might have been admitted on it. We make the worst hypothesis that other processors than π j run the jobs which have the lowest utilization. We obtain:

W (t a ) > (t d -t a ) + (m -1)(t d -t a )U min (k) (4)
where U min (k) = min k j=1 U j . Since W (t a ) is the execution demand on the time interval [t a , t d ), all jobs which contribute to W (t a ) must have a scheduling window which intersects [t a , t d ). Then we consider the jobs which are activated after t a -D max (k) and have their deadline prior to t d + D max (k) where D max (k) = max k j=1 D j . All these jobs have their activation and their deadline in the time interval of length (2D max (k) + (t d -t a )). By definition of the LOAD parameter, we have:

W (t a ) ≤ (t d -t a + 2D max (k)) × LOAD(k)
By Inequality 4, we have:

(t d -t a ) + (m -1)(t d -t a )U min (k) < (t d -t a + 2D max (k)) × LOAD(k) ≡(t d -t a )(1 + (m -1)U min (k)) < (t d -t a + 2D max (k)) × LOAD(k) ≡1 + (m -1)U min (k) < 1 + 2 D max (k) t d -t a × LOAD(k)
By Inequality 3, we have:

1+(m-1)U min (k) < 1 + 2 D max (k) D k ×LOAD(k)
This condition is a necessarily condition for a job missing its deadline. The negation of this condition produces a sufficient condition of schedulability.

Proposition 5. A sufficient schedulability condition for a taskset τ of n tasks such that τ is schedulable with r-SP_wl is given by:

∀k : 1 ≤ k ≤ n : LOAD(k) ≤ 1 + (m -1)U min (k) 1 + 2(D max (k)/D k )

Evaluation

In order to compare our proposed algorithm with existing approaches, we performed some simulations. The simulation protocol we use is extracted from the literature [START_REF] Davis | Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF]. For each utilization value U i = i×m where i ∈ [0.025, 0.05, . . . , 0.975], we randomly generate a set of tasksets for which the utilization U (τ ) = U i . The generation of the taskset is based on the algorithm UUnifast [START_REF] Bini | Biasing effects in schedulability measures[END_REF]. This algorithm has been initially proposed in order to randomly generate taskset for uniprocessor systems. It has been extended to UUniFast-Discard [START_REF] Davis | Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF] for the multiprocessor case. We show in Figure 6 a comparison of schedulability for three different algorithms in static priority. The first one is a global scheduler, the second one is a standard restricted-migration scheduler and finally, the last one is our modified restricted-migration scheduler. The standard static-priority restricted-migration has been implemented as follows. The set of processors is sorted (using a priority queue) in increasing order of the priority of the active job (idle processors are put in head of the list). A job is put in a priority queue at its arrival time. A processor π j is free relative to job J i if π j is idle or its active job is lower priority than J i . The highest priority jobs are dequeued and put on the first free processor of the processors queue while there are ready active job and free processors.

In order to get a good intuition about the schedulability of these algorithms, we simulated the execution of the randomly generated tasksets over their feasibility intervals. Since the size of the feasibility intervals is exponential in the number of tasks, we bounded to 6 the number of tasks per taskset and to 1000 the number of tasksets per value of utilization. For the same reasons, we restrict the number of processors to 2. We notice that our proposed algorithm gives results which are much closer to those of a global scheduler than those of a standard restricted-migration scheduler. This result is interesting in the sense that the number of interprocessor migrations is bounded by just one per job at most. We show in Figure 7 the comparison between the utilization bound presented in [START_REF] Baruah | Global fixed-priority scheduling of arbitrary-deadline sporadic task systems[END_REF] and the one we proposed in Section 5.2. These two utilization bounds are based on the load bound function. Our implementation of this function is based on the one described in [START_REF] Fisher | Algorithms for determining the demand-based load of a sporadic task system[END_REF]. Unfortunately, the computation of the exact load bound function is done in exponential time and chose the computation based on the pseudopolynomial approximation scheme with a precision given by = 10 -6 . We notice that the utilization bound of our algorithm is not as good as the one of global scheduler. As we can see in [START_REF] Bertogna | Evaluation of existing schedulability tests for global EDF[END_REF], in the current stateof-the-art of schedulability conditions, no utilization bounds give efficient results.

Conclusion

We distinguish among three different categories of priority algorithms. We also distinguish among three different scheduling approaches concerning the amount of interprocessor migration allowed. There are 3 × 3 = 9 categories of scheduling algorithms which we represent in Table 1. We have focused on the restricted-migration approach in the static priority case and we have proposed a new algorithm based on the laxity. This algorithm is predictable and we have proposed a necessary and sufficient schedulability condition as well as a utilization bound. We have shown by simulation that our algorithm can schedule almost tasksets as much as a global scheduling algorithm. In order to extend this work, we intend to improve the proposed utilization bound. Since our scheduler dynamically maintains the value of laxity, we also intend to propose a slack-stealer algorithm which can be used in conjunction with r-SP_wl.

Figure 1 .

 1 Figure 1. Restricted-migration scheduling.

Figure 2 .

 2 Figure 2.Laxity-aware restricted-migration scheduling.

Figure 4 .

 4 Figure 4. Jobs scheduled with r-SP_wl

20 (b) e 1 = 3 , e 1 , 3 = 2 Figure 5 .

 20131325 Figure 5. Anomalies for r-SP_wl

Figure 6 .

 6 Figure 6. Comparison of schedulability.

Table 1 .

 1 Classification of algorithms for multiprocessor scheduling of periodic tasks.

		100 %
											g-SP
		80 %									r-SP_wl
	Schedulable tasksets	40 % 60 %
		20 %
		0 % 0.0	0.2	0.4	0.6	0.8	1.0	1.2	1.4	1.6	1.8	2.0
						CPU utilization
		Figure 7. Comparison of utilization bound.
		global
		restricted-migration this research
		partitioned
						static	fixed job dynamic