1
SEP:AStableElectionProtocolforclustered
heterogeneouswirelesssensornetworks
GEORGIOSSMARAGDAKISIBRAHIMMATTAAZERBESTAVROSComputerScienceDepartment
BostonUniversity
gsmaragd,matta,best@cs.bu.edu
Abstract—Westudytheimpactofheterogeneityofnodes,intermsoftheirenergy,inwirelesssensornetworksthatarehierarchicallyclustered.Inthesenetworkssomeofthenodesbecomeclusterheads,aggregatethedataoftheirclustermembersandtransmitittothesink.Weassumethatapercentageofthepopulationofsensornodesisequippedwithadditionalenergyresources—thisisasourceofheterogeneitywhichmayresultfromtheinitialsettingorastheoperationofthenetworkevolves.Wealsoassumethatthesensorsarerandomly(uniformly)distributedandarenotmobile,thecoordinatesofthesinkandthedimensionsofthesensorfieldareknown.Weshowthatthebehaviorofsuchsensornetworksbecomesveryunstableoncethefirstnodedies,especiallyinthepresenceofnodeheterogeneity.Classicalclusteringprotocolsassumethatallthenodesareequippedwiththesameamountofenergyandasaresult,theycannottakefulladvantageofthepresenceofnodeheterogeneity.WeproposeSEP,aheterogeneous-awareprotocoltoprolongthetimeintervalbeforethedeathofthefirstnode(werefertoasstabilityperiod),whichiscrucialformanyapplicationswherethefeedbackfromthesensornetworkmustbereliable.SEPisbasedonweightedelectionprobabilitiesofeachnodetobecomeclusterheadaccordingtotheremainingenergyineachnode.WeshowbysimulationthatSEPalwaysprolongsthestabilityperiodcomparedto(andthattheaveragethroughputisgreaterthan)theoneobtainedusingcurrentclusteringprotocols.WeconcludebystudyingthesensitivityofourSEPprotocoltoheterogeneityparameterscapturingenergyimbalanceinthenetwork.WefoundthatSEPyieldslongerstabilityregionforhighervaluesofextraenergybroughtbymorepowerfulnodes.
I.INTRODUCTION
Motivation:WirelessSensorNetworksarenetworksoftiny,
batterypoweredsensornodeswithlimitedon-boardprocess-
ing,storageandradiocapabilities[1].Nodessenseandsend
theirreportstowardaprocessingcenterwhichiscalled“sink.”
Thedesignofprotocolsandapplicationsforsuchnetworks
hastobeenergyawareinordertoprolongthelifetime
ofthenetwork,becausethereplacementoftheembedded
batteriesisaverydifficultprocessoncethesenodeshave
beendeployed.ClassicalapproacheslikeDirectTransmission
andMinimumTransmissionEnergy[2]donotguaranteewell
balanceddistributionoftheenergyloadamongnodesofthe
sensornetwork.UsingDirectTransmission(DT),sensornodes
transmitdirectlytothesink,asaresultnodesthatarefar
awayfromthesinkwoulddiefirst[3].Ontheotherhand,
usingMinimumTransmissionEnergy(MTE),dataisrouted
ThisworkwassupportedinpartbyNSFgrantsITRANI-0205294,EIA-0202067,ANI-0095988,andANI-9986397.overminimum-costroutes,wherecostreflectsthetransmission
powerexpended.UnderMTE,nodesthatarenearthesinkact
asrelayswithhigherprobabilitythannodesthatarefarfrom
thesink.Thusnodesnearthesinktendtodiefast.Underboth
DTandMTE,apartofthefieldwillnotbemonitoredfora
significantpartofthelifetimeofthenetwork,andasaresult
thesensingprocessofthefieldwillbebiased.Asolution
proposedin[4],calledLEACH,guaranteesthattheenergy
loadiswelldistributedbydynamicallycreatedclusters,using
clusterheadsdynamicallyelectedaccordingtoapriorioptimal
probability.Clusterheadsaggregatereportsfromtheircluster
membersbeforeforwardingthemtothesink.Byrotatingthe
cluster-headroleuniformlyamongallnodes,eachnodetends
toexpendthesameenergyovertime.
MostoftheanalyticalresultsforLEACH-typeschemesare
obtainedassumingthatthenodesofthesensornetworkare
equippedwiththesameamountofenergy—thisisthecase
ofhomogeneoussensornetworks.Inthispaperwestudythe
impactofheterogeneityintermsofnodeenergy.Weassume
thatapercentageofthenodepopulationisequippedwith
moreenergythantherestofthenodesinthesamenetwork—
thisisthecaseofheterogeneoussensornetworks.Weare
motivatedbythefactthattherearealotofapplications
thatwouldhighlybenefitfromunderstandingtheimpactof
suchheterogeneity.Oneoftheseapplicationscouldbethe
re-energizationofsensornetworks.Asthelifetimeofsensor
networksislimitedthereisaneedtore-energizethesensor
networkbyaddingmorenodes.Thesenodeswillbeequipped
withmoreenergythanthenodesthatarealreadyinuse,which
createsheterogeneityintermsofnodeenergy.Notethatdue
topractical/costconstraintsitisnotalwayspossibletosatisfy
theconstraintsforoptimaldistributionbetweendifferenttypes
ofnodesasproposedin[5].
Therearealsoapplicationswherethespatialdensityofsen-
sorsisaconstraint.Assumingthatwiththecurrenttechnology
thecostofasensoristensoftimesgreaterthanthecostof
embeddedbatteries,itwillbevaluabletoexaminewhetherthe
lifetimeofthenetworkcouldbeincreasedbysimplydistribut-
ingextraenergytosomeexistingnodeswithoutintroducing
newnodes.1
1Wealsostudythecaseofuniformlydistributingsuchextraenergyoverallnodes.Inpractice,however,itmaybedifficulttoachievesuchuniformdistributionbecauseextraenergycouldbeexpressedonlyintermsofdiscretebatteryunits.Evenifthisispossible,weshowinthispaperthatsuchfairdistributionofextraenergyisnotalwaysbeneficial.