Fundamentals of Sensor Network Programming E-Book

S. Sitharama Iyengar

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley - IEEE
• Sprache: Englisch

Seitenzahl: 406

Veröffentlichungsjahr: 2011

Beschreibung

This book provides the basics needed to develop sensor network software and supplements it with many case studies covering network applications. It also examines how to develop onboard applications on individual sensors, how to interconnect these sensors, and how to form networks of sensors, although the major aim of this book is to provide foundational principles of developing sensor networking software and critically examine sensor network applications.

Leseprobe

Contents

Cover

Half Title page

Title page

Copyright page

Dedication

Preface

Foreword

Acknowledgments

About the Authors

Notations and Abbreviations

PART I: Overview

Chapter 1: Introduction

1.1 SOME FOUNDATIONAL INFORMATION

1.2 NEXT-GENERATION SENSOR NETWORKED TINY DEVICES

1.3 SENSOR NETWORK SOFTWARE

1.4 PERFORMANCE-DRIVEN NETWORK SOFTWARE PROGRAMMING

1.5 UNIQUE CHARACTERISTICS OF PROGRAMMING ENVIRONMENTS FOR SENSOR NETWORKS

1.6 GOALS OF THE BOOK

1.7 WHY TinyOS AND NesC

1.8 ORGANIZATION OF THE BOOK

1.9 FUTURE DEMANDS ON SENSOR-BASED SOFTWARE

PROBLEMS

REFERENCES

Chapter 2: Wireless Sensor Networks

2.1 SENSOR NETWORK APPLICATIONS

2.2 CHARACTERISTICS OF SENSOR NETWORKS

2.3 NATURE OF DATA IN SENSOR NETWORKS

PROBLEMS

REFERENCES

Chapter 3: Sensor Technology

3.1 SENSOR LEVEL

3.2 SERVER LEVEL

3.3 CLIENT LEVEL

3.4 PROGRAMMING TOOLS

PROBLEMS

REFERENCES

PART II: Background

Chapter 4: Data Structures for Sensor Computing

4.1 INTRODUCTION TO SENSOR COMPUTING

4.2 COMMUNICATION CAPABILITIES

4.3 GENERAL STRUCTURE OF PROGRAMMING

4.4 DETAILS ON EMBEDDED DATA STRUCTURES

4.5 LINKED LIST

4.6 IMPORTANCE OF GRAPH CONCEPTS IN SENSOR PROGRAMMING

4.7. GRAPH AND TREES

4.8 TREES

4.9 GRAPH TRAVERSAL

4.10 CONNECTIVITY

4.11 PLANAR GRAPHS

4.12 COLORING AND INDEPENDENCE

4.13 CLIQUE COVERING

4.14 INTERSECTION GRAPH

4.15 DEFINING DATA STRUCTURE OF SPANNING TREE PROTOCOLS

PROBLEMS

REFERENCES

Chapter 5: Tiny Operating System (TinyOS)

5.1 COMPONENTS OF TinyOS

5.2 AN INTRODUCTION TO NesC

5.3 EVENT-DRIVEN PROGRAMMING

PROBLEMS

REFERENCES

Chapter 6: Programming in NesC

6.1 NesC PROGRAMMING

6.2 A SIMPLE PROGRAM

PROBLEMS

REFERENCE

PART III: Sensor Network Implementation

Chapter 7: Sensor Programming

7.1. PROGRAMMING CHALLENGES IN WIRELESS SENSOR NETWORKS

7.2. SENSING THE WORLD

7.3. APPLICATIONS USING THE INTERFACE SPLITCONTROL

PROBLEMS

REFERENCES

Chapter 8: Algorithms for Wireless Sensor Networks

8.1 STRUCTURAL CHARACTERISTICS OF SENSOR NODES

8.2 DISTINCTIVE PROPERTIES OF WIRELESS SENSOR NETWORKS

8.3 SENSOR NETWORK STACK

8.4 SYNCHRONIZATION IN WIRELESS SENSOR NETWORKS

8.5 COLLISION AVOIDANCE: TOKEN-BASED APPROACH

8.6 CARRIER SENSING VERSUS DECODING

PROBLEMS

REFERENCES

Chapter 9: Techniques for Protocol Programming

9.1 THE MEDIATION DEVICE PROTOCOL

9.2 CONTENTION-BASED PROTOCOLS

9.3 PROGRAMMING WITH LINK-LAYER PROTOCOLS

9.4 AUTOMATIC REPEAT REQUEST (ARQ) PROTOCOL

9.5 TRANSMITTER ROLE

9.6 ALTERNATING-BIT-BASED ARQ PROTOCOLS

9.7 SELECTIVE REPEAT/SELECTIVE REJECT

9.8 NAMING AND ADDRESSING

9.9 DISTRIBUTED ASSIGNMENT OF NETWORKWIDE ADDRESSES

9.10 IMPROVED ALGORITHMS

9.11 CONTENT-BASED ADDRESSING

9.12 FLOODING

9.13 RUMOR ROUTING

9.14 TRACKING

9.15 QUERYING IN RUMOR ROUTING

PROBLEMS

REFERENCES

PART IV: Real-World Scenarios

Chapter 10: Sensor Deployment Abstraction

10.1 SENSOR NETWORK ABSTRACTION

10.2 DATA AGGREGATION

10.3 COLLABORATION GROUP ABSTRACTIONS

10.4 PROGRAMMING BEYOND INDIVIDUAL NODES

PROBLEMS

REFERENCES

Chapter 11: Standards for Building Wireless Sensor Network Applications

11.1 802.XX INDUSTRY FREQUENCY AND DATA RATES

11.2 ZigBee DEVICES AND COMPONENTS

11.3 ZigBee APPLICATION DEVELOPMENT

11.4 DISSEMINATION AND EVALUATION

PROBLEMS

REFERENCES

