Sensor technologies are vital today in gathering information about certain environments and wireless sensor networks are getting more widespread use everyday. These networks are characterized by a number of sensor nodes deployed in the field for the observation of some phenomena. Due to the limited battery capacity in sensor nodes, energy efficiency is a major and challenging problem in such power-constrained networks. Some of the network design parameters have a direct impact on the network&rsquo / s lifetime. These parameters have to be chosen in such a way that the network use its energy resources efficiently. This thesis studies these parameters that should be selected according to certain trade offs with respect to the network&rsquo / s lifetime. In this work, these trade offs have been investigated and illustrated in detail in various combinations. To achieve this goal, a special simulation tool has been designed and implemented in this work that helps in analyzing the effects of the selected parameters on sensor network&rsquo / s lifetime. OMNeT++, a discrete event simulator, provides the framework for the sensor network simulator&rsquo / s development. Ultimately, results of extensive computational tests are presented, which may be helpful in guiding the sensor network designers in optimally selecting the network parameters for prolonged lifetime.

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) / 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)

In this thesis, we consider wireless ad hoc and sensor networks where energy matters. Indeed, sensor nodes are characterized by a small size, a low cost, an advanced communication technology, but also a limited amount of energy. This energy can be very expensive, difficult or even impossible to renew. Energy efficient strategies are required in such networks to maximize network lifetime. We distinguish four categories of strategies: 1. Energy efficient routing, 2. Node activity scheduling, 3. Topology control by tuning node transmission power and 4. Reduction of the volume of information transferred. Our contribution deals with energy efficient routing and node activity scheduling. For energy efficient routing, the idea consists in reducing the energy spent in the transmission of a packet from its source to its destination, while avoiding nodes with low residual energy. The solution we propose, called EOLSR, is based on the link state OLSR routing protocol. We show by simulation that this solution outperforms the solution that selects routes minimizing the end-to-end energy consumption, as well as the solution that builds routes based on node residual energy. We then show how we can improve the benefit of energy efficient routing using cross layering. Informa- tion provided by the MAC layer improves the reactivity of the routing protocol and the robustness of routes. Moreover, taking into account the specificities of some applications like data gathering allows the routing protocol to reduce its overhead by maintaining routes only to the sink nodes. Concerning node activity scheduling, since the sleep state is the least power consuming state, our aim is to schedule node state between sleeping and active to minimize energy consumption while ensuring network and application functionalities. We propose a solution, called SERENA, based on node coloring. The idea is to assign a color to each node, while using a small number of colors and ensuring that two nodes with the same color can transmit without interfering. This color is mapped into a slot in which the node can transmit its messages. Consequently, each node is awake during its slot and the slots granted to its one-hop neighbors. It sleeps the remaining time. We show how this algorithm can adapt to different application requirements: broadcast, immediate acknowledgement of unicast transmissions... The impact of each additional requirement is evaluated by simulation. An originality of this work lies in taking into account real wireless propagation conditions. Color conflicts are then possible. A cross-layering approach with the MAC layer is used to solve these conflicts. We also show how cross-layering with the application layer can improve the coloring per- formance for data gathering applications. This work has been done for the ANR OCARI project whose aim is to design and implement a wireless sensor network for applications in harsh environments such as power plants and war- ships. The network layer including SERENA and EOLSR has been specified and is now under implementation.

In Wireless Sensor Networks, designing a low overhead routing protocol is crucial for prolonging network lifetime. Wireless sensor nodes depend on limited batteries and if they run out of battery, they cannot contribute to the sensing. There are lots of studies aimed at prolonging network lifetime. One of the methods to extend life time of the wireless sensor networks is clustering. In clustering approaches main aim is to prevent unnecessary messaging and decrease number of messages exchanged by aggregating messages. Clustering also contributes to prolong network life time by ruling the child node communications and therefore it decreases message loss caused by transmission collisions. Cluster heads in clusters schedule nodes for sending and receiving messages. In this thesis, a clustering approach based on queries disseminated by sinks is proposed. Two methods to prolong lifetime of sensor network by forming appropriate clusters and selecting suitable cluster heads is developed. Performance of the proposed methods is also evaluated with computer simulations.

