Ben Elyes

Guillaume Hamida
email: guillaume.chelius@inria.fr

Jean Marie Chelius

Gorce

Impact of the Physical Layer Modeling on the Accuracy and Scalability of Wireless Network Simulation

Keywords: wireless network simulation, simulation scalability, accuracy, simulation environment, physical layer modeling, interference modeling

Recent years have witnessed a tremendous growth of research in the field of wireless systems and networking protocols. Consequently, simulation has appeared as the most convenient approach for the performance evaluation of such systems and several wireless network simulators have been proposed in the last years. However, the complexity of the wireless physical layer (PHY) induces a clear tradeoff between the accuracy and the scalability of simulators. Thereby, the accuracy of the simulation results varies drastically from one simulator to another. In this paper, we focus on this tradeoff and we investigate the impact of the physical layer modeling accuracy on both the computational cost and the confidence in simulations. We first provide a detailed discussion on physical layer issues, including the radio range, link and interference modeling, and we investigate how they have been handled in existing popular simulators. We then introduce a flexible and modular new wireless network simulator, called WSNet. Using this simulator, we analyze the influence of the PHY modeling on the performance and the accuracy of simulations. The results show that the PHY modeling, and in particular interference modeling, can significatively impact the behavior of the evaluated protocols at the expense of an increased computational overhead. Moreover, we show that the use of realistic propagation models can improve the simulation accuracy without inducing a severe degradation of scalability.

INTRODUCTION

In wireless multi-hop networks (i.e., ad hoc, sensor and mesh networks), there is a growing need for the performance evaluation of protocols and distributed applications. Three main methodologies are generally adopted to investigate the performance and the behavior of networking protocols: theoretical analysis, experimentation and simulation.

Due to the high complexity of wireless communications, analytical studies are often based on unrealistic assumptions and inaccurate physical layer, e.g., the socalled Unit Disk Graph model that has been widely used to model the radio range of wireless nodes [START_REF] Dousse | Connectivity in ad-hoc and hybrid networks[END_REF]- [START_REF] Frey | On delivery guarantees of face and combined greedy-face routing in ad hoc and sensor networks[END_REF]. Moreover, analytical studies usually focus on a given layer ignoring the impact of the other network and physical layers. The experimentation approach may provide valuable insight into the performance and the behavior of wireless systems. However, setting-up testbeds is a tedious and expensive task. For these reasons, simulations are generally considered as the most convenient methodology to explore the behavior of protocols and distributed applications. Nonetheless, the complexity of the physical phenomena constituting the radio medium introduces a tradeoff between accuracy and computational cost in wireless network simulation.

Several wireless network simulators have been proposed in the last years. Examples are NS-2 [START_REF]The network simulator[END_REF], Glo-MoSim [START_REF] Bajaj | Simulation of large-scale heterogeneous communication systems[END_REF], JiST/SWANS [START_REF] Barr | Scalable Wireless Ad hoc Network Simulation. Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless, and Peer-to-Peer Networks[END_REF], GTSNetS [START_REF] Ould-Ahmed-Vall | Simulation of large-scale sensor networks using gtsnets[END_REF], etc. They all provide an advanced and complete simulation environment to investigate and evaluate networking protocols and wireless systems. However, the complexity of the wireless physical layer (PHY) enforces the use of simplified models and unrealistic assumptions for the design of simulators. As a consequence, the retained tradeoff between accuracy and computational load varies drastically from one simulator to another. As it has been highlighted in previous publications [START_REF] Cavin | On the accuracy of manet simulators[END_REF]- [START_REF] Heidemann | Effects of detail in wireless network simulation[END_REF], these variations largely impact on the results of a simulation, and the obtained simulation results may significantly diverge from experimental results [START_REF] Newport | Experimental evaluation of wireless simulation assumptions[END_REF]. A correct modeling of the PHY layer is then crucial for confidence in the simulation results. Nonetheless, most of wireless network simulators are still based on inaccurate and heterogeneous PHY models [START_REF] Takai | Effects of wireless physical layer modeling in mobile ad hoc networks[END_REF]. The reason that generally prevails to justify this low-accuracy is scalability.

In this paper, we focus on the physical layer modeling issue and we investigate its impact on the accuracy and the complexity of wireless network simulations. The question we raise is what is the real cost of PHY simulation accuracy ? We deliberately keep aside optimizations and scalability of the node and protocol aspects of simulations which have been the subject of other studies [START_REF]Simulation scalability issues in wireless sensor networks[END_REF].

To evaluate the PHY tradeoff, we introduce a flexible and modular simulation framework, called WSNet [START_REF]The wsnet wireless network simulator[END_REF]. We dropped the idea of using existing simulators for such a study as none of them offer a sufficient diversity in PHY models. Comparing several existing simulators would not have helped, as they differ in many other aspects than PHY modeling. We thus use WSNet to better understand the impact of the PHY layer on the obtained simulation results.

The remainder of this paper is organized as follows. In Section 2, we review the related works. In Section 3, we discuss the main aspects of wireless communications. Then, in Section 4, we review some common wireless network simulators and compare their PHY modeling. Next, the WSNet simulation framework is presented in Section 5. In Section 6 we investigate the impact of the PHY modeling on the simulation speedup, and in Section 7 we analyze the limited interference model. Finally, the tradeoff involving accuracy and complexity is illustrated in Section 8.

BACKGROUND

Wireless network simulators. Numerous wireless network simulators have been developed and are concurrently used in the academic research world.