Chapter 12: INSPIRE: Innovation in Sensor Programming Implementation for Real-time Environment

12.1 MOTIVATION AND BACKGROUND

12.2 SOFTWARE MICROFRAMEWORK REQUIREMENTS

REFERENCES

Chapter 13: Performance Analysis of Power-Aware Algorithms

13.1 INTRODUCTION

13.2 SERVICE ARCHITECTURE

13.3 APPROACHES TO WSN PROGRAMMABILITY

13.4 SIMULATION CAPABILITIES

13.5 BENCHMARKING

13.6 CONCLUSION

PROBLEMS

REFERENCES

Chapter 14: Modeling Sensor Networks Through Design and Simulation

14.1 INTRODUCTION

14.2 WHY A NEW SIMULATOR

14.3 CURRENTLY AVAILABLE SIMULATORS

14.4 SIMULATION DESIGN

14.5 IMPLEMENTATION DETAILS

14.6 EXPERIMENTAL RESULTS

14.7 FINAL COMMENTS

APPENDIX

ACKNOWLEDGMENTS

PROBLEMS

REFERENCES

Chapter 15: MATLAB Simulation of Airport Baggage-Handling System

15.1 INTRODUCTION

15.2 BACKGROUND

15.3 PROPOSED ARCHITECTURE

15.4 SIMULATION RESULTS AND DISCUSSION

15.5 SOURCE CODE

PROBLEMS

REFERENCES

Chapter 16: Security in Sensor Networks

16.1 INTRODUCTION

16.2 SECURITY CONSTRAINTS

16.3 DENIAL-OF-SERVICE ATTACKS IN MULTIPLE LAYERS

16.4 SOME WELL-KNOWN ALGORITHMS FOR SECURITY PROBLEMS

16.5 SECURE INFORMATION ROUTING

16.6 SECURITY PROTOCOLS FOR SENSOR NETWORKS

16.7 FINAL COMMENTS

PROBLEMS

REFERENCES

Chapter 17: Closing Comments

Bibliography

Index

FUNDAMENTALS OF SENSOR NETWORK PROGRAMMING

Copyright © 2011 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data is available.

ISBN 978-0470-87614-5

This book is dedicated to Professor Donald E. Knuth (Professor Emeritus at Stanford University) for his fundamental contributions to the programming in Computer Science.

Professors Daniel Siewiorek (Carnegie Mellon), John Hopcroft (Cornell University), Juris Hartmanis (Cornell University), Thomas Kailath (Stanford University), and K. Mani Chandy (Cal-Tech) have all inspired the authors for coming up with the first book on sensor programming.

Also, Dr. S.S. Iyengar would also like to dedicate this book to all his former and current Ph.D. students, his son Vijeth Iyengar and finally, grandson, Ranvir Iyengar. Professor Phoha would like to dedicate this book to Shiela, Rekha, Krishan, and Vivek.

—S.S. IyengarN. ParameshwaranVir PhohaN. BalakrishananChucka Okaye

Preface

The price of greatness is responsibility.

—Winston Churchill

Sensor processing is a central and an important problem in aerospace/defense, automation, medical imaging, and robotics, to name only a few areas. A surveillance system used in aerospace and defense is an example of a sensor processing system. It uses devices such as infrared sensors, microwave radars, and laser radars that are capable of detecting and tracking flying objects in their observational space. A sensor processing system may employ intelligent and disparate sensors that are distributed logically, spatially, and even geographically. It is then referred to as a distributed sensor network (DSN). The sensor may measure scalar values (e.g., temperature) or vector values (e.g., position in three-dimensional space). The measurements are generally a function of time and/or space. Because of variation in operating environments or other factors, such as aging and communication delays, the measurements may appear contradictory. Although combining the numerous sensor measurements may appear contradictory, it minimizes the uncertainty of measurements and improves reliability and fault tolerance.

There is a wide body of literature on sensor networks and on design, analysis, protocols, and other research-related issues in sensor networks. However, the issues of software development, in particular pedagogical material related to software development in sensor networks, has been left mostly untouched. We present this book to focus on software development in sensor networks. This book provides the basics needed to develop sensor network software and supplements it with many case studies covering network applications. We also examine how to develop onboard applications on individual sensors, how to interconnect these sensors, and how to form networks of sensors, although the major aim of this book is to provide foundational principles of developing sensor networking software and to critically examine sensor network applications.

Courses in sensor networks do not provide direct access to sensor networking equipment and software. However, the need for hands-on experience is essential for a high-quality education. We have structured the examples in the book, in such a way that a teacher can demonstrate the material on a small network of four (or more) sensor nodes and a laptop, all of which can be hand-carried to any room and set up on a teacher's desk. It is our hope to impart to students and by extension any reader of this book an understanding of sensor network programming based on general principles with an aim to develop actual software. Thus, in Part II we provide implementations of various algorithms ranging from very simple to more elaborate in complexity.

Features

This is a practical book. The book contains many figures, pseudocode, and actual code tested in a laboratory environment to explain the concepts. Most of the code is written and tested by N. Paramesh and our student Chuka Okoye, and some examples have been adopted and modified from nesC and TinyOS manuals. The programs were tested on various network configurations consisting of six TelosB sensor motes and a laptop. Currently, there exist several platforms designed to run programs written for TinyOS such as Mica, Telos, and Intel X-scale family of motes. Each of these motes has a unique functionality that differentiates it from others. While several of the programs that have been written to illustrate concepts in this book are platform-independent, most have been tested primarily on TelosB, a Telos family suite of sensors. TelosB motes are IEEE 802.15.4–compliant devices having an integrated onboard antenna and a range of sensing devices (light, temperature, and humidity sensors). They are characterized by their USB (universal serial bus) programmability; hence programs can be written on a computer and transferred to the device for testing. TelosB sensors have an already implemented 802.15.4 physical layer and a software MAC (media access control) layer that ensures that sensors can communicate with each other using the onboard antennas and existing radio drivers. Programs written in the TinyOS environment can be checked for program correctness either by running them in the TinyOS simulator (TOSSIM) or by using the integrated LEDs (light-emitting diodes) on the sensors for debugging. TOSSIM allows detailed simulation of TinyOS network stacks at the bit level, therefore allowing both low- and high-level applications that require fine-grained controls to be simulated. TinyViz, a graphical user interface (GUI) for TOSSIM, can be used to visualize and interact with running TOSSIM simulations. The TOSSIM simulator can mimic thousands of nodes and also has the ability to print debug information such as variables.