Wireless sensor networks (WSN) are an emerging technology with a wide range of applications including environment monitoring, security and surveillance, health care, smart homes, etc. Subject to severe resource constraints in wireless sensor networks, in this research, we address the distributed estimation of unknown parameters by studying the correlation among resource, distortion, and lifetime, which are three major concerns for WSN applications. The objective of the proposed research is to design efficient distributed estimation algorithms for resource-constrained wireless sensor networks, where the major challenge is the integrated design of local signal processing operations and strategies for inter-sensor communication and networking so as to achieve a desirable tradeoff among resource efficiency (bandwidth and energy), system performance (estimation distortion and network lifetime), and implementation simplicity. More specifically, we address the efficient distributed estimation from the following perspectives: (i) rate-distortion perspective, where the objective is to study the rate-distortion bound for the distributed estimation and to design practical and distributed algorithms suitable for wireless sensor networks to approach the performance bound by optimally allocating the bit rate for each sensor, (ii) energy-distortion perspective, where the objective is to study the energy-distortion bound for the distributed estimation and to design practical and distributed algorithms suitable for wireless sensor networks to approach the performance bound by optimally allocating the bit rate and transmission energy for each sensor, and (iii) lifetime-distortion perspective, where the objective is to maximize the network lifetime while meeting estimation distortion requirements by jointly optimizing the source coding, source throughput and multi-hop routing. Also, energy-efficient cluster-based distributed estimation is studied, where the objective is to minimize the overall energy cost by appropriately dividing the sensor field into multiple clusters with data aggregation at cluster heads.