• The NS-2 [START_REF]The network simulator[END_REF] network simulator is one of the most popular environment for wired and wireless network simulations. NS-2 is developed in C++ and uses OTcl for scripting and configuration. However it suffers from a limited scalability though some recent optimizations have been proposed to support simulations of a few thousand nodes [START_REF] Naoumov | Simulation of large ad hoc networks[END_REF].

• GloMoSim [START_REF] Bajaj | Simulation of large-scale heterogeneous communication systems[END_REF] is a simulation environment based on a C-derived language, called Parsec, which supports the sequential and parallel execution of discrete-event simulations. Thanks to parallelization, GloMoSim was shown to scale up to 10, 000 nodes [START_REF] Bagrodia | A modular and scalable simulation tool for large wireless networks[END_REF]. • The JiST/SWANS [START_REF] Barr | Scalable Wireless Ad hoc Network Simulation. Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless, and Peer-to-Peer Networks[END_REF] is a java-based discrete event simulation for wireless networks. It was shown that JiST/SWANS outperforms NS-2 and GloMoSim in terms of scalability and memory usage [START_REF] Barr | Scalable Wireless Ad hoc Network Simulation. Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless, and Peer-to-Peer Networks[END_REF].

• The Georgia Tech Network Simulator, GTSNeTS [START_REF] Ould-Ahmed-Vall | Simulation of large-scale sensor networks using gtsnets[END_REF], is a C++ object-oriented simulation environment dedicated to the simulation of wireless sensor networks. GTSNeTS claims to scale to networks of several hundred thousands of nodes [START_REF] Ould-Ahmed-Vall | Largescale sensor networks simulation with gtsnets[END_REF]. This review is far from being exhaustive and other available simulators with wireless support are OPNET, OMNeT++, J-Sim, QualNet, etc.

Accuracy and complexity in wireless network simulations. The literature provides a lot of papers analyzing the accuracy and the complexity of wireless network simulations.

In [START_REF] Cavin | On the accuracy of manet simulators[END_REF], the authors investigate the accuracy of three popular simulators (NS2, GloMoSim and OPNET). They show a significant divergence in the obtained results between the simulators while simulating a basic flooding algorithm. The major reason for this issue is the PHY layer modeling which is implemented differently from one simulator to another. Indeed, in [START_REF] Takai | Effects of wireless physical layer modeling in mobile ad hoc networks[END_REF], the physical layer models of these three simulators is presented in detail, and the authors discuss some PHY layer factors which are relevant to the performance evaluation of protocols. In [START_REF] Newport | Experimental evaluation of wireless simulation assumptions[END_REF], the authors review some assumptions used in many wireless networking studies by comparing simulation results and measurements taken from real experiments. They show the weakness of these assumptions and describe their impact on the accuracy of the simulation results.

Regarding the performance and the complexity of simulations, [START_REF] Heidemann | Effects of detail in wireless network simulation[END_REF] discuss the effects of details in wireless simulation. The authors show how the evaluated performance of protocols can vary when the level of details is tuned. Such details are the energy consumption model, the radio propagation model, the MAC protocol, etc. They suggest to adapt the level of details required by a given case study. In [START_REF] Lee | Efficient simulation of wireless networks using lazy mac state update[END_REF], the authors describe a new method called LAMP (LAzy MAC state uPdate) whose aim is to reduce the overhead introduced by the MAC layer with no loss of accuracy. The idea is to increase the scalability of simulators particularly when simulating large scale networks. Still considering the scalability issue, [START_REF]Simulation scalability issues in wireless sensor networks[END_REF] discusses several aspects impacting the scalability of simulations, including the radio channel, the environment modeling, the energy model, etc.

Contribution. Our contribution is twofold. First, we provide an in-depth analysis of the physical layer modeling issue. We describe analytical models used to model the radio range, the radio link and the interference. We then introduce a new simulation environment called WSNet which provides a large diversity in PHY models. Second, using WSNet we investigate the impact of the physical layer modeling on the accuracy, the complexity and the performance of wireless network simulations.

PHY-LAYER MODELING TRENDS

For the sake of realism and confidence in simulation results, an accurate PHY modeling is a key point. In analytical studies as in simulations, the disk model, shown in Figure 1-(a), has long prevailed. It relies on a set of strong assumptions: time stationarity :

l ij (t) = l ij (1)
independence :

l ij = f (x i , x j ) (2)
switched link (on/off) :

l ij ∈ {0, 1} (3)
symmetry :

l ij = l ji (4)
isotropy :

l ij = f (x i , d ij ) (5)
homogeneity :

l ij = f (d ij ) (6)
where l ij refers to the radio link between nodes i and j and d ij to the geometric distance between i and j.

The disk model provides the radio network with three axioms: the radio range is constant, the radio link is switched, and the network is interference free. The asset of this model holds in its simplicity for both theoretical studies and simulations but in turn suffers from a lack of realism. Nonetheless, improving this model is not a trivial task as a hard tradeoff between complexity and realism holds. Basically, this model can be improved by relaxing either of the three previously stated axioms, as discussed below.

Radio range modeling

The range of a radio system is based upon the definition of a signal to noise ratio (SNR) threshold denoted γlim . If the system is interference free, the range is a constant and the radio link is defined by:

l ij : Ω 2 → B = {0, 1} (x i , x j ) → l(x i , x j ) = 1 if γij ≥ γlim 0 else (7)
where the SNR γij is given by: γij = h ij • Pi Nj , where h ij is the path-loss and P i and N j are the transmission power and the noise level respectively.

The transceiver properties. They are the transmission power P i , the noise level N i , the antenna gain and its radiation pattern g i (θ, φ). Variations of P i , N i or antenna gains affect the spatial homogeneity assumption (and so far the symmetry), which means that all nodes not further have the same range. Note that a non-uniform noise level N j is highly probable for low cost small radio systems. The isotropy which is not statistically affected by these parameters does not further hold if the radiation patterns of the antennas are introduced according to:

h ij = g(x i , x j ) • g i (θ ij , φ ij ) • g j (θ ji , φ ji )
where g(x i , x j ) is the propagation path-loss (see Figure 1-(b)). It should be noted that the use of 3D radiation patterns and a 3D spatial distribution of radio nodes may be pertinent in some cases, in small indoor environments for example.

Propagation models. The simplest model refers to the line of sight (LOS) scenario but in urban and indoor environments, more complicated scenarios occur due to shadowing and multiple paths. Two complementary approaches can be used to deal with propagation.

The former approach relies on a deterministic modeling of the wave propagation and provides fine simulations of any environment. The most usual algorithms are ray-tracing based [START_REF] Almers | Survey of channel and radio propagation models for wirelessmimo systems[END_REF] but discrete methods have also been proposed [START_REF] Gorce | A deterministic approach for fast simulations of indoor radio wave propagation[END_REF]. The high accuracy of these methods is definitely balanced by their high computational cost. Another limitation of purely deterministic models is that simulating one real environment is often too specific. Thus, the latter approach relies on a statistical description complementing the deterministic model. A stochastic variable s ij is then introduced in the propagation pathloss to handle shadowing:

g ij = g ij • s ij
The most usual model is the log-normal shadowing which produces large scale SNR variations as depicted in Figure 1-(c). Introducing a spatial correlation between radio links is not yet proposed in current simulators but represents a challenging issue. For this purpose, s ij should refer to a spatially correlated stochastic process, slowly varying (see [START_REF] Graziosi | A general correlation model for shadow fading in mobile radio systems[END_REF] for instance). Shadowing is sometimes confused with fading. Fading instead relies on SNR time variations due to multi-path self-interference (see Figure 1-(d)). It has a leading role in wireless communications and is introduced also as a stochastic variable f ij :

g ij (t) = g ij • s ij • f ij (t)
This late variable is not spatially correlated as it relies on small scale phenomenon. Meanwhile, it is a time variant parameter. Considering its temporal correlation may be highly relevant [START_REF] Pham | New cross-layer design approach to ad hoc networks under Rayleigh fading[END_REF] and represents another challenge for wireless simulators.

Radio link modeling

A frame error rate (FER), or a packet error rate (PER), as a function of the mean SNR can substitutes for the SNR threshold of Equation 7. It derives from the bit error rate (BER) function which itself relies on the radio interface properties. l ij then relates to the probability of a successful transmission. Some theoretical asymptotic expressions are well-known for various modulation techniques [START_REF] Wang | A simple and general parametrization quantifying performance in fading channels[END_REF]. However, the exact derivation at low SNR is sometimes not straightforward, more specifically in the case of fading channels, which can be introduced at this level with:

P s (E|γ) = ∞ 0 P s (E|γ) • f γ (γ|γ) • dγ s . ( 8
)
where f γ (γ|γ) stands for the instantaneous SNR distribution due to fading. The threshold-based radio link model as opposed to the PER-based radio link model, is depicted in Figure 2. It can be also of great importance to consider channel coding. For instance, bloc coding can be introduced thanks to bounding the code word error probability. Last but not least, the radio link can be more complex if the pulse time-spreading due to multi-path lies beyond the symbol period. In this case, the impulse response should be considered.

Interference modeling

Interference disturbs the packet reception at the physical layer. It appears as a crucial point in PHY simulations as final results can be strongly influenced by the interference model [START_REF] Cavin | On the accuracy of manet simulators[END_REF], [START_REF] Takai | Effects of wireless physical layer modeling in mobile ad hoc networks[END_REF], [START_REF] Heidemann | Effects of detail in wireless network simulation[END_REF]. As we will see in Section 4, interference management is probably the point where current simulators differ the most largely. Sources of interference include nodes operating in the same frequency band or in different frequencies. The first type of interference is known as co-channel interference, while the latter is termed adjacent channel interference.

The most efficient approach for introducing interference consists in replacing the SNR by a signal to interference plus noise ratio, SINR, which can be derived according to:

γij = h ij • P i N j + k =i,j h kj • P k (9)
The proper derivation of the SINR requires the knowledge, at a given time, of all the signals which are concurrently received at a given receiver.

To be exhaustive, it should be noted that non linear receivers (with multi-user detection for instance) [START_REF] Andrews | Interference cancellation for cellular systems: a contemporary overview[END_REF] can outperform classical receivers in the presence of interference. In this case, it is necessary to compute the FER not from the general SINR, but rather from the vector of received powers at each node.

MIMO systems

Multiple input multiple output (MIMO) interfaces are very promising and their simulation can be assessed in two ways. The former but simplest approach is referred to as the node-based approach and exploits the single antenna framework described above by adjusting the FER function according to a MIMO specific model. This approach is however not relevant for realistic systems where the radiation patterns of the multiple antennas differ from each other as well as for correlated channels. The latter, referred to as the antenna-based approach, is more powerful and simulates the channel state for each antenna-to-antenna link, separately. For instance, in a 2 × 2 MIMO system, four channels are simulated. It is very important to take care about the correlation between these channels to have accurate simulations. In this context, modeling spatially correlated shadowing and time correlated fading is of great importance [START_REF] Almers | Survey of channel and radio propagation models for wirelessmimo systems[END_REF].

PHY LAYER MODELING IN COMMON SIMU-

LATORS

