《金仲达教授》课件

SensorNetworks

金仲達教授清華大學資訊系統與應用研究所九十三學年度第一學期0Sources“Comm’nSense:ResearchChallengesinEmbeddedNetworkedSensing,〞D.Estrin,

“ASurveyonSensorNetwork,〞

I.F.Akyildiz,W.Su,Y.Sankarasubramaniam,E.Cayirci,GeorgiaInstituteofTechnology

IEEECommunicationsMagazine,Aug.2002PervasiveComputing1IntroductionMarkWeiserenvisionedaworldinwhichcomputingispervasiveWhatweneedistoinstrumentthephysicalworldwithpervasivenetworksofsensor-rich,embeddedcomputationSuchsystemsfulfilltwoofWeiser’sobjectives:Ubiquity:byinjectcomputationintothephysicalworldwithhighspatialdensityInvisibility:byhavingthenodesandcollectiveofnodesoperateautonomouslyPervasiveComputing2IntroductionWhatisrequiredistheabilitytoeasilydeployflexiblesensing,computation,andactuationcapabilitiesintoourphysicalenvironmentssuchthatthedevicesthemselvesaregeneral-purposeandcanorganizeandadapttosupportseveralapplicationtypesPervasiveComputing3Embednumerousdistributeddevicestomonitor/interactwithphysicalworldExploitspatiallyandtemporallydense,

insitu,sensingandactuationNetworkthesedevicessothattheycancoordinatetoperformhigher-leveltasks.Requiresrobustdistributedsystemsofhundredsorthousandsofdevices.VisionPervasiveComputing4SensorNodesandNetworksSensornodes=sensing,dataprocessing,andcommunicatingcapacitySensornetwork:alargenumberofsensornodesthataredenselydeployedeitherinsidethephenomenonorveryclosetoitSensornodepositionnotengineeredorpredecided

protocolsoralgorithmsmustbeself-organizingCooperativeeffortofsensornodeswithinnetworkprocessingPervasiveComputing5ApplicationsScientific:eco-physiology,biocomplexitymappingInfrastructure:ContaminantflowmonitoringEngineering:adaptivestructuresPervasiveComputing6OtherApplications(I)EnvironmentalForestfiredetection,biocomplexitymappingoftheenvironment,flooddetection,precisionagricultureHealthyTelemonitoringofhumanphysiologicaldata,trackingandmonitoringdoctorsandpatientsinsideahospital,drugadministrationinhospitalsMilitary:Monitoringfriendlyforces,equipmentandammunition;battlefieldsurveillance;reconnaissanceofopposingforcesandterrain;targeting;battledamageassessment;nuclear,biologicalandchemicalattackdetectionandreconnaissancePervasiveComputing7OtherApplications(II)HomeHomeautomationSmartenvironmentCommercialEnvironmentalcontrolinofficebuildingsInteractivemuseumsDetectingandmonitoringcartheftsManaginginventorycontrolVehicletrackinganddetectionMonitoringproductqualityMonitoringdisasterareas….PervasiveComputing8ChallengesTightcouplingtothephysicalworldandembeddedinunattended“controlsystems〞DifferentfromtraditionalInternet,PDA,mobilityapplicationsthatinterfaceprimarilyanddirectlywithhumanusersUntethered,smallform-factor,nodespresentstringentenergyconstraintsLivingwithsmall,finite,energysourceisdifferentfromfixedbutreusableresourcessuchasBW,CPU,storageCommunicationsisprimaryconsumerofenergySendingabitover10or100metersconsumesasmuchenergyasthousands/millionsofoperationsPervasiveComputing9NewDesignThemesLong-livedsystemsthatcanbeuntetheredandunattended

