[Truncated abstract] This thesis develops a scheduled protocol (time division multiple access, TDMA) called flexible-schedule-based TDMA Protocol (FlexiTP), to address the problem of providing end-to-end guarantees on data delivery, whilst also respecting severe resource constraints of wireless sensor networks. FlexiTP achieves this balance through a distributed, synchronised, and loose slot structure in which sensor nodes can build, modify, or extend their schedules based on their local information. In FlexiTP, it is not necessary to predetermine the number of slots required for a network. FlexiTP's local repair scheme allows nodes to adjust their schedules dynamically and autonomously to recover from node and communication faults. Hence, it maintains a reliable and selforganising multihop network. Most sensor network protocols designed for data gathering applications implicitly assume a periodic rate of data collection from all nodes in the network to the base station. However, nodes may want to report their data more rapidly or slowly depending on the significance and importance of their data to the end-user. The problem is that traditional TDMA-based protocols are not flexible to changes in traffic patterns because of their rigid slot structure schemes. This thesis aims to solve this problem by developing an ondemand TDMA slot transfer method that leverages the flexible-slot structure algorithm of FlexiTP to transfer time slots from one part of the network to another part. ... While these communication patterns are sufficient for monitoring applications, individual sensor nodes may need to send their data to multiple destination nodes across the network in order to execute a distributed cooperative-function based on their local environment. This peer-to-peer communication pattern makes sensor networks more reactive to triggers from the environment. This thesis attempts to solve the problem of lack of peer-to-peer communication in the design of a TDMA-driven protocol by extending the idea of on-demand TDMA slot transfer method to allow each sensor node in the network to claim extra time slots to communicate with any other nodes (peers) in the network, without going through the base station. Nodes in the network may have different priorities of data because of event-triggering sensor readings or various types of sensor readings (e.g., light, temperature, and humidity) they provide. When nodes with high priority packets increase the frequency of their data collections, the network bandwidth may be dominated by these nodes. It is desirable to allow nodes with low priority packets to aggregate their packets and so enabling these nodes to send their data to the base station under the current available network bandwidth. This thesis proposes an on-demand data aggregation algorithm that enables sensor nodes to perform an in-network-aggregation based on their current sensing requirements and network capacity constraints. In summary, this thesis describes the design, implementation, and evaluation of protocols for wireless sensor networks that focus on achieving energy-efficiency, provisioning performance assurances, and supporting reactivity and adaptability in constantly changing environment.

Neste trabalho propomos e analisamos algoritmos de alocação dinâmica de banda para rede óptica passiva (PON) de acesso padrão GPON (Gigabit PON). Estes algoritmos utilizam dados oriundos de SLA (service level agreement) para gerenciar a alocação de banda e classificar em 4 contêineres de tráfego (T-CONT) o tráfego gerado em 16 ONUs (optical network unit). Na transmissão upstream é utilizada a técnica de multiplexação por divisão de tempo (TDM) para gerenciar o acesso ao meio, evitando colisões. O primeiro algoritmo proposto aloca banda garantida para as ONUs e distribui a banda não utilizada de acordo com critério baseado em três SLAs. A taxa de bit upstream é 1,25 Gbps e o desempenho do algoritmo é analisado com base na variação do atraso de pacotes em função do tráfego gerado nas ONUs. O segundo algoritmo proposto utiliza ponderação de tráfego. Neste, analisamos o comportamento dos atrasos e a quantidade de banda solicitada e atendida por ONU quando as bandas garantida e extra são alteradas. Por fim, acrescentamos em nossa implementação um intervalo para o processamento do algoritmo de alocação dinâmica de banda (DBA) e resposta do hardware relacionado ao ciclo de interrogação. Então, analisamos o atraso de pacotes quando variamos o intervalo de processamento do DBA. Ao final, propomos uma solução preliminar para minimizar estes atrasos. Os resultados obtidos por meio de simulação computacional mostram a versatilidade dos algoritmos. / In this work we propose and analyze the performance of dynamic bandwidth allocation algorithms for optical passive networks (PON) in GPON standard (Gigabit PON). These algorithms use data from SLA (service level agreement) to manage bandwidth allocation and classify in 4 traffic containers (T-CONT) the traffic generated by 16 ONUs (optical network unit). In the upstream transmission the time division multiplexing (TDM) technique is used to manage the medium access, avoiding collisions. The first proposed algorithm allocates guaranteed bandwidth for the ONUs and distributes the bandwidth not used according to the criteria based on three SLAs. The upstream bit rate is 1.25 Gbps and the algorithm performance is analyzed based on the packets delay variation versus the traffic generated by ONUs. The second proposed algorithm uses weighted traffic. In this, we analyze the delay performance and the required bandwidth for each ONU and how much it is served when the guaranteed and extra bandwidth are changed. Finally, we added in our implementation an interval for the processing of the dynamic bandwidth allocation algorithm (DBA) and response of the hardware related to the interrogation cycle. In the end, we propose a preliminary solution to minimize these delays. The results obtained by means of computational simulation show the versatility of the algorithms.

