Telecommunication

ControlinWirelessSensorNetworks

MartinKubisch,HolgerKarl,AdamWolisz

TelecommunicationNetworksGroupTechnischeUniversit¨atBerlinSekr.FT5-2,Einsteinufer2510587Berlin,Germany

kubisch|karl|wolisz@ee.tu-berlin.de

LizhiCharlieZhong,JanRabaey

BerkeleyWirelessResearchCenterUniversityofCaliforniaBerkeley2108AllstonWay,Suite200Berkeley,CA94704-1302

czhong|jan@eecs.berkeley.edu

Abstract—Twoalgorithmsfordynamicallyadjustingtrans-missionpowerlevelonaper-nodebasishavebeenevaluatedusingasimulativeapproach.Networklifetime,convergencespeedaswellasresultingnetworkconnectivityhavebeenobtainedforthesetwoalgorithmsusingaparticularindoorsensorenvironment.Thenetworklifetimemetricsofthesetwolocalalgorithmsarealsobenchmarkedagainstpowercontrolalgorithmsusingglobalinformation.Weshowthatthesetwoalgorithmsoutperformfixedpowerlevelassignmentandaregenerallywithinalifetimeoftwoofagloballycomputedsolution.

Keywords:Relaying,energyefficiency,sensornetworksI.INTRODUCTION

Sensornetworks[1]—networksoftinynodesequippedwithlimitedsensing,computing,andradiocommunicationcapabilities—areatechnologicalvisionthatiscurrentlyreceivingalotofattentionfromseveralresearchcommu-nities.Inatypicalscenario,suchsensornetworkswouldusewirelesscommunicationtotransmittheirobservationvaluestoagivenmonitorstationwhichwouldserveasauserinterface.

Ajointcharacteristicofmostapplicationscenariosisthatsensorsonlyhavealimitedenergysupplywhichmightnotevenberechargeable,hencetheyhavetoworkasenergy-efficientlyaspossible.Oneoptionistoreducetransmissionpowerusingintermediatenodesasrelaysinsteadofdirectcommunicationwitharemotenode.Whilesuchrelayinghasitsowndisadvantages(energyisnowalsoconsumedforintermediatereceptionandtransmission),relayingcanbebeneficialforimprovingenergyefficiency[2].

Yetarbitrarilyreducingtransmissionpowerisnotpossi-ble;atleast,somedirectneighborsofasensornodemustbereachabletoprovidethepossibilitiestoperformrelayingandtoformaconnectednetworkviarelaying.Thereforeitisimportanttofindalgorithmswhichdetermineappropriatetransmissionpowerlevelsforeverynode.Inaddition,becauseofthesizeanddynamicsofsensornetworks,thesealgorithmsshouldbedistributedones,relyingonlyonlocallyavailableinformationandtherewithbeingscalableasthenetworkgrowths.

Wepresenttwodistributed(local)algorithmsthatdeter-mineanindividualtransmissionpowerlevelforeachnodeofafixed,non-mobilewirelesssensornetwork.Thesame

powerisusedwhensendingtoanyneighbor,irrespectiveofwhethersomeneighborsarecloserthanothers.Onereasontodosoisthetimeandhenceenergyexpenditurethatisrequiretosettheamplifiertodifferentpowerlevels.Algorithmically,theuseofdifferentpowerlevelsdependingontheintendedreceiversiseasilypossible.Thedistributedcomputationhappensinaninitializationphase,andtheresultingpowerlevelsarethenusedforthedatacommunicationwithinthenetwork.Asthisdistributedcalculationdoesnotwarrantyafullconnectednetwork,itmaybereasonabletoleavefew(communicationexpensive)nodesoutinordertospendthisenergyforanetworklifetimeextension.

