List of Figures

List of Tables

 Table 1:
Abstract

Wireless multi-hop ad hoc and sensor networks provide a promising solution to ensure ubiquitous connectivity for the Future Internet. Good network connectivity requires designing a reliable Medium Access Control (MAC) protocol, which is a challenging task in the ad hoc and sensor environments. The broadcast and shared nature of the wireless channel renders the bandwidth resources limited and expose the transmissions to relatively high collisions and loss rates. The necessity to provide guaranteed Quality of Service (QoS) to the upper layers triggered the design of conflict-free MAC protocols. The TDMA synchronization constraint is basically behind the rush of MAC protocol design based on a fixed frame size. This design shows inflexibility towards network variations and creates a network dimensioning issue that leads to a famine risk in case the network is under-dimensioned, and to a waste of resources, otherwise. Moreover, the alternative dynamic protocols provide more adaptive solutions to network topology variations at the expense of a fair access to the channel. Alongside with the efficient channel usage and the fair medium access, reducing the energy consumption represents another challenge for ad hoc and sensor networks. Solutions like node activity scheduling tend to increase the network lifetime while fulfilling the application requirements in terms of throughput and delay, for instance.

Our contributions, named OSTR and S-OSTR, address the shortcomings of the medium access control protocol design in the challenging environment of wireless multi-hop ad hoc and sensor networks, respectively.

For OSTR the idea consists in adopting a dynamic TDMA frame size that increases slotby-slot according to the nodes arrival/departure to/from the network, and aiming to achieve a minimum frame size. For this end, OSTR couples three major attributes: (1) performing slotby-slot frame size increase, (2) providing a spatial reuse scheme that favors the reuse of the same slot if possible, (3) and ensuring an on-demand frame size increase only according to the node requirements in terms of throughput. To tackle different frame sizes co-existence in the network, OSTR brings a cooperative solution that consists in fixing an appointment, a date when the frame size in the network is increased.

Concerning S-OSTR, it is an amendment of OSTR for wireless sensor networks. It brings the idea of a dynamic active period, since it deploys a dynamic frame size that is built slot-byslot according to nodes arrival to the network. S-OSTR enforces the slot-by-slot frame size increase by a node activity scheduling to prolong the inactivity period in the network, and hence prolong the overall network lifetime for wireless sensor networks.

Our contributions are both based on the new dynamic TDMA frame size increase that consists in increasing the frame size slot-by-slot aiming to achieve a shorter frame size, and hence improve the channel utilization, and reduce the energy consumption. The performance analysis of OSTR and S-OSTR shows that they present good potentials to support QoS requirements, to provide energy-efficiency, to ensure fair medium access, to accommodate network topology changes and finally, to enhance robustness against scalability. The impact of this new TDMA frame size increase technique on the medium access control protocol performance is highlighted through multiple simulations of OSTR and S-OSTR. Multiple comparative studies are also handled to point out the effectiveness of this new technique and the soundness of our contributions.

Key words: ad hoc networks, TDMA, dynamic, sensor networks, energy-efficient, fairness.

Résumé

Les réseaux sans fil multi-sauts ad hoc et les réseaux de capteurs présentent une solution prometteuse pour assurer une connectivité quasi-permanente dans l'Internet du Futur. Cette connectivité, néanmoins, nécessite la conception d'un protocole d'accès au canal radio fiable, ce qui défi les caractéristiques hostiles et instables des réseaux ad hoc et des réseaux de capteurs. Cet environnement, en effet, est caractérisé par la rareté des ressources radio disponibles, la perte de la bande passante due aux collisions et aux interférences. La nécessité de garantir une meilleure qualité de service aux couches applicatives a promu la conception des protocoles MAC basés sur la technique d'accès TDMA. Essayant de contourner la contrainte d'une fine synchronisation horloge imposée par ce type de protocoles, les recherches se sont orientées vers une conception de protocoles MAC basés sur la technique TDMA dont la taille de la trame est fixe.

Cependant, cette conception présente deux principaux inconvénients: d'une part elle procure une inflexibilité quant à la variation de la topologie du réseau suite aux mouvements des noeuds. D'une autre part, elle soulève un problème de dimensionnement : si la taille de la trame est surdimensionnée par rapport au nombre de noeuds présents dans le réseau, des slots non alloués apparaissent induisant la perte de la bande passante. Toutefois, si la taille de la trame est sous-dimensionnée, un risque de famine surgit. Les protocoles MAC basés sur la technique TDMA à taille de trame dynamique présentent une alternative, qui réussit à augmenter le débit au détriment d'une non-équité entre les noeuds dans le réseau. Outre l'utilisation optimale et équitable de la bande passante disponible, la réduction de la consommation d'énergie constitue un autre défi majeur pour les réseaux ad hoc et les réseaux de capteurs.

Dans ce travail, deux contributions nommées OSTR et S-OSTR, sont conçues pour améliorer le débit, l'équité et la réduction de la consommation d'énergie dans l'environnement des réseaux ad hoc et des réseaux de capteurs. L'idée motrice d'OSTR consiste à augmenter la taille de la trame TDMA dynamiquement de manière à aboutir à une taille de trame réduite. Dans ce but, OSTR met en place une augmentation à la demande de la taille de la trame. Cette augmentation est établie slot par slot. OSTR se base sur une réutilisation spatiale des times slots ; i.e. un même slot peut être utilisé au même moment par plusieurs noeuds dans le réseau. Afin de prévenir les collisions dues à la coexistence de plusieurs tailles de trames au même temps dans le réseau, OSTR déploie une solution coopérative qui consiste à fixer un rendez-vous au moment duquel la taille de la trame est augmentée simultanément par tous les noeuds dans le réseau.

S-OSTR constitue une adaptation du protocole OSTR à l'environnement des réseaux de capteurs. S-OSTR vise à augmenter la durée de vie du réseau. Il déploie ainsi une période d'activité dynamique qui consiste en une trame TDMA augmentant slot-par-slot. S-OSTR effectue également un ordonnancement des activités des noeuds afin de prolonger la période d'inactivité, et par suite prolonger la durée de vie du réseau.

Nos deux contributions se basent sur une nouvelle technique d'augmentation dynamique de la taille de la trame TDMA qui consiste à augmenter la taille slot-par-slot. Cette technique permet d'atteindre une taille réduite, et par conséquent d'améliorer l'utilisation de la bande passante et de minimiser la consommation de l'énergie dans le réseau.

L'analyse des performances d'OSTR et de S-OSTR souligne leurs potentiels pour s'adapter aux exigences des applications en termes de QoS, pour assurer un accès équitable au canal radio, pour réduire la consommation de l'énergie et pour s'adapter aux différents changements de la topologie du réseau.

Mots clés : Réseaux Ad hoc, réseaux de capteurs, TDMA, équité, dynamique, réduction de l'énergie Chapter 1

Introduction

The current trend in wireless communications is towards a global connectivity "Anytime, Anywhere; with Anything, and with Anyone". This tendency is known as the "internet of things" that aims to integrate the existing communication systems with the evolving Internet to enable communications between physical and virtual "things". This trend has arisen from the wireless revolution supported by the advances in wireless networking, the greater standardization of communication protocols, and the miniaturization of computing devices with higher capabilities and lower cost. This expansion will change the Internet perception, and create new vision of the information society. In the Internet of future, ubiquity is a mandatory requirement to achieve the "all-in-one" communication system.

Ubiquitous communications could not exist without integration with the legacy communication systems that were born since the early 90s when the digital second generation was launched. A decade after, the Global System for Mobile communications (GSM) triggered the wireless communication expansion that has grown from the 2,5G to the third generation (3G) to enable, in the near future, the fourth generation (4G) that allows the integration of heterogeneous Radio Access Networks (RAN) into a single platform capable of supporting inter-RAN roaming; while not interrupting active communications. The WIFI plays a crucial role in this new generation, since it provides high achievable bit rates for a reduced infrastructure cost.

The obvious trend as an all-in-one architecture for the internet of future will result in a more flexible architecture but a more complex management. First, the huge amounts of collected, exchanged, processed and stored data will explode. The management of all these data will require more and more energy to consume. Novel energy-efficient mechanisms to transmit, and process data will, therefore, be needed to ensure a better data management. Moreover, wireless devices involving smart phones, laptops, tiny sensors, and the miniaturized silicon chips are intended to be self-organized, ultra low power, and even capable of auto-harvesting the energy they need. From this perspective, ad hoc communications are one of the key technologies required to fulfill the achievements of the internet of things.

Wireless ad hoc networks are by definition created on-the-fly to achieve a specific purpose; they operate in a distributed way without relying on existing infrastructure. In the early 1970's, ad hoc networks were first designed for battlefield communications. The great amount of research work done insofar has led to the integration of ad hoc networks for applications in daily life. Communicating in an ad hoc fashion brings interesting solutions to guarantee ubiquitous connectivity for the Internet of future; it is exploited in creating smart and self-aware environments. It also provides potentially endless opportunities in a diverse number of applications. Ad hoc communications are useful for Intelligent Transportation Systems (ITS), where a network of sensors set up throughout the vehicle can interact with other vehicles and infrastructure around to provide more accurate feedback about the traffic conditions, and the presence or not of danger on the road [START_REF]The Internet of Things -Strategic Research Roadmap[END_REF]. Wireless ad hoc communications are also used in eco-system monitoring. A set of devices are deployed to monitor the heat, or the water flows into catchment areas, to provide early warning systems for flood prone regions or earthquake prone areas [START_REF] Anastasi | Energy conservation in wireless sensor networks: A survey[END_REF]. The growth of nanotechnologies and short range communication systems such as IEEE 802.15.4 [3] the basis of Zigbee [4], has given rise to health care applications, where a set of sensors is used for pulse or diabetes monitoring, and for old people assistance as well.

Depending on the device characteristics in terms of power transmission range, the processing capacity, the battery capacity, and so on, ad hoc communications way gives rise to two major networks: wireless ad hoc networks and wireless sensor networks. Despite their commonalities, each network needs to bypass specific constraints and to fulfill different application requirements. Ad hoc networks are mainly applied in wide range areas. For instance, they ensure connectivity in student campus, and help providing internet connection in emergency cases where no infrastructure is available. Wireless sensor networks, instead, are characterized by a strong interaction with the environment, and hence are more suited for applications like indoor/outdoor monitoring, interactive museums, sensing for transportation applications, etc.

Despite the enormous amounts of research on both wireless ad hoc and sensor networks, Medium Access Control (MAC) design consists one of the challenging research topics that still require insights to ensure a smooth and reliable involvement of these networks in the Internet of future.

Problem Statement

The medium access control layer plays an important role to ensure consistent and reliable system operation. It coordinates the channel access among different devices in the network. While for traditional wireless systems this task is monitored by a base station (e.g. in GSM) or an access point (e.g. WiFi), it should be held in a completely distributed way in wireless ad hoc and sensor networks. Additional challenges are introduced by the ad hoc communication fashion and require special handling by the medium access layer: [START_REF]The Internet of Things -Strategic Research Roadmap[END_REF] robustness against the inherent wireless environment, [START_REF] Anastasi | Energy conservation in wireless sensor networks: A survey[END_REF] the scarcity of available resources, (3) the resource sharing between different devices in a distributed way, (4) the energy-efficient management of battery-limited devices, [START_REF] Goldsmith | Design Challenges for Energy-Constrained Ad Hoc Wireless Networks[END_REF] the potential need for an accurate time synchronization required for channel access coordination. In this thesis, we consider mainly three important properties in the MAC protocol design for wireless ad hoc and sensor networks:

-Optimal resource management: It consists in achieving rates close to the fundamental capacity limits of the channel [START_REF] Goldsmith | Design Challenges for Energy-Constrained Ad Hoc Wireless Networks[END_REF] ,

-Fair resource management: all users should receive equal bandwidth, -Energy-efficient resource management: Since most wireless devices are batterypowered, MAC protocol that consumes relatively little energy are of interest.

For this end, we first consider the environment of ad hoc networks and focus on the optimization of resource sharing in a distributed and fair manner. Afterwards, we investigate the network lifetime prolonging in wireless sensor environment through the design of a more energy efficient channel access technique in the MAC layer.

Optimization of Resource Management

Bandwidth exploitation efficiency in wireless ad hoc networks is fundamental in order to make the whole system appealing for QoS support. Better the resource exploitation is, better is the QoS provided by the overall network. The resource management optimization can be incurred at different levels of the OSI stack. In this thesis, we focus on possible improvements of channel utilization at the MAC layer.

The medium access protocol design for wireless ad hoc networks need to take into account the broadcast nature of the radio channel. It needs therefore, to minimize collisions and provide a good strategy to tackle the interference effect due to the hidden and exposed terminal problems. These problems are peculiar to the wireless environment and are closely related to the transmission signal power of the devices. The hidden and exposed terminal problems lead to collisions and an underutilization of the channel resources. The main difficulty in the medium access protocol design resides in the distributed coordination of nodes such that a tradeoff between the control packets overhead and the resources allocated to real data transmission is necessary. In addition, efficient bandwidth exploitation needs to be fair among different end users so that no one is penalized while others are monopolizing the available resources. How to design a medium access protocol that tends to an optimal and fair resource sharing in a completely distributed manner, while ensuring low control overhead is a crucial issue to alleviate.

Despite the wide deployment of IEEE 802.11 Distributed Coordination Function (DCF) [6], its random channel access scheme suffers from short term and flow unfairness [START_REF] Emre Koksal | An analysis of short-term fairness in wireless media access protocols[END_REF]. It has been shown in [START_REF] Capdevielle | Multi-Hop Coverage Extension of an IEEE 802.11b WLAN in a Corporate Environment[END_REF] that the standard still has multiple limitations that prevent it from a better resource management. It presents bad performance in multi-hop environment and cannot support high traffic load. Thanks to its natural guaranteed channel access, the Time Division Multiple Access (TDMA) [START_REF] Rom | Multiple Access Protocols Performance and Analysis[END_REF] technique has seduced the research community for MAC protocol design. The idea behind TDMA channel access is to reserve a guaranteed period for each device in the network, during which it accesses the channel without contending with other competing nodes. Despite the accurate clock synchronization required for TDMA channel access deployment, TDMA-based MAC protocol design has gained a lot of attention. The IEEE 802.11s Mesh Deterministic Access [START_REF] Hiertz | Principles of IEEE 802.11s[END_REF] is the fruit of the standardization effort to optimize the channel utilization. The bandwidth is a periodic time frame split in a fixed number of time slots. Each device reserves a number of time slots during which it accesses the channel in a conflict-free manner. Despite the improvements provided by the new IEEE amendments, the channel access still relies solely on the carrier sensing scheme, and therefore still suffers from collisions. Also, the TDMA channel access gives rise to a critical issue to face which consists of the optimal network dimensioning. In other terms, this issue consists on pre-configuring the TDMA frame size according to the number of nodes in the network. However, wireless ad hoc networks are a collection of devices that can dynamically selforganize, and are in perpetual movement; i.e. some nodes can join the network, while others can dispose after the frame size has been configured. This dimensioning problem, lead to two important issues that need to be tackled by the MAC protocol: the famine risk that occurs when the frame size is under-dimensioned, and the underutilization of the available resources that takes place when the frame size is over-dimensioned.

In this thesis, we are trying to bring effective solution to overcome the TDMA frame size dimensioning issue. Before describing the building blocks of our solution, we will describe in more detail the main MAC protocol design challenges for wireless multi-hop ad hoc networks. We will then, analyze the dimensioning problem faced while using TDMA channel access based on fixed frame size. For this end, we will review the masterpiece works that have been proposed in this field to derive their limitations.

Energy Efficiency

The energy conservation is a critical part of the future internet of things that necessitates a tradeoff between the power constraint in one side; and the significant increase of energy consumption in another side. The tons of data exchanged, processed and stored will explode the energy consumption unless new mechanisms are developed to address energy conservation [START_REF]The Internet of Things -Strategic Research Roadmap[END_REF]. The Internet of Things will contribute to the greening of communications based on different attributes: (1) New energy efficient applications need to be established such as power grid, connected electric vehicles, energy efficient buildings, etc, (2) the area of nano-electronics and semiconductor, sensor technology need more investigations to provide low power devices, and(3) reliable energy efficient communication protocols need to be addressed to ensure energy conservation.

In this thesis, we will focus on the development of energy efficient medium access control protocol for wireless sensor networks since these networks have more energy constraints than wireless ad hoc networks. A sensor is generally a tiny device equipped with a battery as sole power supply. The battery often has limited power budget. Moreover, once deployed, a sensor is barely changed when it disposes because it may be deployed in hostile or unpractical environment (e.g. minefields). In addition, depending on the applications, a sensor network should fulfill a long lifetime ranging from several months to several years [START_REF] Anastasi | Energy conservation in wireless sensor networks: A survey[END_REF]. Therefore the crucial question consists on: "how to minimize the energy consumption such that network lifetime is prolonged?"

Increasing the lifetime of a sensor network can be the result of the use of an energyefficient routing strategy; it can be the result of improving the MAC access mechanism by reducing the energy consumed in processing control packet overhead, and minimizing the cause of energy waste at the MAC level. Our work is centered on energy efficient solution at the medium access layer where several techniques to conserve power consumption are proposed. Among these techniques, node activity scheduling has succeeded to spare energy thanks to the alternation between a sleep state when sensors turn off their radio and go to sleep, and a wake up state when sensors are communicating. TDMA schemes are also considered as a promising solution to provide energy efficient access schemes for wireless sensor networks. With a TDMA access scheme, a node turns on its radio only during its slot; therefore the energy consumption is restricted to the minimum required for transmission/receiving data. The TDMA access scheme, however, has the main drawback of fixed frame length that has to be specified beforehand and may be problematic.

In this thesis, we will propose a more reliable energy-efficient solution to take profit from the advantages of the TDMA access scheme, while reducing its flip side. We will first describe the philosophy of the node activity scheduling approach, and then we will analyze the capability of TDMA schemes to provide more energy efficient solution.

Contributions of the Thesis

Wireless ad hoc and sensor networks provide a promising solution for the future internet of things. These networks gained their interest by their flexibility and adaptability to different scenarios. Also, they consist one of the key technologies to provide cost-effective and energyefficient solutions.

Despite the enormous amount of research on wireless ad hoc networks and more recently on wireless sensor networks, many technical design performance issues are preventing its widespread deployment. For instance, ad hoc and sensor networks are still unable to provide quality of service (QoS) comparable to that achieved by wire line or infrastructure-based networks. Innovative and effective solutions are, therefore, needed to improve the QoS of these networks. The Medium Access Control layer design in wireless networks, more precisely ad hoc and sensor networks has a major role in increasing the overall system performance. In this thesis, we tackle the medium access control protocol design from different aspects: (1) optimizing the resources distribution and utilization, (2) providing an energy efficient solution, (3) and addressing flexibility and adaptability to network variations. This thesis starts investigating the given research area by providing a description of key challenges that need to be addressed while designing a MAC protocol for wireless ad hoc and sensor networks. The thesis presents, then, a review on the masterpiece works achieved to address the defined challenges. We show that the standardization efforts of IEEE 802.11 still perform poorly in multi-hop environment and highly loaded networks. On the other hand, our work focus on alternative solutions to carrier sensing, mainly Time Division Multiple Access based ones. We show that TDMA wireless multi-hop networks still perform poorly because of the inflexibility of their frame size design. On the other hand, this drift between the achieved performance and the optimal ones can be justified by the dilemma of frame size dimensioning: an over-dimensioned frame size with respect to the number of users in the network infers an underutilization of the available resources; while an under-dimensioned frame size yields to a famine risk. Achieving an optimal frame size, in this context, is NP complete. For instance, [11] shows that an optimal TDMA schedule is equivalent to a k-hop coloring problem which is NP hard. We investigate then, a distributed and dynamic solution to provide a solution that tends to the optimum. In particular, we highlight the limited scientific research efforts that have addressed a dynamic frame size concept for wireless ad hoc and sensor networks. We argue that a dynamic frame size coupled with an appropriate distributed slot allocation scheme can drastically increase the overall system performance. More precisely, the thesis contributes to the research problem by developing a new frame size increase technique that achieves four main objectives:

1. An adaptive solution to different use-cases in both ad hoc and sensor networks, 2. A frame size increase is performed with respect to the number of nodes in the network, 3. A slower frame size increase is ensured in order to achieve a shorter frame size. The shorter the frame size is, the higher is the channel utilization, 4. And an energy-efficient solution exploiting the shorter frame size achieved.

The new investigated technique increases the frame size slot by slot, only if needed. This new technique is the basis of the two main contributions of the present work: OSTR: OSTR is a distributed and dynamic TDMA-based medium access control protocol for wireless ad hoc networks designed to increase the global throughput and per-node fairness by achieving a shorter overall frame size. OSTR answers to the limitations of fixed frame size based protocols by providing a flexible and adaptive frame size increase. The basic idea of OSTR is to couple three major attributes to provide a shorter frame size: (1) performing a slot-by-slot frame size increase, (2) providing a spatial reuse scheme, (3) and an on-demand frame size increase. To tackle different frame sizes co-existence in the network, OSTR brings cooperative solution that consists in fixing an appointment, a date when the frame size in the network is increased.

Sensor-OSTR:

Sensor OSTR is a new energy efficient MAC protocol for wireless sensor networks. S-OSTR organizes the channel access in a totally distributed way such that energy is optimally consumed. S-OSTR brings the idea of a dynamic active period, since it deploys a dynamic frame size that is built slot-by-slot according to nodes arrival to the network. S-OSTR enforces the slot-by-slot frame size increase by a node activity scheduling to prolong the inactivity period in the network, and hence prolong the overall network lifetime.

Organization of the Thesis

The outline of the thesis is as follows. In this chapter the importance of the medium access protocol design for the Internet of future was discussed. This will be further enlightened in Chapter 2 through which more insight is given on the challenges that need to be addressed while designing a MAC protocol for wireless ad hoc and sensor networks. Also a review of the masterpiece researches achieved in improving MAC layer performance in wireless ad hoc networks are presented including a comprehensive understanding of the limitations of a frozen frame size for TDMA-based MAC protocols, and an explicit enlightening of the promising potentials of the dynamic frame size, instead. Chapter 3 presents the OSTR medium access control protocol for wireless ad hoc networks that reflects the potentials of the slot-by-slot frame size increase in improving the fairness and the throughput in the network. A proof-of-concept implementation and a comparative study with the standard IEEE 802.11 DCF and E-ASAP [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF] are provided as well. Chapter 4 provides the amendment of OSTR to wireless sensor networks resulting in the S-OSTR protocol. A general overview about node activity scheduling and energy-efficient MAC protocols for wireless sensor networks is given with a special emphasis on the different medium access design contributions yielding to network lifetime prolonging. Potentials of the slot-by-slot frame size increase technique brought by OSTR, to provide energy efficient solution are highlighted. Technical description of the S-OSTR protocol is later presented. Chapter 4 ends with an evaluation of S-OSTR performance using extensive simulations and comparative study with SERENA [START_REF] Minet | SERENA: SchEduling RoutEr Nodes Activity in wireless ad hoc and sensor networks[END_REF]. The last chapter concludes the thesis by summarizing the main contributions and results, and discussing the future perspectives and research directives.

Chapter 2

Distributed MAC Protocols for Wireless Ad hoc Networks

Introduction

Ad hoc networks have been a challenging area of research during the recent past. They have specific limitations and characteristics such as resource scarcity, node mobility, lack of central coordinator, and inherent broadcast nature; that complicate the research studies in this field. An efficient and reliable Medium Access Control (MAC) protocol is important to enable a successful operation of wireless multi-hop ad hoc networks, and to ensure better QoS to the upper layers.

The design of an efficient and reliable MAC protocol for multi-hop communications in an ad hoc environment is a challenging task. An efficient MAC protocol should consider the inherent characteristics of such environment, and also provide QoS support mechanism required by the upper layers. The common use of random channel access mainly deployed in the widespread IEEE 802.11 [6] products, still suffers from several drawbacks because it is prone to collisions and interference effect and it is unable to fairly share the resources. Although alternative protocols, mainly based on Time Division Multiple Access techniques (TDMA) are proposed, so far the design of an efficient MAC protocol for multi-hop ad hoc networks still lacks insights in the adaptability to network topology variations, scalability, efficient bandwidth usage, and fairness.

Accordingly, an efficient MAC protocol design needs to address all the aspects that may affect its performance such as node mobility, distributed environment, and lack of available resources. By adopting a TDMA-based channel access technique, the interference effect in nodes' neighborhood is reduced and the network throughput is increased as well, because of the guaranteed channel access offered by the TDMA scheme. In a multi-hop ad hoc network, where nodes are prone to mobility and where the density varies from one network region to another, a frozen TDMA frame size leads to a bandwidth wastage and unfairness issue. With improvements on this level, the MAC protocol converges to an optimal resource management, and to better topology variation adaptability.

In this chapter, we will survey the works that have been done in the field of MAC protocol design for wireless multi-hop ad hoc networks. Mind, of course, that we cannot review the complete body of that work in detail. We will rather focus on the researches that are more relevant to our work. In Section 2.2, we highlight the main MAC protocol design challenges and propose a new classification of the existing MAC protocols in this research field. We give a brief description of contention oriented schemes in Section 2.3, with a focus on the standard IEEE 802.11 in both DCF and EDCA modes. In Section 2.4, we overview the main conflict free TDMA-based MAC protocols. We give a particular attention to the standardization effort limitations to address multi-hop communication in ad hoc networks. We also, point out the importance of dynamic frame size to address the topology changes, the fairness problem and the optimal channel utilization.

MAC issues and protocol classification for multi-hop ad hoc networks

Like in all shared-medium networks, the medium access control protocol has an important role for the successful operation of the network. Some of the fundamental tasks of the MAC protocol are to coordinate the radio resource access between the nodes in the network and to reduce the collisions from interfering nodes [START_REF] Xu | Revealing the problems with 802.11 MAC protocol in multi-hop wireless networks[END_REF]. The inherent nature of wireless multi-hop ad hoc environment introduces additional challenging tasks that should be taken into account while designing a MAC protocol for multi-hop ad hoc networks.

First, the MAC protocol should be distributed because no central coordinator is present in ad hoc networks and nodes need to self organize themselves to enable communications.

Moreover, the MAC protocol should be dynamic in order to take into considerations the dynamic nature of wireless ad hoc networks, and to adapt to topology variations. Thus, the system performance will not be significantly affected by node's mobility.

In addition, the design of a MAC protocol should consider the broadcast nature of the radio channel. A good MAC protocol should therefore, minimize collision and interference effect due to the hidden and exposed terminal problems.

In wireless networks, nodes share a common broadcast radio channel. As the radio spectrum is limited, the available bandwidth to share is also limited. Thus, a good MAC protocol for wireless ad hoc networks should be efficient so that the scarce resources are optimally utilized. Consequently, the MAC protocol should be designed such that the bandwidth consumption incurred by control message exchange is as less as possible.

Besides, radio devices should be energy efficient especially when deployed for specific applications such as data gathering, and monitoring. A good MAC layer design can implement mechanisms to address the energy efficiency issue.