Améliorer la durée de vie est un enjeu important qui s'impose lors du déploiement des réseaux de capteurs sans fil (RCsFs). En effet, ces réseaux sont composés par des capteurs autonomes alimentés par des batteries qu'il est difficile de recharger ou remplacer. Le challenge est donc d'assurer le fonctionnement de ces réseaux pendant plusieurs années sans aucune intervention extérieure majeure.Afin de maximiser la durée de vie des RCsFs, nous avons d'abord exploré la possibilité d'introduire plusieurs puits mobiles. Nous avons proposé deux stratégies. La première détermine les positions optimales sur un réseau de petite échelle et la deuxième, basée sur une heuristique, garantit le passage à l'échelle.Nous nous sommes ensuite intéressés aux RCsFs basés sur IPv6 qui utilisent RPL, le nouveau protocole de routage proposé par l'IETF. Nous avons étudié ce protocole, étendu ses capacités pour gérer des puits mobiles et proposé une stratégie de mobilité des puits adaptée permettant de prolonger la durée de vie du réseau.Puis, nous avons proposé une nouvelle approche qui applique le codage de Slepian-Wolf sur les adresses émises dans les RCsFs. L'idée consiste à exploiter la corrélation des adresses garantie par un schéma approprié d'allocation afin de réduire le nombre de bits d'entête transmis au puits et d'améliorer ainsi la durée de vie du réseau.Finalement, nous avons proposé une infrastructure IPv6 hybride pour bâtiments intelligents qui combine les avantages des technologies sans fil et courants porteurs en ligne afin d'améliorer la durée de vie du réseau, sa connectivité et sa robustesse à faible surcoût. / Improving the network lifetime is a very challenging problem that needs to be taken into account during the deployment of wireless sensor networks (WSNs). Indeed, these networks are composed of many autonomous sensors with a limited energy supply provided by batteries which are usually difficult to recharge or replace. The scientific challenge is to ensure the operation of these networks for several years without major external intervention. To maximize the lifetime of WSNs, we first explored the possibility of introducing multiple mobile sinks. We proposed two mobility strategies. The first one provides the optimal placement in a network of small scale. The second one is based on an heuristic algorithm that ensures scalability.We were then interested in IPv6 based WSNs which use the new proposed routing protocol by IETF namely RPL. We studied this protocol, extended its capacity to manage mobile sinks andproposed an appropriate sinks mobility strategy that extends the network lifetime.Next, we proposed a novel approach which consists in applying Slepian-Wolf coding to emitted addresses in WSNs. The basic idea is to exploit the addresses correlation, guaranteed by an appropriate addresses allocation scheme, in order to reduce the header size of packets transmitted to the sink and thus improve the network lifetime.Finally, we proposed an hybrid IPv6 infrastructure for smart buildings which combines the wireless and power line technologies to guarantee energy efficiency and a longer network lifetime.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / A evoluÃÃo no desenvolvimento de novos dispositivos, cada vez mais baratos e eficientes, expandiu o uso das Redes Sensores Sem Fio (RSSF) e incentivou a criaÃÃo de novas aplicaÃÃes, no cenÃrio contemporÃneo da ComputaÃÃo UbÃqua e Pervasiva. No entanto, a limitaÃÃo de energia continua sendo um desafio na Ãrea de RSSF. Essa situaÃÃo à agravada ainda mais pela a inviabilidade de recarga de energia jà que, em muitos casos, as RSSF sÃo utilizadas em ambientes inacessÃveis. Com o barateamento dos dispositivos utilizados nas RSSFs, ficou mais fÃcil empregar redes muito densas e de larga escala nos ambientes a serem monitorados. O emprego de redes densas, que apresentam alto grau de redundÃncia dos nÃs, permite que a rede continue funcional mesmo com a exaustÃo de alguns nÃs. AlÃm de oferecer tolerÃncia a falhas, o uso de redes muito densas oferece a oportunidade da implementaÃÃo de mecanismos de escalonamento dos nÃs redundantes, de forma que o tempo de vida da rede seja ainda melhor otimizado. Assumindo um cenÃrio com rede muito densas, este trabalho descreve a implementaÃÃo de um mecanismo de escalonamento autonÃmico, simples, robusto e escalÃvel, com o objetivo de melhorar ainda mais os resultados jà apresentados pelo BiO4SeL, um protocolo de roteamento baseado em ColÃnia de Formigas e desenvolvido para maximizar o tempo de vida da rede. Os resultados mostram que o novo esquema de escalonamento efetivamente melhora o tempo de vida de uma RSSF baseada no BiO4SeL em cenÃrios densos. / he evolution and development of new devices, increasingly cheaper and more efficient, expanded the use of Wireless Sensor Networks (WSN) and encouraged the creation of new applications in the contemporary scenery of Ubiquitous and Pervasive Computing. However, energy limitation remains a challenge in the field of WSN. This situation is aggravated even more by the infeasibility of energy recharge since, in many cases, WSN are used in inaccessible enviroments. With cheapness devices used in WSN, became easier to employ dense and large-scale networks in environments that will be monitored. The use of dense networks, which have a high degree redundancy of nodes, allows the network remains functional even with the exhaustion of some nodes. In addition to provide fault tolerance, the use of very dense networks offer the opportunity of implementing scheduling mechanisms for redundant nodes, in a way that the network lifetime is even better optimized. Assuming a scenery with very dense networks, this dissertation describes the implementation of an autonomic scheduling mechanism, simple, robust and scalable, in order to further improve the results already presented by BiO4SeL, which is a routing protocol based on Ant Colony and designed to maximize the network lifetime. The results show that the new scheduling scheme effectively improves the WSN lifetime based on BiO4SeL in dense scenarios.

Saving energy and increasing network lifetime are significant challenges in the field of Wireless Sensor Networks (WSNs). Energy-aware routing protocols have been introduced for WSNs to overcome limitations of WSN including limited power resources and difficulties renewing or recharging sensor nodes batteries. Furthermore, the potentially inhospitable environments of sensor locations, in some applications, such as the bottom of the ocean, or inside tornados also have to be considered. ZigBee is one of the latest communication standards designed for WSNs based on the IEEE 802.15.4 standard. The ZigBee standard supports two routing protocols, the Ad hoc On-demand Distance Vector (AODV), and the cluster-tree routing protocols. These protocols are implemented to establish the network, form clusters, and transfer data between the nodes. The AODV and the cluster-tree routing protocols are two of the most efficient routing protocols in terms of reducing the control message overhead, reducing the bandwidth usage in the network, and reducing the power consumption of wireless sensor nodes compared to other routing protocols. However, neither of these protocols considers the energy level or the energy consumption rate of the wireless sensor nodes during the establishment or routing processes.

