basé sur des informations géographiques 126 C.2 Evaluation des Performances . . . . . . . . . . .

To Marianne, Gaël, Mateo and My parents

Abstract

In Wireless Sensor Networks, the routing task is an essential service that forwards the sensor readings to some data collection points in the network on the basis of the multi-hop relaying. The routing task is particularly challenging as it should be realized in an energy efficiency manner with limited amount of information. Geographic routing is a promising approach because of its good scalability and local information use, but when deploying such approach, some problems still remain because of some practical difficulties.

In this thesis, some techniques have been explored to address two issues in geographic routing protocols: i) Cost associated to: the wireless channel impairments due to fading, mobility patterns or high dynamic environment and ii) the management of constrained resources of the nodes. To tackle these issues, two protocols were presented: a beaconless Cooperative Geographic cross-layer protocol for ad hoc and sensor networks (CoopGeo) and a Relay-Aware Cooperative Routing protocol (RACR).

Unlike traditional geographic routing protocols, CoopGeo deals the wireless impairments by means of a cross-layer framework where a beaconless geographic routing approach was used to build the route not only in a local manner, but also on the fly worked with a relay selection mechanism to exploit the broadcast nature of the wireless communications.

The RACR protocol exploits the coverage extension as a result from node cooperation to improve the non-cooperative geographic routing. It is an alternative to scenarios where network resources like energy should be preserved while respecting a Symbol Error Rate constraint (SER). Thus, the proposed routing protocol, enables a node to make a local route decision depending on the geographic location of a relay while this relay is selected with the purpose of providing the maximum coverage extension toward the destination.

The results obtained from extensive evaluations of CoopGeo and RACR contributions, have demonstrated that both solutions are applicable to sensor networks with very variable channel environments or unpredictable changes in the network topology. Therefore, we have proved that our cross-layer vision of the problem provided an integrated solution to problems like inefficient routing paths, congested medium access, inaccurate location information, and lossy links.

R ésum é

Le routage dans les réseaux de capteurs, est un service essentiel qui transmet les lectures des capteurs à certains points de collecte de données dans le réseau sur la base des relais multi-saut. Cette tâche est particulièrement difficile car elle doit être réalisé d'une manière efficace au niveau de consommation de resources et avec une quantité limitée d'informations disponible. La facilité de mise à l'échelle et l'utilisation d'information local pour fonctionner ont permis au routage géographique être considéré comme une approche prometteuse. Cependant, lors de son implementation, certains problèmes subsistent en raison des difficultés pratiques.

Dans ce travail de recherche, two problématiques inhérentes aux protocoles de routages géographique ont été étudiés: i) Le coût associé: aux évanouissements liés aux obstacles et aux multi-trajets suivis par un signal transmis sur un canal radio, aux changements rapides des conditions physiques du canal de transmission and ii) l'administration de resources affectés à chaque noeud appartenant au réseau. Afin de résoudre ce problème, deux protocoles ont été présentés: un protocole de routage géographique avec communications coopératives, beaconless Cooperative Geographic cross-layer protocol for ad hoc and sensor networks (CoopGeo) et un protocole de routage basé sur le principe d'extension de couverture: Relay-Aware Cooperative Routing (RACR).

Contrairement aux protocoles de routage géographique traditionnelles, Coop-Geo est un protocole de routage "beaconless" basé sur une architecture intercouches où le routage non seulement est réalisé localement, mais aussi à la volé. En plus, les problèmes liés à la couche physique sont traités par les communications coopératives qui exploitaient la nature de la diffusion sans fil.

Le protocole RACR exploite la propriété offert par les communications coopératives: l'extension de la couverture radio. Cet propriété permets d'améliorer les performances d'un réseau que à l'origine utilisé un protocole de routage géographique traditionnel. RACR est une alternative aux scenarios où l'objectif principal est celui de diminuer au maximum la consommation des resources du réseau et au même temps assurer que le réseau offre un taux d'erreur par symbole garanti (SER). Ainsi, le protocole RACR, permets à un noeud effectuer des decisions dites locales, par rapport au routage des paquets qui dependent de la localisation géographique d'un noeud relai, tandis que, ce noued relai a la finalité de donner une extension maximale au niveau de couverture radio envers la destination.

Les résultats obtenus à partir des évaluations approfondies de CoopGeo et RACR, ont démontré que les deux solutions sont applicables aux réseaux de capteurs en présence forte mobilité, environnements très variables au niveau radio, ou avec des erreurs aux niveau de l'information de localisation. Par conséquent, nous avons prouvé que notre vision de inter-couche du problème a fourni deux solutions efficaces, en termes de chemins, accès au media, problèmes liés à l'information imprécise de localisation, et des liens perturbés.

Chapter 1

Introduction

Wireless technologies has grown rapidly in the last decades and the advances in hardware components have followed the same trend enabling the massive production of communication devices like laptops, cellular phones, personal digital assistants (PDA), sensors, processors, etc. Since these devices are getting smaller and cheaper, their association with some technologies leads to the development of new kinds of wireless networks or the enhancement of existing ones such as cellular networks (2G, 2.5G, 3G). Other type of wireless networks are the traditional wireless networks that are spanned into infrastructure and infrastructure-less like ad-hoc, sensor and mesh networks. These new network types, support a certain number of applications, including WLAN hotspots, real-time communications, home networking, surveillance systems, industrial control, vehicular networks, sensor networks and many other. Data wireless network (making reference to IEEE 802.11 and derivations) have been the center of research and commercial interest for several years, nowadays, we can find Wi-Fi services almost everywhere.

In spite of the industry and users interest oriented to traditional wireless networks, recently the scientific and industrial community is turning into a different scenario where a spontaneous group of electronic devices try to communicate without any infrastructure: the ad-hoc and sensor networks. They present important challenges in their architecture design that are inherited from their basic characteristics. Ad-hoc and sensor networks are wireless, self-organizing systems formed by nodes in communication range of each other forming a temporal network. In general, ad hoc networks are formed dynamically by static or mobile nodes that are connected via wireless links excluding a centralized administration or a network infrastructure, the nodes can join and quit the network spontaneously, thus a method to organize themselves is needed to support all Chapter 1. Introduction the topology changes providing without interruption the routing paths from the source towards the destination, briefly, the routing philosophy is to cooperate between nodes to forward the data in a multihop manner.

Wireless sensor networks (WSN) belong to the class of ad hoc networks, but they have some extra characteristics that make them a special case, even if sensor networks closely looks like the behavior of ad hoc networks, sharing many challenges as limited energy available to each node and the error-prone channels, they have differences to keep in mind: for example, the small size of nodes in a WSN involve that the nodes have very limited resources such as, processing speed, memory, energy, and transmission power; as the nodes can be small, they can be deployed in very large quantities, presenting higher node densities. We can also add that they are inexpensive, the nodes are unattended after deployment and designed for a prolonged lifetime with no maintenance or troubleshooting, and shorter transmission ranges.

Thus, WSN are rather designed to detect events or natural phenomena, nodes collect the data, process them and transmit to some users. By the nature of those characteristics, the most challenging issues in sensor networks are the efficient use of limited resources and the adaptable to topology changes derived from the condition of the communication channel.

Context and challenges

The present work is substantially oriented to the wireless sensor networks, even if some protocols, algorithms and techniques are also applied to other types of wireless networks. Thus, in order to clearly define the scope of the work we present the basic characteristics and challenges attached to our subject under study.

The wireless Sensor Networks, are composed of a large number of sensor which are small in size and are able to sense, process and communicate with each other where the main finality is to detect events or phenomena, collect and process data and transmit the information to the users. In addition to the characteristics related to the wireless communication, the sensor networks include some other basic characteristics inherited from the way they work:

• Self-organizing capabilities • Short range communication and multihop routing • Dense deployment and cooperative effort of nodes • Frequent changing topology due to fading, mobility and node failures • Limitations in energy, transmit power, memory, and computing power • Data centric communication model

In the WSN applications classes, we mention some of them to accentuate the difference with other kind of wireless networks, such as:

• Infrastructure security • Environment and habitat monitoring • Industrial and agriculture sensing

• Traffic control • Disaster prevention • Medical care
From the above summary, it can be remarked that the data centric communication model influences the design of routing protocol, where all the data generated by the nodes is forwarded to some data collection points commonly known as sinks. With this communication model in mind, it can be said that the design of wireless sensor networks has some important tasks to fulfill such as, control the consumption of limited resources that are affected by the transmissions and reception of data packets, and to limit the wireless channel effects generated by two physical phenomena: 1) From multipath propagation of the electromagnetic waves that generates variations in the received signal strength as function of the node location and frequency. 2) From the influence of the eventual motion of nodes that produce the effect called wireless channel variation, generally called fading. Thus, a rigorous protocol design is imposed with the goal of minimize the resources consumption (ie. energy) and maximize the network lifetime with the constraint of detecting the topology changes so as to maintain the network connectivity and calculate the proper routes from the sensor nodes to the sinks.

In order to effectively tackle these WSNs challenges, the research community has produced a lot of works, focusing on traditional layered approaches, where each layer of the protocol stack (ie. network, Medium Access Control and physical) is unaware of the operation of the other layer, eliminating thus, the benefits of joint optimization across protocol layers which can improve the network performance.

Therefore, the use of a cross-layer design must be mandatory, where the availability of some important information among the stack layers would allow a node to make more effective routing decisions as it will have a wider view of the network behavior, resulting in an improvement in the global network performance.

This dissertation, take the cross-layer approach as reference to enhance the layered approach and propose an architecture designed to analyze the interaction between the network layer to route de packet to the destination, the medium access control (MAC) layer to get access to the wireless channel and the physical layer to adapt the protocol to the wireless conditions of the environment. We show in our contributions, that a cross-layer architecture will optimize the inter-actions between these three layers and achieve a high performance and reliable communication in the network.

Contributions

During this research work, Geographic Routing is considered as a concrete solution to the routing issue where the sensor nodes builds on a local manner the route to the sink node. In this scope, the main goal of this thesis is to fill the gap between the traditional geographic routing protocols and the physical environment where the sensor nodes are located. To reach this goal, the routing problem with lossy links is treated by the use of a Beaconless Geographic Routing approach to build the route not only in a local manner, but also on the fly and cooperative communications approach since it is an attractive scheme that uses the spatial diversity of nodes to exploit the broadcast nature of the wireless channel, allowing to the radios located at each node to jointly transmit information through relaying. Thus, the primary contributions are:

• A cross-layer design framework called CoopGeo (Cooperative Communications for Geographic routing) is proposed. CoopGeo has been extensively evaluated and compared to the traditional beaconless routing protocol via simulations. CoopGeo performs the greedy forwarding mechanism without using beacon messages. Instead, each node broadcasts the message and each receiving node competes to forward it based on its local metric. Once the forward node wins the contention to transmit the message, we eventually apply a cooperative communication with single relay selection mechanism where the source node and relay node will jointly transmit the information in the wireless channel. With CoopGeo, we improve the physical layer performance in terms of reliability, extending also the network lifetime compared to other geographic routing protocols which do not consider the MAC layer issues. We also apply a mechanism to get out from a local minimum problem using a beaconless planarization mechanism.

• The RACR protocol exploits the coverage extension as a result from node cooperation to improve the non-cooperative geographic routing. It is an alternative to scenarios where network resources like energy should be preserved while respecting a Symbol Error Rate constraint (SER). Thus, the proposed routing protocol, enables a node to make a local route decision depending on the geographic location of a relay while this relay is selected with the purpose of providing the maximum coverage extension toward the destination.

The results obtained from the evaluation of CoopGeo and RACR makes us think that both solutions are applicable to sensor networks in presence of high mobility or highly variable channel environments. Thus, we can say that our cross-layer vision of the problem may provide an integrated solution to problems like define efficient routing paths, medium access, localization, or fault tolerance.

In addition to the main contributions, this research work provides the following complementary contributions:

• An extensive state of the art where some important links between the geographic routing protocols (with its derivation: beaconless geographic routing and virtual coordinates) and the cooperative communications were established.

• Two different beaconless geographic contributions were integrated into one framework. The traditional beaconless greedy forwarding from one contribution and the beaconless recovery forwarding from other contribution were taken and then a new framework was built. Over this new framework, the first contribution was built on.

Thesis Outline

This thesis is organized as follows.

• Chapter 2, first, reviews the state of the art on routing in wireless sensor networks, giving special interest to geographic routing and beaconless geographic routing. Then, it presents the cooperative communications fundamentals, addressing their advantages, their challenges, and their drawbacks. It lastly, gives an overview of the related works covering relay selection on cooperative communications for sensor networks.

• Chapters 3 covers the theory of the models discussed and used in the present work, such graph models, radio propagation models, mobility models, etcetera. This information will help us to allow the appropriate understanding of the contributions. It also presents the tools used to analyze the performances of the routing protocols.

• Chapter 4 presents the details about the first contribution: CoopGeo. With a cooperative strategy, it builds a reliable Beaconless Geographic Routing protocol for Wireless Sensor Networks using a contention-based relay selection mechanism. it also introduces the model and the policies to select the relay nodes according to a predefined metric.

• In Chapter 5, the second contribution, RACR, is described. It is a routing protocol that takes advantage of coverage extension offered by cooperative communications to achieve a scalable and efficient sensor network performance.

• Chapter 6 summarizes our contributions, concludes the thesis and discusses the perspectives and further improvement to the contributions.

Chapter 2

State of the art

In the first part of this chapter, it is provided an introduction to routing in sensor networks and it also supplies an overview to the prior relevant works to the subject developed in other parts of the thesis. It starts by describing generally the existing approaches to the routing problem. Then it covers the Geographic Routing (GR), presenting the way how it works, the advantages, the challenges and the limitations. Finally it presents a Beaconless Geographic Routing (BLGR) as a derivation of the traditional GR, giving some specific references to other related works.

In the second part, the cooperative communications as a mechanism to help the wireless communications are introduced. It covers a brief overview and introduction to this communication scheme and presents why it represents a lot of interest in the design of a communication protocol. Then it covers the background of several basic areas: communications theory, graph models, and radio propagation models in order to provide the basic ideas used in this thesis and allow thus its appropriately understanding.

Routing Protocols for Wireless Sensor Networks

The basic tasks of sensors comprised in a WSN are sensing or gathering the information from the analyzed phenomenon, processing, and transmitting the sensed data to a destination point commonly called sink. To deliver the data to the sink, sensor nodes use the multihop principle whenever infrastructure is unavailable or when the direct transmission from the source to the destination is impossible, thus the node sensing the data uses intermediate nodes to relay its packets across the network until it reaches the destination. Therefore, the source and the intermediate nodes have to decide which neighbor the packet will be sent to, using a routing protocol as a tool to make this decision.

It can be said that routing is still a challenging issue in mobile ad hoc networks and particularly in sensor networks [ Akyildiz 02], due to their limited resources, the nodes mobility and the physical environmental conditions. In these kinds of networks, the most traditional routing protocols are classified into two categories: the topology-based and position-based routing protocols.

Topology-based routing

Topology-based routing protocols use the information about the neighbors or links existing in the network to perform packet forwarding. They can be further divided into proactive, reactive, and hybrid approaches. Proactive algorithms employ classical routing strategies derived from wired routing protocols such as distance vector or link state protocols. To illustrate the former strategy, we can cite from [Perkins 94] the Destination Sequenced Distance Vector protocol(DSDV) and for the latter strategy, from [RFC 03] the Optimized Link-State Routing protocol(OLSR) or from [Ogier 04] the Topology-Based Reverse Path Forwarding (TBRPF). The protocols belonging to this approach try to keep a consistent and up to date routing information about the paths available in the network by exchanging control messages at fixed time periods. The main drawback of this approach is that the maintenance of routing tables may occupy a significant part of the available bandwidth and nodes resources, and this is even worse when the topology of the network changes frequently.

In contrast to this problem, reactive protocols establish a route to a given destination only when a node requests it by initiating a route discovery process and once the route is established, the data communication starts, thereby they reduce the resource consumption of the network. This tend to be efficient in small networks, however, this scheme does not scale well in large networks due to the significant overhead generated to find the paths between the source and destination nodes and the delay to transmit the data packets. Even if route maintenance is restricted to the routes in use, the process can generate overhead in the network when the network topology changes very frequently or the packet can be lost in the transmission process if the new route is not known. Examples of this kind of protocols are Dynamic Source Routing (DSR) [Johnson 04] and Ad-hoc On-Demand Distance Vector (AODV) [ Perkins 03].

Finally, hybrid approach applies principles of both routing schemes, proactive for the local neighborhood and reactive for the distant nodes or they may modify their behavior given some circumstances, sometimes using proactive rules and other times using the reactive rules. These kind of protocols try to mix combine the power of both schemes, some well-known examples are Zone Routing Protocol (ZPR) [Haas 97], Location-Aided Routing (LAR) [Ko 00] and Distance Routing Effect Algorithm for Mobility (DREAM) [ Basagni 98].

Position-based routing (Geographic Routing)

A different vision from topology-based protocols, is the one presented by the position-based protocols that from now and on, we will call geographic-based routing protocols. They use the node location to route the information, taking advantage of the presence of low power GPS receivers at sensor nodes or the use of other techniques to build a coordinate system with virtual or absolute coordinates. Geographic routing in essence works at the network layer providing the way how a packet will be delivered to the destination or sink node based only on local information, for instance the node location. Hence, geographic routing [Stojmenovic 02] is an attractive approach to route in ad hoc networks and wireless sensor networks, because it is efficient, scalable, and it does not need to know the topology of the network.

Unlike topology-based protocols, geographic-based protocols require very few control traffic to work and they do not need to create or maintain the whole route from source to destination and thus they eliminate the overhead of frequent topology updates.

Many Geographic-based routing protocols have been proposed in the literature. In the following, the geographic basic principles are described. Then, their benefits and forwarding strategies are stated. Next, some geographic routing protocols are presented, and finally, it discusses their drawbacks.

Geographic Routing Protocols

In this section, we present some principles used in the development of geographic routing protocols for wireless sensor networks. Some of them, have been refined and improved, but usually, some basic ideas remain the same such as:

• Each node knows its geographic location using some localization mechanism or hardware composant. Location awareness is essential to this routing approach, so it is expected that wireless nodes will be equipped with a GPS or will execute some localization techniques. Several techniques exist for location sensing based on proximity or triangulation using radio signals, acoustic signals, or infrared. • Each node knows its direct neighbors locations (1-hop neighbors). This information could be obtained by a periodic information exchange containing the position in form of beacons, hellos or broadcast messages. It is impor-tant to note that this assumption could be relaxed and give birth to another category of geographic routing. • Each node trying to send data packets already knows the destination location.

Moreover, several benefits associated to geographic routing protocols are stated:

• Low overhead, since the establishment and maintenance of routes are not required in protocols that use location information to route data. • Localized algorithm, since a node only interacts with other nodes in a restricted vicinity to determine which neighbor will forward the message. • Scalability, since these protocols are localized, they neither need to know global information nor recompute the routing tables to follow the topology changes.

• High performance since they can adapt rapidly to the network dynamic, respecting resource constraints of the nodes.

In geographic routing, the source and intermediate nodes forward the packets with respect to a predefined routing metric, in general: the geographic progress to the destination. This kind of protocols have a "greedy" behavior, selecting the neighbor that minimizes the distance to the destination. However this greedy mechanism could fail when it gets into a local minimum: a packet may be stuck at a node that does not have a neighbor closer to the the destination than itself to forward the packet. Traditional geographic routing protocols also need to send beacons messages periodically to get their direct neighbors position and execute the greedy mechanism, however, they may present problems with the mobility of nodes and even if they can adapt the beacon frequency to the degree of the network mobility in order to keep the nodes position update, they can still suffer the inaccurate position problem. Therefore in the presence of high mobility, the inaccurate position information can lead to a significant decrease in the packet delivery rate and fast energy consumption in wireless nodes due to the media access control (MAC) layer retransmissions.

Forwarding Strategies "Greedy Forwarding"

The basic principle of geographic routing is that, when a node wants to send a packet, it includes the position of the recipient in the packet. Thus, when an intermediate node receives a packet, it forwards the packet to a neighbor lying at a location in direction of the recipient. Ideally, this process can be repeated until the recipient has been reached (see Fig. 2.1). The forwarding strategy used, is an important part of the geographic protocol in use, since it allows to choose among the neighborhood the node that will forward the packet. Thus, we proceed to present the most common forwarding strategies used by some geographic protocols. Fig. 2.2 depicts a scenario where S transmit a packet towards the destination node D, the circle with radius r indicates the maximum transmission range of S. The geographic strategy proposed by Takagi and Kleinrock [Takagi 84] introduces the notion of "progress" where intuitively the node forwards the packet to the node that is closest to D. In the scenario the chosen node is A where the progress is calculated by the distance between the current node S and the projection A ′ of the neighbor A onto the line formed by S and D. This strategy is known as Most Forward within the Radius (MFR) and tries to minimize the number of hops a packet has to traverse in order to reach D. MFR is a good strategy in scenarios where the sender of a packet cannot adapt the signal strength of the transmission to the distance between sender and receiver. Fin [Finn 87] proposed the strategy that nowadays is known as "GREEDY" which minimizes the distance d to the destination D (e.g. node B in Fig. 2.2). This is the most used scheme in geographic protocols found in literature. In nearest with forward progress (NFP), the packet is transmitted to the nearest neighbor of the sender which is closer to the destination. In Fig. 2.2 this would be node A. If all nodes employ NFP, the probability of packet collisions is reduced significantly. Therefore, the average progress of the packet, calculated as p∆f (a, b) where p is the likelihood of a successful transmission without a collision and f (a, b) is the progress of the packet when successfully forwarded from a to b, is higher for NFP than for MFR.

Kranakis [Singh 99] proposed the compass routing, which considers the angle between the next hop, current, and destination nodes. This means that, the next forwarding node minimizes the deviation from the line connecting the current and the destination node (e.g. node D in Fig. 2.2). From this angle-based scheme (see Fig. 2.3), we can also mention Nearest neighbor routing (NN), where given a parameter angle α, node S finds the nearest node V as forwarding node among all Nelson 84] proposed a random progress method where the sender randomly choose one of the nodes with progress and forwards the packet to that node. This strategy relax the accuracy of information needed about the position of the neighbors.

So far, the operation of the geographic routing protocols have been described in general terms. In the next subsections, several protocols based on the above principles are described. For the sake of simplicity and taking into consideration their specific characteristics, they can be classified in Beacon-based geographic routing (the traditional protocol, commonly called geographic routing) and Beaconless geographic routing. The following subsections describe them.

Some Traditional Geographic routing protocols

Even if this work is orientated to the beaconless geographic routing, the basis of its way of work comes from the traditional geographic routing protocols, thus, it is important to describe some works that marked some trends and directions in the field.

Greedy Face Greedy (GFG)