Finally, an important attribute for MAC protocol design is the per-node fairness. Although fairness can hardly be defined [START_REF] Nandagopal | Achieving MAC Layer Fairness in Wireless Packet Networks[END_REF], we understand that nodes need to be "treated" fairly with respect to the bandwidth allocation. In other terms, the unfairness consists on enabling some nodes a frequent channel access on dispense of other nodes. The latter can barely acquire the channel, resulting in higher latency, and higher packet loss ratio. Some other attributes include shorter latency, reliable source to destination links, and scalability. In this work the focus is on the network throughput efficiency, per-node fairness, accommodation to network topology variations, and energy efficiency. In the sequel, we highlight some of the main issues in MAC protocol design for wireless multi-hop ad hoc networks.

MAC protocol design challenges

The medium access control sub-layer has an important impact on the system performance. The MAC protocol should coordinate the channel access among contending nodes in a dynamic and distributed way. Therefore, its design is a challenging task. In the following, the major challenges that a MAC protocol needs to face in the wireless multi-hop environment are explained.

a) Varying topology and channel

The wireless medium is a challenging environment mainly because of its broadcast nature and the inability to detect collisions in such context. The wireless medium is prone to multipath propagation, fast fading, and path loss. This yields to a higher bit error rate (BER), and to burst errors because of the bit correlation [11]. Unlike wire line networks, radio links are more frequently broken due to nodes movement and topology variations. This side effect is accentuated in wireless ad hoc network due to the absence of a central coordination. Therefore, distributed mechanisms based on frequent exchange of control packets such as HELLO packets, and RTS/CTS packets, are needed at the MAC layer to cope with channel and topology varying effects. In a wireless environment, the transmission signal power decay with the distance. We distinguish, then, two kinds of neighbors (with reference to node A in Fig. 1): those capable of decoding the received signal from node A like node B; and those that receive the signal but consider it as noise, since they are unable to decode it, as it is the case for node C. Beyond this observation, the definition of transmission range and interference range arise. The transmission range of node A, is defined as the maximum reached distance, denoted by r(A), over which the signal over noise ratio allows correct reception of a message sent by node A. The interference range instead is defined as the area in which nodes perceive the channel as busy due to node's A transmission, but may not be able to decode the message. In the example depicted in Fig. 1, and with reference to node A, node B is a one-hop neighbor of node A, since it is within the transmission range of node A. However, node C is a two-hop neighbor of node A, and is within the interference range of node A. The hidden and exposed terminal problems are a direct consequence of the concept of transmission and interference range in wireless networks.

A hidden terminal is a node within the transmission range of the receiver node, and out of the transmission range of the sender node. In Fig. 1, node B is in the transmission range of node A. However, node C is not aware of the presence of node A, since it is not in the transmission range of node A. Hence, when node B transmits a packet to node B, node C perceives the channel as free and starts a transmission to node B. Such a transmission provokes a collision at node B, and both packets are lost. The hidden terminal problem significantly degrades the carrier sensing based MAC protocols. One of the main solutions provided to tackle this issue is the use of a handshake mechanism such the RTS/CTS mechanism deployed in the standard IEEE 802.11 [6]. An exposed terminal is a node within the transmission range of the sender but out of the range of the receiver. Considering the example illustrated in Fig. 2 with node C transmitting to node D. Node C is in the transmission range of node A but out of the range of node B, so it is exposed. Due to the carrier sensing, node C is unable to transmit to node D even though the two exchanges (node A to node B, and node C to node D) can co exist simultaneously without collisions at the respective receivers. Consider now, that node D initiates a transmission to node C. Since node C perceives the channel as busy, it is blocked and cannot acknowledge node D's transmission. The latter makes several retrials until it aborts and discards the packets.

c) Exposed terminal problem

The exposed terminal problem leads to an underutilization of the channel which is a critical issue in an environment where the resources are scarce.

d) Fairness

In wireless communications, fairness is a critical issue to face. It is a direct consequence of the inherent characteristic of the wireless medium where limited resource should be shared between multiple nodes. [START_REF] Dianati | A new fairness index for radio resource allocatio in wireless networks[END_REF] highlights the complexity of defining the concept of fairness in wireless networks. It is shown that offering the same channel access opportunities for the nodes in the network does not guarantee a fair system behavior, since the channel quality of each node may affects its channel access; and therefore, the medium access protocol is perceived as unfair from its point of view. In wireless communication networks, the fairness is generally measured according to one of the three following indexes: Gini index [START_REF] Garetto | Modeling per-flow throughput and capturing starvation in csma multi-hop wireless networks[END_REF], the Min-max index [START_REF] Huang | On max-min fairness and scheduling in wireless ad-hoc networks: Analytical framework and implementation[END_REF], and the Jain fairness index [START_REF] Jain | A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems[END_REF]. In our work, we measure the amount of allocated resources based on the Jain fairness index defined in [START_REF] Jain | A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems[END_REF]. Suppose a system that allocates bandwidth to n contending nodes. If the Jain fairness index is equal to 1, the protocol

A C r(A) = transmission range of node A Exposed Terminal B D
is 100% fair. In this thesis, the fairness is computed based on the number of nodes in the network using the throughput of each node as a computational metric.

MAC protocol classification

From the literature, two major families of MAC protocols for wireless ad hoc networks are:

1.

The contention-based protocols,

2.

The contention-free protocols.

The former group needs to acquire the channel access before the transmission of each frame. ALOHA [START_REF] Abramson | The Aloha System -Another Alternative for Computer Communication[END_REF], CSMA [START_REF] Kleinrock | Packet switching in radio channels, part I-Carrier sense multiple-access modes ans their throughput-delay characteristics[END_REF], MACAW [START_REF] Bharghavan | MACAW: a Media Access Protocol for Wireless LAN's[END_REF], FAMA [START_REF] Garcia-Luna-Aceves | Floor Acquisition Multiple Access (FAMA) in single-channel wireless networks[END_REF], and IEEE 802.11 [6] are some examples of MAC protocols within this group. The IEEE 802.11 gained wide adoption thanks to its simplicity, robustness and flexibility. It is based on the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) [3].

On the other hand, Contention-free MAC protocols rather reserve the channel for a certain amount of time and ensure, therefore, conflict-free packet exchange. Basically, these protocols proceed in two steps: a random channel access to gain the reservation, followed by a scheduled transmission of data packets.

Among conflict-free MAC protocols we distinguish the basic channel access techniques: Time Division Multiple Access (TDMA) where the frequency band is the same for all nodes in the network and the time is slotted.

Frequency Division Multiple Access (FDMA) where the multiple users simultaneously access the channel by using different frequency bands.

Code Division Multiple Access (CDMA) where the multiple channel access is achieved based on predefined signature sequences called codes. These codes are used to modulate the transmitted signal and hence minimize interference with contending nodes.

In this work, we focus on the TDMA-based solutions. In the literature, multiple classifications of TDMA-based MAC protocols have been proposed. For instance, [11] proposes to classify the conflict-free MAC protocols into node allocation-based and link allocation-based protocols. To our knowledge, the dynamicity of the frame in TDMA-based protocols has known little attention in wireless multi-hop environment. Though, we argue that a dynamic resource handling is necessary to optimally use the scarce resources in ad hoc networks. We also, believe that a dynamic frame size has a major impact on the MAC protocol performance. Consequently, we propose to classify TDMA-like MAC protocols for ad hoc networks based on the frame size characteristic; i.e. static or dynamic. As depicted in Fig. 3, two groups rise: (1) fixed frame size-based MAC protocols, and (2) dynamic frame size-based protocols. Examples of the former group are TRAMA [START_REF] Goldsmith | Design Challenges for Energy-Constrained Ad Hoc Wireless Networks[END_REF], FAMA [START_REF] Garcia-Luna-Aceves | Floor Acquisition Multiple Access (FAMA) in single-channel wireless networks[END_REF], CATA [START_REF] Nandagopal | Achieving MAC Layer Fairness in Wireless Packet Networks[END_REF], FPRP [START_REF] Zhu | A Five-Phase Reservation Protocol (FPRP) for mobile ad hoc networks[END_REF], CROMA [START_REF] Capdevielle | Multi-Hop Coverage Extension of an IEEE 802.11b WLAN in a Corporate Environment[END_REF] and USAP [START_REF] Young | USAP: a unifying dynamic distributed multichannel TDMA slot assignment protocol[END_REF]. The philosophy of these protocols is to firstly contend to acquire a dedicated resource, and then to initiate a conflict-free packets exchange using the reserved resources. This group of protocols can, by its turn, be split into two sub-groups according to whether the mini-slot concept is used or not. In one side, the reservation process is performed in the slot itself using mini-slots concept; i.e. a slot is split into multiple mini-slots, some of them are used to allow nodes contend for one of the mini-slots where DATA are transmitted. In other side, however, the contention is performed in a dedicated part of the frame and is not overlapped with the resources reserved for data exchanging. Examples of dynamic frame size-based protocols are USAP-MA [15] and E-ASAP [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF]. The idea of a dynamic frame size is to build the frame step by step following the number of nodes in the network. By adjusting the frame size, the frame is adaptive to network topology variations. The MAC protocol is, therefore, more efficient and flexible, since it converges to a better use of the channel resources.

Contention-based MAC protocols

Contention-based MAC protocols are one of the most popular classes of MAC protocols for wireless ad hoc networks. These protocols are mainly based on some mechanisms such as packet-sensing [START_REF] Garcia-Luna-Aceves | Floor Acquisition Multiple Access (FAMA) in single-channel wireless networks[END_REF] that characterizes ALOHA-like protocols, and carrier sensing based on which a node is able to know whether the channel is idle or not. In [11] it is mentioned that carrier sensing protocols are more present in today's MAC protocol design. Hereafter, we detail some of the contention-based MAC protocols based on the carrier-sensing scheme.

Carrier Sense Multiple Access (CSMA)

The Carrier Sense Multiple Access (CSMA) is an improvement of the basic ALOHA [START_REF] Abramson | The Aloha System -Another Alternative for Computer Communication[END_REF] access scheme. CSMA is based on the principle of listen before talk. When a node has a packet ready to be transmitted, it has first to sense the channel. If the channel is perceived as busy, i.e. another transmission is already ongoing; the node delays its transmission. A node can proceed with the transmission only if the channel is idle. With CSMA, two or more nodes can attempt to transmit at the same time, and collisions might occur. After a transmission failure, a node may try to transmit once again. CSMA is shown to have good performance when the number of contending nodes is not very large. Nevertheless, its performance suffers from the hidden terminal problem and thus considerably degrades when the number of nodes is high [START_REF] Kleinrock | Packet Switching in Radio Channels: Part II -The Hidden Terminal Problem in Carrier Sense Multiple Access and the Busy-Tone Solution[END_REF].

IEEE 802.11 in DCF and EDCA modes

The IEEE 802.11 [6] has known a tremendous deployment during the last decade. The IEEE 802.11 media access is based on the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) mechanism. With the IEEE 802.11, a node first senses the channel. If the channel is free, it waits for a Distributed Inter-Frame Spacing (DIFS) time period. If the channel remains free, the node transmits a packet. In case the channel is perceived busy, the transmitting node delays its transmission until the channel becomes free. At that time, the node chooses a random back off value from the range [0; CW [, and waits for the chosen back off value of idle slots before attempting to transmit again. The CW has a minimum value of CW min (minimum Contention Window) chosen by the node for the first transmission attempt. A collision occurs when two or more nodes have the same remaining back off values. Therefore, they will access the channel at the same time and collide. To handle the collision issue, the IEEE 802.11 standard uses a binary exponential back off scheme. This scheme is used such that after each transmission failure, the CW value is doubled and hence the node has a larger range of back off values [0; CW [. This process is repeated each time a collision occurs. The CW value is doubled up to a maximum value of CW max = 2 n x CW min , where n is the number of the failed transmission attempts, and is reset to the minimum value after each successful transmission.

To avoid the hidden terminal problem, the IEEE 802.11 uses a handshake of a Request To Send and a Clear To Send (RTS/CTS) before the transmission of the DATA/ACK packets. Before sending a DATA packet, the sender requests for the channel by sending an RTS. If successfully received, the receiver node responds with a CTS packet, after Short Inter-Frame Space (SIFS) period of time. Upon the reception of the CTS, the sender node waits for SIFS, and then starts the DATA transmission. Each correctly received packet is acknowledged by an ACK control packet.

In addition to the RTS/CTS handshake, the IEEE 802.11 implements the virtual carrier sensing (Fig. 4). RTS, CTS and DATA packets include a duration field that is initialized to the duration of the sequence. Any other node that hears the RTS or the CTS sets its Network Allocation Vector (NAV) to one. This indicates that the channel will remain busy for the whole duration of the sequence. The performance of the standard IEEE 802.11 has been largely studied by the scientific community. [START_REF] Bianchi | Performance Analysis of the IEEE 802.11 Distributed Coordination Function[END_REF], for instance, gives an analysis of the IEEE 802.11 Distributed Coordination Function (DCF) in saturation cases in a fully connected network; while the effect of the hidden terminal problem has been studied in [START_REF] Chhaya | Performance Evaluation of the IEEE 802.11 MAC Protocol for Wireless LANs[END_REF]. The IEEE 802.11 was designed for single hop networks. Although it can support ad hoc communications, [START_REF] Xu | Revealing the problems with 802.11 MAC protocol in multi-hop wireless networks[END_REF] shows that it is not intended to support multi-hop wireless communication. This limitation has been raised in [START_REF] Xu | Does the IEEE 802.11 MAC Protocol Work Well in Multihop Wireless Ad Hoc Networks?[END_REF], too. It is claimed that the random access scheme deployed in the standard still suffers from the hidden terminal problem. Also, [START_REF] Cetinkaya | Cooperative medium access protocol for dense wireless networks[END_REF] points out the limitation of the back-off algorithm deployed in the IEEE 802.11 in DCF mode, since it leads to a short-term unfairness, while a short term-fairness is required by real time traffic to reduce the delay.

To support Quality of Service (QoS), a new coordination function has been introduced in the IEEE 802.11e [START_REF] Benveniste | EDCF Proposed Draft Text[END_REF][START_REF] Mangold | IEEE 802.11e wireless LAN for quality of service[END_REF]. The idea behind is to provide priorities to support different kinds of traffic. The new coordination function is called the Enhanced Distributed Channel Access (EDCA). It manages eight traffic queues; each of them is dedicated for a specified Access Categories (four Best Effort categories, Background, Video, and Voice). Each queue is characterized by a dedicated CW min , CW max and the Arbitration IFS Number (AIFSN). The latter is used to compute the AIFS that replaces the SIFS (used in IEEE 802.11 in DFC mode). With EDCA, nodes contend for Transmission Opportunities (TXOPs), where a TXOP is a period of time defined by duration and an offset. The duration of a TXOP depends on the access category. To ensure fairness, a TXOP limit is introduced. A node is able to transmit frames as long as it does not exceed the TXOP limit. Thus, EDCA provides fair channel access among the different traffic categories.

Nevertheless, the introduction of quality of Service consideration in the IEEE 802.11e with the EDCA function shows limitations [START_REF] Hiertz | IEEE 802.11s -mesh deterministic access[END_REF]:

1. The EDCA is intended to work in a fully distributed way, leading to inevitable collisions due to node contention.

2. The EDCA has been designed for single hop communication. A node can access the channel only if the latter is idle. When the number of nodes is high, the contention increases yielding to more unsuccessful transmissions. The contention window size increases and the EDCA is, therefore, less efficient.

3. The EDCA does not consider any node cooperation. Hence, a node in the edge of a wireless network, detects the medium as idle more often than a node located in the core of the network. Therefore, with the absence of cooperation between nodes, an edge node risks to congest its neighbors.

4. The EDCA suffers from the exposed terminal problem that leads to a waste of bandwidth due to unnecessary retransmissions.

Multiple Access Collision Avoidance-By Invitation (MACA-BI)

The Multiple Access Collision Avoidance By Invitation is a receiver-initiated protocol. It is designed mainly to tackle the additional delay and control packet overhead introduced in the sender-initiated protocols. With MACA/BI, the receiver requests the sender to initiate a data transmission. Thus, the handshake of RTS/CTS deployed in the sender-initiated protocols is replaced by a Ready-To-Receive (RTR) packet, reducing this way the number of exchanged control packets.

In the receiver-oriented protocols, the transmitter is unable to initiate a transmission unless it is polled by the receiver. MACA/BI implements a traffic prediction algorithm in the receiver so that the latter can predict when data should be requested from the sender. [START_REF] Talucci | MACA-BI (MACA By Invitation), A wireless MAC protocol for high speed ad hoc networking[END_REF] proposes and algorithm based on the packet queue length and data arrival rate at the sender. It is shown that MACA/BI protocol has good performance in case the traffic patterns are predictable; otherwise, its performance degrades to that of MACA [START_REF] Karn | MACA-a new channel access method for packet radio[END_REF].

Similar to MACA/BI, the Receiver Initiated Busy Tone Multiple Access (RI-BTMA) [START_REF] Wu | Receiver-Initiated Busy-Tone Multiple Access in Packet Radio Networks[END_REF] specifies that only destination node is allowed to transmit the busy tone, and hence the number of exposed nodes is reduced [START_REF]A Survey on Medium Access Control in Wireless LANs, Bogdan Roman[END_REF]. Nevertheless, this technique is still prone to collisions, since the destination node needs to decode the frame header in order to identify the destination address.

Power Aware Medium Access with Signaling (PAMAS)

In order to enhance the carrier sensing protocol performance, some researchers have introduced multi-channel protocol. The Power Aware Medium Access with Signaling (PAMAS) [START_REF] Singh | PAMAS-Power Aware Multi-Access protocol with Signaling for ad hoc networks[END_REF] is one of these protocols. Like IEEE 802.11, PAMAS makes use of a handshake of RTS/CTS to bypass the hidden terminal problem. The novelty of PAMAS is to perform the RTS/CTS exchange in a dedicated channel, called signaling channel; while DATA exchange is performed in a separate channel. Upon a data packet receipt, the packet destination node sends a busy tone over the signaling channel. While listening to the busy tone, neighboring nodes deduce that the DATA channel is busy and delay their transmissions. In [START_REF] Kumar | Medium Access Control protocols for ad hoc wireless networks: A survey[END_REF], the authors highlighted that the radio transceiver turn-around time may affect the performance of PAMAS and further insights considering this item are needed.

Multi Channel CSMA MAC Protocol

The basic idea behind the Multi Channel CSMA MAC Protocol is to divide the available bandwidth over N different channels using either the FDMA or the CDMA techniques. The multi channel CSMA MAC protocol favors the use of the same channel last used by a node; i.e. a sender uses the last channel it has used in case the latter is found free. Otherwise, the sender chooses another channel randomly. In case no free channels are available, the sender performs a back-off mechanism and delays its transmission. [START_REF] Kumar | Medium Access Control protocols for ad hoc wireless networks: A survey[END_REF] highlights the ability of the multi channel CSMA MAC protocol to support high traffic load even with insufficient number of channels comparing to the number of nodes. Nevertheless, the protocol shows lower performance at lower traffic load and with a small number of nodes mainly because idle channels appear leading to the underutilization of the available resources.

Carrier Sense Multiple Access with Collision Notification (CSMA/CN)

A more recent work aiming to enhance the carrier sensing protocol performance is presented in [START_REF] Sen | CSMA/CN: carrier sense multiple access with collision notification[END_REF]. The new protocol is called Carrier Sense Multiple Access with Collision Notification (CSMA/CN). The principle of this protocol is inspired from the CSMA/CD protocol. With CSMA/CN, each node is equipped with two antennas: one for normal transmission and the other is used to capture the notification. While receiving the packet, the receiver performs a cross-layering between the MAC layer and the physical layer to detect the collision. When the collision is detected, it sends a notification to the sender. Upon the notification receipt, the sender aborts its transmission, leaving this way, the channel free for another node in its vicinity.

Contention-free TDMA-based MAC protocols

In order to improve the MAC layer performance, some protocols focus on eliminating the random access nature of contention-based MAC protocols by proposing a contention-free approach. The contention-free MAC protocols appear then as a promising alternative to contention-based protocols, since they eliminate the hidden terminal problem and provide guaranteed channel access. In particular, TDMA has shown good performance [START_REF] Kumar | Medium Access Control protocols for ad hoc wireless networks: A survey[END_REF], since it reserves for each node a guaranteed period of time to access the channel. In the most basic TDMA scheme, the channel resources are divided into frames each of them is composed of time slots. The number of time slots corresponds to the number of nodes in the network. Under the assumption that all nodes have always a packet to transmit, the pure TDMA scheme is optimal in terms of throughput for fully connected networks [11]. In multi-hop environment, two challenging problems are to be tackled while applying TDMA access technique: the node synchronization and slot assignment.

TDMA-based protocols require a strict synchronization among nodes in the network in order to capture the beginning of each time frame, and to avoid collisions due to time slots overlapping. In a distributed multi-hop environment like the wireless ad hoc networks, this task is hard to achieve and can be expensive in terms of additional control overhead. Node synchronization in wireless ad hoc networks is a relevant research topic that is beyond the scope of our work. We refer the readers to some surveys for more details about the node synchronization mechanisms in a distributed environment [START_REF] Wu | Clock synchronization of wireless sensor networks[END_REF], [START_REF] Prakash Ranganathan | Tim Synchronization in wireless sensor networks: A Survey[END_REF], [START_REF] Latha | Clock Synchronization in Distributed Systems[END_REF], and [START_REF] Christmann | Multi-hop Clock Synchronization in Wireless Ad-Hoc Networks[END_REF]. Consequently, in the present work, as well as for the detailed TDMA-based masterpiece works, we assume that nodes 'clocks are perfectly synchronized.

Concerning the slot assignment issue, the spatial reuse appears as an interesting solution to increase the performance of an adapted TDMA scheme. Consequently, the problem of optimizing the slot assignment, e.g. minimizing the TDMA frame size, rose. Most of the TDMA scheduling policies are NP-complete [START_REF] Ephremides | \Scheduling Broadcasts in Multihop Radio Networks[END_REF][START_REF] Arikan | Complexity Results about Packet Radio Networks[END_REF]. For instance, [11] shows that an optimal TDMA schedule is equivalent to a k-hop coloring problem which is NP hard. Consequently, sub-optimal and decentralized solutions have been investigated to cope with slot assignment issue.

We believe that the frame size has a major impact on the performance of TDMA-like MAC protocols. We propose, then, to classify MAC protocols for wireless multi-hop ad hoc into (1) fixed frame size-based and (2) dynamic frame size-based MAC protocols.

Fixed frame size-based MAC protocols

Fixed TDMA frame size-based MAC protocols are the most popular class among the TDMA-based MAC protocols for wireless multi-hop ad hoc networks. As mentioned above, this observation is a direct consequence from the complexity of achieving strict synchronization in a distributed and inherent environment such ad hoc multi-hop networks. In the sequel, we will survey the most relevant works based on fixed TDMA frame size in wireless ad hoc networks. The IEEE 802.11s [START_REF][END_REF] community has developed new amendment to enhance the EDCA performances and enable multi-hop communication within a wireless mesh network. Originally designed for wireless mesh networks, this amendment can be used in ad hoc networks. The IEEE 802.11s aims to connect multiple wireless mesh networks in an ad hoc fashion, such that the different Mesh Points are no longer wired, but can communicate with each other wirelessly. The TDMA capabilities have seduced the IEEE 802.11s community; thus, in addition to the default medium access scheme; i.e. the EDCA function, an optional MAC scheme called Mesh Deterministic Access (MDA) has been defined.

a) Standardization Activities: IEEE 802.11s Mesh Deterministic Access

The MDA works in two different modes: a random access mode where nodes contend in advance for a Transmission Opportunity (TXOP) also referred as MDAOP, and a scheduled access mode where DATA packets are transmitted. It is to mention that the random channel access is the default medium access mode in IEEE 802.11s MDA. Fig. 5 depicts the frame structure of the IEEE 802.11s MDA. The frame is defined as the time interval between two consecutive Delivery Traffic Indication Message (DTIM) beacons. A frame in the IEEE 802.11s MDA is divided into a fixed number of time slots of 32µs each. A node equipped with the mesh deterministic access contends to reserve an MDAOP. The reservation process is as follow:

1. The node intending to reserve a transmission opportunity uses CSMA/CA and back off to send a so called action frame; i.e. control frame, including an MDAOP Setup request Information Element (IE). The latter specifies:  The duration, in terms of number of time slots, of the MDAOP,  The offset of an MDAOP defined as MDAOP starting point with regard to the beginning of the frame,  And the periodicity indicating the number of sub-intervals reserved during the DTIM interval; i.e. a periodicity set to 0 indicates a single reservation that will not be repeated [START_REF] Hiertz | IEEE 802.11s -mesh deterministic access[END_REF].

This MDAOP is advertised, and all MDA-capable neighbors hearing this advertisement are required to not initiate a new transmission during this MDAOP [START_REF]Draft STANDARD for Information Technology-Telecommunications and information exchange between systems-Local and metropolitan area networks-Specific requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications[END_REF].

2. The node receiving the MDAOP Setup request accepts or declines the request. In case the requested MDAOP does not interfere with the MDAOPs the receiver node is aware of, the request packet is accepted; otherwise it is declined.

3. Once the MDAOP is accepted, the receiver as well as the requesting node broadcast the new MDAOP setup within their neighborhood. 4. The receiver and the requesting node also broadcast an interfering report times (the TX-RX times reports of the one-hop neighbors) in order to spread the MDAOP reservation within the two-hop neighborhood. According to [START_REF]Draft STANDARD for Information Technology-Telecommunications and information exchange between systems-Local and metropolitan area networks-Specific requirements-Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications[END_REF], the interfering reports are sent during Mesh DTIM periods so that MDA-capable nodes may receive this report.

[34] and [START_REF] Hiertz | IEEE 802.11s MAC fundamentals[END_REF] studied the performance of the IEEE 802.11s MDA in different scenarios. It is shown that the amendment overcomes the hidden terminal problem as well as the exposed terminal problem thanks to the deployed reservation scheme based on the two-hop neighborhood knowledge. Moreover, the protocol presents higher probability of successful transmission than the EDCA MAC protocol, thanks to its scheduled channel access. Nevertheless, the IEEE 802.11s MDA suffers from some limitations.

The main limitation is that the MDA remains an optional channel access technique that is not deployed in all the nodes. Therefore, MDA non capable nodes are concurrent to MDA capable nodes. The standard specifies that an MDAOP owner accesses the channel immediately; while all other devices perform back off mechanism. However, we argue that the reservation mechanism deployed in the IEEE 802.11s is impacted by non-MDA capable nodes. With the IEEE 802.11s MDA, an MDA capable node has no way to prevent a non-MDA node from accessing the channel [START_REF] Hiertz | IEEE 802.11s -mesh deterministic access[END_REF]. On the other hand, non-MDA capable nodes are not aware of the MDAOP schedules. Therefore, an MDAOP owner may find the channel busy during its reserved MDAOP due to a non-MDA capable ongoing transmission. In this case, the MDAOP owner needs to defer its transmission until the channel becomes free.

In addition, the MDA mechanism induces additional delays, and implies repetitive reservations for the same node. In fact, one of the specifications of the MDA is that MDAOP duration cannot be extended. Thus, in case the MDAOP owner defers its transmission, the MDAOP duration is shortened, and the node needs to reserve another MDAOP according to its traffic rate.

To prevent the MDA capable nodes from monopolizing the channel, the IEEE 802.11s MDA defines an MDA Access Fraction (MAF) limit. The MAF is the ratio of the total duration of the MDAOP a node is involved in (its own MDAOP, the MDAOP of its one-hop and two-hop neighbors) in a frame to the duration of the frame [START_REF][END_REF][START_REF] Hiertz | IEEE 802.11s: WLAN mesh standardization and high performance extensions[END_REF]. We argue that the MAF presents a limitation to the adaptability of the MAC protocol to high loaded networks.

With the IEEE 802.11s MDA, the density (defined as the number of maximum one-hop neighbors) is restricted by the MAF ratio limit. When a node sends a request to reserve an MDAOP, it first verifies that the requested MDAOP does not exceed the MAF of all its neighbors. Also, the same check is made from the request receiver side. In case one of the checks fails, the request is rejected and the new node cannot join the network. Thus, the MAF ratio limit restricts the density of the network.

Finally, the IEEE 802.11s MDA mechanism is also constrained by the fixed frame size. Suppose a network composed of nodes such that the number of non-MDA capable nodes surpasses that of MDA capable nodes. Consequently, only few portions of the frame are reserved for scheduled access. Instead, the portion of the frame available for best-effort wireless access is important and thus, the MAC layer remains fundamentally random access based scheme. Consider now, a network where only MDA capable nodes exist. In high traffic loads and with an important number of nodes, the MDA frame size cannot provide sufficient scheduled resources to all nodes in the network. In the other hand, when only few nodes exist, the bandwidth is wasted due to the underutilization of the available resources.

b) MAC protocols based on the mini-slot concept i. Five-Phase Reservation Protocol (FPRP)

FPRP [START_REF] Zhu | A Five-Phase Reservation Protocol (FPRP) for mobile ad hoc networks[END_REF] is one of the most important works that has introduced the random access reservation for mobile ad hoc networks. FPRP proposes a five phase handshaking mechanism. It divides the frame into two sub-frames: the Reservation sub-frame (RF) for slot reservation, and the Information sub-frame (IF) for data transmission. RF is composed of M Reservation Slots (RS). Each RS corresponds to the time needed to perform M reservation cycles. The latter consists of five phase handshaking performed to compete for a slot in the IF sub-frame.

 The first phase is intended to allow the nodes to request for reservations. It is called the Reservation Request (RR) phase.  Based on a random access, collisions are likely to occur during the first phase.

FPRP specifies that nodes report these collisions during the second phase, known as the Collision Report (CR) phase.  The third phase is the Reservation Confirmation (RC) phase, where node reservations are confirmed.  The fourth phase, called the Reservation Acknowledgment (RA) is indented to spread the reservation confirmation within the two-hop neighborhood. During the RA, each node that hears a reservation confirmation, acknowledges by sending a RA packet. This way, the reservation confirmation is known by the two-hop neighbors.  Finally, FPRP performs the packing and eliminating (P/E) phase.

In terms of graph coloring, [11] shows that FPRP and RAND (random) [START_REF] Ramanathan | A Unifed Framework and Algorithm for (T/F/C)DMA Channel Assignment in Wireless Networks[END_REF] require almost the same number of colors for different topologies. This gives the FPRP protocol the flexibility to adapt to network variations. Nevertheless with FPRP, a node has no guarantee to own a slot in every time frame due to the random access nature of the protocol. A receiver oriented MAC protocol for ad hoc networks (CROMA) is presented in [START_REF] Coupechoux | CROMAa slotted MAC protocol for MANETs with multislot communications[END_REF]. CROMA is based on a reservation mechanism combined with a polling scheme. For each reserved slot, the receiver node of a communication link plays the role of a base station and polls several senders among its neighbors. The frame structure defined by CROMA is depicted

ii. Collision-free Receiver-Oriented MAC (CROMA)

0 1 2 --- ----L-1 1 Frame = L slots REQ RTR DATA
in Fig. 6. A frame is divided into a predefined number of equal time slots. Each time slot is composed of three mini-slots:

1. REQ-mini-slot (Request): used by the requesting node to send a request to the intended receiver, 2. RTR-mini-slot (Ready-to-Receive): used (1) to acknowledge a sender request in case the requested slot is available, (2) to acknowledge previous data transmission, and (3) to perform polling among the senders having succeeded a reservation.

3. DATA-mini-slot: this mini-slot is used by the sender that has been polled in the preceding RTR-mini-slot, to transmit its DATA packet.

CROMA is able to reach higher throughput than IEEE 802.11 in DCF mode [START_REF] Coupechoux | CROMAa slotted MAC protocol for MANETs with multislot communications[END_REF]. However, the polling scheme introduced by CROMA may be penalizing, since a successful reservation does not imply an immediate DATA transmission. Instead, the sender node needs to wait to be polled by the intended receiver which adds additional delays. Following the same philosophy of dividing a slot into multiple mini-slots, [START_REF] Tang | A Protocol for Topology-Dependent Transmission Scheduling in Wireless Networks[END_REF] proposes the Collision Avoidance Time Allocation (CATA). In CATA, a distributed reservation combined with a handshake mechanism is deployed to reserve time slots. Like CROMA, the frame length in CATA is fixed to a predefined number of time slots; each of them is divided into 5 minislots as it is depicted in Fig. 7.

iii. Collision Avoidance Time Allocation (CATA)

To handle the hidden terminal problem, CATA specifies that each node receiving data in a given time slot, sends a Slot Reservation (SR) during the first Control Mini Slot (CMS1). To block any broadcast or multicast reservation while a unicast transmission is ongoing, both the sender and the receiver send a Not-To-Send (NTS) packet during the fourth control mini slot (CMS4). CATA deploys a reservation scheme in order to avoid packet collisions. The reservation scheme is the following:

1. The sender node senses the channel during the first control mini slot (CMS1),

0 1 2 --- ----L-1 1 Frame SR RTS DATA NTS CL RTS DATA CTS NTS CMS1 CMS2 CMS4 CMS3
2. In case the channel is perceived clear during the CMS1, the sender sends an RTS during the second control mini slot (CMS2), and listens to the channel during the third CMS.

3. In case the reservation succeeds, the sender receives a Clear To Send during CMS3.

4. In case of a broadcast or multicast RTS, the sender detects the failure of the reservation if an NTS is received during the CMS4.

Unlike CROMA that needs a new algorithm to support flooding, CATA has the advantage to establish unicast, multicast, and broadcast communications.

iv. On-demand Dynamic Slot Assignment (ODSA) and Distributed Packet Reservation

Multiple Access (DPRMA)

In the same family of MAC protocols for ad hoc networks based on splitting each single slot into multiple mini slots, the On-demand and Dynamic Slot Assignment (ODSA) [START_REF] Xu | An on-demand and dynamic slot assignment protocol for Ad Hoc networks[END_REF] and the Distributed Packet Reservation Access (DPRMA) [START_REF] Jiang | A Simple Distributed PRMA for MANETs[END_REF] are proposed. ODSA assigns the time slots based on information of the two-hop neighborhood. It also deploys an on-demand slot reservation which renders it more flexible and adaptive to application requirements and network load. Nevertheless, [START_REF] Xu | An on-demand and dynamic slot assignment protocol for Ad Hoc networks[END_REF] points out that the frame size in ODSA is predefined to a number of time slots sufficient enough to cover the overall network. Thus, ODSA does take advantage from the on-demand reservation only in case all the time slots are reserved; otherwise, bandwidth is wasted due to unused time slots.

The Distributed Packet Reservation Multiple Access (DPRMA) introduces quality of service by mixing voice and data traffic. It attributes higher priority to voice calls. The channel is slotted and each time slot is divided, then into (m+1) mini-slots. With DPRMA, contention is made with handshake of RTS/CTS during the mini slot 0. Two cases are to be considered:

1. Nodes handling voice traffic start the contention with a probability 1, while data traffic nodes start the contention with a probability p lower than 1.

2. If a node wins the contention in slot 0, it starts data transmission during the remaining mini slots. In case of voice traffic, the slot is reserved for several frames; otherwise nodes handling data traffic use the selected time slot only once; i.e. in one frame cycle.

Dynamic frame size-based MAC protocols a) Unifying Slot Assignment Protocol Multiple-Access (USAP-MA)

Dynamic frame size concept offers a topology-adaptive solution.

In [15], Young introduced a new dynamic TDMA channel access technique, called USAP-MA (Unifying Slot Assignment Protocol Multiple-Access) to ensure effective channel utilization. USAP-MA is an extension of the USAP protocol [START_REF] Young | USAP: a unifying dynamic distributed multichannel TDMA slot assignment protocol[END_REF] which is part of the fixed frame sized MAC protocols for multi-hop ad hoc networks. The Unifying Slot Assignment Protocol defines a cycle as a set of N frames; each of them is composed of M time slots as it is depicted in Fig. 8. In USAP, N and M are fixed numbers. The first slot of each frame is dedicated to one particular node in the network. Thus, only N nodes can communicate with each other based on USAP MAC protocol. Each node sends one control packet called Net Manager Operational Packet (NMOP) per cycle; i.e. N frames. An NMOP is used to exchange TDMA schedules in the two-hop neighborhood. It incurs the following information:

 ST i (s): sets to 1 in case node I sends packet in slot s,  SR i (s): sets to 1 in case node I receives packets in slot s,  NT i (s): sets to 1 in case one of node I neighbors transmits data in slot s.

With USAP, a new node joining the network should first sense the channel for a whole cycle in order to collect the NMOPs transmitted by its neighbors. Once the slot assignment schedule is recognized by the new node, it assigns to itself one free slot. Finally, the new node announces its selection to its neighbors by transmitting an NMOP control packet.

In USAP, the couple (N, M) should be configured in advance and needs to be large enough to consider the case where the network has a maximum number of nodes. Despite its simplicity, USAP suffers from lower channel utilization due to the over-dimensioned cycle; yielding to unassigned slot appearance.

To alleviate the low channel usage of USAP, Young proposes the USAP Multiple Access [15] as an extension of USAP. USAP-MA is distinguished by three main features:

1. Dynamic frame length: Unlike USAP, the frame length in USAP-MA is dynamic.

Each node sets the frame length according to the number of nodes in its vicinity. Hence, the frame length adapts to network density; i.e. if the number of nodes surrounding a node N is small, node N can set a short frame size. This way, the number of unassigned slots decreases.

The frame length is a power of 2:

The frame size in USAP-MA is set as a power of two. This feature ensures collision free packet transmission between nodes having different frame sizes.

0 1 2 --- ----N-1 N Frames = 1 cycle M-1 M-2 M-3 --- --- --- 2 1 0
For NMOP time 3. The slot poaching: USAP-MA follows the same slot assignment procedure as the USAP protocol; i.e. a node first, listens to the channel for a whole cycle to collect the NMOP of its neighbors. Second, the node chooses a free slot based on the slot assignment schedule in its contention area. Finally, the node broadcasts its selection. While USAP protocol defines a large frame size to consider a maximum number of nodes, USAP-MA tends to shorten the frame size instead. With USAP-MA, nodes are continuously looking for unassigned slots in the frame. If a node N assigned slot x detects a free slot y with y<x, it releases the slot x and assigns to itself the slot y. This technique is called the slot poaching. When all the slots in the latter half of the frame become unassigned, the frame is halved.

Despite its adaptability to topology variations, [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF] argues that USAP-MA still suffers from low channel utilization, since it resorts to doubling the frame size in case no unassigned slot is found. This way, free slots appear at the end of the frame leading to bandwidth wastage.

b) Extended-Adaptive Slot Assignment Protocol (E-ASAP)

