Joint Routing and STDMA-based Scheduling to Minimize Delays in Grid Wireless Sensor Networks

In this report, we study the issue of delay optimization and energy efficiency in grid wireless sensor networks (WSNs). We focus on STDMA (Spatial Reuse TDMA)) scheduling, where a predefined cycle is repeated, and where each node has fixed transmission opportunities during specific slots (defined by colors). We assume a STDMA algorithm that takes advantage of the regularity of grid topology to also provide a spatially periodic coloring ("tiling" of the same color pattern). In this setting, the key challenges are: 1) minimizing the average routing delay by ordering the slots in the cycle 2) being energy efficient. Our work follows two directions: first, the baseline performance is evaluated when nothing specific is done and the colors are randomly ordered in the STDMA cycle. Then, we propose a solution, ORCHID that deliberately constructs an efficient STDMA schedule. It proceeds in two steps. In the first step, ORCHID starts form a colored grid and builds a hierarchical routing based on these colors. In the second step, ORCHID builds a color ordering, by considering jointly both routing and scheduling so as to ensure that any node will reach a sink in a single STDMA cycle. We study the performance of these solutions by means of simulations and modeling. Results show the excellent performance of ORCHID in terms of delays and energy compared to a shortest path routing that uses the delay as a heuristic. We also present the adaptation of ORCHID to general networks under the SINR interference model.Dans ce rapport , nous étudions l'optimisation des délais et l'fficacité én- ergétique dans réseau des réseaux de capteurs sans fil (WSNs). Nous nous concentrons sur l'ordonnancement STDMA (Spatial Reuse TDMA)). STDMA se base sur la répétition d'un cycle où chaque noeud a un slot pour transmettre ses données (ces slots sont définis par les couleurs). Nous supposons un algorithme d'ordonnancement STDMA qui tire avantage de la régularité de la topologie de réseau en grille pour fournir également un coloriage spatialement périodique (obtenu en répétant un certain motif de couleurs). Dans ce cadre, les principaux défis sont les suivants: 1) réduire au minimum les délais de routage en ordonnant les slots sur le cycle de façon efficace. 2) tout en étant économe en énergie. Notre travail suit deux directions: d'abord, la performance de solutions de base c'est à dire, quand rien de précis est fait et les couleurs sont ordonnées arbitrairement sur le cycle STDMA. Ensuite, nous proposons une solution appelée ORCHID ("Optimized Routing and sCHeduling in grID wireless sensor networks") qui délibérément construit un ordonnancement STDMA efficace. ORCHID procède en deux étapes. Dans la première étape, ORCHID part d'une grille colorée et construit un routage hiérarchique basé sur ces couleurs. Dans la deuxième étape, ORCHID ordonne les couleurs sur le cycle STDMA en considérant conjointement le routage et l'ordonnancement dans le but de permettre à tout noeud d'atteindre le puits en un seul cycle. Nous étudions les performances de ces solutions par modélisation et simulation. Les résultats montrent les performances excellentes de ORCHID en termes d'économie d'énergie et des délais comparé au routage basé sur les plus courts chemins et utilisant le délai comme métrique. Nous présentons aussi l'adaptation de ORCHID aux graphes quelconques sous le modèle SINR