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

Abderrezak Rachedi
email: rachedi@univ-mlv.fr

Yacine Ghamri-Doudane

A Cost Function for QoS-Aware Routing in Multi-tier Wireless Multimedia Sensor Networks

Keywords: WMSNs, heterogeneous network, cost function, cross-layer, QoS

Wireless Multimedia Sensor Networks (WMSNs) are composed of small devices that are able to capture video or audio information and to transmit it over wireless channels. The development of wireless technologies, such as: WiFi, Bluetooth, Zigbee, and UWB, encourages the emergence of heterogeneous networks. However, only a few existing solutions take into account the constraints of multi-tier and multi-MAC wireless sensor networks. In this paper, we propose a cost function coupled to a new generic (i.e. independent from any MAC protocol) cross-layer routing protocol adapted to multimedia traffic over hierarchical and heterogeneous networks. The goal of our proposed protocol is to dynamically assess the routing process cost and the requirement of the multimedia application in order to ensure a sufficient quality of service (Soft QoS). Furthermore, the cross-layer approach is needed to use the physical and MAC parameters on the routing operation. Simulation results show that our solution is efficient and gives better results than classical protocols.

Introduction

The popularity of Wireless Sensor Networks (WSNs) is growing with the technological advancement that enables to design a small and smart device able to capture the multimedia information such as CMOS cameras and microphones [START_REF] James | Inside CMOS Image Sensor Technology[END_REF]. This growing interest enables the development of particular wireless sensor networks called Wireless Multimedia Sensor Networks (WMSNs). Furthermore, WMSNs enable to enlarge WSNs application field: it can be used for multimedia surveillance systems against crime and terrorist attacks, car traffic monitoring in big cities or highways, environmental monitoring through acoustic and video data, etc. Unlike classical WSNs, WMSNs have specific characteristics such as: 1) high bandwidth demand due to multimedia content, 2) specific QoS requirements that are dependent on the application, and 3) important power resource consumption due to high volumes of data to transmit (or forward) by battery-constrained devices. One should also note that due to the nature of WMSN applications, the node's mobility is not high. Obviously, WMSNs are more challenging than classical WSNs as additional constraints and parameters are introduced. That is why Akyildiz et al. [START_REF] Akyildiz | A survey on wireless multimedia sensor networks[END_REF] proposed and advocated for a multi-tier architecture. This architecture ensures the network scalability and enables the use of heterogeneous elements. These architectures provide efficient cost-performance tradeoff while taking into account less expensive and resource-constrained scalar sensors and high power superior elements such as multimedia sensors. In this architecture, the network is divided into clusters. Each cluster elects a cluster head that has sufficient resources. In this paper, we use the multi-tier architecture to ensure the scalability and the softbased quality of services [START_REF] Akyildiz | A survey on wireless multimedia sensor networks[END_REF]. We focus on the routing process to increase the throughput and reduce the packet loss and the delay. Therefore, in order to optimize the resources and make the multimedia traffic routing more efficient, we propose a new routing protocol based on a cost-function called HQAX (Hierarchical QoS Aware Cross-layer routing protocol). The basic idea of this cost function is to take into account not only the routing parameters, but also the physical and MAC layers parameters such as the channel quality, the SNR, and the number of ACK failures. Our design is thus a cross-layer design allowing taking into account physical and MAC layer parameters at the routing level. We show that with such mechanism, we can improve the network throughput; reduce the packet loss and the delay in indoor environments. The impact of the environment on the communication channel quality is very significant. For instance, in the case of an outdoor environment, called freespace, the channel quality is better than when many obstacles are present inside a building. However, most applications of WMSNs, like building surveillance, are in an indoor environment. That is why we focus on such realistic scenarios to validate our proposed protocol. After analyzing and studying WMSNs requirements and their potential implementation using multi-tier architecture, our contributions can be summarized in the three following points: ─ Proposition of a new routing protocol (HQAX) based on a cost function in order to improve the throughput and to reduce the delay and packet losses. ─ Definition of a cost function in order to optimize the resources and to make the multimedia traffic routing more efficient (the cross-layer approach is used for the cost function in order to take into account the physical and MAC layers parameters at the routing level). ─ Implementation and evaluation of the proposed routing protocol in comparison with other existing protocols like AODV and OLSR which had been adapted to cope with the features and characteristics of multi-tier WMSNs. .

The rest of the paper is organized as follows. In Section 2, we present the related works. In Section 3, we present and detail our proposed routing protocol. A description of our cost function follows in Section 4. In section 5, we evaluate and compare our solution with existing routing protocols. Section 6 concludes the paper.

Related works

Many routing protocols are proposed in the literature. In proactive networks, Heinzelman et al. proposed a Low-Energy Adaptive Clustering Hierarchy (LEACH)

for wireless sensor networks [START_REF] Heinzelman | Energy-Efficient Communication Protocol for Wireless Microsensor Networks[END_REF]. LEACH is a dynamic clustering protocol designed with energy constraint consideration. Lindsey et al. proposed an improvement of LEACH called Power-Efficient Gathering in Sensor Information Systems (PEGASIS) [START_REF] Lindsey | PEGASIS: Power-Efficient GAthering in Sensor Information Systems[END_REF]. The basic idea of PEGASIS is to form a chain among the sensor nodes where each node will receive from and transmit to a close neighbor in order to reduce the energy consumption. These protocols focus on the dynamic clustering issue. Once the clusters are established and the cluster head role assigned, it is still necessary to ensure the quality of services required by multimedia traffic. Our objective is to target this second problem.

In the QoS-aware routing protocols class, we can quote some proposals for WSNs. One of them is the Sequential Assignment Routing (SAR) [START_REF] Sohrabi | Protocols for self-organization of a wireless sensor network[END_REF]. SAR creates trees routed from a one-hop neighbor of the sink by taking into account the QoS metric, the energy resource on each path and the priority level of each packet. However, the SAR protocol does not focus on the throughput maximization. Some other routing protocols also integrate the energy parameters in addition to other QoS parameters. An example of these is the SPEED protocol [START_REF] He | SPEED: A stateless protocol for real-time communication in sensor networks[END_REF]. SPEED is a real-time communication protocol for sensor networks. The protocol provides three types of real-time communication services, namely real-time unicast, real-time area-multicast and realtime area-anycast. However, SPEED needs localization algorithms to achieve high scalability and avoid a flooding operation to discover new paths. Another protocol, proposed by C.G. Lee et al. and called Multipath Multi-SPEED Protocol (MMSPEED) [START_REF] Lee | MMSPEED: Multipath Multi-SPEED Protocol for QoS Guarantee of Reliability and Timeliness in Wireless Sensor Networks Full text[END_REF], adopts a probabilistic approach to offer QoS assurance in wireless sensor networks. To do so, it uses a cross-layer approach between the network and the MAC layers. However, MMSPEED assumes that each node is equipped with a GPS chip which may not be a suitable assumption in WSNs, especially in indoor environments.

An energy-aware routing protocol in a cluster-based architecture is presented in [START_REF] Younis | Energy-Aware Routing in Cluster-Based Sensor Networks[END_REF]. It uses a cost function based on energy saving that is coupled with a source routing protocol. Unlike our approach, the topology is multi-gateway and non multi-tier (multi-MAC). Furthermore, the protocol is specific to the use of a TDMA MAC layer.

3 Hierarchical QoS Aware Cross-Layer Routing Protocol

Context

Figure 1 describes our proposal for a multi-tier architecture inspired by the work of I.F. Akyldiz et al. [START_REF] Akyildiz | A survey on wireless multimedia sensor networks[END_REF]. In this heterogeneous and hierarchical architecture, each tier corresponds to a category of video sensors with increased capabilities in terms of camera resolution, processing, storage and transmission. For the first tier, the sensors can be CMUCam (weak resolution of 160x255) coupled with microcontrollers allowing a minimum processing and not very greedy transmissions like in ZigBee, Bluetooth or UWB standards. The second tier can be made up of a webcam and microcontrollers with more processing, more storage and mixed transmissions, ZigBee and 802.11 for instance. The last tier is connected to the sink (multimedia server) and includes high resolution cameras coupled with laptops.

Fig. 1. Multi-tier Architecture of WMSN

For each tier, our proposal is to organize the topology into clusters with a Cluster Head (CH), Cluster Routers (CR) allowing multi-hop routing when necessary, and Cluster Terminals (CT), only able to capture video information and to transmit it. In order to limit the interferences, the nearby clusters can use distinct transmission channels. The sensors of the various levels can be moved but are not permanently mobile.

Moreover, the processing essentially carried out in the CHs and towards the sink, includes specific operations like compression, data aggregation (images from different scenes in the same flow) and data suppression (redundant images from various sensors). These different characteristics of the multi-tier WMSN architecture (clustered architecture, many-to-one flows, heterogeneous capabilities, and processing into the CHs) make us believe that a hierarchical routing is the most suited one.

