Clustering objectives in wireless sensor networks: A survey and research direction analysis

ContentslistsavailableatScienceDirect

Computer Networks

journalhomepage:www.elsevier.com/locate/comnet

Clustering objectives in wireless sensor networks: A survey and research direction analysis

Amin Shahraki

, Amir Taherkordi

, Øystein Haugen

, Frank Eliassen

aDepartment of Informatics, University of Oslo, Oslo, Norway

bFaculty of Computer Sciences, Østfold University College, Halden, Norway

a r t i c le i n f o

Keywords:

Wireless sensor networks Clustering

Survey Routing

Cluster head selection Topology management

a b s t r a ct

WirelessSensorNetworks(WSNs)typicallyincludethousandsofresource-constrainedsensorstomonitortheir surroundings,collectdata,andtransferittoremoteserversforfurtherprocessing.AlthoughWSNsareconsidered highlyflexiblead-hocnetworks,networkmanagementhasbeenafundamentalchallengeinthesetypesofnet- worksgiventhedeploymentsizeandtheassociatedqualityconcernssuchasresourcemanagement,scalability, andreliability.Topologymanagementisconsideredaviabletechniquetoaddresstheseconcerns.Clusteringis themostwell-knowntopologymanagementmethodinWSNs,groupingnodestomanagethemand/orexecuting varioustasksinadistributedmanner,suchasresourcemanagement.Althoughclusteringtechniquesaremainly knowntoimproveenergyconsumption,therearevariousquality-drivenobjectivesthatcanberealizedthrough clustering.Inthispaper,wereviewcomprehensivelyexistingWSNclusteringtechniques,theirobjectivesand thenetworkpropertiessupportedbythosetechniques.Afterrefiningmorethan500clusteringtechniques,we extractabout215ofthemasthemostimportantones,whichwefurtherreview,catergorizeandclassifybasedon clusteringobjectivesandalsothenetworkpropertiessuchasmobilityandheterogeneity.Inaddition,statistics areprovidedbasedonthechosenmetrics,providinghighlyusefulinsightsintothedesignofclusteringtechniques inWSNs.

1. Introduction

WirelessSensorNetworks(WSNs)areatypeofad-hocnetworktech- nologywhichemergedmorethan20yearsago[1]formonitoringpur- posesinmilitaryapplications[2].WSNsusuallyincludealargenum- berof sensornodes(inshortcalled nodes)whicharefundamentally resource-constrained,butcanconnecttoothernodesofthenetworkfor transmittingsenseddata.Themaintaskofeachnodeismonitoringthe environmentusingtheon-boardsensors,besidesitspossiblecapabilities toactasarelayordatafusionnode.Eachnodecanbeusedasarouter toforwarddatafromneighborstothesinkorBaseStation(BS).BScan processdatalocallyoractasthegatewayofthenetworktotransferdata toremoteservers.

Thankstothedynamicinfrastructureandefficienttransmissionof datainWSNs,theirapplicationareasarequitediverse[3].Inthepast twodecades,variousapplicationshavebeenproposedforWSNs,such asenvironmentmonitoring[4],healthcare[5],smarthomes[6],smart factories[7],anddisastermanagement[8].AlthoughWSNsareconsid- eredhighlydynamicad-hocnetworks,networktopologymanagement hasbeenafundamentalchallengein thesetypesof networks[9],in particularresourcemanagement,scalability,reliability,andefficiency.

∗Correspondingauthor.

E-mailaddress:am.shahraki@ieee.org(A.Shahraki).

Topologymanagementisregardedasaviabletechniquetoensure stable,reliable,trustworthyandefficientnetworkinfrastructuresinad- hocnetworkslikeWSNs[10,11].Clusteringisoneofthemostpopular techniquesforWSNtopologymanagement.Aclusteringtechniqueor- ganizesnodesintoasetofgroupscalledclustersbasedonasetofpre- definedcriteriasuchassupportingQualityofService(QoS),optimizing resourceconsumption,networkloadbalancing,etc.[12].Eachcluster hasoneormoreClusterHeads(CHs)whichgatherdatafromothernodes intheclustercalledmembersandsendthe(fused)datatoBSdirectly,or indirectlyusingothernodescalledmiddlemennodes.Usingclustering techniques,resource-constrainednodesdonotneedtosendtheirdata togateways(sink)directlywhichcancauseenergydepletion,resource consumptioninefficiencyandinterference.

WSNclusteringtechniqueshavebeenreportedinseveralresearch papers.ThereexistanumberofsurveysonWSNclustering,suchas[13–

16].However,mostofthemcoveronlymainclusteringtechniquessuch asLEACH[17],HEED[18]andFLOC[19],asfundamentalmethodspro- posedindifferentformsandextensions.Somesurveypapersconsider onlyonemetricindesigningclusteringtechniquesornetworkinfras- tructureslikeunequalclusters[16].Moreover,anumberofothersurvey workshavestudiedtechniquesderivedfromthemaintechniques.For

https://doi.org/10.1016/j.comnet.2020.107376

Received2March2020;Receivedinrevisedform17June2020;Accepted19June2020 Availableonline20June2020

