Algorithmic Aspects of Wireless Sensor Networks
by Shlomi Dolev
- Length: 274 pages
- Edition: 2
- Language: English
- Publisher: Springer
- Publication Date: 2009-10-26
- ISBN-10: 3642054331
- ISBN-13: 9783642054334
- Sales Rank: #0 (See Top 100 Books)
This book constitutes the reviewed proceedings of the 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks, ALGOSENSORS 2009, held in Rhodes, Greece, July 10-11, 2009. The 21 full papers and two brief announcements were carefully selected from 41 submissions. This 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.
Front matter Chapter 1 Invited Talk I Actuator Nets: Folding, Reconfiguring and Deploying Sensors Chapter 2 Invited Talk II The Power and Limitations of Simple Algorithms: A Partial Case Study of Greedy Mechanisim Design for Combinatorial Actions Chapter 3 Sensor Field: A Computational Model Introduction Static Synchronous Sensor Field: The Model {\sf SSSF}s Solving the Average Monitoring Problem {\sf SSSF}s of Devices with Constant Memory Capacity Trading Space/Time for Size Conclusions and Future Work References Chapter 4 Near-Optimal Radio Use for Wireless Network Synchronization Introduction Mathematical Preliminaries Lower Bounds Matching Upper Bound for Two Processors Upper Bound for $m$ Processors Protocol That Does Not Need to Know the Number of Processors Our Model Can Handle Different Clocks' Speeds with Bounded Ratio Conclusions and Open Problems References Chapter 5 Approximating Barrier Resilience in Wireless Sensor Networks Introduction Background and Related Work $k$-Barrier Coverage of Belt Regions The Minimum Colour Single Path Problem Relating Resilience and Thickness for Unit Disk Sensors Shortest Paths Avoiding Disk Obstacles Proof of Lemma 1 Tightening the Approximation Factor Extensions References Chapter 6 Improved Approximation Algorithms for Maximum Lifetime Problems in Wireless Networks Introduction Previous Work Our Results Weighted Degree Constrained Network Design Proof of Theorems 1 and 2 Partial Level Aggregation Convergecast References Chapter 7 On Active Attacks on Sensor Network Key Distribution Schemes Introduction Key Distribution in Sensor Networks Active vs. Passive Security of the Key Distribution Schemes The Power of Active Attacks Definition The Construction Based on the Scheme of [2] References Chapter 8 Key Levels and Securing Key Predistribution against Node Captures Introduction Key Layers Scheme Single Key Case Expected Time of Adversary Attack Key Trees Evolving Keys Zigzag Key Predistribution References Chapter 9 Revisiting DoS Attacks and Privacy in RFID-Enabled Networks Introduction RFID Security and Privacy Model DoS-Resilient Privacy Notions for RFID Semi-destructive Privacy: Definition and Construction Semi-destructive Privacy for Low-Cost Tags References Chapter 10 Link Reversal: How to Play Better to Work Less Introduction The LR Algorithm Definitions and Work Complexity Locally Uniform Link Labelings Labelings and Work The $LU$ Policy as a Game Game-Theoretic Definitions Properties of Strategy Profiles: The $FR$ Strategy The $PR$ Strategy: A Socially Conscious Choice Properties of Mixed Strategy Profiles Conclusions References Chapter 11 Early Obstacle Detection and Avoidance for All to All Traffic Pattern in Wireless Sensor Networks Introduction State of the Art Single Destination Routing and $Dead-Ends$ Detection Multiple Directions Routing and $Dead-Ends$ Detection Dead-End Analysis Reactive Dead-End Discovery Simulation Results Stretch Dead-End Nodes Convergence Time Conclusion References Chapter 12 A Note on Uniform Power Connectivity in the SINR Model Introduction Related Work Model Connectivity in Grids One-Dimensional Grid Two-Dimensional Grid Connectivity for Random Instances: The One-Dimensional Case Conclusions and Open Problems References Chapter 13 Locating a Black Hole without the Knowledge of Incoming Link Introduction Black Hole Search Aim of This Work Related Work Definitions Distributed System The Problem Lower Bound on the Size of the Optimal Solution Size-Optimal Algorithm Algorithm Correctness Upper Bound on the Size of the Optimal Solution Conclusion References Chapter 14 Energy Efficient Alert in Single-Hop Networks of ExtremelyWeak Devices Introduction Model Description Algorithm Description The Alert Algorithm Extensions Analysis of the Algorithm Time and Energy Complexity Success Probability Lower Bound References Chapter 15 Brief Announcement: Universal DataAggregation Trees for Sensor Networks in Low Doubling Metrics Summary References Chapter 16 Brief Announcement on MOGRIBA: Multi-Objective Geographical Routing for Biomedical Applications of WSN Solution Overview Reference Chapter 17 Routing on Delay Tolerant Sensor Networks Introduction Related Work Outline of the Paper Experimental Results for the k-Greedy Strategy Routing on the Grid Analysis of the Algorithm Lower Bound Conclusion References Chapter 18 Better Face Routing Protocols Introduction Model Related Work A New Version of Face Routing Virtual Face Routing Routing in Quasi Unit Disk Graphs Routing in Edge Dynamic Quasi Unit Disk Graphs Conclusions and Future Work References Chapter 19 Building a Communication Bridge with Mobile Hubs Introduction Related Work Building a Bridge with the Minimum Number of Hubs MaxDist: Minimizing Maximum Distance SumDist: Minimizing the Total Distance Bounds on Number of Hubs Conclusion References Chapter 20 Compressing Kinetic Data from Sensor Networks Introduction Data Framework Compression Results Partitioning Lemma Compression Theorem Locality Results References Chapter 21 Relocation Analysis of Stabilizing MAC Algorithms for Large-Scale Mobile Ad Hoc Networks Introduction Preliminaries Bounded Rate and Unbounded Rate of Relocations The Non-oblivious Strategy for Bounded Rate of Relocations Analyzing the Non-oblivious Strategy Conclusions References Chapter 22 Deterministic Collision Free Communication Despite Continuous Motion Introduction Related Work Definitions Problem Definition Algorithm Overview Analysis Collision Avoidance Maintenance of Neighborhood Knowledge Schedules An Example of the Network Tiling Conclusions References Chapter 23 Self-stabilizing Deterministic Gathering Introduction Preliminaries Distributed Model Specification Gathering with Strong Multiplicity Detection Deterministic Self-stabilizing Algorithm for an Odd Number of Robots Conclusion References Chapter 24 Gossiping in Jail Introduction Related Work Model Singleton Algorithms Collision-Free Algorithms Unrestricted Algorithms Conclusion References Chapter 25 Complexity and Approximation of a Geometric Local Robot Assignment Problem Introduction The Complexity of Robot Assignment The Heterogeneous Scenario The Homogeneous Scenario A Local Approximation Algorithm with Resource Augmentation Open Questions and Final Comment References Back matter
Donate to keep this site alive
To access the Link, solve the captcha.
1. Disable the AdBlock plugin. Otherwise, you may not get any links.
2. Solve the CAPTCHA.
3. Click download link.
4. Lead to download server to download.