The goals of HQAX

The goal is not to propose an additional new routing protocol but rather to adapt existing solutions in order to have a QoS-aware routing protocol:

─ linked to the application : the sensor networks are application-aware; ─ based on a cross-layer cost function with routing, MAC and PHY parameters related to the multimedia feature of the flows; ─ adapted to a hierarchical and multi-tier (multi-MAC) architecture; ─ for many-to-one transmissions, and not for many-to-many like in current ad hoc network protocols like AODV or OLSR; ─ generic, i.e. non related to a specific MAC layer but nevertheless compatible with the existing sensor routing protocols (ZigBee); ─ with a limited overhead thanks to the combination of the cluster association with the route setup processes; ─ easy to implement in the different devices of a real test bed.

The following sections describe our QoS-aware hierarchical routing inside clusters, whatever the tier is, and between the clusters of the various tiers. The QoS route setup is the first step of our solution. Indeed, the network organization must remain evolutionary according to the periodic requests from nodes to join or leave a cluster and to the needs of the sink-application which will select, starting from descriptors (fixed image, possible resolution…), the transmitting sensors as well as the characteristics of the transmitted flows (zone, resolution, compression ratio, cropping…). Thus, the objective here is not to constantly guarantee a QoS but to choose and receive pictures of a sufficient quality (soft QoS). The idea is thus to use the best available routes.

Intra-cluster QoS Routing

The QoS routing proposed in each cluster is proactive and includes 6 stages for the cluster self-organization and the route setup procedures (Figure 2). As indicated previously, we drew our inspiration from the existing solutions like ZigBee for the association process which is adapted to cope with the multi-tier feature of the WMSNs as well as with the QoS requirements of transmitted flows.

1. Each node self-determines its potential role (CH, CR or CT) in a cluster according to fixed or periodically re-evaluated criteria:

─ sufficient storage and energy (in comparison to specific thresholds for each role); ─ for CH: transmission capacity (presence of other devices corresponding to the tier) and computational capacity for aggregation, suppression, compression….

2. Each CH initiates a cluster (scan channels, select a channel, select a cluster id…).

3. CR and CT look for a cluster (Figure 3):

─ CR/CT broadcast a discovery message: Cluster_Discovery_Request (Scan Channels…); ─ response of the nearby CHs (and/or CR in the case of a multi-hop distance) with a Cluster_Discovery_Response (Cluster Description...).

4. Evaluation of a cost 1 C ij for the links involved. This evaluation starts at stage 3 with the exchange of the Cluster_Discovery. 5. CR and CT choose a CH (or a CR) according to the previous QoS evaluation and join a cluster:

─ CR/CT send a message Cluster_Join_Request (Cluster id…); ─ response of the selected CH (or CR) with a Cluster_Join_Response (Cluster id, Network addresses…).

The associations of the CRs and the CTs are carried out in a recursive way: for the multi-hop routing, a CT out of the CH range has to wait for the association of a nearby CR to obtain an answer and thus join the cluster.

6. The CR informs its CH (or its nearby CR which is closer to the CH) about its router's role:

─ the CR sends a message Cluster_Router_Request (Cluster id…); 1 The cost function integrating the QoS parameters is described in Section 4.

─ response of the CH (or CR) with a Cluster_Router_Response Network address block (or a sub-block requesting CR for its CT

Fig. 2. Intra-cluster Routing Algorithm

After one or several exchange cycles, each CR or CT knows the address of its CH or its nearby CR (the one with the lowest cost towards the CH) CR has a routing table for all its nodes. The routing is hierarchical: all data pass through the CH. According periodically re-launched.

Inter-tier QoS Routing

The routing between the CHs of various tiers ( according to the same hierarchical and recursive principle:

1. The CH 3 (CH of third tier) broadcast 2. The CH 3 choose a CH 3. The CH 2 broadcast the CH 1 . 4. The CH 2 choose a CH 5. The CH 1 broadcast computed to evaluate if, according to a sufficient QoS on the link towards the sink.

After sufficient exchanges, (transmitted with the response to the broadcast). Each node of each cluster can thus transmit towards the sink and CH 2 …).

Utility Theory

During the messages exchange of the discovery stage (between CT/CR and CR/CH or between CH i and CH i+1 compared (i) to a threshold to decide if to get a sufficient QoS and (ii) with the costs on the other links to choose the most esponse of the CH (or CR) with a Cluster_Router_Response (Cluster id, ss block…). In its response, the CH specifies the address block lock in the case of a CR answering) which can be used by the CR for its CT and its lower level CR.

cluster Routing Algorithm Fig. 3. Intra-cluster Association Process exchange cycles, each CR or CT knows the address of its CH or its nearby CR (the one with the lowest cost towards the CH). Similarly, each CH or CR has a routing table for all its nodes. The routing is hierarchical: all data pass through the CH. According to the network dynamics, the various stages are launched.

tier QoS Routing

The routing between the CHs of various tiers (Figure 2) proceeds in 5 stages according to the same hierarchical and recursive principle:

third tier) broadcast a request to know the CH 2 . choose a CH 2 according to a cost estimated on the links. broadcast a request in their turn on the corresponding interface to know choose a CH 1 according to a cost estimated on the links. broadcast a request to know the sink. In this last case, the cost is also computed to evaluate if, according to its location and environment, the CH a sufficient QoS on the link towards the sink.

After sufficient exchanges, each CH n knows the address of its CH n-1 and (transmitted with the response to the broadcast). Each node of each cluster can thus transmit towards the sink and vice-versa (the sink knows the CH 1 which knows the

Utility Theory-based Cost function

During the messages exchange of the discovery stage (between CT/CR and CR/CH or i+1 ), the cost on each possible link is periodically estimated and compared (i) to a threshold to decide if it meets the conditions (noise, contentions…) to get a sufficient QoS and (ii) with the costs on the other links to choose the most (Cluster id, address block ) which can be used by the cluster Association Process exchange cycles, each CR or CT knows the address of its CH or each CH or CR has a routing table for all its nodes. The routing is hierarchical: all data pass , the various stages are 2) proceeds in 5 stages in their turn on the corresponding interface to know to know the sink. In this last case, the cost is also and environment, the CH 1 can get and the sink (transmitted with the response to the broadcast). Each node of each cluster can thus which knows the During the messages exchange of the discovery stage (between CT/CR and CR/CH or ), the cost on each possible link is periodically estimated and tentions…) to get a sufficient QoS and (ii) with the costs on the other links to choose the most efficient CR/CH. The cost function on a link between two nodes i and j (j being the closest to the sink) can be expressed according to the chosen QoS metrics as follows:

∑ × = k k ij k k ij x f c C ) (
where

k ij
x is the value of metric k relatively to the link between two nodes i and j, c k is the preference weight of metric k (where

1 = ∑ k k c
), and f k (:) is a normalized function. In our case, we suggest choosing the five following metrics:

) ( ) ( ) ( ) ( ) ( 5 5 4 4 3 3 2 2 1 1 j i ij ji ij ij energy f c energy f c e f c SNR f c delay f c C × + × + × + × + × = ─ f 1 (delay ij
) is a function of the delay for a data packet transmitted from i to j; ─ f 2 (SNR ji ) is a function of the Signal/Noise Ratio assessed from j to i; ─ f 3 (e ij ) gives the error rate for the data packets transmitted from i to j; ─ f 4 (energy i ) and f 5 (energy j ) give the remaining energy in i and j respectively.

The choice of weights c 1 to c 5 depends on the application and on the type of traffic (for instance, for streaming applications the delay is more important than the loss rate). Besides, for "real time" applications, it is necessary to control the end-to-end delay. Rather than using higher level protocols like RTP and RTCP which involve an overhead, we can evaluate this global delay at the routing level, starting from the delay on each link and the knowledge of the route towards the sink, both data being provided by our routing protocol. The loss rate on a path from a CT towards the sink can also be evaluated, starting from the successive loss rates and the knowledge of the route. The remaining question is related to the form to be used for the normalized f k (:) functions. To answer this question, the most suitable form can be found in the wellknown concept of utility functions. Indeed, the utility theory correctly models the soft tuning of the perceived quality in modern networks. The utility theory is used for multi-criteria selection which is a classical problem in economics and in many other fields. It is used to give a measure of the relative satisfaction from (or desirability of) the consumption of various goods and services. The use of the utility theory has been extended to many other fields where it is used as a scoring method that quantifies the score (suitability level, value, worth) of a particular choice compared to another. In our current work, we suggest to use it to quantify the utility of using a link in a QoS-aware routing process. The utility of the link corresponds here to the cost function on the link between both nodes i and j. The utility theory is thus used as the basis of our cost function. The normalized function is introduced to express different characteristics of different units with a comparable numerical representation. Different normalized functions were used in the literature to solve several QoS issues in communication networks. Among them, we can quote: the linear piecewise form [START_REF] Ormond | Economic model for cost effective network selection strategy in service oriented heterogeneous wireless network environment[END_REF], the logarithm form [START_REF] Ormond | Network selection decision in wireless heterogeneous networks[END_REF], the exponential form [START_REF] Ormond | Network selection decision in wireless heterogeneous networks[END_REF], and sigmoid forms [START_REF] Pal | User-Satisfaction based Differentiated Services for Wireless Data Networks[END_REF][START_REF] Badia | An economic model for the radio resource management in multimedia wireless systems[END_REF]. Among these, the most commonly used normalized functions are the sigmoidal (S-shaped) functions. Indeed, sigmoidal functions are well-known functions often used to describe QoS perception [START_REF] Badia | An economic model for the radio resource management in multimedia wireless systems[END_REF]. Thus we chose here to use these functions. More precisely, we consider the following analytic expression for the sigmoid form:

ζ ζ ) ( 1 ) ( ) ( m m x x x x x f - + - =
where x m > 0 and ζ ≥ 2 are tunable parameters, that differentiate the users' utilities. It is also assumed that the utilities are normalized to their highest limit, i.e. the asymptotic value of f(x) for large x is considered to be equal to 1. This is only done for the sake of simplicity [START_REF] Badia | An economic model for the radio resource management in multimedia wireless systems[END_REF]. In other more complicated scenarios, different maximum utilities can also be considered.

Performance Evaluation

Context

To analyze the improvements registered by the HQAX protocol and the cost function, we implemented a set of simulations using the NS-2 simulator (version 2.33). The selected scenario implements a hierarchical multi-tier topology. Insofar as NS-2 is not conceived to bring together various interfaces and various MAC layers in the same node or in the same wireless network, only the 802.11 MAC layer will be used in the clusters of the different tiers. The objective being here to test the efficiency of the cost function integrated into our routing protocol, in comparison with current routing protocols, the simulations can be realized without a real multi-MAC topology. We chose to use the "shadowing" radio-propagation model, which is more realistic as it takes into account the shadowing and the fading effect that are common in indoor and outdoor environments with potential mobile obstacles. Moreover, to highlight the interest of the cost function, we chose the appropriate parameters for an indoor environment corresponding for example to a building surveillance application (see Table 1). The simulated network includes 30 nodes and a sink distributed on a 135x84m area (see Figure 4). The role of each node (CH, CR or CT), which should depend on the available resources, is fixed at the beginning. The distances between the nodes are such that a CT n or a CR n has always the choice between at least two potential routes to join its CH n . It is the same for a CH n , during the association with its CH n+1 . Let us note that CH 2 or CH 3 can directly join the sink as this latter is assumed to have all MAC devices according to the use of multi-tier architecture. In addition, although the 802.11 MAC layer is common to all nodes, a CT (or a CR) can only join a CR or a CH at the same level. In this topology, all nodes can be multimedia sensors so all nodes are modeled as CBR sources. We tested several scenarios of sources activation with a number of CBR sources ranging between 1 and 30 (in this last case, all nodes are sources). The total duration of each simulation is 20s (sufficient in all cases to get a stable network) and the CBR sources are activated every 0.1s to avoid synchronized broadcast (in a multimedia sensor network, all cameras are seldom activated at the same time). In addition, in this type of applications (monitoring, surveillance …), the nodes are often fixed or very slightly mobile. We thus chose a null mobility during the simulation. The cost function implemented for the simulation is adapted to 802.11 devices and takes into account four parameters:

ܥ ൌ ܿ ଵ ൈ ݂൫݈݀݁ܽݕ ൯ ܿ ଶ ൈ ݂൫ܲݎ ൯ ܿ ଷ ൈ ሻݏ݄݂ሺ ܿ ସ ൈ ݂൫ܴܲܮ ൯
─ The delay on the link between nodes i and j is simply evaluated using a timestamp transmitted to the CDREP association packet. ─ The received power Pr is evaluated when receiving the CDREP packet.The number of hops is measured from the source to the sink. ─ The Packet Loss Rate (PLR) is calculated on the node which transmits the CDREP packet and then transmitted in this same packet to the node having requested the association or to the node relaying the answer. The PLR is calculated from the MAC-MIB 802.11 information and then uploaded at the routing level:

ܴܮܲ ெ ൌ ݐ݊ݑܥ݁ݎݑ݈݅ܽܨܭܥܣ ݐ݊ݑܥݐ݊݁݉݃ܽݎܨ݀݁ݐݐ݅݉ݏ݊ܽݎܶ ݐ݊ݑܥ݁ݎݑ݈݅ܽܨܭܥܣ
The coefficients c 1 to c 4 are optimized to get the best results in the selected context. To evaluate the HQAX performances and the associated cost function, we chose to compare it with the AODV and OLSR protocols which we adapted to a multi-tier architecture. Concerning AODV, several reasons justify this choice:

─ it is a standardized reference protocol for ad hoc networks and it is largely used in sensor networks: AODV is included in ZigBee [START_REF]ZigBee Specifications[END_REF]; ─ it is a generic protocol and it is not associated to a specific application or a particular access method as opposed to LEACH (based on dynamic clustering, energy saving and TDMA distribution) or SPEED (real time with geolocalization assumptions); ─ AODV is implemented in the most common simulators like NS-2, as opposed to some specific WSN protocols.

In addition, the choice of OLSR (the implementation used here for NS-2 is UM-OLSR [START_REF]Implementation of OLSR for NS[END_REF]) enables to compare HQAX to a proactive reference protocol in which the relay nodes (MPR) are elected according to the number of neighbors. For these simulations AODV and OLSR were adapted, including cross-layer interactions with the MAC layer, to respect the multi-tier architecture (AODV-mt and OLSR-mt on the following figures). These adaptations are made so that: a CT n /CR n can only join a CR n or a CH n ; a CH n can directly join the sink or must pass by CH n+1 ; a CT does not relay a route request broadcast; a CT cannot be elected as a MPR (in the case of OLSR).

Fig. 4. Multi-tier hierarchical scenario

Results

Figure 5 presents the evolution of the average end-to-end delay for the CBR packets on all routes towards the sink, when the number of sources varies from 1 to 30. The results are slightly better with OLSR but with a much higher loss rate (Figure 7): the delays on the intermediate links between CR and CH can be shorter because many packets are lost on the way. For AODV, the average delay fluctuates between 3 and 8 ms showing a great dependence on the number of sources and the geographical distribution of nodes. Finally, HQAX presents a stable average delay, whatever the number of active sources and relatively low if we take into account the number of actually transmitted packets. This shows the efficiency of the cost function which integrates the delay on the links. Figure 6 shows the evolution of the average global throughput for all active CBR sources. The results are very close for a low number of sources and are slightly better for HQAX for more than 5 active sources. The evaluation in the cost function of the received power and of the loss rate during the association process makes it possible to reduce the risk of contentions on the selected links. In Figure 7, the packet loss rate for all active routes increases very quickly with OLSR, mainly because of a bad load balancing on the MPR which are elected according to the number of neighbors and not to the hierarchical organization of the network. AODV enables, with its error packet transmission mechanism, to limit the loss duration but at the expense of the overhead (see Figure 8). Whatever the number of sources, the loss rate remains lower than 1% with HQAX. This confirms the interest to upload at the routing level the number of unreceived acknowledgements which is computed at the MAC level. The relative overhead of control packets (Figure 8) remains lower than 5% with OLSR and HQAX. Let us remind that for OLSR, the frequencies of Hello and TC messages are optimized for a not very dense and not mobile context. This overhead is much more important with AODV starting from 10 active sources. Although AODV is modified for our multi-tier architecture, the unsolved contentions can be numerous and the error messages can force new requests to be broadcasted, creating a strong overhead.

Conclusion and Perspectives

In this paper, we presented a complete solution including a reactive routing protocol associated with a cost function adapted to a heterogeneous and hierarchical WMSN architecture divided into clusters. This solution allows the sink to collect multimedia flows from different kind of sensors, in the various tiers, with a sufficient quality of service. The advantages of this solution are on one hand its generic feature: it does not depend on a specific MAC layer or a particular access method, and on the other hand, the fact that it is compatible with the existing link and routing layers used by wireless sensor networks: the MAC parameters used in the cost function are generic and exist in both 802.11 and 802.15.4 MIBs; furthermore, the reactive routing approach used in HQAX is compatible with that used in ZigBee.

Our simulation study shows the efficiency of this solution, particularly in terms of throughput, loss rate, and control packet overhead. This first evaluation campaign will have to be confirmed by real test-bed experiments. Such a test-bed should integrate various devices corresponding to the different WMSN tiers (WiFi and ZigBee enabled sensors). The generic and compatibility features of our proposal should facilitate such an implementation. This experimental evaluation constitutes the target of our future work.

Fig. 5 .Fig. 6 .Fig. 7 .Fig. 8 .

 5678 Fig. 5. Average Packet Delay / Number of CBR sources Fig. 6. Average Global Throughput / Number of CBR sources

Table 1 .

 1 Simulation Parameters

	Nodes number	31
	Simulation Area	135 x 84 meters
	Simulation Time	20 seconds
	Traffic Type, Packet size, Period	CBR, 1000 Bytes, 1.5 to 50ms
	Radio-propagation model	Shadowing
	Radio-propagation parameters	Reference distance=10m, β=5, σ=7dB
	Transmission Range	25-50 meters


Damien Masson
email: damien.masson@univ-mlv.fr

Serge Midonnet
email: serge.midonnet@univ-mlv.fr

The Design and Implementation of Real-time Event-based Applications with RTSJ

This paper presents a framework to design real-time event-based applications using Java. The Real-Time Specification for Java (RTSJ) is well designed for hard periodic real-time systems. Though it also proposes classes to model asynchronous events and deal with sporadic or aperiodic tasks, it remains insufficient. The literature proposes the use of periodic servers called task servers to handle nonperiodic traffics in real-time systems. Unfortunately, there is no support for task servers in RTSJ. In order to fix this lack, we propose an RTSJ extension model. To validate our design, we adapt and implement two policies: the polling server and the deferrable server policies. To show how efficient these policies are, we compare implementation results and results obtained with a discrete-event-based simulator.

Introduction

In order to bring to the real-time community the advantages of the Java language, a Java Specification Request (JSR-01) was proposed and accepted by the Java Community Process (JCP) in 1999. This lead to the Real-Time Specification for Java (RTSJ), which version 1.0 was released in November 2001 and first implementation in January 2002. Today, the specification is still evolving and commercial implementations have come out (Aïcas Jamaï-caVM or more recently Sun Mackinac).

If this specification is well designed for periodic realtime systems, the support for non-periodic servicing with temporal constraints is not fully satisfying. In order to assign time and resource constraints to a group of threads, the RTSJ proposes the use of "Processing Group Parameters" (PGP). But as pointed in [START_REF] Burns | Processing group parameters in the real-time specification for java[END_REF], no guidelines are given on how 1-4244-0910-1/07/$20.00 c 2007 IEEE.

to use them, and there is no appropriate schedulability tests to analyse them. Furthermore, the cost enforcement is an optional behaviour for an RTSJ compliant virtual machine, and without this feature, PGP are useless.

That is why we propose in this paper a framework to design real-time event-based applications using RTSJ.

We present in Section 2 the aperiodic servers mechanisms and we detail the Polling Server and the Deferrable Server policies. Section 3 describes our framework to allow the implementation of these servers with RTSJ. Then we explain our implementation of the Polling Server and the Deferrable Server policies using this framework in Section 4. In order to evaluate the efficiency of our implementations, we developed a simulator that we present in Section 5. We give the results of these executions and simulations in Section 6, and discuss of future improvements in Section 7.

Tasks servers: presentation

During years, the assumption was made that real-time systems have to be only composed of periodic-tasks sets. This assumption comes from the feasibility analysis theories. How can we compute response times of tasks which we cannot predict the arrival of ? This is a too strong restriction since many of the real world phenomena are eventbased.

One solution is to set up a mechanism which allows nonperiodic traffic to be served and analysed without changing the feasibility conditions of a periodic task.

The easiest way to achieve this is to schedule all nonperiodic tasks at a lower priority (we assume that the tasks are scheduled using a preemptive fixed priority policy). If it is very simple to implement, it does not offer satisfying response times for non-periodic tasks, especially if the periodic traffic is important. That is why periodic task servers are introduced by Lehoczky et al. in [START_REF] Lehoczky | Enhanced aperiodic responsiveness in hard real-time environments[END_REF].

A periodic task server is a periodic task, for which classical response time determination and admission control methods are applicable (with or without modifications). This particular task is in charge of servicing the nonperiodic traffic with a limited capacity.

Several types of task server can be found in the literature. They differ by the way the capacity is managed. We can cite the Polling Server policy (PS), the Deferrable Server policy (DS), the Priority Exchange policy (PE) first described by Lehoczky et al. in [START_REF] Lehoczky | Enhanced aperiodic responsiveness in hard real-time environments[END_REF] and developed in [START_REF] Strosnider | The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments[END_REF][START_REF] Ghazalie | Aperiodic servers in a deadline scheduling environment[END_REF][START_REF] Sprunt | Exploiting unused periodic time for aperiodic service using the extended priority exchange algorithm[END_REF], the Sporadic Server policy (SS) presented in [START_REF] Sprunt | Aperiodic task scheduling for hard real-time systems[END_REF] and the Slack Stealing techniques introduced in [START_REF] Lehoczky | An optimal algorithm for scheduling soft-aperiodic tasks fixed priority preemptive systems[END_REF].

Depending on the server policy, worst-case response time for the aperiodic tasks can or cannot be computed on-line when they occur. We have to separate periodictasks feasibility analysis -an offline process which can give guarantees on periodic-tasks (and servers) executionand aperiodic-tasks feasibility analysis -an on-line process which can give guarantees at run-time on the aperiodic tasks execution.

Polling Server Principles

The PS is activated every period with its full capacity. If there are aperiodic tasks pending, it serves them with respect to its capacity limits and then loses its remaining capacity until its next activation.

Its most significant advantage is that it can be included in the feasibility analysis like any periodic task.

Assuming the server is the highest-priority task in the system, a feasibility test for the aperiodic tasks can be performed on-line. If the server is not the highest priority task, the complexity of the analysis becomes too high to be performed on-line, and since it cannot be performed off-line because of the unpredictability of the arrival model of aperiodics, it cannot be performed at all.

Deferrable Server Principles

The DS is activated as soon as an aperiodic event occurs (if it has enough capacity). It recovers its capacity every period.

The DS algorithm offers better average response-times than the PS, but since it can be activated with a delay, the feasibility analysis for the periodic tasks must be modified, as described in [START_REF] Strosnider | The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments[END_REF][START_REF] Ghazalie | Aperiodic servers in a deadline scheduling environment[END_REF].

As for the PS algorithm, complexity of the feasibility analysis for the aperiodics requires that the server runs at the highest-priority level in the system to guarantee the response times of aperiodics.

An exhaustive state of the art on this topic can be found in [2, chapter 5].

Tasks servers with Java: design

The RTSJ does not support any particular task server policy.

It proposes two classes AsyncEvent and AsyncEventHandler to model respectively an asynchronous event and its handler.

The only way to include the handler in the feasibility process is to treat it as an independent task, and that implies to know at least its worst-case occurring frequency.

The RTSJ also provides the so called "Processing Group Parameters" (PGP), which allow programmer to assign resources to a group of tasks. A PGP object is like a ReleaseParameters which is shared between several tasks. More specifically, PGP has a cost field which defines a time budget for its associated task set. This budget is replenished periodically, since PGP has also a field period.

This mechanism provides a way to set up a task server at a logical level. Unfortunately it does not take into account any server policy. Moreover, as pointed in [START_REF] Burns | Processing group parameters in the real-time specification for java[END_REF], it is far too much permissive and it does not provide appropriate schedulability analysis techniques.

Finally, since cost enforcement is an optional feature for an RTSJ-compliant virtual Java machine, PGP can have no effect at all. This is the case with the Timesys Reference Implementation of the specification (RI).

This is why we propose an RTSJ extension we can use to design and implement event based applications using task servers.

Figure 1. Classes to implement the server policies

Our framework (Task Server Framework) is composed of six new classes:

• ServableAsyncEvent (SAE)
This AsyncEvent (AE) subclass represents a servable event. Like a normal AE, a SAE can be bound to one or several standard handlers (i.e. Async-EventHandler) using the addHandler(Async-EventHandler handler) method. We overload it with the method addHandler(Servable-AsyncEventHandler handler) and we redefine the method fire().

• ServableAsyncEventHandler (SAEH) This class does not extend AsyncEventHandler (AEH), nor implement Schedulable. It embodies the code which can be associated with an SAE. It can be bound with one ore many SAE but associated with a unique TaskServer, and when one of the event it is bound with is released, it is added to the pendingevents list of this server.

• TaskServer This abstract class represents a task server. It implements Schedulable and extends Scheduler. It is a schedulable object since it is in fact a periodic realtime thread and it is a scheduler since it has to schedule SAEHs. It has a method servableEvent-Released() which takes an AEH. This method is called by the AE fire() method.

• PollingTaskServer A subclass of TaskServer which implements the PS policy.

• DeferrableTaskServer A subclass of TaskServer which implements the DS policy.

• TaskServerParameters A subclass of ReleaseParameters to construct a TaskServer.

Figure 1 shows dependencies between classes in the Task Server Framework and standard RTSJ classes.

To summarize the mechanism, when an SAE is fired, the servableEventReleased() methods of the bound servers are called for each of its SAEHs. This allows developers to write different behaviours for different task server policies: the handlers can be scheduled in a FIFO order, or any other desired order, depending on the implemented policy.

This design also allows programmers to use the add-Tofeasibility() methods on a TaskServer since it implements Schedulable. This approach is compliant with the RTSJ general design, but this is not sufficient. In order to provide a consistent design for the response times analysis, each schedulable object should have a getInterference() method, which would be called by the Scheduler feasibility methods. For example, it is still possible to compute response times in a system with a Defferable Server, but the algorithm has to be modified, and this is not possible in the centralysed RTSJ current approach. Anyway, this is not the matter of this paper.

Tasks servers with Java: Polling Server and Deferrable Server policies

The main issues during the conception of a task server are to guarantee the respect of its capacity and to ensure the capacity enforcement behaviour.

For the first problem, we used the Timed class. This class allows us to execute the run() method of an Interruptible object for a given maximum amount of time. If this maximum is reached before the run() method completes, the AsynchrouslyInterrupted-Exception is raised and the interruptAction() method is called.

To control the server capacity, we make the assumption that the server cannot be preempted. Then, we just have to measure the time passed in the run method of the interruptible and decrease the remaining capacity accordingly.

Moreover, we are not able to resume a generic thread (even if it is explicitly interruptible), this is why a handler cannot be executed on multiple instances of the server. The system designer is in charge to split the treatment of each aperiodic event on multiple handlers, each one with a cost less than or equal to the server capacity (in fact less than because of the server's overhead).

So, our implementations of task servers policies are limited with the following constraints:

• the worst case execution time (wcet) of a non-periodic event treatment has to be less or equal to the server capacity;

• the server has to be the highest-priority task in the system.

Polling Servicing

Our class PollingTaskServer encapsulate a RealtimeThread with PeriodicParameters. The run() method of the server is delegated to this periodic real-time thread. When an asynchronous servable event is fired, its handler is added in a FIFO list. At each periodic activation, a method chooseNextEvent() is called. This method returns an SAEH or null if the server is not able to serve any pending event with its remaining capacity. While the chosen event is not null, it is executed (with the method doInterruptible() of Timed), the capacity is decreased and the chooseNextEvent() method is called again.

Figure 2. Scenario 1

This method return the first handler in the list which has a cost lower than the remaining capacity. This implies that if there is two handlers in the list, if the first -corresponding to the event released first -has a cost greater than the remaining capacity and if the second has a cost lesser than the remaining capacity, the event released last is served first. In the following examples, the task set is composed of two real-time periodic tasks, τ 1 and τ 2 , and one polling server P S running at the highest priority. These three periodic threads are synchronously started. There are two SAEHs, h 1 and h 2 , respectively bound to two SAEs e 1 and e 2 . Table 1 shows the properties of these tasks.

Examples

Scenario 1

Look at Figure 2, e 1 and e 2 are fired respectively at time 0 and 6. Since the server has its entire capacity at these two instants, h 1 and h 2 are immediately processed by the server. Look at Figure 3, e 1 and e 2 are fired respectively at time 2 and 4. We can see that h 2 does not begin its execution at time 8 because the remaining capacity of the server is 1, which is less than the cost of h 2 .

With the real PS policy, h 2 should begin its execution at time 8, suspend it at time 9 and resume it at time 12.

Scenario 3

Without changing the code of h 2 , we declare it with a cost of 1. Then, we fire e 1 and e 2 respectively at time 2 and 4. Figure 4 shows that h 2 begins its execution at time 8 because its cost parameter is set to 1, that is the remaining capacity, and is interrupted at time 9 because the server has consumed all its capacity and because h 2 has not finished.

With the real policy, h 2 should resume its execution at time 12, but it is not possible with Java.

Deferrable Server policy

Unlike the PS, the DS can serve an aperiodic task at any time as it has enough capacity. So the run() method can no longer be delegated to a periodic real-time thread. Instead, it is delegated to an AEH bound to a specific AE we call wakeUp. Each time an aperiodic event occurs, if the server is not already running, this event is fired. Moreover, we add a periodic timer which fire wakeUp if the server is not already running.

The second difference between the PS and the DS is that an event can begin its execution at the end of a server instance (for the PS, we made the assumption that the capacity is lesser than the period). So if the remaining capacity of the server is 1 when it has to serve an event with a cost of 2, if the next refill of the capacity is in a time lesser than 1, the event can be served. The chooseNextEvent() method now compare the current date with the next period: if the current date plus the chosen event cost is bigger than the next period of the server, the time budget associated with the event is equal to the remaining capacity plus the total capacity of the server.

Finally, as for the PS, it has to be noted that the implemented policy has not the exact behaviour of the real Deferrable Server described in literature.

RTSS: a real-time systems simulator

We develop a real-time event-based system simulator. This is a Java program which can simulate the execution of a real-time system and display a temporal diagram of the simulated execution. For now, three scheduling policies are implemented: Preemptive Fixed Priority, EDF and D-OVER. This tool is distributed under the General Public Licence GNU (GPL), and can be found on the following web page: http://igm.univ-mlv.fr/~masson/RTSS In order to compare with our task servers executions, we add the polling and the deferrable server policies to RTSS. The simulated policies are the ones described in literature: this is not a simulation of our implementations. Moreover, it does not take into account the servers overhead, nor the execution overhead.

Results

In order to validate our design, we implement the PS and the DS policy in Java and in an event-based simulator. We randomly generate task systems and we compare the simulations of these systems with their executions. The executions was performed using the reference implementation (RI) of the RTSJ on a 2 GHz processor INTEL Pentium 4 machine with 500 MB of memory and a rtlinux-free realtime kernel.

Real-Time Systems Generation

We develop a package fr.umlv.random-Generator with a class randomSystemGenerator which can take the following parameters:

• taskDensity, the average number of aperiodic events per server period,

• averageCost, the average cost of aperiodic events,

• stdDeviation, the standard deviation of the aperiodicevents' costs

• serverCapacity, the server capacity,

• serverPeriod, the server period,

• nbGeneration, the desired number of generated system,

• seed, the random seed, in order to generate the same systems on multiple platforms.

We generate six sets of ten systems. The first set is defined by the tuple [START_REF] Burns | Processing group parameters in the real-time specification for java[END_REF][START_REF] Santos | Cost monitoring and enforcement in the real-time specification for java -a formal evaluation[END_REF]0,[START_REF] Santos | Formal analysis of aperiodic and sporadic real-time threads in the rtsj[END_REF][START_REF]Expert Group. SI 1.4: Supporting Sporadic and Aperiodic Releases in Real-Time Threads[END_REF][START_REF] Sprunt | Aperiodic task scheduling for hard real-time systems[END_REF]1983). This tuple permits to generate ten systems where the average number of aperiodic event per period is one, the costs of the events are three time units (tu) (the average costs are three and the standard deviations are zero), the servers capacities are f our tu and their periods are six tu.

In order to test the scalability of the system, we generate two other sets with the same parameters, except for the average number of aperiodics per instance: we generate one set with an average number of two and one with an average number of three.

Then we re-generate the same three sets but this time with standard deviations on the aperiodic events costs of two.

So we simulate the PS and the DS algorithms on these sixty systems and we execute them with our modified PS and DS implementation. We limit our simulations and executions on ten server periods.

(1, 0) (2, 0) ( We measure the average response time of aperiodics, the interrupted-aperiodics ratio and the served-aperiodics ratio for each execution and simulation. Then we compute for each set the average of the average-responsetimes (AART ), the average of the interrupted-aperiodics ratios (AIR) and the average of the served-aperiodics ratios (ASR).

The AART give us a qualitative metric: the shorter the response times are, the more efficient the policy is. The AIR permit to estimate the overhead of the task server, since an event can be interrupted only if the server has theoretically enough resources to serve the event, but not enough in practice. Moreover, they can be used to adjust the acceptability threshold on the aperiodics' costs. Finally, the ASR are usefull to estimate the efficiency lost between our implementations and the theoritical algorithms of the DS/PS policies.

Polling Server results

Simulations

The measures on our PS simulations can be found on table 2. We can observe that the response times are a little greater when the event costs are not homogeneous. This is partly due to a bad-design issues on our costs generations: if a cost lower than 0.1ms is generated, we set it to 0.1ms. So the average cost has no longer the correct value. Even without this drawback, it can be explained by the fact that the highest cost a task has, the highest are the chances that the the server serve it in more than one instance, increasing its response time because of the server idle times.

Executions

Table 3 presents our Measures on the executions of our PS implementation. We have first to comment the average served ratios. They are lesser than the simulation ones. This is due to our not-resumable thread limitation: even if the server still has capacity, it has to delay the execution of task with a cost greater than its remaining capacity. This impact is reduced in the case of non-homogeneous task sets. Indeed, our server is able to execute a task released later if its cost is lesser than the capacity. For example, if the event queue contains two tasks τ 1 and τ 2 , with c 1 = 3 and c 2 = 1, if the remaining capacity of the server is 2, then τ 2 can be executed instantaneously, even if it has been released after τ 1 . This server optimisation has an another consequence: the response times of events with low cost are improved. In the same time, there is more unserved task during the execution than during the simulation. In addition of the events which cannot be scheduled during the first ten periods of the server, there is the interrupted tasks, i.e. the ones which had overrun their costs due to the server's overhead. These interrupted tasks are mostly the ones with greater costs. These two facts lead to a far better average response time of served events in the execution than in the simulation. The lesser the costs are, the better the response times will be, as the chances to be not interrupted.

(1, 0) (2, 0) (3,
It has to be noted that the average interrupt ratio is very low for the homogeneous task sets. This is due to a simple fact: the server can only serve one event per period, since its capacity is 4 and the costs of the event are all 3. So each task has an additional time budget of 1s before being interrupted.

Deferrable Server

Simulations

Our simulations measures on the DS are presented on table 4. We can make the same observation than for the PS: the response times are a bit greater with the non homogeneous task set than with the homogeneous ones. Reasons are the same as in the previous case, increased because the deferrable server has a served ratio more important than the polling. This is due to its ability to serve each event as soon as it is released: the average response times are better than the polling ones and the events released during its tenth period can be served if there is no other pending events.

(1, 0) (2, 0) (

Executions

Finally, the measures on the executions of our DS implementation can be found on table 5. Due to the ability of the server to serve the lower cost events in advance if their capacity is reduced and due to the lower served ratio, the response times of the execution are lower than the ones of the simulation for the non homogeneous task sets. We can note that the served ratios are very close to the simulations ones, that validates our implementations of task servers. We have to keep in mind that the simulations does not take into account the execution overhead.

Future Works and Improvements

The performance of our implementations can be improved. First, we have to reduce the average interruptedaperiodics ratio (AIR). An interruption can have two different reasons: the task overruns its worst case execution time (WCET) -we cannot do anything -or the remaining capacity is too close to the cost of the event. Indeed, even if the server has to be the highest priority task in the system, there is also more highest priority tasks: the timers charged to fire the asynchronous events. We could decide that these timers have lower priority, but, in the case of the PS, this means that their executions will also be delayed until the next server period. Moreover, we could no longer measure the response times of the events. That is why we had not done it.

We can avoid some interruptions in delaying the execution of events handlers with a cost too close of the remaining capacity.

The over point we want to address is the on-line computation of event response times. Since the servers have to execute at the highest priority, a response time computation can reasonably be performed on-line at the arrival time of the event.

With the PS standard algorithm, assuming that the tasks are served in ascending deadline order and that the PS is running at the highest priority, the response time R a of a task J a -which is released at time r a -can be computed on-line (at time r a ) with the following equations:

Ra = ( t + Cape(t, d k i) -ra if Cape(t, d k ) ≤ cs(t) (F k + G k )Ts + R k -ra else.
(1)

F k = - Cape(t, d k ) -cs(t) Cs (2)
G k = ‰ t Ts ı (3) R k = Cape(t, d k ) -cs(t) -F k Cs (4)
where C ape (t, d k ) is the sum of the costs of the tasks with a deadline smaller than J k , F k the number of server instances needed to serve C ape (t, d k ), G k the instance which begins to serve C ape (t, d k ) and R k the time needed in the last instance to finish to serve C ape (t, d k ).

But our implementation suffers of some limitations: since a Java thread, even real-time, is not resumable, our PS only begins to serve a task if it has enough capacity to finish to serve it.

Taking into account these limitations, we can formulate the response time R a of an aperiodic event J a released at time r a as:

R a = (I a T s + C pa + C a ) -r a (5)
where I a is the instance of the server where J a handler will be execute in, C pa the cumulative cost of the previous handlers scheduled in the same instance and C a the cost of J a .

To easily compute J a and C pa , we propose a minor modification on our task servers implementations. Instead of put the events handlers in a simple FIFO list, we can set up a structure with a list of lists of handlers. Each list only contains a number of handlers which can be served in one single instance of the server. In addition, we can maintain another list of RelativeTimes which represents the cumulative costs of each handlers list. Now, I a can be compute with the position in the list of lists of handlers where J a has been added and C pa is the corresponding cost in the list of costs. Of course, this proposition will increase the time requested to register the release of a servable asynchronous event, but permits to compute in a constant time the response time of the event, and possibly to cancel its execution.

Related Works

The RTSJ is still subject to a lot of research, on the specification itself (JSR-282) as well as on specific extensions like the Distributed Real-time Specification (JSR-50) and the Safety Critical Java Technology (JSR-302). We can cite a recent publication of the JSR 282 in which the addition of several methods in the RealtimeThread class is suggested [START_REF]Expert Group. SI 1.4: Supporting Sporadic and Aperiodic Releases in Real-Time Threads[END_REF]. Other authors propose the use of model checking technics in order to highlight some issues in the RTSJ cost monitoring and enforcement model [START_REF] Santos | Cost monitoring and enforcement in the real-time specification for java -a formal evaluation[END_REF] and to analyse the behaviour for non-periodic real-time threads in the RTSJ [START_REF] Santos | Formal analysis of aperiodic and sporadic real-time threads in the rtsj[END_REF]. In this paper, we have described the limitations of the RTSJ in regard to the support for aperiodic tasks.

Conclusions

The RTSJ does not support any aperiodic-task server mechanism. In this paper, we have proposed a framework to fill in this lack. In order to illustrate the use of this framework, we have adapted two task server policies: the Polling Server and the Deferrable Server ones. To validate our implementations, we also have implemented a simulator and a real-time system generator. We have compared the executions of 6 sets of 10 real-time systems with their simulations. We have observed better response times in our executions with served ratios very close to the ones from the simulations. There is still an important interrupted task ratio, but we have presented its causes and proposed a solution which we still have to test. Moreover, the simulations do not take into account the server overhead nor the costs of the events' release.

Finally, we have showed that we can easily implement a feasibility test at run-time for the aperiodic events, with a constant complexity. The implementation of this test, its integration in the RTSJ design and its confrontation with the response-times measured during the executions will make the object of our future works on this topic.

Figure 3

 3 Figure 3. Scenario 2

Figure 4 .

 4 Figure 4. Scenario 3

Table 1 . Tasks' Properties

 1

		Priority Cost / capacity Period
	P S	High	3	6
	τ 1	Medium	2	6
	τ 2	Low	1	6
	h 1		2
	h 2		2

Table 2 . Measures on Polling Server simula- tions

 2

				3, 0)
	AART 8.86 17.52 23.76
	AIR	0.00	0.00	0.00
	ASR	0.89	0.63	0.43
		(1, 2) (2, 2) (3, 2)
	AART 10.24 20.58 25.50
	AIR	0.00	0.00	0.00
	ASR	0.85	0.50	0.35

Table 3 . Measures on Polling Server execu- tions

 3

	0)

Table 4 . Measures on Deferrable Server sim- ulations

 4

				3, 0)
	AART 5.30 13.44 19.83
	AIR	0.00	0.00	0.00
	ASR	0.94	0.67	0.46
		(1, 2) (2, 2) (3, 2)
	AART 6.36 17.40 21.71
	AIR	0.00	0.00	0.00
	ASR	0.94	0.56	0.38
		(1, 0) (2, 0) (3, 0)
	AART 6.90 14.55 20.58
	AIR	0.00	0.00	0.00
	ASR	0.84	0.56	0.39
		(1, 2) (2, 2) (3, 2)
	AART 8.02 13.47 16.91
	AIR	0.14	0.26	0.27
	ASR	0.66	0.43	0.30

Table 5 . Measures on Deferrable Server exe- cutions

 5


Abderrezak Rachedi
email: rachedi@univ-mlv.fr

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

Sylvain Cherrier
email: cherrier@univ-mlv.fr

Ismail Salhi
email: salhi@univ-mlv.fr

Wireless Network Simulators Relevance Compared to a Real Testbed in Outdoor and Indoor Environments

Keywords: Wireless Networks, 802.11, Network Simulators, Testbed, Propagation Models I

In this paper, we propose a comparative study between results generated by a real 802.11 testbed in different outdoor and indoor environments and 3 usual network simulators (NS2, QualNet and OPNET). The goal of this study is to evaluate the relevance of the low layers recently implemented in these simulators. The motivation of this paper is to provide a guide to researchers to choose and parameterize a simulator according to a selected context. The study shows that the simulation results can be rather close to the experimental results. However, they are very dependent on the tuning of the physical layer parameters and the selected propagation models.

INTRODUCTION

The design and the implementation of new protocols or models for wireless multi-hop networks such as MANET or WSNs are mainly based on simulation in order to test and validate the proposed solutions. The main reasons are the cost and the complexity of a real implementation in a testbed, especially when the network is dense and the scaling factor has to be tested. In all cases, the simulations allow a fast performance comparison between different protocols/models with different scenarios and for many times. However, in the real world tests (testbeds) and particularly in the wireless communication case, the impact of some parameters such as: the type of environment (indoor/outdoor), the terminal location and movement are very important and can influence the performance evaluation of protocols or models. In order to determine the relevance of the wireless network simulators, we have to answer both following questions: 1) Does the implementation of the lower layers (particularly the physical layer) in the network simulators reflect the reality? In other words, does it give results close to the reality? 2) if the implementation does not reflect the reality, what is the relevance of the obtained results in the case of a dense multihop network, knowing that the transmission model between two nodes is not realistic? Thus, our motivation for this work is based on three aspects: the first is related to the important number of researchers who use the simulator networks to validate their solutions. For example, according to Kurkowski et al. study, more than 75.5% of the published papers for MobiHoc symposium used simulation to validate the proposed solutions [START_REF] Kurkowski | Manet simulation studies: the incredibles[END_REF]. The second aspect is related to the existence of significant divergences in the obtained simulation results based on several popular simulators such as OPNET [START_REF][END_REF], NS-2 [START_REF]The Network Simulator NS-2[END_REF] and GloMoSim [START_REF] Bajaj | GloMoSim: A Scalable Network Simulation Environment[END_REF]. These divergences are illustrated by Cavin et al. [START_REF] Cavin | On the Accuracy of MANETs Simulators[END_REF] study. The third and final aspect of our motivation is to give an explanation of these differences between simulation results by using and comparing them to a real testbed. Finally, the two main contributions of this paper are: 1) highlight the differences at the lower layers between the simulators and reality; 2) point out the sensitive parameters and models which can influence the simulation results and lead to an important difference between the simulation and the testbed results. In order to achieve these goals, we choose two scenarios (indoor and outdoor) with a focus on the transmission between two nodes and three major network simulators: NS2, OPNET and QualNet. This paper is organized as follows: in section 2, we present the summarization of the existing works related to network simulators and the experimentation results. Section 3 presents the selected scenarios and the results for the testbed. The fourth section is dedicated to the results obtained with the simulators and their analysis, compared to the testbed. Finally, section 5 concludes the paper and presents our future works.

