Claude Universite

Bernard -Lyon

M François-Noël

Gilly M Le Professeur

Hamda Ben

Hadid M Le Professeur

Philippe Lalle

M Le Professeur

Germain Gillet

M Alain Helleu

Composantes Sante

J Etienne

La Mme

C Professeure

Burillon

D Bourgeois

Vinciguerra

Y Matillon

Mme La Professeure

A-M Schott

Keywords: Markov Chains, IEEE 802.11 DCF, Multi-hop Wireless Networks, Hierachical Modelling

COMPOSANTES ET DEPARTEMENTS DE SCIENCES ET TECHNOLOGIE

First of all, I would like to thank Mrs. Isabelle Guérin-Lassous (Professor at Université Claude Bernard Lyon 1) and Mr. Thomas Begin (Assistant Professor at Université Claude Bernard Lyon 1) for accepting the task of being my advisors in this thesis. In addition, I thank them for all their availability, valuable learnings and for the help in every moment of this journey.

Secondly I would like to thank Mr. Bruno Baynat (Associate Professor at Université Pierre et Marie Curie Paris 6) by also advising me during this thesis. His valuable contribution allowed the journey over the past few years to be more profitable and of great learning. I thank also all friends and supporters of the LIP laboratory, with whom I had pleasant moments throughout this work. I thank the members of the former RESO team and the current DANTE team with whom I have worked in close cooperation, especially to Mr. Huu-Nghi Nguyen (Phd. student at LIP), for all the work we performed together.

Finally, I thank my parents for always encourage me to overcome the challenges and achieve my dreams. I also thank my girlfriend, Maria Clara, my brothers and all my family by the underlying support over the years. Without their help, this work would never be done.

Abstract

The IEEE 802.11 protocol, based on the CMSA/CA principles, is widely deployed in current communications, mostly due to its simplicity and low cost implementation. One common usage can be found in multi-hop wireless networks, where communications between nodes may involve relay nodes. A simple topology of these networks including one source and one destination is commonly known as a chain.

In this thesis, a hierarchical modeling framework, composed of two levels, is presented in order to analyze the associated performance of such chains. The upper level models the chain topology and the lower level models each of its nodes. It estimates the performance of the chain in terms of the attained throughput and datagram losses, according to different patterns of channel degradation. In terms of precision, the model delivers, in general, accurate results. Furthermore, the time needed for solving it remains very small. The proposed model is then applied to chains with 2, 3 and 4 nodes, in the presence of occasional hidden nodes, finite buffers and non-perfect physical layer.

Moreover, the use of the proposed model allows us to highlight some inherent properties to such networks. For instance, it is shown that a chain presents a performance maximum (with regards to the attained throughput) according to the system workload level, and this performance collapses with the increase of the workload. This represents a non-trivial behavior of wireless networks and cannot be easily identified. However, the model captures this non-trivial effect.

Finally, some of the impacts in chains performance due to the IEEE 802.11 mech-6 anisms are analyzed and detailed. The strong synchronization among nodes of a chain is depicted and how it represents a challenge for the modeling of such networks. The proposed model overcomes this obstacle and allows an easy evaluation of the chain performance.

Résumé

Le protocole IEEE 802.11, basé sur les principes CMSA/CA, est largement déployé dans les communications sans fil actuelles, principalement en raison de sa simplicité et sa mise en oeuvre à faible coût. Une utilisation intéressante de ce protocole peut être trouvée dans les réseaux sans fil multi-sauts, où les communications entre les noeuds peuvent impliquer l'emploi de noeuds relais. Une toplogie simple de ces réseaux impliquant une source et une destination est communément connue en tant que chaîne.

Dans cette thèse, un modèle hiérarchique, composé de deux niveaux, est présenté dans le but d'analyser la performance associée à ces chaînes. Le niveau supérieur modélise la topologie de la chaîne et le niveau inférieur modélise chacun de ses noeuds. On estime les performances de la chaîne, en termes de débit obtenu et de pertes de datagrammes, en fonction de différents modes de qualité du canal. En termes de précision, le modèle offre, en général, des résultats justes. Par ailleurs, le temps nécessaire à sa résolution reste très faible. Le modèle proposé est ensuite appliqué aux chaînes avec deux, trois et quatre noeuds, en présence de stations cachées potentielles, de tampons finis et d'une couche physique non idéale.

Par ailleurs, l'utilisation du modèle proposé permet de mettre en évidence certaines propriétés inhérentes à ces réseaux. Par exemple, on peut montrer que la chaîne présente un maximum de performance (en ce qui concerne le débit atteint) en fonction du niveau de charge de du système, et que cette performance s'effondre par l'augmentation de cette charge. Cela représente un comportement non trivial des réseaux sans fil et il ne peut 8 pas être facilement identifié. Cependant, le modèle capture cet effet non évident. Chapter 1

List of Tables

List of Principal Notations

Introduction

Multi-hop wireless chains and Substitution Networks

The use of wireless networks is, undoubtedly, widespread in communications nowadays.

Several reasons can explain this large usage. For instance, we can mention the mobility feature, in opposition to fixed stations using wired communications, the simplicity to increase the number of users or the possibility of reaching isolated areas, which are not easily connected to traditional wired links.

As a natural consequence, many standards were established in order to organize the way communications are performed. In this context, we mention the IEEE 802.11 protocol, based on the CSMA/CA (carrier sense multiple access with collision avoidance) principles, which stands among the leading communication standards for local wireless networks. Its success can be explained by its simplicity and relatively low cost implementation. One of the most known types of local wireless networks implementing such a protocol is infrastructure-based networks. In this type of organization, communication are performed directly between nodes and access points. Figure 1.1 shows a simple example where some wireless devices perform communication through an access point.

Another well known architecture of wireless local networks is multi-hop networks. In One recent use of multi-hop wireless networks is Substitution Networks. This type of network stands for a wireless solution whose purpose is to bring back connectivity or to provide additional bandwidth capacity to a network that just suffered a failure or a dramatic surge in its workload (e.g., flash crowd effect). This latter network is called the base network, and it can be based on wired or wireless technologies. It is worth pointing out that a substitution network does not seek to provide new services to customers.

Its goal is rather to restore and/or maintain at least some services that were available prior to the base network troubles. As a matter of fact, a substitution network is not a stand-alone network.

Two types of nodes are involved in a substitution network: (i) Bridge routers, which are basically gateways interconnecting the base network and the substitution network;

(ii) Mobile routers, which are the core piece of the substitution network. Their positioning should be done so as to give rise to path(s) that will route the traffic delivered by the base network through the substitution network. Obviously, bridge routers require a wireless interface to connect to the substitution network, and mobile routers require motion capabilities to move towards their expected position. Wifibots1 or micro-drones, like for instance AR.Drone 2.02 , can be used as mobile routers. Last but not the least, an algorithm should decide where mobile routers should move to [START_REF] Miranda | Adaptive deployment scheme for mobile relays in substitution networks[END_REF], [START_REF] Razafimandimby | Fast and reliable robot deployment for substitution networks[END_REF]. technology should be embedded in mobile routers, is far much smaller. Such a drop in the capacity has clear implications with regard to the control policy to be implemented on the traffic at bridge routers. However, prior to these operations, it is crucial to position the mobile routers in the best possible way and so to investigate the performance behavior of a substitution network. For instance, investigated factors may include its capacity with regard to the deployed topology, transmission power assigned to router antennas, and buffer size on the wireless interfaces. In this direction, as an example, [ANB + 12] makes an analysis on the capacity of simple multi-hop wireless networks and how this capacity is impacted according to the amount of conveyed information and the number of relay nodes.

Even more recently, the application of multi-hop wireless networks was extended.

The company Google has developed a new implementation of multi-hop wireless net-works, referred as the Loon Project4 . The goal is to connect isolated areas, where network connections are poor or inexistent, by using balloons equipped with wireless interfaces. Such balloons are capable of communicating between them and, therefore, they are capable of creating a network to connect users to the Internet Service Providers around the world. In the context of multi-hop wireless networks, the most basic topology is a chain. is not possible (stations may be too far away from each other and can not be directly connected). Therefore, it is necessary to use some relay wireless nodes to establish a "path" that ensures the communication between the stations. In our example, the four

Wireless chains models

Throughout this work, the wireless technology considered for communications is IEEE 802.11, implementing the DCF (distributed coordination function) mechanism. Its features and behaviors are described in the next chapter.

Although chains seem simple to understand, their performance can not be, in general, easily derived. It is known that several factors impact the behavior of such topologies, like for instance, the number of relay nodes, the distance between them, the amount of information conveyed, to mention but a few. Moreover, some issues, like for instance, the hidden node problem or the long-term unfairness may take place and they strongly impact the chain performance.

Therefore, several studies are proposed in literature to estimate their performance and to better understand those networks. They can be used to predict the chain behavior and analyze its performance. For example, several works show that the chain performance may collapse whenever the amount of information to convey exceeds a limit [START_REF] Ng | Throughput Analysis of IEEE 802.11 Multi-hop Ad Hoc Networks[END_REF], [ANB + 12]. Although network simulators (or even real testbed experiments) present such behavior, it is not trivial to derive an explanation for this performance collapse without a deeper insight into the network variables. In this direction, analytical models represent interesting tools, since any information of the network can be easily retrieved (on the condition it is incorporated on the model).

Additionally, analytical models are usually quickly solved once they are parameterized, when compared to traditional networks simulators or real testbeds. Besides, some models can predict the behavior of a wide range of topologies with small modifications.

Simulators and real testbeds, however, demand to re-run experiments for each analyzed topology, with is often a strong time-consuming task. Moreover, such simulators and real testbeds usually demand third-party softwares to collect data (like, for instance, Wireshark5 ) or to handle the gathered information (like MATLAB6 ). The implementation of such analytical models is also far less expensive, since no special hardware nor special software is demanded. These advantages make analytical models serious candidates for evaluating chains performance.

Unfortunately, a significant amount of works make strong simplifying assumptions when modeling a chain, in order of to keep the corresponding models tractable. We can cite, for instance, the use of infinite buffers, which avoids dealing with information losses, the implementation of a perfect physical layer or the assumption that nodes have always information to send. As a consequence, the results obtained may considerably deviate from the actual behavior of the studied network. Furthermore, several works restrict their analysis for the cases of one-way traffic. If we take the example of Figure 1.5, it means a traffic generated at station A towards station B, but no traffic in the opposite direction. The substitution networks, however, intend to replace links that are usually bidirectionals. Thus, such networks may convey traffic in both directions. We discuss further about those models in the following chapters.

In this work we overcome some of the limitations of the previously proposed models.

We present a hierarchical based modeling framework, composed of two levels, to evaluate the performance of a IEEE 802.11-based chain. The upper level models the chain topology, while the lower level models each node of the chain. Moreover, the modeling framework also includes a solution for the hidden node problem for the case analyzed in this work. Our model computes the performance of the chain in terms of attained throughput and datagram losses, according to different channel degradations patterns due to Bit Error Rate. In order to validate our model, we compare the performance obtained with the proposed model and those delivered by a discrete-event simulator. Finally, we use our model to investigate some behaviors associated to such a chain, in order to get a better understanding of multi-hop wireless networks and to highlight properties inherent to those networks.

Organization of this work

This work is divided as follows. In Chapter 2, we describe the mechanisms associated to the IEEE 802.11 technology we consider in our model and the tool we use to validate it. We make an extensive use of a network simulator to validate our model, and thus we adapt it to represent multi-hop wireless chain scenarios more realistically. We also describe all the changes we have performed in this simulator in Chapter 2.

A discussion about the state-of-the-art concerning chain models and performance evaluation is presented in Chapter 3. We are interested in the benefits presented by our model and we compare it with other works.

Chapter 4 presents our modeling framework. We discuss all the assumptions that we make. We apply it to two simple scenarios, composed of two and three nodes, with one single station generating traffic, in order to give the most important insights with regards to our model. We show that, despite the apparently simplicity of such scenarios, they present complex behaviors, which are worth of investigation.

In Chapter 5, we extend our scenarios to the case where the two extremity stations generate traffic and the relay node has to deal with different channel conditions at the same time. We show that, with regard to our model, there is no need of many adaptions to handle such scenarios.

Chapter 6 extends the modeling to a scenario where we deal with the problem of hidden nodes. This type of issue is complex and hard to overcome, but we show how our model can be adapted to satisfactorily evaluate chains with such characteristics.

The conclusion of our work and the future researches that shall be performed con- In order to avoid collisions, before transmitting a frame, a node must sense the channel until the latter is found to be idle for a protocol time DIFS (DCF Interframe 30 Space). It is important to clarify when the channel is considered to be idle or busy, according to a node. Consider the topology presented in Figure 2.1. In this topology, node 1 transmits a signal that arrives at some nodes. The nodes that are capable of sensing such signal and decode it are considered as the neighbor nodes of node 1. We refer as the communication range the distance up to which neighbor nodes can receive the signal with a power higher than a given threshold, which triggers the decoding of the packet (nodes 2 and 3 in the figure). For these nodes the channel is considered to be busy. However, if the signal can be sensed by nodes but not with a sufficient power to be decoded by the wireless interface, we consider that these later nodes are in the carrier sensing range (nodes 4 and 5). Note that no communications succeed under these conditions, but the channel is still considered busy by nodes within this range. Finally, if the signal is so weak that it can not be sensed by the physical layer, the channel is considered idle by the nodes (nodes 6 and 7 in the example). If the channel is sensed idle during a time DIFS, the node must, then, defer a certain amount of time, whose value is randomly chosen within an interval determined by the contention window (also denoted W hereafter). This latter delay is expressed as a number of slot times and is referred to as the backoff. The backoff value is decremented by one whenever the channel is sensed idle during an entire slot time. If the channel is sensed as busy, the backoff value remains constant and is not decremented. Whenever "paused", the backoff is said to be in freezing state. The duration of the backoff freezing corresponds to the time the channel is sensed busy. During this period, the "frozen" node shall not transmit its frame. This mechanism aims to prevent two neighbor nodes from transmitting at the same time.

cerning
The backoff quits freezing state, and hence resumes its decrement, if the channel is sensed idle during a DIFS period. As the backoff value reaches zero, the node can start its transmission. Note that a backoff period can be interrupted several times due to multiple transmissions in its neighborhood.

A node considers that its frame has been successfully transmitted to its neighbor node when it receives an acknowledgment frame (ACK). If the node does not receive an acknowledgment before a timeout, whose value includes also a protocol defer time SIFS (Short Interframe Space), it assumes the corresponding frame has been lost, and thus it attempts to retransmit it up to a given limit defined in the standard. Note that at each retransmission of a frame, the contention window size is doubled up to at limit. If the first transmission of a frame as well as all its subsequent retransmissions fail, the node simply discards the corresponding datagram. Finally, each successful transmission of a frame (as well as a complete datagram discard) resets the contention window to its initial value. According to the standard, a node must replace DIFS by a EIFS (Extended Interframe Space) whenever the medium becomes idle after a frame reception that does not result in a correct reception at the MAC layer. In our study, we disable EIFS by only using DIFS. This choice is motivated by some works, like in [START_REF] Chaudet | Experiments of some Performance Issues with IEEE 802.11b in Ad Hoc Networks[END_REF]

Network Simulator 2

In order to simulate multi-hop wireless chains and to validate our model, we use the Network Simulator ns-2.35 [NS2]. We choose this tool, since it is already used in several works and it is quite adapted to wireless scenarios and to the IEEE 802.11 DCF protocol.

We make, however, some improvements in the tool, by incorporating functionalities that are not natively integrated.

One modification we perform is to add a non-perfect physical layer model to wireless transmissions. We incorporate the patch developed in [Fio] for this task. Then, bits may be corrupted during frame transmissions due to channel conditions, according to a certain probability. This probability is referred as Bit-error rate (BER). Whenever incorrect bits are received, we consider that the MAC layer is unable of correctly decoding the associated frame and discards it, forcing a retransmission (or a ultimately discard)

at the sending node. The reasons for these errors are various, including noise, signal attenuation distortion, interference, among others.

The actual value of BER depends on the received signal power, P rx , which is a function of the transmission power P tx of the sender and the distance d between the sender and the destination nodes. In our simulations, the value of P rx is calculated according to the 2-ray ground propagation model, as defined in Relation (2.1).

P rx = P tx . G t . G r . h t 2 . h r 2 d 4 (2.1)
Both signal powers are expressed in watts. G t and G r correspond to the gains of the transmitter and receiver node antennas, respectively, as defined in the wireless card specifications. h t and h r are the height of such antennas (in meters). This propagation model, implemented by default over ns-2.35, is well suited for outdoor environments, which can be considered in the RESCUE project described in the previous chapter.

Finally, we can relate the value of P rx to the corresponding BER, by using tables provided by wireless card manufacturers [START_REF] Hfa ; B Intersil | Direct sequence spread spectrum baseband processor[END_REF]. Note that want other relations could be used instead.

Furthermore, we incorporate to the simulator a datagram generator, according to a

Poisson process. This type of datagram generation is not natively developed for ns-2.35, but, as described in the following chapters, it is needed for our modeling approach.

Graphical Interface for ns-2.35 results

In order to get a better understanding of the IEEE 802.11 DCF interactions between neighbor nodes of a chain, we have developed a graphical interface to easily interpretate the ns-2.35 results1 . This tool translates datafile traces into readable pictures, which allows us to see at a glance when the states of nodes are in backoff, DIFS, transmissions, etc.

Consider the scenario depicted in Figure 2.5, composed of a chain with three nodes and datagrams traveling from node 0, using the relay node 1 up to the destination node 2. All nodes can sense each other and the links are not subjected to large values of Before any transmission, the node defers DIFS time, represented by the yellow bar.

Following, a random backoff is decremented (blue bar marked with "B") until transmission starts, as described in the green bars with a "T". The event T y x (id) corresponds to the x-th attempt of sending the frame identified by id at node y. For example, the first transmission of the image corresponds to the first attempt of sending frame 176 at node 0. In the same way, the event B x indicates that this backoff precedes the x-th transmission of the frame. After a transmission, node 0 remains paused in timeout ("P") Figure 2.6: Graphical interface implemented for ns-2.35 results.