We make no pretense of providing in this book a reference manual for nesC or of TinyOS, and students writing more than trivial programs will do well to avail themselves of specific reference sources on nesC and TinyOS.

Audience

The book is suitable for upper-division (junior or senior) undergraduate-level or first-year graduate-level students. We have presented the material in this book assuming that the reader is knwoledegeable in some conventional programming language and has basic familiarity with an operating system. Although the programming language used in examples is nesC running under the TinyOS operating system, in some cases, particularly in Part III of the book, further knowledge of sensors and networks will be helpful. We have tried to arrange the material in an order that will facilitate following the chapters linearly. However, readers who are confident in the programming, data structures, have a basic understanding of sensors, and want to focus more on software development may skip to Chapter 7, Sensor Programming. In conjunction with the material in the book, readers are encouraged to work on moderate-sized projects taken from the book.

S. S. IYENGARLouisiana State University, Baton Rouge (USA)

N. PARAMESHWARANUniversity of New South Wales (Sydney, Australia)

V. V. PHOHALouisiana Tech University, Ruston (USA)

N. BALAKRISHNANIndian Institute of Science, Bangalore (India)

C. D. OKOYELouisiana Tech University, Ruston (USA)

January 28, 2010

Foreword

Dr. Iyengar et al. have written an excellent piece of senior undergraduate or first year graduate level text for sensor or sensor network programming. The book contains numerous practical examples of real or pseudocode and will be extremely beneficial for both students and teachers. It will also be useful for working engineers writing code for sensor based complex or simple systems. Lately the use of sensors to measure space or temperature has grown exponentially from freeways to airports to medical devices to smartphones. Dr. Iyengar et al.'s book will have a positive impact to the industry in general.

Arup GuptaDirector Wireless Platform TechnologiesUltra Mobile GroupIntel Corp

Acknowledgments

This book started out with a series of discussions in 2008, and evolved from various research projects on sensor networks. It was contributed to and improved on by many individuals, and was funded by several federal agencies. The culmination of this work done by the LSU sensor network research group and others is recorded here. Sensor programming is very different from traditional programming. The authors have made an attempt to present the programming structure and implementation aspects of sensors under the framework of the nesC language.

Many researchers, friends, students, and faculty contributed to this work. We would like to acknowledge their contributions. This work has been supported in part by the DoD DEPSCoR grant by the Office of Naval Research and by a PKSFI grant, LEQSF (2007-12)-ENH-PKSFI-PRS-03, from the Louisiana Board of Regents. The authors would also like to thank the Indian Institute of Science for their travel support to the 100th Centenary Conference. Countless people have provided assistance; we have benefited from discussions with many of our colleagues around the country while working on this project. We are grateful to them all and sorry that we cannot list all by name, but a few need to be mentioned. We would like to thank V. Iyer for his several vital contributions to this work, including working with LaTex and general proofreading.We would like to thank Professor Ramamurthy and Professor M. B. Srinivas of the International Institute of Information Technology, Hyderabad, India for being co-authors of many previous publications that helped us put together this book for FARM (fusionable ambient renewable access control) applications.

We would like to thank the graduate students involved in proofreading/editing, including Robert, Rajesh, Srivathsan Srinivasagopalan, and many others. The authors would like to hear from any readers with comments, suggestions, or bug reports. In writing a book of this proportion, it goes without saying that many people have contributed both directly and indirectly to the inception, development, and completion of this project.

This endeavour would not have been achieved if not for the many hours toiled by both my present and former students. For this, thanks goes to Professors N.S.V. Rao (Oak-Ridge National Lab), Richard Brooks (Clemson), Mengxia Zhu (SIU-Carbondale), and Qishi Wu (U. Memphis) and current PhD students Robert Dibiano, Srivathsan Srinivasagopalan, Vasanth Iyer, J. Kim. Further, I want to thank the faculty at KAIST – S. Korea, specifically Dr. Song and his collaborators who participated in the early discussions of this project.

I want to thank all of my research collaborators, specifically, Krishnendu Chakrabarty (Duke), Sartaj Sahni (Florida), Bhaskar Krishnamachari (Southern Cal), and at Louisiana State University (Professors S. Mukhopadhyay, R. Kannan, C. Busch, J. Zhang, H. Wu, X. Li). Moreover, We, (Iyengar and Phoha) would like to thank various funding agencies, specifically DARPA, ONR, NSF, Army Research Office, Air Force (AFRL) and the Indian Institute of Science – Bangalore. Dr. Parameshwaran acknowledges the support and assistance needed from University of New South Wales, Sydney, Australia during his sabbatical at LSU. The authors also acknowledge Prof. Balakrishnan's research group at Indian Institure of Science, Bangalore, during the preparation of this manuscript. Prof. Phoha acknowledges the support of LaTech researchers and many of his graduate students: Kiran Balagani, Chuka Okoye, Sunil Babu, and colleagues Enam Karim and Rastko Selmic from Louisiana Tech University.

We would also like to thank Prof. Holger Karl and Dr. Adreas Willig, the authors of the book Protocols and Architectures for Wireless Sensor Networks (John Wiley & Sons, 2005) which was instrumental in providing the intial impetus for writing a book at a level with more programming details using nesC upon TinyOS.