Asthelocalalgorithmswouldnotbedeployedasstand-alone,insteadtheywouldbeintegratedwithothermechanismusingthesameinformation,e.g.,locatingofsensors,neitheraparticularMACprotocolnoradedicatedprotocolforroutediscoveryisused.Buttoevaluatethealgorithmsintermsofnetworklifetime,datatransfermustberealized,henceanyMACprotocolintendedtoworkwithmustprovidecorrectdatadelivery.Theroutingtablesarecomputedusingtheper-nodepowerlevelachievedandtheshortest-pathroutingbasedonDijkstra’salgorithm[3].Oneparticularlyinterestingaspectisthefactthatpowerassign-mentalgorithmscanresultinasymmetriccommunicationrelationships.Hence,theroutingprotocolappliedinrealsystemsmustbeabletohandlesuchasituation.

Asthelocalalgorithmscanresultinnetworksnotbeingfullyconnected,itishardtocomparelocalandglobalalgorithmsintermsofnetworklifetime1(timeuntilthefirstsensornodedies;allnodesstartwiththesamefixedamountofenergy).Thesolutionistoconsiderthenodesnotbeingconnectedasdeadnodes,hence,aglobalalgorithmrunsuntilonenodemorethanthenumberofnotconnectednodes(fromthelocalcase)died.Forthelocalalgorithmsthelifetimeisoverwhenthefirstnodeofthelargestconnectedpartofthenetworkrunsoutofenergy.ButascanbeseeninSectionIII-B,theaveragenumberofnodesnotbeingconnectedisfarbelowonepercent,whichinthe

1Alternatively,

timetonetworkpartitioncouldbeused,butasthelocal

algorithmscanendupwithsomenodesnotbeingconnecteditisnotcomparable

scenariosusedmeansbelowonenode.Hence,weneglectedthiseffectandconsideralwaysthedeadofthefirstnodeasourfigureofmeritandoptimizationcriterion.

Theremainderofthispaperisorganizedasfollows.SectionIIdescribesbothlocalalgorithmsconsideredaswellastheglobalalgorithmswhichserveascomparisoncases.SectionIIIoutlinesthesimulationsetupweusedtostudythesealgorithmsandpresentssimulationresults.SectionIVgivesanoverviewofrelatedwork.Finally,SectionVpresentsconclusionsanddirectionsforfuturework.

II.PROBLEMSOLUTIONS

Inthefollowing,fivedifferentapproachesareintroduced.Thefirsttwoarethelocalalgorithmswhichcanbeappliedtosensornetworksinadistributedmanner,whereastheotherthree(global)algorithmsarecomparisoncaseswhichmakeuseofglobalknowledgeandhencealwaysachieveoptimalsolutions,accordingtotheirrespectiverestrictions.Theglobalalgorithmsareusedtoshowtheeffectivenessofthelocalalgorithms.

A.Thresholdinnumberofneighbors

The“localmeanalgorithm”(LMA)worksinthefollow-ingway:Allnodesstartwiththesameinitialtransmissionpower(TransPwr).Everynodeperiodicallybroadcastsalifemessage(LifeMsg)includingitsuniqueidentity.Alltheothernodes,whichreceivesuchaLifeMsg,replywithalifeacknowledgemessage(LifeAckMsg)includingtheaddressoftheLifeMsgsender.BeforeanodeissuesthenextLifeMsgitcountsthenumberofLifeAckMsgsreceived(NodeResp).IfNodeRespislessthanamini-mumthreshold(NodeMinThresh),thenodeincreasesitstransmissionpowerbyacertainamount(Ainc)foreverymissingneighbor;thetransmissionpowerisnotincreasedbymorethanBmaxinasinglestep.2IfNodeRespislargerthanamaximumthreshold(NodeMaxThresh),itdecreasesitstransmissionpowerbyacertainamount(Adec)foreverysupernumeraryneighbor;thetransmissionpowerisnotdecreasedbylessthenBmininasinglestep.3IfNodeRespisbetweenNodeMinThreshandNodeMaxThreshthenodedoesnotchangeitstransmissionpoweranymore;ithasconverged.Whilethisalgorithmhasaperiodicnature,itisimportanttonotethatnoclosesynchronizationofnodesorglobaltimebaseisrequired;thenotionofperiodicityisapurelylocalone.

