20191126Chapter9-yyb20191122

1、NodeandNetworkManagement,Outline,Chapter10:Localization,Chapter10:Roadmap,Overview,Withoutknowledgeoflocationofasensor,theinformationproducedbysuchsensorisoflimiteduselocationofsensedeventsinthephysicalworldlocation-awareserviceslocationoftenprimarysensorinformation(supplychainmanagement,surveillanc

2、e)objecttrackingprotocolsbasedongeographicinformation(routing)coverageareamanagementLocationoftennotknownapriori,therefore,localizationisthetaskofdeterminingtheposition(e.g.,coordinates)ofasensororthespatialrelationshipsamongobjects,Overview,GlobalpositionpositionwithingeneralglobalreferenceframeGlo

3、balPositioningSystemorGPS(longitudes,latitudes)UniversalTransverseMercatororUTM(zonesandlatitudebands)Relativepositionbasedonarbitrarycoordinatesystemsandreferenceframesdistancesbetweensensors(norelationshiptoglobalcoordinates),Overview,AccuracyversusprecisionGPS:truewithin10mfor90%ofallmeasurements

4、accuracy:10m(“howcloseisthereadingtothegroundtruth?”)precision:90%(“howconsistentarethereadings?”)Symbolicpositioninformation“office354”“milemarker17onHighway23”,RangingTechniques,TimeofArrival(ToA,timeofflight)distancebetweensenderandreceiverofasignalcanbedeterminedusingthemeasuredsignalpropagation

5、timeandknownsignalvelocitysoundwaves:343m/s,i.e.,approx.30mstotravel10mradiosignals:300km/s,i.e.,approx.30nstotravel10mOne-wayToAone-waypropagationofsignalrequireshighlyaccuratesynchronizationofsenderandreceiverclocks,RangingTechniques,Two-wayToAround-triptimeofsignalismeasuredatsenderdevicethirdmes

6、sageifreceiverwantstoknowthedistance,RangingTechniques,TimeDifferenceofArrival(TDoA)twosignalswithdifferentvelocitiesexample:radiosignal(sentatt1andreceivedatt2),followedbyacousticsignal(sentatt3=t1+twaitandreceivedatt4)noclocksynchronizationrequireddistancemeasurementscanbeveryaccurateneedforadditi

7、onalhardware,RangingTechniques,AngleofArrival(AoA)directionofsignalpropagationtypicallyachievedusinganarrayofantennasormicrophonesanglebetweensignalandsomereferenceisorientationspatialseparationofantennasormicrophonesleadstodifferencesinarrivaltimes,amplitudes,andphasesaccuracycanbehigh(withinafewde

8、grees)addssignificanthardwarecost,RangingTechniques,ReceivedSignalStrength(RSS)signaldecayswithdistancemanydevicesmeasuresignalstrengthwithreceivedsignalstrengthindicator(RSSI)vendor-specificinterpretationandrepresentationtypicalRSSIvaluesareinrangeof0.RSSI_MaxcommonvaluesforRSSI_Max:100,128,256infr

9、eespace,RSSdegradeswithsquareofdistanceexpressedbyFriistransmissionequationinpractice,theactualattenuationdependsonmultipathpropagationeffects,reflections,noise,etc.realisticmodelsreplaceR2withRn(n=3.5),Chapter10:Roadmap,Triangulation,Exampleofrange-basedlocalizationUsesthegeometricpropertiesoftrian

10、glestoestimatelocationReliesonangle(bearing)measurementsMinimumoftwobearinglines(andthelocationsofanchornodesorthedistancebetweenthem)areneededfortwo-dimensionalspace,Triangulation(left)andtrilateration(right).,Triangulation,Unknownreceiverlocationxr=xr,yrTBearingmeasurementsfromNanchorpoints:=1,NTK

11、nownanchorlocationsxi=xi,yiTActual(unknown)bearings(x)=1(x),N(x)TRelationshipbetweenactualandmeasuredbearingsis=(xr)+with=1,NTbeingtheGaussiannoisewithzero-meanandNxNcovariancematrixS=diag(12,N2)RelationshipbetweenbearingsofNanchorsandtheirlocations:,Triangulation,Maximumlikelihood(ML)estimatorofrec

12、eiverlocationisthen:Thisnon-linearleastsquaresminimizationcanbeperformedusingNewton-Gaussiterations:,Trilateration,LocalizationbasedonmeasureddistancesbetweenanodeandanumberofanchorpointswithknownlocationsBasicconcept:giventhedistancetoananchor,itisknownthatthenodemustbealongthecircumferenceofacircl