Perhaps, most importantly, I would like to thank Dean Kevin Carman, for his continued support and mentorship in my research activities at Louisiana State University.

About the Authors

Each of the five authors has teaching and research interests in sensor networks. A brief biographies of these five authors follow.

Dr. S. S. Iyengar

S. S. Iyengar is currently the Roy Paul Daniels Professor and Chairman of the Computer Science Department at Louisiana State University. He heads the Wireless Sensor Networks Laboratory and the Robotics Research Laboratory at LSU. He has been involved with research in high-performance algorithms, data structures, sensor fusion, data mining, and intelligent systems. Since receiving his Ph.D. degree in 1974 from Mississippi State University (MSU), USA. He has directed over 40 Ph.D. students and 100 master's students, many of whom are faculty at major universities worldwide or scientists or engineers at national laboratories or industries around the world. He has published more than 380 research papers and has authored or coauthored six books and edited seven books, published by John Wiley&Sons, CRC Press, Prentice-Hall, Springer Verlag, and IEEE Computer Society Press, and other publishers. One of his books, titled Introduction to Parallel Algorithms, has been translated into Chinese. His research has been funded by the National Science Foundation (NSF), Defense Advanced Research Projects Agency (DARPA), Multi-University Research Initiative (MURI Program), Office of Naval Research (ONR), Department of Energy/Oak Ridge National Laboratory (DOE/ORNL), Naval Research Laboratory (NRL), National Aeronautics and Space Administration (NASA), US Army Research Office (URO), and various state agencies and companies. He has served on the US National Science Foundation and National Institute of Health panels to review proposals in various aspects of computational science and has been involved as an the external evaluator (ABET-accreditation) for several computer science and engineering departments. He is a fellow of (1) the Institute of Electrical and Electronics Engineers (IEEE), (2) Association for Computing Machinary (ACM), (3) American Association for the Advancement of Science (AAAS), and (4) Society of Design and Process Science (SDPS) and a member of the European Academy of Sciences. He has won many best-paper awards and IEEE Computer Society awards.

Dr. N. Parameshwaran

Nandan Parameshwaran is a senior lecturer in the School of Computer Science and Engineering, University of New South Wales, Sydney, Australia. He obtained his Ph.D. from the Indian Institute of Science, Bangalore, India. His research interests include multiagent system models, ontology-driven techniques for concept mappings, robust rule-based systems, and network management. He has been applying agent-based techniques for real-world applications, including social systems such as road traffic simulations, and fireworld scenarios. He teaches courses in Internet programming, functional programming, data structures and algorithms, and artificial intelligence. Dr. Parameshwaran has served as a member in the Florida Artificial Intelligence Research Society (FLAIRS) and the International Conference on Semantic Computing (ICSC) programming committees, and is a former member of both the IEEE Computer Society and the American Association for Artificial Intelligence (AAAI).

Dr. Vir V. Phoha

Vir V. Phoha is a professor of computer science in the College of Engineering and Science at Louisiana Tech University (USA). He holds the W. W. Chew Endowed Professorship at Louisiana Tech and directs the Center for Secure Cyberspace. He has won various distinctions, including ACM Distinguished Scientist, 2008; research commemoration awards at Louisiana Tech University (2002, 2006, 2007, 2008); outstanding research faculty and faculty Circle of Excellence Award at Northeastern State University, Oklahoma, and as a student was awarded the President's Gold medal for Academic Distinction. Professor Phoha holds an M.S. and a Ph.D. in Computer Science from Texas Tech University.

He has done fundamental and applied work in anomaly detection in network systems, in particular in the detection of rare events. His current research interests include autonomy and security issues in sensor networks. He has eight patent applications and many reports of inventions. He is author of over 90 publications and author/editor of three books: Internet Security Dictionary, Springer-Verlag (2002); Foundations of Wavelet Networks and Applications, CRC Press/Chapman Hall (2002); Quantitative Measure for Discrete Event Supervisory Control, Springer (2005).

Dr. N. Balakrishnan

N. Balakrishnan is a scientist of high international repute and is well decorated with prestigious awards. He received his B.E. (Hons.) in Electronics and Communication from the University of Madras in 1972 and Ph.D. from the Indian Institute of Science in 1979. He then joined the Department of Aerospace Engineering as an assistant professor. He is currently the associate director of the Indian Institute of Science and a Professor at the Department of Aerospace Engineering and at the Supercomputer Education and Research Centre. He played a crucial role in building India's first Supercomputer Centre and the National Centre for Science Information at the Indian Institute of Science.

His areas of research, in which he has published over 200 papers in international journals and for presentation at international conferences, include numerical electromagnetics, high-performance computing and networks, polarimetric radars and aerospace electronic systems, information security, digital libraries, and speech processing. He has received many awards, including the Padmashree, Homi J. Bhabha Award, the JC Bose National Fellowship, the Alumni Award for Excellence in Research for Science & Engineering at the Institute, the Millennium Medal of the Indian National Science Congress in 2000, Ph.D. (Honoris Causa) from Punjab Technical University in 2003, and the CDAC-ACS Foundation Lecture Award. He was the NRC Senior Resident Research Associate at the National Severe Storms Laboratory, Norman, Oklahoma (USA) from 1987 to 1989. He was a visiting research scientist at the University of Oklahoma in 1990, Colorado State University in 1991 and has been a visiting professor at Carnegie Mellon University since 2000. He is an honorary professor in the Jawaharlal Nehru Centre for Advanced Scientific Research (JNCASR).