1389-1286/© 2020TheAuthors.PublishedbyElsevierB.V.ThisisanopenaccessarticleundertheCCBYlicense.(http://creativecommons.org/licenses/by/4.0/)

example,in[20]theauthorsindicatethattherearemorethan60ex- tendedversionsoftheLEACHprotocolintheliterature.Besides,insome surveypaperslike[21],clusteringhasbeenstudiedfromtheviewpoint ofreducingenergyconsumption,whileitisnotthesolereasonforclus- tering.Toconclude,mostclusteringsurveypapersstudyandcompare clusteringtechniquesandtheirefficiency,whiletheyfailtofocuson comparingobjectivesofthosetechniques.Moreover,tothebestofour knowledge,nosurveypaperstudiesexistingclusteringtechniqueswith respecttotheWSNnetworkpropertiesthattheysupport,suchashetero- geneityandmobility.

Thismotivatedustoprovideacomprehensivesurveyonobjectives ofclusteringinWSNs.Inthispaper,WSN-basedclusteringtechniques arereviewedbasedontheobjectivesachievedbyclusteringsuchasQoS, faulttolerance,loadbalancing,etc.Inaddition,weevaluatethosetech- niquesbasedontheircompatibilitywithdifferentnetworkcharacteris- tics,e.g.,heterogeneityandmobility.Finally,weanalysetheresearch directiononclusteringtechniquesandprovideastatisticalmodeltomo- tivatescientiststoutilizeclusteringinaddressingnetworkmanagement challenges.Moreover,thissurveyallowsfindingandevaluatingcluster- ingtechniquesthatsupportagivensetofobjectives.

Themethodologyweadoptedforconductingthissurveyconsistsof thefollowingsteps.First,weextractedthelistofmainWSNclustering techniquesfromtherelevantpapersinreputablejournals,conferences andworkshops,e.g.,ICCCN,WCNC,GLOBCOMM,ICPS,CNCS,SECON, IPDPS,ICDCS,INFOCOM,ITPDS,IEEEIoTJ,ITWC,ITN,ITVT,TOSN, ATSNandIEEETNSM,tonamethemostimportantones.Basedonthe extractedrelevantpapers,wethencheckedtheirreferencesandrelated worktofindotherpapersthatwereconcealed.Havingthemainclus- teringtechniquescompiled,wefinallysearchedforallotherresearch worksthateithercitedthemaintechniqueslikeLEACH[17]orpro- posedtheirownclusteringsolution.Forthat,wehadtoreadandrefine about500papers.Finally,over215paperswereextractedasthemost relevantclusteringtechniquesthatcanbeusedinWSNstoachievevar- iousobjectives.

Themaincontributionsofthisstudyinclude:

• ProvidingacomprehensivesurveyonclusteringtechniquesinWSNs focusingonclusteringobjectivesandnetworkproperties

• Reviewingthemostcommonsolutionsusedbyclusteringtechniques toachievetheidentifiedobjectives.

• Providingastatisticalanalysisofobjectivesofclusteringtechniques andnetworkpropertiessupportedbytheliteraturetoanalyzethe directionoftheresearchinthisfield.

Thispaperisorganizedasfollows.Section2describesthebasiccon- ceptsofclusteringandclusteringtechniques.Section3presentsacom- prehensiveviewofclusteringtechniquesinWSNswithrespecttothe networkpropertiesandtheobjectivesofclustering,inadditiontore- viewingstatistically theavailableclusteringtechniquesin Section4. Finally,in Section5,weconcludethispaperwithasummaryofthis surveywork.

2. Clustering:Basicconceptsandtaxonomy

Topologymanagementisoneof themainchallengesindesigning computer networks,especiallyin ad-hocnetworks as thenumberof nodesisconsiderablyhighandthenetworkinfrastructureisnotreli- able[22].Intopologymanagementtechniquesinad-hocnetworks,de- terminingpossibleneighborstoestablishconnectionsandrecognizing thebestneighborsforhop-by-hopdatatransmissionarecrucialtothe improvementofscalability,resourceconsumption,reliability,etc.Clus- teringisatypeoftopologymanagementtechniqueswhichcangroup nodestoimprovetheefficiencyofthenetworkbymanagingresources androtatingresponsibilitiesamongnodestoprovidefairness.Eachclus- teriscomposedofanumberofmembersandhasoneormoreCHsto managethemembers,aswellastofuse,process,transferandmanage members’data.Finally,eachnetworkhasoneormoreBS(s)whichcan

Fig.1. Differentstructuresofclusteringtechniques.

beusedasgatewaysorlocaldataprocessingnodes.BS(s)receivesdata fromCHsdirectlyorindirectlythroughnodesbetweentheCHandBS, calledmiddlemennodes.Therearesomephasestoestablishclustersand provide connectionbetweenmembersandBS(s)which areexplained below.

2.1. Clusteringphases

Generally,clusteringincludestwomainphases:groupingnodesand allocatingresponsibilities.GroupingisgenerallybasedonVoronoidia- grams,butalsocanbenon-Voronoilikechainorspectrum.IntheVoronoi structure,a2Dor3Dnetworkenvironmentisdividedintoseveral(un- equal)sectionscalledclusters.Eachclusterpossessessomenodesand interactswithotherclustersthroughCHsorgateways.Inchainstruc- tures,nodesinaclusterconnecttoeachothertoreachCHs.Inother words,eachnodehasonlytwoconnectionswithneighborsinthechain toreachCHs.Inthespectrumstructure,anglesofnodestoBSareasim- portantasthedistancetoBS.Nodeanglesaregenerallycapturedbythe ScanningSweepmethod[23].Clustersareestablishedbasedondiffer- entanglesanddistances.Fig.1showsdifferentstructuresofclustering andtheircomparisons. Inbothspectrumandchainstructures,layer- ingcanbeperformedwhichrealizesmulti-hopdatatransmissionand improvestheefficiencyofthenetwork,especiallyintermsofresource consumption.Indirectconnectionbetweenthesourceanddestination reducesenergyconsumptionbybreakingalongjourneyfromanodeto CHtoshorterjourneys,calledintra-clusterrouting.However,usingthis routingmethodcancauseQoSissuessuchasincreasingdelay.Similar totheconnectionbetweenCHsandBS(s),nodesinclusterscanconnect totheirCHsdirectlyorindirectlythroughothermembersofthecluster.

ClusterEstablishmentMethods:Therearetwomethodstoestab- lishclustersinanetwork:

• Determiningclustersbygroupingnodesandselectingoneormore nodesasCH(s)ofthecluster:Nodesgroupingcanbebasedondif- ferentparameters,mainlyphysicalproximity.Inaddition,balanced clustersintermsofclustersize,numberofnodesornetworkloadcan beusedasotherparameterstogroupnodesandestablishclusters.

Moreover,high-levelparameterscanbeusedforgroupingsuchas similarityofservicesinapplicationssharingthesamenetwork,data gatheringanddatafusionalgorithms,andsupportingdifferentQoS parameters.

• DeterminingCHsandinvitingothernodestojoinaneighborCH:

ThismethodisbasedonparameterssuchasdistancetoCHand/or distanceoftheCHtoBS,similarityoftheapplicationsrunningonthe memberswithrespecttodatafusion,orhostingrequestedservice(s) bytheCH.

GeneralCHSelectionMethods:ToselectCHs,anumberofgeneral methodsareavailableaslistedbelow:

• Inafewclusteringtechniques,resource-richnodesarepredetermined asCHs[24].TheproblemwiththismethodisthatmostWSNsareho- mogeneousandresource-constrained.Therefore,themethodisnot operationalinseveralcases.Inaddition,evenifaresource-richnode inaheterogeneousnetworkcanbefoundandselectedasaCH,be- ingCHforalongtimewilldrainthenodepowerquicklyandcause nodedeath.Moreover,ifCHsarefixed,mobilenodesanddynamic- ityofthenetworkcanunbalancetheclustersintermsofthenumber ofmembersorvolumeoftransferreddatawhichcausesunbalanced networkloadandresourceconsumption.

• Insomeclusteringtechniques,randomnessisthesolutiontocirculate theCHresponsibilityamongnodes,e.g.,LEACHasthemostwell- knownclusteringtechnique[17].Althoughthistechniqueisbene- ficialinhomogeneousnetworks,anydynamicityorunbalancingin WSNscan createintensiverun-timeproblemslikechronicenergy consumptioninsomeCHsorunbalancedresourceconsumption.

• ThemostcommonsolutionforCHselectioniscalledconsciousCH selectionwhichisbasedonnodesandnetworkcircumstances.Sev- eralworksintheliteratureproposeclusteringmethodsbasedonthis solution[25–27].Inthesetechniques,CHsareselectedbasedondif- ferentparameterssuchasavailableresources,location,numberof neighbors,etc.CHselectionmethodscanimprovetheefficiencyof thenetworkbyselectingnodesthataremoreappropriatetobeCHs [260].Additionally,somemethodsaredesignedtoreactagainstany unforeseeablecircumstancesbyre-selectingorreplacingCHswith moreappropriatenodesdynamically.

Toselectthebest CHs, clustering methodscan use centralized or distributedCHselectionmethods.Incentralizedtechniques,parameters whichareusedtoselectCHs,aregatheredinacentralnode(generally BS)andcompared,analyzedandprocessedforselectingCHs.Although centralizedmethods canhave universal resultsdue tocomparing all nodes,theyoftenhavehighoverheadforlargeand/orhighlydynamic networks,especiallywhenCHsarere-selectedonaregularbasis.Insuch networks,severalmanagementpacketsshouldbeexchangedwhichcan consumeplentyofresourcesandreducetheefficiencyofthenetwork.

Ontheotherhand,distributedmethodshavelessoverhead,butdueto theirlimitednetworkinformation(i.e.,onlyneighbornodes),selected CHscannotoftenfulfillallnetworkrequirements.

Re-clusteringMethods:Noteverynodecanbe usedasCHfora longtimebecauseofresourcedepletion,therebythedutyofbeingCH shouldberotatedamongappropriatenodesduringthenetworklifetime.

Re-selectingCHscanrotateresponsibilitiesamongnodes,normallyhap- peninginthere-clustering(setup)phase.Therearetwomethodstotrig- gerre-selection:i)Time-basedmethod:Thenetworkwillbere-clustered atacertaintimetobalanceresourceconsumptionamongnodes.This methodisgenerallyusedinhomogeneousnetworkswhichcanhavepre- determinednetworkload,andii)Event-basedmethod:Aneventtriggers partoforthewholenetworktore-selectCHsandpossiblyre-cluster, exceedingresourceusagethresholdslikeenergy,CPU,bandwidthcon- sumption,orhighresourceconsumptioninadeterministictime.Com- biningtime-basedandevent-basedmethodscanbeusedforre-clustering aswell,dependingonwhichre-clusteringconditionholdsfirst,thecor- respondingmethodwillbetriggered.

Re-clusteringcanbelocalorglobal.Intheglobalcase,thewhole networkshouldbere-clusteredwhichhashighoverheadbutinthelocal case,partofthenetworkorjustaclusterwillbere-clustered.

Clustering-basedDataForwarding:Thedatageneratedbynodes canbetransferredinitsrawformatorasafusedvalue.Differenttech- niquesareusedtofusedata,mostlyonCHs.TheCHcantransmitin- dividualdataitemstoBSoraggregatethemandsendtheaggregated datavaluestoBS.Therearetwomethodstotransmit(fused)packets fromCHstoBS(s).CHscansenddatadirectlytoBSorusemiddlemen nodes(whichareoftenotherCHs)totransferdatatoBScalledinter-

clusterrouting.Onthecontrary,inthedirectcommunicationeachCH isresponsibletotransmitdatadirectlytoBS(s)whichcancauseenergy depletionbasedonEq.1[28].

𝐸𝑡𝑟𝑎𝑛𝑠𝑚𝑖𝑡=𝐹(𝑑²) (1)

Similartointer-clusterrouting,intra-clustertechniquesareproposed tobalancetheloadandenergyconsumptionwithinclusters.Although directcommunicationinbothroutingtechniquescanreducedelayand improveQoS,itincreasesenergyconsumptioninCHsandcausesenergy depletionsimultaneously.Differenttrade-off techniquesareproposed forselectingdirectorindirectdatatransmissioninclusteringtechniques likethemethodproposedin[28].Sincecommongroupingtechniques arebasedonnodesthatareneareachotherphysicallyandprovidedata forthesameapplication,itismoreefficenttoperformdataaggregation inCHsandreducetheamountofdatatobetransmittedtoBS.Thiscan significantlyimproveenergysavingonsensornodes.Moreover,having clustersinWSNs,itispossibletomakesomedecisionsbasedoninfor- mationlocallyavailableineachcluster.Thedecisionscanberelated tohowtodealwithdifferentsituationsinapartofthenetwork(i.e.,a cluster)suchasfaults,mobilenodes,andQoSviolations.

3. ClusteringinWSNs

WSNsappearindifferentformsandtypes,suchasTerrestrialWSNs [29], Underground WSNs [30], UnderwaterWSNs [31], Multimedia WSNs[32],MobileWSNs,andWirelessSensorandActuatorNetworks (WSANs) [33]. WSNsare oftenconsidered asinfrastructure-less net- works[34]suchthatthenodesshouldcooperatetoestablishanetwork, andgatherandtransferdata.Duetotheresourcescarcenessofsensor nodes,resourcemanagementisabigchallengeespeciallyinWSNswith amassivenumberofnodesoutofwhichmanynodesmayactasdatafor- wardingnodes.Sincewirelessdatatransmissionisthedominantenergy consumerin sensorplatforms,weneedtocarefullymanage resource consumptioninWSNsandinparticularenergyusage.