B.Thresholdinmeannumberofneighbors

The“localmeanofneighborsalgorithm”(LMN)workssimilartoLMAexceptthatitaddssomeinformationtotheLifeAckMsganditdefinesNodeRespinadifferentway.InadditiontotheaddressfromthereceivedLifeMsg,theLifeAckMsgalsocontainsitsown,mostrecently

2Formally:

TransPwr←min{Bmax·TransPwr,A−NodeResp)·TransPwr}.inc·

(NodeMinThresh3Formally:TransPwr←max{B

min·TransPwr,A−NodeMaxThresh)·TransPwr}.

dec·(1−

(NodeRespcomputed,numberofneighbors.ThenodereceivingtheLifeAckMsgscalculatesameanvaluefromitsneighbors’numberofneighbors—thenewNodeResp,whichinturnisusedtoadjustthetransmissionpower.E.g.,whennodeAsendsaLifeMsg,thenodesB,CandDreceivethismessageandrespondwithaLifeAckMsgcontainingtheirmostrecentNodeResp(B=6;C=4;D=3).AsnodeAreceivesalltheseLifeAckMsgitcreatesthemeanoutofthenumberofresponses(threeneighborsB,C,D)andtheirmeannumberofneighbors(6;4;3),whichisthenewNodeRespforA(here4).IfthisnewNodeRespisbelowNodeMinThreshoraboveNodeMaxThreshthetransmissionpoweradaptionisdoneasdescribedinSectionII-A.

C.Fixedtransmissionpower

Themostsimplestalgorithmistoassignanarbitrarilychosentransmissionpowerleveltoallsensornodes,muchlikeitwouldbedoneatproductiontimeforsensorsthatdonothavepowercontrolatall.Inthefollowingweassumethatthetargetconfiguration(i.e.,thedensityofnodes)isknownandhencetheminimumtransmissionpowerprovidingafullyconnectednetworkisknownaswell.Thisvalueisusedasfixedtransmissionpower.Additionallylargertransmissionvaluesareusedtoshowtheeffectofusingtomuchapower.

D.GlobalsolutionwithequaltransmissionpowerTheEqualTransmissionPower(ETP)algorithmalsoassignsauniformpowertoallnodes,butchoosestheminimalvaluethatensuresafullyconnectednetworkforthisparticularscenario.Tofindtheminimumtransmissionpower,thefollowingalgorithmisused:

1)Amongthenodepairsthatarenotyetconnected,choosetheonewiththesmallestdistance.

2)Settransmissionpowerofallnodestoavaluesuffi-cienttoconnectthesetwonodes.

3)Checkconnectivityoftheresultingnetworkandwhenthenetworkisconnected,theminimumpowerlevelisfound;otherwisestartfrom1.

Thispowervaluerepresentsthesmallestvalueforafullyconnectedsensornetworkwithfixedtransmissionrangeanditalsoresultsinsymmetriccommunicationlinks.Thisalgorithmusesglobalinformationanditisnotevidenthowtoimplementacorrespondinglocalalgorithmthatachievesthesameresults.

E.GlobalsolutionwithdiversetransmissionpowerTheglobalsolutionwithDiverseTransmissionPower(DTP)algorithmcreatesaconnectednetworkbutdoesnotsetalltransmissionrangestothesamevalue.Insteadittriestofindaminimumpowerlevelforeverynodeindividually.Thealgorithmworksinthefollowingway:

1)Amongthenodepairsthatarenotyetconnected,choosetheonewiththesmallestdistance.

2)Settransmissionpowerofthesetwonodestoavaluesufficienttoconnectthem.

3)Checkconnectivityoftheresultingnetworkandwhenthenetworkisnotconnectedstartfrom1.

Thisalgorithmminimizestheoveralltransmissionpowerconsumptionfortheentirenetwork,butitmayresultinasymmetriccommunicationlinks,e.g.,onenodecanreceivedatafromafarneighborwhichusesahighertransmissionpower,butcannotanswerdirectlyduetoitssmallertransmissionpower.

