Topology Management in wireless sensor networks

Wireless sensor networking is ingratiating itself into almost every area of human endeavors. Its drivers include its usages, improvements in microelectronics and manufacturing techniques. The network is made up of multiple tiny sensor nodes deployed in the area to be sensed, with nodes having processing, communicating, and sensing capabilities that enable them to perform their function collaboratively. Nodes sense events and transmit their data to the sink directly or through intermediate nodes acting as relay.Despite all the tremendous advances that have been made on this technology over the past few years, energy has not kept pace. This is based mostly on the fact that battery is its main source of energy. Furthermore, some applications of the network may preclude batteries from either being recharged or changed after deployment.A renowned solution to energy efficiency is duty cycling. This is the periodic or aperiodic placing of a node in an active and an inactive state. This introduces network performance issues of availability, latency, and packet delivery ratio, all linked to the fact that once a node is inactive or off, it is unavailable to communicate. It is therefore important to look for means of still applying duty cycling yet not losing out in availability, latency, and packet delivery ratio.In this dissertation we employ duty cycle on topology management to extend the network lifetime. We propose five algorithms to build various topologies that we divide into two classes. The first class enables nodes to arrange themselves into repetitive and interleaving sets. That is, nodes in the same set repeat themselves on the ground such that a set spans the entire area to be sensed. The second class of algorithms arranges nodes in continuous successive sets with members of a set covering a transmission range. We demonstrate the set formation experimentally.Building on the continuous set formation we propose two algorithms that build disjoint virtual backbone networks, with the disjointedness used for activity scheduling. We then measure the performances of the algorithms notably the approximation ratio and find it quite low (in the order of 3.5) compared to what is obtained in the literature.Finally, we propose a sleep and relay protocol that works on these topologies. Nodes sleep in sets and the activeness is relayed between sets. We evaluate the performance of this protocol and confirm that it actually leads to increase energy savings while not deteriorating other network performance metrics, like latency and packet delivery ratio.
La mise en réseau de capteurs sans fil s'intègre dans presque tous les domaines des activités humaines. Les moteurs de cette technologie comprennent ses domaines d'application et les améliorations des techniques de fabrication microélectroniques. Le réseau est constitué de plusieurs nœuds de capteurs de petite taille déployés dans la zone à détecter. Les nœuds ont des capacités de traitement, de communication et de détection qui leur permettent d'exécuter leur fonction de manière collaborative. Ils détectent les événements et transmettent les informations à un puits directement ou via des nœuds intermédiaires servant de relais.Des progrès considérables ont été réalisés sur cette technologie au cours des dernières années, cependant la gestion de l’énergie n’a pas connu la même évolution. Ceci est principalement dû au fait que la batterie est la principale source d'énergie. De plus, l’environnement du réseau peut empêcher les batteries d'être rechargées ou changées après le déploiement.Une solution classique à ce problème d'efficacité énergétique réside dans la gestion des cycles d’activation. Il s'agit d’alterner, de façon périodique ou non, les états actif et inactif des nœuds. Cela introduit des problèmes de performances réseaux en termes de disponibilité, de latence et de taux d’acheminement des paquets, car les nœuds inactifs ne participent pas aux communications. Il est donc important de trouver des solutions permettant d’utiliser les cycles d’activation tout en garantissant la disponibilité et en réduisant la latence et le taux de perte de paquets.Dans cette thèse, nous utilisons le cycle d’activation en combinaison avec la gestion de la topologie pour prolonger la durée de vie du réseau. Nous proposons cinq algorithmes pour construire différentes topologies que nous divisons en deux classes. La première classe organise les nœuds en ensembles de manière répétitive et entrelacée. C'est-à-dire que les nœuds appartenant à différents ensembles sont intercalés de manière à assurer la continuité des communications. La seconde classe d'algorithmes organise les nœuds en ensembles successifs en couronne. Nous avons montré expérimentalement la construction des différents ensembles.En utilisant la construction successive d’ensembles, nous proposons deux algorithmes qui construisent des réseaux dorsaux (backbones) virtuels disjoints pouvant être activés alternativement. Une évaluation des algorithmes fait ressortir leur efficacité, avec notamment un facteur d’approximation faible (de l’ordre de 3.5) en comparaison avec ceux des travaux de la littérature.Nous proposons ensuite un protocole basé sur les mécanismes de sommeil et relais sur ces topologies. Les périodes d’activité/inactivité sont définies par ensemble. Les résultats expérimentaux montrent que ce protocole permet une économie d’énergie sans dégrader les critères de performance tels que la latence et le taux d’acheminement des paquets.