13、ecenteredatanchorandaradiusequaltothenode-anchordistanceIntwo-dimensionalspace,atleastthreenon-collinearanchorsareneededandinthree-dimensionalspace,atleastfournon-coplanaranchorsareneeded,Trilateration,nanchornodes:xi=(xi,yi)(i=1.n)Unknownsensorlocationx=(x,y)Distancesbetweensensorandanchorsknown(ri

14、,i=1.n)Relationshipsbetweenanchor/sensorpositionsanddistances(2dimensions):ThiscanberepresentedasAx=bwith:,Trilateration,Basedonthisleastsquaressystem,wecanobtainestimationofposition(x,y)usingx=(ATA)-1ATbAnchorpositionsanddistancemeasurementsareinaccurate,therefore,iftheyarebasedonGaussiandistributi

15、ons,wecanassignaweighttoeachequationi:TheleastsquaressystemisthenagainAx=bwith:ThecovariancematrixofxisthenCovx=(ATA)-1,Iterative/CollaborativeMultilateration,Problem:whatifnodedoesnothaveatleastthreeneighboringanchors?Solution:onceanodehasdetermineditsposition,itbecomesananchorIterativemultilaterat

16、ion:repeatsuntilallnodeshavebeenlocalizederroraccumulateswitheachiteration,Iterative/CollaborativeMultilateration,Collaborativemultilateration:goal:constructagraphofparticipatingnodes,i.e.,nodesthatareanchorsorhaveatleastthreeparticipatingneighborsnodethentriestoestimateitspositionbysolvingthecorres

17、pondingsystemofoverconstrainedquadraticequationsrelatingthedistancesamongthenodeanditsneighbors,GPS-BasedLocalization,GlobalPositioningSystemmostwidelypublicizedlocation-sensingsystemprovideslaterationframeworkfordetermininggeographicpositionsoriginallyestablishedasNAVSTAR(NavigationSatelliteTiminga

18、ndRanging)onlyfullyoperationalglobalnavigationsatellitesystem(GNSS)consistsofatleast24satellitesorbitingatapprox.11,000milesstartedin1973,fullyoperationalin1995,GPS-BasedLocalization,Twolevelsofservice:StandardPositioningService(SPS)availabletoallusers,norestrictionsordirectchargehigh-qualityreceive

19、rshaveaccuraciesof3mandbetterhorizontallyPrecisePositioningService(PPS)usedbyUSandAlliedmilitaryusersusestwosignalstoreducetransmissionerrors,GPS-BasedLocalization,Satellitesareuniformlydistributedinsixorbits(4satellitesperorbit)Satellitescircleearthtwiceadayatapprox.7000miles/hourAtleast8satellites

20、canbeseensimultaneouslyfromalmostanywhereEachsatellitebroadcastscodedradiowaves(pseudorandomcode),containingidentityofsatellitelocationofsatellitethesatellitesstatusdataandtimewhensignalwassent,GPS-BasedLocalization,Sixmonitorstationsconstantlyreceivesatellitedataandforwarddatatoamastercontrolstatio

21、n(MCS)MCSislocatednearColoradoSprings,ColoradoMCSusesthedatafrommonitorstationstocomputecorrectionstothesatellitesorbitalandclockinformationwhicharesentbacktothesatellites,GPS-BasedLocalization,SatellitesandreceiversuseaccurateandsynchronizedclocksReceivercomparesgeneratedcodewithreceivedcodetodeter

22、minetheactualcodegenerationtimeofthesatellitetimedifferencebetweencodegenerationtimeandcurrenttimeexpressesthetraveltimeofthecodefromsatellitetoreceiver,GPS-BasedLocalization,Radiowavestravelatthespeedoflight(approx.186,000miles/second)Withknown,thedistancecanbedeterminedReceiverknowsthatitislocated

23、somewhereonaspherecenteredonthesatellitewitharadiusequaltothisdistanceWiththreesatellites,thelocationcanbenarroweddowntotwopointstypicallyoneofthesetwopointscanbeeliminatedeasily,GPS-BasedLocalization,Withfoursatellites,accuratelocalizationispossibleaccuratepositioningreliesonaccuratetimingreceiverc

24、locksaremuchlessaccuratethanatomicGPSclockssmalltimingerrorsleadtolargepositionerrorsexample:clockerrorof1mstranslatestoapositionerrorof300kmfourthspherewouldideallyintersectwithallthreeotherspheresinoneexactlocationspherestoolarge:reducethembyadjustingtheclock(movingitforward)spherestoosmall:increa