GFG [Bose 01] is the first protocol that merges and enhances two basic principles presented in section 2.2.1. They use the greedy routing proposed by Fin to send the packet to forward to the node closer to the destination, minimizing the distance to arrive to the target node (remember that they only consider the greedy forwarding since a backward node may lead to a loop in the packet delivery), and the face routing from Bose et al to bypass the holes in the network topology and avoid the loops as well (see Fig. 2.4). This is the first geographic algorithm that guarantees the packet delivery to its destination. The main principle of GFG, is that when a node finds a local minimum, it routes the packet in the interior faces intersected by the straight line connecting the source node and the destination, the way how the packet traverses the faces is by applying the right or left hand rule. Thus, when a packet is forwarded along an edge in clockwise or counterclockwise direction from the edge where it arrives. In the case of, a packet arrives at an edge that intersects the imaginary line between the source and the destination, the next face intersected by this line is handled in the same way. In brief, GFG starts working in greedy mode and switch to recovery mode applying the face routing when a hole in the topology is found.

Greedy Perimeter Stateless Routing (GPSR)

GPSR [Karp 00] is an algorithm that appeared after GFG, but it actually has a very similar operation since the same algorithms are applied (see Fig. 2.4). The contributions of GPSR with respect to GFG are: the integration of greedy forwarding and face routing into the IEEE 802.11 using thus, a more realistic medium access layer instead of the ideal one used by GFG, and the discussion about the Relative Neighborhood Graph (RNG) as an option to the Gabriel Graph (GG). Afterwards, the Embedded Networks Laboratory team at the University of Southern California (USC) implemented GPSR to run TinyOS. However, a small difference between GPSR and GFG is that GFG may stay in the same face after an intersection in the face routing is encountered while GPSR always changes to the next face.

Other Geographic protocols derived from greedy + face union

Kunh at al, proposed three contributions that are closely related to the greedy forwarding and face routing union. First, in the Adaptive Face Routing AFR [ Kuhn 02], Kunh basically enhances the face routing phase by the employment of an ellipse whose size is iteratively incremented as needed and is bounded by the complete optimal path from the source to the destination when applying the recovery mode. In contrast, the original face routing needs to explore the complete boundary of the faces. In AFR, if the exploration hits the ellipse, it has to "turn back" and continue its exploration of the current face in the opposite direction until hitting the ellipse for the second time, which completes this face's exploration. Secondly, Kunh proposed Greedy Other Adaptive Face Routing (GOAFR) and Greedy Other Adaptive Face Routing Plus (GOAFR+) in [Kuhn 03b, Kuhn 03a], where they use the greedy and a modified version of their AFR contribution. In GOAFR they use the percolation theory and describe the worst case optimal and average case efficient. GOAFR+ is an enhancement to GOAFR for the average case and they also analyzed some cost metrics. Thus, we can say that GOAFR+ use two mechanism: early fall back and boundary circle. The former, is used to return from face routing mode to greedy forwarding mode as soon as possible. The latter is used to restrict a searching area in similar way as AFR achieving optimal results in the worst casa. Briefly, the main the difference between GOAFR and GOAFR+ is that GOAFR does not include the falling back mechanism presented by its enhancement version.

Greedy Distributed Spanning Tree Routing (GDSTR)

Leon et al in [ Leong 06], proposed a different approach than traditional geographic routing. They describe an algorithm that does not require the planarization of the network in recovery mode by routing on a spanning tree until it reaches a node where the greedy mode can be applied again. GDSTR uses the convex hulls to aggregate the locations covered by the spanning tree and decide efficiently the direction of the tree where the node must forward to make a progress to the destination. Briefly, GDSRT build a spanning tree and every node maintains a convex hull, when a node can not forward any more in greedy mode, it checks if the destination is found in its convex hull. If this is the case, it forwards the packet to the proper child node, otherwise, it sends the packet to its parent that maintains a bigger convex hull. Thus, when a node finds another node nearer to the destination than the node where the recovery mode started, it changes to the greedy mode.

Local Tree based Greedy Routing (LTGR)

In [Liu 07b], Liu et al follow the approach proposed in GDSTR in order to avoid the face routing that uses a planarization method to route the packets. In LTGR, when a node gets into a local minima, it uses a local tree instead of face routing without making face routing assumptions such that, the uniform radio ranges of nodes and the bi-directional links existence that hard to be found in real world networks. When a node sends a packet to a destination and this packet is blocked at a local minima, a local tree that can expand to a spanning tree covering all nodes in the network is created to find the next hop toward the destination. The challenges found by the authors is how to embed local tree information in the packet that is used by the data packet when traversing the local tree. They proposed two solutions: 1) When a node receives a packet marked in recovery mode, it divides the space in four quadrants. Then it adds one neighbor by quadrant (except the quadrant that contains the node where the packet comes from) to the local tree. Thus, a node can have only three children in the tree, controlling the number of nodes participating in the routing problem. If the next hop node is not found in the local tree, it can be extended with another "wave" of children nodes. 2) They propose a compression technique to embed the local tree information stored at the data packet.

Beaconless geographic routing (BLGR)

Traditional geographic protocols need periodic exchanges of hello messages in order to aware neighboring nodes about its current position information. This is a proactive mechanism that leads to energy consumption in nodes, and this consumption could be increased if the hello interval is reduced to maintain the information updated due to a high mobility of the nodes.

Accordingly, Beaconless Geographic Routing (BLGR) is an enhancement to the traditional geographic routing approach that overcomes the problems pre-sented by the latter in high mobility scenarios. This approach is based in a principle where the node detaining the packet to transmit is not aware of the existing neighbors it has. So, it neither needs to have a previous knowledge of the network topology to forward the data packet avoiding therefore the exchange of control messages nor information about the available routes to the destination. Beaconless routing uses a scheme where the decision to forward is delegated to the neighbor nodes using only local information. In such scheme, all the candidates to forward the message participate in a contention process where all neighbors start a timer with respect to the progress to the destination and thus, the node whose timer expires the first will forward the packet to the destination.

We can say that the basics of the routing scheme can be described as follows:

• A node s that wants to transmit a message to d, choose a forwarding area where it tries to find a potential forwarding node. • s broadcast the packet or the control message to start the packet transmission. • Nodes in the forwarding area, hear the packet and start up a timer in order to become the forwarding node if the destination is not reached. In general, nodes that are not located in the forwarding area discard the packet (this step may change in accordance to the type of beaconless algorithm used). • The node whose timer expires the first will be the forwarding node and the process start again the step 1 until the destination is reached.

The difference between the algorithms belonging to this approach are: how they choose the forwarding area, how they deal with empty areas, how they avoid the collision between the nodes that content for the transmission, and the metric used in nodes located at the forwarding area that defines the best suited node to transmit the packet.

As traditional geographic protocols, the greedy forwarding and the recovery modes are the main modules of beaconless routing. In the former, the decision is generally based on the progress to destination (minimizing the hop count). For the latter module that is used to avoid the local minimum problem, two different approaches are used: heuristic, where the procedure does not theoretically guarantee the packet delivery and neighbor planarization, where a face routing algorithm is used and the message delivery is theoretically guaranteed.

A common behavior in BLGR schemes is that, as they use the progress to destination as the principal metric when the nodes take the forwarding decision, obtaining this information at the network layer or at the Medium Access Control layer but they are not attentive to the physical conditions of the environment.

The first works in Beaconless Geographic Routing were realized by Heissenbüttel and et al in [Heissenbüttel 03], who proposed the Beaconless Routing (BLR), Füssel et al. in [Fubler 03] proposed Contention-Based Forwarding (CBF) and in [ Blum 03] Blum et al. presented the Implicit Geographic Routing (IGF). All these protocols are very similar, they all apply a mechanism to select the next hop node in a distributed manner without knowledge of its neighborhood which is based on contention timers. The difference are, for CBF and IGF, they focus on the integration of the routing protocol to the MAC layer, in this case IEEE 802.11 was used. In BLR, the authors analyzed the theoretic properties inherent to this kind of protocols. They also propose, several enhancements to the original design such as: the convergence from broadcast to unicast packets, the aggregation of paths and two recovery modes in case of local minimum problem.

Beaconless Routing (BLR)

In BLR [Heissenbüttel 03], the authors defined a forwarding area restricted to a 60˚sector from the node detaining the packet to the destination with a radius that just equals the transmission range r. They establish the 60˚angle as a precondition since they consider that each node within this sector should be able to detect the transmission or any other node within this sector and therefore the algorithm would work properly. In Fig. 2.5 we depict a scenario where only nodes within the sector take part in the competition process to forward the packet (e.g. nodes A, B and C). The rest of the nodes do not participate in the process and just discard the packet (e.g. nodes D, E and F ) To forward the packets, BLR define a Dynamic Forwarding Delay (DFD) at each node that is related to its progress to destination, so to calculate the DFD value each node within the previously defined sector determines its progress p and infer ContentionDelay in the interval [0, .., M axDelay] which indicates the delay introduced before trying to forward the packet.

Additionally, the authors proposed some enhancements to improve the algorithm performance. They converge the transmission once the node detaining the packet already knows the next hop position through a previous transmission from broadcasting to unicasting the packet during a predefined threshold. They also proposed two recovery strategies for the local minimum problem (no node is located at the forwarding sector), actually they call them backup mode. First, authors detail the request-response approach where the node in the local minimum send a request packet and all neighbors answer indicating their location, then the node open the forwarding area to an approximately 180˚sector and wait for a forwarding candidate, if there is no node with forward progress, the actual node adopts build a planar subgraph and applies the right-hand rule (see description in GFG, GPSR) via a unicast packet. Second, the clockwise-relaying approach where the node in the backup mode start again a contention timer according to the angel α between itself, the previous node and the destination. Thus any node with forward progress transmit the packet before any other node with backward progress in a clockwise order.

Contention-Based Forwarding (CBF)

Fûssler et al in [Fubler 03], deal with the traditional geographic protocols with their Contention-Based Forwarding scheme. In addition to the distributed next hop selection using biased timers like BLR and IGF, they propose three suppression strategies to handle the packet duplication or collisions between potential forwarding nodes. CBF consists of two process: 1) the selection of the next hop by means of contention and 2) the suppression used to reduce the chance of accidentally selecting more than one node as the next hop.

CBF starts when a node s wants to transmit a packet to d, the node broadcast its packet to its direct neighborhood, then the selection process begins by setting out at each node timers with random values using uniform or exponential distributions, then the candidate whose timer expires the first forwards the packet. Consequently, they adopt the progress to destination to derive the timer values instead of the random generation. Other candidate nodes cancel their timers when they listen to the winning node transmission toward d. During this process, CBF defines a minimum time interval needed to suppress other candidates to forward δ and state that a packet duplication occurs when the best candidate node has a progress P 1 and there is at least another node with progress P such that t(P )t(P 1 ) < δ.

The suppression process tries to tackle the packet duplication and control the overhead (see scenario depicted in Fig. 2.6), Fûssler et al propose three suppression strategies as follows:

• Basic scheme. This is the simplest and less performance than the other two schemes. Here, if a node gain the forwarding contention, it forwards the packet. When the direct neighborhood receives the message and the nodes belonging to this neighborhood that still have a timer running for the packet, the timer is immediately canceled. • Area-based scheme. They propose to artificially reduce the forwarding area.

The key idea is to define the suppression area in such a way that all nodes within that area are in transmission range of each other, avoiding thus extra packet duplications or collisions as they may appear in the basic suppression scheme. In this direction, the author propose three areas: 1) the basic area defined before, 2) a circle in direction of the destination with the diameter equivalent to the transmission range of the current node. 3) the reuleaux triangle is a shape that better covers the forwarding area and thus offers more forwarding candidate nodes. ward) instead of immediately broadcasting the packet. The RTF contains the forwarding nodes location and the final destinations location. Each neighbor verify if it is located in the forward progress area, if this is the case, it sets a reply timer according to the progress toward d. Thus, when a timer expiry occurs, a control-packet called CTF (Clear To Forward) is transmitted to the forwarding node and the nodes that hear the CTF suppress their timers and the current node send finally the packet in unicast to the node which sent the CTF message. Blum et al in [ Blum 03], proposed the implicit geographic forwarding where they integrate the routing and MAC layer into a common protocol, taking as basis the IEEE 802.11 DCF contention scheme. The principle is the same as BLR and CBF; IGF tries to non-deterministically route packets using a competition process between candidate nodes. Compared to the two beaconless protocols explained before, here IGF incorporate an energy remaining (ER) metric into the route selection process. The procedure used to send a packet is the same as the active selection described in CBF (using RTS/CTF control messages, but here they are called ORTS/CTS -Open RTS-). The IGF forwarding area (see Fig. 2.5) is the same as the one of BLR (a 60˚cone towards the destination). In contrast to CBF, IGF provides a recovery process to bypass the local minimum problem implementing a forwarding area shift where the network layer (previous MAC layer notification) retransmit a message to request a shift in the forwarding area to look for a next hop node and then applies the backpressure from [speed ref]. In Fig. 2.7 we can see the sequence of shifts. GeRaF [ Zorzi 03], is another type of BLGR that takes the positive advancement area of the node coverage area into N sub-regions (see Fig. 2.8). Each of them delimited by the coverage area of the transmitting node and one or two circle areas centered at the sink. Upon forwarding a packet, the sender broadcasts an RTS packet to all nodes in the sub-region closest to the destination and expects a CTS reply. If there is no reply, the sender will broadcast another RTS packet to the sub-region that is the second closest to the destination. This process continues until a CTS is received or all sub-regions have been searched in which case the forwarding fails. When nodes in the same sub-region answer to the RTS packet, a collision may be produced, in this case, the authors adopted the use of busy tones as collision avoidance scheme. The collision avoidance scheme, the nodes should be equipped with two radios to separate one channel for the data traffic and the other is used as a wakeup signaling.

New Beaconless Geographic Routing Protocols

In recent times, other extensions to BLGR were proposed, two of them that contribute with new ideas to the routing issue were presented. Beaconless On demand Strategy (BOSS) [ Sanchez 07], extend the positive advancement subdivisions as GeRaf propose to the negative advancement area (see Fig. 2.9) and thus, the shift from "greedy" mode to recovery mode is automatically. In addition, they studied the impact of the packet size on the packet reception rate by means of some practical experimentations. Kalosha et al [ Kalosha 08], proposed two algorithms used during the beaconless recovery process. The Beaconlees Forwarder planarization (BFP) and the angular relaying, these contributions planarize the neighborhood to allow the face routing following the beaconless principle to minimize the overhead of control messages.

Beaconless On Demand Strategy for Geographic Routing in

Wireless Sensor Networks (BOSS)

As stated in the above section, BOSS [Sanchez 07] considered during its design the physical layer and defined a delay function in order to mitigate the collisions and duplicate packets from the next hop forwarding selection. Based on some experimentations, they found as others before that the packet size has a direct relationship with the probability of error. As big packets have less probability of being received than small packets, the authors decided to avoid the use of RTS/CTS control packets to start the communication between the forwarding node i toward i + 1 node since control packets may induce to select a node that in fact, it may not receive the bigger data packet. To transmit a packet, BOSS uses a three way handshake. The node detaining the packet to send broadcasts it and waits for the first response from the neighborhood and then, they confirm the selection with a final control packet. To reduce the overhead, they use a passive acknowledgement scheme to confirm the successful reception of the transmitted packet. In case of nodes absence in the positive forwarding area, transparently the nodes located a the negative forwarding area form a planar subgraph where the face routing algorithm is applied to avoid the holes in the network. Kalosha et al [ Kalosha 08], based on three select and protest principle, they proposed two methods in the recovery mode to build a planar subgraph that allows the direct application of the face routing algorithm and thus guarantee the delivery of the packet to the destination. In the first contribution called Beaconless Forwarder Planarization (BFP), they build an approximation of a planar subgraph, then they sort out the false nodes from that approximation to get a final planar subgraph used in the beaconless recovery mode. In the second contribution called, the angular relaying, they try to directly find the next hop node of the right-hand face traversal algorithm where if the selected neighbor does not belong to the planar subgraph, in this case the Gabriel Graph, the mechanism look for a consecutive neighbor in the right-hand direction. Given this facts, we can say that the authors proposed two mechanisms to route in recovery mode building planar or partially planar subgraphs minimizing the control messages exchange between the neighborhood and the node detaining the packet to forward.

Virtual Coordinates

In previous sections, we have presented the geographic routing as one of the most efficient and scalable routing solutions since it is stateless and localized: it does not need to recognize the topology of the network. To achieve this, each node in the network must know its own coordinates and the destination coordinates. Such approach presents some drawbacks like the localization error that generates routing problems that could increase the path length or minimize the packet delivery rate. Many sensor nodes do not have a Global Positioning System (GPS) embedded and providing such device to each node could be expensive in terms of energetic resources and money, and finally the network can not be deployed for indoor applications. Another kind of study was then derived taking the greedy forwarding principle of geographic routing protocols, but the greedy routing is executed by encoding the connectivity without geographical information, trying to model the network as a geometric space and characterize the position of a node by a position in this space. Thus, the main idea is to build a virtual coordinates scheme that replaces the real physical coordinates. Hence, each node with these coordinates uses a predefined function to calculate the distance between itself and its neighbors. Based on these distances, the greedy forwarding is applied similarly to the traditional geographic routing protocols.

In this section, we present some important virtual coordinates protocols. Since commonly the virtual coordinates system construction is based on few nodes of the network (often called anchors or landmarks) that initialize the process. We present a very first classification based on their behavior. Hence, the protocols may belong to one of two categories: the first when the landmarks are locationaware and the second where the landmarks do not know its coordinates (they are location-unaware).

Location-aware landmarks

The protocols in this category use some landmark nodes who know their physical coordinates, and from these landmarks, the rest of the nodes infer their coordinates. To do this, the ordinary nodes execute some physical measurements and/or some localization protocols such as triangulation and multi-lateration methods which are helped by other techniques to determining distances between the nodes, including Received Signal Strength (RSS), Time of Arrival (ToA), Angle of Arrival (AoA). This kind of protocols are not considered in the present work since they are designed just to locate a node in a place and then, another protocol is applied to route the information. Refer to [ Niculescu 04], [ Langendoen 05] and [Savarese 01] for more information.

Location-unaware landmarks

This kind of protocols do not try to approximate their physical coordinates, since the landmark nodes do not know their physical coordinates. They rather relax this constraint and build a virtual system that encodes some network connectivity information instead of physical proximity. Hence, once the system is built, the greedy forwarding is used over the virtual coordinates to route the packets.

In this category NoGeo [ Rao 03] based on the graph embedding concepts propose to designate two landmarks, then perimeter nodes are detected and projected in a virtual circle to compute their own coordinates, and finally the non landmark nodes calculate their virtual coordinates executing an iterative rubber band algorithm based on a centroid transformation. NoGeo is relatively complex as it requires a large amount of messages exchanges and iterations to converge. In addition to these drawbacks, they assumed that the network is static once the perimeter nodes are detected which trends to problems when new nodes appear.

Graph EMbedding for sensor networks (GEM) [ Newsome 04] proposes a virtual coordinate system with polar coordinates (given in radius and angle from a center). They first create the virtual coordinates system by constructing a spanning tree, then the radius of each node is defined (number of hops from a node and the root), next each node is assigned an angle range (to identify the node within a level) which will be respectively used to assign an angle range to its subtree. Afterward, each subtree calculates its center of mass and propagates it to the root of the original spanning tree, resulting in a labeled graph tree with virtual coordinates. At this moment, the routing process can be effectuated either by routing up in the tree until a node has been found that is a common parent of both source and destination or using a more efficient scheme called Virtual Polar Coordinate Routing (VPCR). Instead of always routing up the tree, VPCR checks to see if there is a neighboring node with similar radius that is angularly closer to the destination than the current node. If so, that node is given preference; if not, the packet is routed up the tree. Once an ancestor of the destination is reached, the packet is routed downward just like in the simple routing scheme.

Later on, several research works appears, such as Logical Coordinate Space Routing (LCR) [Cao 04], Beacon Vector Routing (BVR) [Fonseca 05], Virtual Coordinate Assignment Protocol VCap [Caruso 05], and HopID [Zhao 05b]. They all have very similar behaviors: 1) Select few landmark nodes and span a tree from them to every node in the network; 2) Each node constructs its virtual coordinates using a vector (see Fig. 2.10) that represent the hop distance to each landmark 3) A distance metric is defined so as to apply it when forwarding the packets. In summary we can say that, first each node derive its virtual coordinates, and then applies the forwarding rule. The small difference between these works can be found in the number of landmark nodes used, LCR defines four landmarks, BVR between ten ant eighty, and Vcap tree. Other dissimilarity is the technique used to avoid the loops in the routing path. BVR is the only protocol implemented in real sensor nodes and also while the other mentioned protocol defined the Euclidean distance as function as forwarding criteria, BVR applies the semi-Manhattan distance. Liu et al, stated later that neither the Manhattan nor semi-Manhattan distance are necessary better measures than Euclidean distance.

Figure 2.10: The node P builds its virtual coordinates vector using the three landmark nodes (yellow)

In [Liu 08] Liu et al described an anomaly of the previous protocols since the integral nature of the coordinate vector (virtual coordinates are based on integer number of hops to the anchors) produces a quantization noise in the estimate of connectivity and node location. They improved the performance by proposing an Aligned Virtual Coordinate System (AVCS). To achieve this, they align the nodes by computing the coordinates of a given node as a function of its own coordinates and the coordinates of the neighboring nodes. This new process allows the discrimination between nodes located at the same level of distance between the conflicting nodes and the landmarks.

Leon in [ Leong 07] described the Greedy Embedding Spring Coordinates (GSpring) protocol inspired from the physical spring system with repulsion forces model. The model used points to an incremental adjusting of the initial virtual coordinates. In GSpring, each link is modeled like a spring by assigning forces among the set of edges between the nodes using the Hooke's law. The forces are applied to the nodes, pulling them closer together or pushing them further apart. This is repeated iteratively until the system comes to an equilibrium state. At the beginning, GSpring detects some perimeter nodes that will act like landmarks and assign them some coordinates, afterward, the rest of the nodes (ordinary nodes) compute their initial virtual coordinates. Then, the ordinary nodes update its coordinates based on the virtual coordinates of its direct neighbors using the spring model.

Landmark-free Virtual Coordinates

Recently, in [Watteyne 09], they proposed the Centroid virtual coordinates, a novel protocol that we will refer as CVC. This new routing paradigm forces us to consider to add a new category in the virtual coordinates protocols classification: the landmark-free virtual coordinates. Watteyne et al, took the centroid transformation used by Rao et al but they eliminate the initialization phase (no landmark nodes needed). Instead, the nodes choose a pair of floating positive numbers as coordinates except the sink node that has a fixed virtual coordinate, known by all the nodes. The virtual coordinates are refined (by the centroid transformation) only when the node has some data to transmit, thus avoiding a lot of traffic overhead. In summary the protocol works as follows. 1) The transmitting node retrieves its neighbors virtual coordinates by means of an adapted neighbor discovery procedure working at the MAC layer. 2) The current node updates its virtual coordinates with the value obtained from the centroid transformation, and 3) The current node verifies that there is no neighbor virtually close to him than a threshold distance, if that is the case a function is used to update the location of that neighbor. To apply the complete routing process from a source to a destination, they coupled the virtual coordinates protocol with the 3rules [ Watteyne 07] routing protocol and the 1-hopMAC [Watteyne 06] MAC protocol.

Cooperative Communications