II. RELATED WORK

In literature many works deal with the comparison between different network simulators. For instance, the accuracy study of different MANETs simulators (OPNET, NS2, GloMoSim) is presented by Cavin et al. [START_REF] Cavin | On the accuracy of MANET simulators[END_REF]. The obtained results from the three network simulators illustrate the significant divergences which are due to the mismatching of the modelling of each simulator. However, no comparison with real wireless network testbed is presented. Another study presented by Kargl and Schoch [START_REF] Kargl | Simulation of MANETs: a qualitative comparison between JiST/SWANS and ns-2[END_REF] consists in comparing network simulators JiST/SWANS and NS2. This study shows that NS2 needs a more important memory compared to SWANS (NS2 consumes 300MB with the scenario of 150 nodes, but SWANS does not require more than 10MB). Therefore, the results divergences between different network simulators lead us to compare network simulators in terms of accuracy with the testbed as reference. That's why Lucio et al. [START_REF] Lucio | OPNET Modeler and ns-2 -Comparing the accuracy of network simulators for packet-level analysis using a network testbed[END_REF] proposed a comparison study between the simulators NS2 and OPNET and the testbed of wired networks. The goal of this study is to present the simulator which gives the result closest to reality under the given conditions. In the case of the CBR traffic, Ns2 gives more accurate results than OPNET Modeler and in the case of FTP traffic OPNET performed more closely to the testbed results. This study is limited to wired networks. In other works, the goal is to validate into simulators the implementation of MAC layer protocols such as IEEE802.11g and IEEE802.11e. For example, the study presented by Bredel and Bergner [START_REF] Bredel | On The Accuracy of IEEE 802.11g Wireless LAN Simulations Using OMNeT++[END_REF] consists in implementing the IEEE802.11g under OMNET++ simulator. The conclusion of this study is that OMENT++ performs quite well in the case of long observation times compared to the testbed results. However, they assume that the physical medium is free of interference from external sources and the fading effects are negligible. Furthermore, the indoor environment is not taken into account which makes the comparison not close to the reality. Garrido et al. [START_REF] Garrido | ns-2 vs. OPNET: a comparative study of the IEEE 802.11e technology on MANET environments[END_REF] have proposed a comparative implementation of the IEEE 802.11e technology with both simulators NS2 and OPNET. The obtained results point out some important differences between both simulators. However, the testbed is not taken into account. Other studies focus on the indoor environment, particularly the propagation models used by the simulators in order to justify the divergences between the different simulator networks. Stepanov et al. [START_REF] Stepanov | On the Impact Propagation Models on MANETs Simulation Results[END_REF] propose to integrate a more accurate radio propagation model into the simulation tool. The proposed model is based on ray tracing and considers geographic data of the simulation area. In order to test this propagation model, they used a commercial implementation of the intelligent ray tracing model called WinROP [7]. The drawbacks of this work are: first, no experimentation or testbed is done to compare with the simulation results. Secondly, the data set generated for the propagation model is from WinPROP which is a commercial tool. Another factor affecting the accuracy of the simulation results is the background noise. The noise models implemented in the network simulators such as: NS2, OPNET and Glomosim are too simplistic and do not reflect the real network conditions. That's why Su and Boppana [START_REF] Su | On the impact of noise on mobile ad hoc networks[END_REF] proposed the measurement of background noise for MANET using a testbed and they illustrate the potential noise modelling by using the generalized extended value (GEV) and the discrete-time Markov chain. However, no impact evaluation of the proposed noise model is presented. In addition, no new or more realistic propagation model is presented. Unlike the existing works, in this paper we focus on the two main environments (outdoor and indoor) and we present and compare the obtained results from three major network simulators (NS2, OPNET, QualNet), without modifying them, with testbed results. The added value of our study is to present and analyse the simulation results and the testbed results in order to point out the divergence between them and the causes of these divergences.