25、sethembyadjustingtheclock(movingitbackward),GPS-BasedLocalization,MostGPSreceiverstodaycanachievegoodaccuracy(e.g.,10morless)Additionaladvancedtechniquescanbeusedtofurtherimproveaccuracy:example:DifferentialGPS(DGPS)reliesonland-basedreceiverswithexactlyknownlocationstheyreceivesignals,computecorrec

26、tionfactors,andbroadcastthemtoGPSreceiversGPSreceiverscorrecttheirownmeasurements,GPS-BasedLocalization,GPSinwirelesssensornetworksprohibitivefactors:powerconsumption,cost,size,needforLOSdeploymentcanbelimitedtoafew(morepowerful)nodesusedasanchornodesandreferencepointsforrange-freelocalizationtechni

27、ques,Chapter10:Roadmap,AdHocPositioningSystem(APS),Exampleofarange-freelocalizationapproachbasedonconnectivityinformationinsteadofdistance/anglemeasurementsnoadditionalhardwarerequired(cost-effective)APSisadistributedconnectivity-basedlocalizationalgorithmestimatesnodelocationswiththesupportofatleas

28、tthreeanchornodeslocalizationerrorscanbereducedbyincreasingthenumberofanchorsusesconceptofDV(distancevector),wherenodesexchangeroutingtableswiththeirone-hopneighbors,AdHocPositioningSystem(APS),MostbasicschemeofAPS:DV-hopeachnodemaintainsatableXi,Yi,hi(locationofnodeianddistanceinhopsbetweenthisnode

29、andnodei)whenananchorobtainsdistancestootheranchors,itdeterminestheaveragehoplength(“correctionfactor”ci),whichisthenpropagatedthroughoutthenetworkgiventhecorrectionfactorandtheanchorlocations,anodecanperformtrilateration,AdHocPositioningSystem(APS),ExamplewiththreeanchorsA1knowsitsdistancetoA2(50m)

30、andA3(110m)A1knowsitshopdistancetoA2(2)andA3(6)correctionfactor:(50+110)/(2+6)=20(estimateddistanceofahop)correctionsarepropagatedusingcontrolledflooding,i.e.,anodeonlyusesonecorrectionfactorandignoressubsequentlyreceivedones,AdHocPositioningSystem(APS),Variationofthisapproach:DV-distancemethoddista

31、ncesaredeterminedusingradiosignalstrengthmeasurementsdistancesarepropagatedtoothernodesprovidesfinergranularity(notallhopsareestimatedtobethesamesize)moresensitivetomeasurementerrorsAnothervariation:EuclideanmethodtrueEuclidiandistancestoanchorsareusednodemusthaveatleasttwoneighborsthathavedistancem

32、easurementstoanchorsandthedistancebetweenthetwoneighborsisknownsimpletrigonometricrelationshipsareusedtodeterminethedistancebetweennodeandanchor,ApproximatePointinTriangulation,Exampleofanarea-basedrange-freelocalizationschemeAPITreliesonanchornodesanycombinationofthreeanchorsformsatriangleanodedete

33、rminesitspresenceinsideoroutsideatriangleusingthePointinTriangulation(PIT)testanodeMisoutsideatriangleformedbyanchorsA,B,andCifthereexistsadirectionsuchthatapointadjacenttoMiseitherfurtherorclosertoallpointssimultaneously;otherwiseMisinside,ApproximatePointinTriangulation,ThisperfectPITtestisinfeasi

34、bleinpracticesinceitwouldrequirethatanodecanbemovedinanydirectionIndensenetworks,nodemovementcanbeemulatedusingneighborinformation(exchangedviabeacons)signalstrengthmeasurementscanbeusedtodetermineifanodeisclosertoananchororfurtherawayifnoneighborofnodeMisfurtherfromorclosertothreeanchorsA,B,Csimult

35、aneously,Mcanassumethatitisinsidethetriangle,MultidimensionalScaling,MDSisbasedonpsychometricandpsychophysicsSetofdataanalysistechniquesthatdisplaystructureofdistance-likedataasageometricalpictureCanbeusedincentralizedlocalizationtechniqueswithpowerfulcentraldevice(basestation)collectsinformationfro

36、mthenetwork,determinesthenodeslocations,andpropagatesthisinformationbackintothenetworkNetworkisrepresentedasundirectedgraphofnnodes,withm(n)anchornodes(whichknowtheirlocations),andedgesrepresentingtheconnectivityGoalofMDSistopreservethedistanceinformations.t.thenetworkcanberecreatedinthemultidimensi