Tosupportbothresourceconsumptionoptimizationanddatafusion, differentmethodshavebeenproposed.Thefirststraightforwardmethod istoaddressresourceefficiencyinalgorithms.Giventhatenergycon- sumptioninwirelessnetworksisafunctionofdistance,routingcanre- duceenergyconsumption bydividinga longrouteintoanumberof smallerroutes.However,atthesametimeroutingmethodsneedtotake intoaccountrequirementssuchasdatafusion,faulttolerance,andload balancing.Nodeclusteringisrecognizedasapopulartechniquetoim- provetheefficiencyofroutingmethodsandsolvetheaforementioned issues.Duringtheyears2000to2019,manyclusteringtechniqueshave beenproposed.PrimaryWSNclusteringtechniquesthatwereproposed morethanadecadeago,includeLEACH[17]andHEED[18].Inthese clusteringtechniques,themaingoalistoreduceenergyconsumption andimprovesomeaspectsofthenetworksuchasloadbalancing.

Inthissection,westudyallsignificantclusteringmethodsbasedon areviewofmorethan215researchpapersandarticles.Unlikeother surveyworks,wedonotfocusonthedesigndetailsofclusteringmeth- odslikealgorithmcomplexity,methodology,etc.Rather,wereviewthe mostsignificantclusteringtechniquesinWSNsbasedontheirobjectives andthesupportofvariousnetworkpropertiessuchasnodeheterogene- ity,nodemobility,etc.Table1showsacomprehensiveoverviewofthe mostimportantclusteringtechniquesinWSNsderivedfromtheabove mentionedreview.

The table lists the clusteringtechniques, objectives and network propertiessupportedbythem.Thecomprehensivelistoftechniquesin TableIallowsfilteringthembasedonthedesiredpropertiesandobjec- tivesforclustering.Itshouldbenotedthattherearesomeminorcluster- ingobjectivesthatarenotlistedamongthesetofcommonobjectivesin Table1sincetheyarespecifictoatechnique.Suchtypesofobjectives areaddedinfrontofeachclusteringtechniqueinthetable.Tothebest ofourknowledge,thistableis,todatethemostcomprehensivelistof existingclusteringtechniquesofWSNs,theirpropertiesandobjectives.

Inaddition,inTable3,thenumberofpapersperobjectiveandprop- ertyofclusteringislistedwhichareextractedfromTable1.Thestudied designparametersinclude:

Node Heterogeneity: Heterogeneity can appear in different re- sources like energy, computation power, network interfaces, etc.

Resource-rich nodescan beleveraged for datatransmissiontoassist otherresourcepoornodes,therebyresource-constrainednodescanstay aliveforalongerperiodoftimethantheycanachievebythemselves..

Usingresource-constrainednodesincollaborativetaskslikedatatrans- mission can causedifferent problems suchasenergy depletion,QoS degradation,nodefailure,etc.Heterogeneitycanhaveahighimpact onnetworkefficiencybysharingavailableresourcesofdifferentnodes

toexecuteatask.Ontheotherhand,heterogeneousnetworksfacemany challengesinmanagingandallocatingresourcesefficiently.Incluster- ingtechniques,nodeheterogeneityisanadvantagewhenselectingCHs, becausenodesthathavemoreresourcesaremoreappropriatetobeCH.

However,selectingthebestnodesasCHsmayleadtootherefficiency issuesthatarediscussedlaterinthissection.

RoleofCH:ThisindicateswhattheprimaryroleofCHinacluster is,aswellasinthenetwork.Generally,CHsinWSNsarenotincharge ofperformingcomplicatedtasks,thustheparameterstoselectCHsare oftenlimitedtoenergyanddataforwardingresources.However,some clusteringtechniquesutilizeCHsfordatafusion,inwhichthecriterion forselectingaCHisthecomputationpowerofnodes.

Table1

ClusteringTechniques.Thereferencescitedinthistableare[17–19,24,35–244].

( continued on next page )

Table1(continued)

( continued on next page )

Inter-clusterRouting:Usinginter-clusterroutingenablescluster- ingtechniquestosupporthierarchicaldatafusion,caching,compression andimprovingloadbalancing,energyconsumption,etc.Anobjectiveof inter-clusterroutingisalsoprovidingaconnectednetworkinfrastruc- turesuchthatthemembersofvariousclusterscanconnecteachother withoutusingtheBS.Inter-clusterroutingallowsCHstosenddataindi- rectlytotheBSthroughotherCHs,ratherthandirectdatatransmission toBS.Inter-clusterroutingmethodsmaycomewiththeirbuilt-inrout- ingmethodortheycanusetypicalmethodslikeAd-hocOn-demandDis- tanceVector(AODV).Usinginter-clusterroutingenablesthenetworkto

connectclustersresultinginconnectingmembersofclustersasanad- hocnetwork.Thisimprovesefficiencybyresourcesharingandrunning distributedtasks.Wedonotconsiderintra-clusterroutinginourevalua- tion,becauseitismainlyusedtoreduceenergyconsumptioncompared tointer-clusterroutingthatprovidesconnectionamongclustersresult- inginconnectingallnodesofanetwork.Incaseofrouting,ourfocus liesonclusteringtechniquesthatcanprovidemoreconnectionsamong nodes,butthemainobjectiveofintra-clusterroutingisimprovingre- sourceconsumption.

Table1(continued)

Mobility:Mobilityisoneofthemostimportantfactorstoevaluate theapplicabilityofclusteringtechniquesinWSNsasalargenumber ofWSNapplicationsaremobile[245].Mobilitycaneffecttheperfor- manceofthenetworkintermsof,e.g.,connectivityandQoS,andis relatedtosupportingmobilenodesinclustering.Clusteringtechniques thatcanhandlemobilityaresimilartohighlydynamicnetworks.Inour survey,aclusteringtechniqueisclassifiedassupportingmobilityifit isappliedtonetworkswheremostofthenodesaremobile.Iftheonly

mobilenodeis(are)BS(s)inamethod,itisnotconsideredasamobility supportmethodinoursurveybecausemobileBS,insuchscenarios,isto easecreatingclustersandgatheringclusterdata.Inotherwords,itisan extrafeatureofclusteringtechniquestobemoreefficient,butinreality, therearenotmanyreal-worldapplicationswhereBSistheonlymobile node.

ClusteringObjectives:Themostcriticalparameteristhedesignob- jectivesofclusteringtechniques.Objectivesshowhowthemethodcan

Table2

StatisticsofcharacteristicsandObjectivesofsurveyedclusteringtechniques.

improvetheefficiencyofthenetwork.Aclusteringtechniquecanbe designedtosupportdifferentobjectivessimultaneouslyorfocusona soleobjective.Objectivegroupsofclusteringtechniquesarelistedbe- low.Inaddition,commonsolutionsproposedbyclusteringtechniques toachieveobjectivesandaddressnetworkingchallengesaredescribed foreachobjectivetogetherwithafewexamplesfromTable1.Itisnote- worthythatthelistofobjectivesandsolutionsincludethemostrelevant ones,butalsoincasesthattheobjectiveofaclusteringtechniqueisnot inthemost-commonobjectiveslist,itisaddedinfrontoftheclustering technique.

1. EnergyConsumption(E):AsthemostimportantobjectiveinWSNs, clusteringtechniquesareaimedtobalanceenergyconsumptionand improvethenetworklifetime.Themostenergyconsumingtaskin WSNsistransferringdatafromnodestoBS[28].Asanad-hocnet- work,WSNnodesmayuseroutestotransfer(aggregated)datatoBS whichcancauseunbalancedenergyconsumption,becausemiddle- mennodesconsumemoreenergythanothersbyforwardingand/or aggregatingpackets.Directcommunicationcauseshighenergycon- sumptionduetoEq.1whichmakesindirectcommunicationmore attractivedespitethecomplexityofdeterminingtooptimizeroutes.

Tooptimizeenergyconsumptionusingclusteringtechniques,some techniquesareproposedwhicharelistedbelow:

• CHDutyRotation:InWSNs,CHsconsumealotofenergycom- paredtoclustermemberswhichcausere-clustering tochange CHs (middlemen) andbalanceenergy consumption [246]. As amulti-objectiveselectiontechnique,CHselectionisacompli- catedtaskwhichcanbecarriedoutusingdifferentmethodslike Fuzzylogic[247–249],AImethods[250],andheuristicmeth- ods[251–253].CHsascentralnodestogatherandtransferdata in WSNs shouldsupport the different networkobjectiveslike

QoS,reliability,dataaggregation,etc.,inadditiontobalancing energyconsumption.ConventionalmethodstorotateCHduty haveathresholdforenergyconsumptionorremainingenergy ofnodeswhichcantriggernetworkre-clustering.Additionally, otherthresholdslikeQoSthresholdscanbeusedinWSNsclus- teringtechniquestoachieveparticularobjectives.