waiting for the acknowledgment from node 1 (event "A" in the second line). We can see that this is a successful transmission and therefore, node 1 starts the procedure to forward frame 176 to the destination. When the last node of the chain acknowledges the frame, we consider that the associated datagram was correctly conveyed along the chain.

We can clearly see that, in this scenario with a light workload, there are empty spaces between two successive transmissions, which correspond to periods where the nodes are in starvation (no datagrams to send). Nevertheless, we can see that node 0 goes shortly into freezing state (red bar marked with "G 1 "), since the datagram associated with frame 178 was generated during the acknowledgment transmission at node 2. After the freezing period, as expected, node 0 defers for DIFS time (yellow bar) and then decrements its backoff.

Figure 2.6 also shows the quasi-periodicity between the events at neighbor nodes (backoff, DIFS, transmission, ...). For instance, a transmission from node 0 always precede a transmission from node 1. Furthermore in the case of light workloads, it is very likely that the nodes buffers are empty. Therefore, the backoff at the relay node is only triggered after the immediate arrival of a datagram from node 0. Moreover, we can see that even for a small duration, a node goes into the freezing state if and only if, during its backoff countdown, a neighbor transmits a frame. We show a second example of the graphical interface, for the same topology with three nodes and good links, but with a single heavy workload, as depicted in Figure 2.7.

The associated events can be found in Figure 2.8. We point out that, unlike to the previous example, datagrams may be lost due to buffer overflow. This happens since the datagram arrival rate at node 0 is greater than the output rate towards the relay node. For example, after the transmission of datagram 261 at node 0, the following one corresponds to 263. That means one datagram (a.k.a 263) was lost before entering the source node buffer, due to buffer overflow. We can also see that datagram 261 is only conveyed by the relay node after several other transmissions are finished (since the buffer is not empty when it arrives).

Another important behavior we can identify in chains, by using our graphical interface, is starvation under saturated scenarios. For example, consider the scenario depicted sensing range. We observe, with the graphical interface, one last behavior associated to chains: the collisions due to hidden nodes. In this scenario, such collisions occur between the frames of node 0 and acknowledgements of node 3, as shown in Figure 2.12, since they can transmit at the same time.

The collisions due to hidden nodes are not negligible and they may greatly impact the system performance. In this example, we can see that a collision occurs at both nodes 1 and 2, since the frame labeled 1596 from node 0 collides with the acknowledgement from node 3. The relay nodes, thus, are not capable of decoding the mixed signal that they capture.

The behaviors described in this section (synchronization, buffer overflow, starvation and collisions) are not easily captured by analytical models. Therefore, estimating the performance of a chain is not a trivial task and several models simply neglect them. Figure 2.12: Graphical interface for a scenario with collisions between frames and acknowledgments.

In our work, we incorporate those intrinsic characteristics at our modeling framework, since we believe they are important to deliver more accurate results.

Used Parameters for the Numerical Results

Throughout this work, we present several numerical results corresponding to different scenarios simulated with ns-2.35. The model, which will be proposed in the following chapters, is implemented by using the MATLAB tool, and its performance are compared with the one delivered by the simulator.

For any analyzed scenario, several characteristics of the network to study remains constant. First of all, we always consider that nodes are placed in a chain network.

Under this topology, a node can only communicate with its 1-hop neighbors, and the carrier sense range affects all its 2-hop neighbors. All nodes in the chain are identical in terms of computation and communication power.

In all the scenarios studied in this work, we have 1 or 2 fixed source nodes, at the borders of the chain, that generate the system workload. The workload is conveyed up to the opposite border node of the chain through relay nodes. Those relay nodes are placed at different positions to evaluate the network performance under different conditions. Second, the links between the nodes are not ideal and are subject to BER. The BER associated to the link is deduced from the signal power at the destination node and a table provided by wireless card manufacturers [START_REF] Hfa ; B Intersil | Direct sequence spread spectrum baseband processor[END_REF]. We assume that the links have a constant physical transmission rate, which means there is no auto-rate adaptation according to its quality. All the numerical results are obtained with a link physical transmission rate of 11 Mb/s.

Third, we use the 2-ray ground propagation model, whose parameters values (identical for all nodes) are described in Finally, the workloads are always generated according to a Poisson process (although they vary in intensity). The datagrams have a constant size of 1500 bytes.

Chapter 3

State-of-the-art

In this chapter, we present a detailed state-of-the-art concerning the subject of this thesis:

the modeling and the performance analysis of IEEE 802.11-based multihop networks using the DCF mechanism.

Insights on multi-hop chains

Some works have described the usage of mobile ad hoc networks for providing connectivity to isolated areas, with regard to commercial and military applications [CMC99], [START_REF] Giordano | Mobile Ad Hoc Networks[END_REF]. However, the notion of "Substitution Networks", to which this work is related to, is initially provided in [RBDDA + 11]. The authors describe the basic concept of such networks, which is to temporarily restore communication to a link that suffers a failure, while maintenance is deployed and performed over the broken link. They also describe the mechanisms required to make substitution networks operational and efficient. For example, the authors in [START_REF] Miranda | Adaptive deployment scheme for mobile relays in substitution networks[END_REF], [START_REF] Razafimandimby | Fast and reliable robot deployment for substitution networks[END_REF] propose an algorithm that evaluates the current throughput of a substitution network and decides if the routers must be differently positioned in order to increase the overall throughput. Moreover, in [START_REF] Miranda | On the impact of router's mobility on substitution networks[END_REF] the impact of mobility in substitution networks is discussed.

In that direction, it is important to evaluate the performance of a chain, which is the simplest topology of a multi-hop wireless network. The authors in [START_REF] Xu | Does the ieee 802.11 mac protocol work well in multihop wireless ad hoc networks?[END_REF] and [START_REF] Xu | Revealing the problems with 802.11 medium access control protocol in multi-hop wireless ad hoc networks[END_REF] study, by simulation, the performance of IEEE 802.11 DCF in multi-hop chains when the injected traffic consists of TCP flows. They point out the TCP instability and the unfairness issues that may arise with this topology. For example, the problem of hidden nodes engenders collisions that force the discard of datagrams, which the TCP mechanism considers as a broken link. As a consequence, it keeps often trying to reestablish the route, which severely penalizes the actual throughput of the network.

The authors of [LBDC + 01] study the capacity of multi-hop wireless networks based on IEEE 802.11 DCF and, specifically, the capacity of multi-hop chains. The performance are studied using the simulator ns-2. The authors turn on the RTS/CTS mechanism, set the physical rate of wireless links to 2 Mb/s, and assume that a single flow is sent through this topology (in fact the flow profile is not specified in the article).

The simulation results show that, when the flow rate becomes too large, the throughput achieved along a multi-hop chain tends to decrease with the number of hops of the chain and seems to converge towards a bound. They also show that the capacity of the chain can be attained for a specific flow sending rate and that the throughput obtained on the chain slightly decreases and becomes smaller than the capacity when the flow sending rate is increased. On the same topic, the authors in [ANB + 12] confirm, through simulations, for different chain topologies, that the throughput delivered by a chain increases with the workload up to a limit. After that limit, any increase in the system workload actually decreases its performance. Their work performs simulations for scenarios with 4, 5 and 6 nodes in a chain where 2 flows are conveyed in opposite directions.

In [START_REF] Ng | Throughput analysis of ieee802.11 multi-hop ad hoc networks[END_REF], the authors provide a throughput analysis of multi-hop chains with one transmitted flow. The analysis is carried out both by simulation and analytically and shows that the load injected into the chain must be controlled in order to reach the optimal overall throughput. This analysis focuses on interactions between hidden nodes. A similar study is provided in [START_REF] Yoo | Maximum end-to-end throughput of chain-topology wireless multi-hop networks[END_REF]. In [LHH + 07], the authors study the performance of a multi-hop chain under different physical rates, with and without the use of RTS/CTS, and with one-way flow. The results show that using high physical rates do not necessarily lead to the best performance in terms of end-to-end throughput and end-to-end delay, specifically when RTS/CTS is used.

The previous works, described in this section, are mainly based on simulation results.

When exploiting the real testbeds, the work developed in [START_REF] Cali | Dynamic tuning of the ieee 802.11 protocol to achieve a theoretical throughput limit[END_REF] estimates the average throughput that a IEEE 802.11-based network can achieve. The authors provide insights on how the exponential backoff mechanism impacts the overall performance of a network, since its conservative approach tends to enlarge the amount of time a node prevents from transmitting, in the presence of several frame losses. This study is deeper analyzed by the same authors in [START_REF] Cali | Ieee 802.11 protocol: design and performance evaluation of an adaptive backoff mechanism. Selected Areas in Communications[END_REF]. In [START_REF] Dhoutaut | Performance of a multi-hops configuration with 802.11: from simulation to experimentation[END_REF], the authors carry out real experiments on a multi-hop chain and comment the obtained performance. The chain consists of at most 4 hops and one CBR (Constant Bit Rate) over UDP flow is transmitted from one endpoint of the chain to the other endpoint at a saturated rate (i.e., there is always a datagram to send at the source and not all of them are correctly conveyed), with a physical layer of 2

Mb/s and without the use of RTS/CTS. The results show that the obtained throughput on the chain is very low (and smaller than the one obtained by simulation) and very unstable. They also show that the third and fourth links have lower performance than the first and second links.

In the same way, the authors in [START_REF] Razak | How do wireless chains behave?: The impact of mac interactions[END_REF] study potential interactions that can arise between the links of a chain. They evaluate, by simulation and with real experiments, the impact of the different possible interactions on the overall chain throughput.

The results show that, beyond a given sending rate of the injected flow, the overall throughput in the chain slightly decreases. This work had been started in [START_REF] Razak | Self-interference in multi-hop wireless chains: Geometric analysis and performance study[END_REF] with a less realistic model for the packet reception. In these works, CBR/UDP flows are transmitted. These studies are applied to TCP flows in [START_REF] Majeed | Analysis of tcp performance on multi-hop wireless networks: A cross layer approach[END_REF], although they are not applied for chain networks. This study therefore does not consider the targeted scenario of this article.

Models and applications

In the first part of this chapter, we have focused on the works that provide insights of the IEEE 802.11-based networks, by analyzing their behavior through simulations or real experiments. Now, our goal is to focus on the current development of models that are capable of representing such behaviors and, therefore, allow to easily derive the performance associated to a wireless multihop network.

Several models have been developed to evaluate the performance of 802.11 networks.

In the case of a cell (i. In other scenarios, where nodes may be outside the carrier sense range of some other nodes (i.e., there may be the hidden node problem), authors have often considered the case of single-hop flows, where the source and destination of flows are only one hop away. Such scenarios are obviously more complex than a cell since nodes are exposed to the hidden node problem. Initial studies are developed in [START_REF] Boorstyn | Throughput analysis in multihop csma packet radio networks[END_REF], [START_REF] Harshal | Performance modeling of asynchronous data transfer methods of ieee 802.11 mac protocol[END_REF], which consider the hidden node problem in simple scenarios. Wang and Kar [START_REF] Wang | Throughput modelling and fairness issues in CSMA/CA based ad-hoc networks[END_REF] develop an analytical markovian model to evaluate the average throughput of flows in such a network. For sake of simplicity, they assume no binary exponential backoff and a perfect physical layer (no BER). This first assumption is not in accordance to the IEEE 802.11 DCF mechanism and therefore, may lead to results that deviate significantly from the real ones. Some interesting studies about the impact of the exponential backoff over the system performance, and why it should not be neglected, can be found in [START_REF] Razafindralambo | Modélisation et évaluation de performances des stratégies de backoff[END_REF],

[RV06b], [HG00], [NP00], [START_REF] Deng | A new backoff algorithm for the IEEE 802.11 distributed coordination function[END_REF], [BDSG + 07] and [START_REF] Nithya | Simulation and performance analysis of various {IEEE} 802.11 backoff algorithms[END_REF].

Still on the field of single-hop transmissions, the authors of [GSK05, [START_REF] Garetto | Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks[END_REF][START_REF] Nardelli | Closed-form throughput expressions for CSMA networks with collisions and hidden terminals[END_REF] proposed models to derive the throughput of the wireless networks. In [START_REF] Garetto | Modeling media access in embedded two-flow topologies of multi-hop wireless networks[END_REF], authors evaluate the impact of the hidden nodes on overall performance and how to include them in modeling. Moreover, they also analyze the behavior of the network, in the presence of flows-in-the-middle, which correspond to flows that are in severe competition for channel access, resulting in poor performance. The works in [START_REF] Garetto | Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks[END_REF] and [START_REF] Nardelli | Closed-form throughput expressions for CSMA networks with collisions and hidden terminals[END_REF] extend this analysis for different nodes positioning and node starvation, but keeping the same characteristics (basically, single-hop flows). Despite their accuracy, these works may not be applied to our case since we focus on multi-hop flows (i.e., flows that use relay nodes to be conveyed up to the destination).

Other works are also proposed to deal with the hidden node problem, but they also restrict their analysis to single-hop flows. For instance, the authors in [ZYY + 14] investigate the maximum throughput of a IEEE 802.11-based wireless network and the performance issues arising in such networks. Authors in [START_REF] Medepalli | Towards performance modeling of ieee 802.11 based wireless networks: A unified framework and its applications[END_REF], [START_REF] Gao | Determining the end-to-end throughput capacity in multi-hop networks: methodology and applications[END_REF], [QZW + 07] and [START_REF] Jindal | The achievable rate region of 802.11-scheduled multihop networks[END_REF] provide frameworks based on iterative models, which is similar to the proposed approach presented in this thesis. However, such models can not be easily derived to multi-hop flows topologies and do not cope with the behaviors we intend to evaluate.

In [START_REF] Medepalli | Towards performance modeling of ieee 802.11 based wireless networks: A unified framework and its applications[END_REF] and [QZW + 07] and [START_REF] Jindal | The achievable rate region of 802.11-scheduled multihop networks[END_REF], authors consider that buffers have infinite capacities and, therefore, no datagrams are lost due to buffer overflows, which is a simplification that also deviates from the actual network performance.

All these works consider a perfect physical layer, where no bits are lost during the radio transmission. To make more realistic scenarios, several studies incorporate a realistic channel propagation model. The works developed in [START_REF] Hole | Capacity of an ieee 802.11b wireless lan supporting voip[END_REF], [START_REF] Syed | Performance analysis and modeling of errors and losses over 802.11b {LANs} for high-bit-rate real-time multimedia[END_REF],

[HHSW10], [START_REF] Chatzimisios | Performance analysis of ieee 802.11 dcf in presence of transmission errors[END_REF], [START_REF] Chatzimisios | Influence of channel ber on ieee 802.11 dcf[END_REF] and [START_REF] Yang | On physical carrier sensing in wireless ad hoc networks[END_REF] provide insights, mainly via simulations on the performance of a network using the IEEE 802.11 standard, in the presence of realistic channels. In [START_REF] Carvalho | A scalable model for channel access protocols in multihop ad hoc networks[END_REF], the authors develop a model that takes into account the frame losses due to transmission errors, although their model is restricted to singlehop flows networks. Other works provide insights on how to recover from such errors or to reduce their impacts, in order to preserve the network throughput performance (e.g., [START_REF] Jamieson | Ppr: Partial packet recovery for wireless networks[END_REF], [START_REF] Camp | Modulation rate adaptation in urban and vehicular environments: Cross-layer implementation and experimental evaluation[END_REF], [START_REF] Judd | Efficient channel-aware rate adaptation in dynamic environments[END_REF] or [START_REF] Vutukuru | Cross-layer wireless bit rate adaptation[END_REF]). Note that our goal in this thesis is to provide an accurate estimation of the actual behavior of the multi-hop wireless networks and not to reduce the impact of the channel errors.

Few works have been devoted to the case of multi-hop flows, i.e., flows where source and destination can not directly communicate, and may suffer from the hidden node problem. The works presented in [START_REF] Aziz | Models of 802.11 multi-hop networks: Theoretical insights and experimental validation[END_REF], [START_REF] Mukesh | Throughput analysis of a path in an IEEE 802.11 multihop wireless network[END_REF] and [START_REF] Abreu | Hierarchical Modeling of IEEE 802.11 Multi-hop Wireless Networks[END_REF] consider the performance of a flow conveyed through a chain. To help their analysis, authors in [START_REF] Aziz | Models of 802.11 multi-hop networks: Theoretical insights and experimental validation[END_REF] assume that all nodes in the chain are in saturation (i.e., they always have a datagram to transmit). However, it is very unlikely that all nodes in a chain are in saturation, since, due to datagram losses that mainly occurs on the first nodes of the chain, nodes nearby the end of the chain can starve (see, for instance, [LBC + 01]). In [START_REF] Mukesh | Throughput analysis of a path in an IEEE 802.11 multihop wireless network[END_REF], in order to evaluate the maximum attainable throughput of the chain, authors assume that it approximately corresponds to the actual capacity of the bottleneck link (i.e., the link with the longest time to transmit a datagram). This assumption neglects the fact that backoff periods of neighbor nodes may overlap, which affects the estimated throughput of the flow. In [START_REF] Abreu | Hierarchical Modeling of IEEE 802.11 Multi-hop Wireless Networks[END_REF], we proposed a model that takes into account the actual buffer limit of each node. Moreover, the model is capable of coping with the impact of starvation in relay nodes. However, it was limited to a 3-nodes scenario, where the hidden node problem was not present. These policies are also adopted, because some works claim that the MAC layer implementation is not suitable for multi-hop wireless networks ( [XS01b], [START_REF] Sobrinho | Quality-of-service in ad hoc carrier sense multiple access wireless networks. Selected Areas in Communications[END_REF], [START_REF] Gerla | Tcp performance in wireless multihop networks[END_REF] and [START_REF] Bensaou | Fair medium access in 802.11 based wireless ad-hoc networks[END_REF]). We can point out one major problem, which is the performance collapse on multi-hop chains [START_REF] Hsieh | Ieee 802.11 over multi-hop wireless networks: problems and new perspectives[END_REF]. For instance, the solution proposed in [START_REF] Yao | Synchronized multi-hop protocol with high throughput for an ieee 802.11 multi-hop wireless network[END_REF] reduces the performance collapse inherent to multi-hop flows by removing the backoff mechanism and protocol overheads. In [START_REF] Du | Emac: An asynchronous routingenhanced mac protocol in multi-hop wireless networks[END_REF] and [START_REF] Du | Using Routing Information to Improve Mac Performance in Multi-hop Wireless Networks[END_REF], the authors change the MAC protocol to incorporate control frames, in order to increase network performance. In the same way, authors in [START_REF] Xu | Unnecessary competition in multi-hop wireless networks[END_REF] investigate how the competition for channel access between neighbor nodes impact the network overall performance. Thus the same authors propose in [START_REF] Xu | Towards analysis of intra-flow contention in multi-hop wireless networks[END_REF] a methodology that defines a controller node that synchronizes all of its neighbors, in order to reduce the competition for the channel access (which doe not cope with the original IEEE 802.11 DCF mechanism). In [START_REF] Jiang | A distributed csma algorithm for throughput and utility maximization in wireless networks[END_REF], authors modify the CSMA algorithm to overcome such issues. Moreover, in [START_REF] Toh | March: a medium access control protocol for multihop wireless ad hoc networks[END_REF] the fundamental behavior of the RTS/CTS mechanism is modified, in order to be used under certain conditions (after a collision, for example). The proposed solutions, in these mentioned works, however, do not cope with the original behavior of the IEEE 802.11 DCF mechanisms, and, therefore, we can not apply them to our scenarios.

To summarize, most of the analytical studies on IEEE 802.11 are devoted to either cell networks, or multi-hop networks with single-hop flows. Considering the few works dealing with multi-hop flows, they tend to make assumptions that significantly deviate from some of the fundamental properties arising in 802.11 chains, and thus they may not be accurate when applied to realistic scenarios. In the next section, we present our Chapter 4

Modeling Framework and its applications

Introduction: general framework

In this chapter, we present our hierarchical modeling framework which is used to estimate the performance of multi-hop wireless chain scenarios. In the following sub-sections, we apply the general modeling to chains, with two or three nodes. Then we discuss all the particularities inherent to each of the presented chains. The idea is to provide the basis under which we expect to develop our model to general cases of multi-hop chains. We describe the general lines of our model, without providing equations nor values. These equations will be presented in the following sub-sections of the chapter, when we deeply analyze the chains with two and three nodes.

Note that a list with all variables used along this thesis is placed in the List of Notations section at page 19 in order to ease the readiness of such work.

Our model consists of a two-level approach split in:

• a global high-level queueing network model;

• several local low-level Markov chain models.

The high-level models the chain topology while the low-level models each node of a chain. Our model computes the performance of the chain in terms of attained throughput and datagram losses, among other parameters.

In order to explain our proposed model, let us first consider the chain, depicted in Figure 4.1, composed of N + 1 nodes (labeled from 1 to N + 1). In this example, datagrams are generated and injected at border node 1 and are conveyed up to the opposite border node N + 1 through all the relay nodes between them. The datagrams generation rate Λ defines the current level of workload of the chain. From now on, a flow is referred to the traffic generated at one border node and conveyed within the nodes of the chain towards to the opposite border node of the chain. In this chapter, we consider only 1 flow traveling within the chain. In the next chapter, 2 flows are considered. the freezing periods. Note that when a node transmits i) it prevents any neighbor (within its carrier sense range) from transmitting and ii) causes any ongoing backoff within carrier sense range to freeze. These periods are directly dependent on the transmissions of neighbor nodes, and thus the time required for a node to transmit may vary significantly according to the workload level of its neighbors. This dependence among nodes makes very hard to evaluate the performance of the system. The originality of our model lies in including the freezing periods in the service time of a datagram. By doing so, the model bypasses the complexity of representing the strong synchronization between different nodes of the system.

