Effect of overhearing transmissions on energy efficiency in dense sensor networks

inDenseSensorNetworks

BBNPrithwishTechnologies

Basu

10MoultonSt.,Cambridge,MA02138

pbasu@bbn.com

ABSTRACT

Energyefficiencyisanimportantdesigncriteriaforthede-velopmentofsensornetworkingprotocolsinvolvingdatadis-seminationandgathering.In-networkprocessingofsensordata,aggregation,transmissionpowercontrolinradios,andperiodiccyclingofnodewake-upschedulesaresometech-niquesthathavebeenproposedinthesensornetworkinglit-eratureforachievingenergyefficiency.Owingtothebroad-castnatureofthewirelesschannelmanynodesinthevicin-ityofasendernodemayoverhearitspackettransmissionseveniftheyarenottheintendedrecipientsofthesetrans-missions.Receptionofthesetransmissionscanresultinun-necessaryexpenditureofbatteryenergyoftherecipients.Inthispaper,weinvestigatetheimpactofoverhearingtrans-missionsontotalenergycostsduringdatagatheringanddisseminationandattempttominimizethemsystematically.Wemodeltheminimumenergydatagatheringproblemasadirectedminimumenergyspanningtreeproblemwheretheenergycostofeachedgeinthewirelessconnectivitygraphisaugmentedbytheoverhearingcostofthecorrespondingtransmission.Weobservethatindensesensornetworks,overhearingcostsconstituteasignificantfractionofthetotalenergycostandthatcomputingtheminimumspanningtreeontheaugmentedcostmetricresultsinenergysavings,es-peciallyinnetworkswithnon-uniformspatialnodedistribu-tion.Wealsostudytheimpactofthisnewmetriconthewellknownenergy-efficientdissemination(alsocalledbroadcast-ing)algorithmsformultihopwirelessnetworks.Weshowviasimulationthatthroughthisaugmentedcostmetric,gainsinenergyefficiencyof10%ormorearepossiblewithoutad-ditionalhardwareandminimaladditionalcomplexity.

CategoriesandSubjectDescriptors

C.2.1[Computer-CommunicationNetworks]:NetworkArchitectureandDesign—WirelessCommunication;G.2.2[MathematicsofComputing]:DiscreteMathematics—Graphalgorithms,Networkproblems

Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.

IPSN’04,April26–27,2004,Berkeley,California,USA.Copyright2004ACM1-58113-846-6/04/0004...$5.00.

BBNJasonTechnologies

Redi

10MoultonSt.,Cambridge,MA02138

redi@bbn.com

GeneralTerms

Algorithms,Performance

Keywords

Sensornetworks,energyefficiency,datagathering,datadis-semination/broadcast,overhearing

1.INTRODUCTION

Explosivegrowthinembeddedcomputingandrapidad-vancesinlowpowerwirelessnetworkingtechnologiesarefuelingthedevelopmentofwirelesssensornetworks.Thesedynamicandadaptivedistributedsystemshaveapplicationsrangingfrommonitoringwild-lifehabitats,inventoryman-agement,datacollection,andmilitaryandspaceapplica-tions.Sensornetworksarecomposedoflowpowersensornodescapableofsensingparticularphysicalphenomenaintheirvicinityandcommunicatingamongthemselvesusingwirelesstransceivers.Duetothelargenumberofnodes,theirlowcost,ortheamountoftimetheyareexpectedtobedeployedinapotentiallyinaccessiblearea1,energy-efficiencybecomesperhapsthemostimportantdesigncri-teriaforsensornetworkingprotocols.Amajorityofsensornetworkingapplicationsinvolvedatagatheringanddissemi-nation;henceenergyefficientmechanismsofprovidingtheseservicesbecomecritical.

Numerousresearchershaverecentlysuggestedavarietyofmechanismsforachievingenergy-efficiencyinsensornet-works,namely,in-networkprocessingofsensordata[7],ag-gregation[10],transmissionpowercontrolinradios,andpe-riodiccyclingofnodes’activityschedules[2].Typically,thetotalenergycostofatransmittedbitiscomputedtobethecostduetotransmissionoverawirelesschanneloveracertaindistanceplusthecostduetoreceptionbythedes-tinationradiohardware[8].However,duetothebroadcastnatureofthewirelesschannelmanynodesinthevicinityofasendernodeoverhearitspackettransmissionsevenifthosearenottheintendedrecipientsofthesetransmissions[14].Thisredundantreceptionresultsinunnecessaryexpenditureofbatteryenergyoftherecipients.Turningoffneighboringradiosduringacertainpoint-to-pointwirelesstransmissioncanmitigatethiscost[14,19].

Inthispaper,weinvestigatetheenergy-costimpactofoverhearingpackettransmissionsduringdatagatheringanddisseminationinsensornetworks.Wemodeltheminimumenergydatagatheringproblemasthatofcomputingadi-1

Thus,rechargingthesensorsmaynotbeanoption.

55555616Prim’s Algorithm

61Directed GraphOptimal In−arborescence