Low-dutycycleoperationwithboundedlatencyExploitredundancyTieredarchitectures(mixofform/energyfactors)Self-configuringsystemsthatcanbedeployedadhocMeasureandadapttounpredictableenvironmentExploitspatialdiversityanddensityofsensor/actuatornodesPervasiveComputing10ApproachLeveragedataprocessinginsidethenetworkExploitcomputationneardatatoreducecommunicationAchievedesiredglobalbehaviorwithadaptivelocalizedalgorithms(i.e.,donotrelyonglobalinteractionorinformation)Dynamic,messy(hardtomodel),environmentsprecludepre-configuredbehaviorCan’taffordtoextractdynamicstateinformationneededforcentralizedcontrolorevenInternet-styledistributedcontrolPervasiveComputing11Whycan’twesimplyadaptInternetprotocolsand“endtoend〞architecture?InternetroutesdatausingIPaddressesinPacketsandLookuptablesinroutersHumansgetdataby“namingdata〞toasearchengineManylevelsofindirectionbetweennameandIPaddressWorkswellfortheInternet,andforsupportofPerson-to-PersoncommunicationEmbedded,energy-constrained(un-tethered,small-form-factor),unattendedsystemscan’ttoleratecommunicationoverheadofindirectionPervasiveComputing12vs.AdHocNetworksLargenumberofsensornodes(severalordersofmagnitudehigher)DenselydeployedPronetofailuresNetworktopologychangesveryfrequentlyMainlyuseabroadcastparadigmvs.point-to-pointinadhocnetworksLimitedinpower,computationalcapacities,andmemoryMaynothaveglobalidentification(ID)PervasiveComputing13CommunicationArchitectureFactorsofdesignconsiderationTransmissionmediaProductioncostsPowerconsumptionFaulttoleranceNWtopologyHWconstraintsEnvironmentScalabilityPervasiveComputing14FaultToleranceTheabilitytosustainsensornetworkfunctionalitieswithoutanyinterruptionduetosensornodefailuresThereliabilityRk(t)orfaulttoleranceofasensornodecanbemodeledwiththePoissondistributiontocapturetheprobabilityofnothavingafailurewithinthetimeinterval(0,t)Rk(t)=exp(-λkt),fornodekPervasiveComputing15ScalabilityThenumberofsensornodes10->100->1000->10000->….DependingontheapplicationNewschemesmustbeabletoutilizethehighdensityThedensityμ(R)=(N.πR2)/AA:regionareaR:radiotransmissionrangeN:thenumberofscatteredsensornodesPervasiveComputing16ProductionCostsThecostofasinglenodeisveryimportanttojustifytheoverallcostofthenetworkThecostofasensornodeshouldbemuchlessthanUS$1Thestate-of-arttechnologyallowsaBluetoothradiosystemtobelessthanUS$1010timesmoreexpensivethethetargetedpricePervasiveComputing17Hardware4basicunits:sensingunit,processingunit,transceiverunit,powerunitSensing:sensors,Analog-to-digitalconverters(ADCs)Additionalapplication-dependentunitsLocationfindingsystem,powergenerator,mobilizer….PervasiveComputing18HardwareConstraintsConstraintsSizePowerOperateinveryhighdensitiesLowcostDispensableAutonomousAdaptivetoenvironmentPervasiveComputing19SensorNetworkTopologyTopologymaintenanceandchangein3phasesPredeploymentanddeploymentphaseBethrowninasamassorplacedonebyonePost-deploymentphaseChangeinsensornodes’position,reachability,availableenergy,malfunctioning,andtaskdetailsRedeploymentofadditionalnodesphaseAdditionalsensornodescanberedeployedPervasiveComputing20EnvironmentNodesaredenselydeployedeitherverycloseordirectlyinsidethephenomenontobeobservedUsuallyworkunattendedinremotegeographicareasintheinterioroflargemachineryatthebottomofanoceaninabiologicallyorchemicallycontaminatedfieldinabattlefieldbeyondtheenemylinesinahomeorlargebuilding….PervasiveComputing21TransmissionMediaOftenbywirelessmediumRadio:UsedbymostsensorsμAMPSsensorusesaBluetooth-compatible2.4GHztransceiverwithanintegratedfrequencysynthesizerInfrared:License-free,robusttointerferencefromelectricaldevicescheaperandeasiertobuildOptical:SmartDustmoteBothinfraredandopticalrequirelineofsightPervasiveComputing22PowerConsumptionInsomeapplicationscenarios,replenishmentofpowerresourcesmightbeimpossibleBatterylifetimeInamultihopadhocsensornetwork,eachnodeplaysdualroleofdataoriginatoranddataroutercausesignificanttopologicalchangesrequirereroutingofpacketsandreorganizationofthenetworkPowerconsumptionsensing,communication,anddataprocessingPervasiveComputing23DesignIssuesAccordingtoProtocolStackPhysicallayer:Simple,robustmodulation,transmission,receivingMACprotocolpower-aware;minimizecollisionwithneighbors’broadcastsNetworklayerroutingdatasuppliedbytransportlayerTransportlayermaintainflowofdataPervasiveComputing24ThreeManagementPlanesThepowermanagementplane,e.g.TurnoffitsreceiverafterreceivingamessageBroadcastslowinpowerandcannotparticipateinroutingmessagesThemobilitymanagementplaneDetectsandregistersmovementofsensornodesmaintainroutebacktotheuser,keeptrackoftheirneighborThetaskmanagementplanebalancesandschedulessensingtasksforaspecificregionTheyareneededforsensornodestoworkpower-efficiently,routedatainamobilenetwork,shareresourcesbetweensensornodesPervasiveComputing25PhysicalLayerResponsibilityFrequencyselection,carrierfrequencygeneration,signaldetection,modulation,anddataencryption.915MHzindustrial,scientific,andmedical(ISM)bandhasbeenwidelyusedLongdistancewirelesscommunicationcanbeexpensiveintermsofpowerAgoodmodulationiscriticalforreliablecomm.BinaryandM-arymodulationschemesUltrawideband(UWB)orimpulseradio(IR)arepromisingPervasiveComputing26PhysicalLayerOpenIssuesModulationschemesSimpleandlow-powermodulationschemesStrategiestoovercomesignalpropagationeffectsHardwaredesignTiny,low-power,low-costtransceiver,sensing,andprocessingunitsPower-efficienthardwaremanagementstrategiesPervasiveComputing27DataLinkLayerResponsibilityMultiplexingofdatastreams,dataframedetection,mediumaccessanderrorcontrolReliablepoint-to-pointandpoint-to-multipointMediumAccessControlprotocolcreationofthenetworkinfrastructurefairlyandefficientlysharecommunicationresourcesExistingMACprotocolscannotbeusedCellularsystem:infrastructure-basedBluetoothandmobileadhocnetwork(MANET)muchlargernumber,powerandradiorange,frequenttopologychange,powerconservationneededPervasiveComputing28SomeProposedMACProtocolsPervasiveComputing29ExampleMACProtocolsSelf-OrganizingMediumAccessControlforSensorNetworks(SMACS)andtheEavesdrop-And-Register(EAR)AlgorithmNodestodiscovertheirneighborsandestablishcommunicationwithouttheneedforanylocalorglobalmasternodesNonecessityfornetworkwidesynchronizationusingarandomwake-upscheduleduringconnectionphaseandturningtheradiooffduringidletimeslotsEARattemptstooffercontinuousservicetothemobilenodesPervasiveComputing30DataLinkOpenIssuesMACformobilesensornetworksmoreextensivemobilityinthesensornodesandtargetsDeterminationoflowerboundsontheenergyrequiredforsensornetworkself-organizationErrorcontrolcodingschemesPower-savingmodesofoperationPervasiveComputing31NetworkLayerDesignprinciplesPowerefficiencySensornetworksaremostlydata-centricDataaggregationisusefulonlywhenitdoesnothinderthecollaborativeeffortofthesensornodes.Anidealsensornetworkhasattribute-basedaddressingandlocationawarenessAlsoprovidinginternetworkingwithexternalnetworksPervasiveComputing32Energy-EfficientRouteAvailablepower:PAEnergyrequired(α)MaximumminimumPAnoderouteMinPAislargerthan