It becomes much more simple to evaluate the system performance by incorporating the freezing time of a node on the service time definition. The reason is that we can decouple the queues of the global model, which is crucial to scale up our model to large scenarios.

In order to solve our queueing system, we first decompose it into isolated queues as illustrated in Figure 4.4. Although the open queueing network depicted in Figure 4.2 could be easily solved without the decomposition step for small chains (with 2 or 3 nodes), we remind that the goal is to extend our approach to complex and realistic scenarios, with larger chains and more than one flow. Therefore, by decomposing it into single queues, the methodology should make the extension easier for these future scenarios.

The datagram generation at the source node (node 1) is a Poisson process, which is a classical behavior in several papers [START_REF] Bianchi | Performance analysis of the IEEE 802.11 distributed coordination function[END_REF][START_REF] Garetto | Modeling per-flow throughput and capturing starvation in CSMA multi-hop wireless networks[END_REF]. The first assumption that we . . . 7 unsuccessful frame transmissions buffer full 7 unsuccessful frame transmissions buffer full 7 unsuccessful frame transmissions buffer full make for this decomposition consists in assuming that the arrival process at each of the subsequent queues of the network is also a Poisson process. This results in several isolated M/G/1/K queues. We know that the output X 1 of queue 1 (which corresponds to the input λ 2 of queue 2) in our original system is not Poisson (with the same reasoning for all other queues). However, our results show that this assumption does not greatly impact the overall performance of our model while it simplifies its solution (refer to Section 5.3.4).