Our intuition for solving some fundamental issues of wireless communications like fading and interferences neglected in common geographic routing protocols is to focus on increasing the spectrum efficiency of the wireless channel by using cooperative communications techniques. The fading emerges from the wireless channel variation whose origin lies in the multi-path propagation of wireless signals that induce changes in the received signal strength as function of the node mobility, location and transmitting frequency. The interference emerges between transmitters communicating with a common receiver or between different transmitter-receiver pairs. In this research work, the goal is to fill the gap between the geographic routing protocols working at the network and MAC layer, and the physical layer. Therefore, we target the use of cooperative communications as a solution to the problem described above.

In this section, the cooperative communications approaches, which mitigate some wireless issues are explored. These approaches, shift us to a new point of view where multi-path fading can be viewed as an opportunity to be exploited to improve the performance of wireless networks and specifically for our case, the ad hoc and sensor networks. Thus, our goal is to capture the main elements of cooperative communications, their properties, their application areas, and thus identify the best suited approach to exploit the spatial diversity in wireless networks as well as its appliance to multihop routing.

General concept

The cooperative communications refers to a set of distributed wireless nodes that interact to jointly transmit information in a network where, radio terminals relay signals for each other emulating an antenna array and exploiting the spatial diversity offered by the fading channels, creating additional paths between the source and destination using intermediate relay nodes. Thus, the destination can detect the transmitted information in a wireless channel variation environment since from a statistical point of view, the chance that all channel links involved in the transmission go down is rare. The main motivations to exploit some forms of cooperation are: to improve the reliability of communications in terms of Symbol Error Rate (SER), Bit Error Rate (BER) for a given transmission rate and also to increase the network performance with respect to the transmission rate.

The simplest way to describe the cooperative communication is to reduce the communication to a scenario with three nodes (see Fig. 2.11). This scenario is derived from the commonly relay channel [Cover 79], where a cooperative node named relay, overhears a direct transmission between a source and a destination. First, the source node transmit its data, the destination and the relay node receive the data. Second, the relay node retransmits the previously received data from the source to the destination. Thus, the destination receives the same data twice, via two independent channels with different characteristics. Finally, the different versions of the data at the destination are combined using a combination technique (ie. Maximum Ratio Combining, MRC; Equal Ratio Combining, ERC; Fixed Ratio Combining, FRC; etc.) so as to obtain a final version of the transmitted data. Later on, others works have been derived from the previous model making a generalization of the relay channel where multiple relays are used during the communication process.

Relay behavior and protocols

The relay nodes acting in cooperative communications may have several behaviors with respect to how they process and decode the received signals as well as the combining methods used at the destination nodes. In other references they are called protocols or signaling methods. These behaviors are summarized as follows.

In the Amplify-and-Forward behavior described by Laneman in [ Laneman 04], the relay node receives a noisy version of the source transmitted signal. The Figure 2.11: In phase 1, the source broadcast its data and relay and destination receive it. In phase 2, the relay node retransmit the data received in phase 1. In these two phases, three different fading paths are used relay amplify the signal within its power constraint, and then retransmit it to the destination which combine the received signals using a combining technique (ie. MRC). The main drawbacks of this behavior are: first, when the relay amplifies the signal, it amplifies the noise as well. Second, the relay must use the gain which depends upon the fading coefficient between the source and the relay, so some mechanisms to get or estimate this information must be considered.

In the Decode-and-Forward behavior also described in [ Laneman 04], the relay node first receives the signal, decodes it, and then re-encodes and transmit the signal. The decoding process may take two different forms: the relay may decode the original signal completely which requires some computing resources but has the advantage that an error correcting code could be used at the relay or it may simply realize a symbol by symbol decoding and let to the destination the full decoding task. Due to its simplicity and advantages with respect to the Amplify-and-Forward behavior, the Decode-and-Forward behavior is most often preferred in cooperative networks. In addition to the presented behaviors, Laneman introduces two kinds of relay behavior: selection and incremental relaying. But we rather consider this like a cooperative mechanism that may present one of the previous behaviors. Hence, we will explain them in the next subsection.

Cooperative communications classification

Now with the description of the relay nodes behavior, a broad classification of cooperation strategies is presented. It will help to identify the strategy to follow in order to get an efficient spectrum utilization in scenarios based on Geographic Routing. This classification is composed of three approaches, described as follows.

In the fixed relay approach, all the nodes listening to the channel simply apply either the Amplify-and-Forward or Decode-and-Forward behavior to relay the data to the destination. In the case of fixed Decode-and-Forward behavior, the network suffers a lost in performance when the relay cannot decode the source message successfully.

The second approach is the relay selection, where the relaying nodes are able to measure the channel quality using the fading coefficients between the source and the relay. In this scheme, a threshold is defined and the transmission is adapted to the situation. Thus, if the measured coefficients falls below an assigned threshold, the source continues the direct transmission process using another mechanism like the repetition or more powerful codes, so as to, the destination node can successfully decode the original data. Otherwise, the relay nodes forward what it had already received from the source with an Amplify-and-Forward or Decodeand-Forward behavior.

The third approach called incremental relaying, employs a limited feedback from the destination node that sends a one-bit acknowledgment (ACK) to the relay and the source if it has decoded the source message successfully. Otherwise, it sends a NACK to indicate failure of transmission. In this case the relay, if it has been able to decode the source message, retransmits the message to the destination by employing repetition coding. This approach, can be viewed as an extension of the incremental redundancy or the hybrid automatic-repeat-request (ARQ) protocols that work at the link layer.

Another classification could be mentioned if the layer where the cooperation takes place is taken into consideration. Actually, nodes cooperation may occur in all layers of the OSI model. The cooperative techniques of our interest are located at the physical and network layer. The physical layer cooperation techniques, commonly known as cooperative relaying, ranges from the amplify and forward [Laneman 04], decode and forward techniques [ Lai 06], to the multiplexing of signals into orthogonal subchannel as CDMA [Sendonaris 03] or TDMA [ Laneman 04]. The network layer cooperation techniques, actually all multihop routing protocols could be considered a cooperation techniques as nodes shares their resources to route some packet to the destination, optimizing a specific network metric (ie. path diversity, energy consumption)[Khandani 07, Ibrahim 08a, Zorzi 03, Biswas 04, Biswas 05].

An alternative vision of cooperation between nodes is expressed by the coded cooperation which is commonly known as network coding. Network coding presents the same motivations as the cooperative communications and relaying, but while cooperative communications process signals, network coding process messages or encoded packets, both visions are based on the transmissions over multiple nodes but network coding area is out of the scope of this research work. Refer to [Ahlswede 00], [ Li 03], and [ Koetter 02] if you are interested.

From this very basic classification, a variety of schemes, techniques, and protocols can be found. Some of them, are derived from the basic approaches, other are combinaisons of the last two approaches where the relay nodes are established by a selection scheme that uses some feedback from the destination.

Relay selection

The selection and incremental relaying approaches have gained interest among the ad hoc and sensor networks research community because they can define a number of relay nodes that will help the source to transmit the data. In general, the criteria used by the relays is: to forward the decoded information only if the amplitude of the measured channel coefficient of source to relay link is larger than a certain threshold. However, the challenge is how to define such a threshold that allows the relay to forward only correctly decoded information.

In [ Laneman 03], a Distributed Space-Time Coded (DSTC)cooperative protocol is presented. In DSTC, all relay nodes that can decode the original transmission re-transmit in the same subchannel using a designed space-time code. The potential relay nodes just have to estimate the Signal to Noise Ratio (SNR) of the received signal, and decode them if the SNR is above a threshold, re-encode the signal and transmit it to the destination. Also in [Su 08], the author discusses an alternate criteria that instead of setting a fixed threshold, the relay is assumed to be able to detect whether or not the information symbol is decoded correctly. Relay forwards decoded information to the destination if it can decode the information symbols correctly. Otherwise relay stays silent.

Zhao in [ Zhao 07], presented a group of several relay nodes which assist simultaneously the transmission providing an additional Signal to Noise gain. Here, the number of relays represents the system diversity order. For instance, a scheme with m relays achieves a diversity order m + 1. Even if, the use of multiple relays provide to the system a higher diversity order, it adds some complexity to the system that leads to a waste of bandwidth while adding difficulty to synchronize the nodes. It is shown that the cooperative relaying presented by [Laneman 03, Su 08, Zhao 07] where m relays operate, consumes node resources like energy and time that could affect seriously a network with constrained resource like ad hoc and sensor networks. Thus, another approach taking into account these constraints is needed.

Many other cooperative techniques involving multiple relays can be found in the literature, for a broader vision, see [Sendonaris 03, Ibrahim 08b, Stanojev 06]

Single relay selection

The above issues, form a critical part in the design of relay selection protocols for wireless sensor networks, motivating thus the research community to continue the studies about relay selection schemes but restricting the number of cooperating nodes in order to minimize the nodes resources consumption. Taking as a starting point the principle that only one relay is needed to cooperate with the source node to transmit its messages, the design of the physical layer is simplified. Compared to [Laneman 03], the requirement of space-time codes is eliminated if the source and relay transmit in orthogonal time-slots. Hence, the above drawbacks can be minimized significatively. The present issues related to single relay selection is that it should tackle the problem of how and when to select a relay node from a set of candidates and weather or not a cooperative communication should help the direct transmission.

In cooperative relaying, one new phase is added to the two traditional phases of cooperative communication. It can be executed before the beginning of the data transmission or between the direct and cooperative phases. This choice is intrinsically related to the protocol design. The new phase is called relay selection, it is often based on the Channel State Information (CSI) between the participating nodes, and, usually the CSI is obtained for each transmission since the channel state may vary frequently.

Bletsas et al in [ Bletsas 06], presented a single relay selection scheme based on instantaneous local measurements. The idea is to let the node with the best channel condition relay the signal. Since only one relay is working at each time slot, a very strict time and carrier synchronization among the relays is no longer needed. Furthermore, because the transmission of one information bearing symbol is completed within two time slots, the relay selection has higher bandwidth efficiency. To select the best relay in end to end path between the source and the destination, the potential relay nodes monitor the instantaneous channel conditions from themselves to the source and destination through the overhearing of a RTS/CTS transmission. With the channel information estimation, the relay participate in a distributed relay selection procedure based on a timer. When a relay receives a CTS packet, it triggers a timer inversely proportional to the channel estimation, so, the timer of the relay with best channel conditions will expire the first. Then the self-selected relay sends a flag packet to signal its presence to avoid other candidates try to relay the packet. Since a possible relay add two paths (source-relay and relay-destination) to the transmission, and each of them has different estimations, the authors proposed two policies to help each node to quantify its goodness to relay. In the first policy, the minimum estimation of the two hops is selected. In the second, the harmonic mean of the two paths is used to build the timer. Given this facts, we can say that this protocol has a proactive relay selection behavior since at the beginning the relay node is selected, then the source transmit its data, and finally, the relay re-transmit the data.

Zhao et al [Zhao 05a] added a diversity effect to the Geographic random Forwarding protocol (GeRaF) [Zorzi 03] by means of a generalization of the Hybrid-Automatic Repeat Request (Hybrid-ARQ) and with incremental redundancy, which is served by the relay closest to the destination among those nodes that have successfully decoded the message. The principle is that, retransmitted packets do not need to come from the original source but could be sent by relays that overhear the transmission. In the protocol, known as HARBINGER -see also [Valenti 04] (Hybrid ARQ-Based INtercluster GEographic Relaying), a source encodes a b bit message into a codeword of n symbols length. The codeword is broken into M blocks, the time is also divided in s = M time slots so that one block is transmitted at one time slot. At the beginning, the source transmit its first block M = 1, then in the next slots s, s 2, any node in the decoding set D(s) (nodes that have successfully decoded the message v ∈ D(s)), could re-encode it and transmit the next block of the codeword. To choose the relay node among those nodes in D(s), HARBINGER applies the same principle as GeRaF where nodes use the position information to identify the relays. Thus, it chooses the closest node to the destination by means of a distributed contention phase.

On the same line of work, [Adam 08, Adam 09] attack the spectral inefficiency and the channel over reservation in cooperative communications. They presented two adaptive relay selection protocols. In their first contribution, they introduced the Relay Selection on Demand with Early Retreat (RSoDER), which uses a on demand scheme where the relay selection process is started only if they are needed by the destination node and an early retreat scheme where the nodes with bad channel conditions do not participate in the selection process. In their second contribution, they proposed Multi-Hop-Aware Cooperative Relaying (MHA-Coop-Relaying) cross-layer scheme which tries to exploit routing information along with cooperative communications. Here, instead of using a hob by hop cooperation, they detected relay nodes that can act in a multi-hop environment (node relaying in a two-hops progress) to avoid the channel reservation. To achieve this, the source node should know the next two hops (ie. D1 and D2) in the path to the final destination. Then, they put the potential relay nodes into two sets, the single-hop relay (potential relay nodes to D1) and the multi-hop relay composed of nodes that can relay the data in a two-hop distance from the source node (ie. potential relay nodes that are in D1 and D2 transmission range). Thus, when a message from source node gets D1 a traditional cooperative communication has been effectuated. But, whenever the message being routed reaches D2 during a cooperation process initiated by the source, a two-hop cooperation is achieved improving the channel utilization.

The Adam et al contributions are very similar to the work of Coronel [Coronel 07] presented one year before of the MHA-Coop-relaying appearance. The Coronel's work differs in that, the protocol is based on geographic routing. Another important feature to remark, is that in MHA-Coop-Relaying the source node should know its two next hops in the path to work, while in Coronel's this information is not needed.

In [Liu 07a], Liu et at described their Cooperative MAC protocol (CoopMAC) based on the IEEE 802.11 protocol. They presented two different versions: Coop-MACI and CoopMACII. The former, a new control frame Helper ready To Send (HTS) is added to prevent other nodes that a relay node will cooperate with the transmission and the destination node reserve two channel slot times for both transmissions. In the latter, the HTS frame is not used, instead the RTS frame is used to advice to its neighbors who is the relay node.

Mainaud et al proposed WSC-MAC [ Mainaud 08] for WSN. In their protocol, the nodes are randomly grouped into sets. When a node transmits a packet, the nodes with the same set ID will participate at the relay selection, thus they limit the number of nodes involved in the process. Then a link state algorithm is executed at each node from the set that is assumed close to one, and the relay node will cooperate only if it enhances the transmission performance with respect to the channel link estimation between the source-destination.

Other references to relay selection algorithms will be cited later while describing our contributions.

Discussion

In this chapter, an extended survey of the state of the art about the routing problem for wireless networks was presented, specifically the sensor networks. Recent research works look at the geographic routing as an attractive solution since it has good scalability. However, most of the geographic protocols presented here suffer from some restrictions. They are implemented having in mind an isolated network layer and cannot cope efficiently neither with node and link failures or mobile nodes, nor with the wireless channel impairments like fading and interference that make wireless transmission a challenging task. In the second part of this chapter, we survey the cooperative diversity and its derived single relay selection techniques that effectively mitigates the channel impairments. The majority of cooperative techniques are physical layer oriented and few of them interact with the MAC layer.

Therefore, it is confirmed that a layered approach in wireless sensor networks, where each layer stack is unaware of the operation of other layers, eliminates the benefits of joint optimization across protocol layers. Hence, a joint cross-layer design between the network and MAC layers on the one hand, and a node cooperation mechanism on the other, is necessary to improve the overall network performance. With this crosslayer approach, we exploit the synergies at the different layers while satisfying the network resource constraints. As stated at the introduction of the present work, our goal is to integrate the network, MAC and physical layers such that the network layer will take advantage of the broadcast nature of wireless transmissions to send the packet, the MAC layer will provide us the forwarding node with respect to a predefined metric and the physical layer will propose the reliability in transmission offered by the cooperative communications.

Chapter 3

Models and tools

Introduction

The precedent chapter presented the state of art related to the geographic routing and cooperative communications. Those works are based on some models and assumptions that will be described in this section. You can skip this part if you are familiarized with the theory, otherwise, it is advised to read it carefully to have a complete overview of how the protocols work.

The chapter is organized in two parts. It starts by describing the network models together with some graph concepts, then, it describes some common propagation models, finally, in the second part it describes the tools used to simulate and compare the contributed protocols and algorithms.

Before describing in details the models, a general overview of a sensor network is presented. Let consider a wireless sensor network with a set V of n nodes distributed in an area, generally a two dimension plane. The sensor nodes are composed of one or several sensor units and one omnidirectional antenna. The node transmission range is considered as a disk centered at the sensor node with a radius equivalent to the transmission power. A lot of works, consider in general the transmission range as a normalized value to the unity. In addition, in some scenarios, the sensor nodes have a Global Positioning System (GPS) receiver, which provides the location information to the node. If GPS devices are not present, some alternative methods are used as the relative and virtual coordinates to embed the node in a graph. The routing protocols working with location information apply some techniques and concepts based on the computational geometry to solve some issues in the route construction, thus, the geometric models described in the next sections belong to the computational geometry field.

Network models

The previous description of a wireless sensor network corresponds to the Unit Disk Graph (UDG) model, where an edge between two nodes u and v exists if the Euclidean distance between the nodes is at most 1. The Euclidean distance correspond to the radius of the disk in the plane (observe in Fig. 3.1 the UDG model and in Fig. 3.2 a WSN modeled as UDG graph). The network graph at a given time may be static or dynamic, depending on the nodes position, transmission power, mobility patterns and node failures. The UDG graph is the most common model used to study the wireless networks due to its simplicity. However, it is known that this model derived from wired networks might represent the wireless network inaccurately as it ignores several wireless properties. Compared to wired networks, the WSNs need a special treatment derived from their properties and limitations. These networks are battery powered with a limited memory. Therefore, the challenge is bigger when trying to design an efficient routing protocol that saves the resources consumption. In fact, many routing protocols are based on some geometric properties of the graph to operate effectively and efficiently. This is the case of the geographic routing protocols (also known as position-based routing) that are based on the right hand routing such as Greedy Perimeter Stateless Routing (GPSR), Greedy Face Greedy (GFG), Adaptive Face Routing (AFR), Greedy Other Adaptive Face Routing (GOAFR+), etc. These protocols, ask the network topology to be planar to guarantee the message delivery, and specially avoid the path loops. A planar graph is one that can be drawn on a plane in such a way that there are no "edge crossings," i.e. edges intersect only at their common vertices. This is difficult to get in real networks, and obviously, the edges may cross when the network is modeled by the unit disk graph (UDG does not belong to the class of planar graph). The alternative to this issue is to design a network topology that builds a subgraph of the UDG so that it can be constructed and updated efficiently, and with some special properties such as planarity, bounded node degree, low-stretch factor that provides the basis platform to build a localized routing scheme with guaranteed performances. We briefly describe some planar and connected subgraph derived from the UDG model.

The Minimum Spanning Tree of G denoted M ST (G), is the tree belonging to E that connects all nodes and whose total edge length is minimized. M ST (G) is obviously one of the sparsest connected subgraphs, but its stretch factor can be as large as n -1 and its construction is centralized.

A Gabriel Graph GG(G), is a graph that connects a set of points in the Euclidean plane. Two points u and v are connected by an edge in the Gabriel Graph whenever the circle having line segment uv as its diameter contains no other points from the given point set. More generally, in any dimension, the Gabriel graph connects any two points forming the endpoints of the diameter of an empty sphere. See in Fig. 3 The Gabriel graph was used as a planar subgraph in the GFG and the GPSR protocols when the protocols work at the recovery mode so as to guarantee the packet delivery. The Relative neighborhood graph was used for efficient broadcasting in [Seddigh 01] in order to minimize the number of retransmissions in a one-to-one broadcasting model.

The Delaunay Triangulation and its dual, the Voronoi Diagram [Aurenhammer 91], are also two geometric structures used in the conception of some ad hoc routing protocols. A triangulation of V is a Delaunay triangulation (see Fig 3.5), denoted by Del(V ), if the circumcircle of each of its triangles does not contain any other nodes of V in its interior. A triangle is called the Delaunay triangle if its circumcircle is empty of nodes of V . The Voronoi region, denoted by V or(v), of a node v ∈ V is the collection of two dimensional points such that every point is closer to v than to any other node of V . The Voronoi diagram for V , denoted by V or(V ), is the union of all Voronoi regions V or(v), where v ∈ V .

Other geometric structures have been proposed that may be applied to geographic routing protocols such as the Yao Graph [Yao 82] where a parameter k (for some integer k ≥ 6), denoted Y G(G), is defined as follows: at each node u, divide the plane into k equally separated cones centered at u; then, connect u to its closest neighbor within each cone. In [ Li 02], the authors proposed the Unit Delaunay Triangulation U Del(V ) where given a set of points V , U Del(V ) is the resulting graph of removing all edges of Del(V ) that are longer than one unit (U Del(V ) = Del(V ) ∩ U DG(V )). Other interesting alternatives are the Restricted Delaunay Graph (RDG) [ Gao 05] and the Local Minimum Spanning Tree (LMST) [ Li 03].

Discussion

To create valid routing schemes in wireless networks as ad-hoc and sensor networks, it is necessary to describe the physical relationship between nodes. Here, geometry seems to be the natural tool, as the devices exist, more or less, on the plane. Furthermore, graphs seem to be a natural representation for networks, and geometric graphs are even more suited for the task. Researchers first made use of the Unit Distance Graph, but eventually that model proved to be insufficient. So other geometric structures were developed to capture the relationships between nodes more accurately. From these structures, we must attempt to find subgraphs of the graphs that will serve in a routing scheme.

Power-attenuation model

A critical issue in WSN, is the energy consumption of the nodes that impact the network lifetime. Each node is composed by transmission, reception and processing units. When a node transmit some data, the involved nodes consume some energy resources that can be estimated by the sum of three parts. First, the source node consume some resources to prepare the signal. Second, in the most common power-attenuation model, the power needed to establish a link between u and v is uv β , where uv represents the Euclidean distance between the nodes, and β is a constant between 2 and 5 dependent on the transmission environment, typically called path loss constant. Finally, when a node receives the signal, it needs to consume some power to receive, store, and precess that signal. For simplicity, a lot of research works consider it as a constant for all the nodes in the network. Thus we can say that, the power cost p(e) of a link e = uv is the power consumed to transmit a signal from u to v.

Radio propagation models

The transmitted signal over wireless channels are subject to the physical environment that modifies the originally transmitted signals at the receiver, introducing some uncertainty about the original encoded and modulated data, resulting in errors during the transmission. Thus, the wireless signal impacts significatively the protocols performance so, the networks simulator should take it into consideration and use some radio propagation model to obtain information like the signal strength, attenuation, interference that affect the simulation development. Several models have been proposed which differ basically in their complexity and accuracy to model the wireless signals.

The free space model is one of the most widely used. It is simple as it consider an isotropic transmission range that allows to behave like a unit disk graph. The free-space model consider a propagation through a clear line of sight between the transmitter and the receiver, and, where the signals are subject to a distance dependent loss of power (path loss). Friis derived an equation to compute the received signal power P r at a distance d from the transmitter.

