Energy-Efficient Routing Protocols in Wireless Sensor Networks - A Survey

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

1

Energy-EfficientRoutingProtocolsinWireless

SensorNetworks:ASurvey

NikolaosA.Pantazis,StefanosA.NikolidakisandDimitriosD.Vergados,SeniorMember,IEEE

Abstract—ThedistributednatureanddynamictopologyofWirelessSensorNetworks(WSNs)introducesveryspecialre-quirementsinroutingprotocolsthatshouldbemet.Themostimportantfeatureofaroutingprotocol,inordertobeefficientforWSNs,istheenergyconsumptionandtheextensionofthenetwork’slifetime.Duringtherecentyears,manyenergyefficientroutingprotocolshavebeenproposedforWSNs.Inthispaper,energyefficientroutingprotocolsareclassifiedintofourmainschemes:NetworkStructure,CommunicationModel,TopologyBasedandReliableRouting.Theroutingprotocolsbelongingtothefirstcategorycanbefurtherclassifiedasflatorhierarchical.TheroutingprotocolsbelongingtothesecondcategorycanbefurtherclassifiedasQuery-basedorCoherentandnon-coherent-basedorNegotiation-based.TheroutingprotocolsbelongingtothethirdcategorycanbefurtherclassifiedasLocation-basedorMobileAgent-based.TheroutingprotocolsbelongingtothefourthcategorycanbefurtherclassifiedasQoS-basedorMultipath-based.Then,ananalyticalsurveyonenergyefficientroutingprotocolsforWSNsisprovided.Inthispaper,theclassificationinitiallyproposedbyAl-Karaki,isexpanded,inordertoenhancealltheproposedpaperssince2004andtobetterdescribewhichissues/operationsineachprotocolillustrate/enhancetheenergy-efficiencyissues.

IndexTerms—RoutingProtocols,EnergyEfficiency,WirelessSensorNetworks.

I.INTRODUCTION

A

WSNisacollectionofwirelessnodeswithlimitedenergycapabilitiesthatmaybemobileorstationaryandarelocatedrandomlyonadynamicallychangingenvironment.Theroutingstrategiesselectionisanimportantissuefortheefficientdeliveryofthepacketstotheirdestination.Moreover,insuchnetworks,theappliedroutingstrategyshouldensuretheminimumoftheenergyconsumptionandhencemaximiza-tionofthelifetimeofthenetwork[1].

OneofthefirstWSNswasdesignedanddevelopedinthemiddleofthe70sbythemilitaryanddefenseindustries.WSNswerealsousedduringtheVietnamWarinordertosup-portthedetectionofenemiesinremotejungleareas.However,theirimplementationhadseveraldrawbacksincludingthatthelargesizeofthesensors,theenergytheyconsumeandthelimitednetworkcapability.

Manuscriptreceived21May2011;revised8December2011and16March2012.

N.A.PantazisiswiththeTechnologicalEducationalInstitute(TEI)ofAthens,DepartmentofElectronicsEngineering,AgiouSpiridonos,GR-12210Egaleo,Athens,Greece(e-mail:npantazis@teiath.gr).

S.A.NikolidakisiswiththeUniversityofPiraeus,DepartmentofInfor-matics,80KaraoliandDimitriouStr.,GR-18534Piraeus,Greece(e-mail:snikol@unipi.gr).

D.D.VergadosiswiththeUniversityofPiraeus,DepartmentofInfor-matics,80KaraoliandDimitriouStr.,GR-18534Piraeus,Greece(e-mail:vergados@unipi.gr).

DigitalObjectIdentifier10.1109/SURV.2012.062612.00084

Sincethen,alotofworkontheWSNsfieldhasbeencarriedoutresultinginthedevelopmentoftheWSNsonawidevarietyofapplicationsandsystemswithvastlyvaryingrequirementsandcharacteristics.Atthesametime,variousenergy-efficientroutingprotocolshavebeendesignedandde-velopedforWSNsinordertosupportefficientdatadeliverytotheirdestination.Thus,eachenergy-efficientroutingprotocolmayhavespecificcharacteristicsdependingontheapplicationandnetworkarchitecture.

TheWSNsmaybeusedinavarietyofeverydaylifeactivitiesorservices.ForexampleacommonapplicationofWSNsisformonitoring.Intheareaofmonitoring,theWSNisdeployedoveraregioninordertomonitorsomephenomenon.Apracticaluseofsuchanetworkcouldbeamilitaryuseofsensorstodetectenemyintrusion.Incasethatthesensorsdetectanevent(changeonheatoronthebloodpressure)thentheeventisimmediatelyreportedtothebasestation,whichdecidestheappropriateaction(sendamessageontheinternetortoasatellite).Asimilarareaofusemaybethemonitoringoftheairpollution,wheretheWSNsaredeployedinseveralcitiestomonitortheconcentrationofdangerousgasesforcitizens.Moreover,aWSNmaybeusedforforestfiresdetectiontocontrolwhenafirehasstarted.Thenodeswillbeequippedwithsensorstocontroltemperature,humidityandgaseswhichareproducedbyfireinthetreesorvegetation.Inadditiontotheabove,animportantareaofuseisthehealthcaresector.thisareatheWSNsmayoffersignificantcostsavingsandenablenewfunctionalitiesthatwillassisttheelderlypeoplelivingalonginthehouseorpeoplewithchronicdiseasesonthedailyactivities.Inwiredsystems,theinstallationofenoughsensorsisoftenlimitedbythecostofwiring.Previouslyinaccessiblelocations,rotatingmachinery,hazardousorrestrictedareas,andmobileassetscannowbereachedwithwirelesssensors.

Moreover,theuseofWSNsonagriculturemaybenefittheindustryfreesthefarmerfromthemaintenanceofwiringinadifficultenvironment.Thegravityfeedwatersystemscanbemonitoredusingpressuretransmitterstomonitorwatertanklevels,pumpscanbecontrolledusingwirelessI/Odevicesandwaterusecanbemeasuredandwirelesslytransmittedbacktoacentralcontrolcenterforbilling.ThewaterindustrymaybebenefitedforpowerordatatransmissioncanbemonitoredusingindustrialwirelessI/Odevicesandsensorspoweredusingsolarpanelsorbatterypacks.

Themaincontributionofthispaperistoprovideanex-haustivesurveyontheenergy-efficientroutingprotocolsforWSNsaswellastheirclassificationintofourmaincategories:NetworkStructure,CommunicationModel,TopologyBased

c2012IEEE1553-877X/12/$31.00󰀁

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

2

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

andReliableRoutingSchemes.Wefocusonthetechniquestheseprotocolsuseinordertoroutemessages,takingintocon-siderationtheenergytheyconsumeandhowtheyachievetominimizethisconsumptionandextendthelifetimeofthenet-work.Moreover,wediscussthestrengthsandweaknessesofeachprotocolprovidingacomparisonamongthemincludingsomemetrics(scalability,mobility,powerusage,routemetric,periodicmessagetype,robustness)inorderforresearchersandpractitionerstounderstandthevarioustechniquesandthushelpingthemtoselectthemostappropriateonebasedontheirneeds.Also,inthispapertheclassificationinitiallyproposedbyAl-Karaki,isexpanded,inordertoenhancealltheproposedpaperssince2004andtobetterdescribewhichissues/operationsineachprotocolillustrate/enhancetheenergy-efficiencyissues.

Thispaperisorganizedasfollows:Insection2,therelatedworkinthesurveyofroutingprotocolsforWSNsispresented.Insection3,therealdeploymentandenergyconsumptioninWSNsispresented.Insection4,theenergy-efficientrouteselectionpoliciesaredescribed.Insection5,theroutingtechniquesandtheirclassificationintofourmaincategories,Structure,CommunicationModel,TopologyBasedandReliableRouting,areanalyzedanddiscussed.Theroutingprotocolsbelongingtothefirstcategorycanbefurtherclassi-fiedasFlatorHierarchical.TheroutingprotocolsbelongingtothesecondcategorycanbefurtherclassifiedasQuery-BasedorCoherentandNon-CoherentBasedorNegotiation-Based.TheroutingprotocolsbelongingtothethirdcategorycanfurtherclassifiedasLocation-basedorMobileAgent-based.TheroutingprotocolsbelongingtothefourthcategorycanbefurtherclassifiedasQoS-basedorMultipath-based.InSection6,wedescribeandcomparetheprotocolsthatbelongtotheNetworkStructurescheme.Insection7,theprotocolsthatbelongtotheCommunicationModelschemearedescribedandcompared.InSection8,wedescribeandcomparetheprotocolsthatbelongtotheTopologyBasedscheme.Insection9,theprotocolsthatbelongtotheReliableRoutingschemearedescribedandcompared.Insection10,therouteselectionfactorsandthefutureresearchdirectionsarediscussed.Finally,insection11,weconcludethepaper.

II.RELATEDWORK

Thereisalargenumberofcurrentworks,aswellaseffortsthatareonthego,forthedevelopmentofroutingprotocolsinWSNs.Theseprotocolsaredevelopedbasedontheapplicationneedsandthearchitectureofthenetwork.However,therearefactorsthatshouldbetakenintoconsiderationwhendevelopingroutingprotocolsforWSNs.Themostimportantfactoristheenergyefficiencyofthesensorsthatdirectlyaffectstheextensionofthelifetimeofthenetwork.ThereareseveralsurveysintheliteratureonroutingprotocolsinWSNsandanattemptismadetopresentbelowanddiscustheexistingdifferencesbetweenthemandourwork.

In[2],theauthorsmakeacomprehensivesurveyonde-signissuesandtechniquesforWSNs(2002).Theydescribethephysicalconstraintsofsensornodesandtheproposedprotocolsconcernalllayersofthenetworkstack.Moreover,thepossibleapplicationsofsensornetworksarediscussed.However,thepaperdoesnotmakeaclassificationforsuchroutingprotocolsandthelistofdiscussedprotocolsisnotmeanttobecomplete,giventhescopeofthesurvey.OursurveyismorefocusedontheenergyefficiencyonWSNsprovidingatthesametimeaclassificationoftheexistingroutingprotocols.Wealsodiscussanumberofdevelopedenergy-efficientroutingprotocolsandprovidedirectionstothereadersonselectingthemostappropriateprotocolfortheirnetwork.

In[3],asurveyonroutingprotocolsinWSNsispresented(2004).Itclassifiestheroutingtechniques,basedonthenetworkstructure,intothreecategories:flat,hierarchical,andlocation-basedroutingprotocols.Furthermore,theseprotocolsareclassifiedintomultipath-based,query-based,negotiation-based,andQoS-basedroutingtechniquesdependingontheprotocoloperation.Itpresents27routingprotocolsintotal.Moreover,thissurveypresentsagoodnumberofenergy-efficientroutingprotocolsthathavebeendevelopedforWSNsandwaspublishedin2004.ItalsopresentstheRoutingChallengesandDesignIssuesthathavetobenoticedwhenusingWSNs.Thus,limitedenergysupply,limitedcomputingpowerandlimitedbandwidthofthewirelesslinksconnectingsensornodesaredescribed.Also,theauthorstrytohigh-lightthedesigntradeoffsbetweenenergyandcommunica-tionoverheadsavingsinsomeoftheroutingparadigm,aswellastheadvantagesanddisadvantagesofeachroutingtechnique.Onthecontrary,inourworkwefocusontheenergyefficiencyissuesinWSNs.Weprovidedetailsandcomprehensivecomparisonsonenergyefficientprotocolsthatmayhelpresearchersontheirwork.Also,inthispaperweexpandtheclassificationinitiallyproposedbyAl-Karakiinordertoenhancealltheproposedpaperssince2004andtobetterdescribewhichissues/operationsineachprotocolillustrate/enhancetheenergy-efficiencyissues.

Thesurveyin[4]discussesfewroutingprotocolsforsensornetworks(24intotal)andclassifiesthemintodata-centric,hierarchicalandlocation-based(2005).AlthoughitpresentsroutingprotocolsforWSNsitdoesnotconcentrateontheenergyefficientpolicies.Onthecontrary,wefocusmainlyontheenergy-efficientroutingprotocolsdiscussingthestrengthsandweaknessesofeachprotocolinsuchawayastoprovidedirectionstothereadersonhowtochoosethemostappropriateenergy-efficientroutingprotocolfortheirnetwork.

In[5],authorsprovideasystematicalinvestigationofcur-rentstate-of-the-artalgorithms(2007).Theyareclassifiedintwoclassesthattakeintoconsiderationtheenergy-awarebroadcast/multicastprobleminrecentresearch.TheauthorsclassifythealgorithmsintheMEB/MEM(minimumenergybroadcast/multicast)problemandtheMLB/MLM(maximumlifetimebroadcast/multicast)probleminwirelessadhocnet-works.Typically,thetwomainenergy-awaremetricsthatareconsideredare:minimizingthetotaltransmissionpowerconsumptionofallnodesinvolvedinthemulticastsessionandmaximizingtheoperationtimeuntilthebatterydepletionofthefirstnodeinvolvedinthemulticastsession.Moreover,eachnodeinthenetworksisconsideredtobeequippedwithanomni-directionalantennawhichisresponsibleforsendingandreceivingsignals.

Thesurveyin[6],presentsatop-downapproachofseveralapplicationsandreviewsonvariousaspectsofWSNs(2008).

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

3

Itclassifiestheproblemsintothreedifferentcategories:inter-nalplatformandunderlyingoperatingsystem,communicationprotocolstack,networkservices,provisioning,anddeploy-ment.However,thepaperneitherdiscussestheenergyefficientroutingprotocolsdevelopedonWSNsnorprovidesadetailedcomparisonoftheprotocols.Ourworkisadedicatedstudyonenergy-efficientroutingprotocolsandprovidesdirectionstothereadersonselectingthemostappropriateprotocolfortheirnetwork.

In[7],theauthorspresentasurveythatisfocusedontheenergyconsumptionbasedonthehardwarecomponentsofatypicalsensornode(2009).Theydividethesensornodeintofourmaincomponents:asensingsubsystemincludingoneormoresensorsfordataacquisition,aprocessingsubsystemincludingamicro-controllerandmemoryforlocaldatapro-cessing,aradiosubsystemforwirelessdatacommunicationandapowersupplyunit.Alsothearchitectureandpowerbreakdownasthesolutiontoreducepowerconsumptioninwirelesssensornetworksisdiscussed.TheyprovidethemaindirectionstoenergyconservationinWSNs.Thepaperisfocusedonthedescriptionofthecharacteristicsandadvan-tagesofthetaxonomyoftheenergyconservationschemes.Theprotocolsareclassifiedintoduty-cycling,data-drivenandmobilitybased.Inthenextprotocols,moredetailsanddiscussionarepresentedofthisclassification.Moreover,theyprovideobservationsaboutthedifferentapproachestoenergymanagementandhighlightthattheenergyconsumptionoftheradioismuchhigherthantheenergyconsumptionduetodatasamplingordataprocessing.However,manyrealapplicationshaveshownthepowerconsumptionofthesensoriscomparableto,orevengreaterthan,thepowerneededbytheradio.Theyconcludethatthesamplingphasemayneedalongtimeespeciallycomparedtothetimeneededforcommunications,sothattheenergyconsumptionofthesensoritselfcanbeveryhighaswell.Alsotheyobserveanincreasinginteresttowardssparsesensornetworkarchitecture.Inourwork,webasicallyfocusontheenergy-efficientprotocolsandwediscussthestrengthsandweaknessesofeachprotocolthatcanprovidedirectionstothereadersaboutthemostappropriateenergy-efficientroutingprotocolfortheirnetwork.In[8],thedesignissuesofWSNsandclassificationofrout-ingprotocolsarepresented(2009).Moreover,afewroutingprotocolsarepresentedbasedontheircharacteristicsandthemechanismstheyuseinordertoextendthenetworklifetimewithoutprovidingdetailsoneachofthedescribedprotocols.Also,theauthorsdonotpresentadirectcomparisonofthediscussedprotocols.Inourworkwedonotonlyfocusontheenergy-efficientprotocolsbutwealsodiscussthestrengthsandweaknessesofeachprotocolinsuchawayastoprovidedirectionstothereadersonhowtochoosethemostappropriateenergy-efficientroutingprotocolfortheirnetwork.

Thepaperin[9]presentsthechallengesinthedesignoftheenergy-efficientMediumAccessControl(MAC)protocolsfortheWSNs(2009).Moreover,itdescribesfewMACprotocols(12intotal)fortheWSNsemphasizingtheirstrengthsandweaknesses,whereverpossible.However,thepaperneitherdiscussestheenergy-efficientroutingprotocolsdevelopedonWSNsnorprovidesadetailedcomparisonoftheprotocols.Oursurveyisconcentratedontheenergy-efficientrouting

protocolsdiscussingthestrengthsandweaknessesofeachprotocolinsuchawayastoprovidedirectionstothereadersonhowtochoosethemostappropriateenergy-efficientroutingprotocolfortheirnetwork.

In[10],fewenergy-efficientroutingtechniquesforWirelessMultimediaSensorNetworks(WMSNs)arepresented(2011).Alsotheauthorshighlighttheperformanceissuesofeachstrategy.TheyoutlinethatthedesignchallengesofroutingprotocolsforWMSNsfollowedbythelimitationsofcurrenttechniquesdesignedfornon-multimediadatatransmission.Further,aclassificationofrecentroutingprotocolsforWM-SNsispresented.ThissurveydiscussessomeissuesonenergyefficiencyinWSNs.However,itismostlybasedontheenergyefficienttechniquescombiningQoSAssuranceforWMSNs.Although,thereisagoodnumberofsurveysforsensornetworks,orroutingandMACalgorithmsforWSNs([2],[3],[4],[5],[6],[7],[8],[9]and[10]),thispaperprovidesananalyticalsurveyemphasizingontheenergy-efficientroutingprotocolsinWSNs.Oursurveyisfocusedontheenergy-efficientroutingprotocolsinWSNsthatcanprovidedirectionstothereadersonhowtochoosethemostappropriateenergy-efficientroutingprotocolfortheirnetwork.Moreover,ourworkreflectsthecurrentstateoftheartinroutingresearchbyincludingacomprehensivelistofrecentlyproposedroutingprotocols.Moreover,wediscussthestrengthsandweaknessesofeachprotocolmakingacomparisonbetweenthemincludingsomemetrics(scalability,multipath,mobility,powerusage,routemetric,periodicmessagetype,robustnessandQoSsupport).

III.REALDEPLOYMENTANDENERGYCONSUMPTIONIN

WSNSA.RealDeploymentsinWSNs

TheresearchanddevelopmentofroutingprotocolsinWSNswereinitiallydrivenbydefenseapplications.ThishasresultedinthedevelopmentofmanyWSNsystemslikeacoustictrackingoflow-flyingaircraftorRemoteBattlefieldSensorSystem(REMBASS).In[11],aWSNthatoffersbattlefieldsurveillancesservicesispresented.Alsoin[12]theapplicationofWSNstotheintrusiondetectionproblemandtherelatedproblemsofclassifyingandtrackingtargetsispresented.However,intherecentyearstheWSNsofferawelldefinedandeasywaytoofferservicestoalotofdailysectorsofpeoplepayingagreatattentiontohealthcareservices[13].In[14]asensorandactuatornetworkinsmarthomesforsupportingelderlyandhandicappedpeopleisstudied.Alsoin[15]anapplicationforsmarthomemonitoringhasalsobeendescribed.AlsothereisalotofeffortondevelopingmorecomplicatingWSNsystemsconcludingtoframeworksandmakethemavailabletoalargersetofapplications[16],[17],[18],[19].

Sensornetworksconsistofasmallorlargeamountofnodescalledsensornodes.Thesenodesarevaryinginsizeandbasedontheirsizethesensornodesworkefficientlyindifferentfields.WSNshavesuchsensornodeswhicharespeciallydesignedinsuchatypicalwaythattheyincludeamicrocontrollerwhichcontrolsthemonitoring,aradiotransceiverforgeneratingradiowaves,differenttypesof

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

4

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

Wireless Sensor ModuleProcessing ModuleCommunication ModuleSensorNetworkSensorAC/DCAC/DCMACTransceiverPower Provision Module (Battery Supply)Fig.1.

ThearchitectureofaWSNnode.

wirelesscommunicatingdevicesandalsoequippedwithanenergysourcesuchasbattery.Theentirenetworkworkssimultaneouslybyusingsensorsofdifferentdimensionsandbyusingaroutingalgorithmtheyaremainlyfocusedonprovidingdeliverydatafromthesourcetothedestinationnodes.

B.EnergyConsumptionModelsforWSNnodes

TheWSNnodesconsistofseveralmodulesasshowninfigure1:SensorModule,ProcessingModule,WirelessCommunicationModuleandPowerSupplyModule.Thesecomponentsworktogetherinordertomakethesensorop-erationalinaWSNenvironment.Thus,inordertoevaluatetheenergyconsumptionofaWSNnode,itisimportanttostudytheenergyconsumptionofitscomponents.

ThereareafewattemptstoproposeanddiscusaboutmodelsforenergyefficiencyWSNs.Mostofthemarebasedonsensornodepowerconsumptionmodel,whileatthesametimetheimpactofthesensornodedevicehardwareandexternalradioenvironmentareconsidered.However,inrealdeploymentstheseparationofthepowerconsumptionofeachhardwarecomponentandtheimpactoftheexternalradioenvironmentshouldbeconsidered.

Inparticular,theauthorsin[20]presentarealisticpowerconsumptionmodelforWSNdevicesbyincorporatingthecharacteristicsofatypicallowpowertransceiver(2006).Thisworkprovesthatfortypicalhardwareconfigurationsandradiofrequencyenvironments,wheneversinglehoproutingispossibleitshouldbepreferredasitismorepowerefficientthanmulti-hoprouting.

In[21],anenergymodelspecificallybuiltforuseforon-lineaccountingispresented.Thismodelofthecommunicationsystemappearstoberelativelysimple,onlytwostatesforthemicrocontrollerandtheradiochipareconsidered(2007).Ontheotherhand,in[22]theauthorspresentanenergymodeldividedintoasetoffinitestatemachinesthatrepresentthestatesandtransitionsofasensornode’shardware(2008).Withthismodelanditsapplicationinon-lineenergyaccounting,itispossibletogetamoredetailedandmorepreciseviewontheenergyconsumptioninasensornetworkthanbefore.Datagatheredfromtheonlineaccountingcanbeusedtotunetheenergyconsumptionofsensornodeapplicationsautomaticallyatrun-time.

Inaddition,in[23]ageneralenergyconsumptionmodelof

WSNsdevicesbasedontheactualhardwarearchitectureisproposed(2007).Inordertoachievethis,theauthorsutilizethemeasuredenergyconsumptionperformanceoftheac-tualhardwarecomponentsandimplementarealisticCSESM(CommunicationSubsystemEnergyConsumptionModel)ofWSNsdevices.Thiscanreflecttheenergyconsumptioninvariousfunctioningstatesandduringtransitionsbetweenstatesofthedevices.Inthismodeltheenergyconsumptionofthecommunicationstageisconsideredtobeinfluencedbythereceivemodule(Rx),thetransmitmodule(Tx),thevoltageregulator(VR),thecrystaloscillator(XOSC),thebiasgenerator(BG),andthefrequencysynthesizer(FS).AnothermodelrelatedtoenergyconsumptionofthesensorCPU(CentralProcessingUnit)ispresentedin[24](2010).It’saprobabilisticmodelwhichevaluatestheenergyconsumptionforCPUofwirelesssensornode.ThismodelinordertoevaluatetheCPUenergyconsumptionitcalculatesthepowerspendonstandby,powerup,idleandactivestateoftheCPU.ThetotalamountofthisCPUconsumptionalongwiththespendtimeconcludetotheenergyconsumption.

Amoreuptodateapproachregardingtheenergyconsump-tionoftheWSNnodesispresentedin[25](2011).Moredetailed,theenergyconsumptionofthewirelesssensornodesbasedonfig.1dependsonitscomponentsandissummarizedonthefollowing:

•

SensorModule.Theenergyconsumptionofsensormod-uleisduetoafewnumbersofoperations.Thisincludessignalsampling,AD(AnaloguetoDigital)signalconver-sionandsignalmodulation.Alsotheenergyconsumptionofthismoduleisrelatedtothesenseoperationofthenode(periodic,sleep/wake,etc.).Forexampleinperiodicmodetheenergyconsumptionismodeledas

Esensor=Eon−off+Eoff−on+Esensor−run(1)

InthisrelationtheEon-offistheonetimeenergycon-sumptionofclosingsensoroperation,Eoff-onistheonetimeenergyconsumptionofopeningsensoroperationandEsensor-runistheenergyconsumptionofsensingoperationthatisequaltothetheworkingvoltagemultipliedbythecurrentofsensorsandthetimeintervalofsensingoperation.

•

ProcessingModule.Themainactivitiesofthismodulearethesensorcontrolling,theprotocolcommunicationanddataprocessing.Inmostcasesthismodulesupportsthreeoperationstates(sleep,idle,run).TheProcessorenergyconsumption,denotedasEcpuisthesumofthestateenergyconsumptionEcpu-stateandthestate-transitionenergyconsumptionEcpu-changewherei=1,2,..mistheprocessoroperationstateandmisthenumberoftheprocessorstate,j=1,2,..n,istheisthetypeofstate

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

5

a) Local Communicationb) Point-to-Pointc) Convergenced) Aggregatione) DiverganceFig.2.ThetrafficpatternsinWSNs.

transitionandnisthenumberofthestate-transition.

Ecpu=

Ecpu−state+Ecpu−change=m󰀁

Pcpu−state(i)Tcpu−state(i)+

i=1n󰀁j=1

adetailedstudyofthepowerrequirementsoftheMICA

nodefordifferentoperationsispresented.C.TrafficPatternsinWSNs(2)

Indifferencetotraditionalnetworks,theWSNsexhibituniqueasymmetrictrafficpatterns.ThisismainlyfacedduetothefunctionoftheWSNwhichistocollectdata,sensornodespersistentlysendtheirdatatothebasestation,whilethebasestationonlyoccasionallysendscontrolmessagestothesensornodes.

Moreover,thedifferentapplicationscancauseawiderangeoftrafficpatterns.ThetrafficofWSNscanbeeithersinglehopormulti-hop.Themulti-hoptrafficpatternscanbefurtherdivided,dependingonthenumberofsendandreceivenodes,orwhetherthenetworksupportsin-networkprocessing,intothefollowing(figure2):

•LocalCommunication.Itisusedtobroadcastthestatusofanodetoitsneighbors.Alsoitisusedtotransmitthedatabetweenthetwonodesdirectly.

•Point-to-Point.Routing.Itisusedtosendadatapacketfromanarbitrarynodetoanotherarbitrarynode.ItiscommonlyusedinawirelessLANenvironment.

•Convergence.Thedatapacketsofmultiplenodesareroutedtoasinglebasenode.ItiscommonlyusedfordatacollectioninWSNs.

•Aggregation.Thedatapacketscanbeprocessedintherelayingnodesandtheaggregatevalueisroutedtothebasenoderatherthantherawdata.

•Divergence.Itisusedtosendacommandfromthebasenodetoothersensornodes.

ItisinterestingtoinvestigatethetrafficpatternsinWSNsalongwiththemobilityofthenodes,asnodemobilityhasbeenutilizedinafewWSNapplicationssuchashealthcaremonitoring.Oneofthefirstattemptsondoingthisisprovidedin[28].However,thereisstillanongoingresearchareathatwillgathergreatattentiononthefollowingyears.IV.ENERGYEFFICIENTROUTESELECTIONPOLICIESEnergyefficiencyisacriticalissueinWSNs.Theexistingenergy-efficientroutingprotocolsoftenuseresidualenergy,transmissionpower,orlinkdistanceasmetricstoselect

Ncpu−change(j)ecpu−change(j)

•

Onthisrelation,Pcpu-state(i)isthepowerofstateithatcanbefoundfromthereferencemanual,Tcpu-state(i)isthetimeintervalinstateiwhichisastatisticalvariable.Ncpu-change(j)isthefrequencyofstatetransitionjandecpu-change(j)istheenergyconsumptionofone-timestatetransitionj.

WirelessCommunicationModule.Thetotalpowercon-sumptionfortransmittingPTandforreceivingPR,isdenotedas

PT(d)=PTB+PTRF+PA(d)=PT0+PA(d)

PR=PRB+PRRF+PL=PR0

(3)(4)

•

WherePA(d)isthepowerconsumptionofthepoweramplifierwhichisafunctionofthetransmissionranged.ThePA(d),willdependonmanyfactorsincludingthespecifichardwareimplementation,DCbiascondition,loadcharacteristics,operatingfrequencyandPAoutputpower,PTx[26].ThePTB,PTRF,PRB,PRRFandPLdonotdependonthetransmissionrange.

PowerSupplyModule.Thepowermoduleofthenodesisrelatedtothemanufacturerandthemodelofeachnode.Forexample,awirelesssensornodeLOTUSandnodeIRISdevelopedbyMEMSIC,arebothsuppliedbytwoAAbatteries,whilethecurrentdrawonreceivemodeis16mAandontransmitforTxvalue-17dBm,-3dBm,+3dBmconsumes10mA,13mAand17mArespectively.Ontheotherhand,theknownnodeMICA2,whichisalsosuppliedbytwoAAbatteries,ontransmitwithmaximumpoweritconsumes27mAandhasanaveragereceiveof10mA.Alsoonthesleepmodeitconsumeslessthan0.001mA.ArealdeploymentexamplewhereMICAsensorsareusedispresentedin[27].Inthisdeployment

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

6

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

anoptimalpath.Inthissection,thefocusisonenergy-efficiencyinWSNsandtherouteselectionpolicieswithnovelmetricsinordertoincreasepathsurvivabilityofWSNs.Thenovelmetricsresultinstablenetworkconnectivityandlessadditionalroutediscoveryoperations.

ThedevicesusedinaWSNareresourceconstrained,theyhavealowprocessingspeed,alowstoragecapacityandalimitedcommunicationbandwidth.Moreover,thenetworkhastooperateforlongperiodsoftime,butthenodesarebattery-powered,sotheavailableenergyresourceslimittheiroveralloperation.Tominimizeenergyconsumption,mostofthedevicecomponents,includingtheradio,shouldbeswitchedoffmostofthetime.Anotherimportantcharacteristicisthatsensornodeshavesignificantprocessingcapabilitiesintheensemble,butnotindividually.Nodeshavetoorganizethem-selves,administeringandmanagingthenetworkalltogether,andthisismuchharderthancontrollingindividualdevices.Furthermore,changesinthephysicalenvironment,whereanetworkisdeployed,makealsonodesexperiencewidevariationsinconnectivityandthusinfluencingthenetworkingprotocols.