The same technique of setting the frame size as a power of two is adopted in [START_REF] Kanzaki | Dynamic TDMA slot assignment for ad hoc networks[END_REF] and further enhanced in [START_REF] Kanzaki | On a TDMA Slot Considering the Amount od Traffic in Wireless Sensor Networks[END_REF]. Kanzaki et .al propose the Extended Adaptive Slot Assignment Protocol (E-ASAP). In E-ASAP, the first slot of each frame is reserved for new incoming node request. The E-ASAP protocol is a topology-based MAC protocol, since it assigns slots based on the two-hop neighborhood information. The slot assignment in E-ASAP follows a three-way handshake mechanism:

1. First, the new node broadcasts a Request (REQ) packet to its one-hop neighbors during the first slot of the frame, 2. The neighbors that receive the REQ packet switch from the TRANSFER mode to the CONTROL mode, and respond by sending information (INF) packets during their own assigned slots.

3. Based on the slot assignment schedule collected from the received INF packets, the new node first sets its frame size to 4 time slots, the minimum frame size defined in the E-ASAP protocol. Then, the node passes through three different procedures to select an appropriate time slot: a) Getting an Unassigned slot (GU): The frame size is set to the minimum frame size defined in the E-ASAP; i.e. 4 time slots. If there is at least one free slot in the frame with the current frame size, apart from the first slot which is reserved to new incoming nodes, the node assigns to itself that slot.

b) Releasing Multiple Assigned (RMA) slots: in case the new node does not find a free slot with the current frame size, the node checks whether one of its neighbors is assigned multiple slots. If it is the case, it releases one of these slots and assigns it to itself. c) Doubling the Frame size (DF): in case the new node fails to find a free slot by the GU and the RMA procedures, it doubles the frame size. Doubling the frame size consists of three main steps: (1) the frame size is first doubled, (2) the nodes assigned slots with the current frame size, are copied to the second half of the new sized frame, (3) Finally, the GU and the RMA are applied to select a free slot.

In [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF], it is shown that E-ASAP succeeds to achieve better channel utilization in comparison with USAP and USAP-MA. Nevertheless, we argue that E-ASAP still suffers from two major limitations: First, the slot assignment scheme in E-ASAP assumes that an assigned slot is always a used slot, which is not usually the case. Thus, a node may have multiple assigned slots regardless its effective bandwidth consumption, leading to bandwidth wastage.

In addition, the frame size set as a power of 2 results in an unfairness issue which impacts the MAC layer performance.

Notice that a detailed analysis of the E-ASAP performance is provided in Section 3.4.1 of Chapter 3.

Conclusion

Wireless Ad hoc networks constitute one of the key technologies for next generation wireless networks. The medium access protocol has a major impact on the network performance. In this chapter, we have presented insights on the main characteristics of an efficient medium access control protocol for wireless ad hoc networks. We also presented masterpiece works that can be found in the literature. From this chapter and the bibliographic study, some main conclusions can be drawn: MAC protocols for wireless multi-hop networks are mainly divided into two families: contention-based and contention-free MAC protocols. For the former group, nodes contend to acquire the channel for each packet transmission; while for the latter group the channel is reserved for a certain period of time.

We have highlighted the limitations of the contention-based MAC protocols to achieve higher throughput because of their random channel access. We pointed out that the widespread IEEE 802.11 DCF is not suitable for multi-hop communications, and shows lower performance at high input loads due to its back off mechanism.

To support quality of service (QoS), TDMA based conflict-free schemes have seduced the research community because of their ability to provide guaranteed channel access.

We have proposed a classification of the TDMA-based MAC protocols based on the frame size characteristic; i.e. static or dynamic.

The fixed frame sized MAC protocols follow the same reservation scheme: a random channel access phase followed by a scheduled channel access. The former is used to contend for a time slot selection, while the latter is dedicated for DATA packet exchange. We have shown that fixed frame size MAC protocols have the important drawback of wasting bandwidth due to the use of mini-slot for control management, or by over-dimensioning the frame size such that unassigned slots might appear. Also, we pointed out the famine risk encountered with fixed frame size MAC protocol by analyzing the IEEE 802.11s mesh deterministic access for multi-hop ad hoc networks. Dynamic frame size based protocols appear then as a promising solution to ensure efficient channel utilization and better quality of service. Nevertheless, to our knowledge, there is a small amount of research that has been proposed to support a dynamic frame size. Two major proposals in the literature have been studied in this chapter: USAP-MA and E-ASAP. They have the drawback of either wasting bandwidth due to unassigned slots appearance, or attributing slots regardless the effective traffic rate of the nodes, or presenting a per-node unfairness problem.

We believe that there is still room for improvements over the design of a reliable and efficient MAC protocol for wireless ad hoc networks that takes full advantage of the flexibility of a dynamic frame size to provide better channel utilization and increase the fairness between the nodes. We are confident that a suitable dynamic frame size design can tackle the unassigned slot appearance, and guarantee better per-node fairness.

In the next chapter, we will present our proposal that consists of a new TDMA-based channel access technique that aims to increase the channel utilization by keeping the frame size as lower as possible.

This new TDMA-based technique is the basis of a new TDMA-based MAC protocol for wireless multi-hop ad hoc networks called the One shot Slot TDMA-based Reservation (OSTR) MAC protocol . In chapter 3, we will first provide a detailed description of our proposal. In order to evaluate the OSTR performance in terms of channel utilization and pernode fairness, a comparison study will be held between the IEEE 802.11 in DCF mode and the OSTR protocol. In a second step, we will study the behavior of the new frame size increase technique introduced by OSTR with the frame size increase technique incurred by the E-ASAP protocol. The choice of the E-ASAP protocol is based on the bibliographic study held in this chapter. This study has highlighted that E-ASAP has the most interesting performance in terms of channel utilization among the dynamic frame size-based MAC protocols.

Introduction

Efficient bandwidth exploitation is fundamental in order to increase the overall system performance especially in a hostile environment where channel resources are scarce, such as wireless ad hoc environment. In order to enhance bandwidth exploitation in multi-hop ad hoc networks, a good MAC protocol design needs to accomplish three main objectives: optimally use the scarce resources, fairly share the available bandwidth between contending nodes, and smoothly adapt to varying network topologies.

In order to accomplish these objectives, different amendments to the existing MAC protocols for ad hoc networks need to be brought in. As explained in Chapter 2, the heir of contention-based MAC protocols; i.e. IEEE 802.11 may not be the optimal choice to support multi-hop communication. As opposite to contention-based schemes, conflict-free with reservation mechanism are favored, since they enhance bandwidth exploitation by coordinating a guaranteed channel access. To further increase throughput, spatial reuse schemes have taken lots of attention. Finally, the necessity to address varying topologies gives rise to dynamic and network density adaptive MAC protocols.

In the previous chapter, we underlined the capabilities of TDMA-based MAC solutions to ensure conflict-free channel access. It has also been shown that fixed frame size-based techniques may not be the appropriate choice to optimally exploit the bandwidth.

In this chapter, we turn to the dynamic frame size-based family of protocols to propose a new adaptive solution to multi-hop wireless ad hoc networks. To bypass the necessity of a trade-off between the predefined frame size and the network density, we adopt a dynamic frame size. To further improve bandwidth exploitation, we focus on maintaining the frame size as low as possible. Finally, to further favor throughput, we exploit the capabilities of a spatial reuse scheme. Our proposition is called OSTR (One shot Slot TDMA-based reservation) MAC protocol.

Four master motivations are behind the OSTR design. First, a TDMA-based protocol can provide a better channel utilization if the frame size is maintained as low as possible. Second, the inherent ad hoc environment and node movement are better managed with a dynamic solution. Third, per-node fairness can be enhanced if the MAC protocol design respects node requirements. Finally, the energy efficiency can be achieved thanks to a shorter frame size.

OSTR introduces then, a new TDMA-based channel access technique that aims to increase the channel utilization and the energy efficiency by keeping the frame size as low as possible. It is based on a slot-by-slot reservation technique. The frame is dynamic and is built slot-byslot according to node arrival/departure to/from the network.

In the following, we will present the detailed description of our proposal. In Section 3.3, the robustness of OSTR in high loaded environment is highlighted via a set of simulations comparing OSTR with the IEEE 802.11 DCF. The good performance of OSTR in terms of fairness and network throughput in multi-hop scenario are also shown. The effectiveness of the slot-by-slot frame size increase technique brought by OSTR is handled via analytical and experimental comparative studies between our proposal and the E-ASAP protocol [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF]. Finally, the chapter is concluded by a discussion about the pros and cons of each TDMA frame size increase technique; i.e. the slot-by-slot frame size increase, and setting the frame size as a power of two. The energy efficient capabilities of the OSTR protocol are tackled in chapter 4.

Most of the results of this chapter have been presented by the author in [START_REF] Sayadi | One shot Slot TDMA-based Reservation MAC Protocol for Wireless Ad hoc Networks[END_REF][START_REF] Sayadi | Comparaison of Two TDMA-based Channel Access Techniques over Wireless Ad hoc Networks[END_REF].

OSTR Protocol

OSTR: Protocol Overview

OSTR is a medium access protocol for mobile ad hoc networks that schedules transmissions in a slotted environment. It is a dynamic and distributed protocol that operates on a single-frequency channel.

The time is organized in frames; each of them is composed of two sub-frames: a CONTROL sub-frame, where channel access follows a CSMA/CA access scheme, and a DATA sub-frame, where channel access is scheduled. The CONTROL sub-frame is intended to allow new incoming node requests and to resolve slot conflicts. During DATA sub-frame, each node sends DATA packets and some specific control packets (Frame Change, REPLY) in its reserved slot.

OSTR is topology-based, where two-hop neighborhood information monitor the slot assignment. It is also reservation-based, since a reservation mechanism is deployed to assign slots to nodes in the network. The bandwidth consumption is enhanced thanks to ; (1) a spatial reuse of resources favoring slot re-utilization in order to keep the frame size as low as possible, (2) an on-demand slot assignments, i.e., slots are allocated only if needed with respect to node requirements, (3) the appointment mechanism, to deal with frame synchronization issue described in Section 3.2.4.c. During control sub-frame nodes follow a CSMA/CA [3] contention scheme to get channel access. This sub-frame is intended for exchanging control information to allow new arriving nodes to request a slot reservation in order to join the network, or to announce a conflict, etc. During DATA sub-frame, each active node accesses the channel during its reserved slot to send data packets. These data packets are of fixed length, fragmentation and reassembly are done by higher layers.

OSTR protocol: Frame Structure and Packets Format

b) Packets Format

This section describes the different packet formats and the MAC header of the data packets. All MAC fields are also defined. Their significance will be detailed later in the protocol description.

Common Parts

The control packet formats and the MAC header of the data packets are depicted in Fig. 10. Generic information, e.g. protocol version, is given in the frame control field (fc). The field fcs (frame check sequence) contains a CRC (cyclic redundancy code) computed on all the fields of the MAC header and on the frame body. Src.ad and Dest.ad give the MAC addresses of the packet source and the packet destination respectively. The field Src.slt contains the packet source's assigned slot.

T cur field gives the current frame size of the packet source; i.e. if a control packet is sent during frame j, T cur includes frame j size.

Length field denotes the length in bytes of the packet. The Type field is 3 bits in length and indicates the type of the packet in process. There are six packet types defined in OSTR protocol and represented in Table 1.

HELLO Control Packet

In OSTR, a HELLO packet has two functions: tracking topology changes and updating neighborhood information. A HELLO packet is sent periodically, with interval set to 2 seconds. HELLO packets are only sent during contention-based sub-frame. That is, nodes periodically perform a CSMA/CA access scheme to transmit HELLO packets.

Apart from common fields, a HELLO packet includes a neighbor update list. The neighbor update list contains one-hop neighbors' MAC addresses (Nei.ad) and their assigned slots (Nei.slot).

REQ Control Packet

In OSTR, a REQ packet is generated each time a node needs to reserve a slot. It is sent during Control sub-frame, and consequently the Src.slot field is set to 0. The Req.slot field indicates the requested slot number. The field qs is used to indicate the required quality of service of the requesting node. This field could be used in future versions of the protocol.

REPLY Control Packet

In OSTR, a REPLY is used to respond to a node REQ. It has the same structure as a REQ packet. The fields Src.slot and req.slot indicate the REPLY source assigned slot and the reserved slot for the destination node, respectively.

In OSTR, only nodes with assigned slots have to send REPLY packets in order to avoid irrelevant slot assignment information. Indeed, a new node may be neighbor to another node that still waits for a DATA slot; thus the slot assignment maintained by that node is inconsistent. Because slot assignment is crucial for the correctness of OSTR, it is specified that only nodes that have already been assigned a DATA slot are allowed to confirm reservation and thus send REPLY packets.

FC Control Packet

An FC (Frame Change) packet has two functions, as detailed in section IV: disseminate a frame size change among all nodes and track the new sized frame start point.

In OSTR, an FC packet is generated each time a change in the current frame size occurs. When the frame size is modified, information about the new frame size and the new sized frame start point must be communicated within the whole network. These information are recorded respectively in T next field and Appoint field.

The Appoint field is set to an integer value denoting "the number of frames to wait for before starting a frame with the new size". The Appoint value is first initialized by the node announcing the frame size change and then it is decremented frame by frame. That is, consider an FC packet first sent during frame j and including an Appoint value of 3. As long as the frame j is not ended, all FC packets sent during frame j include 3 in Appoint field. Nodes that should transmit the packet during frame j+1, decrement the Appoint value. This process continues until Appoint value reaches 0. More details about appointment setting are given in section 3.2.4.c.

In OSTR, only FC packets must be rebroadcasted among all nodes in the network. Thus, Dest.ad field is set to broadcast address.

ERR Control packet

In OSTR, an ERR is generated to indicate a conflict. To enable all nodes in the conflict area be aware of the conflict, the Dest.ad field of an ERR packet is set to the broadcast address. The conf.slot and the conf.ad fields in an ERR packet are used to deal with collisions. If a conflict is detected, conf.slot field includes the conflicting slot; i.e. the slot during which the collision has occurred. To solve the conflict, the node that has detected the conflict, specifies which from the conflicting nodes will lose its assigned slot and puts its MAC address in the conf.ad field.

OSTR from an example

Before going into more detail in the protocol description, let us illustrate the main feature of OSTR, i.e. increasing the frame size slot by slot. This feature is illustrated in Fig. 11, which depicts a 4 node network {A, B, C, D} performing with a frame sized of 4 time slots (including slot 0 for CONTROL sub-frame). Nodes A, B, C and D are assigned slots 1, 2, 3 and 1 respectively. Node N wants to join the network. It first, senses the channel to collect information about its two-hop neighborhood. This is enabled thanks to the OSTR neighbor detection mechanism. This mechanism specifies that each node sends periodically a HELLO packet in the CONTROL sub-frame. A HELLO packet incurs the node unique identifier, the node assigned slot, and the node frame size for the HELLO sender itself and for all its one-hop neighbors as well. Hence, after listening to HELLO packets sent by node D and C, the new arriving node N recognizes:  That the current frame size in the network is set to 4 time slots (including slot 0 for CONTROL sub-frame),  That slots 1 and 3 are used by its one-hop neighbors (D and C),  That slot 2 is used by its two-hop neighbor (node B).