theminPAsMaximumPArouteMinimumenergyrouteMinimumhoproutePervasiveComputing33DataCentricRouteUseinterestdisseminationSinksbroadcasttheinterest,orSensornodesbroadcastanadvertisementandwaitforarequestOftenrequireattribute-basednamingQuerybyusingattributesofphenomenonDataaggregationSolvetheimplosionandoverlapproblemsPervasiveComputing34ProposedSchemesFloodingImplosion(duplicatedmessage),overlap(bothsensorsdetectthesameevent),resourceblindness(notconsideringresourceconstraints)GossipingRelaypacketstorandomlyselectedneighborNegotiation(SPIN)PervasiveComputing35MoreSchemesSmallminimumenergycommunicationnetworkSequentialassignmentroutingLow-energyadaptiveclusteringhierarchyDirecteddiffusionPervasiveComputing36ProtocolSummaryPervasiveComputing37ApplicationLayerProtocolsSensormanagementnodesdonothaveglobalidentificationsandareinfrastructurelessProvidingadministrativetasksIntroducingtherulesrelatedtodataaggregation,attribute-basednaming,andclusteringtothesensornodesExchangingdatarelatedtothelocationfindingalgorithmsTimesynchronizationofthesensornodesMovingsensornodesTurningsensornodesonandoffQueryingthesensornetworkconfigurationandthestatusofnodes,andreconfiguringthesensornetworkAuthentication,keydistribution,andsecurityindatacommunicationsPervasiveComputing38ApplicationLayerProtocolsTaskassignmentanddataadvertisementinterestdisseminationAdvertisementofavailabledataSensorqueryanddatadisseminationissuequeries,respondtoqueriesandcollectincomingrepliesSensorqueryandtaskinglanguage(SQTL)supports3typesofeventsReceivedefineseventsgeneratedbyasensornodewhenthesensornodereceivesamessageeverydefineseventsoccurringperiodicallyduetotimertimeoutexpiredefineseventsoccurringwhenatimerisexpiredDifferenttypesofSQDDPcanbedevelopedforvariousapplications.TheuseofSQDDPsmaybeuniquetoeachapplicationPervasiveComputing39PervasiveComputing40ResearchAreasConstructsfor“innetwork〞distributedprocessingsystemorganizedaroundnamingdata,notnodes“programming〞largecollectionsofdistributedelementsLocalizedalgorithmsthatachievesystem-widepropertiesTimeandlocationsynchronizationenergy-efficienttechniquesforassociatingtimeandspacewithdatatosupportcollaborativeprocessingExperimentalinfrastructurePervasiveComputing41ConstructsforinNWProcessingNodespull,push,storenameddata(usingtuplespace)tocreateeffic.processingpointsinNWe.g.duplicatesuppression,aggregation,correlationNestedqueriesreduceoverheadrelativeto“edgeprocessing〞Complexqueriessupport