ThemaindesigngoalofWSNsisnotonlytotransmitdatafromasourcetoadestination,butalsotoincreasethelifetimeofthenetwork.Thiscanbeachievedbyemployingenergy-efficientroutingprotocols.Dependingontheapplicationsused,differentarchitecturesanddesignshavebeenappliedinWSNs.Theperformanceofaroutingprotocoldependsonthearchitectureanddesignofthenetwork,andthisisaveryimportantfeatureofWSNs.However,theoperationoftheprotocolcanaffecttheenergyspentforthetransmissionofthedata.

ThemainobjectiveofcurrentresearchinWSNsistodesignenergy-efficientnodesandprotocolsthatcouldsupportvariousaspectsofnetworkoperations.In2000and2002,thePicoRadioproject[29]atBerkeleyandAMPsproject[30]atMIT,respectively,focusedontheenergy-constrainedradiosandtheirimpactontheultra-low-powersensingandnetworking.

Theinitialeffortstodevelopenergy-efficientsensorsaremostlydrivenbyacademicinstitutions.However,thelastdecadeanumberofcommercialeffortshavealsoappeared(alotofthembasedonsomeoftheaboveacademicefforts),includingcompaniessuchasCrossbow,Sensoria,Worldsens,DustNetworksandEmberCorporation.Thesecompaniesprovidetheopportunitytopurchasesensordevicesreadyfordeploymentinavarietyofapplicationscenariosalongwithvariousmanagementtoolsforprogramming,maintenance,andsensordatavisualization.

Inparalleltothedevelopmentofthehardwareofthesensors,andinordertoprovideenergy-efficientsolutions,thedevelopmentofroutingprotocolsthatwillrequirelessenergy,resultingintheextensionofthenetworklifetime,isanongoingresearcharea.Thesimplestideaistogreedilyswitchtolowermodewheneverpossible.Theproblemisthatthetimeandpowerconsumptionrequiredtoreachhighermodesisnotnegligible.So,techniquesandprotocolsthatwouldconsiderenergyefficiencyandtransmitpacketsthroughenergy-efficientroutingprotocolsandthusprolongingthelifetimeofthenetwork,arerequired.Mostoftheenergyconsumption,inWSNs,isspentonthreemainactivities:sensing,dataprocessingandcommunication.AllthesefactorsareimportantandshouldbeconsideredwhendevelopingprotocolsforWSNs.Thecommunicationofthesensornodesisthemajorcomponentoftheenergyconsumption.Thus,theon-goingresearchinWSNsismostlyconcentratedondesigningprotocolsthatusethelesspossibleenergyduringthecommunicationofthenodes.

Thepotentialtaskoftheprotocolsisnotonlytofindthelowestenergypathfromasourcetoadestination,butalsotofindthemostefficientwaytoextendthenetwork’slifetime.Thecontinuoususeofalowenergypathfrequentlyleadstoenergydepletionofthenodesalongthispathandintheworstitcasemayleadtonetworkpartition.

TherearesometermsrelatedtotheenergyefficiencyonWSNsthatareusedtoevaluatetheperformanceoftheroutingprotocolsandherearethemostimportantones[31]:

•EnergyperPacket.Thistermisreferredtotheamountoftheenergythatisspentwhilesendingapacketfromasourcetoadestination.

•EnergyandReliability.Itreferstothewaythatatradeoffbetweendifferentapplicationrequirementsisachieved.Insomeapplications,emergencyeventsmayjustifyanincreasedenergycosttospeedupthereportingofsucheventsortoincreasetheredundancyofthetransmissionbyusingseveralpaths.

•NetworkLifetime.Thereisnoneuniversallyagreeddef-initionforthenetworklifetime.Inmanycasesthetermnetworklifetimecorrespondstothetimewhenthefirstnodeexhaustsitsenergy,orwhenacertainfractionofthenetwork’snodesisdead,orevenwhenallnodesaredead.Insomeothercasesitmaybereasonabletomeasurethenetworklifetimebyapplication-specificparameters,suchasthetimewhenthenetworkcannolongerrelaythevideo.However,theimportanceofaWSNistobeoperationalandabletoperformitstasksduringitsuse.InWSNs,itisimportanttomaximizethenetworklifetime,whichmeanstoincreasethenetworksurvivabilityortoprolongthebatterylifetimeofnodes.Thecommonpracticeinnetworksistousetheshortestroutestotransferthepackets.Thiscouldresultthedeathofthenodesalongtheshortestpath.SinceinaWSNeverynodehastoactasarelayinordertoforwardthemessage,ifsomenodesdiesooner,duetothelackofenergy,itispossiblethatothernodeswillnotbeabletocommunicateanymore.Hence,thenetworkwillgetdisconnected,theenergyconsumptionisnotbalancedandthelifetimeofthewholenetworkisseriouslyaffected.Therefore,acombinationbetweentheshortestpathandtheextensionofthenetworklifetimeisthemostsuitableroutingmetricstobeusedinWSNs.Moreover,thelifetimeofanodeiseffectivelydeterminedbyitsbatterylife.Themaindrainageofbatteryisduetotransmittingandreceivingdataamongnodesandtheprocessingelements.•AverageEnergyDissipated.Thismetricisrelatedtothenetworklifetimeandshowstheaveragedissipationofenergypernodeovertimeinthenetworkasitperformsvariousfunctionssuchastransmitting,receiving,sensingandaggregationofdata.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

7

•

LowEnergyConsumption.Alowenergyprotocolhastoconsumelessenergythantraditionalprotocols.Thismeansthataprotocolthattakesintoconsiderationtheremainingenergylevelofthenodesandselectsroutesthatmaximizethenetwork’slifetimeisconsideredaslowenergyprotocol.

•TotalNumberofNodesAlive.Thismetricisalsorelatedtothenetworklifetime.Itgivesanideaoftheareacoverageofthenetworkovertime.

•TotalNumberofDataSignalsReceivedatBS.Thismetricisequivalenttotheenergysavedbytheprotocolbynottransmittingcontinuouslydatapackets(hellomessages),whicharenotrequired.

•AveragePacketDelay.Thismetriciscalculatedastheaverageone-waylatencythatisobservedbetweenthetransmissionandreceptionofadatapacketatthesink.Thismetricmeasuresthetemporalaccuracyofapacket.•PacketDeliveryRatio.Itiscalculatedastheratioofthenumberofdistinctpacketsreceivedatsinkstothenumberoriginallysentfromsourcesensors.Thismetricindicatesthereliabilityofdatadelivery.

•TimeuntiltheFirstNodeDies.Thismetricindicatesthedurationforwhichallthesensornodesonthenetworkarealive.Thereareprotocolsinwhichthefirstnodeonthenetworkrunsoutofenergyearlierthaninotherprotocols,butmanagestokeepthenetworkoperationalmuchlonger.

•EnergySpentperRound.Thismetricisrelatedtothetotalamountofenergyspentinroutingmessagesinaround.Itisashort-termmeasuredesignedtoprovideanideaoftheenergyefficiencyofanyproposedmethodinaparticularround.

•IdleListening.Asensornodethatisinidlelisteningmode,doesnotsendorreceivedata,itcanstillconsumeasubstantialamountofenergy.Therefore,thisnodeshouldnotstayinidlelisteningmode,butshouldbepoweredoff.

•PacketSize.Thesizeofapacketdeterminesthetimethatatransmissionwilllast.Therefore,itiseffectiveinenergyconsumption.Thepacketsizehastobereducedbycombiningseveralpacketsintoonelargepacketorbycompression.

•Distance.Thedistancebetweenthetransmitterandre-ceivercanaffectthepowerthatisrequiredtosendandreceivepackets.Theroutingprotocolscanselecttheshortestpathsbetweennodesandreduceenergyconsumption.

TheselectionoftheenergyefficientprotocolsinWSNsisareallycriticalissueandshouldbeconsideredinallnetworks.Thereareseveralpoliciesforenergy-efficientrouteselection.Themostknowniscalled”CallPacking”.Thispolicyroutesnewcallsonheavily-loadedratherthanlightly-loadedlinks.Theadvantageofcallpackingisthatitfavorshigh-bandwidthcalls;butitsmaindisadvantageisthatitcallsupsomelinkscompletely,andthusreducingtheconnectivityofthenetwork.Theloadbalancingpolicy,incontrasttocallbalancing,triestospreadtheloadevenlyamongthelinks.Thispolicydecidestoroutenewcallsonlightlyloadedpathsratherthanonheavilyloadedones.

Athirdpolicy,called”themin-hoppolicy”,routesacallontheminimum-hoppaththatmeetstheenergyefficiencyrequirements.Thistypeofpolicyhastraditionallybeenusefulinenergy-efficientWSNs.

Theload-balancingpolicyisagoodperformingpolicyinalltopologies,andthecallpackingpolicyistheworstinalltopologies.Inmostcases,thedifferencebetweentheloadbalancingandminimum-hoppoliciesisverysmall.Therelativeperformanceofcallpackingtoloadbalancingisworseinsparselyconnectednetworks,asopposedtodenselyconnectednetworks.

Moreover,thereareschemesformulti-hoprouting.Twooftheseschemesarecomparedin[32].Thefirstmaximizestheminimumlifetimeofthenodes,whilethesecondoneminimizestotalenergyconsumption.Thesimulationresultsin[32]considerthetransmissionenergyandthecircuitenergyspentintransmission,aswellasthereceiverenergy.Thecomparisonrevealsthatmultihoproutingispreferredbythefirstschemewhentheratiooftransmissionenergytocircuitenergyislowandbythesecondschemewhenthisratioishigh.Inordertobalancetheload,thefirstschemelimitstherangeofmulti-hoprouting.Following,weexaminesomeenergy-efficientroutingprotocols.A.EfficientMinimum-CostRouting

Routingalgorithms,whicharecloselyassociatedwithdy-namicprogramming,canbebasedondifferentnetworkanal-ysesandgraphtheoreticconceptsindatacommunicationsys-temsincludingmaximalflow,shortest-route,andminimum-spanproblems.TheShortestPathroutingschemesfigureouttheshortestpathfromanygivennodetothedestinationnode.Ifthecost,insteadofthelinklength,isassociatedwitheachlink,thesealgorithmscanalsocomputetheminimumcostroutes.Thesealgorithmscanbecentralizedordecentralized.TheusualwayofroutinginWSNsistoroutepacketsontheminimum-costpathfromthesourcetothedestination(sinkorbasestation).Incasethatthenodesgeneratedataconstantlyandthebandwidthisconstrained,thenroutingdataontheminimum-costpathscanoverloadwirelesslinksclosetothebasestation.Therefore,aroutingprotocolmusttakeintoconsiderationthewirelesschannelbandwidthlimitation,otherwise,itmightroutethepacketsoverhighlycongestedlinksandpaths.Thiswillleadtoanincreaseofcongestion,increaseddelayandpacketlosses,whichinturnwillcauseretransmissionofpackets,andtherebyincreasingenergycon-sumption.

TheefficientDijkstraalgorithm,whichhaspolynomialcomplexity,andtheBellman-Fordalgorithm,whichfindsthepathwiththeleastnumberofhopsarethetwoverywell-knownandwell-definedalgorithmsforshortestpathrouting.Following,someoftheexistingefficientminimum-costroutingalgorithmsarediscussed.

1)EfficientMinimum-CostBandwidth-ConstrainedRouting(MCBCR)inWSNs:TheEMCBCRroutingprotocolproposedin[33]at2000,isasimple,scalableandefficientsolutiontotheminimumcostroutingprobleminWSNs.Itisaprotocolwhichfindsthemostappropriateroutesfortransferringdatafromsensornodestobasestationsandthusreducingtothe

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

8

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

minimumtheentirecostofrouting,whileguaranteeingthattheloadoneachwirelesslinkdoesnotoverrunitscapacity.Theprotocolisderivedfromacombinatorialoptimizationproblem,knownastheminimumcostflowproblemintheoperationsresearchliterature.Thisprotocolishighlyscalablebecausepolynomial-timeminimumcostflowalgorithmsareused.SimulationresultshaveshownthattheproposedprotocolMCBCRhasgoodperformanceandachieveslongnetworklifetime[33].

2)AScalableSolutiontoMinimum-CostForwarding(SSMCF)inLargeSensorNetworks:FanYeetal.[34]at2001,studiedtheproblemofminimumcostmessagesdeliveryfromanygivensourcetotheinterestedclientuser(calledasink)alongtheminimum-costpathinalargesensornetwork.Whenthefieldisestablished,themessage,thatcarriesdynamiccostinformation,flowsalongtheminimumcostpathinthecostfield.Theintermediatenodesforwardthemessageonlyiftheyfindthemselvestobeontheoptimalpath,basedondynamiccoststates.Theintermediatenodestomaintainexplicitforwardingpathstatesarenotrequiredinthisdesign.Thisalgorithmrequiresonlyafewsimpleoperationsandscalestoanynetworksize.

Theirdesignwasbasedonthefollowingthreegoals:

•Optimality:Toachieveminimumcostforwarding,whilethedesignofthemostdataforwardingprotocolsisbasedonachosenoptimalitycriterion.

•Simplicity:Toreducetotheminimumthenumberoftheperformedoperationsaswellasthestateswhicharemaintainedateachsensornodeparticipatingindataforwarding.

•Scalability:Thesolutionhastoscaletolargenetworksize,sinceunconstrainedscaleisaninherentfeatureofasensornetwork.

Thisapproachrequiresconstanttimeandspacecomplexitiesateachnode,andscalestolargenetworksize.B.MinimumNetworkOverhead

TheoverheadenergyisasubstantialcomponentofenergyconsumptionatsensornodesinaWSN.Negligenceoftheoverheadenergyinenergy-efficientroutingdecisionsmightresultinnon-optimalenergyusage.Routingalgorithmsshouldbefocusedontheoverheadenergywhichisconsumed,andthereforewasted,ateachhopofdatatransmissionthroughthewirelessnetwork.Theuseofshortermulti-hoplinksappearsasamoreadvantageoussolution,ifonlythetransmissionenergyisconsideredasthecommunicationcost.

However,becauseofotherenergy-dissipatingactivitiesonthesensornodes,suchas,receptionofrelayedmessages,sensingandcomputationtasks,aconsiderableoverheaden-ergymightbeconsumedwhileforwardingamessage,somedissipationmodels,proposedat2002,2005,2008respectively,arepresentedin[35],[36],[37].Therefore,multi-hoppingissometimesadisadvantageinwirelesssensornetworks.RecentresearchhasrecentlyfocusedonminimizingWSNsoverheadbytakingintoaccountvariousfactors,suchas,theenergyconsumedatsensingtheenvironment,computingthecollectedinformation,relayingmessages,andtransmittingdataateachhopthroughtheWSN.

C.ChallengingFactorsAffectingtheEnergy-EfficientRoutingProtocolsDesignIssues

WSNs,despitetheirinnumerableapplications,sufferfromseveralrestrictionsconcerning,mainly,limitedenergyde-posits,limitedprocessingpower,andlimitedbandwidthofthewirelesslinksconnectingsensornodes.OneofthemostsignificantdesigngoalsofWSNsistogothroughdatacommunicationwhiletrying,atthesametime,tocontributetothelongevityofthenetworkandtoprecludeconnectivityabasementthroughtheuseofaggressiveenergymanagementtechniques.Thedesignofenergy-efficientroutingprotocolsinWSNsisinfluencedbymanyfactors.ThesefactorsmustgetoverbeforeefficientcommunicationcanbeachievedinWSNs.

Hereisalistofthemostcommonfactorsaffectingtheroutingprotocolsdesign[38]:

•

NodeDeployment:Itisanapplication-dependentopera-tionaffectingtheroutingprotocolperformance,andcanbeeitherdeterministicorrandomized.

•

Node/LinkHeterogeneity:Theexistenceofheterogeneoussetofsensorsgivesrisetomanytechnicalproblemsrelatedtodataroutingandtheyhavetobeovercome.•

DataReportingModel:Datasensing,measurementandreportinginWSNsdependontheapplicationandthetimecriticalityofthedatareporting.Datareportingcanbecategorizedaseithertime-driven(continuous),event-driven,query-driven,andhybrid.

•

EnergyConsumptionWithoutLosingAccuracy:Inthiscase,energy-conservingmechanismsofdatacommuni-cationandprocessingaremorethannecessary.

•

Scalability:WSNsroutingprotocolsshouldbescalableenoughtorespondtoevents,e.g.hugeincreaseofsensornodes,intheenvironment.

•

NetworkDynamics:Mobilityofsensornodesisneces-saryinmanyapplications,despitethefactthatmostofthenetworkarchitecturesassumethatsensornodesarestationary.

•FaultTolerance:Theoveralltaskofthesensornetworkshouldnotbeaffectedbythefailureofsensornodes.•Connectivity:Thesensornodesconnectivitydependsontherandomdistributionofnodes.

•

TransmissionMedia:Inamulti-hopWSN,communicat-ingnodesarelinkedbyawirelessmedium.OneapproachofMACdesignforsensornetworksistouseTDMA-basedprotocolsthatconservemoreenergycomparedtocontention-basedprotocolslikeCSMA(e.g.,IEEE802.11).

•

Coverage:InWSNs,agivensensor’sviewoftheenvi-ronmentislimitedbothinrangeandinaccuracy;itcanonlycoveralimitedphysicalareaoftheenvironment.•

QualityofService:Datashouldbedeliveredwithinacertainperiodoftime.However,inagoodnumberofapplications,conservationofenergy,whichisdirectlyrelatedtonetworklifetime,isconsideredrelativelymoreimportantthanthequalityofdatasent.Hence,energy-awareroutingprotocolsarerequiredtocapturethisrequirement.

•

DataAggregation:Dataaggregationisthecombination

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

9

ofdatafromdifferentsourcesaccordingtoacertainaggregationfunction,e.g.duplicatesuppression.V.ROUTINGTECHNIQUESINWSNS-CLASSIFICATIONRoutinginWSNsmaybemoredemandingthanotherwirelessnetworks,likemobilead-hocnetworksorcellularnetworksforthefollowingreasons:

•Sensornodesdemandcarefulresourcemanagementbe-causeoftheirsevereconstraintsinenergy,processingandstoragecapacities.

•AlmostallapplicationsofWSNsrequiretheflowofsenseddatafrommultiplesourcestoaparticularbasestation.

•DesignrequirementsofaWSNdependontheapplica-tion,becauseWSNsareapplication-specific.

•ThenodesinWSNsaremostlystationaryaftertheirdeploymentwhichresultsinpredictableandnon-frequenttopologicalchanges.

•Datacollectionis,undernormalconditions,basedonthelocation,therefore,positionawarenessofsensornodesisimportant.Thepositionofthesensornodesisdetectedbyusingmethodsbasedontriangulatione.g.radiostrengthfromafewknownpoints.Forthetimebeing,itispossibletouseGlobalPositioningSystem(GPS)hardwareforthispurpose.Moreover,itisfavorabletohavesolutionsindependentofGPSforthelocationprobleminWSNs[39].

•InWSNs,thereisahighprobabilitythatcollecteddatamaypresentsomeundesirableredundancywhichisnecessarytobeexploitedbytheroutingprotocolstoimproveenergyandbandwidthutilization.

Becauseofallthesedisparities,severalnewroutingmecha-nismshavebeendevelopedandproposedtosolvetheroutingprobleminWSNs.TheseroutingmechanismshavetakenintoaccounttheinherentfeaturesofWSNsalongwiththeapplicationandarchitecturerequirements.Ahighefficientroutingschemewilloffersignificantpowercostreductionsandwillimprovenetworklongevity.FindingandmaintainingroutesinWSNsisamajorissuesinceenergyconstraintsandunexpectedchangesinnodestatus(e.g.,inefficiencyorfailure)giverisetofrequentandunforeseentopologicalalterations.RoutingtechniquesproposedintheliteratureforWSNsemploysomewell-knownroutingtactics,suitableforWSNs,tominimizeenergyconsumption.Inthispaper,weexpandtheclassificationinitiallyproposedbyAl-Karakiin[3].Thus,theroutingprotocolscanbeclassifiedintofourmainschemes:NetworkStructureScheme,CommunicationModelScheme,TopologyBasedSchemeandReliableRoutingScheme(figure3).Also,thepresentedclassificationcanbeviewedasfourdifferentapproachestoclassifytheprotocols,ratherthanfourparallelclasses.A.NetworkStructure

Thestructureofanetworkcanbeclassifiedaccordingtonodeuniformity.Thenodesinsomenetworksareconsideredtobedeployeduniformlyandbeequaltoeachother,orothernetworksmakedistinctionsbetweendifferentnodes.Morespecifically,themainattributeoftheroutingprotocols

belongingtothiscategoryisthewaythatthenodesarecon-nectedandtheyroutetheinformationbasedonthenetworksarchitecture.Thisaddressestwotypesofnodedeployments,nodeswiththesamelevelofconnectionandnodeswithdifferenthierarchies.Therefore,theschemesonthiscategorycanbefurtherclassifiedasfollows:

•FlatProtocols:Allthenodesinthenetworkplaythesamerole.Flatnetworkarchitecturepresentsseveraladvantages,includingminimaloverheadtomaintaintheinfrastructurebetweencommunicatingnodes.

•HierarchicalProtocols:Theroutingprotocolsonthisschemeimposeastructureonthenetworktoachieveenergyefficiency,stability,andscalability.Inthisclassofprotocols,networknodesareorganizedinclustersinwhichanodewithhigherresidualenergy,forexample,assumestheroleofaclusterhead.Theclusterheadisresponsibleforcoordinatingactivitieswithintheclusterandforwardinginformationbetweenclusters.Clusteringhasthepotentialtoreduceenergyconsumptionandextendthelifetimeofthenetwork.Theyhavehighdeliveryratioandscalabilityandcanbalancetheenergyconsumption.Thenodesaroundthebasestationorclusterheadwilldepletetheirenergysourcesfasterthantheothernodes.Networkdisconnectivityisaproblemwherecertainsectionsofthenetworkcanbecomeunreachable.Ifthereisonlyonenodeconnectingapartofthenetworktotherestandfails,thenthissectionwouldcutofffromtherestofthenetwork.B.CommunicationModel

TheCommunicationModeladaptedinaroutingprotocolisrelatedtothewaythatthemainoperationoftheprotocolisfollowedinordertoroutepacketsinthenetwork.Theprotocolsofthiscategorycandelivermoredataforagivenamountofenergy.Alsointermsofdisseminationrateandenergyusagetheprotocolsofthisclasscanperformclosethetheoreticaloptimuminpoint-to-pointandbroadcastnetworks.TheproblemwithCommunicationModelprotocolsisthattheydonothavehighdeliveryratioforthedatathataresenttoadestination.Thus,theydonotguaranteethedeliveryofdata.

Theprotocolsonthisschemecanbeclassifiedasfollows:•Query-BasedProtocols:Thedestinationnodespropagateaqueryfordata(sensingtask)fromanodethroughthenetworkandanodehavingthisdatasendsthedata,whichmatchesthequery,backtothenode,whichinturninitiatesthequery.

•CoherentandNon-Coherent-BasedProtocols:Incoher-entrouting,thedataisforwardedtoaggregatorsafteraminimumprocessing.Innon-coherentdataprocessingrouting,nodeslocallyprocesstherawdatabeforeitissenttoothernodesforfurtherprocessing.

•Negotiation-BasedProtocols:Theyusemeta-datanegoti-ationstoreduceredundanttransmissionsinthenetwork.C.TopologyBasedProtocols

Topology-basedprotocolsusetheprinciplethateverynodeinanetworkmaintainstopologyinformationandthatthemain

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

10

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

Routing Protocols in WSNsNetwork StructureCommunication ModelTopology BasedReliable RoutingQuery-Based ProtocolsMobile Agent-Based ProtocolsHierarchical ProtocolsNegotiation-Based ProtocolsMultipath-Based ProtocolsCoherent-Based ProtocolsLocation-Based ProtocolsFlat ProtocolsQoS-Based ProtocolsFig.3.ClassificationofroutingprotocolsinWSNs.

processoftheprotocoloperationisbasedonthetopologyofthenetwork.Theprotocolsonthisschemecanbefurtherclassifiedasfollows:

•Location-basedProtocols:TheytakeadvantageofthepositioninformationinordertorelaythereceiveddatatoonlycertainregionsandnottothewholeWSN.Theprotocolsofthisclasscanfindapathfromasourcetoadestinationandminimizetheenergyconsumptionofthesensornodes.Theyhavelimitedscalabilityincasethatthenodesaremobile.Alsoanodemustknoworlearnaboutthelocationsofothernodes.

•MobileAgent-basedProtocols:Themobileagentproto-colsareusedinWSNstoroutedatafromthesensedareatothedestinationandthisisaninterestingsector.Themobileagentsystemshaveasamaincomponentamobileagent,whichmigratesamongthenodesofanetworktoperformataskautonomouslyandintelligently,basedontheenvironmentconditions.Mobileagentprotocolsmayprovidetothenetworkextraflexibility,aswellasnewcapabilitiesincontrasttotheconventionalWSNoperationsthatarebasedontheclient-servercomputingmodel.D.ReliableRoutingProtocols

Theprotocolsonthisschemearemoreresilienttoroutefailureseitherbyachievingloadbalancingroutesorbysat-isfyingcertainQoSmetrics,asdelay,energy,andbandwidth.ThenodesofthenetworkmaysufferfromtheoverheadofmaintainingroutingtablesandtheQoSmetricsateachsensornode.Theprotocolsareclassifiedasfollows:

•Multipath-BasedProtocols:Theyachieveloadbalancingandaremoreresilienttoroutefailures.

•QoS-BasedProtocols:Thenetworkhastobalancebe-tweenenergyconsumptionanddataquality.Wheneverasinkrequestsfordatafromthesensednodesinthenetwork,thetransmissionhastomeetspecificlevelofquality.E.ComparisonoftheRoutingCategories

ThemainattributeoftheprotocolsbelongingtotheNet-workStructureisthewaythenodesareconnectedandexertsaninfluenceontheroutingoftheinformation.Forexample,inahierarchicalstructurethelowerlevelnodestransittheinformationtoupperlevernodes,resultingtoabalancedenergystructureofthenetwork.

However,intheCommunicationModel,themaincharac-teristicoftheprotocolsisthewaythataroutingdecisionismadeup,withoutmainlybasedonthestructureofthenetwork.Thus,awelldefinedtechnique,forexamplethenegotiationofthenodeswitheachotherbeforetransmittingdataisconsidered,toroutetheinformationfromthesourcetothedestination.

Moreover,therearesomeprotocolsthatapartfromtheCommunicationModelthattheyuseforthedatatransmission,theytakeintoconsiderationthetopologyofthenetwork.Theyoperatewithoutanyroutingtables,byperiodicallytransmittingHELLOmessagestoallowneighborstoknowtheirpositions.Asetoftheseprotocolusemobileagentsinordertomovethedataprocessingelementstothelocationofthesenseddatamayreducetheenergyexpendituresofthenodes.Finally,thereisacategoryofprotocolsthatapartoftheenergyefficiencytheytendtoprovidereliableroutingofthedata.TheyachievethiseitherbyprovidingmultiplepathfromthesourcetothedestinationorbyapplyingQoSontheirmainroutingactivity.Itshouldbenotedthatsomeoftheprotocolsdescribedbelow,mayfalltooneormoreoftheaboveroutingcategories,butonlydiscussedoncetocategorythattheymainlyfit.Also,theTablesII,III,IV,V,VI,VII,VIII,IXandXsummarizetheadvantagesanddisadvantagesofeachprotocoldescribedinthepaper.Moreover,somemetricsforeachprotocol,thatmaybeusefulforthereader,arepresented.Thesemetricsarethefollowing:

•Scalability.Thescalabilityreferstotheabilityoftheprotocoltohandlegrowingamountsofworkinagracefulmanner.Thismeansthattheperformanceoftheprotocolwillbestableforbothsmallandlargenetworks.

•Mobility.Themobilityreferstotheabilityoftheprotocoltoworkincasethatthenodesaremobile.

•RouteMetric.Theroutemetricreferstotheformofroutingwhichattemptstosendpacketsofdataoveranetworkinsuchawaythatthepathtakenfromthesend-ingnodetotherecipientnodeisthemostefficient.Thus,thispathmaybetheshortestpath,whichminimizestheenergyconsumedbynodes,orthepaththatmaximizes

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

11

thenetwork’slifetimeandtakesintoconsiderationtheremainingenergyofthenodes.

•

PeriodicMessageType.Theperiodicmessagetypeisthemessagesthatthenodesexchangeinordertohaveanuptodateviewofthenodesthatarealiveonthenetwork.•

Robust.Aprotocolthatperformswellevenincasesofunordinaryconditions,forexampleinsuddenchangesofthetopologyofthenetwork,isconsideredasrobustprotocol.

VI.NETWORKSTRUCTURESCHEME

A.FlatNetworksRoutingProtocols

Ingeneral,FlatNetworksRoutingProtocolsforWSNscanbeclassified,accordingtotheroutingstrategy,intothreemaindifferentcategories:Pro-activeprotocols,Re-activeprotocolsandHybridprotocols[40].Alltheseprotocolsdifferinmanywaysanddonotpresentthesamecharacteristics,althoughtheyhavebeendesignedforthesameunderlyingnetwork.Accordingtoanotherclassificationfoundintheliterature,FlatNetworksroutingprotocolsforWSNscanbecategorizedasTable-drivenandSource-initiated(orDemand-driven)re-spectively(Pro-activeandRe-activeroutingprotocols).Thefollowingsectionsdiscusstheseprotocolsandclassifythemaccordingtotheircharacteristics.

1)Pro-activeorTable-DrivenRoutingProtocols:Pro-active(ortable-drivenroutingprotocols)workinawaysimilartowirednetworks:basedontheperiodicallyexchangingofroutinginformationbetweenthedifferentnodes,eachnodebuildsitsownroutingtablewhichcanbeusedtofindapathtoadestination.Eachnodeisrequiredtomaintainoneormaybemoretablesbystoringroutinginformation.Theyalsorespondtoanychangesinnetworktopologybysendingupdatesthroughoutthewirelessnetworkandthusmaintainingaconsistentnetworkview.Therefore,whenapathtosomedestinationisneededatanode,orapacketneedstobeforwarded,therouteisalreadyknownandthereisnoextradelayduetoroutediscovery.However,keepingtheinforma-tionup-to-date,itmayrequirealotofbandwidth,whichissparse,andextrabatterypower,whichislimitedinWSNs.Theinformationmaystillbeout-of-date.Following,someoftheexistingtable-drivenroutingprotocolsarediscussed.

