Algorithmic Aspects of Wireless Sensor Networks

This volume contains the contributed papers and invited talks presented at the 1stInternationalWorkshoponAlgorithmicAspectsofWirelessSensorNetworks (ALGOSENSORS 2004), which was held July 16, 2004, in Turku, Finland, - located with the 31st International Colloquium on Automata, Languages, and Programming (ICALP 2004). Wireless ad hoc sensor networks have become a very important research subject due to their potential to provide diverse services in numerous appli- tions. The realization of sensor networks requires intensive technical research and development e?orts, especially in power-aware scalable wireless ad hoc c- munications protocols, due to their unusual application requirements and severe constraints. On the other hand, a solid theoretical background seems necessary for sensor networks to achieve their full potential. It is an algorithmic challenge to achieve e?cient and robust realizations of such large, highly dynamic, complex, n- conventional networking environments. Features, including the huge number of sensor devices involved, the severe power, computational and memory limi- tions, their dense deployment and frequent failures, pose new design, analysis and implementation challenges. This event is intended to provide a forum for researchers and practitioners to present their contributions related to all aspects of wireless sensor networks. Topics of interest for ALGOSENSORS 2004 were: - Modeling of speci?c sensor networks. - Methods for ad hoc deployment. - Algorithms for sensor localization and tracking of mobile users. - Dynamic sensor networks. - Hierarchical clustering architectures. - Attribute-based named networks. - Routing: implosion issues and resource management. - Communication protocols. - Media access control in sensor networks. - Simulators for sensor networks.

Inhalt

Invited Talks.- Algorithm Design and Optimization for Sensor Systems.- Algorithmic and Foundational Aspects of Sensor Systems.- Contributed Papers.- On a Conjecture Related to Geometric Routing.- WiseMAC: An Ultra Low Power MAC Protocol for Multi-hop Wireless Sensor Networks.- On the Computational Complexity of Sensor Network Localization.- A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks.- Balanced Data Gathering in Energy-Constrained Sensor Networks.- Scale Free Aggregation in Sensor Networks.- The Expected Uncertainty of Range Free Localization Protocols in Sensor Networks.- Towards a Dynamical Model for Wireless Sensor Networks.- Efficient Delivery of Information in Sensor Networks Using Smart Antennas.- Neighborhood-Based Topology Recognition in Sensor Networks.- A Novel Fault Tolerant and Energy-Aware Based Algorithm for Wireless Sensor Networks.- Route Discovery with Constant Memory in Oriented Planar Geometric Networks.- Probabilistic Model for Energy Estimation in Wireless Sensor Networks.- Multi: A Hybrid Adaptive Dissemination Protocol for Wireless Sensor Networks.- Constrained Flow Optimization with Applications to Data Gathering in Sensor Networks.