collaborativesignalproc.propagatefunction

describingdesired

locations/nodes/data

(e.g.ellipsefortracking)PervasiveComputing42Self-organizationwithLocalizedAlg.Self-configurationandreconfigurationessentialtolifetimeofunattendedsystemsindynamic,constrainedenergy,environmentEfficient,multi-hoptopologyformation:nodemeasuresneighborhoodtodetermineparticipation,dutycycle,and/orpowerlevelBeaconplacement:candidatebeaconmeasurespotentialreductioninlocalizationerrorRequireslargesolutionspace;notseekinguniqueoptimalInvestigatingapplicability,convergence,roleofselectiveglobalinformationPervasiveComputing43TimeandLocationSynchronizationCommontimecoordinateforinsituprocessing,correlationofeventsDevelopingmethodsthatbalancecommunication(energy)costwithothervariables(e.g.,precision,scope,lifetime,cost,formfactor)PostfactopulsesynchronizationCommonspatialcoordinatefor3-spacerelatedtasksandnetworkoperation(e.g.,geo-routing)MethodsnotrelyonGPSorRFRSSI(duetoenvir.)Multi-modallocalizationusingacoustictimeofflightmeasurements,RFsynchronization,andimagingtoidentifybaddatasources(NLOS)PervasiveComputing44ExperimentalInfrastructurePC-104+

