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.

Wireless Sensor Networks (WSNs) are now widely used for monitoring and controlling of systems where human intervention is not desirable or possible. Connected Dominating Sets (CDSs) based topology control in WSNs is one kind of hierarchical method to ensure sufficient coverage while reducing redundant connections in a relatively crowded network. Moreover, Minimum-sized Connected Dominating Set (MCDS) has become a well-known approach for constructing a Virtual Backbone (VB) to alleviate the broadcasting storm for efficient routing in WSNs extensively. However, no work considers the load-balance factor of CDSsin WSNs. In this dissertation, we first propose a new concept — the Load-Balanced CDS (LBCDS) and a new problem — the Load-Balanced Allocate Dominatee (LBAD) problem. Consequently, we propose a two-phase method to solve LBCDS and LBAD one by one and a one-phase Genetic Algorithm (GA) to solve the problems simultaneously. Secondly, since there is no performance ratio analysis in previously mentioned work, three problems are investigated and analyzed later. To be specific, the MinMax Degree Maximal Independent Set (MDMIS) problem, the Load-Balanced Virtual Backbone (LBVB) problem, and the MinMax Valid-Degree non Backbone node Allocation (MVBA) problem. Approximation algorithms and comprehensive theoretical analysis of the approximation factors are presented in the dissertation. On the other hand, in the current related literature, networks are deterministic where two nodes are assumed either connected or disconnected. In most real applications, however, there are many intermittently connected wireless links called lossy links, which only provide probabilistic connectivity. For WSNs with lossy links, we propose a Stochastic Network Model (SNM). Under this model, we measure the quality of CDSs using CDS reliability. In this dissertation, we construct an MCDS while its reliability is above a preset applicationspecified threshold, called Reliable MCDS (RMCDS). We propose a novel Genetic Algorithm (GA) with immigrant schemes called RMCDS-GA to solve the RMCDS problem. Finally, we apply the constructed LBCDS to a practical application under the realistic SNM model, namely data aggregation. To be specific, a new problem, Load-Balanced Data Aggregation Tree (LBDAT), is introduced finally. Our simulation results show that the proposed algorithms outperform the existing state-of-the-art approaches significantly.

Modifications of footers in title page, page-2 and page-3.

Wireless sensor network is an intelligent network system which has the self-monitoring functionality. It consists of many low-cost, low-power and small-sized sensor nodes that can communicate with each other to perform sensing and data processing. Acting as an important role in the system, network coverage usually has a huge effect on the system’s lifetime.In this thesis, particle swarm algorithm was used as a method to optimize the coverage in the coverage of wireless sensor network. A network coverage optimization strategy based on particle swarm optimization was proposed and MATLAB was used as a tool to apply the algorithm. The model used in this thesis is the probability sensing model and the coverage type is area coverage. Effectiveness of the algorithm is proved by simulation. The simulation of the algorithm suggests the optimal deployment can be determined if a certain parameter which in this thesis is the sensing range is given.

Shooter localization systems are used to detect and locate the origin of gunfire. A wireless sensor network is one possible implementation of such a system. A wireless sensor network is sensitive to synchronization errors. Localization techniques that rely on the timing will give less accurate or even useless results if the synchronization errors are too large. This thesis focuses on the influence of synchronization errors on the abilityto localize a shooter using a wireless sensor network. A localization algorithm is developed and implemented and the effect of synchronization errors is studied. The localization algorithm is evaluated using numerical experiments, simulations, and data from real gunshots collected at field trials. The results indicate that the developed localization algorithm is able to localizea shooter with quite good accuracy. However, the localization performance is to a high degree influenced by the geographical configuration of the network as well as the synchronization error. / Skottlokaliseringssystem används för att upptäcka och lokalisera ursprunget för avlossade skott. Ett trådlöst sensornätverk är ett sätt att utforma ett sådant system.Trådlösa sensornätverk är känsliga för synkroniseringsfel. Lokaliseringsmetoder som bygger på tidsobservationer kommer med för stora synkroniseringsfel ge dåliga eller helt felaktiga resultat. Detta examensarbete fokuserar på vilken inverkan synkroniseringsfel har på möjligheterna att lokalisera en skytt i ett trådlöst sensornätverk. En lokaliseringsalgoritm utvecklas och förmågan att korrekt lokalisera en skytt vid olika synkroniseringsfel undersöks. Lokaliseringsalgoritmen prövas med numeriska experiment, simuleringar och även för data från riktiga skottljud, insamlade vid fältförsök. Resultaten visar att lokaliseringsalgoritmen fungerar tillfredställande, men att lokaliseringsförmågan till stor del påverkas av synkroniseringsfel men även av sensornätverkets geografiska utseende.