Numerous wireless network simulators have been developed and are concurrently used in the wireless networking research domain. In this section, the PHY modeling of four widely used simulators is presented and briefly investigated. Table 1 summarizes the PHY models implemented in NS-2 [START_REF]The network simulator[END_REF], GloMoSim [START_REF] Bajaj | Simulation of large-scale heterogeneous communication systems[END_REF], JiST/SWANS [START_REF] Barr | Scalable Wireless Ad hoc Network Simulation. Handbook on Theoretical and Algorithmic Aspects of Sensor, Ad hoc Wireless, and Peer-to-Peer Networks[END_REF], GTSNetS [START_REF] Riley | Large-scale network simulations with gtnets[END_REF] and WSNet. This review is far from being exhaustive and other simulators with wireless support are available, such as OPNET, OMNeT++, etc.

Let us consider the PHY modeling as implemented in these simulators. As shown in Table 1, interference modeling, which is one of the most crucial aspects for the evaluation of protocols, is probably the point where current simulators differ the most largely.

The first step toward interference evaluation is to identify which signals are interfering with each other in order to assess the terms in the denominator of eq. 9, on the basis of timing considerations only. This set of interfering signals can be very large for large scale simulations. As a consequence, various simulators rather limit the range at which any signal can propagate and thus interfere. In other words, disregarding the radio range model effectively used for the received signal strength computation, the simulator does not generate receptions at nodes further than a given range from the source. Consequently, the considered source cannot induce interference at nodes further than this range. This optimization, which we will call Limited interference model as opposed to a Full interference model, is depicted in Figure 4. It privileges performance at the cost of accuracy. This optimization is implemented in JiST/SWANS, GloMoSim, GTSNeTS, etc.

Regarding the SINR computation, several strategies have been investigated and implemented in existing simulators. They are all variations of eq. 9 regarding timing granularity. They induce a varying level of realism, precision but also complexity. They are summed up in Figure 3: Note that none of these simulators supports multichannel systems and adjacent channel interference. For this purpose, the interference model in ( 9) should be replaced by:

• Fig 3(
γij = h ij • P i N j + k =i,j α ik • h kj • P k , ( 10
)
where α ik stands for the rejection factor between the channels associated with signals i and k.

It is obvious that these interference models offer different levels of complexity, accuracy or realism. In order to better evaluate the computational cost of interference modeling, we introduce the WSNet PHY simulation framework.

THE WSNET SIMULATION FRAMEWORK

The WSNet simulation framework is well-designed for the purpose of evaluating the performance of wireless networks. We first present a general overview of the WSNet simulator. We then focus on the physical layer modeling, including the radio range, the radio link and the interference modeling, and we show how these have been handled in WSNet.

WSNet: a general overview

WSNet [START_REF]The wsnet wireless network simulator[END_REF] operates either as a complete event-driven simulator for wireless networks (e.g., ad hoc, sensor, mesh, etc.), including the simulation of both the wireless nodes (i.e., application, routing, MAC, radio and antenna layers) and the radio medium as shown in Figure 5, or as a physical layer simulator with nodes being simulated by external simulators in a distributed simulation framework [START_REF] Chelius | Worldsens: development and prototyping tools for application specific wireless sensors networks[END_REF]. The design of WSNet has been mainly guided by two constraints: modularity and flexibility. Thanks to modularity, WSNet can offer a wide range of PHY models, from ideal ones to pseudo-realistic ones.

Thanks to flexibility, WSNet can be tuned to offering various trade-off between accuracy and computational complexity in the radio medium simulation. This choice obviously impacts the WSNet performance. The WSNet simulator, which is under the CeCILL Free Software License Agreement, is implemented in C language and runs on the Linux operating system. The WSNet source code can be downloaded from our SVN repository [START_REF]The wsnet wireless network simulator[END_REF]. Thanks to modularity, all simulation models (e.g., application, routing, MAC, propagation model, interference model, antenna, etc.) are compiled into dynamic libraries to ease the development and the integration of new simulation models. Moreover, WSNet uses an xml file to configure a simulation. This xml file describes the simulation setup and specifies, for example, the number of nodes to simulate, the libraries used to model the radio medium and the wireless nodes (e.g., application, routing, mobility, battery, etc.).

Once WSNet is compiled and installed on a Linux operating system, users can run simulations using the following command: "wsnet -c ./demo/cbr.xml", where ./demo/cbr.xml is a file describing the parameters of the simulation (i.e., number of nodes, size of the simulation area, node architecture, PHY models, etc.). Readers can refer to the WSNet website [START_REF]The wsnet wireless network simulator[END_REF] for more information. In the rest of this section, we describe the WSNet PHY modeling.

PHY layer simulation

In WSNet, a radio signal is characterized by the following values: the transmission power, the symbol rate, the modulation scheme and the channel number. The PHY layer is abstracted as a combination of independent blocs which represent radio medium properties or hardware components. The radio simulation is built upon the following blocs: (i) a propagation bloc dealing with propagation aspects including path-loss, shadowing and fading according to the definitions provided in section 3;

(ii) an interference bloc which implements eq. 10; (iii) modulation blocs which provide SINR-to-BER conversions; and (iv) antenna blocs which implement antenna properties: loss, gain, radiation pattern, orientation and position. Note that WSNet offers a 3D spatial representation.

These blocs are black-boxes with well-defined interfaces. At simulation runtime, they are linked to dynamic libraries which effectively implement the interface. As an example, for the propagation bloc, a dynamic library implements the free space propagation model while another one provides a Rayleigh channel and a third one inputs path-loss values from an external file or an external propagation tool. More generally, this architecture is an opportunity to offer a wide range of radio medium models, from a basic ideal physical layer with no interference and no path-loss to a more realistic one including a Rayleigh channel, multiple frequencies, complex modulation schemes and smart antennas. It is thus a good opportunity to study the computational cost of using pseudo-realistic radio models.

Radio range simulation

When considering a transmission initiated by an antenna i, WSNet generates two events at each receiving antenna. The first one notifies the apparition of the signal while the second one notifies its end. Given a receiving antenna j, the two events are scheduled according to the distance between the emitting and receiving antennas, the radio propagation speed and the signal symbol rate. By default, the set of receiving antennas is extended to all antennas of the network. Thus, by default, WSNet operates in a full interference mode. However, the simulation setup may be initialized with a limited interference mode together with a maximum range after which receptions and interference are not further computed. This range is independent from the radio range model implemented in the propagation bloc.

For each reception, i.e. each receiving antenna j, the received signal strength is computed according to the operations and properties depicted in Figure 6: (1) the emitting antenna noise N i , (2) the emitting antenna gain g i (θ ij , φ ij ), (3) the signal attenuation including shadowing and fading effects g ij (t), (4) the receiving antenna gain g j (θ ji , φ ji ) and ( 5) the receiving antenna noise N j . Noise at R = P 1 × α 13 + P 2 × α 23 + P 3 × α 33 α ij is the correlation factor between channels i and j. Channels have also been introduced to support multichannel and MIMO systems. Channels divide the radio resource in sub-resources which mutually interact. As an example, channels can be used to model frequencies in a FDMA (Frequency Division Multiple Access) network as well as codes in a CDMA (Code Division Multiple Access) one. We do not explicit what channels are but we rather explicit their correlation, i.e. how they interfere with each others. While computing the interference on channel i, the contribution of a signal emitted on channel j is weighted by a correlation factor α ji as given in eq. 10. α ji values are provided by the interference bloc. A simple SINR example with adjacent channels interfering signals is depicted in Figure 7-8.

Radio link simulation

Upon signal reception and for each computed SINR, the impact of interference on the radio signal is evaluated through the computation of a BER value. The SINR to BER conversion is provided by the modulation bloc that characterizes the radio signal. As for the SINR, a BER value is associated with each slot of the radio signal. Based on the BER values and the slot lengths, a FER is finally computed. Contrarily to GloMoSim, WSNet forwards the radio signal to the receiving antenna whatever the FER value and whenever the first error arises. Indeed, in real systems, more specifically when complex coding and scrambling are used, the final decision -success or failure -cannot be taken before the frame is completely received.

An optional feature of WSNet is to randomly introduce errors in the radio signal with a probability equal to the computed BER. In this case, an erroneous signal is transmitted to the receiving antenna. Given this feature, it becomes possible to study precisely the performance of channel coding and error correction algorithms through their implementation in the node simulation part. More generally, CDMA schemes can be either simulated statistically using channels and correlation factors or studied precisely through their implementation and the error introduction feature.

IMPACT OF THE PHYSICAL LAYER MODELING

We now study the cost of PHY modeling accuracy using WSNet, focusing on the three aspects that have been developed in Section 3: radio range modeling, interference modeling and radio link modeling. As an estimation of the computational cost, we use the speedup metric. The speedup of a simulation is the ratio between the logical simulated time and the effective simulation time. Unless specified otherwise, the simulations consist in 100 nodes deployed randomly in a 2D 100m × 100m area. Each node emits a 100B/s Constant Bit Rate (CBR) broadcast traffic through an IEEE 802.15.4 868Mhz compliant radio. No MAC protocol is executed in order to focus on the PHY simulation. The presented speedups are averaged over 100 simulations with the confidence intervals being omitted as they have been found to be very small.

Radio range models

To assess the impact of radio range models on the speedup of simulations, we compare four common propagation models: a disk model (no path-loss) with transmission ranges of 60m and 200m, the free-space model, the two-ray ground model and a Rayleigh channel with a path-loss exponent of 2 for the last three cases. Interference and modulation supports are disabled. The results are drawn in Figure 9. Quite obviously, a better accuracy in the radio range model induces a decrease in the simulation speedup. There are two reasons for this overhead. The first one is the computational cost associated with the radio range model. It takes more time to compute a complex pathloss with random variables than a single distance. The second one is an increase in the number of receptions generated by a single emission. Consider for example the Range(60) and Range(200) models. They have the same computational cost but the number of receivers is larger with a range of 200 meters. In a realistic modeling, this overhead is even higher as the signal reaches all nodes. If the first overhead can hardly be reduced, the second one can be reduced using the limited interference model.

Interference models

Keeping the free-space propagation model, we now analyze the impact of interference management on the scalability of simulations. In a first step, we make the number of SINR slots computed vary from 0, no interference simulation, to n -one computed SINR per byte. Results are depicted on Figure 10. In a second step, we evaluate the cost of multi-channel support and adjacent channel interference computation. We vary the number of simultaneously simulated channels from 1 to 16. Results are depicted in Figure 11.

Support of a cumulative interference model induces a strong overhead as the speedup is roughly reduced by 50% from no interference simulation to a single SINR computation. However, in interference modeling, it seems that the first step is the one that costs the most. Indeed, from a single SINR to a per-byte computation, the extra overhead remains quasi constant for each refinement: from 4% for two SINR values to 45% for n values. In consequence, once the interference price has been paid, there is no strong reason to decline paying for a better accuracy. This same conclusion holds for multichannel support as its cost is negligible compared to the one associated with an accurate interference modeling.

Radio link models

In addition to interference, we now evaluate the cost of an accurate radio link modeling by integrating three modulation models in the simulations: SINR threshold, bpsk and oqpsk. The results are shown in Figure 12.

As a BER value is derived from each computed SINR, the overhead induced by the radio link model is function of the interference modeling accuracy. As in Section 6.1, a realistic model induces a higher overhead: the computational cost of the erf c function used in the bpsk model is much higher than a simple comparison between a SINR and a threshold. However, from a SINR threshold to a bpsk function, the speedup only decreases by 4% to 17% depending of the number of SINR slots. This price may clearly be worth the gain.

LIMITED INTERFERENCE MODEL

In this Section, we study the speedup gain that can be achieved through the use of a limited interference model. If this model decreases the accuracy of the PHY layer simulation, it is supposed to increase the scalability of simulators, justifying its use in GloMoSim, JiST/SWANS, NS-2, GTSNeTS, etc. Next, we discuss the feasibility of a statistical interference model whose aim is to improve the accuracy of the limited interference model without loss of performance.

Limited interference model and range searching

When simulating a wireless network, nodes are generally spread over a two or a three dimensional simulation area. Each node is then characterized by geographic coordinates (i.e., an x-y-z position) and communicate with its neighbor nodes which are located within communication range. Thus, during the physical layer simulation step, the simulator has to determine which nodes will receive a given transmitted packet. This operation is called range searching. It is an important operation in wireless network simulation and can be defined more formally as follows: given a set of N nodes deployed over a X ×Y ×Z area, and a source node located at (x 1 , y 1 , z 1 ) and broadcasting a packet, which nodes lie in the sphere with a radius equal to the limited interference range and centered at the source node?.

A naive solution to the problem of range searching is to organize the nodes into a linear structure, as in GTSNetS [START_REF] Riley | Large-scale network simulations with gtnets[END_REF] and NS-2 [START_REF]The network simulator[END_REF]. To determine the nodes located at a given range from a source node, the idea is to parse the entire linear structure and to compute the euclidean distance between the source node and all possible destination nodes. If the distance is below a given threshold (i.e., the limited interference range), the node is thus selected as a possible receiver for a transmitted packet (see Figure 13-(a)). The complexity of range searching using a linear list is O(n).

Several optimized data structures have been proposed for the problem of range searching [START_REF] Bentley | Data structures for range searching[END_REF]. For example, grid partitioning, which have been shown to increase the scalability of NS-2 [START_REF] Naoumov | Simulation of large ad hoc networks[END_REF], can be considered. In this strategy, the simulation area is divided into cells of fixed size as shown in Figure 13-(c). Each cell represents a linear list containing the nodes which are located within the cell. The range search operation consists thus in searching the nodes in the adjacent cells, reducing the number of queries compared to a flat or a linear scheme where all nodes are considered (see Figure 13-(a)).

To cope with irregular topologies, kd-tree [START_REF] Bentley | Data structures for range searching[END_REF] (see Figure 13-(b)) can be used to aggregate adjacent empty grid cells to form a larger empty grid cell. Range search operation is then performed with a complexity of O(log n). However, the main drawback of this approach is that it is very hard to rebalance the tree when inserting or deleting a record. Such an approach will thus be ineffective in very dynamic scenarios.

To optimize simulations under the limited interference model, WSNet implements the grid partitioning strategy. In addition, to cope with irregular topologies an optimized data structure, called db-tree (dynamic balanced tree), is also implemented (see Figure 13-(d)). The idea, similar to the one presented in [START_REF] Tropf | Multidimensional range search in dynamically balanced trees[END_REF], is to combine the grid strategy, for fast query processing, and the treebased approach for the aggregation of adjacent empty We study, in what follows, the speedup gain that can be achieved through the use of a limited interference model and optimized data structures. If this model decreases the accuracy of the PHY layer simulation, it is supposed to increase the performance of simulators, justifying its use in GloMoSim, JiST/SWANS, etc. For this evaluation, we consider a network of 2000 nodes randomly deployed in a network of size 1000m×1000m. No interference nor modulation is simulated. We compare the speedup achieved using the limited interference model for various maximum interference/reception ranges to the one achieved using the full interference model. The results, depicted in Figure 14, show the speedup achieved by the linear, the grid and the db-tree data structures.

As it was already pointed out in Section 6.1, a reduction in the number of receivers induces a large gain in the simulation speedup. For a limited interference range of 30 meters, with the correct data structure, the speedup can be increased by a factor of 332. In largescale networks, this gain remains high even for larger ranges. With a limited range of 120 meters, a gain of 37 is still achieved.

Towards a statistical interference model

It is quite obvious that the limited interference model is a must to ensure a high performance. However, its use raises the issue of determining a correct range (i.e., the distance limit for the propagation). As a solution, [START_REF] Ji | Improving scalability of wireless network simulation with bounded inaccuracies[END_REF] proposes an empirical method to derive a range with a limited impact on the simulation accuracy. We state that a statistical approach may offer a good tradeoff between the computational overhead of the completely deterministic Full interference model and the lower accuracy of the Limited interference model. In this Statistical interference model, the interference received at a node j is computed according to the following equation:

I j = k =i,j|d(|j,k)≤R h kj • P k + ξ R (11)
where ξ R is the realization of a random variable which statistically models the interference stemming from emitters outside the ball of radius R centered in j, B(j, R). As for the Limited interference model, the validity of this statistical model depends on the considered value of R, which can be easily determined as in [START_REF] Ji | Improving scalability of wireless network simulation with bounded inaccuracies[END_REF], but also on the distribution of ξ R . In such a context, the challenge is to find the exact distribution of ξ R that better approximates the level of interference stemming from long-range emitters.

ACCURACY versus COMPLEXITY OF SIMU-

LATIONS

Finally, we propose a case study to clearly summarize the impact of the physical layer modeling on the accuracy and the complexity of simulations.

Assumptions

We consider a varying number of static nodes randomly deployed in a 2D 200m × 200m area. Each node transmits periodically a hello packet (100B/s) through an IEEE 802.15.4 868Mhz compliant radio. We consider five metrics: the speedup, the average number of discovered neighbors, the average number of connex components, the distance to the farthest discovered neighbor node, and the application throughput. The first metric assesses the impact of the physical layer modeling on the performance and the scalability of the simulator while the four latter metrics show the impact of the PHY models on the evaluation of higher level protocols in terms of network connectivity and application throughput.

We perform the same set of simulations with various PHY models. Starting from (i) an ideal PHY layer, with no collisions nor interference, where all transmitted packets are received according to a basic disk propagation model with a range of 50m. We then (ii) introduce an IEEE 802.15.4 868Mhz compliant radio layer with a transmission power of 0dBm, where collisions can occur, and a limited interference model with a range of 50m. Next, we slightly increase the PHY simulation accuracy through the introduction of a (iii) free-space propagation model with a pathloss of 2, and a (iv) lognormal uncorrelated shadowing propagation model with a standard deviation of 4dBm and a close-in reference distance of 1m. Finally, we consider a cumulative interference model with a limited interference range of 100m and BP SK modulation for (v) one slot per packet and (vi) n slots per packet. We finish with the (vii) full interference model. To better investigate the impact of the Medium Access Control (MAC) layer, we design two sets of simulations with and without a 802.11 DCF MAC protocol. The simulation results are averaged over 30 runs and are reported in Figures 1516171819.

Simulation results

The first set of simulations is designed to investigate the impact of the physical layer modeling on the performance of WSNet through the evaluation of the speedup. As shown in Figure 15, the PHY models impact the obtained average simulation speedup. With no MAC layer (see Figure 15-(a)), we notice that the ideal PHY model induces a high simulation speedup which decreases while improving the accuracy of the physical layer modeling. Still considering the speedup, the main gap occurs with the introduction of interference and modulation support. Next, as previously observed in Section 6.2, considering n SINR slots instead of 1 induces a regular extra overhead. Finally, the full interference model does not induce too much overhead as the network area is small in this particular case.

When considering a MAC layer, the number of events and states increase during the simulation, particularly for a high number of nodes. In that case, the computational overhead is expected to raise. However, we notice from Figure 15-(b) that the obtained global speedup remains high and slightly decreases when using more accurate interference models. As the medium access control layer reduces the number of collisions and interferers, the overhead required for computing the SINR is also reduced and thus the global simulation speedup remains high compared to the case without a MAC layer. The extra overhead introduced by the MAC layer is thus balanced by the complexity reduction of the physical layer simulation.

The second set of simulations is designed to analyze the behavior of layer-3 protocols under variable PHY , that the simulation results are quite different from the case with no MAC layer. Indeed, we observe that the maximal distance of discovery as well as the network connectivity are improving with the introduction of more accurate PHY models. Again, this is a direct consequence of the MAC layer which reduces the number of interferers and collisions, yielding thus to better network performance.

Finally, the third set of simulations is designed to study the behavior of application-layer protocols under variable PHY models. From the results depicted in Figure 19, we can make two observations. First, when simulating the wireless nodes without a MAC layer (see Figure 19-(a)), we notice that the application throughput deteriorates while improving the accuracy of the physical layer modeling. Indeed, a first gap occurs when moving from the ideal physical layer to the basic model. Next, a second gap can be observed when adding the interference and modulation support. Second, we observe from the results obtained with a MAC layer (see Figure 19-(b)) a constant application throughput even with an accurate interference model. Again, the MAC layer enhances the network performance by avoiding collisions reducing thus the level of interference.

CONCLUSION

A multitude of research papers have recently presented simulation results for the performance evaluation of wireless networks. Most of these simulations are based on unrealistic and inaccurate physical models which may impact largely the confidence in the results. In this paper, through the introduction of the WSNet simulator, we have studied the impact of the physical layer modeling on the scalability and the accuracy of wireless network simulations.

To the question raised in the introduction, what is the real cost of PHY simulation accuracy, we can give the following conclusions. Accuracy has a variable cost depending on the considered PHY aspect. Regarding the radio range modeling, the cost of using a realistic model remains low, especially compared to the gain that can be achieved in term of accuracy. As a consequence, the unitdisk graph model can be easily substituted for a more realistic propagation model without a severe degradation of the simulation scalability. However, interference modeling, which is the point where current simulators differ the most largely, induces a real high overhead. This extra overhead remains regular when the interference modeling gets refined through the addition of realistic link and modulation models. As a consequence, it seems regrettable to precisely simulate interference without considering a realistic modulation or link model. As shown in this paper, interference and link modeling have a significative impact on the behavior and the performance of the evaluated protocols.

Finally, we conclude that given these trends, it remains up to the user choice to trade PHY accuracy for a desired scalability. However, we must keep in mind that, as highlighted in this work, the validity of simulation results highly depends on the choices made for the PHY modeling. In particular, if the use of optimization techniques drastically reduces the computational load, it does not solve the accuracy versus scalability tradeoff. Considering the limited interference model for example, the optimization performance and correctness now depend on the chosen limited range. In the future, we plan to investigate the statistical interference model in more details. In parallel to the empirical model proposed by [START_REF] Ji | Improving scalability of wireless network simulation with bounded inaccuracies[END_REF], we think that a stochastic theoretical analysis would be helpful in determining an adequate range and the distribution of interference stemming from nodes outside the interference range. The goal is to still enhance the scalability of simulators without affecting the confidence in the simulation results.

Fig. 1 .

 1 Fig. 1. Propagation models.

Fig. 2 .

 2 Fig. 2. Radio link modeling.

Fig. 4 .

 4 Fig. 4. Limited versus full interference model (T: transmitter, R: receiver and I: interfering nodes).

Fig. 3 .

 3 Fig. 3. SINR computation strategies at the node receiving the packet B.

Fig. 5 .

 5 Fig. 5. The WSNet simulation environment.

Fig. 6 .reception 5 . 4 α 12 α 13 α 21 1 α 23 α 31 α 32 1 Fig. 7 .

 65417 Fig. 6. Signal reception

Fig. 8 .

 8 Fig. 8. Co-channel and adjacent channel interference computation.

9 .

 9 Impact of propagation models.

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Impact of co-channel interference.

Fig. 12 .

 12 Fig. 12. Impact of modulation on speedup.

Fig. 13 .

 13 Fig. 13. Space partitioning optimization for range search operation under the limited interference model.

Fig. 14 .

 14 Fig. 14. Space partitioning methods.

  -(a)), the introduction of the interference modeling makes the network less connected and the distance to the farthest discovered neighbor is very low.When considering a 802.11 medium access control protocol, we observe from Figures16-(b), 17-(b), and 18-(b)

