Efficient Algorithms for Structuring Wireless Sensor Networks

A number of application scenarios benefit from using wireless sensor networks for monitoring, tracking and event detection. Since sensor nodes are small and energy-constrained and possess severely limited computational capabilities and memory resources, sensor networks require the development of a new generation of algorithms targeted at large-scale networks, unpredictably changing environments and constantly changing network topologies. Structures result from self-organization of the nodes in the network and are defined in terms of the cooperation between individual nodes. Many sensor network systems require constructing structures in order to perform correctly. This work focuses on both the development and study of structuring algorithms. We present new algorithms for several problems covering the distinctive characteristics of sensor networks: cooperative sensing, communication and location awareness. The problems are energy-efficient routing, time-bounded and space-bounded sensing, range-free boundary recognition, and hierarchical partitioning of the network.