Algorithmic Aspects of Wireless Sensor Networks: First International Workshop, ALGOSENSORS 2004, Turku, Finland, July 16, 2004, Proceedings (Lecture Notes in Computer Science (3121))

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. 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. Sotiris Nikoletseas, José D.p. Rolim (eds.). Includes Bibliographical References And Index. Also Issued Online. 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: {u2013} Modeling of speci?c sensor networks. {u2013} Methods for ad hoc deployment. {u2013} Algorithms for sensor localization and tracking of mobile users. {u2013} Dynamic sensor networks. {u2013} Hierarchical clustering architectures. {u2013} Attribute-based named networks. {u2013} Routing: implosion issues and resource management. {u2013} Communication protocols. {u2013} Media access control in sensor networks. {u2013} Simulators for sensor networks Front Matter....Pages - Algorithm Design and Optimization for Sensor Systems....Pages 1-2 Algorithmic and Foundational Aspects of Sensor Systems....Pages 3-8 On a Conjecture Related to Geometric Routing....Pages 9-17 WiseMAC: An Ultra Low Power MAC Protocol for Multi-hop Wireless Sensor Networks....Pages 18-31 On the Computational Complexity of Sensor Network Localization....Pages 32-44 A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks....Pages 45-58 Balanced Data Gathering in Energy-Constrained Sensor Networks....Pages 59-70 Scale Free Aggregation in Sensor Networks....Pages 71-84 The Expected Uncertainty of Range Free Localization Protocols in Sensor Networks....Pages 85-97 Towards a Dynamical Model for Wireless Sensor Networks....Pages 98-108 Efficient Delivery of Information in Sensor Networks Using Smart Antennas....Pages 109-122 Neighborhood-Based Topology Recognition in Sensor Networks....Pages 123-136 A Novel Fault Tolerant and Energy-Aware Based Algorithm for Wireless Sensor Networks....Pages 137-146 Route Discovery with Constant Memory in Oriented Planar Geometric Networks....Pages 147-156 Probabilistic Model for Energy Estimation in Wireless Sensor Networks....Pages 157-170 Multi: A Hybrid Adaptive Dissemination Protocol for Wireless Sensor Networks....Pages 171-186 Constrained Flow Optimization with Applications to Data Gathering in Sensor Networks....Pages 187-200 Back Matter....Pages - This book constitutes the reviewed proceedings of the First International Workshop on Algorithmic Aspects of Wireless Sensor Networks, ALGOSENSORS 2004, held in Turku, Finland in July 2004, in association with ICALP 2004. The 15 revised full papers presented together with abstracts of two invited papers were carefully reviewed and selected from 40 submissions. Among the topics addressed are sensor network modeling, algorithms for sensor localization, dynamic sensor networks, sensor network architectures, attribute-based named networks, routing, communication protocols, access control in sensor networks, sensor architecture, and energy consumption issues