Consequently, no free slots are available with the current frame size for node N. The latter applies, therefore, for slot number 4. Mind that in this Section we are interested in the slot by slot frame size increase feature brought by the OSTR protocol. All the OSTR mechanisms are detailed further in the following Sections.

In a given frame j and in the CONTROL sub-frame (slot 0), node N initiates the reservation process, and sends a REQ packet to its one-hop neighbor assigned the lowest data slot: node D. In the same frame j, the latter sends REPLY packet during its corresponding slot (slot 1) to confirm node N reservation. Since node N applies for slot number 4 leading to the frame size increase in the network, node D generates an FC packet to flood in the network. Node D specifies an appointment after two time frames to switch to a frame sized of 5 time slots. The appointment value is computed based on the OSTR appointment mechanism explained further in this Chapter. Here, we give an intuitive explanation of the chosen value of 2 time frames.

During slot 1 of frame j+1, the FC packet is broadcasted and is then received by node N and C that are now aware of the switching time to the new frame size. Node C then, rebroadcasts the packet during its assigned slot 3. In frame j+2, node B broadcasts the FC packet which reaches node A. Hence, by the end of frame j+2, all nodes in the network are aware of both the new frame size: 5 time slots, and the switching time to the new sized frame. Also, by the end of frame j+2 two time frames has been elapsed since the flooding start performed by node D. Therefore, frame (j+3) includes 5 time slots. During frame (j+3) node N joins the network and starts transmitting DATA packets during its assigned slot: slot number 4. OSTR is designed to work in a completely distributed manner. It addresses varying topologies by a periodic exchange of HELLO packets. HELLO packets contain the assignment information of the sender and its one-hop neighbors. They are broadcasted in the contentionbased sub-frame and restricted to one-hop neighbors. Upon receiving a HELLO packet, the latter update their neighborhood information and discard the packet. The HELLO packet exchange also enables new incoming nodes to populate their neighborhood table based on which they select an appropriate time slot.

The HELLO sending period mainly depends on topology changes and on the application scenarios. In wireless sensor network scenario where node velocity is too low, a large HELLO sending period is more suitable. Whereas in vehicular network scenario, nodes move more frequently thus a smaller HELLO period is necessary to track topology changes. In this work we consider a periodic exchange of HELLO packets every 2s, according to the HELLO packet mechanism described in OLSR [START_REF] Jacquet | Performance analysis of OLSR multipoint relay flooding in two ad hoc wireless network models[END_REF].

b) Slot reservation mechanism

A new incoming node senses the channel to collect information about the slot distribution in its contention area. In case the sensing period ends without receiving packets, the new node starts a frame and assigns to itself the first DATA slot of the frame. Otherwise, the node receives HELLO packets periodically sent by its neighbors. Thus, a local view is now available for the new node making it possible to properly choose a time slot. Time slot selection: OSTR aims to achieve better channel utilization by diminishing the overall frame size in the network. Accordingly, a simple slot selection algorithm is adopted and is depicted in Fig. 12.The algorithm verifies three main characteristics: simple, depends only on two hop neighborhood information and favors the slot re-utilization if possible.

For the sake of clarity, an exemplification of time slot selection algorithm is given in Fig. 13. A network composed of 3 nodes performing channel access in a frame sized of 4 time slots is depicted in Fig. 13 (slot 0 is reserved for control information sent). The slot distribution in the frame is represented by a letter/number where the letter and number represent node identifier and its corresponding assigned slot number, respectively. In this example, nodes A, B, and C are assigned slots 1, 2 and 3, respectively.

A node D first joins the network. After populating its neighborhood table with information collected in HELLO packets, node D runs OSTR slot selection algorithm. In the first step of the algorithm, node D finds a FREE slot (slot 1); therefore, it chooses the slot 1 and exits. Afterwards, node N joins the network. It populates the Neighborhood table and runs slot selection algorithm. All slots in the frame are occupied by one-hop and two-hop neighbors of node N. Therefore, node N switches to step 2 of slot selection algorithm and applies for slot 4 leading to the frame size increase.

1. With a frame size of K DATA time slots, if there is at least one FREE slot, select the one with the lowest number, otherwise go to step 2; 2. Select the slot (K+1) and exit.

Request (REQ) transmission and REPLY generation:

Once the slot is chosen, the new node selects among its one hop neighbors the one which has been assigned the lowest slot number as REQ destination node, and reserves the intended slot by sending a REQ during the CONTROL sub-frame of the current frame. As the REQ packet is sent during the contentionbased control sub-frame, a collision between the REQ packet and other packets is not negligible. That's why; OSTR specifies that the requesting node launches a timer upon the REQ packet transmission. This timer is stopped upon the reception of the REPLY packet. In case no REPLY packet is received, the requesting node initiates a new reservation attempt. This process continues until either a REPLY packet is received, or the maximum attempts number is reached. Notice that the latter can be configured according to the application requirements (e.g. the application tolerated delay).

Upon the reception of a REQ packet, the behavior of REQ destination node differs on whether the frame size has to be increased or not. In fact, in case the sender has found a free slot without increasing the frame size, the REQ destination sends a REPLY during its assigned slot in the same current frame. Otherwise, the sender reserves a slot leading to the frame size increase. In this case, REQ destination node first sends a REPLY to confirm the new node reservation. Then, it sets an appointment based on the OSTR appointment mechanism described later in Section 3.2.4.c. Finally, it generates an Frame Change (FC) packet and broadcasts it.

REPLY listening and Transmission decision:

A requesting node that has sent a REQ during CONTROL sub-frame of frame j listens to the DATA sub-frame of frame j. If the end of the frame j is achieved without receiving a REPLY, the requesting node restarts a new reservation phase. In case a REPLY is received during DATA sub-frame of frame j, two cases are considered:

1. The frame size does not increase. In this case, a free slot in the current frame is reserved for the requesting node without increasing the frame size; i.e. T cur and T next fields in REPLY packet incur the same frame size. Thus, the requesting node starts DATA transmission immediately in the following frame; i.e. (j+1).

2. The frame size increases; i.e., no free slot is available for the requesting node with the current frame size. Thus, the REPLY packet includes a T next value superior to T cur . Consequently, the requesting node has to wait for an FC packet to get the appointment time and delays DATA transmission till this time is reached. It is to mention, that a REPLY packet has to be sent in the current frame, in order to confirm the requesting node reservation so that the latter won't attempt a new reservation in the following frame.

Reception of an FC: Upon the reception of an FC packet, nodes copy the appointment value and decrement it frame by frame. If appointment value = 0, then each node changes its frame length to the new frame size. Apart from the new arriving node that is not assigned a time slot yet, all nodes receiving an FC packet generate on their turn an FC packet and broadcast it in their assigned slots. In this section, the focus is on the OSTR frame size evolution. For more clarity, a simple case study is depicted in Fig. 14 where a network of 6 nodes is represented. A pair (letter/number) represents one node in the network, where the letter denotes the node identifier and the number stands for the node corresponding slot. Assuming a frame size of 4 time slots (including slot 0 dedicated to CONTROL sub-frame), node N joins the network and selects slot 4 according to the OSTR slot selection algorithm. The frame size is then increased from 4 to 5 time slots. We assume that node D has sent REPLY packet during frame j. In the same frame, node C sends a packet with frame size equals to 5 time slots. The new frame size then reaches node B. Therefore, by the end of frame j, the network is divided into two parts: the left side composed of nodes {A, E} with frame length of 4 time slots, and the right side composed of nodes {B, C, D, N} with a frame sized of 5 time slots. In Fig. 14, the frame size evolution is depicted for nodes E, A and B. Due to the frame size increase, frame j+2 starting point is moved. Thus, the absolute slot positions are modified and collisions occur resulting in a frame synchronization problem.

To handle frame synchronization problem, OSTR specifies that the increase of the frame size should be communicated among all nodes in the network, and the new sized frame is adopted simultaneously. This is reduced in resolving two issues: (1) how to disseminate the frame size change in the whole network, and (2) when nodes in the network should start the frame with the new size. Two mechanisms are defined in OSTR to deal with these issues: A flooding mechanism to disseminate information in the network and an appointment mechanism to set the starting point of the new sized frame.

ii. Flooding mechanism in OSTR Flooding a network is the simplest way to disseminate information in ad hoc networks. Flooding algorithm starts with a source node broadcasting a packet to all its one-hop neighbors. Each of these neighbors rebroadcasts the packet on its turn only if the packet is received for the first time. This process continues till all nodes in the network receive the packet.

Flooding is performed in the OSTR protocol to disseminate the frame change information within the network. It is performed with respect to the following:

1. It is performed only if a change (increase or decrease) in the frame size occurs.

It restricts to Frame Change (FC) packets.

3. It is performed during contention-free sub-frame; i.e., if node n sends REPLY packet during frame j, it generates the corresponding FC packet and sends it during its assigned slot in frame (j+1). All nodes enabling the FC packet forwarding transmit the packet during their own assigned slots. This choice is justified by two arguments: [START_REF]The Internet of Things -Strategic Research Roadmap[END_REF] avoiding additional delays in one hand, and (2) FC packets delivery guarantee in other hand. Indeed, in contention-based sub-frame, nodes perform back off mechanism leading to additional delays. Also, collisions might occur in CONTROL sub-frame leading to irrelevant information sending. Thus, OSTR specifies that FC packets are sent during contention-free sub-frame.

4. It is initiated by the node with the lowest assigned slot number among the one-hop neighbors of the arriving node. The reasons of this choice are twofold: first, minimizing flooding delay in OSTR. Indeed, when flooding is initiated by the node with the smallest slot number, the corresponding neighbors forward the packet during the same frame minimizing this way, the overall flooding delay. Second, this choice guarantees the sender's uniqueness and consequently avoids broadcast storm problem [START_REF] Wu | Survey: Broadcasting in Wireless Sensor Network, Ad Hoc Network and Delay -Tolerant Network[END_REF].

iii. Appointment mechanism in OSTR The key idea of the OSTR appointment mechanism consists on estimating the flooding completion time based on network characteristics. The mechanism enables to fix a date in the future expressed in terms of number of time frames to wait for, before switching to the new sized frame. The main feature of the OSTR appointment mechanism is reduced to answering the following question: After how many time frames should nodes start the new sized frame?

For the sake of clarity, an illustration of the OSTR appointment mechanism is shown in Fig. 15. In this example, the frame size in the example is fixed to 5 time slots, where slot 0 is reserved for new incoming node requests. At t 1 , the frame size increases. Therefore, node n performs three tasks:

1. Fixing an appointment for the new sized frame start (Action 1); 2. Generating an FC packet to disseminate the frame size change and the appointment in the whole network (Action 2), 3. Tracking the frames until the appointment time is reached. At this time all nodes in the network start a frame sized of 6 time slots.

These tasks are performed in the given order. While the second task is ensured by OSTR flooding mechanism; the first task is performed by the so called: Appointment Mechanism.

The OSTR appointment mechanism is evaluated with respect to the following assumptions:  The network remains almost static while running the flooding process.

 If a node is joining the network and meanwhile a flooding process is running, the new node request is treated only when the flooding process ends.  Nodes form a connected graph G (V, E) with V vertices and E edges representing nodes and links in the network, respectively. A connected graph is a graph in which a path always exists between any random pair of vertices.  The diameter D, defined as the longest shortest path in the network, is predefined.

 New arriving nodes join the network one by one such that the network is extended while the diameter remains inferior or equal to D.

According to [START_REF] Pasquale | On the Speed of Information Spreading in Dynamic Networks[END_REF] the flooding time in connected static networks equals the network (or graph) diameter. The appointment time is calculated in terms of number of frames to wait for, before starting the new sized frame.

Let n be a random node from the network initiating the OSTR flooding process, and i its corresponding assigned slot in a frame sized of N time slots. Since slot 0 is reserved for CONTROL sub-frame, i verifies . The OSTR protocol is based on a two-hop interference model; i.e. all nodes in the two-hop neighborhood of node n are concurrent. Therefore, the slot assignment in OSTR is made such that all nodes in the two-hop neighborhood of node n are allocated different slots. Consequently, with the OSTR protocol, a time slot is reused only at a distance of three-hops away from another node detaining the same slot. For instance, only a node that is three-hop away from node n, can be assigned slot i.

In the sequel, we compute an upper bound for the flooding completion time in terms of number of time frames (sized of the current frame size) to wait for, before switching to the new sized frame.

Purpose: How many time frames are needed to complete the flooding within the whole network starting from an arbitrary node n assigned slot i?

Knowing that the OSTR slot distribution in the network verifies the following Rule: Rule 1: Each random slot i in the frame is used mod (3).

  1 1    N i
Therefore, the overall flooding time is reduced to the flooding time necessary to disseminate information from node n to the nodes that are three-hop away from node n. Recall that i verifies , three cases are to be considered:

1. Case 1:

As the first slot is assigned to node n which initiates the flooding process, all node n onehop neighbors are assigned slots which numbers are greater than 1. Suppose node n launches the flooding process during frame j, all its one-hop neighbors will receive the packet and forward it during frame j. Hence, the FC packets reach node n two-hop neighbors in one time frame. In order to reach node n three-hop neighbors, another frame is needed enabling the twohop neighbors to forward the packet by their turn. Therefore, flooding the packet from node n to its three-hop neighbors needs 2 time frames.

Case 2:

In this case, all node n one-hop neighbors cannot forward the packet in frame j. Thus, by the end of frame j, only its one-hop neighbors maintain the forwarded packet. Therefore, the latter proceed to the forwarding process during frame (j+1). Another frame (j+2) is needed to enable packets reach node n three-hop neighbors. Thus, 3 time frames are needed in this case.

Case 3:

In this case, the set of node n one-hop neighbors is divided into two groups: neighbors which slot numbers are superior to i, and neighbors which slot numbers are inferior to i. The former group follows the same reasoning as case 1; while for the latter group the same reasoning as in case 2 is applicable. Therefore, 2 time frames are needed and in other hand the flooding needs 3 time frames. Adopting 2 time frames is problematic because this time period is not sufficient enough to reach all node n three-hop neighbors. Consequently, 3 time frames are needed.

A 3-hop cycle needs then, at most 3 time frames to disseminate information to all nodes in the 3-hop neighborhood. With reference to [START_REF] Pasquale | On the Speed of Information Spreading in Dynamic Networks[END_REF], the overall flooding time in a static network

  1 1    N i 1  i 1   N i ) 1 ( 1    N i
equals the diameter of the network denoted by D. Therefore, it suffices to know how many 3hop cycles D incurs to deduce the time frame number for the overall network flooding. Hence, the flooding completion time denoted by T f verifies (1).

(

It is to mention that a node can acquire the network diameter based on information from the routing layer. For instance, based on table-driven routing protocols, e.g. [START_REF] Perkins | Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers[END_REF], a node maintains a routing table, in which routes to all nodes in the network are continuously updated. Thus, according to the maximum number of hops in its routing table a node can estimate the network diameter.

Performance Evaluation with Comparison to IEEE 802.11 DCF

In the previous Sections, we presented the architecture and detailed the design of the OSTR protocol. Even though OSTR is a TDMA-based MAC protocol, we chose to hold a first evaluation of the OSTR performance in terms of throughput and fairness with comparison to the standard IEEE 802.11 in mode DCF.

Simulation environment and Setup

In order to evaluate the OSTR protocol, we had to implement it in OMNET++ simulator [64]. As we are interested in studying the MAC layer, we chose the mobility framework [65] provided by OMNET++ community to simulate physical and MAC layers. The developed module is an entire MAC layer implementation including all features described in Section 3.2.

To study the performance of OSTR in a multi-hop environment, we faced the issue of choosing an appropriate network topology. Some typical networks are considered in the literature like the grid network supported in [START_REF] Talucci | MACA-BI (MACA By Invitation), A wireless MAC protocol for high speed ad hoc networking[END_REF], or random generated topologies [START_REF] Zhu | A Five-Phase Reservation Protocol (FPRP) for mobile ad hoc networks[END_REF][START_REF] Lin | Asynchronous Multimedia Multihop Wireless Networks[END_REF]. In our work, we consider two different topologies: a very simple multi-hop topology referred as squares topology and used in the literature to evaluate MAC protocols in ad hoc networks, e.g., [START_REF] Garcia-Luna-Aceves | Floor Acquisition Multiple Access (FAMA) in single-channel wireless networks[END_REF]. We also consider a random generated topology.

All the nodes are placed in 1000x1000 meters area, and are assumed to be static. The measurements are performed based on User Datagram Protocol (UDP) traffic. UDP traffic is sent at Constant Bit Rate (CBR). The channel has a physical data rate of 2 Mbps. The squares topology is depicted in Fig. 16, where 8 nodes form a regular topology and 4 flows are running in parallel: A-B-C-D, A-F-C-H, D-G-B-E, andH-G-F-E. While for the random topology, 30 nodes randomly set in the considered area form a multi-hop network including 10 end-to-end connections established between 10 random pairs of nodes. The diameters of the squares and random topologies are 3 hops, and 7 hops, respectively. The evaluation is based on the following metrics:  Aggregate throughput: defined as the average number of bits successfully received by all nodes in the network per second. The Input load is defined as the average number of bits transmitted by source nodes in the network per second.  Fairness index: we use the fairness index defined in [START_REF] Jain | A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems[END_REF]. If all entities get the same amount of resources, then the fairness index is 1 and the system is 100% fair. In our case, we consider that entities are nodes in the network and the metric used to calculate the fairness is their throughput.

3 3         D T f

Simulation Results

In this section, we focus on the intrinsic behavior of the OSTR protocol, i.e., the frame size evolution, and the flooding and appointment mechanisms enabled in OSTR. There is initially one node (node B) assigned slot 1; then the other nodes appear one by one until the eight (resp. thirty) nodes are present in the squares (resp. random) network.

a) Frame size evolution

Since DATA transmission starts at t = 10s (resp. t = 80s) for the squares (resp. random) topology, we are particularly interested in the first 10 seconds (resp. 80 seconds) of the simulation. For the sake of clarity and because node B is the only node that does not have to apply for a slot, the frame size evolution from node B perspective is depicted in Fig. 17 and Fig. 18 for the squares, and random topologies, respectively.

The shape in scale in Fig. 17 reflects the slot by slot frame size increase. In the squares topology, the frame size has changed 5 times starting from 2 time slots till a frame sized of 7 time slots. While for the random topology (Fig. 18), the frame size has increased slot by slot from 2 time slots to 8 time slots. This result is justified by the slot reuse scheme deployed in the OSTR protocol. In fact, to highlight this feature, we plot the slot reuse for an example of a random topology composed of 30 nodes with a network diameter equal to 7 hops. We notice from Fig. 19, that all slots are used which highlights the effectiveness of the slot-by-slot frame size increase to efficiently share the available resources among nodes in the network. Also, we notice that slots 1 and 4 are reused by 12 nodes in the network; while slots 2, 3, and 5 are reused by 15 nodes. Slot 6 is used by 2 nodes; while slot 7 is used by one node. This result points out the effectiveness of the slot assignment algorithm that favors the reuse of the slot three-hops away if possible, leading to a short overall frame size equal to 8 time slots (including slot 0 for CONTROL sub-frame) for a network composed of 30 nodes. A setting delay (SD) metric is introduced to evaluate the correctness of the OSTR flooding and appointment mechanisms. It is the time elapsed between the new node's REQ packet generation and the new node's first DATA packet transmission. Intuitively, the SD is longer when the appointment and flooding mechanisms are performed, i.e., the frame size increases. For instance, nodes D and H have joined the network without inducing a frame size increase with a maximum setting delay of 0,0421523s. This value is smaller than the minimum setting delay value (0,048729s) of the set of nodes that have led to the frame size increase.

With reference to Section 3.2.4.c.iii, the flooding completion time is at most equal to . Moreover, OSTR specifies that the flooding mechanism is initiated in the frame that follows the frame in which the REQ packet was sent. Consequently, the setting delay verifies (2).

(2)

In our case, the network diameter equals 3 hops (resp. 7 hops) for the squares (resp. random) topology. Therefore the theoretic value of the setting delay expressed in terms of number of slots verifies (3), (resp. (4)) for the squares (resp. random) topology:

(3) Where current_frame_size in {2, 3, 4, 5, 6} and slot_duration is a constant.

               3 3 D   duration slot size frame current SD _ _ _ 4    1 3 3                  D SD (4)
Where current_frame_size in {2, 3, 4, 5, 6, 7} and slot_duration is a constant.

The theoretic and the simulated setting delay are depicted in Fig. 20 for both topologies. The setting delay linearly increases with the current frame size. It almost equals the theoretic value for the squares topology, while it remains below the theoretic bound for the random topology. This result goes hand in hand with the analytical result of (3), and (4). 21 shows the aggregate throughput according to input load for the squares and random topologies. We notice that OSTR protocol has higher throughput than 802.11 DCF in saturation cases. 802.11 saturates at a throughput of 500 Kbps and 400 Kbps in the squares and random topologies, respectively; While, OSTR achieves a throughput around 900 Kbps for the squares topology and a throughput of 700 Kbps for the random topology.

The performance of 802.11 DCF is impacted by the exposed terminal problem in case of high input load. Contrarily, the specific reservation scheme implemented in OSTR handles the hidden/exposed terminal problems in one side. In other side, OSTR minimizes collisions thanks to its spatial reuse scheme.

The throughput gain with respect to 802.11 DCF is plotted in Fig. 22 for both topologies. The input load is set to 1500 Kbps. The flows are chosen such that the number of active nodes in the network increases with the number of flows. We intend by active node each node that is involved in a flow and consequently should send and/or receive packets. With few active nodes, we notice a negative gain for the squares topology and a gain of 10% for the random topology. When 100% of nodes are active, the gain increases and achieves 66% (resp. 80%) for the squares topology (resp. random topology). This result is expected as for a small number of active nodes 802.11 DCF experiences less collisions and small backoff windows. Meanwhile, OSTR cannot fully take advantage from its slot re-utilization scheme. However,

  duration slot size frame current SD _ _ _ 10   
when the number of active nodes increases, the gain significantly increases and reaches 80%. Indeed, the increase of active nodes leads to more contention. Thus, 802.11 throughput decreases. At this level, OSTR takes advantage from the spatial reuse to schedule the channel access among the contending nodes.

d) Fairness

The fairness index of OSTR and 802.11 DCF in function of the input load is depicted in Fig. 23. With a lower network density (8 nodes in the squares topology) OSTR and 802.11 DCF show comparable fairness index values (0.92 for OSTR and 0.94 for 802.11). However, with a higher network density (30 in the random topology) OSTR succeeds to provide a higher fairness (0.94) than 802.11 DCF (0.87). This is mainly due to the OSTR scheduling scheme that ensures the channel access for all nodes in each frame cycle. Contrarily to OSTR, with a high density and a high input load, some 802.11 nodes suffer from starvation due to exposed terminal problem leading to short term unfairness. Another dynamic frame size increase technique is introduced in the literature [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF]. It consists in setting the frame size as a power of two. This technique is deployed in the E-ASAP protocol. In [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF], it is shown that the E-ASAP protocol succeeds to achieve higher channel utilization in comparison with USAP and USAP-MA. However, we argue that setting the frame size as a power of two yields to an unfairness problem.

To highlight the effectiveness of our protocol, we propose a comparative study between the two dynamic techniques for the frame size increase, i.e. increasing the frame size slot-by-slot introduced by the OSTR protocol, and setting the frame size as a power of two deployed in the E-ASAP protocol. For this end, a brief description of the E-ASAP protocol is first presented.

E-ASAP Protocol

To our knowledge, few are the research works that have investigated the potentials of a dynamic TDMA frame size in the context of wireless multi-hop networks. E-ASAP [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF], has introduced the dynamic TDMA frame size increase that consists in setting the frame size as a power of two. This frame size increase technique has been applied to wireless vehicular networks in [START_REF] Miao | A-ADHOC: an Adaptive Real-time Distributed MAC Protocol for Vehicular Ad Hoc Networks[END_REF]. In this Section we propose to deeply analyze the E-ASAP protocol.

a) E-ASAP: Protocol Description

E-ASAP is a dynamic and distributed MAC protocol for wireless ad hoc networks. It is based on a TDMA scheduling technique to reduce packet collisions and minimize interference effects. Time slots are then assigned such that nodes in the same contention area are allocated different slots. A contention area is defined for each node as the set of nodes that can cause collisions. It is assumed that the contention area is the set of nodes within the two-hop neighborhood.

The particularity of the E-ASAP protocol consists in setting the frame length as a power of two with a minimum frame size of 4 time slots. The first slot of each frame is reserved for new node requests, i.e. no DATA packet transmission is ensured during that slot. In E-ASAP, nodes switch between two different modes: a TRANSFER mode and a CONTROL mode. A node in a TRANSFER mode only sends DATA packets, while in the CONTROL mode the DATA packet transmission is interrupted to enable control packet sending, instead. When a node joins the network, it first senses the channel to determine the beginning of the frame size, i.e. the 1 st slot position. A 3-way handshake is then performed to assign a slot to the new arriving node. It is ensured via the exchange of request (REQ), information (INF) and suggestion (SUG) packets between the new node and its one-hop neighbors. Once the time slot is selected, new node neighbors send an update (UPD) packet.

b) E-ASAP: Slot Assignment

The E-ASAP protocol is a topology-based MAC protocol since it assigns slots based on the two-hop neighborhood information. Also, E-ASAP is designed to work in a distributed manner. It enables then a three-way handshake for slot assignment. A new incoming node first senses the channel to collect DATA packets. Since E-ASAP data packet header includes the frame size and the current data slot number, the new node is able to be synchronized with other nodes in the network, i.e. the new node determines the time period for the first time slot of the frame. Once the node is synchronized with other nodes in the network, it triggers a 3-way handshake mechanism in order to select an appropriate time slot. The 3-way handshake mechanism is ensured via the exchange of REQ, INF and SUG packets.

Three-way handshake: For time slot selection, the slot assignment information in the twohop neighborhood is required. Hence, the new node transmits a REQ packet to its one-hop neighbors during the first slot of the frame. Nodes that have received the REQ packet switch to the CONTROL mode and send an INF packet during their own assigned slots. An INF packet contains the frame size and the slot assignment of both the sender and the sender neighbors. Based on the INF packets, the new node first sets its frame size to 4 time slots, the minimum frame size in the E-ASAP protocol, and passes through three different procedures to select a time slot: Getting an Unassigned slot (GU), Releasing Multiple Assigned slots (RMU), and Doubling the Frame size (DF). These procedures are detailed later on. Once the new node selects an appropriate slot, it sends a SUG packet to its neighbors. Upon the receipt of the SUG packet, the latter update their slot assignment information and generate a UPD packet so that the updated information spread to the two-hop neighborhood. Afterwards, new node neighbors switch back to the TRANSFER mode and resume their DATA packet transmission.