(off-the-shelf)UCBMote

(Pister/Culler)SoftwareDirectedDiffusion

TinyOS(UCB/Culler)Measurement,SimulationPervasiveComputing45BerkeleyMotes&TinyOS孫文宏46BerkeleyMotes1stgeneration2ndgenerationPervasiveComputing47SystemofMICAMotesPervasiveComputing48MICAMotesProcessorandradioboard- MPR300Sensorboard– MTS310Basestation/interfaceboard- MIB300PervasiveComputing49MICAMotesPervasiveComputing50MICAMotesPervasiveComputing51SensorBoard2.25in1.25inMicrophoneAccelerometerLightSensorTemperatureSensorSounderMagnetometerPervasiveComputing52Processor/RadioBoardPervasiveComputing53Processor/RadioBoardPervasiveComputing54TinyOSTinyOS=application/binaryimage,executableonanATmegaprocessorevent-driven,2-levelscheduling,single-sharedstacknokernel,noprocessmanagement,nomemorymanagement,

novirtualmemorysimpleFIFO

scheduler,part

ofthemainCommunicationActuatingSensingCommunicationApplication(UserComponents)Main(includesScheduler)Hardware

AbstractionsPervasiveComputing55TinyOSf:\avrgcc\cygwin\tinyos-1.x\apps{cnt_to_leds,cnt_to_rfm,sense,…} \docs{connector.pdf,tossim.pdf,…}\tools{toscheck,inject,verify,…}\tos{shared/systemcomponents,…}

…………… ………..PervasiveComputing56ProgrammingModelApplicationComponent2types:modulesandconfigurations.ModuleConfigurationAconfigurationisacomponentthat"wires"othercomponentstogether.EveryNesCapplicationhasasingletop-levelconfiguration.InterfacePervasiveComputing57ProgrammingModelapplication:configurationcomp1:modulecomp3comp4comp2:configurationPervasiveComputing58ReferenceCrossbow

MICAMotes

TinyOS

TinyOSsupport

TinyOStutorial

PADSFTP/TinyOSPervasiveComputing59DirectedDiffusion:

AScalableandRobustCommunicationParadigmforSensorNetworksChalermekIntanagonwiwat(USC/ISI)RameshGovindan(USC/ISI)DeborahEstrin(USC/ISIandUCLA)60TheGoalEmbednumerousdevicestomonitorandinteractwithphysicalworldNetworkthesedevicessothattheycancoordinatetoperformhigher-leveltasksRequiresrobustdistributedsystemsoftensofthousandsofdevicesPervasiveComputing61TheChallenge:Dynamics!ThephysicalworldisdynamicDynamicoperatingconditionsDynamicavailabilityofresources…particularlyenergy!DevicesmustadaptautomaticallytotheenvironmentToomanydevicesformanualconfigurationEnvironmentalconditionsareunpredictableUnattendedandun-tetheredoperationiskeytomanyapplicationsPervasiveComputing62EnergyIstheBottleneckResourceCommunicationVSComputationCostE

R4

