搜索
34520115CHINESEJOURNALOFCOMPUTERSVol.34No.5May2011:20110110;:20110401.(60673127)(2007AA01Z404)(BE2008135)(20103218110017)(20100481133)(1001005B).,,1985,,.Email:liangliu@nuaa.edu.cn.,,1953,,,.,,1988,,.,,1979,,.刘亮秦小麟郑桂能李博涵(210016),.ESA(EnergyefficientSpatialwindowqueryprocessingAlgorithm).,,,,,.ESA,.ESA,.,ESA.,.,ESAIWQE(ItinerarybasedWindowQueryExecution).:,ESAIWQE.;;;;;TP393DOI:10.3724/SP.J.1016.2011.00763AnEnergyEfficientSpatialWindowQueryProcessingAlgorithminWirelessSensorNetworksLIULiangQINXiaoLinZHENGGuiNengLIBoHan(CollegeofInformationScience&Technology,NanjingUniversityofAeronauticsandAstronautics,Nanjing210016)AbstractTheenergyconsumptionofexistingspatialwindowqueryprocessingalgorithmsinwirelesssensornetworksisfairyhigh.Whensomesensornodesfail,thequeryprocessofthesealgorithmsisverylikelytobeinterruptedandunabletoreturnqueryresult.AnenergyefficientspatialwindowqueryprocessingalgorithmcalledESAisproposedinthispaper.Itdividesthequeryregionintoseveralgrids.Eachgridhasaclusternodewhichcollectsthesensorydatainit,aggregatesthedatatoderivepartialqueryresultandsendsittotheclusternodeinthenextgrid.Theaboveprocessisrepeateduntilallnodeswithinthequeryregionaretraversedinordertogeneratethefinalqueryresult.ESAonlyrequireseachnodewithinthequeryregionsenddatamessageonce,whichreducesthedatamessages.TheauthorsproposetwogriddividingandclusternodeselectionalgorithmsaccordingtotheESAsenergyconsumptionformulatoreducetheenergyconsumptionofdistributingthequerymessages.Then,theauthorsdesignaqueryprocessingrecoveryalgorithmusingnoderedundancy,whichavoidstheinterruptionofESAduetonodefailures,andtwodatacollectionalgorithmstoreducetheenergyconsumptionduringtheprocesswheretheclusternodescollectthesensorydataofitsneighbors.Finally,theperformanceofESAandIWQE(itinerarybasedwindowqueryexecution)isanalyzedsystematically.AnalyticalandexperimentalresultsshowthatinmostcasesESAoutperformsIWQEintermsofenergyconsumption,querysuccessrateandqueryresultquality.KeywordsInternetofThings;wirelesssensornetworks;queryprocessing;spatialwindowquery;energyefficiency;nodefailuretolerance1,,.,[1],.,,.,.,[212].,,.IWQE[1](ItinerarybasedWindowQueryExecution),,:(1);(2);(3),.,ESA(EnergyefficientSpatialwindowqueryprocessingAlgorithm).,ESA,,(),,,,,.,;,.,.:,ESAIWQE.,ESA:,.,ESA,.,ESA,.ESA,,.2,;3ESA,ESA,ESA,ESAIWQE;4ESAIWQE;5.2.(1).[2]TAG(TinyAggregationserviceforadhocsensornetworks).,.,7642011,,,,.[35]R[13]TAG,.,,.[6]TAGSTWinFlood(SpatioTemporalWindowFloodalgorithm).3:[14],;,,;.TAG,STWinFlood,.[712],.[1516],.[17],,.(2).,,,.,[1](ItinerarybaseddataCollectionalgorithm,IC)..()()().,,,,,.1,.S1,ICABCD2.S1,S1{a,b,c,d,S2},S1.S1,{a,b,c,d,S1,S2}max{a,b,c,d,S1,S2}.S1S2,max{a,b,c,d,S1,S2}S2.,S1,S1.S2,,S2{a,b,c,d,e,f,S1,S3}{e,f,S3}S2,S2S1max{a,b,c,d,S1,S2}max{a,b,c,d,e,f,S1,S2,S3},.,S4,S4ABCD.12,[1]ICIWQE(3).[14],IC3,,.,[1]3/2.,[1820]ICK,K.7655:3IWQE,,.:(1).,.,,(),;(2).2,,(S2S3),,;(3).2,efS3,S2,,ghijS4.33.1[1,1820]..R.nn.1EtEr,1,E.E=Et+nnEr.,1E.abfd(a,b).SWQ(sw),sw,whA.swM.Sq.Sa.Etotal=Ef+Ec+Eb,,Ef;Ec;Eb..3.2,ESA,4,ESA3:(1).,4a.(2),.cgg,gncgn,cgn.:ESA:gncg,gncgncgn.,cgncg,gn.gncg,cgn.cgngn,cggncgn,,.,,.(3).76620114ESA1,S1,ESAABCD()5.{a,b,c,d,S2}S1,S2{a,b,c,d}.S1S2ABEF.S2,,abcd.{a,b,c,d}S2.S2{a,b,c,d}S1,ABEF,{a,b,c,d,S1,S2}max{a,b,c,d,S1,S2}.{e,f,S3}S2S3{e,f},S2S3EFGH.S2max{a,b,c,d,S1,S2}S3.{e,f}.,S3,S3S2max{a,b,c,d,S1,S2}{e,f}EFGHmax{a,b,c,d,e,f,S1,S2,S3},.,i,iABCD.,ABCD,ESA413(),416.,ESA,.3.4.,.ESA,.5,S2ABEF,{a,b,c,S1},,{a,b,c,S1}ABKLmax{a,b,c,S1}.a,S1bcS2,a.aABKLmax{a,b,c,S1}.S2,,KLCD.,S4,ghS4.,IWQE,ESA,.5ESA6ABCD,,ESA.6,fd(S2,G)fd(S2,K)fd(E,G)fd(F,K).S2EFGK,EFGK,.,:S2ABEF,GHIJ(fd(G,J)),7675:GHIJ.6,GHIJ,GHIJf,f.3.3ESA,ESA,ESA.ESANggi(1iNg),ginsi(1iNg),ci(1iNg).ESAfd(n,ci)R,nnsi-ci,1iNgfd(ci-1,n)R,nnsi,2iNg(1)ESA,c1.()..,ESAEc(ESA)=SqE+(Ng-1)SqE+(Ng-1)SaE+(M-Ng)SaE(2),Ec(ESA)=NgSqE+(M-1)SaE(3),:(1),;.(2).,().,().(3),ESA.,ESA,ESA,.,.Ng,,.,,,,Ng.,:,,.Ng=A/Ag,Ag,(3),Ag,Ec(ESA).,ESA,gi(1iNg),Ag,.1.GBA.:c,Nc:ch,ccgn1.cgn=NULL;2.IFNc.size==03.h=0;RETURN;4.ENDIF5.//NcCD6.SNc=sort(Nc);7.cgn=SNc[1];8.i=SNc.size;9.WHILEi110.//SNc[i]11.//{SNc[1],,SNc[i-1]}12.IFfc(SNc[i],{SNc[1],,SNc[i-1]})istrue13.cgn=SNc[i];BREAK;14.ELSE15.i=i-1;CONTINUE;16.ENDIF17.ENDWHILE18.h=dist(cgn,CD).//hcgnCD:GBA(GridBasedAlgorithm)GAA(GridAreabasedAlgorithm).,7,cRPS.,CDPSABCDc.CDPQdef,dfg.cCDPQNc.ns(x)x.dist(n,l)nl.ns,n7682011s,fc(n,s),.cABCD,CDEF.cgn,gncgn.ccgngnh:(1)GBAGBA:NcCD,SNc.SNcSNc[i](1i|SNc|),:{SNc[1],,SNc[i-1]}SNc[i].cix.cxCD.GBA1.12,Nc,0.,CDPQ,ESA.7,,CDGHCDIJCDKLCDMNc.,ge,GBACDKLc,f.GAAGAA:Ncs,s,ESAgs;Ncx,cxESAgx.Ncgn,CDgn.GAAGBA,.7,Nc={d,e,f,g}.ec,ESACDKL,dfCDMN,gCDGH.{d,e,f,g}gndfdist(d,CD)dist(f,CD).GAACDMNc,f.(2)8,cABCD,CDMNf.fCDMN,i,.,CDMN(d),,;f,.,:CDMNrg,rg,.8deg,CDGHCDIJCDKL..8CDKL.CDMN,,,.,8degCDKLmax{a,b,c,d,e,g},ABKL.,.,8f,eKLEF.787695:(3)cgg,gncgn.gn.cgn,,.,,,.,9,cABCD,CDMNf,CDMN{d,e,f,g,h,i}.,f..1.fCDMN,gn.DC(DistancebasedDataCollectionAlgorithm),,IDC(ImprovedDistancebasedDataCollectionAlgorithm).DC,CDMNCD,,:1.CDMNs,c,CDMNns(CDMN);2.sns(CDMN)fCD,sns,ssnsi,1i||sns|,|sns|;3.i1,sf;i1,s