Eventhoughitispossibletoconstructnetworkswherethisalgorithmdoesnotfindminimumpowerlevelsforallnodes,DTPvastlyoutperformsanyotherglobalalgorithmthatwehaveconsidered.Therefore,weuseDTPasacomparisoncase.SimilarlytotheETPalgorithm,thisalgorithmalsousesglobalknowledge,andequivalentlocalimplementationsarenotobvious.

III.SIMULATIONRESULTS

A.Investigationscenario

Inordertoevaluateandcomparethesealgorithms,wesimulatedtheenergyconsumptionandresultingnetworklifetimeforaparticularindoorsensornetworkscenario.ThesimulatorusedforthistaskwaswrittenusingtheOMNeT++[4]simulationtool.

Duringthedatacommunicationphase,energyiscon-sumedforbothtransmittingandreceivingdatapacketsaswellasforidlephases.Thepowerconsumptionduringtheidlephaseis0.1µW,forreceiving0.5mW,forsending1mW;4asensornode’sinitialenergysupplyis100J.Atanassumedbitrateof10kbit/s,thesevaluescorrespondto1µJand0.5µJtosendandreceiveabit,respectively.Thetransmissionpowerlevelsaresetbytheabovealgorithmssuchthattransmissionerrorsonlyhappenwithnegligibleprobability(moreprecisely,anodeisonlyconsideredtoreceivefromaneighboriftheSNRatitsantennaisatleast-90dBm),hencetransmissionerrorsarenotconsidered.ThephysicallayoutconsistsoffourroomsconnectedbyahallwayasshowninFigure1.Allroomsare3.5mhigh,thegreybarsindicatedoors(1mwide;assumedtoreachuptotheceiling),theblackdotsshowthepositionoftwomonitornodes(actingastheuserinterfaceandbeingthemasterstationwhichpollthesensorsoverthenetwork),whicharepositioned1.2mabovetheground.Wallsareassumedtobeinfinitesimallythin,constitutingnoobstacleforradiocommunication.Thepathlosscoefficientofthechannelissetto2.Basedonthislayout,32differentplacementsofsensornodesweregeneratedbyplacing318nodesrandomlyonthewalls,ceilings,andfloors(usingauniformnodedistribution).

Foreachoftheseplacements,everyalgorithmcomputesthetransmissionpowerlevelassignmentsforeachsensornode.Accordingtothisassignments,edgesbetweenthenodesabletooverheareachotherarecalculatedandwithDijkstra’salgorithm[3]theroutingtableentriesforeverynodearecalculated.FortheETPandDTPalgorithmsas

4the

assumptionisthatasendingnodecanwakeupnodesinitsvicinitybyusingalow-bandwidthsignalingchannelthatiseasytodemodulateevenforalow-powerreceiver,e.g.the”Frisbee”modelin[5]

4m4m4m6mm5RoomRoomRoomRoomm2Hallway18mFig.1.Physicalroomlayout.Greybarsrepresentdoors,blackcirclesrepresentmonitornodes.

wellasforthefixedtransmissionpower,thisresultsinasingleconfigurationofpowerlevelassignments.Thefinaltransmissionpowerlevelforthelocalalgorithmsdependsontheinitialtransmissionpowertobeusedbyeachnodeandthenumberofcyclesanalgorithmruns.Theinitialpowervalueisvariedlinearlyin56stepsfromatransmissionrangeof25mmto1.4m.Foreachoftheseinitialpowerlevels,theinitializationphaseiscomputedusing100cycleswitheitherLMAorLMN.Eventhoughbothalgorithmsettledownearlier,thisnumberwasusedtoavoidinstableroutes.

