Les réseaux de capteurs sans fil suscitent une attention croissante depuis quelques années, tant les applications sont nombreuses, incluant notamment le suivi de véhicules ou la surveillance de champs de bataille. Un ensemble de capteurs disséminé aléatoirement a pour but de surveiller des cibles se déplaçant dans une région donnée. Chaque capteur a une durée de vie limitée et deux états : actif ou inactif. Un capteur actif peut surveiller des cibles dans son rayon de portée, au prix d'une consommation d'énergie. Dans cette thèse, les problèmes étudiés consistent à déterminer un ordonnancement optimal d'activités de surveillance, afin de couvrir toutes les cibles à tout instant de la mission. Nous abordons en premier lieu un problème d'ordonnancement robuste. Une cible dont on connaît la trajectoire spatiale avec précision est sujette à incertitude temporelle. Cette situation est rencontrée lorsqu'un avion vole dans un couloir aérien, qu'un train circule sur une voie ferrée, ou que de tout autre véhicule suit un itinéraire pré-déterminé. L'objectif est de calculer un ordonnancement d'activités capable de résister au plus grand écart par rapport aux dates prévisionnelles de passage de la cible. Ce premier problème est résolu à l'aide d'un algorithme exact pseudo-polynomial, reposant sur une dichotomie. En second lieu, nous étudions le problème visant à préserver la capacité de surveillance du réseau de capteurs dans un contexte multi-missions. Les cibles sont maintenant sujettes à une incertitude spatiale, c'est-à-dire susceptibles de se trouver à une distance inférieure à un seuil delta de leur position prévisionnelle. Ce second problème est résolu à l’aide d’un algorithme exact basé sur la génération de colonnes, et accéléré par une métaheuristique. Les méthodes de résolution proposées ont en commun une étape préliminaire, appelée discrétisation, qui conduit à reformuler les problèmes originaux comme des problèmes d'ordonnancement d'activités de surveillance. L'espace de surveillance est découpé en faces, ensembles de points couverts par un même sous-ensemble de capteurs. Le calcul des durées de séjour des cibles dans chaque face permet de découper la durée de la mission en fenêtres de temps, et d'envisager le problème de couverture de cibles mobiles comme une séquence de problèmes de couverture de cibles immobiles. Les algorithmes proposés pour aborder ces problèmes sont testés sur de nombreuses instances, et leurs résultats sont analysés. De nombreuses perspectives ouvertes par ces travaux sont également présentées. / Wireless sensor networks have received a particular attention during the last years, involving many applications, such as vehicle tracking or battlefield monitoring. A set of sensors is randomly dispatched in a region in order to monitor moving targets. Each sensor has a limited battery lifetime and two states: active or inactive. An active sensor is able to monitor targets inside its sensing radius, which consumes energy. In this thesis, the studied problems consist in deciding an optimal schedule of sensing activities, in order to cover all the targets at any instant of the mission. First, we study a robust scheduling problem. A target such that the spatial trajectory is exactly known is subject to temporal uncertainties. This context is met for a plane flying in an airline route, a train running on a railway, or any vehicle following a predetermined path. The objective is to compute a schedule of activities able to resist to the largest uncertainties This first problem is solved using an exact pseudo-polynomial algorithm, relying on a dichotomy. Second, we study a problem aiming at preserving enough sensor network capacity in order to perform further missions. For this problem, the targets are subject to spatial uncertainties, i.e. their actual position may be at a distance delta of their expected position. This second problem is solved using an exact algorithm based on column generation, accelerated by a metaheuristic. All the proposed methods have a common phase, called discretization, that leads to reformulate the original problems as activity scheduling problems. The monitored area is split into faces, that are defined as sets of points covered by the same set of sensors. Computing the stay duration of targets inside each face leads to split the mission duration into time windows, so the moving target tracking problem can be seen as a sequence of static target tracking problems. The proposed algorithms are tested on many instances, and the analysis of the results is provided. Numerous open perspectives of this work are also given.