Inhomogeneousnetworks,selectingCHsisamorecomplicated taskbecauseallnodeshavethesameresources.Resourceslike energyandcomputationpowerwillbeconsumedandoccupied, respectively, whichcan causetriggering of re-clustering[26]. Beingheterogeneousindifferent aspectsmakesCHselectiona multi-objectiveproblem.Besides,dynamicityinanetworkcan changethenetworkloadwhichcan triggerthenetworktore- clusterandselectnewCHsorchangetheroutes,atleast.Asan example,EECS[63]isamethodinwhichthemainparameter forselectingCHsistheresidualenergy.Theyconsiderthatthe clustersclosertotheBSshouldbesmallerbecausetheyneedto transferdatafromupperlayersinadditiontoaggregatingand transferringdataoftheirmembers.However,energyconsump- tioninaclusterwhichisfarfromBSisstillachallenge.InCOCA [139],theauthorsproposeaclusteringarchitecturetoimprove energyefficiency.Theyestablishthenetworktopologybasedon units.Eachunitcontainssomeclusters.Limitingthenumberof unitscanguaranteetobalanceenergyconsumption byhaving balancedclusters.Theyalsousetheresidualenergyofnodesas aparametertoselectCHswhichbalancestheenergyconsump- tionamongnodes.

• Hierarchical Clustering: hierarchical or layered clustering is a methodthatdividesthenetworkintodifferentlayers.Eachlayer caninteractwithneighboringlayers,whichsavesenergy.Inlay- eredandhierarchicalclusteringtechniquesmiddlemenintheup- perlayers(closertotheBS)consumemoreenergyastheyshould transfermassivevolumeofdatafromlowerlayerstoupperlayers toreachBS.Differenttechniquesareusedtobalancetheenergy consumptionof middlemenin thelowerlayersandtheupper layers.Onepopularmethodisestablishingunbalancedclusters.

Clustersin thelowerlayers can havemore membersascom- paredtotheupperlayers.Sincereceivingdataconsumesafixed amountofenergy,CHsofthelowerlayerscanhavemoremem- bersbutdonotneedtoforward(aggregate)manypacketsfrom otherlayers;thereforeunbalancedlayers/clusterswouldbean appropriateoptiontobalanceenergyconsumption.InEA-CRP [201],theauthorsproposedaunit-basedmethodinwhicheach layercontainsunitstominimizelong-distancecommunications usinglayersof equalsizeclusters.LayersthatareclosertoBS havelesswidthbutalsothenumberofunitsperlayerincreases.

EachunithastwoCHstoaggregatedataandestablishesinter- layercommunications,respectively.

• BalancedClusters:Althoughunbalancedclusteringisasolutionin hierarchicalclustering,itwouldbeachallengeinWSNsinwhich locationdistributionofnodesisnoteven.Networksthathavean unbalancedlocationdistributionofnodesneedtobalancethe clusterstofacewiththeirintrinsicunbalancing.Byhavingun- balancedclustersinsuchanetwork,someCHsconsumemore energyduetogatheringdataofseveralmembernodes.Tohave fairenergyconsumption,clustersshouldbebalancedbasedon thenumberofnodesandlayers,notthesize.InTL-LEACH[50], level-basedCHsareintroducedinwhichthefirstlevelCHcon- nectstothe2ndlevelwhichisconnectedtoallmembers.1stlevel aggregatesdataand2ndlevelaggregatesdataof1stlevelwhich canreducethenumberofpacketsreceivedbyBSandimprove energyconsumption.

2. LoadBalancing(L):Loadbalancingisthesecondmostimportant objectiveofclusteringinWSNsaccordingtoTable3.Ingeneral,clus- teringtechniquesuseatypeofdivideandconquermethodtotransfer datafromnodestoBS.Adatatransferloadcanresultinunbalanced

energyconsumption,networkcongestion,dataloss,andinefficiency insupportingreal-timeanddata-intensiveapplications.Inclustering techniques,loadbalancing canalsosolvethe“Hotspotproblem” whichisacommonprobleminWSNs[231,254].TheHotspotprob- lemisasituationinwhichsomenodesinanetworktransferhigher volumeofdatathanothers.Loadbalancingbydistributingpacket streams,generatedinlowerlayersamongforwarderstotransferto upperlayersandBS,isachallengingproblem..Therefore,inindirect communication,eachroutefromlowerlayerstoBSshouldtransfera balancedamountofdatatosupportloadbalancingbasedonshared resourcesthroughtheroutes.Asolutioninheterogeneousnetworks istolet nodeswithmoreresources transfermoredata.However, therearestillsomechallengestosupportloadbalancing,especially inhierarchicalindirectcommunicationbetweenCHsandBS,e.g., determiningthebestroutesbasedondifferenttypesofsharedre- sourcestosupportaspecificobjective.Sometechniquestobalance theloadofthenetworkinWSNsbyclusteringtechniques,havebeen proposed:

• MoreLayers,MoreCHs:havingmoreCHsallowsdistributingnet- workloadamongmoremiddlemen.ThiscansolvetheHotSpot problem.Moreover,havingmorelayersinhierarchicalcluster- ingcanextendthenumberofhopswhichincreasesthechance ofusingdifferentCHsinroutingdatafromnodestoBS,enabling networkloadbalancing.

• BalancedClusters:Balancingclustersintermsofvolumeofgen- erateddatawouldbeasolutionthatcanbalancethenetwork load,especiallyindirectcommunication.Ifnodesarehomoge- neous,thenumberofnodescanbeaparametertobalancethe loadamongclusters,althoughinunbalancednetworksusingthe numberofnodesasthemetriccanresultsinunbalancedclusters intermsofsize.Thiswillleadtomoremoreenergyconsumption becauseofthedistancebetweenCHandmembers.Inheteroge- neousnetworks,thegeneratedpacketratepernodecanbeapa- rametertobalanceclusters,butthepacketrateisachallenging andresource-consumingparameter[259]topredictandprocess on-the-fly.

• CongestionControl:Evaluatingtheefficiencyofeachrouteinin- directcommunicationcanupdateandoptimizeparallelroutes fromacluster(orlayer)toBStobalancethenetworkload.Hav- ingmultipleroutesfromonesourcetoonedestinationcanalso dividethenetworkloadwhichcangenerallyavoidnetworkcon- gestion.

• BalancedEnergyConsumption:Asdatatransmissionisthemost importantcauseofenergydepletion,fairdistributionofenergy consumption amongnodescan improveloadbalancingsimul- taneously,becausethereis ahighcorrelationbetweenenergy consumptionandtheamountoftransferreddata.

3. Quality of Service: To support QoS in WSNs, different aspects shouldbeconsidered,suchasoptimizingjitterandthroughput,and minimizingdelay,etc.SupportingQoSinWSNsasanad-hocnet- workhasalwaysbeenachallengingissue.Inthefollowing,wedis- cussexistingsolutionsconcerningeachindividualQoSparameter.

• Reliability(R):Onemetricforreliabilityistherateofsuccess- fuldatatransmissionincomputernetworks.InWSNs,clustering techniquescanimprovethereliabilityofthenetworkbyavoid- ingnodedeathandmaintainingconnectivity. Asanexample, in [232]theauthorsimprovethepacketdeliveryratio toen- hancethereliabilityof thenetwork.In[238],theauthorsde- sign a method which can reduce inter-cluster communication costtoimprovereliabilityindatatransmission.Theproposed methodestablishesatreetodetermineconnectionsbetweentwo nodesbasedonaweightingmethod.Anytwonodesthathaveno connectionorunreliableconnectionwillreceiveahighpenalty intheweightingmodeltoreducethenumberofroutesamong nodes. The method will determinean edge with a minimum weightforeachnodetoimprovereliability.

• Delay(D):Asclusteringtechniquesgatherdatafromnodesand transferthemtoBS(s)directlyorindirectly,optimizingtheeffi- ciencyofclusteringtechniquescanreducedelay(i.e.,end-to-end Delay).Generally,thereisatrade-off betweenenergyconsump- tionanddelay[28].Therearesomegeneralsolutionstoreduce delayusingclusteringtechniquesaslistedbelow:

• Reducing NumberofHops: generally,byreducing thenum- berofhopsbetweennodesandBS,thedelayisreduceddue tolessnumberofqueuestoforwardpacketsinmiddlemen nodes whichcause latency.The optimalsolutionin terms ofreducinglatencyissendingdatadirectlyfromeachnode toBSbutthiscauseshigherenergyconsumption.Therefore, toreducedelayandreduceenergyconsumptionsimultane- ously,routingmethodsshouldbeusedtoimproveroutesand reducehops.Eachhopshouldbestable,efficientandavoid networkcongestion,otherwisereducingthenumberofhops cannotreducedelay.In[50],theauthorsintroduceaclus- teringmethodthatlimitsinter-clusterroutingtotwohops.

Byhavingamaximumoftwohops,thedelaycanbelimited.

In[37,57,67],theauthorsusetwofixedhopsinintra-cluster routingtoreducedelayinclusters.

