Algorithmic Aspects of Wireless Sensor Networks: Fourth International Workshop, Algosensors 2008, Reykjavik, Iceland, July 2008. Revised Selected Pape

ISBN-13: 9783540928614 / Angielski / Miękka / 2008 / 151 str.

Sandor P. Fekete

Opis

Wireless ad-hoc sensor networks are a very active research subject, as they have highpotentialtoprovidediverseservicestonumerousimportantapplications, - cluding remote monitoring and tracking in environmental applications and low-maintenance ambient intelligence in everyday life. The e?ective and e?cient realizationofsuchlarge-scale, complexad-hocnetworkingenvironmentsrequires intensive, coordinated technical research and development e?orts, especially in power-aware, scalable, robust wireless distributed protocols, due to the unusual applicationrequirementsandthesevereresourceconstraintsofthesensordevices. On the other hand, a solid foundational backgroundseems necessary for s- sornetworkstoachievetheirfullpotential.Itisachallengeforabstractmodeling, algorithmic design and analysis to achieve provably e?cient, scalable and fau- tolerant realizations of such huge, highly dynamic, complex, non-conventional networks. Features including the extremely large number of sensor devices in the network, the severe power, computing and memory limitations, their dense, random deployment and frequent failures pose new, interesting challenges of great practical impact for abstract modeling, algorithmic design, analysis and implementation. This workshop aimed at bringing together research contributions related to diversealgorithmicandcomplexity-theoreticaspectsofwirelesssensornetworks. Thiswasthefourtheventintheseries.ALGOSENSORS2004washeldinTurku, Finland, ALGOSENSORS 2006 was held in Venice, Italy, and ALGOSENSORS 2007 was held in Wroc law, Poland. Since its beginning, ALGOSENSORS has beencollocatedwithICALP.PreviousproceedingshaveappearedintheSpringer LNCS series: vol. 3121 (2004), vol. 4240 (2006), and vol. 4837 (2007). ALGOSENSORS2008waspartofICALP2008andwasheldonJuly122008 in Reykjavik, Iceland. After a careful review by the ProgramCommittee, 11 out of 27 submissions were accepted; in addition, a keynote speech was given by RogerWattenhofer.TheProgramCommitteeappreciatesthehelpof35external referees, who provided additional expertise. We are also thankful for the help of the sponsors (EU-project "FRONTS" and coalesenses), who supported the organization of the meeting as well as a best-paper award.

Spis treści

Algorithms for Sensor Networks: What Is It Good for?.- Tight Local Approximation Results for Max-Min Linear Programs.- Minimizing Average Flow Time in Sensor Data Gathering.- Target Counting under Minimal Sensing: Complexity and Approximations.- Efficient Scheduling of Data-Harvesting Trees.- Link Scheduling in Local Interference Models.- Algorithms for Location Estimation Based on RSSI Sampling.- Random Fault Attack against Shrinking Generator.- Probabilistic Protocols for Fair Communication in Wireless Sensor Networks.- Simple Robots in Polygonal Environments: A Hierarchy.- Deployment of Asynchronous Robotic Sensors in Unknown Orthogonal Environments.- Optimal Backlog in the Plane.

Blurb

This book constitutes the reviewed proceedings of the Fourth International Workshop on Algorithmic Aspects of Wireless Sensor Networks, ALGOSENSORS 2008, held in Reykjavik, Iceland, Wroclaw, Poland, July 12, 2008.

The workshops aimed at bringing together research contributions related to diverse algorithmic and complexity-theoretic aspects of wireless sensor networks. The topics include but are not limited to optimization problems, noise and probability, robots and tours.