He is a fellow of the Academy of Sciences for the Developing World (TWAS), Indian National Science Academy (currently the vice president), Indian Academy of Sciences, Indian National Academy of Engineering, National Academy of Sciences, and Institution of Electronics & Telecommunication Engineers. He is currently a member of the National Security Advisory Board, part-time member of the Telecom Regulatory Authority of India, and member of the Board of Governors of IIT Chennai. He is a directors of (1) Bharat Electronics Limited (BEL), (2) Data Security Council of India, and (3) CDOT-Alcatel Research Centre at Chennai; he is a member of the Council of CDAC and the council of many universities and CSIR laboratories. He is Editor of the International Journal on Distributed Sensor Networks. He was a member of the Scientific Advisory Committee to the Cabinet (SAC-C), a member of the Board of Governors, IIT Delhi; Chairman, All India Board of Information Technology Education of AICTE; and Editor of Electromagnetics and International Journal of Computational Science and Engineering until recently.

Chuka D. Okoye

Chuka D. Okoye is an undergraduate student majoring in computer science in his senior year at Louisiana Tech University. He has been named to the President's and Dean's lists multiple times for academic distinction and most recently nominated as the most outstanding computer science senior. During his 4 years at Louisiana Tech, he held various leadership positions, including the most coveted vice president of the local ACM chapter, president of the Robotics Club, and Louisiana Tech Programming Team Czar. His research interests include high-performance computing (HPC), machine learning, and wireless sensor networks. Having done exemplary work in the design and implementation of high-availability tools for clusters, he was charged with the development of a high-availability solution for the renowned Louisiana Optical Network Initiative (LONI). After being accepted in the Google Summer of Code Program under the mentorship of researchers from Oak Ridge National Laboratory, he greatly enhanced the widely popular OSCAR software stack for HPC clusters. Currently, he works as an undergraduate student researcher for the Center for Secure Cyberspace under the supervision and mentorship of the well-accomplished Dr. Vir V. Phoha in the Sensors and Machine Learning Group.

Notations and Abbreviations

Clarity of presentation is critical to effectively communicate knowledge.

—S. S. Iyengar

ACRONYMS*

AGacquaintance groupAPIapplication program interfaceARQautomatic repeat requestATRatomic target recognitionBCblock-cut (e.g., block-cut tree)BFS/DFSbreadth-first/depth-first searchBHSbaggage-handling systemCANcontroller area networkCBSchecked-baggage screeningCHAMPcaching and multipath (routing)DIFSdistributed interframe spaceDSNdistributed sensor networkDVSdynamic voltage scalingEEPROMelectrically erasable read-only memoryESMelectronic support measureFARMfusionable ambient renewable MACFDMA/TDMAfrequency-/time-division multiple accessFFDfull-function deviceFIFOfirst-in/first-outFSMfinite-state machineGEARgeographic and energy-aware routingGHTgeographic hashing tableGPSRgreedy perimeter stateless routingGSNGlobal Sensor NetworkGUIgraphical user interfaceHALhardware abstraction layerHBAhub-based architectureHNGhop neighborhood groupHPChigh-performance computingHSRhierarchical state routingIFFIR (infrared) identification–friend/foe (sensor)INSPIREinnovation in sensor programming implementation for real-time environmentIPCinterprocess (or intermediate-performance) communicationISRintelligence–surveillance–reconnaissanceLEACHlow-energy adaptive clustering hierarchyLPLlow-power listeningMACmedia access layerMASmultiagent systemMCUmultipoint control unitMEMSmicroelectromechanical systemMOPmaximal outer planar (graph)OMNeTobjective modular network testbedPLCproduct lifecycle or public limited companyPSGpublish/subscribe groupQoSquality of serviceRAM/ROMrandom-access memory/read-only memoryRFDreduced-function deviceRFIDradiofrequency identification (tag; as in, e.g., airport security)RSArandom structures and algorithmsRSSreallly simple syndicationRTCrun to completionRTOSreal-time OS (operating system)RTSready (or request) to sendSCPscheduled channel pollingSHIMMERsensing health with intelligence, modularity, mobility, and experimental reusabilitySIFSshort interframe spaceSMSsecurity management systemSPEEDsystems planning, engineering, and evaluation deviceTCP/IPTransmission Control Protocol/Internet ProtocolTOSSIMTinyOS simulatorUMLUnified Modeling LanguageUSBUniversal Serial BusUTCUniversal Time, CoordinatedWASNwireless ad hoc sensor networkWSNwireless sensor network

* Proprietary organization abbreviations (IEEE, etc.) and very common acronyms (e.g., CPU, GPS, IR, PC, UV) omitted from this list.

PART I

Overview

Chapter 1

Introduction

The creation of genuinely new software has far more in common with developing a new theory of physics than it does with producing cars or watches on an assembly line.

—T. Bollinger

Software that drives the operations of sensors and communication among sensors is basic to any meaningful application of sensor networks. The goal of this book is to provide an understanding of how this software functions; how it allows the sensors to gather information, process it, and interact with each other in networks; and how these networks interact with the physical world. One aim of this book is to provide fundamental information necessary to write efficient sensor network software. A second aim is to provide a balance between theory and applications, so that the subject matter is complete (self-contained).

Wireless sensor network (WSN) applications may consist of diverse sensors with varying capabilities. For example, sensors may range from an extremely constrained 8-bit “mote” to less resource-constrained 32-bit “microservers.” These sensors may be organized in different network configurations, which use different communication and data dissemination protocols, most software development platforms consist of libraries that implement message-passing interprocess communication (IPC) primitives, tools to support simulation, emulation, and visualization of networked systems, and services that support networking, sensing, and time synchronization. Given all of this diversity, there is an underlying theme of software development and deployment that cuts across platforms.

1.1 SOME FOUNDATIONAL INFORMATION

This section provides some basic information necessary for understanding the sensors and sensor networks.

1.1.1 Sensors

Typically a sensor is composed of components that sense the environment, process the data, and communicate with other sensors/computers. A sensor responds to a physical stimulus, such as heat, light, sound, or pressure, and produces a measurable electrical signal. Thus a sensor with its own sensing device, a memory, and a processor can typically be programmed with a high-level programming language, such as CorJava. The sensing devices can range from nanosensors to micro- and megasensors. In the remainder of this book when we refer to a sensor, we refer to a whole system such as a mote, which may have more than one physical sensor, its memory, processor, and other associated circuitry. Figure 1.1 shows a distributed sensor architecture and various components.