μ 1 μ 2 μ N λ N λ 2 λ 1 = Λ K 2 K N K 1
The second assumption that we make is to consider that the service time of each queue is exponentially distributed. This assumption is intended to make our model simpler and extendable. The resulting queues are M/M/1/K and are easily solved, provided that we know the service rate μ i (yet to be defined). Finally all the required performance parameters of the network can be derived from the well known closed-form formulas of the M/M/1/K queue (for a more detailed analysis in performance evaluation, refer to Chapter 6 in [START_REF] Baynat | Théorie des files d'attente: Des chaînes de Markov aux réseaux à forme produit[END_REF]).

The global model presented so far and the associated performance parameters (like for instance, the throughput) derived from it still depend on the value of the service rate μ i for each queue i, which remains to be determined. This parameter is estimated by the local low-level models. We associate a Continuous-Time Markov Chain (CTMC) to each queue i of the network, to estimate its service time S i . This CTMC precisely describes the succession of the different states a node has to go through in order to transmit a datagram over the wireless channel. For instance, we know that it starts with a DIFS time and follows with the decrementation of the backoff, with occasional freezing periods due to a sensed busy medium, until the frame is corrected transmitted or discarded (refer to Chapter 2 for a more detailed discussion over the IEEE 802.11 DCF mechanisms).

We know that the time spent on the backoff freezing depends on the transmissions of neighbor nodes. The throughput of such neighbors is a performance parameter provided by the global model. In the following sections, we describe in more details this process for two scenarios.

In Section 4.2 we apply our model framework for a toy example of a chain composed by 2 nodes. Chapter 4.3 describes the modeling approach for a scenario with a chain composed by 3 nodes.

Scenario with 2 nodes and 1 flow

In order to help in understanding the proposed model, we first apply it to the most simple chain example, composed of only two nodes. Figure 5.1 depicts the proposed scenario.

Workload generated at node 1 1 2

Transmission range of node 1 We are aware that this is a toy example and such a simple scenario can be easily solved by numerical calculations using the IEEE 802.11 DCF mechanisms detailed in Section 2.1. Our goal is, however, to provide an insight into the modeling framework possibilities. In Section 4.3, we discuss a more complex scenario, but we show that the modeling process does not vary much.

The link between the two nodes is not ideal (the physical layer is non-perfect). We remind that, throughout this work, we refer to the BER (Bit-error rate) as the rate at which bits are incorrectly received at a node due to failures in propagation. Note that we can apply any BER model to our framework, in order to represent a particular scenario we may be interested in.

Global model

In this simple case, we have N = 1, where N is the number of nodes transmitting datagrams. Since only node 1 transmits datagrams (node 2 sends only frame acknowl-edgements), we associate our scenario with a simple queue as depicted in Figure 4.7. We remind that, according to our assumptions given in the previous section, we can solve this queue as a classical M/M/1/K. We associate to this queue a service rate μ 1 , which corresponds to the inverse of the service time S 1 , as mentioned in the previous section. S 1 exactly corresponds to the time separating the instant when a datagram is ready to be sent over the radio channel from the moment when it is acknowledged or discarded. The obtention of S 1 and μ 1 is performed with the local model, which is solved subsequently. We also associate a finite capacity K 1 to the queue, that matches the buffer size of the wireless card. It means that any datagram arriving whenever the buffer is full with K 1 datagrams is discarded. Note that we consider, in all the studied scenarios, that there is no datagram discarded on the destination node (node 2 in this first scenario) as, usually, the time required to process an arriving datagram is smaller than the time required to receive it on the wireless interface card. Therefore, on the destination node, an arriving and correctly decoded datagram is transferred to the application layer before the arrival of another following datagram.

K 1 X i μ 1 λ 1 = Λ p f 1 7 1 -p f 1 7
Therefore, the output throughput of the queue is simply:

X 1 = μ 1 (1 -π 1 (0)) = λ 1 (1 -π 1 (K 1 )) (4.1)
where π 1 (n) is the probability of having n customers in the M/M/1/K queue of node 1.

The chain throughput is simply the number of datagrams correctly transmitted:

X out = X 1 (1 -p f 1 7 ) (4.2)
where p f 1 is the frame error probability on the frames sent by node 1 to node 2 (which is described more precisely in next section).

Equation (4.2) defines the output of the system (in number of datagrams correctly sent per units of time) that exactly corresponds to the output of the queue 1 decreased by the proportions of datagrams rejected due to excessive frame retransmissions.

We do not extend our analysis for all the performance parameters of a M/M/1/K queue, since the objective is only to give an insight in the modeling development. Section 4.3 deals with a more complex chain and makes a more extensive analysis on such performance parameters.

Local model

We now focus on the missing parameter μ 1 for the global model. We propose a Continuous-Time Markov Chain (CTMC) that estimates mean the service time S 1 of the node 1, whose inverse is exactly μ 1 , as depicted in Figure 4.8. For the sake of simplicity and considering that, for this toy example, we have only one queue, we have removed the indexes of the variables used in the CTMC in this subsection (for instance, μ 1 becomes μ).

This CTMC precisely describes the succession of the different states a node has to go through in order to transmit a datagram over the wireless channel using the IEEE 802.11 DCF mechanisms. It is composed of seven "lines", each one corresponding to a given stage k of the backoff and modeling the backoff time preceding the k-th transmission of a given datagram (provided the k -1 preceding transmissions of the datagram were in error). Recall that a maximum of 7 unsuccessful transmissions is considered for a same frame associated to a datagram, after which the datagram is discarded.

After starting a transmission with a DIFS, the system goes to the backoff mechanism, until it reaches the transmission state "T". Following, it goes either to the "end of service" state after a successful transmission with a rate

1-p f T . Otherwise, in case of a 1,W1-1 1,W1-2 1,1 1,0 T α α α α pf T 1st backoff stage DIFS 1 DIF S×W1 1 DIF S×W1 2,W2-1 2,W2-2 2,1 2,0 T α α α α pf T 2nd backoff stage DIFS 1 DIF S×W2 1 DIF S×W2 7,W7-1 7,W7-2 7,1 7,0 T α α α α 7th backoff stage DIFS 1 DIF S×W7 1 DIF S×W7

End of

Serv. T . Remind that p f is the frame error probability and T is the time corresponding to the transmission of a frame plus the defer time SIFS plus a timeout value corresponding to the duration of an acknowledgment.

1-pf T 1-pf T 1 T
Whenever leaving "DIFS" state at any k-th backoff stage, the process randomly chooses any state {k, j} or the transmission state with a uniform probability equal to 1 W k . From any state {k, j}, we reach state {k, j -1} (or transmission state if j = 0) with a rate α, whose inverse is a slot time duration and is fixed by IEEE 802.11 DCF specifications. Note that there is no freezing period in this chain, since only node 1 transmits datagrams, so there is no possibility that the system remains in a certain state {k, j} for more than one slot time (due to transmissions in neighbor nodes) As a result, almost all of the parameters of this CTMC come directly from IEEE 802.11 specifications, except the frame error probability p f . This probability is the result of frame losses due to collisions and to incorrect decoding at the destination node.

The frame collision probability is denoted as p coll and the probability of an unsuccessful decoding due exclusively to BER is denoted as p BER . In this scenario, we neglect any collision that might occur (p coll = 0). In order to a collision take place, at least 2 nodes must finish their backoff at the same time, which is a rare event in our scenario. We consider, however, that frames can be lost due to BER, given that the links are not perfect. The probability p BER is obtained according to wireless card specifications as described in Section 2.4. Therefore, we just consider that, whenever frames collisions are neglected, we have:

p f = p BER (4.3)
Finally, from the CTMC, the service time S corresponds to the mean time that is necessary to reach the state "end of service", starting from the first "DIFS" state of the Markov chain, and is given by:

S = 1 μ = t 1 + p f × (t 2 + p f × (t 3 + ... + p f × t 7 )) (4.4)
where t k corresponds to the mean time spent by the process in "line" k of the CTMC:

t k = DIFS + W k 2 × t slot + T (4.5)
where t slot is simply the duration of a slot time according to the IEEE 802.

Scenario with 3 nodes and 1 flow

From this section until the end of the chapter, we consider the case of a wireless multi-hop chain with three nodes (labeled from 1 to 3). With respect to the system characteristics in Section 2.4, all nodes are in carrier sense range of each other, which means the absence of any hidden station.

The generated traffic (according to a Poisson process), with rate Λ, is conveyed from node 1 towards node 3, by using node 2 as a relay node. The scenario is depicted in datagrams from node 1. Therefore, at certain cases, relay node may go into starvation, even if the first node of the chain is in saturation, which greatly impacts the chain performance.

In the following subsections we describe how the global and local models are suited for this scenario. Moreover, we detail the solution obtained through a fixed-point iterative algorithm and show the obtained results.

Global model

Our 3-nodes scenario is associated with the queueing network depicted in Figure 4.11.

In this present case, we have N=2 queues, since we have only two nodes transmitting datagrams (node 3 only sends acknowledgement frames).

7 unsuccessful frame transmissions buffer full The queueing network exactly matches the topology of our chain, since node 1 trans-mits datagrams to node 2, which conveys those correctly received up to node 3. The capacity of each queue i is denoted K i (with i = 1, 2) and the service rate is μ i . Datagrams are rejected when they arrive at full queue ("buffer full" in Figure 4.11) or due to excessive retransmissions of the associated frames ("7 unsuccessful frame transmissions")

K 1 K 2 ⎫ ⎬ ⎭ datagram losses ⎫ ⎬ ⎭ successful transmissions μ 2 Λ μ 1
We remind that μ i corresponds, by definition, to the inverse of the mean service time S i of the same queue (time separating the moment when a datagram is ready to be sent over the channel radio and the instant when it is finally acknowledged or discarded).

The main difference between this scenario and the previous one with only two nodes (Section 4.2) is the presence of freezing periods in the service time due to transmissions of the neighbor node.

As explained before, the freezing time is included in the definition of the service of a datagram. This definition makes the solution of such network much more simple, by decoupling the queues of the global model.

Before solving our queueing system, we first decompose it into two isolated M/M/1/K queues as illustrated in Figure 4.12. Those isolated queues represent the same behavior as the non-decomposed queueing model, with the first leaving arrows of each queue indicating clients (datagrams) rejected due to a full buffer.

μ 1 μ 2 p f 1 7 p f 2 7 1 -p f 1 7 1 -p f 2 7 X 1 X 2 λ 2 = X 1 (1 -p f 1 7 ) Λ = λ 1 K 1 K 2 Figure 4
.12: Decomposed global model for a chain with 3 nodes and 1 flow.

The performance of the queues can be expressed according to the following relations.

The output throughput at each node i (i = 1, 2) is:

X i = μ i (1 -π i (0)) = λ i (1 -π i (K i )) (4.6)
where π i (n) is the probability of having n customers in the i-th M/M/1/K isolated queue. From relation (4.6) we can then easily derive the number of datagrams that are correctly transmitted to node 2 from node 1:

λ 2 = X 1 (1 -p f 1 7 ) (4.7)
We remind that the arrivals at node 1 are the arrivals at the chain itself λ 1 = Λ.

The mean number of customers in queue i (i = 1, 2), which corresponds to the mean number of datagrams waiting to be transmitted (or in transmission) at node i is:

Q i = K i n=1 nπ i (n) (4.8)
From Little's Law [START_REF] John | A proof for the queuing formula: L = w[END_REF], the mean sojourn time R i of an admitted customer in queue i (i = 1, 2) can be easily derived. This duration corresponds to the mean time that a datagram, which is not lost due to buffer overflow, stays in node i before transmission to node i + 1 or discard due to excessive frame transmission.

R i = Q i X i (4.9)
Furthermore, the utilization of a node i, corresponding to the proportion of time in which queue i (i = 1, 2) has at least one datagram to send, is simply:

U i = 1 -π i (0) (4.10)
And from PASTA theorem [START_REF] Wolff | Poisson arrivals see time averages[END_REF], we can obtain the probability that a datagram is rejected because the buffer of the destination node is full at its arrival instant:

p ri = π i (K i ) (4.11)
From all the previous relations, we can express the overall chain performance, which will be used to validate our model in Subsection 5.3.4. The chain output throughput, X out , corresponding to the mean number of datagrams correctly received at the destination node per unit of time, is a function of the output throughput at node 2 as:

X out = X 2 (1 -p f 7 2 ) (4.12)
The chain rejection probability, p rout , defined as the probability that a datagram is rejected due to a full buffer at its arrival instant at any node of the chain or due to excessive frame retransmissions, is given by:

p rout = Λ -X out Λ (4.13)
And finally, the end-to-end delay of a datagram is simply approximated as the sum of the sojourn times at each node i of the chain.

R out ∼ = R 1 + R 2 (4.14)
This latter approximation is possible since we only consider the end-to-end delay of the datagrams that are successfully conveyed through the chain. We can, therefore, use the sum of the times spent in each of the nodes by such datagrams.

Local model

We associate to each queue of our network the Continuous-Time Markov Chain (CTMC) depicted in Figure 4.13, in order to estimate the service rate μ i (i = 1, 2).

freeze

1,W1-1 1,W1-2 1,1 1,0 T β i γ i α i α i α i α i p f i T 1st backoff stage DIFS 1 DIF S×W1 1 DIF S×W1 freeze freeze freeze freeze 2,W2-1 2,W2-2 2,1 2,0 T β i α i α i α i α i p f i T γ i 2nd backoff stage DIFS 1 DIF S×W2 1 DIF S×W2 freeze freeze freeze freeze 7,W7-1 7,W7-2 7,1 7,0 T β i α i α i α i α i γ i 7th backoff stage DIFS 1 DIF S×W7 1 DIF S×W7
freeze freeze freeze Let us remind that there is a CTMC (with different parameters) associated with each transmitting node i. Note that the main difference between this CTMC and the previous one described for the 2-nodes scenario is the presence of the freezing periods.

β i γ i β i γ i β i γ i β i γ i β i γ i β i γ i β i γ i β i γ i β i γ i End of Serv. 1-p f i T 1-p f i T 1 T
As defined for the global model, p f i is the frame error probability, which depends on the frame collision probability (p colli ) and the frame error probability due to BER (p BERi ), for any node i (i = 1, 2). Since we neglect any collisions that might occur (p colli = 0), from relation (4.3) we obtains its value as:

p f i = p BERi (4.15)
Remind that p BERi is defined according to the wireless card manufacturers specifications, as described in Section 2.4.

State T of the CTMC is the time corresponding to the transmission of a frame plus the defer time SIFS plus a timeout value corresponding to the duration of an acknowledgment. A state {k, j} corresponds to the k-th stage of the backoff (i.e., the k-th transmission attempt of the datagram) with a backoff equal to j (j

∈ [0, W k -1]).
Exiting the k-th "DIFS" state, the process randomly chooses any state {k, j} or the transmission state with a uniform probability (equal to 1 W k ). From any state {k, j}, we can either reach state {k, j -1} (or transmission state if j = 0) if the canal has remained idle during the current slot time, or reach a "freeze" state if the canal has been sensed busy. The corresponding rates are denoted α i and β i . α i is simply the inverse of a slot time duration and is fixed by IEEE 802.11 specifications. The inverse of β i corresponds to the time separating two backoff freezing, provided that the node is in backoff. The value of β i , for any node i, depends on the transmission rates (throughput) of the neighbor nodes, since their transmissions cause the backoff countdown to freeze. In our model, the throughput is a performance parameter provided by the upper level. The rate out of any "freeze" state is γ i , whose inverse corresponds to the freezing duration of the node plus a DIFS time. The duration of the freezing value will be deeper explained in the following sections.

As a result, most of the parameters of this CTMC come directly from IEEE 802.11 specifications, except the frame error probability p f i and the rate β i . The frame error probability can be easily estimated from the BER (we remind that no collisions are considered in this scenario). Estimating the last remaining parameter β i is much more difficult and we now turn our attention to it.

As explained before, it is easier to consider the inverse of parameter β i which corresponds to the mean time between two successive backoff freezing (provided the node is in backoff). This quantity is related to the mean number of freezing of the backoff of the considered node i, denoted as np i and the mean backoff duration B i for a given frame. This is illustrated in Figure 4.14, where the hashed areas correspond to freezing periods of the backoff. From Figure 4.14 we can see that: the backoff is split in two parts: one part before the freezing period and one part after the freezing period and before transmission. In average, we approximate each part as 1 2 B i . With this information, we can count the number of parts that separate two successive backoff freezing (provided the node is in backoff) and determine the value of 1/β i . In this first case, it is simply:

T T T time 1 β i 1 2 1 2 1 2 1 2 T T time 1 β i 2 β i = Bi T 1 β i 1 βi = Bi T T time T 1 3 1 3 1 3 1 3 1 3 1 3 1 β i 1 β i 1 β i 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 3 βi = Bi
1 β i = 1 2 B i + 1 2 B i ⇒ 1 β i = B i .
II. If we have exactly two pauses per backoff (second example of the figure), then we have the backoff divided in three parts (one before the first freezing, one between the two freezings and one after the second freezing and before transmission). Each of them lasts, in average, 1 3 B i . Therefore, with two pauses, there will be a first time 1/β i equal to 1 part ( 1 3 B i , the first occurrence in the example) and a second time 1/β i equal to 2 parts ( 2 3 B i , the second occurrence). Therefore, we can simply express that 1

β i + 1 β i = 1 3 B i + 2 3 B i ⇒ 2 β i = B i .
III. If each backoff is paused exactly three times (third example in the figure), then the backoff is divided in 4 parts of mean duration 1 4 B i each. Repeatdly, we have three occurrences of 1/β i , whose durations are:

1 β i + 1 β i + 1 β i = 1 4 B i + 1 4 B i + 2 4 B i ⇒ 3 β i = B i
We can easily extend these results to an mean number of pauses in the backoff, np i , and obtain the intuitive following relation:

1 β i = B i np i (4.16)
It turns out that parameter β i can be directly obtained from the estimation of the mean number of backoff freezing and the mean backoff duration. This last parameter can be easily estimated from the following mean:

B i = W 1 2 f 1,i + (W 1 +W 2 ) 2 f 2,i + • • • + (W 1 +W 2 +•••+W 7 ) 2 f 7,i f i (4.17)
where W k is the size of the contention window at the k-th frame transmission attempt by assuming an initial W 1 of 31 and a maximal W 7 of 1023 (see Section 2.4):

W k = min(2 4+k -1, 1023) (4.18)
and f k,i is the probability that the transmission of a datagram at node i requires exactly k frames. This probability can be derived from the frame error probability as:

f k,i = p f i k-1 (1 -p f i ) for k ≤ 6 and f 7,i = p f i 6 (4.19)
Finally, f i is the mean number of frame (re)transmissions per datagram at node i:

f i = 7 k=1 k f k,i (4.20)
Now it remains to estimate the mean number of pauses in the backoff of a node.

Let us remind that the backoff of a given node i is paused whenever any node j in the carrier sense range of node i transmits. Now going back to our scenario (with 3 nodes, but where only nodes 1 and 2 transmit datagrams), let us consider the backoff of node 1.

Figure 6.5 illustrates the successive transmissions of node 1 in a saturated case, i.e., when node 1 has always datagrams to transmit. In this case, between two frame transmissions there is always a backoff that is paused by transmissions of node 2. The mean number of pauses of each backoff is thus equal to the mean number of frame transmissions of node 2 in between two conscutive frame transmissions of node 1. If we denote by F i the mean number of frames transmitted by node i by unit of time (i = 1, 2), we thus have:

np 1 = F 2 F 1 , np 2 = F 1 F 2 (4.21) B 1 B 1 B 1 T 1 T 2 T 2 B 1 B 1 B 1 T 1 T 2 T 2 T 2 B 1 T 1 time Figure 4
.15: Relation between transmissions of node 2 and backoff freezing of node 1 in a saturated case.

Note that the frame throughput F i of node i is a representation of the performance at the link layer, while the corresponding datagram throughput X i of the global model is associated with the network layer.

The frame throughputs that appear in this last relation can easily be derived from the datagram throughputs calculated from the global queueing model (relation (4.6))

and the mean number of frame transmissions per datagram as:

F i = X i f i (4.22)
We now consider the general case where nodes are not saturated, as illustrated in Figure 6.6, with the transmissions of node 1.

B 1 B 1 T 1 T 2 T 2 B 1 B 1 T 1 T 2 T 2 T 2 B 1 T 1 time x 1 y 1 S 1 T Figure 4
.16: Relation between transmissions of node 2 and backoff freezing of node 1 in a non-saturated case.

We describe the events for node 1 in the previous Figure, although the reasoning can be also applied to node 2. Between two transmissions, there may occur an idle time (of mean duration x 1 on the figure) before the beginning of the backoff. Some transmissions of node 2 (resp. node 1) freeze the backoff of node 1 (resp. 2), whereas others do not, because they happen during idle periods of node 1 (resp. 2). We define as the corrective factor δ i the proportion of time any node i remains idle between two successive frame transmissions. Its value is simply:

δ i = y i x i + y i (4.23)
Then, the mean number of pauses in the backoff of node i has thus to be adjusted with the corrective factor δ i as:

np 1 = F 2 F 1 × δ 1 , np 2 = F 1 F 2 × δ 2 (4.24)
The final question relies on estimating the corrective factors δ i . Let us first express the utilization U i of queue i with notations of Figure 6.6:

U i = S i S i + x i (4.25)
and use it in the expression of the corrective factor:

δ i = y i x i + y i = S i -T S i 1-U i U i + S i -T (4.26)
Finally, by using together previous equations, we get the following expression for the missing parameters β i :

β i = X j f j X i f i δ i B i (4.27)
with the convention that j = 2 if i = 1, and j = 1 if i = 2. Now that all the parameters of the CTMC have been estimated, we can use it to get a fair estimation of the service rate μ i of the associated M/M/1/K for any queue i.

The inverse of this rate corresponds to the mean time required to reach the state "end of service", starting from the first "DIFS" state of the Markov chain, and is given by:

S i = 1 μ i = t 1,i + p f i × (t 2,i + p f i × (t 3,i + ... + p f i × t 7,i )) (4.28)
where t k,i corresponds to the mean time spent by the process in "line" k of the CTMC:

t k,i = DIFS + CW k 2 × r i + T (4.29)
and r i is the mean time spent in any pair of loop states ({k, j}, {f reeze}) at node i:

r i = 1 α i × 1 + β i γ i (4.30)

Fixed-point solution of the model

From the previous subsections, we see, in one hand, how the global model provides the performance parameters for a 3-nodes chain, once the service rate μ i is well furnished.

Those performance parameters defined in Section 4. On the other hand, the value of the service rate μ i for each queue i is obtained by solving a Continuous-Time Markov Chain, with the condition that the values of X i and

U i are provided.
It is then natural to use a fixed-point iteration to obtain the values of the desired parameters, as described in Algorithm 1. We perform each step of the algorithm for both queues before moving up to the following step. Whenever the relative error (represented by error i ) between the current value of μ i , compared to its value at the previous iteration, is greater than a convergence criteria , the algorithm continues to perform. The algorithm starts with the initialization of the service rate μ i of queue i (i = 1, 2) by setting a non-absurd value to it. Then it performs the different steps (lines 2-12) until the convergence criteria is reached. Note that the maximum value of the vector error i is used to check if the algorithm has converged. It is natural to check it for every queue, since both queues do not reach to their convergence necessarily at the same iteration.

Once the model has converged, we can obtain the chain performance in terms of the chain throughput X out (relation (4.12)), the datagram rejection probability p rout (relation (4.13)) and the end-to-end delay R out (relation (4.14)).

Numerical Results

According to the parameters defined in Section 2.4, we simulate the scenario of the chain with 3 nodes and 1 flow. Nodes 1 and 3 are fixed, 500m away from each other. The relay node can be positioned in several spots within the interval [110m,390m] away from node 1.

We compare the results of our model with those delivered by simulation, for different levels of workload. Each result of the simulation is an mean on at least 80,000 datagrams correctly received at the destination. In our simulations, datagrams are generated by the source (node 1) according to a Poisson process. For both queues we set the buffer size to 50 datagrams. We remind that no RTC/CTS handshake mechanism is used. For a workload of 6Mb/s, the relative error between the results is less than 10% for the worst cases and typically less than 5%. For the relay node, the mean values of backoff freezing substantially increase when this node is distant from the destination (node 3). This is due to losses arising with non-perfect channel conditions, which increase with the distance. The necessary retransmissions yield greater contention windows, which increase the probability that a neighbor node transmits and freezes the backoff decrement. For the source node, this behavior is not observed, despite the elongation of the mean backoff duration due to losses. If few datagrams are correctly transmitted from the source, clearly the relay node will very likely go to starvation. Therefore, it will not be able to freeze the backoff decrement at the source node. This behavior shows that there is no symmetry between the source and relay nodes, which may not be obvious at a first glance.

In the following figures, we show the performance of our model, regarding the mean throughput of a node, datagram rejection probability by buffer overflows and mean endto-end delay, for each node. For the workload of 3Mb/s (Figure 4.19(a)), depending on the actual distance be-tween nodes 1 and 2, node 1 can be in saturation. We clearly see that the relative error between the results of our model and those from simulation is very low (around 5%). In a wide range of relay positions (between 150m and 350m), we see that the system is capable of conveying the entire workload. On the other hand, when source and relay nodes are close, the throughput of node 2 decreases due to a high BER on the transmissions between nodes 2 and 3 and the network can not cope with the workload.

In the other extreme position (source and relay nodes are distant), due to a high BER on the transmissions between nodes 1 and 2, there are more retransmissions for node 1 implying a service time elongation and buffer overflows in node 1. Figure 4.19(b) shows that, when the system workload is set to 6Mb/s, the best performance of the system are obtained in several points around the middle position for node 2, where the effect of BER is less significant. With this workload, the system is not capable of conveying all datagrams and is in saturation (buffer overflows). with the ones obtained by simulation, for the same levels of workload. The accuracy of our model is clearly seen, since the relative error, when comparing to the simulation results, remains mainly low for both cases (less than 5%). The rejection probability for the relay node is significantly more important when it is close to source node. This is due to the high rate of arriving datagrams from node 1 and to the frame error probability between nodes 2 and 3 due to a high BER. These losses increase the frame retransmissions and the mean service time of a datagram for node 2, which leads to a higher buffer occupation. Regarding the source node, it also loses several datagrams by buffer overflow whenever the BER is important. Moreover, for the workload of 6Mb/s, the chain is not capable of conveying the entire workload, and datagrams are rejected by the source node. The relative errors between our model results and those from simulation are low, ranging from 3% (best cases) up to 13% (worst cases). As expected, these values increase significantly when the BER is more important (long distances between nodes), leading to values up to 12 times larger when compared to the best cases around the middle position.

We now show the relative errors of the chain throughput for several workloads, ranging from 0.2Mb/s to 5Mb/s and with different positions for the relay node, in the range of [110m,390m] away from the source node. errors. For more than 96% of the points, the relative errors are smaller than 10%, which implies a good accuracy of our model. mean <5% 5-10% 10-15% >15% 4.54% 60.03% 36.51% 3.32% 0.14% Table 4.1: Overall accuracy of the model for the throughput of the chain with 3 nodes and 1 flow. Given the accuracy of our model, we believe it can be used as a prediction tool to forecast the flow performance for different positions of the relay node. Figure 4.23 shows the actual values of the chain throughput delivered by our model, for different values of the system workload (varying from 0.2Mb/s to 5Mb/s) and for different positions of the relay node. We see that, as the workload increases, the output of the chain copes with it until a limit is reached. However, from this limit on, even for greater workloads, the throughput delivered by the chain will not increase. It is also important to note the saturation in the overall throughput, when the relay node is 130m-150m away from the source. These scenarios present a performance degradation when the workload exceeds a certain limit (around 3.2Mb/s) and the throughput of the chain decreases with an increase of the workload. This behavior can be aggravated in other scenarios, and a prediction tool is thus of high importance, in order to prevent the system from such a performance degradation. This performance collapse due to an increase in the system workload is discussed in details in [ANB + 12].

Conclusion

In this chapter, we presented the basics of our modeling framework for 2 simple scenarios, composed of 2 or 3 nodes and 1 flow, where all nodes are within each other carrier sense range. The adopted methodology, corresponding to a high and a low level models, allows us to easily derive the performance of the chain and the behavior of the nodes, respectively.

The results presented for both scenarios provided fairly accurate results for the relative error between the throughput delivered by our model and that delivered by simulation. Similar results were also obtained in relation with the datagram rejection probability and the end-to-end delay. Moreover, we have shown how our model can be exploited in order to estimate the optimal node positioning, as to obtain the best throughput rate for a scenario with 3 nodes and 1 flow.

In the following chapter, we extend our model, as to include scenarios with 2 flows traveling in opposite directions. We show that our model does not increase much on its complexity to incorporate such new feature.

Chapter 5

Extension to two flows

Introduction

In the previous chapter, we describe our modeling framework and we apply it for scenarios composed of 2 or 3 nodes, but limited to a single flow in the network. In this chapter, we extend our model to deal with 2 flows. The existence of competing flows, which share the chain resources, presents interesting behaviors, e.g., the losses of datagrams even for very light workloads.

Let us recall that our model is composed of 2 levels: i) a global high-level queueing network model, representing the chain topology and ii) several local low-level Markov chains model, describing the behavior of each node in the chain. The queueing network model provides the chain performance for each flow in terms of attained throughput, datagram losses, etc., while the Markovian models provide the capacity of each node.

In the following section, we describe how our model can be implemented for a simple scenario composed of only 2 nodes and 2 opposite flows. With this example, we have a better understanding on the modeling of scenarios with more than one flow. Following, we extend our model for a larger chain, composed of 3 nodes and 2 opposite flows, in order to evaluate the performance of the network in the presence of a relay node. 86

Scenario with two nodes and two flows

Figure 5.1 depicts the proposed scenario, corresponding of a chain with 2 nodes and 2 opposite flows. As for the previous scenarios presented in previous chapter, the traffic is generated according to a Poisson process at both nodes. Moreover, the link between nodes is not perfect (bits can be altered) and is associated to a Bit-Error Rate (BER).

Global model

As described before, we have a global queueing network model that matches the chain topology. In this case, we have 2 flows that are generated independently from each other.

We associate with our scenario the 2 separated queues as depicted in Figure 5.2. We associate to each queue i an exponential service rate μ i , which corresponds to the inverse of the mean service time S i (time separating the instant when a node is ready to send a datagram over the radio channel from the moment when this datagram is acknowledged by the other node or discarded due to excessive frame retransmissions).

K1 K2 λ 1 X 1 X 2 μ 1 μ 2 p f 7 1 1 -p f 7 1 p f 7 2 1 -p f 7 2 λ 2
By assuming that the service rate is exponential, we keep the model consistent with the same modeling assumption given previously in Chapter 4. Moreover, we assume that the buffers of the nodes (which are represented as the queue capacity) are not infinite and datagrams are discarded whenever they arrive and the buffer is full. Therefore, we can solve those queues as classical M/M/1/K.

The chain workload is simply defined as Λ = λ 1 + λ 2 .

The output throughput of each queue i is simply the service rate of the queue, whenever it is not idle:

X i = μ i (1 -π i (0)) , i = 1, 2 (5.1)
where π i (n) is the probability of having n customers in the M/M/1/K queue.

The chain throughput is, regardless of the specific flow under consideration:

X out = 2 i=1 X i (1 -p f i 7 ) (5.2)
Note that for this simple scenario, we do not have a relay node, so the throughput of the chain is just the sum of the throughputs of each node. We restrict our analysis to this parameter, since the goal of this section is only to give the insights of the scenario with 2 flows modeling. In the following sections, we analyze the results of our model for other performance parameters (e.g., datagrams rejection probability).

Local model

To each queue i of our global model, we associate a Continuous-Time Markov Chain (CTMC) depicted in Figure 5.3, whose objective is to provide an estimation of the mean service time S i .

We can clearly see that this CTMC is exactly identical to the one presented in Section 4.3 (scenario with 3 nodes and 1 flow). This is due to the fact that, in this scenario, as in the one studied in Section 4.3, there are 2 transmitting nodes at each others carrier sense range. Whenever a transmission takes place, the neighbor node goes into freezing (provided it is in backoff). Furthermore, the frame loss probability remains the same. Therefore, we can associate 1 CTMC to each queue just as before.

freeze 1,W1-1 1,W1-2 1,1 1,0 T βi γi αi αi αi αi pf i T 1st backoff stage DIFS 1 DIF S×W1 1 DIF S×W1 freeze freeze freeze freeze 2,W2-1 2,W2-2 2,1 2,0 T βi αi αi αi αi pf i T γi 2nd backoff stage DIFS 1 DIF S×W2 1 DIF S×W2 freeze freeze freeze freeze 7,W7-1 7,W7-2 7,1 7,0 T βi αi αi αi αi γi 7th backoff stage DIFS 1 DIF S×W7 1 DIF S×W7 freeze freeze freeze βi γi βi γi βi γi βi γi βi γi βi γi βi γi βi γi βi γi End of Serv. 1-pf i T 1-pf i T 1 T
The CTMC describes all the necessary states a node must go through, in order to transmit a datagram. It starts with a "DIFS" until the process arrives at the state "End of Service". In this path, the process may pass through each of the 7 backoff stages, the freezing periods and the frame transmissions. We remind that for each backoff stage, there is a frame transmission associated to the current datagram.

The frame error probability p f i is defined according to the the frame error probability due to BER, p BERi (see Section 2.4 for this later values). Collisions are neglected for this scenario, then p colli = 0. Thus p f i can be expressed just as defined in relation (4.15), which we rewrite here:

p f i = p BERi (5.3)
Since almost all parameters are obtained from the IEEE 802.11 DCF specifications, we can easily obtain the mean service of a datagram from the following relation:

S i = 1 μ i = t 1,i + p f i × (t 2,i + p f i × (t 3,i + ... + p f i × t 7,i )) (5.4)
where the mean time spent by the process in "line" k (k th backoff stage) of the CTMC is represented by t k,i (see relation 4.27 in previous chapter for more details).

The value of rate β i , as for all the other parameters of the local model, can be obtained with exactly the same relations defined in Section 4.3. Again, we highlight that the only difference between this scenario with 2 nodes and 2 flows from the previous one with 3 nodes and 1 flow remains in the representation of the global model.

Fixed-point solution

The solution for this scenario is also based on the use of a fixed-point iteration, between the global and local models. The algorithm describing the steps of this solution can be found in Section 4.3 in the previous chapter.

Numerical Results

In this section, we compare the throughput results delivered by our model with those obtained through simulation, as described in Section 2.4. The distances between both nodes vary from 110m to 390m. We limit the buffer size to 50 datagrams.

We inject two flows with same levels of loads at nodes 1 and 2, and vary each of them in the range of 0.2Mb/s to 5Mb/s. That results in an aggregate workload for the entire system in the range of 0.4Mb/s to 10Mb/s. Figure 5.4 shows the relative deviation on the chain throughput, between simulation and our model.

Workload of the entire system (Mb/s) Distance between nodes 1 and 2 (meters) Once again, the results show that our modeling provides good approximations, for saturated and non-saturated scenarios. For small values of workload (from 0.2Mb/s to 2.5Mb/s at each node), the throughput relative errors are not greater than 6% and in saturated cases (workload close to 4Mb/s) the error remains low, around 5%. The mean value is just 4.43%. The overall distribution of the relative errors are shown in Table 5.1. mean <5% 5-10% 10-15% >15% 4.43% 73.93% 26.07% 0.0% 0.0% Table 5.1: Overall accuracy of the model for the throughput of the chain with 2 nodes and 2 flows.

As our model is rather accurate, we can use it to estimate the maximum throughput the chain can achieve according to the system workload and the nodes positions, as depicted in Figure 5.5. For instance, let us consider the cases where nodes are close to each other, and, therefore, the BER does not have a great impact on the performance of the system (positions typically smaller than 300m). As expected, for such a simple example, as the system workload increases, also does the output of the chain. When the output limit is achieved, the chain throughput remains insensible to any greater workload at the input. It implies that datagrams are discarded at the sources.

We note, however, that when the BER becomes important (for the greatest distances between nodes in the figure), the maximum attainable throughput of the chain is low.

We see that, when the workload is high (6.5Mb/s), the maximum throughput of the chain decreases when the distance between the 2 nodes increases and reaches a value of 2Mb/s for high values of BER.

Workload of the entire system (Mb/s) Distance between nodes 1 and 2 (meters)

Chain with three nodes and two flows

Consider now the example of the chain with 3 nodes and 2 injected flows depicted in The chain conveys 2 independent flows, each starting at any border node and traveling up to the opposite border node. This scenario is harder to model than the one described in the previous section (2 nodes and 1 flow) since the freezing periods of the backoff may result from the activity of 2 nodes (and not only 1) and relay node 2 processes 2 different flows in opposite ways.

Global model

The high-level queueing network model is made of as many queues as the number of nodes transmitting datagrams, as illustrated in Figure 5.7. The rate of datagrams injected on node 1 (resp. 3) is λ 1 (resp. λ 3 ). The resulting workload is simply Λ = λ 1 +λ 3 . According to the position of node 2 and its distance to both border nodes (which impacts the BER value), the system may present different performance for the 2 directions.

As previously, we denote by μ i the inverse of the mean service time of node i (including all necessary frame transmission times, backoff times and protocols delays), and by K i the buffer size of node i. In order to solve this queueing network, we decompose it into 3 isolated M/M/1/K queues, as depicted in Figure 5.8.

K 3 K 2 K 1 λ 1 λ 3 μ 3 μ 2 μ 1 (1 -p f 3 7 ) (1 -p f 2 7 ) (1 -p f 1 7 ) p f 1 7 p f 2 7 p f 3 7 X 1 X 2 X 3
K 1 K 2 K 3 X 1 X 2 X 3 μ 1 μ 2 μ 3 p f 2 7 1 -p f 2 7 p f 3 7 1 -p f 3 7 λ 2 = X 1 (1 -p f 1 7 ) +X 3 (1 -p f 3 7 ) λ 1 λ 3 p f 1 7 1 -p f 1 7 Figure 5
.8: Decomposed model for a chain with 3 nodes and 2 flows.

As nodes 1 and 3 are only crossed by a single flow, their parameterization is similar to the one described for node 1 in Section 4.3 (scenario with 3 nodes and 1 flow). The main difference relies on estimating the parameters of node 2, since it must deal with 2 incoming flows. Therefore, we mainly highlight the differences between this scenario and the one with 3 nodes and 1 flow. We show that our model does not require too many changes to be adapted to this new topology.

The mean output throughput at each node i is:

X i = μ i (1 -π i (0)) (5.5)
where π i (n) is the probability of having n customers in the i-th M/M/1/K isolated queue.

The difference remains in the number of correctly received datagrams at node 2:

λ 2 = X 1 (1 -p f 1 7 ) + X 3 (1 -p f 3 7 ) (5.6)
where p f i is the frame error probability on frames transmitted by node i.

The mean number of customers in queue i, which corresponds to the mean number of datagrams waiting to be transmitted at node i is:

Q i = K i n=1 nπ i (n) (5.7)
As in previous chapter, from Little's Law [START_REF] John | A proof for the queuing formula: L = w[END_REF], we derive the mean sojourn time R i of an admitted customer in queue i.

R i = Q i X i (5.8)
The utilization of each node is:

U i = 1 -π i (0) (5.9)
And from PASTA theorem [START_REF] Wolff | Poisson arrivals see time averages[END_REF], the probability of rejecting a datagram due to a full buffer node i at its arrival instant is:

p ri = π i (K i ) (5.10)
The overall mean chain throughput is simply the mean number of datagrams correctly sent by node 2 per unit of time, with no regard to their destination (node 1 or 3).

X out = X 2 (1 -p f 2 7 ) (5.11)
The chain rejection probability, p rout , can be represented just as the proportion of datagrams that were rejected due to full buffer or to excessive frame retransmissions:

p rout = Λ -X out Λ
(5.12)

Local model

With the use of the CTMC proposed in the previous chapter (see Figure 4.13), we can estimate the values of the rate μ i , in order to parameterize the global model. In order to solve the CTMC, we calculate the mean backoff time duration per datagram, as follows:

B i = W 1 2 f 1,i + (W 1 +W 2 ) 2 f 2,i + • • • + (W 1 +W 2 +•••+W 7 ) 2 f 7,i f i (5.13)
where W k , varying from 31 to 1023, is the size of the contention window at the k-th frame transmission attempt (see Section 2.4) and f k,i is the probability that a datagram at node i takes exactly k frames to be transmitted:

f k,i = p f i k-1 (1 -p f i ) for k ≤ 6 and f 7,i = p f i 6 (5.14)
Its value depends on the frame error probability due to BER, p BERi (no collisions considered at this point, which means p colli = 0). We have then:

p f i = p BERi (5.15)
The mean number of frame (re)transmissions per datagram at node i:

f i = 7 k=1 kf k,i (5.16)
The first difference between this scenario and the one with 3 nodes and 1 flow concerns the fact that node 2 (relay node) has to transmit datagrams in both directions. This results in different frame error probabilities (referred to as p f 21 and p f 23 ) depending on whether the transmission is towards node 1 or node 3. In the Markov chain associated to node 2, we derive the frame error probability as follows:

p f 2 = q 21 p f 21 + q 23 p f 23 (5.17)
where q 21 (resp. q 23 ) is the probability that a frame transmission is destined to node 1 (resp. node 3). q 21 and q 23 can be estimated as the following ratio:

q 21 = X 1 (1 -p f 1 7 ) X 1 (1 -p f 1 7 ) + X 3 (1 -p f 3 7 ) (5.18) q 23 = X 3 (1 -p f 3 7 ) X 1 (1 -p f 1 7 ) + X 3 (1 -p f 3 7 ) (5.19)
Since no collisions are considered, the probabilities p f 21 and p f 23 are, respectively, the frame error probability due to BER associated to each link, p BER21 and p BER23 . Now, in order to estimate μ 2 , we first need to parameterize the Markov chain associated with node 2. The missing parameter is the mean backoff duration B 2 . Its value can be estimated in the same way as p f 2 :

B 2 = q 21 B 21 + q 23 B 23 (5.20)
where B 21 (corr. B 23 ) corresponds to the mean backoff of the datagrams to be sent from node 2 to node 1 (corr. node 3), obtained from relation (5.13)).

The second difference with the scenario with 3 nodes and 1 flow concerns the fact that, now, each node can be interrupted, during its backoff decrement, by 2 possible nodes (and not just one as with 1 flow), i.e. the 2 other nodes in the chain. Therefore, the estimation of the mean number of backoff freezing, i.e., np i , must be modified. For any node i, the value of np i corresponds to the mean number of frame transmissions of any neighbor j between 2 successive transmissions of i:

np i = j =i F j F i δ i , i = 1, 2, 3 et j = 1, 2, 3 (5.21)
where F i is the mean frame throughput, given by:

F i = X i f i (5.22)
and δ i is the corrective factor given in relation (4.26).

At last, we update the value of parameter β i as previously:

β i = X j f j X i f i δ i B i (5.23)
And we derive the service of queue i:

S i = 1 μ i = t 1,i + p f i × (t 2,i + p f i × (t 3,i + ... + p f i × t 7,i )) (5.24)
with t k,i as the mean time spent by the process at each k-th stage of the backoff:

t k,i = DIFS + W k 2 × r i + T (5.25)
where r i corresponds to the mean time spent in any pair of loop states ({k, j}, {f reeze}) at node i:

r i = 1 α i × 1 + β i γ i
(5.26)

Fixed-point solution

The solution of our model is given by a fixed-point solution as depicted in Algorithm 2.

This algorithm shows the interactions between the global model, which provides the performance parameters of the chain, and the local models, which parameterize the high-level model.

Numerical results

The simulations are performed for fixed positions of node 1 and 3 at 500m from each other. The position of the relay node varies according to several spots within the interval [110m,390m] away from node 1. We calculate the simulation points, by using a set of around 100,000 datagrams sent from the sources, and, from these points, we interpolate to obtain the surfaces we present as results.