Thelocalalgorithmsuseatransmissionpowerincreasevalue(Ainc)of10%withanupperbound(Bmax)oftwotimestheoldtransmissionpowerandadecayvalue(Adec)of2%withalowerbound(Bmin)ofhalftheoldvalue(moreaggressivevalueslettheimplementationoscillate).Notethattheenergyconsumptionduringthisinitializa-tionphaseisnottakenintoaccount.Informationneededforthealgorithmsarealsoavailableinother,sensor-network-relatedprotocols[6],thusitcangetthisinformationwith-outadditionaloverheadandtheconsumptionisnegligible.Aftertheinitialization,thedatacommunicationphaseissimulated.Thetrafficinthenetworkconsistsofre-quest/repliesinitiatedbythemonitor.Theserequestsaredirectedatarandomlychosensensornode(themonitorisassumedtohavesufficientinformationaboutthesen-sors).Thenodesreceivetherequestandanswerwithan(arbitrary)replyvalue.Theserequestsaresenteveryhalfasecond,alternatingbetweenthetwomonitornodes.Thesesimulationrunsresultinatotalof32networklifetimesamplesfortheglobalalgorithmsand32×56sam-plesforthelocalalgorithms;networklifetimes,confidencelevelsfortheaveragelifetimeandcomparisonsareshowninSectionIII-C.Butfirst,thequestionofconvergencespeedofthelocalalgorithmsaswellaswhetherthesealgorithmsreachafullyconnectednetworkisinteresting.B.Convergenceandconnectivity

ThelocalalgorithmsLMAandLMNuseanumberofiterationsbeforesettlingdowntoparticulartransmissionpowerlevels.Anindividualnodehasconvergedwhen

itsnumberofneighborsisbetweenNodeMinThreshandNodeMaxThresh.AsdeterminedbyKLEINROCKandSILVESTERin[7]themeannumberofneighborsassuringagoodconnectivityshouldbe5.89andpreliminaryexperi-mentswiththeglobalalgorithm,asdescribedinSectionII-E,showedthatthenumberofneighborsofmostnodesisbetweenfourandseven;thesevalueswerethereforeusedasthresholdsforthelocalalgorithms.

Adesirablepropertyofsuchanalgorithmwouldbethatallnodesconvergeveryquickly.Evidently,theini-tialtransmissionpower(equivalenttotheinitialrangeoftransmission)playsanimportantroleforthesealgorithms.Figure2showsthatmostnodesconvergewithinasmallnumberofcyclesandsomefewnodestakeupto50cycles.Forcertaininitialpowerlevels,italsohappensthatavery

250LMA1,81,61,41,210,80,60,40,20147101316LMN0,050,0450,040,0350,030,0250,020,0150,010,005019222528LMAConfiguration numberFig.3.Percentageofnodesnotconnectedfordifferentnetworkconfigurations

20015010050073852.5Cycle󰀀number

aroughideaofpossiblenetworklifetimesachievableinourconfiguration,Figure4showstheresultsforthesimplefixedassignmentsoftransmissionpowers(powervaluescorrespondingtotransmissionrangesof3,5,and7mwereused;therewiththeusednetworkswerefullyconnected)aswellasthecasefortheglobalETPalgorithm.Asexpected,ETPoutperformsthefixedvaluealgorithmsandachievesanaveragenetworklifetimeofabout48800seconds,whilethefixednetworkalgorithms’achievements

122.5areconsiderablybelowthat.Itisalsointerestingtosee

62.5Initial󰀀󰀀thatthelifetimeofthenetworkdependsheavilyontherange󰀀actualnetworkconfiguration;differencesareupto50%.(cm)Moreinterestingisthecomparisonbetweentheglobaland

Fixed @ 3m70Number󰀀of󰀀converged󰀀nodes󰀀11325374961Fig.2.Histogramoftimetoconvergence(incycles)dependingonintitialtransmissionrange(incm)

97Fixed @ 5mFixed @ 7m31ETPNetwork lifetime ( x 1000s)smallnumberofnodesdonotconvergeatall.Asanexample,consideracasewhereasinglenodeislocatedfarawayfromaclusterofnodesthatquicklyformaconnectedgroupbeforetheyreceivethefarnodesLifeMsg.

WhilealargervalueofNodeMaxThreshincreasesthelikelihoodofaconnectednetwork,italsoresultsinlargertransmissionpowerlevels.