There is a growing interest in employing sub-soil sensing systems to support precision agriculture. This thesis presents the design of an RFID sub-soil sensing system which is based on integrating passive RFID technology and sub-soil sensing technology. The proposed RFID sub-soil system comprises of an above-ground RFID reader and a number of RFID sub-soil sensor nodes. The key feature of the system is that the sensor nodes do not require an on-board battery, as they are capable of harvesting energy from the ElectroMagnetic (EM) field generated by the RFID reader. The sensor nodes then transmit sensor measurements to the reader wirelessly through soil. With the proposed RFID sub-soil system, the high path loss of the sub-soil wireless channel is a significant problem which leads to the challenge for the system to achieve an acceptable Quality of Service (QoS). In this project, the path loss in soil has been characterised through CST simulations. In the simulations, the effect of the soil on the sensor node antenna has also been investigated. This thesis also presents the design and implementation of a programmable RFID reader platform and an embedded RFID sensor node prototype. The RFID reader platform is implemented using a National Instruments (NI) PXI system, and it is configured and controlled by NI LabVIEW software. The sensor node prototype is capable of harvesting RF energy and transmitting sensor measurements from a temperature sensor through backscatter communication. A series of sub-soil experiments have been carried out to evaluate the performance of the RFID sensor node prototype using the PXI-based RFID reader platform. The experimental results are presented and analysed in this thesis. Additionally, this work has explored trade-offs in the system design, and these design trade-offs are summarised and described.

A wireless sensor network is designed to monitor events and report this information to a central location, or sink node. The information is required to efficiently travel through the network. It is the job of the routing protocol to officiate this process. With transmissions consuming the majority of the energy available to a sensor node, it becomes important to limit their usage while still maintaining reliable communication with the sink node. The aim of the research covered in this dissertation was to adapt the flat and hierarchical architectures to create a new hybrid that draws on current protocol theories. The designed and developed protocol, Hybrid Energy Efficient Routing (HEER) protocol, builds upon the initial groundwork laid out by the previously developed Simple Energy Efficient Routing (SEER) protocol designed by C.J. Leuschner. Another aspect of the work was to focus on the current lack of credibility that is present in the WSN research community. The validity of SEER was examined and tested and this led to the main focus of this research, ensuring that HEER proves to be valid. The HEER protocol for wireless sensor networks is designed such that it is computationally simple, limits the number of transmissions, employs a cross-layer approach, is reliable, is energy-aware, has limited support for mobile nodes, is energy efficient, and most importantly is credible. Sensor nodes are extremely limited when it comes to their available energy resources. To maximise the node and network lifetimes requires the designed algorithm to be energy aware and as efficient as possible. A cross-layer design approach is followed which allows for the different layers of the OSI model to interact. The HEER protocol limits the number of transmissions that are used for network operation. This is achieved by using a minimal amount of messages for network setup and by selecting the optimal route. Route selection is calculated using hop count, current energy available, energy available on the receiving node, and lastly the energy required to reach the destination node. HEER combines and expands upon the method used by SEER for route selection. Network lifetime for networks of large sizes is increased, mainly due to more efficient routing of messages. The protocol was kept computationally simple and energy efficient, thus maintaining network survivability for as long as possible. / Dissertation (MEng)--University of Pretoria, 2008. / Electrical, Electronic and Computer Engineering / unrestricted

Wireless Sensor Networks (WSNs) are widely used for various civilian and military applications, and thus have attracted significant interest in recent years. This work investigates the important problem of optimal deployment of WSNs in terms of coverage and energy consumption. Five deployment algorithms are developed for maximal sensing range and minimal energy consumption in order to provide optimal sensing coverage and maximum lifetime. Also, all developed algorithms include self-healing capabilities in order to restore the operation of WSNs after a number of nodes have become inoperative. Two centralized optimization algorithms are developed, one based on Genetic Algorithms (GAs) and one based on Particle Swarm Optimization (PSO). Both optimization algorithms use powerful central nodes to calculate and obtain the global optimum outcomes. The GA is used to determine the optimal tradeoff between network coverage and overall distance travelled by fixed range sensors. The PSO algorithm is used to ensure 100% network coverage and minimize the energy consumed by mobile and range-adjustable sensors. Up to 30% - 90% energy savings can be provided in different scenarios by using the developed optimization algorithms thereby extending the lifetime of the sensor by 1.4 to 10 times. Three distributed optimization algorithms are also developed to relocate the sensors and optimize the coverage of networks with more stringent design and cost constraints. Each algorithm is cooperatively executed by all sensors to achieve better coverage. Two of our algorithms use the relative positions between sensors to optimize the coverage and energy savings. They provide 20% to 25% more energy savings than existing solutions. Our third algorithm is developed for networks without self-localization capabilities and supports the optimal deployment of such networks without requiring the use of expensive geolocation hardware or energy consuming localization algorithms. This is important for indoor monitoring applications since current localization algorithms cannot provide good accuracy for sensor relocation algorithms in such indoor environments. Also, no sensor redeployment algorithms, which can operate without self-localization systems, developed before our work.