P r(d) = P tGtGrλ 2 (4π) 2 d 2 L = P tGtGrλ 2 (4π) 2 d 2 0 L . d 0 d 2 = P r(d 0 ). d 0 d 2 (3.1)
Where P t is the power of the transmitted signal, λ correspond to the wavelength, Gt and Gr are the antenna gains of the transmitter and receiver respec-tively. L ≥ 1 represents the system loss induced by the transmit/receive circuity and generally is set to 1. The transmission radius r is the distance d at which the power of the received signal P r(d) equals the receiver sensitivity (minimum required power to receive and decode successfully a packet. Thus, the nodes within the transmission range r receive all the packets, and if the distance d > r, they are not able to receive the packets at all. d0 is the far-field distance, which is a reference distance, generally 1 meter for short range systems like wireless data networks.

Since the free-space model is rarely found in practical cases, because the multipath propagation due to reflection from the ground was omitted. With this phenomena present in wireless transmissions, it is likely that not only a single but multiple copies for the same signal reach the receiver over multiple paths with different characteristics. Thus, the model was slightly generalized to:

P r(d) = P r(d 0 ). d 0 d γ (3.2)
where γ represents the path-loss exponent, which varies between 2 and 5 according to the environment (free-space and shadowed and obstructed in-buildings scenarios). The path loss is defined as the ratio of the radiated power to the received power, using Eq. 3.2, it can be expressed in decibel in the following equation.

P L(d)[dB]

= P L(d 0 )[dB] + 10γlog 10 d d 0 , (3.3)
which is commonly known as the log-distance path loss model. P L(d)[dB] is the path loss at the reference distance.

Another model, considered as an extension to the log-distance model was proposed in order to improve the accuracy of the model by accounting the presence of obstacles into account as a shadow effect: the log-normal fading model. Here, the shadow effect is considered as a zero-mean Gaussian random variable X σ , with a standard deviation σ. Thus, the received power in dB can be expressed as follows:

Allowable path loss P L(d) = P athloss + shadow ef f ect

P L(d)[dB] = P L(d 0 )[dB] + 10γlog 10 d d 0 + X σ (3.4)

Discussion

From the propagation models, we can note that the received power at the nodes depends on the frequency, and on the distance between transmitter and receiver, as well as the reflection, diffraction, scattering phenomena. Thus, a wireless routing protocol design should pay a lot of attention on the influences generated by physical layer during a communication process.

Mobility models

In some sensor networks, nodes can move (e.g., assisted living through wearable sensors, tracking, etc.) as well as the data collectors. In this chapter we illustrate the most important mobility models that have a great impact on the performance of routing protocols in wireless sensor networks such as the Random Waypoint (RWP) and the Brownian model.

Random waypoint model, is the most commonly used mobility model for ad hoc networks and sensor networks. The model has been introduced in [Johnson 96], where, each node chooses uniformly at random a destination point (the waypoint) within the deployment region R, and moves toward it along a straight line. Node velocity is chosen uniformly at random in the interval [vmin, vmax], where vmin and vmax are the minimum and maximum node velocities. When the node arrives at destination, it remains stationary for a predefined pause time, and then starts moving again according to the same pattern.

RWP represents an individual movement of the nodes with a obstacle-free scenario, meaning that, each node moves independent of each other, and it can may move in any subregion of R (obstacle-free). The RWP model has also been generalized to slightly more realistic model by [Bettstetter 03]. The authors, is extended the RWP model by allowing nodes to choose pause times from an arbitrary probability distribution. Furthermore, a random fraction of the network nodes remains stationary for the entire simulation time. In Fig. 3.6, we plotted multiples nodes with a RWP behavior.

Brownian motion model has a different vision of RWP where the mobility looks like intentional movement. This model resembles to a non intentional motion. For this reason, sometimes the model is called drunkard-like model. In Brownian motion, the position of a node at a given time step depends (probabilistically) on the node position at the previous step. In particular, no explicit modeling of movement direction and velocity is used in this model. In [Santi 03], the Brownian mobility is modeled with pstat, pmove and m parameters. The pstat represents the probability that a node remains stationary for the entire simulation time. The pmove parameter, is the probability that a node moves at a given time step. And the m parameter models the velocity: if a node is moving at step i, its position

Simulation tools

Throughout the thesis, various tools were used to simulate and analyze the performance of the contributed protocols and algorithms. In this section, those tools are briefly described and it is indicated why we elected them.

OMNeT++ [Omnetpp ] simulator along with the Mixim [MiXiM ]framework were used to simulate and analyze the geographic routing protocols at the packetlevel. The simulator was developped by Andras Varga from the Department of Telecommunications (BME-HIT) of the Technical University of Budapest, Hungary. OMNeT++ is a discrete event simulation environment with an extensible, modular, component-based C++ simulation library and framework, with an Eclipse-based IDE and a graphical runtime environment. Domain-specific functionality (support for simulation of communication networks, queuing networks, performance evaluation, etc.) is provided by model frameworks, developed as independent projects. Its modular structure, its scalability with respect to NS-2, its possibility to run simulations under various user interfaces such as graphical, animating user interfaces are highly useful for demonstration and debugging purposes, and command-line user interfaces for batch execution, motivated us to take it as our simulation environment.

Although OMNeT++ provides a powerful and clear simulation framework, it lacks of direct support and a concise modeling chain for wireless communication. Both is provided by MiXiM. MiXiM joins and extends several existing simulation frameworks developed for wireless and mobile simulations in OMNeT++.

Matlab [Matlab ], as explained above, Omnet++ is a network simulator at the packet-level. To study the behavior of our Geographic Cooperative protocol (CoopGeo) contribution, It was needed to simulate it at bit streams level. In principle its implementation in Omnet and Mixim is possible, but it would carry a lot of complexity, work, and, it would still ask for making a lot of abstractions at the physical layer. Therefore, another tool was used, for instance Matlab. With Matlab, the contributions were successfully simulated with different modulation types as required.

Chapter 4

CoopGeo: A Cooperative Geographic Routing Protocol

In chapters 1 and 2, the Beaconless Geographic Routing protocols were presented as an enhancement to the traditional geographic routing, their vision is based on a cross-layer design which mixes the network and MAC layer. In fact, these beaconless protocols cannot profit from all the available bandwidth and translate it to a good achievable throughput since it lacks of a broad wireless vision: it does not exploit the broadcast nature of the wireless transmissions. Hence, the central object of this chapter is to adapt this beaconless vision to be sensible to the wireless channel, thus, we propose a system that makes the sensor network communications reliable in terms of end to end delivery, and thus, to cope with the influence of attenuation due to fading and shadowing during the communication process.

The cooperative relaying has focused the attention of this research work, since it has been proposed as a promising transmission technique that effectively creates spatial diversity through the cooperation among distributed nodes. However, it is remarked that to achieve efficient communications while gaining full benefits from nodes cooperation, more interactions at higher layers of the protocol stack, in particular the MAC (Medium Access Control) and network layers, are indispensably required. This is ignored in most existing cooperative relaying works that mainly focus on physical-layer cooperative techniques. In this chapter, the first contribution is described. It proposes a cross-layer framework involving two levels of joint design, one is a joint MAC-Network cross-layer design for forwarder selection (or termed routing), and the other MAC-Physical for relay selection. Based on geographical information of nodes and contention processes, the proposed cross-layer protocol, CoopGeo, aims at providing an efficient approach to select the next hops along the communication path as well as the optimal relay for each cooperative hop.

The chapter is organized as follows. At the beginning, the context of cooperative communications and geographic routing is presented. The network model of cooperative multi-hop networks and the problem statement are described in section 4.2. Section 4.3 details CoopGeo, i.e., the proposed cross-layer design for cooperative wireless sensor networks, in which beaconless geographic routing and relay selection, along with a feasible protocol, are included. In section 4.4, we give the numerical simulation results for CoopGeo and evaluate its performance by comparing with an existing protocol.

Introduction

In chapter 2 was stated that by taking advantage of the broadcast nature of the wireless medium, neighbors overhearing data packets can assist the ongoing transmission. Such resource sharing (e.g. power, antennas, etc.) achieved by nodes cooperation is a fundamental idea of cooperative communications. In other words, the number of degrees of freedom in wireless systems can be effectively increased by enabling collaboration between network nodes. Most attractively, without the requirement of equipping wireless terminals with multiple antennas to construct a multiple-input multiple-output (MIMO) system, cooperative techniques break the limitations of the physical size and hardware complexity present in wireless sensor networks.

Most existing work on cooperative techniques focuses on physical-layer cooperation, where various diversity-oriented signaling strategies have been proposed and further demonstrated on the basis of information theory [Laneman 04, Sadek 07, Herhold 04]. However, to achieve efficient communications while gaining full benefits from nodes cooperation, more interactions at higher layers of the protocol stack, in particular the MAC (Medium Access Control) and network layers, are indispensably required. Furthermore, an efficient cooperation-based MAC (or cooperative MAC) scheme should be not only payload-oriented but also channel-adaptive to improve the network throughput and diversity gain simultaneously; otherwise, an inefficient MAC scheme may even make cooperation gain disappeared [ Sanchez 09].

Two major questions related to cooperative MAC design need to be answered: 1) when to cooperate? 2) whom to cooperate with and how to do selection? For the first question, intuitively there is no need to do cooperation if the direct link is of high quality. In addition, cooperation inevitably introduces inefficiency in some degree due to extra protocol overhead and limited payload length. Therefore a cooperative MAC protocol should be carefully designed to prevent unnecessary cooperation. The second question addresses the typical relay selection problem. There may exist a group of available relays around the source; however, some are beneficial and some not. How to find the optimal one(s) efficiently and effectively is of vital importance to a practical MAC protocol.

Most relay selection schemes focus on the design of enhancing system reliability in a centralized manner [Yi 08], neglectful of the needs of overhead produced by nodes coordination, unmindful of the feasibility of capturing a lot of channel state information (CSI) among nodes, unsuitable for being used in resourceconstrained networks. On the contrary, to the best of our knowledge, there is very limited study in the literature on joint MAC-physical layer design for relay selection [Liu 05, Shan 08, Wang 09c]. In [ Liu 05], a cooperative MAC protocol called CoopMAC is proposed to alleviate the throughput hindrance caused by low-date-rate nodes. The main idea is to allow a high-data-rate node helping the data delivery through two-hop transmission. In [ Shan 08], the authors proposed a busy-tone-based cross-layer cooperative MAC (CTBTMA) protocol, where busy tones are utilized to solve collisions in a cooperation scenario and address the optimal relay selection problem. In [Wang 09c], an efficient relay selection scheme based on geographical information is proposed. By jointly combining the source-relay and relay-destination distances, the optimal relay offering the best cooperative link could be efficiently determined. However, the selection process proposed by [Wang 09c] requires a central controller to decide which relay is most helpful, leading to more overhead and power consumption. One goal of the contribution, is to present a distributed relay selection protocol based on [Wang 09c], with MAC-physical cross-layer design.

Likewise, in view of the interaction between the MAC and network layers, we also consider routing issues in this contribution since a properly designed MAC protocol can facilitate routing process at the network layer. In particular, we incorporate the BeaconLess Geographic Routing (BLGR) [Heissenbüttel 03, Fubler 03, Zorzi 03, Blum 03, Sanchez 07]. BLGR is one of the most efficient and scalable routing solutions for wireless ad hoc and sensor networks. The key advantage of BLGR is that it needs neither prior knowledge of network topology for making a route decision nor the periodic exchange of control messages (i.e., beacons) for acquiring neighbors' geographic locations. A current node can make its own routing decisions by using local information. In general, a BLGR protocol comprises two operating phases: forwarding phase and recovery phase. In the forwarding phase, routing decisions are made according to the greedy mechanism, a neighbor closet to the destination is chosen as the next hop of a current node. Greedy forwarding, however, fails when reaching a local minimum, i.e., a current node that has no neighbor closer to the destination. In this case, the recovery mode based on the well-known face routing algorithm is triggered to find another path to the destination.

It is worth noting that BLGR at the network layer is usually coupled with MAC protocols to offer better network throughput and preserve advantageous properties such as localized operation and high scalability. A paradigm of network-MAC cross-layered BLGR protocol is as follows: through a contention process at the MAC layer, each candidate forwarder sets a contention timer depending on the progress to the destination such that the optimal candidate (closest to the destination in greedy sense) responds first, as a result of time-out. Hence, cross-layer design between the network and MAC layers is quite significant. In [ Sanchez 07], Sanchez et al proposed a cross-layered BLGR protocol called BOSS, which uses a three-way (DATA/RESPONSE/SELECTION) handshake and an area-based timer-assignment function to reduce collisions among responses during the forwarder selection phase. However, when operating in recovery mode, BOSS performs face routing by requiring the exchange of complete neighborhood information. To avoid this drawback, we present a fully beaconless protocol that does not require beacons in both the greedy forwarding and recovery modes.

Above, the interactions between the MAC and physical layers and between the network and MAC layers, in a cooperative scenario were introduced. This contribution aims at the integration of the network (NWK), MAC, and physical (PHY) layers as cross-layer design so as to enhance overall system performance. Two issues, routing and relay selection, are the two chief considerations. The proposed novel cross-layer framework, called CoopGeo, consists of two joint crosslayer designs, a joint network-MAC design for next hop selection and a joint MAC-physical design for relay selection. In particular, both the routing and relay selection solutions in CoopGeo are geographic protocols using contentionbased selection processes, providing a strongly practical multi-layer integration for cooperative networks.

The contributions of CoopGeo are:

• It proposes a distributed MAC-PHY cross-layer design for relay selection based on the geographic approach [Wang 09c], where the best relay is chosen as the one that provides the minimum average point-to-point SER. • It presents a fully beaconless approach to geographic routing with a MAC-NWK cross-layer design, where both the greedy forwarding and recovery modes are executed without periodic exchange of beacons and complete neighborhood information. • From networking to communications, the proposed protocol CoopGeo provides a comprehensive integration across the most critical protocol layers, including NWK, MAC, and PHY, to achieve a highly-efficient communication. • Based on the use of geographic information and contention processes, the framework of CoopGeo that supports localized operation as well as high

Network Model and Problem Statement 4.2.1 Network Model

To design the cross-layer framework, a wireless sensor network is considered with k nodes randomly deployed in an area, represented as a dynamic graph G(V, E), where V = {v 1 , v 2 , . . . , v k } is a finite set of nodes and E = {e 1 , e 2 , . . . , e l } a finite set of links between the nodes. A subset N (v i ) ⊂ V , i = 1, . . . , k is denoted as the neighborhood of the node v i , defined as those nodes within the radio range of v i . Fig. 4.1(a) depicts the wireless sensor network model, in which the source S sends its data to the destination D in a multihop manner. In this figure, the dashed circle centered at S illustrates the radio range of S, and so on. At the beginning of every data transmission, S broadcasts the data to its neighbors N (S). One of these neighbors N (S) is chosen as the next hop through a forwarder selection process, denoted as F 1 . Two transmission modes, namely direct and cooperative modes, are considered to operate in each hop. In the direct mode, a point-to-point communication is performed by direct transmission; in the cooperative mode, it is done by cooperative relaying. The cooperative mode operates only when F 1 cannot correctly decode the data from S. After having a correct version of the data packet, F 1 acts as the source node and repeats the same procedure, and so on until the data packet reaches the destination D.

Since the multihop transmission is realized by concatenating multiple singlehop schemes, as shown in Fig. 4.1(a), for convenience of notations S denotes the current source in a current hop and F the forwarder, also called the next hop or the intermediate node in this chapter. In addition, R i , i = 1, . . . , |N (S)| represents the candidate relays of S, one of which is going to cooperate with S whenever needed. Fig. 4.1(b) illustrates the transmission schemes for direct and cooperative modes respectively, where the only difference between them is that F also receives the data from R in the cooperative mode, but not in the direct mode. In the following the signal models for the direct and cooperative transmission modes are introduced.

In the direct mode, S broadcasts its symbol x with transmission power P , where the average power of x is normalized to unity. The received signals at F can be expressed as

y S,F = √ P h S,F x + n S,F , (4.1)
where h S,F is the channel fading coefficient from S to F , modeled as h S,F ∼ CN (0, σ 2 S,F ); the additive noise term n S,F is a circularly symmetric complex Gaussian random variable, assumed as n S,F ∼ CN (0, N 0 ). Without loss of generality, it is assumed that the noise terms have equal variance with N 0 = 1.

For the cooperative mode, it applies a two-phase decode-and-forward (DF) strategy with single-relay selection, described as follows. In the first phase, S broadcasts its symbol x with transmission power P x while the next hop F and a selected relay R (through a relay selection process) listen. The received signals at F and R can be respectively expressed as

y S,F = P x h S,F x + n S,F , (4.2)
y S,R = P x h S,R x + n S,R , (4.3)
where h S,R is the channel fading coefficient from S to R, modeled as h S,R ∼ CN (0, σ 2 S,R ); the additive noise terms n S,R is a circularly symmetric complex Gaussian random variable, assumed as n S,R ∼ CN (0, N 0 ). In the second phase, with the simple adaptive DF strategy [Herhold 04], the selected relay decides whether to forward the decoded symbol to the next hop. If the relay is able to decode the transmitted symbol correctly, it forwards the decoded symbol with identical transmission power P x to the next hop, and if not, it remains idle. In practical scenarios, this 'adaptive' mechanism can be achieved based on an SNR threshold. If the SNR at the relay is greater than a certain threshold, the relay forwards; otherwise, it remains idle. Define the indicator function I R as follows:

I R = 1, if R decodes the transmitted symbol correctly, 0, otherwise. (4.4)
Then, the received signals at the the next hop in the second phase can be written as y R,

F = P x I R h R,F x + n R,F , (4.5)
where h R,F denotes the channel fading coefficient from R to F , modeled as h R,F ∼ CN (0, σ 2 R,F ), and n R,F denotes AWGN, n R,F ∼ CN (0, N 0 ). Finally, the next hop coherently combines the received signals from the current source and the selected relay, i.e., y S,F and y R,F , by using a maximum ratio combining (MRC)

y F = P x h * S,F y S,F + P x I R h * R,F y R,F . (4.6)
Consequently, the decoded symbol x at the next hop is given by x = arg min

x∈A |y F -P x (|h S,F | 2 + I R |h R,F | 2 )x| 2 , (4.7)
where |A| = Θ denotes the cardinality of Θ-ary constellation. By invoking the performance analysis in [ Su 08], the resulting symbol error rate (SER) at the next hop can be expressed as

P s ≈ 4N 2 0 b 2 P 2 x σ 2 S,F A 2 σ 2 S,R + B σ 2 R,F , (4.8)
which is a tight approximation in a high SNR regime, where if M -PSK modulation is used, b = sin 2 (π/M ), and

A = M -1 2M + sin( 2π M ) 4π , B = 3(M -1) 8M + sin( 2π M ) 4π - sin( 4π M ) 32π ; (4.9)
A = M -1 2M + (1 -1/ √ M ) 2 π , B = 3(M -1) 8M + (1 -1/ M ) 2 π . (4.10)
Moreover, the following assumptions in the network model are considered: 1) each node has a single antenna operating over frequency-flat fading channels and can only either transmit or receive data at any time slot; 2) The network is dynamic and the network topology, including the cardinality of a node's neighborhood, the location of nodes, and the linkage between nodes, changes over time due to wireless environments, duty circles, and node failures, etc.; 3) each node is aware of its own location; 4) In addition to itself's location, the source knows the location of the destination, and so does any intermediate node; 5) All the network nodes are homogeneous, and each could become a source, a relay, or a forwarder.

Problem Statement

In considering how cross-layer design improves network throughput and reliability for wireless cooperative multihop sensor networks, the first question that arises concerns the joint MAC-Network cross-layer routing design. For a network G(V, E), given a source-destination pair v S , v D ∈ V , the objective of a routing task is to find a subset of forwarders P F = {v F 1 , v F 2 , . . . , v Fn } ⊂ V that builds a routing path from v S to v D with successful packet delivery guaranteed. In particular, each forwarder in P F is determined locally, within a forwarding area defined as the radio coverage of the current source, which is divided into a positive progress area (PPA) and a negative progress area (NPA). In both, the PPA and The second question that this study addresses, concerns the joint MAC-PHY cross-layer relay selection design. The aim of CoopGeo relay selection is to find a subset of optimal relay nodes P R = {v R 1 , v R 2 , . . . , v Rm } ⊂ V \ P F to enhance the network reliability, where each optimal relay v R i that minimizes the average point-to-point SER for each cooperative hop is locally selected within a relay area defined as a reuleaux triangle.

One design goal of CoopGeo is to develop a fully beaconless approach to geographic routing that does not rely on periodic exchange of beacons as well as complete neighborhood information. Therefore, forwarder and relay selection use a local contention process based on geographical information and area-based timers. A specified interval of time T max is assigned to each selection process.

By tackling the above issues, it is contemplated a feasible cross-layer protocol that comprehensively integrates the NWK, MAC, and PHY layers to achieve a highly-efficient communication. In the following section the framework of the proposed cross-layer design is detailed.

CoopGeo: A geographic cross-layer protocol for cooperative wireless networks

CoopGeo, in general, performs two tasks in wireless cooperative multihop sensor networks: routing and relay selection (see CoopGeo architecture in Fig. 4.3). As described above, the routing process works in two phases, i.e. BLGF and BLRF. Both phases share equally a T max interval of time where the forwarder selection is executed. The first half of the T max period is allocated to the BLGF phase and the second half to the BLRF phase.

In the BLGF phase, a next hop that provides maximal progress toward the destination is selected through a timer-based contention process. When failing to find a next hop in the BLGF phase, the routing process enters transparently to the BLRF phase and applies face routing by using graph planarization along with a select-and-protest principle. Cooperative relaying is required after the routing task, whenever the selected next hop decodes the data packet erroneously. In this case, CoopGeo starts out to execute the relay selection task within another interval of time T max , selecting an optimal relay that offers the best cooperative link between the current source and the next hop. Fig. 4.1(a) gives an example for both the routing and relay selection in Coop-Geo. The nodes competing in the BLGF phase are those located in PPA, i.e., X 1 , X 2 , R 1 , and F 1 . Those located in NPA, i.e., W 1 , . . . , W 4 , are considered to compete in the BLRF phase. The node F 1 is selected as the forwarder node, where the data transmission between the source S and the forwarder F 1 is carried out through a direct or cooperative transmission. In the case a cooperative transmission is used, the candidate relays with respect to the transmitter-receiver pair (S, F 1 ) that participate during the relay selection process are those within the relaying area (that will be defined later), including R 1 and X 1 . In this figure R 1 is selected as the optimal relay node of the cooperative transmission.

Beaconless Greedy Forwarding (BLGF)

At the beginning of a data transmission, S triggers the BLGF phase of the routing process by broadcasting its data to the neighborhood and then waits for the best next hop's response during the first half of the Tmax time. During this period, the neighborhood compete to forward the message by setting their contention-based timers (T CBF ), as will be explained in Section 4.3.1.1. When the best forwarder node is selected due to its timer expiration, it sends a Clear-To-Forward (CTF) message to S, then, the other candidates overhearing this message suppress their running timers and delete the data received from S. Since some candidates situated at the forwarding area may be unable to hear the CTF message, the hidden terminal problem could appear. To prevent it, S broadcast a warning message (SELECT) to indicate that a forwarder node has been found. The hidden candidates overhearing it, will suppress their timer and the data packet. Immediately, F send an acknowledgement (ACK) to S and thereafter, it acts as the source and repeat the process hop-by-hop until the data is delivered to the final destination D.