a)WirelessRoutingProtocol(WRP):TheWRPprotocolisatable-basedroutingprotocol,whichinheritsthepropertiesofthedistributedBellman-Fordalgorithm[41].TheWEPmaintainsanup-to-dateviewofthenetworkbyusingasetoftablestomaintainmoreaccurateinformation.Thetablesthataremaintainedbyanodearethefollowingones:DistanceTable(DT),RoutingTable(RT),LinkCostTable(LCT),andaMessageRetransmissionList(MRL).

EachentryoftheMRLcontainsthefollowing:

•A•Asequencenumberoftheupdate•Anretransmissionacknowledgement-requiredcounter,

message,flagvectorwithoneentryperneighborand

•

Alistofupdatessentintheupdatemessage.Mobilenodesinformeachotherofanylinkchangesbymeansofupdatemessages.

Anupdatemessageistransmittedonlyamongneighboringnodesandcontainsalistofupdates(suchas,thedestination,thedistancetothedestination,andtheforerunnerofthedestination)andalistofresponsesindicatingwhichmobilenodesshouldacknowledgetheupdates.Inthecaseofthelossofalinkbetweenanytwonodes,thenodestransmitupdatemessagestotheirneighbors.Following,theneighborschangetheirdistancetableentriesandcheckfornewpathsamongothernodes.Anynewpathsarerelayedbacktotheoriginalnodessothattheycanupdatetheirtablesaccordingly.

InWRP,eachnodeisfocusedonperformingconsistencychecksofpredecessorinformationreportedbyallitsneigh-bors.Thiscanminimizeloopingsituationsandcanprovidefasterrouteconvergencewhenalinkfailureeventoccurs.Ingeneral,WRPhasfastconvergenceandinvolvesfewtableupdates.ButitdemandslargememoryandgreatprocessingpowerfromnodesintheWSN,duetothecomplexityofmaintenanceofmultipletables.Thus,itsuffersfromlimitedscalabilityandisnotsuitableforlargemobilenetworks.

b)TheTopologyDisseminationBasedonReverse-PathForwardingProtocol(TBRPF):TheTBRPFprotocoltrans-mitsonlythedifferencesbetweenthepreviousnetworkstateandthecurrentnetworkstate[42],[43].Thisresultsinsmallerroutingmessages,thatcanbesentmorefrequently.Thismeansthattheroutingtablesofthenodesaremoreup-to-date.TBRPFprotocolappliestheconceptofreverse-pathforwardingtobroadcastlink-stateupdatesinthereversedirectionalongthespanningtreeformedbytheminimum-hoppathsfromallsensornodestothesourceoftheupdate.Theinformationreceivedthroughthesebroadcasttreescanbeusedtocomputetheminimum-hoppathsthatformthetreesthemselves.Sinceminimum-hoppathshavebeencomputed,eachsourcenodebroadcastslink-stateupdatesforitsoutgoinglinksalongaminimum-hoptreerootedatthesourceandaseparatebroadcasttreeiscreatedforeachsource.

Theprotocolstoresthefollowinginformationateachnodeofthenetwork:

•Atopologytable,consistingofalllink-statesstoredatthenodeand

•AForlisteachofneighbornode:anodes

•parent,alistofchildrenandthesequencenumberofthemostrecentlink-stateupdate.ThemainideainTBRPFistobroadcasttopologyupdatesinreversedirectionalongthistree.Meanwhile,modifyingisbasedonthenewtopologyinformation,receivedalongthetree.Thebroadcastofalink-stateupdateoriginatedatasourceisacceptedbyanothernodeifitisreceivedfromtheparentofthatnodeandifithasalargersequencenumberthanthecorrespondinglink-stateentryinthetopologytable.Thetopologytableisupdatedandthenforwardedtoallchildrenofthenodeonlyifthelink-stateupdateisaccepted.ThepropertiesofTBRPFProtocolare:•ItItisusesapro-activeaminimum-hopprotocol

•spanningtreetobroadcastlink-stateupdates

•Theminimum-hopspanningtreeisrootedtotheupdateofthesource

•Theminimum-hoptreeismaintainedwithinforeceivedbythetreeitself

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

12

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

•

Eachnodeisprovidedwithfulltopologyinformation•Multiplepathstodestinationsarepossible

Periodictopologyupdatesaresentlessfrequentlythanotherprotocolsofthiscategory.Theseupdatesarelargemessageswhichensurethateachnodeeventuallycanlearnthewholetopology.TheTBRPFisnotsuitablefornetworkswithlowmobility(e.g.stationarybattery-poweredsensornetworks).Thelackofloop-freedomcausespacketlossandwasteofbandwidth.

2)Re-activeorSource-InitiatedOn-DemandRoutingPro-tocols:Adifferentapproachfromtable-drivenroutingisthesource-initiatedon-demandrouting.Unlikepro-active(table-driven)routingprotocols,re-activeprotocols(on-demandpro-tocols)onlystartaroutediscoveryprocedurewhenneeded[44].Whenaroutefromasourcetoadestinationisneeded,akindofglobalsearchprocedureisstarted.Thistaskdoesnotrequesttheconstantupdatestobesentthroughthenetwork,asinpro-activeprotocols,butthisprocessdoescausedelays,sincetherequestedroutesarenotavailableandhavetobefound.Insomecases,thedesiredroutesarestillintheroutecachemaintainedbythesensornodes.Whenthisisthecase,thereisnoadditionaldelaysinceroutesdonothavetobediscovered.Thewholeprocessiscompletedassoonasarouteisfoundorallpossibleroutecombinationshavebeenexamined.

Following,someoftheexistingon-demandroutingproto-colsarediscussed.

a)TemporarilyOrderedRoutingAlgorithm(TORA):TheTORAAlgorithmisahighlyadaptiveloop-freedistributedroutingalgorithm[45].Itisbasedontheconceptoflinkreversal.InTORA,eachnodeiknowsitsownheightandtheheightofeachdirectlyconnectedneighborj[46].Thus,thecontrolmessagesarelocalizedtoaverysmallsetofnodesneartheoccurrenceofatopologicalchangeinorderforthisprotocoltoprovideenergyefficiency.Itmarkseachlinkasupstreamordownstreambasedonwhethertheheightofitsneighborisgreaterorlessthanitsownheight.Nodesareassignedheightsbasedontheirlocationwithrespecttothedestination.Whenanodegetsadatapacket,italwaysforwardsitintothedownstreamdirection(figure4).Thuspacketsfindtheirwaytothedestinationflowingdownfromtallnodeslocatedfarawayfromthedestinationtoshortnodeslocatednearit.

ThemainadvantageofTORAisthatitwasdesignedtominimizethecommunicationoverheadassociatedwithadaptingtonetworktopologicalchangesandthus,tominimizetheenergyconsumption.Inadditionitsupportsmultipleroutesandmulticast.However,TORAdoesnotincorporatemulticastintoitsbasicoperation.

b)Gossiping:Gossipingandbroadcastingaretwoprob-lemsofinformationdisseminationdescribedforagroupofindividualsconnectedbymeansofacommunicationnetwork[47].Ingossiping,everypersoninthenetworkknowsauniqueitemofinformationandneedstocommunicateittoeveryoneelse.Inbroadcasting,oneindividualhasanitemofinformationwhichneedstobecommunicatedtoeveryoneelse.Actually,gossipingisaderivativeoffloodingwherenodesdonotbroadcastbutsendtheincomingpacketstoarandomlyselectedneighbor.Althoughthisapproachavoids

NodeHeightMeasurementDestinationFig.4.TheTORAisalwaysforwardspacketsintothedownstreamdirection(redrawnfrom[46]).

theimplosionproblembyjusthavingonecopyofamessageatanynode,ittakeslongtopropagatethemessagetoallsensornodesinthenetwork.

c)Flooding:Floodingisanoldandverysimpletech-niquewhichcanbealsousedforroutinginWSNs[48].Inflooding,copiesofincomingpacketsaresentbyeverylinkexcepttheonebywhichthepacketsarrived.Thisproceduregeneratesanenormousamountofsuperfluoustraffic.Floodingisanextremelyrobusttechniquebutaslongasthereisaroutefromsourcetodestinationthedeliveryofthepacketisguaranteed.

Floodingisareactivetechnique,anddoesnotrequirecostlytopologymaintenanceandcomplexroutediscoveryalgorithms.

However,ithasseveraldrawbacks,whichare:

•Implosion:Implosionisasituationwhereduplicatedmessagesarebroadcastedtothesamenode.

•

Overlay:Iftwonodessharethesameunderobservationregion,bothofthemmaysensethesamestimuliatthesametime.Asaresult,neighbornodesreceiveduplicatedmessages.

•

Resourceblindness:Thefloodingprotocoldoesnottakeintoconsiderationalltheavailableenergyresources.Anenergyresource-awareprotocolmusttakeintoaccounttheamountofenergywhichisavailabletothemallthetime.

Floodinghastwointerestingcharacteristicswhicharisefromthefactthatallpossibleroutesaretried:

•Aslongasthereisaroutefromsourcetodestination,thedeliveryofthepacketisguaranteed.

•

Onecopyofthepacketwillarrivebythequickestpossibleroute.

Floodingisanextremelyrobusttechniqueandwouldbeparticularlysuitableforabattlefieldsituation.Thesecondpropertymightbeusefulforroutelearning.

Moreover,floodingconsumesmuchenergy,asforeachdatapacket,allthenodesthatareinthebroadcastdomainwillreceivepacketsthattheywillforwardittotheirneighbors.Thus,theyrequirealargeamountofpowerthatcausesaprohibitivelyshortnetworklifetime.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

13

NodeEventQuery path to eventNode with path to eventQuery sourceFig.5.

RumorRoutingProtocol(redrawnfrom[50]).

Therehavebeensomeprotocolsdevelopedthatusefloodingasapartoftheirrouting[49].

d)RumorRouting(RR):TheRumorRoutingisacom-promisebetweenfloodingqueriesandfloodingeventnotifica-tions[50].Themainideaofthisprotocolistocreatepathsthatleadtoeachevent(figure5),unlikeeventfloodingwhichcreatesanetwork-widegradientfield.Thus,incasethataqueryisgenerateditcanbethensentonarandomwalkuntilitfindstheeventpath,insteadoffloodingitthroughoutthenetwork.Assoonastheeventpathisdiscovereditcanbefurtherrouteddirectlytotheevent.Ontheotherhand,ifthepathcannotbefound,theapplicationcantryre-submittingthequeryorfloodingit.

TheRumorRoutingcanbeagoodmethodfordeliveringqueriestoeventsinlargenetworksaccordingtoawiderangeofconditions(energyrequirementslowerthanthealterna-tives).Itisdesignedtobetunabletodifferentapplicationrequirements,whileitcanbeadjustedtosupportdifferentquerytoeventratios,successfuldeliveryrates,androuterepair.Furthermore,itisabletohandlenodefailuregracefully,degradingitsdeliveryratelinearlywiththenumberoffailednodes.

e)Energy-awareTemporarilyOrderedRoutingAlgo-rithm(E-TORA):TheE-TORAisanalterationofTORAanditsmainfocusistominimizetheenergyconsumptionofthenodes[51].TheclassicTORAchoosestherouteswiththeleasthopsaslongasthenetworktopologydoesn’tchange.Thismaycausetothenodesthatareonthemainrouteheavyload.Alsoifsomeroutesrepeatedlyincludethesamenode,thenodewillrunoutofitsenergymuchearlierthantheothernodes.Thus,theuseofnodesintheshorterpathwithoutconsideringtheirpowerleadstothedecreaseofthenetworklifetime.Thus,E-TORAwasproposedin[51]tosolvethisproblem.E-TORAtakesintoconsiderationthelevelofpowerofeachnodeandavoidsusingnodeswithlowenergy.Inaddition,theenergyconsumptionofnodesisbalancedinordertoavoidthatsomenodesexhausttheirenergyearlieriftheyareusedtoofrequently.

Incasethatanodewithnodirectedlinksandwitharoute-requiredflagrequiresaroutetothedestination,itbroadcastsa

QUERYpacketandsetsitsroute-requiredflag.WhenanodeireceivesaQUERYitreactsasfollows:

•

Ifnodeihasnodownstreamlinksanditsroute-requiredflagisun-set,itre-broadcaststheQUERYpacketandsetsitsroute-requiredflag.

•

Ifnodeihasnodownstreamlinksandtheroute-requiredflagisset,itdiscardstheQUERYpacket.

Thus,E-TORAtakesintoconsiderationtheenergyleftonthenodesinordertousenodeswithmorepowerandextendsthelifetimeofthenetwork.

3)ComparisonbetweenPro-activeandRe-activeProto-cols:Themaindifferencesbetweenpro-activeandre-activeprotocolsmaybesummarizedasfollows[52],[53]:

•

Proactiveprotocolsrequirealotofroutinginformationandmaintainroutinginformationindependentlyoftheneedforcommunication.Whereas,reactiveprotocolsareondemandandrequirelessamountofroutinginforma-tionforeachnodeandthuslessenergyconsumptionforthesensornodes.

•

Inproactiveprotocolsthereisnolatencyinroutedis-covery,sotheyaresuitableforrealtimetraffic.Inreactiveprotocolsthereisadelayduetoroutediscovery,whichiscalledrouteacquisitiondelaywhichmaynotbeappropriateforrealtimecommunication.

•

Pro-activeprotocolswastebandwidthandenergytope-riodicupdatesincomparisontoreactiveprotocolsthatdonotrequireperiodicupdatingandsotheysaveenergyandbandwidthduringinactivity.

•

Theproactiveprotocolsupdateroutesandtablescontin-uously.Inreactiveprotocolsaroutecanbefoundondemand.

•

Proactiveprotocolsneedtoobtainandmaintaintheroutinginformationforallthenodesinanetwork.Theyrequirealargecapacitytokeepnetworkinformationcurrent.Inreactiveprotocolsintermediatenodesdonothavetomakeroutingdecisions.Thereisnoneedtohaveinformationaboutnodes.

•

Proactiveprotocolssendupdatemessagesthroughoutthenetworkperiodicallyorwhenthetopologychanges.Thereisnoneedtosendtheupdatemessagewhentopologychangesincaseofreactiveprotocol.

•

Proactiveprotocolsaregoodforheavyloadsbutnotgoodenoughforlightloadswhilereactiveprotocolsaregoodforlightloadsandcollapseduringlargeloads.

•Proactiveprotocolsareneverburstybutreactiveprotocolscanbeburstyasthereiscongestionduringhighactivity.•

Ifroutinginformationchangesfrequently,thentheproac-tiveprotocolswouldnotexertanyimpactonthepacketdelivery,butasfarasreactiveprotocolsconcerns,ifroutinginformationchangesfrequently,asthisistheobviouscaseinMANETs,andifroutediscoveriesareneededforthosechangedroutes,thenreactiveprotocolsmayresultinalargevolumeofmessagingoverhead,sincerouterecoveriesrequireaglobalbroadcastondemand.

InTableI,acomparisonbetweenPro-activeandRe-activeProtocolsispresented.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

14

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

TABLEI

COMPARISONBETWEENPRO-ACTIVEANDRE-ACTIVE

PROTOCOLS

Pro-activeRe-activeProtocols

ProtocolsOndemandprotocols

X

UpdateroutescontinuouslyX

RouteacquisitiondelayX

Periodicupdating

XMaintaintheroutinginformationforX

allnodesinthenetwork

SendupdatemessageswhentheX

topologychanges

ProperforheavyloadsX

Bursty

X

ResultinalargevolumeofmessagingX

overhead

Theavailabilityofroutinginformationisakeyadvantageoftable-drivenroutingprotocols,becausefasterroutingdecisions-andconsequentlylessdelayinroutesetupprocess-canbemade,thaninthecaseofon-demandroutingprotocols[54].Ontheotherhand,thisimportantadvantageoftable-drivenroutingprotocolsrequiresperiodicroutingupdatestokeeptheroutingtablesup-to-date,whichinturncostshighersignalingtrafficthantherequiredon-demandroutingprotocols.Moreover,thismakesthesensornodestospendmoreenergyoftheirperiodicupdatemessages.However,forotherfunctionslikepathreconfigurationafterlinkfailures,therearevariationsbetweentheprotocolsofeachclass.Forexample,TORAisanon-demandroutingprotocol.Atthesametime,TORAuseslocalroutemaintenanceschemeswhichreducesignalingoverhead.

4)HybridRoutingProtocols:Hybridprotocolscombinetheadvantagesofbothpro-activeandre-activeroutingproto-cols;theylocallyusepro-activeroutingandinter-locallyusere-activerouting.Thisispartlybasedonthefollowingtwoassumptions:a)MostcommunicationinWSNstakesplacebetweennodesthatareclosetoeachother,andb)Changesintopologyareonlyimportantiftheyhappeninthevicinityofanode.Whenalinkfailsoranodedisappearsontheothersideofthenetwork,itaffectsonlythelocalneighborhoods;nodesontheothersideofthenetworkarenotaffected.

a)ZoneRoutingProtocol(ZRP):TheZRPisahybridroutingschemethatcombinesnotonlytheadvantagesofpro-activebutalsotheadvantagesofre-activeprotocolsinahybridscheme[55].Accordingtothisscheme,thenetworkisdividedintozonesandthezonesproactivelymaintainthetopologyofthezone,however,thereisnoperiodicexchangeofthetopologychangethroughoutthenetwork.Theneighboringnodesareinformedonlyatperiodicintervals.IfthereisneedforZRPtosearchforaparticularnode,thenitinitiatestheroutequeryandbroadcastsittotheneighboringsensornodes.Wheneverasensornode’slinkstateischanged,anoticewillbesentasfaraszoneradiushopsaway(i.e.,thezoneofthisnode).Hence,anodealwaysknowshowtoreachanothernodeinthesamezone.Thisalsolimitsthenumberofupdatestriggeredbyalinkstatechange.Ontheotherhand,theinter-zoneroutingusesascheme,whenanodeneedsaroutetoanodeoutsideitszone;itperformsabordercastingbysendingaRREQ(RouteREQuest)toeachnodeonthe”border”of

thiszone.Onreceivingsuchapacketatabordernode,itfirstchecksitsintra-zoneroutingtableforexistenceofaroutetotherequesteddestinationnode.Ifso,aRREP(RouteREPly)canbesent;otherwise,itperformsanotherbordercastinginitszone.Thisisrepeateduntilarouteisfound.

ThemainadvantageofZRPisthatitrequiresasmallamountofroutinginformationateachnode,soitproducesmuchlessroutingtrafficthanapurereactiveorproactivescheme[56].However,itexperiencesexcessivedelaysandoverheadduetomanyuselesscontrolpacketsthataresentinthenetwork.Therefore,theloadofnetworkisincreasedresultinginadecreaseofnetworkperformance.

InTableII,FlatRoutingSchemesComparisonispresented.TheprotocolsTBRPD,TORA,Gossiping,E-TORAandZRPareefficientincasethatthenodesaremoving.Moreover,protocolsTBRPF,RRandZRParereallyrobust,mainlyduetothefactthattheyuseperiodichellomessagestodiscoverlivenodesinthenetwork.Ontheotherhand,E-TORAandZRPdonotusetheshortestpathastheotherprotocols,buttheyselectthebestroutebasedonenergyofthenodes.Moreover,TORA,Gossiping,RRandE-TORAaremorescalablethantheotherprotocolsofthisscheme.

Finally,inFlatProtocolsafewprotocolscanpartiallybeincluded,thataremainlyclassifiedanddescribedindetailsinthecategoriesonthebelow.Theseprotocolsare:OGFandHGR.

B.HierarchicalNetworksRoutingProtocols

Unlikeflatprotocols,whereeachnodehasitsuniqueglobaladdressandallthenodesarepeers,inhierarchicalprotocolsnodesaregroupedintoclusters.Everyclusterhasaclusterheadtheelectionofwhichisbasedondifferentelectionalgorithms.Theclusterheadsareusedforhigherlevelcommunication,reducingthetrafficoverhead.Clusteringmaybeextendedtomorethanjusttwolevelshavingthesameconceptsofcommunicationineverylevel.Theuseofroutinghierarchyhasalotofadvantages.Itreducesthesizeofroutingtablesprovidingbetterscalability.

1)Low-EnergyAdaptiveClusteringHierarchy(LEACH):TheLEACHprotocolisahierarchicalprotocolinwhichmostnodestransmittoclusterheads[57],[58].

TheoperationoftheLEACHprotocolconsistsoftwophases:

•TheSetupPhase.IntheSetupPhase,theclustersareorganizedandtheclusterheadsareselected.Theclusterheadsaggregate,compressandforwardthedatatothebasestation.Eachnodedetermineswhetheritwillbe-comeaclusterhead,inthisround,byusingastochasticalgorithmateachround.Ifanodebecomesaclusterheadforonetime,itcannotbecomeclusterheadagainforProunds,wherePisthedesiredpercentageofclusterheads.Thereafter,theprobabilityofanodetobecomeaclusterheadineachroundis1/P.Thisrotationofclusterheadsleadstoabalancedenergyconsumptiontoallthenodesandhencetoalongerlifetimeofthenetwork.•TheSteadyStatePhase.IntheSteadyStatePhase,thedataissenttothebasestation.Thedurationofthesteadystatephaseislongerthanthedurationofthesetupphase

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

15

TABLEII

FLATROUTINGSCHEMESCOMPARISON

Advantages

Scheme

Iteliminatesloopingsituationsandprovidesfasterroute

convergencewhenalinkfailureoccurs.

PeriodictopologyupdatesaresentlessfrequentlythanotherprotocolsofthiscategoryItminimizesthe

communicationoverhead,supportsmultipleroutesandmulticast

Itavoidstheimplosionproblemandenquireverylittleornostructuretooperate

Itisasimpleandrobusttechnique

Itisabletohandlenodefailuregracefully,degradingits

deliveryratelinearlywiththenumberoffailednodesItminimizestheenergy

consumptionandresultstothebalanceoftheenergyconsumptionofnodes

Itproduceslowroutingtraffic

Itisnotsuitableforhighlydynamicandalsoforaverylargewirelessnetwork.

Itisnotsuitablefornetworkswithlowmobility

Itdoesnotincorporatemulticastintoitsbasicoperation

IttakeslongtopropagatethemessagetoallsensornodesinthenetworkItmaybroadcast

duplicatedmessagesaretothesamenode

Itmaydeliverduplicatedmessagestothesamenode

Itdoesnotincorporatemulticastintoitsbasicoperation

Itexperiencesexcessivedelays

Limited

Limited

Drawbacks

Scalability

Mobility

RouteMetricShortestPathShortestPathShortestPathRandomShortestPathShortestPathThebestrouteThebestroute

PeriodicMessageTypeTableexchangeHellomessagesIMEPControlNoneNoneHellomessagesIMEPControlHellomessages

RobustLow

WRP

LimitedGood

GoodGood

GoodLow

TBRPF

TORA

GoodLimitedGood

GoodLowLow

GoodGoodGood

GossipingFlooding

RR

GoodGoodLow

E-TORAZRP

LimitedGoodGood

inordertominimizeoverhead.Moreover,eachnodethatisnotaclusterheadselectstheclosestclusterheadandjoinsthatcluster.Afterthattheclusterheadcreatesascheduleforeachnodeinitsclustertotransmititsdata.ThemainadvantageofLEACHisthatitoutperformsconventionalcommunicationprotocols,intermsofenergydissipation,easeofconfiguration,andsystemlifetime/qualityofthenetwork[59].Providingsuchalowenergy,wirelessdistributedprotocolwillhelppavethewayinaWSN.How-ever,LEACHusessingle-hoproutingwhereeachnodecantransmitdirectlytothecluster-headandthesink.Therefore,itisnotrecommendedfornetworksthataredeployedinlargeregions.Furthermore,thedynamicclusteringmayresultstoextraoverhead,e.g.headchanges,advertisementsetc.,whichmaydiminishthegaininenergyconsumption.

2)Low-EnergyAdaptiveClusteringHierarchyCentralized(LEACH-C):TheLEACH-Cutilizesthebasestationforclusterformation,unlikeLEACHwherenodesself-configurethemselvesintoclusters[60].InitiallyintheLEACH-C,theBaseStation(BS)receivesinformationregardingthelocationandenergylevelofeachnodeinthenetwork.Afterthat,usingthisinformation,theBSfindsapredeterminednumberofclusterheadsandconfiguresthenetworkintoclusters.Theclustergroupingsarechosentominimizetheenergyrequiredfornon-cluster-headnodestotransmittheirdatatotheirrespectiveclusterheads.

TheimprovementsofthisalgorithmcomparedtoLEACHarethefollowing:

•TheBSutilizesitsglobalknowledgeofthenetworktoproduceclustersthatrequirelessenergyfordatatransmission.

•UnlikeLEACHwherethenumberofclusterheadsvaries

fromroundtoroundduetothelackofglobalcoordina-tionamongnodes,inLEACH-Cthenumberofclusterheadsineachroundequalsapredeterminedoptimalvalue.

3)Power-EfficientGatheringinSensorInformationSys-tems(PEGASIS):ThePEGASISprotocolisachain-basedprotocolandanimprovementoftheLEACH[61].InPEGA-SISeachnodecommunicatesonlywithanearbyneighborinordertosendandreceivedata.Ittakesturnstransmittingtothebasestation,thusreducingtheamountofenergyspentperround.Thenodesareorganizedinsuchawayastoformachain,whichcaneitherbeaccomplishedbythesensornodesthemselves,usingagreedyalgorithmstartingfromsomenode,ortheBScancomputethischainandbroadcastittoallthesensornodes.

In[61]asimulationisperformedinanetworkthathas100-randomlocatednodes.TheBSisplacedataremotedistancefromalltheothernodes.Thus,fora50mx50mplot,theBSislocatedat(25,150)sothattheBSisatleast100mfarawayfromtheclosestsensornode.Inordertoconstructthechain,itisassumedthatallnodeshaveglobalknowledgeofthenetworkandthatagreedyalgorithmisemployed.Thus,theconstructionofthechainwillstartfromthefarawaynodetotheclosernode.Ifanodedies,thechainisreconstructedinthesamemannertobypassthedeadnode.

Ingeneral,thePEGASISprotocolpresentstwiceormoreperformanceincomparisonwiththeLEACHprotocol[62],[63].However,thePEGASISprotocolcausestheredundantdatatransmissionsinceoneofthenodesonthechainhasbeenselected.UnlikeLEACH,thetransmittingdistanceformostofthenodesisreducedinPEGASIS.ExperimentalresultsshowthatPEGASISprovidesimprovementbyfactor2

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

16

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

comparedtoLEACHprotocolfor50mx50mnetworkandimprovementbyfactor3for100mx100mnetwork.ThePEGASISprotocol,however,hasacriticalproblemthatistheredundanttransmissionofthedata.Thecauseofthisproblemisthatthereisnoconsiderationofthebasestation’slocationabouttheenergyofnodeswhenoneofnodesisselectedastheheadnode.

4)ThresholdsensitiveEnergyEfficientsensorNetworkpro-tocol(TEEN):TheTEENisahierarchicalprotocoldesignedfortheconditionslikesuddenchangesinthesensedattributessuchastemperature[64].Theresponsivenessisimportantfortime-criticalapplications,inwhichthenetworkisoperatedinareactivemode.ThesensornetworkarchitectureinTEENisbasedonahierarchicalgroupingwhereclosernodesformclustersandthisprocessgoesonthesecondleveluntilthesinkisreached.

Inthisschemethecluster-headbroadcaststoitsmemberstheHardThreshold(HT)andtheSoftThreshold(ST).TheHTisathresholdvalueforthesensedattribute.Itistheabsolutevalueoftheattributebeyondwhich,thenodesensingthisvaluemustswitchonitstransmitterandreporttoitsclusterhead.TheSTisasmallchangeinthevalueofthesensedattributewhichtriggersthenodetoswitchonitstransmitterandtransmit.Thenodessensetheirenvironmentcontinuously.Thefirsttimeaparameterfromtheattributesetreachesitshardthresholdvalue,thenodeswitchesonitstransmitterandsendsthesenseddata.Thesensedvalueisstoredinaninternalvariableinthenode,calledthesensedvalue(SV).

ThemainadvantageofTEENisthatitworkswellintheconditionslikesuddenchangesinthesensedattributessuchastemperature.Ontheotherhand,inlargeareanetworksandwhenthenumberoflayersinthehierarchyissmall,TEENtendstoconsumealotofenergy,becauseoflongdistancetransmissions.Moreover,whenthenumberoflayersincreases,thetransmissionsbecomeshorterandoverheadinthesetupphaseaswellastheoperationofthenetworkexist.

5)AdaptiveThresholdsensitiveEnergyEfficientsensorNetwork(APTEEN):TheAPTEENisanimprovementofTEENandaimsatbothcapturingperiodicdatacollectionsandreactingtotime-criticalevents[65].Assoonasthebasestationformstheclusters,theclusterheadsbroadcasttheattributes,thethresholdvaluesandthetransmissionscheduletoallnodes.Afterthattheclusterheadsperformdataaggregation,whichhasasaresulttosaveenergy.

ThemainadvantageofAPTEEN,comparedtoTEEN,isthatnodesconsumeleesenergy.However,themaindrawbacksofAPTEENarethecomplexityandthatitresultsinlongerdelaytimes.

6)VirtualGridArchitectureRouting(VGA):TheVGAcombinesdataaggregationandin-networkprocessingtoachieveenergyefficiencyandmaximizationofnetworklife-time[66].Theoverallschemecanbedividedintotwophases,clusteringandroutingofaggregateddata.Intheclusteringphase,sensorsarearrangedinafixedtopologyasmostoftheapplicationsrequirestationarysensors.Insideeachclusteracluster-head,knownaslocalaggregator,performsaggregation.AsubsetofthisLocalAggregators(LA)isselectedtoperformglobalorin-clusteraggregationanditsmembersareknownasmasteraggregator(MA).Inthedataaggregationphase,

Fig.6.OnesourceBandonesinkS(redrawnfrom[67]).

someheuristicareproposedwhichmaygivesimple,efficientandnearoptimalsolution.AnexampleofaheuristicisthatLAnodesformgroupswhichmaybeoverlapping.Thus,thereadingofmembersinagroupcanbecorrelated.

Themainadvantageofthisprotocolisthatitmayachieveenergyefficiencyandmaximizationofnetworklifetime,buttheproblemofoptimalselectionoflocalaggregatorsasmasteraggregatorsisNP-hardproblem.

