PROTOCOLS AND ARCHITECTURES FOR WIRELESS SENSOR NETWORKS ProtocolsandArchitecturesforWirelessSensorNetworks.HolgerKarlandAndreasWillig Copyright2005JohnWiley&Sons,Ltd.ISBN:0-470-09510-5 PROTOCOLS AND ARCHITECTURES FOR WIRELESS SENSOR NETWORKS Holger Karl UniversityofPaderborn,GERMANY Andreas Willig Hasso-Plattner-Institute attheUniversityofPotsdam,GERMANY Copyright2005 JohnWiley&SonsLtd,TheAtrium,SouthernGate,Chichester, WestSussexPO198SQ,England Telephone(+44)1243779777 Email(forordersandcustomerserviceenquiries):[email protected] VisitourHomePageonwww.wiley.com AllRightsReserved.Nopartofthispublicationmaybereproduced,storedinaretrievalsystemor transmittedinanyformorbyanymeans,electronic,mechanical,photocopying, recording,scanningor otherwise,exceptunderthetermsoftheCopyright,DesignsandPatentsAct1988orunderthetermsofa licenceissuedbytheCopyrightLicensingAgencyLtd,90TottenhamCourtRoad,LondonW1T4LP,UK, withoutthepermissioninwritingofthePublisher.RequeststothePublishershouldbeaddressedtothe PermissionsDepartment,JohnWiley&SonsLtd,TheAtrium,SouthernGate,Chichester,WestSussexPO19 8SQ,England,[email protected],orfaxedto(+44)1243770620. Thispublicationisdesignedtoprovideaccurateandauthoritativeinformationinregardtothesubjectmatter covered.ItissoldontheunderstandingthatthePublisherisnotengagedinrenderingprofessionalservices.If professionaladviceorotherexpertassistanceisrequired,theservicesofacompetentprofessionalshouldbe sought. OtherWileyEditorialOffices JohnWiley&SonsInc.,111RiverStreet,Hoboken,NJ07030,USA Jossey-Bass,989MarketStreet,SanFrancisco,CA94103-1741,USA Wiley-VCHVerlagGmbH,Boschstr.12,D-69469Weinheim,Germany JohnWiley&SonsAustraliaLtd,33ParkRoad,Milton,Queensland4064,Australia JohnWiley&Sons(Asia)PteLtd,2ClementiLoop#02-01,JinXingDistripark,Singapore129809 JohnWiley&SonsCanadaLtd,22WorcesterRoad,Etobicoke,Ontario,CanadaM9W1L1 Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappears inprintmaynotbeavailableinelectronicbooks. LibraryofCongressCataloging-in-Publication Data Karl,Holger,1970- Protocolsandarchitecturesforwirelesssensornetworks/HolgerKarl, AndreasWillig. p.cm. Includesbibliographicalreferencesandindex. ISBN-13978-0-470-09510-2 (cloth:alk.paper) ISBN-100-470-09510-5(cloth:alk.paper) 1. Sensornetworks.2. WirelessLANs.I.Willig,Andreas,1968-II. Title. TK7872.D48K372005 681(cid:1).2–dc22 2005005800 BritishLibraryCataloguinginPublicationData AcataloguerecordforthisbookisavailablefromtheBritishLibrary ISBN-13978-0-470-09510-2 (HB) ISBN-100-470-09510-5(HB) Typesetin10/12TimesbyLaserwordsPrivateLimited,Chennai,India PrintedandboundinGreatBritainbyAntonyRoweLtd,Chippenham,Wiltshire Thisbookisprintedonacid-freepaperresponsiblymanufacturedfromsustainableforestry inwhichatleasttwotreesareplantedforeachoneusedforpaperproduction. Contents Preface xiii List of abbreviations xv A guide to the book xxiii 1 Introduction 1 1.1 The vision of Ambient Intelligence 1 1.2 Application examples 3 1.3 Types of applications 6 1.4 Challenges for WSNs 7 1.4.1 Characteristicrequirements 7 1.4.2 Requiredmechanisms 9 1.5 Why are sensornetworks different? 10 1.5.1 Mobileadhocnetworksandwirelesssensornetworks 10 1.5.2 Fieldbusesandwirelesssensornetworks 12 1.6 Enabling technologies for wireless sensornetworks 13 PART I ARCHITECTURES 15 2 Single-node architecture 17 2.1 Hardware components 18 2.1.1 Sensornodehardwareoverview 18 2.1.2 Controller 19 2.1.3 Memory 21 2.1.4 Communicationdevice 21 2.1.5 Sensorsandactuators 31 2.1.6 Powersupplyofsensornodes 32 2.2 Energy consumption of sensor nodes 36 2.2.1 Operationstateswithdifferentpowerconsumption 36 2.2.2 Microcontrollerenergyconsumption 38 2.2.3 Memory 39 2.2.4 Radiotransceivers 40 vi Contents 2.2.5 Relationshipbetweencomputationandcommunication 44 2.2.6 Powerconsumptionofsensorandactuators 44 2.3 Operating systems and execution environments 45 2.3.1 Embeddedoperatingsystems 45 2.3.2 Programmingparadigmsandapplicationprogramminginterfaces 45 2.3.3 Structureofoperatingsystemandprotocolstack 47 2.3.4 Dynamicenergyandpowermanagement 48 2.3.5 CaseStudy:TinyOSandnesC 50 2.3.6 Otherexamples 53 2.4 Some examples of sensornodes 54 2.4.1 The“MicaMote”family 54 2.4.2 EYESnodes 54 2.4.3 BTnodes 54 2.4.4 Scatterweb 54 2.4.5 Commercialsolutions 55 2.5 Conclusion 56 3 Network architecture 59 3.1 Sensor network scenarios 60 3.1.1 Typesofsourcesandsinks 60 3.1.2 Single-hopversusmultihopnetworks 60 3.1.3 Multiplesinksandsources 62 3.1.4 Threetypesofmobility 62 3.2 Optimization goals and figures of merit 63 3.2.1 Qualityofservice 64 3.2.2 Energyefficiency 65 3.2.3 Scalability 66 3.2.4 Robustness 67 3.3 Design principles for WSNs 67 3.3.1 Distributedorganization 67 3.3.2 In-networkprocessing 67 3.3.3 Adaptivefidelityandaccuracy 70 3.3.4 Datacentricity 70 3.3.5 Exploitlocationinformation 73 3.3.6 Exploitactivitypatterns 73 3.3.7 Exploitheterogeneity 73 3.3.8 Component-basedprotocolstacksandcross-layeroptimization 74 3.4 Service interfaces of WSNs 74 3.4.1 Structuringapplication/protocolstackinterfaces 74 3.4.2 ExpressibilityrequirementsforWSNserviceinterfaces 76 3.4.3 Discussion 77 3.5 Gateway concepts 78 3.5.1 Theneedforgateways 78 3.5.2 WSNtoInternetcommunication 79 3.5.3 InternettoWSNcommunication 80 3.5.4 WSNtunneling 81 3.6 Conclusion 81 Contents vii PART II COMMUNICATION PROTOCOLS 83 4 Physical layer 85 4.1 Introduction 85 4.2 Wireless channel and communication fundamentals 86 4.2.1 Frequencyallocation 86 4.2.2 Modulationanddemodulation 88 4.2.3 Wavepropagationeffectsandnoise 90 4.2.4 Channelmodels 96 4.2.5 Spread-spectrumcommunications 98 4.2.6 Packettransmissionandsynchronization 100 4.2.7 Qualityofwirelesschannelsandmeasuresforimprovement 102 4.3 Physical layer and transceiver design considerations in WSNs 103 4.3.1 Energyusageprofile 103 4.3.2 Choiceofmodulationscheme 104 4.3.3 Dynamicmodulationscaling 108 4.3.4 Antennaconsiderations 108 4.4 Further reading 109 5 MAC protocols 111 5.1 Fundamentals of (wireless)MAC protocols 112 5.1.1 RequirementsanddesignconstraintsforwirelessMACprotocols 112 5.1.2 ImportantclassesofMACprotocols 114 5.1.3 MACprotocolsforwirelesssensornetworks 119 5.2 Low duty cycle protocols and wakeup concepts 120 5.2.1 Sparsetopologyandenergymanagement(STEM) 121 5.2.2 S-MAC 123 5.2.3 Themediationdeviceprotocol 126 5.2.4 Wakeupradioconcepts 127 5.2.5 Furtherreading 128 5.3 Contention-based protocols 129 5.3.1 CSMAprotocols 129 5.3.2 PAMAS 131 5.3.3 Furthersolutions 132 5.4 Schedule-based protocols 133 5.4.1 LEACH 133 5.4.2 SMACS 135 5.4.3 Traffic-adaptivemediumaccessprotocol(TRAMA) 137 5.4.4 Furthersolutions 139 5.5 The IEEE 802.15.4 MAC protocol 139 5.5.1 Networkarchitectureandtypes/rolesofnodes 140 5.5.2 Superframestructure 141 5.5.3 GTSmanagement 141 5.5.4 Datatransferprocedures 142 5.5.5 SlottedCSMA-CAprotocol 142 5.5.6 Nonbeaconedmode 144 5.5.7 Furtherreading 145 5.6 How about IEEE 802.11 and bluetooth? 145 5.7 Further reading 146 5.8 Conclusion 148 viii Contents 6 Link-layer protocols 149 6.1 Fundamentals: tasks and requirements 150 6.2 Error control 151 6.2.1 Causesandcharacteristicsoftransmissionerrors 151 6.2.2 ARQtechniques 152 6.2.3 FECtechniques 158 6.2.4 Hybridschemes 163 6.2.5 Powercontrol 165 6.2.6 Furthermechanismstocombaterrors 166 6.2.7 Errorcontrol:summary 167 6.3 Framing 167 6.3.1 Adaptiveschemes 170 6.3.2 Intermediatechecksumschemes 172 6.3.3 Combiningpacket-sizeoptimizationandFEC 173 6.3.4 Treatmentofframeheaders 174 6.3.5 Framing:summary 174 6.4 Link management 174 6.4.1 Link-qualitycharacteristics 175 6.4.2 Link-qualityestimation 177 6.5 Summary 179 7 Naming and addressing 181 7.1 Fundamentals 182 7.1.1 Useofaddressesandnamesin(sensor)networks 182 7.1.2 Addressmanagementtasks 183 7.1.3 Uniquenessofaddresses 184 7.1.4 Addressallocationandassignment 184 7.1.5 Addressingoverhead 185 7.2 Address and name management in wireless sensor networks 186 7.3 Assignment of MAC addresses 186 7.3.1 Distributedassignmentofnetworkwideaddresses 187 7.4 Distributed assignment of locally unique addresses 189 7.4.1 Addressassignmentalgorithm 189 7.4.2 Addressselectionandrepresentation 191 7.4.3 Furtherschemes 194 7.5 Content-based and geographicaddressing 194 7.5.1 Content-basedaddressing 194 7.5.2 Geographicaddressing 198 7.6 Summary 198 8 Time synchronization 201 8.1 Introduction to thetime synchronizationproblem 201 8.1.1 Theneedfortimesynchronizationinwirelesssensornetworks 202 8.1.2 Nodeclocksandtheproblemofaccuracy 203 8.1.3 Propertiesandstructureoftimesynchronizationalgorithms 204 8.1.4 Timesynchronizationinwirelesssensornetworks 206 8.2 Protocols based on sender/receiver synchronization 207 8.2.1 Lightweighttimesynchronizationprotocol(LTS) 207 Contents ix 8.2.2 Howtoincreaseaccuracyandestimatedrift 212 8.2.3 Timing-syncprotocolforsensornetworks(TPSN) 214 8.3 Protocols based on receiver/receiver synchronization 217 8.3.1 Referencebroadcastsynchronization(RBS) 217 8.3.2 Hierarchyreferencingtimesynchronization(HRTS) 223 8.4 Further reading 226 9 Localization and positioning 231 9.1 Properties of localizationand positioningprocedures 232 9.2 Possible approaches 233 9.2.1 Proximity 233 9.2.2 Trilaterationandtriangulation 234 9.2.3 Sceneanalysis 237 9.3 Mathematical basics for the lateration problem 237 9.3.1 Solutionwiththreeanchorsandcorrectdistancevalues 238 9.3.2 Solvingwithdistanceerrors 238 9.4 Single-hop localization 240 9.4.1 ActiveBadge 240 9.4.2 Activeoffice 240 9.4.3 RADAR 240 9.4.4 Cricket 241 9.4.5 Overlappingconnectivity 241 9.4.6 Approximatepointintriangle 242 9.4.7 Usingangleofarrivalinformation 243 9.5 Positioningin multihop environments 243 9.5.1 Connectivityinamultihopnetwork 244 9.5.2 Multihoprangeestimation 244 9.5.3 Iterativeandcollaborativemultilateration 245 9.5.4 Probabilisticpositioningdescriptionandpropagation 247 9.6 Impact of anchor placement 247 9.7 Further reading 248 9.8 Conclusion 249 10 Topology control 251 10.1 Motivationand basic ideas 251 10.1.1 Optionsfortopologycontrol 252 10.1.2 Aspectsoftopology-controlalgorithms 254 10.2 Controlling topologyin flat networks – Power control 256 10.2.1 Somecomplexityresults 256 10.2.2 Aretheremagicnumbers?–boundsoncriticalparameters 257 10.2.3 Someexampleconstructionsandprotocols 259 10.2.4 Furtherreadingonflattopologycontrol 265 10.3 Hierarchical networks by dominating sets 266 10.3.1 Motivationanddefinition 266 10.3.2 Ahardnessresult 266 10.3.3 Someideasfromcentralizedalgorithms 267 10.3.4 Somedistributedapproximations 270 10.3.5 Furtherreading 273 10.4 Hierarchical networks by clustering 274 x Contents 10.4.1 Definitionofclusters 274 10.4.2 Abasicideatoconstructindependentsets 277 10.4.3 Ageneralizationandsomeperformanceinsights 278 10.4.4 Connectingclusters 278 10.4.5 Rotatingclusterheads 279 10.4.6 Somemorealgorithmexamples 280 10.4.7 Multihopclusters 281 10.4.8 Multiplelayersofclustering 283 10.4.9 Passiveclustering 284 10.4.10Furtherreading 284 10.5 Combining hierarchical topologiesand power control 285 10.5.1 Pilot-basedpowercontrol 285 10.5.2 AdhocNetworkDesignAlgorithm(ANDA) 285 10.5.3 CLUSTERPOW 286 10.6 Adaptive nodeactivity 286 10.6.1 GeographicAdaptiveFidelity(GAF) 286 10.6.2 AdaptiveSelf-ConfiguringsEnsorNetworks’Topologies(ASCENT) 287 10.6.3 Turningoffnodesonthebasisofsensingcoverage 288 10.7 Conclusions 288 11 Routing protocols 289 11.1 The many faces of forwarding and routing 289 11.2 Gossipingand agent-based unicast forwarding 292 11.2.1 Basicidea 292 11.2.2 Randomizedforwarding 292 11.2.3 Randomwalks 293 11.2.4 Furtherreading 294 11.3 Energy-efficient unicast 295 11.3.1 Overview 295 11.3.2 Someexampleunicastprotocols 297 11.3.3 Furtherreading 301 11.3.4 Multipathunicastrouting 301 11.3.5 Furtherreading 304 11.4 Broadcast and multicast 305 11.4.1 Overview 305 11.4.2 Source-basedtreeprotocols 308 11.4.3 Shared,core-basedtreeprotocols 314 11.4.4 Mesh-basedprotocols 314 11.4.5 Furtherreadingonbroadcastandmulticast 315 11.5 Geographic routing 316 11.5.1 Basicsofposition-basedrouting 316 11.5.2 Geocasting 323 11.5.3 Furtherreadingongeographicrouting 326 11.6 Mobilenodes 328 11.6.1 Mobilesinks 328 11.6.2 Mobiledatacollectors 328 11.6.3 Mobileregions 329 11.7 Conclusions 329