SMART A Scan-Based Movement-Assisted Sensor Deployment Method in Wireless Sensor Networks

MethodsinWirelessSensorNetworks∗

ShuhuiYang†,MingluLi‡,andJieWu†

†DepartmentofComputerScienceandEngineering

FloridaAtlanticUniversityBocaRaton,FL33431

‡DepartmentofComputerScienceandEngineering

ShanghaiJiaoTongUniversity

Shanghai,P.R.China

Abstract

Theefficiencyofsensornetworksdependsonthecoverageofthemonitoringarea.Althoughingeneralasufficientnumberofsensorsareusedtoensureacertaindegreeofredundancyincov-erage,agoodsensordeploymentisstillnecessarytobalancetheworkloadofsensors.Inasensornetworkwithlocomotionfacilities,sensorscanmovearoundtoself-deploy.Themovement-assistedsensordeploymentdealswithmovingsensorsfromaninitialunbalancedstatetoabal-ancedstate.Therefore,variousoptimizationproblemscanbedefinedtominimizedifferentparam-eters,includingtotalmovingdistance,totalnumberofmoves,communication/computationcost,andconvergencerate.Inthispaper,wefirstproposeaHungarianalgorithmbasedoptimalsolu-tion,whichiscentralized.ThenalocalizedScan-basedMovement-AssistedsensoRdeploymenTmethod(SMART)anditsseveralvariationsareproposedthatusescananddimensionexchangetoachieveabalancedstate.AnextendedSMARTisdevelopedtoaddressauniqueproblemcalledcommunicationholesinsensornetworks.Extensivesimulationhasbeendonetoverifytheeffectivenessoftheproposedscheme.

Keywords:Dimensionexchange,Hungarianmethod,loadbalance,movement-assisted,scan,sensordeployment,wirelesssensornetworks.

ThisworkwassupportedinpartbyNSFgrantsANI0073736,CCR0329741,CNS0422762,CNS043533,EIA0130806,CNS0531410,CNS0626240,andnationalgrandfundamentalresearch973programofChina,No.2006CB303000.Emails:syang1@fau.edu,li-ml@cs.sjtu.edu.cn,jie@cse.fau.edu.

∗

1

1Introduction

Wirelesssensornetworks(WSNs)[1,2]combineprocessing,sensing,andcommunicationstoformadistributedsystemcapableofself-organizing,self-regulating,andself-repairing.TheapplicationofWSNsrangesfromenvironmentalmonitoring,tosurveillance,tocoordinatedtargetdetection.Theefficiencyofasensornetworkdependsonthecoverageofthemonitoringarea.Although,ingeneral,asufficientnumberofsensorsareusedtoensureacertaindegreeofredundancyincoveragesothatsensorscanrotatebetweenactiveandsleepmodes,agoodsensordeploymentisstillnecessarytobalancetheworkloadofsensors.Mobilesensors[3]canbeexploitedtoprovideare-distribution.Afteraninitialrandomdeploymentofsensorsinthefield,themovement-assistedsensordeploy-ment[4]canbeapplied,whichusesapotential-field-basedapproachtomoveexistingsensorsbytreatingsensorsasvirtualparticles,subjecttovirtualforces.Basically,themovement-assistedsensordeploymentdealswithmovingsensorsfromaninitialunbalancedstatetoabalancedstate.There-fore,variousoptimizationproblemscanbedefinedtominimizedifferentparameters,includingtotalmovingdistance,totalnumberofmoves,communication/computationcost,andconvergencerate.Morerecently,someextendedvirtualforcemethods,suchasin[5]and[6]whicharebasedondiskpackingtheory[7]andthevirtualforcefieldconceptfromrobotics[8],areproposed.Thesemethodssimulatetheattractiveandrepulsiveforcebetweenparticles.Sensorsinarelativelydenseregionwillexplodeslowlyaccordingtoeachother’srepulsiveforceandheadtowardasparseregion.Inthisway,thewholemonitoringareacanachieveanevendistributionofsensors.However,thesemethodsmayhavealongdeploymenttimesincesensorsmoveindependentlyandtheymayevenfailifallthesensorscanachieveforcebalancebutnotloadbalance.

Weassumethatsensorsaredeployedrandomlyintothesquaremonitoringareawithoutconsider-ingofanyphysicalobstacles.Thenifwepartitionthemonitoringareaintomanysmallregions,andusethenumberofsensorsinaregionasitsload,thesensordeploymentproblemcanbeviewedasaloadbalanceproblemintraditionalparallelprocessing,whereeachregioncorrespondstoaprocessorandthenumberofsensorsinaregioncorrespondstotheload.Thesensordeploymentresemblesthetraditionalloadbalanceissueinparallelprocessingwithseveralkeydifferences:

•Differentobjectives.Intraditionalloadbalancing,totalmovingdistanceratherthanthenumberofmovesisimportant,whereasinsensornetworks,thenumberofmovesisalsoimportantbecauseofrelativelyheavyenergyconsumptiontostartorstopamove.

2

•Differenttechnicalissues.Oneuniqueissueinsensornetworksisthecommunicationhole(orsimplyhole)problemwheresomeregionsofthenetworkhavenodeployedsensors.Sincethereisnocentralizedcontrol,thenetworkcanbepartitioned.Therefore,thenetworkneedstobeconnectedfirstbeforeloadbalancing.

Inthispaper,wefirstprovideanoptimalsolutionin2-Dmeshes.ThissolutionisbasedontheclassicHungarianmethod,butrequiresglobalinformationwithoutconsideringsensornetworkcon-nectivity.Wethenproposeamethodusinga2-dimensional(2-D)scancalledScan-basedMovement-AssistedsensoRdeploymenTmethod(SMART).Atypicalscanoperation[9]involvesabinaryopera-tor⊕andanorderedset[w0,w1,...,wn−1]whereeachwirepresentsthenumberofsensorsinaregion,andreturnstheorderedset[w0,(w0⊕w1),...,(w0⊕w1⊕,...,⊕wn)].Inthispaper,weconsideronlyintegeradditionandbooleanANDoperationsforscan.Usingintegeraddition,thescanoperationwillreturnpartialandtotalsumofthenumberofsensors.Sinceeachregionpositionandnareknown,averageloadinformationcanbeeasilycalculatedanddistributedascanbetheoverload/underloadsituationofeachorderedsubsetcorrespondingtoaprefixoftheorderedset.

InSMART,agivenrectangularsensorfieldisfirstpartitionedintoa2-Dmeshthroughclustering.Eachclustercorrespondstoasquareregionandhasaclusterheadwhichisinchargeofbookkeepingandcommunicationwithadjacentclusterheads.Ahybridapproachisusedforloadbalancing,wherethe2-Dmeshispartitionedinto1-Darraysbyrowandbycolumn.Twoscansareusedinsequence:oneforallrows,followedbytheotherforallcolumns.Withineachrowandcolumn,thescanoperationisusedtocalculatetheaverageloadandthentodeterminetheamountofoverloadandunderloadinclusters.Loadisshiftedfromoverloadedclusterstounderloadedclustersinanoptimalwaytoachieveabalancedstate.Byoptimal,wemeantheminimumnumberofmovesandminimumtotalmovingdistance.Byabalancedstate,werefertoastatewiththemaximumclustersize(thenumberofsensorsinacluster)andtheminimumclustersizebeingdifferentbyatmost1.

Thecommunicationholeproblemina2-Dmeshcorrespondstoaclusterwithaclustersizeofzero.Clearly,thescanapproachcannotbeusedinaroworcolumnwithholes,sinceclusterheadsseparatedbyoneormoreholescannotcommunicatewitheachothertoperformascanoperation.Intheextremecase,the2-DmeshmaybedisconnectedasshowninFigure1,wherethenumberineachcirclecorrespondstotheclustersize,andsensorsineachclustercancommunicatewithsensorsinadjacentclustersaswellassensorsinthesamecluster.InFigure1,thenetworkispartitionedintotwocomponents.Oursolutiontotheholeissueisbasedonplantinga“seed”fromanon-emptycluster

3

k(3)k(4)k

(1)(3)(1)(4)(1)

0

(2)(3)

0

(1)(3)

0

(2)(3)

0

(1)(3)(1)

0

1

(2)(4)(2)

1

(1)(4)

0

(2)(4)

00

0k

(1)

0

(2)

k

(4)(1)

0

Figure1:Asampleclusteredsensornetworkthatcorrespondstoa2-Dmesh.

toanadjacentemptycluster.Varioussolutionsareproposedinsuchawaythatthisseed-plantingprocess(alsocalledpre-processing)canbeeasilyintegratedwiththenormal2-Dscanprocesstoachieveagoodbalanceofvariousobjectives.Thenetworkcanusesomenewlydevelopedlocationservices[10,11]toestimatethelocationsofsensors;thusnoGPSserviceisrequiredateachsensorandthecorrespondingoverheadisavoided.Forexample,locationsofsensorscanbedeterminedbyusingsensorsthemselvesaslandmarks[12].