37、onalspaceTheresultisanarbitrarilyrotatedandflippedversionoftheoriginalnetworklayout,MultidimensionalScaling,ClassicalMDS:simpleversion,closedformsolutionforefficientimplementationmatrixofsquareddistancesbetweennodesD2=c1+1c-2SS1=nx1vectorofonesS=similaritymatrix,whereeachrowrepresentsthecoordinateso

38、fpointialongmcoordinatesSS=scalarproductmatrixc=vectorconsistingofdiagonalelementsofthescalarproductmatrixUsingcenteringmatrixT=I-11/n:TD2T=T(c1+1c-2SS)T=Tc1T+T1cT-T(2B)T(whereB=SS)andTD2T=-T(2B)TMultiplyingbothsideswith-1/2:B=-1/2TD2TBcanbedecomposedinto:B=QQ=(Q1/2)(Q1/2)=SSOnceBhasbeenobtained,the

39、coordinatesScanbecomputedbyeigendecomposition:S=Q1/2,MultidimensionalScaling,LocationmethodMDS-MAP:constructdistancematrixDallpairsshortestpathalgorithm(e.g.,Dijkstras)dij=distancebetweennodesiandjclassicalMDSisappliedtoobtainapproximatevalueoftherelativecoordinateofeachnoderelativecoordinatesaretra

40、nsformedtoabsolutecoordinatesbyaligningtheestimatedrelativecoordinatesofanchorswiththeirabsolutecoordinatesestimatescanbefurtherrefinedusingleast-squaresminimization,Chapter10:Roadmap,LighthouseApproach,Exampleofanevent-drivenlocalizationapproachRequirement:basestationwithlightemitterIdealisticlight

41、source:emittedbeamoflightisparallel(constantwidthb)Lightsourcerotatess.t.sensorseesbeamoflightfortbeam,LighthouseApproach,PerfectlyparallellightbeamsarehardtorealizeinpracticeSmallbeamspreadscanresultinlargelocalizationerrorsifb=10cmandspread=1,b=18.7cmat5mdistanceBeamwidthshouldbelargetokeepinaccur

42、aciessmallSolution:twolaserbeamsthatoutlinea“virtual”parallelbeamonlyedgesofthevirtualbeamareofinterest,LighthouseApproach,Prototypebasestationconsistingoftwolighthousesandtheresulting2Dcoordinatesystem.,MultisequencePositioning,MSPworksbyextractingrelativelocationinformationfrommultiplesimpleone-di

43、mensionalorderingsofsensornodeseventgeneratorsatdifferentlocationstriggerevents(e.g.,ultrasoundsignalsorlaserscans)nodesobserveeventsatdifferenttimes,leadingtonodesequencemultisequenceprocessingalgorithmnarrowspotentiallocationsforeachnodedistribution-basedestimationmethodcanestimateexactlocations,M

44、ultisequencePositioning,MSPworksbyextractingrelativelocationinformationfrommultiplesimpleone-dimensionalorderingsofsensornodes,MultisequencePositioning,MSPworksbyextractingrelativelocationinformationfrommultiplesimpleone-dimensionalorderingsofsensornodes,MultisequencePositioning,Obtainingmultiplenod

45、essequences,MultisequencePositioning,EacheventleadstonodesequenceMultisequenceprocessingalgorithmcannarrowthepotentiallocationsforeachnodeDistribution-basedestimationmethodcanestimateexactlocations,MultisequencePositioning,IndoorTestbed,OutdoorTestbed,MultisequencePositioning,MeanLocalizationError,C

46、hapter11:Security,Chapter11:Roadmap,SecurityfundamentalsSecuritychallengesSecurityattacksSecurityprotocolsandmechanismsIEEE802.15.4andZigBeesecurity,Fundamentals,SecurityandprivacyarebigchallengesforanytypeofcomputingandnetworkingenvironmentWell-knownCIAsecuritymodel:Confidentialityensurethatonlythe

47、intendedreceivercanread/interpretamessageunauthorizedaccessispreventedIntegrityensurethatamessagecannotbemodifiedunauthorizedindividualsshouldnotbeabletodestroy/altermessageAvailabilityensurethatsystem/networkisabletoperformitstaskswithoutinterruptionoftenmeasuredintermsofpercentagesofup/downtime,Ex