Figure3showsthepercentageofnodesthatwerenotreachablefromthemonitorstationsforthelocalalgorithmsfromSectionsII-AandII-B.Thelargestvalueis1.65%forLMAand0.04%forLMN,andontheaverage,0.003%arenotconnectedconsideringLMNand0.37%whenonlytakingintoaccountLMA.5TheseresultssuggestthatLMNcreatesamuchstrongerconnectednetworkthanLMA.C.Networklifetime

Themostinterestingperformancemetricforsuchasensornetworkisthenetworklifetime:thelongereverysinglenodeiscapabletocommunicate,thebetterthetransmissionpowerlevelswerechosen.Inordertogive

thatthesenumbersareaveragedoverdifferentinitialtransmission

powerlevels,hencepercentagesdonotcorrespondtoanintegernumberofnodes.

5Note

6050403020100135791113151719212325272931Configuration numberFig.4.Networklifetimesfordifferentconfigurationsforfixedtransmis-sionpowerandequaltransmissionpowerassignments

thelocalalgorithmsinFigure5.ItcomesasnosurprisethatDTPvastlyoutperformsallotheralgorithmswithitsglobalknowledge.Asageneralimpression,thelifetimeachievedbyDTPisupto209%longerthanthatobtainedbyLMNandevenhigherforLMA.Onaverage,DTPachievesnetworklifetimesthatareabouttwiceaslongasLMA,LMN,andETP.Figure5alsosuggeststhatthelocalalgorithmsandtheETPalgorithmperformquitesimilarly.Figure6showstheconfidenceintervalsforthemeannetworklifetimeata95%confidencelevel.Applyingasimplegraphicalinterpretation,wecaninferthatETP

LMNDTP140ETPLMNLMAV.CONCLUSIONS

Wecanstatethatusingheuristics,whichconsiderthenumberofneighborsanodehas,resultinasufficientlyconnectednetwork,provideimprovementsinnetworklife-timeoversimplefixedassignmentsandareintherangeofsymmetricalgorithmsusingperfectknowledge.Whilethepresentedlocalalgorithmsarenotabletooutperformsophisticatedones,theyperformusuallywithinafactoroftwoconsideringthelifetime.

Additionally,thesealgorithmsarestructuredsimilarlytoothermechanismsthatareconjecturedtobedeployedinsensornetworks,e.g.,locationingmechanisms.Itwouldhencebepossibletointegratethesealgorithmsandtoamortizetheirjointresourceconsumption.

Anumberofinterestingquestionsremainforfuturework,e.g.,tousethenumberofneighborsintheannounce-mentmessagesandtoweightthisinformationagainstthetransmissionpowerwithwhichitwassentorhowanon-reliableMACinfluencesthealgorithms.Weintendtoinvestigatetheseareasinthenearfuture.

REFERENCES

[1]D.Estrin,R.Govindan,J.S.Heidemann,andS.Kumar,“Next

centurychallenges:Scalablecoordinationinsensornetworks,”inProc.5thAnn.Intl.Conf.onMobileComputingandNetworking.Seattle,WA:ACM,Aug.1999,pp.263–270.

[2]J.P.Monks,J.-P.Ebert,A.Wolisz,andW.meiW.Hwu,“Astudy

oftheenergysavingandcapacityimprovementpotentialofpowercontrolinmulti-hopwirelessnetworks,”inWorkshoponWirelessLocalNetworks,Tampa,Florida,USA,alsoConf.ofLocalComputerNetworks(LCN),Nov.2001.

[3]E.Dijkstra,“Anoteontwoproblemsinconnectionwithgraphs,”

NumericalMathematics,vol.1,pp.269–271,1959.

[4]A.Varga,OMNeT++:DiscreteEventSimulationSystem,Technical

UniversityofBudapest,FacultyofElectricalEngineeringandInfor-matics,Mar.2001,http://www.hit.bme.hu/phd/vargaa/omnetpp.htm.[5]A.Cerpa,J.Elson,D.Estrin,L.Girod,M.Hamilton,andJ.Zhao,

