We study the scheduling problem for data collection from sensor nodes to the sink node in wireless sensor networks, also referred to as the convergecast problem. The convergecast problem in general network topology has been proven to be NP-hard. In this paper, we propose our heuristic algorithm (finding the minimum scheduling time for convergecast (FMSTC)) for general network topology and evaluate the performance by simulation. The results of the simulation showed that the number of time slots to reach the sink node decreased with an increase in the power. We compared the performance of the proposed algorithm to the optimal time slots in a linear network topology. The proposed algorithm for convergecast in a general network topology has 2.27 times more time slots than that of a linear network topology. To the best of our knowledge, the proposed method is the first attempt to apply the optimal algorithm in a linear network topology to a general network topology.

La technologie des réseaux de capteurs sans fil (RCSF) est l’un des éléments constitutifs de l’Internet des objets (IoT). En raison de leurs caractéristiques de déploiement facile et de leur flexibilité, ils sont utilisés dans de nombreux domaines d’application. Les réseaux à faible consommation et à perte (LLN) sont un type spécial de WSN dans lequel les noeuds sont largement limités en ressources. Convergecast est l’un des modes de communication de base, dans lequel tout le trafic du réseau est destiné à une destination prédéfinie appelée collecteur. Tout en prenant en compte les domaines d’applications IoT, convergecast n’est pas le seul mode de communication sur le réseau. Le récepteur doit envoyer des commandes à certains capteurs pour effectuer des actions. Dans cette application, anycast est un autre mode de communication de base. Dans anycast, le trafic provenant du récepteur est destiné à tout membre d’un groupe de récepteurs potentiels du réseau.Les LLN sont formés de noeuds de capteurs statiques et changent rarement de position. En raison des contraintes de ressources strictes imposées au calcul, à l’énergie et à la mémoire des LLN, la plupart des protocoles de routage ne prennent en charge que les réseaux statiques. Cependant, la mobilité est devenue une exigence importante pour de nombreuses applications émergentes. Dans ces applications, certains noeuds sont libres de se déplacer et de s’organiser dans un réseau connecté. La topologie changerait continuellement en raison du mouvement des noeuds et de l’instabilité des liaisons radio. Il s’agit d’une tâche difficile pour la plupart des protocoles de routage des réseaux LLN afin de s’adapter rapidement au mouvement et de reconstruire la topologie en temps voulu. Le but de cette thèse est de proposer un support de mobilité efficace pour les protocoles de routage dans les réseaux LLN. Nous nous concentrons sur convergecast et anycast, qui sont les modes de communication les plus utilisés dans les réseaux LLN, dans les scénarios de réseau mobile. Nous proposons un mécanisme d’amélioration, nommé RL (RSSI and Level),pour prendre en charge les protocoles de routage dans les réseaux LLN convergecast en mobilité. Ce mécanisme aide le protocole de routage à prendre des décisions plus rapides pour la détection de la mobilité et la mise à jour des voisins du saut suivant,mais souffre d’une surcharge importante. Nous proposons une gestion dynamique des messages de contrôle pour améliorer les performances de RL et l’implémentons en plus du protocole de routage pour réseau à faible consommation (RPL) et nous l’avons nommé RRD (RSSI, Rank and Dynamic). Après une prise en compte de l’hystérésis de la zone de couverture de la plage de transmission des noeuds, nousavons optimisé RRD. Cette version améliorée s’appelle RRD +. Sur la base de RRD+, nous avons proposé MRRD + (Multiple, RSSI, Rank et Dynamic) pour prendre en charge plusieurs puits dans les réseaux LLN convergecast en mobilité. ADUP (Adaptive Downward / Upward Protocol) est une solution de routage prenant en charge simultanément convergecast et anycast dans les réseaux LLN. Nous avons évalué les performances de nos contributions à la fois en simulation avec le simulateur Cooja et en expérience (uniquement pour ADUP) sur des motosTelosB. Les résultats obtenus en simulation et en expérience confirment l’efficacité de nos protocoles de routage. / Wireless Sensor Networks (WSNs) technology is one of the building blocks ofthe Internet of Things (IoT). Due to their features of easy deployment and flexibility,they are used in many application domains. Low-Power and Lossy Networks(LLNs) are a special type of WSNs in which nodes are largely resources constrained.For LLNs, convergecast is one of the basic traffic modes, where all traffic in the networkis destined to a predefined destination called the sink. While considering theIoT application domains, convergecast is not the only traffic mode in the network.The sink needs to send commands to certain sensors to perform actions. In this application,anycast is another basic traffic mode. In anycast, the traffic from the sinkis destined to any member of a group of potential receivers in the network.Traditionally LLNs are formed by static sensor nodes and rarely change positions.Due to the strict resource constraints in computation, energy and memory ofLLNs, most routing protocols only support static network. However, mobility hasbecome an important requirement for many emerging applications. In these applications,certain nodes are free to move and organize themselves into a connectednetwork. The topology would continuously change due to the movement of nodesand radio links instability. This is a hard task for most routing protocols of LLNs toadapt rapidly to the movement and to reconstruct topology in a timely manner.The goal of this thesis is to propose an efficient mobility support for routingprotocols in LLNs. We focus on convergecast and anycast, which are the most usedtraffic modes in LLNs, in mobile network scenarios.We propose an enhancement mechanism, named RL (RSSI and Level), to supportrouting protocols in convergecast LLNs in mobility. This mechanism helps routingprotocol make faster decisions for detecting mobility and updating next-hop neighborsbut suffers from high overhead. We propose a dynamic control message managementto enhance the overhead performance of RL and implement it on top ofRouting Protocol for Low-power and Lossy network (RPL) and we named it RRD(RSSI, Rank and Dynamic). After taking into account hysteresis of the coveragezone of the transmission range of nodes, we optimized RRD. This enhanced versionis called RRD+. Based on RRD+, we proposed MRRD+ (Multiple, RSSI, Rankand Dynamic) to support multiple sinks in convergecast LLNs in mobility. ADUP(Adaptive Downward/Upward Protocol) is a routing solution that supports bothconvergecast and anycast in LLNs concurrently.We evaluated the performance of our contributions in both simulation usingCooja simulator and experiment (only for ADUP) on TelosB motes. The resultsobtained in both simulation and experiment confirm the efficiency of our routingprotocols.