Thecontributionsofthispaperareasfollows:(1)WedevelopanoptimalloadbalancesolutionbasedontheclassicHungarianmethodthatachievesminimumtotalmovingdistance,anduseitasabaselinetochecktheperformanceofotherapproaches.(2)Wesystematicallydiscussthesimilarityanddifferencebetweenthetraditionalloadbalancinginparallelprocessingandmovement-assistedsensordeploymentinsensornetworks.(3)WeproposeanewhybridapproachcalledSMART,to-getherwithseveralvariations,thatcombinessomedesirablefeaturesofbothlocalandglobalap-proacheswhileovercomingtheirdrawbacks.(4)Weidentifyauniquetechnicalproblemcalledcom-municationholeandprovidesolutionstoit.(5)Wesystematicallystudydifferenttrade-offsamongvariouscontradictorygoals.(6)Weconductextensivesimulationsandcompareresultswithseveralexistinglocalmovement-assistedsensordeploymentmethods.

2PreliminariesandRelatedWorks

2.1Loadbalanceinmultiprocessorsystems

Extensiveworkhasbeendoneintheparallelprocessingcommunityonloadbalancing.Ingeneral,loadbalancealgorithmscanbeclassifiedaslocal(suchasiterativenearestneighborexchanging[13,

4

14])andglobal(suchasdirectmapping[15,16]).Theglobalapproachreliesonglobalinformationwhichisusuallynotscalable.Localalgorithmscanbeeitherdeterministicorstochastic.Diffusionanddimensionexchangearetwowidelyusedlocaldeterministicmethods.Bothalgorithmsareiterativeandarebasedonnearestneighborexchange.Onceallnodescompleteoneiteration,itiscalledasweep.Althoughnoinformationonloaddistributionisneededinlocalmethods,iterativemethodsincurasignificantnumberofrounds(movesinsensornetworks).

Inthediffusionmethod,thebalancingprocedureisdividedintoasequenceofsynchronoussteps.Ateachstep,eachnodeiinteractsandexchangesloadwithallitsneighbors,adj(i).Adiffusionparameterdecidestheportionoftheexcessloadtobediffusedbetweennodesiandeachofitsneigh-bors.XuandLau[17]provedthattheoptimaluniformdiffusionparameterthatleadstothefastestconvergencefor2-Dmeshesis1/4.

Inthedimensionexchangemethod,theedgesofthegrapharecoloredsuchthatnotwoadjacentedgeshavethesamecolor.A“dimension”isthendefinedasacollectionofedgeswiththesamecolor.InFigure1,alledgesaregroupedintofourdimensions.Edgeswithlabel(i)belongtodimensioni(i=1,2,3,4).Ateachiteration,oneparticularcolor(dimension)isconsideredandeverytwoadjacentnodesiandjconnectedbyanedgewiththeselectedcolorexchangetheirloadaccordingtoanexchangerate.Again,XuandLau[17]showedtheoptimaluniformexchangeratefor2k1×2k22-Dmeshes(wherebothrowandcolumnnumbersareeven).

2.2Movement-assistedsensordeployment

Thesensorplacementissuehasbeenresearchedrecently[18],[19],[20].Randomplacementofsen-sorsmaynotsatisfythedeploymentrequirementduetoahostiledeploymentenvironment.Therefore,themovement-assistedsensordeploymentmethodisdeveloped.Mostexistingmovement-assistedprotocolsrelyonthenotionofvirtualforcetomoveexistingsensorsfromaninitialunbalancedstatetoabalancedstate.Theseprotocolsaresimilartonearestneighborexchanginginloadbalancing.Sensorsareinvolvedinasequenceofcomputation(foranewposition)andmovement.

In[6],ZouandChakrabartyproposedacentralizedvirtualforcebasedmobilesensordeploymentalgorithm(VFA),whichcombinestheideaofpotentialfieldanddiskpacking[7].InVFA,thereisapowerfulclusterhead,whichwillcommunicatewithalltheothersensors,collectsensorpositioninformation,andcalculateforcesanddesiredpositionforeachsensor.InVFA,thedistancebetween

5

twoadjacentnodeswhenallnodesareevenlydistributedisdefinedasathresholdtodistinguishattractiveorrepulsiveforcebetweentwonodes.Theforcebetweentwonodesiszeroiftheirdistanceisequaltothethreshold,attractiveiflessthanandrepulsiveifgreaterthan.Thetotalforceonanodeisthesumofalltheforcesgivenbyothersensorstogetherwithobstaclesandpreferentialcoverageinthearea.TheclusterheadexecutesVFAanddirectseachsensor’smovement.VFAhasthedrawbacksofcentralizedalgorithms,singlepointfailure,bottleneckofprocessing,andlessscalability.In[5],Wang,Cao,andLaPortadevelopedanoveldistributedself-deploymentprotocolformobilesensors.TheyusedVoronoidiagrams[21]tofindcoverageholesinthesensornetwork,andproposedthreealgorithms,VEC(Vector-based),VOR(Voronoi-based),andMinimax,toguidesensormove-menttowardthecoveragehole.Whenappliedtorandomlydeployedsensors,thesealgorithmscanprovidehighcoveragewithinashorttimeandlimitedmovingdistance.Iftheinitialdistributionofthesensorsisextremelyuneven,disconnectionmayoccur,thus,theVoronoipolygonconstructedmaynotbeaccurateenough,whichresultsinmoremovesandlargermovingdistance.Theyadoptedtheoptimizationofrandomscatteringofsomesensorstocoverholes.Theterminationconditionoftheiralgorithmsiscoverageinsteadofloadbalance.In[22],theyfurtherexploredthemotioncapabilityofsensorsforrelocationtodealwithsensorfailureorrespondtonewevents.Thealgorithmcontainstwophases.Thefirstoneisredundantsensorlocation,andthesecondisredundantsensorrelocation.Agrid-quorumsolutionwasproposedtoquicklylocatetheclosestredundantsensorstothetargetarea,whereasensorfailureoccurs.Intheirrecentwork[23],theydesignedavirtualmovementschemeforthedeploymentprotocoltoreducethemovingdistanceofsensors.Toourbestknowledge,ourworkisthefirsttoexploitscan-basedmovementassistedsolutionforsensorredistribution.

Somerecentworkfocusesonsensorswithlimitedmobility,whichismotivatedbytheDARPAprojectcalledIntelligentMobileLandMineUnits(IMLM)[24].InIMLM,themobilitysystemisbasedonahoppingmechanism.Chellapan,Bai,Ma,andXuan[25]studiedaspecialhoppingmodelinwhicheachsensorcanflip(orflop)onlyoncetoanewlocation.Inaddition,theflipdistanceisbounded.Thedeploymentproblemisthenformulatedasaminimum-costmaximum-flowproblem.

3AnOptimalSolution

Thissectionstartswithanoptimalsolutionfor2-DmeshesbasedontheclassicHungarianmethod.Althoughduetoitspotentialdrawbackofcentralization,thisoptimalsolutionisnotpractical,espe-6

ciallywhentheWSNsarenotconnected,wecanuseitasabaselinetoexaminetheperformanceofotherproposedmethods.

3.1Hungarianmethod

LetusconsidertheedgeweightedmatchingprobleminacompletebipartitegraphKm,m(mnodesontheleftsideandmontheright)withnumbersassociatedwiththeedgescalledweights.Theobjectiveistofindaperfectmatching(ofmpairs),suchthatthesumoftheweightsofedgesinthematchingismaximum(orminimum).Amatchingistofindmedgestoconnectnodesontheleftsidetothoseontheright,andeachnodehasonlyoneedge.

Anaiveapproachtosolvethematchingproblemistoenumerateallmperfectmatchingsandfindanoptimaloneamongthem.AbettersolutioncalledtheHungarianmethod1exists.Thefollowingisthealgebraicformulationforthematchingproblem.Weletxij,(i,j=1,...,m),beasetofvariables.misthenumberofnodesinthenodesetsofthecompletebipartitegraphB=(V,U,E),whereV,Uaretwonodesets,Eistheedgeset.xij=1meansthattheedge(vi,uj)isincludedinthematching,whereasxij=0meansnot.cijistheweightofedge(vi,uj).Anoptimalsolutionisto:

MinimizeΣijcijxij

󰀁

subjecttoj=1xij=1i=1,...,m

󰀁

i=1xij=1j=1,...,m

TousetheHungarianmethodtoloadbalanceinWSNs,weneedtofirstconvertthe2-Dmeshtoacompletebipartitegraphusingthefollowprocedure:(1)Calculatetheglobalaveragev¯anddetermine“give”,“take”,and“neutral”stateofeachgrid.(2)Anodeandedgeweightedbipartitegraphisconstructed,where“give”and“take”gridsappearattheleftandrighthandsidesofthegraph,respectively.Thenodeweightcorrespondstoamountofoverloadandunderload,andtheedgeweightrepresentsthedistancebetweenthe“give”and“take”gridsinamatchingpair.(3)Anedgeweightedperfectbipartitegraphisderivedbyexpandingeachnodewithweightktok“clone”nodes.Theedgeweightofclonenodeswillinheritfromtheoriginalnodes.Itisobviousthatthetotalsensormovingdistanceisminimized.Thetotalnumberofmovesisalsominimizedsinceeachsensor,ifnecessarytomove,onlymoveoncetoitsdestination.

1

InhonoroftheHungarianmathematiciansD.K˝onigandE.Egerv´arywhodevelopedit.

7

M[3,3]3M[3,5]1M[5,5]4313111M[1,2]3M[3,2]1M[5,2]1M[2,3]2M[4,3]