Slot assignment procedures in E-ASAP: E-ASAP defines three procedures for slot assignment: Getting an Unsigned slot (GU), Releasing Multiple Assigned slots (RMA), and Doubling the Frame size (DF). a) Getting an Unsigned slot: The new node first sets its frame size to the minimum frame size in E-ASAP, i.e. 4 time slots. Then, it searches for at least one free slot with the current frame size. If free slots are found, the new node assigns to itself one of them except the first slot which is reserved for new incoming node. b) RMA: In case the new node does not find at least one free slot with the current frame size, it checks whether one of its neighbors is assigned multiple slots with the current frame. In case such node is found, the new node releases one assigned slot to that neighbor and assigns it to itself. c) DF: In case no free slots are available and no neighbor is assigned multiple slots, the node doubles the frame size. Doubling the frame size modifies the neighborhood slot assignment scheme. Indeed, DF process consists of three main steps: 1) doubling the frame size. 2) Copying the nodes that are assigned slots with the current frame size, to the later part of the new sized frame. 3) Applying the GU and the RMA to select a free slot. This process is repeated until a free slot is allocated to the new node.

For the sake of clarity, an example is depicted in Fig. 24 to illustrate the E-ASAP slot assignment procedures. Fig. 24.a shows a network composed of three nodes: A, B, and C assigned slots 1, 2, and 3, respectively. First, node D joins the network as it is depicted in Fig. 24.b. As no free slots are available with the current frame size (4 time slots), node D deploys the RMA procedure. This procedure fails since no neighbor is assigned multiple slots. DF is then executed. While doubling the frame, nodes A, B and C are assigned additional slots with respect to [START_REF] Goldsmith | Design Challenges for Energy-Constrained Ad Hoc Wireless Networks[END_REF]. In ( 5), New_slot_Nb, slot_Nb, and Fr_Size denote the additional slot number, the number of the slot already assigned to the node, and the current frame size of the node; i.e. before doubling the frame size. Therefore, nodes A, B, and C are assigned the pairs of slots {1, 5}, {2, 6}, and {3, 7}, respectively. Since slot 0 is reserved for new node requests, a free slot appears in the frame sized of 8 time slots. Hence, following the GU procedure, node D is assigned the slot number 4. In Fig. 24.c another node E joins the network. As GU procedure fails, node E applies the RMA procedure. Within its neighborhood, three nodes maintain multiple slots. Node E then, releases one slot (e.g. slot 5) from node A and assigns it to itself.

New_slot_Nb = slot_Nb + Fr_Size

(5)

Analytical Analysis between OSTR and E-ASAP

In order to compare the performance of the OSTR and the E-ASAP protocols, we first analyze the frame size evolution in function of the number of competing nodes, from which we deduce the channel utilization and fairness expressions. These analytical results are then enforced by a set of simulations performed in two different scenarios: (i) a fully connected network, and (ii) a multi-hop network.

a) Frame Size Evolution

In our study, the following assumptions are considered:

 Nodes form a fully connected network,  The CONTROL sub-frame for both protocols consists of the first slot of the frame,

 Slots are of equal sizes

Let N be the number of nodes in a fully connected network. As the frame size in the OSTR protocol is increased slot by slot such that nodes in the same neighborhood are assigned different slots, the total number of slots needed is N. Therefore, the frame size of the OSTR protocol is (N+1) as we consider an additional slot for the CONTROL sub-frame.

In E-ASAP, the frame size is set as a power of 2. According to the slot assignment procedures defined in E-ASAP, a node is always assigned at most 2 time slots. Accordingly, the frame size of E-ASAP is given by ( 6).

b) Channel Utilization

We define the channel utilization as the ratio of the number of assigned slots to the frame size in the overall network. The channel utilization for OSTR is given by ( 7), while that of E-ASAP is given by ( 8). First, the channel utilization for both OSTR and E-ASAP protocols increases when the number of nodes in the network increases. This feature is explained by the TDMA-based channel access scheme deployed in both protocols. Indeed, unlike contention-based MAC protocols, TDMA channel access technique avoids collisions and ensures a guaranteed access for each node. The time division multiple accesses are combined with a reservation procedure in both OSTR and E-ASAP so that all nodes in the network are assigned at least one time slot. This way, the node number increase induces a higher number of assigned slots leading to higher channel utilization.

Second, the channel utilization curve of OSTR presents a continuous behavior while that of E-ASAP shows break points. This is closely related to the frame size increase for both OSTR and E-ASAP. We have plotted the frame size (in terms of number of slots) evolution for both protocols in Fig. 26. Since the OSTR protocol assigns slots one by one, the frame size linearly increases. While for the E-ASAP protocol, the frame size increase is performed only when the GU and the RMA procedures fail. These cases correspond to a number of nodes that is set as a power of 2. Apart from the break points, the E-ASAP frame size remains unchanged which justifies the overall shape in scale of the E-ASAP frame size evolution.

Third, the E-ASAP channel utilization is periodic and is slightly better than the OSTR channel utilization. The E-ASAP protocol design specifies that a node is assigned two time slots each time the frame size is doubled, while OSTR only assigns one time slot to every node in the network. This leads to an increase of the channel utilization for the E-ASAP protocol when the frame size is doubled, since all nodes apart from the newly arriving node will be assigned two time slots. Afterwards, the RMA procedure is applied to assign a slot to the new arriving node while the frame size remains unchanged. This maintains the same channel utilization as long as there is nodes allocated multiple slots. Meanwhile, the OSTR channel utilization slowly increases according to the slot-by-slot frame size increase. The two protocols show the same performance in terms of channel utilization when all nodes with E-ASAP are assigned only one time slot, the same as in the OSTR protocol. With reference to ( 7) and ( 8), OSTR and E-ASAP protocols achieve the same channel utilization when the number of nodes is equal to where x is a nonzero integer.

These results are enforced by a set of simulations performed with OMNET++. We have considered a fully connected network with a number of nodes rising from 5 to 50 nodes. In Fig. 27, the global aggregate throughput defined as the average number of successfully received bits per second, is plotted. The E-ASAP protocol achieves higher throughput than OSTR and performs similarly to the OSTR protocol when the nodes number is 30 (1850 Kbps). This goes hand in hand with the theoretical results explained above.

  We have analyzed the frame size evolution of the OSTR and E-ASAP protocols and shown how it affects the channel utilization ratio of both protocols. We argue that the DF procedure deployed in the E-ASAP protocol is a two-edge sword. In fact, it allows achieving higher channel utilization with comparison to the OSTR protocol, since it assigns additional slots to the nodes when the frame size is increased (i.e. doubled). However, it yields to severe unfairness problem, since some nodes may have only one time slot while others are assigned two time slots. To deeply analyze the fairness issue, we have plotted the fairness index according to the number of competing nodes for both OSTR and E-ASAP protocols in Fig. 28. Recall that we have considered the same fairness index definition previously presented in Section 3.3.1.

1 2  x             1 log 1 log
In Fig. 28, the two fairness index curves join when the number of nodes is equal to where x is a nonzero integer. For this number of nodes, both OSTR and E-ASAP protocols assign only one time slot for all nodes in the network, and hence they both ensure per-node fairness (fairness index =1). Even though E-ASAP is fair for specific node numbers, the fairness index oscillates between the maximum value of 1 and a minimum value. This oscillation is due to the variation of the number of slots assigned to the nodes. In fact, the network join decision in E-ASAP is performed by the new arriving nodes; i.e. the number of assigned slots depends on the new arriving node decision. For the sake of clarity, let consider a simple example of a node n assigned the slot number 1 in a frame sized of 4 time slots (including slot 0 for CONTROL sub-frame). Suppose that a new node joins the network and doubles the frame size. Node n is now assigned 2 time slots (slot 1 and slot 5). As long as new arriving nodes join the network, node n will be dislocated one time slot. When the frame size is doubled, it is assigned two time slots once again. This process is periodically repeated leading to an oscillation of the fairness index. For the purpose of performance comparison between the E-ASAP and the OSTR protocols, we have also considered the two multi-hop scenarios described in Section 3.3.1. We consider a saturation case, and set the user data rate at the MAC layer equal to 1500 Kbps. In these set of simulations, we consider different user data flows established between random pairs of nodes in both topologies. The number of flows varies from 2 to 4 for the squares topology, and from 2 to 10 for the random topology. Each simulation result is the average of 10 simulation runs, each with different set of end-to-end flows. The evaluation is based on the network throughput metric. We recall that the network throughput is defined as the total delivered data per second; i.e. the total successfully received bits by the flow destinations per second.

 

b) Simulations results

Fig. 29. depicts the network throughput according to varying number of flows in the squares topology for the OSTR and the E-ASAP protocols. With a small number of flows (2 flows) the OSTR protocol slightly outperforms the E-ASAP protocol. When the number of flows increases and is set to 3, the network throughput achieved by the OSTR protocol significantly increases and largely outperforms that of the E-ASAP protocol. The network throughput reached by OSTR is almost 300 Kbps higher than that of E-ASAP. Even if the network throughput decreases when 4 flows are running in parallel, OSTR still outperforms the E-ASAP protocol. The slot distribution for both protocols is analyzed to justify this result. For the sake of clarity, we consider one typical scenario for each number of flows. These scenarios are depicted in Fig. 30. The slot distribution achieved by the OSTR and the E-ASAP protocols is also presented in Fig. 30, where each pair (letter/number) denotes the node identifier and its corresponding assigned slot. We notice that OSTR reaches a frame sized of 7 time slots (including the slot 0 for CONTROL sub-frame), while E-ASAP achieves a frame sized of 8 time slots.

flows:

In this case, only three nodes are active: the source nodes (nodes D and H) and the common intermediate node (node G). Hence, for OSTR (resp. E-ASAP) slots 2, 4, and 6 (resp. slots 3, 5, and 7) are used, while the other slots in the frame remain empty. The network bandwidth is not fully utilized due to free slot appearance. Nevertheless, the OSTR takes advantage of its shorter frame size (7 for OSTR comparing to 8 for E-ASAP) and then nodes send data packets more frequently than with the E-ASAP protocol; yielding to a higher network throughput comparing to the E-ASAP protocol.

3 flows: Three flows are now considered. In this case, 5 slots (slots 1, 2, 3, 4, and 6) are fully used in OSTR. Thus, OSTR looses only one time slot (slot 5). Similar to OSTR, E-ASAP also fully uses 5 slots (slots 1, 2, 3, 5, and 7), but it looses an additional slot comparing to OSTR (slots 4 and 6). The bandwidth wastage with E-ASAP is more important than that of OSTR (1/4 for E-ASAP compared to 1/7 for OSTR) leading to a lower overall network throughput.

flows:

In the last scenario, the flows are set such that all nodes in the network are involved. Thanks to its spatial reuse scheme, the OSTR achieves higher network throughput than E-ASAP. In fact, as node E is neither a source node nor an intermediate node it does not use its assigned slot (slot 4 for both OSTR and E-ASAP). A free slot then is likely to appear in the frame, unless slot 4 is used by another node in the network. Thanks to the OSTR spatial reuse scheme that favors slot reutilization, node H is assigned slot 4 yielding to a fully resource exploitation. Contrarily, the E-ASAP performs another technique that consists on releasing multiple assigned slots. Hence, slot 4 is only assigned to node E and E-ASAP suffers from bandwidth wastage due to free slot appearance.

In this simple case of study, we highlight two important features of the OSTR protocol: (1) in light traffic case, the OSTR protocol takes advantage from its shorter frame size to achieve higher network throughput. [START_REF] Anastasi | Energy conservation in wireless sensor networks: A survey[END_REF] In heavy traffic case, the slot reutilization scheme deployed in OSTR prevents free slot appearance and ensures a fully resource utilization.

The simulation results for the 30 node random topology are depicted in Fig. 31. For the random topology, both protocols achieve a frame sized of 8 time slots. With little number of flows, the OSTR protocol achieves slightly higher network throughput than E-ASAP. Otherwise, the performance of both protocols is similar. In fact, apart from one single node that is assigned 2 time slots with E-ASAP, all nodes are assigned one time slot, the same as with the OSTR protocol. Reaching the same frame size, and assigning almost one time slot for each node, results to the same performance for both protocols. This result comes hand in hand with the theoretical analysis presented above. In fact, with a network density equal to 30 nodes, the OSTR protocol frame size reaches that of the E-ASAP protocol (8 time slots). Meanwhile, E-ASAP releases multiple assigned slots while maintaining the frame size unchanged. To sum up, we have performed a comparison study between the OSTR protocol and the E-ASAP protocol based on an analytical study enforced by a set of simulations performed in a fully connected network. Following this comparative analysis, we argue that the E-ASAP behavior depends on the number of competing nodes in the network.

1 If the number of nodes in the network is different from where x is a nonzero integer, the E-ASAP protocol shows better channel utilization than the OSTR protocol, since the number of assigned slots is increased while the frame size remains unchanged. However, the high channel utilization achieved comes at the expense of an unfair channel access between nodes. Indeed, the number of assigned slots in the E-ASAP protocol depends on the new node decision; thus, the number of assigned slots for a single node continuously oscillates between 1 time slot and 2 time slots regarding the new node arrivals. This feature has two major consequences: (1) an unfair share of bandwidth between nodes, and (2) a channel utilization fluctuation depending on the new node decision, which might affect the performance of higher layers.

2 If the number of nodes in the network is equal to where x is a nonzero integer, the E-ASAP protocol shows similar performance as the OSTR protocol. Both protocols have the same frame size while assigning only one time slot for each single node in the network. This ensures per-node fairness in one hand and similar channel utilization in other hand.

Discussion: OSTR Vs. E-ASAP

In this section, we point out the similarities and the differences between the E-ASAP and the OSTR protocols. Table 3-2 summarizes the main differences between the OSTR and the E-ASAP protocol characteristics.

 

1 2  x   1 2  x a) Similarities
E-ASAP and OSTR assume the node clocks are perfectly synchronized. An external synchronization mechanism (e.g. [START_REF] Maroti | The Flooding Time Synchronization Protocol[END_REF]) is supposed to be used to ensure clock drifts synchronization.

E-ASAP as well as OSTR uses TDMA access technique to schedule the channel access between contending nodes. Although [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF] does not specify how a new node accesses the first time slot of a frame, E-ASAP and OSTR both entail a contention-based and a contention-free scheme. In contention-based, new nodes perform a random access to the channel; while in contention-free period the resource access is scheduled.

Both E-ASAP and OSTR are topology-based MAC protocols. Two-hop neighborhood information is required to ensure slot assignment.

Both protocols tackle the fixed frame size inflexibility. They are based on a dynamic frame size to handle topology variations and node movement.

b) Differences

 Frame evolution: Although they make use of a dynamic frame size, the E-ASAP and the OSTR protocols present a different frame evolution. The frame length in E-ASAP is set as a power of 2 with a minimum frame size of 4 time slots; whereas OSTR builds the frame slot by slot, and hence the overall frame length in the network is increased one by one.  Frame synchronization resolution: Two different approaches are defined in the E-ASAP and the OSTR protocols to deal with the frame synchronization problem. Unlike E-ASAP, the OSTR protocol separates the frame size evolution from the frame synchronization problem. Thereby, the frame size is increased only with respect to the network topology variation, while new mechanisms are defined to cope with frame synchronization problem. Contrarily, in E-ASAP the frame size evolution is topologyindependent, and restricts the frame size to a power of two. Despite its robustness to minimize collisions due to frame synchronization issue, this solution comes to the detriment of node requirements and upper layer specifications in terms of QoS considerations.  Traffic overhead: The periodic HELLO exchange and the FC packet broadcast add additional traffic overhead to OSTR comparing to E-ASAP, which may contribute to bandwidth wastage. However, HELLO packet exchange allows better track to topology variations. In another hand, the OSTR protocol deploys HELLO packet such that established communications are not interrupted each time a new node joins the network. Unlike OSTR, E-ASAP protocol performs the slot assignment on the expense of the running communications. Indeed, upon the reception of a REQ a node switch to the CONTROL mode, where no DATA packet should be sent. Besides, in E-ASAP a new node needs to listen to exchanged DATA packets to be synchronized to the network, while for the OSTR protocol the new node needs to listen to HELLO packets only. This feature is useful since it avoids network blocking situation. In case no DATA traffic is transmitted, E-ASAP does offer no other means to let the new node join the network resulting in a network blocking situation.  Admission decision: Another major difference between the OSTR and the E-ASAP protocols is the new node admission to the network. Both protocols entail the use of a handshake between the new node and its neighbors for neighborhood discovery and time slot selection. The handshake mechanism yields to the selection of an appropriate time slot for the new arriving node. This achievement is slightly different from the E-ASAP and the OSTR protocols. In effect, while the E-ASAP protocol gives right to the new node to modify the slot assignment of its neighbors, if necessary (in case RMA and/or DF procedures are used); the slot allocation decision is network-based in OSTR. Indeed, with OSTR a new node has to wait for a REPLY packet from the REQ destination node before joining the network. Also, the OSTR slot selection algorithm does not affect the network slots assignment. Contrarily, the E-ASAP slot assignment scheme infers additional slots allocation and already assigned slots release in case the DF and RMA procedures are used, respectively. Hence, the amount of allocated resources varies regarding the willingness of new arriving nodes. This feature reflects the E-ASAP protocol vulnerability towards providing guaranteed QoS.  Throughput and Fairness: Based on analytical and experimental studies, we pointed out that E-ASAP behaves differently according to the number of competing nodes in the network. Accordingly, the throughput achieved by E-ASAP outperforms that of OSTR in a fully connected network, where the number of nodes is not a power of two. However, with respect to this network conditions, the E-ASAP protocol is unable to ensure per-node fairness. The OSTR and the E-ASAP protocols present similar performance in terms of network throughput and fairness when the number of nodes is a power of two in a fully connected scenario. Hence, reaching a shorter frame size is consequent less in such scenario. However, the shorter frame size has a significant effect on the network throughput in a multi-hop scenario with light traffic. We highlighted the effectiveness of the slot reuse scheme and the slot-by-slot technique deployed in the OSTR protocol to increase the resource exploitation.

Table 2: Comparison between OSTR and E-ASAP main characteristics

OSTR E-ASAP

Clock synchronization

Not supported

Not supported

Frame

Dynamic Dynamic

Frame evolution

Slot-by-slot Set as a power of 2

Frame synchronization resolution

Appointment mechanism

+ Flooding mechanism

Setting the frame as a power of 2

Admission decision

Networkbased

According to new node willingness

Channel utilization

Independent from the network density

Depends on the network density

Fairness

Fair Fair only when the network density is equal to , where x is a nonzero integer.

 

1 2  x 3.

Conclusion

In this chapter, a new MAC protocol, called OSTR has been proposed for wireless ad hoc networks. OSTR is a topology-based protocol operating in a slotted environment. It combines a random channel access for control packet transmission with a scheduled channel access for DATA packet exchange. The significance of OSTR is threefold. First, OSTR ensures an efficient spatial reuse of resources, since it favors slot re-utilization in order to keep the frame size as low as possible. Second, OSTR works in a completely distributed manner and adapts to topology changes. Third, OSTR introduces the slot-by-slot dynamic frame size increase inferring a shorter achieved frame size.

The comparative study between OSTR and IEEE 802.11 DCF shows that OSTR handles saturation cases. It outperforms 802.11 DCF at high input loads thanks to its scheduling scheme.

In order to point out the effectiveness of the new slot-by-slot frame size increase, a second comparative study with the frame size increase technique deployed in E-ASAP was handled. For this end, we have given a detailed analysis of the E-ASAP protocol. The E-ASAP description lacks of insights in how the slots are assigned when the frame size is doubled [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF]. In this chapter, we have therefore proposed a formulization of the E-ASAP slot assignment in case the frame size is doubled.

Through analytical analysis combined with simulation results, we pointed out the main benefits brought by the OSTR protocol features. First, it is shown that OSTR can reach high network throughput in a multi-hop environment under different traffic loads. Under light traffic, the OSTR takes advantage of its shorter frame size to achieve higher network throughput. While under heavy traffic, the OSTR spatial reuse scheme ensures fully resource utilization. Also, OSTR ensures per-node fairness regardless the number of competing nodes in the network.

Second, the flooding and appointment mechanisms deployed in OSTR have the advantage to separate the frame size evolution from the frame synchronization problem. The frame size increase depends only on network topology and node requirements.

Finally, thanks to its slot reservation mechanism, the new node admission decision is network-based in OSTR. This feature is of high interest to provide guaranteed QoS and security considerations.

In the two previous chapters, the focus was on the MAC protocol design for multi-hop ad hoc environment. Two fold objectives of a MAC protocol in this context consist in optimizing the shared available resources utilization, and improving the per-node fairness. It is shown that OSTR accomplishes these two main objectives thanks to the slower frame size increase leading to a shorter achieved frame size and to the TDMA scheduling policy favoring the spatial reuse.

These two features are particularly attractive since they contribute to significant energy savings. Shorter the frame size achieved in a slotted environment is, shorter is the active period during which nodes are communicating and hence higher is the energy spared. Beyond this observation, we point out the potential of OSTR to tackle the energy efficiency. The OSTR protocol appears then as a promising solution to reduce energy consumption.

In the next chapter, the focus is on the energy efficient characteristic of the OSTR protocol. We will show the OSTR ability to adapt to a slightly different wireless multi-hop environment, where the energy consumption is of primary concern. The OSTR features are therefore adapted to the sensor network environment to give rise to a new MAC protocol for wireless multi-hop sensor network, called Sensor OSTR (S-OSTR).

Introduction

The Medium Access Control (MAC) protocol plays a significant role to enhance overall wireless network performance. It organizes the channel access among nodes in the network and schedules the resources share between them. As stated in the previous chapters, four objectives of MAC layer are: consider the broadcast nature of the wireless medium, minimize the interference effect, reduce collisions, and provide energy efficient mechanisms.

Ideally, a good MAC protocol design needs to fulfill a maximum number of these objectives. In practice, industrials and consumers favor one feature over another according to the application needs and the network utilization. Indeed, while efficient channel utilization and fair channel access are of a primary concern in wireless ad hoc networks, an energyefficient MAC protocol is instead required for wireless sensor networks.

A wireless sensor network consists of sensor nodes spread over a specific area to monitor real world phenomena such as temperature, humidity, light, sound and so on; or to collect body measurements (e.g. pulse) as for health care applications. Wireless sensor networks mainly differ from wireless ad hoc networks by their low power capacities, and limited coverage and communication range. They are, indeed, composed of battery-powered tiny devices. Wireless sensor networks are energy-constrained, since they need to fulfill a long lifetime rising from several days to several months depending on the application; while sensor batteries are power-limited. Also, sensor nodes are deployed such that a node can hardly be changed when it is disposed, and in general they cannot be replaced or recharged when they dispose.

In [START_REF] Anastasi | Energy conservation in wireless sensor networks: A survey[END_REF], a comparison between the cost of data transmission, data sensing and data processing in terms of energy consumption has been held. It is shown, that data transmission is more expensive in terms of consumed energy; while data processing, in contrary, requires insignificant energy with respect to that consumed for data transmission. Depending on the sensor types [START_REF] Anastasi | Energy conservation in wireless sensor networks: A survey[END_REF], data sensing may consume an amount of energy comparable or greater than data transmission. In other cases, the energy consumption by data sensing is negligible with respect to data processing. Beyond this observation, MAC protocol should have desirable features in the context of wireless sensor networks. It should implement an appropriate mechanism to minimize retransmissions due to interference and collisions. A node activity scheduling is also interesting in order to coordinate the sleeping, sensing and transmitting activities such that the data transmission and sensing are performed only if needed.

Through its deployed features, the OSTR MAC protocol [64] detailed in the previous chapter is capable of supporting the sensor network requirements in terms of energy efficiency. The major motivation behind, is to take advantage of the shorter frame size achieved by OSTR to reduce the active period. Moreover, thanks to its TDMA-based channel access scheme the OSTR is able to reduce the energy consumption to the required energy for transmitting and/or receiving. Finally, OSTR tackles interference effect and collisions thanks to the TDMA conflict-free channel access inferring a significant spare of energy.

In this chapter, a new amendment of the OSTR protocol, called Sensor OSTR (S-OSTR) to appeal wireless sensor network is presented. We first, survey the most common works related to the design of energy-efficient MAC protocol for wireless sensor networks in Section 4.2. Our motivations to accommodate the OSTR protocol to sensor networks are explained in Section 4.3. We give, in Section 4.4, a detailed description of the amendment S-OSTR; while we highlight, if necessary, the main differences with respect to OSTR and the modifications brought by S-OSTR. Several simulations have been carried out in order to validate the effectiveness of S-OSTR in terms of energy efficiency and bandwidth exploitation. Performance evaluations of S-OSTR are held in Section 4.5; while a comparative study between S-OSTR and a two-hop coloring algorithm deployed in SERENA [START_REF] Minet | SERENA: SchEduling RoutEr Nodes Activity in wireless ad hoc and sensor networks[END_REF] is presented in Section 4.6. Section 4.7 concludes this chapter.

Most of the results of this chapter have been presented by the author in [START_REF] Sayadi | Sensor-OSTR: Novel energy-efficient dynamic TDMA frame size-based MAC Protocol for Wireless Multi-hop Sensor Networks[END_REF].

MAC Protocol Design for Wireless Sensor Networks

An energy-efficient MAC protocol is of primary concern in wireless sensor networks. Such networks, indeed, are energy-constrained, since they need to fulfill a long lifetime; while sensor batteries are power-limited. How to reduce the energy consumption is, then, a critical issue to face in wireless sensor networks. In such networks, the energy is consumed depending on the sensor radio state. The energy is also consumed in processing, transmitting and receiving data. However, extra energies are wasted, since they are required for the only purpose of ensuring the correctness of the MAC protocol, while they are useless from the application point of view.

In this Section, we first investigate the major causes of energy waste. Secondly, we survey the major research works most related to the design of an energy-efficient MAC protocol for wireless sensor networks.

Energy Consumption

A sensor node can be in one of the following four states:  Transmit: the sensor is transmitting a packet with a transmission power P transmit .  Receive: the sensor is receiving a packet with P receive .  Idle: the sensor radio is turned on, while packets are neither transmitted nor received.

The sensor stays idle and monitors the medium with a power P idle .  Sleep: the sensor radio is turned off, thus no communication is possible. The power used is P sleep .

The power consumption values depend on the underlying hardware technology deployed in the sensor. Table 3 depicts the reference values of power consumption for the IEEE 802.15.4. It is to mention, that the sleep state, is the state where the less energy at all is consumed.

Causes of energy waste

In wireless sensor networks, the energy consumed while processing, transmitting and receiving data is mandatory to serve the application requirements. Nevertheless, additional energies are consumed for the only purpose to ensure the correctness of the MAC protocol, while they are useless from the application point of view. These additional causes of energy consumption are classified in [START_REF] Mahfoudh | Energy effciency in wireless ad hoc and sensor networks: routing, node activity scheduling and cross-layering[END_REF] in five major types:

1. Collision: A Collision occurs when two packets arrive to a receiver at the same time. All collided packets are discarded and are then retransmitted which increases the energy consumption.

2. Overhearing: overhearing describes the situation where a node is listening to packets that are not destined to it, and hence are useless for it.

3. Control packet overhead: each single packet transmission requires energy. Hence, the more the control packets are, the higher the energy consumption is. An appropriate MAC protocol should then minimize the usage of control packets.