No description available.

Le but principal des réseaux mesh sans fil (Wireless Mesh Networks-WMNs) est de fournir une dorsale de communication pour un grand nombre d'utilisateurs, car les WMNs doivent supporter un trafic énorme. Dans cette thèse, nous visons la maximisation d'utilisation et la répartition équitable de la bande passante dans les WMNs. Nous considérons deux environnements : WMN utilisant la norme IEEE 802.11 MAC, qui est caractérisée par son déploiement répandu et peu cher, et WMN utilisant les antennes directionnelles, qui représentent une technologie clé pour la réutilisation spatiale dans les réseaux sans fil. Pour les WMMs basés sur IEEE 802.11, nous concevons NICC, un protocole de contrôle de congestion qui reconnaît la congestion comme un problème lié au voisinage, et non pas au lien. NICC gère la congestion par une collaboration entre les nœuds d’un voisinage sans fil. En faisant usage de certains champs sous-exploités dans l'en-tête IEEE 802.11, NICC fournit un retour de congestion implicite et multi-bit. Ceci assure un contrôle précis du trafic sans affecter la bande passante. Pour les WMNs utilisant les antennes directionnelles, nous concevons FreeDMAC, un protocole MAC basé sur la technologie TDMA. FreeDMAC garantit que chaque nœud est conscient de toutes les transmissions dans son voisinage, ce qui évite les problèmes MAC causés par les antennes directionnelles, et ainsi, améliore l'utilisation de la bande passante. En outre, FreeDMAC est capable de fournir deux niveaux d’équité: équité entre les liens et équité entre les flux / The main purpose of Wireless Mesh Networks (WMNs) is to provide a communication backbone for a high number of end-users, thus WMNs have to support heavy traffic load. In this thesis, we intend to maximize utilization and achieve fair allocation of the bandwidth resources in WMNs. We consider two WMN environments: WMN using the IEEE 802.11 MAC standard, which is characterized by its cheap devices and widespread deployment, and WMN using directional antennas, which are emerged as an attractive technology to enhance the spatial reusability in wireless networks. For WMM based on IEEE 802.11, we design NICC, a congestion control scheme that recognizes congestion as neighborhood-related problem, and not a link-based one. Indeed, complex interference among neighboring nodes is the main starvation cause in WMNs. Therefore, NICC handles congestion using mutual cooperation within a wireless neighborhood. NICC makes use of some underexploited fields in the IEEE 802.11frame header in order to provide an implicit multi-bit congestion feedback, and thus ensure accurate rate control without generating overhead, making efficient use of bandwidth. For WMN with directional antennas, we design FreeDMAC, a TDMA-based MAC scheme with contention-free scheduling. FreeDMAC guarantees that each node is aware of all ongoing transmissions in its neighborhood, and thus avoids directional-related problems such as deafness, making efficient use of bandwidth. Moreover, FreeDMAC presents a link-slot assignment that provides two levels of fairness: Per-link and per-flow fairness

Les réseaux mesh sans fil (Wireless Mesh Networks-WMNs) sont des réseaux facilement déployables et à faible coût qui peuvent étendre l’Internet dans des zones où les autres réseaux peuvent difficilement accéder. Cependant, plusieurs problèmes de qualité de service (QoS) et de sécurité freinent le déploiement à grande échelle des WMNs. Dans cette thèse, nous proposons un modèle de contrôle d’admission (CA) et un système de réputation afin d’améliorer les performances du réseau mesh et de le protéger des nœuds malveillants. Notre système de CA vise à assurer la QoS des flux admis dans le réseau en termes de bande passante et de délai tout en maximisant l’utilisation de la capacité du canal. L’idée de notre solution est d’associer au contrôle d’admission une planification de liens afin d’augmenter la bande passante disponible. Nous proposons également un système de réputation ayant pour but de détecter les nœuds malveillants et de limiter les fausses alertes induites par la perte de paquets sur les liens du réseau. L’idée de notre solution est d’utiliser des tests statistiques comparant la perte de paquets sur les liens avec un modèle de perte préétabli. De plus, il comprend un système de surveillance composé de plusieurs modules lui permettant détecter un grand nombre d’attaques. Notre CA et notre système de réputation ont été validés, les résultats montrent qu’ils atteignent tous deux leurs objectifs / Wireless mesh networks (WMNs) are a very attractive new field of research. They are low cost, easily deployed and high performance solution to last mile broadband Internet access. However, they have to deal with security and quality of service issues which prevent them from being largely deployed. In order to overcome these problems, we propose in this thesis two solutions: an admission control with links scheduling and a reputation system which detects bad nodes. These solutions have been devised in order to further merge into a secure admission control. Our admission control schedules dynamically the network’s links each time a new flow is accepted in the network. Its goal is to accept only flows which constraints in terms of delay and bandwidth can be respected, increase the network capacity and decrease the packet loss. Our reputation system aims at assigning each node of the network a reputation which value reflects the real behavior of the node. To reach this goal this reputation system is made of a monitoring tool which can watch many types of attacks and consider the packet loss of the network. The evaluations of our solutions show that they both meet their objectives in terms of quality of service and security