12345678

3111312345678

12345678

12345678

(a)

(b)

(c)

Figure2:(a)ThenodeandedgeweightedbipartitegraphofFigure3with“give”gridsattheleft-handsideand“take”gridsattheright-handside.(b)Theedgeweightedcompletebipartitegraphof(a)and(c)theoptimalsolution.

3.2Examplesandanalysis

InFigure3,theglobalaverageincaseis5.Therearethreeoverloadednodesandfiveunderloadednodes.M[3,3]=3meansoverloadedby3unitsandM[1,2]=1isunderloadedby1unit.TheedgeweightistheManhattandistancebetweentwoendnodesM[i,j]andM[i,j].Thatis,∆x+∆y=|i−i|+|j−j|2.Forexample,theedgeconnectingM[3,3]toM[1,2]hasaweightof3.InFigure2(a),thenodeandedgeweightedbipartitegraphshowsweightsofalledgesconnectingM[3,3]tounderloadednodes.InFigure2(b),theedgeweightedcompletebipartitegraphof(a)isshown,whereeachnode(overloadedorunderloaded)withweightkhask“clone”nodes.Forexample,M[3,3]hasthreeclonenodeslabeledfrom1to3.TheHungarianmethodisthenappliedto(b)andtheoptimalresultisshownin(c).TheoptimalresultshowsthatM[5,5](nowwithfourclonenodes)needstomoveonesensortoeachofM[1,2],M[5,2],M[2,3],andM[4,3].

ThereareseveralpolynomialimplementationsfortheHungarianmethod.OurimplementationisbasedonMunkres’method[26].Anotherimplementation[27]solvestheprobleminO(m3),exploitingthesolutiontothemaximumflowproblem.ThecostofimplementingtheHungarianmethodforloadbalanceinWSNsisO(m3),wheremistheamountofoverloads(underloads)which

2

󰀁

󰀁

󰀁

󰀁

Thegeneraldistancebetweentwopointsisdefinedas((∆x)k+(∆y)k)1/k.Whenk=2,itisEuclidiandistance,

andwhenk=1,itisManhattandistance.

8

54321i

55545

j

1

55455

2

65825

3

55355

4

95545

5

65545

65545

65545(b)

65545

65545

55555

55555

55555(c)

55555

55555

(a)

Figure3:AnidealcaseforSMART.

isboundedbythenumberofsensors.Usually,thenumberofsensorsisoneortwomagnitudeshigherthanthenumberofgrids(n).ABS(basestation)isneededtoconnectedtotheWSN,servingasthecentralcontrollerforinformationcollectionandalgorithmexecution.ThenBSinformsallclusterheadsaboutthesensormovementviadirectormulti-hopcommunication.

4SMART

4.1Basicideas

Unliketheoptimalsolution,SMARTisahybridofthelocalandglobalapproach.Itsextension(discussedinthennextsection)canbeusedindisconnectedWSNs.Thesensornetworkispartitionedintoann×n2-Dmeshofclusters(themethodcanbeeasilyextendedtothegeneraln×m2-Dmesh).Eachclustercoversasmallsquarearea,andiscontrolledbyaclusterhead.Theroleofeachclusterheadcanberotatedwithinthecluster.Eachclusterhead,inchargeofcommunicationwithadjacentclusters,knowsthefollowinginformation:(1)itscluster’sposition,i,inthe2-Dmesh(viaGPS)and(2)thenumberofsensors,wi,inthecluster.

Tworoundsofbalancingareusedwithoneforeachdimension,firstrow,thencolumn.AsshowninFigure3,afterthefirstround,allrowsarebalancedin(b);afterthesecondround,allcolumnsarebalanced,asisthewholearea.Althoughbalancingwithinaroworcolumncanbedoneeitherlocallysuchasiterativenearestneighborinteractionorgloballysuchasdirectmapping,SMARTreliesonanextendedscanmethod.

9

4.2Clustering

Sinceeachsensornodeknowsitsclusterid,i,sensorsinthesameclusterelectauniqueclusterheadbasedonapre-definedpriority.Assumeeachclustercoversanx×xsquare.Toensurethesquare

√

iscoveredwheneverthereisasensorintheregion,thesensingranger1shouldbesetto2x(thediagonallengthofthesquare).Tosupporttransmissionfromnon-clusterheadtoclusterhead,theintra-√

clustertransmissionrangeshouldbesettoatleast2x(alsodenotedasr1).Toensuretheclusterheadcancommunicatewithclusterheadsinfouradjacentclusters,theinter-clustertransmissionrangesofeachclusterheadshouldbeatleastthediagonaloftherectangleconstructedfromtwoadjacent

√

squares.Thatis,r2=5x.Ifasensordoesnotsupporttwotransmissionranges,r2canbeusedforintra-clustercommunication.

Generally,theroleofclusterheadshouldrotateamongallthenodesintheclustertoachievebalancedenergyconsumptionandtoprolongthelifespanofeachindividualnode,suchasin[28].Non-clusterheadsonlyneedtoreporttheirownpositionandenergytoclusterheadsusingtransmissionranger1,whileclusterheadswillcommunicatewithneighboringclusters,takeovertheinformationofsensorsinitscluster,anddirectthemovementofsensors.

4.3Scan

Considerthe1-Darrayofclusterswhereclusteridislabelledfollowingthesequenceinthelinearline.Again,denotewiasthenumberofsensorsinclusteri.Letvibetheprefixsumofthefirsti

󰀁󰀁n

clusters,i.e.,vi=iw.v=nj=1jj=1wjisthetotalsum.Clearly,w=vn/nistheaveragenumberofsensorsinabalancedstate,andvi=iwistheprefixsuminthebalancedstate.Notethatwisarealnumberwhichshouldberoundedtoaninteger󰀈w󰀉or󰀊w󰀋.Inabalancedstate,|wi−wj|≤1foranytwoclustersinthenetwork.

Thescanalgorithmworksfromoneendofthearraytoanother(firstscan)andthenfromtheotherendbacktotheinitialend(secondscan).Thedirectionofthefirstsweepiscalledpositive(withincreasingorderofclusterid)andthatofthesecondsweepnegative(withdecreasingorderofclusterid).Thefirstsweepcalculatestheprefixsumvi,whereeachclusterheadideterminesitsprefixsumvibyaddingvi−1+wiandforwardingvitothenextcluster.Theclusterheadinthelastclusterdeterminesvnandw=vn/n(loadinabalancedstate)andinitiatesthesecondscanbysendingoutw.Duringthisscan,eachclusterheadcandeterminevi=iw(loadofprefixsuminabalancedstate)basedonw10

Table1:ThescanprocessonthethirdrowofFigure3.

iwivivi

1555

24910

381715

432020

552525

thatispassedaroundanditsownclusterpositioni.

Knowingtheloadinthebalancedstate,eachclustercaneasilydetermineits“give/take”state.Specifically,whenwi−w=0,clusteriisinthe“neutral”state.Whenwi−w>0,itisoverloadedandinthe“give”state;andwhenwi−w<0,itisunderloadedandinthe“take”state.Eachclusterinthegivestatealsoneedstodeterminethenumberofsensors(load)tobesenttoeachdirection:

→wiforloadinthepositivedirection(orsimplygive-right)and←wiforloadinthenegativedirection

(give-left).Basedonthescanprocedure,wehave

→

wi=min{wi−w,max{vi−vi,0}}←

→wi=(wi−w)−wi

(1)(2)

The2-DscanprocessinvolvesarowscanfollowedbyacolumnscanasshowninFigures3(b)and3(c),respectively.Table1showsdetailsoftherowscanonthethirdrowwhereiisthecolumnnumber.Onlytheclusteratcolumns3isinthe“give”state,sinceitsloadishigherthanw=5.For

→

column3,w3=2(theloadwillbeassignedtocolumn4,theactualschedulewillbediscussedlater)

and

←

w3=1(itwillbeassignedtocolumn2).Similarly,asetofconditionscanbegivenforthe

←“take”state:wifortake-rightand→wifortake-left.Itisclearthat

→

wi=min{w−wi,max{vi−1−vi−1,0}}(3)(4)

←

wi=(w−wi)−→wi

Inthesubsequentdiscussion,weuse→wiforboththenumberoftake-leftunitsandthetake-leftstateofclusteri.Thesameconventionisusedfortheotherthreenotations.Thedistinguishingfeatureofscanisitssimplicity,whereeachclusterheadinipassesonlyonepackageineachsweep,prefixsumwiinonesweepfollowedbyglobalaveragewinthesecondsweep.

11

4.4PropertiesofScan

Anoptimalloadbalanceschedulingbasedonscanshouldsatisfytheabovefourconditionsrelatedtogive-right,give-left,take-right,andtake-leftforeachcluster.Byoptimal,wemeantheminimumnumberofmovesandminimumtotalmovingdistance.Thefollowingtheoremshowsthatanyvio-lationoftheconditionswillresultintheincreaseofoverallmovingdistanceand/ortotalnumberofmovestoreachaloadbalancedstate.

Theorem1:Anyviolationofthefourconditionsongiveandtakestateofeachclusterwillresultintheincreaseofoverallmovingdistanceand/ortotalnumberofmovestoreachaloadbalancedstate.Proof:Weconsiderfourtypesofviolation:takestatechangedtogivestate,givestatechangedtotakestate,take-right(take-left)changedtotake-left(take-right),andgive-right(give-left)changedtogive-left(give-right).