7)Two-TierDataDissemination(TTDD):TheTTDDas-sumesthatthesensornodesarestationaryandlocationawareandsinksareallowedtochangetheirlocationdynamically[67].Atthetimethataneventissensedbynearbysensors,oneofthembecomesthesourcethatwillgeneratedatareports.Afterthatthevirtualgridstructureisbuilt,initiatedbysourcenodeandchoosesitselfasastartcrossingpointofagrid.Itsendsadataannouncementmessagetoitsfourdifferentadjacentcrossingpointsusinggreedygeographicalforwarding.Themessageonlystopsonceitreachestoanodethatisclosesttothecrossingpoint.Thisprocesscontinuesuntilthemessagereachesboundaryofthenetwork.

Infigure6,anexampleispresentedfortheconstructionofthegrid.Inthiscase,onesourceBandonesinkSandatwo-dimensionalsensorfieldareconsidered.ThesourceBdividesthefieldintoagridofcells.Eachcellisanxsquare.Asourceitselfisatonecrossingpointofthegrid.Itpropagatesdataannouncementstoreachallothercrossings.

TheTTDDcanbeusedformultiplemobilesinksinafieldofstationarysensornodes.Themaindrawbackisthateachsourcenodebuildsavirtualgridstructureofdisseminationpointstosupplydatatomobilesinks.

8)Base-StationControlledDynamicClusteringProtocol(BCDCP):TheBCDCPsetsupclustersbasedonthemainideathattheywillbebalanced[68].Inordertoachievethis,thebasestation,beforeconstructingtheroutingpath,receivesinformationonthecurrentenergystatusfromallthenodesinthenetwork.Basedonthisfeedback,thebasestationfirstcomputestheaverageenergylevelofallthenodes.Thenthebasestationchoosesasetofnodeswhoseenergylevelsareabovetheaveragevalue.

Inadditiontotheabove,ateachcluster,theheadclustersareserveanapproximatelyequalnumberofmembernodesbetweeneachothersinordertoachievethefollowing:•avoidclusterplacementheadoverload,

•uniformofclusterheadsthroughoutthewholesensorfieldand

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

17

Source NodeCluster HeadCooperative NodeNodeSinkFig.7.MultihopvirtualMIMOprotocol(redrawnfrom[69]).

•

utilizeaclusterhead-to-clusterhead(CH-to-CH)routingtotransferthedatatothebasestation.

Also,intheBCDCPthebasestationisconsideredtobeahigh-energynodewithalargeamountofenergysupply.9)MultihopVirtualMultipleInputMultipleOutput(MIMO):IntheMultihopVirtualMIMOthedataarecollectedbymultiplesourcenodesandtransmittedtoaremotesinkbymultiplehops[69].Thesensornodesareorganizedintoclusters(figure7).Theclusterheadbroadcaststhedatatotheclusternodesthatbelongtothespecificcluster.AnAdditiveWhiteGaussianNoisechannel(achannelmodelinwhichtheonlyimpairmenttocommunicationisalinearadditionofwidebandorwhitenoisewithaconstantspectraldensityexpressedaswattsperhertzofbandwidthandaGaussiandistributionofamplitude)withasquaredpowerpathlossisassumedinsuchatransmissionduetotheshortintraclustertransmissionrange.Next,theclusternodesencodeandtrans-mitthedatatotheclusterheadinthenexthopaccordingtotheorthogonalSpace-TimeBlockCode(STBC).

Inordertoimprovetheenergysavingperformance,theMultihopVirtualMIMOpresentsthattheaverageattenuationofthechannelbetweeneachclusternodeandclusterheadcanbeestimatedduringtheformationoftheclusters,soitusesanequalSignaltoNoiseRatio(SNR)policytoallocatethetransmitpowerduetoitsspectralefficiencyandsimplicity.10)HierarchicalPowerAwareRouting(HPAR):TheHPARisapowerawareroutingprotocolthatdividesthenetworkintoagroupofsensorscalledzones[70].Eachzoneisagroupofgeographicallyclosesensornodesandistreatedasanentity.Thusthefirststepofthisprotocolistoformattheclusteredzones.Thenextstepisthefunctionofroutingschemetodecidehowamessageisroutedacrossotherzoneshierarchicallysothatbatterylifeofnodesinthesystemismaximized.Thiscanbedonebyamessagethatisroutedalongapathwithamaximumpoweroverallminimumremainingpowers.Thispathiscalledmax-minpath.Themainideaofmakingsuchadecisionisthatitmaybepossiblethatapathwithhighresidualpowerhasmoreenergyconsumptionthantheminimumenergyconsumptionpath.Thisschemepresents

BSABCDEFFig.8.

Athree-levelclusterhierarchy(redrawnfrom[71]).

anapproximationalgorithmcalledmax-minZPminalgorithm.ThealgorithmfirstfindsapathwithleastpowerconsumptionbyapplyingDijkstraalgorithm.Itthenfindsasecondpaththatmaximizestheminimalresidualpowerinthenetwork.Theprotocolthentriestooptimizebothsolutioncriteria.Themainadvantageofthisprotocolisthatittakesintoconsiderationboththetransmissionpowerandtheminimumbatterypowerofthenodeinthepath.Inaddition,itmakesuseofzonestotakecareofthelargenumberofsensornodes.Ontheotherhand,thediscoveryofthepowerestimationmayconsultontheoverheadtothenetwork.

11)Sleep/WakeSchedulingProtocol:Thesleep/wakeschedulingprotocolconservesenergyasitputstheradiotosleepduringidletimesandwakeituprightbeforemes-sagetransmission/reception[71].Theimportantpartforasleep/wakeprotocolisthesynchronizationbetweenthesenderandthereceiver,sothattheycanwakeupsimultaneouslytocommunicatewitheachother.Theexistingsynchronizationschemesachieveprecisesynchronizationimmediatelyaftertheexchangeofsynchronizationmessages,althoughthereisstillrandomsynchronizationerrorbecauseofthenon-deterministicfactorsinthesystem.Theseerrorshaveasconsequencetheclockdisagreementtogrowwithtimeandbecomparabletotheactualmessagetransmissiontime.Thus,in[71]anoptimalsleep/wakeschedulingalgorithmisproposed.Itachievesamessagecaptureprobabilitythresholdwithminimumenergyconsumption.Moreover,multi-hopcommunicationisconsid-ered.

Thesleep/wakeschedulingprotocolisorganizedintoclusterhierarchyandeachclusterconsistsofasingleclusterheadandmultipleclustermembers.Themostimportantissue,inthisprotocol,isthataclustermembercanalsobeaclusterheadinonecluster.Infigure8,CistheclusterheadofE,butitisalsoamemberofA.ThemembernodesaresynchronizedinthesynchronizationintervalandinthetransmissionintervaleachmembernodetransmitsinaTDMAmannerandsendsonemessagetotheclusterheadseveryTseconds.

12)GridBasedDataDissemination(GBDD):InGBDDthesizeofthecellisdeterminedbydualradiorangeofasensornode[72].UnlikeTTDD,wherethesourceinitiatesgridconstruction,inGBDDthesinkthatfirstwasinterestedinsendingorreceivingdatastartsthegridconstructionprocess.Thisnodeissetasthecrossingpoint(CP)ofthegridanditsgeographicalcoordinates(x,y)becomethestartingpointfortheformationofgridcells.TheRHandRLarethetransmis-

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

18

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

sionrangesofeverysensornodewhileworkinginhighpowerradiomodeandlowpowerradiomoderespectively.Thecellofthegridisasquareandeachsideisofsizea.

13)ExtendingLifetimeofClusterHead(ELCH):InELCHthesensorsvotefortheirneighborsinordertoelectsuitableclusterheads[73].Thisprotocolachievestoconsumelowenergyandthusextendingthelifeofthenetworkutilizingahybridprotocol,whichcombinestheclusterarchitecture,withmulti-hoprouting.Thisprotocolpresentstwophases:

•SetupPhase.Inthisphase,theclusterformationandthecluster-headselectionareperformed.Thenodesvotetheirneighborsensors.Themostvotedsensorbecomesthecluster-head.

•Steady-StatePhase.Inthisphase,thecreationofclusters,theforwardingtotheheadandforwardingtothesinkareperformed.Theclustersareformedinawaythattheyconsistofonecluster-headandsomesensors.Thesesensorshavebeenchosenbasedontheirlocation.Thismeansthatthesensorslocatedinaradiuslessthantheradioradiusareselected.Then,thetimeslotTDMAforeachclustermemberineachroundisused.Inaddition,eachcluster-headmaintainsatablewithmaximumpowerforeachnodeateachselectionround.Assoonastheabovearecompletedthedatatransmissioncanstart.Assoonastheclustershavebeenorganized,theclusterheadscanformamulti-hoproutingbackbone.Thedataareforwardeddirectlytotheclusterheadbyeachnode.Moreover,forthecommunicationbetweentheclusterheadsandthesink,amultihoproutingisadopted.Thistechniquecanminimizethetransmissionenergyandthenetworkcanbemorebalancedintermsofenergyefficiency.

14)NovelHierarchicalRoutingProtocolAlgorithm(NHRPA):TheNHRPAalgorithmcanadoptthesuitableroutingtechnologyforthenodesthatisrelativetothedistanceofnodestothebasestation,thedensityofnodesdistributionandtheresidualenergyofnodes[74].Aglanceatthecomputationcostindicatesthattheproposedroutingalgorithmindealingnodesmainlyrequiresloopoperations,judgmentoperations,andassignmentoperations.Moreover,theinitializationprocessofthenodeisperformedonceduringtheperiodofdeployingsensornetworks.Byselectingsuitablethresholdvalue,heNHRPAcanbalancevaryingconcernsamongdifferentdemandsituations,suchassecurityandenergyconcerns.

15)ScalingHierarchicalPowerEfficientRouting(SH-PER):heSHPERprotocolsupposesthecoexistenceofabasestationandasetofhomogeneoussensornodes[75].Thesenodesarerandomlydistributedwithinadelimitedareaofinterest.Thebasestationislocatedalongdistanceawayfromthesensorfield.Boththebasestationandthesetofthesensornodesaresupposedtobestationary.Alsothebasestationisabletotransmitwithhighenoughpowertoallthenetworknodes,duetoitsunlimitedpowersupply.

TheoperationofSHPERprotocolconsistsoftwophases:initializationandsteadystatephase.InthefirstphasethebasestationbroadcastsaTDMAscheduleandrequeststhenodestoadvertisethemselves.Thenodestransmittheiradvertisementsandtherelativedistancesamongthemareidentified.Afterthatthebasestationrandomlyelectsapredefinednumberofhigh

andlowlevelclusterheadsandbroadcaststheIDsofthenewclusterheadsandthevaluesofthethresholds.Inthesteadystatephasetheclusterheaddefinesthemostlyenergyefficientpathtorouteitsmessagestothebasestation.

Themainadvantageofthisprotocolisthatitperformstheclusterleadershipbytakingintoaccounttheresidualenergyofnodesandenergybalanceisachievedandthepowerdepletionamongthenodesisperformedinamoreevenway.Moreover,thedataroutingisbasedonarouteselectionpolicywhichtakesintoconsiderationboththeenergyreservesofthenodesandthecommunicationcostassociatedwiththepotentialpaths.However,itdoesnotsupportthemobilityofthenodes.16)Distributedhierarchicalagglomerativeclustering(DHAC):ThemainideaintheDHACisthatanodeneedstheknowledgeofonlyonehopneighbortobuildtheclusters[76].ThestepsintheDHACtoformclustersarethefollowing:

•

Obtaininputdatasetandbuildresemblancematrix.InthisstepeachnodeelectsitselfasaclusterheadandexchangestheinformationviaHELLOmessagestoitsneighbors.

•

ExecutetheDHACalgorithm.Inthisphaseeachclusterestablishesitsownlocalresemblancematrixandtheminimumcoefficientcanbeeasilyfound.Inaddition,eachclusterthendeterminesitsminimumclusterhead.•

Cutthehierarchicalclustertree.Incasethatapredefinedupperboundsizeofclustersisreached,thecontrolcon-ditionscorrespondtothestepofcuttingthehierarchicalclustertree.

•

Controltheminimumclustersize.ThenextistogeneratetheclustersbyrunningDHAC,theminimumclustersizecanalsobeusedtolimitthelowerboundofclustersizebyperformingtheprocedure”MERGECLUSTERS”.•

ChooseCHs.TochoosetheCHs,theDHACchoosetheloweridnodebetweenthetwonodesthatjointheclusteratthefirststep.TheCHchosendoesnotrequireextraprocessing.

Following,theDHACusesthesequenceofnodesmergingintothecurrentclusterastheschedule.EachclustermembergetsitsassignedroleandstartstosenddatatoCHinturns.Moreover,therearealsoothershierarchicalprotocolsapartfromtheabovethathavebeenproposedforWSNs[77],[78],[79],[80],[81].

InTableIII,HierarchicalRoutingSchemesComparisonispresented.Thus,forexampleprotocols:LEACH,LEACH-C,PEGASIS,TEEN,APTEEN,VGA,MIMO,Sleep/Wake,GBDD,NHRPA,SHPERandDHACaremorerobustthantheothersofthiscategory.Moreover,protocolsPEGASIS,VGA,GBDD,ELCHandTTDDusethegreedyroutepolicyselectingnodesinordertoachievetheenergyefficiencyofthenodes.Inadditiontothis,LEACH,LEACH-C,PEGA-SIS,TEEN,APTEEN,VGA,MIMO,Sleep/Wake,GBDD,NHRPA,SHPERandDHACaremorescalablethantheotherprotocolsofthisscheme.

Finally,inHierarchicalProtocolsafewprotocolscanpar-tiallybeincluded,thataremainlyclassifiedanddescribedindetailsinthecategoriesonthebelow.Theseprotocolsare:GEM,HMRPandCBMPR.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

19

C.ComparisonofFlatandHierarchicalProtocols

Thesimulationresultsin[41]showthatWRPprovidesabout50percentimprovementintheconvergencecomparedtotheBellman-Ford.Aprotocolthatreducesitscomplexity,comparedtoWRP,isTORA.InTORA,thefirstnodeatthenetworkrunsoutofpowerat205secandallthenodesatthenetworkdieat800sec.Thesimulationresultsin[82]showthatTORAwasfoundtohaveaworsedeliveryratioandbetterdelay,rangingfrom0,0025to0,00125seconds,comparedtoWRP.

However,E-TORAcomparedtoTORAcanbalanceeffec-tivelyenergyconsumptionofeachnodeandincreaseevidentlythelifetimeofthenetwork[51].Moreover,thefirstnodeatthenetworkrunsoutofpowerat210sec.

Ontheotherhand,thesimulationresultsin[48]showthatFloodinghasadeliveryratioupto100percentandthedelayvariesfrom100msto180ms.However,theTBRPFachievesuptoa98percentreductionincommunicationcostina20-nodenetworkandtheZRPcanreduceupto95percentthecontrolpacketscomparedtoFlooding.

Oneofthemostpopularprotocol,thegossip,requiresverylittleornostructuretooperate[47].Thismakesitparticu-larlyappealingtoapplyindynamicsystems,wheretopologychangesarecommon.Therefore,itseemsparticularlywellfittooperateinwirelessself-organizingnetworks.

Anotherprotocol,theRRdelivers98.1percentofallqueries,withanaveragecostof92cumulativehopsperqueryorabout1/40ofanetworkfloodandcanachievesignificantsavingsovereventflooding[50].Ifthenumberofqueriespereventislessthanten,asmallersetupcostisbetterthanasmallerper-querydeliverycost.Ontheotherhand,ifweneedtodelivermorequeriesforexample40,alargerinvestmentinpathbuildingyieldswillprovidebetterresults.Thedeliveryisguaranteed,asundeliveredqueriesareflooded.

Aprotocolthatisreallypopular,theLEACH,canreducethetotalnumberoftransmissions,comparedtothatofdirectcommunication.Moreover,thefirstnodeatthenetworkrunsoutofpowerat230secandallthenodesatthenetworkdieat700sec.However,LEACH-CoutperformsLEACHintermsofenergyefficiency.Thefirstnodeatthenetworkrunsoutofpowerat525secandallthenodesatthenetworkdieat600sec.Moreover,thePEGASISperformsbetterthanLEACHbyabout100percentto300percentwhen1percent,20percent,50percentand100percentofnodesdiefordifferentnetworksizesandtopologies[62],[63].

Also,TEENoutperformsLEACHandLEACH-Cintermsofenergyefficiency[64].Thefirstnodeatthenetworkrunsoutofpowerat600secandallthenodesatthenetworkaredeadat2000sec.AlsotheperformanceofAPTEENliesbetweenTEENandLEACHwithrespecttoenergyconsump-tionandlongevityofthenetwork[65].TEENonlytransmitstime-criticaldatawhilesensingtheenvironmentcontinuously.ToovercomethedrawbacksofTEEN,theAPTEENhasaperiodicdatatransmission.

Inaddition,theBCDCPhasamoredesirableenergyexpen-diturecurvethanthoseofLEACH,LEACH-CandPEGASIS[68].AlsoBCDCPreducesoverallenergyconsumptionandimprovesnetworklifetimecomparedtoLEACH,LEACH-CandPEGAGSIS.Moreover,thefirstnodeatthenetworkruns

outofpowerat820secandallthenodesatthenetworkaredeadat900sec.

TheSHPERoutperformsTEENconcerningthemeanen-ergyconsumptionby9.88percent(thedistancebetweenthebasestationandthenodeis100m),18.77percent(thedistancebetweenthebasestationandthenodeis200m),26.23percent(thedistancebetweenthebasestationandthenodeis300m)[75].

AlsoTTDDincreasestheenergygraduallybutsublinearlyasthenumberofsinksincreasesandforaspecificnumberofsinks(e.g.,4sinks),energyconsumptionincreasesalmostlinearlyasthenumberofsourcesincreases[67].Moreover,thedelayrangesfrom20msecto80msecandthedeliveryratiocanbeupto90percent.TheTTDDiscomparedtoDirectedDiffusionandtheresultsshowthatTTDDscalesbetterthanDirectedDiffusiontothenumberofsources.Ifthereare1or2sources,DirectedDiffusionuseslessenergy,butiftherearemorethan2sources,TTDDconsumesmuchlessenergy.However,theGBDDhas43percentoverallenergysavingscomparedtoTTDD.Moreover,GBDDshows30percentimprovementcomparedtoTTDDinaveragedelaycomputedacrossallsource-sinkpairsforadatapackettoreachthedestination.

Moreover,twoprotocols,comparedtoLEACH,aretheMIMOandtheELCH.TheMIMO,outperformsLEACHintermsofenergyconsumption.Thefirstnodeatthenetworkrunsoutofpowerat700sec[69].TheELCHoutperformsLEACHintermsofenergyefficiencyandthefirstnodeatthenetworkrunsoutofpowerat270sec[73].

TheNHRPAoutperformsTEENandDirectDiffusionintermsofpacketlatencyandaverageenergyconsumption[74].Morespecifically,theaverageenergyconsumptioninLEACHvariesfrom3.884mJ(with1percentclusterhead)to0.904mJ(with20percentclusterhead)comparedtoNHRPA,itvariesfrom0.949mJto0.524mJ.

TheHPARperformsbetterthan80percentofoptimalfor92percentoftheexperimentsandperformswithinmorethan90percentoftheoptimalfor53percentoftheexperimentsandthesleep/wakecanachieveatleast0.73oftheoptimalperformance[70].

TheDHACoutperformsLEACHandLEACH-Cintermsofenergyconsumption.Moreover,thefirstnodeatthenetworkrunsoutofpowerat600secandallthenodesatthenetworkaredeadat1100sec.Whilethesinkmovesfurther,thenetworklifetimeofLEACH-CdecreasesveryquicklycomparedtoDHAC.AlsoDHACgainsmuchbetterperformancewhenthenetworkhaslighttraffic[76].

VII.COMMUNICATIONMODELSCHEME

A.Query-BasedRoutingProtocols

InQuery-basedroutingprotocols,thedestinationnodespropagateaqueryfordata(sensingtask)fromanodethroughthenetworkandanodehavingthisdatasendsthedatawhichmatchesthequerybacktothenode,whichinitiatesthequery[83].Thesequeriesareusuallydescribedinnaturallanguage,orinhigh-levelquerylanguages.Forexample,clientC1maysubmitaquerytonodeN1andask:Aretheremovingvehiclesinbattlespaceregion1?Allthenodeshavetablesconsistingof

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

20

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

TABLEIII

HIERARCHICALROUTINGSCHEMESCOMPARISON

Advantages

Scheme

Lowenergy,ad-hoc,distributedprotocol

LEACH

TheenergyfordatatransmissionislessthanLEACH

Thetransmittingdistanceformostofthenodeisreduced

Itisnotapplicableto

networksdeployedinlargeregionsandthedynamicclusteringbringsextraoverheadOverhead

Thereisnoconsiderationofthebasestation’s

locationabouttheenergyofnodeswhenoneofthenodesisselectedastheheadnode

Alotofenergy

consumptionandoverheadincaseoflargenetworkLongdelay

TheproblemofoptimalselectionoflocalaggregatorsasmasteraggregatorsisNP-hardproblem

ThesourcenodebuildsavirtualgridstructureofdisseminationpointstosupplydatatomobilesinksTheperformancegaindecreasesasthesensorfieldareabecomessmallItmayresultsinsuboptimalsystemperformances

Good

FixedBS

Drawbacks

Scalability

Mobility

RouteMetricShortestPath

PeriodicMessageType

NoneGood

Robust

GoodGood

FixedBSFixedBS

LEACH-C

ThebestrouteGreedrouteselection

NoneNone

GoodGood

PEGASIS

TEENAPTEEN

Itworkswellintheconditionslikesuddenchangesinthesensedattributessuchastemperature

LowenergyconsumptionItmayachieveenergy

efficiencyandmaximizationofnetworklifetimeItcanbeusedformultiplemobilesinksinafieldofstationarysensornodesLowenergyconsumption

GoodFixedBS

ThebestrouteThebestroute

Greedyrouteselection

NoneLimited

GoodGood

FixedBSNoIMEPControlNone

GoodGood

VGA

LowNo

TTDD

GreedyrouteselectionThebestrouteThedatabitscollectedbymultiplesourcenodeswillbetransmittedtoaremotesinkbymultiplehops

ItinitiallyselectstheshortestpathandthentriestooptimizeitbasedonthetotalenergyconsumptionThebestrouteIfvalidgridispresent,sink

discoversclosest

cornernodeItselectsthenodewith

maximumremainingpowerThebestrouteThebestrouteThebestroute

NoneGood

LimitedGood

NoNo

NoneNone

LimitedLimited

BCDCP

TheenergysavingandQoSprovisioning

MIMO

HPAR

Ittakesintoconsiderationboththetransmissionpowerandtheminimumbattery

powerofthenodeinthepath.Inaddition,itmakesuseofzonestotakecareofthelargenumberofsensornodesItidentifiesthebottleneckandsignificantlyextendsthenetworklifetimeItensurecontinuousdatadeliveryfromsourcenodestosink

Thediscoveryofthepowerestimationmayresultontheoverheadtothenetwork

LowNoNoneGood

Sleep/Wake

GBDD

Synchronizationand

schedulingwillbothaffecttheoverallsystemperformance

Itconsumesmoreenergywhenthespeedisveryhigh

GoodNoNoneLimited

GoodLimitedNoneGood

ELCH

Itcanminimizethe

transmissionenergyandthenetworkcanbemorebalancedintermsofenergyefficiencyLowenergyconsumptionEnergybalanceofthenetworkThelongernetworklifetime

NHRPASHPERDHAC

Ifthenumberofthe

membersofeachclusterintheenvironmentexceedsfromacertainamountitwillhaveanegativeeffectonthenetworkoperationpacketlatency

Itdoesnotsupportmobility

Theperformanceisworseasthenetworktrafficisgettinghigh

LimitedFixedBSNoneGood

GoodGoodGood

FixedBSFixedBSNo

NoneNoneHellomessages

GoodGoodLimited

thesensingtasksqueriesthattheyreceiveandsenddatawhichmatchesthesetaskswhentheyreceiveit.Directeddiffusionisanexampleofthistypeofrouting.Indirecteddiffusion,theBS(BaseStation)nodesendsoutinterestmessagestosensors.Astheinterestispropagatedthroughoutthesensornetwork,thegradientsfromthesourcebacktotheBSareset

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

21

EventEventSourceSourceSinkSinkEventSourceSinkFig.9.a)Interestpropagation,b)Initialgradientssetup,c)Datadeliveryalongreinforcedpath(redrawnfrom[84]).

up.Whenthesourcehasdatafortheinterest,thesourcesendsthedataalongtheinterests’gradientpath.Tolowerenergyconsumption,dataaggregation(e.g.,duplicatesuppression)isperformedenroute.

1)DirectedDiffusion(DD):InDirectDiffusionallnodesareapplication-aware[84].TheDDcanselectempiricallygoodpathsandusethetechniquesofcachingandprocessingdatain-networkinordertoachievetheminimizationofenergyconsumption.TheDDconsistsofseveralelements[84],figure9:

•Naming.Thetaskdescriptionsarenamedusingalistofattribute-valuepairs.Theseattributesmaybethetypeofdata,theintervaloftransmissiondata,thedurationetc.•InterestsandGradients.Thetaskdescriptionspecifiesaninterestfordatamatchingtheattributes.Thesedata,sentasaresponsetointerests,arenamedusingasimilarnamingscheme.Thegradientsaresetupwithinthenetworkandaredesignedtodraw”events”,forexampledatathatmatchtheinterestrequirements.Everynodeinthenetworkmaintainsaninterestcache.Eachiteminthecachecorrespondstoadistinctinterest.Also,theinterestentrycontainsseveralgradientfieldsuptooneperneighbor.

•DataPropagation.Incasethatasensornodedetectsatarget,itsearchesforitsinterestcacheforamatchinginterestentry.Thus,ifitfindsone,itcomputesthehighestrequestedeventrateamongallitsoutgoinggradients.•Reinforcement.Eventsstartflowingtowardstheorigina-torsofinterestsalongmultiplepaths.Thesensornetworkreinforcesone,orasmallnumberofthesepaths.

Theevaluationandtheperformanceresultsin[84]showthatdirecteddiffusionhasthepotentialforsignificantreductionofenergyefficiencyforthesensornodesandtheextensionofthenetworklifetime.Evenwithrelativelyunoptimizedpathselection,itoutperformsanidealizedtraditionaldatadisseminationschemelikeomniscientmulticast.Moreover,thediffusionmechanismsarestable.

2)COUGARapproach:TheCOUGARviewsthenetworkasahugedistributeddatabasesystem[85].Thekeyideaistousedeclarativequeriesinordertoabstractqueryprocessingfromthenetworklayerfunctionssuchasselectionofrele-vantsensorsandsoon.COUGARutilizesin-networkdata

aggregationtoobtainmoreenergysavings.Theabstractionissupportedthroughanadditionalquerylayer.Thisliesbetweenthenetworkandapplicationlayers.COUGARincorporatesarchitectureforthesensordatabasesystemwheresensornodesselectaleadernodetoperformaggregationandtransmitthedatatotheBS.TheBSisresponsibleforgeneratingaqueryplan,whichspecifiesthenecessaryinformationaboutthedataflowandin-networkcomputationfortheincomingqueryandsendittotherelevantnodes.Thequeryplanalsodescribeshowtoselectaleaderforthequery.Thearchitectureprovidesin-networkcomputationabilitythatcanprovideenergyefficiencyinsituationswhenthegenerateddataishuge[86].COUGARprovidesnetwork-layerindependentmethodsfordataquery.

ThemainadvantageoftheCOUGARisthatitprovidesenergyefficiencywhengenerateddataishuge.Ontheotherhand,themaindisadvantagesoftheCOUGARaretheover-headoftheadditionalquerylayerfortheenergyconsumptionandstorage,thecomplexityofthesynchronizationinnetworkdatacomputationandthedynamicmaintenanceofleadernodestopreventfailure.

3)ACtiveQUeryforwardingInsensoRnEtworks(AC-QUIRE):TheACQUIREissimilartoCOUGAR[87].TheACQUIREviewsthenetworkasadistributeddatabasewherecomplexqueriescanbefurtherdividedintoseveralsubqueries.TheBaseStation(BS)nodesendsaquery,whichisthenforwardedbyeachnodereceivingthequery.Duringthis,eachnodetriestorespondtothequerypartiallybyusingitspre-cachedinformationandthenforwardsittoanothersensornode.Ifthepre-cachedinformationisnotup-to-date,thenodesgatherinformationfromtheirneighborswithinalook-aheadofdhops.Oncethequeryisbeingresolvedcompletely,itissentbackthrougheitherthereverseorshortest-pathtotheBS.Hence,ACQUIREcandealwithcomplexqueriesbyallowingmanynodestosendresponses.Notethatdirecteddiffusionmaynotbeusedforcomplexqueriesduetoenergyconsiderationsasdirecteddiffusionalsousesflooding-basedquerymechanismforcontinuousandaggregatequeries.TheACQUIREisidealforone-shotandcomplexqueriesforresponsewhichmaybeprovidedbymanynodes.Itprovidesefficientqueryingbyadjustingthevalueofthelook-aheadhopparameter.However,iftheparameterisequaltothenetworksize,thetrafficbehavessimilartoflooding.Ontheotherhand,thequeryhastotravelmorehopsifthesettingistoosmall.

InTableIV,theQuery-BasedRoutingSchemesComparisonispresented.Thus,protocolsDDandCOUGARselectthepathwiththelessenergyconsumption,whileACQUIREselectstheshortestpathinordertominimizetheenergyconsumption.Moreover,DDandCOUGARcansupportlimitedmobilityofthenodes.AlsoDDismorescalablethanCOUGARandACQUIRE.

Finally,inQuery-BasedProtocolsafewprotocolscanpartiallybeincluded,thataremainlyclassifiedanddescribedindetailsinthecategoriesonthebelow.Theseprotocolsare:RR,SPIN-PP,SPIN-EC,SPIN-BNandSPIN-RL.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

22

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

TABLEIV

QUERY-BASEDROUTINGSCHEMESCOMPARISON

Advantages

Scheme

Itextendsthenetworklifetime

Itprovidesenergyefficiencywhengenerateddataishuge

COUGAR

Itisidealforone-shotandcomplexqueriesforresponsewhichmaybeprovidedbymanynodes

Itcannotbeusedforcontinuousdatadeliveryorevent-drivenapplicationsOverhead,

complexityofthesynchronizationinnetworkdatacomputationFlooding

Good

Limited

Drawbacks

Scalability

Mobility

RouteMetricThebestpathThebestpath

PeriodicMessageTypeQuerymessagesQuerymessages

RobustLow

DD

LimitedNoLow

LimitedLimited

ACQUIRE

ShortestPathQuerymessages

Low