In a first example, 2 flows of identical loads are injected at nodes 1 and 2. The workload of each flow varies from 0.2Mb/s to 5Mb/s (providing a maximum overall Figure 5.10 shows the relative errors for the datagram rejection probability due to buffer overflow or excessive frame retransmissions. As for the case of relative error for the throughput seen in Figure 5.9, the values depicted for the datagram rejection probability figure are quite accurate, with values typically under 10% for most of the cases. However, we can point out the existence of an area (labeled as "No losses"), where virtually no datagrams are lost (or the are below a threshold we set at 3% , under which they are neglected). Table 5.3 presents the distribution of the relative errors for the datagram rejection probability, with an mean value of 5.53% and 88% of the values have a relative error smaller than 10%. Figure 5.11 shows the chain throughput delivered by our model, when the overall workload corresponds to 2 flows with identical workload as previously. Naturally, we can see that for any workload, the throughput delivered by the chain is greater when the relay node is around middle positions. At these points, the influence of the BER is less important than for spots where the relay node must deal with several frame losses, which triggers successive retransmissions and longer service times. We can see that, for small values of BER (the relay node is almost equidistant from the border nodes), the chain throughput increases with the workload until the aggregated workload reaches 3.4Mb/s. At this point, the chain throughput reaches 3.1Mb/s approximately. After this point, the chain throughput decreases with the wokload, to reach a throughput of 2.2 Mb/s, which represents a performance loss of around 30% . For more extreme positions of node 2 (close to node 1 or close to node 3), we see the same evolution for the chain throughput but with much smaller values. It is important to note that our model can capture such performance collapse of the system. These results show that, for real networks, control admission policy may be needed, in order to maximize the attainable throughput that such a topology can provide. In a second example, we explore the ability of our model to cope with the chain in the presence of flows with asymmetric workload. One flow, ranging from 0.2Mb/s to 5Mb/s is injected in node 1 while a constant flow of 1Mb/s is injected at node 3. The relative throughput errors are shown in Figure 5.13. Apart from some few points, the overall error is quite good, typically around 5%. Table 5.4 gives the distribution for the throughput errors. For more than 90% of the evaluated points, the model deliver results with less than 10% of relative errors. This shows the accuracy of our modeling framework.

Workload at one border node (Mb/s) Distance between nodes 1 and 2 (meters) mean <5% 5-10% 10-15% >15% 4.26% 67.03% 24.28% 7.58% 1.1% Table 5.4: Overall accuracy of the model for the throughput of the chain with 3 nodes and 2 flows with asymmetric workloads.

Moreover, with very similar results, the relative errors for the datagram rejection probability is presented in Figure 5.13 and the error distribution in Table 5.5. mean <5% 5-10% 10-15% >15% 4.28% 67.05% 24.32% 7.54% 1.16% Table 5.5: Overall accuracy of the model for the datagram rejection probability of the chain with 3 nodes and 2 flows with asymmetric workloads.

Conclusion

In this chapter, we have presented an extension for our modeling framework, where we deal with 2 flows in opposite directions. As shown in the results section, the performance delivered by our model, compared to those from simulation are quite accurate. Furthermore, we have shown that the addition of another flow to the chain does not impact greatly the modeling complexity.

In the following chapter, we present a second extension for our model. In this case, the system must deal with the hidden node problem in a chain with 4 nodes. We show, however, that our model is still capable of coping with the chain behavior.

Chapter 6

Extension to four nodes and one flow

Introduction

In Chapter 4, we presented our modeling framework applied to a simple multi-hop network composed of 3 nodes and a single traveling flow. We extended its features in Chapter 5 to include scenarios where 2 flows in opposite directions are conveyed by the nodes. We now study a chain with 4 nodes and 1 flow. This scenario gives rise to the hidden node problem. In this chapter, we show how this issue is incorporated in the model. It is important to highlight that the addition of this feature does not greatly impact the model complexity, as we will show it throughout this chapter.

The modeling framework remains divided in 2. First, we have a global high-level queueing network model delivering the performance of the network, including the negative impacts caused by a hidden node. Second, one local low-level model is associated to each node transmitting datagrams. In the next sections, we discuss this extension to provide the initial modeling framework. Then, we present the performance results associated to this extension. Furthermore, we show how this model can be exploited in 105

Global model

We now detail how our model can be applied for a such scenario and the simple modifications that we must include in the model, in order to take into account the hidden node problem.

As in this 4-node scenario there are 3 transmitting nodes (node 4 only sends acknowledgments), the global queueing model associated with the chain is now made of 3 queues with limited size as illustrated in Figure 6.2. We remind that the customers of this queueing model are the datagrams of the chain and the buffer size of queue i is denoted K i . A service rate μ i is associated to each queue i, whose inverse corresponds, by definition, to the mean service time S i of the same queue. This latter time is the average time node i needs to transmit a datagram that is ready to be sent over the radio channel. Provided that all the parameters of the global model are estimated (i.e., the services rates μ i and the frame error probability p f i ), and assuming poissonian arrivals at each node and exponential service rates, we can solve this queueing model as described in previous chapters. Note that the results obtained on the previous scenarios show that these assumptions are acceptable. We decompose the network into independent single M/M/1/K queues, as illustrated in Figure 6.3. All the required performance parameters can thus be derived from the well known results of the M/M/1/K queue. The output throughput of node i is:

λ 3 = X 2 (1 -p f 7 2 ) K 3 1 -p f 1 7 1 -p f 2 7 p f 2 7 p f 1 7 μ 1 μ 2 λ 1 = Λ K 1 K 2 λ 2 = X 1 (1 -p f 1 7 ) X 1 X 2 μ 3 pf 3 7 1 -pf 3 7 X 3
X i = μ i (1 -π i (0)) (6.1)
where π i (n) is the probability of having n customers in the i-th M/M/1/K isolated queue. The average number of datagrams that are correctly transmitted by unit of time from node i to node i + 1 can be derived from relation (6.1) :

λ i+1 = X i (1 -p f i 7 ) (6.2)
Note that for the first node, the arrival rate correspond to the system workload, λ 1 = Λ.

The utilization of node i is:

U i = 1 -π i (0) (6.3)
The probability that a datagram is rejected because the buffer of node i is full at its arrival instant is obtained from PASTA theorem, which results into:

p ri = π i (K i ) (6.4)
We can finally express the overall chain performance, which will be used to validate our model in Section 6.3. The mean chain output throughput, X out , i.e., the average number of datagrams by units of time that reach the destination, can simply be obtained from the throughput of node 3 as:

X out = X 3 (1 -p f 7 3 ) (6.5)
And the chain rejection probability, p rout , defined as the probability that a datagram is rejected due to a full buffer at its arrival instant at any node of the chain or to excessive frame retransmissions, is given by:

p rout = Λ -X out Λ (6.6)
The end-to-end delay of a datagram is approximated as the sum of the sojourn times at each node i of the chain.

R out ∼ = R 1 + R 2 + R 3 (6.7)

Local models

The missing parameters of the global queueing model presented in the previous section are the frame error probability p f i and the service rate μ i .

We denote by p BERi the probability that a given frame sent by node i is in error exclusively because of the BER (Bit Error Rate), and by p colli the probability that the frame sent by node i is lost because of a collision with another frame. We assume that these 2 events are independent but not disjoint (as defined in Section 4.2.2). Thus the frame error probability p f i of node i is obtained as:

p f i = p colli ∪ p BERi = p colli + p BERi -p colli p BERi (6.8)
The BER estimation is identical to the previous chapters, so we just need to derive an estimation of the collision probability. This will be detailed in Section 6.2.3.

For the remaining of this section, we focus on the derivation of the service rate μ i . Following the methodology presented for the scenario with 3 nodes and 1 flow (see Section 4.3.2), we associate, to each queue i of the global model, a Continuous-Time Markov Chain (CTMC) that precisely describes the transmission process of node i according to the IEEE 802.11 DCF protocol. This CTMC is depicted in Figure 6.4 and its structure is identical to the one described in Chapters 4 and 5. However, some of its parameters are adjusted for this scenario, in order to account for frame collisions.

Therefore, we focus only on these parameters, while all the others are estimated in the same way as previously (see Section 4.3.2 for more details).

The parameters of this CTMC that have to be adjusted (with respect to Section 4.3.2) are the frame error probability p f i (to be derived in next section) and the transition rate β i . We now turn our attention to the derivation of the latter parameter.

We remind that the inverse of β i corresponds to the mean time between 2 successive backoff freezing (provided the node is in backoff). This quantity is directly related to the mean backoff duration of node i, denoted as B i , and the average number of freezing

B i = W 1 2 f 1,i + (W 1 +W 2 ) 2 f 2,i + • • • + (W 1 +W 2 +•••+W 7 ) 2 f 7,i f i (6.10) f i = 7 k=1 k f k,i (6.11)
where f k,i is the probability that the transmission of a datagram at node i requires exactly k frames (see relation (4.17)).

Let us now turn our attention to the estimation of the average number of freezing of the backoff of node i, np i , also referred to as the average number of pauses of the backoff. Whenever any node j in the carrier sense range of node i makes a transmission, the backoff is paused. As an example, let us take node 1 in our scenario. In the case

where it has always a datagram to transmit, as illustrated in Figure 6.5, there is always a backoff that is paused by transmissions of nodes 2 or 3 between 2 frame transmissions of node 1. The average number of frame transmissions of node 2, denoted as F 2 , plus the average number of frame transmissions of node 3, denoted as F 3 , occurring between 2 consecutive frame transmissions of node 1, is referred as the average number of pauses of the backoff in node 1. As a generalization for any node i of the chain, the average number of pauses of its backoff is given by the following relation:

np i = j =i F j F i (6.12) B 1 B 1 B 1 T 1 T 2 T 3 B 1 B 1 B 1 T 1 T 2 T 2 T 3 B 1 T 1 time Figure 6
.5: Relation between transmissions in neighbor nodes and backoff freezing in a saturated case.

The frame throughputs are given by relation (4.20), which we rewrite it for the sake of readiness:

F i = X i f i (6.13) B 1 B 1 T 1 T 2 T 3 B 1 B 1 T 1 T 2 T 2 T 3 B 1 T 1 time x 1 y 1 S 1 T Figure 6
.6: Relation between transmissions in neighbor nodes and backoff freezing in a non-saturated case.

In the more general case where node i is not saturated, the expression of np i must be adjusted with a corrective factor δ i as expressed in relation (6.14). This case is illustrated in Figure 6.6 for node 1.

np i = j =i F j F i δ i (6.14)
Indeed, when node i is not saturated, there may be an idle time (x i in the figure) before the beginning of its backoff between 2 of its consecutive transmissions. During this idle time, transmissions of any other node will not cause a freezing of its backoff, whereas during the rest of the time up to the transmission (y i in the figure), transmissions of other nodes (in the sensing range of node i) will freeze its backoff. The corrective factor can be directly obtained from relation (4.21), which we rewrite here for the sake of readiness:

δ i = y i x i + y i (6.15)
In order to estimate the corrective factor, it is worthwhile reminding that the average service time of queue i, S i , is equal to the time y i plus a time T that corresponds to the frame transmission time plus the transmission time of the corresponding ACK. Now, the missing value x i is clearly related to node i utilization U i , which is obtained with relation (4.23), that we rewrite here for the sake of readiness:

U i = S i S i + x i (6.16)
This implies in:

δ i = y i x i + y i = S i -T S i 1-U i U i + S i -T (6.17)
Finally, the missing parameters β i , defined in relation (6.9), can be estimated as:

β i = j =i X j f j X i f i δ i B i (6.18)
With all parameters of the CTMC already described, we may estimate the service rate μ i of the associated M/M/1/K for any queue i, whose inverse corresponds to the average time to "walk" through the CTMC. This value is represented in relation (4.26):

S i = 1 μ i = t 1 i + p f i × (t 2,i + p f i × (t 3 + ... + p f i × t 7,i )) (6.19)
where the average time spent by the process in "line" k (k th backoff stage) of the CTMC, t k,i , and the average time spent in any pair of loop states ({k, j}, {f reeze}) at node i, r i , are directly obtained with relations (4.27) and (4.28).

Frame collision probability

This section presents the estimation of the frame collision probability, which is a very important and sensitive parameter for our model. It represents a component of the frame error probability (relation (6.8)) that is both needed in the global queueing model and in local Markov chain models. A frame collision may be the result of 2 different factors.

First, a collision can result from the well known hidden problem of 2 nodes that are not in the carrier sensing range of each other. Second, because of the sensing mechanism of the IEEE 802.11 DCF, a collision can also occur when 2 neighboring nodes finish their backoff countdown simultaneously. Surely in the previous scenarios (described in previous chapters) such collisions could take place. But their impact were negligible, which is not the case in this section, due to the fact of having 3 nodes transmitting in one direction. By assuming that these 2 possibilities result in disjoint events (which turns out to be exact in our scenario), we can decompose the frame collision probability of node i as the sum of the probability of both events:

p colli = p hidi ∪ p st i = p hidi + p sti (6.20)

Hidden nodes case

Let us first consider the hidden problem case and see how we can estimate the collision probability for node i due to frame collision with nodes that are hidden from node i, denoted as p hidi . In our scenario, since we assume a 2-hop carrier sensing range, the hidden problem can only take place between node 1 and node 4, and more precisely, between a data frame sent by node 1 to node 2 and an acknowledgement ("ACK") sent back by node 4 to node 3.

As an illustration, in Figure 6.7, node 3 senses the medium idle for the duration of its backoff and then starts the transmission of a frame, freezing the backoff countdowns of nodes 1 and 2. The associated acknowledgement ("ACK") sent by node 4 does not prevent node 1 from resuming its backoff countdown (event "B 1 "), since nodes 1 and 4 are hidden from each other. If the remaining backoff of node 1 is short enough (it corresponds to 1 slot time in the example), node 1 will transmit its frame and a collision will occur on both frame and ACK. Although the ACK from node 4 collides, we consider that the collision happens at node 3, since the retransmission mechanism will be performed by this node.

DIFS B 1 DIFS FRAME DIFS B 2
As can be seen on the figure, the duration of the collision is bounded by the maximum overlap h between the frame transmission of node 1 and the ACK transmission of node 4:

h = SIFS + ACK -DIFS -1 slot time (6.21)
We subtract 1 slot time to it, since after a backoff freezing period, the remaining backoff has at least 1 slot time to decrement.

By considering that the nodes have always a frame to transmit, the collision probability p hidi of node i due to a hidden node j can be estimated in a first approximation as the ratio between the duration of a possible collision (h) and the time during which a collision may take place (h + B j ) in between 2 transmissions of node i:

p hidi = h h + B j (6.22)
Relation (6.22) has however 2 limitations. First, by only considering the average duration of the backoff (B j ), we do not take into account the variability induced by the binary exponential backoff used in IEEE 802.11 on the contention window size. For instance, if node 1 is in the first stage of its backoff, an ACK from node 4 will very likely collide with a frame of node 1. Contrarily, when node 1 is at the last stages of its backoff, an ACK from node 4 will have a high chance to be transmitted successfully. But to take this difference into account, we need to first evaluate tb j (k), the proportion of time during which hidden node j remains in backoff stage k. tb j (k) is the ratio between the average time effectively spent in the k-th backoff stage of node j (i.e., p f k-1 j × t k,j ) and the average service time of node j (i.e., S j ):

tb j (k) = p f k-1 j t k,j S j (6.23)
The collision probability p hidi can thus be rewritten as:

p hidi = 7 k=1 tb j (k) h h + B(k) (6.24)
where B(k) = W k 2 T S is the average backoff duration in slots at stage k (T S being the duration of a slot time).

Second, relation (6.22) (or equivalent relation (6.24)) implicitly assumes that node j has a datagram to transmit (otherwise no collision can occur with node i) and should actually be denoted as the conditional probability p hid i |node j is not idle . From the law of Total Probabilities, we can obtain the unconditioned collision probability, by noting that the probability p hid i |node j is idle is null and by reminding that the probability that node j is not idle is nothing but node j utilization:

p hidi = p hid i |node j is not idle U j (6.25)
By combining the previous relations, the collision probability due to hidden nodes can finally be expressed as:

p hidi = 7 k=1 tb j (k) h h + B(k) U j (6.26)

Simultaneous transmissions case

Let us now consider the possible simultaneous transmissions of 2 neighboring nodes. As explained above, 2 nodes in the carrier sensing range of each other are very likely to synchronize themselves (mainly when the load is high). And there is a non negligible probability that the backoff countdowns of these 2 nodes expire simultaneously and that the 2 nodes start their transmission exactly at the same time, resulting in frame collisions. Let p sti denote the probability that a frame of node i collides with a frame of any node that is in its carrier sensing range and that starts a transmission at the same time as node i. This probability can be estimated as follows:

p sti = 1 - j =i (1 -τ j U j ) (6.27)
where τ j is the probability that a given node j in the carrier sensing range of node i starts its transmission at the same time as node i, provided node j has something to transmit, and U j is the utilization of node j. In this approximation, we take collisions only in pairs of nodes, by assuming that 3 (or more) nodes have a very small chance to start their transmission all together. Now we simply estimate the missing conditional probability τ j as the inverse of the average backoff duration of node j expressed in number of slot times:

τ j = 1 B j (6.28)
Now that we have estimated all the parameters of our model, we can proceed to the numerical calculations and the results that our model can deliver.

Fixed-point solution

The global queueing model, that takes as input the service rates μ i of all queues, provides the performance parameters of the chain, like for instance, the datagram throughput X i (relation (6.1)) and the node utilization U i (relation (6.3)). The local CTMC's provide the service rate μ i if their input values X i and U i are known. We use then a fixed-point iteration to obtain the values of the desired parameters, as described in Algorithm 3.

Each step of this algorithm is executed for all the queues, before executing the next step. update error i (relative error between the old and new values of μ i ) 12: until max 1≤i≤N (error i ) < 13: return After the initialization of the service rate μ i with non-absurd values (e.g., we may first set the datagrams arrivals rate at the source node (node 1) to Λ = 2.0 Mb/s, such that the chain is experiencing a high level of workload. Figure 6.9 represents the percentage relative error value on the chain throughput for our proposed model as a function of the distance of the relay nodes 2 and 3 to node 1.

We define the percentage relative error of our model versus the actual values (delivered by ns-2.35) as the ratio 100× (approximate -actual) / actual. The relative error tends to be very low as it stands below ±6% for each of the nearly 550 configurations we have performed to generate this figure. In fact, the error seems to be almost equally spread over negative and positive values. This could support the idea that our model commits an even smaller relative error for the attained throughput (the observed deviation being mostly due to the intrinsic inaccuracies of our model).

Table 6.1 shows the overall distribution of relative errors in the throughput. We observe that the mean error is around 4% and in almost to 100% of cases the error remains below 10% and it never exceeds 15% in all considered cases.

Average < ±5% ±5-10% ±10-15% > ±15% 3.87% 66.78% 32.50% 0.71% 0.0% Table 6.1: Overall accuracy of the model for the throughput of the chain with 4 nodes, 1 flow, K i =20 and Λ=2Mb/s.

We now turn to the chain datagram rejection probability for the chain with 4 nodes and a single flow. Let us remind that the rejection probability denotes the percentage of datagrams being lost while attempting to travel through the 4-nodes chain. Similarly, we consider the accuracy of our model for hundreds of relay nodes positions. Figure 6.10

shows the corresponding percentage relative error. The overall distribution of the relative error for the datagram rejection probability errors can be found in Table 6.2. In this case, the mean error is 4.4% and, as before, a high proportion of the cases remains below 10%, with few samples exceeding 15% of relative error.

Average < ±5% ±5-10% ±10-15% > ±15% 4.4% 63.93% 28.57% 6.43% 1.07% Table 6.2: Overall accuracy of the model for the datagram rejection probability of the chain with 4 nodes, 1 flow, K i =20 and Λ=2Mb/s.

We have performed the same experiment for a different level of workload, with Λ = 1.6Mb/s (this value implies empty buffers sometimes in the chain). The associated results are generally as good as those for 2Mb/s, as we can see in Figures 6.11 and 6.12.

As a matter of fact, for both the throughput and datagram rejection probability relative errors, the values obtained rarely exceed 10%. .12: Relative errors (in percentage) for datagram rejection probability of the chain with 4 nodes and 1 flow, for various positions of relay nodes (x 2 and x 3 ), with K i =20 and Λ=1.6Mb/s. the datagram rejection probability, respectively. In both cases, more than 90% of the values are under 10% error, with none greater than 15%. Given the intrinsic inaccuracies of our model and the difficulties associated to the modeling of such scenarios, such results can be considered quite good in terms of accuracy.

Average < ±5% ±5-10% ±10-15% > ±15% 5.77% 31.43% 66.79% 1.78% 0.0% Table 6.3: Overall accuracy of the model for the throughput of the chain with 4 nodes, 1 flow, K i =20 and Λ=1.6Mb/s.

Average < ±5% ±5-10% ±10-15% > ±15% 6.27% 30.0% 64.11% 5.89% 0.0% Table 6.4: Overall accuracy of the model for the datagram rejection probability of the chain with 4 nodes, 1 flow, K i =20 and Λ=1.6Mb/s.

In addition to accuracy, we investigate the convergence behavior of our solutions. In the thousands of examples, we have evaluated the number of iterations required by our model to converge. This number is small, typically less than several tens. To illustrate this behavior, Figure 6.13 shows the convergence of the service time S i for the 3 queues, when the distances of relay nodes are x 2 = 350m , x 3 = 600m. We see that after an initial light oscillation, the curves quickly tend to their convergence values. We can also note that the results obtained by our model with Matlab for all the distance pairs (x 2 , x 3 ) tested in Figures 6.9 and 6.10 are computed in less than one minute while, with the same computational resource, it takes around 12 hours to ns-2.35 to deliver its results.

Model exploitation

Now, we resort to our model to investigate the behavior of a wireless chain with 4 nodes with the goal of pointing out properties that may be used to get a better understanding and usage of multi-hop networks. Of course, we cross-validate the correctness of the following results using our simulator NS2.

First we rely on our model to study the influence of the buffers length K on the rejection probability. Losses may occur at the buffer input of each node, or less frequently result from the failure of 7 consecutive frame transmissions. We represent, in Figure 6.14, the evolution of this latter probability against the workload level Λ. The relay nodes are respectively set to x 2 = 350 and x 3 = 500 meters. Each curve corresponds to a different buffer length K. The figure shows that losses tend to occur significantly earlier when K equals to 5 datagrams. On the other hand, the actual value of the rejection probability is not much sensitive to K when the latter exceeds 10. Said differently, having a buffer length of 10 or 50 does not postpone much the emergence of datagram losses. Although the actual values of the rejection probability will differ when the spots of relay nodes are moved, we observe through the many other examples we carried out a relative insensibility (often much more marked) to the buffer length as long as K exceeds 10. These experiments support the idea that, at least in the case of 4-nodes chain, there is not much gain for equipping nodes with large buffers. In our second example, we focus on the presence of a throughput optimum (for a given level of workload Λ) and on the associated performance collapse which occurs when the workload is set to excessive values. Multi-hop wireless chains are known to reach their best throughput level when the workload is capped under a certain threshold [LBC + 01, ANB + 12]. In Figure 6.15 we represent the attained throughput of several 4-nodes chains for values of Λ spanning from low levels to high levels of workload with a buffer length K of 20. Each curve corresponds to the expected throughput for a specific spot of node 2 (expressed in terms of its distance to node 1, i.e., x 2 ) while the other relay node (i.e., node 3) is consistently set to 400 meters away from node 1 (x 3 = 400). As shown by this figure, our model captures the existence of this performance optima. We observe that the magnitude of the associated collapse widely varies depending on the precise spot of node 2. For instance the gap between the maximal value and the value asymptotically attained when the system is totally saturated goes up to 45% for x 2 = 10 meters while it decreases to only 14% in the case of x 2 = 350 meters. On the other hand, Figure 6.15 clearly pinpoints that the maximal value of the chain throughput is reached for different values of Λ depending on the position of the relay nodes. Our proposed model provides a simple and fast means (unlike virtually endless simulations) to locate this optimal value of Λ. Thus, for any position of the relay nodes, our model can very quickly deliver an accurate approximation of what should be the maximum authorized level of workload. This behavior clearly argues in favor of the implementation of controlling mechanisms at the border of the chain (such as admission control and traffic shaping policies) to keep the network away from those "counter-productive" running points.

Conclusion

In this chapter, we present a model that fairly represents a chain composed of 4 nodes and a single flow traveling through it. Such chain presents several difficulties in terms of modeling, like for instance, the presence of hidden stations and starvation in relay nodes.

Our model is, however, capable of bypassing these difficulties and delivering accurate results. We se that, in terms of attained throughput obtained by the chain, the relative error between the results obtained with our model and those with simulator ns-2.35 is typically under 5%. Similar results are obtained when we compare the datagram rejection probability for the chain.

Moreover, we show that our model can quickly converge to the solution. This behavior is interesting, since obtaining results from a fast algorithm is a major advantage when compared to long simulations.

Finally, we show how the use of a model allows us to better understand the real system. The estimation of the optimal operating point (in terms of throughput, for instance) or the impacts of the buffer size in the chain performance can be evaluated with an accurate model.

Conclusion

In this thesis, we study single-hop and multi-hop flows based on IEEE 802.11 wireless networks, and more specifically the chain topology. As a consequence, we identify many intrinsic issues to these structures, that naturally increases the complexity of any analytical model designed to study them. For instance, we can mention starvation in nodes or the datagram losses due to buffer overflow. Moreover, we can mention the recurrent hidden node problem, which greatly impacts the system overall performance and that is not easily captured by a model. Because of their complexity, these problems are often ignored in many works. Our goal in this thesis was to take into account these issues and provides accurate results with our proposed model. We provide an hierarchical model, composed of two level: a high-level global queueing network model that matches the chain topology and a low-level local model, that reproduces the necessary IEEE 802.11 DCF specifications associated to each node of the network. This model is to capture interesting behaviors of chains, like, for instance, the performance collapse that happens after a certain level of workload is injected in the chain.

Contributions

In the first chapter of this thesis, we explain the importance of multi-hop wireless networks, based on the IEEE 802.11 DCF principles, and discuss the potential applications, like, for instance, substitution networks. In such networks, several wireless stations can 128 be used as relay stations to forward packets, and a chain network is the simplest configuration that can be naturally employed for this task. Therefore, there is a clear need to better understand the behavior of chains and to estimate their performance.

In Chapter 2, we describe the IEEE 802.11 DCF mechanisms, since this technology is assumed to be used in the chain scenarios we study. Besides, we introduce the tool that we have used to perform simulations (Network Simulator -ns-2.35). Finally, we have also developed a graphical interface for the IEEE 802.11 DCF mechanisms implemented in the simulator (like, for instance, backoff, freezing, DIFS,...), in order to ease the understanding of the system.

The state-of-the-art concerning the subject of this thesis is presented in Chapter 3. Several studies have analyzed the behavior of multi-hop wireless networks, with the design of many models, but most of them are restricted to single hop flows. In this direction, it is common to evaluate the performance of cell networks, specially due to the absence of hidden stations. In another direction, only a few works have proposed models to study multi-hop flows, and most of them only consider single-hop flows to transmit in the network. Very few works are focused on the modeling of multi-hop networks with multi-hop flows and most of their works rely on restrictive assumptions like, for instance, a perfect physical layer or an infinite buffer on each station.

Chapter 4 contains the description of our proposed modeling framework. At a first time, we focus on chains with up to 3 nodes, where all nodes are in each other's carrier sense range. In such scenarios, only one flow is traveling through the network. With these scenarios, we give the basis of our modeling approach that will be used in the following extensions presented in the subsequent chapters. We show that even in the scenarios presented in this chapter, the derivation of the system performance is not so simple, specially due to the strong dependence between nodes in a chain. Our model, however, successfully delivers the performance of the analyzed networks, with small relative errors, when compared to the results of simulation.

We extend our modeling framework, in Chapter 5, for the cases when two flows, in opposite directions, are conveyed through chains with up to 3 nodes. In these scenarios, the nodes remain in each other's carrier sense range. We show that it is simple to adapt the base model proposed in the previous chapter, in order to incorporate 2 flows. Once again, the results delivered by our model are quite accurate.

Finally, in Chapter 6, once more, we extend the base model to chain with 4 nodes.

In this case, we adapt it to deal with the hidden node problem in a 4-nodes chain. This new feature is fundamental for future extensions to model any N-nodes chain.

By incorporating the probability of frame collisions on the radio channel, and without exhaustive modifications in the base model, the results delivered by our model are found to be accurate, compared to simulations performed with ns-2.35.

Future Work

With this thesis coming to an end after a bit more than three years of studies, naturally some interesting points remain to be further analyzed concerning our model for multihop wireless networks. We can mention the extension of the model for larger chains.

One immediate problem for these scenarios remains the estimation of the mean backoff freezing duration. In these cases, the backoff of a node may be frozen due to the transmissions of frames and acknowledgements from many different neighbors. We also point out that, with larger scenarios, the hidden node problem will have a higher probability to appear. Developing a model for larger networks, dealing with several flows, remains also an interesting topic for future researches. It would also be important to evaluate the accuracy of the model for more recent versions of the IEEE 802.11 protocol. Another point that remains to be studied is the use of adaptive physical transmission rates between nodes. In that case, the number of frame losses have an effect on the rate at which the

Faculté

  Techniques des Activités Physiques et Sportives Observatoire des Sciences de l'Univers de Lyon Polytech Lyon Ecole Supérieure de Chimie Physique Electronique Institut Universitaire de Technologie de Lyon 1 Ecole Supérieure du Professorat et de l'Education Institut de Science Financière et d'Assurances Directeur : M. F. DE MARCHI Directeur : M. le Professeur F. FLEURY Directeur : Mme Caroline FELIX Directeur : M. Hassan HAMMOURI Directeur : M. le Professeur S. AKKOUCHE Directeur : M. le Professeur Georges TOMANOV Directeur : M. le Professeur H. BEN HADID Directeur : M. Jean-Claude PLENET Directeur : M. Y.VANPOULLE Directeur : M. B. GUIDERDONI Directeur : M. P. FOURNIER Directeur : M. G. PIGNAULT Directeur : M. le Professeur C. VITON Directeur : M. le Professeur A. MOUGNIOTTE Directeur : M. N. LEBOISNE

  My thanks also go to Mr. André-Luc Beylot (Professor at École Nationale Supérieure d' Électrotechnique, d' Électronique, d'Informatique, d'Hydraulique et des Télécommunications) and Mr. Gerardo Rubino (Senior Researcher at INRIA) for accepting evaluate my thesis. In this direction, I thank Mr. Vania Conan (Senior Research Expert at Thales Communications & Security) and Mr. Anrdzej Duda (Professor at École Nationale Supérieure d'Informatique et de Mathématiques Appliquées de Grenoble) for accepting to be members of my jury.

Finalement, certains impacts

  sur les performances des chaînes occasionnés par les mécanismes IEEE 802.11 sont analysés et détaillés. La forte synchronisation entre les noeuds d'une chaîne et comment cette synchronisation représente un défi pour la modélisation de ces réseaux sont décrites. Le modèle proposé permet de surmonter cet obstacle et d'assurer une évaluation facile des performances de la chaîne. Mots-clés: Chaînes de Markov, IEEE 802.11 DCF, Réseaux Sans fil Multi-sauts, Modèle Hiérarchique. 2.12 Graphical interface for a scenario with collisions between frames and acknowledgments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.13 Chain topology with communication range to 1-hop neighbors and carrier sense range to 2-hop neighbors. . . . . . . . . . . . . . . . . . . . . . . . . 4.1 A chain with N + 1 nodes and with 1 flow of workload Λ. . . . . . . . . . 4.2 Global model for a chain with N + 1 nodes (but N nodes transmitting datagrams). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 An example of the service time of a datagram at node 1. . . . . . . . . . . 4.4 Decomposed global model for a chain with N nodes transmitting datagrams and 1 flow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Iteration between global and local models. . . . . . . . . . . . . . . . . . . 4.6 A chain with 2 nodes and 1 flow. . . . . . . . . . . . . . . . . . . . . . . . 4.7 Global model for a chain with 2 nodes. . . . . . . . . . . . . . . . . . . . . 4.8 Local CTMC representing the service time of node 1, with a chain of 2 nodes and 1 flow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Relative errors for throughput of the chain with 2 nodes and 1 flow. . . . 4.10 A multi-hop chain with 3 nodes and 1 flow. . . . . . . . . . . . . . . . . . 4.11 Global queueing model for a chain with 3 nodes and 1 flow. . . . . . . . . 4.12 Decomposed global model for a chain with 3 nodes and 1 flow. . . . . . . 4.13 Local CTMC representing the service time of each node transmitting datagrams. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.14 Illustration of the relation between β i , np i and B i . . . . . . . . . . . . . . 4.15 Relation between transmissions of node 2 and backoff freezing of node 1 in a saturated case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.16 Relation between transmissions of node 2 and backoff freezing of node 1 in a non-saturated case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.17 Mean service times of datagrams for a workload of 6Mb/s. . . . . . . . . . 4.18 Mean backoff freezing duration for a workload of 6Mb/s. . . . . . . . . . . 4.19 Mean throughput. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.20 Rejection probability by buffer overflow. . . . . . . . . . . . . . . . . . . . 4.21 End-to-end delay. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.22 Relative errors for throughput of the chain with 3 nodes and 1 flow. . . . 4.23 Throughput estimated by the model for a chain with 3 nodes and 1 flow. 5.1 A chain with 2 nodes and 2 flows. . . . . . . . . . . . . . . . . . . . . . . . 5.2 Global model for a chain with 2 nodes and 2 flows. . . . . . . . . . . . . . 5.3 Local CTMC representing the service time of each node transmitting datagrams. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Relative errors for throughput of the chain with 2 nodes and 2 flows. . . . 5.5 Chain throughput delivered by the model for 2 nodes and 2 flows. . . . . 5.6 A multi-hop chain with 3 nodes and 2 flows. . . . . . . . . . . . . . . . . . 5.7 Global model for a chain with 3 nodes and 2 flows. . . . . . . . . . . . . . 5.8 Decomposed model for a chain with 3 nodes and 2 flows. . . . . . . . . . . 5.9 Relative errors for throughput of the chain with 3 nodes and 2 flow. . . . 5.10 Relative errors for datagram rejection probability of the chain with 3 nodes and 2 flows. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.11 Chain throughput delivered by the model for 3 nodes and 1 flow. . . . . . 5.12 Relative errors for throughput of the chain with 3 nodes and 2 flows with asymmetric workload. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.13 Relative errors for datagram rejection probability of the chain with 3 nodes and 2 flows with asymmetric workload. . . . . . . . . . . . . . . . . 6.1 Multi-hop chain with 4 nodes and 1 flow. . . . . . . . . . . . . . . . . . . 6.2 Global queueing model for a chain with 4 and 1 flow. . . . . . . . . . . . . 6.3 Decomposed global model for a chain with 4 nodes and 1 flow. . . . . . . 6.4 Local Markov chain model. . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Relation between transmissions in neighbor nodes and backoff freezing in a saturated case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Relation between transmissions in neighbor nodes and backoff freezing in a non-saturated case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.7 Collision between ACK from node 4 and frame from node 1. . . . . . . . . 6.8 Topology used for the numerical results. . . . . . . . . . . . . . . . . . . . 6.9 Relative errors (in percentage) for throughput for various positions of relay nodes (x 2 and x 3 ) with K i =20 and Λ=2Mb/s. . . . . . . . . . . . . 6.10 Relative errors (in percentage) for datagram rejection probability of the chain with 4 nodes and 1 flow, for various positions of relay nodes (x 2 and x 3 ) with K i =20 and Λ=2Mb/s. . . . . . . . . . . . . . . . . . . . . . . . . 6.11 Relative errors (in percentage) for throughput for various positions of relay nodes with K i =20 and Λ=1.6Mb/s. . . . . . . . . . . . . . . . . . . 6.12 Relative errors (in percentage) for datagram rejection probability of the chain with 4 nodes and 1 flow, for various positions of relay nodes (x 2 and x 3 ), with K i =20 and Λ=1.6Mb/s. . . . . . . . . . . . . . . . . . . . . . . 6.13 Convergence of the service times of each node, with K i =20, Λ=2Mb/s, x 2 = 350m and x 3 = 600m. . . . . . . . . . . . . . . . . . . . . . . . . . . 6.14 Absolute rejection probability of a chain with 4 nodes as a function of the workload level. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.15 Expected throughput of 4 different chains with 4 nodes as a function of the workload level. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

  List of notations associated to the global model. . . . . . . . . . . . . . . 2 List of notations associated to the local model and the IEEE 802.11 specifications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 2-ray ground propagation model parameters. . . . . . . . . . . . . . . . . 2.2 IEEE 802.11b parameters. . . . . . . . . . . . . . . . . . . . . . . . . . . .4.1 Overall accuracy of the model for the throughput of the chain with 3 nodes and 1 flow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Overall accuracy of the model for the throughput of the chain with 2 nodes and 2 flows. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Overall accuracy of the model for the throughput of the chain with 3 nodes and 2 flows. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Overall accuracy of the model for the datagram rejection probability of the chain with 3 nodes and 2 flows. . . . . . . . . . . . . . . . . . . . . . . 5.4 Overall accuracy of the model for the throughput of the chain with 3 nodes and 2 flows with asymmetric workloads. . . . . . . . . . . . . . . . 5.5 Overall accuracy of the model for the datagram rejection probability of the chain with 3 nodes and 2 flows with asymmetric workloads. . . . . . . 6.1 Overall accuracy of the model for the throughput of the chain with 4 nodes, 1 flow, K i =20 and Λ=2Mb/s. . . . . . . . . . . . . . . . . . . . . . 6.2 Overall accuracy of the model for the datagram rejection probability of the chain with 4 nodes, 1 flow, K i =20 and Λ=2Mb/s. . . . . . . . . . . . 6.3 Overall accuracy of the model for the throughput of the chain with 4 nodes, 1 flow, K i =20 and Λ=1.6Mb/s. . . . . . . . . . . . . . . . . . . . . 6.4 Overall accuracy of the model for the datagram rejection probability of the chain with 4 nodes, 1 flow, K i =20 and Λ=1.6Mb/s. . . . . . . . . . .

Figure 1 Figure 1

 11 Figure 1.1: A simple example of infrastructure-based wireless network.

Figure 1 .Figure 1 . 3 :

 113 Figure 1.3 presents an example of a substitution network operating to restore the service when a link fails. In a) we have the original network and in b) the failure occurs when the link goes down. The idea in c) is to provide temporarily communication through the deployment of mobile routers, while maintenance is performed.The concept of a substitution network is initially proposed in [RBDDA + 11] and it is also the core focus of the ANR VERSO RESCUE project (ANR-10-VERS-003) 3 , to which this work is related. In this context, the base network is assumed to operate through wired technologies or through a wireless technology requiring large and fixed facilities. So it is very likely that the attained capacity of the substitution network, whose

  Figure 1.4 depicts the concept implemented by the company, with the connections among balloons (on top) and between balloons and householders (from top to bottom).

