necessarilynetlife
netlife 时间:2021-03-17 阅读:(
)
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)
paypal贝宝可撸$10的代金券!这两天paypal出了活动,本次并没有其他的限制,只要注册国区的paypal,使用国内的手机号和62开头的银联卡,就可以获得10美元的代金券,这个代金券购买产品需要大于10.1美元,站长给大家推荐几个方式,可以白嫖一年的VPS,有需要的朋友可以看看比较简单。PayPal送10美元活动:点击直达活动sfz与绑定卡的号码可以重复用 注册的邮箱,手机号与绑的银联卡必须...
DediPath 商家成立时间也不过三五年,商家提供的云服务器产品有包括KVM和OPENVZ架构的VPS主机。翻看前面的文章有几次提到这个商家其中机房还是比较多的。其实对于OPENVZ架构的VPS主机以前我们是遇到比较多,只不过这几年很多商家都陆续的全部用KVM和XEN架构替代。这次DediPath商家有基于OPENVZ架构提供低价的VPS主机。这次四折的促销活动不包括512MB内存方案。第一、D...
小白云是一家国人自营的企业IDC,主营国内外VPS,致力于让每一个用户都能轻松、快速、经济地享受高端的服务,成立于2019年,拥有国内大带宽高防御的特点,专注于DDoS/CC等攻击的防护;海外线路精选纯CN2线路,以确保用户体验的首选线路,商家线上多名客服一对一解决处理用户的问题,提供7*24无人全自动化服务。商家承诺绝不超开,以用户体验为中心为用提供服务,一直坚持主打以产品质量用户体验性以及高效...
netlife为你推荐
国家网络安全部加强国家网络安全的重要意义 ?网易网盘关闭入口网易网盘里面有好的东西,怎么才能共享出来?【已解决】哈利波特罗恩升级当爸哈利波特中的赫敏为什么要喜欢罗恩,不喜欢哈利sherylsandberg这个文章什么意思 给个翻译好吗 谢谢了阿丽克丝·布莱肯瑞吉阿丽克斯布莱肯瑞吉演的美国恐怖故事哪两集firetrap你们知道的有多少运动品牌的服饰?老虎数码我想买个一千左右的数码相机!最好低于一千五!再给我说一下像素是多少?www.20ren.com求此欧美艳星名字http://www.sqsmm.com/index.php?album-read-id-1286.htmlwww.983mm.comwww.47683.com关键字关键词标签里写多少个关键词为最好
免费动态域名 草根过期域名 warez 香港机房 z.com 20g硬盘 美国php主机 xfce 服务器维护方案 域名接入 isp服务商 域名dns 中国电信测速器 丽萨 美国盐湖城 国外在线代理服务器 中国电信测速网站 中国域名 lamp怎么读 ledlamp 更多