• Load Balancing: Load balancing can optimize lengths of queuesinmiddlemennodes.Shorterqueueswillreducede- lay.Networkcongestionisaresultofunbalancedloadinthe networkwhichcan causehighlatency.Toreduce network congestion,loadbalancingmethodsthatcansolvethe”hot spotproblem”[254]simultaneously,shouldbeapplied.Clus- teringtechniquesresultinginclustersofunequalsizes,can causeadditionaldelaysincetherewillbemoredatatotrans- ferinsomeareasofthenetworkcomparedtoothers[231]. In[158],theauthorsintroduceatree-basedclusteredWSN method whichcan balancetheloadofthenetworkbyre- orderingclustersbasedonavailablestreamstoimprovedy- namicend-to-enddelay.Theproposedmethodanalyzesthe packetstreamson-the-flyandchangestheclustersandroutes toreducedelay.

• HeterogeneousNetworks:Byhavingnodesthatarecapableof forwardingmorepacketsasmiddlemennodes,differentap- plicationswithdifferentstreamratescanbesupported.Al- thoughheterogeneousnetworkscanreducedelay,selecting inappropriateCHs/forwarderswhichdonothaveenoughre- sources tobea nexthoptarget canchange thegame and highlyincreasedelay[255].

• OptimizedRouting:Inter-clusterroutingandintra-clusterrout- ing can have a high impact on delay,thereby optimizing anddeterminingshortest-fastestroutesthatcanimproveef- ficiency and reduce delay is an important challenge. As establishing routesis not themain objectiveof clustering techniques,differentclusteringtechniquesareintroducedto achieveconcurrentrouting[15].

• Throughput(T): This referstotheamountof datathat issuc- cessfullytransferredthroughthewholenetworkforacertainpe- riodoftime.Thiscanshowtheefficiencyofthewholenetwork withrespecttolatencyreduction.Intime-sensitiveapplications, throughputisanimportantparameterthatcanimprovetheeffi- ciencyofthenetwork.Differentmethodsinclusteringtechniques areusedtoimprovethethroughputofWSNs,aslistedbelow:

• Stability:AsWSNsareinfrastructure-lessnetworks,theyare notalwaysstablebecauseofnodemobility,nodefailure,un- reliableconnections, andnodedeathdue toenergydeple- tion,tonamethemostimportantones.Byhavingamoresta- bleWSNinfrastructure,thenetworkwillhavemorereliable routestotransferdatawhichimprovesthroughput.Cluster- ingservesasanefficientmeanstoimprovestabilitybyreduc- ingthetimespentonnetworkrecoveryinunstablenetwork circumstances.Someclusteringtechniques(e.g.,in[127])in-

creasethenumberof alivenodesasasolutiontoimprove thestabilityofthenetwork. Bybalancing theenergycon- sumption,thenumberofdeadnodesisreduced,leadingto improvednetworkstability.

• CHSelection: Apre-determinednumberof CHswithdirect communicationtoBS(s)canimprovethethroughputofthe networkandkeepthenetworkreliable.Byhavingadetermin- isticnumberofCHs,therateofdatadeliverytotheBSwillbe predictableandthenetworkthroughputwillbemorestable .In[143],theauthorsintroduceamethodthatdetermines anumberofresource-richnodesasCHsinaheterogeneous networktokeepthenetworkthroughputstable.

• DataAggregationandCompression:Datacompressionandag- gregation are two methodsto reduce the volume of data transfer.Usingthesemethods,thevolumeofdatareceived byBS(s)wouldbelessthantheaccumulateddatagenerated inallnodes.Thiswillimprovethroughputanddecreaseen- ergyconsumption.In[144],theauthorsintroduceamethod toeliminaterepetitivereadingsofgeneratedpacketsinintra- clusterandinter-clusteraggregationtechniquestoreducethe volumeofdatatotransfer.

• Jitter(J):AnotherapproachthatcanimproveQoSisusingjit- terpreventiontechniques. Preventingjitteris importantespe- ciallyformultimediaandreal-timeWSNapplicationswhichre- quirestable, long-living, andnon-congested connections. Pro- posedmethodstopreventjitterusingclusteringtechniquesin- clude:

• Tree-basedStructures:Tree-basedclusteringstructuresbalance andpossiblypredictthevolumeofdataineachroutetore- ducejitter.In[214],theauthorsintroduceahierarchicaltree- basedroutingprotocoltoorganizenodesandestablishclus- ters.Theyintroduceareactivemechanismthatusethehis- toryofthenetworktoformCHsandreducejitter.

• SplittingUnbalanced TrafficStreams: Asanad-hocnetwork, WSNsusesomenodesashopstotransferdatainwhicheach hopcanbeusedbymultiplestreams.Differentstreamrates, withinahop,canaffecteachotherbychangingthepriority ofpacketsintheforwardingqueue,leadingtojittercreation.

Bysplittingpacketstreamsacrossmiddlemennodesorusing differentmiddlemen nodesfor differentstreams,theeffect ofstreamsoneachotherwillbereduced,e.g.,theeffectof amultimediastreamonatemperaturesensorstreamcanbe delay,jitter,orthroughputproblems.

4. PacketDeliveryImprovement: canenhanceQoSandreduceen- ergyconsumptionandnetworkoverheadbyreducingthenumberof re-transferredpackets,dataloss,etc.Thereareanumberoffactors thataffectpacketdeliveryaslistedbelow:

• PacketDeliveryRatio(Y):isaparameterthathasahighcorrela- tionwiththroughput.Ahigherpacketdeliveryratiocanimprove throughputsimultaneouslyduetotransferringalargervolumeof dataduringaspecifictimeperiod.Optimizingpacketdeliveryra- tioispossiblebyimprovingreliability(i.e.,datalossreduction) of thenetworkinfrastructure.Byimprovingreliability,inthis context,wemeanreducingpacketlossandnodefailureandim- provingconnectivity.Inaddition,intime-sensitiveapplications, networkcongestioncancausepacketdropswhichreducespacket deliveryratio.In[256],amethodhasbeenproposedtoimprove thepacketdeliveryratiobyselectingCHsbasedontheirremain- ingenergy,QoSparametersandnode’slocation.Theyusethe immune-inspiredoptimizationalgorithmtoselectroutesforde- liveringpackets.Datalosscanalsocausecriticalproblems,espe- ciallyinWSNswhichsenseandgathercriticalinformationlike firedetection,disastermanagement,military-basedinformation, etc.Inmostcases,nodefailureisthemaincauseofdatalossin WSNs.Clusteringtechniquescanbeusedtodetectnodefailures andreducedataloss.In[170],Izadietal.introduceaclustering

methodthatcandetectnodefailureinanacceptabletimeafter failure,avoidingdataloss.Theproposedmethodtriestodetect andreplacefailednodesimmediatelytoavoidsendingdatato themasholesthatlosedata.

• OptimizePackets Received byBS (P): While theparameter (Y) above showsthe amount of datareceivedby BS in a certain timeperiodcomparedtotheamountofgenerateddatainsource nodes,(P)referstooptimizingthevolumeofdatabydatafusion andtechniquesthroughouttheroutefromthesourcenode(s)to BS(s).Inotherwords,(Y)showstheratioofgeneratedpackets bysourcenodestoreceivepacketsbyBS(s)asitshowshigheref- ficiencywhenitapproaches1,but(P)showstheratioofvolume ofgeneratedpacketsbysourcenodestovolumeofreceivedpack- etsbyBSwithoutlosingusefuldataasitshowshigherefficiency whenitapproaches0.Networklifetimecanincreasetheamount ofdatareceivedthroughthetimebyBS[201,213].Insomepa- pers,(P)showsthethroughputofthenetworkincaseoftransfer- ringdatatoBS[20,219].Ontheotherhand,insomeclustering techniques,theparameterisusedtoshowtheeffectofBSposi- tionrelativetoothernodesonthenumberofreceivedpacketsin BS[184].IncreasingpacketsreceivedbyBScanshowtheability oftheclusteringtechniquetogatherandtransferofdatagener- atedbynodes.Thereisahighcorrelationbetween(P)andQoS, suchasdelayandreliability.Insomeclusteringtechniques,re- ducingthenumberofpacketsreceivedbyBSisanobjectivethat canimprovenetworkoverhead,energyconsumption,andQoS.

Usingaggregation,compressionandfusionmethodsisasolution ininter-clusterandintra-clusterroutingstoreducethevolumeof data.Somemethodscanalsoreducethevolumeofdataneeded foragivenserviceusingclusteringtechniquestominimizethe numberofpacketsreceivedbyBS.In[73],theauthorsintroduce aclusteringtechniquetodiscoverservicesintheneighborhood ofnodesthatneedaspecificservice.Intheproposedmethod, theytriedtoreducethenumberofpacketstransferredthrough thenetworkfordiscoveringservices,resultinginreducingthe overheadofnetworkmanagement.

5. Connectivity:Asanad-hocnetwork,node connectivityinWSNs isanimportantchallenge.Improvingconnectivitycanhelpthenet- workbemorereliableandtransferahigheramountofsenseddatato BS.Clusteringtechniquescanimproveconnectivityaseachnodehas atleastoneconnectiontoothernodes(directly)andBS(directlyor indirectly).Inclusteringtechniques,someotherobjectivescanaffect connectivityindirectly.Asanexample,byassumingthatthetrans- missionrangeofthenodesisadaptable,someclusteringtechniques adjustthetransmissionrangeinordertoredcueenergyconsump- tion[195].Ontheotherhand,bylimitingthetransmissionrangeof nodes,thenumberofreachableneighborsisreducedwhichcanlead tothenetworkconnectivityproblem.Clusteringtechniqueshelpto haveatrade-off betweensuchparametersbygroupingnodes,es- tablishingaconnectionbetweenanynodeandatleastoneCHand connectingclsutersdbyCHs.