The use of wireless technology in the process industry is becoming increasingly important to obtain fast deployment at low cost. However, poor channel quality often leads to retransmissions, which are governed by Automatic Repeat Request (ARQ) schemes. While ARQ is a simple and useful tool to alleviate packet errors, it has considerable disadvantages: retransmissions lead to an increase in energy expenditure and latency. The use of Forward Error Correction (FEC) however offers several advantages. We consider a Hybrid-ARQ-Adaptive-FEC scheme (HAF) based on BCH codes and Channel State Information. This scheme is evaluated on AWGN and fading channels. It is shown that HAF offers significantly improved performance both in terms of energy efficiency and latency, as compared to ARQ.

This dissertation presents algorithms for achieving communication in the presence of adversarial attacks in large, decentralized, resource-constrained networks. We consider abstract single-hop communication settings where a set of senders 𝙎 wishes to directly communicate with a set of receivers 𝙍. These results are then extended to provide resource-efficient, multi-hop communication in wireless sensor networks (WSNs), where energy is critically scarce, and peer-to-peer (P2P) networks, where bandwidth and computational power are limited. Our algorithms are provably correct in the face of attacks by a computationally bounded adversary who seeks to disrupt communication between correct participants. The first major result in this dissertation addresses a general scenario involving single-hop communication in a time-slotted network where a single sender in 𝙎 wishes to transmit a message 𝘮 to a single receiver in 𝙍. The two players share a communication channel; however, there exists an adversary who aims to prevent the transmission of 𝘮 by periodically blocking this channel. There are costs to send, receive or block 𝘮 on the channel, and we ask: How much do the two players need to spend relative to the adversary in order to guarantee transmission of the message? This problem abstracts many types of conflict in information networks, and the associated costs represent an expenditure of network resources. We show that it is significantly more costly for the adversary to block 𝘮 than for the two players to achieve communication. Specifically, if the cost to send, receive and block 𝘮 in a slot are fixed constants, and the adversary spends a total of 𝘉 slots to try to block the message, then both the sender and receiver must be active in only O(𝘉ᵠ⁻¹ + 1) slots in expectation to transmit 𝘮, where φ = (1+ √5)/2 is the golden ratio. Surprisingly, this result holds even if (1) the value of 𝘉 is unknown to either player; (2) the adversary knows the algorithms of both players, but not their random bits; and (3) the adversary is able to launch attacks using total knowledge of past actions of both players. Finally, these results are applied to two concrete problems. First, we consider jamming attacks in WSNs and address the fundamental task of propagating 𝘮 from a single device to all others in a WSN in the presence of faults; this is the problem of reliable broadcast. Second, we examine how our algorithms can mitigate application-level distributed denial-of-service attacks in wired client-server scenarios. The second major result deals with a single-hop communication problem where now 𝙎 consists of multiple senders and there is still a single receiver who wishes to obtain a message 𝘮. However, many of the senders (strictly less than half) can be faulty, failing to send 𝘮 or sending incorrect messages. While the majority of the senders possess 𝘮, rather than listening to all of 𝙎 and majority filtering on the received data, we desire an algorithm that allows the single receiver to decide on 𝘮 in a more efficient manner. To investigate this scenario, we define and devise algorithms for a new data streaming problem called the Bad Santa problem which models the selection dilemma faced by the receiver. With our results for the Bad Santa problem, we consider the problem of energy-efficient reliable broadcast. All previous results on reliable broadcast require devices to spend significant time in the energy-expensive receiving state which is a critical problem in WSNs where devices are typically battery powered. In a popular WSN model, we give a reliable broadcast protocol that achieves optimal fault tolerance (i.e., tolerates the maximum number of faults in this WSN model) and improves over previous results by achieving an expected quadratic decrease in the cost to each device. For the case where the number of faults is within a (1-∊)-factor of the optimal fault tolerance, for any constant ∊>0, we give a reliable broadcast protocol that improves further by achieving an expected (roughly) exponential decrease in the cost to each device. The third and final major result of this dissertation addresses single-hop communication where 𝙎 and 𝙍 both consist of multiple peers that need to communicate in an attack-resistant P2P network. There are several analytical results on P2P networks that can tolerate an adversary who controls a large number of peers and uses them to disrupt network functionality. Unfortunately, in such systems, operations such as data retrieval and message sending incur significant communication costs. Here, we employ cryptographic techniques to define two protocols both of which are more efficient than existing solutions. For a network of 𝘯 peers, our first protocol is deterministic with O(log²𝘯) message complexity and our second protocol is randomized with expected O(log 𝘯) message complexity; both improve over all previous results. The hidden constants and setup costs for our protocols are small and no trusted third party is required. Finally, we present an analysis showing that our protocols are practical for deployment under significant churn and adversarial behaviour.