Context represents any knowledge obtained from Wireless Sensor Networks (WSNs) about the object being monitored (such as time and location of the sensed events). Time and location are important constituents of context as the information about the events sensed in WSNs is comprehensive when it includes spatio-temporal knowledge. In this thesis, we first concentrate on the development of a suite of lightweight algorithms on temporal event ordering and time synchronization as well as localization for WSNs. Then, we propose an energy-efficient clustering routing protocol for WSNs that is used for message delivery in the former algorithm. The two problems - temporal event ordering and synchronization - are dealt with together as both are concerned with preserving temporal relationships of events in WSNs. The messages needed for synchronization are piggybacked onto the messages exchanged in underlying algorithms. The synchronization algorithm is tailored to the clustered topology in order to reduce the overhead of keeping WSNs synchronized. The proposed localization algorithm has an objective of lowering the overhead of DV-hop based algorithms by reducing the number of floods in the initial position estimation phase. It also randomizes iterative refinement phase to overcome the synchronicity of DV-hop based algorithms. The position estimates with higher confidences are emphasized to reduce the impact of erroneous estimates on the neighbouring nodes. The proposed clustering routing protocol is used for message delivery in the proposed temporal algorithm. Nearest neighbour nodes are employed for inter-cluster communication. The algorithm provides Quality of Service by forwarding high priority messages via the paths with the least cost. The algorithm is also extended for multiple Sink scenario. The suite of algorithms proposed in this thesis provides the necessary tool for providing spatio-temporal context for context-aware WSNs. The algorithms are lightweight as they aim at satisfying WSN's requirements primarily in terms of energy-efficiency, low latency and fault tolerance. This makes them suitable for emergency response applications and ubiquitous computing.

In this thesis, an investigation of the performance of multipath routing in Wireless Sensor Networks (WSN) is performed. The communication in the network under study is to take place from individual nodes to the sink node. The investigation involved multipath finding methods in WSN. Also, it involves investigating the weight assignment, traffic splitting and route selection methods for the different paths discovered by each node in the WSN. Also, a comparison between Hybrid Routing Protocol, Source Routing Protocol and Diffusion Routing Protocol is performed. A simple traffic routing algorithm for each routing protocol has been developed to conceptualize how the network traffic is routed on a set of active paths. The investigation of the Hybrid, Source and Diffusion Routing Protocol involved using multiple paths simultaneously to transmit messages that belong to the same flow by using a weight assigned to each path and transmit each message as a whole. Finally, the power consumption and the QoS in terms of message delays for a WSN were investigated and compared between different protocols.

Data aggregation is an important technique in wireless sensor networks. The data are gathered together by data fusion routines along the routing path, which is called data-centralized routing. We propose a localized, Delay-bounded and Energy-efficient Data Aggregation framework(DEDA) based on the novel concept of DEsired Progress (DEP). This framework works under request-driven networks with realistic MAC layer protocols. It is based on localized minimal spanning tree (LMST) which is an energy-efficient structure. Besides the energy consideration, delay reliability is also considered by means of the DEP. A node’s DEP reflects its desired progress in LMST which should be largely satisfied. Hence, the LMST edges might be replaced by unit disk graph (UDG) edges which can progress further in LMST. The DEP metric is rooted on realistic degree-based delay model so that DEDA increases the delay reliability to a large extent compared to other hop-based algorithms. We also combine our DEDA framework with area coverage and localized connected dominating set algorithms to achieve two more resilient DEDA implementations: A-DEDA and AC-DEDA. The simulation results confirm that our original DEDA and its two enhanced variants save more energy and attain a higher delay reliability ratio than existing protocols.