III. TESTBED

A. Context

The environment has an important impact on the wireless communications. Indoor environment is more spread in reality, for example using wireless access in companies, offices, airports, and hotspots. Outdoor environment represents the free space area without physical obstacle like for an emergency deployment in a rural environment what is much less frequent. Let us note that a lot of performance simulation studies on dense wireless networks use the free space model which is not very realistic. For this study the indoor environment is our lab, made up of 15-30m 2 offices distributed along a 50m corridor. This is a usual office context. Like for access point deployment, the nodes are located in the corridor to take into account the fading effects. Other transmissions in the band of 2.4 GHz exist in this area and in the vicinity but we selected a free channel. For the outdoor (free space) environment, we chose a park near our university without obstacles. For both contexts, we have selected a simple point-to-point scenario with one communication flow (UDP or TCP) and different distances between the sender and the receiver. We used 4 laptops with Netperf [START_REF]NetPerf tool[END_REF] and MGEN [START_REF]MGEN: The Multi-Generator Toolset[END_REF] as network traffics generator. The embedded wireless devices use the IEEE 802.11g standard which is currently widespread. With this technology, the transmission range in experimentation is limited to almost 35m. That is why we varied the distance between the sender and the receiver from 5 to 40 meters and we estimated the results for each distance. The selected metrics for this study are the throughput and the signal level in order to evaluate the performance of the transmission and the quality of the channel.

