Algorithms for Sensor Systems
7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers
Published on 9. February 2012
X, 239 pages
978-3-642-28209-6 (ISBN)
Description
This book constitutes the thoroughly refereed post-conference proceedings of the 7th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks, and Autonomous Mobile Entities, ALGOSENSORS 2011, held in Saarbrücken, Germany, in September 2011. The 16 revised full papers presented together with two invited keynote talks were carefully reviewed and selected from 31 submissions. The papers are organized in two tracks: sensor networks, covering topics such as localization, lifetime maximization, interference control, neighbor discovery, self-organization, detection, and aggregation; and ad hoc wireless and mobile systems including the topics: routing, scheduling and capacity optimization in the SINR model, continuous monitoring, and broadcasting.
More details
Other editions
Additional editions
Thomas Erlebach | Sotiris Nikoletseas | Pekka Orponen
Algorithms for Sensor Systems
7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers
Book
02/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title Page
- Preface
- Organization
- Table of Contents
- Invited Talks
- Dynamic Multi-party Computation Forever for Swarm and Cloud Computing and Code Obfuscation
- References
- Local, Self-organizing Strategies for Robotic Formation Problems
- Introduction
- The Gathering Problem
- The Robot Chain Problem
- Outlook
- References
- Sensor Networks Track
- Local Approximation Algorithmsfor the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks
- Introduction
- Preliminaries
- Approximation Algorithms
- (5+\epsilon)-Approximation in O(log1+\epsilon^n) Rounds
- (3+\epsilon)-Approximation in O(log^2_{1+\epsilon}n) Rounds
- Dealing with Dynamics
- Conclusion
- References
- Appendix
- Maximizing Network Lifetime o n the Line with Adjustable Sensing Ranges
- Introduction
- Previous Research
- Our Contribution
- Preliminaries
- Analysis of RoundRobin Algorithms
- RoundRobin
- k-RoundRobin
- log2-RoundRobin
- Optimizations
- Open Problems
- References
- Appendix
- Sensor Fusion: From Dependence Analysis via Matroid Bases to Online Synthesis
- Introduction
- Preliminaries
- A Matroid-Based Framework for Identifying Non-correlated Sensors
- A Sensor Fusion Algorithm via Exponential Weighting
- Results on Real and Artificial Data
- References
- Neighbor Discovery in a Sensor Network with Directional Antennae
- Introduction
- Preliminaries and Notation
- Related Work
- Outline and Results of the Paper
- Deterministic Algorithms for Neighbor Discovery
- Lower Bound
- Antenna Rotation Algorithms
- Complexity of Deterministic Antenna Orientation Algorithm
- Randomized Neighbor Discovery Algorithms
- Deterministic Algorithm with Selection of Random Delay
- Algorithm with Random Selection of Rotation Mechanism
- Algorithm If Bound on Antenna Beam Widths Is Known
- Conclusion and Open Problems
- References
- LiMoSense - Live Monitoring in Dynamic Sensor Networks
- Introduction
- Related Work
- Model and Problem Definition
- Model
- The Live Average Monitoring Problem
- The LiMoSense Algorithm
- Failure-Free Algorithm
- Adding Robustness
- Correctness Overview
- Evaluation
- Static
- Dynamic
- Conclusion
- References
- Evader Interdiction and Collateral Damage
- Introduction
- Preliminaries
- Oblivious Innocents and Evaders Oblivious or Not
- Paths, Trees, and Cycles
- General Graphs
- Reactive Innocents and the Bridges Problem
- Convex Bridge Sets
- The Min-error FP+FN Setting
- References
- Proofs
- Other Hardness Results
- Efficient Algorithms for Network Localization Using Cores of Underlying Graphs
- Introduction
- Preliminaries
- The Length of Longest Induced Cycles and the Dimension of Spaces
- Cycles in Higher-Dimensional Spaces
- Polynomial-Time Algorithm for WGEd on Chordal Graphs
- Algorithms for Graphs with Dominating Cores
- General Frameworks for d {1,2}
- Applications of General Frameworks
- Concluding Remarks
- References
- Proof of Theorem 3.4
- Minimizing Average Interference through Topology Control
- Introduction
- Problem Definitions
- Minimizing Average Interference in 1D Networks
- Independent Subproblems
- Algorithms
- Analysis
- Bound on MMI while Minimizing Average Interference
- Preliminaries
- The Upper Bound
- Minimizing Average Interference in 2D Networks
- Basic Ideas
- Algorithms to Compute MAI
- Analysis
- Conclusion
- References
- On Barrier Resilience of Sensor Networks
- Introduction
- Reduction to Edge Colouring of (Bi)3-graphs
- Problem Statement
- Reduction
- Proof of Correctness
- Reduction to ULS-RES
- Relationship to Resilience of a Sensor Network
- Building the Obstacle Environment
- Correctness of the Reduction
- Extension to Other Sensor Shapes
- Hardness of Approximation
- Conclusion
- References
- Distributed (? + 1)-Coloring in the Physical Model
- Introduction
- Related Work
- Our Contribution
- Problem Definitions and Model
- An O(logn+log2n) (?+1)-Coloring Algorithm
- Analysis
- Distributed (? +1)-Coloring for Uniform Power Assignment
- Conclusion
- References
- Ad Hoc Wireless and Mobile Systems Track
- Continuous Monitoring in the Dynamic Sensor Field Model
- Introduction
- The Dynamic Sensor Field Model
- Continuous Monitoring of Static Data
- Continuous Monitoring of Dynamic Data Using Static Devices
- Continuous Monitoring of Dynamic Data Using Dynamic Devices
- Conclusion and Open Problems
- References
- Minimum-Cost Broadcast through Varying-Size Neighborcast
- Introduction
- Preliminaries
- Problem Settings Parameterized by b
- b=0 and b=1
- b log2 3
- 1 b log2 3
- 0 & b & 1
- Conclusion
- References
- Hardness Results
- Real-Time Video Streaming in Multi-hop Wireless Static Ad Hoc Networks
- Introduction
- Problem Definition
- Preliminaries
- Interference Models
- Algorithm MF-I-S
- Networks Governed by Time-Slotted Frequency Tables
- Algorithm Specification
- Algorithm Description
- Flow Control
- Experimental Results
- Scenarios
- Benchmarks
- Results
- Conclusions
- Discussion
- References
- Multi-hop Routing and Scheduling in Wireless Networks in the SINR Model
- Introduction
- Preliminaries
- Problem Definition
- Necessary Conditions: sinr-Feasibility for Links in the Same Bucket
- A Geometric Lemma
- Necessary Conditions
- LP Relaxation
- Algorithm
- Algorithm Description
- Removing Minuscule Flow Paths
- Greedy Multi-coloring
- The Dispersion Procedure disperse
- Algorithm Analysis
- Given Arbitrary Transmission Powers
- Limited Powers
- References
- Wireless Capacity with Arbitrary Gain Matrix
- Introduction
- Related Work
- SDP-Based Algorithm
- Numerical Experiments
- Conclusion
- References
- On the Capacity of Oblivious Powers
- Introduction
- Problem Formulation
- Conjugate Power Assignments
- Non-increasing and Super-Linearly Increasing Power Assignments
- The Capacity of $L_ 0$
- Comparing the Two Communication Models
- Noise Factor
- Future Work
- References
- Author Index
