Multi-constrained QoS Routing and Energy Optimization for Wireless Sensor Networks
Routage avec QoS multi-contraintes et optimisation de l'énergie pour réseaux de capteurs sans fil
Résumé
In this thesis, we focus on routing protocols for Wireless Sensor Networks (WSNs). The main research problems in the domain of routing data packets in a multi-hop network are the optimisation of the energy and the routing under multi-criteria QoS constraints (e.g., energy, reliability, delay, …). To address these problems, this dissertation proposes two contributions. Firstly, an optimal probabilistic routing protocol which balances the usage of energy and secondly, a routing protocol which is able to simultaneously take into account multiple QoS metrics. In fact, for balancing the energy consumption between the multiple existing links, the existing probabilistic routing protocols assign a probability to each link, either in an empirical way or depending on proportional energy level of the path. We did not know what are the optimal probabilities which lead to the optimal network lifetime. Our first contribution proposes optimal probabilities by modeling and solving a linear programming problem. As for the multi-constrainted QoS routing problem, multiple metrics are defined by RPL (a standard of IETF) but the existing protocols chose paths either according to only one metric or using a single aggregated function with multiple metrics, but never all the metrics simultaneously. In this dissertation, we first evaluate the performance of the operator calculus algebra introduced by R. Schott and S. Staples which defines an efficient algorithm allowing to find all the paths which satisfy the multiple constraints in a graph, and secondly we proposed a distributed version of this algorithm based on which a routing protocol has been designed. Both contributions are implemented in Contiki environment and simulated/emulated under Cooja (a software designed for simulating protocols of WSNs)
La thèse porte sur la conception de protocoles de routage pour les réseaux de capteurs. Les problèmes de recherche du routage de données dans un réseau multi-sauts sont d’une part l’optimisation de l’énergie et d’autre part le routage sous contraintes de la qualité de service (QoS) multicritères (e.g., énergie, fiabilité, délai, …). Cette thèse apporte deux contributions par rapport à l’état de l’art : une optimisation d'un protocole de routage probabiliste pour l'équilibre de l'usage d'énergie et un protocole de routage capable de prendre en compte simultanément des métriques de QoS multiples. En effet, pour équilibrer la consommation de l’énergie du routage lorsque des chemins multiples existent, les protocoles de routage probabiliste existants affectent une probabilité de choix à chaque chemin, soit de façon empirique, soit proportionnelle au niveau de l’énergie disponible du chemin. Nous ne savions pas quelles sont les probabilités optimales qui permettent d’avoir la durée de vie maximale du réseau. Cette thèse a permis d’établir ces probabilités optimales à l’aide de la modélisation sous forme d’un problème d’optimisation linéaire. Quant au problème du routage multicritères, bien que des métriques multiples soient définies par RPL (un standard d’IETF), les protocoles existants choisissent la route soit sur une métrique, soit sur une fonction de coût combinant plusieurs (qui introduit par conséquent un biais de pondération), mais jamais plusieurs simultanément. Dans cette thèse, nous avons d’abord évalué numériquement les performances de l’approche « operator calculus algebra » introduit par R. Schott et S. Staples qui définit un algorithme efficace permettant de trouver tous les chemins satisfaisant les contraintes multiples dans un graphe , puis dérivé une version distribuée sur laquelle nous avons conçu un protocole de routage multi-métriques. Ces deux contributions ont été implémentées dans l’environnement Contiki et émulées/simulées sous Cooja (un logiciel permettant de simuler des protocoles des réseaux de capteurs)
Origine : Version validée par le jury (STAR)
Loading...