Gradient Based Routing in Wireless Sensor Networks a Mixed S

We show how recent theoretical advances for data-propagation in Wireless Sensor Networks (WSNs) can be combined to improve gradient-based routing (GBR) in Wireless Sensor Networks. We propose a mixed-strategy of direct transmission and multi-hop propagatio

5

002 voN 32 ]CD.sc[ 1v380115/0sc:viXraGradientBasedRoutinginWirelessSensorNetworks:a

MixedStrategy

OlivierPowell,AubinJarry,PierreLeone,Jos´eRolim

February7,2008

Abstract

Weshowhowrecenttheoreticaladvancesfrom

[11,4,8,9]fordata-propagationinWirelessSensorNetworks(WSNs)canbecombinedtoimprovegradient-basedrouting(GBR)inWire-lessSensorNetworks.Weproposeamixed-strategyofdirecttransmissionandmulti-hoppropagationofdatawhichimprovesthelifes-panofWSNsbyreachingbetterenergy-load-balancingamongstsensornodes.[10].

Keywords:WirelessSensorNetworks,WSN,

routing,gradient-basedrouting,GBR,data-propagation,energy,load-balancing,mixed-strategy

1Introduction

Animportantobjectiveinthedesignandim-plementationofe cientalgorithmsforWire-lessSensorNetworks(WSN)istominimizetheenergyconsumption,inordertomaximizethelifespanofthenetwork([2]).Weareinter-estedintheproblemofdatapropagationinWSNs([3,1]),whichisthefactoftransfer-ringinformationscatteredamongstthenodesoftheWSNtowardsthebasestation,alsocalledthesink.Inthiscontext,energyisconsumedmainlyduringtheradiotransmissionphase[].Theenergy-costoftransmissionstypicallygrowsasapower(greaterthan2)ofthetransmis-sionrange([3,1]).Becauseofthispolynomialgrowth,multi-hopdatapropagationfromnodetonodetowardsthesinkisusuallypreferredtolong-rangeandexpensivesingle-hoptransmis-sionfromdistantnodesdirectlytothesink,un-lessthedistancefromnodestothebasestationissmall(c.f.[6]).Thisintroducestheneces-sitytoroutemessagesfromnodetonode,to-

We show how recent theoretical advances for data-propagation in Wireless Sensor Networks (WSNs) can be combined to improve gradient-based routing (GBR) in Wireless Sensor Networks. We propose a mixed-strategy of direct transmission and multi-hop propagatio

routedalongthesti estslope.Thissimpleap-proachleadstoanoveruseofafewroutes,sotheyintroducenetworkspreadingtechniques,inordertoputtocontributiontherestofthenet-work.Forexample,thestochasticschemein-troducessomerandomizationinthechoiceofroutes(thisideahasalsobeenusedincost eldapproach,e.g.in[12]).Twootherspreadingtechniqueswerealsoproposed:anenergy-basedadjustmenttotheheight,andastream-basedadjustment.Thetechniquesemployedaregen-eralenoughsothattheyarealsoapplicabletootherroutingprotocols.Nevertheless,howeverwellspreadthetra c,thefactthatitisroutedmulti-hoptowardsthesinkyieldsanoveruseofnodesclosetothesink.Thisproblemwasacknowledgedin[11],andfurtherinvestigatedintheseriesofpapers[4,8,9].Inparticu-lar,in[9],ano inealgorithmisproposedtocomputeamixed-strategycombiningmulti-hopdata-propagationandparsimonioususeofdirecttransmissiontothesink,(anditisshownthatundersomeassumptions,themixed-strategycomputedbythealgorithmoptimizesthenet-worklifespan).Thealgorithmin[9]worksof- ineandconsidersanabstractionoftheGBRroutingscheme.Thispaperinspiresitselffromthisalgorithmtoproposeamodi edversionofGBRandshowexperimentallytheadvantagesofthisapproach.

Ouralgorithm:InordertoadaptGBRtoamixed-strategy,wede neastaticpotentialfunctionforeachnoden,whichisequaltothesumofthesquaredheights:pots(n)= n2

1height(n).Weuseanenergy-basedspread-ingtechnique,byde ningthepotentialofanodeaspot(n)=pots(n)+ (n),where (n)isafunctionmeasuringtheenergyspentso-farbythenode.Finally,themixedstrategyisob-tainedbyapplyingthefollowingscheme:whenanodeneedstorouteamessage,itsendsittotheneighbourwiththelowestpotential.However,ifthislowestneighbourhasa(strictly)higherpotentialthanitsown,itdoesnotpassthemes-sagetoaneighbourbutsenditdirectlytothethebasestation.Thisdirecttransmissionisalong-rangetransmission,andithasanenergycost1ofheight2(n)(whereastransmissiontoaneighbourisassumedtocost1energyunit).

We show how recent theoretical advances for data-propagation in Wireless Sensor Networks (WSNs) can be combined to improve gradient-based routing (GBR) in Wireless Sensor Networks. We propose a mixed-strategy of direct transmission and multi-hop propagatio

atpositions( 10,0)and(10,0).Next,weruntheevent-generation/message-propagationparadigmasdescribedabovefor5·106rounds.Theenergyconsumptionforthethreestrate-giesiscomparedin gure1.Whatweseeon

0008000061

t

nep0S00g0rn4000020051015202530

sliceNumber

Figure1:

this gureisthattheenergyconsumptionisbadlybalancedforthestandardGBRprotocol:afewnodesclosetothesinkspendalotofen-ergy,whilethenodesawayfromthesinkdonot.Thiscanbefurtherobservedon gure2,whereadiskwithsurfaceproportionaltotheenergyconsumption(forthestandardGBRprotocol)isplottedforeachsensor.This gurehelpsunder-standhowGBRbehaves:weseenaturalroutesappearingwhicharebottle-neckregionsofthenetwork,composedofcentralgatewaysthroughwhichmostmessageshavetotransit.Thetraf- calongtheseroutescouldprobablybespreadabitbetter(e.g.byusingastream-basedtra cspreadingtechnique[10]),butthemainprob-lemtoenergybalancingisthatnodesclosetothebasestationsusemoreenergythanthoseawayfromthebasestations,(asobservedandexplainedin[11,4,8,9]).Onthecontrary, g-ure1showthatthisproblemiswelladdressedbythemixed-strategyGBRprotocolwepropose.

3.3

Comparisontoanoptimalso-lution

In[9],ano inealgorithmproducinganopti-mal2randomized-strategywasproposed:whena

We show how recent theoretical advances for data-propagation in Wireless Sensor Networks (WSNs) can be combined to improve gradient-based routing (GBR) in Wireless Sensor Networks. We propose a mixed-strategy of direct transmission and multi-hop propagatio

GBRroutingisbroken.Inlightofthis,itdoesnotseemunreasonabletoconsider,asamea-sureofthelifespanofthenetwork,theworst-caseenergyconsumptionamongstnodes.Forthismeasurewecannumericallyobservethatintheaboveexpe …… 此处隐藏：6293字，全部文档内容请下载后查看。喜欢就下载吧 ……