B.CoherentandNon-Coherent-BasedRoutingProtocolsInWSNstheprocessingofthedataisrequiredatthenodelevel.Thesensornodesmakeacollaborativeefforttoprocessthedatawithinthesensornetwork.Theroutingmechanismwhichinitiatesthedataprocessingmoduleisproposedin[88].Thismechanismisdividedintotwocategories:

•CoherentDataProcessing-BasedRouting:Thiscategoryisanenergyefficientmechanismwhereonlythemini-mumprocessingisdonebythesensornode.Timestamp-ing,duplicatesuppressionarethetasksaccomplishedinminimumprocessing.Aftertheminimumprocessing,thedataisforwardedtotheaggregators.

•NonCoherentDataprocessing-basedrouting[89]:Inthiscategorythesensornodeslocallyprocesstheactualdataandthensendittotheothernodesforfurtherprocessing.Thenodesthatperformfurtherprocessingarecalledtheaggregators.Therearethreephasesofdataprocessinginnon-coherentrouting.(a)Targetdetection,datacollection,andpreprocessing,(b)Membershipdec-laration,and(c)Central-nodeelection.Intargetdetectionstage,aneventisdetected;itsinformationiscollectedandpre-processed.Inthemembershipdeclarationphase,thesensornodechoosestoparticipateinacooperativefunctionanddeclarethisintentiontoallneighbors.Inthecentralnodeelectionstage,acentralnodeischosentoperformmorerefinedinformationprocessing.

1)SingleWinnerAlgorithm(SWE):IntheSWE,asingleaggregatornodeiselectedforcomplexprocessing[90].ThisnodeistheCN(CentralNode)andisselectedbasedontheenergyreservesandcomputationalcapabilityofthatnode.InordertoselecttheCNeachnodebroadcastsanelectmessageandannouncesitselfasaCNcandidate.Inresponsetothefirstbatchofelectmessages,thenodesthathavealreadyreceivedthem,willstartcomparingtheproposedCNcandidateswithitselfandrespondwithasecondbatchofelectmessagesthatcarriestheresultofthisinitialcomparison.Thesecondbatchofmessagepassingwillgeneratefurtherexchangeofmessages.Themessagethatpresentsabettercandidate,isrecordedintheregistryandthencanbeforwardedtoallneighbors,otherwisethemessageisdiscarded.

Infigure10,thecontinuingexchange,forwardinganddiscardingphaseofelectmessages,ispresentedandshow

Fig.10.SWEElectionProcess(redrawnfrom[88]).

howtheinformationofthewinningcandidatesaresentinthenetwork.Togetherwiththisdiffusionprocess,aminimum-hopspanningtreerootedatthewinningcandidatewillgraduallyincreaseuntilitcompletelycoversthenetwork.

2)MultipleWinnerAlgorithm(MWE):IntheMWE,asimpleextensiontoSWEisproposed[90].Whenallnodesaresourcesandsendtheirdatatothecentralaggregatornode,alargeamountofenergywillbeconsumed;hence,thisprocesshasahighcost.Theenergycostmaybeloweronlyiftherewillbealimittothenumberofsourcesthatcansenddatatothecentralaggregatornode.Insteadofkeepingarecordofonlythebestcandidatenode(masteraggregatornode),eachnodewillkeeparecordofuptonnodesofthosecandidates.TheMWEprocessmakeseachsensorinthenetworktohaveasetofminimum-energypathstoeachSourceNode(SN).Afterthat,SWEisusedtofindthenodethatyieldstheminimumenergyconsumption.Thisnodecanthenserveasthecentralnodeforcoherentprocessing.

InTableV,aCoherentandnon-CoherentRoutingSchemesComparisonispresented.TheprotocolSWEismorescalablethanMWE,whileMWEcomputesasetofminimum-energypathstoeachnode.

C.Negotiation-BasedRoutingProtocols

Negotiation-basedroutingprotocolsorSensorProtocolsforInformationviaNegotiation(SPIN)isamongtheearlyworkstopursueadata-centricroutingmechanism.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

23

TABLEV

COHERENTANDNON-COHERENT-BASEDROUTINGSCHEMESCOMPARISONAdvantages

SchemeSWEItbuildsaminimum-hopspanningtree

EachsensorinthenetworkItisacomplexprotocol

LongdelayandlowGoodLow

NoNo

Drawbacks

Scalability

Mobility

RouteMetricShortestPathShortestPeriodicMessageTypeHellomessagesHelloRobustLowLow

MWE

hasasetofminimum-energyscalability

pathstoeachsourcenode

Fig.11.SpinprotocolandADV,REQ,andDATApackets(redrawnfrom

[91]).

TheSPINfamilyofprotocolsrestsupontwobasicideas[91].

•First,tooperateefficientlyandtoconserveenergy,sensorapplicationsneedtocommunicatewitheachotheraboutthedatathattheyalreadyhaveandthedatatheystillneedtoobtain.

•Second,nodesinanetworkmustmonitorandadapttochangesintheirownenergyresourcestoextendtheoperatinglifetimeofthesystem.

ThemainideaofSPINistonamethedatausinghighleveldescriptorsormeta-data[92].Theyusemeta-datanegotiationstoreduceredundanttransmissionsinthenetwork.Therefore,ifanodehassomedata,then,firstofall,itwilladvertisebysendinganadvertisepacketthatithassensedaneventorreceivesadatafromanothernodeandifsomeothernodehasreceivedtheadvertisedpacketandisinterestedinthatdatathenitwillsendarequestpacketanduponreceivingtherequestpacketthenodewillsendtheactualdatainthedatapacket(figure11).SoSPINisa3-stageprotocol,ADV,REQ,andDATA.SPINprovidesscalabilityinasensethateachnodeneedstoknowonlyitssingle-hopneighbors,so,anychangesinthetopologywouldbelocal.TheproblemwithSPINisthatitdoesnotguaranteedeliveryofdata,likeconsideringasituationwhenaninterestednodeisveryfarfromtheadvertised,thenthatinterestednodewillnotgetanydataifnodesbetweenthesetwonodesarenotinterestedinthedata.SPINisbasedondata-centricrouting.

ThefollowingprotocolsbelongtoSPINfamilyofprotocols:1)SPINforPointtoPointCommunication(SPIN-PP):Thisprotocolhasbeendesignedtoperformoptimallyforpoint-to-pointcommunication[93].InSPIN-PP,twonodesmayhaveexclusivecommunicationwitheachotherwithoutanyinterferencefromtheothernodes.Thus,thecostof

Path

messages

communicationforonenodetocommunicatewithnnodesisntimesmoreexpensivethancommunicatingwithonenode.Thisprotocolisasimple3-wayhandshakeprotocolandthemaincharacteristicofitisthatenergyisnotconsideredtobeaconstraint.Whenanodehassomenewdata,itadvertisesthisnewdatausingtheADVmessagestoitsneighbors.Assoonas,aneighboringnodereceivesthisadvertisement,thisnodechecksthemeta-dataandcheckifitalreadyhasthedataitemornot.Ifitdoesnot,itsendsanREQmessagebackrequestingforthedataitem.TheoriginatingnodethatwillreceivetheREQmessagewillsendDATAmessagescontainingthemissingdatatotherequestingnode.

Theadvantagesofthisprotocolareitssimplicity,itsimplo-sionavoidanceandtheminimalstart-upcost.Thedisadvan-tagesofthisprotocolarethatitdoesnotguarantythedeliveryofthedataandthatitconsumesunnecessarypower.

2)SPINwithEnergyConservation(SPIN-EC):Inthisprotocol,thesensornodescommunicateusingthesame3-wayhandshakeprotocolasinSPIN-PPbutthereisanenergy-conservationheuristicaddedtoit[93].Ifanodereceivesanadvertisement,itwillnotsendoutanREQmessageifitdoesnothaveenoughenergytotransmitanREQmessageandreceivesthecorrespondingDATAmessage.

ThepropertiesofSPIN-ECaresummarizedasfollows[94]:

•Itaddssimpleenergy-conservationheuristictotheSPIN-PPprotocol.

•Whenenergyisabundant,SPIN-ECactsasSPIN-PPprotocol.

•Wheneverenergycomesclosetolow-energythreshold,itadaptsbyreducingitsparticipation.

•

Thenodewillonlyparticipateinthefullprotocolifitbelievesthatithasenoughenergytocompletetheprotocolwithoutreachingbelowthethresholdvalue.•

ItdoesnotpreventnodesfromreceivingmessagessuchasADVorREQbelowitslow-energythreshold,butpreventsthenodestohandleaDATAmessagebelowthethreshold.

3)SPINforBroadcastNetworks(SPIN-BC):Thisprotocolwasdesignedforbroadcastnetworksinwhichthenodesuseasinglesharedchanneltocommunicate[93].Inthisprotocol,anodesendsoutamessageandalltheothernodeswithinacertainrangeofthesenderreceiveit.Anode,whichhasreceivedanADVmessage,doesnotimmediatelyrespondwithanREQmessage,butwaitforacertaintimebeforesendingouttheREQmessage.IncasethatadifferentnodereceivestheREQmessage,itcancelsitsownrequest,inordertoavoidredundantrequestsforthesamemessage.AftertheadvertisingnodereceivesanREQmessage,itsendsthedatamessageonly

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

24

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

oncebecauseitisabroadcastnetworkeventhoughitmighthavegotmultiplerequestsforthesamemessage.

TheSPIN-BCisbetterthanSPIN-PPforbroadcastnet-worksbyusingcheap,one-to-manycommunications,meaningthatallmessagesaresenttobroadcastaddressandprocessedbyallthenodesthatarewithintransmissionrangeofthesender.

4)SPINwithReliability(SPIN-RL):ThisprotocolmakestwochangestotheaboveSPIN-BCprotocol[93].FirsteachSPIN-RLnodekeepstrackofwhichadvertisementsithearsfromwhichnodesandifitdoesnotreceivethedatawithinacertainperiodoftime,itsendsouttherequestagain.Theimportantpointofthisprotocolisthatnodeshavealimitonthefrequencywithwhichtheyresendthedatamessages.Afterhavingsentoutadatamessage,anodewillwaitforacertainperiodoftimebeforeitrespondstootherrequestsforthesamedatamessage.

TheSPIN-RLisareliableversionofSPIN-BCwhichdis-seminatesdatathroughabroadcastnetworkeveninthecasesthatanetworklosespacketsorcommunicationisasymmetric.InTableVI,Negotiation-BasedRoutingSchemesCompar-isonispresented.TheprotocolsSPIN-PP,SPIN-EC,SPIN-BCandSPIN-RLsupportmobilityofthenodes,whilealloftheseprotocolscommunicatewiththeirneighborsonlyincasethattheyhavedatatosend,minimizingtheenergyspentonperiodicmessages.Moreover,alltheprotocolsSPIN-PP,SPIN-EC,SPIN-BCandSPIN-RLarescalableandrobustandtheirperformanceisindependedofthenetworksize.

Finally,inNegotiation-BasedProtocolsafewprotocolscanpartiallybeincluded,thataremainlyclassifiedanddescribedindetailsinthecategoriesonthebelow.Theseprotocolsare:VGAandSAR.

D.ComparisonofQuery,NegotiationandCoherent,non-CoherentBasedProtocols

InDD,thefirstnodeatthenetworkrunsoutofpowerat90secandallthenodesinthenetworkaredeadat200sec.Ontheotherhand,theCOUGARhasaqueryoptimizergeneratesanefficientqueryplanforin-networkqueryprocessing,whichcanvastlyreduceresourceusageandthusextendthelifetimeofasensornetwork[85].

TheACQUIREforaverysmallamortizationfactorc0.001≤c≤0.01,theoptimallook-aheaddisashighaspossible(d=10).Ontheotherhand,for0.08≤c≤0.9,themostenergyefficientstrategyistojustrequestinformationfromtheimmediateneighbors(d=1).Theresultsalsoshowthattherearevaluesofcintherangefrom[0.001,0.1]suchthateachof1,2...10istheoptimallook-aheadvalue[87].TheMWEprocesshasalongerdelayandalowerscalabilitythanthatfornon-coherentprocessingnetworks[90].

Moreover,theSPINusesapproximatelyafactorof3.5lessenergythanFloodingandthedeliveryratioisupto95percent.TheaverageenergydissipatedinSPIN-PPandSPIN-ECis17msecand16msecaccordingly.Ontheotherhand,theaverageenergydissipatedinSPIN-BCandSPIN-RLis40msec[93].

VIII.TOPOLOGYBASEDSCHEME

A.Location-BasedRoutingProtocols

Inthissection,thebasicsoflocation-aidedorposition-basedrouting,throughmethodsproposedforWSNs,ispresented.Thistypeofprotocolsacknowledgestheinfluenceofphysicaldistancesanddistributionofnodestoareasassignificanttonetworkperformance.

Location-basedroutingprotocolsarebasedontwoprincipalassumptions:

•Itisassumedthateverynodeknowsitsownnetworkneighborspositions.

•Thesourceofamessageisassumedtobeinformedaboutthepositionofthedestination.

Thistechniqueforlocalizedbroadcastingofqueriesingeo-awaresensornetworksmakesuseoftheexistingqueryroutingtreeanddoesnotinvolvethecreationofanyadditionalcommunicationchannels.ThesealgorithmsrequirenodestoperiodicallytransmitHELLOmessagestoallowneighborstoknowtheirpositions.Thelocation-basedroutingtechniqueisveryinterestingbecauseitoperateswithoutanyroutingtables.Furthermore,oncethepositionofthedestinationisknown,alloperationsarestrictlylocal,thatis,everynodeisrequiredtokeeptrackonlyofitsdirectneighbor.

Themaindisadvantagesofsuchalgorithmsare:

•Efficiencydependsonbalancingthegeographicdistribu-tionversusoccurrenceoftraffic.

•Anydependenceofperformancewithtrafficloadthwart-ingthenegligenceofdistancemayoccurinoverload.1)DistanceRoutingEffectAlgorithmforMobility(DREAM):TheDREAMisaproactiveprotocolandeachMobileNode(MN)maintainsalocationtableforallothernodesinthenetwork[95].Tomaintainthetable,eachMNtransmitslocationpacketstonearbyMNsinthesensornetworkatagivenfrequencyandtofarawayMNsinthesensornetworkatanotherlowerfrequency.SincefarawayMNsappeartomovemoreslowlythannearbyMNs,itisnotnecessaryforaMNtomaintainup-to-datelocationinformationforfarawayMNs.Thus,bydifferentiatingbetweennearbyandfarawayMNs,DREAMattemptstolimittheoverheadoflocationpackets.

So,incasethatanodeSneedstosendamessagemtoarecipientnodeR,itreferstoitslocationtableinordertoretrieveitslocationinformation.Afterthat,SselectsfromamongitsneighborsthosenodesthatareinthedirectionofRandforwardsmtothem.Thisisrepeatedforeachofthesenodes,forwardingthemessagetothosenodesinthedirectionofRuntilRisreached.Itis,thus,crucialtoselecttheneighborsofagivennodeinacertaindirectionrangeinsuchawaythatitisguaranteedthatRcanbefoundwithagivenprobabilityp,02)GeographicandEnergyAwareRouting(GEAR):Unlikepreviousgeographicroutingprotocols,GEARdoesnotusegreedyalgorithmstoforwardthepackettothedestination[96].Thus,itdiffersinhowtheyhandlecommunicationholes.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

25

TABLEVI

NEGOTIATION-BASEDROUTINGSCHEMESCOMPARISON

Advantages

Scheme

simplicity,implosionavoidanceandtheminimalstartupcostWheneverenergycomesclosetolow-energythreshold,itadaptsbyreducingitsparticipationItisbetterthanSPIN-PPforbroadcastnetworksbyusingcheap,one-to-manycommunications

Itdisseminatesdata

throughabroadcasteveninthecasesthatanetworklosespacketsorcommunicationisasymmetric

ItdoesnotguarantythedeliveryofthedataandconsumesunnecessarypowerItdoesnotpreventnodesfromreceivingmessagessuchasADVorREQbelowitslow-energythreshold

IthastowaitforacertaintimebeforesendingouttheREQmessageTimeconsuming

Good

Yes

Drawbacks

Scalability

Mobility

RouteMetricEachnodesendsdatatoitssingle-hop

neighborsEachnodesendsdatatoitssingle-hop

neighborsEachnodesendsdatatoitssingle-hop

neighborsEachnodesendsdatatoitssingle-hop

neighbors

PeriodicMessageType

NodewithdataadvertisestoallitsneighborsNodewithdataadvertisestoallitsneighborsNodewithdataadvertisestoallitsneighborsNodewithdataadvertisestoallitsneighbors

RobustGood

SPIN-PP

GoodYesGood

SPIN-EC

GoodYesGood

SPIN-BC

GoodYesGood

SPIN-RL

TheGEARusesenergyawareandgeographicallyinformedneighborselectionheuristicstorouteapackettowardsthetargetregion.Thisprotocolusesanenergyawareneighborselectionheuristictoroutethepackettowardsthetargetregion.Twomaincharacteristicsofthisprotocolarethefollowing:•WhenacloserneighbortothedestinationexistsGEARpicksanext-hopnodeamongallneighborsthatareclosertothedestination.

•Whenallneighborsarefurtheraway,thereisahole.GEARpicksanext-hopnodethatminimizessomecostvalueofthisneighbor.

ThemainadvantageoftheGEARisthateachnodeknowsitsownlocationandremainingenergylevel,anditsneigh-borslocationsandremainingenergylevelsthroughasimpleneighborhelloprotocol.Alsoitattemptstobalanceenergyconsumptionandtherebyincreasenetworklifetime.

3)GraphEmbeddingforRouting(GEM):TheGEMisalocationbasedroutingprotocolthattriestoassignlabelstothesensornodesuniquelyinadistributedmanner[97].Thenodescanroutemessagesknowingonlythelabelsoftheirimmediateneighbors.InGEM,virtualcoordinatesareusedinsteadofactualphysicalcoordinates.

Thisalgorithmconsistsoftwocomponentsthatarethefollowing:

•TheVirtualPolarCoordinateSpace(VPCS).ThefirststeptobuildtheVPCS,istoembedaringedtree.Tobuildthespanningtree,arootnodeshouldbedefined.Afterthat,eachnodeisassignedananglerange,whichcanbeusedtoassignanglestoitssub-trees.Eachnodesplitsitsanglerangeintoitschildrenbasedonthesizeofthesub-treeofeachchild.Foreachsub-treeitscentre-of-massandaveragepositionofallthenodesarecomputedandpropagatedtotheparentofthattree.

•TheVirtualPolarCoordinateRouting(VPCR).TheVPCRroutesfromanynodetoanypointintheVPCS.Apointisdefinedbyalevelandangle.ThemainadvantageofGEMisthatitallowsmessagestobeefficientlyroutedthroughthenetwork,whileeachnodeonlyneedstoknowthelabelsofitsneighbors.Alsoitisrobusttodynamicnetworks,workswellinthefaceofvoidsandobstacles,andscaleswellwithnetworksizeanddensity.Ontheotherhand,itoverloadsnodesthatareatlowlevelsofthetree.

4)ImplicitGeographicForwarding(IGF):Inthelocation-basedprotocols,routingdependsonup-to-datelocalneigh-borhoodtables[98].Incontrast,theIGFallowsasendertodetermineapacket’snext-hoponlineinreal-time.Bycombin-inglazy-bindingandlocation-addresssemantics,IGFbecomesapurestatefreeprotocol,whichdoesnotdependontheknowledgeofthenetworktopologyorthepresence/absenceofothernodes.Thischaracteristicofbeingstate-freeisvaluabletothehighlydynamicsensornetworks,asitsupportsfaulttoleranceandmakesprotocolsrobusttoreal-timetopologyshiftsornodestatetransitions.Thus,thisprotocolcanelim-inatecostlycommunicationthatwouldotherwiseberequiredtomaintainneighbourhoodstateinformationforrouting.Inaddition,thisprotocolenhancesthedecisionmakingprocessbyincorporatingincreaseddistancetowardthedestination(IDTD)andenergyremaining(ER)metricsintotherouteselectionprocess.

ThepropertiesofIGFaresummarizedasfollows:

•Ithasrobustperformancewhennodesmigrateortransitintoandoutofsleepstates.

•Shorterend-to-endlatencycomparedtoschemesthatmustupdatesystemstatepriortosending.•Thedistanceandenergyawareforwarding.•Thedistributionoftheworkload.

•Thedecouplingofroutingfromenergyconservingpro-tocols.

In[98]asimulationofthisprotocol,regardingtheenergyconsumption,ispresented.ThescenarioofMany-to-ManyflowswheretheSleepPercentagetonodesissetat33percent

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

26

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

Sink NodeaFig.12.Datapacketdisseminationmodel(redrawnfrom[99]).

forvariedTogglePeriodsisexamined.TheIGFworkswellintermsofenergyconservationwhentheTogglePeriodisbelow18seconds.

5)ScalableEnergy-efficientLocationAidedRouting(SE-LAR):TheSELARcombinestheenergyconsumptionalongwiththelocationinformationinordertoroutepackets[99].Thefirststepofthisprotocolisthesinknodetoflooditslocationinformationtoitsneighbornodes.Afterthat,allthenodesatthenetworkfloodtheirlocationandenergyinformationtotheirneighboringnodes.Theyalsoincludethelocationofthesinknodeasareference.Afterthatinitialexchangeoftheaboveinformation,onlyenergyinformationneedstobeupdated,asthenetworkisratherstatic.

Inorderforthisprotocoltosaveenergy,thecontrolpacketstravelonehop.Inadditiontothat,datapacketsaresentbyindividualnodesthatcalculatecandidateneighbornodesintheirforwardingzone,whichzoneistheareaformedbytheangleainthedirectionofthesinknodeandtheareaofcoverageofthesendingnode(figure12).Thenodeinitiallysetstheangleaofthezonetominalpha(15)0andincreasesitinstepsuntilanumberofneighboringsensornodesarefound,itispredefined,oruntiltheanglereachesamaxvaluethatmaybeforexample(90)0,inordertomakesurethatthedatapacketisalwaysforwardedinthedirectionofthesink.Incasethatnocandidatenodeisfoundintheforwardingzone,thenSELARusesgossipinginordertodiscoveraroute,makingitmorerobust.

Themainadvantageofthisprotocolisthat,amongtheavailablecandidatenodesintheforwardingzone,itselectsthenodewiththehighestenergylevelinordertoprovideauniformdissipationofenergy.However,thisalgorithmdoesnotworkwellincaseofanetworkthatitsnodesareoftenchanginglocation.

6)GreedyDistributedSpanningTreeRouting(GDSTR):TheGDSTRcanfindtheshortestroutesandgenerateslowmaintenancetraffic[100].Themajorcontributionofthisprotocolisthedefinitionofanewkindofspanningtree,whichisahulltree.Ahulltreeisaspanningtreewhereeachnodehasanassociatedconvexhullthatcontainswithinitthelocationsofallitsdescendantnodesinthetree.Thehulltreesarebuiltbyaggregatingconvexhullinformationthatcanbeusedtoavoidpathsthatwillnotbeproductive;instead,theyareabletotraverseasignificantlyreducedsubtree,consistingofonlythenodeswithconvexhullsthatcontainthedestinationpoint.

ThemaindrawbackofGDSTRcomparedtotheothergeographicroutingprotocolsisthatitfacestheproblemofthelocaldeadendswheregreedyforwardingfails.Mostoftheexistinggeographicroutingalgorithmsplanethenodeconnectivitygraphandthenusestheright-handruletoroutearoundtheresultingfaces,inordertohandlethedeadends.TheGDSTRhandlesthissituationdifferentlybyswitchinginsteadtoroutingonaspanningtreeuntilitreachesapointwheregreedyforwardingcanagainmakeprogress.Inordertochooseadirectiononthetree,thatismostlikelytomakeprogresstowardsthedestination,eachGDSTRnodemaintainsasummaryoftheareacoveredbythesub-treebeloweachofitstreeneighbors.

ThemainadvantagesofGDSTRarethatitachieveslowerpathandhopstretchthanexistinggeographicfaceroutingalgorithmsandthatitissimplerandeasiertounderstandandimplement.WhileGDSTRrequiresonlyonetreeforcorrect-ness,itusesrobustnesstogiveitanadditionalforwardingchoice.

7)MinimumEnergyRelayRouting(MERR)-Location:TheMERRisbasedontheideathatthedistancebetweentwonodesthattransmitdataisveryimportant[101].Thisdistanceiscloselyrelatedtotheenergyconsumedontheentirepath,fromthesourcetothebasestation,thatcontains,insomecases,alargenumberofnodes.Thus,inMERReachsensorseekslocallyforthedownstreamnodewithinitsmaximumtransmissionrangewhosedistanceisclosesttothecharacteristicdistance.

Assoonasasensorhasdecidedtousethenexthop,itadjustsitstransmissionpowertothelowestpossiblelevelsuchthattheradiosignalcanjustbereceivedbytherespectivenode.Thiscanminimizetheenergyconsumption.Ifthedistancesbetweeneachpairofsensorsareallgreaterthanthecharacteristicdistance,eachsensorwillselectitsdirectdownstreamneighborasthenexthopnode.

Wepresentanexamplefortheselectionoftheoptimalroutingpathinfigure13.Thefirststepofthisprotocol(1,2and3pointsatthefigure)istoselecttherelays4,2,andbasestation.Theresultingpathfrom5to4thento2thentoBSapproximatestheoptimalcaseandisusedinstep4)toroutedatafromsensor5tothebasestation.

TheMERRworkswellincasethatthesensorsaredeployedoveralineartopologyandsendsdatatoasinglecontrolcenter.Themainadvantageofthisapproachisthatitdistributestheenergyconsumptionofthesensorsuniformlytothenetworksensors.Ontheotherhand,minimizingtransmitenergymeansthatitchoosesthenearestneighborasrouter.Thus,alargeamountofenergyiswastedincasethatthenodeshappentobeveryclosetoeachother.

8)On-demandGeographicForwarding(OGF):TheOGFisacross-layerprotocolthatemploysanexplicitcontentionschemetoestablishanext-hopnode[102].Incasethatasenderneedstosendapacket,itlooksuptheforwardingtableinordertolearnifanentryexiststothedesignationnode.Ifthenext-hopinformationisavailable,thesourcenodeunicaststhepackettothespecifiednext-hopsensor.Ifthenext-hopIDintheentryisaspecialcodecalledpassive,whichdoesnotallowthesendertoforwardpacketsforothersensorsexceptitself,thenthesendergoesintothevoidhandling

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

27

Fig.13.Selectionoftheoptimalroutingpath(redrawnfrom[101]).

modedirectly.Ontheotherhand,ifthereisnonext-hopentryavailable,thesenderinitiatesacontentiontoestablishitsnext-hopsensor.Incasethatnonext-hopsensorislocatedintheforwardingareaduringthecontentionperiod,thesenderswitchestothevoidhandlingmode.Otherwise,anext-hopnodeisestablishedtoreceivethedatapacketfromthesender.Thesenderupdatestheforwardingtablebyinsertinganewentryaftersuccessfullydeliveringthedatapacket.

Theoperationofthisprotocolisbasedontheactualde-mandsoftheapplication,datatraffic,andnetworkdynamics.Thesimulationsresultsin[102]showthatOGFexhibitsasuperiorperformanceintermsofenergyconsumption,scal-ability,andvoidhandling.Additionally,OGFisviableforefficientdatadeliveryinthetargetedsensornetworks.

9)Partial-partitionAvoidingGeographicRouting-Mobile(PAGER-M):ThePAGER-Musesthelocationinformationofsensorsandthebasestationtoassignacostfunctiontoeachsensornode,whichisclosetotheEuclideanlengthofasensornode’sshortestpathtothebasestation[103].Apacketisforwardedtothebasestationusinggreedyforwardingwheneverpossible[104].Greedyforwardingmayfailataconcavenode(localminimum)thathasnocloserneighbortothebasestation.Toavoidthissituation,whenapacketreachessensornodesnearaconcavenode,thepacketisforwardedtoaneighborfollowingthehigh-costtolow-costrule.

Thetestresultsin[103]showthatPAGER-Machieveshighdeliveryratio,lowroutingoverheadandlowenergyconsumption.TheenergyefficiencyofPAGER-Mcomesfromitslowcontroloverheadandlowpathlength.ThisenergyefficiencyofPAGER-MprovesthatissuitableforWSNswithmobilenodes.Ontheotherhand,PAGER-Mdoesnotrequireanodetomemorizethepasttraffic/path;inthissense,itisastatelesslocation-basedroutingprotocol.

10)HybridGeographicRouting(HGR):In[105],anovelhybridgeographicrouting(HGR)schemethatcombinesbothdistanceanddirectionbasedstrategiesinaflexiblemannerisproposed.Inthisprotocolthemainoperationofanodeistodefinethepriorityasthenexthop.ThispriorityisconsideredasQi.Thegreatertheprojectedprogressofnodeiis,thelargerQibecomes,whereasthelowerdeviationanglebetweenthelinethatconnectszwithiandthelinethatconnectszwithjis,thelargerQibecomes.DifferentformsforQicanbedefinedinordertocombineboththedistanceanddirectionbasedroutingcriteria.

ThesimulationresultsshowthatHGRcanachievedeliveryratiothatinmostcasesreaches100percentandlowend-to-enddelaymaybemet.

Moreover,therearealsootherslocation-basedprotocolsapartfromtheabovethathavebeenproposedforWSNs[106],[107],[108],[109],[110].

InTableVII,Location-BasedRoutingSchemesComparisonispresented.Therefore,DREAM,IGF,PAGER-MandHGRcansupportthemobilityofthenodes,whileatthesametimetheykeeptheenergyconsumptionofthenodesinlowlevels.Moreover,GEMandGDSTRtrytominimizeenergyconsumptionofthenodesbyselectingtheshortestpathtoroutetheinformation.Ontheotherhand,GEM,IGF,MERR,OGFandHGRinordertominimizeenergyconsumptiondonotuseperiodicmessages.Moreover,GEM,OGF,PAGER-MandHGRaremorescalablethantheotherprotocolsofthisscheme.Also,DREAMhaslimitedrobust.

Finally,inLocation-BasedProtocolsafewprotocolscanpartiallybeincluded,thataremainlyclassifiedanddescribedindetailsinthecategoriesonthebelow.Theseprotocolsare:TTDD,COUGARandACQUIRE.

B.MobileAgent-basedProtocols

Inmostcases,theapplication-specificnatureofWSNsrequiresthesensornodestohavemultiplecapabilities.Thus,itisimpracticalforsensorstostorealltheprogramsneededinthelocalmemoryandruneverypossibleapplication,duetothetightmemoryconstraints.