Figure1:Minimumcostin-arborescenceproblem:Weobservethatagreedyalgorithmissub-optimalondirectedgraphs.Intheabovefiguresweareconsideringthedatagatheringproblemwheretheleft-mostnodeineachsubfigureisgeneratingthegatheringtreefortheotherthreenodes.rectedminimumenergyrootedspanningarborescenceofawirelessnetworkwheretheenergycostofeachedgehasbeenaugmentedbytheoverhearingcostofthecorrespond-ingtransmission.Weobservethatindensesensornetworks,overhearingcostscanconstituteasignificantfractionofthetotalenergycostandthatcomputingthedirectedminimumspanningarborescenceontheaugmentedcostmetricresultsinenergysavings.Weobserveasimilarphenomenonforthedissemination(alsoknownasbroadcasting)scenario.

Therestofthepaperisorganizedasfollows:Section2in-troducestheenergymodelswellknowninliterature;Section3introducestheproblemofoverhearingtransmissions;Sec-tion4describesoptimalalgorithmsforcomputingrootedar-borescencesaswellasnear-optimalheuristicsforcomputingbroadcasttreesusingtheoverhearingcostmetric;Section5presentssimulationresultsofthedescribedalgorithms;Sec-tion5concludesthepaper.

propagationchannelandenvironmentalconditions.Etxelecistheenergyexpenditureinthetransmitterelectronics(perbit)and󰀃ampisaconstantthatischaracteristicoftheam-plifierinthetransmitter.Energyrequiredtoreceiveabitofdataatthereceiverisafunctionofthereceiverelectronicsandisgivenby:

(rcv)

=ErxelecEuv

(2)

Researchersroutinelyusetheaboveenergymodelformod-elingenergycostsofedgesinthenetworkgraph[8].

TheabilitytomodifytransmitpowerinsensorsprovidesapowerfultoolforminimizingenergyandisafeatureofnumerousnewsensorsystemssuchastheARLsensorra-dio[17]).Ifweconsiderarbitrarytransmissionpowercontrolinthismodel,everypairofnodesinthenetworkwillhaveanedgeconnectingthemandthetotalenergycostalongthatedgeduetobothtransmissionandreceptionwillbe:

Euv

(xmit)(rcv)

=Euv+Euv

=Etxelec+Erxelec+󰀃ampdαuv

2.PRELIMINARIES

Sensornetworkscanbeclassifiedinto2categories:(1)

query-drivenand(2)event-driven.Forthequery-drivencase,ausersubmitsaqueryfromabasestationnode(BS)whichgetspropagatedthroughthenetworkandsensorsthatcansatisfythequeryrespondtotheoriginatorbymeansofunicastcommunications.Incaseofanevent-drivensystem,eachsensorsendsdatatotheBSwheneveritdetectsacer-tainevent.Thistriggeredmechanismcanbethoughtofasaresponsetoalong-standingqueryaboutthatevent.SincesendingdataalongindividualunicastpathsfrommultiplesensorstotheBSisexpensiveintermsofenergyexpen-diture,researchershaveproposedmechanismstoaggregateupstreamdataasitpropagatesthroughthenetwork[10,20].Essentially,thesenseddataflowsbacktothebasesta-tionalongtheedgesofaspanningtreewhichisconstructedduringthequerydisseminationphase.Suchtreesarere-ferredtoasroutingtreesorgradients.Inthiscontext,theprincipalmechanismofenergyminimizationissuppressionofredundantdatapacketsinthenetwork.

AstaticsensornetworkcanberepresentedbyasetofnodesVwitheachsensornodepossessingageographicalpo-sitionattribute.Thetransmissionenergyrequiredtotrans-mitabitofdatafromnodeutovoverthewirelesschannelisdependentupontheRFpropagationpathlosssufferedoverthedistanceduvbetweenthem;itisgivenby:

(xmit)

=Etxelec+󰀃ampdαEuvuv

(3)

Notethattheenergycostsaresymmetricinthismodel,

inotherwords,Euv=Evu.Henceanenergyefficientmech-anismoftransmittingabitofdatafromallsensorstoabasestationnodeistosendandaggregatedataalongtheedgesofaminimumenergy-costspanningtreecalculatedontheentirenetworkgraph.Notethatthenetworkisrepresentedasacompletegraph(clique)undertheassumptionofarbi-trarypowercontrol.Ifthepeaktransmissionpowerisfixedandthetransmitterisallowedtotransmitatdiscretepowerlevelsonly,thentheresultinggraphmaynotbeacliquebuttheedgecostsareeasytoformulate.Oncethecostsareknown,theminimumenergyspanningtreescanbecalcu-latedusingKruskal’sorPrim’salgorithm[4]inO(elogn)time.Forcliques,acomplexityofO(n2)canbeachievedus-ingefficientpriorityqueuedatastructures.Eachleafnodeintheresultingspanningtreetransmitsitsdatasampletoitsparentwhichaggregatesthisdatawithitsownandthatofotherchildrennodesbeforetransmittingtheaggregateinturntoitsparentnode.Thisprocesscontinuesuntilthebasestationreceivesthecompletesetofaggregatesfromitschildren.

α≥2.0(1)

3.ENERGYEXPENDITUREDUETOOVER-HEARINGTRANSMISSIONS

Inthissectionwedemonstratethattheenergymodelpre-sentedinSection2isinadequatefordensesensornetworks.

Here,αisthepathlossexponentandisdependentonthe

57942035794203618

618

Figure2:MinimumEnergyDirectedSpanningTrees(node0isthebasestation):(a)withoutoverhearingcost;(b)withoverhearingcost.Thisnetworkhastheabilitytobefullyconnectedifnodesusetheirmaximumtransmitpower.

