Wireless Sensor Networks (WSNs) are deployed widely for various applications. A variety of useful data are generated by these deployments. Since WSNs have limited resources and unreliable communication links, traditional data management techniques are not suitable. Therefore, designing effective data management techniques for WSNs becomes important. In this dissertation, we address three key issues of data management in WSNs. For data collection, a scheme of making some nodes sleep and estimating their values according to the other active nodes’ readings has been proved energy-efficient. For the purpose of improving the precision of estimation, we propose two powerful estimation models, Data Estimation using a Physical Model (DEPM) and Data Estimation using a Statistical Model (DESM). Most of existing data processing approaches of WSNs are real-time. However, historical data of WSNs are also significant for various applications. No previous study has specifically addressed distributed historical data query processing. We propose an Index based Historical Data Query Processing scheme which stores historical data locally and processes queries energy-efficiently by using a distributed index tree. Area query processing is significant for various applications of WSNs. No previous study has specifically addressed this issue. We propose an energy-efficient in-network area query processing scheme. In our scheme, we use an intelligent method (Grid lists) to describe an area, thus reducing the communication cost and dropping useless data as early as possible. With a thorough simulation study, it is shown that our schemes are effective and energy- efficient. Based on the area query processing algorithm, an Intelligent Monitoring System is designed to detect various events and provide real-time and accurate information for escaping, rescuing, and evacuation when a dangerous event happened.

Wireless sensor networks are made up of a large number of sensors deployed randomly in an ad-hoc manner in the area/target to be monitored. Due to their weight and size limitations, the energy conservation is the most critical issue. Energy saving in a wireless sensor network can be achieved by scheduling a subset of sensor nodes to activate and allowing others to go into low power sleep mode, or adjusting the transmission or sensing range of wireless sensor nodes. In this thesis, we focus on improving the lifetime of wireless sensor networks using both smart scheduling and adjusting sensing ranges. Firstly, we conduct a survey on existing works in literature and then we define the sensor network lifetime problem with range assignment. We then propose two completely localized and distributed scheduling algorithms with adjustable sensing range. These algorithms are the enhancement of distributed algorithms for fixed sensing range proposed in the literature. The simulation results show that there is almost 20 percent improvement of network lifetime when compare with the previous approaches.

Wireless sensor networks (WSNs) consist of a large number of sensor nodes, capable of on-board sensing and data processing, that are employed to observe some phenomenon of interest. With their desirable properties of flexible deployment, resistance to harsh environment and lower implementation cost, WSNs envisage a plethora of applications in diverse areas such as industrial process control, battle- field surveillance, health monitoring, and target localization and tracking. Much of the sensing and communication paradigm in WSNs involves ensuring power efficient transmission and finding scalable algorithms that can deliver the desired performance objectives while minimizing overall energy utilization. Since power is primarily consumed in radio transmissions delivering timing information, clock synchronization represents an indispensable requirement to boost network lifetime. This dissertation focuses on deriving efficient estimators and performance bounds for the clock parameters in a classical frequentist inference approach as well as in a Bayesian estimation framework. A unified approach to the maximum likelihood (ML) estimation of clock offset is presented for different network delay distributions. This constitutes an analytical alternative to prior works which rely on a graphical maximization of the likelihood function. In order to capture the imperfections in node oscillators, which may render a time-varying nature to the clock offset, a novel Bayesian approach to the clock offset estimation is proposed by using factor graphs. Message passing using the max-product algorithm yields an exact expression for the Bayesian inference problem. This extends the current literature to cases where the clock offset is not deterministic, but is in fact a random process. A natural extension of pairwise synchronization is to develop algorithms for the more challenging case of network-wide synchronization. Assuming exponentially distributed random delays, a network-wide clock synchronization algorithm is proposed using a factor graph representation of the network. Message passing using the max- product algorithm is adopted to derive the update rules for the proposed iterative procedure. A closed form solution is obtained for each node's belief about its clock offset at each iteration. Identifying the close connections between the problems of node localization and clock synchronization, we also address in this dissertation the problem of joint estimation of an unknown node's location and clock parameters by incorporating the effect of imperfections in node oscillators. In order to alleviate the computational complexity associated with the optimal maximum a-posteriori estimator, two iterative approaches are proposed as simpler alternatives. The first approach utilizes an Expectation-Maximization (EM) based algorithm which iteratively estimates the clock parameters and the location of the unknown node. The EM algorithm is further simplified by a non-linear processing of the data to obtain a closed form solution of the location estimation problem using the least squares (LS) approach. The performance of the estimation algorithms is benchmarked by deriving the Hybrid Cramer-Rao lower bound (HCRB) on the mean square error (MSE) of the estimators. We also derive theoretical lower bounds on the MSE of an estimator in a classical frequentist inference approach as well as in a Bayesian estimation framework when the likelihood function is an arbitrary member of the exponential family. The lower bounds not only serve to compare various estimators in our work, but can also be useful in their own right in parameter estimation theory.