Geographic contention-based forwarder selection (T CBF )

To implement the BLGF phase, the timers settings are based on the metric proposed in [ Sanchez 07], which applies an area-based assignment function. Fig. 4.2 depicts, as mentioned above, two areas, PPA and NPA, that divide the radio coverage of a current source, both of which are further divided into sub-areas called Common Sub-Areas (CSAs) in order to avoid collisions during the contention period. Moreover, those candidate nodes situated at the same CSA offer similar progress toward D, and thus, they have similar T CBF values. Note that unlike [Sanchez 07], the NPA area is divided by using concentric coronas instead of slides as used at the PPA area. The reason will be discussed at the BLRF section.

The timer setting for each candidate node is given as follows. First, each candidate node situated in PPA identifies which CSA group it belongs to by using the following equation:

CSA P P A = N SA × r -(d S,D -d F i ,D ) 2r (4.11)
where N SA is a predefined even number of sub-areas to divide the coverage area, r is the transmission range which is equal to the largest progress, and (d S,Dd F i ,D ) represents the candidate progress to the destination (candidates located in NPA use Eq. (4.13).

Next, given CSA P P A , hereafter called CSA, each candidate calculates its T CBF timer according to:

T CBF = CSA × T max N SA + rand T max N SA (4.12)
where T max represents the maximum delay time that the current source S will wait for a next hop's response, and rand(x) a function obtaining a random value between 0 and x to reduce the collision probability. The T CBF function allocates the first half of T max to PPA candidates for the BLGF phase and the second half to the NPA candidates for the BLRF phase.

Beaconless Recovery Forwarding (BLRF)

As introduced before, the BLGF mode may suffer from the local minimum problem: the packet may be stuck at a node that does not have a neighbor (at PPA) closer to the destination than itself. To solve this problem, the Beaconless Forwarder Planarization (BFP) algorithm of [ Kalosha 08], which guarantees the packet delivery is applied at BLRF. BFP reduces the number of messages exchanged by using the select-and-protest principle. In the select stage, some NPA neighbors are selected to form a planar subgraph according to a contention function, then, in the protest stage, falsely planar edges are removed from the subgraph. Finally, the traditional face routing algorithm is applied to select the forwarder node.

BFP is implemented at the BLRF phase of CoopGeo as follows, first, the current source detects the local minimum when a T max /2 time has passed without receiving any CTF message from any neighbor situated at PPA. Thus, CoopGeo switches automatically from the BLGF mode to the BLRF mode, so that, BFP is applied during the second half of T max . To accomplish this, the candidate nodes situated at the NPA area determine their CSAs and compute their contention timers (T CBF ) that will be used by the BFP algorithm. Once the planar subgraph is build, S send a SELECT message to the node that has been elected forwarder node, which confirms the reception with an acknowledgement.

In [Sanchez 07], the CSAs of NPA are created according to the progress toward the destination. CoopGeo, by contrast, adopts the distance with respect to the node that is suffering the local minimum problem, and accordingly, the slides are modified to concentric coronas.

Thus, The NPA area is divided into n = N SA , where the width of the i-th corona is ( √ i -√ i -1)r 1 , and r 1 is the radius of the first corona, being calculated with r 1 = r/ √ n. To use the same terminology as the one used at the BLGF phase, in the following a corona will be referred as a CSA. To set a contention timer, a candidate F in NPA first finds its CSA N P A index by using the following equation:

CSA N P A = √ n • d v,u r 2 + N SA 2 (4.13)
With knowledge of their CSA N P A index, hereafter called CSA1 , each NPA forwarder candidate determines its contention timer according to (4.12), rather than the original equation defined by Kalosha expressed here just as reference and finally, BFP is applied.

T CBF = d r • T max (4.14)
where d represents the distance from the neighboring node to the node suffering the local minimum problem, r the transmission range and T max the maximum delay affected to a contention timer.

The concentric coronas and the contention delay computed by Eq. (4.12) compared to Kalosha allows that:

1. Nodes located in CSA i broadcast their CT F messages before the nodes in CSA j where i < j.

2. All nodes located in the same CSA i and eventually at the same distance to S in Eq. ( 4.12) guarantees that nodes choose different times to transmit.

It has been proved that face traversal on a planar subgraph for the recovery mode of a geographic routing protocol is loop free and guarantees the packet delivery [Bose 01]. However, the planar subgraph construction requires a complete knowledge of the neighborhood via the beacon exchanges. In contrast, BFP reduces the number of messages exchanged using the selection and the protest phases where the former aims to construct a planar subgraph and the latter generate messages to remove falsely selected neighbors from the planar subgraph.

In this work, the BFP algorithm of [ Kalosha 08] is not explained in detail. Instead, an example is presented to illustrate the process in Fig. 4.6 and Fig. 4.7. Let's consider a scenario where the source S is surrounded by six neighbors which respond in the order: F 1 , F 4 , and F 5 according to their timers defined by (4.12). F 2 receives the CTF message from F 1 and becomes a hidden node, F 3 receives the CTF from F 4 , and F 6 receives the CTF from F 5 . Thus, the hidden nodes are F 2 , F 3 and F 6 . F 2 is located in the proximity region (Gabriel Graph) of F 1 and F 3 in the proximity region of F 4 . So, in the protest phase, F 2 protests against F 1 and F 3 protests F 4 . Thus, S removes the links with violating nodes (node in the proximity region of a node) and obtains a planar subgraph that will be used by the face routing algorithm to find the next forwarding node.

MAC-PHY Cross-Layered Relay Selection

Relay selection criterion based on geographical information

A relay selection criterion based on geographical information, where the best relay is determined according to a distance-dependent metric m i that softly combines the source-relay and relay-destination distances on each candidate relay is determined. The relay selection criterion for each cooperative hop can be expressed as follows,

m i = arg min i∈{1,2,...,N } A 2 d p S,R i + Bd p R i ,F , (4.15)
where d S,R i and d R i ,F are the distances between the current source and the i-th relay and between the i-th relay and the next hop, respectively and A and B are modulation dependent constants that satisfies equations (4.9) and (4.10). We note that the best relay selected by the above criterion is the one that provides the best source-relay-forwarder cooperative link in terms of average SER at the next hop.

Geographic contention-based relay selection

The distributed relay selection is based on nodes geographical information and a contention process. First, each relay acquires two relative distances d S,R i and d R i ,F to calculate its own selection metric according to (4.15). Here the path loss exponent is assumed as a known parameter. For the purpose of decentralization, the relay selection metric m i is encoded in time difference inside a timer-based election scheme. The election process starts as soon as each candidate relay overhears the DATA/CTF packets. Each candidate relay sets its timer proportional to the selection metric. Once a candidate whose timer expiration happens first, it relays the data packet to F , and the others candidates cancel their timers after receiving the packet. This contention-based relay selection scheme, which provides a distributed and efficient way to determine the best relay for each cooperative hop, answers a major question about cooperative MAC design, i.e., whom to cooperate with and how to do selection? The metric defined in (4.16) indicates the cooperative link quality in terms of average point-to-point SER, depending on the modulation type and the locations of nodes. x S , x F , and x i denote the locations of the current source, the forwarder, and the i-th candidate relay, respectively.

In addition, we define f as a mapping function that maps a candidate relay's location into its relay selection metric (x S and x F are fixed), as in (4.17). Let x * be the best placement of a relay, which minimizes the average point-to-point SER. The optimal point x * can be obtained by solving the optimization problem (4.18). Thus, the best relay is the one whose metric is closest to f (x * ).

m i A 2 d p S,R i + Bd p R i ,F , i = 1, 2, . . . , N, (4.16
)

f (x i ) = A 2 x i -x S p + B x i -x F p (4.17) minimize f (x i ) = A 2 x -x S p + B x -x F p (4.18) x * = A 2 x S + Bx F A 2 + B (as p = 2) (4.19)
A mapping function M, which scales our metric function f into the interval [0, 1] is used, where x max is a point in the set:

M(f (x)) = f (x) -f (x * ) f (x max ) -f (x * ) (4.20)
Finally, as for the CBF timers, we use the following equation to allocate the time to each node in the contention-based Relay selection scheme (CBR).

T CBR = T max M(f (x)) + rand 2T max N SA (4.21)

Relay selection area

The CoopGeo relay selection process do not use control messages as in the forwarding selection process so as to guarantee that only one node has been selected as relay, and thus, avoid message duplications or collisions. Besides overhearing the relayed message that triggers the contention timers suppression of the other candidate nodes, we have considered the relay area size as a way to control these issues. Since the candidates should reside in a defined area where relay selection is executed, the relay area is determined by the source and forwarder nodes positions. In Fig. 4.8(a) and 4.8(b), two relay areas are depicted. First, let the set C represent the potential relay nodes situated at the relay area formed by the intersection of the source and forwarder node coverage areas. Second, let the set D represent a relay area shaped by a Reuleaux triangle from the source node point of view. In the first case, for any relay candidate x i ∈ C, its selection metric is mapped onto this set, where M(f

(x i )) ∈ [0, 1].
For the Reuleaux triangle, any relay x i and any other possible relay x j have the following relationship: x ix j 2 ≤ r, ∀x i , x j ∈ D, i = j where r is the transmission range of a node. Hence, from the relay areas depicted in the figure, the Reuleaux triangle area is the best suited to be used since all relay candidates can hear each other, and accordingly, the hidden relay problem can be effectively avoided which is not the case of the intersection relay area.

CoopGeo in Action

This section depicts the behavior of nodes running CoopGeo (cf. Fig. 4.9) when a data transmission between a source and a destination is performed.

When the source node S intends to transmit its data to a node D, it checks if the channel is free for a predefined time interval. If this is the case, S broadcast its DATA and starts a T S1 timer. The neighbors of the source node receive the packet, store it and set up their T CBF timers as defined in Eq. (4.12) so as to participate in the forwarding selection process.

The neighbor F ∈ F i whose timer expires first sends a CTF control message to claim the forwarding status, then, it initializes a TF1 timer. The other candidates hearing this control message quit the forwarding selection process.

The DATA/CTF handshake carried out by S and F is used to initiate the relay cooperation on demand if it is needed, since within the CTF message, F activates a flag to indicate if relay cooperation is needed in case of error decoding. In this way, the neighbors situated at the relay region formed by S and F that successfully decoded the DATA previously sent by S start their T CBR timers as defined in Eq. (4.21), so as to participate in the relay selection process.

When S receives the CTF message, it replies with a SELECT message which confirms the forwarding status to F , and updates its T S1 timer to the maximum delay time allowed to receive an ACK from F . Meanwhile, the relay candidates Consequently, the forwarder node combines the received signals from S and R, decodes the data, and stops its T F 1 timer. Then, it sends an acknowledgment to S and continues the CoopGeo execution toward D.

In addition to T CBF and T CBR timers, two other timers were used: T S1 at the source and T F 1 at forwarder node. At the beginning T S1 represents, the maximum allowed time to find a forwarder node in the direction of D, given by

T S1 = T DAT A + T CT F + T max (4.22)
Where T DAT A and T CT F represent the data and CTF packet transmission times respectively, and, T max represents the maximum time interval allowed to the forwarding selection process. For simplicity, in the equation, we do not express the propagation delay.

Since the DATA/CTF handshake represents that a forwarder node F was selected, T S1 is updated to a value that represents the maximum delay time allowed to receive an acknowledgement from F and it depends on whether relay cooperation is executed. The updated timer is given by

T S1 = T SEL + T ACK if no cooperation is needed T SEL + T max + T DAT A + T ACK otherwise (4.23)
where the first statement includes the transmission time of the SELECT (from S to F ) and ACK (from F to S) messages; the second statement includes the required time of the first statement as well as T max and T DAT A which correspond to the maximum allowed time for the relay selection and the time needed to relay the packet.

For T F 1 , the affected value depends on whether the forwarder F correctly decodes the received data from S, or relay cooperation is executed. For the former, F listens to the channel and waits for a SELECT message from S, which completes the direct communication mode; for the latter, F waits for the SELECT message and DATA relayed, from the source and the relay node, respectively.

T F 1 = T CT F + T SEL if no cooperation is needed T CT F + T SEL + T max + T DAT A otherwise (4.24)
where the first statement allocates to T F 1 the time required to transmit the CTF message and the time required to receive a SELECT message from S respectively; the second statement adds to the first statement, the maximum allowed time to select a relay node and the time the relay node needs to send the relayed data, respectively. Similar to T S1 timer, T F 1 does not consider the propagation delay.

If the timer T S1 of S expires before receiving a CTF or an ACK from F , we have different possibilities: 1) S could not find a forwarder; 2) F could not receive the SELECT message from S 3) F could fail; 4) F could not receive the data packet from R in the cooperative mode. For all these situations, the CoopGeo protocol is restarted.

Thus, we can see that the two most significant timers are T CBF and T CBR , which are used to select a forwarder F and an optimal relay R in each hop through contention mechanisms. The timers T S1 and T F 1 just helps to detect a problem during the CoopGeo execution.

Performance Evaluation

First a single-hop cooperative relay network with N = 5 available relays, deployed in R 2 is considered. The source and the destination are located at the coordinates of (0, 0) and (1, 0) respectively, and randomly place the relays at the location displayed in the column (A) of Table 4.1. It is assumed that the channel variances between any two nodes follow σ 2 i,j ∝ d -p i,j , where p is the path loss exponent and is taken to be p = 3 in the simulations. The channel variance is normalized to unity per unit distance. QPSK modulation is used in this simulation and the fading channels are assumed sufficiently fast-varying such that the channel coefficients keep constant only within every symbol interval. From the column (A) of Table 4.1, the distances from each relay to the source and the destination can be determined, which are known at the source, then the corresponding selection metric for each relay can be determined by using (4.15), given in the column (B) of Table 4.1. According to the selection criterion introduced in Section III, R 5 turns out to be the best relay selection since it has the minimum selection metric. Fig. 4.10 depicts the SER versus SNR performance of the above scenario, where SNR is defined as P/N 0 , and P is the total transmitted power fixed in each case. In Fig. 4.10, the performance of direct transmission from the source to the destination is provided as a benchmark for a non-cooperation scheme. Fig. 4.10 shows that R 5 is the best relay since it contributes to the minimum SER at the destination. Moreover, Fig. 4.10 also reveals that the worse relay (leading to the worse SER performance) corresponds to the larger selection metric in the column (B) of Table 4.1. In other words, the simulation results are consistent with the proposed relay selection, that is, the smaller the selection metrics, the better the resulting SER performance. Thus, it has been demonstrated that by utilizing the geographical information, nodes in cooperative networks can efficiently perform relay selection to improve the SER performance at the destination. In addition, the performance is also compared to a relay selection approach, named random relay selection, which means that the source randomly selects a cooperating relay without any information for each transmission. As Fig. 4.10 depicts, the performance curve of the random selection scheme lies between the best and the worst selection. This is because each relay has the same opportunities to be selected so that the performance will be averaged over all the distributed relays.

The next step in the simulation methodology is to evaluate the PHY/MAC layer performance of CoopGeo with Monte-Carlo simulations implemented in Matlab code. The three lower layer processes were simulated, a summary of the simulation settings could be found in table 4.2. The results are based on 20,000 random generated topologies where all the stations are competing to access the channel. It starts by solving the two subproblems stated in section 4.2, and once the forwarder and relay node sets are obtained, they are used to evaluate the packet error rate, the average transmission probability, the saturated throughput, and some other results varying the input parameters.

Packet Error Rate (PER)

To analyze the PER, CoopGeo and BOSS were simulated with different T max values. Starting from T max = 100µs until T max = 1000µs, see the results in Figs.

4.11(a) 4.11(b).

The two plots allow to have a global visualization of the protocols behavior with respect to the PER. From these results, the setting when CoopGeo works with T max = 500µs is chosen as this is the value that presents a good tradeoff between the PER and the delay needed to choose the forwarding and relay nodes. So, Fig. 4.12 shows the average Packet Error Rate of two different protocols, one is for CoopGeo using a cooperative relaying technique and the other 4.12 includes both the probability of collision inside different contention periods and the probability of error over the wireless channel.

It is shown that CoopGeo experienced a lower error rate of 2.5 times less than the traditional geographic based routing protocol in the best circumstances. We also notice that the error rate of the two protocols gets closer to each other as a function of the increased number of nodes in the neighborhood. This error rate is a function of the number of nodes and is induced by the collision probability inside the different contention periods.

Transmission Error Probability

To calculate the error rate during a transmission, the same way as the previous analysis, CoopGeo was simulated with different values for T max = 100...1000 µs. These simulation can be observed in Figs. 4.13(a) 4.13(b).

Therefore, in Fig. 4.14, it is shown that the average probability of having an error in the transmission is clearly better in the cooperative case and the rate is even decreasing as the number of stations present inside the neighborhood grows. This behavior is due to the accurate selection of the relay node when more nodes are present in the neighborhood. It is also noticed that CoopGeo experiments a very low transmission error rate that enable us to raise the constellation size of the modulation scheme, in order to improve the bandwidth efficiency without loosing end to end throughput.

Varying the contention window T max