Whenacertainnodeutransmitsadatapacketfornodevus-ingoptimaltransmitpower,allnodesxsuchthatduxIntheenergymodelthatincorporatesoverhearing,thetotalenergyexpenditureduetoatransmissionfromnodeutovisgivenby:

Euv

=E(uvxmit)+E(uvrcv)+E(uv

ov)

=Etxelec+󰀃ampdαuv+Nuv(ov)

Erxelec,

(4)

whereNuv(ov)

isthenumberofnodeswithinthecommunicat-ingradiusofuwhenitcommunicateswithv.Thesearethe

setofnodeswhichoverhearthetransmissionofthepacketfromutov.)%300( gnira250ehrev200O ot e150ud tso100C ygre50nE ar0txE100150200100250300200500400Number of Sensor Nodes3001000900800700600Dimension of Sq. Area (m)Figure3:ExampleoftheadditionalenergycostduetooverhearingtransmissionsalongtheMini-mumEnergySpanningTree.SimulationparametersincludingenergycostsarethesameasthoseinTa-ble1andnodelocationsweregenerated(uniformly)randomly.

ItiseasytoseethatEuv=EvusinceNuv

(ov)

isnotnec-

2

entailTheperfectsolutionwithoutpointedeachtowardsnodeitshavingparentaindirectionalanoverhearingpenaltywillthespanningantennatree.

perfectlyessarilyequaltoNvu(ov)

.Thisresultsinadirectednetworkgraphwithasymmetricedgecosts,therefore,regularmini-mumcostspanningtreealgorithmsarenotapplicableinthisscenario.Aminimumcostspanningtreewillhavetobere-placedbyadirectedminimumcostarborescenceRrootedatthebasestationnodesuchthateachnodehasavaliddirectedpathtotherootusingtheedgesofR.Figure1illustratesasimpleexampleinwhichthegreedyPrim’sal-gorithmdoesnotyieldanoptimalrootedarborescence.Thisenergymodelofoverhearingassumesthatasensor’sreceivercircuitryisalwaysawakeandcanreceiveanddecodeallincomingpackets.Theenergycostofacompletepacketreceptionisgreaterthanthecostofremainingidle[14,9,19]3andiscompoundedbytheneedofthereceivertode-codetheentirepacketbeforedeterminingwhetheritistheintendedrecipient.Thiscanindeedbeanissueindensesen-sornetworkswhereapackettransmissioncanbeoverheardbyalargenumberofreceivers.Certainly,ifthereceiverpossessesamechanismofdecodingtheheaderofthepacketaloneandthenshuttingtheradiooffforabriefperiodifitisnotanintendedrecipient,thenadditionalenergysavingscanbeachieved.However,suchfinegrainedschedulingofreceiverelectronicscomesforahighpriceintermsofhard-warecomplexityandmayinducedelaysinprotocolprocess-ingathigherlayers.Weleavethisinvestigationforfutureresearch.Figure2illustratesascenariowheretennodesaresendingdatatowardsthebasestation(node0)andtheyareallcapa-bleofcontrollingtheirtransmissionpower;theintermediatenodesaggregatethedatabeforesendingitupstreamtowardsnode0.Figure2(a)showsthecasewheredataistransmittedalongadirectedMinimumEnergySpanningTreeorMEST.Whennode3forwardsapackettonode6,itstransmissionisoverheardbynodes5,7and9;thisresultsinunnecessaryenergyexpenditureatthelatternodeswhichcannotbepre-ventedaltogether.However,ifdataistransmittedalongadirectedMinimumOverhearingEnergySpanningTreeorMOESTshowninFigure2(b),thisunnecessaryexpendi-tureisminimized.Whilethereare8redundantoverhearingtransmissionsintheformercase,thereareonly5suchtrans-missionsinthelattercase.Theenergysavingsduetofeweroverhearingsinthisparticularnetworktopologyaregreaterthantheextratransmissionenergycost,hencetheMOESThasalowertotalenergyexpenditurethantheMEST.

Figure3plotstheextracostofoverhearingifdataisgath-3

hardware.

ExactTx:Rx:IdlepowerratiosvarydependingontheradioFigure4:MinimumEnergyDirectedBroadcastTreeswithWirelessMulticastAdvantageusingDifferentEnergyCostModels:(a)Txcostonly;(b)Txpluselectronicscost;(c)Txpluselectronicsplusoverhearingcost.Thetreesaremorebushyin(b)and(c)whenelectronicandreceiveenergycostsareincluded.eredfromaspecifiednumberofsensorstowardsabasesta-tionnodealongtheedgesofaminimumenergyspanningtree.Theadditionalcostisplottedasapercentageofthebaseenergycost.Theenergycostduetotransmissionelec-tronicsisincludedinbothcases.Weobservethattheover-hearingcostcanbeveryhigh(uptoapproximately300%greaterthanthebaseenergycostaccordingtoEquation3ignoringanyidlingenergycosts)indensenetworksforthenetworksizesplottedinthegraph.Hence,algorithmswhichcanminimizethisextracostarenecessary.Weproposesuchalgorithmsinthenextsection.

efficientimplementationofEdmond’sbranchingalgorithminmin{O(elogn),O(n2)}timeusingefficientpriorityqueueandsetunion/findprimitives[16].

WeimplementedTarjan’salgorithmandtriviallyadoptedittosolvetheminimumcostcaseinsteadofthemaximumcostcaseaswasdoneinboth[6]and[16].Thiswasdonebyreplacingoriginalcostsbytheirnegativevaluesandthenin-vokingthemaximumbranchingalgorithm.Sinceourgraphisstronglyconnected,itisguaranteedtohaveanarbores-cence(andnotjustabranching)andthentheabovestepworks.

Thesalientstepsofthealgorithmtofindthemax-costspanningin-arborescenceareoutlinedbelow.Wefirstre-versethedirectionsoftheedges,computeanout-arborescence(byTarjan’sscheme),andthenreversetheedgedirectionsagain.

1:ConstructcompletegraphG–theedgecostbetweeneverypairofnodesu,visafunctionoftheirpositionsasgivenbyEquation4.InitializesubgraphG(H)←(V,φ).2:Reversethedirectionsofalledgesandreplacethecostsbytheirnegativevalues.Removeallincomingedgesintorootnoder.

3:ChoosearootcomponentSinsubgraphG(H)4.

4:Selectthemax-weightedgee=(u,v)∈V×VincomingintoS.Ifu∈Sdiscardedgeeandgotostep3;otherwisegotostep5.

5:IfuandvdonotbelongtothesameweaklyconnectedcomponentofG(H),add(u,v)toHandgotostep3;otherwisegotostep6.

6:Findthesequence{Si,(xi,yi),...}ki=1ofstronglycon-nectedcomponentsSiandedges(xi,yi)∈H;yi∈Si,xi∈Si+1,Sk=S,(xk,yk)=(u,v),xk∈S1.Findmin-costedge(xj,yj)among(xi,yi).

7:Redefinethecostofunexaminededgesoftheform(x,y),y∈Siasfollows:

c(x,y):=c(x,y)−c(xi,yi)+c(xj,yj)

8:Add(u,v)toHthuscombiningSi’stoonestronglycon-nectedcomponent.IfallnodesinGhavebeenselected,IfSissuchthatnoedge(u1,u2)∈Hsatisfiesu2∈Sandu1∈V\\S,thenSisarootcomponentofG(H).

4

4.

ENERGY-EFFICIENTDATAGATHERINGANDDISSEMINATIONALGORITHMS

4.1DataGatheringProblem

Asmentionedintheprevioussection,theenergy-efficientdatagatheringproblemcanbeoptimallysolvedbycom-putingtheminimumcostarborescencerootedatthebasestationnode.Theproblemcanbeposedformallyasfollows–findarborescenceRthatsatisfiesthefollowing:•

(u,v)∈R

Euvisminimum;EuvisgivenbyEquation4.

•R=(V,E)isadirectedsubgraphofG=(V,V×V)withoutself-loopsandpossesses|V|−1edges.•Rhasexactlyonerootnoder(outdegree(r)=0)anditisconnected,i.e.,thereisexactlyonedirectedpathfromeachnodew∈V−{r}tor.•∀w∈V−{r}:outdegree(w)=1.

Thelasttwoconditionsimposeadditionalconstraintsonthecomputationofthedirectedspanningtreethatmaketheproblemdifferentfromtheregularminimumcostspanningtreeproblem.Edmondsproposedanefficientalgorithmforfindingoptimumbranching(rootedforests)withmaximumcostonarbitrarydirectedgraphs[6].Hepointedoutthatoptimalarborescences(rootedtrees)canbecomputedwithveryminormodificationstothebranchingsalgorithmifthedirectedgraphisstronglyconnected.Tarjanproposedan

gotostep9;otherwise,gotostep3.

9:FindtheshortestpathtreeTonHrootedatr.

10:ReversethedirectionsofedgesinTandrestoretheorigi-nalpositivecosts;Ristheresultantminimumcostgath-eringarborescence.

Weimplementedtheabovealgorithmusingefficientdatastructuressuchaspriorityqueuesassuggestedin[16];since

therearenedgesinG,thetimecomplexityisO(n2).Wesimulated2

theabovealgorithmforsensornetworksofvarioussizesatdifferentnodedensities;bothMESTandMOESTweresimulatedandtheresultsofcomparisonhavebeenpresentedinSection5.

4.2DataDisseminationProblem

Energy-efficientdatadisseminationinwirelessnetworkshasbeenahottopicofinterestintheresearchcommunityrecently[18,1].Theobjectiveistodevelopalgorithmsthatconsumetheminimumamountofenergyforbroadcastingabitofdatatoallnodesinthenetwork.Thebroadcasting(ordissemination)probleminwirelessnetworksisdifferentfromitspoint-to-pointwiredcounterpartbecausethewire-lesschannelhasinherentbroadcastcapability;henceanodecansendapackettoallitsneighborswithjustonebroad-cast.Wieselthieretal.coinedtheterm“wirelessmulti-castadvantage”(WMA)forthisphenomenon.In[18]theydevelopedenergy-efficientbroadcastingprotocolswhichex-ploittheWMA.

Cagaljetal.showedthatthewirelessbroadcast(ordis-semination)problemisNP-completeanddevelopedapprox-imationalgorithmsaswellasaheuristiccalledEWMA(Em-beddedWMA)[1]whosesalientstepsareoutlinedbelow:1:Constructafeasiblesolutionforbroadcast.e.g.,westartwithaMinimumEnergySpanningtreeasaninitialbroadcasttree.

2:Exchangesomeedgesofthistreewithnewedgesinor-dertosystematicallyreducethetotalenergycost.Thisreductionisreferredtoasgain.Attheexpenseofin-creaseinacertainnodev’stransmissionenergy,signif-icantgaincanbeachievedbyexcludingseveralnodesfromthebroadcasttree.Inthisstep,onehastoensurethatthenodevshouldbeabletoreachnodeswhichwerepreviouslyreachableonlythroughasubsetoftheexcludednodesinthebroadcasttree.

3:Iteratethepreviousstepuntilnonodescanbeexcludedfromthebroadcasttreeandallnodesinthenetworkarecovered.

Inthissectionweinvestigatehowoverhearingenergycostmodelsaffectthetotalenergysavings.Figure4illustratestheeffectofusingdifferentenergycostmodelsonthestruc-tureofthebroadcasttreegeneratedbyEWMA.Thein-clusionofthetransmissionelectronicscost(Etxelec)causesEWMAtoreducethenumberoftransmittingnodessincealargenumberoftransmissionsisdeemedexpensiveinthismodel.Thisresultsinsomenodeshavingtoincreasetheirtransmissionpowerandcovertheexcludednodes,andhencegivingthetreeabushyappearance.

Whentheoverhearingcostisincludedintheenergymodel,weobservethatthetreeisbushierneartherootnodebutlesssoatforwardingnodesatlowerlevels.Thereasonbe-hindthisisintuitivelyclear:havinganumberoflowdegreeforwardingnodesatlowerlevelsofthetreeresultsinlesserexpenditureofenergyduetooverhearingthanifthefor-wardingnodesatalllevelshavesimilardegree(whichisthe

TableParameter1:SimulationValue

Parameters

Ptxelec50mWPrxelec50mW

B(datarate)1Mbps

EtxelecPtxelec

=50nJ/bitErxelecPrxelec

B

=50P(Rxsensitivity)−72B

nJ/bitrxthreshdBm

h(antennaheight)1.5mν(frequencyband)916MHzλ(RFwavelength)c/ν

eamp(α=2)16π2Prxthresh

J/bit/e(α=4)Bλ2

m2

ampPrxthresh

BhJ/bit/m4

dxover(crossover)4πh

24λ≈86mcaseforFigure4(b)).Thisnon-uniformdegreestructurefor

caseinFigure4(c)minimizestheredundancyofoverhear-ingatothernodes.WeshowbysimulationsinSection5thatthetotalenergycostcanbeminimizedbyincorporat-ingoverhearingcostintotheenergymodel.

4.3Discussion

Sinceidlelisteningonawirelesschannelisasignificantsourceofenergyconsumption,researchershaveproposedamultitudeofschemesformitigatingthisproblem.Pream-blesampling[5],PAMAS[14]andwake-on-wireless[13]arerepresentativeofsuchschemes.Inthefirstscheme,asen-sornodegoesinto5fine-grainedperiodsofsleepandwakesupperiodicallytosamplethechannel,anditkeepsawakeifitseesapreambletransmittedbythesender.There-ceivermaystillincurtheoverhearingenergycostsinceithastodecodetheentirepacketbeforeascertainingwhetheritindeedisanintendedrecipientofthetransmission.BothPAMASandwake-on-wirelessschemesadvocatethesepara-tionofsignalinganddatachannelstoachievegreaterpowerefficiency.

Inwake-on-wireless,alow-powerradiothatconsumesonly2mWofpowerlistenstoincomingtransmissionsandwakesupthemainradiowhenitdetectsavalidincomingpacket.Althoughthistechniquemitigatestheoverhearingcostinpoint-to-pointtransmissions(asinthedatagatheringcase),itmaynotbeabletodosointhenetwork-widedatadissemi-nationscenario6Arguably,moresophisticatedprotocolscanbedevelopedthatcansaveenergyinthissituation,butweleavethatforfutureinvestigation.

Whileminimizingtotalenergyisalwaysadesirablegoalinthedatadisseminationapplication,thechoiceofthebroad-casttransmissionstrategyshouldbemadeonlyafterevalu-atingallthetrade-offsappropriately.Forexample,ifrelia-bilityinbroadcastismoredesirablethantotalenergysav-ings,asparsetreecanbemoresuitablethanabushyone.Weleavethestudyofsuchtrade-offforfutureresearch.Wenotethatthesealgorithmsrequireknowledgeofthestateofalllinksinthenetwork.Suchalgorithmscanbeimplementedwithoutmodificationinnetworksthatusedis-5

10The6

sinradioeveryis100turneds.onfor30µsinevery300µsinsteadofuponTheredundantthelow-powerarrivalradiowillalwayswakeupthemainradiofromaofdisseminationabroadcastpacketstandpoint.

evenifthatpacketisN = 200x 10−5N = 200x 10−51.1EnergyOverhear (J/bit) (J/bit)43.532.560MEST1Energy0.960504030#Clusters20101004007001000504030Dimension#Clusters20101004007001000DimensionFigure5:TotalEnergyvs.DegreeofClusteringandArea:(a)CostofthegatheringtreeMESTwithoutoverhearingcost;(b)CostofoverhearingalongedgesofMEST(Clusterradius=20m)kthenetworkishighlynon-uniformbutaskapproachesN,thenon-uniformityvanishes.Figure5plotsthevariationinthetotalcostofMESTwithareaandclusteringforN=200.Bothbaseandover-hearingcostsareplotted.Weobservethattheincreaseinareaismoregradualforhighkthanforlowvaluesofk(highdegreeofclustering).Atlowk,thedistancebetweenclus-tersincreasesmorerapidlywithincreaseinareaandthepropagationcostalongedgesconnectingtheclustersstartsdominating.Whenthenetworkisverydense(200nodesina0.01km2area),radioelectronicstendtodominatetheenergycostandhencecost(MEST)isunaffectedbyavariationink.Howeverwhentheareaisincreased,thecostofedgescon-nectingthekclusterstendstodominatetheelectronicscost.Itisknownthatthecostoftheminimumspanningtreeofrandomgraphswithpower-weightededges7diminishesasNincreases[15].Hence,askincreasesthesumofcostsofthelongedgesconnectingthekclustersdecreasesandthuscost(MEST)decreasesaswell8.Forsimilarreasonsweob-servethattheoverhearingcostincreaseswithbothareaanddegreeofclustering.

InFigure6wecomparethetotalenergyexpenditure(trans-mission,electronicsandoverhearingreception)duetoMESTandMOEST.Representativeresultsfor500×500,600×600,and700×700areashavebeenshown.WeobservethatMOESToutperformsMESTinthismetricinallscenarios.Gainsuptoalmost10%areobserved.Whilethismaynotbeaverylargevalue,itisnotinsignificantforlowpowersensornetworkswhichneedtooperateaslongaspossible.ForallN,theabsolutegains(notrelativegains)ofMOESToverMESTaremaximumforlowkanddiminishgraduallyaskincreases.Thisisbecausethereisagreaterdegreeofoverhearingforhighlyclusterednetworksandhenceitpaystoconsiderthatintothecostmodel.

FromFigure7weobservethatthesourcetosinkpathlengthsarenotaffectedmuchbyincorporatingoverhear-ingcostinthecostmodel.Infact,onseveraloccasions(lowk),MOESTgivesshorteraveragepathlengthsthanMEST.Thismeansthattheaggregatedpacketswillnotsuf-Thisreferstothecasewheretheedgecostisoftheformofrβwhereristheeuclideanlengthoftheedgeandβisaquantitygreaterthan1.8

Thisisbecausethecostofedgesconnectingthekclustersdominatesthetotalcost.

7

Table2:OverhearingEnergyCostsforDataGath-eringinRandomTopologies(nodesuniformlydis-tributedina0.25km2area;costinJ/bit)NCost(MEST)Cost(MOEST)%Gain500.66288×10−50.64324×10−52.96−5−51001.34579×101.29657×103.66−5−52002.71298×102.61901×103.46−5−53004.07797×103.92669×103.71−5−54005.4402×105.24448×103.60tributeddatabasesoftopologyinformationsuchaslinkstatestyleprotocols[3,11],orcanbeimplementedwithmod-ificationandsomelossofperformanceinprotocolswhichdistributemorelimitedsetsofnetworkinformationsuchasHSLS[12].

5.SIMULATIONRESULTS

Wesimulatedtheoptimalminimumenergyspanningtreealgorithmfortwodimensionalsensornetworks.TheradioparametersusedforsimulationhavebeenlistedinTable1(mostparametershavebeentakenfrom[8]).

5.1DataGatheringResults

First,wepresentsimulationresultsforthedatagather-ingproblem.WesimulatedTarjan’salgorithmforenergymodelsbothwithandwithoutoverhearingcost.Webeganourinvestigationwithrandomly(2Duniformdistribution)distributedtopologies.Table2presentsasnapshotoftheresults.Thecostspresentedthereincorrespondtothetotalenergyexpenditure(transmission,electronicsandoverhear-ingreception)forMESTandMOESTstyletreeconstruc-tion.Whiletheformermethodignorestheoverhearingcostduringtreecalculation,thelatterfactorsthatin.Weob-servethatthegainsaremodest(lessthan4%)intheuni-formdensitycaseforseveralvaluesofN.Hencewedecidedtoinvestigatewhetherthegainsarehigherfornon-uniformnetworktopologies.

Wesimulatednon-uniformtopologiesinthefollowingman-ner:firstkpointsaregeneratedwithcoordinatesdrawnfromauniformdistribution;thesepointscorrespondtothekclustersinthenetworkandanumberofpoints(totalofN)arerandomlygeneratedwithinacertainradiusoftheseclustercenters(20m,inoursimulations).Forlowvaluesof

2Total Energy (J/bit)1.8x 10−5N=1004x 10−5N=20065.5x 10−5N=300MEST: X=500mMOEST: X=500mMEST: X=600mMOEST: X=600mMEST: X=700mMOEST: X=700m3.51.61.4354.5102030405060Number of clusters102030405060Number of clusters102030405060Number of clustersFigure6:SimulationResultsforClusteredTopologies:TotalEnergyConsumptionvs.NumberofClusters:Linesexistinpairsforeachareaandtheycorrespondtothemanneroftreeconstructionfordatagathering.TheY-axishowever,representsthetotalenergyconsumedintheoverhearingenergycostmodelforeachofthesetrees.fergreaterdelaysifonedecidestoincludeoverhearingcostintotheenergyequation.4540N = 3003530N = 200MEST: X=500mMOEST: X=500mMEST: X=600mMOEST: X=600mMEST: X=700mMOEST: X=700m2520N = 1001510102030405060Number of clustersFigure7:SimulationResultsforClusteredTopolo-gies:AverageHopCountsforMinimumEnergySpanningTrees.Theaveragesourcetosinkpathlengthsarenotaffectedmuchbythecostmodel.

5.2DataDisseminationResults

Herewepresentthesimulationresultsfortheenergy-efficientdatabroadcastalgorithmduetoCagaljetal.[1]asmentionedinSection4.2.Arandom(uniform)distributionofnodeswasassumedinbothdenseandsparsetopologies.InFigure8wesimulateandplotthetotalenergyconsumedtobroadcastabitofdatafor3differentenergycostmodelsforN=100,200,300.Weobservethatgraphsforallthesecostmodelsarewavyingeneralshape,i.e.theyhaveregimesofsharpincreasefollowedbygentleincreaseandthensharpincreaseagain.Forthedensestnetworks(dimensionaround100m)theelectronicscostdominatestheenergyequationandthedepthofthebroadcasttreeis1forenergymodels

2and3;hencethecurvesaremostlyflat.Asthenetworkgetsslightlysparser(dimensionbetween500mand1000m,thedepthoftheEWMAincreasestoafewhopsandthatresultsinasharpincreaseinenergycostsofmodels2and3.Thisistheregimewhereoverhearingstartstobecomeamajorfactor.Asthenetworkbecomessparser(dimensionbetween1000mand3000m),electronicsandoverhearingcostsarecompara-bletothepropagationenergycostsandthetreesarelessbushier.Henceaslightincreaseinareadoesnotresultinasignificantincreaseinenergy.Howeverthereisasharpin-creaseincostsasthenetworkbecomesverysparse(3000m-5000m)becausethepropagationcostisthedominantfactorinthatregime,nottheelectronicsoroverhearingcost.Thebroadcasttreesarenotatallbushyforsuchsparsenetworks.Thegainsofusingelectronicsandoverhearingcostmod-elsaremaximumfordensenetworksandtheseincreaseinabsolutevalueasNisincreased.Thisisbecausefordensenetworks,allnodescanbe“covered”withonlyafewbroad-casts.SeeFigure10showshowthenumberofforwardingnodesincreaseswiththeareaineachcase.ThegainsofusingtheoverhearingcostmodelovertheothertwomodelswhichdonotcapturethatcostcanbeseeninFigures8and9.Thehighestpercentagegainscanbeob-servedaroundthe1km2region.Weseethatincorporatingoverhearingaswellaselectronicscostintotheenergyequa-tioncansaveasmuchas45%energyinthoseregimes.Wealsoobservethatenergymodel3(overhearingcost)yieldsgainsofover10%aboveenergymodel2indensenetworks(N=300;dimensionaround1000m).

Theseenergygainscomeinattheexpenseofothermet-rics.Thetreesarelikelytobeverybushyandthuslessreliableandtheburdenofforwardingthepacketissharedbyonlyasmallfractionofthenodes(seeFigure10).Itisthedutyofthesystemdesignertoanalyzetherequirementsofthetaskandbalancethesetrade-offs.

Mean #hops (src−>sink)Acknowledgments

ThispaperwaspreparedthroughcollaborativeparticipationintheCommunicationsandNetworksConsortiumspon-soredbytheU.S.ArmyResearchLaboratoryundertheCol-

65 (J/bit)x 10−5N=1005Ebroadcast (J/bit)432x 10−5N=2005 (J/bit)432x 10−5N=3004321010010003000Dimension (m)broadcastE5000110010003000Dimension (m)EbroadcastTx cost onlyTx+Elec costTx+Elec+Overhear5000110010003000Dimension (m)5000Figure8:EffectofOverhearingTransmissiononDisseminationAlgorithms:Eachofthe3linesineverysubplotrepresentstheparticularmannerofconstructionofthebroadcasttreealthoughtheY-axisrepresentsthetotalenergyconsumedintheoverhearingenergycostmodelalone.WecanobservethatthegainsofusingtheoverhearingenergycostmodelfortreeconstructionimproveasNincreases.ForeachNthegainsoverthe“transmissioncostonly”modelaremaximumforthedensestscenarios.Overhearing model vs. Tx only model5040% energy gain3020100N=100N=200N=300% energy gain121086420100020003000Dimension (m)4000500000Overhearing model vs. Tx+Elec modelN=100N=200N=300100020003000Dimension (m)40005000Figure9:EnergyGainduetouseoftheOverhearingCostModel:(a)Gainsovertransmissioncostmodel;(b)GainsovertransmissionandelectronicscostmodelN=10080#forwarding nodes#forwarding nodes604020010010003000Dimension (m)150N=200250#forwarding nodes20015010050N=300100Tx cost onlyTx+Elec costTx+Elec+Overhear505000010010003000Dimension (m)5000010010003000Dimension (m)5000Figure10:NumberofNodesForwardingPacketsintheBroadcastTree:Muchlessernumberofnodesparticipateinforwardingbroadcastpacketsifelectronicsand/oroverhearingcostisincludedinthemodel.Thereareafewmoreforwardingnodesintheoverhearingcostmodelthanintheelectronicscostmodel.laborativeTechnologyAllianceProgram,CooperativeAgree-mentDAAD19-01-2-0011.TheU.S.Governmentisautho-rizedtoreproduceanddistributereprintsforGovernmentpurposesnotwithstandinganycopyrightnotationthereon.WealsothankMarioCagaljforprovidingthesourcecodefortheEWMAheuristic.

6.CONCLUSIONSANDFUTUREWORK

Inthispaperweshowedthatindensesensornetworks,packetoverhearingatreceiversbeasignificantadditionalen-ergyexpenditureduringdatagatheringanddissemination.Wearguedthatoverhearingcostshouldbeincorporatedintotheenergyequationwhilecalculatingthebestdatagather-ingandbroadcasttrees.WealsoshowedthattraditionalminimumenergyspanningtreesareinadequateduetotheasymmetricnatureoftheoverhearingcostandwedescribedbrieflyhowTarjan’sminimumbranching/arborescencealgo-rithmcanbeutilizedtodothejob.Wedemonstratedbysimulationsthatincorporatingoverhearingcostintotheen-ergymodelcanresultincloseto10%energysavingsinbothdatagatheringandbroadcastscenarios.

Infuture,weplantoinvestigatetheimpactofoverhear-ingondatadisseminationandgatheringapplicationsundermorecomplexanddetailedenergymodelsandchannelac-cessschemes,especiallytheonesinvolvingintelligentcyclingoflow-powersensorradiostosaveenergy.

7.REFERENCES

[1]M.Cagalj,J.-P.Hubaux,andC.Enz.

“Energy-efficientBroadcastinginAll-wireless

Networks”.ACM/KluwerJournalofMobileNetworksandApplications(MONET).Toappear.[2]I.Chlamtac,C.Petrioli,andJ.Redi.

“Energy-conservingAccessProtocolsforIdentificationNetworks”.IEEETransactionsonNetworking,7(1):51–59,February1999.

[3]T.ClausenandP.Jacquet.OptimizedLinkState

RoutingProtocol(OLSR).RFC3626(Experimental),October2003.

http://www.ietf.org/rfc/rfc3626.txt.

[4]T.H.Cormen,C.E.Leiserson,andR.L.Rivest.

IntroductiontoAlgorithms.MITPressandMcGraw-Hill,1990.

[5]D.Culler,J.Hill,P.Buonadonna,R.Szewczyk,and

A.Woo.ANetwork-CentricApproachtoEmbeddedSoftwareforTinyDevices.TechnicalReportIRB-TR-01-001,Intel-Research,Berkeley,CA,January2001.

[6]J.Edmonds.“OptimumBranchings”.Journalof

ResearchofTheNationalBureauofStandards,71B:233–240,1967.

[7]D.Estrin,R.Govindan,J.Heidemann,andS.Kumar.

“NextCenturyChallenges:ScalableCoordinationinSensorNetworks”.InProc.InternationalConferenceonMobileComputingandNetworking(MobiCom),Seattle,WA,August1999.

[8]W.Heinzelman,A.Chandrakasan,and

H.Balakrishnan.“Energy-EfficientCommunicationProtocolsforWirelessMicrosensorNetworks”.InHawaaianInternationalConferenceonSystemsScience(HICSS),Hawaii,January2000.

[9]O.Kasten.Energyconsumption.URL.

http://www.inf.ethz.ch/~kasten/research/bathtub/energy_consumption.html%.

[10]S.Madden,M.J.Franklin,J.M.Hellerstein,and

W.Hong.“TAG:aTinyAGgregationServiceforAd-HocSensorNetworks”.InProc.SymposiumonOperatingSystemsDesignandImplementation(OSDI),December2002.

[11]R.Ogier,F.Templin,andM.Lewis.Topology

DisseminationBasedonReverse-PathForwarding(TBRPF).RFC3684(Experimental),February2004.http://www.ietf.org/rfc/rfc3684.txt.

[12]C.Santivanez,S.Ramanathan,andI.Stavrakakis.

“MakingLinkStateRoutingScaleforAdHoc

Networks”.InProc.ACMMobiHoc,LongBeach,CA,October2001.

[13]E.Shih,PBahl,andM.J.Sinclair.WakeonWireless:

AnEventDrivenEnergySavingStrategyforBatteryOperatedDevices.InProc.InternationalConferenceonMobileComputingandNetworking(MobiCom),Atlanta,GA,September2002.

[14]S.SinghandC.S.Raghavendra.PAMAS–Power

awaremulti-accessprotocolwithsignallingforadhocnetworks.ACMSIGCOMMComputer

CommunicationReview,28(3):5–26,July1998.[15]J.M.Steele.“GrowthRatesofEuclideanMinimal

SpanningTreeswithPowerWeightedEdges”.TheAnnalsofProbability,16(4):1767–1787,1988.

[16]R.Tarjan.“FindingOptimalBranchings”.Networks,

7(1):25–35,Spring1977.

[17]R.Tobin.“USArmy’sBLUERadio”.InProc.SPIE,

UnattendedGroundSensorTechnologiesand

ApplicationsV,volume5090,Orlando,Florida,April2003.

[18]J.E.Wieselthier,G.D.Nguyen,andA.Ephremides.

“OntheConstructionofEnergy-effcientBroadcastandMulticastTreesinWirelessNetworks”.InProc.IEEEINFOCOM,pages585–594,TelAviv,Israel,March2000.

[19]W.Ye,J.Heidemann,andD.Estrin.“An

Energy-EfficientMACProtocolforWirelessSensorNetworks”.InProc.IEEEInfocom,NewYork,June2002.

[20]J.Zhao,R.Govindan,andD.Estrin.“Computing

AggregatesforMonitoringWirelessSensorNetworks”.InProc.IEEEInternationalWorkshoponSensorNetworkProtocolsandApplications,Anchorage,AK,May2003.