“Habitatmonitoring:Applicationdriverforwirelesscommunicationstechnology,”inProc.ACMSIGCOMMWorkshoponDataCommu-nications,LatinAmericaandtheCaribbean,Apr.2001.

[6]J.Li,J.Jannotti,D.DeCouto,D.Karger,andR.Morris,“A

scalablelocationserviceforgeographicad-hocrouting,”inProc.ofthe6thACMInternationalConferenceonMobileComputingandNetworking(MobiCom20000),Aug.2000,pp.120–130.

[7]L.KleinrockandJ.A.Silvester,“Optimumtransmissionradiiin

packetradionetworksorwhysixisamagicnumber,”inNationalTelecommunicationsConference.Birmingham,Alabama:IEEE,Dec.1978,pp.4.3.1–4.3.5.

[8]R.Wattenhofer,L.Li,P.Bahl,andY.-M.Wang,“Distributed

topologycontrolforpowerefficientoperationinmultihopwirelessadhocnetworks,”invol.3.Anchorage:IEEE,Apr.2001.

[9]V.RodopluandT.H.-Y.Meng,“Minimumenergymobilewireless

networks,”IEEEJournalonSelectedAreasinCommunications,vol.17,no.8,pp.1333–1344,Aug.1999.

[10]C.Savarese,J.M.Rabaey,andJ.Beutel,“Locationingindistributed

ad-hocwirelesssensornetworks,”inProc.InternationalConferenceonAcoustics,Speech,andSignalProcessing,2001.

[11]T.A.ElBatt,S.V.Krishnamurthy,D.Connors,andS.Dao,“Power

managementforthroughputenhancementinwirelessad-hocnet-works,”inICC2000.NewOrleans,LA:IEEE,June2000.

[12]B.Krishnamachari,R.Bejar,andS.B.Wicker,“Distributedcon-straintsatisfactionandtheboundsonresourceallocationinwirelessnetworks,”inSixthInternationalSymposiumonCommunicationsTheoryandApplication.Ambleside,UK:ISCTA,July2001.

[13]R.RamanathanandR.Rosales-Hain,“Topologycontrolofmultihop

wirelessnetworksusingtransmitpoweradjustement,”inProc.IEEEInfocom,Tel-Aviv,Israel,Mar.2000.

Network lifetime ( x 1000s)120100806040200135791113151719212325272931Configuration numberFig.5.Networklifetimes(inthousandsofseconds)fordifferentconfigurationsforglobalandlocalalgorithms

525048464442403836ETPLMNLMAFig.6.ConfidenceintervalsofnetworklifetimesforlocalalgorithmsandETP;95%confidencelevel

outperformsbothlocalalgorithms.ThisstemsfromthefactthatETPusesglobalinformation,butitisimportanttonotethatLMNdoesnotonlycreateamuchstrongerconnectednetwork,italsoperformsinmeanby14%betterthanLMA.Moreover,thelocalalgorithmsarealmostcompetitivewiththeglobalones.

IV.RELATEDWORK

Inrecentpublicationstheproblemofpowercontrolwasaddressedwhileassuminginformationontheangleofreception[8]orthenodesknowledgeofitslocation[9][10].Inthesepublicationsmorecomplicatedalgorithmsthaninthispaperareused,butastheyuseadditionalinformationacomparisoncanonlybemadeusingthesamemetric.Astherearesimilarapproachestosolvetheproblemofpowercontrolasinthiswork[11][12],theydifferinthatELBATTetal.needsaseparateandcontention-freefeedbackchannelandusesacellularTDMAsystem.KRISHNAMACHARIetal.usesanalgorithmwithanexpo-nentialgrowincontrolmessagesinthenumberofnodes.In[13]RAMANATHANandROSALES-HAINprovidedtheideaforthefirstalgorithmusedinthispaper,buttheyusedthealgorithmtoexaminenetworkthroughputanddelayinatwodimensionalspacewithasmallersetofnodes.

Network lifetime ( x 1000s)