Since its inception, cognitive radio (CR) has quickly been accepted as the enabling radio technology for next-generation wireless communications. A CR promises unprecedented flexibility in radio functionalities via programmability at the lowest layer, which was once done in hardware. Due to its spectrum sensing, learning, and adaptation capabilities, CR is able to address the heart of the problem associated with spectrum scarcity (via dynamic spectrum access (DSA)) and interoperability (via channel switching). It is envisioned that CR will be employed as a general radio platform upon which numerous wireless applications can be implemented. For both theoretical and practical purposes, it is important for network researchers to model a cognitive radio ad hoc network (CRN) and optimize its performance. Such efforts are important not only for theoretical understanding, but also in that such results can be used as benchmarks for the design of distributed algorithms and protocols. However, due to some unique characteristics associated with CRNs, existing analytical techniques may not be applied directly. As a result, new theoretical results, along with new mathematical techniques, need to be developed. In this thesis, we focus on modeling and optimization of CRNs. In particular, we will study multicast communications in CRN and MIMO-empowered CRN, which we describe as follows. An important service that must be supported by CRNs is multicast. Although there are a lot of research on multicast in ad hoc networks, those results cannot be applied to a CRN, because of the complexity associated with a CR node (e.g., multiple available frequency bands, difference in available bands from neighboring nodes). In addition, a single-layer approach (e.g., multicast routing) is overly simplistic when resource optimization (i.e., minimizing network resource) is the main objective. For this purpose, a cross-layer approach is usually necessary, which should include joint consideration of multiple lower layers, in addition to network layer. However, such a joint formulation is usually highly complex and difficult. In this thesis, we aim to develop some novel algorithms that provide near-optimal solutions. Our goal is to minimize the required network-wide resource to support a set of multicast sessions, with a certain bit rate for each multicast session. The unique characteristics associated with CR and distinguish this problem from existing multicast research for ad hoc networks. In this work, we formulate this problem via a cross-layer approach with joint consideration of scheduling and routing. Although the problem formulation is in the form of mixed integer linear program (MILP), we are successful in developing a polynomial time algorithm that offers highly competitive solution. The main ideas of the algorithm include identification of key integer variables, fixing these variables via a series of relaxed linear program (LP), and tying up such integer fixing with a bottom-up tree construction. By comparing with a lower bound, we find that the proposed algorithm can provide a solution that is very close to the optimum. In parallel to the development of CR for DSA, multiple-input multiple-output (MIMO) has widely been accepted and now implemented in commercial wireless products to increase capacity. The goal of MIMO and how it operates are largely independent and orthogonal to CR. Instead of exploiting idle channels for wireless communications, MIMO attempts to increase capacity within the same channel via space-time processing. Assuming that CR and MIMO will ultimately marry each other and offer the ultimate flexibility in DSA and spectrum efficiency, we would like to inquire the potential capacity gain in this marriage. In particular, we are interested in how such marriage will affect the capacity of a user communication session in a multi-hop CRN. We explore MIMO-empowered CR network, which we call CRN^MIMO, to achieve ultimate flexibility in DSA and spectrum efficiency. Given that CR and MIMO handle interference at different levels (across channels vs. within a channel), we are interested in how joint optimization of both will maximize user capacity in a multi-hop network. To answer this question, we develop a tractable mathematical model for CRN^MIMO, which captures the essence of channel assignment (for CR) and degree-of-freedom (DoF) allocation (for MIMO). Based on this mathematical model, we use numerical results to show how channel assignment in CRN and DoF allocation in MIMO can be jointly optimized to maximize capacity. More important, for a CRN^MIMO with A_MIMO antennas at each node, we show that joint optimization of CR and MIMO offers more than A_MIMO-fold capacity increase than a CRN with only a single antenna at each node. / Master of Science

