Algorithms for Sensor Systems

Name: 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
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

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

Thomas Erlebach Sotiris Nikoletseas Pekka Orponen(Herausgeber*in)

Springer (Verlag)

1. Auflage

Erschienen am 9. Februar 2012

X, 239 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-28209-6 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken