Energy-efficient-routing-in-wireless-sensor-networks--

ENERGYEFFICIENTROUTINGINWIRELESSSENSORNETWORKS无线传感器网络中的能量有效路由,1.INTRODUCTION2.PROBLEMSTATEMENT3.BASICROUTING4.DATACOMBINING5.NETWORKTRAFFICSPREADING6.CONCLUSIONS,PPT构成,INTRODUCTION,ons.,RecentlyICandMEMShavematuredtothepointwheretheyenabletheintegrationofcommunications,sensorsandsignalprocessingalltogetherinonelow-costpackage.Itisnowfeasibletofabricateultra-smallsensornodesthatcanbescatteredonthebattlefieldtogatherstrategicinformation.Theeventsdetectedbythesenodesneedtocommunicatedtogatewaysoruserswhotapintothenetwork.Thiscommunicationoccursviamulti-hoproutesthroughothersensornodes.Sincethenodesneedtobeunobtrusive,theyhaveasmallform-factorandthereforecancarryonlyasmallbattery.Asaresult,theyhavealimitedenergysupplyandlow-poweroperationisamust.Multi-hoproutingprotocolsforthesenetworksnecessarilyhavetobedesignedwithafocusonenergyefficiency.Inthispaper,weproposetwooptionsforlocalizedalgorithmstoincreasethesensornetworklifetime:(1)minimizetheenergyconsumptionoftransmissionsand(2)exploitthemulti-hopaspectofnetworkcommunications.,1、Thesensornetworksprotocolstack,1.EnergyOptimalRoutingTraditionalad-hocroutingalgorithmsfocusonavoidingcongestionormaintainingconnectivitywhenfacedwithmobility.Theydonotconsiderthelimitedenergysupplyofthenetworkdevices.Theexampleoffigure1illustrateshowthelimitedsupplyalterstheroutingissue.NodesAandEfirstsend50packetstoB.Afterwards,Fsends100packetstoB.Fromaloadbalancingperspective,thepreferredpathsareADB,ECBandFDBrespectively.However,whenthenodesareenergyconstrainedsuchthattheycanonlysend100packets,thesepathsarenolongeroptimal.Indeed,Dwouldhaveusedup50%ofitsenergybeforeitcanforwardpacketsfromFtoB.Inthiscase,allpacketscouldhavebeendeliveredbychoosingpathsACB,ECBandFDB.If,insteadofF,nodeCwouldhavebecomeactive,AshouldhaveusedtheoriginalpathADB.Thissimplecasestudyhighlightsthefollowingcrucialobservation:optimaltrafficschedulinginenergyconstrainednetworksrequiresfutureknowledge.Inourexample,amaximumnumberofpacketscanreachBonlyifrightfromthestartweknowexactlywhen(andwhich)nodeswillgeneratetrafficinthefuture.,Ideally,wewouldlikethesensornetworktoperformitsfunctionalityaslongaspossible.Optimalroutinginenergyconstrainednetworksisnotpracticallyfeasible(becauseitrequiresfutureknowledge).However,wecansoftenourrequirementstowardsastatisticallyoptimalscheme,whichmaximizesthenetworkfunctionalityconsideredoverallpossiblefutureactivity.Aschemeisenergyefficient(incontrasttoenergyoptimal)whenitisstatisticallyoptimalandcausal(i.e.takesonlypastandpresentintoaccount).Inmostpracticalsurveillanceormonitoringapplications,wedonotwantanycoveragegapstodevelop.Wethereforedefinethelifetimewewanttomaximizeastheworst-casetimeuntilanodebreaksdown,insteadoftheaveragetimeoverallscenarios.However,takingintoaccountallpossiblefuturescenariosistoocomputationallyintensive,evenforsimulations.Itisthereforecertainlyunworkableasaguidelinetobasepracticalschemeson.Consideringonlyonefuturescenarioleadstoskewedresults,asshownintheexampleoffigure1.,2.EnergyEfficientRouting,Toderiveapracticalguideline,westartfromthefollowingobservation:theminimumhoppathstoauserfordifferentstreamstendtohavealargenumberofhopsincommon7.Nodesonthosepathsdiesoonerandthereforelimitthelifetimeofthenetwork.Figure2presentsatypicalenergyconsumptionhistogramatacertainpointintime.Somenodeshavehardlybeenused,whileothershavealmostcompletelydrainedtheirenergy.,3.TrafficSpreadingRationale,Asnodesthatarerunninglowonenergyaremoresusceptibletodiesooner,theyhavebecomemorecritical.Ifweassumethatallthenodesareequallyimportantnonodeshouldbemorecriticalthananyotherone.Ateachmomenteverynodeshouldthereforehaveusedaboutthesameamountofenergy,whichshouldalsobeminimized.Thehistogramoffigure3isthusmoredesirablethantheoneoffigure2,althoughthetotalenergyconsumptionisthesame.,Strivingforacompactenergyhistogramtranslatesintotheguidelinethattrafficshouldbespreadoverthenetworkasuniformlyaspossible.Sincevisualizingthehistogramovertimeishard,weproposetousetherootmeansquareERMSasanindicatorinstead(thelowerthisvalue,thebetter).Itprovidesinformationonboththetotalenergyconsumptionandonthespread.,Asanunderlyingroutingscheme,webaseourselvesontheparadigmofdirecteddiffusion.Whenausertapsintothesensornetwork,heannouncesthetypeofinformationheisinterestedin.WhilefloodingthisinterestpossiblyusingtechniqueslikeSPIN,gradientsareestablishedineachnode.Thesegradientsindicatethegoodnessofthedifferentpossiblenexthopsandareusedtoforwardsensordatatotheuser.Wehaveoptedforasimpleinstantiationofthisparadigm,whichwecallGradient-BasedRouting(GBR).Whilebeingflooded,theinterestmessagerecordsthenumberofhopstaken.Thisallowsanodetodiscovertheminimumnumberofhopstotheuser,calledthenodesheight.Thedifferencebetweenanodesheightandthatofitsneighborisconsideredthegradientonthatlink.Apacketisforwardedonthelinkwiththelargestgradient.AlthoughourtechniquestoincreasethenetworklifetimearebuiltuponGBR,themainprinciplesaregeneralenoughtoalsobeapplicabletootherad-hocroutingprotocols.,BASICROUTING,1.DataCombiningEntities(DCE)Individualsensornodesprocesstheirsensordatabeforerelayingittotheuser1.Itisadvantageoustocombineobservationsfromdifferentnodestoincreasetheresourceefficiency.Thisprocessreducesnotonlytheheaderoverhead,butalsothedataitselfcanbecompactedasitcontainspartlythesameinformation.Althoughthiscombiningcanbeimplementedbyexplicitlyselectingaclusterhead3,wepresentaschemethatismorerobusttorandomnodefailures.Firstnotethatsensornodesthataretriggeredbythesameevent,aretypicallylocatedinthesamevicinity.Theresultingcloudofactivatednodesisalsoinclosecommunicationproximity.Theroutesfromthesenodestotheusermergeearlyon7.NodesthathavemultiplestreamsflowingthroughthemcancreateaDataCombiningEntity(DCE),whichtakescareofthedatacompaction.SimulationshaveshownthattheDCEsarelocatedinsideorveryclosetothiscloudofactivatednodes.Thisschemeishighlyrobust.WhenanodewithaDCEdies,thepacketsautomaticallytakeanalternativerouteandpassthroughanothernodethatcancreateanewDCE.,DATACOMBINING,Figure4depictstheeffectsofourDCE-baseddatacompactiononthetotalenergyconsumption.Thenodesinthissimulationaredistributedrandomlyoverarectangularareawithaconstantwidthof32mandalinearlyincreasinglengthB.TheradiotransmissionrangeRis20mandtheaveragenodedensityiskeptconstantat10-2/m2.Thenodesatthetopofthisareasenseatargetandnotifyauserthatislocatedatthebottomend(thetransmissionofonepackettakes5.76J).Forournumericalresults,weassumethatapacketthatiscombinedwithanotheronecanbecompressedto60%ofitsoriginalsize.Weconsider3distinctcases:withoutDCE,withatmostoneDCE(acompressionbitinthepacketheadersignalsifthepackethasbeencompressedalready)oneachroutetotheuserandwithnorestrictionsonthenumberofDCEs.Thereductioninenergyconsumptionisasexpected(uptoafactor2to3),linearlyproportionaltothenumberofbitssent.,2.Simulations,Theflipsideistheaveragedelayperpacket,whichispresentedinfigure5.SinceDCEshavetobufferdataforawhile,thepacketdelaywillincreasewiththenumberofcombiningstagesapplied.Whetherornotthisisacceptabledependsontheapplication.,NETWORKTRAFFICSPREADING,1.SpreadingTechniques,StochasticScheme:Usingarationalesimilartotheoneof,eachnodecanselectthenexthopinastochasticfashion.Morespecifically,whentherearetwoormorenexthopswiththesamelowestgradient,arandomoneischosen.Thisdoesnotincreasethelengthofthepathfollowed,butnonethelesscontributestospreadingthenetworktraffic.Energy-basedScheme:Whenanodedetectsthatitsenergyreservehasdroppedbelowacertainthreshold(50%inoursimulations),itdiscouragesothersfromsendingdatatoitbyincreasingitsheight.Thismaychangeaneighborsheight(sinceanodesheightisonemorethanthatofitslowestneighbor).Itinturninformsothernodesandtheseupdatesarepropagatedasfarasisneededtokeepallthegradientsconsistent.Stream-basedScheme:Theideaistodivertnewstreamsawayfromnodesthatarecurrentlypartofthepathofotherstreams.Anodethatreceivespacketstellsallitsneighborsexcepttotheonefromwherethestreamoriginates,thatitsheighthasincreased.Again,othernodesmustmakesurethegradientsremainconsistent.Asaresultofthisscheme,theoriginalstreamisunaffected,sincethosenodeshavenotupdatedtheheightofthenexthop.Newstreamsofpackets,however,willtakeotherpathsastheheightofthenodesonthefirstpathhasapparentlyincreased.,2.Simulations,Scenario1:NodesAandB(seefigure6)detectadifferenttargetandsendpacketstotheuseratregularintervals.Aftergenerating100packetseach(thistakes11.8seconds),thesetargetsdisappearandbothnodesbecomeinactiveagain.Atthistime,nonodehasbeendrainedyetcompletelyandthenetworkconnectivityisstillfullyintact.Wehaveassumedanodehasonly0.76mJofenergyatitsdisposal(whichisenoughtosendabout140packets).Theresultscanreadilybescaledtowardsmorerealisticscenarios.Figure7showstheevolutionofERMSasafunctionoftime,for5differentschemes.TheunenhancedGBRiscalledstandard.BesidesthethreeschemesdiscussedinV.1,wehavealsostudiedacombinationofthestochasticandenergy-basedone.,Itisclearthatthestream-basedschemeindeedspreadsthetrafficmoreuniformlyoverthenetwork.Assoonastheenergyofsomenodesdropsbelow50%,theenergy-basedschemekicksin.ThestochasticroutingprovidesanimprovementbothontopofthenormalGBRandontopoftheenergy-basedscheme.,ToverifythattheERMScapturestherelevantinformation,figure8showstheenergyhistogramforthestandardandthestream-basedschemeafter7seconds.Itisclearthatspreadingbalancestheenergyconsumptionbetter.Finally,wewouldliketoshowthattheimprovedenergyhistogramisable