B. Results

Figure 1 illustrates the average values of the received signal level (in dBm) and the throughput measured at the receiver according to the different distances between the sender and the receiver nodes in the case of a TCP flow. Measurements were made in both indoor and outdoor environments with our testbed. In the case of outdoor results and according to the mathematic formulation of free space environment, the signal level should decrease with distance square. The measured signal level is more versatile than expected. It depends on many parameters such as: the characteristics and the orientation of the antennas, the reflexions on the floor, the possible background noise etc. In the case of indoor environment, we expected an important variability of the signal level. Our testbed is located in the corridor of our laboratory and both nodes are in line of sight, but as in every real place, people are moving in the area. The measurements show that the signal level is quite close to the one obtained in outdoor. As the selected channel is free, the transmissions in the vicinity do not cause interferences being able to disturb the signal significantly. We even obtain slightly better values (+8 dBm) probably due to the close reflections on the walls (corridor effect). What is the impact of that signal level's variation on the throughput? As we can see in figure 1, for short distances, the throughput remains constant (real throughput between 14 and 18Mb/s corresponding to a 54Mb/s Data Rate) even if the signal level decreases. Then, for a distance greater than 25m, the throughput decreases quickly. We can deduce that the ARF (Auto Rate Fallback) procedure is effective in this case: the 802.11 device tries to maintain a high data rate (54 Mb/s) until a power threshold is reached (approximately -70dBm). Let us remind that we represent the average values of the signal level and the throughput measured at a certain distance: for 30m, the level or the throughput can be maximum or null at certain times. For the second measurement, we use a CBR/UDP source instead of a FTP/TCP source in order to observe the behavior of our connection when the flow increases linearly in an indoor environment. Figure 2 illustrates the average throughput when the rate of the CBR source varies and for different distances between the sender and the receiver. After estimating the throughput with NetPerf and MGEN, we started a sequence of transmissions with the rate of the CBR flow varying from 1Mb/s to 30Mb/s. The throughput is quite stable for a CBR source lower than 13Mb/s. For higher rates, the throughput is highly variable, not only depending on the CBR source. Once again, the 802.11 device tries to preserve a maximum Data Rate but this one is reduced as soon as the signal decreases. This trend is not predictable. However the amplitude of throughput variations remains related to the distance. The green curve shows the throughput variation when we are near the edge of range (35m). In that case, the throughput depends more on the signal level which is near the threshold (-70dBm) than on the CBR source rate.