• ImproveCoverage(O):Abettercoveragecanconnectmorenodes tothenetworkandextend the sensingcoverage area.As the maindutyofWSNnodesissensing,improvingcoveragecanalso physicallyexpandthesensingenvironment.Insomeclustering techniques,therearespecificpoliciesforimprovingcoverage.In MOCA[59],theauthorsproposeaclusteringtechniqueinwhich eachnodeisaCHorhavemaximumk-hopdistancefromaCH.

Basedonthek-hoppolicy,anodewhichcan notfindanyCH inthek-hopdistance,introducesitselfasanewCH.In[136], theauthorsusea directionalantenna toimprove energycon- sumptionandalsocoverageof thenetworkbycontrollingthe transmissionrangeofdirectionalantennas.In[173],theauthors introducea methodin whichanode isselected asanewCH whenitscoveredareaisfullycoveredbyitsneighborsandfully overlappedwithotherneighboringCHs.

• ImproveConnectivity(C):Asimprovingcoveragewillleadtoin- creasingthecoveredsensingarea,wecanhaveamorereliable andfullyconnectednetworkinfrastructure.In[84],theauthors proposeapolicytoestablishclusterswherebetweeneverytwo CHsaroutewithmaximum2khopsexists.Inmobilenetworks, connectivityis abigchallengebecausemobilenodescanlose theirconnectionsdynamically.In[114],theauthorsintroduce amethodformobileWSNstoimproveconnectivitybasedonan estimatedconnectiontimebetweenCHsandmembers.Ifcon- nectionsbetweenmembersandCHarelost,membersdetectcon- nectionlostbasedontheestimatedconnectiontimeandbroad- cast arequesttofindanewCHtoavoid packetloss.Clusters overlapping can improveconnectivity andcoverage. As over- lapping can improve connectivity, especially improvingblind spacescoverageandinter-clusterconnectivity,buthighoverlap- pingcan causedifferentproblems,especiallydelaybecauseof havingmorehopsbetweenanodeandBS.In[195],theauthors introduceaclusteringtechniquethatcancontroltheoverlapping oftheclusters,andreducedelayandenergyconsumptionusing ahierarchicalinfrastructure.Intheproposedmethod,transmis- sionrangeofCHsisincreasedlayerbylayertoreducecluster overlapping.Besides,athresholdisintroducedthateachCHcan nothavelessdistancethanthethresholdtootherCHs.

6. FaultTolerance(F):Asanetworkmanagementproblem,clustering techniquesshouldtoleratefaultynodesandkeepthenetworkcon- nectedandstable.DifferentreasonscancausenodefailureinWSNs.

Batterydepletioncancausefailuresimilartohardwarecomponents, e.g.,transceiverandprocessorfailurewhichcanbedamagedbyex- ternalfactors.Connectivityfailurecanalsohappenbyphysicalor environmentalfactorswhichcanberesolvedbytopologymanage- mentmethods.Nodefailurecancauseconnectivityorcoverageim- pairment.Inaddition,itcancausedatalossifithappenstosensors orCHs(forwarders).

Toavoidtheproblemsmentioned above,fault-tolerantclustering techniquesareusedwhichcanreplacefailednodeswithothernodes andkeep the network stable. In[237], the authors introduce a methodthatselectsfailure-freeCHstoreplacefaultyCHs.Thepro- posedmethodformsavirtualCHthatincludesthreefailure-freeCHs basedonflow-bipartitegraphmodelingandenergyofallfailure-free CHs.AfterdetectingaCH failurebyBS,BS willrequests failure- freeCHstotake overtheresponsibilitiesof faultyCHs. In[130], theauthorsintroduceapacketlossrecoverymodelbasedonmobile CHswhichmovesoutofcoverageofeachotherandmakesinter- cluster communicationimpossible. They use othernodes, named GuardNodes,withinthetransmissionrangeofthesenderCDand thereceiverCH torecovertransmitteddata.Acknowledgmentsof transmittedpacketsareassessedbyGuardNodeasapieceofevi- dencethatthereceiverCHreceivesdataornot.In[141],theau- thorsuse”clusterofCHs” definition tohaveamasterCHforCHs anddetectandreplacefaultyCHs.Ineachcluster,thereisasmaller clusterwhichincludesCHsandamasterofCHswhichisoneofthe CHs.Byhavingafaultymaster,anotherCHisselectedamongCHsin thecluster.In[159],theauthorsuseTimeDivisionMultipleAccess (TDMA)inclusterstodetectfaultynodes.Eachnodeisresponsible forsendingsenseddataoraspecialpacketasapieceofevidencethat isnotfaultyintheallocatedtimeslot.ThisisalsousedbyCHsand BStodetectfaultyCHsandselectanewCH.In[172],theauthors useafault detectionmethodbyevaluatingacknowledgmentfrom CHsinmember nodesandalsoneighbornodesin thesameclus- ter.In[254],theauthorsintroduceamethodthatdetectsfivetypes offailuresincludingbatteryfailure,microcontrollerfailure,sensor failure,andtransmitterandreceiverfailure.Anodeisresponsible fordetectingbatteryfailureitselfbycheckingthebatteryleveland alsosensorfailurebycomparingsenseddatawithneighbor’sdata.It evaluatestransmitterandreceiverbycomparingdatareceivedand senttootherneighbornodes.In[185],theauthorsintroduceVice-

CHwhichisusedwhenCHisfaulty.Theyusetwomodelstorecover inter-clusterandintra-clusterrouting.Inintra-clusterrouting,ifthe CHcannotreceivedatafromamember,themembersendsanoti- ficationmessagetovice-CHtoshowfailureandvice-CHbroadcasts anadvertisingmessagetoitsmembers.Ininter-clusterrouting,each CHandvice-CHknowaboutnexthopCHanditsvice-CH.Nexthop CHcanbe replacedbynexthop-viceCHifitisfaulty.Clustering techniquescanusethegeneralmethodsbelowtobefaulttolerant:

• DetectFailure:Differentmethodsareintroducedtodetectfaulty nodesinWSNs.Bydetectingfailures,itwouldbepossibletofix ortoleratethem.Therearetwoelementsofthenetworkwhich shouldbeevaluated.FirstnodesandCHsshouldbeevaluatedon aregularbasistodetectfailures.Thespeedofdetectionmethods isachallengebecausehighlatencyofdetectingfailurecancause datalossespeciallyindata-losssensitiveapplications.Second, connectionsshouldbecheckedtodiscoverfaultyoneswhichcan causedelayordataloss.

• SpareCHs(Nodes):Totoleratefaultynodes,someclusteringtech- niquesusesparenodestotakeoverresponsibilities.TheHotspot failurecanmakehighnegativeimpactonnetworkefficiencyby datalossanddelay.SpareCHscanreplacefaultyCHsashotspots andsolvetheproblem.

• Re-clustering:Assparenodesinduceoverheadinselecting and keeping them updated, the Ostrich type of solution is re- clustering.Afterdetectingfailures,clusterscanbedestroyedand re-established.InWSNsapplicationsinwhichfaultynodesare nottheircommonproblem,re-clusteringcanbeconsideredasa solution.

7. Network TopologyManagement: As an ad-hocnetwork, WSNs needtobeconnected,reliable,andstable.DifferentWSNnetwork managementtechniqueshavebeenproposed,classfiedintocentral- izedanddistributedtechniques.Clusteringisadistributedmanage- mentmethod.EachCHisresponsibleformanaginganareaofthe network.Twogeneralaspectsshouldbeconsideredtomanagethe topologyofaWSN:

• Stability(B):Stabilityisoneofthemanagementobjectiveswhich canmakethenetworkinfrastructuremorereliableintermsof connectivity,QoS,faulttolerance,etc.Differentchallengescan affectthestabilityofaWSN,suchasmobilityandnodefailure.

SEP[48]isafault-tolerantclusteringtechniquethatisaimedto avoidenergydepletionandnodefailurebyselectingnodeswith moreenergyresourcesasCHs.SEPtriestobalancetheremaining energyofallnodesinaheterogeneousnetworkandavoidnode death.ACHTH-LEACH[87]isanothermethodthatprovidesre- liableroutesandamorestablenetworkinfrastructurefordata transferbyselectingresource-richnodesasCHs.In[93]theau- thorsintroduceamethodwhichcankeepthenumberofselected CHsperroundstabletohelpthenetworktobemorestablein termofenergyconsumptionperroundandimprovethenetwork lifetime.

