Wireless Self-adaptive Ad hoc and Sensor Networks : Energy Efficiency and Spatial Reuse
Institution:
Paris 6Disciplines:
Directors:
Abstract EN:
The need to maximize network lifetime in wireless ad hoc networks and especially in wireless sensor networks requires the use of energy efficient algorithms and protocols. Motivated by the fact that a node consumes the least energy when its radio is in sleep state, we achieveenergy efficiency by scheduling nodes activity. Nodes are assigned time slots during which they can transmit and they can turn off their radio when they are neither transmitting nor receiving. Compared to classical TDMA-based medium access scheme, spatial bandwidth use is optimized: non interfering nodes are able to share the same time slots, collisions are avoided and overhearing and interferences are reduced. In our work about time slots assignment, two cases are studied. First, when nodes require equal channel access, we use node coloring. Second, when nodes have heterogeneous traffic demands, we designed the traffic aware time slot assignment algorithm TRASA. Unlike the majority of previous works, we generalize the definition of node coloring and slot allocation problems. Indeed, we set the maximum distance between two interfering nodes as a parameter of these problems. We prove that they are NP-complete, making heuristic approaches inevitable in practice. A central directive of this thesis is to design self-adaptive solutions. This adaptivity concerns many aspects such as the mission given by the application, the heterogeneity of nnode traffic demands, the network density, the regularity of network topology, and the failure of wirelesslinks.
Abstract FR:
La nécessité de maximiser la durée de vie du réseau sans fil dans les réseaux ad hoc et en particulier dans les réseaux de capteurs sans fil nécessite l'utilisation d'algorithmes d'efficacité énergétique. Motivée par le fait qu'un noeud consomme le moins d'énergie lorsqu’il est en veille, nous réalisons l'efficacité énergétique vi des algorithmes d'ordonnancement des activités des noeuds. Les noeuds reçoivent des slots temporels durant lesquels ils peuvent transmettre et ils peuvent éteindre leur radio quand ils ne sont ni en train de transmettre, ni en train de recevoir. Par rapport au TDMA classique, l’utilisation de la bande passante est optimisée: deux noeuds interférents ne partagent pas les mêmes slots. Dans notre travail sur l’ordonnancement, deux cas sont étudiés. Tout d'abord, lorsque les nœuds nécessitent le même temps d’accès au canal, nous utilisons le coloriage des nœuds. Deuxièmement, lorsque les nœuds requièrent des débits hétérogènes, nous utilisons une allocation de slots « traffic aware ». Contrairement à la majorité des travaux antérieurs, nous généralisons la définition du coloriage des noeuds et les problèmes d'attribution des slots. En effet, nous considérons que la distance maximale entre deux nœuds interférents est un paramètre de ces problèmes. Nous prouvons qu'ils sont NP-complets, ce qui rend inévitable l’utilisation des heuristiques dans la pratique. Une directive centrale de cette thèse est de concevoir des solutions auto-adaptatives. Cette adaptabilité concerne de nombreux aspects tels que la mission confiée par l'application, l'hétérogénéité des demandes de trafic de nœuds, la densité du réseau, de la régularité de la topologie du réseau, et la non fiabilité des liens sans fil.