Figure 1

 1 Figure 1.4: The Google Loon multi-hop wireless network (Image obtained from http://www.google.com/loon).

Figure 1 .

 1 Figure 1.5 shows an example, where direct communication between stations A and B

Figure 1

 1 Figure 1.5: A wireless chain network connecting two stations A and B.

Figure 2 . 1 :

 21 Figure 2.1: Communication and carrier sensing ranges of a node.

Figure 2 .

 2 Figure 2.2 summarizes the different behaviors. Note that the received signal power thresholds, which allow to change from one range to another, depend on the wireless card characteristics.

Figure 2 . 3 :

 23 Figure 2.3: An example of the IEEE 802.11 DCF mechanisms.

Figure 2 . 5 :

 25 Figure 2.5: Scenario with three nodes and one light.

Figure 2 . 7 :

 27 Figure 2.7: Scenario with three nodes and one heavy workload.

Figure 2 . 8 :Figure 2 . 9 :Figure 2 Figure 2

 282922 Figure 2.8: Graphical interface for a saturated scenario.

Figure 2 .Figure 2 . 13 :

 2213 Figure 2.13 shows an example of our topology, for a case where a single workload is injected in one side of a chain composed of 6 nodes.

  e. a single-hop network in which each node senses the transmission of each other), one of the most important works is proposed by Bianchi [Bia00]. The author designs a model based on a Discrete-Time Markov Chain (DTMC) to evaluate the attainable throughput of single-hop transmissions, where nodes are always in saturation. Several extensions of this work have been proposed to closer match to DCF mechanisms. For instance, in [TBX10], the authors propose a new backoff decrement model that preserves the simplicity of the model proposed in [Bia00].

Figure 4

 4 Figure 4.1: A chain with N + 1 nodes and with 1 flow of workload Λ.

Figure 4

 4 Figure 4.3: An example of the service time of a datagram at node 1.

Figure 4

 4 Figure 4.4: Decomposed global model for a chain with N nodes transmitting datagrams and 1 flow.

  Considering the intrinsic dependence between the global and local models, whose output parameters are the inputs of each other, we naturally use a fixed-point iteration to obtain all the desired parameters.

Figure 4

 4 Figure 4.5: Iteration between global and local models.