• Scalability(A):Scalabilityin termsofsupportingahugenum- berofnodesisabigchallengethatcan beaddressedbyclus- tering.Duetohavingmanynodesassensors, WSNsshouldbe scalableandsupporthundredsorthousandsofnodesandkeep thenetworkconnected.Asaproblemoflargenetworks,central- izedmethodsarenotefficientinsuchnetworksandhavehigh overhead.IIndistributedmethods,largenetworksstillhaveover- headsofnetworkmanagementbecauseofsynchronizingnodes andtheirinformationtomakemanagementdecisions,butnot morethancentralizedmethods.In[89],theauthorsintroducea methodwhichusetheGeographicHashingmethodtokeepen- codingoverheadperpacketconstantandreducesmaintenance costtovirtuallyzero.Communicationoverheadisanotherchal- lengetosupportscalability.In[178],theauthorsdesignaclus- tering method that reduces communication overhead tosup- portscalability.Neamatollahietal.[222]introduceaclustering

methodthatsupportsscalabilitybyapplyinganenergy-efficient distributedalgorithmforalllevelsofclusterstoreducecommu- nicationoverheadbasedonthenumberofnodes.Theproposed methodalsoreducesmessagepropagationintheentirenetwork comparedtoLEACHbasedmethods[20].Besides,theproposed methodusesatechniquetodistributeCHsandmembersfairly inmultipleclusterstoincreasetheefficiencyofdistributedman- agementtechniques.

8. SupportMulti-Sink(K):Supportingmulti-sinknetworkisanimpor- tantobjectivethatcanincreasetheefficiencyofWSNsindifferent aspectslikeQoS,resourceconsumption,etc.Multi-sinksupportclus- teringtechniquesallowthenetworktohaveseveralgatewayswhich improvetheefficiencyofthenetworkduringgatheringandtrans- ferringdatatooutofthenetwork.Mostoftheclusteringtechniques whichsupportmulti-sinksfocusondesigningaroutingmethodto determinethebestroutetotransferdatatooutofaWSN.Although someclusteringtechniquesconsidermulti-sinkespeciallyasasce- nariointheirperformanceevaluation,therearenotmanytechniques thathaveaspecificsolutionformulti-sinknetworks.In[203],the authorsproposeamethodthatcansupportmultiplemobilesinks.

TheirmethodusesCHstomaintainoptimalrouteswhichhavemin- imumhopstothelatestlocationofmobilesinks.Inthepaper,the authorsassumethattherearetwosinksthathaveindefiniteenergy resourcesandmoveinacounter-clockwisedirection.Bysupporting multiplesinks,theyreducethenumberof hopsbetweenCHsand sinksasgatewaystoimprovetheefficiencyofthenetwork.In[54], theauthorsintroduceaclusteringtechniquethatcansupportmulti- plemobilesinkstogatherdatabasedonqueries.Theyimprovethe

”successrate” which showstheratioofthenumberof datapack- etsreceivedsuccessfullyatBSstothetotalnumberofdatapackets generatedbyanode.

9. MobilityManagement(M):Mobilityhasalwaysbeenconsidered abigchallengeforwirelessnetworks.Althoughmobilityisanad- vantageinseveralapplications,itcancausedifferentproblemslike connectivity,reliability,stability,etc.Abuarqoubetal.[206]intro- ducesaclusteringtechniquewhichreducestheoverheadofmobility managementinWSNs.Theydividethenetworktoclusterscalledser- vicezones(SZs)toreducethelocalizationcontroloverheadbyper- forminganefficientneighbordiscoverymethodinSZs.In[114],the authorsusethespeedofeachnodeasaparametertoselectCHs.By usingTDMAtoscheduleaccesstothemediumineachcluster,they estimatetheconnectiontimebetweenmembersandCHstodetect themobilityofnodesamongclusters.Somemethodsareintroduced tosupportmobileCHsandsinksforgatheringinformationinthe network[203][226].In[190],CHsareconsideredmobileandused asMulestogatherandtransferdata.Althoughsupportingmobile sinksseemstobeanobjectiveinclusteringtechniques,inreality, therearenotmanyapplicationsthatneedsinksastheonlynodesto bemobile.Onthecontrary,mobilesinkisakindofsolutiontoim- provetheefficiencyofWSNs,notanobjective.Inotherwords,these clusteringtechniquesimprovetheirefficiencyindifferentaspectsby usingmobilesinksasasolution.

10. Security(S):TherearemanyattackthatcanhappenduetoWSN characteristics[257]. Differenttechniquesareintroducedtosolve theattacksanddetectmaliciousnodes,especiallyholeattackswhich areverycommoninad-hocnetworks.Clusteringtechniquescanalso beusedtoimprovethesecurityofWSNs.In[161],theauthorsin- troduceamethodtoevaluateeachnode,detectmaliciousnodesand avoidbeingCH.TheyuseatrustlevelsystemforallnodesofWSNs whichiscalculatedbasedonthebehaviorofthenodeinacluster.

Krishnaetal.[194]introduceamethodthatcanperformperiodic authenticationbetweenCHandmemberstoestablishsecurechan- nelsinWSNs.Theyencrypttransferringdatabyauthentickeysand detectnodeintrusions.Nodesareauthenticatedandverifiedbased onkeyverificationanddatabetweenCHandmembers.In[258], theauthorsintroduceatrust-based CHselectionmodelforWSN-

basedIntelligentTransportation Systems(ITS).Eachclusteris se- lectedbasedontheresidualenergy,trustvalueandthenumberof neighbors.Eachnodeisresponsibleformonitoringthebehaviorof itsneighborsinthecluster.CHsarealsoresponsibleforevaluating thetrustworthinessofeachmemberbasedonanalyzingothermem- bers’evaluation.Then,thevaluesaresenttoBStofinalizeanddetect maliciousnodes.

11. PhysicalLayerSupport(U):Althoughclusteringtechniquesbelong tothenetworklayer,theycancontributetotheefficiencyofother layersincludingthephysicallayer.Ingeneral,therearesomestatic bandwidthreservationmethodswhichareusedinthewirelessnet- worktosharebandwidth, suchasTDMA.Clusteringcanimprove theefficiencyofbandwidthreservationmethods.Asafundamental clusteringmethod,adaptiveclustering[36]isusedtoallocateband- widthineachclustertomembersefficiently.Theyuseavirtualcir- cuitdefinitiontoassignreal-timeconnectionsandreservetimeslots inclusters.In[162],theauthorsintroduceamethodtoutilizeband- widthallocationbasedoninter-clusteraggregationwhichreduces thevolumeof datainahierarchicalclusteringtechniquein each layerandimproveenergyconsumptionandbandwidthallocationin upperlayers.Schedulingisatasktoallocatebandwidthtodifferent nodestotransferdataandavoidtransmissioninterference.Cluster- ingtechniquescangroupnodesandhavealocalschedulingsystem ineachclusterorlayertotransferdata.In[158],theauthorsuse aheuristicschedulingmodelinclusterstoadaptthenetworkwith end-to-enddelayandbandwidthallocationrequirements.Theyuse aschedulingmodelthatcanreacttodifferentdataflowchangesin routers(CHs)byre-orderingactiveperiodsofclustersandtuningthe activeperiodsoftheclustertoaccesstothesharedchannels.In[68], theauthorsintroduceamethodtominimizetheschedulinglength subjectstoenergy-constrainednodes.Ifthereisanodefailure,in thequickrecoveryphasethereschedulingmethodisexecutedinits CHoranewCHisreplacedwiththefailedCH.

4. Statisticalevaluationofexistingclusteringtechniques

BasedonTable3,itisclearthatenergyconsumptionandloadbal- ancingarethemostcommonobjectivesofclusteringtechniques.The tablealsoshowsthatmorethan82%ofclusteringtechniquesconsider CHasthenodefordataaggregation,butbasedonthereviewedlitera- ture,mostofthemhavenotintroducedaspecificaggregationtechnique.

Inotherwords,inmostexistingtechniquesondataaggregation,CHsare assumedtofusedatabeforetransferring.Inaddition,alargenumberof reviewedtechniquesturnfrompureclusteringtoclustering-routingas theysupportinter-clusterrouting.Asinter-clusterroutingcanreduceen- ergyconsumption,94.8%oftheliteraturefocusesonimprovingenergy consumption usingthisroutingmethod.Inaddition,thetableshows thatmostofthereviewedliteratureassumesastaticinfrastructurefor thenetwork.Indifferentapplicationslikevehicularnetworksorsmart cities,thenetworkinfrastructureishighlydynamic.Thus,thestatistic showsthatdesigningclusteringtechniquesthatsupportmobilityneeds moreattention.Asweexpected,energyconsumptionisthemostcom- mon objectiveof clusteringtechniques,butthetablealsoshowsthat loadbalancing,scalabilityandimprovingpacketdeliveryratioareim- portantobjectivesstudiedbytheliterature.Additionally,asmentioned above,althoughclusteringtechniqueshavethegoodpotentialtosolve theproblemofmobilitymanagement,thereexistsnotmuchworktoex- ploitclusteringinmobilitymanagement.Theotherfact,extractedfrom Table3,isthatmostexistingworksfocusonlyonafewobjectives,de- spitethepotentialofclusteringtoachieveawiderangeofobjectives.

Fig.2reviewsthenetworkingchallengesaddressedbyclusteringand themethodswhichareusedbyclusteringtechniquestosolvethem.Blue topicsareobjectivesandyellowtopicsaretherespectivesolutions.The figureshowsthegeneralmethodsusedbyclusteringtechniques,how- evereachworkcanhaveaspecificsolution.Althoughclusteringwas originallyintroducedfortopologymanagement,thefigureshowsthat

Table3