The Wireless Sensor Networks (WSNs) have emerged as a new paradigm for collecting and processing data from physical environments, such as wild life sanctuaries, large warehouses, and battlefields. Users can access sensor data by issuing queries over the network, e.g., to find what are the 10 highest temperature values in the network. Typically, a WSN operates by constructing a logical topology, such as a spanning tree, built on top of the physical topology of the network. The constructed logical topology is then used to disseminate queries in the network, and also to process and return the results of such queries back to the user. A major challenge in this context is prolonging the network's lifetime that mainly depends on the energy cost of data communication via wireless radios, which is known to be very expensive as compared to the cost of data processing within the network. In this research, we investigate some of the core problems that deal with the different aspects of in-network query processing in WSNs. In that context, we propose an efficient filtering based algorithm for the top-k query processing in WSNs. Through a systematic study of the top-k query processing in WSNs we propose several solutions in this thesis, which are applicable not only to the top-k queries, but also to in-network query processing problems in general. Specifically, we consider broadcasting and convergecasting, which are two basic operations that are required by many in-network query processing solutions. Scheduling broadcasting and convergecasting is another problem that is important for energy efficiency in WSNs. Failure of communication links, which are common in WSNs, is yet another important issue that needs to be addressed. In this research, we take a holistic approach to deal with the above problems while processing the top-k queries in WSNs. To this end, the thesis makes several contributions. In particular, our proposed solutions include new logical topologies, scheduling algorithms, and an overall sophisticated communication framework, which allows to process the top-k queries efficiently and with increased reliability. Extensive simulation studies reveal that our solutions are not only energy efficient, saving up to 50% of the energy cost as compared to the current state-of-the-art solutions, but they are also robust to link failures.

No description available.