Supposeclusteri’sstateischangedfromtaketogiveandoneunitissenttoclusterj.Toensureloadbalancing,thatoneunitatclusteriwillbecompensatedbyanotherunitfromclusterk(i.e.,kgivesoneunitbacktoi).Abetterschemewouldbekgivingoneunitdirectlytojtosaveonemove,andshortenthedistanceifjandkareatthesamesideofiinthe1-Darray.

Supposeclusteri’sstateischangedfromgivetotakeandoneunitisgivenfromclusterj.Toensureloadbalancing,thatoneunitwillbegivenawaytoclusterk.Itwouldbebetterforjtogiveoneunitdirectlytoktosaveonemove,andshortenthedistanceifkandjareatthesamesideofi.

→

Whenclusteri’sstatemixesgive-rightwithgive-left,weassumethatoneunitismovedfromwi→

to←wi(similarlyfor←witowi).Weshowthatthisschedulewillgeneratealongermovingdistance.

Supposethisunitismovedfromitoi(1≤i|j−i|+|i−j|.

2.When1≤j|j−i|+|i−j|.Inbothcases,themovingdistancebeforetheswap|i−i|+|j−j|islongerthanthatofaftertheswap.

12

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁󰀁

󰀁

󰀁󰀁

1

i’j

ij’

(a)

n

1j

i’ij’

(b)

n

Figure4:Twocasesformixingupgive-rightwithgive-left.

1

ij

(a)

j’

i’

n

1

ii’

nj’

j

(b)

Figure5:Twocasesformixinguptake-rightwithtake-left.

Whenclusteri’sstatemixestake-rightwithtake-left,weagainassumethatoneunitismovedfrom

→

←←

witowi(similarlyforwito

→

wi).Supposethisunitismovedfromitoi(i󰀁󰀁

onthebalancedstaterequirement,oneunitinaclusterjinregion[1..i−1]needstobemovedouttoclusterjwithn≥j>i.Weconsiderswappingthesetwounitsatiandj.Tocomparemovingdistancebetweenthesetwocases(beforeandaftertheswap),weconsidertwosituationsshowninFigure5forj≤iandj>i.Followingthesimilarargumentasintheabovecase,themovingdistancebeforetheswap|i−i|+|j−j|islongerthanthatofaftertheswap.

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

2

Thefollowingtheoremshowsthatwhenfourconditionsaremet,overallmovingdistanceisinde-pendentoftheactualschedule.

Theorem2:Whentake-right(take-left)statesgetloadfromgive-left(give-right)states,theoverallmovingdistanceisindependentoftheactualschedule.

Proof:Let’sconsiderschedulesforalltake-rightstatesthatgetloadfromgive-leftstates.Thetake-leftstatesgettingloadfromgive-rightstatescasecanbearguedinasimilarway.Startingfromcluster1andcheckingtowardsclustern(i.e.,alongthepositivedirection),foreachunitofunderloadinatake-rightstatei,assignoneunitofloadfromtheclosestgive-leftstatei(i.e.,aclusterinagive-leftstatewithminimumid).Nowweshowthatallotherassignmentscanbeconvertedtotheaboveschedulewithoutchangingthetotalmovingdistance.Supposeintheabovestate,theunittoicomesfromanon-closestgive-leftstatejandtheunitfromiisassignedtoatake-rightstatejwherei≤j≤i.Byswappingiwithj,totalmovingdistanceremainsthesame,andtheoneunitininow

13

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

i

j(a)

i’

j’

i

j(b)

i’j’

Figure6:Swappingofiandjwithoutchangingthetotalmovingdistance:(a)beforetheswap,and(b)aftertheswap.

comesfromi(seeFigure6).Thiskindofswapcanbedoneiteratively.

󰀁

󰀁󰀁

2

4.5Anoptimalscanin1-Darraysanditsextensionin2-Dmeshes

Inthissubsection,weproposeasimplesender-initiatedoptimalloadbalancealgorithmfor1-Darrays.Theuniquepropertyisthatthealgorithmstartsfromeachclusteringivestate(give-leftandgive-right)inparallelwithouttheneedtobeconcernedwiththedetailoftakestateofotherclusters.Supposeiisinatakestatewherew¯−wi>0,thenwedonotdistinguishtake-rightfromtake-left.Sender-InitiatedOptimalLoadBalancein1-DArrays

→

1.Foreachclusteriingivestate,theclusterheadsendswiunitstoitsrightneighborandsends←

wiunitstoitsleftneighbor.

2.Foreachclusteriintakestate,whentheclusterheadsensesseveralbypassingunits,itinter-sectsasmanyunitsaspossibletofillinits“holes”.Unintersectedunitsmovealongthesamedirection.

Theorem3:Theproposedgreedyscheduleensuresanoptimalschedulein1-Darrays.

Proof:ItsufficestoshowthecaseinFigure5isavoided.Thatis,thetwoconditionsrelatedtotakestatearesatisfied.Basedonthealgorithm,whenaunitispassedtoifromrighttoleftasshowninFigure5,itimpliesthatsubarray[i...n]isinoverloadedstate;similarly,whenaunitispassedtoj

󰀁

󰀁

󰀁

fromlefttoright,thesubarray[1...j]isinoverloadedstate.Sincei2.

14

Whenthescanprocedureisextendedfrom1-Darraysto2-Dmeshes,thescanprocedureisappliedtwice:onceonallrows,followedbyonceonallcolumns.This2-DscanprocessrepresentsthecoreofSMART.However,thisapproachisnolongeroptimalin2-Dmeshes.Forexample,considera2×2meshM[1,1]=3,M[1,2]=1,M[2,1]=3,andM[2,2]=5.AscanonrowswillchangeloaddistributionofthemeshtoM[1,1]=2,M[1,2]=2,M[2,1]=4,andM[2,2]=4,andascanoncolumnswillbalancethemeshtoM[1,1]=3,M[1,2]=3,M[2,1]=3,andM[2,2]=3.Atotalof4movesoccur,however,theoptimalsolutionrequiresonly2movesfromM[2,2]toM[1,2]directly.Theorem4:Theratiobetweenthe2-Dscanandtheoptimalsolutionintermsofthenumberofmovesisboundedby2.

Proof:Duringthe2-Dscan,wastedmovesoccurduringthefirstscanwhena(globally)underloadedclusterimovestheloadtoanother(globally)underloadedclusterj.SupposeLunitsofloadaremovedfromiandj.Lunitsofloadforjarenecessary,whileLunitsforiarewastedunits.Asimilarsituationoccurswhena(globally)overloadedclusterimovesloadtoanother(globally)overloadedclusterj.Inthiscase,Lunitsforjarewasted,whileLunitsforiarenecessary.Itiseasytofollowthatforeachwastedmovethereisamatchingnecessarymove,therefore,theratioisboundedby2.2

4.6SeveralvariationsofSMART

InSMART,an“aggressive”approachisusedwherealocal“give”stateinaroworcolumncanbeaglobal“take”state.Toavoidthissituation,a“conservative”approachcanbeusedtodecidelocal“give”and“take”statebasedonglobalaverageinformation.

Besidestheprefixsumofthefirstigridsinarow(orcolumn)inthepositivedirection,i.e.,vi=󰀁i󰀁n󰀁n

󰀃󰀃

w,anothernegativedirectionprefixsumisexploited,wherev=w,andv=i1j=1jj=ijj=1wjisthetotalsumintherow(orcolumn).Thenegativeprefixsumisachievedinthenegativesweepwheretheaverageissendingout.Now,wl=vn/nistheaveragenumberofsensorsinalocal

󰀁󰀁n

balancedstatewithrespecttothecurrentrow(orcolumn).v=nj=1wijistheglobaltotali=1sum.Thenwg=v/n2istheaveragenumberofsensorsinaglobalbalancedstate.Wedefineathirdkindofaverageaswm=|wg−wl|/2,themeanofglobalandlocalbalancedstate.Thisaverageistoachieveacompromisebetweenconservativeandaggressiveapproaches.

ThevariationdiffersfromtheoriginalSMARTinitsdefinitionofthresholdwusedtodetermine

15

the“give/take”state.Still,whenwi−w=0,gridiisinthe“neutral”state.Whenwi−w>0,itisoverloadedandinthe“give”state;andwhenwi−w<0,itisunderloadedandinthe“take”state.wcanbeoneofthreepossiblechoices:wl,wg,andwm.Again,vi=iwisthetheprefixsuminthebalancedstateunderthegiventhresholdw,andvi󰀃=(n−i+1)wisthatofthenegativedirection.wshouldberoundedtoaninteger.

IntheoriginalSMART,thethresholdisbasedonthelocalaverage,wl,when“give”and“take”statesarebalancedinarow(orcolumn).Withachangingthreshold,suchabalanceisnolonger

→

held.Thatis,therecouldbemore“give”than“take”gridsandviceversa.Therefore,wiforloadin

thepositivedirection(orsimplygive-right)and←wiforloadinthenegativedirection(give-left)arechangedasfollows:agridisin“give”stateifitsvalueisoverthegiventhresholdw.Theamountofexcessiveloadtobetransferredtoitsright(orleft)dependsontheamountofunderloadtoitsright(orleft)providedthatamountdoesnotcausetheunderloadofthecurrentnode.Moreformally,wehave

→󰀃󰀃wi=min{wi−w,max{vi+1−vi+1,0}}←

→

,max{(vi−1−vi−1),0}}wi=min{(wi−w)−wi

(5)(6)

Thethreshold-basedscanapproach

1.Ifw=wl,determineglobalbalancedvaluewg.2.Performarowscanfollowedbyacolumnscanusingtheselectedw.3.Ifw=wl,repeatstep(2)usingw=wl.

wginstep(1)canbecalculatedduringstep(2).Basically,wgisdeterminedafterrowandthencolumnscans.However,inthesescanstherearenoactualsensormovements.Movementsoccuroncewisderivedfromwg.Step(3)isneededsincetheresultofstep(2)cannotguaranteeagloballybalancedstate.Whenw=wm,onevariationofthealgorithmistorepeatstep(2)aconstant(c)numberoftimesbeforeapplyingstep(3).WeuseSMART(g),SMART(l),andSMART(m,c)torepresentthethreshold-basedscanthatusesglobalaverage,localaverage(theoriginalSMART),andmeanofglobalandlocalaverage,respectively.cinSMART(m,c)correspondstothenumberofiterationsofstep(2).

Ifthetotalnumberofsensorsisunknown,moreinformationpropagationisnecessary.Afterthelastclusterofeachrowgetsthetotalnumberinitsrow,onemorescanisgeneratedinthelastcolumn

16

toachievetheglobalaverage.Thenascaninthenegativedirectioninthecolumnisconductedtodistributetheaveragetoeachrow.

5ExtendedSMART

5.1Simplesolutions

The2-Dscandiscussedpreviouslyworksonlywhenthereisnohole,otherwise,certainrowsandcolumnsmaynotbeconnected.Intheworstcase,the2-Dmeshmaybedisconnected.Apre-processingisneededtoplant“seeds”toholesateach1-Dscanandtheseseedswillserveascluster-headsintheseholes.

Plantingseedsinholesinanasymptoticallyoptimalwayisanon-trivialtask.Supposewewanttooptimizetotalmovingdistance,thenumberofmoves,andcommunicationlatency(whereeachse-quentialneighborcommunicationisconsideredonestep).ThetotalmovingdistanceshouldbeO(n2)(asinthecaseofthefirstrowofFigure1),thenumberofmovesshouldbeO(n),andcommunicationlatencyshouldbeO(n).

Aconservativeapproachcouldbesendingoutoneseedatatimetoanadjacentemptycluster.ThiswillworkforthecaseofthethirdrowofFigure1wherekisanumberlargerthan5andthedirectionisfromlefttoright.However,thisapproachdoesnotworkwellforthecaseofthefirstrow,sincethefrontiernode,theclusterheadofthefirstnonemptyclusterintheexpansiondirection,needstocommunicatewiththeleftmostnodeaftereachprobingandexpansion.Thecorresponding

󰀁−1

2

communicationlatencyis2ni=1i=O(n).Notethatifthemovingdistanceisadominatingfactor,ratherthanthecommunicationlatency,thisisstillanacceptablesolution.

Inanaggressiveapproach,eachclusterthathasasufficientnumberofsensors(seeds)cansendoutmultipleseedstocovertherest.Thisapproachcertainlyworksforthecaseofthefirstrow,butfailsforthecaseofthethirdrow.Inthiscase,thetotalmovingdistancewouldbe(n−1)2+(n−3)2+...+32+12=O(n3)sinceclustersingivestatecaninitiatetheprocesssimultaneously.Alsothenumberofmovesis(n−1)+(n−3)+...+3+1=O(n2).

Thesimplerecursivedoublingdoesnotworkeitherforthecaseofthesecondrow,wherethespanofeachexpansionisdoubledinthesubsequentstep.Thisisbecauselognexpansionswillincurat

17

leastn/2×logn=O(nlogn)communicationlatency,assumingtheinitialspanis1.

5.2Optimalseedplantingin1-Darrayswithholes

Weproposeasolutionfortheholeissuethatisasymptoticallyoptimalforseveralparameters,includ-ingcommunicationlatency(O(n)),totalmoves(O(n)),andtotalmovingdistance(O(n2)),assumingthateachclusterknowsonlythestateofitstwoneighborsthroughprobing.Itisalsoassumedthatthesensornetworkissufficientlydensesuchthatglobalw≥2(i.e.,onaverage,eachclusterhas2sensors).Laterwewillresorttoaslightlystrongerconditionwhenthesolutionisextendedfrom1-Darraysto2-Dmeshes.

First,wegivesomenotationsusedinthesolution.Asegment,Si,isamaximumsequenceofnon-emptyclusters.WiisthesummationofloadinSiandCiisthelengthofSi.NowweintroducetwoimportantconceptsrelatedtoSi:

•Expansionlevel,Li,ofSi:2Li≤Ci<2Li+1.•Energylevel,Ei,ofSi:Ei=Wi−Ci.

ExpansionlevelLideterminesspansofsuccessiveexpansions2Li,2Li+1,2Li+2,...,whereasenergylevelEiindicatesthenumberofdenotablesensorsinthesegment.Eishouldbelargeenoughtocoverholesineachexpansion,i.e.,Ei≥2Li+kforthekthexpansion,whichiscalledtheexpansioncondition.Anyclusterthathasmorethanonesensorisinadenotablestateforprovidingseeds,eventhoughtheclustermaybeinanunderloadedstate.

Thesolutionisbasedonrecursivedoublingofthespanforeachsuccessiveexpansionuntilthereisnosufficientenergyforexpansion,buttheactualsizeofexpansionisgovernedbythecurrentexpansionlevel.ForsegmentSiwithlevelLi,thesequenceofspanis2Li,2Li+1,2Li+2,....Forexample,supposethelengthCiofSiis13,thefirstspanis23=8,makingthenewsegmentwithlength21;thenextexpansionwithspan24=16willincreasethelengthto29,andsoon.

Twoapproaches,reactiveorproactive,canbeusedhere.Inthereactiveapproach,eachclusterwaitsforanexpansionsignalfromoneofitspredecessorsoruntilapre-definedtime-outexpires(thetime-outvalueisgiveninTheorem5below).Thisapproachtradespotentiallongdelayforsmalltotalmovingdistanceandtotalmoves.Thisapproachoperatesinthesynchronizedenvironment,wherethe

18

synchronizationpointcanbesetduringtheinitialdeploymentphase.Intheproactiveapproach,eachsegmentactsindependentlyforexpansion.Thisapproachhasminimumcommunicationlatencybutwithoccasionalextrasensormovementsforthelackofsynchronization.Thesolutioncanbedescribedbythefollowingsteps:(1)Followingthepositivedirection,eachsegmentperformsexpansionthroughrecursivedoubling,wheneitheritisinformedfromapredecessorsegmentorapredefinedtimeoutexpiresinthereactiveapproach,orwithoutwaitingforanysignalortimeoutforactivationintheproactiveapproach,untiliteitherreachesthelastclusterofthe1-Darrayorfailstheexpansioncondition.(2)Repeatstep1.forthenegativedirectionexceptnotimeoutisneededatthisstep.Theefficiencyofthemethoddependsontheworstcasetimeoutinthereactiveapproachandexcessivemovementinparallelseed-plantingintheproactiveapproach.Thenexttheoremshowsthatitissufficienttosettimeoutto5(i−1),whereiistheidofthefirstclusterinthesegment.ThetotalmovingdistanceintheproactiveapproachisstillboundedwithinO(n2).

Theorem5:IneachsegmentSinascan,thetotalmovingdistanceinconstructingSisboundedbyC2andthecommunicationlatencyisboundedby5C.

Proof:Weprovebyinduction,whenSiexpandstoconnectSjtoformanewSkalongthepositivedi-rection,weassumethatCiisthespanSiusedtoconnectSjandCjisthespanofthenon-overlappingregioninSjasinFigure7.NotethatSimaymergewithanothersegmentSjtoformanewseg-ment,Sk,astheresultoftheexpansionofSi(asshowninFigure7).SkwillcalculateitsWkandLkaccordingly.ThespecialcaseSjdoesnotexistandhasthelength0.Thefollowingproofstillapplies.Basedontheinduction,thelatencyintheformationofSiisboundedby5Ci.Inthecurrentexpansion,CiisneededforthefrontiernodetoinformallrelevantclustersalongthenegativedirectioninSiandittakesCi+Citimetopassseedstorelevantpositions.Finally,ittakesCjstepstoreachthefrontierofSk(i.e.,therightmostnodeinSj).UsingthefactthatCi≤Ci<2Ci(expansionconditions),wehave5Ci+Ci+(Ci+Ci)+Cj<5(Ci+Ci+Cj)=5Ck.

Similarly,weshowtotalmovingdistancebyinduction.Basedontheinduction,theformationofSi

󰀁Ci󰀁−1

2

isboundedbyCi.Inthecurrentexpansion,thetotalmovingdistanceisboundedbyl=0(Ci+l)=CiCi+Ci(Ci−1)/2.Intheproactiveapproach,theformationofSjneedstobeincludedwhichis

2

<(Ci+Cj)2.UsingthefactthatCi≤Ci<2Ci,wehaveCi2+CiCi+Ci(Ci−1)/2+boundedbyCj

2

(Ci+Cj)2<(Ci+Ci+Cj)2=Ck

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

󰀁

2

Sincethemethodinvolvestwosweeps,theoverallmovingdistanceisclearlyboundedbyO(n2)

19

expansion

Ci

Si(Ci)

󰀁

CjSj(Cj)

󰀁

Sk(Ck)

Figure7:Themergingoftwosegments.

andtheoverallcommunicationlatencyisboundedbyO(n).TotalmovesareboundedbyO(n)inthereactiveapproach,andbyO(nlogn)intheproactiveapproach.Inthelattercase,clusterscanplantseedsinparallel,butrecursivedoublinglimitsparallelmergingtolognlevelsofthemergingtree.Therefore,theproposedmethodintheproactivemodeisoptimalforthethreeparameters.

Thefollowingtheoremshowsthatnotimeoutisneededinthesecondscanandprovesthecorrect-nessofthe1-Dscanapproach.Thepostfixofthe1-Darrayisasubarraythatcontainsthelastclusterinthearray.

Theorem6:Assumetheaverageloadisatleast2foreachcluster.Afterthefirstscan,atleastonepostfixofthe1-Darrayisasegment.Inthesecondscan,notimeoutisneeded.Allholeswillbefilled.Proof:Itisassumedthataverageloadforeachclusterisatleast2.SupposeS1,S2,...,Sk−1,Skisthesequenceofsegmentsafterstep1ofpre-processing,whereforeachSi(exceptSk),Ei<2Li,

󰀁−1󰀁k−1

thatis,Wi<2Ci.IfweletkW=WandiMi=1i=1Ci=CM,wehaveWM<2CM.Basedontheassumptionofatleastaverageloadof2foreachcluster,wehaveWM+Wk≥2CM+2Ck>WM+2Ck,therefore,Wk>2Ck.Skhassufficientenergyforexpansion.TheonlycaseforpreventingsuchanexpansionisthatSkincludesthelastclusterinthe1-Darray.Therefore,Skisapostfixofthe1-Darray.

Duringstep2ofpre-processing,sinceSkhassufficientenergy,itwillfillinthe“gap”(acon-secutivesequenceofemptyclusters)betweenSkandSk−1byplantingseedsinholesbetweenthem.Followingthesameargument,thenewlyformedsegmentwillhavesufficientenergytofillthenextgap.Inthisway,allgapswillbefilledafterthesecondscan.

2

TheresultfromTheorem6showsthatthescanprocesscanbecombinedwiththepre-processing(plantingtheseeds).Thatis,thescanprocesscanstartatstep2ofthepre-processing.

20

5.3ExtendedSMART

Nowletusextendtheapproachfrom1-Dto2-D.Thefirstissueistoensurethateach1-Drowarrayinthe2-Dmeshmeetsw≥2.Insteadofenforcingit(whichisimpossible),weproposeasmoothingprocessonallcolumnsbeforethepre-processingonrows.Thesmoothingprocessoncolumnsincludespre-processing(i.e.,plantseedsinholes)andscan(i.e.,loadbalance).Thiscolumn-wisesmoothingprocessdoesnotcompletelyremoveholesorbalanceloadalongcolumnsunlessthenumberofsensorsineachcolumnisatleast2ninitially.However,whenthesensornetworkissufficientlydense,eachrowwillhavew≥2afterthecolumn-wisesmoothingprocess.Thefollowingtheoremshowsthedensityrequirement.

Theorem7Supposetheaveragenumberofsensorsinaclusterisatleast4.Aftercolumn-wisesmoothing,eachrowwillhaveatleast2nsensors.

Proof:Wetrytofindthemaximumnumberofsensorsthatcanbedeployedwhenatleastonerowstillhaslessthan2nsensorsaftercolumn-wisesmoothing.Ifthatnumberislessthan4n2,thetheoremisproven.

Assumeinitiallykcolumnshaveloadofatleast2nandtheremainingn−kcolumnshaveloadunder2n.Theformerkcolumnswillachieveloadbalancingaftersmoothing,whilethelattern−kcolumnswillnot.Withoutlossofgenerality,weassumerow1(i.e.,firstnodesinallcolumns)haslessthan2nsensorsaftersmoothing.Allthefirstnodesofthosen−kcolumnsthathavenotachievedthebalancedstateareholes.Themaximumtotalloadofnodesotherthanthefirstnodesinthesen−kcolumnsisboundedby(n−k)(2n−1).Theloadsoffirstnodesoftheotherkcolumnsthathaveachievedthebalancedstatealongcolumnsareassumedtobei1,i2,...,ik,respectively.Basedonthebalancedstatedefinition,themaximumtotalloadofnodesotherthanthefirstnodesinthesekcolumnsisboundedby(n−1)[(i1+1)+(i2+1)+...(ik+1)].Therefore,thetotalnumberisboundedbyI+(n−1)(I+k)+(n−k)(2n−1)≤(2n−1)+(n−1)(2n+k−1)+(n−k)(2n−1)sinceI=i1+i2+...+ik≤2n−1.Clearly,thetotalnumberisboundedby4n2−(2+k)n<4n2.Thisnumberismaximizedwhenk=1andthecorrespondingdistributionisshowninFigure8.Withtheaboveresult,theextendedSMARTprotocolcanberesolvedtothefollowingsteps:•Step1(column-wisesmoothing):Pre-processingoncolumn(positivedirection).Ifthelastclusterfailscondition1(discussedbelow),step1terminates,otherwise,simultaneouspre-21

2

2n−12n

0

. . .. . ..... . . . . . 00

...

2n2n

2n−12n−12n−1

Figure8:Aworstcasedistribution.

processingandscanoncolumn(negativedirection).Ifthefirstclusterfailscondition2(dis-cussedbelow),step1terminates,otherwise,scanoncolumn(positivedirection).

•Step2(row-wisepre-processingandscan):Pre-processingonrow(positive),followedbysi-multaneouspre-processingandscanonrow(negative),finallyscanonrow(positive).•Step3(column-wisescan):Scanoncolumn(negativefollowedbypositive).

Bothconditions1and2areusedforearlyterminationwhenaparticularcolumnhaslessthan2nsensors.Condition1isdefinedas:thelastclusterisincludedinasegmentSandW≥2C.Condition2isdefinedas:thefirstclusterisincludedinasegmentSsuchthatC=nandW≥2n.Instep1,eachcolumnneeds1,2or3sweepsdependingonwhetherthatcolumnhas2nsensorsornot.Instep2,3sweepsareneededand2sweepsareneededinstep3.Intheworstcase,8sweepsareneeded.Theaboveapproachhaspotentialdrawbacksingeneratinglongercommunicationlatencyevenintheabsenceofholes.Toresolvethisissue,weintroducesomesimplebookkeeping.Oncethefirstsweepofstep1iscompleted,eachendnodeinthelastrowwillsetaflagto1wheneveritregistersatleast2nsensorsinthecorrespondingsegment.Ifallflagsinthelastrowareset,step3canbeskipped.Checkingwhetherallflagsaresetcanbedoneinparallelwithstep2,whichneeds2nstepswithtwosweepsonthelastrow.ThefirstsweepisascanusingbooleanANDandthesecondisabroadcastofthescanvalueofthefirstsweepwhichisabooleanvalue(1forallflagssetand0forotherwise).Withtheabovemodification,theworstcasenumberofsweepsisreducedto5.Onemoresweepcanbeeliminatedbycombiningpre-processingandscaninstep1.Wheneverthefirstclusteris

22

includedinthecurrentsegment,thescanprocessalsostarts.Attheendofthefirstsweep,ifthecurrentsegmentincludesbothfirstandlastclusters,thethirdsweepinstep1canbeeliminatedsinceitsfunctioncanbedoneatthesecondsweep.TheoptimizationfornumberofmovesdiscussedinSectionIIIcanstillbeusedafterthescanprocessstarts.However,thenumberofmovesduringthesmoothingandpre-processingphasescannotbefurtherreduced.

6Simulation

6.1Simulationenvironment

Weuseacustomsimulator.Theinitialdeploymentitgeneratescouldbeauniformornormalrandomdistribution.Wesetupthesimulationina500×500area,whichisthetargetfield.Thetunableparametersinoursimulationareasfollows.(1)Clusternumbersn×n.Largencanimprovethespeedofdeploymentwhilesmallncanachievemorebalancedresults.Weuse4and10asn’svalues.(2)NumberofsensorsN.Wehaveprovedthatatleast4n2sensorsareneededtoguaranteethevalidationofSMART.Therefore,wevaryN’svaluefrom400to1000.Wealsoincludecasesofunder4n2sensorstochecktherobustnessofSMART.(3)Normaldistributionparameterσ.σisthestandarddeviationofthenormaldistributionoftheinitialdeployment,whichcancontrolthedensitydegreeofthesensorclustering.Weuse1to5asitsvalues.Whenσis1,around98%sensorsarein10%regionofthearea.Whenσis10,thedistributionisveryclosetouniformrandomdistribution.Foreachtunableparameter,thesimulationisrepeated1000times.Inadditiontotheproposedalgorithms,wealsosimulatethetraditionalloadbalancingalgorithmsdiffusion(DIFF),dimensionexchange(EXCH),andtheVoronoi-basedlocalizedsensorredistributionalgorithm(VOR)forcomparison.Theperformancemetricsare(a)deploymentqualityand(b)cost.Deploymentqualityisshownbythebalancedegreemeasuredbytwosimulationresults.Oneisthestandarddeviationofthenumberofsensorsinalltheclusters.Theotherisgrads,whichisthedifferencebetweenthelargestclusterandthesmallestone.Deploymentcostismeasuredbythetimeofdeployment,intermsofrounds,andenergyconsumption,intermsofoverallmovingdistance.

23

40

DIFFEXCH 35SMART 30RoundsRounds 25 20 15 10 5 400

40

DIFFEXCH 35SMART 30 25 20 15 10 5

Rounds 100 90 80 70 60 50 40 30 20 10

DIFFEXCHSMART

500 600 700 800 900 1000

0 400

500 600 700 800 900 1000

0 400

500 600 700 800 900 1000

Number of nodesNumber of nodesNumber of nodes

(a)n=4,σ=1

350000

DIFFEXCHSMART

Moving distance 220000

(b)n=4,σ=5

DIFFEXCH

200000SMARTMoving distance 180000 160000 140000 120000 100000

400000

(c)n=10,σ=1

DIFFEXCH

350000SMART 300000 250000 200000 150000 100000 50000

400

300000Moving distance 250000

200000

150000

100000

400

500 600 700 800 900 1000

80000

400

500 600 700 800 900 1000 500 600 700 800 900 1000

Number of nodesNumber of nodesNumber of nodes

(d)n=4,σ=1(e)n=4,σ=5(f)n=10,σ=1

Figure9:ComparisonofDIFF,EXCH,andSMARTinroundnumber(a)-(c),anddistance(d)-(f).

6.2Simulationresults

Figure9comparesthenumberofroundsandmovingdistanceofthesethreealgorithms,DIFF,EXCH,andSMARTinuniformrandomdistribution.From(a)-(c)wecanseethattheproposedSMARThassmallandstablenumberofrounds.Whentheinitialdeploymentisrelativelybalancedandnissmall,everyrowcouldhavemorethan2nsensors,thusithas5rounds;otherwise,ittakes8rounds(theworstcase).Diffusionanddimensionexchangebothhavelargenumbersofrounds,whichincreasewiththegrowthofnodenumber,especiallywhennislargeandtheinitialdeploymentisuneven.(d)-(f)aretheoverallmovingdistancecomparison.Wecanseethattheoverallsensormovingdistanceisproportionaltothenumberofsensors.Therefore,averagemovingdistanceofasensorisinsensitivetonodenumbersinallthesealgorithms.Amongthethree,SMARThasthelargestmovingdistance.Thisisbecauseitachievesthemostbalancedfinalstate,whichleadstomoresensormovements.Figures10(a)and(b)showthebalancedegreeoftheresultsofthesethreealgorithmsbystandarddeviationinuniformrandomdistribution.SMARTachievesabalancedfinalstate,anditsstandard

24

4.5

DIFFEXCH 4SMARTStandard deviation 500

600

700

800

900

1000

14

DIFFEXCH 12SMART 10 8 6 4 2 0 400

Standard deviation 3.5 3 2.5 2 1.5 1 0.5 400

500 600 700 800 900 1000

Number of nodesNumber of nodes

(a)Standarddeviation(n=4)

7

DIFFEXCH 6SMART 5GradsGrads 500

600

700

800

900

1000

4 3 2 1 0 400

(b)Standarddeviation,(n=10)

16

DIFFEXCH 14SMART 12 10 8 6 4 2 0 400

500

600

700

800

900

1000

Number of nodesNumber of nodes

(c)Grads,(n=4)(d)Grads,(n=10)

Figure10:BalancedegreeofDIFF,EXCH,andSMART(σ=1).

deviationisnomorethan2.(c)and(d)areintermsofgrads.ThegradsofSMARTisnomorethan2,andthegradsinaroworacolumnisnomorethan1.InDIFFandEXCH,onlyrelativebalancedstate,theneighboringbalance,isguaranteed.Thatis,thedifferencebetweenadjacentclustersisnomorethan1.Therefore,theresultcouldbealadder-likedistribution,whichleadstoverylargegradsandstandarddeviation.Whennislarge,thegradsofdiffusionanddimensionexchangearelarge,andtheirbalancedegreesarelow.

Figures11(a)(b)(d)and(e)comparethestandarddeviationandmovingdistanceofalgorithmsusingdifferentnormaldistributionparametersσ.Thecurve‘Initial’isthestandarddeviationoftheinitialdeployment.SMARTcanachieveamorebalancedstatethanDIFFandEXCH.SMARTalsooutperformstheminnumberofmoves.InSMART,sensorsmoveatmosttwice,onemoveforverticaldirectionandtheotherforhorizontal;over75%sensorsmoveonlyonce.WhenNis400,andσis1,SMARThas444,diffusionhas1040,anddimensionexchangehas1137.Sincestartupusuallyconsumesmorepowerthanmovingwithinvariablespeed,lessmovementisdesired.(c)isthestandarddeviationand(f)ismovingdistancecomparisonofVORandSMART.WecanseethatVOR

25

200 180 160Standard deviation 140 120 100 80 60 40 20 0 1

DIFFEXCHSMARTInitialStandard deviation 60 50 40 30 20 10 0

DIFFEXCHSMARTInitial

Standard deviation 60 50 40 30 20 10 0

InitialVORO-VORSMART

2 3 4 5 6 1 1.5 2 2.5 3 3.5 4 4.5 5 1 1.5 2 2.5 3 3.5 4 4.5 5

Normal distribution parameterNormal distribution parameterNormal distribution parameter

(a)Standarddeviation,n=4

140000

DIFFEXCH 120000SMARTMoving distanceMoving distance 100000 80000 60000 40000 20000

(b)Standarddeviation,n=10

160000

DIFFEXCH

140000SMART 120000 100000 80000 60000 40000 20000

Moving distance(c)Standarddeviation,n=10

350000 300000 250000 200000 150000 100000 50000

0

VORO-VORSMART

1 2 3 4 5 6

0

1 1.5 2 2.5 3 3.5 4 4.5 5 1 1.5 2 2.5 3 3.5 4 4.5 5

Normal distribution parameterNormal distribution parameterNormal distribution parameter

(d)Movingdistance,n=4(e)Movingdistance,n=10(f)Movingdistance,n=10

Figure11:SMARTcompareswithDIFF,EXCH,andVORusingdifferentσ(N=400).canonlyslightlyreducethestandarddeviationofinitialdeployment.Ithasbeenmentionedin[5]thatthebasicVORalgorithmhasdifficultiesindealingwithhigh-degreeclustering,wheresensorsarecenteredaroundafewlocations.Whenσis1,afterapplyingVOR,theclusteringareastillhashighdensity,whiletheoriginalblankareahaslowdensity.TheoptimizedVOR(O-VOR)proposedtodealwiththisproblemisbetterthanVOR,butSMARTstilloutperformsO-VOR.

VORisdesignedforarelativelysparsesensornetworkthathasauniformrandominitialdeploy-ment,whereasSMARTisdesignedforarelativelydensenetworkwithhigh-degreeclustering.Forfairness,weconductthefollowingsimulationtocomparetheperformanceofSMARTandVORinarelativelysparsenetworkwheretheconditionofTheorem7forSMARTisnotnecessarilysatisfied.Figures12(a)and(b)showthecomparisonsofresultantbalancedegree(intermsofstandarddeviation)andnumberofroundsofSMART,VOR,andO-VOR(σ=3,n=10).In(a),whenNislargerthan400,SMARTguaranteesthebalancedfinalstate,wherethestandarddeviationoftheresultantdeploymentofSMARTshouldbelessthan2.Thisresultisconsistentwiththeanalytical

26

resultsintheprevioussection,whereiftheaveragenumberofsensorsinaclusterislessthan4,somerowsmayhavelessthan2nsensorsaftersmoothing.Whennodenumberissmallerthan400,thestandarddeviationislargerthan2,andthebalancedstatusisnotachieved.However,theincreaseofstandarddeviationissmallandthebalancedegreeofSMARTcanstillbeatthatofVOR.ForVOR,whenthenodenumberissmall,theresultantdeploymentismorebalanced.Withthegrowthofthenumberofdeployednodes,thebalancedegreegetslower.Thisisbecauseinthehigh-degreeclusteringenvironment,whenthecoverageterminationconditionofVORismet,mostareacanbecoveredbyatleastonenode,butVORterminatesbeforenodesintheclusteringareascatterout.(b)isthecomparisonofthenumberofrounds.Atleast400deployednodesareneededtoachievethebestperformance,5rounds,forSMART.Theworstis8rounds.ForVOR,asmallernodenumberleadstofewerrounds.ButVORhasfewerroundsthanSMARTwhenthenodenumberissmallerthan150.O-VORachievesmorebalanceddegreewithsmallerroundnumberthanVOR.

Figures12(c)and(d)arethecomparisonsoftheseveralvariationsofSMART,andalsotheoptimalHungarianbasedmethod(OPT)inuniformandnormalrandomdistributions,respectively(n=10,N=500).SMART(l),SMART(g),andSMART(m,3)aresimulated.Tochecktheeffectofstep(3)inthreshold-basedscanalgorithm,wesimulateSMART(g),whichisSMART(g)withoutstep(3).In(c),SMART(m)hasthemostmovingdistance,whileSMART(g)hasasmallermovingdistancethanSMART(l).OPThasthesmallestmovingdistance.(d)isresultsinnormalrandomdistribution.Withthegrowthofσ,themovingdistancedecreasesandthenumberofmovesdecreasesslightly.SMART(g)andSMART(m)havesmallermovingdistancesthanSMART(l).SMART(m)hasthesmallestamongthethree.SMART(l)hascloseorevenbetterperformancethanOPTbecauseitdoesnotachieveabalancedresultasOPTdoes.

Simulationresultscanbesummarizedasfollows:(1)SMARTachievesamorebalancedstatethandiffusion,dimensionexchange,andVoronoi-basedsensordeploymentmethodsinunevenlydeployedsensornetworks.(2)SMARTneedsfewrounds,whichareboundedby8,forloadbalancing.(3)Thecentralizedoptimalalgorithmhasthebestperformance;amongallvariationsofSMART,SMART(g)hasthebestoverallperformance.(4)SMARTcanbeeffectivewhenusedinrelativelydensesensornetworksasacomplementfortheexistingsensordeploymentmethods.(5)Whennumberofdeployednodesislessthan4n2,theperformanceofSMARTisreduced,sincemoreroundsareneededandbalancedfinalstatecannotbeachieved.(6)Insparsenetwork,SMARTmayneedmoreroundsthanVORtoachieveabalanceddegree,butitstillbeatsVORintermsofstandarddeviation.

󰀁

27

14

VORO-VOR 12SMARTStandard deviationNumber of rounds 300 400

500 600

700 800

900 1000

10 8 6 4 2

0

100 200

12

VORO-VOR 11SMART 10 9 8 7 6

5

100 200

300 400 500 600 700 800 900 1000

Number of nodesNumber of nodes

(a)Standarddeviation

180000OPTSMART(l) 160000SMART(g’)SMART(g) 140000SMART(m,3) 120000 100000 80000 60000 40000 20000 100 200 300 400 500 600 700 800 900 1000Number of nodes

2e+06 1.8e+06 1.6e+06Total moving distance 1.4e+06 1.2e+06 1e+06 800000 600000 400000 200000

0 1

(b)Roundnumber

OPTSMART(l)SMART(g)SMART(m,3)Total moving distance 2 3 4 5 6 7 8 9 10

Normal distribution parameter

(c)Movingdistance,uniform(d)Movingdistance,normal

Figure12:PropertyanalysisofSMARTandVOR;comparationeofvariationsofSMART.

7Conclusion

Inthispaper,wehaveproposedascan-basedmovement-assistedsensordeploymentalgorithm,whichisahybridapproachoflocalandglobalmethods.Wehaveconsideredauniqueissuecalledcommu-nicationhole,wherecertainsensingareashavenodeployedsensors.Amethodofseed-plantinghasbeenproposedtomoveonesenortoeachuncoveredareabeforethescanningprocess.WealsodevelopanoptimalsolutionwhichistheHungarianmethodbased.Simulationresultsshowthattheproposedmethodcanachieveevendeploymentofsensorswithmodestcosts.Inthefuture,wewillperformindepthsimulationonenergyconsumptionofsensordeploymentalgorithmsanddesignsomeintra-clusterbalancingalgorithmstoachievehighresolutionloadbalancing.Wealsoplantoconsiderthecasewhereonlypartsofthesensorsaremobile.Inthiscase,theultimategoalistomaximizetheminimumloadofthesegrids.Thisisamoregeneralmeasurementforthebalancedegreeofthefinaldistribution.

28

References

[1]I.F.Akyildiz,W.Su,Y.Sankrasubramaniam,andE.Cayirci,“Asurveyonsensornetworks,”IEEE

CommunicationMagazine,pp.102–114,August2002.

[2]D.E.CullerandW.Hong,“Wirelesssensornetworks,”CommunicationsoftheACM,vol.47,no.6,pp.

30–33,June2004.

[3]G.T.Sibley,M.H.Rahimi,andG.S.Sukhatme,“Robomote:Atinymobilerobotplatformforlarge-scale

sensornetworks,”inProceedingsofIEEEInternationalConferenceonRoboticsandAutomation(ICRA),2002.

[4]O.Khatib,“Realtimeobstacleavoidanceformanipulatorsandmobilerobots,”InternationalJournalof

RoboticsResearch,vol.5,no.1,pp.90–98,August1986.

[5]G.Wang,G.Cao,andT.LaPorta,“Movement-assistedsensordeployment,”inProceedingsofIEEE

INFOCOM,March2004.

[6]Y.ZouandK.Chakrabarty,“Sensordeploymentandtargetlocalizationbasedonvirtualforces,”in

ProceedingsofIEEEINFOCOM,March2003.

[7]M.LocateliandU.Raber,“Packingequalcirclesinasquare:adeterministicglobaloptimizationap-proach,”DiscreteAppliedMathematics,vol.122,pp.139–166,Octobor2002.

[8]A.Howard,M.J.Mataric,andG.S.Sukhatme,“Anincrementalself-deploymentalgorithmformobile

sensornetworks,”AutonomousRobots,SpecialIssueonIntelligentEmbeddedSystems,September2002.[9]G.E.Blelloch,“Scansasprimitiveparalleloperations,”IEEETransactionsonComputers,vol.38,no.

11,pp.1526–1538,November19.

[10]J.Albowicz,A.Chen,andL.Zhang,“Recursivepositionestimationinsensornetworks,”inProceedings

ofIEEEICNP,pp.35–41.

[11]N.Bulusu,J.Heidemann,andD.Estrin,“GPS-lesslowcostoutdoorlocalizationforverysmalldevices,”

IEEEpersonalcommunications,SpecialIssueonSmartSpacesandEnvironment,vol.7,no.5,pp.28–34,Octobor2000.

[12]A.Howard,M.J.Mataric,andG.S.Sukhatme,“Relaxationonamesh:aformationforgeneralized

localization.,”inProceedingsoftheIEEE/RSJInternationalConferenceonIntelligentRobotsandSystems(IROS),2001.

[13]T.L.CasavantandJ.G.Kuhl,“Acommunicationfiniteautomataapproachtomodelingdistributed

computationanditsapplicationtodistributeddecision-making,”IEEETransactionsonComputers,vol.39,no.5,pp.628–639,May1990.

29

[14]G.Cybenko,“Loadbalancingfordistributedmemorymultiprocessors,”JournalofParallelandDis-tributedComputing,vol.7,pp.279–301,19.

[15]H.C.LinandC.S.Raghavendra,“Adynamicloadbalancingpolicywithacentraljobdispatcher(lbc),”

IEEETransactionsonSoftwareEngineering,vol.18,no.2,pp.148–158,February1992.

[16]L.M.Ni,C.W.Xu,andT.B.Gendreau,“Adistributeddraftingalgorithmforloadbalancing,”IEEE

TransactionsonSoftwareEngineering,vol.11,no.10,pp.1153–1161,Octobor1985.

[17]C.Z.XuandF.C.M.Lau,LoadBalancinginParallelComputers,KluwerAcademicPublishers,1997.[18]T.Clouqueur,V.Phipatanasuphorn,P.Ramanathan,andK.K.Saluja,“Sensordeploymentstrategyfor

targetdetection,”inProceedingsofWSNA,2002.

[19]S.Dhillon,K.Chakrabarty,andS.Iyengar,“Sensorplacementforgridcoverageunderimprecisedetec-tions,”inProceedingsofInternationalConferenceonInformationFusion,2002.

[20]S.Meguerdichian,F.Koushanfar,G.Qu,andM.Potkonjak,“Exposureinwirelessad-hocsensornet-works,”inProceedingsofMobicom,2001.

[21]D.Du,F.Hwang,andS.Fortune,“Voronoidiagramsanddelaunaytriangulations,”EuclideanGeometry

andComputers,1992.

[22]G.Wang,G.Cao,T.LaPorta,andW.Zhang,“Sensorrelocationinmobilesensornetworks,”inProceed-ingsofIEEEINFOCOM,2005.

[23]G.Wang,G.Cao,andT.LaPorta,“Movement-assistedsensordeployment,”IEEETransactionson

MobileComputing,vol.5,no.6,pp.0–652,2006.[24]“http://www.darpa.mil/ato/progarms/shm/index.html,”.

[25]S.Chellappan,X.Bai,B.Ma,andD.Xuan,“Mobilitylimitedflip-basedsensornetworksdeployment,”

inProceedingsofIEEEMASS,2005.

[26]“Dictionaryofalgorithmsanddatastructures,”2005,http://www.nist.gov/dads/HTML/munkresAssignment

.html.

[27]C.H.PapadimitriouandK.Steiglitz,Combinatorialoptimization,algorithmsandcomplexity,Dover

publications,INC,1998.

[28]O.YounisandS.Fahmy,“Distributedclusteringinad-hocsensornetworks:Ahybrid,energy-efficient

approach,”inProceedingsofIEEEINFOCOM,March2004.

30