外文翻译原文-分布式无线传感器网络协同信号处理

ECE736:WIRELESSCOMMUNICATIONS1CollaborativeSignalProcessinginDistributedWirelessSensorNetworksMarcoF.DuarteAbstractDistributedwirelesssensornetworkshavebeenproposedasasolutiontoenvironmentsensing,targettracking,datacollectionandothers.Theseproblemsinvolveestimationordetectionproblemsusingdatacollectedbyindividualsensors.DuetothecharacteristicsoftheDWSN,itisdesiredtouseal-gorithmsthatwillallowforlow-costinformationcommunicationandfusion.Someoftherecentapproachestotheseproblemsaredetailedinthispaper.Thereisaheavyfocusondistributedestimationandoptimizationalgorithmsthatfeaturelowerpowerconsumptionandcommunicationrequirementsthanthestandardcentralizedarchitecture.I.INTRODUCTIONRecentadvancesinVLSIandcommunicationtechnologyhavepromotedthedeploymentofdistributedwirelesssensornetworks(DWSN)forenvironmentsensing,targettracking,datacollectionandotherapplications.Thesenetworksarecomposedgenerallybysmall,low-powerdevicesthatin-tegratemicro-sensingandactuationwithon-boardprocess-ingandwirelesscommunicationcapabilities.Unlikepreviousarchitecturesforsensornetworks,DWSNsallowfordis-tributedsensingandsignalprocessing1.ThesequalitiesofaDWSNaredesirablesincethesensorsarebattery-poweredandhavelimitedwirelesscommunicationbandwidth.Therefore,itisreasonabletoshifttheenergyconsumptioninsensorsfromacommunications-dominatingschemetoasensingandcomputation-dominatingscheme.InanormalDWSNarchitecture,thesystemmayperformestimation,detection,classificationlocalizationandtrackingtasks,dependingontheproblemtheDWSNisappliedto.Thesetaskswilloperateindividuallyoneachsensorbyusingsignalsrecordedlocally.Sensorswilllocallyprocessthedatatoreduceitsdimensionalityandthentranmitthedatatoaprocessingcenter,wherefurtherprocessingmaybedone.Thecentermayalsofusethedatafromtheindividualnodestoarriveatasingledatavalueforthewholenetwork.Forsomeofthetasks,decisionsaremadefromthecollecteddata,andthenodesmaysendindividualdecisions(harddecisions)ortheirmeasuredvalues(softdecisions).Inanycase,theprocessingcenterwillberesponsibleforthedecisionfusionprocessnecessarytoarriveatasingledecisionforthewholenetwork.Inanestimationproblem,severalmethodshavebeenpro-posedthatexploitthephysicalbehavioroftheeventbeingmeasured.Themostimportantcharacteristicformanyeventsisthecorrelatednatureofthemeasurementsatdifferentnodes.Thisnaturehasbeenobservedineventswherethequantitytobeestimatedvariessmoothlyinaspatialdomain(i.e.acousticsignalpower,pressure,temperature,etc.).Themostrecentapproachestodistributedestimationexploitthischaracteristicinanefforttoreducetheamountofcomputationand,especially,theamountofcommunicationrequiredforthevaluefusionneededfortheestimationproblembyreducingtheamountofredundantdatacollectedbytheprocessingcenter.Alsorelevanttotheestimationproblemistheaccuracyoftheestimate.Thisaccuracyisaffectedbothbythechar-acteristicsoftheeventbeingmeasured,theaccuracyofthesensors,thespatialdensityofthesensorsandthecommuni-cationbandwidthavailable.Itisdesirable,then,toadjustadeploymentstrategyaroundthedesiredestimationaccuracy,whichmaybedifferentfordifferentlocationswithintheareabeingmonitored.Inanycase,theamountofinformationthatcanflowthroughthenetworkednodeswillberestrictedbythenetworkcapacity.Thenetworkcapacitywillalsobedependentonthecommu-nicationbandwidth,theamountandspatialdensityofnodesinthenetwork,andthehierarchyusedforthecommunicationnetworkscheme.Theseproblemshavebeenaddressedbyseveralresearchersinrecentyears,withseveraldifferentapproachesbeingpro-posed.Inthispaper,asurveyofthesemethodsiscompiled,withspecialemphasisontheareasofdistributedestimationscheme,distributeddetectionschemesandDWSNcommuni-cationschemesandcapacitybounds.Theseproblemsremainoneofthemainareasofinterestininformationprocessinginsensornetworks,andfurtherresearchisbeingconductedtocreatealgorithmsthatwillexploittheeventcharacteristicstoreducethepowerexpenseinsensornetworksandtoincreasetheaccuracyofthemeasurementsanddecisionsobtainedfromthem.Therestofthepaperisorganizedasfollows.SectionIIfocusesonapproachesfordistributedestimation.SectionIIIfocusesonapproachesfordistributeddetectionandclassifi-cation.SectionIVfocusesoncapacityanddistortionanalysisforsensornetworkarchitectures,andSectionVfocusesonproposedcommunicationschemesforDWSNs.II.DISTRIBUTEDESTIMATIONINDWSNA.RobustDistributedEstimationinSensorNetworksusingtheEmbeddedTrianglesAlgorithmDelouille,NeelamaniandBaraniuk2haveproposedamethodthatminimizesthemeansquareerroroftheestimatebyusinganiterativealgorithm.InsteadofhavingallthesamplestransmittedtoacentralprocessorandusingnormalestimationtechniquessuchasWienerFiltering(withcom-plexityO(N2),whichrequiresalargecommunication,theestimationisdividedamongsmallergroupsofnodeswhichwillinterchangetheirmeasurementstocometoasetofestimates.ECE736:WIRELESSCOMMUNICATIONS2ThesensornetworkismodeledasundirectedgraphG,wheresensorsappearasnodesandsensorswithcorrelatedmeasurementsarejoinedbyanedge.Eachsensorsisasso-ciatedwithahiddenvariablexsandanoisymeasurementys.Then,thevectorxisassumedtobexN(0;),andthenoisymeasurementwillbemodeledasy=x+,N(0;R).Here,theminimummean-squareerrorisprovidedbyp(xjy)=N(x;),andcomputedfromVx=R1y(1)whereV:=1+R1and=V1.Sincexisasmoothly-varyingGaussianrandomvector,theauthorschooseaGaussianHiddenMarkovModeltomodelthenoisymeasurementvectory.Thedecorrelatednoisyvectory=R1yisusedtogetherwitha”splitting”ofthematrixV=JKusingtheJacobialgorithmandthefollowingiterationalgorithmtosolveequation(1),whichcanberewrittenasJx=R1y+Kx:mthStepUpdate:Nodessendsitscurrentestimatexm1stoitsneighborsj2N(s)andreceivesthecurrentestimatesxm1jfromthesameneighbors,itthencalculatesitsestimateys=ysPt2N(s)Vstxm1t.mthStepSolve:xms=V1ssys8s2GTheJacobialgorithmsetsJtobeequaltothediagonalofK.Thisalgorithmconvergesslowlyingeneral,butitiseminentlylocal.TheJacobialgorithmisusedtogetherwiththeEmbeddedTreesalgorithm,inwhichtheinversionofthematrixisperformedbyusingamessagepassingalgorithmalongtheminimumspanningtreecorrespondingtoG.ThecombinationofthesetwoalgorithmsiscalledtheEmbeddedPolygonsAlgorithm(EPA),whichusestheJacobialgorithmatthelocallooplevelandtheembeddedtreesalgorithmatthegloballevel.Thegraphisseparatedintothesetdisjointloops:=fkgMk=1,whichcanbesingletons,pairs,triangles,etc.,dependingonthenumberofnodesineachloop;fortheembeddedtrianglesalgorithmitisassumedtheseloopshaveatmostthreenodes.Inthisfashion,thediagonalmatrixcanbereorderedsothatitbecomestheblockdiagonalmatrixJ=264A1000.000AM375(2)whereAkisthesubmatrixofVcorrespondingtothenodesink.Inthisway,aproposedmodifiedparallelblock-Jacobialgorithmasfollows:mthStepEPAUpdate:Eachnodescomputestheupdateym=y+Kxm1bycommunicatingwithallitsneighborsexceptthosebelongingtothesameembeddedpolygon.mthStepEPASolve:Withineachembeddedpolygonk2,thenodess2kexchangetheirupdatedvaluesymsamongstthemselves.Eachpolygonthecomputesxmk=A1kymkinparallel(Notethatthesingletonsdonotcommunicateinthisstep).Duringinitialization,eachnodebelongingtokgatherstheinformationaboutAkfromitsneighborsandcomputesandstorestheinverseA1k.Forthealgorithmtoberobustagainstcommunicationerrorsandsleepingnodes,eachsensorwillsavethelastreceivedvalueymsfromeachofitsneighborstouseitincasenofurtherupdatesarereported.Itisprovedthatifthedelaytimebetweeniterationsisboundedandnodesareupdatedastimegoeson,theembeddedtrianglesalgorithmconverges.Thealgorithmscomputationtimeisnotaffectedbythesizeofthenetworksincetheprocessingisdoneinparallel.B.DistributedOptimizationinSensorNetworksRabbatandNowak3introduceadistributedestimationalgoithmthatusesanincrementaloptimizationprocesstoarriveattheparameterestimateforallnodesthroughoutthenetwork.Asensornetworkwithnnodescollectsmmeasurementsineachnode.xi;jrepresentsthejthreadingfortheithsensorandrepresentstheparametertobeestimated.Ifalocalcostfunctionfidependentonallthereadingsofthesensoriandtheparameterisdefined,thenthepurposeofthedistributedestimationalgorithmistominimizetheaveragecost:=argmin21nnXi=1fi(fxi;jgmj=1;)(3)Thefunctionsfi()(forshorthand)mustbeconvexandmustbeanon-empty,closed,convexsubsetofRd.Forsuchfunctions,asubgradientoffat0isdefinedasanydirectiongsuchthatf()f(0)+(0)Tg(4)andthesubdifferentialoffat0,denotedf(0),isthesetofallsubgradientsoffat0.Equation(3)issolvedbyusingiterativegradientdescentasfollows:(k+1)=(k)finXi=1gi;k(5)wheregi;k2fi(k),fiisapositivestepsizeandkistheiterationnumber.Adecentralizedincrementalapproachisproposedinwhicheachupdateiterationisdividedintoacycleofnsubiterations,andeachsubiterationfocusesonoptimizingasinglecomponentfi().If(k)isthevectorobtainedafterkcyclesthen(k)=(k)n(6)where(k)nistheresultofnsubiterationsoftheform(k)i=(k)i1figi;k;i=1;:;n(7)withgi;k2fi(k)i1)and(k)0=(k1)n:Foraconstantstepsizefiandassumingthatanoptimalsolutionexistsandthatthereisascalar0suchthatjjgi;kjjforallsubgradientsofthefunctionsfi(),i=1;:;nand2,itisguaranteedthatafterKcycles,min0kKf(k)f()+fi2(8)ECE736:WIRELESSCOMMUNICATIONS3whereK=$jj(0)jjfi22%(9)Theenergysavingsratiobetweentheuseofanincrementaloptimizationalgorithmandacentralizedoptimizationalgo-rithmisshowntobeR=c3mn1=d2(10)fornnodeswithmreadingseach,amaximumestimationerror,dthenumberofdimensionsthesensornetworkisdeployedin,andc3istheratiobetweenthenumberofbitsrequiredtodescribetheparametervectorandthemeasure-mentsizeinbits.Thus,asthenumberofreadingsornodesinthenetworkincreases,itwillbecomemoreadvantageoustouseanincrementalalgorithmforprocessing.C.LocallyConstructedAlgorithmsforDistributedComputa-tionsinAd-HocNetworksSherberandPapadopoulos4proposealgorithmsfordis-tributedestimationanddetectionoveranetworkwitharbitrarybutfixedconnectivity.Thealgorithmsaredevelopedaslineardynamicalsystemsthatgeneratesequencesofapproximationsthatconvergetothedesiredcomputation.MostofthesetaskscanbeexpressedasafunctionG(x)ofthevectoroftherecordeddatax=x1x2:xNT.ThefunctiongeneratesateachnodeinthenetworkasequenceofapproximationstoG(x).TheN-nodetopologyofthenetworkisrepresentedbythematrixwherefori6=j,ij=1ifnodesiandjcommunicatedirectlyandij=0otherwise;forconvenience,ii=Pj6=iij,suchthatjiijcorrespondstothenumberofnodesindirectcommunicationwiththeithnode.Foraconnectednetwork,itisobviousthatforalli,ii6=0.Also,hasoneeigenvalueequaltozero,whiletheotherN1eigenvaluesarenegative.AdistributedrulesetisdefinedasthesetofrulesfF(n)jgNi=1;n0suchthatxjn+1=F(n)j(xj;fxik;kn;ij=1g)(11)i.e.,theestimateattimen+1isafunctionofthevaluereadatthenodesandtheestimatesofitsneighborsforallpreviousapproximations.Thesetofrulesislimitedtolinearadmissiblerules,wherexn=Xk1Wn;kxnk;n0(12)wherexn,x1n:xNnTandWn;kisanNNadmissiblematrixkernel.Tomeettheconditionsinequation(11),theconditionWijn;k=0ifij=0mustbemet.AdistributedruleisdefinedasasymptoticallyconvergingtothefunctionG(x),iflimn!1jjxn1G(x)jj=0(13)wherejjjjistheEuclideannormand1isanN1vectorofones.Theseadmissibleruleswillbelocalinthesensethattheyonlyrelyontheestimatesoftheneighborsofeachnode(givenbythecorrespondingrowin,butnotinthefullnetworktopology.Somerulesarederivedforexamplecases.Forthecasewhenitisdesiredtocalculatethemeanofthemeasurements,i.e.G(x)=1N1Tx(14)theauthorsproposeafirst-orderadmissibleLTIrule,whereWn;k=Wk1,andinthiscase,equation(12)reducestoxn=Wxn1(15)initializedbyxn=x,thevectorofsensorreadings,forn0.ThesequencexnconvergesifthesumoftherowsandcolumnsofWequals1,andforthesetofeigenvaluesofW,fig;1iN,j=max1iNi=1andjijP(xjk)foranyk6=k.Asxisperturbedwithhigherbackgroundnoise,itismorelikelythatthemarginP(xjk)maxk6=k(P(xjk):(23)ECE736:WIRELESSCOMMUNICATIONS5Distance,MetersSNR,dB501001502002503003504004505101520253035404550Fig.2.Probabilityofcorrecttargetclassificationversusdistancebetweenssensornodeandthetargetandthesignaltonoiseratio.Darkermarksrepresenthighercorrectclassificationprobabilitywillshrink.Assuch,theprobabilityofmisclassificationwillincrease.ThelevelofnoisecanbedeterminedcalculatingthesignaltonoiseratioSNRdB,andshouldbeinverselyproportionaltothedistancebetweenthenodeandthevehicle.Figure2showsthedistributionofcorrectlyclassifiedsamplesasafunctionoftheSNRdBandthevehicletonodedistance.Itisquiteclearthatasthetarget-sensordistanceincreasesandthesignaltonoiseratiodecreases,theprobabilityofcorrecttargetclassificationdecreases.Infact,thisprobabilitydroppedbelow0.5whenthetarget-sensordistanceisgreaterthan100meters.Ifthetargetpositionestimatedinthelocalizationtaskisrelativelyaccurate,itispossibletousetheestimatedtargetlocationandknownsensorcoordinatestocalculatethetarget-sensordistance.Then,onemayestimatetheempiricallyde-rivedprobabilityofcorrectclassificationataparticularsensornodebasedonthedistanceinformation.Letx(i)denotethefeaturevectorobservedattheithsensornodewithintheregion,Ckdenotesthekthtypeofvehicle,thegoalistoidentifyafunctionf()suchthatP(x2Ckjx(1);:;x(N),P(x2Ckjx)f(gk(P(x2Ckjx(i);1iN):(24)Wheregkisthemaximumfunctiong(zk)=1ifzkzj,k6=j,andg(zk)=0otherwise.Hence,thisap-proachisknownasdecisionfusion.Conventionally,therearetwobasicformsofthefusionfunctionf.Ifthemeasurementsx(i)areassumedtobestatisticallyindependentfeaturevectors,thenthemultiplicativeformisused:P(x2Ckjx)=NYi=1P(x2Ckjx(i):(25)Thisapproachisnotrealisticinthesensornetworkap-plicationandcannotbeeasilyadaptedtoadecisionfusionframework.Thedecisionfusionfunctionisrepresentedasaweightedsumofthemarginalposteriorprobabilityorlocaldecisions:P(x2Ck)=NXi=1wigi(P(x2Ckjx(i):(26)Abaselineapproachofregion-baseddecisionfusionwouldbesimplychoosewi=1for1iN.Thiswouldbecalledthesimplevotingfusionmethod.Withdistance-baseddecisionfusion,eachoftheweightingfactorswiinequation(26)isafunctionofdistanceandsignaltonoiseratio,thatiswi=h(di;si)wherediisthedistancebetweentheithsensorandthetargetandsiisthesignaltonoiseratiodefinedasSNRdB=10log10EsEnEn:(27)whereEsisthesignalenergyandEnisthenoisemeanenergy,bothdeterminedbytheCFARdetectionalgorithm.ThecharacterizationexplainedearliercanbeusedtoformulateaMaximumAPosterior(MAP)ProbabilityGatingnetwork,usingtheBayesianestimationP(x2Ckjx)=P(x2Ckjx;di;si)P(di;si):(28)ThepriorprobabilityP(di;si)istheprobabilitythatthetargetisatthedistancerangedi,andtheacousticsignalSNRdBisatthesirange,andcanbeestimatedempiricallyfromtheexperiments.TheconditionalprobabilityP(xjdi;si)isalsoavailablefromtheempiricallygathereddata.Withthese,thefollowingweightsinequation(26)maybeassignedas:wi=P(xjdi;si)P(di;si):(29)Inotherwords,ifaparticularsensorsclassificationresultisdeemedaslesslikelytobecorrect,itwillbeexcludedfromtheclassificationfusion.Thereareotherpossiblechoicesofwi.Thatis,wi=1diTNQ=1,thenthereexistsakernel(t)bandlimitedto;suchthatC:=supl2R(Pnjflfltnflfl1;8n2Z2)signdn=signdn+1;8n2Z3)d(t)isdifferentiableand:=supt2Rjd0(t)j0thereexistsafiniteblocklengthlsuchthattheexpecteddistortionforallnodesislessthanorequaltoD+.Whenquantizationisconsidered,thequantizedvaluescanbethoughtofasindependentrandomvectorUwithprobabil-itypUjYwhenconditionedonY,anditsrateanddistortionisgivenbyFig.6.Structureforsensorencodersanddecoderstoachievethebestrate-distortionperformanceRk(pUjY):=1kH(U1;:;Uk)KXi=1H(UijYi)#(41)Dm(pUjY;gm):=Ed(X;gm(Ui1;:;Uim)(42)wheregm:Um!X;kmn.Consideringthatthequantizationisthesameinallnodes,H(UijYi)isthesameforallnodesandtheexpecteddistortiononlydependsonm,gmandpUjY,notonthevaluesi1;:;im.ThepaperprovesthatifRRk(pUjY)andDDm(pUjY;gm)8mk,thenforrateR,thedistortionlevelDisachievable.Toachievetherateanddistortionlevel,theencodingissplitamongtwounits;al-blockquantizerunitwithrateR0matchedtothestatisticsofthesensormeasurements,andarandombinningunitthatexploitsthecorrelationbetweenthequantizedobservationsacrossdifferentsensorstogetarebateofR0Rbitspersample.Thedecoder,then,firstreconstructsthequantizedsensorobservationsfromthebinindicesfordifferentsensorsandthenformsthebestestimateofthephysicalprocessofinterest,asshowninfigure6.V.COMMUNICATIONSCHEMESFORDWSNA.Source-ChannelCommunicationinSensorNetworksGastparandVetterli11considertheusualarchitectureinwhichthedatacodingproblemissplitbetweenthesensors,whoperformlocalcompressionoftheirsignals,andthechan-nelcoding,withthepurposeofcommunicatingthecompressedvalueswithouterrors.Thisschemeleadstosuboptimalper-formanceingeneralnetworktopologies.Thepaperproposesajointsource-channelcodingschemeforaspecificclassofnetworks,andsuggeststhattheoptimalschemefornetworksoutsidethisclasswouldbetoapproachtheperformanceoftheclassofnetworkstreated.TheL-nodesensornetworkclassusedinthepapermodelsthephysicalphenomenonasthesequenceofrandomvectorsSn:=fSngn2Z=f(S1n;:;SLn)gn2Z(43)Here,sdenotestherealizationofS,withdistributionPS(s)orP(s)forshorthand.Thesensorsobservease-quenceUnk=fUkngn2Zwhichdependsonthephysicalphenomenonaccordingtotheconditionalprobabilitydistribu-tionP(ukjs1;:;sL).Basedontheobservations,sensorktransmitsasignalXnk=Fk(Unk)onthemultiaccesschannel,ECE736:WIRELESSCOMMUNICATIONS10Fig.7.Thesensornetworktopologyconsideredin11withaglobalenergyconstrain.ThesefunctionsareusedintheprocessingcentertogenerateestimatesofthesourcemeasurementsSn=(Sn1;:SnL).Suchamodelisshowninfigure7.InaGaussiancase,asinglesourcesignalisobservedbyeachoneoftheMsensorstogetherwithindependentwhitegaussiannoise:Ukn=Sn+Wkn,wherefSngnisasequenceofi.i.d.Gaussianrandomvariablesofvariance2sandfWkngnisasequenceinn=1;2;3;:ofi.i.d.Gaussianrandomvariablesofzeromeanandvariance2w;theseseriesareindependentfordifferentnodes(k6=l).TheenergyconstraininthiscaseforthetransmittedsignalsisPMk=1EjXkj2MP,andthefinaldestinationreceivesYn=MXk=1Xkn+Zn(44)whereZniswhitenoiseofvariance2Z.Inthiscase,thedistortionmeasureistheMSE:D=PMj=1EjSnSnj2.ThegoalthenistocalculatetheminimumdistortionforagivenpowerconstrainMP.Theperformanceofaschemeisanalyzedintwosteps:therate-distortionandthecapacity-costproblem.ThefirstproblemtobetreatedisknownastheCEOproblem,anddealswiththeencodingschemeneededineachsensortoencodeitsobservationsintoabitstreamofRkbitspersample.Itisdesiredtofindthesetofsmallestvalues(R1;:;RM)thatpermitreconstructionofSataspeci