L'objectif général de cette thèse était de proposer une solution de localisation en intérieur à la fois simple et capable de surmonter les défis de la propagation dans les environnements en intérieur. Pour ce faire, un système de localisation basé sur la méthode des signatures et adoptant le temps d'arrivée du signal de l'émetteur au récepteur comme signature, a été proposé. Le système présente deux architectures différentes, une première orientée privée utilisant la méthode d'accès multiple à répartition par code et une deuxième centralisée basée sur la méthode d'accès multiple à répartition dans le temps. Le système calcule la position de l'objet d'intérêt par la méthode de noyau. Une comparaison expérimentale entre le système à architecture orientée privée et un système de localisation sonore déjà existant et basé sur la méthode de trilatération, a permis de confirmer les résultats trouvés dans le cas de la localisation par ondes radiofréquences. Cependant, nos expérimentations étaient les premières à montrer l'effet de la réverbération sur les approches de la localisation acoustique. Dans un second lieu, un système de localisation basé sur la technique de retournement temporel, permettant une localisation simultanée de sources avec différentes précisions, a été testé par simulations en faisant varier le nombre de sources. Ce système a été ensuite validé par expérimentations. Dans la dernière partie de notre étude, nous nous sommes intéressés à la réduction de l'audibilité du signal utile à la localisation par recours à la psycho-acoustique. Un filtre défini à partir du seuil d'audition absolu a été appliqué au signal de localisation. Nos résultats ont montré une amélioration de la précision de localisation comparé au système de localisation sans modèle psycho-acoustique et ce grâce à l'utilisation d'un filtre adapté au modèle psycho-acoustique à la réception. Par ailleurs, l'écoute du signal après application du modèle psycho-acoustique a montré une réduction significative de son audibilité comparée à celle du signal original. / The objective of this PhD is to propose a location solution that should be simple and robust to multipath that characterizes the indoor environments. First, a location system that exploits the time domain of channel parameters has been proposed. The system adopts the time of arrival of the path of maximum amplitude as a signature and estimates the target position through nonparametric kernel regression. The system was evaluated in experiments for two main configurations: a privacy-oriented configuration with code-division multiple-access operation and a centralized configuration with time-division multiple-access operation. A comparison between our privacy-oriented system and another acoustic location system based on code-division multiple-access operation and lateration method confirms the results found in radiofrequency-based localization. However, our experiments are the first to demonstrate the detrimental effect that reverberation has on acoustic localization approaches. Second, a location system based on time reversal technique and able to localize simultaneously sources with different location precisions has been tested through simulations for different values of the number of sources. The system has then been validated by experiments. Finally, we have been interested in reducing the audibility of the localization signal through psycho-acoustics. A filter, set from the absolute threshold of hearing, is then applied to the signal. Our results showed an improvement in precision, when compared to the location system without psychoacoustic model, thanks to the use of matched filter at the receiver. Moreover, we have noticed a significant reduction in the audibility of the filtered signal compared to that of the original signal.