4. Idle listening: consists in monitoring the channel in order to detect possible traffic transmission.

5.

Over emitting: over emitting occurs when a node transmits a packet while the destination node is not ready, leading to the waste of the packet.

A good strategy to save more energy in wireless sensor networks should, therefore:

1. Minimize the waste of energy due to the causes described above, 2. And, prolong the periods during which nodes are in the sleep state, since it is the less energy consumed state.

Node activity scheduling is an energy efficient strategy that combines these two attributes. It consists of an alternate between sleep and active states while ensuring network and application functionalities [START_REF] Mahfoudh | Energy effciency in wireless ad hoc and sensor networks: routing, node activity scheduling and cross-layering[END_REF]. In the sequel, we propose a brief description of some MAC protocols based on the node activity scheduling strategy, while highlighting the pros and cons of each of them. The main idea behind the node activity scheduling is to take advantage from the less energy consumption when the node is in the sleep state. Accordingly, an alternate between an active period and a sleep period is adopted. However, no communication is possible when the sensor nodes are in sleep state. An accurate activity schedule is therefore compulsory to ensure consistent communication while alternating the active and inactive (sleep) periods. Fig. 32 presents a classification of the node activity scheduling strategies. We distinguish two main groups: (1) medium access-independent solutions, and (2) medium access-dependant solutions. The latter can be divided into three major families: (1) contention-based MAC protocols, (2) TDMA-based MAC protocols, and (3) hybrid MAC protocols.

Node activity scheduling

a) Solutions independent from the medium access

The idea behind solutions independent from the medium access is to cover the network by a number of nodes higher than the optimal needed number. These nodes are then grouped in a number of sets such that each set can ensure all network functionalities. To spare energy, the sets are activated one by one; i.e. when nodes belonging to a set are active all other nodes are in sleep state in order to save their energy.

Node Activity Scheduling

Medium access independent solutions

Medium access dependent solutions

CSMA-based MAC protocols (S-MAC, T-MAC)

TDMA-based MAC protocols (TRAMA, FLAMA)

Hybrid MAC protocols (Z-MAC, SERENA)

Node Activity Scheduling

Medium access independent solutions

Medium access dependent solutions

CSMA-based MAC protocols (S-MAC, T-MAC)

TDMA-based MAC protocols (TRAMA, FLAMA)

Hybrid

MAC protocols (Z-MAC, SERENA)

In the literature, medium access independent proposals mainly focus on how to divide the networks into optimal sets of nodes. In [START_REF] Cardei | Energy-efficient target coverage in wireless sensor networks[END_REF], for instance, the nodes are grouped into disjoint sets that are activated separately. Higher the number of sets is, higher is the spared energy. Thus, the major objective of this proposal consists of the maximization of the number of disjoint sets which is shown to be NP-hard. Moreover, the solution does not consider the real energy consumption of nodes; they consider a uniform energy consumption model for all nodes belonging to the same set.

Unlike [START_REF] Cardei | Energy-efficient target coverage in wireless sensor networks[END_REF], the network is divided into non disjoint sets in [START_REF] Cardei | Improving wireless sensor network lifetime through power aware organization[END_REF]. It is shown that network lifetime is enhanced when some nodes are involved in different sets.

[72] presents a distributed solution that selects a connected dominating set of nodes; i.e. each node either belongs to this subset or is one neighbor of a node in this subset. Each node is assigned a priority based on its residual energy. A node activity scheduling policy is proposed based on the attributed priority. The policy specifies that a node can turn to sleep state if and only if:

 The dominating set that it belongs to is connected,  All its neighbors have at least one neighbor in the dominating set,  All nodes belonging to the dominating set have higher priority.

b) Solutions dependant on the medium access

The idea behind the solutions dependant on the medium access is to implement a low duty cycle for power management; i.e. a node is allowed to enter the SLEEP state whenever it is neither on the transmit state nor on the receive state. These solutions are, in general, classified into three classes: contention-based, TDMA-based, and hybrid protocols. In the following, we will survey the most common protocols from each class.

i. Contention-based MAC protocols for wireless sensor networks

Based on a carrier sensing mechanism combined with RTS/CTS exchange before the transmission of each unicast packet, Ye et al [START_REF] Ye | Medium access control with coordinated adaptive sleeping for wireless sensor networks[END_REF] introduce Sensor MAC, an energy efficient MAC protocol designed for wireless sensor networks. S-MAC splits the channel access in two parts: (1) a listen period, where nodes exchange sync packets and specific control packets used for collision avoidance the same way the RTS/CTS handshake is used in IEEE 802.11.

(2) The remaining period, is reserved for actual DATA transmission. With S-MAC, each node runs a random distributed algorithm to establish its sleep/active schedule. This schedule is, then, spread in the neighborhood via sync packets. This way, nodes coordinate their schedules. Nodes detaining the same schedule form a virtual cluster. In case a node is involved in two non-overlapping schedules, it follows both of them. S-MAC introduces three main components to decrease the waste of energy: (1) periodic listen and sleep, (2) collision and overhearing avoidance, and (3) message passing. The former allows nodes to periodically switch from a sleep period to an active period. When a communication is initiated between node peer, all nodes in the immediate neighborhood go to sleep, reducing then the energy consumption due to idle listening. Like IEEE 802.11, RTS/CTS as well as virtual and physical carrier sensing are used to avoid collisions. The last component of S-MAC is the message passing. It consists on dividing long messages into small ones that will be sent in a burst. RTS/CTS are performed before the transmission of each burst, while an ACK from the receiver is acquired for each message fragment. This technique achieves energy savings by reducing the control overhead.

The S-MAC protocol outperforms the standard IEEE 802.11 in terms of energy savings thanks to its periodic sleep-listen cycle. It is well adapted to varying topology and ensures scalability due to its carrier sensing scheme. Nevertheless, S-MAC presents two main shortcomings. First, schedules are broadcasted and a node belonging to two schedules has to follow both schedules leading to a waste of energy. Second, the parameters of the protocol; i.e. active and sleep periods are constant and predefined beforehand. They remain unchanged after network deployment. This static listen and sleep periods make the S-MAC protocol inefficient under variable traffic load and inadaptable to network topology variations.

[75] Proposes Timeout-MAC (T-MAC), an enhancement of S-MAC to better perform under variable traffic load. Instead of fixed predefined listen period, an adaptive active period is used in T-MAC. Dynamic Sensor-MAC (DSMAC) [START_REF] Lu | An Adaptive Energy-Efficient and Low-Latency MAC for Data Gathering in Wireless Sensor Networks[END_REF] is another variation of S-MAC aiming to decrease the latency for delay-sensitive applications. Delay in S-MAC mainly occurs due to unsynchronized wake-up and sleep periods between the sender and the receiver. In the receiver side, average one-hop latency is evaluated. In case this value is high, the receiver shortens its sleep period and announces it to its neighbors. Upon the sleep period decrement receipt, the sender doubles its duty cycle in case it maintains packets destined to the considered receiver. It is shown in [START_REF] Anastasi | Energy conservation in wireless sensor networks: A survey[END_REF] that DSMAC presents reduced latency with comparison to S-MAC.

ii. Scheduled-based MAC protocols for wireless sensor networks Scheduled-based MAC protocols for wireless sensor networks mainly use the TDMA channel access scheme. TDMA gives a natural advantage regarding the energy efficiency, since the transmissions are scheduled and collisions are avoided leading to energy savings. Some probabilistic algorithms assigning slots to nodes exist like [START_REF] Rhee | Randomized dining philosophers to TDMA scheduling in wireless sensor networks[END_REF], where a slot is chosen in a random fashion and is used only if it is not allocated to another node in the same two-hop neighborhood.

[78] introduces Traffic-Adaptive Medium Access (TRAMA) protocol for wireless sensor networks based on a deterministic slot assignment algorithm. TRAMA performs according to three algorithms: (1) a neighboring protocol to gather two-hop neighborhood information, (2) a schedule exchange protocol to determine each node schedule, and (3) an adaptive election algorithm to select the transmitter and the receiver for each time slot. TRAMA holds a priority scheme for slots scheduling. A node chooses the slots for which it has the highest priority among all its neighbors in the contention area. The considered node is denoted by the winner node. It provides the receiver for each single slot. TRAMA increases the bandwidth utilization thanks to its schedule scheme in one side, and its adaptability to traffic patterns in another side. Nevertheless, it presents two major limitations: the complexity of its slot assignment algorithm, and the waste of energy due to an important amount of control packets.

As an improvement of TRAMA, [START_REF] Rajendran | Energy-efficient, application-aware medium access for sensor networks[END_REF] proposes the Flow Aware Medium Access (FLAMA) protocol. FLAMA proposes a simple slot assignment algorithm based only on local information. However, FLAMA was designed for gathering application based on tree topology, making it a non generic medium access control protocol.

iii. Hybrid MAC protocols for wireless sensor networks

One of the most interesting works among this class is Zebra MAC (Z-MAC) [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF]. The main motivation of Z-MAC is to perform a CSMA-based access scheme when contention is low, and to switch to a TDMA-based access scheme in higher contention level. In an initial setup phase, nodes exchange pings in order to gather information about the two-hop neighborhood. This information is an input to a scalable and distributed slot scheduling algorithm DRAND [START_REF] Rhee | Randomized dining philosophers to TDMA scheduling in wireless sensor networks[END_REF]. DRAND ensures a collision-free slot assignment, since slots are attributed such that nodes in the same two-hop neighborhood have different time slots. Z-MAC aims to increase bandwidth utilization by switching the protocol behavior between CSMA and TDMA according to the contention level [START_REF] Rhee | Z-MAC: a hybrid MAC for wireless sensor networks[END_REF]. Accordingly, two operating modes are defined: LCL (Lower Contention Level) and HCL (Higher Contention Level). All nodes operate in LCL, unless they receive an explicit contention notification from a two-hop neighbor. In the LCL mode, contention access is performed to get any time slot access; while in the HCL mode only nodes assigned slots called owners, and their one-hop neighbors are allowed to contend for these slots. In both modes, contention window size is adjusted such that owners always have higher priority to an early channel access compared with non-owner nodes.

From the energy point of view, the active period in Z-MAC is reduced to spare more energy. Z-MAC specifies that nodes should be awake during the whole active period. This contributes to additional waste of energy, since a node should only be awake when it is in transmit or receive state. Based on this observation, [START_REF] Minet | SERENA: SchEduling RoutEr Nodes Activity in wireless ad hoc and sensor networks[END_REF] proposes the SchEduling RoutEr Nodes Activity (SERENA) protocol. SERENA performs according to two levels. First, a distributed and localized two-hop coloring algorithm is run to attribute one color, later mapped on time slot, to each single node in the network. Second, additional slots are assigned adaptively to nodes traffic requirements. This task is accomplished via the SERENA slot assignment algorithm.

Conclusion

To sum up, a good strategy for saving more energy should combine the following attributes:

 Minimize collisions and interference effect via transmission schedule,  Coordinate the activity periods of the nodes; i.e. a node is awake only during its own slots, where it is in the transmit state, and during the slots assigned to its one-hop neighbors, where it is in the receive state,  Reduce the active period.

Based on these observations, we propose a new MAC protocol for wireless sensor networks called Sensor One shot Slot TDMA-based Reservation-based (S-OSTR) MAC protocol. S-OSTR is an accommodation of the OSTR protocol designed for wireless ad hoc networks, to the wireless sensor environment. It aims to take advantage from the dynamic and shorter frame size achieved by the OSTR protocol. S-OSTR prolongs the network lifetime based on three major features: (1) scheduling the transmissions based on a TDMA channel access scheme. (2) Providing a dynamic active period according to the network topologies and nodes arrival and /or departure to / from the network. (3) Coordinating the active and sleep periods for each single node such that a node is awake only during its own slot and the slots assigned to its one-hop neighbors. S-OSTR investigates the energy efficiency thanks to the aforementioned features. The first feature provides a transmission scheduling scheme that avoids the energy waste due to collisions; while the second feature adapts the active period according to the network density while ensuring an overall active period as small as possible. Finally, S-OSTR allows nodes to sleep during the active period so that energy waste due to idle listening is significantly reduced. One major advantage of S-OSTR consists of its quick adaptability to network changes and its quick recover from slot conflict situations.

In the following, a brief recall of the OSTR protocol for wireless ad hoc networks is first presented. Our motivations to accommodate the OSTR MAC protocol for wireless ad hoc networks to the wireless sensor environment are then tackled. Finally, the S-OSTR MAC protocol specifications are detailed.

S-OSTR Motivations

The OSTR MAC protocol for ad hoc networks

In our previous work, the focus was on increasing bandwidth consumption and ensuring per node fairness based on a new scheduling technique for medium access. The One shot Slot TDMA-based Reservation (OSTR) protocol has been introduced. The major goal of OSTR is to increase the channel utilization based on three main features: (1) first, it favors slot reuse and takes advantage from spatial reutilization. (2) Second, it performs an on-demand slot assignment; i.e. slots are assigned only if needed. This way, OSTR avoids bandwidth wastage due to free slot appearance in the frame. (3) Third, OSTR tackles the frame synchronization problem by introducing a novel mechanism called appointment mechanism combined with simple flooding mechanism. Hence, collisions caused by unsynchronized frame start points are considerably decreased while a lower frame size is achieved.

OSTR introduces a new TDMA-based scheduling technique that consists in increasing the frame size slot by slot, if needed. It deploys three main mechanisms: (1) neighbor detection, (2) Slot reservation mechanism, and (3) flooding and appointment mechanisms. OSTR is designed to work in a completely distributed manner. It addresses varying topologies by a periodic exchange of HELLO packets. HELLO packets exchange also enables new incoming nodes to discover their two-hop neighborhood. Upon HELLO packet receipt, a new arriving node populates its neighborhood table and selects an appropriate time slot following the OSTR slot reservation mechanism. This mechanism favors slot re-utilization. Thus, if the new node finds at least one free slot within a frame sized of K time slots, it chooses the time slot with the lowest number. Otherwise, it is constrained to increase the frame size and selects then the slot number (K+1). In case the frame size locally increases, the slots indexes change according to the new frame start point. Thus, the absolute slot positions in the overall network are modified and collisions occur resulting in a frame synchronization problem. To handle this problem, OSTR specifies that the frame size increase should be communicated among all nodes in the network, and the new frame size is adopted simultaneously. This is accomplished via two mechanisms: (1) a flooding mechanism that ensures the transmission of the frame size increase within the whole network, and (2) an appointment mechanism that sets a date when all nodes switch to the new frame size.

Multiple sets of simulations were run to evaluate OSTR performance compared with IEEE 802.11 distributed coordinated function (DCF). It is shown that OSTR achieves higher throughput than IEEE 802.11 (DCF) in saturation cases thanks to its spatial reuse. It also ensures higher fairness thanks to its schedule scheme that guarantees the channel access for all nodes in each frame cycle.

The OSTR MAC protocol appears as a promising solution for wireless multi-hop ad hoc networks. It presents the following advantages:  Channel utilization is increased, since OSTR achieves a shorter frame size thanks to the OSTR slot reuse scheme in one hand, and to the slot-by-slot frame size increase in another hand,  Contention-due collisions are eliminated with OSTR, since it uses a TDMA channel access scheme that guarantees channel access to each node,  Interference is significantly reduced as OSTR attributes slots such that nodes in the same two-hop neighborhood have different time slots,  OSTR is a per-node fair MAC protocol, since each node is assigned one time slot per frame cycle,  Adaptability to network changes and topology variations are held by the OSTR protocol, since it deploys a periodic control packet exchange,  The flooding mechanism combined with the appointment mechanism tackles the frame synchronization problem, while maintaining a fair slot distribution among all nodes in the network.

From ad hoc environment to sensor environment

One of the major advantages of the OSTR protocol is that it achieves a shorter frame size. This feature is typically attractive because it contributes to significant energy savings. This motivates us to accommodate the OSTR protocol to wireless multi-hop sensor networks where reducing energy consumption is of a primary concern. Recall that wireless sensor networks consist of a self-organized set of nodes, where each node has one or more sensors characterized by low-power radio, and limited power. In wireless sensor networks, a dispensed sensor can hardly be changed or recharged. Prolonging network lifetime is then a critical issue. In Section 4.2, we have shown that scheduling node activity is one of the energy savings methods for wireless sensor networks. It consists on switching between sleeping and active periods in order to minimize energy consumption. The shorter the active period is the less energy is consumed. Based on this concept, the OSTR MAC protocol appears as a good candidate to efficiently schedule the channel access while reducing the energy consumption. Three major sources of energy waste are identified: collision, control packet overhead, and idle listening. In order to deeply explain our motivations to accommodate the OSTR protocol to wireless sensor networks, we highlight the solutions offered by the OSTR protocol to deal with the aforementioned causes of energy waste.

 Collision / over emitting: Collision occurs when two or more packets are received simultaneously by the same node. Packet reception is then inconsistent and consequently a retransmission (over emitting) is needed leading to more energy consumption. Thanks to its time division multiple accesses combined with spatial slot reuse, the OSTR protocol provides a collision-free data transmission.  Control packet overhead: One of the main drawbacks of scheduled-based MAC protocols is the use of complex control mechanism (neighborhood discovery, clock synchronization, and so on). However, the fewer control packets are the more energy is spared. Apart from HELLO packets periodically sent, the OSTR protocol mainly uses a REQ/REPLY handshake for new arriving nodes. These handshakes are mainly deployed in the setup phase. Also, sensors generally have a periodic activity depending on the application requirements. That is, sensors may stay in idle state for a long period and start data transmission upon events detection. Consequently, HELLO period exchange of the OSTR protocol can be adjusted to minimize the energy while ensuring the application functionalities. The last type of control packet in the OSTR protocol is the Frame Change (FC) packet used to tackle different frame size coexistence in the network. Notice that sensor network applications are based, in general, on periodic activities repeated every polling cycle time. The polling cycle period is static and is the same for all nodes. Beyond this observation, the frame synchronization problem is gracefully handled, and consequently FC packets are no longer used in the context of sensor networks. A detailed proof of this feature is given in Section 4.4.4.  Idle listening: With the OSTR protocol, idle listening is only performed by the new incoming nodes in order to gather two-hop neighborhood information. Otherwise, nodes are scheduled such that every node is active to either transmit or receive data, i.e. during its own assigned slot and during the slots assigned to its one-hop neighbors, respectively. Accordingly, the OSTR protocol does not suffer from severe waste of energy due to idle listening.

As stated above, the OSTR protocol design can be easily accommodated to wireless sensor environment without additional cost. It takes advantage from its TDMA scheduling scheme and its slot-by-slot reservation technique. The former component provides contention-free data transmission, while the latter component yields to a shorter frame size, thus a reduced duty cycle ratio.

In the sequel, we detail the functionalities and the specifications of the Sensor One shot Slot TDMA-based Reservation-based (S-OSTR) MAC protocol.

Sensor OSTR

The Sensor One-shot Slot TDMA-based Reservation MAC protocol (S-OSTR) is an accommodation of the OSTR MAC protocol to wireless sensor environment. The main goal of S-OSTR is to minimize the energy consumption by reducing the duty cycle. The basic idea behind S-OSTR is to enable the nodes spare energy by alternating between an active period and an inactive period, while taking advantage from the shorter frame size achieved by the OSTR protocol. The longer the inactive (sleep) period is, the more energy is spared. Based on this observation, and since the OSTR protocol achieves a shorter frame size, the active period of S-OSTR is set to be equal to one OSTR frame cycle. S-OSTR behaves similarly to the OSTR protocol when a node joins the network. The major difference with the OSTR protocol is that the flooding and appointment mechanisms are no longer needed, since the alternate between active and inactive periods in sensor networks eliminates collisions due to the coexistence of different frame sizes in the network. In this section we summarize our assumptions about sensor networks and applications. We expect a network composed of a large number of sensors organized in an ad hoc fashion. We assume the communications are between nodes peers rather than to a single sink or base station.

Network and application assumptions

Inactive period active period Inactive period active period

T i T i+1

Polling cycle

The running application enforces an alternate between an inactive period and an active period where some events are detected and information have, then, to be transmitted. This assumption is justifiable, since applications in wireless sensor networks such as monitoring and surveillance are characterized by a long period of inactivity until something is detected. Like the standard 802.15.4 [3], the active and inactive periods are assumed to form a polling cycle as it is depicted in Fig33. The polling cycle duration is enforced by the application and is then the same for all sensors in the network. The time is, therefore, divided in polling cycle periods. For a coherent work of the network, sensors are required to be perfectly synchronized in order to wake up in the beginning of each polling cycle at the same time. Clock synchronization in wireless environment, and in particular in sensor networks is a critical issue to face. However, it is beyond the scope of our work. [START_REF] Prakash Ranganathan | Tim Synchronization in wireless sensor networks: A Survey[END_REF] and [START_REF] Latha | Clock Synchronization in Distributed Systems[END_REF] give detailed surveys on time synchronization techniques.

We also assume that each node has only one slot per frame and that there is only one frame cycle per one active period, i.e. one frame cycle per one polling cycle. In S-OSTR, time is divided in periodic polling cycles. As stated above, the duration of a polling cycle is fixed and defined by the application running on top of the S-OSTR protocol. As it is depicted in Fig. 34, each polling cycle is composed of two periods of time: an active period where DATA packets are transmitted and an inactive (sleep) period where all sensors turn off their radio to save energy. Intuitively, the longer the inactivity period is the more energy-efficient is the MAC protocol. Hence, S-OSTR uses a dynamic active period that can adapt to network topology changes and traffic patterns. The active period then consists on one OSTR frame cycle. Like OSTR protocol, the frame is divided into two parts: a CONTROL sub-frame where the channel access is contention-based and a DATA sub-frame where the channel access is scheduled-based. The CONTROL sub-frame is intended for new incoming nodes to access the network and for control packet exchange, while in the DATA sub-frame each active sensor sends a DATA packet during its assigned time slot. Mind, that we are mainly interested in the channel access method and its capabilities to provide energy-efficient solution, rather than providing a solution to assign multiple slots according to nodes traffic rate. Therefore, we make the assumption that each node only reserves one time slot per frame. This claim can be relaxed in future version of the protocol to make it adaptive to the sensors traffic requirements.

b) Packets formats

In this section, the S-OSTR packet formats are presented. S-OSTR deploys the same control packets as the OSTR protocol apart from the Frame Change (FC) packet. Unlike OSTR, the S-OSTR protocol for wireless sensor networks does not suffer from a frame synchronization problem making the deployment of the FC packets useless. More details of how S-OSTR gracefully handles the frame synchronization problem without the need of FC packets are given in Section 4.4.4.

HELLO Control Packet

Similar to OSTR, HELLO packet exchange is maintained in S-OSTR to track the topology changes in one hand and to update neighborhood information in another hand. HELLO packets are only sent during the CONTROL sub-frame. Unlike OSTR protocol, the HELLO sending period is longer than that defined for OSTR protocol. This is justified by two main reasons: first, wireless sensor networks are generally dedicated to a single application. Hence, in many scenarios a setup phase where all nodes are deployed precede the run of the application. Consequently, topology changes are not so frequent and are more likely to occur when a node is out of battery. Thus a large update period seems to be sufficient for such networks. Second, as stated in Section 4.4.1 a delay-tolerate application is assumed in this work. Hence, a long HELLO packet exchange period goes hand in hand with the long idle period tolerated by the application layer.

REQ and REPLY Control Packets

In S-OSTR, a REQ packet is sent during the CONTROL sub-frame by a new arriving node willing to reserve a time slot. As a response, one of the new node one-hop neighbors already assigned a time slot answers by sending a REPLY packet.

CONF Control Packet

In OSTR, a CONF is generated to indicate a conflict. The CONF is a broadcast packet in order to enable all nodes in the conflict area be aware of the conflict. A node that detects the conflict specifies which from the conflicting nodes will lose its assigned slot. It then, includes in the CONF packet the time slot number where the conflict occurred, and the MAC address of one of the conflicting nodes. Upon the CONF packet receipt, the latter abandons the current slot reservation process and starts a new one in the next polling cycle.

S-OSTR: Protocol description a) Periodic Listen and Sleep

The S-OSTR MAC protocol aims to save energy by reducing the active period in the polling cycle. It takes advantage from the shorter frame size achieved by the slot by slot frame size increase first defined in OSTR [START_REF] Sayadi | One shot Slot TDMA-based Reservation MAC Protocol for Wireless Ad hoc Networks[END_REF]. The TDMA channel access technique deployed in S-OSTR gives a natural advantage of energy conservation because of the periodicity of a TDMA frame enabling nodes to have a reduced duty cycle.

Besides, the S-OSTR MAC protocol uses an alternate between a dynamic active period and a dynamic sleep period in one polling cycle. When the dynamic active period relative to one sensor comes to the end, it turns off its radio and enters the sleep period. To provide energy-efficiency, S-OSTR also allows nodes to sleep during their dynamic active periods. In fact, a node should be awake to transmit/ receive packets or to monitor the channel. In S-OSTR, the nodes monitor the channel during the CONTROL sub-frame of the active period each HELLO period of time. This monitoring is necessary for the sensors to update their neighborhood information. Since S-OSTR specifications make use of a long HELLO sending period, the energy consumed in monitoring is limited. Second, nodes should be awake for data transmission and reception. Moreover, due to the broadcast nature of wireless channel a node can only communicate with its one-hop neighbors. Accordingly, S-OSTR specifies that a node should be awake during its assigned slot for data packets transmission and during the slots assigned to its one-hop neighbors. This task is easily deployed without additional cost, thanks to the periodic neighbor detection mechanism used in S-OSTR. This mechanism is based on a periodic exchange of HELLO packets including the slot assignment of the sender and its one-hop neighbors. Based on the HELLO packet exchange, each node is able to populate its neighborhood table based on which, each S-OSTR node schedules its sleep and wake up periods. For the sake of clarity, a simple sleep/wake up schedule with S-OSTR is analyzed. In Fig. 35, a simple connected network is plotted; while in the Fig. 36 the sleep and wake up schedule for each node is represented. This example, points out the ability of S-OSTR to handle multiple frame size co-existence in the same neighborhood. In the sequel, we assume a polling cycle where nodes should monitors the CONTROL subframe to gather HELLO packets.

Let N 1 (N) be the set of one-hop neighbors of node N. Let T pc and T f denote the Polling Cycle period and the frame period (T f is expressed in terms of number of time slots), respectively. Finally, let T sleep denote the sleep period of node N. According to the S-OSTR sleep/awake procedure, node N is awake during its own assigned slot and during the slots assigned to its one-hop neighbors, i.e. ( | N 1 (N)| +1) time slots. We assume that in the considered polling cycle, nodes should be awake during the CONTROL sub-frame to monitor the channel. This CONTROL sub-frame is assumed to be equal to one time slot. Accordingly, the total number of slots during which node N is awake is given by [START_REF]The Internet of Things -Strategic Research Roadmap[END_REF].

(| N 1 (N)| +2) (1)
Therefore, the sleep period, in terms of number of time slots, of node N is given by [START_REF] Anastasi | Energy conservation in wireless sensor networks: A survey[END_REF].

