Algorithms for self-organizing wireless sensor networks

A sensor network consists of a set of nodes powered by batteries and collaborating to perform sensing tasks in a given environment. It may contain one or more sink nodes (base stations) to collect sensed data and communicate it to a central processing and storage system. A sensor node is typically powered by a battery and can be divided into three main functional units: a sensing unit, a communication unit and a computing unit.; The unique characteristics of sensor networks pose numerous challenges that have to be overcome to enable their efficient and reliable use. In particular, sensor networks are highly energy constrained because of their reliance on battery power and the difficulty and cost of battery replacement. These networks are generally composed of a large number of inexpensive and potentially unreliable individual nodes. These characteristics render the efficient collaboration between individual nodes essential to the accomplishment of the overall network task and justify the development of new algorithms to provide services such as information processing, messages routing, fault-tolerance, localization, naming and addressing.; This work increases the knowledge on the growing field of algorithms for wireless sensor networks by contributing a new evaluation tool and two new algorithms.; A new sensor network simulator that can be used to evaluate sensor network algorithms and sensor network architectures in general is discussed. The simulator incorporates models for the different functional units composing a sensor node and characterizes the energy consumption of each. It is designed in a modular and efficient way favoring the ease of use and extension. The simulator allows the user to choose from different implementations of energy models, accuracy models, communication protocols, application classes and types of sensors. New models can be easily added if necessary.; The second contribution of this thesis is a distributed algorithm to solve the unique ID assignment problem in sensor networks. Our solution starts by assigning long unique IDs and organizing nodes in a tree structure. This tree structure is used to compute the size of the network. Then, unique IDs are assigned using the minimum number of bytes. Globally unique IDs are useful in providing many network functions, e.g. configuration, monitoring of individual nodes and various security mechanisms. Theoretical and simulation analysis of the ID assignment algorithm solution are presented. The results demonstrate that a high percentage of nodes are assigned globally unique IDs at the termination of the algorithm when the algorithm parameters are set properly. Furthermore, the algorithm terminates in a relatively short time that scales well with the network size.; The third contribution of this thesis is a general fault-tolerant event detection scheme that allows nodes to detect erroneous local decisions based on the local decisions reported by their neighbors. This detection scheme does not assume homogeneity of sensor nodes and can handle cases where nodes have different and dynamic accuracy levels. We prove analytically that the derived fault-tolerant estimator is optimal under the maximum a posteriori (MAP) criterion. An equivalent weighted voting scheme is derived. Further, we describe two new error models that take into account the neighbor distance and the geographical distributions of the two decision quorums. These models are particularly suitable for detection applications where the event under consideration is highly localized.