Wireless sensor networks offer the advantages of low cost, flexible measurement of phenomenon in a wide variety of applications, and easy deployment. Since sensor nodes are typically battery powered, energy efficiency is an important objective in designing sensor network algorithms. These algorithms are often application-specific, owing to the need to carefully optimize energy usage, and since deployments usually support a single or very few applications.<p> This thesis concerns applications in which the sensors monitor a continuous scalar field, such as temperature, and addresses the problem of determining the location of a contour line in this scalar field, in response to a query, and communicating this information to a designated sink node. An energy-efficient solution to this problem is proposed and evaluated. This solution includes new contour detection and query propagation algorithms, in-network-processing algorithms, and routing algorithms. Only a small fraction of network nodes may be adjacent to the desired contour line, and the contour detection and query propagation algorithms attempt to minimize processing and communication by the other network nodes. The in-network processing algorithms reduce communication volume through suppression, compression and aggregation techniques. Finally, the routing algorithms attempt to route the contour information to the sink as efficiently as possible, while meshing with the other algorithms. Simulation results show that the proposed algorithms yield significant improvements in data and message volumes compared to baseline models, while maintaining the integrity of the contour representation.

In distributed systems, dependency among different computations of an application leads to a problem of deciding the locations of computations. Spatial requirements of a computation can be expressed in terms of spatial relationships with other computations. This research presents programming abstractions and language constructs which can be used for specifying spatial coordination requirements for distributed computations. A spatial coordination middleware has been implemented for satisfying spatial coordination requirements of systems implemented using the Actor model of concurrent computation. Our approach abstracts spatial requirements of concurrent computations and provides key programming primitives for specifying these requirements. We have also implemented a number of higher level spatial coordination primitives which can be translated into the basic primitives. Spatial requirements can be specified using these primitives and then the runtime system converts them into a constraint satisfaction problem and satisfies them. Our approach reduces the programming complexity and provides a middleware which separates spatial requirements from functional code and enables the application programmer to change spatial requirements at runtime without effecting application's functionality. We have identified some of the high level primitives and provided a mechanism to develop high level primitives on top of the basic primitives. This thesis presents the rationale, design, implementation, and evaluation of spatial coordination. By comparing programs written with and without our spatial coordination primitives, we show how spatial coordination enables a programmer to specify spatial requirements declaratively and simplify the programming task. Experimental results demonstrate the performance of the approach, as the number of constraints increases.

The objective of this thesis is to address the problem of energy conservation in wireless sensor networks by tackling two fundamental problems: topology control and data delivery. We first address energy-aware topology control taking into account throughput per unit energy as the primary metric of interest. Through both experimental observations and analysis, we show that the optimal topology is a function of traffic load in the network. We then propose a new topology control scheme, Adaptive Topology Control (ATC), which increases throughput per unit energy. Based on different coordinations among nodes, we proposed three ATC schemes: ATC-CP, ATC-IP, and ATC-MS. Through simulations, we show that three ATC schemes outperform static topology control schemes, and particularly the ATC-MS has the best performance under all environments. Secondly, we explore an energy-aware data delivery problem consisting of two sub-problems: downstream (from a sink to sensors) and upstream (from sensors to a sink) data delivery. Although we address the problems as two independent ones, we eventually solve those problems with two approaches: GARUDA-DN and GARUDA-UP which share a common structure, the minimum dominating set. For the downstream data delivery, we consider reliability as well as energy conservation since unreliable data delivery can increase energy consumption under high data loss rates. To reduce energy consumption and achieve robustness, we propose GARUDA-DN which is scalable to the network size, message characteristics, loss rate and the reliable delivery semantics. From ns2-based simulations, we show that GARUDA-DN performs significantly better than the basic schemes proposed thus far in terms of latency and energy consumption. For the upstream data delivery, we address an energy efficient aggregation scheme to gather correlated data with theoretical solutions: the shortest path tree (SPT), the minimum spanning tree (MST) and the Steiner minimum tree (SMT). To approximate the optimal solution in case of perfect correlation among data, we propose GARUDA-UP which combines the minimum dominating set (MDS) with SPT in order to aggregate correlated data. From discrete event simulations, we show that GARUDA-UP outperforms the SPT and closely approximates the centralized optimal solution, SMT, with less amount of overhead and in a decentralized fashion.