T sleep = T pc -(| N 1 (N)| +2) (2)
We recall that T pc is enforced by the application. It is fixed and constant for all nodes in the network. Considering E sleep the energy spent in Sleep state, the energy savings relative to node N is given by (3):

E s = (T sleep / T pc ) = (1-(| N 1 (N)| +2)/ T pc ) x E sleep (3)
The last item in the above equation is the duty cycle of the node in S-OSTR.

In this Section, the focus was on the S-OSTR node activity; i.e. sleep and wake up, scheduling. It is shown that in addition to the shorter frame size achieved inferring a shorter active period in the polling cycle, S-OSTR enhances the energy savings thanks to the local node activity scheduling; i.e. nodes are only awake during their assigned slot and the slots assigned to their one-hop neighbors. Recall that S-OSTR is an accommodation of the proposed OSTR protocol to wireless multi-hop sensor networks. OSTR consists of three main mechanisms: (1) Neighborhood detection, (2) Slot reservation mechanism, and (3) Flooding and appointment mechanism. The latter mechanism is deployed to tackle the frame synchronization problem. In the following, we prove how S-OSTR does not suffer from this issue and consequently the flooding and appointment mechanism are useless for S-OSTR. Thus, the S-OSTR MAC protocol restricts to two mechanisms: (1) Neighbor detection, and (2) Slot reservation mechanism.

b) Neighbor Detection

Like OSTR protocol, S-OSTR is designed to work in a completely distributed manner. It addresses varying topology changes by a periodic exchange of HELLO packets. HELLO packets are broadcasted by a node to its one-hop neighbors and are never forwarded. They are transmitted during the CONTROL sub-frame in a contention-based fashion. A HELLO packet includes the following information: Including a list of the one-hop neighbors in the HELLO packets is required to have slot assignment information in the two-hop neighborhood. Hence, upon a HELLO packet receipt, a node updates its neighborhood information and discards the packet. Unlike OSTR protocol, S-OSTR specifies a long HELLO period with respect to the application assumptions presented in Section 4.4.1. Besides, extending the HELLO period exchange yields to the traffic overhead reduce. Consequently, S-OSTR reduces the energy waste due to control packets transmission. The HELLO packet exchange also enables new incoming nodes to populate their neighborhood table based on which they select an appropriate time slot.

c) Slot Reservation Mechanism i. Sensing period and neighborhood information gathering

A new incoming node senses the channel to gather information about the slot distribution in its contention area. In the OSTR protocol, the node senses the channel for at least two time frames. In the S-OSTR MAC protocol the channel sensing slightly differs from that in the OSTR protocol, since it should consider energy constraints in one hand and the wake up and sleep alternate of sensors in another hand. Indeed, the time in S-OSTR is organized in polling cycles divided by their own in sleep and active periods. The latter is the mandatory part of the polling cycle and is composed of a CONTROL part where control packets including HELLO packets are sent, and a DATA part dedicated to DATA packet transmission. As HELLO packets receipt suffices to enable a new arriving node to gather information about the slot distribution and the frame sizes in its two-hop neighborhood, listening to the whole frame is useless and energy-inefficient. Hence, in S-OSTR the sensing period is made of multiple wakes up periods. The node wakes up at the beginning of each polling cycle, and monitors the channel only during the CONTROL sub-frame. Then, it sleeps until the next polling cycle. As channel access during CONTROL sub-frame is contention-based, packets collisions are likely to occur, yielding to inaccurate two-hop neighborhood information. Consequently, S-OSTR specifies that the sensing period should be longer than one polling cycle. After the sensing period, the new node maintains information about the slot distribution and the frame sizes in its contention area enabling it to properly choose a time slot.

1. Select the maximum frame size, denoted by K, among the frame sizes of onehop neighbors;

2. If there is at least one FREE time slot within the frame sized of K time slot, select the one with the lowest number, otherwise go to step 3;

3. Select the slot (K+1) and exit. Based on its two-hop neighborhood information, the new node selects a time slot following the S-OSTR slot selection algorithm depicted in Fig. 37. The S-OSTR slot selection algorithm slightly differs from that defined in OSTR. The major characteristic of increasing the frame size slot-by-slot is maintained. However, when OSTR ensures a common frame size in the whole network, S-OSTR tolerates the co-existence of many frame sizes in the network. Thus, with the OSTR protocol the slot is chosen regarding one common size of the frame. However, with S-OSTR a node may have multiple frame sizes in its two-hop neighborhood. We have then slightly modified the OSTR slot selection algorithm to consider multiple frame sizes in the same contention area of a new node. The new node then, first selects the maximum frame size denoted by K among all the frame sizes in its two-hop neighborhood. If at least one time slot is free among this maximum frame size, then the new node chooses the slot with the lowest number. Otherwise, it chooses the slot number (K+1). A slot is considered a free slot for a node N if it is assigned to any node in node N two-hop neighborhood.

iii. REQ transmission and REPLY listening

Once the slot is chosen, the new node selects among its one-hop neighbors the one which is assigned the lowest slot number to be the REQ destination. Then, it sends a REQ packet during the CONTROL sub-frame to request for the intended slot reservation. The REQ destination node checks if the chosen slot may cause a conflict. If it is not the case, it sends a REPLY packet during its assigned time slot to confirm the new node slot reservation.

Similar to the OSTR protocol, the REQ destination is set to be the one-hop neighbor allocated the lowest slot number. We recall that this choice enables the OSTR protocol to decrease the flooding delay since the flooding mechanism is initiated by the REQ destination node. In S-OSTR instead, this choice enables the new node to know during which time slots it should wake up to receive the REPLY packet.

iv. REPLY listening and Transmission decision

A requesting node that has sent a REQ packet during the CONTROL sub-frame of frame j, listens to the slot of the REQ destination node in the same frame j. In case no REPLY packet is received, the new node restarts a new reservation phase. Otherwise, the node updates its frame size in case the slot selection algorithm yields to the frame size increase and starts DATA transmission in the next polling cycle (j+1). S-OSTR also specifies that the new incoming node sends a HELLO packet in the polling cycle during which it joins the network (j+1, in case it has correctly received the REPLY during frame j). This specification contributes to the save of energy because it avoids the hidden terminal situation in case the new node joins the network such that two of its one-hop neighbors are hidden from each other. More details about this issue are given in the next section. In the sequel, the frame size evolution in the S-OSTR MAC protocol is analyzed. For the sake of clarity, we consider the network example depicted in Fig. 38. The considered network is composed of 6 nodes; each of them is represented by a pair (letter/number). The letter refers to the node identifier, while the number denotes the slot assigned to the node. We consider an initial slot distribution that allocates slot 1 to nodes A and D, slot 2 to node B and slot 3 to nodes C and E. The frame size equals then 4 times slots (including the slot 0 dedicated to the CONTROL sub-frame). When node N joins the network, it checks the slot distribution in its two-hop neighborhood. As no FREE slots are available in the current frame size of 4 time slots, node N requests a reservation for slot number 4 from node D. We assume that node D confirms the reservation and sends a REPLY packet during the polling cycle T i . Therefore, nodes C and N are aware of the new frame size, i.e. 5 time slots, during the same polling cycle T i . These nodes, then, update their information and change their frame size from 4 time slots to 5 time slots. We assume that node N starts transmitting in the next polling cycle, i.e. (T i+1 ) and hence its one-hop neighbors will adopt the new frame size also in the polling cycle T i+1 . This assumption will be justified in the following.

The reason behind the frame synchronization problem is the dependency between the slots indexes and the frame start point. In case the frame size locally increases, the frame start point is locally translated and consequently the slot indexes are mixed up and collisions occur. With S-OSTR this problem is gracefully alleviated thanks to two main features:

1) The restriction of the active period to one frame cycle, 2) Nodes synchronization due to the enforced uniform polling cycle.

In fact, the constant predefined polling cycle provides a global synchronization to the overall network. Consequently, all sensors wake up at the beginning of a new polling cycle, i.e. at the same time. Since the polling cycle begins with the active period that consists of one frame cycle, whatever the frame sizes are in the network the start point of all of them is synchronized with the beginning of the polling cycle. This first component of S-OSTR is necessary but not sufficient to avoid frame synchronization-due collisions. Indeed, if a multiple frame cycles were allowed in the active period, the same frame synchronization issue as with the OSTR protocol is faced. Hence, it is mandatory to avoid a multiple time frames in one polling cycle. This justifies our assumption given in Section 4.4.1 stating that there must be only one frame cycle in an active period, i.e. in one polling cycle.

To sum up, the S-OSTR MAC protocol handles the frame synchronization problem thanks to two main features: first, a global synchronization within the overall network is ensured by the constant predefined polling cycle enforced by the application layer. Second, the uniqueness of the frame cycle in one active period, i.e. in one polling cycle, forces the sensors to start a new frame simultaneously. The design of S-OSTR should consider the minimization of the energy waste due to the over emitting, the control overhead, collisions and idle listening. We have shown till now, how can S-OSTR minimize the traffic overhead, collisions and idle listening. In Fig. 39, a hidden terminal problem is illustrated. For the sake of clarity, we consider the same network described in Fig. 38. We added one-hop neighbor to node B, so that the initial frame size is 5 time slots. When node N joins the network, it follows the slot selection procedure defined in S-OSTR, and requests the slot number 5 from node D. The latter sends a REPLY to confirm node D reservation. As node F is hidden from node D, it cannot update its frame size from 5 to 6 time slots. In the figure, the frame size evolution from nodes D, C and F points of view is depicted. Suppose that node N joins the network upon the receipt of the REPLY packet, i.e. let T i the polling cycle during which the REPLY packet is received by node N, node N joins then the network during T i . In this case, node N transmits its DATA packets while node F is sleeping. This leads to packets loss and inconsistent communications. Since S-OSTR specifies that sensors turn off their radio and sleep when the frame cycle ends, node F will never hear the information about the frame size increase in its neighborhood unless it hears a HELLO packet. The idea then, is to tolerate additional delay for the new node application and to delay the new node transmission till the next polling cycle. However, node F needs to update its frame size before entering the sleep period, that's why S-OSTR specifies that each new incoming node sends a HELLO packet even if the HELLO sending period is not ended. Suppose a new node has received the REPLY packet during the polling cycle T i , it has to send a HELLO packet during the next polling cycle T i+1 , before sending its data packet during its own assigned slot.

b) S-OSTR: Handling the hidden terminal problem

E/3 A/1 B/2 C/3 D/1 N/5 F/4 N/5 C/3 B/2 D/1 0 N/5 C/3 B/2 D/1 0 N/5 F/4 C/3 B/2 D/1 A/1 0 N/5 F/4 C/3 B/2 D/1 A/1 0 sleep F/4 C/3 B/2 A/1 0 sleep F/4 C/3 B/2 A/1 0 N/5 C/3 B/2 D/1 0 N/5 C/3 B/2 D/1 0 N/5 F/4 C/3 B/2 D/1 A/1 0 N/5 F/4 C/3 B/2 D/1 A/1 0 aw ake F/4 C/3 B/2 A/1 0 aw ake F/4 C/3 B/2 A/1 0 N joins the network N sends HELLO T i T i+1 T i+2 D C F

Slot conflict resolution in the S-OSTR protocol

In S-OSTR a conflict of slot assignment occurs in two cases:

1. When a new node connects to two or more nodes to which the same slot is assigned or, 2. When a node moves such that it enters the contention area of another node assigned the same slot number.

In the former case, while joining the network, a new node populates its neighborhood table based on which it selects an appropriate time slot to reserve. While checking its neighborhood table, the new node verifies whether two of its one-hop neighbors have the same assigned slot. If it is the case, the node delays its reservation, and sends a conflict (CONF) packet including the number of the slot causing the conflict. The CONF is destined to the node with the highest MAC address. Notice that this choice is totally arbitrary and can be changed according to the application requirements. Upon the receipt of the CONF packet, the conflicting node releases its slot and enters a new reservation phase in the next polling cycle. Meanwhile, the new node that has detected the conflict increases its contention window size and contends for the channel access to enter the reservation phase once again.

In the second case, the periodic HELLO packet exchange allows both conflicting node to update their neighborhood table. While checking this table, they both detect the conflict between their own assigned slot and the slot attributed to one of their neighbors. Consequently, S-OSTR specifies that the one with highest MAC address releases its slot and enters a new reservation phase. Simulations have been performed for different wireless networks. Table 4 lists the different simulation parameters. We consider a multi-hop environment with random generated topologies where the number of nodes varies from 50 nodes to 150 nodes. User traffic consists of 20 flows, with randomly chosen sources and destinations. Simulation results are averaged over 10 simulation runs.

S-OSTR: Performances Evaluation

In order to study the energy efficiency of the S-OSTR protocol, we have included the battery package in the simulation [83]. This package is a part of the mobility framework project [65]. It implements simple energy consumption model. All nodes in the network have the same battery capacity initialized to 25mAh. The battery left is then recalculated each time the radio state has changed from one state to another. We consider three different radio states: the RX state where the battery is consumed is 200mA, the TX state that consumes 172mA and the SLEEP state that consumes the less amount of battery (0,85mA).

S-OSTR: intrinsic characteristic evaluation a) Network lifetime

In this Section, we analyze the energy efficiency aspects of S-SOTR. We quantify the network lifetime as well as the amount of user data delivered for different networks where the number of nodes rises from 50 to 150 nodes. Fig. 40 shows the evolution of network lifetime achieved with S-OSTR as the medium access control protocol, with the number of nodes. The network lifetime is defined as the time until the first sensor is out of battery. Fig. 40 shows that the network lifetime decreases with the number of nodes in the network. This result was expected. Indeed, the network lifetime computation for these simulations is split in two main phases:

1) The first 150s of the simulation are reserved for node entries in the network. In this phase of the simulation, REQ/REPLY exchange is performed to enable new nodes join the network. HELLO packets exchange is also enabled to update neighborhood information.

2) The second phase starts at 150s and lasts until the end of the simulation. During this phase, user data is sent between random source destination peers. Also, the HELLO mechanism is still performed to track network topology changes and to update neighborhood information.

The increase of the number of nodes yields to an increase of the traffic overhead, i.e. the number of REQ/REPLY enabling nodes join the network, and the number of HELLO packets performed to update neighborhood information as well. Thus, more energy is spent due to the increase of the traffic overhead leading to the decrease of network lifetime according to the number of nodes in the network.

Nevertheless, we notice that network lifetime decrease is not significant. When the number of nodes is doubled (from 50 nodes to 100 nodes) the network lifetime is decreased by about 1.78%. It is decreased by 1.92% when the number of nodes rises from 50 nodes to 150 nodes. This observation shows the robustness of S-OSTR protocol to network scalability thanks to its node activity scheduling. Indeed, the extra-energy consumed due to the number of nodes increase is balanced by the node activity scheduling deployed by the S-OSTR protocol. The latter specifies that a node is active only during its assigned slot and the slots assigned to its one-hop neighbors. Consequently, the overall number of nodes in the network has less influence on the network lifetime than, the network density defined as the number of neighbors in the two-hop neighborhood.

In Fig. 41, the average user data delivered is plotted for different number of nodes in the network. The amount of user data delivered decreases with the number of nodes. This result is coherent with the decrease of network lifetime depicted in Fig. 41. Indeed, when the network lifetime decreases, the nodes have less energy, and thus send less number of packets.

b) Slot reuse

One of the important features brought by S-OSTR is the spatial reuse scheme. The S-OSTR protocol deploys a slot assignment mechanism that favors the reutilization of a slot if possible. To highlight the spatial reuse feature, we consider a network of 150 nodes, achieving a frame size equal to 21 slots (including slot 0 dedicated to the CONTROL sub-frame). The other simulation parameters remain the same as in Table 4. Fig. 42 provides the slot reuse achieved with S-OSTR for this configuration. It provides the distribution of shared slots among the nodes in the network. We first notice, that all slots are used, and there is no empty slot. This reflects the slot-by-slot increase of the frame according to nodes arrival in the network. Thus, the bandwidth is efficiently consumed with S-OSTR. In this configuration, the distribution of shared slots among the nodes in the network is as follow: 5 slots are shared by 7 nodes, 3 slots are reused by 8 nodes, 30 (5+6+9+10) nodes share 2 slots, and 31 nodes reuse one slot. This spatial reuse brought by the slot assignment mechanism of S-OSTR justifies the shorter frame size achieved by the protocol (21 slots for 150 nodes) and results in efficient channel utilization.

S-OSTR evaluation with comparison with SERENA

In this Section, we will compare the performance of the Sensor OSTR protocol with SERENA [START_REF] Minet | SERENA: SchEduling RoutEr Nodes Activity in wireless ad hoc and sensor networks[END_REF].

a) Simulation assumptions

SERENA is based on two algorithms:

1) A two-hop coloring algorithm that assigns a color to each node. The color is mapped then to a slot attributed to the node, and during which it transmits user data. Each color is unique in a two-hop neighborhood area, and it is used three-hop away.

2) SERENA protocol assigns at least one time slot per node. It enables a slot assignment algorithm to assign additional slots to nodes according to their traffic and the number of colors they can see in their two-hop neighborhood.

In this Section, we focus on comparing the performance of the coloring algorithm of SERENA and the S-OSTR protocol, i.e. in the simulated runs, SERENA only assigns one color to each node.

Another important feature to consider is that SERENA needs to wait for the coloring of all nodes in the network before user data transmission is performed. It supposes a set of nodes existing at the same time and forming a connected network, which is not the case of S-OSTR that enables new node entries one by one until a set of nodes is reached (for the sake of simulations). For fair comparison sake, we compare SERENA coloring algorithm with a special version of S-OSTR denoted by: S-OSTR without HELLO mechanism.

First, S-OSTR is running with HELLO mechanism turned on in order to enable the nodes join the network until the intended number of nodes is reached. We refer to this phase as the network setting phase. It is to mention that the energy consumed during network setting is not taken into account. Once the network setting phase is over, nodes disable the HELLO mechanism and run the S-OSTR without HELLO mechanism version. This is justified by the fact that SERENA assumes no network topology changes after the nodes have been assigned their corresponding colors. Consequently, nodes deploying S-OSTR without HELLO mechanism turn off their radio, and enter the SLEEP state during the CONTROL sub-frame.

b) S-OSTR: with and without HELLO mechanism

Before investigating the comparison study between S-OSTR and SERENA, we first highlight the impact of disabling the Hello mechanism on the S-OSTR performance. In Fig. 43, we plotted the network lifetime reached by both S-OSTR versions (with and without Hello mechanism) for different number of nodes rising from 50 nodes to 150 nodes. The results in Fig. 43 show that disabling the Hello mechanism increases the network lifetime whatever the number of nodes in the network is. For instance, network lifetime increases from 502s to 517s, from 493s to 502s, and from 492s to 499s for 50, 100, and 150 nodes, respectively. This result is expected. Indeed, disabling the Hello mechanism implies:

 The reduction of traffic overhead that leads to the spare of transmission and reception energy spent in exchanging and processing the HELLO packets,  The spare of energy dissipated in over-hearing during the CONTROL sub-frame.

Consequently, less energy is dissipated leading to an overall network lifetime increase.

c) Network lifetime and user data delivered

In Fig. 44, we plotted the achieved network lifetime for both versions of S-OSTR (enabling and disabling the Hello mechanism) and for SERENA for a number of nodes in the network rising from 50 nodes to 150 nodes.

The results in Fig. 44, highlight the capacity of S-OSTR to achieve higher network lifetime comparing to SERENA even though the HELLO mechanism is enabled. In Fig. 45, the network lifetime gain achieved with S-OSTR in both modes, i.e. with and without Hello mechanism relativelly to that achieved with SERENA is plotted. For 50 nodes, S-OSTR disabling the Hello mechanism increases the network lifetime by around 6%, while S-OSTR enabling the Hello mechanism reaches a gain around 3%. Eventhough the number of nodes increases, S-OSTR still outperforms SERENA and reaches a gain around 4% when disabling the Hello mechanism, and a gain of 2% when enabling the Hello mechanism, for a number of nodes equal to 100 nodes.

In Fig. 46, the amount of user data delivered with S-OSTR and SERENA is plotted. The results go hand in hand with the network lifetime achieved with both protocols. In fact, nodes deploying the S-OSTR protocol save more energy. Consequently, more packets are sent yielding to higher user data delivered comparing to SERENA. 48 show that with S-OSTR, nodes spend less time in TX and RX states comparing to SERENA for different number of nodes. Consequently, S-OSTR spare more energy comparing to SERENA since it increases the amount of time spent in SLEEP state (The state consuming the least energy). This is highlighted in Fig. 49 and Fig. 50 where the amount of simulation time spent in SLEEP state is plotted for both S-OSTR and SERENA. This is an important benefit brought by S-OSTR justified by two features: 1) First, S-OSTR achieves a shorter frame size thanks to its slot reuse scheme. The shorter the frame size is the longer the inactive period is. Thus, with S-OSTR nodes are able to turn off their radio for a longer period of time. In Fig. 51, we plotted the average overall frame size in the network. The frame size reached with S-OSTR is shorter than that achieved with SERENA for a number of nodes equal to 150 nodes (22 assigned slots for S-OSTR comparing to 25 assigned slots for SERENA).

2) Second, with S-OSTR the shorter frame size achieved is combined with a more reliable node activity scheduling scheme to favor the SLEEP state. In fact, for a number of nodes equal to 100, the S-OSTR achieves an average frame size equal to 22 slots, compared to 20 slots for SERENA. Nevertheless, nodes with S-OSTR sleep longer than nodes deploying SERENA (21% of simulation time for S-OSTR comparing to 19% for SERENA, for 100 nodes). This is justified by the fact that S-OSTR enables nodes to turn off their radio according to the node activity in the neighborhood.

Conclusion

The energy is of primary interest in wireless sensor networks. In this chapter, we first highlighted the main causes of waste of energy. We showed that a good MAC protocol design for wireless sensor networks should not only coordinate the channel access between the nodes, but also save more energy. We showed that using a random access scheme as for contention-based MAC protocols, node energy is not optimally used because of collisions and interferences due to the random access scheme. Moreover, we showed that TDMA-based MAC protocols have a natural advantage thanks to their scheduled access minimizing the interference effect. We highlighted also the effectiveness of a node activity scheduling to spare energy.

A good strategy for saving more energy should combine: (1) the minimization of collisions and interference effects, (2) a reliable node activity scheduling, and (3) prolonging the inactive period time where sensors are in SLEEP state.

Beyond the theoretical analysis, we provided a solution that consists in accommodating the One shot Slot TDMA-based Reservation (OSTR) MAC protocol first designed for wireless ad hoc networks, to the wireless sensor environment. The proposed protocol is called Sensor OSTR (S-OSTR). S-OSTR brings the idea of a dynamic active period that quickly accommodates to network changes and ensures a shorter frame size, i.e. shorter active period. With S-OSTR, nodes are able to sleep during the active period. Each node is, indeed, active only during each own slot and the slots of its one-hop neighbors improving this way, the overall network lifetime. Moreover, with S-OSTR collisions and interferences are significantly reduced by combining the scheduled channel access with an appropriate node activity scheduling. S-OSTR organizes in a totally distributed way the channel access such that energy is optimally consumed.

In this chapter, we also presented the main results obtained by simulating S-OSTR. We have implemented S-OSTR in OMNET++ network simulator. We evaluated our proposal against the two-hop coloring algorithm deployed in SERENA protocol.

We have showed the importance of the spatial reuse scheme incurred in the S-OSTR protocol. We highlighted the impact of the Hello mechanism deployed to track topology changes on the node energy savings. Simulation results have shown the benefits brought by S-OSTR:

 The network lifetime is improved compared to the two-hop coloring algorithm.

 The user data delivered is increased proportionally to the network lifetime.

 The robustness against network scalability is improved thanks to the spatial reuse scheme and the slot-by-slot frame size increase.

Chapter 5

Conclusions and Perspectives 5.1. Conclusions

Future Work

The future networks are going straightforward toward the internet of future characterized by connectivity "Anytime, Anywhere, with Anyone and Anything". This trend will give rise to new business and commercial opportunities to create innovative real time services, handle incidents and environmental degradation (e.g. disaster, global warming, pollution, and so on), enhance achievements in health care applications (old people assistance, diabetes and pulse monitoring, etc.), integrate the new green lifestyle (efficient energy consumption by vehicles, smart energy metering in buildings, etc.). These achievements, of course, could not exist without ensuring a good integration and interoperability with the legacy heterogeneous communication networks and involving ad hoc communication way enabling connectivity between billions of things. In this perspective, wireless ad hoc and sensor networks are a promising approach to provide the foreseen ubiquitous connectivity. Wireless ad hoc networks, indeed, provide seamless last mile internet access; while wireless sensor networks give cost-effective low power device monitoring and network data collecting.

Despite the enormous amounts of research on wireless multi-hop ad hoc and sensor networks, there are still many potential challenging research topics to investigate for a consistent deployment in the Internet of future, whereas medium access control design is one of them. In this thesis, we investigate the medium access protocol design with respect to the main requirements of future networks:

 Accommodation to network variations and mobility, a crucial feature mandatory to ensure anywhere and anytime connectivity,  Efficient channel utilization: the billions of things involved in the future internet are faced to the scarcity of the available resources. Efficient and smart bandwidth exploitation is therefore an important issue to investigate.  Fairness channel usage: the vision of the internet of future is to ensure communication between human things and objects things inferring a persistent need to access the channel. An unfair channel access favors some things to another which is even against the philosophy of ubiquitous connectivity with everything,  Energy efficiency: The involvement of all kind of things in the internet of future requires significant amount of energy that needs to be efficiently used in order to respect the tendency towards a green solutions, and diminish the impact of wireless communication infrastructure on the environment.

In the following Section, we provide an overview of the accomplishments of this thesis while in Section 5.2 we discuss directions for future works.

Conclusions

Wireless multi-hop ad hoc and sensor networks provide a promising solution to ensure ubiquitous connectivity for the future internet. Obviously, good network connectivity requires a reliable medium access control protocol design which is a challenging task in the ad hoc and sensor environments. The broadcast and shared nature of the wireless channel renders the bandwidth resources limited and expose the transmissions to relatively high collisions and loss rates. Traditional IEEE 802.11 DCF based on carrier sense multiple access presents lower channel utilization under heavy load and suffers from short term unfairness. These limitations give rise to more appropriate MAC protocols to the hostile environment of ad hoc networks. The necessity to provide guaranteed QoS to the upper layers triggered the design of conflictfree MAC protocols. The TDMA synchronization constraint is basically behind the rush of MAC protocol design based on a fixed frame size. This design shows inflexibility towards network variations and results on network dimensioning issue that leads to a famine risk in case the network is under-dimensioned, and to a waste of resources, otherwise. Moreover, the alternative dynamic protocols provide more adaptive solutions to network topology variations on dispense of a fairness access to the channel. Alongside with the efficient channel usage and the fairness medium access, reduce the energy consumption represents another challenge for ad hoc and sensor networks. Solutions like node activity scheduling tend to increase the network lifetime while respecting the application requirements.