FIGURE 1.1 Networking structure of a distributed sensor network.

1.1.2 Sensor Networks

A distributed sensor network (DSN) is a collection of sensors distributed logically or geographically over an environment in order to collect data. Distributed computing and distributed problem solving are commonly used in DSN in order to abstract relevant information from the data gathered and derive appropriate inferences. This kind of data fusion can be used to compensate for the shortcomings of the individual sensor in real-world enviornments. For more details on sensor networks, see Refs. 1–3.

Most references to the term sensor network can denote multiple sensing configurations to be used in multiple contexts. Sensor networks typically consist of numerous sensing devices that may communicate over wired or wireless media, and may have as intrinsic properties limitations in computational capability, communication, or energy reserve. This does not imply that all sensor deployments consist of severely resource-constrained devices; for example, radar, closed-circuit cameras, and other wireline devices are commonly used in sensor network experimentations in academia and military research. These sensing devices possess reasonable computational capability and more importantly, may not have limited energy or constrained communication abilities. The main crux of this book is focused on the class of sensors having severely constrained computation, communication, and energy resources. These devices range from penny to matchbox in size and are deployed in an ad hoc and nonplanned (random) fashion. Examples of such devices include the mote platforms commonly used in academia.

1.2 NEXT-GENERATION SENSOR NETWORKED TINY DEVICES

1.2.1 Domain-Specific Challenges

Development of software in wireless sensor networks draws on experiences across several domains in computer science and some engineering disciplines such as

1.Networking. Networking knowledge is critical in sensor networks, providing information on how large-scale mobile ad hoc wireless networks can be created and managed efficiently.

2.Power Systems. Sensor networks, also rely on information from computer science and electrical and nanosystems engineering, in the creation of energy efficient software and hardware components, resulting in improved life of sensor networks.

3.Data Management. Experience in large-scale data management and data mining techniques is required in sensor networks since huge heterogenous datastreams are generated from these ubiquitous sensing devices.

4.Data Fusion. Since most devices have basic sensing capabilities, the need to create software systems capable of combining data from multiple sources to create more complex representation of the world is necessary; hence the need for data fusion. Fusion systems draw on advances in artificial intelligence, statistical analysis, and distributed systems.

1.2.2 Technology-Driven Methods

A few examples of technology driven methods in sensor networks follow.

1.Flooding, such as broadcast of packets in a synchronized network from source to destination until the path is formed to find the topology

2.Clustering, including K-means clustering to find K centers and form a cluster to minimize the distance between nodes in a dense region and efficiently form a topology

3.Short-path algorithms for data aggregation, such as data aggregation trees to form wireless spanners to efficiently collect data periodically

4.Distributed algorithms for energy and reusability loading and fault tolerance in large sensor networks

1.2.3 Wireless Sensor Network Environment

Sensor Network make it possible to monitor, instruct, or control various domains such as homes, buildings, warzones, cities, and forests. Sensor networks can observe the sensing environment at a close range and thus have many advantages, such as ability to monitor smallest details, proximity to places which are difficult to reach by humans, for example difficult terrain or hazardous environment. The major limitations of sensors are their limited power supply, limited communication bandwidth and range, and limited computation ability and memory capacity. Data transmission consumes a large percentage of energy; reducing the amount of data transmitted is the primary focus of data processing. The small bandwidth of the wireless links represents a challenge for data processing. Because of the limited communication radius of a sensor node, data may have to go through multiple hops to reach the final destination. This leads to extra power consumption in sensor nodes on the relay path. Limited processing and memory capacities restrict the complexity of data processing algorithms running at the sensor nodes. The intermediate results and other data are also burdensome to store in the node because of limited memory size. Sensor data are a stream: a real-time, continuous, ordered sequence with limited control over the order in which items arrive and the limitations of low battery life, low bandwidth, and low processing power and operating memory present programming challenges that are unique to the sensor network environment.

1.3 SENSOR NETWORK SOFTWARE

A network architecture and protocols are essential foundations for building software applications.

Developing computational/communication systems for deployment and application for wireless sensor networks has been a challenge since the mid-1990s. More Specifically, wireless ad hoc sensor networks have been largely designed with static and custom architectures for specific tasks, thus providing inflexible operation and interaction capabilities. WSN applications need to be programmed with constrained memory and process-centric resource requirements in mind, in order to write communication code with real-time sensing deadlines, which are critical to a dedicated scheduled measuring task. In short, the problem is the choice of abstraction for the sensor node runtime environment. Our computational framework or paradigm called INSPIRE, defines and supports nanofootprint and real-time deadlines, scheduled tasks for computing, and allows communication and sensing resources at the sensor nodes to be efficiently harnessed in high density event driven application-sensing fashion, through the use of an object oriented framework. A key feature of the runtime abstraction is that all the infrastructure used by the kernel is simulated to provide wireless communications using renewable energy resources with its unique extended lifetime model. This allows it to scale all the code to any processor. The implementation of INSPIRE on a target prototype node occupies less than 10–40 kB (kilobytes) of code memory; for details, refer to Chapter 10. The distributed source coding implementation is used to measure the sensing activity and memory overheads using traditional sensor applications without constraints, but more importantly, we highlight the reliability of the transmitted data from the measuring applications.

1.3.1 Technology-Driven Software

Individual updates of software are impractical because of the large number of nodes and the relative inaccessibility of deployed nodes. One solution for updating software in sensor nodes is the deployment of a support network of small, mobile, temporarily attachable nodes with virtual connections from a host PC to individual nodes. This scheme allows the use of standard tools to update the software in the individual sensor nodes. For many sensor networks in field applications, such as sensors deployed in unreachable places such as in water or trees, it is desirable to remotely update the software on the sensor nodes.