A multi-hop ad hoc network requires no infrastructure, like base stations or routers to function. This means that it can quickly be deployed and in movement, making it ideal for scenarios like natural disasters or battlefield communication. A single-frequency network (SFN) is the idea that transmitters can cooperate to send the same signals simultaneously over the same frequency channel, such that the signals are amplified. It was previously proposed that SFNs could be created in multi-hop ad hoc networks. According to simulations, this could improve the energy consumption, signal reachability, and data transfer rate. As this has only been simulated, the purpose of this project is to experimentally verify that SFN is attainable in a multi-hop ad hoc network, and to assess what the difficulties are of an actual implementation. The method involved synchronizing the transmission of two devices operating under the 802.11a standard. A multi-hop ad hoc network was created by changing the settings of the network interface cards. The devices used were mainly laptops and transmissions were monitored in Wireshark. The laptops were forced to send on one frequency channel to make interference possible, and identical packets were sent. Experiments were made to assess whether SFN was attained. The packet loss rate and distance were used to evaluate the results. The results suggest that a synchronized transmission off by less than 2 μs was attained. However, the error of these measurements were neither known nor approximable. This meant it was hard to know when a SFN was formed. The results indicate that SFN was attained, as the packet loss rate decreased significantly when employed. The effectiveness of SFN was hard to assess because the results were not comparable with the simulation values. The difficulty of an actual implementation is deemed to be the synchronization of transmissions.

Wireless Sensor Networks (WSNs) are composed of a large number of battery-powered sensor nodes that have the ability to sense the physical environment, compute the obtained information and communicate using the radio interfaces. Because sensor nodes are generally deployed on a large and wild area, they are powered by embedded battery. And it is difficult to change or recharge the battery, thus to reduce the energy consumption when sensors and protocols are designed is very important and can extend the lifetime of WSNs. So sensor nodes transmit packets with a lower transmission power (e.g. OdBm). With this transmission power, a packet can only be transmitted dozens of meters away. Therefore, when a sensor detects an event, a packet is sent in a multi-hop, ad-hoc manner (without fixed infrastructure and each sensor is able to relay the packet) to the sink (specific node which gathers information and reacts to the network situation). In this thesis, we first give an elaborate state of the art of WSNs. Then the impacts of duty-cycle and unreliable links or the performances of routing layer are analyzed. Based on the analytical results, we then propose three new simple yet effective methods to construct virtual coordinates under unreliable links in WSNs. By further taking the duty-cycle and real-time constraints into consideration we propose two cross-layer forwarding protocols which can have a greater delivery ratio and satisfy the deadline requirements. In order to have protocols for the WSNs that have dynamic topology, we then propose a robust forwarding protocol which can adapt its parameters when the topology changes. At last, we conclude this thesis and give some perspectives.

Important sujet de recherche dans les télécommunications contemporaines, les réseaux de capteurs sont des réseaux sans fil constitués de plusieurs nœuds pouvant communiquer entre eux. Chaque capteur est autonome et possède une durée de vie limitée, liée à la taille de sa batterie. Dans ce contexte, l’énergie est une ressource critique qui peut être économisée en minimisant le nombre de paquets émis. De part la nature du médium radio, les données transmises subissent des pertes du canal. La fiabilisation de données dans ce contexte n’est pas simple et devient d’autant plus problématique lorsque la taille de réseau augmente. C’est dans ce contexte que s’inscrit cette thèse qui vise à fournir une technique de fiabilisation des transmissions dans un réseau de capteur. Pour cela, nous proposons de mettre en oeuvre un mécanisme de transmission qui exploite le code fontaine. Ce code est sans rendement et les symboles de redondance sont générés à la volée. Il permet de fiabiliser la transmission avec l’utilisation d’un canal de retour limité. Le code fontaine permet d’alléger le mécanisme de contrôle des transmissions tout en assurant un lien complètement fiable, ce qui permet de réduire la latence et la consommation énergétique d’une transmission. Afin d’optimiser la performance globale du réseau, nous étudions également dans cette thèse le cas où les nœuds sont autorisés à coopérer pour le relayage multi-sauts de paquets destinés à des nœuds distants. Nous montrons dans cette thèse que la technique de codage réseau permet d’introduire de la diversité d’information et ainsi d’améliorer la performance globale de transmissions multi-sauts mono-chemin. Ce résultat a été étendu à la transmission coopérative pour laquelle nous avons à la fois pu exploiter la diversité d’information et la diversité spatiale. / This thesis is dedicated to the deployment of fountain codes and network coding in a wireless sensor network (WSN). A WSN is composed of sensor nodes with restricted capacities : memory, energy and computational power. The nodes are usually randomly scattered across the monitored area and the environment may vary. In the presence of fading, outage and node failures, fountain codes are a promising solution to guaranty reliability and improve transmission robustness. The benefits of fountain codes are explored based on an event-driven WSNet simulator considering realistic implementation based on standard IEEE802.15.4. Fountain codes are rateless and capable of adapting their rate to the channel on the fly using a limited feedback channel. In this thesis, we highlight the benefits brought by fountain code in terms of energy consumption and transmission delay. In addition to the traditional transmission with fountain code, we propose in this thesis to study the network coding transmission scheme where nodes are allowed to process the information before forwarding it to their neighbors. By this means, we can say that packet diversity is exploited as each individual packet is unique and contains different representations of binary data. Redundancy is thus optimized since repetitions are avoided and replaced with diversified information. This can further lead to an overall improved performance in cooperative communication where nodes are allowed to assist in relaying packets from the source the destination. We highlight in this thesis the benefits of fountain code combined to network coding and show that it leads to a reduction in transmission delay and energy consumption. The latter is vital to the life duration of any wireless sensor network.