Comparingclusteringobjectivesandtheircorrelations.

Table4

Thecorrelationsbetweenobjectivesandpropertiesofthenetworkinthereviewedclusteringtechniques.

Objective Heterogeneity Role of CH Routing Mobility

Yes No Fusion Relay Both Direct Multi-hop Both Yes No E 16,7% 78,1% 87,0% 13,5% 7,0% 26,0% 65,1% 3,3% 9,8% 85,1%

L 3,7% 24,2% 26,5% 5,1% 3,7% 4,2% 21,9% 1,4% 1,4% 26,5%

R 0,5% 1,4% 1,4% 0,5% 0,0% 0,0% 1,9% 0,0% 0,5% 1,4%

D 1,9% 11,2% 9,8% 4,2% 1,4% 1,9% 11,2% 0,0% 2,8% 10,2%

J 1,4% 0,0% 0,9% 0,5% 1,4% 0,0% 1,4% 0,0% 0,5% 0,9%

T 6,0% 6,0% 10,2% 1,9% 0,0% 2,8% 8,4% 0,5% 2,3% 9,8%

Y 3,3% 11,2% 12,6% 2,3% 0,9% 4,2% 9,8% 0,5% 4,2% 10,2%

P 3,3% 13,0% 15,8% 0,9% 0,5% 6,0% 9,3% 0,5% 0,9% 15,3%

C 0,5% 3,7% 2,8% 2,3% 0,9% 0,5% 3,3% 0,5% 0,9% 3,3%

O 0,5% 4,7% 3,7% 1,4% 0,0% 0,9% 4,2% 0,0% 0,5% 4,7%

F 1,9% 6,0% 6,0% 2,3% 0,9% 2,3% 4,7% 0,9% 3,7% 4,2%

B 0,9% 2,8% 3,3% 0,9% 0,5% 1,9% 1,9% 0,0% 0,5% 3,3%

A 1,9% 15,3% 14,0% 5,6% 2,3% 6,5% 9,3% 1,4% 3,7% 13,5%

M 0,5% 0,5% 0,5% 0,9% 0,5% 0,5% 0,5% 0,0% 0,9% 0,0%

S 0,9% 1,4% 1,9% 0,5% 0,0% 0,9% 1,4% 0,0% 1,4% 0,9%

U 1,4% 2,3% 3,3% 0,9% 0,5% 0,0% 3,3% 0,5% 0,9% 2,8%

K 0,0% 1,9% 0,9% 1,4% 0,5% 0,5% 1,4% 0,0% 0,0% 1,9%

ithasbeenwidelyappliedtoaddressothernetworkingchallenges.As showninthefigure,indifferentcases,hierarchicalclusteringispartof thesolutiontoaddressthosechallenges.Balancedandunbalancedclus- tersarealsocommonsolutionstoachievedifferentobjectives.Another commonmethodtoaddressthenetworkingchallengesisbalancingthe energyconsumptiontoavoiddeadnodes.Inaddition,asshowninthe figure,someobjectivesareconsideredassolutionsaswell.Asanexam- ple,stabilityisbothanobjectiveandasolution.Itisnoteworthythat someclusteringtechniquesusesomeobjectivestoachieveanotherone indirectly.Forexample,improvingthestabilitycanimproveconnectiv- ityresultinginhigherthroughput.

InTable3,objectivesofclusteringarereviewedbasedontheircor- relation.Whitebackgrounddiameterofthetableshowsthenumberof papersproposingaclusteringtechniquewithanobjectiveonx/y-axis.

Thelowerheat-maptriangleshowswhatpercentageofthosepapersad- dressanobjectiveony-axis.Forexample,outof204papersfocusingon E(energy),2%ofthemconsiderK(supportingMulti-sink)asotherob- jectiveforclustering.Similarly,theuppertriangularofthetableshows whatpercentageofpaperswithx-axisobjectiveincludeanobjectiveon y-axis.Forexample,outof threepapersfocusingontheKobjective, 100%ofthemconsiderEasotherobjectiveofclustering.Thetableis

usedtostatisticallyshowthatwhat percentageof eachobjectivehas overlapwithotherobjectives.Thetablehelpstounderstandtherea- sonsofusingclusteringtechniquesinWSNsbybilateralcomparisonof overlapsbetweeneachtwoobjectives.Inotherwords,pairsofobjec- tivesshowninthetablehelpstounderstandwhatobjectivesarecon- sideredtogetherindesigningaclusteringtechnique.Basedonstatistics, Table1alsoshowsthat66,56,33,10,2,1and2ofreviewedcluster- ingtechniquessupport1,2,3,4,5,6and7simultaneousobjectives, respectively.Theresultsshowthatmostoftheclusteringtechniquesfo- cusononeortwoobjectives.Inaddition,thetableshowsthatinmostof existingsolutionsenergyconsummationhasbeenconsideredasamain objective,besidestheirotherspecifiedobjectivesforclustering.Onthe otherhand,thereisalargebodyoftheliteraturethatfocusesonlyon improvingenergyconsumption.

Table4showsthecorrelationsamongobjectivesandpropertiesof thenetwork.Asanexample,82%ofpapersthatconsiderenergyef- ficiency (E)asanobjectivecan notsupportheterogeneity.Thetable showsthatheterogeneityisnotsupportedinmostcases.Inpaperson (J),heterogeneityissupported100%.Specifically,thereareonlythree paperssupporting(J)inwhichatreebasednetworkinfrastructureis providedtoreducejitter.WithrespecttotheroleofCH,thetableshows

Fig.2. Theclusteringobjectivesandtheassociatedmethodstoachieveeach objective.

thatinmostofworksdatafusionhasbeenused,e.g.,morethan91%

oftheliteraturethatconsiderspacketdeliveryimprovement,usesdata fusion toreduce thevolumeof datatotransfer.Consideringrouting, thetableindicatesthatmulti-hoproutinghasbeenmostlyusedforob- jectivesrelatedtoQoSandresourceusage,e.g.,loadbalancing,jitter, improvingcoverage,andenergyconsumptionreduction.Additionally, thetableshowsahighcorrelationbetweenmulti-hoproutinganddata fusionwhichindicatesthatintherespectiveworksdatafusionhasbeen introducedatmultiplenetworklevels.Atthebottomofthetable,the averagesshowthatalthoughmostof solutionsaimtoaddressfunda- mentalnetworkingchallenges(e.g.,QoS)throughclustering,theydo notsupportheterogeneityandmobilityastwomostimportantnetwork characteristics.Therefore,basedonreal-worldnetworkenvironments ofdifferentWSNapplications,statisticalevaluationshowsthatdesign- ingclusteringtechniquesthatsupportmobilityandheterogeneityneeds moreattention.

5. Conclusion

Clusteringhasbeenleveragedasacommontopologymanagement techniqueinWSNs.Althoughclusteringismainlyknownasatechnique toimproveenergyconsumption,clusteringcansolvevariousnetwork- ingchallenges,e.g.,loadbalancing,QoS,security,andmobilitymanage- ment.Inthispaper,wesurveyedtheobjectivesofclusteringtechniques inWSNstoinvestigatethecurrentdirectionofclusteringtechniques, morethan20yearsaftertheintroductionofthefirstimportantcluster- ingtechnique.Wealsorevieweddifferentnetworkcharacteristicsthat clusteringcansupport,e.g.,heterogeneityandmobility.210clustering techniqueswerereviewedtostatisticallyanalyzetheclusteringobjec- tivesandnetworkcharacteristics.Asweexpected,theresultsshowthat themostimportantobjectiveofusingclusteringtechniquesis energy consumption,butalsotheyareusedtoachievemorethan17otherob- jectives.Inaddition,theresultsshowthatmostof existingclustering techniquesareunabletosupportheterogeneousandmobilenetworkin- frastructures.Giventhatmanyapplicationsrequiresupportingsuchnet- workcharacteristics,moreeffortisneededonaddressingheterogeneity andmobilitythroughclustering.Inaddition,theresultsshowthatal- thoughclusteringtechniquesfocusonreducingenergyconsumptionand improvingloadbalancing,theyareabletosolvemorediverschallenges.

Thiswillencouragethescientiststoleverageclusteringtosolveother networkingchallenges.

DeclarationofCompetingInterest

Theauthorsdeclarethattheyhavenoknowncompetingfinancial interestsorpersonalrelationshipsthatcouldhaveappearedtoinfluence theworkreportedinthispaper.

Supplementarymaterial

Supplementarymaterialassociatedwiththisarticlecanbefound,in theonlineversion,atdoi:10.1016/j.comnet.2020.107376.

CRediTauthorshipcontributionstatement

Amin Shahraki:Conceptualization,Methodology,Writing-origi- naldraft,Writing-review&editing,Datacuration, Resources.Amir Taherkordi:Writing-review&editing,Validation.ØysteinHaugen:

Projectadministration,Supervision.FrankEliassen:Supervision.

References

[1] G.J. Pottie , Wireless sensor networks, in: Proceedings of the Information Theory Workshop, IEEE, 1998, pp. 139–140 .

[2] M.P. Durisic , et al. , A survey of military applications of wireless sensor networks, in:

Proceedings of the Mediterranean Conference on Embedded Computing (MECO), IEEE, 2012, pp. 38–74 .