necessarilynetlife

M.
Crovellaetal.
(Eds.
):NETWORKING2010,LNCS6091,pp.
277–290,2010.
IFIPInternationalFederationforInformationProcessingResourceOptimizationAlgorithmforSparseTime-DrivenSensorNetworksMaríaLuisaSantamaría,SebastiàGalmés,andRamonPuigjanerDept.
ofMathematicsandComputerScience,UniversitatdelesIllesBalearsCra.
deValldemossa,km.
7.
5,07122Palma,Spain{maria-luisa.
santamaria,sebastia.
galmes,putxi}@uib.
esAbstract.
Time-drivensensornetworksaredevotedtothecontinuousreportingofdatatotheuser.
Typically,theirtopologyisthatofadata-gatheringtreerootedatthesink,whosevertexescorrespondtonodeslocatedatsamplingloca-tionsthathavebeenselectedaccordingtouserorapplicationrequirements.
Thus,generallytheselocationsarenotclosetoeachotherandtheresultingnodedeploymentisrathersparse.
Inapreviouspaper,wedevelopedaheuristicalgorithmbasedonsimulatedannealingcapableoffindinganoptimalorsubop-timaldata-gatheringtreeintermsoflifetimeexpectancy.
However,despitetheenhancedlifetime,theoveralllinkdistanceisnotoptimized,factthatincreasestheneedforadditionalresources(relaynodes).
Therefore,inthispaperwepro-posetheLinkDistanceReductionalgorithm,withthegoalofreducinglinkdistancesaslongasnetworklifetimeispreserved.
Thebenefitsofthisnewalgorithmareevaluatedindetail.
Keywords:Time-drivensensornetworks,TDMA,spanningtree,minimumspanningtree,networkplanning.
1IntroductionIntime-drivenorcontinuousmonitoringsensornetworks,communicationistriggeredbynodes,whichregularlydeliversenseddatatotheuser[1].
Thus,thetrafficgener-atedbythesenetworksusuallytakestheformofacontinuousandpredictableflow,andthereforetheuseofaTDMA-basedprotocolbecomesespeciallyappropriate[2].
Furthermore,itiscommonthattime-drivensensornetworksaredeployedinastruc-turedmanner[1][2],eitherbyselectingstrategiclocationsorbyadoptingsomeregularsamplingpattern,andthatdataareroutedtothesinkthroughmulti-hopprede-terminedpaths[1].
Thesepathsformareversemulticastorconvergecaststructurecalledthedata-gatheringtree[2].
Becausethestrategiclocationscanwellbefartoeachotherorbecausethemoni-toredvariablecanexhibitlowspatialvariability(asitisusuallythecase),itisnotsurprisingthattheresultingapplication-drivendeploymentisrathersparse.
Sparsemanually-deployedsensornetworkshavereceivedlessattentioninliterature(incon-trasttodenseandrandomly-deployednetworks),inspiteofputtingforwardsomeinterestingchallenges.
Inessence,thesecomefromthefactthatlargeinter-nodedistancescanbeimpracticalorunattainableforsensornodes.
Inevitably,giventhe278M.
L.
Santamaría,S.
Galmés,andR.
Puigjanerlimitedcommunicationrangeofnodes,anysolutiondemandstheintroductionofadditionalresources,basicallyintheformofrelaynodes(nodeswiththeirsensingcapabilitydeactivated).
Thiscouldbedonebyrandomlyscatteringthemoverthewholesensorfield,butthiswouldyieldtoprohibitivelylargeamountsofnodespreciselyinsparseareas.
Thus,wesuggestthattheproblemcanbebetteraddressedfromanetworkplanningperspective,whichtriestocontrolthenumberofadditionalresourcesaslongasthefunctionalityandlifetimeofthenetworkarepreserved.
Aspartofthisstrategy,in[3]wedevelopedaheuristicmethodbasedonsimulatedannealing(SA)thatfindsanoptimal(orsuboptimal)data-gatheringtreeintermsoflifetimeexpectancy.
However,ingeneraltheoveralllinkdistanceofthistreecanbesubstantiallyimproved(decreased),factthatwouldcontributetoreducetheamountofrelaynodesrequiredtomakethenetworkoperational.
Thus,inthispaperweproposetheLinkDistanceReduction(LDR)algorithm,whichstartsfromthedata-gatheringtreedeliveredbytheSA-basedalgorithm,andthenprogressivelyreducesitsoveralllinkdistanceaslongasthelifetimeobtainedfromSAisnotdecreased.
Accordingly,therestofthepaperisorganizedasfollows.
InSection2,wedescribeournetworkplanningapproachtotheproblemoftopologyconstructionforsparsedeployments,alongwithrelatedwork.
InSection3,wemotivatetheneedforanalgo-rithmthatreducesthesumoflinkdistancesoftheSAgraph.
InSection4,wedescribethenewalgorithm(LDR)indetail.
Then,inSection5,weevaluateitsperformanceviasimulation.
Thisalsoincludestheissueofcomputationalcomplexity.
Finally,inSection6,wedrawthemainconclusionsandsuggestionsforfurtherresearch.
2NetworkPlanningApproachandRelatedWorkTheproblemofconstructingadata-gatheringtreecanbefacedupfromanetworkplanningperspectiveoraspartofaprotocol-orienteddesign.
Inthelattercase,areal-timedistributedalgorithmisdesigned,inordertobeembeddedintoanadaptiverout-ingprotocolcapableofsupportingfrequenttopologyupdates.
Thisstrategyhasbeentypicallyusedindense,randomly-deployednetworks.
Incontrast,intheformercase,thegoalistofindanoptimizedstaticroutingtree,andthusthealgorithmtobede-signedisnotsubjecttoreal-timerequirements(althoughcomputationtimeisstillofconcern)andcanbeexecutedcentrally.
Thisapproachbecomesespeciallyappropriateforsparsely-deployedsensornetworksorforsensornetworkswheremaintainingandupdatingaroutingtableateachnodeiscomputationallytooexpensive.
Despiteitsimportance,thenetworkplanningapproachhasreceivedlessattentionthantheapproachcenteredonadaptiverouting.
Yet,someworksdeserveadescription.
Forinstance,theworkpresentedin[4]considerstheproblemofdesigningadata-gatheringtreewiththegoalofreducingthetotalamountofdatatransmitted.
Hence,incontrasttoourpremises(seeSection3),itsmainfocusisonapacketaggregationscheme.
Analogously,theemphasisof[5]isalsoonpacketaggregation.
Acommonfeaturetotheseworks,asstatedby[6],isthattheirultimategoalistominimizethetotalenergyconsumption,thusignoringthefactthatsomenodesmaydepletetheirenergyfasterthanothersandcauselossofcoverage.
Thus,thealgorithmproposedin[6]focusesonmaximizingthelifetimeofthenetwork,definedasthetimeuntilfirstnodedeath(optimizationwithstrictcoveragerequirements).
However,thisworkadoptsseveralassumptionsthatsignificantlysimplifytheanalysisoftheproblem.
OneResourceOptimizationAlgorithmforSparseTime-DrivenSensorNetworks279ofthemisthatnodescannotadjusttheirtransmissionpower,whichisnotalwaysthecase.
Thisassumptioneliminatesthedependenceondistanceandthusitreducesthecomplexityoftheproposedalgorithm.
Anothersimplifyingassumptionistheadoptionofapacketaggregationschemethatreducesthenumberofpacketstobeforwardedbyanodetothenumberofdirectdescendentsithas.
Comparedtothiswork,ourparticu-larapproachadoptsthesamedefinitionoflifetime,butitusesamorecompleteenergyconsumptionmodelthatdoesnotrelyontheabovementionedassumptions.
Anothersimplificationpresentin[6]istheassumptionthattheinitialnetworkisfullyconnected.
Sincethisisnotnecessarilytrue,especiallyinsparsedeployments,thenetworkplanningperspectivehasalsoconsideredthepossibilitytointroduceadditionalresourcesinthenetwork,intheformofrelaynodes.
Inthiscontext,severalworksassumethatnodeshaveamaximumtransmissionrange,andthenformulatetheproblemofintroducingthefewestnumberofrelaynodessothatacertaindegreeofnetworkconnectivityisachieved.
Examplesoftheseworksare[7]and[8],whichconsiderflattopologies,and[9]and[10],whichassumeatwo-tieredarchitecturewhererelaynodesalwaysbelongtothebackbonenetwork.
Essentially,thetheoreticalformulationofthesetopologicalproblemsisthatofaSteinertreewithminimumnum-berofSteinerpoints(ST-MSP),aproblemthatisknowntobeNP-hard.
However,asstatedabove,thefocusoftheseworksisonnetworkconnectivityratherthanonlife-time(atmost,lifetimeispartiallyaddressedbyconsideringtransmissionrangesandtheso-callednodedegrees).
Bycontrast,ournetworkplanningapproachaddressesbothnetworklifetimeandminimizationofthenumberofSteinerpoints(resourceoptimization)bymeansofthefollowingtwostages:Elementarytreeconstruction.
Theconstructionofanelementarydata-gatheringtreeconsistsofdeterminingaspanningtreethatconnectsallregularordutynodes(nodesatlocationsofinterest)tothesink,withaviewtomaximizingthelifetimeofthesensornetwork.
Inthisprocess,weassumethatthesenodeshavefullpowercontrolcapabilitywiththeonlylimitoftheirownenergyresources(battery).
Inotherwords,thelikelyexistenceofamaximumtransmissionrangeisignoredatthisstage.
Underthisassumption,theworkpresentedin[3]showedthattheprob-lemoffindingadata-gatheringtreewithoptimallifetime,byincludingintheanalysistheworkloadofeverynodetoamaximumextent,isNP-hard.
Then,aheuristicmethodbasedonsimulatedannealingwasproposed,whichitwasshowntoyield,ingeneral,aspanningtreewithnear-optimallifetimeinlineartime.
Placementofadditionalnodes.
Inthecaseofsparsedeployments,thedata-gatheringtreethatresultsfromthepreviousstageusuallycontainslinkdistancesthatexceedsomemaximumtransmissionrange.
Inthiscase,ourstrategyconsistsofregularlyinsertingthenecessarynumberofrelaynodesintotheuplinkofeveryregularnode.
Thisisthetechniqueofsteinerizededges,whichwasalsoconsideredin[7],[8],[10]and[11].
Inthelatter,thenumberofinsertednodeswasrelatedtothecorrespondinglifetimeenhancement.
3ProblemMotivationTheworkpresentedinthispaperishalfwaybetweenthetwostagesofthetopologyconstructionprocessdescribedintheprevioussection.
Thereasonisthatalthoughthe280M.
L.
Santamaría,S.
Galmés,andR.
PuigjanerSA-basedalgorithmgeneratesaspanningtreewithoptimalorsuboptimallifetime,ingeneralthesumoftheresultinglinkdistancescanbesubstantiallydecreasedwithoutpenalizingsuchlifetime.
This,inturn,maycontributetoreducetheamountofaddi-tionalresourcesrequiredinthesecondstage.
Inthissection,weillustratetheseideasbymeansofasimpletestscenario;however,forthesakeofcompleteness,wefirstsetupalifetimemodelforatime-drivensensornetworkwithNnodes.
3.
1LifetimeModelAlifetimemodelrequiresanenergyconsumptionmodel.
Theenergyconsumptionmodelusedinthepresentpaperwasfirstdevelopedin[3](onthebasisofaradiomodeldescribedin[12]),underthefollowingpremises:Onlytheenergywastedbythenodetransceiversisconsidered.
Nodataaggregation,sincethespatialcorrelationamongsamples(readings)insparsescenariostendstobelow.
Inaddition,byignoringdataaggregationaworst-caselifetimeanalysisisperformed.
Somelowduty-cycleMACprotocol,suchasTDMA,governstheaccessofnodestothewirelessmedium.
Timeisdividedintoroundsorreportingperiods,whosedurationisspecifiedattheapplicationoruserlevelsandistypicallymuchlargerthanthedurationofpacketsandTDMAframes.
Inaddition,thisallowsforneglectingthedelaysincurredbyTDMA,whateverslotassignmentschemeisusedanddespitetheabsenceofapacketaggregationscheme.
Then,inordertocharacterizethetrafficworkloadofeachnodei=1N,twomagni-tudeswereintroduced:g(i):numberofpacketstobegeneratedbynodeipercommunicationround(gen-eratingparameter).
Thisspecificationtakesintoaccountheterogeneousscenarioswherethesamplingprocessneedstobemoreintensiveinsomelocationsthaninothers.
σ(i):numberofpacketstobeforwardedbynodeiduringeverycommunicationround(forwardingparameter).
Notethatthesemagnitudesbecometime-independentwhendealingwithstaticdata-gatheringtrees,asitisthecaseofthepresentpaper.
NotealsothatifCH(i)denotesthesetofchildnodesofnodei,thefollowingequalityholds:ijjgiiCHjiCHj+=∑∑∈∈,)()()()()(σσ.
(1)Now,letEG(i)(EF(i))betheenergyconsumedbynodeitogenerateandtransmit(receiveandforward)apacket.
Then,thetotalenergyconsumedbythisnodeduringacommunicationround,namelyE(i),canbeexpressedasfollows:iiEiiEigiEFG+=,)()()()()(σ.
(2)ResourceOptimizationAlgorithmforSparseTime-DrivenSensorNetworks281Furthermore,ifERistheenergyconsumedbyanynodetoreceiveapacketandET(i)istheenergyconsumedbynodeitotransmitapacketatdistanced(i),wecansetupthefollowingequations:iiEiETG=,)()(.
(3a)iiEEiETRF+=,)()(.
(3b)Theenergyconsumedtoreceiveapacketistheenergydissipatedbythenodetrans-ceivercircuitrytoperformsuchoperation.
Becauseallnodesareassumedtobeprovidedbythesamevendor,thisenergycanbeconsideredconstantthroughoutthenetwork.
Ontheotherhand,theenergywastedtotransmitapacketincludesadis-tance-dependentcomponentinadditiontotheenergydissipation,andthusitgenerallyvariesfromnodetonode(inspiteofbeingprovidedbythesamevendor).
Thesestatementsaremadeexplicitviatheso-calledradiomodel[12]:mEEelecR=.
(4a)iidmEmEiEfwelecT+=,)()(.
(4b)Here,Eelecstandsfortheenergydissipatedbythetransceivercircuitrytotransmitorreceiveasinglebit,)(idEfwistheenergyradiatedtothewirelessmediumtotransmitasinglebitoveralinkofdistanced(i),fisthepath-lossexponentandmisthepacketsizeinbits.
Inturn,thedistance-dependentcomponentdependsonthedistanceitself:2,0==≤fEEddfsw.
(5a)2,0>=>fEEddmpw.
(5b)Equation(5a)modelsfreespacepropagation,whichisvalidbelowthereferencedis-tance(d0)(althoughbeyondtheso-calledfar-fieldregionofthetransmittingantenna[12]),whereasequation(5b)reflectsmulti-pathfadingeffects.
Inthislattercase,atypicalvalueforthepath-lossexponentis4.
Bycombiningequations(2),(3a)-(3b)and(4a)-(4b),thetotalenergywastedbyanodeineverycommunicationroundcanberewritteninthefollowingway:iidmEiigmEiigiEfwelec+++=,)())()(())(2)(()(σσ.
(6)Notethatinthisanalysistheenergywastedtowakeupanodehasbeenneglected.
Thisisanacceptableandusualapproximation,whichinadditionmakestheanalysisindependentoftheparticularslotassignmentschemeinthecaseofTDMA.
Itcanalsobenoticedthatexpression(6)revealsthattheenergyconsumedbyanodedependsonthreemajorfactors:workload,representedbythetrafficparametersg(i)andσ(i),targetdistanceandpacketsize.
Theenergyconsumptionmodelgivenby(6)cannowbeembeddedintoalifetimemodel.
Byassumingthatlifetimeisdefinedasthetimeuntilfirstnodedeath,wecan282M.
L.
Santamaría,S.
Galmés,andR.
Puigjanerexpressitinroundsasfollows(Bistheenergyinitiallyavailableatallnodes,thatis,thebattery):{}max)(1,)(maxiEBNiiEBL===K.
(7)3.
2IllustrativeExampleWeconsiderthescenariodetailedinFig.
1,where8regularnodesaresupposedtosend1packettothesinkperroundofcommunication,thatis,NiigK1,1)(==(forsim-plicity,withnolossofgenerality).
Fortheradiomodel,wetakethedatafromarealis-ticradiomodulepreviouslyintroducedin[13]:Eelec=50nJ/bit,Ew=10pJ/bit/m2andf=2ifthetransmissiondistanceisbelow75m(theso-calledreferencedistance),Ew=0.
0013pJ/bit/m4andf=4ifthetransmissiondistanceisabove75m,andB=15kJ.
Forthepacketsize,weassumeaslightlylargevalueof125B,althoughthechoiceforthisparameterisnotrelevanttoouranalysis.
Underalltheseassumptions,Fig.
1alsoshowsthegraphgeneratedbytheSAalgorithmdevelopedin[3].
Thisgraphyieldsalifetimeof722168rounds,determinedbynode8–seeexpression(7).
Besides,thisgraphrevealsoneofthemainfeaturesoftheSAalgorithm:itfocusesonmaximizingthelifetimeofthenetworkasdefinedby(7),butnotonenhancingthelifetimesortransmissiondistancesofparticularnodesunlessthiscouldhaveapositiveimpactonthefinalresult.
Forinstance,itisveryprobablethatnode4couldhavebeenconnectedtonode2insteadofnode5withoutperturbingthelifetimeofthenetwork.
Inthiscontext,areferencealgorithmistheMinimumSpanningTree,whichfindsthespanningtreethatminimizestheoveralllinkdistance(iflinkcostisdefinedastheEuclideandistance).
Inparticular,whenappliedtothenodedeploymentofFig.
1,theresultisthegraphshowninFig.
2insolidlines.
Theaveragelinkdistancehasde-creasedfrom207.
970m(withSA)to148.
302m,whichistheminimumachievablevalue.
Thisrepresentsareductionofapproximately30%.
However,thelifetimeofthenetworkhasalsodecreasedto514451rounds(thistimedeterminedbynode7),whichisalsoabout30%smaller.
Thereasonisthat,byfocusingexclusivelyonthetotallinkdistance,theMSTalgorithmignorestheworkloadsupportedbynodesandthusitdoesnotoptimizethelifetimeofthenetwork.
50m162Sink35784ii1234567800201402Fig.
1.
NodedeploymentandgraphgeneratedbytheSAalgorithm.
Forwardingparametersareindicated.
ResourceOptimizationAlgorithmforSparseTime-DrivenSensorNetworks283162Sink35784MSTEnhancedgraphii1234567801240501Fig.
2.
MSTandenhancedgraphs.
Forwardingparametersareindicated,includingthechangeofσ(7)fromonegraphtotheother.
Obviously,aquestionthatarisesiswhetheranintermediatesolutionisfeasible.
Inthisrespect,thegraphshowninFig.
2–withthedashedlineinsteadofline8-7,con-stitutesapositiveanswer.
Thisgraph,whichresultsfromapplyingthecombinedSA+LDRalgorithm(LDRisdescribedinthenextsection),exhibitsthesamelifetimeastheSAgraph(722168rounds,againdeterminedbynode8),butitsaveragelinkdistanceisnow148.
855m,veryclosetotheminimumachievedbytheMSTalgo-rithm.
Infact,itcanbenoticedthatthetwographsinFig.
2areverysimilar,althoughtheirsmalldissimilarityhasanimportanteffectonnetworklifetime.
4LinkDistanceReductionAlgorithmStartingfromthespanningtreegeneratedbytheSAalgorithm,theproposedLinkDistanceReductionalgorithmisaheuristiciterativemethodthatisintendedtotrans-formthistreeintoanotheronewithlessaveragelinkdistance,aslongaslifetimeisnotdegraded.
Inessence,thestrategyistochecktheconnectionsofallnodestotheirparents,tryingtofindcloserparentswhilepreservingthetreestructure(nocyclesareformed)andmaintainingorevenincreasingthelifetimeofthenetwork(recallthat,ingeneral,theSAalgorithmyieldsanear-optimalsolution).
Beforeproceedingtothespecificationofthealgorithm,letusintroducesomeusefuldefinitionsandnamingconventions:Let),(EVt=denoteaparticularspanningtree,whereVisthesetof1+Nverti-cesrepresentingtheN(regular)nodesandthesink,andEisacollectionoftwo-elementsubsetsofVthatrepresentconnectionsbetweenpairsofnodes.
LetTdenotethesetofalltreesspanningallverticesinV.
Giventhattisaspanningtree,everyedgeinEcanbeexpressedasapairNiipiK1)),(,(=,where)(ipdenotestheparentofnodei(thatis,thenodetowhichnodeisendspacketsonthewaytothesink).
Thus,0)(=ipifnodeiisdirectlyconnectedtothesink(itisassumedthatnode0isthesink).
Asstatedabove,thealgorithmexplorespotentialparentsforeachnode.
Thus,weintroduce)(*iptodenotetheparentthatistriedfornodeiataparticularstageoftheexecutionprocess.
284M.
L.
Santamaría,S.
Galmés,andR.
PuigjanerInourformalspecificationofthealgorithm,astatecorrespondstoaparticularspanningtree.
Accordingly,threevariablesaremanaged.
ThefirstoneisInitialState,whichdenotesthespanningtreeobtainedfromtheSAalgorithm.
TheLDRalgorithmstartsfromthisstate.
Then,CurrentStateandNewStatedenotethespanningtreesatthebeginningandendofeachiteration,respectively.
There-fore,NewStateisdifferentfromCurrentStateaslongasatleastoneparentofanynodeischangedduringthecorrespondingiteration.
Let),(jidbetheEuclideandistancebetweenanytwoverticesNjiK0,=.
Ac-cordingly,letAbeanNxNmatrixsuchthativu=),(Aandjvu=)',(Awith'vvp(B(i))do10if(NoCycle==True)and(LifetimeNotDegraded==True)then11p(B(i))←p*(B(i))12else13j←j+1;14p*(B(i))←A(B(i),j);15endif16endwhile17endfor18untilNewState==CurrentStateResourceOptimizationAlgorithmforSparseTime-DrivenSensorNetworks285Inthisalgorithm,lines3-18correspondtoasingleiteration.
Duringaniteration,theconnectionsofallnodestotheirparentsarecheckedindecreasingorderoftheirlinkdistances(lines6-17),and,foreachnode,potentialparentsareexaminedinin-creasingorderoftheirdistancetosuchnode,thatis,startingwiththeclosestone(lines9-16).
Thus,foranygivennode,intheworstcasethisprocessyieldsthesameparentnodeasthepreviousiteration.
Alsonotethat,asstatedbefore,thealgorithmexecutesanewiterationaslongasatleastonechangeisregisteredinthepreviousone.
Ineffect,anychangerequiresrevisitingthesituationofallnodesinasubsequentiteration;forinstance,ifnodeiwascheckedbeforenodejiniterationk,andthecon-nectionofnodejwaschangedduringsuchiteration,maybeapotentialparentfornodeithatwasrejectediniterationkcannowbeacceptediniterationk+1.
5SimulationResultsInordertovalidatetheproposedalgorithmandevaluateitscomputationalcomplex-ity,weperformedseveralsimulationexperimentsusingtheMathematicasoftware.
Thescenariofortheseexperimentswasa1000mx1000mfield,withcoordinate]1000,0[∈xandcoordinate]500,500[∈y.
Weplacedthesinkat)0,0(andfortheradiomodelweusedthevaluesofsubsection3.
2.
Eachsimulationexperimentcorre-spondedtoagivennumberofnodes,whichwasvariedbetween10and100instepsof10.
Thenumberofrunsinallsimulationexperimentswasadjustedsoastoproduce95%confidenceintervalsbelow10%.
Inturn,eachrunconsistedofgeneratingarandomdeploymentwiththecorrespondingnumberofnodes,andthenexecuting,ontheonehand,theMSTalgorithm,and,ontheotherhand,theSAfollowedbytheLDRalgorithms.
TheresultofeachrunconsistedofthegraphsgeneratedbytheMST,SAandSA+LDRalgorithms,aswellasseveralperformancemetricsevaluatedonthesegraphs.
Specifically,themostsignificantperformancemetricswerethefollowingones:Averagelinkdistance.
Foranydata-gatheringtree,thisisthesumoflinkdistancesdividedbythenumberofnodes(thereareasmanylinksasnodes).
Inordertoreducetheamountofadditionalresourcesthatcouldberequired,thegoalistoreducetheaveragelinkdistanceasmuchaspossible.
Lifetime.
Thisisthenetworklifetimeasgivenby(7).
Numberofrelaypoints.
Thisreferstothetotalnumberofrelaypoints(nodes)thatshouldbemarkedonthegraphofthenetworkinordertofulfillsomemaximumtransmissionrangerequirement.
Fig.
3showstheresultsobtainedforthefirsttwometrics.
Inparticular,Fig.
3(a)showsthedownwardtrendoftheaveragelinkdistance(inmeters)withthenumberofnodes,irrespectiveofthealgorithm.
Thisbehaviorwascompletelypredictable,be-causethegreatertheamountofnodesdeployedinafixed-sizeregion,theclosertheyaretoeachother.
Moreover,thisfigureshowsthatthelowestaveragelinkdistancecorrespondstotheMSTalgorithm,whichisobvioussincetheonlygoalofMSTistominimizethesumoflinkdistances.
Ontheotherhand,sincetheSAalgorithmonlytakeslinkdistancesintoaccountaslongastheycontributetoincreasethelifetimeof286M.
L.
Santamaría,S.
Galmés,andR.
Puigjanerààààààààààìììììììììì2040608010050100150200250300350NumberofNodesAverageLinkDistanceHmLìSA+LDRàSAMSTààààààààààìììììììììì204060801002000004000006000008000001.
0μ1061.
2μ1061.
4μ106NumberofNodesLifetimeHroundsLìSA+LDRàSAMST(a)(b)Fig.
3.
Averagelinkdistance(a)andlifetime(b)versusnumberofnodes.
TheSAandSA+LDRcurvesin(b)areinfullagreement.
thenetwork,itgeneratesanaveragelinkdistancesubstantiallygreaterthanthatofMST.
Betweenthesetwoextremecases,thecombinedSA+LDRalgorithmrepresentsthebesttradeoff,asittriestoreducetheoveralllinkdistanceaslongasthelifetimeobtainedfromSAisnotdegraded.
Specifically,itcanbenoticedthatthegapbetweentheSAandSA+LDRcurvesissignificant,factthatvalidatestheroleoftheLDRalgorithm.
Finally,anotherobservationisthattheMSTcurveissmootherthantheothers.
ThisisduetotheinherentrandomnessofthesimulatedannealingtechniqueonwhichtheSAandSA+LDRalgorithmsarebased,whichgenerallyleadstoalargersolutionspacethanwiththeMSTalgorithm(inthiscasethesolutionspaceistypi-callyasinglegraphoratmostaverysmallsetofgraphs).
ThedownwardtrendofcurvesinFig.
3(a)isinlinewiththeupwardtrendofthelifetimecurvesshowninFig.
3(b).
Thisisduetothefactthattransmissiondistanceplaysadominantroleinenergyconsumption,anditsprogressivedecreasewiththenumberofnodeshasmoreimpactthanthecorrespondingincreaseintrafficload(rep-resentedbytheforwardingparameters)–seeexpression(6).
Asitcanalsobenoticed,thecurvescorrespondingtoSAandSA+LDRarecompletelysuperposed,whichisnotsurprisingastheLDRalgorithmdoesnotdegradethelifetimeoftheSAgraph,andusuallydoesnotimproveiteither.
Finally,anotherobservationaboutFig.
3(b)isthegrowingvalueofthegapbetweenthetwocurves.
ThisisexplainedbythefactthatonlytheSAandSA+LDRalgorithmsfocusonnetworklifetime.
ààààààààààìììììììììì20406080100051015NumberofNodesRelayPointsìSA+LDRàSAMSTFig.
4.
NumberofrelaypointsversusnumberofnodesResourceOptimizationAlgorithmforSparseTime-DrivenSensorNetworks287Fig.
4plotstheevolutionofthenumberofrelaypointsasthenumberofnodesin-creases,foramaximumtransmissionrangeof250m.
Inthiscase,thethreealgorithmsexperiencedifferenttrends.
Thesecanbeexplainedbyviewingtheaveragelinkdis-tanceandthenumberofnodesasseparatefactors:ontheonehand,reducingtheav-eragelinkdistance(obviouslyasaconsequenceofincreasingthenumberofnodes)contributestoreducingthenumberofrelaypointsrequiredfornetworkconnectivity;ontheotherhand,sincetherecanbeoneormorerelaypointsper(regular)node,thereissomepositivecorrelationbetweenthesetwomagnitudes.
InthecaseofMST,whichfocusesexclusivelyonreducingtheoveralllinkdistance,theformerfactordominates.
However,theoppositehappenswithSA,sincethewholesetoflinkdis-tancesplayasecondaryroleinthisalgorithm.
Again,theSA+LDRcurveisinanintermediateposition,andthusitexhibitsalocalmaximumatarelativelylownumberofnodes.
Inparticular,thegapbetweentheSAandSA+LDRcurvesaswellasthedecreasingtrendofthelatterbeyonditslocalmaximumvalidatethesignificanceofLDRasaresourceoptimizationalgorithm.
Inadditiontoguaranteeingnetworkconnectivity,theintroductionofrelaynodesenhancesthelifetimeofthenetworkbeyondthevaluesshowninFig.
3(b)(accordingtotheenergyconsumptionmodelconsideredsofar).
Certainly,thisisapplicabletoboththeSA+LDRandMSTalgorithms,butthedifferenceisthatthestartingpointisgenerallybetterfortheformerthanforthelatter.
Thus,theenhancedlifetimeisex-pectedtobegreaterwithSA+LDRthanwithMST,atleastinastatisticalsense.
Inadditiontotheabovemetrics,weintroducedtwocomplementarymeasures:Averageenergyconsumption.
Thisistheaverageenergyconsumedbyanodeperroundofcommunication.
Itistheresultofdividingthetotalenergyconsumedbythenetworkduringaroundofcommunicationbythenumberofnodes.
Althoughthedefinitionoflifetimeusedinthispaperrelegatesthismeasuretoasecondaryrole,itcouldachievemoreimportancefromalternativeviewpoints.
Forinstance,ifelectricalpowersupplyfornodeswasfeasible(asitisthecaseofsomescenarios),lifetimewouldnotbecrucialanymore,butpreservingenergyconsumptionwouldstillbearelevantissue(forenvironmentalprotection).
Numberofcross-points.
Thisisthenumberofcrossingorintersectionpointsamongtheedgesofthegraphthatrepresentsthesensornetwork.
Itcanbeviewedasaroughestimateoftheentropyofsuchgraph.
Althoughthismeasuremayalsoappeartobesecondary,itcouldbecomemoremeaningfulinsomescenarios.
Forinstance,incasedirectiveantennaswereusedforinter-nodecommunication,thenumberofcross-pointswouldhaveanimpactontheamountofinterferences.
Fig.
5plotstheevolutionoftheseadditionalmetricsasthenumberofnodesincreases,forthethreealgorithmsconsideredsofar.
Inparticular,theresultsshowninFig.
5(a)(expressedinnJ)arecompletelycorrelatedwiththoseinFig.
3(a).
Again,thisisduetothefactthattransmissiondistanceplaysadominantroleinenergyconsumption.
So,wecanconcludethatMSToutperformsSAandSA+LDRwhentheemphasisisputontheoverallenergyconsumption,incontrasttowhatisshowninFig.
3(b),whichfocusesonnetworklifetime.
RegardingFig.
5(b),weshouldrecallthattheSAalgorithmfocusesonmaximizingthelifetimeofthenetworkasdefinedby(7),butnotonenhancingtheconnectionsofthenodesthatdonotdeterminethislifetime.
288M.
L.
Santamaría,S.
Galmés,andR.
Puigjaneràààààììììì204060801001μ1072μ1073μ1074μ1075μ1076μ107NumberofNodesAverageEnergyConsumptionHnJLìSA+LDRàSAMSTààààààààààìììììììììì204060801000102030405060NumberofNodesCross-pointsìSA+LDRàSAMST(a)(b)Fig.
5.
Averageenergyconsumption(a)andnumberofcross-points(b)versusnumberofnodesThis,inadditiontotheinherentrandomnessofthisalgorithm,makestheresultinggraphratherchaotic,withalargeamountofcross-pointsthatobviouslyincreaseswiththenumberofnodes.
Fromthispointofview,theMSTalgorithmexhibitsanoppositebehavior:itproducesagraphwithnocross-points,asshowninFig.
5(b).
Betweenthesetwoextremes,theSA+LDRcurvealsoshowsanupwardtrend,butsmootherthanintheSAcase.
Finally,wealsoevaluatedthecomputationalcomplexityoftheproposedalgo-rithm.
Althoughfromanetworkplanningperspectivethetopologydesignalgorithmsarenotsubjecttostrongrealtimerequirements,theissueofcomputationalcomplex-ityisstillofconcern,sincethesealgorithmsmayhavetobeexecutedfromtimetotimefornetworkreconfiguration.
Inthissense,theresultsobtainedforLDRareverysatisfactory,sincethetrendoftheregressioncurveshowninFig.
6ispracticallylin-ear.
Specifically,thiscurverepresentstheevolutionoftheaveragenumberofitera-tions(seeSection4)asthenumberofnodesincreases.
Inadditiontoitslineartrend,thisaveragetakesonrelativelymoderatevalues,asitvariesfromapproximately30for10nodestoaround1800for100nodes.
20406080100050010001500NumberofNodesComputationalComplexityFig.
6.
ComputationalcomplexityofLDRasafunctionofthenumberofnodes6ConclusionsandFurtherResearchInthispaper,wehavedevelopedtheLinkDistanceReductionalgorithm,aheuristicmethodthatminimizestheoveralllinkdistanceofatime-drivensensornetworkgraphwhilepreservingorevenimprovingitslifetime.
Thisalgorithmuseshill-climbingResourceOptimizationAlgorithmforSparseTime-DrivenSensorNetworks289withoutbacktracking,andthusitcouldstopatalocaloptimum.
However,incon-trast,thislimitationhasfavoreditssimplicityandcomputationalefficiency,andatthesametimeithasnotprecludedthealgorithmfromyieldingsignificantreductionsinaveragelinkdistanceandnumberofrelaypoints.
Theworkpresentedinthispapercanbeextendedtootherenergy-consumptionmodels,aswellastoscenarioswherethedeploymentdensityiskeptconstantorthemaximumtransmissionrangeofnodesisvaried.
AmoreadvancedresearchwouldconsistofdevelopingamodifiedversionoftheoriginalSAalgorithmthatincludedtheaveragelinkdistanceminimization,inordertoenabletheachievementoftheglobaloptimum(althoughattheexpenseofincreasingthecomputationalcomplexity).
Anotherissuewouldbethedistributedimplementationoftheproposedalgorithms.
Also,theissuesofconnectivity,lifetimeenhancementandfault-tolerancecouldbejointlytreatedbyreplacingsinglenodeswithclustersofcooperativetransmittingnodes(see[14]forasurveyonMIMO/MISOtechniques).
Finally,ourresearchresultsareprogressivelybeingintegratedinNetLife,asoftwaretoolforplanningtime-drivensensornetworks.
Acknowledgments.
ThisworkhasbeensupportedinpartbytheSpanishMinistryofScienceandTechnologyundercontractTIN2009-11711.
References1.
Akkaya,K.
,Younis,M.
:ASurveyonRoutingProtocolsforWirelessSensorNetworks.
AdHocNetworks3,325–349(2005)2.
Krishnamachari,B.
:NetworkingWirelessSensors.
CambridgeUniversityPress,Cam-bridge(2005)3.
Santamaría,M.
L.
,Galmés,S.
,Puigjaner,R.
:SimulatedAnnealingApproachtoOptimiz-ingtheLifetimeofSparseTime-DrivenSensorNetworks.
In:2009IEEEInternationalSymposiumonModeling,Analysis&SimulationofComputerandTelecommunicationSystems(MASCOTS),pp.
193–202.
IEEE,Inc.
,LosAlamitos(2009)4.
Goel,A.
,Estrin,D.
:SimultaneousOptimizationforConcaveCosts:SingleSinkAggrega-tionorSingleSourceBuy-at-Bulk.
In:ACMSymposiumonDiscreteAlgorithms(2003)5.
Enachescu,M.
,Goel,A.
,Govindam,R.
,Motwani,R.
:ScaleFreeAggregationinSensorNetworks.
In:FirstInternationalWorkshoponAlgorithmicAspectsofWirelessSensorNetworks(2004)6.
Wu,Y.
,Fahmy,S.
,Shroff,N.
B.
:OntheConstructionofaMaximum-LifetimeDataGath-eringTreeinSensorNetworks:NP-CompletenessandApproximationAlgorithm.
In:27thConferenceonComputerCommunications,INFOCOM(2008)7.
Cheng,X.
,Du,D.
,Wang,L.
,Xu,B.
:RelaySensorPlacementinWirelessSensorNet-works.
WirelessNetworks14(3),347–355(2008)8.
Chen,D.
,Du,D.
,Hu,X.
,Lin,G.
,Wang,L.
,Xue,G.
:ApproximationsforSteinerTreeswithMinimumNumberofSteinerPoints.
JournalofGlobalOptimization18(1),17–33(2000)9.
Tang,J.
,Hao,B.
,Sen,A.
:RelayNodePlacementinLargeScaleWirelessSensorNet-works.
ComputerCommunications29(4),490–501(2006)290M.
L.
Santamaría,S.
Galmés,andR.
Puigjaner10.
Kashyap,A.
,Khuller,S.
,Shayman,M.
:RelayPlacementforHighOrderConnectivityinWirelessSensorNetworks.
In:25thConferenceonComputerCommunications,INFO-COM(2006)11.
Galmés,S.
:LifetimePlanningforTDMA-BasedProactiveWSNwithStructuredDeploy-ment.
In:2007IFIP/ACMLatinAmericanNetworkingConference,LANC(2007)12.
Rappaport,T.
S.
:WirelessCommunications:PrinciplesandPractice.
Prentice-Hall,Engle-woodCliffs(2002)13.
Heinzelman,W.
B.
,Chandrakasan,A.
P.
,Balakrishnan,H.
:AnApplication-SpecificProto-colArchitectureforWirelessMicrosensorNetworks.
IEEETrans.
onWirelessCommuni-cations1(4),660–670(2002)14.
Ahmad,M.
R.
,Dutkiewicz,E.
,Huang,X.
:PerformanceEvaluationofMACProtocolsforCooperativeMIMOTransmissionsinSensorNetworks.
In:5thACMSymposiumonPer-formanceEvaluationofWirelessAdHoc,Sensor,andUbiquitousNetworks(2008)