In this thesis, we have presented our investigations toward giving solutions to the aforementioned research directions. We have highlighted the limitations of the contentionbased MAC protocol, especially the standard IEEE 802.11 in both DCF and EDCA modes, to provide efficient and fair channel access. We have also, proposed a novel classification of the contention-free MAC protocol based on the TDMA frame characteristic. Two families rose: static-frame size, and dynamic frame size-based MAC protocols. It has been found that despite their flexibility and higher performance with comparison to carrier sensing schemes, fixed-frame size-based MAC solutions suffer from bandwidth wastage mainly due to free slot appearance. This limitation combined with the lack of research effort in investigating the dynamic frame size-based schemes, gives us a hint to go further in this directive.

We have proposed a new TDMA based dynamic frame size-based MAC protocol for wireless multi-hop ad hoc networks. The idea of OSTR is to adopt a dynamic frame size that increases slot-by-slot, only if needed. OSTR consists in three mechanisms:

1. A neighbor detection and topology tracking mechanism that consists in sending HELLO packets periodically. This mechanism gives OSTR enough flexibility to adapt to different application scenarios, and to handle node movement in future versions.

2. A slot reservation mechanism that reserves a time slot for each active node in the network and performs a spatial reuse to keep the frame size as low as possible. The reservation scheme combined with a spatial reuse makes the OSTR protocol a good candidate to guarantee better QoS while ensuring an efficient and fair channel access thanks to the slot-by-slot frame size increase technique.

3.

A flooding and appointment mechanisms that are deployed to tackle the so called frame synchronization issue resulting from the coexistence of different frame sizes in the same network. The appointment technique has the advantage to not impact the existing slots schedules.

We have implemented the OSTR protocol in OMNET++. We have validated OSTR with two comparative studies. First, the throughput gain resulted from the natural advantage of the TDMA schedule has been highlighted while comparing OSTR with the standard IEEE 802.11 in DCF mode. It has been shown that OSTR is more appropriate to high loaded networks thanks to its scheduled access and spatial reuse schemes. Second, we have proved the effectiveness of the dynamic slot-by-slot frame size increase technique via a comparison study with the power of 2 frame size increase technique proposed by Kanzaki et .al [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF]. For this end, we have proposed a formalization of the frame size increase technique. Moreover, we have pointed out the capacity of OSTR to provide fair channel access and more secure solution at the MAC layer thanks to its reservation mechanism inferring a network-based admission decision for new incoming nodes.

The second contribution of this thesis covers the MAC protocol design in multi-hop wireless sensor networks. At first glance, the contribution looks relatively different from the previously discussed one since we change the overall context from ad hoc environment to sensor environment. However the two contributions are closely related in the sense that energy-efficiency is an important issue in any communication system and especially in wireless networks where users need to be equipped with power-limited batteries. Also, a sensor network differs from ad hoc networks by their low capacities, and limited coverage and communication range. They need to face the same MAC protocol design issues as for ad hoc networks with particular insights on how to reduce the energy consumption so that the network lifetime is prolonged.

We designed Sensor OSTR to maximize the network lifetime in wireless sensor networks. This proposal brings the idea of dynamic active period that adapts to network density and leads to an overall shorter frame size inferring a shorter active period for the sensors. S-OSTR consists of two mechanisms:

1. A neighbor detection mechanism that gives the S-OSTR protocol the potential to accommodate the dynamic topology changes due to the movement of nodes.

2. A slot reservation mechanism that brings a guaranteed channel access for each sensor while reducing the overall activity period leading to efficient energy consumption.

To design S-OSTR, we have first highlighted the main causes of energy waste, and have pointed out the major application requirements in sensor environment. In a second step, we have broken down the natural potentials brought by the OSTR protocol design to provide a good strategy for saving energy. Thus, the feasibility of such protocol design is proven. Afterwards, we have detailed the new S-OSTR protocol where its capacity to gracefully tackle the frame synchronization issue has been enlightened.

We have verified the performance of S-OSTR using extensive simulations and a comparative study with a two-hop coloring algorithm. We have firstly, focused on the impact of neighbor detection and update mechanism on the waste of energy. The simulations have shown that the periodic HELLO mechanism has less impact on network lifetime. One of the most interesting results is the ability of S-OSTR to prolong the time spent in the sleep state, the state consuming the less energy at all. This is a direct consequence of the energyefficiency brought by combining an accurate time slot schedule and a shorter achieved overall frame size. The comparative simulations between S-OSTR and SERENA have highlighted the importance of the reservation scheme brought by S-OSTR. The reservation mechanism leads to a more accurate slots distribution according to the nodes position in the network and nodes arrival to the network. In addition to its ability to prolong network lifetime, we have highlighted the major role played by the slot-by-slot frame size increase combined with the spatial reuse scheme to enhance the S-OSTR robustness against scalability.

In this thesis we have submitted two main contributions that affect many aspects of wireless networks, in particular wireless ad hoc and sensor networks. We have given hints in the medium access control protocol design in these two challenging environments. We mainly contribute two novel MAC protocols: OSTR for wireless ad hoc networks and S-OSTR for wireless sensor networks. Both are based on a new slot-by-slot frame size increase technique. This technique presents good potentials to support QoS requirements, to provide energy-efficiency, to ensure fair medium access, to accommodate network topology changes and finally, to enhance robustness against scalability. We have used OMNET++ simulations to study the performance of both OSTR and S-OSTR. Our two proposals are from now on available to be used as a separate MAC layer in the simulator. For the sake of performance comparison, we have also investigated the development of the E-ASAP protocol in the OMNET++ simulator.

We are confident that our work has contributed in the research efforts provided in the medium access protocol design for wireless ad hoc and sensor networks. We have paid attention to the importance of a dynamic TDMA-based solution that has not been largely investigated in the recent years. We had faith on the capacity that can be brought by such dynamic frame evolution, and this thesis consolidates our beliefs by enlightening the potentials carried by OSTR and S-OSTR protocols; which make them good candidates to integrate the Internet of future. Although our work, have brought solutions to a wide range of issues (frame synchronization issue, hidden terminal problem, slot reservation scheme, spatial reuse scheme, energy efficiency, node activity scheduling, distributed environment, etc.), it leaves ample room for improvements and gives hints to innovative future directives. In the next Section, we end this thesis by discussing some future enhancements to our work and providing new ideas to further investigate.

Future Works

OSTR slot release: In the current version of OSTR we have focused on the frame size increase, and have investigated the frame synchronization issue. An important enhancement to our work is to implement the slot release procedure. One of the eventual solutions for the slot release with OSTR is inspired from the appointment mechanism. Indeed, the critical aspect to face is that a slot that is no longer locally occupied can be assigned to other node three-hops away. This feature is a direct consequence from the spatial reuse scheme deployed in OSTR. Beyond this observation, two mandatory conditions are required to initiate a slot release procedure in OSTR. First, the slot should be the last slot in the frame; i.e. in a frame sized of 4 time slots including slot 0 for CONTROL sub-frame, the slot to release should be the slot number 3. Second, the slot must no longer be used in the whole network. Consequently, the idea of applying the appointment mechanism rises. One solution could be the following: a node that will release its slot in the near future sets an appointment on which the frame size could be decreased by one. It broadcasts therefore, a control message to ask whether the released slot is used elsewhere in the network. In case at least one node is still assigned the considered slot, it broadcasts an ACK. A node that has received both the requesting control message, and later the ACK message, will only consider the information in the ACK message. The frame size in OSTR could be decreased only if no ACK is received until the appointment time is reached, which infers that the released slot is no longer used in the network and hence it could be released. Specifying that the slot to be released should be the one with the highest number facilitates the problem of frame size decrease in OSTR. However, what if the slot to be released is not the last slot? Would it be wise to change the slot numbers of nodes assigned a number of slots higher than the one to be released; i.e. suppose a frame size of 6 time slots, and that slot number 2 is to be released. Is it sensible to reconfigure the slots schedule such that nodes assigned slots 3, 4 and 5 will be assigned slots number 2, 3 and 4 in order to free the last slot in the frame? Obviously, this slot reconfiguration is not costless in terms of number of control messages exchanged, bandwidth consumed and latency. This solution needs to be more investigated. The easiest solution may be to specify a maximum frame size when reached, all slots are released and the frame is constructed from the beginning. Although its simplicity, this solution raises many questions to consider: How would the maximum frame size to reach be configured? What is the impact of releasing all the slots on the current running user flows? In distributed environments, slots management is not an easy task and designing an appropriate time slot release for OSTR still needs more investigations.

Traffic-aware OSTR/S-OSTR: One of the traditional proposals related to MAC protocol design for ad hoc and sensor environment consists of the design of a MAC protocol that assigns a number of slots to each node proportionally to its traffic rate. It is worth noting that the considered approach has small impact on the slots release since it is jointly deployed with a fixed frame size; while the task is much more complicated when the frame size is dynamic. To our knowledge, none of the existing dynamic frame-size based MAC protocol for ad hoc and sensor networks have proposed a multi-slot assignment. It is to mention, that assigning multiple assigned slot in E-ASAP [START_REF] Kanzaki | An Adaptive TDMA Slot Assignment Protocol in Ad Hoc Sensor Networks[END_REF] is a way to tackle the frame synchronization issue. In order to more adapt to node traffic requirements, we are currently working on a traffic-aware version of OSTR/S-OSTR. We have drawn the list of impacts of multiple slots assignment per node on the OSTR protocol design. First, a multi-slot assignment will result on multiple flooding and appointment mechanisms running more frequently which may affect the overall system performance. Also, the OSTR slot assignment algorithm should be adapted. Currently, OSTR specifies that if one free slot is found in the current frame size, the frame size remains the same. This condition is no longer valid when a node requires more than one free slot. It should be modified, instead, to the following: if a node finds exactly the number of required free slots in the current frame, there is no need of increasing the frame size. What is the probability that this condition is fulfilled? Finally, the multi-slot assignment may impact the per-node fairness. How to deal with greedy nodes, in order to ensure per-node fairness in the network? These limitations of traffic-aware OSTR solutions need to be deeply explored.

Spatial reuse flip side in sensor networks: Our work is based on the two-hop interference model; one of the most important assumptions in wireless ad hoc and sensor networks. Recall that the two-hop interference model is that the transmission power of node n decays with the distance, and it is assumed to not interfere with the transmission of a node that is located three-hops away. Based on this assumption, a time slot is reused three hops away. However, real implementations have called into question the reliability of this model [START_REF] Iu -Qiang | An analytical model for link evaluation of wireless sensor networks, Network and Parallel Computing Workshops[END_REF]. The spatial reuse is shown to cause interference; i.e. two three hops away nodes assigned the same slot suffer from mutual interference. One of the proposed solution (e.g. solution adopted by SERENA [START_REF] Minet | SERENA: SchEduling RoutEr Nodes Activity in wireless ad hoc and sensor networks[END_REF]) to this issue is to expand the interference model to three hops; i.e. a slot is unique for a node n, its one hop-neighbors, its two-hops neighbors and its three-hop neighbors. Another interesting solution that can be adapted to the OSTR/S-OSTR protocol is to use variable slot length. The idea behind is that we deduce the appropriate slot length based on the interference level which is proportional to the reuse of the slot. The more a slot is reused the higher the interference level is, and thus the longer should be the length of that slot. Indeed, the longer the slot size is the more a node is able to manipulate interference; i.e. varying the packet length, delaying or advancing its transmission time in the slot, etc. We think that the field of slot assignment based on the interference level has not been fully explored yet, and there is a room for future enhancements to develop more realistic slot assignment techniques.

Channel-aware OSTR/S-OSTR:

In wireless ad hoc and sensor networks the channel is generally supposed invariant, which is not really the case. The channel, indeed, is time varying. Consequently, the channel quality is different from one slot to another. Also for the same slot, the channel quality varies from one frame to another. Under the assumption that the channel does not vary, the current version of OSTR specifies that a node assigned a slot keeps this slot until it finishes its data transmission. A more realistic solution is to consider the channel time variation, and to allow a node to renew its slot reservation at each time frame based on the channel quality perceived in the previous frame. This could be formulized in a Multi Armed bandit (MAB) problem [START_REF] Liu | Distributed Learning in Multi-Armed Bandit with Multiple Players[END_REF]. The MAB aims to improve the spectrum utilization; it is a formulization of the gambler dilemma in casino: a gambler is faced K slot machines and he has to choose which arm to pull at each time step so as to maximize his overall gain at the end of N plays. In the case of slotted environment, OSTR considers a model where the available bandwidth is divided into equal time slots. At each frame iteration, one node needs to decide autonomously via local information, which time slot to use during the next frame. This decision is based on the rewards obtained with the previous choices. The reward is a metric arbitrary defined according to the application requirements (e.g. delay, SINR, and so on). How to set a distributed slot assignment based on the MAB approach is still an open issue. We believe that considering the channel time variation is of high interest to better serve the application requirements. The MAB opens new horizons to investigate and to innovate in this field of research.

Figure 1 :Figure 2 :Figure 5 :Figure 6 :Figure 7 :Figure 8 :Figure 9 :Figure 13 :Figure 14 :Figure 19 :

 1256789131419 Figure 1: Illustration of the hidden terminal problem ....................................................... Figure 2: Illustration of the exposed terminal problem ...................................................... Figure 3: A classification of MAC protocols for multi-hop ad hoc networks ................... Figure 4: RTS/CTS handshake and NAV setting in IEEE 802.11 in DCF mode ............. Figure 5: Frame structure in the IEEE 802.11s MDA ........................................................ Figure 6: Frame structure of CROMA ................................................................................ Figure 7: Frame structure of CATA [11] ............................................................................. Figure 8: Cycle and TDMA frame structure for USAP ..................................................... Figure 9: OSTR frame structure .......................................................................................... Figure 10: OSTR packets format .......................................................................................... Figure 11: OSTR behavior illustration upon a frame size increase .................................. Figure 12: OSTR slot selection algorithm ............................................................................ Figure 13: Illustration of the OSTR slot selection algorithm ............................................. Figure 14: Illustration of the frame synchronization problem .......................................... Figure 15: Frame size evolution in the OSTR protocol based on the appointment mechanism ............................................................................................................................... Figure 16: A simple multi-hop topology: the squares topology ......................................... Figure 17: Frame size evolution for node B in the squares topology ................................ Figure 18: Frame size evolution for node B in the random topology ................................ Figure 19: Slot Reuse example with OSTR in the random topology ................................. Figure 20: Setting Delay (SD) Vs. Current frame size ........................................................ Figure 21: Aggregate throughput in function of the Input load ........................................ Figure 22: Throughput gain with respect to IEEE 802.11 DCF (%) ................................ Figure 23: Fairness Index vs. Input load .............................................................................. Figure 24: Slot assignment procedures in the E-ASAP protocol. ..................................... Figure 25: Channel utilization for OSTR and E-ASAP in function of competing nodes Figure 26: Frame size evolution for both OSTR and E-ASAP according to the number of competing nodes ..................................................................................................................... Figure 27: Global aggregate throughput for OSTR and E-ASAP according to the number of nodes in the network ........................................................................................... Figure 28: Fairness index for OSTR and E-ASAP according to the number of competing nodes ........................................................................................................................................ Figure 29: Network throughput according to the number of flows in the squares topology. .................................................................................................................................. Figure 30: Case of study and the corresponding slot distribution achieved by OSTR and E-ASAP ................................................................................................................................... Figure 31: Network throughput of OSTR and E-ASAP in function of the number of flows in the random topology ................................................................................................ Figure 32: Classification of node activity strategies ............................................................ Figure 33: The active and inactive (sleep) periods in one polling cycle ............................ Figure 34: Frame structure of the S-OSTR MAC protocol ............................................... Figure 35: Example of a wireless multi-hop network ......................................................... Figure 36: Exemplification of the active and sleep period coordination in S-OSTR ....... Figure 37: S-OSTR slot selection algorithm ....................................................................... Figure 38: Handling the frame synchronization issue in S-SOTR .................................... Figure 39: Handling the hidden terminal problem in S-OSTR ......................................... Figure 40: Network lifetime with S-OSTR ..........................................................................

Figure 20 :Figure 21 :Figure 22 :Figure 23 :Figure 24 :Figure 25 :Figure 27 :Figure 28 :Figure 29 :Figure 30 :Figure 31 :Figure 32 :Figure 33 :Figure 34 :Figure 35 :Figure 36 :

 20212223242527282930313233343536 Figure 1: Illustration of the hidden terminal problem ....................................................... Figure 2: Illustration of the exposed terminal problem ...................................................... Figure 3: A classification of MAC protocols for multi-hop ad hoc networks ................... Figure 4: RTS/CTS handshake and NAV setting in IEEE 802.11 in DCF mode ............. Figure 5: Frame structure in the IEEE 802.11s MDA ........................................................ Figure 6: Frame structure of CROMA ................................................................................ Figure 7: Frame structure of CATA [11] ............................................................................. Figure 8: Cycle and TDMA frame structure for USAP ..................................................... Figure 9: OSTR frame structure .......................................................................................... Figure 10: OSTR packets format .......................................................................................... Figure 11: OSTR behavior illustration upon a frame size increase .................................. Figure 12: OSTR slot selection algorithm ............................................................................ Figure 13: Illustration of the OSTR slot selection algorithm ............................................. Figure 14: Illustration of the frame synchronization problem .......................................... Figure 15: Frame size evolution in the OSTR protocol based on the appointment mechanism ............................................................................................................................... Figure 16: A simple multi-hop topology: the squares topology ......................................... Figure 17: Frame size evolution for node B in the squares topology ................................ Figure 18: Frame size evolution for node B in the random topology ................................ Figure 19: Slot Reuse example with OSTR in the random topology ................................. Figure 20: Setting Delay (SD) Vs. Current frame size ........................................................ Figure 21: Aggregate throughput in function of the Input load ........................................ Figure 22: Throughput gain with respect to IEEE 802.11 DCF (%) ................................ Figure 23: Fairness Index vs. Input load .............................................................................. Figure 24: Slot assignment procedures in the E-ASAP protocol. ..................................... Figure 25: Channel utilization for OSTR and E-ASAP in function of competing nodes Figure 26: Frame size evolution for both OSTR and E-ASAP according to the number of competing nodes ..................................................................................................................... Figure 27: Global aggregate throughput for OSTR and E-ASAP according to the number of nodes in the network ........................................................................................... Figure 28: Fairness index for OSTR and E-ASAP according to the number of competing nodes ........................................................................................................................................ Figure 29: Network throughput according to the number of flows in the squares topology. .................................................................................................................................. Figure 30: Case of study and the corresponding slot distribution achieved by OSTR and E-ASAP ................................................................................................................................... Figure 31: Network throughput of OSTR and E-ASAP in function of the number of flows in the random topology ................................................................................................ Figure 32: Classification of node activity strategies ............................................................ Figure 33: The active and inactive (sleep) periods in one polling cycle ............................ Figure 34: Frame structure of the S-OSTR MAC protocol ............................................... Figure 35: Example of a wireless multi-hop network ......................................................... Figure 36: Exemplification of the active and sleep period coordination in S-OSTR ....... Figure 37: S-OSTR slot selection algorithm ....................................................................... Figure 38: Handling the frame synchronization issue in S-SOTR .................................... Figure 39: Handling the hidden terminal problem in S-OSTR ......................................... Figure 40: Network lifetime with S-OSTR ..........................................................................

Figure 41 :Figure 42 :Figure 43 :Figure 44 :Figure 45 :Figure 46 :Figure 47 :Figure 48 :Figure 49 :Figure 50 :Figure 51 :

 4142434445464748495051 Figure 41: Average user data delivered with S-OSTR ....................................................... Figure 42: Slot reuse with S-OSTR protocol. ...................................................................... Figure 43: Impact of the HELLO mechanism on network lifetime with S-OSTR......... Figure 44: Network lifetime comparison between S-OSTR (with and without Hello mechanism) and SERENA ................................................................................................... Figure 45: Network lifetime gain relatively to SERENA (%) .......................................... Figure 46: Amount of user data delivered with S-OSTR and SERENA ......................... Figure 47: Percentage of time spent in TX State for S-OSTR and SERENA ................. Figure 48: Rate of time spent in RX State for S-OSTR and SERENA ........................... Figure 49: Rate of time spent in SLEEP State for S-OSTR and SERENA .................... Figure 50: Energy consumption comparison between S-OSTR and SERENA .............. Figure 51: Average network frame size in function of number of nodes for both S-OSTR and SERENA ........................................................................................................................

  Packet types in OSTR ............................................................................................. Table 2: Comparison between OSTR and E-ASAP main characteristics ........................ Table 3: Examples of power consumption in different states ............................................ Table 4: Parameters used for simulations ............................................................................

Figure 1 :

 1 Figure 1: Illustration of the hidden terminal problem

Figure 2 :

 2 Figure 2: Illustration of the exposed terminal problem

Figure 3 :

 3 Figure 3: A classification of MAC protocols for multi-hop ad hoc networks

Figure 4 :

 4 Figure 4: RTS/CTS handshake and NAV setting in IEEE 802.11 in DCF mode

Figure 5 :

 5 Figure 5: Frame structure in the IEEE 802.11s MDA

Figure 6 :

 6 Figure 6: Frame structure of CROMA

Figure 7 :

 7 Figure 7: Frame structure of CATA [11]

Figure 8 :

 8 Figure 8: Cycle and TDMA frame structure for USAP

  a) Frame StructureOSTR divides time into frames that are, in turn, divided into two sub-frames: Control subframe which length is the same for all OSTR frames and DATA sub-frame composed of L equal time slots. The value L changes according to the number of nodes in the network.

Figure 9 :

 9 Figure 9: OSTR frame structure

  ………….

Figure 10 :

 10 Figure 10: OSTR packets format

Figure 11 :

 11 Figure 11: OSTR behavior illustration upon a frame size increase

Figure 12 :Figure 13 :

 1213 Figure 12: OSTR slot selection algorithm

Figure 14 :

 14 Figure 14: Illustration of the frame synchronization problem

Figure 15 :

 15 Figure 15: Frame size evolution in the OSTR protocol based on the appointment mechanism

Figure 16 :

 16 Figure 16: A simple multi-hop topology: the squares topology

Figure 17 :Figure 18 :Figure 19 :

 171819 Figure 17: Frame size evolution for node B in the squares topology

Figure 20 :

 20 Figure 20: Setting Delay (SD) Vs. Current frame size c) Aggregate Throughput Fig.21shows the aggregate throughput according to input load for the squares and random topologies. We notice that OSTR protocol has higher throughput than 802.11 DCF in saturation cases. 802.11 saturates at a throughput of 500 Kbps and 400 Kbps in the squares and random topologies, respectively; While, OSTR achieves a throughput around 900 Kbps for the squares topology and a throughput of 700 Kbps for the random topology.

Figure 21 :Figure 22 :

 2122 Figure 21: Aggregate throughput in function of the Input load

Figure 23 :

 23 Figure 23: Fairness Index vs. Input load

Figure 24 :

 24 Figure 24: Slot assignment procedures in the E-ASAP protocol.

Fig. 25

 25 Fig.25 depicts the channel utilization evolution according to the number of competing nodes in a fully connected network. Three main features are observed:

Figure 25 :Figure 26 :Figure 27 :

 252627 Figure 25: Channel utilization for OSTR and E-ASAP in function of competing nodes

Figure 28 :

 28 Figure 28: Fairness index for OSTR and E-ASAP according to the number of competing nodes

Figure 29 :

 29 Figure 29: Network throughput according to the number of flows in the squares topology.

Figure 30 :Figure 31 :

 3031 Figure 30: Case of study and the corresponding slot distribution achieved by OSTR and E-ASAP

Figure 32 :

 32 Figure 32: Classification of node activity strategies

Figure 33 :

 33 Figure 33: The active and inactive (sleep) periods in one polling cycle

Figure 34 :

 34 Figure 34: Frame structure of the S-OSTR MAC protocol

  Each node in S-OSTR holds the following information:  The node identifier  Its assigned slot  Its frame size  A list of its one-hop neighbors, including for each of them o The one-hop identifier o The one-hop neighbor time slot o The one-hop neighbor frame size  A list of its two-hop neighbors, including for each of them o The two-hop neighbor identifier, o The two-hop neighbor assigned slot, o The two-hop neighbor frame size.

Figure 35 :Figure 36 :

 3536 Figure 35: Example of a wireless multi-hop network



  The sender identifier  The sender assigned slot number  The sender frame size  A list of the sender's one-hop neighbors including for each of them: o Its identifier o Its assigned slot number o Its frame size

Figure 37 :

 37 Figure 37: S-OSTR slot selection algorithm ii. Time slot selection

Figure 38 :

 38 Figure 38: Handling the frame synchronization issue in S-SOTR

Figure 39 :

 39 Figure 39: Handling the hidden terminal problem in S-OSTR

Figure 40 :Figure 41 :Figure 42 :

 404142 Figure 40: Network lifetime with S-OSTR

Figure 43 :

 43 Figure 43: Impact of the HELLO mechanism on network lifetime with S-OSTR

Figure 44 :Figure 45 :Figure 46 :

 444546 Figure 44: Network lifetime comparison between S-OSTR (with and without Hello mechanism) and SERENA

Fig. 47 and

 47 Fig.[START_REF] Xu | Revealing the problems with 802.11 MAC protocol in multi-hop wireless networks[END_REF] and Fig.48show that with S-OSTR, nodes spend less time in TX and RX states comparing to SERENA for different number of nodes. Consequently, S-OSTR spare more energy comparing to SERENA since it increases the amount of time spent in SLEEP state (The state consuming the least energy). This is highlighted in Fig.49and Fig.50where the amount of simulation time spent in SLEEP state is plotted for both S-OSTR and SERENA. This is an important benefit brought by S-OSTR justified by two features:

Figure 47 :Figure 48 :Figure 49 :Figure 50 :Figure 51 :

 4748495051 Figure 47: Percentage of time spent in TX State for S-OSTR and SERENA

Table 1 : Packet types in OSTR

 1

	Type field value	Packet Type
	000	HELLO
	001	REQ
	010	REPLY
	011	ERR
	100	FC

Table 3 : Examples of power consumption in different states

 3

	State	IEEE 802.15.4
	Transmit	0.1404 (Watt)
	Receive	0.1404 (Watt)
	Idle	-
	Sleep	0.18	)

Table 4 : Parameters used for simulations

 4

		Simulation parameter	Value
	Configuration	Number of nodes	50-100-150
		Bandwidth	2 Mbps
		Transmission range	250 m
		Interference range	500 m
	Energy	Battery capacity	25mAh
		Battery Transmit	153 mA
		Battery Receive	200 mA
		Battery Sleep	0.85 mA
	Traffic	Number of flows	20
		Input load	32 Kbps
		Packet size (MAC level)	512 bytes
	Frame	Number of slots	dynamic
		Slot size	0.005 s

Acknowledgments

Here I am, at the end of four years of work in LOR department at Telecom SudParis for my Phd. There is a mixture of feelings of happiness and emotion, relax and stress also. This moment would have never been achieved without the support of many persons who contributed directly or indirectly.

DATA