Battery powered wireless sensors are widely used in industrial and regulatory monitoring applications. This is primarily due to the ease of installation and the ability to monitor areas that are difficult to access. Additionally, they can be left unattended for long periods of time. However, there are many challenges to successful deployments of wireless sensor networks (WSNs). In this thesis we draw attention to two major challenges. Firstly, with a view to extending network range, modern WSNs use mesh network topologies, where data is sent either directly or by relaying data from node-to-node en route to the central base station. The additional load of relaying other nodes’ data is expensive in terms of energy consumption, and depending on the routes taken some nodes may be heavily loaded. Hence, it is crucial to locate routes that achieve energy efficiency in the network and extend the time before the first node exhausts its battery, thus improving the network lifetime. Secondly, WSNs operate in a dynamic radio environment. With changing conditions, such as modified buildings or the passage of people, links may fail and data will be lost as a consequence. Therefore in addition to finding energy efficient routes, it is important to locate combinations of routes that are robust to the failure of radio links. Dealing with these challenges presents a routing optimisation problem with multiple objectives: find good routes to ensure energy efficiency, extend network lifetime and improve robustness. This is however an NP-hard problem, and thus polynomial time algorithms to solve this problem are unavailable. Therefore we propose hybrid evolutionary approaches to approximate the optimal trade-offs between these objectives. In our approach, we use novel search space pruning methods for network graphs, based on k-shortest paths, partially and edge disjoint paths, and graph reduction to combat the combinatorial explosion in search space size and consequently conduct rapid optimisation. The proposed methods can successfully approximate optimal Pareto fronts. The estimated fronts contain a wide range of robust and energy efficient routes. The fronts typically also include solutions with a network lifetime close to the optimal lifetime if the number of routes per nodes were unconstrained. These methods are demonstrated in a real network deployed at the Victoria & Albert Museum, London, UK.

在無線感測器網路中，由於感測器電池的不可替換性，有效的能源管理是一項重要的研究議題。既然通訊及偵測都會消耗感測器的能量，減少多餘偵測範圍的重疊，及降低重覆資料(duplicate data)的影響，可有效節省能量，延長網路生命週期。於本研究中，我們提出VERA (Voronoi dEtection Range Adjustment)，利用分散式Voronoi diagram演算法劃分各感測器負責監控的區域，並利用基因演算法計算每個感測器最合適的偵測範圍以節省能量，延長網路生命週期。此外，我們亦考慮偵測能力的限制，在減少感測器偵測範圍重疊的同時，也避免某些區域的偵測能力低於門檻值。在實驗模擬的部份，我們利用模擬系統驗證所提出的方法是否能有效降低各感測器偵測範圍的重疊性，並因偵測範圍降低而導致duplicate data的減少和整個感測器網路總能量耗損的減少。末了，也將驗證本方法是否能延長無線感測器網路的生命週期和達到滿足偵測機率的最低保證。 / In the wireless sensor networks, the batteries are not replaceable, efficient power management thus becomes an important research issue. Since both communication and detection consume energy, if we can largely decrease the overlaps among detection ranges and reduce the duplicate data then we can save the energy effectively. This will thus prolong the network lifetime. In this research, we propose a Voronoi dEtection Range Adjustment (VERA) method that utilizes distributed Voronoi diagram to delimit the responsible area for each sensor, and utilize Genetic Algorithm to compute the most suitable detection range for each sensor. As we try to decrease the detection ranges, we still guarantee to meet the lower bound of the sensor detection probability. Simulations showed that our method can decrease the redundant overlaps among detection ranges, minimize energy consumption, and prolong the lifetime of the whole network effectively.