COST-AWAREROUTINGPROTOCOLSFORLOCATION-PRIVACYANDEFFICIENCYIN WIRELESSSENSORNETWORKS ByLeronJ.Lightfoot ADISSERTATION Submittedto MichiganStateUniversity inpartialfulfillmentoftherequirements forthedegreeof ElectricalEngineering–DoctorofPhilosophy 2015ABSTRACT COST-AWAREROUTINGPROTOCOLSFORLOCATION-PRIVACYANDEFFICIENCYIN WIRELESSSENSORNETWORKS ByLeronJ.Lightfoot Wirelesssensornetworks(WSNs)canprovidetheworldwithatechnologyforreal-timeevent monitoringforbothmilitaryandcivilianapplications.Oneoftheprimaryconcernsthathinders thesuccessfuldeploymentofwirelesssensornetworksishowtoprovideadequatesourceand destinationnodeslocationprivacy.Theprivacyofthelocationisvitalandhighlyjeopardizedby theusageofwirelesscommunications.Whilemessagecontentprivacycanbeensuredthrough messageencryption,itismuchmoredifficulttoadequatelyaddressthelocationprivacyissue. ForWSNs,locationprivacyserviceisfurthercomplicatedbythefactthatsensorsconsistoflow- costandenergyefficientradiodevices.Therefore,usingcomputationallyintensivecryptographic algorithms(suchaspublic-keycryptosystems)andlargescalebroadcasting-basedprotocolsare notsuitableforWSNs. Manyprotocolshavebeenproposedtoprovidelocationprivacybutmostofthemarebasedon public-keycryptosystems,whileothersareeitherenergyinefficientorhavecertainsecurityflaws. Afteranalyzingthesecurityweaknessesoftheexistingschemes,weproposeseveralcreativeand secureenergy-awareroutingprotocolsthatcanaddressthelocationprivacyissueinWSNs.For source-locationprivacy,wepropose3schemes.Thefirstschemerouteseachmessagetoaran- domlyselectedintermediatenode(RSIN)beforeitistransmittedtotheSINKnode.However, thisschemecanonlyprovidelocalsource-locationprivacy.Inthesecondscheme,anetworkmix- ingring(NMR)isproposedtoprovidenetwork-levelsource-locationprivacy.Thethirdscheme achievesnetwork-levelsource-locationprivacythroughatechniquewecalltheSinkToroidalRe- gion(STaR)routing.Fordestination-locationprivacy,weproposetheBubbleroutingprotocoland aseriesofR-STaRroutingprotocols.Foreachoftheseroutingschemes,bothsecurityanalysisus- ingquantitativemeasurementsandsimulationresultsshowthattheproposedprotocolsaresecure andenergy-efficient. Whileprovidinglocationprivacyisvital,prolongingthelifetimeofthenetworkcanbeavery essentialcomponentaswell.Inthisdissertation,weproposeacluster-basedenergy-awarerouting scheme,calledQuad-RegionCluster-HeadSelection(Q-ReCHS),whichwillprolongthenetwork lifetimebyevenlydistributingtheenergyloadamongallthenodes.Ourextensivesimulation resultsoncluster-basedroutingdemonstratesthatourproposedQ-ReCHSschemecanoutperform manyoftheexistingschemes. Dedicatedtomyfamily ivACKNOWLEDGEMENTS Firstandforemost,Iwouldliketogiveaheartfelt,specialthankstomyadvisor,Dr.JianRen. Hehasnotonlyprovidedmewithguidanceforseveralyearsthroughoutmygraduatestudiesat MichiganStateUniversity,hehasalsobeenmotivating,encouragingandatruefriendduringthe process.Withhispatienceandwillingnesstoprovidecontinuoussupport,Dr.Renmadethis journeytowardsaPh.D.possibleforme. Iwouldliketogratefullyandsincerelyacknowledgemymentor,friend,androlemodel,Dr. PercyPierre.Servingasonemycommitteemembers,Dr.Pierrehasbeenthereformesince thestartofmygraduatecareer.Fromacademicsguidancetopersonaldevelopment,Dr.Pierre hasbeenaconstantsupporterandIwillbeforeverinhisdebt.Also,Iwouldliketoexpressmy gratitudetotherestmydissertationcommitteemembers,Dr.SubirBiswasandDr.JonathanHall fortheircomments,suggestions,andtimecommitmentduringthisentireprocess. Lastly,Iwouldliketothankmyparentsandsiblingsfortheirloveandcontinuoussupport duringmylongacademiccareer.Specialthankstomybrother,Dr.LeonardLightfoot,forpaving thewayandconstantlypushingmetogreaterheights.Iwouldliketothankmybeautifuldaughter, AriannLightfoot,forremindingmethatthebattleforgreatnessisbiggerthanmyself.Also,I wouldlikegivemajorthanksmylabmatesandfriends,pastandcurrent,foralwaysproviding mewithadviceandfeedbackonresearchtopics,lifelessonsandformakingmytimeatMSUa memorableandanenjoyableexperience.Lastandcertainlynotleast,Iwouldliketothankmy beautiful,intelligent,encouraging,motivating,loving,supportivefiancée,Dr.AshleyJohnson,for herloveandforalwayskeepingmeontracktoaccomplishmygoalsbypickingmeupwhenIdid notalwayshavethestrengthtodoitmyself. vTABLEOFCONTENTS LISTOFTABLES .......................................ixLISTOFFIGURES .......................................xKEYTOABBREVIATIONS ..................................xiiiCHAPTER1INTRODUCTION ...............................11.1WirelessSensorNetworks ..............................1 1.1.1WhatareWirelessSensorNetworks? .....................1 1.1.2IssueswithWirelessSensorNetworks ....................2 1.1.3LocationPrivacyinWirelessSensorNetworks ................3 1.1.3.1WhyisSource-LocationPrivacyImportantinWirelessSensor Networks? .............................4 1.1.3.2WhyisDestination-LocationPrivacyImportantinWireless SensorNetworks? .........................4 1.2OverviewoftheDissertation .............................4 1.2.1MajorContributions .............................4 1.2.2Structure ...................................5 CHAPTER2SOURCE-LOCATIONPRIVACYPROTECTION ..............62.1LimitationswithExistingSolutions ..........................6 2.1.1LimitationswithExistingSolutionsforSource-LocationPrivacy ......6 2.1.2SummaryofMajorLimitationsforLocationPrivacy ............8 2.2NetworkModelsandDesignGoals ..........................8 2.2.1TheSystemModel ..............................8 2.2.2AdversarialModel ..............................9 2.2.3DesignGoals .................................9 2.3ProposedResearchDirectionsforSLP ........................10 2.3.1DirectionsForSource-LocationProtection ..................10 2.4Source-LocationPrivacyusingRandomlySelectedIntermediateNodes(RSIN)..11 2.4.1ConstrainedRSINScheme ..........................11 2.4.2SecurityAnalysisforRSIN ..........................14 2.4.3TotallyRandomRSINScheme ........................15 2.4.4SecurityAnalysisforTotallyRandomRSIN .................26 2.4.5SimulationResultsandPerformanceComparison ..............27 2.5Source-LocationPrivacywithMixingRing .....................29 2.5.1ConstrainedRSIN ...............................29 2.5.2NetworkMixingRing(NMR) ........................29 2.5.3ForwardingtotheSINK ...........................33 2.5.4SecurityAnalysisforMixingRingRouting .................33 vi2.5.5PerformanceAnalysisandSimulationResults ................36 2.6Source-LocationPrivacyusingSTaRRouting ....................42 2.6.1Preliminary:Source-LocationPrivacyEvaluationModel ..........42 2.6.2STaRRoutingScheme ............................46 2.6.3SecurityAnalysisforSTaRRouting .....................49 2.6.4PerformanceAnalysisandSimulationResults ................53 CHAPTER3DESTINATION-LOCATIONPRIVACYPROTECTION ...........573.1LimitationswithExistingSolutionsforDestination-LocationPrivacy ........57 3.2NetworkModelsandDesignGoals ..........................58 3.2.1TheSystemModel ..............................58 3.2.2TheAdversariesModel ............................59 3.2.3DesignGoals .................................60 3.3ProposedResearchDirectionsforDestination-LocationPrivacy ...........60 3.3.1DirectionsforDestination-LocationPrivacy .................60 3.4Preliminary:Destination-LocationPrivacyEvaluationModel ............60 3.5Destination-LocationPrivacyusingBubbleRouting .................64 3.5.1SecurityAnalysisforBubbleRouting ....................67 3.6DestinationLocationPrivacyusingR-STaRRoutingSchemes ...........69 3.6.1R-STaRRoutingProtocol ...........................69 3.6.2R-STaRRoutingProtocolwithFakeDestinationNodes ...........74 3.6.3R-STaRRoutingProtocolmixwithCost-AwareRouting(CAR) ......76 3.6.4SecurityAnalysisforR-STaRRoutingSchemes ...............77 3.6.4.1FirstRoutingPhase ........................77 3.6.4.2SecondRoutingPhase .......................78 3.6.5PerformanceAnalysisandSimulationResults ................82 CHAPTER4Q-RECHSCLUSTER-BASEDENERGYEFFICIENTROUTINGINWIRE- LESSSENSORNETWORKS .........................854.1Introduction ......................................85 4.2RelatedWork .....................................85 4.3EnergyConsumptionModel .............................87 4.4ProposedQ-ReCHSCluster-BasedRoutingScheme .................87 4.4.1Q-ReCHSNetworkModel ..........................88 4.4.2InitializationStage ..............................89 4.4.3Q-ReCHSCluster-HeadSelectionProcess ..................90 4.4.4SystemsAnalysis ...............................92 4.5SimulationResults ..................................92 CHAPTER5CONCLUSIONANDFUTURERESEARCH ................1035.1ConclusionforSource-LocationPrivacy .......................103 5.2ConclusionforDestination-LocationPrivacy .....................103 5.3ConclusionforCluster-BasedRouting ........................104 5.4FutureWork ......................................104 viiBIBLIOGRAPHY........................................105viiiLISTOFTABLES Table3.1Exampledestinationnodelocationtablewith nf=4...............76 Table3.2TableofvariablesanddescriptionsforanalyzingsecurityoftheproposedR- STaRschemes. ...................................81 ixLISTOFFIGURES Figure2.1IllustrationofRSIN ................................13 Figure2.2IntermediatenodesdistributionforconstrainedRSINscheme ..........15 Figure2.3Messageforwardingthroughintermediatenode(s) ................17 Figure2.4Performanceforsingle-intermediatenode:Powerconsumptionfordifferent packetlengths ...................................18 Figure2.5Performanceforsingle-intermediatenode:Powerconsumptionfordifferent packetgenerationintervals ............................19 Figure2.6Performanceforsingle-intermediatenode:Messagelatencyfordifferentpacket lengths.......................................20 Figure2.7Performanceforsingle-intermediatenode:Messagelatencyfordifferentpacket generationintervals ................................21 Figure2.8Performanceforsingle-intermediatenode:Messagedeliveryratiofordiffer- entpacketlengths .................................22 Figure2.9Performanceforsingle-intermediatenode:Messagedeliveryratiofordiffer- entpacketgenerationintervals ..........................23 Figure2.10Performanceforsingle-intermediatenode:Powerconsumptionfordifferent lengthofrandompath ...............................24 Figure2.11Performanceforsingle-intermediatenode:Messagelatencyfordifferentlength ofrandompath ...................................25 Figure2.12Performanceforsingle-intermediatenode:Messagedeliveryratiofordiffer- entlengthofrandompath .............................26 Figure2.13GridsFormation ..................................28 Figure2.14Illustrateofthefirsttwophasesrouting ......................30 Figure2.15Messagetransmissioninthering .........................32 Figure2.16Ringselectioninsimulationsetup .........................35 Figure2.17MixingRing:Powerconsumptionofnormalnodes ...............37 xFigure2.18MixingRing:Powerconsumptionofringnodes .................38 Figure2.19MixingRing:Messagelatency ..........................39 Figure2.20MixingRing:Messagedeliveryratio .......................40 Figure2.21DistributionoftheSTaRarea ...........................47 Figure2.22RoutingillustrationoftheSTaRprotocol .....................50 Figure2.23ThesourcelocationanalysisofSTaRroutingscheme ..............52 Figure2.24PerformanceofSTaRrouting:Powerconsumption ................54 Figure2.25PerformanceofSTaRrouting:Messagelatency .................55 Figure2.26PerformanceofSTaRrouting:Messagedeliveryratio ..............56 Figure3.1IllustrationoftheBubbleRouting .........................64 Figure3.2IllustrationoftheroutingformessagesintheDEEPscheme ...........68 Figure3.3DistributionoftheR-STaRarea ..........................70 Figure3.4CircleGridLayoutNetworkEnvironmentwithradius RN............79 Figure3.5IllustrationforanalyzingthesecuritystrengthusingR-STaRrouting ......80 Figure3.6MessageLatency .................................83 Figure3.7EnergyConsumption ...............................84 Figure4.1Q-ReCHSNetworkRegions:100nodes,100mx100m,BSlocated(50m,50m)89 Figure4.2SimulationNetworkEnvironment:100nodes,100mx100m,BSlocated (50m,50m).....................................93 Figure4.3100Nodesin100mx100mEnvironment:First-To-Die .............94 Figure4.4100Nodesin100mx100mEnvironment:Half-To-Die .............95 Figure4.5100Nodesin100mx100mEnvironment:Last-To-Die .............96 Figure4.6150Nodesin150mx150mEnvironment:First-To-Die .............97 Figure4.7150Nodesin150mx150mEnvironment:Half-To-Die .............98 Figure4.8150Nodesin150mx150mEnvironment:Last-To-Die .............99 xiFigure4.9200Nodesin200mx200mEnvironment:First-To-Die .............100 Figure4.10200Nodesin200mx200mEnvironment:Half-To-Die .............101 Figure4.11200Nodesin200mx200mEnvironment:Last-To-Die .............102 xiiKEYTOABBREVIATIONS DDIDestination-locationDisclosureIndex DLPDestination-LocationPrivacy DSIDestination-locationSpaceIndex NDSINormalizedDestination-locationSpaceIndex NMRnetworkmixingring NSSINormalizedSource-locationSpaceIndex Q-ReCHSQuad-RegionClusterHeadSelection R-STaRReverse-SinkToroidalRegion RSINRoutingtoaSingleIntermediateNode SDISource-locationDisclosureIndex SLPSource-LocationPrivacy SSISource-locationSpaceIndex STaRSinkToroidalRegion TTLTime-To-Live WSNsWirelessSensorNetworks xiiiCHAPTER1 INTRODUCTION 1.1WirelessSensorNetworks 1.1.1WhatareWirelessSensorNetworks? Awirelesssensornetwork(WSN)isanetworkofsensornodes(devices)thatareconnected throughsharedwirelesscommunicationmediums.Thesesensornodescanbeusedtomonitor environmentalactivities,suchastemperature,movement,sound,pressure,etc.Asensornodeis madeupofmanypartsincludingaradiotransceiver,amicrocontroller,andanenergysource,typ- icallyabatteryoranembeddedenergyharvestingtechnique.Thesize,cost,andcapabilitiesof sensornodescanvaryandallhavetrade-offs.Forinstance,ifyouwanttouserelativelycheap sensornodesinthenetwork,therewillbeatrade-offincapabilities,suchascomputationalspeed, memory,transmittingrange,andsecurity(e.g.cryptographic-system"cryptosystem").Alterna- tively,ifyouwanttousesensornodeswithmanycapabilities,therewillbeatrade-offinsizeand cost,suchasusingalargerbatteryandapricermicrocontroller. Asensornodeinthenetworkthathasdetectedanactivityintheenvironmentandhasamessage (packet)totransmit,werefertothatnodeasthesourcenode,andthenodeinthenetworkthatthe messageisintendedfor,werefertothatnodeasthesinknode,destinationnodeorbasestation (BS).Thesourcenodeforwardsmessagestothesinknodewirelesslythroughthenetworkusing multi-hoproutingtechniques.Someofthemostpopularmulti-hoproutingtechniquesareflooding- baseroutingandshortest-pathroutingalgorithms.Inflooding-basedroutingalgorithm,thesource nodewillforwardthemessagetoeachneighbornode(nodeswithinthetransmissionrange)and eachreceivingnodewillforwardthemessagetoeachofitsneighborsuntilthemessagereaches allconnectednodesinthenetwork,hencefloodingthenetworkwiththemessage.Inshortest-path 1routingalgorithm,thesourcenodeforwardsthemessageontheshortest-path(intermsofhop counts)tothesinknode. 1.1.2IssueswithWirelessSensorNetworks Wirelesssensor(WSNs)relyonwirelesscommunications,whichisbynatureabroadcastmedium andismorevulnerabletosecurityattacksthanitswiredcounterpartduetolackofaphysical boundary.Jammingorradiointerferenceattackscanbeperformedonthenetworkbyanadversary emittingsignalstojamthesharedwirelesschannelofthenetwork. Sensorsinthenetworkaremeanttobelow-costandenergyefficientdevices.Theyaredesigned tobedeployedinenvironmentswheretheycanbedamagedordestroyed;thus,thecostofthese sensornodesshouldbeataminimum.Clientscansimplydeploymanywirelesssensornodesinto anenvironmentandmonitortheactivitiesintheenvironmentfromonecentrallocation.Sensor nodesarealsobuilttobeplacedinenvironmentswheretheycanbeunattendedforlengthyperiods oftime.Thesesensorsmaybedeployedinareaswhereitisimpracticalforhumanstoattendand maintainthesensors,thus,changingorrechargingthebatteriesinthesensordevicesisinfeasible. Forthepurposeofpreservingbatterylife,usingintensivecryptographicalgorithms,suchaspublic- keycryptosystems,andtheusageofpowerfultransmittersarenotsuitableforWSNs. Oneofthefocusesofthisdissertationiscluster-basedenergy-awareroutingprotocolstomax- imizetonetworklifetime.Thisfocusisstrictlyonenergy-efficientrouting.Oneoftheusageof WSN’sistoprovidereal-timeeventmonitoringfunctionality.Todoitsjob,thedeviceenergymust beahighpriorityforthesedevicestoperformitsfunctionality. Theotherfocusofthisdissertationisonsecurityforlocation-privacyusingenergy-efficient routingtechniques.Privacyhasbeenanextensivelystudiedtopicinwirelesssensornetworks. OneofthemajorandunsettledissuesinprivacyofWSNsishowtoprovideadequaterouting-based location-privacy.Privacyinanetworkconsistsofnotonlytheprivacyofthemessagecontentbut alsotheprivacyofthenodeslocationprivacy. 21.1.3LocationPrivacyinWirelessSensorNetworks Securityattacks,suchas,privacythreatshavebeenanextensivelystudiedtopicinWirelessSensor Networks(WSNs).Privacythreatscanbeclassifiedintotwocategories:(i)Content-basedprivacy threats,and(ii)Context-basedprivacythreats.Content-basedprivacythreatsrelatetoprotect- ingthecontentofthemessageandcanbeprotectedusingcryptographicencryptionalgorithms. Context-basedprivacythreatsrelatetomonitoringthetransmissionofthedata(i.e.Eavesdropping andlocalizationattacks).Forinstance,anadversarymaybeabletoanalyzethetrafficpatternsby monitoringthetransmissionofthedatausingradiofrequencylocalizationtechniques.Unfortu- nately,usingcryptographictechniquesdoesnotprovideprotectionforcontext-basedthreatsand presentsamuchgreaterchallengetosolve.Inthisdissertation,wewillfocusononeparticular context-basedthreat,routing-basedlocationprivacy. Whenmessagesaretransmittedwirelesslyintheopenair,anycompatiblereceiverswithinthe transmissionrangeofthesenderisabletointerceptthetraffic.Anadversarymaybewell-equipped withpowerfultransceiverstoanalyzethetrafficpatterns.Theymaybeabletointercepttrafficfrom oneormultiplelocationswithinthenetworkenvironment.Withoutanadequateprotectionofthe routingpaths,anadversarymaybeabletoperformcontext-basedattacksonthenetwork.An adversarymaybeabletodeterminetheanodelocationbyusingradiofrequency(RF)localization techniquestolocatethesourceand/ordestinationnodelocationinahop-by-hopapproach.The confidentialityofthemessagecontentcanbeprotectedbyencryptionandauthentication[1–12, 12–25]butthelocationofthesourceand/orsinkcanbeexposedinroutingpatterns.Tobemore concise,theremaybedifferenttypesofinformationbesidesthemessagecontentthatarelinked withamessagetransmission.Therefore,evenifapowerfulencryptionalgorithmisusedtoprotect nodesidentities,theadversarymaystillbeabletodeterminethelocationofthesourceand/orsink nodebymonitoringthetrafficpatternsandroutingpaths. Indevelopingroutingschemestoaddresstheissueforlocationprivacy,theroutingschemes mustbeenergy-efficientduetothelimitedenergysupplyonthesensordevices.Therefore,energy 3consumptionalongwithlocationprivacyaretwoveryvitalcomponentsforthesuccessfuldeploy- mentofwirelesssensornetworks.Inthisdissertation,weproposeroutingschemesthataddress thelocationprivacyissuebyusinguniqueroutingprotocols. 1.1.3.1WhyisSource-LocationPrivacyImportantinWirelessSensorNetworks? ThePanda-HunterGamethatwasintroducedin[26,27],createdinterestforprovidingasecure source-locationprivacyinWSNs.InthePanda-HunterGame,awirelesssensornetworkisde- ployedinahabitattomonitorthelocationofapanda.Thesensorsareusedtolocatethegeneral areaofthepanda.Assoonasthepandaisdiscovered,thecorrespondingsourcenodewillobserve andreportdataperiodicallytotheSINKnode.However,thesourcelocationshouldbekeptsecure fromillegalhunterswhomaytrytotrackandlocatethepanda.Thegoalistomakeitinfeasiblefor thehunterstodeterminethelocationofthepandabyanalyzingthetrafficpatternsinthenetwork. 1.1.3.2WhyisDestination-LocationPrivacyImportantinWirelessSensorNetworks? WirelessSensorNetworkscanbedeployedformilitaryintelligencenetworks.Onabattlefield, soldierscanbeequippedwithsensordevices,inwhichmessagesareroutedtoadestinationbase stationthatislocatedwithinthebattlefield.Todestroythisnetwork,enemiesofsoldierscan simplydestroythedestinationbasestation.Forthesafetyofthesoldiersthataremonitoringthe destinationbasestation,thelocationofthedestinationmustremainunexposedasmessagesare routedthroughthenetwork.Therefore,inmilitaryintelligencenetworks,boththedestination- locationandthemessagecontentmustbeprotected. 1.2OverviewoftheDissertation 1.2.1MajorContributions Themajorcontributionsofthisdissertationarethefollowing: 4•Wedeveloptoprotectthesource-locationprivacythroughatwo-phaseroutingprocess. –Source-locationprivacythroughroutingtoasingleRandomlySelectedIntermediate Node(RSIN). –Source-locationprivacythroughusingSTaRrouting. •Wedevelopsource-locationprivacythroughanetwork-levelmixingring. •WedevisenetworkimplementationcriteriaforsourcenodeprivacyprotectioninWSNs. •Wedeveloptoprotectthedestination-locationprivacythroughatwo-phaseroutingprocess. –Destination-locationprivacyusingBubblerouting. –Destination-locationprivacyusingR-STaRrouting. –Destination-locationprivacyusingR-STaRwithFakeDestinationNodes. –Destination-locationprivacyusingR-STaRmixwithCost-AwareRouting. •Wedesignedcluster-basedenergy-awareroutingschemeusingQ-ReCHSalgorithm. •Weprovideextensivesimulationresultsunderns-2andMATLABfortheproposedrouting protocols.1.2.2Structure Thedissertationisstructuredasfollows: •ChapterII introducestheschemesforsource-locationprivacyprotection. •ChapterIII introducestheschemesfordestination-locationprivacyprotection. •ChapterIV introducesthecluster-basedroutingschemes. •ChapterV summarizesthedissertation. 5CHAPTER2 SOURCE-LOCATIONPRIVACYPROTECTION 2.1LimitationswithExistingSolutions 2.1.1LimitationswithExistingSolutionsforSource-LocationPrivacy Inthepasttwodecades,originatedlargelyfromChaum’smixnet[28]andDC-net[29],anumber ofsource-locationprivacycommunicationprotocolshavebeenproposed[27,30–59].Themixnet familyprotocolsuseasetof"mix"serversthatblendsreceivedpacketstomakethecommunication source(includingthesenderandtherecipient)ambiguous.Toaccomplishtheambiguitybetween thesendersandrecipients,theschemesusesstatisticalpropertiesofbackgroundtraffic.TheDC- netfamilyprotocols[29,32,33]utilizesecuremultipartycomputationtechniques.However,both approachesrequirepublic-keycryptosystemsandarenotsuitableforWSNs. Multipleschemeswereproposedtoprovidedestinationlocationprivacy.In[36,37],base stationlocationprivacybasedonmulti-pathroutingandfakemessagesinjectionwasproposed.In thisscheme,everynodeinthenetworkshastotransmitmessagesataconstantrate.Anotherbase stationlocationprivacyschemewasintroducedin[60],whichinvolveslocationprivacyrouting andfakemessageinjection.Inthisdissertation,wewilladdressthesource-locationprivacyin wirelesssensornetworks. In[38,39],source-locationprivacyisprovidedthroughbroadcastingthatmixesvalidmessages withdummymessages.Themainideaistohaveeachnodetransmitmessagesconsistently.In otherwords,wheneverthereisnovalidmessage(ornoeventdetected),thenodehastotransmit dummymessages.Thetransmissionofdummymessagesnotonlyconsumessignificantamount ofsensorenergy,butalsoincreasesthenetworkscollisionsanddecreasesthepacketdeliveryratio. Therefore,theseschemesarenotquitesuitableforlargescalesensornetworks. 6Dynamictwo-phaseroutingbasedprotocolscanalsoprovidesource-locationprivacytomake itinfeasibleforanadversarytotracebacktothesource-locationthroughtrafficmonitoringand analysis.Themainideaisto,first,routethemessagetoarandomnodethatisawayfromthe actualmessagesourcenodeduringthefirstphase.ThenforwardthemessagetotheSINKnode usingsinglepathroutingduringthesecondphase.However,boththeoreticalandpracticalresults demonstratethatifthemessageisroutedrandomlyfor hhops,thenthemessagewillbelargely withinh/5hopsawayfromtheactualsource, Tosolvethisproblem,severalapproacheshavebeenproposed.Inphantomroutingprotocol, introducedin[27,40],themessagefromtheactualsourcewillberoutedtoaphantomsourcealong adesigneddirectedwalkthrougheithersector-basedapproachorhop-basedapproach.Takethe sector-baseddirectedwalkasanexample,thesourcenodefirstrandomlydeterminesadirection thatthemessagewillbesentto.Thedirectioninformationisstoredintheheaderofthemessage,in which,everyforwarderontherandomwalkpathwillforwardthismessagetoarandomneighbor inthesamedirectiondeterminedbythesourcenode.Inthisway,thephantomsourcecanbeaway fromtheactualsource.Unfortunately,oncethemessageiscapturedontherandomwalkpath, theadversarieswillbeabletogetthedirectioninformationstoredintheheaderofthemessage. Therefore,theexposureofdirectioninformationdecreasesthecomplexityforadversariestotrace backtotheactualmessagesourceinthemagnitudeof2 h.Randomwalkfromboththesource nodeandtheSINKnodewasalsoproposedin[41].Inthisscheme,BloomFilterwasproposed tostoretheinformationofallthevisitednodesinthenetworksforeachmessagetopreventthe messagesfromhoppingback.However,thisdesignallowstheadversariestorecoversignificant routinginformationfromthereceivedmessages.Infact,thisdesignisimpracticalforlargescale sensornetworks.Inthischapter,wewillproposeseveraldynamicroutingbasedprotocolsthat solvesthevulnerabilitiesofthediscussedexistingschemes. 72.1.2SummaryofMajorLimitationsforLocationPrivacy •Public-keybasedschemesarenotsuitableforlocationprotectioninWSNsduetothehigh computationandcommunicationoverhead. •Broadcastingbasedlocationprotectionschemesareenergyinefficient. •Dynamicroutingbasedsource-locationprotectionschemesarethemostpromisingbutmany vulnerabilitiesexposedintheexistingschemes. 2.2NetworkModelsandDesignGoals Togetabetterunderstandingofthenetwork,inthissectionwewillprovidethesystemmodeland adversarialmodeltocapturetherelevantfeaturesofWSNsandpotentialadversariesinlocation privacyapplications. 2.2.1TheSystemModel Thefollowingassumptionsaremadeaboutthesystem: •Thenetworkisdividedintogrids.Thesensornodesineachgridarefullyconnected.In eachgrid,thereisoneheadernoderesponsibleforcommunicatingwithothernearbyheader nodes.Thewholenetworkisfullyconnectedthroughmulti-hopcommunications[61–64]. •Everynodeinthenetworkcanbecomeasourcenodeonadetectionofanevent.Ondetecting anevent,asensorsourcenodewillgenerateandsendmessagestothedestinationnode throughamulti-hoprouting. •EachmessagewillincludeauniquenodeIDwheretheeventwasgenerated.TheSINK (destination)nodecanonlydeterminesourcenodelocationbasedoffthenodeID. •Thesensornodesareassumedtoknowtheirrelativelocationanddestinationnodelocation. Wealsoassumethateachsensornodehastheknowledgeofitsadjacentneighboringnodes. 8Theinformationabouttherelativelocationofthesensordomainmayalsobebroadcasted throughthisnetworkforroutinginformationupdate[65,66]. •Thekeymanagement,includingkeygenerations,keydistributionandkeyupdate,isbeyond thescopeofthisdissertation.However,theinterestedreadersarereferredtoreferencessuch as[8,24,67,68]. 2.2.2AdversarialModel Theadversarieshavethefollowingcharacteristics: •Well-equipped: Theadversarydoesnotneedtoworryabouttheenergyconsumption.The adversaryalsohasadequatecomputationcapability.Ondetectinganeventmessage,hecould determinetheimmediatesenderofthismessagebyanalyzingthestrengthanddirectionof thesignalhereceived.Heisabletomovetothissender’slocationwithoutmuchdelay.If needed,theadversarycancompromisesensornodesinthenetwork. •Passive: Theadversariescarryoutsomepassiveattacks,whichonlyinvolveeavesdropping work. •Traffic-monitoring: Weassumethattheadversaryisunabletomonitortheentirenetwork fromonecentrallocation.Theadversaryisabletomonitorthetrafficinanareathatiswithin one-hoptransmissionrange. 2.2.3DesignGoals Ourdesigngoalscanbesummarizedasfollows: •Theadversariesshouldnotbeabletodeterminesourcelocationinformationbyanalyzing thetrafficpattern. 9•Theadversariesshouldnotbeabletogetthelocationofthesourceeveniftheyareableto monitoracertainareaofthesensornetworkandcompromiseafewnetworknodes. •Onlythesinknodeisabletoidentifythesource-locationwiththemessagesreceived.The recoveryofthesource-locationfromthereceivedmessageshouldbeveryefficient. •Thelengthofeachmessageshouldbeasshortaspossibletosavetheprevioussensornode power.Thisisbecausethatonaverage,transmissionofonebitconsumesaboutasmuch powerasexecuting800-1000instructions[69]. 2.3ProposedResearchDirectionsforSLP 2.3.1DirectionsForSource-LocationProtection Inthisdissertation,weproposetoaddressthesource-locationprivacythroughdynamicrouting schemes.Therearethreeschemesintroducedinthisdissertation. Inthefirstroutingscheme,themessagesourcerandomlyselectsanintermediatenode(RSIN) inthesensordomain,andthentransmitsthemessagetotherandomlyselectedintermediatenode beforethemessageistransmittedtotheSINKnode.Theintermediatenodeisexpectedtobe awayfromthesourcenodeareainthesensordomain.Ouranalysisshowsthatthisschemecan providegreatlocalsource-locationprivacy.However,itmaynotbeabletoprovideadequateglobal source-locationprivacy. Tofurtherimprovetheperformanceofglobalsecurity,thesecondroutingschemeusinga three-phaseroutingprocess.Inthefirstphase,eachmessageistransmittedtoarandomlyselected intermediatenode.Thisphaseprovidesthelocalsource-locationprivacy.Inthesecondrouting phase,thedatapacketwillberoutedfromtherandomlyselectedintermediatenodetoanetwork mixingring(NMR).Thisphaseoffersnetwork-level(global)source-locationprivacy.Inthelast phase,thedatapacketwillbeforwardedtotheSINKnodefromspecificnodeswithinthemixing ring.10Thethirdschemeachieveglobalsource-locationprivacybyroutingthroughanintermediate nodefromapre-determinedregionlocatedaroundtheSINKnode.WecallthisregiontheSink ToroidalRegion(STaR).Fromtherandomintermediatenode,themessagewillberoutedtothe SINKnodethroughtheshortestpathrouting.TheSTaRroutingmethodisperformedforevery messagethesourcenodegenerateandsendtotheSINKnode.Foreachoftheroutingschemes, bothsecurityanalysisandsimulationresultsareprovided. 2.4Source-LocationPrivacyusingRandomlySelectedIntermediateNodes (RSIN)Inthissection,wewilldescribetheproposeRSINscheme.Also,wewillprovideanalytical performanceoftheschemethroughsimulations. 2.4.1ConstrainedRSINScheme TheRSINroutingprotocolwilluseatwo-phaseroutingtechnique.Inthefirstphase,thesource nodewillrouteeachmessagethroughanintermediatenode,whichwillbeselectedrandomly withinthenetwork.Tosolvesomeofthevulnerabilitiesoftheexistingschemes,theintermediate nodeshouldbeaminimumdistancefromthesourcenodebasedonitsrelativelocationwithin thenetworkenvironment.Werefertothisminimumdistanceas dmin.Werefertothedistance betweenthesourcenodeandtherandomlyselectedintermediatenodeas drand .Therefore,forthe intermediatenodetobeminimumdistanceof dminfromthesourcenode,wewillneed drand dmin.Forasourcenodetogenerate drand ,itfirstgeneratesarandomvariable xthatnormallydis- tributedwithmean0andvariance 2,i.e., XN(0,).Withtherandomvariable xdetermined,thesourcenodecancalculate drand asfollows: drand =dmin×(|x|+1).11Therefore,theprobability[70]that drand islocatedintheinterval [dmin,dmin)is:20,2(−1)−1=212e−(−1)222−1=2−1−1,whereisaparameterlargerthan1, 0,2istheprobabilitydensityfunctionofGaussiandis- tribution[71].Ifwechoose tobe1.0,thentheprobabilitythat drand fallswithintheinterval [dmin,2dmin)willbe2 (11)−1=0.6827.Theprobabilitythat drand isintheinterval [dmin,3dmin)willbe2 (21)−1=0.9545.Afterdrand isdetermined,thesourcenoderandomlygeneratesanintermediatenodelocatedat (xd,yd)thatsatisfies: drand =(xd−x0)2+(yd−y0)2dmin.Sinceweassumethateachsensornodeonlyhasknowledgeofitsadjacentnodes,thesourcenode maynothaveaccurateinformationofsensornodesmultiplehopsaway.Inparticular,therandomly selectedintermediatenodelocation (xd,yd)maynotevenexistinthenetworkenvironment.How- ever,theknowledgeofrelativelocationguaranteesthatthemessagepacketwillbeforwardedtoan intermediatenodelocatedwithminimumdistance dminawayfromthesourcenode.Accordingto ourassumption,thelastnodeintheroutingpathadjacenttotheintermediatenodewillbeableto tellwhethersucharandomlyselectedintermediatenodeexistsornot.Inthecasethatsuchanode doesnotexist,thisnodewillbecometheintermediatenode,inwhich,thisnodewillthenroute thereceivedmessagetotheSINKnode.Uponreceivingadatamessage,theintermediatenode forwardsthemessagetotheSINKnode. IntheexplanatoryexamplegiveninFigure2.1, S1,S2denotetwosourcenodesinthesensor network, DrepresentstheSINKnodeand I1,···,I6aresixrandomlyselectedintermediatenodes thatmeettheconstrainedrequirement.Theselectionof drand guaranteesthatnoneoftheinter- mediatenodeswillbelocatedintheshadedareas.Thenodes I1,···,I6willforwardthemessages M1,···,M6totheSINKnode,respectively. 122I1I3I4I5I6I1S2SD1M2M3M6M5M4MFigure2.1IllustrationofRSIN 132.4.2SecurityAnalysisforRSIN IntheconstrainedRSINscheme,theintermediatenodelocationisrandomlydeterminedbythe sourcenodebasedonitsrelativelocationwithinthesensordomain.Fromprobabilitypointofview, everynodeoutsideoftheminimumdistance dminradiusfromthesourcenodecanbeselectedasthe intermediatenode.However,sinceweassumethatthesourcenodedoesnothavefullknowledge ofsensornodesmorethanonehopawayfromitself,theintermediatenodeselectedbythesource nodemaynotevenexist. Itisimpossiblefortheadversarytotraceoridentifytherealmessagesourcenodebasedon anindividualtrafficmonitoring.Thisisbecause(i)thismessageisequallylikelytobegenerated bymanypossiblesources,and(ii)theprobabilityformultipleeventsfromthesamesourcetouse repeatedroutingpathisverylowforlargescalesensornetworks. Ifanadversarytriestotracethesource-locationfromamessagepacketintheroutethrough whichthepacketisbeingtransmitted,thentheadversarywillbeledtotherandomlyselected intermediatenode,insteadoftherealmessagesource.Sincetheintermediatenodeisrandomly selectedforeachdatamessage,theprobabilitythattheadversarieswillreceivethemessagesfrom onesourcenodecontinuouslyisvirtuallyzeroinalargescalenetwork. AsshowninFigure2.1,ifanadversaryreceives M2forwardedfrom I2,theadversarywillbe luredtothedirectionof I2,whichisquiteawayfromtheactualsourcenode S1.Whileformessage M3transmittedfromtheintermediatenode I3,sinceitisfarawayfrom I2,theprobabilityforthe adversarytoreceive M3isclosetozeroaccordingtotheassumption. Thisexampleshowsthatevenifthelocationofoneintermediatenodeisdiscoveredbyan adversary,thesource-locationisstillatleast dminawayfromtherealsourcenode.Therefore,if dminisappropriatelyselected,thesource-locationcanstillbewellprotected. Unlikethedirectedwalkinphantomrouting,ourprotocoldoesnotleaksideinformationinthe headertotheadversaries.Sincetheintermediatenodeisdeterminedbeforeeachdatamessageis transmittedbythesource,thedatamessagecarriesnoobservablesideinformationofthemessage 14Figure2.2IntermediatenodesdistributionforconstrainedRSINscheme source-locationinitscontentduetomessagecontentencryption.Therefore,ourproposedprotocol canprotectsource-locationprivacy. 2.4.3TotallyRandomRSINScheme AlthoughtheconstrainedRSINschemeworkswellinsomescenarios,itslimitationisthatthe probabilityforanintermediatenodetobeselectedisproportionaltothedistancefromthesource node.Therefore,forlargescalesensornetworks,theintermediatenodestendtoberelativelyclose tothesourcenode.Inotherwords,theintermediatenodesarehighlylikelytobeconcentratedinan areasurroundingthesourcenode,butwithminimumdistance dminfromthesource,asillustrated inFigure2.2.Inthissimulationexample,wehaveanetworkenvironmentsizeof5000 ×5000meters.Wesetthesourcenodeislocatedat (−1250,1250)andtheSINKnodelocatedat (0,0).15Also,wesettheminimumdistancetobe dmin=250.Werandomlyselected500intermediate nodeslocationaccordingtotheconstrainedRSINschemeasdescribedinSection2.4.1with equalto1.Itcanbeseenthatallintermediatenodesaredistributedaroundthesourcenode.When thesenodesforwardmessagestotheSINKnode.Theadversariesmayverylikelybeabletolocate thesub-areaofintermediatenodessinceallmeassagesareroutedfromthesub-areaasshownin Figure2.2.Therefore,forlargescalesensornetworks,theconstrainedRSINschememaynot beabletoprovideadequateglobalsource-locationprivacybutdoesprovidelocalsource-location privacy. Inordertoprovidegloballocationprivacyoverthesensornetworks,theselectionofinterme- diatenodeshastobetotallyrandom,i.e.,everysensornodeinthenetworksshouldbeequally likelytobeselectedasanintermediatenodebyallpossiblesourcenodes.Ontheotherhand,ifthe selectionistotallyrandom,someintermediatenodescanbeneartherealsourcenode.Fortunately, theprobabilityforthisisverylowforlargescalesensornetworks.Nevertheless,topreventthis fromhappening,intotallyrandomRSINscheme,theintermediatenodesisrequirestobeatleast dminawayfromtherealsourcenode. AlthoughtotallyrandomRSINschemecanachievegloballocationprivacy,italsohassome limitations:•Thelengthofaroutingpathtendstobetoolong.Forinstance,inFigure2.3, S,D,Iarethesourcenode,SINKnodeandintermediatenode,respectively.Thedistancebetween S,DandI,Daredandb,respectively.Therefore,ifamessageistransmittedthrough I,thetotal lengthoftheroutingpathisnearly d+2b,whichismuchlongerthan d.Asaresult,this routingmayconsumetoomuchenergy. •Themessagedeliveryratiomaydecreaseduetoincreaseoftheroutinglength. •Alongsingleroutingpathmayallowadversariestodeduceinformationofthesource- location.Taketheroutingpathfrom StoIinFigure2.3asanexample,onceapacketis 163I2I1IFigure2.3Messageforwardingthroughintermediatenode(s) capturedbyadversariesen-route,theadversariesmaygetthedirectionofthesource-location accordingtotransmissiondirectionofthecapturedpacket. 171011020.40.50.60.70.80.911.1Length of every packet / BytesEnergy / JoulephantomConstrained RSINtotally randomTotally random RSINno intermediate nodeFigure2.4Performanceforsingle-intermediatenode:Powerconsumptionfordifferentpacket lengths18101000246810121416Packets generation interval / secondsEnergy / JoulephantomConstrained RSINtotally randomTotally random RSINno intermediate nodeFigure2.5Performanceforsingle-intermediatenode:Powerconsumptionfordifferentpacket generationintervals 191011020.020.030.040.050.060.070.080.090.1Length of every packet / BytesDelay / secondsphantomConstrained RSINtotally randomTotally random RSINno intermediate nodeFigure2.6Performanceforsingle-intermediatenode:Messagelatencyfordifferentpacketlengths 20101000.020.040.060.080.10.120.140.160.18Packets generation interval / secondsDelay / secondsphantomConstrained RSINtotally randomTotally random RSINno intermediate nodeFigure2.7Performanceforsingle-intermediatenode:Messagelatencyfordifferentpacketgener- ationintervals 211011020.99650.9970.99750.9980.99850.9990.99951Length of every packet / BytesDelivery RatiophantomConstrained RSINtotally randomTotally random RSINno intermediate nodeFigure2.8Performanceforsingle-intermediatenode:Messagedeliveryratiofordifferentpacket lengths22101000.970.9750.980.9850.990.99511.005Packets generation interval / secondsDelivery RatiophantomConstrained RSINtotally randomTotally random RSINno intermediate nodeFigure2.9Performanceforsingle-intermediatenode:Messagedeliveryratiofordifferentpacket generationintervals 231011020.50.60.70.80.91Length of every packet / BytesEnergy / JouleFigure2.10Performanceforsingle-intermediatenode:Powerconsumptionfordifferentlengthof randompath 241011020.030.0350.040.0450.050.0550.060.065Length of every packet / BytesDelay / secondsFigure2.11Performanceforsingle-intermediatenode:Messagelatencyfordifferentlengthof randompath 251011020.99860.99880.9990.99920.99940.99960.99981Length of every packet / BytesDelivery RatioFigure2.12Performanceforsingle-intermediatenode:Messagedeliveryratiofordifferentlength ofrandompath 2.4.4SecurityAnalysisforTotallyRandomRSIN UnlikeconstrainedRSINscheme,intotallyrandomRSINscheme,theintermediatenodesthat areselectedinthesensornetworkareevenlydistributed.Everynodeoutsideofthe dmininthe networkshasthesamepossibilityofbeingselectedastheintermediatenode.Themessagescanbe forwardedtotheSINKnodefromallpossibledirections.Evenifthelocationofoneintermediate nodeissuccessfullyidentified,thesource-locationisstillatleast dmindistanceaway.Therefore, thegloballocationprivacyisachieved. 262.4.5SimulationResultsandPerformanceComparison Toevaluatetheperformanceofourpropose’constraintRSIN’and’totallyrandomlyRSIN’,we conductsimulationsusingns-2onRedHatLinuxsystem.Inthesimulation,400nodesaredis- tributedinanareaofsize3360 ×3360meters.TheSINKnodeislocatedatthecenterofthe network. SimulationresultsareprovidedinFigure2.4,2.6,2.8,2.10,where(a),(c),(e)illustratethe relationshipbetweenperformanceandthepacketlengths,(b),(d),(f)showperformancewithdif- ferentpacketgenerationintervals,(g),(h),(i)showperformancewithdifferentlengthofrandom path.Forthesimulationfigures,’totallyrandom’representaschemethatissimilartototallyran- domRSINbutwithoutrestrictionto dminforintermediatenodelocationselection.Let’phantom’ representthephantomroutingdiscussedintherelatedworksection. Forsimulationresultsfrom(a)to(f),weset dmin=480metersforconstrainedRSINandtotally randomRSINschemes.Thesimulationshowsthatafterfourhops,theaveragedistancebetween thephantomsourcenodeandtherealsourcenodeforphantomroutingis526.12meters.Whilefor constrainedRSINscheme,theaveragedistancebetweentheintermediatenodeandthesourceis 529.14meters.Forsimulationresultsfrom(g)to(i), R1,R2,R3forphantomroutingcorresponds to526.12meters,783.60meters,and1042.20metersonaveragebetweenthephantomsourcenode andtherealsourcenode,respectively.ForconstrainedRSIN, R1,R2,R3correspondsto529.14 meters,786.51meters,and1049.46metersonaveragebetweentheintermediatenodeandthe sourcenode,respectively. Throughanalysisandsimulationresults,wehave2findings:(i)Directroutingwithoutinterme- diatenodehasthebestperformance;(ii)ConstrainedRSINandphantomroutinghavecomparable performance,whileconstrainedRSINschemeprovidesbetterlocationprivacyprotectiondueto nodirectionexposureintheheader. 27NormalNode NormalRingNode RelayRingNode SINKFigure2.13GridsFormation 282.5Source-LocationPrivacywithMixingRing Inthissection,weproposeathree-phaseroutingprotocoltoprovidesource-locationprivacy.The firstphase(constrainedRSIN),whichhasbeenintroducedinthelastsection,provideslocalsource- locationprivacy.Thesecondphase(NMR)offersthenetwork-levelsource-locationprivacy.The lastphaseforwardsthemessagetotheSINKnode. Aftertheformationofallthegrids,alargering,calledthe mixingring ,isgeneratedintheWSN toprovidenetwork-leveltrafficmix.Themixingringiscomposedofmultipleheadernodes,which arenamed ringnodes .Theringnodesarefurtherdividedinto relayringnodes andnormalring nodes.Themessagesthatwillbetransmittedinthemixingringarereferredtoas vehiclemessages .Vehiclemessageswillbetransmittedintheringintheclockwisedirection,called ringdirection .Onlyrelayringnodescangeneratevehiclemessage.Wealsodefinethegridscontainingringnode asringgrids ,thegridswithoutringnodesas normalgrids .Thesensornodesinnormalgridsare definedas normalnodes ,themessagessentbythenormalnodesarereferredas datamessages .2.5.1ConstrainedRSIN Inthisphase,themessagewillbeforwardedtoanintermediatenodeinthesamewayasthe constrainedRSINintroducedinthelastsection.Thenthemessagewillbeforwardedtothenearest ringnodebythisintermediatenode. AnexampleisgiveninFigure2.14,where Sindicatesasourcenodeinthenetworkand I1,I2,I3arethreeintermediatenodes.Theselectionof drand guaranteesthatnoneoftheintermediatenodes willbeintheshadedarea.Then I1,I2,I3willforwardthesemessages M1,M2,M3totheringnodes R1,R2,R3,respectively. 2.5.2NetworkMixingRing(NMR) Inthesecondroutingphase,themessageswillbeforwardedhop-by-hopinthering.Themessage canhopalongtheringdirectionforarandomnumberoftimesbeforeitisbeingtransmittedtothe 29mindSmind1I2I3I3M2M1M2R1R3RFigure2.14Illustrateofthefirsttwophasesrouting 30SINKnode. Thisroutingprocessprovidessource-locationprivacythatresemblestheairportterminaltrans- portationsystem.Themessagetransmissionintheringactsasanetwork-levelmix.Aslongas itisinfeasibleforanadversarytodistinguishthemessageinitiatorfromthemessageforwarderin themixingring,thenitwouldbeinfeasiblefortheadversariestoidentifytherealmessagesource- location.Therefore,ourgoalistodesignsecuritymechanismssuchthatitisinfeasibleforanyone todistinguishthemessagesourcenodefromthemessageforwardingnode. Relayringnodesgeneratevehiclemessagestobetransmittedinthemixingring.Thenormal ringnodescanstoredatamessagesreceivedfromthenormalnodes.Thevehiclemessagesmay containseveraldataunits.Theseunitsareleftunusedinitially.Ifaunitinthevehiclemessage isnotused,wenamethisunitas dummyunit ,composedofanyfixeddatastructure,suchasall 0s.Thelengthofaunitisthesameasthedatamessagesentbyanormalnode.Uponreceivinga vehiclemessage,ifanormalringnodehasarealdatamessagereceivedandthereisstilladummy unitinthevehiclemessage,itcanreplacethisdummyunitwiththedatamessage.Theupdated vehiclemessagewillthenbeforwardedtoitssuccessorringnode.Ifthisnormalringnodehas notreceivedanydatamessagesfromthenormalnodes,orthereisnodummyunitsleftinthe vehiclemessage,itsimplyforwardsthisvehiclemessage.Thevehiclemessageshouldbesentat theratewhichcouldensurethatallthedatamessagescouldbeembeddedinvehiclemessagesand forwardedtotheSINKwithminimumdelay. Inourscheme,tothwartmessagesourceanalysis,themessagetransmissionintheringis encrypted.Eachringnodesharesasecretkeywithitspredecessorringnodeandasecretkeywith itssuccessorringnode.Asanexample,inFigure2.15,ringnode Bsharesakey KABwithring nodeAandakey KBCwithringnode C.Whennode Breceivesapacket M1fromnode A,itfirst decryptsM1usingthesharesecretkey KAB.Let m1=DKAB(M1).Upondecryption,node Bwillbeabletofindthedummyunit(s)in m1andreplacethedummyunit(s)withthedatamessage(s) thatitreceivedfromthenormalnodes.Denotetheupdatedmessageas {DKAB(M1)}.Theupdated vehiclemessagewillbeencryptedusingthesharedsecret KBCbeforeitistransmittedtothenode 31ABCDE2M1M3MFigure2.15Messagetransmissioninthering 32C.Denotethemessagethatgeneratedinnode BasM2,thenwehave M2=EKBC({DKAB(M1)}).(2.1)WhenDESorAESencryptionalgorithmisbeingusedtoprovidemessageencryption,thenit iscomputationallyinfeasibletofindthecorrelationbetween M1andM2.Apparently,theenergydrainagefortherelayringnodeswillbefasterthanthenormalring nodes.Tobalancetheenergyconsumption,thenormalringnodescantaketurnstobetherelay ringnodes.Similarly,sincetheenergydrainagefortheringnodeswillbefasterthantheregular gridnodes,thenodesintheselectedringgridcantaketurnstobetheringnode. 2.5.3ForwardingtotheSINK Afteravehiclemessagearrivesatarelayringnode,itwillbeforwardedtotheSINKbythisrelay ringnodewithcertainprobability p.Here pisaparameterrelatedtothenumberofrelayring nodesonthemixingring.IfthisvehiclemessageisnotforwardedtotheSINKbytherelayring node,itwillbeforwardedtothenextringnodeuntilanotherrelayringnodeisreached. 2.5.4SecurityAnalysisforMixingRingRouting Wewillfirstanalyzethattheproposedroutingtoarandomintermediatenode(RSIN)inphaseone canprovidelocalsource-locationprivacy.Unlikephantomrouting,whichhasnocontroloverthe phantomsourcewithoutleakingsignificantsideinformation,intheproposedRSINscheme,the intermediatenodeisdeterminedbeforeeachdatamessageistransmittedbythesource-location,the datamessagecarriesnoobservablesideinformationofthemessagesource-locationinitscontent. Therefore,itdoesnothavethesecuritydrawbacksofphantomroutingdiscussedbefore.Itis alsoimpossiblefortheadversarytotracebackandidentifytherealmessagesourcebasedonan individualtrafficmonitoring.Thisisbecausetheprobabilityformultipleeventsfromthesame sourcetousethesameroutingpathandintermediatenodeisverylowforlargesensornetworks. 33Ifanadversarytriestotracebackthesource-locationfromthemessagepacketintheroute throughwhichthepacketisbeingtransmittedtothemixingring,thentheadversarywillbeledto therandomlyselectedintermediatenodeinsteadoftherealmessagesource.Sincetheintermediate nodeisrandomlyselectedforeachdatamessage,theprobabilitythattheadversarieswillreceive themessagesfromonesourcenodecontinuouslyisprettysmall.AsshowninFigure2.14,ifan adversaryreceives M2forwardedby I2,itwouldbeledto I2.However,thenextintermediatenode I3isfarfrom I2,sotheadversariescouldnotreceive M3.Evenifoneintermediatenode’slocationisdiscoveredbytheadversaries,thesource-locationis stillwellprotectedbecausethelocationsoftheintermediatenodesareatleast dminawayfromthe realsourcenode.Therefore,theproposedprotocolcanprovidethelocalsource-locationprivacy. AsshowninFigure2.14,theintermediatenodes I1,I2,I3forwardmessagestoringnodes R1,R2,R3,respectively.Thismeansthatmessagesgeneratedfromonesourcenodewillnotbe forwardedtoaspecificringnode.Conversely,thedatamessagesreceivedfromoneringnode couldalsobetransmittedfrommanydifferentsourcenodesinthenetwork. Theroutinginthemixingringisthesecondphaserouting.Thisphaseaimsatproviding network-levelsource-locationprivacy.Thisisachievedbyhop-by-hopmessageencryption.With- outhop-by-hopmessageencryption,bycomparingthevehiclemessagethatanodereceivedand transmitted,theadversarycandeterminewhetheradatamessagehasbeenloadedintotheupdated vehiclemessage.However,oncethehop-by-hopmessageencryptionisimplemented,itiscompu- tationallyinfeasibleforanadversarytodistinguishthemessageinitiatorandmessageforwarderin themixingring.Themessagesacrossthenetworkaretotallymixedup.AsshowninFigure2.14,a datamessagereceivedbyringnode BcouldbesenttotheSINKnodefromacompletelydifferent ringnode,maybenode Eforinstance.Therefore,thenetwork-levelsource-locationprivacyis achieved. 340xy-4000-ee-ee-400040004000UFigure2.16Ringselectioninsimulationsetup 352.5.5PerformanceAnalysisandSimulationResults Inourdesign,alldatamessageswillbedeliveredtotheSINKnodethroughthemixingring. Whileprovidingnetwork-levelsource-locationprivacy,thelocationoftheringshouldbeselected toensurethattheoverallenergyconsumptionandlatencyformessagetransmissiontobelowest forthenormalnodestocompletetheseoperations.Weassumethateachsensornodeinthenetwork hascompleteknowledgeofitsrelativelocationinthesensornetworkandalsosomeringnodes. Wealsoassumethattheenergydrainageforeachtransmissionisproportionaltothesquareofthe distance,i.e. E=×d2,whereEdenotestheenergyconsumption, isaconstantparameterand disthedistanceofthe transmission.Figure2.16givesanexampleofatargetareaofsize8000 ×8000meters.The shadedgridsareselectedastheringgrids.Thelineinthemiddleoftheshadedareaisindicated bythesolidline.Ifthedensityofthesensornodesinthesensornetworkis ,thenthetotalenergy consumptionforeachsensorinthisareatotransmitonemessagetoaringnodecanbecalculated asfollows: Etotal =8EU=8/404000/cos0(r−e)2rdrd ,whereEUistheenergyconsumptionforarea UasdemonstratedinFigure2.16.Itcanbecalculated thatwhen e=3061,theoverallpowerconsumption Etotal achievestheminimum.Inthisway,we gettheoptimalringlocation. 3610101000510152025303540The percentage of the active nodesDelay / secondmsg freq=1/300msg freq=1/100msg freq=1/10msg freq=1/1Figure2.17MixingRing:Powerconsumptionofnormalnodes 371010100050100150200250The percentage of the active nodesDelay / secondmsg freq=1/300msg freq=1/100msg freq=1/10msg freq=1/1Figure2.18MixingRing:Powerconsumptionofringnodes 38101010000.20.40.60.811.21.41.6The percentage of the active nodesDelay / secondmsg freq=1/300msg freq=1/100msg freq=1/10msg freq=1/1Figure2.19MixingRing:Messagelatency 391010100050100150200250The percentage of the active nodesDelay / secondmsg freq=1/300msg freq=1/100msg freq=1/10msg freq=1/1Figure2.20MixingRing:Messagedeliveryratio Inpracticalapplication,forlargesensornetwork,usuallyonlyasmallfractionofthesensor nodesinthenetworkhaseventstoreport.Wenamethesenodesas activenodes .Wealsodefine twoparametersinthesimulation: ,thenumberofdatamessagesanormalnodegeneratesineach second,and a,activenodesratio. Assumethenetworkiscomposedof gnormalnodes,andtheringconsistsof rringnodes.On average,oneringnodeshouldberesponsiblefordeliveringthedatamessagesfrom g/rnormalnodes.Assumedatamessagesare l-bitlong,thenonaverage,ineachsecond,aringnodewill receive: =gr×l×a×=gla r,messages.40Ifvehiclemessagesare L-bitlong,thenumberofvehiclemessagesgeneratedbyaringnodein onesecondis: gla r×1L=gla rL.Sinceonlytherelayringnodesontheringcangeneratevehiclemessages.Ifthereare nrelayringnodesonthering,theneachrelayringnodeneedstogenerateatleast gla rL×rn=gla nL,vehiclemessageseachsecond. SimulationresultsareprovidedinFigure2.17,2.19todemonstratethepowerconsumption forbothnormalnodesandringnodes,messagelatencyandmessagedeliveryratiooftheproposed scheme.OursimulationwasperformedusingNS2onLinuxsystem.Inthesimulation,thetar- getareaisasquarefieldofsize8000 ×8000meters.Wepartitionthisfieldinto2400normal grids/nodes.Themixingringiscomposedof80grids,i.e, r=80.Therearefourrelayringnodes inthemixingring,i.e, n=4.Weassumethattherandomlyselectedintermediatenodeisatleast 600metersawayfromtherealmessagesource.Thedatamessagesare8-bitlong,i.e, l=8.The vehiclemessagesare16-bitlong,i.e, L=16.FromtheFigure2.17.(a)and(b),wecanseethatringnodesconsumemoreenergythannormal nodes.Tosolvethisproblem,thenodesinringgridscantaketurnstobetheringnodes.Itisalso noticedthatthedeliveryratiodropsexponentiallywhenthetrafficvolumeincreases.Itisprimarily becauseofthetrafficcollisionsandpacketlossescausedbytheincreasedtrafficvolume.Foralarge sensornetwork,itisusuallynotnecessaryforallthesensornodestobeactiveatthesametime.In practice,thepercentageofactivenodesmightbeverylow.Thetransmissionfrequencyalsotends nottobeveryhigh.Inotherwords,thetrafficvolumemaybelow.Inthisscenario,wecanensure almost100%deliveryratio,asshowninFigure2.19.(d).Thesimulationresultsdemonstratethat theproposedschemeisveryefficientandcanbeusedforpracticalapplications. 412.6Source-LocationPrivacyusingSTaRRouting 2.6.1Preliminary:Source-LocationPrivacyEvaluationModel In[72],securityanalysisofsource-locationprivacybasedonquantitativemeasurementoninfor- mationleakageofthesource-locationhasbeenproposed.Thequantitativemeasurementdivides informationleakageanalysisintothreecategories: 1.Correlation-basedsourceidentificationattack: Correlation-basedattackisanIDbased sourcenodedetermination.WhenanadversaryreceivesamessagewithanIDwhoselo- cationisalreadyknown,thelocationofthisnodeisalsoknown. 2.Routingtracebackattack: Routingtracebackisanattackthatwhenanadversarycapturesa message,hecanidentifytheimmediatemessagesenderandquicklymovetoit.Forfixed pathroutingoflength n,iftheadversarycancapture nmessagesfromthissource,thenheis abletolocatethemessagesourcenode. 3.Reducingsourcespaceattack: Reducingsourcespaceattackreferstotheattackthatthe adversarycanlimitthesourcenodetoapropersubset/areainthenetworkswhenamessage iscaptured.Whenmultiplemessagesarecaptured,thesubset/areamaybefurtherreduced sothatthesource-locationcanbelimitedtoasubset/areathatmayleadtoarelativeeasyor completesourceidentification. Topreventcorrelation-basedsourceidentification,adynamicIDbasedapproachcanbeused topreventadversariesfromrelatingmessagestransmittedfromeachsource[72,73].Thiscanbe donebyrequiringthateachnodeinthenetworkbepreloadedwithan ID-hash-chain sothata differentanduncorrelatedIDisattachedtoeachmessage.Theadversariesarenolongerableto getanyusefulinformationaboutthesourcenodethroughcorrelation-basedsourceidentification. Forroutingtracebackandreducingsourcenodespaceanalysis,threecriteriahavebeendefined in[72]. 42Definition1(Source-locationDisclosureIndex(SDI)) SDImeasures,fromaninformationen- tropypointofview,theamountofsource-locationinformationthatonemessagecanleaktothe adversaries. Foraroutingscheme,ifweassumethetotalprivacyforasourcenode Sis1,andthe SDIisfixed,thentheadversaryonlyneedstoreceive 1SDI messagesinitiatedfrom Sinorderto successfullylocate S.Therefore,foragoodSLPscheme, SDIshouldbeassmallaspossible. Definition2(Source-locationSpaceIndex(SSI)) SSIisdefinedasthesetofpossiblenetwork nodes,orareaofthepossiblenetworkdomain,thatamessagecanbetransmittedfrom. Foraroutingscheme,if SSIislarge,itmeansthatthemessagemaybetransmittedbymany possiblesourcenodes.Onthecontrary,if SSIissmall,thentheadversarycanlimitthepossible sourcenodestoasmallgroup.Therefore,foraSLPscheme, SSIshouldbeaslargeaspossible sothatthecomplexityforanadversarytoperformanexhaustivesearchofthemessagesourceis maximized.Definition3(NormalizedSource-locationSpaceIndex(NSSI)) NSSIisdefinedastheratioof theSSIareaoverthetotalareaofthenetworkdomain.Therefore,NSSI [0,1],andwealways haveNSSI =1−forsome [0,1].The iscalledthelocaldegree. Itisclearthattheschemewiththelocaldegree0providesthehighestdegreeofSLP. Basedonthesedefinitions,wehavederivedin[72]thatfixedpathroutingschemesaretheleast secureSLPschemes. Lemma1 SupposethereisafixedroutingpathbetweenthesourcenodeSandthedestination nodeDoflengthLhops.AisanadversarywhocandetectallmessagestransmittedtoD.Then, afterreceivingLmessages,AwillbeabletotracebacktothesourcenodeS,i.e., SDI =1L.43Ifthereare ndisjointroutingpathsbetweenthesourcenode Sanddestinationnode D,andthe lengthofthe npathsare: L1,L2,···,Ln,respectively.Foreachmessage,thesourcenode Swillsenditalongpath Liwithprobability pi,where ni=1pi=1.Forpath i,wehave SDI i=piLi,i=1,···,n.DefinetheoverallSDIas SDI =ni=1pi·SDI i.Wewillthenhavethefollowingresult[72]. Theorem1 SupposetherearendisjointroutingpathesbetweenthesourcenodeSandtheSINK nodeD.ThelengthsofthenroutingpathesareL 1,L2,···,Ln.Letp ibetheprobabilitythat messageswillbetransmittedalongthepathL i,thenwhenp i=LiL1+L2+···+Ln,i=1,2,···,n,theSDIisminimized,whichis SDI =1L1+L2+···+Ln.Corollary1 SupposetherearendisjointroutingpathsbetweenthesourcenodeSandthedesti- nationnodeD.ThelengthofthenroutingpathsareL 1,L2,···,Ln,respectively.Theadversary thenneedstoreceiveonaverage 1SDI =L1+L2+···+Lnmessagestofullydeterminethelocationofthesourcenode,i.e.,tracebacktothesourcenode. Asaresult,toprovideSLPinwirelesssensornetworks,wehavetoincreasethetotalnumberof possibleroutingpathsbetweenthedestinationnodeandthesourcenode.However,forapractical networkconfiguration,thenumberofroutingpathscannotbeincreasedwithoutlimitation.This meansthatwewillalwayshave SDI >0.WecansummarizethetwodefectsoftheSLPschemesthroughfixedroutingpathesasfollows: 44•Non-zeroSDI:Forfixedpathrouting,nomatterhowdedicatedtheschemeisdesigned, SDIisalwayslargerthan0.Inotherwords,foreachmessagesentoutbyonesourcenode,from aprobabilitypointofview,thereisalwaysafractionofsourceinformationtobeleakedto theadversaries.So,nomatterhowsmallthe SDIis,whenenoughmessagesarereceived, theadversariesarealwaysabletolocatethesourcenode. •LimitedSSI:Becausetheroutingpathsarefixedforthesourcenode,thecorrelationbetween themessagestransmittedonaparticularpathandthesourcenodeishigh.Inotherwords, SSIissmallcomparedtotheoverallsensornetworksize. Phantomroutingisadynamicroutingscheme.Inthisscheme,themessageisfirstroutedtoa phantomsourcethrougharandompathbeforeitisforwardedtotheactualdestinationnode.To makesurethatthephantomsourceisawayfromtheactualsourcenode,thedirectioninformation mustbestoredinthemessage’sheader.Inthisway,theintermediatenodesontheroutingpathare abletoselectthenextforwardnodeontheroutingpathalongthesamedirection. In[72],eachsensornodeisassumedtohaveauniqueIDthatcorrespondstoaphysicallocation. Theproblemofthisdesignisthatitmakesitpossiblefortheadversariestomonitorandlinkall messagesfromthesamesourcenodetogether,whichmayhelptheadversariestoidentifythe source-locationsincetheIDscorrespondtothegrids’locations.Therefore,wehave SDI >0.WhenevertheadversariesdiscoveramessagesentfromagridwithanIDthattheyalready know,theycanusethismessagetomoveclosertothemessagesource.Fortunately,thisproblems canbeeasilysolvedifdynamicIDisassignedforeachmessage.Inthiscase,thecorrelation betweenthesourcenodeandthemessagereceivedintherandompathcanbeviewedaszero,i.e., SDI 0.However,thedirectioninformationstoredinthemessageheadercanfacilitatetheadversaryto narrowthepossibleareaofthesourcenode.Takethesection-basedrandomwalkasanexample. 45Onceamessageiscorruptedbyanadversaryontherandompath,theadversarycandetermineto whichdirectionofthecurrentlocationtheactualsourcenodeislocated.Therefore,wehave NSSI <1.Whenmultipleadversariescollaborateinthetargetarea T,the NSSI canbefurtherreducedand theSLPisnolongerwellprotected. 2.6.2STaRRoutingScheme TheSTaRroutingscheme,whichwasintroducedin[74],providessource-locationprivacythrough atwo-phaseroutingprotocol.Inthefirstphase,thesourcenoderoutesthemessagetoarandomly selectedintermediatenodelocatedinapre-determineregionaroundtheSINKnode.Wecallthis regiontheSinkToroidalRegion(STaR).Therandomintermediatenodeservicesasafakesource whenthemessageisforwardedtotheSINKnode.Theintermediatenodewillforwardthemessage totheSINKnodebysingle-pathroutinginthesecondphase.Thecombinationofthesetwophases guaranteesthelocaldegreetobesmall,therefore,providingahighdegreeofSLP.InSTaRSLP scheme,topreventtheadversariesfromgettinganyusefulsource-locationinformationthrough correlation-basedsourceidentification ,adynamicIDproposedin[73]shouldbeassignedfor eachmessage. Inourscheme,thenetworkisevenlydividedintosmallgrids[73].Weassumethatthesensor nodesineachgridareallwithinthedirectcommunicationrangeofeachother.Ineachgrid,the headernodecoordinatesthecommunicationwithotherheadernodesnearby.Weassumethatthe wholenetworkisfullyconnectedthroughthemulti-hopcommunications. Thegoaloftheproposedschemeistoprovidelocalandglobalsource-locationprivacywith adequateenergy-efficientrouting.Localprivacyisobtainedbythefactthattheintermediatenode isexpectedtobeneithertooclose,nortoofarfromtherealsource,formostcases.TheSTaRarea wouldbealargeareawithatleastaminimumradiusdistance rfromtheSINKnodetoprovide globalprivacy.Also,theSTaRareaguaranteesthattheintermediatenodeisatmostamaximum 46XSink(X0,Y0)rRR-rSTaRarea Figure2.21DistributionoftheSTaRarea 47distanceRfromtheSINKnodetolimittheenergyconsumptionintheroutingpaths.Thisrouting schemeisdesignedtogivetheillusionthatthesourcenodeissendingmessagestotheSINKnode fromallthepossibledirections.Inthisway,theSTaRcreatesaneffectthatissimilartothetotally randomRRINscheme[75]butwithlessenergyconsumptionandshorterdelays. Weassumethateachsensornodeonlyhasknowledgeofitsadjacentnodesandhasnoaccurate informationofthesensornodesmorethanonehopaway.Wealsoassumethateachnodehas knowledgeoftheparametersthatareshowninFigure2.21.Thedescriptionoftheparametersare asfollows: •x0,y0:ThecorrespondingXandYcoordinatesoftheSINKnodelocation, •R:Thepre-determinedradiusfromtheSINKtotheouter-edgeoftheSTaRarea, •r:Thepre-determinedradiusfromtheSINKnodetotheinner-edgeoftheSTaRarea. Fromtheseparameters, {x0,y0,R,r},thesourcenodesareabletogeneraterandompoints withintheSTaRarea.SinceweassumethattheSINKnodeislocatedattherelativelocation (x0,y0),thesourcenodeselectstherandomlocation (x,y)accordingtothefollowingtwosteps: 1.Randomlyselect duniformlyfrom [r,R].2.Randomlyselect uniformlyfrom [0,2].Inthisway,wecancalculatethecoordinateoftheintermediatenodeas (x,y)=(x0+dcos(),y0+dsin()).Afterobtainingtherandomlocation (x,y),themessagecanthenberoutedtowardsthegridat location(x,y).Sinceeachnodeonlyknowsitsadjacentneighbornodes’relativelocation,itcan determinethedirectionthatthemessageshouldberouted.Oncethemessageiswithinthedesired gridoftherandomlocation,themessageisroutedtotheheadernodeofthegrid.Theheadernode thenbecomestherandomintermediatenode.Ifthedesiredgriddoesnotcontainanynodes,then thelastnodeintheroutingpathwouldbecomethedesiredlocationandtheheadernodeinthatgrid 48wouldbecometheintermediatenode.Theintermediatenodethenroutesthereceivedmessageto theSINKnodeusingsingle-pathrouting. 2.6.3SecurityAnalysisforSTaRRouting WewillanalyzetheSLPforSTaRroutingscheme.Weassumetheadversaryisunabletomonitor theentiresensorareaofthesourcenode,sinceotherwiseitcanmonitortheactualeventdirectly. IntheproposedSTaRroutingscheme,arandomintermediatenodeisselectedforeachmessage fromtheSTaRareashowninFigure2.21.Unlikethedirectedwalkofthephantomroutingscheme, ourprotocoldoesnotleakdirectioninformationtotheadversaries. Theorem2 FortheproposedSTaRscheme,ifassumethattheSTaRareaislargeenoughsothat theprobabilityformultiplemessagestoberoutedusingthesameintermediatenodeisnegligible. Thentheamountofsource-locationinformationthatcanbeleakedfromonemessageisnegligible, i.e., SDI 0,andSLPwithlocaldegree0. Proof1 FortheproposedSTaRscheme,thesource-locationdisclosureindexcanbeanalyzedin twoscenariosbasedonthelocationoftheadversarialattacks:(i)theadversarymonitorstraffic betweentherandomlyselectedintermediatenodeinSTaRareaandtheSINKnode,and(ii)the adversarymonitorstrafficbetweenthesourcenodeandtherandomlyselectedintermediatenode intheSTaRarea. Forscenario(i),first,theSTaRareaisatleastanrdistanceawayfromtheSINKnode.Second, everynodewithintheSTaRareafromtheSINKnodehasequalprobabilityinbeingselectedas theintermediatenodeforallmessagesbyallpossiblesourcenodes.Therefore,themessagesare beingroutedfromtheSTaRareatoSINKfromalldirectionswithequalprobability,asshownin Figure2.22.Therefore,themessagestobetransmittedfromtheSTaRareatotheSINKnodearea 49SINK2I1I3I1S2S3S2m1m3m4I4mFigure2.22RoutingillustrationoftheSTaRprotocol 50bearnocorrelationwiththeactualmessagesourceanditisimpossibleforanadversarytogain anyinformationofsource-locationforthemessagesource. Itisalsoimpracticalfortheadversarytoperformroutingtracebacktofigureoutthesource locationbyonlymonitoringandanalyzingtrafficpatternsaroundtheSINKnode.Inthisscenario, theglobalsourcelocationprivacycanbeassuredandhencesourcelocationprivacywithalow localdegreecanbeguaranteed. Forcase(ii),themessagesourcemaybelocatedanywhereinthenetworkdomainandthe intermediatenodeisexpectedtobefarfromtherealsourceformostcases.Theprobabilityforthe adversarytointerceptamessageisverylowforlargewirelesssensornetworks.Theprobabilityfor anadversaryinterceptmultiplemessagesfromthesamesourceinthesamelocationisnegligible. Infact,ifadynamicIDisusedfor eachmess age,thene venifanadversaryisabletointerceptone message,heisstillunabletolinkthemtogether. Whenonlyonemessageisintercepted,theadversarycanonlydeterminetheimmediatepre- viousnodebasedonourassumption.Theadversarycanneitherdeterminethedirectionofthe nextprevioushopsourcenode,northedirectionoftheactualsourcenode.Inotherwords,the source-locationdisclosureindexequalsto0withannegligibleexceptionforthenodesinthearea oftheadversary.Therefore,wehave SDI 0,andtheSLPlocaldegreeis0. Theorem3 IntheproposedSTaRscheme,forany receivedmess age,the sourcenodeiseither locatedintheareathattheadversarycanmonitor,ortheadversaryhasnoinformationofthe actualmessagesource.Thatis NSSI 1.Proof2 SimilartoTheorem2,theanalysiscanbedividedintotwoscenario:(i)theadversary monitorstrafficbetweentherandomlyselectedintermediatenodeinSTaRandtheSINKnode,and 51IIIIIBAIFigure2.23ThesourcelocationanalysisofSTaRroutingscheme (ii)theadversarymonitorstrafficbetweenthesourcenodeandtherandomlyselectedintermediate nodeintheSTaRarea. Forcase(i),whenanadversaryreceivesamess age,ifhe isunabletofindthe messagesource inhisarea,thenthesourcenodecanbeinanydirectionandhopdistanceawayfromthelocation wherethemessageisreceived. 52Forcase(ii),asshowninFigure2.23,whenamessageisreceivedinlocationA,basedon ourassumption,theadversarycanfindtheimmediatemessagenode,sayB.However,theonly informationthattheadversarycangetforthenodespriortoBarelocatedintheshadedareaI, I+II,andI +II+III,andsoon. Sincetheadversarycanneitherdeterminethedirection,northe hopdistanceoftheactualsourcenode,theactualmessagesourcenodecanbelocatedanywhere ofthesensordomainexcepttheareacenteredatA.Inthisway,wehave NSSI 1.2.6.4PerformanceAnalysisandSimulationResults Toevaluatetheperformanceoftheschemesproposed,extensivesimulationshavebeenconducted usingns-2onRedHatLinuxsystem.TheresultsofthesimulationsareshowninFig.2.24,2.26. Inthesimulation,400nodesarerandomlydistributedinasquaretargetareaofsize3360 ×3360meters,whiletheSINKnodeislocatedatthecenterofthenetwork.Wesethopcountofdirected walkingofphantomroutingtobefour,whichonaveragethephantomsourcewasfoundtobe 526.12metersawayfromtherealsource.ForRRINscheme,theminimumdistancebetweenthe sourcenodeandtheintermediatenodeswassetto480meters,andtheaveragedistanceturnedout tobe529.14meters.Wealsoillustratetheperformanceofthetotallyrandomlyselectedinterme- diatenodes.ForSTaRrouting,theinnerradius, r,wassetto480meters,whiletheouterradius, R,wassetto640meters. 531011020.40.50.60.70.80.911.1Length of every packet / BytesEnergy / JouleFigure2.24PerformanceofSTaRrouting:Powerconsumption 541011020.020.030.040.050.060.070.080.090.1Length of every packet / BytesDelay / secondsFigure2.25PerformanceofSTaRrouting:Messagelatency 551011020.9920.9940.9960.9981Length of every packet / BytesDelivery RatioFigure2.26PerformanceofSTaRrouting:Messagedeliveryratio Throughanalysisandsimulationresults,wefindthatdirectroutingwithoutintermediatenode hasthebestperformancewhiletotallyrandomRRINhastheworseperformance.Theperformance oftheRRINschemeisbetterthanphantomroutingforcomparablesecuritysincetheaverage routingpathsinphantomroutingislongerthantheRRINduetothemorecurvedroutingpaths. TheperformanceofSTaRisbetweenthetotallyrandomRRINandconstrainedRRIN.Thedelivery ratioforSTaRisslightlylowerthanthetwoRRINschemesduetothepossiblehighercollisions ratio.56CHAPTER3 DESTINATION-LOCATIONPRIVACYPROTECTION 3.1LimitationswithExistingSolutionsforDestination-LocationPrivacy Theonionroutingprotocol,discussedin[34],providesanonymouscommunicationinanetwork. Asamessageispassedinthenetwork,onionroutersrepeatedlyencryptsthemessagebetween routers.Thistechniqueprovidesprivacyoftheidentityofthesender,destinationandthemessage content.Onionroutingpreventsanadversaryfromeavesdroppingonthemessagecontentand protectagainsttraffic-analysisattacksbymakingthesenderanddestinationanonymous.This protocolwasdesignedtoprotectcommunicationovertheinternetnetworkandusescryptosystems, whichmakeitnotsuitableforWSNs. Broadcasting-basedschemesprovidelocationprivacybymixingtherealmessageswithfake messagessothattheybecomeindistinguishabletotheadversaries.In[37],theDEEP(Differential EnforcedFractalPropagation)routingprotocolisintroduced.Inthisscheme,thesourcenodesend therealmessagetothedestinationusingarandomwalkroutinginthedirectiononthedestination andnodesintheroutingpathinjectsfakemessagesintothenetworktocreatehotspotstohelp protectthedestinationlocation.TheLPR(Location-PrivacyRouting)withfakemessageinjection isproposedin[76].ThisschemeissimilartotheDEEProutingprotocolbutdoesnotcreate hotspotsandtrytosolvethevulnerabilityoftheDEEProuting.TheLPRprotocolrandomizes theroutingpathssothattheforwardingdirectionoftherealmessageisnotalwaystowardsthe destination.Insection2.6.3,wewillanalysisthesecurityvulnerabilityofthesetwoschemesin providingdestination-locationprotectionschemes. Providinglocationprivacythroughdynamicroutingis,inouropinion,oneofthemostfeasible approachesinWSNs[27,40].Themainideaistopreventtheadversariesfrommonitoringthe traffictothelocationofasourceordestinationnode.Arepresentativeexampleofarouting- 57basedprotocolisthephantomroutingprotocol,whichinvolvestwophases:arandomordirect walkphaseandasubsequentflooding/singlepathroutingphase.Intherandomwalkingphase, themessagefromtheactualsourcewillberoutedtoaphantomsourcealongarandompathora designeddirectedpath.Thephantomsourceisexpectedtobefarawayfromtheactualsource. Withsector-baseddirectedwalk,thesourcenodefirstrandomlydeterminesadirectionthatthe messagewillbesent.Everyforwarderonthedirectwalkpathwillforwardthismessagetoa randomneighborinthesamedirectiontoensurethatthephantomsourcewillbeawayfromthe actualsource.Thisschemewasdesigntoprotectthesourcenodelocationandnotthedestination nodelocation.Thestrengthofthisschemeisthatthesourcenodewillfirstsendthemessage toaphantomsourcethatmayormaynotbeinthedirectionofthedestinationnodelocation. Theweaknessiswhenthephantomsourceroutethemessagetothedestination,themessagewill alwaysberoutedinthedirectionofthedestinationnode. Likedestination-locationprivacyschemes,source-locationprivacy[72,77]isalsoavitalcom- ponenttocontext-basedattacks.Manyofthetechniquesusedforprotectionofthesourcenodecan notbeappliedforprotectionofthedestinationnode.Source-locationprivacyisbeyondthescope ofthispaperbutwecanapplysomeoftheattributesofsourcelocationprivacyschemesfordes- tinationlocationprivacy,suchasusingfakemessageinjectionandtwo-phaseroutingtechniques. Inthispaper,wefocusonprovidingrouting-baseddestination-locationprivacy. 3.2NetworkModelsandDesignGoals 3.2.1TheSystemModel Thefollowingassumptionsaremadeaboutthesystem: •Thenetworkisdividedintogrids.Thesensornodesineachgridarefullyconnected.In eachgrid,thereisoneheadernoderesponsibleforcommunicatingwithothernearbyheader nodes.Thewholenetworkisfullyconnectedthroughmulti-hopcommunications. 58•Everynodeinthenetworkcanbecomeasourcenodeonadetectionofanevent.Ondetecting anevent,asensorsourcenodewillgenerateandsendmessagestothedestinationnode throughamulti-hoprouting. •EachmessagewillincludeauniquenodeIDwheretheeventwasgenerated.TheSINKnode canonlydeterminesourcenodelocationbasedoffthenodeID. •Thesensornodesareassumedtoknowtheirrelativelocationanddestinationnodelocation. Wealsoassumethateachsensornodehastheknowledgeofitsadjacentneighboringnodes. Theinformationabouttherelativelocationofthesensordomainmayalsobebroadcasted throughthisnetworkforroutinginformationupdate. •Thekeymanagement,includingkeygenerations,keydistributionandkeyupdate,isbeyond thescopeofthispaper.However,theinterestedreadersarereferredtoreferencessuchas[8]. 3.2.2TheAdversariesModel Inthispaper,theadversaryhasthefollowingcharacteristics: •Well-equipped: Theadversarydoesnotneedtoworryabouttheenergyconsumptionandhas adequatecomputationcapability.Ondetectingatransmittedmessage,theadversarycould determinethereceivernodebywaitingtoseewhichneighbornoderetransmitthemessage. Theadversaryisabletomovetothisreceiverâ ˘A´Zslocationwithoutmuchdelayandhas enoughmemorytostoreanyusefulinformation.Ifneeded,theadversarycouldcompromise somesensornodesinthenetwork. •Passive: Theadversariescarryoutsomepassiveattacks,whichonlyinvolveeavesdropping work. •Traffic-monitoring: Theadversaryisabletomonitorthetrafficinanareaandreceiveall messagesinthisarea.However,weassumethattheadversaryisunabletomonitortheentire network. 593.2.3DesignGoals Ourdesigngoalscanbesummarizedasfollows: •Theadversariesshouldnotbeabletogetthedestination-locationinformationbyanalyzing thetrafficpattern. •Theadversariesshouldnotbeabletogetthedestination-locationinformationeveniftheyare abletomonitoracertainareaofthesensornetworkandcompromiseafewnetworknodes. •Thelengthofeachmessageshouldbeasshortaspossibletosavetheprevioussensornode power. 3.3ProposedResearchDirectionsforDestination-LocationPrivacy 3.3.1DirectionsforDestination-LocationPrivacy Inthissection,weproposeauniqueroutingtechnique,calledbubblerouting,thatcanprovide strongdestination-locationprivacywithlowtradeoffintheenergyoverhead.Inourproposed scheme,thesourcenoderandomlyselectsanintermediatenodefrompre-determinedregionlo- catedaroundthedestinationnode,whichwerefertoasthebubbleregion.Thebubbleregion wouldbelargeenoughtomakeitinfeasibleforanadversarytomonitortheentirearea.Also, inthisscheme,wewillmixrealmessageswithfakemessagestoaddtothesecuritystrengthin providingdestination-locationprivacy. 3.4Preliminary:Destination-LocationPrivacyEvaluationModel Inthissection,wewillprovidesecurityanalysisofdestination-locationprivacybasedonquanti- tativemeasurementoninformationleakageofthedestination-location.Thequantitativemeasure- mentdividesinformationleakageanalysisintothreecategories: 601.Correlation-baseddestinationidentificationattack: Correlation-basedattackisanIDbased destinationnodedetermination.WhenanadversaryreceivesamessagewithanIDwhose locationisalreadyknown,thelocationofthisnodeisalsoknown. 2.Routingforwardattack: Routingforwardisanattackthatwhenamessageisforwardto thenexthopnode,anadversarycapturesamessageandidentifytheimmediatemessage receiverandquicklymovetoit.Forfixedpathroutingoflength n,iftheadversarycan capturenmessagesfromthesource,thenanadversarycanlocatethemessagedestination nodewith ncapturedmessages. 3.Reducingdestinationspaceattack: Reducingdestinationspaceattackreferstotheattackthat theadversarycanlimitthedestinationnodetoapropersubset/areainthenetworkswhena messageiscaptured.Whenmultiplemessagesarecaptured,thesubset/areamaybefurther reducedsothatthedestination-locationcanbelimitedtoasubset/areathatmayleadtothe destinationnode. Topreventcorrelation-baseddestinationidentification,adynamicIDbasedapproachcanbe usedtopreventadversariesfromrelatingmessagestransmittedfromeachsource[72,73].Thiscan bedonebyrequiringthateachnodeinthenetworkbepreloadedwithan ID-hash-chain sothata differentanduncorrelatedIDisattachedtoeachmessage.Theadversariesarenolongerabletoget anyusefulinformationaboutthedestinationnodethroughcorrelation-basedsourceidentification. Forroutingtraceforwardandreducingdestinationnodespaceanalysis,canbedefinedinthree criteriaasfollow: Definition4(Destination-locationDisclosureIndex(DDI)) DDImeasures,fromaninformation entropypointofview,theamountofdestination-locationinformationthatonemessagecanleak. Foraroutingscheme,ifweassumethetotalprivacyforadestinationnode Dis1,andthe DDIisfixed,thentheadversaryonlyneedstoreceive 1DDImessagesroutedto Dinorderto successfullylocate D.Therefore,foragoodDLPscheme, DDIshouldbeassmallaspossible. 61Definition5(Destination-locationSpaceIndex(DSI)) DSIisdefinedasthesetofpossiblenet- worknodes,orsub-areaofthenetworkdomain,thatcancontainthedestinationnode. Foraroutingscheme,if DSIislarge,meansthatpracticallytheentirenetworkcancontain thedestinationnode.Onthecontrary,if DSIissmall,thentheadversarycanlimitthenetwork toasmall-subareasofnodesthatpossiblecontainthedestinationnode.Toprovideadequate destination-locationprivacy, DSIshouldbeaslargeaspossible. Definition6(NormalizedDestination-locationSpaceIndex(NDSI)) NDSIisdefinedasthera- tioofthe DSIareaoverthetotalareaofthenetworkdomain.Therefore,NDSI [0,1],andwe alwayshaveNDSI =1−forsome [0,1].The iscalledthelocaldegree. Itisclearthattheschemewiththelocaldegree0providesthehighestdegreeofDLP. Basedonthesedefinitions,wehavederivedin[72]thatfixedpathroutingschemesaretheleast secureDLPschemes. Lemma2 SupposethereisafixedroutingpathbetweenthesourcenodeSandthedestination nodeDoflengthLhops.Then,afterreceivingLmessages,anadversarywillbeabletotrace forwardtothedestinationnodeD,i.e., DDI=1L.Ifthereare ndisjointroutingpathsbetweenthesourcenode Sanddestinationnode D,andthe lengthofthe npathsare: L1,L2,···,Ln,respectively.Foreachmessage,thesourcenode Swillsenditalongpath Liwithprobability pi,where ni=1pi=1.Forpath i,wehave DDIi=piLi,i=1,···,n.DefinetheoverallDDIas DDI=ni=1pi·DDIi.62Theorem4 SupposetherearendisjointroutingpathesbetweenthesourcenodeSandtheSINK nodeD.ThelengthsofthenroutingpathesareL 1,L2,···,Ln.Letp ibetheprobabilitythat messageswillbetransmittedalongthepathL i,thenwhenp i=LiL1+L2+···+Ln,i=1,2,···,n,theSDIisminimized,whichis DDI=1L1+L2+···+Ln.Corollary2 SupposetherearendisjointroutingpathsbetweenthesourcenodeSandthedesti- nationnodeD.ThelengthofthenroutingpathsareL 1,L2,···,Ln,respectively.Theadversary thenneedstoreceiveonaverage 1DDI=L1+L2+···+Lnmessagestofullydeterminethelocationofthedestinationnode,i.e.,traceforwardtothedestina- tionnode. Asaresult,toprovideDLPinwirelesssensornetworks,wehavetoincreasethetotalnumberof possibleroutingpathsbetweenthedestinationnodeandthesourcenode.However,forapractical networkconfiguration,thenumberofroutingpathscannotbeincreasedwithoutlimitation.This meansthatwewillalwayshave DDI>0.WecansummarizethetwodefectsoftheDLPschemesthroughfixedroutingpathesasfollows: •Non-zeroDDI:Forfixedpathrouting,nomatterhowdedicatedtheschemeisdesigned, DDIisalwayslargerthan0.Inotherwords,foreachmessagesentoutbyonesourcenode,from aprobabilitypointofview,thereisalwaysafractionofdestinationinformationtobeleaked totheadversaries.So,nomatterhowsmallthe DDIis,whenenoughmessagesarereceived, theadversariesarealwaysabletolocatethedestinationnode. •LimitedDSI:Becausetheroutingpathsarefixedtothedestinationnode,thecorrelation betweenthemessagestransmittedonaparticularpathandthedestinationnodeishigh.In otherwords, DSIissmallcomparedtotheoverallsensornetworksize. 63Figure3.1IllustrationoftheBubbleRouting 3.5Destination-LocationPrivacyusingBubbleRouting In[78],weproposetwophaseroutingschemetoprotectthedestinationlocationcalledbubble routing.Inthefirstphase,thesourcenoderandomlyselectsanintermediatenodefromapre- determinesub-region,whichwewillrefertoasthebubbleregion.Weassumethatthebubble regionislargeenoughtomakeinfeasibleforanadversarytomonitortheentirebubbleregion.In thesecondphase,theintermediatenodewillthenroutethemessagetothedestinationnode. Forthesourcenodetoestablishanintermediatenode,itmustdothefollowingsteps.Thefirst stepistorandomlyselectalocationwithinacircularareaofradius Raroundthedestinationnode. Weassumethateachsensornodeonlyhasknowledgeofitsadjacentnodesrelativelocationand thedestinationnoderelativelocation.Let x0;y0representtherelativelocationofthedestination 64node.Fromtheseperimeters, x0;y0;R,thesourcenodeisabletogeneratearandompointwithin thepre-determinearea.Sinceweassumethatthedestinationnodeislocatedattherelativelocation (x0;y0),thesourcenodeselectstherandomlocation (xc;yc)accordingtothefollowingprocedures: 1.Randomlyselect dcuniformlyfrom [0,R].2.Randomlyselect cuniformlyfrom [0,2].Inthisway,wecancalculatethecoordinateoftherandomselectedpointas (xc,yc)=(x0+dccos(c),y0+dcsin(c)).Afterobtainingtherandompoint (xc;yc),inthesecondstep,thesourcenodewillgenerate anotherrandompointlocatedwithinacircularareaofradius raroundtherandompoint (xc;yc).Wewillcallthepoint (xc;yc)thecenterpointforpre-determinesub-region.Wewillreferthis pre-determinesub-regionwithradius rasthebubbleregion.Also,weassumethat rissmaller thanR.Nowwiththenewperimeters, xc;yc;r,thesourcenodecanrandomlygenerateapoint (xi,yi)todetermineanintermediatenode.Wecancomputetherandomlocation (xi,yi)accordingtothe followingprocedures: 1.Randomlyselect diuniformlyfrom [0,r].2.Randomlyselect iuniformlyfrom [0,2].3.Calculate (xi,yi)=(xc+dicos(i),yc+disin(i)).Aftercalculatingtherandomselectedpoint, (xi,yi),thesourcenodewillthenroutethemessage towardsthegridthatcontainsthelocation (xi,yi).Sinceeachnodeknowsitsadjacentneighbor nodesâ˘A´Zrelativelocation,itcandeterminethedirectionthatthemessageshouldberoutedto. Oncethemessageiswithinthedesiredgridoftherandomlocation,themessageisroutedtothe headernodeofthegrid.Theheadernodethenbecomestherandomintermediatenode.Ifthe desiredgriddoesnotcontainanynodes,thenthelastnodeintheroutingpathwouldbecome 65thedesiredlocationandtheheadernodeinthatgridwouldbecometheintermediatenode.We assumethatwhennodedetectsanevent,itwillsendmessagesperiodically.Foreverymessage thatiscreatedfromasourcenode,theintermediatenodelocationwillbegeneratedusingthe parametersxc;yc;randsourcenodewillcalculatedanewpointforeachmessage.Inotherwords, thesourcenodewillsendeachmessagetoadifferentintermediatenodelocatedinthesamebubble area.Also,eachsourcenodeinthenetworkwilldetermineitsownbubbleregionbyusingthe stepsdescribedabove.Figure3.1illustratetheBubbleroutingscheme.Whensourcenode1 sendsamessage,itwillforwardthemessagetothebubbleregion1andsourcenode2willforward messagestobubbleregion2.Asyoucansee,themessageroutesfromthesourcenodewillnotlead anadversarydirectlytothedestinationnode.Oncetheintermediatenodereceivesthemessage, thenthemessageisforwardtothedestinationnode. Toincreasethesecurityonprotectingthedestination-location,wewillinjectfakemessages intothenetwork.Astherealmessageisbeingroutedinthenetworkbyahop-by-hopapproach, everynodeintheroutingpathwillhavetheprobability, pfake ,togenerateafakemessage.The realmessageandthefakemessageswillbeindistinguishabletotheadversaries.Bymixingreal messageswithfakemessageswillmakeitmoredifficultforanadversarytodeterminethedirection oftheroutingpathoftherealmessage.Anodethatgeneratesafakemessagewillrandomlyselect aneighbornodetosendthefakemessagetoandalsowillforwardtherealmessagetothenextnode intheroutingpath.Thefakemessagewillhaveapre-determinedtime-to-live( TTLfake )parameter associatedwithit.Asthefakemessagepassesinthenetwork,foreachhopittakestheparameter TTLfake decreasesby1.Thenodethatreceivesthefakemessagewith TTLfake =0willdiscard thefakemessage.Also,whennodesreceivefakemessages,theycancreateanotherfakemessage withprobability pfake .Thepurposeof TTLfake parameteristolimittoenergyconsumptionused ininjectingthenetworkwithfakemessages.Werefertothisroutingschemeasthebubblerouting scheme.Inbubbleroutingscheme,thesecuritystrengthinprotectingthedestination-locationrelyonthe parameters,r;R;pfake ;TTLfake .Toincreasethesecurityofthisschemeyoucansimplyincrease 66anyoftheparameters r;R;pfake ;TTLfake .Increasinganyoftheseparameterswillalsoincrease theenergyconsumption.Foranydestination-locationprivacyschemes,therewillbeatradeoffin securityandenergycost.Ourgoalistoshowthatasmallincreaseintheenergycostcancausea hugeincreaseinsecurityprotectionofthedestination-location.Inthenextsection,wewillanalysis thesecurityofourproposedbubbleroutingschemeandotherwellknownexistingschemes. 3.5.1SecurityAnalysisforBubbleRouting Inthissection,wewillanalyzethattheproposedbubbleroutingschemecanprovidedestination- locationprivacy.Also,wewillanalysisotherdestination-locationprivacyschemesanddetermine itsvulnerabilitiesfordifferentadversaryattacks. Theorem5 Fortheproposedbubblescheme,ifassumethatthebubbleareaislargeenoughso thattheprobabilityformultiplemessagestoberoutedusingthesameintermediatenodeisnegli- gible.Thentheamountofdestination-locationinformationthatcanbeleakedfromonemessage isnegligible,i.e., DDI0,andDLPwithlocaldegree0. DEEProuting[37]andLPRroutingwithfakepacketinjection[76]havesimilaradversary attackvulnerabilities.Weassumethatanadversaryhavefullknowledgeoftheroutingprotocol thatâ˘A´ZsbeingusedintheWSNs.WiththeDEEPprotocol,thevulnerabilityisthatthereal messageisalwaysforwardtowardsthedirectionofthedestinationnode.Inotherwords,thereal messagewillalwaysbeforwardonarandomshortestpathtothedestination.Thetrafficonthese randomshortestpathswillbeheavierthanthefakemessagesroutingpaths.Also,thenumber nodesinvolvedinforwardingtherealmessages,fromsourcetodestination,willbesmalldueto thesmallnumberpathstherealmessagecantake.Figure3.2illustratetheDEEPschemeroutinga realmessagetothedestinationnode.Fromthefigure,theshortestrandompathforthemessageto takefromsourcetodestinationis6hops.Asyoucansee,therealmessagecanonlytakeasmall 67Figure3.2IllustrationoftheroutingformessagesintheDEEPscheme numberofrandompathstoreachthedestinationin6hops.TheLPRprotocolwithfakepacket injectionsattemptstosolvethevulnerabilityoftheDEEProuting.TheLPRprotocolrandomizes theroutingpathssothattheforwardingdirectionoftherealmessageisnotalwaystowardsthe directionofthedestinationnode.ThevulnerabilityoftheLPRschemeisthatanadversarycan usetoitsadvantagetheknowledgethatmorethan50percentoftherealpacketswillbeforward towardsthedestinationnodeandallofthefakepacketswillbeforwardawayfromthedestination. Therefore,iftwopacketsareforwardinthesimilardirectionfromthesamenode,theadversary willknowthatdestinationnodeisnotinthatdirection.ThevulnerabilitiesoftheDEEPandLPR schemeswillbesolvedwithourproposedscheme. OurbubbleroutingschemeaddressesthevulnerabilitiesoftheDEEPandLPRroutingschemes. Inourscheme,randomintermediatenodesareselectedfromabubbleregion.Weassumethatthe 68bubbleregionislargeenoughthatitwouldbeunpracticalforanadversarytomonitorentirely. Fromtheprobabilitypointofview,foralargenetwork,thechancesthatthemessageswillbe routedusingthesamepathandthesameintermediatenodeareextremelylow.Theincreasein thenumberroutingpathstotheintermediatenodesinthebubbleregionsolvesthevulnerabilities oftheDEEProutingscheme.Inadditiontotheincreaseofroutingpathsfortherealmessages, ourschemealsoinjectsfakemessagesintothenetworktomakemoredifficultforanadversaryto discoverthedestination-location.TosolvethevulnerabilityoftheLPRscheme,thefakemessages areforwardtoanyrandomneighbornode.Therefore,basedofftransmissionoffakemessages, anadversarycannoteliminateanareainthenetworkofwherethedestinationnodemaynotbe located.Also,ifanadversarydiscoversanintermediatenode,hewillbelocatedinthebubble region.Formostcases,thebubbleregionwillnotcontainthedestinationnode.Afterdiscovering thebubbleregion,anadversary’sworkisonlyhalfwaydone.Thesecurityanalysisshowsthatour proposedbubbleroutingschemecanprovidemuchbettersecurityinprotectingthedestination- locationprivacyincomparisontotheDEEPandLPRroutingschemes. 3.6DestinationLocationPrivacyusingR-STaRRoutingSchemes 3.6.1R-STaRRoutingProtocol TheReverse-STaRDLPschemeissimilartotheSTaRroutingschemediscussedintheprevious chapter.InsteadoftheSTaRareabeinglocatedaroundtheSINKnode,theSTaRareaislocated aroundthesourcenode,whichwecallittheReverse-STaRorR-STaRarea.R-STaRrouting schemeprovidesdestination-locationprivacythroughatwo-phaseroutingprotocol.Inthefirst phase,thesourcenoderoutesthemessagetoarandomlyselectedintermediatenodelocatedin apre-determineregionaroundthesourcenode.WecallthisregiontheReverseSinkToroidal Region(R-STaR).OppositeoftheSTaRroutingscheme,therandomintermediatenodeactasa fakedestinationnode.Inthesecondphase,theintermediatenodeintheR-STaRareawillforward themessagetotheSINKnodeusingsingle-pathrouting. 69oSource (x,y)RSrSRS-rSR-STaR area Figure3.3DistributionoftheR-STaRarea Inourscheme,thenetworkisevenlydividedintosmallgrids[73].Weassumethatthesensor nodesineachgridareallwithinthedirectcommunicationrangeofeachother.Ineachgrid,the headernodecoordinatesthecommunicationwithotherheadernodesnearby.Weassumethatthe wholenetworkisfullyconnectedthroughthemulti-hopcommunications. Thegoaloftheproposedschemeistoprovidedestination-locationprivacywithadequate 70energy-efficientrouting.Destination-locationprivacyisobtainedbyusingthisschemebecause thesourcenodewillnotleakanyinformationofthedestinationnodelocationasthemessageis routedtotheintermediatenodesinthefirstroutingphase.Sincetheintermediatenodeservesas afakelocationofthedestinationnodeinthefirstroutingphaseandcanbelocatedanydirection ofthesourcenodewithequalprobability,anadversarywillbeunabletodeterminethedestination nodesub-arealocationbyjustmonitoringmessagestransmittednearthesourcenode.Therefore, theR-STaRroutingschemecanprovideadequateglobaldestination-locationprivacy Globalprivacyisobtainedbythefactthatthemessagesfromthesourcenodetotheinterme- diatenodewillnotprovideanyinformationastoaanysub-areawherethedestinationnodemay belocated.WeassumethattheR-STaRareawouldbealargeareawithatleastaminimumradius distancerfromthesourcenode.Also,theR-STaRareaguaranteesthattheintermediatenodeisat mostamaximumdistance Rfromthesourcenodetolimittheenergyconsumptionintherouting pathsinthefirstphase.Thisroutingschemeisdesignedtogivetheillusionthatthedestination nodecanlocatedinallthepossibledirections.Inthisway,theR-STaRcreatesaneffectthatis similartothetotallyrandomRRINscheme[75]butwithlessenergyconsumptionandshorter routes.Weassumethateachsensornodeonlyhasknowledgeofitsadjacentnodesandhasnoaccurate informationofthesensornodesmorethanonehopaway.Wealsoassumethateachnodehas knowledgeoftheparametersthatareshowninFigure3.3.Thedescriptionoftheparametersare asfollows: •xS,yS:ThecorrespondingXandYcoordinatesofthesourcenodelocation, •RS:Thepre-determinedradiusfromthesourcetotheouter-edgeoftheR-STaRarea, •rS:Thepre-determinedradiusfromthesourcenodetotheinner-edgeoftheR-STaRarea. Fromtheseparameters, {xS,yS,RS,rS},thesourcenodesareabletogeneraterandompoints withintheR-STaRarea.Sinceweassumethatthesourcenodeislocatedattherelativelocation 71(xS,yS),thesourcenodedeterminesintermediatenodelocation (xi,yi)accordingtothefollowing steps:1.Randomlyselect diuniformlyfrom [rS,RS].2.Randomlyselect iuniformlyfrom [0,2].3.Calculatethecoordinateoftheintermediatenodeas (xi,yi)=(xS+dicos(i),yS+disin(i)).Afterobtainingtherandomlocation (xi,yi),themessagecanthenberoutedtowardsthegrid thatcontainsthelocation (xi,yi).Sinceeachnodeonlyknowsitsadjacentneighbornodes’relative location,itcandeterminethedirectionthatthemessageshouldberouted.Oncethemessageis withinthedesiredgridoftherandomlocation,themessageisroutedtotheheadernodeofthe grid.Theheadernodethenbecomestherandomintermediatenode.Ifthedesiredgriddoesnot containanynodes,thenthelastnodeintheroutingpathwouldbecomethedesiredlocationandthe headernodeinthatgridwouldbecometheintermediatenode.Theintermediatenodethenroutes thereceivedmessagetothedestinationnodeusingsingle-pathrouting. Toprovideadditionalsecurityforthesecondphaseroutingpath,wewillhavethedestination nodeinjectfakemessagesintothenetwork.Whentherealmessageisreceivedbythedestination node,thedestinationnodewillgenerateafakemessageintothenetworktogivetheillusionthat themessageiscontinuedtobeforwardinthenetworktohidetheidentityofrealdestinationnode. Withoutthisadditionalsecurityfeature,anadversaryisabletolocatetherealdestinationnode locationbysimplydeterminingwherethelasthopnodeofthemessageroutingpath.Butby addingthesecurityfeatureofhavingthedestinationnodeforwardafakemessage,uponreceiving therealmessage,alongthesamepathtrajectoryoftherealmessage,anadversarywillnotbe abletodistinguishdestinationnodefromanyoftheforwardingnodesintheroutingpath.This additionalsecurityfeaturewillprovidelocalnetworkprivacyforthedestination-location. Forconservingtheenergyofthenetwork,thefakemessagethatisgeneratedbytherealdesti- nationnodewillhavecertainTime-To-Live(TTL)valueforthenumberofhopstheitisforwardin 72thenetwork.WewilldenotetheTTLvalueforthefakemessageas NTTLandcanbedetermined bythefollowingequation, NTTL=·Nhop ,whereisarandomgeneratedvaluefrom [0,1]andNhop isthehopcountoftherealmessage fromthesourcenodetothedestinationnode.Ifthesourcenodeislocatedwithin10hopsfromthe destinationnode, NTTLwillbederivedas, NTTL=(·Nhop )+10,Nhop <10,toensurethatthefakemessagewillforwardatleast10hopsawayfromthedestinationnodewhen thesourcenodeislocatedisnearthedestinationnode. Thefakegeneratedmessagemusttakethesamepathtrajectoryastherealmessageasitwas routedfromtheintermediatenodetothedestinationnode.Andtodoso,wemustdetermine thefollowingvalues: df,f,Xf,Yf.Where (Xf,Yf)arethecoordinatesofarandompointon thetrajectorypathforthefakemessageroute.Todeterminethisrandompoint,wemustfirst determinedf,whichisthedistancefromthedestinationnodetotherandomfakepoint (Xf,Yf).Thedestinationnodewilldetermine dfasfollow, df=Tr·NTTL,whereTristhetransmissionrange(inmeters)ofwirelesssensordevices.Thisequationsensure thattherandomfakepoint, (Xf,Yf),willbeatleast NTTLhopsfromthedestinationnode. Second,wemustdeterminethe f,whichistheangleofmessagepathtrajectoryfromthe destinationnodetothefakerandompoint.Todoso,wemustdeterminetheslopeoftrajectory pathoftherealmessagefromtheintermediatenodetothedestinationnode,whichwewilldenote thisslopeas mslope .Let (Xi,Yi)and(Xd,Yd)representthecoordinatesoftheintermediatenode anddestinationnode,respectively.Therefore, fcanbedetermineasfollow, f=tan −1(mslope )=tan −1((Yd−Yi)/(Xd−Xi)).73With dfandf,wecandeterminetherandompoint (Xf,Yf)asfollow, •Xf=cos(f)·df+Xd•Yf=sin(f)·df+Yd.Nowwiththerandompoint (Xf,Yf),thedestinationnodecansendthefakegeneratedmessage onthesametrajectorypathastherealmessage.Thefakemessagewillonlybeforwardinthethe directionoftherandom (Xf,Yf)pointfor Nhop hops.Ifthefakemessagereachanodeontheedge ofthenetwork,thisnodeintheforwardingprocesswilldiscardthefakemessageandactasthe destinationnodeofthemessage. 3.6.2R-STaRRoutingProtocolwithFakeDestinationNodes Toenhancethesecurityfordestination-locationprivacyusingtheR-STaRroutingscheme,we willhavethesourcenodesendmessagestofakedestinationlocations.Thepurposeistoprovide global-networksecurityforthesecondroutingphaseintheR-STaRroutingscheme.Inthesecond phaseoftheR-STaRroutingscheme,themessagetransmitsfromtheintermediatenodestothe destinationusingshortest/singlepathrouting.IfallmessagesaretransmittedfromtheR-StaRarea tothedestinationnodedirectly,thesecondphasepresentssomesecurityvulnerabilities.Tohelp preventsomeofthesesecurityvulnerabilities,wedesignedtheR-STaRroutingschemewithfake destinationnodes. Thefakedestinationnodeswillbelocated,relatively,thesamedistancefromthesourcenodeas therealdestinationnode.Lettherealdestinationlocationcoordinatesbe (XD,YD)andthedistance fromthesourcenodetotherealdestinationnodebedenotedas dD.Thefollowingstepswilltaken bythesourcenodetodeterminearandomfakelocation: 1.Randomlyselect funiformlyfrom [0,2].2.Calculatethecoordinateofthefakedestinationlocationas (Xf,Yf)=(XS+dDcos(f),YS+dDsin(f)).74Toincreasesecurityofthisscheme,thesourcenodewillgenerate nffakedestinationlocations toroutethemessagesto.Anincreasein nfisanincreaseinsecurityinthesecondroutingphase fortheR-STaRroutingscheme.Therefore,foreachfakedestinationnodelocation,thesource nodewillhavetogenerate nfrandomcoordinatesasfollow: •Letirepresentvalues [0,..., nf].•Randomlyselect ifuniformlyfrom [0,2].•Calculatethecoordinateofthe ithfakedestinationlocationas (xif,yif)=(xS+dDcos(if),yS+dDsin(if)).TheSourcenodewillsendmessagestofakedestinationlocation (xif,yif)atprobabilityrate, whichwillbedenotedas pD.Eachfakedestinationnodelocationwillhaveevenprobability tobeselectedbythesourcenodeasthedestination.Also,atthesameprobabilityrate pD,the sourcenodewillhaveinselectingtherealdestinationnodeasthelocationtoroutethemessageto. Therefore,wehave pD=1nf+1.Fromthisequation,wehavethefollowingfindings: •ifnf=0,pD=1,theneverymessagewillberoutedtotherealdestinationnode(Theoriginal R-STaRroutingscheme); •ifnf=1,pD=0.5,then50%ofthemessageswillberoutedtotherealdestinationnode and50%willberoutedtothefakedestinationnode; •ifnf=2,pD=0.333...,then33 .3%ofthemessageswillberoutedtotherealdestination nodeD,33 .3%willberoutedtofirstfakedestinationnode D1f,33 .3%willberoutedto secondfakedestinationnode D2f.Wemustkeepinmindwhenasourcenodedetectanevent,thesourcenodewilltransmitmessages periodicallyaslongasitisstilldetectinganevent.Priortodetectinganevent,thesourcenode 75willgenerate nfrandomfakedestinationnodelocations,similartoexampleshownonTable3.1. Eachsourcenodeinthenetworkwillcreateitsowndistinguishdestinationnodelocationtable. Foreachmessagetransmitted,thesourcenodewillgeneratearandomintermediatenodelocation withintheR-STaRareaforthefirstroutingphaseandfromthelistof nfrandomfakedestination nodelocationsandtherealdestinationnode,thesourcenodewillrandomlydetermine,foreach message,ifthemessagewillbesenttotherealdestinationnodeoroneofthe nffakedestination nodesforthesecondroutingphase.Eachfakedestinationandrealdestinationnodelocationcan beselectedatanequalprobabilityrateof pD.WithusingtheR-STaRroutingschemewithfake destinationnodelocations,wecanprovideroutingsecurityforbothphasesintheroutingpath withoutanyadditionalenergyconsumptionincomparisontotheoriginalR-STaRroutingscheme. Dest.Nodes (withnf=4)CoordinatesProbability (pD)D(RealDest.Node) (xD,yD)pD=1/(nf+1)=0.2D1f(x1f,y1f)pD=0.2D2f(x2f,y2f)pD=0.2D3f(x3f,y3f)pD=0.2Dnff=D4f(x4f,y4f)pD=0.2Table3.1Exampledestinationnodelocationtablewith nf=43.6.3R-STaRRoutingProtocolmixwithCost-AwareRouting(CAR) Thecost-awarerouting(CAR)algorithmthatwasproposedin[79].CARwasdesignedtoprovide anenergy-efficientroutingtechniqueforsource-locationprivacy.FortheproposedR-STaRrouting mixwithCARroutingisatwo-phaseroutingschemetoprovidebalancedenergy-efficientrouting algorithmfordestinationlocationprivacy.ThefirstphaseroutingisthesameastheR-STaRrouting wherethemessagewillberoutedtoarandomintermediatenodelocatedintheR-STaRareabut usingCARenergy-efficientroutingtechnique.Inthesecondphase,themessagewillberoutedto therealdestinationnodeorafakedestinationnodelocationusingCARenergy-efficientrouting technique.R-STaRmixwithCARroutingcanprovideanadditionalsecurityfeatureduetothe 76factthatCARroutingrandomizesandincreasesthenumberofroutingpathsfortherealmessage totakefromsourcenodetointermediatenodeandfromtheintermediatenodetothedestination node.WithoutCARrouting,inthefirstroutingphasetransmitthemessagetotheintermediate nodeusingshortestpathroutinganddoesthesameinthesecondphasewhentransmittingfrom theintermediatenodetothedestinationnode. 3.6.4SecurityAnalysisforR-STaRRoutingSchemes Inthissection,wewillanalyzethesecurityfortheR-STaRrouting,R-STaRroutingwithfake destinationnodesandR-STaRmixwithcost-awarerouting.Weassumethattheadversaryis unabletomonitortheentirenetworkandcanonlytraceforwardtothenextnodethatisonehop awaywitheachtransmittedmessageinthenetwork.Wewillanalyzethesecurityallthreeproposed schemesbyanalyzingthesecurityofeachroutingphase. 3.6.4.1FirstRoutingPhase ForR-STaRandR-STaRwithfakedestinationnoderoutingschemes,thefirstroutingphaseis thesame.Inthefirstroutingphase,thesourcenoderoutethemessagetoarandomintermediate nodelocatedinR-STaRareausingtheshortestroutingpath.FortheR-STaRmixwithCost-Aware Routing(CAR),thefirstroutingphaseusesCARalgorithmwhenroutingthemessagefromthe sourcenodetotherandomintermediatenodelocatedintheR-STaRarea.Besidesthedifferences intheroutingtechniquethatisusedinroutingthemessagetotherandomintermediatenode,all threeschemesroutesthemessagetoanintermediatenodeinfirstroutingphasethatcanbelocated inanydirectionnotassociatedwiththelocationofthedestinationnode.Therefore,inthefirst routingphaseforallthreeschemes,noinformationisleakedaboutthedestinationnodelocation byanalyzingtrafficinthefirstroutingphase. Theorem6 Fortheproposedschemes,ifassumethattheR-STaRareaislargeenoughsothat theprobabilityformultiplemessagestoberoutedusingthesameintermediatenodeisnegligible 77andequalprobabilityofselectinganintermediatenodefromallpossibledirections.Therefore, theamountofdestination-locationinformationthatcanbeleakedfromallmessagesinthefirst routingphaseisnegligible,i.e., DDI0,andDLPwithlocaldegree0. Also,DSIwillincludeallnodesinthenetworkaspossibledestinationnodes.Therefore, DSI =N,whereNrepresentthenumbernodesintheentirenetworkenvironment,and NDSI =DSI N=1..3.6.4.2SecondRoutingPhase ToanalyzethesecurityforthesecondroutingphasefortheR-STaR,R-STaRwithfakedestination nodeandR-STaRmixwithcost-awarerouting,wewillassumethattheadversaryhaveidentified theentireR-STaRareadimensionsandistryingtomonitormessagesinthesecondroutingphase. Forsimplicity,wewillfurtherassumethatnetworkenvironmentisacircleregionwitharadius RN,asseeninfigure3.4.Tohelpanalyzethesecuritystrengthoftheproposedroutingtechniques, wewillbreaktheentirenetworkenvironmentinto3regions. •Region1:Thesourcenoderegionofthenetwork.Thisregionhavearadius rwiththesource nodebeingthecenterlocationoftheregion. •Region2:TheR-STaRregionofthenetwork.Thisregionhaveouterradiusof Randinner radiusof r.Itislocatedaroundthesourcenodelocation. •Region3:OutsidetheR-STaRregion.Thisregionistheremainingareaofthenetworkthat isoutsideofregion1andregion2. 78RNFigure3.4CircleGridLayoutNetworkEnvironmentwithradius RNThesecondroutingphasetransmittherealmessagefromtherandomintermediatenodetoa destinationnode.Recall,uponthedestinationnoderetrievingeachrealmessage,thedestination nodewillgenerateandtransmitafakemessageintothenetwork.Thefakegeneratedmessage willbesentinthenetworkforrandomnumberofhops, NTTL,onthesametrajectoryasthereal messagehelpconcealthedestinationnodelocationandidentity.Tofurtherhelpanalyzetherouting techniques,wewillbreaktheroutingpathintoroutingphases. •RoutePhase1: SImr:Theroutingpathoftherealmessage, mr,fromthesourcenode, S,totherandomintermediatenode, I.•RoutePhase2: IDmr:Theroutingpathoftherealmessage, mr,fromtherandom intermediatenode, I,totherealdestination, D.79CSN1N2Seg A,BR-STaR Network Environment Region 1 Region 3 ABRegion 2 Figure3.5IllustrationforanalyzingthesecuritystrengthusingR-STaRrouting •RoutePhase3: DDfmf:Theroutingpathofthefakemessage, mf,fromthereal destination,D,tothefakedestinationnode, Df.WiththeassumptionthattheadversaryknowslocationandthedimensionsoftheR-STaR area,wewillanalyzehowmuchinformationanadversarycangainfromobservingonemessage transmittedfromnode N1,inregion2(R-STaRarea),tonode N2,inregion3.Ifanadversary observesacommunicationbetweenanodeintheR-STaRareaandoneoutsidetheR-STaRarea, heisabletoassumethatthemessageistransmittingonthesecondorthirdroutingphase.For analyzingpurposes,theadversaryassumethatthemessagesarebeingroutedintheroutephase 2:IDmr.Withthedescribedassumptions,wemustanalyzehowmuchinformationis leakedtoadversarywithobservingonemessage,onehopoutsidetheR-STaRareawhenusingthe proposeddestinationlocationprivacyR-STaRroutingtechniques.Figure3.5helpsillustratethe communicationbetweennode N1andnode N2.Ifanadversaryisabletoobserveonemessagetransmissionfromanode N1andnode N2andassumethatthemessageisroutedonthesecondphase,anadversarycanassumethatthemessage willberoutedonthesametrajectoryastheanglebetweenthetwonodes.Withtheinformationthat themessagewillberoutedonashortestpathtothedestination,theanadversarycanassumethat thedestinationnodewouldbelocatedgiveortake90degreesfromthetrajectorypath,providing thatthelayoutofthenetworkisgridasshowninfigure3.4.Infigure3.5,thearrowfrom N2showstheassumetrajectoryofthemessage. Seg A,Barearepresenttheareathatanadversarycan assumewherethedestinationnodecanbelocated.Table3.2definesthevariablesinfigure3.5and thesevariableswillbeusedtoanalyzedthesecuritystrengthoftheproposedDLPR-STaRrouting schemes.80Variables DescriptionsRNRadiusoftheNetworkEnvironment(N.E.) CCenterpointoftheNetworkEnvironment N1Thenodelocationone-hopinsidetheR-STaRareainRegion2 N2Thenodelocationpointone-hopoutsidetheR-STaRareainRegion3 A,BAnglefromcenter CoftheN.E.topoints AandBSeg A,BSegmentregionbetweenpoints AandBTable3.2TableofvariablesanddescriptionsforanalyzingsecurityoftheproposedR-STaR schemes.Thesegmentarea, Seg A,B,canbedetermineusingthefollowingequation: Seg A,B=R2N2·(180·A,B−sin(A,B)).WhenusingtheoriginalR-STaRroutingtechniqueandobservingthecommunicationbetween N1andN2,theamountofinformationthatcanbeleakwhenassumingthemessageisinroute phase2: IDmr,canbedeterminedasfollow: LetDSI =Seg A,BandNDSI =DSI TheEntireNetworkArea .Therefore,DSI =R2N2·(180·A,B−sin(A,B)),NDSI =Seg A,B·R2N,NDSI =12··(180·A,B−sin(A,B)).81ForR-STaRroutingschemewithfakedestinationnodes,thesecondroutingphasetransmitthe realmessagefromtherandomintermediatenodetoarealorfakedestinationnodesusingshortest pathrouting.Ifanadversaryobservesthecommunicationbetweennode N1andnode N2,the adversarywouldnotknowifthemessageisbeingroutedtowardstherealdestinationoroneof thefakedestinations.Therefore,theR-STaRroutingschemewithfakedestinationnodeswould provideagreatersecuritythanjusttheoriginalR-STaRroutingscheme.Increaseinthenumberof fakedestinationnodes,willprovideanincreaseinthesecurityforthesecondroutingphaseusing thisscheme. ForR-STaRroutingmixwithcost-awarerouting(CAR)scheme,thesecondroutingphase transmittherealmessagefromtherandomintermediatenodetotherealdestinationusingcost- awareroutingtechnique.Sincethisschemedoesnotusetheshortestpathroutingduringthesecond phase,anadversarycannotassumethedirectionand/orsub-areaofwherethedestinationnode maybelocatedbyonlyobservingthecommunicationbetweennode N1andnode N2.Therefore, theR-STaRroutingmixwithCARschemewillprovidegreatersecuritythantheoriginalR-STaR routingscheme. Toprovideagreatersecurityscheme,wecancombineourR-STaRroutingwithfakedestination nodesschemeandourR-STaRroutingmixwithCARroutingscheme.Usingthesecombination ofschemes,thesecondphasewouldtransmittherealmessagetotherealorfakedestinations usingCARroutingtechniqueinsteadoftheshortestpathrouting.Withthecombinationofthetwo schemescanprovetobeprovideverystrongdestinationlocationprivacyschemebyeliminating anyvulnerabilitiesthateitherschememaypresentwhenusedalone. 3.6.5PerformanceAnalysisandSimulationResults Toevaluatetheperformanceoftheschemesproposed[80],extensivesimulationshavebeencon- ductedusingns-2onRedHatLinuxsystem.TheresultsofthesimulationsareshowninFigure 3.6andFigure3.7.Inthesimulation,400nodesareevenlydistributedinasquaretargetareaof size2100 ×2100metersnetworkenvironment.Weillustratetheperformanceofthetotallyran- 82domlyselectedintermediatenodes(RSIN)andtheR-STaRroutingprotocol.ForRSINscheme, thesourcenodecanselectanynodeinthenetworkastheintermediatenodewithequalprobability outsidearadiusminimumdistanceof dmin.Weset dmintoequal395meters.ForR-STaRrouting, theinnerradius, r,wassetto395meters,whiletheouterradius, R,wassetto605meters. Throughanalysisandsimulationresults,wefindthatR-STaRprotocolprovidethebestresults. R-STaRprovidessimilarlevelofsecurityastheRSINschemebutwithlessenergyconsumption andshorterdelays. Packet / Bytes Delay / Seconds Figure3.6MessageLatency 83Packet / Bytes Energy / Joules Figure3.7EnergyConsumption 84CHAPTER4 Q-RECHSCLUSTER-BASEDENERGYEFFICIENTROUTINGINWIRELESS SENSORNETWORKS 4.1Introduction Withthepopularityofwirelesssensornetworks,manyissueshavebeenraisedoverthepastsev- eralyears.ProlongingthelifetimeofWSN’siscriticalconcern.OneoftheusageofWSN’sis toprovidereal-timeeventmonitoringfunctionality.Todoitsjob,thedeviceenergymustbea highpriorityforthesedevicestoperformitsfunctionality.Inanetworkenvironment,havinga portionofthenetworkfilledwithdeaddevicesdoesnotservemuchpurpose,thereforewewill definethenetworklifetimeasthetimescale(rounds)ittakesforcertainpercentageofthenet- worknodestodie.Inthischapter,weproposedacluster-basedenergy-awareroutingscheme calledQuad-RegionCluster-HeadSelection(Q-ReCHS),thatwillprolongthenetworklifetimeby evenlydistributingtheenergyloadamongallthenodes.Wewillprovidesimulationresultsusing definedmetricsformeasuringlifetimeofthenetwork:First-To-Die(FTD),Half-To-Die(HTD), andLast-To-Die(LTD).WewillmeasurethenumberofpacketssenttotheBaseStation(BS)and numberroundsittakeforschemestoreachthedefinedmetrics. 4.2RelatedWork ManydifferentapproacheshavecarriedouttodesignfeasibleWSNs.Energyconservationis crucialtoprolongthenetworklifetimeofWSNs.Manyapproachesforenergyefficientrouting havebeenproposedtoreduceenergyconsumption.Onealternativeapproachtoconserveenergy isusingclusteringtechnique.Inaddition,whenscalabilityisconsideredtobeamajorproblem whennetworkdensityisofhundredsandthousandsofnodesthenclusteringisconsideredtobe ausefultechnique.InvariousWSNsapplications,routingefficiencyisconsideredimportantfor 85energyefficiency,loadbalancing,anddatafusion[81].Inthischapter,weareconcernabout Cluster-Head(CH)selectionschemesanddiscusssomeoftheassociatedschemes. LowEnergyAdaptiveClusteringHierarchy(LEACH)[82]iswellknowclusteringalgorithm inwhichtheCHintheclusterisperiodicallyrotatedamongmemberstoachieveenergybalance. However,thisschemeshowedonlypartialsuccess,itneedsanewclusterformationprocessat everysection.Withclusterformation,ineachclusteranewCHnodeisre-electedwithrandom probability,andfromthepromisingCHcandidates.Theoptimalnodeshouldbeadaptivelyop- timizedforminimumcommunicationdistancestothemaximumnumberofonehopneighbors. Thisonlyproduceworstsuboptimalsolutionduetoclusterre-electionprocess,whichresultsin thenodestospendadditionaldelayandenergy.Inaddition,LEACHdoesnottakeinaccountthe remainingenergyofthenodeintheCHselectionprocess. In[64],theauthorsproposedaprotocolcalledHEED,whereanodeusesitsparameterscom- municationcostbetweenCluster-Members(CM)andremainingenergytoprobabilisticallyelect itselftobecomeaCH.HEEDisamulti-hopclusteringalgorithmforWSNs.Theremainingen- ergyofeachsensornodeisusedtoprobabilisticallydetermineandchoosethefirstsetofCHs, asusuallyperformedinotherclusteringtechniques.In[64],communicationcostbetweenthe Cluster-Membersshowsthenodedegreeornodeasproximitytotheneighborandthemainparam- eterthatdecideswhethertojointhecluster.However,hotspotissueinHEEDappearsinareas thatareclosetothesink,asnodesinsuchareasneedtorelayincomingtrafficfromotherparts ofthenetwork.Furthermore,knowledgeofthewholeWSNsisnecessarytodeterminecommu- nicationcostbetweenCluster-Members.HEEDisadistributedclusteringmechanisminwhich CHnodesarepickedfromtheWSNs.HEEDsCHselectionparameterisahybridofenergyand communicationcost. 864.3EnergyConsumptionModel Inthispaper,weusearadiomodelproposedin[82]asradioenergymodeltomeasureenergycon- sumption.Weassumenodesdissipateenergywheneitherinthetransmitmode Txorthereceiver modeRx.Theenergyconsumedduringthetransmitmodeconsistsoftransmittercircuitry tcandtrans- mitteramplifier ta.Therefore,wehavetransmitmodeenergymodelas: Etx=(tc×k)+(ta×k×d2),(4.1)wherekisthepacketsizeinbitsand drepresentthedistanceofthetransmitrange.Theenergy consumedduringthereceivermodeconsistsofreceivercircuitry rc.Thereforewehavereceiver modeenergymodelas Erx=rc×k.(4.2)Inourwork,weusethesimilarassumptionas[82],wherehetransmittercircuitry tcandreceiver circuitryrcconsumes50 nJ/bit andthetransmitteramplifier taissetto100 pJ/bit /m2.Wealso assumethatallsensornodesaresensingtheenvironmentatafixedrateandalwaysdetectsan eventeveryround;thusalwayshavedatatosendtotheCHeachround.Listeningenergycanbe neglectedinthispapersinceallnodesactassourcenodesduringeveryround. 4.4ProposedQ-ReCHSCluster-BasedRoutingScheme Ourproposedcluster-basedroutingprotocolisdesignedtoprolongthelifetimeofthewireless sensornetwork.WecallourschemeQuad-RegionCluster-HeadSelection(Q-ReCHS).Q-ReCHS willprovideabetterevenlydistributionofenergyloadamongthenodesinthenetworkcompare tothewellknownLEACHcluster-basedroutingscheme. 874.4.1Q-ReCHSNetworkModel Inthissection,thenetworkmodelofourproposedQ-ReCHSroutingschemeisdefinedasfollows: •Nodesarerandomlydistributedthroughoutarectangularnetworkenvironment. •Eachnodeisassignedtooneoffournetworkregionsasshowninfig.4.1. •Allnodeshavesimilarcapabilities(TransmissionPowerLevels,InitialEnergy).Eachnode canbeaCluster-Member(CM)oraCluster-Head(CH). •Nodesareleftunattended,therefore,rechargingorreplacingbatteriesarenotfeasible. •Duringeachround,everyalivenodeactasasourcenodeandalltransmitonepackettothe BaseStation(BS).Aftereachround,anewsetofCHsareselected •Weuseddefinedmetricsformeasuringlifetimeofthenetwork:First-To-Die(FTD),Half- To-Die(HTD),andLast-To-Die(LTD). •NodesuseTDMAschedulewithineachcluster. •Eachnodecanuse2frequencychannelstotransmit: –IntraClusterCommunication-UniquefrequencychanneltotransmitfromCMtoits respectiveCH. –InterClusterCommunication-UniquefrequencychanneltocommunicatetootherCHs and/orBS. •Eachnodecanbeinanyofthefollowingmodes: –Cluster-Member(CM) :Regularclusternode;WhenaCluster-Member(CM)detect anevent,theCMbecomethesourcenodeandtransmitthepacketdirectlytotheits correspondedCH. 88–Cluster-Head(CH) :Serveastheheadofthecluster;CHwillreceivedpacketsfromCM withinit’scluster.AfterreceivingapacketfromCMs,CHcantransmitcompressed packetsdirectlytotheBS. 3421Figure4.1Q-ReCHSNetworkRegions:100nodes,100mx100m,BSlocated(50m,50m) 4.4.2InitializationStage Duringthenetworksetup,theBaseStation(BS)nodewillbroadcastabeaconsignalthatcovers theentirenetwork.Eachnodereceivesthebeaconsignalandusethereceivedsignalstrength todeterminethedistancetotheBS.Forprolongingthenetworklifetime,nodesusingshould minimizethetransmitpowertosendpacketstotheBS.Inthisdissertation,wewilldefinethe 89distancetotheBSas dBSi,where irepresentthe ithnodeinthenetwork. AfterthenodesestablishitscorrespondingdistancetotheBS, dBSi,eachnodewillestablish itsregionlocationwithinthenetwork.Asmentionedinsection4.4.1,thenetworkisdividedinto 4equalregions.Weassumethateachnodeknowsitsrelativelocationwithinthenetworkusinga GPSreceiverorpre-programmedlocationcoordinatesforeachnode.Usingitsrelativelocation, eachnodewillassignitsselfto1ofthe4regionsshowninFigure4.1. 4.4.3Q-ReCHSCluster-HeadSelectionProcess Accordingtothestudypresentedin[83],anetworkcontaining100nodesina100 m×100mnetworkenvironment,itwasfoundthattheoptimumnumberofclustersshouldbearound3-5to minimizetheaverageenergyconsumptionperround.Therefore,tokeepourschemewithinthe optimumrangeofCHsinthenetwork,theBSwillusethefollowingconditiontodeterminethe numberofCHsthatshouldbeassignedtoeachregion: C=N26.(4.3)Letrepresenttheregionid,where 1,2,3,4andlet Nrepresentthenumberactivenodesin thedesignatedregion.Therefore,wehave 4=1N=N(4.4)and4=1C=C,(4.5)whereNrepresentsthenumberofactivenodesinthenetworkand CrepresentsthenumberofCHs inthenetworkforthecurrentround. Todeterminethecluster-heads(CHs)inthenetwork,eachactivenode(alivenode)inthe networkwillsenditsnodeID,thecurrentremainingenergylevel,andtheregionIDtotheBase Station.Let Eirepresentthecurrentremainingenergylevelofthe ithnode.AftertheBSreceives 90theinformationfromallactivenodesinthenetwork,theBSwillthencomputetheaverageregion energylevelforallfourregions.Wedenotetheaverageregionenergylevelas Eavg,where representstheregionID.Theaverageregionenergylevelwillbecomputedasfollow: Eavg=Ni=1EiN,1,2,3,4.(4.6)Amongtheactivenodes,theBSwillcreateasubsetofnodesforeachregionthatfitthefol- lowingcondition: EiEavg.(4.7)Fromthesubsetofnodesthatsatisfyequation(4.7),theBSwillrandomlyselect Ccluster-heads foreachregion.TheselectednodeswillserveastheCHsonlyforthenextround. TheclusterswillbeformulatedbyhavingeachCHsendoutanetworkwidebeaconsignal tothenetworkwithitsnodeID.Fromthereceivedsignals,eachnodewillclusterwiththeCH withthestrongestsignalstrength(hence,closestCH)andbecomecluster-members(CM)with theclosestcluster-head.EachnodewillalignwiththeCHthatwouldrequiretheleastamount energytotransmitto.Eachcluster-member(CM)shoulduseminimumtransmitpowertotransmit apackettoaCH.Therefore,theCMwilldeterminethedistancetoitscorrespondingCHfromthe CHbeaconsignaltominimizethetransmitpowerrequiredtoreachtheCH.Wewilldenotethe distancefromCMtotheCHas dCHi.Toprovideadditionalenergyconsumptionawareness,anode canoptoutbecomingaCMifthenodedistancetotheBSislessthanthethedistancetonearest CH.Inotherwords,if dBSidCHi,(4.8)thenthenodecansaveenergybytransmittingdirectlytotheBSratherthantransmittingtothe nearestCH.ThisapproachwillprovidenetworkwideenergysavingsbecauseCHswillhaveless CMwhichwillresultinlessenergyconsumption.AfteraCMdetectsanevent,theCMwill transmitapackettoitscorrespondingCH.Forenergysavings,theCHcompressesallreceived packetsfromitsCMsusinglossycompressionbeforetransmittingtotheBS. 914.4.4SystemsAnalysis ByhavingtheCHslocatedinall4regions,thiswillsolvesomeoftheweaknessesofLEACH protocol,whereCHscanbeselectedanywhereinthenetworkwithoutconsideringthelocation thatwouldminimizethedistancethatCMswillhavetotransmittoCHs.Also,LEACHprotocol doesnotuseremainingenergyasacriteriaforselectingCHs,whichisanotherweaknessforthe LEACHprotocol,whileQ-ReCHSonlyusesenergyrichnodesasCHssinceCHswillconsume themostenergyineachround. 4.5SimulationResults Inthissection,weevaluatedtheperformanceofourproposedQ-ReCHSschemeandexisting schemes,usingMATLAB.Inoursimulation,weassumedanerrorfreephysicallayerandanideal MAClayer.Also,weassumedthattheenergyconsumptioninthetransmissionandreception ofdatapacketsfollowstheenergyconsumptionmodeldefinedinSection4.3.Wecompareour schemewiththeLEACHprotocolandtheprotocolusingdirecttransmissionfromsourcetothe BS.WecomparethesimulationbasedontheamountofpacketssenttoBSvs.numberofrounds (timescale)tomeasurethelifetimeofthenetwork:First-To-Die(FTD),Half-To-Die(HTD),and Last-To-Die(LTD). Inoursimulation,thenodesarerandomlydistributedthroughoutthenetwork,asshownin Figure4.2.Theinitialenergyforallnodesissetto0 .5J.ForQ-ReCHS,thenetworkisdivided into4equalregionareas,asshowninFigure4.1.ForLEACHprotocol,weusetheprobability P=0.05inthesimulations.Weuseseveralnetworkenvironmentstotesttheperformanceofthe schemes.Thenetworkenvironmentsaredescribedbelow: 1.N=100;Xdim =100m;Ydim =100m,2.N=150;Xdim =150m;Ydim =150m,3.N=200;Xdim =200m;Ydim =200m.9201020304050607080901000102030405060708090100Figure4.2SimulationNetworkEnvironment:100nodes,100mx100m,BSlocated(50m,50m) 93020040060080010001200012345678910x 104Number of rounds# of packets sent to BSLEACHdirectFigure4.3100Nodesin100mx100mEnvironment:First-To-Die 9402004006008001000120014001600180020000246810121416x 104Number of rounds# of packets sent to BSLEACHdirectFigure4.4100Nodesin100mx100mEnvironment:Half-To-Die 95010002000300040005000600000.20.40.60.811.21.41.61.82x 105Number of rounds# of packets sent to BSLEACHdirectFigure4.5100Nodesin100mx100mEnvironment:Last-To-Die 960100200300400500600012345678x 104Number of rounds# of packets sent to BSLEACHdirectFigure4.6150Nodesin150mx150mEnvironment:First-To-Die 970200400600800100012001400024681012141618x 104Number of rounds# of packets sent to BSLEACHdirectFigure4.7150Nodesin150mx150mEnvironment:Half-To-Die 980100020003000400050006000700000.511.522.5x 105Number of rounds# of packets sent to BSLEACHdirectFigure4.8150Nodesin150mx150mEnvironment:Last-To-Die 9905010015020025030035040001234567x 104Number of rounds# of packets sent to BSLEACHdirectFigure4.9200Nodesin200mx200mEnvironment:First-To-Die 100010020030040050060070080090002468101214x 104Number of rounds# of packets sent to BSLEACHdirectFigure4.10200Nodesin200mx200mEnvironment:Half-To-Die 1010100020003000400050006000700000.511.522.5x 105Number of rounds# of packets sent to BSLEACHdirectFigure4.11200Nodesin200mx200mEnvironment:Last-To-Die Fromthefigures,wecanseethatourQ-ReCHSoutperformstheLEACHprotocolinall thresholdsimulations.LEACHprotocoldoesnotassignCHsbasedofremainingenergyanddoes nottakeintoaccountthelocationoftheCHs.WhileQ-ReCHSselectionsclusterheadsbased onregionlocationinthenetworkandtheremainingenergytoprovidemuchevendistributionof energyconsumptionsamongthenetworknodes. 102CHAPTER5 CONCLUSIONANDFUTURERESEARCH Locationprivacyisvitaltothesuccessfuldeploymentofwirelesssensornetworks.Inthisdisser- tation,weproposeduniqueenergy-efficientschemestoprovidelocationprivacyandcluster-based energy-awarerouting.Theintroductoryfirstchapterprovidesinsightonwirelesssensornetworks andtheimportancetohavinganadequaterouting-basedlocationprivacytechnique. 5.1ConclusionforSource-LocationPrivacy Inchapter2 ,weproposedsource-locationprivacyschemes.Weprovidelimitationswithexisting schemesandproposed3uniqueSLPschemes.Thefirstoneisimplementedbyroutingthrough asinglerandomlyselectedintermediatenodewhichprovidelocallevelSLPsecurity.Thesecond oneachievesthelocationprivacybyroutinginanetwork-levelmixingringwhichprovidedglobal networkSLPsecurity.Thethirdschemeachievenetwork-levelsource-locationprivacythrough atechniquewecalltheSinkToroidalRegion(STaR)routingwhichprovidedboth,globaland locallevelSLPsecurity.Theseschemeswereexploredwiththeoreticalanalysisandsimulation results.OursimulationresultsdemonstratethatourproposedSLPschemescanachieveexcellent performanceinenergyconsumption,messagedeliveryratioanddeliverylatency. 5.2ConclusionforDestination-LocationPrivacy Inchapter3 ,weproposedseveraldestination-locationprivacyschemes.Weproposedthebubble routingschemetoprotectthedestination-locationprivacybyfirstroutingthemessagetoanbubble region.Theother3destination-locationprivacyschemesusingaroutingtechniquewecallR-STaR routingwhichisaregionlocatedaroundthesourcenode.Weprovidedtheoreticalsecurityanalysis 103foralloftheproposedDLPschemes.WealsowasabletoshowthattheR-STaRroutingscheme performancewasanimprovementcomparedtotheRSINroutingscheme. 5.3ConclusionforCluster-BasedRouting Inchapter4 ,weintroducedanewcluster-basedenergy-awareroutingprotocolforprolonging thenetworklifetimebyevenlydistributingtheenergyloadamongallthenodes.Ourscheme addressedlocationandselectionprocessfordeterminingthecluster-headswithinthenetwork. Withsimulation,wewasabletoshowthatourproposedQ-ReCHSschemewasabletooutperform somewellknownexistingcluster-basedroutingschemes. 5.4FutureWork Forourfuturework,wewilllookintotestingourQ-ReCHScluster-basedroutingschemewith otherknownschemes,suchas,LEACH-C,HEED,Q-LEACH,andCBER.Also,wewoulddesign astrongerQ-ReCHSschemethatdeterminessmartcluster-headselectionstominimizetransmit distancesandmaximizingnetworklifetime. Forotherprivacyprotectionschemes,weareworkingondesigningprivacy-awareinformation characterizationanddisclosureprotection.Withdataexposure,wewilldeveloptheminimum distributionleakagedatadisclosureforagivenentropyleakage,andtheminimumentropyleakage foragivendistributionleakage. 104BIBLIOGRAPHY105BIBLIOGRAPHY[1]F.Ye,H.Lou,S.Lu,andL.Zhang,“Statisticalen-routefilteringofinjectedfalsedatain sensornetworks,”in IEEEINFOCOM ,March2004. [2]S.Zhu,S.Setia,S.Jajodia,andP.Ning,“Aninterleavedhop-by-hopauthenticationscheme forfilteringfalsedatainsensornetworks,”in IEEESymposiumonSecurityandPrivacy ,2004.[3]A.Perrig,R.Canetti,J.Tygar,andD.Song,“Efficientauthenticationandsigningofmulticast streamsoverlossychannels,”in IEEESymposiumonSecurityandPrivacy ,May2000. [4]D.T.D.S.A.Perrig,R.Canetti,“Theteslabroadcastauthenticationprotocol,”in Crypto-Bytes,2002. [5]D.LiuandP.Ning,“Efficientdistributionofkeychaincommitmentsforbroadcastauthenti- cationindistributedsensornetworks,”tech.rep.,Raleigh,NC,USA,2002. [6]D.LiuandP.Ning,“Multilevel µtesla:Broadcastauthenticationfordistributedsensornet- works,” ACMTrans.Embed.Comput.Syst. ,vol.3,no.4,pp.800–836,2004. [7]J.DrissiandQ.Gu,“Localizedbroadcastauthenticationinlargesensornetworks,”pp.25 –25,july2006. [8]A.Perrig,R.Szewczyk,V.Wen,D.Culler,andJ.Tygar,“SPINS:Securityprotocolsfor sensornetworks,”in SeventhAnnualInternationalConferenceonMobileComputingand Networks(MobiCOM2001) ,(Rome,Italy),July2001. [9]C.Blundo,A.DeSantis,A.Herzberg,S.Kutten,U.Vaccaro,andM.Yung,“Perfectly-secure keydistributionfordynamicconferences,”in AdvancesinCryptology-Crypto’92 (E.F. Brickell,ed.),(Berlin),pp.471–486,Springer-Verlag,1992.LectureNotesinComputer ScienceVolume740. [10]N.Subramanian,C.Yang,andW.Zhang,“Securingdistributeddatastorageandretrievalin sensornetworks,” PervasiveMob.Comput. ,vol.3,no.6,pp.659–676,2007. [11]W.Zhang,M.Tran,S.Zhu,andG.Cao,“Arandomperturbation-basedschemeforpairwise keyestablishmentinsensornetworks,”in MobiHoc’07:Proceedingsofthe8thACMinter- nationalsymposiumonMobileadhocnetworkingandcomputing ,(NewYork,NY,USA), pp.90–99,ACM,2007. [12]W.Zhang,N.Subramanian,andG.Wang,“Lightweightandcompromise-resilientmessage authenticationinsensornetworks,”in IEEEINFOCOM ,(Phoenix,AZ.),April15-172008. [13]M.Albrecht,C.Gentry,S.Halevi,andJ.Katz,“Attackingcryptographicschemesbased on"perturbationpolynomials".”CryptologyePrintArchive,Report2009/098,2009. .106[14]C.K.WongandS.S.Lam,“Digitalsignaturesforflowsandmulticasts,” IEEE/ACMTrans. Netw. ,vol.7,no.4,pp.502–513,1999. [15]R.Watro,D.Kong,S.fenCuti,C.Gardiner,C.Lynn,andP.Kruus,“Tinypk:securing sensornetworkswithpublickeytechnology,”in InSASN˛ a´r04:Proceedingsofthe2ndACM WorkshoponSecurityofAdHocandSensorNetworks ,pp.59–64,ACMPress,2004. [16]N.Gura,A.Patel,A.W,H.Eberle,andS.C.Shantz,“Comparingellipticcurvecryptography andrsaon8-bitcpus,”pp.119–132,2004. [17]A.S.Wander,N.Gura,H.Eberle,V.Gupta,andS.C.Shantz,“Energyanalysisofpublic-key cryptographyforwirelesssensornetworks,”in PERCOM’05:ProceedingsoftheThirdIEEE InternationalConferenceonPervasiveComputingandCommunications ,(Washington,DC, USA),pp.324–328,IEEEComputerSociety,2005. [18]G.Gaubatz,J.-P.Kaps,E.Ozturk,andB.Sunar,“Stateoftheartinultra-lowpowerpublic keycryptographyforwirelesssensornetworks,”in PERCOMW’05:ProceedingsoftheThird IEEEInternationalConferenceonPervasiveComputingandCommunicationsWorkshops ,(Washington,DC,USA),pp.146–150,IEEEComputerSociety,2005. [19]A.LiuandP.Ning.[Online]http://discovery.csc.ncsu.edu/software/TinyECC/,2005. [20]H.Wang,S.Sheng,C.Tan,andQ.Li,“Comparingsymmetric-keyandpublic-keybased securityschemesinsensornetworks:Acasestudyofuseraccesscontrol,”in IEEEICDCS ,(Beijing,China),pp.11–18,2008. [21]H.ChanandA.Perrig,“Securityandprivacyinsensornetworks,” IEEEComputerMagazine ,pp.103–105,Oct.2003. [22]W.Du,J.Deng,Y.S.Han,P.K.Varshney,J.Katz,andA.Khalili,“Apairwisekeypredis- tributionschemeforwirelesssensornetworks,” ACMTrans.Inf.Syst.Secur. ,vol.8,no.2, pp.228–258,2005. [23]D.LiuandP.Ning,“Establishingpairwisekeysindistributedsensornetworks,”in CCS’03: Proceedingsofthe10thACMconferenceonComputerandcommunicationssecurity ,(New York,NY,USA),pp.52–61,ACM,2003. [24]H.ChanandA.Perrig,“Pike:peerintermediariesforkeyestablishmentinsensornetworks,” INFOCOM2005.24thAnnualJointConferenceoftheIEEEComputerandCommunications Societies.ProceedingsIEEE ,vol.1,pp.524–535vol.1,March2005. [25]R.L.Rivest,A.Shamir,andY.Tauman,“Howtoleakasecret,”in AdvancesinCryptology– ASIACRYPT ,LectureNotesinComputerScience,vol2248/2001,SpringerBerlin/Heidel- berg,2001. [26].107[27]P.Kamat,Y.Zhang,W.Trappe,andC.Ozturk,“Enhancingsource-locationprivacyinsensor networkrouting,” DistributedComputingSystems,2005.ICDCS2005.Proceedings.25th IEEEInternationalConferenceon ,pp.599–608,June2005. [28]D.Chaum,“Untraceableelectronicmail,returnaddresses,anddigitalpseudonyms,” Com-municationsoftheACM ,vol.24,February1981. [29]D.Chaum,“Thedinningcryptographerproblem:Unconditionalsenderandrecipientun- traceability,” JournalofCryptology ,vol.1,no.1,pp.65–75,1988. [30]L.vonAhn,A.Bortz,andN.Hopper,“ k-anonymousmessagetransmission,”in Proceedings ofCCS ,(WashingtonD.C.,USA.),pp.122–130,2003. [31]A.BeimelandS.Dolev,“Busesforanonymousmessagedelivery,” J.Cryptology ,vol.16, pp.25–39,2003. [32]P.GolleandA.Juels,“Diningcryptographersrevisited,”in AdvancesinCryptology-Euro- crypt2004 ,LNCS3027,pp.456–473,2004. [33]S.Goel,M.Robson,M.Polte,andE.Sirer,“Herbivore:AScalableandEfficientProtocol forAnonymousCommunication,”Tech.Rep.2003-1890,CornellUniversity,Ithaca,NY, February2003. [34]M.Reed,P.Syverson,andD.Goldschlag,“Anonymousconnectionsandonionrouting,” IEEEJ.onSelectedAreasinCoomunications ,vol.16,no.4,pp.482–494,1998. [35]M.ReiterandA.Rubin,“Crowds:anonymityforwebtransaction,” ACMTransactionson InformationandSystemSecurity ,vol.1,no.1,pp.66–92,1998. [36]J.Deng,R.Han,andS.Mishra,“Intrusiontoleranceandanti-trafficanalysisstrategiesfor wirelesssensornetworks,”in DSN’04:Proceedingsofthe2004InternationalConference onDependableSystemsandNetworks ,(Washington,DC,USA),p.637,IEEEComputer Society,2004. [37]J.Deng,R.Han,andS.Mishra,“Countermeasuresagainsttrafficanalysisattacksinwireless sensornetworks,” SecurityandPrivacyforEmergingAreasinCommunicationsNetworks, 2005.SecureComm2005.FirstInternationalConferenceon ,pp.113–126,Sept.2005. [38]Y.Yang,M.Shao,S.Zhu,B.Urgaonkar,andG.Cao,“Towardseventsourceunobservability withminimumnetworktrafficinsensornetworks,”in WiSec’08:Proceedingsofthefirst ACMconferenceonWirelessnetworksecurity ,(NewYork,NY,USA),pp.77–88,ACM, 2008.[39]M.Shao,Y.Yang,S.Zhu,andG.Cao,“Towardsstatisticallystrongsourceanonymityfor sensornetworks,” INFOCOM2008.The27thConferenceonComputerCommunications. IEEE,pp.51–55,April2008. 108[40]C.Ozturk,Y.Zhang,andW.Trappe,“Source-locationprivacyinenergy-constrainedsensor networkrouting,”in SASN’04:Proceedingsofthe2ndACMworkshoponSecurityofadhoc andsensornetworks ,(NewYork,NY,USA),pp.88–93,ACM,2004. [41]Y.Xi,L.Schwiebert,andW.Shi,“Preservingsourcelocationprivacyinmonitoring-based wirelesssensornetworks.,”in IPDPS,IEEE,2006. [42]O.Berthold,H.Federrath,andS.Köpsell,“WebMIXes:Asystemforanonymousandun- observableInternetaccess,” LectureNotesinComputerScience ,pp.115–129,2001. [43]B.Möller,“Provablysecurepublic-keyencryptionforlength-preservingchaumianmixes,” inProceedingsofCT-RSA2003 ,LNCS2612,pp.244–262,April2003. [44]C.GülcüandG.Tsudik,“Mixingemailwithbabel,”in ProceedingsoftheSymposiumon NetworkandDistributedSystemSecurity ,(SanDiego,CA),1996. [45]U.Möller,L.Cottrell,P.Palfrader,andL.Sassaman,“Mixmasterprotocol,”July2003.Ver- sion2. [46]J.KongandX.Hong,“Anodr:Anonymousondemandroutingwithuntraceableroutesfor mobilead-hocnetworks,”2003. [47]L.Huang,K.Matsuura,H.Yamane,andK.Sezaki,“Enhancingwirelesslocationprivacy usingsilentperiod,”in IEEEWirelessCommunicationsandNetworkingConference(WCNC 2005),(NewOrleans,NL,U.S.A),2005. [48]B.HohandM.Gruteser,“Protectinglocationprivacythroughpathconfusion,”in SE-CURECOMM’05:ProceedingsoftheFirstInternationalConferenceonSecurityandPri- vacyforEmergingAreasinCommunicationsNetworks ,(Washington,DC,USA),pp.194– 205,IEEEComputerSociety,2005. [49]B.Zhu,Z.Wan,M.S.Kankanhalli,F.Bao,andR.H.Deng,“Anonymoussecurerout- inginmobilead-hocnetworks,”in LCN’04:Proceedingsofthe29thAnnualIEEEInter- nationalConferenceonLocalComputerNetworks ,(Washington,DC,USA),pp.102–108, IEEEComputerSociety,2004. [50]W.Y.Zhang,W.Liu,“Anonymouscommunicationsinmobileadhocnetworks,”in IEEEIn- focom,2005. [51]R.A.Shaikh,H.Jameel,B.J.d’Auriol,S.Lee,Y.-J.Song,andH.Lee,“Networklevel privacyforwirelesssensornetworks,”in IAS’08:Proceedingsofthe2008TheFourthIn- ternationalConferenceonInformationAssuranceandSecurity ,(Washington,DC,USA), pp.261–266,IEEEComputerSociety,2008. [52]S.MisraandG.Xue,“Efficientanonymityschemesforclusteredwirelesssensornetworks,” Int.J.Sen.Netw. ,vol.1,no.1/2,pp.50–63,2006. 109[53]Y.Ouyang,Z.Le,D.Liu,J.Ford,andF.Makedon,“Sourcelocationprivacyagainstlaptop- classattacksinsensornetworks,”in SecureComm’08:Proceedingsofthe4thinternational conferenceonSecurityandprivacyincommunicationnetowrks ,(NewYork,NY,USA), pp.1–10,ACM,2008. [54]J.YaoandG.Wen,“Preservingsource-locationprivacyinenergy-constrainedwirelesssensor networks,”pp.412–416,june2008. [55]X.Li,X.Wang,N.Zheng,Z.Wan,andM.Gu,“Enhancedlocationprivacyprotectionof basestationinwirelesssensornetworks,”pp.457–464,dec.2009. [56]Y.Jian,S.Chen,Z.Zhang,andL.Zhang,“Protectingreceiver-locationprivacyinwireless sensornetworks,”pp.1955–1963,may2007. [57]L.Kang,“Protectinglocationprivacyinlarge-scalewirelesssensornetworks,”pp.1–6,june 2009.[58]D.K.MehtaandM.Wright,“Locationprivacyinsensornetworksagainstaglobaleavesdrop- per,”2007. [59]M.Shao,W.Hu,S.Zhu,G.Cao,S.Krishnamurth,andT.LaPorta,“Cross-layerenhanced sourcelocationprivacyinsensornetworks,”pp.1–9,june2009. [60]Y.Jian,S.Chen,Z.Zhang,andL.Zhang,“Anovelschemeforprotectingreceiver’sloca- tionprivacyinwirelesssensornetworks,” WirelessCommunications,IEEETransactionson ,vol.7,pp.3769–3779,October2008. [61]M.Ye,C.Li,G.Chen,andJ.Wu,“Eecs:anenergyefficientclusteringschemeinwireless sensornetworks,” Performance,Computing,andCommunicationsConference,2005.IPCCC 2005.24thIEEEInternational ,pp.535–540,April2005. [62]W.B.Heinzelman, Application-specificprotocolarchitecturesforwirelessnetworks .PhD thesis,2000.Supervisor-AnanthaP.ChandrakasanandSupervisor-HariBalakrishnan. [63]J.Neander,E.Hansen,M.Nolin,andM.Bjorkman,“Asymmetricmultihopcommunication inlargesensornetworks,” WirelessPervasiveComputing,20061stInternationalSymposium on,pp.7pp.–,Jan.2006. [64]O.YounisandS.Fahmy,“Heed:Ahybrid,energy-efficient,distribtedclusteringapproach foradhocsensornetworks,” IEEETransactiononMobileComputing,vol.3,vol.4 ,2004. [65]Y.Zhang,W.Liu,Y.Fang,andD.Wu,“Securelocalizationandauthenticationinultra- widebandsensornetworks,” SelectedAreasinCommunications,IEEEJournalon ,vol.24, pp.829–835,April2006. [66]X.Cheng,A.Thaeler,G.Xue,andD.Chen,“Tps:atime-basedpositioningschemefor outdoorwirelesssensornetworks,” INFOCOM2004.Twenty-thirdAnnualJointConference oftheIEEEComputerandCommunicationsSocieties ,vol.4,pp.2685–2696vol.4,March 2004.110[67]P.Traynor,R.Kumar,H.Choi,G.Cao,S.Zhu,andT.LaPorta,“Efficienthybridsecurity mechanismsforheterogeneoussensornetworks,” MobileComputing,IEEETransactionson ,vol.6,pp.663–677,June2007. [68]S.Zhu,S.Setia,andS.Jajodia,“Leap:efficientsecuritymechanismsforlarge-scaledis- tributedsensornetworks,”in CCS’03:Proceedingsofthe10thACMconferenceonCom- puterandcommunicationssecurity ,(NewYork,NY,USA),pp.62–72,ACM,2003. [69]J.Hill,R.Szewczyk,S.H.A.Woo,D.Culler,andK.Pister,“Systemarchitecturedirections fornetworkedsensors,”in ProceedingsofACMASPLOSIX ,November2000. [70]Wikipedia,“Normaldistribution.” .[71]S.M.Stigler, StatisticsontheTable .HarvardUniversityPress.chapter22. [72]L.Lightfoot,Y.Li,andJ.Ren,“Star:Designandquantitativemeasurementofsource- locationprivacyforwirelesssensornetworks,” Wiley:SecurityandCommunicatiionNet- works2012 ,2012. [73]Y.LiandJ.Ren,“Preservingsource-locationprivacyinwirelesssensornetworks,”in SECON’09:Proceedingsofthe6thAnnualIEEEcommunicationssocietyconferenceonSen- sor,MeshandAdHocCommunicationsandNetworks ,(Piscataway,NJ,USA),pp.493–501, IEEEPress,2009. [74]L.Lightfoot,Y.Li,andJ.Ren,“Preservingsource-locationprivacyinwirelesssensornet- worksusingstarrouting,” IEEEGLOBECOM2010 ,Dec.2010. [75]Y.Li,L.Lightfoot,andJ.Ren,“Routing-basedsource-locationprivacyprotectioninwireless sensornetworks,” IEEEEIT2009 ,June2009. [76]Y.Jian,S.Chen,Z.Zhang,andL.Zhang,“Protectingrecieiver-locationprivacyinwireless sensornetworks,” INFOCOM2007.Twenty-sixAnnualJointConferenceoftheIEEECom- puterandCommunicationsSocieties ,pp.1955–1963,May2007. [77]Y.Li,L.Lightfoot,andJ.Ren,“Routing-basedsource-locationprivacyprotectioninwire- lesssensornetworks,”in Electro/InformationTechnology,2009.eit’09.IEEEInternational Conferenceon ,pp.29–34,june2009. [78]L.LightfootandJ.Ren,“Providingdestination-locationprivacyinwirelesssensorusingbub- blerouting,” InternationalConferenceonCommunicationsSignalProcessingandSystems 2012,2012. [79]D.Tang,T.Li,J.Ren,andJ.Wu,“Cost-awarerouting(car)protocoldesignforwireless sensornetworks,”2013. [80]L.LightfootandJ.Ren,“R-stardestination-locationprivacyschemesinwirelesssensornet- works,” IEEEInternationalCommunicationConference2015(ICC’15) ,2015. 111[81]A.Mammu,A.Sharma,U.Hernandez-Jayo,andN.Sainz,“Anovelcluster-basedenergy efficientroutinginwirelesssensornetworks,” IEEEInternationalConferenceonAdvance InformationNetworkingandApplications’13 ,2013. [82]W.R.Heinzelman,A.Chandrakasan,andH.Balakrishnan,“Anapplicaton-specificprotocol architectureforwirelessmicrosensornetworks,” inproceedingsofHICSS’00 ,2000. [83]W.Heinzelman,A.Chandrakasan,andH.Balakrishnan,“Energy-efficientcommunication protocolforwirelessmicrosensornetworks,” IEEETransactionsonWirelessCommunica- tions’02,Vol.1,No.4 ,2002. 112