The following are a few issues to be considered when updating the nodes with software updates:

Updates need to be planned. The items included in planning are tradeoffs of different updates relative to energy costs, the injection strategy for network configuration, and size reduction techniques that result in quick updates.Injection strategies of software. The strategies could include updating individual nodes, or sending updates to a base station or to a number of select nodes that may then disseminate the updates to other nodes.How software would be activated. Software may be either automatically activated or based on a set of rules, or manual activation may be required. To meet the requirements for backward/forward version compatibility, control over the order of node activation may be needed.Checking the downloaded software for integrity, version mismatch, and platform mismatch, and dynamically checking the operation of the downloaded software after it has been activated.Monitoring of update-related faults.Security-related issues, such as key distribution, authentication, secrecy, integrity, and authorization.Problems related to very small nodes, such as limited code memory, and almost no RAM or EEPROM (random-access or electrically erasable programmable read-only memory) for storing new code. Techniques may need to be developed for incremental building of new code into code memory (usually flash-RAM).Version control, that is, prevention version mismatch.Heterogeneity of sensor nodes. There can be various forms of heterogeneity; for example, there may be a mix of platforms, or a network may consist of a small number of “spine”/data backbone (shown to be optimal for data delivery) and a large number of lower-power nodes (for data collection). Here the backbone nodes will have to handle different versions of their code base as well as different codebases.Performance. The time required to update nodes as well as tradeoffs between time and energy need to be considered.Provisions to recover from faulty updates, with mechanisms to verify the new software both before and during execution.

1.4 PERFORMANCE-DRIVEN NETWORK SOFTWARE PROGRAMMING

There are four basic issues here:

1.Quality of Service. In sensor networks quality of service is an important metric to analyze the performance and reliability of different WSN routing algorithms. As the sensor nodes use fixed batteries to sense and communicate, it is necessary to collaboratively use the network resources to minimize power usage and when idling, conserve power by using ultra-low-duty cycling. The communication module of a sensor mote uses a software “stack” and a radio to receive and transmit information. The network stack has many layers, spanning from physical layer to network layer; with various functionalities. By design, a running stack needs to use a small footprint and be power-aware, avoiding unnecessary overheads at every layer. The QoS can be defined as how the stack performs load balancing (reusability index), power-aware sleep scheduling (due to network density), and the reliability of sending sensed data wirelessly (at the datalink layer).

2.Reusability Index. This performance-based index can described as the number of times that a given node has been used as a clusterhead to communicate to a base station or a sink during its lifetime. As many of the clusterhead selection algorithms are distributed in nature, they will not overuse a specific node more than the critical number of times. If all nodes are used evenly, then the reliability of the network increases during the entire lifetime of the node.

3.Sleep Scheduling. Most of the deployed sensor network applications are dense because of the limited radio transmission range, so even when not transmitting, data nodes are subjected to overhearing and collision. These factors severely impact the total power consumed. So, in a dense deployment if a sufficient number of nodes are awake to receive the multihop traffic, then other nodes can shut off their radios after exchanging the next polling time, to minimize idling. By activating only a subset of nodes and scheduling timeslots for nodes to be active, sleep scheduling saves on power and avoids dropped packets. The end goal of each of these methods is to continue reciving data from the network for as long as possible.

4.Datalink Reliability. Data must be not only available but also accurate. In wireless sensor networks a node needs to not only communicate with its neighbors also forward the periodic sensed data over the network. Many of the MAC protocols are designed for efficient ad hoc communications but not for reliable data sensing as the radio does not have a way to filter floor noise or a new sensed value in harsh environments. For this reason, a twoway handshake is necessary between the MAC and the datalink layer, which allows them to reliably capture the new data everytime a data aggregation is performed. With this reliable datalink mechanism the clusterhead can further fuse the data from neighboring sensors and discard any false values.

1.4.1 Routing

In a sensor network stack the network layer is solely responsible for route planning and maintenance. Most of the energy used by the network is due to its routing activity. In implementing routing there are two methods, one at the network layer, which is controlled by distributed algorithms to form clusters and uses efficient clusterhead selection, and another at the MAC layer, which uses multihop routing to forward data at the lower layers by using best-effort QoS.

1.4.2 Data Aggregation

In a large sensor network deployment many parameters are sensed over a wide area and are periodically sent to the central coordinator. As the sensed parameters are the same at every node (similar sensor types are attached), WSN data aggregation allows reduction of the redundancy in a transmission by statistically evaluating the frequency of occurring samples and the trend direction that they have during its lifetime. When sensor nodes sample individually, only the aggregated data are transmitted, thus increasing the local processing and decreasing the radio usage per aggregation cycle. A simple example is using data compression at the nodes to send fewer bits during each transmission.

1.4.3 Security

Security is a constant threat to outdoor wireless environments; thus it is prudent to have an encryption algorithm that allows encryption and decryption of wireless communications. One novel way to implement a security algorithm is to have a oneway function which is NP-complete at the predeployment stage and cannot be decrypted with limited resources in a deployed site of operation. This method is more suitable in other applications of networks; in the case of WSN networks, because of the nature of their distribution one can design a network polynomial key that is not a local function. The broadcast message cannot be decrypted when a few nodes are compromised as it needs to have other parameters that are well distributed and concealed from the intruder.

1.5 UNIQUE CHARACTERISTICS OF PROGRAMMING ENVIRONMENTS FOR SENSOR NETWORKS

