5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks
July 10-11, 2009, Rhodes, Greece

Dates
Submission deadline: April 30, 2009
Acceptance notification: May 30, 2009
Camera-ready pre-proceedings: June 15, 2009
Camera-ready post-proceedings: August 31, 2009

Program Committee
James Aspnes, Yale
Chen Avin, Ben Gurion U.
Ed Coffman, Columbia U.
Shlomi Dolev, Ben Gurion U., Program Chair
Ted Herman, U. of Iowa
Seth Gilbert, EPFL
Chryssis Georgiou, U. of Cyprus
Mordecai Golin, Hong Kong UST
Maria Gradinariu Potop-Butucaru, Paris 6
Alex Kesselmen, Google
Darek Kowalski, U. of Liverpool
Evangelos Kranakis, Carleton
Danny Krizanc, Wesleyan
Limor Lahiani, Microsoft Israel R&D Center
Flaminia Luccio, U. C`a Foscari Venezia
Nancy Lynch, MIT
Thomas Moscibroda, Microsoft Research
Seffi Naor, Technion
Calvin Newport, MIT
Rafail Ostrovsky, UCLA
Marina Papatriantafilou, Chalmers U.
Andrzej Pelc, U. du Qu ́ebec
Giuseppe Persiano, U. Salerno
Jose Rolim, U. of Geneve
Nicola Santoro, Carleton
Elad Schiller, Chalmers U.
Paul Spirakis, U. of Patras and CTI
Eli Upfal, Brown
Jennifer Welch, Texas A&M
Moti Yung, Google

Steering Committee
Josep Diaz, T.U. of Catalonia
Jan van Leeuwen, U. of Utrecht
Sotiris Nikoletseas, U. of Patras and CTI (Chair)
Jose Rolim, U. of Geneva
Paul Spirakis, U. of Patras and CTI

Proceedings
Accepted papers will be published in full text in hardcopy proceedings, which are planned to appear in the Lecture Notes in Computer Science (LNCS) Series of Springer Verlag after August 2009. Submissions may be considered for a two-pages brief announcement in case not accepted as a full text; au- thors that wish their paper to be considered for both full paper and brief announcement tracks should in- dicate this fact in the front page.

TCS Journal Special Issue
As in previous years, it is planned that selected high-quality papers will be considered for publication in a Special Issue on Algorithmic Aspects of Wireless Sensor Networks of Theoretical Computer Science (TCS).
Scope
Wireless ad-hoc sensor networks have recently become a very active research subject due to their high potential of providing diverse services to numerous important applications, including remote monitoring and tracking in environmental applications and low maintenance ambient intelligence in everyday life. The effective and efficient realization of such large scale, complex ad-hoc networking environments requires intensive, coordinated technical research and development efforts, especially in power aware, scalable, robust wireless distributed protocols, due to the unusual application requirements and the severe resource constraints of the sensor devices.
On the other hand, a solid foundational background seems necessary for sensor networks to achieve their full potential. It is a challenge for abstract modeling, algorithmic design and analysis to achieve provably efficient, scalable and fault-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 abstract modeling, algorithmic design, analysis and implementation challenges of great practical impact.

Algosensors aims to bring together research contributions related to diverse algorithmic and complexity theoretic aspects of wireless sensor networks. Contributions solicited cover the algorithmic issues in a variety of topics including, but not limited to:
- Abstract models of sensor networks
- Virtual infrastructures
- Infrastructure discovery
- Methods for ad-hoc deployment/topology control
- Data propagation and routing
- Data aggregation/data compression
- Error and erasure correcting codes for information dispersal
- Energy management
- Power saving schemes
- Communication protocols
- Medium access control
- Localization
- Tracking
- Fault tolerance and dependability
- Self-stabilization
- Adaptiveness and Self-organization
- Game theoretic aspects
- Cryptography, Security and trust
- Distributed computing issues
- Time synchronization
- Swarm computing
- Mobile robotic sensors
- Algorithms for RFID
- Obstacle avoidance

How to Submit: Authors are invited to submit manuscripts reporting original research in the topics related to the workshop. Simultaneous submission to other conferences is not allowed. Papers should not exceed twelve (12) pages of text using at least 11 point size type, including references, figures, tables, etc., preferably formatted in the LNCS style. Additional material may be added at a clearly marked Appendix to be read at the discretion of the Program Committee Members. Authors must submit their papers electronically via Web page: http://www.algosensors.org. All papers will be peer reviewed and comments will be provided to the authors. Authors need to make sure that for each accepted paper at least one author will attend the workshop.

Accepted Papers
- Bernadette Charron-Bost, Jennifer Welch and Josef Widder. Link Reversal: How to play better to work less
- Marek Klonowski, Miroslaw Kutylowski and Jan Zatopianski. Energy Efficient Alert in Single-Hop Networks of Extremely Weak Devices
- David Kirkpatrick and Sergey Bereg. Approximating barrier resilience in wireless sensor networks
- Milan Bradonjic, Eddie Kohler and Rafail Ostrovsky. Near-Optimal Radio Use For Wireless Network Synchronization
- Olaf Bonorden, Bastian Degener, Barbara Kempkes and Peter Pietrzyk. Complexity and approximation of a geometric local robot assignment problem
- Chen Avin, Zvi Lotker, Francesco Pasquale and Yvonne Anne Pignolet. A Note on Uniform Power Connectivity in the SINR Model
- Sorelle Friedler and David Mount. Compressing Kinetic Data From Sensor Networks
- Zeev Nutov and Michael Segal. Improved Approximation Algorithms for Maximum Lifetime Problems in Wireless Networks
- Jacek Cichon, Jaroslaw Grzaslewicz and Miroslaw Kutylowski. Securing Random Key Predistribution Against Node Captures
- Onur Tekdas, Yokesh Kumar, Volkan Isler and Ravi Janardan. Building a Communication Bridge with Mobile Hubs
- Saira Viqar and Jennifer Welch. Deterministic Collision Free Communication Despite Continuous Motion
- Pierre Leone, Marina Papatriantafilou and Elad M. Schiller. Relocation Analysis of Stabilizing MAC Algorithms for Large-Scale Mobile Ad Hoc Networks
- Michael Keane, Evangelos Kranakis, Danny Krizanc and Lata Narayanan. Routing on Delay Tolerant Sensor Networks
- Florian Huc, Aubin Jarry, Pierre Leone, Jose Rolim, Luminita Moraru and Sotiris Nikoletseas. Early Obstacle Detection and Avoidance for All to All Traffic Pattern in Wireless Sensor Networks
- Paolo D’Arco, Alessandra Scafuro and Ivan Visconti. Revisiting DoS Attacks and Privacy in RFID-Enabled Networks
- Carme Alvarez, Amalia Duch, Joaquim Gabarro and Maria Serna. Sensor Field: A computational model
- Peter Glaus. Locating a Black Hole without the Knowledge of Incoming Link
- Xiaoyang Guan. Better Face Routing Protocols
- Avery Miller. Gossiping in Jail
- Stefan Dziembowski, Alessandro Mei and Alessandro Panconesi. On Active Attacks on Sensor Network Key Distribution Schemes
- Yoann Dieudonne and Franck Petit. Self-stabilizing Deterministic Gathering
- Brief Announcements
- Srivathsan Srinivasagopalan, Costas Busch and Sitharama Iyengar. Brief Announcement: Universal Data Aggregation Trees for Sensor Networks in Low Doubling Metrics
- Djamel Djenouri and Ilangko Balasingham. Brief Announcement: MOGRIBA: Multi-Objective Geographical Routing for Biomedical Applications of Wireless Sensor Networks

Program
Friday, July 10 2009
12:50-13:00 | Algosensors Welcome | |
13:00-14:00 | Algosensors Invited talk Erik Demaine
Actuator Nets: Folding, Reconfiguring, and Deploying Sensors |
|
14:00-14:25 | Carme Alvarez, Amalia Duch, Joaquim Gabarro and Maria Serna.
Sensor Field: A computational model |
|
14:25-14:50 | Milan Bradonjic, Eddie Kohler and Rafail Ostrovsky.
Near-Optimal Radio Use For Wireless Network Synchronization |
|
14:50-15:10 | Break. | |
15:10-15:35 | David Kirkpatrick and Sergey Bereg.
Approximating barrier resilience in wireless sensor networks |
|
15:35-16:00 | Zeev Nutov and Michael Segal.
Improved Approximation Algorithms for Maximum Lifetime Problems in Wireless Networks |
|
16:00-16:20 | Coffee Break | |
16:20-16:55 | Stefan Dziembowski, Alessandro Mei and Alessandro Panconesi.
On Active Attacks on Sensor Network Key Distribution Schemes |
|
16:55-17:20 | Jacek Cichon, Jaroslaw Grzaslewicz and Miroslaw Kutylowski.
Securing Random Key Predistribution Against Node Captures |
|
17:20-17:45 | Paolo D’Arco, Alessandra Scafuro and Ivan Visconti.
Revisiting DoS Attacks and Privacy in RFID-Enabled Networks |
Saturday, July 11 2009
09:00-10:00 | Algosensors invited talk Allan Borodin.
The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanism Design for Combinatorial Auctions |
10:00-10:25 | Bernadette Charron-Bost, Jennifer Welch and Josef Widder.
Link Reversal: How to play better to work less |
10:25-10:50 | Florian Huc, Aubin Jarry, Pierre Leone, Jose Rolim, Luminita Moraru and Sotiris Nikoletseas.
Early Obstacle Detection and Avoidance for All to All Traffic Pattern in Wireless Sensor Networks. |
10:50-11:10 | Coffee Break |
11:10-11:35 | Chen Avin, Zvi Lotker, Francesco Pasquale and Yvonne Anne Pignolet.
A Note on Uniform Power Connectivity in the SINR Model. |
11:35-12:00 | Peter Glaus.
Locating a Black Hole without the Knowledge of Incoming Link. |
12:00-12:25 | Marek Klonowski, Miroslaw Kutylowski and Jan Zatopianski.
Energy Efficient Alert in Single-Hop Networks of Extremely Weak Devices Brief Announcments |
12:25-12:35 | Srivathsan Srinivasagopalan, Costas Busch and Sitharama Iyengar.
Brief Announcement: Universal Data Aggregation Trees for Sensor Networks in Low Doubling Metrics |
12:35-12:45 | Djamel Djenouri and Ilangko Balasingham.
Brief Announcement: MOGRIBA: Multi-Objective Geographical Routing for Biomedical Applications of Wireless Sensor Networks |
12:45-13:25 | Lunch |
13:25-13:50 | Michael Keane, Evangelos Kranakis, Danny Krizanc and Lata Narayanan.
Routing on Delay Tolerant Sensor Networks. |
13:50-14:15 | Xiaoyang Guan.
Better Face Routing Protocols. |
14:15-14:40 | Onur Tekdas, Yokesh Kumar, Volkan Isler and Ravi Janardan.
Building a Communication Bridge with Mobile Hubs. |
14:40-15:05 | Sorelle Friedler and David Mount.
Compressing Kinetic Data From Sensor Networks |
15:05-15:25 | Break |
15:25-15:50 | Pierre Leone, Marina Papatriantafilou and Elad M. Schiller.
Relocation Analysis of Stabilizing MAC Algorithms for Large-Scale Mobile Ad Hoc Networks. |
15:50-16:15 | Saira Viqar and Jennifer Welch.
Deterministic Collision Free Communication Despite Continuous Motion. |
16:15-16:40 | Yoann Dieudonne and Franck Petit.
Self-stabilizing Deterministic Gathering. |
16:40-17:00 | Coffee Break |
16:40-17:05 | Avery Miller .
Gossiping in Jail. |
17:05-17:30 | Olaf Bonorden, Bastian Degener, Barbara Kempkes and Peter Pietrzyk.
Complexity and approximation of a geometric local robot assignment problem. |
17:30-17:50 | Plans for the future of ALGOSENSORS and Goodbye. |