University of Macau / Faculty of Science and Technology / Department of Electrical and Electronics Engineering

This dissertation presents the concept of a small, low-cost, self-powered smart wireless sensor that can be used for monitoring current, temperature and voltage on a variety of utility assets. Novel energy harvesting approaches are proposed that enable the sensor to operate without batteries and to have an expected life of 20-30 years. The sensor measures current flowing in an asset using an open ferromagnetic core, unlike a CT which uses a closed core, which makes the proposed sensor small in size, and low-cost. Further, it allows the sensor to operate in conjunction with different assets having different geometries, such as bus-bars, cables, disconnect switches, overhead conductors, transformers, and shunt capacitors, and function even when kept in the vicinity of an asset. Two novel current sensing algorithms have been developed that help the sensor to autonomously calibrate and make the sensor immune from far-fields and cross-talk. The current sensing algorithms have been implemented and tested in the lab at up to 1000 A. This research also presents a novel self-calibrating low-cost voltage sensing technique. The major purpose of voltage sensing is detection of sags, swells and loss-ofpower on the asset; therefore, the constraint on error in measurement is relaxed. The technique has been tested through several simulation studies. A voltage sensor prototype has been developed and tested on a high voltage bus at up to 35 kV. Finally, a study of sensor operation under faults, such as lightning strikes, and large short circuit currents has been presented. These studies are conducted using simulations and actual experiments. Based on the results of the experiments, a robust protection circuit for the sensor is proposed. Issues related to corona and external electrical noise on the communication network are also discussed and experimentally tested. Further, optimal design of the energy harvester and a novel design of package for the sensor that prevents the circuitry from external electrical noise without attenuation of power signals for the energy harvester are also proposed.

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.