Oneofthemainresearchareas,relatedtoWSNsisthedesign,developmentanddeploymentofmobileagentsystems[111].Themobileagentsystemshaveasmaincomponentamobileagent,softwareorprogram,whichmigratesamongthenodesofanetworktoperformataskautonomouslyandintelligently,basedontheenvironmentconditions.Mobileagentsystemsemploymigratingcodesinordertofacilitateflexibleapplicationre-tasking,localprocessing,andcollab-orativesignalandinformationprocessing.Thismayprovidetothenetworkextraflexibility,aswellasnewcapabilitiesincontrasttotheconventionalWSNoperationsthatarebasedontheclient-servercomputingmodel.

Thus,thedesignofmobileagentsandthedevelopmentofprotocolsinWSNsthatareusedtoroutedatafromthesensedareatothedestinationisareallyinterestingsector.In[111]thedesignissueofmobileagentsinWSNsarepresented.Theagent’sdesigncanbedividedinthefollowing:

•Architecture.Thearchitectureisbasedonthetopologyofthenetworkandisfurtherdividedinflatorhierarchical.•Itineraryplanning.Theitineraryistheroutefollowedduringmobileagentmigration.Theitineraryplanningisrelatedtotheselectionofthesetofthesourcenodes,tobevisitedbythemobileagent,andthedeterminationofasource-visitingsequenceinanenergy-efficientmanner.Theitineraryplanningisdividedinstatic,dynamicorhybrid.

•Middlewaresystemdesign.Mobileagentsareoftenim-plementedasmiddleware.Middlewareisusedtobridgethegapbetweentheoperatingsystemandhigh-levelcom-ponentsandtofacilitatethedevelopmentanddeploymentofapplications.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

28

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

TABLEVII

LOCATION-BASEDROUTINGSCHEMESCOMPARISON

Advantages

Scheme

Efficientdatapackettransmission

DREAM

Itattemptstobalanceenergyconsumptionandtherebyincreasesthenetworklifetime

Itallowsmessagestobeefficientlyroutedthroughthenetwork,whileeachnodeonlyneedstoknowthelabelsofitsneighborsRobustperformance,distributionoftheworkload

ItselectsthenodewiththehighestenergylevelinordertoprovideauniformdissipationofenergyItfindstheshortestroutesandgenerateslowmaintenancetrafficItdistributestheenergyconsumptionofthe

sensorsuniformlytothenetworksensorsItexhibitsasuperiorperformanceintermsofenergyconsumption,scalability,andvoidhandling

Itachieveshighdeliveryratio,lowrouting

overheadandlowenergyconsumption

Itcombinesbothdistanceanddirectionbasedstrategiesinaflexiblemanner

Theperiodictableexchange

Itoverloadsnodesthatareatlowlevelsofthetree

Itdependsontheuptodatelocalneighbortables

Itdoesnotworkwellincaseofanetworkthatitsnodesarechanginglocationoften

Overheadtothenetwork

ItwastesenergyincasethatthenodesareclosetoeachotherItdependsontheuptodatelocalneighbortables

Statelesslocation-basedroutingprotocolItdoesnotguaranteesdelay

Limited

Limited

Thewasteofnetworkbandwidth

Limited

Good

Drawbacks

Scalability

Mobility

RouteMetricThepathsthat

minimizetotalpowerconsumptionThebestrouteShortestPath

PeriodicMessageTypeControlmessages

RobustLimited

GEAR

HellomessagesNone

Good

GoodLimitedGood

GEM

LimitedLimited

GoodLimited

IGF

ThebestrouteTheroutethatnodeshavethehighestpowerShortestPathThepathsthat

minimizetotalpowerconsumptionThebestroute

NoneControlmessages

GoodGood

SELAR

LimitedLimited

NoLow

GDSTR

HellomessagesNone

GoodGood

MERR

GoodLimitedNoneGood

OGF

GoodGood

PAGER-M

GoodGood

HGR

TheshortestpathusinggreedyalgorithmThepathsthat

minimizetotalpower

HellomessagesNone

Good

Good

•

Agentcooperation.Mobileagentscanworkeitherassingleprocessingunitsorasadistributedcollectionofcomponents.TherequirementtoprovidethemeansforagentcooperationisanimportantconsiderationinWMSdesigntoreduceenergyconsumptionintheWSN.

InmostcasesapplyingmobileagentsystemsinWSNsmayleadtoreducebandwidthconsumptionandhighflexibilityonthenetwork.Movingthedataprocessingelementstothelocationofthesenseddatamayreducetheenergyexpendituresofthenodes.However,findingtheoptimalitineraryisNP-hardandalotofeffortsareongoing.

1)Multi-agentbasedItineraryPlanning(MIP):In[112],amulti-agentbaseditineraryplanning(MIP)protocolispre-sented.Inmostscenarios,singleagentbaseditineraryplanning(SIP)protocolsaredevelopedandoperateonmobileagentsystems.However,usingSIPprotocolsinalargescalenetworkmayleadtohighdelayratesandunbalancedload.Thus,theuseofaMultiagentitineraryplanning(MIP)protocolisimportanttobeused.

Thebasicideaoftheprotocolproposedin[112]istodistributeeachsource’simpactfactortoothersourcenodes.Forexample,consideringnasthesourcenumber,theneachsourcewillreceiven-1impactfactorsfromothernodesandonefromitself.Afterthattheaccumulatedimpactfactoriscalculatedandthelocationofthesourcewiththelargestaccumulatedimpactfactorisselected.

ThesimulationresultsprovethattheenergyconsumptionofMIPalgorithmishigherthanSIPalgorithmsincasethatthesourcenumberissmall.However,thisalgorithmisdesignedforusewhensourcenumberislarge.Thus,basedontheresultswhenthesourcenumberis40,theenergyconsumptionofMIPalgorithmismuchbetterthatthoseofSIPalgorithms.

2)ItineraryEnergyMinimumforFirst-source-selection(IEMF)andItineraryEnergyMinimumAlgorithm(IEMA):In[113],anItineraryEnergyMinimumforFirst-source-selection(IEMF)algorithmisproposed.Then,theItineraryEnergyMinimumAlgorithm(IEMA),aniterativeversionofIEMF,ispresented.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

29

IntheIEMFalgorithmthefirstactivityistoselectanarbitrarysourcenodevasatentativeS[1]andtheremainingsourcesetisconsideredasbyV-{v}.Thenext,actionistosetvasthestartpointthedeterminationoftheitineraryforthen-1sourcenodesinV-{v}isevaluatedbyvisitinginsequencetheremainingn-1sourcenodes.Thefollowingactionistoobtaintheentireitinerarysequencestartingfromthesink.Thus,everysourceinVisselectedastentativeS[1]andtheitineraryisestablished.ThefinalactionoftheIEMFisselectingtheitinerarythathastheminimumenergycost.However,IEMA,apartfromselectingtheS[1],thisalgo-rithmseekstooptimizetheremainingitinerarytoacertaindegree.

ThesimulationresultshavedemonstratedthatIEMFpro-videshighenergyefficiencywhileitcanachievedeliveryratioupto90percent.However,thelimitationofutilizingasingleagenttoperformthewholetaskmakesthealgorithmunscalablewithalargenumberofsourcenodestobevisited.InTableVIII,MobileAgent-basedRoutingSchemesCom-parisonispresented.Inthistable,theIEMF/IEMAdescribedtohavelimitedscalabilityanditsperformanceisdecreasedasthenumberofnodesisincreased.Ontheotherhand,MIPconsumeslessenergyasthenumberofnodesinthenetworkincreases.

C.ComparisonofLocationandMultiAgent-basedProtocolsThesimulationresultsin[95]showthatDREAMoutper-formstheNetworkStructureschemes,WRPandTORAintermsofaverageenergyconsumption.Ithasadeliveryratioupto80percentandanend-to-enddelayupto50msec.Inad-dition,SELARoutperformsFlooding,GossipingandDREAMintermsofnetworklifetimeandtheamountofdatadelivery.SELARisabletodeliverupto2.5and4timesmorepacketsthanFlooding[99].

Also,thesimulationresultsin[101]showthatMERRachievespowersavingsofupto80percentcomparedtominimumtransmissionenergyroutingandcandeliverpacketswitharatioupto95percent.However,thesimulationresultsin[100]showthatGDSTRroutespacketsalongshorterpathsthantheotheralgorithms,andisthuslikelytodeliverpacketsfasterandwithlessconsumptionofradioresources.However,thiscanminimizethenetwork’slifetime.

TheIGFcandeliverpacketswitharatiocloseto100percent[98].TheIGFhasthebestresultsconcerningtheenergyconsumptionwhenthetoggleperiodsleep/wakeisbelow18seconds.However,OGFoutperformsIGFandDirectDiffusionintermsofenergyconsumption[102].OGFhasanaverageenergydissipatedupto50msec.Itcandelivermorethan90percentofthepacketsevenunderahighsensorfailureratesuchas0,6.

ThePAGER-Machievesanaveragedeliveryratiogreaterthan99percentwithbeaconinterval3-4seconds[103].PAGER-Mhasanaverageenergydissipatedupto10msec.Themaximumenergyusageamongallnodesis57.44mJfordif-fusion.Also,thebitrateis250bits/sec,whichdemonstratestheextremelylowdataraterequirementsofsensornetworks.TheGEARismoreefficientthanFlooding[96].Itachievesenergybalancingbytakingalternativepath;therefore,itisnot

surprisingthatitincreasesthepathlengthby25percentto45percentoverallpacketsdelivered.AlsoinGEMthelivenodesatthenetworkare500from0to6000packetsthataresentandgetinto0at7500packets[97].

Thesimulationresultsin[112]showthatifthesourcenumberis40,theenergyconsumptionofMIPalgorithmismuchbetterthatthoseofSIPalgorithms.Moreover,thesimulationresultsin[113]havedemonstratedthatIEMFprovideshighenergyefficiencywhileitcanachievedeliveryratioupto90percent.

IX.RELIABLEROUTINGSCHEME

A.MultipathBasedRoutingProtocols

Multi-pathroutingisaninterestingoutingmethodforwire-lesssensornetworks.Themulti-pathroutinghastheadvantagetoachieveloadbalancingandismoreresilienttoroutefailures[114].Therearealotofmulti-pathroutingprotocolsthatbelongtothisschemeforwirelesssensornetworksandtheperformanceevaluationsofthemmayshowthattheytakeadvantageofthelowerroutingoverhead,thelowerend-to-enddelayandthealleviatecongestionincomparisonwithsingle-pathroutingprotocols.Wedescribebelowtheroutingprotocolsofthiscategory.

1)RoutingOn-demandAcyclicMultipath(ROAM):TheROAMpresentsanon-demanddistance-vectoralgorithmcalledRoutingOn-demandAcyclicMultipath(ROAM)[115].Itusesaconceptcalledfeasibledistancetomaintainroutesandloopfreedom.ROAMdetectsnetworkpartitionsbyre-quiringnodestosendupdatemessagestoneighboringroutingwheneverthereisachangeindistancetoacertaindestination.InROAM,eachroutermaintainsadistancetable,aroutingtableandalinkcosttable.Thedistancetableisamatrixcontainingthedistancebetweentwoneighborsatarouter.Theroutingtableatrouterisacolumnvectorcontaining,foreachdestination,thedistancetothedestinationnode,thefeasibledistance,thereporteddistance,thesuccessor,thequeryoriginflagandthetimestamp.Thelink-costtableliststhecostsoflinkstoeachknownadjacentneighbor.Whenaroutergetsadatapacketthatistobedeliveredtoadestinationforwhichithasnoentryinitsroutingtable,itstartsadiffusingsearch.Thediffusingsearchpropagatesfromthesourceoutonahopbyhopbasis,untilitreachesarouterthathasanentryfortherequesteddestination.Assoonasitreachesthisentrytherouterreplieswithitsdistancetoit.Attheendofthesearch,thesourceobtainsafinitedistancetothedestination.Ifthethereisnoroutetothedestinationallthenodesinthesameconnectedcomponentdeterminethatthedestinationisunreachable.

TheROAMinformsrouterswhenadestinationisunreach-ableandpreventsroutersfromsendingunnecessarysearchpackets,inordertofindpathstoanunreachabledestina-tion.Sincethealgorithmrequirestheexchangesofstateinformationbetweennodes,itismoresuitableforuseinstaticnetworksornetworkswithlimitedmobility.Themaindisadvantageofthisalgorithmisthatitneedstosendperiodicupdateinordertobeinformedabouttheactivenodes.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

30

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

TABLEVIII

MOBILEAGENT-BASEDROUTINGSCHEMESCOMPARISON

Advantages

Scheme

Itcanconsumelessenergywhenthenumberofnodesofthenetworkislarge

Highdelay

Limited

Good

Drawbacks

Scalability

Mobility

RouteMetricThepathsthat

minimizethetotalpower

consumptionThepathsthat

PeriodicMessageTypeNone

RobustGood

MIP

ThisprotocolseekstooptimizetheremainingItisunscalablewithalargenumberofsourceLimitedGoodNoneGood

IEMF/IEMA

itinerarytoacertainnodestobevisited

degree

2)Label-basedMultipathRouting(LMR):TheLMRbroadcastsacontrolmessagethroughoutthenetworkforapossiblealternatepath[116].Duringtheprocess,labelsareassignedtothepathsthemessagepassesthrough.Thelabelinformationisusedforsegmentedbackuppathsearchifadisjointpathisnotachievable.TheLMRisdesignedtouseonlythelocalizedinformationtofinddisjointpathsorsegmentstoprotecttheworkingpath.Withoneflooding,LMRcaneitherfinddisjointalternatepathsorseveralsegmentstoprotecttheworkingpath.

InLMR,afterthenodes,ontheworkingpath,haverein-forcedoneoftheirlinks,asthelinktoformaworkingpath,theybroadcastalabelmessagetotherestoftheirneighbors.Both,thereinforcementandlabelmessages,takeaninteger,termedlabel.Thevalueofthelabelisincreasedby1byeachworkingnodewhichthenbroadcastsanewlabelmessage.Everyworkingnodeshouldrememberthisvalueasitsownnodelabel.Thelabelmessagesareforwardedtowardsthesourcealongallthepathswhichtheexploratorydatamessagespassthrough.Anodereceivingtwoormorelabelmessageswillforwardtheonewithsmallerlabelvalueonly.Theideaistomakethelabelmessagefromthenodeclosertothesinkgoasfaraspossiblesothatthedisjointpathsarepossibletobefound.

Theworkingnodesdonotforwardthelabelmessagesfromanyothernodes.Everynodeshouldrememberalllabelsithasseenandtheassociatedneighborstheyarecomingfrom.Ifanodereceivesmultiplelabelmessageswiththesamelabelvaluefromdifferentneighbors,onlythefirstoneisrecordedtofindashortestbackuppath.Thelabelinformationcanreducetheroutingoverheadandbackuppathsetupdelay.However,tofindthepossiblealternatepaths,LMRincursoverhead,afloodedlabelmessage,andalabelreinforcemessageandabackupexploratorymessage.

3)GRAdientBroadcast(GRAB):TheGRAB,isdesignedspecificallyforrobustdatadeliveryinordertodealwiththeunreliablenodesandfalliblewirelesslinks[117].Itbuildsandmaintainsacostfieldbypropagatingadvertisement(ADV)packetsinthenetwork.AssoonasanodereceivesanADVpacketcontainingthecostofthesender,itcalculatesitscostbyaddingthelinkcostbetweenitselfandthesendertothesender’sadvertisedcost.Itcomparesthiscosttothepreviouslyrecordedoneandsetsthenewcostasthesmallerofthetwo.Asitobtainsacostsmallerthantheoldone,itbroadcastsanADVpacketcontainingthenewcost.GRABcontrolstheminimizetotalpower

widthofthebandbytheamountofcreditcarriedineachdatamessage,allowingthesendertoadjusttherobustnessofthedatadelivery.

TheadvantageofGRABisthatitreliesonthecollectiveeffortsofmultiplenodestodeliverdata,withoutdependencyonanyindividualonesanditisreallyrobust.Ontheotherhand,Itmayhaveoverheadbysendingredundantdata.

4)Hierarchy-BasedMultipathRoutingProtocol(HMRP):TheHMRPemploysahierarchicalconcepttoconstructanentiresensornetwork[118].Eachsensornode(involvingthesinknode)justneedstobroadcastthelayerconstructionpacketonceandmaintainitsownCIT(CandidatesInformationTable).Whenasensornodedisseminatesadatapacket,itonlyneedstoknowwhichparentnodetotransfer,withouttomain-tainthewholepathinformation.Thiscanreducetheoverheadofthesensornode.AlthoughHMRPhastocomputesomeinformationtorecordintheCITofthesensornode,theenergyexpenseislessthantransmissionandreception.Furthermore,HMRPsupportsmultipathdataforwarding,withoutusingthefixedpath.Theenergyconsumptionwillbedistributedandthelifetimeofthenetworkwillbeprolonged.Finally,HMRPcansupportformultiplesinknodessituation.

HMRPhasmanycandidatepathstodisseminatedatapack-etstothesink.Thedataaggregationmechanismispresentineachnodeapartfromtheleafnodesreducingtheenergycon-sumptioninthenetworks.Theproposedsystemwasdesignedaccordingtothefollowingobjectives:

•Scalability.Thesensingareamayincludehundredsorthousands,sensornodes.TheHMRPcouldbesuitableforasmallorlargesensingscale,sincethecommunicationoverheadamongsensornodesisverylow.

•Simplicity.Thesensorshaverestrictedcomputingcapa-bilityandmemoryresources.Therefore,thisapproachat-temptstominimizethenumbersofoperationsperformed,andthestatesmaintainedateachnode,whichonlyhastomaintainitscandidateparents’informationtabletodeterminetheroutingpath.

•SystemLifetime.Thesenetworksshouldoperateforaslongaspossible,therechargingofthebatteryofnodesmaybeinconvenientorimpossible.Therefore,dataaggregationandenergy-balancedroutingareadoptedtodecreasethenumberofmessagesinthenetworktoextenditsnetworklifetime.

5)Cluster-BasedMulti-PathRouting(CBMPR):TheCBMPRcombinescluster-basedroutingandmulti-pathrout-

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

31

Fig.14.MultiplePathsestablishedwithconventionalmulti-pathroutingprotocol,MultiplePathsestablishedwithCBMPR(redrawnfrom[119]).

ingefficiently[119].TheCBMPRmakesuseofclusternetworktofindmultiplepaths,thatprovideindependentpaths,decreaseroutingcontroloverheadandimprovethenetworksscalability.

Asinallthehierarchicalprotocols,CBMPRsetsclusterheadsandmembernodes.ThenodesinthenetworkssendHELLOmessagesregularly.AclustermemberaddsitsIPaddress;aclusterheadaddstheIPaddressofitsclustermember,intoitsHELLOmessage.AclusterheadkeepstracksofalltheIPaddressesofitsclustermemberinitsroutingtable.Moreover,theclusterheadkeepsaneighbortable,whichcontainsalltheIPaddressesofitsneighborclusterhead.TheCBMPRisamutlipathprotocolasitsetsupmultiplepathsfromthesourcenodetothedestinationnode.Thesepathscanbeclassifiedintooptimalpath,shortestpathandsoon,accordingtothehopnumber(h),accumulateddelay(d)andbandwidth(b)includedinthepathsmessagesreceivedbysource.

Basedontheabovementioned,themainstepsofthisprotocolarethefollowing:

•Thefirststepistocalculatethepathweightvaluew=b/ln(dh)accordingtothehopnumber(h),accumu-lateddelay(d)andbandwidth(b)includedinthepathsmessages.

•ThenextstepistheutilizationM-for-Ndiversitycod-ingtechnique(reconstructtheoriginalXbitinformationpacket,providedthatatleastNblockswillreachthedestination)tosolvetheinherentunreliabilityofthenetworkbyaddingextrainformationoverheadtoeachpacket.Thedatapacketisfragmentedintosmallerblocks.•Finally,accordingtotheweightvalueofthepath,itdistributestheblocksovertheavailablepaths.Astheweightvalueofthepathisgrowing,moreblocksaredistributedoverthepath.Thedataloadisdistributedovermultiplepathsinordertominimizethepacketdroprate,achieveloadbalancing,andimproveend-to-enddelay.Thefigure14showsanexampleofmultiplepathswhichwillsufferlessinterferencebychoosingroutingpathsthroughdifferentclusters.

ThemainadvantageofCBMPRoverconventionalmulti-pathroutingisthelessinterferenceandissimple.EachpathintheCBMPRjustpassesthroughtheheadsofclusters,resultinginasimpleclusterlevelhop-by-hoprouting.ThismakesCBMPRconvenientandsimplereducingtheburdenofinter-ferencecalculationneededateveryintermediatenode.Even

Video Sensor NodeSinkCooperative NodeFig.15.

IllustrationofDGR-basedmultipathvideotransmission.

thoughtheCBMPRcanmitigatetheinterferenceproblemefficiently,path-joiningproblemsmaybeoccurredbecausepathjoiningcanbeeasilycreatedwhilechoosingcluster-by-clusterlink.However,thedatapacketthatisfragmentedintosmallerblocksmustbereassembledatthedestinationnode,itmayleadtoerrorandincreasecontroloverhead.

6)DirectionalGeographicalRouting(DGR):In[120],anovelmultipathroutingprotocolDGRispresented.ThisprotocolisaveryinterestingsolutiontotheproblemofrealtimevideostreamingoverabandwidthandenergyconstrainedWSNfromasmallnumberofdispersedvideosensornodes(VNs)toasinkbycombiningforwarderrorcorrection(FEC)coding.

InDGRanactiveVideoSensorNode(VN)broadcasttoitsdirectneighborsapacketconcatenatingallthedataandFECpacketsofavideoframe.AssoonasthesenodesreceivetheconcatenatedpacketbroadcastedbytheVN,theyselecttheirownpayloadaccordingtotheidentifiersandthesequencenumbersofthecorrespondingpacketsofthesenodes,intheconcatenatedpacket.Thenthesenodesunicasttheassignedpacketstothesinkviatherespectiveindividualpaths.

Anexampleofthisarchitectureispresentedinfigure15,wherethemultipathroutinglayersetsup3pathsbetweenthesourceandthesink.Moreover,eachpathusesadifferentinitialdirectneighbor.Thisarchitectureincombinationwiththeshortestpathroutingalongwiththenumberofsuccessfulframedeliveriesduringtheperiodthatthenodesarealive,isapromisingandusefulschemethatcanefficientroutethevideotrafficofthenetwork.

ThesimulationresultsdemonstratethatDGRcanofferlowdelaythatisaroundto0.05msec,substantiallylongerlifetimeandbetterreceivedvideoquality.Alsotheaveragevideopeaksignaltonoiseratiocanbeimprovedbyupto3dB.

7)DirectionalControlledFusion(DCF):In[121],adirec-tionalcontrolfusion(DCF)algorithmispresented.ThemainabilityoftheDCFisthejointlyconsiderationofdatafusionandloadbalancing.AlsoakeyparameterinDCFnamedmultipathfusionfactorcanprovidethetrade-offsbetweenmultipath-convergingandmultipath-expandinginordertosatisfyspecificQoSrequirementsfromvariousapplications.InDCFonesourcenodeisselectedasthereferencesourceperroundbasedonsomecriteria(maximumoftheremainingenergy,distancefromthecenterofthetargetregion,ordistancetothesink).ThefirststepisforeverysourcenodetostartaReference-Source-Selection-Timer(RSSTimer).At

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

32

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

theRSSTimerarandomvaluetoeachtimerbasedonaspecificcriterionisset.InthisstepasmallvalueofRSSTimerindicatesthatasourcehashighereligibilityasthereferencesource.ThenextstepisthemonitoringoftheRSS-Timer.Thesourcewhosethisvalueexpiresfirstwillbeselectedasthereferencesourceandwillbroadcastanelectionnotificationmessagewithinthetargetregion.Whenothersourcenodesreceivethismessage,theywillcanceltheirRSS-Timersandknowthereferencesource’slocationpiggybackedinthemessage.Thenextstepisthereferencesourcetoinitiatetheconstructionofthereferencepathandthesidesourcestotransmitthecontrolpackets.

8)RoutingProtocolforLowpowerandLossyNetworks(RPL):RPLisanIPv6routingprotocolforWSNsproposedbytheROLLworkinggroupintheIETF[122].ThebasicingredientofRPListheDestinationOrientedDAG(DODAG).ADestinationOrientedDAGisaDAGrootedatasinglerootnode,whichisanodewithnooutgoingedge.

Intheconvergedstate,eachrouterintheWSNhasidentifiedastablesetofparents,onapathtowardstherootoftheDODAG,aswellasoneamongtheseasitspreferredparent.Eachrouter,whichispartofaDODAG,willemitDODAGInformationObject(DIO)messages,usinglink-localmulti-casting,indicatingitsrespectiveRankintheDODAG.UponhavingreceivedanumberofsuchDIOmessages,arouterwillcalculateitsownranksuchthatitisgreaterthantherankofeachofitsparents,anditwillstartemittingDIOmessages.Thus,theDODAGformationstartsattheroot,andspreadsgraduallytocoverthewholenetwork.Therootcantrigger”globalrecalculation”oftheDODAGbywayofincreasingasequencenumberintheDIOmessages.

RPLprovidesamechanismtodisseminateinformationoverthedynamically-formednetworktopology.Thedisseminationenablesminimalconfigurationinthenodes,allowingnodestooperatemostlyautonomously.

TheminimalsetofinrouterstaterequiredinaWSNrouterrunningRPListhefollowing(figure16):•thetheidentiaddressfierandoftherankDODAGofthepreferredroot,

•parent,

•theconfigurationparameterssharedbytheDODAGrootand

•themaximumrankthattheWSNrouterhasitselfadver-tised

Moreover,therearealsoothersmultipath-basedprotocolsapartfromtheabovethathavebeenproposedforWSNs[123],[124].

InTableIX,Multipath-BasedRoutingSchemesComparisonispresented.AsshownfromtableIX,protocolsLMR,HMRP,DGRandDCFdonotuseperiodicmessagesinordertominimizeenergyconsumption.Moreover,DGRdonotsupportmobilityofthenodes,whileROAM,HMRPandGBMPRperformbetterincasethatthenodesarenotmobile.Moreover,LMR,GRAB,HMRP,DGR,DCFandRPLaremorescalablethantheotherprotocolsofthisscheme.Also,LMR,GRAB,DGR,DCFandRPLaremorerobustthantheortherprotocolsofthisscheme.

Finally,inMultipath-BasedProtocolsafewprotocolscanpartiallybeincluded,thataremainlyclassifiedanddescribedindetailsinthecategoriesonthebelow.Theseprotocols

RABFig.16.ThemultiplenodesintheLLNcoordinateoverabackboneandexposethesameDAGID.

are:TBRPF,TORA,TTDD,MIMO,Sleep/Wake,ELCH,DD,MWEandMMSPEED.B.QoS-BasedRoutingProtocols

InQoS-basedroutingprotocols,thenetworkhastobalancebetweenenergyconsumptionanddataquality[125],[126].Inparticular,thenetworkhastosatisfycertainQoSmetrics,e.g.,delay,energy,bandwidth,etc.whendeliveringdatatotheBS.Inthebest-effortroutingthemainconcernsarethethroughputandaverageresponsetime.QoSroutingisusuallyperformedthroughresourcereservationinaconnection-orientedcommu-nicationthatmeettheQoSrequirementsforeachindividualconnection.WhilemanymechanismshavebeenproposedforroutingQoSconstrainedreal-timemultimediadatainwire-basednetworks,theycannotbedirectlyappliedtoWSNsduetothelimitedresources,suchasbandwidthandenergythatasensornodehas.

1)SequentialAssignmentRouting(SAR):TheSARisoneofthefirstroutingprotocolsforWSNsthatintroducesthenotionofQoSintheroutingdecisions[127].RoutingdecisioninSARdependsonthreefactors:energyresources,QoSoneachpath,andtheprioritylevelofeachpacket.Toavoidsingleroutefailure,amulti-pathapproachisusedandlocalizedpathrestorationschemesareused.TheobjectiveofSARalgorithmistominimizetheaverageweightedQoSmetricthroughoutthelifetimeofthenetwork.

2)SPEEDProtocol:AnotherQoSroutingprotocolforWSNsthatprovidessoftreal-timeend-to-endguaranteesisSPEED,whichcanprovidecongestionavoidancewhenthenetworkiscongested[128].TheroutingmoduleinSPEEDiscalledStatelessGeographicNon-Deterministicforwarding(SNFG)andworkswithfourothermodulesatthenetworklayerSPEEDmaintainsadesireddeliveryspeedacrosssensornetworkswithatwo-tieradaptationincludedfordivertingtrafficatthenetworkinglayerandlocallyregulatingpacketssenttotheMAClayer.Itconsistsofthefollowingcomponents(figure17):

•AnAdelay-estimationAPI(Applicationneighbor-beacon-exchangescheme.

ProgrammingInterface).•A•NondeterministicGeographicscheme.

•AForwarding(NGF)algo-rithm.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

33

TABLEIX

MULTIPATH-BASEDROUTINGSCHEMESCOMPARISON

Advantages

Scheme

Itcaninformrouterswhenadestinationisunreachableand

preventsroutersfromsendingunnecessarysearchpackets

Thelabelinformationcanreducetheroutingoverheadandbackuppathsetupdelay

Itreliesonthecollectiveeffortsofmultiplenodestodeliverdata,withoutdependencyonanyindividualones

Scalability,simplicity,andsystemlifetimeLowinterference,simplicity

Itisaveryinterestingsolutiontotheproblemofrealtimevideostreaming

Itprovidesthetrade-offsbetweenmultipath-convergingand

multipath-expandingLowenergyconsumption

ItneedstosendHellomessagestomaintaintheactivenodes

Limited

Limited

Drawbacks

Scalability

Mobility

RouteMetricAnypath

PeriodicMessageTypeHellomessages

RobustLimited

ROAM

LMR

ItmayhaveanoverheadinordertofindthepossiblealternatepathsItmayhaveoverheadbysendingredundantdata

GoodGoodAnypathNoneGood

GoodGood

GRAB

HMRPCBMPR

ItbroadcaststhelayerconstructionpacketoncePathjoiningproblemsmaybeoccurred

Itisoptimizedforvideotraffic

GoodLimitedHigh

LowLowNo

SetofdisjointpathsthatsatisfyQoSrequirementAnypathThebestpathThepathwithdifferentinitialdirectneighborThebestpathShortestPath

Hellomessages

Good

NoneHellomessagesNone

LimitedLimitedHigh

DGR

DCFRPL

ItselectsonesourcenodeasthereferencesourceperroundItsupportsonlyunicasttraffic

HighHighNoneGood

GoodGood

DIOmessages

Good

Fig.17.SpeedProtocol(redrawnfrom[127]).