A wireless sensor network (WSN) is a collection of sensor nodes distributed over a geographical region to obtain the environmental data. It can have different types of applications ranging from low data rate event driven and monitoring applications to high data rate real time industry and military applications. Energy efficiency and reliability are the two major design issues which should be handled efficiently at all the layers of communication protocol stack, due to resource constraint sensor nodes and erroneous nature of wireless channel respectively. Media access control (MAC) is the protocol which deals with the problem of packet collision due to simultaneous transmissions by more than one neighboring sensor nodes. Time Division Multiple Access based (TDMA-based) and contention-based are the two major types of MAC protocols used in WSNs. In general, the TDMA-based channel access mechanisms perform better than the contention-based channel access mechanisms, in terms of channel utilization, reliability and power consumption, specially for high data rate applications in wireless sensor networks (WSNs). TDMA-based channel access employs a predefined schedule so that the nodes can transmit at their allotted time slots. Based on the frequency of scheduling requirement, the existing distributed TDMA-scheduling techniques can be classified as either static or dynamic. The primary purpose of static TDMA-scheduling algorithms is to improve the channel utilization by generating a schedule of smaller length. But, they usually take longer time to generate such a schedule, and hence, are not suitable for WSNs, in which the network topology changes dynamically. On the other hand, dynamic TDMA-scheduling algorithms generate a schedule quickly, but they are not efficient in terms of generated schedule length. We suggest a new approach to TDMA-scheduling for WSNs, that can bridge the gap between these two extreme types of TDMA-scheduling techniques, by providing the flexibility to trade-off between the schedule length and the time required to generate the schedule, as per the requirements of the underlying applications and channel conditions. The suggested TDMA-scheduling works in two phases. In the first phase, we generate a valid TDMA schedule quickly, which need not have to be very efficient in terms of schedule length. In the second phase, we iteratively reduce the schedule length in a manner, such that the process of schedule length reduction can be terminated after the execution of an arbitrary number of iterations, and still be left with a valid schedule. This step provides the flexibility to trade-off the schedule length with the time required to generate the schedule. In the first phase of above TDMA-scheduling approach, we propose two randomized, distributed and parallel TDMA-scheduling algorithms viz., Distributed TDMA Slot Scheduling (DTSS) and Randomized and Distributed TDMA (RD-TDMA) scheduling algorithm. Both the algorithms are based on graph coloring approach, which generate a TDMA schedule quickly with a fixed schedule length ( Colouring), where is the maximum degree of any node in the graph to be colored. The two algorithms differ in the channel access mechanism used by them to transmit control messages, and in the generated schedule for different modes of communication, i.e., unicast, multicast and broadcast. The novelty of the proposed algorithms lies in the methods, by which an uncolored node detects that the slot picked by it is different from the slots picked by all the neighboring nodes, and the selection of probabilities with which the available slots can be picked up. Furthermore, to achieve faster convergence we introduce the idea of dynamic slot-probability update as per which the nodes update their slot-probability by considering the current slot-probability of their neighboring nodes. Under the second phase of the proposed TDMA-scheduling approach, we provide two randomized and distributed schedule compaction algorithms, viz., Distributed Schedule Compaction (DSC) and Distributed Schedule Length Reduction (DSLR) algorithm, as the mechanism to trade-off the scheduling time with the generated schedule length. These algorithms start with a valid TDMA schedule and progressively compress it in each round of execution. Additionally, Furthermore, the execution of these algorithms can be stopped after an arbitrary number of rounds as per the requirements of underlying applications. Even though TDMA-based MAC protocols avoid packet loss due to collision, due to erroneous nature of wireless medium, they alone are not sufficient to ensure the reliable transmission in WSNs. Automatic Repeat reQuest (ARQ) is the technique commonly used to provide error control for unicast data transmission. Unfortunately, ARQ mechanisms cannot be used for reliable multicast/broadcast transmission in WSNs. To solve this issue, we propose a virtual token-based channel access and feedback protocol (VTCAF) for link level reliable multicasting in single-hop wireless networks. The VTCAF protocol introduces a virtual (implicit) token passing mechanism based on carrier sensing to avoid the collision between feedback messages. The delay performance is improved in VTCAF protocol by reducing the number of feedback messages. Besides, the VTCAF protocol is parametric in nature and can easily trade-off reliability with the delay as per the requirements of the underlying applications. Finally, by integrating all the works, viz., TDMA-scheduling algorithms (DTSS/RD-TDMA), schedule compaction algorithms and link layer feedback mechanism for reliable multicast/ broadcast, we propose a TDMA-based energy aware and reliable MAC protocol, named TEA-MAC for multi-hop WSNs. Similar to VTCAF, TEA-MAC protocol uses the combination of ACK-based and NACK-based approaches to ensure reliable communication. But, instead of using virtual token-based channel access, it uses contention-based channel access for NACK transmission. All the algorithms and protocols proposed in this thesis are distributed, parallel and fault tolerant against packet losses to support scalability, faster execution and robustness respectively. The simulations have been performed using Castalia network simulator to evaluate the performance of proposed algorithms/protocols and also to compare their performance with the existing algorithms/protocols. We have also performed theoretical analysis of these algorithms/protocols to evaluate their performance. Additionally, we have shown the correctness of proposed algorithms/protocols by providing the necessary proofs, whenever it was required. The simulation results together with theoretical analysis show that, in addition to the advantage of trading the runtime with schedule length, the proposed TDMA scheduling approach achieves better runtime and schedule length performance than existing algorithms. Additionally, the TEA-MAC protocol is able to considerably improve the reliability and delay performance of multicast communication in WSNs.