Simulation Radio range modeling Radio link modeling Interference modeling environments pathloss shadowing fading link model modulation model SINR computation NS-2 free

		space, two-ray	log-normal	rician, rayleigh	threshold	-	limited	strongest signal
	GloMoSim [6]	free-space, two-ray	log-normal	rician, rayleigh	threshold, BER	BPSK, QPSK	limited	adaptive
	JiST/SWANS [7]	free-space, two-ray	-	rician, rayleigh	threshold, BER	BPSK	limited	cumulative
	GTSNetS [8]	free-space, two-ray	-	-	threshold	-	limited	strongest signal
	WSNet [23]	free-space, two-ray	log-normal	rician, rayleigh	threshold, BER	BPSK, STEP, OQPSK, FSCK	limited, full	adaptive, cumulative

TABLE 1

 1 PHY layer modeling in common simulation environments: NS 2.31, JiST/SWANS 1.06, GloMoSim 2.03, GTSNetS and WSNet 2.0.

  Impact of the PHY modeling accuracy on the average number of connex components. Impact of the PHY modeling accuracy on the distance of the farthest discovered neighbor. the number of connex components and the distance from the farthest discovered neighbor vary systematically. If the largest gap also occurs when interference and modulation are introduced, the results still degrade when the accuracy of the interference modeling is increased. This degradation is more important with a high number of nodes. Sensibility to PHY accuracy increases with the network size. Indeed, regarding the number of connex components (see Figure17

	60	120
	100	100
	0.001 0.01 0.1 1 10 Fig. 15. Impact of the PHY modeling accuracy on the simulation speedup. ideal basic +pathloss +shad +sinr/bpsk+n slots +all interf Speedup PHY models 250 nodes 500 nodes 750 nodes 1000 nodes 1500 nodes 0.001 0.01 0.1 1 10 ideal basic +pathloss +shad +sinr/bpsk+n slots +all interf Speedup PHY models 250 nodes 500 nodes 750 nodes 1000 nodes 1500 nodes (a) Without MAC (b) With MAC 1 10 100 ideal basic +pathloss +shad +sinr/bpsk +n slots +all interf Avg. nbr of discovered neighbors PHY models 250 nodes 500 nodes 750 nodes 1000 nodes 1500 nodes 1 10 100 ideal basic +pathloss +shad +sinr/bpsk +n slots +all interf Avg. nbr of discovered neighbors PHY models 250 nodes 500 nodes 750 nodes 1000 nodes 1500 nodes (a) Without MAC (b) With MAC Fig. 16. Impact of the PHY modeling accuracy on the average number of discovered neighbors. 1 10 100 1000 ideal basic +pathloss +shad +sinr/bpsk+n slots +all interf Nbr. of connex components PHY models 1500 nodes 1000 nodes 750 nodes 500 nodes 250 nodes 1 10 100 1000 10000 ideal basic +pathloss +shad +sinr/bpsk+n slots +all interf Nbr. of connex components PHY models 1500 nodes 1000 nodes 750 nodes 500 nodes 250 nodes (a) Without MAC (b) With MAC 20 30 40 50 ideal basic +pathloss +shad +sinr/bpsk +n slots +all interf Max. distance of discovery PHY models 250 nodes 500 nodes 750 nodes 1000 nodes 1500 nodes 20 40 60 80 100 ideal basic +pathloss +shad +sinr/bpsk +n slots +all interf 250 nodes Max. distance of discovery PHY models 500 nodes 750 nodes 1000 nodes 1500 nodes (a) Without MAC (b) With MAC Fig. 18. 0.1 1 10 100 ideal basic +pathloss +shad +sinr/bpsk +n slots +all interf Throughput (kbytes/s) PHY models 250 nodes 500 nodes 750 nodes 1000 nodes 1500 nodes 0.1 1 10 100 ideal basic +pathloss +shad +sinr/bpsk +n slots +all interf Throughput (kbytes/s) PHY models 250 nodes 500 nodes 750 nodes 1000 nodes 1500 nodes (a) Without MAC (b) With MAC Fig. 19. Impact of the PHY modeling accuracy on the throughput. models. With no MAC layer, we can observe from Figures 16-(a), 17-(a), and 18-(a), that the number of Fig. 17. 10 discovered neighbors,