•••

ANeighborhoodFeedbackLoop(NFL).BackpressureRerouting.Lastmileprocessing.

Underheavycongestion,SPEEDhasslightlyhigherenergyconsumptionmainlybecauseSPEEDdeliversmorepacketstothedestinationthantheotherprotocolswhenheavilycongested.ThemainadvantageofSPEEDisthatitperformsbetterintermsofend-to-enddelayandmissratio.However,SPEEDdoesnotconsiderenergyconsumptioninitsrout-ingprotocol.Therefore,formorerealisticunderstandingofSPEED’senergyconsumption,thereisaneedtocompareittoaroutingprotocolthatisenergy-aware.

3)Multi-PathandMulti-SPEED(MMSPEED)Protocol:TheMMSPEEDisdevelopedforprobabilisticQoSguaranteeinWSNs.TheQoSprovisioningisperformedintwodomains[129]:

•Timelinessdomain.Thiscanbeaccomplishedbyguar-anteeingmultiplepacketdeliveryspeedoptions.

•Reliabilitydomain.Thiscansupportvariousreliabilityrequirementsbyprobabilisticmultipathforwarding.ThesemechanismsforQoSprovisioningarerealizedinalocalizedwaywithoutglobalnetworkinformationbyemploy-inglocalizedgeographicpacketforwardingaugmentedwithdynamiccompensation,whichcompensatesforlocaldecisioninaccuraciesasapackettravelstowardsitsdestination.

ThemainadvantageofMMSPEEDisthatitguaranteesend-to-endrequirementsinalocalizedway,whichisdesir-ableforscalabilityandadaptabilitytolargescaledynamicsensornetworks.ItcanprovideQoSdifferentiationinbothreliabilityandtimelinessdomainsandsignificantlyimprovestheeffectivecapacityofasensornetworkintermsofnumberofflowsthatmeetbothreliabilityandtimelinessrequirements.4)MultimediaGeographicRouting(MGR):In[130],anewarchitecturecalledmobilemultimediasensornetwork(MMSN)andaroutingschemecalledMobileMultimediaGeographicRouting(MGR)arepresented.Inthisarchitecturethemobilemultimediasensornode(MMN)isexploitedtoenhancethesensornetwork’scapabilityforeventdescription.Theproposedprotocolisdesignedtominimizetheenergyconsumptionandsatisfyconstraintsontheaverageend-to-enddelayofspecificapplicationsinMMSNs.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

34

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

hop1s Current nodeDh2StrategictLocationDh-3>tFig.18.

TheStrategicLocationSelectioninMGR.

Inthisprotocol,themainconcernistotreatthedelayguar-anteeingasthegoalwithtoppriorityfortheQoSprovisioning.Then,theprotocolcontinuestheattemptstominimizetheenergyconsumptionandtoenlargethelifetimeofsensors.Thismotivatestoexploittheenergydelaytradeoffsforthedesignofthisprotocol.

Thus,theprotocol’smainoperationistoselecttheideallocationofcurrentnode’snexthop.Inordertoachievethis,MGRcalculatethedesiredhopdistancefornexthopselection(Dhop),bydividingthedistancefromcurrentnodetothesinknode(Dh→t),withthedesiredhopcountfromcurrentnodetothesinknode(Hh→t).

BasedonDhopcalculation,thestrategiclocationofMGRisdecidedasinfigure18.

Thesimulationresultsin[130]showthatfordelaysetto0.035s,theMGRguaranteestheQoSdelayinthemostcases.InadditiontothatMGRsavesabout30percentenergyconsumptionandextendsthenetworklifetimewhencomparedtoclassicalgeographicrouting.

Moreover,therearealsoothershierarchicalprotocolsapartfromtheabovementionedthathavebeenproposedforWSNs[131],[132],[133],[134],[135].

InTableX,aQoS-BasedRoutingSchemesComparisonispresented.Therefore,SAR,SPEEDandMMSPEEDcanprovideenergyefficientroutingwithguaranteequalityofserviceconsideringthatthenodesarenotmobile.Ontheotherhand,MGRcanbemorescalablethantheothersprotocolsasitcanusemobilityofthenodes.

Finally,inQoS-BasedProtocolsafewprotocolscanpar-tiallybeincluded,thataremainlyclassifiedanddescribedindetailsinthecategoriesontheabove.Theseprotocolsare:MIMO,Sleep/Wake,GRAB,DGRandDCF.

C.ComparisonofMultipathandQoSBasedProtocolsTheLMRisefficientwithlocalmulticastandreducestheaveragenumberofmessagesby1/2D(Distheaveragenodedegree)[116].Moreover,inanetworkof400nodes,incaseofunicast,themaximumoverheadpacketnumberis500whileincaseofmulticastthemaximumoverheadpacketnumberis4500.

TheHMRP,comparedtoLEACHandPEGASIS,improvesthelifetime(75percentofthenodesarealive)ofLEACHby200percentandofPEGASISby8percent[118].HMRPdisplaysareductioninenergyconsumptionof35percentoverLEACH.

TheGRABcansuccessfullydeliverover90percentofpacketswithrelativelylowenergycost,evenundertheadverseconditionsof30percentnodefailurescompoundedwith15percentlinkmessagelosses[117].Fordifferentpacketlossrates,theenergyremainsalmostconstantaround16054,increasinglessthan6Joulesasthepacketlossrategrowsfrom5to50percent.However,TheCBMPRincreasesthroughputabout58percentforeachadditionalpath,finallyreachingat2024percentatfourpaths.

Inthesimulationresultsin[122],RPLshowsthatforthegiventopology,90percentofpathshaveapathlengthof4hopsorlesswithanidealshortestpathroutingmethodology,whereasinRPLPoint-to-Point(P2P)routing,90percentofthepathswillhavealengthofnomorethan5hops.Thisresultindicatesthatdespitehavinganon-optimizedP2Proutingscheme,thepathqualityofRPLisclosetoanoptimizedP2Proutingmechanismforthetopologyinconsideration.Moreover,RPLsupportIPv6thatwillbeusedinallthefuturenetworks.

TheSARofferslesspowerconsumptionthantheminimum-energymetricprotocol[127].SARmaintainsmultiplepathsfromnodestoBaseStation.Thisensuresfault-toleranceandeasyrecovery,buttheprotocolsuffersfromtheoverheadofmaintainingthetablesandstatesateachsensornodeespeciallywhenthenumberofnodesishuge.

Theend-to-enddelayfortheSPEEDvariesfrom10msecto140msecforacongestionratefrom0psupto100ps[128].AlsoSPEEDmanagestodeliver95percentofitspacketstothedestination.However,theMMSPEEDcanprovideclearservicedifferentiationinthereliabilitydomainandbothflowgroupsinthesimulationcanmeettheirownreliabilityrequirementsupto20flows[129].Ontheotherhand,inSPEEDprotocol,twoflowgroupsaremixedupwithnodifferentiationanditmakesflowgroup1tomissreliabilityrequirementof0.7for18flowsandmore.Also,MMSPEEDmayleadtomoreenergyconsumptionduetomorecomplexcomputationandlongerframewithoverheadbits.

ThesimulationsresultsshowthattheROAMoutperformsTORAintermsofenergyefficiency[115].

X.FUTURERESEARCHDIRECTIONS

Allroutingprotocolshavethesamegeneralgoalthatistosharenetworkreachabilityinformationamongroutersandachievethisinavarietyofways.Thus,theymaysendacompleteroutingtabletootherroutersorsendspecificinformationonthestatusofdirectlyconnectedlinks.

AlternativeroutingprotocolsmaysendperiodicHELLOpacketstomaintaintheirstatuswithpeerroutersormayincludeadvancedinformationsuchasasubnetmaskorprefixlengthwithrouteinformation.Themostoftheroutingprotocolssharedynamic(learned)information,butinsomecases,staticconfigurationinformationismoreappropriate.However,themajorgoalsfordevelopingroutingprotocolsforWSNsarethefollowing:

•Improvementofnetworksurvivability,availability(uptime)andservice.

•IncreaseGuaranteeofoftheconnectivitysensornetworkunderbatteryvariouslifemissiontime.

•scenar-iosschemes.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

35

TABLEX

QOS-BASEDROUTINGSCHEMESCOMPARISON

Advantages

Scheme

Lowpowerconsumption.Itmaintainsmultiplepathstodestination

SAR

Overheadof

maintainingthetablesandstatesateachsensornodeespeciallywhenthenumberofnodesishuge

Itdoesnotperformwellinheavycongestion

Limited

No

Drawbacks

Scalability

Mobility

RouteMetric

Thepaththatminimizestheaverage

weightedQoSmetricthroughoutthelifetimeofthenetworkThepaththatistheStatelessGeographicNon-DeterministicThepaththatistheStatelessGeographicNon-DeterministicThepathwiththatminimizesthedelay

PeriodicMessageTypeHellomessages

RobustLow

SPEED

Itperformswellintermsofend-to-enddelayandmissratio

ItcanprovideQoSdifferentiationinbothreliabilityandtimelinessdomainsandsignificantlyimprovestheeffective

capacityofasensornetworkItminimizestheenergyconsumptionandsatisfyconstraintsontheaveragedelay

LimitedNo

Hellomessages

Low

MMSPEED

Inahighloadnetwork,itisunabletomeetendtoenddelayrequirements

Ittreatsthedelay

guaranteeingasthegoalwithtoppriority

LimitedNo

Hellomessages

Low

GoodGoodNoneLow

MGR

Efficientenergyconsumptioncontrol.

•Minimizationofthetransferdelayofthemissioncriticalinformation.

•Reductionofcomplexity.

•ImprovementofWSNperformance.

Routingprotocolsdifferintheirscalabilityandperformancecharacteristics.Manyroutingprotocolsaredesignedforsmallinternetworks.Thereareroutingprotocolsthatworkbestinastaticenvironmentandhaveahardtimeconvergingtoanewtopologywhenchangesoccur.However,thereareroutingprotocolsthataremeantforconnectinginteriorcam-pusnetworks,andothersaremeantforconnectingdifferententerprises.Theabovesectionsprovidemoreinformationonthedifferentcharacteristicsofroutingprotocols.

TheWSNshaveseveralrestrictions,suchaslimitedenergysupply,limitedcomputingpower,andlimitedbandwidthofthewirelesslinksconnectingsensornodes.OneofthemaindesigngoalsofWSNsistocarryoutdatacommunicationwhiletryingtoprolongthelifetimeofthenetworkandpre-ventconnectivitydegradationbyemployingaggressiveenergymanagementtechniques.ManyfactorsinfluencethedesignofroutingprotocolsinWSNs.Forexample,networkdeployment,networkdynamic,datadeliverymodelanddataaggregationaremajorWSNssystemdesignissuesandthefactorsthatinfluenceWSNroutingdesignare:energyconsumption,scal-abilityandQoS.

Dependingontheapplicationandthesizeofthenetwork,differentarchitecturesanddesigngoals-constraintshavebeenconsideredforsensornetworks.Itisclearthattheperformanceofaroutingprotocoliscloselyrelatedtothearchitecturalmodel.

Themostimportantfactorsthatinfluencetheselectionofaroutingprotocolare:

•NetworkDynamics:Themaincomponentsinasensornetworkarethesensornodes,sinkandmonitoredevents.Inthemostofthenetworkarchitecturessensornodesare

•

•

•

•

assumedtobestationary.Ontheotherhand,supportingthemobilityofsinksorcluster-headsissometimesnec-essary.Routingmessagessentorreceivedfromnodesaremorechallengingsinceroutestabilitybecomesanimpor-tantoptimizationfactor,inadditiontoenergy,bandwidthetc.Thesensedeventcanbedynamicorstaticandthisdependsontheapplication.Thus,inatargetdetectionapplication,theeventisdynamic,butforestmonitoringforearlyfirepreventionisastaticevent.

NodeDeployment:Thisaffectstheperformanceoftheroutingprotocol.Thedeploymentmaybedeterministicorself-organizing.Indeterministicsituations,thesensorsareplacedmanuallyandallthedataareroutedthroughpre-definedpaths.Inself-organizingsystems,thesensornodesarescatteredrandomlyandcreateaninfrastructureinanadhocmanner.

EnergyConsiderations:Thesetupofarouteisgreatlyin-fluencedbyenergyconsiderations.Sincethetransmissionpowerofawirelessradiodependsondistancesquaredorevenhigherorderinthepresenceofobstacles,multi-hoproutingwillconsumelessenergythandirectcommuni-cation.However,multi-hoproutingmayaddsignificantoverheadfortopologymanagementandmediumaccesscontrol.InContrast,directroutingperformswellenoughifallthenodesareveryclosetothesink.

DataDeliveryModels:Thedatadeliverymodeltothesink,dependingontheapplicationofthesensornetwork,canbecontinuous,event-driven,query-drivenandhybrid.Inthecontinuousdeliverymodel,eachsensorsendsdataperiodically.Inevent-drivenandquery-drivenmodels,thetransmissionofdataistriggeredwhenaneventoccursoraqueryisgeneratedbythesink.Moreover,therearesomenetworksthatapplyahybridmodelusingacombinationofcontinuous,event-drivenandquery-drivendatadelivery.Theroutingprotocolisbasedonthedatadeliverymodel,especiallywithregardtothe

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

36

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

minimizationofenergyconsumptionandroutestability.•

NodeCapabilities:Inasensornetwork,differentfunc-tionalitiescanbeassociatedwiththesensornodes.Inmostnetworks,anodecanbededicatedtoaparticularspecialfunctionsuchasrelaying,sensingandaggrega-tion,asengagingthethreefunctionalitiesatthesametimeonanodemightquicklydraintheenergyofthatnode.

•

DataAggregation/Fusion:Thesensornodesmightgen-eratesimilarpacketsfrommultiplenodesthatcanbeaggregatedsothatthenumberoftransmissionswouldbereduced.Dataaggregationisthecombinationofdatafromdifferentsources.Thiscanbefulfilledbyusingfunctionssuchassuppression,min,maxandaverage.Thesefunctionscanbeperformedeitherpartiallyorfullyineachsensornode.Thecomputationcanbelessenergyconsumingthancommunicationandsubstantialenergysavingscanbeobtainedthroughdataaggrega-tion.Thistechniquecanachieveenergyefficiencyandtrafficoptimizationinanumberofroutingprotocols.Inmanynetworkarchitecturesallaggregationfunctionsareassignedtomorepowerfulandspecializednodes.

IntherecentyearsalargenumberofenergyefficientroutingprotocolsfortheWSNshavebeendeveloped.However,thereisstillalotofworkthathastobedone,notonlyintheareaofenergyefficiencybutalso,inotherareas.Somefactorsthatshouldbeexaminedwhendevelopingaroutingprotocolmaybethefollowing:

•

EnergyBalancedNetwork.Whendevelopinganenergyefficientroutingprotocoltheloadbalancingoftheenergythatthesensorsconsumeshouldbeoneofthemaintargetsoftheprotocol.Thismeansthattheroutingprotocolsneedtominimizetheenergyconsumptionofthenetworkbyselectingnotonlytheshortestroutesbutalsotheroutesthatwillleadtotheextensionofthenetworklifetime.

•

NetworkSecurity.Animportantfactor,apartfromenergyconsumption,isthesecuritythattheprotocolscanoffertoprotectagainsteavesdroppingandmaliciousbehaviorandmoreadvancedschemestobedeveloped.

•

NodesMobility.ThenodesintheWSNwereassumedtobestatic.Inthelastyearsthereisanincreasedinterestinapplicationsthatsupportthemobilityoftheusers.Anexampleofthisisthemedicalcareapplicationswherethemobilesensorsareattachedtothepatientsandneedtosendcontinuesdatafromthepatienttothedoctor.Therearesomeprotocolsthatcoverthis,butstillthereisalotofscopeforfutureresearchinthisarea.

•

PerformanceEvaluationonRealEnvironment.ThemostoftheprotocolsfortheWSNshavebeenevaluatedthroughsimulations.However,itisimportanttoevaluatetheperformanceoftheseprotocolsinrealenvironmentswithalotofusers.

•

Real-TimeApplicationandQoS.Itisanongoingneedtodevelopreal-timeapplicationthatwillofferhighlevelofQoStotheendusers.Thus,itisimportantforthescientiststomakealotofeffortstodeveloproutingprotocolsthatwillofferQoStoreal-timeapplications.

•

IntegrationofFixedwithMobileNetworks.Mostoftheapplications,forexampleinhealthcaremonitoring,requirethedatacollectedfromthesensornodestobetransmittedtoaserversothatthedoctormayaccessandmakeadiagnosisorsendmedicationtothepatients.Inthiscasetheroutingrequirementsofeachenvironmentaredifferent,furtherresearchisnecessaryforhandlingthiskindofsituations.

•QoSroutingprotocols.TheQoSisimportantinthedeliv-eryofthedataincriticalapplicationssuchashealthcare.Thus,thedevelopmentofroutingprotocolsthatconsiderbothenergyefficiencyandaccuratedeliveryofdatawillhelponthisdirection.

Although,manyoftheproposedalgorithmshavebeenevaluatedbyusingsimulationtoolsi.e.NS2,SensorToolkit,manyofthemmightbeimplementedinrealdeploymentsi.e.ImplicitGeographicForwarding(IGF)[98]inmilitarynetworks,TheTopologyDisseminationBasedonReverse-PathForwardingProtocol(TBRPF)[42],[43],Energy-awareTemporarilyOrderedRoutingAlgorithm(E-TORA)[51]andCOUGAR[85]approachinhealthsystems.

Also,thealgorithmsTwo-TierDataDissemination(TTDD)[67],Column-RowLocation,RoutingOn-demandAcyclicMultipath(ROAM)[115],SingleWinnerAlgorithm(SWE)[90]andMultipleWinnerAlgorithm(MWE)[90],sincetheydon’tperformwellinmobileenvironments,canbefurtherstudiedandimprovedinordertoovercometheseloworlimitedmobilityandminimizetheenergyconsumptiondraw-backs.

AnanalyticalsummaryoftheclassificationoftheroutingprotocolsmaybefoundinTableXI.

Inthepaper,eachprotocolisdescribedindetailonceinthemaincategorythatitbelongs.However,themostoftheabovedescribedroutingprotocols,duetotheircharacteristicsmaybepartiallybelonginmorethanonecategory.Forexample,basedonitsmaincharacteristics,TTDDcanbeclassifiedashierarchical-based.However,thisprotocolmayperforminsomecasesaslocation-basedormultipath-basedprotocol.Thus,intheTableXI,TTDDisclassifiedashierarchical-based(boldX),location-based(normalX)andmultipath-based(normalX).

XI.CONCLUSION

InourdaystheWSNshavegreatlyexpandedplayinganimportantroleforthedataefficientselectionandtheirdelivery.Theenergyefficiencyisaveryimportantissueforthenet-worksespeciallyforWSNswhicharecharacterizedbylimitedbatterycapabilities.ThecomplexityandrelianceofcorporateoperationsonWSNsrequiretheuseofenergy-efficientroutingtechniquesandprotocols,whichwillguaranteethenetworkconnectivityandroutingofinformationwiththelessrequiredenergy.

Inthispaper,weconcentrateontheenergyefficientpro-tocolsthathavebeendevelopedforWSNs.Weclassifytheminflat,hierarchical,query-based,coherentandnon-coherent-based,negotiation-based,location-based,mobileagent-based,multipath-based,QoS-based.

Theflatprotocolsmaybeanidealsolutionforasmallnetworkwithfixednodes.However,inalargenetworkthey

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

37

TABLEXI

CLASSIFICATIONOFROUTINGPROTOCOLS

Flat

Protocols

WRPTBRPFTORAGossipingFloodingRR

E-TORAZRPLEACHLEACH-CPEGASISTEENAPTEENVGATTDDBCDCPMIMOHPAR

Sleep/WakeGBDDELCHNHRPASHPERDHACDD

COUGARACQUIRESWEMWESPIN-PPSPIN-ECSPIN-BNSPIN-RLDREAMGEARGEMIGFSELARGDSTRMERROGF

PAGER-MHGRMIP

IEMF/IEMAROAMLMRGRABHMRPCBMPRDGRDCFRPLSARSPEEDMMSPEEDMGR

XXXXXXXX

XXXXXXXXXXXXXXXX

XXX

XX

XXXX

X

XXXX

XXXXXXXXXX

XX

XXXXXXXXX

XXXXXXX

HierarchicalProtocols

QueryBasedProtocols

CoherentandNon-Coherent

NegotiationBasedProtocols

LocationBasedProtocols

MobileAgent-BasedProtocols

MultipathBasedProtocolsXX

X

QoSBasedProtocols

X

X

XXXX

XX

X

XX

X

XX

XX

becomeinfeasiblebecauseoflinkandprocessingoverhead.Thehierarchicalprotocolstrytosolvethisproblemandtoproducescalableandefficientsolutions.Theydividethenetworkintoclustersandtoefficientlymaintaintheenergyconsumptionofsensornodesandperformdataaggregationandfusioninordertodecreasethenumberoftransmittedmessagestothesink.Theclustersareformattedbasedontheenergyreserveofsensorsandsensor’sproximitytotheclusterhead.Thus,hierarchicalprotocolsaresuitableforsensornetworkswithheavyloadandwidecoveragearea.Ontheotherhand,thelocationbasedprotocolsmaybeusefulforhighdynamicnetworksastheydonotneedastateinroutersnorinpacketheaderanddonotcausefloodinthesearch.Theyuselocationinformationinordertocalculatethedistanceamongnodes,thusminimizingtheenergyconsumptionandextendthelifetimeofthenetwork.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

38

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

Thenegotiationbasedprotocolscanperformclosetothetheoreticaloptimuminbothpoint-to-pointandbroadcastnetworks.Ontheotherhand,theycannotguaranteethesuccessfuldeliveryofdata.Themultipathprotocolsmaintainmultiplepathsfromnodestosink.Thisensuresfaulttoleranceandeasyrecoverybutastheyneedtofindmultiplepathstheysufferfromtheoverheadofmaintainingthetablesandstatesateachsensornodeespecially.Ontheotherhand,inQuery-basedroutingprotocols,thedestinationnodessendaqueryfordatafromanodethroughthenetworkandthenodehavingthisdatasendsthesedatabacktothedestinationnodes.Query-basedroutingisusedtonetworkswithdynamicnetworktopologiessuchasWSNs.Afeatureofroute-queryprotocolsisthesupportformultipleroutereplies.TheproblemoftheaccuratedeliveryofthedatafromthesourcetothedestinationissolvedbyQoSprotocols.TheyensureoptimizedQoSmetricssuchasdelaybound,energyefficiency,andlowbandwidthconsumptionwhileachievingenergyefficiencyinWSNsapplications.Thecoherent-basedroutingprotocolisanenergyefficientmechanismwhereonlytheminimumprocessingisdonebythesensornode.Atnon-coherentdataprocessingbasedonrouting,thesensornodeslocallyprocesstheactualdataandthensendtotheothernodesforfurtherprocessing.

TheapplicationofeachschemeinaWSNhasitsadvantagesanddisadvantages,asTablesII,III,IV,V,VI,VII,VIIIandIXdepict.Therefore,furtherinvestigationinordertodevelopaschemethatwillextendthelifetimeoftheWSNsisneededinordertoimprovetheenergyconsumptionofthesensorsonthenetwork.

Withthepenetrationofnextgenerationwirelessmobilenetworksandpersonalcommunicationsystemsandtheex-ploitationofthesensorarchitecturesanewtypeofschemehasbeenoccurred,themobileagentbased.Mobileagent-basedroutingprotocolshaveasmaincomponentamobileagent,softwareorprogram,whichmigratesamongthenodesofanetworktoperformataskautonomouslyandintelligently,basedontheenvironmentconditions.However,sincetheseagentspresentdifferentcharacteristicsintermsofcoverage,bandwidthanddelay,routingisacriticalprocessandshouldbetakenundercarefulconsiderationinordertoensurethecontinuityofconnectionsandtheenergyconsumptionofthenodes.

Therefore,theapplicationoftheproperroutingprotocolwillincreasethenetworklifetimeandatthesametimeitwillensurethenetworkconnectivityandefficientdatadelivery.

REFERENCES

[1]NikolaosA.Pantazis,DimitriosD.Vergados,“ASurveyonPower

ControlIssuesinWirelessSensorNetworks,”IEEECommunicationsSurveys,2007,Vol.9,Issue4,pp.86-107.

[2]I.F.Akyildiz,W.Su,Y.Sankarasubramaniam,E.Cayirci,“Wireless

SensorNetworks:ASurvey,”ComputerNetworks,2002,Vol.38,Issue4,pp.399-422.

[3]Al-Karaki,A.Kamal,“RoutingTechniquesinWirelessSensornet-works:ASurvey,”SecurityandNetworks,2004,Vol.11,Issue6,pp.6-28.

[4]K.Akkaya,M.Younis,“ASurveyonRoutingProtocolsforWireless

SensorNetworks,”AdHocNetwork,Elsevier,2005,Vol.3,Issue3,pp.325-349.

[5]S.Guo,O.Yang,“Energy-AwareMulticastinginWirelessAdhoc

Networks:ASurveyandDiscussion,”ComputerCommunications,Elsevier,2007,Vol.30,Issue9,pp.21292148.

[6]J.Yick,B.Mukherjee,D.Ghosal,“WirelessSensorNetworkSurvey,”

ComputerNetworks,2008,Vol.52,Issue12,pp.2292-2330.

[7]G.Anastasi,M.Conti,M.Francesco,A.Passarella,“EnergyConserva-tioninWirelessSensorNetworks:Asurvey,”AdHocNetworks,2009,Vol.7,Issue3,pp.537-568.

[8]R.V.Biradar,V.C.Patil,S.R.Sawant,R.R.Mudholkar,“Classi-fiacationandComparisonofRoutingProtocolsinWirelessSensorNetworks,”SpecialIssueonUbiquitousComputingSecuritySystems,2009,Vol.4,Issue2,pp.704-711.

[9]R.Yadav,S.Varma,N.Malaviya,“ASurveyofMACProtocolsfor

WirelessSensorNetworks,”UbiCCJournal,2009,Vol.4,Issue3,pp.827-833.

[10]S.Ehsan,B.Hamdaoui,“ASurveyonEnergy-EfficientRouting

TechniqueswithQoSAssurancesforWirelessMultimediaSensorNetworks,”IEEECommun.SurveysTuts.,2011,Vol.14,Issue2,pp.265-278.

[11]E.Shi,A.Perrig,“DesigningSecureSensorNetworks,”IEEEWireless

Commun.,2004,Vol.11,Issue6,pp.38-43.

[12]A.Basharat,N.Catbas,M.Shah,“AFrameworkforIntelligentSensor

NetworkwithVideoCameraforStructuralHealthMonitoringofBridges,”InProc.3rdIEEEInternationalConferenceonPervasiveComputingandCommunications(PerCom),Hawaii,2005,pp.385-389.

[13]J.Paek,K.Chintalapudi,R.Govindan,J.Caffrey,S.Masri,“AWireless

SensorNetworkforStructuralHealthMonitoring:PerformanceandExperience,”InProc.2ndIEEEWorkshoponEmbeddedNetworkedSensorsEmNetS-II,SyndeyAustralia,2005,pp.1-10.

[14]S.Dengler,A.Awad,F.Dressler,“Sensor/ActuatorNetworksinSmart

HomesforSupportingElderlyandhandicappedPeople,”InProc.21stInternationalConferenceonAdvancedInformationNetworkingandApplicationsWorkshops,NiagaraFalls,2007,Vol.2,pp.863-868.[15]S.Li,“WirelessSensorActuatorNetworkforLightMonitoringand

ControlApplication,”InProc.IEEEConsumerCommunicationsandNetworkingConference,LasVegas,2006,Vol.2,pp.974-978.

[16]C.Lombriser,N.Bharatula,D.Roggen,G.Troster,“On-BodyActivity

RecognitioninaDynamicSensorNetwork,”InProc.2ndInternationalConferenceonBodyAreaNetworks(BodyNets),Florence,Italy,June2007,Vol.17,pp.1-6.

[17]P.Gibbons,B.Karp,Y.Ke,S.Nath,S.Seshan,“IrisNet:ANArchitec-tureforaWorldwideSensorWeb,”IEEEPervasiveComputing,2003,Vol.2,Issue4,pp.22-33.

[18]M.Srivastava,M.Hansen,J.Burke,A.Parker,S.Reddy,G.Saurabh,

M.Allman,V.Paxson,D.Estrin,“WirelessUrbanSensingSystem,”CENSTechnicalReport65,2006,pp.1-20.

[19]A.Dunkels,R.Gold,S.Marti,A.Pears,M.Uddenfeldt,“Janus:An

ArchitectureforFlexibleAccesstoSensorNnetwork,”InProc.1stACMWorkshoponDynamicInterconnectionofNetworks,Cologne,Germany,2005,pp48-52.

[20]Q.Wang,M.Hempstead,W.Yang,“ARealisticPowerConsumption

ModelforWirelessSensorNetworkDevices,”InProc.3rdAnnualIEEECommunicationsSocietyonSensorandAdHocCommunicationsandNetworks,Reston,2006,Vol.1,pp.286-295.

[21]A.Dunkels,F.Osterlind,N.Tsiftes,Z.He,“Software-BasedOn-LineEnergyEstimationforSensorNodes,”InProc.4thworkshoponEmbeddedNetworkedSensors,NewYork,USA,2007,pp.28-32.[22]S.Kellner,M.Pink,D.Meier,E.Blass,“TowardsaRealisticEnergy

ModelforWirelessSensorNetworks,”InProc.5thAnnualConferenceonWirelessonDemandNetworkSystemsandServices,Garmisch,2008,pp.97-100.

[23]Q.Wang,W.Yang,“EnergyConsumptionModelforPowerMan-agementinWirelessSensorNetworks,”InProc.4thAnnualIEEECommunicationsSocietyConferenceonSensor,MeshandAdHocCommunicationsandNetworks,SanDiego,2007,pp.142-151.

[24]A.Shareef,Y.Zhu,“EnergyModelingofWirelessSensorNodesBased

onPetriNets,”InProc.39thInternationalConferenceonParallelProcessing,SanDiego,2010,pp.101-110.

[25]H.Zhou,D.Luo,Y.Gao,D.Zuo,“ModelingofNodeEnergy

ConsumptionforWirelessSensorNetworks,”WirelessSensorNetwork,2011,Vol.3,Issue1,pp.18-23.

[26]T.Lee,“TheDesignofCMOSRadio-FrequencyIntegratedCircuits,”

CambridgeUniversityPress,1998.

[27]A.Mainwaring,J.Polastre,R.Szewczyk,D.Culler,J.Anderson,