In this test, the impact of the contention window size T max is investigated (it controls the delay affected to a contending node when it tries to forward/relay

CTF-Relayed message Collision Probability

In Fig. 4.15 the collision probability suffered by contending nodes is analyzed when sending their Contention to Forward and relayed messages according to the T max size. The sizes from 500µs to 1000µs are the best suited to be used by CoopGeo, as the collision probability is similar and stay low in comparison the other intervals. Then, it was analyzed the relationship between the normalized throughput with cooperative communications vs the CTF-Relayed messages collision probability and observe that we may use a smaller T max size without affecting the performance of the protocol provided that the number of contending nodes be fewer for the case T max = 300µs (cf. Fig. 4.19). If take T max = 500µs from the previous result as reference, it can be seen that for a smaller saturated throughput rate with respect to T max = 300µs we may handle more dense scenarios.

Varying the constellation size

Finally, a series of tests were realized. The constellation sizes of the protocol (see Figs 4.16 and 4.17) were varied. Fig. 4.18 resumes the previous results in one figure , showing the saturated throughput of (NWK/MAC/PHY) CoopGeo and compare it with a traditional geographic NWK/MAC approach such as BOSS. It is shown that CoopGeo outperforms the classical scheme in terms of saturated throughput, using for this case, different order of the M-Quadrature Amplitude Modulation (MQAM). Due to very low transmission error rate in the case the cooperative scheme, we are able to raise the size the of constellation with respect to the transmission environment without deteriorating the end to throughput.

Discussion and conclusions

In this chapter, a cross-layer protocol, CoopGeo has been presented, based on geographic information to effectively integrate the network/MAC/physical layers for cooperative wireless sensor networks. The proposed CoopGeo provides a joint MAC/routing protocol for forwarder selection as well as a joint MAC/physical protocol for relay selection. Both selection methods, are based on geographical information of the nodes, this information is embedded in their metrics which participate in a contention-based mechanism. Simulation results demonstrate that the proposed CoopGeo can work with different densities and achieve better system performances than the existing protocol like BOSS, in terms of packet error rate, transmission error probability, and saturated throughput. Due to the fact that the forwarder and relay selections take place at the MAC layer, CoopGeo is not only reliable and resilient to any change in the network topology, but also scalable since both decisions are local. Chapter 5

RACR: Relay-Aware Cooperative Routing

In chapter 2 it was stated that cooperative communications for wireless networks has been extensively investigated from the physical layer, later, in chapter 4, a crosslayer framework that provides reliability in terms of packet delivery guaranteed and a better bandwidth utilization in terms of throughput was presented. Now, the goal of this chapter is to design an efficient wireless system able to control the resource consumption. To tackle this goal, a second contribution is presented, a cooperative geographic routing protocol with cross-layer design, named, the Relay-Aware Cooperative Routing (RACR) protocol, which exploits the coverage extension property as a result from node cooperation. The RACR protocol enables a forwarding node offering a certain symbol error rate (SER) to participate in the routing process by means of a local route decision that is based on a previous relay selection with the purpose of providing the maximum coverage extension toward the destination. During the RACR design, two questions are answered, where the relay node should be positioned with respect to the physical environment? and, how the coverage extension helps a transmission to be energy efficient? The performance evaluation shows that RACR achieves a nearly half reduction in the average path length in dense sensor networks compared to the non-cooperative geographic routing.

Introduction

In wireless sensor networks, developing efficient and scalable routing protocols is one of the challenging tasks that require significant study due to their inherent nature such as the infrastructure absence and the high dynamics (see chapter 2 for details). Geographic routing, relying on the knowledge of geographic location information of nodes to make local route decisions, emerged as one of the most suitable routing solutions in this context. A large number of geographic routing protocols have been proposed according to different concerns, such as energy consumption, delay time, overhead expense, quality of service (QoS), and network lifetime, etc., and yet these protocols are based on the premise of using direct point-to-point communication (direct communication strategy) at the physical layer.

The previous chapter emphasized the spatial diversity property derived from node cooperation [Laneman 04, Ochiai 05, Sadek 07, Zhong 09, Wang 09a, Vardhe 10] at the physical layer and the lack of interaction with the network and MAC layers.

In addition to this spatial diversity gain from cooperative communication, there is also a potential advantage in terms of coverage extension, which is associated with the link layer connectivity and, hence, affects the routing design and performance at the network layer. However, this is ignored by most existing studies. There is very little insight into the impact of physical-layer cooperation on the network-layer routing design and performance.

Most of the existing cooperative routing solutions are realized either by finding a route first in a traditional manner and then use cooperative transmission to enhance the link quality along the established route or by building the minimumpower route that applies a cooperation scheme to save the required transmission power. Nevertheless, these cooperative routing solutions do not take advantage of coverage extension of physical-layer node cooperation, since the cooperative route with coverage extension may be radically different from previous ones.

In considering the demands for high efficiency and scalability in multihop routing as well as the potential benefit of coverage extension from cooperative transmission, we investigate how the traditional non-cooperative geographic routing, say Greedy Forwarding (GF), can be improved by incorporating the cooperative transmission into the design. In particular, we define the radio coverage based on the SER requirement to identify the coverage extension due to cooperation. Furthermore, the cooperative geographic routing problem for SER-constrained multihop sensor networks is addressed. The proposed routing protocol, named Relay-Aware Cooperative Routing (RACR), enables a node to make a local route decision depending on the geographic location of a relay while this relay is selected with the purpose of providing the maximum coverage extension toward the destination. Simulation results show that in comparison with the non-cooperative GF protocol, the proposed RACR protocol improves significantly the routing performance in terms of the average path length and thus, its stretch factor.

System Model

In this section, the signal, channel, and network models for our cooperationbased routing scheme are described. Then, the cooperative greedy routing problem is formulated.

Signal Model

In the following, we introduce the signaling strategies under the direct and cooperative transmission. To do this, Fig. 5.1 depicts an example of how cooperative transmission leads to a radio coverage extension. We assume that each network node has the same direct radio range. At the first hop, node S can communicate with its neighboring nodes R 1 , R 2 , and R 3 that are within its direct radio range; however, none of them can communicate directly with node D, since D is outside their direct coverage. As exploiting cooperative transmission, D can receive independent symbol copies from different locations, creating thus, a spatial diversity that mitigate the fading effect. Therefore, in this scenario D can be reached due to the extended coverage using cooperative transmission.

Cooperative Transmission

For the cooperative transmission, a modified version of the three-node decodeand-forward (DF) signaling scheme is considered as proposed in [ Laneman 04]. The scheme is set up by a sender S, a relay R, and a receiver D (see Fig. 5.1 here the relay node R is represented as R 1 ), where each node has a single antenna and can only either transmit or receive in the current time slot. In the first phase, S broadcasts its symbol x, while both the receiver and relay receive noisy versions of x. The received symbols at D and R can be respectively modeled as

y S,D = P C 1 h S,D x + n S,D , (5.1)
y S,R = P C 1 h S,R x + n S,R , (5.2)
where P C 1 is the transmission power of S under the cooperative mode, h S,D and h S,R are the channel coefficients from S to D and R respectively, x is the transmitted symbol with unit average power, and both n S,D and n S,R are the noise terms. In the second phase, R decodes the received symbol and then decides whether to relay it. We assume that R correctly decodes the received symbol as long as the received signal-to-noise ratio (SNR) is greater than a certain threshold. In this case, R performs relaying; otherwise, it remains idle. The received symbol at D can be written as

y R,D = P C 2 h R,D x + n R,D , (5.3)
where P C 2 is the transmission power of R under the cooperative mode, h R,D is the channel coefficient from R to D, and n R,D is the noise term. At last, D linearly combines the received symbols from the two different paths, i.e., y S,D and y R,D , and performs the maximum likelihood (ML) detection. To gain the maximum SNR at the symbol combining output, we consider that D applies the maximum ratio combining (MRC) technique [ Brennan 03].

Direct Transmission

For the direct transmission between S and D, the received symbol at D can be expressed as

y S,D = √ P D h S,D x + n S,D , (5.4)
where P D is the transmission power of S under the direct mode.

Channel Model

In this work, large-scale fading and small-scale fading, along with additive noise, are considered for the channel modeling. Given a transmitter-receiver pair (i, j), the channel from i to j is modeled as a frequency-flat fading channel with stationary and ergodic time-varying channel coefficient h i,j . It is assumed that the channel gain |h i,j | follows a Rayleigh distribution with variance σ 2 i,j , that is, h i,j ∼ CN (0, σ 2 i,j ). Moreover, the channel gain variance is modeled using a σ 2 i,j ∝ d -α i,j log-distance path loss model [Sadek 07, Li 06, Wang 09b], where α is the path loss exponent and d i,j is the distance between i and j. It is also assumed that h i,j is independent of the channel input and is constant over a symbol duration, and h i,j may change from a symbol to another as an i.i.d. random process. Regarding the additive noise term n i,j , assuming n i,j as a circularly symmetric zero-mean complex Gaussian random variable with variance N 0 , written as n i,j ∼ CN (0, N 0 ).

Theoretical Average SER Performances

In the following, the theoretical average SER performances for the direct and cooperative transmission schemes are given as described above with the widely used M -QAM modulation.

Average SER under Direct Transmission

As shown in [ Simon 98], for direct transmission the average SER performance of M -QAM over frequency-flat Rayleigh fading channels can be obtained by the following closed-form result:

P D SER (γ) = 2K(1 -g(γ)) + K 2 4 π g(γ) tan -1 g -1 (γ) -1 , (5.5)
where

K = 1 -1 √ M , g(γ) = 1 + 2(M -1) 3γ -2
, and γ = P D σ 2 N 0 is the average received SNR per symbol.

Average SER under DF Cooperative Transmission

The average SER performance under the DF signaling strategy with M -QAM modulation over frequency-flat Rayleigh fading channels has been analyzed in [ Sadek 08], which provides both the exact and approximate average SER expressions as follows. The exact close-form SER is given by

P C SER (γ S,D , γS,R , γR,D ) = F 1 + bγ S,D sin 2 θ F 1 + bγ S,R sin 2 θ + F 1 + bγ S,D sin 2 θ 1 + bγ R,D sin 2 θ 1 -F 1 + bγ S,R sin 2 θ , (5.6)
where

F x(θ) = 4K π π/2 0 x -1 (θ)dθ -4K 2 π π/4 0
x -1 (θ) dθ, b = 3/2(M -1), and γS,D = P C 1 σ 2 S,D /N 0 represents the average received SNR per symbol at node D from node S; similarly, γS,R = P C 1 σ 2 S,R /N 0 and γR,D = P C 2 σ 2 R,D /N 0 . Furthermore, for sufficiently high SNR, (5.6) can be tightly approximated as

P C SER (γ S,D , γS,R , γR,D ) ≈ 1 b 2 γS,D A 2 γS,R + B γR,D , (5.7)
where

A = M -1 2M + (1 -1/ √ M ) 2 π , B = 3(M -1) 8M + (1 -1/ M ) 2 π .
(5.8)

Network Model

During this chapter, a multihop wireless sensor network is considered. It is modeled as a 2-dimensional graph G = (V, E), where V is the set of randomly distributed homogeneous nodes, with |V | = N , and E is the set of communication links between nodes (i, j) for i, j ∈ V . For any two nodes i, j ∈ V , an edge exists if the transmission from i is received by j with an SNR greater than a required threshold. A single session in the network is consided, where data delivery may cross over multiple hops. Thus, in the node set V , two subsets of nodes are included within it: (i) the set of a source-destination pair, V sd = {s, d}, with |V sd | = 2, (ii) the set of available nodes, V a = {a 1 , a 2 , . . . , a Na } with |V a | = N a , some of them may serve as intermediate nodes. For clarity, the roles of an intermediate node in the network are specified as follows. An intermediate node is an active one that helps deliver data toward destination. More specifically, based on different purposes of data delivering, an intermediate node has two major roles-either a relay node or a forwarding node-an intermediate node is called a relay node (e.g., node a in Fig. 5.2) if it is used for cooperative relaying; otherwise, it is called a forwarding node or forwarder (e.g., node b in Fig. 5.2) if used in the traditional multihop sense. Fig. 5.2 depicts a cooperative geographic routing scheme for multihop wireless sensor networks. The multihop routing of interest is realized by a sequence of cooperative hops that apply the three-node cooperation scheme. As stated above, nodes a, b, and c are the intermediate nodes for the source-destination pair (s, d), where node b serves as a forwarder and both nodes a and c serve as relays. Fig. 5.2 also shows that in comparison with the conventional non-cooperative routing, cooperative routing can significantly reduce the number of hops due to the benefit of coverage extension, leading to more efficient communication.

The network model consider the following assumptions: (i) every node knows its own geographic location, (ii) the location of the destination is known at the source, and (iii) every transmit node uses identical transmission power. The power allocation across the sender and relay as well as the power adjustment of each node for topology control complicates the cooperative geographic routing problem. For simplicity, an equal power strategy is considered, giving

P C 1 = P C 2 = P D 2 .

SER-Based Radio Coverage Formulation

To identify the coverage extension due to cooperation, a new mathematical expression for radio coverage has been developed and it is somehow different from the previous notion. To do so, the network graph G = (V, E) is mapped into a 2-dimensional geographic plane, where all nodes can be characterized by their geographic location and give the following definitions.

Definition 1: The SER-guaranteed radio coverage R ⊂ R 2 of a transmitting side t is defined as a geographic area within which any receive node can meet certain SER requirement. Formally,

R = x ∈ R 2 |P SER (x t , x) ζ 0 , (5.9)
where x t and x denote the geographic locations of the transmitting side and receiver, respectively, P SER is the average SER at the receiver as a function of locations of both the transmitting side and receiver, and ζ 0 is the required average SER at the receiver. Note that: (i) the transmitting side t can be a single transmit node using direct transmission or a set of cooperating nodes using cooperative transmission, (ii) given a communication model, the SER requirement ζ 0 translates to a minimum received SNR throughout the radio coverage, (iii) there are other metrics that could be employed to specify the radio coverage, such as average bit error rate, outage probability, SNR, etc. These metrics all lead to this definition; nevertheless, to make the presentation clear we do not try to take into account all of these metrics in the formulation but focus on the average SER, and (iv) throughout this chapter we use the term radio coverage to represent the notion of the SER-guaranteed radio coverage.

From Definition 1, it can be derived and defined the direct and cooperative radio coverage as follows.

Definition 2: The direct radio coverage of a transmit node u with transmission power P D > 0 is defined as follows:

R D = x ∈ R 2 |P D SER (x u , x) ζ 0 . (5.10)
For direct transmission, the radio coverage contour forms a circle with a radius r D around the sender because the path loss, modeled as a distance-dependent term in Section 5.2.2, is the same at a uniform distance from the sender. The Fig. 5.2 shows the contour of direct radio coverage based on a fixed transmit power at the node s. Definition 3: Based on the log-distance path loss model as described in Section 5.2.2, the average received SNR can be defined as a distance-dependent term:

γ(d i,j ) = P D σ 2 i,j N 0 = P D N 0 d α i,j (5.11)
From Definitions 2 and 3, the direct radio coverage of node u can be written in a disk form, i.e., R D = D(x u , r D ), (5.12) where x u is the center of the disk and r D is the radius expressed by

r D = P D N 0 γ0 1 α , (5.13)
where γ0 is the required minimum received average SNR to meet the average SER requirement ζ 0 . Consider the direct transmission model as introduced in Section 5.2.1, given a required average SER ζ 0 the corresponding γ0 can be obtained via (5.5). In addition, in this chapter the radius r D is used to specify neighbors within the direct coverage for a given node u. Similarly, the neighbors within the cooperative coverage are specified by r C . Definition 4: Given a transmit node u that cooperates with a given set of relays V r = {r 1 , r 2 , . . . , r Nr }, the cooperative radio coverage of the transmit node u with respect to the relay set V r is defined as:

R C = x ∈ R 2 |P C SER (x u , x Vr , x) ζ 0 , x r i ∈ R D , for i = 1, 2, . . . , N r . (5.14)
Here it is noted that the cooperating relays are confined to the direct radio coverage of node u. In other words, the cooperating relays have to be one-hop neighbors of node u. Definition 5: Consider a transmit node u with a set of relays V r = {r 1 , r 2 , . . . , r Nr } that can be located at any places within R D , the maximum cooperative radio coverage of the transmit node u is defined as:

R C max = x ∈ R 2 |P C SER (x u , x Vr , x) ζ 0 , ∀ x r i ∈ R D , for i = 1, 2, . . . , N r . (5.15)
By definitions, it can be seen that R C is a subset of R C max , and R C max and is a disk centered at the location of the sender u due to the symmetry of path loss in space. In addition, consider the three-node (s, r, f ) cooperation model as introduced in Section 5.2.1, if we set P C 1 = P C 2 = P , since the optimal position of the relay is on the line segment between the sender and receiver and it approaches toward the middle point of the line segment with increasing the path loss exponent [Wang 09b], it can be shown that

R C max ≈ D(x s , r C max ), (5.16)
where r C max denotes the radius of the maximum cooperative radio coverage and can be expressed as

r C max = b 2 P 2 ζ 0 N 2 0 A 2 k α + B(1 -k) α 1 2α , (5.17)
where b, A, and B are modulation-dependent constants as given in Section 5.2.3, k is a ratio defined by k

x * r -xs

x f -xs , and x * r is denoted as the optimal relaying position (on which the relay provides the maximum coverage extension toward the destination), depending on the path loss exponent α. The calculation of the value k refers to [Wang 09b]. Thus, by denoting x * f as the optimal forwarding position (on which the forwarder provides the largest progress over the maximum cooperative radio coverage toward the destination), the optimal relaying position can be represented as x * r = k x * fx s +x s . Fig. 5.4 gives an illustration of the optimal relaying and forwarding positions as well as the direct and the maximum cooperative transmission radii.

RACR: Relay-Aware Cooperative Routing

In this section, the RACR protocol is presented. It is a cross-layer cooperative routing solution based on a beaconless geographic protocol [Sanchez 09], involving the forwarder and relay selections [ Aguilar 10]. The RACR protocol takes the advantage of coverage extension using the three-node cooperation to select next hops in a greedy manner. As such, the required number of hops for given a source-destination pair can be reduced as compared to non-cooperative geographic routing. The derived radio coverage formulas for direct and cooperative transmission schemes as well as the optimal positions for relaying and forwarding are employed in this protocol. Typically, geographic routing protocols have two operation modes: greedy and recovery routing modes. However, in this chapter we focus on the design of greedy routing. The recovery routing operation is not further discussed.

Conceptually, the RACR architecture (see Fig 5 .3) is realized through a twophase selection process. The first phase is to select the best relay such that the source-relay cooperating pair provides the maximum coverage extension toward the destination, whereas the second phase is to select the forwarder with the largest progress toward the destination. Both the relay and forwarder selections are based on a distributed contention process without periodic exchange of control messages (i.e., beacons) for acquiring neighbors' location information. During the contention process, candidate nodes compete for being a relay or forwarder by setting contention timers relevant to their geographic location.

Given a source-destination pair in the SER-constrained network, the RACR protocol works as follows. First, the source initiates the two-phase selection process by broadcasting its message to its direct and cooperative neighbors. The direct neighbors decode the message, while the cooperative neighbors hold this message and wait for a relay's message to perform the maximum ratio combining (MRC). Second, the direct neighbors being able to decode correctly compete for becoming the relay by setting their contention timers as

T relay ∈ [0, T max ],
where T max is the maximum delay time allowed for waiting for a relay node. The contention timers for relay selection are defined so that candidates located closer to the optimal relaying position x * r answer first. Third, the winning relay transmits its message to its cooperative coverage neighbors, and nodes overhearing this message cancel their timers. Among the cooperative neighbors, nodes that can decode correctly the original message using MRC participate the contentionbased forwarder selection process by setting timers as T f wd ∈ [0, T max ]. The timer setting for forwarder selection is to let candidates located closer to the optimal forwarding position x * f answer first. Forth, once the forwarder comes out, it broadcasts an acknowledgement (ACK) to the source to indicate a correct message reception, while overhearing nodes cancel their timers. Finally, the forwarder acts as the source node and repeats the same steps until the message reaches the destination. In the following we describe how we set the contention timers for relay and forwarder selections, respectively.

Contention Timer Setting for Relay Selection

Since the best relay should be as close to the optimal relaying position x * r as possible (see Fig.

M r = x r i -x * r r D + x s -x * r , (5.18)
where x r i denotes the location of the candidate r i and the denominator represents the farthest distance between a possible candidate's and optimal relaying positions. Finally, we set the relay-selection contention timer for each candidate by

T relay = (N r -1) N r T max × M r + rand T max N r , (5.19)
where N r is the number of groups to be divided in the relaying area and rand(x) is a function obtaining a random value between 0 and x to reduce the collision probability.

Contention Timer Setting for Forwarder Selection

To select the forwarder with the largest progress over the cooperative radio coverage toward the destination, each candidate's contention timer would be proportional to the distance between itself and the optimal forwarding position. To do so, a projection point x m i from the selected relay x r i onto the source-destination line is defined, as depicted in Fig. 5.4, and θ is given by θ = arcsin . Given that the coordinates x s , x * r , and x d are known by each current node and that each possible relay knows its own x m i position, each candidate forwarder can derive the optimal forwarding position x * f and set its corresponding timer T f wd . The forwarder selection metric M f is defined as

M f = x f i -x * f (r D ) 2 + x m i -x * f 2 , (5.20)
where

x m i -x * f = r C max -x s -x m i .
Finally, we set the forwarder-selection contention timer for each candidate by

T f wd = (N f -1) N f T max × M f + rand T max N f , (5.21)
where N f is the number of groups to be divided in the forwarding area. Given given a source node at (0,0), a destination node (0, 300) for r C max = 180m and r D = 110m. The optimal relay position is calculated, the nearest relay node Xr i selected at (30, 80), then the optimal forwarding position Xf * is computed.

Performance Evaluation

In this section, extensive simulations were realized to evaluate the RACR protocol performance, to do so, first it was needed to respond to a question related to the relay selection. Should the relay be chosen as far as possible from the source node? The answer to this question gives some elements to understand the relationship between the direct coverage definition, the path loss environment and the modulation scheme when defining the optimum relay location. Then, the coverage extension benefits using a basic cooperation system were analyzed, and finally, it was determined how the coverage extension benefits from the RACR routing performance in terms of energy efficiency.

Should we choose the relay as far as possible from the source?

To answer this question, some simulations were realized and it was found that it is almost true that the relay node should be as far as possible from the source, but the position is influenced by the path loss exponent and the modulation type used by the system. It was noted that even if the relay selection tries to get closer to the destination node, RACR establishes that, to maintain a sensor network with a SER guaranteed, the relay should be located inside the direct coverage area. Thus, this important information should be taken into consideration when defining the optimal relay position at the first phase of the RACR protocol. Fig. 5.6 depicts how the optimal relay position may change as function of the path loss exponent. Some simulation were effectuated where the SER requirement ζ 0 is assumed to be 10 -2 , the total transmit power for both the direct and cooperative schemes is P = 15 dBm, the average noise power is N 0 = -70 dBm, the modulation type fixed to 16-QAM, and, the path loss exponent was varied α = {2, 3, 3.89, 4}. From this simulations, it was observed that in order to maintain the SER requirement, the relay candidates should be inside r D . If in any case, the optimum relay position is located outside the r D disk, the point should be displaced to the nearest point within the direct coverage area. The simulations showed that the critical point, that is, the location that provides a better progress towards the destination is found when alpha corresponds to 3.89.

Coverage Extension

Then some theoretical results are presented to examine the coverage extension from the basic three-node cooperation model using a modified decode-and-forward strategy over Rayleigh fading channels. The SER requirement ζ 0 is 10 -2 , the total transmit power for both the direct and cooperative schemes is P = 15 dBm, the average noise power is N 0 = -70 dBm, the path loss exponent is α = 4, and the modulation type from 4-QAM to 64-QAM. The RACR cooperative scheme is compared with the direct scheme in terms of the largest progress toward the destination at (0, ∞). For a fair comparison, the power allocation is set to P C 1 = P C 2 = P D 2 , i.e., the total transmit power of the source and relay in the cooperative scheme is the same as used in the direct scheme. Fig. 5.7 and 5.8 depict the increase of radio coverage as a function of the relay node placed between the source (0, 0) and the forwarder (0, 1) with a normalized distance. It is shown that the best relaying position is found at the midpoint between S and D, providing about 80% and 90% coverage extension toward the destination.

Routing performance

Next the numerical results are used to evaluate the routing performance of the RACR protocol. The simulation setting are given in Table 5.1. 100 network topologies were generated where the nodes are randomly deployed within a 1000×1000 m 2 field. For each topology, 750 source-destination random pairs were selected. The simulation results are averaged over the 100×750 simulation runs. To demonstrate how the proposed RACR protocol improves the non-cooperative geographic routing, the energy efficiency was considered as the metric, by measuring the number of hops for the RACR and non-cooperative geographic greedy routing (or named greedy forwarding, termed as GF). In the RACR protocol, each hop is based on the three-node cooperation scheme. In non-cooperative greedy routing, each hop uses direct transmission scheme. As set in the previous simulation, each hop, whatever it is direct or cooperative, has the same total transmit power. Thus, the performance metric of the path length (i.e., the number of hops) translates to energy efficiency. Fig. 5.9(a) shows the performance of the average path length versus the average number of neighbors. It can be seen that the RACR protocol outperforms significantly the GF protocol due to the effect of coverage extension using cooperation. As considering the corresponding stretch factor, which is defined as the path length ratio, Fig. 5.9(b) represents that the RACR protocol achieves a nearly 50% reduction in average path length compared to the GF protocol. It demonstrates that the proposed RACR protocol is much more energy-efficient than the traditional non-cooperative geographic routing protocol.

Conclusions

In this chapter, the cooperative geographic routing problem for SER-constrained multihop sensor networks was addressed. It was analyzed the impact of physicallayer cooperation on the traditional geographic routing. For given a dense sensor network, with the knowledge of geographic location of nodes, the proposed RACR protocol selects the best relay that provides the maximum coverage extension toward the destination, and then selects the next hop in a greedy sense, depending on the cooperating relay's location. It is shown that the average path length reduction of up to nearly 50% is achievable in dense sensor networks with an SER requirement of 10 -2 at the destination.

Chapter 6

Conclusion and Future Directions

The main contribution of this thesis is the design and evaluation of a crosslayer, energy-efficient, local, routing framework able to cope with the wireless channel variations. To achieve this global contribution, we studied the Beaconless Geographic Routing protocols that build the route not only in a local manner, but also on the fly, and, the cooperative communications to exploit the broadcast nature of the wireless channel for Wireless Sensor Networks. During the design and evaluation of our contributions, a scenario of a sensor network with SER-level constraints to be satisfied was considered.

The research work was started by realizing an extensive survey of the current state-of-the-art of routing and cooperative communications approaches, how they work, their properties, assumptions and the models used. Subsequently, the requirements of our network scenario were studied, to understand how we could tackle them by means of a cross-layer system.

Afterwards, the initial intuition was to establish a starting point defined by a beaconless geographic routing strategy that later was used to add our contributions as complementary modules, and, build a cross-layer platform. During the development of this work, the cooperative communications were identified as an attractive and suitable mechanism to solve the isolated design in traditional layered sensor networks. Therefore, the result obtained is a cross-layer framework consisting of two routing modules named CoopGeo and RACR. Both protocols have their own properties and objectives to fulfill.

In the first part of the thesis, the reliability of wireless sensor networks was analyzed, in effect, many studies have shown that this kind of networks are vul-nerable to network and environment dynamics. This context may cause a loss in the delivery of packets and the poor use of network resources. Hence, in chapter 4, CoopGeo was proposed as a solution that allows an enhancement in packet delivery and the system performance, by means of a cross-layer framework. CoopGeo, consists of two joint cross-layer phases, a joint network-MAC phase for next hop selection and a joint MAC-physical phase for relay selection. In particular, both the routing and relay selection solutions in CoopGeo are based on geographic information using contention-based selection processes.

It was demonstrated by simulations that our contribution CoopGeo can work with different densities and achieve better system performances than the existing traditional geographic routing protocol, in terms of packet error rate, transmission error probability, and saturated throughput.

In the second part of the thesis, we were interested how cooperative communications using its coverage extension property can help a sensor network to be energy-efficient. In chapter 5, we proposed RACR protocol that takes the advantage of coverage extension using the three-node cooperation to select next hops in a greedy manner. RACR is realized through a two-phase selection process. The first phase is to select the best relay such that the source-relay cooperating pair provides the maximum coverage extension toward the destination, whereas the second phase is to select the forwarder with the largest progress toward the destination. Both the relay and forwarder selections are based on a distributed contention process without periodic exchange of control messages (i.e., beacons) for acquiring neighbors' location information.

I was also demonstrated by simulations that the required number of hops for a given source-destination pair can be reduced by almost a half in dense wireless sensor networks.

The results obtained from extensive evaluations of CoopGeo and RACR contributions, have demonstrated that both solutions are applicable to sensor networks in the presence of very variable channel environments. Therefore, we have proved that our cross-layer vision of the problem provided an integrated solution to problems like inefficient routing paths, congested medium access and lossy links.

Thus, given the satisfying results of this thesis, we believe that the crosslayer vision in wireless sensor networks using geographic routing protocols and cooperative communications proves to be a practical approach to tackle some problems presented in these networks.

Future directions

We are aware that this thesis establishes a platform where some other works may arise to extend or optimize it such as:

It would be interesting to build a physical testbed where our contributions were implemented and collect experimental data in order to have a more accurate performance evaluation. It would be interesting to adapt our contribution to a scenario where the sensor nodes were not assisted by GPS devices, in this context, a virtual coordinates system must be necessary. Although several research works about virtual coordinates have been presented in the recent years, most of them attack the problem from the network layer viewpoint. It would be interesting to propose a new concept using virtual coordinates that takes into consideration the wireless environment in a beaconless way or at least in a localized way.

We may also think to extend our contributions to include inexpensive and simple directional antennas that can be used to improve the network communication between the nodes of the network. Directional antennas when radiating the signal toward the receiver node may lead to a more efficient utilization of the power, concentrate the signal diffusion in a better link quality and also increase the transmission range.

In general, we can say that this thesis paves the way to further protocols and applications not only in sensors networks but also in other kind of ad hoc networks such that vehicular networks.

Annexe A. Resumé du manuscrit de thèse en français

Contrairement aux protocoles de routage géographiques traditionnelles, Co-opGeo est un protocole de routage "beaconless" basé sur une architecture intercouches où le routage est réalisé non seulement localement, mais aussi à la volé. De plus, les problèmes liés à la couche physique sont traités par les communications coopératives qui exploitent la nature de la diffusion sans fil.

Le protocole RACR exploite la propriété offerte par les communications coopératives : l'extension de la couverture radio. Cette propriété permet d'améliorer les performances d'un réseau que utilisé, à l'origine, un protocole de routage géographique traditionnel. RACR est une alternative aux scenarios dont l'objectif principal est de diminuer au maximum la consommation des resources du réseau et en même temps d'assurer que le réseau offre un taux d'erreur par symbole garanti (SER). Ainsi le protocole RACR permet à un noeud d'effectuer des decisions dites locales, par rapport au routage des paquets qui dependent de la localisation géographique d'un noeud relai, tandis que, ce noeud relai a la finalité de donner une extension maximale au niveau de couverture radio en direction de la destination.

Les résultats obtenus à partir des évaluations approfondies de CoopGeo et RACR ont démontré que les deux solutions sont applicables aux réseaux de capteurs en présence de forte mobilité, aux environnements très variables au niveau radio, ou avec des erreurs aux niveau de l'information de localisation. Par conséquent, nous avons prouvé que notre vision inter-couches du problème a fourni deux solutions efficaces, en termes de chemins, accès au media, problèmes liés à l'information imprécise de localisation, et des liens perturbés.

La Probl ématique

Ces dernières décennies, les technologies sans fil ont connu une croissance rapide. Les progrès des composants matériels ont suivi la même tendance permettant ansi la production massive de dispositifs de communication comme les ordinateurs portables, téléphones cellulaires, assistants numériques personnels (PDA), capteurs, processeurs, etc. Étant donné que ces appareils deviennent plus petits et moins chers et leur association avec certaines technologies conduit à la mise au point de nouveaux types de réseaux sans fil, ou de l'amélioration des existants, telles que les réseaux cellulaires (2G, 2.5G, 3G). Un autre type de réseaux sans fil se démarque des réseaux sans fil des données traditionnels : les réseaux sans fils sans infrastructure comme les réseaux ad-hoc, de capteurs et de réseaux maillés. Ces nouveaux types de réseau supportent des nouvelles applications comme les hotspots, les communications en temps réel, réseaux domestiques, les systèmes de surveillance, le contrôle industriel, les réseaux de véhiculaires et les réseaux de capteurs. Les réseaux de données sans fil (en faisant référence à la norme IEEE 802.11 et dérivations) ont été le centre d'intérêts scientifiques et commerciales pendant plusieurs années.

Récemment, la communauté scientifique s'est orientée vers les réseaux sans fil qui communiquent sans l'aide d'une infrastructure, tel que les réseaux ad hoc et de capteurs. Ce type de réseaux présentent des défis importants dans la conception de leur architecture. Les réseaux ad-hoc et de capteurs sont des systèmes autoorganisables, formés par des noeuds qui essaient de communiquer les uns avec les autres.

Les réseaux de capteurs (Recap) appartiennent à la classe des réseaux ad hoc, mais ils ont des caractéristiques supplémentaires qui en font un cas particulier. Même si les réseaux de capteurs partagent des comportements et caractéristiques avec les réseaux ad hoc, ils ont des différences importantes, par exemple, en raison de la petite taille des noeuds qui composent un réseau de capteurs, les noeuds ont des ressources très limitées telles que le traitement de l'information, la vitesse du processeur, la quantité de mémoire, la quantité d'énergie disponible et la puissance de transmission. Comme les noeuds sont de petite taille et de faible coût, on peut les déployer en très grandes quantités, présentant des densités supérieures à celles des réseaux ad hoc. Nous pouvons également ajouter qu' après le déploiement des noeuds, ils restent sans surveillance pendant la durée de vie du réseau (sans entretien ou dépannage)

Ainsi les Recap sont plutôt conçus pour détecter des événements ou des phénomènes naturels, les noeuds recueillent des lectures, les traitent et les transmettent aux utilisateurs. Par la nature même du réseau, les défis les plus difficiles dans les réseaux de capteurs sont l'efficace gestion de ressources des noeuds et l' adaptabilité aux changements de topologie suivis de l'état du canal de communication.

B.1 Contexte et défis

Notre travail est orienté vers les réseaux de capteurs sans fil, même si certains protocoles, algorithmes et techniques utilisés peuvent être appliqués à d'autres types des réseaux. Ainsi, afin de bien définir la portée du travail, nous présentons les caractéristiques de base et les défis attachés à notre sujet d'étude.

Les réseaux de capteurs sans fil sont composés d'un grand nombre de capteurs de petite taille qui sont en mesure de détecter, traiter et communiquer les uns avec les autres. Leur principale finalité est celle de détecter des événements ou des phénomènes, recueillir et traiter de données correspondant aux événements et les transmettre aux utilisateurs. En plus des caractéristiques liées à la communication sans fil, les réseaux de capteurs présentent d'autres caractéristiques de base héritées de la manière dont ils travaillent :

• Capacité d'auto-organisation • Communication à courte distance et de routage multi-sauts • Déploiement à haute densité • Changement fréquent de la topologie en raison de l'évanouissement du signal, la mobilité des noeuds et la défaillances de noeuds • Contraintes liées à l'énergie, la puissance de transmission, la mémoire et la puissance de calcul • Modèle de communication tous vers un Pendant la conception de l'architecture d'un réseau de capteurs, certaines tâches importantes doivent être considerées, comme, le contrôle de la consomma-tion de ressources dépensées pendant la transmission et la réception de paquets, et la limitation des effets du canal de communications générés par deux phénomènes physiques : 1) La propagation multi-trajets des ondes électromagnétiques qui génèrent des variations dans le signal reçu, 2) De l'influence éventuelle de la mobilité des noeuds qui produisent aussi une variation sur le canal de communications. Ainsi, une conception rigoureuse au niveau protocolaire s'impose dans le but de minimiser la consommation des ressources (i.e. énergie) et de maximiser ainsi la durée de vie du réseau avec les contrainte liées aux changements de topologie de façon à maintenir la connectivité et de calculer les bonnes routes entre les noeuds sources et les noeuds destination.

Afin de reveler ces défis, la communauté scientifique a beaucoup travaillé avec des approches traditionnelles basées sur un modèle de couches séparées, ainsi, chaque couche de la pile protocolaire (ie. réseau, control d'accès et physique) n'est pas au courant de l'opération de l'autre couche, éliminant ainsi, le bénéfice de l'optimisation conjointe de l'ensemble des couches qui peut améliorer les performances du réseau.

En conséquence, l'utilisation d'une approche inter-couches est obligatoire, celle-ci, doit permettre l'échange de certaines informations importantes entre les couches, afin de permettre à un noeud de rendre ses decisions de routage plus efficaces, car il aura une vision plus large du comportement du réseau. Cela entraînera une amélioration de la performance du réseau au niveau global.

Cette étude adopte une approche inter-couches pour améliorer l'approche à plusieurs niveaux et propose une architecture conçue pour faire interagir la couche réseau dans l'acheminement de paquets avec la couche du control d'accès pour obtenir l'accès au canal de communications et avec la couche physique afin d'adapter le protocole aux conditions de l'environnement sans fil.

B.2 Contributions

Au cours de ce travail, nous considérons que le routage géographique est une solution concrete au problème de routage car la route vers la destination est crée à la volé avec des informations locales. Dans ce cadre, l'objectif principal de cette thèse est de remplir l'écart entre les protocoles de routage géographiques traditionnels et l'environnement physique où les capteurs sont situés. Pour atteindre cet objectif, l'approche utilisée dans la resolution du problème de routage avec des liens intermittents se base sur les protocoles de routage géographiques sans balises ; et aussi l'approche des communications coopératives qui exploite la nature de diffusion des communications sans fils. Ainsi, nos principales contributions sont : L'objet central de notre première contribution, est celui d'adapter les protocoles de routage géographiques avec contention au aléas du canal de communications, donc, nous proposons, un système qui rend les communications des capteurs, fiables en termes de livraison de bout en bout, et ainsi, faire face à l'évanouissement du signal pendant le processus de communication.

CoopGeo est un protocole de communications inter-couches composé de deux niveaux des conceptions qui travaillent étroitement. Le premier est une conception Réseau-MAC inter-couche qui sélectionne d'abord le prochain saut du chemin à parcourir (routage), et le deuxième est une conception MAC-PHY pour la sélectionne du relais (communication coopérative). Les deux niveaux de conception de CoopGeo, sont basés sur l'information géographique des noeuds, et sur une méthode de contention local contrôlé par des temporisateurs.

C.1.1 Modèle de communication

Pour concevoir la plateforme de communications inter-couche, nous considérons un réseau de capteurs sans fil avec k noeuds déployés aléatoirement dans une zone, ce réseau représenté comme un graphe dynamique G(V, E), où V = {v 1 , v 2 , . . . , v k } est un ensemble finit de noeuds et E = {e 1 , e 2 , . . . , e l } un ensemble fini de liens entre les noeuds. On note un sous-ensemble N (v i ) ⊂ V , i = 1, . . . , k, comme le voisinage du noeud v i , défini comme l'ensemble des noeuds dans la portée radio de v i . Dans le mode direct, S diffuse un symbole x avec une puissance de transmission P , où la puissance moyenne de x est normalisée à l'unité. Les signaux reçus par F peuvent s'exprimer ainsi :

y S,F = √ P h S,F x + n S,
= P x h S,F x + n S,F , (C.2) y S,R = P x h S,R x + n S,R , (C.3)
Dans la deuxième phase, le noeud relais sélectionné décide s'il transmet le symbole décodé au saut suivant. Si le relais est en mesure de décoder le symbole transmis correctement, il le transmet avec une puissance P x au saut suivant, sinon, il reste inactif. On défini un indicateur I R , tel que :

I R = 1, if R
= P x I R h R,F x + n R,F , (C.5)
Enfin, le prochain saut combine les signaux reçus, en utilisant le mécanisme de maximum de combinaison (MRC). (SER) au noeud suivant peut être exprimé comme

y F = P x h * S,F y S,F + P x I R h * R,F y R,F . (
P s ≈ 4N 2 0 b 2 P 2 x σ 2 S,F A 2 σ 2 S,R + B σ 2 R,F , (C.8)
qui est une approximation dans un régime de haut SNR. Quand M -QAM est utilisé, b = 3/2(M -1), et

A = M -1 2M + (1 -1/ √ M ) 2 π , B = 3(M -1) 8M + (1 -1/ M ) 2 π .
(C.9)

C.1.2 CoopGeo : A geographic cross-layer protocol for cooperative wireless networks

Le protocole CoopGeo, en général, effectue deux tâches dans un réseau de capteurs coopératif multisaut : le routage et la sélection du relais. Comme décrit auparavant, le processus de routage CoopGeo fonctionne en deux phases, à savoir, les phases dites BLGF et BLRF. Dans la phase BLGF, un noeud qui joue le role de prochain saut dans le routage et qui fournit le progrès maximal vers la destination est choisi en utilisant un processus de contention basé sur des temporisateurs. Quand la phase BLGF échoue dans la recherche du prochain saut, le processus de routage entre dans la phase BLRF et applique le mécanisme "face routing" en utilisant la planarisation du réseau basé sur le principe de "selection et protestation". La sélection du relais (relais coopératif) s'effectue quand le noeud désigné comme prochain saut n'est pas arrivé à décoder le paquet correctement. Dans ce cas, CoopGeo démarre la tâche de sélection du relais, afin de trouver un noeud relais optimal qui offre le meilleur lien coopératif entre le noeud source et le prochain saut. Le noeud F 1 est choisi comme le prochain saut du noeud source S. La transmission des données entre la source S et de son prochain saut F 1 est réalisée à travers une transmission directe ou coopérative. Les noeuds relais candidats de la paire source-prochain saut (S, F 1 ) qui participent dans le mécanisme de sélection de relais, sont ceux au sein de la zone de relayage (qui sera définie plus tard), à savoir R 1 et X 1 . Dans cette figure R 1 est sélectionné comme relais optimal dans le mode coopératif.

C.1.3 Transmission greedy sans balises de contrôle (BLGF)

Au début d'une transmission, S déclenche le processus BLGF. en diffusant un paquet dans son voisinage, puis il attend la réponse du meilleur saut au cours d'un temps T max /2 . Pendant cette période, le voisinage est en concurrence pour transmettre le paquet par l'établissement des temporisateurs (T CBF ), comme expliqué dans la section C.1.3.1. Lorsque le meilleur candidat envoie Clear to Forward (CTF) à S en raison de l'expiration de son temporisateur, les autres candidats, en entendant ce paquet, suppriment leurs temporisateurs, et finalement, la source et le noeud gagnant la contention réalisent un échange de paquets de contrôle (SE-LECT / ACK) afin d'indiquer qu'un noeud intermédiaire a été trouvé. A partir de ce moment, le noeud intermédiaire devient la source des données et la procédure se répète.

C.1.3.1 Selection à base de temporisateurs (T CBF )

Pour mettre en oeuvre les temporisateurs T CBF des noeuds intermédiaires candidats, nous avons appliqué les temporisateurs en fonction de leur localisation. La figure C.2 représente la couverture radio d'un noeud source, divisé en deux zones : PPA et NPA. Comme mentionné auparavant, celles ci, sont à la fois divisés en sous-régions appelées sous-zones communes (CSAs).

Le réglage des temporisateurs de chaque noeud est donné comme suit. D'abord, chaque noeud situé dans la zone PPA identifie à quel groupe CSA il appartient

CSA P P A = N SA × r -(d S,D -d F i ,D ) 2r (C.
T CBF = CSA × T max N SA + rand T max N SA (C.11)
où T max représente le retard maximum pendant lequel le noeud source S attend une réponse d'un noeud intermédiaire et rand(x) est une fonction qui donne une valeur aléatoire entre 0 et x pour réduire la probabilité de collision des paquets. La fonction T CBF alloue la premiere moitié du T max aux candidats situés dans PPA pour la phase BLGF et l'autre moitié aux candidats situés dans NPA pour la phase BLRF.

C.1.3.2 Recuperation greedy sans balises de contrôle (BLRF)

Cette procédure de récupération est initiée quand la transmission greedy ne trouve pas un noeud intermédiaire dans la zone PPA. Ainsi, la recherche d'un noeud dans la zone NPA est declanchée automatiquement. Pour ce faire, nous avons appliqué le mécanisme de récupération proposé par [ Kalosha 08] La zone NPA est divisée en n = N SA 2 couronnes concentriques de taille égale, où la largeur de la couronne i th est ( √ i -√ i -1)r 1 , et r 1 est le rayon de la premiere couronne r 1 = r √ n . Afin d'utiliser la même terminologie, à partir de maintenant, nous nous référerons à une couronne comme un groupe CSA. Par conséquence, un noeud v ∈ N P A identifie son CSA de manière similaire à celle de noeuds dans la zone PPA

CSA N P A = √ n • d v,u r 2 + N SA 2 (C.12)
A ce moment, connaissant son CSA, le noeud détermine la valeur de son temporisateur en utilisant la même équation que les noeuds situés dans la zone PPA (Eq. C.11).

C.1.4 Selection du relais basé sur des informations géographiques

Un critère de sélection de relais sur la base d'informations géographiques, où le meilleur relais est déterminé en fonction d'une métrique m i est utilisé. Le critère de sélection de relais pour chaque saut coopératif peut être exprimé comme suit,

i * = arg min i∈{1,2,...,N } m i = arg min i∈{1,2,...,N } A 2 d p S,R i + Bd p R i ,F , (C.13) où d S,R i et d R i ,F
sont les distances entre le noeud source le i-ème noeud relais, et entre le i-ème noeud relais et le prochain saut intermédiaire, respectivement, et A et B sont des constantes de modulation dépendant que satisfont l'équation (C.9). Nous notons que le meilleur noeud relais choisi par le critère ci-dessus est celui qui fournit le meilleur lien source-relais coopératif en matière de SER moyen dans le prochain saut (le prochain noeud intermédiaire).

Le processus de selection du relais commence dès que chaque noeud relais écoute l'échange DATA/CTF. Il démarre son temporisateur si le noeud intermédiaire demande au voisinage de l'aide pour arriver à décoder le paquet reçu. Une fois que le temporisateur du meilleur relais expire, il envoie immédiatement le paquet demandé par le noeud source. Nous avons précédemment défini la métrique pour la sélection du relais, celle qui minimise le SER en fonction du schéma de modulation utilisé, où A et B sont deux constantes dependant du schéma de modulation. Le meilleur relais x i , dont la métrique est f (x i ), serait alors, le plus proche de x * qui satisfait l'équation (C.17) qui provient de (C.1.4).

m i A 2 d p S,R i + Bd p R i ,F , i = 1, 2, . . . , N, (C.14) f (x i ) = A 2 x i -x S p + B x i -x F p (C.15) minimise f (x i ) = A 2 x -x S p + B x -x F p (C.16) x * = A 2 x S + Bx F A 2 + B (p = 2) (C.17)
Nous obtenons une fonction M, qui mappe, la fonction f dans le intervalle [0, 1], où x max est le point dans un ensemble :

M(f (x)) = f (x) -f (x * ) f (x max ) -f (x * ) (C.18)
Enfin, nous utilisons l'équation suivante pour allouer le temps à chaque noeud dans le schéma de sélection relais basé sur la contention (CBR)

T CBR = T max M(f (x)) + rand 2T max N SA (C.19)

C.2 Evaluation des Performances

Notre méthodologie de simulation évalue les performances au niveau PHY/MAC avec des simulations Monte-Carlo mises en oeuvre sur Matlab code. Nous avons simulé les trois processus des couches inférieures. Les paramètres des simulations sont exprimés dans la table C.1. Les résultats obtenus se basent sur 20,000 topologies générées aléatoirement, où tous les noeuds sont en concurrence pour accéder au canal de transmission. Dans les simulations, nous commençons par trouver les noeuds intermédiaires et noeuds relais qui participent à chaque saut vers la destination finale, et une fois ces noeuds obtenus, nous les utilisons pour évaluer le taux d'erreur symbole sur les paquets, la probabilité de transmission moyenne, le débit saturé, et d'autres expérimentations dérivées de la variation des paramètres. Nous remarquons aussi que le taux d'erreur des protocoles se rapproche l'un de l'autre en fonction de la densité de noeuds en raison de la probabilité de collision dans les périodes de contention.

C.2.2 Probabilité d'erreur dans la transmission de bout en bout

Dans la figure C.5, nous montrons que la probabilité moyenne d'avoir une erreur dans la transmission est nettement supérieur dans le cas coopératif. Même le taux diminue avec l'augmentation du nombre des noeuds qui sont candidats à relayer le paquet. Ce comportement est dû à la sélection précise du noeud relais lorsque plusieurs noeuds sont présents dans le voisinage. Nous pouvons également remarquer que CooopGeo expérimente un taux d'erreur de transmission faible qui nous permet d'augmenter la taille de la constellation du schéma de modulation afin de profiter au maximum la bande passante de bout en bout.

C.2.3 Variation des paramètres d'entrée

1) La variation de la fenêtre de contention T max : Dans cet expérimentation, nous étudions l'impact de la taille de la fenêtre de contention T max (contrôle le retard affecté à un noeud concurrent quand il essaie de transmettre un paquet comme intermédiaire ou relais) sur la performance de CoopGeo. Nous simulons le protocole avec des valeurs T max de 100µs à 1000µs. 2) La variation de la taille de constellation de la modulation : la figure C.6(b),d) démontre que CoopGeo à une meilleur performance en terme de débit saturé (saturated throughput) quand la taille de la constellation est augmentée. En raison d'un taux d'erreur très faible dans CoopGeo, nous pouvons augmenter la taille de constellation en fonction des environnements de transmission sans détériorer le débit saturé de bout en bout. Notre objectif dans cette section est de concevoir un système efficace, capable de contrôler la consommation des ressources des noeuds qui composent un réseau de capteurs. Pour faire face à cet objectif, nous présentons notre deuxième contribution : un protocole de routage géographique coopératif avec connaissance du relais, Relais-Aware Cooperative Routing (RACR), qui exploite la propriété d'extension de couverture due à la coopération des noeuds.

Le protocole RACR permet à un noeud intermédiaire (forwarding) qui supporte un taux d'erreur symbole (SER) défini à participer dans le processus de routage par le biais d'une décision locale qui se base sur une sélection préalable d'un noeud relais avec le but de fournir une couverture maximale vers la destination. Lors de la conception RACR, nous répondons à la question, "comment l'extension de couverture permet à une transmission d'être efficace au niveau énergétique ?" L'évaluation des performances montre que RACR réduit de moitié la longueur du chemin moyen pendant les transmission de données dans les réseaux de capteurs denses par rapport à un protocole de routage non-coopératif.

C.4 SER-Based Radio Coverage Formulation

Dans cette section, nous indiquons de nouvelles formulations qui seront utilisées par le protocole RACR. Pour identifier l'extension de couverture grâce à la coopération, nous développons une nouvelle expression mathématique pour la couverture radio. Pour ce faire, nous avons défini un réseau G = (V, E) dans un

C.5 Architecture de RACR

Dans cette section, nous présentons notre deuxième contribution. RACR est un protocole coopératif inter-couches, basé sur un protocole de routage géographique sans balise de contrôle [Sanchez 09], qui implique la sélection des noeuds intermédiaires et relais [ Aguilar 10]. RACR utilise le principe d'extension de couverture à travers la coopération de trois noeuds. Etant donné une pair source-destination, le nombre de saut du chemin peut être réduit par rapport au protocoles de routage géographiques non-coopératifs. Pour ce faire, nous avons utilisé les formules présentées précédemment, telles que, la couverture radio directe et coopérative, ainsi que les positions optimales du relais et intermédiaires. De manière générale, le routage géographique présente deux modes de fonctionnement : le glouton (greedy) et celui de récupération du chemin. Cependant, RACR est concentré sur la conception du routage glouton.

L'architecture RACR se réalise à l'aide de deux processus de sélection. Le premier processus est de sélectionner les meilleurs relais afin que les noeuds sourcerelais coopèrent afin de fournir une extension de couverture maximale à l'égard de la destination, alors que la deuxième phase consiste à sélectionner le noeud intermédiaire (forwarding node) avec les plus grand progrès vers la destination. Les deux sélections sont fondées sur un processus distribué qui évite l'échange périodique de messages de contrôle (les balises) pendant l'acquisition des informations de localisation des voisins. Au cours des processus de sélection, les noeuds en compétition (relais ou intermédiaire) règlent leurs temporisateurs par rapport à leur situation géographique.

Étant donné une paire source-destination dans un réseau avec des contraintes au niveau SER, RACR fonctionne de la manière suivante. D'abord, la source initie le processus de sélection à deux phases par la diffusion de son message à ses voisins directs et coopératifs. Les voisins directs décodent le message, tandis que les voisins coopératifs maintiennent ce message et attendent une deuxième version du message d'un relais pour effectuer leur combinaison (MRC). Après, les voisins directs qui ont décodé correctement le message concurrencent pour devenir le noeud relais en utilisant leur temporisateur T relay ∈ [0, T max ], où T max est le délai maximum autorisé d'attente d'un noeud relais. La conception des temporisateurs est telle que les noeuds relais situés le plus près de la position optimale x * r répondent en premier. Ensuite, le noeud relais choisi transmet le message à ses voisins localisés dans la couverture coopérative, et les noeuds qui entendent ce message annulent leurs temporisateurs. Parmi les voisins coopératifs, les candidats qui sont capables de décoder correctement le message participent au processus de sélection du noeud intermédiaire en définissant aussi des temporisateurs T f wd ∈ [0, T max ]. De la même manière que le cas des temporisateurs des noeuds relais, ces temporisateurs sont réglés tels que, les candidats les plus près de la position optimale x * f répondent en premier. Alors, une fois que le noeud intermédiaire est choisi, il diffuse un accusé de réception (ACK) au noeud source pour indiquer la réception correcte du message, tandis que les autres noeuds annulent leur temporisateurs quand ils écoutent cette transmission. Finalement, le noeud intermédiaire devient le noeud source et les deux phases de RACR se répètent. Maintenant, nous détaillons le réglage des temporisateurs. Où N r désigne le nombre de groupes qui forment la zone de relais et rand(x) nous donne une valeur entre 0 et x, afin de réduire la probabilité de collision des noeuds dans le même groupe.

C.5.2 Selection du noeud intermédiaire

Pour sélectionner le noeud intermédiaire dans un saut (le noeud avec le plus grand avancement dans la couverture radio cooperative vers la destination), les temporisateurs de chaque noeud doivent être proportionnelles à leur distance avec les position optimales de transmission cooperatives. Pour ce faire, nous avons défini un point de projection x m i à partir du noeud relais choisi x r i vers la ligne

M f = x f i -x * f (r D ) 2 + x m i -x * f 2 , (C.31) où x m i -x * f = r C max -x s -x m i .
Finalement, pour affecter le délai au temporisateur de chaque noeud, on calcule :

T f wd = (N f -1) N f T max × M f + rand T max N f , (C.32)
où N f represente le nombre de groupes qui forment la zone de selection des noeuds intermédiaires.

C.6 Evaluation des performances C.6.1 Extension de la couverture D'abord, nous analysons les résultats théoriques de l'extension de la couverture du modèle coopératif avec un canal d'évanouissement Rayleigh. On suppose que le SER demandé est ζ 0 = 10 -2 , la puissance de transmission totale pour les deux régimes (directs et de coopératif) est P = 15 dBm, le bruit moyen est N 0 = -70 dBm, l'exposant d'évanouissement α = 4, et les constellation de la modulation à partir de 4-QAM jusqu'à 64-QAM. Nous comparons les régimes de coopération avec le régime direct en termes d'avancement vers la destination (0, ∞). Afin de produire une comparaison equitable, nous avons défini P C 1 = P C 2 = P D 2 (la puissance de transmission totale du noeud source et du noeud relais dans le régime coopératif est la même que celle utilisée dans le régime direct. La figure C.8 représente l'extension obtenue de la couverture radio en fonction des noeuds relais placés entre la source (0, 0) et le noeud intermédiaire (0, 1) (distance normalisée). On note que la meilleure position du relais se trouve à mi-chemin entre S et D. Les simulations montrent une extension de coverture d'environ 80% et 90% vers la destination.

C.6.2 Efficacité énergétique

Ensuite nous donnons des résultats numériques pour évaluer la performance au niveau routage du protocole RACR. Le réglage des simulations est donné dans le tableauC.2. Dans les simulations, nous générons 100 topologies où les noeuds sont déployés aléatoirement dans un espace de 1000×1000 m 2 . Pour chaque topologie, nous sélectionnons de façon aléatoire 750 paires source-destination. Pour démontrer l'efficacité énergétique du protocole RACR par rapport à une approche géographique non-coopératif, nous considérons que l'efficacité énergétique est mesurée avec le nombre de sauts de la route. Dans notre expérimentation, nous avons considéré la phase de routage greedy d'un protocole de routage géographique traditionnel (Greedy Forwarding). Dans

Figure 2 .

 2 Figure 2.1: Greedy Forwarding: Node s forwards the packet to neighbor F 1

Figure 2 . 2 :

 22 Figure 2.2: Forwarding strategies

Figure 2 . 3 :

 23 Figure 2.3: Nearest and farthest neighbor strategies

Figure 2 . 4 :

 24 Figure 2.4: In blue the right hand rule and in red the face changes, two principles composing the face traversal on a planar graph used in GFG and GPSR algorithms strategies

Figure 2 . 5 :

 25 Figure 2.5: 60˚sector from S to D within the transmission range

Figure 2 .

 2 Figure 2.6: Area-based suppression strategies. Node A, B and C are in the reuleaux triangle whereas only node C is in the circle area

Figure 2 .

 2 Figure 2.7: Forwarding area sequence shifts in IGF

Figure 2 .

 2 Figure 2.8: Regions from the destination point of view

Figure 2 .

 2 Figure 2.9: BOSS extends the positive sub-regions from GeRaf to the negative area of the node coverage area

Figure 3 .

 3 Figure 3.1: Unit Disk Graph

Figure 3 . 2 :

 32 Figure 3.2: Unit Disk Graph network

  (a) Gabriel Graph (b) Gabriel Graph network

Figure 3 . 3 :

 33 Figure 3.3: Gabriel Graph model and network

  (a) Relative Neighborhood Graph (b) Relative Neighborhood network

Figure 3 . 4 :

 34 Figure 3.4: RNG Graph model and network

  .3(a) the GG(G) model and in Fig. 3.3(b) a WSN modeled as GG(G) graph.

Figure 3 . 5 :

 35 Figure 3.5: Delaunay triangulation model and Delaunay network

Figure 3 .

 3 Figure 3.6: The Random Waypoint Model behavior, where each color represents the movement of a node

Figure 4 .

 4 Figure 4.1: (a) Cooperative multihop sensor network model (b) Direct and cooperative modes for each hop

Figure 4 . 2 :

 42 Figure 4.2: Area division for CoopGeo routing. F 1 and F 2 are sub-area 0 and 1 of PPA respectively, whereas F 3 and F 4 are sub-area 4 and 5 of NPA respectively.

Figure 4 . 3 :

 43 Figure 4.3: CoopGeo architecture

Figure 4 . 4 :

 44 Figure 4.4: Recovery forwarding area is divided in N coronas. Each has a width ( √ i -√ i -1)r 1

Figure 4 . 5 :

 45 Figure 4.5: Nodes v i ...v n have the same distance to u. So, each node has to use a random function rand( Tmax N SA ) to decrease the collision probability (see Fig. 4.4), where the width of the i-th corona is ( √ i -√ i -1)r 1 , and r 1 is the radius of the first corona, being calculated with r 1 = r/ √ n. To use the same terminology as the one used at the BLGF phase, in the following a corona will be referred as a CSA. To set a contention timer, a candidate F in NPA first finds its CSA N P A index by using the following equation:

Figure 4 . 6 :

 46 Figure 4.6: Beaconless recovery messages exchange

Figure 4 .

 4 Figure 4.7: Beaconless Recovery Forwarding happens at Negative Progress Area (NPA) when the Beaconless Greedy Forwarding fails

Figure 4 .

 4 Figure 4.8: (a) Mapping of the metric on to the set C (b) Mapping of the metric on to the set D for a normalized distance Source(0,0) Destination(1,0)

Figure 4 . 9 :

 49 Figure 4.9: CoopGeo in action

Figure 4 . 10 :

 410 Figure 4.10: Comparison of each possible relay selection and random relay selection

  (a) PER for BOSS (b) PER for CoopGeo

Figure 4 .

 4 Figure 4.11: PER for BOSS and CoopGeo using T max = 100...1000 µs. The curves located at the bottom of the figures correspond to minimum value of T max = 100 and those located in the upper side to the maximum value T max = 1000

Figure 4 .

 4 Figure 4.12: Packet Error Rate for T max = 500µs

  (a) Error Transmission Rate for BOSS (b) Error Transmission Rate for Coop-Geo

Figure 4 .

 4 Figure 4.13: Error Transmission Rate (end to end) for BOSS and CoopGeo using T max = [100,...,1000] µs

Figure 4 .

 4 Figure 4.14: End to End Transmission Error Probability for T max = 500µs

Figure 4 .

 4 Figure 4.15: CTF-Relayed message collision probability when changing T max from 100µs to 1000µs

Figure 4 .

 4 Figure 4.19: Normalized saturated throughput and collision probability for T max = 300µs and T max = 500µs

Figure 5 .

 5 Figure 5.1: Extended coverage using cooperative transmission

Figure 5 . 2 :

 52 Figure 5.2: Multihop sensor network with cooperative geographic routing.

Figure 5 . 3 :

 53 Figure 5.3: RACR Architecture.

Figure 5 . 4 :

 54 Figure 5.4: Optimal relaying and forwarding positions and the direct and maximum cooperative transmission radii.

Figure 5 . 5 :

 55 Figure 5.5: Example of optimal relay and forwarding positions distributions

  <x d -xs,xr i -xs> x d -xs xr i -xs

Fig. 5 .

 5 Fig.5.5 depicts an example of a simple RACR execution. Given given a source node at (0,0), a destination node (0, 300) for r C max = 180m and r D = 110m. The optimal relay position is calculated, the nearest relay node Xr i selected at (30, 80), then the optimal forwarding position Xf * is computed.

Figure 5 . 6 :

 56 Figure 5.6: Relay selection as function of alpha (a)Alpha: 2 (b)Alpha: 3 c()Alpha: 4 (d)Alpha: 3.8

Figure 5 . 7 :

 57 Figure 5.7: Coverage extension (%) with alpha:4, due to cooperation versus the relaying position with a cross-sectional view for (a) 4QAM, (b) 16QAM, (c)32QAM, (d)64QAM.

Figure 5 . 8 :

 58 Figure 5.8: Coverage extension (%) with alpha:4, due to cooperation versus the relaying position with a 3D view for (a)4QAM, (b)16QAM, (c)32QAM, (d)64QAM.

Figure 5

 5 Figure 5.9: (a)Average path length versus the average number of neighbors. (b)The corresponding stretch factor.

Figure

  Figure C.1 -(a) Cooperative multihop sensor network model (b) Direct and cooperative modes for each hop

  C.6) Ainsi, le symbole decodé par le saut suivant x est exprimé par l'equation x = arg min x∈A |y F -P x (|h S,F | 2 + I R |h R,F | 2 )x| 2 , (C.7) Où |A| = Θ denote la cardinalité de la constellation Θ-aire. Selon l'analyse des performances de [Su 08], le taux d'erreur de symboles

Figure C. 2 -

 2 Figure C.2 -Area division for CoopGeo routing. F 1 and F 2 are sub-area 0 and 1 of PPA respectively, whereas F 3 and F 4 are sub-area 4 and 5 of NPA respectively.

  Fig. C.1(a) donne un exemple de sélection au niveau du routage et du relais dans CoopGeo. Les noeuds localisés dans l'aire PPA participent dans la phase BLGR, à savoir, X 1 , X 2 , R 1 , and F 1 . Ceux situés dans l'aire NPA, c'est-à-dire W 1 , . . . , W 4 , sont considérés comme participant de la phase BLRF.

C. 2 . 1

 21 Taux d'erreur de paquets (PER) Afin d'analyser le PER de BOSS et CoopGeo, nous commençons par simuler les protocoles avec des valeurs T max différents, allant de T max = 100µs jusqu'à T max = 1000µs. Les résultats sont présentés dans les figures C.3(a) C.3(b). Les deux figures nous permettent d'avoir une visualisation globale du comportement des protocoles à l'égard du PER. A partir de ces résultats, nous pensons que le comportement lorsque CoopGeo utilise T max = 500µs represente un bonne rapport entre le PER et le délai nécessaire pour choisir les noeuds coopératifs d'une transmission. Ainsi, dans la figure C.4, nous montrons que le PER moyen de deux protocoles avec cette valeur choisie. Le taux d'erreur sur les paquets de la figure inclut à la fois la probabilité de collision dans les périodes de contention et la probabilité d'erreur sur le canal sans fil.Nous prouvons que notre protocole a présenté une baisse du taux d'erreur de 2,5 fois moins, par rapport au protocole de routage géographique traditionnel.

  Figure C.3 -PER de BOSS et CoopGeo avec T max = 100...1000 µs. Les courbes situées dans la partie inférieure du graph correspondent à T max = 100 et celles situées dans la partie supérieure correspondent à la valeur maximale T max = 1000

Figure C. 4 -

 4 Figure C.4 -Packet Error Rate for T max = 500µs

Figure C. 5 -

 5 Figure C.5 -Transmission Error Probability for T max = 500µs

Figure 2 . 2 : 5 :

 225 Figure C.6 -(a)CTF-Relayed message collision probability when changing T max from 100µs to 1000µs. (b)CoopGeo Saturated throughput for QAM fom 16-128.

Figure

  Figure C.7 -Positions optimales du relais et intermédiaire, et rayon de transmission direct et coopératif.

  formée par les noeuds source et destination, comme illustre la figure C.7, où θ est donné par θ = arcsin <x d -xs,xr i -xs> x d -xs xr i -xs . Etant donné que les coordonnées x s , x * r , et x d sont connues par le noeud actuel et que chaque noeud relais candidat connaît sa propre position x m i , chaque noeud intermédiaire qui est candidat est capable de deriver la position optimale intermédiaire x * f et determiner ainsi son temporisateur T f wd . Donc, la métrique M f de selection d'un noeud intermédiaire est

Figure

  Figure C.8 -Coverage extension (%) with alpha :4, due to cooperation versus the relaying position with a 3D view for (a)4QAM, (b)16QAM, (c)32QAM, (d)64QAM.

•

  Active Selection scheme. It is inspired by the Request To Send, Clear To Send (RTS/CTS) mechanism from the IEEE 802.11 standard. Here, the forwarding node broadcasts a control packet called RTF (Request To For-

Table 4

 4

	.1: Relays Locations and The Corresponding Selection Metrics
	Relay # (A) Location (B) Selection metric m
	R 1	(0.32,0.13)	0.1283
	R 2	(0.08,-0.18)	0.2980
	R 3	(0.71,0.28)	0.1155
	R 4	(0.43,0.47)	0.1989
	R 5	(0.58,-0.07)	0.0691

Table 4 .

 4

		2: Simulation Settings
	Input	Value	Input	Value
	No. of Neighbors	1-20	Tx. Power	25 dBm
	Channel Model	Rayleigh	Average Noise	20 dB
	Carrier Frequency 2.412 Ghz	Noise Figure	15 dB
	Channel Bandwidth	22 Mhz	Packet Size	1538 Bytes
	Modulation Type	QAM	No. of Topologies	20000
	Constellation Size	4-128	No. of Simu. Trials	2000000
	Contention Period	500 µs
	is a BOSS[Sanchez 07] like protocol without cooperative relaying. The packet
	error rate presented in Fig.

Table 5

 5

		.1: Simulation Settings
	Input	Value	Input	Value
	No. of nodes	2000-2450	Tx. power	15 dBm
	Path loss exp.	4	Average noise power -70 dBm
	Modulation type	QAM	Noise figure	15 dBm
	Required SER	10e-2	No. of topologies	100
	Constellation size	4	No. of simulation runs	75000

•

  Une conception multi-couches appelée CoopGeo (Cooperative Communications and Geographic Routing) est proposé. CoopGeo a été largement évaluée et comparée à un protocole de routage traditionnel sans balise. Co-opGeo effectue le mécanisme routage géographique basé sur la méthode de contention et les communications cooperatives avec un mécanisme de selection du relais unique dans le cas où la communication directe échoue. Avec CoopGeo, nous améliorons les performance au niveau de la couche physique en termes de fiabilité.• Le protocole RACR exploite l'extension de la couverture grace à la cooperation des noeuds, afin d'améliorer le routage géographique non-cooperatif en terme d'efficacité énergétique. Il s'agit d'une alternative aux cas où les ressources du réseau telle que l'énergie doit être préservée tout en respectant une contrainte au niveau de taux d'erreur symbole (SER). Les résultats obtenus suite à l'évaluation de CoopGeo et RACR nous fait penser que les deux solutions sont applicables aux réseaux de capteurs en présence forte mobilité ou dans des environnements avec un canal de transmission très variable. Ainsi, nous pouvons dire que notre approche inter-couches du problème peut fournir une solution intégrale aux problèmes de routage et au problèmes physiques suivis par les réseaux de capteurs.

	Annexe C
	Contributions
	C.1 CoopGeo : A Cooperative Geographic Rou-
	ting Protocol

  F , (C.1) où h S,F est le coefficient d'évanouissement du canal de S à F , modélisé comme h S,F ∼ CN (0, σ 2 S,F ) ; n S,F est le bruit additif. Pour le mode coopératif, on applique une stratégie de sélection du relais unique à décodage en deux phases decode-andforward (DF). Dans la première phase, S diffuse son symbole x avec une puissance de transmission P x , tandis que, le prochain saut F et un relais R écoutent la transmission. Les signaux reçus par F et R peuvent être respectivement exprimés en y S,F

  [START_REF] Vardhe | [END_REF] où NSA est un nombre prédéfini sous-domaines qui divisent la zone de cou-verture, r le progrès maximum ou la portée de transmission, et (d S,Dd F i ,D ) représente les progrès d'un noeud intermédiaire candidat à la destination (les noeuds localisés dans NPA utilisent Eq. (C.12) pour obtenir leur CSA). Ensuite, étant donné CSA P P A où CSA N P A , chaque candidat calcule son temporisateur avec l'équation suivante :

Table C

 C

		.1 -Simulation Settings
	Input	Value	Input	Value
	No. of Neighbors	1-20	Tx. Power	25 dBm
	Channel Model	Rayleigh	Average Noise	20 dB
	Carrier Frequency 2.412 Ghz	Noise Figure	15 dB
	Channel Bandwidth	22 Mhz	Packet Size	1538 Bytes
	Modulation Type	QAM	No. of Topologies	20000
	Constellation Size	4-128	No. of Simu. Trials	2000000
	Contention Period	500 µs

  RACR, chaque saut se base sur le régime

	NPA Negative Progress Area, 66
	PER Packet Error Rate, 77
	PPA Positive Progress Area, 66
	Glossary RACR Relay-Aware Cooperative Routing protocol, 9
	SER Symbol Error Rate, 9, 20
	SNR Signal to Noise Ratio, 44
	BER Bit Error Rate, 41
	BFP Beaconless Forwarder Planarization, 69
	BLGF BeaconLess Greedy Forwarding, 66
	BLGR BeaconLess Geographic Routing, 61
	BLR BeaconLess Routing, 31
	BLRF BeaconLess Recovery Forwarding, 66
	BOSS Beaconless On Demand Strategy for Geographic Routing in Wireless
	Sensor Networks, 36
	CBF Contention-Based Forwarding, 31
	CoopGeo Beaconless Cooperative Geographic cross-layer protocol, 9
	CSA Common Sub-Areas, 67
	CSI Channel State Information, 44
	CTF Clear-To-Forward, 67
	GeRaF Geographic Random Forwarding, 35
	GFG Greedy Face Greedy, 28
	GPSR Greedy Perimeter Stateless Routing, 28
	GR Geographic Routing, 23
	IGF Implicit Geographic Routing, 31
	MIMO Multiple-Input Multiple-Output, 60
	MQAM M-Quadrature Amplitude Modulation, 79
	MRC Maximum Ratio Combining, 41

equally sized concentric coronas

"A CSA value at the forwarding selection is a nonnegative integer that falls in [0, N SA-1], where 0 corresponds to the area closest to D and (N SA -1) to the farthest one"

Acknowledgement

I would like to acknowledge my advisor Prof. Hossam Afifi who gave me the opportunity to join the Wireless Networks and Multimedia Services Department (RS2M) at Telecom SudParis. I also thank Dr. Vincent Gauthier who so kindly co-advised this work, spent so many hours helping me and had influenced my research. I am deeply grateful for his support.

I thank Syue-Ju, all the friends from Telecom SudParis: Sépideh, Ines, Anahita, Bastien, Makhlouf, Mehdi, Vincent V, Abid, Boutabia, Emad, Ahmad, Cuiting, Mariem, and so many other that i knew during my research period.

I thank my brothers and sisters and in particular my parents Ronay and Sandra -You did a great job! To my family-in-law for their support and made me feel at home in a foreign place.

I would like to thank my son Gaël and finally to my lovely wife Marianne who supported and motivated me to continue even in the difficult and frustrating times. I love you.

Publications

• S. Syue, V. Gauthier, T. Aguilar, M. Beserra, C. Wang, and H. Afifi, "Relay-Aware Cooperative Routing in Multihop Wireless Networks : A Cross-Layer Approach," (Submitted).

• T. Aguilar Le routage dans les réseaux de capteurs est un service essentiel qui transmet les lectures des capteurs à certains points de collecte de données dans le réseau sur la base des relais multi-saut. Cette tâche est particulièrement difficile car elle doit être réalisé d'une manière efficace au niveau de la consommation de resources et avec une quantité limitée d'informations disponibles. La facilité de mise à l'échelle et l'utilisation d'informations locales pour fonctionner ont permis au routage géographique d'être considéré comme une approche prometteuse. Cependant, lors de son implementation, certains problèmes subsistent en raison des difficultés pratiques.

Dans ce travail de recherche, deux problématiques inhérentes aux protocoles de routage géographiques ont été étudiées : i) Le coût associé : aux évanouissements liés aux obstacles et aux multi-trajets suivis par un signal transmis sur un canal radio, aux changements rapides des conditions physiques du canal de transmission et ii) l'administration de resources affectées à chaque noeud appartenant au réseau. Afin de résoudre ces problèmes, deux protocoles ont été présentés : un protocole de routage géographique avec communications coopératives, beaconless Cooperative Geographic cross-layer protocol for ad hoc and sensor networks (Co-opGeo) et un protocole de routage basé sur le principe d'extension de couverture Relay-Aware Cooperative Routing (RACR).