10m:5000ops/transmittedbit100m:50,000,000ops/transmittedbitShortdistancecommunication=>multi-hopCannotassumeglobalknowledge,cannotpre-configurenetworksGetdesiredglobalbehaviorthrulocalizedinteractionsEmpiricallyadapttoobservedenvironmentCanleveragedataprocessing/aggregationinsidethenetworkPervasiveComputing63ResearchThemeWhatcommunicationprimitivescanbeemployedinsuchunattendedsensornetworks?Assumenostructuredsensorfields,buttask-specificAuserofthenetworkcontactoneofthesensorsinthefieldandposequeries(interrogation):e.g.,“GivemeperiodicreportsaboutanimallocationinregionAeverytseconds〞InterrogationpropagatedtosensornodesinregionASensornodesinregionAaretaskedtocollectdataDataaresentbacktotheuserseverytsecondsDisseminationmechanismsfortasksandevents?PervasiveComputing64IssuestoBeAddressedScalabletothousandsofsensornodesSensornodesmayfail,losebatterypower,betemporarilyunabletocommunication,…

=>communicationmechanismsmustberobustMinimizeenergyusage=>adatadisseminationmechanismforsensors

DirectedDiffusionPervasiveComputing65DirectedDiffusionIn-networkdataprocessing(aggregation,caching)DistributedalgorithmwithlocalizedinteractionApplication-awarecommunicationprimitivesexpressedintermsofnameddata(notintermsofthenodesgeneratingorrequestingdata)

=>data-centricDatageneratedbysensorsnamedbyattribute-valueSensornodesneednothavegloballyuniqueaddress,butneedtodistinguishbetweenneighborsPervasiveComputing66BasicIdeasAnoderequestsdatabysendinginterestsfornameddata(diffusion)GradientsaresetupinnetworktodraweventsDatamatchingtheinterestisdrawntowardsthatnodealongmultiplereversepathsThenetworkreinforcesoneormorepathsIntermediatenodescancache,transform,oraggregatedata,andmaydirectinterestsbasedonpreviouslycacheddataInterest/datapropagation,aggregationdecidedbylocalizedinteractions(withlocalnaming)PervasiveComputing67NamingTaskdescriptionsarenamedbyalistofattribute-valuepairsThisspecifiesaninterestfordatamatchingtheattributesPervasiveComputing68BasicDirectedDiffusionSettingupgradients(flooding)SourceSinkInterest=InterrogationGradient=WhoisinterestedBroadcastperiodicallyDatarate=1msPervasiveComputing69BasicDirectedDiffusionSourceSinkSendingdataandreinforcingthebestpathLowrateeventReinforcement=Increasedintereste.g.1stneighborsendingtheeventPervasiveComputing70MultipleSourcesandSinksPervasiveComputing71DirectedDiffusionandDynamicsRecoveringfromnodefailureSourceSinkLowrateevent

HighrateeventReinforcementPervasiveComputing72DirectedDiffusionandDynamicsSourceSinkStablepathLowrateevent

HighrateeventPervasiveComputing73LocalBehaviorChoicesForpropagatinginterestsInourexample,floodMoresophisticatedbehaviorspossible:e.g.basedoncachedinformation,GPSFordatatransmissionMulti-pathdeliverywithselectivequalityalongdifferentpathsprobabilisticforwardingsingle-pathdelivery,etc.Forsettingupgradientsdata-rategradientsaresetuptowardsneighborswhosendaninterest.Otherspossible:probabilisticgradients,energygradients,etc.Forreinforcementreinforcepaths,orpartsthereof,basedonobserveddelays,losses,variancesetc.othervariants:inhibitcertainpathsbecauseresourcelevelsarelowPervasiveComputing74SimulationStudyofDiffusionKeymetricAverageDissipatedEnergypereventdeliveredindicatesenergyefficiencyandnetworklifetimeComparediffusiontofloodingcentrallycomputedtree(omniscientmulticast)PervasiveComputing75DiffusionSimulationDetailsSimulator:ns-2NetworkSize:50-250NodesTransmissionRange:40mConstantDensity:1.95x10-3nodes/