Les réseaux de capteurs sans fils (WSN) sont composés d'un très grand nombre de capteurs, capables de mesurer des paramètres physiques de l'environnement, de mettre en forme l'information obtenue et de la communiquer aux autres capteurs grâce à une interface radio. Les capteurs étant en général déployés sur de très grandes étendues géographiques, l'énergie nécessaire pour les faire fonctionner est fournie par une batterie embarquée sur le capteur. En général, il est difficile de recharger les batteries une fois les capteurs déployés. Economiser l'énergie est donc une préoccupation constante lors de la conception des capteurs et des protocoles de communication utilisés, de manière à prolonger la durée de vie du réseau. Dans ce but, les capteurs transmettent leurs données avec des puissances d'émission très faibles. Avec de telles puissances d'émission, un message ne peut être transmis que sur quelques dizaine de mètres. De ce fait, lorsqu'un capteur détecte un événement, le message est transmis en mode ad-hoc multisauts jusqu'au puits, un nœud spécifique du réseau, qui récolte toutes les informations et est capable de réagir de manière adéquate. Dans cette thèse, nous donnons d'abord un état de l'art avancé sur les WSN. Ensuite nous analysons l'impact du cycle d'endormissement et des liens non fiable sur la couche de routage. A partir des résultats analytiques, nous proposons trois méthodes originales, simples et efficaces pour construire des coordonnées virtuelles en prenant en compte la non fiabilité des liens dans les WSN. En prenant en compte le cycle d'endormissement et les contraintes temps-réel, nous proposons deux protocoles cross-layer qui ont de bons taux de livraison et qui permettent de respecter des contraintes temporelles. Pour pallier à la dynamicité des réseaux de capteurs sans fil, nous proposons un protocole de routage robuste qui adapte ses paramètres quand la topologie change. Enfin, nous concluons et donnons quelques perspectives. / Wireless Sensor Networks (WSNs) are composed of a large number of battery-powered sensor nodes that have the ability to sense the physical environment, compute the obtained information and communicate using the radio interfaces. Because sensor nodes are generally deployed on a large and wild area, they are powered by embedded battery. And it is difficult to change or recharge the battery, thus to reduce the energy consumption when sensors and protocols are designed is very important and can extend the lifetime of WSNs. So sensor nodes transmit packets with a lower transmission power (e.g. OdBm). With this transmission power, a packet can only be transmitted dozens of meters away. Therefore, when a sensor detects an event, a packet is sent in a multi-hop, ad-hoc manner (without fixed infrastructure and each sensor is able to relay the packet) to the sink (specific node which gathers information and reacts to the network situation). In this thesis, we first give an elaborate state of the art of WSNs. Then the impacts of duty-cycle and unreliable links or the performances of routing layer are analyzed. Based on the analytical results, we then propose three new simple yet effective methods to construct virtual coordinates under unreliable links in WSNs. By further taking the duty-cycle and real-time constraints into consideration we propose two cross-layer forwarding protocols which can have a greater delivery ratio and satisfy the deadline requirements. In order to have protocols for the WSNs that have dynamic topology, we then propose a robust forwarding protocol which can adapt its parameters when the topology changes. At last, we conclude this thesis and give some perspectives.