Figure 4

 4 Figure 4.6: A chain with 2 nodes and 1 flow.

Figure 4 . 7 :

 47 Figure 4.7: Global model for a chain with 2 nodes.

Figure 4 . 8 :

 48 Figure 4.8: Local CTMC representing the service time of node 1, with a chain of 2 nodes and 1 flow.

Figure 4

 4 Figure 4.9: Relative errors for throughput of the chain with 2 nodes and 1 flow.

Figure 4 Figure 4

 44 Figure 4.10.At a first glance, this simple scenario could cause the reader to misinterpret its complexity and the difficulties to derive its performance. However, several issues need to be taken into account when dealing with this type of networks. First of all, the BER varies according to the nodes positions, which impacts the link quality and therefore the number of frame retransmissions. Second, there is a strong dependence between the nodes of the chain. The backoff freezing of one node depends on the transmissions of its neighbors. Those transmissions are related to the level of workload in the chain and, for the relay node, transmissions are dependent on the number of correctly received

Figure 4 .

 4 Figure 4.11: Global queueing model for a chain with 3 nodes and 1 flow.

Figure 4 . 13 :

 413 Figure 4.13: Local CTMC representing the service time of each node transmitting datagrams.

Figure 4

 4 Figure 4.14: Illustration of the relation between β i , np i and B i .

  3.1 are, among others, the datagram throughput X i for queue i (relation (4.6)), the datagram rejection probability due to a full buffer p ri (relation (4.11)) and node utilization U i (relation (4.10)).

Figure 4 .

 4 Figure4.17 compares the mean values of the service time of a datagram (as described in Section 4.3.1) obtained with our model and those collected from simulation, with a workload of 6Mb/s and for different relay positions (node 2). As seen in this figure, the service time, which is a key parameter for our model, closely matches the values of the simulation, with a difference between both results smaller than 10%.Overall, the model presents good performance for most of the positions of the relay node. The existence of a high BER affects the results of our model for the extreme positions. As expected, when node 1 is distant of the relay node, we see the service time in the first queue being multiplied by a factor of 10. Nevertheless, our model satisfactorily represents this behavior.

Figure 4 .Figure 4 Figure 4

 444 Figure 4.18 shows the mean time spent in backoff freezing before transmitting a

Figures 4 .

 4 Figures 4.19(a) and 4.19(b) show the throughputs of both nodes obtained from our model and from simulation, for workloads of 3Mb/s and 6Mb/s.

Figure 4 .

 4 Figure 4.19: Mean throughput.

Figure 4 .

 4 Figure 4.20(a) and 4.20(b) compare the datagram rejection probabilities of our model

Finally, Figure 4

 4 .21(a) and 4.21(b) show the mean end-to-end delay of a datagram.

  Figure 4.20: Rejection probability by buffer overflow.

Figure 4

 4 Figure 4.21: End-to-end delay.

Figure 4

 4 Figure 4.23: Throughput estimated by the model for a chain with 3 nodes and 1 flow.

Figure 5

 5 Figure 5.1: A chain with 2 nodes and 2 flows.

Figure 5 . 2 :

 52 Figure 5.2: Global model for a chain with 2 nodes and 2 flows.

Figure 5 . 3 :

 53 Figure 5.3: Local CTMC representing the service time of each node transmitting datagrams.

Figure 5 . 4 :

 54 Figure 5.4: Relative errors for throughput of the chain with 2 nodes and 2 flows.

Figure 5 . 5 :

 55 Figure 5.5: Chain throughput delivered by the model for 2 nodes and 2 flows.

FigureFigure 5

 5 Figure 5.6.

Figure 5 . 7 :

 57 Figure 5.7: Global model for a chain with 3 nodes and 2 flows.

Figure 5

 5 Figure 5.10: Relative errors for datagram rejection probability of the chain with 3 nodes and 2 flows.

Figure 5

 5 Figure 5.11: Chain throughput delivered by the model for 3 nodes and 1 flow.

Figure 5

 5 Figure5.12: Relative errors for throughput of the chain with 3 nodes and 2 flows with asymmetric workload.

Figure 5 . 13 :

 513 Figure 5.13: Relative errors for datagram rejection probability of the chain with 3 nodes and 2 flows with asymmetric workload.

Figure 6 . 2 :

 62 Figure 6.2: Global queueing model for a chain with 4 and 1 flow.

Figure 6 . 3 :

 63 Figure 6.3: Decomposed global model for a chain with 4 nodes and 1 flow.

FRAMEFigure 6 . 7 :

 67 Figure 6.7: Collision between ACK from node 4 and frame from node 1.

Figure 6 . 8 :

 68 Figure 6.8: Topology used for the numerical results.

Figure 6 Figure 6

 66 Figure6.9: Relative errors (in percentage) for throughput for various positions of relay nodes (x 2 and x 3 ) with K i =20 and Λ=2Mb/s.

Figure 6

 6 Figure 6.11: Relative errors (in percentage) for throughput for various positions of relay nodes with K i =20 and Λ=1.6Mb/s.

Figure 6 . 13 :

 613 Figure 6.13: Convergence of the service times of each node, with K i =20, Λ=2Mb/s, x 2 = 350m and x 3 = 600m.

Figure 6

 6 Figure 6.14: Absolute rejection probability of a chain with 4 nodes as a function of the workload level.

Figure 6

 6 Figure 6.15: Expected throughput of 4 different chains with 4 nodes as a function of the workload level.

Table 1 :

 1 Probability of having n customers in the queue K Number of nodes transmitting datagrams X out Throughput of the chain (in datagrams per second) p rout Datagram rejection probability of the chain R out End-to-end delay of a datagram List of notations associated to the global model. BER Frame error probability due to BER of a link p coll Frame collision probability p hid Frame collision probability due to a hidden node p st Frame collision probability due simultaneous transmissions tb(k) Proportion of time during which a hidden node remains in backoff stage k β -1 Mean time separating two backoff freezing (provided the node in in backoff)

	λ i	Datagram arrival rate at the queue i
	Λ	Workload of the system
	μ i	Service rate of the queue i
	S i	Service time of the queue i
	π(n)

i Capacity of the queue i (in datagrams) X i Throughput of the queue i (in datagrams per second) F i Throughput of the queue i (in frames per second) p ri Datagram rejection probability of the queue i R i Sojourn time in the queue i Q i Number of datagrams to be transmitted and waiting in the queue i U i Utilization of the associated node N γ -1 Mean duration of the backoff freezing plus a DIFS (DCF Interframe Space) time B Backoff duration of a frame np Number of pauses (freezing) in the backoff per frame f k Probability of transmitting a datagram in exactly k frames T Duration of a frame plus acknowledgment transmissions and a SIFS (Short Interframe Space) W k Contention window size at the k-th backoff stage α -1 Duration of a backoff slot t difs Duration of a DIFS time t sifs Duration of a SIFS time Table 2: List of notations associated to the local model and the IEEE 802.11 specifications.

Chapter 2 IEEE 802.11 DCF and Simulator 2.1 DCF mechanisms

  this work are finally presented in Chapter 7.

	The CSMA/CA (Carrier sense multiple access with collision avoidance) is an access
	method developed for wireless networks that aims to avoid collisions on channel during
	transmissions of different stations. In this direction, the IEEE 802.11 standard [IEE12]
	implementing the DCF (Distributed Coordination Function) is among the most impor-
	tant techniques for local wireless networks.
	In this work, we use the IEEE 802.11 DCF mechanism and, therefore, we describe
	its main characteristics in this section. It is important to describe and discuss them,
	since our model, which will be presented in the next sections, lies intrinsically on the
	behavior of the DCF mode.
	When a node has a datagram to transmit, it is enqueued in a buffer. When the node
	is ready to send the datagram, it passes a copy of this datagram to the MAC (Medium
	Access Control) layer, who will implement all the IEEE 802.11 DCF mechanisms that
	we describe in this section. This datagram copy is referred as a frame.

  according to the flowchart depicted in Figure2.4. We can see all the steps a node needs to follow, in order to transmit a frame, and what actions to take in the case of transmission success or failure.

		Start
		Wait new frame
		to transmit
		Choose new
		backoff
		Check channel	Busy	channel is idle Wait until
	Reset
	CW	Idle	Idle channel
		Defer DIFS while channel is idle	Busy channel
		Decrement lasting	Busy channel
		backoff slot by slot
		while channel is idle
		Backoff finished
	ACK
	received	Transmit frame
		and wait timeout
		No ACK
		received
	Discard associated datagram	Double CW
	Yes		No
		Retransmission
		limit?
	Figure 2.4: Flowchart of the IEEE 802.11 DCF mechanisms.
				, suggesting that the
	EIFS is not triggered in some IEEE 802.11 cards. Some chipsets (e.g. Atheros AR9331)
	have also the possibility to ignore EIFS.
	IEEE 802.11 includes an optional mechanism to avoid collisions, known as RTS/CTS.
	When activated, prior to each frame transmission, a node sends a RTS (Request-to-Send)
	frame and should receive a CTS (Clear-to-Send) frame in the aim of getting exclusive
	use of the channel. Note that since RTS/CTS has been shown to be inefficient in the
	case of a chain [XGB03], we did not consider it in our study.
	Finally, we can summarize the IEEE 802.11 DCF mechanism as used in this work,

Table 2

 2 Table 2.1.

	Antennas height	1.5m
	Antennas gain	1
	Nodes transmitting power	0.031622777w
	Carrier sense power threshold	6.309573445 × 10 -13 w
	Communication power threshold 6.309573445 × 10 -12 w
	Communication range	399m
	Carrier sense range	700m
	DIFS	50μs
	SIFS	10μs
	Time slot	20μs
	Contention window size (min,max) 31, 1023
	Frame transmission limit	7

.1: 2-ray ground propagation model parameters. Fourth, we use the IEEE 802.11b protocol throughout this work, whose parameters values are provided in Table 2.2.

Table 2

 2

.2: IEEE 802.11b parameters.

  The works described so far show the complexity of the IEEE 802.11 DCF mechanisms in term of modeling and the associated difficulties. Therefore, several works pro-

	pose modifications in the original IEEE 802.11 methods to make the modeling process
	easier ( [HS02a], [Cho05], [AMB02], [RKKW04], [YCZ

+

06], [YBS + 03] and [PYG

+ 13]

).

  The datagram arrival rate at each queue i is λ i (with i = 1, 2, ..., N ), and, by construction,

					S 1
	node 1	DIFS Backoff	FRAME	Timeout	DIFS Backoff	FREEZE	DIFS Backoff	FRAME	Timeout
									time
	node 2								SIFS+ACK
	One of the major difficulties when modeling chain networks relies on the presence of

Λ = λ 1 . The capacity (queueing room) of each queue i is denoted K i and corresponds to the number of datagrams that can be stored in the queue. A datagram is immediately discarded whenever it arrives at a queue, whose buffer is already full. Moreover, we remind that for each datagram, the system will attempt to transmit the corresponding frames up to 7 times, as described in Section 2.4. If none of these frames is correctly transmitted, the datagram is then discarded. From Figure

4

.2 we can see that our model captures the two types of losses associated to such networks.

To each queue i of our network, we associate a service rate μ i . This rate is, by definition, the inverse of the mean service time S i of the same queue, which corresponds to the mean time node i needs to transmit a datagram that is ready to be sent over the radio channel. S i includes all the IEEE 802.11 DCF transmission mechanisms described in Section 2.1, starting with a defer time DIFS and followed by backoff, eventual freezing periods, possible frame (re)transmissions and timeouts (SIFS and the duration of an acknowledgement) until an ACK is received or the datagram is discarded. The computation of the service rate μ i for queue i is explained later in this section. Figure 4.3 shows an example of the service time for a given datagram at node 1 (S 1 ), with 1 frame transmission that fails.

  of the backoff of node i, denoted as np i , as given in the following relation (see Section

	DIFS
							1
			1				DIF S×W1
	1-pf i		DIF S×W1
	T	T	αi	1,0	αi	1,1	αi		1,W1-2	αi	1,W1-1
	pf i T		βi	γi	βi		γi	βi	γi	βi	γi
				freeze		freeze		freeze		freeze
	DIFS
									1st backoff stage
							1
			1				DIF S×W2
	1-pf i		DIF S×W2
	T	T	αi	2,0	αi	2,1	αi	2,W2-2	αi	2,W2-1
	pf i T		βi	γi	βi		γi	βi	γi	βi	γi
				freeze		freeze		freeze		freeze
									2nd backoff stage
	DIFS
							1
			1				DIF S×W7
			DIF S×W7
	1
	T	T	αi	7,0	αi	7,1	αi	7,W7-2	αi	7,W7-1
			βi	γi	βi		γi	βi	γi	βi	γi
				freeze		freeze		freeze		freeze
	End of Serv.									7th backoff stage
	Figure 6.4: Local Markov chain model.
	4.3.2 for more details):
					1 β i	=	B i np i				(6.9)
	In order to estimate β i , we can directly use relation (4.15) to obtain the average
	backoff per frame of a node. Moreover, we can apply here all the relations from (4.16)

up to (4.18), as to calculate the contention window size W k at row k in the CTMC and the number of frame (re)transmissions per datagram f i .

http://www.wifibot.com

http://ardrone2.parrot.com/

http://rescue.lille.inria.fr/

http://www.google.com/loon

http://www.wireshark.org/

http://www.mathworks.com/

This tool was developed with the collaboration of Mr. Huu-Nghi Nguyen.

Acknowledgements

proposed model to evaluate the performance of such chains. specifications.

Numerical Results

We have simulated the scenario described in this section, according to the definitions in Section 2.4. Node 1 is fixed and node 2 is positioned at several spots within the interval [110m,390m] away from node 1. The queue capacity K 1 is 50 (datagrams).

We compare the results provided by our model with those of simulations, with regard to the performance parameter analyzed for this scenario: the chain throughput X out .

We evaluate our model under different workload levels, ranging from 0.2Mb/s to 5Mb/s, in order to validate its results in the presence or absence of saturation. In our scenario, we have saturation whenever the BER is large (typically with distances greater than 300m). In the following figure, each simulation point is obtained with an mean over at least 80,000 datagrams received at the destination. Figure 4.9 shows the relative error (in %) of the chain throughput between our model and ns-2.35 in function of the workload and the distance between the two nodes. We define the percentage relative error of our model versus the actual values (delivered by ns-2.35) as the ratio 100× (approximate -actual) / actual. This surface is obtained by using interpolation between the simulation points. We note that the mean relative error remains around 3-5% regardless the workload level. However, there is a slight increase in this error when the system has to cope with large values of BER. This is clearly seen for the cases when the distance between nodes is around 390m. Nevertheless, the relative error remains smaller than 10% in the worst cases. Those errors can be explained given the inaccuracies of our modeling framework. For instance, we consider that the service time

workload of 10Mb/s), which allows us to analyze our model when submitted to low and high workloads.

Figure 5.9 shows the relative error for the chain throughput between the simulation and our model. For very light aggregated workloads (under 2Mb/s), our model clearly presents excellent results. The relative errors are low, typically around ±3%, but they increase a little in the presence of high BER (the top and bottom points of the surface). When the workload is around 4Mb/s, we have the largest values for the relative error (approximately 15%), but for all other nodes positions and workloads, the models remains satisfactorily accurate. Table 5.2 shows the overall distribution of the throughput relative errors. We can see that for approximately 90% of points, the relative error remains under 10%.

Workload of the entire system (Mb/s) Distance between nodes 1 and 2 (meters) order to illustrate the importance of such tools for a better understanding of the real system.

Scenario with four nodes and one flow

Our current scenario is depicted in Figure 6.1. There are 4 nodes in the network, labeled from 1 to 4. We remind that the communication range is limited to the 1-hop neighbors for any node. The carrier sense range affects all 2-hop neighbors, which means that nodes 1 and 4 do not sense each other (they are hidden stations). We consider a non-perfect physical layer, subjected to a certain amount of Bit-Error Rate (BER), implying possible frame losses. Unlike the previous scenarios studied so far, frames can also be lost due to collisions between data frames from node 1 and acknowledgments from node 4 (up to 30% of frames in our scenario are lost due to such collisions). We remind that such collisions take place, since we have deactivated the EIFS mechanism, as described in Chapter 2. Otherwise, for this network topology, collisions due to hidden node were unlikely to happen. This triggers several frame retransmissions from nodes 1 and 3, which greatly impacts the overall system performance, especially the attained throughput of the chain.

The traffic is generated according to a Poisson process with rate Λ, from node 1 up to node 4, using both nodes 2 and 3 as relay.

set it to 1), the algorithm will iterate until a convergence criteria is reached. In our case, we calculate, on each queue, the relative deviation between the value of the service rate at the current iteration with the one from the previous iteration (referred as to error i ).

If this value is lower than a criteria for all queues, the iteration is no longer performed.

Once the model has converged, we obtain the chain performance in terms of the chain throughput X out and the chain datagram rejection probability p rout .

Numerical Results

In this section we study the accuracy of our proposed model and we show how its exploitation can bring new insights in the behavior of wireless multi-hop chains at a very low cost of computation. We consider the parameters defined in Section 2.4 for the simulations.

Model accuracy

To evaluate the accuracy of our model, we compare its results with those delivered by simulation. In the following figures (from 6.9 to 6.12), each simulation point has been obtained with 100,000 packets generations at the source node. Note also that each figure

(from 6.9 to 6.12) corresponds to hundreds of data points explored (both by the simulator and by the model), and the surfaces shown are obtained using an interpolation from sets of scattered data points. We consider the following example. The four nodes of the chain are scattered in a straight line as represented by Figure 6.8. Nodes 1 and 4 are fixed while the positions of nodes 2 and 3 vary. We denote by x 2 (resp. x 3 ) the distance between node 2 (resp.

3) and node 1. Note that the positions of nodes 2 and 3 must obey certain rules so that 1-hop neighbors can communicate. This is the reason behind the white "impossible area" band in Figures 6.9 and 6.10. The buffer at each node is set to 20 datagrams. We link will operate, impacting the whole system performance.

Moreover, the use of variable datagram sizes may represent some challenges in the modeling approach. Finally, in order to evaluate the real accuracy of our framework, a comparison between our model performance and those delivered by real experimentations would be of great value.