ALGOSENSORS 2009

5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks

July 10-11, 2009, Rhodes, Greece

Salvador Dali – Colossus of Rhodes

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

The entrance of the old harbor of Rhodes

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

City of Rhodes, gravure

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

Rhodes Medieval Town

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.

Rhode s Old Town

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.

Palace of the Grandmaster

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
Colossus, gravure

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.

Rhodes Yacht Harbor

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
Tsambika Beach

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.