Dans cette thèse, nous nous sommes intéressés aux réseaux urbains considérés par le projet ANR ARESA2 qui sont principalement des réseaux de capteurs et actionneurs hétérogènes : l’hétérogénéité est causée par la coexistence des noeuds capteurs à faibles ressources et des noeuds actionneurs riches en ressources. Ces derniers devraient être utilisés de manière différenciée par le réseau. C’est dans ce contexte que se déroule cette thèse dans laquelle nous avons étudié des algorithmes d’auto-organisations et de routage s’appuyant sur l’hétérogénéité. Au début, nous nous sommes intéressés à l’auto-organisation dans un contexte hétérogène. Se basant sur l’idée que les ressources au niveau des noeuds actionneurs doivent être exploitées afin de réduire la charge de communication au niveau des noeuds capteurs, nous avons proposé un protocole d’auto-organisation appelée Far-Legos. Far-Legos permet de profiter de la puissance d’émission des actionneurs pour apporter une information de gradient au niveau des capteurs. Les actionneurs initient et construisent une topologie logique. Cette dernière sera utilisée pour faciliter la phase de collecte de données à partir des noeuds capteurs vers les noeuds actionneurs. Ensuite, nous nous sommes intéressés aux liens asymétriques causés par la présence de différents types de noeuds avec différentes portées de transmission. Ces liens asymétriques, causés par l’hétérogénéité au niveau des noeuds constituant le réseau, peuvent détériorer les performances des protocoles de routage qui ne tiennent pas compte de ce type de liens. Pour éviter la dégradation de ces protocoles de routage, nous introduisons une nouvelle métrique de calcul de gradient ou de rang. Celle-ci sera utile pour détecter et éviter les liens asymétriques au niveau de la couche réseau pour le protocole de routage RPL. Nous présentons aussi une adaptation du protocole de collecte de données basé sur Legos pour détecter et éviter ces liens asymétriques. Enfin, nous nous sommes intéressés à l’exploitation de ces liens asymétriques. Nous proposons ainsi un protocole de collecte de données dédiés aux réseaux hétérogènes contenant des liens asymétriques appelé AsymRP. AsymRP est un protocole de routage dédié au trafic de collecte de données basé sur une connaissance de voisinage à 2-sauts combinée avec l’utilisation des messages d’acquittements (ACKs) implicites et une technique de routage de messages ACKs explicites. Cette proposition tire profit des liens asymétriques afin d’assurer une collecte de données fiable. / In this thesis, we focused on urban wireless networks considered by the ANR project ARESA2. The networks considered by this project are heterogeneous networks. This heterogeneity is caused by the coexistence of sensor nodes with limited resources and actuator nodes with higher resources. Actuators nodes should be used differentially by the network. Hence designed protocols for WSANs should exploit resource-rich devices to reduce the communication burden on low power nodes. It is in this context that this thesis takes place in which we studied self-organizing and routing algorithms based on the heterogeneity. First, we are interested in self-organization protocols in a heterogeneous network. Based on the idea that resource-rich nodes must be exploited to reduce the communication load level on low-power nodes, we proposed self-organizing protocol called Far-Legos. Far-Legos uses the large transmit power of actuators to provide gradient information to sensor nodes. Actuators initiate and construct a logical topology. The nature of this logical topology is different inside and outside the transmission range of these resourceful nodes. This logical topology will be used to facilitate the data collection from sensor to actuator nodes. Second, we investigated the asymmetric links caused by the presence of heterogeneous nodes with different transmission ranges. The apparition of asymmetric links can dramatically decrease the performance of routing protocols that are not designed to support them. To prevent performance degradation of these routing protocols, we introduce a new metric for rank calculation. This metric will be useful to detect and avoid asymmetric links for RPL routing protocol. We also present an adaptation of data collection protocol based on Legos to detect and avoid these asymmetric links. Finally, we are interested in exploiting the asymmetric links present in the network. We proposed a new routing protocol for data collection in heterogeneous networks, called AsymRP. AsymRP, a convergecast routing protocol, assumes 2-hop neighborhood knowledge and uses implicit and explicit acknowledgment. It takes advantage of asymmetric links to ensure reliable data collection.