Wireless sensor networks (WSN) increasingly permeate modern societies nowadays. But in spite of their plethora of successful applications, WSN are often unable to surmount many operational challenges that unexpectedly arise during their lifetime. Fortunately, robotic agents can now assist a WSN in various ways. This thesis illustrates how mobile robots which are able to carry a limited number of sensors can help the network react to sensor faults, either during or after its deployment in the monitoring region. Two scenarios are envisioned. In the first one, carrier robots surround a point of interest with multiple sensor layers (focused coverage formation). We put forward the first known algorithm of its kind in literature. It is energy-efficient, fault-reactive and aware of the bounded robot cargo capacity. The second one is that of replacing damaged sensing units with spare, functional ones (coverage repair), which gives rise to the formulation of two novel combinatorial optimization problems. Three nature-inspired metaheuristic approaches that run at a centralized location are proposed. They are able to find good-quality solutions in a short time. Two frameworks for the identification of the damaged nodes are considered. The first one leans upon diagnosable systems, i.e. existing distributed detection models in which individual units perform tests upon each other. Two swarm intelligence algorithms are designed to quickly and reliably spot faulty sensors in this context. The second one is an evolving risk management framework for WSNs that is entirely formulated in this thesis.

Wireless Sensor Networks (WSNs) have enticed a strong attention in the research community due to the broad range of applications and services they support. WSNs are composed of intelligent sensor nodes that have the capabilities to monitor different types of environmental phenomena or critical activities. Sensor nodes operate under stringent requirements of scarce power resources, limited storage capacities, limited processing capabilities, and hostile environmental surroundings. However, conserving sensor nodes’ power resources is the top priority requirement in the design of a WSN as it has a direct impact on its lifetime. The IEEE 802.15.4 standard defines a set of specifications for both the PHY layer and the MAC sub-layer that abide by the distinguished requirements of WSNs. The standard’s MAC protocol employs an intelligent backoff algorithm, called the Binary Exponent Backoff (BEB), that minimizes the drainage of power in these networks. In this thesis we present an in-depth study of the IEEE 802.15.4 MAC protocol to highlight both its strong and weak aspects. We show that we have enticing opportunities to improve the performance of this protocol in the context of WSNs. We propose three new backoff algorithms, namely, the Standby-BEB (SB-BEB), the Adaptive Backoff Algorithm (ABA), and the Priority-Based BEB (PB-BEB), to replace the standard BEB. The main contribution of the thesis is that it develops a new design concept that drives the design of efficient backoff algorithms for the IEEE 802.15.4-based WSNs. The concept dictates that controlling the algorithms parameters probabilistically has a direct impact on enhancing the backoff algorithm’s performance. We provide detailed discrete-time Markov-based models (for AB-BEB and ABA) and extensive simulation studies (for the three algorithms) to prove the superiority of our new algorithms over the standard BEB.

This thesis focuses on using Wireless Sensor Networks (WSNs) for monitoring applications on epilepsy patients (EPs). With the increase of these types of patients and the necessity of continuous daily monitoring and the need for an immediate response to their seizures, the main objective of this thesis is to decrease the response time in order to save them from severe consequences, as well as to make them comfortable with the monitoring procedure. Our proposed Epilepsy Patients Monitoring System (EPMS) consists of five ordinary nodes distributed over the patient’s body, as well as a coordinator node and a receive node. These nodes detect the seizures and forward the data to the coordinator, which, in turn, collects the data and transmits it to the receiver, triggering an alarm concerning the seizure occurrence. We focus on the Medium Access Control (MAC) protocol, using the Sensor Medium Access Control (SMAC) protocol to decrease the generated delay, and the Carrier Sense Multiple Access/ Collision Avoidance (CSMA/CA) scheme to prevent collisions that can prolong the response time.