“WirelessSensorNetworksforHabitatMonitoring,”InProc.1stInternationalWorkshoponWirelessSensorNetworksandApplications,Atlanta,2002,pp.88-97.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

39

[28]P.Wang,I.Akyildiz,“EffectsofDifferentMobilityModelsonTraffic

PatternsinWirelessSensorNetworks,”InProc.IEEEGlobalCommu-nicationsConferenceExhibitionandIndustryForum(GLOBECOM),Miami,2010,pp.1-5.

[29]J.M.Rabaey,M.J.Ammer,J.L.daSilva,D.Patel,S.Roundy,

“PicoRadioSupportsAdhocUltralowPowerWirelessNetworking,”IEEEComputer,2000,Vol.33,Issue7,pp.4248.

[30]A.P.Chandrakasan,R.Min,M.Bhardwaj,S.Cho,A.Wang,“Power

AwareWirelessMicrosensorSystems,”KeynotepaperatESSCIRC,Florence,Italy,2002,pp.47-54.

[31]L.Alazzawi,A.Elkateeb,“PerformanceEvaluationoftheWSNRout-ingProtocolsScalability,”JournalofComputerSystems,Networks,andCommunications,2008,Vol.14,Issue2,pp.1-9.

[32]S.C.Ergen,P.Varaiya,“OnMulti-HopRoutingforEnergyEfficiency,”

IEEECommun.Lett.,2005,Vol.9,Issue10,pp.880-881.

[33]J.Chang,,L.Tassiulas,“EnergyConservingRoutinginWireless

Ad-HocNetworks,”InProc.InternationalConferenceonComputerCommunications,Tel-Aviv,Israel,2000,pp.22-31.

[34]Y.Fan,A.Chen,L.Songwu,L.Zhang,“AScalableSolutionto

MinimumCostForwardinginLargeScaleSensorNetworks,”InProc.10thInternationalConferenceonComputerCommunicationsandNetworks,Scottsdale,Orlando,USA,2001,pp.304309.

[35]Y.J.Zhai,R.Govindan,D.Estrin,“ResidualEnergyScansforMon-itoringWirelessSensorNetworks,”InProc.IEEEWirelessCommun.andNetworkingConference(WCNC’02),Orlando,USA,2002,Vol.1,pp.356-362.

[36]R.Mini,M.Machado,A.Loureiro,B.Nath,“Prediction-BasedEnergy

MapforWirelessSensorNetworks,”AdHocNetworks,2005,Vol.3,Issue2,pp.235-253.

[37]D.Guidoni,R.Mini,A.Loureiro,“CreatingSmall-WorldModels

inWirelessSensorNetworks,”InProc.19thIEEEInternationalSymposiumonPersonalIndoorandMobileRadioCommunications,Cannes,France,2008,pp.1-6.

[38]L.Junhai,X.Liu,Y.Danxia,“ResearchonMulticastRoutingProtocols

forMobilead-hocNetworks,”ComputerNetworks,2008,Vol.52,Issue5,pp.988-997.

[39]A.Savvides,C.Han,M.Srivastava,“DynamicFine-GrainedLocal-izationinAd-HocNetworksofSensors,”InProc.7thACMAnnualInternationalConferenceonMobileComputingandNetworking(Mo-biCom),Italy,2001,pp.166-179.

[40]P.Arce,J.Guerri,A.Pajares,O.Lazaro,“PerformanceEvaluationof

VideoStreamingOverAdHocNetworksUsingFlatandHierarchicalRoutingProtocols,”Book:MobileNetworksandApplications,2008,pp.324-336.

[41]S.Murphy,L.Aceves,“AnEfficientRoutingProtocolforWireless

Networks,”MobileNetworksandApplications,ACMJournal,USA,Hingham,1996,Vol.1,Issue2,pp.183-197.

[42]B.Bellur,R.Ogier,“AReliable,EfficientTopologyBroadcastProtocol

forDynamicNetworks,”InProc.IEEEINFOCOM’99,NewYork,USA,1999,vol.1,pp.178-186.

[43]R.Ogier,F.Templin,M.Lewis,“TopologyDisseminationBasedon

Reverse-PathForwarding(TBRPF),”RFCEditor2004.

[44]H.Pucha,S.Das,Y.Hu,“ThePerformanceImpactofTrafficPat-ternsonRoutingProtocolsinMobileAdHocNetworks,”ComputerNetworks,2007,Vol.51,Issue12,pp.3595-3616.

[45]D.Park,S.Corson,“AHighlyAdaptiveDistributedRoutingAlgorithm

forMobileWirelessNetworks,”InProc.16thConferenceonComputerandCommunicationsSocieties,Japan,1997,pp.1405-1413.

[46]S.Bali,“PerformanceComparisonsofDSRandTORA,”Wireless

NetworksandMobileComputing,SouthCarolina,2001,pp.10-15.[47]S.Hedetniemi,A.Liestman,“ASurveyofGossipingandBroadcasting

inCommunicationNetworks,”Book:Networks,1998,Vol.18,Issue4,pp.319-349.

[48]H.Lim,C.Kim,“FloodinginWirelessAdHocNetworks,”Computer

Communications,2001,Vol.24,Issue3,pp.353-363.

[49]M.Ma,Y.Yang,C.Ma,“Single-PathFloodingChainRoutingin

MobileWirelessNetworks,”InternationalJournalofSensorNetworks,2006,Vol.1,issue2,pp.11-19.

[50]D.Braginsky,D.Estrin,“RumorRoutingAlgorithmforSensorNet-works,”InProc.1stACMInternationalWorkshoponWirelessSensorNetworksandApplications,USA,Atlanta,2002,pp.22-31.

[51]F.Yu,Y.Li,F.Fang,Q.Chen,“ANewTORA-BasedEnergyAware

RoutingProtocolinMobileAdHocNetworks,”InProc.3rdIEEE/IFIPInternationalConferenceinCentralAsiaonInternet(ICI),Tashkent,2007,pp.1-4.

[52]K.Yadav,J.Singh,B.Singla,“ProactivevsReactiveProtocolsfor

Ad-HocNetworks,”InProc.WorldCongressonScience,EngineeringandTechnology,Germany,2008,pp.20-25.[53]S.Lee,Y.Yu,S.Nelakuditi,Z.Zhang,C.Chuah,“Proactivevs

ReactiveApproachestoFailureResilientRouting,”InProc.23rdAnnualJointConferenceoftheIEEEComputerandCommunicationsSocieties,China,2004,Vol.1,pp.176-186.

[54]LiLayuan,LiChunlin,YaunPeiyan,“PerformanceEvaluationand

SimulationsofRoutingProtocolsinAdHocNetworks,”ComputerCommunications,2007,Vol.30,Issue8,pp.1890-1898.

[55]Z.J.Haas,“ANewRoutingProtocolfortheReconfigurableWireless

Networks,”InProc.6thInternationalConferenceonUniversalPer-sonalCommunicationsRecord,SanDiego,CA,1997,Vol.2,pp.562-566.

[56]Z.Haas,M.Pearlman,“ThePerformanceofQueryControlSchemes

fortheZoneRoutingProtocol,”IEEE/ACMTrans.Netw.,USA,Pis-cataway,2001,Vol.9,Issue4,pp.427-438.

[57]W.Heinzelman,A.Chandrakasan,H.Balakrishnan,“Energy-Efficient

CommunicationProtocolforWirelessMicrosensorNetworks,”InProc.33rdHawaiiInternationalConferenceonSystemSciences,HI,USA,2000,Vol.8,pp.110.

[58]M.J.Handy,M.Haase,D.Timmermann,“LowEnergyAdaptiveClus-teringHierarchywithDeterministicCluster-HeadSelection,”InProc.4thInternationalWorkshoponMobileandWirelessCommunicationsNetwork,USA,2002,Vol.1,pp.368-372.

[59]D.A.Vidhate,A.K.Patil,S.S.Pophale,“PerformanceEvaluation

ofLowEnergyAdaptiveClusteringHierarchyProtocolforWirelessSensorNetworks,”InProc.InternationalConferenceandWorkshoponEmergingTrendsinTechnology(ICWET2010)TCET,Mumbai,India,2010,pp.59-63.

[60]W.Heinzelman,A.Chandrakasan,H.Balakrishnan,“AnApplication-SpecificProtocolArchitectureforWirelessMicrosensorNetworks,”IEEETrans.WirelessCommun.,2002,Vol.1,Issue4,pp.60-70.[61]S.Lindsey,C.Raghavendra,“PEGASIS:Power-EfficientGAtheringin

SensorInformationSystems,”InProc.IEEEAerospaceConference,USA,Montana,2002,Vol.3,pp.1125-1130.

[62]S.Jung,Y.Han,T.Chung,“TheConcentricClusteringScheme

forEfficientEnergyConsumptioninthePEGASIS,”InProc.9thInternationalConferenceonAdvancedCommunicationTechnology,Gangwon-Do,2007,Vol.1,pp.260-265.

[63]L.Almazaydeh,E.Abdelfattah,M.Al-Bzoor,A.Al-Rahayfeh,“Perfor-manceEvaluationofRoutingProtocolsinWirelessSensorNetworks,”ComputerScienceandInformationTechnology,2010,Vol.2,Issue2,pp.64-73.

[64]A.Manjeshwar,D.Agrawal,“Teen:ARoutingProtocolforEnhanced

EfficiencyinWirelessSensorNetworks,”InProc.15thInternationalParallelandDistributedProcessingSymposium(IPDPS’01)Work-shops,USA,California,2001,pp.2009-2015.

[65]A.Manjeshwar,D.Agrawal,“APTEEN:AHybridProtocolforEffi-cientRoutingandComprehensiveInformationRetrievalinWirelessSensorNetworks,”InProc.InternationalParallelandDistributedProcessingSymposium,Florida,2002,pp.195-202.

[66]J.NAl-Karaki,R.Mustafa,A.Kamal,“DataAggregationinWireless

SensorNetworksExactandApproximateAlgorithms,”InProc.IEEEWorkshopHighPerformanceSwitchingandRouting2004,Phoenix,AZ,2004,pp.241-245.

[67]H.Luo,F.Ye,J.Cheng,S.Lu,L.Zhang,“TTDD:Two-TierData

DisseminationinLarge-ScaleWirelessSensorNetworks,”WirelessNetworks,SpringerNetherlands,2005,Vol.11,Issue1,pp.161-175.[68]S.Muruganathan,D.Ma,R.Bhasin,A.Fapojuwo,“ACentralized

Energy-EfficientRoutingProtocolforWirelessSensorNetworks,”IEEECommun.Mag.,2005,Vol.43,Issue3,pp.8-13.

[69]Y.Yuan,Z.He,M.Chen,“VirtualMIMO-basedCross-layerDesign

forWirelessSensorNetworks,”IEEETrans.Veh.Technol.,2006,Vol.55,Issue3,pp.856-864.

[70]Q.Li,J.Aslam,D.Rus,“HierarchicalPower-awareRoutinginSensor

Networks,”InProc.DIMACSWorkshoponPervasiveNetworking,California,2001,pp.25-27.

[71]Y.Wu,S.Fahmy,N.Shroff,“EnergyEfficientSleep/WakeScheduling

forMulti-HopSensorNetworks:non-ConvexityandApproximationAlgorithm,”InProc.26thAnnualIEEEConferenceonComputerCommunications(INFOCOM2007),Anchorage,Alaska,2007,pp.1568-1576.

[72]T.P.Sharma,R.C.Joshi,ManojMisra,“GBDD:GridBasedDataDis-seminationinWirelessSensorNetworks,”InProc.16thInternationalConferenceonAdvancedComputingandCommunications(ADCOM2008),Chennai,India,2008,pp.234-240.

[73]J.Lotf,M.Bonab,S.Khorsandi,“ANovelCluster-basedRouting

ProtocolwithExtendingLifetimeforWirelessSensorNetworks,”InProc.5thIFIPInternationalConferenceonWirelessandOptical

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

40

IEEECOMMUNICATIONSSURVEYS&TUTORIALS,ACCEPTEDFORPUBLICATION

CommunicationsNetworks(WOCN08),EastJavaIndonesia,Surabaya,2008,pp.1-5.

[74]H.Cheng,G.Yang,S.Hu,“NHRPA:ANovelHierarchicalRoutingProtocolAlgorithmforWirelessSensorNetworks,”ChinaUniversitiesofPostsandTelecommunications,2008,Vol.15,Issue3,pp.75-81.[75]

D.Kandris,P.Tsioumas,A.Tzes,G.Nikolakopoulos,DimitriosD.Vergados,“PowerConservationThroughEnergyEfficientRoutinginWirelessSensorNetworks,”Sensors,2009,Vol.9,Issue9,pp.7320-7342.

[76]C.H.Lung,C.Zhou,“UsingHierarchicalAgglomerativeClusteringinWirelessSensorNetworks:AnEnergy-efficientandFlexibleAp-proach,”AdHocNetworks,2010,Vol.8,Issue3,pp.328-344.

[77]S.Zhao,L.Tan,J.Li,“ADistributedEnergyEfficientMulticastRoutingAlgorithmforWANETs,”SensorNetworks,2006,Vol.2,Issue2,pp.62-67.

[78]Y.Yang,H.Wu,H.Chen,“SHORT:ShortestHopRoutingTreeforWirelessSensorNetworks,”SensorNetworks,2007,Vol.2,Issue5,pp.368-374.

[79]Y.Jia,L.Zhao,B.Ma,“AHclustering-BasedRoutingProtocolforWirelessSensorNetworksSupportingMultipleDataAggregationQualities,”SensorNetworks,2008,Vol.4,Issue1,pp.79-91.

[80]W.El-Hajj,D.Kountanis,A.Al-Fuqaha,S.Guizani,“AFuzzy-BasedVirtualBackboneRoutingforLarge-ScaleMANETs,”SensorNetworks,2008,Vol.4,Issue4,pp.250-259.

[81]J.Liu,X.Hong,“AnOnlineEnergy-EfficientRoutingProtocolwithTrafficLoadProspectsinWirelessSensorNetworks,”SensorNetworks,2009,Vol.5,Issue3,pp.185-197.

[82]

S.Giannoulis,C.Antonopoulos,E.Topalis,S.Koubias,“ZRPversusDSRandTORA:AcomprehensivesurveyonZRPperformance,”InProc.10thIEEEConferenceonEmergingTechnologiesandFactoryAutomation,Catania,2005,pp.1017-1024.

[83]N.Sadagopan,B.Krishnamachari,A.Helmy,“ActiveQueryForward-inginSensorNetworks,”AdHocNetworks,2005,Vol.3,Issue1,pp.91-113.

[84]

C.Intanagonwiwat,R.Govindan,D.Estrin,“DirectedDiffusion:AScalableandRobustCommunicationParadigmforSensorNetworks,”InProc.6thAnnualInternationalConferenceonMobileComputingandNetworking,Boston,Massachusetts,2000,pp.56-67.

[85]Y.Yao,J.Gehrke,“TheCougarApproachtoIn-NetworkQueryProcessinginSensorNetworks,”SIGMODRecord,2002,Vol.31,Issue3,pp.9-18.

[86]

NikolaosA.Pantazis,DimitriosJ.Vergados,DimitriosD.Vergados,“IncreasingIntelligentWirelessSensorNetworksSurvivabilitybyApplyingEnergy-EfficientSchemes,”InProc.3rdIFIPInternationalConferenceonArtificialIntelligenceApplicationsandInnovations,SpringerIFIP(InternationalFederationforInformationProcessing),2006,Vol.204,pp.657-664.

[87]N.Sadagopan,B.Krishnamachari,A.Helmy,“ActiveQueryForward-inginSensorNetworks(ACQUIRE),”AdHocNetworks,2005,Vol.3,Issue1,pp.91-113.

[88]K.Sohrabi,J.Pottie,“ProtocolsforSelf-OrganizationofaWirelessSensorNetwork,”IEEEPers.Commun.,2000,Vol.7,Issue5,pp16-27.

[89]V.Jolly,S.Latifi,“ComprehensiveStudyofRoutingManagementinWirelessSensorNetworks-Part-2,”InProc.InternationalConferenceonWirelessNetworks,LasVegas,Nevada,USA,2006,pp.4962.[90]

D.Cevizovic,S.Galovic,S.Zekovic,Z.Ivic,“BoundaryBetweenCoherentandNoncoherentSmallPolaronMotion:InfluenceofthePhononHardening,”PhysicaB:CondensedMatter,2009,Vol.404,Issue2,pp.270-274.

[91]

J.Kulik,W.Rabiner,H.Balakrishnan,“AdaptiveProtocolsforInfor-mationDisseminationinWirelessSensorNetworks,”InProc.5thAn-nualACM/IEEEInternationalConferenceonMobileComputingandNetworking,MassachusettsInstituteofTechnology,USA,Washington,1999,pp.174-185.

[92]

F.Bokhari,“Energy-EfficientQoS-basedRoutingProtocolforWirelessSensorNetworks,”ParallelandDistributedComputing,DepartmentofComputerScience,LahoreUniversityofManagementSciences,2010,Vol.70,Issue8,pp.849-85.

[93]C.M.Cordeiro,D.P.Agrawal,“Book:AdhocandSensorNet-works:TheoryandApplicationsEdition,”WorldScientific,2006.

[94]J.Kulik,W.Heinzelman,H.Balakrishnan,“Negotiation-BasedPro-tocolsforDisseminatingInformationinWirelessSensorNetworks,”WirelessNetworksJournal,2004,Vol.8,Issue2,pp.169-185.

[95]

S.Basagni,I.Chlamtac,V.Syrotiuk,B.Woodward,“ADistanceRoutingEffectAlgorithmforMobility(DREAM),”InProc.4thannualACM/IEEEinternationalconferenceonMobilecomputingandnetworking,USA,Texas,1998,pp.67-84.[96]Y.Yu,R.Govindan,D.Estrin,“GeographicalandEnergyAware

Routing:ARecursiveDataDisseminationProtocolforWirelessSensorNetworks,”UCLAComputerScienceDepartmentTechnicalReport,2001,pp.1-11.

[97]J.Newsome,D.Song,“GEM:GraphEMbeddingforRoutingand

Data-centricStorageinSensorNetworksWithoutGeographicInforma-tion,”InProc.1stInternationalConferenceonEmbeddedNetworkedSensorSystems,California,USA,2003,pp.76-88.

[98]B.Blum,T.He,S.Son,J.Stankovic,“IGF:AState-FreeRobust

CommunicationProtocolforWirelessSensorNetworks,”TechnicalReportCS-2003-11,DepartmentofComputerScience,UniversityofVirginia,USA,2003.

[99]G.Lukachan,M.Labrador,“SELAR:ScalableEnergy-EfficientLo-cationAidedRoutingProtocolforWirelessSensorNetworks,”InProc.29thAnnualIEEEInternationalConferenceonLocalComputerNetworks,USA,Florida,2004,pp.694-695.

[100]B.Leong,B.Liskov,R.Morris,“GeographicRoutingWithoutPla-narization,”InProc.3rdConferenceonNetworkedSystemsDesignandImplementation,SanJose,CA,2006,Vol.3,pp.25-39.

[101]M.Zimmerling,W.Dargie,J.M.Reason,“Energy-EfficientRouting

inLinearWirelessSensorNetworks,”InProc.4thIEEEInternatonalConferenceonMobileAdhocandSensorSystems(MASS2007),Italy,Pisa,2007,pp.1-3.

[102]D.Chen,P.Varshney,“On-demandGeographicForwardingforData

DeliveryinWirelessSensorNetworks,”ComputerCommunications,2007,Vol.30,Issue14-15,pp.29542967.

[103]L.Zou,M.Lu,Z.Xiong,“PAGER-M:ANovelLocation-Based

RoutingProtocolforMobileSensorNetworks,”InProc.2007ACMSIGMODInternationalConferenceonManagementofData,Beijing,China,2007,pp.1182-1185.

[104]I.Stojmenovic,X.Lin,“Loop-freeHybridSingle-Path/Flooding

RoutingAlgorithmswithGuaranteedDeliveryforWirelessNetworks,”IEEETrans.ParallelDistrib.Syst.,Canada,2001,Vol.12,Issue10,pp.1023-1032.

[105]M.Chen,V.Leung,S.Mao,Y.Xiao,I.Chlamtac,“HybridGeograph-icalRoutingforFlexibleEnergy-DelayTrade-Offs,”IEEETrans.Veh.Technol.,2009,Vol.58,Issue9,pp.4976-4988.

[106]K.Sha,J.Du,W.Shi,“WEAR:ABalanced,Fault-Tolerant,Energy-AwareRoutingProtocolinWSNs,”SensorNetworks,2006,Vol.1,issue3,pp.156-168.

[107]K.Liu,N.Abu-Ghazaleh,“AlignedVirtualCoordinatesforGreedy

GeometricRoutinginWSNs,”SensorNetworks,2008,Vol.3,Issue4,pp.252-265.

[108]G.Wang,L.Zhang,J.Cao,“Hole-ShadowingRoutinginLarge-Scale

MANETs,”SensorNetworks,2008,Vol.4,Issue4,pp.220-229.[109]M.Chen,T.Kwon,S.Mao,V.Leung,“Spatial-TemporalRelation-BasedEnergy-EfficientReliableRoutingProtocolinWirelessSensorNetworks,”SensorNetworks,2009,Vol.5,Issue3,pp.129-141.[110]M.Al-Otaibi,H.Soliman,“EfficientGeographicRoutelessRouting

ProtocolswithEnhancedLocationUpdateMechanism,”SensorNet-works,2010,Vol.8,Issue4,pp.160-171.

[111]M.Chen,S.Gonzalez,V.Leung,“ApplicationsandDesignIssues

ofMobileAgentsinWirelessSensorNetworks,”IEEEWirelessCommun.,2007,Vol.14,Issue6,pp.20-26.

[112]M.Chen,S.Gonzalez,Y.Zhang,V.Leung,“Multi-agentItinerary

PlanninginWirelessSensorNetworks,”ComputerScience,2009,Vol.22,Issue10,pp.584-597.

[113]M.Chen,L.Yang,T.Kwon,L.Zhou,M.Jo,“ItineraryPlanningfor

Energy-efficientAgentCommunicationinWirelessSensorNetworks,”IEEETrans.Veh.Technol.,2011,Vol.60,Issue7,pp.1-8.

[114]M.Tarique,K.Tepe,S.Adibi,S.Erfani,“SurveyofMultipathRouting

ProtocolsforMobileAdHocNetworks,”NetworkandComputerApplications,2009,Vol.32,Issue6,pp.1125-1143.

[115]J.Raju,J.Garcia-Luna-Aceves,“ANewApproachtoon-Demand

Loop-freeMultipathRouting,”InProc.8thInternationalConferenceonComputerCommunicationsandNetworks,Boston,MA,1999,pp.522-527.

[116]X.Hou,D.Tipper,J.Kabara,“Label-basedMultipathRouting(LMR)

inWirelessSensorNetworks,”InProc.6thInternationalSymposiumonAdvancedRadioTechnologies(ISART),USA,Boulder,2004,pp.113-118.

[117]F.Ye,G.Zhong,S.Lu,L.Zhang,“GRAdientBroadcast:ARobust

DataDeliveryProtocolforLargeScaleSensorNetworks,”WirelessNetworks(WINET),2005,Vol.11,Issue3,pp.285-298.

[118]Y.Wang,C.Tsai,H.Mao,“HMRP:Hierarchy-BasedMultipathRout-ingProtocolforWirelessSensorNetworks,”ScienceandEngineering,2006,Vol.9,Issue3,pp.255-264.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.

PANTAZISetal.:ENERGY-EFFICIENTROUTINGPROTOCOLSINWIRELESSSENSORNETWORKS:ASURVEY

41

[119]J.Zhang,C.Jeong,G.Lee,H.Kim,“Cluster-BasedMulti-PathRout-ingAlgorithmforMulti-hopWirelessNetwork,”FutureGenerationCommunicationandNetworking,Korea,2007,Vol.1,Issue1,pp.67-75.

[120]M.Chen,V.Leung,S.Mao,Y.Yuan,“DirectionalGeographical

RoutingforReal-TimeVideoCommunicationsinWirelessSensorNetworks,”ComputerCommunications,2007,Vol.30,Issue17,pp.1-16.

[121]M.Chen,V.Leung,S.Mao,“DirectionalControlledFusioninWireless

SensorNetworks,”MobileNetworkApplication,2009,Vol.14,Issue2,pp.220-229.

[122]T.Winter,P.Thubert,A.Brandt,T.Clausen,J.Hui,R.Kelsey,

P.Levis,K.Pister,R.Struik,JP.Vasseur,”Internetdraft,http://tools.ietf.org/html/draft-ietf-roll-rpl-18,2011.

[123]H.Chao,C.Chang,“AFault-TolerantRoutingProtocolinWireless

SensorNetworks,”SensorNetworks,2008,Vol.2,Issue2,pp.66-73.[124]H.Soliman,M.Al-Otaibi,“EnhancingAODVRoutingProtocolover

MobileadhocSensorNetworks,”SensorNetworks,2011,Vol.10,Isuue2,pp.36-41.

[125]K.Akkaya,M.Younis,“EnergyandQoSRoutingforWirelessSensor

Networks,”ClusterComputing,2005,Vol.8,Issue2,pp.179-188.[126]G.Shafiullah,A.Agyei.P.Wolfs,“ASurveyofEnergy-Efficient

andQoS-AwareRoutingProtocolsforWirelessSensorNetworks,”Book:NovelAlgorithmsandTechniques,InTelecommunications,Au-tomationandIndustrialElectronics,2008,pp.352-357.

[127]K.Sohrabi,J.Gao,V.Ailawadhi,G.Pottie,“ProtocolsforSelf-OrganizationofaWirelessSensorNetwork,”IEEEPers.Commun.,1999,Vol.7,Issue5,pp.16-27.

[128]T.He,J.Stankovic,C.Lu,T.Abdelzaher,“SPEED:AStatelessProtocol

forReal-TimeCommunicationinSensorNetworks,”InProc.23rdInternationalConferenceonDistributedComputingSystems,Torodo,2003,pp.46-55.

[129]E.Felemban,C.Lee,E.Ekici,“MMSPEED:MultipathMulti-SPEED

ProtocolforQoSGuaranteeofReliabilityandTimelinessinWirelessSensorNetworks,”IEEETrans.MobileComputing,2006,Vol.5,Issue6,pp.738-754.

[130]M.Chen,M.Guizani,M.Jo,“MobileMultimediaSensorNetworks:

ArchitectureandRouting,”InProc.MobilityManagementintheNetworksoftheFutureWorld,Shanghai,2011,pp.409-412.

[131]J.Lian,K.Naik,“SkippingTechniqueinFaceRoutingforWireless

adhocandSensorNetworks,”SensorNetworks,2008,Vol.4,Issue1,pp.92-103.

[132]M.Chen,T.Kwon,S.Mao,Y.Yuan,V.Leung,“ReliableandEnergy-EfficientRoutingProtocolinDenseWirelessSensorNetworks,”SensorNetworks,2008,Vol.4,Issue1,pp.104-117.

[133]Y.Chen,N.Nasser,T.ElSalti,H.Zhang,“AMultipathQoSRouting

ProtocolinWirelessSensorNetworks,”SensorNetworks,2010,Vol.7,Issue4,pp.207-216.

[134]Y.Yang,M.Cardei,“Delay-ConstrainedEnergy-EfficientRoutingin

HeterogeneousWirelessSensorNetworks,”SensorNetworks,2010,Vol.7,Issue4,pp.236-247.

[135]M.B.Haider,S.Imahori,K.Sugihara,“SuccessGuaranteedRouting

inAlmostDelaunayPlanarnetsforWirelessSensorCommunication,”SensorNetworks,2011,Vol.9,Issue2,pp.69-75.NikolaosA.Pantazis[npantazis@teiath.gr]isanAssistantProfessorintheTechnologicalEducationalInstitution(TEI)ofAthens,DepartmentofElectronicsEngineering.Priortothat,hewasafulltimeLecturer,andtheheadoftheControlSystemsandComputerslaboratoryintheAdvancedSchoolofVocationalandTechnicalEducationTeachers(ASETEM/SELETE),DepartmentofElectronicsEngineering,Athens,Greece.Since2004hehasbeenaresearchassociateintheUniversityoftheAegean,DepartmentofInformationandCommunicationSystemsEngineering,andsince2008asamainresearcherinthedepartmentwhereheworks.HispresentresearchinterestsincludedesignandanalysisofPowerControlissuesandEnergyEfficiencyinWirelessSensorNetworksinconnectionwithroboticsandindustrialautomation.Heisanactiveparticipantinseveralresearchprojects,asamainresearcheroraresponsiblescientist,fundedbyEUandNationalAgencies.Hehasservedinmanytechnicalprogramcommitteesasamemberandpresident.Heistheauthoroftwentyseventechnicalbooksinthefieldofwirelesssensornetworks,industrialautomation,robotics,andcontrolsystems.Heistheco-authorofseveralarticlesinrefereedjournals,booksandconferenceproceedings.Heisalsoareviewerinseveralinternationaljournals.

StefanosA.Nikolidakis[snikol@unipi.gr]isaPhDcandidateintheUniversityofPiraeus,DepartmentofInformatics.HereceivedhisB.Eng.andM.Sc.fromtheUniversityoftheAegean,DepartmentofInformationandCommunicationSystemsinCommunicationandComputerNetworkingTechnologies.Hispresentresearchinterestsincludehealthcareservices,energyefficiency,reliability,resourceallocation,wirelesssensornetworks.

DimitriosD.Vergados[vergados@unipi.gr]isAss.ProfessorintheDe-partmentofInformatics,UniversityofPiraeus.HehasheldpositionasaLecturerintheDepartmentofInformatics,UniversityofPiraeusandintheDepartmentofInformationandCommunicationSystemsEngineering,UniversityoftheAegean.HereceivedhisB.Sc.fromtheUniversityofIoanninaandhisPh.D.fromtheNationalTechnicalUniversityofAthens,DepartmentofElectricalandComputerEngineering.HisresearchinterestsareintheareaofCommunicationNetworks(WirelessBroadbandNetworks,SensorNetworks,Ad-hocNetworks,WLANs,IMS,MeshNetworks),NeuralNetworks,CloudComputingandGreenTechnologies,andComputerVision.HehasparticipatedinseveralprojectsfundedbyEUandNationalAgenciesandhasseveralpublicationsinjournals,booksandconferenceproceedings.HehasservedasacommitteememberandevaluatorinNationalandInternationalOrganizationsandAgenciesandasachairandaTechnicalProgramCommitteememberinseveralinternationalconferences.

Heisamemberoftheeditorialboardandareviewerinseveraljournals.HeisanIEEESeniorMember.