The main contributions of this thesis are located in the domain of wireless sensor netorks. More in detail, we introduce energyaware algorithms and protocols in the context of the following topics: self-synchronized duty-cycling in networks with energy harvesting capabilities, distributed graph coloring and minimum energy broadcasting with realistic antennas. In the following, we review the research conducted in each case. We propose a self-synchronized duty-cycling mechanism for sensor networks. This mechanism is based on the working and resting phases of natural ant colonies, which show self-synchronized activity phases. The main goal of duty-cycling methods is to save energy by efficiently alternating between different states. In the case at hand, we considered two different states: the sleep state, where communications are not possible and energy consumption is low; and the active state, where communication result in a higher energy consumption. In order to test the model, we conducted an extensive experimentation with synchronous simulations on mobile networks and static networks, and also considering asynchronous networks. Later, we extended this work by assuming a broader point of view and including a comprehensive study of the parameters. In addition, thanks to a collaboration with the Technical University of Braunschweig, we were able to test our algorithm in the real sensor network simulator Shawn (http://shawn.sf.net). The second part of this thesis is devoted to the desynchronization of wireless sensor nodes and its application to the distributed graph coloring problem. In particular, our research is inspired by the calling behavior of Japanese tree frogs, whose males use their calls to attract females. Interestingly, as female frogs are only able to correctly localize the male frogs when their calls are not too close in time, groups of males that are located nearby each other desynchronize their calls. Based on a model of this behavior from the literature, we propose a novel algorithm with applications to the field of sensor networks. More in detail, we analyzed the ability of the algorithm to desynchronize neighboring nodes. Furthermore, we considered extensions of the original model, hereby improving its desynchronization capabilities.To illustrate the potential benefits of desynchronized networks, we then focused on distributed graph coloring. Later, we analyzed the algorithm more extensively and show its performance on a larger set of benchmark instances. The classical minimum energy broadcast (MEB) problem in wireless ad hoc networks, which is well-studied in the scientific literature, considers an antenna model that allows the adjustment of the transmission power to any desired real value from zero up to the maximum transmission power level. However, when specifically considering sensor networks, a look at the currently available hardware shows that this antenna model is not very realistic. In this work we re-formulate the MEB problem for an antenna model that is realistic for sensor networks. In this antenna model transmission power levels are chosen from a finite set of possible ones. A further contribution concerns the adaptation of an ant colony optimization algorithm --currently being the state of the art for the classical MEB problem-- to the more realistic problem version, the so-called minimum energy broadcast problem with realistic antennas (MEBRA). The obtained results show that the advantage of ant colony optimization over classical heuristics even grows when the number of possible transmission power levels decreases. Finally we build a distributed version of the algorithm, which also compares quite favorably against centralized heuristics from the literature. / Las principles contribuciones de esta tesis se encuentran en el domino de las redes de sensores inalámbricas. Más en detalle, introducimos algoritmos y protocolos que intentan minimizar el consumo energético para los siguientes problemas: gestión autosincronizada de encendido y apagado de sensores con capacidad para obtener energía del ambiente, coloreado de grafos distribuido y broadcasting de consumo mínimo en entornos con antenas reales. En primer lugar, proponemos un sistema capaz de autosincronizar los ciclos de encendido y apagado de los nodos de una red de sensores. El mecanismo está basado en las fases de trabajo y reposo de las colonias de hormigas tal y como estas pueden observarse en la naturaleza, es decir, con fases de actividad autosincronizadas. El principal objectivo de este tipo de técnicas es ahorrar energía gracias a alternar estados de forma eficiente. En este caso en concreto, consideramos dos estados diferentes: el estado dormido, en el que los nodos no pueden comunicarse y el consumo energético es bajo; y el estado activo, en el que las comunicaciones propician un consumo energético elevado. Con el objetivo de probar el modelo, se ha llevado a cabo una extensa experimentación que incluye tanto simulaciones síncronas en redes móviles y estáticas, como simulaciones en redes asíncronas. Además, este trabajo se extendió asumiendo un punto de vista más amplio e incluyendo un detallado estudio de los parámetros del algoritmo. Finalmente, gracias a la colaboración con la Technical University of Braunschweig, tuvimos la oportunidad de probar el mecanismo en el simulador realista de redes de sensores, Shawn (http://shawn.sf.net). La segunda parte de esta tesis está dedicada a la desincronización de nodos en redes de sensores y a su aplicación al problema del coloreado de grafos de forma distribuida. En particular, nuestra investigación está inspirada por el canto de las ranas de árbol japonesas, cuyos machos utilizan su canto para atraer a las hembras. Resulta interesante que debido a que las hembras solo son capaces de localizar las ranas macho cuando sus cantos no están demasiado cerca en el tiempo, los grupos de machos que se hallan en una misma región desincronizan sus cantos. Basado en un modelo de este comportamiento que se encuentra en la literatura, proponemos un nuevo algoritmo con aplicaciones al campo de las redes de sensores. Más en detalle, analizamos la habilidad del algoritmo para desincronizar nodos vecinos. Además, consideramos extensiones del modelo original, mejorando su capacidad de desincronización. Para ilustrar los potenciales beneficios de las redes desincronizadas, nos centramos en el problema del coloreado de grafos distribuido que tiene relación con diferentes tareas habituales en redes de sensores. El clásico problema del broadcasting de consumo mínimo en redes ad hoc ha sido bien estudiado en la literatura. El problema considera un modelo de antena que permite transmitir a cualquier potencia elegida (hasta un máximo establecido por el dispositivo). Sin embargo, cuando se trabaja de forma específica con redes de sensores, un vistazo al hardware actualmente disponible muestra que este modelo de antena no es demasiado realista. En este trabajo reformulamos el problema para el modelo de antena más habitual en redes de sensores. En este modelo, los niveles de potencia de transmisión se eligen de un conjunto finito de posibilidades. La siguiente contribución consiste en en la adaptación de un algoritmo de optimización por colonias de hormigas a la versión más realista del problema, también conocida como broadcasting de consumo mínimo con antenas realistas. Los resultados obtenidos muestran que la ventaja de este método sobre heurísticas clásicas incluso crece cuando el número de posibles potencias de transmisión decrece. Además, se ha presentado una versión distribuida del algoritmo, que también se compara de forma bastante favorable contra las heurísticas centralizadas conocidas.