Sensor networks differ from both wired and wireless computer networks in many ways. The topology of sensor networks can change rapidly and frequently. The nodes in a sensor network do not have a global identifier such as an IP (Internet Protocol) address, and the number of sensor nodes in a sensor network may be an order of magnitude greater than that in a typical computer network. The memory and the processing capabilities of sensor nodes are limited in comparison to nodes in a computer network. These characteristics lead to a programming environment that is unique. Thus, the programs need to be short and efficient, providing capabilities of interfaces and links of components and modules to each other. Additionally, to save battery power, the nodes may need to have aggressive power management capabilities; thus the programming environment needs to provide mechanisms such as split phase, the nonblocking equivalent of common power-saving techniques such as the sleep command.

1.6 GOALS OF THE BOOK

The goals of this book are to develop programming methodologies unique to sensor networks, and present in an organized fashion techniques for programming of sensors to enable them to work effectively as a group. Thus, although the focus is on programming of the individual sensor, the goal is to enable the sensor to work within a collaborative environment.

1.7 WHY TinyOS AND NesC

TinyOS is an emerging platform that provides a framework for the most common type of sensor application programming. Thus we have a tool that can be implemented on small Crossbow sensors and a wireless sensor network that can be ported to different classrooms and laboratories. NesC provides a C-type, component-based language.

In NesC a module is the lowest level of component abstraction that implements any commands provided in its interface. It may directly address a particular hardware component such as a light sensor, providing methods that abstract the actual operation of that particular hardware component. Several modules may be grouped together using a configuration to form a larger component.

1.8 ORGANIZATION OF THE BOOK

The book is organized as follows. In Part I, we present an overview of the subject of sensor network programming, beginning with a general introduction in the remainder of this chapter (Chapter 1). Chapter 2 gives a general description of the wireless sensors. It explains the basic components of a sensor, its sensing environment, and the various roles that a sensor can play in a wireless sensor network. Chapter 3 discusses current sensor technology, including the major families and types of sensors currently in use, including the Mica, Telos, Tmote Sky families, and others.

Part II provides a general background for sensor network (SN) programming, beginning with discussions on data structures for sensor computing programming in Chapter 4. Sensor computing programming of individual sensors in a SN environment requires an understanding of data structures, such as arrays, queues, stacks, and lists, which are essential to programming. For network implementation, an understanding of graphs is useful to appreciate routing and message passing. Thus, Chapter 4 explains those data structures, which are essential for programming in a wireless sensor network environment. Chapter 5 explains the tiny operating system (TinyOS) environment, and is essential to understanding the subsequent chapters. It presents the structure of application programming interfaces (APIs) built using a nesC like structure, which facilitates the readability of the examples given in the rest of that chapter. For the sake of completeness and continuity, Chapter 5 also includes a bare-minimum description of nesC programming language. In Chapter 6, on nesC programming, the nesC language is formally introduced and some major concepts in the language are discussed.

Part III discusses and presents examples of sensor network implementation. Chapter 7 provides a basic introduction to sensor programming. It discusses some of the challenges encountered when programming large numbers of sensors and some interfaces provided by TinyOS to alleviate these programming challenges. Chapter 8, on algorithms for wireless sensor networks, is the core and the major focus of the book. It gives detailed descriptions of various algorithms and their implementation in nesC. In Chapter 9, on techniques for protocol programming, we discuss several protocols used in most wireless sensor networks and provide accompanying pseudocode to explain the concepts.

Part IV presents real-world scenarios in sensor network programming. In Chapter 10 we discuss some programming abstractions that simplify the development and deployment of sensors. Chapter 11 presents standards for building WSN applications, with a brief overview of the ZigBee networking standard. Chapter 12 discusses an active sensor approach to distributed algorithms, widely known as INSPIRE (innovation in sensor programming implementation for real-time environments). Chapter 13 explores the performance analysis of networks in some detail with respect to power-aware algorithms. Chapter 14 describes sensor network modeling through design and simulation. This chapter presents an architecture of a sensor simulator and a sensor node that is used in the simulator, and further elaborates that OMNeT++ is a viable discrete-event simulation framework for studying both the networking aspects and the distributed computing aspects of sensor networks. We present the architecture of a sensor node that is used in the simulator and the general architecture of the simulator. Chapter 15 presents a MATLAB implementation of simple data processing and decisionmaking logic to be used to detect and respond to events in an airport baggage-handling system. Chapter 16 consists of closing comments.

1.9 FUTURE DEMANDS ON SENSOR-BASED SOFTWARE

In the future, advances in microelectromechanical systems (MEMSs) will lead to miniature sensing devices of about 20 (μm micrometers) to a millimeter in length. These devices will be self-powered, allowing even more collaboration with other devices. In regard to software, more standards specifying how data can be exported between different sensor networks will be established, allowing a more enriched and integrated sensing experience such as

Real-time collaboration between navigation systems and traffic monitoring sensorsCurrent information about seat availability at local restaurants or physicians officesReal-time environmental awareness by a wide range of applications and devices leading to better management of scarce resources, such as smart energy-saving homes.

In this regard, the principles addressed in this book will serve as building blocks for developing large-scale, longlived systems requiring self-organization and adaptivity.

PROBLEMS

1.1 Define the following:

a. Sensor

b. Ad hoc network

c. Distributed sensor network

d. Wireless sensor network

e. Reusability index

1.2 Discuss some of the design challenges that set wireless sensor networks apart from conventional networks.

1.3 Crossbow Technology Inc.’s MTS400 multisensor board is one of the most popular multipurpose heterogeneous sensing devices available on the market. Research and prepare a two-page report discussing the specifications and functionality of the MTS400 multisensor board.

1.4 Write a one-page summary of the article by Akyildiz et al. [4].

1.8 Other than those discussed in this introductory chapter, list three advantages and three disadvantages of sensor networks.

1.6 Crossbow Technology Inc.’s MICAz mote and Europe’s Smart-Its platform are two popular sensor platforms. Research and contrast the features of MICAz with smart-Its (in terms of size, weight, battery life, onboard sensors, memory, CPU, operating system, processing limits, radio range, etc.).

1.7 What are the unique characteristics of programming environments for sensor network software?

1.8