Les Réseaux de Capteurs Sans Fil (RCSF) sont de plus en plus exploités par des applications diverses grâce à leur facilité de déploiement et d’auto-configuration. Les applications de collecte de données qui utilisent les RCSF ont souvent un profil convergecast : l’ensemble des données récoltées par tous les capteurs du réseau sont acheminées vers un puits de collecte, grâce à une communication multi-saut. Pendant l’acheminement des données des nœuds de collecte vers le puits, des goulots d’étranglement sont fréquemment observés, principalement au voisinage du puits. Cela est du à la congestion et au phénomène d’entonnoir couramment observé sur le trafic de données ayant un profile convergecast. Outre un risque accru de collision, cela entraîne le débordement des files d’attente des nœuds concernés conduisant à des pertes de données. Cette perte réduit le taux de livraison au puits entraînant une baisse du débit du réseau. Afin de réduire ces pertes et de permettre un meilleur taux de livraison au puits, le trafic doit être équitablement réparti au niveau de chaque saut pendant l’acheminement. Dans cette thèse, nous avons d’une part proposé S-CoLBA (Single channel Collaborative Load Balancing Algorithm), un protocole mono-canal de routage dynamique avec équilibrage de la charge. Sa métrique de routage est basée sur le délais moyen d’accès au medium radio par nœud. Chaque nœud choisit comme prochain saut à destination du puits, un de ses voisins ayant le délais d’accès le plus court. S-CoLBA intègre également une surveillance permanente des files d’attente des nœuds afin de prévenir la congestion et d’éviter le débordement de ces files. D’autre part, nous avons adapté S-CoLBA pour le rendre utilisable dans un réseau multicanal. Cette version du protocole s’appelle M-CoLBA (pour Mulitchannel CoLBA). M-CoLBA évite la congestion en équilibrant la charge grâce à une répartition du trafic au niveau de chaque saut du réseau. Dans un réseau multicanal, le problème de support de diffusion se pose. M-CoLBA introduit des périodes de synchronisations où tous les nœuds utilisent le même canal pour échanger les informations de routage. Ces périodes de synchronisation contribuent à allonger les délais de bout en bout des paquets. Nous avons ainsi optimisé M-CoLBA en "surchargeant" les acquittements des trames avec les informations de routage ( piggybacking) et les états des files d’attente. Cela évite de passer par des périodes de synchronisation pour diffuser ces informations. Cette version optimisée s’appelle ABORt ( Acknowledgement-Based opportunistic Routing protocol). Dans un cas de trafic de type convergecast, ABORt induit une diversité des routes prises par les données collectées, ce qui est bénéfique à la quantité de données transportées et à la robustesse de la solution. Les contributions ont été évaluées par simulation et expérimentation dans un réseau monocanal et multicanal. Les résultats montrent que nos contributions améliorent le taux de livraison des données au puits, optimisent le délais de bout en bout et réduisent la quantité de trafic de contrôle comparé à des solutions déjà existantes. / The popularity of wireless sensor networks (WSNs) is increasing due to their ease ofdeployment and auto-configuration capabilities. They are used in different applica-tion domains including data collection with convergecast scenarios. In convergecast,all data collected in the network is destined to one common node usually called thesink. In case of high carried traffic load and depending on the used routing policy,this many-to-one data collection leads to congestion and queue overflow mainly innodes located near the sink. Congestion and queue overflow reduce delivery ratiothat negatively affects the network efficiency.Wireless sensor nodes are resource constrained devices with limited buffers sizeto store and forward data to the sink. Introducing multichannel communication inWSNs helps to increase the carried traffic load thanks to allowing parallel data trans-mission and reduction of contention and interference. With high traffic load, thenumber of data packets travelling from leaf nodes towards the sink becomes higher.In case the routing scheme does not balance the traffic load, it will be unfairly dis-tributed between forwarding nodes. Thus, nodes that are in part of the routing will beoverloaded while others are less used. Overloaded nodes increase the risk of conges-tion and queue overflow leading to data loss that reduces the throughput. Therefore,we need to couple the routing protocols with traffic load balancing scheme in hightraffic load network scenarios.The goal of this thesis is to propose an efficient routing solution to prevent con-gestion and queue overflow in high data rate convergecast WSNs, in such a way, tooptimize data delivery ratio at the sink node.On the one hand, we proposed a single channel traffic load balancing routingprotocol, named S-CoLBA (Single channel Collaborative Load balancing routing).It relies on data queueing delay metric and best score (according to the value of themetric) next hop neighbors to fairly distribute traffic load in per hop basis in the net-work. Since the carried traffic load increases in multichannel communication, onthe other hand, we adapted our contribution to cope with multichannel WSNs andwe named it as Multichannel CoLBA (M-CoLBA). As broadcasting information isnot straightforward in multichannel, we optimize M-CoLBA to use piggybackingscheme for routing information sharing in the network. This enhanced version iscalled ABORt for Acknowledgement-Based opportunistic Routing protocol and re-lies on ACK frames to share routing information. Doing so helps to optimize dataframe end-to-end delay and to reduce the transmitted beacons in the network. ABORtfairly distributes traffic load in the network and avoids congestion and queue over-flow.We evaluated the performance of our contributions in both simulation using Con-tiki OS Cooja simulator and experiment (only for S-CoLBA) on TelosB motes. Ob-tained results in both simulation and experiment confirm the efficiency of our routingprotocols in term of packet delivery ratio and queue overflow compared to some ex-isting routing protocols in the literature.