48、amples,Confidentiality:eavesdropping:unauthorizedmessagereceptionIntegrity:man-in-the-middleattack:unauthorizedindividual/systempositionsitselfbetweensenderandreceivertointercept,modify,andretransmitmessagesAvailability:denial-of-serviceattack:attempttodisrupttransmissionorservice,Examples,MoreTermi

49、nology,Authenticationprocessofestablishingorconfirmingtheidentityofuser/deviceensuresthatmessagecamefromwhoitclaimstohavecomefromNonrepudiationprocessofprovingthatperson/devicehasperformedacertaintransaction/transmissionDigitalsignaturesoftenusedtosupportauthentication,nonrepudiation,andintegrity,Cr

50、yptography,Processofprotectinginformationusingencoding/decodingtechniquesSymmetrickeycryptographysinglekeysharedbetweencommunicatingpartiessimpleexample:shiftcipher(key=fixedshiftinalphabet)challenge:securedistributionofsharedkeyexamples:DES,AES,IDEA,Cryptography,Publickeycryptographysecretkey:willn

51、everbesharedwithanyoneelsepublickey:canbesharedfreelymessageencryptedwithsecretkeycanonlybedecryptedwithcorrespondingpublickey(e.g.,forauthenticatingthesender)messageencryptedwithpublickeycanonlybedecryptedwithcorrespondingsecretkey(e.g.,forprovidingconfidentiality)examples:RSA,Diffie-Hellmanagreeme

52、ntprotocol,ChallengesofSecurityinWSNs,Resourceconstraintslimitedcomputational,networking,andstoragecapabilitiesofsensorsenergyconstraintsofsensorsLackofcentralcontrollargeWSNsoftendonthavecentralizedcontrolrequiresdistributed/decentralizedsecuritysolutionsRemotelocationsensorsoftenleftunattendeddiff

53、iculttopreventunauthorizedphysicalaccessandtamperingError-pronecommunicationdifficulttodistinguishwirelesscommunicationerrorsfromattacks,SecurityinWSNs,WSNcharacteristicsthatfacilitatesecurity:self-managingandself-repairingnatureredundancyDatafreshnessproblemWSNsecuritymustensurethatsensordataarerec

54、ent(andnotreplaysofolddata)particularlyimportantforkeydistributionschemesWSNsprovidemoreopportunitiesforattacksthanothernetworksmanysensorprotocolsrequirelocationinformationmanysensornodesrequireaccuratetimesynchronizationbothcanbeaffectedbymodifying,injecting,droppingmessages(e.g.,beacons)carryings

55、uchinformation,Denial-of-Service(DoS),Attempttostopnetwork/systemfromfunctioningorprovidingaservicePhysicalLayerDoSjammingattackinterferewiththeradiofrequenciesofaWSNevensmallnumbersofattackingnodescanbeeffectiveifwellpositioned(e.g.,closetoanimportantnodesuchasaBS)oriftheirsignalsarestrongcounterme

56、asure:spread-spectrumcommunication(e.g.,FHSS)tamperingattackattackerobtainsphysicalaccesstosensornodeusedtomodify/destroynode,obtainsensitiveinformationoruseasentrypointsforfurtherattacksintothenetworkcountermeasures:tamper-proofmaterialsandenclosures,disabledevicewhenattackdetected,Denial-of-Servic

57、e(DoS),LinkLayerDoScollisionattackattempttointerferewithpackettransmissionscausescostlyexponentialbackoffproceduresandretransmissionsoftentriestocausecollisionsneartheendofaframe,requiringretransmissionofentireframeexhaustionattackattacks(suchascollisionattack)withthegoalofprematuredepletionofasenso

58、rsenergysourcesexample:issueRTSmessagetopromptCTSresponsefromanothernode(exploitinghandshaketechniques),AttacksonRouting,BlackholeattackmaliciousnodeonaroutesimplydropsallpacketsSelectiveforwardingattacksimilartoblackholeattack,butnotalltrafficisdroppedmoredifficulttodetect(hardtodistinguishattackfr

59、ompoorconnectivity)Rushingattackexploitsroutediscoverytechniquesofon-demandprotocolsrouterequestpacketsarerushedtowardsdestination,increasingthemaliciousnodesprobabilitytobeontheselectedrouteSinkholeattacknodeattemptstopositionitselfonasmanynetworkflowsaspossibleSybilattackattackerclaimstohavemultipleidentitiesorlocations,AttacksonTransportLayer,Floodingattackexploitsfactthatmanytransportprotocolsmaintainstateinformationandarethereforevulnerabletomemoryexhaustionexample:attackermakesmany(incomplete)connectionreque