Springer Series on SIGNALS AND COMMUNICATION TECHNOLOGY SIGNALS AND COMMUNICATION TECHNOLOGY Foundations and Applications of Sensor The Variational Bayes Method Management in Signal Processing V. Šmídl and A. Quinn A.O. Hero III, D. Castañón, D. Cochran, and K. ISBN 3-540-28819-8 Kastella (Eds.) ISBN 978-0-387-27892-6 Topics in Acoustic Echo and Noise Control Selected Methods for the Cancellation of Human Factors and Voice Interactive Systems, Acoustical Echoes, the Reduction of Background Noise, and Speech Processing Second Edition E. Hänsler and G. Schmidt (Eds.) D. Gardner-Bonneau and H. Blanchard ISBN 3-540-33212-x ISBN 978-0-387-25482-1 EM Modeling of Antennas and RF Wireless Communications: 2007 CNIT Components for Wireless Communication Systems Thyrrenian Symposium F. Gustrau, D. Manteuffel S. Pupolin ISBN 3-540-28614-4 ISBN 978-0-387-73824-6 Interactive Video Adaptive Nonlinear System Identification: The Methods and Applications R. I Hammoud (Ed.) Volterra and Wiener Model Approaches ISBN 3-540-33214-6 T. Ogunfunmi ISBN 978-0-387-26328-1 ContinuousTime Signals Y. Shmaliy Wireless Network Security ISBN 1-4020-4817-3 Y. Xiao, X. Shen, and D.Z. Du (Eds.) Voice and Speech Quality Perception ISBN 978-0-387-28040-0 Assessment and Evaluation U. Jekosch Satellite Communications and Navigation ISBN 3-540-24095-0 Systems Advanced ManMachine Interaction E. Del Re and M. Ruggieri Fundamentals and Implementation ISBN: 0-387-47522-2 K.-F. Kraiss ISBN 3-540-30618-8 Wireless Ad Hoc and Sensor Networks A Cross-Layer Design Perspective Orthogonal Frequency Division Multiplexing for Wireless Communications R. Jurdak Y. (Geoffrey) Li and G.L. Stüber (Eds.) ISBN 0-387-39022-7 ISBN 0-387-29095-8 Cryptographic Algorithms on Reconfigurable Circuits and Systems Hardware Based on Delta Modulation Linear, Nonlinear and Mixed Mode Processing F. Rodriguez-Henriquez, N.A. Saqib, A. Díaz D.G. Zrilic ISBN 3-540-23751-8 Pérez, and C.K. Koc ISBN 0-387-33956-6 Functional Structures in Networks AMLn—A Language for Model Driven Development of Telecom Systems Multimedia Database Retrieval T. Muth ISBN 3-540-22545-5 A Human-Centered Approach P. Muneesawang and L. Guan RadioWave Propagation ISBN 0-387-25627-X for Telecommunication Applications H. Sizun ISBN 3-540-40758-8 Broadband Fixed Wireless Access A System Perspective Electronic Noise and Interfering Signals M. Engels and F. Petre Principles and Applications ISBN 0-387-33956-6 G. Vasilescu ISBN 3-540-40741-3 Distributed Cooperative Laboratories DVB Networking, Instrumentation, and Measurements The Family of International Standards F. Davoli, S. Palazzo and S. Zappatore (Eds.) for Digital Video Broadcasting, 2nd ed. ISBN 0-387-29811-8 U. Reimers ISBN 3-540-43545-X (continued at the end of book) Edited by Yingshu Li My T. Thai Weili Wu Wireless Sensor Networks and Applications Yingshu Li My T. Thai Georgia State University University of Florida Atlanta, GA Gainesville, FL USA USA Weili Wu University of Texas at Dallas Richardson, TX USA Library of Congress Control Number: 2007934546 ISBN 978-0-387-49591-0 e-ISBN 978-0-387-49592-7 Printed on acid-free paper. © 2008 Springer Science+Business Media, LLC All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now know or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. 9 8 7 6 5 4 3 2 1 springer.com This book is dedicated to our families Contents Dedication ............................................................. V Contributing Authors ..............................................XIII Preface .............................................................. XIX SECTION I Network Design and Network Modelling Chapter 1 A Taxonomy-based Approach to Design of Large-scale Sensor Networks .............................................................. 3 AravindIyer,SunilS.Kulkarni,VivekMhatre andCatherineP.Rosenberg 1. Introduction........................................................... 3 2. Classification of Sensor Network Applications ......................... 7 3. Salient Features of Sensor Networks ....................................8 4. Common Design Problems in Sensor Networks ........................11 5. Class-specific Problems in Sensor Networks ...........................13 6. Sensor Network Implementations .....................................21 7. Conclusions and Future Directions ....................................28 References ..............................................................30 Chapter 2 Algorithms for Robotic Deployment of WSN in Adaptive Sampling Applications ...................................35 Dan O. Popa and Frank L. Lewis 1. Introduction ..........................................................35 2. Problem Formulation .................................................37 3. Communication Models ...............................................39 4. Sampling of Parametrized Fields Based on Closed-Form Information Measures ......................................40 5. Adaptive Sampling Using the Extended Kalman Filter ................50 6. Potential Fields .......................................................53 7. Conclusions and Future Work .........................................59 References ..............................................................61 VII VIII Contents Chapter 3 A Scalable Graph Model and Coordination Algorithms for Mobile Sensor Networks ........................................65 Jindong Tan 1. Introduction ..........................................................65 2. Distributed Graph Model .............................................67 3. Self-deployment Algorithm ............................................70 4. Simulation Results ....................................................75 5. Conclusion ...........................................................81 References ..............................................................81 SECTION II Network Management Chapter 4 MediumAccessControlProtocolsforWirelessSensorNetworks..87 Ali Abu-el Humos, Mihaela Cardei, Bassem Alhalabi and Sam Hsu 1. Introduction ..........................................................87 2. Characteristics of MAC Protocols in WSNs ...........................89 3. Scheduled-based MAC Protocols ......................................92 4. Contention-based Protocols ...........................................93 5. Short Note on the Energy Model in NS2 Network Simulator .........106 6. Conclusion ..........................................................108 References .............................................................109 Chapter 5 Topology Control for Wireless Sensor Networks ................113 Yu Wang 1. Introduction .........................................................113 2. Geometrical Spanners ...............................................116 3. Geometrical Low-Weight Structures .................................128 4. Virtual Backbones ...................................................133 5. Others ..............................................................138 6. Conclusion ..........................................................139 References .............................................................140 Chapter 6 Boundary Detection for Sensor Networks ........................149 Ren-Shiou Liu, Lifeng Sang and Prasun Sinha 1. Introduction .........................................................149 2. Localized Edge Detection ............................................151 3. Centralized edge determination ......................................162 4. Distributed Edge Detection ..........................................165 5. Hierarchical edge estimation .........................................169 6. Conclusion and future work ..........................................172 References .............................................................174 Contents IX Chapter 7 TPSS: A Time-based Positioning Scheme for Sensor Networks with Short Range Beacons .....................175 Fang Liu, Xiuzhen Cheng, Dong Hua and Dechang Chen 1. Introduction .........................................................175 2. An Overview on Current Location Discovery Schemes for Sensor Networks ..............................................................176 3. Network Model ......................................................181 4. TPSS:ATime-BasedPositioningSchemewithShortRangeBeacons...181 5. Performance Evaluation .............................................186 6. Conclusion ..........................................................189 References .............................................................191 Chapter 8 Wakeup Strategies in Wireless Sensor Networks ................195 Curt Schurgers 1. Introduction: The Wakeup Principle..................................195 2. Classification ........................................................200 3. On-demand Paging ..................................................203 4. Synchronous Wakeup ................................................205 5. Asynchronous Wakeup ...............................................209 6. Conclusions .........................................................214 References .............................................................215 Chapter 9 Time-Synchronization Challenges and Techniques ..............219 Weilian Su 1. Introduction .........................................................219 2. Sensor Network Nodes ...............................................220 3. Influencing Factors ..................................................220 4. Design Challenges ...................................................222 5. Time Synchronization Fundamentals .................................223 6. State-of-the-Art Time Synchronization Protocols .....................226 7. Conclusions .........................................................231 References .............................................................232 Chapter 10 Location Service, Information Dissemination and Object Tracking in Wireless Sensor Networks by Using Quorum Methods ......235 Dan-Dan Liu and Xiao-Hua Jia 1. Introduction .........................................................235 2. Location Service .....................................................238 3. Information Dissemination ...........................................243 4. Object Tracking .....................................................249 5. Conclusion ..........................................................254 References .............................................................255 X Contents Chapter 11 Maximizing the Lifetime of an Always-On Wireless Sensor Network Application: A Case Study ...........259 Santosh Kumar, Anish Arora and Ten H. Lai 1. Introduction .........................................................259 2. Fine-grained Power Management Schemes ...........................262 3. The ExScal Application and the XSM Platform ......................266 4. Lifetime Analysis of ExScal ..........................................270 5. Conclusion ..........................................................281 References .............................................................282 SECTION III Data Management Chapter 12 Data Management in Sensor Networks ...........................287 Jinbao Li, Zhipeng Cai and Jianzhong Li 1. Difference between Data Management Systems In Sensor Networks and In Distributed Database Systems ..................................287 2. Architecture of Data Management System in Sensor Networks .......290 3. Data Model and Query Language in Sensor Networks ................292 4. Storage and Index Techniques in Sensor Networks ...................297 5. Query Processing in Sensor Networks ................................310 6. Sensor Network Data Management System ...........................322 References .............................................................329 Chapter 13 Data Aggregation in Wireless Sensor Networks .................331 Kai-Wei Fan, Sha Liu and Prasun Sinha 1. Introduction .........................................................331 2. Directed Diffusion ...................................................332 3. Low-Energy Adaptive Clustering Hierarchy ..........................335 4. Tiny Aggregation ....................................................337 5. Greedy Aggregation on Directed Diffusion ...........................338 6. DCTC ...............................................................341 7. Gateway Placement .................................................344 8. Summary ............................................................346 References .............................................................347 Chapter 14 PerformanceComparisonofClusteringSchemesinSensor Networks .............................................................349 Yadi Ma and Maggie Cheng 1. Introduction .........................................................349 2. Related Work .......................................................350 3. Overview of Algorithms .............................................352 Contents XI 4. Performance Comparison ............................................355 5. Conclusion ..........................................................361 References .............................................................362 Chapter 15 Reliable and Efficient Information Forwarding and Traffic Engineering in Wireless Sensor Networks ................365 Fernand S. Cohen, Joshua Goldberg and Jaudelice C. de Oliveira 1. Introduction .........................................................365 2. Routing in Ad Hoc Networks ........................................366 3. Routing in Sensor Networks .........................................368 4. TE-Routing .........................................................373 5. Conclusions and Research Directions .................................383 References .............................................................383 Chapter 16 Modeling Data Gathering in Wireless Sensor Networks ........387 Bhaskar Krishnamachari 1. Introduction .........................................................387 2. Active Querying with Look-Ahead ...................................389 3. Cluster-Based Joint Routing and Compression .......................391 4. Joint Search and Replication ........................................394 5. Conclusions .........................................................397 References .............................................................399 SECTION IV Security Chapter 17 A Survey on Sensor Network Security ............................403 Xiaojiang Du and Yang Xiao 1. Introduction .........................................................403 2. Attacks on Sensor Networks .........................................405 3. Security Objectives for Sensor Networks .............................411 4. Key Management in Sensor Networks ................................412 5. Secure Routing in Sensor Networks ..................................417 6. Conclusions .........................................................419 References .............................................................419 Chapter 18 A Passive Approach to Unauthorized Sensor Node Identification.........................................................423 Cherita Corbett, John Copeland and Raheem Beyah 1. Introduction .........................................................423 2. Related Work .......................................................425 3. Organization of a Radio Interface ....................................427