IV. SIMULATORS

A. NS-2 [4]

NS-2 is currently the most popular network simulator: more than 43% of researchers have been using NS-2 to evaluate their proposed solution [START_REF] Kurkowski | Manet simulation studies: the incredibles[END_REF]. We adapted the rate of the existing IEEE802.11 MAC layer to support the IEEE802.11g current standard. However, a real PHY layer with OFDM multiplexing is not implemented. We used the FreeSpace and TwoRayGround propagation models to simulate the Outdoor environment and the Shadowing model with different parameters to simulate the Indoor environment. To be close to the real testbed, neither background noise nor interference in the same channel is simulated in the vicinity of both nodes. For the Free Space model, the power attenuation of the signals is proportional to 1/d 2 :

ܲ ൌ ܲ ௧ ܩ ௧ ܩ ߣ ଶ ሺ4ߨ݀ሻ ଶ ܮ
G t and G r are the antennas gains, λ the wavelength and L the Loss Factor. We choose 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 field measurement. For example, β=2 corresponds to free space propagation. When we set a larger value of β that means that the number of obstructions is more important 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 and reflects the variation of the received power at certain distance.

X dB is thus a Gaussian random variable with zero mean and 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. The simulation parameters are resumed in table 1. The results are plotted in figure 3. First, we notice that for short distances, the throughput obtained by simulation is always higher, whatever the model is. This is mainly due to the lack of a specific 802.11g physical layer. The Free Space and the Two Ray Ground models give the same results which are not representative. The ARF procedure is not implemented in NS-2 and for these simplistic models, the propagation is maximum or null beyond a certain distance.

The shadowing model offers results closer to reality but the parameters that drive shadowing propagation are difficult to set. The documentation of NS-2 gives typical values of β and σ (for example: β=2 and σ=4dB to 12 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 adjust the parameters to obtain a curve close to reality (indoor or outdoor) but these adjustments cannot be generalized. In figure 3, for β=1.8 and σ=3.5, the throughput presents the same decrease as for the testbed in outdoor. However, according to the model, these parameters correspond to an "in building, line-of-sight" environment. Moreover, a wrong tuning can lead to false results (see yellow curve in figure 3). B. QualNet [START_REF] Qualnet | [END_REF] In order to perform an efficient and fair comparison between the simulators, we used the same parameters as in NS-2, whether for the PHY or MAC layer as summarized in table 1.

Let us note that the implementation of the PHY layer is not complete for the IEEE 802.11g standard. Nevertheless, Qualnet is the only simulator offering the possibility of using the ARF procedure. The proposed propagation models are closed to those proposed in NS-2: free space, two ray ground and log-normal shadowing (in this only the deviation parameter is used). Qualnet also proposes Rayleigh fading model, which occurs when there is no line of sight between the source and destination. Note that Qualnet proposes additional propagation models for different outdoor configurations, like the irregular terrain model, the urban model, the Walfish-Ikegami model, suburban and other terrain feature formats such as Geographic Information System (GIS) and Compact Terrain DataBase (CTDB). As for OPNET, these models are specifics to large outdoor environment and give results very close to the free space or two ray ground models. Figure 4 shows the results of the Qualnet simulations. The first observation concerns the average values of the throughputs which are close to those obtained in the testbed (indoor and outdoor), comparing to NS-2 and Opnet. We can also see that the ARF enhances considerably the accuracy of the results. As for NS-2, the shadowing model gives the best results for the indoor environment. Here also, the shadowing deviation is adjusted to obtain a curve close to reality (σ=4dB) and the adjustment is much more precise and effective than for NS.

In the Rayleigh fading model, with a velocity parameter of 1m/s (pedestrian moving), the decreasing is quite linear and does not correspond to the selected real environment. In addition, OPNET uses a fixed value of the pathloss exponent without considering the diversity of the environments. Like for NS-2 and Qualnet the transmitted power is adjusted in the free space model to obtain a 40m reception range. The other parameters are the same (see table 1). The results for the free space model are plotted in figure 5.

With the same power value, the other propagation models give very nearby results and are thus not represented. They are indeed designed for outdoor environment and thus for transmission powers much higher than those usually used in IEEE 802.11 (greater than 100mW) and for antennas with a range much higher than those present in the laptops (greater than 100m). For example, Hata is a widely used propagation model suitable for predicting RF path loss in an urban environment. This model has a parameter, which specifies the relative size and distribution of buildings (large city, small city, suburban, and open areas) and antenna heights are chosen starting from the selected size.

As conclusion, although OPNET integrates 802.11g device and a lot of possible adjustments (noise, loss factor, antenna models…), the propagation models proposed by default do not make it possible to carry out simulations close to reality for short distances, particularly in an indoor environment. It is necessary in this case to add other propagation models like the shadowing type. Figure 5 illustrates the obtained results from NS2, OPNET, QualNet simulators and the testbed. We remark that the simulation with ARF (QualNet) and shadowing model consideration (NS2 and QualNet) are close to testbed results in both cases indoor and outdoor environments. However, the parameter setting of this model is empirical and cannot be applied to other contexts.

V. CONCLUSION

In this work, we present a comparative study between results obtained from a real testbed and three usual network simulators (NS-2, Qualnet and OPNET). The main goal of this study is to evaluate the relevance of these simulators in indoor and outdoor environments. According to this study, we can point out that for the simulators, the choice of the PHY layer characteristics is predominant, particularly the propagation model and the associated parameters. The ARF procedure is only implemented in Qualnet which has also a very important role in the networks where the received power is variable according to the distance and the obstacles.

Concerning the dense multi-hop networks, the use in simulations of the free space or two ray ground models is not adapted to indoor contexts (majority of the cases in the WiFi deployment). However, we can use them only to validate routing algorithms without taking into account QoS or other parameters from the low layers.

In the future works, we plan to improve the lower layers of the network simulators in order to generate results which are closer to reality. To achieve this goal, we have to introduce ARF procedure and other propagation models with explicit parameters in order to reproduce a particular indoor environment.

Figure 1 .

 1 Figure 1. Average Signal Level and Throughput / Distance (testbed)

Figure 2 .

 2 Figure 2. Average Throughput / CBR sources Rate (testbed)

Figure 3 .

 3 Figure 3. Average Throughput / Distance (Testbed compared to NS-2)

Figure 4 .

 4 Figure 4. Average Throughput / Distance (Testbed compared to Qualnet)C. OPNET OPNET Modeler is a network simulator well known in industry. The wireless suite of OPNET integrates 802.11g 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. Like for NS-2 and Qualnet the transmitted power is adjusted in the free space model to obtain a 40m reception range. The other parameters are the same (see table1). The results for the free space model are plotted in figure5. With the same power value, the other propagation models give very nearby results and are thus not represented. They are indeed designed for outdoor environment and thus for transmission powers much higher than those usually used in IEEE 802.11 (greater than 100mW) and for antennas with a range much higher than those present in the laptops (greater than 100m). For example, Hata is a widely used propagation model suitable for predicting RF path loss in an urban environment. This model has a parameter, which specifies the

Figure 5 .

 5 Figure 5. Average Throughput / Distance (Testbed compared to Simulators)

TABLE 1 :

 1 SIMULATION PARAMETERS

	Physical Channel	Extended Rate -802.11g
	Data Rate	54Mbps
	Reception range (Capture Threshold)	40m
	Detection range (Carrier Sense Threshold)	80m
	UDP packet size (CBR sources with max. rate)	1000Bytes